sphinx.addnodesdocument)}( rawsourcechildren]( translations LanguagesNode)}(hhh](h pending_xref)}(hhh]docutils.nodesTextChinese (Simplified)}parenthsba attributes}(ids]classes]names]dupnames]backrefs] refdomainstdreftypedoc reftarget*/translations/zh_CN/locking/lockdep-designmodnameN classnameN refexplicitutagnamehhh ubh)}(hhh]hChinese (Traditional)}hh2sbah}(h]h ]h"]h$]h&] refdomainh)reftypeh+ reftarget*/translations/zh_TW/locking/lockdep-designmodnameN classnameN refexplicituh1hhh ubh)}(hhh]hItalian}hhFsbah}(h]h ]h"]h$]h&] refdomainh)reftypeh+ reftarget*/translations/it_IT/locking/lockdep-designmodnameN classnameN refexplicituh1hhh ubh)}(hhh]hJapanese}hhZsbah}(h]h ]h"]h$]h&] refdomainh)reftypeh+ reftarget*/translations/ja_JP/locking/lockdep-designmodnameN classnameN refexplicituh1hhh ubh)}(hhh]hKorean}hhnsbah}(h]h ]h"]h$]h&] refdomainh)reftypeh+ reftarget*/translations/ko_KR/locking/lockdep-designmodnameN classnameN refexplicituh1hhh ubh)}(hhh]hPortuguese (Brazilian)}hhsbah}(h]h ]h"]h$]h&] refdomainh)reftypeh+ reftarget*/translations/pt_BR/locking/lockdep-designmodnameN classnameN refexplicituh1hhh ubh)}(hhh]hSpanish}hhsbah}(h]h ]h"]h$]h&] refdomainh)reftypeh+ reftarget*/translations/sp_SP/locking/lockdep-designmodnameN classnameN refexplicituh1hhh ubeh}(h]h ]h"]h$]h&]current_languageEnglishuh1h hh _documenthsourceNlineNubhsection)}(hhh](htitle)}(h%Runtime locking correctness validatorh]h%Runtime locking correctness validator}(hhhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhhhD/var/lib/git/docbuild/linux/Documentation/locking/lockdep-design.rsthKubh paragraph)}(h)started by Ingo Molnar h](hstarted by Ingo Molnar <}(hhhhhNhNubh reference)}(hmingo@redhat.comh]hmingo@redhat.com}(hhhhhNhNubah}(h]h ]h"]h$]h&]refurimailto:mingo@redhat.comuh1hhhubh>}(hhhhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhKhhhhubh)}(h5additions by Arjan van de Ven h](hadditions by Arjan van de Ven <}(hhhhhNhNubh)}(harjan@linux.intel.comh]harjan@linux.intel.com}(hhhhhNhNubah}(h]h ]h"]h$]h&]refurimailto:arjan@linux.intel.comuh1hhhubh>}(hhhhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhKhhhhubh)}(hhh](h)}(h Lock-classh]h Lock-class}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhjhhhhhK ubh)}(hCThe basic object the validator operates upon is a 'class' of locks.h]hGThe basic object the validator operates upon is a ‘class’ of locks.}(hj$hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK hjhhubh)}(hX'A class of locks is a group of locks that are logically the same with respect to locking rules, even if the locks may have multiple (possibly tens of thousands of) instantiations. For example a lock in the inode struct is one class, while each inode has its own instantiation of that lock class.h]hX'A class of locks is a group of locks that are logically the same with respect to locking rules, even if the locks may have multiple (possibly tens of thousands of) instantiations. For example a lock in the inode struct is one class, while each inode has its own instantiation of that lock class.}(hj2hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK hjhhubh)}(hX_The validator tracks the 'usage state' of lock-classes, and it tracks the dependencies between different lock-classes. Lock usage indicates how a lock is used with regard to its IRQ contexts, while lock dependency can be understood as lock order, where L1 -> L2 suggests that a task is attempting to acquire L2 while holding L1. From lockdep's perspective, the two locks (L1 and L2) are not necessarily related; that dependency just means the order ever happened. The validator maintains a continuing effort to prove lock usages and dependencies are correct or the validator will shoot a splat if incorrect.h]hXeThe validator tracks the ‘usage state’ of lock-classes, and it tracks the dependencies between different lock-classes. Lock usage indicates how a lock is used with regard to its IRQ contexts, while lock dependency can be understood as lock order, where L1 -> L2 suggests that a task is attempting to acquire L2 while holding L1. From lockdep’s perspective, the two locks (L1 and L2) are not necessarily related; that dependency just means the order ever happened. The validator maintains a continuing effort to prove lock usages and dependencies are correct or the validator will shoot a splat if incorrect.}(hj@hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhjhhubh)}(hXA lock-class's behavior is constructed by its instances collectively: when the first instance of a lock-class is used after bootup the class gets registered, then all (subsequent) instances will be mapped to the class and hence their usages and dependencies will contribute to those of the class. A lock-class does not go away when a lock instance does, but it can be removed if the memory space of the lock class (static or dynamic) is reclaimed, this happens for example when a module is unloaded or a workqueue is destroyed.h]hXA lock-class’s behavior is constructed by its instances collectively: when the first instance of a lock-class is used after bootup the class gets registered, then all (subsequent) instances will be mapped to the class and hence their usages and dependencies will contribute to those of the class. A lock-class does not go away when a lock instance does, but it can be removed if the memory space of the lock class (static or dynamic) is reclaimed, this happens for example when a module is unloaded or a workqueue is destroyed.}(hjNhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhjhhubeh}(h] lock-classah ]h"] lock-classah$]h&]uh1hhhhhhhhK ubh)}(hhh](h)}(hStateh]hState}(hjghhhNhNubah}(h]h ]h"]h$]h&]uh1hhjdhhhhhK'ubh)}(hnThe validator tracks lock-class usage history and divides the usage into (4 usages * n STATEs + 1) categories:h]hnThe validator tracks lock-class usage history and divides the usage into (4 usages * n STATEs + 1) categories:}(hjuhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK)hjdhhubh)}(hwhere the 4 usages can be:h]hwhere the 4 usages can be:}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK,hjdhhubh bullet_list)}(hhh](h list_item)}(h'ever held in STATE context'h]h)}(hjh]h ‘ever held in STATE context’}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK.hjubah}(h]h ]h"]h$]h&]uh1jhjhhhhhNubj)}(h('ever held as readlock in STATE context'h]h)}(hjh]h,‘ever held as readlock in STATE context’}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK/hjubah}(h]h ]h"]h$]h&]uh1jhjhhhhhNubj)}(h'ever held with STATE enabled'h]h)}(hjh]h"‘ever held with STATE enabled’}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK0hjubah}(h]h ]h"]h$]h&]uh1jhjhhhhhNubj)}(h+'ever held as readlock with STATE enabled' h]h)}(h*'ever held as readlock with STATE enabled'h]h.‘ever held as readlock with STATE enabled’}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK1hjubah}(h]h ]h"]h$]h&]uh1jhjhhhhhNubeh}(h]h ]h"]h$]h&]bullet-uh1jhhhK.hjdhhubh)}(h[where the n STATEs are coded in kernel/locking/lockdep_states.h and as of now they include:h]h[where the n STATEs are coded in kernel/locking/lockdep_states.h and as of now they include:}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK3hjdhhubj)}(hhh](j)}(hhardirqh]h)}(hjh]hhardirq}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK6hjubah}(h]h ]h"]h$]h&]uh1jhj hhhhhNubj)}(hsoftirq h]h)}(hsoftirqh]hsoftirq}(hj)hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK7hj%ubah}(h]h ]h"]h$]h&]uh1jhj hhhhhNubeh}(h]h ]h"]h$]h&]jjuh1jhhhK6hjdhhubh)}(hwhere the last 1 category is:h]hwhere the last 1 category is:}(hjChhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK9hjdhhubj)}(hhh]j)}(hH'ever used' [ == !unused ] h]h)}(hG'ever used' [ == !unused ]h]hK‘ever used’ [ == !unused ]}(hjXhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK;hjTubah}(h]h ]h"]h$]h&]uh1jhjQhhhhhNubah}(h]h ]h"]h$]h&]jjuh1jhhhK;hjdhhubh)}(hWhen locking rules are violated, these usage bits are presented in the locking error messages, inside curlies, with a total of 2 * n STATEs bits. A contrived example::h]hWhen locking rules are violated, these usage bits are presented in the locking error messages, inside curlies, with a total of 2 * n STATEs bits. A contrived example:}(hjrhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK=hjdhhubh literal_block)}(hmodprobe/2287 is trying to acquire lock: (&sio_locks[i].lock){-.-.}, at: [] mutex_lock+0x21/0x24 but task is already holding lock: (&sio_locks[i].lock){-.-.}, at: [] mutex_lock+0x21/0x24h]hmodprobe/2287 is trying to acquire lock: (&sio_locks[i].lock){-.-.}, at: [] mutex_lock+0x21/0x24 but task is already holding lock: (&sio_locks[i].lock){-.-.}, at: [] mutex_lock+0x21/0x24}hjsbah}(h]h ]h"]h$]h&] xml:spacepreserveuh1jhhhKAhjdhhubh)}(hFor a given lock, the bit positions from left to right indicate the usage of the lock and readlock (if exists), for each of the n STATEs listed above respectively, and the character displayed at each bit position indicates:h]hFor a given lock, the bit positions from left to right indicate the usage of the lock and readlock (if exists), for each of the n STATEs listed above respectively, and the character displayed at each bit position indicates:}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKHhjdhhubh block_quote)}(hX=== =================================================== '.' acquired while irqs disabled and not in irq context '-' acquired in irq context '+' acquired with irqs enabled '?' acquired in irq context with irqs enabled. === =================================================== h]htable)}(hhh]htgroup)}(hhh](hcolspec)}(hhh]h}(h]h ]h"]h$]h&]colwidthKuh1jhjubj)}(hhh]h}(h]h ]h"]h$]h&]colwidthK3uh1jhjubhtbody)}(hhh](hrow)}(hhh](hentry)}(hhh]h)}(h'.'h]h‘.’}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKNhjubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(h3acquired while irqs disabled and not in irq contexth]h3acquired while irqs disabled and not in irq context}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKNhjubah}(h]h ]h"]h$]h&]uh1jhjubeh}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh](j)}(hhh]h)}(h'-'h]h‘-’}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKOhj ubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hacquired in irq contexth]hacquired in irq context}(hj#hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKOhj ubah}(h]h ]h"]h$]h&]uh1jhjubeh}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh](j)}(hhh]h)}(h'+'h]h‘+’}(hjChhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKPhj@ubah}(h]h ]h"]h$]h&]uh1jhj=ubj)}(hhh]h)}(hacquired with irqs enabledh]hacquired with irqs enabled}(hjZhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKPhjWubah}(h]h ]h"]h$]h&]uh1jhj=ubeh}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh](j)}(hhh]h)}(h'?'h]h‘?’}(hjzhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKQhjwubah}(h]h ]h"]h$]h&]uh1jhjtubj)}(hhh]h)}(h*acquired in irq context with irqs enabled.h]h*acquired in irq context with irqs enabled.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKQhjubah}(h]h ]h"]h$]h&]uh1jhjtubeh}(h]h ]h"]h$]h&]uh1jhjubeh}(h]h ]h"]h$]h&]uh1jhjubeh}(h]h ]h"]h$]h&]colsKuh1jhjubah}(h]h ]h"]h$]h&]uh1jhjubah}(h]h ]h"]h$]h&]uh1jhhhKMhjdhhubh)}(h*The bits are illustrated with an example::h]h)The bits are illustrated with an example:}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKThjdhhubj)}(hX_(&sio_locks[i].lock){-.-.}, at: [] mutex_lock+0x21/0x24 |||| ||| \-> softirq disabled and not in softirq context || \--> acquired in softirq context | \---> hardirq disabled and not in hardirq context \----> acquired in hardirq contexth]hX_(&sio_locks[i].lock){-.-.}, at: [] mutex_lock+0x21/0x24 |||| ||| \-> softirq disabled and not in softirq context || \--> acquired in softirq context | \---> hardirq disabled and not in hardirq context \----> acquired in hardirq context}hjsbah}(h]h ]h"]h$]h&]jjuh1jhhhKVhjdhhubh)}(hXFor a given STATE, whether the lock is ever acquired in that STATE context and whether that STATE is enabled yields four possible cases as shown in the table below. The bit character is able to indicate which exact case is for the lock as of the reporting time.h]hXFor a given STATE, whether the lock is ever acquired in that STATE context and whether that STATE is enabled yields four possible cases as shown in the table below. The bit character is able to indicate which exact case is for the lock as of the reporting time.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK^hjdhhubj)}(hXB+--------------+-------------+--------------+ | | irq enabled | irq disabled | +--------------+-------------+--------------+ | ever in irq | '?' | '-' | +--------------+-------------+--------------+ | never in irq | '+' | '.' | +--------------+-------------+--------------+ h]j)}(hhh]j)}(hhh](j)}(hhh]h}(h]h ]h"]h$]h&]colwidthKuh1jhjubj)}(hhh]h}(h]h ]h"]h$]h&]colwidthK uh1jhjubj)}(hhh]h}(h]h ]h"]h$]h&]colwidthKuh1jhjubj)}(hhh](j)}(hhh](j)}(hhh]h}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(h irq enabledh]h irq enabled}(hj(hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKdhj%ubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(h irq disabledh]h irq disabled}(hj?hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKdhj<ubah}(h]h ]h"]h$]h&]uh1jhjubeh}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh](j)}(hhh]h)}(h ever in irqh]h ever in irq}(hj_hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKfhj\ubah}(h]h ]h"]h$]h&]uh1jhjYubj)}(hhh]h)}(h'?'h]h‘?’}(hjvhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKfhjsubah}(h]h ]h"]h$]h&]uh1jhjYubj)}(hhh]h)}(h'-'h]h‘-’}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKfhjubah}(h]h ]h"]h$]h&]uh1jhjYubeh}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh](j)}(hhh]h)}(h never in irqh]h never in irq}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhhjubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(h'+'h]h‘+’}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhhjubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(h'.'h]h‘.’}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhhjubah}(h]h ]h"]h$]h&]uh1jhjubeh}(h]h ]h"]h$]h&]uh1jhjubeh}(h]h ]h"]h$]h&]uh1jhjubeh}(h]h ]h"]h$]h&]colsKuh1jhjubah}(h]h ]h"]h$]h&]uh1jhjubah}(h]h ]h"]h$]h&]uh1jhhhKchjdhhubh)}(hThe character '-' suggests irq is disabled because if otherwise the character '?' would have been shown instead. Similar deduction can be applied for '+' too.h]hThe character ‘-’ suggests irq is disabled because if otherwise the character ‘?’ would have been shown instead. Similar deduction can be applied for ‘+’ too.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKkhjdhhubh)}(hEUnused locks (e.g., mutexes) cannot be part of the cause of an error.h]hEUnused locks (e.g., mutexes) cannot be part of the cause of an error.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKohjdhhubeh}(h]stateah ]h"]stateah$]h&]uh1hhhhhhhhK'ubh)}(hhh](h)}(hSingle-lock state rules:h]hSingle-lock state rules:}(hj5hhhNhNubah}(h]h ]h"]h$]h&]uh1hhj2hhhhhKsubh)}(hA lock is irq-safe means it was ever used in an irq context, while a lock is irq-unsafe means it was ever acquired with irq enabled.h]hA lock is irq-safe means it was ever used in an irq context, while a lock is irq-unsafe means it was ever acquired with irq enabled.}(hjChhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKuhj2hhubh)}(hA softirq-unsafe lock-class is automatically hardirq-unsafe as well. The following states must be exclusive: only one of them is allowed to be set for any lock-class based on its usage::h]hA softirq-unsafe lock-class is automatically hardirq-unsafe as well. The following states must be exclusive: only one of them is allowed to be set for any lock-class based on its usage:}(hjQhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKxhj2hhubj)}(hE or or h]hE or or }hj_sbah}(h]h ]h"]h$]h&]jjuh1jhhhK|hj2hhubh)}(hXThis is because if a lock can be used in irq context (irq-safe) then it cannot be ever acquired with irq enabled (irq-unsafe). Otherwise, a deadlock may happen. For example, in the scenario that after this lock was acquired but before released, if the context is interrupted this lock will be attempted to acquire twice, which creates a deadlock, referred to as lock recursion deadlock.h]hXThis is because if a lock can be used in irq context (irq-safe) then it cannot be ever acquired with irq enabled (irq-unsafe). Otherwise, a deadlock may happen. For example, in the scenario that after this lock was acquired but before released, if the context is interrupted this lock will be attempted to acquire twice, which creates a deadlock, referred to as lock recursion deadlock.}(hjmhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhj2hhubh)}(hYThe validator detects and reports lock usage that violates these single-lock state rules.h]hYThe validator detects and reports lock usage that violates these single-lock state rules.}(hj{hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhj2hhubeh}(h]single-lock-state-rulesah ]h"]single-lock state rules:ah$]h&]uh1hhhhhhhhKsubh)}(hhh](h)}(hMulti-lock dependency rules:h]hMulti-lock dependency rules:}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhjhhhhhKubh)}(hdThe same lock-class must not be acquired twice, because this could lead to lock recursion deadlocks.h]hdThe same lock-class must not be acquired twice, because this could lead to lock recursion deadlocks.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhjhhubh)}(h:Furthermore, two locks can not be taken in inverse order::h]h9Furthermore, two locks can not be taken in inverse order:}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhjhhubj)}(h -> -> h]h -> -> }hjsbah}(h]h ]h"]h$]h&]jjuh1jhhhKhjhhubh)}(hXbecause this could lead to a deadlock - referred to as lock inversion deadlock - as attempts to acquire the two locks form a circle which could lead to the two contexts waiting for each other permanently. The validator will find such dependency circle in arbitrary complexity, i.e., there can be any other locking sequence between the acquire-lock operations; the validator will still find whether these locks can be acquired in a circular fashion.h]hXbecause this could lead to a deadlock - referred to as lock inversion deadlock - as attempts to acquire the two locks form a circle which could lead to the two contexts waiting for each other permanently. The validator will find such dependency circle in arbitrary complexity, i.e., there can be any other locking sequence between the acquire-lock operations; the validator will still find whether these locks can be acquired in a circular fashion.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhjhhubh)}(hgFurthermore, the following usage based lock dependencies are not allowed between any two lock-classes::h]hfFurthermore, the following usage based lock dependencies are not allowed between any two lock-classes:}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhjhhubj)}(hK -> -> h]hK -> -> }hjsbah}(h]h ]h"]h$]h&]jjuh1jhhhKhjhhubh)}(hX!The first rule comes from the fact that a hardirq-safe lock could be taken by a hardirq context, interrupting a hardirq-unsafe lock - and thus could result in a lock inversion deadlock. Likewise, a softirq-safe lock could be taken by an softirq context, interrupting a softirq-unsafe lock.h]hX!The first rule comes from the fact that a hardirq-safe lock could be taken by a hardirq context, interrupting a hardirq-unsafe lock - and thus could result in a lock inversion deadlock. Likewise, a softirq-safe lock could be taken by an softirq context, interrupting a softirq-unsafe lock.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhjhhubh)}(hThe above rules are enforced for any locking sequence that occurs in the kernel: when acquiring a new lock, the validator checks whether there is any rule violation between the new lock and any of the held locks.h]hThe above rules are enforced for any locking sequence that occurs in the kernel: when acquiring a new lock, the validator checks whether there is any rule violation between the new lock and any of the held locks.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhjhhubh)}(hfWhen a lock-class changes its state, the following aspects of the above dependency rules are enforced:h]hfWhen a lock-class changes its state, the following aspects of the above dependency rules are enforced:}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhjhhubj)}(hhh](j)}(hhif a new hardirq-safe lock is discovered, we check whether it took any hardirq-unsafe lock in the past. h]h)}(hgif a new hardirq-safe lock is discovered, we check whether it took any hardirq-unsafe lock in the past.h]hgif a new hardirq-safe lock is discovered, we check whether it took any hardirq-unsafe lock in the past.}(hj'hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhj#ubah}(h]h ]h"]h$]h&]uh1jhj hhhhhNubj)}(hhif a new softirq-safe lock is discovered, we check whether it took any softirq-unsafe lock in the past. h]h)}(hgif a new softirq-safe lock is discovered, we check whether it took any softirq-unsafe lock in the past.h]hgif a new softirq-safe lock is discovered, we check whether it took any softirq-unsafe lock in the past.}(hj?hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhj;ubah}(h]h ]h"]h$]h&]uh1jhj hhhhhNubj)}(hhif a new hardirq-unsafe lock is discovered, we check whether any hardirq-safe lock took it in the past. h]h)}(hgif a new hardirq-unsafe lock is discovered, we check whether any hardirq-safe lock took it in the past.h]hgif a new hardirq-unsafe lock is discovered, we check whether any hardirq-safe lock took it in the past.}(hjWhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhjSubah}(h]h ]h"]h$]h&]uh1jhj hhhhhNubj)}(hhif a new softirq-unsafe lock is discovered, we check whether any softirq-safe lock took it in the past. h]h)}(hgif a new softirq-unsafe lock is discovered, we check whether any softirq-safe lock took it in the past.h]hgif a new softirq-unsafe lock is discovered, we check whether any softirq-safe lock took it in the past.}(hjohhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhjkubah}(h]h ]h"]h$]h&]uh1jhj hhhhhNubeh}(h]h ]h"]h$]h&]jjuh1jhhhKhjhhubh)}(h(Again, we do these checks too on the basis that an interrupt context could interrupt _any_ of the irq-unsafe or hardirq-unsafe locks, which could lead to a lock inversion deadlock - even if that lock scenario did not trigger in practice yet.)h]h(Again, we do these checks too on the basis that an interrupt context could interrupt _any_ of the irq-unsafe or hardirq-unsafe locks, which could lead to a lock inversion deadlock - even if that lock scenario did not trigger in practice yet.)}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhjhhubeh}(h]multi-lock-dependency-rulesah ]h"]multi-lock dependency rules:ah$]h&]uh1hhhhhhhhKubh)}(hhh](h)}(h=Exception: Nested data dependencies leading to nested lockingh]h=Exception: Nested data dependencies leading to nested locking}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhjhhhhhKubh)}(hXThere are a few cases where the Linux kernel acquires more than one instance of the same lock-class. Such cases typically happen when there is some sort of hierarchy within objects of the same type. In these cases there is an inherent "natural" ordering between the two objects (defined by the properties of the hierarchy), and the kernel grabs the locks in this fixed order on each of the objects.h]hXThere are a few cases where the Linux kernel acquires more than one instance of the same lock-class. Such cases typically happen when there is some sort of hierarchy within objects of the same type. In these cases there is an inherent “natural” ordering between the two objects (defined by the properties of the hierarchy), and the kernel grabs the locks in this fixed order on each of the objects.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhjhhubh)}(hXAn example of such an object hierarchy that results in "nested locking" is that of a "whole disk" block-dev object and a "partition" block-dev object; the partition is "part of" the whole device and as long as one always takes the whole disk lock as a higher lock than the partition lock, the lock ordering is fully correct. The validator does not automatically detect this natural ordering, as the locking rule behind the ordering is not static.h]hXAn example of such an object hierarchy that results in “nested locking” is that of a “whole disk” block-dev object and a “partition” block-dev object; the partition is “part of” the whole device and as long as one always takes the whole disk lock as a higher lock than the partition lock, the lock ordering is fully correct. The validator does not automatically detect this natural ordering, as the locking rule behind the ordering is not static.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhjhhubh)}(hIn order to teach the validator about this correct usage model, new versions of the various locking primitives were added that allow you to specify a "nesting level". An example call, for the block device mutex, looks like this::h]hIn order to teach the validator about this correct usage model, new versions of the various locking primitives were added that allow you to specify a “nesting level”. An example call, for the block device mutex, looks like this:}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhjhhubj)}(henum bdev_bd_mutex_lock_class { BD_MUTEX_NORMAL, BD_MUTEX_WHOLE, BD_MUTEX_PARTITION }; mutex_lock_nested(&bdev->bd_contains->bd_mutex, BD_MUTEX_PARTITION);h]henum bdev_bd_mutex_lock_class { BD_MUTEX_NORMAL, BD_MUTEX_WHOLE, BD_MUTEX_PARTITION }; mutex_lock_nested(&bdev->bd_contains->bd_mutex, BD_MUTEX_PARTITION);}hjsbah}(h]h ]h"]h$]h&]jjuh1jhhhKhjhhubh)}(hRIn this case the locking is done on a bdev object that is known to be a partition.h]hRIn this case the locking is done on a bdev object that is known to be a partition.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhjhhubh)}(h{The validator treats a lock that is taken in such a nested fashion as a separate (sub)class for the purposes of validation.h]h{The validator treats a lock that is taken in such a nested fashion as a separate (sub)class for the purposes of validation.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhjhhubh)}(hNote: When changing code to use the _nested() primitives, be careful and check really thoroughly that the hierarchy is correctly mapped; otherwise you can get false positives or false negatives.h]hNote: When changing code to use the _nested() primitives, be careful and check really thoroughly that the hierarchy is correctly mapped; otherwise you can get false positives or false negatives.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhjhhubeh}(h]lock); [...] }h]hkvoid update_rq_clock(struct rq *rq) { s64 delta; lockdep_assert_held(&rq->lock); [...] }}hjGsbah}(h]h ]h"]h$]h&]jjuh1jhhhKhjhhubh)}(hAwhere holding rq->lock is required to safely update a rq's clock.h]hCwhere holding rq->lock is required to safely update a rq’s clock.}(hjUhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhjhhubh)}(hX[The other family of macros is lockdep_*pin_lock(), which is admittedly only used for rq->lock ATM. Despite their limited adoption these annotations generate a WARN() if the lock of interest is "accidentally" unlocked. This turns out to be especially helpful to debug code with callbacks, where an upper layer assumes a lock remains taken, but a lower layer thinks it can maybe drop and reacquire the lock ("unwittingly" introducing races). lockdep_pin_lock() returns a 'struct pin_cookie' that is then used by lockdep_unpin_lock() to check that nobody tampered with the lock, e.g. kernel/sched/sched.h::h]hXfThe other family of macros is lockdep_*pin_lock(), which is admittedly only used for rq->lock ATM. Despite their limited adoption these annotations generate a WARN() if the lock of interest is “accidentally” unlocked. This turns out to be especially helpful to debug code with callbacks, where an upper layer assumes a lock remains taken, but a lower layer thinks it can maybe drop and reacquire the lock (“unwittingly” introducing races). lockdep_pin_lock() returns a ‘struct pin_cookie’ that is then used by lockdep_unpin_lock() to check that nobody tampered with the lock, e.g. kernel/sched/sched.h:}(hjchhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhjhhubj)}(hX static inline void rq_pin_lock(struct rq *rq, struct rq_flags *rf) { rf->cookie = lockdep_pin_lock(&rq->lock); [...] } static inline void rq_unpin_lock(struct rq *rq, struct rq_flags *rf) { [...] lockdep_unpin_lock(&rq->lock, rf->cookie); }h]hX static inline void rq_pin_lock(struct rq *rq, struct rq_flags *rf) { rf->cookie = lockdep_pin_lock(&rq->lock); [...] } static inline void rq_unpin_lock(struct rq *rq, struct rq_flags *rf) { [...] lockdep_unpin_lock(&rq->lock, rf->cookie); }}hjqsbah}(h]h ]h"]h$]h&]jjuh1jhhhMhjhhubh)}(hXWhile comments about locking requirements might provide useful information, the runtime checks performed by annotations are invaluable when debugging locking problems and they carry the same level of details when inspecting code. Always prefer annotations when in doubt!h]hXWhile comments about locking requirements might provide useful information, the runtime checks performed by annotations are invaluable when debugging locking problems and they carry the same level of details when inspecting code. Always prefer annotations when in doubt!}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjhhubeh}(h] annotationsah ]h"] annotationsah$]h&]uh1hhhhhhhhKubh)}(hhh](h)}(hProof of 100% correctness:h]hProof of 100% correctness:}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhjhhhhhMubh)}(hX{The validator achieves perfect, mathematical 'closure' (proof of locking correctness) in the sense that for every simple, standalone single-task locking sequence that occurred at least once during the lifetime of the kernel, the validator proves it with a 100% certainty that no combination and timing of these locking sequences can cause any class of lock related deadlock. [1]_h](hX{The validator achieves perfect, mathematical ‘closure’ (proof of locking correctness) in the sense that for every simple, standalone single-task locking sequence that occurred at least once during the lifetime of the kernel, the validator proves it with a 100% certainty that no combination and timing of these locking sequences can cause any class of lock related deadlock. }(hjhhhNhNubhfootnote_reference)}(h[1]_h]h1}(hjhhhNhNubah}(h]id1ah ]h"]h$]h&]refidid2docnamelocking/lockdep-designuh1jhjresolvedKubeh}(h]h ]h"]h$]h&]uh1hhhhMhjhhubh)}(hXI.e. complex multi-CPU and multi-task locking scenarios do not have to occur in practice to prove a deadlock: only the simple 'component' locking chains have to occur at least once (anytime, in any task/context) for the validator to be able to prove correctness. (For example, complex deadlocks that would normally need more than 3 CPUs and a very unlikely constellation of tasks, irq-contexts and timings to occur, can be detected on a plain, lightly loaded single-CPU system as well!)h]hXI.e. complex multi-CPU and multi-task locking scenarios do not have to occur in practice to prove a deadlock: only the simple ‘component’ locking chains have to occur at least once (anytime, in any task/context) for the validator to be able to prove correctness. (For example, complex deadlocks that would normally need more than 3 CPUs and a very unlikely constellation of tasks, irq-contexts and timings to occur, can be detected on a plain, lightly loaded single-CPU system as well!)}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhM#hjhhubh)}(hXThis radically decreases the complexity of locking related QA of the kernel: what has to be done during QA is to trigger as many "simple" single-task locking dependencies in the kernel as possible, at least once, to prove locking correctness - instead of having to trigger every possible combination of locking interaction between CPUs, combined with every possible hardirq and softirq nesting scenario (which is impossible to do in practice).h]hXThis radically decreases the complexity of locking related QA of the kernel: what has to be done during QA is to trigger as many “simple” single-task locking dependencies in the kernel as possible, at least once, to prove locking correctness - instead of having to trigger every possible combination of locking interaction between CPUs, combined with every possible hardirq and softirq nesting scenario (which is impossible to do in practice).}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhM,hjhhubhfootnote)}(hXassuming that the validator itself is 100% correct, and no other part of the system corrupts the state of the validator in any way. We also assume that all NMI/SMM paths [which could interrupt even hardirq-disabled codepaths] are correct and do not interfere with the validator. We also assume that the 64-bit 'chain hash' value is unique for every lock-chain in the system. Also, lock recursion must not be higher than 20. h](hlabel)}(h1h]h1}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1jhjubh)}(hXassuming that the validator itself is 100% correct, and no other part of the system corrupts the state of the validator in any way. We also assume that all NMI/SMM paths [which could interrupt even hardirq-disabled codepaths] are correct and do not interfere with the validator. We also assume that the 64-bit 'chain hash' value is unique for every lock-chain in the system. Also, lock recursion must not be higher than 20.h]hXassuming that the validator itself is 100% correct, and no other part of the system corrupts the state of the validator in any way. We also assume that all NMI/SMM paths [which could interrupt even hardirq-disabled codepaths] are correct and do not interfere with the validator. We also assume that the 64-bit ‘chain hash’ value is unique for every lock-chain in the system. Also, lock recursion must not be higher than 20.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhM6hjubeh}(h]jah ]h"]1ah$]h&]jajjuh1jhhhM4hjhhjKubeh}(h]proof-of-100-correctnessah ]h"]proof of 100% correctness:ah$]h&]uh1hhhhhhhhMubh)}(hhh](h)}(h Performance:h]h Performance:}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhjhhhhhM?ubh)}(hXKThe above rules require **massive** amounts of runtime checking. If we did that for every lock taken and for every irqs-enable event, it would render the system practically unusably slow. The complexity of checking is O(N^2), so even with just a few hundred lock-classes we'd have to do tens of thousands of checks for every event.h](hThe above rules require }(hj*hhhNhNubhstrong)}(h **massive**h]hmassive}(hj4hhhNhNubah}(h]h ]h"]h$]h&]uh1j2hj*ubhX* amounts of runtime checking. If we did that for every lock taken and for every irqs-enable event, it would render the system practically unusably slow. The complexity of checking is O(N^2), so even with just a few hundred lock-classes we’d have to do tens of thousands of checks for every event.}(hj*hhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhMAhjhhubh)}(hXThis problem is solved by checking any given 'locking scenario' (unique sequence of locks taken after each other) only once. A simple stack of held locks is maintained, and a lightweight 64-bit hash value is calculated, which hash is unique for every lock chain. The hash value, when the chain is validated for the first time, is then put into a hash table, which hash-table can be checked in a lockfree manner. If the locking chain occurs again later on, the hash table tells us that we don't have to validate the chain again.h]hXThis problem is solved by checking any given ‘locking scenario’ (unique sequence of locks taken after each other) only once. A simple stack of held locks is maintained, and a lightweight 64-bit hash value is calculated, which hash is unique for every lock chain. The hash value, when the chain is validated for the first time, is then put into a hash table, which hash-table can be checked in a lockfree manner. If the locking chain occurs again later on, the hash table tells us that we don’t have to validate the chain again.}(hjLhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMGhjhhubeh}(h] performanceah ]h"] performance:ah$]h&]uh1hhhhhhhhM?ubh)}(hhh](h)}(hTroubleshooting:h]hTroubleshooting:}(hjehhhNhNubah}(h]h ]h"]h$]h&]uh1hhjbhhhhhMQubh)}(hThe validator tracks a maximum of MAX_LOCKDEP_KEYS number of lock classes. Exceeding this number will trigger the following lockdep warning::h]hThe validator tracks a maximum of MAX_LOCKDEP_KEYS number of lock classes. Exceeding this number will trigger the following lockdep warning:}(hjshhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMShjbhhubj)}(h-(DEBUG_LOCKS_WARN_ON(id >= MAX_LOCKDEP_KEYS))h]h-(DEBUG_LOCKS_WARN_ON(id >= MAX_LOCKDEP_KEYS))}hjsbah}(h]h ]h"]h$]h&]jjuh1jhhhMVhjbhhubh)}(hXBy default, MAX_LOCKDEP_KEYS is currently set to 8191, and typical desktop systems have less than 1,000 lock classes, so this warning normally results from lock-class leakage or failure to properly initialize locks. These two problems are illustrated below:h]hXBy default, MAX_LOCKDEP_KEYS is currently set to 8191, and typical desktop systems have less than 1,000 lock classes, so this warning normally results from lock-class leakage or failure to properly initialize locks. These two problems are illustrated below:}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMXhjbhhubhenumerated_list)}(hhh](j)}(hXRepeated module loading and unloading while running the validator will result in lock-class leakage. The issue here is that each load of the module will create a new set of lock classes for that module's locks, but module unloading does not remove old classes (see below discussion of reuse of lock classes for why). Therefore, if that module is loaded and unloaded repeatedly, the number of lock classes will eventually reach the maximum. h]h)}(hXRepeated module loading and unloading while running the validator will result in lock-class leakage. The issue here is that each load of the module will create a new set of lock classes for that module's locks, but module unloading does not remove old classes (see below discussion of reuse of lock classes for why). Therefore, if that module is loaded and unloaded repeatedly, the number of lock classes will eventually reach the maximum.h]hXRepeated module loading and unloading while running the validator will result in lock-class leakage. The issue here is that each load of the module will create a new set of lock classes for that module’s locks, but module unloading does not remove old classes (see below discussion of reuse of lock classes for why). Therefore, if that module is loaded and unloaded repeatedly, the number of lock classes will eventually reach the maximum.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhM]hjubah}(h]h ]h"]h$]h&]uh1jhjhhhhhNubj)}(hXUsing structures such as arrays that have large numbers of locks that are not explicitly initialized. For example, a hash table with 8192 buckets where each bucket has its own spinlock_t will consume 8192 lock classes -unless- each spinlock is explicitly initialized at runtime, for example, using the run-time spin_lock_init() as opposed to compile-time initializers such as __SPIN_LOCK_UNLOCKED(). Failure to properly initialize the per-bucket spinlocks would guarantee lock-class overflow. In contrast, a loop that called spin_lock_init() on each lock would place all 8192 locks into a single lock class. The moral of this story is that you should always explicitly initialize your locks. h](h)}(hXaUsing structures such as arrays that have large numbers of locks that are not explicitly initialized. For example, a hash table with 8192 buckets where each bucket has its own spinlock_t will consume 8192 lock classes -unless- each spinlock is explicitly initialized at runtime, for example, using the run-time spin_lock_init() as opposed to compile-time initializers such as __SPIN_LOCK_UNLOCKED(). Failure to properly initialize the per-bucket spinlocks would guarantee lock-class overflow. In contrast, a loop that called spin_lock_init() on each lock would place all 8192 locks into a single lock class.h]hXaUsing structures such as arrays that have large numbers of locks that are not explicitly initialized. For example, a hash table with 8192 buckets where each bucket has its own spinlock_t will consume 8192 lock classes -unless- each spinlock is explicitly initialized at runtime, for example, using the run-time spin_lock_init() as opposed to compile-time initializers such as __SPIN_LOCK_UNLOCKED(). Failure to properly initialize the per-bucket spinlocks would guarantee lock-class overflow. In contrast, a loop that called spin_lock_init() on each lock would place all 8192 locks into a single lock class.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMehjubh)}(hSThe moral of this story is that you should always explicitly initialize your locks.h]hSThe moral of this story is that you should always explicitly initialize your locks.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMphjubeh}(h]h ]h"]h$]h&]uh1jhjhhhhhNubeh}(h]h ]h"]h$]h&]enumtypearabicprefixhsuffix.uh1jhjbhhhhhM]ubh)}(hXuOne might argue that the validator should be modified to allow lock classes to be reused. However, if you are tempted to make this argument, first review the code and think through the changes that would be required, keeping in mind that the lock classes to be removed are likely to be linked into the lock-dependency graph. This turns out to be harder to do than to say.h]hXuOne might argue that the validator should be modified to allow lock classes to be reused. However, if you are tempted to make this argument, first review the code and think through the changes that would be required, keeping in mind that the lock classes to be removed are likely to be linked into the lock-dependency graph. This turns out to be harder to do than to say.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMshjbhhubh)}(hOf course, if you do run out of lock classes, the next thing to do is to find the offending lock classes. First, the following command gives you the number of lock classes currently in use along with the maximum::h]hOf course, if you do run out of lock classes, the next thing to do is to find the offending lock classes. First, the following command gives you the number of lock classes currently in use along with the maximum:}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMzhjbhhubj)}(h'grep "lock-classes" /proc/lockdep_statsh]h'grep "lock-classes" /proc/lockdep_stats}hj sbah}(h]h ]h"]h$]h&]jjuh1jhhhM~hjbhhubh)}(h?This command produces the following output on a modest system::h]h>This command produces the following output on a modest system:}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjbhhubj)}(h6lock-classes: 748 [max: 8191]h]h6lock-classes: 748 [max: 8191]}hj# sbah}(h]h ]h"]h$]h&]jjuh1jhhhMhjbhhubh)}(hIf the number allocated (748 above) increases continually over time, then there is likely a leak. The following command can be used to identify the leaking lock classes::h]hIf the number allocated (748 above) increases continually over time, then there is likely a leak. The following command can be used to identify the leaking lock classes:}(hj1 hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjbhhubj)}(hgrep "BD" /proc/lockdeph]hgrep "BD" /proc/lockdep}hj? sbah}(h]h ]h"]h$]h&]jjuh1jhhhMhjbhhubh)}(hRun the command and save the output, then compare against the output from a later run of this command to identify the leakers. This same output can also help you find situations where runtime lock initialization has been omitted.h]hRun the command and save the output, then compare against the output from a later run of this command to identify the leakers. This same output can also help you find situations where runtime lock initialization has been omitted.}(hjM hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjbhhubeh}(h]troubleshootingah ]h"]troubleshooting:ah$]h&]uh1hhhhhhhhMQubh)}(hhh](h)}(hRecursive read locks:h]hRecursive read locks:}(hjf hhhNhNubah}(h]h ]h"]h$]h&]uh1hhjc hhhhhMubh)}(hlThe whole of the rest document tries to prove a certain type of cycle is equivalent to deadlock possibility.h]hlThe whole of the rest document tries to prove a certain type of cycle is equivalent to deadlock possibility.}(hjt hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjc hhubh)}(hX<There are three types of lockers: writers (i.e. exclusive lockers, like spin_lock() or write_lock()), non-recursive readers (i.e. shared lockers, like down_read()) and recursive readers (recursive shared lockers, like rcu_read_lock()). And we use the following notations of those lockers in the rest of the document:h]hX<There are three types of lockers: writers (i.e. exclusive lockers, like spin_lock() or write_lock()), non-recursive readers (i.e. shared lockers, like down_read()) and recursive readers (recursive shared lockers, like rcu_read_lock()). And we use the following notations of those lockers in the rest of the document:}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjc hhubj)}(hX)W or E: stands for writers (exclusive lockers). r: stands for non-recursive readers. R: stands for recursive readers. S: stands for all readers (non-recursive + recursive), as both are shared lockers. N: stands for writers and non-recursive readers, as both are not recursive. h]h)}(hX(W or E: stands for writers (exclusive lockers). r: stands for non-recursive readers. R: stands for recursive readers. S: stands for all readers (non-recursive + recursive), as both are shared lockers. N: stands for writers and non-recursive readers, as both are not recursive.h]hX(W or E: stands for writers (exclusive lockers). r: stands for non-recursive readers. R: stands for recursive readers. S: stands for all readers (non-recursive + recursive), as both are shared lockers. N: stands for writers and non-recursive readers, as both are not recursive.}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj ubah}(h]h ]h"]h$]h&]uh1jhhhMhjc hhubh)}(h+Obviously, N is "r or W" and S is "r or R".h]h3Obviously, N is “r or W” and S is “r or R”.}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjc hhubh)}(hRecursive readers, as their name indicates, are the lockers allowed to acquire even inside the critical section of another reader of the same lock instance, in other words, allowing nested read-side critical sections of one lock instance.h]hRecursive readers, as their name indicates, are the lockers allowed to acquire even inside the critical section of another reader of the same lock instance, in other words, allowing nested read-side critical sections of one lock instance.}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjc hhubh)}(hWhile non-recursive readers will cause a self deadlock if trying to acquire inside the critical section of another reader of the same lock instance.h]hWhile non-recursive readers will cause a self deadlock if trying to acquire inside the critical section of another reader of the same lock instance.}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjc hhubh)}(hThe difference between recursive readers and non-recursive readers is because: recursive readers get blocked only by a write lock *holder*, while non-recursive readers could get blocked by a write lock *waiter*. Considering the follow example::h](hThe difference between recursive readers and non-recursive readers is because: recursive readers get blocked only by a write lock }(hj hhhNhNubhemphasis)}(h*holder*h]hholder}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1j hj ubh@, while non-recursive readers could get blocked by a write lock }(hj hhhNhNubj )}(h*waiter*h]hwaiter}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1j hj ubh!. Considering the follow example:}(hj hhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhMhjc hhubj)}(heTASK A: TASK B: read_lock(X); write_lock(X); read_lock_2(X);h]heTASK A: TASK B: read_lock(X); write_lock(X); read_lock_2(X);}hj sbah}(h]h ]h"]h$]h&]jjuh1jhhhMhjc hhubh)}(hXTask A gets the reader (no matter whether recursive or non-recursive) on X via read_lock() first. And when task B tries to acquire writer on X, it will block and become a waiter for writer on X. Now if read_lock_2() is recursive readers, task A will make progress, because writer waiters don't block recursive readers, and there is no deadlock. However, if read_lock_2() is non-recursive readers, it will get blocked by writer waiter B, and cause a self deadlock.h]hXTask A gets the reader (no matter whether recursive or non-recursive) on X via read_lock() first. And when task B tries to acquire writer on X, it will block and become a waiter for writer on X. Now if read_lock_2() is recursive readers, task A will make progress, because writer waiters don’t block recursive readers, and there is no deadlock. However, if read_lock_2() is non-recursive readers, it will get blocked by writer waiter B, and cause a self deadlock.}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjc hhubeh}(h]recursive-read-locksah ]h"]recursive read locks:ah$]h&]uh1hhhhhhhhMubh)}(hhh](h)}(h>Block conditions on readers/writers of the same lock instance:h]h>Block conditions on readers/writers of the same lock instance:}(hj- hhhNhNubah}(h]h ]h"]h$]h&]uh1hhj* hhhhhMubh)}(h'There are simply four block conditions:h]h'There are simply four block conditions:}(hj; hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj* hhubj)}(hhh](j)}(hWriters block other writers.h]h)}(hjN h]hWriters block other writers.}(hjP hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjL ubah}(h]h ]h"]h$]h&]uh1jhjI hhhhhNubj)}(hReaders block writers.h]h)}(hje h]hReaders block writers.}(hjg hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjc ubah}(h]h ]h"]h$]h&]uh1jhjI hhhhhNubj)}(h?Writers block both recursive readers and non-recursive readers.h]h)}(hj| h]h?Writers block both recursive readers and non-recursive readers.}(hj~ hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjz ubah}(h]h ]h"]h$]h&]uh1jhjI hhhhhNubj)}(hAnd readers (recursive or not) don't block other recursive readers but may block non-recursive readers (because of the potential co-existing writer waiters) h]h)}(hAnd readers (recursive or not) don't block other recursive readers but may block non-recursive readers (because of the potential co-existing writer waiters)h]hAnd readers (recursive or not) don’t block other recursive readers but may block non-recursive readers (because of the potential co-existing writer waiters)}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj ubah}(h]h ]h"]h$]h&]uh1jhjI hhhhhNubeh}(h]h ]h"]h$]h&]jjjhjjuh1jhj* hhhhhMubh)}(hQBlock condition matrix, Y means the row blocks the column, and N means otherwise.h]hQBlock condition matrix, Y means the row blocks the column, and N means otherwise.}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj* hhubj)}(h+---+---+---+---+ | | W | r | R | +---+---+---+---+ | W | Y | Y | Y | +---+---+---+---+ | r | Y | Y | N | +---+---+---+---+ | R | Y | Y | N | +---+---+---+---+ (W: writers, r: non-recursive readers, R: recursive readers) h](j)}(hhh]j)}(hhh](j)}(hhh]h}(h]h ]h"]h$]h&]colwidthKuh1jhj ubj)}(hhh]h}(h]h ]h"]h$]h&]colwidthKuh1jhj ubj)}(hhh]h}(h]h ]h"]h$]h&]colwidthKuh1jhj ubj)}(hhh]h}(h]h ]h"]h$]h&]colwidthKuh1jhj ubj)}(hhh](j)}(hhh](j)}(hhh]h}(h]h ]h"]h$]h&]uh1jhj ubj)}(hhh]h)}(hWh]hW}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj ubah}(h]h ]h"]h$]h&]uh1jhj ubj)}(hhh]h)}(hrh]hr}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj ubah}(h]h ]h"]h$]h&]uh1jhj ubj)}(hhh]h)}(hRh]hR}(hj/ hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj, ubah}(h]h ]h"]h$]h&]uh1jhj ubeh}(h]h ]h"]h$]h&]uh1jhj ubj)}(hhh](j)}(hhh]h)}(hj h]hW}(hjO hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjL ubah}(h]h ]h"]h$]h&]uh1jhjI ubj)}(hhh]h)}(hYh]hY}(hje hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjb ubah}(h]h ]h"]h$]h&]uh1jhjI ubj)}(hhh]h)}(hjg h]hY}(hj| hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjy ubah}(h]h ]h"]h$]h&]uh1jhjI ubj)}(hhh]h)}(hjg h]hY}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj ubah}(h]h ]h"]h$]h&]uh1jhjI ubeh}(h]h ]h"]h$]h&]uh1jhj ubj)}(hhh](j)}(hhh]h)}(hj h]hr}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj ubah}(h]h ]h"]h$]h&]uh1jhj ubj)}(hhh]h)}(hjg h]hY}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj ubah}(h]h ]h"]h$]h&]uh1jhj ubj)}(hhh]h)}(hjg h]hY}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj ubah}(h]h ]h"]h$]h&]uh1jhj ubj)}(hhh]h)}(hNh]hN}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj ubah}(h]h ]h"]h$]h&]uh1jhj ubeh}(h]h ]h"]h$]h&]uh1jhj ubj)}(hhh](j)}(hhh]h)}(hj1 h]hR}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj ubah}(h]h ]h"]h$]h&]uh1jhj ubj)}(hhh]h)}(hjg h]hY}(hj) hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj& ubah}(h]h ]h"]h$]h&]uh1jhj ubj)}(hhh]h)}(hjg h]hY}(hj? hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj< ubah}(h]h ]h"]h$]h&]uh1jhj ubj)}(hhh]h)}(hj h]hN}(hjU hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjR ubah}(h]h ]h"]h$]h&]uh1jhj ubeh}(h]h ]h"]h$]h&]uh1jhj ubeh}(h]h ]h"]h$]h&]uh1jhj ubeh}(h]h ]h"]h$]h&]colsKuh1jhj ubah}(h]h ]h"]h$]h&]uh1jhj ubh)}(h<(W: writers, r: non-recursive readers, R: recursive readers)h]h<(W: writers, r: non-recursive readers, R: recursive readers)}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj ubeh}(h]h ]h"]h$]h&]uh1jhhhMhj* hhubh)}(hacquired recursively. Unlike non-recursive read locks, recursive read locks only get blocked by current write lock *holders* other than write lock *waiters*, for example::h](hsacquired recursively. Unlike non-recursive read locks, recursive read locks only get blocked by current write lock }(hj hhhNhNubj )}(h *holders*h]hholders}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1j hj ubh other than write lock }(hj hhhNhNubj )}(h *waiters*h]hwaiters}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1j hj ubh, for example:}(hj hhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhMhj* hhubj)}(heTASK A: TASK B: read_lock(X); write_lock(X); read_lock(X);h]heTASK A: TASK B: read_lock(X); write_lock(X); read_lock(X);}hj sbah}(h]h ]h"]h$]h&]jjuh1jhhhMhj* hhubh)}(hXwis not a deadlock for recursive read locks, as while the task B is waiting for the lock X, the second read_lock() doesn't need to wait because it's a recursive read lock. However if the read_lock() is non-recursive read lock, then the above case is a deadlock, because even if the write_lock() in TASK B cannot get the lock, but it can block the second read_lock() in TASK A.h]hX{is not a deadlock for recursive read locks, as while the task B is waiting for the lock X, the second read_lock() doesn’t need to wait because it’s a recursive read lock. However if the read_lock() is non-recursive read lock, then the above case is a deadlock, because even if the write_lock() in TASK B cannot get the lock, but it can block the second read_lock() in TASK A.qa}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj* hhubh)}(hXNote that a lock can be a write lock (exclusive lock), a non-recursive read lock (non-recursive shared lock) or a recursive read lock (recursive shared lock), depending on the lock operations used to acquire it (more specifically, the value of the 'read' parameter for lock_acquire()). In other words, a single lock instance has three types of acquisition depending on the acquisition functions: exclusive, non-recursive read, and recursive read.h]hXNote that a lock can be a write lock (exclusive lock), a non-recursive read lock (non-recursive shared lock) or a recursive read lock (recursive shared lock), depending on the lock operations used to acquire it (more specifically, the value of the ‘read’ parameter for lock_acquire()). In other words, a single lock instance has three types of acquisition depending on the acquisition functions: exclusive, non-recursive read, and recursive read.}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj* hhubh)}(hTo be concise, we call that write locks and non-recursive read locks as "non-recursive" locks and recursive read locks as "recursive" locks.h]hTo be concise, we call that write locks and non-recursive read locks as “non-recursive” locks and recursive read locks as “recursive” locks.}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj* hhubh)}(hRecursive locks don't block each other, while non-recursive locks do (this is even true for two non-recursive read locks). A non-recursive lock can block the corresponding recursive lock, and vice versa.h]hRecursive locks don’t block each other, while non-recursive locks do (this is even true for two non-recursive read locks). A non-recursive lock can block the corresponding recursive lock, and vice versa.}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj* hhubh)}(hblock conditions on readers/writers of the same lock instance:ah$]h&]uh1hhhhhhhhMubh)}(hhh](h)}(h-Dependency types and strong dependency paths:h]h-Dependency types and strong dependency paths:}(hjB hhhNhNubah}(h]h ]h"]h$]h&]uh1hhj? hhhhhMubh)}(hLock dependencies record the orders of the acquisitions of a pair of locks, and because there are 3 types for lockers, there are, in theory, 9 types of lock dependencies, but we can show that 4 types of lock dependencies are enough for deadlock detection.h]hLock dependencies record the orders of the acquisitions of a pair of locks, and because there are 3 types for lockers, there are, in theory, 9 types of lock dependencies, but we can show that 4 types of lock dependencies are enough for deadlock detection.}(hjP hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj? hhubh)}(hFor each lock dependency::h]hFor each lock dependency:}(hj^ hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj? hhubj)}(hL1 -> L2h]hL1 -> L2}hjl sbah}(h]h ]h"]h$]h&]jjuh1jhhhM hj? hhubh)}(hX , which means lockdep has seen L1 held before L2 held in the same context at runtime. And in deadlock detection, we care whether we could get blocked on L2 with L1 held, IOW, whether there is a locker L3 that L1 blocks L3 and L2 gets blocked by L3. So we only care about 1) what L1 blocks and 2) what blocks L2. As a result, we can combine recursive readers and non-recursive readers for L1 (as they block the same types) and we can combine writers and non-recursive readers for L2 (as they get blocked by the same types).h]hX , which means lockdep has seen L1 held before L2 held in the same context at runtime. And in deadlock detection, we care whether we could get blocked on L2 with L1 held, IOW, whether there is a locker L3 that L1 blocks L3 and L2 gets blocked by L3. So we only care about 1) what L1 blocks and 2) what blocks L2. As a result, we can combine recursive readers and non-recursive readers for L1 (as they block the same types) and we can combine writers and non-recursive readers for L2 (as they get blocked by the same types).}(hjz hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhM hj? hhubh)}(hjWith the above combination for simplification, there are 4 types of dependency edges in the lockdep graph:h]hjWith the above combination for simplification, there are 4 types of dependency edges in the lockdep graph:}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj? hhubj)}(hhh](j)}(h-(ER)->: exclusive writer to recursive reader dependency, "X -(ER)-> Y" means X -> Y and X is a writer and Y is a recursive reader. h]hdefinition_list)}(hhh]hdefinition_list_item)}(h-(ER)->: exclusive writer to recursive reader dependency, "X -(ER)-> Y" means X -> Y and X is a writer and Y is a recursive reader. h](hterm)}(h-(ER)->:h]h-(ER)->:}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1j hhhMhj ubh definition)}(hhh]h)}(hzexclusive writer to recursive reader dependency, "X -(ER)-> Y" means X -> Y and X is a writer and Y is a recursive reader.h]h~exclusive writer to recursive reader dependency, “X -(ER)-> Y” means X -> Y and X is a writer and Y is a recursive reader.}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj ubah}(h]h ]h"]h$]h&]uh1j hj ubeh}(h]h ]h"]h$]h&]uh1j hhhMhj ubah}(h]h ]h"]h$]h&]uh1j hj ubah}(h]h ]h"]h$]h&]uh1jhj hhhNhNubj)}(h-(EN)->: exclusive writer to non-recursive locker dependency, "X -(EN)-> Y" means X -> Y and X is a writer and Y is either a writer or non-recursive reader. h]j )}(hhh]j )}(h-(EN)->: exclusive writer to non-recursive locker dependency, "X -(EN)-> Y" means X -> Y and X is a writer and Y is either a writer or non-recursive reader. h](j )}(h-(EN)->:h]h-(EN)->:}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1j hhhMhj ubj )}(hhh]h)}(hexclusive writer to non-recursive locker dependency, "X -(EN)-> Y" means X -> Y and X is a writer and Y is either a writer or non-recursive reader.h]hexclusive writer to non-recursive locker dependency, “X -(EN)-> Y” means X -> Y and X is a writer and Y is either a writer or non-recursive reader.}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj ubah}(h]h ]h"]h$]h&]uh1j hj ubeh}(h]h ]h"]h$]h&]uh1j hhhMhj ubah}(h]h ]h"]h$]h&]uh1j hj ubah}(h]h ]h"]h$]h&]uh1jhj hhhNhNubj)}(h-(SR)->: shared reader to recursive reader dependency, "X -(SR)-> Y" means X -> Y and X is a reader (recursive or not) and Y is a recursive reader. h]j )}(hhh]j )}(h-(SR)->: shared reader to recursive reader dependency, "X -(SR)-> Y" means X -> Y and X is a reader (recursive or not) and Y is a recursive reader. h](j )}(h-(SR)->:h]h-(SR)->:}(hj0hhhNhNubah}(h]h ]h"]h$]h&]uh1j hhhM hj,ubj )}(hhh]h)}(hshared reader to recursive reader dependency, "X -(SR)-> Y" means X -> Y and X is a reader (recursive or not) and Y is a recursive reader.h]hshared reader to recursive reader dependency, “X -(SR)-> Y” means X -> Y and X is a reader (recursive or not) and Y is a recursive reader.}(hjAhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj>ubah}(h]h ]h"]h$]h&]uh1j hj,ubeh}(h]h ]h"]h$]h&]uh1j hhhM hj)ubah}(h]h ]h"]h$]h&]uh1j hj%ubah}(h]h ]h"]h$]h&]uh1jhj hhhNhNubj)}(h-(SN)->: shared reader to non-recursive locker dependency, "X -(SN)-> Y" means X -> Y and X is a reader (recursive or not) and Y is either a writer or non-recursive reader. h]j )}(hhh]j )}(h-(SN)->: shared reader to non-recursive locker dependency, "X -(SN)-> Y" means X -> Y and X is a reader (recursive or not) and Y is either a writer or non-recursive reader. h](j )}(h-(SN)->:h]h-(SN)->:}(hjrhhhNhNubah}(h]h ]h"]h$]h&]uh1j hhhM%hjnubj )}(hhh]h)}(hshared reader to non-recursive locker dependency, "X -(SN)-> Y" means X -> Y and X is a reader (recursive or not) and Y is either a writer or non-recursive reader.h]hshared reader to non-recursive locker dependency, “X -(SN)-> Y” means X -> Y and X is a reader (recursive or not) and Y is either a writer or non-recursive reader.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhM#hjubah}(h]h ]h"]h$]h&]uh1j hjnubeh}(h]h ]h"]h$]h&]uh1j hhhM%hjkubah}(h]h ]h"]h$]h&]uh1j hjgubah}(h]h ]h"]h$]h&]uh1jhj hhhNhNubeh}(h]h ]h"]h$]h&]jjjhj)uh1jhj? hhhhhMubh)}(hZNote that given two locks, they may have multiple dependencies between them, for example::h]hYNote that given two locks, they may have multiple dependencies between them, for example:}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhM'hj? hhubj)}(hQTASK A: read_lock(X); write_lock(Y); ... TASK B: write_lock(X); write_lock(Y);h]hQTASK A: read_lock(X); write_lock(Y); ... TASK B: write_lock(X); write_lock(Y);}hjsbah}(h]h ]h"]h$]h&]jjuh1jhhhM*hj? hhubh)}(hC, we have both X -(SN)-> Y and X -(EN)-> Y in the dependency graph.h]hC, we have both X -(SN)-> Y and X -(EN)-> Y in the dependency graph.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhM5hj? hhubh)}(hrWe use -(xN)-> to represent edges that are either -(EN)-> or -(SN)->, the similar for -(Ex)->, -(xR)-> and -(Sx)->h]hrWe use -(xN)-> to represent edges that are either -(EN)-> or -(SN)->, the similar for -(Ex)->, -(xR)-> and -(Sx)->}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhM7hj? hhubh)}(hX8A "path" is a series of conjunct dependency edges in the graph. And we define a "strong" path, which indicates the strong dependency throughout each dependency in the path, as the path that doesn't have two conjunct edges (dependencies) as -(xR)-> and -(Sx)->. In other words, a "strong" path is a path from a lock walking to another through the lock dependencies, and if X -> Y -> Z is in the path (where X, Y, Z are locks), and the walk from X to Y is through a -(SR)-> or -(ER)-> dependency, the walk from Y to Z must not be through a -(SN)-> or -(SR)-> dependency.h]hXFA “path” is a series of conjunct dependency edges in the graph. And we define a “strong” path, which indicates the strong dependency throughout each dependency in the path, as the path that doesn’t have two conjunct edges (dependencies) as -(xR)-> and -(Sx)->. In other words, a “strong” path is a path from a lock walking to another through the lock dependencies, and if X -> Y -> Z is in the path (where X, Y, Z are locks), and the walk from X to Y is through a -(SR)-> or -(ER)-> dependency, the walk from Y to Z must not be through a -(SN)-> or -(SR)-> dependency.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhM:hj? hhubh)}(h L2 ... -> Ln -> L1h]hL1 -> L2 ... -> Ln -> L1}hjsbah}(h]h ]h"]h$]h&]jjuh1jhhhM`hj hhubh)}(h$, which means we have dependencies::h]h#, which means we have dependencies:}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMbhj hhubj)}(h)L1 -> L2 L2 -> L3 ... Ln-1 -> Ln Ln -> L1h]h)L1 -> L2 L2 -> L3 ... Ln-1 -> Ln Ln -> L1}hjsbah}(h]h ]h"]h$]h&]jjuh1jhhhMdhj hhubh)}(hLWe now can construct a combination of locking sequences that cause deadlock:h]hLWe now can construct a combination of locking sequences that cause deadlock:}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMjhj hhubh)}(hFirstly let's make one CPU/task get the L1 in L1 -> L2, and then another get the L2 in L2 -> L3, and so on. After this, all of the Lx in Lx -> Lx+1 are held by different CPU/tasks.h]hFirstly let’s make one CPU/task get the L1 in L1 -> L2, and then another get the L2 in L2 -> L3, and so on. After this, all of the Lx in Lx -> Lx+1 are held by different CPU/tasks.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMlhj hhubh)}(hXAnd then because we have L1 -> L2, so the holder of L1 is going to acquire L2 in L1 -> L2, however since L2 is already held by another CPU/task, plus L1 -> L2 and L2 -> L3 are not -(xR)-> and -(Sx)-> (the definition of strong), which means either L2 in L1 -> L2 is a non-recursive locker (blocked by anyone) or the L2 in L2 -> L3, is writer (blocking anyone), therefore the holder of L1 cannot get L2, it has to wait L2's holder to release.h]hXAnd then because we have L1 -> L2, so the holder of L1 is going to acquire L2 in L1 -> L2, however since L2 is already held by another CPU/task, plus L1 -> L2 and L2 -> L3 are not -(xR)-> and -(Sx)-> (the definition of strong), which means either L2 in L1 -> L2 is a non-recursive locker (blocked by anyone) or the L2 in L2 -> L3, is writer (blocking anyone), therefore the holder of L1 cannot get L2, it has to wait L2’s holder to release.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMphj hhubh)}(hX-Moreover, we can have a similar conclusion for L2's holder: it has to wait L3's holder to release, and so on. We now can prove that Lx's holder has to wait for Lx+1's holder to release, and note that Ln+1 is L1, so we have a circular waiting scenario and nobody can get progress, therefore a deadlock.h]hX5Moreover, we can have a similar conclusion for L2’s holder: it has to wait L3’s holder to release, and so on. We now can prove that Lx’s holder has to wait for Lx+1’s holder to release, and note that Ln+1 is L1, so we have a circular waiting scenario and nobody can get progress, therefore a deadlock.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMwhj hhubh)}(hProof for necessary (Lemma 2):h]hProof for necessary (Lemma 2):}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhM|hj hhubh)}(hvLemma 2 is equivalent to: If there is a deadlock scenario, then there must be a strong circle in the dependency graph.h]hvLemma 2 is equivalent to: If there is a deadlock scenario, then there must be a strong circle in the dependency graph.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhM~hj hhubh)}(hXAccording to Wikipedia[1], if there is a deadlock, then there must be a circular waiting scenario, means there are N CPU/tasks, where CPU/task P1 is waiting for a lock held by P2, and P2 is waiting for a lock held by P3, ... and Pn is waiting for a lock held by P1. Let's name the lock Px is waiting as Lx, so since P1 is waiting for L1 and holding Ln, so we will have Ln -> L1 in the dependency graph. Similarly, we have L1 -> L2, L2 -> L3, ..., Ln-1 -> Ln in the dependency graph, which means we have a circle::h]hXAccording to Wikipedia[1], if there is a deadlock, then there must be a circular waiting scenario, means there are N CPU/tasks, where CPU/task P1 is waiting for a lock held by P2, and P2 is waiting for a lock held by P3, ... and Pn is waiting for a lock held by P1. Let’s name the lock Px is waiting as Lx, so since P1 is waiting for L1 and holding Ln, so we will have Ln -> L1 in the dependency graph. Similarly, we have L1 -> L2, L2 -> L3, ..., Ln-1 -> Ln in the dependency graph, which means we have a circle:}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj hhubj)}(hLn -> L1 -> L2 -> ... -> Lnh]hLn -> L1 -> L2 -> ... -> Ln}hjsbah}(h]h ]h"]h$]h&]jjuh1jhhhMhj hhubh)}(h+, and now let's prove the circle is strong:h]h-, and now let’s prove the circle is strong:}(hj'hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj hhubh)}(hXFor a lock Lx, Px contributes the dependency Lx-1 -> Lx and Px+1 contributes the dependency Lx -> Lx+1, and since Px is waiting for Px+1 to release Lx, so it's impossible that Lx on Px+1 is a reader and Lx on Px is a recursive reader, because readers (no matter recursive or not) don't block recursive readers, therefore Lx-1 -> Lx and Lx -> Lx+1 cannot be a -(xR)-> -(Sx)-> pair, and this is true for any lock in the circle, therefore, the circle is strong.h]hXFor a lock Lx, Px contributes the dependency Lx-1 -> Lx and Px+1 contributes the dependency Lx -> Lx+1, and since Px is waiting for Px+1 to release Lx, so it’s impossible that Lx on Px+1 is a reader and Lx on Px is a recursive reader, because readers (no matter recursive or not) don’t block recursive readers, therefore Lx-1 -> Lx and Lx -> Lx+1 cannot be a -(xR)-> -(Sx)-> pair, and this is true for any lock in the circle, therefore, the circle is strong.}(hj5hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj hhubeh}(h]!recursive-read-deadlock-detectionah ]h"]"recursive read deadlock detection:ah$]h&]uh1hhhhhhhhMFubh)}(hhh](h)}(h References:h]h References:}(hjNhhhNhNubah}(h]h ]h"]h$]h&]uh1hhjKhhhhhMubh)}(hx[1]: https://en.wikipedia.org/wiki/Deadlock [2]: Shibu, K. (2009). Intro To Embedded Systems (1st ed.). Tata McGraw-Hillh](h[1]: }(hj\hhhNhNubh)}(h&https://en.wikipedia.org/wiki/Deadlockh]h&https://en.wikipedia.org/wiki/Deadlock}(hjdhhhNhNubah}(h]h ]h"]h$]h&]refurijfuh1hhj\ubhM [2]: Shibu, K. (2009). Intro To Embedded Systems (1st ed.). Tata McGraw-Hill}(hj\hhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhMhjKhhubeh}(h] referencesah ]h"] references:ah$]h&]uh1hhhhhhhhMubeh}(h]%runtime-locking-correctness-validatorah ]h"]%runtime locking correctness validatorah$]h&]uh1hhhhhhhhKubeh}(h]h ]h"]h$]h&]sourcehuh1hcurrent_sourceN current_lineNsettingsdocutils.frontendValues)}(hN generatorN datestampN source_linkN source_urlN toc_backlinksjfootnote_backlinksK sectnum_xformKstrip_commentsNstrip_elements_with_classesN strip_classesN report_levelK halt_levelKexit_status_levelKdebugNwarning_streamN tracebackinput_encoding utf-8-siginput_encoding_error_handlerstrictoutput_encodingutf-8output_encoding_error_handlerjerror_encodingutf-8error_encoding_error_handlerbackslashreplace language_codeenrecord_dependenciesNconfigN id_prefixhauto_id_prefixid dump_settingsNdump_internalsNdump_transformsNdump_pseudo_xmlNexpose_internalsNstrict_visitorN_disable_configN_sourcehʌ _destinationN _config_files]7/var/lib/git/docbuild/linux/Documentation/docutils.confafile_insertion_enabled raw_enabledKline_length_limitM'pep_referencesN pep_base_urlhttps://peps.python.org/pep_file_url_templatepep-%04drfc_referencesN rfc_base_url&https://datatracker.ietf.org/doc/html/ tab_widthKtrim_footnote_reference_spacesyntax_highlightlong smart_quotessmartquotes_locales]character_level_inline_markupdoctitle_xform docinfo_xformKsectsubtitle_xform image_loadinglinkembed_stylesheetcloak_email_addressessection_self_linkenvNubreporterNindirect_targets]substitution_defs}substitution_names}refnames}1]jasrefids}nameids}(jjjaj^j/j,jjjjjjjjjjjjj_j\j` j] j' j$ j< j9 j jjHjEjju nametypes}(jjaj/jjjjjjj_j` j' j< j jHjuh}(jhj^jj,jdjj2jjjjjjjjjjjjj\jj] jbj$ jc j9 j* jj? jEj jjKu footnote_refs}j]jas citation_refs} autofootnotes]autofootnote_refs]symbol_footnotes]symbol_footnote_refs] footnotes]ja citations]autofootnote_startKsymbol_footnote_startK id_counter collectionsCounter}jKsRparse_messages]transform_messages] transformerN include_log] decorationNhhub.