(glibc) malloc - 1
Heap
요청에 따라 할당되는, chunk의 형태로 나뉠 수 있는 (인접한)연속된 메모리 영역을 의미한다. 예전에는 한 어플리케이션에 하나의 힙만 존재했지만, 지금은 한 어플리케이션이 여러 힙을 가질 수 있다. 각각의 heap은 하나의 arena에만 속할 수 있다.
Chunk
실제로 malloc()
으로 할당/반환받게 되는 영역을 말한다. 8 bytes의 배수로 할당된다.
* 64bit OS에서는 16 bytes의 배수로 할당된다.
Glibc’s malloc은 chunk-oriented다. 커다란 heap을 다양한 사이즈의 chunk로 나눠 할당한다. 하나의 chunk는 하나의 heap 내부에 존재하며, 당연히 하나의 arena에 속한다.
각 chunk는 size가 얼마인지, adjacent chunk의 위치는 어디인지를 나타내는 meta-data를 포함한다.
- chunk가 free되면 그 공간을 재사용할 수 있도록 linked list 형태의 arena-related information에 추가한다.
- free’d chunk의 마지막
word
(type)는 chunk size의 복사본을 가지고 있으며, 이word
의 3 LSBs는 0으로 설정된다. - chunk의 앞쪽에 있는 원래 chunk size의 3 LSBs는 flags로 사용된다. * chunk는 8 bytes의 배수이기 때문에 3 LSBs를 flag로 사용할 수 있다.
- chunk의 최소 크기는
4\*sizeof(void\*)
이다. 생각해보면size, fwd, bck, prev\_size
를 모두 담으려면 저 사이즈가 필요하다.
In-use Chunk | Free Chunk |
MallocInternals-chunk-inuse.svg | |
MallocInternals-chunk-free.svg | |
mchunkptr
이prev\_size
를 가리키고 있고chunk
구조체가 여기서 부터 시작하기 때문에, 위 그림과 달리 상단의prev\_size
부터 chunk가 시작한다고 보는게 편하다. 위는 하단의prev\_size
까지payload
로 사용하기 때문에 이렇게 표현한 듯.- malloc이 반환하는 주소가 chunk의 시작 지점이 아니라
payload
다. 따라서 반환되는 위치부터 바로 포인터로 접근해 쓸 수 있다. prev\_size
field가 존재하는건 이를 보고 이전 chunk와 merge하기 위해.
flags
A : NON\_MAIN\_ARENA (0x04)
0
이면 이 chunk는 main arena와 main heap에서 왔다는 것을 의미한다. 1
이면 이 chunk는 mmap’d memory에서 왔다는 것을 의미한다. 이 경우 chunk’s address를 이용해 heap_info의 위치를 계산할 수 있다.
M : IS\_MMAPPED (0x02)
chunk 자체가 단일 mmap()
호출로 할당된 영역 전체일 때 set된다. 따라서 어떤 heap의 일부가 아니라, c mmap()
으로 할당된 영역 그 자체가 모두 chunk임을 의미한다.
P : PREV\_INUSE (0x01)
실제로는 Previous chunk should not be considered a candidate for coalescing. 를 의미한다. 그래서 chunk가 사용되고 있는 경우 / fastbins에 들어가는 chunk일 경우 set된다.
Arena
arena는 하나 또는 여러 heap들의 reference나, heap chunk들의 linked lists(“bins”)를 포함하고 있는구조(structure)를 말한다.
arena는 원래 한 번 크게 할당한 다음 이를 직접 나누어 부분 부분 접근하는 용도로 사용하는 크고 연속적인 메모리 영역을 의미한다.
1
2
3
4
char \*arena = (HUGE\_SIZE);
...
char \*p = arena + offset;
- main_arena는application’s initial heap만 사용한다.
- 다른 arena는 mmap’d heap을 사용한다.
- main_arena를 제외한 arenas는 additional arenas를 가리키는
next
pointer를 가지고 있다. - arenas는 “top” chunk를 가리키는 포인터를 가지고 있다. * top chunk는 아직 할당하지 않은, 힙의 최상단에 있는 chunk를 의미한다.
Heaps and Arenas ( Except main_arena ) |
MallocInternals-heaps.svg |
* main_arena는 heap_info가 없으며 arena 구조 자체도 heap에 존재하는게 아니라 libc.so의 data segment에 존재한다.
bins
arena에는 free’d chunks를 빠르게 재할당할 수 있도록 free’d chunk를 종류 별로 가리키는 포인터의 리스트를 가지고 있는데, 이를 “bins”라고 한다.
Note ) chunk는 항상 (fast)bins[]
바로 다음(리스트의 왼쪽)에 추가된다. fastbins[]
는 LIFO 이므로 맨 왼쪽 chunk가 먼저 serve되며, bins[]
는 FIFO 이므로 맨 오른쪽 chunk가 먼저 serve된다. 따라서 bins[].bk
번지의 chunk가 다음 반환 chunk다.
Free, Unsorted, Small, and Large Bin Chains |
MallocInternals-bins.svg |
fastbin
같은 크기를 기준으로 linked list로 연결된 일정 크기 이하의 작은 chunks를 의미한다.
single-linked list구조로 연결되었기 때문에, stack과 같은LIFO구조다.
인접 chunk와 consolidate 되지 않는다!!!!(P
flag) 그리고, 시스템에 리턴되지 않는다. 사용하면 fragmentation이 증가하지만, 같은 크기에 대한 할당 요청을 빠르게 처리할 수 있게 된다.
mallopt(M\_MXFAST, value);
를 지정해 fastbins를 사용할 size limit를 설정할 수 있다. default value는 64\*sizeof(size\_t)/4
이기 때문에 32bit os의 경우 mchunkptr.size == 0x40
까지 fastbin으로 분류된다. 0-80\*sizeof(size\_t)/4
까지 지정 가능하다. 0
이면 fast bins 비활성화.
Unsorted bin
top chunk가 아닐 경우, chunk가 free되면 바로 계산되어 small bin / large bin으로 들어가는게 아니라, 일단 Unsorted bin으로 들어가서 재할당을 기다리게 된다. 따라서 unsorted bin이 small bin / large bin에 chunk를 추가하는 유일한 지점이다. unsorted bin == 단일 chunk라고 생각해서는 안된다. unsorted bin도 linked-list이기 때문에, 여러 chunk가 연결될 수 있다. small bin chunk가 unsorted bin에 존재하는 상태에서 또 다른 small bin chunk가 free되는 경우 이를 계속 unsorted bin에 추가하다가, fastbin같은 다른 size의 chunk가 free될 때 small bin으로 옮긴다.
* small bin으로 분류되지만 다른 size를 가진 chunk인 경우에도 unsorted bin에 추가한다.
Small bin
MINSIZE < sizeof(chunk) < 512
인 경우. 따라서 fastbin size를 포함한다. 각 bin마다 chunk가 동일한 크기를 가진다. fastbin과의 차이점은 P
flag가 없어 일단 chunk가 small bin에 연결되면 인접 chunk와 합치려고 한다는 점, 그리고 circular doubly linked list 구조라는 점이다. 인접 chunk와 모두 결합하기 때문에 small bin’s chunk는 인접 chunk가 없다. * fast, unsorted, in-use chunk와 인접해있는 경우는 결합하지 않기 때문에 인접 chunk가 있을 수 있다.
chunk 반환 순서 smallbin.fd
도 fastbin.fd
와 동일하게 제일 최근에 반환된 chunk를 가리키고 있다. 그러나 fastbin이 제일 최근에 반환된 chunk를 반환하는 LIFO 구조인 반면, smallbin은FIFO구조다. 따라서 리스트에 제일 오래 있었던 chunk를 반환하며 이는 리스트의 맨 마지막에 있는 chunk이므로 smallbin.bk
가 가리키는 chunk다.
Large bin
각 bin마다 chunk가 일정 범위의 크기를 가진다. chunk가 크다면 여기로 들어온다. circular doubly linked list구조이며, 요청에 가장 알맞는 크기의 chunk를 찾는 작업이 필요하기 때문에 이를 위해 fd\_nextsize/bk\_nextsize
라는 추가적인 circular doubly linked list를 사용한다. 요청을 처리하기 위해 chunk가 나뉠 수도 있다.
| | | — | | Large Bin “Next Size” Chains | | MallocInternals-large-bins.svg | * 요청 사이즈를 만족하는 chunk가 여러 개 있을 경우, 보통 두 번째가 선택되는데 이는 첫 번째 chunk를 선택하면 \*\*\_nextsize
포인터를 다시 이어야 해서 번거롭기 때문이다.
multi-thread and arenas
기본적으로는 thread 마다 각각의 heap arena를 가지고 있으며 main thread가 사용하는 arena는 main_arena다. 그러나 무조건 thread의 수 만큼 arena가 존재하는 것은 아니며 현재 시스템의 core 수, os bit에 따라 가질 수 있는 최대 arena 수가 결정되기 때문에 thread가 많아질 경우 여러 thread가 arena를 공유할 수도 있다. 그래서 access control을 위해 각각의 arena는 mutex를 가지고 있다. * 단, fastbin에 접근하는 것과 같은 atomic operations는 arena lock을 필요로 하지 않는다.
참고
https://sourceware.org/glibc/wiki/MallocInternals
https://sploitfun.wordpress.com/2015/02/10/understanding-glibc-malloc