Custom malloc implementation

Question

Recently I was asked a question to implement a very simple malloc with the following restrictions and initial conditions.

#define HEAP_SIZE 2048
int main()
{
    privateHeap = malloc(HEAP_SIZE + 256); //extra 256 bytes for heap metadata

    void* ptr = mymalloc( size_t(750) );

    myfree( ptr );
    return 0;

}

I need to implement mymalloc and myfree here using the exact space provided. 256 bytes is nicely mapping to 2048 bits, and I can have a bit array storing if a byte is allocated or if it is free. But when I make a myfree call with ptr, I cannot tell how much size was allocated to begin with. I cannot use any extra bits.

I don't seem to think there is a way around this, but I've been reiterated that it can be done. Any suggestions ?

EDIT 1:

Alignment restrictions don't exist. I assumed I am not going to align anything.
There was a demo program that did a series of mallocs and frees to test this, and it didn't have any memory blocks that were small. But that doesn't guarantee anything.

EDIT 2:

The guidelines from the documentation: Certain Guidelines on your code:

Manage the heap metadata in the private heap; do not create extra linked lists outside of the provided private heap;
Design mymalloc, myrealloc, myFree to work for all possible inputs.
myrealloc should do the following like the realloc in C++ library: void* myrealloc( void* C, size_t newSize ):
1. If newSize is bigger than the size of chunk in reallocThis:
  1. It should first try to allocate a chunk of size newSize in place so that new chunk's base pointer also is reallocThis;
  2. If there is no free space available to do in place allocation, it should allocate a chunk of requested size in a different region; and then it should copy the contents from the previous chunk.
  3. If the function failed to allocate the requested block of memory, a NULL pointer is returned, and the memory block pointed to by argument reallocThis is left unchanged.
2. If newSize is smaller, realloc should shrink the size of the chunk and should always succeed.
3. If newSize is 0, it should work like free.
4. If reallocThis is NULL, it should work like malloc.
5. If reallocThis is pointer that was already freed, then it should fail gracefully by returning NULL
myFree should not crash when it is passed a pointer that has already been freed.

Some information is missing here. How well is your heap expected to perform? Is it supposed to be able to satisfy 2048 1-byte allocations? — Jon
Instead of tracking each individual byte, track each individual allocation. (And if there's not enough room for another allocation tracking structure in the metadata space, simply return null on that malloc.) — Cameron
@shrinidhisondur: It would be best to copy/paste the relevant parts into the question. Anything else (linking) risks the link dying in the future. — Jon

Ross Ridge Ross Ridge · Accepted Answer · 2014-08-20T22:05:56

A common way malloc implementations keep track of the size of memory allocations so free knows how big they are is to store the size in the bytes before pointer return by malloc. So say you only need two bytes to store the length, when the caller of malloc requests n bytes of memory, you actually allocate n + 2 bytes. You then store the length in the first two bytes, and return a pointer to the byte just past where you stored the size.

As for your algorithm generally, a simple and naive implementation is to keep track of unallocated memory with a linked list of free memory blocks that are kept in order of their location in memory. To allocate space you search for a free block that's big enough. You then modify the free list to exclude that allocation. To free a block you add it back to the free list, coalescing adjacent free blocks.

This isn't a good malloc implementation by modern standards, but a lot of old memory allocators worked this way.

Custom malloc implementation

EDIT 1:

EDIT 2:

2 Answers