kernel

Linux kernel 7.0 Slub allocator analyze

Overview

note for linux kernel 7.0 slub allocator analyze

in linux kernel to manage small kernel object uses slab allocator , a bit similar to userspace glibc ptmalloc same size object goes to same size slab cache.

as for slab allocator implementation theres 3 ways:

  • slab , removed in linux kernel 6.8
  • slub , the only slab allocator in mainline currently
  • slob , removed in linux kernel 6.4

this note only talked about slub allocator , the slab mentioned below all refers to slub

Object

if CONFIG_SLUB_DEBUG_ON and CONFIG_KASAN is on , its layout would look like this
image

but in default setting these won’t be on , default layout would be look like this instead
image
the FP is free pointer , which used when the object get freed and append to the freelist , pointing the next freed object
image

kmem_cache

different kernel object(size) got it’s own slab cache , struct kmem_cache including all the slab cache info.

https://elixir.bootlin.com/linux/v7.0/source/mm/slab.h#L197

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
52
53
54
55
struct kmem_cache {
 struct slub_percpu_sheaves __percpu *cpu_sheaves;
 /* Used for retrieving partial slabs, etc. */
 slab_flags_t flags;
 unsigned long min_partial;
 unsigned int size;  /* Object size including metadata */
 unsigned int object_size; /* Object size without metadata */
 struct reciprocal_value reciprocal_size;
 unsigned int offset;  /* Free pointer offset */
 unsigned int sheaf_capacity;
 struct kmem_cache_order_objects oo;

 /* Allocation and freeing of slabs */
 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 *object); /* Object constructor */
 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 */
#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_GENERIC
 struct kasan_cache kasan_info;
#endif

#ifdef CONFIG_HARDENED_USERCOPY
 unsigned int useroffset; /* Usercopy region offset */
 unsigned int usersize;  /* Usercopy region size */
#endif

#ifdef CONFIG_SLUB_STATS
 struct kmem_cache_stats __percpu *cpu_stats;
#endif

 struct kmem_cache_node *node[MAX_NUMNODES];
};

__kmem_cache_create_args()

__kmem_cache_create_args() is used to create kmem_cache for specific kernel object
example: cred object

macro KMEM_CACHE()

https://elixir.bootlin.com/linux/v7.0/source/kernel/cred.c#L535

1
2
3
4
5
6
7
8
9
/*
 * initialise the credentials stuff
 */
void __init cred_init(void)
{
 /* allocate a slab in which we can store credentials */
 cred_jar = KMEM_CACHE(cred,
         SLAB_HWCACHE_ALIGN | SLAB_PANIC | SLAB_ACCOUNT);
}
expand the macro KMEM_CACHE()

https://elixir.bootlin.com/linux/v7.0/source/include/linux/slab.h#L484

1
2
3
4
5
#define KMEM_CACHE(__struct, __flags)                                   \
 __kmem_cache_create_args(#__struct, sizeof(struct __struct),    \
   &(struct kmem_cache_args) {   \
    .align = __alignof__(struct __struct), \
   }, (__flags))

kmem_cache_alloc()

kmem_cache_alloc() used to allocate object from slab cache

https://elixir.bootlin.com/linux/v7.0/source/kernel/cred.c#L558

1
2
3
4
5
6
7
8
9
struct cred *prepare_kernel_cred(struct task_struct *daemon)
{
 const struct cred *old;
 struct cred *new;

 if (WARN_ON_ONCE(!daemon))
  return NULL;

 new = kmem_cache_alloc(cred_jar, GFP_KERNEL);

slub_percpu_sheaves

every logical cpu has it’s own slub_percpu_sheaves
https://elixir.bootlin.com/linux/v7.0/source/mm/slub.c#L420

1
2
3
4
5
6
struct slub_percpu_sheaves {
 local_trylock_t lock;
 struct slab_sheaf *main; /* never NULL when unlocked */
 struct slab_sheaf *spare; /* empty or full, may be NULL */
 struct slab_sheaf *rcu_free; /* for batching kfree_rcu() */
};

example: CPU 0 and CPU 1
image

slab_sheaf

https://elixir.bootlin.com/linux/v7.0/source/mm/slub.c#L404

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct slab_sheaf {
 union {
  struct rcu_head rcu_head;
  struct list_head barn_list;
  /* only used for prefilled sheafs */
  struct {
   unsigned int capacity;
   bool pfmemalloc;
  };
 };
 struct kmem_cache *cache;
 unsigned int size;
 int node; /* only used for rcu_sheaf */
 void *objects[];
};

slab_sheaves layout

  • struct slab_sheaf *main : full; default sheaf. alloc/free fastpath hits this first.
  • struct slab_sheaf *spare : partially filled; swapped in when main empties
  • struct slab_sheaf *rcu_free : collects kfree_rcu objects, batch-freed after grace period
  • void *objects[] : points to an object in some slab held by sheaf (“held by sheaf” state, NOT in slab.freelist)
  • one slub_percpu_sheaves per logical CPU, per kmem_cache , 16 logical CPUs × 200 caches = 3200 sheaf-sets in the system.
    image

kmem_cache_node

https://elixir.bootlin.com/linux/v7.0/source/mm/slub.c#L430

1
2
3
4
5
6
7
8
9
10
11
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
 struct node_barn *barn;
};

slab

struct slab used to manage a single slab

a single slab contains multiple objects based on the object size and page size allocated by buddy allocator

example: allocated one 0x1000 size page from buddy allocator and the object size is 0x100 then theres 0x10 objects in the slab

https://elixir.bootlin.com/linux/v7.0/source/mm/slab.h#L74

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
struct slab {
 memdesc_flags_t flags;

 struct kmem_cache *slab_cache;
 union {
  struct {
   struct list_head slab_list;
   /* Double-word boundary */
   struct freelist_counters;
  };
  struct rcu_head rcu_head;
 };

 unsigned int __page_type;
 atomic_t __page_refcount;
#ifdef CONFIG_SLAB_OBJ_EXT
 unsigned long obj_exts;
#endif
};

node_barn

https://elixir.bootlin.com/linux/v7.0.10/source/mm/slub.c#L396

1
2
3
4
5
6
7
struct node_barn {
 spinlock_t lock;
 struct list_head sheaves_full;
 struct list_head sheaves_empty;
 unsigned int nr_full;
 unsigned int nr_empty;
};

kmem_cache_node slabs/node barns layout

image

full layout

image

Allocation

Allocation flow overview

image

  • API layer : kmem_cache_alloc() / kmalloc() , only pick which kmem_cache to use
  • Fastpath : alloc_from_pcs() , pop one object from the percpu sheaf . no lock on the node
  • Slowpath : ___slab_alloc() , go to the node partial list , then to the buddy allocator

Type of allocation API

kmem_cache_alloc()

used to allocate specific type of cache
https://elixir.bootlin.com/linux/v7.0/source/include/linux/slab.h#L768

1
#define kmem_cache_alloc(...)   alloc_hooks(kmem_cache_alloc_noprof(__VA_ARGS__))

https://elixir.bootlin.com/linux/v7.0/source/mm/slub.c#L4871

1
2
3
4
5
6
7
8
9
void *kmem_cache_alloc_noprof(struct kmem_cache *s, gfp_t gfpflags)
{
 void *ret = slab_alloc_node(s, NULL, gfpflags, NUMA_NO_NODE, _RET_IP_,
        s->object_size);

 trace_kmem_cache_alloc(_RET_IP_, ret, s, gfpflags, NUMA_NO_NODE);

 return ret;
}

example:
image

kmalloc()

allocate from generic slab cache (kmalloc-8, kmalloc-16, … kmalloc-8k).
image

the kernel picks the right kmem_cache based on size and gfpflags

https://elixir.bootlin.com/linux/v7.0/source/include/linux/slab.h#L956

1
#define kmalloc(...)    alloc_hooks(kmalloc_noprof(__VA_ARGS__))

https://elixir.bootlin.com/linux/v7.0/source/include/linux/slab.h#L941

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
static __always_inline __alloc_size(1) void *kmalloc_noprof(size_t size, gfp_t flags)
{
 if (__builtin_constant_p(size) && size) {
  unsigned int index;

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

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

https://elixir.bootlin.com/linux/v7.0/source/mm/slub.c#L5373

1
2
3
4
5
6
7
8
9
10
void *__kmalloc_cache_noprof(struct kmem_cache *s, gfp_t gfpflags, size_t size)
{
 void *ret = slab_alloc_node(s, NULL, gfpflags, NUMA_NO_NODE,
         _RET_IP_, size);

 trace_kmalloc(_RET_IP_, ret, size, s->size, gfpflags, NUMA_NO_NODE);

 ret = kasan_kmalloc(s, ret, size, gfpflags);
 return ret;
}

Entrypoint

the API mentioned above just to decide which slab cache to allocate and will always call the slab_alloc_node() in the end which is the actual entrypoint of the slab allocator

slab_alloc_node()

https://elixir.bootlin.com/linux/v7.0/source/mm/slub.c#L4837

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
static __fastpath_inline void *slab_alloc_node(struct kmem_cache *s, struct list_lru *lru,
  gfp_t gfpflags, int node, unsigned long addr, size_t orig_size)
{
 void *object;
 bool init = false;

 s = slab_pre_alloc_hook(s, gfpflags);
 if (unlikely(!s))
  return NULL;

 object = kfence_alloc(s, orig_size, gfpflags);
 if (unlikely(object))
  goto out;

 object = alloc_from_pcs(s, gfpflags, node);

 if (!object)
  object = __slab_alloc_node(s, gfpflags, node, addr, orig_size);

 maybe_wipe_obj_freeptr(s, object);
 init = slab_want_init_on_alloc(gfpflags, s);

out:
 /*
  * When init equals 'true', like for kzalloc() family, only
  * @orig_size bytes might be zeroed instead of s->object_size
  * In case this fails due to memcg_slab_post_alloc_hook(),
  * object is set to NULL
  */
 slab_post_alloc_hook(s, lru, gfpflags, 1, &object, init, orig_size);

 return object;
}
  • alloc_from_pcs(), the Fastpath
  • __slab_alloc_node() , the Slowpath, if Fastpath return null

Fastpath

alloc_from_pcs()

https://elixir.bootlin.com/linux/v7.0/source/mm/slub.c#L4671

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
static __fastpath_inline
void *alloc_from_pcs(struct kmem_cache *s, gfp_t gfp, int node)
{
 struct slub_percpu_sheaves *pcs;
 bool node_requested;
 void *object;

#ifdef CONFIG_NUMA
 if (static_branch_unlikely(&strict_numa) &&
    node == NUMA_NO_NODE) {

  struct mempolicy *mpol = current->mempolicy;

  if (mpol) {
   /*
    * Special BIND rule support. If the local node
    * is in permitted set then do not redirect
    * to a particular node.
    * Otherwise we apply the memory policy to get
    * the node we need to allocate on.
    */
   if (mpol->mode != MPOL_BIND ||
     !node_isset(numa_mem_id(), mpol->nodes))

    node = mempolicy_slab_node();
  }
 }
#endif

 node_requested = IS_ENABLED(CONFIG_NUMA) && node != NUMA_NO_NODE;

 /*
  * We assume the percpu sheaves contain only local objects although it's
  * not completely guaranteed, so we verify later.
  */
 if (unlikely(node_requested && node != numa_mem_id())) {
  stat(s, ALLOC_NODE_MISMATCH);
  return NULL;
 }

 if (!local_trylock(&s->cpu_sheaves->lock))
  return NULL;

 pcs = this_cpu_ptr(s->cpu_sheaves);

 if (unlikely(pcs->main->size == 0)) {
  pcs = __pcs_replace_empty_main(s, pcs, gfp);
  if (unlikely(!pcs))
   return NULL;
 }

 object = pcs->main->objects[pcs->main->size - 1];

 if (unlikely(node_requested)) {
  /*
   * Verify that the object was from the node we want. This could
   * be false because of cpu migration during an unlocked part of
   * the current allocation or previous freeing process.
   */
  if (page_to_nid(virt_to_page(object)) != node) {
   local_unlock(&s->cpu_sheaves->lock);
   stat(s, ALLOC_NODE_MISMATCH);
   return NULL;
  }
 }

 pcs->main->size--;

 local_unlock(&s->cpu_sheaves->lock);

 stat(s, ALLOC_FASTPATH);

 return object;
}

the core behavior of alloc_from_pcs() is basically 3 lines

took the cpu_sheaves from provided slab cache

1
pcs = this_cpu_ptr(s->cpu_sheaves);

the objects[] is a LIFO pointer array(like stack)
it pop the pointer from top of the array
the size control the index of array

1
object = pcs->main->objects[pcs->main->size - 1];

decrease index

1
pcs->main->size--;

image

but if the main sheaf is empty the it will try refill with __pcs_replace_empty_main()

when main is empty : __pcs_replace_empty_main()

https://elixir.bootlin.com/linux/v7.0/source/mm/slub.c#L4560

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
static struct slub_percpu_sheaves *
__pcs_replace_empty_main(struct kmem_cache *s, struct slub_percpu_sheaves *pcs, gfp_t gfp)
{
 struct slab_sheaf *empty = NULL;
 struct slab_sheaf *full;
 struct node_barn *barn;
 bool allow_spin;

 lockdep_assert_held(this_cpu_ptr(&s->cpu_sheaves->lock));

 /* Bootstrap or debug cache, back off */
 if (unlikely(!cache_has_sheaves(s))) {
  local_unlock(&s->cpu_sheaves->lock);
  return NULL;
 }

 if (pcs->spare && pcs->spare->size > 0) {
  swap(pcs->main, pcs->spare);
  return pcs;
 }

 barn = get_barn(s);
 if (!barn) {
  local_unlock(&s->cpu_sheaves->lock);
  return NULL;
 }

 allow_spin = gfpflags_allow_spinning(gfp);

 full = barn_replace_empty_sheaf(barn, pcs->main, allow_spin);

 if (full) {
  stat(s, BARN_GET);
  pcs->main = full;
  return pcs;
 }

 stat(s, BARN_GET_FAIL);

 if (allow_spin) {
  if (pcs->spare) {
   empty = pcs->spare;
   pcs->spare = NULL;
  } else {
   empty = barn_get_empty_sheaf(barn, true);
  }
 }

 local_unlock(&s->cpu_sheaves->lock);
 pcs = NULL;

 if (!allow_spin)
  return NULL;

 if (empty) {
  if (!refill_sheaf(s, empty, gfp | __GFP_NOMEMALLOC | __GFP_NOWARN)) {
   full = empty;
  } else {
   /*
    * we must be very low on memory so don't bother
    * with the barn
    */
   sheaf_flush_unused(s, empty);
   free_empty_sheaf(s, empty);
  }
 } else {
  full = alloc_full_sheaf(s, gfp);
 }

 if (!full)
  return NULL;

 if (!local_trylock(&s->cpu_sheaves->lock))
  goto barn_put;
 pcs = this_cpu_ptr(s->cpu_sheaves);

 /*
  * If we are returning empty sheaf, we either got it from the
  * barn or had to allocate one. If we are returning a full
  * sheaf, it's due to racing or being migrated to a different
  * cpu. Breaching the barn's sheaf limits should be thus rare
  * enough so just ignore them to simplify the recovery.
  */

 if (pcs->main->size == 0) {
  if (!pcs->spare)
   pcs->spare = pcs->main;
  else
   barn_put_empty_sheaf(barn, pcs->main);
  pcs->main = full;
  return pcs;
 }

 if (!pcs->spare) {
  pcs->spare = full;
  return pcs;
 }

 if (pcs->spare->size == 0) {
  barn_put_empty_sheaf(barn, pcs->spare);
  pcs->spare = full;
  return pcs;
 }

barn_put:
 barn_put_full_sheaf(barn, full);
 stat(s, BARN_PUT);

 return pcs;
}
  • its job is to get a non-empty main sheaf back
  1. when spare sheaf isnt empty it will swap(pcs->main, pcs->spare) which is swapping the spare sheaf with main sheaf
  2. if the spare sheaf is empty too
    it will try barn_replace_empty_sheaf(barn, pcs->main, allow_spin) to get full sheaf from barn
  3. refill an empty sheaf
    take spare or barn_get_empty_sheaf() and refill_sheaf() it from the node partial lists / buddy
  4. alloc_full_sheaf(), when theres no empty sheaf around , allocate a new sheaf struct and refill it

refill_sheaf()

when both spare or the barn only have empty sheaves
it will call this function to refill them from node partial lists/buddy

it also count as another entry of slowpath since it refill from node partial lists/buddy

https://elixir.bootlin.com/linux/v7.0/source/mm/slub.c#L2803

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
static int refill_sheaf(struct kmem_cache *s, struct slab_sheaf *sheaf,
    gfp_t gfp)
{
 int to_fill = s->sheaf_capacity - sheaf->size;
 int filled;

 if (!to_fill)
  return 0;

 filled = refill_objects(s, &sheaf->objects[sheaf->size], gfp, to_fill,
    to_fill);

 sheaf->size += filled;

 stat_add(s, SHEAF_REFILL, filled);

 if (filled < to_fill)
  return -ENOMEM;

 return 0;
}

it calculate how many objects needed to fill then pass it to refill_objects()

refill_objects()

https://elixir.bootlin.com/linux/v7.0/source/mm/slub.c#L7151

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
static unsigned int
refill_objects(struct kmem_cache *s, void **p, gfp_t gfp, unsigned int min,
        unsigned int max)
{
 int local_node = numa_mem_id();
 unsigned int refilled;
 struct slab *slab;

 if (WARN_ON_ONCE(!gfpflags_allow_spinning(gfp)))
  return 0;

 refilled = __refill_objects_node(s, p, gfp, min, max,
      get_node(s, local_node),
      /* allow_spin = */ true);
 if (refilled >= min)
  return refilled;

 refilled += __refill_objects_any(s, p + refilled, gfp, min - refilled,
      max - refilled);
 if (refilled >= min)
  return refilled;

new_slab:

 slab = new_slab(s, gfp, local_node);
 if (!slab)
  goto out;

 stat(s, ALLOC_SLAB);

 /*
  * TODO: possible optimization - if we know we will consume the whole
  * slab we might skip creating the freelist?
  */
 refilled += alloc_from_new_slab(s, slab, p + refilled, max - refilled,
     /* allow_spin = */ true);

 if (refilled < min)
  goto new_slab;

out:
 return refilled;
}

try order: local node partial -> remote node partial -> buddy , in a loop until min is reached

Slowpath

happened when alloc_from_pcs() failed

__slab_alloc_node()

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
static __always_inline void *__slab_alloc_node(struct kmem_cache *s,
  gfp_t gfpflags, int node, unsigned long addr, size_t orig_size)
{
 void *object;

#ifdef CONFIG_NUMA
 if (static_branch_unlikely(&strict_numa) &&
   node == NUMA_NO_NODE) {

  struct mempolicy *mpol = current->mempolicy;

  if (mpol) {
   /*
    * Special BIND rule support. If the local node
    * is in permitted set then do not redirect
    * to a particular node.
    * Otherwise we apply the memory policy to get
    * the node we need to allocate on.
    */
   if (mpol->mode != MPOL_BIND ||
     !node_isset(numa_mem_id(), mpol->nodes))
    node = mempolicy_slab_node();
  }
 }
#endif

 object = ___slab_alloc(s, gfpflags, node, addr, orig_size);

 return object;
}

pretty much just to call ___slab_alloc()

___slab_alloc()

https://elixir.bootlin.com/linux/v7.0/source/mm/slub.c#L4374

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
static void *___slab_alloc(struct kmem_cache *s, gfp_t gfpflags, int node,
      unsigned long addr, unsigned int orig_size)
{
 bool allow_spin = gfpflags_allow_spinning(gfpflags);
 void *object;
 struct slab *slab;
 struct partial_context pc;
 bool try_thisnode = true;

 stat(s, ALLOC_SLOWPATH);

new_objects:

 pc.flags = gfpflags;
 /*
  * When a preferred node is indicated but no __GFP_THISNODE
  *
  * 1) try to get a partial slab from target node only by having
  *    __GFP_THISNODE in pc.flags for get_from_partial()
  * 2) if 1) failed, try to allocate a new slab from target node with
  *    GPF_NOWAIT | __GFP_THISNODE opportunistically
  * 3) if 2) failed, retry with original gfpflags which will allow
  *    get_from_partial() try partial lists of other nodes before
  *    potentially allocating new page from other nodes
  */
 if (unlikely(node != NUMA_NO_NODE && !(gfpflags & __GFP_THISNODE)
       && try_thisnode)) {
  if (unlikely(!allow_spin))
   /* Do not upgrade gfp to NOWAIT from more restrictive mode */
   pc.flags = gfpflags | __GFP_THISNODE;
  else
   pc.flags = GFP_NOWAIT | __GFP_THISNODE;
 }

 pc.orig_size = orig_size;
 object = get_from_partial(s, node, &pc);
 if (object)
  goto success;

 slab = new_slab(s, pc.flags, node);

 if (unlikely(!slab)) {
  if (node != NUMA_NO_NODE && !(gfpflags & __GFP_THISNODE)
      && try_thisnode) {
   try_thisnode = false;
   goto new_objects;
  }
  slab_out_of_memory(s, gfpflags, node);
  return NULL;
 }

 stat(s, ALLOC_SLAB);

 if (IS_ENABLED(CONFIG_SLUB_TINY) || kmem_cache_debug(s)) {
  object = alloc_single_from_new_slab(s, slab, orig_size, gfpflags);

  if (likely(object))
   goto success;
 } else {
  alloc_from_new_slab(s, slab, &object, 1, allow_spin);

  /* we don't need to check SLAB_STORE_USER here */
  if (likely(object))
   return object;
 }

 if (allow_spin)
  goto new_objects;

 /* This could cause an endless loop. Fail instead. */
 return NULL;

success:
 if (kmem_cache_debug_flags(s, SLAB_STORE_USER))
  set_track(s, object, TRACK_ALLOC, addr, gfpflags);

 return object;
}
  1. get_from_partial() , take one object from a partial slab
  2. new_slab() , get a new slab from buddy allocator if get_from_partial() failed
  3. after new_slab() it call alloc_from_new_slab()
    to take the first object out of it

get_from_partial()

https://elixir.bootlin.com/linux/v7.0/source/mm/slub.c#L3926

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*
 * Get an object from a partial slab
 */
static void *get_from_partial(struct kmem_cache *s, int node,
         struct partial_context *pc)
{
 int searchnode = node;
 void *object;

 if (node == NUMA_NO_NODE)
  searchnode = numa_mem_id();

 object = get_from_partial_node(s, get_node(s, searchnode), pc);
 if (object || (node != NUMA_NO_NODE && (pc->flags & __GFP_THISNODE)))
  return object;

 return get_from_any_partial(s, pc);
}

try local node partial list get_from_partial_node() first
if get_from_partial_node() failed it will try remote nodes get_from_any_partial()

get_from_partial_node()

https://elixir.bootlin.com/linux/v7.0/source/mm/slub.c#L3789

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
52
53
54
55
56
57
58
59
60
61
62
63
/*
 * Try to allocate object from a partial slab on a specific node.
 */
static void *get_from_partial_node(struct kmem_cache *s,
       struct kmem_cache_node *n,
       struct partial_context *pc)
{
 struct slab *slab, *slab2;
 unsigned long flags;
 void *object = NULL;

 /*
  * Racy check. If we mistakenly see no partial slabs then we
  * just allocate an empty slab. If we mistakenly try to get a
  * partial slab and there is none available then get_from_partial()
  * will return NULL.
  */
 if (!n || !n->nr_partial)
  return NULL;

 if (gfpflags_allow_spinning(pc->flags))
  spin_lock_irqsave(&n->list_lock, flags);
 else if (!spin_trylock_irqsave(&n->list_lock, flags))
  return NULL;
 list_for_each_entry_safe(slab, slab2, &n->partial, slab_list) {

  struct freelist_counters old, new;

  if (!pfmemalloc_match(slab, pc->flags))
   continue;

  if (IS_ENABLED(CONFIG_SLUB_TINY) || kmem_cache_debug(s)) {
   object = alloc_single_from_partial(s, n, slab,
       pc->orig_size);
   if (object)
    break;
   continue;
  }

  /*
   * get a single object from the slab. This might race against
   * __slab_free(), which however has to take the list_lock if
   * it's about to make the slab fully free.
   */
  do {
   old.freelist = slab->freelist;
   old.counters = slab->counters;

   new.freelist = get_freepointer(s, old.freelist);
   new.counters = old.counters;
   new.inuse++;

  } while (!__slab_update_freelist(s, slab, &old, &new, "get_from_partial_node"));

  object = old.freelist;
  if (!new.freelist)
   remove_partial(n, slab);

  break;
 }
 spin_unlock_irqrestore(&n->list_lock, flags);
 return object;
}

pop slab->freelist once with cmpxchg on freelist and counters
usually CONFIG_SLAB_FREELIST_HARDENED is on so the freelist pointer will get encoded so it use get_freepointer() to take the free pointer

image

Summarize

image

Free

Free flow overview

image

  • API layer : kmem_cache_free() / kfree() find which kmem_cache the object belongs to
  • fastpath : free_to_pcs() push the object pointer into the percpu sheaf
  • slowpath : __slab_free() , put the object back on slab->freelist

Type of free API

kmem_cache_free()

free an object back to a specific cache

https://elixir.bootlin.com/linux/v7.0/source/mm/slub.c#L6275

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void kmem_cache_free(struct kmem_cache *s, void *x)
{
 struct slab *slab;

 slab = virt_to_slab(x);

 if (IS_ENABLED(CONFIG_SLAB_FREELIST_HARDENED) ||
     kmem_cache_debug_flags(s, SLAB_CONSISTENCY_CHECKS)) {

  /*
   * Intentionally leak the object in these cases, because it
   * would be too dangerous to continue.
   */
  if (unlikely(!slab || (slab->slab_cache != s))) {
   warn_free_bad_obj(s, x);
   return;
  }
 }

 trace_kmem_cache_free(_RET_IP_, x, s);
 slab_free(s, slab, x, _RET_IP_);
}
EXPORT_SYMBOL(kmem_cache_free);

kfree()

free generic slab cache (kmalloc-8, kmalloc-16, … kmalloc-8k).

https://elixir.bootlin.com/linux/v7.0/source/mm/slub.c#L6462

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void kfree(const void *object)
{
 struct page *page;
 struct slab *slab;
 struct kmem_cache *s;
 void *x = (void *)object;

 trace_kfree(_RET_IP_, object);

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

 page = virt_to_page(object);
 slab = page_slab(page);
 if (!slab) {
  /* kmalloc_nolock() doesn't support large kmalloc */
  free_large_kmalloc(page, (void *)object);
  return;
 }

 s = slab->slab_cache;
 slab_free(s, slab, x, _RET_IP_);
}
EXPORT_SYMBOL(kfree);

first calculate object located at what page
convert it to slab struct, the page and slab struct use the same memory just like union
after converted to slab
it use slab->slab_cache to know which kmem_cache this object from

Entrypoint

above APIs end in slab_free() the entry of slub allocator

slab_free()

https://elixir.bootlin.com/linux/v7.0/source/mm/slub.c#L6158

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
static __fastpath_inline
void slab_free(struct kmem_cache *s, struct slab *slab, void *object,
        unsigned long addr)
{
 memcg_slab_free_hook(s, slab, &object, 1);
 alloc_tagging_slab_free_hook(s, slab, &object, 1);

 if (unlikely(!slab_free_hook(s, object, slab_want_init_on_free(s), false)))
  return;

 if (likely(!IS_ENABLED(CONFIG_NUMA) || slab_nid(slab) == numa_mem_id())
     && likely(!slab_test_pfmemalloc(slab))) {
  if (likely(free_to_pcs(s, object, true)))
   return;
 }

 __slab_free(s, slab, object, object, 1, addr);
 stat(s, FREE_SLOWPATH);
}
  • free_to_pcs(), the Fastpath
  • __slab_free , the Slowpath, if fastpath return null

Fastpath

free_to_pcs()

https://elixir.bootlin.com/linux/v7.0/source/mm/slub.c#L5763

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
static __fastpath_inline
bool free_to_pcs(struct kmem_cache *s, void *object, bool allow_spin)
{
 struct slub_percpu_sheaves *pcs;

 if (!local_trylock(&s->cpu_sheaves->lock))
  return false;

 pcs = this_cpu_ptr(s->cpu_sheaves);

 if (unlikely(pcs->main->size == s->sheaf_capacity)) {

  pcs = __pcs_replace_full_main(s, pcs, allow_spin);
  if (unlikely(!pcs))
   return false;
 }

 pcs->main->objects[pcs->main->size++] = object;

 local_unlock(&s->cpu_sheaves->lock);

 stat(s, FREE_FASTPATH);

 return true;
}

the core of fastpath just 1 line:
push the object to main sheaf

1
pcs->main->objects[pcs->main->size++] = object;

when main is full : __pcs_replace_full_main()

https://elixir.bootlin.com/linux/v7.0/source/mm/slub.c#L5640

basically the opposite of __pcs_replace_empty_main()

Slowpath

__slab_free()

https://elixir.bootlin.com/linux/v7.0/source/mm/slub.c#L5470

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
/*
 * 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)

{
 bool was_full;
 struct freelist_counters old, new;
 struct kmem_cache_node *n = NULL;
 unsigned long flags;
 bool on_node_partial;

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

  old.freelist = slab->freelist;
  old.counters = slab->counters;

  was_full = (old.freelist == NULL);

  set_freepointer(s, tail, old.freelist);

  new.freelist = head;
  new.counters = old.counters;
  new.inuse -= cnt;

  /*
   * Might need to be taken off (due to becoming empty) or added
   * to (due to not being full anymore) the partial list.
   * Unless it's frozen.
   */
  if (!new.inuse || was_full) {

   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, &old, &new, "__slab_free"));

 if (likely(!n)) {
  /*
   * We didn't take the list_lock because the slab was already on
   * the partial list and will remain there.
   */
  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 (!was_full && !on_node_partial) {
  spin_unlock_irqrestore(&n->list_lock, flags);
  return;
 }

 /*
  * If slab became empty, should we add/keep it on the partial list or we
  * have enough?
  */
 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 (unlikely(was_full)) {
  add_partial(n, slab, ADD_TO_TAIL);
  stat(s, FREE_ADD_PARTIAL);
 }
 spin_unlock_irqrestore(&n->list_lock, flags);
 return;

slab_empty:
 /*
  * The slab could have a single object and thus go from full to empty in
  * a single free, but more likely it was on the partial list. Remove it.
  */
 if (likely(!was_full)) {
  remove_partial(n, slab);
  stat(s, FREE_REMOVE_PARTIAL);
 }

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

the core:

1
2
3
set_freepointer(s, tail, old.freelist);   /* object's FP <- old head */
new.freelist = head;                      /* slab->freelist <- object */
new.inuse -= cnt;

just set the FP of object to current slab freelist head address
and set the current slab freelist head to the object we are freeing
image

after the object freed into the slab
it will check the current slab status:

  • still partial: just return normally
  • from full to partial:
    call add_partial(n, slab, ADD_TO_TAIL) to add the slab to partial slab list
  • from empty to partial:
    call remove_partial(n, slab); to remove it from partial slab list
    secondly call discard_slab(s, slab); return the slab back to buddy allocator

Summarize

image

Afterall

after the change of linux kernel 7.0 slub allocator
the performance in general showing an improvement, but with specific cases showing worse performance

but theres some worth mentioning security issue:
the CONFIG_SLAB_FREELIST_HARDENED and CONFIG_SLAB_FREELIST_RANDOM mitgations does not apply to sheaf layer also it wont check double free or memory corruption while freeing in sheaf layer and more issues…

References

https://slavin.cn/2024/05/06/Slub-allocator-%E5%88%86%E6%9E%90/
https://fosdem.org/2026/events/attachments/DPXVYJ-slub-sheaves-update/slides/267397/fosdem-sh_pvi6fpf.pdf
https://elixir.bootlin.com/linux/v7.0/source/mm/slub.c
https://elixir.bootlin.com/linux/v7.0/source/include/linux/slab.h
https://naup.mygo.tw/2026/08/22/Harvest-Season-For-Slub/