cvs commit: src/sys/kern subr_witness.c

[John Baldwin]

On Monday 29 August 2005 01:10 pm, Don Lewis wrote:
> On 29 Aug, John Baldwin wrote:
> > On Wednesday 24 August 2005 11:47 pm, Don Lewis wrote:
> >> truckman    2005-08-25 03:47:37 UTC
> >>
> >>   FreeBSD src repository
> >>
> >>   Modified files:
> >>     sys/kern             subr_witness.c
> >>   Log:
> >>   Track all lock relationships instead of pruning direct relationships
> >>   if an indirect relationship exists (keep both A->B->C and A->C).
> >>   This allows witness_checkorder() to use isitmychild() instead of
> >>   the much more expensive isitmydescendant() to check for valid lock
> >>   ordering.
> >>
> >>   Don't do an expensive tree walk to update the w_level values when
> >>   the tree is updated.  Only update the w_level values when using the
> >>   debugger to display the tree.
> >>
> >>   Nuke the experimental "witness_watch > 1" mode that only compared
> >>   w_level for the two locks.  This information is no longer maintained
> >>   at run time, and the use of isitmychild() in witness_checkorder
> >>   should bring performance close enough to the acceptable level that
> >>   this hack is not needed.
> >>
> >>   Report witness data structure allocation statistics under the
> >>   debug.witness sysctl.
> >>
> >>   Reviewed by:    jhb
> >>   MFC after:      30 days
> >>
> >>   Revision  Changes    Path
> >>   1.198     +31 -71    src/sys/kern/subr_witness.c
> >
> > I didn't think of this until now, but I think this breaks indirect lock
> > order relationships that aren't explicit.  That is, suppose at some point
> > the following lock order pairs are recorded:
> >
> > A -> B
> > C -> D
>
> Ok ...

That should have been B -> C rather than C -> D.

> > That will give you a tree structure of something like:
> >
> > A --> B --> C
>
> You lost me here.  How did this transformation happen?
>
> > If you then do C -> A, since C isn't a direct descendant of A, witness
> > won't catch it anymore.  So, you might need to back this out until a
> > solution to this problem is solved.
>
> No, C -> A should still be caught.  We first check for known direct
> relationships by calling isitmychild(C, A), which will return 0, and
> then start checking for reversals.  In the loop, we will call
> isitmydescendent(A, C), which will find the A -> B -> C relationship,
> return 1, and cause witness_checkorder() to fall through to the "lock
> order reversal" message.

Ah, I thought you only checked the direct children since the log message said:

  This allows witness_checkorder() to use isitmychild() instead of
  the much more expensive isitmydescendant() to check for valid lock
  ordering.

> The entire tree is still checked for reversals.  The optimization is to
> only check for direct relationships when validating that the lock is
> being grabbed in the direct order, so if anything, witness_checkorder()
> should fall through into the lock order reversal checking code more
> frequently.

Yeah, I see that now, sorry for the noise.

-- 
John Baldwin <jhb at FreeBSD.org>  <><  http://www.FreeBSD.org/~jhb/
"Power Users Use the Power to Serve"  =  http://www.FreeBSD.org