malloc4 is a small system for managing memory allocations, much like the UNIX/Linux malloc system call.
The system divides up the heap space into chunks, maintaining a linked list of empty chunks. A cleanup process is run periodically, which joins together adjacent empty chunks.
NN-byte integer that uniquely references a byte within the heap.
N-byte value that is different from any value that represents a valid address in the heap. The same value must be used for all occurrences of null, in the context of this allocation system.
N-byte integer that represents the size of the chunk body, in bytes.
malloc and passed to free are pointers to chunk bodies.
malloc and is now in control of user code.
free.
N-byte variable/register/memory location holding a pointer to the first chunk in the free chunk list.
N-byte pointer to the next chunk in the free chunk list. It is stored in first word of a chunk’s body.
When the system is started, a short initialisation procedure must occur. This consists of three steps:
N-byte word in the heap to the size of heap minus N.N-byte word in the heap to null.These steps create a single chunk in the heap, starting at the first available address and extending to the end of the heap. The head pointer is set to point to this chunk. The length of this chunk is the size of the heap minus N, since it is the length of just the chunk body (which contains the word set in the third step, but not the word set in the second step). The next-pointer for this chunk is set to null to mark the end of the list.
init() {
head ← HEAPSTART
[HEAPSTART] ← HEAPSIZE - N
[HEAPSTART + N] ← NULL
}The first step in allocation is to round the requested allocation size up to the next multiple of N. This ensures that all chunks start on N-byte boundaries, which on some machines speeds up multibyte memory accesses.
The algorithm then iterates through the free chunk list. The size of each chunk is fetched and compared against the requested allocation size.
Z) of words (i.e. if chunksize >= reqsize + Z*N), a slice occurs.chunksize >= reqsize), a fit occurs.If the end of the free chunk list is reached without either a slice or fit event occurring, then there are no free chunks large enough and so the system can be considered to be out of memory. The system may run a coalesce (described in later sections) and then try the allocation algorithm again before reporting an error condition.
A slice event means that the current chunk is fairly large in comparison to the requested allocation size, and so the chunk will be split into two. One will be used as the return value from malloc whilst the other will be returned to the free chunk list.
The parameter Z (seen in the condition expression in the list above) determines the minimum number of words that the size of the current chunk must exceed the allocation size by. It can be assigned any value greater than one (since a chunk must have a total size of at least two words). A typical value for a processor with a small amount of memory is 9 (to leave room for a chunk with an 8 word body).
To perform a slice:
p bytes, where p is equal to the requested allocation size plus N. This creates room for a new chunk with a body size equal to the requested allocation size.A fit event means that the current chunk is just large enough for the requested allocation size.
To perform a fit:
null), the next-pointer of the previous chunk is set to null as well.malloc(size) {
-- Round size up to word boundary
size = (size + N - 1) & -N
last_chunk ← NULL
this_chunk ← head
while this_chunk != NULL {
this_chunk_size ← [this_chunk]
next_chunk ← [this_chunk + N]
if this_chunk_size >= size + Z*N {
-- slice
this_chunk_size ← this_chunk_size - size - N
[this_chunk] ← this_chunk_size
new_chunk ← this_chunk + N + this_chunk_size
[new_chunk] ← size
return new_chunk + N
}
else if this_chunk_size >= size {
-- fit
if last_chunk == NULL {
head ← next_chunk
}
else {
[last_chunk + N] ← next_chunk
}
return this_chunk + N
}
else {
last_chunk ← this_chunk
this_chunk ← next_chunk
}
}
-- Out of memory
return NULL
}Allocated chunks are deallocated by adding them to the free chunk list. Since the free chunk list is to be kept sorted, the system iterates through the list until it finds a suitable place to insert the chunk, then insert it. This mechanism also allows the condition of an already unallocated chunk being passed to free to be detected and handled.
free(ptr) {
insert_chunk ← ptr - N
last_chunk ← NULL
this_chunk ← head
forever {
if insert_chunk == this_chunk {
-- Already unallocated, or NULL.
return
}
else if this_chunk == NULL || insert_chunk < this_chunk {
if last_chunk == NULL {
-- Insert insert_chunk at start of list.
head ← insert_chunk
}
else {
-- Insert insert_chunk between last_chunk and this_chunk.
[last_chunk + N] ← insert_chunk
}
[insert_chunk + N] ← this_chunk
return
}
else {
last_chunk ← this_chunk
this_chunk ← [this_chunk + N]
}
}
}Coalescing is the process of joining together adjacent free chunks in order to increase their mean size. The system iterates over the free chunk list, merging any two directly adjacent chunks into one larger one.
coalesce() {
this_chunk ← head
while this_chunk != NULL {
this_chunk_size ← [this_chunk]
next_chunk ← [this_chunk + N]
if this_chunk + N + this_chunk_size == next_chunk {
-- this_chunk and next_chunk are directly adjacent
next_chunk_size ← [next_chunk]
-- Expand this_chunk to also contain next_chunk's header & body.
[this_chunk] ← this_chunk_size + N + next_chunk_size
-- Copy next-pointer from next chunk to this chunk.
[this_chunk + N] ← [next_chunk + N]
-- Do not move this_chunk forward since we may be able to
-- coalesce again.
}
else {
this_chunk ← next_chunk
}
}
}