kmem_cache_free()

void kmem_cache_free(struct kmem_cache *s, void *x)
{
	s = cache_from_obj(s, x);
	if (!s)
		return;
	trace_kmem_cache_free(_RET_IP_, x, s);
	slab_free(s, virt_to_slab(x), x, NULL, &x, 1, _RET_IP_);
}

슬랩 오브젝트를 free하기 위한 함수이다.

cache_from_obj()를 통해 인자로 넘어온 kmem_cache인 s와 free할 오브젝트인 x가 속한 kmem_cache가 맞는지 확인한다. 오브젝트의 kmem_cache를 가져오기 위해서는 x가 속한 page의 헤더에 있는 정보를 참조한다. 이 과정은 몇 가지 처리가 더 필요함으로 설정에 따라 비교를 하지 않을 수 있다.

static __fastpath_inline void slab_free(struct kmem_cache *s, struct slab *slab,
				      void *head, void *tail, void **p, int cnt,
				      unsigned long addr)
{
	memcg_slab_free_hook(s, slab, p, cnt);

cgroup의 memory controller 관련 hook 함수를 호출한다.

	/*
	 * With KASAN enabled slab_free_freelist_hook modifies the freelist
	 * to remove objects, whose reuse must be delayed.
	 */
	if (slab_free_freelist_hook(s, &head, &tail, &cnt))
		do_slab_free(s, slab, head, tail, cnt, addr);
}

do_slab_free()가 실질적으로 해제를 하는 함수인데, KASAN이 활성화된 경우, freelist (head ~ tail)를 수정할 수 있다.

do_slab_free() (!SLUB_TINY)

/*
 * 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 slab) 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 slab *slab, void *head, void *tail,
				int cnt, unsigned long addr)
{
	void *tail_obj = tail ? : head;
	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();

현재 CPU의 kmem_cache_cpu (c)를 읽어오고, 다른 필드들보다 가장 먼저 transaction id (tid) 필드를 읽어온다. tid 이외의 다른 필드를 먼저 읽지 않도록 컴파일러 배리어를 사용한다. 컴파일러 배리어는 읽기/쓰기 배리어처럼 실제 CPU instruction 이 삽입되지는 않고, 컴파일러가 순서를 바꾸지 못하록 한다.

만약 kmem_cache_cpu의 다른 필드를 tid보다 먼저 읽어온다면 무결성이 깨질 수 있다. (cmpxchg_double을 할때 tid가 바뀌지 않았더라도, c→freelist or c→slab를 읽고 나서 c→tid를 읽는 그 사이에 누군가 객체를 해제하거나 할당했을 수 있다.)

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

현재 CPU slab에 속하지 않는 객체를 해제하는 경우, slowpath를 탄다.

fastpath에서는 보통 lock을 사용하지 않지만, PREEMPT_RT config 옵션이 켜진 경우에는 (cmpxchg_double을 사용한) lockless fastpath를 사용하지 않고, local_lock을 사용한다.

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

		set_freepointer(s, tail_obj, freelist);

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

!PREEMPT_RT인 경우에는 free list에 객체를 삽입한다. (tail_obj → fp)를 freelist로 바꾸고, c→freelist를 head로 갱신한다.

 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_obj, freelist);
		c->freelist = head;
		c->tid = next_tid(tid);

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

PREEMPT_RT에서도 똑같이 객체를 freelist에 삽입하지만 local_lock을 사용한다.

__slab_free()

slowpath에서는, 위 다이어그램과 같이 slab→freelist와 counter(inuse, frozen)들을 갱신한다. SLUB은 free path에서 최대한 n→list_lock을 사용하지 않고, slab_update_freelist()로 객체를 해제하려고 한다. 단, 객체의 해제 후 node의 partial slab list를 수정해야 하는 경우 (1. full → partial이 되어서 slab을 node partial slab list에 삽입하거나, 2. partial or full → empty가 되어서 slab을 node partial slab list에서 제거하거나)에는 slab_update_freelist()로 freelist를 갱신하기 전에 n→list_lock을 먼저 획득한다.

/*
 * 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 slab
 * handling required then we can return immediately.
 */
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;

	stat(s, FREE_SLOWPATH);

	if (kfence_free(head))
		return;

kfence에서 할당한 객체인 경우, SLUB이 아닌 kfence에서 해제되므로, 이 경우는 곧바로 리턴한다.

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

CPU slab과 CPU partial을 사용하지 않는 경우 (SLUB_TINY 옵션이 켜져있거나, 디버그 캐시인 경우) free_to_partial_list()로 node의 partial slab list에 있는 slab에 곧바로 해제한다.

아래 do ~ while문은 slab_update_freelist()이 성공할 때까지 반복하여 해제를 시도한다. slab_update_freelist()는 slab→freelist와 slab→counters를 atomic하게 갱신한다.

	do {
		if (unlikely(n)) {
			spin_unlock_irqrestore(&n->list_lock, flags);
			n = NULL;
		}

n ≠ NULL인 경우, n→list_lock을 획득한 상태로 slab_update_freelist()를 실패한 경우이므로 n→list_lock을 반환한다.

		prior = slab->freelist;
		counters = slab->counters;
		set_freepointer(s, tail, prior);
		new.counters = counters;
		was_frozen = new.frozen;
		new.inuse -= cnt;

prior는 기존의 slab→freelist의 값을 저장한다. set_freepointer()로 tail의 free pointer를 slab→freelist 변경한다.

counters에는 objects, inuse, frozen 세 값이 포함되어있다. (union과 struct를 사용하여). 기존의 counters 값을 복사한 다음, inuse를 해제할 객체의 수만큼 빼주고, was_frozen 변수에 이 슬랩이 어떤 CPU에 의해서 freeze 되었는지를 저장한다.

		if ((!new.inuse || !prior) && !was_frozen) {

일반적으로 SLUB은 __slab_free()에서 n→list_lock을 최대한 획득하지 않으려고 하지만, 객체를 해제한 다음 node의 partial slab list를 수정해야 하는 경우에는 n→list_lock을 먼저 획득한다.

1. 이번에 객체를 해제함으로써 슬랩이 empty slab이 되거나

2. slab→freelist (= prior)가 NULL이었던 경우, full slab → partial slab으로 바뀐 경우

위 두 가지 경우에는, 슬랩이 frozen slab이 아니라면 (!was_frozen) n→partial을 수정해야 하므로 n→list_lock을 획득한다. 1번 케이스는 partial slab을 n→partial에서 제거하는 경우이고, 2번 케이스는 full이었던 slab이 partial slab으로 바뀌어서 n→partial에 삽입되는 경우이다.

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;

			}

단, full slab → partial slab이 되는 경우에, 현재 캐시가 CPU partial을 사용한다면 n→partial에 삽입하는 대신 현재 CPU에서 freeze를 한 다음 CPU partial list에 삽입한다.

			else { /* Needs to be taken off a list */

				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);

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

만약 위에서 freeze를 하지 않았다면, n→list_lock을 획득한 다음 slab_update_freelist()를 시도한다. 단, slab_update_freelist()가 실패하면 다시 처음부터 시도한다.

if (likely(!n)) {

		if (likely(was_frozen)) {
			/*
			 * The list lock was not taken therefore no list
			 * activity can be necessary.
			 */
			stat(s, FREE_FROZEN);
		}

slab_update_freelist()가 성공했는데 n == NULL인 경우에는 n→partial을 전혀 수정하지 않는 경우다. was_frozen == true였다면 stat을 갱신한다.

 else if (new.frozen) {
			/*
			 * If we just froze the slab then put it onto the
			 * per cpu partial list.
			 */
			put_cpu_partial(s, slab, 1);
			stat(s, CPU_PARTIAL_FREE);
		}

		return;
	}

full → partial이 되면서 현재 CPU가 freeze한 경우에는 여기서 put_cpu_partial()로 slab을 CPU partial list에 삽입하고 stat을 갱신한다.

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

slab이 empty가 된 경우에는, 현재 노드의 partial slab 수가 최소 threshold (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, slab);
		add_partial(n, slab, DEACTIVATE_TO_TAIL);
		stat(s, FREE_ADD_PARTIAL);
	}
	spin_unlock_irqrestore(&n->list_lock, flags);
	return;

실행 흐름이 여기까지 온 경우는 1) empty slab이 되었지만 threshold 때문에 해제하지 않은 경우거나, 2) full slab → partial slab이 되었지만 freeze를 하지 않은 경우이다.

1번의 경우, 이미 n→partial에 존재하기 때문에, 2번의 경우에만 슬랩을 n→partial에 삽입한다. 일반적으로 SLUB은 full slab list를 관리하지 않지만, SLAB_STORE_USER 디버깅 플래그를 사용하는 경우에는 full slab의 linked list를 관리하기 때문에 full slab → partial slab이 되었을때, n→full에서 슬랩을 제거해주어야 한다.

n→partial 리스트를 수정한 다음에는 n→list_lock을 반환한다.

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

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

empty slab을 해제하는 경우는 두 가지로 나뉜다.

1) partial slab → empty slab이 된 경우에는 n→partial 리스트에서 슬랩을 제거한 다음 버디에게 반환한다.

2) full slab → empty slab이 된 경우에는 n→full 리스트에서 슬랩을 제거한 다음 버디에게 반환한다.

버디에게 empty slab을 반환할 때는 n→list_lock을 반환한 다음 discard_slab()을 호출한다.