From owner-freebsd-current@FreeBSD.ORG Fri Sep 3 23:27:20 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 0BEC916A4CE for ; Fri, 3 Sep 2004 23:27:20 +0000 (GMT) Received: from mail1.speakeasy.net (mail1.speakeasy.net [216.254.0.201]) by mx1.FreeBSD.org (Postfix) with ESMTP id CE56443D53 for ; Fri, 3 Sep 2004 23:27:19 +0000 (GMT) (envelope-from jmg@hydrogen.funkthat.com) Received: (qmail 29410 invoked from network); 3 Sep 2004 23:27:19 -0000 Received: from gate.funkthat.com (HELO hydrogen.funkthat.com) ([69.17.45.168]) (envelope-sender ) by mail1.speakeasy.net (qmail-ldap-1.03) with SMTP for ; 3 Sep 2004 23:27:19 -0000 Received: from hydrogen.funkthat.com (lwxklm@localhost.funkthat.com [127.0.0.1])i83NRHuU026503; Fri, 3 Sep 2004 16:27:18 -0700 (PDT) (envelope-from jmg@hydrogen.funkthat.com) Received: (from jmg@localhost) by hydrogen.funkthat.com (8.12.10/8.12.10/Submit) id i83NRHhD026502; Fri, 3 Sep 2004 16:27:17 -0700 (PDT) Date: Fri, 3 Sep 2004 16:27:17 -0700 From: John-Mark Gurney To: Maksim Yevmenkin Message-ID: <20040903232716.GL29902@funkthat.com> Mail-Followup-To: Maksim Yevmenkin , Brooks Davis , freebsd-current@freebsd.org References: <4138BE8D.7000102@savvis.net> <20040903191128.GA649@odin.ac.hmc.edu> <4138C82A.5020304@savvis.net> <20040903195528.GA9245@odin.ac.hmc.edu> <4138EA67.8090605@savvis.net> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <4138EA67.8090605@savvis.net> User-Agent: Mutt/1.4.1i X-Operating-System: FreeBSD 4.2-RELEASE i386 X-PGP-Fingerprint: B7 EC EF F8 AE ED A7 31 96 7A 22 B3 D8 56 36 F4 X-Files: The truth is out there X-URL: http://resnet.uoregon.edu/~gurney_j/ X-Resume: http://resnet.uoregon.edu/~gurney_j/resume.html 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 Reply-To: John-Mark Gurney 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 23:27:20 -0000 Maksim Yevmenkin wrote this message on Fri, Sep 03, 2004 at 15:04 -0700: > >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". This can still lead to a dead lock: obja <-> objb <-> objc <-> objd T1: lock (objb), lock(obja) T2: lock (objc), lock(objb, but blocks for T1) T1: lock (objc, blocks for T2) So, one solution is to use a list lock, and a refcnt'd object. Then all of the next/previous pointers are protected by the list lock, and the list gets one ref... Since you're using refcnts, you can keep a ref, unlock the object lock, lock the list lock, before relocking the object lock if necessary... -- John-Mark Gurney Voice: +1 415 225 5579 "All that I will do, has been done, All that I have, has not."