Glibc malloc Internals

Glibc malloc Internals

직접 소스코드를 분석하다가 너무나도 많은 매크로 함수 및 유틸 함수들을 해석하다 진절머리가 나서 glibc의 위키를 먼저 보고 분석하기로 했다.

malloc()의 간단한 역사를 소개하자면 ptmalloc(pthreads malloc)의 구현을 가져왔으며 ptmalloc은 Doug Lea가 구현한 malloc을 기반으로 하고 있다. glibc 소스트리에 포함시킨 후 독립적으로 발전해나갔기 때문에 ptmalloc의 구현과 glibc의 malloc의 구현은 상당히 차이가 난다. 다른 구현과 달리 여러 사이즈의 청크(Chunk, 또는 덩어리)가 존재하는 힙 스타일의 malloc이다.

용어 정리

앞으로 사용할 여러 용어에 대해 미리 정리하면 뒤의 내용 이해가 쉬워지기 때문에 사용되는 용어에 대해 먼저 정리를 한다. 용어 정리이기는 하지만 용어들이 glibc의 malloc에 핵심이 되는 자료구조에 대한 것이기도 하기 때문에 큰 그림을 그리는데 도움이 될 수 있다.

• 아레나(Arena): 한 개 이상의 스레드가 공유하는 구조체로 여러 힙에 대한 reference를 가지고 있으며 reference하고 있는 힙에 속한 free한 메모리 청크들의 연결리스트를 가지고 있다. 각 아레나에 속한 스레드는 아레나의 free 메모리 청크 리스트를 통해 메모리를 할당 받는다.
• 힙(Heap): 메모리 청크로 나누어 할당되는 연속적인 메모리 공간. 각 힙은 정확히 하나의 아레나에 속하게 된다.
• 청크(Chunk): 작은 범위의 메모리로 유저에게 할당되거나 free되거나, 인접한 다른 청크와 합쳐져 하나의 메모리 청크가 되기도 한다. 청크는 실제 데이터와 함께 메모리 블록에 대한 메타 데이터를 저장한다. 각 청크는 하나의 힙에 존재하며 따라서 하나의 아레나에 속하게 된다.
• 메모리: 어플리케이션의 주소 공간이며 RAM 또는 스왑 파티션에 저장될 수 있다. 이 글에서는 사용하는 메모리는 일반적인 의미에서의 메모리를 일컫는 것으로 real memory 또는 virtual memory하고는 무관하다.

Chunk란 무엇인가

이미지 출처: glibc wiki

• 메모리는 여러 사이즈의 힙으로 나누어진다.
• 각 청크는 해당 메모리 블록의 크기와 다음 청크가 어디있는지와 같은 메타 데이터를 저장하고 있다.
• 청크가 free되면 아레나가 쉽게 맞는 사이즈의 청크를 찾기 위한 여러 데이터를 저장하여 아레나의 리스트에 저장한다.
• free된 청크의 마지막 워드는 해당 청크의 사이즈를 가지고 있다.
• 사이즈 필드의 3비트의 LSB는 플래그로 사용된다.
  • A(0x04): 메인아레나일 떄 0이 된다.
    • 메인 아레나는 어플리케이션의 힙을 사용하며 다른 아레나는mmap으로 할당 받은 힙을 사용한다.
    • 이 때문에 메인 아레나에 속한 청크인지 확인하는 작업이 필요하다.
  • M(0x02): 메모리 청크 전체가 mmap으로 할당받았으면 1이 된다. 1이면 어느 한 힙에 속하지 않는 상태가 된다.
  • P(0x01): 이전 청크가 사용되면 1이 되며 이 때 prev_size valid하지 않게 된다. fastbin에 속한 청크인 경우 이전 청크가 어플리케이션 입장에서는 free되도 P 비트를 사용한다. 사실 이 비트의 실제 의미는 coalescing의 대상이 되냐 안되냐를 의미한다.
• 청크는 메모리상에서는 인접해있기 때문에 첫 청크의 주소만 알아도 전체 청크를 순회할 수 있다. 단, 마지막 청크에 도달했는지 확인하는 것은 어렵다.
• 힙은 항상 2의 승수 형태의 메모리 주소로 align된다. 따라서 어떤 청크가 속한 힙의 정보를 쉽게 확인할 수 있다. 예를 들어 청크의 메모리 주소(mchunkptr)이 0x7ffa6b3414123dc0라면 heap_info*를 0x7ffa6b3414000000에서 찾을 수 있으며 zero bit의 수는 HEAP_MAX_SIZE 상수를 통해 확인할 수 있다.

아레나와 힙

• 여러 스레드가 메모리 할당을 위해 벌이는 경합을 최소화 하기 위해 독립적인 메모리 공간을 가지는 아레나를 만들어 스레드가 하나의 아레나에 속하도록 만든다.
• 메인 아레나는 어플리케이션이 시작되면서 갖게되는 힙으로 메인 아레나를 가리키는 정적 변수가 있으며 next 멤버 변수를 통해 다른 아레나에 접근할 수 있다.
• 메인 아레나를 제외한 아레나는 총 CPU의 수 * 8이 된다. 예를 들어 코어가 4개인 CPU의 아레나의 총 수는 32 + 1(메인 아레나)가 된다.
• 각 아레나는 뮤텍스를 가지고 있다. 모든 아레나 접근에 대해 뮤텍스 락을 사용해야되는 것은 아니며, fastbin을 통해 메모리를 할당 받는 경우에는 뮤텍스를 걸지 않아도 된다. 스레드가 메모리를 할당받으려고 할 때 락이 걸리지 않은 아레나를 찾을 떄까지 순회하여 찾는다.

• 각 아레나는 한개 이상의 힙으로부터 메모리를 얻는다. 메인 아레나는 프로그램이 시작될 떄 할당받는 힙을 사용하며 다른 아레나는 mmap을 통해 힙 메모리를 할당받는다. 각 아레나가 사용하는 힙을 다 사용하면 새로운 힙을 할당한다.

• 각 아레나에 속한 청크는 어플리케이션이 사용중이거나 free한 청크일 수 있다. 어플리케이션이 사용중인 청크는 아레나가 관리하지는 않지만 free한 청크는 아레나 내의 여러 bin 중 하나에 속할 수 있으며 어떤 bin에 속할지는 청크의 크기와 history에 따라 결정된다.
  • Fast: 작은 청크들은 사이즈가 고정된 bin에 저장된다. fastbin에 저장된 청크는 다른 인접한 청크와 합쳐지지 않으며 필요하면 다른 bin으로 옮겨질 수 있다. 같은 크기의 청크들로 구성되어 있기 때문에 단방향 연결리스트로 관리한다.
  • Unsorted: 청크들이 free가 되면 일단 하나의 bin에 저장되며 나중에 크기에 맞게 정렬된다. 이렇게하면 재사용시 빠르게 메모리를 할당받을 수 있게 된다.
  • Small: 일반적인 bin은 여러 개의 “small” bin(각 청크가 같은 사이즈를 가짐)과 “Large” bin(다양한 사이즈를 가짐)으로 나누어진다. 어떤 청크가 이 bin에 들어가게 되면 일단 인접한 청크를 찾아서 하나의 청크로 합치는 작업을 하기 때문에 각 청크들은 인접하지 않는다. 양방향 연결 리스트로 관리된다.
  • Large: 한 bin이 여러 종류의 크기의 청크를 갖게 되면 Large로 취급한다. small bin이라면 사이즈에 맞는 청크를 골라 사용하기만 하면 되지만 large bin은 가장 적절한 청크를 찾아야되며 적절한 청크가 없다면 원하는 사이즈가 되도록 청크를 2개로 나누는 작업을 할 수도 있다.

Large bin인 경우 적절한 크기의 청크를 찾기 위해 순회해야 한다. fd_nextsize를 따라 순회하면 큰 크기의 청크에서 작은 크기의 청크로 순회할 수 있다.

Thread Local Cache(tcache)

• NUMA 아키첵처에서의 최적화를 위해 도입
• 각 스레드는 스레드 로컬한 변수를 가지게 되며 이 변수는 가장 마지막으로 사용된 아레나를 가리킨다.
• 메모리를 할당 받을 때 스레드 로컬한 아레나가 사용중이라면(뮤텍스 락) 아레나를 사용할 때까지 블락된다.
• 어떤 아레나도 사용해본 적이 없다면 다른 아레나를 재사용하거나, 새로 아레나를 만든다.
• 각 스래드는 tcache라고 불리는 캐시를 가지게 되며 아레나에 락 걸 필요 없이 바로 접근 가능한 청크를 보관한다.
  • 단방향연결리스트의 배열로 관리된다.
  • 각 배열의 인덱스는 같은 크기를 가지는 단방향연결리스트를 가지고 있다.
  • fastbin과 다른 점은 tcache는 각 bin마다 가질 수 있는 청크의 수가 제한되어 있다는 점이다.
  • tcache에서 요청한 크기의 청크를 찾을 수 없다면 다음으로 큰 크기의 청크를 사용하는 것이 아니라 정상적인 malloc 루틴을 진행하게 된다.

malloc 알고리즘

1. tcache에 정확하게 맞는 사이즈의 청크가 있다면 tcache에서 청크를 할당한다.
2. 요청한 메모리의 크기가 M_MMAP_THRESHOLD보다 크다면 mmap을 사용해 할당한다.
3. fastbin에 요청한 크기의 청크가 있다면 fastbin에서 청크를 할당한다. 같은 크기의 청크를 더 사용할 수 있다면 tcache에 해당 청크들을 미리 채운다.(pre-fill)
4. smallbin에 요청한 크기의 청크가 있다면 smallbin에서 청크를 할당한다. fastbin과 마찬가지로 같은 크기의 청크를 더 사용할 수 있다면 tcache에 해당 청크들을 미리 채운다.(pre-fill)
5. 요청한 크기가 위의 bin에서 찾을 수 없을 정도로 크다면, fastbin의 모든 청크를 unsorted bin으로 옮기고 coalescing한다.
6. coalescing한 청크들을 다시 small/large bin으로 옮긴다. 옮기는 과정에서 요청한 크기의 청크가 있다면 그걸 사용한다.
7. 여전히 원하는 크기의 청크를 찾을 수 없다면, large bins에서 요청한 사이즈보다 크면서 가장 작은 청크를 찾는다.
8. fastbin에 청크가 남아있다면, fastbin에서 모든 청크를 합치고 6번과 7번 과정을 반복한다.
9. “top” 청크를 나눈다.

free 알고리즘

free는 실제로 OS에 메모리를 반환하지 않는다. 하지만 힙의 top chunk가 충분히 크다면 그 메모리는 unmap되어 OS에 반환될 수 있다.

1. tcache에 자리가 있다면 tcache에 저장한다.
2. fastbin에 들어갈 정도로 작다면, fastbin에 넣는다.
3. 청크가 mmap된 청크라면 munmap한다.
4. 다른 free한 청크와 인접한지 확인해 합친다. 합친 청크를 unosrted list에 넣는다.
5. 청크가 크다면, 다른 fastbin의 청크와 합친 후 top chunk가 충분히 큰지 확인한다. 충분히 크다면 OS에 반환한다.

아레나 바꾸기

• 일반적으로는 한 스레드에 아레나가 할당되면 바뀌지 않는다. 그러나 어떤 경우에는 바뀔 수 있다.
• 스레드가 자신이 속한 아레나에서 메모리를 할당받지 못한다면
  1. 청크 합치기를 수행중이거나, free list 중이거나, unosrted list를 처리하는 중이라고 볼 수 있다.
  2. 또는, 힙 확장(expansion) 중에 sbrk가 실패했거나 새로운 mapping을 하는데 실패했다고 볼 수 있다.
• 아레나를 바꿀 때 이전에 사용했던 아레나가 메인 아레나가 아니라면 arena_get_retry를 통해 메인 아레나로 바꿀 수 있다. 반대로 이전에 사용했던 아레나가 메인 아레나라면 같은 함수를 통해 메인 아레나가 아닌 다른 아레나로 바꾸게 된다. 싱글스레드는 메인 아레나만 사용하기 때문에 해당 사항이 없다.

결론

유저가 코드 상에서 malloc()을 호출하면 그 즉시 malloc에 해당하는 시스템 콜을 호출하는 것이 아니라 시스템 콜을 최소화하기 위해 여러가지 메모리 블록을 캐싱해놓는다는 것을 알았다. 오버헤드가 상당히 있어보이기 때문에 호출 자체를 최소화하거나 어쩔 수 없이 호출을 많이 해야되는 상황이라면 미리 할당을 해 놓은 후 메모리 풀 형태로 사용하는 것이 더 좋을 것 같다.