[Skiboot] [PATCH] core/lock: Add deadlock detection

[Alistair Popple]

On Fri, 23 Jun 2017 06:24:12 PM Nicholas Piggin wrote:
> On Fri, 23 Jun 2017 17:14:34 +1000
> Oliver <oohall at gmail.com> wrote:
> 
> > Hey nick, you're a concurrency wizard can you review this?
> 
> I could try.
> 
> > On Fri, Jun 23, 2017 at 2:35 PM, Matt Brown <matthew.brown.dev at gmail.com> wrote:
> > > This adds simple deadlock detection.
> > > The detection looks for circular dependencies in the lock requests.
> > > It will abort and display a stack trace when a deadlock occurs.
> > > The detection will reduce performance so only use for debugging.
> > > To use, enable DEBUG_DEADLOCKS in include/config.h (disabled by default).  
> > 
> > It might be useful if we can get stack traces for every thread
> > involved in the deadlock. You might be able
> > to use the NMI injection that nick was working on to wake up
> > individual threads to get them to print the stack
> > trace.
> 
> Would probably be a good idea. We'll have to somehow bribe or
> Alistair to do the NMI injection firmware though :)

Bribes are welcome but not necessary :-)

It's on my list of things to come back to.

- Alistair

> > > Signed-off-by: Matt Brown <matthew.brown.dev at gmail.com>
> > > ---
> > >  core/lock.c      | 83 +++++++++++++++++++++++++++++++++++++++++++++++++++++++-
> > >  include/config.h |  3 ++
> > >  include/lock.h   |  5 ++++
> > >  3 files changed, 90 insertions(+), 1 deletion(-)
> 
> Hmm, okay so the algorithm is follows, if a CPU can't get a lock
> immediately, it registers that it is waiting for the lock in
> lock_table, and then checks if the lock owner of that lock is waiting
> for another lock, etc. and if it reaches back to us it's a deadlock.
> 
> Seems like a reasonable algorithm.
> 
> I think the deadlock detection algorithm itself needs to be
> protected from concurrency. You could have a lock owner release
> its lock and later try to grab the one you hold while the check
> is running, I think?
> 
> An issue with this type of detection is that it doesn't catch a lot
> in testing. I mean only actual deadlocks. Probably better than
> nothing, but what would be really cool is to dynamically build the
> observed relationship between locks (aka lockdep aka witness).
> Then you can complain if you have ever seen locks being taken in
> the wrong order.
> 
> But I don't want to say "don't do this because we can spend a lot
> more time and work to do something else" :) This could make a good
> start for lock debugging. A basic timeout warning for acquiring a
> lock wouldn't be a bad idea either (and may catch some different
> bugs).
> 
> Thanks,
> Nick
>