Slub Allocator 동작 방식
ref
OverView
- Page Allocator(Buddy): 페이지 할당을 요청하면 실제 물리 주소의 페이지를 할당해준다.
- Slab Allocator: 할당받은 페이지를 slab 이라는 객체 단위로 쪼개서 사용한다. 커널은 같은 모양의 객체를 반복해서 사용하기 때문에 효율적인 메모리 관리를 위해 사용한다.
- Slub Allocator: 슬랩할당자는 복잡한 큐 기반 캐싱 방법을 사용하는데, 최신 리눅스는 단순화하고 성능을 개선한 슬럽할당자를 사용한다.
커널영역에서 사용하는 대부분의 메모리 할당은 Slub Allocator라는 추가적인 계층 위에서 할당받은 Page 프레임을 더 쪼개서 사용한다.
Slab Allocator
커널이 할당하는 객체는 유형과 크기에 따라 캐시에 아래처럼 저장된다.
고정된 수, 고정된 크기의 객체 모임을 하나의 슬랩이라고 부른다.
각 캐시는 슬랩들을 가리키고 있는데, 전부 꽉찬 슬랩, 일부 객체만 할당된 슬랩, 완전히 빈 슬랩으로 나뉘어 연결리스트로 관리된다.
커널이 객체를 할당하려할 때 부분슬랩이나 빈 슬랩이 없는 경우에만 Page Allocator를 통해 PAGE SIZE 단위로 물리적으로 연속된 페이지를 슬랩으로 할당받게 된다.
Slub Allocator
Slab vs Slub
Slab, Slub, Slob은 커널메모리를 다른 구조로 관리하게되며, 작은 임베디드는 Slob, 최신 리눅스는 Slub Allocator 를 사용하기 때문에 이 이후에는 Slub이라고 생각하면 된다.
커널은 이 슬랩할당자들을 컴파일 시점에 선택할 수 있게 제공하고 있다.
kmem_cache의 구조체부터 모양이 달라지기 때문에 mm/slab.h 에는 공통으로 사용하는 코드를 확인할 수 있고 include/linux/slab_def.h, include/linux/slub_def.h 등의 파일에서 할당자에 맞는 구조체를 볼 수 있다.
#ifdef CONFIG_SLAB
#include <linux/slab_def.h>
#endif
#ifdef CONFIG_SLUB
#include <linux/slub_def.h>
#endif
Slab Allocator 구조
위에서 Slab을 설명할 때 있던 그림이 Slab Allocator 이다.
slab.c (array_cache), slab_def.h (kmem_cache), slab.h (kmem_cache_node), struct slab
해제된 object는 CPU코어의 L1캐시에 남아있을 수도 있고, 공유 cache에서 가져오려면 lock이 필요하기 때문에 cpu캐시에서 재사용하면 효율이 좋다.
kmem_cache별로 크기가 일정하기 때문에 크기는 신경쓸 필요 없이 entry에서 꺼내서 할당해주면 된다.
cpu_cache에 저장된 메모리주소를 this_cpu_ptr 같은 매크로로 접근하면 CPU코어번호 기반 주소로 변경되어 접근할 수 있다.
array_cache → slabs_partial → slabs_free → new page 순으로 할당된다.
[ kmem_cache (ex. kmalloc-64) ]
├─ cpu_cache ─────> [ array_cache (per cpu) ]
│ void *entry[] # 최근 해제된 free object ptr 스택 (CPU별로 관리)
│ uint limit # 캐시 최대 크기. 초과되면 batchcount 단위로 kmem_cache_node에 반납
│
└─ node[] ────────> [ kmem_cache_node (per node) ]
├─ slabs_partial ────┐
├─ slabs_full ───────┼──> [ struct slab ] # from kernel 5.17
└─ slabs_free ───────┘ slab_cache
slab_list : kmem_cache_node 에 연결하기 위한 구조체
┌─────────────── freelist : 해제된 object 확인하기 위한 인덱스배열
[2][0][3][1] active : 사용중인 object 수
│ s_mem : 첫 object 시작주소
freelist[active] │
부터 free obj v
[obj:use][obj:free][obj:use][obj:free]
Slub Allocator 구조
위에서 설명했던 array_cache 처럼 kmem_cache_cpu에서 먼저 할당 후 부족하면 kmem_cache_node 라는 전역 슬랩관리 구조체에서 가져오도록 구현되어 있다.
node는 CPU 소켓에 가까운 메모리를 의미하는데, 멀티 CPU 시스템(서버)에서는 의미가 있지만 일반 PC같은 싱글 cpu에서는 커널 전체에서 공유하는 노드가 된다.
kmem_cache에서는 할당을 위해 슬랩을 관리하기 때문에 slabs_full(꽉찬 슬랩)은 관리하지 않고 partial이 된 경우만 관리를 시작한다.
slabs_free(빈 슬랩)은 일반적으로 page allocator에 반환되고, min_partial 값보다 적어진 경우에만 성능을 위해 리스트로 관리한다. (CPU slab에서 내려올 때 deactivate_slab()에서 min_partial로 판단함)
kmem_cache_cpu, kmem_cache_node
[ kmem_cache (ex. kmalloc-64) ]
├─ min_partial : 최소 partial slab
├─ cpu_slab ─────> [ kmem_cache_cpu (per cpu) ]
│ freelist : 현재 CPU가 바로 사용할 다음 free object pointer
│ slab : 현재 CPU가 바로 할당에 사용할 active slab 1개
│ partial : CPU가 예비로 들고 있는 partial slab list (optional)
│
└─ node[] ───────> [ kmem_cache_node (per node) ]
nr_partial : kmem_cache_node 에서 관리하는 partial 수 (>= min_partial)
partial ───────> [ struct slab ] ────> [ struct slab ]
freelist : 첫 free object 주소
inuse : 사용 중인 object 수
objects : 전체 object 수
[ call slab_address(slab) ]
│ *freelist
[obj0:use][obj1:free][obj2:use][obj3:free]
└── next ptr ───────┘└─ next ptr ─> NULL
TODO
실제 할당과 해제 방식에서는 fast 방식과 slow 방식이 나뉘어있다.
대략적인 설명은 적어놨지만 상세한 분석을 해서 적어놓진 않았기 때문에 두 경로를 나눠서 정리할 필요가 있다.
총 4가지 경로
fast local, slow local, fast remote, slow remote ….
Slub Allocator 할당 방식
메모리 할당 함수 중 slub allocator 를 통하는 kmalloc() 을 호출하게되면, 사이즈에 맞는 kmem_cache 에서 메모리를 할당받게 된다.
kmem_cache_cpu
kmem_cache_cpu.slab에 자리가 있는 경우 freelist의 주소를 반환해주고 freelist는 다음 노드를 가리키도록 하면 돼서 쉽게 할당이 가능하다. (+ 할당 관련 메타데이터 업데이트)
kmem_cache_cpu.partial을 사용하는 경우엔 slab을 다 사용하면 partial 에서 slab으로 하나를 꺼내온다.
kmem_cache_node
kmem_cache_cpu.slab과 kmem_cache_cpu.partial 에 남은 자리가 없다면 사용된다. 여러 코어가 하나의 노드를 공유하는 구조이기 때문에 접근 시 lock을 걸고 접근하게 된다.
numactl -H 로 노드 구조를 확인할 수 있으며 그림에서는 core 4개가 하나의 numa node를 같이 사용한다.
node.partial 은 새로운 할당을 위해 어떤 core도 관리하고 있지않은 slab이기 때문에 할당하려고하는 core가 락을 잡고 선점해서 가져간 후 앞으로 해당 슬랩을 사용하게된다.
어차피 물리메모리의 빠른 할당만을 위해 kmem_cache_cpu로 관리하는 것이기 때문에 어떤 cpu가 슬랩을 가져가도 상관없다.
1. node->list_lock 잡음
2. slab A를 node.partial에서 제거 후 kmem_cache_cpu.slab 으로 넘김
3. slab A의 frozen bit를 1로 설정
4. slab A의 freelist를 kmem_cache_cpu 으로 넘김
5. node->list_lock 해제
CONFIG_SLUB_DEBUG 가 설정된 경우 kmem_cache_node.full 도 관리하게 된다. 아래는 오브젝트 할당 시 full 리스트로 슬랩이 관리되는 과정이다.
0x1000 슬랩에 마지막 오브젝트를 추가했을때 node.full 로 넘어가고 예비용 cpu.partial 에 있는 슬랩을 cpu.slab 에 올린다.
해제
object를 해제하는 시점에는, 해당 object를 할당했던 CPU와 다른 CPU에서 kfree()가 호출될 수 있다.
예를 들어 CPU0이 어떤 slab을 cpu slab으로 들고 allocation을 수행했더라도, 그 object를 사용하는 task가 CPU1에서 실행되다가 해제할 수 있다.
만약 할당한 CPU(core)만 free 가능하도록 만들면, 해제 요청을 원래 CPU로 넘겨야 하므로 오버헤드가 커진다.
그래서 SLUB에서는 다른 CPU도 해당 object가 속한 slab에 object를 반납할 수 있다.
local free (fast path)
해제하려는 object가 현재 CPU의 kmem_cache_cpu.slab (자기자신이 관리하는 slab)에 속해 있으면 fast path로 처리된다.
이 경우 struct slab의 freelist가 아니라 현재 CPU의 kmem_cache_cpu.freelist 앞에 object를 연결한다.
SLUB은 tid를 함께 사용해, 중간에 preemption이나 CPU migration으로 per-cpu 상태가 바뀌었는지 확인한다.
조건이 맞으면 별도의 중앙 lock 없이 c->freelist와 c->tid만 갱신하고 종료한다.
CPU0 kmem_cache_cpu
slab -> slab A
freelist -> obj3 -> obj7 -> NULL
CPU0에서 kfree(obj1 from slab A)
set_freepointer(obj1, c->freelist) // freelist가 가리키던 리스트에 해제된 obj1 연결
c->freelist = obj1
c->tid++
local free (slow path)
해제하려는 object가 현재 CPU의 c->slab에 속하더라도, 항상 lockless fastpath를 사용할 수 있는 것은 아니다.
PREEMPT_RT, debug 설정, lockless fastpath 비활성화, 또는 local lock과 충돌할 수 있는 특수 상황에서는 local lock을 잡고 현재 CPU의 kmem_cache_cpu를 갱신한다.
local_lock_cpu_slab()
obj1->next = c->freelist
c->freelist = obj1
c->tid++
local_unlock_cpu_slab()
remote free (slow path)
free할 obj를 관리하는 slab이 다른 core인 경우 다른 CPU의 kmem_cache_cpu를 직접 수정하는 것은 아니다.
대신 object가 속한 struct slab의 freelist와 카운터를 갱신한다.
즉 remote free에서의 push 대상은 kmem_cache_cpu.freelist가 아니라 slab->freelist이다.
CPU0 kmem_cache_cpu
slab -> slab A
CPU1에서 kfree(obj from slab A)
CPU1은 CPU0의 kmem_cache_cpu를 직접 수정하지 않고 slab A의 metadata만 갱신한다.
slab A
old.freelist = slab->freelist
freed obj
next -> old.freelist
slab->freelist = freed obj
slab->inuse--
슬랩의 상태가 변경됐으니 추가 처리가 필요하다.
Comments