ptmalloc2 - Memory Allocator in Linux

 

운영체제에서 메모리 공석을 최대한 줄이고 효율성을 높이는 방식으로 공간을 할당해 주는 할당자를 Memory Allocator라고 한다.

 

리눅스에서는 이러한 메모리 할당자 역할을 ptmalloc2가 해준다. ptmalloc2는 glibc에 구현되어 있다.

동적 할당시 메모리를 관리해주는 리눅스의 핵심 알고리즘이며, 메모리 낭비 방지, 빠른 메모리 재사용, 메모리 단편화 방지를 목적으로 한다.

 

내부 단편화 vs 외부 단편화

 

chunk의 크기가 여유가 되지만, 다른 프로세스가 사용할 수 없어 낭비되는 것을 내부 단편화라고 하고,

연속적이지 않은 공간에 여유 공간이 있어 다른 프로세스가 들어갈 수 없는 현상을 외부 단편화라고 한다.

단편화가 심해질수록 메모리의사용 효율이 떨어진다.

이들 단편화는 정렬(alignment), 병합(coalescence), 분할(split) 등의 방법으로 해결이 가능하다.

 

 

ptmalloc2는 메모리 공간 해제시, 해당 메모리 주소를 tcache 또는 bin이라는 연결 리스트에 저장한다.

이후 특정 크기의 할당 요청시에 해당 크기에 관련된 메모리 저장소를 탐색하여 효율적으로 메모리를 관리한다.

아래에서 ptmalloc2의 객체들에 대해서 설명하도록 하겠다.

 

Chunk

: 덩어리, 헤더와 데이터로 구성되며, 보통 동적 할당한 메모리 공간을 부르는 말이다. malloc_chunk구조체로 구성된다.

 크게 In-Use Chunk, Freed Chunk, Top Chunk, Last Reminder Chunk로 분류된다.

 

<malloc_chunk 구조체>

struct malloc_chunk;
typedef struct malloc_chunk* mchunkptr;

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;
};

chunk header

• prev_size(8bytes) : 인접한 직전 chunk의 크기. 청크 병합시 직전 청크를 찾는데 사용한다.
• size(8bytes) : 현재 chunk(In-Use Chunk)의 크기.
• flags(3bit) : 위 구조체에서 flags항목이 안보일텐데 flags는 size하위 3비트에 담겨있다. chunk는 항상 16바이트 단위로 할당되기 때문에 size의 하위 4비트는 의미 없는 값이 들어있게 되는데, 이중 하위 3비트를 flag값으로 사용한다. 

1. P : PREV_INUSE : 직전 청크가 사용중인지 나타내고, 병합 필요성을 판단한다. 이전 청크가 사용중일시 1, 아니면 0 값을 가진다.
2. M : IS_MMAPED : 현재 청크가 mmap 시스템 콜로 할당된 경우 설정된다.
3. A : NON_MAIN_ARENA :  현재 청크를 main_arena에서 관리하지 않을 경우에 설정된다.

• fd, bk(8bytes) : freed chunk에만 존재하는 영역으로, 각각 연결 리스트에서 다음 청크, 이전 청크를 가리킨다. fd는 forward, bk는 backword의 의미이다. 그러면 제일 먼저 해제된 청크의 bk, 제일 나중에 해제된 청크의 fd는 무슨 값을 가질까? 먼저 전자부터 설명하자면 bin의 head포인터를 가리키고, 후자는 밑에서 설명하겠지만 원형 연결리스트인 bin에서는 다시 bin의 head포인터를 가리키고, 단일 연결 리스트인 bin에서의 경우 NULL값을 가진다.

 

bin

사용이 끝난 청크들(freed chunks)이 저장되는 free list 구조체로, 메모리 낭비를 막고 해제된 청크를 빠르게 재사용 가능하도록 한다.

free -> 사용이 끝난 영역을 freelist에 추가 / alloc -> freelist에 추가된 영역을 리스트에서 제거 후 해당 영역 할당

bin의 종류에도 여러가지가 있는데, chunk의 크기에 따라 다양한 bin에 저장된다.

 

먼저 bin의 구조를 알아보자면 

0. not-used

1. unsorted bin

2. small bin[0]

...

63. small bin[61]

64.large bin[0]

...

126. large bin[62]

127. not-used  이렇게 구성된다.

연결 리스트 구조

fastbin

작은 크기의 청크들을 할당하고 해제할 때 사용하는 bin이다. 32~128bytes(64bit) 크기에 해당하는 청크들이 들어가는 곳이다.

LIFO(후입선출)방식으로, 마지막으로 free된 청크가 가장 먼저 재할당된다. 단일 연결 리스트 구조(bk를 사용하지 않음)를 가지며, bin중에 가장 할당 및 해제 속도가 빠른 특징이 있다. fastbin의 청크들은 서로 병합되지 않는다. 최대 10개의 bin을 관리하지만 7개만 사용한다.

 

• 할당 : 요청된 청크 크기와 부합하는 fastbin의 인덱스를 검색 - 선택된 청크의 fd가 가리키는 청크를 fastbin 연결리스트의 첫번째로 업데이트 -> 청크 할당
• 해제 : 해당 청크의 크기가 fastbin 범위에 속하는지 확인 -> 청크의 크기에 해당하는 fastbin 연결리스트 호출 -> fastbin리스트에 추가(먼저 해제된 청크가 있으면 해제되는 청크의 fd가 먼저 해제된 청크를 가리키게 함)

 

 

smallbin

32bytes ~ 1023bytes 크기의(64비트 기준) chunk들이 해제될 때 unsorted bin을 거쳐 최종적으로 들어가는 영역이다.

FIFO(선입선출)방식이고, 이중 원형 연결 리스트 구조를 가진다. smallbin의 청크들은 서로 인접하게 배치될 수 없다는 특징이 있다.

인접해 위치할 경우 하나의 청크로 병합된다. 같은 smallbin에는 같은 크기의 청크만이 존재한다.

 

• 할당/해제  : 요청한 청크 크기가 smallbin에 해당하는지 검사 후 크기에 해당하는 smallbin 리스트 선택 -> smallbin에 청크 유무 확인 비어있을 경우 : fastbin에 남아있는 청크들을 다 꺼내서 합침 / 비어있지 않을 경우 : smallbin에서 앞에 있는 하나의 청크를 꺼내서 할당 -> 꺼낸 청크 바로 다음의 청크의 prev_inuse를 1로 설정 -> 꺼낸 청크의 fd는 bin head를 가리킴 -> bin head의 bk는 꺼낸 청크를 가리킴(이중 연결 리스트 유지) + smallbin 크기의 청크가 해제될 때는 unsorted bin에서 확인 가능

 

Largebin

이름 그대로 큰 크기의 청크들이 들어가는 bin이다. 1024bytes 이상(64비트 기준)의 청크들이 unsorted bin을 거쳐서 들어간다.

FIFO(선입선출)방식이고, 이중 연형 연결리스트 구조를 가진다. fd_nextsize와 bk_nextsize 로 서로 다른 크기의 청크들을 리스트로 연결한다. 즉, 하나의 largebin에 여러 크기의 청크가 같이 들어올 수 있다. 이 청크들은 크기의 내림차순으로 정렬이 된다. largebin도 마찬가지로 청크가 서로 인접하게 배치될 수 없다. 인접해 위치할 경우 하나의 청크로 병합된다.

 

• 할당/해제  : 요청한 청크 크기가 largebin에 해당하는지 검사 -> largebin의 가장 큰 청크가 요청된 크기보다 큰 지 검사 -> bk_nextsize를 순회하며 요청된 청크의 크기에 부합하는 청크가 있는지 찾기 -> 청크를 꺼낸 뒤 연결리스트를 유지하기 위해 unlink매크로 사용하여 fd, bk, nextsize 전부 조작하여 깨지지 않게 유지 -> 요청한 청크보다 largebin청크가 더 클경우 분할하여 일부를 사용자에게 주고 남은 부분(remainder)는 따로 처리

 

unsortedbin

 

smallbin과 largebin 크기의 청크가 해제될 경우 이후 재할당을 위해 사용되는 bin이다. fastbin외의 모든 청크가 해제 되었을 때 크기를 구분하지 않고 unsortedbin에 보관한다. bin의 개수는 한개이다. FIFO(선입선출)방식이고, 이중 원형 연결리스트 구조이다. 

• unsortedbin에서 크기에 맞는 bin으로 옮겨지는 과정 : smallbin, largebin 크기의 청크가 해제될 경우 unsortedbin에 저장 -> 이후 동일 크기의 청크 할당 요청시 fastbin, small(large)bin에 없음 -> unsortedbin에서 꺼내서 할당 -> unsortedbin에 남아있는 청크가 있으면 크기에 맞는 bin으로 이동
• smallbin크기 할당 요청 -> fastbin, smallbin에서 검색 -> 없으면 unsortedbin에서 검색하여 할당
• largebin크기 할당 요청 -> fastbin, largebin에서 검색 -> 없으면 unsortedbin에서 검색하여 할당

 

Arena

아레나는 bin들의 정보를 모두 담고 있는 객체로, malloc에서 청크들을 관리하는 관리자 공간이다. 각종 bin들과 top chunk를 담고있다.

arena는 멀티스레드 환경에서 공유 자원 사용으로 인한 레이스컨디션 취약점을 방지하기 위해서 lock이라는 방식을 사용한다. 64개의 arena가 모두 lock될시 병목현상이 생기는 단점이 있다. 

 

main arena

메인 아레나는 기본 아레나이다. 싱글 스레드에서 주로 사용한다. libc.so안에 존재한다. 때문에 unsortedbin->fd == main_arena + offset 이런식으로 존재하는데 leak하면 libc_base의 주소를 알아낼 수도 있다.

 

sub arena

서브 아레나는 멀티스레드 환경에서 생성되는 추가 아레나이다. 멀티스레드 환경에서 공유 자원 사용시 발생할 수 있는 성능 문제를 방지하기 위해 존재한다. 

 

tcache bin

아레나의 병목현상을 해소시킬 목적으로 나온 독립적인 청크 저장소이다. 

LIFO(후입선출)방식이고, 32~1040bytes 크기의 청크들이 저장된다. 단일 연결 리스트 구조를 가지고 있다.

한개의 tcache에 들어갈 수 있는 청크의 최대 개수는 7개이다. tcache bin의 범위의 청크를 할당 요청할 경우 제일 먼저 tcache에서 검색하여 청크를 찾는다. tcache 가 꽉차면 청크 크기에 맞는 bin으로 분류가 된다. 작은 단위의 메모리 할당이 필요할 경우 arena를 참조하지 않고 바로 메모리를 할당하기 때문에, 메모리 할당 속도가 빠르다. 또한, 하나의 tcache에는 동일한 크기의 청크들만 들어있으며, tcache의 청크들은 서로 병합되지 않는다.

 

glibc 구버전에서는 tcache bin에 대한 보안 검사가 많이 생략되어 heap exploit의 좋은 도구가 될 수 있다.