My own malloc() function in C

Question

Is this acceptable? What is the next step to improve algorithm and make them more clear and faster?

typedef struct heap_block
{  
    struct heap_block* next;
    size_t size;
    bool isfree;
    int x; // for alligment
}header;

#define Heap_Capacity 16777216
unsigned long long active_size;  // # bytes in active allocations

static uint64_t heap[Heap_Capacity/sizeof(uint64_t)];

static char* max_heap =(char*)(&heap[0]);
static char* min_heap = (char*)(&heap[0]);
static char *END_CHK = "\xDE\xAD\xC0\xDA";
header* last_allocated;

void* malloc(size_t sz) 
{
    if(sz == 0 || sz > Heap_Capacity)
    {
        return NULL;
    }

    header* block = (header*)heap;
    if(active_size == 0)
    {
        set_data_to_block(block, sz);
        return (void*)last_allocated;
    }

    while(block->next != NULL)
    {
        block = block->next;
    }

    block->next = (header*)((char*)to_end_data(block) + 8);
    header* new_block = block->next;
    set_data_to_block(new_block, sz);

    return (void*)last_allocated;
}


void set_data_to_block(header* block, size_t sz)
{
    block->size = sz;
    block->isfree = false;
    block->next = NULL;

    active_size += sz;
    last_allocated = block + 1;
    char* end_of_data_block = (char*)to_end_data(block);

    if(max_heap < end_of_data_block)
    {
        max_heap = end_of_data_block;
    }
    strcpy(end_of_data_block, END_CHK);
}

header* to_start_metadata(header* block)
{
    return --block;
}

header* to_end_data(header* block)
{
    return (header*)((size_t)(block+1) + block->size);
}

Answer 1

struct heap_block is three words long. This means that if the caller is allocating small objects (one word long or shorter) then your internal fragmentation will 75% or larger.

The usual way to implement this kind of heap allocation is to store only the size of the block in the header. This works because:

1. You only need to keep track of the free blocks (because the caller has to keep track of the allocated blocks). So you don't need the isfree Boolean: if you know about a block, then it must be free.

2. You only need to store a pointer to the next block when the block is free. But in this case you have the whole of the block available (not just the header) so you can store the pointer in the remainder of the block, overwriting the data that the caller had previously stored there.

Answer 2

• Avoid globals

  last_allocated is only used to communicate the result of set_data_to_block back to malloc. Returning the result is much cleaner.

• Avoid special cases

  There is no need to special case the initial allocation. If you do not want to rely on ((header *) heap)->next == NULL initially, you may want to provide an initialization method (which I recommend anyway).

Answer 3

One additional comment on top of what's already mentioned in previous answers.

---

Using sizeof(void*) instead of 8 will make it:

1. More efficient (memory wise) on 32-bit platforms
2. More robust on future ("larger than 64-bit") platforms

Answer 4

Empty mallocs

    if(sz == 0 || sz > Heap_Capacity)

It is actually legal to call the standard library's malloc() with an argument of 0, and you are guaranteed to get a unique pointer when you do (you can't do anything with it though).

Const-correctness

static char *END_CHK = "\xDE\xAD\xC0\xDA";

You mean static char const * right? String literals are char const * not char * (though the compiler won't warn you about it)

Uninitialized variables

active_size is still uninitialized at the time of first access. Didn't the compiler warn you about this?

Data types

Why is heap defined as being a uint64_t [], but then always accessed by casting to a char *, and sometimes a header *?

Out of bounds

if the heap is almost full, you check to see if there's enough space for the header and the requested memory...and then you write 5 extra bytes after that. You could end up writing past the bounds of heap.

Running time

while(block->next != NULL)
{
    block = block->next;
}

The more memory you allocate, the longer and longer each malloc will take. You need a better data structure.