티스토리 뷰
원본 URL : https://sploitfun.wordpress.com/2015/02/10/understanding-glibc-malloc/
※ 원본 URL의 빨간색 표시된 글을 누르면 추가적인 참고자료가 있습니다.
------------------------------------------------------------------------------------------------------------------------------
Understanding glibc malloc
나는 항상 힙 메모리에 매료되었다. 다음과 같은 질문은
커널로부터 힙 메모리는 어떻게 획득되는가? 어떻게 메모리는 능률적으로 관리되는가? 힙은 커널 또는 라이브러리 또는 어플리케이션에 의해 관리되는가? 힙 메모리를 exploit 가능한가? |
상당한 시간이 걸리는 질문이다. 그러나 최근 이것에 대해 이해를 가지는 시간을 가졌다. 그래서 여기에 나는 내가 매료된 지식을 공유하고자 한다!! 많은 메모리 할당자들이 사용가능하다 :
- dllmalloc - 일반적인 목적의 할당자
- ptmalloc2 - glibc
- jemalloc - FreeBSD와 Firefox
- tcmalloc - Google(Chrome)
- libumem - Solaris
- ...
System Calls : 이 글에서 볼 수 있듯이 malloc은 내부에서 brk 또는 mmap syscall 중 하나를 호출한다.
Threading : 리눅스의 초창기에는, dlmalloc이 기본 메모리 할당자로 사용되었다. 그러나 ptmalloc2의 스레딩 지원 기능이 추가된 이후로는, 이것이 리눅스의 기본 메모리 할당자가 되었다. 스레딩 지원은 메모리 할당자 성능을 개량시켜주어, 어플리케이션의 성능 또한 개량된다. dlmalloc에서 동일한 시간에 2개의 스레드가 malloc을 호출할 경우, freelist data structures는 모든 사용가능한 스레드에 둘러싸인 상태로 공유되어 있기 때문에, 오로지 하나의 스레드만 critical section(임계 영역)에 들어갈 수 있다. 이런 이유로 메모리 할당은 다중 스레드 어플리케이션에서 시간을 잡아먹게 되어, 결과적으로 성능 저하로 이어진다. 거기에 반해 ptmalloc2에서는, 동일한 시간에 2개의 스레드가 malloc을 호출할 경우, 메모리는 각각의 스레드가 분배된 힙 영역을 일정하게 유지하고, 힙을 유지하기 위한 freelist data structures 또한 분배되어 있기 때문에 즉시 할당된다. 이렇게 각각의 스레드의 유지를 위해 분배된 힙과 freelist data structures의 행동을 per thread arena라고 부른다.
예제 :
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 | /* Per thread arena example. */ #include <stdio.h> #include <stdlib.h> #include <pthread.h> #include <unistd.h> #include <sys/types.h> void* threadFunc(void* arg) { printf("Before malloc in thread 1\n"); getchar(); char* addr = (char*) malloc(1000); printf("After malloc and before free in thread 1\n"); getchar(); free(addr); printf("After free in thread 1\n"); getchar(); } int main() { pthread_t t1; void* s; int ret; char* addr; printf("Welcome to per thread arena example::%d\n",getpid()); printf("Before malloc in main thread\n"); getchar(); addr = (char*) malloc(1000); printf("After malloc and before free in main thread\n"); getchar(); free(addr); printf("After free in main thread\n"); getchar(); ret = pthread_create(&t1, NULL, threadFunc, NULL); if(ret) { printf("Thread creation error\n"); return -1; } ret = pthread_join(t1, &s); if(ret) { printf("Thread join error\n"); return -1; } return 0; } | cs |
출력 분석 :
메인 스레드에서의 malloc 호출 이전 : 아래의 출력에서 힙 영역이 아직 없는 것과 thread1이 생성되지 않아 스레드의 스택이 없는 것을 볼 수 있다.
sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$ ./mthread Welcome to per thread arena example::6501 Before malloc in main thread ... sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$ cat /proc/6501/maps 08048000-08049000 r-xp 00000000 08:01 539625 /home/sploitfun/ptmalloc.ppt/mthread/mthread 08049000-0804a000 r--p 00000000 08:01 539625 /home/sploitfun/ptmalloc.ppt/mthread/mthread 0804a000-0804b000 rw-p 00001000 08:01 539625 /home/sploitfun/ptmalloc.ppt/mthread/mthread b7e05000-b7e07000 rw-p 00000000 00:00 0 ... sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$ | cs |
메인 스레드에서의 malloc 호출 이후 :아래의 출력에서 힙 영역이 생성되었고 데이터 영역(0x0804b000 - 0x0806c000) 위에 위치한 것을 볼 수 있고, 이는 힙 메모리가 프로그램의 break 위치를 증가시킴으로써 생성되는 것을 보여준다 ( ie) brk syscall 사용). 또한, 사용자는 오직 1000바이트만 요청했으나, 힙 메모리의 크기는 132KB나 생성되었다. 이러한 힙 메모리의 인접한 지역을 arena라고 부른다. 이 arena는 메인 스레드로써 생성되었기 때문에, 이것을 main arena라고 부른다. 이후, 할당 요청은 이 arena를 사용하여 비어있는 공간이 없어질 때 까지 유지하면서 사용한다. arena의 비어있는 공간이 고갈되었을 경우, 프로그램의 break 위치를 증가시킴으로써 더욱 성장할 수 있다 (top 청크의 크기를 증가시켜 여분의 공간을 포함할 수 있도록 조정한 후). 이와 비슷하게 top 청크에 비어있는 공간이 많은 경우, arena는 또한 줄어들 수도 있다.
NOTE : top 청크는 arena의 최상단의 청크를 말한다. 아래에서는 이것에 대해 자세하게 "Top Chunk" 섹션을 보여준다.
sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$ ./mthread Welcome to per thread arena example::6501 Before malloc in main thread After malloc and before free in main thread ... sploitfun@sploitfun-VirtualBox:~/lsploits/hof/ptmalloc.ppt/mthread$ cat /proc/6501/maps 08048000-08049000 r-xp 00000000 08:01 539625 /home/sploitfun/ptmalloc.ppt/mthread/mthread 08049000-0804a000 r--p 00000000 08:01 539625 /home/sploitfun/ptmalloc.ppt/mthread/mthread 0804a000-0804b000 rw-p 00001000 08:01 539625 /home/sploitfun/ptmalloc.ppt/mthread/mthread 0804b000-0806c000 rw-p 00000000 00:00 0 [heap] b7e05000-b7e07000 rw-p 00000000 00:00 0 ... sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$ | cs |
메인 스레드에서의 free 호출 이후 : 아래의 출력에서 할당된 메모리 집단이 해제된 경우, 메모리의 뒤에서 해제된 메모리가 즉각 운영체제에 반환되지 않는 것을 볼 수 있다. 할당된 메모리의 일부분(1000바이트)은 오로지 main arena의 bin(glibc malloc에서, freelist data structures는 bin으로써 참조됨)에 이 해제된 블럭을 추가하고 'glibc malloc' 라이브러리에 반환된다. 이후, 사용자가 메모리를 요청하는 경우, 'glibc malloc'은 커널로부터 새로운 힙 메모리를 얻지 않고, 대신 bin에서 비어있는 블럭을 탐색해준다. 그리고 비어있는 공간이 존재하지 않는 경우, 커널로부터 메모리를 받는다.
sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$ ./mthread Welcome to per thread arena example::6501 Before malloc in main thread After malloc and before free in main thread After free in main thread ... sploitfun@sploitfun-VirtualBox:~/lsploits/hof/ptmalloc.ppt/mthread$ cat /proc/6501/maps 08048000-08049000 r-xp 00000000 08:01 539625 /home/sploitfun/ptmalloc.ppt/mthread/mthread 08049000-0804a000 r--p 00000000 08:01 539625 /home/sploitfun/ptmalloc.ppt/mthread/mthread 0804a000-0804b000 rw-p 00001000 08:01 539625 /home/sploitfun/ptmalloc.ppt/mthread/mthread 0804b000-0806c000 rw-p 00000000 00:00 0 [heap] b7e05000-b7e07000 rw-p 00000000 00:00 0 ... sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$ | cs |
thread1에서의 malloc 호출 이전 : 아래의 출력에서 thread1의 힙 영역은 업으나, thread1의 스레드 스택은 생성된 것을 볼 수 있다.
sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$ ./mthread Welcome to per thread arena example::6501 Before malloc in main thread After malloc and before free in main thread After free in main thread Before malloc in thread 1 ... sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$ cat /proc/6501/maps 08048000-08049000 r-xp 00000000 08:01 539625 /home/sploitfun/ptmalloc.ppt/mthread/mthread 08049000-0804a000 r--p 00000000 08:01 539625 /home/sploitfun/ptmalloc.ppt/mthread/mthread 0804a000-0804b000 rw-p 00001000 08:01 539625 /home/sploitfun/ptmalloc.ppt/mthread/mthread 0804b000-0806c000 rw-p 00000000 00:00 0 [heap] b7604000-b7605000 ---p 00000000 00:00 0 b7605000-b7e07000 rw-p 00000000 00:00 0 [stack:6594] ... sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$ | cs |
thread1에서의 malloc 호출 이후 : 아래의 출력에서 thread1의 힙 영역이 생성된 것을 볼 수 있다. 그리고 이 영역은 메모리의 메핑된 세그먼트 일부 (0xb7500000-0xb7521000, 132KB의 크기)에 위치하며, sbrk를 사용하는 main thread와 달리 mmap을 사용하여 힙 메모리가 생성된다. 여기서 다시 볼 수 있듯이, 사용자는 1000바이트만 요청했지만, 1MB 크기의 힙 메모리가 프로세스 주소 공간에 매핑되어 있다. 이 1MB 중, 132KB가 read-write 권한이 세트되어, 이 스레드를 위해 힙 메모리로 할당되었다. 이러한 메모리의 일부분(132KB을 thread arena라고 부른다.
NOTE : 사용자가 128KB(malloc(132*1024))보다 큰 크기를 요청할 경우와 arena에 사용자의 요청을 만족시킬 수 있는 충분한 공간이 없는 경우, 비록 main arena 또는 thread arena에서 만들어진 요청이지만 이것을 무시하고 메모리는 mmap syscall(sbrk 미사용)을 사용하여 할당된다.
sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$ ./mthread Welcome to per thread arena example::6501 Before malloc in main thread After malloc and before free in main thread After free in main thread Before malloc in thread 1 After malloc and before free in thread 1 ... sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$ cat /proc/6501/maps 08048000-08049000 r-xp 00000000 08:01 539625 /home/sploitfun/ptmalloc.ppt/mthread/mthread 08049000-0804a000 r--p 00000000 08:01 539625 /home/sploitfun/ptmalloc.ppt/mthread/mthread 0804a000-0804b000 rw-p 00001000 08:01 539625 /home/sploitfun/ptmalloc.ppt/mthread/mthread 0804b000-0806c000 rw-p 00000000 00:00 0 [heap] b7500000-b7521000 rw-p 00000000 00:00 0 b7521000-b7600000 ---p 00000000 00:00 0 b7604000-b7605000 ---p 00000000 00:00 0 b7605000-b7e07000 rw-p 00000000 00:00 0 [stack:6594] ... sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$ | cs |
thread1에서의 free 호출 이후 : 아래의 출력에서 해제한 할당된 메모리 집단은 운영체제에 힙 메모리를 반환하지 않는다. 대신 할당된 메모리 지역(1000바이트)을 thread arena의 bin에 해제된 블럭을 추가하고 'glibc malloc'에 반환한다.
sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$ ./mthread Welcome to per thread arena example::6501 Before malloc in main thread After malloc and before free in main thread After free in main thread Before malloc in thread 1 After malloc and before free in thread 1 After free in thread 1 ... sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$ cat /proc/6501/maps 08048000-08049000 r-xp 00000000 08:01 539625 /home/sploitfun/ptmalloc.ppt/mthread/mthread 08049000-0804a000 r--p 00000000 08:01 539625 /home/sploitfun/ptmalloc.ppt/mthread/mthread 0804a000-0804b000 rw-p 00001000 08:01 539625 /home/sploitfun/ptmalloc.ppt/mthread/mthread 0804b000-0806c000 rw-p 00000000 00:00 0 [heap] b7500000-b7521000 rw-p 00000000 00:00 0 b7521000-b7600000 ---p 00000000 00:00 0 b7604000-b7605000 ---p 00000000 00:00 0 b7605000-b7e07000 rw-p 00000000 00:00 0 [stack:6594] ... sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$ | cs |
Arena :
arena의 수 : 위의 예제에서, 메인 스레드가 main arena를 가지고 thread1이 자신의 thread arena를 가지는 것을 보았다. 그래서 스레드의 수를 무시하고 스레드들과 arena 사이의 일대일 매핑은 존재할 수 있는가? 틀림없이 아니다. 맛이 간 어플리케이션은 core의 수보다 많은 스레드의 수를 가질 수 있으나, 이러한 경우는, 하나의 arena당 스레드를 가져 bit가 크게 낭비된다. 이런 이유로, 어플리케이션의 arena 제한은 현재 시스템의 core의 수에 기반된다.
For 32 bit systems: Number of arena = 2 * number of cores. For 64 bit systems: Number of arena = 8 * number of cores. | cs |
다중 Arena :
예제 : 1개의 코어를 가진 32bit 시스템에서 다중스레드 어플리케이션(4개의 스레드 = 메인 스레드 + 3개의 사용자 스레드)을 실행시켜 보자. 여기서 스레드가 없는 경우 (4) > 2개의 코어가 없는 경우 (2)를 확인할 수 있다. 이런 이유로 이와 같은 상황에서, 'glibc malloc'는 다중 arena가 모든 사용가능한 스레드와 공유되는지를 확인한다. 그런데 어떻게 공유하는가?
- 메인 스레드의 경우, 처음으로 malloc을 호출하면 이미 생성되어 있던 main arena는 어떠한 충돌도 없이 사용된다.
- thread1과 thread2가 처음으로 malloc을 호출하는 경우, 이 스레드들을 위해 새로운 arena가 생성되고 어떠한 충돌도 없이 사용된다. 여기까지는 스레드와 arena가 일대일 매핑을 가진다.
- thread3이 처음으로 malloc을 호출하는 경우, arena의 제한 개수가 계산된다. 여기서 arena의 한계를 넘어, 현재 존재하는 arena들(Main arena나 Arena1 또는 Arena2)을 재사용한다.
- 재사용 :
- 사용가능한 arena들이 한 번의 루프를 넘는 동안, arena에 lock을 반복한다.
- 만일 성공적으로 lock된 경우(main arena가 성공적으로 lock된 경우), 사용자에게 arena는 반환된다.
- 만일 어떠한 arena도 해제되지 않은 경우, 다음 행에 arena를 위한 블럭이 있다.
- thread3이 malloc을 호출한 경우(두 번째 호출), malloc은 가장 마지막에 접근한 arena를 사용할 것이다(main arena). 만일 main arena를 해제하는 경우, 또 다른 thread3을 main arena가 해제된 곳까지 폐쇄시킨 후, 이를 사용한다. 그래서 main arena는 main thread와 thread3에 공유된다.
주로 'glibc malloc'의 소스 코드에서 아래와 같은 3개의 데이터 구조체를 확인할 수 있다 :
heap_info - Heap Header - 단일 스레드 arena는 여러 개의 힙을 가질 수 있다. 각 힙은 각자의 헤더를 가진다. 왜 여러 개의 힙이 필요한가? 모든 스레드 arena는 오직 하나의 힙만을 가지고 시작하지만, 힙 영역의 공간이 부족해지는 경우, arena에 새로운 힙(인접하지 않은 영역)을 할당해주어야 한다.
malloc_state - Arena Header - 단일 스레드 arena는 여러 개의 힙을 가질 수 있지만, 이러한 모든 힙에 대해서는 오직 하나의 arena header만이 존재한다. Arena header는 bin, top chunk, last remainder chunk 등에 대한 정보를 가진다.
malloc_chunk - Chunk Header - 힙은 사용자의 요청을 기반으로 다수의 청크로 분열된다. 그리고 각 청크는 각자의 청크 헤더를 가진다.
NOTE :
- Main arena는 여러 개의 힙과 heap_info 구조체를 가질 수 없다. main arena의 공간이 부족한 경우, sbrk 힙 영역은 메모리가 매핑된 영역까지 확장(인접한 영역)된다.
- thread arena와 달리, main arena의 arena header는 sbrk 힙 영역의 일부가 아니다. main arena는 전역 변수이며, libc.so의 데이터 영역에서 찾을 수 있다.
thread arena를 그림으로 나타낸 경우(여러 개의 힙 영역) :
Chunk : 청크는 힙 영역에서 찾을 수 있으며, 아래 중 하나의 타입을 가진다 :
- Allocated chunk
- Free chunk
- Top chunk
- Last Remainder chunk
Allocated chunk(할당되어 있는 청크) :
prev_size : 만일 이전 청크를 해제하는 경우, 이 필드는 이전 청크의 크기를 저장한다. 만일 이전 청크가 할당된 경우에는, 이 필드는 이전 청크의 사용자 데이터를 저장한다.
size : 이 필드는 할당된 청크의 크기를 저장한다. 이 필드의 맨 끝 3bit는 flag 정보를 저장한다.
- PREV_INUSE (P) - 이 비트는 이전 청크가 할당된 경우 세트된다.
- IS_MMAPPED (M) - 이 비트는 현재 청크가 mmap을 통해 할당된 경우 세트된다.
- NON_MAIN_ARENA (N) - 이 비트는 현재 청크가 thread arena에 위치하는 경우 세트된다.
- malloc_chunk의 다른 필드(fd,bk)는 할당되어 있는 청크에서는 사용하지 않는다. 따라서 할당되어 있는 청크는 사용자 데이터가 저장되어 있다.
- 사용자가 요청한 크기는 malloc_chunk를 저장하고 메모리를 정렬하기 위해서는 약간의 공간이 여분으로 필요하기 때문에 사용할 수 있는 크기(청크 내부를 나타내는 크기)로 변환된다.
prev_size : 2개의 free chunk는 함께 붙어 있을 수 없다. 각 청크를 해제하는 경우, 하나의 단일 free chunk로 결합된다. 따라서, 항상 해제된 청크의 이전 청크를 할당하고 있어서, prev_size는 이전 청크의 사용자 데이터를 저장하고 있다.
size : 이 필드는 free chunk의 크기를 저장하고 있다.
fd : Forward pointer - 동일한 빈에서의 다음 청크를 가리킨다(물리 메모리에서의 다음 청크가 아님).
bk : Backward pointer - 동일한 빈에서의 이전 청크를 가리킨다(물리 메모리에서의 이전 청크가 아님).
Bins : Bin은 freelist data structures이며, free chunk들을 수용하는데 사용한다. 청크의 크기를 기준으로 사용가능한 bin이 달라지게 된다 :
- Fast bin
- Unsorted bin
- Small bin
- Large bin
fastbinsY - 이 배열은 fast bin을 수용한다.
bins - 이 배열은 unsorted, small 그리고 large bin을 수용한다. 총 126개의 bin이 있고 다음과 같은 기준으로 나뉜다 :
- Bin 1 - Unsorted bin
- Bin 2 ~ Bin 63 - Small bin
- Bin 64 ~ Bin 126 - Large bin
- bin의 갯수 - 10
- 각 fast bin은 free chunk로 구성된 단일 연결리스트(다른 말로 binlist)를 가진다. 단일 연결리스트는 list의 중간으로부터 fast bin chunk을 제거할 수 없기 때문에 사용된다. 추가와 제거는 list의 앞쪽 끝에서 발생한다 - LIFO.
- 청크의 크기 - 각 8바이트씩
- Fast bin은 각 8바이트 크기를 가지는 청크의 binlist를 가진다. ie) 첫 번째 fast bin(index 0)은 16바이트 크기의 청크 binlist를 가지며, 두 번째 fast bin(index 1)은 24바이트 크기의 청크 binlist를 가지는 식으로, 이어진다.
- fast bin 내부의 청크는 동일한 크기이다.
- malloc 초기화에서, fast bin의 최대 크기는 64(!80)바이트로 세트되어 있다. 따라서, 기본 청크의 크기는 16 ~ 64인 경우, fast chunk로 분류된다.
- 병합 없음 - 해제된 2개의 청크가 서로 인접해 있을 수 있으며, 단일 free chunk로 결합되지 않는다. 병합이 없다는 것은 외부 단편화라는 결과를 가져올 수 있지만 해제의 속도가 빠르다는 장점도 있다!!
- malloc(fast chunk) -
- 초기의 fast bin의 최대 크기와 fast bin 인덱스는 비어 있기 때문에, 사용자가 fast chunk를 요청하더라도, fast bin code 대신, small bin code가 서비스할 수 있다.
- 이후에 비어있지 않게 된 경우, fast bin 인덱스는 해당하는 binlist로부터 검색을 하여 계산된다.
- 위에서 반환된 binlist의 첫 번째 청크는 삭제된 후, 사용자에게 반환된다.
- free(fast chunk) -
- Fast bin 인덱스는 해당하는 binlist로부터 검색을 하여 계산된다.
- free chunk는 위에서 반환된 binlist의 앞쪽 위치에 추가된다.
Unsorted Bin : small 또는 large chunk는 각각의 bin에서 추가가 아닌 해제되는 경우, unsorted bin에 추가된다. 이러한 처리방법은 최근에 해제된 청크를 재사용할 수 있도록 'glibc malloc'가 2번째 기회를 제공하기 위해서 있다. 따라서, 적절한 bin을 찾는데 걸리는 시간이 적기 때문에 메모리 할당과 반납의 비트 처리 속도가 빠르다(unsorted bin이기 때문).
- bin의 개수 - 1
- Unsorted bin은 free chunk의 환형 이중 연결리스트(다른 말로 binlist)를 가진다.
- 청크의 크기 - 크기에 제한이 없기 때문에, 다양한 크기의 청크가 이 bin에 저장될 수 있다.
Small Bin : 청크의 크기가 512바이트보다 작은 경우, small chunk라고 부른다. small chunk를 수용한 Bin을 small bin이라고 부른다. Small bin은 메모리 할당 및 반환이 large bin보다 빠르다(다만, fast bin보다는 느리다).
- bin의 개수 - 62
- 각 small bin은 free chunk로 구성된 환형 이중 연결리스트를 가진다. 이중 연결리스트는 list의 중간에서 small bin chunk를 제거할 수 있기 때문에 사용된다. 노드의 추가는 앞쪽 끝에서 발생하고 삭제는 list의 뒤쪽 끝에서 발생한다 - FIFO.
- 청크의 크기 - 각 8바이트씩
- Small bin은 각 8바이트 크기를 가지는 청크 binlist를 가진다. ie) 첫 번째 Small bin(Bin 2)은 16바이트 크기의 청크 binlist를 가지며, 두 번째 small bin(Bin 3)은 24바이트 크기의 청크 binlist를 가지는 식으로, 이어진다.
- small bin 내부의 청크는 동일한 크기이며, 따라서 정렬이 필요없다.
- 병합 - 해제된 2개의 청크는 각각 인접해 있을 수 없으며, 단일 free chunk로 결합된다. 병합은 외부 단편화를 제거하지만, 해제의 속도가 느리다.
- malloc(small chunk) -
- 초기의 모든 small bin은 NULL이기 때문에, 사용자가 small chunk를 요청했더라도, small bin code 대신, unsorted bin code가 서비스할 수 있다.
- 또한 malloc을 처음 호출할 경우, small bin과 large bin의 datastructures (bins)는 malloc_state는 초기화되어 있기 때문에 찾을 수 있다. ie) bin은 비어있는 자기자신을 가리키고 있다.
- 이후에 small bin이 비어있지 않은 경우, 해당하는 binlist의 마지막 청크는 제거된 후, 사용자에게 반환된다.
- free(small chunk) -
- 이 청크를 해제하는 동안, 이전 또는 다음 청크가 해제되었는지 체크하여, 해제된 경우 병합한다. ie) 각각의 연결 리스트로부터 청크를 제거하고 unsorted bin의 연결 리스트의 시작 부분에 새롭게 합병된 청크를 추가한다.
- bin의 개수 - 63
- 각 large bin은 free chunk로 구성된 환형 이중 연결리스트를 가진다. 이중 연결리스트는 어느 위치(맨 앞, 중간, 끝)에서나 large bins chunk를 추가하고 삭제할 수 있기 때문에 사용된다.
- 63개의 bins :
- 32개의 bin은 각 64바이트 크기를 가지는 청크의 binlist를 가진다. ie) 첫 번째 large bin(Bin 65)은 512바이트 ~ 568바이트 크기의 청크 binlist를 가지고, 두 번째 large bin(Bin 66)은 576바이트 ~ 632바이트 크기의 청크 binlist를 가지는 식으로, 이어진다.
- 16개의 bin은 각 512바이트 크기를 가지는 청크의 binlist를 가진다.
- 8개의 bin은 각 4,096바이트 크기를 가지는 청크의 binlist를 가진다.
- 4개의 bin은 각 32,768바이트 크기를 가지는 청크의 binlist를 가진다.
- 2개의 bin은 각 262,144바이트 크기를 가지는 청크의 binlist를 가진다.
- 1개의 bin은 남은 크기를 가지는 청크를 가진다.
- small bin과 달리, large bin 내부의 청크는 동일한 크기를 가지고 있지 않다. 따라서, 내림차순으로 저장된다. 가장 큰 청크는 binlist의 가장 앞쪽에 저장되고, 가장 작은 청크는 binlist의 가장 뒷쪽에 저장된다.
- 병합 - 해제된 2개의 청크는 각각 인접해 있을 수 없으며, 단일 free chunk로 결합된다.
- malloc(large chunk) -
- 초기의 모든 large bin은 NULL이기 때문에, 사용자가 large chunk를 요청했더라도, large bin code 대신, next largest bin code가 서비스할 수 있다.
- 또한 malloc을 처음 호출할 경우, small bin과 large bin의 datastructures (bins)는 malloc_state는 초기화되어 있기 때문에 찾을 수 있다. ie) bin은 비어있는 자기자신을 가리키고 있다.
- 이후에 large bin이 비어있지 않은 경우에서, largest chunk(이것의 binlist에서)의 크기가 사용자가 요청한 크기보다 크다면, binlist를 뒷쪽 끝부터 앞쪽 끝까지 확인하여, 사용자가 요청한 크기에 가깝거나 같은 적합한 크기의 청크를 찾는다. 찾게 되면, 해당 청크는 2개의 청크로 분리된다.
- User chunk(사용자가 요청한 크기) - 사용자에게 반환
- Remainder chunk(나머지 크기) - unsorted bin에 추가
- 만일 largest chunk(이것의 binlist에서)의 크기가 사용자가 요청한 크기보다 작다면, 비어있지 않는 다음 largest bin을 사용하여 사용자의 요청에 응답한다. 다음 largest bin code는 비어있지 않은 다음 largest bin을 찾기 위해 binmaps을 스캔하여, 해당하는 bin을 찾은 경우, 해당 binlist에서 적합한 청크가 검색되고, 적합한 청크를 분리하여 사용자에게 반환된다. 만일 찾지 못 한 경우에는, top chunk를 사용하여 사용자의 요청에 응답한다.
- free(large chunk) - free(small chunk)와 절차가 비슷하다.
- User chunk(사용자가 요청한 크기)
- Remainder chunk(나머지 크기)
Last Remainder Chunk : Remainder는 요청에 의해 너무 작게 분할되어 만들어진다. Last remainder chunk는 지역 참조성을 증가시키는데 도움을 준다. ie) 연속된 작은 청크의 malloc 요청은 결국 각각의 할당을 끝낼 것이다.
그러나 arena에서 사용가능한 많은 청크 중, last remainder chunk에 적합한 청크는?
사용자가 작은 청크를 요청했는데, small bin과 unsorted bin으로 제공할 수 없는 경우, binmaps는 비어있지 않는 다음 largest bin을 찾기 위해 스캔된다. 무사히, 비어있지 않는 다음 largest bin을 찾은 경우, 2개로 분리되어, user chunk는 사용자에게 반환되고 remainder chunk는 unsorted bin에 추가된다. 이 추가로 새로운 last remainder chunk가 생겼다.
어떻게 지역 참조성을 달성시키는가?
뒤늦게 사용자가 작은 청크를 요청했으나, last remainder chunk가 오로지 unsorted bin에만 있는 청크인 경우, last remainder chunk는 2개로 분리되어, user chunk는 사용자에게 반환되고 remainder chunk는 unsorted bin에 추가된다. 이 추가로 새로운 last remainder chunk가 생겼다. 이와 같은 후속 메모리 할당은 서로의 옆에 할당되는 것으로 끝난다.
'System > Linux' 카테고리의 다른 글
| 절대 디렉토리 경로 조작(Absolute Path Traversal) (0) | 2017.03.21 |
|---|---|
| qira 설치 및 사용법 (0) | 2016.07.31 |
| Heap overflow using Malloc Maleficarum 번역 (0) | 2016.07.14 |
| Position Independent Executables(PIE) 번역 (0) | 2016.06.17 |
| Memory Leak으로 얻은 주소로 offset 알아내기 (0) | 2016.05.01 |