Slab Allocator

슬랩할당자 (Slab Allocator)

작성자
조재혁(minzkn@minzkn.com)
고친과정
2008년 12월 13일 : 어셈러브(http://www.asmlove.co.kr/)의 김기오(gurugio)씨의 Offline study로부터 내용정리
2008년 12월 15일 : 실제 알고리즘을 확인하기 위한 예제구현
2009년 3월 5일 : slab초기화시에 사용가능한 object수를 계산하는 방법으로 변경

여기서 나오는 용어 및 변수명등은 실제 범용적인 이론책에 나온 용어해석과 다를수도 있습니다. 또한 알고리즘의 기본을 강조하고 이해도를 높이기 위하여 실제 보강되어야 할부분들이 제거되어 소개됩니다.

Slab Allocator(슬랩 할당자)는 1994년 Sun Microsystems의 Solaris 2.4라는 운영체제에서 구현된 "Slab allocator"라는 할당전략에서 유래되었습니다.

이 할당전략의 주요 특징으로는 다음과 같은 점이 있습니다.

유지에 필요한 자료구조와 함께 생성자(Constructor), 소멸자(Destructor)를 구현함으로써 일종의 객체로서의 접근을 구현합니다. (하지만 일부 운영체제에서는 객체관점으로 바라보기는 하지만 생성자, 소멸자를 사용하지 않는 경우도 많이 있습니다.)
객체를 불필요하게 반복 초기화 하는 현상을 회피하기 위하여 할당후에 해제되는 객체를 즉각 폐기하지 않고 메모리에 그대로 유지하려는 속성을 가지고 있습니다.
비슷한 크기의 객체를 캐시하는 유사구조를 사용하기 때문에 일반적으로 발생할수 있는 단편화 문제를 해소합니다.
리눅스의 경우 커널에서 사용하는 일련의 구조중에 매우 빈도가 높은 반복할당객체에 대해서 Cache로 바라보고 그에 맞도록 Slab을 구현합니다.
하드웨어 캐시에 정렬될수 있고 컬러링기법이 적용되기 때문에 캐시성능을 높일수 있습니다.

막상 구현을 보시면 해제블록을 할당시 꺼내쓰고 해제시 해제블록에 넣는 것으로 구현이 단순한 알고리즘입니다.

최신 소스 다운로드 : https://github.com/minzkn/slab_allocator
다음은 기본적인 Slab Allocator의 기본구조를 그림으로 나타내어 보았습니다. 크게 slab + nft[slab.objects] + object[slab.objects] 구조로 구성됩니다.

[PNG image (5.99 KB)]

예제에서는 다음과 같은 구조를 설계안(초기화과정: mzslab_init)으로 설정하고 구현하였습니다. 설계안에서는 생성자(Constructor), 소멸자(Destructor)를 고려하였으나 예제코드 구현에서 이 부분은 적절한 객체의 표면화된 예시까지 제시할 필요가 없기 때문에 생략되었습니다.

[PNG image (26.24 KB)]
Slab 자료구조
mzslab_t 의 초기화

가장 먼저 Free object block index (s_slab->f)를 0으로 초기화 하고 Slab index table (s_nftn = n + 1)을 순차적으로 그 다음값으로 초기화 하여 Slab을 사용하기 위한 초기화 동작을 완료합니다.
할당

할당가능한 Free object block index (s_slab->f)에 대응하는 Free object block의 메모리주소 (&s_slab->entry...)를 반환후 s_slab->f가 가르키는 Slab index table (s_nfts_slab->f)에서 가르키는 다음 Free object block index를 s_slab->f로 취하여 할당이 완료되게 됩니다.
해제

할당된 Object block memory 주소 (s_ptr)로부터 해당하는 Object block index (s_index)를 취하고 해당 Object block index의 Slab index table (s_ntfs_index)에 현재 할당 가능한 Freee object block index (s_slab->f)를 저장하고 Object block index (s_index)를 Free object block index (s_slab->f)에 저장하여 해제동작이 완료됩니다.