[PATCH 0/3] deadline-iosched: performance, style and documentation changes

[PATCH 0/3] deadline-iosched: performance, style and documentation changes

[Aaron Carroll]

Hi Jens,

Patch 1 changes deadline to dispatch in a CSCAN-like manner for improved
throughput.  This fixes two performance issues, namely deadline avalanche
that occurs under high load, and FCFS-like behaviour for mixed read/write
workloads.  Benchmark results are below.

Patches 2 and 3 introduce some non-functional changes, mostly for style
and documentation.

Thanks,
  -- Aaron


-----------------------------------x8-----------------------------------

Figures quoted in KiB/s unless otherwise noted.  Disk under test is a 73GiB
15krpm Cheetah.  Host machine is a 2-way IA64 w/ 2GiB RAM.


fio 16KiB reads
-------------------------------

Load      Bandwidth      %
        New      Old
32    3585.789 3580.412  0.1
64    3657.062 3361.460  8.8
128   3844.572 2459.811  56
256   3860.864 2455.446  57
512   3896.296 2472.468  58


fio 16KiB read/write (50/50)
-------------------------------

Load      Bandwidth      %
        New      Old
32    3461.336 2630.765  32
64    3715.625 2369.822  57
128   3931.525 2375.380  66
256   3953.333 2377.132  66


fio 1MiB reads
-------------------------------

Load       Bandwidth       %
        New        Old
32    49502.789 45744.023  8.2
64    50109.827 45776.416  9.5
128   50232.672 45884.900  9.5
256   50641.255 46266.082  9.5


fio 1MiB read/write (50/50)
-------------------------------

Load       Bandwidth       %
        New        Old
32    48543.272 44557.494  8.9
64    49388.251 44597.785  11
128   49794.080 45131.637  10
256   50632.356 45777.333  11


Postmark 
-------------------------------

5 instances, 10k files, 100 dirs, 15k xacts, XFS

Old: 10.79 xact/s
New: 11.26 xact/s  (+4.2%)

[PATCH 1/3] deadline-iosched: allow non-sequential batching

[Aaron Carroll]

Deadline currently only batches sector-contiguous requests, so except
for a few circumstances (e.g. requests in a single direction), it is
essentially first come first served.  This is bad for throughput, so
change it to CSCAN, which means requests in a batch do not need to be
sequential and are issued in increasing sector order.

Signed-off-by: Aaron Carroll <aaronc@gelato.unsw.edu.au>
---
 block/deadline-iosched.c |   14 +++-----------
 1 files changed, 3 insertions(+), 11 deletions(-)

diff --git a/block/deadline-iosched.c b/block/deadline-iosched.c
index 342448c..07b80e4 100644
--- a/block/deadline-iosched.c
+++ b/block/deadline-iosched.c
@@ -258,17 +258,9 @@ static int deadline_dispatch_requests(struct request_queue *q, int force)
 	else
 		rq = dd->next_rq[READ];
 
-	if (rq) {
-		/* we have a "next request" */
-		
-		if (dd->last_sector != rq->sector)
-			/* end the batch on a non sequential request */
-			dd->batching += dd->fifo_batch;
-		
-		if (dd->batching < dd->fifo_batch)
-			/* we are still entitled to batch */
-			goto dispatch_request;
-	}
+	if (rq && dd->batching < dd->fifo_batch)
+		/* we have a next request are still entitled to batch */
+		goto dispatch_request;
 
 	/*
 	 * at this point we are not running a batch. select the appropriate
-- 
1.5.4.5

[PATCH 2/3] deadline-iosched: non-functional fixes

[Aaron Carroll]

 * convert goto to simpler while loop;
 * use rq_end_sector() instead of computing manually;
 * fix false comments;
 * remove spurious whitespace;
 * convert rq_rb_root macro to an inline function.

Signed-off-by: Aaron Carroll <aaronc@gelato.unsw.edu.au>
---
 block/deadline-iosched.c |   26 +++++++++++++-------------
 1 files changed, 13 insertions(+), 13 deletions(-)

diff --git a/block/deadline-iosched.c b/block/deadline-iosched.c
index 07b80e4..fd31117 100644
--- a/block/deadline-iosched.c
+++ b/block/deadline-iosched.c
@@ -33,7 +33,7 @@ struct deadline_data {
 	 */
 	struct rb_root sort_list[2];	
 	struct list_head fifo_list[2];
-	
+
 	/*
 	 * next in sort order. read, write or both are NULL
 	 */
@@ -53,7 +53,11 @@ struct deadline_data {
 
 static void deadline_move_request(struct deadline_data *, struct request *);
 
-#define RQ_RB_ROOT(dd, rq)	(&(dd)->sort_list[rq_data_dir((rq))])
+static inline struct rb_root *
+deadline_rb_root(struct deadline_data *dd, struct request *rq)
+{
+	return &dd->sort_list[rq_data_dir(rq)];
+}
 
 /*
  * get the request after `rq' in sector-sorted order
@@ -72,15 +76,11 @@ deadline_latter_request(struct request *rq)
 static void
 deadline_add_rq_rb(struct deadline_data *dd, struct request *rq)
 {
-	struct rb_root *root = RQ_RB_ROOT(dd, rq);
+	struct rb_root *root = deadline_rb_root(dd, rq);
 	struct request *__alias;
 
-retry:
-	__alias = elv_rb_add(root, rq);
-	if (unlikely(__alias)) {
+	while (unlikely(__alias = elv_rb_add(root, rq)))
 		deadline_move_request(dd, __alias);
-		goto retry;
-	}
 }
 
 static inline void
@@ -91,7 +91,7 @@ deadline_del_rq_rb(struct deadline_data *dd, struct request *rq)
 	if (dd->next_rq[data_dir] == rq)
 		dd->next_rq[data_dir] = deadline_latter_request(rq);
 
-	elv_rb_del(RQ_RB_ROOT(dd, rq), rq);
+	elv_rb_del(deadline_rb_root(dd, rq), rq);
 }
 
 /*
@@ -106,7 +106,7 @@ deadline_add_request(struct request_queue *q, struct request *rq)
 	deadline_add_rq_rb(dd, rq);
 
 	/*
-	 * set expire time (only used for reads) and add to fifo list
+	 * set expire time and add to fifo list
 	 */
 	rq_set_fifo_time(rq, jiffies + dd->fifo_expire[data_dir]);
 	list_add_tail(&rq->queuelist, &dd->fifo_list[data_dir]);
@@ -162,7 +162,7 @@ static void deadline_merged_request(struct request_queue *q,
 	 * if the merge was a front merge, we need to reposition request
 	 */
 	if (type == ELEVATOR_FRONT_MERGE) {
-		elv_rb_del(RQ_RB_ROOT(dd, req), req);
+		elv_rb_del(deadline_rb_root(dd, req), req);
 		deadline_add_rq_rb(dd, req);
 	}
 }
@@ -212,7 +212,7 @@ deadline_move_request(struct deadline_data *dd, struct request *rq)
 	dd->next_rq[WRITE] = NULL;
 	dd->next_rq[data_dir] = deadline_latter_request(rq);
 
-	dd->last_sector = rq->sector + rq->nr_sectors;
+	dd->last_sector = rq_end_sector(rq);
 
 	/*
 	 * take it off the sort and fifo list, move
@@ -222,7 +222,7 @@ deadline_move_request(struct deadline_data *dd, struct request *rq)
 }
 
 /*
- * deadline_check_fifo returns 0 if there are no expired reads on the fifo,
+ * deadline_check_fifo returns 0 if there are no expired requests on the fifo,
  * 1 otherwise. Requires !list_empty(&dd->fifo_list[data_dir])
  */
 static inline int deadline_check_fifo(struct deadline_data *dd, int ddir)
-- 
1.5.4.5

[PATCH 3/3] block: update documentation for deadline fifo_batch tunable

[Aaron Carroll]

Update the description of fifo_batch to match the current implementation,
and include a description of how to tune it.

Signed-off-by: Aaron Carroll <aaronc@gelato.unsw.edu.au>
---
 Documentation/block/deadline-iosched.txt |   14 ++++++++++----
 1 files changed, 10 insertions(+), 4 deletions(-)

diff --git a/Documentation/block/deadline-iosched.txt b/Documentation/block/deadline-iosched.txt
index c23cab1..7257676 100644
--- a/Documentation/block/deadline-iosched.txt
+++ b/Documentation/block/deadline-iosched.txt
@@ -30,12 +30,18 @@ write_expire	(in ms)
 Similar to read_expire mentioned above, but for writes.
 
 
-fifo_batch
+fifo_batch	(number of requests)
 ----------
 
-When a read request expires its deadline, we must move some requests from
-the sorted io scheduler list to the block device dispatch queue. fifo_batch
-controls how many requests we move.
+Requests are grouped into ``batches'' of a particular data direction (read or
+write) which are serviced in increasing sector order.  To limit extra seeking,
+deadline expiries are only checked between batches.  fifo_batch controls the
+maximum number of requests per batch.
+
+This parameter tunes the balance between per-request latency and aggregate
+throughput.  When low latency is the primary concern, smaller is better (where
+a value of 1 yields first-come first-served behaviour).  Increasing fifo_batch
+generally improves throughput, at the cost of latency variation.
 
 
 writes_starved	(number of dispatches)
-- 
1.5.4.5

Re: [PATCH 0/3] deadline-iosched: performance, style and documentation changes

[Jens Axboe]

On Thu, Aug 14 2008, Aaron Carroll wrote:
> 
> Hi Jens,
> 
> Patch 1 changes deadline to dispatch in a CSCAN-like manner for improved
> throughput.  This fixes two performance issues, namely deadline avalanche
> that occurs under high load, and FCFS-like behaviour for mixed read/write
> workloads.  Benchmark results are below.
> 
> Patches 2 and 3 introduce some non-functional changes, mostly for style
> and documentation.

Looks good, thanks Aaron!

-- 
Jens Axboe