Re: futex: private hash can stay on the shared atomic refcount indefinitely after auto-scaling

[Nikita Taranov]

Following up with three things: a better reproducer, results from two more
vendors, and a prototype of the approach you suggested.

## A new repro

The code could be found at https://gist.github.com/nickitat/a7a46b61d6769ceec493881f82e7b344 .

This one is an ordinary producer/consumer: threads park in plain FUTEX_WAIT
like the idle workers of a thread pool, others issue plain FUTEX_WAKE on the
same futexes, so waiters are woken, loop and re-park. Only plain FUTEX_WAIT and
FUTEX_WAKE. The kernel's own auto-scaling during thread creation is the only
thing that ever asks for a pivot.

The control is one prctl(PR_FUTEX_HASH, PR_FUTEX_HASH_SET_SLOTS, n) before any
thread exists, which marks the hash custom and disables auto-scaling, so no
pivot is ever requested and the stall cannot occur. Basically, the same story
as in the first repro.

v7.2, Xeon 6975P-C 96c/192t SNC=3, 8 runs of 4 s per point, clock pinned:

  threads   auto   pre-sized   stalled
       16   25.8        42.3      0/8
       32   34.8        41.1      0/8
       48   28.7        31.8      0/8
       64   29.9        34.2      0/8
       96    3.7        46.3      8/8
      128    3.6        53.6      8/8
      192    4.0        38.7      8/8

Throughput is far lower than the numbers in my earlier mails because the work
is real; the comparison is the point. The control (pre-sized) is almost flat
across the whole range, so the work does not get harder with thread count
-- only the arm that requests a pivot collapses, and only above a threshold.

## It is not only this Intel box

> You might have hit the sweet spot with your CPU. I have here a 144 CPU
> box and

I wrote previously that this Intel host was the only one where the repro worked,
based on a 96-thread sweep with the old reproducer. At 192 threads, with the
reproducer above, Graviton4 does reach the same state -- less often,
but permanently when it does.

192 threads, 15 s runs, per-second traces:

                        latched permanently   transient   never
  Xeon 6975P-C                  8 / 8              -        0
  Graviton4 Neoverse-V2         1 / 15           2 / 15    12 / 15
  AMD EPYC 9R45                 0 / 14          14 / 14      -

Graviton4 will stall at a higher rate if the wakers are created gradually
rather than all at once -- the `ramp_ms` parameter spreads their creation
over that many milliseconds in total, which is what a thread pool growing
while already under load does. I saw 5/16 stalls on one run.
AMD still never latched in ~200 runs.

So the state is reachable on more than one vendor's hardware and usually permanent
once entered. What differs is how often a process falls in.
Arguably, this flakiness is worse than a deterministic stall for a real production.

## Prototype of your suggestion

> Not sure what we could do here. One idea might be to block further
> futex syscalls so they don't acquire a new reference on the existing
> hash and allow a transition to the new hash more quickly.

The only analogy available to me due to lack of any knowledge is rw-locks. I asked
Claude to adapt the percpu-rwsem code to futex, and after a few iterations we
produced a hopefully viable patch. I suppose it implements plus-minus your suggestion.

The results (same box and all the rest of the environment):

  - the reproducer: 0/8 stalled at every thread count, against 8/8 on stock at
    96 and above; 192 threads run at 54 Mops/s instead of 4.
  - futex kselftests: 14 passed, 0 failed, with the mechanism enabled and
    disabled; futex_numa and futex_numa_mpol pass.
  - requeue-PI selftests looped under a continuous pivot storm, to exercise the
    drop_fph handoff against the phase: all rounds passed.
  - stress-ng: 64 futex stressors, and a 40-way futex/clone/mmap mix, 0 failures.
  - PROVE_LOCKING and KASAN builds: clean.
  - measured overhead ~0.6% on a pthread_mutex/pthread_cond benchmark with pinned clock.

Makes sense to note that the patch was applied to v7.2 and all testing was done on that build.

The code could be found at https://gist.github.com/nickitat/0b1cc68deff5fe2b27209b150da6fb00 .
If you find it useful, I can prepare a proper patch for the kernel tree.

Regards.