cvs commit: src/sys/kern subr_witness.c

[Don Lewis]

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

> What you changed is the situation where one does A -> B and A -> C first, 
> establishing a tree like this:
> 
> A --> B
>   \-> C
> 
> And then does B -> C.  The old code moved C under B:
> 
> A --> B --> C
> 
> and would still catch C -> A because it checked the full tree.
> 
> With your changes you would end up with:
> 
> A --> B --> C
>   \-> C
> 
> Which is fine except that it only catches reversals of explicit reversals, it 
> doesn't actually handle any indirect lock orders as in my first scenario 
> above.  Sorry I didn't think of this until now when you asked for my review 
> earlier.

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.