Week 4 - Slub Allocator

Posted on Edited on In

本文章涵蓋基礎 Slub Allocator 的運作流程。

slub allocator 是基於 buddy system 上，進行更精細物件分配的機制。
buddy system 分配時皆以 2^n 個 page 為單位，但一般情況不需要這麼大的記憶體。
若我們只想要 192 bytes 的空間，卻得到一個 page，將造成不小的 fragmentation。而且空間被 free 掉後，就會馬上被合併。兩者使 buddy system 在時間和空間上，都不適合小量頻繁操作。

因此 slub allocator 將一塊連續記憶體由一個 slab 控管。底下包含多個 object，類似 glibc 的 chunk，代表固定大小要分配的區塊。
而 slab 由 kmem_cache, kmem_cache_node, kmem_cache_cpu 控管。

常用結構

slab

在較早的 linux，slab 內嵌在 page 結構，畢竟一個 slab 由多個 page 組成，page 管好底下的 object 就好。
後來統一用 slab 結構管理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
struct slab {
	unsigned long __page_flags;

	struct kmem_cache *slab_cache;
	union {
		struct {
			union {
				struct list_head slab_list;
#ifdef CONFIG_SLUB_CPU_PARTIAL
				struct {
					struct slab *next;
					int slabs;	/* Nr of slabs left */
				};
#endif
			};
			/* Double-word boundary */
			union {
				struct {
					void *freelist;		/* first free object */
					union {
						unsigned long counters;
						struct {
							unsigned inuse:16;
							unsigned objects:15;
							/*
							 * If slab debugging is enabled then the
							 * frozen bit can be reused to indicate
							 * that the slab was corrupted
							 */
							unsigned frozen:1;
						};
					};
				};
#ifdef system_has_freelist_aba
				freelist_aba_t freelist_counter;
#endif
			};
		};
		struct rcu_head rcu_head;
	};

	unsigned int __page_type;
	atomic_t __page_refcount;
#ifdef CONFIG_SLAB_OBJ_EXT
	unsigned long obj_exts;
#endif
};
  • slab_cache slab 屬於的 kmem_cache
  • freelist slab 上的 free object 組成一個 linked list，freelist 指向第一个 free object
  • slab_list 串連多個 slab
  • inuse 目前多少 object 正被使用
  • objects 此 slab 上的 object 數量
  • frozen 是否被凍結，也就是屬於特定的 CPU

counters 和 inuse, objects, frozen 組成 union，後續對 counter 做操作，等同修改他們的值。
slab 的管理範圍，基本上是負責的連續記憶體，及其擁有的 free object。

kmem_cache

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
struct kmem_cache {
#ifndef CONFIG_SLUB_TINY
    struct kmem_cache_cpu __percpu *cpu_slab;
#endif
    slab_flags_t flags;
    unsigned long min_partial;
    unsigned int size;
    unsigned int object_size;
    struct reciprocal_value reciprocal_size;
    unsigned int offset;
#ifdef CONFIG_SLUB_CPU_PARTIAL
    unsigned int cpu_partial;
    unsigned int cpu_partial_slabs;
#endif
    struct kmem_cache_order_objects oo;

    struct kmem_cache_order_objects min;
    gfp_t allocflags;
    int refcount;
    void (*ctor)(void *);
    unsigned int inuse;
    unsigned int align;
    unsigned int red_left_pad;
    const char *name;
    struct list_head list;
#ifdef CONFIG_SYSFS
    struct kobject kobj;
#endif
#ifdef CONFIG_SLAB_FREELIST_HARDENED
    unsigned long random;
#endif

#ifdef CONFIG_NUMA
    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

#ifdef CONFIG_HARDENED_USERCOPY
    unsigned int useroffset;
    unsigned int usersize;
#endif

    struct kmem_cache_node *node[MAX_NUMNODES];
};
  • cpu_slab 當前 CPU 使用的 kmem_cache_cpu 結構
  • min_partial partial list 上 slab 的最大數量
  • cpu_partial 每個 CPU 的 partial list 的最大 object 數量
  • cpu_partial_slabs 每個 CPU 的 partial list 的最大 slab 數量
  • size 一個 object 包含 alignment 的大小
  • object_size 一個 object 實際大小
  • offset slab 的 freelist 指向 object 上的偏移
  • oo 一個 int
    • 低 16 位：一個 slab 的 object 數量
    • 高 16 位：一個 slab 的大小
  • min 一個 slab 的最少 object 數量
  • allocflags 向 buddy system 索取 page 所用的 gfp flag
  • ctor 分配 object 後調用 constructor
  • random_seq 用於 CONFIG_SLAB_FREELIST_RANDOM 打亂 freelist 順序
  • CONFIG_HARDENED_USERCOPY 相關
    • useroffset user space 能讀寫的 offset
    • usersize user space 能讀寫的 size
  • node 包含多個 kmem_cache_node

kmem_cache 負責控管全局資訊，包含 size, metadata，底下的 node 和 per cpu 等。一個 kmem_cache 只負責一個 size 的 object，與其他 cache 組成 double linked list。

kmem_cache_cpu

1
2
3
4
5
6
7
8
9
10
11
12
struct kmem_cache_cpu {
    void **freelist;
    unsigned long tid;
    struct slab *slab;
#ifdef CONFIG_SLUB_CPU_PARTIAL
    struct slab *partial;
#endif
    local_lock_t lock;
#ifdef CONFIG_SLUB_STATS
    unsigned stat[NR_SLUB_STAT_ITEMS];
#endif
};
  • freelist 指向下一個 free object
  • slab 當前用來分配的 slab（只有一個），若要 allocate 時已滿，或是 free 時已完全空閒，可能換成其他 slab
  • partial 包含擁有 free object 的 slab 列表

kmem_cache_cpu 統合所有 slab，包含已經無 freelist 的 slab，操作時爲避免 context switch 造成 race condition，對 list 操作前常使用 lock。
slab->freelist 僅當在 partial 時有用，若它是當前 CPU 使用的 slab，則 freelist 會移到 kmem_cache_cpu->freelist。

xSLqghNZ23nCMiz.png

kmem_cache_node

1
2
3
4
5
6
7
8
9
10
struct kmem_cache_node {
    spinlock_t list_lock;
    unsigned long nr_partial;
    struct list_head partial;
#ifdef CONFIG_SLUB_DEBUG
    atomic_long_t nr_slabs;
    atomic_long_t total_objects;
    struct list_head full;
#endif
};
  • list_lock 保護 partial 和 full 的 lock
  • nr_partial partial slab 的数量
  • partial 包含擁有 free object 的 slab
  • nr_slabs partial + full 的 slab 数量
  • total_objects object 數量總和
  • full 包含無 free object 的 slab

object

object 並無一個固定的 struct，它的結構依 object 大小和設定調整。

1
2
3
4
5
6
7
8
9
Debug off:
---------------------------------
| object | free pointer | align |
---------------------------------

Debug on:
--------------------------------------------------------------------------------
| object | red zone | free pointer | track | origin kmalloc req | red left pad |
--------------------------------------------------------------------------------

free pointer 位置在某些情況會存 object 正中間。
slab 只紀錄 free object，正被使用的 object 不會有 pointer 指向下一個 free object。

參考資料