Skip site navigation (1)Skip section navigation (2) 
Date:      Fri, 03 Sep 2004 11:57:17 -0700
From:      Maksim Yevmenkin <maksim.yevmenkin@savvis.net>
To:        freebsd-current@freebsd.org
Subject:   fine grained locking and traversing linked lists
Message-ID:  <4138BE8D.7000102@savvis.net>
next in thread | raw e-mail | index | archive | help 
Dear Hackers,

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.

--------------------------->8-------------------------------------

#include <assert.h>
#include <stdio.h>

#define N       21

static int      locks[N] = { 0, };

static void
lock(int x)
{
        assert(0 <= x && x < sizeof(locks)/sizeof(locks[0]));\
        assert(locks[x] == 0);
        locks[x] ++;
}

static void
unlock(int x)
{
        assert(0 <= x && x < sizeof(locks)/sizeof(locks[0]));
        assert(locks[x] == 1);
        locks[x] --;
}

static int
locked(int x)
{
        if (0 <= x && x < sizeof(locks)/sizeof(locks[0]))
                return (locks[x]);

        return (-1);
}

static void
printlocks(void)
{
        int     i;

        printf("\n");
        for (i = 0; i < sizeof(locks)/sizeof(locks[0]); i++)
                printf("%d ", locks[i]);
        printf("\n");
}

int
main(void)
{
        int     i, x, y, z;

        y = 0;

        lock(y);
        if ((x = (y - 1)) >= 0)
                lock(x);
        else
                x = -1;

        for (i = 1; ; i++) {
                if ((z = (y + 1)) < sizeof(locks)/sizeof(locks[0]))
                        lock(z);
                else
                        z = -1;

                printf("%-3d: (%-3d:%-3d) (%-3d:%-3d) (%-3d:%-3d)\n",
                        i, x, locked(x), y, locked(y), z, locked(z));

                if (z == -1)
                        break;

                y = z;

                if (x != -1)
                        unlock(x);

                x = y - 1;
        }

        if (x != -1)
                unlock(x);
        if (y != -1)
                unlock(y);

        printlocks();

        return (0);
}

------------->8------------------------------------

thanks,
max

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