witness performance improvements

[John Baldwin]

On Friday 18 July 2008 10:41:58 pm Jeff Roberson wrote:
> Hello,
> 
> I have a patch that improves witness performance available at:
> 
> http://people.freebsd.org/~jeff/witness.diff
> 
> This improvement comes at the cost of some significant space overhead.  It 
> changes the witness graph from a linked tree to a matrix based approach. 
> Relationships can be quickly resolved with a table lookup.  The table size 
> is WITNESS_COUNT^2, or 1MB with the current count of 1024.

Woo!  Thanks for polishing this.

> This patch also makes struct witness objects persistent even after the 
> last lock using this name has been removed.  This is helpful for short 
> lived objects which may be created frequently.

Originally, the idea was that if one had a LOR bug in a driver, one could 
kldunload the driver and have WITNESS forget about any orders for the 
driver's lock, fix the bug, and try again, but the short-lived names problem 
is much more common in practice, and trying to remove info about a specific 
lock class from the graph is a bit tenuous, so I think this is the better 
approach going forward.

> To reduce lock contention on SMP witness_checkorder() now runs without the 
> w_mtx when there are no lock violations.  I also cache a lock_list_entry 
> in each thread as allocating these requires the w_mtx.  The entry is 
> disposed of at thread_exit().

Neat.

> I'm mostly interested in hearing what people have to say about the space 
> bloat.  I believe it is in a commit ready state.

I think the space usage is perfectly fine.  Also, now that you malloc the 
actual witness objects instead of putting them in the BSS (something that 
should have been done anyway I think), I would make the number of witness 
objects a loader tunable.

-- 
John Baldwin