The Heap Allocator

(CORE/HEAPALLOCATOR.JAVA, CORE/EXPLICITFREEALLOCATOR.JAVA )

The SaM memory allocator is responsible for managing the heap. It must support reserving chunks of memory of a particular size, and reclaiming the space later, without fragmentation.

The current allocator is based on the Doug Lea's malloc allocator: Doug Lea's malloc allocator http://gee.cs.oswego.edu/dl/html/malloc.html, or rather the high-level description of it. The implementation was written independently, and was simplified for our purposes.

Access Interface

The heap allocator supports the following methods:

• void init () - initialize the state of memory
• void malloc (int size) - allocate a memory chunk of the requested size, and place its address on the stack
• void free (int pos) - free a previously allocated memory chunk
• Iterator<HeapAllocator.Allocation> getAllocations () - obtain an iterator for all allocations
• Memory getMemory () - obtain the Memory object associated with this allocator
• void setMemory(Memory mem) - set the Memory object for this allocator

Design

The allocator's main feature is the division of memory space into chunks (slices) with power-of-two sizes. Those chunks are grouped together into linked lists with other chunks of the same size. The linked list is attached to an "anchor," whose memory offset from the base of the heap corresponds to $\log_{2}$(size) of chunks contained within - this makes it trivial to locate chunks of a required size, using simple bitwise algebra. Offset 0 is special, and contains chunks of various sizes that have already been allocated. Each memory chunk includes accounting metadata before and after the actual space visible to the user. This is used internally to maintain the linked lists, and for error detection.

malloc:

When a chunk of size x is requested, x is rounded to a power of two, and the anchor is traversed looking of free memory of that size, or larger (by a factor of 2 for each anchor index). If no such slice is found, exception is thrown (OMEM). If a slice is found, it is disconnected from the linked list. The slice is cut back to the smallest power-of-two slice sufficiently large to contain the requested allocation. The remainder is distributed throughout the anchor as free space. The allocated chunk's metadata is updated to reflect how large it is, and what the neighbor chunks are, and the user-visible address of it (past the metadata) is returned by malloc.

free:

When a chunk is freed, it is removed from the list of allocations and it is merged together with preceding free chunks and following free chunks. This process prevents fragmentation of memory - it reassembles small chunks into larger ones, which allow the allocator to handle larger requests. There may be more than one consecutive free chunk, because, after the chunks are merged, the result is cut and redistributed back into bins of various sizes. Unless the result was an exact power of two, this may cause multiple consecutive free chunks to exist in memory. However, the distribution algorithm makes sure that this number is bound by the size of the anchor, which ensures that free is kept O(1).

getAllocations:

An interesting consequence of keeping the list of allocations in anchor 0 is that we can iterate this list. This function returns a Java iterator (in O(1)) which allows a debugging program to iterate the contents of memory, if necessary. This can be useful, for example, to check for memory leaks (if any allocations remain).

Notes:

Enable the constant DEBUG_ALLOCATOR to print the allocator bins after every malloc and free call.

This allocator was successfully translated to SaM assembly from an enhanced version of the Bali language in Spring 2005. It executed correctly, at about 100% overhead. The compiler and the code may be found in the SVN repository for 2005sp/part3c.

Further Work:

While power-of-two blocks simplify computations, and are easy to manipulate, the allocator is extremely wasteful on requests of size 2k + c for large k and small c. To address this, a better distribution of bin sizes should be designed - this is an opportunity for future improvement of SaM.