Memory Allocator
동적 메모리의 할당 및 해제를 효율적으로 관리하기 위한 알고리즘
ptmalloc2
개요: 리눅스에서 사용되는 Memory Allocator 알고리즘. ptmalloc2는 어떤 메모리가 해제되면, 해제된 메모리의 특징을 기억하고 있다가 비슷한 메모리의 할당 요청이 발생하면, 그 해제됐던 메모리를 비슷한 callee에게 할당해준다.
(구글은 tcmalloc, 페이스북이나 파이어폭스는 jemalloc을 사용)
ptmalloc의 역할
1. 메모리 낭비 방지
해제된 메모리 공간 중에서 요청된 크기와 같은 크기의 메모리 공간이 있다면 이를 그대로 재사용하게 한다. and 작은 크기의 할당 요청이 발생했을 때, 해제된 메모리 공간 중 매우 큰 메모리 공간이 있으면 그 영역을 나누어 주기도 한다.
2. 빠른 메모리 재사용
ptmalloc은 메모리 공간을 해제할 때, tcache 또는 bin이라는 연결 리스트에 해제된 공간의 정보를 저장해둔다. tcache와 bin은 여러 개가 정의되어 있으며, 각각은 서로 다른 크기의 메모리 공간들을 저장한다. 이렇게 하면 특정 크기의 할당 요청이 발생했을 때, 그 크기와 관련된 저장소만 탐색하면 되므로 더욱 효율적으로 공간을 재사용할 수 있다.
3. 메모리 단편화 방지
a) 내부 단편화 == 할당한 메모리 공간의 크기에 비해 실제 데이터가 점유하는 공간이 적을 때 발생
b) 외부 단편화 == 할당한 메모리 공간들 사이에 공간이 많아서 발생하는 비효율을 의미
- ptmalloc은 단편화 문제를 줄이기 위해 "정렬(Alignment), 병합(Coalescence), 분할(Split)"을 사용한다.
64비트 환경에서 ptmalloc은 메모리 공간을 16바이트 단위로 할당해준다.
ex) 4바이트를 요청하면 16바이트를, 17바이트를 요청하면 32바이트를 할당
- 또한 ptmalloc은 해제된 공간들을 "병합 or 분할" 하여 새로운 크기의 공간을 창조하기도 한다.
ptmalloc의 주요 객체
Chunk
-ptmalloc이 할당한 메모리 공간을 의미
-Chunk는 크게 헤더와 데이터로 구분된다.
헤더에는 청크 관리에 필요한 정보가 담겨 있으며, 데이터에는 사용자가 입력한 데이터가 저장된다.
-헤더는 청크의 상태를 나타내므로 사용 중인 청크(in-use)의 헤더와 해제된 청크(freed)의 헤더는 구조가 다르다.
-사용 중인 청크(In-use Chunk)는 fd와 bk를 사용하지 않고, 그 영역에 사용자가 입력한 데이터를 저장한다.
Chunk 헤더의 요소
| prev_size | 8바이트 | 인접한 바로 앞 청크의 크기. 청크를 병합할 때 바로 앞의 청크를 찾는 데 사용된다. |
| size | 8바이트 | 현재 청크의 크기. 헤더의 크기도 포함한 값. 64비트 환경에서, 사용 중인 청크 헤더의 크기는 16바이트이므로 사용자가 요청한 크기를 정렬하고, 그 값에 16바이트를 더한 값이 된다. |
| flags | 3비트 | 64비트 환경에서 청크는 16바이트 단위로 할당되므로, size의 하위 4비트는 의미를 갖지 않는다. 그래서 ptmalloc은 size의 하위 3비트를 청크 관리에 필요한 플래그 값으로 사용한다. 각 플래그는 순서대로 allocated arena(A), mmap’d(M), prev-in-use(P)를 나타낸다. prev-in-use 플래그는 직전 청크가 사용 중인지를 나타내므로, ptmalloc은 이 플래그를 참조하여 병합이 필요한지 판단할 수 있다. 나머지 플래그에 대해서는 여기서 설명하지 않는다. |
| fd | 8바이트 | 연결 리스트에서 다음 청크를 가리킴. 해제된 청크에만 있다. |
| bk | 8바이트 | 연결 리스트에서 이전 청크를 가리킴. 해제된 청크에만 있다. |
Chunk의 구조
bin
-사용이 끝난 청크들이 저장되는 객체. 메모리의 낭비를 막고, 해제된 청크를 빠르게 재사용할 수 있게 한다.
-ptmalloc에는 총 128개의 bin이 정의되어 있다. 이 중 62개는 smallbin, 63개는 largebin, 1개는 unsortedbin으로 사용되고, 나머지 2개는 사용되지 않는다.
small bin
-smallbin에는 32 바이트 이상 1024 바이트 미만의 크기를 갖는 청크들이 보관된다.
-하나의 smallbin에는 같은 크기의 청크들만 보관되며, index가 증가하면 저장되는 청크들의 크기는 16바이트씩 커진다. 즉, smallbin[0]는 32바이트 크기의 청크를, smallbin[61]은 1008 바이트 크기의 청크를 보관한다.
-smallbin은 원형 이중 연결 리스트(circular doubly-linked list)이며, 먼저 해제된 청크가 먼저 재할당(FIFO, First-In-First-Out) 된다.
-이중 연결 리스트의 특성상, smallbin에 청크를 추가하거나 꺼낼 때 연결 고리를 끊는 과정이 필요하다. ptmalloc은 이 과정을 unlink라고 부른다.
-smallbin의 청크들은 ptmalloc의 병합 대상이다. 메모리상에서 인접한 두 청크가 해제되어 있고, 이들이 smallbin에 들어있으면 이 둘은 병합된다. ptmalloc은 이 과정을 consolidation이라고 부른다.
small bin의 할당, 해제, 병합 과정
fastbin
-일반적으로 크기가 작은 청크들이 큰 청크들보다 빈번하게 할당되고 해제된다. 그래서 작은 청크들의 할당과 해제를 효율적으로 하는 게 전체적인 효율성 측면에서 중요하다. 이런 이유로 ptmalloc은 어떤 크기를 정해두고, 이보다 작은 청크들은 smallbin이 아니라 fastbin에 저장한다. 그리고 fastbin을 관리할 때는 메모리 단편화보다 속도를 조금 더 우선순위로 둔다.
-fastbin에는 32 바이트 이상 176 바이트 이하 크기의 청크들이 보관되며, 이에 따라 16바이트 단위로 총 10개의 fastbin이 있다.
-리눅스는 이 중에서 작은 크기부터 7개의 fastbin만을 사용한다. 즉, 리눅스에서는 32바이트 이상, 128바이트 이하의 청크들을 fastbin에 저장한다.
-fastbin은 단일 연결 리스트이며 LIFO 방식으로 동작한다. 단일 연결리스트이므로 청크를 꺼낼 때 꺼낸 청크의 앞과 뒤를 연결하는 unlink과정을 수행하지 않아도 된다.
-fastbin에 저장되는 청크들은 서로 병합되지 않는다.
fast bin의 동작 과정
large bin
-largebin은 1024 바이트 이상의 크기를 갖는 청크들이 보관된다.
-총 63개의 largebin이 있는데, smallbin, fastbin과 달리 한 largebin에서 일정 범위 안의 크기를 갖는 청크들을 모두 보관한다. 이 범위는 largebin의 인덱스가 증가하면 로그적으로 증가한다. 예를 들어, largebin[0]는 1024 바이트 이상, 1088 바이트 미만의 청크를 보관하며, largebin[32]는 3072 바이트 이상, 3584 바이트 미만의 청크를 보관한다.
-largebin은 범위에 해당하는 모든 청크를 보관하기 때문에, 재할당 요청이 발생했을 때 ptmalloc은 그 안에서 크기가 가장 비슷한 청크(best-fit)를 꺼내 재할당한다.
-largebin은 이중 연결 리스트이므로 재할당 과정에서 unlink도 동반된다.
-연속된 largebin 청크들은 병합의 대상이 된다.
unsorted bin
-분류되지 않은 청크들을 보관하는 bin
-unsortedbin은 하나만 존재하며, fastbin에 들어가지 않는 모든 청크들은 해제되었을 때 크기를 구분하지 않고 unsortedbin에 보관된다.
-unsortedbin은 원형 이중 연결 리스트이며 내부적으로 정렬되지 않는다.
-smallbin 크기에 해당하는 청크를 할당 요청하면, ptmalloc은 fastbin 또는 smallbin을 탐색한 뒤 unsortedbin을 탐색한다. largebin의 크기에 해당하는 청크는 unsortedbin을 먼저 탐색한다. unsortedbin에서 적절한 청크가 발견되면 해당 청크를 꺼내어 사용한다. 이 과정에서, 탐색된 청크들은 크기에 따라 적절한 bin으로 분류된다.
arena
-fastbin, smallbin, largebin 등의 정보를 모두 담고 있는 객체
-멀티 쓰레드 환경에서 ptmalloc은 *레이스 컨디션을 막기 위해 arena에 접근할 때 arena에 *락을 적용한다.
-ptmalloc에서는 최대 64개의 arena를 생성할 수 있다. arena에 락이 걸려서 대기해야 하는 경우, 새로운 arena를 생성해서 이를 피할 수 있다. 그런데, 생성할 수 있는 갯수가 64개로 제한되어 있으므로 과도한 멀티 쓰레드 환경에서는 병목 현상이 발생한다. 그래서 GLibc 2.26에서는 tcache를 추가적으로 도입했다.
*추가설명(레이스 컨디션, 락)
💡레이스 컨디션(Race Condition)
| 레이스 컨디션은 어떤 공유 자원을 여러 쓰레드나 프로세스에서 접근할 때 발생하는 오동작을 의미합니다. 예를 들어, 한 쓰레드가 어떤 사용자의 계정 정보를 참조하고 있는데, 다른 쓰레드가 그 계정 정보를 삭제하면, 참조하고 있던 쓰레드에서는 삭제된 계정 정보를 참조하게 됩니다. 이는 경우에 따라 심각한 보안 문제로 이어질 수 있습니다. 이런 문제를 막기 위해 멀티 쓰레딩을 지원하는 프로그래밍 언어들은 락(Lock) 기능을 제공합니다. 락은 문자 그대로 자물쇠의 역할을 합니다. 한 쓰레드에서 어떤 공유 자원에 락을 걸면, 그 공유 자원을 이용하려는 다른 쓰레드는 락이 해제될 때까지 기다려야 합니다. 공유 자원을 사용하는 동안 락을 걸어 놓음으로써 다른 쓰레드에 의한 조작을 차단할 수 있고, 레이스 컨디션을 방지할 수 있습니다. 그런데 락은 쓰레드를 무제한으로 대기시키기 때문에, 구현을 잘못하거나 쓰레드의 수가 과다하게 많아지면 병목 현상을 일으킬 수 있습니다. 락으로 발생하는 대표적인 문제 중 하나가 데드락(Deadlock)입니다. 여러 쓰레드가 서로 물리고 물려서 어떤 쓰레드도 락을 해제하지 못하는 상황을 의미합니다. 레이스 컨디션을 이용한 공격 기법은 심화 로드맵에서 살펴보도록 하겠습니다. |
tcache
-thread local cache의 약자. 이름에서 알 수 있듯, 각 쓰레드에 독립적으로 할당되는 캐시 저장소
-각 쓰레드는 64개의 tcache를 가지고 있다.
-tcache는 fastbin과 마찬가지로 LIFO 방식으로 사용되는 단일 연결리스트이며, tcache에는 32 바이트 이상, 1040 바이트 이하의 크기를 갖는 청크들이 보관된다. 하나의 tcache는 같은 크기의 청크들만 보관한다.
-리눅스는 각 tcache에 보관할 수 있는 청크의 갯수를 7개로 제한하고 있는데, 이는 쓰레드마다 정의되는 tcache의 특성상, 무제한으로 청크를 연결할 수 있으면 메모리가 낭비될 수 있기 때문이다.
-tcache에 들어간 청크들은 병합되지 않는다.
-이 범위에 속하는 청크들은 할당 및 해제될 때 tcache를 가장 먼저 조회하며, 청크가 보관될 tcache가 가득찼을 경우에는 적절한 bin으로 분류된다.
-tcache는 각 쓰레드가 고유하게 갖는 캐시이기 때문에, ptmalloc은 레이스 컨디션을 고려하지 않고 이 캐시에 접근할 수 있다.
-arena의 bin에 접근하기 전에 tcache를 먼저 사용하므로 arena에서 발생할 수 있는 병목 현상을 완화하는 효과가 있다.
-tcache는 보안 검사가 많이 생략되어 있어서 공격자들에게 힙 익스플로잇의 좋은 도구로 활용되고 있다.
tcache의 동작 과정
키워드 정리
|
'DreamHack: System Hacking > F Stage 11' 카테고리의 다른 글
| uaf_overwrite (0) | 2023.08.01 |
|---|---|
| Use After Free 개념 설명 (0) | 2023.08.01 |
