[PATCH V4 11/16] block, bfq: reduce idling only in symmetric scenarios

[Paolo Valente]

From: Arianna Avanzini 

A seeky queue (i..e, a queue containing random requests) is assigned a
very small device-idling slice, for throughput issues. Unfortunately,
given the process associated with a seeky queue, this behavior causes
the following problem: if the process, say P, performs sync I/O and
has a higher weight than some other processes doing I/O and associated
with non-seeky queues, then BFQ may fail to guarantee to P its
reserved share of the throughput. The reason is that idling is key
for providing service guarantees to processes doing sync I/O [1].

This commit addresses this issue by allowing the device-idling slice
to be reduced for a seeky queue only if the scenario happens to be
symmetric, i.e., if all the queues are to receive the same share of
the throughput.

[1] P. Valente, A. Avanzini, "Evolution of the BFQ Storage I/O
Scheduler", Proceedings of the First Workshop on Mobile System
Technologies (MST-2015), May 2015.
http://algogroup.unimore.it/people/paolo/disk_sched/mst-2015.pdf

Signed-off-by: Arianna Avanzini 
Signed-off-by: Riccardo Pizzetti 
Signed-off-by: Samuele Zecchini 
Signed-off-by: Paolo Valente 
---
 block/bfq-iosched.c | 287 ++--
 1 file changed, 280 insertions(+), 7 deletions(-)

diff --git a/block/bfq-iosched.c b/block/bfq-iosched.c
index 6e7388a..b97801f 100644
--- a/block/bfq-iosched.c
+++ b/block/bfq-iosched.c
@@ -183,6 +183,20 @@ struct bfq_sched_data {
 };
 
 /**
+ * struct bfq_weight_counter - counter of the number of all active entities
+ * with a given weight.
+ */
+struct bfq_weight_counter {
+   unsigned int weight; /* weight of the entities this counter refers to */
+   unsigned int num_active; /* nr of active entities with this weight */
+   /*
+* Weights tree member (see bfq_data's @queue_weights_tree and
+* @group_weights_tree)
+*/
+   struct rb_node weights_node;
+};
+
+/**
  * struct bfq_entity - schedulable entity.
  *
  * A bfq_entity is used to represent either a bfq_queue (leaf node in the
@@ -212,6 +226,8 @@ struct bfq_sched_data {
 struct bfq_entity {
/* service_tree member */
struct rb_node rb_node;
+   /* pointer to the weight counter associated with this entity */
+   struct bfq_weight_counter *weight_counter;
 
/*
 * Flag, true if the entity is on a tree (either the active or
@@ -456,6 +472,25 @@ struct bfq_data {
struct bfq_group *root_group;
 
/*
+* rbtree of weight counters of @bfq_queues, sorted by
+* weight. Used to keep track of whether all @bfq_queues have
+* the same weight. The tree contains one counter for each
+* distinct weight associated to some active and not
+* weight-raised @bfq_queue (see the comments to the functions
+* bfq_weights_tree_[add|remove] for further details).
+*/
+   struct rb_root queue_weights_tree;
+   /*
+* rbtree of non-queue @bfq_entity weight counters, sorted by
+* weight. Used to keep track of whether all @bfq_groups have
+* the same weight. The tree contains one counter for each
+* distinct weight associated to some active @bfq_group (see
+* the comments to the functions bfq_weights_tree_[add|remove]
+* for further details).
+*/
+   struct rb_root group_weights_tree;
+
+   /*
 * Number of bfq_queues containing requests (including the
 * queue in service, even if it is idling).
 */
@@ -791,6 +826,11 @@ struct bfq_group_data {
  * to avoid too many special cases during group creation/
  * migration.
  * @stats: stats for this bfqg.
+ * @active_entities: number of active entities belonging to the group;
+ *   unused for the root group. Used to know whether there
+ *   are groups with more than one active @bfq_entity
+ *   (see the comments to the function
+ *   bfq_bfqq_may_idle()).
  * @rq_pos_tree: rbtree sorted by next_request position, used when
  *   determining if two or more queues have interleaving
  *   requests (see bfq_find_close_cooperator()).
@@ -818,6 +858,8 @@ struct bfq_group {
 
struct bfq_entity *my_entity;
 
+   int active_entities;
+
struct rb_root rq_pos_tree;
 
struct bfqg_stats stats;
@@ -1254,12 +1296,27 @@ static bool bfq_update_parent_budget(struct bfq_entity 
*next_in_service)
  * a candidate for next service (i.e, a candidate entity to serve
  * after the in-service entity is expired). The function then returns
  * true.
+ *
+ * In contrast, the entity could stil be a candidate for next service
+ * if it is not a queue, and has more than one child. In fact, even if
+ * one 

[PATCH V4 11/16] block, bfq: reduce idling only in symmetric scenarios

[Paolo Valente]

From: Arianna Avanzini 

A seeky queue (i..e, a queue containing random requests) is assigned a
very small device-idling slice, for throughput issues. Unfortunately,
given the process associated with a seeky queue, this behavior causes
the following problem: if the process, say P, performs sync I/O and
has a higher weight than some other processes doing I/O and associated
with non-seeky queues, then BFQ may fail to guarantee to P its
reserved share of the throughput. The reason is that idling is key
for providing service guarantees to processes doing sync I/O [1].

This commit addresses this issue by allowing the device-idling slice
to be reduced for a seeky queue only if the scenario happens to be
symmetric, i.e., if all the queues are to receive the same share of
the throughput.

[1] P. Valente, A. Avanzini, "Evolution of the BFQ Storage I/O
Scheduler", Proceedings of the First Workshop on Mobile System
Technologies (MST-2015), May 2015.
http://algogroup.unimore.it/people/paolo/disk_sched/mst-2015.pdf

Signed-off-by: Arianna Avanzini 
Signed-off-by: Riccardo Pizzetti 
Signed-off-by: Samuele Zecchini 
Signed-off-by: Paolo Valente 
---
 block/bfq-iosched.c | 287 ++--
 1 file changed, 280 insertions(+), 7 deletions(-)

diff --git a/block/bfq-iosched.c b/block/bfq-iosched.c
index 6e7388a..b97801f 100644
--- a/block/bfq-iosched.c
+++ b/block/bfq-iosched.c
@@ -183,6 +183,20 @@ struct bfq_sched_data {
 };
 
 /**
+ * struct bfq_weight_counter - counter of the number of all active entities
+ * with a given weight.
+ */
+struct bfq_weight_counter {
+   unsigned int weight; /* weight of the entities this counter refers to */
+   unsigned int num_active; /* nr of active entities with this weight */
+   /*
+* Weights tree member (see bfq_data's @queue_weights_tree and
+* @group_weights_tree)
+*/
+   struct rb_node weights_node;
+};
+
+/**
  * struct bfq_entity - schedulable entity.
  *
  * A bfq_entity is used to represent either a bfq_queue (leaf node in the
@@ -212,6 +226,8 @@ struct bfq_sched_data {
 struct bfq_entity {
/* service_tree member */
struct rb_node rb_node;
+   /* pointer to the weight counter associated with this entity */
+   struct bfq_weight_counter *weight_counter;
 
/*
 * Flag, true if the entity is on a tree (either the active or
@@ -456,6 +472,25 @@ struct bfq_data {
struct bfq_group *root_group;
 
/*
+* rbtree of weight counters of @bfq_queues, sorted by
+* weight. Used to keep track of whether all @bfq_queues have
+* the same weight. The tree contains one counter for each
+* distinct weight associated to some active and not
+* weight-raised @bfq_queue (see the comments to the functions
+* bfq_weights_tree_[add|remove] for further details).
+*/
+   struct rb_root queue_weights_tree;
+   /*
+* rbtree of non-queue @bfq_entity weight counters, sorted by
+* weight. Used to keep track of whether all @bfq_groups have
+* the same weight. The tree contains one counter for each
+* distinct weight associated to some active @bfq_group (see
+* the comments to the functions bfq_weights_tree_[add|remove]
+* for further details).
+*/
+   struct rb_root group_weights_tree;
+
+   /*
 * Number of bfq_queues containing requests (including the
 * queue in service, even if it is idling).
 */
@@ -791,6 +826,11 @@ struct bfq_group_data {
  * to avoid too many special cases during group creation/
  * migration.
  * @stats: stats for this bfqg.
+ * @active_entities: number of active entities belonging to the group;
+ *   unused for the root group. Used to know whether there
+ *   are groups with more than one active @bfq_entity
+ *   (see the comments to the function
+ *   bfq_bfqq_may_idle()).
  * @rq_pos_tree: rbtree sorted by next_request position, used when
  *   determining if two or more queues have interleaving
  *   requests (see bfq_find_close_cooperator()).
@@ -818,6 +858,8 @@ struct bfq_group {
 
struct bfq_entity *my_entity;
 
+   int active_entities;
+
struct rb_root rq_pos_tree;
 
struct bfqg_stats stats;
@@ -1254,12 +1296,27 @@ static bool bfq_update_parent_budget(struct bfq_entity 
*next_in_service)
  * a candidate for next service (i.e, a candidate entity to serve
  * after the in-service entity is expired). The function then returns
  * true.
+ *
+ * In contrast, the entity could stil be a candidate for next service
+ * if it is not a queue, and has more than one child. In fact, even if
+ * one of its children is about to be set in service, other children
+ * may still be the next to serve. As a consequence, a non-queue
+ * entity