# malloc / free implementation

• 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 public void dInit()
{
_dBuffer = getMemBlock(64 * 1024);
_dTail = _dBuffer;
}

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

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;
}

{
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)
{

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
}

-
I can't see how the content of Header pointed at by dBuffer is initialized. I assume it is inside getMemBlock(). – Loki Astari Dec 15 '12 at 17:02
@Loki Astari - Correct – Ohad Schneider Dec 15 '12 at 17:19
I've provided a sample getMemBlock() implementation to make things clearer – Ohad Schneider Dec 15 '12 at 17:28
It appears that the original code was updated based on an answer, so I've rolled back the edit. This does include bug fixes given in answers. – Jamal May 14 '14 at 1:53

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)
{
}


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.

-
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 Dec 15 '12 at 18:21
Also your bug report is spot on - though I believe the correct line would be _dTail = (_dTail->next == 0) ? NULL : _dBuffer + _dTail->next – Ohad Schneider Dec 15 '12 at 18:29

• 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)
{
}

• 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.

-
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. – Ohad Schneider Dec 18 '12 at 14:39
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. – William Morris Dec 18 '12 at 18:53
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! – Ohad Schneider Dec 18 '12 at 19:04