5.2 fastbin

5.2.1 설명

일반적으로 크기가 작은 청크들이 큰 청크들보다 빈번하게 할당되고 해제된다.

그래서 작은 청크들의 할당과 해제를 효율적으로 하는 게 전체적인 효율성 측면에서 중요하다.

이런 이유로 ptmalloc은 어떤 크기를 정해두고, 이보다 작은 청크들은 smallbin이 아니라 fastbin에 저장한다.

이들을 관리할 때 메모리 단편화보다 속도를 중요시 한다.

fastbin에서 32 바이트 이상 176 바이트 이하 크기의 청크들이 보관되며, 이에 따라 16바이트 단위로 총 10개의 fastbin이 있다.

리눅스는 이 중에서 작은 크기부터 7개의 fastbin만을 사용하므로,

리눅스에서 32바이트 이상, 128 바이트 이하의 청크들을 fastbin에 저장한다.

5.2.2 연결 방식

fastbin은 단일 연결 리스트이다.

단일 연결리스트이므로 청크를 꺼낼 때 꺼낸 청크의 앞과 뒤를 연결하는 unlink 과정을 수행하지 않는다.

또한, fastbin은 속도는 빠르지만, 다른 방법에 비해 파편화가 심한 LIFO 방식이다.

이에 따라 나중에 해제된 청크가 먼저 재할당 된다.

마지막으로, fastbin에 저장되는 청크들은 서로 병합되지 않는다.

그래서 청크 간 병합에 사용되는 연산도 아낄 수 있다.

5.2.3 실습

1. A, B 할당

A = malloc(0x20)

B = malloc(0x20)

2. A 해제

A가 해제되면, A의 시작 주소인 0x1234000이 fastbin에 추가된다.

3. B 해제

B가 해제되면, B의 시작 주소인 0x12340030이 fastbin에 추가되고,

LIFO 방식으로, 단일 연결 된다.

4. C 할당

C를 할당하기 위해, fastbin에 나중에 들어온 0x12340030이 재할당된다.

(LIFO 이므로)

5. D 할당

D를 할당하기 위해, 제일 처음들어 왔던 0x1234000이 재할당된다.

5.3 largebin

설명

largebin은 1024 바이트 이상의 크기를 갖는 청크들이 보관된다.

총 63개의 largebin이 있는데, smallbin, fastbin과 달리 한 largebin에서 일정 범위 안의 크기를 갖는 청크들을 모두 보관한다.

이 범위는 largebin의 인덱스가 증가하면 로그적으로 증가한다.

예를 들어, largebin[0]는 1024 바이트 이상, 1088 바이트 미만의 청크를 보관하며, largebin[32]는 3072 바이트 이상, 3584 바이트 미만의 청크를 보관한다.

largebin은 범위에 해당하는 모든 청크를 보관하기 때문에, 재할당 요청이 발생했을 때 ptmalloc은 그 안에서 크기가 가장 비슷한 청크(best-fit)를 꺼내 재할당한다.

이 과정을 빠르게 하려고 ptmalloc은 largebin안의 청크를 크기 내림차순으로 정렬한다.

largebin은 이중 연결 리스트이므로 재할당 과정에서 unlink도 되고, 또한, 연속된 largebin 청크들은 병합의 대상이 됩니다.

5.4 unsortedbin

5.4.1 설명

unsortedbin은 문자 그대로, 분류되지 않은 청크들을 보관하는 bin이다.

unsortedbin은 하나만 존재하며, fastbin에 들어가지 않는 모든 청크들은 해제되었을 때 크기를 구분하지 않고 unsortedbin에 보관된다.

fastbin: (32 바이트 이상 176 바이트 이하)

unsortedbin은 원형 이중 연결 리스트이며 내부적으로 정렬되지는 않는다.

smallbin 크기에 해당하는 청크를 할당 요청하면, ptmalloc은 fastbin 또는 smallbin을 탐색한 뒤 unsortedbin을 탐색한다.

largebin의 크기에 해당하는 청크는 unsortedbin을 먼저 탐색한다. unsortedbin에서 적절한 청크가 발견되면 해당 청크를 꺼내어 사용한다.

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

ptmalloc은 unsortedbin을 활용하여 불필요한 연산을 줄이고, 성능을 최적화한다.

5.4.2 예시

1. 어떤 청크를 해제한 다음에 비슷한 크기의 청크를 바로 할당하는 경우

이 상황에서 unsortedbin을 사용하면, 청크 분류에 낭비되는 비용을 없앨 수 있다.

또한, 청크의 크기가 largebin의 범위에 속하면 청크를 연결할 적절한 위치를 탐색해야하는데 이 과정이 생략된다.

2. 한번에 여러 청크들을 연속적으로 해제하는 경우

연속적으로 청크를 해제하면서, 병합하고 재분류하는 과정이 반복적으로 발생한다.

unsortedbin을 사용하면 이러한 비용도 줄일 수 있다.

6. arena

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

멀티 쓰레드 환경에서 ptmalloc은 Race Condition을 막기 위해 arena에 접근할 때, arena에 락을 적용한다.

그런데 이 방식을 사용하면 Race Condition을 막을 수 있지만, 반대로 병목 현상을 일으킬 수 있다.

ptmalloc은 이를 최대한 피하기 위해 최대 64개의 arena를 생성할 수 있게 한다.

arena에 락이 걸려서 대기해야하는 경우, 새로운 arena를 생성해서 이를 피할 수 있다.

그런데, 생성할 수 있는 갯수가 64개로 제한되어 있으므로 과도한 멀티 스레드 환경에서는 결국 병목 현상이 발생한다.

그래서 GLibc 2.26에서는 tcache를 추가 도입했다.

7. tcache

7.1 설명

tcache는 thread local cache의 약자이다.

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

tcache는 멀티 쓰레드 환경에 더욱 최적화된 메모리 관리 메커니즘을 제공한다.

7.2 연결 방식

각 쓰레드는 64개의 tcache를 가지고 있다.

tcache는 fastbin과 마찬가지로 LIFO 방식으로 사용되는 단일 연결리스트이며, 하나의 tcache는 같은 크기의 청크들만 보관한다.

리눅스는 각 tcache에 보관할 수 있는 청크의 갯수를 7개로 제한하고 있는데,

이는 쓰레드마다 정의되는 tcache의 특성상, 무제한으로 청크를 연결할 수 있으면 메모리가 낭비될 수 있기 때문이다. tcache에 들어간 청크들은 병합되지 않는다.

7.3 보관 방식

tcache에는 32 바이트 이상, 1040 바이트 이하의 크기를 갖는 청크들이 보관된다.

이 범위에 속하는 청크들은 할당 및 해제될 때 tcache를 가장 먼저 조회한다.

청크가 보관될 tcache가 가득찼을 경우에는 적절한 bin으로 분류된다.

7.4 보안 취약점

tcache는 각 쓰레드가 고유하게 갖는 캐시이기 때문에, ptmalloc은 레이스 컨디션을 고려하지 않고 이 캐시에 접근할 수 있다.

arena의 bin에 접근하기 전에 tcache를 먼저 사용하므로 arena에서 발생할 수 있는 병목 현상을 완화하는 효과가 있다.

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

7.5 실습

1. 청크 할당

8개의 청크를 할당한다.

2. 7개의 청크 해제

7개의 청크를 해제해서 tcache를 채운다.

3. 청크 하나 더 해제

청크를 하나 더 해제한다. tcache가 꽉 찼으므로, 이 청크는 fastbin에 보관된다.

4. 청크 재할당

청크를 새로 할당하고, tcache에 청크가 있으므로 꺼내서 사용한다.

5. 6개 청크 재할당

위에서, tcache에 청크를 꺼냈으므로, tcache에는 6개의 청크가 있다.

그리고, 이 6개의 청크를 재할당한다.

6. fastbin에서 청크 할당

tache가 비었으므로, fastbin에서 가져와서 할당

7. 결과

이렇게 chunk와 tcache, fastbin의 움직임을 확인할 수 있다.

마치며

Memory Allocator

프로세스의 요청에 따라 동적으로 메모리를 할당 및 해제해주는 주체, 또는 관련된 알고리즘들의 집합

dlmalloc, ptmalloc, jemalloc, tcmalloc 등이 있으며, 리눅스는 그 중에서 ptmalloc2를 사용한다.

구현되는 방식은 다소 차이가 있지만, 핵심 목표는 메모리 단편화의 최소화, 공간 복잡도 및 시간 복잡도의 최적화이다.

ptmalloc(pthread memory-allocation)

dlmalloc을 모태로하는 메모리 할당자. malloc, free, realloc 등을 기반으로 사용자의 동적 메모리 요청을 처리함.

사용하는 주요 객체로는 청크, bins, arena, tcache가 있음

청크(Chunk)

ptmalloc2가 메모리를 할당하는 단위.

bins

해제된 청크들을 보관함.

ptmalloc은 bin을 이용하여 청크를 빠르게 재할당하고, 단편화를 최소화함. bins에는 fastbin, smallbin, largebin, unsortedbin이 있음.

arena

ptmalloc이 관리하는 메모리들의 정보가 담겨있음.

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

병목 현상을 막기 위해 64개까지 생성 가능하지만, 이를 초과할 정도로 많은 연산이 발생하면 병목 현상이 일어남.

tcache

쓰레드마다 해제된 청크들을 보관하는 저장소.

멀티 쓰레드 환경에서 arena가 가지고 있는 병목 현상의 문제를 일부 해결해줄 수 있음.

쓰레드마다 할당되므로 용량을 고려하여 각 tcache당 7개의 청크만 보관할 수 있음.

Reference

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