04.Bins and Chunks

2018. 5. 24. 14:41

Bin

bin은 더블이나 싱글로 link된 free(할당되지 않은) chunks의 리스트이다. 청크의 크기에 따라 bin의 종류가 달라지는데

1. Fast bin 2. Unsorted bin 3. Small bin 4. Large bin 이 있다.

Fast bin은 아래와 같이 관리된다.

1
2
3
typedef struct malloc_chunk *mfastbinptr;
 
mfastbinptr fastbinsY[]; // chunks의 포인터들의 배열
cs

Unsorted, small 과 large bin은 단일 배열을 사용하여 관리된다.

1
2
3
typedef struct malloc_chunk* mchunkptr;
 
mchunkptr bins[]; // Array of pointers to chunks
cs

초기에, 프로세스 초기화 과정에 small, large bin은 비어있다.

각각의 bin은 배열의 두개의 값으로 표현되는데, bin리스트의 'HEAD'와 'TAIL' 포인터이다. fast bin은 싱글 링크드 리스트 구조이고, 두번째 값(TAIL)은 NULL값을 가진다.

Fast bins

패스트빈은 10가지 종류가 있다. 모두 다 싱글 링크드 리스트 구조이며 추가 삭제는 리스트의 앞쪽에서 일어난다. Last In First Out 구조를 가진다.

하나의 패스트빈은 모두 같은 사이즈의 chunks의 집합으로 이루어져있고 사이즈는 16 / 24 / 32 / 40 / 48 / 56 / 64 / 72 / 80 / 88 이 있다.

인접한 두개의 free된 fast chunk는 병합되지 않는다. 할당할 때에는 먼저 할당하려는 사이즈와 같은 크기의 사용하지 않는 청크가 fastbin에 존재

하는 지를 검사한다. 만약 존재한다면 바로 fastbin에서 빼오고 반환한다. 만약 없다면 다른 방식(top chunk 절단)을 통해 크기가 적합한 청크를

얻어와 반환한다. 하나의 청크를 프리(free)할 때에도, 먼저 해당 청크의 크기가 fastbin의 범위 안에 있는 지를 검사한다. 만약 있다면 그에 대응하

는 bin에 넣는다. 이름을 보면 뜻을 알 수 있다고, fastbin은 비교적 작은 사이즈의 청크들을 분배하고 회수한다. 그렇기 때문에 위에서 얘기한 bk

에 대한 작업은 진행하지 않는다. 그저 fd만 사용하여 더블 링크드 리스트가 아닌 싱글링크드 리스트를 구성하며 LIFO 원칙을 준수한다.

Unsorted bin

모든 chunk들은 free되어 처음에 unsorted bin에 추가된다. 최근에 free된 chunk들을 재사용 할 수 있도록 하기 위함.

First In First Out 형태로 동작하며 검색된 chunk는 바로 재할당 되더라도 원래의 bin으로 돌아가게 됨. 단 한번의 재사용 기회가 주어짐

double linked 리스트 구조를 갖으며 개수는 1개이다. 속도 향상

Small bin

small bin은 62 종류를 가지며 fast bin 보다는 느리지만 Large bin 보다는 빠르다. 더블 링크드 리스트 구조이며 First In First Out 방식으로

'HEAD'에서 삽입이 발생하는 동안 'TAIL'에서 삭제가 발생한다. fast bins처럼 같은 사이즈의 청크끼리 묶이며 사이즈는 16, 24 ... , 504바이트(8바이트 단위) 등

32bit

size : 0x10, 0x18, 0x20 ...... , 0x1F8(504)

이 있다. free된 두개의 청크가 있다면 병합을 진행한다.

Large bin

63가지의 bin을 가지며 더블 링크드 리스트 구조를 가진다. 512바이트 이상의 크기를 가지는 chunk모으며 크기가 같은 청크만 모으지 않는다.

'HEAD'에서 가장 큰 청크, 'TAIL'에서 가장 작은 청크 등의 순서로 정렬된다.

fd_nextsize와 bk_nextsize에 대한 필드가 존재한다고 생각하면 되고, 역시 인접한 두 청크가 free상태이면 병합을 진행한다.

만약 128KB 이상의 공간이 할당되는 경우에는 mmap() 시스템 콜을 거쳐 별도의 공간을 할당한 뒤에 청크가 생성된다.

그리고 이렇게 생성된 청크들은 bin에 속하지 않는다. IS_MMAPPED플래그로 체크하며 munmap()으로 해제한다.

oiehso0