동적 할당이 해제되는 과정 & bins에 대해서 정리

List of Contents

Free (glibc2.23)

c언어를 기반으로 프로그래밍을 할때 동적할당을 위해서 malloc, free 를 자주 사용합니다.

실제 메모리 상에서 free가 어떤식으로 진행되는지를 알아볼것입니다. 우선 bins이 무엇인지 알아보겠습니다.

bins란 쉽게 말해서, free 청크들을 관리하는 관리자라고 생각하면 됩니다. 또한 관리자도 다 같은 관리자가 아닌, 1번째 영역을 관리하는 관리자, 2번째 영역을 관리하는 관리자, 3번째 영역을 관리하는 관리자 이렇게 각자의 역할이 있습니다.

bins의 종류는 크게 4개로 나뉩다(fastbins, unsorted bin, small bin, large bin). 이는 malloc_state구조체(Arena_Header)에서 확인이 가능합니다.

  
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 정보는 위의 malloc_state 구조체에서 관리됩니다.

FastbinsY : Fast bin을 관리한다.
Bins : 총 127개의 빈중 제일 처음 빈은 특별한 용도(Unsorted bin)으로 사용되고 나머지 126개가 unsorted bin, small bin, large bin으로 사용됩니다.

자세한 Bins의 구성은 다음과 같습니다(Index 0은 특별한 용도로 쓰인다).

Index 1 : Unsorted bin
Index 2 ~ 63 : Small bin
Index 64 ~ 126 : Large bin

할당된 청크는 청크 사이즈의 크기에 따라서 다음과 같이 구분됩니다.

위의 표에서 나온 청크 사이즈는 chunk 구조체의 size 부분에 들어가는 값입니다. 해당 size에 들어가는 값은 다음 청크의 prev_size를 제외하고 계산된 사이즈이지만, 실질적으로 할당된 청크의 데이터 영역은 다음 청크의 prev_size영역(0x10)까지 포함됩니다.

각 빈들의 전체적인 속성은 다음과 같다

(참고로 fastbin의 경우 0x20 ~ 0xb0 크기의 청크들을 총 10개로 관리한다고 하는데 실제로는 0x20부터 0x80까지 총 7개만 fastbin으로 관리되는것 같습니다.) → fastbin 사이즈를 임의로 변경하지 않는이상

이러한 빈들이 존재하는 이유는, malloc 요청시 매번 메모리 할당을 요청하는것이 아닌, free 청크들을 재사용하기 위함입니다. 사용자가 요청한 특정 사이즈의 청크가 특정 bin에 존재한다면, 그 빈에 있는 청크를 다시 재할당해줍니다.
또한 물리적으로 인접해 있는 free 청크들은 일반적으로 서로 병합을 하려고 합니다.(fastbin은 특별한 경우를 제외하고 병합안하는 특징이 있습니다). 크게 현재 청크의 이전 청크와 병합하거나, 다음 청크와 병합하는 경우가 있습니다.

병합 과정

다음 청크와 결합하는 경우

A를 해제하려고 할 때 다음 청크인 B가 해제된 상태이기 때문에 병합이 이루어집니다. B의 할당 or 해제 여부는 C의 prev_inuse 비트로 판단하기 때문에 A주소에서 size+size로 C의 p flag를 확인한 후 병합을 진행합니다.

병합 결과

이전 청크와 결합하는 경우

다음의 상황은 B를 해제하려고 하는데 A가 현재 해제되어 있는 상황입니다. 이 경우는 B의 prev_inuse 비트를 바로확인하여 이전 청크의 할당 or 해제 여부를 바로 파악 가능합니다. 현재 해당 플래그가 0이므로 B에서 Prev_size를 더하여 A와 결합을 진행합니다.

Fast bin

같은 크기를 기준으로 단일 연결 리스트로 연결된 일정크기 이하의 작은 청크를 의미합니다. fast bin의 특징은 다음과 같습니다.
LIFO 방식을 사용합니다(스택과 동일한 방식).
10개의 bin을 사용합니다(64bit에서는 디폴트로 7개 빈만을 사용하는 듯).
속도 향상을 위해 단일 연결 리스트로 구성됨. 다른 bins 다 이중 연결 리스트로 구성된다.
fast bin이 처리하는 메모리의 최대 크기는 “global_max_fast” 에 의해서 결정됩니다.
출처 : https://say2.tistory.com/entry/glibc-mallocc의-malloc함수-분석-약간의-exploit관점
32bit
- 빈 크기는 최소 크기 16byte 부터 24, 32, 40, 48, 56, 64 byte 까지입니다.
64bit
- 빈 크기는 최소 크기 32 byte 부터 48, 64, 80, 96, 112, 128 byte 까지입니다.
fast bin의 경우 free chunk가 서로 인접해 있어도 하나의 free chunk로 병합되지 않는다

*알아둘점*

일반적인 경우, 인접한 free chunk 들은 단일 청크로 존재하지 않는다. 
인접한 free된 청크들은 서로 병합을 진행하여 bins list들을 관리한다. 
하지만 fastbins의 특징 자체가 작은 크기의 청크들을 관리하기 위한 
목적이므로 인접한 free 청크를 병합하지 않는다. 
그렇기 때문에 free가 되어도 prev_inuse를 변경하지 않는다.

fastbin 실습

Unsorted bin

bins의 첫번째 인덱스가 바로 Unsorted bin의 list로 사용됩니다. 일종의 cache와 같은 역할로 free된 청크가 바로 자신의 bin(small or large)으로 바로 들어가지 않고 먼저 unsorted bin으로 들어갑니다(fast bin은 예외).
그 이후 malloc 요청시 동일한 크기의 영역을 재요청하는 경우 unsorted bin에 들어있는 청크를 바로 재사용 할 수 있게 합니다. unsorted bin은 FIFO 방식으로 동작하며, malloc 요청으로 unsorted bin에서 검색된 청크들은 알맞은 사이즈인 경우 재할당을 하고 아닌경우 이때 각자의 bin(small or large)으로 들어갑니다.
즉, unsorted bin의 경우 단 한번의 재할당 기회만 주어집니다. Unsorted bin의 특징은 다음과 같습니다.

Unsorted bin의 특징

1개의 bin만 사용한다.
이중 연결리스트로 구성된다.
small, large chunk를 보관한다.
unsorted bin에서 적절한 bin을 찾는 시간이 적기 때문에 할당과 해제의 처리 속도가 빠르다.
Chunk 크기에 대한 제한이 없기 때문에 다양한 크기의 청크가 저장될 수 있습니다.
free() 된 청크는 unsorted bin에 보관되며, 메모리 할당 시 동일한 크기의 영역을 다시 요청하는 경우 해당 영역을 재할당한다.
FIFO 방식을 사용한다.
검색된 청크는 바로 할당되거나 실패하면 자신의 bin으로 들어간다.
unsorted chunk는 NON_MAIN_ARENA 플래그를 절대 세팅하지 않는다.

출처 : http://studyfoss.egloos.com/5206220

위 사진은 bins의 구조를 대략적으로 표현한 그림입니다. 맨 위에 index1 리스트가 바로 unsorted bin입니다.

실습으로 unsorted bin의 동작 과정을 알아보겠습니다.

Unsorted bin 실습

small bin

청크의 최소 사이즈 0x20 ~ 0x400 미만까지는 다 small bin으로 들어간다. 여기서 fastbin size도 포함되는데 일반적인 경우 0x80까지는 fastbin에 들어가지만, 리스트에 연결된 청크가 10개가 넘어가는 경우 0x20 ~ 0x80 사이즈 청크는 small bin에 들어간다.
62개의 bin을 사용함 ( small_bin[0]~small_bin[61] )
해당 bin에는 2개의 Free chunk가 서로 인접해 있을 수 없다.
- 같은 free small chunk가 아닌 fast,unsorted, in-use chunk와 인접해있는 경우는 경우는 결합하지 않는다.
- 해당 bin에 2개의 Free chunk가 서로 인접해 있을 경우 하나의 Free chunk로 병합된다.

small bin 실습

Large bin

bin의 개수 : 63개
- 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개 빈
  이 외의 남은 크기의 청크를 관리한다.
bin의 구성
- 각 빈들이 동일한 크기의 청크만을 포함하지 않는다. 동일 크기의 청크도 존재하고 다른 크기의 청크도 존재한다. 단 각 사이즈 별로 위에 설명한 것처럼 구성된다.
- 즉 해당 index가 나타내는 크기 보다 작은 크기의 청크들도 모두 포함된다.
- 인접한 free 청크들은 병합을 한다.
- 예를 들어 4k 크기를 위한 빈이 있다면 4096 byte의 청크만을 포함하는 것이 아닌, 4088, 4000, 3989 등의 크기를 가지는 청크들도 포함한다.
  - 할당의 효율성을 높이기 위해 크기 별로 정렬된다.
  - 이 때 fd_nextsize, bk_nextsize 필드가 이용된다.
  - 동일한 크기의 청크끼리는 fd_nextsize, bk_nextsize가 연결되지 않는다
- 무조건적인 큰 사이즈가 다 largebin에 들어가는 것은 아니라, 128kb 이상의 큰 사이즈 요청은 mmap() 시스템 콜을 이용하여 별도의 메모리 영역을 할당해준다.
  - 해당 크기의 청크는 bin에 속하지 않는다.
  - 이러한 청크들은 IS_MMAPPED 플래그가 설정된다.
  - 해당 영역이 Free될 경우 munmmap()을 호출해 해당 메모리 영역을 해지한다.
이렇게 하나의 빈에 다양한 크기의 청크가 저장되기 때문에 빈 내부에서 적당한 크기의 청크를 찾기 쉽도록 내림차순으로 정렬하여 저장된다. 따라서 맨 왼쪽이 가장 큰 청크가 되고, 맨 오른쪽이 가장 작은 청크가 된다.(sorted)
출처 : http://egloos.zum.com/studyfoss/v/5206220

위 사진과 같이 large bin이 관리가 된다.

Large bin 실습

Top Chunk

Top chunk는 아레나의 메모리 끝 부분에 위치한 청크를 뜻합니다. 이는 어떠한 bin에도 속하지 않습니다. 다음의 경우에 top 청크를 활용합니다.
- 사용자가 요청한 사이즈를 처리할 적당한 청크를 어떠한 bin에서도 찾을 수 없을때
  이런 경우 top청크를 확인합니다. 요청 사이즈가 현재 top 청크 크기보다 작을 경우, top 청크를 분할하여 할당해줍니다.
- 사용자가 요청한 사이즈를 처리할 적당한 청크를 어떠한 bin에서도 찾을 수 없고, 현재 top 청크 사이보다 요청 사이즈가 더 클때
  이런 경우도 2가지로 나뉩니다.
  1. top chunk < 요청 사이즈 < 128 kb
    이런 경우 main_arena는 sysmalloc 함수를 통해 sbrk syscall을 호출하여 확장시키고 thread_arena는 mmap으로 확장시킵니다.
  2. top chunk < 128kb < 요청 사이즈
    main_arena, thread_arena 둘다 mmap으로 확장시킵니다.
또한 fast bin 을 제외하고 모든 bin(small, unsorted)들은 top 청크 바로 이전 청크가 해제된 경우, top 청크와 병합하는데, 병합된 top 청크가 m_trim_threshold라는 내부적인 특정 임계값 보다 커졌다면, top 청크를 축소합니다.

요약

fastbin > unsorted bin > small bin > large bin 순으로 빠른 성능을 보입니다.
힙이 복잡하게 메모리 관리하는 이유
- 메모리의 효율적인 사용을 위함입니다.
  Ex) 내부 단편화, 외부 단편화

공부한 내용들은 glibc 2.23 기준이고 2.26 이후에는 tache 라는 기능이 추가되었습니다.

Free (glibc2.23)

병합 과정

Fast bin

Unsorted bin

small bin

Large bin

Top Chunk

요약

Further Reading

Heap 공부 1(allocator & glibc)

Heap 공부 2(chunk)

NX Bit [MS : DEP]