malloc implementation

Question

Please give me some feedback to my malloc implementation. I implemented this design to understand the basic concept.

#include <stdio.h>
#include <stdbool.h>
#include <string.h>

#define HEAP_MEM_SIZE 150
#define MEMORY_AVAILABLE 1 
#define MEMORY_USED 0 

struct chunk_header {
  struct chunk_header *next; // next pointer on free list
  size_t size;               // the size of this chunk
  bool is_available;         // indicates if this chunk is MEMORY_AVAILABLE or MEMORY_USED
};

typedef struct chunk_header chunk_header;
chunk_header *chunk_header_begin;
static char buffer[HEAP_MEM_SIZE];
unsigned int heap_size;

void init() {
    heap_size = HEAP_MEM_SIZE;
    chunk_header_begin = (chunk_header*)&buffer;
    chunk_header_begin->next = NULL;
    chunk_header_begin->size = heap_size;
    chunk_header_begin->is_available = MEMORY_AVAILABLE;
}

void init_next_chunk(chunk_header *curr, unsigned int bytes) {
    heap_size -= bytes;
    curr->next = NULL;
    curr->size = heap_size;
    curr->is_available = MEMORY_AVAILABLE;
}

void *my_malloc(unsigned int nbytes) {
    static bool init_flag = false;

    if(!init_flag) {
        init();
        init_flag = true;
    }

    int alloc_size = nbytes + sizeof(chunk_header); 
    chunk_header *curr = chunk_header_begin;

    while(curr) {
        if(curr->is_available && curr->size >= alloc_size) {
            curr->is_available = MEMORY_USED;
            curr->size = alloc_size;
            curr->next = curr + alloc_size;

            init_next_chunk(curr->next, alloc_size);

            // return memory region
            curr = curr + sizeof(chunk_header);
            return curr;
        }

        curr = curr->next;
    }

    return NULL;
}

void my_free(void *firstbyte) {
    chunk_header *mem = (chunk_header*)firstbyte - sizeof(chunk_header);
    chunk_header *curr = chunk_header_begin;

    while (curr) {
        if (curr == mem) {
            heap_size += curr->size;

            // Mark the block as being available
            curr->is_available = MEMORY_AVAILABLE;
            break;
        }

        curr = curr->next;
    }

    firstbyte = NULL;
}

void print_heap_allocations() {
    chunk_header *curr = chunk_header_begin;

    printf("\n\tSize\tAvailable\tMemory-Ptr");

    while (curr) {
        void *mem_ptr = curr + sizeof(chunk_header);
        printf("\n\t%d\t%d\t\t%x", curr->size, curr->is_available, mem_ptr);
        curr = curr->next;
    }

    printf("\n");
}

int main() {
    char *mem1 = (char*)my_malloc(20); 
    if(mem1 == NULL) {
        goto err;
    }
        memset (mem1,'x',19); 
        mem1[19] = '\0'; 

        print_heap_allocations();

        char *mem2 = (char*)my_malloc(20); 
        if(mem2 == NULL) {
        goto err;
    }
        memset (mem2,'y',19); 
        mem2[19] = '\0'; 

        print_heap_allocations();

        char *mem3 = (char*)my_malloc(20); 
        if(mem3 == NULL) {
            goto err;
        }
        memset (mem3,'z',19); 
        mem3[19] = '\0'; 

        print_heap_allocations();

    my_free(mem2);

    print_heap_allocations();

    char *mem4 = (char*)my_malloc(20);
    if(mem4 == NULL) {
        goto err;
    } 
        memset (mem4,'a',20); 
    mem4[19] = '\0';

        print_heap_allocations();

        printf("should be 19 x sein: %s\n", mem1); 
        printf("should be 19 a sein: %s\n", mem4); 
        printf("should be 19 z sein: %s\n", mem3);

    return 0;

err:
        printf("could not allocate mem\n");
        return 0;
}

Answer 1

Things you did well:

• Some use of comments.

• Use of typedef.

Things you could improve:

Syntax/Styling:

• Never use goto.

  

  Yes, there are some rare situations where you may find it necessary to use it. This is not one of them.

  err:
          printf("could not allocate mem\n");
          return 0;
  

  As you can see, all you do in your little block of code here is print out an unspecific error message, and then exit (using 0, which means the program was successful and is contradictory here).

  You should instead abolish the goto's completely. Print out specific, useful error messages instead, and then return with a unique exit code.

  if(mem2 == NULL) 
  {
      fprintf(stderr, "Error allocating memory to mem2.\n");
      return -2;
  }
  

• Your format specifies type int when you are trying to print a string, but the argument has type size_t (basically, unsigned long). Your format also specifies type unsigned int but the argument has type void *.

  printf("\n\t%d\t%d\t\t%x", curr->size, curr->is_available, mem_ptr);
  

  Just change they type you are trying to print out, and cast mem_ptr to an unsigned int.

  printf("\n\t%zuu\t%d\t\t%x", curr->size, curr->is_available, (unsigned int) mem_ptr);
  

• You aren't using standard naming conventions with your typedef struct.

  typedef struct chunk_header chunk_header;
  

  1. You should be giving the typedef a specific name, different from the abstract struct name.

  2. You should be capitalizing the name of the type, or adding a _t to the end (though this is reserved in POSIX)

• typedef your structs when you declare them.

  struct chunk_header {
   struct chunk_header *next; // next pointer on free list
   size_t size;               // the size of this chunk
   bool is_available;         // indicates if this chunk is MEMORY_AVAILABLE or MEMORY_USED
  };
  typedef struct chunk_header chunk_header;
  

  The typedef means you no longer have to write struct all over the place, as you have used it. But you can combine these two parts to make things more simple:

  typedef struct chunk_header
  {
      struct chunk_header *next; // next pointer on free list
      size_t size;               // the size of this chunk
      bool is_available;         // indicates if this chunk is MEMORY_AVAILABLE or MEMORY_USED
  } ChunkHeader;
  

• You can simplify your NULL checks.

   if(mem1 == NULL)
  

  Since NULL is defined as (void *)0, we can treat is as a comparison to 0.

  if(!mem1)
  

Parameters/Returns:

• You don't accept any parameters for some of your functions, such as main(). If you do not take in any parameters, declare them as void.

  int main(void)
  

• You should still return from a function, even if it is declared to return void.

  void my_free(void *firstbyte) {
      ...
      return;
  }
  

Compilation:

• I can see from some warnings I received that you have not enabled all of your compiler warnings, which you should do.

Answer 2

I'd find it neater without chunk_header_begin and heap_size as global variables: instead, assume that chunk_header_begin is at &buffer[0] and assume that the heap size is defined by the several chunk_header->size values.

I'm worried about what happens when you free-and-then-reallocate memory: the implementation doesn't look correct to me.

I'm having trouble with statements like curr + sizeof(chunk_header);: if curr were type char* then curr+3 would mean "3 chars beyond curr"; but when curr is type chunk_header * then curr+3 mean "3 chunk header beyond curr" and so curr + sizeof(chunk_header); means "sizeof(chunk_header)*sizeof(chunk_header) chars beyond curr" which isn't what you want.

IMO you should improve your unit-tests/assertions to verify that:

• next is at the expected place for a given size
• The sum of all size values (plus the size of the corresponding chunk header) matches the total heap size.

It's conventional to put some magic number e.g. 0xdeadbeef at the start and end of each chunk header:

struct chunk_header {
  int magic_start;           // 0xdeadbeef 
  struct chunk_header *next; // next pointer on free list
  size_t size;               // the size of this chunk
  bool is_available;         // indicates if this chunk is MEMORY_AVAILABLE or MEMORY_USED
  int magic_end;             // 0xdeadbeef
};

• Initialize the magic numbers when you create a chunk header
• Assert the magic numbers when you use a chunk header
• That will help detect chunk headers being overwritten by anyone using bad pointer arithmetic

You can also write some magic byte value (e.g. 0xa3) into all free/unused memory chunks, and later (when you walk the list of unallocated blocks) verify/assert than no-one has over-written those byte values.

To avoid fragmentation some heap managers use a different algorithm: e.g. have a list of 32-byte chunks and another list of 256-byte chunks; if you ask for 43 bytes then you get one of the 256-byte chunks.

---

FYI I think your malloc implementation should be more like this:

void *my_malloc(unsigned int nbytes) {
    static bool init_flag = false;

    if(!init_flag) {
        init();
        init_flag = true;
    }

    int alloc_size = nbytes + sizeof(chunk_header); 
    chunk_header *curr = chunk_header_begin;

    while(curr) {
        if(curr->is_available && curr->size >= alloc_size) {
            // we will use this chunk
            curr->is_available = MEMORY_USED;
            // is it big enough that we can split it into two chunks
            // i.e. use the start of this chunk and create a new free chunk afterwards?
            size_t min_chunk_size = sizeof(chunk_header) + 1; // big enough to allocate 1 byte
            if (cur->size - alloc_size >= min_chunk_size)
            {
                // yes so create a new chunk ...
                // ... new chunk is smaller than this one
                size_t new_size = cur->size - alloc_size;
                // ... new chunk is a few bytes beyond this one
                chunk_header *new_chunk = (chunk_header*)((char*)curr + alloc_size);
                init_next_chunk(new_chunk, new_size);
                // fit the new chunk into the existing chain of chunks
                new_chunk->next = curr->next;
                curr->next = new_chunk;
                // this chunk is smaller because its end is now a different/new chunk
                curr->size = alloc_size;
            }
            else
            {
                // can't split this into two chunk
                // don't adjust curr->next
                // don't adjust curr->size even if it's slightly too big
            }
            // return memory region
            // curr = curr + sizeof(chunk_header); I think this is wrong
            ++curr; // I think this is right
            return curr;
        }

        curr = curr->next;
    }

    return NULL;
}

Similarly, when you free a chunk you should see whether:

• It has another chunk chained after it
• That next chunk is also already free

If so then you should merge the two chunks to make a single, bigger free chunk.