Question: I have a question about low level stuff of dynamic memory allocation.
I understand that there may be different implementations, but I need to understand the fundamental ideas.

So,

when a modern OS memory allocator or the equivalent allocates a block of memory, this block needs to be freed.

But, before that happends, some system needs to exist to control the allocation process.

I need to know:

* How this system keeps track of allocated and unallocated memory. I mean, the system needs to know what blocks have already been allocated and what their size is to use this information in allocation and deallocation process.

Is this process supported by modern hardware, like allocation bits or something like that?
Or is some kind of data structure used to store allocation information.
If there is a data structure, how much memory it uses compared to the allocated memory?

Is it better to allocate memory in big chunks rather than small ones and why?

Any answer that can help reveal fundamental implementation details is appreciated.

If there is a need for code examples, C or C++ will be just fine.

Answer: 
"How this system keeps track of allocated and unallocated memory." For non-embedded systems with operating systems, a [virtual page table](http://en.wikipedia.org/wiki/Page_table), which the OS is in charge of organizing (with hardware [TLB](http://en.wikipedia.org/wiki/Translation_lookaside_buffer) support of course), tracks the memory usage of programs.

***AS FAR AS I KNOW* (and the community will surely yell at me if I'm mistaken),** tracking individual `malloc()` sizes and locations has a good number of implementations and is runtime-library dependent. Generally speaking, whenever you call `malloc()`, the size and location is stored in a table. Whenever you call `free()`, the table entry for the provided pointer is looked up. If it is found, that entry is removed. If it is not found, the `free()` is ignored (which also indicates a possible memory leak).

When all `malloc()` entries in a virtual page are freed, that virtual page is then released back to the OS (this also implies that `free()` does not always release memory back to the OS since the virtual page may still have other `malloc()` entries in it). If there is not enough space within a given virtual page to support another `malloc()` of a specified size, another virtual page is requested from the OS.

Embedded processors *usually* don't have operating systems, virtual page tables, nor multiple processes. In this case, virtual memory is not used. Instead, the entire memory of the embedded processor is treated like one large virtual page (although the addresses are actually physical addresses) and memory management follows a similar process as previously described.

[Here](https://stackoverflow.com/questions/1119134/how-do-malloc-and-free-work) is a similar stack overflow question with more in-depth answers.

"Is it better to allocate memory in big chunks rather than small ones and why?" Allocate as much memory as you need, no more and no less. Compiler optimizations are *very* smart, and memory will almost always be managed more efficiently (i.e. reducing memory fragmentation) than the programmer can manually do. This is especially true in a non-embedded environment.

[Here](https://stackoverflow.com/questions/2079151/minimizing-the-amount-of-malloc-calls-improves-performance) is a similar stack overflow question with more in-depth answers (note that it pertains to C and not C++, however it is still relevant to this discussion).
Well, there are more than one way to achieve that.
I once had to wrote a `malloc()` (and `free()`) implementation for educational purpose.

This is from my experience, and real world implementation surely vary.

I used a double linked list.
Memory chunk returned to the user after calling `malloc()` were in fact a `struct` containing relevant information to my implementation (ie the `next` and `prev` pointer, and a is\_used byte).

So when a user request N bytes I allocated N + sizeof(my\_struct) bytes, hiding `next` and `prev` pointers at the begenning of the chunk, and returning what's left to the user.

Surely, this is poor design for a program that use a lot of small allocation (because each allocation takes up to N + 2 pointers + 1 byte).

For a real world implementation, you can take a look to the code of good and well known memory allocator.