Custom implementation of malloc

Question

Recently I was asked a question about implementing 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 location. 256 bytes compares well with 2048 bits, and I can store an array bit if a byte is allocated or if it is free. But when I make a call to myfree with ptr , I cannot say how much was allocated to start. I cannot use extra bits.

I do not think that there is a way around this, but I was repeated that this can be done. Any suggestions?

EDIT 1:

• Alignment restrictions do not exist. I assumed that I was not going to expose anything.
• There was a demo program that made the malloc series and freed up to check it out, and it didn't have memory blocks that were small. But this does not guarantee anything.

EDIT 2:

Documentation Guides: Some recommendations for your code:

• Manage heap metadata in a private heap; Do not create additional linked lists outside of the provided personal heap.
• The mymalloc , myrealloc , myfree works for all possible inputs.
• myrealloc should do the following, like realloc in the C ++ library: void* myrealloc( void* C, size_t newSize ) :
  • If newSize larger than the chunk size in reallocThis :
    • First you need to try to allocate a piece of size newSize in place so that the new baseline pointer is also reallocThis ;
    • If there is no free space for placement on the spot, he must allocate a piece of the requested size in another region; and then it should copy the contents from the previous snippet.
    • If the function failed to allocate the requested memory block, a NULL pointer is returned, and the memory block points to the argument reallocThis remains unchanged.
  • If newSize smaller, realloc should reduce the size of the chunk and should always succeed.
  • If newSize is 0, it should work as free.
  • If reallocThis is NULL, it should work like malloc .
  • If reallocThis is a pointer that has already been freed, then it must fail due to returning NULL
• myfree should not myfree when passed to it a pointer that has already been freed.

Answer 1

It seems you are thinking of 256 bytes of metadata in the form of a bitmap to track free / in use byte by byte.

I would consider the following as one of the possible alternatives:

I would start by looking at a heap of 2048 bytes in the form of 1024 "pieces" of 2 bytes. This gives you 2 bits of information for each fragment. You can treat the first of them as meaning whether this fragment is used, and the second means whether the next fragment is part of the same logical block as the current one.

When you call the free function, you use the passed address to find the correct starting point in your bitmap. Then you go through the bits, designating each piece as free until you reach where the second bit is set to 0, indicating the end of the current logical block (i.e., the next 2-byte piece is not part of the current logical block).

[Unfortunately, I just noticed that Ross Ridge has already proposed almost the same basic idea in the commentary.]

Answer 2

The usual way to implement malloc is to track the size of memory allocations, so free knows how large they are — store the size in bytes until the pointer returns to malloc . Let's say you only need two bytes to store the length, when the malloc caller requests n bytes of memory, you actually allocate n + 2 bytes. Then you save the length in the first two bytes and return a pointer to the bytes past which you saved the size.

As for your algorithm, a simple and naive implementation is to keep track of unallocated memory with a linked list of free memory blocks that are stored in the order of their location in memory. To highlight the space, you are looking for a free block that is large enough. Then you modify the free list to exclude this distribution. To free a block, you add it back to the free list by combining adjacent free blocks.

This is not a good implementation of malloc by modern standards, but many old memory allocators worked this way.