Skip to contentSkip to conversation

mm/slub: reduce list_lock contention with slab parking

RFC PATCH Superseded Hao Li 4 participants 22 messages Aug 24 – Sep 17

Subsystems (2)

v1 of 2 Superseded Latest is v2 →

lore
Share & tools
lore

Hao Li

author reviewer
#0 lore raw

cover mm/slub: reduce list_lock contention with slab parking

This patch series might sound a bit wild, but the initial numbers don't look too bad so far. I would really appreciate any feedback and discussion :)

On a will-it-scale mmap1 run with 192 processes, list_lock is the top contention point: __slab_free() and __refill_objects_node() together spend 44% of cycles in native_queued_spin_lock_slowpath. The free slowpath takes the lock mainly to add slabs that became non-full to the partial list.

By adding extra instrumentation to __slab_free(), I collect the following data for the maple_node cache (in counts):

  partial->partial    843017414
  full->partial       550719384
  partial->empty      17459564
  full->empty         2

We can see that full -> partial transitions account for a significant proportion, and optimizing them can help reduce lock contention to some extent.

This series introduces the parking mechanism to address this issue. When the trylock fails during a full -> partial/empty transition, __slab_free() parks the slab on a per-node llist instead of waiting. The paths that consume the partial list (sheaf refill, alloc slowpath, shrink, cache destruction) unpark the slabs after taking the lock, and a delayed work covers the case where none of them runs.

Patch 1 cleans up the case handling in __slab_free(), no functional change. Patch 2 introduces the parking mechanism.

Tested with will-it-scale mmap1 (192 processes).

Summary data
------------

throughput             29237910 -> 35585663  (+21.7%)
alloc_slab,free_slab   -52%
cmpxchg_double_fail    -85%

perf data without this patchset:
- 44.22% [kernel] [k] native_queued_spin_lock_slowpath 43.48% native_queued_spin_lock_slowpath
- _raw_spin_lock_irqsave
- 23.80% __refill_objects_node
- 19.12% __slab_free

perf data with this patchset:
- 30.39% [kernel] [k] native_queued_spin_lock_slowpath 29.82% native_queued_spin_lock_slowpath
- _raw_spin_lock_irqsave
- 29.06% __refill_objects_node

Additionally, the number of partial slabs and the number of objects show no noticeable change before and after applying this patchset, indicating that this change has a negligible impact on slab fragmentation.

Detailed data
-------------

metric before after delta change
==========================================================================================
alloc_fastpath 155,417 168,534 13,117 +8.44%
alloc_slab 55,679,646 26,702,510 -28,977,136 -52.04%
alloc_slowpath 0 0 0 +0.00%

barn_get                             2,715             2,771                56      +2.06%
barn_get_fail                            2                 0                -2    -100.00%
barn_put                             2,715             2,770                55      +2.03%
barn_put_fail                1,370,488,457     1,668,257,974       297,769,517     +21.73%
cmpxchg_double_fail              3,827,935           549,427        -3,278,508     -85.65%
free_add_partial             1,684,340,964     2,161,921,625       477,580,661     +28.35%
free_fastpath                       31,766            32,979             1,213      +3.82%
free_rcu_sheaf              43,855,689,417    53,384,314,553     9,528,625,136     +21.73%
free_rcu_sheaf_fail                      0                 0                 0      +0.00%
free_remove_partial             55,678,459        26,685,274       -28,993,185     -52.07%
free_slab                       55,678,459        26,701,099       -28,977,360     -52.04%
free_slowpath                  107,771,739        63,197,344       -44,574,395     -41.36%
min_partial                              5                 5                 0      +0.00%
object_size                            256               256                 0      +0.00%
objects                             14,504            14,336              -168      -1.16%
objects_partial                     14,504            14,208              -296      -2.04%
objs_per_slab                           64                64                 0      +0.00%
park_slab                                -     2,147,963,530                 -      absent
partial                              1,398             1,367               -31      -2.22%
sheaf_alloc                    743,660,288     1,284,618,991       540,958,703     +72.74%
sheaf_capacity                          32                32                 0      +0.00%
sheaf_flush                 43,855,651,858    53,384,274,983     9,528,623,125     +21.73%
sheaf_free                     743,660,280     1,284,618,967       540,958,687     +72.74%
sheaf_prefill_fast          17,585,335,850    21,378,958,833     3,793,622,983     +21.57%
sheaf_prefill_oversize                   0                 0                 0      +0.00%
sheaf_prefill_slow                   2,060             2,051                -9      -0.44%
sheaf_refill                43,963,424,505    53,447,473,167     9,484,048,662     +21.57%
sheaf_return_fast           17,585,336,335    21,378,959,334     3,793,622,999     +21.57%
sheaf_return_slow                    1,402             1,277              -125      -8.92%
slabs                                1,398             1,369               -29      -2.07%
total_objects                       89,472            87,616            -1,856      -2.07%
unpark_event                             -       315,397,838                 -      absent
unpark_slab                              -     2,147,963,530                 -      absent

derived before after change
=============================================================================================

PARK_SLAB / FREE_ADD_PARTIAL                                  -            99.35%      absent
UNPARK_SLAB / UNPARK_EVENT                                    -              6.81      absent
PARK_SLAB - UNPARK_SLAB                                       -                 0      absent

page allocator churn (alloc_slab + free_slab) 111,358,105 53,403,609 -52.04%

Note that some metrics have very small absolute values (such as alloc_fastpath, partial, slabs, and total_objects) and are subject to noise. Across multiple test runs, their rate of change fluctuates between positive and negative, which supports the hypothesis that this is measurement noise and demonstrates that this patch has no noticeable impact on these metrics.

For metrics with large absolute values, their trends are distinct. The data indicates that the primary benefit of this approach is significantly relieved pressure on the buddy system, with page allocator churn reduced by 52%. Additionally, free_slowpath decreases by 41%, and cmpxchg_double_fail decreases by 85%.

The PARK_SLAB / FREE_ADD_PARTIAL ratio reaches 99.35%, which indicates that the vast majority of partial slabs are added back to the partial list via the parking mechanism, reflecting that the lock stayed saturated and nearly all additions avoided waiting for the lock. The ratio of UNPARK_SLAB / UNPARK_EVENT shows that each unpark event processes roughly 6 slabs. PARK_SLAB - UNPARK_SLAB being 0 confirms that no parked slabs are left stranded.

I also observe increases in both sheaf_alloc and sheaf_free, which could currently be attributed to faster allocation and free paths resulting from the overall performance improvement. However, I'm not sure about this, which is part of why this is posted as an RFC.

Based on slab/for-next.

Hao Li (2):
mm/slub: make the case handling in __slab_free() easier to follow mm/slub: introduce slab parking to reduce list_lock contention

 mm/slub.c | 326 +++++++++++++++++++++++++++++++++++++++++++++---------
 1 file changed, 274 insertions(+), 52 deletions(-)

base-commit: e7f630142df2afccce90555e4972e60008222311

Signature · 1 line
2.55.0
author reviewer
#1 lore raw

RFC PATCH 1/2 mm/slub: make the case handling in __slab_free() easier to follow

There are 7 possible transitions in __slab_free():

a. partial->partial
b. partial->empty, offlist
c. partial->empty, onlist, exceeding min_partial d. partial->empty, onlist, not exceeding min_partial e. full->empty, exceeding min_partial
f. full->empty, not exceeding min_partial g. full->partial

(There is no offlist variant of e, f and g as a full slab is on no list.)

Clarify which case each branch handles, and replace the goto with a return at the end of the skipped block so that every branch explicitly states its coverage.

Case 'a' is the only path that needs neither list_lock nor list handling. Give it an early continue: handling it upfront is much clearer than forcing every other case into a nested block.

Also, read SL_partial once after the loop right where it is used, rather than re-reading it on every iteration.

No functional change.

---
 mm/slub.c | 95 ++++++++++++++++++++++++++++---------------------------
 1 file changed, 49 insertions(+), 46 deletions(-)
mm/slub.c +49 -46
index b0cd0572e2f2..e20375307770 100644
@@ -5748,76 +5748,79 @@ static void __slab_free(struct kmem_cache *s, struct slab *slab,
 		new.inuse -= cnt;
 
 		/*
-		 * Might need to be taken off (due to becoming empty) or added
-		 * to (due to not being full anymore) the partial list.
-		 * Unless it's frozen.
+		 * partial->partial: the slab was on the node partial list and
+		 * stays there, so we need no list handling and no list_lock.
+		 *
+		 * Note that continue in a do-while goes on to evaluate the
+		 * condition below, so we do perform the freelist update.
 		 */
-		if (!new.inuse || was_full) {
-
-			n = get_node(s, slab_nid(slab));
-			/*
-			 * Speculatively acquire the list_lock.
-			 * If the cmpxchg does not succeed then we may
-			 * drop the list_lock without any processing.
-			 *
-			 * Otherwise the list_lock will synchronize with
-			 * other processors updating the list of slabs.
-			 */
-			spin_lock_irqsave(&n->list_lock, flags);
+		if (!was_full && new.inuse)
+			continue;
 
-			on_node_partial = slab_test_node_partial(slab);
-		}
+		/*
+		 * The slab might need to be taken off (due to becoming empty)
+		 * or added to (due to not being full anymore) the partial
+		 * list.
+		 *
+		 * Speculatively acquire list_lock before calling cmpxchg(), as
+		 * performing cmpxchg() prior to lock acquisition races with
+		 * concurrent paths, such as the shrinker.
+		 *
+		 * If the cmpxchg does not succeed then we will drop the
+		 * list_lock and retry.
+		 */
+		n = get_node(s, slab_nid(slab));
+		spin_lock_irqsave(&n->list_lock, flags);
 
 	} while (!slab_update_freelist(s, slab, &old, &new, "__slab_free"));
 
 	if (likely(!n)) {
+		/* partial->partial: we didn't take the list_lock */
+		return;
+	}
+
+	on_node_partial = slab_test_node_partial(slab);
+
+	if (!was_full && !on_node_partial) {
 		/*
-		 * We didn't take the list_lock because the slab was already on
-		 * the partial list and will remain there.
+		 * partial->empty, offlist: a bulk refill has taken the slab
+		 * off the partial list and will put it back, so its list
+		 * handling is not ours to do.
 		 */
+		spin_unlock_irqrestore(&n->list_lock, flags);
 		return;
 	}
 
-	/*
-	 * This slab was partially empty but not on the per-node partial list,
-	 * in which case we shouldn't manipulate its list, just return.
-	 */
-	if (!was_full && !on_node_partial) {
+	/* full/partial->empty, exceed: we have enough partial slabs already */
+	if (unlikely(!new.inuse && n->nr_partial >= s->min_partial)) {
+		/* partial->empty, onlist, exceed */
+		if (likely(!was_full)) {
+			remove_partial(n, slab);
+			stat(s, FREE_REMOVE_PARTIAL);
+		}
+		/* full->empty, exceed: it is on no list to remove from */
+
 		spin_unlock_irqrestore(&n->list_lock, flags);
+		stat(s, FREE_SLAB);
+		discard_slab(s, slab);
 		return;
 	}
 
 	/*
-	 * If slab became empty, should we add/keep it on the partial list or we
-	 * have enough?
+	 * At this point, only three cases remain:
+	 *   full->partial
+	 *   full->empty, not exceed
+	 *   partial->empty, onlist, not exceed
 	 */
-	if (unlikely(!new.inuse && n->nr_partial >= s->min_partial))
-		goto slab_empty;
 
-	/*
-	 * Objects left in the slab. If it was not on the partial list before
-	 * then add it.
-	 */
+	/* full->partial; full->empty, not exceed */
 	if (unlikely(was_full)) {
 		add_partial(n, slab, ADD_TO_TAIL);
 		stat(s, FREE_ADD_PARTIAL);
 	}
-	spin_unlock_irqrestore(&n->list_lock, flags);
-	return;
-
-slab_empty:
-	/*
-	 * The slab could have a single object and thus go from full to empty in
-	 * a single free, but more likely it was on the partial list. Remove it.
-	 */
-	if (likely(!was_full)) {
-		remove_partial(n, slab);
-		stat(s, FREE_REMOVE_PARTIAL);
-	}
+	/* partial->empty, onlist, not exceed: it stays where it is */
 
 	spin_unlock_irqrestore(&n->list_lock, flags);
-	stat(s, FREE_SLAB);
-	discard_slab(s, slab);
 }
 
 /*
Signature · 1 line
2.55.0
author reviewer
#2 lore raw

RFC PATCH 2/2 mm/slub: introduce slab parking to reduce list_lock contention

Introduce a mechanism called parking to mitigate lock contention in the free slowpath.

In the free slowpath, when __slab_free() transitions a full slab into a partial/empty slab through a free operation, it must acquire the list lock to add these newly freed partial/empty slabs to the partial list.

Why must partial and empty slabs converted from full slabs be added to the partial list? Because only by doing so can the sheaf refill or alloc slowpath see these partial slabs and allocate from them. Therefore, the list insertion must be performed, which requires acquiring the lock and leads to heavy lock contention under high concurrency.

Analysis of profiling data from the will-it-scale mmap1 benchmark shows that full -> partial transitions account for a large proportion, second only to partial -> partial.

With extra instrumentation added to __slab_free(), the following data was collected for the maple_node cache (in counts):

  partial->partial    843017414
  full->partial       550719384
  partial->empty      17459564
  full->empty         2

Since the fundamental purpose of __slab_free() is to make newly freed partial/empty slabs visible to the sheaf refill or alloc slowpath, these slabs can be temporarily stored in a staging area in a lockless manner instead of making the free slowpath contend for the lock. The sheaf refill or alloc slowpath then checks this staging area first when allocating objects. This achieves the goal of making these slabs visible to the sheaf refill or alloc slowpath while allowing the free slowpath to operate locklessly. This process is called "parking".

Parking occurs in only one case: when __slab_free() encounters a full -> partial/empty transition and the trylock fails. In this case, __slab_free() attaches the slab to an llist locklessly, instead of waiting for the lock unnecessarily.

Conversely, the process of moving these parked slabs from the llist back to the partial list is called "unpark". Unpark occurs in four cases:

1. Sheaf refill or alloc slowpath: This is the core case. The sheaf refill or alloc slowpath must see the parked slabs, so the first thing done after acquiring the lock in the sheaf refill or alloc slowpath is unpark.
2. Cache shrinking: shrinking also needs to see slabs in the parked state.
3. Cache destruction: kmem_cache_destroy() must also see parked slabs, which is obvious, otherwise memory would leak.
4. delayed_work (see corner case b below)

Why is this scheme correct? Because paths entering the sheaf refill or alloc slowpath can see both slabs on the partial list and slabs on the parked llist, while allocation paths that do not enter the sheaf refill or alloc slowpath would not check the partial list in the first place and naturally do not need to care about parked slabs. Therefore, whether an allocation takes the sheaf refill or the alloc slowpath or not, slabs on the parked llist and slabs on the partial list make no difference to the allocator. This visibility equivalence is the core of the scheme. This analysis also shows that the scheme does not affect the utilization of partial slabs or lead to increased fragmentation.

Corner cases to handle:
a. Parked slabs may become completely empty. Therefore, unpark must also
check min_partial and free excess empty slabs instead of adding them back to the partial list.

b. In rare cases, the system may go idle immediately after slabs are
parked, and the sheaf refill or alloc slowpath may never run again. These parked slabs would then remain in the llist until the next sheaf refill or alloc slowpath performs an unpark. To solve this problem, add a delayed_work named unpark_work to add parked slabs back to the partial list when no other path unparks them.

On will-it-scale mmap1 with 192 processes, throughput increases from 29237910 to 35585663 (+21.7%). native_queued_spin_lock_slowpath drops from 44% to 30% of cycles and __slab_free() disappears from the lock profile. alloc_slab,free_slab drop by 52%, and park_slab equals unpark_slab exactly, confirming no parked slabs are left stranded.

---
 mm/slub.c | 275 ++++++++++++++++++++++++++++++++++++++++++++++++------
 1 file changed, 247 insertions(+), 28 deletions(-)
mm/slub.c +247 -28
index e20375307770..27a78d63f537 100644
@@ -49,6 +49,7 @@
 #include <linux/sort.h>
 #include <linux/irq_work.h>
 #include <linux/kprobes.h>
+#include <linux/llist.h>
 #include <linux/debugfs.h>
 #include <trace/events/kmem.h>
 
@@ -122,6 +123,8 @@
  *   (Note that the total number of slabs is an atomic value that may be
  *   modified without taking the list lock).
  *
+ *   Slabs may be pushed to node->parked_slabs without acquiring list_lock.
+ *
  *   The list_lock is a centralized lock and thus we avoid taking it as
  *   much as possible. As long as SLUB does not have to handle partial
  *   slabs, operations can continue without any centralized lock.
@@ -368,6 +371,9 @@ enum stat_item {
 	FREE_SLOWPATH,		/* Free to a slab */
 	FREE_ADD_PARTIAL,	/* Freeing moves slab to partial list */
 	FREE_REMOVE_PARTIAL,	/* Freeing removes last object */
+	PARK_SLAB,		/* Slabs parked onto the llist by free slowpath */
+	UNPARK_SLAB,		/* Slabs unparked from the llist */
+	UNPARK_EVENT,		/* Unpark events */
 	ALLOC_SLAB,		/* New slab acquired from page allocator */
 	ALLOC_NODE_MISMATCH,	/* Requested node different from cpu sheaf */
 	FREE_SLAB,		/* Slab freed to the page allocator */
@@ -462,6 +468,14 @@ struct kmem_cache_node {
 	atomic_long_t total_objects;
 	struct list_head full;
 #endif
+	/*
+	 * If neither sheaf refill nor the alloc slowpath performs the unpark,
+	 * unpark_work_fn takes care of it.
+	 */
+	struct delayed_work unpark_work;
+
+	/* Used to link parked slabs */
+	struct llist_head parked_slabs ____cacheline_aligned_in_smp;
 };
 
 static inline struct kmem_cache_node *get_node(struct kmem_cache *s, int node)
@@ -509,6 +523,12 @@ static nodemask_t slab_barn_nodes;
  */
 static struct workqueue_struct *flushwq;
 
+/*
+ * Ceiling on how long slabs stay parked when no sheaf refill or alloc
+ * slowpath unparks them.
+ */
+#define UNPARK_DELAY	(HZ)
+
 struct slub_flush_work {
 	struct work_struct work;
 	struct kmem_cache *s;
@@ -3623,6 +3643,122 @@ static inline void remove_partial(struct kmem_cache_node *n,
 	clear_node_partial_state(n, slab);
 }
 
+/*
+ * A slab parked on n->parked_slabs is not on partial list, so its slab_list is
+ * free and we reuse it as the llist_node.
+ */
+static inline struct llist_node *slab_to_parked_llnode(struct slab *slab)
+{
+	return (struct llist_node *)&slab->slab_list;
+}
+
+static inline struct slab *parked_llnode_to_slab(struct llist_node *node)
+{
+	return container_of((struct list_head *)node, struct slab, slab_list);
+}
+
+/*
+ * Move slabs parked on n->parked_slabs to n->partial. Called with the
+ * list_lock held, by the paths that consume the partial list, on behalf of the
+ * cpus that could not get the lock when parking.
+ *
+ * If @discard is not NULL, put empty slabs beyond min_partial on @discard, the
+ * caller should call discard_slab() after dropping the lock.  Callers that may
+ * not free pages in their context should pass NULL.
+ */
+static void unpark_slabs(struct kmem_cache *s, struct kmem_cache_node *n,
+			 struct list_head *discard)
+{
+	struct llist_node *pos, *next;
+	unsigned long added = 0, discarded = 0;
+	unsigned long headroom = 0;
+	LIST_HEAD(to_add);
+
+	slab_lockdep_assert_held(&n->list_lock);
+
+	pos = llist_del_all(&n->parked_slabs);
+	if (likely(!pos))
+		return;
+
+	/*
+	 * Calculate how many more slabs the partial list wants before it has
+	 * reached min_partial.
+	 */
+	if (s->min_partial > n->nr_partial)
+		headroom = s->min_partial - n->nr_partial;
+
+	for (; pos; pos = next) {
+		struct slab *slab = parked_llnode_to_slab(pos);
+		struct freelist_counters flc;
+
+		/*
+		 * Back up the pointer, because the list_add_tail() below
+		 * overwrites the llist linkage.
+		 */
+		next = pos->next;
+
+		if (discard) {
+			flc.counters = data_race(READ_ONCE(slab->counters));
+			if (!flc.inuse && added >= headroom) {
+				list_add_tail(&slab->slab_list, discard);
+				discarded++;
+				continue;
+			}
+		}
+
+		slab_set_node_partial(slab);
+		list_add_tail(&slab->slab_list, &to_add);
+		added++;
+	}
+
+	n->nr_partial += added;
+	list_splice_tail(&to_add, &n->partial);
+
+	stat_add(s, FREE_ADD_PARTIAL, added);
+	stat_add(s, UNPARK_SLAB, added + discarded);
+	if (unlikely(discarded))
+		stat_add(s, FREE_SLAB, discarded);
+	stat(s, UNPARK_EVENT);
+}
+
+/*
+ * Parked slabs are normally unparked by sheaf refill or the alloc slowpath, but
+ * when the system experiences a heavy burst of frees, abruptly goes idle,
+ * and neither sheaf refill nor the alloc slowpath is reached,
+ * some parked slabs may be left stranded in the parked llist. This function
+ * serves as a last-resort fallback.
+ * This work is scheduled by the llist_add() that makes the parked llist non-empty.
+ */
+static void unpark_work_fn(struct work_struct *work)
+{
+	struct kmem_cache_node *n = container_of(to_delayed_work(work),
+						 struct kmem_cache_node,
+						 unpark_work);
+	struct llist_node *first;
+	struct kmem_cache *s;
+	struct slab *slab, *t;
+	unsigned long flags;
+	LIST_HEAD(discard);
+
+	if (likely(llist_empty(&n->parked_slabs)))
+		return;
+
+	spin_lock_irqsave(&n->list_lock, flags);
+
+	first = READ_ONCE(n->parked_slabs.first);
+	if (unlikely(!first)) {
+		spin_unlock_irqrestore(&n->list_lock, flags);
+		return;
+	}
+	s = parked_llnode_to_slab(first)->slab_cache;
+
+	unpark_slabs(s, n, &discard);
+	spin_unlock_irqrestore(&n->list_lock, flags);
+
+	list_for_each_entry_safe(slab, t, &discard, slab_list)
+		discard_slab(s, slab);
+}
+
 /*
  * Called only for kmem_cache_debug() caches instead of remove_partial(), with a
  * slab from the n->partial list. Remove only a single object from the slab, do
@@ -3818,9 +3954,13 @@ static bool get_partial_node_bulk(struct kmem_cache *s,
 	struct slab *first = NULL, *last = NULL;
 	unsigned int total_free = 0;
 	unsigned long flags;
+	LIST_HEAD(discard);
 
-	/* Racy check to avoid taking the lock unnecessarily. */
-	if (!n || data_race(!n->nr_partial))
+	/*
+	 * Racy check to avoid taking the lock unnecessarily.
+	 * The parked_slabs llist must also be accounted for.
+	 */
+	if (!n || (!data_race(n->nr_partial) && llist_empty(&n->parked_slabs)))
 		return false;
 
 	INIT_LIST_HEAD(&pc->slabs);
@@ -3830,6 +3970,9 @@ static bool get_partial_node_bulk(struct kmem_cache *s,
 	else if (!spin_trylock_irqsave(&n->list_lock, flags))
 		return false;
 
+	/* If there are parked slabs, move them to the partial list first. */
+	unpark_slabs(s, n, allow_spin ? &discard : NULL);
+
 	list_for_each_entry_safe(slab, slab2, &n->partial, slab_list) {
 		struct freelist_counters flc;
 		unsigned int slab_free;
@@ -3874,6 +4017,10 @@ static bool get_partial_node_bulk(struct kmem_cache *s,
 				    &last->slab_list);
 
 	spin_unlock_irqrestore(&n->list_lock, flags);
+
+	list_for_each_entry_safe(slab, slab2, &discard, slab_list)
+		discard_slab(s, slab);
+
 	return total_free > 0;
 }
 
@@ -3885,23 +4032,29 @@ static void *get_from_partial_node(struct kmem_cache *s,
 				   gfp_t gfp_flags,
 				   const struct slab_alloc_context *ac)
 {
+	bool allow_spin = alloc_flags_allow_spinning(ac->alloc_flags);
 	struct slab *slab, *slab2;
 	unsigned long flags;
 	void *object = NULL;
+	LIST_HEAD(discard);
 
 	/*
 	 * Racy check. If we mistakenly see no partial slabs then we
 	 * just allocate an empty slab. If we mistakenly try to get a
 	 * partial slab and there is none available then get_from_partial()
-	 * will return NULL.
+	 * will return NULL. Also take the parked_slabs llist into account.
 	 */
-	if (!n || !n->nr_partial)
+	if (!n || (!data_race(n->nr_partial) && llist_empty(&n->parked_slabs)))
 		return NULL;
 
-	if (alloc_flags_allow_spinning(ac->alloc_flags))
+	if (allow_spin)
 		spin_lock_irqsave(&n->list_lock, flags);
 	else if (!spin_trylock_irqsave(&n->list_lock, flags))
 		return NULL;
+
+	/* If there are parked slabs, move them to the partial list first. */
+	unpark_slabs(s, n, allow_spin ? &discard : NULL);
+
 	list_for_each_entry_safe(slab, slab2, &n->partial, slab_list) {
 
 		struct freelist_counters old, new;
@@ -3939,6 +4092,10 @@ static void *get_from_partial_node(struct kmem_cache *s,
 		break;
 	}
 	spin_unlock_irqrestore(&n->list_lock, flags);
+
+	list_for_each_entry_safe(slab, slab2, &discard, slab_list)
+		discard_slab(s, slab);
+
 	return object;
 }
 
@@ -3994,8 +4151,13 @@ static void *get_from_any_partial(struct kmem_cache *s, gfp_t gfp_flags,
 
 			n = get_node(s, zone_to_nid(zone));
 
+			/*
+			 * Parked slabs make the node worth visiting even if
+			 * nr_partial looks low.
+			 */
 			if (n && cpuset_zone_allowed(zone, gfp_flags) &&
-					n->nr_partial > s->min_partial) {
+					(n->nr_partial > s->min_partial ||
+					 !llist_empty(&n->parked_slabs))) {
 
 				void *object = get_from_partial_node(s, n,
 								gfp_flags, ac);
@@ -5719,7 +5881,7 @@ static void __slab_free(struct kmem_cache *s, struct slab *slab,
 			unsigned long addr)
 
 {
-	bool was_full;
+	bool was_full, park = false;
 	struct freelist_counters old, new;
 	struct kmem_cache_node *n = NULL;
 	unsigned long flags;
@@ -5731,10 +5893,11 @@ static void __slab_free(struct kmem_cache *s, struct slab *slab,
 	}
 
 	do {
-		if (unlikely(n)) {
+		if (unlikely(n && !park))
 			spin_unlock_irqrestore(&n->list_lock, flags);
-			n = NULL;
-		}
+
+		park = false;
+		n = NULL;
 
 		old.freelist = slab->freelist;
 		old.counters = slab->counters;
@@ -5749,9 +5912,10 @@ static void __slab_free(struct kmem_cache *s, struct slab *slab,
 
 		/*
 		 * partial->partial: the slab was on the node partial list and
-		 * stays there, so we need no list handling and no list_lock.
+		 * will still stay there, so we need no list handling and no
+		 * list_lock.
 		 *
-		 * Note that continue in a do-while goes on to evaluate the
+		 * Note that "continue;" in a do-while goes on to evaluate the
 		 * condition below, so we do perform the freelist update.
 		 */
 		if (!was_full && new.inuse)
@@ -5762,20 +5926,46 @@ static void __slab_free(struct kmem_cache *s, struct slab *slab,
 		 * or added to (due to not being full anymore) the partial
 		 * list.
 		 *
-		 * Speculatively acquire list_lock before calling cmpxchg(), as
-		 * performing cmpxchg() prior to lock acquisition races with
-		 * concurrent paths, such as the shrinker.
+		 * For the full -> partial/empty transition, use
+		 * spin_trylock_irqsave() and the parking mechanism to reduce
+		 * lock contention.
 		 *
-		 * If the cmpxchg does not succeed then we will drop the
-		 * list_lock and retry.
+		 * If the cmpxchg does not succeed then we will retry.
 		 */
 		n = get_node(s, slab_nid(slab));
-		spin_lock_irqsave(&n->list_lock, flags);
+
+		if (!was_full) {
+			/*
+			 * partial->empty: speculatively acquire list_lock
+			 * prior to cmpxchg(), as performing cmpxchg() before
+			 * lock acquisition races with concurrent operations
+			 * (e.g., the shrinker).
+			 */
+			spin_lock_irqsave(&n->list_lock, flags);
+		} else if (!spin_trylock_irqsave(&n->list_lock, flags)) {
+			/*
+			 * full->partial/empty: the slab is full, so it is on
+			 * no list; if the list_lock is contended, then we
+			 * park the slab without waiting for the lock.
+			 */
+			park = true;
+		}
 
 	} while (!slab_update_freelist(s, slab, &old, &new, "__slab_free"));
 
-	if (likely(!n)) {
-		/* partial->partial: we didn't take the list_lock */
+	/* partial->partial: we didn't take the list_lock. */
+	if (likely(!n))
+		return;
+
+	/*
+	 * Park the slab. If this park makes the parked llist non-empty,
+	 * then schedule unpark_work.
+	 */
+	if (unlikely(park)) {
+		if (llist_add(slab_to_parked_llnode(slab), &n->parked_slabs))
+			queue_delayed_work(flushwq, &n->unpark_work,
+					   UNPARK_DELAY);
+		stat(s, PARK_SLAB);
 		return;
 	}
 
@@ -5783,22 +5973,30 @@ static void __slab_free(struct kmem_cache *s, struct slab *slab,
 
 	if (!was_full && !on_node_partial) {
 		/*
-		 * partial->empty, offlist: a bulk refill has taken the slab
-		 * off the partial list and will put it back, so its list
-		 * handling is not ours to do.
+		 * partial->empty, offlist: the slab has been taken off the
+		 * partial list by a bulk refill, or parked during its full ->
+		 * partial/empty transition. It will be put back by other paths,
+		 * so this slab's list handling is not ours to do.
 		 */
 		spin_unlock_irqrestore(&n->list_lock, flags);
 		return;
 	}
 
-	/* full/partial->empty, exceed: we have enough partial slabs already */
-	if (unlikely(!new.inuse && n->nr_partial >= s->min_partial)) {
+	/*
+	 * full/partial->empty, exceed: we have enough partial slabs already.
+	 *
+	 * Parked slabs are also counted as partial slabs. We don't
+	 * keep an exact count of parked slabs, so we treat any parked
+	 * slab as roughly exceeding.
+	 */
+	if (unlikely(!new.inuse && (n->nr_partial >= s->min_partial ||
+				    !llist_empty(&n->parked_slabs)))) {
 		/* partial->empty, onlist, exceed */
 		if (likely(!was_full)) {
 			remove_partial(n, slab);
 			stat(s, FREE_REMOVE_PARTIAL);
 		}
-		/* full->empty, exceed: it is on no list to remove from */
+		/* else full->empty, exceed: it is on no list to remove from */
 
 		spin_unlock_irqrestore(&n->list_lock, flags);
 		stat(s, FREE_SLAB);
@@ -5818,7 +6016,7 @@ static void __slab_free(struct kmem_cache *s, struct slab *slab,
 		add_partial(n, slab, ADD_TO_TAIL);
 		stat(s, FREE_ADD_PARTIAL);
 	}
-	/* partial->empty, onlist, not exceed: it stays where it is */
+	/* else partial->empty, onlist, not exceed: it stays on partial list */
 
 	spin_unlock_irqrestore(&n->list_lock, flags);
 }
@@ -7360,8 +7558,13 @@ __refill_objects_any(struct kmem_cache *s, void **p, gfp_t gfp, unsigned int min
 
 			n = get_node(s, zone_to_nid(zone));
 
+			/*
+			 * Parked slabs make the node worth trying
+			 * even if nr_partial looks low.
+			 */
 			if (!n || !cpuset_zone_allowed(zone, gfp) ||
-					n->nr_partial <= s->min_partial)
+					(n->nr_partial <= s->min_partial &&
+					 llist_empty(&n->parked_slabs)))
 				continue;
 
 			r = __refill_objects_node(s, p, gfp, min, max, n,
@@ -7682,6 +7885,8 @@ init_kmem_cache_node(struct kmem_cache_node *n)
 	n->nr_partial = 0;
 	spin_lock_init(&n->list_lock);
 	INIT_LIST_HEAD(&n->partial);
+	init_llist_head(&n->parked_slabs);
+	INIT_DELAYED_WORK(&n->unpark_work, unpark_work_fn);
 #ifdef CONFIG_SLUB_DEBUG
 	atomic_long_set(&n->nr_slabs, 0);
 	atomic_long_set(&n->total_objects, 0);
@@ -7815,6 +8020,7 @@ static void free_kmem_cache_nodes(struct kmem_cache *s)
 	}
 
 	for_each_kmem_cache_node(s, node, n) {
+		cancel_delayed_work_sync(&n->unpark_work);
 		s->per_node[node].node = NULL;
 		kmem_cache_free(kmem_cache_node, n);
 	}
@@ -8115,6 +8321,10 @@ static void free_partial(struct kmem_cache *s, struct kmem_cache_node *n)
 
 	BUG_ON(irqs_disabled());
 	spin_lock_irq(&n->list_lock);
+
+	/* Unpark slabs so the walk can find them. */
+	unpark_slabs(s, n, NULL);
+
 	list_for_each_entry_safe(slab, h, &n->partial, slab_list) {
 		if (!slab->inuse) {
 			remove_partial(n, slab);
@@ -8386,6 +8596,9 @@ static int __kmem_cache_do_shrink(struct kmem_cache *s)
 
 		spin_lock_irqsave(&n->list_lock, flags);
 
+		/* Parked slabs are shrink candidates as well. */
+		unpark_slabs(s, n, NULL);
+
 		/*
 		 * Build lists of slabs to discard or promote.
 		 *
@@ -9525,6 +9738,9 @@ STAT_ATTR(FREE_FASTPATH, free_fastpath);
 STAT_ATTR(FREE_SLOWPATH, free_slowpath);
 STAT_ATTR(FREE_ADD_PARTIAL, free_add_partial);
 STAT_ATTR(FREE_REMOVE_PARTIAL, free_remove_partial);
+STAT_ATTR(PARK_SLAB, park_slab);
+STAT_ATTR(UNPARK_SLAB, unpark_slab);
+STAT_ATTR(UNPARK_EVENT, unpark_event);
 STAT_ATTR(ALLOC_SLAB, alloc_slab);
 STAT_ATTR(ALLOC_NODE_MISMATCH, alloc_node_mismatch);
 STAT_ATTR(FREE_SLAB, free_slab);
@@ -9613,6 +9829,9 @@ static const struct attribute *const slab_attrs[] = {
 	&free_slowpath_attr.attr,
 	&free_add_partial_attr.attr,
 	&free_remove_partial_attr.attr,
+	&park_slab_attr.attr,
+	&unpark_slab_attr.attr,
+	&unpark_event_attr.attr,
 	&alloc_slab_attr.attr,
 	&alloc_node_mismatch_attr.attr,
 	&free_slab_attr.attr,
Signature · 1 line
2.55.0
#16 lore raw
In reply to Hao Li
Quoted 3 lines · Hao Li

This patch series might sound a bit wild, but the initial numbers don't look too bad so far. I would really appreciate any feedback and discussion :)

The numbers look great, I have to say ;)

Quoted 6 lines

On a will-it-scale mmap1 run with 192 processes, list_lock is the top contention point: __slab_free() and __refill_objects_node() together spend 44% of cycles in native_queued_spin_lock_slowpath. The free slowpath takes the lock mainly to add slabs that became non-full to the partial list.

Doesn't this mean you're hitting the slow path way too many times? I think that's the actual issue, no?

Quoted 20 lines

By adding extra instrumentation to __slab_free(), I collect the following data for the maple_node cache (in counts):

  partial->partial    843017414
  full->partial       550719384
  partial->empty      17459564
  full->empty         2

We can see that full -> partial transitions account for a significant proportion, and optimizing them can help reduce lock contention to some extent.

This series introduces the parking mechanism to address this issue. When the trylock fails during a full -> partial/empty transition, __slab_free() parks the slab on a per-node llist instead of waiting. The paths that consume the partial list (sheaf refill, alloc slowpath, shrink, cache destruction) unpark the slabs after taking the lock, and a delayed work covers the case where none of them runs.

Quoted 2 lines

Patch 1 cleans up the case handling in __slab_free(), no functional change. Patch 2 introduces the parking mechanism.

This looks like fundamentally the wrong fix, when we want to find out why
1) you're hitting the alloc slowpath so hard
2) you're hitting the free slowpath so hard

and ideally find some way to tune it properly. Maybe if sheaf size is scaled up/down in some way (by default at least), according to amount of RAM or amount of CPUs.

Signature · 1 line
Pedro
author reviewer
#17 lore raw
Quoted 6 lines · Pedro Falcato
Quoted 3 lines · Hao Li

This patch series might sound a bit wild, but the initial numbers don't look too bad so far. I would really appreciate any feedback and discussion :)

The numbers look great, I have to say ;)

Thanks and sorry for the delayed reply!

Quoted 10 lines
Quoted 7 lines

On a will-it-scale mmap1 run with 192 processes, list_lock is the top contention point: __slab_free() and __refill_objects_node() together spend 44% of cycles in native_queued_spin_lock_slowpath. The free slowpath takes the lock mainly to add slabs that became non-full to the partial list.

Doesn't this mean you're hitting the slow path way too many times? I think that's the actual issue, no?

Partly, let me separate the two sides.

Quoted 21 lines
Quoted 21 lines

By adding extra instrumentation to __slab_free(), I collect the following data for the maple_node cache (in counts):

  partial->partial    843017414
  full->partial       550719384
  partial->empty      17459564
  full->empty         2

We can see that full -> partial transitions account for a significant proportion, and optimizing them can help reduce lock contention to some extent.

This series introduces the parking mechanism to address this issue. When the trylock fails during a full -> partial/empty transition, __slab_free() parks the slab on a per-node llist instead of waiting. The paths that consume the partial list (sheaf refill, alloc slowpath, shrink, cache destruction) unpark the slabs after taking the lock, and a delayed work covers the case where none of them runs.

Quoted 5 lines
Quoted 2 lines

Patch 1 cleans up the case handling in __slab_free(), no functional change. Patch 2 introduces the parking mechanism.

This looks like fundamentally the wrong fix, when we want to find out why
1) you're hitting the alloc slowpath so hard

Regarding the alloc side, it mostly goes through sheaf refilling, which isn't quite the actual slowpath in the usual sense. The full slowpath would be allocating a single object directly from the partial list, and from what we've observed in testing, that path is rarely ever hit.

Quoted 1 line

2) you're hitting the free slowpath so hard

Yes, the free side does indeed take the slowpath, which is precisely the problem this series aims to address.

Quoted 4 lines

and ideally find some way to tune it properly. Maybe if sheaf size is scaled up/down in some way (by default at least), according to amount of RAM or amount of CPUs.

I think the idea makes sense, though it might only offer partial relief. Since much of the overhead seems to come from free-side lock contention, a lockless approach could be a more fundamental fix.

Thanks for the discussion!

Signature · 2 lines
Thanks,
Hao
maintainer Reviewed-by on v1 1/2
#12 lore raw

Re: [RFC PATCH 1/2] mm/slub: make the case handling in __slab_free() easier to follow

In reply to Hao Li
Quoted 3 lines · Hao Li

There are 7 possible transitions in __slab_free():

a. partial->partial

maybe add "(offlist/onlist doesn't matter)"

Quoted 18 lines

b. partial->empty, offlist
c. partial->empty, onlist, exceeding min_partial d. partial->empty, onlist, not exceeding min_partial e. full->empty, exceeding min_partial
f. full->empty, not exceeding min_partial g. full->partial

(There is no offlist variant of e, f and g as a full slab is on no list.)

Clarify which case each branch handles, and replace the goto with a return at the end of the skipped block so that every branch explicitly states its coverage.

Case 'a' is the only path that needs neither list_lock nor list handling. Give it an early continue: handling it upfront is much clearer than forcing every other case into a nested block.

Quoted 6 lines

Also, read SL_partial once after the loop right where it is used, rather than re-reading it on every iteration.

No functional change.

Nit:

Quoted 9 lines
---
 mm/slub.c | 95 ++++++++++++++++++++++++++++---------------------------
 1 file changed, 49 insertions(+), 46 deletions(-)
mm/slub.c +0 -0
index b0cd0572e2f2..e20375307770 100644

mm/slub.c static void __slab_free(struct kmem_cache *s, struct slab *slab, · line 5752

Quoted 8 lines
mm/slub.c +2 -3
@@ -5748,76 +5748,79 @@ static void __slab_free(struct kmem_cache *s, struct slab *slab,
 		new.inuse -= cnt;
 
 		/*
-		 * Might need to be taken off (due to becoming empty) or added
-		 * to (due to not being full anymore) the partial list.
-		 * Unless it's frozen.
+		 * partial->partial: the slab was on the node partial list and
+		 * stays there, so we need no list handling and no list_lock.

I think more accurate is "if the slab was on the node partial list, it stays there, and if it was off, it stays off, so we need no..." ?

Quoted 117 lines
mm/slub.c +47 -43
+		 *
+		 * Note that continue in a do-while goes on to evaluate the
+		 * condition below, so we do perform the freelist update.
 		 */
-		if (!new.inuse || was_full) {
-
-			n = get_node(s, slab_nid(slab));
-			/*
-			 * Speculatively acquire the list_lock.
-			 * If the cmpxchg does not succeed then we may
-			 * drop the list_lock without any processing.
-			 *
-			 * Otherwise the list_lock will synchronize with
-			 * other processors updating the list of slabs.
-			 */
-			spin_lock_irqsave(&n->list_lock, flags);
+		if (!was_full && new.inuse)
+			continue;
 
-			on_node_partial = slab_test_node_partial(slab);
-		}
+		/*
+		 * The slab might need to be taken off (due to becoming empty)
+		 * or added to (due to not being full anymore) the partial
+		 * list.
+		 *
+		 * Speculatively acquire list_lock before calling cmpxchg(), as
+		 * performing cmpxchg() prior to lock acquisition races with
+		 * concurrent paths, such as the shrinker.
+		 *
+		 * If the cmpxchg does not succeed then we will drop the
+		 * list_lock and retry.
+		 */
+		n = get_node(s, slab_nid(slab));
+		spin_lock_irqsave(&n->list_lock, flags);
 
 	} while (!slab_update_freelist(s, slab, &old, &new, "__slab_free"));
 
 	if (likely(!n)) {
+		/* partial->partial: we didn't take the list_lock */
+		return;
+	}
+
+	on_node_partial = slab_test_node_partial(slab);
+
+	if (!was_full && !on_node_partial) {
 		/*
-		 * We didn't take the list_lock because the slab was already on
-		 * the partial list and will remain there.
+		 * partial->empty, offlist: a bulk refill has taken the slab
+		 * off the partial list and will put it back, so its list
+		 * handling is not ours to do.
 		 */
+		spin_unlock_irqrestore(&n->list_lock, flags);
 		return;
 	}
 
-	/*
-	 * This slab was partially empty but not on the per-node partial list,
-	 * in which case we shouldn't manipulate its list, just return.
-	 */
-	if (!was_full && !on_node_partial) {
+	/* full/partial->empty, exceed: we have enough partial slabs already */
+	if (unlikely(!new.inuse && n->nr_partial >= s->min_partial)) {
+		/* partial->empty, onlist, exceed */
+		if (likely(!was_full)) {
+			remove_partial(n, slab);
+			stat(s, FREE_REMOVE_PARTIAL);
+		}
+		/* full->empty, exceed: it is on no list to remove from */
+
 		spin_unlock_irqrestore(&n->list_lock, flags);
+		stat(s, FREE_SLAB);
+		discard_slab(s, slab);
 		return;
 	}
 
 	/*
-	 * If slab became empty, should we add/keep it on the partial list or we
-	 * have enough?
+	 * At this point, only three cases remain:
+	 *   full->partial
+	 *   full->empty, not exceed
+	 *   partial->empty, onlist, not exceed
 	 */
-	if (unlikely(!new.inuse && n->nr_partial >= s->min_partial))
-		goto slab_empty;
 
-	/*
-	 * Objects left in the slab. If it was not on the partial list before
-	 * then add it.
-	 */
+	/* full->partial; full->empty, not exceed */
 	if (unlikely(was_full)) {
 		add_partial(n, slab, ADD_TO_TAIL);
 		stat(s, FREE_ADD_PARTIAL);
 	}
-	spin_unlock_irqrestore(&n->list_lock, flags);
-	return;
-
-slab_empty:
-	/*
-	 * The slab could have a single object and thus go from full to empty in
-	 * a single free, but more likely it was on the partial list. Remove it.
-	 */
-	if (likely(!was_full)) {
-		remove_partial(n, slab);
-		stat(s, FREE_REMOVE_PARTIAL);
-	}
+	/* partial->empty, onlist, not exceed: it stays where it is */
 
 	spin_unlock_irqrestore(&n->list_lock, flags);
-	stat(s, FREE_SLAB);
-	discard_slab(s, slab);
 }
 
 /*
author reviewer
#13 lore raw

Re: [RFC PATCH 1/2] mm/slub: make the case handling in __slab_free() easier to follow

Quoted 6 lines · Vlastimil Babka (SUSE)
Quoted 3 lines · Hao Li

There are 7 possible transitions in __slab_free():

a. partial->partial

maybe add "(offlist/onlist doesn't matter)"

Exactly, this should be split into two subcases. will do.

Quoted 19 lines
Quoted 19 lines

b. partial->empty, offlist
c. partial->empty, onlist, exceeding min_partial d. partial->empty, onlist, not exceeding min_partial e. full->empty, exceeding min_partial
f. full->empty, not exceeding min_partial g. full->partial

(There is no offlist variant of e, f and g as a full slab is on no list.)

Clarify which case each branch handles, and replace the goto with a return at the end of the skipped block so that every branch explicitly states its coverage.

Case 'a' is the only path that needs neither list_lock nor list handling. Give it an early continue: handling it upfront is much clearer than forcing every other case into a nested block.

Quoted 8 lines
Quoted 6 lines

Also, read SL_partial once after the loop right where it is used, rather than re-reading it on every iteration.

No functional change.

Thanks!

Quoted 14 lines

Nit:

Quoted 11 lines
---
 mm/slub.c | 95 ++++++++++++++++++++++++++++---------------------------
 1 file changed, 49 insertions(+), 46 deletions(-)
mm/slub.c +0 -0
index b0cd0572e2f2..e20375307770 100644
@@ -5748,76 +5748,79 @@ static void __slab_free(struct kmem_cache *s, struct slab *slab,
 		new.inuse -= cnt;
 
Quoted 9 lines

mm/slub.c static void __slab_free(struct kmem_cache *s, struct slab *slab, · line 5752

Quoted 6 lines
mm/slub.c +2 -3
 		/*
-		 * Might need to be taken off (due to becoming empty) or added
-		 * to (due to not being full anymore) the partial list.
-		 * Unless it's frozen.
+		 * partial->partial: the slab was on the node partial list and
+		 * stays there, so we need no list handling and no list_lock.

I think more accurate is "if the slab was on the node partial list, it stays there, and if it was off, it stays off, so we need no..." ?

Yes, this is clearer, will do!

Quoted 119 lines
Quoted 118 lines
mm/slub.c +47 -43
+		 *
+		 * Note that continue in a do-while goes on to evaluate the
+		 * condition below, so we do perform the freelist update.
 		 */
-		if (!new.inuse || was_full) {
-
-			n = get_node(s, slab_nid(slab));
-			/*
-			 * Speculatively acquire the list_lock.
-			 * If the cmpxchg does not succeed then we may
-			 * drop the list_lock without any processing.
-			 *
-			 * Otherwise the list_lock will synchronize with
-			 * other processors updating the list of slabs.
-			 */
-			spin_lock_irqsave(&n->list_lock, flags);
+		if (!was_full && new.inuse)
+			continue;
 
-			on_node_partial = slab_test_node_partial(slab);
-		}
+		/*
+		 * The slab might need to be taken off (due to becoming empty)
+		 * or added to (due to not being full anymore) the partial
+		 * list.
+		 *
+		 * Speculatively acquire list_lock before calling cmpxchg(), as
+		 * performing cmpxchg() prior to lock acquisition races with
+		 * concurrent paths, such as the shrinker.
+		 *
+		 * If the cmpxchg does not succeed then we will drop the
+		 * list_lock and retry.
+		 */
+		n = get_node(s, slab_nid(slab));
+		spin_lock_irqsave(&n->list_lock, flags);
 
 	} while (!slab_update_freelist(s, slab, &old, &new, "__slab_free"));
 
 	if (likely(!n)) {
+		/* partial->partial: we didn't take the list_lock */
+		return;
+	}
+
+	on_node_partial = slab_test_node_partial(slab);
+
+	if (!was_full && !on_node_partial) {
 		/*
-		 * We didn't take the list_lock because the slab was already on
-		 * the partial list and will remain there.
+		 * partial->empty, offlist: a bulk refill has taken the slab
+		 * off the partial list and will put it back, so its list
+		 * handling is not ours to do.
 		 */
+		spin_unlock_irqrestore(&n->list_lock, flags);
 		return;
 	}
 
-	/*
-	 * This slab was partially empty but not on the per-node partial list,
-	 * in which case we shouldn't manipulate its list, just return.
-	 */
-	if (!was_full && !on_node_partial) {
+	/* full/partial->empty, exceed: we have enough partial slabs already */
+	if (unlikely(!new.inuse && n->nr_partial >= s->min_partial)) {
+		/* partial->empty, onlist, exceed */
+		if (likely(!was_full)) {
+			remove_partial(n, slab);
+			stat(s, FREE_REMOVE_PARTIAL);
+		}
+		/* full->empty, exceed: it is on no list to remove from */
+
 		spin_unlock_irqrestore(&n->list_lock, flags);
+		stat(s, FREE_SLAB);
+		discard_slab(s, slab);
 		return;
 	}
 
 	/*
-	 * If slab became empty, should we add/keep it on the partial list or we
-	 * have enough?
+	 * At this point, only three cases remain:
+	 *   full->partial
+	 *   full->empty, not exceed
+	 *   partial->empty, onlist, not exceed
 	 */
-	if (unlikely(!new.inuse && n->nr_partial >= s->min_partial))
-		goto slab_empty;
 
-	/*
-	 * Objects left in the slab. If it was not on the partial list before
-	 * then add it.
-	 */
+	/* full->partial; full->empty, not exceed */
 	if (unlikely(was_full)) {
 		add_partial(n, slab, ADD_TO_TAIL);
 		stat(s, FREE_ADD_PARTIAL);
 	}
-	spin_unlock_irqrestore(&n->list_lock, flags);
-	return;
-
-slab_empty:
-	/*
-	 * The slab could have a single object and thus go from full to empty in
-	 * a single free, but more likely it was on the partial list. Remove it.
-	 */
-	if (likely(!was_full)) {
-		remove_partial(n, slab);
-		stat(s, FREE_REMOVE_PARTIAL);
-	}
+	/* partial->empty, onlist, not exceed: it stays where it is */
 
 	spin_unlock_irqrestore(&n->list_lock, flags);
-	stat(s, FREE_SLAB);
-	discard_slab(s, slab);
 }
 
 /*
Signature · 2 lines
Thanks,
Hao
#3 lore raw

Re: [RFC PATCH 2/2] mm/slub: introduce slab parking to reduce list_lock contention

In reply to Hao Li
Quoted 2 lines · Hao Li

Introduce a mechanism called parking to mitigate lock contention in the free slowpath.

Interesting!

Quoted 14 lines

In the free slowpath, when __slab_free() transitions a full slab into a partial/empty slab through a free operation, it must acquire the list lock to add these newly freed partial/empty slabs to the partial list.

Why must partial and empty slabs converted from full slabs be added to the partial list? Because only by doing so can the sheaf refill or alloc slowpath see these partial slabs and allocate from them. Therefore, the list insertion must be performed, which requires acquiring the lock and leads to heavy lock contention under high concurrency.

Analysis of profiling data from the will-it-scale mmap1 benchmark shows that full -> partial transitions account for a large proportion, second only to partial -> partial.

Quoted 7 lines

With extra instrumentation added to __slab_free(), the following data was collected for the maple_node cache (in counts):

  partial->partial    843017414
  full->partial       550719384
  partial->empty      17459564
  full->empty         2

That's a lot inded. I'd be careful if it's some specific aspect of the test, i.e. lots of parallel allocations followed by lots of frees, that wouldn't be that common in realistic workloads. But worth looking into at least. If it's this kind of pathologic behavior, then I expect changing sheaf size as suggested by Pedro wouldn't help much.

Quoted 4 lines

Since the fundamental purpose of __slab_free() is to make newly freed partial/empty slabs visible to the sheaf refill or alloc slowpath, these slabs can be temporarily stored in a staging area in a lockless manner instead of making the free slowpath contend for the lock. The sheaf

However the lockless manipulation is still going to contend on the llist_head. But perhaps it's limited enough in both users and lenght of operations to make a difference.

Quoted 4 lines

refill or alloc slowpath then checks this staging area first when allocating objects. This achieves the goal of making these slabs visible to the sheaf refill or alloc slowpath while allowing the free slowpath to operate locklessly. This process is called "parking".

I'm gonna pull a David Hildenbrand trick here and question the name :) It seems to me it's an (extension of the) partial list, but lockless. Parking would suggest to me that it's put somewhere aside not to be used, or something.

Quoted 4 lines

Parking occurs in only one case: when __slab_free() encounters a full -> partial/empty transition and the trylock fails. In this case, __slab_free() attaches the slab to an llist locklessly, instead of waiting for the lock unnecessarily.

It could be interesting to also see if skipping the trylock completely (another cache contending operation) helps even more. Also whether moving the llist_node to a different cache line than list_lock (and fields protected by it) helps even more, or not.

Quoted 29 lines

Conversely, the process of moving these parked slabs from the llist back to the partial list is called "unpark". Unpark occurs in four cases:

1. Sheaf refill or alloc slowpath: This is the core case. The sheaf refill or alloc slowpath must see the parked slabs, so the first thing done after acquiring the lock in the sheaf refill or alloc slowpath is unpark.
2. Cache shrinking: shrinking also needs to see slabs in the parked state.
3. Cache destruction: kmem_cache_destroy() must also see parked slabs, which is obvious, otherwise memory would leak.
4. delayed_work (see corner case b below)

Why is this scheme correct? Because paths entering the sheaf refill or alloc slowpath can see both slabs on the partial list and slabs on the parked llist, while allocation paths that do not enter the sheaf refill or alloc slowpath would not check the partial list in the first place and naturally do not need to care about parked slabs. Therefore, whether an allocation takes the sheaf refill or the alloc slowpath or not, slabs on the parked llist and slabs on the partial list make no difference to the allocator. This visibility equivalence is the core of the scheme. This analysis also shows that the scheme does not affect the utilization of partial slabs or lead to increased fragmentation.

Corner cases to handle:
a. Parked slabs may become completely empty. Therefore, unpark must also
check min_partial and free excess empty slabs instead of adding them back to the partial list.

Quoted 7 lines

b. In rare cases, the system may go idle immediately after slabs are
parked, and the sheaf refill or alloc slowpath may never run again. These parked slabs would then remain in the llist until the next sheaf refill or alloc slowpath performs an unpark. To solve this problem, add a delayed_work named unpark_work to add parked slabs back to the partial list when no other path unparks them.

OK, but is this a problem that needs the delayed work? If the slabs are still partial, they would just sit on the partial list rather than on the llist, but it would cause no extra bloat?
It could be a problem only if free slab(s) got stuck on the llist.

So I'd try to avoid the delayed work as it's quite a red flag. Periodic flushing of alien arrays used to be a very unpopular part of SLAB implementation. I think there might be two ways:

1) submit the delayed work only when transitioning partial->empty slab on the llist. Would likely require flagging slabs that are on the llist. Hopefully this will limit the submissions to negligible amounts.

2) remove the delayed work completely, instead __slab_free() would perform the "unpark" immediately when detecting partial->empty slab transition on the llist. Would need flagging the slabs as well.

I guess 2) would be preferred unless it compromises the benefits too much.

Quoted 7 lines

On will-it-scale mmap1 with 192 processes, throughput increases from 29237910 to 35585663 (+21.7%). native_queued_spin_lock_slowpath drops from 44% to 30% of cycles and __slab_free() disappears from the lock profile. alloc_slab,free_slab drop by 52%, and park_slab equals unpark_slab exactly, confirming no parked slabs are left stranded.

#18 lore raw
In reply to Hao Li
Quoted 58 lines · Hao Li

This patch series might sound a bit wild, but the initial numbers don't look too bad so far. I would really appreciate any feedback and discussion :)

On a will-it-scale mmap1 run with 192 processes, list_lock is the top contention point: __slab_free() and __refill_objects_node() together spend 44% of cycles in native_queued_spin_lock_slowpath. The free slowpath takes the lock mainly to add slabs that became non-full to the partial list.

By adding extra instrumentation to __slab_free(), I collect the following data for the maple_node cache (in counts):

  partial->partial    843017414
  full->partial       550719384
  partial->empty      17459564
  full->empty         2

We can see that full -> partial transitions account for a significant proportion, and optimizing them can help reduce lock contention to some extent.

This series introduces the parking mechanism to address this issue. When the trylock fails during a full -> partial/empty transition, __slab_free() parks the slab on a per-node llist instead of waiting. The paths that consume the partial list (sheaf refill, alloc slowpath, shrink, cache destruction) unpark the slabs after taking the lock, and a delayed work covers the case where none of them runs.

Patch 1 cleans up the case handling in __slab_free(), no functional change. Patch 2 introduces the parking mechanism.

Tested with will-it-scale mmap1 (192 processes).

Summary data
------------

throughput             29237910 -> 35585663  (+21.7%)
alloc_slab,free_slab   -52%
cmpxchg_double_fail    -85%

perf data without this patchset:
- 44.22% [kernel] [k] native_queued_spin_lock_slowpath 43.48% native_queued_spin_lock_slowpath
- _raw_spin_lock_irqsave
- 23.80% __refill_objects_node
- 19.12% __slab_free

perf data with this patchset:
- 30.39% [kernel] [k] native_queued_spin_lock_slowpath 29.82% native_queued_spin_lock_slowpath
- _raw_spin_lock_irqsave
- 29.06% __refill_objects_node

Additionally, the number of partial slabs and the number of objects show no noticeable change before and after applying this patchset, indicating that this change has a negligible impact on slab fragmentation.

Quoted 7 lines

Detailed data
-------------

metric before after delta change
==========================================================================================
alloc_fastpath 155,417 168,534 13,117 +8.44%
alloc_slab 55,679,646 26,702,510 -28,977,136 -52.04%

It's interesting that this is reduced so much. Is it because parked slabs cause more slabs to stay around for reuse, despite they are unparked immediately when trying to allocate/refill? That seems odd?

Quoted 9 lines

alloc_slowpath 0 0 0 +0.00%

barn_get                             2,715             2,771                56      +2.06%
barn_get_fail                            2                 0                -2    -100.00%
barn_put                             2,715             2,770                55      +2.03%
barn_put_fail                1,370,488,457     1,668,257,974       297,769,517     +21.73%
cmpxchg_double_fail              3,827,935           549,427        -3,278,508     -85.65%
free_add_partial             1,684,340,964     2,161,921,625       477,580,661     +28.35%

free_fastpath 31,766 32,979 1,213 +3.82%
free_rcu_sheaf 43,855,689,417 53,384,314,553 9,528,625,136 +21.73%

This metric (and others with similar numbers) should not be affected by the change. Does it mean the benchmark has a fixed time to run, but manages to do more work in that time thanks to the increased throughput?

Quoted 69 lines

free_rcu_sheaf_fail 0 0 0 +0.00%

free_remove_partial             55,678,459        26,685,274       -28,993,185     -52.07%
free_slab                       55,678,459        26,701,099       -28,977,360     -52.04%
free_slowpath                  107,771,739        63,197,344       -44,574,395     -41.36%
min_partial                              5                 5                 0      +0.00%
object_size                            256               256                 0      +0.00%
objects                             14,504            14,336              -168      -1.16%
objects_partial                     14,504            14,208              -296      -2.04%
objs_per_slab                           64                64                 0      +0.00%
park_slab                                -     2,147,963,530                 -      absent
partial                              1,398             1,367               -31      -2.22%
sheaf_alloc                    743,660,288     1,284,618,991       540,958,703     +72.74%
sheaf_capacity                          32                32                 0      +0.00%
sheaf_flush                 43,855,651,858    53,384,274,983     9,528,623,125     +21.73%
sheaf_free                     743,660,280     1,284,618,967       540,958,687     +72.74%
sheaf_prefill_fast          17,585,335,850    21,378,958,833     3,793,622,983     +21.57%
sheaf_prefill_oversize                   0                 0                 0      +0.00%
sheaf_prefill_slow                   2,060             2,051                -9      -0.44%
sheaf_refill                43,963,424,505    53,447,473,167     9,484,048,662     +21.57%
sheaf_return_fast           17,585,336,335    21,378,959,334     3,793,622,999     +21.57%
sheaf_return_slow                    1,402             1,277              -125      -8.92%
slabs                                1,398             1,369               -29      -2.07%
total_objects                       89,472            87,616            -1,856      -2.07%
unpark_event                             -       315,397,838                 -      absent
unpark_slab                              -     2,147,963,530                 -      absent

derived before after change
=============================================================================================

PARK_SLAB / FREE_ADD_PARTIAL                                  -            99.35%      absent
UNPARK_SLAB / UNPARK_EVENT                                    -              6.81      absent
PARK_SLAB - UNPARK_SLAB                                       -                 0      absent

page allocator churn (alloc_slab + free_slab) 111,358,105 53,403,609 -52.04%

Note that some metrics have very small absolute values (such as alloc_fastpath, partial, slabs, and total_objects) and are subject to noise. Across multiple test runs, their rate of change fluctuates between positive and negative, which supports the hypothesis that this is measurement noise and demonstrates that this patch has no noticeable impact on these metrics.

For metrics with large absolute values, their trends are distinct. The data indicates that the primary benefit of this approach is significantly relieved pressure on the buddy system, with page allocator churn reduced by 52%. Additionally, free_slowpath decreases by 41%, and cmpxchg_double_fail decreases by 85%.

The PARK_SLAB / FREE_ADD_PARTIAL ratio reaches 99.35%, which indicates that the vast majority of partial slabs are added back to the partial list via the parking mechanism, reflecting that the lock stayed saturated and nearly all additions avoided waiting for the lock. The ratio of UNPARK_SLAB / UNPARK_EVENT shows that each unpark event processes roughly 6 slabs. PARK_SLAB - UNPARK_SLAB being 0 confirms that no parked slabs are left stranded.

I also observe increases in both sheaf_alloc and sheaf_free, which could currently be attributed to faster allocation and free paths resulting from the overall performance improvement. However, I'm not sure about this, which is part of why this is posted as an RFC.

Based on slab/for-next.

Hao Li (2):
mm/slub: make the case handling in __slab_free() easier to follow mm/slub: introduce slab parking to reduce list_lock contention

 mm/slub.c | 326 +++++++++++++++++++++++++++++++++++++++++++++---------
 1 file changed, 274 insertions(+), 52 deletions(-)

base-commit: e7f630142df2afccce90555e4972e60008222311

#4 lore raw

Re: [RFC PATCH 2/2] mm/slub: introduce slab parking to reduce list_lock contention

In reply to Vlastimil Babka (SUSE)
Quoted 28 lines · Vlastimil Babka (SUSE)
Quoted 2 lines · Hao Li

Introduce a mechanism called parking to mitigate lock contention in the free slowpath.

Interesting!

Quoted 14 lines

In the free slowpath, when __slab_free() transitions a full slab into a partial/empty slab through a free operation, it must acquire the list lock to add these newly freed partial/empty slabs to the partial list.

Why must partial and empty slabs converted from full slabs be added to the partial list? Because only by doing so can the sheaf refill or alloc slowpath see these partial slabs and allocate from them. Therefore, the list insertion must be performed, which requires acquiring the lock and leads to heavy lock contention under high concurrency.

Analysis of profiling data from the will-it-scale mmap1 benchmark shows that full -> partial transitions account for a large proportion, second only to partial -> partial.

Quoted 7 lines

With extra instrumentation added to __slab_free(), the following data was collected for the maple_node cache (in counts):

  partial->partial    843017414
  full->partial       550719384
  partial->empty      17459564
  full->empty         2
Quoted 5 lines

That's a lot inded. I'd be careful if it's some specific aspect of the test, i.e. lots of parallel allocations followed by lots of frees, that wouldn't be that common in realistic workloads. But worth looking into at least. If it's this kind of pathologic behavior, then I expect changing sheaf size as suggested by Pedro wouldn't help much.

mmap1[1] is a very simple test. It just mmaps and munmaps. I assume what we're observing here is the churn in maple tree nodes as we allocate/free/split/etc.

I suspect it's also possible that bulk RCU freeing is causing this. It might
1) be substantially delayed and 2) dumping a lot of freed maple tree node objects that overflow the pcs.

[1] https://github.com/heatd/will-it-scale/blob/master/tests/mmap1.c

Quoted 76 lines
Quoted 5 lines

Since the fundamental purpose of __slab_free() is to make newly freed partial/empty slabs visible to the sheaf refill or alloc slowpath, these slabs can be temporarily stored in a staging area in a lockless manner instead of making the free slowpath contend for the lock. The sheaf

However the lockless manipulation is still going to contend on the llist_head. But perhaps it's limited enough in both users and lenght of operations to make a difference.

Quoted 4 lines

refill or alloc slowpath then checks this staging area first when allocating objects. This achieves the goal of making these slabs visible to the sheaf refill or alloc slowpath while allowing the free slowpath to operate locklessly. This process is called "parking".

I'm gonna pull a David Hildenbrand trick here and question the name :) It seems to me it's an (extension of the) partial list, but lockless. Parking would suggest to me that it's put somewhere aside not to be used, or something.

Quoted 4 lines

Parking occurs in only one case: when __slab_free() encounters a full -> partial/empty transition and the trylock fails. In this case, __slab_free() attaches the slab to an llist locklessly, instead of waiting for the lock unnecessarily.

It could be interesting to also see if skipping the trylock completely (another cache contending operation) helps even more. Also whether moving the llist_node to a different cache line than list_lock (and fields protected by it) helps even more, or not.

Quoted 29 lines

Conversely, the process of moving these parked slabs from the llist back to the partial list is called "unpark". Unpark occurs in four cases:

1. Sheaf refill or alloc slowpath: This is the core case. The sheaf refill or alloc slowpath must see the parked slabs, so the first thing done after acquiring the lock in the sheaf refill or alloc slowpath is unpark.
2. Cache shrinking: shrinking also needs to see slabs in the parked state.
3. Cache destruction: kmem_cache_destroy() must also see parked slabs, which is obvious, otherwise memory would leak.
4. delayed_work (see corner case b below)

Why is this scheme correct? Because paths entering the sheaf refill or alloc slowpath can see both slabs on the partial list and slabs on the parked llist, while allocation paths that do not enter the sheaf refill or alloc slowpath would not check the partial list in the first place and naturally do not need to care about parked slabs. Therefore, whether an allocation takes the sheaf refill or the alloc slowpath or not, slabs on the parked llist and slabs on the partial list make no difference to the allocator. This visibility equivalence is the core of the scheme. This analysis also shows that the scheme does not affect the utilization of partial slabs or lead to increased fragmentation.

Corner cases to handle:
a. Parked slabs may become completely empty. Therefore, unpark must also
check min_partial and free excess empty slabs instead of adding them back to the partial list.

Quoted 7 lines

b. In rare cases, the system may go idle immediately after slabs are
parked, and the sheaf refill or alloc slowpath may never run again. These parked slabs would then remain in the llist until the next sheaf refill or alloc slowpath performs an unpark. To solve this problem, add a delayed_work named unpark_work to add parked slabs back to the partial list when no other path unparks them.

OK, but is this a problem that needs the delayed work? If the slabs are still partial, they would just sit on the partial list rather than on the llist, but it would cause no extra bloat?
It could be a problem only if free slab(s) got stuck on the llist.

So I'd try to avoid the delayed work as it's quite a red flag. Periodic flushing of alien arrays used to be a very unpopular part of SLAB implementation. I think there might be two ways:

Quoted 7 lines

1) submit the delayed work only when transitioning partial->empty slab on the llist. Would likely require flagging slabs that are on the llist. Hopefully this will limit the submissions to negligible amounts.

2) remove the delayed work completely, instead __slab_free() would perform the "unpark" immediately when detecting partial->empty slab transition on the llist. Would need flagging the slabs as well.

3) Don't do any of this and keep a small(ish?) barn locally, for each CPU (welcome back per-CPU partial slabs!). I'll play around with this idea and see if I can get interesting results...

I also have other vague, handwavy ideas... Hmm...

But I really, really suspect that deferring work and playing around with trylocks is really just working around allocator deficiencies.

Signature · 1 line
Pedro
author reviewer
#19 lore raw
In reply to Vlastimil Babka (SUSE)
Quoted 62 lines · Vlastimil Babka (SUSE)
Quoted 61 lines · Hao Li

This patch series might sound a bit wild, but the initial numbers don't look too bad so far. I would really appreciate any feedback and discussion :)

On a will-it-scale mmap1 run with 192 processes, list_lock is the top contention point: __slab_free() and __refill_objects_node() together spend 44% of cycles in native_queued_spin_lock_slowpath. The free slowpath takes the lock mainly to add slabs that became non-full to the partial list.

By adding extra instrumentation to __slab_free(), I collect the following data for the maple_node cache (in counts):

  partial->partial    843017414
  full->partial       550719384
  partial->empty      17459564
  full->empty         2

We can see that full -> partial transitions account for a significant proportion, and optimizing them can help reduce lock contention to some extent.

This series introduces the parking mechanism to address this issue. When the trylock fails during a full -> partial/empty transition, __slab_free() parks the slab on a per-node llist instead of waiting. The paths that consume the partial list (sheaf refill, alloc slowpath, shrink, cache destruction) unpark the slabs after taking the lock, and a delayed work covers the case where none of them runs.

Patch 1 cleans up the case handling in __slab_free(), no functional change. Patch 2 introduces the parking mechanism.

Tested with will-it-scale mmap1 (192 processes).

Summary data
------------

throughput             29237910 -> 35585663  (+21.7%)
alloc_slab,free_slab   -52%
cmpxchg_double_fail    -85%

perf data without this patchset:
- 44.22% [kernel] [k] native_queued_spin_lock_slowpath 43.48% native_queued_spin_lock_slowpath
- _raw_spin_lock_irqsave
- 23.80% __refill_objects_node
- 19.12% __slab_free

perf data with this patchset:
- 30.39% [kernel] [k] native_queued_spin_lock_slowpath 29.82% native_queued_spin_lock_slowpath
- _raw_spin_lock_irqsave
- 29.06% __refill_objects_node

Additionally, the number of partial slabs and the number of objects show no noticeable change before and after applying this patchset, indicating that this change has a negligible impact on slab fragmentation.

Detailed data
-------------

Quoted 8 lines
Quoted 4 lines

metric before after delta change
==========================================================================================
alloc_fastpath 155,417 168,534 13,117 +8.44%
alloc_slab 55,679,646 26,702,510 -28,977,136 -52.04%

It's interesting that this is reduced so much. Is it because parked slabs cause more slabs to stay around for reuse, despite they are unparked immediately when trying to allocate/refill? That seems odd?

Yeah, it does look counter-intuitive at first glance. My understanding is that the parking mechanism helps by bypassing the partial list spinlock, allowing partial slabs to be parked onto the llist locklessly at any point. Because of this, the refill path gets to see and reuse more partial slabs instead of having to allocate fresh ones so frequently.

Quoted 11 lines
Quoted 10 lines

alloc_slowpath 0 0 0 +0.00%

barn_get                             2,715             2,771                56      +2.06%
barn_get_fail                            2                 0                -2    -100.00%
barn_put                             2,715             2,770                55      +2.03%
barn_put_fail                1,370,488,457     1,668,257,974       297,769,517     +21.73%
cmpxchg_double_fail              3,827,935           549,427        -3,278,508     -85.65%
free_add_partial             1,684,340,964     2,161,921,625       477,580,661     +28.35%

free_fastpath 31,766 32,979 1,213 +3.82%
free_rcu_sheaf 43,855,689,417 53,384,314,553 9,528,625,136 +21.73%

Quoted 3 lines

This metric (and others with similar numbers) should not be affected by the change. Does it mean the benchmark has a fixed time to run, but manages to do more work in that time thanks to the increased throughput?

Exactly! In fact, the increase in free_rcu_sheaf matches the throughput gain almost 1:1. A ~21% increase in throughput naturally translates to ~21% more object allocations and frees.

Quoted 71 lines
Quoted 70 lines

free_rcu_sheaf_fail 0 0 0 +0.00%

free_remove_partial             55,678,459        26,685,274       -28,993,185     -52.07%
free_slab                       55,678,459        26,701,099       -28,977,360     -52.04%
free_slowpath                  107,771,739        63,197,344       -44,574,395     -41.36%
min_partial                              5                 5                 0      +0.00%
object_size                            256               256                 0      +0.00%
objects                             14,504            14,336              -168      -1.16%
objects_partial                     14,504            14,208              -296      -2.04%
objs_per_slab                           64                64                 0      +0.00%
park_slab                                -     2,147,963,530                 -      absent
partial                              1,398             1,367               -31      -2.22%
sheaf_alloc                    743,660,288     1,284,618,991       540,958,703     +72.74%
sheaf_capacity                          32                32                 0      +0.00%
sheaf_flush                 43,855,651,858    53,384,274,983     9,528,623,125     +21.73%
sheaf_free                     743,660,280     1,284,618,967       540,958,687     +72.74%
sheaf_prefill_fast          17,585,335,850    21,378,958,833     3,793,622,983     +21.57%
sheaf_prefill_oversize                   0                 0                 0      +0.00%
sheaf_prefill_slow                   2,060             2,051                -9      -0.44%
sheaf_refill                43,963,424,505    53,447,473,167     9,484,048,662     +21.57%
sheaf_return_fast           17,585,336,335    21,378,959,334     3,793,622,999     +21.57%
sheaf_return_slow                    1,402             1,277              -125      -8.92%
slabs                                1,398             1,369               -29      -2.07%
total_objects                       89,472            87,616            -1,856      -2.07%
unpark_event                             -       315,397,838                 -      absent
unpark_slab                              -     2,147,963,530                 -      absent

derived before after change
=============================================================================================

PARK_SLAB / FREE_ADD_PARTIAL                                  -            99.35%      absent
UNPARK_SLAB / UNPARK_EVENT                                    -              6.81      absent
PARK_SLAB - UNPARK_SLAB                                       -                 0      absent

page allocator churn (alloc_slab + free_slab) 111,358,105 53,403,609 -52.04%

Note that some metrics have very small absolute values (such as alloc_fastpath, partial, slabs, and total_objects) and are subject to noise. Across multiple test runs, their rate of change fluctuates between positive and negative, which supports the hypothesis that this is measurement noise and demonstrates that this patch has no noticeable impact on these metrics.

For metrics with large absolute values, their trends are distinct. The data indicates that the primary benefit of this approach is significantly relieved pressure on the buddy system, with page allocator churn reduced by 52%. Additionally, free_slowpath decreases by 41%, and cmpxchg_double_fail decreases by 85%.

The PARK_SLAB / FREE_ADD_PARTIAL ratio reaches 99.35%, which indicates that the vast majority of partial slabs are added back to the partial list via the parking mechanism, reflecting that the lock stayed saturated and nearly all additions avoided waiting for the lock. The ratio of UNPARK_SLAB / UNPARK_EVENT shows that each unpark event processes roughly 6 slabs. PARK_SLAB - UNPARK_SLAB being 0 confirms that no parked slabs are left stranded.

I also observe increases in both sheaf_alloc and sheaf_free, which could currently be attributed to faster allocation and free paths resulting from the overall performance improvement. However, I'm not sure about this, which is part of why this is posted as an RFC.

Based on slab/for-next.

Hao Li (2):
mm/slub: make the case handling in __slab_free() easier to follow mm/slub: introduce slab parking to reduce list_lock contention

 mm/slub.c | 326 +++++++++++++++++++++++++++++++++++++++++++++---------
 1 file changed, 274 insertions(+), 52 deletions(-)

base-commit: e7f630142df2afccce90555e4972e60008222311

Signature · 2 lines
Thanks,
Hao
author reviewer
#5 lore raw

Re: [RFC PATCH 2/2] mm/slub: introduce slab parking to reduce list_lock contention

In reply to Vlastimil Babka (SUSE)
Quoted 5 lines · Vlastimil Babka (SUSE)
Quoted 2 lines · Hao Li

Introduce a mechanism called parking to mitigate lock contention in the free slowpath.

Interesting!

Thanks!

Quoted 23 lines
Quoted 15 lines

In the free slowpath, when __slab_free() transitions a full slab into a partial/empty slab through a free operation, it must acquire the list lock to add these newly freed partial/empty slabs to the partial list.

Why must partial and empty slabs converted from full slabs be added to the partial list? Because only by doing so can the sheaf refill or alloc slowpath see these partial slabs and allocate from them. Therefore, the list insertion must be performed, which requires acquiring the lock and leads to heavy lock contention under high concurrency.

Analysis of profiling data from the will-it-scale mmap1 benchmark shows that full -> partial transitions account for a large proportion, second only to partial -> partial.

Quoted 7 lines

With extra instrumentation added to __slab_free(), the following data was collected for the maple_node cache (in counts):

  partial->partial    843017414
  full->partial       550719384
  partial->empty      17459564
  full->empty         2
Quoted 5 lines

That's a lot inded. I'd be careful if it's some specific aspect of the test, i.e. lots of parallel allocations followed by lots of frees, that wouldn't be that common in realistic workloads. But worth looking into at least. If it's this kind of pathologic behavior, then I expect changing sheaf size as suggested by Pedro wouldn't help much.

Thanks for pointing this out. I looked into this bursty alloc-and-free behavior a bit deeper and ran some further experiments.

The core question we want to answer is: why does such a massive volume of object allocations and frees fall straight through to the node partial list layer, rather than being caught and handled at the barn/sheaf layer? In SLUB's current design, the per-CPU main/spare sheaves act as the L1 cache, the barn as L2, and the node partial list as L3. For the mmap1 benchmark (which heavily stresses the maple tree), the allocation path uses kmem_cache_prefill_sheaf() rather than the generic allocation APIs, and the frees go through kfree_rcu().

Then, here is what happens during allocation: kmem_cache_prefill_sheaf() normally borrows the spare sheaf directly. If the sheaf holds fewer objects than requested, it refills it to capacity from the node partial list layer and this completely bypasses the barn layer. Once the maple tree finishes allocating a batch of objects, it returns the sheaf back to pcs->spare via kmem_cache_return_sheaf(). So in essence, this prefill path is just funneling objects directly from the node partial list into the maple tree through the spare sheaf. It skips the barn layer.

Then on the free side: these objects are freed via kfree_rcu, and then rcu_free_sheaf() checks if there is still room on the barn's full list. But since the allocation path never actually pulled from the barn, the full list stays permanently saturated. As a result, rcu_free_sheaf() always falls back to sheaf_flush_unused(), flushing objects straight into the node partial list layer. It skips the barn layer too.

So looking at this behavior, the benchmark does seem to reveal a gap in this allocation path, where a huge amount of traffic ends up bypassing the barn layer entirely.

To see if we can address this, I draft an experimental patch. It introduces a new field, barn->sheaf_partial, which is a single sheaf rather than a list.

[The patch code is included at the end of this email.]

Whenever kmem_cache_prefill_sheaf() runs, it detaches pcs->spare and checks whether it holds enough objects for the request.

If so, it returns it right away as in the original code.

If not, call __prefill_sheaf_pfmemalloc() and then go into barn_replace_partial_sheaf() to swap the non-full spare sheaf with a full sheaf from the barn. The full sheaf is handed to the caller, while the non-full sheaf is temporarily stashed into barn->sheaf_partial. This largely avoids falling back to the node partial list. If barn->sheaf_partial already has a sheaf, we merge them together, and any resulting full or empty sheaves are placed back into the barn accordingly.

The key idea here is simply to let __prefill_sheaf_pfmemalloc() pull a sheaf from the barn's full list, which makes room on the list for future rcu_free_sheaf() calls.

Here are the numbers with just this experimental patch applied (without the parking patch):

baseline: 28779879
after experimental patch: 35550211 (+23.5%)

metric before after delta change
=============================================================================================

aliases                                  0                 0                 0      +0.00%
align                                  256               256                 0      +0.00%

alloc_fastpath 23,259 59,287 36,028 +154.90%
alloc_node_mismatch 0 0 0 +0.00%
alloc_slab 10,171,378 4,796,346 -5,375,032 -52.84%
alloc_slowpath 0 0 0 +0.00%
barn_get 441 193,807,528 193,807,087 +43947185.26%
barn_get_fail 0 377 377 new
barn_put 441 181,694,607 181,694,166 +41200491.16%
barn_put_fail 272,868,220 156,335,632 -116,532,588 -42.71%
cache_dma 0 0 0 +0.00%
cmpxchg_double_fail 744,975 357,255 -387,720 -52.04%

cpu_partial                              0                 0                 0      +0.00%
cpu_slabs                                0                 0                 0      +0.00%
destroy_by_rcu                           0                 0                 0      +0.00%

free_add_partial 337,390,126 162,178,648 -175,211,478 -51.93%
free_fastpath 5,204 14,081 8,877 +170.58%
free_rcu_sheaf 8,731,794,372 10,816,953,777 2,085,159,405 +23.88%
free_rcu_sheaf_fail 0 0 0 +0.00%

free_remove_partial             10,170,229         4,794,785        -5,375,444     -52.85%
free_slab                       10,170,229         4,794,785        -5,375,444     -52.85%
free_slowpath                   18,697,056        11,563,127        -7,133,929     -38.16%
hwcache_align                            0                 0                 0      +0.00%
min_partial                              5                 5                 0      +0.00%
object_size                            256               256                 0      +0.00%
objects                             14,774            14,596              -178      -1.20%
objects_partial                     14,774            14,596              -178      -1.20%
objs_per_slab                           64                64                 0      +0.00%
order                                    2                 2                 0      +0.00%
order_fallback                           0                 0                 0      +0.00%
partial                              1,913             2,544               631     +32.98%
poison                                   0                 0                 0      +0.00%
reclaim_account                          0                 0                 0      +0.00%
red_zone                                 0                 0                 0      +0.00%
remote_node_defrag_ratio               100               100                 0      +0.00%
sanity_checks                            0                 0                 0      +0.00%
sheaf_alloc                    145,870,437       151,536,660         5,666,223      +3.88%
sheaf_capacity                          32                32                 0      +0.00%

sheaf_flush 8,731,787,311 5,002,740,743 -3,729,046,568 -42.71%
sheaf_free 145,870,431 151,536,655 5,666,224 +3.88%
sheaf_prefill_fast 3,500,187,266 4,331,383,393 831,196,127 +23.75%
sheaf_prefill_oversize 0 0 0 +0.00%
sheaf_prefill_slow 322 646 324 +100.62%

sheaf_refill                 8,750,484,664     5,014,304,944    -3,736,179,720     -42.70%
sheaf_return_fast            3,500,187,348     4,331,383,596       831,196,248     +23.75%
sheaf_return_slow                      240               443               203     +84.58%
slab_size                              256               256                 0      +0.00%
slabs                                1,913             2,544               631     +32.98%
slabs_cpu_partial                        0                 0                 0      +0.00%
store_user                               0                 0                 0      +0.00%
total_objects                      122,432           162,816            40,384     +32.98%
trace                                    0                 0                 0      +0.00%
usersize                                 0                 0                 0      +0.00%

derived before after change
=============================================================================================
page allocator churn (alloc_slab + free_slab) 20,341,607 9,591,131 -52.85%

As we can see from the data, barn_get and barn_put spike significantly, which shows a large part of the traffic is redirected into the barn. This eases slab alloc/free churn and cuts page allocator allocations/frees by 52.85%.

Additionally, NUMA performance also seems to see some improvement. Under the maple tree benchmark, the free_slowpath metric likely reflects objects that enter add_ptr_to_bulk_krc_lock() due to nid mismatches and are eventually freed via kfree_bulk(). This metric also shows a noticeable drop.

Metrics like alloc_fastpath did improve, but their absolute numbers are small and likely unrelated to the maple tree test.

The tradeoff is a increase in slab fragmentation, with total_objects and slabs growing by 32.98%. I suspect this happens because as more traffic gets routed to the barn layer, objects end up being more scattered, which ends up pinning more slabs.

For comparison: the parking mechanism reduces lock contention at the node partial list layer, while this experimental patch absorb the traffic earlier at the barn layer. They are independent in mechanism. Interestingly, both approaches deliver very comparable performance improvements. A bit frustratingly, combining the two only squeezes out an extra ~1% gain, I'm still investigating why that is.

Phew, that turned out to be quite a long write-up!

All in all, I feel we could probably focus on evaluating and pursuing this experimental patch first. For maple tree performance specifically, it seems like it might be the better fit compared to the parking mechanism (which is probably better suited for generic allocation pressure outside of maple tree).

Quoted 9 lines
Quoted 5 lines

Since the fundamental purpose of __slab_free() is to make newly freed partial/empty slabs visible to the sheaf refill or alloc slowpath, these slabs can be temporarily stored in a staging area in a lockless manner instead of making the free slowpath contend for the lock. The sheaf

However the lockless manipulation is still going to contend on the llist_head. But perhaps it's limited enough in both users and lenght of operations to make a difference.

Agreed, locked or lockless, there's always some unavoidable cost. But from the performance data, contention on llist_head still seems quite a bit friendlier.

Quoted 10 lines
Quoted 5 lines

refill or alloc slowpath then checks this staging area first when allocating objects. This achieves the goal of making these slabs visible to the sheaf refill or alloc slowpath while allowing the free slowpath to operate locklessly. This process is called "parking".

I'm gonna pull a David Hildenbrand trick here and question the name :) It seems to me it's an (extension of the) partial list, but lockless. Parking would suggest to me that it's put somewhere aside not to be used, or something.

Haha totally! When I first came up with the idea, the word 'park' just popped into my head. I thought it sounded pretty cool, so I just went with it :P

It definitely deserves a more fitting name!

Until we come up with a better name, I'll stick with the term 'park' for the rest of this discussion. :)

Quoted 10 lines
Quoted 5 lines

Parking occurs in only one case: when __slab_free() encounters a full -> partial/empty transition and the trylock fails. In this case, __slab_free() attaches the slab to an llist locklessly, instead of waiting for the lock unnecessarily.

It could be interesting to also see if skipping the trylock completely (another cache contending operation) helps even more. Also whether moving the llist_node to a different cache line than list_lock (and fields protected by it) helps even more, or not.

That's a really insightful idea! I'll verify it next and follow up once I have the results.

Quoted 38 lines
Quoted 30 lines

Conversely, the process of moving these parked slabs from the llist back to the partial list is called "unpark". Unpark occurs in four cases:

1. Sheaf refill or alloc slowpath: This is the core case. The sheaf refill or alloc slowpath must see the parked slabs, so the first thing done after acquiring the lock in the sheaf refill or alloc slowpath is unpark.
2. Cache shrinking: shrinking also needs to see slabs in the parked state.
3. Cache destruction: kmem_cache_destroy() must also see parked slabs, which is obvious, otherwise memory would leak.
4. delayed_work (see corner case b below)

Why is this scheme correct? Because paths entering the sheaf refill or alloc slowpath can see both slabs on the partial list and slabs on the parked llist, while allocation paths that do not enter the sheaf refill or alloc slowpath would not check the partial list in the first place and naturally do not need to care about parked slabs. Therefore, whether an allocation takes the sheaf refill or the alloc slowpath or not, slabs on the parked llist and slabs on the partial list make no difference to the allocator. This visibility equivalence is the core of the scheme. This analysis also shows that the scheme does not affect the utilization of partial slabs or lead to increased fragmentation.

Corner cases to handle:
a. Parked slabs may become completely empty. Therefore, unpark must also
check min_partial and free excess empty slabs instead of adding them back to the partial list.

Quoted 7 lines

b. In rare cases, the system may go idle immediately after slabs are
parked, and the sheaf refill or alloc slowpath may never run again. These parked slabs would then remain in the llist until the next sheaf refill or alloc slowpath performs an unpark. To solve this problem, add a delayed_work named unpark_work to add parked slabs back to the partial list when no other path unparks them.

Quoted 3 lines

OK, but is this a problem that needs the delayed work? If the slabs are still partial, they would just sit on the partial list rather than on the llist, but it would cause no extra bloat?

Spot on, that's very true.
When I originally decided to flush it as soon as possible, the intent was to stay as close to the existing code flow as possible, essentially making the parking mechanism a transient measure that steps in only briefly at specific moments rather than a persistent one.

Quoted 3 lines

It could be a problem only if free slab(s) got stuck on the llist.

So I'd try to avoid the delayed work as it's quite a red flag.

Agreed, it's indeed not ideal.

Quoted 8 lines

Periodic
flushing of alien arrays used to be a very unpopular part of SLAB implementation. I think there might be two ways:

1) submit the delayed work only when transitioning partial->empty slab on the llist. Would likely require flagging slabs that are on the llist. Hopefully this will limit the submissions to negligible amounts.

Quoted 5 lines

2) remove the delayed work completely, instead __slab_free() would perform the "unpark" immediately when detecting partial->empty slab transition on the llist. Would need flagging the slabs as well.

I guess 2) would be preferred unless it compromises the benefits too much.

Agreed, option 2) looks like the better way to go. Perhaps have __slab_free() detect the partial->empty transition, and if the current slab isn't on the partial list (either parked or detached by a refill), trigger an unpark operation. That would nicely eliminate the need for a delayed work. (The only slab we could miss this way is one where the parking path is between the cmpxchg and the llist_add.)

Quoted 9 lines
Quoted 8 lines

On will-it-scale mmap1 with 192 processes, throughput increases from 29237910 to 35585663 (+21.7%). native_queued_spin_lock_slowpath drops from 44% to 30% of cycles and __slab_free() disappears from the lock profile. alloc_slab,free_slab drop by 52%, and park_slab equals unpark_slab exactly, confirming no parked slabs are left stranded.

--- >8 ---
mm/slub: refill prefilled sheaves from the barn

For evaluation.

---
 mm/slub.c | 118 +++++++++++++++++++++++++++++++++++++++++++++++++++---
 1 file changed, 112 insertions(+), 6 deletions(-)
mm/slub.c +112 -6
index 27a78d63f537..7d337dbe26a5 100644
@@ -427,6 +427,8 @@ struct node_barn {
 	spinlock_t lock;
 	struct list_head sheaves_full;
 	struct list_head sheaves_empty;
+	/* leftovers of prefill or refill, protected by barn->lock */
+	struct slab_sheaf *sheaf_partial;
 	unsigned int nr_full;
 	unsigned int nr_empty;
 };
@@ -3183,6 +3185,69 @@ static struct slab_sheaf *barn_get_empty_sheaf(struct node_barn *barn,
 	return empty;
 }
 
+/*
+ * Exchange @sheaf, which holds fewer objects than requested, for a full sheaf
+ * from the barn. The objects of @sheaf stay in the barn: it becomes the barn's
+ * partial sheaf, or its objects are merged into the existing one, which becomes
+ * a full sheaf when it reaches capacity. That way the leftovers neither occupy
+ * a full-sheaf count nor have to be flushed.
+ *
+ * Returns NULL if the barn has no full sheaf.
+ */
+static struct slab_sheaf *barn_replace_partial_sheaf(struct kmem_cache *s,
+						     struct node_barn *barn,
+						     struct slab_sheaf *sheaf)
+{
+	struct slab_sheaf *full, *partial;
+	unsigned int to_move;
+	unsigned long flags;
+
+	if (!data_race(barn->nr_full))
+		return NULL;
+
+	spin_lock_irqsave(&barn->lock, flags);
+
+	if (unlikely(!barn->nr_full)) {
+		spin_unlock_irqrestore(&barn->lock, flags);
+		return NULL;
+	}
+
+	full = list_first_entry(&barn->sheaves_full, struct slab_sheaf,
+				barn_list);
+	list_del(&full->barn_list);
+	barn->nr_full--;
+
+	partial = barn->sheaf_partial;
+	if (partial) {
+		to_move = min(sheaf->size, s->sheaf_capacity - partial->size);
+		sheaf->size -= to_move;
+		memcpy(&partial->objects[partial->size],
+		       &sheaf->objects[sheaf->size], to_move * sizeof(void *));
+		partial->size += to_move;
+
+		if (partial->size == s->sheaf_capacity) {
+			list_add(&partial->barn_list, &barn->sheaves_full);
+			barn->nr_full++;
+			barn->sheaf_partial = NULL;
+		}
+	}
+
+	if (sheaf->size) {
+		/* no partial sheaf, or it just became full */
+		barn->sheaf_partial = sheaf;
+	} else {
+		list_add(&sheaf->barn_list, &barn->sheaves_empty);
+		barn->nr_empty++;
+	}
+
+	spin_unlock_irqrestore(&barn->lock, flags);
+
+	full->capacity = s->sheaf_capacity;
+	full->pfmemalloc = false;
+
+	return full;
+}
+
 /*
  * The following two functions are used mainly in cases where we have to undo an
  * intended action due to a race or cpu migration. Thus they do not check the
@@ -3317,6 +3382,7 @@ 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->sheaf_partial = NULL;
 	barn->nr_full = 0;
 	barn->nr_empty = 0;
 }
@@ -3334,6 +3400,10 @@ static void barn_shrink(struct kmem_cache *s, struct node_barn *barn)
 	barn->nr_full = 0;
 	list_splice_init(&barn->sheaves_empty, &empty_list);
 	barn->nr_empty = 0;
+	if (barn->sheaf_partial) {
+		list_add(&barn->sheaf_partial->barn_list, &full_list);
+		barn->sheaf_partial = NULL;
+	}
 
 	spin_unlock_irqrestore(&barn->lock, flags);
 
@@ -5233,12 +5303,49 @@ void *kmem_cache_alloc_node_noprof(struct kmem_cache *s, gfp_t gfpflags, int nod
 }
 EXPORT_SYMBOL(kmem_cache_alloc_node_noprof);
 
+/*
+ * Refill by swapping *@sheafp for a full sheaf from the barn. The old sheaf and
+ * its objects stay in the barn. Returns true when the new sheaf is full.
+ */
+static bool refill_sheaf_from_barn(struct kmem_cache *s,
+				   struct slab_sheaf **sheafp)
+{
+	struct node_barn *barn = get_barn(s);
+	struct slab_sheaf *sheaf = *sheafp;
+	struct slab_sheaf *full;
+
+	/* objects from pfmemalloc slabs must not enter the barn */
+	if (!barn || sheaf->pfmemalloc)
+		return false;
+
+	full = barn_replace_partial_sheaf(s, barn, sheaf);
+	if (!full)
+		return false;
+
+	stat(s, BARN_GET);
+	*sheafp = full;
+
+	/*
+	 * The sheaf may hold fewer than capacity objects: rcu_free_sheaf()
+	 * puts it in the barn as full even when slab_free_hook() has taken
+	 * some out (KFENCE, KASAN). __prefill_sheaf_pfmemalloc() then
+	 * continues to refill it.
+	 */
+	return full->size == s->sheaf_capacity;
+}
+
 static int __prefill_sheaf_pfmemalloc(struct kmem_cache *s,
-				      struct slab_sheaf *sheaf, gfp_t gfp)
+				      struct slab_sheaf **sheafp, gfp_t gfp)
 {
+	struct slab_sheaf *sheaf;
 	gfp_t gfp_nomemalloc;
 	int ret;
 
+	if (refill_sheaf_from_barn(s, sheafp))
+		return 0;
+
+	sheaf = *sheafp;
+
 	gfp_nomemalloc = gfp | __GFP_NOMEMALLOC;
 	if (gfp_pfmemalloc_allowed(gfp))
 		gfp_nomemalloc |= __GFP_NOWARN;
@@ -5331,7 +5438,7 @@ kmem_cache_prefill_sheaf(struct kmem_cache *s, gfp_t gfp, unsigned int size)
 		sheaf->pfmemalloc = false;
 
 		if (sheaf->size < size &&
-		    __prefill_sheaf_pfmemalloc(s, sheaf, gfp)) {
+		    __prefill_sheaf_pfmemalloc(s, &sheaf, gfp)) {
 			sheaf_flush_unused(s, sheaf);
 			free_empty_sheaf(s, sheaf);
 			sheaf = NULL;
@@ -5401,11 +5508,10 @@ void kmem_cache_return_sheaf(struct kmem_cache *s, gfp_t gfp,
  * the given size.
  *
  * Return: 0 on success. The sheaf will contain at least @size objects.
- * The sheaf might have been replaced with a new one if more than
- * sheaf->capacity objects are requested.
+ * The sheaf might have been replaced with a new one.
  *
  * Return: -ENOMEM on failure. Some objects might have been added to the sheaf
- * but the sheaf will not be replaced.
+ * and the sheaf might have been replaced.
  *
  * In practice we always refill to full sheaf's capacity.
  */
@@ -5427,7 +5533,7 @@ int kmem_cache_refill_sheaf(struct kmem_cache *s, gfp_t gfp,
 
 	if (likely(sheaf->capacity >= size)) {
 		if (likely(sheaf->capacity == s->sheaf_capacity))
-			return __prefill_sheaf_pfmemalloc(s, sheaf, gfp);
+			return __prefill_sheaf_pfmemalloc(s, sheafp, gfp);
 
 		if (!__kmem_cache_alloc_bulk(s, gfp, sheaf->capacity - sheaf->size,
 					     &sheaf->objects[sheaf->size]))
Signature · 1 line
2.55.0
maintainer Reviewed-by on v1 1/2
#14 lore raw

Re: [RFC PATCH 1/2] mm/slub: make the case handling in __slab_free() easier to follow

In reply to Hao Li
Quoted 21 lines · Hao Li

There are 7 possible transitions in __slab_free():

a. partial->partial
b. partial->empty, offlist
c. partial->empty, onlist, exceeding min_partial d. partial->empty, onlist, not exceeding min_partial e. full->empty, exceeding min_partial
f. full->empty, not exceeding min_partial g. full->partial

(There is no offlist variant of e, f and g as a full slab is on no list.)

Clarify which case each branch handles, and replace the goto with a return at the end of the skipped block so that every branch explicitly states its coverage.

Case 'a' is the only path that needs neither list_lock nor list handling. Give it an early continue: handling it upfront is much clearer than forcing every other case into a nested block.

Quoted 7 lines

Also, read SL_partial once after the loop right where it is used, rather than re-reading it on every iteration.

No functional change.

---

Looks good to me (with Vlastimil's suggestions adjusted),

Quoted 8 lines
 mm/slub.c | 95 ++++++++++++++++++++++++++++---------------------------
 1 file changed, 49 insertions(+), 46 deletions(-)
mm/slub.c +0 -0
index b0cd0572e2f2..e20375307770 100644
@@ -5748,76 +5748,79 @@ static void __slab_free(struct kmem_cache *s, struct slab *slab,

[...]

mm/slub.c static void __slab_free(struct kmem_cache *s, struct slab *slab, · line 5767

Quoted 8 lines
mm/slub.c +8 -0
+		/*
+		 * The slab might need to be taken off (due to becoming empty)
+		 * or added to (due to not being full anymore) the partial
+		 * list.
+		 *
+		 * Speculatively acquire list_lock before calling cmpxchg(), as
+		 * performing cmpxchg() prior to lock acquisition races with
+		 * concurrent paths, such as the shrinker.

nit: it's bit weird to mention shrinkers specifically?

Signature · 2 lines
Cheers,
Harry / Hyeonggon
#20 lore raw
In reply to Hao Li
Quoted 15 lines · Hao Li
Quoted 5 lines · Vlastimil Babka (SUSE)
Quoted 4 lines · Hao Li

Detailed data
-------------

Quoted 8 lines
Quoted 4 lines

metric before after delta change
==========================================================================================
alloc_fastpath 155,417 168,534 13,117 +8.44%
alloc_slab 55,679,646 26,702,510 -28,977,136 -52.04%

It's interesting that this is reduced so much. Is it because parked slabs cause more slabs to stay around for reuse, despite they are unparked immediately when trying to allocate/refill? That seems odd?

Quoted 5 lines

Yeah, it does look counter-intuitive at first glance. My understanding is that the parking mechanism helps by bypassing the partial list spinlock, allowing partial slabs to be parked onto the llist locklessly at any point. Because of this, the refill path gets to see and reuse more partial slabs instead of having to allocate fresh ones so frequently.

Hmm that's an interesting effect, surprisingly large if true. Because the slabs we'd be parking are transitioning from full, there would be most often just a single free object to reuse?

Quoted 11 lines
Quoted 11 lines
Quoted 10 lines

alloc_slowpath 0 0 0 +0.00%

barn_get                             2,715             2,771                56      +2.06%
barn_get_fail                            2                 0                -2    -100.00%
barn_put                             2,715             2,770                55      +2.03%
barn_put_fail                1,370,488,457     1,668,257,974       297,769,517     +21.73%
cmpxchg_double_fail              3,827,935           549,427        -3,278,508     -85.65%
free_add_partial             1,684,340,964     2,161,921,625       477,580,661     +28.35%

free_fastpath 31,766 32,979 1,213 +3.82%
free_rcu_sheaf 43,855,689,417 53,384,314,553 9,528,625,136 +21.73%

Quoted 7 lines
Quoted 3 lines

This metric (and others with similar numbers) should not be affected by the change. Does it mean the benchmark has a fixed time to run, but manages to do more work in that time thanks to the increased throughput?

Exactly! In fact, the increase in free_rcu_sheaf matches the throughput gain almost 1:1. A ~21% increase in throughput naturally translates to ~21% more object allocations and frees.

Ack!

#6 lore raw

Re: [RFC PATCH 2/2] mm/slub: introduce slab parking to reduce list_lock contention

In reply to Hao Li
Quoted 65 lines · Hao Li
Quoted 5 lines · Vlastimil Babka (SUSE)
Quoted 2 lines · Hao Li

Introduce a mechanism called parking to mitigate lock contention in the free slowpath.

Interesting!

Thanks!

Quoted 23 lines
Quoted 15 lines

In the free slowpath, when __slab_free() transitions a full slab into a partial/empty slab through a free operation, it must acquire the list lock to add these newly freed partial/empty slabs to the partial list.

Why must partial and empty slabs converted from full slabs be added to the partial list? Because only by doing so can the sheaf refill or alloc slowpath see these partial slabs and allocate from them. Therefore, the list insertion must be performed, which requires acquiring the lock and leads to heavy lock contention under high concurrency.

Analysis of profiling data from the will-it-scale mmap1 benchmark shows that full -> partial transitions account for a large proportion, second only to partial -> partial.

Quoted 7 lines

With extra instrumentation added to __slab_free(), the following data was collected for the maple_node cache (in counts):

  partial->partial    843017414
  full->partial       550719384
  partial->empty      17459564
  full->empty         2
Quoted 5 lines

That's a lot inded. I'd be careful if it's some specific aspect of the test, i.e. lots of parallel allocations followed by lots of frees, that wouldn't be that common in realistic workloads. But worth looking into at least. If it's this kind of pathologic behavior, then I expect changing sheaf size as suggested by Pedro wouldn't help much.

Thanks for pointing this out. I looked into this bursty alloc-and-free behavior a bit deeper and ran some further experiments.

The core question we want to answer is: why does such a massive volume of object allocations and frees fall straight through to the node partial list layer, rather than being caught and handled at the barn/sheaf layer? In SLUB's current design, the per-CPU main/spare sheaves act as the L1 cache, the barn as L2, and the node partial list as L3. For the mmap1 benchmark (which heavily stresses the maple tree), the allocation path uses kmem_cache_prefill_sheaf() rather than the generic allocation APIs, and the frees go through kfree_rcu().

Then, here is what happens during allocation: kmem_cache_prefill_sheaf() normally borrows the spare sheaf directly. If the sheaf holds fewer objects than requested, it refills it to capacity from the node partial list layer and this completely bypasses the barn layer. Once the maple tree finishes allocating a batch of objects, it returns the sheaf back to pcs->spare via kmem_cache_return_sheaf(). So in essence, this prefill path is just funneling objects directly from the node partial list into the maple tree through the spare sheaf. It skips the barn layer.

Then on the free side: these objects are freed via kfree_rcu, and then rcu_free_sheaf() checks if there is still room on the barn's full list. But since the allocation path never actually pulled from the barn, the full list stays permanently saturated. As a result, rcu_free_sheaf() always falls back to sheaf_flush_unused(), flushing objects straight into the node partial list layer. It skips the barn layer too.

Quoted 3 lines

So looking at this behavior, the benchmark does seem to reveal a gap in this allocation path, where a huge amount of traffic ends up bypassing the barn layer entirely.

Great find! Indeed that's a big gap for prefilled sheaf users, doh.

Quoted 10 lines

To see if we can address this, I draft an experimental patch. It introduces a new field, barn->sheaf_partial, which is a single sheaf rather than a list.

[The patch code is included at the end of this email.]

Whenever kmem_cache_prefill_sheaf() runs, it detaches pcs->spare and checks whether it holds enough objects for the request.

If so, it returns it right away as in the original code.

Quoted 7 lines

If not, call __prefill_sheaf_pfmemalloc() and then go into barn_replace_partial_sheaf() to swap the non-full spare sheaf with a full sheaf from the barn. The full sheaf is handed to the caller, while the non-full sheaf is temporarily stashed into barn->sheaf_partial. This largely avoids falling back to the node partial list. If barn->sheaf_partial already has a sheaf, we merge them together, and any resulting full or empty sheaves are placed back into the barn accordingly.

Makes sense to me!

Quoted 66 lines

The key idea here is simply to let __prefill_sheaf_pfmemalloc() pull a sheaf from the barn's full list, which makes room on the list for future rcu_free_sheaf() calls.

Here are the numbers with just this experimental patch applied (without the parking patch):

baseline: 28779879
after experimental patch: 35550211 (+23.5%)

metric before after delta change
=============================================================================================

aliases                                  0                 0                 0      +0.00%
align                                  256               256                 0      +0.00%

alloc_fastpath 23,259 59,287 36,028 +154.90%
alloc_node_mismatch 0 0 0 +0.00%
alloc_slab 10,171,378 4,796,346 -5,375,032 -52.84%
alloc_slowpath 0 0 0 +0.00%
barn_get 441 193,807,528 193,807,087 +43947185.26%
barn_get_fail 0 377 377 new
barn_put 441 181,694,607 181,694,166 +41200491.16%
barn_put_fail 272,868,220 156,335,632 -116,532,588 -42.71%
cache_dma 0 0 0 +0.00%
cmpxchg_double_fail 744,975 357,255 -387,720 -52.04%

cpu_partial                              0                 0                 0      +0.00%
cpu_slabs                                0                 0                 0      +0.00%
destroy_by_rcu                           0                 0                 0      +0.00%

free_add_partial 337,390,126 162,178,648 -175,211,478 -51.93%
free_fastpath 5,204 14,081 8,877 +170.58%
free_rcu_sheaf 8,731,794,372 10,816,953,777 2,085,159,405 +23.88%
free_rcu_sheaf_fail 0 0 0 +0.00%

free_remove_partial             10,170,229         4,794,785        -5,375,444     -52.85%
free_slab                       10,170,229         4,794,785        -5,375,444     -52.85%
free_slowpath                   18,697,056        11,563,127        -7,133,929     -38.16%
hwcache_align                            0                 0                 0      +0.00%
min_partial                              5                 5                 0      +0.00%
object_size                            256               256                 0      +0.00%
objects                             14,774            14,596              -178      -1.20%
objects_partial                     14,774            14,596              -178      -1.20%
objs_per_slab                           64                64                 0      +0.00%
order                                    2                 2                 0      +0.00%
order_fallback                           0                 0                 0      +0.00%
partial                              1,913             2,544               631     +32.98%
poison                                   0                 0                 0      +0.00%
reclaim_account                          0                 0                 0      +0.00%
red_zone                                 0                 0                 0      +0.00%
remote_node_defrag_ratio               100               100                 0      +0.00%
sanity_checks                            0                 0                 0      +0.00%
sheaf_alloc                    145,870,437       151,536,660         5,666,223      +3.88%
sheaf_capacity                          32                32                 0      +0.00%

sheaf_flush 8,731,787,311 5,002,740,743 -3,729,046,568 -42.71%
sheaf_free 145,870,431 151,536,655 5,666,224 +3.88%
sheaf_prefill_fast 3,500,187,266 4,331,383,393 831,196,127 +23.75%
sheaf_prefill_oversize 0 0 0 +0.00%
sheaf_prefill_slow 322 646 324 +100.62%

sheaf_refill                 8,750,484,664     5,014,304,944    -3,736,179,720     -42.70%
sheaf_return_fast            3,500,187,348     4,331,383,596       831,196,248     +23.75%
sheaf_return_slow                      240               443               203     +84.58%
slab_size                              256               256                 0      +0.00%
slabs                                1,913             2,544               631     +32.98%
slabs_cpu_partial                        0                 0                 0      +0.00%
store_user                               0                 0                 0      +0.00%
total_objects                      122,432           162,816            40,384     +32.98%
trace                                    0                 0                 0      +0.00%
usersize                                 0                 0                 0      +0.00%
Quoted 3 lines

derived before after change
=============================================================================================
page allocator churn (alloc_slab + free_slab) 20,341,607 9,591,131 -52.85%

Very nice!

Quoted 10 lines

As we can see from the data, barn_get and barn_put spike significantly, which shows a large part of the traffic is redirected into the barn. This eases slab alloc/free churn and cuts page allocator allocations/frees by 52.85%.

Additionally, NUMA performance also seems to see some improvement. Under the maple tree benchmark, the free_slowpath metric likely reflects objects that enter add_ptr_to_bulk_krc_lock() due to nid mismatches and are eventually freed via kfree_bulk(). This metric also shows a noticeable drop.

Quoted 7 lines

Metrics like alloc_fastpath did improve, but their absolute numbers are small and likely unrelated to the maple tree test.

The tradeoff is a increase in slab fragmentation, with total_objects and slabs growing by 32.98%. I suspect this happens because as more traffic gets routed to the barn layer, objects end up being more scattered, which ends up pinning more slabs.

Maybe it's partially also due to the fact that the test can run faster (as we discussed earlier), thus have e.g. more kfree_rcu() objects in flight (free_rcu_sheaf above increased a lot), etc. So I wouldn't worry too much.

Quoted 4 lines

For comparison: the parking mechanism reduces lock contention at the node partial list layer, while this experimental patch absorb the traffic earlier at the barn layer. They are independent in mechanism. Interestingly, both approaches deliver very comparable performance improvements. A bit

Great.

Quoted 2 lines

frustratingly, combining the two only squeezes out an extra ~1% gain, I'm still investigating why that is.

I don't think it would be bad if this change rendered the parking approach unnecessary. I suspect Pedro would be very happy :)

Quoted 1 line

Phew, that turned out to be quite a long write-up!

Thanks for that :)

Quoted 4 lines

All in all, I feel we could probably focus on evaluating and pursuing this experimental patch first. For maple tree performance specifically, it seems like it might be the better fit compared to the parking mechanism (which is probably better suited for generic allocation pressure outside of maple tree).

Agreed! I'd try to look at the code ASAP. For now we can probably... eh... park the parking patch :) and its possible improvements.

Thanks again!

author reviewer
#7 lore raw

Re: [RFC PATCH 2/2] mm/slub: introduce slab parking to reduce list_lock contention

Quoted 66 lines · Vlastimil Babka (SUSE)
Quoted 65 lines · Hao Li
Quoted 5 lines · Vlastimil Babka (SUSE)
Quoted 2 lines · Hao Li

Introduce a mechanism called parking to mitigate lock contention in the free slowpath.

Interesting!

Thanks!

Quoted 23 lines
Quoted 15 lines

In the free slowpath, when __slab_free() transitions a full slab into a partial/empty slab through a free operation, it must acquire the list lock to add these newly freed partial/empty slabs to the partial list.

Why must partial and empty slabs converted from full slabs be added to the partial list? Because only by doing so can the sheaf refill or alloc slowpath see these partial slabs and allocate from them. Therefore, the list insertion must be performed, which requires acquiring the lock and leads to heavy lock contention under high concurrency.

Analysis of profiling data from the will-it-scale mmap1 benchmark shows that full -> partial transitions account for a large proportion, second only to partial -> partial.

Quoted 7 lines

With extra instrumentation added to __slab_free(), the following data was collected for the maple_node cache (in counts):

  partial->partial    843017414
  full->partial       550719384
  partial->empty      17459564
  full->empty         2
Quoted 5 lines

That's a lot inded. I'd be careful if it's some specific aspect of the test, i.e. lots of parallel allocations followed by lots of frees, that wouldn't be that common in realistic workloads. But worth looking into at least. If it's this kind of pathologic behavior, then I expect changing sheaf size as suggested by Pedro wouldn't help much.

Thanks for pointing this out. I looked into this bursty alloc-and-free behavior a bit deeper and ran some further experiments.

The core question we want to answer is: why does such a massive volume of object allocations and frees fall straight through to the node partial list layer, rather than being caught and handled at the barn/sheaf layer? In SLUB's current design, the per-CPU main/spare sheaves act as the L1 cache, the barn as L2, and the node partial list as L3. For the mmap1 benchmark (which heavily stresses the maple tree), the allocation path uses kmem_cache_prefill_sheaf() rather than the generic allocation APIs, and the frees go through kfree_rcu().

Then, here is what happens during allocation: kmem_cache_prefill_sheaf() normally borrows the spare sheaf directly. If the sheaf holds fewer objects than requested, it refills it to capacity from the node partial list layer and this completely bypasses the barn layer. Once the maple tree finishes allocating a batch of objects, it returns the sheaf back to pcs->spare via kmem_cache_return_sheaf(). So in essence, this prefill path is just funneling objects directly from the node partial list into the maple tree through the spare sheaf. It skips the barn layer.

Then on the free side: these objects are freed via kfree_rcu, and then rcu_free_sheaf() checks if there is still room on the barn's full list. But since the allocation path never actually pulled from the barn, the full list stays permanently saturated. As a result, rcu_free_sheaf() always falls back to sheaf_flush_unused(), flushing objects straight into the node partial list layer. It skips the barn layer too.

Quoted 5 lines
Quoted 3 lines

So looking at this behavior, the benchmark does seem to reveal a gap in this allocation path, where a huge amount of traffic ends up bypassing the barn layer entirely.

Great find! Indeed that's a big gap for prefilled sheaf users, doh.

Thanks for confirming! :)

Quoted 106 lines
Quoted 11 lines

To see if we can address this, I draft an experimental patch. It introduces a new field, barn->sheaf_partial, which is a single sheaf rather than a list.

[The patch code is included at the end of this email.]

Whenever kmem_cache_prefill_sheaf() runs, it detaches pcs->spare and checks whether it holds enough objects for the request.

If so, it returns it right away as in the original code.

Quoted 7 lines

If not, call __prefill_sheaf_pfmemalloc() and then go into barn_replace_partial_sheaf() to swap the non-full spare sheaf with a full sheaf from the barn. The full sheaf is handed to the caller, while the non-full sheaf is temporarily stashed into barn->sheaf_partial. This largely avoids falling back to the node partial list. If barn->sheaf_partial already has a sheaf, we merge them together, and any resulting full or empty sheaves are placed back into the barn accordingly.

Makes sense to me!

Quoted 66 lines

The key idea here is simply to let __prefill_sheaf_pfmemalloc() pull a sheaf from the barn's full list, which makes room on the list for future rcu_free_sheaf() calls.

Here are the numbers with just this experimental patch applied (without the parking patch):

baseline: 28779879
after experimental patch: 35550211 (+23.5%)

metric before after delta change
=============================================================================================

aliases                                  0                 0                 0      +0.00%
align                                  256               256                 0      +0.00%

alloc_fastpath 23,259 59,287 36,028 +154.90%
alloc_node_mismatch 0 0 0 +0.00%
alloc_slab 10,171,378 4,796,346 -5,375,032 -52.84%
alloc_slowpath 0 0 0 +0.00%
barn_get 441 193,807,528 193,807,087 +43947185.26%
barn_get_fail 0 377 377 new
barn_put 441 181,694,607 181,694,166 +41200491.16%
barn_put_fail 272,868,220 156,335,632 -116,532,588 -42.71%
cache_dma 0 0 0 +0.00%
cmpxchg_double_fail 744,975 357,255 -387,720 -52.04%

cpu_partial                              0                 0                 0      +0.00%
cpu_slabs                                0                 0                 0      +0.00%
destroy_by_rcu                           0                 0                 0      +0.00%

free_add_partial 337,390,126 162,178,648 -175,211,478 -51.93%
free_fastpath 5,204 14,081 8,877 +170.58%
free_rcu_sheaf 8,731,794,372 10,816,953,777 2,085,159,405 +23.88%
free_rcu_sheaf_fail 0 0 0 +0.00%

free_remove_partial             10,170,229         4,794,785        -5,375,444     -52.85%
free_slab                       10,170,229         4,794,785        -5,375,444     -52.85%
free_slowpath                   18,697,056        11,563,127        -7,133,929     -38.16%
hwcache_align                            0                 0                 0      +0.00%
min_partial                              5                 5                 0      +0.00%
object_size                            256               256                 0      +0.00%
objects                             14,774            14,596              -178      -1.20%
objects_partial                     14,774            14,596              -178      -1.20%
objs_per_slab                           64                64                 0      +0.00%
order                                    2                 2                 0      +0.00%
order_fallback                           0                 0                 0      +0.00%
partial                              1,913             2,544               631     +32.98%
poison                                   0                 0                 0      +0.00%
reclaim_account                          0                 0                 0      +0.00%
red_zone                                 0                 0                 0      +0.00%
remote_node_defrag_ratio               100               100                 0      +0.00%
sanity_checks                            0                 0                 0      +0.00%
sheaf_alloc                    145,870,437       151,536,660         5,666,223      +3.88%
sheaf_capacity                          32                32                 0      +0.00%

sheaf_flush 8,731,787,311 5,002,740,743 -3,729,046,568 -42.71%
sheaf_free 145,870,431 151,536,655 5,666,224 +3.88%
sheaf_prefill_fast 3,500,187,266 4,331,383,393 831,196,127 +23.75%
sheaf_prefill_oversize 0 0 0 +0.00%
sheaf_prefill_slow 322 646 324 +100.62%

sheaf_refill                 8,750,484,664     5,014,304,944    -3,736,179,720     -42.70%
sheaf_return_fast            3,500,187,348     4,331,383,596       831,196,248     +23.75%
sheaf_return_slow                      240               443               203     +84.58%
slab_size                              256               256                 0      +0.00%
slabs                                1,913             2,544               631     +32.98%
slabs_cpu_partial                        0                 0                 0      +0.00%
store_user                               0                 0                 0      +0.00%
total_objects                      122,432           162,816            40,384     +32.98%
trace                                    0                 0                 0      +0.00%
usersize                                 0                 0                 0      +0.00%
Quoted 3 lines

derived before after change
=============================================================================================
page allocator churn (alloc_slab + free_slab) 20,341,607 9,591,131 -52.85%

Very nice!

Quoted 13 lines

As we can see from the data, barn_get and barn_put spike significantly, which shows a large part of the traffic is redirected into the barn. This eases slab alloc/free churn and cuts page allocator allocations/frees by 52.85%.

Additionally, NUMA performance also seems to see some improvement. Under the maple tree benchmark, the free_slowpath metric likely reflects objects that enter add_ptr_to_bulk_krc_lock() due to nid mismatches and are eventually freed via kfree_bulk(). This metric also shows a noticeable drop.

Metrics like alloc_fastpath did improve, but their absolute numbers are small and likely unrelated to the maple tree test.

Quoted 8 lines
Quoted 4 lines

The tradeoff is a increase in slab fragmentation, with total_objects and slabs growing by 32.98%. I suspect this happens because as more traffic gets routed to the barn layer, objects end up being more scattered, which ends up pinning more slabs.

Maybe it's partially also due to the fact that the test can run faster (as we discussed earlier), thus have e.g. more kfree_rcu() objects in flight (free_rcu_sheaf above increased a lot), etc. So I wouldn't worry too much.

Yeah, make sense, and I tested it multiple times, this impact is bounded.

Quoted 6 lines
Quoted 5 lines

For comparison: the parking mechanism reduces lock contention at the node partial list layer, while this experimental patch absorb the traffic earlier at the barn layer. They are independent in mechanism. Interestingly, both approaches deliver very comparable performance improvements. A bit

Quoted 7 lines

Great.

Quoted 2 lines

frustratingly, combining the two only squeezes out an extra ~1% gain, I'm still investigating why that is.

I don't think it would be bad if this change rendered the parking approach unnecessary. I suspect Pedro would be very happy :)

Exactly. The parking approach is a bit invasive, while partial sheaves feel much cleaner.

Quoted 5 lines
Quoted 2 lines

Phew, that turned out to be quite a long write-up!

Thanks for that :)

Quoted 7 lines
Quoted 4 lines

All in all, I feel we could probably focus on evaluating and pursuing this experimental patch first. For maple tree performance specifically, it seems like it might be the better fit compared to the parking mechanism (which is probably better suited for generic allocation pressure outside of maple tree).

Agreed! I'd try to look at the code ASAP. For now we can probably... eh... park the parking patch :) and its possible improvements.

Haha, totally agree, thanks! No rush though, take your time. :)

Quoted 2 lines

Thanks again!

Signature · 2 lines
Thanks,
Hao
#8 lore raw

Re: [RFC PATCH 2/2] mm/slub: introduce slab parking to reduce list_lock contention

In reply to Hao Li
Quoted 14 lines · Hao Li

--- >8 ---
mm/slub: refill prefilled sheaves from the barn

For evaluation.

---
 mm/slub.c | 118 +++++++++++++++++++++++++++++++++++++++++++++++++++---
 1 file changed, 112 insertions(+), 6 deletions(-)
mm/slub.c +0 -0
index 27a78d63f537..7d337dbe26a5 100644

mm/slub.c struct node_barn { · line 430

Quoted 4 lines
mm/slub.c +1 -0
@@ -427,6 +427,8 @@ struct node_barn {
 	spinlock_t lock;
 	struct list_head sheaves_full;
 	struct list_head sheaves_empty;
+	/* leftovers of prefill or refill, protected by barn->lock */

All the fields are protected by the lock so I don't think it's worth pointing out specifically.
"prefill or refill" sounds like it may include also internal sheaf refill, which is not the case (but maybe something worth exploring later)

Quoted 23 lines
mm/slub.c +16 -0
+	struct slab_sheaf *sheaf_partial;
 	unsigned int nr_full;
 	unsigned int nr_empty;
 };
@@ -3183,6 +3185,69 @@ static struct slab_sheaf *barn_get_empty_sheaf(struct node_barn *barn,
 	return empty;
 }
 
+/*
+ * Exchange @sheaf, which holds fewer objects than requested, for a full sheaf
+ * from the barn. The objects of @sheaf stay in the barn: it becomes the barn's
+ * partial sheaf, or its objects are merged into the existing one, which becomes
+ * a full sheaf when it reaches capacity. That way the leftovers neither occupy
+ * a full-sheaf count nor have to be flushed.
+ *
+ * Returns NULL if the barn has no full sheaf.
+ */
+static struct slab_sheaf *barn_replace_partial_sheaf(struct kmem_cache *s,
+						     struct node_barn *barn,
+						     struct slab_sheaf *sheaf)
+{
+	struct slab_sheaf *full, *partial;
+	unsigned int to_move;

mm/slub.c static struct slab_sheaf *barn_get_empty_sheaf(struct node_barn *barn, · line 3212

Quoted 10 lines
mm/slub.c +10 -0
+	unsigned long flags;
+
+	if (!data_race(barn->nr_full))
+		return NULL;
+
+	spin_lock_irqsave(&barn->lock, flags);
+
+	if (unlikely(!barn->nr_full)) {
+		spin_unlock_irqrestore(&barn->lock, flags);
+		return NULL;

Hmm what if there's no full, but there's sheaf_partial with enough objects to make a full sheaf together with @sheaf?

Quoted 24 lines
mm/slub.c +24 -0
+	}
+
+	full = list_first_entry(&barn->sheaves_full, struct slab_sheaf,
+				barn_list);
+	list_del(&full->barn_list);
+	barn->nr_full--;
+
+	partial = barn->sheaf_partial;
+	if (partial) {
+		to_move = min(sheaf->size, s->sheaf_capacity - partial->size);
+		sheaf->size -= to_move;
+		memcpy(&partial->objects[partial->size],
+		       &sheaf->objects[sheaf->size], to_move * sizeof(void *));
+		partial->size += to_move;
+
+		if (partial->size == s->sheaf_capacity) {
+			list_add(&partial->barn_list, &barn->sheaves_full);
+			barn->nr_full++;
+			barn->sheaf_partial = NULL;
+		}
+	}
+
+	if (sheaf->size) {
+		/* no partial sheaf, or it just became full */

mm/slub.c static struct slab_sheaf *barn_get_empty_sheaf(struct node_barn *barn, · line 3246

Quoted 10 lines
mm/slub.c +10 -0
+		barn->sheaf_partial = sheaf;
+	} else {
+		list_add(&sheaf->barn_list, &barn->sheaves_empty);
+		barn->nr_empty++;
+	}
+
+	spin_unlock_irqrestore(&barn->lock, flags);
+
+	full->capacity = s->sheaf_capacity;
+	full->pfmemalloc = false;

I think this belongs more to the caller which deals with the prefilled sheaves specifically, and this helper is more low level.

Otherwise LGTM!

Quoted 110 lines
mm/slub.c +51 -6
+
+	return full;
+}
+
 /*
  * The following two functions are used mainly in cases where we have to undo an
  * intended action due to a race or cpu migration. Thus they do not check the
@@ -3317,6 +3382,7 @@ 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->sheaf_partial = NULL;
 	barn->nr_full = 0;
 	barn->nr_empty = 0;
 }
@@ -3334,6 +3400,10 @@ static void barn_shrink(struct kmem_cache *s, struct node_barn *barn)
 	barn->nr_full = 0;
 	list_splice_init(&barn->sheaves_empty, &empty_list);
 	barn->nr_empty = 0;
+	if (barn->sheaf_partial) {
+		list_add(&barn->sheaf_partial->barn_list, &full_list);
+		barn->sheaf_partial = NULL;
+	}
 
 	spin_unlock_irqrestore(&barn->lock, flags);
 
@@ -5233,12 +5303,49 @@ void *kmem_cache_alloc_node_noprof(struct kmem_cache *s, gfp_t gfpflags, int nod
 }
 EXPORT_SYMBOL(kmem_cache_alloc_node_noprof);
 
+/*
+ * Refill by swapping *@sheafp for a full sheaf from the barn. The old sheaf and
+ * its objects stay in the barn. Returns true when the new sheaf is full.
+ */
+static bool refill_sheaf_from_barn(struct kmem_cache *s,
+				   struct slab_sheaf **sheafp)
+{
+	struct node_barn *barn = get_barn(s);
+	struct slab_sheaf *sheaf = *sheafp;
+	struct slab_sheaf *full;
+
+	/* objects from pfmemalloc slabs must not enter the barn */
+	if (!barn || sheaf->pfmemalloc)
+		return false;
+
+	full = barn_replace_partial_sheaf(s, barn, sheaf);
+	if (!full)
+		return false;
+
+	stat(s, BARN_GET);
+	*sheafp = full;
+
+	/*
+	 * The sheaf may hold fewer than capacity objects: rcu_free_sheaf()
+	 * puts it in the barn as full even when slab_free_hook() has taken
+	 * some out (KFENCE, KASAN). __prefill_sheaf_pfmemalloc() then
+	 * continues to refill it.
+	 */
+	return full->size == s->sheaf_capacity;
+}
+
 static int __prefill_sheaf_pfmemalloc(struct kmem_cache *s,
-				      struct slab_sheaf *sheaf, gfp_t gfp)
+				      struct slab_sheaf **sheafp, gfp_t gfp)
 {
+	struct slab_sheaf *sheaf;
 	gfp_t gfp_nomemalloc;
 	int ret;
 
+	if (refill_sheaf_from_barn(s, sheafp))
+		return 0;
+
+	sheaf = *sheafp;
+
 	gfp_nomemalloc = gfp | __GFP_NOMEMALLOC;
 	if (gfp_pfmemalloc_allowed(gfp))
 		gfp_nomemalloc |= __GFP_NOWARN;
@@ -5331,7 +5438,7 @@ kmem_cache_prefill_sheaf(struct kmem_cache *s, gfp_t gfp, unsigned int size)
 		sheaf->pfmemalloc = false;
 
 		if (sheaf->size < size &&
-		    __prefill_sheaf_pfmemalloc(s, sheaf, gfp)) {
+		    __prefill_sheaf_pfmemalloc(s, &sheaf, gfp)) {
 			sheaf_flush_unused(s, sheaf);
 			free_empty_sheaf(s, sheaf);
 			sheaf = NULL;
@@ -5401,11 +5508,10 @@ void kmem_cache_return_sheaf(struct kmem_cache *s, gfp_t gfp,
  * the given size.
  *
  * Return: 0 on success. The sheaf will contain at least @size objects.
- * The sheaf might have been replaced with a new one if more than
- * sheaf->capacity objects are requested.
+ * The sheaf might have been replaced with a new one.
  *
  * Return: -ENOMEM on failure. Some objects might have been added to the sheaf
- * but the sheaf will not be replaced.
+ * and the sheaf might have been replaced.
  *
  * In practice we always refill to full sheaf's capacity.
  */
@@ -5427,7 +5533,7 @@ int kmem_cache_refill_sheaf(struct kmem_cache *s, gfp_t gfp,
 
 	if (likely(sheaf->capacity >= size)) {
 		if (likely(sheaf->capacity == s->sheaf_capacity))
-			return __prefill_sheaf_pfmemalloc(s, sheaf, gfp);
+			return __prefill_sheaf_pfmemalloc(s, sheafp, gfp);
 
 		if (!__kmem_cache_alloc_bulk(s, gfp, sheaf->capacity - sheaf->size,
 					     &sheaf->objects[sheaf->size]))
author reviewer
#21 lore raw
In reply to Vlastimil Babka (SUSE)
Quoted 22 lines · Vlastimil Babka (SUSE)
Quoted 15 lines · Hao Li
Quoted 5 lines · Vlastimil Babka (SUSE)
Quoted 4 lines · Hao Li

Detailed data
-------------

Quoted 8 lines
Quoted 4 lines

metric before after delta change
==========================================================================================
alloc_fastpath 155,417 168,534 13,117 +8.44%
alloc_slab 55,679,646 26,702,510 -28,977,136 -52.04%

It's interesting that this is reduced so much. Is it because parked slabs cause more slabs to stay around for reuse, despite they are unparked immediately when trying to allocate/refill? That seems odd?

Quoted 5 lines

Yeah, it does look counter-intuitive at first glance. My understanding is that the parking mechanism helps by bypassing the partial list spinlock, allowing partial slabs to be parked onto the llist locklessly at any point. Because of this, the refill path gets to see and reuse more partial slabs instead of having to allocate fresh ones so frequently.

Quoted 3 lines

Hmm that's an interesting effect, surprisingly large if true. Because the slabs we'd be parking are transitioning from full, there would be most often just a single free object to reuse?

That makes sense. That said, it might be more than a single object, since build_detached_freelist() tries to free objects from the same slab together.

Even though we "park" the parking series for now, I was still curious to understand the underlying behavior. So I add a counter in get_partial_node_bulk() to see how many partial slabs it can see. (counting freed objects directly is tough, so the partial slab count gives us a rough picture)

Interestingly, each get_partial_node_bulk() on the patched kernel saw about 3-4x more partial slabs on average compared to baseline. This suggest that the parking mechanism can supply more allocatable objects even under lock contention, since it can avoid waiting for list lock.

For example, in the baseline kernel, if the lock is held by an allocator, a freer has to wait on it. Once it's released, the lock might just get grabbed by yet another allocator, leaving the freer stuck waiting. As a result, the partial list ends up starved of free objects.

Signature · 2 lines
Thanks,
Hao
maintainer
#10 lore raw

Re: [RFC PATCH 2/2] mm/slub: introduce slab parking to reduce list_lock contention

In reply to Hao Li

Apologies for chiming in late, trying to catch up...

Quoted 13 lines · Hao Li
Quoted 1 line · Vlastimil Babka (SUSE)

On 8/24/26 14:25, Hao Li wrote:

Thanks for pointing this out. I looked into this bursty alloc-and-free behavior a bit deeper and ran some further experiments.

The core question we want to answer is: why does such a massive volume of object allocations and frees fall straight through to the node partial list layer, rather than being caught and handled at the barn/sheaf layer? In SLUB's current design, the per-CPU main/spare sheaves act as the L1 cache, the barn as L2, and the node partial list as L3. For the mmap1 benchmark (which heavily stresses the maple tree), the allocation path uses kmem_cache_prefill_sheaf() rather than the generic allocation APIs, and the frees go through kfree_rcu().

Quoted 4 lines

Then, here is what happens during allocation: kmem_cache_prefill_sheaf() normally borrows the spare sheaf directly. If the sheaf holds fewer objects than requested, it refills it to capacity from the node partial list layer and this completely bypasses the barn layer.

Nice observation, Hao!

Quoted 5 lines

Once the maple tree finishes
allocating a batch of objects, it returns the sheaf back to pcs->spare via kmem_cache_return_sheaf(). So in essence, this prefill path is just funneling objects directly from the node partial list into the maple tree through the spare sheaf. It skips the barn layer.

Nice observation.

Quoted 6 lines

Then on the free side: these objects are freed via kfree_rcu, and then rcu_free_sheaf() checks if there is still room on the barn's full list. But since the allocation path never actually pulled from the barn, the full list stays permanently saturated. As a result, rcu_free_sheaf() always falls back to sheaf_flush_unused(), flushing objects straight into the node partial list layer. It skips the barn layer too.

Nice observation.

Quoted 3 lines

So looking at this behavior, the benchmark does seem to reveal a gap in this allocation path, where a huge amount of traffic ends up bypassing the barn layer entirely.

Indeed.

So, either refilling or flushing partial sheaves bypasses the barn layer. This is particularly a problem for prefilled sheaf users because they perform refills and flushes more frequently.

Partial sheaves serve alloc and free for ordinary users, but often times that's not the case for prefilled sheaf users.

Quoted 18 lines

To see if we can address this, I draft an experimental patch. It introduces a new field, barn->sheaf_partial, which is a single sheaf rather than a list.

[The patch code is included at the end of this email.]

Whenever kmem_cache_prefill_sheaf() runs, it detaches pcs->spare and checks whether it holds enough objects for the request.

If so, it returns it right away as in the original code.

If not, call __prefill_sheaf_pfmemalloc() and then go into barn_replace_partial_sheaf() to swap the non-full spare sheaf with a full sheaf from the barn. The full sheaf is handed to the caller, while the non-full sheaf is temporarily stashed into barn->sheaf_partial. This largely avoids falling back to the node partial list. If barn->sheaf_partial already has a sheaf, we merge them together, and any resulting full or empty sheaves are placed back into the barn accordingly.

Quoted 3 lines

The key idea here is simply to let __prefill_sheaf_pfmemalloc() pull a sheaf from the barn's full list, which makes room on the list for future rcu_free_sheaf() calls.

And the idea is to provide a place for a partial sheaf to say to avoid flushing and refilling it, and which helps avoiding bypassing the barn layer.

The reason why we don't need a list of partial sheaves because we want to merge them and move the partial sheaf to full or empty list.

Makes sense to me :-)

Quoted 62 lines

Here are the numbers with just this experimental patch applied (without the parking patch):

baseline: 28779879
after experimental patch: 35550211 (+23.5%)

metric before after delta change
=============================================================================================

aliases                                  0                 0                 0      +0.00%
align                                  256               256                 0      +0.00%

alloc_fastpath 23,259 59,287 36,028 +154.90%
alloc_node_mismatch 0 0 0 +0.00%
alloc_slab 10,171,378 4,796,346 -5,375,032 -52.84%
alloc_slowpath 0 0 0 +0.00%
barn_get 441 193,807,528 193,807,087 +43947185.26%
barn_get_fail 0 377 377 new
barn_put 441 181,694,607 181,694,166 +41200491.16%
barn_put_fail 272,868,220 156,335,632 -116,532,588 -42.71%
cache_dma 0 0 0 +0.00%
cmpxchg_double_fail 744,975 357,255 -387,720 -52.04%

cpu_partial                              0                 0                 0      +0.00%
cpu_slabs                                0                 0                 0      +0.00%
destroy_by_rcu                           0                 0                 0      +0.00%

free_add_partial 337,390,126 162,178,648 -175,211,478 -51.93%
free_fastpath 5,204 14,081 8,877 +170.58%
free_rcu_sheaf 8,731,794,372 10,816,953,777 2,085,159,405 +23.88%
free_rcu_sheaf_fail 0 0 0 +0.00%

free_remove_partial             10,170,229         4,794,785        -5,375,444     -52.85%
free_slab                       10,170,229         4,794,785        -5,375,444     -52.85%
free_slowpath                   18,697,056        11,563,127        -7,133,929     -38.16%
hwcache_align                            0                 0                 0      +0.00%
min_partial                              5                 5                 0      +0.00%
object_size                            256               256                 0      +0.00%
objects                             14,774            14,596              -178      -1.20%
objects_partial                     14,774            14,596              -178      -1.20%
objs_per_slab                           64                64                 0      +0.00%
order                                    2                 2                 0      +0.00%
order_fallback                           0                 0                 0      +0.00%
partial                              1,913             2,544               631     +32.98%
poison                                   0                 0                 0      +0.00%
reclaim_account                          0                 0                 0      +0.00%
red_zone                                 0                 0                 0      +0.00%
remote_node_defrag_ratio               100               100                 0      +0.00%
sanity_checks                            0                 0                 0      +0.00%
sheaf_alloc                    145,870,437       151,536,660         5,666,223      +3.88%
sheaf_capacity                          32                32                 0      +0.00%

sheaf_flush 8,731,787,311 5,002,740,743 -3,729,046,568 -42.71%
sheaf_free 145,870,431 151,536,655 5,666,224 +3.88%
sheaf_prefill_fast 3,500,187,266 4,331,383,393 831,196,127 +23.75%
sheaf_prefill_oversize 0 0 0 +0.00%
sheaf_prefill_slow 322 646 324 +100.62%

sheaf_refill                 8,750,484,664     5,014,304,944    -3,736,179,720     -42.70%
sheaf_return_fast            3,500,187,348     4,331,383,596       831,196,248     +23.75%
sheaf_return_slow                      240               443               203     +84.58%
slab_size                              256               256                 0      +0.00%
slabs                                1,913             2,544               631     +32.98%
slabs_cpu_partial                        0                 0                 0      +0.00%
store_user                               0                 0                 0      +0.00%
total_objects                      122,432           162,816            40,384     +32.98%
trace                                    0                 0                 0      +0.00%
usersize                                 0                 0                 0      +0.00%
Quoted 7 lines

derived before after change
=============================================================================================
page allocator churn (alloc_slab + free_slab) 20,341,607 9,591,131 -52.85%

As we can see from the data, barn_get and barn_put spike significantly, which shows a large part of the traffic is redirected into the barn. This eases slab alloc/free churn and cuts page allocator allocations/frees by 52.85%.

Cool!

Quoted 4 lines

All in all, I feel we could probably focus on evaluating and pursuing this experimental patch first. For maple tree performance specifically, it seems like it might be the better fit compared to the parking mechanism (which is probably better suited for generic allocation pressure outside of maple tree).

Sounds good.

Keeping eyes on seeing if we do (or don't) need the parking idea after this.

[ now moving on to the actual code... ]

Signature · 2 lines
Cheers,
Harry / Hyeonggon
author reviewer
#15 lore raw

Re: [RFC PATCH 1/2] mm/slub: make the case handling in __slab_free() easier to follow

In reply to Harry Yoo
Quoted 25 lines · Harry Yoo
Quoted 24 lines · Hao Li

There are 7 possible transitions in __slab_free():

a. partial->partial
b. partial->empty, offlist
c. partial->empty, onlist, exceeding min_partial d. partial->empty, onlist, not exceeding min_partial e. full->empty, exceeding min_partial
f. full->empty, not exceeding min_partial g. full->partial

(There is no offlist variant of e, f and g as a full slab is on no list.)

Clarify which case each branch handles, and replace the goto with a return at the end of the skipped block so that every branch explicitly states its coverage.

Case 'a' is the only path that needs neither list_lock nor list handling. Give it an early continue: handling it upfront is much clearer than forcing every other case into a nested block.

Also, read SL_partial once after the loop right where it is used, rather than re-reading it on every iteration.

Quoted 7 lines
Quoted 4 lines

No functional change.

---

Looks good to me (with Vlastimil's suggestions adjusted),

Thanks!

Quoted 12 lines
Quoted 9 lines
 mm/slub.c | 95 ++++++++++++++++++++++++++++---------------------------
 1 file changed, 49 insertions(+), 46 deletions(-)
mm/slub.c +0 -0
index b0cd0572e2f2..e20375307770 100644
@@ -5748,76 +5748,79 @@ static void __slab_free(struct kmem_cache *s, struct slab *slab,

[...]

Quoted 10 lines

mm/slub.c static void __slab_free(struct kmem_cache *s, struct slab *slab, · line 5767

Quoted 8 lines
mm/slub.c +8 -0
+		/*
+		 * The slab might need to be taken off (due to becoming empty)
+		 * or added to (due to not being full anymore) the partial
+		 * list.
+		 *
+		 * Speculatively acquire list_lock before calling cmpxchg(), as
+		 * performing cmpxchg() prior to lock acquisition races with
+		 * concurrent paths, such as the shrinker.

nit: it's bit weird to mention shrinkers specifically?

Yeah, better to remove it to be more generic.

Signature · 2 lines
Thanks,
Hao
author reviewer
#9 lore raw

Re: [RFC PATCH 2/2] mm/slub: introduce slab parking to reduce list_lock contention

In reply to Vlastimil Babka (SUSE)
Quoted 10 lines · Vlastimil Babka (SUSE)
Quoted 9 lines · Hao Li

--- >8 ---
mm/slub: refill prefilled sheaves from the barn

For evaluation.

---
 mm/slub.c | 118 +++++++++++++++++++++++++++++++++++++++++++++++++++---
 1 file changed, 112 insertions(+), 6 deletions(-)
Quoted 12 lines

mm/slub.c struct node_barn { · line 430

Quoted 9 lines
mm/slub.c +1 -0
index 27a78d63f537..7d337dbe26a5 100644
@@ -427,6 +427,8 @@ struct node_barn {
 	spinlock_t lock;
 	struct list_head sheaves_full;
 	struct list_head sheaves_empty;
+	/* leftovers of prefill or refill, protected by barn->lock */

All the fields are protected by the lock so I don't think it's worth pointing out specifically.

Yeah, make sense to me.

Quoted 2 lines

"prefill or refill" sounds like it may include also internal sheaf refill, which is not the case

Yeah, agreed, refill is a generic word, so I will remove the comment and let the code speak for itself.

Quoted 1 line

(but maybe something worth exploring later)

Yes! later we can see if partial_sheaf can have more use cases.

Quoted 29 lines
Quoted 29 lines
mm/slub.c +21 -0
+	struct slab_sheaf *sheaf_partial;
 	unsigned int nr_full;
 	unsigned int nr_empty;
 };
@@ -3183,6 +3185,69 @@ static struct slab_sheaf *barn_get_empty_sheaf(struct node_barn *barn,
 	return empty;
 }
 
+/*
+ * Exchange @sheaf, which holds fewer objects than requested, for a full sheaf
+ * from the barn. The objects of @sheaf stay in the barn: it becomes the barn's
+ * partial sheaf, or its objects are merged into the existing one, which becomes
+ * a full sheaf when it reaches capacity. That way the leftovers neither occupy
+ * a full-sheaf count nor have to be flushed.
+ *
+ * Returns NULL if the barn has no full sheaf.
+ */
+static struct slab_sheaf *barn_replace_partial_sheaf(struct kmem_cache *s,
+						     struct node_barn *barn,
+						     struct slab_sheaf *sheaf)
+{
+	struct slab_sheaf *full, *partial;
+	unsigned int to_move;
+	unsigned long flags;
+
+	if (!data_race(barn->nr_full))
+		return NULL;
+
Quoted 8 lines

mm/slub.c static struct slab_sheaf *barn_get_empty_sheaf(struct node_barn *barn, · line 3212

Quoted 5 lines
mm/slub.c +5 -0
+	spin_lock_irqsave(&barn->lock, flags);
+
+	if (unlikely(!barn->nr_full)) {
+		spin_unlock_irqrestore(&barn->lock, flags);
+		return NULL;

Hmm what if there's no full, but there's sheaf_partial with enough objects to make a full sheaf together with @sheaf?

This is very inspiring, thanks!

And I feel this doesn't just apply when barn->nr_full == 0. At any time, as long as the @sheaf and sheaf_partial together have enough objects to make a full sheaf, we can always complete a full sheaf out of the two and skip the barn list operations entirely.

This small optimization is essentially equivalent to what the current patch does, because the current code basically takes a full sheaf from the barn, then put the newly assembled full sheaf back into the barn, which is an unnecessary round trip.

On top of that, to be more efficient, we could compare their sizes first to make sure we always copy from the one with fewer objects to the one with more.

I ran a quick test, the performance and stats difference isn't very noticeable, but logically it feels much more elegant.

I'll roll this into a non-rfc patch and send it out later.

Quoted 30 lines
Quoted 30 lines
mm/slub.c +29 -0
+	}
+
+	full = list_first_entry(&barn->sheaves_full, struct slab_sheaf,
+				barn_list);
+	list_del(&full->barn_list);
+	barn->nr_full--;
+
+	partial = barn->sheaf_partial;
+	if (partial) {
+		to_move = min(sheaf->size, s->sheaf_capacity - partial->size);
+		sheaf->size -= to_move;
+		memcpy(&partial->objects[partial->size],
+		       &sheaf->objects[sheaf->size], to_move * sizeof(void *));
+		partial->size += to_move;
+
+		if (partial->size == s->sheaf_capacity) {
+			list_add(&partial->barn_list, &barn->sheaves_full);
+			barn->nr_full++;
+			barn->sheaf_partial = NULL;
+		}
+	}
+
+	if (sheaf->size) {
+		/* no partial sheaf, or it just became full */
+		barn->sheaf_partial = sheaf;
+	} else {
+		list_add(&sheaf->barn_list, &barn->sheaves_empty);
+		barn->nr_empty++;
+	}
Quoted 8 lines

mm/slub.c static struct slab_sheaf *barn_get_empty_sheaf(struct node_barn *barn, · line 3246

Quoted 5 lines
mm/slub.c +5 -0
+
+	spin_unlock_irqrestore(&barn->lock, flags);
+
+	full->capacity = s->sheaf_capacity;
+	full->pfmemalloc = false;

I think this belongs more to the caller which deals with the prefilled sheaves specifically, and this helper is more low level.

Makes sense to me! will do.

Quoted 2 lines

Otherwise LGTM!

Awesome, thanks!

Quoted 112 lines
Quoted 111 lines
mm/slub.c +51 -6
+
+	return full;
+}
+
 /*
  * The following two functions are used mainly in cases where we have to undo an
  * intended action due to a race or cpu migration. Thus they do not check the
@@ -3317,6 +3382,7 @@ 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->sheaf_partial = NULL;
 	barn->nr_full = 0;
 	barn->nr_empty = 0;
 }
@@ -3334,6 +3400,10 @@ static void barn_shrink(struct kmem_cache *s, struct node_barn *barn)
 	barn->nr_full = 0;
 	list_splice_init(&barn->sheaves_empty, &empty_list);
 	barn->nr_empty = 0;
+	if (barn->sheaf_partial) {
+		list_add(&barn->sheaf_partial->barn_list, &full_list);
+		barn->sheaf_partial = NULL;
+	}
 
 	spin_unlock_irqrestore(&barn->lock, flags);
 
@@ -5233,12 +5303,49 @@ void *kmem_cache_alloc_node_noprof(struct kmem_cache *s, gfp_t gfpflags, int nod
 }
 EXPORT_SYMBOL(kmem_cache_alloc_node_noprof);
 
+/*
+ * Refill by swapping *@sheafp for a full sheaf from the barn. The old sheaf and
+ * its objects stay in the barn. Returns true when the new sheaf is full.
+ */
+static bool refill_sheaf_from_barn(struct kmem_cache *s,
+				   struct slab_sheaf **sheafp)
+{
+	struct node_barn *barn = get_barn(s);
+	struct slab_sheaf *sheaf = *sheafp;
+	struct slab_sheaf *full;
+
+	/* objects from pfmemalloc slabs must not enter the barn */
+	if (!barn || sheaf->pfmemalloc)
+		return false;
+
+	full = barn_replace_partial_sheaf(s, barn, sheaf);
+	if (!full)
+		return false;
+
+	stat(s, BARN_GET);
+	*sheafp = full;
+
+	/*
+	 * The sheaf may hold fewer than capacity objects: rcu_free_sheaf()
+	 * puts it in the barn as full even when slab_free_hook() has taken
+	 * some out (KFENCE, KASAN). __prefill_sheaf_pfmemalloc() then
+	 * continues to refill it.
+	 */
+	return full->size == s->sheaf_capacity;
+}
+
 static int __prefill_sheaf_pfmemalloc(struct kmem_cache *s,
-				      struct slab_sheaf *sheaf, gfp_t gfp)
+				      struct slab_sheaf **sheafp, gfp_t gfp)
 {
+	struct slab_sheaf *sheaf;
 	gfp_t gfp_nomemalloc;
 	int ret;
 
+	if (refill_sheaf_from_barn(s, sheafp))
+		return 0;
+
+	sheaf = *sheafp;
+
 	gfp_nomemalloc = gfp | __GFP_NOMEMALLOC;
 	if (gfp_pfmemalloc_allowed(gfp))
 		gfp_nomemalloc |= __GFP_NOWARN;
@@ -5331,7 +5438,7 @@ kmem_cache_prefill_sheaf(struct kmem_cache *s, gfp_t gfp, unsigned int size)
 		sheaf->pfmemalloc = false;
 
 		if (sheaf->size < size &&
-		    __prefill_sheaf_pfmemalloc(s, sheaf, gfp)) {
+		    __prefill_sheaf_pfmemalloc(s, &sheaf, gfp)) {
 			sheaf_flush_unused(s, sheaf);
 			free_empty_sheaf(s, sheaf);
 			sheaf = NULL;
@@ -5401,11 +5508,10 @@ void kmem_cache_return_sheaf(struct kmem_cache *s, gfp_t gfp,
  * the given size.
  *
  * Return: 0 on success. The sheaf will contain at least @size objects.
- * The sheaf might have been replaced with a new one if more than
- * sheaf->capacity objects are requested.
+ * The sheaf might have been replaced with a new one.
  *
  * Return: -ENOMEM on failure. Some objects might have been added to the sheaf
- * but the sheaf will not be replaced.
+ * and the sheaf might have been replaced.
  *
  * In practice we always refill to full sheaf's capacity.
  */
@@ -5427,7 +5533,7 @@ int kmem_cache_refill_sheaf(struct kmem_cache *s, gfp_t gfp,
 
 	if (likely(sheaf->capacity >= size)) {
 		if (likely(sheaf->capacity == s->sheaf_capacity))
-			return __prefill_sheaf_pfmemalloc(s, sheaf, gfp);
+			return __prefill_sheaf_pfmemalloc(s, sheafp, gfp);
 
 		if (!__kmem_cache_alloc_bulk(s, gfp, sheaf->capacity - sheaf->size,
 					     &sheaf->objects[sheaf->size]))
author reviewer
#11 lore raw

Re: [RFC PATCH 2/2] mm/slub: introduce slab parking to reduce list_lock contention

In reply to Harry Yoo
Quoted 1 line · Harry Yoo

Apologies for chiming in late, trying to catch up...

No worries at all, thanks for taking a look!

Quoted 15 lines · Hao Li
Quoted 13 lines · Vlastimil Babka (SUSE)
Quoted 1 line · Hao Li

Thanks for pointing this out. I looked into this bursty alloc-and-free behavior a bit deeper and ran some further experiments.

The core question we want to answer is: why does such a massive volume of object allocations and frees fall straight through to the node partial list layer, rather than being caught and handled at the barn/sheaf layer? In SLUB's current design, the per-CPU main/spare sheaves act as the L1 cache, the barn as L2, and the node partial list as L3. For the mmap1 benchmark (which heavily stresses the maple tree), the allocation path uses kmem_cache_prefill_sheaf() rather than the generic allocation APIs, and the frees go through kfree_rcu().

Quoted 6 lines
Quoted 4 lines

Then, here is what happens during allocation: kmem_cache_prefill_sheaf() normally borrows the spare sheaf directly. If the sheaf holds fewer objects than requested, it refills it to capacity from the node partial list layer and this completely bypasses the barn layer.

Nice observation, Hao!

Thanks, Harry!

Quoted 22 lines
Quoted 6 lines

Once the maple tree finishes
allocating a batch of objects, it returns the sheaf back to pcs->spare via kmem_cache_return_sheaf(). So in essence, this prefill path is just funneling objects directly from the node partial list into the maple tree through the spare sheaf. It skips the barn layer.

Nice observation.

Quoted 6 lines

Then on the free side: these objects are freed via kfree_rcu, and then rcu_free_sheaf() checks if there is still room on the barn's full list. But since the allocation path never actually pulled from the barn, the full list stays permanently saturated. As a result, rcu_free_sheaf() always falls back to sheaf_flush_unused(), flushing objects straight into the node partial list layer. It skips the barn layer too.

Nice observation.

Quoted 3 lines

So looking at this behavior, the benchmark does seem to reveal a gap in this allocation path, where a huge amount of traffic ends up bypassing the barn layer entirely.

Quoted 5 lines

Indeed.

So, either refilling or flushing partial sheaves bypasses the barn layer. This is particularly a problem for prefilled sheaf users because they perform refills and flushes more frequently.

Exactly!

Quoted 3 lines

Partial sheaves serve alloc and free for ordinary users, but often times that's not the case for prefilled sheaf users.

Yes, prefill is special.

Quoted 19 lines
Quoted 19 lines

To see if we can address this, I draft an experimental patch. It introduces a new field, barn->sheaf_partial, which is a single sheaf rather than a list.

[The patch code is included at the end of this email.]

Whenever kmem_cache_prefill_sheaf() runs, it detaches pcs->spare and checks whether it holds enough objects for the request.

If so, it returns it right away as in the original code.

If not, call __prefill_sheaf_pfmemalloc() and then go into barn_replace_partial_sheaf() to swap the non-full spare sheaf with a full sheaf from the barn. The full sheaf is handed to the caller, while the non-full sheaf is temporarily stashed into barn->sheaf_partial. This largely avoids falling back to the node partial list. If barn->sheaf_partial already has a sheaf, we merge them together, and any resulting full or empty sheaves are placed back into the barn accordingly.

Quoted 7 lines
Quoted 3 lines

The key idea here is simply to let __prefill_sheaf_pfmemalloc() pull a sheaf from the barn's full list, which makes room on the list for future rcu_free_sheaf() calls.

And the idea is to provide a place for a partial sheaf to say to avoid flushing and refilling it, and which helps avoiding bypassing the barn layer.

Yes.

Quoted 3 lines

The reason why we don't need a list of partial sheaves because we want to merge them and move the partial sheaf to full or empty list.

Right, and a single partial sheaf is lightweight and sufficient.

Quoted 2 lines

Makes sense to me :-)

Awesome, thanks!

Quoted 78 lines
Quoted 63 lines

Here are the numbers with just this experimental patch applied (without the parking patch):

baseline: 28779879
after experimental patch: 35550211 (+23.5%)

metric before after delta change
=============================================================================================

aliases                                  0                 0                 0      +0.00%
align                                  256               256                 0      +0.00%

alloc_fastpath 23,259 59,287 36,028 +154.90%
alloc_node_mismatch 0 0 0 +0.00%
alloc_slab 10,171,378 4,796,346 -5,375,032 -52.84%
alloc_slowpath 0 0 0 +0.00%
barn_get 441 193,807,528 193,807,087 +43947185.26%
barn_get_fail 0 377 377 new
barn_put 441 181,694,607 181,694,166 +41200491.16%
barn_put_fail 272,868,220 156,335,632 -116,532,588 -42.71%
cache_dma 0 0 0 +0.00%
cmpxchg_double_fail 744,975 357,255 -387,720 -52.04%

cpu_partial                              0                 0                 0      +0.00%
cpu_slabs                                0                 0                 0      +0.00%
destroy_by_rcu                           0                 0                 0      +0.00%

free_add_partial 337,390,126 162,178,648 -175,211,478 -51.93%
free_fastpath 5,204 14,081 8,877 +170.58%
free_rcu_sheaf 8,731,794,372 10,816,953,777 2,085,159,405 +23.88%
free_rcu_sheaf_fail 0 0 0 +0.00%

free_remove_partial             10,170,229         4,794,785        -5,375,444     -52.85%
free_slab                       10,170,229         4,794,785        -5,375,444     -52.85%
free_slowpath                   18,697,056        11,563,127        -7,133,929     -38.16%
hwcache_align                            0                 0                 0      +0.00%
min_partial                              5                 5                 0      +0.00%
object_size                            256               256                 0      +0.00%
objects                             14,774            14,596              -178      -1.20%
objects_partial                     14,774            14,596              -178      -1.20%
objs_per_slab                           64                64                 0      +0.00%
order                                    2                 2                 0      +0.00%
order_fallback                           0                 0                 0      +0.00%
partial                              1,913             2,544               631     +32.98%
poison                                   0                 0                 0      +0.00%
reclaim_account                          0                 0                 0      +0.00%
red_zone                                 0                 0                 0      +0.00%
remote_node_defrag_ratio               100               100                 0      +0.00%
sanity_checks                            0                 0                 0      +0.00%
sheaf_alloc                    145,870,437       151,536,660         5,666,223      +3.88%
sheaf_capacity                          32                32                 0      +0.00%

sheaf_flush 8,731,787,311 5,002,740,743 -3,729,046,568 -42.71%
sheaf_free 145,870,431 151,536,655 5,666,224 +3.88%
sheaf_prefill_fast 3,500,187,266 4,331,383,393 831,196,127 +23.75%
sheaf_prefill_oversize 0 0 0 +0.00%
sheaf_prefill_slow 322 646 324 +100.62%

sheaf_refill                 8,750,484,664     5,014,304,944    -3,736,179,720     -42.70%
sheaf_return_fast            3,500,187,348     4,331,383,596       831,196,248     +23.75%
sheaf_return_slow                      240               443               203     +84.58%
slab_size                              256               256                 0      +0.00%
slabs                                1,913             2,544               631     +32.98%
slabs_cpu_partial                        0                 0                 0      +0.00%
store_user                               0                 0                 0      +0.00%
total_objects                      122,432           162,816            40,384     +32.98%
trace                                    0                 0                 0      +0.00%
usersize                                 0                 0                 0      +0.00%
Quoted 7 lines

derived before after change
=============================================================================================
page allocator churn (alloc_slab + free_slab) 20,341,607 9,591,131 -52.85%

As we can see from the data, barn_get and barn_put spike significantly, which shows a large part of the traffic is redirected into the barn. This eases slab alloc/free churn and cuts page allocator allocations/frees by 52.85%.

Cool!

Quoted 4 lines

All in all, I feel we could probably focus on evaluating and pursuing this experimental patch first. For maple tree performance specifically, it seems like it might be the better fit compared to the parking mechanism (which is probably better suited for generic allocation pressure outside of maple tree).

Quoted 4 lines

Sounds good.

Keeping eyes on seeing if we do (or don't) need the parking idea after this.

Yeah, we can always revisit it if needed.

Quoted 2 lines

[ now moving on to the actual code... ]

Thanks, and formal patch will follow later.