10
\$\begingroup\$

I have implemented a simple version of malloc() and its associated functions, free(), calloc(), and realloc().

  • When free() is called, my implementation simply puts this memory on its own internal free-list.
  • When malloc() is called, it first checks the internal free-list. Only if the memory is not available there, it calls sbrk() to request another chunk.
  • All block sizes are based on powers of 2.
  • A best fit strategy is used to allocate from the free-list.

Could you please review the same and let me know your suggestions/comments?

#include <stdio.h>
#include <unistd.h>
#include <string.h>

// a struct representing a memory block
struct memoryBlock {
    // metadata about memory block
    size_t size;
    struct memoryBlock *next;
};

// function declarations
void* malloc(size_t);
void free(void*);
void* calloc(size_t, size_t);
void* realloc(void*, size_t);
struct memoryBlock* mymemcpy(void*, const void*, size_t);
void fuse_adjacent_freeBlocks();
size_t round_to_next_power_of_two(unsigned int);
struct memoryBlock* get_bestFit_freeBlock(size_t size);
void print_freelist();

struct memoryBlock head = { 0, 0 };

/* This function allocates a block of memory of size bytes. */
void* malloc(size_t size) {

    //If size is zero or less, return NULL
    if (size <= 0) {
        return NULL;
    }

    struct memoryBlock *p = head.next;

    size = round_to_next_power_of_two(size + sizeof(struct memoryBlock));

    // when free-list is empty, No freelist traversal, just sbrk and return the pointer
    if (p == NULL) {

        p = (struct memoryBlock*) sbrk(size);
        p->size = size;

        return ((char*) p) + sizeof(struct memoryBlock);
    }

    // traverse the free-list for a best-fit, if found return it
    p = get_bestFit_freeBlock(size);
    if (p != NULL) {
        return ((char*) p) + sizeof(struct memoryBlock);
    }

    // reached only if best-fit not found, sbrk and return

    p = (struct memoryBlock*) sbrk(size);
    p->size = size;
    return ((char*) p) + sizeof(struct memoryBlock);
}

/* This function frees a block of memory that had previously been allocated. */
void free(void *ptr) {

    // If ptr is NULL, this function does nothing, just RETURNs
    if (ptr == NULL) {
        return;
    }

    struct memoryBlock *to_free = (struct memoryBlock*) (((char*) ptr)
            - sizeof(struct memoryBlock));

    struct memoryBlock *p = head.next;

    // if free-list is empty, insert and return
    if (p == NULL) {
        head.next = to_free;
        to_free->next = NULL;
        return;
    }

    // try to insert at the appropriate location, fuse and return
    for (p = head.next; p->next != NULL; p = p->next) {
        if ((p < to_free) && (to_free < p->next)) {
            to_free->next = p->next;
            p->next = to_free;
            fuse_adjacent_freeBlocks();
            return;
        }
    }

    // last resort - insert at the end of free-list
    p->next = to_free;
    to_free->next = NULL;

    // coalesce
    fuse_adjacent_freeBlocks();
}

/* This function allocates memory for an array of nmemb elements of size bytes each and returns a pointer to the allocated memory. */
void* calloc(size_t nmemb, size_t size) {

    //If nmemb or size is 0, then returns NULL
    if ((nmemb == 0) || (size == 0)) {
        return NULL;
    }

    size_t actualSize = nmemb * size;

    void *p = malloc(actualSize);

    // zero the memory location
    char *d = (char*) p;
    for (size_t i = 0; i < size; i++) {
        d[i] = 0;
    }

    return p;
}

/* realloc() changes the size of the memory block pointed to by ptr to size bytes. */
void* realloc(void *ptr, size_t size) {

    size_t actulSize = round_to_next_power_of_two(
            size + sizeof(struct memoryBlock));

    // If ptr is NULL, then the call is equivalent to just calling malloc(size) for all values of size.
    if (ptr == NULL) {
        return (malloc(size));
    }

    //if size is equal to zero, and ptr is not NULL, then
    if ((size == 0) && (ptr != NULL)) {
        free(ptr);
        return NULL;
    }

    struct memoryBlock *p = (struct memoryBlock*) (((char*) ptr)
            - sizeof(struct memoryBlock)); //move the pointer back by sizeof(struct FreeList) to make it overlap properly

    // if the new size is equal to the existing size of the block, then just return the ptr as is
    if (actulSize == p->size) {
        return ptr;
    }

    // if the new size is less than the existing size of the block, split it.
    // can be split only if the resulting block is of size - power of 2, if not then we allocate a new block (after this IF)
    if (actulSize < p->size) {

        size_t size_difference = p->size - actulSize;
        if ((size_difference > sizeof(struct memoryBlock))
                && (size_difference
                        >= round_to_next_power_of_two(size_difference))) {

            p->size = actulSize;

            struct memoryBlock *return_to_freelist =
                    (struct memoryBlock*) (((char*) p) + p->size);
            return_to_freelist->size = size_difference;
            return_to_freelist =
                    (struct memoryBlock*) (((char*) return_to_freelist)
                            + sizeof(struct memoryBlock));
            free(return_to_freelist);

            return ((char*) p) + sizeof(struct memoryBlock);
        }

    }

    // reached when neither of the cases were satisfied , and allocating a new block is the option left
    // Allocate a new block  to accommodate the new size, copy the contents to the new block and free the old block
    struct memoryBlock *reallocedBlock = malloc(size);

    // If malloc returns NULL
    if (reallocedBlock == NULL) {
        return NULL;
    }

    // Copy contents from old location to the new one
    if (actulSize > p->size) {
        mymemcpy(reallocedBlock, (((char*) p) + sizeof(struct memoryBlock)),
                (p->size - sizeof(struct memoryBlock)));

    } else if (actulSize < p->size) {
        mymemcpy(reallocedBlock, (((char*) p) + sizeof(struct memoryBlock)),
                size);
    }

    // Free the old block
    free(ptr);
    return reallocedBlock;

}

struct memoryBlock* mymemcpy(void *dest, const void *src, size_t len) {

    char *d = (char*) dest;
    const char *s = (char*) src;

    for (size_t i = 0; i < len; i++) {
        d[i] = s[i];
    }
    return (struct memoryBlock*) d;
}

/* auxillary function to print the free list, meant for debug purpose only */
void print_freelist() {

    char msg_buf[100];

    sprintf(msg_buf, "\t(%s) ", __func__);
    write(2, msg_buf, strlen(msg_buf));

    struct memoryBlock *p = head.next;

    if (p == NULL) {
        sprintf(msg_buf, "Free list is empty!!\n");
        write(2, msg_buf, strlen(msg_buf));

        return;
    }

    sprintf(msg_buf, "Free-List: ");
    write(2, msg_buf, strlen(msg_buf));

    for (p = head.next; p != NULL; p = p->next) {
        sprintf(msg_buf, "[%lu](%p) --> ", p->size, (void*) p);
        write(2, msg_buf, strlen(msg_buf));

    }
    sprintf(msg_buf, " %p\n", (void*) p);
    write(2, msg_buf, strlen(msg_buf));

}

/* Merges two adjacent free blocks into a single, contiguous free block. */
void fuse_adjacent_freeBlocks() {

    struct memoryBlock *p;

    // merge until no more merges possible, 2 passes are enough
    for (int i = 0; i < 2; i++) {
        for (p = head.next; p != NULL; p = p->next) {

            if (p->next != NULL) {

                if (((((char*) p) + p->size) == (char*) p->next)
                        && (p->size == p->next->size)) { // check contiguity & equality of size

                    p->size = p->size + p->next->size; // update the size
                    p->next = p->next->next; // merge
                }
            }
        }
    }
}

/* Given a size, returns the best-fit block from the free-list */
struct memoryBlock* get_bestFit_freeBlock(size_t size) {

    struct memoryBlock *bestFit_freeBlock = NULL;

    // set the minumum to the size difference with the first free block in the free-list
    size_t minimum = head.next->size - size;

    struct memoryBlock *p = head.next;
    struct memoryBlock *trail_p = &head;

    for (p = head.next; p != NULL; p = p->next) {
        if (p->size >= size) {
            // exact size best-fit
            if (p->size == size) {

                bestFit_freeBlock = p;
                trail_p->next = p->next; // unlink p
                return bestFit_freeBlock; // no further search needed, a kind of optimization.
            } else if ((p->size - size) <= minimum) {
                // check if OK to split
                if (((p->size - size) > sizeof(struct memoryBlock))
                        && ((p->size - size)
                                >= round_to_next_power_of_two(p->size - size))) {
                    minimum = p->size - size;
                    bestFit_freeBlock = p;
                }
            }
        }
        trail_p = p; // trail p, useful while unlinking
    }

    // reached if best-fit found by splitting (i.e not by exact size match)
    if (bestFit_freeBlock != NULL) {
        bestFit_freeBlock->size = bestFit_freeBlock->size - size;

        bestFit_freeBlock = (struct memoryBlock*) (((char*) bestFit_freeBlock)
                + bestFit_freeBlock->size);
        bestFit_freeBlock->size = size;
    }

    return bestFit_freeBlock;
}

// code for below function was taken from https://graphics.stanford.edu/~seander/bithacks.html
size_t round_to_next_power_of_two(unsigned int v) {

    v--;
    v |= v >> 1;
    v |= v >> 2;
    v |= v >> 4;
    v |= v >> 8;
    v |= v >> 16;
    v++;

    return v;
}
\$\endgroup\$
  • \$\begingroup\$ Is that your actual indentation? Or did you accidentally indent it too much? \$\endgroup\$ – Zeta Feb 15 '17 at 17:51
  • \$\begingroup\$ I had a hard time using the "Code sample" feature, had to indent it by 4 more spaces. Its not the actual indentation. \$\endgroup\$ – CompSciple Feb 15 '17 at 18:16
  • \$\begingroup\$ Is that your original indentation? It's enough to indent the code with 4 spaces usually. You've used 4 tabs, if I'm not mistaken. \$\endgroup\$ – Zeta Feb 15 '17 at 18:57
  • \$\begingroup\$ I used the shift right feature of eclipse, not sure if its tabs or spaces, Thanks for fixing it :) \$\endgroup\$ – CompSciple Feb 15 '17 at 19:03
  • 1
    \$\begingroup\$ I don't understand the requirement then. If you allocate and free a 4KB block, then you allocate a 128 byte block, what happens? You can't chop 128 bytes from the free 4KB block? Why not? Your answer "A free block is split only if there is enough free space to create a block of the next smaller power of 2" doesn't make sense to me really, because the 4KB block if needed could be split into 2KB + 1KB + 512 + 256 + 128 + 128 to create a 128 byte block and all those other power of 2 sized blocks. \$\endgroup\$ – JS1 Feb 15 '17 at 21:10
7
\$\begingroup\$
  1. You should separate your declarations into three parts:
    1. The public interface. malloc calloc realloc free
    2. The debug interface. print_freelist
    3. The implementation details, which should be kept out of headers. (the rest, consider static linkage)
  2. Avoid needless casts. Each and every cast is a possible trouble-spot.
  3. Use the standard library where allowed. No need to build your own square wheels.
  4. Comment on the why, not the what. The latter is already better expressed in code.
  5. Put the contract next to the declaration, not the definition.
    Especially your malloc/realloc should mention they always fail a 0-sized request.
    And realloc is an especially troublesome beast. (Consider reading the man-page or the c standard)
  6. There are many places you risk silent wrap-around. Be more careful! And pack the full blocksize-calculation into its own function.

    static size_t getBlockSize(size_t v) {
        // reject too big requests
        if(v > (size_t)-1 / 2 + 1 - sizeof(struct memoryBlock))
            return (size_t)-1;
        v += sizeof(struct memoryBlock);
        // round up to nearest power of 2
        // below code was taken from https://graphics.stanford.edu/~seander/bithacks.html
        v--;
        v |= v >> 1;
        v |= v >> 2;
        v |= v >> 4;
        v |= v >> 8;
        v |= v >> 16;
        v++;
    
        return v;
    }
    
  7. Your malloc contains needless duplication, and you fail to check sbrk succeeded. Consider this instead:

    void* malloc(size_t size) {
        // Intentionally fail 0-size requests just because
        if (!size)
            return NULL;
    
        struct memoryBlock *p;
    
        size = getBlockSize(size);
    
        // Try to reuse old allocation
        if (head.next && (p = get_bestFit_freeBlock(size)))
            return p + 1;
        // Try to get new memory
        if((intptr_t)size < 0 || (p = sbrk(size)) == (void*)-1)
            return NULL;
        p->size = size;
        return p + 1;
    }
    
  8. calloc must check for overflow of the multiplication. Also, it must check for failure of malloc.

    void* calloc(size_t nmemb, size_t size) {
        //Reject wrap-around and 0-requests
        size_t actualSize = nmemb * size;
        if(!size || actualSize / size != nmemb)
            return NULL;
        void *p = malloc(actualSize);
        if(p)
            memset(p, 0, actualSize);
        return p;
    }
    
  9. Why don't you use fprintf(stderr, ...) in print_freelist?

  10. Consider rewriting your code so your blocks are always naturally aligned for better splitting and fusing.
\$\endgroup\$
5
\$\begingroup\$

Simplify block splitting

According to the comments, only blocks that are 2x the requested size can be split, because all blocks must remain a power of 2 size. Currently, your block splitting function searches through all blocks, keeping a minimum size around, even though that minimum size must always be size. That is really confusing because it makes it seem like you are allowing arbitrary block sizes to be split. I would rewrite your get_bestFit_freeBlock() function like this:

/* Given a size, returns the best-fit block from the free-list */
struct memoryBlock* get_bestFit_freeBlock(size_t size) {

    struct memoryBlock *doubleSize_freeBlock = NULL;
    struct memoryBlock *p                    = NULL;
    struct memoryBlock *prev                 = &head;

    for (p = head.next; p != NULL; p = p->next) {
        if (p->size == size) {
            // Exact size best-fit.  Unlink and return block.
            prev->next = p->next;
            return p;
        } else if (p->size == 2 * size && doubleSize_freeBlock == NULL) {
            // Found first size * 2 block.
            doubleSize_freeBlock = p;
        }
        prev = p;
    }

    // Reached if no exact size match was found.
    if (doubleSize_freeBlock != NULL) {
        struct memoryBlock *ret = (struct memoryBlock *)
                                    (((char*) doubleSize_freeBlock) + size);

        ret->size                  = size;
        doubleSize_freeBlock->size = size;
        return ret;
    }

    return NULL;
}

A similar change could be done to realloc() as well.

Unwanted size_t to int conversion

Your rounding function looks like this:

size_t round_to_next_power_of_two(unsigned int v);

You should be using size_t v instead, because everywhere you call round_to_next_power_of_two(), you pass a size_t as the argument. As it is, if you were on a target with 16-bit int and 32-bit size_t, you would be returning 0 when you passed in a size greater than 32KB.

Redundant code

In malloc(), you have this code:

// when free-list is empty, No freelist traversal, just sbrk and return the pointer
if (p == NULL) {

    p = (struct memoryBlock*) sbrk(size);
    p->size = size;

    return ((char*) p) + sizeof(struct memoryBlock);
}

You can remove this code, because if the free list is empty, get_bestFit_freeBlock() will return NULL and you will do the exact same call to sbrk() a few lines lower.

In realloc(), you have this check:

//if size is equal to zero, and ptr is not NULL, then
if ((size == 0) && (ptr != NULL)) {

You can simplify to just:

// if size is equal to zero
if (size == 0) {

because you already checked and handled the NULL pointer case above.

Use memset()

In calloc(), you use this code to zero the returned block:

// zero the memory location
char *d = (char*) p;
for (size_t i = 0; i < size; i++) {
    d[i] = 0;
}

You should just call memset() instead, as memset() is optimized to be as fast as possible.

memset(p, 0, size);

Also, you should use memcpy() instead of mymemcpy().

Fusing adjacent blocks

In fuse_adjacent_blocks(), you use two passes. I don't really think that is enough to ensure the complete job. Suppose your free block list looked something like this (where all blocks are adjacent):

1024 -> 512 -> 256 -> 128 -> 64 -> 64 (just added)

On the first pass, you will merge the two 64 byte blocks:

1024 -> 512 -> 256 -> 128 -> 128

On the second pass, you will merge the two 128 byte blocks:

1024 -> 512 -> 256 -> 256

It would take another 3 passes to fully merge that list to a single 2048 byte block. I think you could do it in one pass, if you tracked the start of every "run", where a "run" consists of block -> block/2 -> block/4 -> .... If the "run" ends in a pair of the same sized block, then you can merge all the blocks from the start of the run to the end (like in the example above).

Minor things

In calloc(), you don't check if nmemb * size overflows. Also, you don't check if malloc() returned a NULL.

In malloc(), you do this check:

//If size is zero or less, return NULL
if (size <= 0) {
    return NULL;
}

But really it should be

//If size is zero, return NULL
if (size == 0) {
    return NULL;
}

because size_t is unsigned.

In realloc(), the variable actulSize should be spelled actualSize.

In realloc(), it is very possible for your code to allocate the same sized block as before and copy to it instead of just returning the original block. Also, you may allocate a new half sized block instead of cutting the original block in half. This is because the code that checks for these special "reuse" cases only succeeds if the newly requested size is exactly the right size (a power of 2). You should round the newly requested size up to a power of 2 first when doing these checks so that the current block can be reused when possible.

\$\endgroup\$
2
\$\begingroup\$

My two cents. In realloc(), replace ((char*) p) + sizeof(struct memoryBlock); usage with ptr wherever it is redundant, since p is derived from ptr.

struct memoryBlock *p = (struct memoryBlock*) (((char*) ptr)
        - sizeof(struct memoryBlock));

Also you can move the initial if validations to the top before size_t actulSize = round_to_next_power_of_two(size + sizeof(struct memoryBlock));

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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