Date: Fri, 03 Sep 2004 19:34:19 -0600 (MDT) From: "M. Warner Losh" <imp@bsdimp.com> To: maksim.yevmenkin@savvis.net Cc: freebsd-current@freebsd.org Subject: Re: fine grained locking and traversing linked lists Message-ID: <20040903.193419.101345623.imp@bsdimp.com> In-Reply-To: <4138BE8D.7000102@savvis.net>
index | next in thread | previous in thread | raw e-mail
In message: <4138BE8D.7000102@savvis.net>
Maksim Yevmenkin <maksim.yevmenkin@savvis.net> 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
home |
help
Want to link to this message? Use this
URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20040903.193419.101345623.imp>