^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1) Runtime locking correctness validator
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 2) =====================================
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 3)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 4) started by Ingo Molnar <mingo@redhat.com>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 5)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 6) additions by Arjan van de Ven <arjan@linux.intel.com>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 7)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 8) Lock-class
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 9) ----------
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 10)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 11) The basic object the validator operates upon is a 'class' of locks.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 12)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 13) A class of locks is a group of locks that are logically the same with
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 14) respect to locking rules, even if the locks may have multiple (possibly
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 15) tens of thousands of) instantiations. For example a lock in the inode
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 16) struct is one class, while each inode has its own instantiation of that
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 17) lock class.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 18)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 19) The validator tracks the 'usage state' of lock-classes, and it tracks
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 20) the dependencies between different lock-classes. Lock usage indicates
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 21) how a lock is used with regard to its IRQ contexts, while lock
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 22) dependency can be understood as lock order, where L1 -> L2 suggests that
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 23) a task is attempting to acquire L2 while holding L1. From lockdep's
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 24) perspective, the two locks (L1 and L2) are not necessarily related; that
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 25) dependency just means the order ever happened. The validator maintains a
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 26) continuing effort to prove lock usages and dependencies are correct or
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 27) the validator will shoot a splat if incorrect.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 28)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 29) A lock-class's behavior is constructed by its instances collectively:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 30) when the first instance of a lock-class is used after bootup the class
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 31) gets registered, then all (subsequent) instances will be mapped to the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 32) class and hence their usages and dependecies will contribute to those of
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 33) the class. A lock-class does not go away when a lock instance does, but
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 34) it can be removed if the memory space of the lock class (static or
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 35) dynamic) is reclaimed, this happens for example when a module is
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 36) unloaded or a workqueue is destroyed.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 37)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 38) State
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 39) -----
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 40)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 41) The validator tracks lock-class usage history and divides the usage into
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 42) (4 usages * n STATEs + 1) categories:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 43)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 44) where the 4 usages can be:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 45)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 46) - 'ever held in STATE context'
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 47) - 'ever held as readlock in STATE context'
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 48) - 'ever held with STATE enabled'
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 49) - 'ever held as readlock with STATE enabled'
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 50)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 51) where the n STATEs are coded in kernel/locking/lockdep_states.h and as of
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 52) now they include:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 53)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 54) - hardirq
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 55) - softirq
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 56)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 57) where the last 1 category is:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 58)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 59) - 'ever used' [ == !unused ]
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 60)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 61) When locking rules are violated, these usage bits are presented in the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 62) locking error messages, inside curlies, with a total of 2 * n STATEs bits.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 63) A contrived example::
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 64)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 65) modprobe/2287 is trying to acquire lock:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 66) (&sio_locks[i].lock){-.-.}, at: [<c02867fd>] mutex_lock+0x21/0x24
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 67)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 68) but task is already holding lock:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 69) (&sio_locks[i].lock){-.-.}, at: [<c02867fd>] mutex_lock+0x21/0x24
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 70)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 71)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 72) For a given lock, the bit positions from left to right indicate the usage
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 73) of the lock and readlock (if exists), for each of the n STATEs listed
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 74) above respectively, and the character displayed at each bit position
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 75) indicates:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 76)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 77) === ===================================================
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 78) '.' acquired while irqs disabled and not in irq context
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 79) '-' acquired in irq context
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 80) '+' acquired with irqs enabled
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 81) '?' acquired in irq context with irqs enabled.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 82) === ===================================================
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 83)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 84) The bits are illustrated with an example::
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 85)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 86) (&sio_locks[i].lock){-.-.}, at: [<c02867fd>] mutex_lock+0x21/0x24
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 87) ||||
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 88) ||| \-> softirq disabled and not in softirq context
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 89) || \--> acquired in softirq context
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 90) | \---> hardirq disabled and not in hardirq context
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 91) \----> acquired in hardirq context
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 92)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 93)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 94) For a given STATE, whether the lock is ever acquired in that STATE
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 95) context and whether that STATE is enabled yields four possible cases as
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 96) shown in the table below. The bit character is able to indicate which
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 97) exact case is for the lock as of the reporting time.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 98)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 99) +--------------+-------------+--------------+
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 100) | | irq enabled | irq disabled |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 101) +--------------+-------------+--------------+
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 102) | ever in irq | '?' | '-' |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 103) +--------------+-------------+--------------+
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 104) | never in irq | '+' | '.' |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 105) +--------------+-------------+--------------+
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 106)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 107) The character '-' suggests irq is disabled because if otherwise the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 108) charactor '?' would have been shown instead. Similar deduction can be
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 109) applied for '+' too.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 110)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 111) Unused locks (e.g., mutexes) cannot be part of the cause of an error.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 112)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 113)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 114) Single-lock state rules:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 115) ------------------------
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 116)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 117) A lock is irq-safe means it was ever used in an irq context, while a lock
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 118) is irq-unsafe means it was ever acquired with irq enabled.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 119)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 120) A softirq-unsafe lock-class is automatically hardirq-unsafe as well. The
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 121) following states must be exclusive: only one of them is allowed to be set
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 122) for any lock-class based on its usage::
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 123)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 124) <hardirq-safe> or <hardirq-unsafe>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 125) <softirq-safe> or <softirq-unsafe>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 126)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 127) This is because if a lock can be used in irq context (irq-safe) then it
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 128) cannot be ever acquired with irq enabled (irq-unsafe). Otherwise, a
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 129) deadlock may happen. For example, in the scenario that after this lock
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 130) was acquired but before released, if the context is interrupted this
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 131) lock will be attempted to acquire twice, which creates a deadlock,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 132) referred to as lock recursion deadlock.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 133)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 134) The validator detects and reports lock usage that violates these
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 135) single-lock state rules.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 136)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 137) Multi-lock dependency rules:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 138) ----------------------------
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 139)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 140) The same lock-class must not be acquired twice, because this could lead
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 141) to lock recursion deadlocks.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 142)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 143) Furthermore, two locks can not be taken in inverse order::
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 144)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 145) <L1> -> <L2>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 146) <L2> -> <L1>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 147)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 148) because this could lead to a deadlock - referred to as lock inversion
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 149) deadlock - as attempts to acquire the two locks form a circle which
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 150) could lead to the two contexts waiting for each other permanently. The
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 151) validator will find such dependency circle in arbitrary complexity,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 152) i.e., there can be any other locking sequence between the acquire-lock
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 153) operations; the validator will still find whether these locks can be
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 154) acquired in a circular fashion.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 155)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 156) Furthermore, the following usage based lock dependencies are not allowed
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 157) between any two lock-classes::
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 158)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 159) <hardirq-safe> -> <hardirq-unsafe>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 160) <softirq-safe> -> <softirq-unsafe>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 161)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 162) The first rule comes from the fact that a hardirq-safe lock could be
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 163) taken by a hardirq context, interrupting a hardirq-unsafe lock - and
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 164) thus could result in a lock inversion deadlock. Likewise, a softirq-safe
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 165) lock could be taken by an softirq context, interrupting a softirq-unsafe
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 166) lock.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 167)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 168) The above rules are enforced for any locking sequence that occurs in the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 169) kernel: when acquiring a new lock, the validator checks whether there is
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 170) any rule violation between the new lock and any of the held locks.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 171)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 172) When a lock-class changes its state, the following aspects of the above
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 173) dependency rules are enforced:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 174)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 175) - if a new hardirq-safe lock is discovered, we check whether it
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 176) took any hardirq-unsafe lock in the past.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 177)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 178) - if a new softirq-safe lock is discovered, we check whether it took
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 179) any softirq-unsafe lock in the past.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 180)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 181) - if a new hardirq-unsafe lock is discovered, we check whether any
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 182) hardirq-safe lock took it in the past.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 183)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 184) - if a new softirq-unsafe lock is discovered, we check whether any
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 185) softirq-safe lock took it in the past.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 186)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 187) (Again, we do these checks too on the basis that an interrupt context
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 188) could interrupt _any_ of the irq-unsafe or hardirq-unsafe locks, which
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 189) could lead to a lock inversion deadlock - even if that lock scenario did
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 190) not trigger in practice yet.)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 191)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 192) Exception: Nested data dependencies leading to nested locking
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 193) -------------------------------------------------------------
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 194)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 195) There are a few cases where the Linux kernel acquires more than one
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 196) instance of the same lock-class. Such cases typically happen when there
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 197) is some sort of hierarchy within objects of the same type. In these
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 198) cases there is an inherent "natural" ordering between the two objects
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 199) (defined by the properties of the hierarchy), and the kernel grabs the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 200) locks in this fixed order on each of the objects.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 201)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 202) An example of such an object hierarchy that results in "nested locking"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 203) is that of a "whole disk" block-dev object and a "partition" block-dev
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 204) object; the partition is "part of" the whole device and as long as one
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 205) always takes the whole disk lock as a higher lock than the partition
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 206) lock, the lock ordering is fully correct. The validator does not
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 207) automatically detect this natural ordering, as the locking rule behind
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 208) the ordering is not static.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 209)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 210) In order to teach the validator about this correct usage model, new
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 211) versions of the various locking primitives were added that allow you to
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 212) specify a "nesting level". An example call, for the block device mutex,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 213) looks like this::
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 214)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 215) enum bdev_bd_mutex_lock_class
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 216) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 217) BD_MUTEX_NORMAL,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 218) BD_MUTEX_WHOLE,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 219) BD_MUTEX_PARTITION
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 220) };
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 221)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 222) mutex_lock_nested(&bdev->bd_contains->bd_mutex, BD_MUTEX_PARTITION);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 223)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 224) In this case the locking is done on a bdev object that is known to be a
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 225) partition.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 226)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 227) The validator treats a lock that is taken in such a nested fashion as a
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 228) separate (sub)class for the purposes of validation.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 229)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 230) Note: When changing code to use the _nested() primitives, be careful and
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 231) check really thoroughly that the hierarchy is correctly mapped; otherwise
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 232) you can get false positives or false negatives.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 233)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 234) Annotations
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 235) -----------
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 236)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 237) Two constructs can be used to annotate and check where and if certain locks
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 238) must be held: lockdep_assert_held*(&lock) and lockdep_*pin_lock(&lock).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 239)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 240) As the name suggests, lockdep_assert_held* family of macros assert that a
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 241) particular lock is held at a certain time (and generate a WARN() otherwise).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 242) This annotation is largely used all over the kernel, e.g. kernel/sched/
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 243) core.c::
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 244)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 245) void update_rq_clock(struct rq *rq)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 246) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 247) s64 delta;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 248)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 249) lockdep_assert_held(&rq->lock);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 250) [...]
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 251) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 252)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 253) where holding rq->lock is required to safely update a rq's clock.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 254)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 255) The other family of macros is lockdep_*pin_lock(), which is admittedly only
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 256) used for rq->lock ATM. Despite their limited adoption these annotations
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 257) generate a WARN() if the lock of interest is "accidentally" unlocked. This turns
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 258) out to be especially helpful to debug code with callbacks, where an upper
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 259) layer assumes a lock remains taken, but a lower layer thinks it can maybe drop
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 260) and reacquire the lock ("unwittingly" introducing races). lockdep_pin_lock()
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 261) returns a 'struct pin_cookie' that is then used by lockdep_unpin_lock() to check
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 262) that nobody tampered with the lock, e.g. kernel/sched/sched.h::
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 263)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 264) static inline void rq_pin_lock(struct rq *rq, struct rq_flags *rf)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 265) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 266) rf->cookie = lockdep_pin_lock(&rq->lock);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 267) [...]
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 268) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 269)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 270) static inline void rq_unpin_lock(struct rq *rq, struct rq_flags *rf)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 271) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 272) [...]
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 273) lockdep_unpin_lock(&rq->lock, rf->cookie);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 274) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 275)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 276) While comments about locking requirements might provide useful information,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 277) the runtime checks performed by annotations are invaluable when debugging
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 278) locking problems and they carry the same level of details when inspecting
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 279) code. Always prefer annotations when in doubt!
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 280)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 281) Proof of 100% correctness:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 282) --------------------------
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 283)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 284) The validator achieves perfect, mathematical 'closure' (proof of locking
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 285) correctness) in the sense that for every simple, standalone single-task
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 286) locking sequence that occurred at least once during the lifetime of the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 287) kernel, the validator proves it with a 100% certainty that no
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 288) combination and timing of these locking sequences can cause any class of
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 289) lock related deadlock. [1]_
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 290)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 291) I.e. complex multi-CPU and multi-task locking scenarios do not have to
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 292) occur in practice to prove a deadlock: only the simple 'component'
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 293) locking chains have to occur at least once (anytime, in any
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 294) task/context) for the validator to be able to prove correctness. (For
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 295) example, complex deadlocks that would normally need more than 3 CPUs and
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 296) a very unlikely constellation of tasks, irq-contexts and timings to
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 297) occur, can be detected on a plain, lightly loaded single-CPU system as
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 298) well!)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 299)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 300) This radically decreases the complexity of locking related QA of the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 301) kernel: what has to be done during QA is to trigger as many "simple"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 302) single-task locking dependencies in the kernel as possible, at least
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 303) once, to prove locking correctness - instead of having to trigger every
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 304) possible combination of locking interaction between CPUs, combined with
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 305) every possible hardirq and softirq nesting scenario (which is impossible
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 306) to do in practice).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 307)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 308) .. [1]
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 309)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 310) assuming that the validator itself is 100% correct, and no other
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 311) part of the system corrupts the state of the validator in any way.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 312) We also assume that all NMI/SMM paths [which could interrupt
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 313) even hardirq-disabled codepaths] are correct and do not interfere
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 314) with the validator. We also assume that the 64-bit 'chain hash'
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 315) value is unique for every lock-chain in the system. Also, lock
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 316) recursion must not be higher than 20.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 317)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 318) Performance:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 319) ------------
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 320)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 321) The above rules require **massive** amounts of runtime checking. If we did
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 322) that for every lock taken and for every irqs-enable event, it would
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 323) render the system practically unusably slow. The complexity of checking
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 324) is O(N^2), so even with just a few hundred lock-classes we'd have to do
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 325) tens of thousands of checks for every event.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 326)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 327) This problem is solved by checking any given 'locking scenario' (unique
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 328) sequence of locks taken after each other) only once. A simple stack of
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 329) held locks is maintained, and a lightweight 64-bit hash value is
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 330) calculated, which hash is unique for every lock chain. The hash value,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 331) when the chain is validated for the first time, is then put into a hash
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 332) table, which hash-table can be checked in a lockfree manner. If the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 333) locking chain occurs again later on, the hash table tells us that we
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 334) don't have to validate the chain again.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 335)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 336) Troubleshooting:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 337) ----------------
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 338)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 339) The validator tracks a maximum of MAX_LOCKDEP_KEYS number of lock classes.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 340) Exceeding this number will trigger the following lockdep warning::
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 341)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 342) (DEBUG_LOCKS_WARN_ON(id >= MAX_LOCKDEP_KEYS))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 343)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 344) By default, MAX_LOCKDEP_KEYS is currently set to 8191, and typical
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 345) desktop systems have less than 1,000 lock classes, so this warning
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 346) normally results from lock-class leakage or failure to properly
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 347) initialize locks. These two problems are illustrated below:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 348)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 349) 1. Repeated module loading and unloading while running the validator
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 350) will result in lock-class leakage. The issue here is that each
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 351) load of the module will create a new set of lock classes for
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 352) that module's locks, but module unloading does not remove old
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 353) classes (see below discussion of reuse of lock classes for why).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 354) Therefore, if that module is loaded and unloaded repeatedly,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 355) the number of lock classes will eventually reach the maximum.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 356)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 357) 2. Using structures such as arrays that have large numbers of
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 358) locks that are not explicitly initialized. For example,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 359) a hash table with 8192 buckets where each bucket has its own
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 360) spinlock_t will consume 8192 lock classes -unless- each spinlock
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 361) is explicitly initialized at runtime, for example, using the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 362) run-time spin_lock_init() as opposed to compile-time initializers
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 363) such as __SPIN_LOCK_UNLOCKED(). Failure to properly initialize
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 364) the per-bucket spinlocks would guarantee lock-class overflow.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 365) In contrast, a loop that called spin_lock_init() on each lock
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 366) would place all 8192 locks into a single lock class.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 367)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 368) The moral of this story is that you should always explicitly
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 369) initialize your locks.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 370)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 371) One might argue that the validator should be modified to allow
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 372) lock classes to be reused. However, if you are tempted to make this
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 373) argument, first review the code and think through the changes that would
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 374) be required, keeping in mind that the lock classes to be removed are
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 375) likely to be linked into the lock-dependency graph. This turns out to
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 376) be harder to do than to say.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 377)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 378) Of course, if you do run out of lock classes, the next thing to do is
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 379) to find the offending lock classes. First, the following command gives
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 380) you the number of lock classes currently in use along with the maximum::
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 381)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 382) grep "lock-classes" /proc/lockdep_stats
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 383)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 384) This command produces the following output on a modest system::
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 385)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 386) lock-classes: 748 [max: 8191]
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 387)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 388) If the number allocated (748 above) increases continually over time,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 389) then there is likely a leak. The following command can be used to
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 390) identify the leaking lock classes::
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 391)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 392) grep "BD" /proc/lockdep
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 393)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 394) Run the command and save the output, then compare against the output from
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 395) a later run of this command to identify the leakers. This same output
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 396) can also help you find situations where runtime lock initialization has
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 397) been omitted.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 398)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 399) Recursive read locks:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 400) ---------------------
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 401) The whole of the rest document tries to prove a certain type of cycle is equivalent
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 402) to deadlock possibility.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 403)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 404) There are three types of lockers: writers (i.e. exclusive lockers, like
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 405) spin_lock() or write_lock()), non-recursive readers (i.e. shared lockers, like
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 406) down_read()) and recursive readers (recursive shared lockers, like rcu_read_lock()).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 407) And we use the following notations of those lockers in the rest of the document:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 408)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 409) W or E: stands for writers (exclusive lockers).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 410) r: stands for non-recursive readers.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 411) R: stands for recursive readers.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 412) S: stands for all readers (non-recursive + recursive), as both are shared lockers.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 413) N: stands for writers and non-recursive readers, as both are not recursive.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 414)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 415) Obviously, N is "r or W" and S is "r or R".
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 416)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 417) Recursive readers, as their name indicates, are the lockers allowed to acquire
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 418) even inside the critical section of another reader of the same lock instance,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 419) in other words, allowing nested read-side critical sections of one lock instance.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 420)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 421) While non-recursive readers will cause a self deadlock if trying to acquire inside
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 422) the critical section of another reader of the same lock instance.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 423)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 424) The difference between recursive readers and non-recursive readers is because:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 425) recursive readers get blocked only by a write lock *holder*, while non-recursive
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 426) readers could get blocked by a write lock *waiter*. Considering the follow
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 427) example::
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 428)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 429) TASK A: TASK B:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 430)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 431) read_lock(X);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 432) write_lock(X);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 433) read_lock_2(X);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 434)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 435) Task A gets the reader (no matter whether recursive or non-recursive) on X via
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 436) read_lock() first. And when task B tries to acquire writer on X, it will block
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 437) and become a waiter for writer on X. Now if read_lock_2() is recursive readers,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 438) task A will make progress, because writer waiters don't block recursive readers,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 439) and there is no deadlock. However, if read_lock_2() is non-recursive readers,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 440) it will get blocked by writer waiter B, and cause a self deadlock.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 441)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 442) Block conditions on readers/writers of the same lock instance:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 443) --------------------------------------------------------------
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 444) There are simply four block conditions:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 445)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 446) 1. Writers block other writers.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 447) 2. Readers block writers.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 448) 3. Writers block both recursive readers and non-recursive readers.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 449) 4. And readers (recursive or not) don't block other recursive readers but
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 450) may block non-recursive readers (because of the potential co-existing
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 451) writer waiters)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 452)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 453) Block condition matrix, Y means the row blocks the column, and N means otherwise.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 454)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 455) +---+---+---+---+
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 456) | | E | r | R |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 457) +---+---+---+---+
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 458) | E | Y | Y | Y |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 459) +---+---+---+---+
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 460) | r | Y | Y | N |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 461) +---+---+---+---+
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 462) | R | Y | Y | N |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 463) +---+---+---+---+
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 464)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 465) (W: writers, r: non-recursive readers, R: recursive readers)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 466)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 467)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 468) acquired recursively. Unlike non-recursive read locks, recursive read locks
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 469) only get blocked by current write lock *holders* other than write lock
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 470) *waiters*, for example::
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 471)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 472) TASK A: TASK B:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 473)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 474) read_lock(X);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 475)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 476) write_lock(X);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 477)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 478) read_lock(X);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 479)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 480) is not a deadlock for recursive read locks, as while the task B is waiting for
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 481) the lock X, the second read_lock() doesn't need to wait because it's a recursive
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 482) read lock. However if the read_lock() is non-recursive read lock, then the above
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 483) case is a deadlock, because even if the write_lock() in TASK B cannot get the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 484) lock, but it can block the second read_lock() in TASK A.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 485)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 486) Note that a lock can be a write lock (exclusive lock), a non-recursive read
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 487) lock (non-recursive shared lock) or a recursive read lock (recursive shared
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 488) lock), depending on the lock operations used to acquire it (more specifically,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 489) the value of the 'read' parameter for lock_acquire()). In other words, a single
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 490) lock instance has three types of acquisition depending on the acquisition
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 491) functions: exclusive, non-recursive read, and recursive read.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 492)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 493) To be concise, we call that write locks and non-recursive read locks as
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 494) "non-recursive" locks and recursive read locks as "recursive" locks.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 495)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 496) Recursive locks don't block each other, while non-recursive locks do (this is
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 497) even true for two non-recursive read locks). A non-recursive lock can block the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 498) corresponding recursive lock, and vice versa.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 499)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 500) A deadlock case with recursive locks involved is as follow::
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 501)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 502) TASK A: TASK B:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 503)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 504) read_lock(X);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 505) read_lock(Y);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 506) write_lock(Y);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 507) write_lock(X);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 508)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 509) Task A is waiting for task B to read_unlock() Y and task B is waiting for task
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 510) A to read_unlock() X.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 511)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 512) Dependency types and strong dependency paths:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 513) ---------------------------------------------
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 514) Lock dependencies record the orders of the acquisitions of a pair of locks, and
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 515) because there are 3 types for lockers, there are, in theory, 9 types of lock
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 516) dependencies, but we can show that 4 types of lock dependencies are enough for
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 517) deadlock detection.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 518)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 519) For each lock dependency::
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 520)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 521) L1 -> L2
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 522)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 523) , which means lockdep has seen L1 held before L2 held in the same context at runtime.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 524) And in deadlock detection, we care whether we could get blocked on L2 with L1 held,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 525) IOW, whether there is a locker L3 that L1 blocks L3 and L2 gets blocked by L3. So
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 526) we only care about 1) what L1 blocks and 2) what blocks L2. As a result, we can combine
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 527) recursive readers and non-recursive readers for L1 (as they block the same types) and
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 528) we can combine writers and non-recursive readers for L2 (as they get blocked by the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 529) same types).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 530)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 531) With the above combination for simplification, there are 4 types of dependency edges
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 532) in the lockdep graph:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 533)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 534) 1) -(ER)->:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 535) exclusive writer to recursive reader dependency, "X -(ER)-> Y" means
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 536) X -> Y and X is a writer and Y is a recursive reader.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 537)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 538) 2) -(EN)->:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 539) exclusive writer to non-recursive locker dependency, "X -(EN)-> Y" means
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 540) X -> Y and X is a writer and Y is either a writer or non-recursive reader.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 541)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 542) 3) -(SR)->:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 543) shared reader to recursive reader dependency, "X -(SR)-> Y" means
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 544) X -> Y and X is a reader (recursive or not) and Y is a recursive reader.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 545)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 546) 4) -(SN)->:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 547) shared reader to non-recursive locker dependency, "X -(SN)-> Y" means
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 548) X -> Y and X is a reader (recursive or not) and Y is either a writer or
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 549) non-recursive reader.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 550)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 551) Note that given two locks, they may have multiple dependencies between them,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 552) for example::
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 553)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 554) TASK A:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 555)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 556) read_lock(X);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 557) write_lock(Y);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 558) ...
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 559)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 560) TASK B:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 561)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 562) write_lock(X);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 563) write_lock(Y);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 564)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 565) , we have both X -(SN)-> Y and X -(EN)-> Y in the dependency graph.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 566)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 567) We use -(xN)-> to represent edges that are either -(EN)-> or -(SN)->, the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 568) similar for -(Ex)->, -(xR)-> and -(Sx)->
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 569)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 570) A "path" is a series of conjunct dependency edges in the graph. And we define a
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 571) "strong" path, which indicates the strong dependency throughout each dependency
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 572) in the path, as the path that doesn't have two conjunct edges (dependencies) as
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 573) -(xR)-> and -(Sx)->. In other words, a "strong" path is a path from a lock
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 574) walking to another through the lock dependencies, and if X -> Y -> Z is in the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 575) path (where X, Y, Z are locks), and the walk from X to Y is through a -(SR)-> or
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 576) -(ER)-> dependency, the walk from Y to Z must not be through a -(SN)-> or
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 577) -(SR)-> dependency.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 578)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 579) We will see why the path is called "strong" in next section.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 580)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 581) Recursive Read Deadlock Detection:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 582) ----------------------------------
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 583)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 584) We now prove two things:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 585)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 586) Lemma 1:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 587)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 588) If there is a closed strong path (i.e. a strong circle), then there is a
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 589) combination of locking sequences that causes deadlock. I.e. a strong circle is
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 590) sufficient for deadlock detection.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 591)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 592) Lemma 2:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 593)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 594) If there is no closed strong path (i.e. strong circle), then there is no
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 595) combination of locking sequences that could cause deadlock. I.e. strong
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 596) circles are necessary for deadlock detection.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 597)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 598) With these two Lemmas, we can easily say a closed strong path is both sufficient
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 599) and necessary for deadlocks, therefore a closed strong path is equivalent to
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 600) deadlock possibility. As a closed strong path stands for a dependency chain that
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 601) could cause deadlocks, so we call it "strong", considering there are dependency
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 602) circles that won't cause deadlocks.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 603)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 604) Proof for sufficiency (Lemma 1):
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 605)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 606) Let's say we have a strong circle::
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 607)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 608) L1 -> L2 ... -> Ln -> L1
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 609)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 610) , which means we have dependencies::
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 611)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 612) L1 -> L2
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 613) L2 -> L3
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 614) ...
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 615) Ln-1 -> Ln
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 616) Ln -> L1
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 617)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 618) We now can construct a combination of locking sequences that cause deadlock:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 619)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 620) Firstly let's make one CPU/task get the L1 in L1 -> L2, and then another get
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 621) the L2 in L2 -> L3, and so on. After this, all of the Lx in Lx -> Lx+1 are
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 622) held by different CPU/tasks.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 623)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 624) And then because we have L1 -> L2, so the holder of L1 is going to acquire L2
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 625) in L1 -> L2, however since L2 is already held by another CPU/task, plus L1 ->
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 626) L2 and L2 -> L3 are not -(xR)-> and -(Sx)-> (the definition of strong), which
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 627) means either L2 in L1 -> L2 is a non-recursive locker (blocked by anyone) or
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 628) the L2 in L2 -> L3, is writer (blocking anyone), therefore the holder of L1
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 629) cannot get L2, it has to wait L2's holder to release.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 630)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 631) Moreover, we can have a similar conclusion for L2's holder: it has to wait L3's
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 632) holder to release, and so on. We now can prove that Lx's holder has to wait for
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 633) Lx+1's holder to release, and note that Ln+1 is L1, so we have a circular
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 634) waiting scenario and nobody can get progress, therefore a deadlock.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 635)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 636) Proof for necessary (Lemma 2):
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 637)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 638) Lemma 2 is equivalent to: If there is a deadlock scenario, then there must be a
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 639) strong circle in the dependency graph.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 640)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 641) According to Wikipedia[1], if there is a deadlock, then there must be a circular
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 642) waiting scenario, means there are N CPU/tasks, where CPU/task P1 is waiting for
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 643) a lock held by P2, and P2 is waiting for a lock held by P3, ... and Pn is waiting
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 644) for a lock held by P1. Let's name the lock Px is waiting as Lx, so since P1 is waiting
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 645) for L1 and holding Ln, so we will have Ln -> L1 in the dependency graph. Similarly,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 646) we have L1 -> L2, L2 -> L3, ..., Ln-1 -> Ln in the dependency graph, which means we
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 647) have a circle::
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 648)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 649) Ln -> L1 -> L2 -> ... -> Ln
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 650)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 651) , and now let's prove the circle is strong:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 652)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 653) For a lock Lx, Px contributes the dependency Lx-1 -> Lx and Px+1 contributes
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 654) the dependency Lx -> Lx+1, and since Px is waiting for Px+1 to release Lx,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 655) so it's impossible that Lx on Px+1 is a reader and Lx on Px is a recursive
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 656) reader, because readers (no matter recursive or not) don't block recursive
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 657) readers, therefore Lx-1 -> Lx and Lx -> Lx+1 cannot be a -(xR)-> -(Sx)-> pair,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 658) and this is true for any lock in the circle, therefore, the circle is strong.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 659)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 660) References:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 661) -----------
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 662) [1]: https://en.wikipedia.org/wiki/Deadlock
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 663) [2]: Shibu, K. (2009). Intro To Embedded Systems (1st ed.). Tata McGraw-Hill
Orange Pi5 kernel
Deprecated Linux kernel 5.10.110 for OrangePi 5/5B/5+ boards
3 Commits
0 Branches
0 Tags