Date: Fri, 03 Sep 2004 15:04:23 -0700 From: Maksim Yevmenkin <maksim.yevmenkin@savvis.net> To: Brooks Davis <brooks@one-eyed-alien.net> Cc: freebsd-current@freebsd.org Subject: Re: fine grained locking and traversing linked lists Message-ID: <4138EA67.8090605@savvis.net> In-Reply-To: <20040903195528.GA9245@odin.ac.hmc.edu> References: <4138BE8D.7000102@savvis.net> <20040903191128.GA649@odin.ac.hmc.edu> <4138C82A.5020304@savvis.net> <20040903195528.GA9245@odin.ac.hmc.edu>
next in thread | previous in thread | raw e-mail | index | archive | help
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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?4138EA67.8090605>