Behind malloc() and free()

* Whenever we use malloc(), if it finds that memory is not available within the data segment of the process, (as a last step ) it internally calls brk() system call . This system call increases the data segment address (virtual) space of the current process by the requested amount. Actually it is quite possible that although brk() returns sucessfully, physical memory might not be quite available.

* When we use free(), it returns the specific chunk of memory to allocation library ( not to the OS ). Next time you call malloc(), the allocation library may return the freed space without calling the brk() system call. Thus the OS just increases the virtual address space of the Data Segment (by brk()), but the management of the memory that is returned is up to the allocation library . Also, i dont see a system call to explicitly reduce the virtual address space of a process ( a kind of reverse brk() ). So once VA increases, it is upto the allocation library to manage this memory. Update: You did not look around enough ! In fact, calling brk() with a negative argument would reduce the VM address space of the process by that amount, only thing is that the allocation library can't do this unless it is sure that last contigous portion of VM (that is requested to be returned to the OS) is not used by the process.

* All the memory management policies like first fit, best fit and maintaining a free list, storing the size within a header of allocated block and so on goes on in the allocation library with the memory got by brk(). Only when there is no memory available, is malloc() going to go to the OS.

* Some of the popular allocators are Doug Lea Malloc, BSD Malloc and Hoard

* Also, memory management can be split between the program and the memory management by using reference counts ( for data which is read-only in some cases or even for shared data ) and then use garbage collection ( no explicit free - helps in the fact that we dont need to keep track of pointers that point to a data chunk and worry about freeing pointers twice/ using a freed pointer ).

* Another memory management technique is memory pools. For eg, the Apache web server has different memory pools, one that lasts a request, one that lasts a connection, one that lasts a thread and so on. GNU's obstack implementation is one way of using allocation pools [ provides reuse of similar sized data chunks ].

[Reference]