[BlackHat Heap] Binning

메모리가 free() 된 후에는, bin이라는 링크드 리스트에 저장된다. 검색을 위해서 주어진 청크에서 가장 빠른 액세스를 허용하는 크기로 정렬이된다.

즉, free() 할 때, 실제로 운영체제로 리턴이 되지않지만 나중에있을 할당을 위해 빈의 linked list로 저장된다.

bin은 링크드 리스트에대한 포인터 배열이다. 기본적으로 fastbin과 normal bin이 존재한다.

fastbin을 사용하기위해서는 작은 청크를 가져야한다. free() 될때 주변 청크와 병합되지않고 정렬되지않으며, single linked list를 갖는다.

청크의 구조체는 normal 청크와 동일하며, 표현법만 다르다. 기존의 FIFO 방식과 달리 LIFO 방식으로 제거되고, 청크가 통합되지 않아 액세스 속도가 정상적인 청크보다

빠르기때문에 fastbin의 단편화 속도가 빨라졌다.

사이즈가 0~80 까지의 chunk를 포함하는 10개의 fastbin을 갖게된다. 

number : fastbin배열에 대한 index

hold chunk sizes : bin이 보유 할 크기 범위

real chunk size : 실제 크기

malloc() / realloc() 은 free()된 모든 청크를 bin에 넣는다. 크기가 512바이트보다 작다면 small chunk로 간주하게되고, small chunk bin은 주어진 chunk의 모든 크기가 

같은 크기이기때문에 정렬되지 않는다.

그러나 fastbin 특정환경에서는 통합되기때문에 fastbin범위에 속한 크기의 normal chunk가 있는거처럼 보일 수 있다.

large chunk는 128바이트와 512바이트 미만에서 처리된다. 또, 128k size 보다 큰 청크가 할당되면 mmap()으로 직접 할당된다.

large chunk는 크기가 작은 순으로 정렬된 chunk가 들어가있고, FIFO 순서로 할당된다. 

마지막으론 top chunk와 last_remainder chunk가 존재한다.

[ Top Chunk ]

 top chunk는 사용 가능한 메모리의 경계를 차지하는 청크이다. bin의 적절한 청크가 없는 경우에 사용되고, last_remainder 청크가 맞지 않을때 요청에 맞게

통합 될 청크가없는경우 사용된다.

할당 된 청크가 자유로운 상태에서 맨 위 청크와 경계를 맞추면 통합되고, 축소될 수 있다. 간단히 말해서 top chunk는 메모리의 지정된 위치를 제외하고는 다른

모든 청크와 같으며 항상 이전에 사용 된 플래그 세트가 있다. 일반적으로는 항상 존재하는것처럼 처리한다.

[ last_remainder ]

 

 last_remainder 청크는 임의의 빈에 정확하게 들어맞는 small chunk에 대한 할당이 있어야한다. 할당 할 때, last_remainder chunk보다 크지만 bin의 블록

보다 작으면 청크가 다시 분할한다.