SLUB percpu array caches and maple tree nodes
Subsystems (6)
v2 cover SLUB percpu array caches and maple tree nodes
Also in git [1]. Changes since v1 [2]:
- fix a few bugs
- SLAB marked as BROKEN so bots dont complain about missing functions
- incorporate Liam's patches, which allows getting rid of preallocations in mas_prealloc() completely. This has reduced the allocation stats further, with the whole series.
More notes wrt v1 RFC feedback:
- locking is still done as in v1, as it allows remote draining, which should be added before this is suitable for merging
- there's currently no bulk freeing/refill of the percpu array, which will eventually be added, but I expect most perf gain for the maple tree use case to come from the avoided preallocations anyway
----
At LSF/MM I've mentioned that I see several use cases for introducing opt-in percpu arrays for caching alloc/free objects in SLUB. This is my first exploration of this idea, speficially for the use case of maple tree nodes. We have brainstormed this use case on IRC last week with Liam and Matthew and this how I understood the requirements:
- percpu arrays will be faster thank bulk alloc/free which needs relatively long freelists to work well. Especially in the freeing case we need the nodes to come from the same slab (or small set of those)
- preallocation for the worst case of needed nodes for a tree operation that can't reclaim due to locks is wasteful. We could instead expect that most of the time percpu arrays would satisfy the constained allocations, and in the rare cases it does not we can dip into GFP_ATOMIC reserves temporarily. Instead of preallocation just prefill the arrays.
- NUMA locality is not a concern as the nodes of a process's VMA tree end up all over the place anyway.
So this RFC patchset adds such percpu array in Patch 2. Locking is stolen from Mel's recent page allocator's pcplists implementation so it can avoid disabling IRQs and just disable preemption, but the trylocks can fail in rare situations.
Then maple tree is modified in patches 3-6 to benefit from this. This is done in a very crude way as I'm not so familiar with the code.
I've briefly tested this with virtme VM boot and checking the stats from CONFIG_SLUB_STATS in sysfs.
Patch 2:
slub changes implemented including new counters alloc_cpu_cache and free_cpu_cache but maple tree doesn't use them yet
(none):/sys/kernel/slab/maple_node # grep . alloc_cpu_cache alloc_*path free_cpu_cache free_*path | cut -d' ' -f1 alloc_cpu_cache:0
alloc_fastpath:54842
alloc_slowpath:8142
free_cpu_cache:0
free_fastpath:32336
free_slowpath:23484
Patch 3:
maple node cache creates percpu array with 32 entries, not changed anything else
-> some allocs/free satisfied by the array
alloc_cpu_cache:11956
alloc_fastpath:40675
alloc_slowpath:7308
free_cpu_cache:12082
free_fastpath:23617
free_slowpath:17956
Patch 4:
maple tree nodes bulk alloc/free converted to loop of normal alloc to use percpu array more, because bulk alloc bypasses it
-> majority alloc/free now satisfied by percpu array
alloc_cpu_cache:54673
alloc_fastpath:4491
alloc_slowpath:737
free_cpu_cache:54759
free_fastpath:332
free_slowpath:4723
Patch 5+6:
mas_preallocate() just prefills the percpu array, doesn't preallocate anything mas_store_prealloc() gains a retry loop with mas_nomem(mas, GFP_ATOMIC | __GFP_NOFAIL)
-> major drop of alloc/free
(the prefills are included in the accounting)
alloc_cpu_cache:15036
alloc_fastpath:4651
alloc_slowpath:656
free_cpu_cache:15102
free_fastpath:299
free_slowpath:4835
It would be interesting to see how it affects the workloads that saw regressions from the maple tree introduction, as the slab operations were suspected to be a major factor and now they should be both reduced and made cheaper.
Liam R. Howlett (2):
maple_tree: Remove MA_STATE_PREALLOC
tools: Add SLUB percpu array functions for testing
Vlastimil Babka (5):
mm, slub: fix bulk alloc and free stats
mm, slub: add opt-in slub_percpu_array
maple_tree: use slub percpu array
maple_tree: avoid bulk alloc/free to use percpu array more
maple_tree: replace preallocation with slub percpu array prefill
include/linux/slab.h | 4 + include/linux/slub_def.h | 10 ++ lib/maple_tree.c | 60 ++++--- mm/Kconfig | 1 + mm/slub.c | 221 +++++++++++++++++++++++- tools/include/linux/slab.h | 4 + tools/testing/radix-tree/linux.c | 14 ++ tools/testing/radix-tree/linux/kernel.h | 1 + 8 files changed, 286 insertions(+), 29 deletions(-)
Signature · 1 line
2.41.0
RFC v2 1/7 mm, slub: fix bulk alloc and free stats
The SLUB sysfs stats enabled CONFIG_SLUB_STATS have two deficiencies identified wrt bulk alloc/free operations:
- Bulk allocations from cpu freelist are not counted. Add the ALLOC_FASTPATH counter there.
- Bulk fastpath freeing will count a list of multiple objects with a single FREE_FASTPATH inc. Add a stat_add() variant to count them all.
--- mm/slub.c | 11 ++++++++++- 1 file changed, 10 insertions(+), 1 deletion(-)
mm/slub.c +10 -1
@@ -341,6 +341,14 @@ static inline void stat(const struct kmem_cache *s, enum stat_item si)#endif } +static inline void stat_add (const struct kmem_cache *s,enum stat_item si,int v) +{ +#ifdef CONFIG_SLUB_STATS +raw_cpu_add (s->cpu_slab->stat[si], v); +#endif +} + +/* * Tracks for which NUMA nodes we have kmem_cache_nodes allocated. * Corresponds to node_state[N_NORMAL_MEMORY], but can temporarily
@@ -3776,7 +3784,7 @@ static __always_inline void do_slab_free(struct kmem_cache *s, local_unlock(&s->cpu_slab->lock); } -stat (s,FREE_FASTPATH ); +stat_add (s,FREE_FASTPATH , cnt); }#else /* CONFIG_SLUB_TINY */ static void do_slab_free(struct kmem_cache *s,
@@ -3978,6 +3986,7 @@ static inline int __kmem_cache_alloc_bulk(struct kmem_cache *s, gfp_t flags, c->freelist =get_freepointer (s, object); p[i] = object;maybe_wipe_obj_freeptr (s, p[i]); +stat (s,ALLOC_FASTPATH ); } c->tid =next_tid (c->tid);local_unlock_irqrestore (&s->cpu_slab->lock, irqflags);
Signature · 1 line
2.41.0
RFC v2 2/7 mm, slub: add opt-in slub_percpu_array
In reply to Vlastimil Babkakmem_cache_setup_percpu_array() will allocate a per-cpu array for caching alloc/free objects of given size for the cache. The cache has to be created with SLAB_NO_MERGE flag.
The array is filled by freeing. When empty for alloc or full for freeing, it's simply bypassed by the operation, there's currently no batch freeing/allocations.
The locking is copied from the page allocator's pcplists, based on embedded spin locks. Interrupts are not disabled, only preemption (cpu migration on RT). Trylock is attempted to avoid deadlock due to an intnerrupt, trylock failure means the array is bypassed.
Sysfs stat counters alloc_cpu_cache and free_cpu_cache count operations that used the percpu array.
Bulk allocation bypasses the array, bulk freeing does not.
kmem_cache_prefill_percpu_array() can be called to ensure the array on the current cpu to at least the given number of objects. However this is only opportunistic as there's no cpu pinning and the trylocks may always fail. Therefore allocations cannot rely on the array for success even after the prefill. But misses should be rare enough that e.g. GFP_ATOMIC allocations should be acceptable after the refill.
The operation is currently not optimized.
Mark SLAB_DEPRECATED as BROKEN so the new APIs don't need to be reimplemented there and the bots don't complain. SLAB has percpu arrays by design but their sizes are determined internally.
More TODO/FIXMEs:
- NUMA awareness - preferred node currently ignored, __GFP_THISNODE not honored
- slub_debug - will not work for allocations from the array. Normally in SLUB implementation the slub_debug kills all fast paths, but that could lead to depleting the reserves if we ignore the prefill and use GFP_ATOMIC. Needs more thought.
--- include/linux/slab.h | 4 + include/linux/slub_def.h | 10 ++ mm/Kconfig | 1 + mm/slub.c | 210 ++++++++++++++++++++++++++++++++++++++- 4 files changed, 224 insertions(+), 1 deletion(-)
include/linux/slab.h +4 -0
@@ -196,6 +196,8 @@ struct kmem_cache *kmem_cache_create_usercopy(const char *name,void kmem_cache_destroy (struct kmem_cache *s);int kmem_cache_shrink (struct kmem_cache *s); +int kmem_cache_setup_percpu_array (struct kmem_cache *s,unsigned int count); +/* * Please use this macro to create slab caches. Simply specify the * name of the structure and maybe some flags that are listed above.
@@ -494,6 +496,8 @@ void kmem_cache_free(struct kmem_cache *s, void *objp);void kmem_cache_free_bulk (struct kmem_cache *s,size_t size,void **p);int kmem_cache_alloc_bulk (struct kmem_cache *s,gfp_t flags,size_t size,void **p); +int kmem_cache_prefill_percpu_array (struct kmem_cache *s,unsigned int count,gfp_t gfp); + static __always_inline void kfree_bulk(size_t size, void **p) {kmem_cache_free_bulk (NULL , size, p);
include/linux/slub_def.h +10 -0
@@ -13,8 +13,10 @@#include <linux/local_lock.h> enum stat_item { +ALLOC_PERCPU_CACHE ,/* Allocation from percpu array cache */ ALLOC_FASTPATH ,/* Allocation from cpu slab */ ALLOC_SLOWPATH ,/* Allocation by getting a new cpu slab */ +FREE_PERCPU_CACHE ,/* Free to percpu array cache */ FREE_FASTPATH ,/* Free to cpu slab */ FREE_SLOWPATH ,/* Freeing not to cpu slab */ FREE_FROZEN ,/* Freeing to frozen slab */
@@ -66,6 +68,13 @@ struct kmem_cache_cpu { };#endif /* CONFIG_SLUB_TINY */ +struct slub_percpu_array { +spinlock_t lock; +unsigned int count; +unsigned int used; +void * objects[]; +}; +#ifdef CONFIG_SLUB_CPU_PARTIAL #define slub_percpu_partial (c) ((c)->partial)
@@ -99,6 +108,7 @@ struct kmem_cache {#ifndef CONFIG_SLUB_TINY struct kmem_cache_cpu __percpu *cpu_slab;#endif +struct slub_percpu_array __percpu *cpu_array;/* Used for retrieving partial slabs, etc. */ slab_flags_t flags;unsigned long min_partial;
mm/Kconfig +1 -0
@@ -237,6 +237,7 @@ choice config SLAB_DEPRECATED bool "SLAB (DEPRECATED)" depends on !PREEMPT_RT + depends on BROKEN help Deprecated and scheduled for removal in a few cycles. Replaced by SLUB.
mm/slub.c +209 -1
274 lines not on this page · raw message
Signature · 1 line
2.41.0
Re: [RFC v2 2/7] mm, slub: add opt-in slub_percpu_array
Hi,
Quoted 5 lines · Vlastimil Babka
kmem_cache_setup_percpu_array()will allocate a per-cpu array for caching alloc/free objects of given size for the cache. The cache has to be created withSLAB_NO_MERGEflag.
Quoted 8 lines
The array is filled by freeing. When empty for alloc or full for freeing, it's simply bypassed by the operation, there's currently no batch freeing/allocations.
The locking is copied from the page allocator's pcplists, based on embedded spin locks. Interrupts are not disabled, only preemption (cpu migration on RT). Trylock is attempted to avoid deadlock due to an intnerrupt, trylock failure means the array is bypassed.
nit: s/intnerrupt/interrupt/
Quoted 37 lines
/*
* Inlined fastpath so that allocation functions (kmalloc,kmem_cache_alloc)
* have the fastpath folded into their functions. So no function callmm/slub.c +10
-1@@ -3465,7 +3564,11 @@ static __fastpath_inline void *slab_alloc_node(struct kmem_cache *s, struct listif (unlikely (object)) goto out; - object =__slab_alloc_node (s, gfpflags, node, addr, orig_size); +if (s->cpu_array) + object =alloc_from_pca (s); + +if (!object) + object =__slab_alloc_node (s, gfpflags, node, addr, orig_size);maybe_wipe_obj_freeptr (s, object); init =slab_want_init_on_alloc (gfpflags, s);@@ -3715,6 +3818,34 @@ static void __slab_free(struct kmem_cache *s, struct slab *slab,discard_slab (s, slab); }#ifndef CONFIG_SLUB_TINY /* * Fastpath with forced inlining to produce a kfree and kmem_cache_free that @@ -3740,6 +3871,11 @@ static __always_inline void do_slab_free(struct kmem_cache *s,unsigned long tid;void **freelist; +if (s->cpu_array && cnt ==1 ) { +if (free_to_pca (s, head)) +return ; + } + redo:/* * Determine the currently cpus per cpu slab. @@ -3793,6 +3929,11 @@ static void do_slab_free(struct kmem_cache *s, {
mm/slub.c static void do_slab_free(struct kmem_cache *s, · line 3939
Quoted 10 lines
mm/slub.c +5
-0void *tail_obj = tail ? : head; +if (s->cpu_array && cnt ==1 ) { +if (free_to_pca (s, head)) +return ; + } + __slab_free(s, slab, head, tail_obj, cnt, addr); }#endif /* CONFIG_SLUB_TINY */
Is this functionality needed for SLUB_TINY?
Quoted 9 lines
mm/slub.c +5
-0@@ -4060,6 +4201,45 @@ int kmem_cache_alloc_bulk(struct kmem_cache *s, gfp_t flags, size_t size, }EXPORT_SYMBOL (kmem_cache_alloc_bulk); +int kmem_cache_prefill_percpu_array (struct kmem_cache *s,unsigned int count, +gfp_t gfp) +{ +struct slub_percpu_array *pca; +void *objects[32 ];
mm/slub.c int kmem_cache_alloc_bulk(struct kmem_cache *s, gfp_t flags, size_t size, · line 4218
Quoted 10 lines
mm/slub.c +10
-0+unsigned int used; +unsigned int allocated; + +if (!s->cpu_array) +return -EINVAL ; + +/* racy but we don't care */ + pca =raw_cpu_ptr (s->cpu_array); + + used =READ_ONCE (pca->used);
Hmm for the prefill to be meaningful,
remote allocation should be possible, right?
Otherwise it only prefills for the CPU that requested it.
Quoted 11 lines
mm/slub.c +11
-0+if (used >= count) +return 0 ; + +if (pca->count < count) +return -EINVAL ; + + count -= used; + +/* TODO fix later */ +if (count >32 ) + count =32 ;
mm/slub.c int kmem_cache_alloc_bulk(struct kmem_cache *s, gfp_t flags, size_t size, · line 4240
Quoted 10 lines
mm/slub.c +10
-0+ +for (int i =0 ; i < count; i++) + objects[i] =NULL ; + allocated =kmem_cache_alloc_bulk (s, gfp, count, &objects[0 ]); + +for (int i =0 ; i < count; i++) { +if (objects[i]) { +kmem_cache_free (s, objects[i]); + } + }
nit: why not
for (int i = 0; i < allocated; i++) {
kmem_cache_free(s, objects[i]);
}and skip objects[i] = NULL
mm/slub.c int kmem_cache_alloc_bulk(struct kmem_cache *s, gfp_t flags, size_t size, · line 4242
Quoted 2 lines
mm/slub.c +2
-0+return allocated; +}
And a question:
Does SLUB still need to maintain per-cpu partial slab lists even when an opt-in percpu array is used?
Re: [RFC v2 2/7] mm, slub: add opt-in slub_percpu_array
Quoted 3 lines · Hyeonggon Yoo
Hi,
On Fri, Aug 11, 2023 at 1:36 AM Vlastimil Babka <[email protected]> wrote:
Oops, looks like I forgot reply, sorry (preparing v3 now).
Quoted 9 lines
Quoted 9 lines
kmem_cache_setup_percpu_array()will allocate a per-cpu array for caching alloc/free objects of given size for the cache. The cache has to be created withSLAB_NO_MERGEflag.The array is filled by freeing. When empty for alloc or full for freeing, it's simply bypassed by the operation, there's currently no batch freeing/allocations.
Quoted 6 lines
Quoted 4 lines
The locking is copied from the page allocator's pcplists, based on embedded spin locks. Interrupts are not disabled, only preemption (cpu migration on RT). Trylock is attempted to avoid deadlock due to an intnerrupt, trylock failure means the array is bypassed.
nit: s/intnerrupt/interrupt/
Thanks.
Quoted 40 lines
Quoted 40 lines
/*
* Inlined fastpath so that allocation functions (kmalloc,kmem_cache_alloc)
* have the fastpath folded into their functions. So no function callmm/slub.c +10
-1@@ -3465,7 +3564,11 @@ static __fastpath_inline void *slab_alloc_node(struct kmem_cache *s, struct listif (unlikely (object)) goto out; - object =__slab_alloc_node (s, gfpflags, node, addr, orig_size); +if (s->cpu_array) + object =alloc_from_pca (s); + +if (!object) + object =__slab_alloc_node (s, gfpflags, node, addr, orig_size);maybe_wipe_obj_freeptr (s, object); init =slab_want_init_on_alloc (gfpflags, s);@@ -3715,6 +3818,34 @@ static void __slab_free(struct kmem_cache *s, struct slab *slab,discard_slab (s, slab); }#ifndef CONFIG_SLUB_TINY /* * Fastpath with forced inlining to produce a kfree and kmem_cache_free that @@ -3740,6 +3871,11 @@ static __always_inline void do_slab_free(struct kmem_cache *s,unsigned long tid;void **freelist; +if (s->cpu_array && cnt ==1 ) { +if (free_to_pca (s, head)) +return ; + } + redo:/* * Determine the currently cpus per cpu slab. @@ -3793,6 +3929,11 @@ static void do_slab_free(struct kmem_cache *s, {void *tail_obj = tail ? : head;
Quoted 10 lines
mm/slub.c static void do_slab_free(struct kmem_cache *s, · line 3939
Quoted 8 lines
mm/slub.c +5
-0+if (s->cpu_array && cnt ==1 ) { +if (free_to_pca (s, head)) +return ; + } + __slab_free(s, slab, head, tail_obj, cnt, addr); }#endif /* CONFIG_SLUB_TINY */ Is this functionality needed for
SLUB_TINY?
Due to the prefill semantics, I think it has to be be even in TINY, or we risk running out of memory reserves. Also later I want to investigate extending this approach for supporting allocations in very constrained contexts (NMI) so e.g. bpf doesn't have to reimplement the slab allocator, and that would also not be good to limit to !SLUB_TINY.
Quoted 14 lines
Quoted 14 lines
mm/slub.c +10
-0@@ -4060,6 +4201,45 @@ int kmem_cache_alloc_bulk(struct kmem_cache *s, gfp_t flags, size_t size, }EXPORT_SYMBOL (kmem_cache_alloc_bulk); +int kmem_cache_prefill_percpu_array (struct kmem_cache *s,unsigned int count, +gfp_t gfp) +{ +struct slub_percpu_array *pca; +void *objects[32 ]; +unsigned int used; +unsigned int allocated; + +if (!s->cpu_array) +return -EINVAL ;
Quoted 8 lines
mm/slub.c int kmem_cache_alloc_bulk(struct kmem_cache *s, gfp_t flags, size_t size, · line 4218
Quoted 5 lines
mm/slub.c +5
-0+ +/* racy but we don't care */ + pca =raw_cpu_ptr (s->cpu_array); + + used =READ_ONCE (pca->used);Hmm for the prefill to be meaningful,
remote allocation should be possible, right?
Remote in what sense?
Quoted 1 line
Otherwise it only prefills for the CPU that requested it.
If there's a cpu migration between the prefill and usage, it might run out of the cached array, but assumption is to be rare enough to become an issue.
Quoted 24 lines
Quoted 11 lines
mm/slub.c +11
-0+if (used >= count) +return 0 ; + +if (pca->count < count) +return -EINVAL ; + + count -= used; + +/* TODO fix later */ +if (count >32 ) + count =32 ;mm/slub.c int kmem_cache_alloc_bulk(struct kmem_cache *s, gfp_t flags, size_t size, · line 4240
Quoted 10 lines
mm/slub.c +10
-0+ +for (int i =0 ; i < count; i++) + objects[i] =NULL ; + allocated =kmem_cache_alloc_bulk (s, gfp, count, &objects[0 ]); + +for (int i =0 ; i < count; i++) { +if (objects[i]) { +kmem_cache_free (s, objects[i]); + } + }nit: why not
Quoted 6 lines
for (int i = 0; i < allocated; i++) { kmem_cache_free(s, objects[i]); }and skip objects[i] = NULL
This is rewritten significantly in v3 so I think it doesn't apply anymore.
Quoted 6 lines
mm/slub.c int kmem_cache_alloc_bulk(struct kmem_cache *s, gfp_t flags, size_t size, · line 4242
Quoted 2 lines
mm/slub.c +2
-0+return allocated; +}And a question:
Does SLUB still need to maintain per-cpu partial slab lists even when an opt-in percpu array is used?
Good question :) didn't investigate it yet. We can, once this settles.
Thanks.
Re: [RFC v2 2/7] mm, slub: add opt-in slub_percpu_array
Quoted 7 lines · Vlastimil Babka
Quoted 3 lines · Hyeonggon Yoo
Hi,
On Fri, Aug 11, 2023 at 1:36 AM Vlastimil Babka <[email protected]> wrote:
Oops, looks like I forgot reply, sorry (preparing v3 now).
It's fine, you were busy removing SLAB :)
thanks for replying.
Quoted 51 lines
Quoted 40 lines
Quoted 40 lines
/*
* Inlined fastpath so that allocation functions (kmalloc,kmem_cache_alloc)
* have the fastpath folded into their functions. So no function callmm/slub.c +10
-1@@ -3465,7 +3564,11 @@ static __fastpath_inline void *slab_alloc_node(struct kmem_cache *s, struct listif (unlikely (object)) goto out; - object =__slab_alloc_node (s, gfpflags, node, addr, orig_size); +if (s->cpu_array) + object =alloc_from_pca (s); + +if (!object) + object =__slab_alloc_node (s, gfpflags, node, addr, orig_size);maybe_wipe_obj_freeptr (s, object); init =slab_want_init_on_alloc (gfpflags, s);@@ -3715,6 +3818,34 @@ static void __slab_free(struct kmem_cache *s, struct slab *slab,discard_slab (s, slab); }#ifndef CONFIG_SLUB_TINY /* * Fastpath with forced inlining to produce a kfree and kmem_cache_free that @@ -3740,6 +3871,11 @@ static __always_inline void do_slab_free(struct kmem_cache *s,unsigned long tid;void **freelist; +if (s->cpu_array && cnt ==1 ) { +if (free_to_pca (s, head)) +return ; + } + redo:/* * Determine the currently cpus per cpu slab. @@ -3793,6 +3929,11 @@ static void do_slab_free(struct kmem_cache *s, {void *tail_obj = tail ? : head;Quoted 10 lines
mm/slub.c static void do_slab_free(struct kmem_cache *s, · line 3939
Quoted 8 lines
mm/slub.c +5
-0+if (s->cpu_array && cnt ==1 ) { +if (free_to_pca (s, head)) +return ; + } + __slab_free(s, slab, head, tail_obj, cnt, addr); }#endif /* CONFIG_SLUB_TINY */ Is this functionality needed for
SLUB_TINY?
Quoted 5 lines
Due to the prefill semantics, I think it has to be be even in TINY, or we risk running out of memory reserves. Also later I want to investigate extending this approach for supporting allocations in very constrained contexts (NMI) so e.g. bpf doesn't have to reimplement the slab allocator, and that would also not be good to limit to !SLUB_TINY.
I've got the point, thanks for the explanation!
Quoted 23 lines
Quoted 14 lines
Quoted 14 lines
mm/slub.c +10
-0@@ -4060,6 +4201,45 @@ int kmem_cache_alloc_bulk(struct kmem_cache *s, gfp_t flags, size_t size, }EXPORT_SYMBOL (kmem_cache_alloc_bulk); +int kmem_cache_prefill_percpu_array (struct kmem_cache *s,unsigned int count, +gfp_t gfp) +{ +struct slub_percpu_array *pca; +void *objects[32 ]; +unsigned int used; +unsigned int allocated; + +if (!s->cpu_array) +return -EINVAL ;Quoted 8 lines
mm/slub.c int kmem_cache_alloc_bulk(struct kmem_cache *s, gfp_t flags, size_t size, · line 4218
Quoted 5 lines
mm/slub.c +5
-0+ +/* racy but we don't care */ + pca =raw_cpu_ptr (s->cpu_array); + + used =READ_ONCE (pca->used);Hmm for the prefill to be meaningful,
remote allocation should be possible, right?
Quoted 1 line
Remote in what sense?
TL;DR) What I wanted to ask was:
"How pre-filling a number of objects works when the pre-filled objects are not shared between CPUs"
IIUC the prefill is opportunistically filling the array so (hopefully) expecting there are
some objects filled in it.
Let's say CPU X calls kmem_cache_prefill_percpu_array(32) and all 32 objects are filled into CPU X's array.
But if CPU Y can't allocate from CPU X's array (which I referred to as "remote allocation"), the semantics differ from
the maple tree's perspective because preallocated objects were shared between CPUs before, but now it's not?
Thanks!
--
Hyeonggon
Re: [RFC v2 2/7] mm, slub: add opt-in slub_percpu_array
Quoted 27 lines · Hyeonggon Yoo
Quoted 23 lines · Vlastimil Babka
Quoted 14 lines
Quoted 14 lines
mm/slub.c +10
-0@@ -4060,6 +4201,45 @@ int kmem_cache_alloc_bulk(struct kmem_cache *s, gfp_t flags, size_t size, }EXPORT_SYMBOL (kmem_cache_alloc_bulk); +int kmem_cache_prefill_percpu_array (struct kmem_cache *s,unsigned int count, +gfp_t gfp) +{ +struct slub_percpu_array *pca; +void *objects[32 ]; +unsigned int used; +unsigned int allocated; + +if (!s->cpu_array) +return -EINVAL ;Quoted 8 lines
mm/slub.c int kmem_cache_alloc_bulk(struct kmem_cache *s, gfp_t flags, size_t size, · line 4218
Quoted 5 lines
mm/slub.c +5
-0+ +/* racy but we don't care */ + pca =raw_cpu_ptr (s->cpu_array); + + used =READ_ONCE (pca->used);Hmm for the prefill to be meaningful,
remote allocation should be possible, right?Quoted 1 line
Remote in what sense?
Quoted 7 lines
TL;DR) What I wanted to ask was:
"How pre-filling a number of objects works when the pre-filled objects are not shared between CPUs"IIUC the prefill is opportunistically filling the array so (hopefully) expecting there are
some objects filled in it.
Yes.
Quoted 6 lines
Let's say CPU X calls
kmem_cache_prefill_percpu_array(32)and all 32 objects are filled into CPU X's array.
But if CPU Y can't allocate from CPU X's array (which I referred to as "remote allocation"), the semantics differ from
the maple tree's perspective because preallocated objects were shared between CPUs before, but now it's not?
The assumption is that the operation will prefill on CPU X and then consume it also on X, because shortly after prefill it will enter some restricted context (i.e. spin_lock_irqsave or whatnot) that prevents it from migrating. That's not guaranteed of course, but migration in a bad moment and subsequent depleted array should be rare enough that we'll just handle it in the slow paths, and if it results in dipping into reserves, it won't be too disruptive.
Quoted 4 lines
Thanks!
--
Hyeonggon
RFC v2 3/7 maple_tree: use slub percpu array
In reply to Vlastimil BabkaJust make sure the maple_node_cache has a percpu array of size 32.
Will break with CONFIG_SLAB.
--- lib/maple_tree.c | 9 ++++++++- 1 file changed, 8 insertions(+), 1 deletion(-)
lib/maple_tree.c +8 -1
@@ -6180,9 +6180,16 @@ bool mas_nomem(struct ma_state *mas, gfp_t gfp)void __init maple_tree_init (void ) { +int ret; + maple_node_cache =kmem_cache_create ("maple_node" ,sizeof (struct maple_node ),sizeof (struct maple_node ), -SLAB_PANIC ,NULL ); +SLAB_PANIC |SLAB_NO_MERGE ,NULL ); + + ret =kmem_cache_setup_percpu_array (maple_node_cache,32 ); + +if (ret) +pr_warn ("error %d creating percpu_array for maple_node_cache\n" , ret); }/**
Signature · 1 line
2.41.0
RFC v2 4/7 maple_tree: avoid bulk alloc/free to use percpu array more
In reply to Vlastimil BabkaUsing bulk alloc/free on a cache with percpu array should not be necessary and the bulk alloc actually bypasses the array (the prefill functionality currently relies on this).
The simplest change for now is just to convert the respective maple tree wrappers to do a loop of normal alloc/free. We can optimize later versions if needed.
--- lib/maple_tree.c | 12 ++++++++++-- 1 file changed, 10 insertions(+), 2 deletions(-)
lib/maple_tree.c +10 -2
@@ -161,12 +161,20 @@ static inline struct maple_node *mt_alloc_one(gfp_t gfp)static inline int mt_alloc_bulk (gfp_t gfp,size_t size,void **nodes) { -return kmem_cache_alloc_bulk (maple_node_cache, gfp, size, nodes); +int i; + +for (i =0 ; i < size; i++) { + nodes[i] =kmem_cache_alloc (maple_node_cache, gfp); +if (!nodes[i]) +break ; + } +return i; }static inline void mt_free_bulk (size_t size,void __rcu **nodes) { -kmem_cache_free_bulk (maple_node_cache, size, (void **)nodes); +for (size_t i =0 ; i < size; i++) +kmem_cache_free (maple_node_cache, nodes[i]); }static void mt_free_rcu (struct rcu_head *head)
Signature · 1 line
2.41.0
RFC v2 5/7 maple_tree: Remove MA_STATE_PREALLOC
In reply to Vlastimil BabkaFrom: "Liam R. Howlett" <[email protected]>
MA_SATE_PREALLOC was added to catch any writes that try to allocate when the maple state is being used in preallocation mode. This can safely be removed in favour of the percpu array of nodes.
Note that mas_expected_entries() still expects no allocations during operation and so MA_STATE_BULK can be used in place of preallocations for this case, which is primarily used for forking.
--- lib/maple_tree.c | 19 ++++++------------- 1 file changed, 6 insertions(+), 13 deletions(-)
lib/maple_tree.c +6 -13
@@ -68,11 +68,9 @@* Maple state flags * * MA_STATE_BULK - Bulk insert mode * * MA_STATE_REBALANCE - Indicate a rebalance during bulk insert -* * MA_STATE_PREALLOC - Preallocated nodes, WARN_ON allocation */ #define MA_STATE_BULK 1#define MA_STATE_REBALANCE 2 -#define MA_STATE_PREALLOC 4#define ma_parent_ptr (x) ((struct maple_pnode *)(x))#define ma_mnode_ptr (x) ((struct maple_node *)(x))
@@ -1280,11 +1278,8 @@ static inline void mas_alloc_nodes(struct ma_state *mas, gfp_t gfp)return ;mas_set_alloc_req (mas,0 ); -if (mas->mas_flags &MA_STATE_PREALLOC ) { -if (allocated) -return ; -WARN_ON (!allocated); - } +if (mas->mas_flags &MA_STATE_BULK ) +return ;if (!allocated || mas->alloc->node_count ==MAPLE_ALLOC_SLOTS ) { node = (struct maple_alloc *)mt_alloc_one (gfp);
@@ -5596,7 +5591,7 @@ void mas_destroy(struct ma_state *mas) mas->mas_flags &= ~MA_STATE_REBALANCE ; } - mas->mas_flags &= ~(MA_STATE_BULK |MA_STATE_PREALLOC ); + mas->mas_flags &= ~MA_STATE_BULK ; total =mas_allocated (mas);while (total) {
@@ -5645,9 +5640,6 @@ int mas_expected_entries(struct ma_state *mas, unsigned long nr_entries)* of nodes during the operation. */ -/* Optimize splitting for bulk insert in-order */ - mas->mas_flags |=MA_STATE_BULK ; -/* * Avoid overflow, assume a gap between each entry and a trailing null. * If this is wrong, it just means allocation can happen during
@@ -5664,8 +5656,9 @@ int mas_expected_entries(struct ma_state *mas, unsigned long nr_entries)/* Add working room for split (2 nodes) + new parents */ mas_node_count (mas, nr_nodes +3 ); -/* Detect if allocations run out */ - mas->mas_flags |=MA_STATE_PREALLOC ; +/* Optimize splitting for bulk insert in-order */ + mas->mas_flags |=MA_STATE_BULK ; +if (!mas_is_err (mas))return 0 ;
Signature · 1 line
2.41.0
RFC v2 6/7 maple_tree: replace preallocation with slub percpu array prefill
In reply to Vlastimil BabkaWith the percpu array we can try not doing the preallocations in maple tree, and instead make sure the percpu array is prefilled, and using GFP_ATOMIC in places that relied on the preallocation (in case we miss or fail trylock on the array), i.e. mas_store_prealloc(). For now simply add __GFP_NOFAIL there as well.
--- lib/maple_tree.c | 20 +++++++++----------- 1 file changed, 9 insertions(+), 11 deletions(-)
lib/maple_tree.c +9 -11
@@ -5530,7 +5530,12 @@ void mas_store_prealloc(struct ma_state *mas, void *entry)mas_wr_store_setup (&wr_mas);trace_ma_write (__func__, mas,0 , entry); + +retry:mas_wr_store_entry (&wr_mas); +if (unlikely (mas_nomem (mas,GFP_ATOMIC | __GFP_NOFAIL))) + goto retry; +MAS_WR_BUG_ON (&wr_mas,mas_is_err (mas));mas_destroy (mas); }
@@ -5545,19 +5550,12 @@ EXPORT_SYMBOL_GPL(mas_store_prealloc);*/ int mas_preallocate (struct ma_state *mas,gfp_t gfp) { -int ret; +int count =1 +mas_mt_height (mas) *3 ; -mas_node_count_gfp (mas,1 +mas_mt_height (mas) *3 , gfp); - mas->mas_flags |=MA_STATE_PREALLOC ; -if (likely (!mas_is_err (mas))) -return 0 ; +// TODO: should probably indicate if it failed the prefill? +kmem_cache_prefill_percpu_array (maple_node_cache, count, gfp); -mas_set_alloc_req (mas,0 ); - ret =xa_err (mas->node); -mas_reset (mas); -mas_destroy (mas); -mas_reset (mas); -return ret; +return 0 ; }EXPORT_SYMBOL_GPL (mas_preallocate);
Signature · 1 line
2.41.0
RFC v2 7/7 tools: Add SLUB percpu array functions for testing
In reply to Vlastimil BabkaFrom: "Liam R. Howlett" <[email protected]>
Support new percpu array functions to the test code so they can be used in the maple tree testing.
--- tools/include/linux/slab.h | 4 ++++ tools/testing/radix-tree/linux.c | 14 ++++++++++++++ tools/testing/radix-tree/linux/kernel.h | 1 + 3 files changed, 19 insertions(+)
tools/include/linux/slab.h +4 -0
@@ -7,6 +7,7 @@#define SLAB_PANIC 2#define SLAB_RECLAIM_ACCOUNT 0x00020000UL/* Objects are reclaimable */ +#define SLAB_NO_MERGE 0x01000000UL/* Prevent merging with compatible kmem caches */ #define kzalloc_node (size, flags, node) kmalloc(size, flags)
@@ -45,4 +46,7 @@ void kmem_cache_free_bulk(struct kmem_cache *cachep, size_t size, void **list);int kmem_cache_alloc_bulk (struct kmem_cache *cachep,gfp_t gfp,size_t size,void **list); +int kmem_cache_setup_percpu_array (struct kmem_cache *s,unsigned int count); +int kmem_cache_prefill_percpu_array (struct kmem_cache *s,unsigned int count, +gfp_t gfp);#endif /* _TOOLS_SLAB_H */
tools/testing/radix-tree/linux.c +14 -0
@@ -187,6 +187,20 @@ int kmem_cache_alloc_bulk(struct kmem_cache *cachep, gfp_t gfp, size_t size,return size; } +int kmem_cache_setup_percpu_array (struct kmem_cache *s,unsigned int count) +{ +return 0 ; +} + +int kmem_cache_prefill_percpu_array (struct kmem_cache *s,unsigned int count, +gfp_t gfp) +{ +if (count > s->non_kernel) +return s->non_kernel; + +return count; +} +struct kmem_cache *kmem_cache_create (const char *name,unsigned int size,unsigned int align,unsigned int flags,void (*ctor)(void *))
tools/testing/radix-tree/linux/kernel.h +1 -0
@@ -15,6 +15,7 @@#define printk printf#define pr_err printk +#define pr_warn printk#define pr_info printk#define pr_debug printk#define pr_cont printk
Signature · 1 line
2.41.0
Suren Baghdasaryan
reviewerQuoted 106 lines · Vlastimil Babka
Also in git [1]. Changes since v1 [2]:
- fix a few bugs
- SLAB marked as BROKEN so bots dont complain about missing functions
- incorporate Liam's patches, which allows getting rid of preallocations inmas_prealloc()completely. This has reduced the allocation stats further, with the whole series.More notes wrt v1 RFC feedback:
- locking is still done as in v1, as it allows remote draining, which should be added before this is suitable for merging
- there's currently no bulk freeing/refill of the percpu array, which will eventually be added, but I expect most perf gain for the maple tree use case to come from the avoided preallocations anyway----
At LSF/MM I've mentioned that I see several use cases for introducing opt-in percpu arrays for caching alloc/free objects in SLUB. This is my first exploration of this idea, speficially for the use case of maple tree nodes. We have brainstormed this use case on IRC last week with Liam and Matthew and this how I understood the requirements:
- percpu arrays will be faster thank bulk alloc/free which needs relatively long freelists to work well. Especially in the freeing case we need the nodes to come from the same slab (or small set of those)
- preallocation for the worst case of needed nodes for a tree operation that can't reclaim due to locks is wasteful. We could instead expect that most of the time percpu arrays would satisfy the constained allocations, and in the rare cases it does not we can dip into
GFP_ATOMICreserves temporarily. Instead of preallocation just prefill the arrays.- NUMA locality is not a concern as the nodes of a process's VMA tree end up all over the place anyway.
So this RFC patchset adds such percpu array in Patch 2. Locking is stolen from Mel's recent page allocator's pcplists implementation so it can avoid disabling IRQs and just disable preemption, but the trylocks can fail in rare situations.
Then maple tree is modified in patches 3-6 to benefit from this. This is done in a very crude way as I'm not so familiar with the code.
I've briefly tested this with virtme VM boot and checking the stats from
CONFIG_SLUB_STATSin sysfs.Patch 2:
slub changes implemented including new counters
alloc_cpu_cacheandfree_cpu_cachebut maple tree doesn't use them yet(none):/sys/kernel/slab/maple_node # grep .
alloc_cpu_cachealloc_*pathfree_cpu_cachefree_*path | cut -d' ' -f1 alloc_cpu_cache:0
alloc_fastpath:54842
alloc_slowpath:8142
free_cpu_cache:0
free_fastpath:32336
free_slowpath:23484Patch 3:
maple node cache creates percpu array with 32 entries, not changed anything else
-> some allocs/free satisfied by the array
alloc_cpu_cache:11956
alloc_fastpath:40675
alloc_slowpath:7308
free_cpu_cache:12082
free_fastpath:23617
free_slowpath:17956Patch 4:
maple tree nodes bulk alloc/free converted to loop of normal alloc to use percpu array more, because bulk alloc bypasses it
-> majority alloc/free now satisfied by percpu array
alloc_cpu_cache:54673
alloc_fastpath:4491
alloc_slowpath:737
free_cpu_cache:54759
free_fastpath:332
free_slowpath:4723Patch 5+6:
mas_preallocate()just prefills the percpu array, doesn't preallocate anythingmas_store_prealloc()gains a retry loop withmas_nomem(mas, GFP_ATOMIC | __GFP_NOFAIL)-> major drop of alloc/free
(the prefills are included in the accounting)alloc_cpu_cache:15036
alloc_fastpath:4651
alloc_slowpath:656
free_cpu_cache:15102
free_fastpath:299
free_slowpath:4835
Quoted 4 lines
It would be interesting to see how it affects the workloads that saw regressions from the maple tree introduction, as the slab operations were suspected to be a major factor and now they should be both reduced and made cheaper.
Hi Vlastimil,
I backported your patchset to 6.1 and tested it on Android with my mmap stress test (mmap a file-backed page, read-fault, unmap all in a tight loop). The performance of such tests is important for Android because that's what is being done during application launch and app launch time is an important metric for us. I recorded 1.8% performance improvement with this test.
Thanks,
Suren.
Quoted 25 lines
Liam R. Howlett (2):
maple_tree: RemoveMA_STATE_PREALLOC
tools: Add SLUB percpu array functions for testingVlastimil Babka (5):
mm, slub: fix bulk alloc and free stats
mm, slub: add opt-inslub_percpu_array
maple_tree: use slub percpu array
maple_tree: avoid bulk alloc/free to use percpu array more
maple_tree: replace preallocation with slub percpu array prefillinclude/linux/slab.h | 4 + include/linux/slub_def.h | 10 ++ lib/maple_tree.c | 60 ++++--- mm/Kconfig | 1 + mm/slub.c | 221 +++++++++++++++++++++++- tools/include/linux/slab.h | 4 + tools/testing/radix-tree/linux.c | 14 ++ tools/testing/radix-tree/linux/kernel.h | 1 + 8 files changed, 286 insertions(+), 29 deletions(-)--
2.41.0