Progressing slowly but steady

5 minute read

1. bin의 개념

bin은 free된 chunk들을 저장하는 객체이다. 메모리의 낭비를 막고 새로운 메모리 할당 요청이 들어왔을 때, free된 chunk들을 빠르게 재사용할 수 있게 도와준다.

struct malloc_state
{
  mutex_t mutex;
  int flags;
  /* Fastbins */
  mfastbinptr fastbinsY[NFASTBINS];
  mchunkptr top;
  mchunkptr last_remainder;
  /* Normal bins packed as described above */
  mchunkptr bins[NBINS * 2 - 2];
  /* Bitmap of bins */
  unsigned int binmap[BINMAPSIZE];
  struct malloc_state *next;
  struct malloc_state *next_free;
  INTERNAL_SIZE_T attached_threads;
  INTERNAL_SIZE_T system_mem;
  INTERNAL_SIZE_T max_system_mem;
};

위의 구조체는 Heap basic #2에서 다루었던 molloc_state (arena header) 구조체이다. 해당 구조체를 확인해 보면 필드로 mfastbinptr fastbinsY[NFASTBINS]와 mchunkptr bins[NBINS * 2 - 2]가 존재하는 것을 확인할 수 있다.

해당 필드들이 각종 bins의 정보를 저장하기 위한 포인터 배열이다.

bin들은 다음 그림과 같이 이중 혹은 단일 연결 리스트의 형태로 (실제 물리적으로는 불연속적일 수 있는) freed chunk들에 대한 정보를 저장한다.

bins

bins는 fastbin, smallbin, largebin, unsortedbin이라는 4가지 종류가 있으며, 해당 bin들에 대한 자세한 설명은 다음에서 설명한다.

2. bins

fastbin의 경우, 위의 arena header 구조체에서 fastbinsY가 관리하고, 다른 3개의 bins는 bins에서 관리된다.

다음은 bins 배열의 그림이다.

bins_arr

총 128개의 bins 요소들 중, 1개의 unsortedbin, 62개의 smallbin, 64개의 largebin들이 사용된다. (인덱스 0과 127의 경우 사용되지 않는다.)

smallbin과 largebin의 경우, freed chunk들 사이에서 병합 (consolidation)이 일어날 수 있다.

병합은 물리적으로 인접해 있는 freed chunk들 사이에서 일어난다. 특정 chunk를 free하려고 할때, 해당 chunk, 혹은 그 다음 다음 chunk의 (해당 chunk의 다음 chunk의 free 여부를 확인하기 위해서) chunk header의 prev_inuse flag를 확인하여 병합을 진행한다.

2.1 fastbin (32 바이트 ~ 128 바이트)

fastbin은 fragmentation의 발생 감소보다 메모리 할당의 속도를 더 우선시한 bin이다.

fastbin에는 32 바이트 이상, 176 바이트 이하의 chunk들이 보관되어 16 바이트 단위로 총 10개의 fastbin들이 존재한다.

그러나, 리눅스에서는 이 중에서 작은 크기부터 7개의 fastbin만을 사용한다.

따라서, 리눅스에서는 32 바이트 이상, 128 바이트 이하의 chunk들이 fastbin에 저장된다.

fastbin의 경우 단일 연결리스트를 사용하며, 나중에 free되어 fastbin에 연결된 chunk가 메모리 할당 요청이 발생시 먼저 재할당 되는 LIFO로 동작한다.

fastbin의 chunk들은 서로 병합(consolidation)되지 않는다. (fastbin은 빠른 재할당이 우선이므로 이런 과정이 생략된다.)

처음 free된 chunk의 fd는 0으로 초기화 된다.

fastbin은 단일 연결리스트이고 LIFO여서 unlink과정이 필요가 없고, (특별한 경우가 아니면) 병합을 할 필요가 없어 속도가 빠르다는 장점이 있지만, memory fragmentation이 발생하기 쉽다는 단점이 존재한다.

cf)

  • 32 bit 환경 : 최소 크기 16byte 부터 24, 32, 40, 48, 56, 64 byte 까지이다
  • 64 bit 환경 : 최소 크기 32 byte 부터 48, 64, 80, 96, 112, 128 byte 까지이다

2.2 smallbin(32 바이트 ~ 1008 바이트)

smallbin에는 32 바이트 이상, 1024 바이트 미만의 크기를 갖는 chunk들이 보관되는데, 하나의 smallbin에는 같은 크기의 chunk들만이 보관된다.

즉, smallbin[0]은 32 바이트 크기의 chunk들만을, smallbin[61]은 1008 바이트 크기의 chunk들만을 보관한다.

smallbin은 원형 이중 연결리스트 형태로, 먼저 free되어 들어온 chunk가 먼저 재할당되는 FIFO 방식이다. (이중 연결리스트의 특성상, chunk를 추가하거나 꺼낼 때, 연결 고리를 끊는 unlink라는 과정이 들어간다.)

smallbin의 경우, 메모리 상에서 물리적으로 인접한 두 chunk들의 경우 병합이 수행된다.

fastbin 리스트에 연결된 청크가 10개가 넘어가는 경우, 0x20 ~ 0x80 사이즈 청크는 smallbin으로 들어간다고 한다.

2.3 largebin(1024 바이트 이상)

1024 바이트 이상의 크기를 갖는 chunk들이 보관된다. 총 63개의 bin을 사용하는데, 각 bin에서 동일한 크기의 chunk를 보관하는 smallbin, fastbin과는 달리 각 largebin은 일정 범위 안의 chunk들을 모두 보관한다. 해당 범위는 인덱스가 증가하면 로그적으로 증가한다.

위의 방법으로 largebin은 적은 수로 다양한 크기의 chunk들을 관리할 수 있다.

largebin은 범위에 대항하는 모든 chunk들을 보관하기 때문에, 재할당 요청이 발생시, 크기가 가장 비슷한, best-fit chunk를 꺼내서 재할당 한다. 이를 위해서 largebin은 내부의 chunk들을 내림차순 형태로 정렬한다.

(이 때 fd_nextsize, bk_nextsize 필드가 이용된다. 다만, 동일한 크기의 청크끼리는 fd_nextsize, bk_nextsize가 설정되지 않는다.)

이중 연결리스트 형태의 largebin은 재할당 과정에서 unlink를 동반한다.

연속된 largebin chunk들은 병합의 대상이 된다.

128kb 이상의 큰 청크 요청은 mmap()을 통해 별도로 할당된다. 이를 통해 할당된 청크는

  1. bin에 속하지 않는다.
  2. Mmap’d 플래그가 설정된다.
  3. free될 경우 munmmap()을 통해 해제된다.

cf)

  • largebin[0] ~ largebin[31] = 32개 빈
    • 64 bytes 씩 증가하면서 해당 사이즈 범위에 해당하는 청크를 관리함
  • largebin[32] ~ largebin[47] = 16개 빈
    • 512 bytes 씩 증가하면서 해당 사이즈 범위에 해당하는 청크를 관리함
  • largebin[48] ~ largebin[55] = 8개 빈
    • 4096 bytes 씩 증가하면서 해당 사이즈 범위에 해당하는 청크를 관리함
  • largebin[56] ~largebin[59] = 4개 빈
    • 32768 bytes 씩 증가하면서 해당 사이즈 범위에 해당하는 청크를 관리함
  • largebin[60] ~ largebin[61] = 2개 빈
    • 262144 bytes 씩 증가하면서 해당 사이즈 범위에 해당하는 청크를 관리함
  • largebin[62] = 1개 빈
    • 이 외의 남은 크기의 청크를 관리함

2.4 unsortedbin

프로그램의 특성상 어떤 chunk를 해제한 다음에 비슷한 크기의 chunk를 바로 할당하거나, 또는 한번에 여러 chunk들을 연속적으로 해제하는 하는 경우가 빈번하게 발생한다.

따라서, chunk가 free 되었을 때, 금방 다시 재사용될 chunk의 분류에 드는 시간은 비효율적이고, 동시에 여러 chunk들을 free할 때 드는 분류 + 병합의 반복적인 작업은 메모리 할당에 드는 시간적 비용을 증가시킨다.

unsortedbin은 위와 같은 문제를 해결하기 위한 bin으로 분류되지 않은 chunk들을 보관하기 위한 bin이다. free가 되었을 때, fastbin에 보관되지 않은 모든 chunk들은 크기를 구분하지 않고 일단 unsortedbin에 보관된다.

그 후 할당 요청이 들어왔을 때, 다음과 같은 과정을 거친다.

malloc

위의 그림에서 확인할 수 있듯이 요청한 chunk의 크기에 따라서 다음과 같은 과정을 거친다.

  1. fastbin 최대 크기 미만 요청 : fastbins에서 먼저 탐색 후, 존재하지 않을 시 unsortedbin 탐색
  2. (fastbin 최대 크기 이상) smallbin 최대 크기 미만 요청 : smallbin 먼저 탐색 후, unsortedbin 탐색
  3. largebin 크기 요청 : unsortedbin 먼저 탐색
  • 이 탐색 과정에서 재할당 되지 못하고 넘어간 chunk들은 자신의 크기에 맞는 적절한 bin으로 분류된다.

Unsortedbin은 다음과 같은 특징들이 있다.

  • 해당 bin은 1개의 bin만 사용함
  • 해당 bin은 이중 연결리스트로 구성됨
  • 해당 bin을 이용해 적절한 bin을 찾는 시간이 적기 때문에 할당과 해제의 처리속도가 빠름
  • 해당 bin은 Chunk 크기에 대한 제한이 없기 때문에 다양한 크기의 청크가 해당 Bin에 저장될 수 있음
  • free()된 청크는 unsorted bin에 보관되며, 메모리 할당 시 동일한 크기의 영역을 다시 요청하는 경우 해당 영역을 재사용함. (fast chunk는 예외)
  • 해당 Bin은 FIFO 방식을 사용함
  • 검색된 청크는 바로 재할당되거나 실패하면 원래의 Bin을 돌아감
  • unsorted chunk는 NON_MAIN_ARENA 플래그를 절대 세팅하지 않음
  • unsortedbin에 처음으로 들어온 chunk의 경우, fp,bk가 libc의 특정 영역을 가리켜, 이를 이용해 libc_base의 주소를 leak할 수 있다.

3. Top Chunk

이전 포스트에서 설명한 Top chunk를 bin과 관련시켜 설명하면 다음과 같은 특징들이 있다.

Top chunk는 아레나의 메모리 끝 부분에 위치한 청크를 뜻한다. Top chunk는 어떤 bin에도 속하지 않는다.

다음의 경우에 top 청크를 활용한다.

  • 사용자가 요청한 사이즈를 처리할 적당한 청크를 어떠한 bin에서도 찾을 수 없을때 이런 경우 top chunk를 확인한다. 요청 사이즈가 현재 top chunk 크기보다 작을 경우, top chunk를 분할하여 할당해준다.
  • 사용자가 요청한 사이즈를 처리할 적당한 청크를 어떠한 bin에서도 찾을 수 없고, 현재 top 청크 사이보다 요청 사이즈가 더 클때
    1. top chunk < 요청 사이즈 < 128 KB
      • main_arena는 sysmalloc 함수를 통해 sbrk syscall을 호출하여 확장시키고 thread_arena는 mmap으로 확장시킨다
    2. top chunk < 128 KB < 요청 사이즈
      • main_arena, thread_arena 둘다 mmap으로 확장시킴

또한 fast bin 을 제외하고 모든 bin(small, unsorted)들은 top chunk와 물리적으로 인접한 chunk가 해제된 경우, top chunk와 병합하는데, 병합된 top chunk가 m_trim_threshold라는 내부적인 특정 임계값 보다 커졌다면, top chunk를 축소한다.

출처 & 참고

참고 1
참고 2

You may also enjoy