Re: fine grained locking and traversing linked lists

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

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

thanks,
max