여러 대단하신 분들이 작성하신 글을 처음에 보고 도대체 이 심오한 영역은 무엇인가라는 한탄을 하였다. 그래서 이렇게 정리를 해서 글을 쓰면 조금이나마 이해에 도움이 될까하여 작성해본다.

ptmalloc2

Linux에서는 ptmalloc2라는 memory allocator를 이용해서 운영체제로부터 메모리를 할당 받아서 사용한다. 메모리를 할당 받을 때 fragmentation이 발생하기 때문에 이를 최소화 시키는 것이 목적이다.

여기서 fragmentation에서는 internal과 external이 존재하는데 internal은 큰 메모리를 할당 받았으나 실제로 사용하는 크기가 작은 것을 말하고 external은 할당 받은 메모리 크기가 제각각이며 데이터가 연속적으로 적재되지 않는 것을 말한다. 이런 문제들을 해결하기 위해서 정렬과 병합 그리고 분할을 이용해서 위 문제들을 해결한다. 데이터가 연속적으로 적재되지 않았다면 정렬을 통해서 문제를 해결하고 할당 받은 메모리가 너무 크면 분할을 사용해서 필요한 만큼만 사용하게 할 수 있고 받은 영역이 부족하다면 더 할당받아서 병합시켜 하나의 큰 메모리를 만들 수 있게 하는 것이다.

Internal Fagmentation

External Fragmentation

ptmalloc2 객체

ptmalloc2에서는 arena, chunk, bin, tchache를 주요 객체로 사용한다. 우선 먼저 집고 넘어가야 할 부분은 객체가 무엇인가부터 시작해야 할 것 같다.

간단히 말해서 여기서 말하는 객체는 구조나 개념을 의미한다. 그러니 ptmalloc2에서는 arena, chunk, bin, tchache와 같은 개념 또는 구조를 사용한다고 이해하면 될 것 같다.

그럼 우선 arena가 무엇인지에 대해서 설명해보려고 한다.

Arena

Arena의 사전적 의미는 경기장을 의미한다. 콜로세움처럼 투기장을 아레나라고 불렀으며 이 아레나를 들었을 때 느껴야하는 것은 바로 경쟁이다. 어떤 프로세스가 실행이 되고 있으면 각 Thread 별로 task를 분담하여 일을 처리 할 것이다. 그렇다면 task를 진행 할 때 필요한 메모리가 있을 것이고 이를 공동으로 사용되는 heap 영역에 가서 여러 multi Thread가 경쟁을 통해서 메모리를 할당 받으려고 한다면 성능이 저하가 될 것이다. 이런 경쟁을 막기 위해서 도입 된 것이 Arena인 것이다. 그리고 공동으로 사용되는 메모리이다 보니 다른 Thread에서 마음대로 메모리에 저장되어 있는 값을 바꾸고 할 수 있기 때문에 이런 것을 사전에 방지하고 하는 목적도 존재한다. 이를 Race conditon이라고 한다.

Arena는 Thread마다 부여되는 heap 영역이라고 보면 된다. 각 Thread마다 자신만의 heap 영역이 있다면 위와 같은 경쟁을 할 필요가 없기 때문이다. 좀 더 쉽게 설명을 하자면 heap 영역에 있는 메모리를 각 Thread 별로 일정 크기를 분배해 주는 것이라고 생각하면 편하다. 만약 할당 받은 메모리 공간이 부족하면 새로운 영역에 추가로 할당받기 때문에 여러 개의 힙 영역을 가질 수 있다(Main Thread 제외).

아래와 같은 사진을 보면 이해하는데 도움을 줄 것 같다.

모든 Thread에 arena가 있으면 좋겠지만 그러면 메모리 부족과 낭비가 될 수 있기 때문에 cpu의 core 갯수에 따라 arena 수가 결정이 된다.

그림을 보면 Main Arena가 있고 sub heap등이 보일 것이다. sub heap들이 arena가 되는 것을 볼 수 있는데 이를 sub arena라고 한다. Main과 sub arena에 대해서 설명하겠다.

Main Arena

Main Thread에서 사용하는 arena이다. 기본적으로 이 arena는 메모리가 부족하면 확장을 통해서 메모리를 확보한다. heap을 사용하지 않아도 기본적으로 132KB의 크기를 갖고 있다. 확장을 시킬 때에는 sbrk()라는 syscall을 이용해서 확장을 시키는데 data segment의 끝을 움직일 수 있게 해준다. 하지만 일정 크기 이상의 메모리를 요구하게 된다면 확장하지 않고 사진처럼 sub heap을 mmap syscall을 통해서 할당하게 한다. 그렇게 할당 받은 sub heap이 sub arena가 되는 것이다.

이런 힙 영역은 어떤 Arena가 관리하고 있는지, 힙 영역의 크기가 어느정도인지, 이전에 사용하던 heap 영역의 정보가 어디에 있는지를 저장할 필요가 있다. 이런 정보를 저장하기 위한 구조체가 malloc_info 구조체이며, 힙에 대한 정보를 저장하기 때문에 Heap_Header라고도 할 수 있다.

typedef struct _heap_info {
 mstate ar_ptr;    /* 현재 heap을 담당하고 있는 Arena */
 struct _heap_info *prev;  /* 이전 heap 영역 */
 size_t size;      /* 현재 size(bytes) */
 size_t mprotect_size; /* mprotected(PROT_READ|PROT_WRITE) size(bytes) */
 char pad[(-6*SIZE_SZ)&MALLOC_ALIGN_MASK]; /* 메모리 정렬 */
 /* sizeof(heap_info) + 2*SIZE_SZ는 MALLOC_ALIGN_MASK의 배수 */
} heap_info;

위의 Heap_Header에서는 단순히 힙 영역에 대한 정보만을 저장하였기 때문에, 힙 영역에서도 어떤 부분을 사용하면 되는지에 대해 Arena는 이를 관리하기 때문에 알고 있을 필요가 있다. malloc_state 구조체는 각 Arena에 하나씩 주어지고, 해제된 Chunk를 관리하는 연결리스트 bin과 최상위 Chunk인 top chunk와 같은 Arena에 대한 정보를 저장한다.

struct malloc_state
{
  /* Serialize access.  */
  mutex_t mutex;
 
  /* Flags (formerly in max_fast).  */
  int flags;
 
  /* Fastbins */
  mfastbinptr fastbinsY[NFASTBINS];
 
  /* topchunk의 base address */
  mchunkptr top;
 
  /* 가장 최근의 작은 요청으로부터 분리된 나머지 */
  mchunkptr last_remainder;
 
  /* 위에서 설명한대로 pack된 일반적인 bins */
  mchunkptr bins[NBINS * 2 - 2];
 
  /* Bitmap of bins */
  unsigned int binmap[BINMAPSIZE];
 
  /* 연결 리스트 */
  struct malloc_state *next;
 
  /* 해제된 아레나를 위한 연결 리스트 */
  struct malloc_state *next_free;
 
  /* 현재 Arena의 시스템으로부터 메모리 할당  */
  INTERNAL_SIZE_T system_mem;
  INTERNAL_SIZE_T max_system_mem;
};

위 구조체들을 보면 알다시피 bin과 chunk가 보일 것이다. 이 말 뜻은 Arena에서 bin과 chunk를 관리한다고 볼 수 있다. 이제 Arena가 무엇인지 감이 올 것이다. 그 다음에는 Chunk가 무엇인지에 대해서 설명하려 한다.

Chunk

chunk는 사전적 의미로 덩어리라는 뜻을 갖고 있다. 말 그대로 arena에서 데이터를 담고 있는 메모리 덩어리라고 보면 된다. 쉬운 설명을 위해 아래와 같은 사진을 첨부한다.

prev_size : 만일 이전 청크를 해제하는 경우, 이 필드는 이전 청크의 크기를 저장한다. 만일 이전 청크가 할당된 경우에는, 이 필드는 이전 청크의 사용자 데이터를 저장한다.

size : 이 필드는 할당된 청크의 크기를 저장한다. 이 필드의 맨 끝 3bit는 flag 정보를 저장한다.

PREV_INUSE (P) - 이 비트는 이전 청크가 할당된 경우 세트된다.
IS_MMAPPED (M) - 이 비트는 현재 청크가 mmap을 통해 할당된 경우 세트된다.
NON_MAIN_ARENA (A) - 이 비트는 현재 청크가 thread arena에 위치하는 경우 세트된다.

이제는 free가 된 chunk 사진을 보려고 한다.

fd : Forward pointer - 동일한 빈에서의 다음 청크를 가리킨다(물리 메모리에서의 다음 청크가 아님).

bk : Backward pointer - 동일한 빈에서의 이전 청크를 가리킨다(물리 메모리에서의 이전 청크가 아님).

bin은 chunk가 해제가 된 후 안 쓰는 chunk list 모음집이라고 생각하면 편하다. 종류도 다양하다. unsorted, fast, small, large bin들이 존재하는데 어떤 chunk가 해제가 된 후 tchache에 있고 다 차면 unsorted 그 후에 맞는 bin들을 찾아서 모음집에 들어가게 되는 것인데 더 자세한 내용들은 아래 사이트 주소를 남기니 참고 하면 좋을 듯하다. 아주 좋은 내용을 담고 있다.

사이트 : https://tribal1012.tistory.com/78

tchache (Thread local chache)

Thread에서 독립적으로 갖고 있는 캐쉬 메모리라고 생각하면 된다. 각 쓰레드는 64개의 tcache를 가지고 있고 2 바이트 이상, 1040 바이트 이하의 크기를 갖는 청크들을 저장한다. 하지만 리눅스에서는 7개의 chunk까지만 저장할 수가 있다.
위에서 이야기 했다시피 free를 하면 우선 먼저 tchache에 저장이 되고 그 후에 다른 bin으로 넘어가는 형식이다.

아래 그림들을 참고하면 free 후 어떤 방식으로 저장이 되는지 이해하기 쉬울 것이다.

반대로 어떻게 malloc으로 메모리를 할당하는지 알려주는 사진은 아래와 같다.

오늘은 이렇게 heap에 대해서 조금 deep하게 알아보는 시간을 갖었다. 이해를 한 후 보면 당연하다고 생각 할 수도 있다. 각 Thread 별로 필요한 heap 영역을 arena라는 단위로 할당을 해주고 그 arena에서 chunk를 이용해서 데이터를 double linked 방식으로 저장하고 다 쓴 chunk를 해제하고 그 chunk를 다 쓴 모음집에 저장한 것이 bin이고 비슷한 chunk 크기가 필요하면 bin에서 비슷한 크기를 찾아서 다시 사용하고 등등 이런 과정들을 이해하는 시간을 갖게 되었다.