malloc函数源码笔记

chunk类型分类

fastbin

在32位linux下当请求的空间小于0x64时使用fastbin分配,即申请出来的chunk size<0x50时使用fastbin分配.
在32位linux下当请求的空间小于0x80时使用fastbin分配,即申请出来的chunk size<0x90时使用fastbin分配.

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
if ((unsigned long) (nb) <= (unsigned long) (get_max_fast ()))
{
idx = fastbin_index (nb);
mfastbinptr *fb = &fastbin (av, idx);
mchunkptr pp = *fb;
do
{
victim = pp;
if (victim == NULL)
break;
}
while ((pp = catomic_compare_and_exchange_val_acq (fb, victim->fd, victim))
!= victim);
if (victim != 0)
{
if (__builtin_expect (fastbin_index (chunksize (victim)) != idx, 0))
{
errstr = "malloc(): memory corruption (fast)";
errout:
malloc_printerr (check_action, errstr, chunk2mem (victim), av);
return NULL;
}
check_remalloced_chunk (av, victim, nb);
void *p = chunk2mem (victim);
alloc_perturb (p, bytes);
return p;
}
}

第一行:判断大小是否使用fastbin分配,大小不符合跳转至下一步。

第三行:得到大小对应的数组索引值

第六行:此时fb的值为fastbin数组的地址,即main_arena+偏移,pp为fastbin数组的第一项。进行循环判断。

catomic_compare_and_exchange_val_acq函数声明为atomic_compare_and_exchange_val_rel(mem, newval, oldval)
当 newval 和 oldval不相等时,返回oldval.将newval填写到mem地址上。
未malloc时的main_arena
未malloc时的main_arena
第6行的do while循环作用为若fastbin数组对应索引地址为空break,若不为空则将victim->fd覆盖到fastbin数组对应索引地址,即将单链表第一项摘下分配。

第16行进行fast chunk分配的检测,检测为:摘除的chunk的size要满足用户请求的大小,但是由于是使用idx索引值进行判断,还是有很大机会可以进行fast bin attack.

如 0x70-0x7f在64位下使用的idx是同一值。检测通过即分配fast chunk 分配结束。

small bin

若请求大小小于512byte且fastbin未分配成功时,进入small bin分配流程

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
 if (in_smallbin_range (nb))
{
idx = smallbin_index (nb);
bin = bin_at (av, idx);

if ((victim = last (bin)) != bin)
{
if (victim == 0) /* initialization check */
malloc_consolidate (av);
else
{
bck = victim->bk;
if (__glibc_unlikely (bck->fd != victim))
{
errstr = "malloc(): smallbin double linked list corrupted";
goto errout;
}
set_inuse_bit_at_offset (victim, nb);
bin->bk = bck;
bck->fd = bin;

if (av != &main_arena)
victim->size |= NON_MAIN_ARENA;
check_malloced_chunk (av, victim, nb);
void *p = chunk2mem (victim);
alloc_perturb (p, bytes);
return p;
}
}
}

第一行判断请求的大小是否小于512字节

第六行判断bin->bk是否等于自己,若等于自己说明链表为空,跳转至下一步。链表初始化后空链表的bk,fd指针都指向main_arena中的smallbin数组位置。由于使用的是bk指针,small chunk的分配是先入后出的模式。

一次malloc后的main_arena
一次malloc后的main_arena

main_arena+0x58为top chunk地址。

main_arena+0x60为last_reminder chunk地址。

main_arena+0x68为unsorted bin chunk。

main_arena+0x78后为small bin数组。

第8行,判断bk指针是否指向0,从图一可知,只有在未初始化的main_arena中指针才会指向0,此行功能即判断是否进行过初始化。若未初始化执行malloc_consolidate函数进行初始化。

第13行进行double link的检测,检测要求为分配出来的victim->bk->fd=victim,

第18行根据分配出来的地址及请求的大小查找相邻堆块,并设置其inuse标志

第19行为small bin的摘除操作,可控性差,若可修改free后的small bin,可做到修改main_arena中对应bk指针为受限的任意值,限制条件为任意地址->fd=victim。同时会修改任意地址->fd=main_arena中数组对应索引地址。

第22行判断使用的arena是不是main_arena,一个进程只有一个main_arena,每个线程会分配一个arena。若不是在size上增加标志NON_MAIN_ARENA,PS:size低3位有三个标志位,分配结束。

unsorted bin

若请求大小小于512字节且并未在fastbin或smallbin中分配,转至这一步。

若请求大于512字节,先判断fastbin是否为空,不为空执行malloc_consolidate函数对fast chunk进行合并插入到unsorted bin中。之后转入unsorted bin分配。

1
2
3
idx = largebin_index (nb);
if (have_fastchunks (av))
malloc_consolidate (av);

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
      while ((victim = unsorted_chunks (av)->bk) != unsorted_chunks (av))
{
bck = victim->bk;
if (__builtin_expect (victim->size <= 2 * SIZE_SZ, 0)
|| __builtin_expect (victim->size > av->system_mem, 0))
malloc_printerr (check_action, "malloc(): memory corruption",
chunk2mem (victim), av);
size = chunksize (victim);

/*
If a small request, try to use last remainder if it is the
only chunk in unsorted bin. This helps promote locality for
runs of consecutive small requests. This is the only
exception to best-fit, and applies only when there is
no exact fit for a small chunk.
*/

if (in_smallbin_range (nb) &&
bck == unsorted_chunks (av) &&
victim == av->last_remainder &&
(unsigned long) (size) > (unsigned long) (nb + MINSIZE))
{
/* split and reattach remainder */
remainder_size = size - nb;
remainder = chunk_at_offset (victim, nb);
unsorted_chunks (av)->bk = unsorted_chunks (av)->fd = remainder;
av->last_remainder = remainder;
remainder->bk = remainder->fd = unsorted_chunks (av);
if (!in_smallbin_range (remainder_size))
{
remainder->fd_nextsize = NULL;
remainder->bk_nextsize = NULL;
}

set_head (victim, nb | PREV_INUSE |
(av != &main_arena ? NON_MAIN_ARENA : 0));
set_head (remainder, remainder_size | PREV_INUSE);
set_foot (remainder, remainder_size);

check_malloced_chunk (av, victim, nb);
void *p = chunk2mem (victim);
alloc_perturb (p, bytes);
return p;
}

/* remove from unsorted list */
unsorted_chunks (av)->bk = bck;
bck->fd = unsorted_chunks (av);

/* Take now instead of binning if exact fit */

if (size == nb)
{
set_inuse_bit_at_offset (victim, size);
if (av != &main_arena)
victim->size |= NON_MAIN_ARENA;
check_malloced_chunk (av, victim, nb);
void *p = chunk2mem (victim);
alloc_perturb (p, bytes);
return p;
}

/* place chunk in bin */

if (in_smallbin_range (size))
{
victim_index = smallbin_index (size);
bck = bin_at (av, victim_index);
fwd = bck->fd;
}
else
{
victim_index = largebin_index (size);
bck = bin_at (av, victim_index);
fwd = bck->fd;

/* maintain large bins in sorted order */
if (fwd != bck)
{
/* Or with inuse bit to speed comparisons */
size |= PREV_INUSE;
/* if smaller than smallest, bypass loop below */
assert ((bck->bk->size & NON_MAIN_ARENA) == 0);
if ((unsigned long) (size) < (unsigned long) (bck->bk->size))
{
fwd = bck;
bck = bck->bk;

victim->fd_nextsize = fwd->fd;
victim->bk_nextsize = fwd->fd->bk_nextsize;
fwd->fd->bk_nextsize = victim->bk_nextsize->fd_nextsize = victim;
}
else
{
assert ((fwd->size & NON_MAIN_ARENA) == 0);
while ((unsigned long) size < fwd->size)
{
fwd = fwd->fd_nextsize;
assert ((fwd->size & NON_MAIN_ARENA) == 0);
}

if ((unsigned long) size == (unsigned long) fwd->size)
/* Always insert in the second position. */
fwd = fwd->fd;
else
{
victim->fd_nextsize = fwd;
victim->bk_nextsize = fwd->bk_nextsize;
fwd->bk_nextsize = victim;
victim->bk_nextsize->fd_nextsize = victim;
}
bck = fwd->bk;
}
}
else
victim->fd_nextsize = victim->bk_nextsize = victim;
}

mark_bin (av, victim_index);
victim->bk = bck;
victim->fd = fwd;
fwd->bk = victim;
bck->fd = victim;

#define MAX_ITERS 10000
if (++iters >= MAX_ITERS)
break;
}

unsorted分配的源码比较长,因为涉及到了从unsorted bin链表卸除的部分。

第一行,unsorted bin遍历,通过判断bk指针是否指向自己来表示是否遍历完毕。

第四行,对每一个unsorted chunk的size进行判断,大小要大于8字节,小于system_mem字节。

第18行,请求大小<512byte &&="" unsorted_chunks-="">bk->bk=unsorted_chunks(链表中之只有一个chunk) && victim为last_remainder chunk(main_arena+0x60) &&victim的大小要大于请求的大小。若通过转入19行

第19行-43行,从victim中分割出一个chunk分配,进行last_remainder chunk的更新,并将更新后的victim加入unsorted bin中。分配结束。

第46行 进行unsorted bin的拆卸,unsorted_chunks (av)->bk = victim->bk;
victim->bk->fd = unsorted_chunks (av); victim->bk可控会造成unsorted bin attack,且可以看出unsorted bin同样是先入后出的模式。

第52行,若存在unsorted chunk大小正好符合请求的大小,拆卸后分配出来。分配结束

第65行,此时unsorted bin已经不能满足分配要求,开始进行其他链表的插入操作。此行判断unsorted chunk大小是否属于small bin范围。

第66行-第70行,若大小属于small chunk,将他插入链表首部。(small bin优先分配链表末端chunk)

当大小属于large bin时,插入链表的位置需要进行判断。
large bin链表中每个chunk的大小可以不相等,且按照从大到小的顺序进行双向连接。
由于使用fd,bk组成的双向链表中会存在main_arena中的索引伪chunk。使用这样的双链表进行大小的排序会产生问题。
两个双向链表

large chunk增加一对指针fd_nextsize和bk_nextsize,用来组成只由空闲的large chunk的双向链表。

第78行,判断双向链表是否为空。

第84行,判断插入的chunk大小是否小于链表中最小的chunk size,若小于,则将他插入到main_arena索引及链表中最小chunk中间,bck为插入chunk的前一个节点,fwd为插入chunk后一个节点。 同时将他插入到使用fd_nextsize和bk_nextsize组成链表的最末端。

第96,97行,判断插入的chunk大小是否大于链表中最大的chunk size,若不大于,寻找使用fd_nextsize和bk_nextsize组成链表中应该插入的位置。同样找到后fwd为插入chunk的后一个chunk,bck为前一个,在下面各分支结束进行插入操作。

第102行,若插入chunk大小等于链表中某一chunk size,只将它插入到fd,bk双向链表。

第105-110行,若插入大小不等于,插入到fd,bk fd_nextsize,bk_nextsize两个双向链表中。

第119-124行,fd,bk插入操作。

large bin

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
if (!in_smallbin_range (nb))
{
bin = bin_at (av, idx);

/* skip scan if empty or largest chunk is too small */
if ((victim = first (bin)) != bin &&
(unsigned long) (victim->size) >= (unsigned long) (nb))
{
victim = victim->bk_nextsize;
while (((unsigned long) (size = chunksize (victim)) <
(unsigned long) (nb)))
victim = victim->bk_nextsize;

/* Avoid removing the first entry for a size so that the skip
list does not have to be rerouted. */
if (victim != last (bin) && victim->size == victim->fd->size)
victim = victim->fd;

remainder_size = size - nb;
unlink (av, victim, bck, fwd);

/* Exhaust */
if (remainder_size < MINSIZE)
{
set_inuse_bit_at_offset (victim, size);
if (av != &main_arena)
victim->size |= NON_MAIN_ARENA;
}
/* Split */
else
{
remainder = chunk_at_offset (victim, nb);
/* We cannot assume the unsorted list is empty and therefore
have to perform a complete insert here. */
bck = unsorted_chunks (av);
fwd = bck->fd;
if (__glibc_unlikely (fwd->bk != bck))
{
errstr = "malloc(): corrupted unsorted chunks";
goto errout;
}
remainder->bk = bck;
remainder->fd = fwd;
bck->fd = remainder;
fwd->bk = remainder;
if (!in_smallbin_range (remainder_size))
{
remainder->fd_nextsize = NULL;
remainder->bk_nextsize = NULL;
}
set_head (victim, nb | PREV_INUSE |
(av != &main_arena ? NON_MAIN_ARENA : 0));
set_head (remainder, remainder_size | PREV_INUSE);
set_foot (remainder, remainder_size);
}
check_malloced_chunk (av, victim, nb);
void *p = chunk2mem (victim);
alloc_perturb (p, bytes);
return p;
}
}

第6行,判断链表是否为空及链表中最大chunk size是否大于请求的size,不符合要求跳转至下一步。

第10行,由小到大寻找最适合请求大小的chunk。

第16行,对链表中相同大小的chunk,选择second chunk。

第20行,使用unlink宏将匹配到的chunk从链表中卸下

第23行-61行,若拆分后剩余的chunk大小大于minsize,更新last_remainder指针,并将他插入unsorted bin链表,要求(unsorted_chunks (av)->fd->bk=bck),并将拆分的chunk分配出去。

bitmap

暂留以后补

TOP 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
victim = av->top;
size = chunksize (victim);

if ((unsigned long) (size) >= (unsigned long) (nb + MINSIZE))
{
remainder_size = size - nb;
remainder = chunk_at_offset (victim, nb);
av->top = remainder;
set_head (victim, nb | PREV_INUSE |
(av != &main_arena ? NON_MAIN_ARENA : 0));
set_head (remainder, remainder_size | PREV_INUSE);

check_malloced_chunk (av, victim, nb);
void *p = chunk2mem (victim);
alloc_perturb (p, bytes);
return p;
}

/* When we are using atomic ops to free fast chunks we can get
here for all block sizes. */
else if (have_fastchunks (av))
{
malloc_consolidate (av);
/* restore original bin index */
if (in_smallbin_range (nb))
idx = smallbin_index (nb);
else
idx = largebin_index (nb);
}

/*
Otherwise, relay to handle system-dependent cases
*/
else
{
void *p = sysmalloc (nb, av);
if (p != NULL)
alloc_perturb (p, bytes);
return p;
}
}

第4-17行,若top chunk的size大于需求的大小+MINSIZE,更新last remainder指针,拆分top_chunk分配出需求的chunk。

第21-29行,若top chunk不足,进行一次malloc_consolidate,.

第34-39行,进行sysmalloc函数,根据自身是否为main_arena进行top chunk的扩张或新分配。

malloc函数完