7
\$\begingroup\$

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);
}
\$\endgroup\$
  • 11
    \$\begingroup\$ if you have malloc you should also have free \$\endgroup\$ – ratchet freak May 1 '15 at 12:35
  • 2
    \$\begingroup\$ There are a number of undefined variables, such as last_allocated and active_size and Heap_Capacity. Maybe you should repost the complete code. \$\endgroup\$ – Edward May 1 '15 at 12:45
  • \$\begingroup\$ @ivan_petrushenko: still incomplete. Missing active_size, fail_count, fail_size, file, line... \$\endgroup\$ – Edward May 1 '15 at 12:51
  • \$\begingroup\$ @Edward Now its ok \$\endgroup\$ – petrush May 1 '15 at 13:01
  • 1
    \$\begingroup\$ "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. \$\endgroup\$ – d33tah May 1 '15 at 14:47
4
\$\begingroup\$

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.

\$\endgroup\$
6
\$\begingroup\$
  • 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).

\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ 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.) \$\endgroup\$ – Gareth Rees May 1 '15 at 14:48
  • 1
    \$\begingroup\$ "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 \$\endgroup\$ – chux May 4 '15 at 17:54
  • \$\begingroup\$ Wow, that's not how I remembered it used to be. C11's way makes a lot mroe sense.Thanks. \$\endgroup\$ – Snowbody May 4 '15 at 18:51
  • 1
    \$\begingroup\$ 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*. \$\endgroup\$ – Ajay Brahmakshatriya Jun 5 '17 at 5:10
  • \$\begingroup\$ @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. \$\endgroup\$ – Toby Speight Jun 7 '17 at 14:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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