Re: fine grained locking and traversing linked lists

On Fri, Sep 03, 2004 at 12:38:18PM -0700, Maksim Yevmenkin wrote:
> Brooks Davis wrote:
> >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.
> 
> well, again i'm using bluetooth sockets code as an example. there is a 
> linked list of all PCB. each PCB has its own lock. so, when i need to 
> locate PCB by any field i do
> 
> lock(list);
> list_foreach(pcb, ...) {
>   lock(pcb);
>   if (compare(key)) {
>     unlock(pcb);
>     unlock(list);
>     return (pcb);
>   }
>   unlock(pcb);
> }
> unlock(list);
> return (NULL);
> 
> in sockets layer some functions (i.e. bind, connect, control etc.) can 
> change PCB fields without holding sockets list lock.
> 
> so, in some cases i want: lock(list), lock(pcb) and in other cases i 
> want lock(pcb), lock(list).

I guess my question was, do you really need to hold the pcb lock to
do the compare.  It doesn't matter if other fields change if the key
can not.  I don't know the code in question well enough do answer that
question.

The key thing is that just because a object has a lock, it does not
follow that the lock must be held to touch the object.  You just need to
be sure the object can't be deleted.  If you have refcounted objects,
the list holds a refrence so if you hold the list lock, you are safe.

> >>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.
> 
> yes, the head is still the issue. but i think it can be avoided. i think 
> it only has to be protected when head changes from NULL -> non NULL and 
> vice versa. otherwise its just lock(head).
>
> i do not think that scanning backwards and forwards at the same time is 
> an issue. it is a (serious?) limitation i agree. but it is possible to 
> scan list forward staring from any point.

If you implement this, I strongly recommend making the lists singally
linked to avoid the possiablity of this 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