I first started programming in c earlier this year. Coming from a background in Java, Python, and c++ I really didn't know anything about memory management. One of the first projects I was tasked to work on in my Operating Systems class was implementing malloc and free. For someone who barely knew what they do, much less how to use them, this seemed like a daunting task. First, lets briefly describe malloc and free: malloc is used to allocate some memory on the heap, i.e. a pointer, and free is used to free that memory. Here is some very basic usage:
//create a new int pointer the size of an int object int *test = malloc(sizeof(int)); //free the memory from that pointer so we can use it later free(test);
Clearly in order to implement malloc we need to return the address of a specific chunk of memory, and to implement free we need to be able to reuse the address for something else. In my version of malloc I chose to use a linked list for the free chunks of memory and a simple struct with header info for the allocated chunks.
typedef struct __header_t
{
int size;
int magic;
} header_t;
typedef struct __node_t
{
int size;
int magic;
struct __node_t *next;
} node_t;
We will also need to get a couple of other variables out of the way and grab a large chunk of memory (4kb in this example) using mmap before we can start with allocating anything.
char * start_of_memory; char * end_of_memory; node_t *head = mmap(NULL, 4096, PROT_READ|PROT_WRITE, MAP_ANON|MAP_PRIVATE, -1, 0); head->size = 4084; head->magic = 98765; head->next = NULL; start_of_memory = (char *)head; end_of_memory = (char *)head + 4096;
Now we are ready to start malloc. I will describe a high level overview of the function and then let the code do the rest. What malloc needs to do is go through the free cells of memory, starting with the head of the linked list, and find one that is big enough to store the size the user asked for and the necessary header information. There are a couple of ways to do this, but I chose a simple first fit approach in which it will use the first node that is big enough. If the node happens to be the perfect size, it will simply return it to the user, otherwise it will cut it up and return the first part that is now just the right size.
void *malloc(size_t size) { node_t *cell = head; while(1) { if(cell->size >= size) { if(cell->size <= size)//if it is an exact fit just return it { header_t *new_cell = (header_t *)cell; new_cell->magic=1234567; new_cell->size=size; audit(); return (void *)new_cell + sizeof(header_t); } //otherwise lets carve up this cell int new_size = cell->size - size - sizeof(node_t); header_t *new_cell = (header_t *)cell; cell = (void *)cell + sizeof(node_t) + size; cell->size = new_size; cell->magic = 98765; new_cell->magic = 1234567; new_cell->size = size; head = cell;//set head so I can point to it in the next freed cell audit(); return (void *)new_cell + sizeof(header_t); } else if(cell->next != NULL) { cell = cell->next; } else { printf("ran out of size, need to sbrk\n"); cell = sbrk(4096); cell->size=4084; cell->magic=98765; cell->next=NULL; break; } } }
Now that we have malloc in place, it is time to implement its counterpart 'free'. From a high level view point, free simply needs to take the address of the pointer that the user gives it and create a node_t out of it, reusing all of the information that was stored in the header_t. Free is also responsible for coalescing the node_t's with each other in order to make everything quicker and better conserve memory. Here is the implementation:
void free(void *ptr) { header_t *hptr = (void *)ptr - sizeof(header_t); assert(hptr->magic == 1234567); node_t *cell = (node_t *)hptr; node_t *next_cell = head; node_t *before_cell; cell->size = hptr->size; cell->magic = 98765; if(cell < head)//must be the first one on the list { if((void *)cell + sizeof(node_t) + cell->size == head) { cell->size=cell->size + head->size + sizeof(node_t); cell->next=head->next; head = cell; } else { cell->next = next_cell; } } else { while(1) { if(next_cell->next != NULL) { before_cell = next_cell; next_cell = next_cell->next; } else { printf("We're gonna have a problem here\n"); } if(cell < next_cell) { if((void *)cell + sizeof(node_t) + cell->size == next_cell) { cell->size=cell->size + next_cell->size + sizeof(node_t); cell->next=next_cell->next; } if((void *)cell - sizeof(node_t) - before_cell->size == before_cell) { before_cell->size=cell->size + before_cell->size + sizeof(node_t); before_cell->next=cell->next; } else { before_cell->next = cell; cell->next = next_cell; } break; } } } if(cell < head) { head = cell; } }
Now we have a full memory allocation system in place! A simple auditing function can be written to test if it all works as it should, and then you are finished. I wouldn't include our version of malloc and free in all of your c projects from now on, but at least you have a little more understanding of how it all works!
