[PATCH v8 00/15] futex: Add support task local hash maps.

[Sebastian Andrzej Siewior]

Hi,

this is a follow up on
	https://lore.kernel.org/ZwVOMgBMxrw7BU9A@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

and adds support for task local futex_hash_bucket. It can be created via
prctl().

This version supports resize at runtime, auto resize while creating
threads. The upper limit is at 256 * num_possible_cpus() but I guess we
can lower that. The resize can only increase, never lower the the amount
of available local hash bucket slots.

I posted performance numbers of "perf bench futex hash"
	https://lore.kernel.org/all/20241101110810.R3AnEqdu@xxxxxxxxxxxxx/

While the performance of the 16 default bucket looks worse than the 512
(after that the performance hardly changes while before it doubles) be
aware those are now task local (and not shared with others) and it seems
to be sufficient in general.
For the systems with 512CPUs and one db application we should probably
resize. So either the application needs to resize it or we offer auto
resize based on threads and CPUs. But be aware that workloads like
"xz huge_file.tar" will happily acquire all CPUs in the system and only
use a few locks in total and not very often. So it would probably
perform with two hash buckets as good as 512 in this scenario.

v7…v8 https://lore.kernel.org/all/20250123202446.610203-1-bigeasy@xxxxxxxxxxxxx/
  - Rebase on v6.14-rc1

v6…v7: https://lore.kernel.org/all/20241218111618.268028-1-bigeasy@xxxxxxxxxxxxx/
  - Closed a local hash release race during resize.
  - Closed a resize race in exit_pi_state_list()
  - Closed a resize related race in futex_get_locked_hb() (observed in
    futex_lock_pi() and futex_wait_requeue_pi()).
  - Avoid losing task state in futex_wait_multiple_setup().
  - CONFIG_BASE_SMALL systems use only 2 hash buckets within the private
    hash. The global hash uses here always 16.

v5…v6: https://lore.kernel.org/all/20241215230642.104118-1-bigeasy@xxxxxxxxxxxxx/
  - Let only futex_hash() perform the delayed assignment of the new
    local hash.
  - Make sure that futex_hash_allocate() does not drop the initial
    reference of the current local hash more than once.
  - Split "futex_hb_waiters_dec() before unlock" into its own patch.
  - Reword the commit description in a few patches as suggested by
    Thomas Gleixner.

v4…v5: https://lore.kernel.org/all/20241203164335.1125381-1-bigeasy@xxxxxxxxxxxxx/
  - Changed the the reference-tracking scheme: The reference is now
    dropped once the lock is dropped. The resize operation also requeues
    all users on the hash bucket from the old one to the new one.

v3…v4: https://lore.kernel.org/all/20241115172035.795842-1-bigeasy@xxxxxxxxxxxxx/
  - Completed resize. Tested with wait/wake, lock_pi, requeue and
    requeue_pi.
  - Added auto resize during thread creation.
  - Fixed bucket initialisation of the global hash bucket resilting in a
    crash sometimes.

v2…v3 https://lore.kernel.org/all/20241028121921.1264150-1-bigeasy@xxxxxxxxxxxxx/
  - The default auto size for auto creation is 16.
  - For the private hash jhash2 is used and only for the address.
  - My "perf bench futex hash" hacks have been added.
  - The structure moved from signal's struct to mm.
  - It is possible resize it at runtime.

v1…v2 https://lore.kernel.org/all/20241026224306.982896-1-bigeasy@xxxxxxxxxxxxx/:
  - Moved to struct signal_struct and is used process wide.
  - Automatically allocated once the first thread is created.

Sebastian

Sebastian Andrzej Siewior (14):
  futex: Create helper function to initialize a hash slot.
  futex: Add basic infrastructure for local task local hash.
  futex: Allow automatic allocation of process wide futex hash.
  futex: Hash only the address for private futexes.
  futex: Move private hashing into its own function.
  futex: Decrease the waiter count before the unlock operation.
  futex: Prepare for reference counting of the process private hash end
    of operation.
  futex: Re-evaluate the hash bucket after dropping the lock
  futex: Introduce futex_get_locked_hb().
  futex: Acquire a hash reference in futex_wait_multiple_setup().
  futex: Allow to re-allocate the private local hash.
  futex: Resize local futex hash table based on number of threads.
  futex: Use a hashmask instead of hashsize.
  futex: Avoid allocating new local hash if there is something pending.

Thomas Gleixner (1):
  rcuref: Avoid false positive "imbalanced put" report.

 include/linux/futex.h      |  21 ++
 include/linux/mm_types.h   |   7 +-
 include/linux/rcuref.h     |   9 +-
 include/uapi/linux/prctl.h |   5 +
 io_uring/futex.c           |   2 +-
 kernel/fork.c              |  24 ++
 kernel/futex/core.c        | 447 ++++++++++++++++++++++++++++++++++---
 kernel/futex/futex.h       |  38 +++-
 kernel/futex/pi.c          |  36 ++-
 kernel/futex/requeue.c     |  37 ++-
 kernel/futex/waitwake.c    |  50 +++--
 kernel/sys.c               |   4 +
 lib/rcuref.c               |   5 +-
 13 files changed, 602 insertions(+), 83 deletions(-)

-- 
2.47.2