Pwn进你的心
0%

musl 1.1.x 堆分配器初探

Posted on In 4.6k 4 mins.

Libc Musl 简析

Musl 是一个轻量级的C标准库，设计作为 GNU C library (glibc)、 uClibc 或 Android Bionic 的替代用于嵌入式操作系统和移动设备

它遵循 POSIX 2008 规格和 C99 标准，采用 MIT 许可证授权，使用 Musl 的 Linux 发行版和项目包括 sabotage， bootstrap-linux， LightCube OS 等

Libc Musl 堆管理器 - 1.1.x

1.1.x 和 1.2.x 堆管理结构几乎完全不同：

  • 1.2.x 新版本使用 mallocng
  • 1.1.x 旧版本使用 oidmalloc

1.1.x Musl 关键结构体

基础堆块结构体 chunk：

1
2
3
4
struct chunk {
    size_t psize, csize; 
    struct chunk *next, *prev;
};
  • psize 和 csize 字段都有标志位，但只有最低位的标志位 INUSE 有效（该标记用于表示自己的状态）
    • 若设置 INUSE 标志位（最低位为1），表示 chunk 正在被使用
    • 若没有设置 INUSE 标志位（最低位为0），表示 chunk 已经被释放或者通过 mmap 分配的，需要通过 psize 的标志位来进一步判断 chunk 的状态

核心结构体 mal：

1
2
3
4
5
static struct {
    volatile uint64_t binmap;
    struct bin bins[64];
    volatile int free_lock[2];
} mal;
  • 64 位无符号整数 binmap，记录每个 bin 是否为非空
  • 前面 32 个 bin 存放的 chunk 大小固定，而后面的存放一定范围的 chunk

空闲循环链表 bin：

1
2
3
4
5
struct bin {
    volatile int lock[2];
    struct chunk *head;
    struct chunk *tail;
};
  • head 和 tail 指针分别指向首部和尾部的 chunk
  • 首部 chunk 的 prev 指针和尾部 chunk 的 next 指针指向 bin 链表头部

1.1.x Musl 关键函数

申请函数 malloc：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
void *malloc(size_t n)
{
	struct chunk *c;
	int i, j;

	if (adjust_size(&n) < 0) return 0; /* 对齐 */

	if (n > MMAP_THRESHOLD) { /* 使用mmap */
		size_t len = n + OVERHEAD + PAGE_SIZE - 1 & -PAGE_SIZE;
		char *base = __mmap(0, len, PROT_READ|PROT_WRITE,
			MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
		if (base == (void *)-1) return 0;
		c = (void *)(base + SIZE_ALIGN - OVERHEAD);
		c->csize = len - (SIZE_ALIGN - OVERHEAD);
		c->psize = SIZE_ALIGN - OVERHEAD;
		return CHUNK_TO_MEM(c);
	}

	i = bin_index_up(n); /* 计算该chunk所属的bin */
	for (;;) {
		uint64_t mask = mal.binmap & -(1ULL<<i); /* 通过binmap查找bin中是否有free chunk */
		if (!mask) { /* 查找失败 */
			c = expand_heap(n); /* 扩展堆空间 */
			if (!c) return 0;
			if (alloc_rev(c)) {
				struct chunk *x = c;
				c = PREV_CHUNK(c);
				NEXT_CHUNK(x)->psize = c->csize =
					x->csize + CHUNK_SIZE(c);
			}
			break;
		} /* 查找成功 */
		j = first_set(mask); /* 获取bin */
		lock_bin(j);
		c = mal.bins[j].head;
		if (c != BIN_TO_CHUNK(j)) { /* 若大小不合适,则使用pretrim进行分割 */
			if (!pretrim(c, n, i, j)) unbin(c, j);
			unlock_bin(j);
			break;
		}
		unlock_bin(j);
	}

	/* Now patch up in case we over-allocated */
	trim(c, n); /* 最后malloc会将没有使用的内存释放(这一点会破坏堆风水) */

	return CHUNK_TO_MEM(c);
}

unlink 操作函数 unbin：

1
2
3
4
5
6
7
8
9
static void unbin(struct chunk *c, int i)
{
	if (c->prev == c->next)
		a_and_64(&mal.binmap, ~(1ULL<<i));
	c->prev->next = c->next;
	c->next->prev = c->prev;
	c->csize |= C_INUSE;
	NEXT_CHUNK(c)->psize |= C_INUSE;
}
  • 在 libc 中会有 c->prev->next == c && c->next->prev == c 的检查，而这里没有

释放函数 free：

1
2
3
4
5
6
7
8
9
10
11
void free(void *p)
{
	if (!p) return;

	struct chunk *self = MEM_TO_CHUNK(p);

	if (IS_MMAPPED(self))
		unmap_chunk(self);
	else
		__bin_chunk(self);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
void __bin_chunk(struct chunk *self)
{
	struct chunk *next = NEXT_CHUNK(self);
	size_t final_size, new_size, size;
	int reclaim=0;
	int i;

	final_size = new_size = CHUNK_SIZE(self);

	/* Crash on corrupted footer (likely from buffer overflow) */
	if (next->psize != self->csize) a_crash();

	for (;;) {
		if (self->psize & next->csize & C_INUSE) {
			self->csize = final_size | C_INUSE;
			next->psize = final_size | C_INUSE;
			i = bin_index(final_size);
			lock_bin(i);
			lock(mal.free_lock);
			if (self->psize & next->csize & C_INUSE)
				break;
			unlock(mal.free_lock);
			unlock_bin(i);
		}

		if (alloc_rev(self)) { /* 向前合并空闲chunk */
			self = PREV_CHUNK(self);
			size = CHUNK_SIZE(self);
			final_size += size;
			if (new_size+size > RECLAIM && (new_size+size^size) > size)
				reclaim = 1;
		}

		if (alloc_fwd(next)) { /* 向后合并空闲chunk */
			size = CHUNK_SIZE(next);
			final_size += size;
			if (new_size+size > RECLAIM && (new_size+size^size) > size)
				reclaim = 1;
			next = NEXT_CHUNK(next);
		}
	}

	if (!(mal.binmap & 1ULL<<i)) /* 在binmap中设置非空 */
		a_or_64(&mal.binmap, 1ULL<<i);

	self->csize = final_size;
	next->psize = final_size;
	unlock(mal.free_lock);

	self->next = BIN_TO_CHUNK(i); /* 将self插入到链表的尾部 */
	self->prev = mal.bins[i].tail;
	self->next->prev = self;
	self->prev->next = self;

	/* Replace middle of large chunks with fresh zero pages */
	if (reclaim) {
		uintptr_t a = (uintptr_t)self + SIZE_ALIGN+PAGE_SIZE-1 & -PAGE_SIZE;
		uintptr_t b = (uintptr_t)next - SIZE_ALIGN & -PAGE_SIZE;
#if 1
		__madvise((void *)a, b-a, MADV_DONTNEED);
#else
		__mmap((void *)a, b-a, PROT_READ|PROT_WRITE,
			MAP_PRIVATE|MAP_ANONYMOUS|MAP_FIXED, -1, 0);
#endif
	}

	unlock_bin(i);
}

1.1.x Musl 堆排布

在堆初始化之后，程序会自动生成一个基于 libc 基地址的 chunk 和一个基于程序基地址的 chunk

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
pwndbg> p /x mal
$3 = {
  binmap = 0x4000000000,
  bins = {{
      lock = {0x0, 0x0},
      head = 0x0,
      tail = 0x0
    } <repeats 38 times>, {
      lock = {0x0, 0x0},
      head = 0x6021f0,
      tail = 0x7f02cb591350
    }, {
      lock = {0x0, 0x0},
      head = 0x0,
      tail = 0x0
    } <repeats 25 times>},
  free_lock = {0x0, 0x0}
}
  • 最开始申请的堆都会从这两个 chunk 中切割，直到有更合适的 chunk 出现