Excuse the ads! We need some help to keep our site up.
Chunk에는 사용 중인 덩어리, 해제된 덩어리, Top 덩어리, Last Remainder 덩어리가 있습니다.
Top chunk는 Arena의 가장 상단에 있는 덩어리입니다.
Allocator는 메모리를 할당할 때 Free chunks 중에서 사용가능한 chunk가 있는지 확인합니다.
만약 요청한 크기와 일치하는 chunk가 없고, 요청된 크기 보다 큰 chunk가 있다면 해당 덩어리를 분할합니다.
이때 분할되고 남은 덩어리가 "Last Remainder chunk"입니다.
size_t가 void*와 같은 크기가 아니라면 청크의 최소 크기는 4*sizeof(void*)입니다.
플랫폼의 ABI에 추가 정렬이 필요한 경우 최소 크기가 더 클 수 있습니다.
각 청크에는 크기와 인접한 청크의 위치에 대한 메타 데이터를 가지고 있습니다.
메타 데이터를 이용하여 해당 chunk가 사용중인지 또는 해제되었는지를 알수 있습니다.
그리고 이전 청크가 사용중인지 해제되었는지도 알 수 있습니다.
malloc()은 각 chunk를 관리하기 위해 malloc_chunk 구조체인 mchunkptr를 선언합니다.
malloc_chunk 구조체는 앞에서 설명한 메타데이터 입니다.
/* Forward declarations. */ struct malloc_chunk; typedef struct malloc_chunk* mchunkptr; |
struct malloc_chunk { INTERNAL_SIZE_T mchunk_prev_size; /* Size of previous chunk (if free). */ INTERNAL_SIZE_T mchunk_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; }; |
모든 청크의 크기는 MALLOC_ALIGNMENT(2 * sizeof(size_t))의 배수입니다.
따라서 청크의 mchunk_size에서 3 LSB(least significant bit)를 플래그로 사용될 수 있습니다.
mchunk_size 필드의 맨 끝 3bit는 플래그로 사용되며, 다음과 같이 정의됩니다
PREV_INUSE [P](0x1) 플래그는 인접한 이전 청크가 사용중일 때 사용됩니다.
IS_MMAPPED [M](0x2) 플래그는 해당 청크를 mmap()으로 부터 할당받았은 청크일 경우 사용됩니다.
NON_MAIN_ARENA [A](0x4) 플래그는 해당 청크를 비 주요 경기장(non-main arena)으로부터 할당받은 경우 사용됩니다.
/* --------------- Physical chunk operations --------------- */ /* size field is or'ed with PREV_INUSE when previous adjacent chunk in use */ #define PREV_INUSE 0x1 /* extract inuse bit of previous chunk */ #define prev_inuse(p) ((p)->size & PREV_INUSE) /* size field is or'ed with IS_MMAPPED if the chunk was obtained with mmap() */ #define IS_MMAPPED 0x2 /* check for mmap()'ed chunk */ #define chunk_is_mmapped(p) ((p)->size & IS_MMAPPED) /* size field is or'ed with NON_MAIN_ARENA if the chunk was obtained from a non-main arena. This is only set immediately before handing the chunk to the user, if necessary. */ #define NON_MAIN_ARENA 0x4 /* check for chunk from non-main arena */ #define chunk_non_main_arena(p) ((p)->size & NON_MAIN_ARENA) |
다음 코드를 이용하여 어플리케이션의 메모리에서 in-use chunk를 확인하겠습니다.
malloc()에 크기가 128 byte와 80byte인 메모리 할당을 요청합니다.
malloc()으로 부터 반환된 포인터를 heap1, heap2에 저장합니다.
#include <stdio.h> #include <stdlib.h> #include <unistd.h> void main(){ char *heap1 = malloc(136); char *heap2 = malloc(80); free(heap1); char *heap3 = malloc(136); read(STDIN_FILENO,heap3,136); } |
다음과 같이 breakpoints를 설정하여 메모리 변경을 확인합니다.
lazenca0x0@ubuntu:~/Book/Heap/1.Malloc$ gdb -q ./in-use Reading symbols from ./in-use...(no debugging symbols found)...done. (gdb) set disassembly-flavor intel (gdb) disassemble main Dump of assembler code for function main: 0x00000000004005b6 <+0>: push rbp 0x00000000004005b7 <+1>: mov rbp,rsp 0x00000000004005ba <+4>: sub rsp,0x20 0x00000000004005be <+8>: mov edi,0x88 0x00000000004005c3 <+13>: call 0x4004a0 <malloc@plt> 0x00000000004005c8 <+18>: mov QWORD PTR [rbp-0x18],rax 0x00000000004005cc <+22>: mov edi,0x50 0x00000000004005d1 <+27>: call 0x4004a0 <malloc@plt> 0x00000000004005d6 <+32>: mov QWORD PTR [rbp-0x10],rax 0x00000000004005da <+36>: mov rax,QWORD PTR [rbp-0x18] 0x00000000004005de <+40>: mov rdi,rax 0x00000000004005e1 <+43>: call 0x400470 <free@plt> 0x00000000004005e6 <+48>: mov edi,0x88 0x00000000004005eb <+53>: call 0x4004a0 <malloc@plt> 0x00000000004005f0 <+58>: mov QWORD PTR [rbp-0x8],rax 0x00000000004005f4 <+62>: mov rax,QWORD PTR [rbp-0x8] 0x00000000004005f8 <+66>: mov edx,0x88 0x00000000004005fd <+71>: mov rsi,rax 0x0000000000400600 <+74>: mov edi,0x0 0x0000000000400605 <+79>: call 0x400480 <read@plt> 0x000000000040060a <+84>: nop 0x000000000040060b <+85>: leave 0x000000000040060c <+86>: ret End of assembler dump. (gdb) b *0x00000000004005c3 Breakpoint 1 at 0x4005c3 (gdb) b *0x00000000004005d6 Breakpoint 2 at 0x4005d6 (gdb) b *0x00000000004005e6 Breakpoint 3 at 0x4005e6 (gdb) b *0x00000000004005f0 Breakpoint 4 at 0x4005f0 (gdb) b *0x000000000040060a Breakpoint 5 at 0x40060a (gdb) |
(gdb) r Starting program: /home/lazenca0x0/Book/Heap/1.Malloc/in-use Breakpoint 1, 0x00000000004005c3 in main () (gdb) x/i $rip => 0x4005c3 <main+13>: call 0x4004a0 <malloc@plt> (gdb) info proc map process 7207 Mapped address spaces: Start Addr End Addr Size Offset objfile 0x400000 0x401000 0x1000 0x0 /home/lazenca0x0/Book/Heap/1.Malloc/in-use 0x600000 0x601000 0x1000 0x0 /home/lazenca0x0/Book/Heap/1.Malloc/in-use 0x601000 0x602000 0x1000 0x1000 /home/lazenca0x0/Book/Heap/1.Malloc/in-use 0x7ffff7a0d000 0x7ffff7bcd000 0x1c0000 0x0 /lib/x86_64-linux-gnu/libc-2.23.so 0x7ffff7bcd000 0x7ffff7dcd000 0x200000 0x1c0000 /lib/x86_64-linux-gnu/libc-2.23.so 0x7ffff7dcd000 0x7ffff7dd1000 0x4000 0x1c0000 /lib/x86_64-linux-gnu/libc-2.23.so 0x7ffff7dd1000 0x7ffff7dd3000 0x2000 0x1c4000 /lib/x86_64-linux-gnu/libc-2.23.so 0x7ffff7dd3000 0x7ffff7dd7000 0x4000 0x0 0x7ffff7dd7000 0x7ffff7dfd000 0x26000 0x0 /lib/x86_64-linux-gnu/ld-2.23.so 0x7ffff7fde000 0x7ffff7fe1000 0x3000 0x0 0x7ffff7ff7000 0x7ffff7ffa000 0x3000 0x0 [vvar] 0x7ffff7ffa000 0x7ffff7ffc000 0x2000 0x0 [vdso] 0x7ffff7ffc000 0x7ffff7ffd000 0x1000 0x25000 /lib/x86_64-linux-gnu/ld-2.23.so 0x7ffff7ffd000 0x7ffff7ffe000 0x1000 0x26000 /lib/x86_64-linux-gnu/ld-2.23.so 0x7ffff7ffe000 0x7ffff7fff000 0x1000 0x0 0x7ffffffde000 0x7ffffffff000 0x21000 0x0 [stack] 0xffffffffff600000 0xffffffffff601000 0x1000 0x0 [vsyscall] (gdb) |
(gdb) ni 0x00000000004005c8 in main () (gdb) info proc map process 7207 Mapped address spaces: Start Addr End Addr Size Offset objfile 0x400000 0x401000 0x1000 0x0 /home/lazenca0x0/Book/Heap/1.Malloc/in-use 0x600000 0x601000 0x1000 0x0 /home/lazenca0x0/Book/Heap/1.Malloc/in-use 0x601000 0x602000 0x1000 0x1000 /home/lazenca0x0/Book/Heap/1.Malloc/in-use 0x602000 0x623000 0x21000 0x0 [heap] 0x7ffff7a0d000 0x7ffff7bcd000 0x1c0000 0x0 /lib/x86_64-linux-gnu/libc-2.23.so ... 0x7ffffffde000 0x7ffffffff000 0x21000 0x0 [stack] 0xffffffffff600000 0xffffffffff601000 0x1000 0x0 [vsyscall] (gdb) |
할당자로 부터 할당받은 첫번째 Heap의 포인터는 0x602010입니다.
할당이 가능한 메모리의 크기가 bk(0x602098)에 저장됩니다.
(gdb) i r rax rax 0x602010 6299664 (gdb) x/32gx 0x602010 - 0x10 0x602000: 0x0000000000000000 0x0000000000000091 0x602010: 0x0000000000000000 0x0000000000000000 0x602020: 0x0000000000000000 0x0000000000000000 0x602030: 0x0000000000000000 0x0000000000000000 0x602040: 0x0000000000000000 0x0000000000000000 0x602050: 0x0000000000000000 0x0000000000000000 0x602060: 0x0000000000000000 0x0000000000000000 0x602070: 0x0000000000000000 0x0000000000000000 0x602080: 0x0000000000000000 0x0000000000000000 0x602090: 0x0000000000000000 0x0000000000020f71 0x6020a0: 0x0000000000000000 0x0000000000000000 0x6020b0: 0x0000000000000000 0x0000000000000000 0x6020c0: 0x0000000000000000 0x0000000000000000 0x6020d0: 0x0000000000000000 0x0000000000000000 0x6020e0: 0x0000000000000000 0x0000000000000000 0x6020f0: 0x0000000000000000 0x0000000000000000 (gdb) |
할당자로부터 할당받은 두번째 Heap의 포인터는 0x6020a0입니다.
(gdb) c Continuing. Breakpoint 2, 0x00000000004005d6 in main () (gdb) i r rax rax 0x6020a0 6299808 (gdb) x/32gx 0x602010 - 0x10 0x602000: 0x0000000000000000 0x0000000000000091 0x602010: 0x0000000000000000 0x0000000000000000 0x602020: 0x0000000000000000 0x0000000000000000 0x602030: 0x0000000000000000 0x0000000000000000 0x602040: 0x0000000000000000 0x0000000000000000 0x602050: 0x0000000000000000 0x0000000000000000 0x602060: 0x0000000000000000 0x0000000000000000 0x602070: 0x0000000000000000 0x0000000000000000 0x602080: 0x0000000000000000 0x0000000000000000 0x602090: 0x0000000000000000 0x0000000000000061 0x6020a0: 0x0000000000000000 0x0000000000000000 0x6020b0: 0x0000000000000000 0x0000000000000000 0x6020c0: 0x0000000000000000 0x0000000000000000 0x6020d0: 0x0000000000000000 0x0000000000000000 0x6020e0: 0x0000000000000000 0x0000000000000000 0x6020f0: 0x0000000000000000 0x0000000000020f11 (gdb) |
프로세스는 free()함수를 이용하여 첫번째 덩어리(0x602010)를 해제합니다.
(gdb) c Continuing. Breakpoint 3, 0x00000000004005e6 in main () (gdb) x/32gx 0x602010 - 0x10 0x602000: 0x0000000000000000 0x0000000000000091 0x602010: 0x00007ffff7dd1b78 0x00007ffff7dd1b78 0x602020: 0x0000000000000000 0x0000000000000000 0x602030: 0x0000000000000000 0x0000000000000000 0x602040: 0x0000000000000000 0x0000000000000000 0x602050: 0x0000000000000000 0x0000000000000000 0x602060: 0x0000000000000000 0x0000000000000000 0x602070: 0x0000000000000000 0x0000000000000000 0x602080: 0x0000000000000000 0x0000000000000000 0x602090: 0x0000000000000090 0x0000000000000060 0x6020a0: 0x0000000000000000 0x0000000000000000 0x6020b0: 0x0000000000000000 0x0000000000000000 0x6020c0: 0x0000000000000000 0x0000000000000000 0x6020d0: 0x0000000000000000 0x0000000000000000 0x6020e0: 0x0000000000000000 0x0000000000000000 0x6020f0: 0x0000000000000000 0x0000000000020f11 (gdb) |
할당자로부터 할당받은 세번째 Heap의 포인터는 0x602010입니다.
(gdb) c Continuing. Breakpoint 4, 0x00000000004005f0 in main () (gdb) i r rax rax 0x602010 6299664 (gdb) x/32gx 0x602010 - 0x10 0x602000: 0x0000000000000000 0x0000000000000091 0x602010: 0x00007ffff7dd1b78 0x00007ffff7dd1b78 0x602020: 0x0000000000000000 0x0000000000000000 0x602030: 0x0000000000000000 0x0000000000000000 0x602040: 0x0000000000000000 0x0000000000000000 0x602050: 0x0000000000000000 0x0000000000000000 0x602060: 0x0000000000000000 0x0000000000000000 0x602070: 0x0000000000000000 0x0000000000000000 0x602080: 0x0000000000000000 0x0000000000000000 0x602090: 0x0000000000000090 0x0000000000000061 0x6020a0: 0x0000000000000000 0x0000000000000000 0x6020b0: 0x0000000000000000 0x0000000000000000 0x6020c0: 0x0000000000000000 0x0000000000000000 0x6020d0: 0x0000000000000000 0x0000000000000000 0x6020e0: 0x0000000000000000 0x0000000000000000 0x6020f0: 0x0000000000000000 0x0000000000020f11 (gdb) |
(gdb) c Continuing. AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABBBBBBB Breakpoint 5, 0x000000000040060a in main () (gdb) x/32gx 0x602010 - 0x10 0x602000: 0x0000000000000000 0x0000000000000091 0x602010: 0x4141414141414141 0x4141414141414141 0x602020: 0x4141414141414141 0x4141414141414141 0x602030: 0x4141414141414141 0x4141414141414141 0x602040: 0x4141414141414141 0x4141414141414141 0x602050: 0x4141414141414141 0x4141414141414141 0x602060: 0x4141414141414141 0x4141414141414141 0x602070: 0x4141414141414141 0x4141414141414141 0x602080: 0x4141414141414141 0x4141414141414141 0x602090: 0x0a42424242424242 0x0000000000000061 0x6020a0: 0x0000000000000000 0x0000000000000000 0x6020b0: 0x0000000000000000 0x0000000000000000 0x6020c0: 0x0000000000000000 0x0000000000000000 0x6020d0: 0x0000000000000000 0x0000000000000000 0x6020e0: 0x0000000000000000 0x0000000000000000 0x6020f0: 0x0000000000000000 0x0000000000020f11 (gdb) |
#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); free(heap1); free(heap2); free(heap3); } |
lazenca0x0@ubuntu:~/Book/Heap/1.Malloc$ gcc -o free free.c lazenca0x0@ubuntu:~/Book/Heap/1.Malloc$ gdb -q ./free Reading symbols from ./free...(no debugging symbols found)...done. (gdb) disassemble main Dump of assembler code for function main: 0x0000000000400566 <+0>: push rbp 0x0000000000400567 <+1>: mov rbp,rsp 0x000000000040056a <+4>: sub rsp,0x30 0x000000000040056e <+8>: mov edi,0x80 0x0000000000400573 <+13>: call 0x400450 <malloc@plt> 0x0000000000400578 <+18>: mov QWORD PTR [rbp-0x30],rax 0x000000000040057c <+22>: mov edi,0x8 0x0000000000400581 <+27>: call 0x400450 <malloc@plt> 0x0000000000400586 <+32>: mov QWORD PTR [rbp-0x28],rax 0x000000000040058a <+36>: mov edi,0x80 0x000000000040058f <+41>: call 0x400450 <malloc@plt> 0x0000000000400594 <+46>: mov QWORD PTR [rbp-0x20],rax 0x0000000000400598 <+50>: mov edi,0x8 0x000000000040059d <+55>: call 0x400450 <malloc@plt> 0x00000000004005a2 <+60>: mov QWORD PTR [rbp-0x18],rax 0x00000000004005a6 <+64>: mov edi,0x80 0x00000000004005ab <+69>: call 0x400450 <malloc@plt> 0x00000000004005b0 <+74>: mov QWORD PTR [rbp-0x10],rax 0x00000000004005b4 <+78>: mov edi,0x8 0x00000000004005b9 <+83>: call 0x400450 <malloc@plt> 0x00000000004005be <+88>: mov QWORD PTR [rbp-0x8],rax 0x00000000004005c2 <+92>: mov rax,QWORD PTR [rbp-0x30] 0x00000000004005c6 <+96>: mov rdi,rax 0x00000000004005c9 <+99>: call 0x400430 <free@plt> 0x00000000004005ce <+104>: mov rax,QWORD PTR [rbp-0x20] 0x00000000004005d2 <+108>: mov rdi,rax 0x00000000004005d5 <+111>: call 0x400430 <free@plt> 0x00000000004005da <+116>: mov rax,QWORD PTR [rbp-0x10] 0x00000000004005de <+120>: mov rdi,rax 0x00000000004005e1 <+123>: call 0x400430 <free@plt> 0x00000000004005e6 <+128>: nop 0x00000000004005e7 <+129>: leave 0x00000000004005e8 <+130>: ret End of assembler dump. (gdb) b *0x00000000004005be Breakpoint 1 at 0x4005be (gdb) b *0x00000000004005ce Breakpoint 2 at 0x4005ce (gdb) b *0x00000000004005da Breakpoint 3 at 0x4005da (gdb) b *0x00000000004005e6 Breakpoint 4 at 0x4005e6 (gdb) |
할당자가 할당한 메모리는 다음과 같습니다.
(gdb) r Starting program: /home/lazenca0x0/Book/Heap/1.Malloc/free Breakpoint 1, 0x00000000004005be in main () (gdb) x/70gx 0x602000 0x602000: 0x0000000000000000 0x0000000000000091 0x602010: 0x0000000000000000 0x0000000000000000 0x602020: 0x0000000000000000 0x0000000000000000 0x602030: 0x0000000000000000 0x0000000000000000 0x602040: 0x0000000000000000 0x0000000000000000 0x602050: 0x0000000000000000 0x0000000000000000 0x602060: 0x0000000000000000 0x0000000000000000 0x602070: 0x0000000000000000 0x0000000000000000 0x602080: 0x0000000000000000 0x0000000000000000 0x602090: 0x0000000000000000 0x0000000000000021 0x6020a0: 0x0000000000000000 0x0000000000000000 0x6020b0: 0x0000000000000000 0x0000000000000091 0x6020c0: 0x0000000000000000 0x0000000000000000 0x6020d0: 0x0000000000000000 0x0000000000000000 0x6020e0: 0x0000000000000000 0x0000000000000000 0x6020f0: 0x0000000000000000 0x0000000000000000 0x602100: 0x0000000000000000 0x0000000000000000 0x602110: 0x0000000000000000 0x0000000000000000 0x602120: 0x0000000000000000 0x0000000000000000 0x602130: 0x0000000000000000 0x0000000000000000 0x602140: 0x0000000000000000 0x0000000000000021 0x602150: 0x0000000000000000 0x0000000000000000 0x602160: 0x0000000000000000 0x0000000000000091 0x602170: 0x0000000000000000 0x0000000000000000 0x602180: 0x0000000000000000 0x0000000000000000 0x602190: 0x0000000000000000 0x0000000000000000 0x6021a0: 0x0000000000000000 0x0000000000000000 0x6021b0: 0x0000000000000000 0x0000000000000000 0x6021c0: 0x0000000000000000 0x0000000000000000 0x6021d0: 0x0000000000000000 0x0000000000000000 0x6021e0: 0x0000000000000000 0x0000000000000000 0x6021f0: 0x0000000000000000 0x0000000000000021 0x602200: 0x0000000000000000 0x0000000000000000 0x602210: 0x0000000000000000 0x0000000000020df1 0x602220: 0x0000000000000000 0x0000000000000000 (gdb) |
heap1(0x602010)이 해제되면 해당 chunk에 bk,fd 값이 저장됩니다.
(gdb) c Continuing. Breakpoint 2, 0x00000000004005ce in main () (gdb) x/70gx 0x602000 0x602000: 0x0000000000000000 0x0000000000000091 0x602010: 0x00007ffff7dd1b78 0x00007ffff7dd1b78 0x602020: 0x0000000000000000 0x0000000000000000 ... 0x602080: 0x0000000000000000 0x0000000000000000 0x602090: 0x0000000000000090 0x0000000000000020 0x6020a0: 0x0000000000000000 0x0000000000000000 0x6020b0: 0x0000000000000000 0x0000000000000091 0x6020c0: 0x0000000000000000 0x0000000000000000 0x6020d0: 0x0000000000000000 0x0000000000000000 ... 0x602130: 0x0000000000000000 0x0000000000000000 0x602140: 0x0000000000000000 0x0000000000000021 0x602150: 0x0000000000000000 0x0000000000000000 0x602160: 0x0000000000000000 0x0000000000000091 0x602170: 0x0000000000000000 0x0000000000000000 0x602180: 0x0000000000000000 0x0000000000000000 ... 0x6021e0: 0x0000000000000000 0x0000000000000000 0x6021f0: 0x0000000000000000 0x0000000000000021 0x602200: 0x0000000000000000 0x0000000000000000 0x602210: 0x0000000000000000 0x0000000000020df1 0x602220: 0x0000000000000000 0x0000000000000000 (gdb) |
heap2(0x6020c0)가 해제되면 해당 chunk에 fd, bk값이 저장됩니다.
그리고 heap1의 bk(0x602018)에 heap2의 mchunkptr(0x6020b0)이 저장됩니다.
(gdb) c Continuing. Breakpoint 3, 0x00000000004005da in main () (gdb) x/70gx 0x602000 0x602000: 0x0000000000000000 0x0000000000000091 0x602010: 0x00007ffff7dd1b78 0x00000000006020b0 0x602020: 0x0000000000000000 0x0000000000000000 ... 0x602080: 0x0000000000000000 0x0000000000000000 0x602090: 0x0000000000000090 0x0000000000000020 0x6020a0: 0x0000000000000000 0x0000000000000000 0x6020b0: 0x0000000000000000 0x0000000000000091 0x6020c0: 0x0000000000602000 0x00007ffff7dd1b78 0x6020d0: 0x0000000000000000 0x0000000000000000 ... 0x602130: 0x0000000000000000 0x0000000000000000 0x602140: 0x0000000000000090 0x0000000000000020 0x602150: 0x0000000000000000 0x0000000000000000 0x602160: 0x0000000000000000 0x0000000000000091 0x602170: 0x0000000000000000 0x0000000000000000 0x602180: 0x0000000000000000 0x0000000000000000 ... 0x6021e0: 0x0000000000000000 0x0000000000000000 0x6021f0: 0x0000000000000000 0x0000000000000021 0x602200: 0x0000000000000000 0x0000000000000000 0x602210: 0x0000000000000000 0x0000000000020df1 0x602220: 0x0000000000000000 0x0000000000000000 (gdb) |
heap3(0x602170)가 해제되면 fd(0x602170)에 해당 chunk 앞에 있는 Free chunk의 mchunkptr(0x6020b0)이 저장합니다.
그리고 heap2의 bk(0x6020c8)에 heap3의 mchunkptr(0x602160)이 저장됩니다.
(gdb) c Continuing. Breakpoint 4, 0x00000000004005e6 in main () (gdb) x/70gx 0x602000 0x602000: 0x0000000000000000 0x0000000000000091 0x602010: 0x00007ffff7dd1b78 0x00000000006020b0 0x602020: 0x0000000000000000 0x0000000000000000 ... 0x602080: 0x0000000000000000 0x0000000000000000 0x602090: 0x0000000000000090 0x0000000000000020 0x6020a0: 0x0000000000000000 0x0000000000000000 0x6020b0: 0x0000000000000000 0x0000000000000091 0x6020c0: 0x0000000000602000 0x0000000000602160 0x6020d0: 0x0000000000000000 0x0000000000000000 ... 0x602130: 0x0000000000000000 0x0000000000000000 0x602140: 0x0000000000000090 0x0000000000000020 0x602150: 0x0000000000000000 0x0000000000000000 0x602160: 0x0000000000000000 0x0000000000000091 0x602170: 0x00000000006020b0 0x00007ffff7dd1b78 0x602180: 0x0000000000000000 0x0000000000000000 ... 0x6021e0: 0x0000000000000000 0x0000000000000000 0x6021f0: 0x0000000000000090 0x0000000000000020 0x602200: 0x0000000000000000 0x0000000000000000 0x602210: 0x0000000000000000 0x0000000000020df1 0x602220: 0x0000000000000000 0x0000000000000000 (gdb) |
Free chunk는 크기와 히스토리에 따라 다양한 목록에 저장됩니다.
이러한 목록을 "bins"라고 합니다.
할당자는 할당 요청을 충족시키기 위해 적합한 청크를 bins에서 신속하게 찾아서 재할당합니다.
bins의 종류에는 Fast bin, Small bin, Large bin, Unsorted bin이 있습니다.
매개변수를 최대로 설정하면 32비트 아키텍처에서는 최대 80byte(80*4/4), 64bit에서는 최대 160byte(80*8/4)의 상한을 설정 할 수 있습니다.
fast bin을 비활성화하려면 0으로 설정하면 됩니다.
Symbol param # default allowed param values M_MXFAST 1 64 0-80 (0 disables fastbins) M_TRIM_THRESHOLD -1 128*1024 any (-1U disables trimming) M_TOP_PAD -2 0 any M_MMAP_THRESHOLD -3 128*1024 any (or 0 if no MMAP support) M_MMAP_MAX -4 65536 any (0 disables use of mmap) */ |
/* M_MXFAST is a standard SVID/XPG tuning option, usually listed in malloc.h */ #ifndef M_MXFAST #define M_MXFAST 1 #endif #ifndef DEFAULT_MXFAST #define DEFAULT_MXFAST (64 * SIZE_SZ / 4) #endif |
Fastbin은 LIFO(last in, first out)를 사용합니다.
마지막으로 해제 된 chunk가 먼저 재 할당됩니다.
해당 bin은 최대 10개의 bin 관리 할 수 있으며, 패스트빈의 상한 값보다 크기가 작은 chunk들을 관리합니다.
해당 bin은 single-linked list로 구성됩니다.
해당 bin에 포함되는 chunk들은 서로 인접해 있어도 병합하지 않습니다.
Small bin이 포함하는 chunk는 크기가 MIN_LARGE_SIZE 보다 작은 chunk들입니다.
32bit 시스템은 MALLOC_ALIGNMENT는 8이고, SIZE_SZ는 4입니다.
MIN_LARGE_SIZE는 512((64 - 0) * 8)입니다.
64bit 시스템은 MALLOC_ALIGNMENT는 16이고,SIZE_SZ는 8입니다.
MIN_LARGE_SIZE는 1024((64 * 0) * 16)입니다.
즉, 32bit 시스템에서 Small bin의 범위는 16~504byte(64*8-8)이며 64bit에서는 32~1008byte입니다.
Small bin은 FIFO(First In, First Out)을 사용합니다.
먼저 해제 된 청크가 먼저 재 할당됩니다.
Small bin에 해당되는 chunk들은 서로 인접하게 배치될수 없습니다.
해당 chunk가 서로 인접해 있을 경우 하나의 chunk로 병합됩니다.
#define NBINS 128 #define NSMALLBINS 64 #define SMALLBIN_WIDTH MALLOC_ALIGNMENT #define SMALLBIN_CORRECTION (MALLOC_ALIGNMENT > 2 * SIZE_SZ) #define MIN_LARGE_SIZE ((NSMALLBINS - SMALLBIN_CORRECTION) * SMALLBIN_WIDTH) #define in_smallbin_range(sz) \ ((unsigned long) (sz) < (unsigned long) MIN_LARGE_SIZE) |
bin의 인덱스는 smallbin_index() 함수를 이용하여 확인 할 수 있습니다.
예를 들어 64bit에서 144byte의 free chunk의 인덱스는 9(504 >> 3 + 0)입니다.
#define smallbin_index(sz) \ ((SMALLBIN_WIDTH == 16 ? (((unsigned) (sz)) >> 4) : (((unsigned) (sz)) >> 3))\ + SMALLBIN_CORRECTION) |
Large bin이 포함하는 chunk의 크기가 MIN_LARGE_SIZE와 같거나 큰 chunk들입니다.
그러나 Large bin은 Small Bin과 다르게 하나의 bin에 다양한 크기의 chunk들을 보관합니다.
/* Indexing Bins for sizes < 512 bytes contain chunks of all the same size, spaced 8 bytes apart. Larger bins are approximately logarithmically spaced: 64 bins of size 8 32 bins of size 64 16 bins of size 512 8 bins of size 4096 4 bins of size 32768 2 bins of size 262144 1 bin of size what's left There is actually a little bit of slop in the numbers in bin_index for the sake of speed. This makes no difference elsewhere. The bins top out around 1MB because we expect to service large requests via mmap. Bin 0 does not exist. Bin 1 is the unordered list; if that would be a valid chunk size the small bins are bumped up one. */ |
Large bin에 해당하는 chunk들의 인덱스는 largebin_index_32(), largebin_index_64() 함수를 이용하여 확인할 수 있습니다.
#define largebin_index_32(sz) \ (((((unsigned long) (sz)) >> 6) <= 38) ? 56 + (((unsigned long) (sz)) >> 6) :\ ((((unsigned long) (sz)) >> 9) <= 20) ? 91 + (((unsigned long) (sz)) >> 9) :\ ((((unsigned long) (sz)) >> 12) <= 10) ? 110 + (((unsigned long) (sz)) >> 12) :\ ((((unsigned long) (sz)) >> 15) <= 4) ? 119 + (((unsigned long) (sz)) >> 15) :\ ((((unsigned long) (sz)) >> 18) <= 2) ? 124 + (((unsigned long) (sz)) >> 18) :\ 126) #define largebin_index_32_big(sz) \ (((((unsigned long) (sz)) >> 6) <= 45) ? 49 + (((unsigned long) (sz)) >> 6) :\ ((((unsigned long) (sz)) >> 9) <= 20) ? 91 + (((unsigned long) (sz)) >> 9) :\ ((((unsigned long) (sz)) >> 12) <= 10) ? 110 + (((unsigned long) (sz)) >> 12) :\ ((((unsigned long) (sz)) >> 15) <= 4) ? 119 + (((unsigned long) (sz)) >> 15) :\ ((((unsigned long) (sz)) >> 18) <= 2) ? 124 + (((unsigned long) (sz)) >> 18) :\ 126) // XXX It remains to be seen whether it is good to keep the widths of // XXX the buckets the same or whether it should be scaled by a factor // XXX of two as well. #define largebin_index_64(sz) \ (((((unsigned long) (sz)) >> 6) <= 48) ? 48 + (((unsigned long) (sz)) >> 6) :\ ((((unsigned long) (sz)) >> 9) <= 20) ? 91 + (((unsigned long) (sz)) >> 9) :\ ((((unsigned long) (sz)) >> 12) <= 10) ? 110 + (((unsigned long) (sz)) >> 12) :\ ((((unsigned long) (sz)) >> 15) <= 4) ? 119 + (((unsigned long) (sz)) >> 15) :\ ((((unsigned long) (sz)) >> 18) <= 2) ? 124 + (((unsigned long) (sz)) >> 18) :\ 126) #define largebin_index(sz) \ (SIZE_SZ == 8 ? largebin_index_64 (sz) \ : MALLOC_ALIGNMENT == 16 ? largebin_index_32_big (sz) \ : largebin_index_32 (sz)) #define bin_index(sz) \ ((in_smallbin_range (sz)) ? smallbin_index (sz) : largebin_index (sz)) |
할당자는 크기가 128KB보다 큰 메모리를 할당하기 위해 mmap()에 새로운 메모리를 매핑을 요청한 후 해당 메모리에서 Chunk를 할당합니다.
/* There are several instances of this struct ("arenas") in this malloc. If you are adapting this malloc in a way that does NOT use a static or mmapped malloc_state, you MUST explicitly zero-fill it before using. This malloc relies on the property that malloc_state is initialized to all zeroes (as is true of C statics). */ static struct malloc_state main_arena = { .mutex = _LIBC_LOCK_INITIALIZER, .next = &main_arena, .attached_threads = 1 }; |
mutex는 해당 arena에 대한 액세스를 제어하는 데 사용됩니다.
패스트 빈에 대한 액세스와 같은 일부 작업은 경기장을 잠글 필요가 없습니다.
이 외에 다른 모든 작업을 하려면 스레드가 Arena를 잠글 필요가 있습니다.
struct malloc_state { /* Serialize access. */ __libc_lock_define (, 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; }; |
main_arena의 flags는 2개의 bit로 정보들의 유무를 나타냅니다.
#define FASTCHUNKS_BIT (1U) #define have_fastchunks(M) (((M)->flags & FASTCHUNKS_BIT) == 0) #define clear_fastchunks(M) catomic_or (&(M)->flags, FASTCHUNKS_BIT) #define set_fastchunks(M) catomic_and (&(M)->flags, ~FASTCHUNKS_BIT) /* NONCONTIGUOUS_BIT indicates that MORECORE does not return contiguous regions. Otherwise, contiguity is exploited in merging together, when possible, results from consecutive MORECORE calls. The initial value comes from MORECORE_CONTIGUOUS, but is changed dynamically if mmap is ever used as an sbrk substitute. */ #define NONCONTIGUOUS_BIT (2U) #define contiguous(M) (((M)->flags & NONCONTIGUOUS_BIT) == 0) #define noncontiguous(M) (((M)->flags & NONCONTIGUOUS_BIT) != 0) #define set_noncontiguous(M) ((M)->flags |= NONCONTIGUOUS_BIT) #define set_contiguous(M) ((M)->flags &= ~NONCONTIGUOUS_BIT) |
fastbins에 fastbin에 해당하는 free chunk가 배치됩니다.
fastbin에 해당하는 chunk의 인덱스는 fastbin_index()함수를 이용하여 확인할 수 있습니다.
해당 함수는 우측 시프트를 이용하여 chunk의 크기(sz)를 8(32bit) 또는 16(64bit)으로 나눈 값에 2를 뺍니다.
예를 들어 64bit 아키텍처에서 크기가 32byte인 chunk의 인덱스는 0((32 >> 4) - 2)입니다.
/* offset 2 to use otherwise unindexable first 2 bins */ #define fastbin_index(sz) \ ((((unsigned int) (sz)) >> (SIZE_SZ == 8 ? 4 : 3)) - 2) |
할당자는 요청받은 chunk의 크기가 DEFAULT_MMAP_THRESHOLD(131072)보다 큰경우 mmap()을 호출하여 새로운 Heap 영역을 매핑합니다.
if (av == NULL || ((unsigned long) (nb) >= (unsigned long) (mp_.mmap_threshold) && (mp_.n_mmaps < mp_.n_mmaps_max))) { char *mm; /* return value from mmap call*/ try_mmap: /* Round up size to nearest page. For mmapped chunks, the overhead is one SIZE_SZ unit larger than for normal chunks, because there is no following chunk whose prev_size field could be used. See the front_misalign handling below, for glibc there is no need for further alignments unless we have have high alignment. */ if (MALLOC_ALIGNMENT == 2 * SIZE_SZ) size = ALIGN_UP (nb + SIZE_SZ, pagesize); else size = ALIGN_UP (nb + SIZE_SZ + MALLOC_ALIGN_MASK, pagesize); tried_mmap = true; /* Don't try if size wraps around 0 */ if ((unsigned long) (size) > (unsigned long) (nb)) { mm = (char *) (MMAP (0, size, PROT_READ | PROT_WRITE, 0)); |
할당자는 메모리를 할당하기에 arena의 공간이 부족할 경우 sbrk()를 호출하여 메모리의 공간을 증가시킵니다.
/* 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); } |
할당자는 요청한 크기와 일치하는 free chunk가 없으면, 요청한 크기보다 큰 free chunk를 요청 크기로 분할하는 경우가 있습니다.
"bins"에 Unsorted bin, Small bin, Large bin가 포함하는 free chunk가 배치됩니다.
이 변수는 배열 변수이며 총(128 * 2 - 2)254개의 chunk 포인터를 배치할 수 있습니다.
free chunk를 bins에 배치할 때 chunk의 fd, bk 정보를 저장하기 때문 배열의 크기가 128이 아닌 254입니다.
bins[0], bins[1]은 Unsorted bin들이 배치됩니다.
binmap[0] : 0 ~ 31, binmap[1] : 32 ~ 64, binmap[2] : 65 ~ 96, binmap[3] : 97 ~128
bins[]에 free chunk가 배치되면, binmap[]에는 그 bin이 해당하는 위치에 해당 bin의 bit가 배치됩니다.
예를 들어 크기가 256byte인 free chunk의 인덱스는 65이며, binmap[2]에 bit정보가 저장됩니다.
할당자는 idx2bit() 함수를 이용하여 저장할 bit값을 계산합니다.
binmap[2]에는 2(1 << (index(65) & 31))가 배치됩니다.
binmap[] 배열을 사용하면 많은양의 빈 검색이 간소화됩니다.
/* Conservatively use 32 bits per map word, even if on 64bit system */ #define BINMAPSHIFT 5 #define BITSPERMAP (1U << BINMAPSHIFT) #define BINMAPSIZE (NBINS / BITSPERMAP) #define idx2block(i) ((i) >> BINMAPSHIFT) #define idx2bit(i) ((1U << ((i) & ((1U << BINMAPSHIFT)-1)))) #define mark_bin(m,i) ((m)->binmap[idx2block(i)] |= idx2bit(i)) #define unmark_bin(m,i) ((m)->binmap[idx2block(i)] &= ~(idx2bit(i))) #define get_binmap(m,i) ((m)->binmap[idx2block(i)] & idx2bit(i)) |
#include <stdio.h> #include <stdlib.h> void main(){ char *fast1 = malloc(16); char *fast2 = malloc(32); char *fast3 = malloc(48); char *fast4 = malloc(64); char *fast5 = malloc(80); char *fast6 = malloc(96); char *fast7 = malloc(128); char *fast8 = malloc(144); free(fast1); free(fast2); free(fast3); free(fast4); free(fast5); free(fast6); free(fast7); } |
해제된 chunk들 중 fastbin에 포함되는 chunk들은 fastbinsY에 배치되어 있습니다.
lazenca0x0@ubuntu:~/Book/malloc$ gdb -q ./fast Reading symbols from ./fast...(no debugging symbols found)...done. gdb-peda$ disassemble main Dump of assembler code for function main: 0x0000000000400566 <+0>: push rbp 0x0000000000400567 <+1>: mov rbp,rsp 0x000000000040056a <+4>: sub rsp,0x50 0x000000000040056e <+8>: mov edi,0x10 ... 0x0000000000400647 <+225>: call 0x400430 <free@plt> 0x000000000040064c <+230>: nop 0x000000000040064d <+231>: leave 0x000000000040064e <+232>: ret End of assembler dump. gdb-peda$ b *0x000000000040064c Breakpoint 1 at 0x40064c gdb-peda$ r Starting program: /home/lazenca0x0/Book/malloc/fast Breakpoint 1, 0x000000000040064c in main () gdb-peda$ p main_arena $1 = { mutex = 0x0, flags = 0x0, fastbinsY = {0x602000, 0x602020, 0x602050, 0x602090, 0x6020e0, 0x602140, 0x0, 0x0, 0x0, 0x0}, top = 0x602390, ... binmap = {0x0, 0x0, 0x0, 0x0}, next = 0x7ffff7dd1b20 <main_arena>, next_free = 0x0, attached_threads = 0x1, system_mem = 0x21000, max_system_mem = 0x21000 } gdb-peda$ x/2gx 0x602000 0x602000: 0x0000000000000000 0x0000000000000021 gdb-peda$ x/2gx 0x602140 0x602140: 0x0000000000000000 0x0000000000000071 gdb-peda$ |
#include <stdio.h> #include <stdlib.h> void main(){ char *fast1 = malloc(16); char *fast2 = malloc(16); char *fast3 = malloc(16); char *fast4 = malloc(16); free(fast2); free(fast1); free(fast3); free(fast4); } |
0x4005bc, 0x4005c6에 break point를 설정합니다.
lazenca0x0@ubuntu:~/Book/malloc$ gdb -q ./fast2 Reading symbols from ./fast2...(no debugging symbols found)...done. gdb-peda$ disassemble main Dump of assembler code for function main: 0x0000000000400566 <+0>: push rbp 0x0000000000400567 <+1>: mov rbp,rsp 0x000000000040056a <+4>: sub rsp,0x20 ... 0x00000000004005b7 <+81>: call 0x400430 <free@plt> 0x00000000004005bc <+86>: mov edi,0x10 0x00000000004005c1 <+91>: call 0x400450 <malloc@plt> 0x00000000004005c6 <+96>: mov QWORD PTR [rbp-0x8],rax 0x00000000004005ca <+100>: nop 0x00000000004005cb <+101>: leave 0x00000000004005cc <+102>: ret End of assembler dump. gdb-peda$ b *0x00000000004005bc Breakpoint 1 at 0x4005bc gdb-peda$ b *0x00000000004005c6 Breakpoint 2 at 0x4005c6 gdb-peda$ r Starting program: /home/lazenca0x0/Book/malloc/fast2 Breakpoint 1, 0x00000000004005bc in main () gdb-peda$ p main_arena.fastbinsY $1 = {0x602040, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0} gdb-peda$ x/4gx 0x602040 0x602040: 0x0000000000000000 0x0000000000000021 0x602050: 0x0000000000602000 0x0000000000000000 gdb-peda$ x/4gx 0x0000000000602000 0x602000: 0x0000000000000000 0x0000000000000021 0x602010: 0x0000000000602020 0x0000000000000000 gdb-peda$ x/4gx 0x0000000000602020 0x602020: 0x0000000000000000 0x0000000000000021 0x602030: 0x0000000000000000 0x0000000000000000 gdb-peda$ |
gdb-peda$ c Continuing. Breakpoint 2, 0x00000000004005c6 in main () gdb-peda$ p main_arena.fastbinsY $2 = {0x602000, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0} gdb-peda$ x/4gx 0x602000 0x602000: 0x0000000000000000 0x0000000000000021 0x602010: 0x0000000000602020 0x0000000000000000 gdb-peda$ x/4gx 0x0000000000602020 0x602020: 0x0000000000000000 0x0000000000000021 0x602030: 0x0000000000000000 0x0000000000000000 gdb-peda$ i r rax rax 0x602050 0x602050 gdb-peda$ |
"small*"변수들이 가리키는 메모리들을 모두 해제한 후 200byte, 128byte의 메모리 할당을 요청합니다.
#include <stdio.h> #include <stdlib.h> void main(){ char *small1 = malloc(128); char *tmp1 = malloc(16); char *small2 = malloc(128); char *tmp2 = malloc(16); char *small3 = malloc(128); char *tmp3 = malloc(16); char *small4 = malloc(200); char *tmp4 = malloc(16); char *small5 = malloc(160); char *small6= malloc(160); char *tmp9 = malloc(16); free(small2); free(small1); free(small3); free(small4); free(small5); free(small6); char *small7 = malloc(200); char *small8 = malloc(128); } |
0x40064b에서 인접한 small chunk의 변화를 확인합니다.
0x40065a에서 bins영역에 등록된 small bin을 확인합니다.
lazenca0x0@ubuntu:~/Book/malloc$ gcc -o small small.c lazenca0x0@ubuntu:~/Book/malloc$ gdb -q ./small Reading symbols from ./small...(no debugging symbols found)...done. gdb-peda$ disassemble main Dump of assembler code for function main: 0x0000000000400566 <+0>: push rbp 0x0000000000400567 <+1>: mov rbp,rsp 0x000000000040056a <+4>: sub rsp,0x70 ... 0x000000000040064b <+229>: call 0x400430 <free@plt> 0x0000000000400650 <+234>: mov edi,0xc8 0x0000000000400655 <+239>: call 0x400450 <malloc@plt> 0x000000000040065a <+244>: mov QWORD PTR [rbp-0x10],rax 0x000000000040065e <+248>: mov edi,0x80 0x0000000000400663 <+253>: call 0x400450 <malloc@plt> 0x0000000000400668 <+258>: mov QWORD PTR [rbp-0x8],rax 0x000000000040066c <+262>: nop 0x000000000040066d <+263>: leave 0x000000000040066e <+264>: ret End of assembler dump. gdb-peda$ b *0x000000000040064b Breakpoint 1 at 0x40064b gdb-peda$ b *0x000000000040065a Breakpoint 2 at 0x40065a gdb-peda$ b *0x0000000000400668 Breakpoint 3 at 0x400668 gdb-peda$ |
free()가 실행되면 두 chunk는 병합되어 하나의 chunk가 됩니다.
해당 chunk(0x602300)의 크기가 352byte가 되었습니다.
gdb-peda$ r Starting program: /home/lazenca0x0/Book/malloc/small Breakpoint 1, 0x000000000040064b in main () gdb-peda$ p main_arena.bins[0] $2 = (mchunkptr) 0x602300 gdb-peda$ p main_arena.bins[1] $3 = (mchunkptr) 0x6020b0 gdb-peda$ p main_arena.bins[0].size $4 = 0xb1 gdb-peda$ p/d main_arena.bins[0].size - 1 $5 = 176 gdb-peda$ x/i $rip => 0x40064b <main+229>: call 0x400430 <free@plt> gdb-peda$ i r rdi rdi 0x6023c0 0x6023c0 gdb-peda$ ni 0x0000000000400650 in main () gdb-peda$ p main_arena.bins[0] $6 = (mchunkptr) 0x602300 gdb-peda$ p/d main_arena.bins[0].size - 1 $7 = 352 gdb-peda$ |
gdb-peda$ p/d ((0x90 >> 4) - 1) * 2 $8 = 16 gdb-peda$ p main_arena.bins[16] $9 = (mchunkptr) 0x7ffff7dd1bf8 <main_arena+216> gdb-peda$ p main_arena.bins[17] $10 = (mchunkptr) 0x7ffff7dd1bf8 <main_arena+216> gdb-peda$ c Continuing. Breakpoint 2, 0x000000000040065a in main () gdb-peda$ p main_arena.bins[16] $11 = (mchunkptr) 0x602160 gdb-peda$ p main_arena.bins[17] $12 = (mchunkptr) 0x6020b0 gdb-peda$ x/4gx 0x602160 0x602160: 0x0000000000000000 0x0000000000000091 0x602170: 0x0000000000602000 0x00007ffff7dd1bf8 gdb-peda$ x/4gx 0x602000 0x602000: 0x0000000000000000 0x0000000000000091 0x602010: 0x00000000006020b0 0x0000000000602160 gdb-peda$ x/4gx 0x00000000006020b0 0x6020b0: 0x0000000000000000 0x0000000000000091 0x6020c0: 0x00007ffff7dd1bf8 0x0000000000602000 gdb-peda$ |
gdb-peda$ c Continuing. Breakpoint 3, 0x0000000000400668 in main () gdb-peda$ p main_arena.bins[16] $13 = (mchunkptr) 0x602160 gdb-peda$ p main_arena.bins[17] $14 = (mchunkptr) 0x602000 gdb-peda$ i r rax rax 0x6020c0 0x6020c0 gdb-peda$ |
"large*" 변수가 가리키는 메모리들을 모두 해제한 후 200byte, 1040byte의 메모리 할당을 요청합니다.
#include <stdio.h> #include <stdlib.h> void main(){ char *large1 = malloc(1024); char *tmp1 = malloc(16); char *large2 = malloc(1040); char *tmp2 = malloc(16); char *large3 = malloc(1056); char *tmp3 = malloc(16); char *large4 = malloc(200); char *tmp4 = malloc(16); char *large5 = malloc(1120); char *large6= malloc(1120); char *tmp9 = malloc(16); free(large2); free(large1); free(large3); free(large4); free(large5); free(large6); char *large7 = malloc(200); char *large8 = malloc(1040); } |
0x40064b에서 인접한 Large chunk의 변화를 확인합니다.
0x40065a에서 bins[]에 배치된 Large chunk을 확인합니다.
lazenca0x0@ubuntu:~/Book/Heap/1.Malloc$ gcc -o large large.c lazenca0x0@ubuntu:~/Book/Heap/1.Malloc$ gdb -q ./large Reading symbols from ./large...(no debugging symbols found)...done. gdb-peda$ disassemble main Dump of assembler code for function main: 0x0000000000400566 <+0>: push rbp 0x0000000000400567 <+1>: mov rbp,rsp 0x000000000040056a <+4>: sub rsp,0x70 ... 0x000000000040064b <+229>: call 0x400430 <free@plt> 0x0000000000400650 <+234>: mov edi,0xc8 0x0000000000400655 <+239>: call 0x400450 <malloc@plt> 0x000000000040065a <+244>: mov QWORD PTR [rbp-0x10],rax 0x000000000040065e <+248>: mov edi,0x410 0x0000000000400663 <+253>: call 0x400450 <malloc@plt> 0x0000000000400668 <+258>: mov QWORD PTR [rbp-0x8],rax 0x000000000040066c <+262>: nop 0x000000000040066d <+263>: leave 0x000000000040066e <+264>: ret End of assembler dump. gdb-peda$ b *0x000000000040064b Breakpoint 1 at 0x40064b gdb-peda$ b *0x000000000040065a Breakpoint 2 at 0x40065a gdb-peda$ b *0x0000000000400668 Breakpoint 3 at 0x400668 gdb-peda$ |
free()가 실행되면 두 chunk는 병합되어 하나의 chunk가 됩니다
해당 chunk(0x602db0)의 크기가 2272byte가 되었습니다.
gdb-peda$ r Starting program: /home/lazenca0x0/Book/Heap/1.Malloc/large Breakpoint 1, 0x000000000040064b in main () gdb-peda$ p main_arena.bins[0] $1 = (mchunkptr) 0x602db0 gdb-peda$ p main_arena.bins[1] $2 = (mchunkptr) 0x602430 gdb-peda$ p main_arena.bins[0].size $3 = 0x471 gdb-peda$ p/d main_arena.bins[0].size - 1 $4 = 1136 gdb-peda$ x/i $rip => 0x40064b <main+229>: call 0x400430 <free@plt> gdb-peda$ i r rdi rdi 0x603230 0x603230 gdb-peda$ ni 0x0000000000400650 in main () gdb-peda$ p main_arena.bins[0] $6 = (mchunkptr) 0x602db0 gdb-peda$ p main_arena.bins[0].size $7 = 0x8e1 gdb-peda$ p/d main_arena.bins[0].size - 1 $9 = 2272 gdb-peda$ |
Large bin은 Small bin과 동일하게 doubly-linked list 로 chunk들을 연결합니다.
할당자는 Large bin에 해당하는 chunk가 "bins"에 배치될때 해당 인덱스에 해당하는 chunk들을 크기 별로 정렬합니다.
Chunk가 Unsorted bin에 있을 때는 해제된 순서데로 연결되어 있습니다.
0x602870 (size : 0x430) <--> 0x602000 (size : 0x410) <--> 0x602430 (size : 0x420)
하지만 Chunk가 "bins"에 배치되면 chunk의 크기순으로 정렬됩니다.
0x602870 (size : 0x430) <--> 0x602430 (size : 0x420) <--> 0x602000 (size : 0x410)
gdb-peda$ p main_arena.bins[1] $19 = (mchunkptr) 0x602430 gdb-peda$ x/4gx 0x602430 0x602430: 0x0000000000000000 0x0000000000000421 0x602440: 0x00007ffff7dd1b78 0x0000000000602000 gdb-peda$ x/4gx 0x0000000000602000 0x602000: 0x0000000000000000 0x0000000000000411 0x602010: 0x0000000000602430 0x0000000000602870 gdb-peda$ x/4gx 0x0000000000602870 0x602870: 0x0000000000000000 0x0000000000000431 0x602880: 0x0000000000602000 0x0000000000602cc0 gdb-peda$ p/d ((1040 >> 6) + 48 - 1) * 2 $12 = 126 gdb-peda$ p main_arena.bins[126] $13 = (mchunkptr) 0x7ffff7dd1f68 <main_arena+1096> gdb-peda$ p main_arena.bins[127] $14 = (mchunkptr) 0x7ffff7dd1f68 <main_arena+1096> gdb-peda$ c Continuing. Breakpoint 2, 0x000000000040065a in main () gdb-peda$ p main_arena.bins[126] $15 = (mchunkptr) 0x602870 gdb-peda$ p main_arena.bins[127] $16 = (mchunkptr) 0x602000 gdb-peda$ x/4gx 0x602870 0x602870: 0x0000000000000000 0x0000000000000431 0x602880: 0x0000000000602430 0x00007ffff7dd1f68 gdb-peda$ x/4gx0x0000000000602430 0x602430: 0x0000000000000000 0x0000000000000421 0x602440: 0x0000000000602000 0x0000000000602870 gdb-peda$ x/4gx 0x0000000000602000 0x602000: 0x0000000000000000 0x0000000000000411 0x602010: 0x00007ffff7dd1f68 0x0000000000602430 gdb-peda$ |
gdb-peda$ c Continuing. Breakpoint 3, 0x0000000000400668 in main () gdb-peda$ p main_arena.bins[126] $17 = (mchunkptr) 0x602870 gdb-peda$ p main_arena.bins[127] $18 = (mchunkptr) 0x602000 gdb-peda$ i r rax rax 0x602440 0x602440 gdb-peda$ |
Excuse the ads! We need some help to keep our site up.