Lines Matching +full:- +full:a
2 RT-mutex implementation design
12 Documentation/locking/rt-mutex.rst. Although this document does explain problems
22 ----------------------------
24 Priority inversion is when a lower priority process executes while a higher
26 most of the time it can't be helped. Anytime a high priority process wants
27 to use a resource that a lower priority process has (a mutex for example),
29 with the resource. This is a priority inversion. What we want to prevent
31 priority process is prevented from running by a lower priority process for
35 processes, let's call them processes A, B, and C, where A is the highest
36 priority process, C is the lowest, and B is in between. A tries to grab a lock
38 meantime, B executes, and since B is of a higher priority than C, it preempts C,
39 but by doing so, it is in fact preempting A which is a higher priority process.
40 Now there's no way of knowing how long A will be sleeping waiting for C
41 to release the lock, because for all we know, B is a CPU hog and will
42 never give C a chance to release the lock. This is called unbounded priority
45 Here's a little ASCII art to show the problem::
49 A ---+
52 C +----+
54 B +-------->
55 B now keeps A from running.
59 -------------------------
64 PI is where a process inherits the priority of another process if the other
65 process blocks on a lock owned by the current process. To make this easier
66 to understand, let's use the previous example, with processes A, B, and C again.
68 This time, when A blocks on the lock owned by C, C would inherit the priority
69 of A. So now if B becomes runnable, it would not preempt C, since C now has
70 the high priority of A. As soon as C releases the lock, it loses its
71 inherited priority, and A then can continue with the resource that C had.
74 -----------
80 - The PI chain is an ordered series of locks and processes that cause
81 processes to inherit priorities from a previous process that is
86 - In this document, to differentiate from locks that implement
88 the PI locks will be called a mutex.
91 - In this document from now on, I will use the term lock when
98 - Same as lock above.
101 - A waiter is a struct that is stored on the stack of a blocked
103 a process being blocked on the mutex, it is fine to allocate
105 structure holds a pointer to the task, as well as the mutex that
107 place the task in the waiters rbtree of a mutex as well as the
108 pi_waiters rbtree of a mutex owner task (described below).
111 on a mutex. This is the same as waiter->task.
114 - A list of processes that are blocked on a mutex.
117 - The highest priority process waiting on a specific mutex.
120 - The highest priority process waiting on one of the mutexes
121 that a specific process owns.
129 --------
131 The PI chain is a list of processes and mutexes that may cause priority
132 inheritance to take place. Multiple chains may converge, but a chain
133 would never diverge, since a process can't be blocked on more than one
134 mutex at a time.
138 Process: A, B, C, D, E
141 A owns: L1
152 E->L4->D->L3->C->L2->B->L1->A
159 F->L5->B->L1->A
161 Since a process may own more than one mutex, but never be blocked on more than
166 E->L4->D->L3->C->L2-+
168 +->B->L1->A
170 F->L5-+
176 Also since a mutex may have more than one process blocked on it, we can
180 G->L2->B->L1->A
185 E->L4->D->L3->C-+
186 +->L2-+
188 G-+ +->B->L1->A
190 F->L5-+
193 the chain (A and B in this example), must have their priorities increased
197 ------------------
200 mutex has a rbtree to store these waiters by priority. This tree is protected
201 by a spin lock that is located in the struct of the mutex. This lock is called
206 ------------
209 a tree of all top waiters of the mutexes that are owned by the process.
214 is waiting on a mutex that is owned by the task. So if the task has
215 inherited a priority, it will always be the priority of the task that is
218 This tree is stored in the task structure of a process as a rbtree called
219 pi_waiters. It is protected by a spin lock also in the task structure,
225 ---------------------
231 The following shows a locking order of L1->L2->L3, but may not actually
275 Processes A, B, C, and D which run functions func1, func2, func3 and func4
276 respectively, and such that D runs first and A last. With D being preempted
277 in func4 in the "do something again" area, we have a locking that follows::
284 A blocked on L1
286 And thus we have the chain A->L1->B->L2->C->L3->D.
288 This gives us a PI depth of 4 (four processes), but looking at any of the
289 functions individually, it seems as though they only have at most a locking
293 Now since mutexes can be defined by user-land applications, we don't want a DOS
294 type of application that nests large amounts of mutexes to create a large
295 PI chain, and have the code holding spin locks while looking at a large
297 a maximum lock depth, but also only holds at most two different locks at a
302 ---------------------
304 The mutex structure contains a pointer to the owner of the mutex. If the
306 have the task structure on at least a two byte alignment (and if this is
308 significant bit to be used as a flag. Bit 0 is used as the "Has Waiters"
309 flag. It's set whenever there are waiters on a mutex.
311 See Documentation/locking/rt-mutex.rst for further details.
314 --------------
322 unsigned long _cmpxchg(unsigned long *A, unsigned long *B, unsigned long *C)
324 unsigned long T = *A;
325 if (*A == *B) {
326 *A = *C;
330 #define cmpxchg(a,b,c) _cmpxchg(&a,&b,&c)
332 This is really nice to have, since it allows you to only update a variable
334 the return value (the old value of A) is equal to B.
347 --------------------
349 The implementation of the PI code in rtmutex.c has several places that a
350 process must adjust its priority. With the help of the pi_waiters of a
358 the pi_waiters of a task holds an order by priority of all the top waiters
367 higher the priority. A "prio" of 5 is of higher priority than a
371 or decrease the priority of the task. In the case that a higher priority
372 process has just blocked on a mutex owned by the task, rt_mutex_adjust_prio
373 would increase/boost the task's priority. But if a higher priority task
376 always contains the highest priority task that is waiting on a mutex owned
382 ----------------------------------------
388 at most two locks at a time, and is very efficient.
393 rt_mutex_adjust_prio_chain is called with a task to be checked for PI
394 (de)boosting (the owner of a mutex that a process is blocking on), a flag to
395 check for deadlocking, the mutex that the task owns, a pointer to a waiter
397 parameter may be NULL for deboosting), a pointer to the mutex on which the task
398 is blocked, and a top_task as the top waiter of the mutex.
401 will try to stay at a high level.
417 Taking of a mutex (The walk through)
418 ------------------------------------
420 OK, now let's take a look at the detailed walk through of what happens when
421 taking a mutex.
444 try_to_take_rt_mutex is used every time the task tries to grab a mutex in the
470 --------------------
472 The accounting of a mutex and process is done with the waiter structure of
485 If the owner is also blocked on a lock, and had its pi_waiters changed
489 Now all locks are released, and if the current process is still blocked on a
493 ---------------------
495 The task can then wake up for a couple of reasons:
497 2) we received a signal or timeout
506 The second case is only applicable for tasks that are grabbing a mutex
507 that can wake up before getting the lock, either due to a signal or
508 a timeout (i.e. rt_mutex_timed_futex_lock()). When woken, it will try to
510 lock held, otherwise it will return with -EINTR if the task was woken
511 by a signal, or -ETIMEDOUT if it timed out.
515 -------------------
517 The unlocking of a mutex also has a fast path for those architectures with
518 CMPXCHG. Since the taking of a mutex on contention always sets the
530 A check is made to see if the mutex has waiters or not. On architectures that
532 determine if a waiter needs to be awoken or not. On architectures that
534 in the slow path too. If a waiter of a mutex woke up because of a signal
552 -------
558 -------
562 Updated: Alex Shi <alex.shi@linaro.org> - 7/6/2017
571 -------
573 This document was originally written for 2.6.17-rc3-mm1