It’s been a while since the last edition (I do say this every time). Behold, a seventh article!
Allow me to restate the prerequisites:
- Proficiency in C
- Understanding of the Stack vs Heap
- Familiarity with this article’s predecessors (all of them).
Disclaimer: what follows are my findings, and my own personal implementation of free(). Do not expect another person’s free() to follow the same logic or routine.
Logic Walkthrough
void my_free(void *ptr);
ptr is expected to be an address previously returned by my_malloc. Note: This function will not be able to correctly or safely free memory allocated by another utility.
Using some pointer arithmetic, my_free() finds the relevant chunk containing ptr's metadata. Let us reexamine what a chunk looks like:
typedef struct _chunk {
size_t _chunk_sz;
struct _chunk *next,
*prev,
*next_free,
*prev_free;
_free_t _free;
} _chunk;
In the above struct declaration, _free_t is a type I defined. It’s merely an enum that I use as a flag to… you guessed it: tell whether or not a chunk is free.
As you might expect, one of the things my_free does is alter this flag.
Each chunk also contains next_free and prev_free attributes that make up a doubly-linked list. This doubly-linked list is used to “remember” which chunks are free. Note: next and prev are meant to point to memory-adjacent chunks, but next_free and prev_free are not guaranteed to point to adjacent memory; rather, these pointers are used to speed up access to free chunks so that we can avoid looking at chunks that are already in use.
my_free() inserts this newly-freed chunk at the end of the freed chunks linked list. This means that the freed chunks list is not sorted.
There is also one more optimization. If the chunks to either side (memory-adjacent) of this now-freed chunk are free as well, the chunks will be merged. I have written a subroutine to handle this (mainly because linked-list pointer gymnastics look so ugly).
Example
Imagine we have some memory laid out like so (I apologize in advance for the bleh-ness):
In the above photo, assume that the session struct is stored in memory somewhere to the left of A and the program break is somewhere to the right of E.
Our linked list of all chunks is {A,B,C,D,E}. Our linked list of freed chunks is {A,D}.
A user now calls my_free to request the deallocation of C:
C is marked as FREE. While our linked list of all chunks remains the same, our linked list of freed chunks becomes {A,D,C} (remember that newly-freed chunks are just inserted at the end).
my_free realizes that C and D, adjacent chunks, are both free. To adhere to the program design, C and D must now be merged. As C is before D, it will absorb D’s space in memory, essentially making one larger C:
In merging C and D, D is removed from the all chunks linked list, making that list {A,B,C,E}. The free chunks list now becomes {A,C}. The memory session decrements its count of chunks. D no longer exists as its own entity.
I hope this helps you, @_py.
Implementation
Don’t worry. It’s just fifty lines.
void my_free(void *ptr) {
// 1. Calculate chunk's address.
_chunk *c = (_chunk*)((char*)ptr - sizeof(_chunk) );
// 2. Check chunk's validity
if ( c < _session->_first_chunk || c > _session->_last_chunk + _session->_last_chunk->_chunk_sz) {
fprintf(stderr, "[!] Invalid Free! %p is out of range!\n", ptr);
return;
}
// 3. Ignore chunk if it's free already.
if (c->_free == FREE)
return;
// 4. Mark chunk as free.
c->_free = FREE;
// 5. Put chunk into free chunk list.
if ( !_session->_first_free_chunk ) {
/* if there are no chunks... */
_session->_first_free_chunk = c;
_session->_last_free_chunk = c;
c->prev_free = NULL;
c->next_free = NULL;
} else {
if (_session->_last_free_chunk) /* just in case... */
_session->_last_free_chunk->next_free = c;
c->prev_free = _session->_last_free_chunk;
_session->_last_free_chunk = c;
}
// 6. Do chunk merging:
if (c->next != NULL && c->next->_free == FREE)
_merge_chunks(c, c->next);
// 6(b) Merge other side, if needed.
if (c->prev != NULL && c->prev->_free == FREE)
_merge_chunks(c->prev, c);
}
I have left notes in the code snippet. If you’re confused, feel free to comment a question.
Conclusion
There are many things that can be done differently in this implementation:
- Newly-freed chunks could be inserted into the freed chunks list by size to speed up allocation lookups.
- The session’s chunk list could be traversed to ensure that the chunk point is valid. Right now, only a range check is performed. Linear search can be costly, and binary search is out of question for several reasons.
- One notable optimization is the use of a freed chunks list, but the freed chunks list could be omitted. In its place, the entire list of chunks (free or not) could be scanned. The freed chunks list trades space for speed, however, and most computers can sacrifice a few bytes of RAM (* insert jab about Java here *).