Yet another implementation of malloc() in C 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:


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


mem.h

#ifndef __MEM__
#define __MEM__
#include&lt;stdio.h&gt;
#include&lt;stdlib.h&gt;

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 &lt;assert.h&gt;
#include &lt;sys/types.h&gt;
#include &lt;unistd.h&gt;

#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-&gt; next = node;
  last = node;
  last-&gt; size = size;
  last-&gt; free = false;
  last-&gt; next = NULL;
  return last;
}

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

void* memalloc(size_t size)
{
  page_t* result = NULL;
  if(size &gt;= 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-&gt; size = UNDEFINED;
    page-&gt; 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.
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-&gt;********* --&gt;********* --&gt;********* --&gt;*********
        *   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!!!!