ptmalloc2

ptmalloc은 리눅스에서 사용하는 memory allocator이다.

모든 프로세스는 실행 중에 메모리를 동적으로 할당하고 해제하는 과정이

매우 빈번하게 일어나는데 이 동작을 빠르고 메모리의 낭비 없이 이뤄지도록 하는 역할을 memory allocator이 한다.

 

ptmalloc2 역할

 

- 메모리 낭비 방지

  할당 요청이 발생하면 이전에 해제된 메모리 공간중 비슷한 크기의 메모리 공간이 있는지 탐색,

  작은 크기의 요청 발생시 해제된 메모리 공간 중 큰 메모리 공간이 있으면 그 영역을 나눠주기도 한다.

 

- 재사용

  빠른 메모리 재사용을 위해 동적할당된 메모리를 해제할 때 tcache 또는 bin이라는 연결리스트에 저장해둠

  

- 단편화 방지

  단편화가 심해지면 각 데이터 사이에 공간이 많아져 메모리 사용의 효율이 감소한다.

  이를 해결하고자 ptmalloc에서는 x64 환경에서는 16바이트 단위로 할당한다.

  또한 특정 조건을 만족하는 청크는 병합을 하고 필요할 때 나눠쓰는 방식으로 재사용율을 높인다.

 

---

청크 구조

 

prev_size : 크기는 8바이트이고 인접한 직전 청크의 크기 저장

size : 크기는 8바이트이고 현재 청크의 크기 저장

flags (A, M, P) :크기는 3비트이다

 - A : allocated arena

 - M : mmap'd

 - P : prev-in-use ( 직전청크 사용중인지 나타냄. ptmalloc은 이를 참조하여 병합이 필요한지 판단)

fd : 크기는 8바이트이고 연결리스트에서 다음 청크를 가리킴

bk :                            "                              이전 청크를 가리킴

 

---

bin & tcache

 

ptmalloc의 역할 파트에서 잠깐 설명했듯이 bin은 사용이 끝난 청크들이 저장되는 곳이다.

ptmalloc에는 총 128개의 bin이 정의되어 있다.

 

smallbin : 62개

largebin : 63개

unsortedbin : 1개

 

- small bin

32 ~ 1023 바이트 크기의 청크 보관

하나의 smallbin에는 같은 크기의 청크만 보관. index가 증가하면서 저장되는 청크의 크기는 16바이트씩 커짐.

즉, smallbin[0]에는 32바이트 청크, smallbin[1]에는 48바이트 청크 ...

이중 연결 리스트로 구성되어 있으며 FIFO(first in first out) 방식으로 재할당

smallbin은 병합 대상이기 때문에 메모리상에서 인접한 두 청크가 해제되어 있고, 이들이 smallbin에 들어있다면

이 둘은 병합된다.

 

- fast bin

일반적으로 프로그램에서 큰 크기 보다 작은 크기의 청크들이 더 많이 할당되고 해제된다.

그래서 ptmalloc은 작은 크기의 청크 할당과 해제를 효율적으로 하고자

32 ~ 176 바이트 크기의 청크들이 보관되며 16바이트 단위로 총 10개가 있다.

리눅스에서는 작은크기부터 7개의 fastbin을 사용한다. 즉, 32 ~ 128 바이트의 청크를 fastbin에 저장한다.

또한 단일 연결 리스트이기 때문에 unlink 과정을 수행하지 않아도 되고

파편화가 심하지만 속도는 빠른 LIFO(last in first out) 방식을 사용한다.

fastbin에 저장된 청크들은 병합이 되지 않아 병합에 사용되는 연산도 아낄 수 있다.

 

- large bin

1024 바이트 이상의 청크들이 보관되고 이중 연결 리스트로 구성된다.

한 largebin에 한가지 크기만 저장하지 않고 일점 범위 안의 크기를 갖는 청크들을 모두 보관한다.

예를 들어 largebin[0]에는 1024 ~ 1087 바이트 크기의 청크를 보관하며

largebin[32]는 3072 ~ 3583 바이트 크기의 청크를 보관한다.

largebin은 특정 크기의 청크만 모아서 보관하지 않기 때문에 재할당 요청에 빠르게 대응하기 위해

크기를 기준으로 내림차순 정렬을 하고 요청된 크기와 가장 비슷한 크기의 청크를 꺼내 재할당한다.

또한 연속된 largebin 청크는 병합 대상이다.

 

- unsorted bin

분류되지 않은 청크 보관하고 원형 이중 연결 리스트로 내부적으로 정렬되지 않는다.

즉, fast bin에 들어가지 않는 모든 청크들은 해제되었을 때 크기를 구분하지 않고 unsorted bin에 보관된다.

smallbin 크기(32 ~ 1023)의 요청이 오면 fastbin -> smallbin -> unsortedbin 순서로 탐색한다.

largebin 크기(1024 ~ )의 요청이 오면 unsortedbin을 먼저 탐색한다.

unsortedbin에서 적절한 청크가 발견되면 해당 청크를 꺼내어 사용한다.

이 과정에서, 탐색된 청크들은 크기에 따라 적절한 bin으로 분류된다.

unsortedbin에 해당하는 청크는 top 청크와 맞닿아 있고 해제된 상태라면 병합된다.

 

- arena

fastbin, smallbin, largebin 등의 정보를 모두 담고 있는 객체

모든 쓰레드가 공유하는 자원으로, 한 쓰레드가 이를 점유하면 race condition을 막기 위해 lock이 걸린다.

그런데 이 방식을 사용하면 병목현상이 발생할 수 있다.

그래서 64개의 arena로 락이 걸려 대기해야하는 경우 새로운 arena를 생성해서 이를 피할 수 있다.

그런데 생성 개수가 64개로 제한되어 이써 과도한 멀티 쓰레드 환경에서는 병목 현상이 발생할 수 있다.

이를 해결하고자 glibc 2.26에서는 tcache를 추가적으로 도입했다.

 

- tcache (thread local cache)

각 쓰레드에 독립적으로 할당되는 캐시 저장소를 지칭한다.

각 쓰레드는 64개의 tcache를 가지고 있고 fastbin과 동일하게 LIFO방식으로 사용되는 단일 연결 리스트이다.

하나의 tcache는 같은 크기의 청크들만 보관하고 리눅스에서는 각 tcache에 보관할 수 있는 청크의 개수를

7개로 제한하고 있다. 병합도 되지 않는다.

tcache에는 32 ~ 1040 바이트 크기의 청크들이 보관되고 해당 tcache가 가득 차면 적절한 bin으로 분류된다.

tcache는 위 설명과 같이 각 쓰레드가 고유가헤 갖는 캐시이기 때문에 레이스 컨디션을 고려하지 않고 이 캐시에 접근.

병목현상 완화가 가능하지만 tcache는 보안 검사가 많이 생량되어 있어 힙 익스에 취약하다.

 

---

 

chunk 할당 과정