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> References: <4138BE8D.7000102@savvis.net>
next in thread | previous in thread | raw e-mail | index | archive | help
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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20040903.193419.101345623.imp>