From owner-freebsd-current@FreeBSD.ORG Fri Sep 3 22:04:30 2004 Return-Path: Delivered-To: freebsd-current@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id 842DD16A4CE for ; Fri, 3 Sep 2004 22:04:30 +0000 (GMT) Received: from out002.email.savvis.net (out002.apptix.savvis.net [216.91.32.45]) by mx1.FreeBSD.org (Postfix) with ESMTP id 3D88943D41 for ; Fri, 3 Sep 2004 22:04:30 +0000 (GMT) (envelope-from Maksim.Yevmenkin@savvis.net) Received: from s228130hz1ew03.apptix-01.savvis.net ([10.146.4.28]) by out002.email.savvis.net with Microsoft SMTPSVC(6.0.3790.0); Fri, 3 Sep 2004 17:04:29 -0500 Received: from [10.254.186.111] ([66.35.239.94]) by s228130hz1ew03.apptix-01.savvis.net with Microsoft SMTPSVC(6.0.3790.0); Fri, 3 Sep 2004 17:04:28 -0500 Message-ID: <4138EA67.8090605@savvis.net> Date: Fri, 03 Sep 2004 15:04:23 -0700 From: Maksim Yevmenkin User-Agent: Mozilla/5.0 (X11; U; FreeBSD i386; en-US; rv:1.7.2) Gecko/20040822 X-Accept-Language: en-us, en MIME-Version: 1.0 To: Brooks Davis References: <4138BE8D.7000102@savvis.net> <20040903191128.GA649@odin.ac.hmc.edu> <4138C82A.5020304@savvis.net> <20040903195528.GA9245@odin.ac.hmc.edu> In-Reply-To: <20040903195528.GA9245@odin.ac.hmc.edu> Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit X-OriginalArrivalTime: 03 Sep 2004 22:04:28.0902 (UTC) FILETIME=[FBB8A060:01C49201] cc: freebsd-current@freebsd.org Subject: Re: fine grained locking and traversing linked lists X-BeenThere: freebsd-current@freebsd.org X-Mailman-Version: 2.1.1 Precedence: list List-Id: Discussions about the use of FreeBSD-current List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 03 Sep 2004 22:04:30 -0000 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