TIL: ptmalloc2 🗃️

https://dreamhack.io/lecture/courses/98

ptmalloc2

ptmalloc2는 Linux의 Memory Allocator이다. ptmalloc2는 memory를 효율적으로 관리하기 위해 아래 세 가지 특징을 갖는다:

1. Memory 낭비를 방지하기 위해 memory allocation 요청이 들어오면 우선 free된 block 중에서 재사용할 수 있는 block이 있는지 확인한다.
2. tcache와 bin이라는 linked list에 free된 block들의 정보를 저장한다.
3. Fragmentation을 최소화하기 위해 alignment, coalescence, split을 사용한다. 64 bit machine에서 ptmalloc2는 memory 공간을 16 byte 단위로 할당한다.

Chunk

Chunk는 ptmalloc이 allocate하고 free하는 block을 의미한다. Header와 data로 구성되는데, header는 아래와 같이 구성된다.

bin

bin은 freed chunk가 저장되는 연결 리스트들이다. ptmalloc에는 총 128개의 bin들이 정의되어 있는데, 이 중 62개는 smallbin, 63개는 largebin, 1개는 unsortedbin이고, 나머지 2개는 사용되지 않는다.

smallbin

• 32 byte ~ 1008 byte 크기의 chunk가 저장됨.
• 각 bin 별로 정해진 크기의 chunk만이 저장되며, index가 증가함에 따라 저장되는 chunk의 크기는 16 byte씩 증가한다. (smallbin[0]에는 32 byte, smallbin[61]에는 1008 byte의 chunk가 저장된다.)
• Circular doubly linked list이며, FIFO 방식을 사용한다. (먼저 free된 chunk가 먼저 allocation을 위해 사용된다.) (FIFO는 속도, fragmentation 둘 다 중간)
• coalescence가 일어난다. ptmalloc2에서는 consolidation이라는 용어를 사용한다.

fastbin

• smallbin, largebin, unsortedbin과는 별도로 존재하는 bin으로, 작은 chunk가 반복적으로 allocate 및 free될 때 빠르게 작동하도록 하기 위해 존재한다.
• 32 byte ~ 176 byte 크기의 chunk가 저장됨. 16 byte씩 끊어 총 10개의 fastbin이 존재하는데, linux는 이 중 작은 크기부터 7개만을 사용한다. 즉, 32 byte ~ 128 byte의 chunk들을 저장한다.
• Singly linked list이며, LIFO 방식을 사용한다. (LIFO는 속도는 빠르지만 fragmentation이 심하다.)
• NO coalescence

largebin

• 1024 byte 이상의 크기를 갖는 chunk가 저장된다.
• 각 bin에 일정 범위 안의 크기를 갖는 모든 chunk가 저장된다. 이 범위는 index가 증가할수록 로그적으로 증가한다. (largebin[0]는 1024 ~ 1088 byte, largebin[32]는 3072 ~ 3584 byte)
• Circular doubly linked list이며, best-fit 방식을 사용한다. (속도가 느리지만 fragmentation이 가장 적음)
• coalescence가 일어난다.

unsortedbin

• 분류되지 않은 chunk들을 보관하는 bin이다. 하나만 존재하며, fastbin에 들어가지 않는 모든 chunk들은 이 bin에 보관된다.
• Circular doubly linked list이며, 내부는 정렬되어 있지 않다.
• smallbin 크기에 해당하는 청크를 할당 요청하면, ptmalloc은 fastbin 또는 smallbin을 탐색한 뒤 unsortedbin을 탐색한다.
• largebin 크기에 해당하는 chunk는 unsortedbin을 먼저 탐색한다. 이 과정에서 탐색된 chunk들은 각자의 크기에 따라 적절한 bin으로 이동된다.
• 불필요한 연산을 줄이기 위해 존재한다.

arena

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

Multi thread 환경에서 race condition을 막기 위해 arena에 lock을 적용하는데 (mutex 같은), 이 방식은 속도를 저하시키므로 최대 64개의 arena를 생성할 수 있도록 되어 있다. 그러나, 이보다 과도한 multi thread 환경에서는 64개의 arena도 부족하므로 속도 저하가 일어난다. ⇒ GLibc 2.26에서는 tcache를 추가로 도입했다.

tcache

• Thread local cache의 약자이다. 각 thread에 독립적으로 할당되는 cache 저장소이다.
• 각 thread는 64개의 tcache를 갖는다. 하나의 tcache는 같은 크기의 chunk만을 저장한다. 각각 최대 7개의 chunk를 넣을 수 있다.
• 32 byte ~ 1040 byte 크기의 chunk들이 보관된다. 이 범위의 chunk들은 allocate 및 free될 때 tcache를 가장 먼저 조회한다. chunk가 가득 찼을 땐 bin을 사용한다.
• Singly linked list이며, LIFO 방식을 사용한다.
• 각 thread 별로 갖는 cache이므로 arena의 bin을 사용할 일이 줄어든다. → arena 사용으로 인한 속도 저하가 줄어든다.