fine grained locking and traversing linked lists
M. Warner Losh
imp at bsdimp.com
Fri Sep 3 18:36:58 PDT 2004
In message: <4138BE8D.7000102 at savvis.net>
Maksim Yevmenkin <maksim.yevmenkin at 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).
More information about the freebsd-current