[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, 6 insertions, 8 deletions

diff --git a/include/linux/blkdev.h b/include/linux/blkdev.h
index c179966f1a2f..ed0ffa673568 100644
--- a/include/linux/blkdev.h
+++ b/include/linux/blkdev.h
@@ -55,13 +55,11 @@ struct as_io_context {
 
 struct cfq_queue;
 struct cfq_io_context {
-        /*
-         * circular list of cfq_io_contexts belonging to a process io context
-         */
-        struct list_head list;
-        struct cfq_queue *cfqq[2];
+        struct rb_node rb_node;
         void *key;
 
+        struct cfq_queue *cfqq[2];
+
         struct io_context *ioc;
 
         unsigned long last_end_request;
@@ -72,8 +70,8 @@ struct cfq_io_context {
 
         struct list_head queue_list;
 
-        void (*dtor)(struct cfq_io_context *);
-        void (*exit)(struct cfq_io_context *);
+        void (*dtor)(struct io_context *); /* destructor */
+        void (*exit)(struct io_context *); /* called on task exit */
 };
 
 /*
@@ -94,7 +92,7 @@ struct io_context {
         int nr_batch_requests;     /* Number of requests left in the batch */
 
         struct as_io_context *aic;
-        struct cfq_io_context *cic;
+        struct rb_root cic_root;
 };
 
 void put_io_context(struct io_context *ioc);