From owner-freebsd-current@FreeBSD.ORG Sat Sep 4 01:36:58 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 70D4316A4CE for ; Sat, 4 Sep 2004 01:36:58 +0000 (GMT) Received: from harmony.village.org (rover.village.org [168.103.84.182]) by mx1.FreeBSD.org (Postfix) with ESMTP id BB81F43D2D for ; Sat, 4 Sep 2004 01:36:57 +0000 (GMT) (envelope-from imp@bsdimp.com) Received: from localhost (warner@rover2.village.org [10.0.0.1]) by harmony.village.org (8.12.11/8.12.11) with ESMTP id i841Xxrn013904; Fri, 3 Sep 2004 19:34:00 -0600 (MDT) (envelope-from imp@bsdimp.com) Date: Fri, 03 Sep 2004 19:34:19 -0600 (MDT) Message-Id: <20040903.193419.101345623.imp@bsdimp.com> To: maksim.yevmenkin@savvis.net From: "M. Warner Losh" In-Reply-To: <4138BE8D.7000102@savvis.net> References: <4138BE8D.7000102@savvis.net> X-Mailer: Mew version 3.3 on Emacs 21.3 / Mule 5.0 (SAKAKI) Mime-Version: 1.0 Content-Type: Text/Plain; charset=us-ascii Content-Transfer-Encoding: 7bit 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: Sat, 04 Sep 2004 01:36:58 -0000 In message: <4138BE8D.7000102@savvis.net> Maksim Yevmenkin writes: : 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. : : 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? : : note: in the "spherical cow" below linked list is replaced by array, : ->next and ->previous operation are replaced with +1 and -1 : respectively and -1 stands for NULL. I suspect that having a lock for the entire list would be more worthwhile. Especially since you'd have to acquire O(n) locks to safely traverse the list rather than O(1). Warner