Re: fine grained locking and traversing linked lists

On Fri, Sep 03, 2004 at 11:57:17AM -0700, Maksim Yevmenkin wrote:
> Dear Hackers,
> 
> recent Robert Watson's locking changes made me to revisit locking in
> the bluetooth code. bluetooth code uses linked lists for various
> objects. quite often it is required to locate a certain object in the
> list. during this operation i have to hold list mutex and individual
> object mutex. this is very inconvenient.

Why do you have to hold the object mutex?  I can think of scenerios
where that is required, but usually it isn't since they key is fixed at
the time the item is inserted in to the list, or is at least protected
by the list mutex.  For an example of a key protected by the list
mutex, consider struct ifnet's if_xname member relative to ifunit() and
renaming.

> so, i've written a "spherical cow" that shows fine grained locking
> when traversing linked lists (see below). basically, for double linked
> list, in order to safely manipulate by object "y" one must hold three
> locks: object "y" lock, object "x = y->previous" lock and object "z =
> y->next" lock.
> 
> so, the $1 million question is: am i missing something? or this will work?

How do you protect the head in this case?  The list mutex would normally
do so, but if the head can change, you'll need a mutex to protect it
(using an array hid this issue).  Also, doubly linked lists won't work
without a lot of effort (read pain :-) because scanning backwards and
forwards at the same time will lead to deadlock.

-- Brooks

-- 
Any statement of the form "X is the one, true Y" is FALSE.
PGP fingerprint 655D 519C 26A7 82E7 2529  9BF0 5D8E 8BE9 F238 1AD4