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>