Issue
I know there is a meta-data which stores auxiliary information which is used during free(), realloc() when we supply only the pointer.
I have few doubts about heap.
- Stack is allocated per-process. There is no doubt in that, but not sure about heap. Whether a heap information is globally maintained else per-process there will be some mechanism which holds info about allocated memory for that particular process.
- How heap information will be maintained? I guess hashing mechanism. I googled and tried SO also. most of them explained it as implementation specific.. like that.
Solution
The heap, like the stack, is a per-process, and an (almost) purely user-space thing.
The heap manager uses the sbrk syscall to inform the operating system that it intends to grow the amount of memory needed. This does little apart from change a range of pages from "not known" to "existing, zero, never accessed" (this means in reality that they still don't exist, but the OS pretends they do). When a page is first accessed, it faults, and the OS pulls a zero page from the zero pool.
(It can be slightly more complex, since the the heap manager might also shrink the data segment if a lot of memory has been released from the top, but basically it's as simple as that).
That's already all the OS knows about the heap. Everything else, such as splitting blocks, putting freed blocks onto a list or similar structure, and reusing blocks happens inside the heap manager, which is directly or indirectly (e.g. as part of the glibc) part of your program.
What exactly the heap manager is doing is implementation dependent, there exist at least half a dozen well-known different malloc implementations which work in different ways. See for example this one or this one or this one.
The stack works in the same or a similar way. A certain memory range is initially "reserved" without actually reserving anything (that is, without creating pages). A few pages are committed (that is, created) and the last page is either write protected or non-existent and this is remembered in a special way. When the stack grows so this last page is touched, a fault happens. A new page is then pulled from the zero pool, provided that the stack still is within its allowable size.
When the process terminates, all references to those pages are removed and (assuming they are not shared with another process that still holds a reference) handed over to a low priority background task which zeroes them out and adds them to the "zero pool".
Answered By - Damon