musl malloc - Hiroshi123/bin_tools GitHub Wiki

musl libc malloc

This is not the documentation of my implementation but malloc of musl libc. This is written intended for my understanding to improve my memory allocator, and its vulnerability of heap exploitation.

There are two malloc implementation on it. One is a light-weight malloc, and the other is malloc which is used by default. Since light-weight malloc is close to what I had already implemented, I will pick the latter malloc up here.

First of all, since malloc is implemented on top of basically mmap or brk, you can guess first malloc should call either of them at least. But, in fact, most of cases memory which are used for malloc has already been donated by loader. Loader needs to mmap for each program header when they are allocated, but they do not necessarily need to be filled up down to the page boundary as the position of the last piece of data on the given file and tail address of page has some spaces. These is used for malloc. That is how it works on musl libc.

Rather than reading from malloc, this donation mechanism provides shortcut for better understanding. After a bulk of memory is passed, a chunk will be allocated. a chunk is represented as follows.

struct chunk {
    size_t psize, csize;
    struct chunk* next, prev;
}

chunk.psize means offset bytes to come up previous chunk. chunk.csize means offset bytes to next chunk.

First time, when memory was allocated, it creates two connected chunks.

psize of 1st chunk is 0, and csize of 1st chunk is size of byte which are donated. psize of 2nd chunk is csize of 1st chunk, and csize of 2nd chunk is 0.

chunk has prev and next pointer to another chunk. To understand it, you need to know a role of bins. Bins are statically allocated on libc, and its structure is as follows.

struct bin {
   volatile int lock[2];
   struct chunk* head, tail;
}

static struct {
    volatile uint64_t binmap;
    struct bin bins[64];
    volatile int free_lock[2];
} mal;

Each bin is able to point on a pair of chunk, which are head and tail. Mal manages collection of bins and its size have already been determined which is 64. mal.Binmap is 64bit which means each bit of Binmap tells you whether each bins are used up or not. Index of Bins which is used when a new chunk is created would be determined by the size of chunk.

static const unsigned char bin_tab[60] = {
	            32,33,34,35,36,36,37,37,38,38,39,39,
	40,40,40,40,41,41,41,41,42,42,42,42,43,43,43,43,
	44,44,44,44,44,44,44,44,45,45,45,45,45,45,45,45,
	46,46,46,46,46,46,46,46,47,47,47,47,47,47,47,47,
};

static int bin_index(size_t x)
{
	x = x / SIZE_ALIGN - 1;
	if (x <= 32) return x;
	if (x < 512) return bin_tab[x/8-4];
	if (x > 0x1c00) return 63;
	return bin_tab[x/128-4] + 16;
}

x is the size of chunk. If a chunk size is 1, then index will be 1 as it is less than 32. Since maximum index of bin is 63, it means half of bins index are used up chunk of which size is less than 32byte. If it is more, it is likely to be put on a and managed with different index of bins.

Then, what happen when a bin is set?

If it is the first chunk of the bin, then address of first bin's head is pointed on head & tail of first chunk.

+-------+
| bin[1]| 
+-------+
| bin[2]| 
+-------+
| bin[3]| 
+-------+

| bin[2]| 
+-------+


 +------------------head---------------+
 | +--tail----+                        |
 | |          |                        v
++-+----+   +-v------------------------+---+
| bin[1]|   |chunk1||chunk2||chunk3||chunk4|
+-------+   +-^------+-+---------------^---+
| bin[2]|     |      | |               |
+-------+     +-pre<-+ +------next-----+
| bin[3]|
+-------+

musl libc allocates meta information for malloc not on