Lines Matching +full:set +full:- +full:top
2 RT-mutex implementation design
12 Documentation/locking/rt-mutex.rst. Although this document does explain problems
22 ----------------------------
49 A ---+
52 C +----+
54 B +-------->
59 -------------------------
74 -----------
80 - The PI chain is an ordered series of locks and processes that cause
86 - In this document, to differentiate from locks that implement
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
111 on a mutex. This is the same as waiter->task.
114 - A list of processes that are blocked on a mutex.
116 top waiter
117 - The highest priority process waiting on a specific mutex.
119 top pi waiter
120 - The highest priority process waiting on one of the mutexes
129 --------
152 E->L4->D->L3->C->L2->B->L1->A
159 F->L5->B->L1->A
166 E->L4->D->L3->C->L2-+
168 +->B->L1->A
170 F->L5-+
173 also call it the Top of the chain) must be equal to or higher in priority
180 G->L2->B->L1->A
185 E->L4->D->L3->C-+
186 +->L2-+
188 G-+ +->B->L1->A
190 F->L5-+
197 ------------------
206 ------------
209 a tree of all top waiters of the mutexes that are owned by the process.
210 Note that this tree only holds the top waiters and not all waiters that are
213 The top of the task's PI tree is always the highest priority task that
216 at the top of this tree.
225 ---------------------
231 The following shows a locking order of L1->L2->L3, but may not actually
286 And thus we have the chain A->L1->B->L2->C->L3->D.
293 Now since mutexes can be defined by user-land applications, we don't want a DOS
302 ---------------------
305 mutex is not owned, this owner is set to NULL. Since all architectures
309 flag. It's set whenever there are waiters on a mutex.
311 See Documentation/locking/rt-mutex.rst for further details.
314 --------------
337 the architecture does not support CMPXCHG, then this macro is simply set
347 --------------------
358 the pi_waiters of a task holds an order by priority of all the top waiters
359 of all the mutexes that the task owns, we simply need to compare the top
377 by the task, so we only need to compare the priority of that top pi waiter
382 ----------------------------------------
398 is blocked, and a top_task as the top waiter of the mutex.
407 performed on it. This means that the task is set to the priority that it
418 ------------------------------------
458 If the task succeeds to acquire the lock, then the task is set as the
470 --------------------
473 the process. The "task" field is set to the process, and the "lock" field
480 previous top waiter process (if it exists) from the pi_waiters of the owner,
493 ---------------------
500 does, then it will take itself off the waiters tree and set itself back
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 -------------------
524 If the owner field has the "Has Waiters" bit set (or CMPXCHG is not available),
538 owner field is set to NULL, the wait_lock is released and nothing more is
543 On the wake up code, the pi_lock of the current owner is taken. The top
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