[glibc] malloc 정리2 - bin

Bins

Free된 chunk들을 size를 기준으로 관리하는 자료구조

Free chunk는 크기와 히스토리에 따라 다양한 목록에 저장되며 이러한 목록들을 bins라고 한다.

할당자는 할당 요청을 충족시키기 위해 적합한 chunk를 bins에서 신속하게 찾아서 재할당합니다.

Bin의 종류

• Fast bin
• Small bin - Bin 2 ~ Bin 63
• Large bin - Bin 64 ~ Bin 126
• Unsorted bin - Bin 1

Fast bin

M_MXFAST(1)라는 매개변수를 사용해서 "fastbin"에 포함되는 청크의 범위를 설정합니다.

• fastbin에 포함되는 chunk 크기의 범위는 (0 ~ 80)*sizeof(size_t)/4까지
• fastbin의 default
  • 32bit 아키텍처 64byte(64*4/4)
  • 64bit 아키텍처 128byte(64*8/4)
  • 해당 크기보다 작은 chunk들이 fastbin에 배치됩니다.
• 해당 크기는 매개변수 "value"를 이용하여 변경할 수 있습니다.
  • 32bit 아키텍처 최대 80byte(80*4/4)
  • 64bit 아키텍처 최대 160byte(80*8/4)
  • fast bin을 비활성화하려면 0으로 설정하면 됩니다.

• LIFO(last in, first out)를 사용 → 마지막으로 해제 된 chunk가 먼저 재할당됨
• 해당 bin은 최대 10개의 bin 관리 할 수 있으며, fastbin의 상한 값보다 크기가 작은 chunk들을 관리합니다. 
  • 32bit 아키텍처 chunk의 크기 = 16, 24, 32, 40 ...
  • 64bit 아키텍처 chunk의 크기 = 32, 48, 64, 80 ...
  • fastbin_index로 index 계산

• single-linked list로 구성
  • 같은 크기의 chunk가 해제되면 마지막으로 해제된 chunk의 fd에 새로 해제된 chunk의 mchunkptr을 저장됩니다.
  • bk는 사용하지 않습니다.
• 해당 bin에 포함되는 chunk들은 서로 인접해 있어도 병합하지 않습니다.
  • 해제가 되어도 다음 chunk의 prev_inuse값이 변경되지 않음

 

Small bin

• Small bin이 포함하는 chunk는 크기가 MIN_LARGE_SIZE 보다 작은 chunk들입니다.
  • 32bit 시스템은 MALLOC_ALIGNMENT는 8이고, SIZE_SZ는 4입니다.
    • MIN_LARGE_SIZE는 512((64 - 0) * 8)입니다.
  • 64bit 시스템은 MALLOC_ALIGNMENT는 16이고,SIZE_SZ는 8입니다.
    • MIN_LARGE_SIZE는 1024((64 * 0) * 16)입니다.
  • 즉, 32bit 시스템에서 Small bin의 범위는 16~504byte(64*8-8)이며 64bit에서는 32~1008byte입니다.
• 해당 bin은 62개의 bin들을 관리하며, doubly-linked list로 구성됩니다.
  • 같은 크기의 chunk가 해제되면 마지막으로 해제된 chunk의 fd에 새로 해제된 chunk의 mchunkptr가 저장됩니다.
  • 새로 해제된 chunk의 bk에 마지막으로 해제된 같은 크기의 chunk의 mchunkptr가 저장됩니다.
• FIFO(First In, First Out)을 사용 → 먼저 해제 된 청크가 먼저 재할당됩니다.
• 해당 chunk가 서로 인접해 있을 경우 하나의 chunk로 병합됩니다.

• bin의 인덱스는 smallbin_index() 함수를 이용하여 확인 할 수 있습니다.  
  • 이함수는 SMALLBIN_WIDTH을 사용해서 해당 시스템이 32bit인지 64bit인지 확인합니다.
    
    • 64bit의 경우 chunk 크기를 16으로 나눈다음, 그 값에 SMALLBIN_CORRECTION를 더 합니다.
    • 이 값이 해당 chunk의 인덱스 입니다.
    • 32bit의 경우 chunk의 크기를 8로 나눕니다.
  • 예를 들어 64bit에서 144byte의 free chunk의 인덱스는 9입니다.

 

Large bin

• Large bin이 포함하는 chunk의 크기가 MIN_LARGE_SIZE와 같거나 큰 chunk들입니다.
  • 32bit 아키텍처의 경우 free chunk >= 512 
  • 64bit 아키텍처의 경우 free chunk >= 1024
• Large bin이 포함하는 chunk들은 서로 인접해 있을 경우 하나의 chunk로 병합됩니다.
• Large bin은 63개의 bin을 사용하며, doubly-linked list로 구성됩니다.
  • 그러나 Large bin은 Small Bin과 다르게 하나의 bin에 다양한 크기의 chunk들을 보관합니다.
  • 해당 bin들은 bin내에서 크기 별로 정렬되어 할당의 효율성을 높입니다.
    • 앞쪽이 더 큰 size의 chunk

• Large bin에 해당하는 chunk들의 인덱스는 largebin_index_32(), largebin_index_64() 함수를 이용하여 확인할 수 있습니다.
  • free chunk의 크기를 쉬프트 연산을 이용하여 나누고, 그 값이 조건에 만족하는 값이라면 기본 인덱스 값을 더한 값이 해당 chunk의 인덱스 값이 됩니다.
  • 예를 들어 64bit 아키텍처에서 chunk의 크기가 3072 ~ 3120인 chunk들은 bin[96]에 보관됩니다. 48 + (3072 >> 6) = 96

 

Unsorted bin

• free 했을 때 각 bin(smallbin, largebin)으로 들어가기 전 (fastbin 제외)
• 인접한 chunk도 이미 free되어 있어, 병합된 free chunck
• best fit으로 chunk를 분할 할당한 후에 남은 chunk
  • 해당 bin은 Chunk 크기에 대한 제한이 없기 때문에 다양한 크기의 chunk가 해당 Bin에 저장될 수 있습니다. 
  • Fast bin에 해당하는 chunk는 Unsorted bin에 배치 되지 않습니다.
  • 할당자는 Unsorted bin에 요청받은 메모리의 크기와 같은 chunk가 있다면 해당 chunk를 재할당합니다.
• Unsorted Bin은 1개의 bin만 사용하며, doubly-linked list와 FIFO를 사용합니다.
  • 해당 bin을 이용해 적절한 bin을 찾는 시간이 덜 걸리므로 할당과 해제의 처리가 빠릅니다.
• Allocator에 의해 검색된 Chunk는 바로 재할당 되거나 아니면 원래의 Bin에 배치 됩니다.

 

128KB 이상의 큰 메모리

• 할당자는 크기가 128KB보다 큰 메모리를 할당하기 위해 mmap()에 새로운 메모리를 매핑을 요청한 후 해당 메모리에서 Chunk를 할당합니다.
  • 해당 Chunk들은 Bin에 속하지 않습니다.
  • 해당 Chunk들은 IS_MMAPPED 플래그가 설정됩니다.
  • 해당 chunk들은 munmap()을 호출하여 해제합니다.

 

Reference

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

Understanding glibc malloc

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

01.Malloc - glibc(ptmalloc2)[Korean] - TechNote - Lazenca.0x0

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

malloc.c - malloc/malloc.c - Glibc source code (glibc-2.31) - Bootlin