Linux lockdep

BUG: Invalid wait context

raw_spin_lock(&foo);
spin_lock(&bar);
spin_unlock(&bar);
raw_spin_unlock(&foo);

[   15.090335][    T1]
[   15.090359][    T1] =============================
[   15.090365][    T1] [ BUG: Invalid wait context ]
[   15.090373][    T1] 5.10.59-rt52-00983-g186a6841c682-dirty #3 Not tainted
[   15.090386][    T1] -----------------------------
[   15.090392][    T1] swapper/0/1 is trying to lock:
[   15.090402][    T1] 70ff00018507c188 (&gc->bgpio_lock){....}-{3:3}, at: _raw_spin_lock_irqsave+0x1c/0x28
[   15.090470][    T1] other info that might help us debug this:
[   15.090477][    T1] context-{5:5}
[   15.090485][    T1] 3 locks held by swapper/0/1:
[   15.090497][    T1]  #0: c2ff0001816de1a0 (&dev->mutex){....}-{4:4}, at: __device_driver_lock+0x98/0x104
[   15.090553][    T1]  #1: ffff90001485b4b8 (irq_domain_mutex){+.+.}-{4:4}, at: irq_domain_associate+0xbc/0x6d4
[   15.090606][    T1]  #2: 4bff000185d7a8e0 (lock_class){....}-{2:2}, at: _raw_spin_lock_irqsave+0x1c/0x28
[   15.090654][    T1] stack backtrace:
[   15.090661][    T1] CPU: 4 PID: 1 Comm: swapper/0 Not tainted 5.10.59-rt52-00983-g186a6841c682-dirty #3
[   15.090682][    T1] Hardware name: Horizon Robotics Journey 5 DVB (DT)
[   15.090692][    T1] Call trace:
[   15.090698][    T1]  dump_backtrace+0x0/0x708
[   15.090717][    T1]  show_stack+0x24/0x30
[   15.090733][    T1]  dump_stack+0x1b4/0x2bc
[   15.090752][    T1]  __lock_acquire+0x2800/0xb760
[   15.090774][    T1]  lock_acquire+0x248/0x85c
[   15.090793][    T1]  __raw_spin_lock_irqsave+0xd4/0x270
[   15.090811][    T1]  _raw_spin_lock_irqsave+0x1c/0x28
[   15.090828][    T1]  dwapb_irq_ack+0xb4/0x300
[   15.090846][    T1]  __irq_do_set_handler+0x494/0xb2c
[   15.090864][    T1]  __irq_set_handler+0x74/0x114
[   15.090881][    T1]  irq_set_chip_and_handler_name+0x44/0x58
[   15.090900][    T1]  gpiochip_irq_map+0x210/0x644
[   15.090917][    T1]  irq_domain_associate+0x168/0x6d4
[   15.090935][    T1]  irq_create_mapping_affinity+0x15c/0x354
[   15.090955][    T1]  gpiochip_to_irq+0xb4/0x390
[   15.090970][    T1]  gpiod_to_irq+0xf8/0x1e4
[   15.090987][    T1]  gpio_keys_probe+0x9a0/0x24d0
[   15.091008][    T1]  platform_drv_probe+0x138/0x214
[   15.091026][    T1]  really_probe+0x2e0/0x15d4
[   15.091045][    T1]  driver_probe_device+0x100/0x418
[   15.091064][    T1]  device_driver_attach+0x138/0x234
[   15.091084][    T1]  __driver_attach+0x184/0x358
[   15.091103][    T1]  bus_for_each_dev+0x100/0x1e0
[   15.091122][    T1]  driver_attach+0x5c/0x98
[   15.091141][    T1]  bus_add_driver+0x33c/0x9d8
[   15.091159][    T1]  driver_register+0x1e4/0x6b0
[   15.091179][    T1]  __platform_driver_register+0x118/0x214
[   15.091196][    T1]  gpio_keys_init+0x28/0x34
[   15.091218][    T1]  do_one_initcall+0x8c/0x2d8
[   15.091236][    T1]  do_initcall_level+0x144/0x230
[   15.091257][    T1]  do_initcalls+0xb0/0x170
[   15.091275][    T1]  do_basic_setup+0xd0/0xe4
[   15.091293][    T1]  kernel_init_freeable+0x180/0x3e4
[   15.091311][    T1]  kernel_init+0x2c/0x398
[   15.091330][    T1]  ret_from_fork+0x10/0x30

WARNING: bad contention detected!

WARNING: possible circular locking dependency detected

WARNING: possible recursive locking detected

WARNING: bad unlock balance detected

WARNING: suspicious RCU usage

WARNING: lock held when returning to user space!

WARNING: %s/%d still has locks held!

WARNING: held lock freed!

WARNING: Nested lock was not taken

WARNING: possible irq lock inversion dependency detected

[  108.223030]        CPU0                    CPU1
[  108.223030]        ----                    ----
[  108.223030]   lock(&(&list->lock)->rlock#2);
[  108.223030]                                local_irq_disable();
[  108.223030]                                lock(policy_rwlock);
[  108.223030]                                lock(&(&list->lock)->rlock#2);
[  108.223030]   <Interrupt>
[  108.223030]     lock(policy_rwlock);

WARNING: inconsistent lock state

[  313.402947]        CPU0
[  313.402948]        ----
[  313.402949]   lock(&(&wsm.lock)->rlock);
[  313.402951]   <Interrupt>
[  313.402952]     lock(&(&wsm.lock)->rlock);
[  313.402954]
*** DEADLOCK ***

WARNING: chain_key collision

WARNING: %s-safe -> %s-unsafe lock order detected

RSLS Call Trace

Mutex lock

上下文判断

enum lockdep_wait_type {
    LD_WAIT_INV = 0,    /* not checked, catch all */

    LD_WAIT_FREE,               /* wait free, rcu etc.. */
    LD_WAIT_SPIN,               /* spin loops, raw_spinlock_t etc.. */

#ifdef CONFIG_PROVE_RAW_LOCK_NESTING
    LD_WAIT_CONFIG,             /* preemptible in PREEMPT_RT, spinlock_t etc.. */
#else
    LD_WAIT_CONFIG = LD_WAIT_SPIN,
#endif
    LD_WAIT_SLEEP,              /* sleeping locks, mutex_t etc.. */

    LD_WAIT_MAX,                /* must be last */
};

锁依赖

• lock type
  

  因为不同性质的锁阻塞的条件不同，所以内核根据阻塞产生条件，给内核中的锁分为了以下的几大类.lockdep将锁分为以下几种类型
  

  writers

  exclusive lockers, like spin_lock() or write_lock()
  此种锁是内核编程中最常用的类型，完全独占的锁，同一时间只会有一个owner，最容易分析
  

  non-recursive readers

  shared lockers, like down_read()
  此种锁是普通的读锁，因为读锁可以同时被读端锁持有，因此允许多线程同时持有，有相互依赖的持有关系也不一定会死锁
  

  recursive readers

  recursive shared lockers, like rcu_read_lock()
  这种锁是更不易死锁的类型，由于支持重入，具有更佳宽松个的死锁条件
  

  并且为了方便文章编写，做出缩写如下
  

  abbr	type
  W/E	exclusive lockers
  r	non-recursive readers
  R	recursive readers
  S	all readers (non-recursive + recursive), as both are shared lockers.
  N	writers and non-recursive readers, as both are not recursive.

• non-recursive readers的死锁情形
  

  为了方便理解，通过下面的例子，可以看出重入属性对死锁的产生的影响
  这个例子展示了non-recursive readers被writer的waiter阻塞导致出现deadlock的情形
  虽然read_lock可以同时被多个cpu/单个cpu持有，但是如果有线程在等待write锁, 系统依旧会因此而阻塞
  

  TASK A: TASK B:
  
  read_lock(X);
                      write_lock(X);
  read_lock_2(X);
  

  简而言之就是锁X在第二次获取读锁时，会因为另一个task在等待获取写锁而导致死
  锁。这是因为写锁会block之后尝试获取读锁的操作，如果没有这个block操作，系统
  可能会因为一致有进程不断获取读锁，而导致，写入的进程无法拿到锁，造成饿死.
  

  具体可以参考 read_lock will wait for write waiter
  

  void queued_read_lock_slowpath(struct qrwlock *lock)
  {
      /*
       * Readers come here when they cannot get the lock without waiting
       */
      if (unlikely(in_interrupt())) {
          /*
           * Readers in interrupt context will get the lock immediately
           * if the writer is just waiting (not holding the lock yet),
           * so spin with ACQUIRE semantics until the lock is available
           * without waiting in the queue.
           */
          atomic_cond_read_acquire(&lock->cnts, !(VAL & _QW_LOCKED));
          return;
      }
      atomic_sub(_QR_BIAS, &lock->cnts);
  
      /*
       * Put the reader into the wait queue
       */
      arch_spin_lock(&lock->wait_lock);
      atomic_add(_QR_BIAS, &lock->cnts);
  
      /*
       * The ACQUIRE semantics of the following spinning code ensure
       * that accesses can't leak upwards out of our subsequent critical
       * section in the case that the lock is currently held for write.
       */
      atomic_cond_read_acquire(&lock->cnts, !(VAL & _QW_LOCKED));
  
      /*
       * Signal the next one in queue to become queue head
       */
      arch_spin_unlock(&lock->wait_lock);
  }
  EXPORT_SYMBOL(queued_read_lock_slowpath);
  

  如上面的内核实现，读锁会block在arch_spin_lock(&lock->wait_lock);或者 atomic_cond_read_acquire(&lock->cnts, !(VAL & _QW_LOCKED));，在此处等待写锁离开临界区，单此时，读写被Task A拿到，导致死锁.
  

• 根据锁类型，来观察死锁的条件关系
  

  针对这三种锁类型，可以有如下几种的阻塞关系矩阵. Y表示行标会阻塞列标, N表示不会产生阻塞的问题
  
  

  上面列出了不同类型的锁在相互依赖时是否会产生block，N表示完全不会形成阻塞等待
  下面简单列举两个不会产生阻塞的路径
  

  • R won't block r. 递归的读锁不会阻塞非递归的读锁
    
  • R won't block R. 递归的读锁不会相互block
    
• 依赖分析
  

  通过上面的表格，在检测死锁时，共需要检测9种情况
  

  考虑如下的依赖情况
  L1 -> L2
  我们需要关心在获取L1的情况下，再去获取L2系统会不会被block. 换句话说就是有没有可能存在L3，L3依赖于L1，而L2依赖于L3.
  这样我们只需要检测一下获取L1之前获取过的锁列表, 以及获取L2之后获取过的锁列表，再综合锁的类型进行考虑就可以检测出来死锁。
  

  综合上面的阻塞关系图，具有如下规律
  
  根据这个规律，可以方便的将关系简化为4种，这样，就可以大大降低复杂度.
  lockdep会动态生成一张依赖图，系统将对应的lockclass添加到这张图中，通过对应的算法照出相应的依赖关系.
  依赖类型
  针对不同的锁类型，可以抽象出以下四中依赖关系, 按照上面的阻塞关系图。
  

  • -(ER)->
    exclusive writer to recursive reader dependency
    
  • -(EN)->
    exclusive writer to non-recursive locker dependency
    
  • -(SR)->
    shared reader to recursive reader dependency
    
  • -(SN)->
    shared reader to non-recursive locker dependency
    
• strong path定义
  

  根据阻塞图，如果一条依赖路径上全部都是可阻塞的类型，则定义为strong path
  简单来说就是不经过-(R)-> -(S)->路径的定义为strong path. 因为经过这种路径的都有非block的锁关系，lockdep认为不会造成死锁.
  下面是内核文档中对strong path定义的原文
  

  A "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.
  

• 死锁关系证明
  
  • 定理1
    如果一条路径上有闭环的strong path，那么这个就会构成死锁.
    

  • 定理2
    如果一条路径上没有闭环的strong path，那么一定不会构成死锁.
    

    在这两个定理的前提下，可以很容易得出，闭环的strong path是死锁的充分必要条件. 上面两条定理的证明在内核文档中有详细的描述。在此不再赘述.
    

    所以在lockdep的检测中，只需要找出持锁路径上是否有闭环的strong path就可以了.
    

• 代码实现
  

  source to call check_noncircular
  通过代码注释可以看到，内核通过广度优先的遍历方式，寻找是否会形成依赖环路, 在找到对应的环路之后，再经过对闭环strong path的判断来验证是否存在死锁.
  检测是否存在闭环的strong path
  

  /*
   * We are about to add B -> A into the dependency graph, and in __bfs() a
   * strong dependency path A -> .. -> B is found: hlock_class equals
   * entry->class.
   *
   * We will have a deadlock case (conflict) if A -> .. -> B -> A is a strong
   * dependency cycle, that means:
   *
   * Either
   *
   *     a) B -> A is -(E*)->
   *
   * or
   *
   *     b) A -> .. -> B is -(*N)-> (i.e. A -> .. -(*N)-> B)
   *
   * as then we don't have -(*R)-> -(S*)-> in the cycle.
   */
  static inline bool hlock_conflict(struct lock_list *entry, void *data)
  {
      struct held_lock *hlock = (struct held_lock *)data;
  
      return hlock_class(hlock) == entry->class && /* Found A -> .. -> B */
          (hlock->read == 0 || /* B -> A is -(E*)-> */
              !entry->only_xr); /* A -> .. -> B is -(*N)-> */
  }
  

  如上面的注释，判断几个东西
  

  hlock_class(hlock) == entry->class

  A -> B 这个锁和即将获取的锁形成了依赖关系
  以前有依赖关系 A -> B, 再尝试通过B -> A的顺序拿锁是会造成这个条件成立
  

  hlock->read == 0

  B -(E*)-> A 这个情况满足闭环strong path的条件
  

  !entry->only_xr

  A -> .. -> B is -(*N)-> (i.e. A -> .. -(*N)-> B)
  如果这几个条件成立，则认为满足了闭环strong path的充要条件.