* [PATCH RFC v3 0/8] SLUB percpu sheaves
@ 2025-03-17 14:33 Vlastimil Babka
2025-03-17 14:33 ` [PATCH RFC v3 1/8] locking/local_lock: Introduce localtry_lock_t Vlastimil Babka
` (7 more replies)
0 siblings, 8 replies; 20+ messages in thread
From: Vlastimil Babka @ 2025-03-17 14:33 UTC (permalink / raw)
To: Suren Baghdasaryan, Liam R. Howlett, Christoph Lameter, David Rientjes
Cc: Roman Gushchin, Harry Yoo, Uladzislau Rezki, linux-mm,
linux-kernel, rcu, maple-tree, vbabka, Sebastian Andrzej Siewior,
Davidlohr Bueso, Alexei Starovoitov, Liam R. Howlett
Hi,
This is the v3 RFC to add an opt-in percpu array-based caching layer to
SLUB. This is to publish accumulated fixes since v2 ahead of LSF/MM. I
have also squashed the usage of localtry_lock to be used immediately
(not converted to in a separate patch) as the lock should be going to
6.15 at this point. There's still a patch introducing it for this RFC to
avoid depending on bpf-next tree.
The name "sheaf" was invented by Matthew so we don't call it magazine
like the original Bonwick paper. The per-NUMA-node cache of sheaves is
thus called "barn".
This may seem similar to the arrays in SLAB, but the main differences
are:
- opt-in, not used for every cache
- does not distinguish NUMA locality, thus no "shared" arrays and no
"alien" arrays that would need periodical flushing
- improves kfree_rcu() handling
- API for obtaining a preallocated sheaf that can be used for guaranteed
and efficient allocations in a restricted context, when the upper
bound for needed objects is known but rarely reached
The motivation comes mainly from the ongoing work related to VMA
scalability and the related maple tree operations. This is why maple
tree nodes are sheaf-enabled in the RFC, but it's not a full conversion
that would take benefits of the improved preallocation API. The VMA part
is currently left out as it's expected that Suren will land the VMA
TYPESAFE_BY_RCU conversion [3] soon and there would be conflict with that.
With both series applied it means just adding a line to kmem_cache_args
in proc_caches_init().
Some performance benefits were measured by Suren and Liam in previous
versions. Suren's results in [5] look promising, so far except for the
preallocation support as used by the refactored maple tree code.
A sheaf-enabled cache has the following expected advantages:
- Cheaper fast paths. For allocations, instead of local double cmpxchg,
after Patch 5 it's preempt_disable() and no atomic operations. Same for
freeing, which is normally a local double cmpxchg only for a short
term allocations (so the same slab is still active on the same cpu when
freeing the object) and a more costly locked double cmpxchg otherwise.
The downside is the lack of NUMA locality guarantees for the allocated
objects.
- kfree_rcu() batching and recycling. kfree_rcu() will put objects to a
separate percpu sheaf and only submit the whole sheaf to call_rcu()
when full. After the grace period, the sheaf can be used for
allocations, which is more efficient than freeing and reallocating
individual slab objects (even with the batching done by kfree_rcu()
implementation itself). In case only some cpus are allowed to handle rcu
callbacks, the sheaf can still be made available to other cpus on the
same node via the shared barn. The maple_node cache uses kfree_rcu() and
thus can benefit from this.
- Preallocation support. A prefilled sheaf can be privately borrowed for
a short term operation that is not allowed to block in the middle and
may need to allocate some objects. If an upper bound (worst case) for
the number of allocations is known, but only much fewer allocations
actually needed on average, borrowing and returning a sheaf is much more
efficient then a bulk allocation for the worst case followed by a bulk
free of the many unused objects. Maple tree write operations should
benefit from this.
Patch 1 is copied from the series "bpf, mm: Introduce try_alloc_pages()"
[2] to introduce a variant of local_lock that has a trylock operation.
Patch 2 implements the basic sheaf functionality as a caching layer on
top of (per-cpu) slabs.
Patch 3 adds the sheaf kfree_rcu() support.
Patch 4 implements borrowing prefilled sheaves, with maple tree being the
ancticipated user.
Patch 5 seeks to reduce barn spinlock contention. Separately for
possible evaluation.
Patches 6 and 7 by Liam add testing stubs that maple tree will use in
its userspace tests.
Patch 9 enables sheaves for the maple tree node cache, but does not
take advantage of prefilling yet.
(RFC) LIMITATIONS:
- with slub_debug enabled, objects in sheaves are considered allocated
so allocation/free stacktraces may become imprecise and checking of
e.g. redzone violations may be delayed
GIT TREES:
this series: https://git.kernel.org/vbabka/l/slub-percpu-sheaves-v3
To avoid conflicts, the series requires (and the branch above is based
on) the kfree_rcu() code refactoring scheduled for 6.15:
https://git.kernel.org/pub/scm/linux/kernel/git/vbabka/slab.git/log/?h=slab/for-6.15/kfree_rcu_tiny
Vlastimil
[1] https://lore.kernel.org/all/20241111205506.3404479-1-surenb@google.com/
[2] https://lore.kernel.org/all/20250222024427.30294-2-alexei.starovoitov@gmail.com/
[3] https://lore.kernel.org/all/20250213224655.1680278-1-surenb@google.com/
[4] https://www.infradead.org/git/?p=users/jedix/linux-maple.git;a=shortlog;h=refs/heads/slub-percpu-sheaves-v2
[5] https://lore.kernel.org/all/CAJuCfpFVopL%2BsMdU4bLRxs%2BHS_WPCmFZBdCmwE8qV2Dpa5WZnA@mail.gmail.com/
---
Changes in v3:
- Squash localtry_lock conversion so it's used immediately.
- Incorporate feedback and add tags from Suren and Harry - thanks!
- Mostly adding comments and some refactoring.
- Fixes for kfree_rcu_sheaf() vmalloc handling, cpu hotremove
flushing.
- Fix wrong condition in kmem_cache_return_sheaf() that may have
affected performance negatively.
- Refactoring of free_to_pcs()
- Link to v2: https://lore.kernel.org/r/20250214-slub-percpu-caches-v2-0-88592ee0966a@suse.cz
Changes in v2:
- Removed kfree_rcu() destructors support as VMAs will not need it
anymore after [3] is merged.
- Changed to localtry_lock_t borrowed from [2] instead of an own
implementation of the same idea.
- Many fixes and improvements thanks to Liam's adoption for maple tree
nodes.
- Userspace Testing stubs by Liam.
- Reduced limitations/todos - hooking to kfree_rcu() is complete,
prefilled sheaves can exceed cache's sheaf_capacity.
- Link to v1: https://lore.kernel.org/r/20241112-slub-percpu-caches-v1-0-ddc0bdc27e05@suse.cz
---
Liam R. Howlett (2):
tools: Add testing support for changes to rcu and slab for sheaves
tools: Add sheafs support to testing infrastructure
Sebastian Andrzej Siewior (1):
locking/local_lock: Introduce localtry_lock_t
Vlastimil Babka (5):
slab: add opt-in caching layer of percpu sheaves
slab: add sheaf support for batching kfree_rcu() operations
slab: sheaf prefilling for guaranteed allocations
slab: determine barn status racily outside of lock
maple_tree: use percpu sheaves for maple_node_cache
include/linux/local_lock.h | 70 ++
include/linux/local_lock_internal.h | 146 ++++
include/linux/slab.h | 50 ++
lib/maple_tree.c | 11 +-
mm/slab.h | 4 +
mm/slab_common.c | 29 +-
mm/slub.c | 1463 +++++++++++++++++++++++++++++++--
tools/include/linux/slab.h | 65 +-
tools/testing/shared/linux.c | 108 ++-
tools/testing/shared/linux/rcupdate.h | 22 +
10 files changed, 1891 insertions(+), 77 deletions(-)
---
base-commit: 379487e17ca406b47392e7ab6cf35d1c3bacb371
change-id: 20231128-slub-percpu-caches-9441892011d7
prerequisite-message-id: 20250203-slub-tiny-kfree_rcu-v1-0-d4428bf9a8a1@suse.cz
prerequisite-patch-id: 1a4af92b5eb1b8bfc86bac8d7fc1ef0963e7d9d6
prerequisite-patch-id: f24a39c38103b7e09fbf2e6f84e6108499ab7980
prerequisite-patch-id: 23e90b23482f4775c95295821dd779ba4e3712e9
prerequisite-patch-id: 5c53a619477acdce07071abec0f40e79501ea40b
Best regards,
--
Vlastimil Babka <vbabka@suse.cz>
^ permalink raw reply [flat|nested] 20+ messages in thread
* [PATCH RFC v3 1/8] locking/local_lock: Introduce localtry_lock_t
2025-03-17 14:33 [PATCH RFC v3 0/8] SLUB percpu sheaves Vlastimil Babka
@ 2025-03-17 14:33 ` Vlastimil Babka
2025-03-17 14:33 ` [PATCH RFC v3 2/8] slab: add opt-in caching layer of percpu sheaves Vlastimil Babka
` (6 subsequent siblings)
7 siblings, 0 replies; 20+ messages in thread
From: Vlastimil Babka @ 2025-03-17 14:33 UTC (permalink / raw)
To: Suren Baghdasaryan, Liam R. Howlett, Christoph Lameter, David Rientjes
Cc: Roman Gushchin, Harry Yoo, Uladzislau Rezki, linux-mm,
linux-kernel, rcu, maple-tree, vbabka, Sebastian Andrzej Siewior,
Davidlohr Bueso, Alexei Starovoitov
From: Sebastian Andrzej Siewior <bigeasy@linutronix.de>
In !PREEMPT_RT local_lock_irqsave() disables interrupts to protect
critical section, but it doesn't prevent NMI, so the fully reentrant
code cannot use local_lock_irqsave() for exclusive access.
Introduce localtry_lock_t and localtry_lock_irqsave() that
disables interrupts and sets acquired=1, so localtry_lock_irqsave()
from NMI attempting to acquire the same lock will return false.
In PREEMPT_RT local_lock_irqsave() maps to preemptible spin_lock().
Map localtry_lock_irqsave() to preemptible spin_trylock().
When in hard IRQ or NMI return false right away, since
spin_trylock() is not safe due to explicit locking in the underneath
rt_spin_trylock() implementation. Removing this explicit locking and
attempting only "trylock" is undesired due to PI implications.
Note there is no need to use local_inc for acquired variable,
since it's a percpu variable with strict nesting scopes.
Acked-by: Davidlohr Bueso <dave@stgolabs.net>
Signed-off-by: Sebastian Andrzej Siewior <bigeasy@linutronix.de>
Signed-off-by: Vlastimil Babka <vbabka@suse.cz>
Link: https://lore.kernel.org/r/20250222024427.30294-2-alexei.starovoitov@gmail.com
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
include/linux/local_lock.h | 70 +++++++++++++++++
include/linux/local_lock_internal.h | 146 ++++++++++++++++++++++++++++++++++++
2 files changed, 216 insertions(+)
diff --git a/include/linux/local_lock.h b/include/linux/local_lock.h
index 091dc0b6bdfb9f4721f94d19828a38fbfa59346c..1a0bc35839e360d5c8170105849c3883463852f8 100644
--- a/include/linux/local_lock.h
+++ b/include/linux/local_lock.h
@@ -51,6 +51,76 @@
#define local_unlock_irqrestore(lock, flags) \
__local_unlock_irqrestore(lock, flags)
+/**
+ * localtry_lock_init - Runtime initialize a lock instance
+ */
+#define localtry_lock_init(lock) __localtry_lock_init(lock)
+
+/**
+ * localtry_lock - Acquire a per CPU local lock
+ * @lock: The lock variable
+ */
+#define localtry_lock(lock) __localtry_lock(lock)
+
+/**
+ * localtry_lock_irq - Acquire a per CPU local lock and disable interrupts
+ * @lock: The lock variable
+ */
+#define localtry_lock_irq(lock) __localtry_lock_irq(lock)
+
+/**
+ * localtry_lock_irqsave - Acquire a per CPU local lock, save and disable
+ * interrupts
+ * @lock: The lock variable
+ * @flags: Storage for interrupt flags
+ */
+#define localtry_lock_irqsave(lock, flags) \
+ __localtry_lock_irqsave(lock, flags)
+
+/**
+ * localtry_trylock - Try to acquire a per CPU local lock.
+ * @lock: The lock variable
+ *
+ * The function can be used in any context such as NMI or HARDIRQ. Due to
+ * locking constrains it will _always_ fail to acquire the lock in NMI or
+ * HARDIRQ context on PREEMPT_RT.
+ */
+#define localtry_trylock(lock) __localtry_trylock(lock)
+
+/**
+ * localtry_trylock_irqsave - Try to acquire a per CPU local lock, save and disable
+ * interrupts if acquired
+ * @lock: The lock variable
+ * @flags: Storage for interrupt flags
+ *
+ * The function can be used in any context such as NMI or HARDIRQ. Due to
+ * locking constrains it will _always_ fail to acquire the lock in NMI or
+ * HARDIRQ context on PREEMPT_RT.
+ */
+#define localtry_trylock_irqsave(lock, flags) \
+ __localtry_trylock_irqsave(lock, flags)
+
+/**
+ * local_unlock - Release a per CPU local lock
+ * @lock: The lock variable
+ */
+#define localtry_unlock(lock) __localtry_unlock(lock)
+
+/**
+ * local_unlock_irq - Release a per CPU local lock and enable interrupts
+ * @lock: The lock variable
+ */
+#define localtry_unlock_irq(lock) __localtry_unlock_irq(lock)
+
+/**
+ * localtry_unlock_irqrestore - Release a per CPU local lock and restore
+ * interrupt flags
+ * @lock: The lock variable
+ * @flags: Interrupt flags to restore
+ */
+#define localtry_unlock_irqrestore(lock, flags) \
+ __localtry_unlock_irqrestore(lock, flags)
+
DEFINE_GUARD(local_lock, local_lock_t __percpu*,
local_lock(_T),
local_unlock(_T))
diff --git a/include/linux/local_lock_internal.h b/include/linux/local_lock_internal.h
index 8dd71fbbb6d2b6748969438c4642f7d970834871..67bd13d142fac39bc0f8b2c05eaf81717ff480f9 100644
--- a/include/linux/local_lock_internal.h
+++ b/include/linux/local_lock_internal.h
@@ -15,6 +15,11 @@ typedef struct {
#endif
} local_lock_t;
+typedef struct {
+ local_lock_t llock;
+ unsigned int acquired;
+} localtry_lock_t;
+
#ifdef CONFIG_DEBUG_LOCK_ALLOC
# define LOCAL_LOCK_DEBUG_INIT(lockname) \
.dep_map = { \
@@ -31,6 +36,13 @@ static inline void local_lock_acquire(local_lock_t *l)
l->owner = current;
}
+static inline void local_trylock_acquire(local_lock_t *l)
+{
+ lock_map_acquire_try(&l->dep_map);
+ DEBUG_LOCKS_WARN_ON(l->owner);
+ l->owner = current;
+}
+
static inline void local_lock_release(local_lock_t *l)
{
DEBUG_LOCKS_WARN_ON(l->owner != current);
@@ -45,11 +57,13 @@ static inline void local_lock_debug_init(local_lock_t *l)
#else /* CONFIG_DEBUG_LOCK_ALLOC */
# define LOCAL_LOCK_DEBUG_INIT(lockname)
static inline void local_lock_acquire(local_lock_t *l) { }
+static inline void local_trylock_acquire(local_lock_t *l) { }
static inline void local_lock_release(local_lock_t *l) { }
static inline void local_lock_debug_init(local_lock_t *l) { }
#endif /* !CONFIG_DEBUG_LOCK_ALLOC */
#define INIT_LOCAL_LOCK(lockname) { LOCAL_LOCK_DEBUG_INIT(lockname) }
+#define INIT_LOCALTRY_LOCK(lockname) { .llock = { LOCAL_LOCK_DEBUG_INIT(lockname.llock) }}
#define __local_lock_init(lock) \
do { \
@@ -118,6 +132,104 @@ do { \
#define __local_unlock_nested_bh(lock) \
local_lock_release(this_cpu_ptr(lock))
+/* localtry_lock_t variants */
+
+#define __localtry_lock_init(lock) \
+do { \
+ __local_lock_init(&(lock)->llock); \
+ WRITE_ONCE((lock)->acquired, 0); \
+} while (0)
+
+#define __localtry_lock(lock) \
+ do { \
+ localtry_lock_t *lt; \
+ preempt_disable(); \
+ lt = this_cpu_ptr(lock); \
+ local_lock_acquire(<->llock); \
+ WRITE_ONCE(lt->acquired, 1); \
+ } while (0)
+
+#define __localtry_lock_irq(lock) \
+ do { \
+ localtry_lock_t *lt; \
+ local_irq_disable(); \
+ lt = this_cpu_ptr(lock); \
+ local_lock_acquire(<->llock); \
+ WRITE_ONCE(lt->acquired, 1); \
+ } while (0)
+
+#define __localtry_lock_irqsave(lock, flags) \
+ do { \
+ localtry_lock_t *lt; \
+ local_irq_save(flags); \
+ lt = this_cpu_ptr(lock); \
+ local_lock_acquire(<->llock); \
+ WRITE_ONCE(lt->acquired, 1); \
+ } while (0)
+
+#define __localtry_trylock(lock) \
+ ({ \
+ localtry_lock_t *lt; \
+ bool _ret; \
+ \
+ preempt_disable(); \
+ lt = this_cpu_ptr(lock); \
+ if (!READ_ONCE(lt->acquired)) { \
+ WRITE_ONCE(lt->acquired, 1); \
+ local_trylock_acquire(<->llock); \
+ _ret = true; \
+ } else { \
+ _ret = false; \
+ preempt_enable(); \
+ } \
+ _ret; \
+ })
+
+#define __localtry_trylock_irqsave(lock, flags) \
+ ({ \
+ localtry_lock_t *lt; \
+ bool _ret; \
+ \
+ local_irq_save(flags); \
+ lt = this_cpu_ptr(lock); \
+ if (!READ_ONCE(lt->acquired)) { \
+ WRITE_ONCE(lt->acquired, 1); \
+ local_trylock_acquire(<->llock); \
+ _ret = true; \
+ } else { \
+ _ret = false; \
+ local_irq_restore(flags); \
+ } \
+ _ret; \
+ })
+
+#define __localtry_unlock(lock) \
+ do { \
+ localtry_lock_t *lt; \
+ lt = this_cpu_ptr(lock); \
+ WRITE_ONCE(lt->acquired, 0); \
+ local_lock_release(<->llock); \
+ preempt_enable(); \
+ } while (0)
+
+#define __localtry_unlock_irq(lock) \
+ do { \
+ localtry_lock_t *lt; \
+ lt = this_cpu_ptr(lock); \
+ WRITE_ONCE(lt->acquired, 0); \
+ local_lock_release(<->llock); \
+ local_irq_enable(); \
+ } while (0)
+
+#define __localtry_unlock_irqrestore(lock, flags) \
+ do { \
+ localtry_lock_t *lt; \
+ lt = this_cpu_ptr(lock); \
+ WRITE_ONCE(lt->acquired, 0); \
+ local_lock_release(<->llock); \
+ local_irq_restore(flags); \
+ } while (0)
+
#else /* !CONFIG_PREEMPT_RT */
/*
@@ -125,8 +237,10 @@ do { \
* critical section while staying preemptible.
*/
typedef spinlock_t local_lock_t;
+typedef spinlock_t localtry_lock_t;
#define INIT_LOCAL_LOCK(lockname) __LOCAL_SPIN_LOCK_UNLOCKED((lockname))
+#define INIT_LOCALTRY_LOCK(lockname) INIT_LOCAL_LOCK(lockname)
#define __local_lock_init(l) \
do { \
@@ -169,4 +283,36 @@ do { \
spin_unlock(this_cpu_ptr((lock))); \
} while (0)
+/* localtry_lock_t variants */
+
+#define __localtry_lock_init(lock) __local_lock_init(lock)
+#define __localtry_lock(lock) __local_lock(lock)
+#define __localtry_lock_irq(lock) __local_lock(lock)
+#define __localtry_lock_irqsave(lock, flags) __local_lock_irqsave(lock, flags)
+#define __localtry_unlock(lock) __local_unlock(lock)
+#define __localtry_unlock_irq(lock) __local_unlock(lock)
+#define __localtry_unlock_irqrestore(lock, flags) __local_unlock_irqrestore(lock, flags)
+
+#define __localtry_trylock(lock) \
+ ({ \
+ int __locked; \
+ \
+ if (in_nmi() | in_hardirq()) { \
+ __locked = 0; \
+ } else { \
+ migrate_disable(); \
+ __locked = spin_trylock(this_cpu_ptr((lock))); \
+ if (!__locked) \
+ migrate_enable(); \
+ } \
+ __locked; \
+ })
+
+#define __localtry_trylock_irqsave(lock, flags) \
+ ({ \
+ typecheck(unsigned long, flags); \
+ flags = 0; \
+ __localtry_trylock(lock); \
+ })
+
#endif /* CONFIG_PREEMPT_RT */
--
2.48.1
^ permalink raw reply [flat|nested] 20+ messages in thread
* [PATCH RFC v3 2/8] slab: add opt-in caching layer of percpu sheaves
2025-03-17 14:33 [PATCH RFC v3 0/8] SLUB percpu sheaves Vlastimil Babka
2025-03-17 14:33 ` [PATCH RFC v3 1/8] locking/local_lock: Introduce localtry_lock_t Vlastimil Babka
@ 2025-03-17 14:33 ` Vlastimil Babka
2025-04-03 8:31 ` Harry Yoo
2025-04-10 19:51 ` Suren Baghdasaryan
2025-03-17 14:33 ` [PATCH RFC v3 3/8] slab: add sheaf support for batching kfree_rcu() operations Vlastimil Babka
` (5 subsequent siblings)
7 siblings, 2 replies; 20+ messages in thread
From: Vlastimil Babka @ 2025-03-17 14:33 UTC (permalink / raw)
To: Suren Baghdasaryan, Liam R. Howlett, Christoph Lameter, David Rientjes
Cc: Roman Gushchin, Harry Yoo, Uladzislau Rezki, linux-mm,
linux-kernel, rcu, maple-tree, vbabka
Specifying a non-zero value for a new struct kmem_cache_args field
sheaf_capacity will setup a caching layer of percpu arrays called
sheaves of given capacity for the created cache.
Allocations from the cache will allocate via the percpu sheaves (main or
spare) as long as they have no NUMA node preference. Frees will also
refill one of the sheaves.
When both percpu sheaves are found empty during an allocation, an empty
sheaf may be replaced with a full one from the per-node barn. If none
are available and the allocation is allowed to block, an empty sheaf is
refilled from slab(s) by an internal bulk alloc operation. When both
percpu sheaves are full during freeing, the barn can replace a full one
with an empty one, unless over a full sheaves limit. In that case a
sheaf is flushed to slab(s) by an internal bulk free operation. Flushing
sheaves and barns is also wired to the existing cpu flushing and cache
shrinking operations.
The sheaves do not distinguish NUMA locality of the cached objects. If
an allocation is requested with kmem_cache_alloc_node() with a specific
node (not NUMA_NO_NODE), sheaves are bypassed.
The bulk operations exposed to slab users also try to utilize the
sheaves as long as the necessary (full or empty) sheaves are available
on the cpu or in the barn. Once depleted, they will fallback to bulk
alloc/free to slabs directly to avoid double copying.
Sysfs stat counters alloc_cpu_sheaf and free_cpu_sheaf count objects
allocated or freed using the sheaves. Counters sheaf_refill,
sheaf_flush_main and sheaf_flush_other count objects filled or flushed
from or to slab pages, and can be used to assess how effective the
caching is. The refill and flush operations will also count towards the
usual alloc_fastpath/slowpath, free_fastpath/slowpath and other
counters.
Access to the percpu sheaves is protected by localtry_trylock() when
potential callers include irq context, and localtry_lock() otherwise
(such as when we already know the gfp flags allow blocking). The trylock
failures should be rare and we can easily fallback. Each per-NUMA-node
barn has a spin_lock.
A current limitation is that when slub_debug is enabled for a cache with
percpu sheaves, the objects in the array are considered as allocated from
the slub_debug perspective, and the alloc/free debugging hooks occur
when moving the objects between the array and slab pages. This means
that e.g. an use-after-free that occurs for an object cached in the
array is undetected. Collected alloc/free stacktraces might also be less
useful. This limitation could be changed in the future.
On the other hand, KASAN, kmemcg and other hooks are executed on actual
allocations and frees by kmem_cache users even if those use the array,
so their debugging or accounting accuracy should be unaffected.
Signed-off-by: Vlastimil Babka <vbabka@suse.cz>
---
include/linux/slab.h | 34 ++
mm/slab.h | 2 +
mm/slab_common.c | 5 +-
mm/slub.c | 1029 +++++++++++++++++++++++++++++++++++++++++++++++---
4 files changed, 1020 insertions(+), 50 deletions(-)
diff --git a/include/linux/slab.h b/include/linux/slab.h
index 7686054dd494cc65def7f58748718e03eb78e481..0e1b25228c77140d05b5b4433c9d7923de36ec05 100644
--- a/include/linux/slab.h
+++ b/include/linux/slab.h
@@ -332,6 +332,40 @@ struct kmem_cache_args {
* %NULL means no constructor.
*/
void (*ctor)(void *);
+ /**
+ * @sheaf_capacity: Enable sheaves of given capacity for the cache.
+ *
+ * With a non-zero value, allocations from the cache go through caching
+ * arrays called sheaves. Each cpu has a main sheaf that's always
+ * present, and a spare sheaf thay may be not present. When both become
+ * empty, there's an attempt to replace an empty sheaf with a full sheaf
+ * from the per-node barn.
+ *
+ * When no full sheaf is available, and gfp flags allow blocking, a
+ * sheaf is allocated and filled from slab(s) using bulk allocation.
+ * Otherwise the allocation falls back to the normal operation
+ * allocating a single object from a slab.
+ *
+ * Analogically when freeing and both percpu sheaves are full, the barn
+ * may replace it with an empty sheaf, unless it's over capacity. In
+ * that case a sheaf is bulk freed to slab pages.
+ *
+ * The sheaves does not distinguish NUMA placement of objects, so
+ * allocations via kmem_cache_alloc_node() with a node specified other
+ * than NUMA_NO_NODE will bypass them.
+ *
+ * Bulk allocation and free operations also try to use the cpu sheaves
+ * and barn, but fallback to using slab pages directly.
+ *
+ * Limitations: when slub_debug is enabled for the cache, all relevant
+ * actions (i.e. poisoning, obtaining stacktraces) and checks happen
+ * when objects move between sheaves and slab pages, which may result in
+ * e.g. not detecting a use-after-free while the object is in the array
+ * cache, and the stacktraces may be less useful.
+ *
+ * %0 means no sheaves will be created
+ */
+ unsigned int sheaf_capacity;
};
struct kmem_cache *__kmem_cache_create_args(const char *name,
diff --git a/mm/slab.h b/mm/slab.h
index 2f01c7317988ce036f0b22807403226a59f0f708..8daaec53b6ecfc44171191d421adb12e5cba2c58 100644
--- a/mm/slab.h
+++ b/mm/slab.h
@@ -259,6 +259,7 @@ struct kmem_cache {
#ifndef CONFIG_SLUB_TINY
struct kmem_cache_cpu __percpu *cpu_slab;
#endif
+ struct slub_percpu_sheaves __percpu *cpu_sheaves;
/* Used for retrieving partial slabs, etc. */
slab_flags_t flags;
unsigned long min_partial;
@@ -272,6 +273,7 @@ struct kmem_cache {
/* Number of per cpu partial slabs to keep around */
unsigned int cpu_partial_slabs;
#endif
+ unsigned int sheaf_capacity;
struct kmem_cache_order_objects oo;
/* Allocation and freeing of slabs */
diff --git a/mm/slab_common.c b/mm/slab_common.c
index 46d0a4cd33b5982fd79c307d572f231fdea9514a..ceeefb287899a82f30ad79b403556001c1860311 100644
--- a/mm/slab_common.c
+++ b/mm/slab_common.c
@@ -163,6 +163,9 @@ int slab_unmergeable(struct kmem_cache *s)
return 1;
#endif
+ if (s->cpu_sheaves)
+ return 1;
+
/*
* We may have set a slab to be unmergeable during bootstrap.
*/
@@ -328,7 +331,7 @@ struct kmem_cache *__kmem_cache_create_args(const char *name,
object_size - args->usersize < args->useroffset))
args->usersize = args->useroffset = 0;
- if (!args->usersize)
+ if (!args->usersize && !args->sheaf_capacity)
s = __kmem_cache_alias(name, object_size, args->align, flags,
args->ctor);
if (s)
diff --git a/mm/slub.c b/mm/slub.c
index e8273f28656936c05d015c53923f8fe69cd161b2..fa3a6329713a9f45b189f27d4b1b334b54589c38 100644
--- a/mm/slub.c
+++ b/mm/slub.c
@@ -346,8 +346,10 @@ static inline void debugfs_slab_add(struct kmem_cache *s) { }
#endif
enum stat_item {
+ ALLOC_PCS, /* Allocation from percpu sheaf */
ALLOC_FASTPATH, /* Allocation from cpu slab */
ALLOC_SLOWPATH, /* Allocation by getting a new cpu slab */
+ FREE_PCS, /* Free to percpu sheaf */
FREE_FASTPATH, /* Free to cpu slab */
FREE_SLOWPATH, /* Freeing not to cpu slab */
FREE_FROZEN, /* Freeing to frozen slab */
@@ -372,6 +374,12 @@ enum stat_item {
CPU_PARTIAL_FREE, /* Refill cpu partial on free */
CPU_PARTIAL_NODE, /* Refill cpu partial from node partial */
CPU_PARTIAL_DRAIN, /* Drain cpu partial to node partial */
+ SHEAF_FLUSH_MAIN, /* Objects flushed from main percpu sheaf */
+ SHEAF_FLUSH_OTHER, /* Objects flushed from other sheaves */
+ SHEAF_REFILL, /* Objects refilled to a sheaf */
+ SHEAF_SWAP, /* Swapping main and spare sheaf */
+ SHEAF_ALLOC, /* Allocation of an empty sheaf */
+ SHEAF_FREE, /* Freeing of an empty sheaf */
NR_SLUB_STAT_ITEMS
};
@@ -418,6 +426,33 @@ void stat_add(const struct kmem_cache *s, enum stat_item si, int v)
#endif
}
+#define MAX_FULL_SHEAVES 10
+#define MAX_EMPTY_SHEAVES 10
+
+struct node_barn {
+ spinlock_t lock;
+ struct list_head sheaves_full;
+ struct list_head sheaves_empty;
+ unsigned int nr_full;
+ unsigned int nr_empty;
+};
+
+struct slab_sheaf {
+ union {
+ struct rcu_head rcu_head;
+ struct list_head barn_list;
+ };
+ unsigned int size;
+ void *objects[];
+};
+
+struct slub_percpu_sheaves {
+ localtry_lock_t lock;
+ struct slab_sheaf *main; /* never NULL when unlocked */
+ struct slab_sheaf *spare; /* empty or full, may be NULL */
+ struct node_barn *barn;
+};
+
/*
* The slab lists for all objects.
*/
@@ -430,6 +465,7 @@ struct kmem_cache_node {
atomic_long_t total_objects;
struct list_head full;
#endif
+ struct node_barn *barn;
};
static inline struct kmem_cache_node *get_node(struct kmem_cache *s, int node)
@@ -453,12 +489,19 @@ static inline struct kmem_cache_node *get_node(struct kmem_cache *s, int node)
*/
static nodemask_t slab_nodes;
-#ifndef CONFIG_SLUB_TINY
/*
* Workqueue used for flush_cpu_slab().
*/
static struct workqueue_struct *flushwq;
-#endif
+
+struct slub_flush_work {
+ struct work_struct work;
+ struct kmem_cache *s;
+ bool skip;
+};
+
+static DEFINE_MUTEX(flush_lock);
+static DEFINE_PER_CPU(struct slub_flush_work, slub_flush);
/********************************************************************
* Core slab cache functions
@@ -2410,6 +2453,358 @@ static void *setup_object(struct kmem_cache *s, void *object)
return object;
}
+static struct slab_sheaf *alloc_empty_sheaf(struct kmem_cache *s, gfp_t gfp)
+{
+ struct slab_sheaf *sheaf = kzalloc(struct_size(sheaf, objects,
+ s->sheaf_capacity), gfp);
+
+ if (unlikely(!sheaf))
+ return NULL;
+
+ stat(s, SHEAF_ALLOC);
+
+ return sheaf;
+}
+
+static void free_empty_sheaf(struct kmem_cache *s, struct slab_sheaf *sheaf)
+{
+ kfree(sheaf);
+
+ stat(s, SHEAF_FREE);
+}
+
+static int __kmem_cache_alloc_bulk(struct kmem_cache *s, gfp_t flags,
+ size_t size, void **p);
+
+
+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 = __kmem_cache_alloc_bulk(s, gfp, to_fill,
+ &sheaf->objects[sheaf->size]);
+
+ sheaf->size += filled;
+
+ stat_add(s, SHEAF_REFILL, filled);
+
+ if (filled < to_fill)
+ return -ENOMEM;
+
+ return 0;
+}
+
+
+static struct slab_sheaf *alloc_full_sheaf(struct kmem_cache *s, gfp_t gfp)
+{
+ struct slab_sheaf *sheaf = alloc_empty_sheaf(s, gfp);
+
+ if (!sheaf)
+ return NULL;
+
+ if (refill_sheaf(s, sheaf, gfp)) {
+ free_empty_sheaf(s, sheaf);
+ return NULL;
+ }
+
+ return sheaf;
+}
+
+/*
+ * Maximum number of objects freed during a single flush of main pcs sheaf.
+ * Translates directly to an on-stack array size.
+ */
+#define PCS_BATCH_MAX 32U
+
+static void __kmem_cache_free_bulk(struct kmem_cache *s, size_t size, void **p);
+
+/*
+ * Free all objects from the main sheaf. In order to perform
+ * __kmem_cache_free_bulk() outside of cpu_sheaves->lock, work in batches where
+ * object pointers are moved to a on-stack array under the lock. To bound the
+ * stack usage, limit each batch to PCS_BATCH_MAX.
+ *
+ * returns true if at least partially flushed
+ */
+static bool sheaf_flush_main(struct kmem_cache *s)
+{
+ struct slub_percpu_sheaves *pcs;
+ unsigned int batch, remaining;
+ void *objects[PCS_BATCH_MAX];
+ struct slab_sheaf *sheaf;
+ bool ret = false;
+
+next_batch:
+ if (!localtry_trylock(&s->cpu_sheaves->lock))
+ return ret;
+
+ pcs = this_cpu_ptr(s->cpu_sheaves);
+ sheaf = pcs->main;
+
+ batch = min(PCS_BATCH_MAX, sheaf->size);
+
+ sheaf->size -= batch;
+ memcpy(objects, sheaf->objects + sheaf->size, batch * sizeof(void *));
+
+ remaining = sheaf->size;
+
+ localtry_unlock(&s->cpu_sheaves->lock);
+
+ __kmem_cache_free_bulk(s, batch, &objects[0]);
+
+ stat_add(s, SHEAF_FLUSH_MAIN, batch);
+
+ ret = true;
+
+ if (remaining)
+ goto next_batch;
+
+ return ret;
+}
+
+/*
+ * Free all objects from a sheaf that's unused, i.e. not linked to any
+ * cpu_sheaves, so we need no locking and batching. The locking is also not
+ * necessary when flushing cpu's sheaves (both spare and main) during cpu
+ * hotremove as the cpu is not executing anymore.
+ */
+static void sheaf_flush_unused(struct kmem_cache *s, struct slab_sheaf *sheaf)
+{
+ if (!sheaf->size)
+ return;
+
+ stat_add(s, SHEAF_FLUSH_OTHER, sheaf->size);
+
+ __kmem_cache_free_bulk(s, sheaf->size, &sheaf->objects[0]);
+
+ sheaf->size = 0;
+}
+
+/*
+ * Caller needs to make sure migration is disabled in order to fully flush
+ * single cpu's sheaves
+ *
+ * must not be called from an irq
+ *
+ * flushing operations are rare so let's keep it simple and flush to slabs
+ * directly, skipping the barn
+ */
+static void pcs_flush_all(struct kmem_cache *s)
+{
+ struct slub_percpu_sheaves *pcs;
+ struct slab_sheaf *spare;
+
+ localtry_lock(&s->cpu_sheaves->lock);
+ pcs = this_cpu_ptr(s->cpu_sheaves);
+
+ spare = pcs->spare;
+ pcs->spare = NULL;
+
+ localtry_unlock(&s->cpu_sheaves->lock);
+
+ if (spare) {
+ sheaf_flush_unused(s, spare);
+ free_empty_sheaf(s, spare);
+ }
+
+ sheaf_flush_main(s);
+}
+
+static void __pcs_flush_all_cpu(struct kmem_cache *s, unsigned int cpu)
+{
+ struct slub_percpu_sheaves *pcs;
+
+ pcs = per_cpu_ptr(s->cpu_sheaves, cpu);
+
+ /* The cpu is not executing anymore so we don't need pcs->lock */
+ sheaf_flush_unused(s, pcs->main);
+ if (pcs->spare) {
+ sheaf_flush_unused(s, pcs->spare);
+ free_empty_sheaf(s, pcs->spare);
+ pcs->spare = NULL;
+ }
+}
+
+static void pcs_destroy(struct kmem_cache *s)
+{
+ int cpu;
+
+ for_each_possible_cpu(cpu) {
+ struct slub_percpu_sheaves *pcs;
+
+ pcs = per_cpu_ptr(s->cpu_sheaves, cpu);
+
+ /* can happen when unwinding failed create */
+ if (!pcs->main)
+ continue;
+
+ WARN_ON(pcs->spare);
+
+ if (!WARN_ON(pcs->main->size)) {
+ free_empty_sheaf(s, pcs->main);
+ pcs->main = NULL;
+ }
+ }
+
+ free_percpu(s->cpu_sheaves);
+ s->cpu_sheaves = NULL;
+}
+
+static struct slab_sheaf *barn_get_empty_sheaf(struct node_barn *barn)
+{
+ struct slab_sheaf *empty = NULL;
+ unsigned long flags;
+
+ spin_lock_irqsave(&barn->lock, flags);
+
+ if (barn->nr_empty) {
+ empty = list_first_entry(&barn->sheaves_empty,
+ struct slab_sheaf, barn_list);
+ list_del(&empty->barn_list);
+ barn->nr_empty--;
+ }
+
+ spin_unlock_irqrestore(&barn->lock, flags);
+
+ return empty;
+}
+
+static int barn_put_empty_sheaf(struct node_barn *barn,
+ struct slab_sheaf *sheaf, bool ignore_limit)
+{
+ unsigned long flags;
+ int ret = 0;
+
+ spin_lock_irqsave(&barn->lock, flags);
+
+ if (!ignore_limit && barn->nr_empty >= MAX_EMPTY_SHEAVES) {
+ ret = -E2BIG;
+ } else {
+ list_add(&sheaf->barn_list, &barn->sheaves_empty);
+ barn->nr_empty++;
+ }
+
+ spin_unlock_irqrestore(&barn->lock, flags);
+ return ret;
+}
+
+static int barn_put_full_sheaf(struct node_barn *barn, struct slab_sheaf *sheaf,
+ bool ignore_limit)
+{
+ unsigned long flags;
+ int ret = 0;
+
+ spin_lock_irqsave(&barn->lock, flags);
+
+ if (!ignore_limit && barn->nr_full >= MAX_FULL_SHEAVES) {
+ ret = -E2BIG;
+ } else {
+ list_add(&sheaf->barn_list, &barn->sheaves_full);
+ barn->nr_full++;
+ }
+
+ spin_unlock_irqrestore(&barn->lock, flags);
+ return ret;
+}
+
+/*
+ * If a full sheaf is available, return it and put the supplied empty one to
+ * barn. We ignore the limit on empty sheaves as the number of sheaves doesn't
+ * change.
+ */
+static struct slab_sheaf *
+barn_replace_empty_sheaf(struct node_barn *barn, struct slab_sheaf *empty)
+{
+ struct slab_sheaf *full = NULL;
+ unsigned long flags;
+
+ spin_lock_irqsave(&barn->lock, flags);
+
+ if (barn->nr_full) {
+ full = list_first_entry(&barn->sheaves_full, struct slab_sheaf,
+ barn_list);
+ list_del(&full->barn_list);
+ list_add(&empty->barn_list, &barn->sheaves_empty);
+ barn->nr_full--;
+ barn->nr_empty++;
+ }
+
+ spin_unlock_irqrestore(&barn->lock, flags);
+
+ return full;
+}
+/*
+ * If a empty sheaf is available, return it and put the supplied full one to
+ * barn. But if there are too many full sheaves, reject this with -E2BIG.
+ */
+static struct slab_sheaf *
+barn_replace_full_sheaf(struct node_barn *barn, struct slab_sheaf *full)
+{
+ struct slab_sheaf *empty;
+ unsigned long flags;
+
+ spin_lock_irqsave(&barn->lock, flags);
+
+ if (barn->nr_full >= MAX_FULL_SHEAVES) {
+ empty = ERR_PTR(-E2BIG);
+ } else if (!barn->nr_empty) {
+ empty = ERR_PTR(-ENOMEM);
+ } else {
+ empty = list_first_entry(&barn->sheaves_empty, struct slab_sheaf,
+ barn_list);
+ list_del(&empty->barn_list);
+ list_add(&full->barn_list, &barn->sheaves_full);
+ barn->nr_empty--;
+ barn->nr_full++;
+ }
+
+ spin_unlock_irqrestore(&barn->lock, flags);
+
+ return empty;
+}
+
+static void barn_init(struct node_barn *barn)
+{
+ spin_lock_init(&barn->lock);
+ INIT_LIST_HEAD(&barn->sheaves_full);
+ INIT_LIST_HEAD(&barn->sheaves_empty);
+ barn->nr_full = 0;
+ barn->nr_empty = 0;
+}
+
+static void barn_shrink(struct kmem_cache *s, struct node_barn *barn)
+{
+ struct list_head empty_list;
+ struct list_head full_list;
+ struct slab_sheaf *sheaf, *sheaf2;
+ unsigned long flags;
+
+ INIT_LIST_HEAD(&empty_list);
+ INIT_LIST_HEAD(&full_list);
+
+ spin_lock_irqsave(&barn->lock, flags);
+
+ list_splice_init(&barn->sheaves_full, &full_list);
+ barn->nr_full = 0;
+ list_splice_init(&barn->sheaves_empty, &empty_list);
+ barn->nr_empty = 0;
+
+ spin_unlock_irqrestore(&barn->lock, flags);
+
+ list_for_each_entry_safe(sheaf, sheaf2, &full_list, barn_list) {
+ sheaf_flush_unused(s, sheaf);
+ free_empty_sheaf(s, sheaf);
+ }
+
+ list_for_each_entry_safe(sheaf, sheaf2, &empty_list, barn_list)
+ free_empty_sheaf(s, sheaf);
+}
+
/*
* Slab allocation and freeing
*/
@@ -3280,11 +3675,42 @@ static inline void __flush_cpu_slab(struct kmem_cache *s, int cpu)
put_partials_cpu(s, c);
}
-struct slub_flush_work {
- struct work_struct work;
- struct kmem_cache *s;
- bool skip;
-};
+static inline void flush_this_cpu_slab(struct kmem_cache *s)
+{
+ struct kmem_cache_cpu *c = this_cpu_ptr(s->cpu_slab);
+
+ if (c->slab)
+ flush_slab(s, c);
+
+ put_partials(s);
+}
+
+static bool has_cpu_slab(int cpu, struct kmem_cache *s)
+{
+ struct kmem_cache_cpu *c = per_cpu_ptr(s->cpu_slab, cpu);
+
+ return c->slab || slub_percpu_partial(c);
+}
+
+#else /* CONFIG_SLUB_TINY */
+static inline void __flush_cpu_slab(struct kmem_cache *s, int cpu) { }
+static inline bool has_cpu_slab(int cpu, struct kmem_cache *s) { return false; }
+static inline void flush_this_cpu_slab(struct kmem_cache *s) { }
+#endif /* CONFIG_SLUB_TINY */
+
+static bool has_pcs_used(int cpu, struct kmem_cache *s)
+{
+ struct slub_percpu_sheaves *pcs;
+
+ if (!s->cpu_sheaves)
+ return false;
+
+ pcs = per_cpu_ptr(s->cpu_sheaves, cpu);
+
+ return (pcs->spare || pcs->main->size);
+}
+
+static void pcs_flush_all(struct kmem_cache *s);
/*
* Flush cpu slab.
@@ -3294,30 +3720,18 @@ struct slub_flush_work {
static void flush_cpu_slab(struct work_struct *w)
{
struct kmem_cache *s;
- struct kmem_cache_cpu *c;
struct slub_flush_work *sfw;
sfw = container_of(w, struct slub_flush_work, work);
s = sfw->s;
- c = this_cpu_ptr(s->cpu_slab);
-
- if (c->slab)
- flush_slab(s, c);
-
- put_partials(s);
-}
-static bool has_cpu_slab(int cpu, struct kmem_cache *s)
-{
- struct kmem_cache_cpu *c = per_cpu_ptr(s->cpu_slab, cpu);
+ if (s->cpu_sheaves)
+ pcs_flush_all(s);
- return c->slab || slub_percpu_partial(c);
+ flush_this_cpu_slab(s);
}
-static DEFINE_MUTEX(flush_lock);
-static DEFINE_PER_CPU(struct slub_flush_work, slub_flush);
-
static void flush_all_cpus_locked(struct kmem_cache *s)
{
struct slub_flush_work *sfw;
@@ -3328,7 +3742,7 @@ static void flush_all_cpus_locked(struct kmem_cache *s)
for_each_online_cpu(cpu) {
sfw = &per_cpu(slub_flush, cpu);
- if (!has_cpu_slab(cpu, s)) {
+ if (!has_cpu_slab(cpu, s) && !has_pcs_used(cpu, s)) {
sfw->skip = true;
continue;
}
@@ -3364,19 +3778,14 @@ static int slub_cpu_dead(unsigned int cpu)
struct kmem_cache *s;
mutex_lock(&slab_mutex);
- list_for_each_entry(s, &slab_caches, list)
+ list_for_each_entry(s, &slab_caches, list) {
__flush_cpu_slab(s, cpu);
+ __pcs_flush_all_cpu(s, cpu);
+ }
mutex_unlock(&slab_mutex);
return 0;
}
-#else /* CONFIG_SLUB_TINY */
-static inline void flush_all_cpus_locked(struct kmem_cache *s) { }
-static inline void flush_all(struct kmem_cache *s) { }
-static inline void __flush_cpu_slab(struct kmem_cache *s, int cpu) { }
-static inline int slub_cpu_dead(unsigned int cpu) { return 0; }
-#endif /* CONFIG_SLUB_TINY */
-
/*
* Check if the objects in a per cpu structure fit numa
* locality expectations.
@@ -4126,6 +4535,179 @@ bool slab_post_alloc_hook(struct kmem_cache *s, struct list_lru *lru,
return memcg_slab_post_alloc_hook(s, lru, flags, size, p);
}
+static __fastpath_inline
+void *alloc_from_pcs(struct kmem_cache *s, gfp_t gfp)
+{
+ struct slub_percpu_sheaves *pcs;
+ void *object;
+
+ if (!localtry_trylock(&s->cpu_sheaves->lock))
+ return NULL;
+
+ pcs = this_cpu_ptr(s->cpu_sheaves);
+
+ if (unlikely(pcs->main->size == 0)) {
+
+ struct slab_sheaf *empty = NULL;
+ struct slab_sheaf *full;
+ bool can_alloc;
+
+ if (pcs->spare && pcs->spare->size > 0) {
+ stat(s, SHEAF_SWAP);
+ swap(pcs->main, pcs->spare);
+ goto do_alloc;
+ }
+
+ full = barn_replace_empty_sheaf(pcs->barn, pcs->main);
+
+ if (full) {
+ pcs->main = full;
+ goto do_alloc;
+ }
+
+ can_alloc = gfpflags_allow_blocking(gfp);
+
+ if (can_alloc) {
+ if (pcs->spare) {
+ empty = pcs->spare;
+ pcs->spare = NULL;
+ } else {
+ empty = barn_get_empty_sheaf(pcs->barn);
+ }
+ }
+
+ localtry_unlock(&s->cpu_sheaves->lock);
+
+ if (!can_alloc)
+ return NULL;
+
+ if (empty) {
+ if (!refill_sheaf(s, empty, gfp)) {
+ full = empty;
+ } else {
+ /*
+ * we must be very low on memory so don't bother
+ * with the barn
+ */
+ free_empty_sheaf(s, empty);
+ }
+ } else {
+ full = alloc_full_sheaf(s, gfp);
+ }
+
+ if (!full)
+ return NULL;
+
+ /*
+ * we can reach here only when gfpflags_allow_blocking
+ * so this must not be an irq
+ */
+ localtry_lock(&s->cpu_sheaves->lock);
+ 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) {
+ barn_put_empty_sheaf(pcs->barn, pcs->main, true);
+ pcs->main = full;
+ goto do_alloc;
+ }
+
+ if (!pcs->spare) {
+ pcs->spare = full;
+ goto do_alloc;
+ }
+
+ if (pcs->spare->size == 0) {
+ barn_put_empty_sheaf(pcs->barn, pcs->spare, true);
+ pcs->spare = full;
+ goto do_alloc;
+ }
+
+ barn_put_full_sheaf(pcs->barn, full, true);
+ }
+
+do_alloc:
+ object = pcs->main->objects[--pcs->main->size];
+
+ localtry_unlock(&s->cpu_sheaves->lock);
+
+ stat(s, ALLOC_PCS);
+
+ return object;
+}
+
+static __fastpath_inline
+unsigned int alloc_from_pcs_bulk(struct kmem_cache *s, size_t size, void **p)
+{
+ struct slub_percpu_sheaves *pcs;
+ struct slab_sheaf *main;
+ unsigned int allocated = 0;
+ unsigned int batch;
+
+next_batch:
+ if (!localtry_trylock(&s->cpu_sheaves->lock))
+ return allocated;
+
+ pcs = this_cpu_ptr(s->cpu_sheaves);
+
+ if (unlikely(pcs->main->size == 0)) {
+
+ struct slab_sheaf *full;
+
+ if (pcs->spare && pcs->spare->size > 0) {
+ stat(s, SHEAF_SWAP);
+ swap(pcs->main, pcs->spare);
+ goto do_alloc;
+ }
+
+ full = barn_replace_empty_sheaf(pcs->barn, pcs->main);
+
+ if (full) {
+ pcs->main = full;
+ goto do_alloc;
+ }
+
+ localtry_unlock(&s->cpu_sheaves->lock);
+
+ /*
+ * Once full sheaves in barn are depleted, let the bulk
+ * allocation continue from slab pages, otherwise we would just
+ * be copying arrays of pointers twice.
+ */
+ return allocated;
+ }
+
+do_alloc:
+
+ main = pcs->main;
+ batch = min(size, main->size);
+
+ main->size -= batch;
+ memcpy(p, main->objects + main->size, batch * sizeof(void *));
+
+ localtry_unlock(&s->cpu_sheaves->lock);
+
+ stat_add(s, ALLOC_PCS, batch);
+
+ allocated += batch;
+
+ if (batch < size) {
+ p += batch;
+ size -= batch;
+ goto next_batch;
+ }
+
+ return allocated;
+}
+
+
/*
* Inlined fastpath so that allocation functions (kmalloc, kmem_cache_alloc)
* have the fastpath folded into their functions. So no function call
@@ -4150,7 +4732,11 @@ static __fastpath_inline void *slab_alloc_node(struct kmem_cache *s, struct list
if (unlikely(object))
goto out;
- object = __slab_alloc_node(s, gfpflags, node, addr, orig_size);
+ if (s->cpu_sheaves && (node == NUMA_NO_NODE))
+ object = alloc_from_pcs(s, gfpflags);
+
+ 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);
@@ -4521,6 +5107,232 @@ static void __slab_free(struct kmem_cache *s, struct slab *slab,
discard_slab(s, slab);
}
+/*
+ * pcs is locked. We should have get rid of the spare sheaf and obtained an
+ * empty sheaf, while the main sheaf is full. We want to install the empty sheaf
+ * as a main sheaf, and make the current main sheaf a spare sheaf.
+ *
+ * However due to having relinquished the cpu_sheaves lock when obtaining
+ * the empty sheaf, we need to handle some unlikely but possible cases.
+ *
+ * If we put any sheaf to barn here, it's because we were interrupted or have
+ * been migrated to a different cpu, which should be rare enough so just ignore
+ * the barn's limits to simplify the handling.
+ */
+static void __pcs_install_empty_sheaf(struct kmem_cache *s,
+ struct slub_percpu_sheaves *pcs, struct slab_sheaf *empty)
+{
+ /* this is what we expect to find in nobody interrupted us */
+ if (likely(!pcs->spare)) {
+ pcs->spare = pcs->main;
+ pcs->main = empty;
+ return;
+ }
+
+ /*
+ * Unlikely because if the main sheaf had space, we would have just
+ * freed to it. Get rid of our empty sheaf.
+ */
+ if (pcs->main->size < s->sheaf_capacity) {
+ barn_put_empty_sheaf(pcs->barn, empty, true);
+ return;
+ }
+
+ /* Also unlikely for the same reason */
+ if (pcs->spare->size < s->sheaf_capacity) {
+ stat(s, SHEAF_SWAP);
+ swap(pcs->main, pcs->spare);
+ barn_put_empty_sheaf(pcs->barn, empty, true);
+ return;
+ }
+
+ barn_put_full_sheaf(pcs->barn, pcs->main, true);
+ pcs->main = empty;
+}
+
+/*
+ * Free an object to the percpu sheaves.
+ * The object is expected to have passed slab_free_hook() already.
+ */
+static __fastpath_inline
+bool free_to_pcs(struct kmem_cache *s, void *object)
+{
+ struct slub_percpu_sheaves *pcs;
+
+restart:
+ if (!localtry_trylock(&s->cpu_sheaves->lock))
+ return false;
+
+ pcs = this_cpu_ptr(s->cpu_sheaves);
+
+ if (unlikely(pcs->main->size == s->sheaf_capacity)) {
+
+ struct slab_sheaf *empty;
+
+ if (!pcs->spare) {
+ empty = barn_get_empty_sheaf(pcs->barn);
+ if (empty) {
+ pcs->spare = pcs->main;
+ pcs->main = empty;
+ goto do_free;
+ }
+ goto alloc_empty;
+ }
+
+ if (pcs->spare->size < s->sheaf_capacity) {
+ stat(s, SHEAF_SWAP);
+ swap(pcs->main, pcs->spare);
+ goto do_free;
+ }
+
+ empty = barn_replace_full_sheaf(pcs->barn, pcs->main);
+
+ if (!IS_ERR(empty)) {
+ pcs->main = empty;
+ goto do_free;
+ }
+
+ if (PTR_ERR(empty) == -E2BIG) {
+ /* Since we got here, spare exists and is full */
+ struct slab_sheaf *to_flush = pcs->spare;
+
+ pcs->spare = NULL;
+ localtry_unlock(&s->cpu_sheaves->lock);
+
+ sheaf_flush_unused(s, to_flush);
+ empty = to_flush;
+ goto got_empty;
+ }
+
+alloc_empty:
+ localtry_unlock(&s->cpu_sheaves->lock);
+
+ empty = alloc_empty_sheaf(s, GFP_NOWAIT);
+
+ if (!empty) {
+ if (sheaf_flush_main(s))
+ goto restart;
+ else
+ return false;
+ }
+
+got_empty:
+ if (!localtry_trylock(&s->cpu_sheaves->lock)) {
+ struct node_barn *barn;
+
+ barn = get_node(s, numa_mem_id())->barn;
+
+ barn_put_empty_sheaf(barn, empty, true);
+ return false;
+ }
+
+ pcs = this_cpu_ptr(s->cpu_sheaves);
+ __pcs_install_empty_sheaf(s, pcs, empty);
+ }
+
+do_free:
+ pcs->main->objects[pcs->main->size++] = object;
+
+ localtry_unlock(&s->cpu_sheaves->lock);
+
+ stat(s, FREE_PCS);
+
+ return true;
+}
+
+/*
+ * Bulk free objects to the percpu sheaves.
+ * Unlike free_to_pcs() this includes the calls to all necessary hooks
+ * and the fallback to freeing to slab pages.
+ */
+static void free_to_pcs_bulk(struct kmem_cache *s, size_t size, void **p)
+{
+ struct slub_percpu_sheaves *pcs;
+ struct slab_sheaf *main;
+ unsigned int batch, i = 0;
+ bool init;
+
+ init = slab_want_init_on_free(s);
+
+ while (i < size) {
+ struct slab *slab = virt_to_slab(p[i]);
+
+ memcg_slab_free_hook(s, slab, p + i, 1);
+ alloc_tagging_slab_free_hook(s, slab, p + i, 1);
+
+ if (unlikely(!slab_free_hook(s, p[i], init, false))) {
+ p[i] = p[--size];
+ if (!size)
+ return;
+ continue;
+ }
+
+ i++;
+ }
+
+next_batch:
+ if (!localtry_trylock(&s->cpu_sheaves->lock))
+ goto fallback;
+
+ pcs = this_cpu_ptr(s->cpu_sheaves);
+
+ if (unlikely(pcs->main->size == s->sheaf_capacity)) {
+
+ struct slab_sheaf *empty;
+
+ if (!pcs->spare) {
+ empty = barn_get_empty_sheaf(pcs->barn);
+ if (empty) {
+ pcs->spare = pcs->main;
+ pcs->main = empty;
+ goto do_free;
+ }
+ goto no_empty;
+ }
+
+ if (pcs->spare->size < s->sheaf_capacity) {
+ stat(s, SHEAF_SWAP);
+ swap(pcs->main, pcs->spare);
+ goto do_free;
+ }
+
+ empty = barn_replace_full_sheaf(pcs->barn, pcs->main);
+
+ if (!IS_ERR(empty)) {
+ pcs->main = empty;
+ goto do_free;
+ }
+
+no_empty:
+ localtry_unlock(&s->cpu_sheaves->lock);
+
+ /*
+ * if we depleted all empty sheaves in the barn or there are too
+ * many full sheaves, free the rest to slab pages
+ */
+fallback:
+ __kmem_cache_free_bulk(s, size, p);
+ return;
+ }
+
+do_free:
+ main = pcs->main;
+ batch = min(size, s->sheaf_capacity - main->size);
+
+ memcpy(main->objects + main->size, p, batch * sizeof(void *));
+ main->size += batch;
+
+ localtry_unlock(&s->cpu_sheaves->lock);
+
+ stat_add(s, FREE_PCS, batch);
+
+ if (batch < size) {
+ p += batch;
+ size -= batch;
+ goto next_batch;
+ }
+}
+
#ifndef CONFIG_SLUB_TINY
/*
* Fastpath with forced inlining to produce a kfree and kmem_cache_free that
@@ -4607,7 +5419,10 @@ void slab_free(struct kmem_cache *s, struct slab *slab, void *object,
memcg_slab_free_hook(s, slab, &object, 1);
alloc_tagging_slab_free_hook(s, slab, &object, 1);
- if (likely(slab_free_hook(s, object, slab_want_init_on_free(s), false)))
+ if (unlikely(!slab_free_hook(s, object, slab_want_init_on_free(s), false)))
+ return;
+
+ if (!s->cpu_sheaves || !free_to_pcs(s, object))
do_slab_free(s, slab, object, object, 1, addr);
}
@@ -5033,6 +5848,15 @@ void kmem_cache_free_bulk(struct kmem_cache *s, size_t size, void **p)
if (!size)
return;
+ /*
+ * freeing to sheaves is so incompatible with the detached freelist so
+ * once we go that way, we have to do everything differently
+ */
+ if (s && s->cpu_sheaves) {
+ free_to_pcs_bulk(s, size, p);
+ return;
+ }
+
do {
struct detached_freelist df;
@@ -5151,7 +5975,7 @@ static int __kmem_cache_alloc_bulk(struct kmem_cache *s, gfp_t flags,
int kmem_cache_alloc_bulk_noprof(struct kmem_cache *s, gfp_t flags, size_t size,
void **p)
{
- int i;
+ unsigned int i = 0;
if (!size)
return 0;
@@ -5160,9 +5984,21 @@ int kmem_cache_alloc_bulk_noprof(struct kmem_cache *s, gfp_t flags, size_t size,
if (unlikely(!s))
return 0;
- i = __kmem_cache_alloc_bulk(s, flags, size, p);
- if (unlikely(i == 0))
- return 0;
+ if (s->cpu_sheaves)
+ i = alloc_from_pcs_bulk(s, size, p);
+
+ if (i < size) {
+ unsigned int j = __kmem_cache_alloc_bulk(s, flags, size - i, p + i);
+ /*
+ * If we ran out of memory, don't bother with freeing back to
+ * the percpu sheaves, we have bigger problems.
+ */
+ if (unlikely(j == 0)) {
+ if (i > 0)
+ __kmem_cache_free_bulk(s, i, p);
+ return 0;
+ }
+ }
/*
* memcg and kmem_cache debug support and memory initialization.
@@ -5172,11 +6008,11 @@ int kmem_cache_alloc_bulk_noprof(struct kmem_cache *s, gfp_t flags, size_t size,
slab_want_init_on_alloc(flags, s), s->object_size))) {
return 0;
}
- return i;
+
+ return size;
}
EXPORT_SYMBOL(kmem_cache_alloc_bulk_noprof);
-
/*
* Object placement in a slab is made very easy because we always start at
* offset 0. If we tune the size of the object to the alignment then we can
@@ -5309,8 +6145,8 @@ static inline int calculate_order(unsigned int size)
return -ENOSYS;
}
-static void
-init_kmem_cache_node(struct kmem_cache_node *n)
+static bool
+init_kmem_cache_node(struct kmem_cache_node *n, struct node_barn *barn)
{
n->nr_partial = 0;
spin_lock_init(&n->list_lock);
@@ -5320,6 +6156,11 @@ init_kmem_cache_node(struct kmem_cache_node *n)
atomic_long_set(&n->total_objects, 0);
INIT_LIST_HEAD(&n->full);
#endif
+ n->barn = barn;
+ if (barn)
+ barn_init(barn);
+
+ return true;
}
#ifndef CONFIG_SLUB_TINY
@@ -5350,6 +6191,30 @@ static inline int alloc_kmem_cache_cpus(struct kmem_cache *s)
}
#endif /* CONFIG_SLUB_TINY */
+static int init_percpu_sheaves(struct kmem_cache *s)
+{
+ int cpu;
+
+ for_each_possible_cpu(cpu) {
+ struct slub_percpu_sheaves *pcs;
+ int nid;
+
+ pcs = per_cpu_ptr(s->cpu_sheaves, cpu);
+
+ localtry_lock_init(&pcs->lock);
+
+ nid = cpu_to_mem(cpu);
+
+ pcs->barn = get_node(s, nid)->barn;
+ pcs->main = alloc_empty_sheaf(s, GFP_KERNEL);
+
+ if (!pcs->main)
+ return -ENOMEM;
+ }
+
+ return 0;
+}
+
static struct kmem_cache *kmem_cache_node;
/*
@@ -5385,7 +6250,7 @@ static void early_kmem_cache_node_alloc(int node)
slab->freelist = get_freepointer(kmem_cache_node, n);
slab->inuse = 1;
kmem_cache_node->node[node] = n;
- init_kmem_cache_node(n);
+ init_kmem_cache_node(n, NULL);
inc_slabs_node(kmem_cache_node, node, slab->objects);
/*
@@ -5401,6 +6266,13 @@ static void free_kmem_cache_nodes(struct kmem_cache *s)
struct kmem_cache_node *n;
for_each_kmem_cache_node(s, node, n) {
+ if (n->barn) {
+ WARN_ON(n->barn->nr_full);
+ WARN_ON(n->barn->nr_empty);
+ kfree(n->barn);
+ n->barn = NULL;
+ }
+
s->node[node] = NULL;
kmem_cache_free(kmem_cache_node, n);
}
@@ -5409,6 +6281,8 @@ static void free_kmem_cache_nodes(struct kmem_cache *s)
void __kmem_cache_release(struct kmem_cache *s)
{
cache_random_seq_destroy(s);
+ if (s->cpu_sheaves)
+ pcs_destroy(s);
#ifndef CONFIG_SLUB_TINY
free_percpu(s->cpu_slab);
#endif
@@ -5421,20 +6295,27 @@ static int init_kmem_cache_nodes(struct kmem_cache *s)
for_each_node_mask(node, slab_nodes) {
struct kmem_cache_node *n;
+ struct node_barn *barn = NULL;
if (slab_state == DOWN) {
early_kmem_cache_node_alloc(node);
continue;
}
+
+ if (s->cpu_sheaves) {
+ barn = kmalloc_node(sizeof(*barn), GFP_KERNEL, node);
+
+ if (!barn)
+ return 0;
+ }
+
n = kmem_cache_alloc_node(kmem_cache_node,
GFP_KERNEL, node);
-
- if (!n) {
- free_kmem_cache_nodes(s);
+ if (!n)
return 0;
- }
- init_kmem_cache_node(n);
+ init_kmem_cache_node(n, barn);
+
s->node[node] = n;
}
return 1;
@@ -5690,6 +6571,8 @@ int __kmem_cache_shutdown(struct kmem_cache *s)
flush_all_cpus_locked(s);
/* Attempt to free all objects */
for_each_kmem_cache_node(s, node, n) {
+ if (n->barn)
+ barn_shrink(s, n->barn);
free_partial(s, n);
if (n->nr_partial || node_nr_slabs(n))
return 1;
@@ -5893,6 +6776,9 @@ static int __kmem_cache_do_shrink(struct kmem_cache *s)
for (i = 0; i < SHRINK_PROMOTE_MAX; i++)
INIT_LIST_HEAD(promote + i);
+ if (n->barn)
+ barn_shrink(s, n->barn);
+
spin_lock_irqsave(&n->list_lock, flags);
/*
@@ -6005,12 +6891,24 @@ static int slab_mem_going_online_callback(void *arg)
*/
mutex_lock(&slab_mutex);
list_for_each_entry(s, &slab_caches, list) {
+ struct node_barn *barn = NULL;
+
/*
* The structure may already exist if the node was previously
* onlined and offlined.
*/
if (get_node(s, nid))
continue;
+
+ if (s->cpu_sheaves) {
+ barn = kmalloc_node(sizeof(*barn), GFP_KERNEL, nid);
+
+ if (!barn) {
+ ret = -ENOMEM;
+ goto out;
+ }
+ }
+
/*
* XXX: kmem_cache_alloc_node will fallback to other nodes
* since memory is not yet available from the node that
@@ -6021,7 +6919,9 @@ static int slab_mem_going_online_callback(void *arg)
ret = -ENOMEM;
goto out;
}
- init_kmem_cache_node(n);
+
+ init_kmem_cache_node(n, barn);
+
s->node[nid] = n;
}
/*
@@ -6240,6 +7140,16 @@ int do_kmem_cache_create(struct kmem_cache *s, const char *name,
set_cpu_partial(s);
+ if (args->sheaf_capacity) {
+ s->cpu_sheaves = alloc_percpu(struct slub_percpu_sheaves);
+ if (!s->cpu_sheaves) {
+ err = -ENOMEM;
+ goto out;
+ }
+ // TODO: increase capacity to grow slab_sheaf up to next kmalloc size?
+ s->sheaf_capacity = args->sheaf_capacity;
+ }
+
#ifdef CONFIG_NUMA
s->remote_node_defrag_ratio = 1000;
#endif
@@ -6256,6 +7166,12 @@ int do_kmem_cache_create(struct kmem_cache *s, const char *name,
if (!alloc_kmem_cache_cpus(s))
goto out;
+ if (s->cpu_sheaves) {
+ err = init_percpu_sheaves(s);
+ if (err)
+ goto out;
+ }
+
err = 0;
/* Mutex is not taken during early boot */
@@ -6277,7 +7193,6 @@ int do_kmem_cache_create(struct kmem_cache *s, const char *name,
__kmem_cache_release(s);
return err;
}
-
#ifdef SLAB_SUPPORTS_SYSFS
static int count_inuse(struct slab *slab)
{
@@ -7055,8 +7970,10 @@ static ssize_t text##_store(struct kmem_cache *s, \
} \
SLAB_ATTR(text); \
+STAT_ATTR(ALLOC_PCS, alloc_cpu_sheaf);
STAT_ATTR(ALLOC_FASTPATH, alloc_fastpath);
STAT_ATTR(ALLOC_SLOWPATH, alloc_slowpath);
+STAT_ATTR(FREE_PCS, free_cpu_sheaf);
STAT_ATTR(FREE_FASTPATH, free_fastpath);
STAT_ATTR(FREE_SLOWPATH, free_slowpath);
STAT_ATTR(FREE_FROZEN, free_frozen);
@@ -7081,6 +7998,12 @@ STAT_ATTR(CPU_PARTIAL_ALLOC, cpu_partial_alloc);
STAT_ATTR(CPU_PARTIAL_FREE, cpu_partial_free);
STAT_ATTR(CPU_PARTIAL_NODE, cpu_partial_node);
STAT_ATTR(CPU_PARTIAL_DRAIN, cpu_partial_drain);
+STAT_ATTR(SHEAF_FLUSH_MAIN, sheaf_flush_main);
+STAT_ATTR(SHEAF_FLUSH_OTHER, sheaf_flush_other);
+STAT_ATTR(SHEAF_REFILL, sheaf_refill);
+STAT_ATTR(SHEAF_SWAP, sheaf_swap);
+STAT_ATTR(SHEAF_ALLOC, sheaf_alloc);
+STAT_ATTR(SHEAF_FREE, sheaf_free);
#endif /* CONFIG_SLUB_STATS */
#ifdef CONFIG_KFENCE
@@ -7142,8 +8065,10 @@ static struct attribute *slab_attrs[] = {
&remote_node_defrag_ratio_attr.attr,
#endif
#ifdef CONFIG_SLUB_STATS
+ &alloc_cpu_sheaf_attr.attr,
&alloc_fastpath_attr.attr,
&alloc_slowpath_attr.attr,
+ &free_cpu_sheaf_attr.attr,
&free_fastpath_attr.attr,
&free_slowpath_attr.attr,
&free_frozen_attr.attr,
@@ -7168,6 +8093,12 @@ static struct attribute *slab_attrs[] = {
&cpu_partial_free_attr.attr,
&cpu_partial_node_attr.attr,
&cpu_partial_drain_attr.attr,
+ &sheaf_flush_main_attr.attr,
+ &sheaf_flush_other_attr.attr,
+ &sheaf_refill_attr.attr,
+ &sheaf_swap_attr.attr,
+ &sheaf_alloc_attr.attr,
+ &sheaf_free_attr.attr,
#endif
#ifdef CONFIG_FAILSLAB
&failslab_attr.attr,
--
2.48.1
^ permalink raw reply [flat|nested] 20+ messages in thread
* [PATCH RFC v3 3/8] slab: add sheaf support for batching kfree_rcu() operations
2025-03-17 14:33 [PATCH RFC v3 0/8] SLUB percpu sheaves Vlastimil Babka
2025-03-17 14:33 ` [PATCH RFC v3 1/8] locking/local_lock: Introduce localtry_lock_t Vlastimil Babka
2025-03-17 14:33 ` [PATCH RFC v3 2/8] slab: add opt-in caching layer of percpu sheaves Vlastimil Babka
@ 2025-03-17 14:33 ` Vlastimil Babka
2025-04-09 1:50 ` Harry Yoo
2025-04-10 20:24 ` Suren Baghdasaryan
2025-03-17 14:33 ` [PATCH RFC v3 4/8] slab: sheaf prefilling for guaranteed allocations Vlastimil Babka
` (4 subsequent siblings)
7 siblings, 2 replies; 20+ messages in thread
From: Vlastimil Babka @ 2025-03-17 14:33 UTC (permalink / raw)
To: Suren Baghdasaryan, Liam R. Howlett, Christoph Lameter, David Rientjes
Cc: Roman Gushchin, Harry Yoo, Uladzislau Rezki, linux-mm,
linux-kernel, rcu, maple-tree, vbabka
Extend the sheaf infrastructure for more efficient kfree_rcu() handling.
For caches with sheaves, on each cpu maintain a rcu_free sheaf in
addition to main and spare sheaves.
kfree_rcu() operations will try to put objects on this sheaf. Once full,
the sheaf is detached and submitted to call_rcu() with a handler that
will try to put it in the barn, or flush to slab pages using bulk free,
when the barn is full. Then a new empty sheaf must be obtained to put
more objects there.
It's possible that no free sheaves are available to use for a new
rcu_free sheaf, and the allocation in kfree_rcu() context can only use
GFP_NOWAIT and thus may fail. In that case, fall back to the existing
kfree_rcu() machinery.
Expected advantages:
- batching the kfree_rcu() operations, that could eventually replace the
existing batching
- sheaves can be reused for allocations via barn instead of being
flushed to slabs, which is more efficient
- this includes cases where only some cpus are allowed to process rcu
callbacks (Android)
Possible disadvantage:
- objects might be waiting for more than their grace period (it is
determined by the last object freed into the sheaf), increasing memory
usage - but the existing batching does that too?
Only implement this for CONFIG_KVFREE_RCU_BATCHED as the tiny
implementation favors smaller memory footprint over performance.
Signed-off-by: Vlastimil Babka <vbabka@suse.cz>
Reviewed-by: Suren Baghdasaryan <surenb@google.com>
---
mm/slab.h | 2 +
mm/slab_common.c | 24 ++++++++
mm/slub.c | 165 ++++++++++++++++++++++++++++++++++++++++++++++++++++++-
3 files changed, 189 insertions(+), 2 deletions(-)
diff --git a/mm/slab.h b/mm/slab.h
index 8daaec53b6ecfc44171191d421adb12e5cba2c58..94e9959e1aefa350d3d74e3f5309fde7a5cf2ec8 100644
--- a/mm/slab.h
+++ b/mm/slab.h
@@ -459,6 +459,8 @@ static inline bool is_kmalloc_normal(struct kmem_cache *s)
return !(s->flags & (SLAB_CACHE_DMA|SLAB_ACCOUNT|SLAB_RECLAIM_ACCOUNT));
}
+bool __kfree_rcu_sheaf(struct kmem_cache *s, void *obj);
+
/* Legal flag mask for kmem_cache_create(), for various configurations */
#define SLAB_CORE_FLAGS (SLAB_HWCACHE_ALIGN | SLAB_CACHE_DMA | \
SLAB_CACHE_DMA32 | SLAB_PANIC | \
diff --git a/mm/slab_common.c b/mm/slab_common.c
index ceeefb287899a82f30ad79b403556001c1860311..9496176770ed47491e01ed78e060a74771d5541e 100644
--- a/mm/slab_common.c
+++ b/mm/slab_common.c
@@ -1613,6 +1613,27 @@ static void kfree_rcu_work(struct work_struct *work)
kvfree_rcu_list(head);
}
+static bool kfree_rcu_sheaf(void *obj)
+{
+ struct kmem_cache *s;
+ struct folio *folio;
+ struct slab *slab;
+
+ if (is_vmalloc_addr(obj))
+ return false;
+
+ folio = virt_to_folio(obj);
+ if (unlikely(!folio_test_slab(folio)))
+ return false;
+
+ slab = folio_slab(folio);
+ s = slab->slab_cache;
+ if (s->cpu_sheaves)
+ return __kfree_rcu_sheaf(s, obj);
+
+ return false;
+}
+
static bool
need_offload_krc(struct kfree_rcu_cpu *krcp)
{
@@ -1957,6 +1978,9 @@ void kvfree_call_rcu(struct rcu_head *head, void *ptr)
if (!head)
might_sleep();
+ if (kfree_rcu_sheaf(ptr))
+ return;
+
// Queue the object but don't yet schedule the batch.
if (debug_rcu_head_queue(ptr)) {
// Probable double kfree_rcu(), just leak.
diff --git a/mm/slub.c b/mm/slub.c
index fa3a6329713a9f45b189f27d4b1b334b54589c38..83f4395267dccfbc144920baa7d0a85a27fbb1b4 100644
--- a/mm/slub.c
+++ b/mm/slub.c
@@ -350,6 +350,8 @@ enum stat_item {
ALLOC_FASTPATH, /* Allocation from cpu slab */
ALLOC_SLOWPATH, /* Allocation by getting a new cpu slab */
FREE_PCS, /* Free to percpu sheaf */
+ FREE_RCU_SHEAF, /* Free to rcu_free sheaf */
+ FREE_RCU_SHEAF_FAIL, /* Failed to free to a rcu_free sheaf */
FREE_FASTPATH, /* Free to cpu slab */
FREE_SLOWPATH, /* Freeing not to cpu slab */
FREE_FROZEN, /* Freeing to frozen slab */
@@ -442,6 +444,7 @@ struct slab_sheaf {
struct rcu_head rcu_head;
struct list_head barn_list;
};
+ struct kmem_cache *cache;
unsigned int size;
void *objects[];
};
@@ -450,6 +453,7 @@ struct slub_percpu_sheaves {
localtry_lock_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() */
struct node_barn *barn;
};
@@ -2461,6 +2465,8 @@ static struct slab_sheaf *alloc_empty_sheaf(struct kmem_cache *s, gfp_t gfp)
if (unlikely(!sheaf))
return NULL;
+ sheaf->cache = s;
+
stat(s, SHEAF_ALLOC);
return sheaf;
@@ -2585,6 +2591,24 @@ static void sheaf_flush_unused(struct kmem_cache *s, struct slab_sheaf *sheaf)
sheaf->size = 0;
}
+static void __rcu_free_sheaf_prepare(struct kmem_cache *s,
+ struct slab_sheaf *sheaf);
+
+static void rcu_free_sheaf_nobarn(struct rcu_head *head)
+{
+ struct slab_sheaf *sheaf;
+ struct kmem_cache *s;
+
+ sheaf = container_of(head, struct slab_sheaf, rcu_head);
+ s = sheaf->cache;
+
+ __rcu_free_sheaf_prepare(s, sheaf);
+
+ sheaf_flush_unused(s, sheaf);
+
+ free_empty_sheaf(s, sheaf);
+}
+
/*
* Caller needs to make sure migration is disabled in order to fully flush
* single cpu's sheaves
@@ -2597,7 +2621,7 @@ static void sheaf_flush_unused(struct kmem_cache *s, struct slab_sheaf *sheaf)
static void pcs_flush_all(struct kmem_cache *s)
{
struct slub_percpu_sheaves *pcs;
- struct slab_sheaf *spare;
+ struct slab_sheaf *spare, *rcu_free;
localtry_lock(&s->cpu_sheaves->lock);
pcs = this_cpu_ptr(s->cpu_sheaves);
@@ -2605,6 +2629,9 @@ static void pcs_flush_all(struct kmem_cache *s)
spare = pcs->spare;
pcs->spare = NULL;
+ rcu_free = pcs->rcu_free;
+ pcs->rcu_free = NULL;
+
localtry_unlock(&s->cpu_sheaves->lock);
if (spare) {
@@ -2612,6 +2639,9 @@ static void pcs_flush_all(struct kmem_cache *s)
free_empty_sheaf(s, spare);
}
+ if (rcu_free)
+ call_rcu(&rcu_free->rcu_head, rcu_free_sheaf_nobarn);
+
sheaf_flush_main(s);
}
@@ -2628,6 +2658,11 @@ static void __pcs_flush_all_cpu(struct kmem_cache *s, unsigned int cpu)
free_empty_sheaf(s, pcs->spare);
pcs->spare = NULL;
}
+
+ if (pcs->rcu_free) {
+ call_rcu(&pcs->rcu_free->rcu_head, rcu_free_sheaf_nobarn);
+ pcs->rcu_free = NULL;
+ }
}
static void pcs_destroy(struct kmem_cache *s)
@@ -2644,6 +2679,7 @@ static void pcs_destroy(struct kmem_cache *s)
continue;
WARN_ON(pcs->spare);
+ WARN_ON(pcs->rcu_free);
if (!WARN_ON(pcs->main->size)) {
free_empty_sheaf(s, pcs->main);
@@ -3707,7 +3743,7 @@ static bool has_pcs_used(int cpu, struct kmem_cache *s)
pcs = per_cpu_ptr(s->cpu_sheaves, cpu);
- return (pcs->spare || pcs->main->size);
+ return (pcs->spare || pcs->rcu_free || pcs->main->size);
}
static void pcs_flush_all(struct kmem_cache *s);
@@ -5240,6 +5276,122 @@ bool free_to_pcs(struct kmem_cache *s, void *object)
return true;
}
+static void __rcu_free_sheaf_prepare(struct kmem_cache *s,
+ struct slab_sheaf *sheaf)
+{
+ bool init = slab_want_init_on_free(s);
+ void **p = &sheaf->objects[0];
+ unsigned int i = 0;
+
+ while (i < sheaf->size) {
+ struct slab *slab = virt_to_slab(p[i]);
+
+ memcg_slab_free_hook(s, slab, p + i, 1);
+ alloc_tagging_slab_free_hook(s, slab, p + i, 1);
+
+ if (unlikely(!slab_free_hook(s, p[i], init, false))) {
+ p[i] = p[--sheaf->size];
+ continue;
+ }
+
+ i++;
+ }
+}
+
+static void rcu_free_sheaf(struct rcu_head *head)
+{
+ struct slab_sheaf *sheaf;
+ struct node_barn *barn;
+ struct kmem_cache *s;
+
+ sheaf = container_of(head, struct slab_sheaf, rcu_head);
+
+ s = sheaf->cache;
+
+ __rcu_free_sheaf_prepare(s, sheaf);
+
+ barn = get_node(s, numa_mem_id())->barn;
+
+ /* due to slab_free_hook() */
+ if (unlikely(sheaf->size == 0))
+ goto empty;
+
+ if (!barn_put_full_sheaf(barn, sheaf, false))
+ return;
+
+ sheaf_flush_unused(s, sheaf);
+
+empty:
+ if (!barn_put_empty_sheaf(barn, sheaf, false))
+ return;
+
+ free_empty_sheaf(s, sheaf);
+}
+
+bool __kfree_rcu_sheaf(struct kmem_cache *s, void *obj)
+{
+ struct slub_percpu_sheaves *pcs;
+ struct slab_sheaf *rcu_sheaf;
+
+ if (!localtry_trylock(&s->cpu_sheaves->lock))
+ goto fail;
+
+ pcs = this_cpu_ptr(s->cpu_sheaves);
+
+ if (unlikely(!pcs->rcu_free)) {
+
+ struct slab_sheaf *empty;
+
+ empty = barn_get_empty_sheaf(pcs->barn);
+
+ if (empty) {
+ pcs->rcu_free = empty;
+ goto do_free;
+ }
+
+ localtry_unlock(&s->cpu_sheaves->lock);
+
+ empty = alloc_empty_sheaf(s, GFP_NOWAIT);
+
+ if (!empty)
+ goto fail;
+
+ if (!localtry_trylock(&s->cpu_sheaves->lock))
+ goto fail;
+
+ pcs = this_cpu_ptr(s->cpu_sheaves);
+
+ if (unlikely(pcs->rcu_free))
+ barn_put_empty_sheaf(pcs->barn, empty, true);
+ else
+ pcs->rcu_free = empty;
+ }
+
+do_free:
+
+ rcu_sheaf = pcs->rcu_free;
+
+ rcu_sheaf->objects[rcu_sheaf->size++] = obj;
+
+ if (likely(rcu_sheaf->size < s->sheaf_capacity)) {
+ localtry_unlock(&s->cpu_sheaves->lock);
+ stat(s, FREE_RCU_SHEAF);
+ return true;
+ }
+
+ pcs->rcu_free = NULL;
+ localtry_unlock(&s->cpu_sheaves->lock);
+
+ call_rcu(&rcu_sheaf->rcu_head, rcu_free_sheaf);
+
+ stat(s, FREE_RCU_SHEAF);
+ return true;
+
+fail:
+ stat(s, FREE_RCU_SHEAF_FAIL);
+ return false;
+}
+
/*
* Bulk free objects to the percpu sheaves.
* Unlike free_to_pcs() this includes the calls to all necessary hooks
@@ -6569,6 +6721,11 @@ int __kmem_cache_shutdown(struct kmem_cache *s)
struct kmem_cache_node *n;
flush_all_cpus_locked(s);
+
+ /* we might have rcu sheaves in flight */
+ if (s->cpu_sheaves)
+ rcu_barrier();
+
/* Attempt to free all objects */
for_each_kmem_cache_node(s, node, n) {
if (n->barn)
@@ -7974,6 +8131,8 @@ STAT_ATTR(ALLOC_PCS, alloc_cpu_sheaf);
STAT_ATTR(ALLOC_FASTPATH, alloc_fastpath);
STAT_ATTR(ALLOC_SLOWPATH, alloc_slowpath);
STAT_ATTR(FREE_PCS, free_cpu_sheaf);
+STAT_ATTR(FREE_RCU_SHEAF, free_rcu_sheaf);
+STAT_ATTR(FREE_RCU_SHEAF_FAIL, free_rcu_sheaf_fail);
STAT_ATTR(FREE_FASTPATH, free_fastpath);
STAT_ATTR(FREE_SLOWPATH, free_slowpath);
STAT_ATTR(FREE_FROZEN, free_frozen);
@@ -8069,6 +8228,8 @@ static struct attribute *slab_attrs[] = {
&alloc_fastpath_attr.attr,
&alloc_slowpath_attr.attr,
&free_cpu_sheaf_attr.attr,
+ &free_rcu_sheaf_attr.attr,
+ &free_rcu_sheaf_fail_attr.attr,
&free_fastpath_attr.attr,
&free_slowpath_attr.attr,
&free_frozen_attr.attr,
--
2.48.1
^ permalink raw reply [flat|nested] 20+ messages in thread
* [PATCH RFC v3 4/8] slab: sheaf prefilling for guaranteed allocations
2025-03-17 14:33 [PATCH RFC v3 0/8] SLUB percpu sheaves Vlastimil Babka
` (2 preceding siblings ...)
2025-03-17 14:33 ` [PATCH RFC v3 3/8] slab: add sheaf support for batching kfree_rcu() operations Vlastimil Babka
@ 2025-03-17 14:33 ` Vlastimil Babka
2025-04-10 20:47 ` Suren Baghdasaryan
2025-03-17 14:33 ` [PATCH RFC v3 5/8] slab: determine barn status racily outside of lock Vlastimil Babka
` (3 subsequent siblings)
7 siblings, 1 reply; 20+ messages in thread
From: Vlastimil Babka @ 2025-03-17 14:33 UTC (permalink / raw)
To: Suren Baghdasaryan, Liam R. Howlett, Christoph Lameter, David Rientjes
Cc: Roman Gushchin, Harry Yoo, Uladzislau Rezki, linux-mm,
linux-kernel, rcu, maple-tree, vbabka
Add functions for efficient guaranteed allocations e.g. in a critical
section that cannot sleep, when the exact number of allocations is not
known beforehand, but an upper limit can be calculated.
kmem_cache_prefill_sheaf() returns a sheaf containing at least given
number of objects.
kmem_cache_alloc_from_sheaf() will allocate an object from the sheaf
and is guaranteed not to fail until depleted.
kmem_cache_return_sheaf() is for giving the sheaf back to the slab
allocator after the critical section. This will also attempt to refill
it to cache's sheaf capacity for better efficiency of sheaves handling,
but it's not stricly necessary to succeed.
kmem_cache_refill_sheaf() can be used to refill a previously obtained
sheaf to requested size. If the current size is sufficient, it does
nothing. If the requested size exceeds cache's sheaf_capacity and the
sheaf's current capacity, the sheaf will be replaced with a new one,
hence the indirect pointer parameter.
kmem_cache_sheaf_size() can be used to query the current size.
The implementation supports requesting sizes that exceed cache's
sheaf_capacity, but it is not efficient - such sheaves are allocated
fresh in kmem_cache_prefill_sheaf() and flushed and freed immediately by
kmem_cache_return_sheaf(). kmem_cache_refill_sheaf() might be especially
ineffective when replacing a sheaf with a new one of a larger capacity.
It is therefore better to size cache's sheaf_capacity accordingly.
Signed-off-by: Vlastimil Babka <vbabka@suse.cz>
Reviewed-by: Suren Baghdasaryan <surenb@google.com>
---
include/linux/slab.h | 16 ++++
mm/slub.c | 228 +++++++++++++++++++++++++++++++++++++++++++++++++++
2 files changed, 244 insertions(+)
diff --git a/include/linux/slab.h b/include/linux/slab.h
index 0e1b25228c77140d05b5b4433c9d7923de36ec05..dd01b67982e856b1b02f4f0e6fc557726e7f02a8 100644
--- a/include/linux/slab.h
+++ b/include/linux/slab.h
@@ -829,6 +829,22 @@ void *kmem_cache_alloc_node_noprof(struct kmem_cache *s, gfp_t flags,
int node) __assume_slab_alignment __malloc;
#define kmem_cache_alloc_node(...) alloc_hooks(kmem_cache_alloc_node_noprof(__VA_ARGS__))
+struct slab_sheaf *
+kmem_cache_prefill_sheaf(struct kmem_cache *s, gfp_t gfp, unsigned int size);
+
+int kmem_cache_refill_sheaf(struct kmem_cache *s, gfp_t gfp,
+ struct slab_sheaf **sheafp, unsigned int size);
+
+void kmem_cache_return_sheaf(struct kmem_cache *s, gfp_t gfp,
+ struct slab_sheaf *sheaf);
+
+void *kmem_cache_alloc_from_sheaf_noprof(struct kmem_cache *cachep, gfp_t gfp,
+ struct slab_sheaf *sheaf) __assume_slab_alignment __malloc;
+#define kmem_cache_alloc_from_sheaf(...) \
+ alloc_hooks(kmem_cache_alloc_from_sheaf_noprof(__VA_ARGS__))
+
+unsigned int kmem_cache_sheaf_size(struct slab_sheaf *sheaf);
+
/*
* These macros allow declaring a kmem_buckets * parameter alongside size, which
* can be compiled out with CONFIG_SLAB_BUCKETS=n so that a large number of call
diff --git a/mm/slub.c b/mm/slub.c
index 83f4395267dccfbc144920baa7d0a85a27fbb1b4..ab3532d5f41045d8268b12ad774541dcd066c4c4 100644
--- a/mm/slub.c
+++ b/mm/slub.c
@@ -443,6 +443,8 @@ struct slab_sheaf {
union {
struct rcu_head rcu_head;
struct list_head barn_list;
+ /* only used for prefilled sheafs */
+ unsigned int capacity;
};
struct kmem_cache *cache;
unsigned int size;
@@ -2748,6 +2750,30 @@ static int barn_put_full_sheaf(struct node_barn *barn, struct slab_sheaf *sheaf,
return ret;
}
+static struct slab_sheaf *barn_get_full_or_empty_sheaf(struct node_barn *barn)
+{
+ struct slab_sheaf *sheaf = NULL;
+ unsigned long flags;
+
+ spin_lock_irqsave(&barn->lock, flags);
+
+ if (barn->nr_full) {
+ sheaf = list_first_entry(&barn->sheaves_full, struct slab_sheaf,
+ barn_list);
+ list_del(&sheaf->barn_list);
+ barn->nr_full--;
+ } else if (barn->nr_empty) {
+ sheaf = list_first_entry(&barn->sheaves_empty,
+ struct slab_sheaf, barn_list);
+ list_del(&sheaf->barn_list);
+ barn->nr_empty--;
+ }
+
+ spin_unlock_irqrestore(&barn->lock, flags);
+
+ return sheaf;
+}
+
/*
* If a full sheaf is available, return it and put the supplied empty one to
* barn. We ignore the limit on empty sheaves as the number of sheaves doesn't
@@ -4844,6 +4870,208 @@ void *kmem_cache_alloc_node_noprof(struct kmem_cache *s, gfp_t gfpflags, int nod
}
EXPORT_SYMBOL(kmem_cache_alloc_node_noprof);
+/*
+ * returns a sheaf that has least the requested size
+ * when prefilling is needed, do so with given gfp flags
+ *
+ * return NULL if sheaf allocation or prefilling failed
+ */
+struct slab_sheaf *
+kmem_cache_prefill_sheaf(struct kmem_cache *s, gfp_t gfp, unsigned int size)
+{
+ struct slub_percpu_sheaves *pcs;
+ struct slab_sheaf *sheaf = NULL;
+
+ if (unlikely(size > s->sheaf_capacity)) {
+ sheaf = kzalloc(struct_size(sheaf, objects, size), gfp);
+ if (!sheaf)
+ return NULL;
+
+ sheaf->cache = s;
+ sheaf->capacity = size;
+
+ if (!__kmem_cache_alloc_bulk(s, gfp, size,
+ &sheaf->objects[0])) {
+ kfree(sheaf);
+ return NULL;
+ }
+
+ sheaf->size = size;
+
+ return sheaf;
+ }
+
+ localtry_lock(&s->cpu_sheaves->lock);
+ pcs = this_cpu_ptr(s->cpu_sheaves);
+
+ if (pcs->spare) {
+ sheaf = pcs->spare;
+ pcs->spare = NULL;
+ }
+
+ if (!sheaf)
+ sheaf = barn_get_full_or_empty_sheaf(pcs->barn);
+
+ localtry_unlock(&s->cpu_sheaves->lock);
+
+ if (!sheaf)
+ sheaf = alloc_empty_sheaf(s, gfp);
+
+ if (sheaf && sheaf->size < size) {
+ if (refill_sheaf(s, sheaf, gfp)) {
+ sheaf_flush_unused(s, sheaf);
+ free_empty_sheaf(s, sheaf);
+ sheaf = NULL;
+ }
+ }
+
+ if (sheaf)
+ sheaf->capacity = s->sheaf_capacity;
+
+ return sheaf;
+}
+
+/*
+ * Use this to return a sheaf obtained by kmem_cache_prefill_sheaf()
+ *
+ * If the sheaf cannot simply become the percpu spare sheaf, but there's space
+ * for a full sheaf in the barn, we try to refill the sheaf back to the cache's
+ * sheaf_capacity to avoid handling partially full sheaves.
+ *
+ * If the refill fails because gfp is e.g. GFP_NOWAIT, or the barn is full, the
+ * sheaf is instead flushed and freed.
+ */
+void kmem_cache_return_sheaf(struct kmem_cache *s, gfp_t gfp,
+ struct slab_sheaf *sheaf)
+{
+ struct slub_percpu_sheaves *pcs;
+ bool refill = false;
+ struct node_barn *barn;
+
+ if (unlikely(sheaf->capacity != s->sheaf_capacity)) {
+ sheaf_flush_unused(s, sheaf);
+ kfree(sheaf);
+ return;
+ }
+
+ localtry_lock(&s->cpu_sheaves->lock);
+ pcs = this_cpu_ptr(s->cpu_sheaves);
+
+ if (!pcs->spare) {
+ pcs->spare = sheaf;
+ sheaf = NULL;
+ } else if (data_race(pcs->barn->nr_full) < MAX_FULL_SHEAVES) {
+ barn = pcs->barn;
+ refill = true;
+ }
+
+ localtry_unlock(&s->cpu_sheaves->lock);
+
+ if (!sheaf)
+ return;
+
+ /*
+ * if the barn is full of full sheaves or we fail to refill the sheaf,
+ * simply flush and free it
+ */
+ if (!refill || refill_sheaf(s, sheaf, gfp)) {
+ sheaf_flush_unused(s, sheaf);
+ free_empty_sheaf(s, sheaf);
+ return;
+ }
+
+ /* we racily determined the sheaf would fit, so now force it */
+ barn_put_full_sheaf(barn, sheaf, true);
+}
+
+/*
+ * refill a sheaf previously returned by kmem_cache_prefill_sheaf to at least
+ * the given size
+ *
+ * the sheaf might be replaced by a new one when requesting more than
+ * s->sheaf_capacity objects if such replacement is necessary, but the refill
+ * fails (returning -ENOMEM), the existing sheaf is left intact
+ *
+ * In practice we always refill to full sheaf's capacity.
+ */
+int kmem_cache_refill_sheaf(struct kmem_cache *s, gfp_t gfp,
+ struct slab_sheaf **sheafp, unsigned int size)
+{
+ struct slab_sheaf *sheaf;
+
+ /*
+ * TODO: do we want to support *sheaf == NULL to be equivalent of
+ * kmem_cache_prefill_sheaf() ?
+ */
+ if (!sheafp || !(*sheafp))
+ return -EINVAL;
+
+ sheaf = *sheafp;
+ if (sheaf->size >= size)
+ return 0;
+
+ if (likely(sheaf->capacity >= size)) {
+ if (likely(sheaf->capacity == s->sheaf_capacity))
+ return refill_sheaf(s, sheaf, gfp);
+
+ if (!__kmem_cache_alloc_bulk(s, gfp, sheaf->capacity - sheaf->size,
+ &sheaf->objects[sheaf->size])) {
+ return -ENOMEM;
+ }
+ sheaf->size = sheaf->capacity;
+
+ return 0;
+ }
+
+ /*
+ * We had a regular sized sheaf and need an oversize one, or we had an
+ * oversize one already but need a larger one now.
+ * This should be a very rare path so let's not complicate it.
+ */
+ sheaf = kmem_cache_prefill_sheaf(s, gfp, size);
+ if (!sheaf)
+ return -ENOMEM;
+
+ kmem_cache_return_sheaf(s, gfp, *sheafp);
+ *sheafp = sheaf;
+ return 0;
+}
+
+/*
+ * Allocate from a sheaf obtained by kmem_cache_prefill_sheaf()
+ *
+ * Guaranteed not to fail as many allocations as was the requested size.
+ * After the sheaf is emptied, it fails - no fallback to the slab cache itself.
+ *
+ * The gfp parameter is meant only to specify __GFP_ZERO or __GFP_ACCOUNT
+ * memcg charging is forced over limit if necessary, to avoid failure.
+ */
+void *
+kmem_cache_alloc_from_sheaf_noprof(struct kmem_cache *s, gfp_t gfp,
+ struct slab_sheaf *sheaf)
+{
+ void *ret = NULL;
+ bool init;
+
+ if (sheaf->size == 0)
+ goto out;
+
+ ret = sheaf->objects[--sheaf->size];
+
+ init = slab_want_init_on_alloc(gfp, s);
+
+ /* add __GFP_NOFAIL to force successful memcg charging */
+ slab_post_alloc_hook(s, NULL, gfp | __GFP_NOFAIL, 1, &ret, init, s->object_size);
+out:
+ trace_kmem_cache_alloc(_RET_IP_, ret, s, gfp, NUMA_NO_NODE);
+
+ return ret;
+}
+
+unsigned int kmem_cache_sheaf_size(struct slab_sheaf *sheaf)
+{
+ return sheaf->size;
+}
/*
* To avoid unnecessary overhead, we pass through large allocation requests
* directly to the page allocator. We use __GFP_COMP, because we will need to
--
2.48.1
^ permalink raw reply [flat|nested] 20+ messages in thread
* [PATCH RFC v3 5/8] slab: determine barn status racily outside of lock
2025-03-17 14:33 [PATCH RFC v3 0/8] SLUB percpu sheaves Vlastimil Babka
` (3 preceding siblings ...)
2025-03-17 14:33 ` [PATCH RFC v3 4/8] slab: sheaf prefilling for guaranteed allocations Vlastimil Babka
@ 2025-03-17 14:33 ` Vlastimil Babka
2025-03-17 14:33 ` [PATCH RFC v3 6/8] tools: Add testing support for changes to rcu and slab for sheaves Vlastimil Babka
` (2 subsequent siblings)
7 siblings, 0 replies; 20+ messages in thread
From: Vlastimil Babka @ 2025-03-17 14:33 UTC (permalink / raw)
To: Suren Baghdasaryan, Liam R. Howlett, Christoph Lameter, David Rientjes
Cc: Roman Gushchin, Harry Yoo, Uladzislau Rezki, linux-mm,
linux-kernel, rcu, maple-tree, vbabka
The possibility of many barn operations is determined by the current
number of full or empty sheaves. Taking the barn->lock just to find out
that e.g. there are no empty sheaves results in unnecessary overhead and
lock contention. Thus perform these checks outside of the lock with a
data_race() annotated variable read and fail quickly without taking the
lock.
Checks for sheaf availability that racily succeed have to be obviously
repeated under the lock for correctness, but we can skip repeating
checks if there are too many sheaves on the given list as the limits
don't need to be strict.
Signed-off-by: Vlastimil Babka <vbabka@suse.cz>
Reviewed-by: Suren Baghdasaryan <surenb@google.com>
Reviewed-by: Harry Yoo <harry.yoo@oracle.com>
---
mm/slub.c | 57 ++++++++++++++++++++++++++++++++++-----------------------
1 file changed, 34 insertions(+), 23 deletions(-)
diff --git a/mm/slub.c b/mm/slub.c
index ab3532d5f41045d8268b12ad774541dcd066c4c4..2c7b2a85c628d01fa4811dd6cd3e4fd198d80381 100644
--- a/mm/slub.c
+++ b/mm/slub.c
@@ -2698,9 +2698,12 @@ static struct slab_sheaf *barn_get_empty_sheaf(struct node_barn *barn)
struct slab_sheaf *empty = NULL;
unsigned long flags;
+ if (!data_race(barn->nr_empty))
+ return NULL;
+
spin_lock_irqsave(&barn->lock, flags);
- if (barn->nr_empty) {
+ if (likely(barn->nr_empty)) {
empty = list_first_entry(&barn->sheaves_empty,
struct slab_sheaf, barn_list);
list_del(&empty->barn_list);
@@ -2716,38 +2719,36 @@ static int barn_put_empty_sheaf(struct node_barn *barn,
struct slab_sheaf *sheaf, bool ignore_limit)
{
unsigned long flags;
- int ret = 0;
+
+ /* we don't repeat the check under barn->lock as it's not critical */
+ if (!ignore_limit && data_race(barn->nr_empty) >= MAX_EMPTY_SHEAVES)
+ return -E2BIG;
spin_lock_irqsave(&barn->lock, flags);
- if (!ignore_limit && barn->nr_empty >= MAX_EMPTY_SHEAVES) {
- ret = -E2BIG;
- } else {
- list_add(&sheaf->barn_list, &barn->sheaves_empty);
- barn->nr_empty++;
- }
+ list_add(&sheaf->barn_list, &barn->sheaves_empty);
+ barn->nr_empty++;
spin_unlock_irqrestore(&barn->lock, flags);
- return ret;
+ return 0;
}
static int barn_put_full_sheaf(struct node_barn *barn, struct slab_sheaf *sheaf,
bool ignore_limit)
{
unsigned long flags;
- int ret = 0;
+
+ /* we don't repeat the check under barn->lock as it's not critical */
+ if (!ignore_limit && data_race(barn->nr_full) >= MAX_FULL_SHEAVES)
+ return -E2BIG;
spin_lock_irqsave(&barn->lock, flags);
- if (!ignore_limit && barn->nr_full >= MAX_FULL_SHEAVES) {
- ret = -E2BIG;
- } else {
- list_add(&sheaf->barn_list, &barn->sheaves_full);
- barn->nr_full++;
- }
+ list_add(&sheaf->barn_list, &barn->sheaves_full);
+ barn->nr_full++;
spin_unlock_irqrestore(&barn->lock, flags);
- return ret;
+ return 0;
}
static struct slab_sheaf *barn_get_full_or_empty_sheaf(struct node_barn *barn)
@@ -2755,6 +2756,9 @@ static struct slab_sheaf *barn_get_full_or_empty_sheaf(struct node_barn *barn)
struct slab_sheaf *sheaf = NULL;
unsigned long flags;
+ if (!data_race(barn->nr_full) && !data_race(barn->nr_empty))
+ return NULL;
+
spin_lock_irqsave(&barn->lock, flags);
if (barn->nr_full) {
@@ -2785,9 +2789,12 @@ barn_replace_empty_sheaf(struct node_barn *barn, struct slab_sheaf *empty)
struct slab_sheaf *full = NULL;
unsigned long flags;
+ if (!data_race(barn->nr_full))
+ return NULL;
+
spin_lock_irqsave(&barn->lock, flags);
- if (barn->nr_full) {
+ if (likely(barn->nr_full)) {
full = list_first_entry(&barn->sheaves_full, struct slab_sheaf,
barn_list);
list_del(&full->barn_list);
@@ -2810,19 +2817,23 @@ barn_replace_full_sheaf(struct node_barn *barn, struct slab_sheaf *full)
struct slab_sheaf *empty;
unsigned long flags;
+ /* we don't repeat this check under barn->lock as it's not critical */
+ if (data_race(barn->nr_full) >= MAX_FULL_SHEAVES)
+ return ERR_PTR(-E2BIG);
+ if (!data_race(barn->nr_empty))
+ return ERR_PTR(-ENOMEM);
+
spin_lock_irqsave(&barn->lock, flags);
- if (barn->nr_full >= MAX_FULL_SHEAVES) {
- empty = ERR_PTR(-E2BIG);
- } else if (!barn->nr_empty) {
- empty = ERR_PTR(-ENOMEM);
- } else {
+ if (likely(barn->nr_empty)) {
empty = list_first_entry(&barn->sheaves_empty, struct slab_sheaf,
barn_list);
list_del(&empty->barn_list);
list_add(&full->barn_list, &barn->sheaves_full);
barn->nr_empty--;
barn->nr_full++;
+ } else {
+ empty = ERR_PTR(-ENOMEM);
}
spin_unlock_irqrestore(&barn->lock, flags);
--
2.48.1
^ permalink raw reply [flat|nested] 20+ messages in thread
* [PATCH RFC v3 6/8] tools: Add testing support for changes to rcu and slab for sheaves
2025-03-17 14:33 [PATCH RFC v3 0/8] SLUB percpu sheaves Vlastimil Babka
` (4 preceding siblings ...)
2025-03-17 14:33 ` [PATCH RFC v3 5/8] slab: determine barn status racily outside of lock Vlastimil Babka
@ 2025-03-17 14:33 ` Vlastimil Babka
2025-03-17 14:33 ` [PATCH RFC v3 7/8] tools: Add sheafs support to testing infrastructure Vlastimil Babka
2025-03-17 14:33 ` [PATCH RFC v3 8/8] maple_tree: use percpu sheaves for maple_node_cache Vlastimil Babka
7 siblings, 0 replies; 20+ messages in thread
From: Vlastimil Babka @ 2025-03-17 14:33 UTC (permalink / raw)
To: Suren Baghdasaryan, Liam R. Howlett, Christoph Lameter, David Rientjes
Cc: Roman Gushchin, Harry Yoo, Uladzislau Rezki, linux-mm,
linux-kernel, rcu, maple-tree, vbabka, Liam R. Howlett
From: "Liam R. Howlett" <Liam.Howlett@Oracle.com>
Make testing work for the slab and rcu changes that have come in with
the sheaves work.
This only works with one kmem_cache, and only the first one used.
Subsequent setting of kmem_cache will not update the active kmem_cache
and will be silently dropped because there are other tests which happen
after the kmem_cache of interest is set.
The saved active kmem_cache is used in the rcu callback, which passes
the object to be freed.
The rcu call takes the rcu_head, which is passed in as the field in the
struct (in this case rcu in the maple tree node), which is calculated by
pointer math. The offset of which is saved (in a global variable) for
restoring the node pointer on the callback after the rcu grace period
expires.
Don't use any of this outside of testing, please.
Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>
---
tools/include/linux/slab.h | 41 ++++++++++++++++++++++++++++++++---
tools/testing/shared/linux.c | 24 ++++++++++++++++----
tools/testing/shared/linux/rcupdate.h | 22 +++++++++++++++++++
3 files changed, 80 insertions(+), 7 deletions(-)
diff --git a/tools/include/linux/slab.h b/tools/include/linux/slab.h
index 51b25e9c4ec7b66bdf4c68cc1353c6faf1ca7bb8..a475364cfd9fcdb10db252aab18ea3a620326b6b 100644
--- a/tools/include/linux/slab.h
+++ b/tools/include/linux/slab.h
@@ -22,6 +22,12 @@ enum slab_state {
FULL
};
+struct kmem_cache_args {
+ unsigned int align;
+ unsigned int sheaf_capacity;
+ void (*ctor)(void *);
+};
+
static inline void *kzalloc(size_t size, gfp_t gfp)
{
return kmalloc(size, gfp | __GFP_ZERO);
@@ -36,9 +42,38 @@ static inline void *kmem_cache_alloc(struct kmem_cache *cachep, int flags)
}
void kmem_cache_free(struct kmem_cache *cachep, void *objp);
-struct kmem_cache *kmem_cache_create(const char *name, unsigned int size,
- unsigned int align, unsigned int flags,
- void (*ctor)(void *));
+
+struct kmem_cache *
+__kmem_cache_create_args(const char *name, unsigned int size,
+ struct kmem_cache_args *args, unsigned int flags);
+
+/* If NULL is passed for @args, use this variant with default arguments. */
+static inline struct kmem_cache *
+__kmem_cache_default_args(const char *name, unsigned int size,
+ struct kmem_cache_args *args, unsigned int flags)
+{
+ struct kmem_cache_args kmem_default_args = {};
+
+ return __kmem_cache_create_args(name, size, &kmem_default_args, flags);
+}
+
+static inline struct kmem_cache *
+__kmem_cache_create(const char *name, unsigned int size, unsigned int align,
+ unsigned int flags, void (*ctor)(void *))
+{
+ struct kmem_cache_args kmem_args = {
+ .align = align,
+ .ctor = ctor,
+ };
+
+ return __kmem_cache_create_args(name, size, &kmem_args, flags);
+}
+
+#define kmem_cache_create(__name, __object_size, __args, ...) \
+ _Generic((__args), \
+ struct kmem_cache_args *: __kmem_cache_create_args, \
+ void *: __kmem_cache_default_args, \
+ default: __kmem_cache_create)(__name, __object_size, __args, __VA_ARGS__)
void kmem_cache_free_bulk(struct kmem_cache *cachep, size_t size, void **list);
int kmem_cache_alloc_bulk(struct kmem_cache *cachep, gfp_t gfp, size_t size,
diff --git a/tools/testing/shared/linux.c b/tools/testing/shared/linux.c
index 66dbb362385f3c3d923233448cc591adfe6dc9e7..9f5fd722f27f1d3877be8927be30409cd74ab3c3 100644
--- a/tools/testing/shared/linux.c
+++ b/tools/testing/shared/linux.c
@@ -20,6 +20,7 @@ struct kmem_cache {
pthread_mutex_t lock;
unsigned int size;
unsigned int align;
+ unsigned int sheaf_capacity;
int nr_objs;
void *objs;
void (*ctor)(void *);
@@ -31,6 +32,8 @@ struct kmem_cache {
void *private;
};
+static struct kmem_cache *kmem_active = NULL;
+
void kmem_cache_set_callback(struct kmem_cache *cachep, void (*callback)(void *))
{
cachep->callback = callback;
@@ -147,6 +150,14 @@ void kmem_cache_free(struct kmem_cache *cachep, void *objp)
pthread_mutex_unlock(&cachep->lock);
}
+void kmem_cache_free_active(void *objp)
+{
+ if (!kmem_active)
+ printf("WARNING: No active kmem_cache\n");
+
+ kmem_cache_free(kmem_active, objp);
+}
+
void kmem_cache_free_bulk(struct kmem_cache *cachep, size_t size, void **list)
{
if (kmalloc_verbose)
@@ -234,23 +245,28 @@ int kmem_cache_alloc_bulk(struct kmem_cache *cachep, gfp_t gfp, size_t size,
}
struct kmem_cache *
-kmem_cache_create(const char *name, unsigned int size, unsigned int align,
- unsigned int flags, void (*ctor)(void *))
+__kmem_cache_create_args(const char *name, unsigned int size,
+ struct kmem_cache_args *args,
+ unsigned int flags)
{
struct kmem_cache *ret = malloc(sizeof(*ret));
pthread_mutex_init(&ret->lock, NULL);
ret->size = size;
- ret->align = align;
+ ret->align = args->align;
+ ret->sheaf_capacity = args->sheaf_capacity;
ret->nr_objs = 0;
ret->nr_allocated = 0;
ret->nr_tallocated = 0;
ret->objs = NULL;
- ret->ctor = ctor;
+ ret->ctor = args->ctor;
ret->non_kernel = 0;
ret->exec_callback = false;
ret->callback = NULL;
ret->private = NULL;
+ if (!kmem_active)
+ kmem_active = ret;
+
return ret;
}
diff --git a/tools/testing/shared/linux/rcupdate.h b/tools/testing/shared/linux/rcupdate.h
index fed468fb0c78db6f33fb1900c7110ab5f3c19c65..c95e2f0bbd93798e544d7d34e0823ed68414f924 100644
--- a/tools/testing/shared/linux/rcupdate.h
+++ b/tools/testing/shared/linux/rcupdate.h
@@ -9,4 +9,26 @@
#define rcu_dereference_check(p, cond) rcu_dereference(p)
#define RCU_INIT_POINTER(p, v) do { (p) = (v); } while (0)
+void kmem_cache_free_active(void *objp);
+static unsigned long kfree_cb_offset = 0;
+
+static inline void kfree_rcu_cb(struct rcu_head *head)
+{
+ void *objp = (void *) ((unsigned long)head - kfree_cb_offset);
+
+ kmem_cache_free_active(objp);
+}
+
+#ifndef offsetof
+#define offsetof(TYPE, MEMBER) __builtin_offsetof(TYPE, MEMBER)
+#endif
+
+#define kfree_rcu(ptr, rhv) \
+do { \
+ if (!kfree_cb_offset) \
+ kfree_cb_offset = offsetof(typeof(*(ptr)), rhv); \
+ \
+ call_rcu(&ptr->rhv, kfree_rcu_cb); \
+} while (0)
+
#endif
--
2.48.1
^ permalink raw reply [flat|nested] 20+ messages in thread
* [PATCH RFC v3 7/8] tools: Add sheafs support to testing infrastructure
2025-03-17 14:33 [PATCH RFC v3 0/8] SLUB percpu sheaves Vlastimil Babka
` (5 preceding siblings ...)
2025-03-17 14:33 ` [PATCH RFC v3 6/8] tools: Add testing support for changes to rcu and slab for sheaves Vlastimil Babka
@ 2025-03-17 14:33 ` Vlastimil Babka
2025-03-17 14:33 ` [PATCH RFC v3 8/8] maple_tree: use percpu sheaves for maple_node_cache Vlastimil Babka
7 siblings, 0 replies; 20+ messages in thread
From: Vlastimil Babka @ 2025-03-17 14:33 UTC (permalink / raw)
To: Suren Baghdasaryan, Liam R. Howlett, Christoph Lameter, David Rientjes
Cc: Roman Gushchin, Harry Yoo, Uladzislau Rezki, linux-mm,
linux-kernel, rcu, maple-tree, vbabka, Liam R. Howlett
From: "Liam R. Howlett" <Liam.Howlett@Oracle.com>
Allocate a sheaf and fill it to the count amount. Does not fill to the
sheaf limit to detect incorrect allocation requests.
Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>
---
tools/include/linux/slab.h | 24 +++++++++++++
tools/testing/shared/linux.c | 84 ++++++++++++++++++++++++++++++++++++++++++++
2 files changed, 108 insertions(+)
diff --git a/tools/include/linux/slab.h b/tools/include/linux/slab.h
index a475364cfd9fcdb10db252aab18ea3a620326b6b..0b6b42c9921fc402b4f3d4f681a95c9067d128db 100644
--- a/tools/include/linux/slab.h
+++ b/tools/include/linux/slab.h
@@ -22,6 +22,13 @@ enum slab_state {
FULL
};
+struct slab_sheaf {
+ struct kmem_cache *cache;
+ unsigned int size;
+ unsigned int capacity;
+ void *objects[];
+};
+
struct kmem_cache_args {
unsigned int align;
unsigned int sheaf_capacity;
@@ -79,4 +86,21 @@ void kmem_cache_free_bulk(struct kmem_cache *cachep, size_t size, void **list);
int kmem_cache_alloc_bulk(struct kmem_cache *cachep, gfp_t gfp, size_t size,
void **list);
+struct slab_sheaf *
+kmem_cache_prefill_sheaf(struct kmem_cache *s, gfp_t gfp, unsigned int size);
+
+void *
+kmem_cache_alloc_from_sheaf(struct kmem_cache *s, gfp_t gfp,
+ struct slab_sheaf *sheaf);
+
+void kmem_cache_return_sheaf(struct kmem_cache *s, gfp_t gfp,
+ struct slab_sheaf *sheaf);
+int kmem_cache_refill_sheaf(struct kmem_cache *s, gfp_t gfp,
+ struct slab_sheaf **sheafp, unsigned int size);
+
+static inline unsigned int kmem_cache_sheaf_size(struct slab_sheaf *sheaf)
+{
+ return sheaf->size;
+}
+
#endif /* _TOOLS_SLAB_H */
diff --git a/tools/testing/shared/linux.c b/tools/testing/shared/linux.c
index 9f5fd722f27f1d3877be8927be30409cd74ab3c3..a61c755c3c87e80036a5173115e955bfe7d5a80c 100644
--- a/tools/testing/shared/linux.c
+++ b/tools/testing/shared/linux.c
@@ -181,6 +181,12 @@ int kmem_cache_alloc_bulk(struct kmem_cache *cachep, gfp_t gfp, size_t size,
if (kmalloc_verbose)
pr_debug("Bulk alloc %lu\n", size);
+ if (cachep->exec_callback) {
+ if (cachep->callback)
+ cachep->callback(cachep->private);
+ cachep->exec_callback = false;
+ }
+
pthread_mutex_lock(&cachep->lock);
if (cachep->nr_objs >= size) {
struct radix_tree_node *node;
@@ -270,6 +276,84 @@ __kmem_cache_create_args(const char *name, unsigned int size,
return ret;
}
+struct slab_sheaf *
+kmem_cache_prefill_sheaf(struct kmem_cache *s, gfp_t gfp, unsigned int size)
+{
+ struct slab_sheaf *sheaf;
+ unsigned int capacity;
+
+ if (size > s->sheaf_capacity)
+ capacity = size;
+ else
+ capacity = s->sheaf_capacity;
+
+ sheaf = malloc(sizeof(*sheaf) + sizeof(void *) * s->sheaf_capacity * capacity);
+ if (!sheaf) {
+ return NULL;
+ }
+
+ memset(sheaf, 0, size);
+ sheaf->cache = s;
+ sheaf->capacity = capacity;
+ sheaf->size = kmem_cache_alloc_bulk(s, gfp, size, sheaf->objects);
+ if (!sheaf->size) {
+ free(sheaf);
+ return NULL;
+ }
+
+ return sheaf;
+}
+
+int kmem_cache_refill_sheaf(struct kmem_cache *s, gfp_t gfp,
+ struct slab_sheaf **sheafp, unsigned int size)
+{
+ struct slab_sheaf *sheaf = *sheafp;
+ int refill;
+
+ if (sheaf->size >= size)
+ return 0;
+
+ if (size > sheaf->capacity) {
+ sheaf = kmem_cache_prefill_sheaf(s, gfp, size);
+ if (!sheaf)
+ return -ENOMEM;
+
+ kmem_cache_return_sheaf(s, gfp, *sheafp);
+ *sheafp = sheaf;
+ return 0;
+ }
+
+ refill = kmem_cache_alloc_bulk(s, gfp, size - sheaf->size,
+ &sheaf->objects[sheaf->size]);
+ if (!refill)
+ return -ENOMEM;
+
+ sheaf->size += refill;
+ return 0;
+}
+
+void kmem_cache_return_sheaf(struct kmem_cache *s, gfp_t gfp,
+ struct slab_sheaf *sheaf)
+{
+ if (sheaf->size) {
+ //s->non_kernel += sheaf->size;
+ kmem_cache_free_bulk(s, sheaf->size, &sheaf->objects[0]);
+ }
+ free(sheaf);
+}
+
+void *
+kmem_cache_alloc_from_sheaf(struct kmem_cache *s, gfp_t gfp,
+ struct slab_sheaf *sheaf)
+{
+ if (sheaf->size == 0) {
+ printf("Nothing left in sheaf!\n");
+ return NULL;
+ }
+
+ return sheaf->objects[--sheaf->size];
+}
+
/*
* Test the test infrastructure for kem_cache_alloc/free and bulk counterparts.
*/
--
2.48.1
^ permalink raw reply [flat|nested] 20+ messages in thread
* [PATCH RFC v3 8/8] maple_tree: use percpu sheaves for maple_node_cache
2025-03-17 14:33 [PATCH RFC v3 0/8] SLUB percpu sheaves Vlastimil Babka
` (6 preceding siblings ...)
2025-03-17 14:33 ` [PATCH RFC v3 7/8] tools: Add sheafs support to testing infrastructure Vlastimil Babka
@ 2025-03-17 14:33 ` Vlastimil Babka
7 siblings, 0 replies; 20+ messages in thread
From: Vlastimil Babka @ 2025-03-17 14:33 UTC (permalink / raw)
To: Suren Baghdasaryan, Liam R. Howlett, Christoph Lameter, David Rientjes
Cc: Roman Gushchin, Harry Yoo, Uladzislau Rezki, linux-mm,
linux-kernel, rcu, maple-tree, vbabka
Setup the maple_node_cache with percpu sheaves of size 32 to hopefully
improve its performance. Change the single node rcu freeing in
ma_free_rcu() to use kfree_rcu() instead of the custom callback, which
allows the rcu_free sheaf batching to be used. Note there are other
users of mt_free_rcu() where larger parts of maple tree are submitted to
call_rcu() as a whole, and that cannot use the rcu_free sheaf, but it's
still possible for maple nodes freed this way to be reused via the barn,
even if only some cpus are allowed to process rcu callbacks.
Signed-off-by: Vlastimil Babka <vbabka@suse.cz>
Reviewed-by: Suren Baghdasaryan <surenb@google.com>
---
lib/maple_tree.c | 11 ++++++++---
1 file changed, 8 insertions(+), 3 deletions(-)
diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index f7153ade1be5f16423f0ca073846a7f3dfa60523..56e7a00f6f0941bff163091c999a873e4273f071 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -208,7 +208,7 @@ static void mt_free_rcu(struct rcu_head *head)
static void ma_free_rcu(struct maple_node *node)
{
WARN_ON(node->parent != ma_parent_ptr(node));
- call_rcu(&node->rcu, mt_free_rcu);
+ kfree_rcu(node, rcu);
}
static void mas_set_height(struct ma_state *mas)
@@ -6258,9 +6258,14 @@ bool mas_nomem(struct ma_state *mas, gfp_t gfp)
void __init maple_tree_init(void)
{
+ struct kmem_cache_args args = {
+ .align = sizeof(struct maple_node),
+ .sheaf_capacity = 32,
+ };
+
maple_node_cache = kmem_cache_create("maple_node",
- sizeof(struct maple_node), sizeof(struct maple_node),
- SLAB_PANIC, NULL);
+ sizeof(struct maple_node), &args,
+ SLAB_PANIC);
}
/**
--
2.48.1
^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: [PATCH RFC v3 2/8] slab: add opt-in caching layer of percpu sheaves
2025-03-17 14:33 ` [PATCH RFC v3 2/8] slab: add opt-in caching layer of percpu sheaves Vlastimil Babka
@ 2025-04-03 8:31 ` Harry Yoo
2025-04-03 14:11 ` Vlastimil Babka
2025-04-10 19:51 ` Suren Baghdasaryan
1 sibling, 1 reply; 20+ messages in thread
From: Harry Yoo @ 2025-04-03 8:31 UTC (permalink / raw)
To: Vlastimil Babka
Cc: Suren Baghdasaryan, Liam R. Howlett, Christoph Lameter,
David Rientjes, Roman Gushchin, Uladzislau Rezki, linux-mm,
linux-kernel, rcu, maple-tree
On Mon, Mar 17, 2025 at 03:33:03PM +0100, Vlastimil Babka wrote:
> Specifying a non-zero value for a new struct kmem_cache_args field
> sheaf_capacity will setup a caching layer of percpu arrays called
> sheaves of given capacity for the created cache.
>
> Allocations from the cache will allocate via the percpu sheaves (main or
> spare) as long as they have no NUMA node preference. Frees will also
> refill one of the sheaves.
>
> When both percpu sheaves are found empty during an allocation, an empty
> sheaf may be replaced with a full one from the per-node barn. If none
> are available and the allocation is allowed to block, an empty sheaf is
> refilled from slab(s) by an internal bulk alloc operation. When both
> percpu sheaves are full during freeing, the barn can replace a full one
> with an empty one, unless over a full sheaves limit. In that case a
> sheaf is flushed to slab(s) by an internal bulk free operation. Flushing
> sheaves and barns is also wired to the existing cpu flushing and cache
> shrinking operations.
>
> The sheaves do not distinguish NUMA locality of the cached objects. If
> an allocation is requested with kmem_cache_alloc_node() with a specific
> node (not NUMA_NO_NODE), sheaves are bypassed.
>
> The bulk operations exposed to slab users also try to utilize the
> sheaves as long as the necessary (full or empty) sheaves are available
> on the cpu or in the barn. Once depleted, they will fallback to bulk
> alloc/free to slabs directly to avoid double copying.
>
> Sysfs stat counters alloc_cpu_sheaf and free_cpu_sheaf count objects
> allocated or freed using the sheaves. Counters sheaf_refill,
> sheaf_flush_main and sheaf_flush_other count objects filled or flushed
> from or to slab pages, and can be used to assess how effective the
> caching is. The refill and flush operations will also count towards the
> usual alloc_fastpath/slowpath, free_fastpath/slowpath and other
> counters.
>
> Access to the percpu sheaves is protected by localtry_trylock() when
> potential callers include irq context, and localtry_lock() otherwise
> (such as when we already know the gfp flags allow blocking). The trylock
> failures should be rare and we can easily fallback. Each per-NUMA-node
> barn has a spin_lock.
>
> A current limitation is that when slub_debug is enabled for a cache with
> percpu sheaves, the objects in the array are considered as allocated from
> the slub_debug perspective, and the alloc/free debugging hooks occur
> when moving the objects between the array and slab pages. This means
> that e.g. an use-after-free that occurs for an object cached in the
> array is undetected. Collected alloc/free stacktraces might also be less
> useful. This limitation could be changed in the future.
>
> On the other hand, KASAN, kmemcg and other hooks are executed on actual
> allocations and frees by kmem_cache users even if those use the array,
> so their debugging or accounting accuracy should be unaffected.
>
> Signed-off-by: Vlastimil Babka <vbabka@suse.cz>
> ---
> include/linux/slab.h | 34 ++
> mm/slab.h | 2 +
> mm/slab_common.c | 5 +-
> mm/slub.c | 1029 +++++++++++++++++++++++++++++++++++++++++++++++---
> 4 files changed, 1020 insertions(+), 50 deletions(-)
>
> diff --git a/include/linux/slab.h b/include/linux/slab.h
> index 7686054dd494cc65def7f58748718e03eb78e481..0e1b25228c77140d05b5b4433c9d7923de36ec05 100644
> --- a/include/linux/slab.h
> +++ b/include/linux/slab.h
> @@ -453,12 +489,19 @@ static inline struct kmem_cache_node *get_node(struct kmem_cache *s, int node)
> */
> static nodemask_t slab_nodes;
>
> -#ifndef CONFIG_SLUB_TINY
> /*
> * Workqueue used for flush_cpu_slab().
> */
> static struct workqueue_struct *flushwq;
> -#endif
> +
> +struct slub_flush_work {
> + struct work_struct work;
> + struct kmem_cache *s;
> + bool skip;
> +};
> +
> +static DEFINE_MUTEX(flush_lock);
> +static DEFINE_PER_CPU(struct slub_flush_work, slub_flush);
>
> /********************************************************************
> * Core slab cache functions
> @@ -2410,6 +2453,358 @@ static void *setup_object(struct kmem_cache *s, void *object)
> return object;
> }
> +/*
> + * Bulk free objects to the percpu sheaves.
> + * Unlike free_to_pcs() this includes the calls to all necessary hooks
> + * and the fallback to freeing to slab pages.
> + */
> +static void free_to_pcs_bulk(struct kmem_cache *s, size_t size, void **p)
> +{
[...snip...]
> +next_batch:
> + if (!localtry_trylock(&s->cpu_sheaves->lock))
> + goto fallback;
> +
> + pcs = this_cpu_ptr(s->cpu_sheaves);
> +
> + if (unlikely(pcs->main->size == s->sheaf_capacity)) {
> +
> + struct slab_sheaf *empty;
> +
> + if (!pcs->spare) {
> + empty = barn_get_empty_sheaf(pcs->barn);
> + if (empty) {
> + pcs->spare = pcs->main;
> + pcs->main = empty;
> + goto do_free;
> + }
> + goto no_empty;
Maybe a silly question, but if neither of alloc_from_pcs_bulk() or
free_to_pcs_bulk() allocates empty sheaves (and sometimes put empty or full
sheaves in the barn), you should expect usually sheaves not to be in the barn
when using bulk interfces?
> + }
> +
> + if (pcs->spare->size < s->sheaf_capacity) {
> + stat(s, SHEAF_SWAP);
> + swap(pcs->main, pcs->spare);
> + goto do_free;
> + }
> +
> + empty = barn_replace_full_sheaf(pcs->barn, pcs->main);
> +
> + if (!IS_ERR(empty)) {
> + pcs->main = empty;
> + goto do_free;
> + }
> +
> +no_empty:
> + localtry_unlock(&s->cpu_sheaves->lock);
> +
> + /*
> + * if we depleted all empty sheaves in the barn or there are too
> + * many full sheaves, free the rest to slab pages
> + */
> +fallback:
> + __kmem_cache_free_bulk(s, size, p);
> + return;
> + }
> +
> +do_free:
> + main = pcs->main;
> + batch = min(size, s->sheaf_capacity - main->size);
> +
> + memcpy(main->objects + main->size, p, batch * sizeof(void *));
> + main->size += batch;
> +
> + localtry_unlock(&s->cpu_sheaves->lock);
> +
> + stat_add(s, FREE_PCS, batch);
> +
> + if (batch < size) {
> + p += batch;
> + size -= batch;
> + goto next_batch;
> + }
> +}
> +
> #ifndef CONFIG_SLUB_TINY
> /*
> * Fastpath with forced inlining to produce a kfree and kmem_cache_free that
> @@ -5309,8 +6145,8 @@ static inline int calculate_order(unsigned int size)
> return -ENOSYS;
> }
>
> -static void
> -init_kmem_cache_node(struct kmem_cache_node *n)
> +static bool
> +init_kmem_cache_node(struct kmem_cache_node *n, struct node_barn *barn)
> {
Why is the return type bool, when it always succeeds?
> n->nr_partial = 0;
> spin_lock_init(&n->list_lock);
> @@ -5320,6 +6156,11 @@ init_kmem_cache_node(struct kmem_cache_node *n)
> atomic_long_set(&n->total_objects, 0);
> INIT_LIST_HEAD(&n->full);
> #endif
> + n->barn = barn;
> + if (barn)
> + barn_init(barn);
> +
> + return true;
> }
>
> #ifndef CONFIG_SLUB_TINY
> @@ -5385,7 +6250,7 @@ static void early_kmem_cache_node_alloc(int node)
> slab->freelist = get_freepointer(kmem_cache_node, n);
> slab->inuse = 1;
> kmem_cache_node->node[node] = n;
> - init_kmem_cache_node(n);
> + init_kmem_cache_node(n, NULL);
> inc_slabs_node(kmem_cache_node, node, slab->objects);
>
> /*
> @@ -5421,20 +6295,27 @@ static int init_kmem_cache_nodes(struct kmem_cache *s)
>
> for_each_node_mask(node, slab_nodes) {
> struct kmem_cache_node *n;
> + struct node_barn *barn = NULL;
>
> if (slab_state == DOWN) {
> early_kmem_cache_node_alloc(node);
> continue;
> }
> +
> + if (s->cpu_sheaves) {
> + barn = kmalloc_node(sizeof(*barn), GFP_KERNEL, node);
> +
> + if (!barn)
> + return 0;
> + }
> +
> n = kmem_cache_alloc_node(kmem_cache_node,
> GFP_KERNEL, node);
> -
> - if (!n) {
> - free_kmem_cache_nodes(s);
> + if (!n)
> return 0;
> - }
Looks like it's leaking the barn
if the allocation of kmem_cache_node fails?
> - init_kmem_cache_node(n);
> + init_kmem_cache_node(n, barn);
> +
> s->node[node] = n;
> }
> return 1;
> @@ -6005,12 +6891,24 @@ static int slab_mem_going_online_callback(void *arg)
> */
> mutex_lock(&slab_mutex);
> list_for_each_entry(s, &slab_caches, list) {
> + struct node_barn *barn = NULL;
> +
> /*
> * The structure may already exist if the node was previously
> * onlined and offlined.
> */
> if (get_node(s, nid))
> continue;
> +
> + if (s->cpu_sheaves) {
> + barn = kmalloc_node(sizeof(*barn), GFP_KERNEL, nid);
> +
> + if (!barn) {
> + ret = -ENOMEM;
> + goto out;
> + }
> + }
> +
Ditto.
Otherwise looks good to me :)
> /*
> * XXX: kmem_cache_alloc_node will fallback to other nodes
> * since memory is not yet available from the node that
> @@ -6021,7 +6919,9 @@ static int slab_mem_going_online_callback(void *arg)
> ret = -ENOMEM;
> goto out;
> }
> - init_kmem_cache_node(n);
> +
> + init_kmem_cache_node(n, barn);
> +
> s->node[nid] = n;
> }
> /*
--
Cheers,
Harry (formerly known as Hyeonggon)
^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: [PATCH RFC v3 2/8] slab: add opt-in caching layer of percpu sheaves
2025-04-03 8:31 ` Harry Yoo
@ 2025-04-03 14:11 ` Vlastimil Babka
0 siblings, 0 replies; 20+ messages in thread
From: Vlastimil Babka @ 2025-04-03 14:11 UTC (permalink / raw)
To: Harry Yoo
Cc: Suren Baghdasaryan, Liam R. Howlett, Christoph Lameter,
David Rientjes, Roman Gushchin, Uladzislau Rezki, linux-mm,
linux-kernel, rcu, maple-tree
On 4/3/25 10:31, Harry Yoo wrote:
>> +/*
>> + * Bulk free objects to the percpu sheaves.
>> + * Unlike free_to_pcs() this includes the calls to all necessary hooks
>> + * and the fallback to freeing to slab pages.
>> + */
>> +static void free_to_pcs_bulk(struct kmem_cache *s, size_t size, void **p)
>> +{
>
> [...snip...]
>
>> +next_batch:
>> + if (!localtry_trylock(&s->cpu_sheaves->lock))
>> + goto fallback;
>> +
>> + pcs = this_cpu_ptr(s->cpu_sheaves);
>> +
>> + if (unlikely(pcs->main->size == s->sheaf_capacity)) {
>> +
>> + struct slab_sheaf *empty;
>> +
>> + if (!pcs->spare) {
>> + empty = barn_get_empty_sheaf(pcs->barn);
>> + if (empty) {
>> + pcs->spare = pcs->main;
>> + pcs->main = empty;
>> + goto do_free;
>> + }
>> + goto no_empty;
>
> Maybe a silly question, but if neither of alloc_from_pcs_bulk() or
> free_to_pcs_bulk() allocates empty sheaves (and sometimes put empty or full
> sheaves in the barn), you should expect usually sheaves not to be in the barn
> when using bulk interfces?
Hm maybe, but with patch 5/8 it becomes cheap to check? And there might be
caches mixing both bulk and individual allocs?
But maybe I should at least add the free sheaf alloc with GFP_NOWAIT attempt
to bulk free? Can't recall if I missed it intentionally or forgot.
>> -static void
>> -init_kmem_cache_node(struct kmem_cache_node *n)
>> +static bool
>> +init_kmem_cache_node(struct kmem_cache_node *n, struct node_barn *barn)
>> {
>
> Why is the return type bool, when it always succeeds?
I guess leftover from earlier versions. Will fix.
>> @@ -5421,20 +6295,27 @@ static int init_kmem_cache_nodes(struct kmem_cache *s)
>>
>> for_each_node_mask(node, slab_nodes) {
>> struct kmem_cache_node *n;
>> + struct node_barn *barn = NULL;
>>
>> if (slab_state == DOWN) {
>> early_kmem_cache_node_alloc(node);
>> continue;
>> }
>> +
>> + if (s->cpu_sheaves) {
>> + barn = kmalloc_node(sizeof(*barn), GFP_KERNEL, node);
>> +
>> + if (!barn)
>> + return 0;
>> + }
>> +
>> n = kmem_cache_alloc_node(kmem_cache_node,
>> GFP_KERNEL, node);
>> -
>> - if (!n) {
>> - free_kmem_cache_nodes(s);
>> + if (!n)
>> return 0;
>> - }
>
> Looks like it's leaking the barn
> if the allocation of kmem_cache_node fails?
Oops right, will add kfree(barn) before return 0;
>
>> - init_kmem_cache_node(n);
>> + init_kmem_cache_node(n, barn);
>> +
>> s->node[node] = n;
>> }
>> return 1;
>> @@ -6005,12 +6891,24 @@ static int slab_mem_going_online_callback(void *arg)
>> */
>> mutex_lock(&slab_mutex);
>> list_for_each_entry(s, &slab_caches, list) {
>> + struct node_barn *barn = NULL;
>> +
>> /*
>> * The structure may already exist if the node was previously
>> * onlined and offlined.
>> */
>> if (get_node(s, nid))
>> continue;
>> +
>> + if (s->cpu_sheaves) {
>> + barn = kmalloc_node(sizeof(*barn), GFP_KERNEL, nid);
>> +
>> + if (!barn) {
>> + ret = -ENOMEM;
>> + goto out;
>> + }
>> + }
>> +
>
> Ditto.
>
> Otherwise looks good to me :)
Thanks a lot!
^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: [PATCH RFC v3 3/8] slab: add sheaf support for batching kfree_rcu() operations
2025-03-17 14:33 ` [PATCH RFC v3 3/8] slab: add sheaf support for batching kfree_rcu() operations Vlastimil Babka
@ 2025-04-09 1:50 ` Harry Yoo
2025-04-09 15:09 ` Vlastimil Babka
2025-04-10 20:24 ` Suren Baghdasaryan
1 sibling, 1 reply; 20+ messages in thread
From: Harry Yoo @ 2025-04-09 1:50 UTC (permalink / raw)
To: Vlastimil Babka
Cc: Suren Baghdasaryan, Liam R. Howlett, Christoph Lameter,
David Rientjes, Roman Gushchin, Uladzislau Rezki, linux-mm,
linux-kernel, rcu, maple-tree
On Mon, Mar 17, 2025 at 03:33:04PM +0100, Vlastimil Babka wrote:
> Extend the sheaf infrastructure for more efficient kfree_rcu() handling.
> For caches with sheaves, on each cpu maintain a rcu_free sheaf in
> addition to main and spare sheaves.
>
> kfree_rcu() operations will try to put objects on this sheaf. Once full,
> the sheaf is detached and submitted to call_rcu() with a handler that
> will try to put it in the barn, or flush to slab pages using bulk free,
> when the barn is full. Then a new empty sheaf must be obtained to put
> more objects there.
>
> It's possible that no free sheaves are available to use for a new
> rcu_free sheaf, and the allocation in kfree_rcu() context can only use
> GFP_NOWAIT and thus may fail. In that case, fall back to the existing
> kfree_rcu() machinery.
>
> Expected advantages:
> - batching the kfree_rcu() operations, that could eventually replace the
> existing batching
> - sheaves can be reused for allocations via barn instead of being
> flushed to slabs, which is more efficient
> - this includes cases where only some cpus are allowed to process rcu
> callbacks (Android)
>
> Possible disadvantage:
> - objects might be waiting for more than their grace period (it is
> determined by the last object freed into the sheaf), increasing memory
> usage - but the existing batching does that too?
>
> Only implement this for CONFIG_KVFREE_RCU_BATCHED as the tiny
> implementation favors smaller memory footprint over performance.
>
> Signed-off-by: Vlastimil Babka <vbabka@suse.cz>
> Reviewed-by: Suren Baghdasaryan <surenb@google.com>
> ---
> mm/slab.h | 2 +
> mm/slab_common.c | 24 ++++++++
> mm/slub.c | 165 ++++++++++++++++++++++++++++++++++++++++++++++++++++++-
> 3 files changed, 189 insertions(+), 2 deletions(-)
>
> diff --git a/mm/slab.h b/mm/slab.h
> index 8daaec53b6ecfc44171191d421adb12e5cba2c58..94e9959e1aefa350d3d74e3f5309fde7a5cf2ec8 100644
> --- a/mm/slab.h
> +++ b/mm/slab.h
> @@ -459,6 +459,8 @@ static inline bool is_kmalloc_normal(struct kmem_cache *s)
> return !(s->flags & (SLAB_CACHE_DMA|SLAB_ACCOUNT|SLAB_RECLAIM_ACCOUNT));
> }
>
> +bool __kfree_rcu_sheaf(struct kmem_cache *s, void *obj);
> +
> /* Legal flag mask for kmem_cache_create(), for various configurations */
> #define SLAB_CORE_FLAGS (SLAB_HWCACHE_ALIGN | SLAB_CACHE_DMA | \
> SLAB_CACHE_DMA32 | SLAB_PANIC | \
> diff --git a/mm/slab_common.c b/mm/slab_common.c
> index ceeefb287899a82f30ad79b403556001c1860311..9496176770ed47491e01ed78e060a74771d5541e 100644
> --- a/mm/slab_common.c
> +++ b/mm/slab_common.c
> @@ -1957,6 +1978,9 @@ void kvfree_call_rcu(struct rcu_head *head, void *ptr)
> if (!head)
> might_sleep();
>
> + if (kfree_rcu_sheaf(ptr))
> + return;
> +
> // Queue the object but don't yet schedule the batch.
> if (debug_rcu_head_queue(ptr)) {
> // Probable double kfree_rcu(), just leak.
> diff --git a/mm/slub.c b/mm/slub.c
> index fa3a6329713a9f45b189f27d4b1b334b54589c38..83f4395267dccfbc144920baa7d0a85a27fbb1b4 100644
> --- a/mm/slub.c
> +++ b/mm/slub.c
> @@ -350,6 +350,8 @@ enum stat_item {
> ALLOC_FASTPATH, /* Allocation from cpu slab */
> ALLOC_SLOWPATH, /* Allocation by getting a new cpu slab */
> FREE_PCS, /* Free to percpu sheaf */
> + FREE_RCU_SHEAF, /* Free to rcu_free sheaf */
> + FREE_RCU_SHEAF_FAIL, /* Failed to free to a rcu_free sheaf */
> FREE_FASTPATH, /* Free to cpu slab */
> FREE_SLOWPATH, /* Freeing not to cpu slab */
> FREE_FROZEN, /* Freeing to frozen slab */
> @@ -442,6 +444,7 @@ struct slab_sheaf {
> struct rcu_head rcu_head;
> struct list_head barn_list;
> };
> + struct kmem_cache *cache;
> unsigned int size;
> void *objects[];
> };
> @@ -450,6 +453,7 @@ struct slub_percpu_sheaves {
> localtry_lock_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() */
> struct node_barn *barn;
> };
>
> @@ -2597,7 +2621,7 @@ static void sheaf_flush_unused(struct kmem_cache *s, struct slab_sheaf *sheaf)
> static void pcs_flush_all(struct kmem_cache *s)
> {
> struct slub_percpu_sheaves *pcs;
> - struct slab_sheaf *spare;
> + struct slab_sheaf *spare, *rcu_free;
>
> localtry_lock(&s->cpu_sheaves->lock);
> pcs = this_cpu_ptr(s->cpu_sheaves);
> @@ -2605,6 +2629,9 @@ static void pcs_flush_all(struct kmem_cache *s)
> spare = pcs->spare;
> pcs->spare = NULL;
>
> + rcu_free = pcs->rcu_free;
> + pcs->rcu_free = NULL;
> +
> localtry_unlock(&s->cpu_sheaves->lock);
Hmm this hunk in v3 is fine, but on your slub-percpu-shaves-v4r0 branch
it's calling local_unlock() twice. Probably a rebase error?
Otherwise looks good to me.
When you address this, please feel free to add:
Reviewed-by: Harry Yoo <harry.yoo@oracle.com>
Thanks!
--
Cheers,
Harry / Hyeonggon
^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: [PATCH RFC v3 3/8] slab: add sheaf support for batching kfree_rcu() operations
2025-04-09 1:50 ` Harry Yoo
@ 2025-04-09 15:09 ` Vlastimil Babka
0 siblings, 0 replies; 20+ messages in thread
From: Vlastimil Babka @ 2025-04-09 15:09 UTC (permalink / raw)
To: Harry Yoo
Cc: Suren Baghdasaryan, Liam R. Howlett, Christoph Lameter,
David Rientjes, Roman Gushchin, Uladzislau Rezki, linux-mm,
linux-kernel, rcu, maple-tree
On 4/9/25 3:50 AM, Harry Yoo wrote:
> On Mon, Mar 17, 2025 at 03:33:04PM +0100, Vlastimil Babka wrote:
>
> Hmm this hunk in v3 is fine, but on your slub-percpu-shaves-v4r0 branch
> it's calling local_unlock() twice. Probably a rebase error?
Yeah, thanks a lot for catching that! I've just pushed
https://git.kernel.org/pub/scm/linux/kernel/git/vbabka/linux.git/log/?h=slub-percpu-sheaves-v4r1
with this fixed, and fixups for 2/8 to the points you made, plus a
proper strict_numa handling in 2/8, and an extra patch for better NUMA
locality
> Otherwise looks good to me.
>
> When you address this, please feel free to add:
>
> Reviewed-by: Harry Yoo <harry.yoo@oracle.com>
>
> Thanks!
>
^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: [PATCH RFC v3 2/8] slab: add opt-in caching layer of percpu sheaves
2025-03-17 14:33 ` [PATCH RFC v3 2/8] slab: add opt-in caching layer of percpu sheaves Vlastimil Babka
2025-04-03 8:31 ` Harry Yoo
@ 2025-04-10 19:51 ` Suren Baghdasaryan
2025-04-22 15:02 ` Vlastimil Babka
1 sibling, 1 reply; 20+ messages in thread
From: Suren Baghdasaryan @ 2025-04-10 19:51 UTC (permalink / raw)
To: Vlastimil Babka
Cc: Liam R. Howlett, Christoph Lameter, David Rientjes,
Roman Gushchin, Harry Yoo, Uladzislau Rezki, linux-mm,
linux-kernel, rcu, maple-tree
On Mon, Mar 17, 2025 at 7:33 AM Vlastimil Babka <vbabka@suse.cz> wrote:
>
> Specifying a non-zero value for a new struct kmem_cache_args field
> sheaf_capacity will setup a caching layer of percpu arrays called
> sheaves of given capacity for the created cache.
>
> Allocations from the cache will allocate via the percpu sheaves (main or
> spare) as long as they have no NUMA node preference. Frees will also
> refill one of the sheaves.
>
> When both percpu sheaves are found empty during an allocation, an empty
> sheaf may be replaced with a full one from the per-node barn. If none
> are available and the allocation is allowed to block, an empty sheaf is
> refilled from slab(s) by an internal bulk alloc operation. When both
> percpu sheaves are full during freeing, the barn can replace a full one
> with an empty one, unless over a full sheaves limit. In that case a
> sheaf is flushed to slab(s) by an internal bulk free operation. Flushing
> sheaves and barns is also wired to the existing cpu flushing and cache
> shrinking operations.
>
> The sheaves do not distinguish NUMA locality of the cached objects. If
> an allocation is requested with kmem_cache_alloc_node() with a specific
> node (not NUMA_NO_NODE), sheaves are bypassed.
>
> The bulk operations exposed to slab users also try to utilize the
> sheaves as long as the necessary (full or empty) sheaves are available
> on the cpu or in the barn. Once depleted, they will fallback to bulk
> alloc/free to slabs directly to avoid double copying.
>
> Sysfs stat counters alloc_cpu_sheaf and free_cpu_sheaf count objects
> allocated or freed using the sheaves. Counters sheaf_refill,
> sheaf_flush_main and sheaf_flush_other count objects filled or flushed
> from or to slab pages, and can be used to assess how effective the
> caching is. The refill and flush operations will also count towards the
> usual alloc_fastpath/slowpath, free_fastpath/slowpath and other
> counters.
>
> Access to the percpu sheaves is protected by localtry_trylock() when
> potential callers include irq context, and localtry_lock() otherwise
> (such as when we already know the gfp flags allow blocking). The trylock
> failures should be rare and we can easily fallback. Each per-NUMA-node
> barn has a spin_lock.
>
> A current limitation is that when slub_debug is enabled for a cache with
> percpu sheaves, the objects in the array are considered as allocated from
> the slub_debug perspective, and the alloc/free debugging hooks occur
> when moving the objects between the array and slab pages. This means
> that e.g. an use-after-free that occurs for an object cached in the
> array is undetected. Collected alloc/free stacktraces might also be less
> useful. This limitation could be changed in the future.
>
> On the other hand, KASAN, kmemcg and other hooks are executed on actual
> allocations and frees by kmem_cache users even if those use the array,
> so their debugging or accounting accuracy should be unaffected.
>
> Signed-off-by: Vlastimil Babka <vbabka@suse.cz>
> ---
> include/linux/slab.h | 34 ++
> mm/slab.h | 2 +
> mm/slab_common.c | 5 +-
> mm/slub.c | 1029 +++++++++++++++++++++++++++++++++++++++++++++++---
> 4 files changed, 1020 insertions(+), 50 deletions(-)
>
> diff --git a/include/linux/slab.h b/include/linux/slab.h
> index 7686054dd494cc65def7f58748718e03eb78e481..0e1b25228c77140d05b5b4433c9d7923de36ec05 100644
> --- a/include/linux/slab.h
> +++ b/include/linux/slab.h
> @@ -332,6 +332,40 @@ struct kmem_cache_args {
> * %NULL means no constructor.
> */
> void (*ctor)(void *);
> + /**
> + * @sheaf_capacity: Enable sheaves of given capacity for the cache.
> + *
> + * With a non-zero value, allocations from the cache go through caching
> + * arrays called sheaves. Each cpu has a main sheaf that's always
> + * present, and a spare sheaf thay may be not present. When both become
> + * empty, there's an attempt to replace an empty sheaf with a full sheaf
> + * from the per-node barn.
> + *
> + * When no full sheaf is available, and gfp flags allow blocking, a
> + * sheaf is allocated and filled from slab(s) using bulk allocation.
> + * Otherwise the allocation falls back to the normal operation
> + * allocating a single object from a slab.
> + *
> + * Analogically when freeing and both percpu sheaves are full, the barn
> + * may replace it with an empty sheaf, unless it's over capacity. In
> + * that case a sheaf is bulk freed to slab pages.
> + *
> + * The sheaves does not distinguish NUMA placement of objects, so
> + * allocations via kmem_cache_alloc_node() with a node specified other
> + * than NUMA_NO_NODE will bypass them.
> + *
> + * Bulk allocation and free operations also try to use the cpu sheaves
> + * and barn, but fallback to using slab pages directly.
> + *
> + * Limitations: when slub_debug is enabled for the cache, all relevant
> + * actions (i.e. poisoning, obtaining stacktraces) and checks happen
> + * when objects move between sheaves and slab pages, which may result in
> + * e.g. not detecting a use-after-free while the object is in the array
> + * cache, and the stacktraces may be less useful.
> + *
> + * %0 means no sheaves will be created
> + */
> + unsigned int sheaf_capacity;
> };
>
> struct kmem_cache *__kmem_cache_create_args(const char *name,
> diff --git a/mm/slab.h b/mm/slab.h
> index 2f01c7317988ce036f0b22807403226a59f0f708..8daaec53b6ecfc44171191d421adb12e5cba2c58 100644
> --- a/mm/slab.h
> +++ b/mm/slab.h
> @@ -259,6 +259,7 @@ struct kmem_cache {
> #ifndef CONFIG_SLUB_TINY
> struct kmem_cache_cpu __percpu *cpu_slab;
> #endif
> + struct slub_percpu_sheaves __percpu *cpu_sheaves;
> /* Used for retrieving partial slabs, etc. */
> slab_flags_t flags;
> unsigned long min_partial;
> @@ -272,6 +273,7 @@ struct kmem_cache {
> /* Number of per cpu partial slabs to keep around */
> unsigned int cpu_partial_slabs;
> #endif
> + unsigned int sheaf_capacity;
> struct kmem_cache_order_objects oo;
>
> /* Allocation and freeing of slabs */
> diff --git a/mm/slab_common.c b/mm/slab_common.c
> index 46d0a4cd33b5982fd79c307d572f231fdea9514a..ceeefb287899a82f30ad79b403556001c1860311 100644
> --- a/mm/slab_common.c
> +++ b/mm/slab_common.c
> @@ -163,6 +163,9 @@ int slab_unmergeable(struct kmem_cache *s)
> return 1;
> #endif
>
> + if (s->cpu_sheaves)
> + return 1;
> +
> /*
> * We may have set a slab to be unmergeable during bootstrap.
> */
> @@ -328,7 +331,7 @@ struct kmem_cache *__kmem_cache_create_args(const char *name,
> object_size - args->usersize < args->useroffset))
> args->usersize = args->useroffset = 0;
>
> - if (!args->usersize)
> + if (!args->usersize && !args->sheaf_capacity)
> s = __kmem_cache_alias(name, object_size, args->align, flags,
> args->ctor);
> if (s)
> diff --git a/mm/slub.c b/mm/slub.c
> index e8273f28656936c05d015c53923f8fe69cd161b2..fa3a6329713a9f45b189f27d4b1b334b54589c38 100644
> --- a/mm/slub.c
> +++ b/mm/slub.c
> @@ -346,8 +346,10 @@ static inline void debugfs_slab_add(struct kmem_cache *s) { }
> #endif
>
> enum stat_item {
> + ALLOC_PCS, /* Allocation from percpu sheaf */
> ALLOC_FASTPATH, /* Allocation from cpu slab */
> ALLOC_SLOWPATH, /* Allocation by getting a new cpu slab */
> + FREE_PCS, /* Free to percpu sheaf */
> FREE_FASTPATH, /* Free to cpu slab */
> FREE_SLOWPATH, /* Freeing not to cpu slab */
> FREE_FROZEN, /* Freeing to frozen slab */
> @@ -372,6 +374,12 @@ enum stat_item {
> CPU_PARTIAL_FREE, /* Refill cpu partial on free */
> CPU_PARTIAL_NODE, /* Refill cpu partial from node partial */
> CPU_PARTIAL_DRAIN, /* Drain cpu partial to node partial */
> + SHEAF_FLUSH_MAIN, /* Objects flushed from main percpu sheaf */
> + SHEAF_FLUSH_OTHER, /* Objects flushed from other sheaves */
> + SHEAF_REFILL, /* Objects refilled to a sheaf */
> + SHEAF_SWAP, /* Swapping main and spare sheaf */
> + SHEAF_ALLOC, /* Allocation of an empty sheaf */
> + SHEAF_FREE, /* Freeing of an empty sheaf */
> NR_SLUB_STAT_ITEMS
> };
>
> @@ -418,6 +426,33 @@ void stat_add(const struct kmem_cache *s, enum stat_item si, int v)
> #endif
> }
>
> +#define MAX_FULL_SHEAVES 10
> +#define MAX_EMPTY_SHEAVES 10
> +
> +struct node_barn {
> + spinlock_t lock;
> + struct list_head sheaves_full;
> + struct list_head sheaves_empty;
> + unsigned int nr_full;
> + unsigned int nr_empty;
> +};
> +
> +struct slab_sheaf {
> + union {
> + struct rcu_head rcu_head;
> + struct list_head barn_list;
> + };
> + unsigned int size;
> + void *objects[];
> +};
> +
> +struct slub_percpu_sheaves {
> + localtry_lock_t lock;
> + struct slab_sheaf *main; /* never NULL when unlocked */
> + struct slab_sheaf *spare; /* empty or full, may be NULL */
> + struct node_barn *barn;
> +};
> +
> /*
> * The slab lists for all objects.
> */
> @@ -430,6 +465,7 @@ struct kmem_cache_node {
> atomic_long_t total_objects;
> struct list_head full;
> #endif
> + struct node_barn *barn;
> };
>
> static inline struct kmem_cache_node *get_node(struct kmem_cache *s, int node)
> @@ -453,12 +489,19 @@ static inline struct kmem_cache_node *get_node(struct kmem_cache *s, int node)
> */
> static nodemask_t slab_nodes;
>
> -#ifndef CONFIG_SLUB_TINY
> /*
> * Workqueue used for flush_cpu_slab().
> */
> static struct workqueue_struct *flushwq;
> -#endif
> +
> +struct slub_flush_work {
> + struct work_struct work;
> + struct kmem_cache *s;
> + bool skip;
> +};
> +
> +static DEFINE_MUTEX(flush_lock);
> +static DEFINE_PER_CPU(struct slub_flush_work, slub_flush);
>
> /********************************************************************
> * Core slab cache functions
> @@ -2410,6 +2453,358 @@ static void *setup_object(struct kmem_cache *s, void *object)
> return object;
> }
>
> +static struct slab_sheaf *alloc_empty_sheaf(struct kmem_cache *s, gfp_t gfp)
> +{
> + struct slab_sheaf *sheaf = kzalloc(struct_size(sheaf, objects,
> + s->sheaf_capacity), gfp);
> +
> + if (unlikely(!sheaf))
> + return NULL;
> +
> + stat(s, SHEAF_ALLOC);
> +
> + return sheaf;
> +}
> +
> +static void free_empty_sheaf(struct kmem_cache *s, struct slab_sheaf *sheaf)
> +{
> + kfree(sheaf);
> +
> + stat(s, SHEAF_FREE);
> +}
> +
> +static int __kmem_cache_alloc_bulk(struct kmem_cache *s, gfp_t flags,
> + size_t size, void **p);
> +
> +
> +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 = __kmem_cache_alloc_bulk(s, gfp, to_fill,
> + &sheaf->objects[sheaf->size]);
> +
> + sheaf->size += filled;
> +
> + stat_add(s, SHEAF_REFILL, filled);
> +
> + if (filled < to_fill)
> + return -ENOMEM;
> +
> + return 0;
> +}
> +
> +
> +static struct slab_sheaf *alloc_full_sheaf(struct kmem_cache *s, gfp_t gfp)
> +{
> + struct slab_sheaf *sheaf = alloc_empty_sheaf(s, gfp);
> +
> + if (!sheaf)
> + return NULL;
> +
> + if (refill_sheaf(s, sheaf, gfp)) {
> + free_empty_sheaf(s, sheaf);
> + return NULL;
> + }
> +
> + return sheaf;
> +}
> +
> +/*
> + * Maximum number of objects freed during a single flush of main pcs sheaf.
> + * Translates directly to an on-stack array size.
> + */
> +#define PCS_BATCH_MAX 32U
> +
> +static void __kmem_cache_free_bulk(struct kmem_cache *s, size_t size, void **p);
> +
> +/*
> + * Free all objects from the main sheaf. In order to perform
> + * __kmem_cache_free_bulk() outside of cpu_sheaves->lock, work in batches where
> + * object pointers are moved to a on-stack array under the lock. To bound the
> + * stack usage, limit each batch to PCS_BATCH_MAX.
> + *
> + * returns true if at least partially flushed
> + */
> +static bool sheaf_flush_main(struct kmem_cache *s)
> +{
> + struct slub_percpu_sheaves *pcs;
> + unsigned int batch, remaining;
> + void *objects[PCS_BATCH_MAX];
> + struct slab_sheaf *sheaf;
> + bool ret = false;
> +
> +next_batch:
> + if (!localtry_trylock(&s->cpu_sheaves->lock))
> + return ret;
> +
> + pcs = this_cpu_ptr(s->cpu_sheaves);
> + sheaf = pcs->main;
> +
> + batch = min(PCS_BATCH_MAX, sheaf->size);
> +
> + sheaf->size -= batch;
> + memcpy(objects, sheaf->objects + sheaf->size, batch * sizeof(void *));
> +
> + remaining = sheaf->size;
> +
> + localtry_unlock(&s->cpu_sheaves->lock);
> +
> + __kmem_cache_free_bulk(s, batch, &objects[0]);
> +
> + stat_add(s, SHEAF_FLUSH_MAIN, batch);
> +
> + ret = true;
> +
> + if (remaining)
> + goto next_batch;
> +
> + return ret;
> +}
> +
> +/*
> + * Free all objects from a sheaf that's unused, i.e. not linked to any
> + * cpu_sheaves, so we need no locking and batching. The locking is also not
> + * necessary when flushing cpu's sheaves (both spare and main) during cpu
> + * hotremove as the cpu is not executing anymore.
> + */
> +static void sheaf_flush_unused(struct kmem_cache *s, struct slab_sheaf *sheaf)
> +{
> + if (!sheaf->size)
> + return;
> +
> + stat_add(s, SHEAF_FLUSH_OTHER, sheaf->size);
> +
> + __kmem_cache_free_bulk(s, sheaf->size, &sheaf->objects[0]);
> +
> + sheaf->size = 0;
> +}
> +
> +/*
> + * Caller needs to make sure migration is disabled in order to fully flush
> + * single cpu's sheaves
> + *
> + * must not be called from an irq
> + *
> + * flushing operations are rare so let's keep it simple and flush to slabs
> + * directly, skipping the barn
> + */
> +static void pcs_flush_all(struct kmem_cache *s)
> +{
> + struct slub_percpu_sheaves *pcs;
> + struct slab_sheaf *spare;
> +
> + localtry_lock(&s->cpu_sheaves->lock);
> + pcs = this_cpu_ptr(s->cpu_sheaves);
> +
> + spare = pcs->spare;
> + pcs->spare = NULL;
> +
> + localtry_unlock(&s->cpu_sheaves->lock);
> +
> + if (spare) {
> + sheaf_flush_unused(s, spare);
> + free_empty_sheaf(s, spare);
> + }
> +
> + sheaf_flush_main(s);
> +}
> +
> +static void __pcs_flush_all_cpu(struct kmem_cache *s, unsigned int cpu)
> +{
> + struct slub_percpu_sheaves *pcs;
> +
> + pcs = per_cpu_ptr(s->cpu_sheaves, cpu);
> +
> + /* The cpu is not executing anymore so we don't need pcs->lock */
> + sheaf_flush_unused(s, pcs->main);
You are flushing pcs->main but sheaf_flush_unused() will account that
in SHEAF_FLUSH_OTHER instead of SHEAF_FLUSH_MAIN. Perhaps
sheaf_flush_unused() needs a parameter to indicate which counter to be
incremented.
> + if (pcs->spare) {
> + sheaf_flush_unused(s, pcs->spare);
> + free_empty_sheaf(s, pcs->spare);
> + pcs->spare = NULL;
> + }
> +}
> +
> +static void pcs_destroy(struct kmem_cache *s)
> +{
> + int cpu;
> +
> + for_each_possible_cpu(cpu) {
> + struct slub_percpu_sheaves *pcs;
> +
> + pcs = per_cpu_ptr(s->cpu_sheaves, cpu);
> +
> + /* can happen when unwinding failed create */
> + if (!pcs->main)
> + continue;
> +
> + WARN_ON(pcs->spare);
> +
> + if (!WARN_ON(pcs->main->size)) {
If pcs->main->size > 0, shouldn't we flush pcs->main? I understand
it's not a normal situation but I think something like this would be
more correct:
if (WARN_ON(pcs->main->size))
sheaf_flush_unused(s, pcs->main);
free_empty_sheaf(s, pcs->main);
pcs->main = NULL;
> + free_empty_sheaf(s, pcs->main);
> + pcs->main = NULL;
> + }
> + }
> +
> + free_percpu(s->cpu_sheaves);
> + s->cpu_sheaves = NULL;
> +}
> +
> +static struct slab_sheaf *barn_get_empty_sheaf(struct node_barn *barn)
> +{
> + struct slab_sheaf *empty = NULL;
> + unsigned long flags;
> +
> + spin_lock_irqsave(&barn->lock, flags);
> +
> + if (barn->nr_empty) {
> + empty = list_first_entry(&barn->sheaves_empty,
> + struct slab_sheaf, barn_list);
> + list_del(&empty->barn_list);
> + barn->nr_empty--;
> + }
> +
> + spin_unlock_irqrestore(&barn->lock, flags);
> +
> + return empty;
> +}
> +
> +static int barn_put_empty_sheaf(struct node_barn *barn,
> + struct slab_sheaf *sheaf, bool ignore_limit)
This ignore_limit in barn_put_empty_sheaf()/barn_put_full_sheaf() is
sticking out and really used only inside rcu_free_sheaf() in the next
patch. Every time I saw the return value of these functions ignored I
had to remind myself that they pass ignore_limit=true, so the function
can't really fail. Maybe we could get rid of this flag and do trimming
of barn lists inside rcu_free_sheaf() separately in one go? IIUC
because we ignore the limits in all other places, at the time of
rcu_free_sheaf() we might end up with a barn having many more sheaves
than the limit allows for, so trimming in bulk might be even more
productive.
> +{
> + unsigned long flags;
> + int ret = 0;
> +
> + spin_lock_irqsave(&barn->lock, flags);
> +
> + if (!ignore_limit && barn->nr_empty >= MAX_EMPTY_SHEAVES) {
> + ret = -E2BIG;
> + } else {
> + list_add(&sheaf->barn_list, &barn->sheaves_empty);
> + barn->nr_empty++;
> + }
> +
> + spin_unlock_irqrestore(&barn->lock, flags);
> + return ret;
> +}
> +
> +static int barn_put_full_sheaf(struct node_barn *barn, struct slab_sheaf *sheaf,
> + bool ignore_limit)
Can this function be called for partially populated sheaves or only
full ones? I think rcu_free_sheaf() in the next patch might end up
calling it for a partially populated sheaf.
> +{
> + unsigned long flags;
> + int ret = 0;
> +
> + spin_lock_irqsave(&barn->lock, flags);
> +
> + if (!ignore_limit && barn->nr_full >= MAX_FULL_SHEAVES) {
> + ret = -E2BIG;
> + } else {
> + list_add(&sheaf->barn_list, &barn->sheaves_full);
> + barn->nr_full++;
> + }
> +
> + spin_unlock_irqrestore(&barn->lock, flags);
> + return ret;
> +}
> +
> +/*
> + * If a full sheaf is available, return it and put the supplied empty one to
> + * barn. We ignore the limit on empty sheaves as the number of sheaves doesn't
> + * change.
I'm unclear why we ignore the limit here but not in
barn_replace_full_sheaf(). Maybe because full sheaves consume more
memory? But then why do we mostly pass ignore_limit=true when invoking
barn_put_full_sheaf()? Explanation of this limit logic needs to be
clarified.
> + */
> +static struct slab_sheaf *
> +barn_replace_empty_sheaf(struct node_barn *barn, struct slab_sheaf *empty)
> +{
> + struct slab_sheaf *full = NULL;
> + unsigned long flags;
> +
> + spin_lock_irqsave(&barn->lock, flags);
> +
> + if (barn->nr_full) {
> + full = list_first_entry(&barn->sheaves_full, struct slab_sheaf,
> + barn_list);
> + list_del(&full->barn_list);
> + list_add(&empty->barn_list, &barn->sheaves_empty);
> + barn->nr_full--;
> + barn->nr_empty++;
> + }
> +
> + spin_unlock_irqrestore(&barn->lock, flags);
> +
> + return full;
> +}
> +/*
> + * If a empty sheaf is available, return it and put the supplied full one to
> + * barn. But if there are too many full sheaves, reject this with -E2BIG.
> + */
> +static struct slab_sheaf *
> +barn_replace_full_sheaf(struct node_barn *barn, struct slab_sheaf *full)
> +{
> + struct slab_sheaf *empty;
> + unsigned long flags;
> +
> + spin_lock_irqsave(&barn->lock, flags);
> +
> + if (barn->nr_full >= MAX_FULL_SHEAVES) {
> + empty = ERR_PTR(-E2BIG);
> + } else if (!barn->nr_empty) {
> + empty = ERR_PTR(-ENOMEM);
> + } else {
> + empty = list_first_entry(&barn->sheaves_empty, struct slab_sheaf,
> + barn_list);
> + list_del(&empty->barn_list);
> + list_add(&full->barn_list, &barn->sheaves_full);
> + barn->nr_empty--;
> + barn->nr_full++;
> + }
> +
> + spin_unlock_irqrestore(&barn->lock, flags);
> +
> + return empty;
> +}
> +
> +static void barn_init(struct node_barn *barn)
> +{
> + spin_lock_init(&barn->lock);
> + INIT_LIST_HEAD(&barn->sheaves_full);
> + INIT_LIST_HEAD(&barn->sheaves_empty);
> + barn->nr_full = 0;
> + barn->nr_empty = 0;
> +}
> +
> +static void barn_shrink(struct kmem_cache *s, struct node_barn *barn)
> +{
> + struct list_head empty_list;
> + struct list_head full_list;
> + struct slab_sheaf *sheaf, *sheaf2;
> + unsigned long flags;
> +
> + INIT_LIST_HEAD(&empty_list);
> + INIT_LIST_HEAD(&full_list);
> +
> + spin_lock_irqsave(&barn->lock, flags);
> +
> + list_splice_init(&barn->sheaves_full, &full_list);
> + barn->nr_full = 0;
> + list_splice_init(&barn->sheaves_empty, &empty_list);
> + barn->nr_empty = 0;
> +
> + spin_unlock_irqrestore(&barn->lock, flags);
> +
> + list_for_each_entry_safe(sheaf, sheaf2, &full_list, barn_list) {
> + sheaf_flush_unused(s, sheaf);
> + free_empty_sheaf(s, sheaf);
> + }
> +
> + list_for_each_entry_safe(sheaf, sheaf2, &empty_list, barn_list)
> + free_empty_sheaf(s, sheaf);
> +}
> +
> /*
> * Slab allocation and freeing
> */
> @@ -3280,11 +3675,42 @@ static inline void __flush_cpu_slab(struct kmem_cache *s, int cpu)
> put_partials_cpu(s, c);
> }
>
> -struct slub_flush_work {
> - struct work_struct work;
> - struct kmem_cache *s;
> - bool skip;
> -};
> +static inline void flush_this_cpu_slab(struct kmem_cache *s)
> +{
> + struct kmem_cache_cpu *c = this_cpu_ptr(s->cpu_slab);
> +
> + if (c->slab)
> + flush_slab(s, c);
> +
> + put_partials(s);
> +}
> +
> +static bool has_cpu_slab(int cpu, struct kmem_cache *s)
> +{
> + struct kmem_cache_cpu *c = per_cpu_ptr(s->cpu_slab, cpu);
> +
> + return c->slab || slub_percpu_partial(c);
> +}
> +
> +#else /* CONFIG_SLUB_TINY */
> +static inline void __flush_cpu_slab(struct kmem_cache *s, int cpu) { }
> +static inline bool has_cpu_slab(int cpu, struct kmem_cache *s) { return false; }
> +static inline void flush_this_cpu_slab(struct kmem_cache *s) { }
> +#endif /* CONFIG_SLUB_TINY */
> +
> +static bool has_pcs_used(int cpu, struct kmem_cache *s)
> +{
> + struct slub_percpu_sheaves *pcs;
> +
> + if (!s->cpu_sheaves)
> + return false;
> +
> + pcs = per_cpu_ptr(s->cpu_sheaves, cpu);
> +
> + return (pcs->spare || pcs->main->size);
> +}
> +
> +static void pcs_flush_all(struct kmem_cache *s);
>
> /*
> * Flush cpu slab.
> @@ -3294,30 +3720,18 @@ struct slub_flush_work {
> static void flush_cpu_slab(struct work_struct *w)
> {
> struct kmem_cache *s;
> - struct kmem_cache_cpu *c;
> struct slub_flush_work *sfw;
>
> sfw = container_of(w, struct slub_flush_work, work);
>
> s = sfw->s;
> - c = this_cpu_ptr(s->cpu_slab);
> -
> - if (c->slab)
> - flush_slab(s, c);
> -
> - put_partials(s);
> -}
>
> -static bool has_cpu_slab(int cpu, struct kmem_cache *s)
> -{
> - struct kmem_cache_cpu *c = per_cpu_ptr(s->cpu_slab, cpu);
> + if (s->cpu_sheaves)
> + pcs_flush_all(s);
>
> - return c->slab || slub_percpu_partial(c);
> + flush_this_cpu_slab(s);
> }
>
> -static DEFINE_MUTEX(flush_lock);
> -static DEFINE_PER_CPU(struct slub_flush_work, slub_flush);
> -
> static void flush_all_cpus_locked(struct kmem_cache *s)
> {
> struct slub_flush_work *sfw;
> @@ -3328,7 +3742,7 @@ static void flush_all_cpus_locked(struct kmem_cache *s)
>
> for_each_online_cpu(cpu) {
> sfw = &per_cpu(slub_flush, cpu);
> - if (!has_cpu_slab(cpu, s)) {
> + if (!has_cpu_slab(cpu, s) && !has_pcs_used(cpu, s)) {
> sfw->skip = true;
> continue;
> }
> @@ -3364,19 +3778,14 @@ static int slub_cpu_dead(unsigned int cpu)
> struct kmem_cache *s;
>
> mutex_lock(&slab_mutex);
> - list_for_each_entry(s, &slab_caches, list)
> + list_for_each_entry(s, &slab_caches, list) {
> __flush_cpu_slab(s, cpu);
> + __pcs_flush_all_cpu(s, cpu);
> + }
> mutex_unlock(&slab_mutex);
> return 0;
> }
>
> -#else /* CONFIG_SLUB_TINY */
> -static inline void flush_all_cpus_locked(struct kmem_cache *s) { }
> -static inline void flush_all(struct kmem_cache *s) { }
> -static inline void __flush_cpu_slab(struct kmem_cache *s, int cpu) { }
> -static inline int slub_cpu_dead(unsigned int cpu) { return 0; }
> -#endif /* CONFIG_SLUB_TINY */
> -
> /*
> * Check if the objects in a per cpu structure fit numa
> * locality expectations.
> @@ -4126,6 +4535,179 @@ bool slab_post_alloc_hook(struct kmem_cache *s, struct list_lru *lru,
> return memcg_slab_post_alloc_hook(s, lru, flags, size, p);
> }
>
> +static __fastpath_inline
> +void *alloc_from_pcs(struct kmem_cache *s, gfp_t gfp)
> +{
> + struct slub_percpu_sheaves *pcs;
> + void *object;
> +
> + if (!localtry_trylock(&s->cpu_sheaves->lock))
> + return NULL;
> +
> + pcs = this_cpu_ptr(s->cpu_sheaves);
> +
> + if (unlikely(pcs->main->size == 0)) {
> +
> + struct slab_sheaf *empty = NULL;
> + struct slab_sheaf *full;
> + bool can_alloc;
> +
> + if (pcs->spare && pcs->spare->size > 0) {
> + stat(s, SHEAF_SWAP);
> + swap(pcs->main, pcs->spare);
> + goto do_alloc;
> + }
> +
> + full = barn_replace_empty_sheaf(pcs->barn, pcs->main);
> +
> + if (full) {
> + pcs->main = full;
> + goto do_alloc;
> + }
> +
> + can_alloc = gfpflags_allow_blocking(gfp);
> +
> + if (can_alloc) {
> + if (pcs->spare) {
> + empty = pcs->spare;
> + pcs->spare = NULL;
> + } else {
> + empty = barn_get_empty_sheaf(pcs->barn);
> + }
> + }
> +
> + localtry_unlock(&s->cpu_sheaves->lock);
> +
> + if (!can_alloc)
> + return NULL;
> +
> + if (empty) {
> + if (!refill_sheaf(s, empty, gfp)) {
> + full = empty;
> + } else {
> + /*
> + * we must be very low on memory so don't bother
> + * with the barn
> + */
> + free_empty_sheaf(s, empty);
> + }
> + } else {
> + full = alloc_full_sheaf(s, gfp);
> + }
> +
> + if (!full)
> + return NULL;
> +
> + /*
> + * we can reach here only when gfpflags_allow_blocking
> + * so this must not be an irq
> + */
> + localtry_lock(&s->cpu_sheaves->lock);
> + 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) {
> + barn_put_empty_sheaf(pcs->barn, pcs->main, true);
> + pcs->main = full;
> + goto do_alloc;
> + }
> +
> + if (!pcs->spare) {
> + pcs->spare = full;
> + goto do_alloc;
> + }
> +
> + if (pcs->spare->size == 0) {
> + barn_put_empty_sheaf(pcs->barn, pcs->spare, true);
> + pcs->spare = full;
> + goto do_alloc;
> + }
> +
> + barn_put_full_sheaf(pcs->barn, full, true);
> + }
> +
> +do_alloc:
> + object = pcs->main->objects[--pcs->main->size];
> +
> + localtry_unlock(&s->cpu_sheaves->lock);
> +
> + stat(s, ALLOC_PCS);
> +
> + return object;
> +}
> +
> +static __fastpath_inline
> +unsigned int alloc_from_pcs_bulk(struct kmem_cache *s, size_t size, void **p)
> +{
> + struct slub_percpu_sheaves *pcs;
> + struct slab_sheaf *main;
> + unsigned int allocated = 0;
> + unsigned int batch;
> +
> +next_batch:
> + if (!localtry_trylock(&s->cpu_sheaves->lock))
> + return allocated;
> +
> + pcs = this_cpu_ptr(s->cpu_sheaves);
> +
> + if (unlikely(pcs->main->size == 0)) {
The above condition is unlikely only for the first batch. I think it's
actually guaranteed on all consecutive batches once you do "goto
next_batch", right?
> +
> + struct slab_sheaf *full;
> +
> + if (pcs->spare && pcs->spare->size > 0) {
> + stat(s, SHEAF_SWAP);
> + swap(pcs->main, pcs->spare);
> + goto do_alloc;
> + }
> +
> + full = barn_replace_empty_sheaf(pcs->barn, pcs->main);
> +
> + if (full) {
> + pcs->main = full;
> + goto do_alloc;
> + }
> +
> + localtry_unlock(&s->cpu_sheaves->lock);
> +
> + /*
> + * Once full sheaves in barn are depleted, let the bulk
> + * allocation continue from slab pages, otherwise we would just
> + * be copying arrays of pointers twice.
> + */
> + return allocated;
> + }
> +
> +do_alloc:
> +
> + main = pcs->main;
> + batch = min(size, main->size);
> +
> + main->size -= batch;
> + memcpy(p, main->objects + main->size, batch * sizeof(void *));
> +
> + localtry_unlock(&s->cpu_sheaves->lock);
> +
> + stat_add(s, ALLOC_PCS, batch);
> +
> + allocated += batch;
> +
> + if (batch < size) {
> + p += batch;
> + size -= batch;
> + goto next_batch;
> + }
> +
> + return allocated;
> +}
> +
> +
> /*
> * Inlined fastpath so that allocation functions (kmalloc, kmem_cache_alloc)
> * have the fastpath folded into their functions. So no function call
> @@ -4150,7 +4732,11 @@ static __fastpath_inline void *slab_alloc_node(struct kmem_cache *s, struct list
> if (unlikely(object))
> goto out;
>
> - object = __slab_alloc_node(s, gfpflags, node, addr, orig_size);
> + if (s->cpu_sheaves && (node == NUMA_NO_NODE))
> + object = alloc_from_pcs(s, gfpflags);
> +
> + 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);
> @@ -4521,6 +5107,232 @@ static void __slab_free(struct kmem_cache *s, struct slab *slab,
> discard_slab(s, slab);
> }
>
> +/*
> + * pcs is locked. We should have get rid of the spare sheaf and obtained an
> + * empty sheaf, while the main sheaf is full. We want to install the empty sheaf
> + * as a main sheaf, and make the current main sheaf a spare sheaf.
> + *
> + * However due to having relinquished the cpu_sheaves lock when obtaining
> + * the empty sheaf, we need to handle some unlikely but possible cases.
> + *
> + * If we put any sheaf to barn here, it's because we were interrupted or have
> + * been migrated to a different cpu, which should be rare enough so just ignore
> + * the barn's limits to simplify the handling.
> + */
> +static void __pcs_install_empty_sheaf(struct kmem_cache *s,
> + struct slub_percpu_sheaves *pcs, struct slab_sheaf *empty)
> +{
> + /* this is what we expect to find in nobody interrupted us */
s/in/if in the above comment
> + if (likely(!pcs->spare)) {
> + pcs->spare = pcs->main;
> + pcs->main = empty;
> + return;
> + }
> +
> + /*
> + * Unlikely because if the main sheaf had space, we would have just
> + * freed to it. Get rid of our empty sheaf.
> + */
> + if (pcs->main->size < s->sheaf_capacity) {
> + barn_put_empty_sheaf(pcs->barn, empty, true);
> + return;
> + }
> +
> + /* Also unlikely for the same reason */
> + if (pcs->spare->size < s->sheaf_capacity) {
> + stat(s, SHEAF_SWAP);
> + swap(pcs->main, pcs->spare);
> + barn_put_empty_sheaf(pcs->barn, empty, true);
> + return;
> + }
> +
> + barn_put_full_sheaf(pcs->barn, pcs->main, true);
> + pcs->main = empty;
> +}
> +
> +/*
> + * Free an object to the percpu sheaves.
> + * The object is expected to have passed slab_free_hook() already.
> + */
> +static __fastpath_inline
> +bool free_to_pcs(struct kmem_cache *s, void *object)
> +{
> + struct slub_percpu_sheaves *pcs;
> +
> +restart:
> + if (!localtry_trylock(&s->cpu_sheaves->lock))
> + return false;
> +
> + pcs = this_cpu_ptr(s->cpu_sheaves);
> +
> + if (unlikely(pcs->main->size == s->sheaf_capacity)) {
> +
> + struct slab_sheaf *empty;
> +
> + if (!pcs->spare) {
> + empty = barn_get_empty_sheaf(pcs->barn);
> + if (empty) {
> + pcs->spare = pcs->main;
> + pcs->main = empty;
> + goto do_free;
> + }
> + goto alloc_empty;
> + }
> +
> + if (pcs->spare->size < s->sheaf_capacity) {
> + stat(s, SHEAF_SWAP);
> + swap(pcs->main, pcs->spare);
> + goto do_free;
> + }
> +
> + empty = barn_replace_full_sheaf(pcs->barn, pcs->main);
This function reads easier now but if barn_replace_full_sheaf() could
ignore the MAX_FULL_SHEAVES and barn list trimming could be done
later, it would simplify this function even further.
> +
> + if (!IS_ERR(empty)) {
> + pcs->main = empty;
> + goto do_free;
> + }
> +
> + if (PTR_ERR(empty) == -E2BIG) {
> + /* Since we got here, spare exists and is full */
> + struct slab_sheaf *to_flush = pcs->spare;
> +
> + pcs->spare = NULL;
> + localtry_unlock(&s->cpu_sheaves->lock);
> +
> + sheaf_flush_unused(s, to_flush);
> + empty = to_flush;
> + goto got_empty;
> + }
> +
> +alloc_empty:
> + localtry_unlock(&s->cpu_sheaves->lock);
> +
> + empty = alloc_empty_sheaf(s, GFP_NOWAIT);
> +
> + if (!empty) {
> + if (sheaf_flush_main(s))
> + goto restart;
> + else
> + return false;
> + }
> +
> +got_empty:
> + if (!localtry_trylock(&s->cpu_sheaves->lock)) {
> + struct node_barn *barn;
> +
> + barn = get_node(s, numa_mem_id())->barn;
> +
> + barn_put_empty_sheaf(barn, empty, true);
> + return false;
> + }
> +
> + pcs = this_cpu_ptr(s->cpu_sheaves);
> + __pcs_install_empty_sheaf(s, pcs, empty);
> + }
> +
> +do_free:
> + pcs->main->objects[pcs->main->size++] = object;
> +
> + localtry_unlock(&s->cpu_sheaves->lock);
> +
> + stat(s, FREE_PCS);
> +
> + return true;
> +}
> +
> +/*
> + * Bulk free objects to the percpu sheaves.
> + * Unlike free_to_pcs() this includes the calls to all necessary hooks
> + * and the fallback to freeing to slab pages.
> + */
> +static void free_to_pcs_bulk(struct kmem_cache *s, size_t size, void **p)
> +{
> + struct slub_percpu_sheaves *pcs;
> + struct slab_sheaf *main;
> + unsigned int batch, i = 0;
> + bool init;
> +
> + init = slab_want_init_on_free(s);
> +
> + while (i < size) {
> + struct slab *slab = virt_to_slab(p[i]);
> +
> + memcg_slab_free_hook(s, slab, p + i, 1);
> + alloc_tagging_slab_free_hook(s, slab, p + i, 1);
> +
> + if (unlikely(!slab_free_hook(s, p[i], init, false))) {
> + p[i] = p[--size];
> + if (!size)
> + return;
> + continue;
> + }
> +
> + i++;
> + }
> +
> +next_batch:
nit: I think the section below would be more readable if structured
with fail handling blocks at the end. Something like this:
next_batch:
if (!localtry_trylock(&s->cpu_sheaves->lock))
goto fallback;
pcs = this_cpu_ptr(s->cpu_sheaves);
if (likely(pcs->main->size < s->sheaf_capacity))
goto do_free;
if (!pcs->spare) {
empty = barn_get_empty_sheaf(pcs->barn);
if (!empty)
goto no_empty;
pcs->spare = pcs->main;
pcs->main = empty;
goto do_free;
}
if (pcs->spare->size < s->sheaf_capacity) {
stat(s, SHEAF_SWAP);
swap(pcs->main, pcs->spare);
goto do_free;
}
empty = barn_replace_full_sheaf(pcs->barn, pcs->main);
if (IS_ERR(empty))
goto no_empty;
pcs->main = empty;
do_free:
main = pcs->main;
batch = min(size, s->sheaf_capacity - main->size);
memcpy(main->objects + main->size, p, batch * sizeof(void *));
main->size += batch;
localtry_unlock(&s->cpu_sheaves->lock);
stat_add(s, FREE_PCS, batch);
if (batch < size) {
p += batch;
size -= batch;
goto next_batch;
}
return;
no_empty:
localtry_unlock(&s->cpu_sheaves->lock);
/*
* if we depleted all empty sheaves in the barn or there are too
* many full sheaves, free the rest to slab pages
*/
fallback:
__kmem_cache_free_bulk(s, size, p);
}
> + if (!localtry_trylock(&s->cpu_sheaves->lock))
> + goto fallback;
> +
> + pcs = this_cpu_ptr(s->cpu_sheaves);
> +
> + if (unlikely(pcs->main->size == s->sheaf_capacity)) {
> +
> + struct slab_sheaf *empty;
> +
> + if (!pcs->spare) {
> + empty = barn_get_empty_sheaf(pcs->barn);
> + if (empty) {
> + pcs->spare = pcs->main;
> + pcs->main = empty;
> + goto do_free;
> + }
> + goto no_empty;
> + }
> +
> + if (pcs->spare->size < s->sheaf_capacity) {
> + stat(s, SHEAF_SWAP);
> + swap(pcs->main, pcs->spare);
> + goto do_free;
> + }
> +
> + empty = barn_replace_full_sheaf(pcs->barn, pcs->main);
> +
> + if (!IS_ERR(empty)) {
> + pcs->main = empty;
> + goto do_free;
> + }
> +
> +no_empty:
> + localtry_unlock(&s->cpu_sheaves->lock);
> +
> + /*
> + * if we depleted all empty sheaves in the barn or there are too
> + * many full sheaves, free the rest to slab pages
> + */
> +fallback:
> + __kmem_cache_free_bulk(s, size, p);
> + return;
> + }
> +
> +do_free:
> + main = pcs->main;
> + batch = min(size, s->sheaf_capacity - main->size);
> +
> + memcpy(main->objects + main->size, p, batch * sizeof(void *));
> + main->size += batch;
> +
> + localtry_unlock(&s->cpu_sheaves->lock);
> +
> + stat_add(s, FREE_PCS, batch);
> +
> + if (batch < size) {
> + p += batch;
> + size -= batch;
> + goto next_batch;
> + }
> +}
> +
> #ifndef CONFIG_SLUB_TINY
> /*
> * Fastpath with forced inlining to produce a kfree and kmem_cache_free that
> @@ -4607,7 +5419,10 @@ void slab_free(struct kmem_cache *s, struct slab *slab, void *object,
> memcg_slab_free_hook(s, slab, &object, 1);
> alloc_tagging_slab_free_hook(s, slab, &object, 1);
>
> - if (likely(slab_free_hook(s, object, slab_want_init_on_free(s), false)))
> + if (unlikely(!slab_free_hook(s, object, slab_want_init_on_free(s), false)))
> + return;
> +
> + if (!s->cpu_sheaves || !free_to_pcs(s, object))
> do_slab_free(s, slab, object, object, 1, addr);
> }
>
> @@ -5033,6 +5848,15 @@ void kmem_cache_free_bulk(struct kmem_cache *s, size_t size, void **p)
> if (!size)
> return;
>
> + /*
> + * freeing to sheaves is so incompatible with the detached freelist so
> + * once we go that way, we have to do everything differently
> + */
> + if (s && s->cpu_sheaves) {
> + free_to_pcs_bulk(s, size, p);
> + return;
> + }
> +
> do {
> struct detached_freelist df;
>
> @@ -5151,7 +5975,7 @@ static int __kmem_cache_alloc_bulk(struct kmem_cache *s, gfp_t flags,
> int kmem_cache_alloc_bulk_noprof(struct kmem_cache *s, gfp_t flags, size_t size,
> void **p)
> {
> - int i;
> + unsigned int i = 0;
>
> if (!size)
> return 0;
> @@ -5160,9 +5984,21 @@ int kmem_cache_alloc_bulk_noprof(struct kmem_cache *s, gfp_t flags, size_t size,
> if (unlikely(!s))
> return 0;
>
> - i = __kmem_cache_alloc_bulk(s, flags, size, p);
> - if (unlikely(i == 0))
> - return 0;
> + if (s->cpu_sheaves)
> + i = alloc_from_pcs_bulk(s, size, p);
> +
> + if (i < size) {
> + unsigned int j = __kmem_cache_alloc_bulk(s, flags, size - i, p + i);
> + /*
> + * If we ran out of memory, don't bother with freeing back to
> + * the percpu sheaves, we have bigger problems.
> + */
> + if (unlikely(j == 0)) {
> + if (i > 0)
> + __kmem_cache_free_bulk(s, i, p);
> + return 0;
> + }
> + }
>
> /*
> * memcg and kmem_cache debug support and memory initialization.
> @@ -5172,11 +6008,11 @@ int kmem_cache_alloc_bulk_noprof(struct kmem_cache *s, gfp_t flags, size_t size,
> slab_want_init_on_alloc(flags, s), s->object_size))) {
> return 0;
> }
> - return i;
> +
> + return size;
> }
> EXPORT_SYMBOL(kmem_cache_alloc_bulk_noprof);
>
> -
> /*
> * Object placement in a slab is made very easy because we always start at
> * offset 0. If we tune the size of the object to the alignment then we can
> @@ -5309,8 +6145,8 @@ static inline int calculate_order(unsigned int size)
> return -ENOSYS;
> }
>
> -static void
> -init_kmem_cache_node(struct kmem_cache_node *n)
> +static bool
> +init_kmem_cache_node(struct kmem_cache_node *n, struct node_barn *barn)
> {
> n->nr_partial = 0;
> spin_lock_init(&n->list_lock);
> @@ -5320,6 +6156,11 @@ init_kmem_cache_node(struct kmem_cache_node *n)
> atomic_long_set(&n->total_objects, 0);
> INIT_LIST_HEAD(&n->full);
> #endif
> + n->barn = barn;
> + if (barn)
> + barn_init(barn);
> +
> + return true;
> }
>
> #ifndef CONFIG_SLUB_TINY
> @@ -5350,6 +6191,30 @@ static inline int alloc_kmem_cache_cpus(struct kmem_cache *s)
> }
> #endif /* CONFIG_SLUB_TINY */
>
> +static int init_percpu_sheaves(struct kmem_cache *s)
> +{
> + int cpu;
> +
> + for_each_possible_cpu(cpu) {
> + struct slub_percpu_sheaves *pcs;
> + int nid;
> +
> + pcs = per_cpu_ptr(s->cpu_sheaves, cpu);
> +
> + localtry_lock_init(&pcs->lock);
> +
> + nid = cpu_to_mem(cpu);
> +
> + pcs->barn = get_node(s, nid)->barn;
> + pcs->main = alloc_empty_sheaf(s, GFP_KERNEL);
> +
> + if (!pcs->main)
> + return -ENOMEM;
> + }
> +
> + return 0;
> +}
> +
> static struct kmem_cache *kmem_cache_node;
>
> /*
> @@ -5385,7 +6250,7 @@ static void early_kmem_cache_node_alloc(int node)
> slab->freelist = get_freepointer(kmem_cache_node, n);
> slab->inuse = 1;
> kmem_cache_node->node[node] = n;
> - init_kmem_cache_node(n);
> + init_kmem_cache_node(n, NULL);
> inc_slabs_node(kmem_cache_node, node, slab->objects);
>
> /*
> @@ -5401,6 +6266,13 @@ static void free_kmem_cache_nodes(struct kmem_cache *s)
> struct kmem_cache_node *n;
>
> for_each_kmem_cache_node(s, node, n) {
> + if (n->barn) {
> + WARN_ON(n->barn->nr_full);
> + WARN_ON(n->barn->nr_empty);
> + kfree(n->barn);
> + n->barn = NULL;
> + }
> +
> s->node[node] = NULL;
> kmem_cache_free(kmem_cache_node, n);
> }
> @@ -5409,6 +6281,8 @@ static void free_kmem_cache_nodes(struct kmem_cache *s)
> void __kmem_cache_release(struct kmem_cache *s)
> {
> cache_random_seq_destroy(s);
> + if (s->cpu_sheaves)
> + pcs_destroy(s);
> #ifndef CONFIG_SLUB_TINY
> free_percpu(s->cpu_slab);
> #endif
> @@ -5421,20 +6295,27 @@ static int init_kmem_cache_nodes(struct kmem_cache *s)
>
> for_each_node_mask(node, slab_nodes) {
> struct kmem_cache_node *n;
> + struct node_barn *barn = NULL;
>
> if (slab_state == DOWN) {
> early_kmem_cache_node_alloc(node);
> continue;
> }
> +
> + if (s->cpu_sheaves) {
> + barn = kmalloc_node(sizeof(*barn), GFP_KERNEL, node);
> +
> + if (!barn)
> + return 0;
> + }
> +
> n = kmem_cache_alloc_node(kmem_cache_node,
> GFP_KERNEL, node);
> -
> - if (!n) {
> - free_kmem_cache_nodes(s);
> + if (!n)
> return 0;
> - }
>
> - init_kmem_cache_node(n);
> + init_kmem_cache_node(n, barn);
> +
> s->node[node] = n;
> }
> return 1;
> @@ -5690,6 +6571,8 @@ int __kmem_cache_shutdown(struct kmem_cache *s)
> flush_all_cpus_locked(s);
> /* Attempt to free all objects */
> for_each_kmem_cache_node(s, node, n) {
> + if (n->barn)
> + barn_shrink(s, n->barn);
> free_partial(s, n);
> if (n->nr_partial || node_nr_slabs(n))
> return 1;
> @@ -5893,6 +6776,9 @@ static int __kmem_cache_do_shrink(struct kmem_cache *s)
> for (i = 0; i < SHRINK_PROMOTE_MAX; i++)
> INIT_LIST_HEAD(promote + i);
>
> + if (n->barn)
> + barn_shrink(s, n->barn);
> +
> spin_lock_irqsave(&n->list_lock, flags);
>
> /*
> @@ -6005,12 +6891,24 @@ static int slab_mem_going_online_callback(void *arg)
> */
> mutex_lock(&slab_mutex);
> list_for_each_entry(s, &slab_caches, list) {
> + struct node_barn *barn = NULL;
> +
> /*
> * The structure may already exist if the node was previously
> * onlined and offlined.
> */
> if (get_node(s, nid))
> continue;
> +
> + if (s->cpu_sheaves) {
> + barn = kmalloc_node(sizeof(*barn), GFP_KERNEL, nid);
> +
> + if (!barn) {
> + ret = -ENOMEM;
> + goto out;
> + }
> + }
> +
> /*
> * XXX: kmem_cache_alloc_node will fallback to other nodes
> * since memory is not yet available from the node that
> @@ -6021,7 +6919,9 @@ static int slab_mem_going_online_callback(void *arg)
> ret = -ENOMEM;
> goto out;
> }
> - init_kmem_cache_node(n);
> +
> + init_kmem_cache_node(n, barn);
> +
> s->node[nid] = n;
> }
> /*
> @@ -6240,6 +7140,16 @@ int do_kmem_cache_create(struct kmem_cache *s, const char *name,
>
> set_cpu_partial(s);
>
> + if (args->sheaf_capacity) {
> + s->cpu_sheaves = alloc_percpu(struct slub_percpu_sheaves);
> + if (!s->cpu_sheaves) {
> + err = -ENOMEM;
> + goto out;
> + }
> + // TODO: increase capacity to grow slab_sheaf up to next kmalloc size?
> + s->sheaf_capacity = args->sheaf_capacity;
> + }
> +
> #ifdef CONFIG_NUMA
> s->remote_node_defrag_ratio = 1000;
> #endif
> @@ -6256,6 +7166,12 @@ int do_kmem_cache_create(struct kmem_cache *s, const char *name,
> if (!alloc_kmem_cache_cpus(s))
> goto out;
>
> + if (s->cpu_sheaves) {
> + err = init_percpu_sheaves(s);
> + if (err)
> + goto out;
> + }
> +
> err = 0;
>
> /* Mutex is not taken during early boot */
> @@ -6277,7 +7193,6 @@ int do_kmem_cache_create(struct kmem_cache *s, const char *name,
> __kmem_cache_release(s);
> return err;
> }
> -
> #ifdef SLAB_SUPPORTS_SYSFS
> static int count_inuse(struct slab *slab)
> {
> @@ -7055,8 +7970,10 @@ static ssize_t text##_store(struct kmem_cache *s, \
> } \
> SLAB_ATTR(text); \
>
> +STAT_ATTR(ALLOC_PCS, alloc_cpu_sheaf);
> STAT_ATTR(ALLOC_FASTPATH, alloc_fastpath);
> STAT_ATTR(ALLOC_SLOWPATH, alloc_slowpath);
> +STAT_ATTR(FREE_PCS, free_cpu_sheaf);
> STAT_ATTR(FREE_FASTPATH, free_fastpath);
> STAT_ATTR(FREE_SLOWPATH, free_slowpath);
> STAT_ATTR(FREE_FROZEN, free_frozen);
> @@ -7081,6 +7998,12 @@ STAT_ATTR(CPU_PARTIAL_ALLOC, cpu_partial_alloc);
> STAT_ATTR(CPU_PARTIAL_FREE, cpu_partial_free);
> STAT_ATTR(CPU_PARTIAL_NODE, cpu_partial_node);
> STAT_ATTR(CPU_PARTIAL_DRAIN, cpu_partial_drain);
> +STAT_ATTR(SHEAF_FLUSH_MAIN, sheaf_flush_main);
> +STAT_ATTR(SHEAF_FLUSH_OTHER, sheaf_flush_other);
> +STAT_ATTR(SHEAF_REFILL, sheaf_refill);
> +STAT_ATTR(SHEAF_SWAP, sheaf_swap);
> +STAT_ATTR(SHEAF_ALLOC, sheaf_alloc);
> +STAT_ATTR(SHEAF_FREE, sheaf_free);
> #endif /* CONFIG_SLUB_STATS */
>
> #ifdef CONFIG_KFENCE
> @@ -7142,8 +8065,10 @@ static struct attribute *slab_attrs[] = {
> &remote_node_defrag_ratio_attr.attr,
> #endif
> #ifdef CONFIG_SLUB_STATS
> + &alloc_cpu_sheaf_attr.attr,
> &alloc_fastpath_attr.attr,
> &alloc_slowpath_attr.attr,
> + &free_cpu_sheaf_attr.attr,
> &free_fastpath_attr.attr,
> &free_slowpath_attr.attr,
> &free_frozen_attr.attr,
> @@ -7168,6 +8093,12 @@ static struct attribute *slab_attrs[] = {
> &cpu_partial_free_attr.attr,
> &cpu_partial_node_attr.attr,
> &cpu_partial_drain_attr.attr,
> + &sheaf_flush_main_attr.attr,
> + &sheaf_flush_other_attr.attr,
> + &sheaf_refill_attr.attr,
> + &sheaf_swap_attr.attr,
> + &sheaf_alloc_attr.attr,
> + &sheaf_free_attr.attr,
> #endif
> #ifdef CONFIG_FAILSLAB
> &failslab_attr.attr,
>
> --
> 2.48.1
>
^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: [PATCH RFC v3 3/8] slab: add sheaf support for batching kfree_rcu() operations
2025-03-17 14:33 ` [PATCH RFC v3 3/8] slab: add sheaf support for batching kfree_rcu() operations Vlastimil Babka
2025-04-09 1:50 ` Harry Yoo
@ 2025-04-10 20:24 ` Suren Baghdasaryan
2025-04-22 15:18 ` Vlastimil Babka
1 sibling, 1 reply; 20+ messages in thread
From: Suren Baghdasaryan @ 2025-04-10 20:24 UTC (permalink / raw)
To: Vlastimil Babka
Cc: Liam R. Howlett, Christoph Lameter, David Rientjes,
Roman Gushchin, Harry Yoo, Uladzislau Rezki, linux-mm,
linux-kernel, rcu, maple-tree
On Mon, Mar 17, 2025 at 7:33 AM Vlastimil Babka <vbabka@suse.cz> wrote:
>
> Extend the sheaf infrastructure for more efficient kfree_rcu() handling.
> For caches with sheaves, on each cpu maintain a rcu_free sheaf in
> addition to main and spare sheaves.
>
> kfree_rcu() operations will try to put objects on this sheaf. Once full,
> the sheaf is detached and submitted to call_rcu() with a handler that
> will try to put it in the barn, or flush to slab pages using bulk free,
> when the barn is full. Then a new empty sheaf must be obtained to put
> more objects there.
>
> It's possible that no free sheaves are available to use for a new
> rcu_free sheaf, and the allocation in kfree_rcu() context can only use
> GFP_NOWAIT and thus may fail. In that case, fall back to the existing
> kfree_rcu() machinery.
>
> Expected advantages:
> - batching the kfree_rcu() operations, that could eventually replace the
> existing batching
> - sheaves can be reused for allocations via barn instead of being
> flushed to slabs, which is more efficient
> - this includes cases where only some cpus are allowed to process rcu
> callbacks (Android)
>
> Possible disadvantage:
> - objects might be waiting for more than their grace period (it is
> determined by the last object freed into the sheaf), increasing memory
> usage - but the existing batching does that too?
>
> Only implement this for CONFIG_KVFREE_RCU_BATCHED as the tiny
> implementation favors smaller memory footprint over performance.
>
> Signed-off-by: Vlastimil Babka <vbabka@suse.cz>
> Reviewed-by: Suren Baghdasaryan <surenb@google.com>
> ---
> mm/slab.h | 2 +
> mm/slab_common.c | 24 ++++++++
> mm/slub.c | 165 ++++++++++++++++++++++++++++++++++++++++++++++++++++++-
> 3 files changed, 189 insertions(+), 2 deletions(-)
>
> diff --git a/mm/slab.h b/mm/slab.h
> index 8daaec53b6ecfc44171191d421adb12e5cba2c58..94e9959e1aefa350d3d74e3f5309fde7a5cf2ec8 100644
> --- a/mm/slab.h
> +++ b/mm/slab.h
> @@ -459,6 +459,8 @@ static inline bool is_kmalloc_normal(struct kmem_cache *s)
> return !(s->flags & (SLAB_CACHE_DMA|SLAB_ACCOUNT|SLAB_RECLAIM_ACCOUNT));
> }
>
> +bool __kfree_rcu_sheaf(struct kmem_cache *s, void *obj);
> +
> /* Legal flag mask for kmem_cache_create(), for various configurations */
> #define SLAB_CORE_FLAGS (SLAB_HWCACHE_ALIGN | SLAB_CACHE_DMA | \
> SLAB_CACHE_DMA32 | SLAB_PANIC | \
> diff --git a/mm/slab_common.c b/mm/slab_common.c
> index ceeefb287899a82f30ad79b403556001c1860311..9496176770ed47491e01ed78e060a74771d5541e 100644
> --- a/mm/slab_common.c
> +++ b/mm/slab_common.c
> @@ -1613,6 +1613,27 @@ static void kfree_rcu_work(struct work_struct *work)
> kvfree_rcu_list(head);
> }
>
> +static bool kfree_rcu_sheaf(void *obj)
> +{
> + struct kmem_cache *s;
> + struct folio *folio;
> + struct slab *slab;
> +
> + if (is_vmalloc_addr(obj))
> + return false;
> +
> + folio = virt_to_folio(obj);
> + if (unlikely(!folio_test_slab(folio)))
> + return false;
> +
> + slab = folio_slab(folio);
> + s = slab->slab_cache;
> + if (s->cpu_sheaves)
> + return __kfree_rcu_sheaf(s, obj);
> +
> + return false;
> +}
> +
> static bool
> need_offload_krc(struct kfree_rcu_cpu *krcp)
> {
> @@ -1957,6 +1978,9 @@ void kvfree_call_rcu(struct rcu_head *head, void *ptr)
> if (!head)
> might_sleep();
>
> + if (kfree_rcu_sheaf(ptr))
> + return;
> +
> // Queue the object but don't yet schedule the batch.
> if (debug_rcu_head_queue(ptr)) {
> // Probable double kfree_rcu(), just leak.
> diff --git a/mm/slub.c b/mm/slub.c
> index fa3a6329713a9f45b189f27d4b1b334b54589c38..83f4395267dccfbc144920baa7d0a85a27fbb1b4 100644
> --- a/mm/slub.c
> +++ b/mm/slub.c
> @@ -350,6 +350,8 @@ enum stat_item {
> ALLOC_FASTPATH, /* Allocation from cpu slab */
> ALLOC_SLOWPATH, /* Allocation by getting a new cpu slab */
> FREE_PCS, /* Free to percpu sheaf */
> + FREE_RCU_SHEAF, /* Free to rcu_free sheaf */
> + FREE_RCU_SHEAF_FAIL, /* Failed to free to a rcu_free sheaf */
> FREE_FASTPATH, /* Free to cpu slab */
> FREE_SLOWPATH, /* Freeing not to cpu slab */
> FREE_FROZEN, /* Freeing to frozen slab */
> @@ -442,6 +444,7 @@ struct slab_sheaf {
> struct rcu_head rcu_head;
> struct list_head barn_list;
> };
> + struct kmem_cache *cache;
> unsigned int size;
> void *objects[];
> };
> @@ -450,6 +453,7 @@ struct slub_percpu_sheaves {
> localtry_lock_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() */
> struct node_barn *barn;
> };
>
> @@ -2461,6 +2465,8 @@ static struct slab_sheaf *alloc_empty_sheaf(struct kmem_cache *s, gfp_t gfp)
> if (unlikely(!sheaf))
> return NULL;
>
> + sheaf->cache = s;
> +
> stat(s, SHEAF_ALLOC);
>
> return sheaf;
> @@ -2585,6 +2591,24 @@ static void sheaf_flush_unused(struct kmem_cache *s, struct slab_sheaf *sheaf)
> sheaf->size = 0;
> }
>
> +static void __rcu_free_sheaf_prepare(struct kmem_cache *s,
> + struct slab_sheaf *sheaf);
> +
> +static void rcu_free_sheaf_nobarn(struct rcu_head *head)
> +{
> + struct slab_sheaf *sheaf;
> + struct kmem_cache *s;
> +
> + sheaf = container_of(head, struct slab_sheaf, rcu_head);
> + s = sheaf->cache;
> +
> + __rcu_free_sheaf_prepare(s, sheaf);
> +
> + sheaf_flush_unused(s, sheaf);
> +
> + free_empty_sheaf(s, sheaf);
> +}
> +
> /*
> * Caller needs to make sure migration is disabled in order to fully flush
> * single cpu's sheaves
> @@ -2597,7 +2621,7 @@ static void sheaf_flush_unused(struct kmem_cache *s, struct slab_sheaf *sheaf)
> static void pcs_flush_all(struct kmem_cache *s)
> {
> struct slub_percpu_sheaves *pcs;
> - struct slab_sheaf *spare;
> + struct slab_sheaf *spare, *rcu_free;
>
> localtry_lock(&s->cpu_sheaves->lock);
> pcs = this_cpu_ptr(s->cpu_sheaves);
> @@ -2605,6 +2629,9 @@ static void pcs_flush_all(struct kmem_cache *s)
> spare = pcs->spare;
> pcs->spare = NULL;
>
> + rcu_free = pcs->rcu_free;
> + pcs->rcu_free = NULL;
> +
> localtry_unlock(&s->cpu_sheaves->lock);
>
> if (spare) {
> @@ -2612,6 +2639,9 @@ static void pcs_flush_all(struct kmem_cache *s)
> free_empty_sheaf(s, spare);
> }
>
> + if (rcu_free)
> + call_rcu(&rcu_free->rcu_head, rcu_free_sheaf_nobarn);
> +
> sheaf_flush_main(s);
> }
>
> @@ -2628,6 +2658,11 @@ static void __pcs_flush_all_cpu(struct kmem_cache *s, unsigned int cpu)
> free_empty_sheaf(s, pcs->spare);
> pcs->spare = NULL;
> }
> +
> + if (pcs->rcu_free) {
> + call_rcu(&pcs->rcu_free->rcu_head, rcu_free_sheaf_nobarn);
> + pcs->rcu_free = NULL;
> + }
> }
>
> static void pcs_destroy(struct kmem_cache *s)
> @@ -2644,6 +2679,7 @@ static void pcs_destroy(struct kmem_cache *s)
> continue;
>
> WARN_ON(pcs->spare);
> + WARN_ON(pcs->rcu_free);
>
> if (!WARN_ON(pcs->main->size)) {
> free_empty_sheaf(s, pcs->main);
> @@ -3707,7 +3743,7 @@ static bool has_pcs_used(int cpu, struct kmem_cache *s)
>
> pcs = per_cpu_ptr(s->cpu_sheaves, cpu);
>
> - return (pcs->spare || pcs->main->size);
> + return (pcs->spare || pcs->rcu_free || pcs->main->size);
> }
>
> static void pcs_flush_all(struct kmem_cache *s);
> @@ -5240,6 +5276,122 @@ bool free_to_pcs(struct kmem_cache *s, void *object)
> return true;
> }
>
> +static void __rcu_free_sheaf_prepare(struct kmem_cache *s,
> + struct slab_sheaf *sheaf)
> +{
> + bool init = slab_want_init_on_free(s);
> + void **p = &sheaf->objects[0];
> + unsigned int i = 0;
> +
> + while (i < sheaf->size) {
> + struct slab *slab = virt_to_slab(p[i]);
> +
> + memcg_slab_free_hook(s, slab, p + i, 1);
> + alloc_tagging_slab_free_hook(s, slab, p + i, 1);
> +
> + if (unlikely(!slab_free_hook(s, p[i], init, false))) {
> + p[i] = p[--sheaf->size];
> + continue;
> + }
> +
> + i++;
> + }
> +}
> +
> +static void rcu_free_sheaf(struct rcu_head *head)
> +{
> + struct slab_sheaf *sheaf;
> + struct node_barn *barn;
> + struct kmem_cache *s;
> +
> + sheaf = container_of(head, struct slab_sheaf, rcu_head);
> +
> + s = sheaf->cache;
> +
> + __rcu_free_sheaf_prepare(s, sheaf);
> +
> + barn = get_node(s, numa_mem_id())->barn;
> +
> + /* due to slab_free_hook() */
> + if (unlikely(sheaf->size == 0))
> + goto empty;
> +
> + if (!barn_put_full_sheaf(barn, sheaf, false))
> + return;
> +
> + sheaf_flush_unused(s, sheaf);
> +
> +empty:
> + if (!barn_put_empty_sheaf(barn, sheaf, false))
> + return;
> +
> + free_empty_sheaf(s, sheaf);
> +}
> +
> +bool __kfree_rcu_sheaf(struct kmem_cache *s, void *obj)
> +{
> + struct slub_percpu_sheaves *pcs;
> + struct slab_sheaf *rcu_sheaf;
> +
> + if (!localtry_trylock(&s->cpu_sheaves->lock))
> + goto fail;
> +
> + pcs = this_cpu_ptr(s->cpu_sheaves);
> +
> + if (unlikely(!pcs->rcu_free)) {
> +
> + struct slab_sheaf *empty;
> +
> + empty = barn_get_empty_sheaf(pcs->barn);
> +
> + if (empty) {
> + pcs->rcu_free = empty;
> + goto do_free;
> + }
> +
> + localtry_unlock(&s->cpu_sheaves->lock);
> +
> + empty = alloc_empty_sheaf(s, GFP_NOWAIT);
> +
> + if (!empty)
> + goto fail;
> +
> + if (!localtry_trylock(&s->cpu_sheaves->lock))
> + goto fail;
> +
> + pcs = this_cpu_ptr(s->cpu_sheaves);
> +
> + if (unlikely(pcs->rcu_free))
> + barn_put_empty_sheaf(pcs->barn, empty, true);
> + else
> + pcs->rcu_free = empty;
> + }
> +
> +do_free:
> +
> + rcu_sheaf = pcs->rcu_free;
> +
> + rcu_sheaf->objects[rcu_sheaf->size++] = obj;
> +
> + if (likely(rcu_sheaf->size < s->sheaf_capacity)) {
> + localtry_unlock(&s->cpu_sheaves->lock);
> + stat(s, FREE_RCU_SHEAF);
> + return true;
> + }
> +
> + pcs->rcu_free = NULL;
> + localtry_unlock(&s->cpu_sheaves->lock);
> +
> + call_rcu(&rcu_sheaf->rcu_head, rcu_free_sheaf);
> +
> + stat(s, FREE_RCU_SHEAF);
> + return true;
nit: I think the above code could be simplified to:
do_free:
rcu_sheaf = pcs->rcu_free;
rcu_sheaf->objects[rcu_sheaf->size++] = obj;
if (likely(rcu_sheaf->size < s->sheaf_capacity))
rcu_sheaf = NULL;
else
pcs->rcu_free = NULL;
localtry_unlock(&s->cpu_sheaves->lock);
stat(s, FREE_RCU_SHEAF);
if (rcu_sheaf)
call_rcu(&rcu_sheaf->rcu_head, rcu_free_sheaf);
return true;
> +
> +fail:
> + stat(s, FREE_RCU_SHEAF_FAIL);
> + return false;
> +}
> +
> /*
> * Bulk free objects to the percpu sheaves.
> * Unlike free_to_pcs() this includes the calls to all necessary hooks
> @@ -6569,6 +6721,11 @@ int __kmem_cache_shutdown(struct kmem_cache *s)
> struct kmem_cache_node *n;
>
> flush_all_cpus_locked(s);
> +
> + /* we might have rcu sheaves in flight */
> + if (s->cpu_sheaves)
> + rcu_barrier();
> +
> /* Attempt to free all objects */
> for_each_kmem_cache_node(s, node, n) {
> if (n->barn)
> @@ -7974,6 +8131,8 @@ STAT_ATTR(ALLOC_PCS, alloc_cpu_sheaf);
> STAT_ATTR(ALLOC_FASTPATH, alloc_fastpath);
> STAT_ATTR(ALLOC_SLOWPATH, alloc_slowpath);
> STAT_ATTR(FREE_PCS, free_cpu_sheaf);
> +STAT_ATTR(FREE_RCU_SHEAF, free_rcu_sheaf);
> +STAT_ATTR(FREE_RCU_SHEAF_FAIL, free_rcu_sheaf_fail);
> STAT_ATTR(FREE_FASTPATH, free_fastpath);
> STAT_ATTR(FREE_SLOWPATH, free_slowpath);
> STAT_ATTR(FREE_FROZEN, free_frozen);
> @@ -8069,6 +8228,8 @@ static struct attribute *slab_attrs[] = {
> &alloc_fastpath_attr.attr,
> &alloc_slowpath_attr.attr,
> &free_cpu_sheaf_attr.attr,
> + &free_rcu_sheaf_attr.attr,
> + &free_rcu_sheaf_fail_attr.attr,
> &free_fastpath_attr.attr,
> &free_slowpath_attr.attr,
> &free_frozen_attr.attr,
>
> --
> 2.48.1
>
^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: [PATCH RFC v3 4/8] slab: sheaf prefilling for guaranteed allocations
2025-03-17 14:33 ` [PATCH RFC v3 4/8] slab: sheaf prefilling for guaranteed allocations Vlastimil Babka
@ 2025-04-10 20:47 ` Suren Baghdasaryan
2025-04-23 13:06 ` Vlastimil Babka
0 siblings, 1 reply; 20+ messages in thread
From: Suren Baghdasaryan @ 2025-04-10 20:47 UTC (permalink / raw)
To: Vlastimil Babka
Cc: Liam R. Howlett, Christoph Lameter, David Rientjes,
Roman Gushchin, Harry Yoo, Uladzislau Rezki, linux-mm,
linux-kernel, rcu, maple-tree
On Mon, Mar 17, 2025 at 7:33 AM Vlastimil Babka <vbabka@suse.cz> wrote:
>
> Add functions for efficient guaranteed allocations e.g. in a critical
> section that cannot sleep, when the exact number of allocations is not
> known beforehand, but an upper limit can be calculated.
>
> kmem_cache_prefill_sheaf() returns a sheaf containing at least given
> number of objects.
>
> kmem_cache_alloc_from_sheaf() will allocate an object from the sheaf
> and is guaranteed not to fail until depleted.
>
> kmem_cache_return_sheaf() is for giving the sheaf back to the slab
> allocator after the critical section. This will also attempt to refill
> it to cache's sheaf capacity for better efficiency of sheaves handling,
> but it's not stricly necessary to succeed.
>
> kmem_cache_refill_sheaf() can be used to refill a previously obtained
> sheaf to requested size. If the current size is sufficient, it does
> nothing. If the requested size exceeds cache's sheaf_capacity and the
> sheaf's current capacity, the sheaf will be replaced with a new one,
> hence the indirect pointer parameter.
>
> kmem_cache_sheaf_size() can be used to query the current size.
>
> The implementation supports requesting sizes that exceed cache's
> sheaf_capacity, but it is not efficient - such sheaves are allocated
> fresh in kmem_cache_prefill_sheaf() and flushed and freed immediately by
> kmem_cache_return_sheaf(). kmem_cache_refill_sheaf() might be especially
> ineffective when replacing a sheaf with a new one of a larger capacity.
> It is therefore better to size cache's sheaf_capacity accordingly.
>
> Signed-off-by: Vlastimil Babka <vbabka@suse.cz>
> Reviewed-by: Suren Baghdasaryan <surenb@google.com>
> ---
> include/linux/slab.h | 16 ++++
> mm/slub.c | 228 +++++++++++++++++++++++++++++++++++++++++++++++++++
> 2 files changed, 244 insertions(+)
>
> diff --git a/include/linux/slab.h b/include/linux/slab.h
> index 0e1b25228c77140d05b5b4433c9d7923de36ec05..dd01b67982e856b1b02f4f0e6fc557726e7f02a8 100644
> --- a/include/linux/slab.h
> +++ b/include/linux/slab.h
> @@ -829,6 +829,22 @@ void *kmem_cache_alloc_node_noprof(struct kmem_cache *s, gfp_t flags,
> int node) __assume_slab_alignment __malloc;
> #define kmem_cache_alloc_node(...) alloc_hooks(kmem_cache_alloc_node_noprof(__VA_ARGS__))
>
> +struct slab_sheaf *
> +kmem_cache_prefill_sheaf(struct kmem_cache *s, gfp_t gfp, unsigned int size);
> +
> +int kmem_cache_refill_sheaf(struct kmem_cache *s, gfp_t gfp,
> + struct slab_sheaf **sheafp, unsigned int size);
> +
> +void kmem_cache_return_sheaf(struct kmem_cache *s, gfp_t gfp,
> + struct slab_sheaf *sheaf);
> +
> +void *kmem_cache_alloc_from_sheaf_noprof(struct kmem_cache *cachep, gfp_t gfp,
> + struct slab_sheaf *sheaf) __assume_slab_alignment __malloc;
> +#define kmem_cache_alloc_from_sheaf(...) \
> + alloc_hooks(kmem_cache_alloc_from_sheaf_noprof(__VA_ARGS__))
> +
> +unsigned int kmem_cache_sheaf_size(struct slab_sheaf *sheaf);
> +
> /*
> * These macros allow declaring a kmem_buckets * parameter alongside size, which
> * can be compiled out with CONFIG_SLAB_BUCKETS=n so that a large number of call
> diff --git a/mm/slub.c b/mm/slub.c
> index 83f4395267dccfbc144920baa7d0a85a27fbb1b4..ab3532d5f41045d8268b12ad774541dcd066c4c4 100644
> --- a/mm/slub.c
> +++ b/mm/slub.c
> @@ -443,6 +443,8 @@ struct slab_sheaf {
> union {
> struct rcu_head rcu_head;
> struct list_head barn_list;
> + /* only used for prefilled sheafs */
> + unsigned int capacity;
> };
> struct kmem_cache *cache;
> unsigned int size;
> @@ -2748,6 +2750,30 @@ static int barn_put_full_sheaf(struct node_barn *barn, struct slab_sheaf *sheaf,
> return ret;
> }
>
> +static struct slab_sheaf *barn_get_full_or_empty_sheaf(struct node_barn *barn)
> +{
> + struct slab_sheaf *sheaf = NULL;
> + unsigned long flags;
> +
> + spin_lock_irqsave(&barn->lock, flags);
> +
> + if (barn->nr_full) {
> + sheaf = list_first_entry(&barn->sheaves_full, struct slab_sheaf,
> + barn_list);
> + list_del(&sheaf->barn_list);
> + barn->nr_full--;
> + } else if (barn->nr_empty) {
> + sheaf = list_first_entry(&barn->sheaves_empty,
> + struct slab_sheaf, barn_list);
> + list_del(&sheaf->barn_list);
> + barn->nr_empty--;
> + }
> +
> + spin_unlock_irqrestore(&barn->lock, flags);
> +
> + return sheaf;
> +}
> +
> /*
> * If a full sheaf is available, return it and put the supplied empty one to
> * barn. We ignore the limit on empty sheaves as the number of sheaves doesn't
> @@ -4844,6 +4870,208 @@ void *kmem_cache_alloc_node_noprof(struct kmem_cache *s, gfp_t gfpflags, int nod
> }
> EXPORT_SYMBOL(kmem_cache_alloc_node_noprof);
>
> +/*
> + * returns a sheaf that has least the requested size
> + * when prefilling is needed, do so with given gfp flags
> + *
> + * return NULL if sheaf allocation or prefilling failed
> + */
> +struct slab_sheaf *
> +kmem_cache_prefill_sheaf(struct kmem_cache *s, gfp_t gfp, unsigned int size)
> +{
> + struct slub_percpu_sheaves *pcs;
> + struct slab_sheaf *sheaf = NULL;
> +
> + if (unlikely(size > s->sheaf_capacity)) {
> + sheaf = kzalloc(struct_size(sheaf, objects, size), gfp);
> + if (!sheaf)
> + return NULL;
> +
> + sheaf->cache = s;
> + sheaf->capacity = size;
> +
> + if (!__kmem_cache_alloc_bulk(s, gfp, size,
> + &sheaf->objects[0])) {
> + kfree(sheaf);
> + return NULL;
> + }
> +
> + sheaf->size = size;
> +
> + return sheaf;
> + }
> +
> + localtry_lock(&s->cpu_sheaves->lock);
> + pcs = this_cpu_ptr(s->cpu_sheaves);
> +
> + if (pcs->spare) {
> + sheaf = pcs->spare;
> + pcs->spare = NULL;
> + }
> +
> + if (!sheaf)
> + sheaf = barn_get_full_or_empty_sheaf(pcs->barn);
> +
> + localtry_unlock(&s->cpu_sheaves->lock);
> +
> + if (!sheaf)
> + sheaf = alloc_empty_sheaf(s, gfp);
> +
> + if (sheaf && sheaf->size < size) {
> + if (refill_sheaf(s, sheaf, gfp)) {
> + sheaf_flush_unused(s, sheaf);
> + free_empty_sheaf(s, sheaf);
> + sheaf = NULL;
> + }
> + }
> +
> + if (sheaf)
> + sheaf->capacity = s->sheaf_capacity;
> +
> + return sheaf;
> +}
> +
> +/*
> + * Use this to return a sheaf obtained by kmem_cache_prefill_sheaf()
> + *
> + * If the sheaf cannot simply become the percpu spare sheaf, but there's space
> + * for a full sheaf in the barn, we try to refill the sheaf back to the cache's
> + * sheaf_capacity to avoid handling partially full sheaves.
> + *
> + * If the refill fails because gfp is e.g. GFP_NOWAIT, or the barn is full, the
> + * sheaf is instead flushed and freed.
> + */
> +void kmem_cache_return_sheaf(struct kmem_cache *s, gfp_t gfp,
> + struct slab_sheaf *sheaf)
> +{
> + struct slub_percpu_sheaves *pcs;
> + bool refill = false;
> + struct node_barn *barn;
> +
> + if (unlikely(sheaf->capacity != s->sheaf_capacity)) {
> + sheaf_flush_unused(s, sheaf);
> + kfree(sheaf);
> + return;
> + }
> +
> + localtry_lock(&s->cpu_sheaves->lock);
> + pcs = this_cpu_ptr(s->cpu_sheaves);
> +
> + if (!pcs->spare) {
> + pcs->spare = sheaf;
> + sheaf = NULL;
> + } else if (data_race(pcs->barn->nr_full) < MAX_FULL_SHEAVES) {
> + barn = pcs->barn;
> + refill = true;
> + }
> +
> + localtry_unlock(&s->cpu_sheaves->lock);
> +
> + if (!sheaf)
> + return;
> +
> + /*
> + * if the barn is full of full sheaves or we fail to refill the sheaf,
> + * simply flush and free it
> + */
> + if (!refill || refill_sheaf(s, sheaf, gfp)) {
> + sheaf_flush_unused(s, sheaf);
> + free_empty_sheaf(s, sheaf);
> + return;
> + }
> +
> + /* we racily determined the sheaf would fit, so now force it */
> + barn_put_full_sheaf(barn, sheaf, true);
> +}
> +
> +/*
> + * refill a sheaf previously returned by kmem_cache_prefill_sheaf to at least
> + * the given size
> + *
> + * the sheaf might be replaced by a new one when requesting more than
> + * s->sheaf_capacity objects if such replacement is necessary, but the refill
> + * fails (returning -ENOMEM), the existing sheaf is left intact
> + *
> + * In practice we always refill to full sheaf's capacity.
> + */
> +int kmem_cache_refill_sheaf(struct kmem_cache *s, gfp_t gfp,
> + struct slab_sheaf **sheafp, unsigned int size)
nit: Would returning a refilled sheaf be a slightly better API than
passing pointer to a pointer?
> +{
> + struct slab_sheaf *sheaf;
> +
> + /*
> + * TODO: do we want to support *sheaf == NULL to be equivalent of
> + * kmem_cache_prefill_sheaf() ?
> + */
> + if (!sheafp || !(*sheafp))
> + return -EINVAL;
> +
> + sheaf = *sheafp;
> + if (sheaf->size >= size)
> + return 0;
> +
> + if (likely(sheaf->capacity >= size)) {
> + if (likely(sheaf->capacity == s->sheaf_capacity))
> + return refill_sheaf(s, sheaf, gfp);
> +
> + if (!__kmem_cache_alloc_bulk(s, gfp, sheaf->capacity - sheaf->size,
> + &sheaf->objects[sheaf->size])) {
> + return -ENOMEM;
> + }
> + sheaf->size = sheaf->capacity;
> +
> + return 0;
> + }
> +
> + /*
> + * We had a regular sized sheaf and need an oversize one, or we had an
> + * oversize one already but need a larger one now.
> + * This should be a very rare path so let's not complicate it.
> + */
> + sheaf = kmem_cache_prefill_sheaf(s, gfp, size);
> + if (!sheaf)
> + return -ENOMEM;
> +
> + kmem_cache_return_sheaf(s, gfp, *sheafp);
> + *sheafp = sheaf;
> + return 0;
> +}
> +
> +/*
> + * Allocate from a sheaf obtained by kmem_cache_prefill_sheaf()
> + *
> + * Guaranteed not to fail as many allocations as was the requested size.
> + * After the sheaf is emptied, it fails - no fallback to the slab cache itself.
> + *
> + * The gfp parameter is meant only to specify __GFP_ZERO or __GFP_ACCOUNT
> + * memcg charging is forced over limit if necessary, to avoid failure.
> + */
> +void *
> +kmem_cache_alloc_from_sheaf_noprof(struct kmem_cache *s, gfp_t gfp,
> + struct slab_sheaf *sheaf)
> +{
> + void *ret = NULL;
> + bool init;
> +
> + if (sheaf->size == 0)
> + goto out;
> +
> + ret = sheaf->objects[--sheaf->size];
> +
> + init = slab_want_init_on_alloc(gfp, s);
> +
> + /* add __GFP_NOFAIL to force successful memcg charging */
> + slab_post_alloc_hook(s, NULL, gfp | __GFP_NOFAIL, 1, &ret, init, s->object_size);
> +out:
> + trace_kmem_cache_alloc(_RET_IP_, ret, s, gfp, NUMA_NO_NODE);
> +
> + return ret;
> +}
> +
> +unsigned int kmem_cache_sheaf_size(struct slab_sheaf *sheaf)
> +{
> + return sheaf->size;
> +}
> /*
> * To avoid unnecessary overhead, we pass through large allocation requests
> * directly to the page allocator. We use __GFP_COMP, because we will need to
>
> --
> 2.48.1
>
^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: [PATCH RFC v3 2/8] slab: add opt-in caching layer of percpu sheaves
2025-04-10 19:51 ` Suren Baghdasaryan
@ 2025-04-22 15:02 ` Vlastimil Babka
0 siblings, 0 replies; 20+ messages in thread
From: Vlastimil Babka @ 2025-04-22 15:02 UTC (permalink / raw)
To: Suren Baghdasaryan
Cc: Liam R. Howlett, Christoph Lameter, David Rientjes,
Roman Gushchin, Harry Yoo, Uladzislau Rezki, linux-mm,
linux-kernel, rcu, maple-tree
On 4/10/25 21:51, Suren Baghdasaryan wrote:
>> +static void __pcs_flush_all_cpu(struct kmem_cache *s, unsigned int cpu)
>> +{
>> + struct slub_percpu_sheaves *pcs;
>> +
>> + pcs = per_cpu_ptr(s->cpu_sheaves, cpu);
>> +
>> + /* The cpu is not executing anymore so we don't need pcs->lock */
>> + sheaf_flush_unused(s, pcs->main);
>
> You are flushing pcs->main but sheaf_flush_unused() will account that
> in SHEAF_FLUSH_OTHER instead of SHEAF_FLUSH_MAIN. Perhaps
> sheaf_flush_unused() needs a parameter to indicate which counter to be
> incremented.
Hm it's technically true, but it's a cpu hotremove operation so rather rare
and not performance sensitive and one could argue it's not a main sheaf (of
an active cpu) anymore. So I rather went with a comment than complicating
the code.
>> + if (pcs->spare) {
>> + sheaf_flush_unused(s, pcs->spare);
>> + free_empty_sheaf(s, pcs->spare);
>> + pcs->spare = NULL;
>> + }
>> +}
>> +
>> +static void pcs_destroy(struct kmem_cache *s)
>> +{
>> + int cpu;
>> +
>> + for_each_possible_cpu(cpu) {
>> + struct slub_percpu_sheaves *pcs;
>> +
>> + pcs = per_cpu_ptr(s->cpu_sheaves, cpu);
>> +
>> + /* can happen when unwinding failed create */
>> + if (!pcs->main)
>> + continue;
>> +
>> + WARN_ON(pcs->spare);
>> +
>> + if (!WARN_ON(pcs->main->size)) {
>
> If pcs->main->size > 0, shouldn't we flush pcs->main? I understand
> it's not a normal situation but I think something like this would be
> more correct:
>
> if (WARN_ON(pcs->main->size))
> sheaf_flush_unused(s, pcs->main);
> free_empty_sheaf(s, pcs->main);
> pcs->main = NULL;
Initially I agreed but then I realized we only reach this code when we
already found all slabs only containing free objects. So if we then find
some in sheaves it means something must have gone terribly wrong so trying
to flush can only make things worse. I've added a comment instead.
>> + free_empty_sheaf(s, pcs->main);
>> + pcs->main = NULL;
>> + }
>> + }
>> +
>> + free_percpu(s->cpu_sheaves);
>> + s->cpu_sheaves = NULL;
>> +}
>> +
>> +static struct slab_sheaf *barn_get_empty_sheaf(struct node_barn *barn)
>> +{
>> + struct slab_sheaf *empty = NULL;
>> + unsigned long flags;
>> +
>> + spin_lock_irqsave(&barn->lock, flags);
>> +
>> + if (barn->nr_empty) {
>> + empty = list_first_entry(&barn->sheaves_empty,
>> + struct slab_sheaf, barn_list);
>> + list_del(&empty->barn_list);
>> + barn->nr_empty--;
>> + }
>> +
>> + spin_unlock_irqrestore(&barn->lock, flags);
>> +
>> + return empty;
>> +}
>> +
>> +static int barn_put_empty_sheaf(struct node_barn *barn,
>> + struct slab_sheaf *sheaf, bool ignore_limit)
>
> This ignore_limit in barn_put_empty_sheaf()/barn_put_full_sheaf() is
> sticking out and really used only inside rcu_free_sheaf() in the next
> patch. Every time I saw the return value of these functions ignored I
> had to remind myself that they pass ignore_limit=true, so the function
> can't really fail. Maybe we could get rid of this flag and do trimming
> of barn lists inside rcu_free_sheaf() separately in one go? IIUC
Good suggestion, didn't realize the barn_put_() are only used in the
fallback-due-to-a-race-or-cpu-migration paths, so did as you suggested.
> because we ignore the limits in all other places, at the time of
> rcu_free_sheaf() we might end up with a barn having many more sheaves
> than the limit allows for, so trimming in bulk might be even more
> productive.
There are many caches with no rcu freeing happening so making
rcu_free_sheaf() a bulk trimming point could be insufficient. I'd just leave
it for now and hope that ignoring limits only due to races won't cause barns
to grow more than it could self-correct for just by further allocation/freeing.
>> +{
>> + unsigned long flags;
>> + int ret = 0;
>> +
>> + spin_lock_irqsave(&barn->lock, flags);
>> +
>> + if (!ignore_limit && barn->nr_empty >= MAX_EMPTY_SHEAVES) {
>> + ret = -E2BIG;
>> + } else {
>> + list_add(&sheaf->barn_list, &barn->sheaves_empty);
>> + barn->nr_empty++;
>> + }
>> +
>> + spin_unlock_irqrestore(&barn->lock, flags);
>> + return ret;
>> +}
>> +
>> +static int barn_put_full_sheaf(struct node_barn *barn, struct slab_sheaf *sheaf,
>> + bool ignore_limit)
>
> Can this function be called for partially populated sheaves or only
> full ones? I think rcu_free_sheaf() in the next patch might end up
> calling it for a partially populated sheaf.
It can, but the code handles not-really-full sheaves fine and it's easier to
allow them than try to be strict, there should be just a bit lower
efficiency in debug scenarios and that's fine. Adding a comment.
>> +{
>> + unsigned long flags;
>> + int ret = 0;
>> +
>> + spin_lock_irqsave(&barn->lock, flags);
>> +
>> + if (!ignore_limit && barn->nr_full >= MAX_FULL_SHEAVES) {
>> + ret = -E2BIG;
>> + } else {
>> + list_add(&sheaf->barn_list, &barn->sheaves_full);
>> + barn->nr_full++;
>> + }
>> +
>> + spin_unlock_irqrestore(&barn->lock, flags);
>> + return ret;
>> +}
>> +
>> +/*
>> + * If a full sheaf is available, return it and put the supplied empty one to
>> + * barn. We ignore the limit on empty sheaves as the number of sheaves doesn't
>> + * change.
>
> I'm unclear why we ignore the limit here but not in
> barn_replace_full_sheaf(). Maybe because full sheaves consume more
> memory?
Yes.
> But then why do we mostly pass ignore_limit=true when invoking
> barn_put_full_sheaf()?
Not anymore with your suggestion.
> Explanation of this limit logic needs to be
> clarified.
>
>> +static __fastpath_inline
>> +unsigned int alloc_from_pcs_bulk(struct kmem_cache *s, size_t size, void **p)
>> +{
>> + struct slub_percpu_sheaves *pcs;
>> + struct slab_sheaf *main;
>> + unsigned int allocated = 0;
>> + unsigned int batch;
>> +
>> +next_batch:
>> + if (!localtry_trylock(&s->cpu_sheaves->lock))
>> + return allocated;
>> +
>> + pcs = this_cpu_ptr(s->cpu_sheaves);
>> +
>> + if (unlikely(pcs->main->size == 0)) {
>
> The above condition is unlikely only for the first batch. I think it's
> actually guaranteed on all consecutive batches once you do "goto
> next_batch", right?
Hm yes but perhaps bulk allocs larger than batch size are rare?
>> +static __fastpath_inline
>> +bool free_to_pcs(struct kmem_cache *s, void *object)
>> +{
>> + struct slub_percpu_sheaves *pcs;
>> +
>> +restart:
>> + if (!localtry_trylock(&s->cpu_sheaves->lock))
>> + return false;
>> +
>> + pcs = this_cpu_ptr(s->cpu_sheaves);
>> +
>> + if (unlikely(pcs->main->size == s->sheaf_capacity)) {
>> +
>> + struct slab_sheaf *empty;
>> +
>> + if (!pcs->spare) {
>> + empty = barn_get_empty_sheaf(pcs->barn);
>> + if (empty) {
>> + pcs->spare = pcs->main;
>> + pcs->main = empty;
>> + goto do_free;
>> + }
>> + goto alloc_empty;
>> + }
>> +
>> + if (pcs->spare->size < s->sheaf_capacity) {
>> + stat(s, SHEAF_SWAP);
>> + swap(pcs->main, pcs->spare);
>> + goto do_free;
>> + }
>> +
>> + empty = barn_replace_full_sheaf(pcs->barn, pcs->main);
>
> This function reads easier now but if barn_replace_full_sheaf() could
> ignore the MAX_FULL_SHEAVES and barn list trimming could be done
> later, it would simplify this function even further.
It could increase barn lock contention to put full sheaves there over limit
and then flush them afterwards so I think it's better to not do that.
Especially with "slab: determine barn status racily outside of lock".
>
> nit: I think the section below would be more readable if structured
> with fail handling blocks at the end. Something like this:
>
> next_batch:
> if (!localtry_trylock(&s->cpu_sheaves->lock))
> goto fallback;
>
> pcs = this_cpu_ptr(s->cpu_sheaves);
>
> if (likely(pcs->main->size < s->sheaf_capacity))
> goto do_free;
Nice suggestion, did that. Thanks.
^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: [PATCH RFC v3 3/8] slab: add sheaf support for batching kfree_rcu() operations
2025-04-10 20:24 ` Suren Baghdasaryan
@ 2025-04-22 15:18 ` Vlastimil Babka
0 siblings, 0 replies; 20+ messages in thread
From: Vlastimil Babka @ 2025-04-22 15:18 UTC (permalink / raw)
To: Suren Baghdasaryan
Cc: Liam R. Howlett, Christoph Lameter, David Rientjes,
Roman Gushchin, Harry Yoo, Uladzislau Rezki, linux-mm,
linux-kernel, rcu, maple-tree
On 4/10/25 22:24, Suren Baghdasaryan wrote:
> On Mon, Mar 17, 2025 at 7:33 AM Vlastimil Babka <vbabka@suse.cz> wrote:
>> +do_free:
>> +
>> + rcu_sheaf = pcs->rcu_free;
>> +
>> + rcu_sheaf->objects[rcu_sheaf->size++] = obj;
>> +
>> + if (likely(rcu_sheaf->size < s->sheaf_capacity)) {
>> + localtry_unlock(&s->cpu_sheaves->lock);
>> + stat(s, FREE_RCU_SHEAF);
>> + return true;
>> + }
>> +
>> + pcs->rcu_free = NULL;
>> + localtry_unlock(&s->cpu_sheaves->lock);
>> +
>> + call_rcu(&rcu_sheaf->rcu_head, rcu_free_sheaf);
>> +
>> + stat(s, FREE_RCU_SHEAF);
>> + return true;
>
> nit: I think the above code could be simplified to:
>
> do_free:
> rcu_sheaf = pcs->rcu_free;
> rcu_sheaf->objects[rcu_sheaf->size++] = obj;
> if (likely(rcu_sheaf->size < s->sheaf_capacity))
> rcu_sheaf = NULL;
> else
> pcs->rcu_free = NULL;
>
> localtry_unlock(&s->cpu_sheaves->lock);
> stat(s, FREE_RCU_SHEAF);
> if (rcu_sheaf)
> call_rcu(&rcu_sheaf->rcu_head, rcu_free_sheaf);
>
> return true;
Right, done. Thanks.
^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: [PATCH RFC v3 4/8] slab: sheaf prefilling for guaranteed allocations
2025-04-10 20:47 ` Suren Baghdasaryan
@ 2025-04-23 13:06 ` Vlastimil Babka
2025-04-23 17:13 ` Suren Baghdasaryan
0 siblings, 1 reply; 20+ messages in thread
From: Vlastimil Babka @ 2025-04-23 13:06 UTC (permalink / raw)
To: Suren Baghdasaryan
Cc: Liam R. Howlett, Christoph Lameter, David Rientjes,
Roman Gushchin, Harry Yoo, Uladzislau Rezki, linux-mm,
linux-kernel, rcu, maple-tree
On 4/10/25 22:47, Suren Baghdasaryan wrote:
>> +/*
>> + * refill a sheaf previously returned by kmem_cache_prefill_sheaf to at least
>> + * the given size
>> + *
>> + * the sheaf might be replaced by a new one when requesting more than
>> + * s->sheaf_capacity objects if such replacement is necessary, but the refill
>> + * fails (returning -ENOMEM), the existing sheaf is left intact
>> + *
>> + * In practice we always refill to full sheaf's capacity.
>> + */
>> +int kmem_cache_refill_sheaf(struct kmem_cache *s, gfp_t gfp,
>> + struct slab_sheaf **sheafp, unsigned int size)
>
> nit: Would returning a refilled sheaf be a slightly better API than
> passing pointer to a pointer?
I'm not sure it would be simpler to use, since we need to be able to
indicate -ENOMEM which would presumably become NULL, so the user would have
to store the existing sheaf pointer and not just blindly do "sheaf =
refill(sheaf)". Or the semantics would have to be that in case of failure
the existing sheaf is returned and caller is left with nothing. Liam, what
do you think?
>> +{
>> + struct slab_sheaf *sheaf;
>> +
>> + /*
>> + * TODO: do we want to support *sheaf == NULL to be equivalent of
>> + * kmem_cache_prefill_sheaf() ?
>> + */
>> + if (!sheafp || !(*sheafp))
>> + return -EINVAL;
>> +
>> + sheaf = *sheafp;
>> + if (sheaf->size >= size)
>> + return 0;
>> +
>> + if (likely(sheaf->capacity >= size)) {
>> + if (likely(sheaf->capacity == s->sheaf_capacity))
>> + return refill_sheaf(s, sheaf, gfp);
>> +
>> + if (!__kmem_cache_alloc_bulk(s, gfp, sheaf->capacity - sheaf->size,
>> + &sheaf->objects[sheaf->size])) {
>> + return -ENOMEM;
>> + }
>> + sheaf->size = sheaf->capacity;
>> +
>> + return 0;
>> + }
>> +
>> + /*
>> + * We had a regular sized sheaf and need an oversize one, or we had an
>> + * oversize one already but need a larger one now.
>> + * This should be a very rare path so let's not complicate it.
>> + */
>> + sheaf = kmem_cache_prefill_sheaf(s, gfp, size);
>> + if (!sheaf)
>> + return -ENOMEM;
>> +
>> + kmem_cache_return_sheaf(s, gfp, *sheafp);
>> + *sheafp = sheaf;
>> + return 0;
>> +}
>> +
>> +/*
>> + * Allocate from a sheaf obtained by kmem_cache_prefill_sheaf()
>> + *
>> + * Guaranteed not to fail as many allocations as was the requested size.
>> + * After the sheaf is emptied, it fails - no fallback to the slab cache itself.
>> + *
>> + * The gfp parameter is meant only to specify __GFP_ZERO or __GFP_ACCOUNT
>> + * memcg charging is forced over limit if necessary, to avoid failure.
>> + */
>> +void *
>> +kmem_cache_alloc_from_sheaf_noprof(struct kmem_cache *s, gfp_t gfp,
>> + struct slab_sheaf *sheaf)
>> +{
>> + void *ret = NULL;
>> + bool init;
>> +
>> + if (sheaf->size == 0)
>> + goto out;
>> +
>> + ret = sheaf->objects[--sheaf->size];
>> +
>> + init = slab_want_init_on_alloc(gfp, s);
>> +
>> + /* add __GFP_NOFAIL to force successful memcg charging */
>> + slab_post_alloc_hook(s, NULL, gfp | __GFP_NOFAIL, 1, &ret, init, s->object_size);
>> +out:
>> + trace_kmem_cache_alloc(_RET_IP_, ret, s, gfp, NUMA_NO_NODE);
>> +
>> + return ret;
>> +}
>> +
>> +unsigned int kmem_cache_sheaf_size(struct slab_sheaf *sheaf)
>> +{
>> + return sheaf->size;
>> +}
>> /*
>> * To avoid unnecessary overhead, we pass through large allocation requests
>> * directly to the page allocator. We use __GFP_COMP, because we will need to
>>
>> --
>> 2.48.1
>>
^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: [PATCH RFC v3 4/8] slab: sheaf prefilling for guaranteed allocations
2025-04-23 13:06 ` Vlastimil Babka
@ 2025-04-23 17:13 ` Suren Baghdasaryan
0 siblings, 0 replies; 20+ messages in thread
From: Suren Baghdasaryan @ 2025-04-23 17:13 UTC (permalink / raw)
To: Vlastimil Babka
Cc: Liam R. Howlett, Christoph Lameter, David Rientjes,
Roman Gushchin, Harry Yoo, Uladzislau Rezki, linux-mm,
linux-kernel, rcu, maple-tree
On Wed, Apr 23, 2025 at 6:06 AM Vlastimil Babka <vbabka@suse.cz> wrote:
>
> On 4/10/25 22:47, Suren Baghdasaryan wrote:
> >> +/*
> >> + * refill a sheaf previously returned by kmem_cache_prefill_sheaf to at least
> >> + * the given size
> >> + *
> >> + * the sheaf might be replaced by a new one when requesting more than
> >> + * s->sheaf_capacity objects if such replacement is necessary, but the refill
> >> + * fails (returning -ENOMEM), the existing sheaf is left intact
> >> + *
> >> + * In practice we always refill to full sheaf's capacity.
> >> + */
> >> +int kmem_cache_refill_sheaf(struct kmem_cache *s, gfp_t gfp,
> >> + struct slab_sheaf **sheafp, unsigned int size)
> >
> > nit: Would returning a refilled sheaf be a slightly better API than
> > passing pointer to a pointer?
>
> I'm not sure it would be simpler to use, since we need to be able to
> indicate -ENOMEM which would presumably become NULL, so the user would have
> to store the existing sheaf pointer and not just blindly do "sheaf =
> refill(sheaf)".
Ack.
> Or the semantics would have to be that in case of failure
> the existing sheaf is returned and caller is left with nothing. Liam, what
> do you think?
That sounds confusing. Compared to that alternative, I would prefer
keeping it the way it is now.
>
> >> +{
> >> + struct slab_sheaf *sheaf;
> >> +
> >> + /*
> >> + * TODO: do we want to support *sheaf == NULL to be equivalent of
> >> + * kmem_cache_prefill_sheaf() ?
> >> + */
> >> + if (!sheafp || !(*sheafp))
> >> + return -EINVAL;
> >> +
> >> + sheaf = *sheafp;
> >> + if (sheaf->size >= size)
> >> + return 0;
> >> +
> >> + if (likely(sheaf->capacity >= size)) {
> >> + if (likely(sheaf->capacity == s->sheaf_capacity))
> >> + return refill_sheaf(s, sheaf, gfp);
> >> +
> >> + if (!__kmem_cache_alloc_bulk(s, gfp, sheaf->capacity - sheaf->size,
> >> + &sheaf->objects[sheaf->size])) {
> >> + return -ENOMEM;
> >> + }
> >> + sheaf->size = sheaf->capacity;
> >> +
> >> + return 0;
> >> + }
> >> +
> >> + /*
> >> + * We had a regular sized sheaf and need an oversize one, or we had an
> >> + * oversize one already but need a larger one now.
> >> + * This should be a very rare path so let's not complicate it.
> >> + */
> >> + sheaf = kmem_cache_prefill_sheaf(s, gfp, size);
> >> + if (!sheaf)
> >> + return -ENOMEM;
> >> +
> >> + kmem_cache_return_sheaf(s, gfp, *sheafp);
> >> + *sheafp = sheaf;
> >> + return 0;
> >> +}
> >> +
> >> +/*
> >> + * Allocate from a sheaf obtained by kmem_cache_prefill_sheaf()
> >> + *
> >> + * Guaranteed not to fail as many allocations as was the requested size.
> >> + * After the sheaf is emptied, it fails - no fallback to the slab cache itself.
> >> + *
> >> + * The gfp parameter is meant only to specify __GFP_ZERO or __GFP_ACCOUNT
> >> + * memcg charging is forced over limit if necessary, to avoid failure.
> >> + */
> >> +void *
> >> +kmem_cache_alloc_from_sheaf_noprof(struct kmem_cache *s, gfp_t gfp,
> >> + struct slab_sheaf *sheaf)
> >> +{
> >> + void *ret = NULL;
> >> + bool init;
> >> +
> >> + if (sheaf->size == 0)
> >> + goto out;
> >> +
> >> + ret = sheaf->objects[--sheaf->size];
> >> +
> >> + init = slab_want_init_on_alloc(gfp, s);
> >> +
> >> + /* add __GFP_NOFAIL to force successful memcg charging */
> >> + slab_post_alloc_hook(s, NULL, gfp | __GFP_NOFAIL, 1, &ret, init, s->object_size);
> >> +out:
> >> + trace_kmem_cache_alloc(_RET_IP_, ret, s, gfp, NUMA_NO_NODE);
> >> +
> >> + return ret;
> >> +}
> >> +
> >> +unsigned int kmem_cache_sheaf_size(struct slab_sheaf *sheaf)
> >> +{
> >> + return sheaf->size;
> >> +}
> >> /*
> >> * To avoid unnecessary overhead, we pass through large allocation requests
> >> * directly to the page allocator. We use __GFP_COMP, because we will need to
> >>
> >> --
> >> 2.48.1
> >>
>
^ permalink raw reply [flat|nested] 20+ messages in thread
end of thread, other threads:[~2025-04-23 17:14 UTC | newest]
Thread overview: 20+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2025-03-17 14:33 [PATCH RFC v3 0/8] SLUB percpu sheaves Vlastimil Babka
2025-03-17 14:33 ` [PATCH RFC v3 1/8] locking/local_lock: Introduce localtry_lock_t Vlastimil Babka
2025-03-17 14:33 ` [PATCH RFC v3 2/8] slab: add opt-in caching layer of percpu sheaves Vlastimil Babka
2025-04-03 8:31 ` Harry Yoo
2025-04-03 14:11 ` Vlastimil Babka
2025-04-10 19:51 ` Suren Baghdasaryan
2025-04-22 15:02 ` Vlastimil Babka
2025-03-17 14:33 ` [PATCH RFC v3 3/8] slab: add sheaf support for batching kfree_rcu() operations Vlastimil Babka
2025-04-09 1:50 ` Harry Yoo
2025-04-09 15:09 ` Vlastimil Babka
2025-04-10 20:24 ` Suren Baghdasaryan
2025-04-22 15:18 ` Vlastimil Babka
2025-03-17 14:33 ` [PATCH RFC v3 4/8] slab: sheaf prefilling for guaranteed allocations Vlastimil Babka
2025-04-10 20:47 ` Suren Baghdasaryan
2025-04-23 13:06 ` Vlastimil Babka
2025-04-23 17:13 ` Suren Baghdasaryan
2025-03-17 14:33 ` [PATCH RFC v3 5/8] slab: determine barn status racily outside of lock Vlastimil Babka
2025-03-17 14:33 ` [PATCH RFC v3 6/8] tools: Add testing support for changes to rcu and slab for sheaves Vlastimil Babka
2025-03-17 14:33 ` [PATCH RFC v3 7/8] tools: Add sheafs support to testing infrastructure Vlastimil Babka
2025-03-17 14:33 ` [PATCH RFC v3 8/8] maple_tree: use percpu sheaves for maple_node_cache Vlastimil Babka
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox