Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > linux.kernel > #1508990 > unrolled thread
| Started by | Paolo Valente <paolo.valente@linaro.org> |
|---|---|
| First post | 2016-10-26 11:30 +0200 |
| Last post | 2016-10-26 14:50 +0200 |
| Articles | 14 — 5 participants |
Back to article view | Back to linux.kernel
[PATCH 00/14] introduce the BFQ-v0 I/O scheduler as an extra scheduler Paolo Valente <paolo.valente@linaro.org> - 2016-10-26 11:30 +0200
[PATCH 05/14] block, bfq: add more fairness with writes and slow processes Paolo Valente <paolo.valente@linaro.org> - 2016-10-26 11:30 +0200
[PATCH 04/14] block, bfq: modify the peak-rate estimator Paolo Valente <paolo.valente@linaro.org> - 2016-10-26 11:40 +0200
[PATCH 03/14] block, bfq: improve throughput boosting Paolo Valente <paolo.valente@linaro.org> - 2016-10-26 11:40 +0200
[PATCH 09/14] block, bfq: reduce latency during request-pool saturation Paolo Valente <paolo.valente@linaro.org> - 2016-10-26 11:40 +0200
[PATCH 07/14] block, bfq: reduce I/O latency for soft real-time applications Paolo Valente <paolo.valente@linaro.org> - 2016-10-26 11:40 +0200
Re: [PATCH 00/14] introduce the BFQ-v0 I/O scheduler as an extra scheduler Christoph Hellwig <hch@infradead.org> - 2016-10-26 12:30 +0200
Re: [PATCH 00/14] introduce the BFQ-v0 I/O scheduler as an extra scheduler Jan Kara <jack@suse.cz> - 2016-10-26 13:40 +0200
Re: [PATCH 00/14] introduce the BFQ-v0 I/O scheduler as an extra scheduler Arnd Bergmann <arnd@arndb.de> - 2016-10-26 17:20 +0200
Re: [PATCH 00/14] introduce the BFQ-v0 I/O scheduler as an extra scheduler Christoph Hellwig <hch@infradead.org> - 2016-10-26 17:40 +0200
Re: [PATCH 00/14] introduce the BFQ-v0 I/O scheduler as an extra scheduler Jens Axboe <axboe@kernel.dk> - 2016-10-26 17:40 +0200
Re: [PATCH 00/14] introduce the BFQ-v0 I/O scheduler as an extra scheduler Paolo Valente <paolo.valente@linaro.org> - 2016-10-26 18:10 +0200
Re: [PATCH 00/14] introduce the BFQ-v0 I/O scheduler as an extra scheduler Jens Axboe <axboe@kernel.dk> - 2016-10-26 18:20 +0200
Re: [PATCH 00/14] introduce the BFQ-v0 I/O scheduler as an extra scheduler Paolo Valente <paolo.valente@linaro.org> - 2016-10-26 14:50 +0200
| From | Paolo Valente <paolo.valente@linaro.org> |
|---|---|
| Date | 2016-10-26 11:30 +0200 |
| Subject | [PATCH 00/14] introduce the BFQ-v0 I/O scheduler as an extra scheduler |
| Message-ID | <swsH0-1Ia-9@gated-at.bofh.it> |
Hi,
this new patch series turns back to the initial approach, i.e., it
adds BFQ as an extra scheduler, instead of replacing CFQ with
BFQ. This patch series also contains all the improvements and bug
fixes recommended by Tejun [5], plus new features of BFQ-v8r5. Details
about old and new features in patch descriptions.
The first version of BFQ was submitted a few years ago [1]. It is
denoted as v0 in this patchset, to distinguish it from the version I
am submitting now, v8r5. In particular, the first two patches
introduce BFQ-v0, whereas the remaining patches turn progressively
BFQ-v0 into BFQ-v8r5.
Some patch generates WARNINGS with checkpatch.pl, but these WARNINGS
seem to be either unavoidable for the involved pieces of code (which
the patch just extends), or false positives.
For your convenience, a slightly updated and extended description of
BFQ follows.
On average CPUs, the current version of BFQ can handle devices
performing at most ~30K IOPS; at most ~50 KIOPS on faster CPUs. These
are about the same limits as CFQ. There may be room for noticeable
improvements regarding these limits, but, given the overall
limitations of blk itself, I thought it was not the case to further
delay this new submission.
Here are some nice features of BFQ-v8r5.
Low latency for interactive applications
Regardless of the actual background workload, BFQ guarantees that, for
interactive tasks, the storage device is virtually as responsive as if
it was idle. For example, even if one or more of the following
background workloads are being executed:
- one or more large files are being read, written or copied,
- a tree of source files is being compiled,
- one or more virtual machines are performing I/O,
- a software update is in progress,
- indexing daemons are scanning filesystems and updating their
databases,
starting an application or loading a file from within an application
takes about the same time as if the storage device was idle. As a
comparison, with CFQ, NOOP or DEADLINE, and in the same conditions,
applications experience high latencies, or even become unresponsive
until the background workload terminates (also on SSDs).
Low latency for soft real-time applications
Also soft real-time applications, such as audio and video
players/streamers, enjoy a low latency and a low drop rate, regardless
of the background I/O workload. As a consequence, these applications
do not suffer from almost any glitch due to the background workload.
Higher speed for code-development tasks
If some additional workload happens to be executed in parallel, then
BFQ executes the I/O-related components of typical code-development
tasks (compilation, checkout, merge, ...) much more quickly than CFQ,
NOOP or DEADLINE.
High throughput
On hard disks, BFQ achieves up to 30% higher throughput than CFQ, and
up to 150% higher throughput than DEADLINE and NOOP, with all the
sequential workloads considered in our tests. With random workloads,
and with all the workloads on flash-based devices, BFQ achieves,
instead, about the same throughput as the other schedulers.
Strong fairness, bandwidth and delay guarantees
BFQ distributes the device throughput, and not just the device time,
among I/O-bound applications in proportion their weights, with any
workload and regardless of the device parameters. From these bandwidth
guarantees, it is possible to compute tight per-I/O-request delay
guarantees by a simple formula. If not configured for strict service
guarantees, BFQ switches to time-based resource sharing (only) for
applications that would otherwise cause a throughput loss.
BFQ achieves the above service properties thanks to the combination of
its accurate scheduling engine (patches 1-2), and a set of simple
heuristics and improvements (patches 3-14). Details on how BFQ and
its components work are provided in the descriptions of the
patches. In addition, an organic description of the main BFQ algorithm
and of most of its features can be found in this paper [2].
What BFQ can do in practice is shown, e.g., in this 8-minute demo with
an SSD: [3]. I made this demo with an older version of BFQ (v7r6) and
under Linux 3.17.0, but, for the tests considered in the demo,
performance has remained about the same with more recent BFQ and
kernel versions. More details about this point can be found here [4],
together with graphs showing the performance of BFQ, as compared with
CFQ, DEADLINE and NOOP, and on: a fast and a slow hard disk, a RAID1,
an SSD, a microSDHC Card and an eMMC. As an example, our results on
the SSD are reported also in a table at the end of this email.
Finally, as for testing in everyday use, BFQ is the default I/O
scheduler in, e.g., Mageia, Manjaro, Sabayon, OpenMandriva and Arch
Linux ARM, plus several kernel forks for PCs and smartphones. In
addition, BFQ is optionally available in, e.g., Arch, PCLinuxOS and
Gentoo, and we record several downloads a day from people using other
distributions. The feedback received so far basically confirms the
expected latency drop and throughput boost.
Thanks,
Paolo
Results on a Plextor PX-256M5S SSD
The first two rows of the next table report the aggregate throughput
achieved by BFQ, CFQ, DEADLINE and NOOP, while ten parallel processes
read, either sequentially or randomly, a separate portion of the
memory blocks each. These processes read directly from the device, and
no process performs writes, to avoid writing large files repeatedly
and wearing out the device during the many tests done. As can be seen,
all schedulers achieve about the same throughput with sequential
readers, whereas, with random readers, the throughput slightly grows
as the complexity, and hence the execution time, of the schedulers
decreases. In fact, with random readers, the number of IOPS is
extremely higher, and all CPUs spend all the time either executing
instructions or waiting for I/O (the total idle percentage is
0). Therefore, the processing time of I/O requests influences the
maximum throughput achievable.
The remaining rows report the cold-cache start-up time experienced by
various applications while one of the above two workloads is being
executed in parallel. In particular, "Start-up time 10 seq/rand"
stands for "Start-up time of the application at hand while 10
sequential/random readers are running". A timeout fires, and the test
is aborted, if the application does not start within 60 seconds; so,
in the table, '>60' means that the application did not start before
the timeout fired.
With sequential readers, the performance gap between BFQ and the other
schedulers is remarkable. Background workloads are intentionally very
heavy, to show the performance of the schedulers in somewhat extreme
conditions. Differences are however still significant also with
lighter workloads, as shown, e.g., here [4] for slower devices.
-----------------------------------------------------------------------------
| SCHEDULER | Test |
-----------------------------------------------------------------------------
| BFQ | CFQ | DEADLINE | NOOP | |
-----------------------------------------------------------------------------
| | | | | Aggregate Throughput |
| | | | | [MB/s] |
| 399 | 400 | 400 | 400 | 10 raw seq. readers |
| 191 | 193 | 202 | 203 | 10 raw random readers |
-----------------------------------------------------------------------------
| | | | | Start-up time 10 seq |
| | | | | [sec] |
| 0.21 | >60 | 1.91 | 1.88 | xterm |
| 0.93 | >60 | 10.2 | 10.8 | oowriter |
| 0.89 | >60 | 29.7 | 30.0 | konsole |
-----------------------------------------------------------------------------
| | | | | Start-up time 10 rand |
| | | | | [sec] |
| 0.20 | 0.30 | 0.21 | 0.21 | xterm |
| 0.81 | 3.28 | 0.80 | 0.81 | oowriter |
| 0.88 | 2.90 | 1.02 | 1.00 | konsole |
-----------------------------------------------------------------------------
[1] https://lkml.org/lkml/2008/4/1/234
[2] 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
[3] https://youtu.be/1cjZeaCXIyM
[4] http://algogroup.unimore.it/people/paolo/disk_sched/results.php
[5] https://lkml.org/lkml/2016/2/1/818
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 (10):
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
Documentation/block/00-INDEX | 2 +
Documentation/block/bfq-iosched.txt | 516 +++
block/Kconfig.iosched | 27 +
block/Makefile | 1 +
block/bfq-iosched.c | 8195 +++++++++++++++++++++++++++++++++++
include/linux/blkdev.h | 2 +-
6 files changed, 8742 insertions(+), 1 deletion(-)
create mode 100644 Documentation/block/bfq-iosched.txt
create mode 100644 block/bfq-iosched.c
--
2.10.0
[toc] | [next] | [standalone]
| From | Paolo Valente <paolo.valente@linaro.org> |
|---|---|
| Date | 2016-10-26 11:30 +0200 |
| Subject | [PATCH 05/14] block, bfq: add more fairness with writes and slow processes |
| Message-ID | <swsH0-1Ia-11@gated-at.bofh.it> |
| In reply to | #1508990 |
This patch deals with two sources of unfairness, which can also cause
high latencies and throughput loss. The first source is related to
write requests. Write requests tend to starve read requests, basically
because, on one side, writes are slower than reads, whereas, on the
other side, storage devices confuse schedulers by deceptively
signaling the completion of write requests immediately after receiving
them. This patch addresses this issue by just throttling writes. In
particular, after a write request is dispatched for a queue, the
budget of the queue is decremented by the number of sectors to write,
multiplied by an (over)charge coefficient. The value of the
coefficient is the result of our tuning with different devices.
The second source of unfairness has to do with slowness detection:
when the in-service queue is expired, BFQ also controls whether the
queue has been "too slow", i.e., has consumed its last-assigned budget
at such a low rate that it would have been impossible to consume all
of this budget within the maximum time slice T_max (Subsec. 3.5 in
[1]). In this case, the queue is always (over)charged the whole
budget, to reduce its utilization of the device. Both this overcharge
and the slowness-detection criterion may cause unfairness.
First, always charging a full budget to a slow queue is too coarse. It
is much more accurate, and this patch lets BFQ do so, to charge an
amount of service 'equivalent' to the amount of time during which the
queue has been in service. As explained in more detail in the comments
on the code, this enables BFQ to provide time fairness among slow
queues.
Secondly, because of ZBR, a queue may be deemed as slow when its
associated process is performing I/O on the slowest zones of a
disk. However, unless the process is truly too slow, not reducing the
disk utilization of the queue is more profitable in terms of disk
throughput than the opposite. A similar problem is caused by logical
block mapping on non-rotational devices. For this reason, this patch
lets a queue be charged time, and not budget, only if the queue has
consumed less than 2/3 of its assigned budget. As an additional,
important benefit, this tolerance allows BFQ to preserve enough
elasticity to still perform bandwidth, and not time, distribution with
little unlucky or quasi-sequential processes.
Finally, for the same reasons as above, this patch makes slowness
detection itself much less harsh: a queue is deemed slow only if it
has consumed its budget at less than half of the peak rate.
[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 | 120 +++++++++++++++++++++++++++++++++++++---------------
1 file changed, 85 insertions(+), 35 deletions(-)
diff --git a/block/bfq-iosched.c b/block/bfq-iosched.c
index 101c591..3162e02 100644
--- a/block/bfq-iosched.c
+++ b/block/bfq-iosched.c
@@ -695,6 +695,13 @@ static const int bfq_stats_min_budgets = 194;
/* Default maximum budget values, in sectors and number of requests. */
static const int bfq_default_max_budget = 16 * 1024;
+/*
+ * Async to sync throughput distribution is controlled as follows:
+ * when an async request is served, the entity is charged the number
+ * of sectors of the request, multiplied by the factor below
+ */
+static const int bfq_async_charge_factor = 10;
+
/* Default timeout values, in jiffies, approximating CFQ defaults. */
static const int bfq_timeout = HZ / 8;
@@ -1371,22 +1378,52 @@ static void bfq_bfqq_served(struct bfq_queue *bfqq, int served)
}
/**
- * bfq_bfqq_charge_full_budget - set the service to the entity budget.
+ * bfq_bfqq_charge_time - charge an amount of service equivalent to the length
+ * of the time interval during which bfqq has been in
+ * service.
+ * @bfqd: the device
* @bfqq: the queue that needs a service update.
+ * @time_ms: the amount of time during which the queue has received service
*
- * When it's not possible to be fair in the service domain, because
- * a queue is not consuming its budget fast enough (the meaning of
- * fast depends on the timeout parameter), we charge it a full
- * budget. In this way we should obtain a sort of time-domain
- * fairness among all the seeky/slow queues.
+ * If a queue does not consume its budget fast enough, then providing
+ * the queue with service fairness may impair throughput, more or less
+ * severely. For this reason, queues that consume their budget slowly
+ * are provided with time fairness instead of service fairness. This
+ * goal is achieved through the BFQ scheduling engine, even if such an
+ * engine works in the service, and not in the time domain. The trick
+ * is charging these queues with an inflated amount of service, equal
+ * to the amount of service that they would have received during their
+ * service slot if they had been fast, i.e., if their requests had
+ * been dispatched at a rate equal to the estimated peak rate.
+ *
+ * It is worth noting that time fairness can cause important
+ * distortions in terms of bandwidth distribution, on devices with
+ * internal queueing. The reason is that I/O requests dispatched
+ * during the service slot of a queue may be served after that service
+ * slot is finished, and may have a total processing time loosely
+ * correlated with the duration of the service slot. This is
+ * especially true for short service slots.
*/
-static void bfq_bfqq_charge_full_budget(struct bfq_queue *bfqq)
+static void bfq_bfqq_charge_time(struct bfq_data *bfqd, struct bfq_queue *bfqq,
+ unsigned long time_ms)
{
struct bfq_entity *entity = &bfqq->entity;
+ int tot_serv_to_charge = entity->service;
+ unsigned int timeout_ms = jiffies_to_msecs(bfq_timeout);
+
+ if (time_ms > 0 && time_ms < timeout_ms)
+ tot_serv_to_charge =
+ (bfqd->bfq_max_budget * time_ms) / timeout_ms;
- bfq_log_bfqq(bfqq->bfqd, bfqq, "charge_full_budget");
+ if (tot_serv_to_charge < entity->service)
+ tot_serv_to_charge = entity->service;
- bfq_bfqq_served(bfqq, entity->budget - entity->service);
+ /* Increase budget to avoid inconsistencies */
+ if (tot_serv_to_charge > entity->budget)
+ entity->budget = tot_serv_to_charge;
+
+ bfq_bfqq_served(bfqq,
+ max_t(int, 0, tot_serv_to_charge - entity->service));
}
/**
@@ -3129,10 +3166,14 @@ static struct request *bfq_find_next_rq(struct bfq_data *bfqd,
return bfq_choose_req(bfqd, next, prev, blk_rq_pos(last));
}
+/* see the definition of bfq_async_charge_factor for details */
static unsigned long bfq_serv_to_charge(struct request *rq,
struct bfq_queue *bfqq)
{
- return blk_rq_sectors(rq);
+ if (bfq_bfqq_sync(bfqq))
+ return blk_rq_sectors(rq);
+
+ return blk_rq_sectors(rq) * bfq_async_charge_factor;
}
/**
@@ -4232,28 +4273,24 @@ static unsigned long bfq_smallest_from_now(void)
* @compensate: if true, compensate for the time spent idling.
* @reason: the reason causing the expiration.
*
+ * If the process associated with bfqq does slow I/O (e.g., because it
+ * issues random requests), we charge bfqq with the time it has been
+ * in service instead of the service it has received (see
+ * bfq_bfqq_charge_time for details on how this goal is achieved). As
+ * a consequence, bfqq will typically get higher timestamps upon
+ * reactivation, and hence it will be rescheduled as if it had
+ * received more service than what it has actually received. In the
+ * end, bfqq receives less service in proportion to how slowly its
+ * associated process consumes its budgets (and hence how seriously it
+ * tends to lower the throughput). In addition, this time-charging
+ * strategy guarantees time fairness among slow processes. In
+ * contrast, if the process associated with bfqq is not slow, we
+ * charge bfqq exactly with the service it has received.
*
- * If the process associated with the queue is slow (i.e., seeky), or
- * in case of budget timeout, or, finally, if it is async, we
- * artificially charge it an entire budget (independently of the
- * actual service it received). As a consequence, the queue will get
- * higher timestamps than the correct ones upon reactivation, and
- * hence it will be rescheduled as if it had received more service
- * than what it actually received. In the end, this class of processes
- * will receive less service in proportion to how slowly they consume
- * their budgets (and hence how seriously they tend to lower the
- * throughput).
- *
- * In contrast, when a queue expires because it has been idling for
- * too much or because it exhausted its budget, we do not touch the
- * amount of service it has received. Hence when the queue will be
- * reactivated and its timestamps updated, the latter will be in sync
- * with the actual service received by the queue until expiration.
- *
- * Charging a full budget to the first type of queues and the exact
- * service to the others has the effect of using the WF2Q+ policy to
- * schedule the former on a timeslice basis, without violating the
- * service domain guarantees of the latter.
+ * Charging time to the first type of queues and the exact service to
+ * the other has the effect of using the WF2Q+ policy to schedule the
+ * former on a timeslice basis, without violating service domain
+ * guarantees among the latter.
*/
static void bfq_bfqq_expire(struct bfq_data *bfqd,
struct bfq_queue *bfqq,
@@ -4270,11 +4307,24 @@ static void bfq_bfqq_expire(struct bfq_data *bfqd,
slow = bfq_bfqq_is_slow(bfqd, bfqq, compensate, reason, &delta);
/*
- * As above explained, 'punish' slow (i.e., seeky), timed-out
- * and async queues, to favor sequential sync workloads.
+ * As above explained, charge slow (typically seeky) and
+ * timed-out queues with the time and not the service
+ * received, to favor sequential workloads.
+ *
+ * Processes doing I/O in the slower disk zones will tend to
+ * be slow(er) even if not seeky. Therefore, since the
+ * estimated peak rate is actually an average over the disk
+ * surface, these processes may timeout just for bad luck. To
+ * avoid punishing them, do not charge time to processes that
+ * succeeded in consuming at least 2/3 of their budget. This
+ * allows BFQ to preserve enough elasticity to still perform
+ * bandwidth, and not time, distribution with little unlucky
+ * or quasi-sequential processes.
*/
- if (slow || reason == BFQ_BFQQ_BUDGET_TIMEOUT)
- bfq_bfqq_charge_full_budget(bfqq);
+ if (slow ||
+ (reason == BFQ_BFQQ_BUDGET_TIMEOUT &&
+ bfq_bfqq_budget_left(bfqq) >= entity->budget / 3))
+ bfq_bfqq_charge_time(bfqd, bfqq, delta);
if (reason == BFQ_BFQQ_TOO_IDLE &&
entity->service <= 2 * entity->budget / 10)
--
2.10.0
[toc] | [prev] | [next] | [standalone]
| From | Paolo Valente <paolo.valente@linaro.org> |
|---|---|
| Date | 2016-10-26 11:40 +0200 |
| Subject | [PATCH 04/14] block, bfq: modify the peak-rate estimator |
| Message-ID | <swsQF-1Lu-1@gated-at.bofh.it> |
| In reply to | #1508990 |
Unless the maximum budget B_max that BFQ can assign to a queue is set
explicitly by the user, BFQ automatically updates B_max. In
particular, BFQ dynamically sets B_max to the number of sectors that
can be read, at the current estimated peak rate, during the maximum
time, T_max, allowed before a budget timeout occurs. In formulas, if
we denote as R_est the estimated peak rate, then B_max = T_max ∗
R_est. Hence, the higher R_est is with respect to the actual device
peak rate, the higher the probability that processes incur budget
timeouts unjustly is. Besides, a too high value of B_max unnecessarily
increases the deviation from an ideal, smooth service.
Unfortunately, it is not trivial to estimate the peak rate correctly:
because of the presence of sw and hw queues between the scheduler and
the device components that finally serve I/O requests, it is hard to
say exactly when a given dispatched request is served inside the
device, and for how long. As a consequence, it is hard to know
precisely at what rate a given set of requests is actually served by
the device.
On the opposite end, the dispatch time of any request is trivially
available, and, from this piece of information, the "dispatch rate"
of requests can be immediately computed. So, the idea in the next
function is to use what is known, namely request dispatch times
(plus, when useful, request completion times), to estimate what is
unknown, namely in-device request service rate.
The main issue is that, because of the above facts, the rate at
which a certain set of requests is dispatched over a certain time
interval can vary greatly with respect to the rate at which the
same requests are then served. But, since the size of any
intermediate queue is limited, and the service scheme is lossless
(no request is silently dropped), the following obvious convergence
property holds: the number of requests dispatched MUST become
closer and closer to the number of requests completed as the
observation interval grows. This is the key property used in
this new version of the peak-rate estimator.
Signed-off-by: Paolo Valente <paolo.valente@linaro.org>
Signed-off-by: Arianna Avanzini <avanzini.arianna@gmail.com>
---
block/bfq-iosched.c | 496 +++++++++++++++++++++++++++++++++++++++-------------
1 file changed, 376 insertions(+), 120 deletions(-)
diff --git a/block/bfq-iosched.c b/block/bfq-iosched.c
index fa1e531..101c591 100644
--- a/block/bfq-iosched.c
+++ b/block/bfq-iosched.c
@@ -367,14 +367,32 @@ struct bfq_data {
/* on-disk position of the last served request */
sector_t last_position;
+ /* time of last request completion (ns) */
+ u64 last_completion;
+
+ /* time of first rq dispatch in current observation interval (ns) */
+ u64 first_dispatch;
+ /* time of last rq dispatch in current observation interval (ns) */
+ u64 last_dispatch;
+
/* beginning of the last budget */
ktime_t last_budget_start;
/* beginning of the last idle slice */
ktime_t last_idling_start;
- /* number of samples used to calculate @peak_rate */
+
+ /* number of samples in current observation interval */
int peak_rate_samples;
- /* peak transfer rate observed for a budget */
- u64 peak_rate;
+ /* num of samples of seq dispatches in current observation interval */
+ u32 sequential_samples;
+ /* total num of sectors transferred in current observation interval */
+ u64 tot_sectors_dispatched;
+ /* max rq size seen during current observation interval (sectors) */
+ u32 last_rq_max_size;
+ /* time elapsed from first dispatch in current observ. interval (us) */
+ u64 delta_from_first;
+ /* current estimate of device peak rate */
+ u32 peak_rate;
+
/* maximum budget allotted to a bfq_queue before rescheduling */
int bfq_max_budget;
@@ -682,7 +700,7 @@ static const int bfq_timeout = HZ / 8;
struct kmem_cache *bfq_pool;
-/* Below this threshold (in ms), we consider thinktime immediate. */
+/* Below this threshold (in ns), we consider thinktime immediate. */
#define BFQ_MIN_TT (2 * NSEC_PER_MSEC)
/* hw_tag detection: parallel requests threshold and min samples needed. */
@@ -692,8 +710,12 @@ struct kmem_cache *bfq_pool;
#define BFQQ_SEEK_THR (sector_t)(8 * 100)
#define BFQQ_SEEKY(bfqq) (hweight32(bfqq->seek_history) > 32/8)
-/* Min samples used for peak rate estimation (for autotuning). */
-#define BFQ_PEAK_RATE_SAMPLES 32
+/* Min number of samples required to perform peak-rate update */
+#define BFQ_RATE_MIN_SAMPLES 32
+/* Min observation time interval required to perform a peak-rate update (ns) */
+#define BFQ_RATE_MIN_INTERVAL (300*NSEC_PER_MSEC)
+/* Target observation time interval for a peak-rate update (ns) */
+#define BFQ_RATE_REF_INTERVAL NSEC_PER_SEC
/* Shift used for peak rate fixed precision calculations. */
#define BFQ_RATE_SHIFT 16
@@ -3400,14 +3422,25 @@ static struct request *bfq_find_rq_fmerge(struct bfq_data *bfqd,
return NULL;
}
+static sector_t get_sdist(sector_t last_pos, struct request *rq)
+{
+ sector_t sdist = 0;
+
+ if (last_pos) {
+ if (last_pos < blk_rq_pos(rq))
+ sdist = blk_rq_pos(rq) - last_pos;
+ else
+ sdist = last_pos - blk_rq_pos(rq);
+ }
+
+ return sdist;
+}
+
static void bfq_activate_request(struct request_queue *q, struct request *rq)
{
struct bfq_data *bfqd = q->elevator->elevator_data;
bfqd->rq_in_driver++;
- bfqd->last_position = blk_rq_pos(rq) + blk_rq_sectors(rq);
- bfq_log(bfqd, "activate_request: new bfqd->last_position %llu",
- (unsigned long long)bfqd->last_position);
}
static void bfq_deactivate_request(struct request_queue *q, struct request *rq)
@@ -3659,6 +3692,226 @@ static void bfq_set_budget_timeout(struct bfq_data *bfqd)
}
/*
+ * In autotuning mode, max_budget is dynamically recomputed as the
+ * amount of sectors transferred in timeout at the estimated peak
+ * rate. This enables BFQ to utilize a full timeslice with a full
+ * budget, even if the in-service queue is served at peak rate. And
+ * this maximises throughput with sequential workloads.
+ */
+static unsigned long bfq_calc_max_budget(struct bfq_data *bfqd)
+{
+ return (u64)bfqd->peak_rate * USEC_PER_MSEC *
+ jiffies_to_msecs(bfqd->bfq_timeout)>>BFQ_RATE_SHIFT;
+}
+
+void bfq_reset_rate_computation(struct bfq_data *bfqd, struct request *rq)
+{
+ if (rq != NULL) { /* new rq dispatch now, reset accordingly */
+ bfqd->last_dispatch = bfqd->first_dispatch = ktime_get_ns();
+ bfqd->peak_rate_samples = 1;
+ bfqd->sequential_samples = 0;
+ bfqd->tot_sectors_dispatched = bfqd->last_rq_max_size =
+ blk_rq_sectors(rq);
+ } else /* no new rq dispatched, just reset the number of samples */
+ bfqd->peak_rate_samples = 0; /* full re-init on next disp. */
+
+ bfq_log(bfqd,
+ "reset_rate_computation at end, sample %u/%u tot_sects %llu",
+ bfqd->peak_rate_samples, bfqd->sequential_samples,
+ bfqd->tot_sectors_dispatched);
+}
+
+void bfq_update_rate_reset(struct bfq_data *bfqd, struct request *rq)
+{
+ u32 rate, weight, divisor;
+
+ /*
+ * For the convergence property to hold (see comments on
+ * bfq_update_peak_rate()) and for the assessment to be
+ * reliable, a minimum number of samples must be present, and
+ * a minimum amount of time must have elapsed. If not so, do
+ * not compute new rate. Just reset parameters, to get ready
+ * for a new evaluation attempt.
+ */
+ if (bfqd->peak_rate_samples < BFQ_RATE_MIN_SAMPLES ||
+ bfqd->delta_from_first < BFQ_RATE_MIN_INTERVAL)
+ goto reset_computation;
+
+ /*
+ * If a new request completion has occurred after last
+ * dispatch, then, to approximate the rate at which requests
+ * have been served by the device, it is more precise to
+ * extend the observation interval to the last completion.
+ */
+ bfqd->delta_from_first =
+ max_t(u64, bfqd->delta_from_first,
+ bfqd->last_completion - bfqd->first_dispatch);
+
+ /*
+ * Rate computed in sects/usec, and not sects/nsec, for
+ * precision issues.
+ */
+ rate = div64_ul(bfqd->tot_sectors_dispatched<<BFQ_RATE_SHIFT,
+ div_u64(bfqd->delta_from_first, NSEC_PER_USEC));
+
+ /*
+ * Peak rate not updated if:
+ * - the percentage of sequential dispatches is below 3/4 of the
+ * total, and rate is below the current estimated peak rate
+ * - rate is unreasonably high (> 20M sectors/sec)
+ */
+ if ((bfqd->peak_rate_samples > (3 * bfqd->sequential_samples)>>2 &&
+ rate <= bfqd->peak_rate) ||
+ rate > 20<<BFQ_RATE_SHIFT)
+ goto reset_computation;
+
+ /*
+ * We have to update the peak rate, at last! To this purpose,
+ * we use a low-pass filter. We compute the smoothing constant
+ * of the filter as a function of the 'weight' of the new
+ * measured rate.
+ *
+ * As can be seen in next formulas, we define this weight as a
+ * quantity proportional to how sequential the workload is,
+ * and to how long the observation time interval is.
+ *
+ * The weight runs from 0 to 8. The maximum value of the
+ * weight, 8, yields the minimum value for the smoothing
+ * constant. At this minimum value for the smoothing constant,
+ * the measured rate contributes for half of the next value of
+ * the estimated peak rate.
+ *
+ * So, the first step is to compute the weight as a function
+ * of how sequential the workload is. Note that the weight
+ * cannot reach 9, because bfqd->sequential_samples cannot
+ * become equal to bfqd->peak_rate_samples, which, in its
+ * turn, holds true because bfqd->sequential_samples is not
+ * incremented for the first sample.
+ */
+ weight = (9 * bfqd->sequential_samples) / bfqd->peak_rate_samples;
+
+ /*
+ * Second step: further refine the weight as a function of the
+ * duration of the observation interval.
+ */
+ weight = min_t(u32, 8,
+ div_u64(weight * bfqd->delta_from_first,
+ BFQ_RATE_REF_INTERVAL));
+
+ /*
+ * Divisor ranging from 10, for minimum weight, to 2, for
+ * maximum weight.
+ */
+ divisor = 10 - weight;
+
+ /*
+ * Finally, update peak rate:
+ *
+ * peak_rate = peak_rate * (divisor-1) / divisor + rate / divisor
+ */
+ bfqd->peak_rate *= divisor-1;
+ bfqd->peak_rate /= divisor;
+ rate /= divisor; /* smoothing constant alpha = 1/divisor */
+
+ bfqd->peak_rate += rate;
+ if (bfqd->bfq_user_max_budget == 0)
+ bfqd->bfq_max_budget =
+ bfq_calc_max_budget(bfqd);
+
+reset_computation:
+ bfq_reset_rate_computation(bfqd, rq);
+}
+
+/*
+ * Update the read/write peak rate (the main quantity used for
+ * auto-tuning, see update_thr_responsiveness_params()).
+ *
+ * It is not trivial to estimate the peak rate (correctly): because of
+ * the presence of sw and hw queues between the scheduler and the
+ * device components that finally serve I/O requests, it is hard to
+ * say exactly when a given dispatched request is served inside the
+ * device, and for how long. As a consequence, it is hard to know
+ * precisely at what rate a given set of requests is actually served
+ * by the device.
+ *
+ * On the opposite end, the dispatch time of any request is trivially
+ * available, and, from this piece of information, the "dispatch rate"
+ * of requests can be immediately computed. So, the idea in the next
+ * function is to use what is known, namely request dispatch times
+ * (plus, when useful, request completion times), to estimate what is
+ * unknown, namely in-device request service rate.
+ *
+ * The main issue is that, because of the above facts, the rate at
+ * which a certain set of requests is dispatched over a certain time
+ * interval can vary greatly with respect to the rate at which the
+ * same requests are then served. But, since the size of any
+ * intermediate queue is limited, and the service scheme is lossless
+ * (no request is silently dropped), the following obvious convergence
+ * property holds: the number of requests dispatched MUST become
+ * closer and closer to the number of requests completed as the
+ * observation interval grows. This is the key property used in
+ * the next function to estimate the peak service rate as a function
+ * of the observed dispatch rate. The function assumes to be invoked
+ * on every request dispatch.
+ */
+void bfq_update_peak_rate(struct bfq_data *bfqd, struct request *rq)
+{
+ u64 now_ns = ktime_get_ns();
+
+ if (bfqd->peak_rate_samples == 0) { /* first dispatch */
+ bfq_log(bfqd, "update_peak_rate: goto reset, samples %d",
+ bfqd->peak_rate_samples);
+ bfq_reset_rate_computation(bfqd, rq);
+ goto update_last_values; /* will add one sample */
+ }
+
+ /*
+ * Device idle for very long: the observation interval lasting
+ * up to this dispatch cannot be a valid observation interval
+ * for computing a new peak rate (similarly to the late-
+ * completion event in bfq_completed_request()). Go to
+ * update_rate_and_reset to have the following three steps
+ * taken:
+ * - close the observation interval at the last (previous)
+ * request dispatch or completion
+ * - compute rate, if possible, for that observation interval
+ * - start a new observation interval with this dispatch
+ */
+ if (now_ns - bfqd->last_dispatch > 100*NSEC_PER_MSEC &&
+ bfqd->rq_in_driver == 0)
+ goto update_rate_and_reset;
+
+ /* Update sampling information */
+ bfqd->peak_rate_samples++;
+
+ if ((bfqd->rq_in_driver > 0 ||
+ now_ns - bfqd->last_completion < BFQ_MIN_TT)
+ && get_sdist(bfqd->last_position, rq) < BFQQ_SEEK_THR)
+ bfqd->sequential_samples++;
+
+ bfqd->tot_sectors_dispatched += blk_rq_sectors(rq);
+
+ /* Reset max observed rq size every 32 dispatches */
+ if (likely(bfqd->peak_rate_samples % 32))
+ bfqd->last_rq_max_size =
+ max_t(u32, blk_rq_sectors(rq), bfqd->last_rq_max_size);
+ else
+ bfqd->last_rq_max_size = blk_rq_sectors(rq);
+
+ bfqd->delta_from_first = now_ns - bfqd->first_dispatch;
+
+ /* Target observation interval not yet reached, go on sampling */
+ if (bfqd->delta_from_first < BFQ_RATE_REF_INTERVAL)
+ goto update_last_values;
+
+update_rate_and_reset:
+ bfq_update_rate_reset(bfqd, rq);
+update_last_values:
+ bfqd->last_position = blk_rq_pos(rq) + blk_rq_sectors(rq);
+ bfqd->last_dispatch = now_ns;
+}
+
+/*
* Move request from internal lists to the dispatch list of the request queue.
*/
static void bfq_dispatch_insert(struct request_queue *q, struct request *rq)
@@ -3676,6 +3929,7 @@ static void bfq_dispatch_insert(struct request_queue *q, struct request *rq)
* incrementing bfqq->dispatched.
*/
bfqq->dispatched++;
+ bfq_update_peak_rate(q->elevator->elevator_data, rq);
bfq_remove_request(rq);
elv_dispatch_sort(q, rq);
@@ -3874,105 +4128,92 @@ static void __bfq_bfqq_recalc_budget(struct bfq_data *bfqd,
bfqq->entity.budget);
}
-static unsigned long bfq_calc_max_budget(u64 peak_rate, u64 timeout)
-{
- unsigned long max_budget;
-
- /*
- * The max_budget calculated when autotuning is equal to the
- * amount of sectors transferred in timeout at the
- * estimated peak rate.
- */
- max_budget = (unsigned long)(peak_rate * 1000 *
- timeout >> BFQ_RATE_SHIFT);
-
- return max_budget;
-}
-
/*
- * In addition to updating the peak rate, checks whether the process
- * is "slow", and returns 1 if so. This slow flag is used, in addition
- * to the budget timeout, to reduce the amount of service provided to
- * seeky processes, and hence reduce their chances to lower the
- * throughput. See the code for more details.
+ * Return true if the process associated with bfqq is "slow". The slow
+ * flag is used, in addition to the budget timeout, to reduce the
+ * amount of service provided to seeky processes, and thus reduce
+ * their chances to lower the throughput. More details in the comments
+ * on the function bfq_bfqq_expire().
+ *
+ * An important observation is in order: as discussed in the comments
+ * on the function bfq_update_peak_rate(), with devices with internal
+ * queues, it is hard if ever possible to know when and for how long
+ * an I/O request is processed by the device (apart from the trivial
+ * I/O pattern where a new request is dispatched only after the
+ * previous one has been completed). This makes it hard to evaluate
+ * the real rate at which the I/O requests of each bfq_queue are
+ * served. In fact, for an I/O scheduler like BFQ, serving a
+ * bfq_queue means just dispatching its requests during its service
+ * slot (i.e., until the budget of the queue is exhausted, or the
+ * queue remains idle, or, finally, a timeout fires). But, during the
+ * service slot of a bfq_queue, around 100 ms at most, the device may
+ * be even still processing requests of bfq_queues served in previous
+ * service slots. On the opposite end, the requests of the in-service
+ * bfq_queue may be completed after the service slot of the queue
+ * finishes.
+ *
+ * Anyway, unless more sophisticated solutions are used
+ * (where possible), the sum of the sizes of the requests dispatched
+ * during the service slot of a bfq_queue is probably the only
+ * approximation available for the service received by the bfq_queue
+ * during its service slot. And this sum is the quantity used in this
+ * function to evaluate the I/O speed of a process.
*/
-static bool bfq_update_peak_rate(struct bfq_data *bfqd, struct bfq_queue *bfqq,
- bool compensate)
+static bool bfq_bfqq_is_slow(struct bfq_data *bfqd, struct bfq_queue *bfqq,
+ bool compensate, enum bfqq_expiration reason,
+ unsigned long *delta_ms)
{
- u64 bw, usecs, expected, timeout;
- ktime_t delta;
- int update = 0;
+ ktime_t delta_ktime;
+ u32 delta_usecs;
+ bool slow = BFQQ_SEEKY(bfqq); /* if delta too short, use seekyness */
- if (!bfq_bfqq_sync(bfqq) || bfq_bfqq_budget_new(bfqq))
+ if (!bfq_bfqq_sync(bfqq))
return false;
if (compensate)
- delta = bfqd->last_idling_start;
+ delta_ktime = bfqd->last_idling_start;
else
- delta = ktime_get();
- delta = ktime_sub(delta, bfqd->last_budget_start);
- usecs = ktime_to_us(delta);
-
- /* Don't trust short/unrealistic values. */
- if (usecs < 100 || usecs >= LONG_MAX)
- return false;
-
- /*
- * Calculate the bandwidth for the last slice. We use a 64 bit
- * value to store the peak rate, in sectors per usec in fixed
- * point math. We do so to have enough precision in the estimate
- * and to avoid overflows.
- */
- bw = (u64)bfqq->entity.service << BFQ_RATE_SHIFT;
- do_div(bw, (unsigned long)usecs);
+ delta_ktime = ktime_get();
+ delta_ktime = ktime_sub(delta_ktime, bfqd->last_budget_start);
+ delta_usecs = ktime_to_us(delta_ktime);
+
+ /* don't trust short/unrealistic values. */
+ if (delta_usecs < 1000 || delta_usecs >= LONG_MAX) {
+ if (blk_queue_nonrot(bfqd->queue))
+ /*
+ * give same worst-case guarantees as idling
+ * for seeky
+ */
+ *delta_ms = BFQ_MIN_TT / NSEC_PER_MSEC;
+ else /* charge at least one seek */
+ *delta_ms = bfq_slice_idle / NSEC_PER_MSEC;
+
+ return slow;
+ }
- timeout = jiffies_to_msecs(bfqd->bfq_timeout);
+ *delta_ms = delta_usecs / USEC_PER_MSEC;
/*
- * Use only long (> 20ms) intervals to filter out spikes for
- * the peak rate estimation.
+ * Use only long (> 20ms) intervals to filter out excessive
+ * spikes in service rate estimation.
*/
- if (usecs > 20000) {
- if (bw > bfqd->peak_rate) {
- bfqd->peak_rate = bw;
- update = 1;
- bfq_log(bfqd, "new peak_rate=%llu", bw);
- }
-
- update |= bfqd->peak_rate_samples == BFQ_PEAK_RATE_SAMPLES - 1;
-
- if (bfqd->peak_rate_samples < BFQ_PEAK_RATE_SAMPLES)
- bfqd->peak_rate_samples++;
-
- if (bfqd->peak_rate_samples == BFQ_PEAK_RATE_SAMPLES &&
- update && bfqd->bfq_user_max_budget == 0) {
- bfqd->bfq_max_budget =
- bfq_calc_max_budget(bfqd->peak_rate,
- timeout);
- bfq_log(bfqd, "new max_budget=%d",
- bfqd->bfq_max_budget);
- }
+ if (delta_usecs > 20000) {
+ /*
+ * Caveat for rotational devices: processes doing I/O
+ * in the slower disk zones tend to be slow(er) even
+ * if not seeky. In this respect, the estimated peak
+ * rate is likely to be an average over the disk
+ * surface. Accordingly, to not be too harsh with
+ * unlucky processes, a process is deemed slow only if
+ * its rate has been lower than half of the estimated
+ * peak rate.
+ */
+ slow = bfqq->entity.service < bfqd->bfq_max_budget / 2;
}
- /*
- * A process is considered ``slow'' (i.e., seeky, so that we
- * cannot treat it fairly in the service domain, as it would
- * slow down too much the other processes) if, when a slice
- * ends for whatever reason, it has received service at a
- * rate that would not be high enough to complete the budget
- * before the budget timeout expiration.
- */
- expected = bw * 1000 * timeout >> BFQ_RATE_SHIFT;
+ bfq_log_bfqq(bfqd, bfqq, "bfq_bfqq_is_slow: slow %d", slow);
- /*
- * Caveat: processes doing IO in the slower disk zones will
- * tend to be slow(er) even if not seeky. And the estimated
- * peak rate will actually be an average over the disk
- * surface. Hence, to not be too harsh with unlucky processes,
- * we keep a budget/3 margin of safety before declaring a
- * process slow.
- */
- return expected > (4 * bfqq->entity.budget) / 3;
+ return slow;
}
/*
@@ -4020,12 +4261,13 @@ static void bfq_bfqq_expire(struct bfq_data *bfqd,
enum bfqq_expiration reason)
{
bool slow;
+ unsigned long delta = 0;
+ struct bfq_entity *entity = &bfqq->entity;
/*
- * Update device peak rate for autotuning and check whether the
- * process is slow (see bfq_update_peak_rate).
+ * Check whether the process is slow (see bfq_bfqq_is_slow).
*/
- slow = bfq_update_peak_rate(bfqd, bfqq, compensate);
+ slow = bfq_bfqq_is_slow(bfqd, bfqq, compensate, reason, &delta);
/*
* As above explained, 'punish' slow (i.e., seeky), timed-out
@@ -4035,7 +4277,7 @@ static void bfq_bfqq_expire(struct bfq_data *bfqd,
bfq_bfqq_charge_full_budget(bfqq);
if (reason == BFQ_BFQQ_TOO_IDLE &&
- bfqq->entity.service <= 2 * bfqq->entity.budget / 10)
+ entity->service <= 2 * entity->budget / 10)
bfq_clear_bfqq_IO_bound(bfqq);
bfq_log_bfqq(bfqd, bfqq,
@@ -4636,17 +4878,9 @@ static void
bfq_update_io_seektime(struct bfq_data *bfqd, struct bfq_queue *bfqq,
struct request *rq)
{
- sector_t sdist = 0;
-
- if (bfqq->last_request_pos) {
- if (bfqq->last_request_pos < blk_rq_pos(rq))
- sdist = blk_rq_pos(rq) - bfqq->last_request_pos;
- else
- sdist = bfqq->last_request_pos - blk_rq_pos(rq);
- }
-
bfqq->seek_history <<= 1;
- bfqq->seek_history |= (sdist > BFQQ_SEEK_THR);
+ bfqq->seek_history |=
+ get_sdist(bfqq->last_request_pos, rq) > BFQQ_SEEK_THR;
}
/*
@@ -4804,6 +5038,8 @@ static void bfq_completed_request(struct request_queue *q, struct request *rq)
{
struct bfq_queue *bfqq = RQ_BFQQ(rq);
struct bfq_data *bfqd = bfqq->bfqd;
+ u64 now_ns;
+ u32 delta_us;
bfq_update_hw_tag(bfqd);
@@ -4814,7 +5050,37 @@ static void bfq_completed_request(struct request_queue *q, struct request *rq)
rq_io_start_time_ns(rq), req_op(rq),
rq->cmd_flags);
- RQ_BIC(rq)->ttime.last_end_request = ktime_get_ns();
+ now_ns = ktime_get_ns();
+
+ RQ_BIC(rq)->ttime.last_end_request = now_ns;
+
+ /*
+ * Using us instead of ns, to get a reasonable precision in
+ * computing rate in next check.
+ */
+ delta_us = div_u64(now_ns - bfqd->last_completion, NSEC_PER_USEC);
+
+ /*
+ * If the request took rather long to complete, and, according
+ * to the maximum request size recorded, this completion latency
+ * implies that the request was certainly served at a very low
+ * rate (less than 1M sectors/sec), then the whole observation
+ * interval that lasts up to this time instant cannot be a
+ * valid time interval for computing a new peak rate. Invoke
+ * bfq_update_rate_reset to have the following three steps
+ * taken:
+ * - close the observation interval at the last (previous)
+ * request dispatch or completion
+ * - compute rate, if possible, for that observation interval
+ * - reset to zero samples, which will trigger a proper
+ * re-initialization of the observation interval on next
+ * dispatch
+ */
+ if (delta_us > BFQ_MIN_TT/NSEC_PER_USEC &&
+ (bfqd->last_rq_max_size<<BFQ_RATE_SHIFT)/delta_us <
+ 1UL<<(BFQ_RATE_SHIFT - 10))
+ bfq_update_rate_reset(bfqd, NULL);
+ bfqd->last_completion = now_ns;
/*
* If this is the in-service queue, check if it needs to be expired,
@@ -5322,16 +5588,6 @@ static ssize_t bfq_weights_store(struct elevator_queue *e,
return count;
}
-static unsigned long bfq_estimated_max_budget(struct bfq_data *bfqd)
-{
- u64 timeout = jiffies_to_msecs(bfqd->bfq_timeout);
-
- if (bfqd->peak_rate_samples >= BFQ_PEAK_RATE_SAMPLES)
- return bfq_calc_max_budget(bfqd->peak_rate, timeout);
- else
- return bfq_default_max_budget;
-}
-
static ssize_t bfq_max_budget_store(struct elevator_queue *e,
const char *page, size_t count)
{
@@ -5340,7 +5596,7 @@ static ssize_t bfq_max_budget_store(struct elevator_queue *e,
int ret = bfq_var_store(&__data, (page), count);
if (__data == 0)
- bfqd->bfq_max_budget = bfq_estimated_max_budget(bfqd);
+ bfqd->bfq_max_budget = bfq_calc_max_budget(bfqd);
else {
if (__data > INT_MAX)
__data = INT_MAX;
@@ -5370,7 +5626,7 @@ static ssize_t bfq_timeout_sync_store(struct elevator_queue *e,
bfqd->bfq_timeout = msecs_to_jiffies(__data);
if (bfqd->bfq_user_max_budget == 0)
- bfqd->bfq_max_budget = bfq_estimated_max_budget(bfqd);
+ bfqd->bfq_max_budget = bfq_calc_max_budget(bfqd);
return ret;
}
--
2.10.0
[toc] | [prev] | [next] | [standalone]
| From | Paolo Valente <paolo.valente@linaro.org> |
|---|---|
| Date | 2016-10-26 11:40 +0200 |
| Subject | [PATCH 03/14] block, bfq: improve throughput boosting |
| Message-ID | <swsQG-1Lu-11@gated-at.bofh.it> |
| In reply to | #1508990 |
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 | 83 ++++++++++++++++++++++++++---------------------------
1 file changed, 41 insertions(+), 42 deletions(-)
diff --git a/block/bfq-iosched.c b/block/bfq-iosched.c
index e33f85e..fa1e531 100644
--- a/block/bfq-iosched.c
+++ b/block/bfq-iosched.c
@@ -692,9 +692,6 @@ struct kmem_cache *bfq_pool;
#define BFQQ_SEEK_THR (sector_t)(8 * 100)
#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
@@ -3609,36 +3606,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.
- */
- 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;
@@ -3780,13 +3747,47 @@ static void __bfq_bfqq_recalc_budget(struct bfq_data *bfqd,
* for throughput.
*/
case BFQ_BFQQ_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 BFQ_BFQQ_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 BFQ_BFQQ_BUDGET_EXHAUSTED:
/*
@@ -3798,8 +3799,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 BFQ_BFQQ_NO_MORE_REQUESTS:
/*
@@ -4533,9 +4533,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]
| From | Paolo Valente <paolo.valente@linaro.org> |
|---|---|
| Date | 2016-10-26 11:40 +0200 |
| Subject | [PATCH 09/14] block, bfq: reduce latency during request-pool saturation |
| Message-ID | <swsQG-1Lu-51@gated-at.bofh.it> |
| In reply to | #1508990 |
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 3b11772..46d6df3 100644
--- a/block/bfq-iosched.c
+++ b/block/bfq-iosched.c
@@ -378,6 +378,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 */
@@ -2019,6 +2021,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, requeue);
@@ -2035,6 +2040,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++;
}
#if defined(CONFIG_BFQ_GROUP_IOSCHED) && defined(CONFIG_DEBUG_BLK_CGROUP)
@@ -3335,7 +3343,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;
}
/**
@@ -3791,6 +3808,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)
@@ -4003,6 +4021,8 @@ static void bfq_merged_requests(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;
@@ -5049,7 +5069,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;
@@ -5072,6 +5093,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
@@ -5145,7 +5204,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);
}
/*
@@ -6315,6 +6374,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]
| From | Paolo Valente <paolo.valente@linaro.org> |
|---|---|
| Date | 2016-10-26 11:40 +0200 |
| Subject | [PATCH 07/14] block, bfq: reduce I/O latency for soft real-time applications |
| Message-ID | <swsQG-1Lu-41@gated-at.bofh.it> |
| In reply to | #1508990 |
To guarantee a low latency also to the I/O requests issued by soft
real-time applications, this patch introduces a further heuristic,
which weight-raises (in the sense explained in the previous patch)
also the queues associated to applications deemed as soft real-time.
To be deemed as soft real-time, an application must meet two
requirements. First, the application must not require an average
bandwidth higher than the approximate bandwidth required to playback
or record a compressed high-definition video. Second, the request
pattern of the application must be isochronous, i.e., after issuing a
request or a batch of requests, the application must stop issuing new
requests until all its pending requests have been completed. After
that, the application may issue a new batch, and so on.
As for the second requirement, it is critical to require also that,
after all the pending requests of the application have been completed,
an adequate minimum amount of time elapses before the application
starts issuing new requests. This prevents also greedy (i.e.,
I/O-bound) applications from being incorrectly deemed, occasionally,
as soft real-time. In fact, if *any amount of time* is fine, then even
a greedy application may, paradoxically, meet both the above
requirements, if: (1) the application performs random I/O and/or the
device is slow, and (2) the CPU load is high. The reason is the
following. First, if condition (1) is true, then, during the service
of the application, the throughput may be low enough to let the
application meet the bandwidth requirement. Second, if condition (2)
is true as well, then the application may occasionally behave in an
apparently isochronous way, because it may simply stop issuing
requests while the CPUs are busy serving other processes.
To address this issue, the heuristic leverages the simple fact that
greedy applications issue *all* their requests as quickly as they can,
whereas soft real-time applications spend some time processing data
after each batch of requests is completed. In particular, the
heuristic works as follows. First, according to the above isochrony
requirement, the heuristic checks whether an application may be soft
real-time, thereby giving to the application the opportunity to be
deemed as such, only when both the following two conditions happen to
hold: 1) the queue associated with the application has expired and is
empty, 2) there is no outstanding request of the application.
Suppose that both conditions hold at time, say, t_c and that the
application issues its next request at time, say, t_i. At time t_c the
heuristic computes the next time instant, called soft_rt_next_start in
the code, such that, only if t_i >= soft_rt_next_start, then both the
next conditions will hold when the application issues its next
request: 1) the application will meet the above bandwidth requirement,
2) a given minimum time interval, say Delta, will have elapsed from
time t_c (so as to filter out greedy application).
The current value of Delta is a little bit higher than the value that
we have found, experimentally, to be adequate on a real,
general-purpose machine. In particular we had to increase Delta to
make the filter quite precise also in slower, embedded systems, and in
KVM/QEMU virtual machines (details in the comments on the code).
If the application actually issues its next request after time
soft_rt_next_start, then its associated queue will be weight-raised
for a relatively short time interval. If, during this time interval,
the application proves again to meet the bandwidth and isochrony
requirements, then the end of the weight-raising period for the queue
is moved forward, and so on. Note that an application whose associated
queue never happens to be empty when it expires will never have the
opportunity to be deemed as soft real-time.
Signed-off-by: Paolo Valente <paolo.valente@linaro.org>
Signed-off-by: Arianna Avanzini <avanzini.arianna@gmail.com>
---
block/Kconfig.iosched | 2 +-
block/bfq-iosched.c | 359 ++++++++++++++++++++++++++++++++++++++++++++++----
2 files changed, 337 insertions(+), 24 deletions(-)
diff --git a/block/Kconfig.iosched b/block/Kconfig.iosched
index ecc6ca2..be242aa 100644
--- a/block/Kconfig.iosched
+++ b/block/Kconfig.iosched
@@ -46,7 +46,7 @@ config IOSCHED_BFQ
The BFQ I/O scheduler distributes bandwidth among all
processes according to their weights, regardless of the
device parameters and with any workload. It also guarantees
- a low latency to interactive applications.
+ a low latency to interactive and soft real-time applications.
config BFQ_GROUP_IOSCHED
bool "BFQ hierarchical scheduling support"
diff --git a/block/bfq-iosched.c b/block/bfq-iosched.c
index e5a92fa..d9b0900 100644
--- a/block/bfq-iosched.c
+++ b/block/bfq-iosched.c
@@ -34,9 +34,10 @@
* guarantee a low latency to non-I/O bound processes (the latter
* often belong to time-sensitive applications).
*
- * Even better for latency, BFQ explicitly privileges the I/O of
- * interactive applications, thereby providing these applications with
- * a very low latency.
+ * Even better for latency, BFQ explicitly privileges the I/O of two
+ * classes of time-sensitive applications: interactive and soft
+ * real-time. This feature enables BFQ to provide applications in
+ * these classes with a very low latency.
*
* With respect to the version of BFQ presented in [1], and in the
* papers cited therein, this implementation adds a hierarchical
@@ -93,6 +94,13 @@
#define BFQ_DEFAULT_GRP_IOPRIO 0
#define BFQ_DEFAULT_GRP_CLASS IOPRIO_CLASS_BE
+/*
+ * Soft real-time applications are extremely more latency sensitive
+ * than interactive ones. Over-raise the weight of the former to
+ * privilege them against the latter.
+ */
+#define BFQ_SOFTRT_WEIGHT_FACTOR 100
+
struct bfq_entity;
/**
@@ -288,6 +296,14 @@ struct bfq_queue {
/* current maximum weight-raising time for this queue */
unsigned long wr_cur_max_time;
/*
+ * Minimum time instant such that, only if a new request is
+ * enqueued after this time instant in an idle @bfq_queue with
+ * no outstanding requests, then the task associated with the
+ * queue it is deemed as soft real-time (see the comments on
+ * the function bfq_bfqq_softrt_next_start())
+ */
+ unsigned long soft_rt_next_start;
+ /*
* Start time of the current weight-raising period if
* the @bfq-queue is being weight-raised, otherwise
* finish time of the last weight-raising period.
@@ -295,6 +311,20 @@ struct bfq_queue {
unsigned long last_wr_start_finish;
/* factor by which the weight of this queue is multiplied */
unsigned int wr_coeff;
+ /*
+ * Time of the last transition of the @bfq_queue from idle to
+ * backlogged.
+ */
+ unsigned long last_idle_bklogged;
+ /*
+ * Cumulative service received from the @bfq_queue since the
+ * last transition from idle to backlogged.
+ */
+ unsigned long service_from_backlogged;
+ /*
+ * Value of wr start time when switching to soft rt
+ */
+ unsigned long wr_start_at_switch_to_srt;
};
/**
@@ -468,6 +498,9 @@ struct bfq_data {
unsigned int bfq_wr_coeff;
/* maximum duration of a weight-raising period (jiffies) */
unsigned int bfq_wr_max_time;
+
+ /* Maximum weight-raising duration for soft real-time processes */
+ unsigned int bfq_wr_rt_max_time;
/*
* Minimum idle period after which weight-raising may be
* reactivated for a queue (in jiffies).
@@ -479,6 +512,9 @@ struct bfq_data {
* queue (in jiffies).
*/
unsigned long bfq_wr_min_inter_arr_async;
+
+ /* Max service-rate for a soft real-time queue, in sectors/sec */
+ unsigned int bfq_wr_max_softrt_rate;
/*
* Cached value of the product R*T, used for computing the
* maximum duration of weight raising automatically.
@@ -507,6 +543,10 @@ enum bfqq_state_flags {
* having consumed at most 2/10 of
* its budget
*/
+ BFQ_BFQQ_FLAG_softrt_update, /*
+ * may need softrt-next-start
+ * update
+ */
};
#define BFQ_BFQQ_FNS(name) \
@@ -531,6 +571,7 @@ BFQ_BFQQ_FNS(fifo_expire);
BFQ_BFQQ_FNS(idle_window);
BFQ_BFQQ_FNS(sync);
BFQ_BFQQ_FNS(IO_bound);
+BFQ_BFQQ_FNS(softrt_update);
#undef BFQ_BFQQ_FNS
/* Logging facilities. */
@@ -3547,13 +3588,21 @@ static void bfq_update_bfqq_wr_on_rq_arrival(struct bfq_data *bfqd,
struct bfq_queue *bfqq,
unsigned int old_wr_coeff,
bool wr_or_deserves_wr,
- bool interactive)
+ bool interactive,
+ bool soft_rt)
{
if (old_wr_coeff == 1 && wr_or_deserves_wr) {
/* start a weight-raising period */
- bfqq->wr_coeff = bfqd->bfq_wr_coeff;
- /* update wr duration */
- bfqq->wr_cur_max_time = bfq_wr_duration(bfqd);
+ if (interactive) {
+ bfqq->wr_coeff = bfqd->bfq_wr_coeff;
+ bfqq->wr_cur_max_time = bfq_wr_duration(bfqd);
+ } else {
+ bfqq->wr_start_at_switch_to_srt = jiffies;
+ bfqq->wr_coeff = bfqd->bfq_wr_coeff *
+ BFQ_SOFTRT_WEIGHT_FACTOR;
+ bfqq->wr_cur_max_time =
+ bfqd->bfq_wr_rt_max_time;
+ }
/*
* If needed, further reduce budget to make sure it is
@@ -3568,8 +3617,51 @@ static void bfq_update_bfqq_wr_on_rq_arrival(struct bfq_data *bfqd,
bfqq->entity.budget,
2 * bfq_min_budget(bfqd));
} else if (old_wr_coeff > 1) {
- /* update wr duration */
- bfqq->wr_cur_max_time = bfq_wr_duration(bfqd);
+ if (interactive) { /* update wr coeff and duration */
+ bfqq->wr_coeff = bfqd->bfq_wr_coeff;
+ bfqq->wr_cur_max_time = bfq_wr_duration(bfqd);
+ } else if (soft_rt) {
+ /*
+ * The application is now or still meeting the
+ * requirements for being deemed soft rt. We
+ * can then correctly and safely (re)charge
+ * the weight-raising duration for the
+ * application with the weight-raising
+ * duration for soft rt applications.
+ *
+ * In particular, doing this recharge now, i.e.,
+ * before the weight-raising period for the
+ * application finishes, reduces the probability
+ * of the following negative scenario:
+ * 1) the weight of a soft rt application is
+ * raised at startup (as for any newly
+ * created application),
+ * 2) since the application is not interactive,
+ * at a certain time weight-raising is
+ * stopped for the application,
+ * 3) at that time the application happens to
+ * still have pending requests, and hence
+ * is destined to not have a chance to be
+ * deemed soft rt before these requests are
+ * completed (see the comments to the
+ * function bfq_bfqq_softrt_next_start()
+ * for details on soft rt detection),
+ * 4) these pending requests experience a high
+ * latency because the application is not
+ * weight-raised while they are pending.
+ */
+ if (bfqq->wr_cur_max_time !=
+ bfqd->bfq_wr_rt_max_time) {
+ bfqq->wr_start_at_switch_to_srt =
+ bfqq->last_wr_start_finish;
+
+ bfqq->wr_cur_max_time =
+ bfqd->bfq_wr_rt_max_time;
+ bfqq->wr_coeff = bfqd->bfq_wr_coeff *
+ BFQ_SOFTRT_WEIGHT_FACTOR;
+ }
+ bfqq->last_wr_start_finish = jiffies;
+ }
}
}
@@ -3588,7 +3680,7 @@ static void bfq_bfqq_handle_idle_busy_switch(struct bfq_data *bfqd,
struct request *rq,
bool *interactive)
{
- bool wr_or_deserves_wr, bfqq_wants_to_preempt,
+ bool soft_rt, wr_or_deserves_wr, bfqq_wants_to_preempt,
idle_for_long_time = bfq_bfqq_idle_for_long_time(bfqd, bfqq),
/*
* See the comments on
@@ -3605,12 +3697,14 @@ static void bfq_bfqq_handle_idle_busy_switch(struct bfq_data *bfqd,
/*
* bfqq deserves to be weight-raised if:
* - it is sync,
- * - it has been idle for enough time.
+ * - it has been idle for enough time or is soft real-time.
*/
+ soft_rt = bfqd->bfq_wr_max_softrt_rate > 0 &&
+ time_is_before_jiffies(bfqq->soft_rt_next_start);
*interactive = idle_for_long_time;
wr_or_deserves_wr = bfqd->low_latency &&
(bfqq->wr_coeff > 1 ||
- (bfq_bfqq_sync(bfqq) && *interactive));
+ (bfq_bfqq_sync(bfqq) && (*interactive || soft_rt)));
/*
* Using the last flag, update budget and check whether bfqq
@@ -3635,12 +3729,17 @@ static void bfq_bfqq_handle_idle_busy_switch(struct bfq_data *bfqd,
bfq_update_bfqq_wr_on_rq_arrival(bfqd, bfqq,
old_wr_coeff,
wr_or_deserves_wr,
- *interactive);
+ *interactive,
+ soft_rt);
if (old_wr_coeff != bfqq->wr_coeff)
bfqq->entity.prio_changed = 1;
}
+ bfqq->last_idle_bklogged = jiffies;
+ bfqq->service_from_backlogged = 0;
+ bfq_clear_bfqq_softrt_update(bfqq);
+
bfq_add_bfqq_busy(bfqd, bfqq);
/*
@@ -3654,7 +3753,7 @@ static void bfq_bfqq_handle_idle_busy_switch(struct bfq_data *bfqd,
* function bfq_bfqq_update_budg_for_activation).
*/
if (bfqd->in_service_queue && bfqq_wants_to_preempt &&
- bfqd->in_service_queue->wr_coeff == 1 &&
+ bfqd->in_service_queue->wr_coeff < bfqq->wr_coeff &&
next_queue_may_preempt(bfqd))
bfq_bfqq_expire(bfqd, bfqd->in_service_queue,
false, BFQ_BFQQ_PREEMPTED);
@@ -3717,6 +3816,12 @@ static void bfq_add_request(struct request *rq)
* period must start or restart (this case is considered
* separately because it is not detected by the above
* conditions, if bfqq is already weight-raised)
+ *
+ * last_wr_start_finish has to be updated also if bfqq is soft
+ * real-time, because the weight-raising period is constantly
+ * restarted on idle-to-busy transitions for these queues, but
+ * this is already done in bfq_bfqq_handle_idle_busy_switch if
+ * needed.
*/
if (bfqd->low_latency &&
(old_wr_coeff == 1 || bfqq->wr_coeff == 1 || interactive))
@@ -3900,6 +4005,7 @@ static void bfq_bfqq_end_wr(struct bfq_queue *bfqq)
{
bfqq->wr_coeff = 1;
bfqq->wr_cur_max_time = 0;
+ bfqq->last_wr_start_finish = jiffies;
/*
* Trigger a weight change on the next invocation of
* __bfq_entity_update_weight_prio.
@@ -3977,11 +4083,17 @@ static int bfq_allow_rq_merge(struct request_queue *q, struct request *rq,
static void bfq_set_budget_timeout(struct bfq_data *bfqd,
struct bfq_queue *bfqq)
{
+ unsigned int timeout_coeff;
+
+ if (bfqq->wr_cur_max_time == bfqd->bfq_wr_rt_max_time)
+ timeout_coeff = 1;
+ else
+ timeout_coeff = bfqq->entity.weight / bfqq->entity.orig_weight;
+
bfqd->last_budget_start = ktime_get();
bfqq->budget_timeout = jiffies +
- bfqd->bfq_timeout *
- (bfqq->entity.weight / bfqq->entity.orig_weight);
+ bfqd->bfq_timeout * timeout_coeff;
}
static void __bfq_set_in_service_queue(struct bfq_data *bfqd,
@@ -3994,6 +4106,42 @@ static void __bfq_set_in_service_queue(struct bfq_data *bfqd,
bfqd->budgets_assigned = (bfqd->budgets_assigned*7 + 256) / 8;
+ if (time_is_before_jiffies(bfqq->last_wr_start_finish) &&
+ bfqq->wr_coeff > 1 &&
+ bfqq->wr_cur_max_time == bfqd->bfq_wr_rt_max_time &&
+ time_is_before_jiffies(bfqq->budget_timeout)) {
+ /*
+ * For soft real-time queues, move the start
+ * of the weight-raising period forward by the
+ * time the queue has not received any
+ * service. Otherwise, a relatively long
+ * service delay is likely to cause the
+ * weight-raising period of the queue to end,
+ * because of the short duration of the
+ * weight-raising period of a soft real-time
+ * queue. It is worth noting that this move
+ * is not so dangerous for the other queues,
+ * because soft real-time queues are not
+ * greedy.
+ *
+ * To not add a further variable, we use the
+ * overloaded field budget_timeout to
+ * determine for how long the queue has not
+ * received service, i.e., how much time has
+ * elapsed since the queue expired. However,
+ * this is a little imprecise, because
+ * budget_timeout is set to jiffies if bfqq
+ * not only expires, but also remains with no
+ * request.
+ */
+ if (time_after(bfqq->budget_timeout,
+ bfqq->last_wr_start_finish))
+ bfqq->last_wr_start_finish +=
+ jiffies - bfqq->budget_timeout;
+ else
+ bfqq->last_wr_start_finish = jiffies;
+ }
+
bfq_set_budget_timeout(bfqd, bfqq);
bfq_log_bfqq(bfqd, bfqq,
"set_in_service_queue, cur-budget = %d",
@@ -4627,6 +4775,76 @@ static bool bfq_bfqq_is_slow(struct bfq_data *bfqd, struct bfq_queue *bfqq,
}
/*
+ * To be deemed as soft real-time, an application must meet two
+ * requirements. First, the application must not require an average
+ * bandwidth higher than the approximate bandwidth required to playback or
+ * record a compressed high-definition video.
+ * The next function is invoked on the completion of the last request of a
+ * batch, to compute the next-start time instant, soft_rt_next_start, such
+ * that, if the next request of the application does not arrive before
+ * soft_rt_next_start, then the above requirement on the bandwidth is met.
+ *
+ * The second requirement is that the request pattern of the application is
+ * isochronous, i.e., that, after issuing a request or a batch of requests,
+ * the application stops issuing new requests until all its pending requests
+ * have been completed. After that, the application may issue a new batch,
+ * and so on.
+ * For this reason the next function is invoked to compute
+ * soft_rt_next_start only for applications that meet this requirement,
+ * whereas soft_rt_next_start is set to infinity for applications that do
+ * not.
+ *
+ * Unfortunately, even a greedy application may happen to behave in an
+ * isochronous way if the CPU load is high. In fact, the application may
+ * stop issuing requests while the CPUs are busy serving other processes,
+ * then restart, then stop again for a while, and so on. In addition, if
+ * the disk achieves a low enough throughput with the request pattern
+ * issued by the application (e.g., because the request pattern is random
+ * and/or the device is slow), then the application may meet the above
+ * bandwidth requirement too. To prevent such a greedy application to be
+ * deemed as soft real-time, a further rule is used in the computation of
+ * soft_rt_next_start: soft_rt_next_start must be higher than the current
+ * time plus the maximum time for which the arrival of a request is waited
+ * for when a sync queue becomes idle, namely bfqd->bfq_slice_idle.
+ * This filters out greedy applications, as the latter issue instead their
+ * next request as soon as possible after the last one has been completed
+ * (in contrast, when a batch of requests is completed, a soft real-time
+ * application spends some time processing data).
+ *
+ * Unfortunately, the last filter may easily generate false positives if
+ * only bfqd->bfq_slice_idle is used as a reference time interval and one
+ * or both the following cases occur:
+ * 1) HZ is so low that the duration of a jiffy is comparable to or higher
+ * than bfqd->bfq_slice_idle. This happens, e.g., on slow devices with
+ * HZ=100.
+ * 2) jiffies, instead of increasing at a constant rate, may stop increasing
+ * for a while, then suddenly 'jump' by several units to recover the lost
+ * increments. This seems to happen, e.g., inside virtual machines.
+ * To address this issue, we do not use as a reference time interval just
+ * bfqd->bfq_slice_idle, but bfqd->bfq_slice_idle plus a few jiffies. In
+ * particular we add the minimum number of jiffies for which the filter
+ * seems to be quite precise also in embedded systems and KVM/QEMU virtual
+ * machines.
+ */
+static unsigned long bfq_bfqq_softrt_next_start(struct bfq_data *bfqd,
+ struct bfq_queue *bfqq)
+{
+ return max(bfqq->last_idle_bklogged +
+ HZ * bfqq->service_from_backlogged /
+ bfqd->bfq_wr_max_softrt_rate,
+ jiffies + nsecs_to_jiffies(bfqq->bfqd->bfq_slice_idle) + 4);
+}
+
+/*
+ * Return the farthest future time instant according to jiffies
+ * macros.
+ */
+static unsigned long bfq_greatest_from_now(void)
+{
+ return jiffies + MAX_JIFFY_OFFSET;
+}
+
+/*
* Return the farthest past time instant according to jiffies
* macros.
*/
@@ -4676,6 +4894,17 @@ static void bfq_bfqq_expire(struct bfq_data *bfqd,
slow = bfq_bfqq_is_slow(bfqd, bfqq, compensate, reason, &delta);
/*
+ * Increase service_from_backlogged before next statement,
+ * because the possible next invocation of
+ * bfq_bfqq_charge_time would likely inflate
+ * entity->service. In contrast, service_from_backlogged must
+ * contain real service, to enable the soft real-time
+ * heuristic to correctly compute the bandwidth consumed by
+ * bfqq.
+ */
+ bfqq->service_from_backlogged += entity->service;
+
+ /*
* As above explained, charge slow (typically seeky) and
* timed-out queues with the time and not the service
* received, to favor sequential workloads.
@@ -4703,6 +4932,48 @@ static void bfq_bfqq_expire(struct bfq_data *bfqd,
if (bfqd->low_latency && bfqq->wr_coeff == 1)
bfqq->last_wr_start_finish = jiffies;
+ if (bfqd->low_latency && bfqd->bfq_wr_max_softrt_rate > 0 &&
+ RB_EMPTY_ROOT(&bfqq->sort_list)) {
+ /*
+ * If we get here, and there are no outstanding
+ * requests, then the request pattern is isochronous
+ * (see the comments on the function
+ * bfq_bfqq_softrt_next_start()). Thus we can compute
+ * soft_rt_next_start. If, instead, the queue still
+ * has outstanding requests, then we have to wait for
+ * the completion of all the outstanding requests to
+ * discover whether the request pattern is actually
+ * isochronous.
+ */
+ if (bfqq->dispatched == 0)
+ bfqq->soft_rt_next_start =
+ bfq_bfqq_softrt_next_start(bfqd, bfqq);
+ else {
+ /*
+ * The application is still waiting for the
+ * completion of one or more requests:
+ * prevent it from possibly being incorrectly
+ * deemed as soft real-time by setting its
+ * soft_rt_next_start to infinity. In fact,
+ * without this assignment, the application
+ * would be incorrectly deemed as soft
+ * real-time if:
+ * 1) it issued a new request before the
+ * completion of all its in-flight
+ * requests, and
+ * 2) at that time, its soft_rt_next_start
+ * happened to be in the past.
+ */
+ bfqq->soft_rt_next_start =
+ bfq_greatest_from_now();
+ /*
+ * Schedule an update of soft_rt_next_start to when
+ * the task may be discovered to be isochronous.
+ */
+ bfq_mark_bfqq_softrt_update(bfqq);
+ }
+ }
+
bfq_log_bfqq(bfqd, bfqq,
"expire (%d, slow %d, num_disp %d, idle_win %d)", reason,
slow, bfqq->dispatched, bfq_bfqq_idle_window(bfqq));
@@ -4999,12 +5270,18 @@ static void bfq_update_wr_data(struct bfq_data *bfqd, struct bfq_queue *bfqq)
*/
if (time_is_before_jiffies(bfqq->last_wr_start_finish +
bfqq->wr_cur_max_time)) {
- bfqq->last_wr_start_finish = jiffies;
- bfq_log_bfqq(bfqd, bfqq,
- "wrais ending at %lu, rais_max_time %u",
- bfqq->last_wr_start_finish,
- jiffies_to_msecs(bfqq->wr_cur_max_time));
- bfq_bfqq_end_wr(bfqq);
+ if (bfqq->wr_cur_max_time != bfqd->bfq_wr_rt_max_time ||
+ time_is_before_jiffies(bfqq->wr_start_at_switch_to_srt +
+ bfq_wr_duration(bfqd)))
+ bfq_bfqq_end_wr(bfqq);
+ else {
+ /* switch back to interactive wr */
+ bfqq->wr_coeff = bfqd->bfq_wr_coeff;
+ bfqq->wr_cur_max_time = bfq_wr_duration(bfqd);
+ bfqq->last_wr_start_finish =
+ bfqq->wr_start_at_switch_to_srt;
+ bfqq->entity.prio_changed = 1;
+ }
}
}
/* Update weight both if it must be raised and if it must be lowered */
@@ -5338,6 +5615,13 @@ static void bfq_init_bfqq(struct bfq_data *bfqd, struct bfq_queue *bfqq,
bfqq->wr_coeff = 1;
bfqq->last_wr_start_finish = bfq_smallest_from_now();
+ bfqq->wr_start_at_switch_to_srt = bfq_smallest_from_now();
+
+ /*
+ * Set to the value for which bfqq will not be deemed as
+ * soft rt when it becomes backlogged.
+ */
+ bfqq->soft_rt_next_start = bfq_greatest_from_now();
/* first request is almost certainly seeky */
bfqq->seek_history = 1;
@@ -5655,6 +5939,20 @@ static void bfq_completed_request(struct request_queue *q, struct request *rq)
bfqd->last_completion = now_ns;
/*
+ * If we are waiting to discover whether the request pattern
+ * of the task associated with the queue is actually
+ * isochronous, and both requisites for this condition to hold
+ * are now satisfied, then compute soft_rt_next_start (see the
+ * comments on the function bfq_bfqq_softrt_next_start()). We
+ * schedule this delayed check when bfqq expires, if it still
+ * has in-flight requests.
+ */
+ if (bfq_bfqq_softrt_update(bfqq) && bfqq->dispatched == 0 &&
+ RB_EMPTY_ROOT(&bfqq->sort_list))
+ bfqq->soft_rt_next_start =
+ bfq_bfqq_softrt_next_start(bfqd, bfqq);
+
+ /*
* If this is the in-service queue, check if it needs to be expired,
* or if we want to idle in case it has no pending requests.
*/
@@ -6006,9 +6304,16 @@ static int bfq_init_queue(struct request_queue *q, struct elevator_type *e)
* Trade-off between responsiveness and fairness.
*/
bfqd->bfq_wr_coeff = 30;
+ bfqd->bfq_wr_rt_max_time = msecs_to_jiffies(300);
bfqd->bfq_wr_max_time = 0;
bfqd->bfq_wr_min_idle_time = msecs_to_jiffies(2000);
bfqd->bfq_wr_min_inter_arr_async = msecs_to_jiffies(500);
+ bfqd->bfq_wr_max_softrt_rate = 7000; /*
+ * Approximate rate required
+ * to playback or record a
+ * high-definition compressed
+ * video.
+ */
/*
* Begin by assuming, optimistically, that the device is a
@@ -6132,9 +6437,11 @@ SHOW_FUNCTION(bfq_timeout_sync_show, bfqd->bfq_timeout, 1);
SHOW_FUNCTION(bfq_strict_guarantees_show, bfqd->strict_guarantees, 0);
SHOW_FUNCTION(bfq_low_latency_show, bfqd->low_latency, 0);
SHOW_FUNCTION(bfq_wr_coeff_show, bfqd->bfq_wr_coeff, 0);
+SHOW_FUNCTION(bfq_wr_rt_max_time_show, bfqd->bfq_wr_rt_max_time, 1);
SHOW_FUNCTION(bfq_wr_min_idle_time_show, bfqd->bfq_wr_min_idle_time, 1);
SHOW_FUNCTION(bfq_wr_min_inter_arr_async_show, bfqd->bfq_wr_min_inter_arr_async,
1);
+SHOW_FUNCTION(bfq_wr_max_softrt_rate_show, bfqd->bfq_wr_max_softrt_rate, 0);
#undef SHOW_FUNCTION
#define USEC_SHOW_FUNCTION(__FUNC, __VAR) \
@@ -6177,10 +6484,14 @@ STORE_FUNCTION(bfq_back_seek_penalty_store, &bfqd->bfq_back_penalty, 1,
STORE_FUNCTION(bfq_slice_idle_store, &bfqd->bfq_slice_idle, 0, INT_MAX, 2);
STORE_FUNCTION(bfq_wr_coeff_store, &bfqd->bfq_wr_coeff, 1, INT_MAX, 0);
STORE_FUNCTION(bfq_wr_max_time_store, &bfqd->bfq_wr_max_time, 0, INT_MAX, 1);
+STORE_FUNCTION(bfq_wr_rt_max_time_store, &bfqd->bfq_wr_rt_max_time, 0, INT_MAX,
+ 1);
STORE_FUNCTION(bfq_wr_min_idle_time_store, &bfqd->bfq_wr_min_idle_time, 0,
INT_MAX, 1);
STORE_FUNCTION(bfq_wr_min_inter_arr_async_store,
&bfqd->bfq_wr_min_inter_arr_async, 0, INT_MAX, 1);
+STORE_FUNCTION(bfq_wr_max_softrt_rate_store, &bfqd->bfq_wr_max_softrt_rate, 0,
+ INT_MAX, 0);
#undef STORE_FUNCTION
#define USEC_STORE_FUNCTION(__FUNC, __PTR, MIN, MAX) \
@@ -6300,8 +6611,10 @@ static struct elv_fs_entry bfq_attrs[] = {
BFQ_ATTR(low_latency),
BFQ_ATTR(wr_coeff),
BFQ_ATTR(wr_max_time),
+ BFQ_ATTR(wr_rt_max_time),
BFQ_ATTR(wr_min_idle_time),
BFQ_ATTR(wr_min_inter_arr_async),
+ BFQ_ATTR(wr_max_softrt_rate),
BFQ_ATTR(weights),
__ATTR_NULL
};
@@ -6359,7 +6672,7 @@ static struct blkcg_policy blkcg_policy_bfq = {
static int __init bfq_init(void)
{
int ret;
- char msg[50] = "BFQ I/O-scheduler: v1";
+ char msg[50] = "BFQ I/O-scheduler: v2";
#ifdef CONFIG_BFQ_GROUP_IOSCHED
ret = blkcg_policy_register(&blkcg_policy_bfq);
--
2.10.0
[toc] | [prev] | [next] | [standalone]
| From | Christoph Hellwig <hch@infradead.org> |
|---|---|
| Date | 2016-10-26 12:30 +0200 |
| Subject | Re: [PATCH 00/14] introduce the BFQ-v0 I/O scheduler as an extra scheduler |
| Message-ID | <swtD4-2ly-25@gated-at.bofh.it> |
| In reply to | #1508990 |
Just as last time: big NAK for introducing giant new infrastructure like a new I/O scheduler for the legacy request structure. Please direct your engergy towards blk-mq instead.
[toc] | [prev] | [next] | [standalone]
| From | Jan Kara <jack@suse.cz> |
|---|---|
| Date | 2016-10-26 13:40 +0200 |
| Subject | Re: [PATCH 00/14] introduce the BFQ-v0 I/O scheduler as an extra scheduler |
| Message-ID | <swuIN-2Z9-7@gated-at.bofh.it> |
| In reply to | #1509038 |
On Wed 26-10-16 03:19:03, Christoph Hellwig wrote: > Just as last time: > > big NAK for introducing giant new infrastructure like a new I/O scheduler > for the legacy request structure. > > Please direct your engergy towards blk-mq instead. Christoph, we will probably talk about this next week but IMO rotating disks and SATA based SSDs are going to stay with us for another 15 years, likely more. For them blk-mq is no win, relatively complex IO scheduling like CFQ or BFQ does is a big win for them in some cases. So I think IO scheduling (and thus place for something like BFQ) is going to stay with us for quite a long time still. So are we going to add hooks in blk-mq to support full-blown IO scheduling at least for single queue devices? Or how else do we want to support that HW? Honza -- Jan Kara <jack@suse.com> SUSE Labs, CR
[toc] | [prev] | [next] | [standalone]
| From | Arnd Bergmann <arnd@arndb.de> |
|---|---|
| Date | 2016-10-26 17:20 +0200 |
| Message-ID | <swy9I-5BD-17@gated-at.bofh.it> |
| In reply to | #1509103 |
On Wednesday, October 26, 2016 8:05:11 AM CEST Bart Van Assche wrote: > On 10/26/2016 04:34 AM, Jan Kara wrote: > > On Wed 26-10-16 03:19:03, Christoph Hellwig wrote: > >> Just as last time: > >> > >> big NAK for introducing giant new infrastructure like a new I/O scheduler > >> for the legacy request structure. > >> > >> Please direct your engergy towards blk-mq instead. > > > > Christoph, we will probably talk about this next week but IMO rotating > > disks and SATA based SSDs are going to stay with us for another 15 years, > > likely more. For them blk-mq is no win, relatively complex IO scheduling > > like CFQ or BFQ does is a big win for them in some cases. So I think IO > > scheduling (and thus place for something like BFQ) is going to stay with us > > for quite a long time still. So are we going to add hooks in blk-mq to > > support full-blown IO scheduling at least for single queue devices? Or how > > else do we want to support that HW? > > Hello Jan, > > Having two versions (one for non-blk-mq, one for blk-mq) of every I/O > scheduler would be a maintenance nightmare. Has anyone already analyzed > whether it would be possible to come up with an API for I/O schedulers > that makes it possible to use the same I/O scheduler for both blk-mq and > the traditional block layer? The question to ask first is whether to actually have pluggable schedulers on blk-mq at all, or just have one that is meant to do the right thing in every case (and possibly can be bypassed completely). Arnd
[toc] | [prev] | [next] | [standalone]
| From | Christoph Hellwig <hch@infradead.org> |
|---|---|
| Date | 2016-10-26 17:40 +0200 |
| Subject | Re: [PATCH 00/14] introduce the BFQ-v0 I/O scheduler as an extra scheduler |
| Message-ID | <swyt4-5IE-9@gated-at.bofh.it> |
| In reply to | #1509524 |
On Wed, Oct 26, 2016 at 05:13:07PM +0200, Arnd Bergmann wrote: > The question to ask first is whether to actually have pluggable > schedulers on blk-mq at all, or just have one that is meant to > do the right thing in every case (and possibly can be bypassed > completely). That would be my preference. Have a BFQ-variant for blk-mq as an option (default to off unless opted in by the driver or user), and not other scheduler for blk-mq. Don't bother with bfq for non blk-mq. It's not like there is any advantage in the legacy-request device even for slow devices, except for the option of having I/O scheduling.
[toc] | [prev] | [next] | [standalone]
| From | Jens Axboe <axboe@kernel.dk> |
|---|---|
| Date | 2016-10-26 17:40 +0200 |
| Subject | Re: [PATCH 00/14] introduce the BFQ-v0 I/O scheduler as an extra scheduler |
| Message-ID | <swyt4-5IE-23@gated-at.bofh.it> |
| In reply to | #1509532 |
On 10/26/2016 09:29 AM, Christoph Hellwig wrote: > On Wed, Oct 26, 2016 at 05:13:07PM +0200, Arnd Bergmann wrote: >> The question to ask first is whether to actually have pluggable >> schedulers on blk-mq at all, or just have one that is meant to >> do the right thing in every case (and possibly can be bypassed >> completely). > > That would be my preference. Have a BFQ-variant for blk-mq as an > option (default to off unless opted in by the driver or user), and > not other scheduler for blk-mq. Don't bother with bfq for non > blk-mq. It's not like there is any advantage in the legacy-request > device even for slow devices, except for the option of having I/O > scheduling. It's the only right way forward. blk-mq might not offer any substantial advantages to rotating storage, but with scheduling, it won't offer a downside either. And it'll take us towards the real goal, which is to have just one IO path. Adding a new scheduler for the legacy IO path makes no sense. Adding one for blk-mq and phasing out the old path is what we need to do. -- Jens Axboe
[toc] | [prev] | [next] | [standalone]
| From | Paolo Valente <paolo.valente@linaro.org> |
|---|---|
| Date | 2016-10-26 18:10 +0200 |
| Message-ID | <swyW6-6ba-45@gated-at.bofh.it> |
| In reply to | #1509534 |
> Il giorno 26 ott 2016, alle ore 17:32, Jens Axboe <axboe@kernel.dk> ha scritto: > > On 10/26/2016 09:29 AM, Christoph Hellwig wrote: >> On Wed, Oct 26, 2016 at 05:13:07PM +0200, Arnd Bergmann wrote: >>> The question to ask first is whether to actually have pluggable >>> schedulers on blk-mq at all, or just have one that is meant to >>> do the right thing in every case (and possibly can be bypassed >>> completely). >> >> That would be my preference. Have a BFQ-variant for blk-mq as an >> option (default to off unless opted in by the driver or user), and >> not other scheduler for blk-mq. Don't bother with bfq for non >> blk-mq. It's not like there is any advantage in the legacy-request >> device even for slow devices, except for the option of having I/O >> scheduling. > > It's the only right way forward. blk-mq might not offer any substantial > advantages to rotating storage, but with scheduling, it won't offer a > downside either. And it'll take us towards the real goal, which is to > have just one IO path. ok > Adding a new scheduler for the legacy IO path > makes no sense. I would fully agree if effective and stable I/O scheduling would be available in blk-mq in one or two months. But I guess that it will take at least one year optimistically, given the current status of the needed infrastructure, and given the great difficulties of doing effective scheduling at the high parallelism and extreme target speeds of blk-mq. Of course, this holds true unless little clever scheduling is performed. So, what's the point in forcing a lot of users wait another year or more, for a solution that has yet to be even defined, while they could enjoy a much better system, and then switch an even better system when scheduling is ready in blk-mq too? For example, currently, opening a terminal on a 50KIOPS SSD with cfq, deadline or noop, if there happens to be some background workload, takes *more* time than opening the same terminal on a 1KIOPS HDD with the same background workload, but with BFQ. Does this make any sense? > Adding one for blk-mq and phasing out the old path is > what we need to do. > Yes, as the ultimate goal. Thanks, Paolo > -- > Jens Axboe >
[toc] | [prev] | [next] | [standalone]
| From | Jens Axboe <axboe@kernel.dk> |
|---|---|
| Date | 2016-10-26 18:20 +0200 |
| Subject | Re: [PATCH 00/14] introduce the BFQ-v0 I/O scheduler as an extra scheduler |
| Message-ID | <swz5Q-6fE-11@gated-at.bofh.it> |
| In reply to | #1509574 |
On 10/26/2016 10:04 AM, Paolo Valente wrote: > >> Il giorno 26 ott 2016, alle ore 17:32, Jens Axboe <axboe@kernel.dk> ha scritto: >> >> On 10/26/2016 09:29 AM, Christoph Hellwig wrote: >>> On Wed, Oct 26, 2016 at 05:13:07PM +0200, Arnd Bergmann wrote: >>>> The question to ask first is whether to actually have pluggable >>>> schedulers on blk-mq at all, or just have one that is meant to >>>> do the right thing in every case (and possibly can be bypassed >>>> completely). >>> >>> That would be my preference. Have a BFQ-variant for blk-mq as an >>> option (default to off unless opted in by the driver or user), and >>> not other scheduler for blk-mq. Don't bother with bfq for non >>> blk-mq. It's not like there is any advantage in the legacy-request >>> device even for slow devices, except for the option of having I/O >>> scheduling. >> >> It's the only right way forward. blk-mq might not offer any substantial >> advantages to rotating storage, but with scheduling, it won't offer a >> downside either. And it'll take us towards the real goal, which is to >> have just one IO path. > > ok > >> Adding a new scheduler for the legacy IO path >> makes no sense. > > I would fully agree if effective and stable I/O scheduling would be > available in blk-mq in one or two months. But I guess that it will > take at least one year optimistically, given the current status of the > needed infrastructure, and given the great difficulties of doing > effective scheduling at the high parallelism and extreme target speeds > of blk-mq. Of course, this holds true unless little clever scheduling > is performed. > > So, what's the point in forcing a lot of users wait another year or > more, for a solution that has yet to be even defined, while they could > enjoy a much better system, and then switch an even better system when > scheduling is ready in blk-mq too? That same argument could have been made 2 years ago. Saying no to a new scheduler for the legacy framework goes back roughly that long. We could have had BFQ for mq NOW, if we didn't keep coming back to this very point. I'm hesistant to add a new scheduler because it's very easy to add, very difficult to get rid of. If we do add BFQ as a legacy scheduler now, it'll take us years and years to get rid of it again. We should be moving towards LESS moving parts in the legacy path, not more. We can keep having this discussion every few years, but I think we'd both prefer to make some actual progress here. It's perfectly fine to add an interface for a single queue interface for an IO scheduler for blk-mq, since we don't care too much about scalability there. And that won't take years, that should be a few weeks. Retrofitting BFQ on top of that should not be hard either. That can co-exist with a real multiqueue scheduler as well, something that's geared towards some fairness for faster devices. -- Jens Axboe
[toc] | [prev] | [next] | [standalone]
| From | Paolo Valente <paolo.valente@linaro.org> |
|---|---|
| Date | 2016-10-26 14:50 +0200 |
| Message-ID | <swvOz-3Ml-89@gated-at.bofh.it> |
| In reply to | #1509038 |
> Il giorno 26 ott 2016, alle ore 12:19, Christoph Hellwig <hch@infradead.org> ha scritto: > > Just as last time: > > big NAK for introducing giant new infrastructure like a new I/O scheduler > for the legacy request structure. > I would fully agree, if there weren't important problems involved. But there are. Linux has been suffering for years from responsiveness and latency problems, related to I/O (and I/O bandwidth fairness is still just not available). Users are not happy about that. BFQ apparently solves these problems in most scenarios. Adding BFQ would not be disruptive for any use case. People could just try it if they want, and check whether things get better. IMO these problems are more important than the clear code- maintenance issue you raise. > Please direct your engergy towards blk-mq instead. Definitely. I would really like to help. To this purpose, I have already tried to stimulate discussion, as well offer and ask for help [1]. And I think that addressing these latency problems (and not only) is even more important with blk-mq. In fact, with blk-mq, they get worse, as no I/O scheduler is available yet. Thanks, Paolo [1] http://www.spinics.net/lists/linux-block/msg04555.html > -- > To unsubscribe from this list: send the line "unsubscribe linux-block" in > the body of a message to majordomo@vger.kernel.org > More majordomo info at http://vger.kernel.org/majordomo-info.html
[toc] | [prev] | [standalone]
Back to top | Article view | linux.kernel
csiph-web