malloc() 작동 원리

http://blackrain.egloos.com/1224982

글 본문에 대한 내 생각을 밝히는 것이 아니기 때문에 트랙백은 남기지 않았다. 다만 글 쓰신 Gony님이 인용하신 '조엘 온 소프트웨어'의 대목에 많은 오류가 있어서 이렇게 글을 적어본다. 물론 좁은 지면과 독자의 배경 지식을 감안해서 쉽고 간단하게 malloc() 동작 원리를 썼으리라 생각한다. 그러나 실제 방식은 이와 많이 다르다. 혹시나 오해를 가질까 해서 이 글을 쓴다.

malloc이 어떻게 동작하는지 아십니까? malloc의 본질은 사용 가능한 메모리 블록을 연결 리스트linked list로 길게 연결한 자유 체인(free chain)입니다. malloc은 연결리스트를 따라가며, 요청 받은 메모리 양보다 큰 블록을 찾습니다. 이렇게 찾은 블록을 2개로 쪼개서, 하나는 호출한 사용자에게 반환하며, 쪼개고 난 다음에 남아있는 블록은 다시 연결 리스트에 넣어 둡니다. free를 호출할 때, free는 해제한 메모리를 자유 체인에 추가합니다. 결국 자유 체인은 자그마한 조각으로 잘게 쪼개지므로, 큰 조각을 요청하면 원하는 크기를 충족하는 조각이 없을 수도 있습니다. 이럴 경우 malloc이 타임아웃을 선언한 다음에 자유 체인 주위를 샅샅이 훑어 조각을 정렬하고 인접한 작은 자유 블록을 더 큰 블록으로 결합합니다. 이런 작업을 하다 보면 밤이 샐 것입니다. 결국 이 모든 혼란의 끝은 malloc의 성능 특성이 결코 아주 빠르다고 볼 수 없으며(malloc은 항상 자유 체인을 돌아다닙니다), 정리하는 과정에서 종종 예측할 수 없을 정도로 지독하게 느려질 수 있다는 사실로 귀결됩니다.

덧붙여 말하자면, 이런 현상은 가비지 컬렉션을 지원하는 시스템과 동일한 성능 특성이며, 시스템 성능 저하 원인이 가비지 컬렉션(garbage collection)이라는 주장이 전적으로 옳지만은 않다는 놀라운 결론에 도달합니다. 비록 정도는 약하지만, 전형적인 malloc구현을 따를 경우에도 가비지 컬렉션과 유사한 성능저하 문제가 생기니까요.

아 길다. 이걸 직접 타자하신 것 같은 Gony님께 감사의 말씀을 전한다 (띄어쓰기는 손을 좀 봤습니다). malloc의 작동 원리는 보기에는 간단하지만 실제로는 수 많은 최적화가 되어있어서 상당히 복잡하다. malloc 구현은 사실 여러 가지 버전이 있다. 대표적으로 리눅스의 libc에서 사용되는 Doug Lea의 dlmalloc이 있다. 이 외에도 Solaris 플랫폼의 버전도 있고 Win32 Heap 관리 알고리즘도 있다. 약간의 미세한 차이는 있지만 큰 틀은 차이가 없다. 내가 지적하는 것은 모두 Doug Lea의 malloc 구현 (버전 2.8.3)을 바탕으로 이야기 하는 것이다.

malloc구현은 일단 큰 메모리를 시스템으로부터 얻어오는 것으로 시작한다. 리눅스라면 brk/sbrk가 있고, Win32라면 VirtualAlloc이 있다. 이들 함수가 user-level에서 사용할 수 있는 가장 원초적인 메모리 할당 함수들이다. 그러나 이들 메모리 할당 함수들은 그 할당 단위가 크다. 보통 페이지 단위이기 때문에 4KB 정도이다. 그리고 시작 메모리도 이 페이지 크기에 정렬이 되어있어야 하므로, 작은 메모리를 동적으로 할당 받고 쓰기에는 사실 상 불가능하다. 그래서 이렇게 크게 얻어온 메모리 덩어리를 잘게 썰어주고 관리하는 녀석들이 heap management library이다. 그리고 이 malloc 구현은 20년 가까이 된 것이고 속도와 메모리에 상당히 많은 최적화가 되어있다. 속도 보다는 메모리에 보다 더 많은 관심을 기울였다고 볼 수 있다.

또, malloc의 할당 단위는 보통 8byte이고 최소 할당 크기는 16byte 정도 된다. (시스템마다 32/64비트 마다 다를 수 있다). 그러니까 malloc(14)와 malloc(15)를 호출해도 부가 정보를 기록하기 위한 8바이트를 더해 다음 8바이트 단위로 align 시켜서 똑같이 24바이트가 할당 된다.

예를 들어, malloc(16)을 호출해서 100번지의 주소를 반환 받았다면, 92번지에 현재 이 노드가 사용 중인가, 얼마나 할당 하였는가, 혹은 그 전 노드의 크기가 얼마인지를 저장한다. 이러한 노드는 'chunk'라는 구조체로 표현이 되는데 사실 이 보다 더 복잡하다. 비록 8바이트를 metadata를 위해 쓰지만 앞의 chunk가 사용 중이라면 맨 앞 4바이트는 앞 chunk의 데이터로 채워질 수 있다. 그러니까 겹쳐있는 부분이 있다. 메모리를 조금이라도 아끼기 위해 이런 방식을 취했는데 처음 소스 보면 이해하기 쉽지가 않다.

Malloc이 처음 나왔을 당시에는 그 누구도 이걸 악용해서 컴퓨터 제어권을 탈취하는 상황을 생각해 본 사람이 없다. 그래서 보안에는 사실 상 전혀 관심을 두고 있지 않았다. 물론 익히 알려진 consolidation attack등을 막기 위해 몇몇 알고리즘이 바뀌었고, Windows XP SP2에는 metadata 중 security cookie를 넣기도 하였다. 또한, layout obfuscation이라고 랜덤하게 위치를 바꾸어 공격을 어렵게 하는 방법도 채택이 되었다. 그러나 이러한 방식은 복잡도, entropy가 낮아서 결국 무식한 방법, brute-force로 충분히 뚫릴 수가 있다. 8비트 짜리 security cookie가 가지는 경우의 수가 고작 몇 가지 밖에 안되기 때문이다.

그렇다면 직접 조엘이 한 말을 한 문장씩 검증해보자.

malloc이 어떻게 동작하는지 아십니까? malloc의 본질은 사용 가능한 메모리 블록을 연결 리스트 linked list로 길게 연결한 자유 체인 free chain입니다.

사용 가능한 메모리 블록 (free node)을 관리하는 것은 맞다. 그리고 이미 사용중인 메모리 블록은 따로 관리하지 않는다. 단순히 얼마나 많은 메모리가 사용 중인가 (footprint) 정도만 기억할 뿐이고, 실제 heap에 사용 중인 메모리를 확인하려면 일일이 heap을 돌아다니면서 체크해야 한다. 그런데, 이 free node를 절대 우리가 알고 있는 linked-list 형태로 관리하는 것이 아니다. 물론 chunk struct에 forward/backward로 list 스러운 모습이 있지만 결코 linked-list와 같은 형태로 작동되지는 않는다.

malloc은 연결리스트를 따라가며, 요청 받은 메모리 양보다 큰 블록을 찾습니다.

만약 앞 문장에서 독자가 흔히 알고 있는 linked-list를 떠올렸다면 이 대목은 아주 쉽게 이해가 된다. 즉, free node들을 쭉 이은 리스트를 선형 탐색 (혹은 더 똑똑한 탐색을 하던)으로 'first-fit'으로 하는 것으로 이해할 것이다. 그러나 free node는 그냥 무식하게 다 관리가 되는 것이 아니라 그 크기 별로 매우 효율적으로 관리되고 있다. Free node는 먼저, 512 byte보다 작은 경우에는 그 크기 별로 모두 별도로 관리 된다. 물론 이 때는 linked list 형태로 관리가 된다. 즉, 16 byte 짜리 free node 리스트, 24 byte 짜리 free node 리스트, … 이런 식으로 관리한다. 이들 포인터는 smallbins에 저장이 된다. 그래서 만약 512바이트 보다 작은 메모리가 요청 된다면 이 smallbins을 뒤져서 바로 free node 하나를 때어준다. 그러니 탐색을 할 필요 없고 그냥 상수 시간에 요청이 완료 된다.

그리고 이 보다 큰 경우에는 treebins라는 Trie 자료구조를 이용해서 저장이 된다. 그래서 임의의 크기가 들어왔을 때 'best-fit'으로 적합한 free node를 찾는데 결코 시간이 오래 걸리는 작업이 아니다. 트리 같은 구조를 순회를 하기는 하지만 Trie 자료구조 특성상 depth 에 비례하는 time complexity를 가진다. 일반 binary search tree처럼 전체 노드 개수 n과 관계가 없다.

마지막으로 페이지 단위보다 큰 메모리 요청이 들어오면 그냥 바로 mmap이나 VirtualAlloc을 불러버린다. 그래서 크기를 대략 3개의 큰 분류로 나누어서 처리한다. 게다가 비교적 최신 버전 malloc 구현에서는 designated victim이라는 변수를 두어 조금이라도 순회하는 양을 줄이려고 한다.

이렇게 찾은 블록을 2개로 쪼개서, 하나는 호출한 사용자에게 반환하며, 쪼개고 난 다음에 남아있는 블록은 다시 연결 리스트에 넣어 둡니다.

정확한 표현이다. 쓰고 남은 블록은 위에서 설명했듯이 크기가 크다면 treebins으로, 크기가 작다면 바로 리스트에 연결해준다. 그리고 locality를 보존해서 캐쉬 효율성을 높이려는 부분도 엿볼 수 있다.

free를 호출할 때, free는 해제한 메모리를 자유 체인에 추가합니다.

이 말은 맞으나, 단순히 해제한 메모리를 추가하는 것 이외에 coalescing, 즉 병합이라는 과정도 병행한다. 만약 free되는 노드 앞에도 free node라면 그 자리에서 바로 backward-consolidation을 수행한다. 초창기의 heap buffer overflow 어택은 바로 이 과정을 노린 것이었다. 여기에 포인터 연산이 들어가는데, 만약 이 metadata를 엄하게 고쳐놓으면 이상한 곳으로 점프할 수 있었다. 물론 이제는 이렇게 간단하게 heap integrity가 손상 받지는 않는다.

결국 자유 체인은 자그마한 조각으로 잘게 쪼개지므로, 큰 조각을 요청하면 원하는 크기를 충족하는 조각이 없을 수도 있습니다. 이럴 경우 malloc이 타임아웃을 선언한 다음에 자유 체인 주위를 샅샅이 훑어 조각을 정렬하고 인접한 작은 자유 블록을 더 큰 블록으로 결합합니다. 이런 작업을 하다 보면 밤이 샐 것입니다.

첫 번째 문장이야 당연히 맞는 말이지만, 타임아웃 등의 이야기는 전혀 사실이 아니다. 적어도 Doug Lea의 구현에서는 저런 부분을 찾아볼 수가 없다. 위에서도 말했듯이 인접한 작은 자유 블록을 결합하는 것은 free를 할 때 마다 수행을 이미 했다. 그래서 안정된 힙 구조에서 (즉, malloc/free 호출이 끝난 뒤), 인접한 두 블록이 모두다 자유 블록인 경우는 절대 없다. 그래서 자유 체인 주위를 샅샅이 순회해가며 삽질하는 경우가 없다. 무한정 시간이 걸리는 부분은 한 곳도 없다. 그냥 찾다 찾아도 빈 공간이 없으면 (그래 봐야 3~4단계 작업이면 바로 알 수 있음), 그냥 sbrk등을 호출해서 메모리를 늘린다.

만약, 너무 많은 메모리 요구로 힙이 매우 단편화 되어있고, 그리고 최악의 경우가 발생해 매번 자유 블록 보다 큰 메모리가 들어온다고 해도 느려지는 것은 malloc 외적인 요소, 즉 스와핑이나 과도한 페이지 폴트로 인한 것이지 malloc 자체에서 병목현상은 거의 일어나지 않는다고 볼 수 있다. 작은 크기의 malloc/free는 1초당 5백만 번 이상 일어날 수 있을 정도로 상당히 빠르다. 그러나 일반적인 프로그램에서 이런 경우는 매우 찾아보기 힘들다. malloc 때문에 밤샌다는 표현은 비록 과장이지만 너무 터무니 없고 잘못된 인상을 심어주기에 충분하다.

결국 이 모든 혼란의 끝은 malloc의 성능 특성이 결코 아주 빠르다고 볼 수 없으며(malloc은 항상 자유 체인을 돌아다닙니다), 정리하는 과정에서 종종 예측할 수 없을 정도로 지독하게 느려질 수 있다는 사실로 귀결됩니다.

따라서, 이 결론도 완전히 거짓말이다. malloc은 결코 자유 체인을 항상 돌아다니지 않는다. 돌아다니는 것이 아니라 smallbin 뒤지고, treebin 뒤지는 과정만이 있고, 이 과정은 설명하였듯이 O(n)과 같은 시간이 걸리는 것이 아니다. 예측할 수 없을 정도로 느려진다면 이미 이 프로그램 자체가 매우 메모리를 과다하게 쓴다는 그 원초적인 문제 때문이다.

물론, 예전 글에서도 잠깐 언급했는데, malloc은 멀티프로세서를 고려하지 않았다. 그래서 false sharing등이 큰 문제로 대두되어 여러 방법이 나오기도 하였다. 또, 최근 심각한 문제인 heap overflow vulnerability를 어떻게 막을 것인가도 여전히 숙제이다.

주절주절 거리다 보니 정말 글이 길어졌다. 과연 여기까지 얼마나 많은 분께서 다 읽으셨는지 궁금하다. 작년 가을 malloc 가지고 사투를 벌리면서 얻은 그래프나 하나 붙여본다. 3DMark 06 이 수행 도중에 얼마나 많은 malloc을 요청하는지 데이터를 뽑아보았다. 스레드 하나가 아니라 여러 개에서 부르다 보니 이 데이터 얻는데 꼬박 하루를 날렸었다. ㅠ 보면 초당 25만 번 까지도 malloc 요청이 일어나는데 이 정도로는 전혀 heap-intensive라고 부르지 않는다. 최소 2백만 번은 불러야 좀 빡센 프로그램으로 분류할 만큼 malloc은 빠르게 돌아간다.

정작 조엘이 언급하고 있는 가비지 콜렉터 이야기는 다음에 한 번… 흔히 자바에는 가비지 콜렉터 덕 분에 memory leak이 없는 것으로 알고 있지만 이는 잘못된 사실이다. 여전히 memory leak이 존재할 수 있다.