[RFC PATCH 00/12] FUTEX_PING: A stealable futex using Proxy Execution.

[Suleiman Souhlal <suleiman@google.com>]

Hello,

This patch series adds a new type of PI futexes, PI Next Generation,
or PING (name coined by Steven Rostedt) (but other name suggestions
are welcome!), that differs from classic PI futexes in that they can
be stolen from the top waiter, and use Proxy Execution instead of
rtmutexes internally. 

The reason to allow the futexes to be stolen is that with classic PI
futex's strict handoff to the top waiter, new contending lockers are
now forced to wait in queue, which means that any locking operation
now becomes a scheduling event. With stealing, a contending locker has
the chance of taking the lock without blocking. The longer wait time
of blocked tasks can be mitigated by forcing the lock to be handed
off to them in a way that can't be stolen, when they've been stolen
from too much, to ensure they don't get starved.

The use of Proxy Execution lets us also get Priority Inheritance for
for fair tasks, which PI futexes don't really allow.


PING futexes are used similarly to FUTEX_*_PI, where the owner is
expected to write its TID in the futex.

The main user-visible difference with regular PI futexes is that the
kernel is allowed to set the FUTEX_WAITERS bit with an empty TID.
This is to allow for a new locker to steal the lock from the top
waiter, which is supposed to improve performance in workloads that
don't need strict RT handling.
The user is also allowed to notice that the futex is unlocked but
has waiters, and steal it without going to the kernel.

An example of how they're meant to be used:
Lock:
        static __thread pid_t tid = gettid();
        uint32_t oldval = 0;
        if (atomic_compare_exchange_strong(ftx, &oldval, tid)
                return;
        oldval = FUTEX_WAITERS;
        // The user could also spin here a bit.
        if (atomic_compare_exchange_strong(ftx, &oldval,
            tid | FUTEX_WAITERS))
                return;
        if (futex(ftx, FUTEX_LOCK_PING, 0, NULL) != 0)
                err(1, "FUTEX_LOCK_PING");

Unlock:
        static __thread pid_t tid = gettid();
        uint32_t oldval = tid;
        if (atomic_compare_exchange_strong(ftx, &oldval, 0))
                return;
        if (futex(ftx, FUTEX_UNLOCK_PING, 0, NULL) != 0)
                err(1, "FUTEX_UNLOCK_PING");


Why did we opt for a new futex type instead of making PI futexes
and rtmutex use Proxy Execution?

PI futexes have strict rtmutex semantics, which while important
for RT workloads, could also potentially result in performance
penalties in workloads where maintaining those semantics isn't
as important. Since we don't want to break existing applications,
creating a new futex type seems appropriate.
Making a new futex type also lets us change the user interface a bit,
to allow for userspace stealing.

We do hope to eventually enable rtmutexes to use Proxy Execution
but the rtmutex wait_lock and pi_lock ordering is backwards for
Proxy Execution, so a potentially complicated rework might be needed
before rtmutexes can use it.
In the meantime, Proxy Execution boosting and rtmutex boosting
can continue to coexist.


Some features of PING futexes:
- Uses Proxy Execution.
- Optimistic spinning (can also be done in userspace, similarly to
  FUTEX_WAIT futexes).
- Allows for userspace stealing.
- Starvation prevention with handoff.


Some performance numbers (lock acquisition time, in nsec, lower is better):
(The numbers were kindly gathered by John on a machine with 11th Gen
Intel(R) Core(TM) i5.)
(How PING performs compared to PI and FUTEX_WAIT seems to vary a lot
based on hardware and ping_bench parameters, and the results look a
bit more impressive on my device :-), but I did not include them since
they are based on an older kernel version.)

With all fair tasks:
"ping_bench -a -w 50000 -s 1000 -t 16"

x FUTEX_PING
+ FUTEX_PI
* glibc pthread_mutex_t (using FUTEX_WAIT)
    N      Mean    Stddev     Min     25p     50p     75p     Max
x 159984  214377.3 859183.23      21   13703   15580   75343 1.15e+07
+ 159984 240690.75 23090.391  234635  237833  239962  241565 1.07e+06
Difference at 95.0% confidence
      26313.4 +/- 4211.65 [22101.8 30525.1]
      12.274363% +/- 1.9646%
      (z 12.2454 p-val 1.77893e-34 crit val 1.95996 se 2148.84)
* 159984 203941.44  14257763      17      20      21      21 1.21e+09
No difference proven at 95.0% confidence
      (z -0.292232 p-val 0.770109 crit val 1.95996 se 35710.9)

With priority inversions with a RT foreground task:
"ping_bench -t 8 -b 16 -r 1 -p -w 10000 -S 500"

x FUTEX_PING
+ FUTEX_PI
* glibc pthread_mutex_t (using FUTEX_WAIT)
    N      Mean    Stddev     Min     25p     50p     75p     Max
x 9999 615.55326 3387.2647      21      50      52      54 8.2e+04
+ 9999 701.18222 3450.3964      21      49      52      53 3.34e+04
No difference proven at 95.0% confidence
      (z 1.77087 p-val 0.0765815 crit val 1.95996 se 48.354)
* 9999 205935.36 2881211.5      24      53      54      55 1.24e+08
Difference at 95.0% confidence
      205320 +/- 56473.6 [148846 261793]
      33355.327862% +/- 9174.44%
      (z 7.1258 p-val 1.03486e-12 crit val 1.95996 se 28813.6)


The patches apply on top of Linus' HEAD.

Any feedback is welcome!


Suleiman Souhlal (12):
  sched: Abstract task_struct->blocked_on by locking primitive.
  futex: Switch PI futex to use p->pi_futex_lock instead of p->pi_lock.
  futex: Add "ping" parameter to pi_state management functions and
    export them.
  futex: Introduce stealable PI futex, FUTEX_*_PING.
  futex: Implement exit_ping_state_list().
  futex: Address aborting from futex_lock_ping() while owning
    ping_state.
  futex: Make FUTEX_*_PING use Proxy Execution.
  futex: Implement PING futex handoff.
  futex: Wake up donor in PING futex unlock.
  futex: Optimistic spinning for PING futexes.
  futex: Allow userspace stealing for PING futexes.
  tools/testing/futex: Add ping_bench, a tool for benchmarking futexes.

 include/linux/futex.h            |  22 +
 include/linux/futex_types.h      |   1 +
 include/linux/sched.h            |  53 ++-
 include/uapi/linux/futex.h       |   3 +
 init/init_task.c                 |   1 +
 kernel/fork.c                    |   3 +-
 kernel/futex/Makefile            |   2 +-
 kernel/futex/core.c              | 102 ++++-
 kernel/futex/futex.h             |  27 +-
 kernel/futex/pi.c                | 132 +++---
 kernel/futex/ping.c              | 707 +++++++++++++++++++++++++++++++
 kernel/futex/syscalls.c          |   6 +
 kernel/locking/mutex.c           |   8 +-
 kernel/sched/core.c              |  69 ++-
 kernel/sched/sched.h             |   2 +-
 tools/testing/futex/Makefile     |  13 +
 tools/testing/futex/ping_bench.c | 428 +++++++++++++++++++
 17 files changed, 1484 insertions(+), 95 deletions(-)
 create mode 100644 kernel/futex/ping.c
 create mode 100644 tools/testing/futex/Makefile
 create mode 100644 tools/testing/futex/ping_bench.c

-- 
2.55.0.1082.g2b9226bbc0-goog