Hi,
After quite some silence I've checked in alloc-mem and free-mem today. I used a simple free list allocator that does, unlike a buddy allocator, not distinguish between different block sizes. The free list is always sorted by address range, thus allowing to allocate/insert with a worst case of O(n) (Due to using a linked list). This was the happy medium between having a pretty complex implementation giving optimal run time and ease of reading/debugging which is definitely something you want at this level.
The free list entries are kept in place, so no additional space outside the memory space is needed to do the house keeping. A free list entry looks like follows:
size | type -------------- cell | length of this entry cell | pointer to next entry len | memory itself.
When the memory is allocated, the pointer to the next entry becomes invalid, thus it is used as memory as well. Therefore the length field includes that cell in the usable memory area length.
On freeing, boundaries are checked against existing free list entries. If blocks can be merged, they are merged immediately in free-mem.
There's also a small test suite that shows it actually works.
the memory management stuff itself can be found in CVS at openbios/forth/base/memory.fs the testsuite is at openbios/forth/testsuite/memory-testsuite.fs
if memory-testsuite.fs and memory.fs are in the same directory, you can just call the test suite with
paflof < memory-testsuite.fs 2>/dev/null
(the 2>/dev/null prevents the dictionary dump at program end, because for quickhacked getting a usable memory area i allocated 256k dictionary space. In a working system the memory area to use will probably be parsed from the LinuxBIOS table)
Any comments are welcome.
Stefan