ptmalloc2
ptmalloc2
ptmalloc2(pthread malloc 2)는 Memory Allocator로 리눅스에서 사용하고 있으며, GLibc에 구현되어 있습니다.
ptmallc의 구현 목표는 메모리의 효율적인 관리입니다. 자세히 말하면 메모리 낭비 방지, 빠른 메모리 재사용, 메모리 단편화 방지 등을 위한 것입니다.
메모리 낭비 방지
메모리의 동적 할당과 해제는 매우 빈번하게 일어납니다. 그러나 컴퓨터의 전체 메모리는 한정적이므로 새로운 메모리 공간을 무한히 할당할 수는 없습니다. 그래서 ptmalloc는 메모리 할당 요청이 발생하면, 먼저 해제된 메모리 공간 중에서 재사용할 수 있는 공간이 있는지 탐색하고 요청한 크기와 같은 크기의 메모리 공간이 있다면 이를 그대로 재사용하게 합니다. 또한, 작은 크기의 할당 요청이 발생했을 때, 해제된 메모리 공간 중 매우 큰 메모리 공간이 있으면 그 공간을 나누어 주기도 합니다.
빠른 메모리 재사용
운영자가 프로세스에게 제공해주는 가상 메모리 공간은 매우 넓습니다. 따라서 특정 메모리 공간을 해제한 이후에 이를 빠르게 재사용하려면 해제된 메모리 공간의 주소를 기억하고 있어야 합니다. 이를 위해 ptmalloc은 메모리 공간을 해제할 때 tcache 또는 bin이라는 연결 리스트에 해제된 공간의 정보를 저장해둡니다.
메모리 단편화 방지
메모리 단편화는 컴퓨터 과학의 메모리 관리 이론에서 다루는 중요한 문제 중 하나입니다. 내부 단편화와 외부 단편화가 있는데, 내부 단편화는 할당된 메모리 공간의 크기에 비해 실제 데이터가 점유하는 공간이 적으 때 발생합니다. 외부 단편화는 할당된 메모리 공간들 사이에 공간이 많아서 발생하는 비효율을 의미합니다.
ptmalloc은 단편화를 줄이기 위해 정렬과 병합, 그리고 분할을 사용합니다. 64비트 환경에서 ptmalloc은 메모리 공간을 16바이트 단위로 할당해줍니다. 사용자가 어떤 크기의 메모리 공간을 요청하면, 그보다 조금 크거나 같은 16바이트 단위의 메모리 공간을 제공합니다. 예를 들어, 4바이트를 요청하면 16바이트를, 17바이트를 요청하면 32바이트를 할당해주는 방식입니다. 이렇게 공간을 정렬하면 16바이트 이내의 내부 단편화가 발생할 수 있지만, 외부 단편화를 감소시키는 효과가 있습니다.
청크
청크는 덩어리라는 뜻으로, 여기서는 ptmalloc이 할당한 메모리 공간을 의미합니다. 청크는 헤더와 데이터로 구성됩니다. 헤더는 청크 관리에 필요한 정보를담고 있고, 데이터 영역에는 사용자가 입력한 데이터가 저장됩니다.
헤더는 청크의 상태를 나타내므로 사용중인 청크와 해제된 청크의 헤더 구조는 다소 다릅니다. 사용중인 쳥크는 fd와 bk가 사용되지 않고, 그 자리에 데이터를 저장합니다.
청크 헤더의 각 요소는 다음과 같습니다.
이름 크기 의미 prev_size 8바이트 인접한 직전 청크의 크기. 청크를 병합할 때 직전 청크를 찾는데 사용됩니다. size 8바이트 현제 청크의 크기입니다. flags 3비트 64비트 환경에서 청크는 16바이트 단위로 할당되므로 size의 하위 4비트는 의미를 갖지 않습니다. 그래서 ptmalloc은 size의 하위 3비트를 청크 관리에 필요한 플래그 값으로 사용합니다. fd 8바이트 연결 리스트에서 다음 청크를 가리킵니다. 해제된 청크에만 있습니다. bk 8바이트 연결 리스트에서 이전 청크를 가리킵니다. 해제된 청크에만 있습니다.
bin
bin은 문자 그대로, 사용이 끝난 청크들이 저장되는 객체입니다.
ptmalloc에는 총 128개의 bin이 정의되어 있습니다. 이 중 62개는 smallbin, 63개는 largebin, 1개는 unsortedbin으로 사용되고 나머지 2개는 사용되지 않습니다.
smallbin
smallbin에는 32 바이트 이상 1024 바이트 미만의 크기를 갖는 청크들이 보관됩니다. 하나의 smallbin에는 같은 크기의 청크들만 보관되며, index가 증가하면 저장되는 청크들의 크기는 16바이트씩 커집니다. 즉 smallbin[0]은 32바이트 크기의 청크를, smallbin[61]은 32+(16*61) = 1008 바이트 크기의 청크를 보관합니다.
smallbin은 원형 이중 연결 리스트이며, 먼저 해제된 청크가 먼저 재할당되는 FIFO(First-In-First-Out, 선입선츨) 방식입니다.
fastbin
일반적으로 크기가 작은 청크들이 큰 청크들보다 빈번하게 할당되고 해제됩니다. 그래서 작은 청크들의 할당과 해제를 효율적으로 하는 것이 전체적인 효율성 측면에서 중요합니다. 이런 이유로 ptmalloc은 어떤 크기를 정해두고, 이보다 작은 청크들은 smallbin이 아니라 fastbin에 저장합니다.
fastbin은 32 바이트 이상, 176 바이트 이하 크기의 청크들이 보관되며, 이에 따라 16 바이트 단위로 총 10개의 fastbin이 존재합니다. 리눅스는 이 중에서 작은 크기부터 7개의 fastbin만을 사용합니다. 즉 리눅스는 32 바이트부터 128 바이트 사이의 청크들을 fastbin에 저장합니다.
fastbin은 단일 연결 리스트입니다. 단일 연결리스트이므로 청크를 꺼낼 때 앞과 뒤를 연결해는 unlink 과정을 수행하지 않아도 됩니다. 그리고 fastbin은 LIFO(Last-In-First-Out, 후입선출) 방식을 사용합니다.
largebin
largebin은 1024 바이트 이상의 크기를 갖는 청크들이 보관됩니다. 총 63개의 largebin이 있으며, 한 largebin에서 일정 범위 안의 크기를 갖는 청크들을 모두 보관합니다. 이 범위는 largebin의 인덱스가 증가하면 로그적으로 증가합니다.
largebin은 범위에 해당하는 모든 청크를 보관하기 때문에, 재할당 요청이 발생했을 때 ptmalloc은 그 안에서 크기가 가장 비슷한 청크를 꺼내 재할당합니다.
unsortedbin
unsortedbin은 문자 그대로, 분류되지 않은 청크들을 보관하는 bin입니다. unsortedbin은 하나만 존재하며, fastbin에 들어가지 않는 모든 청크들은 해제되었을 때 크기를 구분하지 않고 unsortedbin에 보관됩니다. unsortedbin은 원형 이중 연결 리스트입니다.
smallbin 크기에 해당하는 청크를 할당 요청하면, ptmalloc은 fastbin 또는 smallbin을 탐색한 뒤 unsortedbin을 탐색합니다. largebin 크기에 해당하는 청크는 unsortedbin을 먼저 탐색합니다. unsortedbin에서 적절한 청크가 발견되면 해당 청크를 꺼내어 사용합니다. 이를 통해 불필요한 연산을 줄이고 성능을 최적화합니다.
arena
arena는 fastbin, smallbin, largebin 등의 정보를 모두 담고 있는 객체입니다. 멀티 쓰레드 환경에서 레이스 컨디션(어떤 공유 자원을 여러 쓰레드나 프로세스에서 접근할 때 발생하는 오동작)을 막기 위해 arena에 접근할 때 arena에 락을 적용합니다. 그런데 이 방식을 사용하면 레이스 컨디션은 피할 수 있지만 병목 현상을 일으킬 수 있습니다.
ptmalloc는 이를 해결하기 위해 최대 64개의 arena를 생성할 수 있게 하고 있습니다. 그러나 생성할 수 있는 갯수가 64개로 제한되어 있으므로 과도한 멀티 쓰레드 환경에서는 결국 병목 현상이 발생합니다. 그래서 glibc 2.26에서는 tcache를 추가적으로 도입했습니다.
tcache
tcache는 thread local cache의 약자입니다. 이름에서 알 수 있듯, 각 쓰레드에 독립적으로 할당되는 캐시 저장소를 지칭합니다.
각 쓰레드는 64개의 tcache를 가지고 있습니다. tcache는 LIFO 방식으로 사용되는 단일 연결 리스트이며, 하느의 tcache는 같은 크기의 청크들만 보관합니다. 리눅스는 각 tcache에 보관할 수 있는 갯수를 7개로 제한하고 있습니다.
tcache에는 32 바이트 이상, 1040 바이트 이하의 크기를 갖는 청크들이 보관됩니다. 이 범위에 속하는 청크들은 할당 및 해제될 때 tcache를 가장 먼저 조회합니다.
tcache는 보안 검사가 많이 생략되어 있어 공격자들에게 힙 익스플로잇의 좋은 도구로 활용되고 있습니다.
