Heap 기초3

Heap 기초3

Date	@Mar 07, 2020
Person	jaeho jung

 

목차

1. Free (glibc 2.23 기준)

2. Fast bin

3. Unsorted bin

4. Small bin

5. Large bin

6. Top 청크

7. 정리

8. 참고문헌

---

 

1. Free (glibc 2.23 기준)

c언어를 기반으로 프로그래밍을 할때 동적할당을 위해서 malloc, free 를 자주 사용한다. 실제 메모리 상에서 free가 어떤식으로 진행되는지를 알아볼것이다. 개인적으로 free를 공부하면 malloc은 자연스럽게 이해가 된다고 생각한다. 우런 bins이 뭔지 알아보자.

 

쉽게 말해서, free 청크라는 훈련병들을 관리하는 조교라고 생각하면 된다. 또한 조교도 다 같은 조교가 아닌, 1소대 관리하는 조교, 2소대 관리하는 조교, 3소대 관리하는 조교, 이렇게 각자의 역할이 있다.

 

아레나에는 free된 청크들을 관리하기 위한 bins이 바로 조교같은 조재이다. 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영역까지 포함된다.

 

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

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

 

이러한 빈들이 존재하는 이유는, malloc 요청시 매번 메모리 할당을 요청하는것이 아닌, free 청크들을 재사용하기 위함이다. 사용자가 요청한 특정 사이즈의 청크가 특정 bin에 존재한다면, 그 빈을 때내서 돌려준다.

 

또한 물리적으로 인접해 있는 free 청크들은 일반적으로 서로 병합을 하여 큰 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와 결합을 진행한다

 

이제 각 빈들에 대해서 자세하게 알아보자

 

2. Fast bin

같은 크기를 기준으로 단일 연결 리스트로 연결된 일정크기 이하의 작은 청크를 의미한다. fast bin의 특징은 다음과 같다

 

---

Fast bin 특징

• LIFO 방식을 사용한다. (스택과 동일한 방식)

• 10개의 bin을 사용한다. (64bit에서는 디폴트로 7개 빈만을 사용하는 듯)

• 속도 향상을 위해 단일 연결 리스트로 구성됨. 다른 빈들은 다 이중 연결 리스트로 구성됨

• fast bin이 처리하는 메모리의 최대 크기는 "global_max_fast" 에 의해서 결정됨

  

  출처 :

  glibc malloc.c의 malloc함수 분석 약간의 exploit관점

  https://say2.tistory.com/entry/glibc-mallocc%EC%9D%98-malloc%ED%95%A8%EC%88%98-%EB%B6%84%EC%84%9D-%EC%95%BD%EA%B0%84%EC%9D%98-exploit%EA%B4%80%EC%A0%90

  

• 32 bit : 빈 크기는 최소 크기 16byte 부터 24, 32, 40, 48, 56, 64 byte 까지이다

• 64 bit : 빈 크기는 최소 크기 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이 어떻게 관리되는지 확인해보자

• fastbin.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main()
{
        char* a=(char*)malloc(0x10);
        char* b=(char*)malloc(0x20); 
        char* b2=(char*)malloc(0x25);
        char* c=(char*)malloc(0x30);
        char* d=(char*)malloc(0x40);
        char* d2=(char*)malloc(0x45);
        char* e=(char*)malloc(0x50);
        char* f=(char*)malloc(0x60);
        char* g=(char*)malloc(0x70);

        free(a);
        free(b);
        free(b2);
        free(c);
        free(d);
        free(d2);
        free(e);
        free(f);
        free(g);        

        return 0;
}

 

총 10번의 malloc 호출을 하고 전부다 free를 하는 단순한 코드이다. fastbin이 관리하는 0x20 ~ 0x80 사이즈를 확인하기 위해 사이즈별로 동적할당을 진행하였다. 또한 단일연결 리스트로 구성되는 걸 확인하기 위해 b2와 d2를 추가적으로 삽입하였다.

 

우선 맨 마지막 free(h)가 진행되기 직전 메모리 상태를 확인해보자.

 

 

• fastbin[0] : 0x20

  요청한 크기 0x10 + 헤더 0x10 이 합쳐저 총 0x20 bytes의 청크가 만들어졌고 0번 인덱스 binlist에 추가됨

• fastbin[1] : 0x30

  청크는 0x10 단위로 할당되므로 요청 사이즈 0x20과 0x25은 0x30 사이즈로 할당된다. 따라서 binlist의 0x30 사이즈인 인덱스 1에 추가된다. b청크(0x602020)이 먼저 추가되고, 그 이후에 b2청크(0x602050)가 추가된것을 확인할 수 있다

• fastbin[2] : 0x40

  요청크기 0x30 + 헤더 0x10 이 합쳐저 총 0x40사이즈 청크가 추가됨

• fastbin[3] : 0x50

  d청크와 d2청크 모두 헤더포함 0x50 사이즈이므로 3번 인덱스에 추가됨

• fastbin[4] : 0x60

  요청 크기 0x50 + 헤더 0x10이 합쳐저 총 0x60사이즈 청크가 추가됨

• fastbin[5] : 0x70

  요청 크기 0x60 + 헤더 0x10이 합쳐저 총 0x70사이즈 청크가 추가됨

• fastbin[6] : 0x80

  요청 크기 0x70 + 헤더 0x10이 합쳐저 총 0x80사이즈 청크가 추가됨

 

그림으로 표현하면 다음과 같은 상황이다

 

 

위 그림을 보면 a, c, e, f, g 청크들이 위치한 인덱스에는 단 하나밖에 free 청크가 없다. 이러한 청크들은 next free chunk를 가리키는 포인터가 저장되있는 fd가 0으로 세팅된다. 그 이유는 다음과 같다

 

현재 fastbin에 아무것도 없는 상태에서, 만약 0x20사이즈의 청크가 사용중이라고 해보자. 그렇다면 mem 영역에 사용자가 입력한 데이터가 들어가 있을 것이다.

 

0x20사이즈 K청크가 free되면 fastbin[0]에 들어가게 될텐데, 여기서 fd가 0으로 초기화 되지 않는다면,

fastbin[0]→K청크→K청크's 데이터

이렇게 리스트가 연결되어 다음에 동일한 사이즈인 0x20 가 요청들어왔을때 k청크를 반환하는 것이 아닌, k청크's 데이터값을 반환하려고 할것이다.

 

fastbins은 단일 연결리스트로 fd에 들어가있는 값을 보고 LIFO를 진행하기 때문이다. 아래의 그림을 보면 쉽게 이해가 될 것이다. (그림에 표현된 값들은 상관없는 값임)

 

 

따라서 처음 free된 청크들의 fd를 0으로 만드는 것이다. 이는 libc malloc, free 관련한 소스코드를 자세하기 분석할 예정이다. 어쩃든 이러한 이유로 코드에서 a, b, c, d, e, f, g 청크들의 fd 부분을 0으로 채워진다. 직접 확인해보자.

 

 

b2, d2 청크를 제외하곤 fastbin의 인덱스에 하나씩 들어가 있기 때문에 fd 부분이 0인것을 확인할 수 있다. 또한 아래의 사실을 알수 있다

• fastbin[1]→b2(0x602050)→b(0x602020)

• fastbin[3]→d2(0x602120)→d(0x6020c0)

 

또한 fastbin에서는 free 청크들을 병합하지 않기 떄문에 prev_inuse비트가 변하지 않는 것을 볼 수 있다. 하지만 fastbin은 아예 병합이 되는건 아니고 특별한 경우에 병합이 된다. 바로 fast chunk 사이즈 이상의 청크를 free 하려고 할때 병합이 되면서 unsorted bin으로 들어간다. 아래의 소스코드가 해당 부분이다

 

결론적으로 이렇게 fastbin들은 병합과정을 거치지 않기 때문에(특별 경우제외) fd만 필요할 분, bk가 필요없는 단일연결리스트로 구성된다. 이러한 특징 때문에 작은 사이즈의 청크들의 할당 및 해제가 빠르게 이루어지지만 내부 단편화를 발생시킬수 있는 단점이 존재한다.

 

 

3. Unsorted bin

bins의 첫번째 인덱스가 바로 Unsorted bin의 list로 사용된다. 이는 일종의 cache와 같은 역할로 free된 청크가 자기의 빈(small bin or large bin)으로 바로 들어가지 않고 먼저 unsorted bin으로 들어간다. (단 fastbin은 예외).

 

그 이후 malloc 요청시 동일한 크기의 영역을 다시 요청하는 경우 unsorted bin에 들어있는 청크를 바로 재사용 할 수 있게 한다. 이는 FIFO 방식으로 동작하며, malloc 요청으로 unsorted bin에서 검색된 청크들은 알맞은 사이즈인 경우 재사용을 하게 하고 알맞은 사이즈가 아닌 경우 이때 각자 자기의 bin(small or large bin)으로 돌아간다

 

즉, unsorted bin의 경우 단 한번의 재사용 기회만 주어진다. Unsorted bin의 특징은 다음과 같다

 

---

Unsorted bin 특징

• 해당 bin은 1개의 bin만 사용함

• 해당 bin은 이중 연결리스트로 구성됨

• 해당 bin은 small, large chunk를 보관함

• 해당 bin을 이용해 적절한 bin을 찾는 시간이 적기 때문에 할당과 해제의 처리속도가 빠름

• 해당 bin은 Chunk 크기에 대한 제한이 없기 때문에 다양한 크기의 청크가 해당 Bin에 저장될 수 있다

• free()된 청크는 unsorted bin에 보관되며, 메모리 할당 시 동일한 크기의 영역을 다시 요청하는 경우 해당 영역을 재사용함. (fast chunk는 예외)

• 해당 Bin은 FIFO 방식을 사용함

• 검색된 청크는 바로 재할당되거나 실패하면 원래의 Bin을 돌아감

• unsorted chunk는 NON_MAIN_ARENA 플래그를 절대 세팅하지 않음

---

 

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

 

위 사진은 bins들의 구조를 대략적으로 표현한 그림이다. 맨 위쪽의 index1의 리스트가 바로 unsorted bin을 의미한다

 

코드를 통해 unsorted bin의 동작 과정을 살펴보자

• unsorted.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main()
{
        char* a=(char*)malloc(0x20);
        char* a2=(char*)malloc(0x100); // small chunk
        char* b=(char*)malloc(0x14);
        char* b2=(char*)malloc(0x111); // small chunk
        char* c=(char*)malloc(0x30);
        char* c2=(char*)malloc(0x122); // small chunk
        char* d=(char*)malloc(0x24);
        char* e=(char*)malloc(0x22);


        free(b); // insert fastbin
        free(d); // insert fastbin

        free(a2); // insert unsorted bin
        free(b2); // insert unsorted bin
        free(c2); // insert unsorted bin

        char* f=(char*)malloc(0x100);
        char* g=(char*)malloc(0x110);   
        free(g);

        return 0;
}

 

• a, b, c, d, e는 fast chunk 사이즈 요청이므로 해당 청크들은 해제시 fatstbin으로 들어갈 것이다. 그리고 a2, b2, c2는 small chunk 이므로 해제시 unsorted bin을 거쳐 small bin으로 들어갈 것이다

 

• f는 a2와 동일한 사이즈인 0x100를 요청한다. 위에 free(a2)를 호출했음으로 unsorted bin에 해당 청크가 들어가 있을 것이다. 따라서 이 청크를 재사용하여 할당할 것이다

 

• free(a2)가 호출되기 직전 상황부터 확인해보자.

 

현재 free(b), free(d)가 호출되었으므로 fastbin[0]과 fastbin[1]에 해제된 b, d가 들어가 있다. 이 두개를 제외하고는 해제된 청크가 없으므로 unsorted bin에는 아무것도 없다

 

 

free(a2)가 호출된 직후 상황이다. unsorted bin에 a2청크의 주소가 들어가 있는 것을 볼 수 있다. 여기서 free(b2)가 호출되 된다면 unsorted bin에 추가될 것이다.

 

 

free(b2), free(c2)가 호출된 직후 상황이다. unsorted bin에 a2, b2, c2가 이중연결리스트로 연결되어 있는 것을 확인할 수 있다. unsorted bin은 FIFO 구조이므로 이 후 malloc 요청이 들어오면, unsorted bin을 뒤져 적절한 사이즈가 존재하는지를 제일 오른쪽부터 검색할 것이다

 

만일 들어온 요청 사이즈가 0x100 이면 헤더 포함 0x110이므로 한번에 찾게되고, 바로 재할당을 해준다. 하지만 들어온 요청 사이즈가 0x120이면 헤더 포함 0x130이므로 제일 왼쪽에 있는 청크를 할당해줘야 한다.

 

이를 위해 우측부터 검색을 시작하고, 0x110 사이즈는 탈락 , 0x120 사이즈도 탈락, 마지막 청크가 딱 맞으므로 이를 재할당할것이다. 따라서 앞서 검색을 진행했던 두개의 청크는 이 즉시 small bin으로 빠질것이다. 직접 확인해보자.

 

• ex) 0x100 재요청 직후 상황 (위 코드와 동일)

				...

				free(b);
        free(d);

        free(a2);   // 0x100
        free(b2);   // 0x110
        free(c2);   // 0x122

        char* sx=(char*)malloc(0x100);

				...

 

0x602160 다음에 <-> 0x602030 청크가 연결되어있었는데, 해당 청크를 재사용하여 반환해주었기 때문에 unsorted bin에서 빠졌다. 이번엔 0x100이 아닌 0x122를 요청한 직후를 살펴보자.

 

 

• ex) 0x122 재요청 직후 상황 (위 코드와 동일하고 sx 사이즈만 다름)

				...

				free(b);
        free(d);

        free(a2);   // 0x100
        free(b2);   // 0x110
        free(c2);   // 0x122

        char* sx=(char*)malloc(0x122);

				...

 

unsorted bin에 있던 것들이 재할당 해준것이 빠지고 다 small bin으로 들어간것을 확인할 수 있다. FIFO 구조이므로 검색을 한번이라도 한 청크들은 small bin으로 빠진다는 것을 확실히 알수 있다.

 

추가적으로 fastbin의 경우 물리적으로 인접한 free 청크들도 병합을 하지 않는다고 했다. 헌데 만약 다음과 같은 상황이면 우짤꾜?

 

현재 0x20 크기 청크가 해제되어 fastbin에 들어가 있는 상황이다. 근데 그 이전 청크가 그 이후 해제되어 unsorted bin에 들어갔다. unsorted bin부터는 물리적으로 인접한 free 청크들은 병합이 이루어지는데 현 상황에서 다음 청크가 free된 상태이지만 fastbin에 들어가있다

 

이런 경우 0x100 사이즈 의 small 청크가 해제될때 다음 청크의 prev_inuse 비트를 0으로 변경하긴 하지만 0x20 사이즈의 free 청크는 fastbin에서 관리되는 특징 때문에 그 다음 청크의 prev_inuse 비트가 현재 그대로 1로 세팅되어있을 것이다. libc 소스코드 중 _int_Free 함수부분에서 확인 가능하다

 

(아래 조건문에 포함되는 내용이 fastbin관련 로직이다.)

 

따라서 0x100 small 청크가 해제될때 0x20 청크의 다음 청크의 prev_inuse 비트를 확인하고, 현재 1로 세팅 되어있으므로 병합은 진행하지 않고 단순 자기자신의 다음 청크(0x20)의 prev_inuse 비트만 0으로 변경한다. 이 역시 소스코드에서 확인 가능하다

 

해당 else if 하위 로직이 관련 부분이다.

 

어쨋든 결론적으로 small chunk or large chunk 사이즈의 해제시 병합할수 있는 청크들은 병합을 하고 unsorted bin으로 들어간다.

 

추가적으로 사용자가 요청한 크기가 0x90인데 현재 unsorted bin에 0x120 크기의 청크가 들어가 있다면, 0x90을 분할하여 재할당해주고 나머지 0x30은 last_remainder 청크에 들어간다. 이는 지역 참조성을 증가시키는데 도움이 된다고 한다.

위의 그림과 같이 unsorted bin에서 분할되고 남은 청크가 저기 last_remainder에 들어간다

 

 

4. Small bin

MINSIZE < sizeof(chunk) < 1024 사이즈의 청크인 경우 small chunk로 분류되며 unsorted bin을 거쳐 small bin 에 들어간다. 소스코드에 small bin의 범위를 확인 가능하다.

 

1477 라인을 봐보자. 현재 청크 사이즈(sz)가 MIN_LARGE_SIZE 보다 작으면 small bin으로 분류된다. 그럼 MIN_LARGE_SIZE를 확인해보자.

 

MIN_LARGE_SIZE는 1475라인에서 계산이 된다. MALLOC_ALIGNMENT는 16이고 SIZE_SZ는 8이다. 따라서 계산을 해보면 MIN_LARGE_SIZE는 ( 64 - (16 > 2*8) ) * 16 = 1024이다.

 

즉 청크의 최소 사이즈 0x20 ~ 0x400 미만까지는 다 small bin으로 들어간다. 여기서 fastbin size도 포함되는데 일반적인 경우 0x80까지는 fastbin에 들어가지만, 리스트에 연결된 청크가 10개가 넘어가는 경우 0x20 ~ 0x80 사이즈 청크는 small bin에 들어간다. small bin의 특징을 몇개 알아보자

 

---

small bin

• FIFO 방식을 사용

• 62개의 bin을 사용함 ( small_bin[0]~small_bin[61] )

• 해제된 Small chunk를 보관함

• 이중 연결 리스트로 구성됨

• 0x20 ~ 0x400 미만의 크기를 가지는 chunk를 관리함

• 해당 bin에는 2개의 Free chunk가 서로 인접해 있을 수 없다
  • 같은 free small chunk가 아닌 fast,unsorted, in-use chunk와 인접해있는 경우는 경우는 결합하지 않음

• 해당 bin에 2개의 Free chunk가 서로 인접해 있을 경우 하나의 Free chunk로 병합됨

---

 

소스코드로 직접 확인해보자

• smallbin.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main()
{

        char* a=(char*)malloc(0x80);
        char* b=(char*)malloc(0x400);
        char* c=(char*)malloc(0x40);
        char* d=(char*)malloc(0x3e0);

        free(a);
        char* e=(char*)malloc(0x500);

        free(d);
        char* f=(char*)malloc(0x500);

        return 0;
}

 

a는 fast chunk 사이즈 큰 청크중 가장 작은 사이즈이고, d는 small bin 중 제일 큰 청크가 될 것이다.

또한 일부러 보기쉽게 인접하지 않게 free를 했다. return 0 바로 위 라인 (char* f 부분)이 실행된 직후의 메모리 상황을 살펴보자.

 

 

fast chunk size 보다 큰 값중 제일 작은 small bin size에 헤더포함 0x90 청크가 들어가있다. 또한 small bin의 가장 큰 사이즈인 0x3f0 사이즈의 청크가 61 인덱스에 들어가 있는걸 확인 할 수 있다.

 

만약 free 하려는 기준으로 이전 or 다음 청크가 free된 청크라면 병합이 이뤄지고, 병합된 청크는 다시 unsorted bin으로 들어갈 것이다.

 

 

5. Large bin

large bin은 0x400 이상의 청크가 저장되는 bin으로써, 메모리 할당과 반환의 속도가 fastbin, unsorted bin, small bin 중에서 가장 느리다. bin의 개수는 63개이며 large bin은 다른 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이 관리가 된다. 실제 디버깅을 통해서 largebin을 확인해보자

 

• largebin.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main()
{
        char* a0=(char*)malloc(0x3f0);
				char* b0=(char*)malloc(0x80);
				char* a1=(char*)malloc(0x400);
				char* b1=(char*)malloc(0x40);
        char* a2=(char*)malloc(0x410);
				char* b2=(char*)malloc(0x200);
				char* a3=(char*)malloc(0x420);
				char* b3=(char*)malloc(0x200);
				char* a4=(char*)malloc(0x430);
				char* b4=(char*)malloc(0x300);
        char* a5=(char*)malloc(0x440);
        char* b5=(char*)malloc(0x300);
        char* a6=(char*)malloc(0x450);
        char* b6=(char*)malloc(0x300);
        char* a7=(char*)malloc(0x460);
        char* b7=(char*)malloc(0x300);
        char* a8=(char*)malloc(0x470);
        char* b8=(char*)malloc(0x300);
	
        free(a0);
        char* e0=(char*)malloc(0x500);
				free(a1);
				char* e1=(char*)malloc(0x500);
				free(a2);
				char* e2=(char*)malloc(0x500);
				free(a3);
				char* e3=(char*)malloc(0x600);
        free(a4);
        char* e4=(char*)malloc(0x600);
        free(a5);
        char* e5=(char*)malloc(0x500);
        free(a6);
        char* e6=(char*)malloc(0x500);
        free(a7);
        char* e7=(char*)malloc(0x600);
        free(a8);
        char* e8=(char*)malloc(0x600);

	return 0;
}

 

위 코드는 보기 쉽게 병합이 진행되지 않게 malloc 및 free가 되는 로직으로 짰다. 요청한 사이즈 그대로 디버깅을 통해 largebin에 들어가는 것을 보기위함이다. 맨마지막 malloc이 호출된 직후 메모리 상황을 봐보자. (a로 시작하는 변수들이 의미있는 부분임)

 

• 현재 largebin[0]에 0x400부터 0x430 까지의 사이즈를 가진 청크가 들어가 있다. 또한 정렬이되어 맨 왼쪽이 가장 큰 사이즈를 갖는다.

• larebin[0] 의 각 청크들은 모두 사이즈가 다르므로 fd,bk와 fd_nextsize,bk_nextsize 모두 동일할 것이다.

 

 

6. Top 청크

Top 청크에 대해서 전에 설명하긴 했지만 bin들에 대해서 설명을 끝마친 상황에서 다시한번 특징들을 정리해보자.

 

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 청크를 축소한다

 

 

 

7. 정리

최종적으로 fastbin > unsorted bin > small bin > large bin 순으로 빠른 성능을 보인다. 힙이 이렇게 복잡하게 메모리를 관리하는 이유는 메모리의 효율적인 사용을 위함이다. 내부 단편화 혹은 외부 단편화를 최소화해야 하기 때문이다.

 

공부한 내용들은 glibc 2.23 기준이고 2.26 이후에는 tache 라는 기능이 추가되었다고 한다. 추후 해당 추가된 부분도 확인하여 공부할것이고, 소스코드를 직접적으로 제대로 분석해볼 생각이다

 

(정리한 내용에 틀린 부분이 있으면 말해주세요)

 

 

 

8. 참고문헌

• https://tribal1012.tistory.com/141

• https://tribal1012.tistory.com/78

• http://studyfoss.egloos.com/5206979

• https://www.lazenca.net/pages/viewpage.action?pageId=1147929#id-01.Malloc-glibc(ptmalloc2)-Largebin

• https://github.com/andigena/glibc-2.23-0ubuntu3/blob/master/malloc/malloc.c

• https://umbum.dev/386