Heap - glibc 2.23 (1)

Heap - glibc 2.23 (1)

---

malloc_chunk

1. chunk 구조체

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

• 이전 청크의 크기를 저장한다.
• 이전 청크가 free 상태일 때만 유효한 값을 가진다.
  → 사용중(inuse)이라면 데이터 영역의 일부로 취급된다.
• 청크가 free될 때 인접한 청크를(free됨) 병합(coalescing)하기 위해 사용된다.
  → prev_size값을 이용해 이전 청크의 시작 주소를 정확히 계산할 수 있다.

size

• 현재 청크의 크기를 저장한다. (사용자 요청 크기 + 헤더)
• 하위 3비트는 플래그 비트로 사용된다.
  • PREV_INUSE(P-bit) : 가장 마지막 비트로 이전 청크가 사용 중이면 1 아니면 0
  • IS_MMAPPED(M-bit) : 끝에서 두 번째 비트로 1이면 sbrk로 확장된 힙이 아닌 mmap으로 할당됨
  • NON_MAIN_ARENA(A-bit) : 끝에서 세 번째 비트로 1이면 main arena가 아닌 thread arena에 속함

fd, bk

• free된 청크를 이중 연결 리스트로 묶기 위한 포인터이다.
  • fd (forward pointer) : 다음 청크를 가리킴
  • bk (backward pointer) : 이전 청크를 가리킴

fd_nextsize, bk_nextsize

• large bin에만 사용되는 이중 연결 리스트 포인터이다.
• small bin은 동일한 크기의 청크만 들어있지만 large bin은 특정 크기 범위에 속하는 청크가 들어있다. (중복 가능)
• large bin에서 청크는 순서대로 정렬되어 있지 않다.
  → malloc이 요청한 크기에 맞는 청크(best-fit)을 찾으려면 전체를 순회해야 한다.
  이 문제 해결을 위해 fd_nextsize와 bk_nextsize는 서로 다른 크기의 청크만 연결한다.(빠른 탐색용)

 

malloc_state

1. arena 구조체

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

mutex

• 멀티쓰레드 환경에서 두 개 이상의 쓰레드가 동시에 같은 아레나에 접근하는 것을 막는다.

int flags

• 아레나의 현재 상태를 나타내는 플래그 비트를 저장한다.
  • FASTCHUNKS_BIT : fastbin에 청크가 있는지 여부를 나타낸다.
  • NONCONTIGUOUS_BIT  : 아레나에 할당된 메모리가 물리적으로 연속적이지 않다는 것을 나타낸다.

fastbinY[NFASTBINS]

• fastbin을 관리하는 배열이다.
• NFASTBINS는 보통 10이다.
• free는 작은 청크를 병합 없이 이 배열에 빠르게 추가한다.

NFASTBINS가 왜 10일까?

---

32bit 환경에서 malloc은 8byte 단위로 메모리를 정렬한다.

→ 모든 청크의 크기는 8의 배수여야 한다.

 

malloc_chunk 구조체는 prev_size와 size 필드(총 8byte)를 가지기 때문에 최소 청크 크기는 16byte이다.

fastbin은 각 bin마다 8byte씩 크기가 증가하는 청크를 관리한다.

• fastbinsY[0]: 16 바이트 (0x10) 크기 청크
• fastbinsY[1]: 24 바이트 (0x18) 크기 청크
• fastbinsY[2]: 32 바이트 (0x20) 크기 청크
• fastbinsY[3]: 40 바이트 (0x28) 크기 청크
• fastbinsY[4]: 48 바이트 (0x30) 크기 청크
• fastbinsY[5]: 56 바이트 (0x38) 크기 청크
• fastbinsY[6]: 64 바이트 (0x40) 크기 청크
• fastbinsY[7]: 72 바이트 (0x48) 크기 청크
• fastbinsY[8]: 80 바이트 (0x50) 크기 청크
• fastbinsY[9]: 88 바이트 (0x60) 크기 청크

glibc는 NFASTBINS를 계산하기 위해 상수와 매크로를 정의한다

#define MAX_FAST_SIZE (80 * SIZE_SZ / 4)

• SIZE_SZ는 4(32bit) 또는 8(64bit)이다.
  • 32bit : (80 * 4 / 4) = 80byte
  • 64bit : (80 * 8 / 4) = 160byte

#define fastbin_index(sz) ((((unsigned int)(sz)) >> (SIZE_SZ==8 ? 4 : 3)) - 2)

• 청크 크기(sz)를 받아서 fastbinY의 몇 번째 인덱스에 해당하는지 계산한다.

#define NFASTBINS (fastbin_index(request2size(MAX_FAST_SIZE)) + 1)

• MAX_FAST_SIZE를 request2size를 통해 실제 청크 크기로 변환하고 fastbin_index를 구한 뒤 0부터 시작하는 인덱스이므로 + 1을 해준 값이다

 

그럼 64bit 는 어떻게 될까?

---

NFASTBINS는 똑같이 10으로 정의되어 있다. → 관리하는 청크의 크기가 다르다.

메모리 정렬이 16byte 기준이기 때문에 fastbinsY의 배열은 다음과 같다

• fastbinsY[0]: 32 바이트 (0x20) 크기 청크
• fastbinsY[1]: 48 바이트 (0x30) 크기 청크
• fastbinsY[2]: 64 바이트 (0x40) 크기 청크
• ...
• fastbinsY[6]: 128 바이트 (0x80) 크기 청크
• fastbinsY[7]: 144바이트 (0x90) 크기 청크
• fastbinsY[8]: 160바이트 (0xA0) 크기 청크
• fastbinsY[9]: 176바이트 (0xB0) 크기 청크

64비트 아키텍처에서는 0부터 9까지 총 10개의 bin이 사용된다.

 

top

• top chunk를 가리키는 포인터
• top chunk는 어떤 bin에도 속하지 않는 특별한 청크이다. (가장 높은 주소)
• 모든 bin에서 적절한 크기의 청크를 찾지 못했을 때, top chunk의 일부를 잘라서 할당한다.

last_remainder

• 가장 최근에 분할되고 남은 청크를 가리킨다.
• malloc이 큰 청크를 쪼개서 작은 요청을 처리하고 남은 부분을 last_remainde에 저장한다.
  → 다음 malloc 요청이 last_remainder 크기와 맞는다면 바로 이 청크를 반환한다. (성능 향상)

bins[NBINS * 2 - 2]

• unsorted bin, small bin, large bin을 모두 담고 있는 배열이다.
• bins[0] : unsorted bins의 헤드(fd)
• bins[1] : unsorted bins의 헤드(bk)
• bins[2]~bins[125] : small bins의 fd, bk
• bins[126]~bins[253] : large bins의 fd, bk

왜 NBINS * 2를 하는가?

---

bins 배열은 unsorted bin small bins, large bins의 헤드 역할을 한다.

이 bin 들은 모두 이중 연결 리스트로 각 헤드는 리스트의 시작(fd 포인터)과 끝(bk 포인터)을 모두 알아야 한다.

→ 각 bin 마다 2개의 포인터 공간이 필요하다

 

128개의 bin을 사용하면 NBINS * 2 즉, 256개가 필요하다

 

 

왜 -2 를 하는가?

---

ptmalloc에서 관리하는 bin은 논리적으로 1~127까지이다.

따라서 실제 의미를 갖는 bin은 bin[1](unsorted bin)부터 시작한다.

bin[0]의 fd, bk 포인터는 필요하지 않기 때문에 2개를 제외해서 -2를 한다.

 

 

예시

---

bin[1] (unsorted bin)의 헤드 → bin[0], bin[1]에 저장

bin[2] (small bin)의 헤드 → bin[2], bin[3]에 저장

binmap[BINMAPSIZE]

• 어떤 bin이 비어있지 않은지 표시하는 비트맵(bitmap)
• malloc이 bin을 일일이 검사하는 것은 비효율적이기 때문에 binmap의 비트가 1인지 0인지만 확인하면 청크의 존재 여부를 알 수 있다. (속도 향상)

malloc_state *next

• 전체 아레나 리스트를 구성하기 위한 포인터이다.
• 생성된 모든 아레나를 순환 이중 연결 리스트로 관리하는데 이 포인터가 그 역할을 한다.

malloc_state *next_free

• 어떤 쓰레드에도 할당되지 않은 아레나들만 따로 연결하는 리스트의 포인터

attached_threads

• 현재 이 아레나를 사용하고 있는 쓰레드의 수를 나타내는 카운터이다.
• 이 값이 0이 되면 해당 아레나는 next_free 리스트로 옮겨질 수 있다.

system_mem, max_system_mem

• 해당 아레나가 운영체제로부터 sbrk나 mmap을 통해 할당받은 총 메모리의 양과 최대량을 기록하는 통계용 변수