Post

(glibc) malloc - 1

Posted Updated
By umbum 11 min read
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 ChunkFree 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

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

Security, System Exploit
This post is licensed under CC BY 4.0 by the author.