mirror of https://lore.kernel.org/lkml/
 help / color / mirror / Atom feed
From: Robert Love <rml@novell.com>
To: John McCutchan <ttb@tentacle.dhs.org>
Cc: linux-kernel@vger.kernel.org, akpm@osdl.org, iggy@gentoo.org
Subject: [patch] inotify: use the idr layer
Date: Tue, 28 Sep 2004 17:46:04 -0400	[thread overview]
Message-ID: <1096407964.4911.90.camel@betsy.boston.ximian.com> (raw)
In-Reply-To: <1096250524.18505.2.camel@vertex>

[-- Attachment #1: Type: text/plain, Size: 1310 bytes --]

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


[-- Attachment #2: inotify-idr-layer-1.patch --]
[-- Type: text/x-patch, Size: 5925 bytes --]

idr layer support for inotify

Signed-Off-By: Robert Love <rml@novell.com>

 drivers/char/inotify.c |   93 +++++++++++++++++++++++++++----------------------
 1 files changed, 53 insertions(+), 40 deletions(-)

diff -urN linux-inotify/drivers/char/inotify.c linux/drivers/char/inotify.c
--- linux-inotify/drivers/char/inotify.c	2004-09-28 15:22:02.152818864 -0400
+++ linux/drivers/char/inotify.c	2004-09-28 15:27:03.994931888 -0400
@@ -17,15 +17,14 @@
 /* TODO: 
  * rename inotify_watcher to inotify_watch
  * need a way to connect MOVED_TO/MOVED_FROM events in user space
- * use b-tree so looking up watch by WD is faster
  */
 
 #include <linux/bitops.h>
-#include <linux/bitmap.h>
 #include <linux/module.h>
 #include <linux/kernel.h>
 #include <linux/sched.h>
 #include <linux/spinlock.h>
+#include <linux/idr.h>
 #include <linux/slab.h>
 #include <linux/fs.h>
 #include <linux/namei.h>
@@ -61,22 +60,19 @@
  * For each inotify device, we need to keep track of the events queued on it,
  * a list of the inodes that we are watching, and so on.
  *
- * 'bitmask' holds one bit for each possible watcher descriptor: a set bit
- * implies that the given WD is valid, unset implies it is not.
- *
  * This structure is protected by 'lock'.  Lock ordering:
  *	dev->lock
  *		dev->wait->lock
  * FIXME: Define lock ordering wrt inode and dentry locking!
  */
 struct inotify_device {
-	DECLARE_BITMAP(bitmask, MAX_INOTIFY_DEV_WATCHERS);
 	wait_queue_head_t 	wait;
+	struct idr		idr;
 	struct list_head 	events;
 	struct list_head 	watchers;
 	spinlock_t		lock;
 	unsigned int		event_count;
-	int			nr_watches;
+	unsigned int		nr_watches;
 };
 
 struct inotify_watcher {
@@ -179,10 +175,6 @@
 		return;
 
 	event_object_count--;
-	INIT_LIST_HEAD(&kevent->list);
-	kevent->event.wd = -1;
-	kevent->event.mask = 0;
-
 	iprintk(INOTIFY_DEBUG_ALLOC, "free'd kevent %p\n", kevent);
 	kmem_cache_free(kevent_cache, kevent);
 }
@@ -282,20 +274,30 @@
 /*
  * inotify_dev_get_wd - returns the next WD for use by the given dev
  *
- * Caller must hold dev->lock before calling.
+ * This function sleeps.
  */
-static int inotify_dev_get_wd(struct inotify_device *dev)
+static int inotify_dev_get_wd(struct inotify_device *dev,
+			      struct inotify_watcher *watcher)
 {
-	int wd;
+	int ret;
 
-	if (!dev || dev->nr_watches == MAX_INOTIFY_DEV_WATCHERS)
+	if (dev->nr_watches == MAX_INOTIFY_DEV_WATCHERS)
 		return -1;
 
+repeat:
+	if (!idr_pre_get(&dev->idr, GFP_KERNEL))
+		return -1;
+
+	spin_lock(&dev->lock);
+	ret = idr_get_new(&dev->idr, watcher, &watcher->wd);
+	spin_lock(&dev->lock);
+	if (ret == -EAGAIN)	/* more memory is required, try again */
+		goto repeat;
+	if (ret == -ENOSPC)	/* the idr is full! */
+		return -1;
 	dev->nr_watches++;
-	wd = find_first_zero_bit(dev->bitmask, MAX_INOTIFY_DEV_WATCHERS);
-	set_bit(wd, dev->bitmask);
 
-	return wd;
+	return 0;
 }
 
 /*
@@ -309,7 +311,7 @@
 		return -1;
 
 	dev->nr_watches--;
-	clear_bit(wd, dev->bitmask);
+	idr_remove(&dev->idr, wd);
 
 	return 0;
 }
@@ -331,7 +333,6 @@
 		return NULL;
 	}
 
-	watcher->wd = -1;
 	watcher->mask = mask;
 	watcher->inode = inode;
 	watcher->dev = dev;
@@ -339,11 +340,7 @@
 	INIT_LIST_HEAD(&watcher->i_list);
 	INIT_LIST_HEAD(&watcher->u_list);
 
-	spin_lock(&dev->lock);
-	watcher->wd = inotify_dev_get_wd(dev);
-	spin_unlock(&dev->lock);
-
-	if (watcher->wd < 0) {
+	if (inotify_dev_get_wd(dev, watcher)) {
 		iprintk(INOTIFY_DEBUG_ERRORS,
 			"Could not get wd for watcher %p\n", watcher);
 		iprintk(INOTIFY_DEBUG_ALLOC, "free'd watcher %p\n", watcher);
@@ -387,15 +384,18 @@
 	return NULL;
 }
 
-static struct inotify_watcher *dev_find_wd(struct inotify_device *dev, int wd)
+/*
+ * dev_find_wd - given a (dev,wd) pair, returns the matching inotify_watcher
+ *
+ * Returns the results of looking up (dev,wd) in the idr layer.  NULL is
+ * returned on error.
+ *
+ * The caller must hold dev->lock.
+ */
+static inline struct inotify_watcher *dev_find_wd(struct inotify_device *dev,
+						  int wd)
 {
-	struct inotify_watcher *watcher;
-
-	list_for_each_entry(watcher, &dev->watchers, d_list) {
-		if (watcher->wd == wd)
-			return watcher;
-	}
-	return NULL;
+	return idr_find(&dev->idr, wd);
 }
 
 static int inotify_dev_is_watching_inode(struct inotify_device *dev,
@@ -411,6 +411,11 @@
 	return 0;
 }
 
+/*
+ * inotify_dev_add_watcher - add the given watcher to the given device instance
+ *
+ * Caller must hold dev->lock.
+ */
 static int inotify_dev_add_watcher(struct inotify_device *dev,
 				   struct inotify_watcher *watcher)
 {
@@ -570,11 +575,11 @@
 	struct inotify_device *dev;
 	struct inode *inode;
 
-	spin_lock(&watcher->dev->lock);
-	spin_lock(&watcher->inode->i_lock);
-
-	inode = watcher->inode;
 	dev = watcher->dev;
+	inode = watcher->inode;
+
+	spin_lock(&dev->lock);
+	spin_lock(&inode->i_lock);
 
 	if (event)
 		inotify_dev_queue_event(dev, watcher, event, NULL);
@@ -590,7 +595,8 @@
 	unref_inode(inode);
 }
 
-static void process_umount_list(struct list_head *umount) {
+static void process_umount_list(struct list_head *umount)
+{
 	struct inotify_watcher *watcher, *next;
 
 	list_for_each_entry_safe(watcher, next, umount, u_list)
@@ -598,7 +604,7 @@
 }
 
 static void build_umount_list(struct list_head *head, struct super_block *sb,
-			       struct list_head *umount)
+			      struct list_head *umount)
 {
 	struct inode *	inode;
 
@@ -766,7 +772,7 @@
 	if (!dev)
 		return -ENOMEM;
 
-	bitmap_zero(dev->bitmask, MAX_INOTIFY_DEV_WATCHERS);
+	idr_init(&dev->idr);
 
 	INIT_LIST_HEAD(&dev->events);
 	INIT_LIST_HEAD(&dev->watchers);
@@ -898,9 +904,16 @@
 {
 	struct inotify_watcher *watcher;
 
+	/*
+	 * FIXME: Silly to grab dev->lock here and then drop it, when
+	 * ignore_helper() grabs it anyway a few lines down.
+	 */
+	spin_lock(&dev->lock);
 	watcher = dev_find_wd(dev, wd);
+	spin_unlock(&dev->lock);
 	if (!watcher)
 		return -EINVAL;
+
 	ignore_helper(watcher, 0);
 
 	return 0;

  parent reply	other threads:[~2004-09-28 21:48 UTC|newest]

Thread overview: 61+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2004-09-27  2:02 [RFC][PATCH] inotify 0.10.0 John McCutchan
2004-09-27  4:17 ` Andrew Morton
2004-09-27 20:52   ` Robert Love
2004-09-28  4:41     ` Andrew Morton
2004-09-28  2:14       ` Robert Love
2004-09-28  3:44         ` John McCutchan
2004-09-28 17:31           ` Robert Love
2004-09-28  5:45     ` Ray Lee
2004-09-28 19:08       ` Andrew Morton
2004-09-28 16:41         ` Chris Friesen
2004-09-28 16:53           ` Robert Love
2004-09-28 17:32             ` Ray Lee
2004-09-28 20:34               ` John McCutchan
2004-09-28 21:20                 ` Ray Lee
2004-09-30  4:15                 ` Andrew Morton
2004-09-30  1:32                   ` John McCutchan
2004-09-30  1:34                   ` Robert Love
2004-09-30  3:05                     ` Paul Jackson
2004-09-30  5:37                       ` Chris Friesen
2004-09-30 12:43                         ` Paul Jackson
2004-09-30 15:29                       ` Ray Lee
2004-09-30 16:27                         ` Paul Jackson
2004-09-30 16:53                           ` Ray Lee
2004-09-30 17:48                             ` Paul Jackson
2004-10-01  1:22                               ` Ray Lee
2004-10-01  4:09                                 ` Paul Jackson
2004-10-04 20:58                                   ` Ray Lee
2004-09-28 20:40         ` John McCutchan
2004-09-28 20:47           ` Robert Love
2004-09-28 21:39             ` Ray Lee
2004-09-28 22:10               ` Robert Love
2004-09-28 21:32           ` Ray Lee
2004-09-30  4:31           ` Andrew Morton
2004-09-28 20:26       ` John McCutchan
2004-09-28 21:10         ` Ray Lee
2004-09-28 21:20           ` Robert Love
2004-09-28 21:21           ` John McCutchan
2004-09-28 21:35             ` Robert Love
2004-09-28 21:50               ` Ray Lee
2004-09-28 22:03                 ` Robert Love
2004-09-27 16:21 ` [gamin] [RFC][PATCH] inotify 0.10.0 [u] Martin Schlemmer [c]
2004-09-27 16:24   ` Robert Love
2004-09-27 16:30     ` Martin Schlemmer [c]
2004-09-27 16:35       ` Robert Love
2004-09-27 17:10         ` Martin Schlemmer [c]
2004-09-27 16:25 ` Martin Schlemmer [c]
2004-09-27 17:12 ` [RFC][PATCH] inotify 0.10.0 Robert Love
2004-09-27 19:48   ` Paul Jackson
2004-09-27 20:22     ` patch] inotify: use bitmap.h functions Robert Love
2004-09-27 20:38       ` Paul Jackson
2004-09-27 19:51 ` [patch] inotify: make it configurable Robert Love
2004-09-27 19:53 ` [patch] inotify: doh Robert Love
2004-09-27 20:06 ` [RFC][PATCH] inotify 0.10.0 Robert Love
2004-09-27 20:39 ` [patch] inotify: don't check private_data Robert Love
2004-09-28  1:05 ` [patch] inotify: silly fix Robert Love
2004-09-28 17:38 ` [RFC][PATCH] inotify 0.10.0 Mike Waychison
2004-09-28 20:35   ` John McCutchan
2004-09-28 17:48 ` [patch] inotify: remove timer Robert Love
2004-09-28 21:46 ` Robert Love [this message]
2004-09-28 21:58   ` [patch] inotify: use the idr layer John McCutchan
2004-09-28 22:08     ` Robert Love

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=1096407964.4911.90.camel@betsy.boston.ximian.com \
    --to=rml@novell.com \
    --cc=akpm@osdl.org \
    --cc=iggy@gentoo.org \
    --cc=linux-kernel@vger.kernel.org \
    --cc=ttb@tentacle.dhs.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox

all inboxes | Powered by JetHome®