SLAB Allocator

이동화·2025년 7월 28일

해당 기초 내용에서 나아가 어떻게 커널 내에서 메모리를 할당하는지를 알아보자

node

NUMA(Non‑Uniform Memory Access) 구조는 한 컴퓨터에 CPU가 많아짐에 따라 각 CPU core가 자신만의 Local Memory를 가지되, 다른 CPU core의 메모리에도 접근할 수 있도록 설계한 구조이다. NUMA가 좋은 이유는 모든 core가 단일 메모리에 의존하는 UMA 구조에서는 core 수가 늘어날 수록 병목 현상이 심해진다는 단점이 있으며, local memory의 존재에 의해 socket을 추가해도 로컬 액세스 성능을 일정 부분 유지하되 전체 시스템 메모리 용량을 쉽게 확장할 수 있다는 점이다.

node는 이러한 NUMA 환경의 linux kernel에서 사용하는 단위로, Locality를 기준으로 물리 메모리와 CPU를 묶어 놓은 단위이다. 자기 자신의 CPU local memory(=node 0)에 접근하는 속도는 빠르지만 다른 메모리에 접근하면 속도가 느려지기에, kernel은 메모리 할당 시 가능하면 해당 CPU가 속한 node 위주로 페이지를 할당하여 성능을 최적화한다.

각 NUMA node를 용도나 접근성에 따라 여러 zone으로 나누고, zone 별로 page와 block을 관리하는 system이 buddy system이다.

buddy system

buddy system는 메모리 단편화(external fragmentation)를 줄이기 위해, 연속된 페이지 할당을 효율적으로 처리하는 구조이다. 2의 거듭제곱 단위인 Order 단위로 할당 요청을 받아 관리를 하며, 이를 통해 적당한 크기의 페이지 묶음을 간편하게 나누고 합치는 것이 가능하다.

각 메모리 영역 (zone)은 내부에 free_area[MAX_ORDER]라는 배열을 가지고 있는데, MAX_ORDER는 아키텍처별로 정해진 최대 order 수를 의미한다. Zone의 배열에는 각각 페이지 묶음 중 얼마나 자유 공간이 남아있는지를 나타내는 nr_free와, block 단위(2^order 개의 연속된 페이지 묶음)로 종류를 구분하여 연결 리스트로 관리하는 free_list[MIGRATE_TYPES] 가 존재한다. 여기서 migrate type는 페이지를 옮길 수 있는지, 회수가 가능한지, I/O buffer나 page table처럼 움직일 수 없는지 등 type을 나타낸다. 해당 type에 따라 관리되는 영역을 나눠두고, 페이지 할당 시 요청한 migrate type에 따라 해당하는 영역에서 페이지를 할당해준다.

메모리를 할당할 때는 요청 크기를 페이지 크기 (4KB)로 나눈 후 bit 수를 계산하여 적절한 order 값을 찾아낸다. 요청한 order에 빈 블록이 남아 있지 않으면 상위 order block 하나를 선택하여 반으로 쪼개고, 그 중 절반을 사용자에게 할당하고 나머지는 하위 order block의 free list에 넣는다. 이를 통해 최소한의 분할만을 통해서 유저에게 효율적으로 메모리를 할당할 수 있고, 가능한 한 큰 연속 블록을 보존할 수 있다.

메모리를 해제할 땐 되돌리는 블록의 order에서 짝(buddy)을 이루는 페이지가 자유 상태인지 확인한다. 짝을 이루는 페이지 플록은 항상 고정되어 있어 동일한 위치의 짝 페이지를 빠르게 찾아 병합 여부를 확인할 수 있다. 둘 다 free 상태라면 둘을 합쳐 상위 order block으로 병합하고, 이를 반복하여 더 이상 병합할 수 없을 때 해당 order의 free list에 추가한다.

kernel 부팅 시에는 start_kernel에서 메모리 초기화를 거쳐 모든 부팅용 메모리를 할꺼번에 buddy system에 넘긴다. 이후 __free_page_boot_core이랑 __free_pages 등 내부 함수를 거쳐 각 페이지를 적절한 order에 등록하여 기반을 만들고 해당 기반 위에서 동적 할당과 해제가 반복되어 커널 메모리 관리가 이루어진다.

buddy allocator는 buddy system을 실제 커널에서 코드로 구현한 모듈 또는 함수 집합을 의미한다.

SLAB 할당자 구조

slab 할당자는 ptmalloc처럼 자주 쓰는 메모리 패턴을 미리 정의하고 미리 할당하여 빠르게 메모리를 할당한다. 또한, 특정 패턴으로 메모리 해제 요청을 하면 바로 반환하는 것이 아닌, 비슷한 요청이 또 올 수 있음을 염두하고 대기 상태에 놓이게 된다.

buddy system에서 order 단위로 페이지를 관리하기에, order-N 페이지를 사용하여 slab page를 구성하고 slab page에서 할당 가능한 slab object를 배치하게 된다. 이런 slab page를 여러 개 모아 하나의 slab cache를 구성하게 된다. 이때, 하나의 slab cache 내의 모든 object 크기는 같다.

slab 할당자는 자주 쓰는 메모리 패턴을 미리 정의한다고 했는데, 프로세스를 생성할 때 task_struct 라는 pcb 구조체를 매번 할당해야 하기 때문에 slab 할당자의 의도와 부합한다. 미리 task_struct 를 slab cache 내부에 block 단위로 할당을 해두고 프로세스가 생성될 때 마다 cache에서 바로 프로세스 메모리로 넘겨주면 CPU에 부하가 걸리지 않고 빠르게 메모리 할당이 가능하다. task_struct 뿐만 아니라, inode, mm_struct 등 파일 메타 데이터나 가상 메모리 공간 관련 구조체들도 slab cache로 구현이 되어 있다. 각 slab cache 내부의 블록 크기는 할당할 구조체의 크기일 것이고, 당연히 같은 cache에서의 블록 크기는 같고 서로 다른 cache의 블록 크기는 다르다.

slab cache

struct kmem_cache {
	struct kmem_cache_cpu __percpu *cpu_slab;
	/* Used for retriving partial slabs etc */
	unsigned long flags;
	unsigned long min_partial;
	int size;		/* The size of an object including meta data */
	int object_size;	/* The size of an object without meta data */
	int offset;		/* Free pointer offset. */
#ifdef CONFIG_SLUB_CPU_PARTIAL
	int cpu_partial;	/* Number of per cpu partial objects to keep around */
#endif
	struct kmem_cache_order_objects oo;

	/* Allocation and freeing of slabs */
	struct kmem_cache_order_objects max;
	struct kmem_cache_order_objects min;
	gfp_t allocflags;	/* gfp flags to use on each alloc */
	int refcount;		/* Refcount for slab cache destroy */
	void (*ctor)(void *);
	int inuse;		/* Offset to metadata */
	int align;		/* Alignment */
	int reserved;		/* Reserved bytes at the end of slabs */
	int red_left_pad;	/* Left redzone padding size */
	const char *name;	/* Name (only for display!) */
	struct list_head list;	/* List of slab caches */
#ifdef CONFIG_SYSFS
	struct kobject kobj;	/* For sysfs */
	struct work_struct kobj_remove_work;
#endif
#ifdef CONFIG_MEMCG
	struct memcg_cache_params memcg_params;
	int max_attr_size; /* for propagation, maximum size of a stored attr */
#ifdef CONFIG_SYSFS
	struct kset *memcg_kset;
#endif
#endif

#ifdef CONFIG_SLAB_FREELIST_HARDENED
	unsigned long random;
#endif

#ifdef CONFIG_NUMA
	/*
	 * Defragmentation by allocating from a remote node.
	 */
	int remote_node_defrag_ratio;
#endif

#ifdef CONFIG_SLAB_FREELIST_RANDOM
	unsigned int *random_seq;
#endif

#ifdef CONFIG_KASAN
	struct kasan_cache kasan_info;
#endif

	struct kmem_cache_node *node[MAX_NUMNODES];
};

위 코드는 slab cache가 코드로 구현된 구조체 kmem_cache이다. 내부에 있는 두 개의 구조체로 node별로, cpu 별로 메모리를 관리한다.

struct kmem_cache_cpu __percpu *cpu_slab;
해당 라인은 빠른 할당을 위해 CPU 별로 slab cache를 관리하는 구조체로, CPU 개수만큼 가지고 있다.
struct kmem_cache_node *node[MAX_NUMNODES];
각 node별로 slab page를 관리하기 위한 구조체이다.

kmem_cache_cpu 구조체는 freelist, page, partial 필드가 존재한다.

partial은 slab page들이 list로 연결이 되어 있으며, 각 page에는 free/inuse 상태의 object가 들어있다. partial 필드의 slab page들은 바로 이용할 수 없고, page 필드로 이동되어야만 사용이 가능하다. (대기 중이라는 상태)

page 필드는 하나의 slab page만을 관리하고, 페이지에 들어있는 여거 object 중 free 상태의 object들을 할당한다.

freelist 필드는 구조체의 page 필드의 free 상태인 object들을 연결한 연결 리스트이다. freelist는 kmem_cache_cpu->page 구조체 내부의 freelist와 kmem_cache_cpu 구조체의 freelist 두 가지가 존재한다.
후자는 현재의 CPU가 관리하는 freelist로, object의 할당 및 해제가 자유롭다. 반면 전자는 다른 CPU가 현재 CPU가 관리하는 object를 해제한 경우 object를 반환받는 리스트로, 다른 CPU에서 해당 리스트의 free object에는 해제만 할 수 있고 할당이 불가능하다. page 필드의 inuse 값은 page->freelist에서 사용 중인 object 수를 의미하고, percpu의 freelist에서 사용 중인 object 수와는 관계가 없다.

Allocate Scenario

kmalloc() 함수 등을 통해 커널에서 동적 메모리 요청을 하면 free 상태의 object가 반환된다. object를 할당하는 방법은 5가지가 있다.

Fastpath

percpu의 freelist에 들어있는 free object를 바로 할당해주는 방식으로, 제일 빠르다.

반환되는 경우 freelist에 다시 넣어주면 된다.

Slowpath 1

percpu의 freelist에 object가 없는 경우, percpu의 page 필드 내의 freelist에 들어있는 object를 percpu의 freelist로 올리고, fastpath를 시도하는 할당 방법이다. 이 경우 page 내부의 object들이 반환되기 전까지 해당 page는 frozen 상태가 되어, kmem_cache의 관리를 벗어난다.

Slowpath 2

page의 freelist에도 할당할 object가 없는 경우, percpu의 partial 필드를 이용한다. partial에서 대기 중인 slab page를 page로 올리고, page 내부의 object들을 다시 freelist로 올려서 다시 fastpath를 수행한다.

Slowpath 3

partial 필드에도 할당할 수 있는 object가 없다면, per node를 이용하게 된다. pernode의 partial 필드에 있는 첫 slab page를 percpu의 page 필드로 올리고, object들을 freelist로 이동시킨다. 그리고 pernode의 partial에 있는 다른 slab page 중 일부를 percpu의 partial 필드로 옮긴다. 만약 pernode의 partial 필드가 비어있는 경우 다른 node의 partial 필드를 뒤진다.