Re: [CHECKER] a couple potential deadlocks in 2.4.5-ac8

[Alexander Viro]

On Sat, 9 Jun 2001, Dawson Engler wrote:

> Hi All,
> 
> we're starting to develop a checker that finds deadlocks by (1)
> computing all lock acquisition paths and (2) checking if two paths
> violate a partial order.
> 
> E.g., for two threads T1 and T2:
> 	T1: foo acquires A --> calls bar which tries to acquire B
> 	T2: baz acquires B --> calls blah which tries to acquire A
> all else being equal, this deadlocks.
> 
> The checker is pretty primitive.  In particular:
> 	- lots of false negatives come from the fact that it does not 
> 	  track interrupt disabling.  A missed deadlock:
> 		foo acquires A
> 		bar interrupts foo, disables interrupts, tries to acquire A
> 	  (Is this the most common deadlock?)
> 
> 	- many potential false positives since it does not realize when
> 	two kernel call traces are mutually exclusive.
> 
> To check it's mechanics I've enclosed what look to me to be two potential
> deadlocks --- given the limits of the tool and my understanding of what
> can happen when, these could be (likely be?) false positive, so I'd
> appreciate any corrective feedback.

BKL is special. It has no nesting constraints wrt. semaphores. It is
a spinlock, but we are allowed to block while holding it - then it will
be released and the next time we get a timeslice we will start with
attempt to reacquire it.