trjhtr

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 

/**
 * 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);

Some quick ideas:

Masking with an int is not safe. Consider that size_t may be wider than unsigned/int, then the desired ~ mask will be insufficient.

// size = (size + 7) & ~0x07; // Avoid
size = (size + 7) & ~((size_t)0x07); // Better

Pointer math treads on thin ice. It is assumed that aligning to 8 is sufficient.

struct malloc_chunk* return_ptr = 
 (struct malloc_chunk*) ((char*) chunk + chunk->size - size); // Iffy 

Better to use sizeof (max_align_t) from <stddef.h> and precede with:

#define ALIGNMENT_N (sizeof (max_align_t))
#define PRE_N (sizeof (union size_t size; max_align_t dummy;))
size = (size + ALIGNMENT_N - 1) & ~ALIGNMENT_N; // Better

Perhaps replace magic number 16 too.

Also wrap 8192 in macro

#define MY_MALLOC_BIG 8192

Consider pre-pending allocated data with a well aligned size. This aligns data and negates the need for the not-so-magical 8 coded in so many places.

struct malloc_chunk 
 union 
 size_t size; 
 max_align_t dummy;
 u;
 union 
 struct malloc_chunk* next_chunk;
 max_align_t dummy;
 v;
;

Robust code would also check against large requests

if (size > SIZE_MAX - ALIGNMENT_N - PRE_N) 
 return NULL; // Fail

...
// else the following code is problematic.
size = (size + ALIGNMENT_N - 1) & ~ALIGNMENT_N;
size += PRE_N;

sbrk() is not from the standard C library.

Use (void) when declaring functions to ensure parameter checking, else a call like free_list_begin(42) will not flag an error.

// void* free_list_begin();
void* free_list_begin(void);

1. Horizontal scrolling is the bane of readability. Actually, that's the case with long lines even if they don't quite pass that threshold.
   
   So, why do you force 194 characters onto a single line, most of that comment?


2. Get rid of all the magic numbers. And especially those numbers somehow derived from the original magic numbers, or maybe not, who knows.
   
   Instead, use well-named preprocessor-defines with sensible defaults derived from standard types.


3. Mark all the functions which are implementation-details static. No need to inhibit inlining, risk name-clashes, or pollute the export- and import-tables.


4. Actually, put the public API into its own self-contained header.


5. Anyone LD_PRELOAD-ing your code will be in for a rude surprise, as you supply neither calloc() nor realloc(). Using two different memory-managers as-if they were the same is not a sane idea.