Can anyone explain how malloc()
works internally?
I have sometimes done strace program
and I see a lot of sbrk
system calls, doing man sbrk
talks about it being used in malloc()
but not much more.
The sbrk
system call moves the "border" of the data segment. This means it moves a border of an area in which a program may read/write data (letting it grow or shrink, although AFAIK no malloc
really gives memory segments back to the kernel with that method). Aside from that, there's also mmap
which is used to map files into memory but is also used to allocate memory (if you need to allocate shared memory, mmap
is how you do it).
So you have two methods of getting more memory from the kernel: sbrk
and mmap
. There are various strategies on how to organize the memory that you've got from the kernel.
One naive way is to partition it into zones, often called "buckets", which are dedicated to certain structure sizes. For example, a malloc
implementation could create buckets for 16, 64, 256 and 1024 byte structures. If you ask malloc
to give you memory of a given size it rounds that number up to the next bucket size and then gives you an element from that bucket. If you need a bigger area malloc
could use mmap
to allocate directly with the kernel. If the bucket of a certain size is empty malloc
could use sbrk
to get more space for a new bucket.
There are various malloc
designs and there is propably no one true way of implementing malloc
as you need to make a compromise between speed, overhead and avoiding fragmentation/space effectiveness. For example, if a bucket runs out of elements an implementation might get an element from a bigger bucket, split it up and add it to the bucket that ran out of elements. This would be quite space efficient but would not be possible with every design. If you just get another bucket via sbrk
/mmap
that might be faster and even easier, but not as space efficient. Also, the design must of course take into account that "free" needs to make space available to malloc
again somehow. You don't just hand out memory without reusing it.
If you're interested, the OpenSER/Kamailio SIP proxy has two malloc
implementations (they need their own because they make heavy use of shared memory and the system malloc
doesn't support shared memory). See: https://github.com/OpenSIPS/opensips/tree/master/mem
Then you could also have a look at the GNU libc malloc
implementation, but that one is very complicated, IIRC.