Slub은 이미 많은 블로그에서 자세히 설명하고 있습니다. 따라서 해당 포스트에서는 중복된 내용을 작성하기보다는, Slub의 기본적인 컨셉을 빠르게 이해하는데에 초점을 맞춥니다. 해당 포스트가 Slub 자료 구조가 어떻게 동작하는지 이해를 도와 다른 글들을 이해하는데에 도움이 되었으면 합니다 :)
주의! 쉬운 이해를 위해 SLUB이 처음 도입된 Linux kernel v2.6.21을 다루고 있습니다.
Slub 기본 컨셉과 자료 구조
SLUB이 메인 라인에 처음 도입되었을 때(Commit: "SLUB core")의 대략적인 자료 구조는 아래 그림과 같습니다.
kmem_cache(가장 큰 사각형)이 특정 오브젝트들의 할당과 해제를 관리합니다. 오브젝트의 크기와 align과 같은 기본적인 정보를 저장하고 있습니다. 단순하게 오브젝트들을 하나의 free list(linked list)로 관리할 수도 있지만, SMP(symmetric multiprocessing)과 NUMA(Non-uniform memory access)를 고려하여 설계되었습니다.
kmem_cache는 아래 코드와 같이
Node마다 kmem_cache_node 구조체로 Partial list를 관리합니다.
CPU마다 Slab 페이지를 가지고 있습니다.
Node 별로 kmem_cache_node 구조체를 가지며, 멤버 변수 partial에 Slab 페이지들을 연결합니다.
위 코드에서 보았듯이 CPU slab 또는 kmem_cache_node는 모두 페이지 디스크립터(struct page*) 단위로 Slab을 관리합니다. 이때, CPU가 가지고 있는 Slab 페이지는 Active 상태라 하고, CPU가 가지고 있지 않은 Slab 페이지는 Deactivated된 페이지라고 합니다.
또한 아래에서 볼 수 있듯이 SLUB의 특징 중 하나는, 여러 메타 정보들을 페이지 디스크립터에 union의 형태로 정의하여 사용하는 것입니다.
위 코드에서 볼 수 있듯이, Slab 페이지로 사용될 때 사용되지 않는 필드들(_mapcount, index)를 union으로 묶어 페이지 디스크립터의 크기를 늘리지 않도록 노력한 모습을 엿볼 수 있습니다. 추가된 중요한 멤버 변수들은 아래와 같습니다.
inuse는 해당 페이지에 사용 중인 오브젝트의 수를 저장합니다.
kmem_cache는 해당 페이지가 속한 kmem_cache의 주소(백 링크)를 저장합니다.
freelist는 해당 페이지에 사용 가능한 오브젝트의 주소를 저장합니다. 이를 통해 오브젝트들과 단뱡향 리스트의 형태로 연결됩니다.
이제 Slab 페이지 내의 오브젝트들이 어떤 식으로 구성되었는지 살펴보도록 하겠습니다. 오브젝트들은 다음 사용 가능한 오브젝트의 위치를 저장하는 포인터 뿐만 아니라 용도에 따라 다양한 추가적인 영역들을 가지고 있습니다.
Redzone: 디버그 용으로 Redzone이 활성화되면, 특별한 값을 이 영역에 저장합니다. 이 값이 변화되었는지를 통해 buffer overflow를 확인할 수 있습니다. 비활성화 되어 있다면 해당 영역은 존재하지 않습니다.
Track: 디버그 용으로 track 옵션이 활성화 되어 있다면, 해당 오브젝트를 alloc/free할 때의 정보를 저장하는 영역을 배정합니다. 비활성화 되어 있면 해당 영역은 존재하지 않습니다.
Free pointer는 오브젝트 영역에 있을 수 있고, 오브젝트 영역 밖에 있을 수 있습니다. 아래의 첫 번째 그림은 free pointer가 오브젝트 영역 밖에 있는 그림입니다. 두 번째 그림은 free pointer가 오브젝트 영역 내에 있는 그림입니다.
위에서 살펴 본 오브젝트들은 Slab 페이지에 차곡차곡 배치되어 있고, 사용 가능한 오브젝트들은 free pointer으로 단방향 리스트를 이루고 있습니다.
이렇게 SLUB의 자료 구조들을 살펴보았습니다. 이제 이 자료 구조에 대한 여러 함수들을 살펴보도록 하겠습니다.
Slub 관련 함수
slab_alloc
slab_alloc이 호출되면, Per CPU Slab 페이지에 사용 가능 한 object를 반환합니다. 바로 이 과정을 fast path라고 합니다. 구체적인 구현은 아래의 코드를 보면서 살펴보도록 하겠습니다.
11~13번 라인: 현재 CPU가 Slab 페이지를 보유하는지 확인한다.
19번 라인: object의 주소를 가지고 온다.
26~27번 라인: Page에 저장된 메타 정보들을 업데이트한다.
만약, 로컬 CPU가 Slab 페이지가 없거나 Slab 페이지 내에 사용 가능한 오브젝트가 없다면, another_slab 또는 new_slab 라벨로 점프하게 됩니다. 로컬 CPU가 사용할 slab 페이지를 채우기 위해 두 가지 방식을 취할 수 있습니다.
kmem_cache_node에서 slab 페이지를 가져온다.
Buddy allocator를 통해 새로운 페이지를 할당 받고, 이 페이지를 slab 페이지로 초기화합니다.
구현에서는 1번을 시도한 뒤, 실패한다면 2번을 시도하도록 되어 있습니다. 구체적인 구현은 아래 코드와 같습니다.
7번 라인: Per CPU로 등록된 Slab 페이지를 해제한다.
10번 라인: Per Node partial list에서 Slab 페이지를 가지고 온다. 가지고 온 페이지를 Per CPU Slab 페이지로 등록한다.
18번 라인: Partial list에서 Slab 페이지를 찾지 못하였으므로, new_slab 함수를 통해 새로운 Slab 페이지를 할당 받는다. 해당 함수 내부에서는 Buddy allocator을 통해 페이지를 할당 받고 Slab 페이지로써 초기화한다.
21~25번 라인: 현재 CPU에 등록된 Slab 페이지가 없다면, have_slab 라벨로 이동하여 할당 받은 Slab 페이지를 현재 CPU에 등록한다.
slab_free
오브젝트를 free힐 때, 오브젝트가 속한 Slab 페이지를 가져와 freelist에 반환된 오브젝트를 삽입합니다. 이 Slab 페이지가 Active한(CPU가 잡고 있는) 경우라면, 더 이상할 일이 없기에 리턴합니다. 만약, 이 Slab 페이지가 active하지 않은 경우에는 두 가지를 살펴봐야 합니다.
Slab 페이지에 사용 중인 오브젝트들이 없다면, discard_slab 함수를 통해 해당 Slab 페이지를 buddy system으로 반환합니다.
만약 Slab 페이지의 모든 오브젝트가 사용되어 kmem_cache_node의 partial 리스트에서 관리되지 않았다면, 해당 페이지를 partial 리스트에 넣습니다.
13~15번 라인: page는 오브젝트가 속한 slab 페이지입니다. 따라서 반환된 오브젝트를 freelist에 insert하는 작업입니다.
17~22번 라인: 오브젝트가 Active한 Slab 페이지에 반환되었다면, 더 이상해야할 일이 없습니다.
24~34번 라인: 해당 Slab 페이지 내에 더 이상 사용하고 있는 object가 없다면 buddy system에 반환하는 절차를 밟게 됩니다. 만약 Slab 페이지가 kmem_cache_node의 Partial list에 연결되어 있다면, remove_partial을 통해 리스트에서 제거합니다. 마지막으로 discard_slab 함수를 호출하여 버디 시스템에 반환합니다.
41~42번 라인: 이전까지해당 Slab 페이지에 사용 가능한 오브젝트가 없던 경우이므로, 이제 사용 가능한 오브젝트가 생긴 slab 페이지를 add_partial 함수를 통해 partial list에 넣습니다.
핵심적인 함수들 slab_alloc과 slab_free에 대해 살펴보았습니다. 이제 slab_alloc/slab_free에서 사용된 다른 함수들을 살펴보겠습니다. 이 부분은 Slub에 대해 간단하게 알고 싶은 분들은 넘어가셔도 괜찮습니다.
new_slab
new_slab 함수는 buddy allocator에서 새로운 페이지를 할당받고, 그 페이지를 slab 페이지로 초기화해주는 함수였습니다. 따라서 내부 구현은 크게 3가지의 파트로 나뉩니다.
Buddy allocator에서 페이지 할당
페이지 디스크립터에 메타 정보들 초기화
페이지 안의 오브젝트들 초기화
이 3가지의 파트가 어떻게 구현되었는지 아래의 코드에서 살펴보도록 하겠습니다.
16번 라인: allocate_slab 함수에서는 내부적으로 alloc_pages 함수를 호출합니다. 이때 페이지의 order은 kmem_cache.order을 사용합니다.
24~30번 라인: 페이지 디스크립터에 여러 메타 정보들을 초기화합니다. 참고로 28~30번 라인에서 볼 수 있듯이 디버그 옵션이 활성화되어 있다면, PG_error 플래그를 설정합니다(크게 중요하진 않습니다).
39~44번 라인: 이제 오브젝트들을 free pointer를 사용해 연결시킵니다.
45번 라인: 각 오브젝트 별로 초기화를 진행합니다. Redzone, poisoning, track 중 활성화 된 것이 있으면 관련 영역들을 초기화 합니다. 또한 kmem_cache의 ctor이 존재한다면 object 별로 ctor을 호출합니다.
46번 라인: freelist의 마지막 노드는 NULL을 가르킵니다.
discard_slab
discard_slab은 new_slab과 짝을 이루는 함수로, slab 페이지를 다시 buddy system으로 반환해주는 일을 합니다. 하는 일들은 new_slab에서 했던 일들을 역순으로 진행합니다. 따라서 구현은 3가지의 파트로 구성되어 있을 것입니다.
페이지 안의 오브젝트들 파괴
페이지 디스크립터에 메타 정보들 리셋
Buddy allocator으로 페이지 반환
이제 코드를 살펴보도록 하겠습니다.
주의! 이해를 위해 discard_slab 함수에서 다른 함수 호출을 전부 embed 하였습니다. 하지만 실제 동작과는 큰 차이는 없습니다.
7~8번 라인: 페이지 디스크립터의 메타 데이터를 전부 리셋합니다. (_mapcount는 inuse와 offset과 union으로 묶여 있습니다.)
10~21번 라인: 디버그 또는 dtor이 존재한다면, 오브젝트 별로 검사 및 dtor을 호출합니다.
39번 라인: 버디 시스템에 해당 페이지를 반환합니다.
add_partial/remove_partial
kmem_cache_node의 partial 리스트에 추가 삭제의 기능을 담당하는 함수들입니다. 구현이 복잡하지 않으므로 별도의 설명은 하지 않겠습니다.
deactivate_slab/flush_slab
decativate_slab와 flush_slab 함수는 allocate_slab 함수에서 잠깐 등장했습니다. deactivate_slab 함수는 deactivate라는 이름처럼, Active 상태의 slab 페이지를 active하지 않은 상태로 변환하는 함수입니다. 구현이 어렵지 않으니 아래의 코드를 살펴보겠습니다.
6~7번 라인: 로컬 CPU의 cpu_slab을 NULL로 세팅하고, page의 Active 플래그도 내립니다.
9~12번 라인: 만약 deactivate하려는 페이지에 사용 가능한 오브젝트가 있다면 이 페이지는 kmem_cache_node의 partial 리스트 이동하여 관리됩니다. 그 반대로 모든 오브젝트가 사용 중이라면 별도의 리스트로 관리되지 않습니다. 14~15번 라인: 만약 페이지에 사용 중인 오브젝트가 하나도 존재하지 않는다면, discard_page를 통해 buddy system에 반환합니다.
이때, deactivate_slab은 이미 page에 lock을 잡은 상태로 가정합니다. flush_slab의 경우 이 함수 내부에서 lock을 잡은 다음 deactivate합니다.
get_partial/ get_partial_node/get_partial_any
alloc_slab에서 새로운 slab 페이지를 partial list에서 가져올 때 사용되는 함수는 get_partial이였습니다. 해당 함수는 local node에서 우선으로 get_partial_node 함수를 통해 partial list를 검색하고, 실패한다면 get_any_partial 함수를 통해 다른 노드들의 partial list를 검색합니다. 구현은 아래와 같이 단순합니다.
get_partial_node는 특정 노드의 kmem_cache_node의 partial list를 순회하면서, 사용 가능한 페이지를 pop합니다.
get_any_partial 함수는 defrag_ratio라는 파라미터를 통해 다른 노드의 partial list를 검색할 지 또는 새로운 slab 페이지를 할당할 지의 비율을 결정합니다. 다른 노드에서 검색하기로 결정하면 접근 가능한 노드에 대해 get_partial_node 함수를 호출하고, 페이지를 찾았다면 반환합니다.
한 가지 살펴볼 부분은 Line 28~29 입니다. get_cycles 함수는 현재 cpu_cycles를 가져오고 그 값은 매 번 호출 때마다 달라집니다. 이 값을 1024로 모듈러 연산을 하여 0부터 1023의 값을 가질 수 있습니다. 이 시간에 따라 변화하는 값을 sys 파일 시스템을 통해 값을 조절할 수 있는 defrag_ratio와 비교 합니다. 이런 식으로 다른 노드들의 검색하는 비율을 조절합니다.
Slub Lock
Slub에서는 2가지의 lock을 사용합니다.
Slab 페이지 내부 자료구조(ex freelist)을 보호하기 위해 PG_locked 플래그를 사용합니다.
kmem_cache_node의 partial list를 보호하기 위해 스핀 락인 list_lock을 사용합니다.
Slab 페이지의 PG_Locked 플래그는 아래의 래핑 함수들을 이용하여 설정됩니다.
마무리
지금까지 3천 줄 남짓한 분량의 초기 Slub을 살펴보았습니다. 최신의 Slub은 lockless 구조와 Premption에 관련된 패치 등등 다양한 변화가 있었습니다. 하지만 초기의 컨셉은 여전하며 최신 코드의 이곳저곳에서 여러 흔적들을 발견할 수 있습니다. 끝으로 최신 버전의 분석 글들을 소개하며 마치겠습니다.
Todo.
Todo. Lockless 패치 포인트 설명?
page의 freelist와 counter의 경쟁조건. cmpxchg_double을 통해 lockless하게 구현한다.
alloc_thread와 slab free thread
Lockless (and preemptless) fastpaths for slub(8a5ec0ba42c4919e2d8f4c3138cc8b987fdb0b79)
Cache line bouncing
dfb4f09609827301740ef0a11b37530d190f1681
cmp_xchg 첫 도입 패치
1f84260c8ce3b1ce26d4c1d6dedc2f33a3a29c0c
후속 revert(다양한 이유로...)
00e962c5408b9f2d0bebd2308673fe982cb9a5fe
Todo. Fast path에서 Preemption
SLUB: Alternate fast paths using cmpxchg_local(1f84260c8ce3b1ce26d4c1d6dedc2f33a3a29c0c)
Todo. Fast path에서 Preemption이 가능하더라도 자료 구조 갱신하는 포인트.
premption_disable과 alloc_thread와 slab free thread
Todo. /sys/kernel/slab/-/validate trace 확인 Config?
일종의 bootstratp.(kmalloc을 사용하기 위해 초기화를 하는데 그 때 kmalloc이 필요하다?)
コメント