Post

[Heap] Bin

Posted Updated
By br0nzu 19 min read

프로그램에서는 메모리 할당(malloc) 또는 해제(free)가 빈번하게 발생하는데, Free(해제)된 Chunk들은 이후 메모리 할당 요청이 들어올 경우 다시 재활용되어야 하기 때문에 관리되어야 한다.

단순하게 모든 Chunk들을 Linked List로 관리하면 편할수 있지만, 이는 malloc할 경우 Free된 Chunk를 찾기 위해 모든 Chunk를 탐색해야하며 속도 저하를 일으켜 프로그램의 전체 성능에 큰 영향을 미칠 것이다.

따라서, 성능 향상을 위해 bin이라는 개념을 도입하여 Free된 Chunk들만 관리한다.

Bin

Bin은 Free Chunk들을 크기 단위로 관리(binning)하는 역할이다. binning을 통해 관리되는 청크를 bin이라 부르며, 할당자에서 메모리 할당 요청시 적합한 청크를 재할당한다.

bin은 종류에 따라 크게 4가지 유형으로 나뉜다. bin에 대한 정보는 malloc_state구조체(Arena Header)에서 확인할 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

// glibc 2.23 malloc.c line 1686

struct malloc_state
{
  /* Serialize access.  */
  mutex_t mutex;

  /* Flags (formerly in max_fast).  */
  // 아레나 동작 모드 등을 저장하는 용도
  int flags;

  /* Fastbins */
  // Fast bin을 관리하기 위한 포인터 배열
  mfastbinptr fastbinsY[NFASTBINS];

  /* Base of the topmost chunk -- not otherwise kept in a bin */
  // topchunk 포인터
  mchunkptr top;

  /* The remainder from the most recent split of a small request */
  // small bin 할당을 수행할 때 블록을 분할하고 남은 잔여 블록을 가리키는 포인터
  mchunkptr last_remainder;

  /* Normal bins packed as described above */
  // fast bin을 제외한 일반 bin을 저장하는 배열
  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;
};

bin의 정보는 malloc_state구조체에서 관리한다.

  • fastbinsY[NFASTBINS]: fast bin을 관리하는 배열(10개)
  • bins[NBINS * 2 - 2]: unsorted bin, small bin, large bin을 관리하는 배열
    • bin[0]: N/A(사용되지 않음), 특수한 목적에 사용
    • bin[1]: unsorted bin(1개)
    • bin[2] ~ bin[63]: small bin(62개)
    • bin[64] ~ bin[126]: large bin(63개)
Binsfast binsmall binlarge binunsorted bin
Chunk Typefast chunksmall chunklarge chunksmall, unsorted chunk
Size of Chunk16 ~ 64byte(32bit), 32 ~ 128(64bit)1024byte 미만1024byte 이상제한 없음(Free Chunk만 등록 가능)
Bin 개수1062631

fast bin

fast bin은 인접한 청크들과 병합이 일어나지 않으며, 같은 크기를 기준으로 단일 연결 리스트로 연결된 일정크기 이하의 작은 청크이다.

fast bin의 특징은 다음과 같다.

  • 10개의 bin을 관리하며 fast bin의 상한 값보다 크기가 작은 청크들을 관리
    • 32bit
      • 상한값: 64byte(64*4/4)
      • chunk size 종류: 16, 24, 32, 40, 48, 56, 64byte
    • 64bit
      • 상한값: 128byte(64*8/4)
      • chunk size 종류: 32, 48, 64, 80, 96, 112, 128byte
      • 일반적으로 7개의 bin만 사용
  • LIFO 방식 사용(스택과 동일한 방식)
  • 속도 향상을 위해 단일 연결리스트로 구성 → bk는 사용되지 않음
  • free chunk가 서로 인접해 있어도 하나의 free chunk로 병합 X
    • fast bin은 작은 청크들을 관리하는 것이 목적이므로, 병합 X
    • free가 되어도 prev_inuse bit 변경 X
    • 단점: 메모리 시간이 지남에 따라 단편화(fragmentation)가 심해짐
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

// heap.c
// gcc -g -fno-stack-protector -z execstack -z norelro -no-pie -o heap heap.c -lpthread

#include<stdio.h>
#include<stdlib.h>

#define INDEX 14

int main() {
    char *fast_p[INDEX];
    char *malloc_p[INDEX];
    char *lifo_p;
    int i;

    for(i=0;i<INDEX;i++)
        fast_p[i] = (char*)malloc(0x10+i*0x8);

    puts("finish malloc!!");

    for(i=0;i<INDEX;i++)
        free(fast_p[i]);

    puts("creation fast bin!!");

    lifo_p = (char*)malloc(0x10);

    puts("exit!!");

    return 0;
}

fast bin

이는 두번째 puts에 bp를 걸고 디버깅한 결과이다.

  • 총 14개의 fast bin이 생성되었으며, 각 크기에 맞게 fastbin[0] ~ fastbin[6]까지 들어가 있음
  • 단일 연결리스트기 때문에 bk는 설정되어 있지 않음
  • Free가 되었음에도 불구하고 인접한 청크끼리 병합되지 않음 → prev_inuse bit가 0x1로 세팅

fast bin2

lifo_p에 bp를 걸고 디버깅한 결과이다.

fast bin은 LIFO 방식을 사용하기 때문에 fastbin[0]에서 제일 나중에 free된 0x601020이 할당된 것을 볼 수 있다.

unsorted bin

free된 청크가 small bin 또는 large bin에 바로 들어가는 것이 아니라, unsorted bin에 먼저 들어가게 된다.(fast bin 제외)

이후 메모리 할당 요청시 unsorted bin을 제일 먼저 확인하여 적절한 크기의 청크가 있으면 해당 청크를 재사용한다.

만약 적절한 크기의 청크가 존재하지 않으면, 청크들은 각각 자신의 bin(small bin, large bin)으로 들어간다.

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

  • 1개의 bin만 사용 → bin[1]
  • 이중 연결리스트로 구성되고, FIFO 방식을 사용
  • 청크 크기에 대한 제한이 없기 때문에, 다양한 크기의 청크가 저장될 수 있음
  • NON_MAIN_ARENA[A]플래그를 설정하지 않음
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

// heap.c
// gcc -g -fno-stack-protector -z execstack -z norelro -no-pie -o heap heap.c -lpthread

#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(0x140);   

    return 0;
}

a, b, c, d, e는 free가 되면 fast bin에 들어갈 것이다. a2, b2, c2는 free가 되면 unsorted bin을 거쳐 small bin으로 들어갈 것이다. f는 a2와 동일한 크기를 요청한다. a2가 free가 되면, unsorted bin에 a2의 청크가 들어있고 해당 청크를 f에 재할당 할 것이다.

unsorted bin

free(a2) 호출 직전 상황이다. b와 d가 free가 되었기 때문에 fastbin[0]과 fastbin[1]에는 b와 d가 들어갈 것이다. 또한, b와 d를 제외하고는 free된 청크가 없기 때문에 unsortbin에는 아무것도 없다.

unsorted bin2

free(a2) 호출 이후 상황이다. 이전 사진과 비교하면 unsortbin에는 a2가 들어간 모습을 볼 수 있다. 여기서 free(b2), free(c2)가 호출되면 unsortbin에 b2, c2가 추가 될 것이다.

unsorted bin3

free(b2), free(c2) 호출 이후 상황이다. unsortbin에 a2, b2, c2가 이중 연결리스트로 연결되어 있다. unsorted bin은 FIFO 방식을 사용하기 때문에 malloc 요청이 오면, 가장 먼저 들어온 청크부터 검색한다.

만약 요청한 크기가 unsorted bin에 있다면 해당 청크를 재할당하고, 요청한 크기가 unsorted bin에 없다면 새로운 청크를 할당하게 되고 unsorted bin에 있던 청크들은 각각 적절한 bin(small bin, large bin)으로 옮겨 진다.

unsorted bin4

char* f=(char*)malloc(0x100) 이후 상황이다. f는 a2와 동일한 크기를 요청하고, unsorted bin에 해당 청크가 있기 때문에 a2의 청크를 재할당 한 모습을 볼 수 있다.

unsorted bin5

char* g=(char*)malloc(0x140) 이후 상황이다. g는 0x140 만큼의 크기를 요청했지만 unsorted bin에 g가 요청한 크기만큼의 청크가 없어 새로운 청크를 할당 받고, unsorted bin에 있던 청크들은 적절한 bin으로 옮겨진 모습을 볼 수 있다.

1
2
3
4

...
    char* f = (char*)malloc(0x100);
    char* g = (char*)malloc(0x80);  
...

위 예시 코드에서 g의 요청 크기를 unsorted bin에 있는 크기보다 작은 크기로 변경하면 다음과 같은 결과가 나온다.

unsorted bin6

이는 best fit에 따라 unsorted bin에 있는 적합한 크기를 찾고, 해당 크기에서 요청한 크기를 분할하고 나머지 크기(last_remainder)는 unsorted bin에 들어가는 모습을 볼 수 있다.

small bin

청크의 크기가 MIN_LARGE_SIZE보다 작은 청크인 경우 small chunk로 분류되며, unsorted bon을 거쳐 small bin에 들어간다.

small bin의 특징은 다음과 같다.

1
2
3
4
5
6
7
8

// glibc 2.23 malloc.c line 1471
#define NSMALLBINS         64
#define SMALLBIN_WIDTH    MALLOC_ALIGNMENT
#define SMALLBIN_CORRECTION (MALLOC_ALIGNMENT > 2 * SIZE_SZ)
#define MIN_LARGE_SIZE    ((NSMALLBINS - SMALLBIN_CORRECTION) * SMALLBIN_WIDTH)

#define in_smallbin_range(sz)  \
  ((unsigned long) (sz) < (unsigned long) MIN_LARGE_SIZE)
  • 62개의 bin을 사용(bin[2] ~ bin[63])
  • 청크의 크기가 MIN_LARGE_SIZE보다 작은 청크들 관리
    • 32bit system: MIN_LARGE_SIZE = 512 byte
    • 64bit system: MIN_LARGE_SIZE = 1024 byte
    • 0x20 ~ 0x400 미만의 크기를 가지는 청크를 관리
  • 이중 연결리스트로 관리하며, FIFO 방식을 사용
  • small bin에 2개의 Free chunk가 물리적으로 서로 인접해 있을 경우 하나의 Free chunk로 병합됨
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

// heap.c
// gcc -g -fno-stack-protector -z execstack -z norelro -no-pie -o heap heap.c -lpthread

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

char* f=(char*)malloc(0x500)에 bp를 걸고 디버깅한 결과이다.

small bin

a는 smallbin[7]에 들어가고, d는 smallbin[61]에 들어간 모습을 볼 수 있다. 또한, a와 d의 청크가 물리적으로 서로 인접하지 않아 별도의 청크로 남아 있는 모습을 볼 수 있다.

large bin

small bin과 같은 방식으로 동작하지만, small bin과 fast bin처럼 정해진 크기 단위로 관리하는 것이 아니라 특정 범위 단위에 따라 관리하기 때문에 다양한 크기를 저장한다. 이로 인해 삽입에 대한 정렬이 수동으로 이루어지기 때문에 메모리 할당 또는 반환 속도가 가장 느리다.

large bin의 특징은 다음과 같다.

  • 청크의 크기는 MIN_LARGE_SIZE보다 같거나 큰 청크들을 관리한다.
    • 32bit system: MIN_LARGE_SIZE = 512 byte = 64bit system: MIN_LARGE_SIZE = 1024 byte
  • 63개의 bin을 사용하며(bin[64] ~ bin[126]) 특정 범위 단위로 관리
    • largebin[0] ~ largebin[31]: 32개의 large bin으로, 64(0x40) 바이트씩 증가하면서 해당 사이즈 범위에 해당하는 청크를 관리
    • largebin[32] ~ largebin[47]: 16개의 large bin으로, 512(0x200) 바이트씩 증가하면서 해당 사이즈 범위에 해당하는 청크를 관리
    • largebin[48] ~ largebin[55]: 8개의 large bin으로, 4096(0x1000) 바이트씩 증가하면서 해당 사이즈 범위에 해당하는 청크를 관리
    • largebin[56] ~ largebin[59]: 4개의 large bin으로, 32768(0x8000) 바이트씩 증가하면서 해당 사이즈 범위에 해당하는 청크를 관리
    • largebin[60] ~ largebin[61]: 2개의 large bin으로, 262144(0x40000) 바이트씩 증가하면서 해당 사이즈 범위에 해당하는 청크를 관리
    • largebin[62]: 1개의 large bin으로, 이외 남은 크기 청크 관리
  • 각 bin들이 동일한 크기의 청크만을 포함하지 않는다.
    • 동일 크기의 청크도 존재할 수 있고, 다른 크기의 청크도 존재한다.
  • 범위 내 가장 큰 크기의 청크가 제일 앞에 오도록 설정(내림차순)된다.
  • 이중 연결리스트로 구성되며, FIFO 방식을 사용
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

// heap.c
// gcc -g -fno-stack-protector -z execstack -z norelro -no-pie -o heap heap.c -lpthread

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

아래는 char* e8=(char*)malloc(0x600)에 bp를 걸고 디버깅한 결과이다.

large bin

largebin[0]에 0x400부터 0x430까지의 크기를 가진 청크가 있는 모습을 볼 수 있다. 또한, largebin[0]에서 내림차순으로 정렬되어 있다.

large bin2

정리

  • fastbinsY[NFASTBINS]: fast bin을 관리하는 배열(10개)
    • 인접한 Free 청크가 존재해도 병합 X
    • 단일 연결리스트로 LIFO 방식
  • bins[NBINS * 2 - 2]: unsorted bin, small bin, large bin을 관리하는 배열
    • bin[0]: N/A(사용되지 않음), 특수한 목적에 사용
    • bin[1]: unsorted bin(1개)
      • small bin, large bin에 삽입되기 전, 재할당을 위한 1번의 기회가 주어짐
      • 이중 연결리스트로 FIFO 방식
    • bin[2] ~ bin[63]: small bin(62개)
      • 인접한 Free 청크가 존재하면 병합
      • 이중 연결리스트로 FIFO 방식
    • bin[64] ~ bin[126]: large bin(63개)
      • 인접한 Free 청크가 존재하면 병합
      • 이중 연결리스트로 FIFO 방식

최종적으로 fast bin > unsorted bin > small bin > large bin 순으로 빠른 성능을 보인다.

Ref

[1] heap - glibc malloc (feat. bin)

[2] Heap 기초3

[3] 시스템해킹 튜토리얼 - Heap Concept Tutorial

[4] glibc 2.23 malloc

0x00. Computer Science, 0x00. Theory
heap bin