memory management

[Stefan Reinauer]

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