sysmalloc源码分析

之前在做SUCTF的note时接触到了house of orange的原理,即将top的大小修改为一个比较小的值,再分配一个比size大的值时,原来的top就会free并放入到unsorted bin里,重新产生一个新的top。而note这道题由于可以自己创造出unsorted bin,就没有修改top的大小。今天简单看了一下sysmalloc的源码,重新认识了house of orange。ps:在网上找了一些大佬讲原理的blog,发现各位大佬都分析的是非主分配区部分的源码,而实际上多数用到的是main arena的源码,虽然原理类似,但是金牛座就愿意钻牛角尖=。=

一个用来调试的栗子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#define fake_size 0x1fe1

int main(void)
{
void *ptr;

ptr=malloc(0x10);
ptr=(void *)((int)ptr+24);

*((long long*)ptr)=fake_size;

malloc(0x2000);

malloc(0x60);
}

栗子参考了ctf-wiki,将top的大小改为了0x1fe1,然后再分配0x2000大小的chunk,由于_int_malloc的其他环节都不能处理了,由此调用sysmalloc

sysmalloc的源码

根据上面的栗子,在第二个malloc处对sysmalloc的源码逐步分析的

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
static void *
sysmalloc (INTERNAL_SIZE_T nb, mstate av)
{
mchunkptr old_top; /* incoming value of av->top */
INTERNAL_SIZE_T old_size; /* its size */
char *old_end; /* its end address */

long size; /* arg to first MORECORE or mmap call */
char *brk; /* return value from MORECORE */

long correction; /* arg to 2nd MORECORE call */
char *snd_brk; /* 2nd return val */

INTERNAL_SIZE_T front_misalign; /* unusable bytes at front of new space */
INTERNAL_SIZE_T end_misalign; /* partial page left at end of new space */
char *aligned_brk; /* aligned offset into brk */

mchunkptr p; /* the allocated/returned chunk */
mchunkptr remainder; /* remainder from allocation */
unsigned long remainder_size; /* its size */


size_t pagesize = GLRO (dl_pagesize);
bool tried_mmap = false;


/*
If have mmap, and the request size meets the mmap threshold, and
the system supports mmap, and there are few enough currently
allocated mmapped regions, try to directly map this request
rather than expanding top.
*/

if (av == NULL
|| ((unsigned long) (nb) >= (unsigned long) (mp_.mmap_threshold)
&& (mp_.n_mmaps < mp_.n_mmaps_max)))
{
……
}

av是当前的分配区,mmap_threshold是能够使用mmap分配的阈值,n_mmaps_max是mmap分配的内存块设定的最大值,调试查看这两个值:

mp_结构体

显然当前我们输入的0x2000不满足这个条件,执行下一个分支。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
old_top = av->top;
old_size = chunksize (old_top);
old_end = (char *) (chunk_at_offset (old_top, old_size));

brk = snd_brk = (char *) (MORECORE_FAILURE);

/*
If not the first time through, we require old_size to be
at least MINSIZE and to have prev_inuse set.
*/

assert ((old_top == initial_top (av) && old_size == 0) ||
((unsigned long) (old_size) >= MINSIZE &&
prev_inuse (old_top) &&
((unsigned long) old_end & (pagesize - 1)) == 0));

/* Precondition: not enough current space to satisfy nb request */
assert ((unsigned long) (old_size) < (unsigned long) (nb + MINSIZE));

接下来获取原来的top信息:起始地址、大小、终止地址。并且要求满足两个assert的条件:

  1. 第一次调用sysmalloc函数,top还没有初始化;或者已经初始化,top的大小大于MINSIZE(0x20),前一个chunk处于inuse状态,以及top chunk的结束地址是页对齐的。
  2. 原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
if (av != &main_arena)
{
……
}
else /* av == main_arena */
{ /* Request enough space for nb + pad + overhead */
size = nb + mp_.top_pad + MINSIZE;

/*
If contiguous, we can subtract out existing space that we hope to
combine with new space. We add it back later only if
we don't actually get contiguous space.
*/

if (contiguous (av))
size -= old_size;

/*
Round to a multiple of page size.
If MORECORE is not contiguous, this ensures that we only call it
with whole-page arguments. And if MORECORE is contiguous and
this is not first time through, this preserves page-alignment of
previous calls. Otherwise, we correct to page-align below.
*/

size = ALIGN_UP (size, pagesize);

/*
Don't try to call MORECORE if argument is so big as to appear
negative. Note that since mmap takes size_t arg, it may succeed
below even if we cannot call MORECORE.
*/

if (size > 0)
{
brk = (char *) (MORECORE (size));
LIBC_PROBE (memory_sbrk_more, 2, brk, size);
}

之后是判断av是主分配区还是配主分配区,大部分大佬分析的都是非主分配区这部分,我这里就主要看主分配区了。先是重新计算需要分配的size。然后判断当前分配区是否连续,并将size按照页对齐。当size>0时,通过MORECOREsbrk)分配连续的内存。

contiguous函数定义为:

1
2
#define NONCONTIGUOUS_BIT     (2U)
#define contiguous(M) (((M)->flags & NONCONTIGUOUS_BIT) == 0)
1
2
3
4
5
6
7
8
9
10
11
if (brk != (char *) (MORECORE_FAILURE))
{
/* Call the `morecore' hook if necessary. */
void (*hook) (void) = atomic_forced_read (__after_morecore_hook);
if (__builtin_expect (hook != NULL, 0))
(*hook)();
}
else
{
……
}

如果sbrk分配成功,并且MORECORE的hook函数存在,调用hook函数。(还不清楚hook用来干嘛)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
if (brk != (char *) (MORECORE_FAILURE))
{
if (mp_.sbrk_base == 0)
mp_.sbrk_base = brk;
av->system_mem += size;

/*
If MORECORE extends previous space, we can likewise extend top size.
*/

if (brk == old_end && snd_brk == (char *) (MORECORE_FAILURE))
set_head (old_top, (size + old_size) | PREV_INUSE);

else if (contiguous (av) && old_size && brk < old_end)
{
/* Oops! Someone else killed our space.. Can't touch anything. */
malloc_printerr (3, "break adjusted to free malloc space", brk,
av);
}

如果sbrk_base还没有初始化,就根据brk修改sbrk_base的值。更新当前分配区的内存分配总量。

如果新的brk和旧的top结尾是同一地址,也就是说新分配的内存与原top是挨着的,就直接更新原top头中的大小和PREV_INUSE位,相当于直接扩大了top。

如果brk小于原top结尾,则出错。

而对于house of orange,由于我们修改了top大小,top_end也提前了,此时分配的brk和top_end不是同一地址,而是从未修改前的top结尾开始分配的内存,即以上两个条件都不满足,从而进入到下面的这个分支。

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
      else
{
front_misalign = 0;
end_misalign = 0;
correction = 0;
aligned_brk = brk;

/* handle contiguous cases */
……
/* Adjust top based on results of second sbrk */
if (snd_brk != (char *) (MORECORE_FAILURE))
{
av->top = (mchunkptr) aligned_brk;
set_head (av->top, (snd_brk - aligned_brk + correction) | PREV_INUSE);
av->system_mem += correction;

/*
If not the first time through, we either have a
gap due to foreign sbrk or a non-contiguous region. Insert a
double fencepost at old_top to prevent consolidation with space
we don't own. These fenceposts are artificial chunks that are
marked as inuse and are in any case too small to use. We need
two to make sizes and alignments work out.
*/

if (old_size != 0)
{
/*
Shrink old_top to insert fenceposts, keeping size a
multiple of MALLOC_ALIGNMENT. We know there is at least
enough space in old_top to do this.
*/
old_size = (old_size - 4 * SIZE_SZ) & ~MALLOC_ALIGN_MASK;
set_head (old_top, old_size | PREV_INUSE);

/*
Note that the following assignments completely overwrite
old_top when old_size was previously MINSIZE. This is
intentional. We need the fencepost, even if old_top otherwise gets
lost.
*/
chunk_at_offset (old_top, old_size)->size =
(2 * SIZE_SZ) | PREV_INUSE;

chunk_at_offset (old_top, old_size + 2 * SIZE_SZ)->size =
(2 * SIZE_SZ) | PREV_INUSE;

/* If possible, release the rest. */
if (old_size >= MINSIZE)
{
_int_free (av, old_top, 1);
}
}
}
}
}
} /* if (av != &main_arena) */

先有一些对齐操作,这里省略掉了,其中aligned_brk就是处理好之后的内存地址。

重新设置av->top的地址,为重新分配的aligned_brk,然后通过set_head设置top的大小和标志位,更新分配区的总分配内存量。

接着将top chunk切分为fenceposts和空闲块两部分,设置切分出空闲chunk大小为old_size。最终通过int_free释放掉old_top。

执行前后heap的大小比对:

原heap

执行后的heap

以及top地址的变化:

原top

执行后的新top地址

第二个malloc执行结束后,unsortedbin中存放的即为原来的top地址

unsorted bin

总结

将sysmalloc的流程简化为以下流程(针对上面的栗子):