1 ======================
2 Lightweight PI-futexes
3 ======================
4
5 We are calling them lightweight for 3 reasons:
6
7 - in the user-space fastpath a PI-enabled fut
8 (or any other PI complexity) at all. No reg
9 calls - just pure fast atomic ops in usersp
10
11 - even in the slowpath, the system call and s
12 similar to normal futexes.
13
14 - the in-kernel PI implementation is streamli
15 abstraction, with strict rules that keep th
16 relatively simple: only a single owner may
17 read-write lock support), only the owner ma
18 recursive locking, etc.
19
20 Priority Inheritance - why?
21 ---------------------------
22
23 The short reply: user-space PI helps achieving
24 user-space applications. In the best-case, it
25 determinism and well-bound latencies. Even in
26 improve the statistical distribution of lockin
27 delays.
28
29 The longer reply
30 ----------------
31
32 Firstly, sharing locks between multiple tasks
33 technique that often cannot be replaced with l
34 can see it in the kernel [which is a quite com
35 lockless structures are rather the exception t
36 ratio of lockless vs. locky code for shared da
37 between 1:10 and 1:100. Lockless is hard, and
38 algorithms often endangers to ability to do ro
39 I.e. critical RT apps often choose lock struct
40 data structures, instead of lockless algorithm
41 cases (like shared hardware, or other resource
42 access is mathematically impossible.
43
44 Media players (such as Jack) are an example of
45 design with multiple tasks (with multiple prio
46 short-held locks: for example, a highprio audi
47 combined with medium-prio construct-audio-data
48 display-colory-stuff threads. Add video and de
49 we've got even more priority levels.
50
51 So once we accept that synchronization objects
52 unavoidable fact of life, and once we accept t
53 apps have a very fair expectation of being abl
54 to think about how to offer the option of a de
55 implementation to user-space.
56
57 Most of the technical counter-arguments agains
58 inheritance only apply to kernel-space locks.
59 different, there we cannot disable interrupts
60 non-preemptible in a critical section, so the
61 does not apply (user-space spinlocks have the
62 problems as other user-space locking construct
63 the only technique that currently enables good
64 locks (such as futex-based pthread mutexes) is
65
66 Currently (without PI), if a high-prio and a l
67 [this is a quite common scenario for most non-
68 even if all critical sections are coded carefu
69 (i.e. all critical sections are short in durat
70 limited number of instructions), the kernel ca
71 deterministic execution of the high-prio task:
72 could preempt the low-prio task while it holds
73 executes the critical section, and could delay
74
75 Implementation
76 --------------
77
78 As mentioned before, the userspace fastpath of
79 mutexes involves no kernel work at all - they
80 normal futex-based locks: a 0 value means unlo
81 means locked. (This is the same method as used
82 futexes.) Userspace uses atomic ops to lock/un
83 entering the kernel.
84
85 To handle the slowpath, we have added two new
86
87 - FUTEX_LOCK_PI
88 - FUTEX_UNLOCK_PI
89
90 If the lock-acquire fastpath fails, [i.e. an a
91 TID fails], then FUTEX_LOCK_PI is called. The
92 remaining work: if there is no futex-queue att
93 yet then the code looks up the task that owns
94 own TID into the futex value], and attaches a
95 the futex-queue. The pi_state includes an rt-m
96 kernel-based synchronization object. The 'othe
97 of the rt-mutex, and the FUTEX_WAITERS bit is
98 futex value. Then this task tries to lock the
99 blocks. Once it returns, it has the mutex acqu
100 futex value to its own TID and returns. Usersp
101 perform - it now owns the lock, and futex valu
102 FUTEX_WAITERS|TID.
103
104 If the unlock side fastpath succeeds, [i.e. us
105 TID -> 0 atomic transition of the futex value]
106 triggered.
107
108 If the unlock fastpath fails (because the FUTE
109 then FUTEX_UNLOCK_PI is called, and the kernel
110 behalf of userspace - and it also unlocks the
111 pi_state->rt_mutex and thus wakes up any poten
112
113 Note that under this approach, contrary to pre
114 there is no prior 'registration' of a PI-futex
115 possible anyway, due to existing ABI propertie
116
117 Also, under this scheme, 'robustness' and 'PI'
118 properties of futexes, and all four combinatio
119 robust-futex, PI-futex, robust+PI-futex.
120
121 More details about priority inheritance can be
122 Documentation/locking/rt-mutex.rst.
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.