lockdep: Optimize the memory usage of circular queue
PATCH 1/1 lockdep: Optimize the memory usage of circular queue
Qian Cai reported a BFS_EQUEUEFULL warning [1] after read recursive deadlock detection merged into tip tree recently. Unlike the previous lockep graph searching, which iterate every lock class (every node in the graph) exactly once, the graph searching for read recurisve deadlock detection needs to iterate every lock dependency (every edge in the graph) once, as a result, the maximum memory cost of the circular queue changes from O(V), where V is the number of lock classes (nodes or vertices) in the graph, to O(E), where E is the number of lock dependencies (edges), because every lock class or dependency gets enqueued once in the BFS. Therefore we hit the BFS_EQUEUEFULL case.
However, actually we don't need to enqueue all dependencies for the BFS, because every time we enqueue a dependency, we almostly enqueue all other dependencies in the same dependency list ("almostly" is because we currently check before enqueue, so if a dependency doesn't pass the check stage we won't enqueue it, however, we can always do in reverse ordering), based on this, we can only enqueue the first dependency from a dependency list and every time we want to fetch a new dependency to work, we can either:
1) fetch the dependency next to the current dependency in the
dependency list
or
2) if the dependency in 1) doesn't exist, fetch the dependency from
the queue.
With this approach, the "max bfs queue depth" for a x86_64_defconfig + lockdep and selftest config kernel can get descreased from:
max bfs queue depth: 201
to (after apply this patch)
max bfs queue depth: 61
While I'm at it, clean up the code logic a little (e.g. directly return other than set a "ret" value and goto the "exit" label).
[1]: https://lore.kernel.org/lkml/[email protected]/
--- kernel/locking/lockdep.c | 108 ++++++++++++++++++++++++--------------- 1 file changed, 67 insertions(+), 41 deletions(-)
kernel/locking/lockdep.c +67 -41
@@ -1640,35 +1640,22 @@ static enum bfs_result __bfs(struct lock_list *source_entry, int offset) {struct lock_list *entry; -struct lock_list *lock; +struct lock_list *lock =NULL ;struct list_head *head;struct circular_queue *cq = &lock_cq; -enum bfs_result ret =BFS_RNOMATCH ;lockdep_assert_locked (); -if (match (source_entry, data)) { - *target_entry = source_entry; - ret =BFS_RMATCH ; - goto exit; - } - - head =get_dep_list (source_entry, offset); -if (list_empty (head)) - goto exit; -__cq_init (cq);__cq_enqueue (cq, source_entry); -while ((lock =__cq_dequeue (cq))) { -bool prev_only_xr; - -if (!lock->class) { - ret =BFS_EINVALIDNODE ; - goto exit; - } +while (lock || (lock =__cq_dequeue (cq))) { +if (!lock->class) +return BFS_EINVALIDNODE ;/* +* Step 1: check whether we already finish on this one. +* * If we have visited all the dependencies from this @lock to * others (iow, if we have visited all lock_list entries in * @lock->class->locks_{after,before}) we skip, otherwise go
@@ -1676,17 +1663,17 @@ static enum bfs_result __bfs(struct lock_list *source_entry,* list accessed. */ if (lock_accessed (lock)) -continue ; + goto next;else mark_lock_accessed (lock); - head =get_dep_list (lock, offset); - - prev_only_xr = lock->only_xr; - -list_for_each_entry_rcu (entry, head, entry) { -unsigned int cq_depth; -u8 dep = entry->dep; +/* +* Step 2: check whether prev dependency and this form a strong +* dependency path. +*/ +if (lock->parent) {/* Parent exists, check prev dependency */ +u8 dep = lock->dep; +bool prev_only_xr = lock->parent->only_xr;/* * Mask out all -(S*)-> if we only have *R in previous
@@ -1698,29 +1685,68 @@ static enum bfs_result __bfs(struct lock_list *source_entry,/* If nothing left, we skip */ if (!dep) -continue ; + goto next;/* If there are only -(*R)-> left, set that for the next step */ - entry->only_xr = !(dep & (DEP_SN_MASK |DEP_EN_MASK )); + lock->only_xr = !(dep & (DEP_SN_MASK |DEP_EN_MASK )); + } -visit_lock_entry (entry, lock); -if (match (entry, data)) { - *target_entry = entry; - ret =BFS_RMATCH ; - goto exit; - } +/* +* Step 3: we haven't visited this and there is a strong +* dependency path to this, so check with @match. +*/ +if (match (lock, data)) { + *target_entry = lock; +return BFS_RMATCH ; + } + +/* +* Step 4: if not match, expand the path by adding the +* afterwards or backwards dependencis in the search +* +* Note we only enqueue the first of the list into the queue, +* because we can always find a sibling dependency from one +* (see label 'next'), as a result the space of queue is saved. +*/ + head =get_dep_list (lock, offset); + entry = list_first_or_null_rcu(head, struct lock_list, entry); +if (entry) { +unsigned int cq_depth; + +if (__cq_enqueue (cq, entry)) +return BFS_EQUEUEFULL ; -if (__cq_enqueue (cq, entry)) { - ret =BFS_EQUEUEFULL ; - goto exit; - } cq_depth =__cq_get_elem_count (cq);if (max_bfs_queue_depth < cq_depth) max_bfs_queue_depth = cq_depth; } + +/* +* Update the ->parent, so when @entry is iterated, we know the +* previous dependency. +*/ +list_for_each_entry_rcu (entry, head, entry) +visit_lock_entry (entry, lock); +next: +/* +* Step 5: fetch the next dependency to process. +* +* If there is a previous dependency, we fetch the sibling +* dependency in the dep list of previous dependency. +* +* Otherwise set @lock to NULL to fetch the next entry from +* queue. +*/ +if (lock->parent) { + head =get_dep_list (lock->parent, offset); + lock =list_next_or_null_rcu (head, &lock->entry, + struct lock_list, entry); + }else { + lock =NULL ; + } } -exit: -return ret; + +return BFS_RNOMATCH ; } static inline enum bfs_result
Signature · 1 line
2.28.0
Ping ;-)
Regards,
Boqun
Quoted 204 lines · Boqun Feng
Qian Cai reported a
BFS_EQUEUEFULLwarning [1] after read recursive deadlock detection merged into tip tree recently. Unlike the previous lockep graph searching, which iterate every lock class (every node in the graph) exactly once, the graph searching for read recurisve deadlock detection needs to iterate every lock dependency (every edge in the graph) once, as a result, the maximum memory cost of the circular queue changes from O(V), where V is the number of lock classes (nodes or vertices) in the graph, to O(E), where E is the number of lock dependencies (edges), because every lock class or dependency gets enqueued once in the BFS. Therefore we hit theBFS_EQUEUEFULLcase.However, actually we don't need to enqueue all dependencies for the BFS, because every time we enqueue a dependency, we almostly enqueue all other dependencies in the same dependency list ("almostly" is because we currently check before enqueue, so if a dependency doesn't pass the check stage we won't enqueue it, however, we can always do in reverse ordering), based on this, we can only enqueue the first dependency from a dependency list and every time we want to fetch a new dependency to work, we can either:
1) fetch the dependency next to the current dependency in the
dependency list
or
2) if the dependency in 1) doesn't exist, fetch the dependency from
the queue.With this approach, the "max bfs queue depth" for a
x86_64_defconfig+ lockdep and selftest config kernel can get descreased from:max bfs queue depth: 201
to (after apply this patch)
max bfs queue depth: 61
While I'm at it, clean up the code logic a little (e.g. directly return other than set a "ret" value and goto the "exit" label).
[1]: https://lore.kernel.org/lkml/[email protected]/
Reported-by Qian Cai <[email protected]>Signed-off-by Boqun Feng <[email protected]>--- kernel/locking/lockdep.c | 108 ++++++++++++++++++++++++--------------- 1 file changed, 67 insertions(+), 41 deletions(-)kernel/locking/lockdep.c +67
-41@@ -1640,35 +1640,22 @@ static enum bfs_result __bfs(struct lock_list *source_entry, int offset) {struct lock_list *entry; -struct lock_list *lock; +struct lock_list *lock =NULL ;struct list_head *head;struct circular_queue *cq = &lock_cq; -enum bfs_result ret =BFS_RNOMATCH ;lockdep_assert_locked (); -if (match (source_entry, data)) { - *target_entry = source_entry; - ret =BFS_RMATCH ; - goto exit; - } - - head =get_dep_list (source_entry, offset); -if (list_empty (head)) - goto exit; -__cq_init (cq);__cq_enqueue (cq, source_entry); -while ((lock =__cq_dequeue (cq))) { -bool prev_only_xr; - -if (!lock->class) { - ret =BFS_EINVALIDNODE ; - goto exit; - } +while (lock || (lock =__cq_dequeue (cq))) { +if (!lock->class) +return BFS_EINVALIDNODE ;/* +* Step 1: check whether we already finish on this one. +* * If we have visited all the dependencies from this @lock to * others (iow, if we have visited all lock_list entries in * @lock->class->locks_{after,before}) we skip, otherwise go @@ -1676,17 +1663,17 @@ static enum bfs_result __bfs(struct lock_list *source_entry,* list accessed. */ if (lock_accessed (lock)) -continue ; + goto next;else mark_lock_accessed (lock); - head =get_dep_list (lock, offset); - - prev_only_xr = lock->only_xr; - -list_for_each_entry_rcu (entry, head, entry) { -unsigned int cq_depth; -u8 dep = entry->dep; +/* +* Step 2: check whether prev dependency and this form a strong +* dependency path. +*/ +if (lock->parent) {/* Parent exists, check prev dependency */ +u8 dep = lock->dep; +bool prev_only_xr = lock->parent->only_xr;/* * Mask out all -(S*)-> if we only have *R in previous @@ -1698,29 +1685,68 @@ static enum bfs_result __bfs(struct lock_list *source_entry,/* If nothing left, we skip */ if (!dep) -continue ; + goto next;/* If there are only -(*R)-> left, set that for the next step */ - entry->only_xr = !(dep & (DEP_SN_MASK |DEP_EN_MASK )); + lock->only_xr = !(dep & (DEP_SN_MASK |DEP_EN_MASK )); + } -visit_lock_entry (entry, lock); -if (match (entry, data)) { - *target_entry = entry; - ret =BFS_RMATCH ; - goto exit; - } +/* +* Step 3: we haven't visited this and there is a strong +* dependency path to this, so check with @match. +*/ +if (match (lock, data)) { + *target_entry = lock; +return BFS_RMATCH ; + } + +/* +* Step 4: if not match, expand the path by adding the +* afterwards or backwards dependencis in the search +* +* Note we only enqueue the first of the list into the queue, +* because we can always find a sibling dependency from one +* (see label 'next'), as a result the space of queue is saved. +*/ + head =get_dep_list (lock, offset); + entry = list_first_or_null_rcu(head, struct lock_list, entry); +if (entry) { +unsigned int cq_depth; + +if (__cq_enqueue (cq, entry)) +return BFS_EQUEUEFULL ; -if (__cq_enqueue (cq, entry)) { - ret =BFS_EQUEUEFULL ; - goto exit; - } cq_depth =__cq_get_elem_count (cq);if (max_bfs_queue_depth < cq_depth) max_bfs_queue_depth = cq_depth; } + +/* +* Update the ->parent, so when @entry is iterated, we know the +* previous dependency. +*/ +list_for_each_entry_rcu (entry, head, entry) +visit_lock_entry (entry, lock); +next: +/* +* Step 5: fetch the next dependency to process. +* +* If there is a previous dependency, we fetch the sibling +* dependency in the dep list of previous dependency. +* +* Otherwise set @lock to NULL to fetch the next entry from +* queue. +*/ +if (lock->parent) { + head =get_dep_list (lock->parent, offset); + lock =list_next_or_null_rcu (head, &lock->entry, + struct lock_list, entry); + }else { + lock =NULL ; + } } -exit: -return ret; + +return BFS_RNOMATCH ; } static inline enum bfs_resultSignature · 1 line
2.28.0
Quoted 5 lines · Boqun Feng
Ping ;-)
Regards,
Boqun
Hi Boqun,
Peter says this may also fix this issue:
https://syzkaller.appspot.com/bug?extid=62ebe501c1ce9a91f68c
please add the following tag to the patch so that the bug report will be closed on merge:
Quoted 205 lines · Boqun Feng
Quoted 204 lines
Qian Cai reported a
BFS_EQUEUEFULLwarning [1] after read recursive deadlock detection merged into tip tree recently. Unlike the previous lockep graph searching, which iterate every lock class (every node in the graph) exactly once, the graph searching for read recurisve deadlock detection needs to iterate every lock dependency (every edge in the graph) once, as a result, the maximum memory cost of the circular queue changes from O(V), where V is the number of lock classes (nodes or vertices) in the graph, to O(E), where E is the number of lock dependencies (edges), because every lock class or dependency gets enqueued once in the BFS. Therefore we hit theBFS_EQUEUEFULLcase.However, actually we don't need to enqueue all dependencies for the BFS, because every time we enqueue a dependency, we almostly enqueue all other dependencies in the same dependency list ("almostly" is because we currently check before enqueue, so if a dependency doesn't pass the check stage we won't enqueue it, however, we can always do in reverse ordering), based on this, we can only enqueue the first dependency from a dependency list and every time we want to fetch a new dependency to work, we can either:
1) fetch the dependency next to the current dependency in the
dependency list
or
2) if the dependency in 1) doesn't exist, fetch the dependency from
the queue.With this approach, the "max bfs queue depth" for a
x86_64_defconfig+ lockdep and selftest config kernel can get descreased from:max bfs queue depth: 201
to (after apply this patch)
max bfs queue depth: 61
While I'm at it, clean up the code logic a little (e.g. directly return other than set a "ret" value and goto the "exit" label).
[1]: https://lore.kernel.org/lkml/[email protected]/
Reported-by Qian Cai <[email protected]>Signed-off-by Boqun Feng <[email protected]>--- kernel/locking/lockdep.c | 108 ++++++++++++++++++++++++--------------- 1 file changed, 67 insertions(+), 41 deletions(-)kernel/locking/lockdep.c +67
-42@@ -1640,35 +1640,22 @@ static enum bfs_result __bfs(struct lock_list *source_entry, int offset) {struct lock_list *entry; -struct lock_list *lock; +struct lock_list *lock =NULL ;struct list_head *head;struct circular_queue *cq = &lock_cq; -enum bfs_result ret =BFS_RNOMATCH ;lockdep_assert_locked (); -if (match (source_entry, data)) { - *target_entry = source_entry; - ret =BFS_RMATCH ; - goto exit; - } - - head =get_dep_list (source_entry, offset); -if (list_empty (head)) - goto exit; -__cq_init (cq);__cq_enqueue (cq, source_entry); -while ((lock =__cq_dequeue (cq))) { -bool prev_only_xr; - -if (!lock->class) { - ret =BFS_EINVALIDNODE ; - goto exit; - } +while (lock || (lock =__cq_dequeue (cq))) { +if (!lock->class) +return BFS_EINVALIDNODE ;/* +* Step 1: check whether we already finish on this one. +* * If we have visited all the dependencies from this @lock to * others (iow, if we have visited all lock_list entries in * @lock->class->locks_{after,before}) we skip, otherwise go @@ -1676,17 +1663,17 @@ static enum bfs_result __bfs(struct lock_list *source_entry,* list accessed. */ if (lock_accessed (lock)) -continue ; + goto next;else mark_lock_accessed (lock); - head =get_dep_list (lock, offset); - - prev_only_xr = lock->only_xr; - -list_for_each_entry_rcu (entry, head, entry) { -unsigned int cq_depth; -u8 dep = entry->dep; +/* +* Step 2: check whether prev dependency and this form a strong +* dependency path. +*/ +if (lock->parent) {/* Parent exists, check prev dependency */ +u8 dep = lock->dep; +bool prev_only_xr = lock->parent->only_xr;/* * Mask out all -(S*)-> if we only have *R in previous @@ -1698,29 +1685,68 @@ static enum bfs_result __bfs(struct lock_list *source_entry,/* If nothing left, we skip */ if (!dep) -continue ; + goto next;/* If there are only -(*R)-> left, set that for the next step */ - entry->only_xr = !(dep & (DEP_SN_MASK |DEP_EN_MASK )); + lock->only_xr = !(dep & (DEP_SN_MASK |DEP_EN_MASK )); + } -visit_lock_entry (entry, lock); -if (match (entry, data)) { - *target_entry = entry; - ret =BFS_RMATCH ; - goto exit; - } +/* +* Step 3: we haven't visited this and there is a strong +* dependency path to this, so check with @match. +*/ +if (match (lock, data)) { + *target_entry = lock; +return BFS_RMATCH ; + } + +/* +* Step 4: if not match, expand the path by adding the +* afterwards or backwards dependencis in the search +* +* Note we only enqueue the first of the list into the queue, +* because we can always find a sibling dependency from one +* (see label 'next'), as a result the space of queue is saved. +*/ + head =get_dep_list (lock, offset); + entry = list_first_or_null_rcu(head, struct lock_list, entry); +if (entry) { +unsigned int cq_depth; + +if (__cq_enqueue (cq, entry)) +return BFS_EQUEUEFULL ; -if (__cq_enqueue (cq, entry)) { - ret =BFS_EQUEUEFULL ; - goto exit; - } cq_depth =__cq_get_elem_count (cq);if (max_bfs_queue_depth < cq_depth) max_bfs_queue_depth = cq_depth; } + +/* +* Update the ->parent, so when @entry is iterated, we know the +* previous dependency. +*/ +list_for_each_entry_rcu (entry, head, entry) +visit_lock_entry (entry, lock); +next: +/* +* Step 5: fetch the next dependency to process. +* +* If there is a previous dependency, we fetch the sibling +* dependency in the dep list of previous dependency. +* +* Otherwise set @lock to NULL to fetch the next entry from +* queue. +*/ +if (lock->parent) { + head =get_dep_list (lock->parent, offset); + lock =list_next_or_null_rcu (head, &lock->entry, + struct lock_list, entry); + }else { + lock =NULL ; + } } -exit: -return ret; + +return BFS_RNOMATCH ; } static inline enum bfs_result --2.28.0
Quoted 7 lines · Dmitry Vyukov
Quoted 5 lines · Boqun Feng
Ping ;-)
Regards,
Boqun
Quoted 8 lines
Hi Boqun,
Peter says this may also fix this issue:
https://syzkaller.appspot.com/bug?extid=62ebe501c1ce9a91f68c
please add the following tag to the patch so that the bug report will be closed on merge:Reported-by [email protected]
Sure, I will if another version of this patch is required, otherwise (if this one looks good to Peter), I will rely on Peter to add the tag ;-) Works for you?
Regards,
Boqun
Quoted 205 lines
Quoted 205 lines · Boqun Feng
Quoted 204 lines
Qian Cai reported a
BFS_EQUEUEFULLwarning [1] after read recursive deadlock detection merged into tip tree recently. Unlike the previous lockep graph searching, which iterate every lock class (every node in the graph) exactly once, the graph searching for read recurisve deadlock detection needs to iterate every lock dependency (every edge in the graph) once, as a result, the maximum memory cost of the circular queue changes from O(V), where V is the number of lock classes (nodes or vertices) in the graph, to O(E), where E is the number of lock dependencies (edges), because every lock class or dependency gets enqueued once in the BFS. Therefore we hit theBFS_EQUEUEFULLcase.However, actually we don't need to enqueue all dependencies for the BFS, because every time we enqueue a dependency, we almostly enqueue all other dependencies in the same dependency list ("almostly" is because we currently check before enqueue, so if a dependency doesn't pass the check stage we won't enqueue it, however, we can always do in reverse ordering), based on this, we can only enqueue the first dependency from a dependency list and every time we want to fetch a new dependency to work, we can either:
1) fetch the dependency next to the current dependency in the
dependency list
or
2) if the dependency in 1) doesn't exist, fetch the dependency from
the queue.With this approach, the "max bfs queue depth" for a
x86_64_defconfig+ lockdep and selftest config kernel can get descreased from:max bfs queue depth: 201
to (after apply this patch)
max bfs queue depth: 61
While I'm at it, clean up the code logic a little (e.g. directly return other than set a "ret" value and goto the "exit" label).
[1]: https://lore.kernel.org/lkml/[email protected]/
Reported-by Qian Cai <[email protected]>Signed-off-by Boqun Feng <[email protected]>--- kernel/locking/lockdep.c | 108 ++++++++++++++++++++++++--------------- 1 file changed, 67 insertions(+), 41 deletions(-)kernel/locking/lockdep.c +67
-42@@ -1640,35 +1640,22 @@ static enum bfs_result __bfs(struct lock_list *source_entry, int offset) {struct lock_list *entry; -struct lock_list *lock; +struct lock_list *lock =NULL ;struct list_head *head;struct circular_queue *cq = &lock_cq; -enum bfs_result ret =BFS_RNOMATCH ;lockdep_assert_locked (); -if (match (source_entry, data)) { - *target_entry = source_entry; - ret =BFS_RMATCH ; - goto exit; - } - - head =get_dep_list (source_entry, offset); -if (list_empty (head)) - goto exit; -__cq_init (cq);__cq_enqueue (cq, source_entry); -while ((lock =__cq_dequeue (cq))) { -bool prev_only_xr; - -if (!lock->class) { - ret =BFS_EINVALIDNODE ; - goto exit; - } +while (lock || (lock =__cq_dequeue (cq))) { +if (!lock->class) +return BFS_EINVALIDNODE ;/* +* Step 1: check whether we already finish on this one. +* * If we have visited all the dependencies from this @lock to * others (iow, if we have visited all lock_list entries in * @lock->class->locks_{after,before}) we skip, otherwise go @@ -1676,17 +1663,17 @@ static enum bfs_result __bfs(struct lock_list *source_entry,* list accessed. */ if (lock_accessed (lock)) -continue ; + goto next;else mark_lock_accessed (lock); - head =get_dep_list (lock, offset); - - prev_only_xr = lock->only_xr; - -list_for_each_entry_rcu (entry, head, entry) { -unsigned int cq_depth; -u8 dep = entry->dep; +/* +* Step 2: check whether prev dependency and this form a strong +* dependency path. +*/ +if (lock->parent) {/* Parent exists, check prev dependency */ +u8 dep = lock->dep; +bool prev_only_xr = lock->parent->only_xr;/* * Mask out all -(S*)-> if we only have *R in previous @@ -1698,29 +1685,68 @@ static enum bfs_result __bfs(struct lock_list *source_entry,/* If nothing left, we skip */ if (!dep) -continue ; + goto next;/* If there are only -(*R)-> left, set that for the next step */ - entry->only_xr = !(dep & (DEP_SN_MASK |DEP_EN_MASK )); + lock->only_xr = !(dep & (DEP_SN_MASK |DEP_EN_MASK )); + } -visit_lock_entry (entry, lock); -if (match (entry, data)) { - *target_entry = entry; - ret =BFS_RMATCH ; - goto exit; - } +/* +* Step 3: we haven't visited this and there is a strong +* dependency path to this, so check with @match. +*/ +if (match (lock, data)) { + *target_entry = lock; +return BFS_RMATCH ; + } + +/* +* Step 4: if not match, expand the path by adding the +* afterwards or backwards dependencis in the search +* +* Note we only enqueue the first of the list into the queue, +* because we can always find a sibling dependency from one +* (see label 'next'), as a result the space of queue is saved. +*/ + head =get_dep_list (lock, offset); + entry = list_first_or_null_rcu(head, struct lock_list, entry); +if (entry) { +unsigned int cq_depth; + +if (__cq_enqueue (cq, entry)) +return BFS_EQUEUEFULL ; -if (__cq_enqueue (cq, entry)) { - ret =BFS_EQUEUEFULL ; - goto exit; - } cq_depth =__cq_get_elem_count (cq);if (max_bfs_queue_depth < cq_depth) max_bfs_queue_depth = cq_depth; } + +/* +* Update the ->parent, so when @entry is iterated, we know the +* previous dependency. +*/ +list_for_each_entry_rcu (entry, head, entry) +visit_lock_entry (entry, lock); +next: +/* +* Step 5: fetch the next dependency to process. +* +* If there is a previous dependency, we fetch the sibling +* dependency in the dep list of previous dependency. +* +* Otherwise set @lock to NULL to fetch the next entry from +* queue. +*/ +if (lock->parent) { + head =get_dep_list (lock->parent, offset); + lock =list_next_or_null_rcu (head, &lock->entry, + struct lock_list, entry); + }else { + lock =NULL ; + } } -exit: -return ret; + +return BFS_RNOMATCH ; } static inline enum bfs_result --2.28.0
Quoted 18 lines · Boqun Feng
Quoted 7 lines · Dmitry Vyukov
Quoted 5 lines · Boqun Feng
Ping ;-)
Regards,
BoqunQuoted 8 lines
Hi Boqun,
Peter says this may also fix this issue:
https://syzkaller.appspot.com/bug?extid=62ebe501c1ce9a91f68c
please add the following tag to the patch so that the bug report will be closed on merge:Reported-by [email protected]
Quoted 3 lines
Sure, I will if another version of this patch is required, otherwise (if this one looks good to Peter), I will rely on Peter to add the tag ;-) Works for you?
Yes, totally, thanks.
Quoted 208 lines
Regards,
BoqunQuoted 205 lines
Quoted 205 lines · Boqun Feng
Quoted 204 lines
Qian Cai reported a
BFS_EQUEUEFULLwarning [1] after read recursive deadlock detection merged into tip tree recently. Unlike the previous lockep graph searching, which iterate every lock class (every node in the graph) exactly once, the graph searching for read recurisve deadlock detection needs to iterate every lock dependency (every edge in the graph) once, as a result, the maximum memory cost of the circular queue changes from O(V), where V is the number of lock classes (nodes or vertices) in the graph, to O(E), where E is the number of lock dependencies (edges), because every lock class or dependency gets enqueued once in the BFS. Therefore we hit theBFS_EQUEUEFULLcase.However, actually we don't need to enqueue all dependencies for the BFS, because every time we enqueue a dependency, we almostly enqueue all other dependencies in the same dependency list ("almostly" is because we currently check before enqueue, so if a dependency doesn't pass the check stage we won't enqueue it, however, we can always do in reverse ordering), based on this, we can only enqueue the first dependency from a dependency list and every time we want to fetch a new dependency to work, we can either:
1) fetch the dependency next to the current dependency in the
dependency list
or
2) if the dependency in 1) doesn't exist, fetch the dependency from
the queue.With this approach, the "max bfs queue depth" for a
x86_64_defconfig+ lockdep and selftest config kernel can get descreased from:max bfs queue depth: 201
to (after apply this patch)
max bfs queue depth: 61
While I'm at it, clean up the code logic a little (e.g. directly return other than set a "ret" value and goto the "exit" label).
[1]: https://lore.kernel.org/lkml/[email protected]/
Reported-by Qian Cai <[email protected]>Signed-off-by Boqun Feng <[email protected]>--- kernel/locking/lockdep.c | 108 ++++++++++++++++++++++++--------------- 1 file changed, 67 insertions(+), 41 deletions(-)kernel/locking/lockdep.c +67
-42@@ -1640,35 +1640,22 @@ static enum bfs_result __bfs(struct lock_list *source_entry, int offset) {struct lock_list *entry; -struct lock_list *lock; +struct lock_list *lock =NULL ;struct list_head *head;struct circular_queue *cq = &lock_cq; -enum bfs_result ret =BFS_RNOMATCH ;lockdep_assert_locked (); -if (match (source_entry, data)) { - *target_entry = source_entry; - ret =BFS_RMATCH ; - goto exit; - } - - head =get_dep_list (source_entry, offset); -if (list_empty (head)) - goto exit; -__cq_init (cq);__cq_enqueue (cq, source_entry); -while ((lock =__cq_dequeue (cq))) { -bool prev_only_xr; - -if (!lock->class) { - ret =BFS_EINVALIDNODE ; - goto exit; - } +while (lock || (lock =__cq_dequeue (cq))) { +if (!lock->class) +return BFS_EINVALIDNODE ;/* +* Step 1: check whether we already finish on this one. +* * If we have visited all the dependencies from this @lock to * others (iow, if we have visited all lock_list entries in * @lock->class->locks_{after,before}) we skip, otherwise go @@ -1676,17 +1663,17 @@ static enum bfs_result __bfs(struct lock_list *source_entry,* list accessed. */ if (lock_accessed (lock)) -continue ; + goto next;else mark_lock_accessed (lock); - head =get_dep_list (lock, offset); - - prev_only_xr = lock->only_xr; - -list_for_each_entry_rcu (entry, head, entry) { -unsigned int cq_depth; -u8 dep = entry->dep; +/* +* Step 2: check whether prev dependency and this form a strong +* dependency path. +*/ +if (lock->parent) {/* Parent exists, check prev dependency */ +u8 dep = lock->dep; +bool prev_only_xr = lock->parent->only_xr;/* * Mask out all -(S*)-> if we only have *R in previous @@ -1698,29 +1685,68 @@ static enum bfs_result __bfs(struct lock_list *source_entry,/* If nothing left, we skip */ if (!dep) -continue ; + goto next;/* If there are only -(*R)-> left, set that for the next step */ - entry->only_xr = !(dep & (DEP_SN_MASK |DEP_EN_MASK )); + lock->only_xr = !(dep & (DEP_SN_MASK |DEP_EN_MASK )); + } -visit_lock_entry (entry, lock); -if (match (entry, data)) { - *target_entry = entry; - ret =BFS_RMATCH ; - goto exit; - } +/* +* Step 3: we haven't visited this and there is a strong +* dependency path to this, so check with @match. +*/ +if (match (lock, data)) { + *target_entry = lock; +return BFS_RMATCH ; + } + +/* +* Step 4: if not match, expand the path by adding the +* afterwards or backwards dependencis in the search +* +* Note we only enqueue the first of the list into the queue, +* because we can always find a sibling dependency from one +* (see label 'next'), as a result the space of queue is saved. +*/ + head =get_dep_list (lock, offset); + entry = list_first_or_null_rcu(head, struct lock_list, entry); +if (entry) { +unsigned int cq_depth; + +if (__cq_enqueue (cq, entry)) +return BFS_EQUEUEFULL ; -if (__cq_enqueue (cq, entry)) { - ret =BFS_EQUEUEFULL ; - goto exit; - } cq_depth =__cq_get_elem_count (cq);if (max_bfs_queue_depth < cq_depth) max_bfs_queue_depth = cq_depth; } + +/* +* Update the ->parent, so when @entry is iterated, we know the +* previous dependency. +*/ +list_for_each_entry_rcu (entry, head, entry) +visit_lock_entry (entry, lock); +next: +/* +* Step 5: fetch the next dependency to process. +* +* If there is a previous dependency, we fetch the sibling +* dependency in the dep list of previous dependency. +* +* Otherwise set @lock to NULL to fetch the next entry from +* queue. +*/ +if (lock->parent) { + head =get_dep_list (lock->parent, offset); + lock =list_next_or_null_rcu (head, &lock->entry, + struct lock_list, entry); + }else { + lock =NULL ; + } } -exit: -return ret; + +return BFS_RNOMATCH ; } static inline enum bfs_result --2.28.0
Peter Zijlstra
maintainerQuoted 50 lines · Boqun Feng
(quoted diff) +32
-0__cq_init(cq); __cq_enqueue(cq, source_entry); + while (lock || (lock = __cq_dequeue(cq))) { + if (!lock->class) + return BFS_EINVALIDNODE; /* + * Step 1: check whether we already finish on this one. + * * If we have visited all the dependencies from this @lock to * others (iow, if we have visited all lock_list entries in * @lock->class->locks_{after,before}) we skip, otherwise go@@ -1698,29 +1685,68 @@ static enum bfs_result __bfs(struct lock_list *source_entry, /* If nothing left, we skip */ if (!dep) + goto next; /* If there are only -(*R)-> left, set that for the next step */ + lock->only_xr = !(dep & (DEP_SN_MASK | DEP_EN_MASK)); + } + /* + * Step 3: we haven't visited this and there is a strong + * dependency path to this, so check with @match. + */ + if (match(lock, data)) { + *target_entry = lock; + return BFS_RMATCH; + } + + /* + * Step 4: if not match, expand the path by adding the + * afterwards or backwards dependencis in the search + * + * Note we only enqueue the first of the list into the queue, + * because we can always find a sibling dependency from one + * (see label 'next'), as a result the space of queue is saved. + */ + head = get_dep_list(lock, offset); + entry = list_first_or_null_rcu(head, struct lock_list, entry); + if (entry) { + unsigned int cq_depth; + + if (__cq_enqueue(cq, entry)) + return BFS_EQUEUEFULL; cq_depth = __cq_get_elem_count(cq);
Review static enum bfs_result __bfs(struct lock_list *source_entry, · line 1729
Quoted 10 lines
(quoted diff) +7
-0if (max_bfs_queue_depth < cq_depth) max_bfs_queue_depth = cq_depth; } + + /* + * Update the ->parent, so when @entry is iterated, we know the + * previous dependency. + */ + list_for_each_entry_rcu(entry, head, entry) + visit_lock_entry(entry, lock);
This confused me for a while. I think it might be a little clearer if we put this inside the previous block.
Alternatively, we could try and write it something like so:
/*
* Step 4: if not match, expand the path by adding the
* afterwards or backwards dependencis in the search
*/
first = true;
head = get_dep_list(lock, offset);
list_for_each_entry_rcu(entry, head, entry) {
visit_lock_entry(entry, lock);
if (!first)
continue;
/*
* Only enqueue the first entry of the list,
* we'll iterate it's siblings at the next
* label.
*/
first = false;
if (__cq_enqueue(cq, entry))
return BFS_EQUEUEFULL;
cq_depth = __cq_get_elem_count(cq);
if (max_bfs_queue_depth < cq_depth)
max_bfs_queue_depth = cq_depth;
}Hmm?
Quoted 7 lines
(quoted diff) +7
-0+next: + /* + * Step 5: fetch the next dependency to process. + * + * If there is a previous dependency, we fetch the sibling + * dependency in the dep list of previous dependency. + *
Review static enum bfs_result __bfs(struct lock_list *source_entry, · line 1746
Quoted 10 lines
(quoted diff) +10
-0+ * Otherwise set @lock to NULL to fetch the next entry from + * queue. + */ + if (lock->parent) { + head = get_dep_list(lock->parent, offset); + lock = list_next_or_null_rcu(head, &lock->entry, + struct lock_list, entry); + } else { + lock = NULL; + }
I think that if we hide this in a __bfs_next() helper, the iteration becomes nicer.
Review static enum bfs_result __bfs(struct lock_list *source_entry, · line 1750
Quoted 5 lines
(quoted diff) +2
-1} -exit: + + return BFS_RNOMATCH; }
How's this?
---
Subject: lockdep: Optimize the memory usage of circular queue
From: Boqun Feng <[email protected]>
Date: Thu, 17 Sep 2020 16:01:50 +0800
From: Boqun Feng <[email protected]>
Qian Cai reported a BFS_EQUEUEFULL warning [1] after read recursive deadlock detection merged into tip tree recently. Unlike the previous lockep graph searching, which iterate every lock class (every node in the graph) exactly once, the graph searching for read recurisve deadlock detection needs to iterate every lock dependency (every edge in the graph) once, as a result, the maximum memory cost of the circular queue changes from O(V), where V is the number of lock classes (nodes or vertices) in the graph, to O(E), where E is the number of lock dependencies (edges), because every lock class or dependency gets enqueued once in the BFS. Therefore we hit the BFS_EQUEUEFULL case.
However, actually we don't need to enqueue all dependencies for the BFS, because every time we enqueue a dependency, we almostly enqueue all other dependencies in the same dependency list ("almostly" is because we currently check before enqueue, so if a dependency doesn't pass the check stage we won't enqueue it, however, we can always do in reverse ordering), based on this, we can only enqueue the first dependency from a dependency list and every time we want to fetch a new dependency to work, we can either:
1) fetch the dependency next to the current dependency in the
dependency list
or
2) if the dependency in 1) doesn't exist, fetch the dependency from
the queue.
With this approach, the "max bfs queue depth" for a x86_64_defconfig + lockdep and selftest config kernel can get descreased from:
max bfs queue depth: 201
to (after apply this patch)
max bfs queue depth: 61
While I'm at it, clean up the code logic a little (e.g. directly return other than set a "ret" value and goto the "exit" label).
[1]: https://lore.kernel.org/lkml/[email protected]/
--- kernel/locking/lockdep.c | 101 ++++++++++++++++++++++++++++------------------- 1 file changed, 61 insertions(+), 40 deletions(-)
kernel/locking/lockdep.c +61 -40
@@ -1606,6 +1606,15 @@ static inline void bfs_init_rootb(struct lock->only_xr = (hlock->read !=0 ); } +static inline struct lock_list *__bfs_next (struct lock_list *lock,int offset) +{ +if (!lock || !lock->parent) +return NULL ; + +return list_next_or_null_rcu (get_dep_list (lock->parent, offset), + &lock->entry, struct lock_list, entry); +} +/* * Breadth-First Search to find a strong path in the dependency graph. *
@@ -1639,36 +1648,25 @@ static enum bfs_result __bfs(struct lock struct lock_list **target_entry, int offset) { +struct circular_queue *cq = &lock_cq; +struct lock_list *lock =NULL ;struct lock_list *entry; -struct lock_list *lock;struct list_head *head; -struct circular_queue *cq = &lock_cq; -enum bfs_result ret =BFS_RNOMATCH ; +unsigned int cq_depth; +bool first;lockdep_assert_locked (); -if (match (source_entry, data)) { - *target_entry = source_entry; - ret =BFS_RMATCH ; - goto exit; - } - - head =get_dep_list (source_entry, offset); -if (list_empty (head)) - goto exit; -__cq_init (cq);__cq_enqueue (cq, source_entry); -while ((lock =__cq_dequeue (cq))) { -bool prev_only_xr; - -if (!lock->class) { - ret =BFS_EINVALIDNODE ; - goto exit; - } +while ((lock =__bfs_next (lock, offset)) || (lock =__cq_dequeue (cq))) { +if (!lock->class) +return BFS_EINVALIDNODE ;/* +* Step 1: check whether we already finish on this one. +* * If we have visited all the dependencies from this @lock to * others (iow, if we have visited all lock_list entries in * @lock->class->locks_{after,before}) we skip, otherwise go
@@ -1680,13 +1678,13 @@ static enum bfs_result __bfs(struct lockelse mark_lock_accessed (lock); - head =get_dep_list (lock, offset); - - prev_only_xr = lock->only_xr; - -list_for_each_entry_rcu (entry, head, entry) { -unsigned int cq_depth; -u8 dep = entry->dep; +/* +* Step 2: check whether prev dependency and this form a strong +* dependency path. +*/ +if (lock->parent) {/* Parent exists, check prev dependency */ +u8 dep = lock->dep; +bool prev_only_xr = lock->parent->only_xr;/* * Mask out all -(S*)-> if we only have *R in previous
@@ -1701,26 +1699,49 @@ static enum bfs_result __bfs(struct lockcontinue ;/* If there are only -(*R)-> left, set that for the next step */ - entry->only_xr = !(dep & (DEP_SN_MASK |DEP_EN_MASK )); + lock->only_xr = !(dep & (DEP_SN_MASK |DEP_EN_MASK )); + } + +/* +* Step 3: we haven't visited this and there is a strong +* dependency path to this, so check with @match. +*/ +if (match (lock, data)) { + *target_entry = lock; +return BFS_RMATCH ; + } +/* +* Step 4: if not match, expand the path by adding the +* afterwards or backwards dependencis in the search +* +*/ + first = true; + head =get_dep_list (lock, offset); +list_for_each_entry_rcu (entry, head, entry) {visit_lock_entry (entry, lock); -if (match (entry, data)) { - *target_entry = entry; - ret =BFS_RMATCH ; - goto exit; - } - -if (__cq_enqueue (cq, entry)) { - ret =BFS_EQUEUEFULL ; - goto exit; - } + +/* +* Note we only enqueue the first of the list into the +* queue, because we can always find a sibling +* dependency from one (see _bfs_next()), as a result +* the space of queue is saved. +*/ +if (!first) +continue ; + + first = false; + +if (__cq_enqueue (cq, entry)) +return BFS_EQUEUEFULL ; + cq_depth =__cq_get_elem_count (cq);if (max_bfs_queue_depth < cq_depth) max_bfs_queue_depth = cq_depth; } } -exit: -return ret; + +return BFS_RNOMATCH ; } static inline enum bfs_result
Quoted 94 lines · Peter Zijlstra
Quoted 50 lines · Boqun Feng
kernel/locking/lockdep.c +32
-0__cq_init (cq);__cq_enqueue (cq, source_entry); +while (lock || (lock =__cq_dequeue (cq))) { +if (!lock->class) +return BFS_EINVALIDNODE ;/* +* Step 1: check whether we already finish on this one. +* * If we have visited all the dependencies from this @lock to * others (iow, if we have visited all lock_list entries in * @lock->class->locks_{after,before}) we skip, otherwise go @@ -1698,29 +1685,68 @@ static enum bfs_result __bfs(struct lock_list *source_entry,/* If nothing left, we skip */ if (!dep) + goto next;/* If there are only -(*R)-> left, set that for the next step */ + lock->only_xr = !(dep & (DEP_SN_MASK |DEP_EN_MASK )); + } +/* +* Step 3: we haven't visited this and there is a strong +* dependency path to this, so check with @match. +*/ +if (match (lock, data)) { + *target_entry = lock; +return BFS_RMATCH ; + } + +/* +* Step 4: if not match, expand the path by adding the +* afterwards or backwards dependencis in the search +* +* Note we only enqueue the first of the list into the queue, +* because we can always find a sibling dependency from one +* (see label 'next'), as a result the space of queue is saved. +*/ + head =get_dep_list (lock, offset); + entry = list_first_or_null_rcu(head, struct lock_list, entry); +if (entry) { +unsigned int cq_depth; + +if (__cq_enqueue (cq, entry)) +return BFS_EQUEUEFULL ; cq_depth =__cq_get_elem_count (cq);kernel/locking/lockdep.c static enum bfs_result __bfs(struct lock_list *source_entry, · line 1729
Quoted 10 lines
kernel/locking/lockdep.c +7
-0if (max_bfs_queue_depth < cq_depth) max_bfs_queue_depth = cq_depth; } + +/* +* Update the ->parent, so when @entry is iterated, we know the +* previous dependency. +*/ +list_for_each_entry_rcu (entry, head, entry) +visit_lock_entry (entry, lock);This confused me for a while. I think it might be a little clearer if we put this inside the previous block.
Alternatively, we could try and write it something like so:
/* * Step 4: if not match, expand the path by adding the * afterwards or backwards dependencis in the search */ first = true; head = get_dep_list(lock, offset); list_for_each_entry_rcu(entry, head, entry) { visit_lock_entry(entry, lock); if (!first) continue; /* * Only enqueue the first entry of the list, * we'll iterate it's siblings at the next * label. */ first = false; if (__cq_enqueue(cq, entry)) return BFS_EQUEUEFULL; cq_depth = __cq_get_elem_count(cq); if (max_bfs_queue_depth < cq_depth) max_bfs_queue_depth = cq_depth; }
Quoted 2 lines
Hmm?
Better than mine ;-)
Quoted 21 lines
Quoted 7 lines
(quoted diff) +7
-0+next: + /* + * Step 5: fetch the next dependency to process. + * + * If there is a previous dependency, we fetch the sibling + * dependency in the dep list of previous dependency. + *Review static enum bfs_result __bfs(struct lock_list *source_entry, · line 1746
Quoted 10 lines
(quoted diff) +10
-0+ * Otherwise set @lock to NULL to fetch the next entry from + * queue. + */ + if (lock->parent) { + head = get_dep_list(lock->parent, offset); + lock = list_next_or_null_rcu(head, &lock->entry, + struct lock_list, entry); + } else { + lock = NULL; + }I think that if we hide this in a
__bfs_next()helper, the iteration becomes nicer.
Quoted 8 lines
kernel/locking/lockdep.c static enum bfs_result __bfs(struct lock · line 1745
Quoted 5 lines
kernel/locking/lockdep.c +2
-1} -exit: + +return BFS_RNOMATCH ; }How's this?
I think your version is better and should be functionally identical to mine, also FWIW, I tested with a lockdep boot selftests, everything worked fine.
Regards,
Boqun
Quoted 205 lines
---
Subject: lockdep: Optimize the memory usage of circular queue
From: Boqun Feng <[email protected]>
Date: Thu, 17 Sep 2020 16:01:50 +0800From: Boqun Feng <[email protected]>
Qian Cai reported a
BFS_EQUEUEFULLwarning [1] after read recursive deadlock detection merged into tip tree recently. Unlike the previous lockep graph searching, which iterate every lock class (every node in the graph) exactly once, the graph searching for read recurisve deadlock detection needs to iterate every lock dependency (every edge in the graph) once, as a result, the maximum memory cost of the circular queue changes from O(V), where V is the number of lock classes (nodes or vertices) in the graph, to O(E), where E is the number of lock dependencies (edges), because every lock class or dependency gets enqueued once in the BFS. Therefore we hit theBFS_EQUEUEFULLcase.However, actually we don't need to enqueue all dependencies for the BFS, because every time we enqueue a dependency, we almostly enqueue all other dependencies in the same dependency list ("almostly" is because we currently check before enqueue, so if a dependency doesn't pass the check stage we won't enqueue it, however, we can always do in reverse ordering), based on this, we can only enqueue the first dependency from a dependency list and every time we want to fetch a new dependency to work, we can either:
1) fetch the dependency next to the current dependency in the
dependency list
or2) if the dependency in 1) doesn't exist, fetch the dependency from
the queue.With this approach, the "max bfs queue depth" for a
x86_64_defconfig+ lockdep and selftest config kernel can get descreased from:max bfs queue depth: 201
to (after apply this patch)
max bfs queue depth: 61
While I'm at it, clean up the code logic a little (e.g. directly return other than set a "ret" value and goto the "exit" label).
[1]: https://lore.kernel.org/lkml/[email protected]/
Reported-by Qian Cai <[email protected]>Reported-by [email protected]Signed-off-by Boqun Feng <[email protected]>Signed-off-by Peter Zijlstra (Intel) <[email protected]>--- kernel/locking/lockdep.c | 101 ++++++++++++++++++++++++++++------------------- 1 file changed, 61 insertions(+), 40 deletions(-)kernel/locking/lockdep.c +61
-40@@ -1606,6 +1606,15 @@ static inline void bfs_init_rootb(struct lock->only_xr = (hlock->read !=0 ); } +static inline struct lock_list *__bfs_next (struct lock_list *lock,int offset) +{ +if (!lock || !lock->parent) +return NULL ; + +return list_next_or_null_rcu (get_dep_list (lock->parent, offset), + &lock->entry, struct lock_list, entry); +} +/* * Breadth-First Search to find a strong path in the dependency graph. * @@ -1639,36 +1648,25 @@ static enum bfs_result __bfs(struct lock struct lock_list **target_entry, int offset) { +struct circular_queue *cq = &lock_cq; +struct lock_list *lock =NULL ;struct lock_list *entry; -struct lock_list *lock;struct list_head *head; -struct circular_queue *cq = &lock_cq; -enum bfs_result ret =BFS_RNOMATCH ; +unsigned int cq_depth; +bool first;lockdep_assert_locked (); -if (match (source_entry, data)) { - *target_entry = source_entry; - ret =BFS_RMATCH ; - goto exit; - } - - head =get_dep_list (source_entry, offset); -if (list_empty (head)) - goto exit; -__cq_init (cq);__cq_enqueue (cq, source_entry); -while ((lock =__cq_dequeue (cq))) { -bool prev_only_xr; - -if (!lock->class) { - ret =BFS_EINVALIDNODE ; - goto exit; - } +while ((lock =__bfs_next (lock, offset)) || (lock =__cq_dequeue (cq))) { +if (!lock->class) +return BFS_EINVALIDNODE ;/* +* Step 1: check whether we already finish on this one. +* * If we have visited all the dependencies from this @lock to * others (iow, if we have visited all lock_list entries in * @lock->class->locks_{after,before}) we skip, otherwise go @@ -1680,13 +1678,13 @@ static enum bfs_result __bfs(struct lockelse mark_lock_accessed (lock); - head =get_dep_list (lock, offset); - - prev_only_xr = lock->only_xr; - -list_for_each_entry_rcu (entry, head, entry) { -unsigned int cq_depth; -u8 dep = entry->dep; +/* +* Step 2: check whether prev dependency and this form a strong +* dependency path. +*/ +if (lock->parent) {/* Parent exists, check prev dependency */ +u8 dep = lock->dep; +bool prev_only_xr = lock->parent->only_xr;/* * Mask out all -(S*)-> if we only have *R in previous @@ -1701,26 +1699,49 @@ static enum bfs_result __bfs(struct lockcontinue ;/* If there are only -(*R)-> left, set that for the next step */ - entry->only_xr = !(dep & (DEP_SN_MASK |DEP_EN_MASK )); + lock->only_xr = !(dep & (DEP_SN_MASK |DEP_EN_MASK )); + } + +/* +* Step 3: we haven't visited this and there is a strong +* dependency path to this, so check with @match. +*/ +if (match (lock, data)) { + *target_entry = lock; +return BFS_RMATCH ; + } +/* +* Step 4: if not match, expand the path by adding the +* afterwards or backwards dependencis in the search +* +*/ + first = true; + head =get_dep_list (lock, offset); +list_for_each_entry_rcu (entry, head, entry) {visit_lock_entry (entry, lock); -if (match (entry, data)) { - *target_entry = entry; - ret =BFS_RMATCH ; - goto exit; - } - -if (__cq_enqueue (cq, entry)) { - ret =BFS_EQUEUEFULL ; - goto exit; - } + +/* +* Note we only enqueue the first of the list into the +* queue, because we can always find a sibling +* dependency from one (see _bfs_next()), as a result +* the space of queue is saved. +*/ +if (!first) +continue ; + + first = false; + +if (__cq_enqueue (cq, entry)) +return BFS_EQUEUEFULL ; + cq_depth =__cq_get_elem_count (cq);if (max_bfs_queue_depth < cq_depth) max_bfs_queue_depth = cq_depth; } } -exit: -return ret; + +return BFS_RNOMATCH ; } static inline enum bfs_result
Peter Zijlstra
maintainerQuoted 3 lines · Boqun Feng
I think your version is better and should be functionally identical to mine, also FWIW, I tested with a lockdep boot selftests, everything worked fine.
Excellent, thanks! I'll go feed it to the robots.
The following commit has been merged into the locking/core branch of tip:
The following commit has been merged into the locking/core branch of tip:
Commit-ID: 6d1823ccc480866e571ab1206665d693aeb600cf Gitweb: https://git.kernel.org/tip/6d1823ccc480866e571ab1206665d693aeb600cf Author: Boqun Feng <[email protected]> AuthorDate: Thu, 17 Sep 2020 16:01:50 +08:00 Committer: Peter Zijlstra <[email protected]> CommitterDate: Tue, 29 Sep 2020 09:56:59 +02:00
lockdep: Optimize the memory usage of circular queue
Qian Cai reported a BFS_EQUEUEFULL warning [1] after read recursive deadlock detection merged into tip tree recently. Unlike the previous lockep graph searching, which iterate every lock class (every node in the graph) exactly once, the graph searching for read recurisve deadlock detection needs to iterate every lock dependency (every edge in the graph) once, as a result, the maximum memory cost of the circular queue changes from O(V), where V is the number of lock classes (nodes or vertices) in the graph, to O(E), where E is the number of lock dependencies (edges), because every lock class or dependency gets enqueued once in the BFS. Therefore we hit the BFS_EQUEUEFULL case.
However, actually we don't need to enqueue all dependencies for the BFS, because every time we enqueue a dependency, we almostly enqueue all other dependencies in the same dependency list ("almostly" is because we currently check before enqueue, so if a dependency doesn't pass the check stage we won't enqueue it, however, we can always do in reverse ordering), based on this, we can only enqueue the first dependency from a dependency list and every time we want to fetch a new dependency to work, we can either:
1) fetch the dependency next to the current dependency in the
dependency list
or
2) if the dependency in 1) doesn't exist, fetch the dependency from
the queue.
With this approach, the "max bfs queue depth" for a x86_64_defconfig + lockdep and selftest config kernel can get descreased from:
max bfs queue depth: 201
to (after apply this patch)
max bfs queue depth: 61
While I'm at it, clean up the code logic a little (e.g. directly return other than set a "ret" value and goto the "exit" label).
[1]: https://lore.kernel.org/lkml/[email protected]/
--- kernel/locking/lockdep.c | 99 +++++++++++++++++++++++--------------- 1 file changed, 60 insertions(+), 39 deletions(-)
kernel/locking/lockdep.c +60 -39
@@ -1606,6 +1606,15 @@ static inline void bfs_init_rootb(struct lock_list *lock, lock->only_xr = (hlock->read !=0 ); } +static inline struct lock_list *__bfs_next (struct lock_list *lock,int offset) +{ +if (!lock || !lock->parent) +return NULL ; + +return list_next_or_null_rcu (get_dep_list (lock->parent, offset), + &lock->entry, struct lock_list, entry); +} +/* * Breadth-First Search to find a strong path in the dependency graph. *
@@ -1639,36 +1648,25 @@ static enum bfs_result __bfs(struct lock_list *source_entry, struct lock_list **target_entry, int offset) { +struct circular_queue *cq = &lock_cq; +struct lock_list *lock =NULL ;struct lock_list *entry; -struct lock_list *lock;struct list_head *head; -struct circular_queue *cq = &lock_cq; -enum bfs_result ret =BFS_RNOMATCH ; +unsigned int cq_depth; +bool first;lockdep_assert_locked (); -if (match (source_entry, data)) { - *target_entry = source_entry; - ret =BFS_RMATCH ; - goto exit; - } - - head =get_dep_list (source_entry, offset); -if (list_empty (head)) - goto exit; -__cq_init (cq);__cq_enqueue (cq, source_entry); -while ((lock =__cq_dequeue (cq))) { -bool prev_only_xr; - -if (!lock->class) { - ret =BFS_EINVALIDNODE ; - goto exit; - } +while ((lock =__bfs_next (lock, offset)) || (lock =__cq_dequeue (cq))) { +if (!lock->class) +return BFS_EINVALIDNODE ;/* +* Step 1: check whether we already finish on this one. +* * If we have visited all the dependencies from this @lock to * others (iow, if we have visited all lock_list entries in * @lock->class->locks_{after,before}) we skip, otherwise go
@@ -1680,13 +1678,13 @@ static enum bfs_result __bfs(struct lock_list *source_entry,else mark_lock_accessed (lock); - head =get_dep_list (lock, offset); - - prev_only_xr = lock->only_xr; - -list_for_each_entry_rcu (entry, head, entry) { -unsigned int cq_depth; -u8 dep = entry->dep; +/* +* Step 2: check whether prev dependency and this form a strong +* dependency path. +*/ +if (lock->parent) {/* Parent exists, check prev dependency */ +u8 dep = lock->dep; +bool prev_only_xr = lock->parent->only_xr;/* * Mask out all -(S*)-> if we only have *R in previous
@@ -1701,26 +1699,49 @@ static enum bfs_result __bfs(struct lock_list *source_entry,continue ;/* If there are only -(*R)-> left, set that for the next step */ - entry->only_xr = !(dep & (DEP_SN_MASK |DEP_EN_MASK )); + lock->only_xr = !(dep & (DEP_SN_MASK |DEP_EN_MASK )); + } +/* +* Step 3: we haven't visited this and there is a strong +* dependency path to this, so check with @match. +*/ +if (match (lock, data)) { + *target_entry = lock; +return BFS_RMATCH ; + } + +/* +* Step 4: if not match, expand the path by adding the +* forward or backwards dependencis in the search +* +*/ + first = true; + head =get_dep_list (lock, offset); +list_for_each_entry_rcu (entry, head, entry) {visit_lock_entry (entry, lock); -if (match (entry, data)) { - *target_entry = entry; - ret =BFS_RMATCH ; - goto exit; - } -if (__cq_enqueue (cq, entry)) { - ret =BFS_EQUEUEFULL ; - goto exit; - } +/* +* Note we only enqueue the first of the list into the +* queue, because we can always find a sibling +* dependency from one (see __bfs_next()), as a result +* the space of queue is saved. +*/ +if (!first) +continue ; + + first = false; + +if (__cq_enqueue (cq, entry)) +return BFS_EQUEUEFULL ; + cq_depth =__cq_get_elem_count (cq);if (max_bfs_queue_depth < cq_depth) max_bfs_queue_depth = cq_depth; } } -exit: -return ret; + +return BFS_RNOMATCH ; } static inline enum bfs_result