Subject: Re: [patch] inotify: use the idr layer
From: John McCutchan <ttb@tentacle.dhs.org>
To: Robert Love <rml@novell.com>
Cc: linux-kernel@vger.kernel.org, akpm@osdl.org, iggy@gentoo.org
In-Reply-To: <1096407964.4911.90.camel@betsy.boston.ximian.com>
References: <1096250524.18505.2.camel@vertex>
	 <1096407964.4911.90.camel@betsy.boston.ximian.com>
Content-Type: text/plain
Content-Transfer-Encoding: 7bit
Message-Id: <1096408694.16622.1.camel@vertex>
Mime-Version: 1.0
Date: Tue, 28 Sep 2004 17:58:14 -0400
Sender: linux-kernel-owner@vger.kernel.org
Content-Length: 1880
Lines: 44

+       spin_lock(&dev->lock);
+       ret = idr_get_new(&dev->idr, watcher, &watcher->wd);
+       spin_lock(&dev->lock);

I think you mean spin_unlock on the third line? Other than that I think
it should work.

John
On Tue, 2004-09-28 at 17:46, Robert Love wrote:
> OK, I told John I would post this ASAP, as soon as I finished testing
> it, but I got backed up, so here it is without much testing.  It does
> compile fine.
> 
> This patch removes our current bitmap-based allocation system and
> replaces it with the idr layer.  The idr layer allows us to use a radix
> tree, rooted at each device instance, to trivially map between watcher
> descriptors and watcher structures.  In idr terminology, the watcher
> descriptor is the id and the watcher structure is the pointer.
> 
> Allocating a new watcher descriptor and associating it with a given
> watcher structure is done in the same place as before,
> inotify_dev_get_wd().  The code for doing this is a bit weird.  The idr
> layer's interface leaves a bit to be desired.
> 
> The function dev_find_wd() is used to map from a given watcher
> descriptor to a watcher structure.  This used to be our least scalable
> function: O(n), but at a small fixed n, so you could call it O(1).  Now
> it is O(lg n); n is still fixed, so you can still call it O(1).
> 
> I also cleaned up some locking and added some comments.
> 
> Like I said, I have not tested this, probably won't until tomorrow, but
> here it is to play with earlier if anyone so chooses.  The idr layer is
> rather nice for this sort of thing.
> 
> Patch is on top of all of my previous patches.
> 
> 	Robert Love
> 
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/