Designing Custom Memory Allocator : free()
This is the second blog on custom memory allocator design. In the first blog, we discussed about using a circular list as a bookkeeping mechanism that maintains a linked list of free or available blocks to help with allocation. In this blog, we will cover the details of a corresponding free() API design.
Like malloc() , even free() shall update the free list maintained to reflect the available blocks. When free() is called, it checks if the blocks adjacent to
the freed block (left or right sides), are also free :
• If so, adjacent free blocks are merged (coalesced) into a single, larger free block.
• Otherwise, the freed block is just added to the free list.
Implementation
To implement a free() API, we simply need to manipulate (or update) data structure (namely free list) maintained by the memory allocator to reflect free blocks.
There are three main cases to be handled in this list update process:
- if the
free()is called upon address at the end of the free list. - if
free()is called on an address that points to a chunk that can be coalesced into, on the right side. - if
free()is called on an address that points to a chunk that can be coalesced into, on the left side.
void myFree(void* allocatedAddress)
{
Header *curr,*prev;
curr=(Header*)allocatedAddress-1; // read header , address to be freed./* 1a) freed block at start or end of arena */
for(prev = pFree;!(curr > prev && curr < prev->next);prev=prev->next)
{
if(prev >= prev->next && (curr > prev ||curr < prev ->next))
{
break;
}
}if(curr + curr->size == prev->next)
/* 2a) stretch right side of curr, add curr to free list.
if prev->next is the exact end of curr one we are trying to free , prev --> next to prev -->[curr + next] */
{
curr->size += prev->next->size;
curr->next = prev->next->next;
}else{
/* 2b)if prev->next is the NOT exact end of curr, just link it to curr - no coalesce as above. */
curr->next = prev->next;
}if(prev + prev->size == curr)
/* 3a) stretch left side of curr. if prev->next is the exact start of curr one we are trying to free , prev --> next to [prev+curr] --> next] */
{
prev->size += curr->size;
prev->next = curr->next;
}else{/* 3b) if prev->next is the NOT exact start of curr, just link it to prev - no coalesce as above. prev-->next to [prev --> curr --> next */
prev->next = curr;
}pFree = prev;}
Complexity
Time complexity
free()involves just adding an entry to free list- it takes constant time O(1).
In the next blog in this series, we will look at a modified version of malloc() and free() that support “aligned” allocations.
If you liked reading this blog, don’t forget to drop some claps below to help reach more people. Thank you! :)
