How do malloc() and free() work?

OK some answers about malloc were already posted.

The more interesting part is how free works (and in this direction, malloc too can be understood better).

In many malloc/free implementations, free does normally not return the memory to the operating system (or at least only in rare cases). The reason is that you will get gaps in your heap and thus it can happen, that you just finish off your 2 or 4 GB of virtual memory with gaps. This should be avoided, since as soon as the virtual memory is finished, you will be in really big trouble. The other reason is, that the OS can only handle memory chunks that are of a specific size and alignment. To be specific: Normally the OS can only handle blocks that the virtual memory manager can handle (most often multiples of 512 bytes e.g. 4KB).

So returning 40 Bytes to the OS will just not work. So what does free do?

Free will put the memory block in its own free block list. Normally it also tries to meld together adjacent blocks in the address space. The free block list is just a circular list of memory chunks which have some administrative data in the beginning. This is also the reason why managing very small memory elements with the standard malloc/free is not efficient. Every memory chunk needs additional data and with smaller sizes more fragmentation happens.

The free-list is also the first place that malloc looks at when a new chunk of memory is needed. It is scanned before it calls for new memory from the OS. When a chunk is found that is bigger than the needed memory, it is divided into two parts. One is returned to caller, the other is put back into the free list.

There are many different optimizations to this standard behaviour (for example for small chunks of memory). But since malloc and free must be so universal, the standard behaviour is always the fallback when alternatives are not usable. There are also optimizations in handling the free-list — for example storing the chunks in lists sorted by sizes. But all optimizations also have their own limitations.

Why does your code crash:

The reason is that by writing 9 chars (don't forget the trailing null byte) into an area sized for 4 chars, you will probably overwrite the administrative-data stored for another chunk of memory that resides "behind" your chunk of data (since this data is most often stored "in front" of the memory chunks). When free then tries to put your chunk into the free list, it can touch this administrative-data and therefore stumble over an overwritten pointer. This will crash the system.

This is a rather graceful behaviour. I have also seen situations where a runaway pointer somewhere has overwritten data in the memory-free-list and the system did not immediately crash but some subroutines later. Even in a system of medium complexity such problems can be really, really hard to debug! In the one case I was involved, it took us (a larger group of developers) several days to find the reason of the crash -- since it was in a totally different location than the one indicated by the memory dump. It is like a time-bomb. You know, your next "free" or "malloc" will crash, but you don't know why!

Those are some of the worst C/C++ problems, and one reason why pointers can be so problematic.

As aluser says in this forum thread:

Your process has a region of memory, from address x to address y, called the heap. All your malloc'd data lives in this area. malloc() keeps some data structure, let's say a list, of all the free chunks of space in the heap. When you call malloc, it looks through the list for a chunk that's big enough for you, returns a pointer to it, and records the fact that it's not free any more as well as how big it is. When you call free() with the same pointer, free() looks up how big that chunk is and adds it back into the list of free chunks(). If you call malloc() and it can't find any large enough chunk in the heap, it uses the brk() syscall to grow the heap, i.e. increase address y and cause all the addresses between the old y and the new y to be valid memory. brk() must be a syscall; there is no way to do the same thing entirely from userspace.

malloc() is system/compiler dependent so it's hard to give a specific answer. Basically however it does keep track of what memory it's allocated and depending on how it does so your calls to free could fail or succeed.

malloc() and free() don't work the same way on every O/S.

One implementation of malloc/free does the following:

1. Get a block of memory from the OS through sbrk() (Unix call).
2. Create a header and a footer around that block of memory with some information such as size, permissions, and where the next and previous block are.
3. When a call to malloc comes in, a list is referenced which points to blocks of the appropriate size.
4. This block is then returned and headers and footers are updated accordingly.