setup_kmalloc_cache_index_table()

• kmalloc min size에 맞게 캐시 인덱스를 조정해주는 함수이다.

struct kmem_cache *
kmalloc_caches[NR_KMALLOC_TYPES][KMALLOC_SHIFT_HIGH + 1] __ro_after_init =
{ /* initialization for <https://bugs.llvm.org/show_bug.cgi?id=42570> */ };
EXPORT_SYMBOL(kmalloc_caches);

/*
 * Conversion table for small slabs sizes / 8 to the index in the
 * kmalloc array. This is necessary for slabs < 192 since we have non power
 * of two cache sizes there. The size of larger slabs can be determined using
 * fls.
 */
static u8 size_index[24] __ro_after_init = {
	3,	/* 8 */
	4,	/* 16 */
	5,	/* 24 */
	5,	/* 32 */
	6,	/* 40 */
	6,	/* 48 */
	6,	/* 56 */
	6,	/* 64 */
	1,	/* 72 */
	1,	/* 80 */
	1,	/* 88 */
	1,	/* 96 */
	7,	/* 104 */
	7,	/* 112 */
	7,	/* 120 */
	7,	/* 128 */
	2,	/* 136 */
	2,	/* 144 */
	2,	/* 152 */
	2,	/* 160 */
	2,	/* 168 */
	2,	/* 176 */
	2,	/* 184 */
	2	/* 192 */
};

• kmalloc_caches는 kmalloc의 캐시들을 가지고 있는 배열이다. 타입 별로 페이지 두개 크기까지 가지고 있다.
• size_index 배열은 8의 배수 크기별로 참조할 캐시의 인덱스 저장한다.

/*
 * Patch up the size_index table if we have strange large alignment
 * requirements for the kmalloc array. This is only the case for
 * MIPS it seems. The standard arches will not generate any code here.
 *
 * Largest permitted alignment is 256 bytes due to the way we
 * handle the index determination for the smaller caches.
 *
 * Make sure that nothing crazy happens if someone starts tinkering
 * around with ARCH_KMALLOC_MINALIGN
 */
void __init setup_kmalloc_cache_index_table(void)
{
	unsigned int i;

	BUILD_BUG_ON(KMALLOC_MIN_SIZE > 256 ||
		!is_power_of_2(KMALLOC_MIN_SIZE));

• Min size가 256크거나 2의 승수가 아니면 안됨.

	for (i = 8; i < KMALLOC_MIN_SIZE; i += 8) {
		unsigned int elem = size_index_elem(i);

		if (elem >= ARRAY_SIZE(size_index))
			break;
		size_index[elem] = KMALLOC_SHIFT_LOW;
	}

• KMALLOC_MIN_SIZE보다 작은 size에 대해서는 모두 제일 작은 kmalloc 캐시를 사용하도록 인덱스를 설정한다.

	if (KMALLOC_MIN_SIZE >= 64) {
		/*
		 * The 96 byte sized cache is not used if the alignment
		 * is 64 byte.
		 */
		for (i = 64 + 8; i <= 96; i += 8)
			size_index[size_index_elem(i)] = 7;

	}

• KMALLOC_MIN_SIZE가 64바이트 이상일 경우에는 kmalloc 사이즈 96은 align에 맞지 않으므로 128의 kmalloc 캐시를 사용하도록 인덱스를 세팅한다.

	if (KMALLOC_MIN_SIZE >= 128) {
		/*
		 * The 192 byte sized cache is not used if the alignment
		 * is 128 byte. Redirect kmalloc to use the 256 byte cache
		 * instead.
		 */
		for (i = 128 + 8; i <= 192; i += 8)
			size_index[size_index_elem(i)] = 8;
	}
}

• KMALLOC_MIN_SIZE가 128바이트 이상일 경우에는 kmalloc 사이즈 192은 align에 맞지 않으므로 256의 kmalloc 캐시를 사용하도록 인덱스를 세팅한다.

create_kmalloc_caches()

• kmalloc 타입과 사이즈 별로 kmalloc 캐시를 생성한다.

/*
 * Create the kmalloc array. Some of the regular kmalloc arrays
 * may already have been created because they were needed to
 * enable allocations for slab creation.
 */
void __init create_kmalloc_caches(slab_flags_t flags)
{
	int i;
	enum kmalloc_cache_type type;

	/*
	 * Including KMALLOC_CGROUP if CONFIG_MEMCG_KMEM defined
	 */
	for (type = KMALLOC_NORMAL; type < NR_KMALLOC_TYPES; type++) {
		for (i = KMALLOC_SHIFT_LOW; i <= KMALLOC_SHIFT_HIGH; i++) {
			if (!kmalloc_caches[type][i])
				new_kmalloc_cache(i, type, flags);

			/*
			 * Caches that are not of the two-to-the-power-of size.
			 * These have to be created immediately after the
			 * earlier power of two caches
			 */
			if (KMALLOC_MIN_SIZE <= 32 && i == 6 &&
					!kmalloc_caches[type][1])
				new_kmalloc_cache(1, type, flags);
			if (KMALLOC_MIN_SIZE <= 64 && i == 7 &&
					!kmalloc_caches[type][2])
				new_kmalloc_cache(2, type, flags);
		}
	}

• type과 kmalloc 크기 별로 for문을 돌면서 new_kmalloc_cache함수를 통해 해당 타입과 사이즈의 kmalloc을 생성한다.
• 64와 192 사이즈의 kmalloc 캐시의 경우, KMALLOC_MIN_SIZE에 따라 사용을 하지 않는 경우가 있으므로 생성하지 않을 수도 있다.
• Slab의 제약조건으로 크기 순으로 캐시가 생성되어야 하지만, Slub에서는 해당 제한이 사라졌다.

#ifdef CONFIG_RANDOM_KMALLOC_CACHES
	random_kmalloc_seed = get_random_u64();
#endif

• CONFIG_RANDOM_KMALLOC_CACHES이 켜져 있으면 보안적인 이유로 같은 크기의 kmalloc 캐시를 15개씩 생성한다. random_kmalloc_seed을 통해 alloc 요청이 오면 어떤 캐시를 사용할지 결정한다.

	/* Kmalloc array is now usable */
	slab_state = UP;
}

• kmalloc이 전부 생성되면 slab_state를 UP으로 설정한다.

new_kmalloc_cache()

• kmalloc 캐시를 생성해주는 함수.

void __init
new_kmalloc_cache(int idx, enum kmalloc_cache_type type, slab_flags_t flags)
{
	unsigned int minalign = __kmalloc_minalign();
	unsigned int aligned_size = kmalloc_info[idx].size;
	int aligned_idx = idx;

• __kmalloc_minalign()을 통해 캐시 사이즈의 min align값을 가지고 온다.

if ((KMALLOC_RECLAIM != KMALLOC_NORMAL) && (type == KMALLOC_RECLAIM)) {
		flags |= SLAB_RECLAIM_ACCOUNT;
	} else if (IS_ENABLED(CONFIG_MEMCG_KMEM) && (type == KMALLOC_CGROUP)) {
		if (mem_cgroup_kmem_disabled()) {
			kmalloc_caches[type][idx] = kmalloc_caches[KMALLOC_NORMAL][idx];
			return;
		}
		flags |= SLAB_ACCOUNT;
	} else if (IS_ENABLED(CONFIG_ZONE_DMA) && (type == KMALLOC_DMA)) {
		flags |= SLAB_CACHE_DMA;
	}

#ifdef CONFIG_RANDOM_KMALLOC_CACHES
	if (type >= KMALLOC_RANDOM_START && type <= KMALLOC_RANDOM_END)
		flags |= SLAB_NO_MERGE;
#endif

	/*
	 * If CONFIG_MEMCG_KMEM is enabled, disable cache merging for
	 * KMALLOC_NORMAL caches.
	 */
	if (IS_ENABLED(CONFIG_MEMCG_KMEM) && (type == KMALLOC_NORMAL))
		flags |= SLAB_NO_MERGE;

• kmalloc 타입이 RECLAIM, CGROUP, DMA인 경우 각각 맞는 flag를 세팅해준다.
• 랜덤 캐시를 사용하거나 cgroup을 사용하는데 타입이 normal이면 머지를 하지 않도록 flag를 세팅한다.

	if (minalign > ARCH_KMALLOC_MINALIGN) {
		aligned_size = ALIGN(aligned_size, minalign);
		aligned_idx = __kmalloc_index(aligned_size, false);
	}

	if (!kmalloc_caches[type][aligned_idx])
		kmalloc_caches[type][aligned_idx] = create_kmalloc_cache(
					kmalloc_info[aligned_idx].name[type],
					aligned_size, flags);
	if (idx != aligned_idx)
		kmalloc_caches[type][idx] = kmalloc_caches[type][aligned_idx];
}

• ARCH_KMALLOC_MINALIGN보다 minaling이 큰 경우 size를 minaling에 맞게 조정해주고 변경된 크기에 따라 사용할 캐시의 인덱스를 새로 가지고 온다.
• create_kmalloc_cache()를 통해 캐시를 생성해 kmalloc 캐시 배열에 넣는다.
• align으로 인해 캐시 인덱스가 변경된 경우 변경된 인덱스의 캐시를 사용하도록 한다.

__kmalloc_minalign()

static unsigned int __kmalloc_minalign(void)
{
	unsigned int minalign = dma_get_cache_alignment();

	if (IS_ENABLED(CONFIG_DMA_BOUNCE_UNALIGNED_KMALLOC) &&
	    is_swiotlb_allocated())
		minalign = ARCH_KMALLOC_MINALIGN;

	return max(minalign, arch_slab_minalign());
}

• dma align을 기본 align으로 한다. ARM에서는 cache line 사이즈가 dma align이다.
• 소프트웨어로 구현된 IO MMU와 유사한 swiotlb를 사용하고, DMA bounce buffer를 사용하는 경우, ARCH_KMALLOC_MINALIGN로 minalign을 설정한다. dma aling을 min aling으로 사용할 경우 align 값이 매우 커질 수 있으므로 ARCH_KMALLOC_MINALIGN로 세팅하는 것이 유리하다.

init_freelist_randomization()

static void __init init_freelist_randomization(void)
{
	struct kmem_cache *s;

	mutex_lock(&slab_mutex);

	list_for_each_entry(s, &slab_caches, list)
		init_cache_random_seq(s);

	mutex_unlock(&slab_mutex);
}

각 cache 별로, random sequence를 초기화 한다.

init_cache_random_seq()

static int init_cache_random_seq(struct kmem_cache *s)
{
	unsigned int count = oo_objects(s->oo);
	int err;

인자로 받은 cache가 몇 개의 object를 가지고 있는 지를 반환한다.

	/* Bailout if already initialised */
	if (s->random_seq)
		return 0;

kmem_cache 구조체에 random_seq 값이 설정되어 있다는 것은 이미 random sequence를 초기화 했다는 뜻이므로 더 진행하지 않고 종료한다.

	err = cache_random_seq_create(s, count, GFP_KERNEL);
	if (err) {
		pr_err("SLUB: Unable to initialize free list for %s\\n",
			s->name);
		return err;
	}

각 캐시에 대한 random sequence를 초기화하기 위한 함수를 호출하고, 실패시 에러 로그 출력 후 에러를 반환한다.

	/* Transform to an offset on the set of pages */
	if (s->random_seq) {
		unsigned int i;

		for (i = 0; i < count; i++)
			s->random_seq[i] *= s->size;
	}
	return 0;

정상적으로 random sequence를 초기화 하였다면 random_seq 배열이 다음처럼 설정되었을 것이다.

이 배열에 object size를 곱해주어, page로부터의 offset을 저장해둔다.

예를 들어, 0번째 object를 첫 번째로 freelist에 넣었다면, 다음 들어갈 object의 위치는 slab page address + (random_seq배열의 0번째 index에 있는 값 = 3 * object_size) 가 된다.

그 다음 object의 위치는 slab page address + (random_seq배열의 3번째 index에 있는 값 = 2 * object_size) 가 된다.

cache_random_seq_create()

int cache_random_seq_create(struct kmem_cache *cachep, unsigned int count,
				    gfp_t gfp)
{

	if (count < 2 || cachep->random_seq)
		return 0;

shuffle의 의미 없거나 (object가 2개 미만), 이미 random sequence 배열이 설정되어 있는 경우 더이상 진행하지 않고 종료한다.

	cachep->random_seq = kcalloc(count, sizeof(unsigned int), gfp);
	if (!cachep->random_seq)
		return -ENOMEM;

kcalloc을 통하여, object개수만큼의 길이를 가지는 unsigned int 배열을 할당받고, 실패시 에러를 반환하고 종료한다.

	freelist_randomize(cachep->random_seq, count);
	return 0;

할당받은 배열을 freelist_randomize 함수에 전달하여 randomize를 진행한다.

freelist_randomize()

static void freelist_randomize(unsigned int *list,
			       unsigned int count)
{
	unsigned int rand;
	unsigned int i;

	for (i = 0; i < count; i++)
		list[i] = i;

	/* Fisher-Yates shuffle */
	for (i = count - 1; i > 0; i--) {
		rand = get_random_u32_below(i + 1);
		swap(list[i], list[rand]);
	}
}

Fisher-Yates shuffle 방식을 활용한다.

1. list에 값을 idx 값으로 초기화한다.

2. 전체 idx에서 하나를 랜덤하게 골라 마지막 idx에 있는 값과 교환한다. 예를 들어, idx 1이 선택된 경우, 마지막 idx인 5에 있는 값과 교환한다.

3. 마지막 idx를 제외한 배열에서, 하나를 랜덤하게 골라 해당 배열의 끝과 교환한다. 예를 들어, idx 2가 선택된 경우, 마지막 idx를 제외한 배열의 마지막 idx인 4에 있는 값과 교환한다.
4. 반복하여 리스트 전체를 shuffle 한다.

kmalloc

• 커널이 미리 준비해둔 캐시인 kmalloc 캐시를 사용해서 메모리를 할당해주는 함수이다.

static __always_inline __alloc_size(1) void *kmalloc(size_t size, gfp_t flags)
{
	if (__builtin_constant_p(size) && size) {
		unsigned int index;

		if (size > KMALLOC_MAX_CACHE_SIZE)
			return kmalloc_large(size, flags);

		index = kmalloc_index(size);
		return kmalloc_trace(
				kmalloc_caches[kmalloc_type(flags, _RET_IP_)][index],
				flags, size);
	}
	return __kmalloc(size, flags);
}

• inline함수로 size가 상수일 경우에 몇몇 부분에서 컴파일 타임에 최적화가 될 수 있다.
• size가 kmalloc 최대 캐시 크기보다 클 경우, kmalloc_large()를 통해 버디에서 바로 적절한 오더의 페이지를 가지고 와서 반환한다.
• 사이즈에 따라 kmalloc 인덱스를 가지고 와서 kmalloc_trace() 함수 안에서 __kmem_cache_alloc_node()을 통해 캐시 객체를 가지고 온다.
• size가 상수가 아닐 경우 __kmalloc()을 통해 __do_kmalloc_node()로 넘어가 객체를 가지고 온다.

__do_kmalloc_node()

void *__do_kmalloc_node(size_t size, gfp_t flags, int node, unsigned long caller)
{
	struct kmem_cache *s;
	void *ret;

	if (unlikely(size > KMALLOC_MAX_CACHE_SIZE)) {
		ret = __kmalloc_large_node(size, flags, node);
		trace_kmalloc(caller, ret, size,
			      PAGE_SIZE << get_order(size), flags, node);
		return ret;
	}

• size가 KMALLOC_MAX_CACHE_SIZE 보다 클 경우 __kmalloc_large_node()을 통해 버디에서 적절한 오더의 페이지를 가지고 와서 반환한다.

	s = kmalloc_slab(size, flags, caller);

	if (unlikely(ZERO_OR_NULL_PTR(s)))
		return s;

• kmalloc_slab()에서 size에 맞는 인덱스를 구해 kmalloc 캐시 배열에서 캐시를 가지고 온다.

	ret = __kmem_cache_alloc_node(s, flags, node, size, caller);
	ret = kasan_kmalloc(s, ret, size, flags);
	trace_kmalloc(caller, ret, size, s->size, flags, node);
	return ret;
}

• 가져온 캐시로 __kmem_cache_alloc_node()를 통해 객체를 할당해 온다.

kfree

general cache (kmalloc-xx) object 또는 kmem_cache_alloc으로 할당한 dedicated cache object를 할당 해제하기 위해 사용한다.

void kfree(const void *object)
{
	struct folio *folio;
	struct slab *slab;
	struct kmem_cache *s;

	trace_kfree(_RET_IP_, object);

	if (unlikely(ZERO_OR_NULL_PTR(object)))
		return;

kfree에 대한 trace event를 발생시키고, 인자로 들어온 object가 zero거나 null ptr인 경우 더 이상 진행하지 않고 종료한다.

	folio = virt_to_folio(object);

해당 object를 가진 folio를 얻어온다.

folio란, compound page를 표현하는 추상화된 구조체로, struct page 1~3개로 구성되어있다

• struct page 1개 : order 0 page
• struct page 2개: order ≥ 1 compound page, not use hugetlb
• struct page 3개: order ≥2 compound page, use hugetlb

struct folio를 사용하는 경우, 반드시 head page를 포함하고 있음을 보장한다.

	if (unlikely(!folio_test_slab(folio))) {
		free_large_kmalloc(folio, (void *)object);
		return;
	}

free할 object를 포함하고 있는 folio가 slab page로 mark 되어 있지 않은 경우 (does not set PG_slab flag), 해당 folio는 kmalloc_large로부터 할당된 folio이다.

따라서, 별도의 처리 루틴을 거친다.

	slab = folio_slab(folio);
	s = slab->slab_cache;
	__kmem_cache_free(s, (void *)object, _RET_IP_);
}

해당 folio가 slab page로 mark 되어 있는 경우, 일반적인 slab cache object free 루틴을 따른다.

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)를 수정할 수 있다.