5
\$\begingroup\$

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.

\$\endgroup\$
6
  • 1
    \$\begingroup\$ Did you miss an include? There's no declaration of printf. \$\endgroup\$ Oct 30, 2023 at 7:13
  • \$\begingroup\$ @TobySpeight yes. updated the post \$\endgroup\$ Oct 30, 2023 at 14:55
  • 1
    \$\begingroup\$ Please don’t edit the code after receiving a review. Readers should be able to see the same code the reviewers did. \$\endgroup\$
    – Davislor
    Oct 30, 2023 at 15:00
  • \$\begingroup\$ 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. \$\endgroup\$
    – Davislor
    Oct 30, 2023 at 15:01
  • \$\begingroup\$ Nice question, by the way. Welcome to the site! \$\endgroup\$
    – Davislor
    Oct 30, 2023 at 15:02

1 Answer 1

6
\$\begingroup\$

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.
\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.