Date: Fri, 3 Sep 2004 16:27:17 -0700 From: John-Mark Gurney <gurney_j@resnet.uoregon.edu> To: Maksim Yevmenkin <maksim.yevmenkin@savvis.net> Cc: freebsd-current@freebsd.org Subject: Re: fine grained locking and traversing linked lists Message-ID: <20040903232716.GL29902@funkthat.com> In-Reply-To: <4138EA67.8090605@savvis.net> 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>
next in thread | previous in thread | raw e-mail | index | archive | help
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."
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20040903232716.GL29902>