Low-level Mechanisms
This lesson thoroughly discusses the low-level mechanisms used by memory allocators.
We'll cover the following...
Before delving into some policy details, we’ll first cover some common mechanisms used in most allocators. First, we’ll discuss the basics of splitting and coalescing, common techniques in most any allocator. Second, we’ll show how one can track the size of allocated regions quickly and with relative ease. Finally, we’ll discuss how to build a simple list inside the free space to keep track of what is free and what isn’t.
Splitting and coalescing
A free list contains a set of elements that describe the free space still remaining in the heap. Thus, assume the following 30-byte heap:
The free list for this heap would have two elements on it. One entry describes the first 10-byte free segment (bytes 0-9), and one entry describes the other free segment (bytes 20-29):
As described above, a request for anything greater than 10 bytes will fail (returning NULL); there just isn’t a single contiguous chunk of memory of that size available. A request for exactly that size (10 bytes) could be satisfied easily by either of the free chunks. But what happens if the request is for something smaller than 10 bytes?
Assume we have a request for just a single byte of memory. In this case, the allocator will perform an action known as splitting: it will find a free chunk of memory that can satisfy the request and split it into two. It will return the first chunk to the caller; the second chunk will remain on the list. Thus, in our example above, if a request for 1 byte were made, and the allocator decided to use the second of the two elements on the list to satisfy the request, the call to malloc() would return 20 (the address of the 1-byte allocated region) and the list would end up looking like this:
In the picture, you can see the list basically stays intact; the only change is that the free region now starts at 21 instead of 20, and the length of that free region is now just 9. Thus, the split is commonly used in allocators when requests are smaller than the size of any particular free chunk.
A corollary mechanism found in many allocators is ...