[Linux Kernel 5] Slab & Slub Allocator #1

1. Basis

 

슬랩은 자주 사용하는 메모리 타입을 부팅 시 미리 할당하여 동적 메모리 할당/해제의 비용과 메모리 fragmentation을 최소화하는 일종의 캐시다.

`# cat /proc/slabinfo` 명령의 결과로 아래와 같이 슬랩 할당자의 정보를 볼 수 있다.

cat /proc/slabinfo 결과

친숙한(?) task_struct 구조체나, 이 전 포스트들에서 공부했던 request_queue, blkdev_requests, vm_area_struct, mm_struct, anon_vma(_chain) 등이 보인다.

즉, 슬랩은 이렇게 자주 사용하는 데이터 컨테이너를 미리 할당해두고 해당 데이터 할당 요청 시 할당 오버헤드를 최소화한다.

 

Slab Allocator의 최소 할당 단위는 slab object이다.

그리고 slab object가 모여 하나 이상의 연속된 페이지를 하나의 slab으로 구성한다.

과거 Slab Allocator의 경우 slab cache를 관리하기 위한 구조체 kmem_cache_t에 full list, partial list, empty list 세 개의 리스트를 두고, 처음 만들어진 슬랩은 full list에, object를 하나라도 사용중인 슬랩은 partial list에, object를 전부 사용한 슬랩은 empty list에 저장했다.

이런 Slab Allocator에서 각 슬랩의 앞쪽에 위치한 메타 데이터 조각들이 object의 정렬을 어렵게 하고, 메모리 부족으로 캐시 클리닝 시 처리가 복잡해지는 등의 문제가 있었다.

 

이런 문제점들을 해결한 Slub(The unqueued slab) Allocator가 등장했다.

슬럽 할당자는 partial 리스트 하나로 슬랩을 관리하며, freelist 관리를 위해 별도의 공간을 사용하지 않는다.

복잡성 문제 외에도 슬럽은 슬랩에 비해 시스템에 슬랩 캐시가 줄고, locality가 늘고, fragmentation이 줄었다.

 

슬랩과 슬럽에 대한 더 자세한 내용은 다음 LWN article을 참고한다.

(해당 포스트는 이 후 Slub에 대해 설명할 것이므로, Slab에 대해 더 알고 싶다면 링크를 참고한다.)

 

같은 사이즈의 슬랩 object들이 모여 슬랩 페이지를 구성하며, 1개 이상의 같은 사이즈의 슬랩 페이지가 모여 슬랩 캐시를 구성한다. 또한, LWN 게시글에서 볼 수 있듯이 per-cpu와 per-node 관리를 지원한다.

 

이 전 포스트의 struct page의 멤버를 보면 freelist 멤버가 있는 것을 볼 수 있다.

이 freelist가 슬랩 페이지의 첫번째 free object를 가리킨다. object들은 리스트로 구성된다.

 

 

 

2. Slab Data Structure

 

slab 캐시를 관리하는 struct kmem_cache 의 정의는 다음과 같다.

/*
 * Slab cache management.
 */
struct kmem_cache {
	struct kmem_cache_cpu __percpu *cpu_slab;
	/* Used for retrieving partial slabs, etc. */
	slab_flags_t flags;
	unsigned long min_partial;
	unsigned int size;	/* The size of an object including metadata */
	unsigned int object_size;/* The size of an object without metadata */
	unsigned int offset;	/* Free pointer offset */
#ifdef CONFIG_SLUB_CPU_PARTIAL
	/* Number of per cpu partial objects to keep around */
	unsigned int cpu_partial;
#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 *);
	unsigned int inuse;		/* Offset to metadata */
	unsigned int align;		/* Alignment */
	unsigned 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;
	/* For propagation, maximum size of a stored attr */
	unsigned int max_attr_size;
#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.
	 */
	unsigned 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
 
	unsigned int useroffset;	/* Usercopy region offset */
	unsigned int usersize;		/* Usercopy region size */
 
	struct kmem_cache_node *node[MAX_NUMNODES];
};

min_partial은 캐시가 유지할 partial 슬랩 페이지 최소 수이다.

size는 metadata를 포함한 object의 사이즈이다.

object_size는 metadata를 제외한 object의 사이즈이다.

offset은 object내의 Free Pointer의 위치이다.

oo는 슬랩 페이지 생성 시 적용할 order이다.

max/min은 슬랩 페이지 생성 시 최대/최소 order이다.

allocflags는 object alloc 시 사용할 GFP flag다.

refcount는 슬랩 캐시 삭제에 사용하기 위한 reference counter이다.

ctor는 object의 생성자 함수 포인터이다.

inuse는 metadata의 위치(offset)이다. /* 확인 필요 */

align은 정렬할 바이트 수이다.

red_left_pad는 left redzone 패딩 크기다.

name은 출력용 이름이다.

list는 슬랩 캐시를 리스트화하기 위한 멤버이다.

useroffset은 usercopy 영역의 offset이다.

usersize는 usercopy 영역의 크기이다.

node[]는 노드 별 partial 리스트를 관리하기 위한 구조체 배열 포인터이다.

 

page 구조체에서 slab/slub 용으로 사용하는 멤버만 다시 보면 다음과 같다.

struct page {
		struct {	/* slab, slob and slub */
			union {
				struct list_head slab_list;
				struct {	/* Partial pages */
					struct page *next;
#ifdef CONFIG_64BIT
					int pages;	/* Nr of pages left */
					int pobjects;	/* Approximate count */
#else
					short int pages;
					short int pobjects;
#endif
				};
			};
			struct kmem_cache *slab_cache; /* not slob */
			/* Double-word boundary */
			void *freelist;		/* first free object */
			union {
				void *s_mem;	/* slab: first object */
				unsigned long counters;		/* SLUB */
				struct {			/* SLUB */
					unsigned inuse:16;
					unsigned objects:15;
					unsigned frozen:1;
				};
			};
		};
} _struct_page_alignment;

slab_list는 슬랩 페이지로 사용될 때의 리스트 노드이다.

next는 다음 partial 페이지를 가리킨다.

pages는 남은 partial 페이지의 수다.

pboejcts는 대략적으로 남은 partial object 수이다.

slab_cache는 슬랩 캐시를 가리킨다.

freelist는 첫 번째 free object를 가리킨다.

inuse는 사용중인 object의 수이다.

objects는 object의 총 수이다.

frozen은 frozen 여부를 나타낸다.

 

slab object의 size는 여러 metadata의 포함 여부 등에 따라 매우 유동적인데, 주 항목은 다음과 같다.

• Free Pointer : 다음 free object를 가리키는 포인터다.
• Red-Zone : 데이터 주소 침범을 방지/검출 한다.
• Poison : 데이터 주소 등의 poison 여부를 나타낸다.
• Owner Track : object의 생성/소멸 시 호출한 함수 정보이다.
• Align Padding : 정렬 용 패딩이다.

 

 

 

3. 슬랩 캐시 생성

 

우선 슬랩 캐시를 생성하기 전에 커널은 kmem_cache_init()을 호출하여 (무려 init/main 함수에서 호출한다) 슬랩 캐시를 초기화 한다.

해당 함수에선 부트 타임에서 사용할 슬랩 캐시를 할당 및 초기화하거나, kmem_cache / kmem_cache_node / kmalloc-<size> / dma-kmalloc-<size> 슬랩 캐시를 생성 및 슬랩 캐시 관리를 위한 초기화 등을 진행한다.

 

이 후 슬랩 캐시를 생성하기 위한 함수 kmem_cache_create은 다음과 같다.

/**
 * kmem_cache_create - Create a cache.
 * @name: A string which is used in /proc/slabinfo to identify this cache.
 * @size: The size of objects to be created in this cache.
 * @align: The required alignment for the objects.
 * @flags: SLAB flags
 * @ctor: A constructor for the objects.
 *
 * Cannot be called within a interrupt, but can be interrupted.
 * The @ctor is run when new pages are allocated by the cache.
 *
 * The flags are
 *
 * %SLAB_POISON - Poison the slab with a known test pattern (a5a5a5a5)
 * to catch references to uninitialised memory.
 *
 * %SLAB_RED_ZONE - Insert `Red` zones around the allocated memory to check
 * for buffer overruns.
 *
 * %SLAB_HWCACHE_ALIGN - Align the objects in this cache to a hardware
 * cacheline.  This can be beneficial if you're counting cycles as closely
 * as davem.
 *
 * Return: a pointer to the cache on success, NULL on failure.
 */
struct kmem_cache *
kmem_cache_create(const char *name, unsigned int size, unsigned int align,
		slab_flags_t flags, void (*ctor)(void *))
{
	return kmem_cache_create_usercopy(name, size, align, flags, 0, 0,
					  ctor);
}
 
/**
 * kmem_cache_create_usercopy - Create a cache with a region suitable
 * for copying to userspace
 * @name: A string which is used in /proc/slabinfo to identify this cache.
 * @size: The size of objects to be created in this cache.
 * @align: The required alignment for the objects.
 * @flags: SLAB flags
 * @useroffset: Usercopy region offset
 * @usersize: Usercopy region size
 * @ctor: A constructor for the objects.
 *
 * Cannot be called within a interrupt, but can be interrupted.
 * The @ctor is run when new pages are allocated by the cache.
 *
 * The flags are
 *
 * %SLAB_POISON - Poison the slab with a known test pattern (a5a5a5a5)
 * to catch references to uninitialised memory.
 *
 * %SLAB_RED_ZONE - Insert `Red` zones around the allocated memory to check
 * for buffer overruns.
 *
 * %SLAB_HWCACHE_ALIGN - Align the objects in this cache to a hardware
 * cacheline.  This can be beneficial if you're counting cycles as closely
 * as davem.
 *
 * Return: a pointer to the cache on success, NULL on failure.
 */
struct kmem_cache *
kmem_cache_create_usercopy(const char *name,
		  unsigned int size, unsigned int align,
		  slab_flags_t flags,
		  unsigned int useroffset, unsigned int usersize,
		  void (*ctor)(void *))
{
	struct kmem_cache *s = NULL;
	const char *cache_name;
	int err;
 
	get_online_cpus();
	get_online_mems();
	memcg_get_cache_ids();
 
	mutex_lock(&slab_mutex);
 
	err = kmem_cache_sanity_check(name, size);
	if (err) {
		goto out_unlock;
	}
 
	/* Refuse requests with allocator specific flags */
	if (flags & ~SLAB_FLAGS_PERMITTED) {
		err = -EINVAL;
		goto out_unlock;
	}
 
	/*
	 * Some allocators will constraint the set of valid flags to a subset
	 * of all flags. We expect them to define CACHE_CREATE_MASK in this
	 * case, and we'll just provide them with a sanitized version of the
	 * passed flags.
	 */
	flags &= CACHE_CREATE_MASK;
 
	/* Fail closed on bad usersize of useroffset values. */
	if (WARN_ON(!usersize && useroffset) ||
	    WARN_ON(size < usersize || size - usersize < useroffset))
		usersize = useroffset = 0;
 
	if (!usersize)
		s = __kmem_cache_alias(name, size, align, flags, ctor);
	if (s)
		goto out_unlock;
 
	cache_name = kstrdup_const(name, GFP_KERNEL);
	if (!cache_name) {
		err = -ENOMEM;
		goto out_unlock;
	}
 
	s = create_cache(cache_name, size,
			 calculate_alignment(flags, align, size),
			 flags, useroffset, usersize, ctor, NULL, NULL);
	if (IS_ERR(s)) {
		err = PTR_ERR(s);
		kfree_const(cache_name);
	}
 
out_unlock:
	mutex_unlock(&slab_mutex);
 
	memcg_put_cache_ids();
	put_online_mems();
	put_online_cpus();
 
	if (err) {
		if (flags & SLAB_PANIC)
			panic("kmem_cache_create: Failed to create slab '%s'. Error %d\n",
				name, err);
		else {
			pr_warn("kmem_cache_create(%s) failed with error %d\n",
				name, err);
			dump_stack();
		}
		return NULL;
	}
	return s;
}

kmem_cache_create_usercopy의 동작은 다음과 같다.

1) 설정 및 체킹 작업 이후 플래그 마스킹한다.

2) __kmem_cache_alias 함수 결과 기존 슬랩 캐시 중 병합 가능한 슬랩 캐시를 찾은 경우 alias 캐시로 등록하고 캐시 생성 과정을 스킵한다.

3) cache_name에 출력용 이름을 설정한다.

4) create_cache 함수가 새 캐시를 생성한다.

5) 리소스 반환 이 후 할당 받은 캐시를 반환한다.

결국 핵심은 __kmem_cache_alias와 create_cache 두 함수다.

 

__kmem_cache_alias 함수의 정의는 다음과 같다.

struct kmem_cache *
__kmem_cache_alias(const char *name, unsigned int size, unsigned int align,
		   slab_flags_t flags, void (*ctor)(void *))
{
	struct kmem_cache *s, *c;
 
	s = find_mergeable(size, align, flags, name, ctor);
	if (s) {
		s->refcount++;
 
		/*
		 * Adjust the object sizes so that we clear
		 * the complete object on kzalloc.
		 */
		s->object_size = max(s->object_size, size);
		s->inuse = max(s->inuse, ALIGN(size, sizeof(void *)));
 
		for_each_memcg_cache(c, s) {
			c->object_size = s->object_size;
			c->inuse = max(c->inuse, ALIGN(size, sizeof(void *)));
		}
 
		if (sysfs_slab_alias(s, name)) {
			s->refcount--;
			s = NULL;
		}
	}
 
	return s;
}

1) find_mergeable 함수는 병합 가능한 캐시를 찾는다.

2) 병합 가능한 캐시를 찾은 경우 해당 캐시의 reference counter를 증가시킨다.

3) 병합 될 캐시보다 병합 요청한 캐시의 크기(인자로 전달받은 값)가 더 큰 경우 사이즈들을 업데이트한다.

4) 병합될 캐시의 모든 memcg 캐시를 순회하며 memcg 캐시의 사이즈를 갱신한다.

5) sysfs를 사용하는 경우 생성된 캐시에 대한 sysfs 링크를 만든다.

여기서 alias 슬랩 캐시란 새로 생성하려는 캐시가 기존에 생성한 캐시와 object size가 같고 기타 조건들이 유사한 경우 (find_mergeable 함수의 조건을 만족) 기존의 캐시를 공유해서 사용하는 캐시를 말한다.

 

일반 캐시를 생성하는 함수 create_cache의 정의는 다음과 같다.

static struct kmem_cache *create_cache(const char *name,
		unsigned int object_size, unsigned int align,
		slab_flags_t flags, unsigned int useroffset,
		unsigned int usersize, void (*ctor)(void *),
		struct mem_cgroup *memcg, struct kmem_cache *root_cache)
{
	struct kmem_cache *s;
	int err;
 
	if (WARN_ON(useroffset + usersize > object_size))
		useroffset = usersize = 0;
 
	err = -ENOMEM;
	s = kmem_cache_zalloc(kmem_cache, GFP_KERNEL);
	if (!s)
		goto out;
 
	s->name = name;
	s->size = s->object_size = object_size;
	s->align = align;
	s->ctor = ctor;
	s->useroffset = useroffset;
	s->usersize = usersize;
 
	err = init_memcg_params(s, root_cache);
	if (err)
		goto out_free_cache;
 
	err = __kmem_cache_create(s, flags);
	if (err)
		goto out_free_cache;
 
	s->refcount = 1;
	list_add(&s->list, &slab_caches);
	memcg_link_cache(s, memcg);
out:
	if (err)
		return ERR_PTR(err);
	return s;
 
out_free_cache:
	destroy_memcg_params(s);
	kmem_cache_free(kmem_cache, s);
	goto out;
}

1) kmem_cache_zalloc으로 kmem_cache를 할당한 후 전달받은 인자로 초기화한다.

2) init_memcg_params로 memcg용 파라미터들을 초기화한다.

3) __kmem_cache_create로 캐시를 생성한다.

4) 캐시의 reference counter를 1로 설정하고 slab_caches 리스트에 추가한다.

5) memcg_link_cache로 캐시가 root 캐시인 경우 slab_root_caches 리스트에 추가하고, 아닌 경우 memcg에 추가한다.

 

 

 

4. Slub Object 할당

 

kmem_cache_zalloc은 kmem_cache_alloc -> slab_alloc -> slab_alloc_node 순으로 호출하여 slub object를 할당한다.

/*
 * Inlined fastpath so that allocation functions (kmalloc, kmem_cache_alloc)
 * have the fastpath folded into their functions. So no function call
 * overhead for requests that can be satisfied on the fastpath.
 *
 * The fastpath works by first checking if the lockless freelist can be used.
 * If not then __slab_alloc is called for slow processing.
 *
 * Otherwise we can simply pick the next object from the lockless free list.
 */
static __always_inline void *slab_alloc_node(struct kmem_cache *s,
		gfp_t gfpflags, int node, unsigned long addr)
{
	void *object;
	struct kmem_cache_cpu *c;
	struct page *page;
	unsigned long tid;
 
	s = slab_pre_alloc_hook(s, gfpflags);
	if (!s)
		return NULL;
redo:
	/*
	 * Must read kmem_cache cpu data via this cpu ptr. Preemption is
	 * enabled. We may switch back and forth between cpus while
	 * reading from one cpu area. That does not matter as long
	 * as we end up on the original cpu again when doing the cmpxchg.
	 *
	 * We should guarantee that tid and kmem_cache are retrieved on
	 * the same cpu. It could be different if CONFIG_PREEMPTION so we need
	 * to check if it is matched or not.
	 */
	do {
		tid = this_cpu_read(s->cpu_slab->tid);
		c = raw_cpu_ptr(s->cpu_slab);
	} while (IS_ENABLED(CONFIG_PREEMPTION) &&
		 unlikely(tid != READ_ONCE(c->tid)));
 
	/*
	 * Irqless object alloc/free algorithm used here depends on sequence
	 * of fetching cpu_slab's data. tid should be fetched before anything
	 * on c to guarantee that object and page associated with previous tid
	 * won't be used with current tid. If we fetch tid first, object and
	 * page could be one associated with next tid and our alloc/free
	 * request will be failed. In this case, we will retry. So, no problem.
	 */
	barrier();
 
	/*
	 * The transaction ids are globally unique per cpu and per operation on
	 * a per cpu queue. Thus they can be guarantee that the cmpxchg_double
	 * occurs on the right processor and that there was no operation on the
	 * linked list in between.
	 */
 
	object = c->freelist;
	page = c->page;
	if (unlikely(!object || !node_match(page, node))) {
		object = __slab_alloc(s, gfpflags, node, addr, c);
		stat(s, ALLOC_SLOWPATH);
	} else {
		void *next_object = get_freepointer_safe(s, object);
 
		/*
		 * The cmpxchg will only match if there was no additional
		 * operation and if we are on the right processor.
		 *
		 * The cmpxchg does the following atomically (without lock
		 * semantics!)
		 * 1. Relocate first pointer to the current per cpu area.
		 * 2. Verify that tid and freelist have not been changed
		 * 3. If they were not changed replace tid and freelist
		 *
		 * Since this is without lock semantics the protection is only
		 * against code executing on this cpu *not* from access by
		 * other cpus.
		 */
		if (unlikely(!this_cpu_cmpxchg_double(
				s->cpu_slab->freelist, s->cpu_slab->tid,
				object, tid,
				next_object, next_tid(tid)))) {
 
			note_cmpxchg_failure("slab_alloc", s, tid);
			goto redo;
		}
		prefetch_freepointer(s, next_object);
		stat(s, ALLOC_FASTPATH);
	}
 
	maybe_wipe_obj_freeptr(s, object);
 
	if (unlikely(slab_want_init_on_alloc(gfpflags, s)) && object)
		memset(object, 0, s->object_size);
 
	slab_post_alloc_hook(s, gfpflags, 1, &object);
 
	return object;
}

기본적인 fast-path slab object 할당 함수다.

1) slab_pre_alloc_hook을 호출하여 object 할당을 위한 준비를 한다. 해당 함수에서 memcg 캐시가 enable 상태인 경우 memcg_kmem_get_cache를 호출해 memcg 캐시를 반환한다.

2) this_cpu_read / raw_cpu_ptr로 tid와 per-cpu 캐시를 읽는다. (해당 과정에서 preemption 당할 수 있기 때문에, 같은 cpu에서 tid와 per-cpu 캐시 읽기를 보장하기 위해 atomic 하게 값을 비교한다.)

3) Irqless object 할당/해제 알고리즘은 cpu_slab 데이터를 fetch하는 순서에 의존적이다. (tid가 가장 먼저 fetch 되어야 object와 page를 정상적으로 읽을 수 있다.) 따라서 명령어 최적화를 피하기 위해 barrier를 사용한다.

4) per-cpu cache의 freelist (c->freelist)에서 첫 번째 free object를 가져오고, page (c->page)를 가져온다.

5) per-cpu freelist에 object가 없거나 per-cpu cache slab page의 노드와 지정된 노드가 매치되지 않는 경우 __slab_alloc 함수를 통해 slow-path object 할당을 진행한다.

6) object를 가져온 경우 get_freepointer_safe 함수로 FP에서 다음 object의 주소를 저장한다.

7) this_cpu_cmpxchg_double로 fast-path 할당 성공 여부를 확인 및 후처리를 진행한다. cpu나 tid가 변경된 경우 redo 레이블로 되돌아가서 재시도한다.

this_cpu_cmpxchg_double(pcp1, pcp2, oval1, oval2, nval1, nval2)은 (pcp1,oval1)와 (pcp2,oval2)를 비교하여 둘 다 동일한 경우 nval1과 nval2의 값을 pcp1과 pcp2에 atomic하게 대입한다.

즉, freelist와 tid가 바뀌지 않았다는 것을 확인한 경우 freelist와 tid를 다음 엔트리로 교체하는 것을 atomic하게 진행한다.

8) prefetch_freepointer 함수로 다음 object에 대한 캐시라인을 prefetch한다.

9) __GFP_ZERO 플래그가 설정되어 있으면 object를 0으로 초기화한다.

10) 할당 완료를 알리고 반환한다.

 

fast-path 할당에 실패해 slow-path로 넘어가는 __slab_alloc은 내부에서 ___slab_alloc을 호출하며, 해당 함수는 다음과 같다.

/*
 * Slow path. The lockless freelist is empty or we need to perform
 * debugging duties.
 *
 * Processing is still very fast if new objects have been freed to the
 * regular freelist. In that case we simply take over the regular freelist
 * as the lockless freelist and zap the regular freelist.
 *
 * If that is not working then we fall back to the partial lists. We take the
 * first element of the freelist as the object to allocate now and move the
 * rest of the freelist to the lockless freelist.
 *
 * And if we were unable to get a new slab from the partial slab lists then
 * we need to allocate a new slab. This is the slowest path since it involves
 * a call to the page allocator and the setup of a new slab.
 *
 * Version of __slab_alloc to use when we know that interrupts are
 * already disabled (which is the case for bulk allocation).
 */
static void *___slab_alloc(struct kmem_cache *s, gfp_t gfpflags, int node,
			  unsigned long addr, struct kmem_cache_cpu *c)
{
	void *freelist;
	struct page *page;
 
	page = c->page;
	if (!page) {
		/*
		 * if the node is not online or has no normal memory, just
		 * ignore the node constraint
		 */
		if (unlikely(node != NUMA_NO_NODE &&
			     !node_state(node, N_NORMAL_MEMORY)))
			node = NUMA_NO_NODE;
		goto new_slab;
	}
redo:
 
	if (unlikely(!node_match(page, node))) {
		/*
		 * same as above but node_match() being false already
		 * implies node != NUMA_NO_NODE
		 */
		if (!node_state(node, N_NORMAL_MEMORY)) {
			node = NUMA_NO_NODE;
			goto redo;
		} else {
			stat(s, ALLOC_NODE_MISMATCH);
			deactivate_slab(s, page, c->freelist, c);
			goto new_slab;
		}
	}
 
	/*
	 * By rights, we should be searching for a slab page that was
	 * PFMEMALLOC but right now, we are losing the pfmemalloc
	 * information when the page leaves the per-cpu allocator
	 */
	if (unlikely(!pfmemalloc_match(page, gfpflags))) {
		deactivate_slab(s, page, c->freelist, c);
		goto new_slab;
	}
 
	/* must check again c->freelist in case of cpu migration or IRQ */
	freelist = c->freelist;
	if (freelist)
		goto load_freelist;
 
	freelist = get_freelist(s, page);
 
	if (!freelist) {
		c->page = NULL;
		stat(s, DEACTIVATE_BYPASS);
		goto new_slab;
	}
 
	stat(s, ALLOC_REFILL);
 
load_freelist:
	/*
	 * freelist is pointing to the list of objects to be used.
	 * page is pointing to the page from which the objects are obtained.
	 * That page must be frozen for per cpu allocations to work.
	 */
	VM_BUG_ON(!c->page->frozen);
	c->freelist = get_freepointer(s, freelist);
	c->tid = next_tid(c->tid);
	return freelist;
 
new_slab:
 
	if (slub_percpu_partial(c)) {
		page = c->page = slub_percpu_partial(c);
		slub_set_percpu_partial(c, page);
		stat(s, CPU_PARTIAL_ALLOC);
		goto redo;
	}
 
	freelist = new_slab_objects(s, gfpflags, node, &c);
 
	if (unlikely(!freelist)) {
		slab_out_of_memory(s, gfpflags, node);
		return NULL;
	}
 
	page = c->page;
	if (likely(!kmem_cache_debug(s) && pfmemalloc_match(page, gfpflags)))
		goto load_freelist;
 
	/* Only entered in the debug case */
	if (kmem_cache_debug(s) &&
			!alloc_debug_processing(s, page, freelist, addr))
		goto new_slab;	/* Slab failed checks. Next slab needed */
 
	deactivate_slab(s, page, get_freepointer(s, freelist), c);
	return freelist;
}

1) per-cpu slab page가 지정되지 않은 경우 per-cpu의 partial 리스트에서 slab page를 가져오기 위해 new_slab 레이블로 이동한다.

2) per-cpu slab page의 노드와 요청한 노드가 다른 경우 node에 N_NORMAL_MEMORY가 세트되어 있다면 node를 NUMA_NO_NODE로 설정하여 재시도하고, 아니라면 MISMATCH 카운터를 증가시키고 s->page에 연결된 slab page를 deactivate 시키고 per-cpu partial 리스트에서 slab page를 가져오기 위하여 new_slab 레이블로 이동한다.

3) 비상 상황이 아닌데 비상용 slub page가 선택된 경우 s->page에 연결된 slab page를 deactivate 시키고 per-cpu partial 리스트에서 slab page를 가져오기 위하여 new_slab 레이블로 이동한다.

4) cpu migration이나 IRQ같은 인터럽트 직전에 반납한 object가 freelist에 남아있는 경우 해당 object를 할당받기 위하여 load_freelist 레이블로 이동한다.

5) get_freelist로 per-cpu의 freelist에 per-cpu slab page의 freelist를 대입한다.

6) 해당 freelist에 free object가 없는 경우 slab page가 전부 사용중인 경우이므로 per-cpu page에 null을 대입하고 new_slab 레이블로 이동한다.

7) per-cpu freelist에 free object가 다시 생긴 경우 ALLOC_REFILL 카운터를 증가시킨다.

8) load_freelist 레이블에서는 per-cpu freelist와 tid가 다음 엔트리를 가리키게 한 후 object를 반환한다.

9) per-cpu partial 리스트에 slab page가 존재하는 경우 리스트의 slab page 하나를 per-cpu slab page로 설정하여 redo 레이블로 이동한다.

10) new_slab_objects를 호출하여 node의 partial 리스트 혹은 buddy system allocator에서 새 free object를 할당받는다.

11) 할당받지 못한 경우 out of memory 처리 후 NULL을 반환한다.

12) 비상 상황이 아닌데 비상용 slub page가 선택된 경우 load_freelist 레이블로 이동하여 할당을 재시도한다.

13) 디버그 상황에서 문제가 생긴 경우 new_slab 레이블로 다시 이동한다.

14) s->page에 연결된 slab page를 deactivate 시키고 할당 받은 object를 반환한다.

루틴이 길었는데, 결국 c->page->freelist, c->partial, node->partial 순으로 refill을 시도하고 실패한 경우 직접 할당자에서 slab page를 할당 받는다.

 

 

 

5. Slub Object 해제

 

슬랩 object 해제는 single slab 해제인 kmem_cache_free 함수와 bulk slab 해제인 kmem_cache_free_bulk가 있다.

두 함수 모두 slab_free -> do_slab_free를 호출하여 object를 해제한다.

/*
 * Fastpath with forced inlining to produce a kfree and kmem_cache_free that
 * can perform fastpath freeing without additional function calls.
 *
 * The fastpath is only possible if we are freeing to the current cpu slab
 * of this processor. This typically the case if we have just allocated
 * the item before.
 *
 * If fastpath is not possible then fall back to __slab_free where we deal
 * with all sorts of special processing.
 *
 * Bulk free of a freelist with several objects (all pointing to the
 * same page) possible by specifying head and tail ptr, plus objects
 * count (cnt). Bulk free indicated by tail pointer being set.
 */
static __always_inline void do_slab_free(struct kmem_cache *s,
				struct page *page, void *head, void *tail,
				int cnt, unsigned long addr)
{
	void *tail_obj = tail ? : head;
	struct kmem_cache_cpu *c;
	unsigned long tid;
redo:
	/*
	 * Determine the currently cpus per cpu slab.
	 * The cpu may change afterward. However that does not matter since
	 * data is retrieved via this pointer. If we are on the same cpu
	 * during the cmpxchg then the free will succeed.
	 */
	do {
		tid = this_cpu_read(s->cpu_slab->tid);
		c = raw_cpu_ptr(s->cpu_slab);
	} while (IS_ENABLED(CONFIG_PREEMPTION) &&
		 unlikely(tid != READ_ONCE(c->tid)));
 
	/* Same with comment on barrier() in slab_alloc_node() */
	barrier();
 
	if (likely(page == c->page)) {
		void **freelist = READ_ONCE(c->freelist);
 
		set_freepointer(s, tail_obj, freelist);
 
		if (unlikely(!this_cpu_cmpxchg_double(
				s->cpu_slab->freelist, s->cpu_slab->tid,
				freelist, tid,
				head, next_tid(tid)))) {
 
			note_cmpxchg_failure("slab_free", s, tid);
			goto redo;
		}
		stat(s, FREE_FASTPATH);
	} else
		__slab_free(s, page, head, tail_obj, cnt, addr);
 
}

간략화하면 인자로 전달받은 head부터 tail까지의 object를 set_freepointer, this_cpu_cmpxchg_double로 해제하고 FREE_FASTPATH 카운터를 증가하거나, slab page가 현재 per-cpu cache page와 다른 경우 __slab_free를 호출하여 slow-path free를 진행한다.

이미 할당 함수에서 봤던 내용과 유사하기에 간략화하고 넘어간다.

 

__slab_free 함수의 정의는 다음과 같다.

/*
 * Slow path handling. This may still be called frequently since objects
 * have a longer lifetime than the cpu slabs in most processing loads.
 *
 * So we still attempt to reduce cache line usage. Just take the slab
 * lock and free the item. If there is no additional partial page
 * handling required then we can return immediately.
 */
static void __slab_free(struct kmem_cache *s, struct page *page,
			void *head, void *tail, int cnt,
			unsigned long addr)
 
{
	void *prior;
	int was_frozen;
	struct page new;
	unsigned long counters;
	struct kmem_cache_node *n = NULL;
	unsigned long uninitialized_var(flags);
 
	stat(s, FREE_SLOWPATH);
 
	if (kmem_cache_debug(s) &&
	    !free_debug_processing(s, page, head, tail, cnt, addr))
		return;
 
	do {
		if (unlikely(n)) {
			spin_unlock_irqrestore(&n->list_lock, flags);
			n = NULL;
		}
		prior = page->freelist;
		counters = page->counters;
		set_freepointer(s, tail, prior);
		new.counters = counters;
		was_frozen = new.frozen;
		new.inuse -= cnt;
		if ((!new.inuse || !prior) && !was_frozen) {
 
			if (kmem_cache_has_cpu_partial(s) && !prior) {
 
				/*
				 * Slab was on no list before and will be
				 * partially empty
				 * We can defer the list move and instead
				 * freeze it.
				 */
				new.frozen = 1;
 
			} else { /* Needs to be taken off a list */
 
				n = get_node(s, page_to_nid(page));
				/*
				 * Speculatively acquire the list_lock.
				 * If the cmpxchg does not succeed then we may
				 * drop the list_lock without any processing.
				 *
				 * Otherwise the list_lock will synchronize with
				 * other processors updating the list of slabs.
				 */
				spin_lock_irqsave(&n->list_lock, flags);
 
			}
		}
 
	} while (!cmpxchg_double_slab(s, page,
		prior, counters,
		head, new.counters,
		"__slab_free"));
 
	if (likely(!n)) {
 
		/*
		 * If we just froze the page then put it onto the
		 * per cpu partial list.
		 */
		if (new.frozen && !was_frozen) {
			put_cpu_partial(s, page, 1);
			stat(s, CPU_PARTIAL_FREE);
		}
		/*
		 * The list lock was not taken therefore no list
		 * activity can be necessary.
		 */
		if (was_frozen)
			stat(s, FREE_FROZEN);
		return;
	}
 
	if (unlikely(!new.inuse && n->nr_partial >= s->min_partial))
		goto slab_empty;
 
	/*
	 * Objects left in the slab. If it was not on the partial list before
	 * then add it.
	 */
	if (!kmem_cache_has_cpu_partial(s) && unlikely(!prior)) {
		remove_full(s, n, page);
		add_partial(n, page, DEACTIVATE_TO_TAIL);
		stat(s, FREE_ADD_PARTIAL);
	}
	spin_unlock_irqrestore(&n->list_lock, flags);
	return;
 
slab_empty:
	if (prior) {
		/*
		 * Slab on the partial list.
		 */
		remove_partial(n, page);
		stat(s, FREE_REMOVE_PARTIAL);
	} else {
		/* Slab must be on the full list */
		remove_full(s, n, page);
	}
 
	spin_unlock_irqrestore(&n->list_lock, flags);
	stat(s, FREE_SLAB);
	discard_slab(s, page);
}

간략화하면 다음과 같다.

1) page->freelist의 앞에 free object를 insert 할 준비를 한다.

2) frozen 조건이 아니면서 prior(page->freelist)가 없는 경우 slab page를 frozen 시킬 준비를 한다.

3) frozen 조건이 아니면서 prior가 있는 경우 소속 노드를 구한다.

4) cmpxchg_double_slab으로 page->freelist와 prior이 같을 경우 (counter 또한) page의 freelist에 head를 대입한다.

5) node가 NULL인 경우 새로 frozen 된 slab page는 c->partial 리스트에 추가하고, 기존에 frozen인 경우는 카운터를 증가시킨 후 return한다.

6) slab page의 모든 object가 free object이며 node의 partial slab 수가 overflow된 경우 slab_empty 레이블로 이동한다.

7) per-cpu partial 리스트를 지원하지 않으면서 prior이 없는 경우 page를 node의 partial 리스트에 추가한다.

8) slab_empty 레이블에서는 리스트를 정리하고 slab page를 buddy system상에서 해제하게 만든다.

 

 

 

 

이번 포스트에서는 슬랩의 개념과 슬랩 캐시/오브젝트의 생성에 대해서 알아보았다.

다음 포스트에서는 슬랩 페이지를 할당하는 과정에 대해 알아보고, 슬랩 사용 모듈 예제를 작성하도록 한다.