memory allocator

In C - dynamic memory allocation is done using malloc, realloc, calloc and free.

In linux kernel:
__get_free_pages() allocates memory from buddy system
-> /proc/buddyinfo
kmalloc() returns memory from slab caches
-> with slab allocation, memory chunks suitable to fit data objects of certain type or size are preallocated.
-> good for 32bytes to 32pages
-> /proc/slabinfo

In linux user space:
The GNU C library (glibc) uses an allocator based on dlmalloc ("Doug Lea's Malloc").
Allocated memory contains an 8 or 16 byte overhead for the size of the chunk and usage flags.

For requests below 256 bytes (a "smallbin" request), a simple two power best fit allocator is used. If there are no free blocks in that bin, a block from the next highest bin is split in two.

For requests of 256 bytes or above but below the mmap threshold, dlmalloc use an in-place bitwise trie algorithm.

For requests above the mmap threshold (a "largebin" request), the memory is always allocated using the mmap system call. The threshold is usually 256 KB.


Reference:
http://en.wikipedia.org/wiki/C_dynamic_memory_allocation#dlmalloc
http://www.win.tue.nl/~aeb/linux/lk/lk-9.html#ss9.3
http://en.wikipedia.org/wiki/Slab_allocation
http://en.wikipedia.org/wiki/Trie#Bitwise_tries