malloc / free implementation

Question

• Purpose: Educational
• Requirement: Given 64KB of memory, implement your own malloc and free
• Method: First-Fit

struct Header 
{
    unsigned short next; //in blocks of sizeof(Header)
    unsigned short size; //in blocks of sizeof(Header)
};

static Header* _dBuffer;
static Header* _dTail;

static public void dInit()
{
    _dBuffer = getMemBlock(64 * 1024);
    _dTail = _dBuffer;
}

static public void* dMalloc(unsigned short nbytes)
{
    if (_dTail == NULL) //empty free list
        return NULL;

    Header* prev = NULL;
    Header* current = _dTail;

    // below is equivalent to ceil((nbytes + sizeof(Header)) / sizeof(Header))
    int nblocks = (nbytes + sizeof(Header) - 1) / sizeof(Header) + 1; 
    while (current->next != 0 && current->size < nblocks)
    {
        prev = current;
        current = _dBuffer + current->next;
    }

    if (current->size < nblocks) 
        //we've reached the end of the free list without finding a chunk big enough 
        return NULL;

    if (current->size == nblocks) 
    {
        //we've found an exact match, remove the chunk from the free list
        if (prev == NULL) //remove the first chunk
            _dTail = NULL;
        else
            prev->next = current->next;
        return current + 1;
    }

    //current->size > nblocks
    current->size -= nblocks;
    current+= current->size;
    current->size = nblocks;
    return current + 1;
}

static bool coalesce(Header* block)
{
    Header* nextBlock = _dBuffer + block->next;
    if (block + block->size != nextBlock)
        return false;

    block->size += nextBlock->size;
    block->next = nextBlock->next;
    return true;
}

static public void dFree(void* p) 
{
    Header* released = (Header*)p - 1;
    Header* before = NULL;
    Header* after = _dTail;

    if (_dTail == NULL) //the free list is empty
    {
        released->next = 0;
        _dTail = released;
        return;
    }

    //find where released is located in the free list
    while (after->next != 0 && after < released) 
    {
        before = after;
        after = _dBuffer + after->next;
    }

    if (after < released) //released chunk after the end of the free list
    {
        released->next = 0;
        after->next = released - _dBuffer;
        coalesce(after);
        return;
    }

    if (before == NULL) //released chunk before the beginning of the free list
    {
        released->next = _dTail - _dBuffer;
        _dTail = released;
        coalesce(released);
        return;
    }

    //released chunk is somewhere in the middle of the list
    released->next = before->next;
    before->next = released - _dBuffer;
    if (coalesce(before)) //before was coalesced with released
        coalesce(before); //now try to coalesce it with after
    else
        coalesce(released); //otherwise, try coalescing released with after
}

Answer 1

I think this is a bug:

if (current->size == nblocks) 
{
    //we've found an exact match, remove the chunk from the free list
    if (prev == NULL) //remove the first chunk
        _dTail = NULL;
        ^^^^^^^^^^^^^^^
        You are just removing the head of the list
        Not NULL(ing) the list.
        I think the line should be:

        _dTail = current->next;

    else
        prev->next = current->next;
    return current + 1;
}

The only thing I don't like is:

unsigned short next; //in blocks of sizeof(Header)

This because you have to keep doing maths to covert it to/from a pointer. I think your code would become much simpler if you just convert this too:

Header* next; // next block in list

I would also remove the assert:

assert(nbytes % sizeof(Header) == 0);

and replace it with code to move the size up.

if (nbytes % sizeof(Header) != 0)
{
    nbytes += (sizeof(Header) - (nbytes % sizeof(Header)));
}

I think you can simplify your code by quite a bit by using sentinel values on your list. See this answer about lists read the bit about sentinals and how it makes things easier.

Answer 2

A few minor comments

• I don't like the use of a leading underscore on variable names (reserved for system use I think)

• I would add a little function to calculate the number of blocks instead of doing it twice (in getMemBlock and dMalloc). eg

  static inline size_t nBlocks(size_t nbytes)
  {
      return (nbytes + sizeof(Header) - 1) / sizeof(Header);
  }
  

• There are many implicit conversion and sign conversions warnings resulting from your mixing of signed and unsigned variables. These can often cause subtle problems.

• There are also various precision loss warnings resulting from the use of short integers in the header.

• dInit needs a parameter list (void). Perhaps better to pass in the size. Also needs to return success/failure.

• You have no record of the allocated area and no way of checking for validity in dFree. So I can do:

  int main(int argc, char **argv)
  {
      void *mem;
      dFree(mem);
   ...
  

  and it will work, adding some random location to the pool.

• Also, I can call dFree without calling dInit and it will not fail.