Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
  • 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
}
share|improve this question
    
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 at 1:53

2 Answers 2

up vote 5 down vote accepted

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.

share|improve this answer
    
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

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.