Writing new "malloc" and "free" functions [closed]

Question

For an interview question: how would I write new "malloc" and "free" functions? I don't think "using new and delete" would be an acceptable answer or using something similar like LocalAlloc/HeapAlloc

Answer 1

Since this is for an interview question, it probably won't have a "right" answer, and they're more interested in your thought process, and your general knowledge surrounding the topic.

You should ask to clarify the requirements, or give a range of answers depending on the situation. Here are some issues to consider:

• Is it important to avoid memory fragmentation? A fixed alloc size may help.
• Do you need speed guarantees for allocation? Use index of used/free blocks.
• Do you need to easily trace the allocations performed? Add logging structures to the malloc/free library.
• Do you need to protect against or detect memory under/overruns? Extra padding and periodic padding checks.

Answer 2

Simply put,

Your malloc function should be able to get memory from the operation system and give it to the client(say, your C program) that requests for memory to be allocated dynamically. To implement this, the malloc library usually has many data structures (depending on implementation) - For eg, the malloc implementation may choose to keep track of free blocks of memory using a linked-list. A more efficient way would be to have a list of linked lists, each containing blocks of a paticular size range.

I happened to work on TCMalloc library, that might help you understand this more clearly

Memory allocation through freelists

Lets say, class 0 is a linked list of free blocks of size 4k, class 1 is a linked list of free blocks of size 8k and so on.

When a call to malloc is made (say, of size 10k), your malloc implementation traverses through the freelist to find out the smallest free block that would satisfy the request (In this case, a 4k block would not be sufficient, so it'll fetch an 8k block, remove it from the freelist, and return it to your program).

Similarly, when a call to free is made, your implementation(among other things) should reclaim the block from the program and adds it in the appropriate place to one of the freelists.