19. TCMalloc 작동원리

아래의 내용은 다음의 url의 내용 중 작동 원리 부분만 번역하여 정리한 것입니다. 

http://goog-perftools.sourceforge.net/doc/tcmalloc.html

TCMalloc은 스레드별로 스레드가 사용할 로컬 캐쉬를 만들어서 할당한다. 이 영역은 작게 할당되는데 각 스레드의 로컬로 동작하기 때문에 문제가 되지 않는다. 오브젝트들은 필요한 경우 로컬 영역에서 중양 영역으로 이동하기도 하는데, 주기적인 GC(Garbage Collection)이 로컬 영역에서 중앙 영역으로 메모리가 이동될 수 있게 작업을 진행시킨다. 

[그림]

TCMalloc은 Large 오브젝트와 다르게 32kbqㅗ다 작은 사이즈를 가진 Small 오브젝트를 관리한다. Large 오브젝트는 page-level allocator를 사용하여 로컬 영역에 할당하지 않고 중앙 영역에 직접 할당된다. (하나의 페이지는 4k로 메모리에 할당된다.) large 오브젝트는 page의 수만큼 할당하여 공간을 차지하고, 페이지 순으로 정렬된다. 

페이지들의 run은 Small 오브젝트의 수로 잘라질 수 있다. 즉, 하나의 페이지의 run에 128 byte의 32개의 Small Object로 나뉘어 질 수 있다. 

Small Object Allocation 

각각의 Small 오브젝트 size는 대략 170개의 할당 가능한 size-class중의 하나로 맵핑된다. 예를 들어, 961 부터 1024 byte를 사용하는 할당영역은 모두 1024에 맵핑된다.  Small 사이즈의 경우 8 byte로 각각 나누어서 관리하고, Large 사이즈는 16 byte로 나누어서 관리하고, 더 큰 사이즈는 32 byte로 나누어서 size classes에 정리된다. 그리고, 가장 큰 사이즈 공간은 256 byte이다. 

thread cache는 하나의 리스트를 포함하고 있는데, 이 리스트는 각 size class별로 사용할 수 있는 free object들의 리스트를 가지고 있다. 

[그림]

Small 오브젝트 할당방법

1) 먼저, 사용할 수 있는 size-class를 찾아서 맵핑 한다. 

2) 현재의 스레드가 사용할 수 있는 스레드 로컬 캐쉬에서 사용할 수 있는 free list를 찾는다. 

3) free list가 비어있지 않다면, 첫번째 오브젝트를 리스트에서 제거하고 그것을 반환하여 사용하게 한다. 

위와 같이 할당하는 경우 TCMalloc은 lock을 전혀 사용하지 않는다. 락을 할당하여 사용하지 않는 것은 성능 향상에 크게 도움이 된다. 

free list가 비어있다면, 

1) 해당 size class에 해당하는 중앙 영역의 free list에서 사용할 수 있는 오브젝트들을 가져온다. ( 중앙 영역에 위치한 free list는 모든 스레드들이 같이 사용할 수 있다. ) 

2) 스레드가 사용하는 로컬 영역에 해당 오브젝트들을 위치시킨다. 

3) 새롭게 가져온 오브젝트 중 하나를 반환하여 사용하게 한다. 

중앙 영역에 위치한 free list도 비어있다면, 

1) Central page allocator로 부터 페이지들을 할당받는다. 

2) size-class에 오브젝트들로 자른다. 

3) 중앙영역에 위치한 free list로 위치시킨다. 

4) thread local의 free list로 몇개를 이동시킨다. 

Large 오브젝트 할당방법

32K보다 큰 Large 오브젝트들은 4K(page 단위)로 반올림된다. 그리고, Large 오브젝트들은 중앙의 page heapd에 의해 관리된다. 중앙의 page heap 은 free list들의 배열이다. i가 256 보다 작은 경우에 위치하게 되고, 페이지의 수에따라 entry로 나뉘어서 위치하게 된다. 마지막의 256번째 엔트리에는 256개 이상의 페이지들의 묶음이 연결되어있다. 

[그림]

k개의 page들을 할당하려고 하면 k번째 엔트리에가서 찾아보면 된다. 만약, 그 리스트가 비어있다면, 다음 리스트에서 찾으면 된다. 필요한 경우, 가장 마지막 엔트리에서 찾을 수도 있다. 그것도 실패하게 되면 시스템으로 부터 메모리를 패치한다. (이때, sbrk, mmap을 사용하던가 한다. )

k개의page들의 묶음을 할당하려고 할때, 상위 갯수의 페이지 묶음 리스트에서 할당한 경우, 나머지 들은 그 리스트의 적절한 entry로 재배치 된다. 

Span

TCMalloc에서 관리되는 heap은 page의 묶음으로 구성되어있다. 연속된 페이지들의 묶음은 Span 오브젝트로 표현된다. Span은 할당 될 수도 있고, 해제 될 수도 있다. free가 되면, Span은 page heap linked list안의 entry중의 하나가 된다. 할당되면, 어플리케이션에 넘겨진 Large 오브젝트가 되던가, Small 오브젝트의 순서에 따ㅏ 분할된 페이지들의 묶음이 된다. Small 오브젝트들로 나뉘어 지면, 오브젝트의 size class가 Span안에 기록된다. 

페이지의 수에따라 정렬된 Central 배열은 페이지에 속한 Span을 찾아서 사용되어진다. 예를 들어 다음과 같이 각각의 a,b,c,d Span에 페이지들이 할당되었다고 가정하자. a는 2개의 페이지를 차지하고 있고, b는 1개, c는 5개, d는 3개의 페이지를 차지하고 있다고 하자. 그럼, 다음의 그림처럼 구성된다. 

[그림]

32-bit 주소 체계에서는 2의 20승의 4k 페이지를 위치시켜 사용할 수 있다. 그래서, 중앙의 리스트 배열은 4MB의 공간을 배열 공간으로 사용하게 된다. 64-bit 주소 체계에서는 Span 포인터에 상응하는 page number의 맵핑 배열을 대신해서 3-레벨의 radix tree를 사용한다. 

Deallocation 

오브젝트를 해제할 때, 그것의 page number를 계산하고, 상응하는 Span 오브젝트를 찾기 위해 Central array를 뒤진다. 그 Span은 오브젝트의 크기가 작은지 큰지, 작으면 어느 szie-class에 위치하는지를 알려준다. 오브젝트가 Small이라면, 현재의 thread의 로컬 캐쉬의 적절한 free list에 해당 오브젝트를 위치시킨다. 스레드 캐쉬가 기본 크기보다 커지는 경우(기본값은 2M), Cenral free list로 사용하지 않는 객체를 반환하기 위해 GC를 실행한다. 

오브잭트가 Large라면, Span은 우리에게 해당 오브젝트를 받아 들일 수 있는 페이지의 크기를 알려준다. 그 위치가 [p.q]라고 한다면, p-1 페이지 부터 q+1까지 페이지를 검색하게 되고, 만약 free라면 다 같이 병합해 버린다.  그리고 그 결과를 page heap의 리스트에 포함시켜 버린다. 

Central Free Lists for Small Objects

앞에서 각 size-class별로 Central free list를 관리 한다고 이야기 했었다. 각 Central free list는 두개의 레벨로 데이터 구조를 만들어 관리한다. 하나는 Span의 묶음, 하나는 Span에 따른 free 오브젝트의 링크드 리스트. 

오브젝트는 몇몇의 Span의 리스트의 첫번째 entry를 삭제함으로 Central free list로 부터 할당된다. (모든 Span이 비어있는 리스트를 가지게 되면, Central page heap으로 부터 사용가능한 사이즈의 span을 첫번째로 할당 받게 된다. )

오브젝트는 포함된 Span의 리스트에 추가됨으로 Central free list에서 해제된다. 그리고, Span안의 Small 오브젝트의 전체 수와 리스트의 길이가 같으면, Span은 page heap에 반환하고, free가 된다. 

Gabage Collection of Thread Caches

스레드 캐쉬는 캐쉬안의 모든 오브젝트의 사이즈가 2M를 넘어가면 GC를 실행한다.  GC의 이 기준점은 스레드의 수가 증가할수록 자동적으로 감소된다. GC를 실행하면 캐쉬안의 free 리스트를 모두 찾아서, Central list로 이동시킨다. 

The number of objects to be moved from a free list is determined using a per-list low-water-mark L. L records the minimum length of the list since the last garbage collection. Note that we could have shortened the list by L objects at the last garbage collection without requiring any extra accesses to the central list. We use this past history as a predictor of future accesses and move L/2 objects from the thread cache free list to the corresponding central free list. This algorithm has the nice property that if a thread stops using a particular size, all objects of that size will quickly move from the thread cache to the central free list where they can be used by other threads.