[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>
diff --git a/include/linux/blkdev.h b/include/linux/blkdev.h
index c179966..ed0ffa6 100644
--- a/include/linux/blkdev.h
+++ b/include/linux/blkdev.h
@@ -55,13 +55,11 @@
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 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 @@
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);