Message-Id: <20250425-slub-percpu-caches-v4-0-8a636982b4a4@suse.cz>
Date: Fri, 25 Apr 2025 10:27:20 +0200
From: Vlastimil Babka <vbabka@...e.cz>
To: Suren Baghdasaryan <surenb@...gle.com>, 
 "Liam R. Howlett" <Liam.Howlett@...cle.com>, 
 Christoph Lameter <cl@...ux.com>, David Rientjes <rientjes@...gle.com>
Cc: Roman Gushchin <roman.gushchin@...ux.dev>, 
 Harry Yoo <harry.yoo@...cle.com>, Uladzislau Rezki <urezki@...il.com>, 
 linux-mm@...ck.org, linux-kernel@...r.kernel.org, rcu@...r.kernel.org, 
 maple-tree@...ts.infradead.org, vbabka@...e.cz, 
 "Liam R. Howlett" <Liam.Howlett@...cle.com>
Subject: [PATCH v4 0/9] SLUB percpu sheaves

Hi,

This is the v4 and first non-RFC series to add an opt-in percpu
array-based caching layer to SLUB, following the LSF/MM discussions.
Since v3 I've also made changes to achieve full compatibility with
slub_debug, and IRC discussions led to the last patch intended to
improve NUMA locality (the patch remains separate for evaluation
purposes).

Harry's RFC [1] also prompted me to reconsider the stat counters and as
a result I removed some that seemed unnecessary and added others that
were missing to evaluate how effective the barns and sheaf preffiling
are.

I have also addressed the RFC v3 feedback by Suren and Harry - thanks!

Note the name "sheaf" was invented by Matthew so we don't call the
arrays magazine like the original Bonwick paper. The per-NUMA-node cache
of sheaves is thus called "barn".

This caching may seem similar to the arrays in SLAB, but there are some
important differences:

- opt-in, not used for every cache
- does not distinguish NUMA locality, thus there are no per-node
  "shared" arrays (with possible lock contention) and no "alien" arrays
  that would need periodical flushing
  - NUMA restricted allocations and strict_numa mode is still honoured,
    the percpu sheaves are bypassed for those allocations
  - a later patch (for separate evaluation) makes freeing remote objects
    bypass sheaves so sheaves contain mostly (not strictly) local objects
- improves kfree_rcu() handling by reusing whole sheaves
- there is an API for obtaining a preallocated sheaf that can be used
  for guaranteed and efficient allocations in a restricted context, when
  the upper bound for needed objects is known but rarely reached

The motivation comes mainly from the ongoing work related to VMA locking
scalability and the related maple tree operations. This is why VMA and
maple nodes caches are sheaf-enabled in the patchset, but for maple tree
it's not a full conversion that would benefit from the improved
preallocation API.

Some performance benefits were measured by Suren and Liam in previous
versions. Suren's results in [2] looked quite promising.

A sheaf-enabled cache has the following expected advantages:

- Cheaper fast paths. For allocations, instead of local double cmpxchg,
  thanks to local_trylock() it becomes a preempt_disable() and no atomic
  operations. Same for freeing, which is normally a local double cmpxchg
  only for short term allocations (so the same slab is still active on the
  same cpu when freeing the object) and a more costly locked double
  cmpxchg otherwise.

  There is a possible downside with a larger fraction of
  non-NUMA-restricted allocations to get remote objects. The last patch
  changes it by making remote frees bypass sheaves. Some very preliminary
  measurements suggest only 5% frees are remote, but whether this is a net
  improvement has to be evaluated.

- kfree_rcu() batching and recycling. kfree_rcu() will put objects to a
  separate percpu sheaf and only submit the whole sheaf to call_rcu()
  when full. After the grace period, the sheaf can be used for
  allocations, which is more efficient than freeing and reallocating
  individual slab objects (even with the batching done by kfree_rcu()
  implementation itself). In case only some cpus are allowed to handle rcu
  callbacks, the sheaf can still be made available to other cpus on the
  same node via the shared barn. The maple_node cache uses kfree_rcu() and
  thus can benefit from this.

- Preallocation support. A prefilled sheaf can be privately borrowed to
  perform a short term operation that is not allowed to block in the
  middle and may need to allocate some objects. If an upper bound (worst
  case) for the number of allocations is known, but only much fewer
  allocations actually needed on average, borrowing and returning a sheaf
  is much more efficient then a bulk allocation for the worst case
  followed by a bulk free of the many unused objects. Maple tree write
  operations should benefit from this.

- Compatibility with slub_debug. When slub_debug is enabled for a cache,
  we simply don't create the percpu sheaves so that the debugging hooks
  (at the node partial list slowpaths) are reached as before. Sheaf
  preallocation still works by reusing the (ineffective) paths for
  requests exceeding the cache's sheaf_capacity. This is in line with the
  existing approach where debugging bypasses the fast paths.

GIT TREES:

this series: https://git.kernel.org/vbabka/l/slub-percpu-sheaves-v4r2

It is based on post-6.15-rc3 commit 82efd569a890 ("locking/local_lock:
fix _Generic() matching of local_trylock_t") as it definitely needs
local_trylock_t to work properly.

I have tried to rebase the full maple tree conversion, but there were
conflicts due to 6.15 changes and I don't know the code well enought to
resolve them confidently.

Vlastimil

[1] https://lore.kernel.org/all/20250407041810.13861-1-harry.yoo@oracle.com/
[2] https://lore.kernel.org/all/CAJuCfpFVopL%2BsMdU4bLRxs%2BHS_WPCmFZBdCmwE8qV2Dpa5WZnA@mail.gmail.com/

---
Changes in v4:
- slub_debug disables sheaves for the cache in order to work properly
- strict_numa mode works as intended
- added a separate patch to make freeing remote objects skip sheaves
- various code refactoring suggested by Suren and Harry
- removed less useful stat counters and added missing ones for barn
  and prefilled sheaf events
- Link to v3: https://lore.kernel.org/r/20250317-slub-percpu-caches-v3-0-9d9884d8b643@suse.cz

Changes in v3:
- Squash localtry_lock conversion so it's used immediately.
- Incorporate feedback and add tags from Suren and Harry - thanks!
  - Mostly adding comments and some refactoring.
  - Fixes for kfree_rcu_sheaf() vmalloc handling, cpu hotremove
    flushing.
  - Fix wrong condition in kmem_cache_return_sheaf() that may have
    affected performance negatively.
  - Refactoring of free_to_pcs()
- Link to v2: https://lore.kernel.org/r/20250214-slub-percpu-caches-v2-0-88592ee0966a@suse.cz

Changes in v2:
- Removed kfree_rcu() destructors support as VMAs will not need it
  anymore after [3] is merged.
- Changed to localtry_lock_t borrowed from [2] instead of an own
  implementation of the same idea.
- Many fixes and improvements thanks to Liam's adoption for maple tree
  nodes.
- Userspace Testing stubs by Liam.
- Reduced limitations/todos - hooking to kfree_rcu() is complete,
  prefilled sheaves can exceed cache's sheaf_capacity.
- Link to v1: https://lore.kernel.org/r/20241112-slub-percpu-caches-v1-0-ddc0bdc27e05@suse.cz

---
Liam R. Howlett (2):
      tools: Add testing support for changes to rcu and slab for sheaves
      tools: Add sheaves support to testing infrastructure

Vlastimil Babka (7):
      slab: add opt-in caching layer of percpu sheaves
      slab: add sheaf support for batching kfree_rcu() operations
      slab: sheaf prefilling for guaranteed allocations
      slab: determine barn status racily outside of lock
      maple_tree: use percpu sheaves for maple_node_cache
      mm, vma: use percpu sheaves for vm_area_struct cache
      mm, slub: skip percpu sheaves for remote object freeing

 include/linux/slab.h                  |   47 +
 kernel/fork.c                         |    1 +
 lib/maple_tree.c                      |   11 +-
 mm/slab.h                             |    5 +
 mm/slab_common.c                      |   32 +-
 mm/slub.c                             | 1573 +++++++++++++++++++++++++++++++--
 tools/include/linux/slab.h            |   65 +-
 tools/testing/shared/linux.c          |  108 ++-
 tools/testing/shared/linux/rcupdate.h |   22 +
 9 files changed, 1791 insertions(+), 73 deletions(-)
---
base-commit: 82efd569a8909f2b13140c1b3de88535aea0b051
change-id: 20231128-slub-percpu-caches-9441892011d7

Best regards,
-- 
Vlastimil Babka <vbabka@...e.cz>

Powered by blists - more mailing lists