[PATCH] [BLOCK] cfq-iosched: change cfq io context linking from list to tree

On setups with many disks, we spend a considerable amount of time
looking up the process-disk mapping on each queue of io. Testing with
a NULL based block driver, this costs 40-50% reduction in throughput
for 1000 disks.

Signed-off-by: Jens Axboe <axboe@suse.de>

1 files changed, 13 insertions, 6 deletions

diff --git a/block/ll_rw_blk.c b/block/ll_rw_blk.c
index 82469db25100..cb608768ca37 100644
--- a/block/ll_rw_blk.c
+++ b/block/ll_rw_blk.c
@@ -3539,11 +3539,15 @@ void put_io_context(struct io_context *ioc)
         BUG_ON(atomic_read(&ioc->refcount) == 0);
 
         if (atomic_dec_and_test(&ioc->refcount)) {
+                struct cfq_io_context *cic;
+
                 rcu_read_lock();
                 if (ioc->aic && ioc->aic->dtor)
                         ioc->aic->dtor(ioc->aic);
-                if (ioc->cic && ioc->cic->dtor)
-                        ioc->cic->dtor(ioc->cic);
+                if (ioc->cic_root.rb_node != NULL) {
+                        cic = rb_entry(rb_first(&ioc->cic_root), struct cfq_io_context, rb_node);
+                        cic->dtor(ioc);
+                }
                 rcu_read_unlock();
 
                 kmem_cache_free(iocontext_cachep, ioc);
@@ -3556,6 +3560,7 @@ void exit_io_context(void)
 {
         unsigned long flags;
         struct io_context *ioc;
+        struct cfq_io_context *cic;
 
         local_irq_save(flags);
         task_lock(current);
@@ -3567,9 +3572,11 @@ void exit_io_context(void)
 
         if (ioc->aic && ioc->aic->exit)
                 ioc->aic->exit(ioc->aic);
-        if (ioc->cic && ioc->cic->exit)
-                ioc->cic->exit(ioc->cic);
-
+        if (ioc->cic_root.rb_node != NULL) {
+                cic = rb_entry(rb_first(&ioc->cic_root), struct cfq_io_context, rb_node);
+                cic->exit(ioc);
+        }
+ 
         put_io_context(ioc);
 }
 
@@ -3598,7 +3605,7 @@ struct io_context *current_io_context(gfp_t gfp_flags)
                 ret->last_waited = jiffies; /* doesn't matter... */
                 ret->nr_batch_requests = 0; /* because this is 0 */
                 ret->aic = NULL;
-                ret->cic = NULL;
+                ret->cic_root.rb_node = NULL;
                 tsk->io_context = ret;
         }