ptmalloc - linux 메모리 할당 ( Memory Allocator )

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

Background:ptmalloc2

위 드림핵 강의를 참고 했는데 이 강의는 Ubuntu 18.04 64-bit(Glibc 2.27 버전)을 기준으로 한다.

ptmalloc 이란?

ptmalloc은 리눅스에 Memory Allocator이다. Memory Allocator는 운영체제 안에서 메모리를 효율적으로 관리하는 일은 한다. 모든 프로세서는 실행 하는 동안 메모리를 동적으로 할당하고, 해제하기를 빈번하게 한다. 그래서 운영체제  Memory Allocator는 이 과정을 효율적으로 하기 위해 특수한 알고리즘을 사용하여 빠르고,  낭비 없이 이루어 지도록 구현되었다. 

Memory Allocator는 여러 종류가 있는데 우리는 그 중에 리눅스에 있는 ptmalloc을 공부할 것이다.

ptmalloc2는 어떤 메모리가 해제되면, 해제된 메모리의 특징을 기억하고 있다가 비슷한 메모리의 할당 요청이 발생하면 이를 빠르게 반환해준다.

 

ptmalloc은 동적 메모리 관리를 위한 리눅스에 핵심 알고리즘이며, 이와 관련한 공격기법, 그것을 방어하기 위한 보호기법이 지속적으로 발달되었다. 그래서 ptmalloc은 버젼마다 적용할 수 있는 공격기법이 큰 차이가 생기기도 한다. 

 

※주의 이 블로그는 ptmalloc은 깊게 공부하지 않기 때문에

깊이 heap 영역을 공부하고 싶으신 분들은 다른 블로그를 봐주세요!!※

 

ptmalloc의 목표는 메모리의 효율적인 관리이다.

그 중 핵심

- 메모리 낭비 방지

- 빠른 메모리 재사용

- 메모리 단편화 방지

위와 같은 핵심 목표들이 있다.

메모리 관리 전략

아까 말한 목표들에 대응되는 ptmalloc의 메모리 관리 전략들을 살펴 볼 것이다.

메모리 낭비 방지

메모리의 동적 할당과 해제는 빈번하게 일어난 데에 반해 메모리는 한정적이다. 그래서 새로운 메모리 공간을 무한정으로 할당해줄 수 없다. 그래서 ptmalloc은 해제된 메모리 공간에서 먼저 재사용할 수 있는 공간이 있는지 탐색한다. 

해제된 메모리 공간 중 요청된 크기와 같은 크기에 메모리 가 있으면, 이를 그대로 사용하기도 한다. 또한 작은 크기의 할당 요청이 들어왔을 때 해제된 메모리 공간 중 매우 큰 메모리 공간이 있으면, 그를 나누어 할당해주기도 한다.

빠른 메모리 재사용

운영체제가 프로세스에게 제공하는 가상 메모리의 크기는 매우 넓다. 그래서 우리가 건물을 찾아갈 때 주소를 알고 찾아가면 빨리 찾아가는 것처럼 특정 메모리 공간을 빠르게 재사용하려면 그 공간의 주소를 기억하고 있어야 한다. 이를 위해 ptmalloc은 메모리 공간을 해제할 때, tcache 또는 bin이라는 연결 리스트에 해제된 공간의 정보를 기억해둔다.  

tcache나 bin은 여러 개가 정의되어 있으며, 각각 서로 다른 크기의 메모리를 저장하고 탐색할 때도 그 크기와 관련된 저장소만 탐색하여 효율적으로 사용할 수 있다. 

메모리 단편화 방지

먼저 메모리 단편화의 의미이다. 메모리 단편화는 컴퓨터 과학의 메모리 관리 이론에서 다루는 중요한 문제 중에 하나이다. 사용가능한 메모리가 충분히 존재하지만 할당(사용)이 불가능한 상태를 메모리 단편화가 발생했다고 한다.

메모리 단편화는 외부 단편화와 내부 단편화로 나뉜다.

내부 단편화는 메모리가 할당할 때 메모리를 할당할 때 프로세스가 필요한 양보다 더 큰 메모리가 할당되어 메모리 공간이 낭비되는 상황을 말한다.

외부 단편화는 메모리가 할당되고 해제되는 작업을 반복될 때 중간중간 작은 메모리가 존재하게 되는데, 이 때 중간중간 생기는 작은 메모리로 인해서 총 메모리 공간은 충분하지만 실제론 할당할 수 없는 상황을 말한다. 

위와 같은 단편화가 심해질 수록 메모리 효율이 떨어진다.

 

ptmalloc은 메모리 단편화를 줄이기 위해 정렬, 병합, 분할을 사용합니다. 64bit 환경에서는 ptmalloc은 메모리 공간을 16byte 단위로 할당해준다. 사용자가 어떤 크기의 메모리 공간을 요청하면, 그보다 조금 크거나 같은 16byte의 단위로 메모리 공간을 제공한다. 이렇게 공간을 정렬하면 16바이트 이내에 내부 단편화가 발생할 수 있지만, 역설적으로 외부 단편화를 감소하는 효과가 있다. -> 예시) 4byte를 요청하면 16byte, 17byte를 요청하면 32byte

 

공간을 정렬하지 않고, 프로세스가 요청하는 만큼 할당할 수 있다면 모든 데이터가 연속적으로 할당되어 외부 단편화를 줄일 수 있다. 그러나 공간을 해제하고 재사용할 때, 정확히 같은 크기의 할당 요청이 발생할 확률보다 비슷한 크기의 요청이 발생할 확률이 높다. 그래서 비슷한 크기의 요청에 대해서는 모두 같은 크기의 공간을 반환해야 해제된 청크들의 재사용률을 높이고, 외부 단편화도 줄일 수 있다.

ptmalloc은 특정 조건을 만족하면 해제된 공간들을 병합하기도 한다. 병합으로 생성된 큰 공간은 그 공간과 같은 크기의 요청에 의해, 또는 그보다 작은 요청에 의해 분할되어 재사용됩니다. 잘게 나뉜 영역을 병합하고, 필요할 때 구역을 다시 설정함으로써 해제된 공간의 재사용률을 높이고, 외부 단편화를 줄일 수 있습니다.

 

위와 같은 방법으로 메모리를 관리한다.

 

ptmalloc의 객체

주요 객체

- 청크(chunk)

- bin

- tcache

- arena

위와 같은 객체를 ptmalloc은 주요 객체로 사용한다.

 

Chunk(청크)

Chunk(청크)는 덩어리라는 뜻으로, ptmalloc에서 할당한 공간을 의미 한다. 청크는 크게 헤더와 데이터로 구분하는데, 헤더는 청크 관리에 필요한 정보가 들어 있으며, 데이터 영역에는 사용자가 입력한 데이터가 저장된다.

 

헤더

헤더는 청크의 상태를 나타내므로 사용 중인 청크와 해제된 청크의 구조가 다르다. 기본적으론 사용 중인 청크에는 fd와 bk를 사용하지 않고, 그 영역에 데이터를 저장한다.  

청크 헤더에는 다음과 같은 요소가 존재 하는데

이름	크기	의미
prev_size	8byte	직전 청크의 크기이다. 청크를 병합할 때 직전 청크를 찾는 데 사용된다.
size	8byte	현재 청크의 크기이다. 헤더의 값을 포함한다. 그러므로 사용자가 준 데이터 + 16byte가 된다.
flags	3bit	64bit 환경에서 청크는 16byte단위로 할당된다. 그러므로 size의 하위 4bit는 의미가 없으므로 그 중 3bit를 청크 관리에 필요한 플래그 값으로 사용한다. 각 플래그는 순서대로 allocated arena(A), mmap’d(M), prev-in-use(P)를 나타난다. P는 직전 청크가 사용 중인지를 나타내므로 ptmalloc은 이 플래그를 참조하여 병합이 필요한지 판단할 수 있다. 나머지는 이 강의에서 설명하지 않으므로 나중에...
fd	8byte	해제된 청크에서 연결리스트의 다음을 가르킨다
bk	8byte	해제된 청크에서 연결리스트의 이전을 가르킨다.

 

bin

bin은 사용이 끝난 청크들을 저장하는 객체이다. 메모리 낭비를 막고, 빠르게 재사용 할 수 있도록 도와준다. ptmalloc에는 총 126개의 bin이 정의되어 있다. 이 중에 62개는 smallbin, 63개는 largebin, 1개는 unsortedbin이다.

 

청크 관리

청크를 관리하는 방법에는 크게 LIFO(last-in-first-out, 후입선출), FIFO, address-ordered가 있다. LIFO는 속도가 빠르지만 파편화가 가장 심하고, address-ordered는 정렬을 해야 해서 속도는 느리지만 파편화가 가장 적고, FIFO는 그 중간이다.

TOP chunck란

가장 마지막에 있는 청크이다. 기본적으로 사용자가 요청한 malloc보다 많은 사이즈를 heap 영역에 할당하는데 이 때 사용자 요청외에 남는 부분이 바로 top chunk이다.

top chunk는 기본적으로 main, thread에서 더 많은 heap을 요구할 때 메모리 공간을 추가적으로 제공하기 위해 존재하는 것이다.

smallbin

smallbin에는 32byte 이 1024 byte 바이트 미만의 크기를 갖는 청크들이 보관한다. 하나의 smallbin에는 같은 크기의 청크들만 보관된다. 또한 index가 증가하면서 저장되는 청크들의 크기는 16byte씩 커진다. 즉, smallbin[0]는 32바이트 크기의 청크를, smallbin[61]은 1008 바이트 크기의 청크를 보관한다.

smallbin은 원형 이중 연결리스트 (circular doubly - linked list) 이며, 먼저 해제된 청크가 먼저 재할당 된다. 이 같은 방식은 FIFO (first-in-last-out, 선입선출) 구조이다. 이중 연결 리스트 특성상, smallbin에 청크를 추가하거나 꺼낼 때 연결 리스트 고리를 끊는 과정이 필요하다. ptmalloc은 이 과정을 unlink라고 부른다. 

smallbin의 청크들은 ptmalloc의 병합 대상이다. 메모리 상에서 두 청크가 인접해있고, 이들이 해제되어 있는 상태에서 smallbin에 들어가 있으면, 이 두 청크는 병합된다. ptmalloc은 이 과정을 consolidation 이라고 부른다. 

 

fastbin

일반적으로는 작은 청크들이 큰 청크들보다 빈번하게 해제된다. 그래서 작은 청크들은 할당과 해제를 효율적으로 하는게 중요하다. 이렇게 효율적으로 하기 위해 ptmalloc은 어떤 크기를 정해두고, 이보다 작은 청크들을 smallbin이 아니라 fastbin에 저장한다. 그리고 fastbin의 이름 처럼 메모리 단편화 보다 속도를 조금 더 우선순위로 둔다.

fastbin에는 32 byte 이상, 176 byte 이하 크기의 청크들이 보관 되며, 이에 따라 16byte 단위로 10개의 fastbin이 있다. 리눅스는 작은 크기부터 7개의 fastbin만 사용된다. 즉, 리눅스에서는 32byte 이상, 128byte 이하의 청크들을 fastbin에 저정한다. 

fastbin은 단일 연결리스트이다. 단일 연결리스트 이므로, 청크를 꺼낼 때 꺼낸 청크의 앞과 뒤를 연결하는 unlink과정을 수행하지 않아도 된다. 또한, fastbin은 속도는 빠르지만 다른 방법에 비해 파편화가 심한 LIFO의 방법을 사용한다. 이에 따라 나중에 해제된 청크가 먼저 재할당 된다. 마지막으로, fastbin에 저장되는 청크들은 서로 병합되지 않는다. 그래서 청크간의 병합에 사용되는 연산도 아낄 수 있다. 

largebin

largebin은 1024 byte 이상의 크기를 갖는 청크들은 보관된다. smallbin, fastbin과 달리 한 largebin에서 일정 범위 안에 크기를 갖는 청크들을 모두 보관한다. 이 범위는 largebin의 인덱스가 증가하면 로그적으로 증가합니다. 

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

이러한 방법을 사용하면 적은 수의 largebin으로 다양한 크기를 갖는 청크들을 관리할 수 있다. 

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

unsortedbin

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

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

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

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

arena

arena는 fastbin, smallbin, largebin 등의 정보를 모두 담고 있는 객체이다. 멀티 쓰레드 환경에서 ptmalloc은 레이스 컨디션을 막기 위해 arena에 막기 위해 arena에 락을 적용한다. 그런데 이 방식을 사용하면 레이스 컨디션은 막을 수 있지만 반대로 병목 현상이 일어날 수 있다. 즉 일부분에 의해 전체가 제한받는 상황이 생기는 것이다.

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

 

레이스 컨디션이란?

레이스 컨디션은 어떤 공유 자원을 여러 쓰레드나 프로세스에서 접근할 때 발생하는 오작동을 의미한다. 

예시) 한 쓰레드가 어떤 사용자의 정보를 참조하고 있는데, 다른 쓰레드가 그 계정 정보를 삭제하면, 참조하고 있던 쓰레드에서는 삭제된 계정의 정보를 참조하게 된다. 이는 경우에 따라 심한 보안 문제로 이어질 수 있다. 

이런 문제를 막기 위해 멀티 쓰레드를 지원하는 프로그래밍 언어들은 락(Lock) 기능을 제공한다. 락은 말 그대로 자물쇠 역할을 한다. 한 쓰레드에서 어떤 공유 자원에 락을 걸면, 그 공유된 자원을 이용하려는 다른 쓰레드는 락이 해제될 때 까지 기다려야 한다. 공유 자원에 락을 걸어 다른 쓰레드에 의한 조작을 차단할 수 있고, 레이스 컨디션을 방지할 수 있다.

그런데 락은 쓰레드를 무제한으로 대기시키기 때문에, 구현을 잘못하거나 쓰레드의 수가 과다하게 많아지는 병목현상이 일어날 수 있다. 락으로 발생하는 대표적인 문제 중 하나가 데드락(Deadlock)이다. 여러 쓰레드가 서로 물리고 물려서 어떤 쓰레드도 락을 해제하지 못하는 상황을 의미한다.

Tcache

tcache는 thread local cache의 약자이다. 이름부터 알 수 있듯, 각 쓰레드에 독립적으로 할당되는 캐시 저장소를 지칭한다. tcache는 Glibc 버전 2.26에 도입되었으며, 멀티 쓰레드 환경에서는 더욱 최적화된 메모리 관리 메커니즘을 제공한다.

각 쓰레드는 64개의 tcache를 가지고 있다. tcache는 LIFO 방식으로 사용되고 단일 연결 리스트이다. 하나의 tcache에는 같은 청크들만 보관된다. 리눅스는 각 tcache에 보관할 수 있는 7개로 제한하고 있다. 이는 쓰레드 마다 정의되는 tcache의 특성상, 무제한으로 청크를 연결할 수 있으면 메모리가 낭비될 수 있기 때문이다. (이유->) tcache에 들어간 청크들은 병합되지 않는다. (이유->)힙 할당 요청이 들어오면 빠른 재할당을 위해 즉시 해당 주소를 할당해 속도를 향상시켰기 때문이다. 

tcache에는 32byte이상, 1040byte이하의 크기를 갖는 청크들이 보관된다. 이 범위에 속하는 청크들은 할당 및 해제될 때 tcache를 가장 먼저 조회한다. 청크가 보관될 tcache가 가득 차면 적절한 bin에 분류된다. 

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

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