Skip to contentSkip to conversation

Use rbtree in fs/aio.c

RFC PATCH New Eric Sesterhenn / snakebyte 1 participant 1 message Jan 10, 2006

Subsystems (5)
lore
Share & tools
lore
#0 lore raw

RFC PATCH 1/1 Use rbtree in fs/aio.c

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.

include/linux/aio.h +2 -1
@@ -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;
 
fs/aio.c +93 -31

165 lines not on this page · raw message

kernel/fork.c +1 -1
@@ -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;
 
include/linux/sched.h +1 -1
@@ -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 {