[Linux Kernel] SLUB allocator - (2)

어쩌다 보니 (2) 부터 쓰게 되었는데..
SLUB allocator의 할당 해제 동작에 대해서 알아보자.

우선 kmem_cache_free() 함수를 통해서 free()가 이루어지는데,
호출 순서는 kmem_cache_free() -> slab_free() -> do_slab_free() 순이다.

do_slab_free() 부터 알아보도록 하자.

do_slab_free()

static __always_inline void do_slab_free(struct kmem_cache *s,
				struct slab *slab, void *head, void *tail,
				int cnt, unsigned long addr)
{
	struct kmem_cache_cpu *c;
	unsigned long tid;
	void **freelist;

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.
	 */
	c = raw_cpu_ptr(s->cpu_slab);
	tid = READ_ONCE(c->tid);

	/* Same with comment on barrier() in slab_alloc_node() */
	barrier();

	if (unlikely(slab != c->slab)) {
		__slab_free(s, slab, head, tail, cnt, addr);
		return;
	}

	if (USE_LOCKLESS_FAST_PATH()) {
		freelist = READ_ONCE(c->freelist);

		set_freepointer(s, tail, freelist);

		if (unlikely(!__update_cpu_freelist_fast(s, freelist, head, tid))) {
			note_cmpxchg_failure("slab_free", s, tid);
			goto redo;
		}
	} else {
		/* Update the free list under the local lock */
		local_lock(&s->cpu_slab->lock);
		c = this_cpu_ptr(s->cpu_slab);
		if (unlikely(slab != c->slab)) {
			local_unlock(&s->cpu_slab->lock);
			goto redo;
		}
		tid = c->tid;
		freelist = c->freelist;

		set_freepointer(s, tail, freelist);
		c->freelist = head;
		c->tid = next_tid(tid);

		local_unlock(&s->cpu_slab->lock);
	}
	stat_add(s, FREE_FASTPATH, cnt);
}

함수의 인자를 보면, head와 tail이 있는데, 이는 여러 objects를 동시에 할당 해제하고 싶을 때 쓰이는 최적화를 위한 부분인 것 같다.
우리는 하나의 object만 할당 해제하는 경우를 살펴볼 것이므로 head == tail == obj 라고 가정한다.

slab_free 의 경우에도 alloc과 마찬가지로 FASTPATH와 SLOWPATH가 존재한다.
먼저 첫 번째 if문을 보자.

	if (unlikely(slab != c->slab)) {
		__slab_free(s, slab, head, tail, cnt, addr);
		return;
	}

현재 할당해제하는 object가 속해있는 slab이 active slab에 해당하지 않는다면 __slab_free()를 호출하는데, 여기서 __slab_free()는 SLOWPATH에 해당한다.

SLOWPATH는 나중에 알아보고, 먼저 FASTPATH 부터 알아본다.
아키텍쳐가 cmpxchg 연산을 지원한다고 가정한다. (USE_LOCKLESS_FAST_PATH() == true)

우선 set_freepointer() 함수를 보자.

static inline void set_freepointer(struct kmem_cache *s, void *object, void *fp)
{
	unsigned long freeptr_addr = (unsigned long)object + s->offset;

#ifdef CONFIG_SLAB_FREELIST_HARDENED
	BUG_ON(object == fp); /* naive detection of double free or corruption */
#endif

	freeptr_addr = (unsigned long)kasan_reset_tag((void *)freeptr_addr);
	*(freeptr_t *)freeptr_addr = freelist_ptr_encode(s, fp, freeptr_addr);
}

object의 next pointer 값을 fp로 설정해 주는 함수이다.
CONFIG_SLAB_FREELIST_HARDENED 의 여부에 따라 encode될지 안 될지가 선택되고, 단순한 double-free 체크도 진행된다.

if (USE_LOCKLESS_FAST_PATH()) {
		freelist = READ_ONCE(c->freelist);

		set_freepointer(s, tail, freelist);

		if (unlikely(!__update_cpu_freelist_fast(s, freelist, head, tid))) {
			note_cmpxchg_failure("slab_free", s, tid);
			goto redo;
		}
	}

그냥 per-cpu freelist에 저장되고 끝난다.

그 다음 SLOWPATH를 알아보자.

static void __slab_free(struct kmem_cache *s, struct slab *slab,
			void *head, void *tail, int cnt,
			unsigned long addr)

{
	void *prior;
	int was_frozen;
	struct slab new;
	unsigned long counters;
	struct kmem_cache_node *n = NULL;
	unsigned long flags;
	bool on_node_partial;

	stat(s, FREE_SLOWPATH);

	if (IS_ENABLED(CONFIG_SLUB_TINY) || kmem_cache_debug(s)) {
		free_to_partial_list(s, slab, head, tail, cnt, addr);
		return;
	}

	do {
		if (unlikely(n)) {
			spin_unlock_irqrestore(&n->list_lock, flags);
			n = NULL;
		}
		prior = slab->freelist;
		counters = slab->counters;
		set_freepointer(s, tail, prior);
		new.counters = counters;
		was_frozen = new.frozen;
		new.inuse -= cnt;
		if ((!new.inuse || !prior) && !was_frozen) {
			/* Needs to be taken off a list */
			if (!kmem_cache_has_cpu_partial(s) || prior) {

				n = get_node(s, slab_nid(slab));
				/*
				 * 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);

				on_node_partial = slab_test_node_partial(slab);
			}
		}

	} while (!slab_update_freelist(s, slab,
		prior, counters,
		head, new.counters,
		"__slab_free"));

	if (likely(!n)) {

		if (likely(was_frozen)) {
			/*
			 * The list lock was not taken therefore no list
			 * activity can be necessary.
			 */
			stat(s, FREE_FROZEN);
		} else if (kmem_cache_has_cpu_partial(s) && !prior) {
			/*
			 * If we started with a full slab then put it onto the
			 * per cpu partial list.
			 */
			put_cpu_partial(s, slab, 1);
			stat(s, CPU_PARTIAL_FREE);
		}

		return;
	}

	/*
	 * This slab was partially empty but not on the per-node partial list,
	 * in which case we shouldn't manipulate its list, just return.
	 */
	if (prior && !on_node_partial) {
		spin_unlock_irqrestore(&n->list_lock, flags);
		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)) {
		add_partial(n, slab, 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, slab);
		stat(s, FREE_REMOVE_PARTIAL);
	}

	spin_unlock_irqrestore(&n->list_lock, flags);
	stat(s, FREE_SLAB);
	discard_slab(s, slab);
}

먼저 변수에 대한 설명이다.

• prior: 현재 slab의 freelist에 있는 제일 첫 번째 원소
• new: 현재 object가 할당 해제되면서 변화될 slab의 counters 값이 임시로 저장된다. (사실상 new.counters에 대한 정보만 쓰임)
• was_frozen: 현재 slab이 frozen인지 아닌지에 대한 정보 (리눅스 버전에 따라 다른데, 최신 버전에서는 active slab의 경우에만 frozen bit가 set되고, 예전 버전에서는 per-cpu partial freelist에 있는 slab의 경우에도 frozen bit가 set 되었다. -> 아직 불확실함. 일단은 active slab인 경우만 그렇다고 가정)

우선 do-while 문을 통해 각 변수들이 초기화되고, tail의 next 값이 prior로 설정된다.
그 후 살펴볼 내용은 다음 부분이다.

		if ((!new.inuse || !prior) && !was_frozen) {
			/* Needs to be taken off a list */
			if (!kmem_cache_has_cpu_partial(s) || prior) {

				n = get_node(s, slab_nid(slab));
				/*
				 * 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);

				on_node_partial = slab_test_node_partial(slab);
			}
		}

if 문을 해석하는데에 좀 애먹었는데, 의미는 다음과 같다.

• !was_frozen: frozen bit이 unset 되었다 -> active slab이 아니다.
• !prior: 모든 object가 할당되어있던 상태 혹은 그 중 일부가 per-cpu freelist에 속해있는 상태. 하지만 !was_frozen과 함께 생각해 보면 active slab이 아니므로 per-cpu freelist가 존재하지 않는다. -> full slab 인 경우만 해당.
• !new.inuse: free slab이 될 예정이다.

또한, 다음 if 문 또한 만족시켜야 한다.

• prior: 앞선 if문 조건 중 하나를 부정한다. 즉, !was_frozen 과 !new.inuse 만 만족하게 된다. -> partial slab에서 free slab이 될 예정인 경우만 해당한다.

왜 굳이 if 문을 이렇게 나눴나 찾아보니, 이전 버전에서는 if (kmem_cache_has_cpu_partials(s) && !prior) / else 로 경우를 나눠서 따로 처리해 놓았었다. 이 코드의 잔재가 남아있는듯.

어쨌든, 위 조건을 모두 만족시키면 n에 kmem_cache_node 가 저장되고, 현재 slab이 node의 partial list에 속해있었다면 on_node_partial은 true 값을 가지게 된다.

그 후 do-while 문에 의해 freelist 는 update 되게 된다.

n이 NULL이 아닌 경우에 대해 먼저 살펴보자.

	/*
	 * This slab was partially empty but not on the per-node partial list,
	 * in which case we shouldn't manipulate its list, just return.
	 */
	if (prior && !on_node_partial) {
		spin_unlock_irqrestore(&n->list_lock, flags);
		return;
	}

사실 주석에 설명이 잘 나와있는데, 말 그대로 처음에 partially empty이면서 node의 partial list에 속하지 않은 경우 그냥 리턴한다.

	if (unlikely(!new.inuse && n->nr_partial >= s->min_partial))
		goto slab_empty;

앞선 if문에 걸리지 않았으므로 node의 partial list에 들어가 있는 상태이다.
현재 node의 partial list에 속한 slab의 수가 s->min_partial보다 크거나 같으면 해당 slab을 free하는 과정으로 간다.

물론 이 if문에 걸리지 않으면 바로 return 한다.

slab_empty:
	if (prior) {
		/*
		 * Slab on the partial list.
		 */
		remove_partial(n, slab);
		stat(s, FREE_REMOVE_PARTIAL);
	}

	spin_unlock_irqrestore(&n->list_lock, flags);
	stat(s, FREE_SLAB);
	discard_slab(s, slab);

partial list에서 현재 slab을 제거한 후, discard_slab()을 통해서 slab의 page를 free한다.

n이 NULL인 경우를 살펴보자.

	if (likely(!n)) {

		if (likely(was_frozen)) {
			/*
			 * The list lock was not taken therefore no list
			 * activity can be necessary.
			 */
			stat(s, FREE_FROZEN);
		} else if (kmem_cache_has_cpu_partial(s) && !prior) {
			/*
			 * If we started with a full slab then put it onto the
			 * per cpu partial list.
			 */
			put_cpu_partial(s, slab, 1);
			stat(s, CPU_PARTIAL_FREE);
		}

		return;
	}

active slab인 경우 (if문) 그냥 바로 리턴한다.
full slab이었다면 (else if문) put_cpu_partial() 함수를 호출한다.
나머지 경우 그냥 리턴한다.

put_cpu_partial() 함수

/*
 * Put a slab into a partial slab slot if available.
 *
 * If we did not find a slot then simply move all the partials to the
 * per node partial list.
 */
static void put_cpu_partial(struct kmem_cache *s, struct slab *slab, int drain)
{
	struct slab *oldslab;
	struct slab *slab_to_put = NULL;
	unsigned long flags;
	int slabs = 0;

	local_lock_irqsave(&s->cpu_slab->lock, flags);

	oldslab = this_cpu_read(s->cpu_slab->partial);

	if (oldslab) {
		if (drain && oldslab->slabs >= s->cpu_partial_slabs) {
			/*
			 * Partial array is full. Move the existing set to the
			 * per node partial list. Postpone the actual unfreezing
			 * outside of the critical section.
			 */
			slab_to_put = oldslab;
			oldslab = NULL;
		} else {
			slabs = oldslab->slabs;
		}
	}

	slabs++;

	slab->slabs = slabs;
	slab->next = oldslab;

	this_cpu_write(s->cpu_slab->partial, slab);

	local_unlock_irqrestore(&s->cpu_slab->lock, flags);

	if (slab_to_put) {
		__put_partials(s, slab_to_put);
		stat(s, CPU_PARTIAL_DRAIN);
	}
}

함수 자체는 주석에 설명이 잘 나와있는데, slab을 partial list에 집어넣는데, 만약 이미 꽉 차 있다면 node partial list로 옮기는 함수이다.

node partial list로 옮기는 경우, __put_partials() 함수가 호출된다.

static void __put_partials(struct kmem_cache *s, struct slab *partial_slab)
{
	struct kmem_cache_node *n = NULL, *n2 = NULL;
	struct slab *slab, *slab_to_discard = NULL;
	unsigned long flags = 0;

	while (partial_slab) {
		slab = partial_slab;
		partial_slab = slab->next;

		n2 = get_node(s, slab_nid(slab));
		if (n != n2) {
			if (n)
				spin_unlock_irqrestore(&n->list_lock, flags);

			n = n2;
			spin_lock_irqsave(&n->list_lock, flags);
		}

		if (unlikely(!slab->inuse && n->nr_partial >= s->min_partial)) {
			slab->next = slab_to_discard;
			slab_to_discard = slab;
		} else {
			add_partial(n, slab, DEACTIVATE_TO_TAIL);
			stat(s, FREE_ADD_PARTIAL);
		}
	}

	if (n)
		spin_unlock_irqrestore(&n->list_lock, flags);

	while (slab_to_discard) {
		slab = slab_to_discard;
		slab_to_discard = slab_to_discard->next;

		stat(s, DEACTIVATE_EMPTY);
		discard_slab(s, slab);
		stat(s, FREE_SLAB);
	}
}

while 문을 통해서 partial_slab을 순회한다.
만약 free slab이고, n->nr_partial >= s->min_partial 이라면 slab_to_discard 에 저장해 놓는다.
그렇지 않다면 n의 partial list에 slab을 추가한다.

만약 slab_to_discard != NULL 이면 저장되어 있던 slab들은 discard_slab()을 통해 page가 free된다.

slab page가 free 되는 경우

앞서 살펴 보았듯이, 두 가지 경우가 존재한다.

• node partial list에 존재하면서 free slab이 될 예정이고, n->nr_partial >= s->min_partial인 경우
• per-cpu partial freelist는 꽉 차 있는 상태에서 full slab의 obj가 free되는 경우 per-cpu partial freelist에서 node partial freelist로 옮겨지는데, 그 도중에 free slab 이면서 n->nr_partial >= s->min_partial인 경우