From owner-freebsd-current@FreeBSD.ORG Fri Sep 3 18:57:23 2004 Return-Path: Delivered-To: freebsd-current@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id 5280D16A4CE for ; Fri, 3 Sep 2004 18:57:23 +0000 (GMT) Received: from out002.email.savvis.net (out002.apptix.savvis.net [216.91.32.45]) by mx1.FreeBSD.org (Postfix) with ESMTP id 127CC43D2D for ; Fri, 3 Sep 2004 18:57:23 +0000 (GMT) (envelope-from Maksim.Yevmenkin@savvis.net) Received: from s228130hz1ew03.apptix-01.savvis.net ([10.146.4.28]) by out002.email.savvis.net with Microsoft SMTPSVC(6.0.3790.0); Fri, 3 Sep 2004 13:57:25 -0500 Received: from [10.254.186.111] ([66.35.239.94]) by s228130hz1ew03.apptix-01.savvis.net with Microsoft SMTPSVC(6.0.3790.0); Fri, 3 Sep 2004 13:57:21 -0500 Message-ID: <4138BE8D.7000102@savvis.net> Date: Fri, 03 Sep 2004 11:57:17 -0700 From: Maksim Yevmenkin User-Agent: Mozilla/5.0 (X11; U; FreeBSD i386; en-US; rv:1.7.2) Gecko/20040822 X-Accept-Language: en-us, en MIME-Version: 1.0 To: freebsd-current@freebsd.org Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit X-OriginalArrivalTime: 03 Sep 2004 18:57:21.0335 (UTC) FILETIME=[D791DC70:01C491E7] Subject: fine grained locking and traversing linked lists X-BeenThere: freebsd-current@freebsd.org X-Mailman-Version: 2.1.1 Precedence: list List-Id: Discussions about the use of FreeBSD-current List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 03 Sep 2004 18:57:23 -0000 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 #include #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