Documentation/locking/rt-mutex-design.rst

2 RT-mutex implementation design
12 Documentation/locking/rt-mutex.rst.  Although this document does explain problems
27 to use a resource that a lower priority process has (a mutex for example),
85 mutex
88            the PI locks will be called a mutex.
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.
134 mutex at a time.
155 another mutex L5 where B owns L5 and F is blocked on mutex L5.
161 Since a process may own more than one mutex, but never be blocked on more than
176 Also since a mutex may have more than one process blocked on it, we can
178 blocked on mutex L2::
196 Mutex Waiters Tree
199 Every mutex keeps track of all the waiters that are blocked on itself. The
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
214 is waiting on a mutex that is owned by the task.  So if the task has
301 Mutex owner and flags
304 The mutex structure contains a pointer to the owner of the mutex.  If the
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.
372 process has just blocked on a mutex owned by the task, rt_mutex_adjust_prio
374 were for some reason to leave the mutex (timeout or signal), this same function
376 always contains the highest priority task that is waiting on a mutex owned
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
396 that is the process's waiter struct that is blocked on the mutex (although this
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.
417 Taking of a mutex (The walk through)
421 taking a mutex.
423 The first thing that is tried is the fast taking of the mutex.  This is
425 fails).  Only when the owner field of the mutex is NULL can the lock be
434 the task on the waiters tree of the mutex, and if need be, the pi_waiters
437 The wait_lock of the mutex is taken since the slow path of unlocking the
438 mutex also takes this lock.
444 try_to_take_rt_mutex is used every time the task tries to grab a mutex in the
446 the "Has Waiters" flag of the mutex's owner field. By setting this flag
447 now, the current owner of the mutex being contended for can't release the mutex
469 Task blocks on mutex
472 The accounting of a mutex and process is done with the waiter structure of
474 to the mutex.  The rbtree node of waiter are initialized to the processes
479 highest priority process currently waiting on this mutex, then we remove the
486 (or deadlock checking is on), we unlock the wait_lock of the mutex and go ahead
490 mutex (waiter "task" field is not NULL), then we go to sleep (call schedule).
506 The second case is only applicable for tasks that are grabbing a mutex
514 Unlocking the Mutex
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
519 "Has Waiters" flag of the mutex's owner, we use this to know if we need to
520 take the slow path when unlocking the mutex.  If the mutex doesn't have any
521 waiters, the owner field of the mutex would equal the current process and
522 the mutex can be unlocked by just replacing the owner field with NULL.
528 mutex.  This synchronizes the locking and unlocking of the mutex.
530 A check is made to see if the mutex has waiters or not.  On architectures that
531 do not have CMPXCHG, this is the location that the owner of the mutex will
534 in the slow path too.  If a waiter of a mutex woke up because of a signal
536 the grabbing of the wait_lock, the mutex may not have any waiters, thus the
537 owner still needs to make this check. If there are no waiters then the mutex
544 waiter of the lock is found and removed from the waiters tree of the mutex