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.

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.