How are malloc and free implemented in C?

Question

Possible Duplicate:
How do malloc() and free() work?

I read somewhere that calling free twice using the same pointer argument causes undefined behavior. So how does free know how much memory it has to free? Does the heap always allocate contiguous memory when we call malloc/calloc/realloc? Please provide links to relevant articles/posts/blogs etc.

You don't really need to know how free works to understand that. As long as you remember that after calling free on a pointer, you don't anymore own the memory at that location. Try to access it and you'll be punished. — , Oct 09 '11 at 20:48
Perhaps you should change your question to say that you would like to know how malloc/free are implemented. The statement "In order to understand this I must first know how free works" is misleading. — David Heffernan, Oct 09 '11 at 20:58
This isn't *exactly* a dup, so I'm not voting to close, but a previous answer here on SO probably answers a lot of your questions: http://stackoverflow.com/questions/1119134/how-do-malloc-and-free-work — Brian Roach, Oct 09 '11 at 21:05

score 5 · Accepted Answer · answered Oct 09 '11 at 20:46

5

How malloc and free work is implementation defined. Commonly the info about the memory block would be stored in a header just below ptr. But not necessarily.

The great thing about malloc and free is that you don't need to know how they work. The system takes care of the details for you.

I read somewhere that calling free twice using the same pointer argument causes undefined behavior. In order to understand this I must first know how free works?

I'm not sure I agree with this statement. You simply need to follow the rule.

Does the heap always allocate contiguous memory when we call malloc/calloc/realloc?

If you mean that the block of memory returned is contiguous in the address space, then yes that is so. If you mean that successive allocations are sequential, then no.

answered Oct 09 '11 at 20:46

David Heffernan

601,492
42
1,072
1,490

Thank you for the answer. Can you please tell me where I can find how gcc (or some other well known compiler) implements free? It would be great to learn this for at least one compiler. – Bruce Oct 09 '11 at 20:49
The compiler doesn't implement free. libc does. – arsenm Oct 09 '11 at 20:50
1

@Bruce you can read about one memory allocator here: http://g.oswego.edu/dl/html/malloc.html – Omri Barel Oct 09 '11 at 20:51
That's far too complex a topic for a Stack Overflow question, at least to answer in any detail. I certainly could not tell you the details. I note that you concentrate on `free`. But really any implementation of `free` has to be made in tandem with that of `malloc`. You can't have one without the other as the song goes. – David Heffernan Oct 09 '11 at 20:51
@arsenm: Oops :-). So how does it work? – Bruce Oct 09 '11 at 20:52
@David: Where can I read about this? Is there a good book or online resource? – Bruce Oct 09 '11 at 20:53
1

@Bruce, just FYI, although the memory returned from `malloc` is contiguous in YOUR address space, it may be not physically contiguous, but that is an operating system issue which you don't normally need to care about. – Shahbaz Oct 09 '11 at 20:56
1

"The great thing about malloc and free is that you don't need to know how they work." Ooh, controversial! – James Oct 09 '11 at 21:25
I think on GNU systems, `pt2malloc` is the current, popular allocator; it's derived from Doug Lea's `dlmalloc` (but improved for a multithreaded environment). There are other free allocators out there, have a look on the internet. Google has `tcmalloc`, and IBM's Thread Building Blocks also come with a different one. You can often just swap them out right under your executable's feet. – Kerrek SB Oct 09 '11 at 22:35

score 1 · Answer 2 · answered Oct 09 '11 at 21:08

You can read about an example implementation on the tcmalloc page. It's relatively short and straight forward: http://goog-perftools.sourceforge.net/doc/tcmalloc.html (jump down to Overview)

If you're wondering how malloc requests memory from the OS, it's typically by either calling sbrk or mmap. But that's implementation defined of course.

score 0 · Answer 3 · answered Oct 09 '11 at 20:53

If you want to see an implementation, look for glibc, which is the GNU implementation of the C standard library, which includes the memory management functionality. But be aware that the exact detail of implementation will be different on other platforms and may change between versions of the standard library.

How are malloc and free implemented in C?

3 Answers3