It’s been a while since the last edition (I feel like I say this every time). What you’re looking at is the sixth installment of my [C] Dynamic Memory Series.
I’ll start this paper by enumerating some prerequisites:
- Proficiency in C
- Understanding of the Stack vs Heap
-
Understanding of
sbrkandbrk. - Familiarity with this article’s predecessors (all of them).
As always, the above is merely a suggestion.
One last thing: What follows is more a writeup of my findings and experience than a tutorial.
Adapting the headers
Before I introduce the actual code, it is paramount that we take a look at the headers.
/*
my-malloc.h
*/
#include <stddef.h>
#ifndef MY_MALLOC_HDR
#define MY_MALLOC_HDR
typedef enum _free_t {
NOT_FREE, FREE
} _free_t;
typedef struct _chunk {
size_t _chunk_sz;
struct _chunk *next,
*prev,
*next_free,
*prev_free;
_free_t _free;
} _chunk;
typedef struct _mem_session {
_chunk *_first_chunk,
*_last_chunk,
*_first_free_chunk,
*_last_free_chunk;
size_t _chunks_allocated;
} _mem_session;
/* ... */
#endif
I’m using an enum (Google if necessary) to denote whether or not a chunk is free or not.
The main thing that has changed in this code is the way free chunks are handled in memory. In addition to having a linked list for all of the chunks, there will also be a linked list exclusively for free chunks. Both of the above struct declarations have been updated in accordance with this new concept.
The logic of my_malloc()
Function prototype:
void* my_malloc(size_t bytes);
My implementation takes a single parameter, bytes, denoting the number of bytes the user has requested. This number bytes is rounded up to the nearest multiple of 4, which is the standard size of an int. At the top of the routine, bytes is modified to be a multiple of four.
The inaugural call to my_malloc does one extra step before proceeding to allocate memory for the user. It calls a special function called _create_session() that sets up a _mem_session. This _mem_session, which we will refer to as “session” from now on, has valuable, useful metadata about the heap. Included in the session data are the linked list pointers (all and free-only) as well as a size_t that keeps track of the number of chunks in the session. This session consumes 40 bytes of memory (four pointers and a size_t use that much on my machine). Not bad, eh?
Once the session is created (and it is only created during the first call to my_malloc(), the function tries to find some memory for the user. The first step in doing so is scanning the freed chunks linked list for any available chunks large enough to hold at least bytes bytes of memory.
If a free chunk is found, my_malloc() will prepare to return this memory to the user. First, however, my code will attempt to cut the chunk into two pieces following this logic: if there is enough space such that _chunk_sz is greater than the sum of bytes, the size of a chunk, and another 4, split the chunk in two.
There is always the possibility that no free chunk large enough to store bytes memory is found. If such is the case, my_malloc uses sbrk() to expand the program break by the sum of the size of a chunk and bytes.
Whether an existing chunk was reused or a new one was made, the end result is the same. my_malloc() returns a pointer offset. The user data begins at a sizeof(_chunk) offset from the pointer to the beginning of the chunk. This is what is returned.
Note: If something does fail during the my_malloc() call, (void*)NULL is returned.
Coding out my_malloc()
void *my_malloc(size_t bytes) {
if (!_session && _create_session() < 0) {
return NULL;
}
/* Round up to nearest multiple of 4. */
size_t cnt = (((bytes-1)>>2)<<2) + 4;
_chunk *c = _find_free_chunk( cnt );
if ( !c ) {
/* we will extend the program break if we can't
find a viable chunk at this time. */
void *ptr;
if ( (ptr = sbrk(sizeof(_chunk) + cnt)) == (void*)(-1) ) {
fprintf(stderr, "Couldn't allocate memory!!\n");
return NULL;
}
c = (_chunk*)ptr;
c->_chunk_sz = cnt;
c->_free = NOT_FREE;
c->prev = _session->_last_chunk;
c->next = NULL;
c->prev_free = NULL;
c->next_free = NULL;
if ( !_session->_first_chunk )
_session->_first_chunk = c;
/*
The current last chunk should have its
`next` attr point to c before we make the
last chunk in the session point to c.
*/
if ( _session->_last_chunk )
_session->_last_chunk->next = c;
_session->_last_chunk = c;
_session->_chunks_allocated++;
} else {
c->_free = NOT_FREE;
/* patch free chunks */
if (c->next_free && c->prev_free) {
/* runs if c is in the middle of the freed chunks list */
c->next_free->prev_free = c->prev_free;
c->prev_free->next_free = c->next_free;
} else if (c->next_free) {
/* runs if c is the first of the freed chunks list */
c->next_free->prev_free = NULL;
} else if (c->prev_free) {
/* runs if c is the last of the freed chunks list */
c->prev_free->next_free = NULL;
}
if (_session->_first_free_chunk == c)
_session->_first_free_chunk = c->next_free;
if (_session->_last_free_chunk == c)
_session->_last_free_chunk = c->prev_free;
/* end patching of free chunks */
/* -------------------------------------------- */
/* Can we shrink the chunk?
If so, let's create a chunk to handle the rest
of the memory, so that we don't take more than
we truly need. */
if (c->_chunk_sz >= cnt + (sizeof(int) + sizeof(_chunk) )) {
_chunk *d = (_chunk*)((char*)c + sizeof(_chunk) + c->_chunk_sz);
size_t extra = c->_chunk_sz - cnt - sizeof(_chunk);
c->_chunk_sz = cnt;
d->_chunk_sz = extra;
d->_free = FREE;
if ( !_session->_first_free_chunk )
_session->_first_free_chunk = d;
if ( _session->_last_free_chunk )
_session->_last_free_chunk->next_free = d;
d->prev_free = _session->_last_free_chunk;
_session->_last_free_chunk = d;
d->next_free = NULL;
d->next = c->next;
c->next = d;
d->prev = c;
_session->_chunks_allocated++;
}
}
/* return `c` offset by the size of a chunk,
resulting in a pointer pointing to the
beginning of user data space*/
return (sizeof(_chunk) + (char*)c);
}
There are a few things to take note of:
-
_find_free_chunk( cnt )is a subroutine I wrote out that… finds free chunks. It, as you would think, finds a suitable free chunk if there is one, or returnsNULL.
What takes place in the if ( !c ) block is the extending of the program break for a new chunk. It initializes the chunk’s metadata appropriately and links the chunk into the session’s linked lists.
The else block runs when we do find a free chunk. The found chunk is flagged as NOT_FREE. The chunk is removed from the free-only linked list. Then, if possible, the chunk is split up into two smaller chunks to save excess memory for usage elsewhere. The splitting involves some metadata initialization (like setting the size of chunk d and adjusting the size of chunk c). In addition, some linked list logic is done to ensure that the session knows about the new chunk.
As mentioned above, the last thing to happen is the returning of the pointer to the user data.
Conclusion
After reading this article, read it again. Ensure that you understand the code. Post a question if you must.
Then, I invite you to think of the upsides and downsides of this implementation. For example: how can we ensure that the user doesn’t write into the next chunk? do we really need the doubly-linked list stuff to manage the chunks properly? is there another way? should we manage the chunks by size for quicker access? should we pay more attention to allocation speed, rather than space-efficiency? what happens when we run out of memory?
The solutions to some of the problems listed above may already be clear to you. If so, post a suggestion! I have a few ideas in mind, as well, but I’m eager to hear your thoughts.