cfq-iosched: Introduce cfq_entity for CFQ queue

On Mon, Dec 27, 2010 at 04:50:51PM +0800, Gui Jianfeng wrote:

[..]

Quoted 6 lines

block/cfq-iosched.c +1 -1

-static struct cfq_group *cfq_rb_first_group(struct cfq_rb_root *root)
+static struct cfq_entity *cfq_rb_first_entity(struct cfq_rb_root *root)
 {
 	if (!root->left)
 		root->left = rb_first(&root->rb);

block/cfq-iosched.c static struct cfq_entity *cfq_rb_first(struct cfq_rb_root *root) · line 798

Quoted 4 lines

block/cfq-iosched.c +1 -1

 	if (root->left)
-		return rb_entry_cfqg(root->left);
+		return rb_entry_entity(root->left);

Why are we defining cfq_rb_first_entity(). Can't we simply use cfq_rb_first() as introduced in first patch.

Thanks
Vivek

On Mon, Dec 27, 2010 at 04:50:51PM +0800, Gui Jianfeng wrote:

[..]

Quoted 6 lines

block/cfq-iosched.c +1 -1

-static struct cfq_group *cfq_rb_first_group(struct cfq_rb_root *root)
+static struct cfq_entity *cfq_rb_first_entity(struct cfq_rb_root *root)
 {
 	if (!root->left)
 		root->left = rb_first(&root->rb);

block/cfq-iosched.c static struct cfq_entity *cfq_rb_first(struct cfq_rb_root *root) · line 798

Quoted 4 lines

block/cfq-iosched.c +1 -1

 	if (root->left)
-		return rb_entry_cfqg(root->left);
+		return rb_entry_entity(root->left);

Why are we defining cfq_rb_first_entity(). Can't we simply use cfq_rb_first() as introduced in first patch.

Thanks
Vivek

Introduce vdisktime and io weight for CFQ queue scheduling. Currently, io priority maps to a range [100,1000]. It also gets rid of cfq_slice_offset() logic and makes use the same scheduling algorithm as CFQ group does. This helps for CFQ queue and group scheduling on the same service tree.

Signed-off-by Gui Jianfeng <[email protected]>

---
 block/cfq-iosched.c |  211 ++++++++++++++++++++++++++++++++++++++-------------
 1 files changed, 158 insertions(+), 53 deletions(-)

block/cfq-iosched.c +21 -14

index a2553c0..b598798 100644
@@ -100,10 +100,7 @@ struct cfq_entity {
        struct cfq_rb_root *service_tree;
        /* service_tree member */
        struct rb_node rb_node;
-       /* service_tree key, represent the position on the tree */
-       unsigned long rb_key;
-
-       /* group service_tree key */
+       /* service_tree key */
        u64 vdisktime;
        bool is_group_entity;
        unsigned int weight;

@@ -115,6 +112,8 @@ struct cfq_entity {
 struct cfq_queue {
        /* The schedule entity */
        struct cfq_entity cfqe;
+       /* Reposition time */
+       unsigned long reposition_time;
        /* reference count */
        atomic_t ref;
        /* various state flags, see below */

@@ -313,6 +312,24 @@ struct cfq_data {
        struct rcu_head rcu;
 };
 
+/*
+ * Map io priority(7 ~ 0) to io weight(100 ~ 1000) as follows
+ *     prio       0    1     2    3    4    5    6     7
+ *     weight  1000  868   740  612  484  356  228   100
+ */
+static inline unsigned int cfq_prio_to_weight(unsigned short ioprio)
+{
+       unsigned int step;
+
+       BUG_ON(ioprio >= IOPRIO_BE_NR);
+
+       step = (BLKIO_WEIGHT_MAX - BLKIO_WEIGHT_MIN) / (IOPRIO_BE_NR - 1);
+       if (ioprio == 0)
+               return BLKIO_WEIGHT_MAX;
+
+       return BLKIO_WEIGHT_MIN + (IOPRIO_BE_NR - ioprio - 1) * step;
+}
+
 static inline struct cfq_queue *
 cfqq_of_entity(struct cfq_entity *cfqe)
 {

@@ -841,16 +858,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
 entity_key(struct cfq_rb_root *st, struct cfq_entity *entity)
 {

@@ -1199,6 +1206,16 @@ static inline void cfq_put_cfqg(struct cfq_group *cfqg) {}
 
 #endif /* GROUP_IOSCHED */

block/cfq-iosched.c +20 -4

+
 /*
  * The cfqd->service_trees holds all pending cfq_queue's that have
  * requests waiting to be processed. It is sorted in the order that

@@ -1210,13 +1227,14 @@ static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
        struct cfq_entity *cfqe;
        struct rb_node **p, *parent;
        struct cfq_entity *__cfqe;
-       unsigned long rb_key;
-       struct cfq_rb_root *service_tree;
+       struct cfq_rb_root *service_tree, *orig_st;
        int left;
        int new_cfqq = 1;
        int group_changed = 0;
+       s64 key;
 
        cfqe = &cfqq->cfqe;
+       orig_st = cfqe->service_tree;
 
 #ifdef CONFIG_CFQ_GROUP_IOSCHED
        if (!cfqd->cfq_group_isolation

@@ -1224,8 +1242,15 @@ static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
            && cfqq->cfqg && cfqq->cfqg != &cfqd->root_group) {
                /* Move this cfq to root group */
                cfq_log_cfqq(cfqd, cfqq, "moving to root group");
-               if (!RB_EMPTY_NODE(&cfqe->rb_node))
+               if (!RB_EMPTY_NODE(&cfqe->rb_node)) {
                        cfq_group_service_tree_del(cfqd, cfqq->cfqg);
+                       /*
+                        * Group changed, dequeue this CFQ queue from the
+                        * original service tree.
+                        */
+                       cfq_rb_erase(&cfqe->rb_node, cfqe->service_tree);
+                       orig_st->total_weight -= cfqe->weight;
+               }
                cfqq->orig_cfqg = cfqq->cfqg;
                cfqq->cfqg = &cfqd->root_group;
                atomic_inc(&cfqd->root_group.ref);

@@ -1234,8 +1259,15 @@ static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
                   && cfqq_type(cfqq) == SYNC_WORKLOAD && cfqq->orig_cfqg) {
                /* cfqq is sequential now needs to go to its original group */
                BUG_ON(cfqq->cfqg != &cfqd->root_group);
-               if (!RB_EMPTY_NODE(&cfqe->rb_node))
+               if (!RB_EMPTY_NODE(&cfqe->rb_node)) {
                        cfq_group_service_tree_del(cfqd, cfqq->cfqg);
+                       /*
+                        * Group changed, dequeue this CFQ queue from the
+                        * original service tree.
+                        */
+                       cfq_rb_erase(&cfqe->rb_node, cfqe->service_tree);
+                       orig_st->total_weight -= cfqe->weight;
+               }
                cfq_put_cfqg(cfqq->cfqg);
                cfqq->cfqg = cfqq->orig_cfqg;
                cfqq->orig_cfqg = NULL;

block/cfq-iosched.c +39 -21

+       if (RB_EMPTY_NODE(&cfqe->rb_node)) {
+               /*
+                * If this CFQ queue moves to another group, the original
+                * vdisktime makes no sense any more, reset the vdisktime
+                * here.
+                */
+               parent = rb_last(&service_tree->rb);
+               if (parent) {
+                       u64 boost;
+                       s64 __vdisktime;
+
+                       __cfqe = rb_entry_entity(parent);
+                       cfqe->vdisktime = __cfqe->vdisktime + CFQ_IDLE_DELAY;
+
+                       /* Give some vdisktime boost according to its weight */
+                       boost = cfq_get_boost(cfqd, cfqe);
+                       __vdisktime = cfqe->vdisktime - boost;
+                       if (__vdisktime > service_tree->min_vdisktime)
+                               cfqe->vdisktime = __vdisktime;
+                       else
+                               cfqe->vdisktime = service_tree->min_vdisktime;
+               } else
+                       cfqe->vdisktime = service_tree->min_vdisktime;
+
+               goto insert;
+       }
+       /*
+        * Ok, we get here, this CFQ queue is on the service tree, dequeue it
+        * firstly.
+        */
+       cfq_rb_erase(&cfqe->rb_node, cfqe->service_tree);
+       orig_st->total_weight -= cfqe->weight;
+
+       new_cfqq = 0;
+
        if (cfq_class_idle(cfqq)) {
-               rb_key = CFQ_IDLE_DELAY;
                parent = rb_last(&service_tree->rb);
                if (parent && parent != &cfqe->rb_node) {
                        __cfqe = rb_entry(parent, struct cfq_entity, rb_node);
-                       rb_key += __cfqe->rb_key;
+                       cfqe->vdisktime = __cfqe->vdisktime + CFQ_IDLE_DELAY;
                } else
-                       rb_key += jiffies;
+                       cfqe->vdisktime = service_tree->min_vdisktime;
        } 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;
-       } else {
-               rb_key = -HZ;
-               __cfqe = cfq_rb_first(service_tree);
-               rb_key += __cfqe ? __cfqe->rb_key : jiffies;
-       }
-
-       if (!RB_EMPTY_NODE(&cfqe->rb_node)) {
-               new_cfqq = 0;
-               /*
-                * same position, nothing more to do
+                * We charge the CFQ queue by the time this queue runs, and
+                * repsition it on the service tree.

block/cfq-iosched.c +20 -2

+       } else {
+               cfqe->vdisktime = service_tree->min_vdisktime;
        }
 
+insert:
        left = 1;
        parent = NULL;
        cfqe->service_tree = service_tree;
        p = &service_tree->rb.rb_node;
+       key = entity_key(service_tree, cfqe);
        while (*p) {
                struct rb_node **n;
 

@@ -1296,7 +1352,7 @@ static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
                /*
                 * sort by key, that represents service time.
                 */
-               if (time_before(rb_key, __cfqe->rb_key))
+               if (key < entity_key(service_tree, __cfqe))
                        n = &(*p)->rb_left;
                else {
                        n = &(*p)->rb_right;

@@ -1309,10 +1365,12 @@ static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
        if (left)
                service_tree->left = &cfqe->rb_node;
 
-       cfqe->rb_key = rb_key;
        rb_link_node(&cfqe->rb_node, parent, p);
        rb_insert_color(&cfqe->rb_node, &service_tree->rb);
+       update_min_vdisktime(service_tree);
        service_tree->count++;
+       service_tree->total_weight += cfqe->weight;
+       cfqq->reposition_time = jiffies;
        if ((add_front || !new_cfqq) && !group_changed)
                return;
        cfq_group_service_tree_add(cfqd, cfqq->cfqg);

@@ -1414,14 +1472,18 @@ static void cfq_add_cfqq_rr(struct cfq_data *cfqd, struct cfq_queue *cfqq)
 static void cfq_del_cfqq_rr(struct cfq_data *cfqd, struct cfq_queue *cfqq)
 {
        struct cfq_entity *cfqe;
+       struct cfq_rb_root *service_tree;
+
        cfq_log_cfqq(cfqd, cfqq, "del_from_rr");
        BUG_ON(!cfq_cfqq_on_rr(cfqq));
        cfq_clear_cfqq_on_rr(cfqq);
 
        cfqe = &cfqq->cfqe;
+       service_tree = cfqe->service_tree;
 
        if (!RB_EMPTY_NODE(&cfqe->rb_node)) {
                cfq_rb_erase(&cfqe->rb_node, cfqe->service_tree);
+               service_tree->total_weight -= cfqe->weight;
                cfqe->service_tree = NULL;
        }
        if (cfqq->p_root) {

@@ -2120,23 +2182,35 @@ static void cfq_setup_merge(struct cfq_queue *cfqq, struct cfq_queue *new_cfqq)
        }
 }
 
+/*
+ * The time when a CFQ queue is put onto a service tree is recoreded in
+ * cfqq->reposition_time. Currently, we check the first priority CFQ queues
+ * on each service tree, and select the workload type that contain the lowest
+ * reposition_time CFQ queue among them.
+ */
 static enum wl_type_t cfq_choose_wl(struct cfq_data *cfqd,
                                struct cfq_group *cfqg, enum wl_prio_t prio)
 {
        struct cfq_entity *cfqe;
+       struct cfq_queue *cfqq;
+       unsigned long lowest_start_time;

block/cfq-iosched.c +0 -4

        for (i = 0; i <= SYNC_WORKLOAD; ++i) {
-               /* select the one with lowest rb_key */
                cfqe = cfq_rb_first(service_tree_for(cfqg, prio, i));
-               if (cfqe &&
-                   (!key_valid || time_before(cfqe->rb_key, lowest_key))) {
-                       lowest_key = cfqe->rb_key;

Quoted 4 lines · Gui Jianfeng

Introduce vdisktime and io weight for CFQ queue scheduling. Currently, io priority maps to a range [100,1000]. It also gets rid of cfq_slice_offset() logic and makes use the same scheduling algorithm as CFQ group does. This helps for CFQ queue and group scheduling on the same service tree.

Haven't read the whole series yet. Looks this changes a lot of logic even without cgroup support. Did you have test if this changes both performance and latency in some mixed workloads?

Quoted 77 lines

Signed-off-by Gui Jianfeng <[email protected]>

---
 block/cfq-iosched.c |  211 ++++++++++++++++++++++++++++++++++++++-------------
 1 files changed, 158 insertions(+), 53 deletions(-)

block/cfq-iosched.c +21 -14

index a2553c0..b598798 100644
@@ -100,10 +100,7 @@ struct cfq_entity {
        struct cfq_rb_root *service_tree;
        /* service_tree member */
        struct rb_node rb_node;
-       /* service_tree key, represent the position on the tree */
-       unsigned long rb_key;
-
-       /* group service_tree key */
+       /* service_tree key */
        u64 vdisktime;
        bool is_group_entity;
        unsigned int weight;

@@ -115,6 +112,8 @@ struct cfq_entity {
 struct cfq_queue {
        /* The schedule entity */
        struct cfq_entity cfqe;
+       /* Reposition time */
+       unsigned long reposition_time;
        /* reference count */
        atomic_t ref;
        /* various state flags, see below */

@@ -313,6 +312,24 @@ struct cfq_data {
        struct rcu_head rcu;
 };
 
+/*
+ * Map io priority(7 ~ 0) to io weight(100 ~ 1000) as follows
+ *     prio       0    1     2    3    4    5    6     7
+ *     weight  1000  868   740  612  484  356  228   100
+ */
+static inline unsigned int cfq_prio_to_weight(unsigned short ioprio)
+{
+       unsigned int step;
+
+       BUG_ON(ioprio >= IOPRIO_BE_NR);
+
+       step = (BLKIO_WEIGHT_MAX - BLKIO_WEIGHT_MIN) / (IOPRIO_BE_NR - 1);
+       if (ioprio == 0)
+               return BLKIO_WEIGHT_MAX;
+
+       return BLKIO_WEIGHT_MIN + (IOPRIO_BE_NR - ioprio - 1) * step;
+}
+
 static inline struct cfq_queue *
 cfqq_of_entity(struct cfq_entity *cfqe)
 {

@@ -841,16 +858,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
 entity_key(struct cfq_rb_root *st, struct cfq_entity *entity)
 {

@@ -1199,6 +1206,16 @@ static inline void cfq_put_cfqg(struct cfq_group *cfqg) {}
 
 #endif /* GROUP_IOSCHED */
 

block/cfq-iosched.c static inline void cfq_put_cfqg(struct cfq_group *cfqg) {} · line 1217

Quoted 9 lines

block/cfq-iosched.c +9 -0

+static inline u64 cfq_get_boost(struct cfq_data *cfqd,
+                                struct cfq_entity *cfqe)
+{
+       u64 d = cfqd->cfq_slice[1] << CFQ_SERVICE_SHIFT;
+
+       d = d * BLKIO_WEIGHT_DEFAULT;
+       do_div(d, BLKIO_WEIGHT_MAX - cfqe->weight + BLKIO_WEIGHT_MIN);
+       return d;
+}

don't consider sync/async here? for group, we don't have such issue, but we need boost sync otherwise.

Quoted 57 lines

block/cfq-iosched.c +20 -4

+
 /*
  * The cfqd->service_trees holds all pending cfq_queue's that have
  * requests waiting to be processed. It is sorted in the order that

@@ -1210,13 +1227,14 @@ static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
        struct cfq_entity *cfqe;
        struct rb_node **p, *parent;
        struct cfq_entity *__cfqe;
-       unsigned long rb_key;
-       struct cfq_rb_root *service_tree;
+       struct cfq_rb_root *service_tree, *orig_st;
        int left;
        int new_cfqq = 1;
        int group_changed = 0;
+       s64 key;
 
        cfqe = &cfqq->cfqe;
+       orig_st = cfqe->service_tree;
 
 #ifdef CONFIG_CFQ_GROUP_IOSCHED
        if (!cfqd->cfq_group_isolation

@@ -1224,8 +1242,15 @@ static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
            && cfqq->cfqg && cfqq->cfqg != &cfqd->root_group) {
                /* Move this cfq to root group */
                cfq_log_cfqq(cfqd, cfqq, "moving to root group");
-               if (!RB_EMPTY_NODE(&cfqe->rb_node))
+               if (!RB_EMPTY_NODE(&cfqe->rb_node)) {
                        cfq_group_service_tree_del(cfqd, cfqq->cfqg);
+                       /*
+                        * Group changed, dequeue this CFQ queue from the
+                        * original service tree.
+                        */
+                       cfq_rb_erase(&cfqe->rb_node, cfqe->service_tree);
+                       orig_st->total_weight -= cfqe->weight;
+               }
                cfqq->orig_cfqg = cfqq->cfqg;
                cfqq->cfqg = &cfqd->root_group;
                atomic_inc(&cfqd->root_group.ref);

@@ -1234,8 +1259,15 @@ static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
                   && cfqq_type(cfqq) == SYNC_WORKLOAD && cfqq->orig_cfqg) {
                /* cfqq is sequential now needs to go to its original group */
                BUG_ON(cfqq->cfqg != &cfqd->root_group);
-               if (!RB_EMPTY_NODE(&cfqe->rb_node))
+               if (!RB_EMPTY_NODE(&cfqe->rb_node)) {
                        cfq_group_service_tree_del(cfqd, cfqq->cfqg);
+                       /*
+                        * Group changed, dequeue this CFQ queue from the
+                        * original service tree.
+                        */
+                       cfq_rb_erase(&cfqe->rb_node, cfqe->service_tree);
+                       orig_st->total_weight -= cfqe->weight;
+               }
                cfq_put_cfqg(cfqq->cfqg);
                cfqq->cfqg = cfqq->orig_cfqg;
                cfqq->orig_cfqg = NULL;

@@ -1246,47 +1278,71 @@ static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
 

block/cfq-iosched.c static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq, · line 1284

Quoted 6 lines

block/cfq-iosched.c +4 -0

        service_tree = service_tree_for(cfqq->cfqg, cfqq_prio(cfqq),
                                                cfqq_type(cfqq));
+       /*
+        * For the time being, put the newly added CFQ queue at the end of the
+        * service tree.
+        */

so this should be fixed later? please mark it as a todo.

Quoted 73 lines

block/cfq-iosched.c +40 -24

+       if (RB_EMPTY_NODE(&cfqe->rb_node)) {
+               /*
+                * If this CFQ queue moves to another group, the original
+                * vdisktime makes no sense any more, reset the vdisktime
+                * here.
+                */
+               parent = rb_last(&service_tree->rb);
+               if (parent) {
+                       u64 boost;
+                       s64 __vdisktime;
+
+                       __cfqe = rb_entry_entity(parent);
+                       cfqe->vdisktime = __cfqe->vdisktime + CFQ_IDLE_DELAY;
+
+                       /* Give some vdisktime boost according to its weight */
+                       boost = cfq_get_boost(cfqd, cfqe);
+                       __vdisktime = cfqe->vdisktime - boost;
+                       if (__vdisktime > service_tree->min_vdisktime)
+                               cfqe->vdisktime = __vdisktime;
+                       else
+                               cfqe->vdisktime = service_tree->min_vdisktime;
+               } else
+                       cfqe->vdisktime = service_tree->min_vdisktime;
+
+               goto insert;
+       }
+       /*
+        * Ok, we get here, this CFQ queue is on the service tree, dequeue it
+        * firstly.
+        */
+       cfq_rb_erase(&cfqe->rb_node, cfqe->service_tree);
+       orig_st->total_weight -= cfqe->weight;
+
+       new_cfqq = 0;
+
        if (cfq_class_idle(cfqq)) {
-               rb_key = CFQ_IDLE_DELAY;
                parent = rb_last(&service_tree->rb);
                if (parent && parent != &cfqe->rb_node) {
                        __cfqe = rb_entry(parent, struct cfq_entity, rb_node);
-                       rb_key += __cfqe->rb_key;
+                       cfqe->vdisktime = __cfqe->vdisktime + CFQ_IDLE_DELAY;
                } else
-                       rb_key += jiffies;
+                       cfqe->vdisktime = service_tree->min_vdisktime;
        } 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;
-       } else {
-               rb_key = -HZ;
-               __cfqe = cfq_rb_first(service_tree);
-               rb_key += __cfqe ? __cfqe->rb_key : jiffies;
-       }
-
-       if (!RB_EMPTY_NODE(&cfqe->rb_node)) {
-               new_cfqq = 0;
-               /*
-                * same position, nothing more to do
+                * We charge the CFQ queue by the time this queue runs, and
+                * repsition it on the service tree.
                 */
-               if (rb_key == cfqe->rb_key &&
-                   cfqe->service_tree == service_tree)
-                       return;
+               unsigned int used_sl;
 

block/cfq-iosched.c static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq, · line 1335

Quoted 4 lines

block/cfq-iosched.c +2 -2

-               cfq_rb_erase(&cfqe->rb_node, cfqe->service_tree);
-               cfqe->service_tree = NULL;
+               used_sl = cfq_cfqq_slice_usage(cfqq);
+               cfqe->vdisktime += cfq_scale_slice(used_sl, cfqe);

cfqq->slice_resid could be > 0 or < 0, and the queue can be boosted or penalized. Looks the logic is completely removed. This exists in current cfq group too, I wonder why?

Quoted 78 lines

block/cfq-iosched.c +21 -4

+       } else {
+               cfqe->vdisktime = service_tree->min_vdisktime;
        }
 
+insert:
        left = 1;
        parent = NULL;
        cfqe->service_tree = service_tree;
        p = &service_tree->rb.rb_node;
+       key = entity_key(service_tree, cfqe);
        while (*p) {
                struct rb_node **n;
 

@@ -1296,7 +1352,7 @@ static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
                /*
                 * sort by key, that represents service time.
                 */
-               if (time_before(rb_key, __cfqe->rb_key))
+               if (key < entity_key(service_tree, __cfqe))
                        n = &(*p)->rb_left;
                else {
                        n = &(*p)->rb_right;

@@ -1309,10 +1365,12 @@ static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
        if (left)
                service_tree->left = &cfqe->rb_node;
 
-       cfqe->rb_key = rb_key;
        rb_link_node(&cfqe->rb_node, parent, p);
        rb_insert_color(&cfqe->rb_node, &service_tree->rb);
+       update_min_vdisktime(service_tree);
        service_tree->count++;
+       service_tree->total_weight += cfqe->weight;
+       cfqq->reposition_time = jiffies;
        if ((add_front || !new_cfqq) && !group_changed)
                return;
        cfq_group_service_tree_add(cfqd, cfqq->cfqg);

@@ -1414,14 +1472,18 @@ static void cfq_add_cfqq_rr(struct cfq_data *cfqd, struct cfq_queue *cfqq)
 static void cfq_del_cfqq_rr(struct cfq_data *cfqd, struct cfq_queue *cfqq)
 {
        struct cfq_entity *cfqe;
+       struct cfq_rb_root *service_tree;
+
        cfq_log_cfqq(cfqd, cfqq, "del_from_rr");
        BUG_ON(!cfq_cfqq_on_rr(cfqq));
        cfq_clear_cfqq_on_rr(cfqq);
 
        cfqe = &cfqq->cfqe;
+       service_tree = cfqe->service_tree;
 
        if (!RB_EMPTY_NODE(&cfqe->rb_node)) {
                cfq_rb_erase(&cfqe->rb_node, cfqe->service_tree);
+               service_tree->total_weight -= cfqe->weight;
                cfqe->service_tree = NULL;
        }
        if (cfqq->p_root) {

@@ -2120,23 +2182,35 @@ static void cfq_setup_merge(struct cfq_queue *cfqq, struct cfq_queue *new_cfqq)
        }
 }
 
+/*
+ * The time when a CFQ queue is put onto a service tree is recoreded in
+ * cfqq->reposition_time. Currently, we check the first priority CFQ queues
+ * on each service tree, and select the workload type that contain the lowest
+ * reposition_time CFQ queue among them.
+ */
 static enum wl_type_t cfq_choose_wl(struct cfq_data *cfqd,
                                struct cfq_group *cfqg, enum wl_prio_t prio)
 {
        struct cfq_entity *cfqe;
+       struct cfq_queue *cfqq;
+       unsigned long lowest_start_time;
        int i;
-       bool key_valid = false;
-       unsigned long lowest_key = 0;
+       bool time_valid = false;
        enum wl_type_t cur_best = SYNC_NOIDLE_WORKLOAD;
 

block/cfq-iosched.c static void cfq_setup_merge(struct cfq_queue *cfqq, struct cfq_queue *new_cfqq) · line 2204

Quoted 4 lines

block/cfq-iosched.c +4 -0

+       /*
+        * TODO: We may take io priority into account when choosing a workload
+        * type. But for the time being just make use of reposition_time only.
+        */

not just priority, original rb_key considers sys/async too.

Quoted 6 lines

block/cfq-iosched.c +0 -4

        for (i = 0; i <= SYNC_WORKLOAD; ++i) {
-               /* select the one with lowest rb_key */
                cfqe = cfq_rb_first(service_tree_for(cfqg, prio, i));
-               if (cfqe &&
-                   (!key_valid || time_before(cfqe->rb_key, lowest_key))) {
-                       lowest_key = cfqe->rb_key;

block/cfq-iosched.c static void cfq_setup_merge(struct cfq_queue *cfqq, struct cfq_queue *new_cfqq) · line 2215

Quoted 10 lines

block/cfq-iosched.c +6 -1

+               cfqq = cfqq_of_entity(cfqe);
+               if (cfqe && (!time_valid ||
+                            time_before(cfqq->reposition_time,
+                                        lowest_start_time))) {
+                       lowest_start_time = cfqq->reposition_time;
                        cur_best = i;
-                       key_valid = true;
+                       time_valid = true;
                }
        }

Thanks,
Shaohua

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

Quoted 5 lines · Shaohua Li

Quoted 4 lines · Gui Jianfeng

Introduce vdisktime and io weight for CFQ queue scheduling. Currently, io priority maps to a range [100,1000]. It also gets rid of cfq_slice_offset() logic and makes use the same scheduling algorithm as CFQ group does. This helps for CFQ queue and group scheduling on the same service tree.

Quoted 3 lines

Haven't read the whole series yet. Looks this changes a lot of logic even without cgroup support. Did you have test if this changes both performance and latency in some mixed workloads?

Hi Shaohua,

I did some tests with different workloads and with idling on or idling off. I don't see performance drop on my box.

Quoted 76 lines

Quoted 76 lines

Signed-off-by Gui Jianfeng <[email protected]>

---
 block/cfq-iosched.c |  211 ++++++++++++++++++++++++++++++++++++++-------------
 1 files changed, 158 insertions(+), 53 deletions(-)

block/cfq-iosched.c +21 -14

index a2553c0..b598798 100644
@@ -100,10 +100,7 @@ struct cfq_entity {
        struct cfq_rb_root *service_tree;
        /* service_tree member */
        struct rb_node rb_node;
-       /* service_tree key, represent the position on the tree */
-       unsigned long rb_key;
-
-       /* group service_tree key */
+       /* service_tree key */
        u64 vdisktime;
        bool is_group_entity;
        unsigned int weight;

@@ -115,6 +112,8 @@ struct cfq_entity {
 struct cfq_queue {
        /* The schedule entity */
        struct cfq_entity cfqe;
+       /* Reposition time */
+       unsigned long reposition_time;
        /* reference count */
        atomic_t ref;
        /* various state flags, see below */

@@ -313,6 +312,24 @@ struct cfq_data {
        struct rcu_head rcu;
 };
 
+/*
+ * Map io priority(7 ~ 0) to io weight(100 ~ 1000) as follows
+ *     prio       0    1     2    3    4    5    6     7
+ *     weight  1000  868   740  612  484  356  228   100
+ */
+static inline unsigned int cfq_prio_to_weight(unsigned short ioprio)
+{
+       unsigned int step;
+
+       BUG_ON(ioprio >= IOPRIO_BE_NR);
+
+       step = (BLKIO_WEIGHT_MAX - BLKIO_WEIGHT_MIN) / (IOPRIO_BE_NR - 1);
+       if (ioprio == 0)
+               return BLKIO_WEIGHT_MAX;
+
+       return BLKIO_WEIGHT_MIN + (IOPRIO_BE_NR - ioprio - 1) * step;
+}
+
 static inline struct cfq_queue *
 cfqq_of_entity(struct cfq_entity *cfqe)
 {

@@ -841,16 +858,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
 entity_key(struct cfq_rb_root *st, struct cfq_entity *entity)
 {

@@ -1199,6 +1206,16 @@ static inline void cfq_put_cfqg(struct cfq_group *cfqg) {}
 
 #endif /* GROUP_IOSCHED */
 

Quoted 11 lines

block/cfq-iosched.c static inline void cfq_put_cfqg(struct cfq_group *cfqg) {} · line 1217

Quoted 9 lines

block/cfq-iosched.c +9 -0

+static inline u64 cfq_get_boost(struct cfq_data *cfqd,
+                                struct cfq_entity *cfqe)
+{
+       u64 d = cfqd->cfq_slice[1] << CFQ_SERVICE_SHIFT;
+
+       d = d * BLKIO_WEIGHT_DEFAULT;
+       do_div(d, BLKIO_WEIGHT_MAX - cfqe->weight + BLKIO_WEIGHT_MIN);
+       return d;
+}

don't consider sync/async here? for group, we don't have such issue, but we need boost sync otherwise.

Ok, we should.

Quoted 57 lines

Quoted 57 lines

block/cfq-iosched.c +20 -4

+
 /*
  * The cfqd->service_trees holds all pending cfq_queue's that have
  * requests waiting to be processed. It is sorted in the order that

@@ -1210,13 +1227,14 @@ static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
        struct cfq_entity *cfqe;
        struct rb_node **p, *parent;
        struct cfq_entity *__cfqe;
-       unsigned long rb_key;
-       struct cfq_rb_root *service_tree;
+       struct cfq_rb_root *service_tree, *orig_st;
        int left;
        int new_cfqq = 1;
        int group_changed = 0;
+       s64 key;
 
        cfqe = &cfqq->cfqe;
+       orig_st = cfqe->service_tree;
 
 #ifdef CONFIG_CFQ_GROUP_IOSCHED
        if (!cfqd->cfq_group_isolation

@@ -1224,8 +1242,15 @@ static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
            && cfqq->cfqg && cfqq->cfqg != &cfqd->root_group) {
                /* Move this cfq to root group */
                cfq_log_cfqq(cfqd, cfqq, "moving to root group");
-               if (!RB_EMPTY_NODE(&cfqe->rb_node))
+               if (!RB_EMPTY_NODE(&cfqe->rb_node)) {
                        cfq_group_service_tree_del(cfqd, cfqq->cfqg);
+                       /*
+                        * Group changed, dequeue this CFQ queue from the
+                        * original service tree.
+                        */
+                       cfq_rb_erase(&cfqe->rb_node, cfqe->service_tree);
+                       orig_st->total_weight -= cfqe->weight;
+               }
                cfqq->orig_cfqg = cfqq->cfqg;
                cfqq->cfqg = &cfqd->root_group;
                atomic_inc(&cfqd->root_group.ref);

@@ -1234,8 +1259,15 @@ static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
                   && cfqq_type(cfqq) == SYNC_WORKLOAD && cfqq->orig_cfqg) {
                /* cfqq is sequential now needs to go to its original group */
                BUG_ON(cfqq->cfqg != &cfqd->root_group);
-               if (!RB_EMPTY_NODE(&cfqe->rb_node))
+               if (!RB_EMPTY_NODE(&cfqe->rb_node)) {
                        cfq_group_service_tree_del(cfqd, cfqq->cfqg);
+                       /*
+                        * Group changed, dequeue this CFQ queue from the
+                        * original service tree.
+                        */
+                       cfq_rb_erase(&cfqe->rb_node, cfqe->service_tree);
+                       orig_st->total_weight -= cfqe->weight;
+               }
                cfq_put_cfqg(cfqq->cfqg);
                cfqq->cfqg = cfqq->orig_cfqg;
                cfqq->orig_cfqg = NULL;

@@ -1246,47 +1278,71 @@ static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
 

Quoted 7 lines

block/cfq-iosched.c static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq, · line 1284

Quoted 6 lines

block/cfq-iosched.c +4 -0

        service_tree = service_tree_for(cfqq->cfqg, cfqq_prio(cfqq),
                                                cfqq_type(cfqq));
+       /*
+        * For the time being, put the newly added CFQ queue at the end of the
+        * service tree.
+        */

so this should be fixed later? please mark it as a todo.

Ahh, forgot remove this annotation, I'v already boost vdisktime according to it ioprio.

Quoted 73 lines

Quoted 73 lines

block/cfq-iosched.c +40 -24

+       if (RB_EMPTY_NODE(&cfqe->rb_node)) {
+               /*
+                * If this CFQ queue moves to another group, the original
+                * vdisktime makes no sense any more, reset the vdisktime
+                * here.
+                */
+               parent = rb_last(&service_tree->rb);
+               if (parent) {
+                       u64 boost;
+                       s64 __vdisktime;
+
+                       __cfqe = rb_entry_entity(parent);
+                       cfqe->vdisktime = __cfqe->vdisktime + CFQ_IDLE_DELAY;
+
+                       /* Give some vdisktime boost according to its weight */
+                       boost = cfq_get_boost(cfqd, cfqe);
+                       __vdisktime = cfqe->vdisktime - boost;
+                       if (__vdisktime > service_tree->min_vdisktime)
+                               cfqe->vdisktime = __vdisktime;
+                       else
+                               cfqe->vdisktime = service_tree->min_vdisktime;
+               } else
+                       cfqe->vdisktime = service_tree->min_vdisktime;
+
+               goto insert;
+       }
+       /*
+        * Ok, we get here, this CFQ queue is on the service tree, dequeue it
+        * firstly.
+        */
+       cfq_rb_erase(&cfqe->rb_node, cfqe->service_tree);
+       orig_st->total_weight -= cfqe->weight;
+
+       new_cfqq = 0;
+
        if (cfq_class_idle(cfqq)) {
-               rb_key = CFQ_IDLE_DELAY;
                parent = rb_last(&service_tree->rb);
                if (parent && parent != &cfqe->rb_node) {
                        __cfqe = rb_entry(parent, struct cfq_entity, rb_node);
-                       rb_key += __cfqe->rb_key;
+                       cfqe->vdisktime = __cfqe->vdisktime + CFQ_IDLE_DELAY;
                } else
-                       rb_key += jiffies;
+                       cfqe->vdisktime = service_tree->min_vdisktime;
        } 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;
-       } else {
-               rb_key = -HZ;
-               __cfqe = cfq_rb_first(service_tree);
-               rb_key += __cfqe ? __cfqe->rb_key : jiffies;
-       }
-
-       if (!RB_EMPTY_NODE(&cfqe->rb_node)) {
-               new_cfqq = 0;
-               /*
-                * same position, nothing more to do
+                * We charge the CFQ queue by the time this queue runs, and
+                * repsition it on the service tree.
                 */
-               if (rb_key == cfqe->rb_key &&
-                   cfqe->service_tree == service_tree)
-                       return;
+               unsigned int used_sl;
 

Quoted 7 lines

block/cfq-iosched.c static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq, · line 1335

Quoted 4 lines

block/cfq-iosched.c +2 -2

-               cfq_rb_erase(&cfqe->rb_node, cfqe->service_tree);
-               cfqe->service_tree = NULL;
+               used_sl = cfq_cfqq_slice_usage(cfqq);
+               cfqe->vdisktime += cfq_scale_slice(used_sl, cfqe);

cfqq->slice_resid could be > 0 or < 0, and the queue can be boosted or penalized. Looks the logic is completely removed. This exists in current cfq group too, I wonder why?

With vdisktime introduced, vdisktime represents cfqq's position on a service tree. And vdisktime is decided by the acutal running time by a cfqq. So we don't need slice_resid any more here.

Quoted 78 lines

Quoted 78 lines

block/cfq-iosched.c +21 -4

+       } else {
+               cfqe->vdisktime = service_tree->min_vdisktime;
        }
 
+insert:
        left = 1;
        parent = NULL;
        cfqe->service_tree = service_tree;
        p = &service_tree->rb.rb_node;
+       key = entity_key(service_tree, cfqe);
        while (*p) {
                struct rb_node **n;
 

@@ -1296,7 +1352,7 @@ static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
                /*
                 * sort by key, that represents service time.
                 */
-               if (time_before(rb_key, __cfqe->rb_key))
+               if (key < entity_key(service_tree, __cfqe))
                        n = &(*p)->rb_left;
                else {
                        n = &(*p)->rb_right;

@@ -1309,10 +1365,12 @@ static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
        if (left)
                service_tree->left = &cfqe->rb_node;
 
-       cfqe->rb_key = rb_key;
        rb_link_node(&cfqe->rb_node, parent, p);
        rb_insert_color(&cfqe->rb_node, &service_tree->rb);
+       update_min_vdisktime(service_tree);
        service_tree->count++;
+       service_tree->total_weight += cfqe->weight;
+       cfqq->reposition_time = jiffies;
        if ((add_front || !new_cfqq) && !group_changed)
                return;
        cfq_group_service_tree_add(cfqd, cfqq->cfqg);

@@ -1414,14 +1472,18 @@ static void cfq_add_cfqq_rr(struct cfq_data *cfqd, struct cfq_queue *cfqq)
 static void cfq_del_cfqq_rr(struct cfq_data *cfqd, struct cfq_queue *cfqq)
 {
        struct cfq_entity *cfqe;
+       struct cfq_rb_root *service_tree;
+
        cfq_log_cfqq(cfqd, cfqq, "del_from_rr");
        BUG_ON(!cfq_cfqq_on_rr(cfqq));
        cfq_clear_cfqq_on_rr(cfqq);
 
        cfqe = &cfqq->cfqe;
+       service_tree = cfqe->service_tree;
 
        if (!RB_EMPTY_NODE(&cfqe->rb_node)) {
                cfq_rb_erase(&cfqe->rb_node, cfqe->service_tree);
+               service_tree->total_weight -= cfqe->weight;
                cfqe->service_tree = NULL;
        }
        if (cfqq->p_root) {

@@ -2120,23 +2182,35 @@ static void cfq_setup_merge(struct cfq_queue *cfqq, struct cfq_queue *new_cfqq)
        }
 }
 
+/*
+ * The time when a CFQ queue is put onto a service tree is recoreded in
+ * cfqq->reposition_time. Currently, we check the first priority CFQ queues
+ * on each service tree, and select the workload type that contain the lowest
+ * reposition_time CFQ queue among them.
+ */
 static enum wl_type_t cfq_choose_wl(struct cfq_data *cfqd,
                                struct cfq_group *cfqg, enum wl_prio_t prio)
 {
        struct cfq_entity *cfqe;
+       struct cfq_queue *cfqq;
+       unsigned long lowest_start_time;
        int i;
-       bool key_valid = false;
-       unsigned long lowest_key = 0;
+       bool time_valid = false;
        enum wl_type_t cur_best = SYNC_NOIDLE_WORKLOAD;
 

Quoted 5 lines

block/cfq-iosched.c static void cfq_setup_merge(struct cfq_queue *cfqq, struct cfq_queue *new_cfqq) · line 2204

Quoted 4 lines

block/cfq-iosched.c +4 -0

+       /*
+        * TODO: We may take io priority into account when choosing a workload
+        * type. But for the time being just make use of reposition_time only.
+        */

not just priority, original rb_key considers sys/async too.

IIUC, in original CFQ, rb_key is cross tree, so we need to take sync/async into account. But with vdisktime introduced, each service has its own vdisktime space. So there's no need to consider sync/async here.

Quoted 6 lines · Gui Jianfeng

Quoted 5 lines · Shaohua Li

Quoted 4 lines · Gui Jianfeng

Introduce vdisktime and io weight for CFQ queue scheduling. Currently, io priority maps to a range [100,1000]. It also gets rid of cfq_slice_offset() logic and makes use the same scheduling algorithm as CFQ group does. This helps for CFQ queue and group scheduling on the same service tree.

Quoted 7 lines

Quoted 3 lines

Haven't read the whole series yet. Looks this changes a lot of logic even without cgroup support. Did you have test if this changes both performance and latency in some mixed workloads?

Hi Shaohua,

I did some tests with different workloads and with idling on or idling off. I don't see performance drop on my box.

please check latency too.

Quoted 153 lines

Quoted 76 lines

Quoted 76 lines

Signed-off-by Gui Jianfeng <[email protected]>

---
 block/cfq-iosched.c |  211 ++++++++++++++++++++++++++++++++++++++-------------
 1 files changed, 158 insertions(+), 53 deletions(-)

block/cfq-iosched.c +21 -14

index a2553c0..b598798 100644
@@ -100,10 +100,7 @@ struct cfq_entity {
        struct cfq_rb_root *service_tree;
        /* service_tree member */
        struct rb_node rb_node;
-       /* service_tree key, represent the position on the tree */
-       unsigned long rb_key;
-
-       /* group service_tree key */
+       /* service_tree key */
        u64 vdisktime;
        bool is_group_entity;
        unsigned int weight;

@@ -115,6 +112,8 @@ struct cfq_entity {
 struct cfq_queue {
        /* The schedule entity */
        struct cfq_entity cfqe;
+       /* Reposition time */
+       unsigned long reposition_time;
        /* reference count */
        atomic_t ref;
        /* various state flags, see below */

@@ -313,6 +312,24 @@ struct cfq_data {
        struct rcu_head rcu;
 };
 
+/*
+ * Map io priority(7 ~ 0) to io weight(100 ~ 1000) as follows
+ *     prio       0    1     2    3    4    5    6     7
+ *     weight  1000  868   740  612  484  356  228   100
+ */
+static inline unsigned int cfq_prio_to_weight(unsigned short ioprio)
+{
+       unsigned int step;
+
+       BUG_ON(ioprio >= IOPRIO_BE_NR);
+
+       step = (BLKIO_WEIGHT_MAX - BLKIO_WEIGHT_MIN) / (IOPRIO_BE_NR - 1);
+       if (ioprio == 0)
+               return BLKIO_WEIGHT_MAX;
+
+       return BLKIO_WEIGHT_MIN + (IOPRIO_BE_NR - ioprio - 1) * step;
+}
+
 static inline struct cfq_queue *
 cfqq_of_entity(struct cfq_entity *cfqe)
 {

@@ -841,16 +858,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
 entity_key(struct cfq_rb_root *st, struct cfq_entity *entity)
 {

@@ -1199,6 +1206,16 @@ static inline void cfq_put_cfqg(struct cfq_group *cfqg) {}
 
 #endif /* GROUP_IOSCHED */
 

Quoted 11 lines

block/cfq-iosched.c static inline void cfq_put_cfqg(struct cfq_group *cfqg) {} · line 1217

Quoted 9 lines

block/cfq-iosched.c +9 -0

+static inline u64 cfq_get_boost(struct cfq_data *cfqd,
+                                struct cfq_entity *cfqe)
+{
+       u64 d = cfqd->cfq_slice[1] << CFQ_SERVICE_SHIFT;
+
+       d = d * BLKIO_WEIGHT_DEFAULT;
+       do_div(d, BLKIO_WEIGHT_MAX - cfqe->weight + BLKIO_WEIGHT_MIN);
+       return d;
+}

don't consider sync/async here? for group, we don't have such issue, but we need boost sync otherwise.

Ok, we should.

Quoted 64 lines

Quoted 56 lines

block/cfq-iosched.c +20 -4

+
 /*
  * The cfqd->service_trees holds all pending cfq_queue's that have
  * requests waiting to be processed. It is sorted in the order that

@@ -1210,13 +1227,14 @@ static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
        struct cfq_entity *cfqe;
        struct rb_node **p, *parent;
        struct cfq_entity *__cfqe;
-       unsigned long rb_key;
-       struct cfq_rb_root *service_tree;
+       struct cfq_rb_root *service_tree, *orig_st;
        int left;
        int new_cfqq = 1;
        int group_changed = 0;
+       s64 key;
 
        cfqe = &cfqq->cfqe;
+       orig_st = cfqe->service_tree;
 
 #ifdef CONFIG_CFQ_GROUP_IOSCHED
        if (!cfqd->cfq_group_isolation

@@ -1224,8 +1242,15 @@ static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
            && cfqq->cfqg && cfqq->cfqg != &cfqd->root_group) {
                /* Move this cfq to root group */
                cfq_log_cfqq(cfqd, cfqq, "moving to root group");
-               if (!RB_EMPTY_NODE(&cfqe->rb_node))
+               if (!RB_EMPTY_NODE(&cfqe->rb_node)) {
                        cfq_group_service_tree_del(cfqd, cfqq->cfqg);
+                       /*
+                        * Group changed, dequeue this CFQ queue from the
+                        * original service tree.
+                        */
+                       cfq_rb_erase(&cfqe->rb_node, cfqe->service_tree);
+                       orig_st->total_weight -= cfqe->weight;
+               }
                cfqq->orig_cfqg = cfqq->cfqg;
                cfqq->cfqg = &cfqd->root_group;
                atomic_inc(&cfqd->root_group.ref);

@@ -1234,8 +1259,15 @@ static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
                   && cfqq_type(cfqq) == SYNC_WORKLOAD && cfqq->orig_cfqg) {
                /* cfqq is sequential now needs to go to its original group */
                BUG_ON(cfqq->cfqg != &cfqd->root_group);
-               if (!RB_EMPTY_NODE(&cfqe->rb_node))
+               if (!RB_EMPTY_NODE(&cfqe->rb_node)) {
                        cfq_group_service_tree_del(cfqd, cfqq->cfqg);
+                       /*
+                        * Group changed, dequeue this CFQ queue from the
+                        * original service tree.
+                        */
+                       cfq_rb_erase(&cfqe->rb_node, cfqe->service_tree);
+                       orig_st->total_weight -= cfqe->weight;
+               }
                cfq_put_cfqg(cfqq->cfqg);
                cfqq->cfqg = cfqq->orig_cfqg;
                cfqq->orig_cfqg = NULL;

block/cfq-iosched.c static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq, · line 1284

Quoted 7 lines

block/cfq-iosched.c +4 -0

@@ -1246,47 +1278,71 @@ static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
 
        service_tree = service_tree_for(cfqq->cfqg, cfqq_prio(cfqq),
                                                cfqq_type(cfqq));
+       /*
+        * For the time being, put the newly added CFQ queue at the end of the
+        * service tree.
+        */

so this should be fixed later? please mark it as a todo.

Quoted 1 line

Ahh, forgot remove this annotation, I'v already boost vdisktime according to it ioprio.

ok, at below code, looks cfq_get_boost returns a value which is always greater than CFQ_IDLE_DELAY, so the new queue is inserted before __cfqe, is this intended?

Quoted 80 lines

Quoted 73 lines

Quoted 73 lines

block/cfq-iosched.c +40 -24

+       if (RB_EMPTY_NODE(&cfqe->rb_node)) {
+               /*
+                * If this CFQ queue moves to another group, the original
+                * vdisktime makes no sense any more, reset the vdisktime
+                * here.
+                */
+               parent = rb_last(&service_tree->rb);
+               if (parent) {
+                       u64 boost;
+                       s64 __vdisktime;
+
+                       __cfqe = rb_entry_entity(parent);
+                       cfqe->vdisktime = __cfqe->vdisktime + CFQ_IDLE_DELAY;
+
+                       /* Give some vdisktime boost according to its weight */
+                       boost = cfq_get_boost(cfqd, cfqe);
+                       __vdisktime = cfqe->vdisktime - boost;
+                       if (__vdisktime > service_tree->min_vdisktime)
+                               cfqe->vdisktime = __vdisktime;
+                       else
+                               cfqe->vdisktime = service_tree->min_vdisktime;
+               } else
+                       cfqe->vdisktime = service_tree->min_vdisktime;
+
+               goto insert;
+       }
+       /*
+        * Ok, we get here, this CFQ queue is on the service tree, dequeue it
+        * firstly.
+        */
+       cfq_rb_erase(&cfqe->rb_node, cfqe->service_tree);
+       orig_st->total_weight -= cfqe->weight;
+
+       new_cfqq = 0;
+
        if (cfq_class_idle(cfqq)) {
-               rb_key = CFQ_IDLE_DELAY;
                parent = rb_last(&service_tree->rb);
                if (parent && parent != &cfqe->rb_node) {
                        __cfqe = rb_entry(parent, struct cfq_entity, rb_node);
-                       rb_key += __cfqe->rb_key;
+                       cfqe->vdisktime = __cfqe->vdisktime + CFQ_IDLE_DELAY;
                } else
-                       rb_key += jiffies;
+                       cfqe->vdisktime = service_tree->min_vdisktime;
        } 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;
-       } else {
-               rb_key = -HZ;
-               __cfqe = cfq_rb_first(service_tree);
-               rb_key += __cfqe ? __cfqe->rb_key : jiffies;
-       }
-
-       if (!RB_EMPTY_NODE(&cfqe->rb_node)) {
-               new_cfqq = 0;
-               /*
-                * same position, nothing more to do
+                * We charge the CFQ queue by the time this queue runs, and
+                * repsition it on the service tree.
                 */
-               if (rb_key == cfqe->rb_key &&
-                   cfqe->service_tree == service_tree)
-                       return;
+               unsigned int used_sl;
 

Quoted 7 lines

block/cfq-iosched.c static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq, · line 1335

Quoted 4 lines

block/cfq-iosched.c +2 -2

-               cfq_rb_erase(&cfqe->rb_node, cfqe->service_tree);
-               cfqe->service_tree = NULL;
+               used_sl = cfq_cfqq_slice_usage(cfqq);
+               cfqe->vdisktime += cfq_scale_slice(used_sl, cfqe);

cfqq->slice_resid could be > 0 or < 0, and the queue can be boosted or penalized. Looks the logic is completely removed. This exists in current cfq group too, I wonder why?

Quoted 3 lines

With vdisktime introduced, vdisktime represents cfqq's position on a service tree. And vdisktime is decided by the acutal running time by a cfqq. So we don't need slice_resid any more here.

I mean the logic. cfq_cfq_slice_usage does:

		slice_used = jiffies - cfqq->slice_start;
		if (slice_used > cfqq->allocated_slice)
			slice_used = cfqq->allocated_slice;

so the queue doesn't get penalty if it uses more slices than allocated, looks like a bug here.

Quoted 77 lines

Quoted 77 lines

Quoted 77 lines

block/cfq-iosched.c +21 -4

+       } else {
+               cfqe->vdisktime = service_tree->min_vdisktime;
        }
 
+insert:
        left = 1;
        parent = NULL;
        cfqe->service_tree = service_tree;
        p = &service_tree->rb.rb_node;
+       key = entity_key(service_tree, cfqe);
        while (*p) {
                struct rb_node **n;
 

@@ -1296,7 +1352,7 @@ static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
                /*
                 * sort by key, that represents service time.
                 */
-               if (time_before(rb_key, __cfqe->rb_key))
+               if (key < entity_key(service_tree, __cfqe))
                        n = &(*p)->rb_left;
                else {
                        n = &(*p)->rb_right;

@@ -1309,10 +1365,12 @@ static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
        if (left)
                service_tree->left = &cfqe->rb_node;
 
-       cfqe->rb_key = rb_key;
        rb_link_node(&cfqe->rb_node, parent, p);
        rb_insert_color(&cfqe->rb_node, &service_tree->rb);
+       update_min_vdisktime(service_tree);
        service_tree->count++;
+       service_tree->total_weight += cfqe->weight;
+       cfqq->reposition_time = jiffies;
        if ((add_front || !new_cfqq) && !group_changed)
                return;
        cfq_group_service_tree_add(cfqd, cfqq->cfqg);

@@ -1414,14 +1472,18 @@ static void cfq_add_cfqq_rr(struct cfq_data *cfqd, struct cfq_queue *cfqq)
 static void cfq_del_cfqq_rr(struct cfq_data *cfqd, struct cfq_queue *cfqq)
 {
        struct cfq_entity *cfqe;
+       struct cfq_rb_root *service_tree;
+
        cfq_log_cfqq(cfqd, cfqq, "del_from_rr");
        BUG_ON(!cfq_cfqq_on_rr(cfqq));
        cfq_clear_cfqq_on_rr(cfqq);
 
        cfqe = &cfqq->cfqe;
+       service_tree = cfqe->service_tree;
 
        if (!RB_EMPTY_NODE(&cfqe->rb_node)) {
                cfq_rb_erase(&cfqe->rb_node, cfqe->service_tree);
+               service_tree->total_weight -= cfqe->weight;
                cfqe->service_tree = NULL;
        }
        if (cfqq->p_root) {

@@ -2120,23 +2182,35 @@ static void cfq_setup_merge(struct cfq_queue *cfqq, struct cfq_queue *new_cfqq)
        }
 }
 
+/*
+ * The time when a CFQ queue is put onto a service tree is recoreded in
+ * cfqq->reposition_time. Currently, we check the first priority CFQ queues
+ * on each service tree, and select the workload type that contain the lowest
+ * reposition_time CFQ queue among them.
+ */
 static enum wl_type_t cfq_choose_wl(struct cfq_data *cfqd,
                                struct cfq_group *cfqg, enum wl_prio_t prio)
 {
        struct cfq_entity *cfqe;
+       struct cfq_queue *cfqq;
+       unsigned long lowest_start_time;
        int i;
-       bool key_valid = false;
-       unsigned long lowest_key = 0;
+       bool time_valid = false;
        enum wl_type_t cur_best = SYNC_NOIDLE_WORKLOAD;
 

Quoted 8 lines

Quoted 5 lines

block/cfq-iosched.c static void cfq_setup_merge(struct cfq_queue *cfqq, struct cfq_queue *new_cfqq) · line 2204

Quoted 4 lines

block/cfq-iosched.c +4 -0

+       /*
+        * TODO: We may take io priority into account when choosing a workload
+        * type. But for the time being just make use of reposition_time only.
+        */

not just priority, original rb_key considers sys/async too.

IIUC, in original CFQ, rb_key is cross tree, so we need to take sync/async into account. But with vdisktime introduced, each service has its own vdisktime space. So there's no need to consider sync/async here.

previously rb_key is jiffies + offset, where offset is scaled by priority and sync/async. So if you add two queues with different type and same priority, sync queue will be dispatched first, while currently only the inserted time is checked here, so sync queue isn't boosted. That's why I said original code not just consider priority but also sync/async

Thanks,
Shaohua

Introduce vdisktime and io weight for CFQ queue scheduling. Currently, io priority maps to a range [100,1000]. It also gets rid of cfq_slice_offset() logic and makes use the same scheduling algorithm as CFQ group does. This helps for CFQ queue and group scheduling on the same service tree.

Signed-off-by Gui Jianfeng <[email protected]>

block/cfq-iosched.c +17 -0

@@ -1246,47 +1278,71 @@ static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
 
 	service_tree = service_tree_for(cfqq->cfqg, cfqq_prio(cfqq),
 						cfqq_type(cfqq));
+	/*
+	 * For the time being, put the newly added CFQ queue at the end of the
+	 * service tree.
+	 */
+	if (RB_EMPTY_NODE(&cfqe->rb_node)) {
+		/*
+		 * If this CFQ queue moves to another group, the original
+		 * vdisktime makes no sense any more, reset the vdisktime
+		 * here.
+		 */
+		parent = rb_last(&service_tree->rb);
+		if (parent) {
+			u64 boost;
+			s64 __vdisktime;
+
+			__cfqe = rb_entry_entity(parent);
+			cfqe->vdisktime = __cfqe->vdisktime + CFQ_IDLE_DELAY;

Quoted 6 lines · Gui Jianfeng

Introduce vdisktime and io weight for CFQ queue scheduling. Currently, io priority maps to a range [100,1000]. It also gets rid of cfq_slice_offset() logic and makes use the same scheduling algorithm as CFQ group does. This helps for CFQ queue and group scheduling on the same service tree.

Signed-off-by Gui Jianfeng <[email protected]>

[..]

Quoted 21 lines

block/cfq-iosched.c +17 -0

@@ -1246,47 +1278,71 @@ static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
 
 	service_tree = service_tree_for(cfqq->cfqg, cfqq_prio(cfqq),
 						cfqq_type(cfqq));
+	/*
+	 * For the time being, put the newly added CFQ queue at the end of the
+	 * service tree.
+	 */
+	if (RB_EMPTY_NODE(&cfqe->rb_node)) {
+		/*
+		 * If this CFQ queue moves to another group, the original
+		 * vdisktime makes no sense any more, reset the vdisktime
+		 * here.
+		 */
+		parent = rb_last(&service_tree->rb);
+		if (parent) {
+			u64 boost;
+			s64 __vdisktime;
+
+			__cfqe = rb_entry_entity(parent);
+			cfqe->vdisktime = __cfqe->vdisktime + CFQ_IDLE_DELAY;

block/cfq-iosched.c static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq, · line 1307

Quoted 10 lines

block/cfq-iosched.c +10 -0

+
+			/* Give some vdisktime boost according to its weight */
+			boost = cfq_get_boost(cfqd, cfqe);
+			__vdisktime = cfqe->vdisktime - boost;
+			if (__vdisktime > service_tree->min_vdisktime)
+				cfqe->vdisktime = __vdisktime;
+			else
+				cfqe->vdisktime = service_tree->min_vdisktime;
+		} else
+			cfqe->vdisktime = service_tree->min_vdisktime;

Hi Gui,

Is above logic actually working? I suspect that most of the time all the new queues will end up getting same vdisktime and that is st->min_vdisktime and there will be no service differentiation across various prio.

Reason being, on SSD, idle is disabled. So very few/no queue will consume its slice and follow reque path. So every queue will be new. Now you are doing following.

	cfqd->vdisktime = vdisktime_of_parent + IDLE_DELAY - boost

assume vdisktime_of_parent=st->min_vdisktime, then (IDLE_DELAY - boost) is always going to be a -ve number and hence cfqd->vdisktime will default to st->min_vdisktime. (IDLE_DELAY=200 while boost should be a huge value due to SERVICE_SHIFT thing).

I think this logic needs refining. Maybe instead of subtracting the boost we can instead place entities further away from st->min_vdisktime and offset is higher for lower ioprio queues.

	cfqe->vdisktime = st->min_vdisktime + offset

here offset is something similar to boost but reversed in nature in the sense that lower weight has got lower offset and vice-versa.

The important test here will be to run bunch of cfqq queues of different ioprio on a SSD with queue depth 1 and see if you can see the service differentiation. If yes, then you can increase the queue depth a bit and also number of competing queues and see what's the result. Also monitor the blktrace and vdisktime and make sure higher prio queues get to run more than lower prio queues.

This is the most critical piece of converting cfqq scheduling logic, so lets make sure that we get it right.

Thanks
Vivek

Quoted 51 lines · Vivek Goyal

Quoted 6 lines · Gui Jianfeng

Introduce vdisktime and io weight for CFQ queue scheduling. Currently, io priority maps to a range [100,1000]. It also gets rid of cfq_slice_offset() logic and makes use the same scheduling algorithm as CFQ group does. This helps for CFQ queue and group scheduling on the same service tree.

Signed-off-by Gui Jianfeng <[email protected]>

[..]

Quoted 21 lines

block/cfq-iosched.c +17 -0

@@ -1246,47 +1278,71 @@ static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
 
 	service_tree = service_tree_for(cfqq->cfqg, cfqq_prio(cfqq),
 						cfqq_type(cfqq));
+	/*
+	 * For the time being, put the newly added CFQ queue at the end of the
+	 * service tree.
+	 */
+	if (RB_EMPTY_NODE(&cfqe->rb_node)) {
+		/*
+		 * If this CFQ queue moves to another group, the original
+		 * vdisktime makes no sense any more, reset the vdisktime
+		 * here.
+		 */
+		parent = rb_last(&service_tree->rb);
+		if (parent) {
+			u64 boost;
+			s64 __vdisktime;
+
+			__cfqe = rb_entry_entity(parent);
+			cfqe->vdisktime = __cfqe->vdisktime + CFQ_IDLE_DELAY;

block/cfq-iosched.c static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq, · line 1307

Quoted 10 lines

block/cfq-iosched.c +10 -0

+
+			/* Give some vdisktime boost according to its weight */
+			boost = cfq_get_boost(cfqd, cfqe);
+			__vdisktime = cfqe->vdisktime - boost;
+			if (__vdisktime > service_tree->min_vdisktime)
+				cfqe->vdisktime = __vdisktime;
+			else
+				cfqe->vdisktime = service_tree->min_vdisktime;
+		} else
+			cfqe->vdisktime = service_tree->min_vdisktime;

Hi Gui,

Is above logic actually working? I suspect that most of the time all the new queues will end up getting same vdisktime and that is st->min_vdisktime and there will be no service differentiation across various prio.

Reason being, on SSD, idle is disabled. So very few/no queue will consume its slice and follow reque path. So every queue will be new. Now you are doing following.

Quoted 6 lines

	cfqd->vdisktime = vdisktime_of_parent + IDLE_DELAY - boost

assume vdisktime_of_parent=st->min_vdisktime, then (IDLE_DELAY - boost) is always going to be a -ve number and hence cfqd->vdisktime will default to st->min_vdisktime. (IDLE_DELAY=200 while boost should be a huge value due to SERVICE_SHIFT thing).

Vivek,

Actually, I tested on rotational disk with idling disabled, I saw service differentiation between two tasks with different ioprio.
I don't have a SSD on hand, But I'll get one and do more tests.

Quoted 6 lines

I think this logic needs refining. Maybe instead of subtracting the boost we can instead place entities further away from st->min_vdisktime and offset is higher for lower ioprio queues.

Quoted 4 lines

	cfqe->vdisktime = st->min_vdisktime + offset

here offset is something similar to boost but reversed in nature in the sense that lower weight has got lower offset and vice-versa.

I'll consider this idea and try it.

Quoted 58 lines · Gui Jianfeng

Quoted 49 lines · Vivek Goyal

Quoted 6 lines · Gui Jianfeng

Introduce vdisktime and io weight for CFQ queue scheduling. Currently, io priority maps to a range [100,1000]. It also gets rid of cfq_slice_offset() logic and makes use the same scheduling algorithm as CFQ group does. This helps for CFQ queue and group scheduling on the same service tree.

Signed-off-by Gui Jianfeng <[email protected]>

[..]

Quoted 21 lines

block/cfq-iosched.c +17 -0

@@ -1246,47 +1278,71 @@ static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
 
 	service_tree = service_tree_for(cfqq->cfqg, cfqq_prio(cfqq),
 						cfqq_type(cfqq));
+	/*
+	 * For the time being, put the newly added CFQ queue at the end of the
+	 * service tree.
+	 */
+	if (RB_EMPTY_NODE(&cfqe->rb_node)) {
+		/*
+		 * If this CFQ queue moves to another group, the original
+		 * vdisktime makes no sense any more, reset the vdisktime
+		 * here.
+		 */
+		parent = rb_last(&service_tree->rb);
+		if (parent) {
+			u64 boost;
+			s64 __vdisktime;
+
+			__cfqe = rb_entry_entity(parent);
+			cfqe->vdisktime = __cfqe->vdisktime + CFQ_IDLE_DELAY;

block/cfq-iosched.c static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq, · line 1307

Quoted 10 lines

block/cfq-iosched.c +10 -0

+
+			/* Give some vdisktime boost according to its weight */
+			boost = cfq_get_boost(cfqd, cfqe);
+			__vdisktime = cfqe->vdisktime - boost;
+			if (__vdisktime > service_tree->min_vdisktime)
+				cfqe->vdisktime = __vdisktime;
+			else
+				cfqe->vdisktime = service_tree->min_vdisktime;
+		} else
+			cfqe->vdisktime = service_tree->min_vdisktime;

Hi Gui,

Is above logic actually working? I suspect that most of the time all the new queues will end up getting same vdisktime and that is st->min_vdisktime and there will be no service differentiation across various prio.

Reason being, on SSD, idle is disabled. So very few/no queue will consume its slice and follow reque path. So every queue will be new. Now you are doing following.

Quoted 6 lines

	cfqd->vdisktime = vdisktime_of_parent + IDLE_DELAY - boost

assume vdisktime_of_parent=st->min_vdisktime, then (IDLE_DELAY - boost) is always going to be a -ve number and hence cfqd->vdisktime will default to st->min_vdisktime. (IDLE_DELAY=200 while boost should be a huge value due to SERVICE_SHIFT thing).

Vivek,

Quoted 3 lines

Actually, I tested on rotational disk with idling disabled, I saw service differentiation between two tasks with different ioprio.
I don't have a SSD on hand, But I'll get one and do more tests.

Ok, I am really not sure how did it work for you because boost will turn out to be huge number in comparision to IDLE_DELAY or vdisktime of parent. If you have some blktrace data or if you can explain how it is working will help in understanding it better.

Quoted 59 lines · Vivek Goyal

Quoted 58 lines · Gui Jianfeng

Quoted 49 lines · Vivek Goyal

Quoted 6 lines · Gui Jianfeng

Introduce vdisktime and io weight for CFQ queue scheduling. Currently, io priority maps to a range [100,1000]. It also gets rid of cfq_slice_offset() logic and makes use the same scheduling algorithm as CFQ group does. This helps for CFQ queue and group scheduling on the same service tree.

Signed-off-by Gui Jianfeng <[email protected]>

[..]

Quoted 21 lines

block/cfq-iosched.c +17 -0

@@ -1246,47 +1278,71 @@ static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
 
 	service_tree = service_tree_for(cfqq->cfqg, cfqq_prio(cfqq),
 						cfqq_type(cfqq));
+	/*
+	 * For the time being, put the newly added CFQ queue at the end of the
+	 * service tree.
+	 */
+	if (RB_EMPTY_NODE(&cfqe->rb_node)) {
+		/*
+		 * If this CFQ queue moves to another group, the original
+		 * vdisktime makes no sense any more, reset the vdisktime
+		 * here.
+		 */
+		parent = rb_last(&service_tree->rb);
+		if (parent) {
+			u64 boost;
+			s64 __vdisktime;
+
+			__cfqe = rb_entry_entity(parent);
+			cfqe->vdisktime = __cfqe->vdisktime + CFQ_IDLE_DELAY;

block/cfq-iosched.c static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq, · line 1307

Quoted 10 lines

block/cfq-iosched.c +10 -0

+
+			/* Give some vdisktime boost according to its weight */
+			boost = cfq_get_boost(cfqd, cfqe);
+			__vdisktime = cfqe->vdisktime - boost;
+			if (__vdisktime > service_tree->min_vdisktime)
+				cfqe->vdisktime = __vdisktime;
+			else
+				cfqe->vdisktime = service_tree->min_vdisktime;
+		} else
+			cfqe->vdisktime = service_tree->min_vdisktime;

Hi Gui,

Is above logic actually working? I suspect that most of the time all the new queues will end up getting same vdisktime and that is st->min_vdisktime and there will be no service differentiation across various prio.

Reason being, on SSD, idle is disabled. So very few/no queue will consume its slice and follow reque path. So every queue will be new. Now you are doing following.

Quoted 6 lines

	cfqd->vdisktime = vdisktime_of_parent + IDLE_DELAY - boost

assume vdisktime_of_parent=st->min_vdisktime, then (IDLE_DELAY - boost) is always going to be a -ve number and hence cfqd->vdisktime will default to st->min_vdisktime. (IDLE_DELAY=200 while boost should be a huge value due to SERVICE_SHIFT thing).

Vivek,

Quoted 8 lines

Quoted 3 lines

Actually, I tested on rotational disk with idling disabled, I saw service differentiation between two tasks with different ioprio.
I don't have a SSD on hand, But I'll get one and do more tests.

Ok, I am really not sure how did it work for you because boost will turn out to be huge number in comparision to IDLE_DELAY or vdisktime of parent. If you have some blktrace data or if you can explain how it is working will help in understanding it better.

Vivek,

I think there must be something configuration wrong in my previous tests. I tested again with patch applied. I don't see service differentiation this time.
But, I do the same test on vanilla kernel, I don't see service differentiation either. I dig into it. It seems when I set slice_idle and group_idle to zero, it means i close idle window by mannual. In this case, IO tasks becomes SYNC NOIDLE workloads, they will preempts each other mutually. And the cfqq will always be put at the front of service tree. So we don't see service differentiation.

Actually, We don't want preemption happening in such case, right? So I think we should refine the preemption logic.
Thoughts?

Below is my fio job file:

[global]
directory=/hdb3
ioengine=sync
runtime=30
time_based=1
direct=1
bs=128K
size=64M
numjobs=1
exec_prerun='echo 3 > /proc/sys/vm/drop_caches'

[task-prio-0]
description=task-prio-0
rw=read
prio=0
filename=file1

[task-prio-7]
description=task-prio-7
rw=read
prio=7
filename=file2

Thanks,
Gui

block/cfq-iosched.c +4 -3

-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_type_t type)

@@ -640,10 +646,19 @@ 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_entity *cfqe = &cfqg->cfqe;
+	struct cfq_rb_root *st = cfqe->service_tree;
+	int group_slice = cfq_target_latency;
+
+	/* Calculate group slice in a hierarchical way */

Document for blkio.use_hierarchy interface

Signed-off-by Gui Jianfeng <[email protected]>

---
 Documentation/cgroups/blkio-controller.txt |   70 ++++++++++++++++++++--------
 1 files changed, 51 insertions(+), 19 deletions(-)

Documentation/cgroups/blkio-controller.txt +0 -0

index 4ed7b5c..bd01d6c 100644

Both hierarchical bandwidth division and flat

Documentation/cgroups/blkio-controller.txt +11 -12

+  bandwidth division are supported. "blkio.use_hierarchy" can be used to
+  switch between flat mode and hierarchical mode.
 
-  So this patch will allow creation of cgroup hierarhcy but at the backend
-  everything will be treated as flat. So if somebody created a hierarchy like
-  as follows.
+  Consider the following CGroup hierarchy:
 
-			root
-			/  \
-		     test1 test2
-			|
-		     test3
+			  Root
+			/  |   \
+		     Grp1  Grp2 tsk1
+	            /  \
+		 Grp3 tsk2
 
-  CFQ and throttling will practically treat all groups at same level.
+  If blkio.use_hierarchy is disabled in all CGroups, CFQ will practically treat all groups
+  at the same level.
 
-				pivot
-			     /  |   \  \
-			root  test1 test2  test3
+			     Pivot tree

Documentation/cgroups/blkio-controller.txt +11 -0

+  same view in CGroup hierarchy, it looks as follows.
+
+
+			     Pivot tree
+			    /    |    \
+			  Root  Grp1  Grp2
+			  /     /  \
+		       tsk1   Grp3 tsk2
+
+  Root, Grp1 and Grp2 are treated at the same level under Pivot tree. tsk1 stays under Root.
+  Grp3 and tsk2 are treated at the same level under Grp1. Below is the mapping between

Various user visible config options
===================================

Documentation/cgroups/blkio-controller.txt +1 -0

@@ -169,6 +190,17 @@ Proportional weight policy files
 	  dev     weight
 	  8:16    300
 
+- blkio.use_hierarchy

Documentation/cgroups/blkio-controller.txt +0 -0

 - blkio.time
 	- disk time allocated to cgroup per device in milliseconds. First
 	  two fields specify the major and minor number of the device and

Signature · 1 line

1.6.5.2

Quoted 12 lines · Gui Jianfeng

Document for blkio.use_hierarchy interface

Signed-off-by Gui Jianfeng <[email protected]>

---
 Documentation/cgroups/blkio-controller.txt |   70 ++++++++++++++++++++--------
 1 files changed, 51 insertions(+), 19 deletions(-)

Documentation/cgroups/blkio-controller.txt +0 -0

index 4ed7b5c..bd01d6c 100644

Documentation/cgroups/blkio-controller.txt Throttling/Upper Limit policy · line 96

Quoted 9 lines

Documentation/cgroups/blkio-controller.txt +3 -3

@@ -91,30 +91,51 @@ Throttling/Upper Limit policy
 
 Hierarchical Cgroups
 ====================
-- Currently none of the IO control policy supports hierarhical groups. But
-  cgroup interface does allow creation of hierarhical cgroups and internally
-  IO policies treat them as flat hierarchy.
+- Cgroup interface allows creation of hierarchical cgroups. Currently,
+  internally IO policies are able to treat them as flat hierarchy or
+  hierarchical hierarchy.

Gui, now we have 2 IO policies. Throttling policy still supports only flat mode. Can you please make it clear here that CFQ will support both flat and hierarhical mode while throttling supports only flat mode as of today.

Quoted 28 lines

Both hierarchical bandwidth division and flat

Documentation/cgroups/blkio-controller.txt +11 -12

+  bandwidth division are supported. "blkio.use_hierarchy" can be used to
+  switch between flat mode and hierarchical mode.
 
-  So this patch will allow creation of cgroup hierarhcy but at the backend
-  everything will be treated as flat. So if somebody created a hierarchy like
-  as follows.
+  Consider the following CGroup hierarchy:
 
-			root
-			/  \
-		     test1 test2
-			|
-		     test3
+			  Root
+			/  |   \
+		     Grp1  Grp2 tsk1
+	            /  \
+		 Grp3 tsk2
 
-  CFQ and throttling will practically treat all groups at same level.
+  If blkio.use_hierarchy is disabled in all CGroups, CFQ will practically treat all groups
+  at the same level.
 
-				pivot
-			     /  |   \  \
-			root  test1 test2  test3
+			     Pivot tree

Documentation/cgroups/blkio-controller.txt Throttling/Upper Limit policy · line 117

Quoted 10 lines

Documentation/cgroups/blkio-controller.txt +5 -4

+			    /  |   |   \
+			Root Grp1 Grp2 Grp3
+			 /     |
+			tsk1  tsk2
 
-  Down the line we can implement hierarchical accounting/control support
-  and also introduce a new cgroup file "use_hierarchy" which will control
-  whether cgroup hierarchy is viewed as flat or hierarchical by the policy..
-  This is how memory controller also has implemented the things.
+  If blkio.use_hierarchy is enabled in Grp1 and Grp3, CFQ will treat groups and tasks as the

I would think that before this example, we can give one simpler example where use_hierarhcy=1 in root cgroup and that would/should lead to all children group under root having use_hierarchy=1 set automatically and will look as follows.

		     	Pivot tree
			    |
		           root
			 /  |  | 
	             tsk1   G1 G2 
			   / \
			 grp3 tsk2

After this now you can give more complicated example as below where use_hierarchy=1 is only set for sub branch of tree and not the whole tree.

Quoted 18 lines

Documentation/cgroups/blkio-controller.txt +17 -0

+  same view in CGroup hierarchy, it looks as follows.
+
+
+			     Pivot tree
+			    /    |    \
+			  Root  Grp1  Grp2
+			  /     /  \
+		       tsk1   Grp3 tsk2
+
+  Root, Grp1 and Grp2 are treated at the same level under Pivot tree. tsk1 stays under Root.
+  Grp3 and tsk2 are treated at the same level under Grp1. Below is the mapping between
+  task io priority and io weight:
+
+	    prio       0    1     2    3    4    5    6     7
+	    weight  1000  868   740  612  484  356  228   100
+
+  Note1: Regardless of the use_hierarchy setting in Root group, Root group is always put onto

Documentation/cgroups/blkio-controller.txt Throttling/Upper Limit policy · line 138

Quoted 5 lines

Documentation/cgroups/blkio-controller.txt +4 -0

+  Pivot tree.
+
+  Note2: Currently, "blkio.use_hierarchy" only effects proportional bandwidth division. For
+  Throttling logic, it still continue to treat everything as flat.

Ok, I see you mentioned throttling flat mode here. I guess it is better to clarify it in the beginning itself.

Quoted 8 lines

Various user visible config options
===================================

Documentation/cgroups/blkio-controller.txt +1 -0

@@ -169,6 +190,17 @@ Proportional weight policy files
 	  dev     weight
 	  8:16    300
 
+- blkio.use_hierarchy

Documentation/cgroups/blkio-controller.txt Proportional weight policy files · line 203

Quoted 10 lines

Documentation/cgroups/blkio-controller.txt +10 -0

+	- Switch between hierarchical mode and flat mode as stated above.
+	  blkio.use_hierarchy == 1 means hierarchical mode is enabled.
+	  blkio.use_hierarchy == 0 means flat mode is enabled.
+	  You can set this interface only if there isn't any child CGroup under
+	  this CGroup. If one CGroup's blkio.use_hierarchy is set, the created
+	  children will inherit it. it's not allowed to unset it in children.
+	  The default mode in Root CGroup is flat.
+	  blkio.use_hierarchy only works for proportional bandwidth division
+	  as of today and doesn't have any effect on throttling logic.
+

This is good. Makes use_hierarchy behavior for children and subtree very clear.

Quoted 11 lines

Documentation/cgroups/blkio-controller.txt +0 -0

 - blkio.time
 	- disk time allocated to cgroup per device in milliseconds. First
 	  two fields specify the major and minor number of the device and

Signature · 1 line

1.6.5.2