时间要是再多点就好了，我能避免许多遗憾。

什么是 musl ？

musl，一种C标准库，主要使用于以Linux内核为主的操作系统上，目标为嵌入式系统与移动设备。开发此库的目的是写一份干净、高效、符合标准的C标准库。

为啥要学 musl ？glibc 玩明白了？

💢 没玩明白呢还。原因一个是最近的比赛( *ctf )接触到了 musl ，想学习一下，算是拓展知识面提升自己了。另外 musl 和 glibc 肯定有相同的地方，况且 🐮 🅱 的 glibc 还有漏洞呢， musl 的洞岂不是也不会少,乐观点。最后，盯着各种各样奇奇怪怪的代码去 exploit 很炫酷的欧尅？一 一✧

前言

musl 1.2.2 版本源码相比较 1.1.x 有较大变动，这里先从师傅们的文章学习一下 1.2.2 ，其他的以后再来补。

源码分析

关键数据结构

先认识一下几个结构体：

chunk

源码中并没有显式地定义出 chunk 结构体，实际上其结构为：

1
2
3
4
5
6
7
8
9
10
struct chunk
{
	uint8_t idx;  // 低 5bit 作为 idx 表示这是 group 中第几个 chunk, 高3bit作为 reserved
	uint16_t offset; // 与第一个 chunk 的偏移
    // idx 和 offset 就是此 chunk 的元数据域了，仅占 4 Byte
	char user_data[];
    /*
假设用户申请后获得的指针为 char *p，那么 p 就指向 user_data[] 的头部
    */
};

group

malloc/mallocng/meta.h

1
2
3
4
5
6
7
8
// meta 管理 group
// group 管理 chunk ，其中的 storage 就是给用户使用的部分
struct group {
	struct meta *meta;   // 指向管理本 group 的 meta
	unsigned char active_idx:5;     // 5 bit
	char pad[UNIT - sizeof(struct meta *) - 1];     // 16 字节对齐，使给用户的 storage[] 是对齐的
	unsigned char storage[];
};

meta

malloc/mallocng/meta.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// meta 管理 group
// group 管理 chunk ，其中的 storage 就是给用户使用的部分
// meta 管理的 group 个数由 small_cnt_tab 数组指定
// meta 管理的 group 中每个 chunk 的大小固定，由 sizeclass 指定
struct meta {
	struct meta *prev, *next;   // 说明是双向链表
    // 指向的 group 与 meta 内存页隔离，防止溢出攻击
	struct group *mem;
	volatile int avail_mask, freed_mask;     // 掩码的形式，用一个 bit 表示存在与否
	uintptr_t last_idx:5;
	uintptr_t freeable:1; 	// 标识是否可以被 free
	uintptr_t sizeclass:6;      // 管理的 group 大小，同一个 meta 中保持一致。如果 mem 是 mmap 分配固定为 63
                //if (n >= MMAP_THRESHOLD) { ... g->sizeclass = 63;}
	uintptr_t maplen:8*sizeof(uintptr_t)-12;    // 如果管理的 group 是 mmap 分配的，则为内存页数，否则为 0
};

meta_area

malloc/mallocng/meta.h

1
2
3
4
5
6
7
8
9
// 单独申请一个内存页，页起始地址为一个 struct meta_area 结构，该内存页剩下的部分就是一个个 meta
//	const struct meta_area *area = (void *)((uintptr_t)meta & -4096);
struct meta_area {
	uint64_t check;     // assert(area->check == ctx.secret);
	struct meta_area *next;
	int nslots;     // 管理 meta 的个数 一般为定值
            // ctx.avail_meta_count = ctx.meta_area_tail->nslots = (4096-sizeof(struct meta_area))/sizeof *m;
	struct meta slots[];
};

malloc_context

malloc/mallocng/meta.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
struct malloc_context {
	uint64_t secret;    // ctx.secret = get_random_secret();
#ifndef PAGESIZE
	size_t pagesize;
#endif
	int init_done;  //if (!ctx.init_done) { 执行 init ... ctx.init_done = 1;}
	unsigned mmap_counter;  // 使用 mmap 分配的次数
    /********************************************************************************/
	struct meta *free_meta_head;
	struct meta *avail_meta;    // meta_area 中管理的空闲的 meta 首地址
	size_t avail_meta_count, avail_meta_area_count, meta_alloc_shift;// avail_meta_count 空闲的 meta 数量
	struct meta_area *meta_area_head, *meta_area_tail;
	unsigned char *avail_meta_areas;
	struct meta *active[48];     // 缓存可继续分配的 meta，类似 glibc 里的各种 bins
	size_t usage_by_class[48];   // 对应大小的缓存的所有 meta 的 group 所管理的 chunk 个数
	uint8_t unmap_seq[32], bounces[32];
	uint8_t seq;
	uintptr_t brk;   // 记录目前的 sbrk(0) 即 Heap 的最高地址
};

Musl-mallocng 部分源码分析

size_to_class

计算出来的 size_class 与 malloc_context 中的 active[48] 对应。

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
#define IB 4

const uint16_t size_classes[] = {
    1, 2, 3, 4, 5, 6, 7, 8,
    9, 10, 12, 15,
    18, 20, 25, 31,
    36, 42, 50, 63,
    72, 84, 102, 127,
    146, 170, 204, 255,
    292, 340, 409, 511,
    584, 682, 818, 1023,
    1169, 1364, 1637, 2047,
    2340, 2730, 3276, 4095,
    4680, 5460, 6552, 8191,
};

static const uint8_t small_cnt_tab[][3] = {
	{ 30, 30, 30 },
	{ 31, 15, 15 },
	{ 20, 10, 10 },
	{ 31, 15, 7 },
	{ 25, 12, 6 },
	{ 21, 10, 5 },
	{ 18, 8, 4 },
	{ 31, 15, 7 },
	{ 28, 14, 6 },
};

static inline int a_ctz_32(uint32_t x)
{
#ifdef a_clz_32
    return 31-a_clz_32(x&-x);
#else
    static const char debruijn32[32] = {
        0, 1, 23, 2, 29, 24, 19, 3, 30, 27, 25, 11, 20, 8, 4, 13,
        31, 22, 28, 18, 26, 10, 7, 12, 21, 17, 9, 6, 16, 5, 15, 14
    };
    return debruijn32[(x&-x)*0x076be629 >> 27];
#endif
}
static inline int a_clz_32(uint32_t x)
{
    x >>= 1;
    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
    x++;
    return 31-a_ctz_32(x);
}
static inline int size_to_class(size_t n)
{
    n = (n+IB-1)>>4;
    if (n<10) return n;
    n++;
    int i = (28-a_clz_32(n))*4 + 8;
    if (n>size_classes[i+1]) i+=2;
    if (n>size_classes[i]) i++;
    return i;
}

计算完大概是：

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
0x0     ~ 0xc ->0
0xd     ~ 0x1c ->1
0x1d    ~ 0x2c ->2
0x2d    ~ 0x3c ->3
0x3d    ~ 0x4c ->4
0x4d    ~ 0x5c ->5
0x5d    ~ 0x6c ->6
0x6d    ~ 0x7c ->7
0x7d    ~ 0x8c ->8
0x8d    ~ 0x9c ->9
0x9d    ~ 0xbc ->10
0xbd    ~ 0xec ->11
0xed    ~ 0x11c ->12
0x11d   ~ 0x13c ->13
0x13d   ~ 0x18c ->14
0x18d   ~ 0x1ec ->15
0x1ed   ~ 0x23c ->16
0x23d   ~ 0x29c ->17
0x29d   ~ 0x31c ->18
0x31d   ~ 0x3ec ->19
0x3ed   ~ 0x47c ->20
0x47d   ~ 0x53c ->21
0x53d   ~ 0x65c ->22
0x65d   ~ 0x7ec ->23
0x7ed   ~ 0x91c ->24
0x91d   ~ 0xa9c ->25
0xa9d   ~ 0xcbc ->26
0xcbd   ~ 0xfec ->27
0xfed   ~ 0x123c ->28
0x123d  ~ 0x153c ->29
0x153d  ~ 0x198c ->30
0x198d  ~ 0x1fec ->31
0x1fed  ~ 0x247c ->32
0x247d  ~ 0x2a9c ->33
0x2a9d  ~ 0x331c ->34
0x331d  ~ 0x3fec ->35
0x3fed  ~ 0x490c ->36
0x490d  ~ 0x553c ->37
0x553d  ~ 0x664c ->38
0x664d  ~ 0x7fec ->39
0x7fed  ~ 0x923c ->40
0x923d  ~ 0xaa9c ->41
0xaa9d  ~ 0xccbc ->42
0xccbd  ~ 0xffec ->43
0xffed  ~ 0x1247c ->44
0x1247d ~ 0x1553c ->45
0x1553d ~ 0x1997c ->46

malloc

malloc/mallocng/malloc.c

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
void *malloc(size_t n)
{
	if (size_overflows(n)) return 0;
	struct meta *g;
	uint32_t mask, first;
	int sc;
	int idx;
	int ctr;
// #define MMAP_THRESHOLD 131052
// #define UNIT 16
// #define IB 4
// 如果走 mmap 分配（跳过）
/**************************************************************/
	if (n >= MMAP_THRESHOLD) {
		size_t needed = n + IB + UNIT;
		void *p = mmap(0, needed, PROT_READ|PROT_WRITE,
			MAP_PRIVATE|MAP_ANON, -1, 0);
		if (p==MAP_FAILED) return 0;
		wrlock();
		step_seq();
		g = alloc_meta();
		if (!g) {
			unlock();
			munmap(p, needed);
			return 0;
		}
		g->mem = p;
		g->mem->meta = g;
		g->last_idx = 0;
		g->freeable = 1;
		g->sizeclass = 63;
		g->maplen = (needed+4095)/4096;
		g->avail_mask = g->freed_mask = 0;
		// use a global counter to cycle offset in
		// individually-mmapped allocations.
		ctx.mmap_counter++;
		idx = 0;
		goto success;
	}
/**************************************************************/

    // 不走 mmap 则
	sc = size_to_class(n);
	rdlock();
	g = ctx.active[sc];  // 查找缓存 "bins" ，拿到 meta *g

// meta 为空且 4 =< sc <= 32 且不等于 6 且为偶数并且该 sc 没有正在使用的 chunk（?）
/**************************************************************/
	// use coarse size classes initially when there are not yet
	// any groups of desired size. this allows counts of 2 or 3
	// to be allocated at first rather than having to start with
	// 7 or 5, the min counts for even size classes.
	if (!g && sc>=4 && sc<32 && sc!=6 && !(sc&1) && !ctx.usage_by_class[sc]) {
		size_t usage = ctx.usage_by_class[sc|1];
		// if a new group may be allocated, count it toward
		// usage in deciding if we can use coarse class.
		if (!ctx.active[sc|1] || (!ctx.active[sc|1]->avail_mask
		    && !ctx.active[sc|1]->freed_mask))
			usage += 3;
		if (usage <= 12)
			sc |= 1;
		g = ctx.active[sc];
	}
/**************************************************************/

	for (;;) {
		mask = g ? g->avail_mask : 0;
		first = mask&-mask;     // 找到最低的为 1 的 bit 位
		if (!first) break;  // 没有 avail 的 chunk ， break
		if (RDLOCK_IS_EXCLUSIVE || !MT)
			g->avail_mask = mask-first;     // 把 avail 这个 bit 置零 ， 为分配 chunk 做准备
		else if (a_cas(&g->avail_mask, mask, mask-first)!=mask)
			continue;
		idx = a_ctz_32(first);  // 计算 group 中的 chunk 下标
		goto success;   // 跳到分配 chunk
	}
	upgradelock();

    // 如果缓存中没有 avial 的 chunk ， 进一步申请
	idx = alloc_slot(sc, n);
	if (idx < 0) {
		unlock();
		return 0;
	}
	g = ctx.active[sc];     // 刷新 g

success:
	ctr = ctx.mmap_counter;
	unlock();
	return enframe(g, idx, n, ctr);
}

alloc_slot

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 当 malloc 时初步发现 ctx.active[sc] 没有 avail 的 chunk
// sc = size_to_class(n); req 是请求分配的大小
static int alloc_slot(int sc, size_t req)
{
    // 详细检查一下缓存(可能有 freed mask 或者 meta.next 有可分配的)
	uint32_t first = try_avail(&ctx.active[sc]);
	if (first) return a_ctz_32(first);  // 分配成功 return

	struct meta *g = alloc_group(sc, req);  // 进一步申请，全新的 meta 与 group
	if (!g) return -1;

	g->avail_mask--;
	queue(&ctx.active[sc], g);  // 加入缓存 "bins"
	return 0;
}

try_avail

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
// try_avail(&ctx.active[sc])
static uint32_t try_avail(struct meta **pm)
{
	struct meta *m = *pm;
	uint32_t first;
	if (!m) return 0;
	uint32_t mask = m->avail_mask;
	if (!mask) {    // 没有 avail
		if (!m->freed_mask) {   // 没有 free 的 chunk ， meta 的 group 中所有的 chunk 都分配出去了
			dequeue(pm, m);     // meta UNLINK , UNSAFE UNLINK!!! 任意写漏洞
			m = *pm;
			if (!m) return 0;
		} else {
			m = m->next;    // 找下一个，如果没有下一个指向自己（循环链表）
			*pm = m;
		}

		mask = m->freed_mask;

		// skip fully-free group unless it's the only one
		// or it's a permanently non-freeable group
		if (mask == (2u<<m->last_idx)-1 && m->freeable) {
			m = m->next;
			*pm = m;
			mask = m->freed_mask;
		}

		// activate more slots in a not-fully-active group
		// if needed, but only as a last resort. prefer using
		// any other group with free slots. this avoids
		// touching & dirtying as-yet-unused pages.
		if (!(mask & ((2u<<m->mem->active_idx)-1))) {
			if (m->next != m) {
				m = m->next;
				*pm = m;
			} else {
				int cnt = m->mem->active_idx + 2;
				int size = size_classes[m->sizeclass]*UNIT;
				int span = UNIT + size*cnt;
				// activate up to next 4k boundary
				while ((span^(span+size-1)) < 4096) {
					cnt++;
					span += size;
				}
				if (cnt > m->last_idx+1)
					cnt = m->last_idx+1;
				m->mem->active_idx = cnt-1;
			}
		}
		mask = activate_group(m);
		assert(mask);
		decay_bounces(m->sizeclass);
	}
    // 提取出 avail 的第一个 chunk 对应的 mask ，return
	first = mask&-mask;
	m->avail_mask = mask-first;
	return first;
}

alloc_slot

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
static int alloc_slot(int, size_t);

// 	struct meta *g = alloc_group(sc, req);  // 进一步申请，全新的 meta 与 group
static struct meta *alloc_group(int sc, size_t req)
{
	size_t size = UNIT*size_classes[sc];
	int i = 0, cnt;
	unsigned char *p;

    // 分配全新的 meta
    // 优先查看 ctx.free_meta_head 链表，如果没有
    // 再查看  ctx 管理的 main_are 是否有剩的 meta，是否有其他的 meta_area ，如果都没有
    // 尝试用 brk() 以内存页为标准分配堆，会中间多分配一个无读写权限的内存页，作为 guard
    // brk() 失败会尝试用 mmap()
	struct meta *m = alloc_meta();
	if (!m) return 0;
	size_t usage = ctx.usage_by_class[sc];
// 给 cnt 赋值，mmap，跳过
/**************************************************************************/
	size_t pagesize = PGSZ;
	int active_idx;
	if (sc < 9) {
		while (i<2 && 4*small_cnt_tab[sc][i] > usage)
			i++;
		cnt = small_cnt_tab[sc][i];
	} else {
		// lookup max number of slots fitting in power-of-two size
		// from a table, along with number of factors of two we
		// can divide out without a remainder or reaching 1.
		cnt = med_cnt_tab[sc&3];

		// reduce cnt to avoid excessive eagar allocation.
		while (!(cnt&1) && 4*cnt > usage)
			cnt >>= 1;

		// data structures don't support groups whose slot offsets
		// in units don't fit in 16 bits.
		while (size*cnt >= 65536*UNIT)
			cnt >>= 1;
	}

    // 需求比较大的时候调用 mmap 分配
	// If we selected a count of 1 above but it's not sufficient to use
	// mmap, increase to 2. Then it might be; if not it will nest.
	if (cnt==1 && size*cnt+UNIT <= pagesize/2) cnt = 2;

	// All choices of size*cnt are "just below" a power of two, so anything
	// larger than half the page size should be allocated as whole pages.
	if (size*cnt+UNIT > pagesize/2) {
		// check/update bounce counter to start/increase retention
		// of freed maps, and inhibit use of low-count, odd-size
		// small mappings and single-slot groups if activated.
		int nosmall = is_bouncing(sc);
		account_bounce(sc);
		step_seq();

		// since the following count reduction opportunities have
		// an absolute memory usage cost, don't overdo them. count
		// coarse usage as part of usage.
		if (!(sc&1) && sc<32) usage += ctx.usage_by_class[sc+1];

		// try to drop to a lower count if the one found above
		// increases usage by more than 25%. these reduced counts
		// roughly fill an integral number of pages, just not a
		// power of two, limiting amount of unusable space.
		if (4*cnt > usage && !nosmall) {
			if (0);
			else if ((sc&3)==1 && size*cnt>8*pagesize) cnt = 2;
			else if ((sc&3)==2 && size*cnt>4*pagesize) cnt = 3;
			else if ((sc&3)==0 && size*cnt>8*pagesize) cnt = 3;
			else if ((sc&3)==0 && size*cnt>2*pagesize) cnt = 5;
		}
		size_t needed = size*cnt + UNIT;
		needed += -needed & (pagesize-1);

		// produce an individually-mmapped allocation if usage is low,
		// bounce counter hasn't triggered, and either it saves memory
		// or it avoids eagar slot allocation without wasting too much.
		if (!nosmall && cnt<=7) {
			req += IB + UNIT;
			req += -req & (pagesize-1);
			if (req<size+UNIT || (req>=4*pagesize && 2*cnt>usage)) {
				cnt = 1;
				needed = req;
			}
		}

		p = mmap(0, needed, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANON, -1, 0);
		if (p==MAP_FAILED) {
			free_meta(m);
			return 0;
		}
		m->maplen = needed>>12;
		ctx.mmap_counter++;
		active_idx = (4096-UNIT)/size-1;
		if (active_idx > cnt-1) active_idx = cnt-1;
		if (active_idx < 0) active_idx = 0;
	}
/**************************************************************************/
    else {
		int j = size_to_class(UNIT+cnt*size-IB);
        // 又一次 alloc_slot 这是一个递归过程
        // 尝试向更大的缓存要内存，更大缓存中的 chunk 会成为这里的 group
		int idx = alloc_slot(j, UNIT+cnt*size-IB);
		if (idx < 0) {
			free_meta(m);
			return 0;
		}
		struct meta *g = ctx.active[j];
		p = enframe(g, idx, UNIT*size_classes[j]-IB, ctx.mmap_counter);
        // 以上代码走了类似 malloc 的过程 ， 向更大缓存要了块 chunk
		m->maplen = 0;
		p[-3] = (p[-3]&31) | (6<<5);
		for (int i=0; i<=cnt; i++)
			p[UNIT+i*size-4] = 0;
		active_idx = cnt-1;
	}
    // 加入缓存的计数
	ctx.usage_by_class[sc] += cnt;
    // 设置新 meta 的初始值
	m->avail_mask = (2u<<active_idx)-1;
	m->freed_mask = (2u<<(cnt-1))-1 - m->avail_mask;
	m->mem = (void *)p;
	m->mem->meta = m;
	m->mem->active_idx = active_idx;
	m->last_idx = cnt-1;
	m->freeable = 1;
	m->sizeclass = sc;
	return m;
}
1
2
3
4
5
6
7
8
9
10
$10 = {                                                                                                           
prev = 0x55a680b781d0,                                                                                          
next = 0x55a680b781d0,                                                                                          
mem = 0x7f3478f92c50,                                                                                           
avail_mask = 0,                                                                                                 
freed_mask = 252,                                                                                               
last_idx = 9,                                                                                                   
freeable = 1,                                                                                                   
sizeclass = 2,                                                                                                  
maplen = 0

Exploit

主要是 dequeque 和 FSOP 的利用，先欠着(好吧其实是太菜了不会以后学)

参考资料

[阅读型]新版musl libc(1.2.2)堆管理之源码剖析！- easylyou

RCTF2021-musl-WP - chuj