Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1621286 > unrolled thread

[PATCH V3 00/16] Introduce the BFQ I/O scheduler

Back to article view | Back to linux.kernel

Contents

  [PATCH V3 00/16] Introduce the BFQ I/O scheduler Paolo Valente <paolo.valente@linaro.org> - 2017-04-11 15:50 +0200
    [PATCH V3 12/16] block, bfq: boost the throughput on NCQ-capable flash-based devices Paolo Valente <paolo.valente@linaro.org> - 2017-04-11 15:50 +0200
    [PATCH V3 11/16] block, bfq: reduce idling only in symmetric scenarios Paolo Valente <paolo.valente@linaro.org> - 2017-04-11 15:50 +0200
    [PATCH V3 03/16] block, bfq: improve throughput boosting Paolo Valente <paolo.valente@linaro.org> - 2017-04-11 15:50 +0200
    [PATCH V3 09/16] block, bfq: reduce latency during request-pool saturation Paolo Valente <paolo.valente@linaro.org> - 2017-04-11 15:50 +0200
    Re: [PATCH V3 00/16] Introduce the BFQ I/O scheduler Bart Van Assche <Bart.VanAssche@sandisk.com> - 2017-04-11 16:40 +0200
      Re: [PATCH V3 00/16] Introduce the BFQ I/O scheduler Paolo Valente <paolo.valente@linaro.org> - 2017-04-11 19:40 +0200
        Re: [PATCH V3 00/16] Introduce the BFQ I/O scheduler Bart Van Assche <Bart.VanAssche@sandisk.com> - 2017-04-11 20:40 +0200
          Re: [PATCH V3 00/16] Introduce the BFQ I/O scheduler Paolo Valente <paolo.valente@linaro.org> - 2017-04-12 08:10 +0200
            Re: [PATCH V3 00/16] Introduce the BFQ I/O scheduler Bart Van Assche <Bart.VanAssche@sandisk.com> - 2017-04-12 17:40 +0200
              Re: [PATCH V3 00/16] Introduce the BFQ I/O scheduler Paolo Valente <paolo.valente@linaro.org> - 2017-04-12 18:10 +0200
    Re: [PATCH V3 02/16] block, bfq: add full hierarchical scheduling  and cgroups support Tejun Heo <tj@kernel.org> - 2017-04-11 23:50 +0200
      Re: [PATCH V3 02/16] block, bfq: add full hierarchical scheduling and cgroups support Paolo Valente <paolo.valente@linaro.org> - 2017-04-12 07:30 +0200
        Re: [PATCH V3 02/16] block, bfq: add full hierarchical scheduling  and cgroups support Tejun Heo <tj@kernel.org> - 2017-04-18 09:10 +0200
          Re: [PATCH V3 02/16] block, bfq: add full hierarchical scheduling and cgroups support Paolo Valente <paolo.valente@linaro.org> - 2017-04-19 07:40 +0200
            Re: [PATCH V3 02/16] block, bfq: add full hierarchical scheduling and cgroups support Paolo Valente <paolo.valente@linaro.org> - 2017-04-19 09:10 +0200
    Re: [PATCH V3 00/16] Introduce the BFQ I/O scheduler Heinz Diehl <htd+ml@fritha.org> - 2017-04-16 10:20 +0200

#1621286 — [PATCH V3 00/16] Introduce the BFQ I/O scheduler

Hi,
new patch series, addressing (both) issues raised by Bart [1].

Thanks,
Paolo

[1] https://lkml.org/lkml/2017/3/31/393

Arianna Avanzini (4):
  block, bfq: add full hierarchical scheduling and cgroups support
  block, bfq: add Early Queue Merge (EQM)
  block, bfq: reduce idling only in symmetric scenarios
  block, bfq: handle bursts of queue activations

Paolo Valente (12):
  block, bfq: introduce the BFQ-v0 I/O scheduler as an extra scheduler
  block, bfq: improve throughput boosting
  block, bfq: modify the peak-rate estimator
  block, bfq: add more fairness with writes and slow processes
  block, bfq: improve responsiveness
  block, bfq: reduce I/O latency for soft real-time applications
  block, bfq: preserve a low latency also with NCQ-capable drives
  block, bfq: reduce latency during request-pool saturation
  block, bfq: boost the throughput on NCQ-capable flash-based devices
  block, bfq: boost the throughput with random I/O on NCQ-capable HDDs
  block, bfq: remove all get and put of I/O contexts
  block, bfq: split bfq-iosched.c into multiple source files

 Documentation/block/00-INDEX        |    2 +
 Documentation/block/bfq-iosched.txt |  531 ++++
 block/Kconfig.iosched               |   21 +
 block/Makefile                      |    1 +
 block/bfq-cgroup.c                  | 1139 ++++++++
 block/bfq-iosched.c                 | 5047 +++++++++++++++++++++++++++++++++++
 block/bfq-iosched.h                 |  942 +++++++
 block/bfq-wf2q.c                    | 1616 +++++++++++
 include/linux/blkdev.h              |    2 +-
 9 files changed, 9300 insertions(+), 1 deletion(-)
 create mode 100644 Documentation/block/bfq-iosched.txt
 create mode 100644 block/bfq-cgroup.c
 create mode 100644 block/bfq-iosched.c
 create mode 100644 block/bfq-iosched.h
 create mode 100644 block/bfq-wf2q.c

--
2.10.0

[toc] | [next] | [standalone]

#1621289 — [PATCH V3 12/16] block, bfq: boost the throughput on NCQ-capable flash-based devices

This patch boosts the throughput on NCQ-capable flash-based devices,
while still preserving latency guarantees for interactive and soft
real-time applications. The throughput is boosted by just not idling
the device when the in-service queue remains empty, even if the queue
is sync and has a non-null idle window. This helps to keep the drive's
internal queue full, which is necessary to achieve maximum
performance. This solution to boost the throughput is a port of
commits a68bbdd and f7d7b7a for CFQ.

As already highlighted in a previous patch, allowing the device to
prefetch and internally reorder requests trivially causes loss of
control on the request service order, and hence on service guarantees.
Fortunately, as discussed in detail in the comments on the function
bfq_bfqq_may_idle(), if every process has to receive the same
fraction of the throughput, then the service order enforced by the
internal scheduler of a flash-based device is relatively close to that
enforced by BFQ. In particular, it is close enough to let service
guarantees be substantially preserved.

Things change in an asymmetric scenario, i.e., if not every process
has to receive the same fraction of the throughput. In this case, to
guarantee the desired throughput distribution, the device must be
prevented from prefetching requests. This is exactly what this patch
does in asymmetric scenarios.

Signed-off-by: Paolo Valente <paolo.valente@linaro.org>
Signed-off-by: Arianna Avanzini <avanzini.arianna@gmail.com>
---
 block/bfq-iosched.c | 154 ++++++++++++++++++++++++++++++++++++----------------
 1 file changed, 106 insertions(+), 48 deletions(-)

diff --git a/block/bfq-iosched.c b/block/bfq-iosched.c
index b97801f..2081784 100644
--- a/block/bfq-iosched.c
+++ b/block/bfq-iosched.c
@@ -6442,15 +6442,25 @@ static bool bfq_bfqq_may_idle(struct bfq_queue *bfqq)
 	 * The value of the variable is computed considering that
 	 * idling is usually beneficial for the throughput if:
 	 * (a) the device is not NCQ-capable, or
-	 * (b) regardless of the presence of NCQ, the request pattern
-	 *     for bfqq is I/O-bound (possible throughput losses
-	 *     caused by granting idling to seeky queues are mitigated
-	 *     by the fact that, in all scenarios where boosting
-	 *     throughput is the best thing to do, i.e., in all
-	 *     symmetric scenarios, only a minimal idle time is
-	 *     allowed to seeky queues).
+	 * (b) regardless of the presence of NCQ, the device is rotational
+	 *     and the request pattern for bfqq is I/O-bound (possible
+	 *     throughput losses caused by granting idling to seeky queues
+	 *     are mitigated by the fact that, in all scenarios where
+	 *     boosting throughput is the best thing to do, i.e., in all
+	 *     symmetric scenarios, only a minimal idle time is allowed to
+	 *     seeky queues).
+	 *
+	 * Secondly, and in contrast to the above item (b), idling an
+	 * NCQ-capable flash-based device would not boost the
+	 * throughput even with intense I/O; rather it would lower
+	 * the throughput in proportion to how fast the device
+	 * is. Accordingly, the next variable is true if any of the
+	 * above conditions (a) and (b) is true, and, in particular,
+	 * happens to be false if bfqd is an NCQ-capable flash-based
+	 * device.
 	 */
-	idling_boosts_thr = !bfqd->hw_tag || bfq_bfqq_IO_bound(bfqq);
+	idling_boosts_thr = !bfqd->hw_tag ||
+		(!blk_queue_nonrot(bfqd->queue) && bfq_bfqq_IO_bound(bfqq));
 
 	/*
 	 * The value of the next variable,
@@ -6491,14 +6501,16 @@ static bool bfq_bfqq_may_idle(struct bfq_queue *bfqq)
 		bfqd->wr_busy_queues == 0;
 
 	/*
-	 * There is then a case where idling must be performed not for
-	 * throughput concerns, but to preserve service guarantees. To
-	 * introduce it, we can note that allowing the drive to
-	 * enqueue more than one request at a time, and hence
+	 * There is then a case where idling must be performed not
+	 * for throughput concerns, but to preserve service
+	 * guarantees.
+	 *
+	 * To introduce this case, we can note that allowing the drive
+	 * to enqueue more than one request at a time, and hence
 	 * delegating de facto final scheduling decisions to the
-	 * drive's internal scheduler, causes loss of control on the
+	 * drive's internal scheduler, entails loss of control on the
 	 * actual request service order. In particular, the critical
-	 * situation is when requests from different processes happens
+	 * situation is when requests from different processes happen
 	 * to be present, at the same time, in the internal queue(s)
 	 * of the drive. In such a situation, the drive, by deciding
 	 * the service order of the internally-queued requests, does
@@ -6509,51 +6521,97 @@ static bool bfq_bfqq_may_idle(struct bfq_queue *bfqq)
 	 * the service distribution enforced by the drive's internal
 	 * scheduler is likely to coincide with the desired
 	 * device-throughput distribution only in a completely
-	 * symmetric scenario where: (i) each of these processes must
-	 * get the same throughput as the others; (ii) all these
-	 * processes have the same I/O pattern (either sequential or
-	 * random).  In fact, in such a scenario, the drive will tend
-	 * to treat the requests of each of these processes in about
-	 * the same way as the requests of the others, and thus to
-	 * provide each of these processes with about the same
-	 * throughput (which is exactly the desired throughput
-	 * distribution). In contrast, in any asymmetric scenario,
-	 * device idling is certainly needed to guarantee that bfqq
-	 * receives its assigned fraction of the device throughput
-	 * (see [1] for details).
+	 * symmetric scenario where:
+	 * (i)  each of these processes must get the same throughput as
+	 *      the others;
+	 * (ii) all these processes have the same I/O pattern
+		(either sequential or random).
+	 * In fact, in such a scenario, the drive will tend to treat
+	 * the requests of each of these processes in about the same
+	 * way as the requests of the others, and thus to provide
+	 * each of these processes with about the same throughput
+	 * (which is exactly the desired throughput distribution). In
+	 * contrast, in any asymmetric scenario, device idling is
+	 * certainly needed to guarantee that bfqq receives its
+	 * assigned fraction of the device throughput (see [1] for
+	 * details).
+	 *
+	 * We address this issue by controlling, actually, only the
+	 * symmetry sub-condition (i), i.e., provided that
+	 * sub-condition (i) holds, idling is not performed,
+	 * regardless of whether sub-condition (ii) holds. In other
+	 * words, only if sub-condition (i) holds, then idling is
+	 * allowed, and the device tends to be prevented from queueing
+	 * many requests, possibly of several processes. The reason
+	 * for not controlling also sub-condition (ii) is that we
+	 * exploit preemption to preserve guarantees in case of
+	 * symmetric scenarios, even if (ii) does not hold, as
+	 * explained in the next two paragraphs.
+	 *
+	 * Even if a queue, say Q, is expired when it remains idle, Q
+	 * can still preempt the new in-service queue if the next
+	 * request of Q arrives soon (see the comments on
+	 * bfq_bfqq_update_budg_for_activation). If all queues and
+	 * groups have the same weight, this form of preemption,
+	 * combined with the hole-recovery heuristic described in the
+	 * comments on function bfq_bfqq_update_budg_for_activation,
+	 * are enough to preserve a correct bandwidth distribution in
+	 * the mid term, even without idling. In fact, even if not
+	 * idling allows the internal queues of the device to contain
+	 * many requests, and thus to reorder requests, we can rather
+	 * safely assume that the internal scheduler still preserves a
+	 * minimum of mid-term fairness. The motivation for using
+	 * preemption instead of idling is that, by not idling,
+	 * service guarantees are preserved without minimally
+	 * sacrificing throughput. In other words, both a high
+	 * throughput and its desired distribution are obtained.
+	 *
+	 * More precisely, this preemption-based, idleless approach
+	 * provides fairness in terms of IOPS, and not sectors per
+	 * second. This can be seen with a simple example. Suppose
+	 * that there are two queues with the same weight, but that
+	 * the first queue receives requests of 8 sectors, while the
+	 * second queue receives requests of 1024 sectors. In
+	 * addition, suppose that each of the two queues contains at
+	 * most one request at a time, which implies that each queue
+	 * always remains idle after it is served. Finally, after
+	 * remaining idle, each queue receives very quickly a new
+	 * request. It follows that the two queues are served
+	 * alternatively, preempting each other if needed. This
+	 * implies that, although both queues have the same weight,
+	 * the queue with large requests receives a service that is
+	 * 1024/8 times as high as the service received by the other
+	 * queue.
 	 *
-	 * As for sub-condition (i), actually we check only whether
-	 * bfqq is being weight-raised. In fact, if bfqq is not being
-	 * weight-raised, we have that:
-	 * - if the process associated with bfqq is not I/O-bound, then
-	 *   it is not either latency- or throughput-critical; therefore
-	 *   idling is not needed for bfqq;
-	 * - if the process asociated with bfqq is I/O-bound, then
-	 *   idling is already granted with bfqq (see the comments on
-	 *   idling_boosts_thr).
+	 * On the other hand, device idling is performed, and thus
+	 * pure sector-domain guarantees are provided, for the
+	 * following queues, which are likely to need stronger
+	 * throughput guarantees: weight-raised queues, and queues
+	 * with a higher weight than other queues. When such queues
+	 * are active, sub-condition (i) is false, which triggers
+	 * device idling.
 	 *
-	 * We do not check sub-condition (ii) at all, i.e., the next
-	 * variable is true if and only if bfqq is being
-	 * weight-raised. We do not need to control sub-condition (ii)
-	 * for the following reason:
-	 * - if bfqq is being weight-raised, then idling is already
-	 *   guaranteed to bfqq by sub-condition (i);
-	 * - if bfqq is not being weight-raised, then idling is
-	 *   already guaranteed to bfqq (only) if it matters, i.e., if
-	 *   bfqq is associated to a currently I/O-bound process (see
-	 *   the above comment on sub-condition (i)).
+	 * According to the above considerations, the next variable is
+	 * true (only) if sub-condition (i) holds. To compute the
+	 * value of this variable, we not only use the return value of
+	 * the function bfq_symmetric_scenario(), but also check
+	 * whether bfqq is being weight-raised, because
+	 * bfq_symmetric_scenario() does not take into account also
+	 * weight-raised queues (see comments on
+	 * bfq_weights_tree_add()).
 	 *
 	 * As a side note, it is worth considering that the above
 	 * device-idling countermeasures may however fail in the
 	 * following unlucky scenario: if idling is (correctly)
-	 * disabled in a time period during which the symmetry
-	 * sub-condition holds, and hence the device is allowed to
+	 * disabled in a time period during which all symmetry
+	 * sub-conditions hold, and hence the device is allowed to
 	 * enqueue many requests, but at some later point in time some
 	 * sub-condition stops to hold, then it may become impossible
 	 * to let requests be served in the desired order until all
 	 * the requests already queued in the device have been served.
 	 */
-	asymmetric_scenario = bfqq->wr_coeff > 1;
+	asymmetric_scenario = bfqq->wr_coeff > 1 ||
+		!bfq_symmetric_scenario(bfqd);
 
 	/*
 	 * We have now all the components we need to compute the return
-- 
2.10.0

[toc] | [prev] | [next] | [standalone]

#1621290 — [PATCH V3 11/16] block, bfq: reduce idling only in symmetric scenarios

From: Arianna Avanzini <avanzini.arianna@gmail.com>

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 <avanzini.arianna@gmail.com>
Signed-off-by: Riccardo Pizzetti <riccardo.pizzetti@gmail.com>
Signed-off-by: Samuele Zecchini <samuele.zecchini92@gmail.com>
Signed-off-by: Paolo Valente <paolo.valente@linaro.org>
---
 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 is not a candidate for next-service only if it has only one
+ * child. And only if this condition holds, then the function returns
+ * true for a non-queue entity.
  */
 static bool bfq_no_longer_next_in_service(struct bfq_entity *entity)
 {
+	struct bfq_group *bfqg;
+
 	if (bfq_entity_to_bfqq(entity))
 		return true;
 
+	bfqg = container_of(entity, struct bfq_group, entity);
+
+	if (bfqg->active_entities == 1)
+		return true;
+
 	return false;
 }
 
@@ -1498,6 +1555,15 @@ static void bfq_update_active_tree(struct rb_node *node)
 	goto up;
 }
 
+static void bfq_weights_tree_add(struct bfq_data *bfqd,
+				 struct bfq_entity *entity,
+				 struct rb_root *root);
+
+static void bfq_weights_tree_remove(struct bfq_data *bfqd,
+				    struct bfq_entity *entity,
+				    struct rb_root *root);
+
+
 /**
  * bfq_active_insert - insert an entity in the active tree of its
  *                     group/device.
@@ -1536,6 +1602,13 @@ static void bfq_active_insert(struct bfq_service_tree *st,
 #endif
 	if (bfqq)
 		list_add(&bfqq->bfqq_list, &bfqq->bfqd->active_list);
+#ifdef CONFIG_BFQ_GROUP_IOSCHED
+	else /* bfq_group */
+		bfq_weights_tree_add(bfqd, entity, &bfqd->group_weights_tree);
+
+	if (bfqg != bfqd->root_group)
+		bfqg->active_entities++;
+#endif
 }
 
 /**
@@ -1631,6 +1704,14 @@ static void bfq_active_extract(struct bfq_service_tree *st,
 #endif
 	if (bfqq)
 		list_del(&bfqq->bfqq_list);
+#ifdef CONFIG_BFQ_GROUP_IOSCHED
+	else /* bfq_group */
+		bfq_weights_tree_remove(bfqd, entity,
+					&bfqd->group_weights_tree);
+
+	if (bfqg != bfqd->root_group)
+		bfqg->active_entities--;
+#endif
 }
 
 /**
@@ -1731,6 +1812,7 @@ __bfq_entity_update_weight_prio(struct bfq_service_tree *old_st,
 		struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);
 		unsigned int prev_weight, new_weight;
 		struct bfq_data *bfqd = NULL;
+		struct rb_root *root;
 #ifdef CONFIG_BFQ_GROUP_IOSCHED
 		struct bfq_sched_data *sd;
 		struct bfq_group *bfqg;
@@ -1780,7 +1862,26 @@ __bfq_entity_update_weight_prio(struct bfq_service_tree *old_st,
 		prev_weight = entity->weight;
 		new_weight = entity->orig_weight *
 			     (bfqq ? bfqq->wr_coeff : 1);
+		/*
+		 * If the weight of the entity changes, remove the entity
+		 * from its old weight counter (if there is a counter
+		 * associated with the entity), and add it to the counter
+		 * associated with its new weight.
+		 */
+		if (prev_weight != new_weight) {
+			root = bfqq ? &bfqd->queue_weights_tree :
+				      &bfqd->group_weights_tree;
+			bfq_weights_tree_remove(bfqd, entity, root);
+		}
 		entity->weight = new_weight;
+		/*
+		 * Add the entity to its weights tree only if it is
+		 * not associated with a weight-raised queue.
+		 */
+		if (prev_weight != new_weight &&
+		    (bfqq ? bfqq->wr_coeff == 1 : 1))
+			/* If we get here, root has been initialized. */
+			bfq_weights_tree_add(bfqd, entity, root);
 
 		new_st->wsum += entity->weight;
 
@@ -2606,6 +2707,10 @@ static void bfq_del_bfqq_busy(struct bfq_data *bfqd, struct bfq_queue *bfqq,
 
 	bfqd->busy_queues--;
 
+	if (!bfqq->dispatched)
+		bfq_weights_tree_remove(bfqd, &bfqq->entity,
+					&bfqd->queue_weights_tree);
+
 	if (bfqq->wr_coeff > 1)
 		bfqd->wr_busy_queues--;
 
@@ -2626,6 +2731,11 @@ static void bfq_add_bfqq_busy(struct bfq_data *bfqd, struct bfq_queue *bfqq)
 	bfq_mark_bfqq_busy(bfqq);
 	bfqd->busy_queues++;
 
+	if (!bfqq->dispatched)
+		if (bfqq->wr_coeff == 1)
+			bfq_weights_tree_add(bfqd, &bfqq->entity,
+					     &bfqd->queue_weights_tree);
+
 	if (bfqq->wr_coeff > 1)
 		bfqd->wr_busy_queues++;
 }
@@ -3028,6 +3138,7 @@ static void bfq_pd_init(struct blkg_policy_data *pd)
 				   * in bfq_init_queue()
 				   */
 	bfqg->bfqd = bfqd;
+	bfqg->active_entities = 0;
 	bfqg->rq_pos_tree = RB_ROOT;
 }
 
@@ -3916,6 +4027,158 @@ static void bfq_pos_tree_add_move(struct bfq_data *bfqd, struct bfq_queue *bfqq)
 }
 
 /*
+ * Tell whether there are active queues or groups with differentiated weights.
+ */
+static bool bfq_differentiated_weights(struct bfq_data *bfqd)
+{
+	/*
+	 * For weights to differ, at least one of the trees must contain
+	 * at least two nodes.
+	 */
+	return (!RB_EMPTY_ROOT(&bfqd->queue_weights_tree) &&
+		(bfqd->queue_weights_tree.rb_node->rb_left ||
+		 bfqd->queue_weights_tree.rb_node->rb_right)
+#ifdef CONFIG_BFQ_GROUP_IOSCHED
+	       ) ||
+	       (!RB_EMPTY_ROOT(&bfqd->group_weights_tree) &&
+		(bfqd->group_weights_tree.rb_node->rb_left ||
+		 bfqd->group_weights_tree.rb_node->rb_right)
+#endif
+	       );
+}
+
+/*
+ * The following function returns true if every queue must receive the
+ * same share of the throughput (this condition is used when deciding
+ * whether idling may be disabled, see the comments in the function
+ * bfq_bfqq_may_idle()).
+ *
+ * Such a scenario occurs when:
+ * 1) all active queues have the same weight,
+ * 2) all active groups at the same level in the groups tree have the same
+ *    weight,
+ * 3) all active groups at the same level in the groups tree have the same
+ *    number of children.
+ *
+ * Unfortunately, keeping the necessary state for evaluating exactly the
+ * above symmetry conditions would be quite complex and time-consuming.
+ * Therefore this function evaluates, instead, the following stronger
+ * sub-conditions, for which it is much easier to maintain the needed
+ * state:
+ * 1) all active queues have the same weight,
+ * 2) all active groups have the same weight,
+ * 3) all active groups have at most one active child each.
+ * In particular, the last two conditions are always true if hierarchical
+ * support and the cgroups interface are not enabled, thus no state needs
+ * to be maintained in this case.
+ */
+static bool bfq_symmetric_scenario(struct bfq_data *bfqd)
+{
+	return !bfq_differentiated_weights(bfqd);
+}
+
+/*
+ * If the weight-counter tree passed as input contains no counter for
+ * the weight of the input entity, then add that counter; otherwise just
+ * increment the existing counter.
+ *
+ * Note that weight-counter trees contain few nodes in mostly symmetric
+ * scenarios. For example, if all queues have the same weight, then the
+ * weight-counter tree for the queues may contain at most one node.
+ * This holds even if low_latency is on, because weight-raised queues
+ * are not inserted in the tree.
+ * In most scenarios, the rate at which nodes are created/destroyed
+ * should be low too.
+ */
+static void bfq_weights_tree_add(struct bfq_data *bfqd,
+				 struct bfq_entity *entity,
+				 struct rb_root *root)
+{
+	struct rb_node **new = &(root->rb_node), *parent = NULL;
+
+	/*
+	 * Do not insert if the entity is already associated with a
+	 * counter, which happens if:
+	 *   1) the entity is associated with a queue,
+	 *   2) a request arrival has caused the queue to become both
+	 *      non-weight-raised, and hence change its weight, and
+	 *      backlogged; in this respect, each of the two events
+	 *      causes an invocation of this function,
+	 *   3) this is the invocation of this function caused by the
+	 *      second event. This second invocation is actually useless,
+	 *      and we handle this fact by exiting immediately. More
+	 *      efficient or clearer solutions might possibly be adopted.
+	 */
+	if (entity->weight_counter)
+		return;
+
+	while (*new) {
+		struct bfq_weight_counter *__counter = container_of(*new,
+						struct bfq_weight_counter,
+						weights_node);
+		parent = *new;
+
+		if (entity->weight == __counter->weight) {
+			entity->weight_counter = __counter;
+			goto inc_counter;
+		}
+		if (entity->weight < __counter->weight)
+			new = &((*new)->rb_left);
+		else
+			new = &((*new)->rb_right);
+	}
+
+	entity->weight_counter = kzalloc(sizeof(struct bfq_weight_counter),
+					 GFP_ATOMIC);
+
+	/*
+	 * In the unlucky event of an allocation failure, we just
+	 * exit. This will cause the weight of entity to not be
+	 * considered in bfq_differentiated_weights, which, in its
+	 * turn, causes the scenario to be deemed wrongly symmetric in
+	 * case entity's weight would have been the only weight making
+	 * the scenario asymmetric. On the bright side, no unbalance
+	 * will however occur when entity becomes inactive again (the
+	 * invocation of this function is triggered by an activation
+	 * of entity). In fact, bfq_weights_tree_remove does nothing
+	 * if !entity->weight_counter.
+	 */
+	if (unlikely(!entity->weight_counter))
+		return;
+
+	entity->weight_counter->weight = entity->weight;
+	rb_link_node(&entity->weight_counter->weights_node, parent, new);
+	rb_insert_color(&entity->weight_counter->weights_node, root);
+
+inc_counter:
+	entity->weight_counter->num_active++;
+}
+
+/*
+ * Decrement the weight counter associated with the entity, and, if the
+ * counter reaches 0, remove the counter from the tree.
+ * See the comments to the function bfq_weights_tree_add() for considerations
+ * about overhead.
+ */
+static void bfq_weights_tree_remove(struct bfq_data *bfqd,
+				    struct bfq_entity *entity,
+				    struct rb_root *root)
+{
+	if (!entity->weight_counter)
+		return;
+
+	entity->weight_counter->num_active--;
+	if (entity->weight_counter->num_active > 0)
+		goto reset_entity_pointer;
+
+	rb_erase(&entity->weight_counter->weights_node, root);
+	kfree(entity->weight_counter);
+
+reset_entity_pointer:
+	entity->weight_counter = NULL;
+}
+
+/*
  * Return expired entry, or NULL to just start from scratch in rbtree.
  */
 static struct request *bfq_check_fifo(struct bfq_queue *bfqq,
@@ -5293,13 +5556,17 @@ static void bfq_arm_slice_timer(struct bfq_data *bfqd)
 	 */
 	sl = bfqd->bfq_slice_idle;
 	/*
-	 * Unless the queue is being weight-raised, grant only minimum
-	 * idle time if the queue is seeky. A long idling is preserved
-	 * for a weight-raised queue, because it is needed for
-	 * guaranteeing to the queue its reserved share of the
-	 * throughput.
-	 */
-	if (BFQQ_SEEKY(bfqq) && bfqq->wr_coeff == 1)
+	 * Unless the queue is being weight-raised or the scenario is
+	 * asymmetric, grant only minimum idle time if the queue
+	 * is seeky. A long idling is preserved for a weight-raised
+	 * queue, or, more in general, in an asymmetric scenario,
+	 * because a long idling is needed for guaranteeing to a queue
+	 * its reserved share of the throughput (in particular, it is
+	 * needed if the queue has a higher weight than some other
+	 * queue).
+	 */
+	if (BFQQ_SEEKY(bfqq) && bfqq->wr_coeff == 1 &&
+	    bfq_symmetric_scenario(bfqd))
 		sl = min_t(u64, sl, BFQ_MIN_TT);
 
 	bfqd->last_idling_start = ktime_get();
@@ -7197,6 +7464,9 @@ static void bfq_completed_request(struct bfq_queue *bfqq, struct bfq_data *bfqd)
 		 * mechanism).
 		 */
 		bfqq->budget_timeout = jiffies;
+
+		bfq_weights_tree_remove(bfqd, &bfqq->entity,
+					&bfqd->queue_weights_tree);
 	}
 
 	now_ns = ktime_get_ns();
@@ -7627,6 +7897,9 @@ static int bfq_init_queue(struct request_queue *q, struct elevator_type *e)
 		     HRTIMER_MODE_REL);
 	bfqd->idle_slice_timer.function = bfq_idle_slice_timer;
 
+	bfqd->queue_weights_tree = RB_ROOT;
+	bfqd->group_weights_tree = RB_ROOT;
+
 	INIT_LIST_HEAD(&bfqd->active_list);
 	INIT_LIST_HEAD(&bfqd->idle_list);
 
-- 
2.10.0

[toc] | [prev] | [next] | [standalone]

#1621291 — [PATCH V3 03/16] block, bfq: improve throughput boosting

The feedback-loop algorithm used by BFQ to compute queue (process)
budgets is basically a set of three update rules, one for each of the
main reasons why a queue may be expired. If many processes suddenly
switch from sporadic I/O to greedy and sequential I/O, then these
rules are quite slow to assign large budgets to these processes, and
hence to achieve a high throughput. On the opposite side, BFQ assigns
the maximum possible budget B_max to a just-created queue. This allows
a high throughput to be achieved immediately if the associated process
is I/O-bound and performs sequential I/O from the beginning. But it
also increases the worst-case latency experienced by the first
requests issued by the process, because the larger the budget of a
queue waiting for service is, the later the queue will be served by
B-WF2Q+ (Subsec 3.3 in [1]). This is detrimental for an interactive or
soft real-time application.

To tackle these throughput and latency problems, on one hand this
patch changes the initial budget value to B_max/2. On the other hand,
it re-tunes the three rules, adopting a more aggressive,
multiplicative increase/linear decrease scheme. This scheme trades
latency for throughput more than before, and tends to assign large
budgets quickly to processes that are or become I/O-bound. For two of
the expiration reasons, the new version of the rules also contains
some more little improvements, briefly described below.

*No more backlog.* In this case, the budget was larger than the number
of sectors actually read/written by the process before it stopped
doing I/O. Hence, to reduce latency for the possible future I/O
requests of the process, the old rule simply set the next budget to
the number of sectors actually consumed by the process. However, if
there are still outstanding requests, then the process may have not
yet issued its next request just because it is still waiting for the
completion of some of the still outstanding ones. If this sub-case
holds true, then the new rule, instead of decreasing the budget,
doubles it, proactively, in the hope that: 1) a larger budget will fit
the actual needs of the process, and 2) the process is sequential and
hence a higher throughput will be achieved by serving the process
longer after granting it access to the device.

*Budget timeout*. The original rule set the new budget to the maximum
value B_max, to maximize throughput and let all processes experiencing
budget timeouts receive the same share of the device time. In our
experiments we verified that this sudden jump to B_max did not provide
sensible benefits; rather it increased the latency of processes
performing sporadic and short I/O. The new rule only doubles the
budget.

[1] P. Valente and M. Andreolini, "Improving Application
    Responsiveness with the BFQ Disk I/O Scheduler", Proceedings of
    the 5th Annual International Systems and Storage Conference
    (SYSTOR '12), June 2012.
    Slightly extended version:
    http://algogroup.unimore.it/people/paolo/disk_sched/bfq-v1-suite-
							results.pdf

Signed-off-by: Paolo Valente <paolo.valente@linaro.org>
Signed-off-by: Arianna Avanzini <avanzini.arianna@gmail.com>
---
 block/bfq-iosched.c | 87 +++++++++++++++++++++++++----------------------------
 1 file changed, 41 insertions(+), 46 deletions(-)

diff --git a/block/bfq-iosched.c b/block/bfq-iosched.c
index 800048fa..553aee1 100644
--- a/block/bfq-iosched.c
+++ b/block/bfq-iosched.c
@@ -752,9 +752,6 @@ static struct kmem_cache *bfq_pool;
 #define BFQQ_CLOSE_THR		(sector_t)(8 * 1024)
 #define BFQQ_SEEKY(bfqq)	(hweight32(bfqq->seek_history) > 32/8)
 
-/* Budget feedback step. */
-#define BFQ_BUDGET_STEP         128
-
 /* Min samples used for peak rate estimation (for autotuning). */
 #define BFQ_PEAK_RATE_SAMPLES	32
 
@@ -4074,40 +4071,6 @@ static struct bfq_queue *bfq_set_in_service_queue(struct bfq_data *bfqd)
 	return bfqq;
 }
 
-/*
- * bfq_default_budget - return the default budget for @bfqq on @bfqd.
- * @bfqd: the device descriptor.
- * @bfqq: the queue to consider.
- *
- * We use 3/4 of the @bfqd maximum budget as the default value
- * for the max_budget field of the queues.  This lets the feedback
- * mechanism to start from some middle ground, then the behavior
- * of the process will drive the heuristics towards high values, if
- * it behaves as a greedy sequential reader, or towards small values
- * if it shows a more intermittent behavior.
- */
-static unsigned long bfq_default_budget(struct bfq_data *bfqd,
-					struct bfq_queue *bfqq)
-{
-	unsigned long budget;
-
-	/*
-	 * When we need an estimate of the peak rate we need to avoid
-	 * to give budgets that are too short due to previous
-	 * measurements.  So, in the first 10 assignments use a
-	 * ``safe'' budget value. For such first assignment the value
-	 * of bfqd->budgets_assigned happens to be lower than 194.
-	 * See __bfq_set_in_service_queue for the formula by which
-	 * this field is computed.
-	 */
-	if (bfqd->budgets_assigned < 194 && bfqd->bfq_user_max_budget == 0)
-		budget = bfq_default_max_budget;
-	else
-		budget = bfqd->bfq_max_budget;
-
-	return budget - budget / 4;
-}
-
 static void bfq_arm_slice_timer(struct bfq_data *bfqd)
 {
 	struct bfq_queue *bfqq = bfqd->in_service_queue;
@@ -4232,13 +4195,47 @@ static void __bfq_bfqq_recalc_budget(struct bfq_data *bfqd,
 		 * for throughput.
 		 */
 		case BFQQE_TOO_IDLE:
-			if (budget > min_budget + BFQ_BUDGET_STEP)
-				budget -= BFQ_BUDGET_STEP;
-			else
-				budget = min_budget;
+			/*
+			 * This is the only case where we may reduce
+			 * the budget: if there is no request of the
+			 * process still waiting for completion, then
+			 * we assume (tentatively) that the timer has
+			 * expired because the batch of requests of
+			 * the process could have been served with a
+			 * smaller budget.  Hence, betting that
+			 * process will behave in the same way when it
+			 * becomes backlogged again, we reduce its
+			 * next budget.  As long as we guess right,
+			 * this budget cut reduces the latency
+			 * experienced by the process.
+			 *
+			 * However, if there are still outstanding
+			 * requests, then the process may have not yet
+			 * issued its next request just because it is
+			 * still waiting for the completion of some of
+			 * the still outstanding ones.  So in this
+			 * subcase we do not reduce its budget, on the
+			 * contrary we increase it to possibly boost
+			 * the throughput, as discussed in the
+			 * comments to the BUDGET_TIMEOUT case.
+			 */
+			if (bfqq->dispatched > 0) /* still outstanding reqs */
+				budget = min(budget * 2, bfqd->bfq_max_budget);
+			else {
+				if (budget > 5 * min_budget)
+					budget -= 4 * min_budget;
+				else
+					budget = min_budget;
+			}
 			break;
 		case BFQQE_BUDGET_TIMEOUT:
-			budget = bfq_default_budget(bfqd, bfqq);
+			/*
+			 * We double the budget here because it gives
+			 * the chance to boost the throughput if this
+			 * is not a seeky process (and has bumped into
+			 * this timeout because of, e.g., ZBR).
+			 */
+			budget = min(budget * 2, bfqd->bfq_max_budget);
 			break;
 		case BFQQE_BUDGET_EXHAUSTED:
 			/*
@@ -4250,8 +4247,7 @@ static void __bfq_bfqq_recalc_budget(struct bfq_data *bfqd,
 			 * definitely increase the budget of this good
 			 * candidate to boost the disk throughput.
 			 */
-			budget = min(budget + 8 * BFQ_BUDGET_STEP,
-				     bfqd->bfq_max_budget);
+			budget = min(budget * 4, bfqd->bfq_max_budget);
 			break;
 		case BFQQE_NO_MORE_REQUESTS:
 			/*
@@ -5025,9 +5021,8 @@ static void bfq_init_bfqq(struct bfq_data *bfqd, struct bfq_queue *bfqq,
 	bfqq->pid = pid;
 
 	/* Tentative initial value to trade off between thr and lat */
-	bfqq->max_budget = bfq_default_budget(bfqd, bfqq);
+	bfqq->max_budget = (2 * bfq_max_budget(bfqd)) / 3;
 	bfqq->budget_timeout = bfq_smallest_from_now();
-	bfqq->pid = pid;
 
 	/* first request is almost certainly seeky */
 	bfqq->seek_history = 1;
-- 
2.10.0

[toc] | [prev] | [next] | [standalone]

#1621292 — [PATCH V3 09/16] block, bfq: reduce latency during request-pool saturation

This patch introduces an heuristic that reduces latency when the
I/O-request pool is saturated. This goal is achieved by disabling
device idling, for non-weight-raised queues, when there are weight-
raised queues with pending or in-flight requests. In fact, as
explained in more detail in the comment on the function
bfq_bfqq_may_idle(), this reduces the rate at which processes
associated with non-weight-raised queues grab requests from the pool,
thereby increasing the probability that processes associated with
weight-raised queues get a request immediately (or at least soon) when
they need one. Along the same line, if there are weight-raised queues,
then this patch halves the service rate of async (write) requests for
non-weight-raised queues.

Signed-off-by: Paolo Valente <paolo.valente@linaro.org>
Signed-off-by: Arianna Avanzini <avanzini.arianna@gmail.com>
---
 block/bfq-iosched.c | 66 ++++++++++++++++++++++++++++++++++++++++++++++++++---
 1 file changed, 63 insertions(+), 3 deletions(-)

diff --git a/block/bfq-iosched.c b/block/bfq-iosched.c
index 574a5f6..deb1f21c 100644
--- a/block/bfq-iosched.c
+++ b/block/bfq-iosched.c
@@ -420,6 +420,8 @@ struct bfq_data {
 	 * queue in service, even if it is idling).
 	 */
 	int busy_queues;
+	/* number of weight-raised busy @bfq_queues */
+	int wr_busy_queues;
 	/* number of queued requests */
 	int queued;
 	/* number of requests dispatched and waiting for completion */
@@ -2490,6 +2492,9 @@ static void bfq_del_bfqq_busy(struct bfq_data *bfqd, struct bfq_queue *bfqq,
 
 	bfqd->busy_queues--;
 
+	if (bfqq->wr_coeff > 1)
+		bfqd->wr_busy_queues--;
+
 	bfqg_stats_update_dequeue(bfqq_group(bfqq));
 
 	bfq_deactivate_bfqq(bfqd, bfqq, true, expiration);
@@ -2506,6 +2511,9 @@ static void bfq_add_bfqq_busy(struct bfq_data *bfqd, struct bfq_queue *bfqq)
 
 	bfq_mark_bfqq_busy(bfqq);
 	bfqd->busy_queues++;
+
+	if (bfqq->wr_coeff > 1)
+		bfqd->wr_busy_queues++;
 }
 
 #ifdef CONFIG_BFQ_GROUP_IOSCHED
@@ -3779,7 +3787,16 @@ static unsigned long bfq_serv_to_charge(struct request *rq,
 	if (bfq_bfqq_sync(bfqq) || bfqq->wr_coeff > 1)
 		return blk_rq_sectors(rq);
 
-	return blk_rq_sectors(rq) * bfq_async_charge_factor;
+	/*
+	 * If there are no weight-raised queues, then amplify service
+	 * by just the async charge factor; otherwise amplify service
+	 * by twice the async charge factor, to further reduce latency
+	 * for weight-raised queues.
+	 */
+	if (bfqq->bfqd->wr_busy_queues == 0)
+		return blk_rq_sectors(rq) * bfq_async_charge_factor;
+
+	return blk_rq_sectors(rq) * 2 * bfq_async_charge_factor;
 }
 
 /**
@@ -4234,6 +4251,7 @@ static void bfq_add_request(struct request *rq)
 			bfqq->wr_coeff = bfqd->bfq_wr_coeff;
 			bfqq->wr_cur_max_time = bfq_wr_duration(bfqd);
 
+			bfqd->wr_busy_queues++;
 			bfqq->entity.prio_changed = 1;
 		}
 		if (prev != bfqq->next_rq)
@@ -4474,6 +4492,8 @@ static void bfq_requests_merged(struct request_queue *q, struct request *rq,
 /* Must be called with bfqq != NULL */
 static void bfq_bfqq_end_wr(struct bfq_queue *bfqq)
 {
+	if (bfq_bfqq_busy(bfqq))
+		bfqq->bfqd->wr_busy_queues--;
 	bfqq->wr_coeff = 1;
 	bfqq->wr_cur_max_time = 0;
 	bfqq->last_wr_start_finish = jiffies;
@@ -5497,7 +5517,8 @@ static bool bfq_may_expire_for_budg_timeout(struct bfq_queue *bfqq)
 static bool bfq_bfqq_may_idle(struct bfq_queue *bfqq)
 {
 	struct bfq_data *bfqd = bfqq->bfqd;
-	bool idling_boosts_thr, asymmetric_scenario;
+	bool idling_boosts_thr, idling_boosts_thr_without_issues,
+		asymmetric_scenario;
 
 	if (bfqd->strict_guarantees)
 		return true;
@@ -5520,6 +5541,44 @@ static bool bfq_bfqq_may_idle(struct bfq_queue *bfqq)
 	idling_boosts_thr = !bfqd->hw_tag || bfq_bfqq_IO_bound(bfqq);
 
 	/*
+	 * The value of the next variable,
+	 * idling_boosts_thr_without_issues, is equal to that of
+	 * idling_boosts_thr, unless a special case holds. In this
+	 * special case, described below, idling may cause problems to
+	 * weight-raised queues.
+	 *
+	 * When the request pool is saturated (e.g., in the presence
+	 * of write hogs), if the processes associated with
+	 * non-weight-raised queues ask for requests at a lower rate,
+	 * then processes associated with weight-raised queues have a
+	 * higher probability to get a request from the pool
+	 * immediately (or at least soon) when they need one. Thus
+	 * they have a higher probability to actually get a fraction
+	 * of the device throughput proportional to their high
+	 * weight. This is especially true with NCQ-capable drives,
+	 * which enqueue several requests in advance, and further
+	 * reorder internally-queued requests.
+	 *
+	 * For this reason, we force to false the value of
+	 * idling_boosts_thr_without_issues if there are weight-raised
+	 * busy queues. In this case, and if bfqq is not weight-raised,
+	 * this guarantees that the device is not idled for bfqq (if,
+	 * instead, bfqq is weight-raised, then idling will be
+	 * guaranteed by another variable, see below). Combined with
+	 * the timestamping rules of BFQ (see [1] for details), this
+	 * behavior causes bfqq, and hence any sync non-weight-raised
+	 * queue, to get a lower number of requests served, and thus
+	 * to ask for a lower number of requests from the request
+	 * pool, before the busy weight-raised queues get served
+	 * again. This often mitigates starvation problems in the
+	 * presence of heavy write workloads and NCQ, thereby
+	 * guaranteeing a higher application and system responsiveness
+	 * in these hostile scenarios.
+	 */
+	idling_boosts_thr_without_issues = idling_boosts_thr &&
+		bfqd->wr_busy_queues == 0;
+
+	/*
 	 * There is then a case where idling must be performed not for
 	 * throughput concerns, but to preserve service guarantees. To
 	 * introduce it, we can note that allowing the drive to
@@ -5593,7 +5652,7 @@ static bool bfq_bfqq_may_idle(struct bfq_queue *bfqq)
 	 *    is necessary to preserve service guarantees.
 	 */
 	return bfq_bfqq_sync(bfqq) &&
-		(idling_boosts_thr || asymmetric_scenario);
+		(idling_boosts_thr_without_issues || asymmetric_scenario);
 }
 
 /*
@@ -6801,6 +6860,7 @@ static int bfq_init_queue(struct request_queue *q, struct elevator_type *e)
 					      * high-definition compressed
 					      * video.
 					      */
+	bfqd->wr_busy_queues = 0;
 
 	/*
 	 * Begin by assuming, optimistically, that the device is a
-- 
2.10.0

[toc] | [prev] | [next] | [standalone]

#1621372

On Tue, 2017-04-11 at 15:42 +0200, Paolo Valente wrote:
> new patch series, addressing (both) issues raised by Bart [1].

Hello Paolo,

Is there a git tree available somewhere with these patches and without
the single queue BFQ scheduler?

Thanks,

Bart.

[toc] | [prev] | [next] | [standalone]

#1621499

> Il giorno 11 apr 2017, alle ore 16:37, Bart Van Assche <bart.vanassche@sandisk.com> ha scritto:
> 
> On Tue, 2017-04-11 at 15:42 +0200, Paolo Valente wrote:
>> new patch series, addressing (both) issues raised by Bart [1].
> 
> Hello Paolo,
> 
> Is there a git tree available somewhere with these patches and without
> the single queue BFQ scheduler?
> 

Just pushed:
https://github.com/Algodev-github/bfq-mq/tree/add-bfq-mq-logical

Thanks,
Paolo

> Thanks,
> 
> Bart.

[toc] | [prev] | [next] | [standalone]

#1621538

On Tue, 2017-04-11 at 19:37 +0200, Paolo Valente wrote:
> Just pushed:
> https://github.com/Algodev-github/bfq-mq/tree/add-bfq-mq-logical

Thanks!

But are you aware that the code on that branch doesn't build?

$ make all
[ ... ]
ERROR: "bfq_mark_bfqq_busy" [block/bfq-wf2q.ko] undefined!
ERROR: "bfqg_stats_update_dequeue" [block/bfq-wf2q.ko] undefined!
[ ... ]

$ PAGER= git grep bfq_mark_bfqq_busy
block/bfq-wf2q.c:       bfq_mark_bfqq_busy(bfqq);

Bart.

[toc] | [prev] | [next] | [standalone]

#1621829

> Il giorno 11 apr 2017, alle ore 20:31, Bart Van Assche <bart.vanassche@sandisk.com> ha scritto:
> 
> On Tue, 2017-04-11 at 19:37 +0200, Paolo Valente wrote:
>> Just pushed:
>> https://github.com/Algodev-github/bfq-mq/tree/add-bfq-mq-logical
> 
> Thanks!
> 
> But are you aware that the code on that branch doesn't build?
> 
> $ make all
> [ ... ]
> ERROR: "bfq_mark_bfqq_busy" [block/bfq-wf2q.ko] undefined!
> ERROR: "bfqg_stats_update_dequeue" [block/bfq-wf2q.ko] undefined!
> [ ... ]
> 
> $ PAGER= git grep bfq_mark_bfqq_busy
> block/bfq-wf2q.c:       bfq_mark_bfqq_busy(bfqq);
> 

That's exactly the complain of the kbuild test robot.  As I wrote,
build completes with no problem in my test system (Ubuntu 16.04, gcc
5.4.0), even with the exact offending tree and .config that the robot
reports.

I didn't understand what is going on.  In your case, as well as for
the test robot, the compilation of the file block/bfq-wf2q.c as a
module component fails, because that file does not contain the
definition of the reported functions.  But that definition is
(uniquely) in the file block/bfq-iosched.c, which is to be compiled
with the former file, according to the following rule in
block/Makefile:
obj-$(CONFIG_IOSCHED_BFQ)       += bfq-iosched.o bfq-wf2q.o bfq-cgroup.o

I have tried all combinations of configurations for bfq (builti-in or
module, with or without cgrousp support), always successfully.  If it
makes any sense to share this information, these are the exact
commands I used to test al combinations (in addition to make full
builds in some cases, and try make all as in your case):

make O=builddir M=block

and

make O=builddir M=block modules

Where is my mistake?

Thanks,
Paolo

> Bart.

[toc] | [prev] | [next] | [standalone]

#1622249

On Wed, 2017-04-12 at 08:01 +0200, Paolo Valente wrote:
> Where is my mistake?

I think in the Makefile. How about the patch below? Please note that I'm no
Kbuild expert.

diff --git a/block/Makefile b/block/Makefile
index 546066ee7fa6..b3711af6b637 100644
--- a/block/Makefile
+++ b/block/Makefile
@@ -20,7 +20,8 @@ obj-$(CONFIG_IOSCHED_NOOP)    += noop-iosched.o
 obj-$(CONFIG_IOSCHED_DEADLINE) += deadline-iosched.o
 obj-$(CONFIG_IOSCHED_CFQ)      += cfq-iosched.o
 obj-$(CONFIG_MQ_IOSCHED_DEADLINE)      += mq-deadline.o
-obj-$(CONFIG_IOSCHED_BFQ)      += bfq-iosched.o bfq-wf2q.o bfq-cgroup.o
+bfq-y                          := bfq-iosched.o bfq-wf2q.o bfq-cgroup.o
+obj-$(CONFIG_IOSCHED_BFQ)      += bfq.o
   obj-$(CONFIG_BLOCK_COMPAT)     += compat_ioctl.o
 obj-$(CONFIG_BLK_CMDLINE_PARSER)       += cmdline-parser.o

[toc] | [prev] | [next] | [standalone]

#1622273

> Il giorno 12 apr 2017, alle ore 17:30, Bart Van Assche <Bart.VanAssche@sandisk.com> ha scritto:
> 
> On Wed, 2017-04-12 at 08:01 +0200, Paolo Valente wrote:
>> Where is my mistake?
> 
> I think in the Makefile. How about the patch below? Please note that I'm no
> Kbuild expert.
> 

Thank you very much for finding and fixing the bug.  I was working
exactly on that, and had got to the same solution (which I guess is
the only correct one).  I'll apply these changes and resubmit.

Thanks,
Paolo

> diff --git a/block/Makefile b/block/Makefile
> index 546066ee7fa6..b3711af6b637 100644
> --- a/block/Makefile
> +++ b/block/Makefile
> @@ -20,7 +20,8 @@ obj-$(CONFIG_IOSCHED_NOOP)    += noop-iosched.o
>  obj-$(CONFIG_IOSCHED_DEADLINE) += deadline-iosched.o
>  obj-$(CONFIG_IOSCHED_CFQ)      += cfq-iosched.o
>  obj-$(CONFIG_MQ_IOSCHED_DEADLINE)      += mq-deadline.o
> -obj-$(CONFIG_IOSCHED_BFQ)      += bfq-iosched.o bfq-wf2q.o bfq-cgroup.o
> +bfq-y                          := bfq-iosched.o bfq-wf2q.o bfq-cgroup.o
> +obj-$(CONFIG_IOSCHED_BFQ)      += bfq.o
>    obj-$(CONFIG_BLOCK_COMPAT)     += compat_ioctl.o
>  obj-$(CONFIG_BLK_CMDLINE_PARSER)       += cmdline-parser.o
> 

[toc] | [prev] | [next] | [standalone]

#1621646 — Re: [PATCH V3 02/16] block, bfq: add full hierarchical scheduling and cgroups support

Hello,

On Tue, Apr 11, 2017 at 03:43:01PM +0200, Paolo Valente wrote:
> From: Arianna Avanzini <avanzini.arianna@gmail.com>
> 
> Add complete support for full hierarchical scheduling, with a cgroups
> interface. Full hierarchical scheduling is implemented through the
> 'entity' abstraction: both bfq_queues, i.e., the internal BFQ queues
> associated with processes, and groups are represented in general by
> entities. Given the bfq_queues associated with the processes belonging
> to a given group, the entities representing these queues are sons of
> the entity representing the group. At higher levels, if a group, say
> G, contains other groups, then the entity representing G is the parent
> entity of the entities representing the groups in G.
> 
> Hierarchical scheduling is performed as follows: if the timestamps of
> a leaf entity (i.e., of a bfq_queue) change, and such a change lets
> the entity become the next-to-serve entity for its parent entity, then
> the timestamps of the parent entity are recomputed as a function of
> the budget of its new next-to-serve leaf entity. If the parent entity
> belongs, in its turn, to a group, and its new timestamps let it become
> the next-to-serve for its parent entity, then the timestamps of the
> latter parent entity are recomputed as well, and so on. When a new
> bfq_queue must be set in service, the reverse path is followed: the
> next-to-serve highest-level entity is chosen, then its next-to-serve
> child entity, and so on, until the next-to-serve leaf entity is
> reached, and the bfq_queue that this entity represents is set in
> service.
> 
> Writeback is accounted for on a per-group basis, i.e., for each group,
> the async I/O requests of the processes of the group are enqueued in a
> distinct bfq_queue, and the entity associated with this queue is a
> child of the entity associated with the group.
> 
> Weights can be assigned explicitly to groups and processes through the
> cgroups interface, differently from what happens, for single
> processes, if the cgroups interface is not used (as explained in the
> description of the previous patch). In particular, since each node has
> a full scheduler, each group can be assigned its own weight.

Can we please hold off on cgroup support for now?  I've been trying to
chase down cpu scheduler latency issues lately and have some doubts
about implementing cgroup support by simply nesting the timelines like
this.

Thanks

-- 
tejun

[toc] | [prev] | [next] | [standalone]

#1621798 — Re: [PATCH V3 02/16] block, bfq: add full hierarchical scheduling and cgroups support

> Il giorno 11 apr 2017, alle ore 23:47, Tejun Heo <tj@kernel.org> ha scritto:
> 
> Hello,
> 
> On Tue, Apr 11, 2017 at 03:43:01PM +0200, Paolo Valente wrote:
>> From: Arianna Avanzini <avanzini.arianna@gmail.com>
>> 
>> Add complete support for full hierarchical scheduling, with a cgroups
>> interface. Full hierarchical scheduling is implemented through the
>> 'entity' abstraction: both bfq_queues, i.e., the internal BFQ queues
>> associated with processes, and groups are represented in general by
>> entities. Given the bfq_queues associated with the processes belonging
>> to a given group, the entities representing these queues are sons of
>> the entity representing the group. At higher levels, if a group, say
>> G, contains other groups, then the entity representing G is the parent
>> entity of the entities representing the groups in G.
>> 
>> Hierarchical scheduling is performed as follows: if the timestamps of
>> a leaf entity (i.e., of a bfq_queue) change, and such a change lets
>> the entity become the next-to-serve entity for its parent entity, then
>> the timestamps of the parent entity are recomputed as a function of
>> the budget of its new next-to-serve leaf entity. If the parent entity
>> belongs, in its turn, to a group, and its new timestamps let it become
>> the next-to-serve for its parent entity, then the timestamps of the
>> latter parent entity are recomputed as well, and so on. When a new
>> bfq_queue must be set in service, the reverse path is followed: the
>> next-to-serve highest-level entity is chosen, then its next-to-serve
>> child entity, and so on, until the next-to-serve leaf entity is
>> reached, and the bfq_queue that this entity represents is set in
>> service.
>> 
>> Writeback is accounted for on a per-group basis, i.e., for each group,
>> the async I/O requests of the processes of the group are enqueued in a
>> distinct bfq_queue, and the entity associated with this queue is a
>> child of the entity associated with the group.
>> 
>> Weights can be assigned explicitly to groups and processes through the
>> cgroups interface, differently from what happens, for single
>> processes, if the cgroups interface is not used (as explained in the
>> description of the previous patch). In particular, since each node has
>> a full scheduler, each group can be assigned its own weight.
> 
> Can we please hold off on cgroup support for now?  I've been trying to
> chase down cpu scheduler latency issues lately and have some doubts
> about implementing cgroup support by simply nesting the timelines like
> this.
> 

Hi Tejun,
could you elaborate a bit more on this?  I mean, cgroups support has
been in BFQ (and CFQ) for almost ten years, perfectly working as far
as I know.  Of course it is perfectly working in terms of I/O and not
of CPU bandwidth distribution; and, for the moment, it is effective
only for devices below 30-50KIOPS.  What's the point in throwing
(momentarily?) away such a fundamental feature?  What am I missing?

Thanks,
Paolo


> Thanks
> 
> -- 
> tejun

[toc] | [prev] | [next] | [standalone]

#1625083 — Re: [PATCH V3 02/16] block, bfq: add full hierarchical scheduling and cgroups support

Hello, Paolo.

On Wed, Apr 12, 2017 at 07:22:03AM +0200, Paolo Valente wrote:
> could you elaborate a bit more on this?  I mean, cgroups support has
> been in BFQ (and CFQ) for almost ten years, perfectly working as far
> as I know.  Of course it is perfectly working in terms of I/O and not
> of CPU bandwidth distribution; and, for the moment, it is effective
> only for devices below 30-50KIOPS.  What's the point in throwing
> (momentarily?) away such a fundamental feature?  What am I missing?

I've been trying to track down latency issues with the CPU controller
which basically takes the same approach and I'm not sure nesting
scheduler timelines is a good approach.  It intuitively feels elegant
but seems to have some fundamental issues.  IIUC, bfq isn't quite the
same in that it doesn't need load balancer across multiple queues and
it could be that bfq is close enough to the basic model that the
nested behavior maps to the correct scheduling behavior.

However, for example, in the CPU controller, the nested timelines
break sleeper boost.  The boost is implemented by considering the
thread to have woken up upto some duration prior to the current time;
however, it only affects the timeline inside the cgroup and there's no
good way to propagate it upwards.  The final result is two threads in
a cgroup with the double weight can behave significantly worse in
terms of latency compared to two threads with the weight of 1 in the
root.

Given that the nested scheduling ends up pretty expensive, I'm not
sure how good a model this nesting approach is.  Especially if there
can be multiple queues, the weight distribution across cgroup
instances across multiple queues has to be coordinated globally
anyway, so the weight / cost adjustment part can't happen
automatically anyway as in single queue case.  If we're going there,
we might as well implement cgroup support by actively modulating the
combined weights, which will make individual scheduling operations
cheaper and it easier to think about and guarantee latency behaviors.

If you think that bfq will stay single queue and won't need timeline
modifying heuristics (for responsiveness or whatever), the current
approach could be fine, but I'm a bit awry about committing to the
current approach if we're gonna encounter the same problems.

Thanks.

-- 
tejun

[toc] | [prev] | [next] | [standalone]

#1625836 — Re: [PATCH V3 02/16] block, bfq: add full hierarchical scheduling and cgroups support

> Il giorno 18 apr 2017, alle ore 09:04, Tejun Heo <tj@kernel.org> ha scritto:
> 
> Hello, Paolo.
> 
> On Wed, Apr 12, 2017 at 07:22:03AM +0200, Paolo Valente wrote:
>> could you elaborate a bit more on this?  I mean, cgroups support has
>> been in BFQ (and CFQ) for almost ten years, perfectly working as far
>> as I know.  Of course it is perfectly working in terms of I/O and not
>> of CPU bandwidth distribution; and, for the moment, it is effective
>> only for devices below 30-50KIOPS.  What's the point in throwing
>> (momentarily?) away such a fundamental feature?  What am I missing?
> 
> I've been trying to track down latency issues with the CPU controller
> which basically takes the same approach and I'm not sure nesting
> scheduler timelines is a good approach.  It intuitively feels elegant
> but seems to have some fundamental issues.  IIUC, bfq isn't quite the
> same in that it doesn't need load balancer across multiple queues and
> it could be that bfq is close enough to the basic model that the
> nested behavior maps to the correct scheduling behavior.
> 
> However, for example, in the CPU controller, the nested timelines
> break sleeper boost.  The boost is implemented by considering the
> thread to have woken up upto some duration prior to the current time;
> however, it only affects the timeline inside the cgroup and there's no
> good way to propagate it upwards.  The final result is two threads in
> a cgroup with the double weight can behave significantly worse in
> terms of latency compared to two threads with the weight of 1 in the
> root.
> 

Hi Tejun,
I don't know in detail the specific multiple-queue issues you report,
but bfq implements the upward propagation you mention: if a process in
a group is to be privileged, i.e., if the process has basically to be
provided with a higher weight (in addition to other important forms of
help), then this weight boost is propagated upward through the path
from the process to the root node in the group hierarchy.

> Given that the nested scheduling ends up pretty expensive, I'm not
> sure how good a model this nesting approach is.  Especially if there
> can be multiple queues, the weight distribution across cgroup
> instances across multiple queues has to be coordinated globally
> anyway,

To get perfect global service guarantees, yes.  But you can settle
with tradeoffs that, according to my experience with storage and
packet I/O, are so good to be probably indistinguishable from an
ideal, but too costly solution.  I mean, with a well-done approximated
scheduling solution, the deviation with respect to an ideal service
can be in the same order of the noise caused by unavoidable latencies
of other sw and hw components than the scheduler.

> so the weight / cost adjustment part can't happen
> automatically anyway as in single queue case.  If we're going there,
> we might as well implement cgroup support by actively modulating the
> combined weights, which will make individual scheduling operations
> cheaper and it easier to think about and guarantee latency behaviors.
> 

Yes.  Anyway, I didn't quite understand what is or could be the
alternative, w.r.t. hierarchical scheduling, for guaranteeing
bandwidth distribution of shared resources in a complex setting.  If
you think I could be of any help on this, just put me somehow in the
loop.

> If you think that bfq will stay single queue and won't need timeline
> modifying heuristics (for responsiveness or whatever), the current
> approach could be fine, but I'm a bit awry about committing to the
> current approach if we're gonna encounter the same problems.
> 

As of now, bfq is targeted at not too fast devices (< 30-50KIOPS),
which happen to be single queue.  In particular, bfq is currently
agnostic w.r.t.  to the number of downstream queues.

Thanks,
Paolo

> Thanks.
> 
> -- 
> tejun

[toc] | [prev] | [next] | [standalone]

#1625867 — Re: [PATCH V3 02/16] block, bfq: add full hierarchical scheduling and cgroups support

> Il giorno 19 apr 2017, alle ore 07:33, Paolo Valente <paolo.valente@linaro.org> ha scritto:
> 
>> 
>> Il giorno 18 apr 2017, alle ore 09:04, Tejun Heo <tj@kernel.org> ha scritto:
>> 
>> Hello, Paolo.
>> 
>> On Wed, Apr 12, 2017 at 07:22:03AM +0200, Paolo Valente wrote:
>>> could you elaborate a bit more on this?  I mean, cgroups support has
>>> been in BFQ (and CFQ) for almost ten years, perfectly working as far
>>> as I know.  Of course it is perfectly working in terms of I/O and not
>>> of CPU bandwidth distribution; and, for the moment, it is effective
>>> only for devices below 30-50KIOPS.  What's the point in throwing
>>> (momentarily?) away such a fundamental feature?  What am I missing?
>> 
>> I've been trying to track down latency issues with the CPU controller
>> which basically takes the same approach and I'm not sure nesting
>> scheduler timelines is a good approach.  It intuitively feels elegant
>> but seems to have some fundamental issues.  IIUC, bfq isn't quite the
>> same in that it doesn't need load balancer across multiple queues and
>> it could be that bfq is close enough to the basic model that the
>> nested behavior maps to the correct scheduling behavior.
>> 
>> However, for example, in the CPU controller, the nested timelines
>> break sleeper boost.  The boost is implemented by considering the
>> thread to have woken up upto some duration prior to the current time;
>> however, it only affects the timeline inside the cgroup and there's no
>> good way to propagate it upwards.  The final result is two threads in
>> a cgroup with the double weight can behave significantly worse in
>> terms of latency compared to two threads with the weight of 1 in the
>> root.
>> 
> 
> Hi Tejun,
> I don't know in detail the specific multiple-queue issues you report,
> but bfq implements the upward propagation you mention: if a process in
> a group is to be privileged, i.e., if the process has basically to be
> provided with a higher weight (in addition to other important forms of
> help), then this weight boost is propagated upward through the path
> from the process to the root node in the group hierarchy.
> 

ERRATA CORRIGE: actually, this propagation is implemented in a simple
variant of bfq that I made for a virtualization company (to truly
guarantee a low latency to the processes in a guest OS, regardless of
the load in the host).  The base version of bfq in these patches
contains all the mechanisms needed to get this propagation, but
doesn't modify group weights autonomously.

Paolo

>> Given that the nested scheduling ends up pretty expensive, I'm not
>> sure how good a model this nesting approach is.  Especially if there
>> can be multiple queues, the weight distribution across cgroup
>> instances across multiple queues has to be coordinated globally
>> anyway,
> 
> To get perfect global service guarantees, yes.  But you can settle
> with tradeoffs that, according to my experience with storage and
> packet I/O, are so good to be probably indistinguishable from an
> ideal, but too costly solution.  I mean, with a well-done approximated
> scheduling solution, the deviation with respect to an ideal service
> can be in the same order of the noise caused by unavoidable latencies
> of other sw and hw components than the scheduler.
> 
>> so the weight / cost adjustment part can't happen
>> automatically anyway as in single queue case.  If we're going there,
>> we might as well implement cgroup support by actively modulating the
>> combined weights, which will make individual scheduling operations
>> cheaper and it easier to think about and guarantee latency behaviors.
>> 
> 
> Yes.  Anyway, I didn't quite understand what is or could be the
> alternative, w.r.t. hierarchical scheduling, for guaranteeing
> bandwidth distribution of shared resources in a complex setting.  If
> you think I could be of any help on this, just put me somehow in the
> loop.
> 
>> If you think that bfq will stay single queue and won't need timeline
>> modifying heuristics (for responsiveness or whatever), the current
>> approach could be fine, but I'm a bit awry about committing to the
>> current approach if we're gonna encounter the same problems.
>> 
> 
> As of now, bfq is targeted at not too fast devices (< 30-50KIOPS),
> which happen to be single queue.  In particular, bfq is currently
> agnostic w.r.t.  to the number of downstream queues.
> 
> Thanks,
> Paolo
> 
>> Thanks.
>> 
>> -- 
>> tejun

[toc] | [prev] | [next] | [standalone]

#1624198

On 11.04.2017, Paolo Valente wrote: 

> new patch series, addressing (both) issues raised by Bart [1].

I'm doing a lot of automatic video transcoding in order to get my
collection of homemade videos down to an acceptable size (mainly
landscapes and boats all over the Norwegian west coast, taken with an old
cam that only produces uncompressed files). This process
involves heavy permanent writing to disk, often over a period of 10
min and more. When this happens, the whole system is kind of
unresponsive. I'm running Fedora 25, but with a self-customised kernel
that is fully low-latency, and the machine is a quadcore Intel Xeon
which should have enough power (Intel(R) Xeon(R) CPU E3-1241 v3 @
3.50GHz).

Using plain blk-mq, the system is very sluggish when there is heavy
disk writing, and it can take up to several minutes (up to the point
where the disk writing actually finishes) to start programs like gimp
or Libreoffice. In fact, when I click on the "applications" button
within XFCE, it can take a long time before the window even opens.
I played with deadline-mq too, and the situation remains the same
unless I do some heavy tuning like this:

echo "mq-deadline" > /sys/block/nvme0n1/queue/scheduler
echo "1" > /sys/block/nvme0n1/queue/iosched/fifo_batch
echo "4" > /sys/block/nvme0n1/queue/iosched/writes_starved
echo "100" > /sys/block/nvme0n1/queue/iosched/read_expire
echo "2000" > /sys/block/nvme0n1/queue/iosched/write_expire

With deadline-mq tuned like this, overall responsiveness is a little bit
better, but not nearly as good as when using bfq. With plain bfq, no
tuning is needed. The system is no longer sluggish. Any program starts
within seconds, and all is very much responsive. Max throughput isn't
important to me, the nvme "harddisk" is fast enough that some MB/s
more or less do not really matter.

[root@chiara ~]# lspci -v | grep -i nvme
01:00.0 Non-Volatile memory controller: Samsung Electronics Co Ltd NVMe
SSD Controller SM951/PM951 (rev 01) (prog-if 02 [NVM Express])
	Kernel driver in use: nvme
	Kernel modules: nvme

As an end-user with no relevant programming skills to be able to
contribute, I would wish that developers would combine their forces and
help Paolo to get bfq into the kernel and to make bfq even better.

Thanks,
 Heinz
 

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web