Yet another implementation of malloc() in C

Question

I'm really curious to know someone else's opinion on this implementation. Specifically, I would be interested to know the way you would have implemented it. Here the list of issues I've found with in this primitive implementation:

1. It's slow. You have to traverse the entire list in order to find a free block of memory.
2. Overuse of sbrk().
3. Very high possibility of internal fragmentation.

mem.h

#ifndef __MEM__
#define __MEM__
#include<stdio.h>
#include<stdlib.h>

typedef enum { false, true } bool;

typedef struct page
{
  size_t size;
  bool free;
  struct page* next;
  struct page* prev;
} page_t;

extern void* memalloc(size_t size);
extern void  memfree(void* pointer);

#endif

mem.c

#include "include/mem.h"
#include <assert.h>
#include <sys/types.h>
#include <unistd.h>

#define SBRK_ERROR (void*)(-1)
#define UNDEFINED 0

page_t* global;
page_t* last;

page_t* allocate(size_t size)
{
  page_t* node = sbrk(0);
  void* pointer = sbrk(size + sizeof(page_t));
  if(pointer == SBRK_ERROR)
    return NULL;
  if(last != NULL)
    last-> next = node;
  last = node;
  last-> size = size;
  last-> free = false;
  last-> next = NULL;
  return last;
}

void* search(size_t size)
{
  page_t* node = global;
  while(node != NULL){
    if(node-> size >= size || node-> size == UNDEFINED){
      if(node-> free)
        return node;
    }
    node = node-> next;
  }
  return NULL;
}

void* memalloc(size_t size)
{
  page_t* result = NULL;
  if(size >= 0){
    if(global != NULL){
      result = search(size);
      if(result == NULL)
        result = allocate(size);
    }else {
      global = allocate(size);
      result = global;
    }
  }
  return result != NULL ? (result + 1) : NULL;
}

page_t* to_page(void* pointer){
  return pointer - sizeof(page_t);
}

void memfree(void* pointer)
{
  if(pointer != NULL) {
    page_t* page = to_page(pointer);
    page-> size = UNDEFINED;
    page-> free = true;
  }
}

int main(int argc, char** argv)
{
  char* pointer = memalloc(5);
  memfree(pointer);
  return 1;
}

What are the most common techniques (implementations) to solve the issues above? Just rough ideas of it.

Answer 1

Design.

The trouble with your design is that you have to search a list. Where none of the sizes may match. Even if there is a block in the list of the correct size you have to search through all the blocks that don't match your size.

Step 1

Use a list of lists. The top level list is an ordered list of sizes. So you can loop across this list quickly looking for the size you want. And stop if it does not exist.

The second level list is a list of all blocks of a specific size. So if you find the list of 24 bytes. That list contains all the 24 byte blocks that have been freed (so you just take the first one).

When an object is used you remove it from a list and when it is free'd you add it back to the list of free blocks.

global->********* -->********* -->********* -->*********
        *   8   * |  *   16  * |  *  24   * |  *  32   *
        * next  *-|  * next  *-|  * next  *    * next  *
        *********    *********    *********    *********
            |            |            |            |
            \/           \/           \/           \/
        *********    *********    *********    *********    
        * block *    * block *    * block *    * block *    
        * next  *    * next  *    * next  *    * next  *    
        *********    *********    *********    *********    
            |            |            |            |
            \/           \/           \/           \/
        *********       null      *********    *********    
        * block *                 * block *    * block *    
        * next  *                 * next  *    * next  *    
        *********                 *********    *********    
            |                         |            |
            \/                        \/           \/
        *********                    null      *********    
        * block *                              * block *    
        * next  *                              * next  *    
        *********                              *********    
            |                                      |
            \/                                     \/
        *********                                  null         
        * block *                                          
        * next  *                                          
        *********   
            |
            \/
            null     

Step 2 Simple Optimizations

If you don't find a block of the exact size you can re-use a block that is too large. There are two version of this. a) slightly too large and just waste a small amount of space b) twice as big as you need and split the block into two pieces.

Searching the size list can still be expensive but that can be simplified by using a skip list. This should significantly reduce the time you need to search the list.

Alternatively rather than a top level list you could use a balanced tree to hold the top level structure. That way finding a value is always O(ln(x)) where x is the number of different sizes.

Code Review

Your code is fine for handling string data. But you don't take into account the alignment of the object you are allocating for. If you allocate a block of 5 you don't guarantee that the object is aligned for a structure of 5 bytes (only aligned for an array of 5 characters).

Search across blocks that have already been allocated seems like a waste of time. Either simply remove allocated blocks from the global chain or if you absolutely must track them then keep two lists (one for allocated objects and one for freed objects).

There is no need to add blocks onto the end. It is far simpler to add new blocks to the front of a list.

Your code does not use the prev pointer!!!!

Answer 2

Bug

After you free a node, you set its size to UNDEFINED (i.e. 0). Then the next time you allocate, you will use this block, even if its size was too small. This is the problematic code in search():

if(node-> size >= size || node-> size == UNDEFINED){
  if(node-> free)
    return node;
}

I would suggest the following:

1. Do not set the size to UNDEFINED. It is enough that you set node->free to true to indicate that the node is now free.

2. Change your search loop to this:

   if (node->free && node->size >= size) {
       return node;
   }
   

Unnecessary double sbrk

You can just call sbrk() once, like this:

page_t* allocate(size_t size)
{
  page_t* node = sbrk(size + sizeof(page_t));
  if(node == SBRK_ERROR)
    return NULL;
  if(last != NULL)
    last-> next = node;
  last = node;
  last-> size = size;
  last-> free = false;
  last-> next = NULL;
  return last;
}

Organizing your freed nodes

One optimization you could make would be to only keep freed nodes on your list, instead of all nodes. That way, when making a new allocation, you don't have to search through currently in-use nodes in order to find a free node.

Another optimization would be to use an array of free lists instead of just one. For example, you could have an array with 32 slots, and each slot [i] would hold a list allocations that are of size: \$2^i <= size < 2^{i+1}\$. So for example slot [10] would hold the head of a free list of nodes which have sizes between 1024 and 2047. That way when you search for a particular size node, you could skip over buckets with nodes that are definitely too small.

Of course you could pick better bucket sizes based on expected usage patterns. The power of two bucket sizes was just an example.