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);
}

• ratchet freak: if you have malloc you should also have free
• Edward: There are a number of undefined variables, such as last_allocated and active_size and Heap_Capacity. Maybe you should repost the complete code.
• Edward: @ivan_petrushenko: still incomplete. Missing active_size, fail_count, fail_size, file, line...
• indigo153: @Edward Now its ok
• d33tah: "What is the next step to improve algorithm and make them more clear and faster?" - this depends on your application. Where do you plan to use it? Also, a simple testing code would be useful.

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.

• Gareth Rees: In C, global variables are initialized to 0 if no initializer is given. (It's still a good idea to write an explicit initializer, to make it clear what happens.)
• chux: "argument of 0... guaranteed to get a unique pointer when you do" is incorrect. malloc(0) may return NULL even with multiple calls of malloc(0). Not even certain uniqueness holds here either. "If the size of the space requested is zero, the behavior is implementation-defined: either a null pointer is returned, or the behavior is as if the size were some nonzero value, except that the returned pointer shall not be used to access an object." C11 §7.22.3 1
• Snowbody: Wow, that's not how I remembered it used to be. C11's way makes a lot mroe sense.Thanks.
• Ajay Brahmakshatriya: The type of a string literal in C is still char* and not const char*. Although it is undefined behavior to modify it, it is still defined by standards to be char*.
• Toby Speight: @Ajay While char *s = "literal" is legal, a good compiler will warn about it. Using a pointer to const char will make the code safer and silence the warning.