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.

• Ohad Schneider: I don't like the unsigned short next either, but this way I can have a Header of size 4 (rather than 6 or 10 depending on x86/x64). I totally agree that if I were handling a general amount of memory (as opposed to 64KB) a pointer would have made life much easier (I could also use it to store NULL)
• Ohad Schneider: Also your bug report is spot on - though I believe the correct line would be _dTail = (_dTail->next == 0) ? NULL : _dBuffer + _dTail->next

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.

• Ohad Schneider: Thanks so much for the input ! leading underscores I'm used to it from C# but you may be right about using them in C/C++. nBlocks good idea warnings I don't recall seeing any warning but I'll chcek again. dInit the assumption is that we're given 64KB, otherwise using short fields in the header won't work anyway. validity I agree about calling to dFree without calling dInit, but the only way I could check for validity would be statistical (insert some magic word in the header that may appear in the user data anyway). I had max space efficiency in mind but it's a possible tradeoff.
• William Morris: For warnings, it depends upon your compiler and which warnings you have enabled. To check validity, I imagined you could keep a pinter to the base and limit of the allocated memory and check the dFree parameter lies between the two.
• Ohad Schneider: Thanks, I've increased the warning level and I do see some warnings like you predicted, I'll check them out. Regarding validity, I agree this range check would be useful. A user would still be able to mess things up by calling dFree on an address inside the range not returned by dMalloc, but why not make that extra check when it's possible. Thanks again!