Writing new "malloc" and "free" functions

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.

Answer 3

This sites answers your question.

http://www.codeproject.com/Questions/177316/Write-your-own-malloc -- same question http://www.inf.udec.cl/~leo/Malloc_tutorial.pdf

Answer 4

If an interviewer ask you

how would I write new "malloc" and "free" functions?

And you start talking about what you are going to do, you have already failed. Before hand you need ask few questions to have a more precise usage of your malloc function. On top of my head some of the first questions are:

• For which OS?
• For which memory? User malloc or Kernel malloc?
• Which is the most frequent usage scenario? All purpose malloc ? Better for huge chunks or small chunks?

There need to be a first round of requirement elicitation before even starting talking about code.

Answer 5

It depends on the requirements, for instance say you want to create embedded software where it sometimes it is not allowed to do malloc/free during runtime or because of performance reasons. You could then instead create your own version of malloc/free that do not allocate/free memory but instead just takes/retruns blocks from a preallocated heap.

Answer 6

If you are talking about hooking malloc() and free() calls, you can do that with something like this:

#define malloc(x) your_malloc(x)
#define free(x) your_free(x)

But, if you're talking of creating your own memory allocator, then you might want to look at one of the implementations of heap allocator, by Kernighan and Ritchie in their book "The C Programming Language 2nd Edition". It basically relies on using sbrk() system function to increase the size of the data segment for the process.

Answer 7

I guess they could/should word the question another way: "How is heap memory managed by malloc and free?".

Then you can think of the problem in a slightly different way - given a linear list of values how do you partition out chunks of the list and keep track of them, how do you give chunks of that list back, how do you manage fragmentation of the list etc.

In short though the address of the next free block is stored in heap next to the block that's allocated out, the information for where the next free piece of memory is stored is invisible to the user but is still part of the same heap. This is why overrunning mallocated memory can completely corrupt the heap and cause the likes of malloc and free to crash.

---

Usually the interviewer is using the question to give you free reign to demonstrate your knowledge. You can start with basic functionality and then if you know your onions go on to how different O/Ss manage it, what the different algorithms are etc. After all, whatever you would describe is unlikely to encompass the last twenty years of R&D on the subject!