Date: Fri, 03 Sep 2004 12:38:18 -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: <4138C82A.5020304@savvis.net> In-Reply-To: <20040903191128.GA649@odin.ac.hmc.edu> References: <4138BE8D.7000102@savvis.net> <20040903191128.GA649@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 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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?4138C82A.5020304>