[System_Hacking] ptmalloc2 allocator

ptmalloc2는 리눅스 GLIBC에서 사용하는 메모리 할당자임. (메모리 할당자는 os따라 다른데, ptmalloc2는 리눅스 유저 모드에서 주로 이용하는 할당자이다.)

 

ptmalloc2의 경우 glibc2.23에서 2.26으로 바뀌면서 tcache개념이 생겨 동작 방식이 약간 달라졌다.

 

$ wget https://ftp.gnu.org/gnu/glibc/glibc-2.23.tar.xz
$ tar -xvf glibc-2.23.tar.xz

위 명령어를 통해 GLIBC코드를 받아주자.

 

 

 

*청크 구조

ptmalloc2에서 힙 청크들은 아래  malloc_chunk구조체를 사용한다. ↓ 

 

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

 

해당 구조체에는 다음과 같은 멤버들이 존재한다. (이전 드림핵 로드맵에서 봤던 청크의 구조 말하는 거 맞다.)

 

prev_size -> 연결 리스트에서 이전 힙 청크가 해제 상태일 경우 해당 청크의 크기를 저장한다. (해제되지 않았다면 이전 힙 청크의 데이터 영역으로 이용된다.)

 

size -> 현재 청크(자신)의 크기가 저장되는 곳이며, 청크는 0x10단위로 할당되므로 마지막 4비트는 무의미 -> 하위 3비트는 플래그로 이용된다.

 

Flags(P, M, N) ->

PREV_INUSE(P) : 이전 힙 청크가 해제된 경우 0, 해제되지 않은 경우 1

IS_MMAPPED(M) : 현재 청크가 mmap시스템 콜을 이용해 할당된 경우 설정된다.

NON_MAIN_ARENA(N) : 현재 청크가 main_arena에서 관리하지 않을 경우에 설정된다.

 

FD(ForwarD pointer) -> 동일한 bin에 존재하는 다음 힙 청크의 주소를 저장한다. (여기서 다음 힙 청크의 주소란, 데이터 영역부터의 주소이다.) bin들은 FD와 BK를 이용해 연결 리스트를 형성한다. (FD는 데이터 영역과 겹친다. 따라서 해제된 청크에만 있음)

 

(*여기서 다음 힙 청크란, 먼저 할당된 청크를 말한다. 단일 연결 리스트의 경우 가장 처음 할당된 청크의 FD값은 NULL이다.)

 

BK(BacKward pointer) -> 동일한 bin에서 이전 청크를 가리킨다. 여기서 이전 청크란, 현재 청크 기준, 이후에 할당된 청크를 말한다. 단일 연결 리스트 구조의 경우 BK는 이용되지 않으므로 NULL이다.

 

fd_nextsize -> large bin에서 사용하는 포인터로, 현재 힙 청크의 크기보다 작은 힙 청크의 주소를 가리킨다. (large bin은 다른 bin처럼 정확히 해당 크기인 청크들끼리 모여있는 게 아니라, 범위 단위로 묶이기 때문)

 

bk_nextsize -> large bin에서 사용하는 포인터로, 현재 힙 청크의 크기보다 큰 힙 청크의 주소를 가리킨다. 

 

(*참고로, 하나의 large bin안에서 청크들은 크기 기준 내림차순으로 정렬되어 있으며, 이중 연결 리스트 방식이다.)

 

 

 

 

*청크 종류

 

Allocator Chunk -> 동적 메모리 할당 함수들(malloc, calloc)을 통해 할당된 청크.

 

Free Chunk -> 메모리 해제 함수를 통해 해제된 청크.

 

Top Chunk -> 힙 메모리의 마지막에 위치한 청크, 힙 메모리 영역의 끝..이라고 하는데 보면 다른 청크들 빼면 모두 탑청크가 자리 차지하고 있음. 청크가 할당됐다가 해제된 경우 탑청크랑 병합되지 않는 이상 bin에 별개로 존재하기 때문.. 그냥 가장 아래 있는 가장 큰(보편적으로) 청크덩어리라고 생각하면 되고, 할당요청 받았을 때 적당한 사이즈의 Free Chunk가 없으면 탑청크를 쪼개 가져가게 됨.

 

Last Remainder Chunk -> 작은 사이즈의 할당 요청이 들어왔을 때 Free Chunk가 쪼개지고 남은 청크. 연속된 작은 사이즈의 할당 요청이 들어왔을 때, 비슷한 주소에 힙 청크가 할당되도록 하기 위해(할당의 지역성 유지) 사용된다.

 

 

 

 

*bin 종류

 

해제된 청크는 bin이라고 하는 free list구조체를 통해 관리된다. freelist는 메모리 관리의 효율성을 위해 할당되지 않은 영역을 관리하는 연결 리스트이다.

 

ptmalloc2에는 128개의 bin이 있다. 62개는 smallbin, 63개는 largebin, 1개는 unsortedbin이다. (2개는 안 쓴다.)

0번과 127번이 not used, 1번이 unsortedbin, 2번 ~ 63번이 smallbin, 64번 ~ 126번이 largebin이다. 

 

청크 관리에는 LIFO, FIFO, address-ordered 의 3가지 방법이 있다.

(LIFO : 속도 빠름/ 파편화 심함, FIFO : 중간, address-ordered : 느림/ 파편화 적음)

 

그리고 연결 방식에는 단일 연결 리스트, 이중 연결 리스트, 원형 이중 연결 리스트가 있는데, fd와 bk로 리스트들이 묶이는 방식을 말하는거다. 

(참고로 이중 연결 리스트의 경우 청크를 추가하거나 꺼낼 때 연결고리를 끊는 unlink과정이 필요하다. 단일은 불필요)

 

마지막으로 병합 대상 여부는 메모리상 인접한 청크가 같은 bin에 들어있으면 병합되는지 여부를 말한다. 참고로 병합되었을 경우 병합된 사이즈를 저장하는 bin으로 옮겨 저장됨.

 

그리고 참고로 청크의 size는 헤더 크기를 포함한 값이다.

 

 

Fastbin -> 단일 연결 리스트, LIFO, 병합 대상X, 크기별 구분

 

16 ~ 64바이트(32비트), 32 ~ 128(64비트)의 freechunk을 저장한다.

 

사실 64비트를 기준으로 32바이트 이상 ~ 176바이트 이하의 청크들이 보관된다. -> 16바이트 단위로 10개의 fastbin존재 -> 리눅스는 이 중 작은 크기부터 7개만 이용함. -> 사실상 리눅스에서는 32바이트 이상 ~ 128바이트 이하 청크들을 fastbin에 저장하는 셈.

 

 

 

Unsortedbin -> 원형 이중 연결 리스트, 내부 정렬X

 

분류되지 않은 청크들을 보관하는 bin이다. fastbin에 들어가지 않는 청크는 해제 시 크기 불문하고 여기 들어간다.

 

ptmalloc2는 할당 요청이 들어왔을 경우, 해당 사이즈에 적당한 free chunk가 있는지 탐색하는 과정을 거친다.

 

smallbin크기에 해당하는 할당 요청이 들어왔을 경우, fastbin, smallbin탐색 후 -> unsortedbin을 탐색한다.

largebin크기에 해당하는 할당 요청이 들어왔을 경우, unsortedbin을 먼저 탐색하고, 여기서 탐색된 청크는 크기에 따라 적절한 bin으로 분류된다.

 

 

 

Smallbin -> 원형 이중 연결 리스트, FIFO, 병합 대상O, 크기별 구분

 

32바이트 ~ 1024바이트 미만(64비트), ~512바이트 미만(32비트)

 

smallbin의 경우 smallbin[ 0 ]이 32바이트짜리를 보관, smallbin[61]이 1008바이트를 보관하는 형태이다. (d == 16 인 등차수열 느낌)

 

 

Largebin -> 이중 연결 리스트, 병합 대상O, 크기별 구분 + 내림차순 정렬

 

512바이트 이상(32비트), 1024바이트 이상(64비트)

 

이친구는 굉장히 큰 청크도 보관할 수 있어야 하기 때문에, 각 bin들이 특정 값이 아닌, 일정 범위의 청크들을 보관한다.

 

각 인덱스마다 범위의 크기는 로그적으로 증가한다. 0번은 1024이상 ~ 1088미만(64), 31번까지는 64단위로 잘리다가, 32번은 3072이상 ~ 3584미만(512) 이런 식으로 62번까지 총 63개가 있다.

 

 

malloc.c를 보면 위와 같은 부분을 볼 수 있는데, 해제된 청크의 크기(sz)를 쉬프트 연산한 결과에 따라 적절한 bin으로 분류하고 있다.

 

예를 들어 어떤 청크의 크기가 3072라면, 3072 >> 6 == 3072 / 64 == 48이고, 48은 48이하이므로, 48 + 48을 한 값인 96, 즉 bin[96]에 보관되는 것이다.

 

(bin[0]은 not used, bin[1]은 unsorted이고, bin[2] ~ bin[63]이 smallbin이니 bin[96]은 largebin으로 치면 largebin[32]인 것이다.)

 

largebin은 위와 같이 청크를 크기 범위별로 나누어 보관하기 때문에, 재할당 요청이 들어오면 ptmalloc2는 그 안에서 크기가 가장 비슷한(best-fit)청크를 꺼내 재할당한다.

 

 

malloc.c를 보면 다음과 같은 주석이 있다.

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

 

 

*main_arena

 

brk시스템 콜을 사용해 할당된 힙을 효율적으로 관리하기 위해 존재하는 malloc_state구조체이다. 이 구조체에는 힙 청크를 관리하기 위한 배열과 포인터들이 선언되어 있다.

 

 

이렇게 생겼다.↑

 

탑청크 크기보다 큰 사이즈의 할당 요청이 들어오면 mmap시스템 콜을 이용해 새로운 페이지를 할당하는데, 이런 방식으로 할당된 힙은 main_arena에서 관리하지 않는다.

 

#include <stdio.h>
#include <malloc.h>
int main()
{
	char *ptr = malloc(0x10);
	free(ptr);
	char *ptr2 = malloc(0x20);
	free(ptr2);
	
}

위 코드를 컴파일 한 뒤 main_arena를 뜯어보자.

 

아 그런데 나느 glibc버전이 2.27이다. 2.26부터 tcache가 새롭게 도입되어 위와 같은 코드에서 해제한 청크는 fastbin으로 가지 않고 tcache로 가게 된다. fastbin에 연결하기 위해서는 tcache7개를 먼저 다 채워야 하기 때문에 아래와 같은 코드로 진행하였다.

 

#include <stdio.h>
#include <malloc.h>
int main()
{
        char *ptr2 = malloc(0x20);
        char *ptr3 = malloc(0x20);
        char *ptr4 = malloc(0x20);
        char *ptr5 = malloc(0x20);
        char *ptr6 = malloc(0x20);
        char *ptr7 = malloc(0x20);
        char *ptr8 = malloc(0x20);
        char *ptr9 = malloc(0x20);
        char *ptra = malloc(0x20);
        
        free(ptr2);
        free(ptr3);
        free(ptr4);
        free(ptr5);
        free(ptr6);
        free(ptr7);
        free(ptr8);
        free(ptr9);
        free(ptra);
}

 

gdb로 해당 코드를 마지막 free까지 모두 진행시킨 뒤 청크 상태를 조회해보면 아래와 같다.

 

 

맨 위 청크는 내가 할당해준 게 아니고(쟤는 항상 있다.), fd로 연결된 걸 보면  1 <- 2 <- 3 <- 4 <- 5 <- 6 <- 7 이렇게 7개가 단일 연결 리스트로 이어져 있고(tcache가 단일 연결 리스트), 두개는 fastbin인데, fastbin도 단일 연결 리스트이기 때문에 bk는 전혀 쓰이지 않고, 첫 번째 청크의 fd는 NULL인 위 상태가 된다.

 

위 상태에서 main_arena를 프린트하면 아래와 같은데↓

 

 

위에서 fastbinsY에 보이는 것들은 fd값들을 보여주는 것 같다..

 

fastbinsY는 fastbin에 해당하는 크기로 할당하고 해제된 청크를 수용하기 위한 배열이다. 이 상태에서 해제된 힙 영역과 동일한 크기를 할당 요청하면 fastbinsY를 참조해 할당할 것이다.

 

 

위 상황을 heapinfo로 출력해보면 위와 같다. 우선 tcache에서 파란색 부분은 맨 끝이니 fd에 적힌 값이 아니고 7번째 청크의 데이터 영역 주소를 그냥 보여주는거고, 흰 부분이 이제 fd에 직접적으로 적혀서 연결되어 있는 것이다.

 

0x20이라는 동일한 사이즈(청크 크기는 0x30)를 7회 이상 연속적으로 해제하였으므로 tcache_entry[1]의 일곱 자리가 가득 찬 것을 볼 수 있다. 앞의 (0x30)은 해당 tcache가 어느 사이즈의 청크를 보관중인지 보여주는 것이다.

 

그리고 fastbin들을 쭉 보여주는데, 내가 해제한 청크들의 크기는 모두 0x30이므로 위와 같이 표현된다. fastbin에 들어있는 청크의 수는 두 개인데, 마찬가지로 파란색은 fd에 적힌 값이 아니라, 마지막에 연결된 청크의 데이터 부분 주소이고, 흰 부분들이 실질적으로 fd에 적힌 값들이다.

 

(fastbin은 0x0까지 표시해줬으면서 tcache는 왜 안해준건지는 모른다.. 아무튼 둘다 단일 연결 리스트라서 위와 같이 연결되어 있음)

 

 

 

*Fastbin: 단일 연결 리스트, LIFO, 병합 대상X, 크기별 구분

작은 크기의 힙 청크를 관리할 때 사용하는 bin이다. 단일 연결 리스트(unlink과정 불필요) + 메모리 검증 루틴이 적음 -> 다른 bin들보다 할당/해제 속도가 빠르다.

 

Last In First Out방식으로 청크들을 처리하며, 인접한 청크들이 병합되지 않는다.

 

  if ((unsigned long)(size) <= (unsigned long)(get_max_fast ())

#if TRIM_FASTBINS
      /*
	If TRIM_FASTBINS set, don't place chunks
	bordering top into fastbins
      */
      && (chunk_at_offset(p, size) != av->top)
#endif
      ) {

    if (__builtin_expect (chunk_at_offset (p, size)->size <= 2 * SIZE_SZ, 0)
	|| __builtin_expect (chunksize (chunk_at_offset (p, size))
			     >= av->system_mem, 0))
      {
	/* We might not have a lock at this point and concurrent modifications
	   of system_mem might have let to a false positive.  Redo the test
	   after getting the lock.  */
	if (have_lock
	    || ({ assert (locked == 0);
		  mutex_lock(&av->mutex);
		  locked = 1;
		  chunk_at_offset (p, size)->size <= 2 * SIZE_SZ
		    || chunksize (chunk_at_offset (p, size)) >= av->system_mem;
	      }))
	  {
	    errstr = "free(): invalid next size (fast)";
	    goto errout;
	  }
	if (! have_lock)
	  {
	    (void)mutex_unlock(&av->mutex);
	    locked = 0;
	  }
      }

    free_perturb (chunk2mem(p), size - 2 * SIZE_SZ);

    set_fastchunks(av);
    unsigned int idx = fastbin_index(size);
    fb = &fastbin (av, idx);

    /* Atomically link P to its fastbin: P->FD = *FB; *FB = P;  */
    mchunkptr old = *fb, old2;
    unsigned int old_idx = ~0u;
    do
      {
	/* Check that the top of the bin is not the record we are going to add
	   (i.e., double free).  */
	if (__builtin_expect (old == p, 0))
	  {
	    errstr = "double free or corruption (fasttop)";
	    goto errout;
	  }

 

이 코드도 malloc.c에 있는 코드인데, free함수에서 fastbin청크를 처리하는 부분이다.