[C언어] Memory Allocator(ptmalloc2, 동적할당 동작 과정)
malloc은 한정된 메모리 자원을 각 프로세스에 효율적으로 사용하기 위해 필수적인 요소입니다.
거의 모든 프로세스는 실행 중에 메모리를 동적으로 할당하고, 할당한 메모리의 쓰임이 다하면 이를 해제하는데, 운영체제의 Memory Allocator는 이 동작이 빠르고 효율적으로 이루어지도록 복잡하고 특수한 알고리즘으로 이루어집니다
Memory Allocatyor는 알고리즘에 따라 종류가 다른데, 리눅스는 ptmalloc2, 구글은 tcmalloc, 파이어폭스는 jemalloc을 사용합니다.
이 중에서 ptmalloc2에 대해 깊게 알아보겠습니다.
먼저 드림핵 유닛을 따라 수강하느라 Ubuntu 18.04 64-bit환경 (Glic 2.27버전)을 준비하기 위해 도커파일 세팅을 먼저 했습니다.
먼저 ptmalloc의 구현 목표는 메모리의 효율적 관리입니다.
효율적 관리를 위해서는 1. 메모리 낭비가 없어야 하고, 2.빠른 재사용이 가능하며 3.메모리 파편화가 없어야합니다.
1. 메모리 낭비 방지
ptmalloc은 메모리 할당 요청 발생시, 먼저 해제된 메모리 공간 중 재사용할 수 있는 공간이 있는지 먼저 탐색합니다.
해제된 공간 중 요청된 크기와 같은 크기의 메모리가 있다면 그 영역을 재사용하고, 큰 메모리 공간이 있으면 영역을 나누기도 합니다.
2. 빠른 재사용
메모리 해제 후 빠른 재사용을 위해 해제된 메모리 공간의 주소를 저장해둡니다. ptmalloc은 tcache 또는 bin이라는 연결 리스트에 해제된 공간의 정보를 저장합니다.
tcache와 bin은 여러 개가 정의되어 있고, 각각 서로 다른 크기의 메모리 공간들을 저장해, 특정 크기의 할당 요청이 발생시, 그 크기에 관련된 저장소만 탐색하므로 공간을 효율적으로 재사용합니다.
(bin과 tcache는 자료구조나 저장 범위에서 차이가 있는 데 조금 이따가 다루도록 하겠습니다.)
3.메모리 파편화 방지
메모리 파편화는 외부 단편화와 내부 단편화로 나누어집니다.
외부 단편화는 빈 공간은 많지만 큰 블록이 없어서 새 요청을 만족시키지 못하는 경우고, 내부 단편화는 할당 단위 정렬(16바이트 단위로 할당)때문에 실제 요청보다 크게 할당되어 낭비되는 경우입니다.
ptmalloc2같은 경우에는 외부 단편화를 줄이는걸 목표로 합니다.
ptmalloc은 단편화 방지를 위해 청크 단위 관리,bin분류,병합,분할,arena구조 등 여러가지 방법을 사용합니다.
그중 대표적인 것만 살펴보자면 할당 단위 정렬입니다.
64비트기준으로 ptmalloc은 메모리 공간을 16바이트 기준으로 할당해줍니다. 4바이트를 요청해도 12바이트를 요청해도 똑같이 16바이트를 요청해주지만 사용자가 17바이트를 요청할경우 32바이트를 할당하는 방식입니다.
이런 할당방식은 내부 단편화가 발생하지만, 외부 단편화를 감소시켜줍니다.
(공간을 해제하고 재사용할 때, 정확히 같은 크기의 할당 요청이 발생할 확률 보다, 비슷한 크기의 요청이 발생할 확률이 큼)
또한 외부 단편화 감소 뿐 아니라 반환포인터를 배수단위로 맞춤으로써, 성능과 호환성 측면에서도 좋습니다.
ptmalloc의 객체
ptmalloc2는 Chunk, bin, tcache, arena를 주요 객체로 사용합니다. 각각에 대해 살펴보겠습니다.
청크
청크는 ptmalloc이 할당한 메모리 공간을 의미합니다. 헤더와 데이터로 구성됩니다. 헤더는 청크에 필요한 정보를 담고, 데이터 영역은 사용자가 입력한 데이터가 저장됩니다.
헤더는 사용중인 청크(In-use, 사진 왼쪽) 해제된 청크(freed, 오른쪽)의 구조가 다릅니다.
사용중인 청크는 fd와 bk 없이 그 영역에 데이터를 저장합니다.
청크 헤더의 요소는 다음과 같습니다.
| 이름 | 크기 | 용도 |
| prev_size | 8byte | 인접한 직전 청크의 크기, 청크를 병합할 때 직전 청크를 찾는데 사용 |
| size | 8byte | 현재 청크의 크기(헤더도 포함한 값) |
| flag | 3byte | chunksize는 16바이트 단위로 할당되므로 size의 남는 4바이트에 청크 관리에 필요한 플래그 값으로 사용합니다(사진상의 N,M,P) N은 allocated area M은 mmap P는 prev-in-use입니다. |
| fd,bk | 8byte | 해제된 청크의 연결리스트에서 각각 다음청크, 이전 청크를 가르킴 |
살짝 파일의 PE헤더와 비슷한 느낌으로 데이터의 입출력 전에 정보를 저장해두는 느낌인 듯 싶습니다.
bin
bin은 사용이 끝난 청크들이 저장되는 객체입니다. 해제된 청크를 빠르게 재사용하기 위해 크기에 맞게 보관하는 객체입니다.
ptmalloc에는 총 128개의 bin이 저장되어 있으며, 62개는 smallbin, 63개는 largebin, 1개는 unsortedbin이며 2개는 사용하지 않습니다.
1. smallbin
smallbin은 32바이트 ~ 1024바이트 미만의 크기를 가지는 청크들이 보관됩니다. 하나의 smallbin에는 같은 크기의 청크들만 보관되고, index마다 16바이트씩 증가하는 크기를 가집니다. 즉 smallbin[0]은 32바이트 크기의 청크를 smallbin[61]은 1008바이트 크기의 청크를 가집니다.
smaillbin은 이중 연결 리스트이고 FIFO 방식을으로 청크를 할당합니다.
아까 봤든 해제된 청크에는 fd,bk에선 다음,이전 청크를 가르 키는 포인터가 있고, bin의 헤더도 같은 형태로 되어있어서 원형을 이룹니다.
이러한 이중 연결 리스트는 중간의 노드를 빼거나 낄 때 양 옆 포인터만 바꾸면 되므로 빠르고, 임의 청크 제거가 용이하다는 장점이 있습니다.
2.fastbin
일반적으로 크기가 작은 청크들이 큰 청크보다 빈번하게 할당하고 해제되기 때문에 작은 청크들의 할당과 해제를 효율적으로 하는게 중요합니다. 그래서 ptmalloc은 32바이트 이상 128이하의 청크들을 fastbin에 저장합니다.
fastbin은 단일 연결 리스트이고, 청크를 꺼낼 때 가장 빠르지만 파편화가 심한 LIFO의 방법을 사용합니다.
따라서 나중에 해제된 청크가 먼저 재할당 되고, 서로 병합되지 않으므로, 병합에 사용되는 연산을 아낄 수 있습니다.
3.Largebin
largebin에는 1024바이트 이상의 크기를 갖는 청크들이 보관됩니다. 총 63개의 largebin이 있는데, 일정 범위 안의 크기를 갖는 청크들을 모두 보관합니다.
lagebin의 인덱스에 따라 로그적으로 보관하는데, largebin[0]은 1024바이트~1088바이트를 largebin[32]는 3072바이트~3584바이트 사이의 청크들을 보관합니다.
largebin은 범위에 해당하는 모든 청크를 보관하기 때문에 재할당 요청 발생시 크기가 가장 비슷한 청크를 꺼내 재할당하고, 이 과정을 빠르게 하려고 청크를 미리 정렬해둡니다.
largebin은 이중 연결 리스트이므로 재할당과정에서 unlink도 동반되고, 연속된 청크들은 병합의 대상이 됩니다.
4.unsortedbin
unsortedbin은 방금 free()된 청크들이 잠깐 모이는 임시 대기실입니다. 각 아레나마다 하나씩 보관되고, 원형 이중 연결 리스트의 형태로 보관됩니다.
unsortedbin 방식이 조금 신기한데, 시스템에서 smallbin에 해당하는 크기의 청크를 요청하면, fastbin 또는 smallbin을 탐색 후 unsortedbin을 탐색해서 맞는게 있으면 꺼내고, 안맞으면 크기에 맞게 분류하는 방식입니다.
largebin의 크기에 해당하는 청크는 largebin을 탐색하기 전 unsortedbin을 먼저 탐색하고 largebin을 탐색합니다.
이러한 방식이, 어떤 청크를 해제한 다음에 비슷한 크기의 청크를 바로 할당하는 경우가 많아 이런 경우에 청크분류에 낭비되는 비용을 없애기 위해 사용합니다.
또 largebin을 탐색하는데 기회비용이 많이드는데 이 과정도 생략할 수 있습니다.
Arena
아레나는 힙 관리 단위의 상위 객체이고, bin안의 정보를 모두 담고 있습니다.
ptmalloc은 최대 64개의 arena를 형성할 수 있게 하고 있어 그 이상을 만드려고 할때는 하나가 해제될 때 까지 대기해야합니다.
이러한 제한을 락이라고 하는데 락 기능은 레이스 컨디션을 방지할 수 있지만, 쓰레드를 무한으로 대기시키기 때문에, 데드락같은 치명적인 문제를 발생시키기도 합니다.
tcache
tcache는 thread local cache의 약자로 glibc 2.26버전에 새로 도입된 쓰레드에 독립적으로 할당되는 캐시 저장소입니다.
각 쓰레드마다 64개의 tcache를 가지고 있으며 LIFO방식으로 사용되는 단일 연결 리스트입니다.
하나의 tcache는 같은 크기의 청크들만 보관하고, 각 tcache마다 청크를 7개씩만 보관합니다.
tcache에는 32바이트~1040바이트 사이의 크기의 청크들이 보관되고, 이 범위들의 청크들은 할당 및 해제될 때 tcache를 가장 먼저 조회합니다. tcache가 가득 찼을 경우에만 적절한 bin으로 분류합니다.
tcache는 bin접근 전 사용하므로 arena에서 발생하는 병목 현상을 완화하고 레이스 컨디션을 방지하지만, 보안 검사가 많이 생략되어있어 힙 익스플로잇의 대상으로 활용됩니다.
오늘은 ptmalloc2의 구조와 할당과정에 대해 간단하게 살펴봤습니다.
내용에 사진이 글보다 많은건 오랜만인 것 같네요 .. ㅜㅠ
동적 할당이 복잡하다고는 들었어도 이렇게 어려운 과정을 겪을줄은 몰랐습니다 ..
드림핵 유닛안에 있는 내용만 공부한 건데도 넘 어렵네요.
다음 포스팅 때 Use After Free유닛을 공부하면서 더 몸으로 체감을 해야될 것 같습니다.
읽어주셔서 감사합니다`