1. 07 Oct, 2020 1 commit
  2. 29 Sep, 2020 1 commit
    • Boqun Feng's avatar
      lockdep: Optimize the memory usage of circular queue · 6d1823cc
      Boqun Feng authored
      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/17343f6f7f2438fc376125384133c5ba70c2a681.camel@redhat.com/Reported-by: default avatarQian Cai <cai@redhat.com>
      Reported-by: syzbot+62ebe501c1ce9a91f68c@syzkaller.appspotmail.com
      Signed-off-by: default avatarBoqun Feng <boqun.feng@gmail.com>
      Signed-off-by: default avatarPeter Zijlstra (Intel) <peterz@infradead.org>
      Link: https://lkml.kernel.org/r/20200917080210.108095-1-boqun.feng@gmail.com
      6d1823cc
  3. 16 Sep, 2020 1 commit
  4. 10 Sep, 2020 13 commits
  5. 26 Aug, 2020 24 commits