About Heap(1)

계기

생각을 해보니 이전에 heap에 관한 기법에 관해서 글을 쓴 적이 있었다.

하지만 메모리 할당,heap,malloc,free,chunk에 관해서 글을 쓴 적은 없었던 것 같다.

이러한 계기로 heap에 관한 글을 쓰게 된다.

 

1. Allocator

리눅스에서는 기본적으로 ptmalloc2라는 Memory Allocator를 사용하고 있다.

하지만 환경에 따라서 다른 Allocator를 사용을 할 수도 있다.

이 글에서는 ptmalloc2에 대해서 다루겠지만,

dllmalloc,jemalloc...등등 여러 가지 라이브러리가 존재한다.

 

ptmalloc2는 멀티 쓰레딩 기능을 지원한다.

멀티 쓰레딩 기능을 지원을 하면서 Arena라는 개념을 도입하여 사용하게 되는데,

이는 프로그램들을 더욱 효율적으로 처리하게 만들었다.

 

2. Arena

Arena는 크게 "Main Arena"와 "Sub Arena"로 나뉘게 된다.

 

Main Arena는 메인 쓰레드로써 생성이 된다.

malloc()과 같은 힙 작업을 하지 않아도 기본적으로 initial heap을 가지고 있으며,

Main Arena가 할당 가능한 크기의 요청이 들어오면 sbrk()를 통해서 heap 영역을 확장을 한다.

하지만 큰 사이즈의 할당 요구가 들어오면 mmap()을 통해 힙 메모리를 새로이 할당해준다.

Sub Arena와는 다르게 하나의 힙만 가질 수 있으며 heap_info 구조체를 가질 수 없다.

(※heap_info와 같은 malloc 데이터 구조체에 대해서는 아래에서 언급하겠다.)

 

Sub Arena는 힙 작업을 새로운 쓰레드를 만들어 수행하고자 할 때

다른 스레드가 대기하는 것을 감소하기 위해 이 Arena를 생성을 한다.

sbrk()를 이용하는 Main Arena와는 다르게 mmap을 통해서 할당을 하고 mprotect()를 이용해 사용 가능하게끔 한다.

Main Arena와는 다르게 여러 개의 힙과 heap_info 구조체를 가질 수 있다.

 

여기서 의문이 가는 점들이 있을 수 있다.

그러면 사용자 컴퓨터의 core의 수보다 많은 쓰레드를 가지고 있는 프로그램들은 여러 개의 Arena를 가지는 건가??

이렇게 되면 하나의 arena당 쓰레드를 가져 bit가 크게 낭비될 것이다.

이러한 이유로 arena는 코어 수에 따른 제한이 있다.

 

32 bit systems:

    Number of arena = 2 * number of cores

64 bit systems:

    Number of arena = 8 * number of cores 

 

여기서 추가로 알 수 있는 점이 있다.

32bit 시스템에서 다중 쓰레드 프로그램(4개의 쓰레드를 이용하는)을 실행시킨다고 가정해보자.

그렇게 되면 2개의 코어가 있어야지 4개의 쓰레드를 이용하는 프로그램을 실행시킬 수 있다.

하지만 2개의 코어가 없으면 프로그램을 실행하지 못하게 되는 것이다.

이와 같은 이유로 arena가 모든 사용 가능한 스레드와 공유가 된다.

(※일대일 매핑이 아니라 자원 공유를 함)

• 처음 malloc을 호출할 때 생기는 main arena는 어떠한 충돌 없이 사용된다.
• thread1과 thread2가 처음으로 malloc을 호출하는 경우에는, 이 스레드들을 위해 새로운 sub arena가 생성되고 어떠한 충돌도 없이 사용된다. 여기까지는 스레드와 arena가 일대일 매핑을 한다.
• thread3이 처음으로 malloc()을 호출하는 경우에 arena의 개수가 제한이 된다. 여기서 제한된 arena의 개수를 위해서 현재 존재하는 arena들을 재사용한다.

3. Datastrucutures of "glibc malloc"

malloc의 소스코드에서 3개의 데이터 구조체를 확인 가능하다.

heap_info - Heap Header 

Sub arena는 여러 개의 힙을 가질 수 있다.

각 힙은 각자의 헤더를 가지며 모든 쓰레드 arena는 하나의 힙을 가지고 시작을 하지만,

힙 영역 공간이 부족해지면 arena에 새로운 힙을 할당해주어야 한다.

 

malloc_state - Arena Header

Sub arena는 여러 개의 힙을 가질 수 있다.

이 힙들에 대해서는 하나의 Arena Header만 가진다.

 

malloc_chunk - Chunk Header

각 청크는 각각의 헤더를 가지며 사용자 요청을 기반으로 힙은 다수의 청크로 분열된다.

 

데이터 구조체 소스코드

 

Heap_info(Heap Header)

typedef struct _heap_info {
	mstate ar_ptr; /* 현재 Heap의 Arena pointer */
	struct _heap_info *prev; /* 이전 Heap_info에 대한 포인터 */
	size_t size; /* 해당 청크 사이즈 */
	char pad[-5 * SIZE_SZ & MALLOC_ALIGN_MASK]; /* 적절한 정렬을 위한 패딩으로 사용 */
} heap_info;

 

Malloc_state(Arena Header)

struct malloc_state
{
  __libc_lock_define (, mutex);   /* Serialize access.  */
  int flags; 					  /* Flags (formerly in max_fast).  */

  mfastbinptr fastbinsY[NFASTBINS]; /* Fastbins */
  mchunkptr top;					/* Base of the Top chunk */
  mchunkptr last_remainder;			/* 청크 할당 후 남은 사이즈 */
  mchunkptr bins[NBINS * 2 - 2];    /* Unsortedbin, Smallbin, Largebin */

  unsigned int binmap[BINMAPSIZE];  /* 사용중인 bins이 있는지 확인 */

  struct malloc_state *next;		/* Arena 연결 리스트 */
  struct malloc_state *next_free;   /* 해제된 Arena 연결 리스트 */
 
  INTERNAL_SIZE_T attached_threads; /* 해당 아레나에 붙은 스레드의 갯수. 만약 0이면 free list*/
  
  INTERNAL_SIZE_T system_mem;
  INTERNAL_SIZE_T max_system_mem;
};

typedef struct malloc_state *mstate;

 

Malloc_chunk(Chunk Header)

struct malloc_chunk {
 
  INTERNAL_SIZE_T      prev_size;  /* 이전 chunk의 size(free된 경우), free가 아닌 경우 0으로 설정*/
  INTERNAL_SIZE_T      size;       /* 해당 chunk의 header를 포함한 크기 하위 3bit는 특정 조건을 체크하는 플래그 */
 
 /* Free된 경우만 사용 (double links) */
  struct malloc_chunk* fd;         /* 다음 Free Chunk를 가리키는 포인터 */
  struct malloc_chunk* bk;         /* 이전 Free Chunk를 가리키는 포인터 */
 
 /* Free된 경우만 사용 (double links) */
 /* large blocks에 대해서만 사용 */
  struct malloc_chunk* fd_nextsize; /* 다음 Free Chunk Size를 가리키는 포인터 */
  struct malloc_chunk* bk_nextsize; /* 이전 Free Chunk SIze를 가리키는 포인터 */
};

 

 

 

Continue..

해당 글에서는 Heap의 매커니즘,Arena에 대해서 알아봤다.

다음 글은 chunk,bin에 대해서 쓸 거다.

그럼 20000 ^^7

 

+ 도움을 받은 글들

https://sploitfun.wordpress.com/2015/02/10/understanding-glibc-malloc/

Understanding glibc malloc

https://tribal1012.tistory.com/78