[RFC][Patch] Use rbtree in fs/aio.c

[Eric Sesterhenn / snakebyte <snakebyte@gmx.de>]

hi,

while grepping trough the kernel sources, i noticed there are
quite a few FIXME and TODO comments and the number is increasing
each release by ~30. That is why i try to tackle a fixme in fs/aio.c.

/*	Lookup an ioctx id.  ioctx_list is lockless for reads.
 *	FIXME: this is O(n) and is only suitable for development.
 */

The attached patch replaces the linked list in aio.c with a
rbtree to speed up the lookups. Since it seems likely() that
the first entry in the list is the one we try to lookup I
dont know if this is the way to go:

  for (ioctx = mm->ioctx_list; ioctx; ioctx = ioctx->next)
	if (likely(ioctx->user_id == ctx_id && !ioctx->dead))  {

The patch compiles, boots, and survives an aio-stress
( ftp://ftp.suse.com/pub/people/mason/utils/aio-stress.c )
run with multiple threads. When i only run a read/write test
with no random access it is ~2-3 seconds faster than without
the patch, but that might also be an error in measurement.

Since i am pretty new to kernel stuff, feel free to flame and
please cc me on replies.


Signed-off-by: Eric Sesterhenn <snakebyte@gmx.de>


--- linux-2.6.15/include/linux/aio.h	2006-01-03 04:21:10.000000000 +0100
+++ linux-2.6.15-aio/include/linux/aio.h	2006-01-10 16:53:05.000000000 +0100
@@ -4,6 +4,7 @@
 #include <linux/list.h>
 #include <linux/workqueue.h>
 #include <linux/aio_abi.h>
+#include <linux/rbtree.h>
 
 #include <asm/atomic.h>
 
@@ -173,7 +174,7 @@ struct kioctx {
 
 	/* This needs improving */
 	unsigned long		user_id;
-	struct kioctx		*next;
+	struct rb_node		rb_node;
 
 	wait_queue_head_t	wait;
 
--- linux-2.6.15/fs/aio.c	2006-01-03 04:21:10.000000000 +0100
+++ linux-2.6.15-aio/fs/aio.c	2006-01-10 18:40:30.000000000 +0100
@@ -62,6 +62,11 @@ static LIST_HEAD(fput_head);
 static void aio_kick_handler(void *);
 static void aio_queue_work(struct kioctx *);
 
+struct kioctx *ioctx_rb_get_next(struct kioctx *ioctx);
+struct kioctx *ioctx_rb_find(unsigned long ctx_id);
+void ioctx_rb_insert(struct kioctx *ioctx);
+void ioctx_rb_erase(struct kioctx *ioctx);
+
 /* aio_setup
  *	Creates the slab caches used by the aio routines, panic on
  *	failure as this is done early during the boot sequence.
@@ -244,11 +249,8 @@ static struct kioctx *ioctx_alloc(unsign
 	if (ctx->max_reqs == 0)
 		goto out_cleanup;
 
-	/* now link into global list.  kludge.  FIXME */
-	write_lock(&mm->ioctx_list_lock);
-	ctx->next = mm->ioctx_list;
-	mm->ioctx_list = ctx;
-	write_unlock(&mm->ioctx_list_lock);
+	/* insert into the tree */
+	ioctx_rb_insert(ctx);
 
 	dprintk("aio: allocated ioctx %p[%ld]: mm=%p mask=0x%x\n",
 		ctx, ctx->user_id, current->mm, ctx->ring_info.nr);
@@ -336,11 +338,10 @@ ssize_t fastcall wait_on_sync_kiocb(stru
  */
 void fastcall exit_aio(struct mm_struct *mm)
 {
-	struct kioctx *ctx = mm->ioctx_list;
-	mm->ioctx_list = NULL;
+	struct kioctx *ctx = (struct kioctx *) mm->ioctx_rb.rb_node;
 	while (ctx) {
-		struct kioctx *next = ctx->next;
-		ctx->next = NULL;
+		struct kioctx *next = ioctx_rb_get_next(ctx);
+		ioctx_rb_erase(ctx);
 		aio_cancel_all(ctx);
 
 		wait_for_all_aios(ctx);
@@ -541,23 +542,92 @@ int fastcall aio_put_req(struct kiocb *r
 	return ret;
 }
 
-/*	Lookup an ioctx id.  ioctx_list is lockless for reads.
- *	FIXME: this is O(n) and is only suitable for development.
- */
-struct kioctx *lookup_ioctx(unsigned long ctx_id)
+struct kioctx *ioctx_rb_get_next(struct kioctx *ioctx)
 {
-	struct kioctx *ioctx;
-	struct mm_struct *mm;
+	struct mm_struct *mm = current->mm;
+	struct rb_node *tmp;
+	
+	read_lock(&mm->ioctx_list_lock);
+	tmp = rb_next(&ioctx->rb_node);
+	read_unlock(&mm->ioctx_list_lock);
+	return rb_entry(tmp, struct kioctx, rb_node);
+}
 
-	mm = current->mm;
+/*
+ *	dead -> search for !ioctx->dead
+ */
+struct kioctx *ioctx_rb_find(unsigned long ctx_id)
+{
+	struct mm_struct *mm = current->mm;
+	struct rb_node *n, *next;
+	struct kioctx *tmp;
+	
+	n = mm->ioctx_rb.rb_node;
+	if (!n)
+		return NULL;
+	
 	read_lock(&mm->ioctx_list_lock);
-	for (ioctx = mm->ioctx_list; ioctx; ioctx = ioctx->next)
-		if (likely(ioctx->user_id == ctx_id && !ioctx->dead)) {
-			get_ioctx(ioctx);
+	for (;;)
+	{
+		tmp = rb_entry(n, struct kioctx, rb_node);
+		if (ctx_id <= tmp->user_id)
+			next = n->rb_left;
+		else
+			next = n->rb_right;
+
+		if (!next)
 			break;
-		}
+		n = next;
+	}
+	if (ctx_id > tmp->user_id)
+	{
+		tmp = ioctx_rb_get_next(tmp);
+	}
 	read_unlock(&mm->ioctx_list_lock);
+	if (tmp->dead)
+		return NULL;
+
+	return tmp;
+}
+
+void ioctx_rb_insert(struct kioctx *ioctx)
+{
+	struct mm_struct *mm = current->mm;
+	struct rb_node *parent = NULL;
+	struct rb_node **p = &mm->ioctx_rb.rb_node;
+	struct kioctx *tmp;
+	
+	write_lock(&mm->ioctx_list_lock);
+	while(*p)
+	{
+		parent = *p;
+		tmp = rb_entry(parent, struct kioctx, rb_node);
+		if (ioctx->user_id < tmp->user_id)
+			p = &(*p)->rb_left;
+		else
+			p = &(*p)->rb_right;
+	}
+	rb_link_node(&ioctx->rb_node, parent, p);
+	rb_insert_color(&ioctx->rb_node, &mm->ioctx_rb);
+	write_unlock(&mm->ioctx_list_lock);
+}
+
+void ioctx_rb_erase(struct kioctx *ioctx)
+{
+        struct mm_struct *mm = current->mm;
+        write_lock(&mm->ioctx_list_lock);
+	rb_erase(&ioctx->rb_node, &mm->ioctx_rb);
+	write_unlock(&mm->ioctx_list_lock);
+}
 
+/*	Lookup an ioctx id.  ioctx_list is lockless for reads.
+ */
+struct kioctx *lookup_ioctx(unsigned long ctx_id)
+{
+	struct kioctx *ioctx;
+
+	ioctx = ioctx_rb_find(ctx_id);
+	get_ioctx(ioctx);
 	return ioctx;
 }
 
@@ -1216,21 +1286,13 @@ out:
  */
 static void io_destroy(struct kioctx *ioctx)
 {
-	struct mm_struct *mm = current->mm;
-	struct kioctx **tmp;
 	int was_dead;
 
-	/* delete the entry from the list is someone else hasn't already */
-	write_lock(&mm->ioctx_list_lock);
+	/* delete the entry from the list if someone else hasn't already */
 	was_dead = ioctx->dead;
 	ioctx->dead = 1;
-	for (tmp = &mm->ioctx_list; *tmp && *tmp != ioctx;
-	     tmp = &(*tmp)->next)
-		;
-	if (*tmp)
-		*tmp = ioctx->next;
-	write_unlock(&mm->ioctx_list_lock);
-
+	ioctx_rb_erase(ioctx);
+	
 	dprintk("aio_release(%p)\n", ioctx);
 	if (likely(!was_dead))
 		put_ioctx(ioctx);	/* twice for the list */

--- linux-2.6.15/kernel/fork.c	2006-01-03 04:21:10.000000000 +0100
+++ linux-2.6.15-aio/kernel/fork.c	2006-01-10 15:53:54.000000000 +0100
@@ -322,7 +322,7 @@ static struct mm_struct * mm_init(struct
 	set_mm_counter(mm, anon_rss, 0);
 	spin_lock_init(&mm->page_table_lock);
 	rwlock_init(&mm->ioctx_list_lock);
-	mm->ioctx_list = NULL;
+	mm->ioctx_rb = RB_ROOT;
 	mm->free_area_cache = TASK_UNMAPPED_BASE;
 	mm->cached_hole_size = ~0UL;
 
--- linux-2.6.15/include/linux/sched.h	2006-01-03 04:21:10.000000000 +0100
+++ linux-2.6.15-aio/include/linux/sched.h	2006-01-10 15:50:19.000000000 +0100
@@ -356,7 +356,7 @@ struct mm_struct {
 
 	/* aio bits */
 	rwlock_t		ioctx_list_lock;
-	struct kioctx		*ioctx_list;
+	struct rb_root		ioctx_rb;
 };
 
 struct sighand_struct {


-
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/