Re: fine grained locking and traversing linked lists

Brooks Davis wrote:
> On Fri, Sep 03, 2004 at 12:38:18PM -0700, Maksim Yevmenkin wrote:
>>>>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 field can change :(

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

yes, i understand this.

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

well, after thinking a bit more about the list head protection, i do not 
really need the list head lock. all i need is to ensure the list head 
never changes. this can be easily done by addind the static dummy entry 
and use it as the list head. this way if i want to insert element into 
the list all i need is lock dummy entry (head) and head->next (if any). 
then i can safely insert element after the head.

> If you implement this, I strongly recommend making the lists singally
> linked to avoid the possiablity of this deadlock.

yes, i was thinking the same too. but double-linked list gives o(1) 
deletion (which is very nice :)

so i guess the restrictions are:

1) lock order: item "x", then item "x->previous" (if any), then item 
"x->next" (if any)

2) always scan list forward

3) never use "x->previuos" field (except for "x" locking)

it can even be done with standard sys/queue.h macros :) i just ran 
wintess test and it only complained about "acquiring duplicate lock of 
same type".

thanks,
max