Simple malloc and free implementation

Question

I am trying to implement a simple malloc and free. The buffer is a char array. Each chunk's address is calculated using the size of the previous chunk.

#define BUFF_SZ 64
typedef struct {
 int sz;
 int used;
}blk_hdr;
char buff[BUFF_SZ];
blk_hdr *start,*end;
void init()
{
 start = buff;
 start->sz = BUFF_SZ - sizeof(blk_hdr);
 start->used = 0;
 end = &buff[BUFF_SZ];
}
blk_hdr* next_block(blk_hdr *curr)
{
 return (void*)(curr+1) + curr->sz;
}
void split(blk_hdr *curr,int sz)
{
 int old_sz;
 old_sz = curr->sz;
 curr->used = 1; // mark used
 curr->sz = sz;
 blk_hdr *next = (void*)(curr+1) + sz; // new block with remaining bytes
 next->sz = old_sz - sz - sizeof(blk_hdr);
 next->used = 0;
}
void* mm_malloc(int size)
{
 for(blk_hdr *i = start; i!=end; i = next_block(i))
 {
 if(i->sz >= size && i->used == 0) // if big enough and free
 {
 split(i,size);
 return (void*)(i+1); // return address after header of current block
 }
 }
 return -1;
}
void coalesce()
{
 blk_hdr *prev = NULL;
 blk_hdr *curr;
 for(curr = start; curr != end; curr = next_block(curr))
 {
 /* coalesce current free block with previous block if free */
 if(curr->used == 0 && prev && prev->used == 0)
 prev->sz += curr->sz + sizeof(blk_hdr);
 else
 prev = curr;
 } 
}
void mm_free(blk_hdr *curr)
{
 curr->used=0; // mark free
 coalesce();
}
#define CONTAINER(offset) ((blk_hdr*)(offset) - 1)
int main()
{
 init();
 void *ptr1,*ptr2,*ptr3;
 ptr1 = mm_malloc(4);
 printf("block: %p\n",ptr1);
 
 ptr2 = mm_malloc(4);
 printf("block: %p\n",ptr2);
 ptr3 = mm_malloc(16);
 printf("block: %p\n",ptr3);
 mm_free(CONTAINER(ptr1));
 mm_free(CONTAINER(ptr2));
 mm_free(CONTAINER(ptr3));
 ptr1 = mm_malloc(10);
}

I have tested this and it works. The free call results in going through all the blocks and coalescing adjacent free blocks resulting in O(n) complexity. I am looking for any corner cases that I may be missing and improvements while keeping the algorithm same.

• Toby Speight: Did you miss an include? There's no declaration of printf.
• user3280530: @TobySpeight yes. updated the post
• Davislor: Please don’t edit the code after receiving a review. Readers should be able to see the same code the reviewers did.
• Davislor: If you’d like to update and receive reviews of the new version, that’s great: you can post it as a follow-up question.
• Davislor: Nice question, by the way. Welcome to the site!

Answer 1

This review pertains more to the language than the allocator.

Use size_t for sizes, cardinalities, or ordinal numbers:

typedef struct {
 int sz;
 int used;
} blk_hdr;

Can sz and used ever be negative? If not, change their types to size_t. Or if used is supposed to denote the availability of a chunk, consider changing its type to bool from stdbool.h.

Missing header file:

The code is missing the inclusion of stdio.h.

Enable more compiler warnings:

mm_malloc() is returning an int in case of a failure without a cast. There is no implicit conversion from a void * to an int.

Check the return values of library/system calls:

init();
 // ??
 ptr1 = mm_malloc(4);
 printf("block: %p\n",ptr1);
 
 // ??
 ptr2 = mm_malloc(4);
 ...

There is no point in returning an error code if you're not going to check for it.

Arithmetic on a void * is illegal in C:

blk_hdr *next = (void*)(curr+1) + sz;

The cast operator trumps binary addition according to the precedence table. In cases where the compiler provides extensions, it's still a good idea to adhere to the C standard to ensure code portability and readability.

Redundant casts:

There is an implicit conversion to and from a void * in C. Most of the casts in your code are redundant.

If the function does not take any parameters, it should be defined with the keyword void inside the parenthesis:

void init()

This takes an unspecified number of arguments, not zero. (Prior to C23)

Change it to:

void init(void)

Incompatible pointer type assignments:.

In the init() function, there are assignments to start and end pointers that result in incompatible pointer types. Specifically, start and end are declared as blk_hdr * pointers, but they are being assigned values of type char *.

Others:

• Consider using true and false from stdbool.h to denote a binary state:

  // curr->used = 1; // mark used
  curr->used = true; 
  

• Use an automatic code formatter like GNU indent to format the code.