[RFC PATCH] mm/slub: barn sheaf counts can exceed their limit

[RFC PATCH] mm/slub: barn sheaf counts can exceed their limit

[Junseo Lim]

Hello,

Following the suggestion to discuss this publicly, I would like to
report a repeatable overshoot of the SLUB barn limits. Although
MAX_FULL_SHEAVES and MAX_EMPTY_SHEAVES are both 10, a userspace workload
can repeatedly trigger the refill recovery path. In one run, I observed
states like nr_full=91.

I would appreciate feedback on the appropriate way to enforce these
limits.

Description
-----------

While the sheaf layer provides a simple array structure for
amortization, the edge cases that involve refills and allocating
structures are inherently complex when combined with multiple threads.
One problematic case occurs in the allocation path. Consider a state
where every object is drained and TH1 on CPU1 is running:

  CPU1
  =======================================================================
  TH1                    TH2                    TH3
  ---------------------  ---------------------  --------------------- ...
  pcs->main->size=0      not entered            not entered
  pcs->spare->size=0
  nr_full=0 nr_empty=10

    <observed states>      <observed states>      <observed states>

If an allocation request hits this state, __pcs_replace_empty_main is
called to retrieve a full sheaf and swap it with main. However, no full
sheaf is available in the barn, so TH1 removes pcs->spare, sets it to
NULL, and refills the removed sheaf through the slow path. Here, the
per-CPU sheaf lock is released during refill and reacquired afterward.
If preemption occurs during this period, a subsequent thread (TH2) sees
pcs->spare=NULL and tries to get a remaining sheaf from the barn's empty
list and refill it. Likewise, this part is not protected by the lock.
Chaining this results in a state where new threads keep draining the
sheaf and ultimately consume all the empty sheaves in the barn and start
to allocate new sheaves.

  CPU1
  =======================================================================
  TH1 (preempted)        TH2 (preempted)        TH3
  ---------------------  ---------------------  --------------------- ...
  pcs->main->size=0      pcs->main->size=0      pcs->main->size=0
  pcs->spare->size=0     pcs->spare=NULL        pcs->spare=NULL
  nr_full=0 nr_empty=10  nr_full=0 nr_empty=10  nr_full=0 nr_empty=9

    <observed states>      <observed states>      <observed states>

The construction of the sheaf layer allows such racy scenarios, as
mentioned in the comments. Nevertheless, this overshoot is much larger
than what we would expect, and the fact that this state can be recreated
with moderate effort implies that a fix would be appropriate.

Impact
------

This itself does not pose a direct threat or system failure. But, in a
security sense, this behavior can be leveraged for heap grooming that
targets the underlying slab_sheaf.

Design considerations and Question
----------------------------------

One way to limit barn overshoot is to constrain the racy allocations.
Simply using the current nr_full and nr_empty values does not help in
detecting excessive allocation. What I came up with is adding an
nr_alloc counter that keeps track of allocations during the unlocked
path. From what I've tested, this restricted the targeted workload that
induces the excessive allocation. Before this patch, nr_full reached 60
to 90. After the patch, it remained at 22 under the adversarial
workload.

I haven't checked every possible interleaving yet, but I would like to
know whether you think this is the right direction. The possible
regressions are that it requires an additional field just to track the
adversarial input and that, in a highly contended scenario, every
allocation after hitting the nr_alloc limit will go to the slow path
until the preempted task returns and continues the allocation.

Is tracking in-flight sheaf allocations per barn, and falling back when
too many are in progress, the right way to limit this refill race?

Note: This is only an implementation on the allocation side and is still
a prototype.

---
 mm/slub.c | 34 +++++++++++++++++++++++++++++-----
 1 file changed, 29 insertions(+), 5 deletions(-)

diff --git a/mm/slub.c b/mm/slub.c
index 45e077c7526c..472fcae4ac91 100644
--- a/mm/slub.c
+++ b/mm/slub.c
@@ -456,6 +456,7 @@ struct node_barn {
 	struct slab_sheaf *sheaf_partial;
 	unsigned int nr_full;
 	unsigned int nr_empty;
+	unsigned int nr_alloc;
 };
 
 struct slab_sheaf {
@@ -3333,6 +3334,7 @@ static void barn_init(struct node_barn *barn)
 	barn->sheaf_partial = NULL;
 	barn->nr_full = 0;
 	barn->nr_empty = 0;
+	barn->nr_alloc = 0;
 }
 
 static void barn_shrink(struct kmem_cache *s, struct node_barn *barn)
@@ -4754,7 +4756,9 @@ __pcs_replace_empty_main(struct kmem_cache *s, struct slub_percpu_sheaves *pcs,
 	struct slab_sheaf *empty = NULL;
 	struct slab_sheaf *full;
 	struct node_barn *barn;
+	unsigned long flags;
 	bool allow_spin;
+	bool alloc_new = false;
 
 	slab_lockdep_assert_held(this_cpu_ptr(&s->cpu_sheaves->lock));
 
@@ -4796,6 +4800,19 @@ __pcs_replace_empty_main(struct kmem_cache *s, struct slub_percpu_sheaves *pcs,
 		}
 	}
 
+	if (allow_spin && !empty) {
+		/* The limit is advisory; concurrent reservations may exceed it. */
+		if (data_race(barn->nr_alloc) > MAX_EMPTY_SHEAVES) {
+			local_unlock(&s->cpu_sheaves->lock);
+			return NULL;
+		}
+
+		spin_lock_irqsave(&barn->lock, flags);
+		barn->nr_alloc++;
+		spin_unlock_irqrestore(&barn->lock, flags);
+		alloc_new = true;
+	}
+
 	local_unlock(&s->cpu_sheaves->lock);
 	pcs = NULL;
 
@@ -4805,7 +4822,7 @@ __pcs_replace_empty_main(struct kmem_cache *s, struct slub_percpu_sheaves *pcs,
 	if (!empty) {
 		empty = alloc_empty_sheaf(s, gfp, alloc_flags);
 		if (!empty)
-			return NULL;
+			goto out;
 	}
 
 	if (refill_sheaf(s, empty, gfp | __GFP_NOMEMALLOC | __GFP_NOWARN)) {
@@ -4816,7 +4833,7 @@ __pcs_replace_empty_main(struct kmem_cache *s, struct slub_percpu_sheaves *pcs,
 		sheaf_flush_unused(s, empty);
 		free_empty_sheaf(s, empty);
 
-		return NULL;
+		goto out;
 	}
 
 	full = empty;
@@ -4839,24 +4856,31 @@ __pcs_replace_empty_main(struct kmem_cache *s, struct slub_percpu_sheaves *pcs,
 		else
 			barn_put_empty_sheaf(barn, pcs->main);
 		pcs->main = full;
-		return pcs;
+		goto out;
 	}
 
 	if (!pcs->spare) {
 		pcs->spare = full;
-		return pcs;
+		goto out;
 	}
 
 	if (pcs->spare->size == 0) {
 		barn_put_empty_sheaf(barn, pcs->spare);
 		pcs->spare = full;
-		return pcs;
+		goto out;
 	}
 
 barn_put:
 	barn_put_full_sheaf(barn, full);
 	stat(s, BARN_PUT);
 
+out:
+	if (alloc_new) {
+		spin_lock_irqsave(&barn->lock, flags);
+		barn->nr_alloc--;
+		spin_unlock_irqrestore(&barn->lock, flags);
+	}
+
 	return pcs;
 }
 
-- 
2.56.0

Re: [RFC PATCH] mm/slub: barn sheaf counts can exceed their limit

[sashiko-bot]

Thank you for your contribution! Sashiko AI review found 5 potential
issues to consider:
- [High] mm/slub: missing Signed-off-by trailer and RFC email body in
  commit message
- [Medium] mm/slub: unbounded barn sheaf growth across refill waves in
  __pcs_replace_empty_main()
- [Low] mm/slub: off-by-one and unlocked check on barn->nr_alloc in
  __pcs_replace_empty_main()
- [Low] mm/slub: redundant back-to-back barn->lock acquisitions in
  __pcs_replace_empty_main()
- [Low] mm/slub: missing Fixes trailer for commit 2d517aa09bbc in commit
  message
--

commit 4002c32d0ca36a2bf13b1261531aaa78aeae34dc
Author: Junseo Lim <zirajs7@gmail.com>

> mm/slub: barn sheaf counts can exceed their limit
>
> Hello,
>
> Following the suggestion to discuss this publicly, I would like to
> report a repeatable overshoot of the SLUB barn limits. Although
> MAX_FULL_SHEAVES and MAX_EMPTY_SHEAVES are both 10, a userspace workload
> can repeatedly trigger the refill recovery path. In one run, I observed
> states like nr_full=91.
>
> I would appreciate feedback on the appropriate way to enforce these
> limits.
>
> Description
> -----------
>
> While the sheaf layer provides a simple array structure for
> amortization, the edge cases that involve refills and allocating
> structures are inherently complex when combined with multiple threads.
> One problematic case occurs in the allocation path. Consider a state
> where every object is drained and TH1 on CPU1 is running:
>
>   CPU1
>   =======================================================================
>   TH1                    TH2                    TH3
>   ---------------------  ---------------------  --------------------- ...
>   pcs->main->size=0      not entered            not entered
>   pcs->spare->size=0
>   nr_full=0 nr_empty=10
>
>     <observed states>      <observed states>      <observed states>
>
> If an allocation request hits this state, __pcs_replace_empty_main is
> called to retrieve a full sheaf and swap it with main. However, no full
> sheaf is available in the barn, so TH1 removes pcs->spare, sets it to
> NULL, and refills the removed sheaf through the slow path. Here, the
> per-CPU sheaf lock is released during refill and reacquired afterward.
> If preemption occurs during this period, a subsequent thread (TH2) sees
> pcs->spare=NULL and tries to get a remaining sheaf from the barn's empty
> list and refill it. Likewise, this part is not protected by the lock.
> Chaining this results in a state where new threads keep draining the
> sheaf and ultimately consume all the empty sheaves in the barn and start
> to allocate new sheaves.
>
>   CPU1
>   =======================================================================
>   TH1 (preempted)        TH2 (preempted)        TH3
>   ---------------------  ---------------------  --------------------- ...
>   pcs->main->size=0      pcs->main->size=0      pcs->main->size=0
>   pcs->spare->size=0     pcs->spare=NULL        pcs->spare=NULL
>   nr_full=0 nr_empty=10  nr_full=0 nr_empty=10  nr_full=0 nr_empty=9
>
>     <observed states>      <observed states>      <observed states>
>
> The construction of the sheaf layer allows such racy scenarios, as
> mentioned in the comments. Nevertheless, this overshoot is much larger
> than what we would expect, and the fact that this state can be recreated
> with moderate effort implies that a fix would be appropriate.
>
> Impact
> ------
>
> This itself does not pose a direct threat or system failure. But, in a
> security sense, this behavior can be leveraged for heap grooming that
> targets the underlying slab_sheaf.
>
> Design considerations and Question
> ----------------------------------
>
> One way to limit barn overshoot is to constrain the racy allocations.
> Simply using the current nr_full and nr_empty values does not help in
> detecting excessive allocation. What I came up with is adding an
> nr_alloc counter that keeps track of allocations during the unlocked
> path. From what I've tested, this restricted the targeted workload that
> induces the excessive allocation. Before this patch, nr_full reached 60
> to 90. After the patch, it remained at 22 under the adversarial
> workload.
>
> I haven't checked every possible interleaving yet, but I would like to
> know whether you think this is the right direction. The possible
> regressions are that it requires an additional field just to track the
> adversarial input and that, in a highly contended scenario, every
> allocation after hitting the nr_alloc limit will go to the slow path
> until the preempted task returns and continues the allocation.
>
> Is tracking in-flight sheaf allocations per barn, and falling back when
> too many are in progress, the right way to limit this refill race?
>
> Note: This is only an implementation on the allocation side and is still
> a prototype.

[Severity: High]
This commit is missing a Signed-off-by: trailer, and the commit message is
formatted as a mailing-list question rather than a changelog entry (any
discussion or prototype notes belong below the --- line).

[Severity: Low]
Should this commit include a Fixes: tag for the commit that introduced
per-CPU sheaves and __pcs_replace_empty_main()?

  Fixes: 2d517aa09bbc ("slab: add opt-in caching layer of percpu sheaves")

> diff --git a/mm/slub.c b/mm/slub.c
> index a151268b97263..7076902509ed3 100644
> --- a/mm/slub.c
> +++ b/mm/slub.c

[ ... ]

> @@ -4798,6 +4802,19 @@ __pcs_replace_empty_main(struct kmem_cache *s, struct slub_percpu_sheaves *pcs,
>  		}
>  	}
>  
> +	if (allow_spin && !empty) {
> +		/* The limit is advisory; concurrent reservations may exceed it. */
> +		if (data_race(barn->nr_alloc) > MAX_EMPTY_SHEAVES) {
> +			local_unlock(&s->cpu_sheaves->lock);
> +			return NULL;
> +		}
> +
> +		spin_lock_irqsave(&barn->lock, flags);
> +		barn->nr_alloc++;
> +		spin_unlock_irqrestore(&barn->lock, flags);
> +		alloc_new = true;
> +	}

[Severity: Low]
Should this check be >= MAX_EMPTY_SHEAVES, and rechecked after acquiring
barn->lock?  Starting from barn->nr_alloc == 0, checking > MAX_EMPTY_SHEAVES
allows MAX_EMPTY_SHEAVES + 1 (11) concurrent allocations rather than
MAX_EMPTY_SHEAVES (10), and threads on other CPUs that pass the unlocked
check before taking barn->lock will still increment barn->nr_alloc past the
limit.

[ ... ]

> @@ -4841,24 +4858,31 @@ __pcs_replace_empty_main(struct kmem_cache *s, struct slub_percpu_sheaves *pcs,
>  		else
>  			barn_put_empty_sheaf(barn, pcs->main);
>  		pcs->main = full;
> -		return pcs;
> +		goto out;
>  	}
>  
>  	if (!pcs->spare) {
>  		pcs->spare = full;
> -		return pcs;
> +		goto out;
>  	}
>  
>  	if (pcs->spare->size == 0) {
>  		barn_put_empty_sheaf(barn, pcs->spare);
>  		pcs->spare = full;
> -		return pcs;
> +		goto out;
>  	}
>  
>  barn_put:
>  	barn_put_full_sheaf(barn, full);
>  	stat(s, BARN_PUT);
>  
> +out:
> +	if (alloc_new) {
> +		spin_lock_irqsave(&barn->lock, flags);
> +		barn->nr_alloc--;
> +		spin_unlock_irqrestore(&barn->lock, flags);
> +	}
> +
>  	return pcs;
>  }

[Severity: Medium]
Can barn->nr_full and barn->nr_empty still grow without bound across
repeated drain-and-refill waves?

barn->nr_alloc is only checked and incremented when !empty (after
pcs->spare and barn->sheaves_empty are already exhausted), and is
decremented back to 0 at out: as soon as __pcs_replace_empty_main()
finishes.  When a wave of threads allocates new sheaves via
alloc_empty_sheaf(), any excess sheaves are placed into the barn by
barn_put_full_sheaf() or barn_put_empty_sheaf() without checking
MAX_FULL_SHEAVES or MAX_EMPTY_SHEAVES, while barn->nr_alloc returns to 0.
As subsequent allocations consume those full sheaves via
barn_replace_empty_sheaf(), they are swapped onto barn->sheaves_empty
without checking MAX_EMPTY_SHEAVES:

mm/slub.c:barn_replace_empty_sheaf() {
    ...
	if (likely(barn->nr_full)) {
		full = list_first_entry(&barn->sheaves_full, struct slab_sheaf,
					barn_list);
		list_del(&full->barn_list);
		list_add(&empty->barn_list, &barn->sheaves_empty);
		barn->nr_full--;
		barn->nr_empty++;
	}
    ...
}

In the next preemption wave, threads pull all of those accumulated empty
sheaves via barn_get_empty_sheaf() with empty != NULL (leaving
barn->nr_alloc at 0 while preempted in refill_sheaf()), and once
barn->nr_empty hits 0 again, another wave sees empty == NULL and
barn->nr_alloc == 0 and allocates another batch of MAX_EMPTY_SHEAVES + 1
sheaves.  Meanwhile, on a NUMA node with more than 11 CPUs warming up a
cold cache, capping per-node in-flight allocations at MAX_EMPTY_SHEAVES
forces concurrent allocations on other CPUs onto the ___slab_alloc()
slowpath even when no preemption race occurs.  Enforcing MAX_FULL_SHEAVES
and MAX_EMPTY_SHEAVES when returning excess sheaves to the barn (and
flushing and freeing any excess via sheaf_flush_unused() and
free_empty_sheaf(), as rcu_free_sheaf() and kmem_cache_return_sheaf() do)
would bound the barn directly without throttling cold-cache allocations.

[Severity: Low]
Does this acquire and release barn->lock back-to-back on the recovery
paths?  When alloc_new is true and __pcs_replace_empty_main() calls
barn_put_empty_sheaf() or barn_put_full_sheaf(), those helpers take and
drop barn->lock, and the out: label immediately takes and drops barn->lock
again under s->cpu_sheaves->lock just to decrement barn->nr_alloc (which is
only ever read via data_race()).

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/20261111142337.748120-1-zirajs7@gmail.com?part=1