fine grained locking and traversing linked lists

M. Warner Losh imp at
Fri Sep 3 18:36:58 PDT 2004

In message: <4138BE8D.7000102 at>
            Maksim Yevmenkin <maksim.yevmenkin at> 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 mailing list