Skip site navigation (1)Skip section navigation (2)
Date:      Fri, 3 Sep 2004 12:11:28 -0700
From:      Brooks Davis <brooks@one-eyed-alien.net>
To:        Maksim Yevmenkin <maksim.yevmenkin@savvis.net>
Cc:        freebsd-current@freebsd.org
Subject:   Re: fine grained locking and traversing linked lists
Message-ID:  <20040903191128.GA649@odin.ac.hmc.edu>
In-Reply-To: <4138BE8D.7000102@savvis.net>
References:  <4138BE8D.7000102@savvis.net>

next in thread | previous in thread | raw e-mail | index | archive | help

--ikeVEW9yuYc//A+q
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

On Fri, Sep 03, 2004 at 11:57:17AM -0700, Maksim Yevmenkin wrote:
> Dear Hackers,
>=20
> 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.

Why do you have to hold the object mutex?  I can think of scenerios
where that is required, but usually it isn't since they key is fixed at
the time the item is inserted in to the list, or is at least protected
by the list mutex.  For an example of a key protected by the list
mutex, consider struct ifnet's if_xname member relative to ifunit() and
renaming.

> 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 =3D y->previous" lock and object "z =3D
> y->next" lock.
>=20
> so, the $1 million question is: am i missing something? or this will work?

How do you protect the head in this case?  The list mutex would normally
do so, but if the head can change, you'll need a mutex to protect it
(using an array hid this issue).  Also, doubly linked lists won't work
without a lot of effort (read pain :-) because scanning backwards and
forwards at the same time will lead to deadlock.

-- Brooks

--=20
Any statement of the form "X is the one, true Y" is FALSE.
PGP fingerprint 655D 519C 26A7 82E7 2529  9BF0 5D8E 8BE9 F238 1AD4

--ikeVEW9yuYc//A+q
Content-Type: application/pgp-signature
Content-Disposition: inline

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.1 (GNU/Linux)

iD8DBQFBOMHgXY6L6fI4GtQRAvziAJ4yiCYMxbjgb3rKV+PaEAtjOWo40gCgu8Ee
o6NZGJUda8f7hXxOr5OMgV0=
=UNv4
-----END PGP SIGNATURE-----

--ikeVEW9yuYc//A+q--



Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20040903191128.GA649>