ptmalloc源码学习(二)

ptmalloc源码学习第二篇,malloc的过程。

说明:本篇文章的所有源码均来自glibc-2.29,主要是arena.c和malloc.c这两个源文件。

__libc_malloc

检查malloc_hook

调用malloc时,真正调用执行的是libc_malloc函数,该函数首先检查是否有malloc_hook存在,在有关堆的漏洞利用中最后可以通过修改malloc_hook为system函数或one_gadget,然后调用malloc触发malloc_hook,从而获得shell:

1
2
3
4
5
6
7
8
9
10
void *
__libc_malloc (size_t bytes)
{
mstate ar_ptr;
void *victim;

void *(*hook) (size_t, const void *)
= atomic_forced_read (__malloc_hook);
if (__builtin_expect (hook != NULL, 0))
return (*hook)(bytes, RETURN_ADDRESS (0));

检查是否有tcache

然后检测是否使用tcache,在libc2.26之后有了tcache,tcache相当于在fastbin之前又设置了一个内存块的缓存,在进行malloc时首先尝试在tcache中寻找是否有合适的内存块,初次malloc时,会进入到MAYBE_INIT_TCACHE ()进行tcache的初始化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#if USE_TCACHE
/* int_free also calls request2size, be careful to not pad twice. */
size_t tbytes;
checked_request2size (bytes, tbytes); //将用户申请的chunk大小转化为真正分配的chunk大小
size_t tc_idx = csize2tidx (tbytes); //计算tcache的下标
//初始化tcache
MAYBE_INIT_TCACHE ();

DIAG_PUSH_NEEDS_COMMENT;
//申请的size在tcache范围内
if (tc_idx < mp_.tcache_bins
/*&& tc_idx < TCACHE_MAX_BINS*/ /* to appease gcc */
&& tcache
&& tcache->entries[tc_idx] != NULL) //对应的tcache链表不为空
{
return tcache_get (tc_idx);
}
DIAG_POP_NEEDS_COMMENT;
#endif

tcache初始化

MAYBE_INIT_TCACHE()中调用了tcache_init()进行初始化,每个线程都有一个tcache_perthread_struct,用于管理tcache。

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
# define MAYBE_INIT_TCACHE() \
if (__glibc_unlikely (tcache == NULL)) \
tcache_init();

static void
tcache_init(void)
{
mstate ar_ptr;
void *victim = 0;
const size_t bytes = sizeof (tcache_perthread_struct);

if (tcache_shutting_down)
return;
//找到可用的分配区
arena_get (ar_ptr, bytes);
//申请一个大小为tcache_perthread_struct的chunk
victim = _int_malloc (ar_ptr, bytes);
if (!victim && ar_ptr != NULL)
{
ar_ptr = arena_get_retry (ar_ptr, bytes);
victim = _int_malloc (ar_ptr, bytes);
}


if (ar_ptr != NULL)
__libc_lock_unlock (ar_ptr->mutex);

/* In a low memory situation, we may not be able to allocate memory
- in which case, we just keep trying later. However, we
typically do this very early, so either there is sufficient
memory, or there isn't enough memory to do non-trivial
allocations anyway. */
//初始化tcache
if (victim)
{
tcache = (tcache_perthread_struct *) victim;
memset (tcache, 0, sizeof (tcache_perthread_struct));
}

}

tcache_init()成功执行后,tcache_perthread_struct被成功建立,它有TCACHE_MAX_BINS个计数器和TCACHE_MAX_BINS个entry,TCACHE_MAX_BINS最大为64。在2.29的tcache_entry中除了有一个next指针外,还增加了一个key,用来检测tcache中是否存在double free。

1
2
3
4
5
6
7
8
9
10
11
12
13
typedef struct tcache_perthread_struct
{
char counts[TCACHE_MAX_BINS]; //记录每个tcache_entry上空闲chunk的数量,最大为7个
tcache_entry *entries[TCACHE_MAX_BINS]; //使用单链表形式链接相同大小的空闲chunk
} tcache_perthread_struct;

typedef struct tcache_entry
{
struct tcache_entry *next;
/* This field exists to detect double frees. */
struct tcache_perthread_struct *key;
} tcache_entry;
# define TCACHE_MAX_BINS 64

从tcache中分配chunk

当不是初次进行tcache分配或tcache初始化完毕后,__libc_malloc函数尝试从tcache中寻找合适的chunk,通过tc_idx找到对应的tcache_entry,如果tcache链表不为空,则调用tcache_get分配一个chunk并返回。

1
2
3
4
5
6
7
8
//申请的size在tcache范围内
if (tc_idx < mp_.tcache_bins
/*&& tc_idx < TCACHE_MAX_BINS*/ /* to appease gcc */
&& tcache
&& tcache->entries[tc_idx] != NULL) //对应的tcache链表不为空
{
return tcache_get (tc_idx);
}

tcache_get函数从相应的tcache链中取出一个堆块,当成功分配到这个堆块时,会将该堆块的key置为空,对应tcache_entry链表的count减一。

1
2
3
4
5
6
7
8
9
10
11
static __always_inline void *
tcache_get (size_t tc_idx)
{
tcache_entry *e = tcache->entries[tc_idx];
assert (tc_idx < TCACHE_MAX_BINS);
assert (tcache->entries[tc_idx] > 0);
tcache->entries[tc_idx] = e->next;
--(tcache->counts[tc_idx]);
e->key = NULL;
return (void *) e;
}

如果没有tcache或tcache中没有合适的chunk,则继续执行,如果是单线程,则尝试调用从主分配区main_arena分配chunk。

1
2
3
4
5
6
7
if (SINGLE_THREAD_P)
{
victim = _int_malloc (&main_arena, bytes);
assert (!victim || chunk_is_mmapped (mem2chunk (victim)) ||
&main_arena == arena_for_chunk (mem2chunk (victim)));
return victim;
}

否则寻找一个arena调用_int_malloc尝试分配内存:

1
2
arena_get (ar_ptr, bytes);
victim = _int_malloc (ar_ptr, bytes);

如果分配失败则尝试再次寻找一个arena并调用_int_malloc分配内存,如果分配成功,则释放该分配区的锁。

1
2
3
4
5
6
7
8
9
10
11
/* Retry with another arena only if we were able to find a usable arena
before. */
if (!victim && ar_ptr != NULL)
{
LIBC_PROBE (memory_malloc_retry, 1, bytes);
ar_ptr = arena_get_retry (ar_ptr, bytes);
victim = _int_malloc (ar_ptr, bytes);
}

if (ar_ptr != NULL)
__libc_lock_unlock (ar_ptr->mutex);

此时有三种状态,没有成功分配;或者使用mmap分配内存;分配的内存在其所分配的arena中,最后__libc_malloc函数返回。

1
2
3
assert (!victim || chunk_is_mmapped (mem2chunk (victim)) ||
ar_ptr == arena_for_chunk (mem2chunk (victim)));
return victim;

_int_malloc

临时变量

首先定义了用到的临时变量,并将用户申请的chunk大小bytes转化为实际大小nb,都是无符号整数。

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
static void *
_int_malloc (mstate av, size_t bytes)
{
INTERNAL_SIZE_T nb; /* normalized request size */
unsigned int idx; /* associated bin index */
mbinptr bin; /* associated bin */

mchunkptr victim; /* inspected/selected chunk */
INTERNAL_SIZE_T size; /* its size */
int victim_index; /* its bin index */

mchunkptr remainder; /* remainder from a split */
unsigned long remainder_size; /* its size */

unsigned int block; /* bit map traverser */
unsigned int bit; /* bit map traverser */
unsigned int map; /* current word of binmap */

mchunkptr fwd; /* misc temp for linking */
mchunkptr bck; /* misc temp for linking */

#if USE_TCACHE
size_t tcache_unsorted_count; /* count of unsorted chunks processed */
#endif

checked_request2size (bytes, nb);

无可用arena

没有没有可用的arena,则调用mmap进行内存分配。

1
2
3
4
5
6
7
8
9
/* There are no usable arenas.  Fall back to sysmalloc to get a chunk from
mmap. */
if (__glibc_unlikely (av == NULL))
{
void *p = sysmalloc (nb, av);
if (p != NULL)
alloc_perturb (p, bytes);
return p;
}

fastbin

如果申请chunk大小在fastbin范围内,找到对应的fastbin链表,如果fastbin链表中有空闲chunk,检查其大小与索引是否一致,通过检查后说明找到了目标chunk。再返回之前,如果有tcache,且tcache链表中空闲chunk数量小于7,会将目标chunk对应的那个fastbin链表中的剩余的空闲chunk放入对应的tcache链表中,然后再返回。

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
if ((unsigned long) (nb) <= (unsigned long) (get_max_fast ()))
{
idx = fastbin_index (nb); //得到对应fastbin链表的下标
mfastbinptr *fb = &fastbin (av, idx); //得到对应fastbin链表的头指针
mchunkptr pp;
victim = *fb;

if (victim != NULL) //如果对应的fastbin链表不为空
{
if (SINGLE_THREAD_P)
*fb = victim->fd;
else
REMOVE_FB (fb, pp, victim); //利用fd遍历对应的链表中是否有空闲的chunk
//存在空闲的chunk
if (__glibc_likely (victim != NULL))
{ //检查找到的chunk大小与对应的fastbin索引是否一致
size_t victim_idx = fastbin_index (chunksize (victim)); //利用chunk大小计算索引
if (__builtin_expect (victim_idx != idx, 0))
malloc_printerr ("malloc(): memory corruption (fast)");
check_remalloced_chunk (av, victim, nb);
#if USE_TCACHE
/* While we're here, if we see other chunks of the same size,
stash them in the tcache. */
size_t tc_idx = csize2tidx (nb); //找到对应的tcache链表的索引
if (tcache && tc_idx < mp_.tcache_bins)
{
mchunkptr tc_victim;

/* While bin not empty and tcache not full, copy chunks. */
//遍历对应tcache链表
while (tcache->counts[tc_idx] < mp_.tcache_count
&& (tc_victim = *fb) != NULL)
{
if (SINGLE_THREAD_P)
*fb = tc_victim->fd;
else
{
REMOVE_FB (fb, pp, tc_victim);
if (__glibc_unlikely (tc_victim == NULL))
break;
}
tcache_put (tc_victim, tc_idx); //将chunk放入tcache中
}
}
#endif
void *p = chunk2mem (victim); //转化为mem,即指向chunk的数据区
alloc_perturb (p, bytes);
return p;
}
}
}

tcache_put将chunk放入tcache中,同时会将该堆块的key置为tcache,便于下次free时进行检查,防止double free。

1
2
3
4
5
6
7
8
9
10
11
12
13
static __always_inline void
tcache_put (mchunkptr chunk, size_t tc_idx)
{
tcache_entry *e = (tcache_entry *) chunk2mem (chunk);
assert (tc_idx < TCACHE_MAX_BINS);

/* Mark this chunk as "in the tcache" so the test in _int_free will
detect a double free. */
e->key = tcache; //patch

e->next = tcache->entries[tc_idx];
tcache->entries[tc_idx] = e;
++(tcache->counts[tc_idx]);

smallbin

如果tcache、fastbin中没有找到合适的chunk,请求的chunk大小在smallbin范围内,通过索引找到对应的smallbin链表,如果bin中有空闲chunk,将smallbi双向链表中的最后一个chunk进行解链并取出。在返回之前同样检查是否有tcache,如果这个bin中还有相同大小的空闲chunk,且tcache还有空闲位置可以放入,就将双向链表中的空闲chunk移除tcache链表中。最后返回victim。

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
if (in_smallbin_range (nb))
{
idx = smallbin_index (nb); //获取smallbin的索引
bin = bin_at (av, idx); //获取对应smallbin中对应的chunk的头指针

if ((victim = last (bin)) != bin) //如果smallbin链表不为空
{
bck = victim->bk; //获取victim的前一个chunk
if (__glibc_unlikely (bck->fd != victim)) //检查victim->bk->fd与victim是否相等,防止伪造chunk
malloc_printerr ("malloc(): smallbin double linked list corrupted");
set_inuse_bit_at_offset (victim, nb); //修改victim的inuse位
//修改smallbin链表,将smallbin的最后一个chunk取出
bin->bk = bck; //将链表头bin的bk指向victim的bk
bck->fd = bin; //将victim的fd指向链表头

if (av != &main_arena) //如果分配区不是main_arena
set_non_main_arena (victim); //设置victim的NON_MAIN_ARENA位
check_malloced_chunk (av, victim, nb);
#if USE_TCACHE
/* While we're here, if we see other chunks of the same size,
stash them in the tcache. */
size_t tc_idx = csize2tidx (nb);
if (tcache && tc_idx < mp_.tcache_bins)
{
mchunkptr tc_victim;

/* While bin not empty and tcache not full, copy chunks over. */
while (tcache->counts[tc_idx] < mp_.tcache_count
&& (tc_victim = last (bin)) != bin)
{
if (tc_victim != 0)
{
bck = tc_victim->bk;
set_inuse_bit_at_offset (tc_victim, nb);
if (av != &main_arena)
set_non_main_arena (tc_victim);
bin->bk = bck;
bck->fd = bin;

tcache_put (tc_victim, tc_idx);
}
}
}
#endif
void *p = chunk2mem (victim); //转化为mem,即指向chunk的数据区
alloc_perturb (p, bytes);
return p;
}
}

largebin和chunk合并

当tcache,fastbin,smallbin中都没有找到合适的chunk时,就考虑largebin,但是先不再largebin中去寻找chunk,而是先调用malloc_consolidate函数进行fastbin空闲chunk的合并,合并后将chunk放入到unsorted bin中,不能够合并的chunk就直接放入unsorted bin中,然后再进行chunk的处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*
If this is a large request, consolidate fastbins before continuing.
While it might look excessive to kill all fastbins before
even seeing if there is space available, this avoids
fragmentation problems normally associated with fastbins.
Also, in practice, programs tend to have runs of either small or
large requests, but less often mixtures, so consolidation is not
invoked all that often in most programs. And the programs that
it is called frequently in otherwise tend to fragment.
*/

else
{
idx = largebin_index (nb); //计算下标
if (atomic_load_relaxed (&av->have_fastchunks)) //如果有fastbin的话
malloc_consolidate (av); //进行chunk的合并,这个函数稍后再说
}

unsorted bin循环遍历

合并后的chunk放入到了unsorted bin中,按照FIFO的规则遍历unsorted bin中的chunk,首先进行size域的检查。

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
for (;; )
{
int iters = 0;
//如果unsorted bin不为空,找到链表中的最后一个chunk
while ((victim = unsorted_chunks (av)->bk) != unsorted_chunks (av))
{
bck = victim->bk; //bck是victim的bk
size = chunksize (victim); //通过victim的size域得到自身size
mchunkptr next = chunk_at_offset (victim, size); 根据size获取victim的下一个chunk,记为next

//检查victim的size是否小于MINSIZE,以及是否超过当前分配区已经分配的大小
if (__glibc_unlikely (size <= 2 * SIZE_SZ)
|| __glibc_unlikely (size > av->system_mem))
malloc_printerr ("malloc(): invalid size (unsorted)");

//检查next的size是否小于MINSIZE,以及是否超过当前分配区已经分配的大小
if (__glibc_unlikely (chunksize_nomask (next) < 2 * SIZE_SZ)
|| __glibc_unlikely (chunksize_nomask (next) > av->system_mem))
malloc_printerr ("malloc(): invalid next size (unsorted)");

//利用next->prev_size与victim的size是否一致
if (__glibc_unlikely ((prev_size (next) & ~(SIZE_BITS)) != size))
malloc_printerr ("malloc(): mismatching next->prev_size (unsorted)");

//检查victim->bk->fd是否等于victim,以及检查是否存在double free
if (__glibc_unlikely (bck->fd != victim)
|| __glibc_unlikely (victim->fd != unsorted_chunks (av)))
malloc_printerr ("malloc(): unsorted double linked list corrupted");

//检查next的prev_iuse位,防止产生chunk overlap
if (__glibc_unlikely (prev_inuse (next)))
malloc_printerr ("malloc(): invalid next->prev_inuse (unsorted)");

这里涉及到两个size的宏,size是通过victim自身的size域得到,去掉了SIZE_BITS,chunksize_nomask保留了chunk的低三个bit。

1
2
3
4
5
/* Get size, ignoring use bits */
#define chunksize(p) (chunksize_nomask (p) & ~(SIZE_BITS))

/* Like chunksize, but do not mask SIZE_BITS. */
#define chunksize_nomask(p) ((p)->mchunk_size)

last remainder

在遍历中如果unsorted bin中只有唯一的last remainder时,因为av是头指针,victim = av -> bk,如果victim -> bk指向头指针时,则说明unsorted bin中只有一个last remainder,如果last remainder符合分配要求,last remainder大小范围属于smallbin,就对last remainder进行分割,剩余的chunk作为新的remainder,并更新相应的标志位和指针指向,然后返回,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
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的大小,即减去nb
remainder = chunk_at_offset (victim, nb); //获取新的remainder的地址

//更新头指针av的fd和bk指向新的remainder
unsorted_chunks (av)->bk = unsorted_chunks (av)->fd = remainder;
av->last_remainder = remainder;

//更新remainder的bk和fd指向头指针av
remainder->bk = remainder->fd = unsorted_chunks (av);

if (!in_smallbin_range (remainder_size))
{
remainder->fd_nextsize = NULL;
remainder->bk_nextsize = NULL;
}

//设置victim的prev_inuse和NON_MAIN_ARENA位
set_head (victim, nb | PREV_INUSE |
(av != &main_arena ? NON_MAIN_ARENA : 0));

//设置remainder的prev_inuse位,remainder此时处于freed状态
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;
}

取出放入tcache

如果遍历的unsorted bin不符合last remainder的要求,检查victim->bk->fd与victim是否一致,通过检查后将victim从unsorted bin取出。如果victim恰好与请求的size相等,则设置victim的标志位。再检查是否有tcache,如果有tcache,且对应tcache链表还未满,则将取出的victim放入到tcache中,return_cached置1,继续while循环遍历unsorted bin中的chunk;如果有tcache且tcache链表已满,则直接返回victim,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
          /* remove from unsorted list */
if (__glibc_unlikely (bck->fd != victim))
malloc_printerr ("malloc(): corrupted unsorted chunks 3");
unsorted_chunks (av)->bk = bck; //将av->bk指向victim的bk
bck->fd = unsorted_chunks (av); //victim的bk的fd指向头指针

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

if (size == nb) //请求的size与victim的size恰好相等
{
set_inuse_bit_at_offset (victim, size); //设置victim相邻chunk的prev_inuse位,以标识victim
if (av != &main_arena)
set_non_main_arena (victim); //设置victim的NO_MAIN_ARENA位
#if USE_TCACHE
/* Fill cache first, return to user only if cache fills.
We may return one of these chunks later. */
if (tcache_nb
&& tcache->counts[tc_idx] < mp_.tcache_count)
{
tcache_put (victim, tc_idx);
return_cached = 1;
continue;
}
else
{
#endif
check_malloced_chunk (av, victim, nb);
void *p = chunk2mem (victim);
alloc_perturb (p, bytes);
return p;
#if USE_TCACHE
}
#endif
}

取出放入smallbin

如果没有tcache则继续执行while循环,如果victim在smallbin范围内,取出将其放入到smallbin中。这个地方现在还没有放入到smallbin中,但设置了头指针bck和fwd的值,在“真正放入到bin”小节中将其插入到链表中。

1
2
3
4
5
6
7
8
/* place chunk in bin */

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

取出放入largebin

如果unsorted bin中的chunk不是smallbin,则将其放入largebin中,这部分代码是再链表中寻找合适的位置,找到后首先修改nextsize域,修改完成后再将victim取出,并修改对应位置的fd和bk指针。

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
          else
{
victim_index = largebin_index (size); //找到索引
bck = bin_at (av, victim_index); //largebin的头指针
fwd = bck->fd;

/* maintain large bins in sorted order */
if (fwd != bck) // largebin链表不为空
{
/* Or with inuse bit to speed comparisons */
size |= PREV_INUSE;
/* if smaller than smallest, bypass loop below */
assert (chunk_main_arena (bck->bk)); 判断最后一个chunk是否在主分配区内

//victim的size小于链表中最后一个chunk的size,将victim插入到链表尾部
if ((unsigned long) (size)
< (unsigned long) chunksize_nomask (bck->bk)) //头指针的bk是最后一个chunk
{
fwd = bck; //fwd指向链表头部
bck = bck->bk; //bck指向链表尾部
victim->fd_nextsize = fwd->fd; //victim->fd_nextsize指向链表中第一个chunk
//victim->bk_nextsize指向原来链表第一个chunk指向的bk_nextsize,即原来链表的最后一个chunk
victim->bk_nextsize = fwd->fd->bk_nextsize;

//原来链表第一个chunk的bk_nextsize指向victim,原来最后一个链表的最后一个chunk的fd_nextsize指向victim
fwd->fd->bk_nextsize = victim->bk_nextsize->fd_nextsize = victim;
}
else
{ ////插入的chunk的大小大于当前链表中最小的chunk
assert (chunk_main_arena (fwd));

//从链表头开始寻找第一个不大于victim的chunk
while ((unsigned long) size < chunksize_nomask (fwd))
{
fwd = fwd->fd_nextsize;
assert (chunk_main_arena (fwd));
}

//如果找到与victim相等的chunk,直接插入
if ((unsigned long) size
== (unsigned long) chunksize_nomask (fwd))
/* Always insert in the second position. */
fwd = fwd->fd;

//找到小于victim的chunk,fwd指向比victim小的chunk,插入到fwd前面,并更新nextsize。
else
{
victim->fd_nextsize = fwd;
victim->bk_nextsize = fwd->bk_nextsize;
fwd->bk_nextsize = victim;
victim->bk_nextsize->fd_nextsize = victim;
}
bck = fwd->bk;
}
}

//如果当前largebin链表为空,则插入的victim自己构成一个双向链表
else
victim->fd_nextsize = victim->bk_nextsize = victim;
}
### 真正放入到bin中
将其放入到对应的smallbin或largbin中。
~~~C
//取出victim插入到链表中,并修改fd和bk
mark_bin (av, victim_index);
victim->bk = bck;
victim->fd = fwd;
fwd->bk = victim;
bck->fd = victim;

检查tcache和迭代次数

在循环中如果遍历的victim恰好与请求的size相同,则先插入到tcache中,当循环执行若干次后,可能有一些chunk插入到了tcache中,这里再检查是否有tcache机制,且tcache中有刚刚插入的大小恰好相同的空闲chunk,则返回这样的chunk,程序结束。另外规定了while循环的迭代次数最多执行10000次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#if USE_TCACHE
/* If we've processed as many chunks as we're allowed while
filling the cache, return one of the cached ones. */
++tcache_unsorted_count;
if (return_cached
&& mp_.tcache_unsorted_limit > 0
&& tcache_unsorted_count > mp_.tcache_unsorted_limit)
{
return tcache_get (tc_idx);
}
#endif

#define MAX_ITERS 10000
if (++iters >= MAX_ITERS)
break;
} //while循环的边界

跳出while循环后又检查了一次tcache,如果tcache之前被放入过大小相等的chunk,则取出返回,程序结束。到这里unsorted bin的遍历就结束了,在遍历时将合并后的chunk放入到tcache或largebin中,如果有大小恰好相等的chunk或唯一的last remainder符合要求,则直接返回该chunk,程序结束。

1
2
3
4
5
6
7
#if USE_TCACHE
/* If all the small chunks we found ended up cached, return one now. */
if (return_cached)
{
return tcache_get (tc_idx);
}
#endif

largebin

当请求的chunk不符合fastbin,smallbin且完成unsorted bin的遍历后,检查请求的chunk是否满足largebin。在largedbins中从小到大进行遍历,寻找第一个合适的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
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
  if (!in_smallbin_range (nb))
{
bin = bin_at (av, idx);

/* skip scan if empty or largest chunk is too small */
//跳过空的bin和当前链表中最大的chunk也小于nb的bin
if ((victim = first (bin)) != bin
&& (unsigned long) chunksize_nomask (victim)
>= (unsigned long) (nb))
{

//反向遍历链表,找到第一个不小于所需chunk大小的chunk
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. */
//如果找到的victim不是bin中的最后一个chunk,且victim的fd与其大小相同,则取后一个chunk,避免nextsize域的更改
if (victim != last (bin)
&& chunksize_nomask (victim)
== chunksize_nomask (victim->fd))
victim = victim->fd;

//计算分配后的剩余大小
remainder_size = size - nb;
//进行unlink解链
unlink_chunk (av, victim);

/* Exhaust */
//如果剩余的chunk小于MINSIZE,则直接分配size大小的chunk,不进行切割,并设置相应的标志位
if (remainder_size < MINSIZE)
{
set_inuse_bit_at_offset (victim, size);
if (av != &main_arena)
set_non_main_arena (victim);
}
/* Split */
else
{
//切割chunk,剩余部分为remainder,将remainder插入到unsorted bin中
remainder = chunk_at_offset (victim, nb);

/* We cannot assume the unsorted list is empty and therefore
have to perform a complete insert here. */
//首先检查unsorted bin是否被破坏,检查头指针bck->fd->bk是否等于bck
bck = unsorted_chunks (av);
fwd = bck->fd;
if (__glibc_unlikely (fwd->bk != bck))
malloc_printerr ("malloc(): corrupted unsorted chunks");

//将remainder插入到unsorted bin中
remainder->bk = bck;
remainder->fd = fwd;
bck->fd = remainder;
fwd->bk = remainder;

//如果不属于smallbin,则将nextsize域置空
if (!in_smallbin_range (remainder_size))
{
remainder->fd_nextsize = NULL;
remainder->bk_nextsize = NULL;
}

//设置相应的prev_insuse位
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;
}
}

寻找较大的chunk

分割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
42
43
44
45
46
47
48
49
50
51
52
53
54
use_top:
/*
If large enough, split off the chunk bordering the end of memory
(held in av->top). Note that this is in accord with the best-fit
search rule. In effect, av->top is treated as larger (and thus
less well fitting) than any other available chunk since it can
be extended to be as large as necessary (up to system
limitations).

We require that av->top always exists (i.e., has size >=
MINSIZE) after initialization, so if it would otherwise be
exhausted by current request, it is replenished. (The main
reason for ensuring it exists is that we may need MINSIZE space
to put in fenceposts in sysmalloc.)
*/

victim = av->top;
size = chunksize (victim);

if (__glibc_unlikely (size > av->system_mem))
malloc_printerr ("malloc(): corrupted top size");

//如果分割后的top chunk仍然满足MINSIZE的要求,则直接分割,并更新top chunk,设置标志位。
if ((unsigned long) (size) >= (unsigned long) (nb + MINSIZE))
{
remainder_size = size - nb;
remainder = chunk_at_offset (victim, nb);
av->top = remainder;

//设置prev_inuse防止nb与top chunk合并
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. */
//否则再判断是否有fastbin
else if (atomic_load_relaxed (&av->have_fastchunks))
{
malloc_consolidate (av); //先进行fastbin的合并

/* restore original bin index */
判断需要的chunk在smallbin范围还是largebin范围内,继续for循环,尝试下次分配
if (in_smallbin_range (nb))
idx = smallbin_index (nb);
else
idx = largebin_index (nb);
}

sysmalloc申请内存

如果top chunk不能满足分配需求,则尝试调用sysmalloc申请内存。

1
2
3
4
5
6
7
8
9
10
11
12
      /*
Otherwise, relay to handle system-dependent cases
*/
else
{
void *p = sysmalloc (nb, av);
if (p != NULL)
alloc_perturb (p, bytes);
return p;
}
}
}

参考

https://ctf-wiki.github.io/ctf-wiki/pwn/linux/glibc-heap/implementation/malloc-zh/
《glibc内存管理ptmalloc源代码分析@华庭》