1.first_fit

发表于 | 分类于 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int	main(){
	char*	a	=	malloc(512);
	char*	b	=	malloc(256);
	char*	c;
	fprintf(stderr,	"1st	malloc(512):	%p\n",	a);
	fprintf(stderr,	"2nd	malloc(256):	%p\n",	b);
	strcpy(a,	"AAAAAAAA");
	strcpy(b,	"BBBBBBBB");
	fprintf(stderr,	"first	allocation	%p	points	to	%s\n",	a,	a);
	fprintf(stderr,	"Freeing	the	first	one...\n");
	free(a);
	c	=	malloc(500);
	fprintf(stderr,	"3rd	malloc(500):	%p\n",	c);
	strcpy(c,	"CCCCCCCC");
	fprintf(stderr,	"3rd	allocation	%p	points	to	%s\n",	c,	c);
	fprintf(stderr,	"first	allocation	%p	points	to	%s\n",	a,	a);
}

申请512的堆
申请256的堆
释放512的堆
再申请500的堆

1
2
3
4
5
6
7
8
9
10
11
user@ubuntu:~/workspace/pwn/first_fit$ vim first_fit.c
user@ubuntu:~/workspace/pwn/first_fit$ gcc -g first_fit.c  -o first_fit
user@ubuntu:~/workspace/pwn/first_fit$ ./first_fit 
1st	malloc(512):	0x602010
2nd	malloc(256):	0x602220
first	allocation	0x602010	points	to	AAAAAAAA
Freeing	the	first	one...
3rd	malloc(500):	0x602010
3rd	allocation	0x602010	points	to	CCCCCCCC
first	allocation	0x602010	points	to	CCCCCCCC
user@ubuntu:~/workspace/pwn/first_fit$

==这第一个程序展示了glibc堆分配的策略，即first-fit。在分配内存时，malloc会先到unsortedbin（或者fastbins） 中查找适合的被free的chunk，如果没有，就会把unsorted bin中的所有chunk分别放入到所属的bins中，然后再去这些bins里去找合适的chunk。可以看到第三次malloc的地址和第一次相同，即malloc找到了第一次free掉的chunk，并把它重新分配。==

gdb调试这个程序

0x1 malloc(512); malloc(256);

两次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
pwndbg> x/6gx 0x602010-0x10
0x602000:	0x0000000000000000	0x0000000000000211
0x602010:	0x4141414141414141	0x0000000000000000
0x602020:	0x0000000000000000	0x0000000000000000
pwndbg> x/6gx 0x602220-0x10
0x602210:	0x0000000000000000	0x0000000000000111
0x602220:	0x4242424242424242	0x0000000000000000
0x602230:	0x0000000000000000	0x0000000000000000



pwndbg> p main_arena
$14 = {
  mutex = 0x0, 
  flags = 0x1, 
  fastbinsY = {0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0}, 
  top = 0x602320, 
  last_remainder = 0x0, 
  bins = {0x7ffff7dd1b78 <main_arena+88>, 0x7ffff7dd1b78 <main_arena+88>, 0x7ffff7dd1b88 <main_arena+104>, 0x7ffff7dd1b88 <main_arena+104>, 0x7ffff7dd1b98 <main_arena+120>, 0x7ffff7dd1b98 <main_arena+120>, 0x7ffff7dd1ba8 <main_arena+136>, 0x7ffff7dd1ba8 <main_arena+136>, 0x7ffff7dd1bb8 <main_arena+152>, 0x7ffff7dd1bb8 <main_arena+152>, 0x7ffff7dd1bc8 <main_arena+168>, 0x7ffff7dd1bc8 <main_arena+168>, 0x7ffff7dd1bd8 <main_arena+184>, 0x7ffff7dd1bd8 <main_arena+184>, 0x7ffff7dd1be8 <main_arena+200>...}, 
  binmap = {0x0, 0x0, 0x0, 0x0}, 
  next = 0x7ffff7dd1b20 <main_arena>, 
  next_free = 0x0, 
  attached_threads = 0x1, 
  system_mem = 0x21000, 
  max_system_mem = 0x21000
}



pwndbg> x/14gx &main_arena.bins
0x7ffff7dd1b88 <main_arena+104>:	0x00007ffff7dd1b78	0x00007ffff7dd1b78
0x7ffff7dd1b98 <main_arena+120>:	0x00007ffff7dd1b88	0x00007ffff7dd1b88
0x7ffff7dd1ba8 <main_arena+136>:	0x00007ffff7dd1b98	0x00007ffff7dd1b98
0x7ffff7dd1bb8 <main_arena+152>:	0x00007ffff7dd1ba8	0x00007ffff7dd1ba8
0x7ffff7dd1bc8 <main_arena+168>:	0x00007ffff7dd1bb8	0x00007ffff7dd1bb8
0x7ffff7dd1bd8 <main_arena+184>:	0x00007ffff7dd1bc8	0x00007ffff7dd1bc8
0x7ffff7dd1be8 <main_arena+200>:	0x00007ffff7dd1bd8	0x00007ffff7dd1bd8
......
0x7ffff7dd2338 <main_arena+2072>:	0x00007ffff7dd2328	0x00007ffff7dd2328
0x7ffff7dd2348 <main_arena+2088>:	0x00007ffff7dd2338	0x00007ffff7dd2338
0x7ffff7dd2358 <main_arena+2104>:	0x00007ffff7dd2348	0x00007ffff7dd2348
0x7ffff7dd2368 <main_arena+2120>:	0x00007ffff7dd2358	0x00007ffff7dd2358
binmap-->0x7ffff7dd2378 <main_arena+2136>:	0x0000000000000000	0x0000000000000000

0x3 free(a)

释放掉这个512Byte的堆

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
pwndbg> x/6gx 0x602010-0x10
0x602000:	0x0000000000000000	0x0000000000000211
0x602010:	0x00007ffff7dd1b78	0x00007ffff7dd1b78
0x602020:	0x0000000000000000	0x0000000000000000
pwndbg> x/6gx 0x602220-0x10
0x602210:	0x0000000000000210	0x0000000000000110
0x602220:	0x4242424242424242	0x0000000000000000
0x602230:	0x0000000000000000	0x0000000000000000




pwndbg> p main_arena
$17 = {
  mutex = 0x0, 
  flags = 0x1, 
  fastbinsY = {0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0}, 
  top = 0x602320, 
  last_remainder = 0x0, 
  bins = {0x602000, 0x602000, 0x7ffff7dd1b88 <main_arena+104>, 0x7ffff7dd1b88 <main_arena+104>, 0x7ffff7dd1b98 <main_arena+120>, 0x7ffff7dd1b98 <main_arena+120>, 0x7ffff7dd1ba8 <main_arena+136>, 0x7ffff7dd1ba8 <main_arena+136>, 0x7ffff7dd1bb8 <main_arena+152>, 0x7ffff7dd1bb8 <main_arena+152>, 0x7ffff7dd1bc8 <main_arena+168>, 0x7ffff7dd1bc8 <main_arena+168>, 0x7ffff7dd1bd8 <main_arena+184>, 0x7ffff7dd1bd8 <main_arena+184>, 0x7ffff7dd1be8 <main_arena+200>...}, 
  binmap = {0x0, 0x0, 0x0, 0x0}, 
  next = 0x7ffff7dd1b20 <main_arena>, 
  next_free = 0x0, 
  attached_threads = 0x1, 
  system_mem = 0x21000, 
  max_system_mem = 0x21000
} 
pwndbg>

由上看出，a被free掉后，原本的用户数据域现在变成了fd域和bk域，而且被赋了值。这个0x7ffff7dd1b78是main_arena的地址+88。
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
pwndbg> heap
Top Chunk: 0x602320
Last Remainder: 0

0x602000 PREV_INUSE {
  prev_size = 0x0, 
  size = 0x211, 
  fd = 0x7ffff7dd1b78 <main_arena+88>, 
  bk = 0x7ffff7dd1b78 <main_arena+88>, 
  fd_nextsize = 0x0, 
  bk_nextsize = 0x0
}
0x602210 {
  prev_size = 0x210, 
  size = 0x110, 
  fd = 0x4242424242424242, 
  bk = 0x0, 
  fd_nextsize = 0x0, 
  bk_nextsize = 0x0
}
0x602320 PREV_INUSE {
  prev_size = 0x0, 
  size = 0x20ce1, 
  fd = 0x0, 
  bk = 0x0, 
  fd_nextsize = 0x0, 
  bk_nextsize = 0x0
}




pwndbg> bins
fastbins
0x20: 0x0
0x30: 0x0
0x40: 0x0
0x50: 0x0
0x60: 0x0
0x70: 0x0
0x80: 0x0
unsortedbin
all: 0x7ffff7dd1b78 (main_arena+88) —▸ 0x602000 ◂— 0x7ffff7dd1b78
smallbins
empty
largebins
empty
pwndbg>

，

第一个free后，被加入到unsorted bin中。这时fd和bk里的值都没undorted bins链表的表头。main_arena + 0x58处。

==注意chunk b，chunk b的pre_size字段和size的pre_inuse标志位都变了。==

0x04 malloc(500) 0x200 - 12

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
pwndbg> heap
Top Chunk: 0x602320
Last Remainder: 0

0x602000 PREV_INUSE {
  prev_size = 0x0, 
  size = 0x211, 
  fd = 0x7ffff7dd1d78 <main_arena+600>, 
  bk = 0x7ffff7dd1d78 <main_arena+600>, 
  fd_nextsize = 0x0, 
  bk_nextsize = 0x0
}
0x602210 PREV_INUSE {
  prev_size = 0x210, 
  size = 0x111, 
  fd = 0x4242424242424242, 
  bk = 0x0, 
  fd_nextsize = 0x0, 
  bk_nextsize = 0x0
}
0x602320 PREV_INUSE {
  prev_size = 0x0, 
  size = 0x20ce1, 
  fd = 0x0, 
  bk = 0x0, 
  fd_nextsize = 0x0, 
  bk_nextsize = 0x0
}
pwndbg> bins
fastbins
0x20: 0x0
0x30: 0x0
0x40: 0x0
0x50: 0x0
0x60: 0x0
0x70: 0x0
0x80: 0x0
unsortedbin
all: 0x0
smallbins
empty
largebins
empty
pwndbg>

所以当释放一块内存后再申请一块大小略小于的空间，那么glibc倾向于将先前被释放的空间重新分配。

且这个unsorted bins的位置是在main_arena偏移0x58处

总结

glibc堆分配的策略，即first-fit。在分配内存时，malloc会先到unsorted bin（或者fastbins）中查找适合的被free的chunk，如果没有，就会把unsorted bin中的所有chunk分别放入到所属的bins中，然后再去这些bins里去找合适的 chunk。可以看到第三次malloc的地址和第一次相同，即malloc找到了第一次 free掉的chunk，并把它重新分配.