This is a one file implementation of K&R Malloc. It's passed all test cases I've run on it, so I would like to request a code review.
my_malloc.c
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
void insert_into_free_list(void* ptr);
void* my_malloc(size_t size);
void my_free(void* ptr);
void coalesce_free_list();
void* free_list_begin();
void* free_list_next(void* node);
void* malloc(size_t size);
void free(void* ptr);
/**
* A single chunk in the free list that my_malloc uses to dole out memory.
*/
struct malloc_chunk {
size_t size; /*!< The size of the chunk in bytes. This includes the bookkeeping bytes, the block presented to the user, and any necessary padding. Valid for both free and allocated chunks.*/
struct malloc_chunk* next_chunk; /*!< A pointer to the next chunk in the free list. Should always be NULL for the tail of the free list. Valid for free chunks only. */
};
/**
* The head of the free list.
*/
static struct malloc_chunk* head_of_free_list = NULL;
/**
* A memory allocator which acts as a buffered interface to the sbrk system call.
* Given a number of bytes, it returns a pointer to a block of memory whose size is greater than or equal to the number given aligned by eight bytes or NULL if the user requested 0 bytes.
* It will also return NULL on failure of sbrk. The user is trusted to check for this failure condition.
* It will include an additional eight bytes at the start of every block of memory allocated to be used for bookkeeping.
* Those eight bytes should NOT be presented to the user.
*
* @param size The size in bytes of the memory block to be presented to the user.
* @return The pointer to the beginning of the memory block that is presented to the user.
*/
void* my_malloc(size_t size) {
size_t size_to_allocate;
struct malloc_chunk* chunk;
struct malloc_chunk** chunk_pointer;
if(size == 0) {
return NULL;
}
/* Round size up to the nearest multiple of eight */
size = (size + 7) & ~0x07;
/* Add eight bytes for bookkeeping */
size += 8;
/* If we can find a chunk in our free list that is large enough to accommodate the user's request, take it out of our free list and give it to the user. */
chunk = head_of_free_list;
chunk_pointer = &head_of_free_list;
while(chunk != NULL) {
if(chunk->size >= size) {
struct malloc_chunk* return_ptr = (struct malloc_chunk*) ((char*) chunk + chunk->size - size);
/**
* We either found an exact match or one that's close enough.
* To avoid fragmentation, we simply give the user the entire chunk if it's close enough.
*/
if(chunk->size - size <= 16) {
return_ptr = chunk;
*chunk_pointer = chunk->next_chunk;
/* In this case, the chunk is more than big enough for the requested amount of memory, so we just decrease the chunk's size. */
} else {
chunk->size -= size;
return_ptr->size = size;
}
return (char*) return_ptr + 8;
}
chunk_pointer = &chunk->next_chunk;
chunk = chunk->next_chunk;
}
/* my_malloc should not call sbrk with a value lower than 8192. */
size_to_allocate = size > 8192 ? size : 8192;
chunk = sbrk(size_to_allocate);
if(chunk == (void*) -1) {
perror("my_malloc");
return NULL;
}
/**
* This covers the case that the user requested a large amount of memory.
* Since they requested such a large amount, we don't attempt to add a buffer of extra memory to the free list and give them everything instead.
*/
if(size_to_allocate > 8192) {
chunk->size = size;
return (char*) chunk + 8;
}
chunk->size = size_to_allocate - size;
struct malloc_chunk* ptr = (struct malloc_chunk*) ((char*) chunk + size_to_allocate - size);
insert_into_free_list(chunk);
ptr->size = size;
return (char*) ptr + 8;
}
/**
* A memory de-allocator which returns memory to the free list used by my_malloc.
* Given a pointer which indicates a chunk of memory that was previously presented to the user by my_malloc, it uses information found in the eight bookkeeping bytes
* found before the chunk specified by the pointer to add the chunk to the free list. * It can safely be called with NULL.
* It will also coalesce the chunks in the free list to keep the number of chunks in the list to a minimum.
* @param ptr A pointer to the beginning of a chunk of memory that was presented to the user by my_malloc.
*/
void my_free(void* ptr) {
if(ptr == NULL) {
coalesce_free_list();
return;
}
/* Back up by eight bytes, so that we can easily access the bookkeeping bytes. */
ptr = ((char*) ptr) - 8;
insert_into_free_list(ptr);
coalesce_free_list();
}
/**
* Returns the head of the free list or NULL if the free list is empty.
* @return Head of the free list used by my_malloc.
*/
void* free_list_begin() {
return head_of_free_list;
}
/**
* Given a pointer to a node in the free list, it returns the next node in the list or NULL if node points to the tail of the list.
* @param node A pointer to a node in the free list.
* @return A pointer to the next node in the free list or NULL if @node points to the tail of the list.
*/
void* free_list_next(void* node) {
return ((struct malloc_chunk*) node)->next_chunk;
}
/**
* Used by my_free to coalesce the free list and keep the number of chunks present in the free list to a minimum.
*/
void coalesce_free_list() {
struct malloc_chunk* node = head_of_free_list;
if(node == NULL) {
return;
}
while(node != NULL) {
/* If two chunks are right next to each other in memory, then we can coalesce them. */
while((char*) node + node->size == (char*) node->next_chunk) {
node->size += node->next_chunk->size;
node->next_chunk = node->next_chunk->next_chunk;
}
node = node->next_chunk;
}
}
void insert_into_free_list(void* ptr) {
struct malloc_chunk* chunk_in_free_list;
struct malloc_chunk* new_chunk;
new_chunk = ptr;
/**
* The head of the free list being NULL means one of two things:
* 1.) The user has called my_free without a corresponding call to my_malloc. We trust that they won't do this.
* 2.) All chunks in the free list have been allocated.
*
* If the head isn't NULL, it could also be the case that ptr needs to be inserted before the head of the free list.
* Either way, we make ptr the new head of the free list.
*/
if(head_of_free_list == NULL || head_of_free_list >= new_chunk) {
new_chunk->next_chunk = head_of_free_list;
head_of_free_list = new_chunk;
} else {
chunk_in_free_list = head_of_free_list;
/**
* We try to insert into our free list at the point where ptr->previous_chunk < ptr < ptr->next_chunk.
* This will make coalescing the free list easier.
*/
while(chunk_in_free_list->next_chunk != NULL && chunk_in_free_list->next_chunk < new_chunk) {
chunk_in_free_list = chunk_in_free_list->next_chunk;
}
new_chunk->next_chunk = chunk_in_free_list->next_chunk;
chunk_in_free_list->next_chunk = new_chunk;
}
}
/**
* Alias of my_malloc, so it can be used with LD_PRELOAD
*/
void* malloc(size_t size) {
return my_malloc(size);
}
/**
* Alias of my_free, so it can be used with LD_PRELOAD
*/
void free(void* ptr) {
my_free(ptr);
}
