what is Heap & how it work

ptmalloc2

ptmalloc2

ptmalloc2(pthread malloc 2)는 Wolfram Gloger가 개발한 Memory Allocator로, Doug Lea의 dlmalloc을 개선한 ptmalloc의 두 번째 버전입니다. 이하에서는 버전을 제거하고 ptmalloc이라고 부르겠습니다. ptmalloc은 리눅스에서 사용하고 있으며, GLibc에 구현돼 있습니다.

>> 즉, 현재 사용되고 있는 heap 방식은 ptmalloc2 방식이다.

당연히 이러한 Memory allocator을 사용하는 이유는 다음과 같다.

메모리 낭비 방지

빠른 메모리 재사용

메모리 단편화 방지

ptmalloc2의 객체들

ptmalloc2는 청크(Chunk), bin, tcache, arena를 주요 객체로 사용한다. 이에 대해 알아보자

Chunk

→ 할당한 메모리 공간의 나타낸다.

사진을 보면 알겠지만, 사용하고 있는 청크와 free 된 후에 청크는 상태가 아예 다르다.

다음과 같은데 여기서 눈여겨 볼점은 fd 와 bk 의 존재이다. 해제된 청크에만 있다는 것과 다음청크를 가리킨 다는 것은 이를 변조하면 exploit이 가능하게 된다.

bin

사용이 끝난 청크들이 저장되는 객체 , 빠르게 재사용할 수 있게 하기 위함

ptmalloc에는 총 128개의 bin이 정의되어 있다. 이 중 62개는 smallbin, 63개는 largebin, 1개는 unsortedbin으로 사용되고, 나머지 2개는 사용되지 않음

bin의 종류에는 smallbin , fastbin , largebin 등이 있다.

일단 bin의 종류가 많은 이유는 유저가 할당하고 free한 chunk의 크기 별로 정리를 하기 위함이다. 즉, 분리수거를 위해 여러 종류의 bin이 있는 것

공부하다 보니 내가 직접 분석을 했다.

출처 :

Small bin

출처 :

small bin의 특징을 간추리자면, 위에gif로 한번에 알 수 있는데 일단 다음과 같은 중요한 특징이 있다.

1. FIFO

먼저 free 되어서 bin에 들어온 chunk가 먼저 다시 할당된다.

FIFO 방식은 단편화를 줄일 수 있다고 함

2.consolidation

2개의 인전한( 딱 붙은 ) 메모리가 모두다 free 가 된다면 굳이 병합(consolidation)을 안할 이유가 없다

일단 병합을 하면 병합된 위치에 다른 크기에 chunk를 넣을 수도 있는 것이며 단편화를 막을 수 있기 때문이다.

사진에서 free 된 B와 C 가 B 하나만으로 병합되는 것처럼 하나로 병합된다.

3.이중 연결 리스트

이중 연결 리스트 형식을 가진다. 즉, freed 된 chunk 형태에서 fd , bk 가 다 쓰인다.

여기서 헷갈리면 안되는게 그럼 0x25를 할당하고 free 하면 0x30 으로 가나요 0x40으로 가나요? 라고 할 수 있다. ( 0x25 + 헤더크기 니깐 ) 그런데 알다시피 청크는 0x10 단위로 관리된다. 즉, 0x25크기를 할당 하든 0x30 을 할당하든 모든 0x30 + 0x10(헤더 크기) 인 0x40 으로 할당 되며 당연히 청크의 크기가 0x40 이라는 거임

fast bin

작은 것에 대한 것을 다루다 보니 단편화 방지 , 메모리 관리에 힘을 쓰기 보다는 속도, 효율 중점이다.

위에 표에서는 fast bin 이 10개가 있다고 했는데 리눅스에서는 7개만 실질적으로 사용한다. 그래서

32 바이트 이상 176 가 아닌 32~128 이라고 하는 것이다.

중요한 특징

1.LIFO

small bin가 다르게 가장 최근에 free 된 청크를 다시 사용한다

2.단일연결 리스트

또한 단일 연결 리스트로 fd 밖에 있지 않다

large bin

largebin은 1024 바이트 이상의 크기를 갖는 청크들이 보관됩니다. 총 63개의 largebin이 있는데, smallbin, fastbin과 달리 한 largebin에서 일정 범위 안의 크기를 갖는 청크들을 모두 보관합니다. 이 범위는 largebin의 인덱스가 증가하면 로그적으로 증가합니다. 예를 들어, largebin[0]는 1024 바이트 이상, 1088 바이트 미만의 청크를 보관하며, largebin[32]는 3072 바이트 이상, 3584 바이트 미만의 청크를 보관합니다. 이런 방법을 사용하면 적은 수의 largebin으로 다양한 크기를 갖는 청크들을 관리할 수 있습니다.

largebin은 범위에 해당하는 모든 청크를 보관하기 때문에, 재할당 요청이 발생했을 때 ptmalloc은 그 안에서 크기가 가장 비슷한 청크(best-fit)를 꺼내 재할당합니다. 이 과정을 빠르게 하려고 ptmalloc은 largebin안의 청크를 크기 내림차순으로 정렬합니다. largebin은 이중 연결 리스트이므로 재할당 과정에서 unlink 도 동반됩니다. 또한, 연속된 largebin 청크들은 병합의 대상이 됩니다.

→ 대충 알겠지만, 그동안 small bin, fast bin은 0x10 단위로 딱딱 나누어서 bin이 존재하였다. 하지만 large bin을 이런식으로 관리할 수가 없다. 커버하는 크기가 1024부터 엄청 큰 범위이기 때문이다. 따라서 small bin , fast bin은 [n] , [n+1] 이 무조건 0x10 차이가 나겠지만, large bin은 이 크기가 지수함수로 관리 하겠다는 거다. 그럴려면 당연히 [n] , [n+1] 사이 범위의 크기를 가지는 청크들을 같이 보관한다는 의미임

unsorted bin

unsortedbin은 문자 그대로, 분류되지 않은 청크들을 보관하는 bin입니다. unsortedbin은 하나만 존재하며, fastbin에 들어가지 않는 모든 청크들은 해제되었을 때 크기를 구분하지 않고 unsortedbin에 보관됩니다. unsortedbin은 원형 이중 연결 리스트이며 내부적으로 정렬되지는 않습니다.

smallbin 크기에 해당하는 청크를 할당 요청하면, ptmalloc은 fastbin 또는 smallbin을 탐색한 뒤 unsortedbin을 탐색합니다. largebin의 크기에 해당하는 청크는 unsortedbin을 먼저 탐색합니다. unsortedbin에서 적절한 청크가 발견되면 해당 청크를 꺼내어 사용합니다. 이 과정에서, 탐색된 청크들은 크기에 따라 적절한 bin으로 분류됩니다.

ptmalloc은 unsortedbin을 활용하여 불필요한 연산을 줄이고, 성능을 최적화합니다. 연구에 따르면, 어떤 청크를 해제한 다음에 비슷한 크기의 청크를 바로 할당하거나, 또는 한번에 여러 청크들을 연속적으로 해제하는 경우가 빈번하게 발생한다고 합니다.

전자의 상황에서 unsortedbin을 사용하면, 청크 분류에 낭비되는 비용을 없앨 수 있습니다. 또한, 청크의 크기가 largebin의 범위에 속하면 청크를 연결할 적절한 위치를 탐색해야 하는데 이 과정도 생략할 수 있습니다. 한편, 후자의 상황에서는 연속적으로 청크를 해제하면서, 병합하고 재분류하는 과정이 반복적으로 발생합니다. unsortedbin을 사용하면 이러한 비용도 줄일 수 있습니다.

→ 일단 한마디로 요약하자면 , 캐시라는 의미이다. 일단 fast bin 크기의 청크들 말고는 여기에 먼저 들어간다. 근데 이제 다시 할당을 할려면 각각의 크기의 bin을 찾고는 없다면( 당연히 일단 여기를 찾아야지 확실하게 있는 얘들인데 ) 이 캐시 역할을 하는 unsorted bin을 뒤적뒤적 할 것이다. 근데 FIFO 방식이라서 버려진 얘들이 순서대로 있기 때문에 하나하나 순서대로 뒤질텐데 만약 적당하다면 사용하고 아니라면 unsorted bin에 있던거를 뒤적뒤적 한김에 해당 사이즈에 bin으로 옮긴다.

‣← 여기에 자세한 정보

공부하다 보니 내가 직접 분석을 했다.

arena

arena는 fastbin, smallbin, largebin 등의 정보를 모두 담고 있는 객체입니다. 멀티 쓰레드 환경에서 ptmalloc은 레이스 컨디션 을 막기 위해 arena에 접근할 때 arena에 락 을 적용합니다. 그런데 이 방식을 사용하면 레이스 컨디션은 막을 수 있지만, 반대로 병목 현상을 일으킬 수 있습니다.

ptmalloc은 이를 최대한 피하기 위해 최대 64개의 arena를 생성할 수 있게 하고 있습니다. arena에 락이 걸려서 대기해야 하는 경우, 새로운 arena를 생성해서 이를 피할 수 있습니다. 그런데, 생성할 수 있는 갯수가 64개로 제한되어 있으므로 과도한 멀티 쓰레드 환경에서는 결국 병목 현상이 발생합니다. 그래서 glibc 2.26에서는 tcache를 추가적으로 도입했습니다.

→ 핵심을 말하자면 bin 정보들을 담고 있는 겍체가 이제 arena 인데 이를 당연히 여러 쓰레드에서 동시에 접근할 것이다. 따라서 레이스 컨디션을 방지 하기 위해 lock을 걸건데 이는 당연히 기다리는 overhead가 존재하게 되기에 문제가 된다. 그래서 여러 arena를 두게 된다

알겠지만, 멀티 스레드 프로세스에서 각각의 스레드가 가지고 있는 건 레지스터( rip) , 스택이다. 즉, 힙은 스레드 들이 같이 써야 하는 자원이다. 이를 여러 64개의 arena을 통해 병목을 방지하고 lock을 걸어 race condition을 방지하겠다는 말이다.

tcache

전에 arena 에서 arena 객체가 여러 쓰레드가 사용해서 여러 문제가 있었고 이를 해결하기 위해 여러 mitigation을 사용했다. 그럼 arena 를 사용하기 전에 쓰레드 마다 캐시를 두면 어떨까? 라는 생각에서 나온게 tache 이다. → 성능 향상의 목표만을 보고 나온 기술이기에 보안성이 약함

각 쓰레드는 64개의 tcache를 가지고 있습니다. tcache는 fastbin과 마찬가지로 LIFO 방식으로 사용되는 단일 연결리스트이며, 하나의 tcache는 같은 크기의 청크들만 보관합니다. 리눅스는 각 tcache에 보관할 수 있는 청크의 갯수를 7개로 제한하고 있는데, 이는 쓰레드마다 정의되는 tcache의 특성상, 무제한으로 청크를 연결할 수 있으면 메모리가 낭비될 수 있기 때문입니다. tcache에 들어간 청크들은 병합되지 않습니다.

→ 좀 어려울 수도 있지만 64개의 각각 다른 크기를 가지는 tcache가 생길 수 있으며, 각각의 tcache는 7개를 가질 수 있다는 의미이다.

다음과 같이 tcache_perthread_struct 에서 관리하며, 64개의 배열로 되어있고 , 각각의 배열 값은 tcache_entry의 주소를 가지고 있는 형태이다.

tcache에는 32 바이트 이상, 1040 바이트 이하의 크기를 갖는 청크들이 보관됩니다. 이 범위에 속하는 청크들은 할당 및 해제될 때 tcache를 가장 먼저 조회합니다. 청크가 보관될 tcache가 가득찼을 경우에는 적절한 bin으로 분류됩니다.

→ 기본이 tcache이 이며, 이 캐시가 가득 찾을때 비로서 arena 의 bin으로 들어가게 된다. ( 여기서도 unsorted bin이라는 캐시 느낌의 bin이 있었음 )

좀 더 이해를 쉽게 그림을 같이 첨부하자면,

( 출처 : 까망눈 연구소 heap4)

free 함수가 invoke 되었을때 ,hook → init이 안되어 있으면 init → 한뒤에 free 함수로 들어오는데 → 이때 tcache_put 을 통해 tcache에 넣는다. 그런데 앞에서 언급했다 싶이 tcache가 가득 차 있으면, 그제서야 bin으로 간다.

반대로 malloc에 flow도 같이 알아보자면,

딱 보았을때 hook → init → tcache 확인 → ( 없으면 ) malloc 내부 함수 실행 후 → bin 확인으로 넘어간다. ( 그리고 tcache가 이때 비어있으면 넣고 → 주소를 반환한다.

tcache는 각 쓰레드가 고유하게 갖는 캐시이기 때문에, ptmalloc은 레이스 컨디션을 고려하지 않고 이 캐시에 접근할 수 있습니다. arena의 bin에 접근하기 전에 tcache를 먼저 사용하므로 arena에서 발생할 수 있는 병목 현상을 완화하는 효과가 있습니다.

tcache는 보안 검사가 많이 생략되어 있어서 공격자들에게 힙 익스플로잇의 좋은 도구로 활용되고 있다.

아래에서 tcache를 활용한 메모리 할당과 해제 과정을 살필 수 있습니다.

당연히 tcache는 스레드 마다 처리 되므로 각각의 스레드 들이 이 정보를 공유 하지 않는다. 즉, freed된 청크 들에 대해 경쟁이 발생하지 않는다