The SCI Heap

Heap structure

The original heap starts with 200 separate entries with a size of four bytes. Each of those entries appears to be a pointer to "hunk" memory, which is separate from the heap and not covered here. The actual heap base pointer points to the first byte that is not part of these pointers.

Memory handles

A memory handle consists of two consecutive unsigned 16 bit integers:

• The memory block size

• The heap address of the next memory handle

Memory handles are stored inside of the heap; they delimit the holes in the heap by indexing each other, with the exception of the last handle, which points to zero.

Initialization

The list is initialized to 0. Memory handle #0 is set to contain 0xffff minus the size required by the memory handles (800 bytes) to a total of 0xfcdf, the pointer to the next free index is set to 0x0.

Memory allocation

The memory allocation function takes one parameter; this is the requested allocation block size. If it is 0, the function aborts. Otherwise, the size is increased by 2 (and then again by 1, if it is odd, for alignment purposes).

After the memory allocation algorithm finds a sufficiently large memory hole, it allocates its memory by splitting the memory hole and allocating the lower part (or by swallowing the upper part if its size would be less than four). It adjusts the previous memory handle (which used to point to the start of the now allocated part of the heap) to point to the next hole, and then goes on to write its size to the first two bytes of its newly allocated home.

If no sufficiently large memory hole can be found, the function returns 0; otherwise, it returns a heap pointer to the start of the allocated block (i.e. to the two bytes that carry the block's size).

Memory deallocation does this process in reverse; it also merges adjacent memory holes to prevent memory fragmentation.