[RFC PATCH 00/15] Use vdisktime based scheduling logic for cfq queues

[RFC PATCH 00/15] Use vdisktime based scheduling logic for cfq queues

[Vivek Goyal]

Hi,

This patches series primarily does few things.

- Intial few patches are just renaming and small cleanups so that
  reading code is easier. (Patches 1-5)

- A patch to print cfqq type (sync-noidle) in blktrace message. (Patch 6)

- Then patches to use vdisktime based scheduling logic for cfq queues.
  This is very similar to cfq group scheduling logic.

Why to change scheduling algorithm
==================================
Currently we use two scheduling algorithms at two different layers. 
vdisktime based algorithm for groups and round robin for cfq queues.
Now we are planning to do more development in cfqq so that it can
handle group hierarchies. And I think before we do that we first need
to change the code so that both queues and groups are treated same way
when it comes to scheduling. Otherwise the whole thing is a mess.

This patch series does not merge the queue and group scheduling code.
It just tries to make these similar enough so that merging of code
becomes easier in future patches.

What's the functionality impact
===============================
I don't expect much to change except that service differentiation
among various prio levels might vary a bit. In did my testing on 
a SATA disk and lauched 8 processes with prio 0-7, all doing 
sequential reads. Here are the results.

		0	1	3	4	4	5	6	7
vanilla(MB/s)  14.8     10.4    7.6     6.5     4.4     3.7     3.3     1.5
patched(MB/s)  15.0	10.7	7.3	6.6	4.8	3.4	2.2	1.6

Thanks
Vivek

Vivek Goyal (15):
  cfq-iosched: Properly name all references to IO class
  cfq-iosched: More renaming to better represent wl_class and wl_type
  cfq-iosched: Rename "service_tree" to "st"
  cfq-iosched: Rename few functions related to selecting workload
  cfq-iosched: Get rid of unnecessary local variable
  cfq-iosched: Print sync-noidle information in blktrace messages
  cfq-iosced: Do the round robin selection of workload type
  cfq-iosched: Make cfq_scale_slice() usable for both queues and groups
  cfq-iosched: make new_cfqq variable bool
  cfq-get-rid-of-slice-offset-and-always-put-new-queue-at-the-end-2
  cfq-iosched: Remove residual slice logic
  cfq-iosched: put cooperating queue at the front of service tree
  cfq-iosched: Use same scheduling algorithm for groups and queues
  cfq-iosched: Wait for queue to get busy even if this is not last
    queue in group
  cfq-ioschd: Give boost to higher prio/weight queues

 block/cfq-iosched.c |  567 +++++++++++++++++++++++++++++----------------------
 1 files changed, 324 insertions(+), 243 deletions(-)

-- 
1.7.7.6

[PATCH 01/15] cfq-iosched: Properly name all references to IO class

[Vivek Goyal]

Currently CFQ has three IO classes, RT, BE and IDLE. At many a places we
are calling workloads belonging to these classes as "prio". This gets
very confusing as one starts to associate it with ioprio.

So this patch just does bunch of renaming so that reading code becomes
easier. All reference to RT, BE and IDLE workload are done using keyword
"class" and all references to subclass, SYNC, SYNC-IDLE, ASYNC are made
using keyword "type".

This makes me feel much better while I am reading the code. There is no
functionality change due to this patch.

Signed-off-by: Vivek Goyal <vgoyal@redhat.com>
---
 block/cfq-iosched.c |   67 ++++++++++++++++++++++++++-------------------------
 1 files changed, 34 insertions(+), 33 deletions(-)

diff --git a/block/cfq-iosched.c b/block/cfq-iosched.c
index fb52df9..9d44394 100644
--- a/block/cfq-iosched.c
+++ b/block/cfq-iosched.c
@@ -155,7 +155,7 @@ struct cfq_queue {
  * First index in the service_trees.
  * IDLE is handled separately, so it has negative index
  */
-enum wl_prio_t {
+enum wl_class_t {
 	BE_WORKLOAD = 0,
 	RT_WORKLOAD = 1,
 	IDLE_WORKLOAD = 2,
@@ -250,7 +250,7 @@ struct cfq_group {
 
 	unsigned long saved_workload_slice;
 	enum wl_type_t saved_workload;
-	enum wl_prio_t saved_serving_prio;
+	enum wl_class_t saved_serving_class;
 
 	/* number of requests that are on the dispatch list or inside driver */
 	int dispatched;
@@ -280,7 +280,7 @@ struct cfq_data {
 	/*
 	 * The priority currently being served
 	 */
-	enum wl_prio_t serving_prio;
+	enum wl_class_t serving_class;
 	enum wl_type_t serving_type;
 	unsigned long workload_expires;
 	struct cfq_group *serving_group;
@@ -354,16 +354,16 @@ struct cfq_data {
 static struct cfq_group *cfq_get_next_cfqg(struct cfq_data *cfqd);
 
 static struct cfq_rb_root *service_tree_for(struct cfq_group *cfqg,
-					    enum wl_prio_t prio,
+					    enum wl_class_t class,
 					    enum wl_type_t type)
 {
 	if (!cfqg)
 		return NULL;
 
-	if (prio == IDLE_WORKLOAD)
+	if (class == IDLE_WORKLOAD)
 		return &cfqg->service_tree_idle;
 
-	return &cfqg->service_trees[prio][type];
+	return &cfqg->service_trees[class][type];
 }
 
 enum cfqq_state_flags {
@@ -732,7 +732,7 @@ static inline bool iops_mode(struct cfq_data *cfqd)
 		return false;
 }
 
-static inline enum wl_prio_t cfqq_prio(struct cfq_queue *cfqq)
+static inline enum wl_class_t cfqq_class(struct cfq_queue *cfqq)
 {
 	if (cfq_class_idle(cfqq))
 		return IDLE_WORKLOAD;
@@ -751,16 +751,16 @@ static enum wl_type_t cfqq_type(struct cfq_queue *cfqq)
 	return SYNC_WORKLOAD;
 }
 
-static inline int cfq_group_busy_queues_wl(enum wl_prio_t wl,
+static inline int cfq_group_busy_queues_wl(enum wl_class_t wl_class,
 					struct cfq_data *cfqd,
 					struct cfq_group *cfqg)
 {
-	if (wl == IDLE_WORKLOAD)
+	if (wl_class == IDLE_WORKLOAD)
 		return cfqg->service_tree_idle.count;
 
-	return cfqg->service_trees[wl][ASYNC_WORKLOAD].count
-		+ cfqg->service_trees[wl][SYNC_NOIDLE_WORKLOAD].count
-		+ cfqg->service_trees[wl][SYNC_WORKLOAD].count;
+	return cfqg->service_trees[wl_class][ASYNC_WORKLOAD].count
+		+ cfqg->service_trees[wl_class][SYNC_NOIDLE_WORKLOAD].count
+		+ cfqg->service_trees[wl_class][SYNC_WORKLOAD].count;
 }
 
 static inline int cfqg_busy_async_queues(struct cfq_data *cfqd,
@@ -1304,7 +1304,7 @@ static void cfq_group_served(struct cfq_data *cfqd, struct cfq_group *cfqg,
 		cfqg->saved_workload_slice = cfqd->workload_expires
 						- jiffies;
 		cfqg->saved_workload = cfqd->serving_type;
-		cfqg->saved_serving_prio = cfqd->serving_prio;
+		cfqg->saved_serving_class = cfqd->serving_class;
 	} else
 		cfqg->saved_workload_slice = 0;
 
@@ -1616,7 +1616,7 @@ static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
 	int left;
 	int new_cfqq = 1;
 
-	service_tree = service_tree_for(cfqq->cfqg, cfqq_prio(cfqq),
+	service_tree = service_tree_for(cfqq->cfqg, cfqq_class(cfqq),
 						cfqq_type(cfqq));
 	if (cfq_class_idle(cfqq)) {
 		rb_key = CFQ_IDLE_DELAY;
@@ -2029,8 +2029,8 @@ static void __cfq_set_active_queue(struct cfq_data *cfqd,
 				   struct cfq_queue *cfqq)
 {
 	if (cfqq) {
-		cfq_log_cfqq(cfqd, cfqq, "set_active wl_prio:%d wl_type:%d",
-				cfqd->serving_prio, cfqd->serving_type);
+		cfq_log_cfqq(cfqd, cfqq, "set_active wl_class:%d wl_type:%d",
+				cfqd->serving_class, cfqd->serving_type);
 		cfqg_stats_update_avg_queue_size(cfqq->cfqg);
 		cfqq->slice_start = 0;
 		cfqq->dispatch_start = jiffies;
@@ -2117,7 +2117,7 @@ static inline void cfq_slice_expired(struct cfq_data *cfqd, bool timed_out)
 static struct cfq_queue *cfq_get_next_queue(struct cfq_data *cfqd)
 {
 	struct cfq_rb_root *service_tree =
-		service_tree_for(cfqd->serving_group, cfqd->serving_prio,
+		service_tree_for(cfqd->serving_group, cfqd->serving_class,
 					cfqd->serving_type);
 
 	if (!cfqd->rq_queued)
@@ -2284,7 +2284,7 @@ static struct cfq_queue *cfq_close_cooperator(struct cfq_data *cfqd,
 
 static bool cfq_should_idle(struct cfq_data *cfqd, struct cfq_queue *cfqq)
 {
-	enum wl_prio_t prio = cfqq_prio(cfqq);
+	enum wl_class_t wl_class = cfqq_class(cfqq);
 	struct cfq_rb_root *service_tree = cfqq->service_tree;
 
 	BUG_ON(!service_tree);
@@ -2294,7 +2294,7 @@ static bool cfq_should_idle(struct cfq_data *cfqd, struct cfq_queue *cfqq)
 		return false;
 
 	/* We never do for idle class queues. */
-	if (prio == IDLE_WORKLOAD)
+	if (wl_class == IDLE_WORKLOAD)
 		return false;
 
 	/* We do for queues that were marked with idle window flag. */
@@ -2494,7 +2494,7 @@ static void cfq_setup_merge(struct cfq_queue *cfqq, struct cfq_queue *new_cfqq)
 }
 
 static enum wl_type_t cfq_choose_wl(struct cfq_data *cfqd,
-				struct cfq_group *cfqg, enum wl_prio_t prio)
+			struct cfq_group *cfqg, enum wl_class_t wl_class)
 {
 	struct cfq_queue *queue;
 	int i;
@@ -2504,7 +2504,7 @@ static enum wl_type_t cfq_choose_wl(struct cfq_data *cfqd,
 
 	for (i = 0; i <= SYNC_WORKLOAD; ++i) {
 		/* select the one with lowest rb_key */
-		queue = cfq_rb_first(service_tree_for(cfqg, prio, i));
+		queue = cfq_rb_first(service_tree_for(cfqg, wl_class, i));
 		if (queue &&
 		    (!key_valid || time_before(queue->rb_key, lowest_key))) {
 			lowest_key = queue->rb_key;
@@ -2522,20 +2522,20 @@ static void choose_service_tree(struct cfq_data *cfqd, struct cfq_group *cfqg)
 	unsigned count;
 	struct cfq_rb_root *st;
 	unsigned group_slice;
-	enum wl_prio_t original_prio = cfqd->serving_prio;
+	enum wl_class_t original_class = cfqd->serving_class;
 
 	/* Choose next priority. RT > BE > IDLE */
 	if (cfq_group_busy_queues_wl(RT_WORKLOAD, cfqd, cfqg))
-		cfqd->serving_prio = RT_WORKLOAD;
+		cfqd->serving_class = RT_WORKLOAD;
 	else if (cfq_group_busy_queues_wl(BE_WORKLOAD, cfqd, cfqg))
-		cfqd->serving_prio = BE_WORKLOAD;
+		cfqd->serving_class = BE_WORKLOAD;
 	else {
-		cfqd->serving_prio = IDLE_WORKLOAD;
+		cfqd->serving_class = IDLE_WORKLOAD;
 		cfqd->workload_expires = jiffies + 1;
 		return;
 	}
 
-	if (original_prio != cfqd->serving_prio)
+	if (original_class != cfqd->serving_class)
 		goto new_workload;
 
 	/*
@@ -2543,7 +2543,7 @@ static void choose_service_tree(struct cfq_data *cfqd, struct cfq_group *cfqg)
 	 * (SYNC, SYNC_NOIDLE, ASYNC), and to compute a workload
 	 * expiration time
 	 */
-	st = service_tree_for(cfqg, cfqd->serving_prio, cfqd->serving_type);
+	st = service_tree_for(cfqg, cfqd->serving_class, cfqd->serving_type);
 	count = st->count;
 
 	/*
@@ -2555,8 +2555,8 @@ static void choose_service_tree(struct cfq_data *cfqd, struct cfq_group *cfqg)
 new_workload:
 	/* otherwise select new workload type */
 	cfqd->serving_type =
-		cfq_choose_wl(cfqd, cfqg, cfqd->serving_prio);
-	st = service_tree_for(cfqg, cfqd->serving_prio, cfqd->serving_type);
+		cfq_choose_wl(cfqd, cfqg, cfqd->serving_class);
+	st = service_tree_for(cfqg, cfqd->serving_class, cfqd->serving_type);
 	count = st->count;
 
 	/*
@@ -2567,8 +2567,9 @@ new_workload:
 	group_slice = cfq_group_slice(cfqd, cfqg);
 
 	slice = group_slice * count /
-		max_t(unsigned, cfqg->busy_queues_avg[cfqd->serving_prio],
-		      cfq_group_busy_queues_wl(cfqd->serving_prio, cfqd, cfqg));
+		max_t(unsigned, cfqg->busy_queues_avg[cfqd->serving_class],
+		      cfq_group_busy_queues_wl(cfqd->serving_class, cfqd,
+					cfqg));
 
 	if (cfqd->serving_type == ASYNC_WORKLOAD) {
 		unsigned int tmp;
@@ -2619,7 +2620,7 @@ static void cfq_choose_cfqg(struct cfq_data *cfqd)
 	if (cfqg->saved_workload_slice) {
 		cfqd->workload_expires = jiffies + cfqg->saved_workload_slice;
 		cfqd->serving_type = cfqg->saved_workload;
-		cfqd->serving_prio = cfqg->saved_serving_prio;
+		cfqd->serving_class = cfqg->saved_serving_class;
 	} else
 		cfqd->workload_expires = jiffies - 1;
 
@@ -3644,7 +3645,7 @@ static void cfq_completed_request(struct request_queue *q, struct request *rq)
 			service_tree = cfqq->service_tree;
 		else
 			service_tree = service_tree_for(cfqq->cfqg,
-				cfqq_prio(cfqq), cfqq_type(cfqq));
+				cfqq_class(cfqq), cfqq_type(cfqq));
 		service_tree->ttime.last_end_request = now;
 		if (!time_after(rq->start_time + cfqd->cfq_fifo_expire[1], now))
 			cfqd->last_delayed_sync = now;
-- 
1.7.7.6

[PATCH 02/15] cfq-iosched: More renaming to better represent wl_class and wl_type

[Vivek Goyal]

Some more renaming. Again making the code uniform w.r.t use of
wl_class/class to represent IO class (RT, BE, IDLE) and using
wl_type/type to represent subclass (SYNC, SYNC-IDLE, ASYNC).

At places this patch shortens the string "workload" to "wl". Also at
places I have got rid of keyword "serving" as it is obivious.

Again, just trying to increase uniformity and improve readability. No
functional change.

Signed-off-by: Vivek Goyal <vgoyal@redhat.com>
---
 block/cfq-iosched.c |   61 +++++++++++++++++++++++++--------------------------
 1 files changed, 30 insertions(+), 31 deletions(-)

diff --git a/block/cfq-iosched.c b/block/cfq-iosched.c
index 9d44394..44ac479 100644
--- a/block/cfq-iosched.c
+++ b/block/cfq-iosched.c
@@ -248,9 +248,9 @@ struct cfq_group {
 	struct cfq_rb_root service_trees[2][3];
 	struct cfq_rb_root service_tree_idle;
 
-	unsigned long saved_workload_slice;
-	enum wl_type_t saved_workload;
-	enum wl_class_t saved_serving_class;
+	unsigned long saved_wl_slice;
+	enum wl_type_t saved_wl_type;
+	enum wl_class_t saved_wl_class;
 
 	/* number of requests that are on the dispatch list or inside driver */
 	int dispatched;
@@ -280,8 +280,8 @@ struct cfq_data {
 	/*
 	 * The priority currently being served
 	 */
-	enum wl_class_t serving_class;
-	enum wl_type_t serving_type;
+	enum wl_class_t wl_class;
+	enum wl_type_t wl_type;
 	unsigned long workload_expires;
 	struct cfq_group *serving_group;
 
@@ -1241,7 +1241,7 @@ cfq_group_notify_queue_del(struct cfq_data *cfqd, struct cfq_group *cfqg)
 
 	cfq_log_cfqg(cfqd, cfqg, "del_from_rr group");
 	cfq_group_service_tree_del(st, cfqg);
-	cfqg->saved_workload_slice = 0;
+	cfqg->saved_wl_slice = 0;
 	cfqg_stats_update_dequeue(cfqg);
 }
 
@@ -1301,12 +1301,12 @@ static void cfq_group_served(struct cfq_data *cfqd, struct cfq_group *cfqg,
 
 	/* This group is being expired. Save the context */
 	if (time_after(cfqd->workload_expires, jiffies)) {
-		cfqg->saved_workload_slice = cfqd->workload_expires
+		cfqg->saved_wl_slice = cfqd->workload_expires
 						- jiffies;
-		cfqg->saved_workload = cfqd->serving_type;
-		cfqg->saved_serving_class = cfqd->serving_class;
+		cfqg->saved_wl_type = cfqd->wl_type;
+		cfqg->saved_wl_class = cfqd->wl_class;
 	} else
-		cfqg->saved_workload_slice = 0;
+		cfqg->saved_wl_slice = 0;
 
 	cfq_log_cfqg(cfqd, cfqg, "served: vt=%llu min_vt=%llu", cfqg->vdisktime,
 					st->min_vdisktime);
@@ -2030,7 +2030,7 @@ static void __cfq_set_active_queue(struct cfq_data *cfqd,
 {
 	if (cfqq) {
 		cfq_log_cfqq(cfqd, cfqq, "set_active wl_class:%d wl_type:%d",
-				cfqd->serving_class, cfqd->serving_type);
+				cfqd->wl_class, cfqd->wl_type);
 		cfqg_stats_update_avg_queue_size(cfqq->cfqg);
 		cfqq->slice_start = 0;
 		cfqq->dispatch_start = jiffies;
@@ -2117,8 +2117,8 @@ static inline void cfq_slice_expired(struct cfq_data *cfqd, bool timed_out)
 static struct cfq_queue *cfq_get_next_queue(struct cfq_data *cfqd)
 {
 	struct cfq_rb_root *service_tree =
-		service_tree_for(cfqd->serving_group, cfqd->serving_class,
-					cfqd->serving_type);
+		service_tree_for(cfqd->serving_group, cfqd->wl_class,
+						cfqd->wl_type);
 
 	if (!cfqd->rq_queued)
 		return NULL;
@@ -2522,20 +2522,20 @@ static void choose_service_tree(struct cfq_data *cfqd, struct cfq_group *cfqg)
 	unsigned count;
 	struct cfq_rb_root *st;
 	unsigned group_slice;
-	enum wl_class_t original_class = cfqd->serving_class;
+	enum wl_class_t original_class = cfqd->wl_class;
 
 	/* Choose next priority. RT > BE > IDLE */
 	if (cfq_group_busy_queues_wl(RT_WORKLOAD, cfqd, cfqg))
-		cfqd->serving_class = RT_WORKLOAD;
+		cfqd->wl_class = RT_WORKLOAD;
 	else if (cfq_group_busy_queues_wl(BE_WORKLOAD, cfqd, cfqg))
-		cfqd->serving_class = BE_WORKLOAD;
+		cfqd->wl_class = BE_WORKLOAD;
 	else {
-		cfqd->serving_class = IDLE_WORKLOAD;
+		cfqd->wl_class = IDLE_WORKLOAD;
 		cfqd->workload_expires = jiffies + 1;
 		return;
 	}
 
-	if (original_class != cfqd->serving_class)
+	if (original_class != cfqd->wl_class)
 		goto new_workload;
 
 	/*
@@ -2543,7 +2543,7 @@ static void choose_service_tree(struct cfq_data *cfqd, struct cfq_group *cfqg)
 	 * (SYNC, SYNC_NOIDLE, ASYNC), and to compute a workload
 	 * expiration time
 	 */
-	st = service_tree_for(cfqg, cfqd->serving_class, cfqd->serving_type);
+	st = service_tree_for(cfqg, cfqd->wl_class, cfqd->wl_type);
 	count = st->count;
 
 	/*
@@ -2554,9 +2554,8 @@ static void choose_service_tree(struct cfq_data *cfqd, struct cfq_group *cfqg)
 
 new_workload:
 	/* otherwise select new workload type */
-	cfqd->serving_type =
-		cfq_choose_wl(cfqd, cfqg, cfqd->serving_class);
-	st = service_tree_for(cfqg, cfqd->serving_class, cfqd->serving_type);
+	cfqd->wl_type = cfq_choose_wl(cfqd, cfqg, cfqd->wl_class);
+	st = service_tree_for(cfqg, cfqd->wl_class, cfqd->wl_type);
 	count = st->count;
 
 	/*
@@ -2567,11 +2566,11 @@ new_workload:
 	group_slice = cfq_group_slice(cfqd, cfqg);
 
 	slice = group_slice * count /
-		max_t(unsigned, cfqg->busy_queues_avg[cfqd->serving_class],
-		      cfq_group_busy_queues_wl(cfqd->serving_class, cfqd,
+		max_t(unsigned, cfqg->busy_queues_avg[cfqd->wl_class],
+		      cfq_group_busy_queues_wl(cfqd->wl_class, cfqd,
 					cfqg));
 
-	if (cfqd->serving_type == ASYNC_WORKLOAD) {
+	if (cfqd->wl_type == ASYNC_WORKLOAD) {
 		unsigned int tmp;
 
 		/*
@@ -2617,10 +2616,10 @@ static void cfq_choose_cfqg(struct cfq_data *cfqd)
 	cfqd->serving_group = cfqg;
 
 	/* Restore the workload type data */
-	if (cfqg->saved_workload_slice) {
-		cfqd->workload_expires = jiffies + cfqg->saved_workload_slice;
-		cfqd->serving_type = cfqg->saved_workload;
-		cfqd->serving_class = cfqg->saved_serving_class;
+	if (cfqg->saved_wl_slice) {
+		cfqd->workload_expires = jiffies + cfqg->saved_wl_slice;
+		cfqd->wl_type = cfqg->saved_wl_type;
+		cfqd->wl_class = cfqg->saved_wl_class;
 	} else
 		cfqd->workload_expires = jiffies - 1;
 
@@ -3403,7 +3402,7 @@ cfq_should_preempt(struct cfq_data *cfqd, struct cfq_queue *new_cfqq,
 		return true;
 
 	/* Allow preemption only if we are idling on sync-noidle tree */
-	if (cfqd->serving_type == SYNC_NOIDLE_WORKLOAD &&
+	if (cfqd->wl_type == SYNC_NOIDLE_WORKLOAD &&
 	    cfqq_type(new_cfqq) == SYNC_NOIDLE_WORKLOAD &&
 	    new_cfqq->service_tree->count == 2 &&
 	    RB_EMPTY_ROOT(&cfqq->sort_list))
@@ -3455,7 +3454,7 @@ static void cfq_preempt_queue(struct cfq_data *cfqd, struct cfq_queue *cfqq)
 	 * doesn't happen
 	 */
 	if (old_type != cfqq_type(cfqq))
-		cfqq->cfqg->saved_workload_slice = 0;
+		cfqq->cfqg->saved_wl_slice = 0;
 
 	/*
 	 * Put the new queue at the front of the of the current list,
-- 
1.7.7.6

[PATCH 03/15] cfq-iosched: Rename "service_tree" to "st"

[Vivek Goyal]

At quite a few places we use the keyword "service_tree" and I feel that
names in CFQ are already very long and they need to be shortened a bit
where appropriate.

So this patch just renames "service_tree" to "st" at most of the places.
No functionality change.

Signed-off-by: Vivek Goyal <vgoyal@redhat.com>
---
 block/cfq-iosched.c |  153 ++++++++++++++++++++++++--------------------------
 1 files changed, 73 insertions(+), 80 deletions(-)

diff --git a/block/cfq-iosched.c b/block/cfq-iosched.c
index 44ac479..5eb3ed2 100644
--- a/block/cfq-iosched.c
+++ b/block/cfq-iosched.c
@@ -144,7 +144,7 @@ struct cfq_queue {
 	u32 seek_history;
 	sector_t last_request_pos;
 
-	struct cfq_rb_root *service_tree;
+	struct cfq_rb_root *st;
 	struct cfq_queue *new_cfqq;
 	struct cfq_group *cfqg;
 	/* Number of sectors dispatched from queue in single dispatch round */
@@ -245,8 +245,8 @@ struct cfq_group {
 	 * a single tree service_tree_idle.
 	 * Counts are embedded in the cfq_rb_root
 	 */
-	struct cfq_rb_root service_trees[2][3];
-	struct cfq_rb_root service_tree_idle;
+	struct cfq_rb_root sts[2][3];
+	struct cfq_rb_root st_idle;
 
 	unsigned long saved_wl_slice;
 	enum wl_type_t saved_wl_type;
@@ -274,7 +274,7 @@ struct cfq_io_cq {
 struct cfq_data {
 	struct request_queue *queue;
 	/* Root service tree for cfq_groups */
-	struct cfq_rb_root grp_service_tree;
+	struct cfq_rb_root grp_st;
 	struct cfq_group *root_group;
 
 	/*
@@ -353,7 +353,7 @@ struct cfq_data {
 
 static struct cfq_group *cfq_get_next_cfqg(struct cfq_data *cfqd);
 
-static struct cfq_rb_root *service_tree_for(struct cfq_group *cfqg,
+static struct cfq_rb_root *st_for(struct cfq_group *cfqg,
 					    enum wl_class_t class,
 					    enum wl_type_t type)
 {
@@ -361,9 +361,9 @@ static struct cfq_rb_root *service_tree_for(struct cfq_group *cfqg,
 		return NULL;
 
 	if (class == IDLE_WORKLOAD)
-		return &cfqg->service_tree_idle;
+		return &cfqg->st_idle;
 
-	return &cfqg->service_trees[class][type];
+	return &cfqg->sts[class][type];
 }
 
 enum cfqq_state_flags {
@@ -697,12 +697,12 @@ static inline void cfqg_stats_update_completion(struct cfq_group *cfqg,
 /* Traverses through cfq group service trees */
 #define for_each_cfqg_st(cfqg, i, j, st) \
 	for (i = 0; i <= IDLE_WORKLOAD; i++) \
-		for (j = 0, st = i < IDLE_WORKLOAD ? &cfqg->service_trees[i][j]\
-			: &cfqg->service_tree_idle; \
+		for (j = 0, st = i < IDLE_WORKLOAD ? &cfqg->sts[i][j]\
+			: &cfqg->st_idle; \
 			(i < IDLE_WORKLOAD && j <= SYNC_WORKLOAD) || \
 			(i == IDLE_WORKLOAD && j == 0); \
 			j++, st = i < IDLE_WORKLOAD ? \
-			&cfqg->service_trees[i][j]: NULL) \
+			&cfqg->sts[i][j]: NULL) \
 
 static inline bool cfq_io_thinktime_big(struct cfq_data *cfqd,
 	struct cfq_ttime *ttime, bool group_idle)
@@ -756,18 +756,18 @@ static inline int cfq_group_busy_queues_wl(enum wl_class_t wl_class,
 					struct cfq_group *cfqg)
 {
 	if (wl_class == IDLE_WORKLOAD)
-		return cfqg->service_tree_idle.count;
+		return cfqg->st_idle.count;
 
-	return cfqg->service_trees[wl_class][ASYNC_WORKLOAD].count
-		+ cfqg->service_trees[wl_class][SYNC_NOIDLE_WORKLOAD].count
-		+ cfqg->service_trees[wl_class][SYNC_WORKLOAD].count;
+	return cfqg->sts[wl_class][ASYNC_WORKLOAD].count
+		+ cfqg->sts[wl_class][SYNC_NOIDLE_WORKLOAD].count
+		+ cfqg->sts[wl_class][SYNC_WORKLOAD].count;
 }
 
 static inline int cfqg_busy_async_queues(struct cfq_data *cfqd,
 					struct cfq_group *cfqg)
 {
-	return cfqg->service_trees[RT_WORKLOAD][ASYNC_WORKLOAD].count
-		+ cfqg->service_trees[BE_WORKLOAD][ASYNC_WORKLOAD].count;
+	return cfqg->sts[RT_WORKLOAD][ASYNC_WORKLOAD].count
+		+ cfqg->sts[BE_WORKLOAD][ASYNC_WORKLOAD].count;
 }
 
 static void cfq_dispatch_insert(struct request_queue *, struct request *);
@@ -909,7 +909,7 @@ static inline unsigned cfq_group_get_avg_queues(struct cfq_data *cfqd,
 static inline unsigned
 cfq_group_slice(struct cfq_data *cfqd, struct cfq_group *cfqg)
 {
-	struct cfq_rb_root *st = &cfqd->grp_service_tree;
+	struct cfq_rb_root *st = &cfqd->grp_st;
 
 	return cfqd->cfq_target_latency * cfqg->weight / st->total_weight;
 }
@@ -1146,8 +1146,7 @@ cfqg_key(struct cfq_rb_root *st, struct cfq_group *cfqg)
 	return cfqg->vdisktime - st->min_vdisktime;
 }
 
-static void
-__cfq_group_service_tree_add(struct cfq_rb_root *st, struct cfq_group *cfqg)
+static void __cfq_group_st_add(struct cfq_rb_root *st, struct cfq_group *cfqg)
 {
 	struct rb_node **node = &st->rb.rb_node;
 	struct rb_node *parent = NULL;
@@ -1184,20 +1183,19 @@ cfq_update_group_weight(struct cfq_group *cfqg)
 	}
 }
 
-static void
-cfq_group_service_tree_add(struct cfq_rb_root *st, struct cfq_group *cfqg)
+static void cfq_group_st_add(struct cfq_rb_root *st, struct cfq_group *cfqg)
 {
 	BUG_ON(!RB_EMPTY_NODE(&cfqg->rb_node));
 
 	cfq_update_group_weight(cfqg);
-	__cfq_group_service_tree_add(st, cfqg);
+	__cfq_group_st_add(st, cfqg);
 	st->total_weight += cfqg->weight;
 }
 
 static void
 cfq_group_notify_queue_add(struct cfq_data *cfqd, struct cfq_group *cfqg)
 {
-	struct cfq_rb_root *st = &cfqd->grp_service_tree;
+	struct cfq_rb_root *st = &cfqd->grp_st;
 	struct cfq_group *__cfqg;
 	struct rb_node *n;
 
@@ -1216,11 +1214,10 @@ cfq_group_notify_queue_add(struct cfq_data *cfqd, struct cfq_group *cfqg)
 		cfqg->vdisktime = __cfqg->vdisktime + CFQ_IDLE_DELAY;
 	} else
 		cfqg->vdisktime = st->min_vdisktime;
-	cfq_group_service_tree_add(st, cfqg);
+	cfq_group_st_add(st, cfqg);
 }
 
-static void
-cfq_group_service_tree_del(struct cfq_rb_root *st, struct cfq_group *cfqg)
+static void cfq_group_st_del(struct cfq_rb_root *st, struct cfq_group *cfqg)
 {
 	st->total_weight -= cfqg->weight;
 	if (!RB_EMPTY_NODE(&cfqg->rb_node))
@@ -1230,7 +1227,7 @@ cfq_group_service_tree_del(struct cfq_rb_root *st, struct cfq_group *cfqg)
 static void
 cfq_group_notify_queue_del(struct cfq_data *cfqd, struct cfq_group *cfqg)
 {
-	struct cfq_rb_root *st = &cfqd->grp_service_tree;
+	struct cfq_rb_root *st = &cfqd->grp_st;
 
 	BUG_ON(cfqg->nr_cfqq < 1);
 	cfqg->nr_cfqq--;
@@ -1240,7 +1237,7 @@ cfq_group_notify_queue_del(struct cfq_data *cfqd, struct cfq_group *cfqg)
 		return;
 
 	cfq_log_cfqg(cfqd, cfqg, "del_from_rr group");
-	cfq_group_service_tree_del(st, cfqg);
+	cfq_group_st_del(st, cfqg);
 	cfqg->saved_wl_slice = 0;
 	cfqg_stats_update_dequeue(cfqg);
 }
@@ -1280,10 +1277,10 @@ static inline unsigned int cfq_cfqq_slice_usage(struct cfq_queue *cfqq,
 static void cfq_group_served(struct cfq_data *cfqd, struct cfq_group *cfqg,
 				struct cfq_queue *cfqq)
 {
-	struct cfq_rb_root *st = &cfqd->grp_service_tree;
+	struct cfq_rb_root *st = &cfqd->grp_st;
 	unsigned int used_sl, charge, unaccounted_sl = 0;
 	int nr_sync = cfqg->nr_cfqq - cfqg_busy_async_queues(cfqd, cfqg)
-			- cfqg->service_tree_idle.count;
+			- cfqg->st_idle.count;
 
 	BUG_ON(nr_sync < 0);
 	used_sl = charge = cfq_cfqq_slice_usage(cfqq, &unaccounted_sl);
@@ -1294,10 +1291,10 @@ static void cfq_group_served(struct cfq_data *cfqd, struct cfq_group *cfqg,
 		charge = cfqq->allocated_slice;
 
 	/* Can't update vdisktime while group is on service tree */
-	cfq_group_service_tree_del(st, cfqg);
+	cfq_group_st_del(st, cfqg);
 	cfqg->vdisktime += cfq_scale_slice(charge, cfqg);
 	/* If a new weight was requested, update now, off tree */
-	cfq_group_service_tree_add(st, cfqg);
+	cfq_group_st_add(st, cfqg);
 
 	/* This group is being expired. Save the context */
 	if (time_after(cfqd->workload_expires, jiffies)) {
@@ -1602,25 +1599,24 @@ cfq_link_cfqq_cfqg(struct cfq_queue *cfqq, struct cfq_group *cfqg) {
 #endif /* GROUP_IOSCHED */
 
 /*
- * The cfqd->service_trees holds all pending cfq_queue's that have
+ * The cfqd->st holds all pending cfq_queue's that have
  * requests waiting to be processed. It is sorted in the order that
  * we will service the queues.
  */
-static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
+static void cfq_st_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
 				 bool add_front)
 {
 	struct rb_node **p, *parent;
 	struct cfq_queue *__cfqq;
 	unsigned long rb_key;
-	struct cfq_rb_root *service_tree;
+	struct cfq_rb_root *st;
 	int left;
 	int new_cfqq = 1;
 
-	service_tree = service_tree_for(cfqq->cfqg, cfqq_class(cfqq),
-						cfqq_type(cfqq));
+	st = st_for(cfqq->cfqg, cfqq_class(cfqq), cfqq_type(cfqq));
 	if (cfq_class_idle(cfqq)) {
 		rb_key = CFQ_IDLE_DELAY;
-		parent = rb_last(&service_tree->rb);
+		parent = rb_last(&st->rb);
 		if (parent && parent != &cfqq->rb_node) {
 			__cfqq = rb_entry(parent, struct cfq_queue, rb_node);
 			rb_key += __cfqq->rb_key;
@@ -1638,7 +1634,7 @@ static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
 		cfqq->slice_resid = 0;
 	} else {
 		rb_key = -HZ;
-		__cfqq = cfq_rb_first(service_tree);
+		__cfqq = cfq_rb_first(st);
 		rb_key += __cfqq ? __cfqq->rb_key : jiffies;
 	}
 
@@ -1647,18 +1643,17 @@ static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
 		/*
 		 * same position, nothing more to do
 		 */
-		if (rb_key == cfqq->rb_key &&
-		    cfqq->service_tree == service_tree)
+		if (rb_key == cfqq->rb_key && cfqq->st == st)
 			return;
 
-		cfq_rb_erase(&cfqq->rb_node, cfqq->service_tree);
-		cfqq->service_tree = NULL;
+		cfq_rb_erase(&cfqq->rb_node, cfqq->st);
+		cfqq->st = NULL;
 	}
 
 	left = 1;
 	parent = NULL;
-	cfqq->service_tree = service_tree;
-	p = &service_tree->rb.rb_node;
+	cfqq->st = st;
+	p = &st->rb.rb_node;
 	while (*p) {
 		struct rb_node **n;
 
@@ -1679,12 +1674,12 @@ static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
 	}
 
 	if (left)
-		service_tree->left = &cfqq->rb_node;
+		st->left = &cfqq->rb_node;
 
 	cfqq->rb_key = rb_key;
 	rb_link_node(&cfqq->rb_node, parent, p);
-	rb_insert_color(&cfqq->rb_node, &service_tree->rb);
-	service_tree->count++;
+	rb_insert_color(&cfqq->rb_node, &st->rb);
+	st->count++;
 	if (add_front || !new_cfqq)
 		return;
 	cfq_group_notify_queue_add(cfqd, cfqq->cfqg);
@@ -1760,7 +1755,7 @@ static void cfq_resort_rr_list(struct cfq_data *cfqd, struct cfq_queue *cfqq)
 	 * Resorting requires the cfqq to be on the RR list already.
 	 */
 	if (cfq_cfqq_on_rr(cfqq)) {
-		cfq_service_tree_add(cfqd, cfqq, 0);
+		cfq_st_add(cfqd, cfqq, 0);
 		cfq_prio_tree_add(cfqd, cfqq);
 	}
 }
@@ -1792,8 +1787,8 @@ static void cfq_del_cfqq_rr(struct cfq_data *cfqd, struct cfq_queue *cfqq)
 	cfq_clear_cfqq_on_rr(cfqq);
 
 	if (!RB_EMPTY_NODE(&cfqq->rb_node)) {
-		cfq_rb_erase(&cfqq->rb_node, cfqq->service_tree);
-		cfqq->service_tree = NULL;
+		cfq_rb_erase(&cfqq->rb_node, cfqq->st);
+		cfqq->st = NULL;
 	}
 	if (cfqq->p_root) {
 		rb_erase(&cfqq->p_node, cfqq->p_root);
@@ -2116,19 +2111,18 @@ static inline void cfq_slice_expired(struct cfq_data *cfqd, bool timed_out)
  */
 static struct cfq_queue *cfq_get_next_queue(struct cfq_data *cfqd)
 {
-	struct cfq_rb_root *service_tree =
-		service_tree_for(cfqd->serving_group, cfqd->wl_class,
-						cfqd->wl_type);
+	struct cfq_rb_root *st =
+		st_for(cfqd->serving_group, cfqd->wl_class, cfqd->wl_type);
 
 	if (!cfqd->rq_queued)
 		return NULL;
 
 	/* There is nothing to dispatch */
-	if (!service_tree)
+	if (!st)
 		return NULL;
-	if (RB_EMPTY_ROOT(&service_tree->rb))
+	if (RB_EMPTY_ROOT(&st->rb))
 		return NULL;
-	return cfq_rb_first(service_tree);
+	return cfq_rb_first(st);
 }
 
 static struct cfq_queue *cfq_get_next_queue_forced(struct cfq_data *cfqd)
@@ -2285,10 +2279,10 @@ static struct cfq_queue *cfq_close_cooperator(struct cfq_data *cfqd,
 static bool cfq_should_idle(struct cfq_data *cfqd, struct cfq_queue *cfqq)
 {
 	enum wl_class_t wl_class = cfqq_class(cfqq);
-	struct cfq_rb_root *service_tree = cfqq->service_tree;
+	struct cfq_rb_root *st = cfqq->st;
 
-	BUG_ON(!service_tree);
-	BUG_ON(!service_tree->count);
+	BUG_ON(!st);
+	BUG_ON(!st->count);
 
 	if (!cfqd->cfq_slice_idle)
 		return false;
@@ -2306,11 +2300,10 @@ static bool cfq_should_idle(struct cfq_data *cfqd, struct cfq_queue *cfqq)
 	 * Otherwise, we do only if they are the last ones
 	 * in their service tree.
 	 */
-	if (service_tree->count == 1 && cfq_cfqq_sync(cfqq) &&
-	   !cfq_io_thinktime_big(cfqd, &service_tree->ttime, false))
+	if (st->count == 1 && cfq_cfqq_sync(cfqq) &&
+	   !cfq_io_thinktime_big(cfqd, &st->ttime, false))
 		return true;
-	cfq_log_cfqq(cfqd, cfqq, "Not idling. st->count:%d",
-			service_tree->count);
+	cfq_log_cfqq(cfqd, cfqq, "Not idling. st->count:%d", st->count);
 	return false;
 }
 
@@ -2504,7 +2497,7 @@ static enum wl_type_t cfq_choose_wl(struct cfq_data *cfqd,
 
 	for (i = 0; i <= SYNC_WORKLOAD; ++i) {
 		/* select the one with lowest rb_key */
-		queue = cfq_rb_first(service_tree_for(cfqg, wl_class, i));
+		queue = cfq_rb_first(st_for(cfqg, wl_class, i));
 		if (queue &&
 		    (!key_valid || time_before(queue->rb_key, lowest_key))) {
 			lowest_key = queue->rb_key;
@@ -2516,7 +2509,7 @@ static enum wl_type_t cfq_choose_wl(struct cfq_data *cfqd,
 	return cur_best;
 }
 
-static void choose_service_tree(struct cfq_data *cfqd, struct cfq_group *cfqg)
+static void choose_st(struct cfq_data *cfqd, struct cfq_group *cfqg)
 {
 	unsigned slice;
 	unsigned count;
@@ -2543,7 +2536,7 @@ static void choose_service_tree(struct cfq_data *cfqd, struct cfq_group *cfqg)
 	 * (SYNC, SYNC_NOIDLE, ASYNC), and to compute a workload
 	 * expiration time
 	 */
-	st = service_tree_for(cfqg, cfqd->wl_class, cfqd->wl_type);
+	st = st_for(cfqg, cfqd->wl_class, cfqd->wl_type);
 	count = st->count;
 
 	/*
@@ -2555,7 +2548,7 @@ static void choose_service_tree(struct cfq_data *cfqd, struct cfq_group *cfqg)
 new_workload:
 	/* otherwise select new workload type */
 	cfqd->wl_type = cfq_choose_wl(cfqd, cfqg, cfqd->wl_class);
-	st = service_tree_for(cfqg, cfqd->wl_class, cfqd->wl_type);
+	st = st_for(cfqg, cfqd->wl_class, cfqd->wl_type);
 	count = st->count;
 
 	/*
@@ -2599,7 +2592,7 @@ new_workload:
 
 static struct cfq_group *cfq_get_next_cfqg(struct cfq_data *cfqd)
 {
-	struct cfq_rb_root *st = &cfqd->grp_service_tree;
+	struct cfq_rb_root *st = &cfqd->grp_st;
 	struct cfq_group *cfqg;
 
 	if (RB_EMPTY_ROOT(&st->rb))
@@ -2623,7 +2616,7 @@ static void cfq_choose_cfqg(struct cfq_data *cfqd)
 	} else
 		cfqd->workload_expires = jiffies - 1;
 
-	choose_service_tree(cfqd, cfqg);
+	choose_st(cfqd, cfqg);
 }
 
 /*
@@ -3291,7 +3284,7 @@ cfq_update_io_thinktime(struct cfq_data *cfqd, struct cfq_queue *cfqq,
 {
 	if (cfq_cfqq_sync(cfqq)) {
 		__cfq_update_io_thinktime(&cic->ttime, cfqd->cfq_slice_idle);
-		__cfq_update_io_thinktime(&cfqq->service_tree->ttime,
+		__cfq_update_io_thinktime(&cfqq->st->ttime,
 			cfqd->cfq_slice_idle);
 	}
 #ifdef CONFIG_CFQ_GROUP_IOSCHED
@@ -3404,8 +3397,7 @@ cfq_should_preempt(struct cfq_data *cfqd, struct cfq_queue *new_cfqq,
 	/* Allow preemption only if we are idling on sync-noidle tree */
 	if (cfqd->wl_type == SYNC_NOIDLE_WORKLOAD &&
 	    cfqq_type(new_cfqq) == SYNC_NOIDLE_WORKLOAD &&
-	    new_cfqq->service_tree->count == 2 &&
-	    RB_EMPTY_ROOT(&cfqq->sort_list))
+	    new_cfqq->st->count == 2 && RB_EMPTY_ROOT(&cfqq->sort_list))
 		return true;
 
 	/*
@@ -3462,7 +3454,7 @@ static void cfq_preempt_queue(struct cfq_data *cfqd, struct cfq_queue *cfqq)
 	 */
 	BUG_ON(!cfq_cfqq_on_rr(cfqq));
 
-	cfq_service_tree_add(cfqd, cfqq, 1);
+	cfq_st_add(cfqd, cfqq, 1);
 
 	cfqq->slice_end = 0;
 	cfq_mark_cfqq_slice_new(cfqq);
@@ -3636,16 +3628,17 @@ static void cfq_completed_request(struct request_queue *q, struct request *rq)
 	cfqd->rq_in_flight[cfq_cfqq_sync(cfqq)]--;
 
 	if (sync) {
-		struct cfq_rb_root *service_tree;
+		struct cfq_rb_root *st;
 
 		RQ_CIC(rq)->ttime.last_end_request = now;
 
 		if (cfq_cfqq_on_rr(cfqq))
-			service_tree = cfqq->service_tree;
+			st = cfqq->st;
 		else
-			service_tree = service_tree_for(cfqq->cfqg,
-				cfqq_class(cfqq), cfqq_type(cfqq));
-		service_tree->ttime.last_end_request = now;
+			st = st_for(cfqq->cfqg, cfqq_class(cfqq),
+					cfqq_type(cfqq));
+
+		st->ttime.last_end_request = now;
 		if (!time_after(rq->start_time + cfqd->cfq_fifo_expire[1], now))
 			cfqd->last_delayed_sync = now;
 	}
@@ -3973,7 +3966,7 @@ static int cfq_init_queue(struct request_queue *q)
 	q->elevator->elevator_data = cfqd;
 
 	/* Init root service tree */
-	cfqd->grp_service_tree = CFQ_RB_ROOT;
+	cfqd->grp_st = CFQ_RB_ROOT;
 
 	/* Init root group and prefer root group over other groups by default */
 #ifdef CONFIG_CFQ_GROUP_IOSCHED
-- 
1.7.7.6

[PATCH 04/15] cfq-iosched: Rename few functions related to selecting workload

[Vivek Goyal]

choose_st() selects/sets both wl_class and wl_type.  Rename it to
choose_wl_class_and_type() to make it very clear.

cfq_choose_wl() only selects and sets wl_type. It is easy to confuse
it with choose_st(). So rename it to cfq_choose_wl_type() to make
it clear what does it do.

Just renaming. No functionality change.

Signed-off-by: Vivek Goyal <vgoyal@redhat.com>
---
 block/cfq-iosched.c |    9 +++++----
 1 files changed, 5 insertions(+), 4 deletions(-)

diff --git a/block/cfq-iosched.c b/block/cfq-iosched.c
index 5eb3ed2..9657924 100644
--- a/block/cfq-iosched.c
+++ b/block/cfq-iosched.c
@@ -2486,7 +2486,7 @@ static void cfq_setup_merge(struct cfq_queue *cfqq, struct cfq_queue *new_cfqq)
 	}
 }
 
-static enum wl_type_t cfq_choose_wl(struct cfq_data *cfqd,
+static enum wl_type_t cfq_choose_wl_type(struct cfq_data *cfqd,
 			struct cfq_group *cfqg, enum wl_class_t wl_class)
 {
 	struct cfq_queue *queue;
@@ -2509,7 +2509,8 @@ static enum wl_type_t cfq_choose_wl(struct cfq_data *cfqd,
 	return cur_best;
 }
 
-static void choose_st(struct cfq_data *cfqd, struct cfq_group *cfqg)
+static void
+choose_wl_class_and_type(struct cfq_data *cfqd, struct cfq_group *cfqg)
 {
 	unsigned slice;
 	unsigned count;
@@ -2547,7 +2548,7 @@ static void choose_st(struct cfq_data *cfqd, struct cfq_group *cfqg)
 
 new_workload:
 	/* otherwise select new workload type */
-	cfqd->wl_type = cfq_choose_wl(cfqd, cfqg, cfqd->wl_class);
+	cfqd->wl_type = cfq_choose_wl_type(cfqd, cfqg, cfqd->wl_class);
 	st = st_for(cfqg, cfqd->wl_class, cfqd->wl_type);
 	count = st->count;
 
@@ -2616,7 +2617,7 @@ static void cfq_choose_cfqg(struct cfq_data *cfqd)
 	} else
 		cfqd->workload_expires = jiffies - 1;
 
-	choose_st(cfqd, cfqg);
+	choose_wl_class_and_type(cfqd, cfqg);
 }
 
 /*
-- 
1.7.7.6

[PATCH 05/15] cfq-iosched: Get rid of unnecessary local variable

[Vivek Goyal]

Use of local varibale "n" seems to be unnecessary. Remove it. This brings
it inline with function __cfq_group_st_add(), which is also doing the
similar operation of adding a group to a rb tree.

No functionality change here.

Signed-off-by: Vivek Goyal <vgoyal@redhat.com>
---
 block/cfq-iosched.c |    8 ++------
 1 files changed, 2 insertions(+), 6 deletions(-)

diff --git a/block/cfq-iosched.c b/block/cfq-iosched.c
index 9657924..573e668 100644
--- a/block/cfq-iosched.c
+++ b/block/cfq-iosched.c
@@ -1655,8 +1655,6 @@ static void cfq_st_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
 	cfqq->st = st;
 	p = &st->rb.rb_node;
 	while (*p) {
-		struct rb_node **n;
-
 		parent = *p;
 		__cfqq = rb_entry(parent, struct cfq_queue, rb_node);
 
@@ -1664,13 +1662,11 @@ static void cfq_st_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
 		 * sort by key, that represents service time.
 		 */
 		if (time_before(rb_key, __cfqq->rb_key))
-			n = &(*p)->rb_left;
+			p = &parent->rb_left;
 		else {
-			n = &(*p)->rb_right;
+			p = &parent->rb_right;
 			left = 0;
 		}
-
-		p = n;
 	}
 
 	if (left)
-- 
1.7.7.6

[PATCH 06/15] cfq-iosched: Print sync-noidle information in blktrace messages

[Vivek Goyal]

Currently we attach a character "S" or "A" to the cfqq<pid>, to represent
whether queues is sync or async. Add one more character "N" to represent
whether it is sync-noidle queue or sync queue. So now three different
type of queues will look as follows.

cfq1234S   --> sync queus
cfq1234SN  --> sync noidle queue
cfq1234A   --> Async queue

Previously S/A classification was being printed only if group scheduling
was enabled. This patch also makes sure that this classification is
displayed even if group idling is disabled.

Signed-off-by: Vivek Goyal <vgoyal@redhat.com>
---
 block/cfq-iosched.c |   10 +++++++---
 1 files changed, 7 insertions(+), 3 deletions(-)

diff --git a/block/cfq-iosched.c b/block/cfq-iosched.c
index 573e668..619c680 100644
--- a/block/cfq-iosched.c
+++ b/block/cfq-iosched.c
@@ -586,8 +586,9 @@ static inline void cfqg_put(struct cfq_group *cfqg)
 	char __pbuf[128];						\
 									\
 	blkg_path(cfqg_to_blkg((cfqq)->cfqg), __pbuf, sizeof(__pbuf));	\
-	blk_add_trace_msg((cfqd)->queue, "cfq%d%c %s " fmt, (cfqq)->pid, \
-			  cfq_cfqq_sync((cfqq)) ? 'S' : 'A',		\
+	blk_add_trace_msg((cfqd)->queue, "cfq%d%c%c %s " fmt, (cfqq)->pid, \
+			cfq_cfqq_sync((cfqq)) ? 'S' : 'A',		\
+			cfqq_type((cfqq)) == SYNC_NOIDLE_WORKLOAD ? 'N' : ' ',\
 			  __pbuf, ##args);				\
 } while (0)
 
@@ -675,7 +676,10 @@ static inline void cfqg_get(struct cfq_group *cfqg) { }
 static inline void cfqg_put(struct cfq_group *cfqg) { }
 
 #define cfq_log_cfqq(cfqd, cfqq, fmt, args...)	\
-	blk_add_trace_msg((cfqd)->queue, "cfq%d " fmt, (cfqq)->pid, ##args)
+	blk_add_trace_msg((cfqd)->queue, "cfq%d%c%c " fmt, (cfqq)->pid,	\
+			cfq_cfqq_sync((cfqq)) ? 'S' : 'A',		\
+			cfqq_type((cfqq)) == SYNC_NOIDLE_WORKLOAD ? 'N' : ' ',\
+				##args)
 #define cfq_log_cfqg(cfqd, cfqg, fmt, args...)		do {} while (0)
 
 static inline void cfqg_stats_update_io_add(struct cfq_group *cfqg,
-- 
1.7.7.6

[PATCH 07/15] cfq-iosced: Do the round robin selection of workload type

[Vivek Goyal]

We have three subclass of workloads (SYNC_NODILE, SYNC and ASYNC) for
prio class RT and BE. And cfq needs to select a workload to dispatch
from before it selects a cfqq.

Current workload selection seems to be selecting a workload which has
the lowest key for a cfqq. So effectively all three service tree are
kind of related using that cfqq->rb_key. And that cfqq->rb_key is
influenced by time (apart from other factors). So basically service
tree keys are influenced by time of queuing as well as prio of queue
and service trees are related.

I want to change the workload selection logic a bit for following
reason.

I am moving away from the notion of time for rb_key. The reason
being that I am bringing queue scheduling logic closer to group
scheduling logic where every service tree keeps track of virtual
time (vdisktime) based on disk share used by that group.

That means we can't use real time on queue service tree. And that
also means that virtual time of every service tree will move
independently and I can't use current logic of workload selection
which assumes that cfqq->rb_key of all three service tree are
co-related.

I think one simple way to select workload is do the round robin
among active workloads. That way each workload gets it fair share.
(Though we override that later by allowing preemption of of async
queue by sync queue).

In case a group is freshly queued, we always start with sync-noidle
workload first as that seems to be most important.

So making this change allows us to bring closer to group scheduling
logic, simplifies the workload selection logic and makes the workload
selection more predictable. I am not expecting any serious adverse effects
of this change.

Signed-off-by: Vivek Goyal <vgoyal@redhat.com>
---
 block/cfq-iosched.c |   51 ++++++++++++++++++++++++++++++++-------------------
 1 files changed, 32 insertions(+), 19 deletions(-)

diff --git a/block/cfq-iosched.c b/block/cfq-iosched.c
index 619c680..7a65e12 100644
--- a/block/cfq-iosched.c
+++ b/block/cfq-iosched.c
@@ -166,9 +166,10 @@ enum wl_class_t {
  * Second index in the service_trees.
  */
 enum wl_type_t {
-	ASYNC_WORKLOAD = 0,
-	SYNC_NOIDLE_WORKLOAD = 1,
-	SYNC_WORKLOAD = 2
+	SYNC_NOIDLE_WORKLOAD = 0,
+	SYNC_WORKLOAD = 1,
+	ASYNC_WORKLOAD = 2,
+	WL_TYPE_NR,
 };
 
 struct cfqg_stats {
@@ -248,10 +249,14 @@ struct cfq_group {
 	struct cfq_rb_root sts[2][3];
 	struct cfq_rb_root st_idle;
 
+	/* Saved state when group is scheduled out */
 	unsigned long saved_wl_slice;
 	enum wl_type_t saved_wl_type;
 	enum wl_class_t saved_wl_class;
 
+	/* Last workload type chosen to run in this group */
+	enum wl_type_t last_run_wl_type;
+
 	/* number of requests that are on the dispatch list or inside driver */
 	int dispatched;
 	struct cfq_ttime ttime;
@@ -703,7 +708,7 @@ static inline void cfqg_stats_update_completion(struct cfq_group *cfqg,
 	for (i = 0; i <= IDLE_WORKLOAD; i++) \
 		for (j = 0, st = i < IDLE_WORKLOAD ? &cfqg->sts[i][j]\
 			: &cfqg->st_idle; \
-			(i < IDLE_WORKLOAD && j <= SYNC_WORKLOAD) || \
+			(i < IDLE_WORKLOAD && j < WL_TYPE_NR) || \
 			(i == IDLE_WORKLOAD && j == 0); \
 			j++, st = i < IDLE_WORKLOAD ? \
 			&cfqg->sts[i][j]: NULL) \
@@ -1243,6 +1248,7 @@ cfq_group_notify_queue_del(struct cfq_data *cfqd, struct cfq_group *cfqg)
 	cfq_log_cfqg(cfqd, cfqg, "del_from_rr group");
 	cfq_group_st_del(st, cfqg);
 	cfqg->saved_wl_slice = 0;
+	cfqg->last_run_wl_type = WL_TYPE_NR;
 	cfqg_stats_update_dequeue(cfqg);
 }
 
@@ -1336,6 +1342,7 @@ static void cfq_init_cfqg_base(struct cfq_group *cfqg)
 	RB_CLEAR_NODE(&cfqg->rb_node);
 
 	cfqg->ttime.last_end_request = jiffies;
+	cfqg->last_run_wl_type = WL_TYPE_NR;
 }
 
 #ifdef CONFIG_CFQ_GROUP_IOSCHED
@@ -2486,27 +2493,33 @@ static void cfq_setup_merge(struct cfq_queue *cfqq, struct cfq_queue *new_cfqq)
 	}
 }
 
+static inline enum wl_type_t next_wl_type(enum wl_type_t wl_type)
+{
+	wl_type++;
+	if (wl_type >= WL_TYPE_NR)
+		wl_type = 0;
+	return wl_type;
+}
+
 static enum wl_type_t cfq_choose_wl_type(struct cfq_data *cfqd,
 			struct cfq_group *cfqg, enum wl_class_t wl_class)
 {
-	struct cfq_queue *queue;
+	enum wl_type_t new_wl_type, old_wl_type;
+	struct cfq_rb_root *st;
 	int i;
-	bool key_valid = false;
-	unsigned long lowest_key = 0;
-	enum wl_type_t cur_best = SYNC_NOIDLE_WORKLOAD;
-
-	for (i = 0; i <= SYNC_WORKLOAD; ++i) {
-		/* select the one with lowest rb_key */
-		queue = cfq_rb_first(st_for(cfqg, wl_class, i));
-		if (queue &&
-		    (!key_valid || time_before(queue->rb_key, lowest_key))) {
-			lowest_key = queue->rb_key;
-			cur_best = i;
-			key_valid = true;
-		}
+
+	old_wl_type = cfqg->last_run_wl_type;
+
+	for (i = 0; i < WL_TYPE_NR; i++) {
+		new_wl_type = next_wl_type(old_wl_type);
+		st = st_for(cfqg, wl_class, new_wl_type);
+		if (st->count)
+			break;
+		old_wl_type = new_wl_type;
 	}
 
-	return cur_best;
+	cfqg->last_run_wl_type = new_wl_type;
+	return new_wl_type;
 }
 
 static void
-- 
1.7.7.6

[PATCH 08/15] cfq-iosched: Make cfq_scale_slice() usable for both queues and groups

[Vivek Goyal]

Make cfq_scale_slice() usable both for queues and groups by taking in
weight as a parameter.

Signed-off-by: Vivek Goyal <vgoyal@redhat.com>
---
 block/cfq-iosched.c |    6 +++---
 1 files changed, 3 insertions(+), 3 deletions(-)

diff --git a/block/cfq-iosched.c b/block/cfq-iosched.c
index 7a65e12..a929e2d 100644
--- a/block/cfq-iosched.c
+++ b/block/cfq-iosched.c
@@ -856,12 +856,12 @@ cfq_prio_to_slice(struct cfq_data *cfqd, struct cfq_queue *cfqq)
 	return cfq_prio_slice(cfqd, cfq_cfqq_sync(cfqq), cfqq->ioprio);
 }
 
-static inline u64 cfq_scale_slice(unsigned long delta, struct cfq_group *cfqg)
+static inline u64 cfq_scale_slice(unsigned long delta, unsigned int weight)
 {
 	u64 d = delta << CFQ_SERVICE_SHIFT;
 
 	d = d * CFQ_WEIGHT_DEFAULT;
-	do_div(d, cfqg->weight);
+	do_div(d, weight);
 	return d;
 }
 
@@ -1302,7 +1302,7 @@ static void cfq_group_served(struct cfq_data *cfqd, struct cfq_group *cfqg,
 
 	/* Can't update vdisktime while group is on service tree */
 	cfq_group_st_del(st, cfqg);
-	cfqg->vdisktime += cfq_scale_slice(charge, cfqg);
+	cfqg->vdisktime += cfq_scale_slice(charge, cfqg->weight);
 	/* If a new weight was requested, update now, off tree */
 	cfq_group_st_add(st, cfqg);
 
-- 
1.7.7.6

[PATCH 09/15] cfq-iosched: make new_cfqq variable bool

[Vivek Goyal]

Make new_cfqq bool. Also set the variable in the beginning of function.

Signed-off-by: Vivek Goyal <vgoyal@redhat.com>
---
 block/cfq-iosched.c |    5 ++---
 1 files changed, 2 insertions(+), 3 deletions(-)

diff --git a/block/cfq-iosched.c b/block/cfq-iosched.c
index a929e2d..76f020f 100644
--- a/block/cfq-iosched.c
+++ b/block/cfq-iosched.c
@@ -1622,7 +1622,7 @@ static void cfq_st_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
 	unsigned long rb_key;
 	struct cfq_rb_root *st;
 	int left;
-	int new_cfqq = 1;
+	bool new_cfqq = RB_EMPTY_NODE(&cfqq->rb_node);
 
 	st = st_for(cfqq->cfqg, cfqq_class(cfqq), cfqq_type(cfqq));
 	if (cfq_class_idle(cfqq)) {
@@ -1649,8 +1649,7 @@ static void cfq_st_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
 		rb_key += __cfqq ? __cfqq->rb_key : jiffies;
 	}
 
-	if (!RB_EMPTY_NODE(&cfqq->rb_node)) {
-		new_cfqq = 0;
+	if (!new_cfqq) {
 		/*
 		 * same position, nothing more to do
 		 */
-- 
1.7.7.6

[PATCH 10/15] cfq-get-rid-of-slice-offset-and-always-put-new-queue-at-the-end-2

[Vivek Goyal]

Currently cfq does round robin among cfqq and allocates bigger slices
to higher prio queue. But it also does additional logic of putting
higher priority queues ahead of lower priority queues in the service
tree. cfq_slice_offset() determines the postion of a queue in the
service tree.

I think it was done so that higher prio queues can get even higher
share of disk. As I am planning to move to vdisktime logic, this
does not fit anymore in to scheme of things. In the end of patch
series, I will introduce another approximation which provides vdisktime
boost based on weight. So that will kind of emulate this logic to
provide higher prio queues more than fair share of disk.

So this patch puts every new queue at the end of service tree by
default. Existing queues get their position in the tree depending
on how much slice did they use recently and what's their prio/weight.

This patch only introduces the functionality of adding queues at
the end of service tree. Later patches will introduce the functionality
of determining vdisktime (hence position in service tree) based on
slice used and weight.

If a queue is being requeued, then it will already be on service tree
and we can't determine the rb_key of last element using cfq_rb_last().
So we always remove the queue from service tree first.

This is just an intermediate patch to show clearly how I am chaning
existing functionality. Did not want to lump it together with bigger
patches.

Signed-off-by: Vivek Goyal <vgoyal@redhat.com>
---
 block/cfq-iosched.c |   51 ++++++++++++++++++---------------------------------
 1 files changed, 18 insertions(+), 33 deletions(-)

diff --git a/block/cfq-iosched.c b/block/cfq-iosched.c
index 76f020f..bf2bc32 100644
--- a/block/cfq-iosched.c
+++ b/block/cfq-iosched.c
@@ -1139,16 +1139,6 @@ cfq_find_next_rq(struct cfq_data *cfqd, struct cfq_queue *cfqq,
 	return cfq_choose_req(cfqd, next, prev, blk_rq_pos(last));
 }
 
-static unsigned long cfq_slice_offset(struct cfq_data *cfqd,
-				      struct cfq_queue *cfqq)
-{
-	/*
-	 * just an approximation, should be ok.
-	 */
-	return (cfqq->cfqg->nr_cfqq - 1) * (cfq_prio_slice(cfqd, 1, 0) -
-		       cfq_prio_slice(cfqd, cfq_cfqq_sync(cfqq), cfqq->ioprio));
-}
-
 static inline s64
 cfqg_key(struct cfq_rb_root *st, struct cfq_group *cfqg)
 {
@@ -1625,41 +1615,36 @@ static void cfq_st_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
 	bool new_cfqq = RB_EMPTY_NODE(&cfqq->rb_node);
 
 	st = st_for(cfqq->cfqg, cfqq_class(cfqq), cfqq_type(cfqq));
-	if (cfq_class_idle(cfqq)) {
+
+	if (!new_cfqq) {
+		cfq_rb_erase(&cfqq->rb_node, cfqq->st);
+		cfqq->st = NULL;
+	}
+
+	if (!add_front) {
 		rb_key = CFQ_IDLE_DELAY;
 		parent = rb_last(&st->rb);
-		if (parent && parent != &cfqq->rb_node) {
+		if (parent) {
 			__cfqq = rb_entry(parent, struct cfq_queue, rb_node);
 			rb_key += __cfqq->rb_key;
 		} else
 			rb_key += jiffies;
-	} else if (!add_front) {
-		/*
-		 * Get our rb key offset. Subtract any residual slice
-		 * value carried from last service. A negative resid
-		 * count indicates slice overrun, and this should position
-		 * the next service time further away in the tree.
-		 */
-		rb_key = cfq_slice_offset(cfqd, cfqq) + jiffies;
-		rb_key -= cfqq->slice_resid;
-		cfqq->slice_resid = 0;
+		if (!cfq_class_idle(cfqq)) {
+			/*
+			 * Subtract any residual slice * value carried from
+			 * last service. A negative resid count indicates
+			 * slice overrun, and this should position
+			 * the next service time further away in the tree.
+			 */
+			rb_key -= cfqq->slice_resid;
+			cfqq->slice_resid = 0;
+		}
 	} else {
 		rb_key = -HZ;
 		__cfqq = cfq_rb_first(st);
 		rb_key += __cfqq ? __cfqq->rb_key : jiffies;
 	}
 
-	if (!new_cfqq) {
-		/*
-		 * same position, nothing more to do
-		 */
-		if (rb_key == cfqq->rb_key && cfqq->st == st)
-			return;
-
-		cfq_rb_erase(&cfqq->rb_node, cfqq->st);
-		cfqq->st = NULL;
-	}
-
 	left = 1;
 	parent = NULL;
 	cfqq->st = st;
-- 
1.7.7.6

[PATCH 11/15] cfq-iosched: Remove residual slice logic

[Vivek Goyal]

CFQ has this logic of residual slice so that a queue does not lose its
allocated share due to preemption. When when we move to vdisktime logic,
a queue will not lose its share even if it preempted. (It will get queued
back into service tree with smaller key and get selected to run again).

So scheduling algorithm will take care of making sure preempted queue
still gets the fair share. Hence remove the logic of residual slice.

Note: vdisktime patches for queues are ahead in the series. I am first
cleaning up the code.

Signed-off-by: Vivek Goyal <vgoyal@redhat.com>
---
 block/cfq-iosched.c |   53 +++++++++++++-------------------------------------
 1 files changed, 14 insertions(+), 39 deletions(-)

diff --git a/block/cfq-iosched.c b/block/cfq-iosched.c
index bf2bc32..a2016f5 100644
--- a/block/cfq-iosched.c
+++ b/block/cfq-iosched.c
@@ -128,7 +128,6 @@ struct cfq_queue {
 	/* time when first request from queue completed and slice started. */
 	unsigned long slice_start;
 	unsigned long slice_end;
-	long slice_resid;
 
 	/* pending priority requests */
 	int prio_pending;
@@ -1629,16 +1628,6 @@ static void cfq_st_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
 			rb_key += __cfqq->rb_key;
 		} else
 			rb_key += jiffies;
-		if (!cfq_class_idle(cfqq)) {
-			/*
-			 * Subtract any residual slice * value carried from
-			 * last service. A negative resid count indicates
-			 * slice overrun, and this should position
-			 * the next service time further away in the tree.
-			 */
-			rb_key -= cfqq->slice_resid;
-			cfqq->slice_resid = 0;
-		}
 	} else {
 		rb_key = -HZ;
 		__cfqq = cfq_rb_first(st);
@@ -2041,10 +2030,9 @@ static void __cfq_set_active_queue(struct cfq_data *cfqd,
  * current cfqq expired its slice (or was too idle), select new one
  */
 static void
-__cfq_slice_expired(struct cfq_data *cfqd, struct cfq_queue *cfqq,
-		    bool timed_out)
+__cfq_slice_expired(struct cfq_data *cfqd, struct cfq_queue *cfqq)
 {
-	cfq_log_cfqq(cfqd, cfqq, "slice expired t=%d", timed_out);
+	cfq_log_cfqq(cfqd, cfqq, "slice expired");
 
 	if (cfq_cfqq_wait_request(cfqq))
 		cfq_del_timer(cfqd, cfqq);
@@ -2061,17 +2049,6 @@ __cfq_slice_expired(struct cfq_data *cfqd, struct cfq_queue *cfqq,
 	if (cfq_cfqq_coop(cfqq) && CFQQ_SEEKY(cfqq))
 		cfq_mark_cfqq_split_coop(cfqq);
 
-	/*
-	 * store what was left of this slice, if the queue idled/timed out
-	 */
-	if (timed_out) {
-		if (cfq_cfqq_slice_new(cfqq))
-			cfqq->slice_resid = cfq_scaled_cfqq_slice(cfqd, cfqq);
-		else
-			cfqq->slice_resid = cfqq->slice_end - jiffies;
-		cfq_log_cfqq(cfqd, cfqq, "resid=%ld", cfqq->slice_resid);
-	}
-
 	cfq_group_served(cfqd, cfqq->cfqg, cfqq);
 
 	if (cfq_cfqq_on_rr(cfqq) && RB_EMPTY_ROOT(&cfqq->sort_list))
@@ -2088,12 +2065,12 @@ __cfq_slice_expired(struct cfq_data *cfqd, struct cfq_queue *cfqq,
 	}
 }
 
-static inline void cfq_slice_expired(struct cfq_data *cfqd, bool timed_out)
+static inline void cfq_slice_expired(struct cfq_data *cfqd)
 {
 	struct cfq_queue *cfqq = cfqd->active_queue;
 
 	if (cfqq)
-		__cfq_slice_expired(cfqd, cfqq, timed_out);
+		__cfq_slice_expired(cfqd, cfqq);
 }
 
 /*
@@ -2718,7 +2695,7 @@ check_group_idle:
 	}
 
 expire:
-	cfq_slice_expired(cfqd, 0);
+	cfq_slice_expired(cfqd);
 new_queue:
 	/*
 	 * Current queue expired. Check if we have to switch to a new
@@ -2744,7 +2721,7 @@ static int __cfq_forced_dispatch_cfqq(struct cfq_queue *cfqq)
 	BUG_ON(!list_empty(&cfqq->fifo));
 
 	/* By default cfqq is not expired if it is empty. Do it explicitly */
-	__cfq_slice_expired(cfqq->cfqd, cfqq, 0);
+	__cfq_slice_expired(cfqq->cfqd, cfqq);
 	return dispatched;
 }
 
@@ -2758,7 +2735,7 @@ static int cfq_forced_dispatch(struct cfq_data *cfqd)
 	int dispatched = 0;
 
 	/* Expire the timeslice of the current active queue first */
-	cfq_slice_expired(cfqd, 0);
+	cfq_slice_expired(cfqd);
 	while ((cfqq = cfq_get_next_queue_forced(cfqd)) != NULL) {
 		__cfq_set_active_queue(cfqd, cfqq);
 		dispatched += __cfq_forced_dispatch_cfqq(cfqq);
@@ -2939,7 +2916,7 @@ static int cfq_dispatch_requests(struct request_queue *q, int force)
 	    cfqq->slice_dispatch >= cfq_prio_to_maxrq(cfqd, cfqq)) ||
 	    cfq_class_idle(cfqq))) {
 		cfqq->slice_end = jiffies + 1;
-		cfq_slice_expired(cfqd, 0);
+		cfq_slice_expired(cfqd);
 	}
 
 	cfq_log_cfqq(cfqd, cfqq, "dispatched a request");
@@ -2970,7 +2947,7 @@ static void cfq_put_queue(struct cfq_queue *cfqq)
 	cfqg = cfqq->cfqg;
 
 	if (unlikely(cfqd->active_queue == cfqq)) {
-		__cfq_slice_expired(cfqd, cfqq, 0);
+		__cfq_slice_expired(cfqd, cfqq);
 		cfq_schedule_dispatch(cfqd);
 	}
 
@@ -3003,7 +2980,7 @@ static void cfq_put_cooperator(struct cfq_queue *cfqq)
 static void cfq_exit_cfqq(struct cfq_data *cfqd, struct cfq_queue *cfqq)
 {
 	if (unlikely(cfqq == cfqd->active_queue)) {
-		__cfq_slice_expired(cfqd, cfqq, 0);
+		__cfq_slice_expired(cfqd, cfqq);
 		cfq_schedule_dispatch(cfqd);
 	}
 
@@ -3437,7 +3414,7 @@ static void cfq_preempt_queue(struct cfq_data *cfqd, struct cfq_queue *cfqq)
 	enum wl_type_t old_type = cfqq_type(cfqd->active_queue);
 
 	cfq_log_cfqq(cfqd, cfqq, "preempt");
-	cfq_slice_expired(cfqd, 1);
+	cfq_slice_expired(cfqd);
 
 	/*
 	 * workload type is changed, don't save slice, otherwise preempt
@@ -3679,7 +3656,7 @@ static void cfq_completed_request(struct request_queue *q, struct request *rq)
 		 * - when there is a close cooperator
 		 */
 		if (cfq_slice_used(cfqq) || cfq_class_idle(cfqq))
-			cfq_slice_expired(cfqd, 1);
+			cfq_slice_expired(cfqd);
 		else if (sync && cfqq_empty &&
 			 !cfq_close_cooperator(cfqd, cfqq)) {
 			cfq_arm_slice_timer(cfqd);
@@ -3855,7 +3832,6 @@ static void cfq_idle_slice_timer(unsigned long data)
 	struct cfq_data *cfqd = (struct cfq_data *) data;
 	struct cfq_queue *cfqq;
 	unsigned long flags;
-	int timed_out = 1;
 
 	cfq_log(cfqd, "idle timer fired");
 
@@ -3863,7 +3839,6 @@ static void cfq_idle_slice_timer(unsigned long data)
 
 	cfqq = cfqd->active_queue;
 	if (cfqq) {
-		timed_out = 0;
 
 		/*
 		 * We saw a request before the queue expired, let it through
@@ -3896,7 +3871,7 @@ static void cfq_idle_slice_timer(unsigned long data)
 		cfq_clear_cfqq_deep(cfqq);
 	}
 expire:
-	cfq_slice_expired(cfqd, timed_out);
+	cfq_slice_expired(cfqd);
 out_kick:
 	cfq_schedule_dispatch(cfqd);
 out_cont:
@@ -3934,7 +3909,7 @@ static void cfq_exit_queue(struct elevator_queue *e)
 	spin_lock_irq(q->queue_lock);
 
 	if (cfqd->active_queue)
-		__cfq_slice_expired(cfqd, cfqd->active_queue, 0);
+		__cfq_slice_expired(cfqd, cfqd->active_queue);
 
 	cfq_put_async_queues(cfqd);
 
-- 
1.7.7.6

[PATCH 12/15] cfq-iosched: put cooperating queue at the front of service tree

[Vivek Goyal]

Currently during select_queue(), if a cfqq runs out of requests, cfq
checks if there is a cooperating queue doing IO nearby. If yes, it
lets that queue run out of turn.

But while doing so, CFQ does not put that queue at the front of service
tree and select it. It just forces it to be active queue.

This will not play very nice with new algorithm where we keep track
of min_vdisktime on service tree and always select first queue on
the service tree to run.

So instead of force setting active queue, put desired cooperating
queue at the front of service tree (like preemption), and then
go through get_next_cfqq() to select first queue on service tree.

So end result still remains the same, just that this method will
play better with new algorithm.

Signed-off-by: Vivek Goyal <vgoyal@redhat.com>
---
 block/cfq-iosched.c |   15 ++++++++++-----
 1 files changed, 10 insertions(+), 5 deletions(-)

diff --git a/block/cfq-iosched.c b/block/cfq-iosched.c
index a2016f5..8912051 100644
--- a/block/cfq-iosched.c
+++ b/block/cfq-iosched.c
@@ -2116,12 +2116,11 @@ static struct cfq_queue *cfq_get_next_queue_forced(struct cfq_data *cfqd)
 /*
  * Get and set a new active queue for service.
  */
-static struct cfq_queue *cfq_set_active_queue(struct cfq_data *cfqd,
-					      struct cfq_queue *cfqq)
+static struct cfq_queue *cfq_set_active_queue(struct cfq_data *cfqd)
 {
-	if (!cfqq)
-		cfqq = cfq_get_next_queue(cfqd);
+	struct cfq_queue *cfqq;
 
+	cfqq = cfq_get_next_queue(cfqd);
 	__cfq_set_active_queue(cfqd, cfqq);
 	return cfqq;
 }
@@ -2651,6 +2650,12 @@ static struct cfq_queue *cfq_select_queue(struct cfq_data *cfqd)
 	 */
 	new_cfqq = cfq_close_cooperator(cfqd, cfqq);
 	if (new_cfqq) {
+		/*
+		 * This close cooperator queue will be selected next. Put
+		 * it at the front of servie tree and then go through normal
+		 * get_next_queue() logic.
+		 */
+		cfq_st_add(cfqd, new_cfqq, 1);
 		if (!cfqq->new_cfqq)
 			cfq_setup_merge(cfqq, new_cfqq);
 		goto expire;
@@ -2704,7 +2709,7 @@ new_queue:
 	if (!new_cfqq)
 		cfq_choose_cfqg(cfqd);
 
-	cfqq = cfq_set_active_queue(cfqd, new_cfqq);
+	cfqq = cfq_set_active_queue(cfqd);
 keep_queue:
 	return cfqq;
 }
-- 
1.7.7.6

[PATCH 13/15] cfq-iosched: Use same scheduling algorithm for groups and queues

[Vivek Goyal]

Ok, finally, this patch introduces the notion of vdisktime for queues
and uses same scheduling algorithm for queues as groups.

It does not merge the two code paths yet, but philosophy of scheduling
is same. Once this gets stablized, then we will require some more
changes to the code to actually share the scheduling code between
queue and groups.

One important change here is mapping of io priority to weights. Current
prio levels 0-7 are mapped over weight range 1000-1, as follows.

prio	  0     1    2    3    4   5    6    7
weight	 1000  875  750  625  500 375  250  125

Now ideally the ratio of disk share between prio 0 and 7 should
be 8 (1000/125). That is prio 0 task gets 8 times the disk share
of prio 7 task.

This patch does treat queue and groups at same level. Existing scheme
of flat hierarchy continues. This series is just preparing CFQ for
more changes.

After this patch, CFQ queues get disk time share in proportion to
their prio/weight. One interesting observation is that some queues
do not do higher amount of IO despite getting higher share of disk
time. Looking at blktrace, it looks as if disk slows down and completion
time goes up if a single queue if running for long. Not sure what to
do about it. May be it is just my hardware.

Signed-off-by: Vivek Goyal <vgoyal@redhat.com>
---
 block/cfq-iosched.c |  154 ++++++++++++++++++++++++++++++++++++++-------------
 1 files changed, 115 insertions(+), 39 deletions(-)

diff --git a/block/cfq-iosched.c b/block/cfq-iosched.c
index 8912051..732e465 100644
--- a/block/cfq-iosched.c
+++ b/block/cfq-iosched.c
@@ -105,7 +105,7 @@ struct cfq_queue {
 	/* service_tree member */
 	struct rb_node rb_node;
 	/* service_tree key */
-	unsigned long rb_key;
+	u64 vdisktime;
 	/* prio tree member */
 	struct rb_node p_node;
 	/* prio tree root we belong to, if any */
@@ -355,6 +355,18 @@ struct cfq_data {
 	unsigned long last_delayed_sync;
 };
 
+/*
+ * Map cfqq prio to weights.
+ * Prio 0-7 is mapped to weight range 0 - CFQ_WEIGHT_MAX
+ */
+static inline int cfq_prio_to_weight(unsigned short ioprio)
+{
+	unsigned int weight;
+
+	weight = (CFQ_WEIGHT_MAX * (IOPRIO_BE_NR-ioprio))/IOPRIO_BE_NR;
+	return weight;
+}
+
 static struct cfq_group *cfq_get_next_cfqg(struct cfq_data *cfqd);
 
 static struct cfq_rb_root *st_for(struct cfq_group *cfqg,
@@ -843,10 +855,12 @@ static inline int cfq_prio_slice(struct cfq_data *cfqd, bool sync,
 				 unsigned short prio)
 {
 	const int base_slice = cfqd->cfq_slice[sync];
+	unsigned int weight = cfq_prio_to_weight(prio);
 
 	WARN_ON(prio >= IOPRIO_BE_NR);
 
-	return base_slice + (base_slice/CFQ_SLICE_SCALE * (4 - prio));
+	/* scale base slice according to proportionate weight */
+	return (2 * base_slice * weight)/CFQ_WEIGHT_MAX;
 }
 
 static inline int
@@ -882,7 +896,7 @@ static inline u64 min_vdisktime(u64 min_vdisktime, u64 vdisktime)
 	return min_vdisktime;
 }
 
-static void update_min_vdisktime(struct cfq_rb_root *st)
+static void update_min_vdisktime_group(struct cfq_rb_root *st)
 {
 	struct cfq_group *cfqg;
 
@@ -893,6 +907,17 @@ static void update_min_vdisktime(struct cfq_rb_root *st)
 	}
 }
 
+static void update_min_vdisktime_queue(struct cfq_rb_root *st)
+{
+	struct cfq_queue *cfqq;
+
+	if (st->left) {
+		cfqq = rb_entry(st->left, struct cfq_queue, rb_node);
+		st->min_vdisktime = max_vdisktime(st->min_vdisktime,
+						  cfqq->vdisktime);
+	}
+}
+
 /*
  * get averaged number of queues of RT/BE priority.
  * average is updated, with a formula that gives more weight to higher numbers,
@@ -1143,6 +1168,11 @@ cfqg_key(struct cfq_rb_root *st, struct cfq_group *cfqg)
 {
 	return cfqg->vdisktime - st->min_vdisktime;
 }
+static inline s64
+cfqq_key(struct cfq_rb_root *st, struct cfq_queue *cfqq)
+{
+	return cfqq->vdisktime - st->min_vdisktime;
+}
 
 static void __cfq_group_st_add(struct cfq_rb_root *st, struct cfq_group *cfqg)
 {
@@ -1598,54 +1628,73 @@ cfq_link_cfqq_cfqg(struct cfq_queue *cfqq, struct cfq_group *cfqg) {
 
 #endif /* GROUP_IOSCHED */
 
-/*
- * The cfqd->st holds all pending cfq_queue's that have
- * requests waiting to be processed. It is sorted in the order that
- * we will service the queues.
- */
-static void cfq_st_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
-				 bool add_front)
+static u64 calc_st_last_entry_vdisktime(struct cfq_rb_root *st)
 {
-	struct rb_node **p, *parent;
 	struct cfq_queue *__cfqq;
-	unsigned long rb_key;
+	struct rb_node *parent;
+
+	parent = rb_last(&st->rb);
+	if (parent) {
+		__cfqq = rb_entry(parent, struct cfq_queue, rb_node);
+		return (__cfqq->vdisktime + CFQ_IDLE_DELAY);
+	} else
+		return st->min_vdisktime;
+}
+
+static u64 calc_cfqq_vdisktime(struct cfq_queue *cfqq, bool add_front,
+			bool new_cfqq, struct cfq_rb_root *old_st)
+{
+
+	unsigned int charge, unaccounted_sl = 0, weight;
 	struct cfq_rb_root *st;
-	int left;
-	bool new_cfqq = RB_EMPTY_NODE(&cfqq->rb_node);
 
 	st = st_for(cfqq->cfqg, cfqq_class(cfqq), cfqq_type(cfqq));
 
-	if (!new_cfqq) {
-		cfq_rb_erase(&cfqq->rb_node, cfqq->st);
-		cfqq->st = NULL;
-	}
+	/*
+	 * This queue is being added to the front. This is overriding
+	 * fairness algorithm so charging for disk time does not make
+	 * any difference
+	 */
+	if (add_front)
+		return st->min_vdisktime;
 
-	if (!add_front) {
-		rb_key = CFQ_IDLE_DELAY;
-		parent = rb_last(&st->rb);
-		if (parent) {
-			__cfqq = rb_entry(parent, struct cfq_queue, rb_node);
-			rb_key += __cfqq->rb_key;
-		} else
-			rb_key += jiffies;
-	} else {
-		rb_key = -HZ;
-		__cfqq = cfq_rb_first(st);
-		rb_key += __cfqq ? __cfqq->rb_key : jiffies;
-	}
+	/* A new queue is being added. Just add it to end of service tree */
+	if (new_cfqq)
+		return calc_st_last_entry_vdisktime(st);
+
+	/*
+	 * A queue is being requeued. If service tree has changed, then
+	 * just put the queue at the end of current entries.
+	 * */
+	if (st != old_st)
+		return calc_st_last_entry_vdisktime(st);
+
+	/*
+	 * A cfqq is being requeued on same st. Charge the amount of slice
+	 * used
+	 */
+	weight = cfq_prio_to_weight(cfqq->ioprio);
+	charge = cfq_cfqq_slice_usage(cfqq, &unaccounted_sl);
+	return cfqq->vdisktime + cfq_scale_slice(charge, weight);
+}
+
+static void __cfq_st_add(struct cfq_queue *cfqq, bool add_front)
+{
+	int left;
+	struct cfq_rb_root *st = cfqq->st;
+	struct rb_node **p, *parent;
+	struct cfq_queue *__cfqq;
+	s64 key = cfqq_key(st, cfqq);
 
 	left = 1;
 	parent = NULL;
-	cfqq->st = st;
 	p = &st->rb.rb_node;
 	while (*p) {
 		parent = *p;
 		__cfqq = rb_entry(parent, struct cfq_queue, rb_node);
 
-		/*
-		 * sort by key, that represents service time.
-		 */
-		if (time_before(rb_key, __cfqq->rb_key))
+		if (key < cfqq_key(st, __cfqq) ||
+		    ((add_front == true) && key == cfqq_key(st, __cfqq)))
 			p = &parent->rb_left;
 		else {
 			p = &parent->rb_right;
@@ -1656,10 +1705,34 @@ static void cfq_st_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
 	if (left)
 		st->left = &cfqq->rb_node;
 
-	cfqq->rb_key = rb_key;
 	rb_link_node(&cfqq->rb_node, parent, p);
 	rb_insert_color(&cfqq->rb_node, &st->rb);
 	st->count++;
+}
+
+/*
+ * The cfqd->st holds all pending cfq_queue's that have
+ * requests waiting to be processed. It is sorted in the order that
+ * we will service the queues.
+ */
+static void cfq_st_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
+				 bool add_front)
+{
+	struct cfq_rb_root *st, *old_st;
+	bool new_cfqq = RB_EMPTY_NODE(&cfqq->rb_node);
+
+	st = st_for(cfqq->cfqg, cfqq_class(cfqq), cfqq_type(cfqq));
+	old_st = cfqq->st;
+
+	if (!new_cfqq) {
+		cfq_rb_erase(&cfqq->rb_node, cfqq->st);
+		cfqq->st = NULL;
+	}
+
+	cfqq->vdisktime = calc_cfqq_vdisktime(cfqq, add_front, new_cfqq,
+							old_st);
+	cfqq->st = st;
+	__cfq_st_add(cfqq, add_front);
 	if (add_front || !new_cfqq)
 		return;
 	cfq_group_notify_queue_add(cfqd, cfqq->cfqg);
@@ -2081,6 +2154,7 @@ static struct cfq_queue *cfq_get_next_queue(struct cfq_data *cfqd)
 {
 	struct cfq_rb_root *st =
 		st_for(cfqd->serving_group, cfqd->wl_class, cfqd->wl_type);
+	struct cfq_queue *cfqq;
 
 	if (!cfqd->rq_queued)
 		return NULL;
@@ -2090,7 +2164,9 @@ static struct cfq_queue *cfq_get_next_queue(struct cfq_data *cfqd)
 		return NULL;
 	if (RB_EMPTY_ROOT(&st->rb))
 		return NULL;
-	return cfq_rb_first(st);
+	cfqq = cfq_rb_first(st);
+	update_min_vdisktime_queue(st);
+	return cfqq;
 }
 
 static struct cfq_queue *cfq_get_next_queue_forced(struct cfq_data *cfqd)
@@ -2572,7 +2648,7 @@ static struct cfq_group *cfq_get_next_cfqg(struct cfq_data *cfqd)
 	if (RB_EMPTY_ROOT(&st->rb))
 		return NULL;
 	cfqg = cfq_rb_first_group(st);
-	update_min_vdisktime(st);
+	update_min_vdisktime_group(st);
 	return cfqg;
 }
 
-- 
1.7.7.6

[PATCH 14/15] cfq-iosched: Wait for queue to get busy even if this is not last queue in group

[Vivek Goyal]

With new algorithm, to maintain fairness we need to make sure that queue
does not get deleted from tree at slice expiry. Otherwise when new
request comes in very shortly after deletion, queue gets queued at
the end of service tree.

In general it is not too much of a problem as we had scaled slice
length based on prio/weight scaling to begin with. But low_latency
logic might introduce some imperfections.

We intoroduced wait for queue to get backlogged logic already. Just
that we trigger it only when queue is last queue in the group (In
an attempt to provide group its fair share). Just extend same wait
busy logic to queue too.

Because this little extra wait happens only if we have been idling
all along on the queue, I am not expecting any serious impact of this
little extra idling.

Signed-off-by: Vivek Goyal <vgoyal@redhat.com>
---
 block/cfq-iosched.c |    8 ++------
 1 files changed, 2 insertions(+), 6 deletions(-)

diff --git a/block/cfq-iosched.c b/block/cfq-iosched.c
index 732e465..7d1fa41 100644
--- a/block/cfq-iosched.c
+++ b/block/cfq-iosched.c
@@ -2685,7 +2685,7 @@ static struct cfq_queue *cfq_select_queue(struct cfq_data *cfqd)
 		return NULL;
 
 	/*
-	 * We were waiting for group to get backlogged. Expire the queue
+	 * We were waiting for queue to get backlogged. Expire the queue
 	 */
 	if (cfq_cfqq_wait_busy(cfqq) && !RB_EMPTY_ROOT(&cfqq->sort_list))
 		goto expire;
@@ -2703,7 +2703,7 @@ static struct cfq_queue *cfq_select_queue(struct cfq_data *cfqd)
 		 * have been idling all along on this queue and it should be
 		 * ok to wait for this request to complete.
 		 */
-		if (cfqq->cfqg->nr_cfqq == 1 && RB_EMPTY_ROOT(&cfqq->sort_list)
+		if (RB_EMPTY_ROOT(&cfqq->sort_list)
 		    && cfqq->dispatched && cfq_should_idle(cfqd, cfqq)) {
 			cfqq = NULL;
 			goto keep_queue;
@@ -3631,10 +3631,6 @@ static bool cfq_should_wait_busy(struct cfq_data *cfqd, struct cfq_queue *cfqq)
 	if (!RB_EMPTY_ROOT(&cfqq->sort_list))
 		return false;
 
-	/* If there are other queues in the group, don't wait */
-	if (cfqq->cfqg->nr_cfqq > 1)
-		return false;
-
 	/* the only queue in the group, but think time is big */
 	if (cfq_io_thinktime_big(cfqd, &cfqq->cfqg->ttime, true))
 		return false;
-- 
1.7.7.6

[PATCH 15/15] cfq-ioschd: Give boost to higher prio/weight queues

[Vivek Goyal]

Though vdisktime based scheduling will take care of providng a queue
its fair share time of disk, the service differentiation between prio
levels is not as pronounced as with unpatched kernel. One of the reason
is that I got rid of cfq_slice_offset() logic which will do some
approximations to allow more than fair share of disk time to higher
prio queues.

This patch does intorduce a boost logic which provides vdisktime boost
to queues based on their weights. Higher the prio/weight, higher the
boost. So higher priority queues end up getting more than their fair
disk share.

I noticed another oddity during testing and that is that even I
provide higher disk slice to a queue, it does not seem to be doing
higher amount of IO. Somehow disk seems to slow down and delays the
completions of IO. Not sure how that can happen and how to tackle
that.

This arbitrary approximation is primarily there to provide bigger
service differentiation between various prio levels. I think we
should get rid of it when we merge queue and group scheduling logic.

Signed-off-by: Vivek Goyal <vgoyal@redhat.com>
---
 block/cfq-iosched.c |   44 +++++++++++++++++++++++++++++++++++++++++---
 1 files changed, 41 insertions(+), 3 deletions(-)

diff --git a/block/cfq-iosched.c b/block/cfq-iosched.c
index 7d1fa41..a2f7e8d 100644
--- a/block/cfq-iosched.c
+++ b/block/cfq-iosched.c
@@ -1641,12 +1641,45 @@ static u64 calc_st_last_entry_vdisktime(struct cfq_rb_root *st)
 		return st->min_vdisktime;
 }
 
+/*
+ * Give boost to a queue based on its ioprio. This is very approximate
+ * and arbitrary boost to give higher prio queues even greater share of
+ * disk than what they are entitled to based on their weight. So why
+ * to do this. Two reasons.
+ *
+ * - Provide more service differentation between queues and keep it inline
+ *   with exisitng logic.
+ *
+ * - vdisktime logic works only if we are idling on the queue. For SSD
+ *   we might skip idling and this logic will help to provide some kind
+ *   of service differentiation. Most of the time this will not help as
+ *   there are not enough processes doing IO. If SSD has deep queue depth,
+ *   readers will be blocked as their request is with driver/device and
+ *   there are not enough readers on service tree to create service
+ *   differentiation. So this might kick in only you have 32/64 or
+ *   greater processes doing IO.
+ *
+ * I think we should do away with this boost logic some day.
+ */
+static u64 calc_cfqq_vdisktime_boost(struct cfq_rb_root *st,
+			struct cfq_queue *cfqq)
+{
+	u64 spread;
+	unsigned int weight = cfq_prio_to_weight(cfqq->ioprio);
+
+	spread = calc_st_last_entry_vdisktime(st) - st->min_vdisktime;
+
+	/* divide 50% of spread in proportion to weight as boost */
+	return (spread * weight)/(2*CFQ_WEIGHT_MAX);
+}
+
 static u64 calc_cfqq_vdisktime(struct cfq_queue *cfqq, bool add_front,
 			bool new_cfqq, struct cfq_rb_root *old_st)
 {
 
 	unsigned int charge, unaccounted_sl = 0, weight;
 	struct cfq_rb_root *st;
+	u64 vdisktime, boost;
 
 	st = st_for(cfqq->cfqg, cfqq_class(cfqq), cfqq_type(cfqq));
 
@@ -1659,8 +1692,11 @@ static u64 calc_cfqq_vdisktime(struct cfq_queue *cfqq, bool add_front,
 		return st->min_vdisktime;
 
 	/* A new queue is being added. Just add it to end of service tree */
-	if (new_cfqq)
-		return calc_st_last_entry_vdisktime(st);
+	if (new_cfqq) {
+		vdisktime = calc_st_last_entry_vdisktime(st);
+		boost = calc_cfqq_vdisktime_boost(st, cfqq);
+		return max_t(u64, st->min_vdisktime, (vdisktime - boost));
+	}
 
 	/*
 	 * A queue is being requeued. If service tree has changed, then
@@ -1675,7 +1711,9 @@ static u64 calc_cfqq_vdisktime(struct cfq_queue *cfqq, bool add_front,
 	 */
 	weight = cfq_prio_to_weight(cfqq->ioprio);
 	charge = cfq_cfqq_slice_usage(cfqq, &unaccounted_sl);
-	return cfqq->vdisktime + cfq_scale_slice(charge, weight);
+	vdisktime = cfqq->vdisktime + cfq_scale_slice(charge, weight);
+	boost = calc_cfqq_vdisktime_boost(st, cfqq);
+	return max_t(u64, st->min_vdisktime, (vdisktime - boost));
 }
 
 static void __cfq_st_add(struct cfq_queue *cfqq, bool add_front)
-- 
1.7.7.6

Re: [PATCH 02/15] cfq-iosched: More renaming to better represent wl_class and wl_type

[Jeff Moyer]

Vivek Goyal <vgoyal@redhat.com> writes:

> Also at places I have got rid of keyword "serving" as it is obivious.

I don't agree with getting rid of serving.  After your patch, it looks
as though a cfqd has a static workload class and type.  It reads better
to me the way it is.

Cheers,
Jeff

Re: [PATCH 01/15] cfq-iosched: Properly name all references to IO class

[Jeff Moyer]

Vivek Goyal <vgoyal@redhat.com> writes:

> Currently CFQ has three IO classes, RT, BE and IDLE. At many a places we
> are calling workloads belonging to these classes as "prio". This gets
> very confusing as one starts to associate it with ioprio.
>
> So this patch just does bunch of renaming so that reading code becomes
> easier. All reference to RT, BE and IDLE workload are done using keyword
> "class" and all references to subclass, SYNC, SYNC-IDLE, ASYNC are made
> using keyword "type".
>
> This makes me feel much better while I am reading the code. There is no
> functionality change due to this patch.
>
> Signed-off-by: Vivek Goyal <vgoyal@redhat.com>

Thank you!

Acked-by: Jeff Moyer <jmoyer@redhat.com>

Re: [PATCH 03/15] cfq-iosched: Rename "service_tree" to "st"

[Jeff Moyer]

Vivek Goyal <vgoyal@redhat.com> writes:

> At quite a few places we use the keyword "service_tree" and I feel that
> names in CFQ are already very long and they need to be shortened a bit
> where appropriate.
>
> So this patch just renames "service_tree" to "st" at most of the places.
> No functionality change.

NACK.

> -	struct cfq_rb_root service_trees[2][3];
> -	struct cfq_rb_root service_tree_idle;
> +	struct cfq_rb_root sts[2][3];
> +	struct cfq_rb_root st_idle;

Honestly, who looks at sts and thinks "service trees?"

Re: [PATCH 04/15] cfq-iosched: Rename few functions related to selecting workload

[Jeff Moyer]

Vivek Goyal <vgoyal@redhat.com> writes:

> choose_st() selects/sets both wl_class and wl_type.  Rename it to
> choose_wl_class_and_type() to make it very clear.
>
> cfq_choose_wl() only selects and sets wl_type. It is easy to confuse
> it with choose_st(). So rename it to cfq_choose_wl_type() to make
> it clear what does it do.
>
> Just renaming. No functionality change.
>
> Signed-off-by: Vivek Goyal <vgoyal@redhat.com>

No objections.

Acked-by: Jeff Moyer <jmoyer@redhat.com>

Re: [PATCH 05/15] cfq-iosched: Get rid of unnecessary local variable

[Jeff Moyer]

Vivek Goyal <vgoyal@redhat.com> writes:

> Use of local varibale "n" seems to be unnecessary. Remove it. This brings
> it inline with function __cfq_group_st_add(), which is also doing the
> similar operation of adding a group to a rb tree.
>
> No functionality change here.

Agreed.

Acked-by: Jeff Moyer <jmoyer@redhat.com>

Re: [PATCH 06/15] cfq-iosched: Print sync-noidle information in blktrace messages

[Jeff Moyer]

Vivek Goyal <vgoyal@redhat.com> writes:

> Currently we attach a character "S" or "A" to the cfqq<pid>, to represent
> whether queues is sync or async. Add one more character "N" to represent
> whether it is sync-noidle queue or sync queue. So now three different
> type of queues will look as follows.
>
> cfq1234S   --> sync queus
> cfq1234SN  --> sync noidle queue
> cfq1234A   --> Async queue
>
> Previously S/A classification was being printed only if group scheduling
> was enabled. This patch also makes sure that this classification is
> displayed even if group idling is disabled.
>
> Signed-off-by: Vivek Goyal <vgoyal@redhat.com>

I'm assuming nobody relies on the contents of trace_message output not
changing in blktrace output.

Acked-by: Jeff Moyer <jmoyer@redhat.com>

Re: [PATCH 02/15] cfq-iosched: More renaming to better represent wl_class and wl_type

[Vivek Goyal]

On Mon, Oct 01, 2012 at 04:50:37PM -0400, Jeff Moyer wrote:
> Vivek Goyal <vgoyal@redhat.com> writes:
> 
> > Also at places I have got rid of keyword "serving" as it is obivious.
> 
> I don't agree with getting rid of serving.  After your patch, it looks
> as though a cfqd has a static workload class and type.  It reads better
> to me the way it is.

It is also about the length of name. To me now a days CFQ code looks
pretty messy with very long names or lines at many a places.

So yes, "cfqd->serving_wl_class" and "cfqd->serving_wl_type" is more
readable than "cfqd->wl_class" and "cfqd->wl_type". But it also 
increases the string length significantly.

I don't know. Some of the strings seem too long and code spills into
multiple lines for a single statement.

Anyway, for this I guess I will retain "serving" keyword.

Thanks
Vivek

Re: [PATCH 03/15] cfq-iosched: Rename "service_tree" to "st"

[Vivek Goyal]

On Mon, Oct 01, 2012 at 04:52:13PM -0400, Jeff Moyer wrote:
> Vivek Goyal <vgoyal@redhat.com> writes:
> 
> > At quite a few places we use the keyword "service_tree" and I feel that
> > names in CFQ are already very long and they need to be shortened a bit
> > where appropriate.
> >
> > So this patch just renames "service_tree" to "st" at most of the places.
> > No functionality change.
> 
> NACK.
> 
> > -	struct cfq_rb_root service_trees[2][3];
> > -	struct cfq_rb_root service_tree_idle;
> > +	struct cfq_rb_root sts[2][3];
> > +	struct cfq_rb_root st_idle;
> 
> Honestly, who looks at sts and thinks "service trees?"

Yes this one is little odd. Ok, I will change it back to "service_tree"
and only use "st" for local variables and in some function names.

Vivek

Re: [PATCH 01/15] cfq-iosched: Properly name all references to IO class

[Tejun Heo]

On Mon, Oct 01, 2012 at 03:32:42PM -0400, Vivek Goyal wrote:
> Currently CFQ has three IO classes, RT, BE and IDLE. At many a places we
> are calling workloads belonging to these classes as "prio". This gets
> very confusing as one starts to associate it with ioprio.
> 
> So this patch just does bunch of renaming so that reading code becomes
> easier. All reference to RT, BE and IDLE workload are done using keyword
> "class" and all references to subclass, SYNC, SYNC-IDLE, ASYNC are made
> using keyword "type".
> 
> This makes me feel much better while I am reading the code. There is no
> functionality change due to this patch.
> 
> Signed-off-by: Vivek Goyal <vgoyal@redhat.com>

Acked-by: Tejun Heo <tj@kernel.org>

> @@ -751,16 +751,16 @@ static enum wl_type_t cfqq_type(struct cfq_queue *cfqq)
>  	return SYNC_WORKLOAD;
>  }
>  
> -static inline int cfq_group_busy_queues_wl(enum wl_prio_t wl,
> +static inline int cfq_group_busy_queues_wl(enum wl_class_t wl_class,
>  					struct cfq_data *cfqd,
>  					struct cfq_group *cfqg)
>  {
> -	if (wl == IDLE_WORKLOAD)
> +	if (wl_class == IDLE_WORKLOAD)
>  		return cfqg->service_tree_idle.count;
>  
> -	return cfqg->service_trees[wl][ASYNC_WORKLOAD].count
> -		+ cfqg->service_trees[wl][SYNC_NOIDLE_WORKLOAD].count
> -		+ cfqg->service_trees[wl][SYNC_WORKLOAD].count;
> +	return cfqg->service_trees[wl_class][ASYNC_WORKLOAD].count
> +		+ cfqg->service_trees[wl_class][SYNC_NOIDLE_WORKLOAD].count
> +		+ cfqg->service_trees[wl_class][SYNC_WORKLOAD].count;

While at it, maybe move the operator to the end of the preceding line
like everybody else?

Thanks.

-- 
tejun

Re: [PATCH 03/15] cfq-iosched: Rename "service_tree" to "st"

[Tejun Heo]

Hello,

On Tue, Oct 02, 2012 at 09:26:03AM -0400, Vivek Goyal wrote:
> Yes this one is little odd. Ok, I will change it back to "service_tree"
> and only use "st" for local variables and in some function names.

Yes, please do that.  In general, it's beneficial to use at least
somewhat descriptive names for globals / struct fields and use
consistent shorthands for local variables dealing with them.

Thanks.

-- 
tejun

Re: [PATCH 01/15] cfq-iosched: Properly name all references to IO class

[Vivek Goyal]

On Wed, Oct 03, 2012 at 09:54:29AM +0900, Tejun Heo wrote:

[..]
> > -	return cfqg->service_trees[wl][ASYNC_WORKLOAD].count
> > -		+ cfqg->service_trees[wl][SYNC_NOIDLE_WORKLOAD].count
> > -		+ cfqg->service_trees[wl][SYNC_WORKLOAD].count;
> > +	return cfqg->service_trees[wl_class][ASYNC_WORKLOAD].count
> > +		+ cfqg->service_trees[wl_class][SYNC_NOIDLE_WORKLOAD].count
> > +		+ cfqg->service_trees[wl_class][SYNC_WORKLOAD].count;
> 
> While at it, maybe move the operator to the end of the preceding line
> like everybody else?

Ok, will do.

Thanks
Vivek