Pwn进你的心
0%

musl 1.2.x 堆分配器初探

Posted on Edited on In 13k 11 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.2.x

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

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

1.2.x Musl 关键结构体

在 Musl 中有几大重要的结构体：

malloc_context：musl libc 的全局管理结构指针，存放在 libc.so 的 .bss 段 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct malloc_context {
	uint64_t secret; /* 在每页的开头,用于校验/检查meta_area->check */
#ifndef PAGESIZE
	size_t pagesize;
#endif
	int init_done; /* 用于判断该结构体是否进行了初始化 */
	unsigned mmap_counter; /* mmap计数器 */
	struct meta *free_meta_head; /* 释放堆内存管理器 */
	struct meta *avail_meta; /* 可用的的堆内存管理器 */
	size_t avail_meta_count, avail_meta_area_count, meta_alloc_shift;
	struct meta_area *meta_area_head, *meta_area_tail; /* 头指针和尾指针 */
	unsigned char *avail_meta_areas;
	struct meta *active[48]; /* 可以用来分配的meta */
	size_t usage_by_class[48]; /* 对应大小的group所管理的chunk个数 */
	uint8_t unmap_seq[32], bounces[32];
	uint8_t seq;
	uintptr_t brk; /* 使用brk开拓的heap的最高地址 */
};
  • 数组 active 中的每个条目都是一个 meta 链表，其含义为 “有可用 chunk 的 meta 链表”（当一个 meta 被填满时，它将不会出现在 active 中）
  • musl 把 chunk 大小分为48类，用 size_to_class 进行计算（与 *active[48] 对应）
1
2
3
4
5
6
7
8
9
10
11
12
13
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,
};

meta_area：mallocng 在分配 meta 时，总是先分配一页的内存，然后划分为多个 meta 区域，而该页的最开始存放的就是 meta_area

1
2
3
4
5
6
struct meta_area {
	uint64_t check; /* 用于和malloc_context->secret进行匹配 */
	struct meta_area *next; /* 下一个节点指针 */
	int nslots; /* 当前使用的meta数量 */
	struct meta slots[]; /* 指向meta的指针(结构体meta_area后面的内存就是meta数组) */
};
  • slots 结构体数组可以看作是一个 meta 的集合

meta：组成一个 meta 队列

1
2
3
4
5
6
7
8
9
struct meta {
	struct meta *prev, *next; /* 双向链表 */
	struct group *mem; /* 指向group */
	volatile int avail_mask, freed_mask; /* 可用/释放chunk的bitmap */
	uintptr_t last_idx:5; /* 表示最后一个chunk的下标 */
	uintptr_t freeable:1;
	uintptr_t sizeclass:6; /* group的大小,如果mem是mmap分配,固定为63 */
	uintptr_t maplen:8*sizeof(uintptr_t)-12; /* 如果group是mmap分配的,则代表内存页数,否则为'0' */
};
  • meta 可以是 brk 分配的，可以是 mmap 映射的

group：由多个相同大小的 chunk 以及一些控制信息组成的（并且物理相邻）

1
2
3
4
5
6
struct group {
	struct meta *meta; /* 指回meta */
	unsigned char active_idx:5;
	char pad[UNIT - sizeof(struct meta *) - 1]; /* 0x10字节对齐(NUIT为0x10) */
	unsigned char storage[];
};
  • group 只能是 mmap 映射的
  • 这里的 storage 就是我们习惯中理解的 chunk

chunk 没有专门在代码中定义，但总体结构如下：

1
2
3
4
5
6
struct chunk {
    char prev_user_data[]; /* 用于存储上一个chunk的数据 */
    uint8_t idx; /* 低5bit作为idx表示这是group中第几个chunk,高3bit作为预留位 */
    uint16_t offset; /* 与第一个chunk的偏移 */
    char user_data[]; /* 用于存储数据 */
};
  • group 中第一个 chunk 的 pre_user_data 为一个指针，指向这个 group 的 meta 元数据（其实就是 group->meta 指针）
  • 其余 chunk 使用 offset 表示与所属 group 中第一个 chunk 的偏移，而 pre_user_data 用于存储上一个 chunk 的数据

这些结构体的关系如下图：

  • 相同类型的 meta 之间通过双向链表进行连接，头节点地址存储于 malloc_context->active 中
  • 而 meta_area 会形成一条单向链表，其头节点和尾节点指针都存储于 malloc_context 中

1.2.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
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
void *malloc(size_t n)
{
	if (size_overflows(n)) return 0;
	struct meta *g;
	uint32_t mask, first;
	int sc;
	int idx;
	int ctr;
    
    /* 判断size大小是否大于131052(0x1FFEC),由于chunk存在12字节的复用,所以这里大小为0x1FFEC */
	if (n >= MMAP_THRESHOLD) { /* 大于则使用mmap进行内存分配 */
		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(); /* 加malloc锁 */
		step_seq();
		g = alloc_meta(); /* 分配一个meta,mmap得到的chunk会记录在这个meta结构体中 */
		if (!g) {
			unlock(); /* 解除malloc锁 */
			munmap(p, needed);
			return 0;
		}
        
		g->mem = p; /* 返回的chunk指针 */ 
		g->mem->meta = g; /* meta指针 */
		g->last_idx = 0; /* 该group只存在一个chunk,idx设为'0' */
		g->freeable = 1; /* 记录是否可释放的标志位 */
		g->sizeclass = 63; /* 由mmap分配的内存,默认为'63' */
		g->maplen = (needed+4095)/4096; /* 计算映射内存的长度 */
		g->avail_mask = g->freed_mask = 0; /* 设置两个bitmap */
		ctx.mmap_counter++;
		idx = 0;
		goto success;
	}

	sc = size_to_class(n); /* 计算size类别 */

	rdlock(); /* 对malloc函数进行上锁 */
	g = ctx.active[sc]; /* 取得对应的meta结构体(可能取NULL,也可能取满的meta) */

    /* 如果这个sc对应的meta为空,则根据条件选择更大的meta进行分配 */
	if (!g && sc>=4 && sc<32 && sc!=6 && !(sc&1) && !ctx.usage_by_class[sc]) {
        /* if g!=0 sc∈[4,32) sc≠6 sc为偶数:对应的meta数组存在可用chunk */
		size_t usage = ctx.usage_by_class[sc|1];
		if (!ctx.active[sc|1] || (!ctx.active[sc|1]->avail_mask
		    && !ctx.active[sc|1]->freed_mask))
			usage += 3;
		if (usage <= 12)
			sc |= 1; /* 尝试增加sc的值 */
		g = ctx.active[sc];
	}

	for (;;) { /* avail_mask就是表示可用chunk的bitmap */
		mask = g ? g->avail_mask : 0; /* g=0,表示其没有可用的chunk,first一定为'0' */
		first = mask&-mask; /* 只要avail_mask的每个位不全为'0',first就也不为'0',代表还有可用的chunk */
		if (!first) break; /* 没有avail的chunk(满的meta),跳出循环 */
		if (RDLOCK_IS_EXCLUSIVE || !MT)
			g->avail_mask = mask-first; /* 将取出chunk对应的avail设为'0' */
		else if (a_cas(&g->avail_mask, mask, mask-first)!=mask) /* 自旋 */
			continue;
		idx = a_ctz_32(first); /* 获取对应chunk的idx */
		goto success;
	}
	upgradelock(); /* malloc锁更新 */

	idx = alloc_slot(sc, n); /* 申请新的chunk(重新分配meta) */
	if (idx < 0) {
		unlock(); /* 解除malloc锁 */
		return 0;
	}
	g = ctx.active[sc]; /* 更新g,找到对应的meta */

success:
	ctr = ctx.mmap_counter;
	unlock(); /* 解除malloc锁 */
	return enframe(g, idx, n, ctr); /* 返回分配的chunk */
}
  • 判断是否需要调用 mmap
  • 先计算 chunk size 的范围，判断 ctx.active[sc] 中对应的 meta，此时有3种情况：
    • meta 为 NULL：
      • 查看是否可以获取更大的 meta，进入下一步（判断 meta 是否装满）
    • meta 存在但是装满：
      • 调用 alloc_slot 尝试分配新的 meta，进入下一步（返回目标 chunk）
    • meta 存在并且有空闲：
      • 计算对应 chunk 的 idx，返回目标 chunk

其中有一些重要的函数：alloc_meta，alloc_slot

alloc_meta：分配一个 meta

1
#define alloc_meta __malloc_alloc_meta
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
struct meta *alloc_meta(void)
{
	struct meta *m;
	unsigned char *p;
	if (!ctx.init_done) { /* 查看ctx是否进行了初始化,没有就简单初始化一下 */
#ifndef PAGESIZE
		ctx.pagesize = get_page_size();
#endif
		ctx.secret = get_random_secret();
		ctx.init_done = 1;
	}
	size_t pagesize = PGSZ;
	if (pagesize < 4096) pagesize = 4096;
    /* 查看释放的meta队列是否存在空闲的结点,存在的话就直接返回 */
	if ((m = dequeue_head(&ctx.free_meta_head))) return m;
	if (!ctx.avail_meta_count) {
		int need_unprotect = 1;
		if (!ctx.avail_meta_area_count && ctx.brk!=-1) {
            /* 新分配一页内存 */
			uintptr_t new = ctx.brk + pagesize;
			int need_guard = 0;
			if (!ctx.brk) {
				need_guard = 1;
				ctx.brk = brk(0);
				ctx.brk += -ctx.brk & (pagesize-1);
				new = ctx.brk + 2*pagesize;
			}
			if (brk(new) != new) { /* 获取内存失败 */
				ctx.brk = -1;
			} else { /* 获取内存成功 */
				if (need_guard) mmap((void *)ctx.brk, pagesize,
					PROT_NONE, MAP_ANON|MAP_PRIVATE|MAP_FIXED, -1, 0);
                /* 保护页,在brk后面映射一个不可用的页(PROT_NONE)
                如果堆溢出到这里就会发送SIGV */
				ctx.brk = new;
				ctx.avail_meta_areas = (void *)(new - pagesize);
				ctx.avail_meta_area_count = pagesize>>12;
				need_unprotect = 0;
			}
		}
		if (!ctx.avail_meta_area_count) { /* 如果前面brk()分配失败了,直接mmap匿名映射一片PROT_NONE的内存再划分 */
			size_t n = 2UL << ctx.meta_alloc_shift;
			p = mmap(0, n*pagesize, PROT_NONE,
				MAP_PRIVATE|MAP_ANON, -1, 0);
			if (p==MAP_FAILED) return 0;
			ctx.avail_meta_areas = p + pagesize;
			ctx.avail_meta_area_count = (n-1)*(pagesize>>12);
			ctx.meta_alloc_shift++;
		}
		p = ctx.avail_meta_areas;
		if ((uintptr_t)p & (pagesize-1)) need_unprotect = 0;
		if (need_unprotect)
			if (mprotect(p, pagesize, PROT_READ|PROT_WRITE)
			    && errno != ENOSYS)
				return 0;
		ctx.avail_meta_area_count--;
		ctx.avail_meta_areas = p + 4096;
		if (ctx.meta_area_tail) {
			ctx.meta_area_tail->next = (void *)p;
		} else {
			ctx.meta_area_head = (void *)p;
		}
		ctx.meta_area_tail = (void *)p;
		ctx.meta_area_tail->check = ctx.secret;
		ctx.avail_meta_count = ctx.meta_area_tail->nslots
			= (4096-sizeof(struct meta_area))/sizeof *m;
		ctx.avail_meta = ctx.meta_area_tail->slots;
	}
	ctx.avail_meta_count--;
	m = ctx.avail_meta++;
	m->prev = m->next = 0;
	return m;
}

alloc_slot：申请新的 chunk（重新分配 meta）

1
2
3
4
5
6
7
8
9
10
11
12
static int alloc_slot(int sc, size_t req)
{
	uint32_t first = try_avail(&ctx.active[sc]); /* 寻找队列中可用的chunk */
	if (first) return a_ctz_32(first);

	struct meta *g = alloc_group(sc, req); /* 给sc分配一个meta再分配一个新的group结构体 */
	if (!g) return -1;

	g->avail_mask--; /* 第一个chunk被使用了 */
	queue(&ctx.active[sc], g); /* 分配的meta入队 */
	return 0;
}

alloc_group：给 sc 分配一个 meta 再分配一个新的 group 结构体

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
static struct meta *alloc_group(int sc, size_t req)
{
	size_t size = UNIT*size_classes[sc];
	int i = 0, cnt;
	unsigned char *p;
	struct meta *m = alloc_meta(); /* 分配一个新的meta用于管理新的meta */
	if (!m) return 0;
	size_t usage = ctx.usage_by_class[sc];
	size_t pagesize = PGSZ;
	int active_idx;
    
    /* cnt为需要增加的chunk数量,以下算法是通过sc来求得最优cnt */
	if (sc < 9) {
		while (i<2 && 4*small_cnt_tab[sc][i] > usage)
			i++;
		cnt = small_cnt_tab[sc][i];
	} else {
		cnt = med_cnt_tab[sc&3];
		while (!(cnt&1) && 4*cnt > usage)
			cnt >>= 1;
		while (size*cnt >= 65536*UNIT)
			cnt >>= 1;
	}

	if (cnt==1 && size*cnt+UNIT <= pagesize/2) cnt = 2; /* 如果在上面我们的cnt为'1',是不够使用mmap的,将cnt增加到2可能就可以了 */
	if (size*cnt+UNIT > pagesize/2) { /* 通过mmap分配 */
		int nosmall = is_bouncing(sc);
		account_bounce(sc);
		step_seq();

		if (!(sc&1) && sc<32) usage += ctx.usage_by_class[sc+1];

		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); /* 进行对齐操作 */

		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++; /* mmap申请的内存数量加'1' */
		active_idx = (4096-UNIT)/size-1; /* 计算active_idx(最多为cnt-1) */
		if (active_idx > cnt-1) active_idx = cnt-1;
		if (active_idx < 0) active_idx = 0;
	} else { /* 通过brk分配 */
		int j = size_to_class(UNIT+cnt*size-IB); /* 将size转化为内部的类 */
		int idx = alloc_slot(j, UNIT+cnt*size-IB); /* 重新分配meta(又调用回去了?有点迷) */
		if (idx < 0) {
			free_meta(m);
			return 0;
		}
		struct meta *g = ctx.active[j]; /* 直接获取meta */
		p = enframe(g, idx, UNIT*size_classes[j]-IB, ctx.mmap_counter);
		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; /* 这个sc又增加了cnt个chunk */
	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;
}

free：释放 chunk 的核心函数

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 free(void *p)
{
	if (!p) return; 

	struct meta *g = get_meta(p); /* 寻找释放chunk对应的meta结构体 */
	int idx = get_slot_index(p); /* 获取对应chunk在对应group下标 */
	size_t stride = get_stride(g); /* 获取chunk的大小 */
	unsigned char *start = g->mem->storage + stride*idx; 
	unsigned char *end = start + stride - IB; 
	get_nominal_size(p, end); /* 计算chunk的真实大小 */
	uint32_t self = 1u<<idx, all = (2u<<g->last_idx)-1; /* 计算chunk的bitmap */
	((unsigned char *)p)[-3] = 255; /* 将p[-3]置为0xff(对应chunk的下标),使其无效 */
	*(uint16_t *)((char *)p-2) = 0; /* 将p[-1],p[-2]置为'0'(即(uint_64)p[-1]=0xff)
	chunk的头部存在0x10大小的控制信息,这一步将其head+0x8的位置置为0xff */

	if (((uintptr_t)(start-1) ^ (uintptr_t)end) >= 2*PGSZ && g->last_idx) {
		unsigned char *base = start + (-(uintptr_t)start & (PGSZ-1));
		size_t len = (end-base) & -PGSZ;
		if (len) {
			int e = errno;
			madvise(base, len, MADV_FREE);
			errno = e;
		}
	}

    /* 在meta->free_mask进行记录,表示该chunk被释放 */
	for (;;) {
		uint32_t freed = g->freed_mask;
		uint32_t avail = g->avail_mask;
		uint32_t mask = freed | avail; /* mask=所有被释放的chunk+现在可用的chunk */
		assert(!(mask&self)); /* 对应:要释放的chunk既不能在freed中,也不在avail中 */
		if (!freed || mask+self==all) break;
		if (!MT)
			g->freed_mask = freed+self;
		else if (a_cas(&g->freed_mask, freed, freed+self)!=freed) /* 如遇多线程使用原子操作 */
			continue;
		return;
	}

	wrlock();
	struct mapinfo mi = nontrivial_free(g, idx); /* 处理meta */
	unlock();
	if (mi.len) {
		int e = errno;
		munmap(mi.base, mi.len);
		errno = e;
	}
}

nontrivial_free：设置关于属于该 group 的 meta

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
static struct mapinfo nontrivial_free(struct meta *g, int i)
{
	uint32_t self = 1u<<i;
	int sc = g->sizeclass;
	uint32_t mask = g->freed_mask | g->avail_mask;

	if (mask+self == (2u<<g->last_idx)-1 && okay_to_free(g)) {
        /* 如果group中所有chunk要么freed要么avail,并且g可以被释放,那么就要回收掉整个meta */
		if (g->next) { /* 检查改meta是否合法 */
			assert(sc < 48);
			int activate_new = (ctx.active[sc]==g);
			dequeue(&ctx.active[sc], g);
			if (activate_new && ctx.active[sc])
                /* 如果g是队列中开头的meta,那么将它弹出队列后,要激活后一个meta */
				activate_group(ctx.active[sc]);
		}
		return free_group(g); /* meta已经取出,现在要释放这个meta */
	} else if (!mask) {
        /* 如果mask==0,也就是这个group中所有的chunk都被分配出去了 */
		assert(sc < 48); /* 判断sc是否合法 */
		if (ctx.active[sc] != g) {
			queue(&ctx.active[sc], g);
		}
	}
	a_or(&g->freed_mask, self);
	return (struct mapinfo){ 0 };
}

参考：musl-1.2.2堆内存分配源码分析 | eur1ka’s blog