Yesterday I suggested that a Hare implementation a runtime system to implement memory management, fast data movement (our ATMEL AVR target has opcodes specifically for iterating over its RAM), & to crash the program (for embedded dev I'd trigger a breakpoint & reboot). The most complex of these being the memory management!
If we constrain outselves to supplying memory in powers-of-2, we could use Buddy Memory Management!
1/3?
In this scheme we track a doubly-linked-lists of each size, with an array holding theier heads. alloc() & free() can tweak the appropriate linkedlist, with alloc() falling back to allocating a larger amount of memory & splitting in half until we get the desired size.
Store the lengths of the next & previous chunks between any 2 of them so we can merge free chunks of the same size back together, thus countering fragmentation.
Our AVR target has a 16bit address-bus, so...
2/3!
An AVR target would require less than 16 of these linked lists, & a single nybble to store the size. Thus a single byte between chunks. As such the overhead's quite low on such memory-constrained systems!
The catch is that we need to flag used memory so free() doesn't attempt to merge its given chunk with them. The simplest solution would be flag their size as 0 & leaving it to the compiler to track the chunk's size to pass to free().
Though for more flexibility... How'd you implement it?
3/3
