Excuse the ads! We need some help to keep our site up.
List
Arena
Arena?
malloc()에서 메모리 영역과 메모리 관리 부분을 arena라고 합니다.
프로세스에 할당된 Heap 영역(non-mmapped )입니다.
Main Arena
- main_arena는 Malloc.c 에서 "struct malloc_state" 구조체를 사용하는 변수 입니다.
static struct malloc_state main_arena =
static struct malloc_state main_arena =
{
.mutex = _LIBC_LOCK_INITIALIZER,
.next = &main_arena,
.attached_threads = 1
};
- malloc_state 구조체의 형태는 다음과 같습니다.
- 해당 구조체를 이용해 Arena의 세부 정보를 보관합니다.
- 해당 정보를 이용해 할당된 chunk들을 관리합니다.
struct malloc_state
struct malloc_state
{
/* Serialize access. */
mutex_t mutex;
/* Flags (formerly in max_fast). */
int flags;
/* Fastbins */
mfastbinptr fastbinsY[NFASTBINS];
/* Base of the topmost chunk -- not otherwise kept in a bin */
mchunkptr top;
/* The remainder from the most recent split of a small request */
mchunkptr last_remainder;
/* Normal bins packed as described above */
mchunkptr bins[NBINS * 2 - 2];
/* Bitmap of bins */
unsigned int binmap[BINMAPSIZE];
/* Linked list */
struct malloc_state *next;
/* Linked list for free arenas. Access to this field is serialized
by free_list_lock in arena.c. */
struct malloc_state *next_free;
/* Number of threads attached to this arena. 0 if the arena is on
the free list. Access to this field is serialized by
free_list_lock in arena.c. */
INTERNAL_SIZE_T attached_threads;
/* Memory allocated from the system in this arena. */
INTERNAL_SIZE_T system_mem;
INTERNAL_SIZE_T max_system_mem;
};
- 이러한 정보들은 GDB에서 다음과 같이 확인할 수 있습니다.
p main_arena
gdb-peda$ p main_arena
$1 = {
mutex = 0x0,
flags = 0x1,
fastbinsY = {0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0},
top = 0x602070,
last_remainder = 0x0,
bins = {0x7ffff7dd37b8 <main_arena+88>, 0x7ffff7dd37b8 <main_arena+88>, 0x7ffff7dd37c8 <main_arena+104>, 0x7ffff7dd37c8 <main_arena+104>, 0x7ffff7dd37d8 <main_arena+120>, 0x7ffff7dd37d8 <main_arena+120>, 0x7ffff7dd37e8 <main_arena+136>, 0x7ffff7dd37e8 <main_arena+136>, 0x7ffff7dd37f8 <main_arena+152>, 0x7ffff7dd37f8 <main_arena+152>, 0x7ffff7dd3808 <main_arena+168>, 0x7ffff7dd3808 <main_arena+168>,
0x7ffff7dd3818 <main_arena+184>, 0x7ffff7dd3818 <main_arena+184>, 0x7ffff7dd3828 <main_arena+200>, 0x7ffff7dd3828 <main_arena+200>, 0x7ffff7dd3838 <main_arena+216>, 0x7ffff7dd3838 <main_arena+216>, 0x7ffff7dd3848 <main_arena+232>, 0x7ffff7dd3848 <main_arena+232>, 0x7ffff7dd3858 <main_arena+248>, 0x7ffff7dd3858 <main_arena+248>, 0x7ffff7dd3868 <main_arena+264>, 0x7ffff7dd3868 <main_arena+264>,
0x7ffff7dd3878 <main_arena+280>, 0x7ffff7dd3878 <main_arena+280>, 0x7ffff7dd3888 <main_arena+296>, 0x7ffff7dd3888 <main_arena+296>, 0x7ffff7dd3898 <main_arena+312>, 0x7ffff7dd3898 <main_arena+312>, 0x7ffff7dd38a8 <main_arena+328>, 0x7ffff7dd38a8 <main_arena+328>, 0x7ffff7dd38b8 <main_arena+344>, 0x7ffff7dd38b8 <main_arena+344>, 0x7ffff7dd38c8 <main_arena+360>, 0x7ffff7dd38c8 <main_arena+360>,
0x7ffff7dd38d8 <main_arena+376>, 0x7ffff7dd38d8 <main_arena+376>, 0x7ffff7dd38e8 <main_arena+392>, 0x7ffff7dd38e8 <main_arena+392>, 0x7ffff7dd38f8 <main_arena+408>, 0x7ffff7dd38f8 <main_arena+408>, 0x7ffff7dd3908 <main_arena+424>, 0x7ffff7dd3908 <main_arena+424>, 0x7ffff7dd3918 <main_arena+440>, 0x7ffff7dd3918 <main_arena+440>, 0x7ffff7dd3928 <main_arena+456>, 0x7ffff7dd3928 <main_arena+456>,
0x7ffff7dd3938 <main_arena+472>, 0x7ffff7dd3938 <main_arena+472>, 0x7ffff7dd3948 <main_arena+488>, 0x7ffff7dd3948 <main_arena+488>, 0x7ffff7dd3958 <main_arena+504>, 0x7ffff7dd3958 <main_arena+504>, 0x7ffff7dd3968 <main_arena+520>, 0x7ffff7dd3968 <main_arena+520>, 0x7ffff7dd3978 <main_arena+536>, 0x7ffff7dd3978 <main_arena+536>, 0x7ffff7dd3988 <main_arena+552>, 0x7ffff7dd3988 <main_arena+552>,
0x7ffff7dd3998 <main_arena+568>, 0x7ffff7dd3998 <main_arena+568>, 0x7ffff7dd39a8 <main_arena+584>, 0x7ffff7dd39a8 <main_arena+584>, 0x7ffff7dd39b8 <main_arena+600>, 0x7ffff7dd39b8 <main_arena+600>, 0x7ffff7dd39c8 <main_arena+616>, 0x7ffff7dd39c8 <main_arena+616>, 0x7ffff7dd39d8 <main_arena+632>, 0x7ffff7dd39d8 <main_arena+632>, 0x7ffff7dd39e8 <main_arena+648>, 0x7ffff7dd39e8 <main_arena+648>,
0x7ffff7dd39f8 <main_arena+664>, 0x7ffff7dd39f8 <main_arena+664>, 0x7ffff7dd3a08 <main_arena+680>, 0x7ffff7dd3a08 <main_arena+680>, 0x7ffff7dd3a18 <main_arena+696>, 0x7ffff7dd3a18 <main_arena+696>, 0x7ffff7dd3a28 <main_arena+712>, 0x7ffff7dd3a28 <main_arena+712>, 0x7ffff7dd3a38 <main_arena+728>, 0x7ffff7dd3a38 <main_arena+728>, 0x7ffff7dd3a48 <main_arena+744>, 0x7ffff7dd3a48 <main_arena+744>,
0x7ffff7dd3a58 <main_arena+760>, 0x7ffff7dd3a58 <main_arena+760>, 0x7ffff7dd3a68 <main_arena+776>, 0x7ffff7dd3a68 <main_arena+776>, 0x7ffff7dd3a78 <main_arena+792>, 0x7ffff7dd3a78 <main_arena+792>, 0x7ffff7dd3a88 <main_arena+808>, 0x7ffff7dd3a88 <main_arena+808>, 0x7ffff7dd3a98 <main_arena+824>, 0x7ffff7dd3a98 <main_arena+824>, 0x7ffff7dd3aa8 <main_arena+840>, 0x7ffff7dd3aa8 <main_arena+840>,
0x7ffff7dd3ab8 <main_arena+856>, 0x7ffff7dd3ab8 <main_arena+856>, 0x7ffff7dd3ac8 <main_arena+872>, 0x7ffff7dd3ac8 <main_arena+872>, 0x7ffff7dd3ad8 <main_arena+888>, 0x7ffff7dd3ad8 <main_arena+888>, 0x7ffff7dd3ae8 <main_arena+904>, 0x7ffff7dd3ae8 <main_arena+904>, 0x7ffff7dd3af8 <main_arena+920>, 0x7ffff7dd3af8 <main_arena+920>, 0x7ffff7dd3b08 <main_arena+936>, 0x7ffff7dd3b08 <main_arena+936>,
0x7ffff7dd3b18 <main_arena+952>, 0x7ffff7dd3b18 <main_arena+952>, 0x7ffff7dd3b28 <main_arena+968>, 0x7ffff7dd3b28 <main_arena+968>, 0x7ffff7dd3b38 <main_arena+984>, 0x7ffff7dd3b38 <main_arena+984>, 0x7ffff7dd3b48 <main_arena+1000>, 0x7ffff7dd3b48 <main_arena+1000>, 0x7ffff7dd3b58 <main_arena+1016>, 0x7ffff7dd3b58 <main_arena+1016>, 0x7ffff7dd3b68 <main_arena+1032>, 0x7ffff7dd3b68 <main_arena+1032>,
0x7ffff7dd3b78 <main_arena+1048>, 0x7ffff7dd3b78 <main_arena+1048>, 0x7ffff7dd3b88 <main_arena+1064>, 0x7ffff7dd3b88 <main_arena+1064>, 0x7ffff7dd3b98 <main_arena+1080>, 0x7ffff7dd3b98 <main_arena+1080>, 0x7ffff7dd3ba8 <main_arena+1096>, 0x7ffff7dd3ba8 <main_arena+1096>, 0x7ffff7dd3bb8 <main_arena+1112>, 0x7ffff7dd3bb8 <main_arena+1112>, 0x7ffff7dd3bc8 <main_arena+1128>, 0x7ffff7dd3bc8 <main_arena+1128>,
0x7ffff7dd3bd8 <main_arena+1144>, 0x7ffff7dd3bd8 <main_arena+1144>, 0x7ffff7dd3be8 <main_arena+1160>, 0x7ffff7dd3be8 <main_arena+1160>, 0x7ffff7dd3bf8 <main_arena+1176>, 0x7ffff7dd3bf8 <main_arena+1176>, 0x7ffff7dd3c08 <main_arena+1192>, 0x7ffff7dd3c08 <main_arena+1192>, 0x7ffff7dd3c18 <main_arena+1208>, 0x7ffff7dd3c18 <main_arena+1208>, 0x7ffff7dd3c28 <main_arena+1224>, 0x7ffff7dd3c28 <main_arena+1224>,
0x7ffff7dd3c38 <main_arena+1240>, 0x7ffff7dd3c38 <main_arena+1240>, 0x7ffff7dd3c48 <main_arena+1256>, 0x7ffff7dd3c48 <main_arena+1256>, 0x7ffff7dd3c58 <main_arena+1272>, 0x7ffff7dd3c58 <main_arena+1272>, 0x7ffff7dd3c68 <main_arena+1288>, 0x7ffff7dd3c68 <main_arena+1288>, 0x7ffff7dd3c78 <main_arena+1304>, 0x7ffff7dd3c78 <main_arena+1304>, 0x7ffff7dd3c88 <main_arena+1320>, 0x7ffff7dd3c88 <main_arena+1320>,
0x7ffff7dd3c98 <main_arena+1336>, 0x7ffff7dd3c98 <main_arena+1336>, 0x7ffff7dd3ca8 <main_arena+1352>, 0x7ffff7dd3ca8 <main_arena+1352>, 0x7ffff7dd3cb8 <main_arena+1368>, 0x7ffff7dd3cb8 <main_arena+1368>, 0x7ffff7dd3cc8 <main_arena+1384>, 0x7ffff7dd3cc8 <main_arena+1384>, 0x7ffff7dd3cd8 <main_arena+1400>, 0x7ffff7dd3cd8 <main_arena+1400>, 0x7ffff7dd3ce8 <main_arena+1416>, 0x7ffff7dd3ce8 <main_arena+1416>,
0x7ffff7dd3cf8 <main_arena+1432>, 0x7ffff7dd3cf8 <main_arena+1432>, 0x7ffff7dd3d08 <main_arena+1448>, 0x7ffff7dd3d08 <main_arena+1448>, 0x7ffff7dd3d18 <main_arena+1464>, 0x7ffff7dd3d18 <main_arena+1464>, 0x7ffff7dd3d28 <main_arena+1480>, 0x7ffff7dd3d28 <main_arena+1480>, 0x7ffff7dd3d38 <main_arena+1496>, 0x7ffff7dd3d38 <main_arena+1496>, 0x7ffff7dd3d48 <main_arena+1512>, 0x7ffff7dd3d48 <main_arena+1512>,
0x7ffff7dd3d58 <main_arena+1528>, 0x7ffff7dd3d58 <main_arena+1528>, 0x7ffff7dd3d68 <main_arena+1544>, 0x7ffff7dd3d68 <main_arena+1544>, 0x7ffff7dd3d78 <main_arena+1560>, 0x7ffff7dd3d78 <main_arena+1560>, 0x7ffff7dd3d88 <main_arena+1576>, 0x7ffff7dd3d88 <main_arena+1576>, 0x7ffff7dd3d98 <main_arena+1592>, 0x7ffff7dd3d98 <main_arena+1592>, 0x7ffff7dd3da8 <main_arena+1608>, 0x7ffff7dd3da8 <main_arena+1608>,
0x7ffff7dd3db8 <main_arena+1624>, 0x7ffff7dd3db8 <main_arena+1624>, 0x7ffff7dd3dc8 <main_arena+1640>, 0x7ffff7dd3dc8 <main_arena+1640>, 0x7ffff7dd3dd8 <main_arena+1656>, 0x7ffff7dd3dd8 <main_arena+1656>, 0x7ffff7dd3de8 <main_arena+1672>, 0x7ffff7dd3de8 <main_arena+1672>...},
binmap = {0x0, 0x0, 0x0, 0x0},
next = 0x7ffff7dd3760 <main_arena>,
next_free = 0x0,
system_mem = 0x21000,
max_system_mem = 0x21000
}
gdb-peda$
Chunk
Chunk type
- 다음과 같은 Chunk type 이 있습니다.
- Allocated chunk
- Free chunk
- Top chunk
- Last Remainder chunk
struct malloc_chunk
- Allocated, Free Chunk는 "malloc_chunk" 구조체를 이용해 필요한 정보를 저장합니다.
struct malloc_chunk
/*
----------------------- Chunk representations -----------------------
*/
/*
This struct declaration is misleading (but accurate and necessary).
It declares a "view" into memory allowing access to necessary
fields at known offsets from a given base. See explanation below.
*/
struct malloc_chunk {
INTERNAL_SIZE_T prev_size; /* Size of previous chunk (if free). */
INTERNAL_SIZE_T size; /* Size in bytes, including overhead. */
struct malloc_chunk* fd; /* double links -- used only if free. */
struct malloc_chunk* bk;
/* Only used for large blocks: pointer to next larger size. */
struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
struct malloc_chunk* bk_nextsize;
};
Allocated chunk
- Allocated chunk의 구조는 다음과 같습니다.
- Allocated 최소 크기는 다음과 같습니다.
- 32 Bit: 16 byte
- 64 Bit: 32 byte
- Allocated 최소 크기는 다음과 같습니다.
Allocated chunk Sample(64 bit)
| prev_size | Size of chunk | A | M | P | |||||||||||
User data | Next chunk(Size of chunk) | ||||||||||||||
- Allocated chunk는 다음과 같은 정보를 포함합니다.
| prev_size |
|
|---|---|
| size |
|
Example - Allocated chunk
- 다음과 같은 코드를 이용해 Allocated chunk를 확인합니다.
allocated.c
#include <stdio.h>
#include <stdlib.h>
void main(){
char *heap = malloc(8);
printf("Heap Addr : %p\n",heap);
free(heap);
}
다음과 같은 방법으로 Allocated chunk의 구조를 확인할 수 있습니다.
해당 Chunk 앞에 해제된 Chunk가 없기 때문에 prev_size 영역은 비워져있습니다.
size는 다음과 같은 값을 더한 값이 저장되어 있습니다.
Allocated chunk의 header 정보를 저장하는 공간 - 16byte
사용자가 요청한 Heap 공간의 크기 - 8 byte
Next chunk 정보를 저장할 공간 - 8 byte
Check allocated
lazenca0x0@ubuntu:~/Documents/def$ gcc -o allocated allocated.c lazenca0x0@ubuntu:~/Documents/def$ gdb ./allocated gdb-peda$ disassemble main Dump of assembler code for function main: 0x00000000004005bd <+0>: push rbp 0x00000000004005be <+1>: mov rbp,rsp 0x00000000004005c1 <+4>: sub rsp,0x10 0x00000000004005c5 <+8>: mov edi,0x8 0x00000000004005ca <+13>: call 0x4004c0 <malloc@plt> 0x00000000004005cf <+18>: mov QWORD PTR [rbp-0x8],rax 0x00000000004005d3 <+22>: mov rax,QWORD PTR [rbp-0x8] 0x00000000004005d7 <+26>: mov rsi,rax 0x00000000004005da <+29>: mov edi,0x400684 0x00000000004005df <+34>: mov eax,0x0 0x00000000004005e4 <+39>: call 0x400490 <printf@plt> 0x00000000004005e9 <+44>: mov rax,QWORD PTR [rbp-0x8] 0x00000000004005ed <+48>: mov rdi,rax 0x00000000004005f0 <+51>: call 0x400480 <free@plt> 0x00000000004005f5 <+56>: leave 0x00000000004005f6 <+57>: ret End of assembler dump. gdb-peda$ b *0x00000000004005cf Breakpoint 1 at 0x4005cf gdb-peda$ r Starting program: /home/lazenca0x0/Documents/def/allocated Breakpoint 1, 0x00000000004005cf in main () gdb-peda$ heap heapbase : 0x602000 gdb-peda$ x/10gx 0x602000 0x602000: 0x0000000000000000 0x0000000000000021 0x602010: 0x0000000000000000 0x0000000000000000 0x602020: 0x0000000000000000 0x0000000000020fe1 0x602030: 0x0000000000000000 0x0000000000000000 0x602040: 0x0000000000000000 0x0000000000000000 gdb-peda$
Free chunk
- Free chunk의 구조는 다음과 같습니다.
Free chunk Sample(64 bit)
| Chunk | Chunk size | A | M | P | |||||||||||
| fd | bk | ||||||||||||||
| Unused Space | Next chunk(Size of chunk) | ||||||||||||||
- Free chunk는 다음과 같은 정보를 포함합니다.
| prev_size |
|
|---|---|
| size |
|
| fd(Forward pointer) |
|
| bk(Backward pointer) |
|
Example - Free chunk
- 다음과 같은 코드를 이용해 Free chunk를 확인합니다.
freechunk.c
#include <stdio.h>
#include <stdlib.h>
void main(){
char *heap1 = malloc(128);
char *tmp2 = malloc(8);
char *heap2 = malloc(128);
char *tmp3 = malloc(8);
char *heap3 = malloc(128);
char *tmp1 = malloc(8);
printf("Free chunk : %p\n",heap2);
free(heap1);
free(heap2);
free(heap3);
getchar();
}
- 다음과 같은 방법으로 Free chunk의 구조를 확인할 수 있습니다.
- Chunk size는 다음과 같은 값을 더한 값이 저장되어 있습니다.
Free chunk의 header 정보를 저장하는 공간 - 16byte
해제된 Heap 공간의 크기 - 128 byte
"PREV_INUSE" flag 설정 - 1 byte
- fd 영역에 해제된 heap1 영역의 주소가 저장되어 있습니다.
- bk 영역에 해제된 heap2 영역의 주소가 저장되어 있습니다.
Check Free chunk
lazenca0x0@ubuntu:~/Documents/def$ gcc -o freechunk freechunk.c lazenca0x0@ubuntu:~/Documents/def$ gdb ./freechunk gdb-peda$ r Starting program: /home/lazenca0x0/Documents/def/unsorted Free chunk : 0x6020c0 ^C Program received signal SIGINT, Interrupt. gdb-peda$ x/4gx 0x6020c0 - 0x10 0x6020b0: 0x0000000000000000 0x0000000000000091 0x6020c0: 0x0000000000602000 0x0000000000602160 gdb-peda$
Top chunk
- Top chunk는 Arena의 가장 상위 영역에 있는 Chunk입니다.
- Top chunk는 bin에 포함되지 않습니다.
- Top chunk는 PREV_INUSE 플래그가 설정됩니다.
- Top chunk의 크기가 사용자가 요청한 크기보다 큰 경우 top chunk는 2개로 분리됩니다.
- User chunk(사용자가 요청한 크기)
- Remainder chunk(나머지 크기)
- Remainder chunk는 새로운 Top chunk가 됩니다.
- Top chunk의 크기가 사용자가 요청한 크기보다 작은 경우 syscall을 사용하여 Top chunk의 크기를 증가 시킵니다.
- sbrk(main arena)
- mmap(thread arena)
Fast chunk, Small chunk, Large chunk
- Allocated chunk는 Chunk size(+User data)의 크기에 따라 다음과 같이 구분됩니다.
Chunk의 크기에 따른 분류
| Chunk | size of Chunk (32bit) | size of Chunk (64bit) |
|---|---|---|
| Fast chunk | 16 ~ 64 byte | 32 ~ 128 byte |
| Small chunk | size of User data < 512 byte | |
| Large chunk | size of User data >= 512 byte | |
Bin
- Bin의 종류는 다음과 같습니다.
- Fast bin, Small bin, Large bin, Unsorted bin
- 각 Bins의 속성은 다음과 같습니다.
| Bins | Fast bin | Small bin | Large bin | Unsorted bin |
|---|---|---|---|---|
| Chunk type | Fast chunk | Small chunk | Large chunk | Small, Large chunk |
| the size of chunk | 16 ~ 80 byte | 512 byte 이하 | 512 byte이상 | 제한 없음 (Free chunk만 등록 가능) |
| Bin의 갯수 | 10 | 62 | 63 | 1 |
| Free chunk 관리 |
|
| - | |
malloc_state
Bin 정보는 "malloc_state" 구조체에서 관리됩니다.
FastbinsY : "Fast bin"을 관리합니다.
Bins : "Unsorted bin", "Small bin", "Large bin"을 관리 합니다.
총 126개의 bin을 관리 합니다.
Bins의 구성은 다음과 같습니다.
Index 1 : Unsorted bin
Index 2 ~ 63 : Small bin
Index 64 ~ 126 : Large bin
Fast bin
- Fast bin은 다음과 같습니다.
- 해당 bin은 LIFO방식을 사용합니다.
- 해당 bin은 10개의 bin을 사용합니다.
- 해당 bin은 해제된 Fast chunk를 보관합니다.
해당 bin은 속도 향상을 위해 single-linked list로 구성됩니다.
- Bin의 구성
- Fast bin이 처리하는 메모리의 최대 크기 "global_max_fast"에 의해 결정됩니다.
- 32bit: 최소 크기 16 byte 부터 24, 32, 40, 48, 56, 64 byte 까지 포함합니다.
- 64bit: 최소 크기 32 byte 부터 48, 64, 80, 96, 112, 128 byte 까지 포함합니다.
- Fast bin이 처리하는 메모리의 최대 크기 "global_max_fast"에 의해 결정됩니다.
- Free chunk
- 해당 bind의 경우 Free chunk가 서로 인접해 있어도 하나의 Free chunk로 병합되지 않습니다.
64bit - global_max_fast
gdb-peda$ p global_max_fast $2 = 0x80 gdb-peda$
Small bin
- Small bin은 다음과 같습니다.
- 해당 bin은 FIFO방식을 사용합니다.
- 해당 bin은 62개의 bin을 사용합니다.
- 해당 bin은 해제된 Small chunk를 보관합니다.
- 해당 bin은 doubly-linked list로 구성됩니다.
- Bin 구성
- 해당 bin은 512바이트 미만의 크기를 가지는 Chunk를 위한 Bin입니다.
- 최소 크기 16 byte 부터 24,32,48, ... 504byte 까지 총 62개의 bin으로 구성됩니다.
- Free chunk
- 해당 bin에는 2개의 Free chunk가 서로 인접해 있을 수 없습니다.
- 해당 bin에 2개의 Free chunk가 서로 인접해 있을 경우 하나의 Free chunk로 병합됩니다.
Large bin
- Large bin은 다음과 같습니다.
- 해당 bin은 63개의 bin을 사용합니다.
- 해당 bin은 해제된 Large chunk를 보관합니다.
- 해당 bin은 doubly-linked list로 구성됩니다.
- Bin의 구성
- 해당 Bin은 512 byte 이상의 크기를 가지는 Chunk를 위한 Bin입니다.
- Small Bin 처럼 동일한 크기의 chunk만을 포함하지 않습니다.
- 해당 index가 나타내는 크기 보다 작은 크기의 chunk들도 모두 포함됩니다.
- 예를 들어 4kb를 위한 bin 이 있다면 4096 byte의 chunk만을 포함하는 것이 아니라, 4088,4000,3968 등의 크기를 가지는 chunk들도 포함합니다.
- 단지 이들의 할당의 효율성을 높이기 위해 해당 bin내에서 크기 별로 정렬됩니다.
- 이 때 fd_nextsize와 bk_nextsize 필드가 이용됩니다.
- Free Chunk
- 해당 bin에는 2개의 Free chunk가 서로 인접해 있을 수 없습니다.
- 해당 bin에 2개의 Free chunk가 서로 인접해 있을 경우 하나의 Free chunk로 병합됩니다.
- 128KB 이상의 큰 메모리
- 해당 크기의 메모리 영역은 mmap() 시스템 콜을 이용해 별도의 메모리 영역을 할당 후 Chunk를 생성합니다.
- 해당 크기의 Chunk들은 Bin에 속하지 않습니다.
- 해당 Chunk들은 IS_MMAPPED 플래그가 설정됩니다.
- 해당 영역이 Free 될 경우 munmap()을 호출해 해당 메모리 영역을 해지 합니다.
Unsorted bin
- Unsorted bin은 다음과 같습니다.
- 해당 bin은 1개의 bin만 사용합니다.
- 해당 bin은 doubly-linked list로 구성됩니다.
- 해당 bin은 해제된 Small ,Large chunk를 보관합니다.
- 해당 bin을 이용해 적절한 bin을 찾는 시간이 적기 때문에 할당과 해제의 처리속도가 빠릅니다.
- 해당 bin은 Chunk 크기에 대한 제한이 없기 때문에 다양한 크기의 청크가 해당 Bin에 저장될 수 있습니다.
- free()된 chunk는 unsorted bin에 보관되며, 메모리 할당 시 동일한 크기의 영역을 다시 요청하는 경우 해당 영역을 재사용합니다.
- 해당 Bin은 FIFO 방식을 사용합니다.
- 검색된 Chunk는 바로 재할당 되거나 아니면 원래의 Bin으로 돌아가게 됩니다.
- 즉, 해제한 Chunk를 재사용하기 위해서 Chunk 해제 후 곧 바로 동일한 크기의 Chunk를 생성해야 합니다.
Bins - Example
Fast bin
- 다음 소스코드를 이용해 fastbin에 해제된 chunk가 등록되는 것을 확인할 수 있습니다.
fastbin.c
#include <stdio.h>
#include <stdlib.h>
void main(){
char *heap = malloc(16);
char *heap1 = malloc(32);
char *heap2 = malloc(48);
char *heap3 = malloc(64);
char *heap4 = malloc(80);
char *heap5 = malloc(96);
char *heap6 = malloc(112);
printf("Heap Addr : %p\n",heap);
printf("Heap Addr : %p\n",heap1);
printf("Heap Addr : %p\n",heap2);
printf("Heap Addr : %p\n",heap3);
printf("Heap Addr : %p\n",heap4);
printf("Heap Addr : %p\n",heap5);
printf("Heap Addr : %p\n",heap6);
free(heap);
free(heap1);
free(heap2);
free(heap3);
free(heap4);
free(heap5);
free(heap6);
getchar();
}
- 다음과 같은 방법으로 Fast bin을 확인할 수 있습니다.
- main_arena을 이용해 fastbinsY의 정보를 확인 할 수 있습니다.
- 해제된 모든 Heap 영역이 fastbinsY에 추가되었습니다.
- Unsorted bin 영역에 해제된 Heap영역이 추가되지 않았습니다.
Check fastbin(64bit)
lazenca0x0@ubuntu:~/Documents/def$ gcc -o fastbin fastbin.c
lazenca0x0@ubuntu:~/Documents/def$ gdb ./fastbin
gdb-peda$ r
Starting program: /home/lazenca0x0/Documents/def/fastbin
Heap Addr : 0x602010
Heap Addr : 0x602030
Heap Addr : 0x602060
Heap Addr : 0x6020a0
Heap Addr : 0x6020f0
Heap Addr : 0x602150
Heap Addr : 0x6021c0
^C
Program received signal SIGINT, Interrupt.
gdb-peda$ p main_arena
$1 = {
mutex = 0x0,
flags = 0x0,
fastbinsY = {0x602000, 0x602020, 0x602050, 0x602090, 0x6020e0, 0x602140, 0x6021b0, 0x0, 0x0, 0x0},
top = 0x602230,
last_remainder = 0x0,
bins = {0x7ffff7dd37b8 <main_arena+88>, 0x7ffff7dd37b8 <main_arena+88>,
...
Unsorted bin
- 다음과 같은 소스 코드를 이용해 Unsorted bin을 확인 할 수 있습니다.
unsorted.c
#include <stdio.h>
#include <stdlib.h>
void main(){
char *heap = malloc(8);
char *heap2 = malloc(128);
char *heap3 = malloc(8);
free(heap2);
getchar();
}
- 다음과 같은 방법으로 Unsort bin을 확인할 수 있습니다.
free()가 호출 후에 bins의 1번째 Index 영역(0x7ffff7dd37c8,0x7ffff7dd37d0)에 해제된 heap영역의 주소 값이 저장되었습니다.
Check unsorted bin
lazenca0x0@ubuntu:~/Documents/def$ gcc -o unsorted unsorted.c
lazenca0x0@ubuntu:~/Documents/def$ gdb ./unsorted
gdb-peda$ disassemble main
Dump of assembler code for function main:
0x00000000004005bd <+0>: push rbp
0x00000000004005be <+1>: mov rbp,rsp
0x00000000004005c1 <+4>: sub rsp,0x20
0x00000000004005c5 <+8>: mov edi,0x8
0x00000000004005ca <+13>: call 0x4004c0 <malloc@plt>
0x00000000004005cf <+18>: mov QWORD PTR [rbp-0x18],rax
0x00000000004005d3 <+22>: mov edi,0x80
0x00000000004005d8 <+27>: call 0x4004c0 <malloc@plt>
0x00000000004005dd <+32>: mov QWORD PTR [rbp-0x10],rax
0x00000000004005e1 <+36>: mov edi,0x8
0x00000000004005e6 <+41>: call 0x4004c0 <malloc@plt>
0x00000000004005eb <+46>: mov QWORD PTR [rbp-0x8],rax
0x00000000004005ef <+50>: mov rax,QWORD PTR [rbp-0x10]
0x00000000004005f3 <+54>: mov rdi,rax
0x00000000004005f6 <+57>: call 0x400480 <free@plt>
0x00000000004005fb <+62>: call 0x4004a0 <getchar@plt>
0x0000000000400600 <+67>: leave
0x0000000000400601 <+68>: ret
End of assembler dump.
gdb-peda$ b *0x00000000004005f6
Breakpoint 1 at 0x4005f6
gdb-peda$ r
Starting program: /home/lazenca0x0/Documents/def/unsorted
Breakpoint 1, 0x00000000004005f6 in main ()
gdb-peda$ p main_arena
$2 = {
mutex = 0x0,
flags = 0x1,
fastbinsY = {0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0},
top = 0x6020d0,
last_remainder = 0x0,
bins = {0x7ffff7dd37b8 <main_arena+88>, 0x7ffff7dd37b8 <main_arena+88>, 0x7ffff7dd37c8 <main_arena+104>, 0x7ffff7dd37c8
...
}
gdb-peda$ ni
0x00000000004005fb in main ()
gdb-peda$ p main_arena
$3 = {
mutex = 0x0,
flags = 0x1,
fastbinsY = {0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0},
top = 0x6020d0,
last_remainder = 0x0,
bins = {0x602020, 0x602020, 0x7ffff7dd37c8 <main_arena+104>, 0x7ffff7dd37c8 <main_arena+104>, 0x7ffff7dd37d8
...
}
Related site
- http://www.blackhat.com/presentations/bh-usa-07/Ferguson/Whitepaper/bh-usa-07-ferguson-WP.pdf
- http://core-analyzer.sourceforge.net/index_files/Page335.html
- https://sourceware.org/glibc/wiki/MallocInternals
- https://sploitfun.wordpress.com/2015/03/04/heap-overflow-using-malloc-maleficarum/
- https://sploitfun.wordpress.com/2015/02/10/understanding-glibc-malloc/
- http://paper.seebug.org/papers/Archive/refs/heap/glibc%E5%86%85%E5%AD%98%E7%AE%A1%E7%90%86ptmalloc%E6%BA%90%E4%BB%A3%E7%A0%81%E5%88%86%E6%9E%90.pdf
- http://files.cnblogs.com/files/hseagle/demo.pdf
- http://studyfoss.egloos.com/5206220
- https://heap-exploitation.dhavalkapil.com/diving_into_glibc_heap/
- http://gee.cs.oswego.edu/dl/html/malloc.html
- http://www.valinux.co.jp/technologylibrary/document/linux/malloc0001/
Excuse the ads! We need some help to keep our site up.