[PATCH 0/7] [RFC] iosched: make a difference between read/readahead requests

[PATCH 0/7] [RFC] iosched: make a difference between read/readahead requests

[Fengguang Wu]

Hi Jens,

This patchset does two jobs:
	1) do io schedule differently on READ/READA requests.
		- to help improve I/O latency and throughput
	2) do notification/action on READA => READ events
		- to make the elevators better informed
		- to prevent the priority inversion problem
		- also brings some CPU overheads(*)

(*) Most overheads should be in functions deadline_kick_page() and
deadline_add_drq_fifo(). Optimizations should be possible.

The features are required when one is doing a lot of fadvise(WILLNEED) calls,
and do not want to interfere with normal I/Os. Servers that serve lots of
concurrent clients would benifit a lot, too.

The patches come in two groups:

1) explicitly schedule READA requests
Note: currently only the deadline elevator is touched.

[PATCH 1/7] iosched: introduce WRITEA                                                  
[PATCH 2/7] iosched: introduce parameter deadline.reada_expire                         
[PATCH 3/7] iosched: introduce deadline_add_drq_fifo()                                 
[PATCH 4/7] iosched: submit READA requests on possible readahead code path             

2) notify/act on pending reads
Naming issue: how about pending_read/need_page/... for kick_page?

[PATCH 5/7] iosched: introduce elv_kick_page()                                         
[PATCH 6/7] iosched: run elv_kick_page() on sync read                                  
[PATCH 7/7] iosched: introduce deadline_kick_page()                                    

Any comments are welcome, thanks.

Fengguang Wu
--
Dept. Automation                University of Science and Technology of China

[PATCH 1/7] iosched: introduce WRITEA

[Fengguang Wu]

[-- Attachment #1: iosched-reada-redef.patch --]
[-- Type: text/plain, Size: 911 bytes --]

Introduce WRITEA as 3, and redefine SWRITE as 5.

I'm not sure if WRITEA will ever be used, though it would be better to
redefine SWRITE to avoid possible conflict with BIO_RW_AHEAD.

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


--- linux-2.6.17-rc6-mm2.orig/include/linux/fs.h
+++ linux-2.6.17-rc6-mm2/include/linux/fs.h
@@ -74,8 +74,9 @@ extern int dir_notify_enable;
 #define READ 0
 #define WRITE 1
 #define READA 2		/* read-ahead  - don't block if no resources */
-#define SWRITE 3	/* for ll_rw_block() - wait for buffer lock */
+#define WRITEA 3	/* write-ahead - don't block if no resources */
 #define SPECIAL 4	/* For non-blockdevice requests in request queue */
+#define SWRITE 5	/* for ll_rw_block() - wait for buffer lock */
 #define READ_SYNC	(READ | (1 << BIO_RW_SYNC))
 #define WRITE_SYNC	(WRITE | (1 << BIO_RW_SYNC))
 #define WRITE_BARRIER	((1 << BIO_RW) | (1 << BIO_RW_BARRIER))

--

[PATCH 2/7] iosched: introduce parameter deadline.reada_expire

[Fengguang Wu]

[-- Attachment #1: iosched-reada-deadline.patch --]
[-- Type: text/plain, Size: 2760 bytes --]

Introduce parameter reada_expire to the deadline elevator.

It avoids readahead requests contending with read requests,
and helps improve latency/throughput when there's many concurrent readers.

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


--- linux-2.6.17-rc6-mm2.orig/block/deadline-iosched.c
+++ linux-2.6.17-rc6-mm2/block/deadline-iosched.c
@@ -19,7 +19,8 @@
 /*
  * See Documentation/block/deadline-iosched.txt
  */
-static const int read_expire = HZ / 2;  /* max time before a read is submitted. */
+static const int read_expire = HZ / 2;	/* max time before an _impending_ read is submitted. */
+static const int reada_expire = 60 * HZ;/* max time before a read-ahead is submitted. */
 static const int write_expire = 5 * HZ; /* ditto for writes, these limits are SOFT! */
 static const int writes_starved = 2;    /* max times reads can starve a write */
 static const int fifo_batch = 16;       /* # of sequential requests treated as one
@@ -56,7 +57,7 @@ struct deadline_data {
 	/*
 	 * settings that change how the i/o scheduler behaves
 	 */
-	int fifo_expire[2];
+	int fifo_expire[4];
 	int fifo_batch;
 	int writes_starved;
 	int front_merges;
@@ -711,7 +712,9 @@ static void *deadline_init_queue(request
 	dd->sort_list[READ] = RB_ROOT;
 	dd->sort_list[WRITE] = RB_ROOT;
 	dd->fifo_expire[READ] = read_expire;
+	dd->fifo_expire[READA] = reada_expire;
 	dd->fifo_expire[WRITE] = write_expire;
+	dd->fifo_expire[WRITEA] = write_expire;
 	dd->writes_starved = writes_starved;
 	dd->front_merges = 1;
 	dd->fifo_batch = fifo_batch;
@@ -780,6 +783,7 @@ static ssize_t __FUNC(elevator_t *e, cha
 	return deadline_var_show(__data, (page));			\
 }
 SHOW_FUNCTION(deadline_read_expire_show, dd->fifo_expire[READ], 1);
+SHOW_FUNCTION(deadline_reada_expire_show, dd->fifo_expire[READA], 1);
 SHOW_FUNCTION(deadline_write_expire_show, dd->fifo_expire[WRITE], 1);
 SHOW_FUNCTION(deadline_writes_starved_show, dd->writes_starved, 0);
 SHOW_FUNCTION(deadline_front_merges_show, dd->front_merges, 0);
@@ -803,6 +807,7 @@ static ssize_t __FUNC(elevator_t *e, con
 	return ret;							\
 }
 STORE_FUNCTION(deadline_read_expire_store, &dd->fifo_expire[READ], 0, INT_MAX, 1);
+STORE_FUNCTION(deadline_reada_expire_store, &dd->fifo_expire[READA], 0, INT_MAX, 1);
 STORE_FUNCTION(deadline_write_expire_store, &dd->fifo_expire[WRITE], 0, INT_MAX, 1);
 STORE_FUNCTION(deadline_writes_starved_store, &dd->writes_starved, INT_MIN, INT_MAX, 0);
 STORE_FUNCTION(deadline_front_merges_store, &dd->front_merges, 0, 1, 0);
@@ -815,6 +820,7 @@ STORE_FUNCTION(deadline_fifo_batch_store
 
 static struct elv_fs_entry deadline_attrs[] = {
 	DD_ATTR(read_expire),
+	DD_ATTR(reada_expire),
 	DD_ATTR(write_expire),
 	DD_ATTR(writes_starved),
 	DD_ATTR(front_merges),

--

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

[Fengguang Wu]

[-- 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])

--

[PATCH 6/7] iosched: run elv_kick_page() on sync read

[Fengguang Wu]

[-- Attachment #1: iosched-kick-page-on-sync-read.patch --]
[-- Type: text/plain, Size: 939 bytes --]

Call elv_kick_page() to notify the elevator of a pending read.

Requests of priority IOPRIO_CLASS_IDLE are ignored.

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


--- linux-2.6.17-rc5-mm3.orig/block/ll_rw_blk.c
+++ linux-2.6.17-rc5-mm3/block/ll_rw_blk.c
@@ -1619,6 +1619,9 @@ static void blk_backing_dev_unplug(struc
 {
 	request_queue_t *q = bdi->unplug_io_data;
 
+	if (IOPRIO_PRIO_CLASS(current->ioprio) != IOPRIO_CLASS_IDLE)
+		elv_kick_page(q, page);
+
 	/*
 	 * devices don't necessarily have an ->unplug_fn defined
 	 */
--- linux-2.6.17-rc5-mm3.orig/fs/buffer.c
+++ linux-2.6.17-rc5-mm3/fs/buffer.c
@@ -63,8 +63,9 @@ static int sync_buffer(void *word)
 
 	smp_mb();
 	bd = bh->b_bdev;
-	if (bd)
-		blk_run_address_space(bd->bd_inode->i_mapping);
+	if (bd && bd->bd_inode && bd->bd_inode->i_mapping)
+		blk_run_backing_dev(bd->bd_inode->i_mapping->backing_dev_info,
+					bh->b_page);
 	io_schedule();
 	return 0;
 }

--

[PATCH 0/7] [RFC] iosched: make a difference between read/readahead requests

[Fengguang Wu]

Hi Jens,

This patchset does two jobs:
	1) do io schedule differently on READ/READA requests.
		- to help improve I/O latency and throughput
	2) do notification/action on READA => READ events
		- to make the elevators better informed
		- to prevent the priority inversion problem
		- also brings some CPU overheads*
(*) I'm not able to provide numbers at the moment.
    Our server is not up for testing these days. But sure will for the next time.


The patches come in two groups:

1) explicitly schedule READA requests
Note: currently only the deadline elevator is touched.

[PATCH 1/7] iosched: introduce WRITEA                                                  
[PATCH 2/7] iosched: introduce parameter deadline.reada_expire                         
[PATCH 3/7] iosched: introduce deadline_add_drq_fifo()                                 
[PATCH 4/7] iosched: submit READA requests on possible readahead code path             

2) notify/act on pending reads
Naming issue: how about pending_read/need_page/... for kick_page?

[PATCH 5/7] iosched: introduce elv_kick_page()                                         
[PATCH 6/7] iosched: run elv_kick_page() on sync read                                  
[PATCH 7/7] iosched: introduce deadline_kick_page()                                    

Most overheads should be in functions deadline_kick_page() and
deadline_add_drq_fifo(). I'll explore the details later.

Any comments are welcome, thanks.

Fengguang Wu
--
Dept. Automation                University of Science and Technology of China

[PATCH 0/7] [RFC] iosched: make a difference between read/readahead requests

[Fengguang Wu]

Hi Jens,

This patchset does two jobs:
	1) do io schedule differently on READ/READA requests.
		- to help improve I/O latency and throughput
	2) do notification/action on READA => READ events
		- to make the elevators better informed
		- to prevent the priority inversion problem
		- also brings some CPU overheads*
(*) I'm not able to provide the numbers at the moment.
    But sure for the next time.


The patches come in two groups:

1) explicitly schedule READA requests
Note: currently only the deadline elevator is touched.

[PATCH 1/7] iosched: introduce WRITEA                                                  
[PATCH 2/7] iosched: introduce parameter deadline.reada_expire                         
[PATCH 3/7] iosched: introduce deadline_add_drq_fifo()                                 
[PATCH 4/7] iosched: submit READA requests on possible readahead code path             

2) notify/act on pending reads
Naming issue: how about pending_read/need_page/... for kick_page?

[PATCH 5/7] iosched: introduce elv_kick_page()                                         
[PATCH 6/7] iosched: run elv_kick_page() on sync read                                  
[PATCH 7/7] iosched: introduce deadline_kick_page()                                    

Most overheads should be in functions deadline_kick_page() and
deadline_add_drq_fifo(). I'll explore the details later.

Any comments are welcome, thanks.

Fengguang Wu
--
Dept. Automation                University of Science and Technology of China