[PATCH 3/7] iosched: introduce deadline_add_drq_fifo()

[Fengguang Wu <wfg@mail.ustc.edu.cn>]

[-- Attachment #1: iosched-deadline-fifo-enqueue.patch --]
[-- Type: text/plain, Size: 3091 bytes --]

deadline_rq.fifo is now a queue sorted by request expire time.
New requests can be inserted _anywhere_ into deadline_rq.fifo.

Introduce a new function deadline_add_drq_fifo() to do the work.

Signed-off-by: Wu Fengguang <wfg@mail.ustc.edu.cn>
---


 block/deadline-iosched.c |   33 ++++++++++++++++++++++++---------
 include/linux/blkdev.h   |    1 +
 2 files changed, 25 insertions(+), 9 deletions(-)

--- linux-2.6.17-rc6-mm2.orig/include/linux/blkdev.h
+++ linux-2.6.17-rc6-mm2/include/linux/blkdev.h
@@ -516,6 +516,7 @@ enum {
 #define list_entry_rq(ptr)	list_entry((ptr), struct request, queuelist)
 
 #define rq_data_dir(rq)		((rq)->flags & 1)
+#define rq_data_rwa(rq)		((rq)->flags & 3)
 
 static inline int blk_queue_full(struct request_queue *q, int rw)
 {
--- linux-2.6.17-rc6-mm2.orig/block/deadline-iosched.c
+++ linux-2.6.17-rc6-mm2/block/deadline-iosched.c
@@ -30,6 +30,7 @@ static const int deadline_hash_shift = 5
 #define DL_HASH_FN(sec)		(hash_long(DL_HASH_BLOCK((sec)), deadline_hash_shift))
 #define DL_HASH_ENTRIES		(1 << deadline_hash_shift)
 #define rq_hash_key(rq)		((rq)->sector + (rq)->nr_sectors)
+#define list_entry_fifo(ptr)	list_entry((ptr), struct deadline_rq, fifo)
 #define ON_HASH(drq)		(!hlist_unhashed(&(drq)->hash))
 
 struct deadline_data {
@@ -264,6 +265,41 @@ deadline_find_first_drq(struct deadline_
 }
 
 /*
+ * set expire time (only used for reads) and add to fifo list
+ */
+static void
+deadline_add_drq_fifo(struct deadline_data *dd, struct request *rq)
+{
+	const int data_dir = rq_data_dir(rq);
+	struct deadline_rq *drq = RQ_DATA(rq);
+	struct list_head *ip; /* insert before me */
+	int expire;
+
+	expire = dd->fifo_expire[rq_data_rwa(rq)];
+	drq->expires = jiffies + expire;
+
+	/*
+	 * Scan forward/backward and insert.
+	 */
+	if (expire > dd->fifo_expire[READ]) {
+		list_for_each(ip, &dd->fifo_list[data_dir]) {
+			if (time_before(drq->expires,
+					list_entry_fifo(ip)->expires))
+				break;
+		}
+		list_add_tail(&drq->fifo, ip);
+	} else {
+		list_for_each_prev(ip, &dd->fifo_list[data_dir]) {
+			if (!time_before(drq->expires,
+					list_entry_fifo(ip)->expires))
+				break;
+		}
+		list_add(&drq->fifo, ip);
+	}
+
+}
+
+/*
  * add drq to rbtree and fifo
  */
 static void
@@ -272,14 +308,8 @@ deadline_add_request(struct request_queu
 	struct deadline_data *dd = q->elevator->elevator_data;
 	struct deadline_rq *drq = RQ_DATA(rq);
 
-	const int data_dir = rq_data_dir(drq->request);
-
 	deadline_add_drq_rb(dd, drq);
-	/*
-	 * set expire time (only used for reads) and add to fifo list
-	 */
-	drq->expires = jiffies + dd->fifo_expire[data_dir];
-	list_add_tail(&drq->fifo, &dd->fifo_list[data_dir]);
+	deadline_add_drq_fifo(dd, rq);
 
 	if (rq_mergeable(rq))
 		deadline_add_drq_hash(dd, drq);
@@ -439,8 +469,6 @@ deadline_move_request(struct deadline_da
 	deadline_move_to_dispatch(dd, drq);
 }
 
-#define list_entry_fifo(ptr)	list_entry((ptr), struct deadline_rq, fifo)
-
 /*
  * deadline_check_fifo returns 0 if there are no expired reads on the fifo,
  * 1 otherwise. Requires !list_empty(&dd->fifo_list[data_dir])

--