How do malloc() and free() work?

Question

I want to know how malloc and free work.

int main() {
    unsigned char *p = (unsigned char*)malloc(4*sizeof(unsigned char));
    memset(p,0,4);
    strcpy((char*)p,"abcdabcd"); // **deliberately storing 8bytes**
    cout << p;
    free(p); // Obvious Crash, but I need how it works and why crash.
    cout << p;
    return 0;
}

I would be really grateful if the answer is in depth at memory level, if it's possible.

Solution 1

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.

Solution 2

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.

Solution 3

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.

Solution 4

Memory protection has page-granularity and would require kernel interaction

Your example code essentially asks why the example program doesn't trap, and the answer is that memory protection is a kernel feature and applies only to entire pages, whereas the memory allocator is a library feature and it manages .. without enforcement .. arbitrary sized blocks which are often much smaller than pages.

Memory can only be removed from your program in units of pages, and even that is unlikely to be observed.

calloc(3) and malloc(3) do interact with the kernel to get memory, if necessary. But most implementations of free(3) do not return memory to the kernel¹, they just add it to a free list that calloc() and malloc() will consult later in order to reuse the released blocks.

Even if a free() wanted to return memory to the system, it would need at least one contiguous memory page in order to get the kernel to actually protect the region, so releasing a small block would only lead to a protection change if it was the last small block in a page.

So your block is there, sitting on the free list. You can almost always access it and nearby memory just as if it were still allocated. C compiles straight to machine code and without special debugging arrangements there are no sanity checks on loads and stores. Now, if you try and access a free block, the behavior is undefined by the standard in order to not make unreasonable demands on library implementators. If you try and access freed memory or meory outside an allocated block, there are various things that can go wrong:

• Sometimes allocators maintain separate blocks of memory, sometimes they use a header they allocate just before or after (a "footer", I guess) your block, but they just might want to use memory within the block for the purpose of keeping the free list linked together. If so, your reading the block is OK, but its contents may change, and writing to the block would be likely to cause the allocator to misbehave or crash.
• Naturally, your block may be allocated in the future, and then it is likely to be overwritten by your code or a library routine, or with zeroes by calloc().
• If the block is reallocated, it may also have its size changed, in which case yet more links or initialization will be written in various places.
• Obviously you may reference so far out of range that you cross a boundary of one of your program's kernel-known segments, and in this one case you will trap.

Theory of Operation

So, working backwards from your example to the overall theory, malloc(3) gets memory from the kernel when it needs it, and typically in units of pages. These pages are divided or consolidated as the program requires. Malloc and free cooperate to maintain a directory. They coalesce adjacent free blocks when possible in order to be able to provide large blocks. The directory may or may not involve using the memory in freed blocks to form a linked list. (The alternative is a bit more shared-memory and paging-friendly, and it involves allocating memory specifically for the directory.) Malloc and free have little if any ability to enforce access to individual blocks even when special and optional debugging code is compiled into the program.

---

^{1. The fact that very few implementations of free() attempt to return memory to the system is not necessarily due to the implementors slacking off. Interacting with the kernel is much slower than simply executing library code, and the benefit would be small. Most programs have a steady-state or increasing memory footprint, so the time spent analyzing the heap looking for returnable memory would be completely wasted. Other reasons include the fact that internal fragmentation makes page-aligned blocks unlikely to exist, and it's likely that returning a block would fragment blocks to either side. Finally, the few programs that do return large amounts of memory are likely to bypass malloc() and simply allocate and free pages anyway.}

Solution 5

In theory, malloc gets memory from the operating system for this application. However, since you may only want 4 bytes, and the OS needs to work in pages (often 4k), malloc does a little more than that. It takes a page, and puts it's own information in there so it can keep track of what you have allocated and freed from that page.

When you allocate 4 bytes, for instance, malloc gives you a pointer to 4 bytes. What you may not realize is that the memory 8-12 bytes before your 4 bytes is being used by malloc to make a chain of all the memory you have allocated. When you call free, it takes your pointer, backs up to where it's data is, and operates on that.

When you free memory, malloc takes that memory block off the chain... and may or may not return that memory to the operating system. If it does, than accessing that memory will probably fail, as the OS will take away your permissions to access that location. If malloc keeps the memory ( because it has other things allocated in that page, or for some optimization ), then the access will happen to work. It's still wrong, but it might work.

DISCLAIMER: What I described is a common implementation of malloc, but by no means the only possible one.

View more solutions

Comments

[Vilx-]

Shouldn't it actually depend on the compiler and the runtime library used?

[Jonathan Leffler]

There's a sample implementation of malloc() and free() in The Book (Kernighan and Ritchie "The C Programming Language"). Since you had to ask, you haven't read it - go forth and read it, and repent of your sinful ways. :D

[dstromberg]

This article is about FORTRAN really, but the same ideas apply to C and C++: stromberg.dnsalias.org/~strombrg/checking-early.html . The article talks about some of the things that can go wrong when you write to an undefined region of memory.

[Koray Tugay]

Which section, what page?

[Jonathan Leffler]

@KorayTugay: In the 1st Edition, it is on pages 173-177. In the 2nd Edition, it is on pages 185-189. In both editions, it is the last section of the last chapter, immediately before Appendix A, the Reference Manual.

[phuclv]

Don't cast the result of malloc in C

[Braden Best]

@LưuVĩnhPhúc that's C++. Note the cout <<

[akD]

This code is not crashing at all, unless optimisation is enabled in your Makefile or compiler.

[Nagappa]

Deleting more then four byte, so your program get crash

[Artelius]

Soooo many people don't realise that free() may not return memory to the OS, it's infuriating. Thanks for helping enlighten them.

[Guillaume Paris]

Artelius: on the contrary, new will always does ?

[Yay295]

@Guillaume07 I assume you meant delete, not new. No, it does not (necessarily). delete and free do (nearly) the same thing. Here's the code each one calls in MSVC2013: goo.gl/3O2Kyu

[Goaler444]

Good answer. Would recommend the paper: Dynamic Storage Allocation: A survey and Critical review by Wilson et al for an in depth review on internal mechanisms, such as header fields and free lists, that are utilised by allocators.

[David C.]

delete will always call the destructor, but the memory itself may go onto a free-list for later allocation. Depending on the implementation, it might even be the same free-list that malloc uses.

[router]

Can you tell me how exactly is the metadata overwritten when we greedily start writing more bytes than allocated starting from a memory location?

[Undefined Behaviour]

@Juergen But when free() read extra byte which contain information how much memory allocated from malloc, it get 4. Then how crash happened or how free() touch administrative data ?

[Juergen]

@vidhugangwar: Not the free touches administrative data, but the strcpy of the application writes to much data and thus overwriting administrative data. And this data is for example used when free is called -- when wrong, it leads to havoc.

[Braden Best]

Which is why it's called undefined behavior. One implementation could make demons fly out of your nose when you call free after an invalid write. You never know.

[Sapphire_Brick]

So, exiting immediately after free(malloc(1)); leaks ½KB byte of memory, since the chunks are ½KB, and one byte isn't big enough to return to the OS?

[Juergen]

@Sapphire_Brick No. Malloc will allocate some amount of memory from the OS and return a pointer to a small junk of this with at least 1 byte of size. When you free that junk, the whole memory amount can be returned to the OS, since you did not allocate more than that. When you exit -- all allocated memory is returned to the OS anyway.

[Maya Cohen]

so where can i find good inplementation ?