Use rbtree in fs/aio.c
Subsystems (5)
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(structset_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 {