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:

1. Alignment restrictions don't exist. I assumed I am not going to align anything.
2. 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:

1. Manage the heap metadata in the private heap; do not create extra linked lists outside of the provided private heap;
2. Design mymalloc, myrealloc, myFree to work for all possible inputs.
3. 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
4. myFree should not crash when it is passed a pointer that has already been freed.

Answer 1

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.

Answer 2

You seem to be thinking of the 256 bytes of meta-data as a bit-map to track free/in-use on a byte-by-byte basis.

I'd consider the following as only one possible alternative:

I'd start by treating the 2048-byte heap as a 1024 "chunks" of 2 bytes each. This gives you 2 bits of information for each chunk. You can treat the first of those as signifying whether that chunk is in use, and the second as signifying whether the following chunk is part of the same logical block as the current one.

When your free function is called, you use the passed address to find the correct beginning point in your bitmap. You then walk through bits marking each chunk as free until you reach one where the second bit is set to 0, indicating the end of the current logical block (i.e., that the next 2 byte chunk is not part of the current logical block).

[Oops: just noticed that Ross Ridge already suggested nearly the same basic idea in a comment.]