heap(2) - glibc malloc(1) (feat. Arena)

이제 본격적으로 메모리 할당 및 해제하는 동작 과정과 할당되었을 때 또는 해제되었을 떄 어떠한 구조를 가지는지 등등 상세히 알아보도록 하겠다.

 

처음에 전체적인 동작 과정을 먼저 설명하고 싶으나 동작 과정을 이해하기 위해 Arena, bins, Chunk 등등.. 모르는 용어가 많이 나와서 각각에 대한 개념을 먼저 설명한 뒤에 전체적인 동작 과정을 설명하기로 하겠다.

 

 

---

0. Overview

 

이전에 다양한 종류의 Dynamic Memory Allocator를 잠깐 간략하게 설명하고 넘어갔을 것이다.

이처럼 힙이 작동하는 방식은 플랫폼(Windows, Linux, MacOS.. 등등)과 구현에 따라 다르며 다양한 힙 구현이 존재한다.

 

따라서, 모든 Memory Allocator를 설명을 할 수는 없으므로 이전에 Linux에서 사용하였고 많은 malloc의 base가 되는 dlmalloc에서 멀티 쓰레딩 기능이 추가된 ptmalloc2를 다루고자 한다.

 

지금부터 소개되는 내용은 현재 Linux기본 Memory Allocator인 ptmalloc2(glibc 2.23)과 C / C++프로그램의 힙 할당 작동 방식을 중심으로 다루도록 하겠다.. (참고로 현재 2020-02-01에 릴리즈된 glibc 2.31까지 나옴)

---

ptmalloc2란?

기존에 리눅스에서 기본 Memory Allocator인 Dong Lea가 만든 dlmalloc을 사용하였지만 멀티 쓰레드 환경을 고려하게 되어 현재 기본 Memory Allocator는 ptmalloc2이다.

 

ptmalloc2(glibc 2.23 ~ 2.28에서 구현됨)는 dlmalloc코드를 기반으로 하며 여기에 멀티 쓰레딩 기능을 지원한다. 기존에 dlmalloc에서는 동일한 시간에 2개의 스레드가 메모리 할당 요청을 할 경우 freelist data structures는 사용가능한 스레드에 둘러싸인 상태로 공유되어 오로지 하나의 스레드만 critical section(임계영역)에 들어갈 수 있으므로 멀티 스레드 환경에 적합하지 않는다(많은 스레드를 사용하는 응용 프로그램에서 성능 문제 발생). 하지만, ptmalloc2에서는 동일한 시간에 2개의 스레드가 메모리 할당 요청을 할 경우 메모리는 각각의 스레드에게 분배된 힙 영역을 일정하게 유지시키고 힙을 유지하기 위한 freelist data structures 또한 분배되어 있기 때문에 즉시 할당가능하다.

 

---

1. Arena

위에서 잠깐 설명했듯이 ptmalloc2 이전에(dlmalloc)는 많은 쓰레드를 요구하는 애플리케이션에 멀티 쓰레딩 기능을 지원하지 않아 심각한 성능 문제가 발생한다고 하였다. 이에 따라 ptmalloc2 Memory Allocator는 Arena라는 개념을 도입하여 멀티 쓰레드 응용 프로그램을 효율적으로 처리하게 된다.

 

1.1. Arena란?

각각의 스레드가 서로 간섭하지 않고 서로 다른 메모리 영역에서 액세스할 수 있게 도와주는 힙 영역이다. 단일 스레드 프로세스인 경우 하나의 Arena를 가지지만 멀티 스레드 프로세스인 경우 하나 이상의 Arena를 가지므로 서로 다른 Arena안에 존재하는 각각의 스레드는 정지하지 않고 힙 작업을 수행할 수 있다.

 

그럼 각각의 스레드마다 자신만의 Arena를 가진다고 생각할 수 있는데 이는 잘못된 생각이다. 모든 스레드마다 각각의 Arena를 할당하게 해준다면 자원 고갈이 심각할 것이므로 32bit 또는 64bit System과 시스템의 Core의 갯수에 따라 Arena의 개수가 제한되어 있다.

 

[glibc 2.23 malloc.c line 1176]

#define NARENAS_FROM_NCORES(n) ((n) * (sizeof (long) == 4 ? 2 : 8))

// 32bit system인 경우 long타입 크기가 4bytes이므로 (core 갯수 * 4)만큼 arena를 가짐
// 64bit system인 경우 long타입 크기가 8bytes이므로 (core 갯수 * 8)만큼 arena를 가짐

제한된 크기만큼 Arena의 개수가 증가하여 더이상 늘릴 수 없다면 여러 스레드가 하나의 Arena안에서 공유하며 힙 작업을 수행해야 한다. 따라서, 각각의 Arena안에서 여러 개의 스레드가 존재할 수 있으며 뮤텍스를 사용하여 액세스를 제어한다.

 

만일, 새로운 스레드가 생성되면 다른 스레드가 사용하지 않는 Arena를 찾아 해당 스레드에 Arena를 연결하며, 사용 가능한 모든 Arena가 다른 스레드에서 사용중이면 새로운 Arena를 만들고 제한된 Arena의 갯수에 도달하면 여러 스레드가 하나의 Arena에서 공유하게 된다.

 

잠깐 정리)

• Arena는 멀티 쓰레드 환경을 지원하기 위해 도입된 개념

• 멀티 스레드 프로세스인 경우 하나 이상의 Arena를 가짐

• 서로 다른 Arena는 서로 간섭을 받지 않고 힙 작업 수행 가능

• 하나의 Arena에서 여러 개의 쓰레드가 존재할 수 있으며 뮤텍스를 통해 충돌 방지

• 자원 고갈의 방지를 위해 시스템 환경에 따라 Arena의 갯수가 제한

 

1.2 Arena의 종류

Arena는 크게 "Main Arena"와 "Main Arena를 제외한 다른 Arena"로 나뉜다. (편하게 Sub Arena라고 하자)

 

1) Main Arena

메인 쓰레드로써 생성되었기 때문에 Main Arena로 부른다.

단일 스레드용 프로그램을 위해 존재하며 malloc()과 같은 힙 작업을 요구

하는 코드를 실행하지 않아도 기본적으로 132KB크기의 initial heap을 가진다.

 

Main Arena가 감당할 수 있을 만큼의 동적 할당 요구가 들어오면 sbrk()를 통해 heap segment를 확장한다. (즉, Main Arena 는 start_brk와 brk사이의 공간에 존재

 

너무 큰 사이즈의 동적 할당 요구가 들어오면 mmap()을 통해 새로운 힙 메모리를 할당해준다.

 

Main Arena는 하나의 힙만 가질 수 있으며 heap_info구조체를 가질 수 없다. 이 때, 하나의 힙은 여러 개의 chunk로 나누어지며 각 chunk는 각각의 header를 갖는다.

 

 

 

 

2) Sub Arena

새로운 스레드가 생성되어 힙 작업을 수행하고자 할 때 다른 스레드를 기다리는 것을 줄이기 위해 새로운 Arena를 생성하게

되는데 이를 Sub Arena라고 부르며 sbrk를 사용하는 Main Arena 와 달리 mmap()을 통해 새로운 힙 메모리에 할당받으며 mprotect()를 사용하여 확장한다.

 

또한, Sub Arena는 Main Arena와 달리 여러 개의 서브 힙과 heap_info구조체를 가질 수 있다.

 

 

 

 

 

 

+) 참고

brk()

• 프로세스의 data segment에 할당 메모리량을 변경하기 위해 사용

• program break 위치를 이동시킴으로써 메모리를 획득하며 성공 시 0, 실패 시 -1을 반환

• 참고로 break는 BSS영역 끝의 다음 위치에 존재함

• ex) brk(주소 값) : 요청한 주소 값까지 메모리 할당

sbrk()

• sbrk의 기능은 내부적으로 brk system call을 사용

• brk와 동일하게 작업하며 성공 시 세그먼트 break주소를 반환하며 실패 시 -1을 반환

• ex) sbrk(메모리 크기) : 이전 세그먼트부터 메모리 크기만큼 메모리 할당

mmap()

• 새로운 메모리를 할당하고 호출한 프로세스에서 해당 메모리를 사용

 

1.3 Arena 구조

1) 전체적인 구조

출처 : http://core-analyzer.sourceforge.net/index_files/Page335.html

 

 

2) 소스 코드 분석

참고 링크)

• https://elixir.bootlin.com/glibc/glibc-2.23/source/malloc/malloc.c

• https://elixir.bootlin.com/glibc/glibc-2.23/source/malloc/arena.c

 

main_arena

static struct malloc_state main_arena =
{
  .mutex = _LIBC_LOCK_INITIALIZER,
  .next = &main_arena,
  .attached_threads = 1
};

[glibc 2.23 malloc.c / line 1761 - 1766]

 

malloc_state (Arena Header)

struct malloc_state
{
  /* Serialize access.  */
  mutex_t mutex;

  /* Flags (formerly in max_fast).  */
  int flags;

  /* Fastbins */
  mfastbinptr fastbinsY[NFASTBINS];

  /* Base of the topmost chunk -- not otherwise kept in a bin */
  mchunkptr top;

  /* The remainder from the most recent split of a small request */
  mchunkptr last_remainder;

  /* Normal bins packed as described above */
  mchunkptr bins[NBINS * 2 - 2];

  /* Bitmap of bins */
  unsigned int binmap[BINMAPSIZE];

  /* Linked list */
  struct malloc_state *next;

  /* Linked list for free arenas.  Access to this field is serialized
     by free_list_lock in arena.c.  */
  struct malloc_state *next_free;

  /* Number of threads attached to this arena.  0 if the arena is on
     the free list.  Access to this field is serialized by
     free_list_lock in arena.c.  */
  INTERNAL_SIZE_T attached_threads;

  /* Memory allocated from the system in this arena.  */
  INTERNAL_SIZE_T system_mem;
  INTERNAL_SIZE_T max_system_mem;
};

[glibc 2.23 malloc.c / line 1686 - 1724]

• bin, top chunk, last remainder chunk 등에 대한 정보를 가짐

• 모든 Arena는 단 하나의 Areana Header를 가짐

 

heap_info (Heap Header)

typedef struct _heap_info
{
  mstate ar_ptr; /* Arena for this heap. */
  struct _heap_info *prev; /* Previous heap. */
  size_t size;   /* Current size in bytes. */
  size_t mprotect_size; /* Size in bytes that has been mprotected
                           PROT_READ|PROT_WRITE.  */
  /* Make sure the following data is properly aligned, particularly
     that sizeof (heap_info) + 2 * SIZE_SZ is a multiple of
     MALLOC_ALIGNMENT. */
  char pad[-6 * SIZE_SZ & MALLOC_ALIGN_MASK];
} heap_info;

[glibc 2.23 arena.c / line 48 - 59]

• 각각의 힙마다 Header를 포함

• 힙 영역의 공간이 부족해지는 경우 Arena에 새로운 힙(인접하지 않은 영역)을 할당해줘야 하기 때문에 여러 개의 힙이 필요

 

malloc_chunk (Chunk Header)

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

[glibc 2.23 malloc.c / line 1111 - 1122]

• 각각의 Chunk마다 Header를 포함

• 사용자의 요청으로 할당된 힙에서 여러 개의 Chunk로 나뉨

• 각 Chunk들은 double linked list로 구성

• Chunk에 관련한 내용은 다음에 다시 자세하게 설명

 

---

2. Example

 

2.1 환경 구성

• OS : ubuntu 16.03

• glibc 2.23

• debugger : gef

원래는 peda-gdb를 사용하였으나 syscall(brk, mmap)에 대한 backtrace를 보는데 편리하여 gef디버거를 사용하였다.

(근데 아레나 구조 보는거는 pwndbg가 더 편한거 같기도.. 모르겠다ㅎㅎㅎ.. 3개 다 써 보니깐 각자 장단점 있음)

 

추가로 분석하기에 앞서 좀 디버깅할 때 더 편리하게 힙을 분석할 수 있도록 heap관련 plugin을 설치해준다.

참고)

https://github.com/scwuaptx/Pwngdb

(설치 방법 및 사용 방법은 링크 들어가면 확인할 수 있음, 이거 원래 peda용이라고 되어있는데 gef에도 모듈포함되는듯 ㄷㄷ)

 

2.2 실습 코드

#include<stdio.h>
#include<stdlib.h>
#include<pthread.h>
#include<unistd.h>

#define NTHREAD 4

void* thread_func(void*);

int main(){

	
	int *p;
	int i, status;
	int t_id[NTHREAD];
	pthread_t t1[NTHREAD];

	p = (int*)malloc(sizeof(int)*1000);
	
	*p = 1000;

	for(i=0;i<NTHREAD;i++){
		t_id[i] = pthread_create(&t1[i], NULL, thread_func, (void*)i);
	}
	
	for(i=0;i<NTHREAD;i++){
		pthread_join(t1[i], (void**)&status);
	}

	free(p);
	return 0;
	
}

void* thread_func(void* data){
	
	pid_t pid;
	pthread_t tid;
	
	pid = getpid();
	tid = pthread_self();
	
	int *p = (int*)malloc(sizeof(int)*1000);
	*p = (int)data*1000;
	
	printf("\n#%d Creation Thread!!\n", (int*)data);
	printf("pid : %u, tid : %x\n", (unsigned int)pid, (unsigned int)tid);
	printf("# Thread malloc data : %d\n", *p);

	free(p);
}

 

1) main함수 - malloc함수 호출 전

• 해당 Arena는 Main Arena로써 메인 쓰레드에 의해 생성되며 malloc과 같은 힙 작업을 하지 않아도 기본적으로 존재

• Sub Arena가 존재하지 않으므로 다음 Arena는 자기 자신을 가리키고 있음

• Main Arena는 heap에 존재하지 않으며 libc-2.23.so의 데이터 세그먼트에 존재함을 알 수 있음

• 또한, 아직 heap영역이 할당되지 않음을 알 수 있음

 

2) main함수 - malloc함수 호출

• 메인 함수에서 malloc함수를 호출하기 직전에 $catch syscall brk, mmap에 체크 포인트를 걸고 실행해보자

• 힙 영역을 확장하기 위해 syscall brk가 사용됨을 확인할 수 있음

• malloc이후에 heap영역 추가됨

• Main Arena의 malloc_state구조체의 값이 바뀐 것을 알 수 있음

 

3) Thread생성 후 Malloc

• brk가 아닌 mmap을 통해 메모리 할당을 받음

• Sub Arena가 하나 생성됨

• 위 그림은 Main Arena의 malloc_state구조체이며 next포인터의 값이 바뀐 것을 알 수 있음

• next를 따라가다 보면 Sub Arena의 malloc_state구조체가 나오며 다시 next포인터는 Main Arena를 가리킴

 

4) 중간점검

• 현재까지 메인 스레드 포함하여 총 5개의 스레드가 존재

• 한 개의 스레드를 제외한 나머지 스레드들(메인 스레드 포함)은 각각 Arena를 가지고 있음

• 각 스레드별 힙 영역(빨간색 박스)과 스택 영역(노란색 박스)이 생긴 것을 확인

• Arena끼리 서로 Linked List로 연결됨

• Main Arena에는 heap_info구조체가 존재하지 않음

• 모든 Sub Arena 하나의 heap_info구조체를 가지고 있음

• 노란색 박스 → heap_info, 빨간색 박스 → malloc_state

 

5) 저장된 데이터 위치 확인

5-1) 메인 함수에서 동적 할당 후 저장된 데이터 위치

 

5-2) 각 스레드에서 동적 할당 후 저장된 데이터 위치

각 아레나의 malloc_state구조체 다음에 확인할 수 있음

• 잉.. 그 사이 스레드 하나 사라졌다..(ㅠㅠ)

• Main Arena인 경우 Sub Arena와 달리 malloc_state구조체 다음에 연속적으로 위치하지 않음

• Sub Arena인 경우 서브 힙이 생기지 않는 한 malloc_state구조체 다음에 연속적으로 위치하여 데이터가 저장

• 참고로 마지막에 있는 청크는 데이터가 없고 주소 값이 존재 → free된거

 

6) free 이후

• 스레드가 모두 종료되고 free를 통해 동적 할당받은 메모리를 반환해도 아레나는 아직 살아있음(메인 스레드도 free통해 반환됨)

 

---

3. 참고 자료

1) 참고 자료

• https://sourceware.org/glibc/wiki/MallocInternals

• https://www.lazenca.net/pages/viewpage.action?pageId=1147929

• https://tribal1012.tistory.com/141?category=658553

• https://wogh8732.tistory.com/179?category=699165

• https://azeria-labs.com/heap-exploitation-part-1-understanding-the-glibc-heap-implementation/

 

2) ptmalloc2뿐만 아니라 windows, macOS Memory Allocator내용도 간략히 잘 설명되어 있음

• http://core-analyzer.sourceforge.net/index_files/Page335.html

 

3) 다른 버젼의 glibc로 링킹하여 컴파일하기

• https://wiki.kldp.org/HOWTO/html/Glibc2/Glibc2-HOWTO-5.html

• https://d4m0n.tistory.com/119

• https://ftp.gnu.org/gnu/glibc/

 

(아직 안해봤는데.. 나중에 한번 시도해바야게따)

 

---

4. 결론

위에서 설명하다가 아니면 디버깅하다보면 Chunk, Top Chunk, bin도 나오는데 일단은 건너띄고 ptmalloc2와 Arena를 중점적으로 다뤘다.

 

구글링하면서 많은 자료를 참조하면서 이해했는데 혹여나 틀린 내용이 있으면 답변주세요ㅠㅠ