신비한 malloc 사전

진짜 서문

이 글의 첫 버전은 서상현이 2022년에 작성했습니다. malloc은 시스템 프로그래밍의 최전선에 서 있는 분야이며 빠르게 변화하고 있습니다. 그러므로 이 글은 주기적으로 갱신될 것입니다.

시간상의 제약으로 꼭 다뤄야 할 주제들을 다루지 못했습니다. 윈도의 malloc 구현, malloc의 보안성과 malloc과 운영체제의 인터페이스에 대한 부분이 그 예입니다. 적절한 위치에 그러한 문제가 있다는 사실을 명시했으며, 차차 보완해 나가도록 하겠습니다.

이 글의 정보는 2022년 기준으로 최신입니다. 정확성을 기하기 위해 최선을 다했으나 실수가 있을 수 있습니다. 독자 여러분의 이해를 바랍니다.

잘못된 내용이나 최신이 아니게 된 내용, 추가해야 할 내용이 있으신 분은 관련 사항을 sanxiyn@gmail.com 또는 @sanxiyn으로 알려주시기 바랍니다. 가능한 한 빠르게 반영하도록 하겠습니다.

이 글은 한국의 프로그래밍 언어 공부 모임인 LangDev의 팀 블로그 GitHub 저장소에서 관리되고 있으므로, 해당 저장소에 이슈나 PR을 올려주셔도 됩니다. 감사합니다.

가짜 서문

(이 서문은 해리 포터와 반지의 제왕 팬을 위한 패러디입니다. 무슨 소리인지 모르겠으면 넘어가셔도 됩니다.)

2001년 마법 정부는 머글들을 위한 신비한 동물 사전을 출간하는 것을 인준하였습니다. 국제 마법사 비밀 법령을 준수하기 위해, 알버스 덤블도어는 독자들에게 신비한 동물들은 실제로는 존재하지 않으며 허구라고 안심시키는 서문을 썼습니다.

하지만 미스터리부의 말할 수 없는 자들이 반대했기 때문에 malloc에 대한 정보는 포함될 수 없었습니다. 소문에 따르면 관련된 예언이 있었다고 합니다. 20년이 넘는 세월이 지난 지금, 미스터리부의 동의 하에, 삭제되었던 malloc에 대한 정보를 여러분과 공유할 수 있게 되어 기쁘게 생각합니다.

malloc은 말록이라고 읽으며 발록의 친척입니다. 발록의 발은 힘이 세다는 뜻인데 말록도 그렇습니다. 하지만 멜코르가 타락시켜 사악한 악마가 된 발록과 달리 말록은 인간의 친구가 될 수 있습니다. 발록이 나타나면 투명드래곤을 불러야 하지만 말록은 그럴 필요가 없습니다.

말록은 잘못 다루면 힘이 세서 무섭지만 알고보면 사랑스러운 존재들입니다. 아무쪼록 여러분이 이 글을 읽고 말록과 사이좋게 지내는데 도움이 된다면 더 바랄 것이 없겠습니다.

이 글에서 다루지 않는 것

이 글에서는 주로 malloc의 성능을 다룹니다. 성능은 malloc을 평가하는데 있어 중요한 요소이지만, 성능이 malloc의 전부는 아닙니다. 본론을 시작하기 전에, 언젠가 이 주제들도 다룰 수 있게 될 훗날을 기약하면서, 다른 어떤 요소들이 있는지 짚고 넘어가도록 하겠습니다. 가능한 경우 해당 요소에 특화된 malloc 구현을 같이 소개하겠습니다.

가장 먼저 떠오르는 것은 정확성입니다. malloc에는 버그가 없어야 합니다. 성능 향상을 위한 교묘한 기법들은 보통 코드의 복잡성을 증가시키므로, 버그가 발생할 가능성도 증가시킵니다. 아래에서 다룰 범용 malloc들은 단순함을 장점으로 내세우는 경우조차도 꽤 복잡하며, 모두 버그가 있었습니다. 이때문에 의료나 항공과 같이 안전성에 필수적이어서 정확성을 중시하는 응용에서는 malloc을 사용하지 않아 왔습니다. 최근 코드의 정확성을 증명하는 기법이 발전함에 따라 이 분야에는 변화가 예상됩니다. 한 예로 Andrew Appel은 ISMM 2020에서 정확성이 증명된 malloc 구현을 발표하였습니다: Verified Sequential Malloc/Free.

예측 가능성도 있습니다. 실시간 처리를 하는 RTOS를 비롯한 많은 응용에서, 평균적인 성능보다 최악의 경우의 성능이 더 중요할 수 있습니다. 아래에서 다룰 범용 malloc들은 모두 최악의 경우의 성능을 보장하지 않습니다. 이는 최악의 경우의 성능과 평균적인 성능이 서로 교환 관계에 있기 때문입니다. 이때문에 실시간 처리를 필요로 하는 응용에서는 malloc을 사용하지 않아 왔습니다. 최근 연구가 진행됨에 따라 이 분야에는 변화가 예상됩니다. 한 예로 Miguel Masmano는 2007년 박사 학위 논문에서 최악의 경우 실행 시간을 보장하는 malloc 구현을 기술하였습니다: Two Level Segregate Fit (ECRTS 2004 논문, 발표 자료).

범용 malloc들의 코드 크기는 꽤 큽니다. FreeBSD 시스템의 경우, malloc은 전체 C 라이브러리 코드 크기의 30% 이상을 차지했습니다. 이때문에 코드 크기가 중요한 임베디드 응용에서는 malloc을 사용하지 않아 왔습니다. 최근 주목받고 있는 WebAssembly에서도 같은 문제가 있습니다. Nick Fitzgerald는 2018년 WebAssembly를 위해 코드 크기를 최적화한 malloc 구현을 공개하였습니다: wee_alloc.

실 사용이 아닌 개발 과정에서 개발자들을 돕기 위한 malloc들도 있습니다. malloc은 개발자들을 돕기 위한 여러 도구를 마련하기에 좋은 위치에 자리하고 있습니다. 디버깅 malloc은 성능을 희생하면서 개발자가 malloc을 잘못 사용하는 경우 빠르게 버그를 수정할 수 있도록 도울 수 있습니다. 프로파일링 malloc은 개발자가 응용의 메모리가 어디에 쓰이는지 파악하고 최적화하는데 도움을 줄 수 있습니다. 한 예로 Bruce Perens는 1987년 버퍼 넘침과 해제 후 사용을 감지할 수 있는 디버깅 malloc 구현을 공개하였습니다: Electric Fence.

끝으로 보안성이 있습니다. malloc에 버그가 없는 경우에도, malloc을 사용하는 응용에는 버그가 있습니다. 응용이 malloc을 잘못 사용하는 경우, 응용을 바로 멈추게 함으로써 추가적인 피해를 막을 수 있습니다. 개발 과정에서만 사용되므로 성능을 크게 희생할 수 있는 디버깅 malloc과는 달리, 보안 malloc은 실제로 사용되므로 성능을 크게 희생할 수 없습니다. 보안 malloc은 메타데이터를 별도로 저장하여 버퍼 넘침 등의 공격이 있을 때에도 메타데이터가 덮어써지지 않도록 보호할 수 있습니다. 보안 malloc은 또한 난수를 활용하고 예측 불가능하게 동작함으로써 취약점의 공격을 어렵게 할 수 있습니다. 한 예로 Daniel Micay는 2018년부터 보안성이 크게 향상된 malloc 구현을 개발하고 있습니다: hardened_malloc.

이 글에서는 자세히 다루지 못했지만 malloc의 보안성은 매우 중요한 주제입니다. 이 점을 보완하기 위해, malloc의 보안성에 대해 한국어로 작성된 글로 박재유님의 메모리 취약점: 과거, 현재, 미래 (4) Heap Attacks을 추천드립니다.

성능 지표

malloc의 성능을 이야기하려면 성능 지표가 필요합니다. 가장 쉽게 생각할 수 있는 지표로 malloc이 사용하는 시간이 있습니다. malloc이 호출되었을 때부터 결과를 반환할 때까지의 시간을 재고 모든 malloc 호출에 대해 합하는 것입니다.

이 지표에는 여러가지 심각한 문제가 있어서 malloc의 성능 평가에 쓸 수 없습니다. 일단 비교적 사소한 문제를 짚고 넘어가겠습니다. malloc의 성능과 free의 성능은 서로 교환 관계에 있습니다. malloc이 사용하는 시간만 고려한다면 free가 느린 구현이 좋은 평가를 받을 수도 있습니다.

malloc이 사용하는 시간과 free가 사용하는 시간, 일반적으로 할당자가 사용하는 시간을 모두 합하면 어떨까요? 하지만 전산학에서 종종 그렇듯이 시간과 공간은 서로 교환 관계에 있습니다. free에서 아무 일도 하지 않는다면 공간은 낭비되지만 시간적으로는 빠를 것입니다.

할당자가 사용하는 시간과 할당자가 사용하는 공간을 함께 고려하면 될까요? 여기서 우리는 공간을 어떻게 평가할 것인가 고민할 필요가 있습니다. 실시간 처리에 대해 언급하면서 범용 malloc은 평균적인 성능을 최적화한다고 말씀드렸습니다. 시간에 대해서는 그렇지만, 공간에 대해서는 최악의 경우의 성능, 구체적으로는 최대 메모리 사용량을 보통 고려합니다. 최대 메모리 사용량이 높으면 시스템이 메모리 부족을 겪을 수 있기 때문입니다.

할당자가 사용하는 평균 시간과 최대 메모리 사용량을 고려하면 될까요? 이것은 아주 나쁜 성능 지표는 아닙니다. 실제로 이 성능 지표를 사용하는 논문들도 있습니다. 그러나 연구가 진행됨에 따라 문제점들이 발견되었습니다. 가장 중요한 점들을 살펴보도록 합시다.

…

2006년 Intel Core 2 Duo가 출시되면서 멀티코어 확장성에 대한 관심이 높아졌습니다…

(여기서부터 TODO)

average time in allocator and peak memory (여기까지 작성함)

time in allocator vs application time

cache awareness and improving application locality

(TODO: NUMA awareness)

reducing fragmentation and blowup

reducing lock contention

avoiding false sharing

handling bleeding (cross-thread free)

벤치마크

가장 좋은 벤치마크는 실제로 사용할 응용 자체입니다. 다행히 malloc 구현은 보통 다시 빌드하지 않고도 쉽게 적용할 수 있습니다. 그러나 그런 방법으로 시스템 malloc을 선택할 수는 없으므로 일반적인 벤치마크도 필요합니다.

다음은 malloc의 성능을 평가하기 위해 자주 사용되는 벤치마크들입니다. 좋은 malloc 벤치마크는 malloc 구현의 특성에 따라 성능이 크게 변하는 벤치마크입니다.

barnes: Barnes-Hut 알고리즘으로 N체 문제를 풉니다. 스레드를 써서 병렬로 계산합니다. 동적 메모리 할당을 하기는 하는데 많이 하지는 않는 응용을 대표합니다.

cfrac: 연분수 계산을 위해 수명이 짧은 다수의 작은 할당을 합니다. 함수형 프로그래밍 언어들의 전형적인 동작을 대표합니다.

espresso: 전자 회로를 최적화합니다. 캐시에 크게 의존하므로 할당자가 지역성 최적화를 하는지 검사합니다.

gs: Ghostscript는 널리 쓰이는 PostScript 인터프리터입니다. 내부적으로 자체 할당자를 가지고 있는 응용을 대표합니다.

다음 벤치마크들은 SPEC CPU 2017의 일부로 malloc을 위한 벤치마크가 아니라 일반적인 성능을 평가하기 위한 벤치마크입니다. SPEC에는 다른 벤치마크들도 있지만 비디오 압축(x264)이나 데이터 압축(xz)은 동적 메모리 할당을 많이 사용하지 않습니다.

gcc: GCC는 널리 쓰이는 C 컴파일러입니다. 내부적으로 GC를 사용하는 응용을 대표합니다.

xalancbmk: Xalan-C++은 XSLT 처리기입니다. 동적 메모리 할당을 많이 하는 평범한 응용을 대표합니다.

다음 벤치마크들은 malloc에 특정 부하를 주어 malloc 구현이 해당 사용 유형을 잘 처리하는지 검사합니다.

(여기서부터 TODO)

alloc-test: http://ithare.com/testing-memory-allocators-ptmalloc2-tcmalloc-hoard-jemalloc-while-trying-to-simulate-real-world-loads/

cache-scratch: passive false sharing

cache-thrash: active false sharing

larson: bleeding

shbench: locality and anti-locality

xmalloc-test: extreme bleeding (producer-consumer)

위에 언급된 벤치마크들은 모두 mimalloc-bench 저장소에서 얻을 수 있습니다.

도움 요청

이 글은 2000년 이후의 역사적이나 실용적으로 중요한 malloc 구현들을 다루고 있으나, malloc의 역사는 그보다도 20년이 넘게 더 오래되었습니다. 글쓴이는 신비한 malloc 사전의 후속으로 malloc디치의 역사를 준비하고 있습니다. 역사적인 조사를 위해 여러분의 도움이 필요합니다.

역사적인 유닉스의 소스 코드는 유닉스 유산 협회에서 운영하는 유닉스 트리 기록 보관소에서 살펴볼 수 있습니다. 애플이 개발하는 맥과 iOS의 소스 코드는 애플 오픈 소스에서 살펴볼 수 있습니다. 그러나 살펴보려면 먼저 찾아야 하기 때문에, 관련된 코드를 찾는데 도움을 요청드립니다.

윈도의 malloc 구현은 역사적으로나 실용적으로나 중요합니다. 그러나 글쓴이의 지식이 부족하고 소스 코드가 공개되어 있지 않기 때문에 이 글에서 다루지 못했습니다. 윈도의 내부 구현을 파헤친 자료가 충분히 있으므로 정보를 얻을 수 있을 것으로 기대하고 있습니다. 윈도에 대해 잘 아시는 분의 도움을 요청드립니다.

(다음 자료를 추천받았습니다: Mark Yason의 Windows 10 Segment Heap Internals (Black Hat USA 2016 논문, 발표 자료))

(TODO: malloc 구현과 관련된 소프트웨어 특허에 대해서)

(TODO: malloc과 운영체제의 인터페이스에 대해서 please help me… sbrk vs mmap, VirtualAlloc/VirtualAlloc2, lazy commit, madvise MADV_FREE hint)

(TODO: malloc API와 API 확장에 대해 블라블라: malloc_trim, malloc_usable_size…)

(TODO: malloc() and free() are a bad API)

malloc 구현의 역사는 C 언어와 C 표준의 역사와 밀접한 관계를 맺고 있습니다. 다음 1차 사료들에 대한 조사가 필요합니다: 이른바 K&R이라 불리는 Brian Kernighan과 Dennis Ritchie의 1978년에 출판된 The C Programming Language 1판, 1988년에 출판된 2판, 1993년 두 번째로 열린 프로그래밍 언어의 역사 컨퍼런스에서 Dennis Ritchie가 발표한 The Development of the C Language, 1994년 Bjarne Stroustrup이 출판한 The Design and Evolution of C++.

이 글에서 다룬 malloc이 논문에서 언급하거나 벤치마크에서 비교하고 있지만 다루지 못한 malloc들이 있는데 다음과 같습니다: LKmalloc, rpmalloc, scalloc, SuperMalloc, tbbmalloc, Vam. 언젠가 다룰 수 있게 되기를 바랍니다.

끝으로 리눅스에는 glibc 외에도 musl이라는 널리 쓰이는 또다른 C 표준 라이브러리가 있습니다. musl은 버전 1.2.1 이전에는 dlmalloc과 비슷한 malloc 구현을 사용했으나, 2020년 출시된 버전 1.2.1부터는 Rich Felker가 개발한 mallocng라는 이름의 새로운 malloc 구현으로 바꾸었습니다. 이후 버전에서 이에 대한 내용을 반영할 계획입니다.

일러두기

(TODO: line count 재는데 line counter는 뭘 썼고 code size 재는데 compiler는 뭘 썼고 블라블라)

A부터 Z까지

dlmalloc

dlmalloc은 Doug Lea가…

elfmalloc

elfmalloc은…

Hoard

Hoard는 Emery Berger가 1998년부터 개발해온 malloc 구현입니다. Hoard는 쟁인다는 뜻입니다. Hoard의 코드는 C++로 작성되었으며 GitHub에서 관리되고 있습니다. Hoard는 Apache-2.0 라이선스로 제공됩니다.

Emery Berger는 ASPLOS 2000에서 Hoard의 구현에 대해 Hoard: A Scalable Memory Allocator for Multithreaded Applications라는 제목으로 발표하였습니다.

Hoard는 맥과 iOS의 시스템 malloc 구현에 영향을 주었습니다. 해당 변경은 2008년에 반영되어 2009년 macOS 10.6 버전에 출시되었습니다.

jemalloc

jemalloc은 Jason Evans가 2005년부터 개발해온 malloc 구현입니다. jemalloc의 코드는 C로 작성되었으며 GitHub에서 관리되고 있습니다. jemalloc의 문서는 GitHub 위키에서 관리되고 있습니다. jemalloc은 BSD-2-Clause 라이선스로 제공됩니다.

Jason Evans는 BSDCan 2006에서 jemalloc의 구현에 대해 A Scalable Concurrent malloc(3) Implementation for FreeBSD라는 제목으로 발표하였습니다. (논문, 발표 자료)

jemalloc은 2008년 출시된 FreeBSD 7.0 버전부터 FreeBSD의 시스템 malloc 구현입니다. jemalloc은 2008년 출시된 Firefox 3 버전부터 Firefox의 malloc 구현입니다. jemalloc은 2009년부터 Facebook의 malloc 구현입니다.

jemalloc에 대해 한국어로 작성된 글로 하용호님의 마지막 남은 공짜 점심 Facebook의 메모리 할당자 jemalloc이 있습니다.