Remember back to when we spoke about the C runtime environment and the
XINU memory model. Memory in XINU is organized with free memory in between
the heap and the stacks. The heap grows into free memory from low addresses,
and stacks are allocated into free memory from high addresses. This organization
is shown below:
All of the free memory is kept on one list. The list is ordered by address from lowest to highest. The list is a singly-linked list made of structures (mblocks) which contain only two fields: the length of the free block, and a pointer to the next free block. These structures are kept in the free blocks themselves, so no extra memory is required to keep track of free memory.
XINU memory allocation is first fit for heap storage, and backwards first-fit for stack storage. Remember that both of these allocate from the same list. Remember also that since the free memory list is singly-linked, both allocation routines have to start searching from the same end. You'll see in a moment that this is somewhat inefficient. A better approach would have the free memory list be doubly-linked and the getstk() routine start searching from high addresses down.
One more thing to consider in the allocation and freeing routines is that we must be careful to never leave a free hunk of memory that is too small to hold the structure (an mblock) that describes a free memory block. Thus all requests are rounded up to an even multiple of mblocks. Also, the total free space must initially be a multiple of mblocks.
