From owner-freebsd-current@FreeBSD.ORG Fri Sep 3 19:38:21 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 77C9516A4CE for ; Fri, 3 Sep 2004 19:38:21 +0000 (GMT) Received: from out001.email.savvis.net (out001.apptix.savvis.net [216.91.32.44]) by mx1.FreeBSD.org (Postfix) with ESMTP id 2076F43D54 for ; Fri, 3 Sep 2004 19:38:21 +0000 (GMT) (envelope-from Maksim.Yevmenkin@savvis.net) Received: from s228130hz1ew03.apptix-01.savvis.net ([10.146.4.28]) by out001.email.savvis.net with Microsoft SMTPSVC(6.0.3790.0); Fri, 3 Sep 2004 14:38:20 -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 14:38:20 -0500 Message-ID: <4138C82A.5020304@savvis.net> Date: Fri, 03 Sep 2004 12:38:18 -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> In-Reply-To: <20040903191128.GA649@odin.ac.hmc.edu> Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit X-OriginalArrivalTime: 03 Sep 2004 19:38:20.0157 (UTC) FILETIME=[912452D0:01C491ED] 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 19:38:21 -0000 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