[linux-yocto] [PATCH 3/3] block, bfq: add Early Queue Merge (EQM) to BFQ-v7r5 for 3.14.0

2014-08-27 Thread jianchuan.wang
From: Mauro Andreolini mauro.andreol...@unimore.it

Original patch taken from: 
http://algo.ing.unimo.it/people/paolo/disk_sched/patches/3.14.0-v7r5

A set of processes may happen  to  perform interleaved reads, i.e.,requests
whose union would give rise to a  sequential read  pattern.  There are two
typical  cases: in the first  case,   processes  read  fixed-size chunks of
data at a fixed distance from each other, while in the second case processes
may read variable-size chunks at  variable distances. The latter case occurs
for  example with  QEMU, which  splits the  I/O generated  by the  guest into
multiple chunks,  and lets these chunks  be served by a  pool of cooperating
processes,  iteratively  assigning  the  next  chunk of  I/O  to  the first
available  process. CFQ  uses actual  queue merging  for the  first type of
rocesses, whereas it  uses preemption to get a sequential  read pattern out
of the read requests  performed by the second type of  processes. In the end
it uses  two different  mechanisms to  achieve the  same goal: boosting the
throughput with interleaved I/O.

This patch introduces  Early Queue Merge (EQM), a unified mechanism to get a
sequential  read pattern  with both  types of  processes. The  main idea is
checking newly arrived requests against the next request of the active queue
both in case of actual request insert and in case of request merge. By doing
so, both the types of processes can be handled by just merging their queues.
EQM is  then simpler and  more compact than the  pair of mechanisms used in
CFQ.

Finally, EQM  also preserves the  typical low-latency properties of BFQ, by
properly restoring the weight-raising state of  a queue when it gets back to
a non-merged state.

Signed-off-by: Mauro Andreolini mauro.andreol...@unimore.it
Signed-off-by: Arianna Avanzini avanzini.aria...@gmail.com
Signed-off-by: Paolo Valente paolo.vale...@unimore.it
Signed-off-by: Jianchuan Wang jianchuan.w...@windriver.com
---
 block/bfq-iosched.c | 736 
 block/bfq-sched.c   |  28 --
 block/bfq.h |  46 +++-
 3 files changed, 556 insertions(+), 254 deletions(-)

diff --git a/block/bfq-iosched.c b/block/bfq-iosched.c
index 0cbb182..452f477 100644
--- a/block/bfq-iosched.c
+++ b/block/bfq-iosched.c
@@ -571,6 +571,57 @@ static inline unsigned int bfq_wr_duration(struct bfq_data 
*bfqd)
return dur;
 }
 
+static inline unsigned
+bfq_bfqq_cooperations(struct bfq_queue *bfqq)
+{
+   return bfqq-bic ? bfqq-bic-cooperations : 0;
+}
+
+static inline void
+bfq_bfqq_resume_state(struct bfq_queue *bfqq, struct bfq_io_cq *bic)
+{
+   if (bic-saved_idle_window)
+   bfq_mark_bfqq_idle_window(bfqq);
+   else
+   bfq_clear_bfqq_idle_window(bfqq);
+   if (bic-saved_IO_bound)
+   bfq_mark_bfqq_IO_bound(bfqq);
+   else
+   bfq_clear_bfqq_IO_bound(bfqq);
+   if (bic-wr_time_left  bfqq-bfqd-low_latency 
+   bic-cooperations  bfqq-bfqd-bfq_coop_thresh) {
+   /*
+* Start a weight raising period with the duration given by
+* the raising_time_left snapshot.
+*/
+   if (bfq_bfqq_busy(bfqq))
+   bfqq-bfqd-wr_busy_queues++;
+   bfqq-wr_coeff = bfqq-bfqd-bfq_wr_coeff;
+   bfqq-wr_cur_max_time = bic-wr_time_left;
+   bfqq-last_wr_start_finish = jiffies;
+   bfqq-entity.ioprio_changed = 1;
+   }
+   /*
+* Clear wr_time_left to prevent bfq_bfqq_save_state() from
+* getting confused about the queue's need of a weight-raising
+* period.
+*/
+   bic-wr_time_left = 0;
+}
+
+/*
+ * Must be called with the queue_lock held.
+ */
+static int bfqq_process_refs(struct bfq_queue *bfqq)
+{
+   int process_refs, io_refs;
+
+   io_refs = bfqq-allocated[READ] + bfqq-allocated[WRITE];
+   process_refs = atomic_read(bfqq-ref) - io_refs - bfqq-entity.on_st;
+   BUG_ON(process_refs  0);
+   return process_refs;
+}
+
 static void bfq_add_request(struct request *rq)
 {
struct bfq_queue *bfqq = RQ_BFQQ(rq);
@@ -602,8 +653,11 @@ static void bfq_add_request(struct request *rq)
 
if (!bfq_bfqq_busy(bfqq)) {
int soft_rt = bfqd-bfq_wr_max_softrt_rate  0 
+   bfq_bfqq_cooperations(bfqq)  bfqd-bfq_coop_thresh 
time_is_before_jiffies(bfqq-soft_rt_next_start);
-   idle_for_long_time = time_is_before_jiffies(
+   idle_for_long_time = bfq_bfqq_cooperations(bfqq) 
+bfqd-bfq_coop_thresh 
+   time_is_before_jiffies(
bfqq-budget_timeout +
bfqd-bfq_wr_min_idle_time);
entity-budget = max_t(unsigned long, bfqq-max_budget,
@@ -624,11 +678,20 @@ static void bfq_add_request(struct request *rq)

[linux-yocto] [PATCH 3/3] block, bfq: add Early Queue Merge (EQM) to BFQ-v7r5 for 3.14.0

2014-08-26 Thread jianchuan.wang
From: Mauro Andreolini mauro.andreol...@unimore.it

Original patch taken from: 
http://algo.ing.unimo.it/people/paolo/disk_sched/patches/3.14.0-v7r5

A set of processes may happen  to  perform interleaved reads, i.e.,requests
whose union would give rise to a  sequential read  pattern.  There are two
typical  cases: in the first  case,   processes  read  fixed-size chunks of
data at a fixed distance from each other, while in the second case processes
may read variable-size chunks at  variable distances. The latter case occurs
for  example with  QEMU, which  splits the  I/O generated  by the  guest into
multiple chunks,  and lets these chunks  be served by a  pool of cooperating
processes,  iteratively  assigning  the  next  chunk of  I/O  to  the first
available  process. CFQ  uses actual  queue merging  for the  first type of
rocesses, whereas it  uses preemption to get a sequential  read pattern out
of the read requests  performed by the second type of  processes. In the end
it uses  two different  mechanisms to  achieve the  same goal: boosting the
throughput with interleaved I/O.

This patch introduces  Early Queue Merge (EQM), a unified mechanism to get a
sequential  read pattern  with both  types of  processes. The  main idea is
checking newly arrived requests against the next request of the active queue
both in case of actual request insert and in case of request merge. By doing
so, both the types of processes can be handled by just merging their queues.
EQM is  then simpler and  more compact than the  pair of mechanisms used in
CFQ.

Finally, EQM  also preserves the  typical low-latency properties of BFQ, by
properly restoring the weight-raising state of  a queue when it gets back to
a non-merged state.

Signed-off-by: Mauro Andreolini mauro.andreol...@unimore.it
Signed-off-by: Arianna Avanzini avanzini.aria...@gmail.com
Signed-off-by: Paolo Valente paolo.vale...@unimore.it
Signed-off-by: Jianchuan Wang jianchuan.w...@windriver.com
---
 block/bfq-iosched.c | 736 
 block/bfq-sched.c   |  28 --
 block/bfq.h |  46 +++-
 3 files changed, 556 insertions(+), 254 deletions(-)

diff --git a/block/bfq-iosched.c b/block/bfq-iosched.c
index 0cbb182..452f477 100644
--- a/block/bfq-iosched.c
+++ b/block/bfq-iosched.c
@@ -571,6 +571,57 @@ static inline unsigned int bfq_wr_duration(struct bfq_data 
*bfqd)
return dur;
 }
 
+static inline unsigned
+bfq_bfqq_cooperations(struct bfq_queue *bfqq)
+{
+   return bfqq-bic ? bfqq-bic-cooperations : 0;
+}
+
+static inline void
+bfq_bfqq_resume_state(struct bfq_queue *bfqq, struct bfq_io_cq *bic)
+{
+   if (bic-saved_idle_window)
+   bfq_mark_bfqq_idle_window(bfqq);
+   else
+   bfq_clear_bfqq_idle_window(bfqq);
+   if (bic-saved_IO_bound)
+   bfq_mark_bfqq_IO_bound(bfqq);
+   else
+   bfq_clear_bfqq_IO_bound(bfqq);
+   if (bic-wr_time_left  bfqq-bfqd-low_latency 
+   bic-cooperations  bfqq-bfqd-bfq_coop_thresh) {
+   /*
+* Start a weight raising period with the duration given by
+* the raising_time_left snapshot.
+*/
+   if (bfq_bfqq_busy(bfqq))
+   bfqq-bfqd-wr_busy_queues++;
+   bfqq-wr_coeff = bfqq-bfqd-bfq_wr_coeff;
+   bfqq-wr_cur_max_time = bic-wr_time_left;
+   bfqq-last_wr_start_finish = jiffies;
+   bfqq-entity.ioprio_changed = 1;
+   }
+   /*
+* Clear wr_time_left to prevent bfq_bfqq_save_state() from
+* getting confused about the queue's need of a weight-raising
+* period.
+*/
+   bic-wr_time_left = 0;
+}
+
+/*
+ * Must be called with the queue_lock held.
+ */
+static int bfqq_process_refs(struct bfq_queue *bfqq)
+{
+   int process_refs, io_refs;
+
+   io_refs = bfqq-allocated[READ] + bfqq-allocated[WRITE];
+   process_refs = atomic_read(bfqq-ref) - io_refs - bfqq-entity.on_st;
+   BUG_ON(process_refs  0);
+   return process_refs;
+}
+
 static void bfq_add_request(struct request *rq)
 {
struct bfq_queue *bfqq = RQ_BFQQ(rq);
@@ -602,8 +653,11 @@ static void bfq_add_request(struct request *rq)
 
if (!bfq_bfqq_busy(bfqq)) {
int soft_rt = bfqd-bfq_wr_max_softrt_rate  0 
+   bfq_bfqq_cooperations(bfqq)  bfqd-bfq_coop_thresh 
time_is_before_jiffies(bfqq-soft_rt_next_start);
-   idle_for_long_time = time_is_before_jiffies(
+   idle_for_long_time = bfq_bfqq_cooperations(bfqq) 
+bfqd-bfq_coop_thresh 
+   time_is_before_jiffies(
bfqq-budget_timeout +
bfqd-bfq_wr_min_idle_time);
entity-budget = max_t(unsigned long, bfqq-max_budget,
@@ -624,11 +678,20 @@ static void bfq_add_request(struct request *rq)