Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > linux.kernel > #1451384 > unrolled thread
| Started by | Paolo Valente <paolo.valente@linaro.org> |
|---|---|
| First post | 2016-07-27 18:20 +0200 |
| Last post | 2016-07-28 19:00 +0200 |
| Articles | 17 — 2 participants |
Back to article view | Back to linux.kernel
This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by
below is the oldest one visible, not the original post.
[PATCH RFC V8 00/22] Replace the CFQ I/O Scheduler with BFQ Paolo Valente <paolo.valente@linaro.org> - 2016-07-27 18:20 +0200
[PATCH RFC V8 12/22] block, bfq: modify the peak-rate estimator Paolo Valente <paolo.valente@linaro.org> - 2016-07-27 18:20 +0200
[PATCH RFC V8 04/22] block, cfq: remove SSD-related logic Paolo Valente <paolo.valente@linaro.org> - 2016-07-27 18:20 +0200
[PATCH RFC V8 17/22] block, bfq: reduce latency during request-pool saturation Paolo Valente <paolo.valente@linaro.org> - 2016-07-27 18:20 +0200
[PATCH RFC V8 13/22] block, bfq: add more fairness with writes and slow processes Paolo Valente <paolo.valente@linaro.org> - 2016-07-27 18:20 +0200
[PATCH RFC V8 08/22] block, cfq: get rid of latency tunables Paolo Valente <paolo.valente@linaro.org> - 2016-07-27 18:20 +0200
[PATCH RFC V8 20/22] block, bfq: boost the throughput on NCQ-capable flash-based devices Paolo Valente <paolo.valente@linaro.org> - 2016-07-27 18:20 +0200
[PATCH RFC V8 19/22] block, bfq: reduce idling only in symmetric scenarios Paolo Valente <paolo.valente@linaro.org> - 2016-07-27 18:20 +0200
[PATCH RFC V8 22/22] block, bfq: handle bursts of queue activations Paolo Valente <paolo.valente@linaro.org> - 2016-07-27 18:20 +0200
[PATCH RFC V8 16/22] block, bfq: preserve a low latency also with NCQ-capable drives Paolo Valente <paolo.valente@linaro.org> - 2016-07-27 18:20 +0200
[PATCH RFC V8 11/22] block, bfq: improve throughput boosting Paolo Valente <paolo.valente@linaro.org> - 2016-07-27 18:20 +0200
[PATCH RFC V8 15/22] block, bfq: reduce I/O latency for soft real-time applications Paolo Valente <paolo.valente@linaro.org> - 2016-07-27 18:20 +0200
[PATCH RFC V8 02/22] block, cfq: remove close-based preemption Paolo Valente <paolo.valente@linaro.org> - 2016-07-27 18:20 +0200
[PATCH RFC V8 21/22] block, bfq: boost the throughput with random I/O on NCQ-capable HDDs Paolo Valente <paolo.valente@linaro.org> - 2016-07-27 18:20 +0200
[PATCH RFC V8 18/22] block, bfq: add Early Queue Merge (EQM) Paolo Valente <paolo.valente@linaro.org> - 2016-07-27 18:20 +0200
[PATCH RFC V8 07/22] block, cfq: get rid of workload type Paolo Valente <paolo.valente@linaro.org> - 2016-07-27 18:20 +0200
Re: [PATCH RFC V8 00/22] Replace the CFQ I/O Scheduler with BFQ Paolo <paolo.valente@linaro.org> - 2016-07-28 19:00 +0200
| From | Paolo Valente <paolo.valente@linaro.org> |
|---|---|
| Date | 2016-07-27 18:20 +0200 |
| Subject | [PATCH RFC V8 00/22] Replace the CFQ I/O Scheduler with BFQ |
| Message-ID | <rZzIR-1FV-3@gated-at.bofh.it> |
Hi,
this new version of the patchset contains all the improvements and bug
fixes recommended by Tejun [7], plus new features of BFQ-v8. Details
about old and new features in patch descriptions. For your
convenience, here is the usual description of the overall patchset.
This patchset replaces CFQ with the last version of BFQ (which is a
proportional-share I/O scheduler). To make a smooth transition, this
patchset first brings CFQ back to its state at the time when BFQ was
forked from CFQ. Basically, this reduces CFQ to its engine, by
removing every heuristic and improvement that has nothing to do with
any heuristic or improvement in BFQ, and every heuristic and
improvement whose goal is achieved in a different way in BFQ. Then,
the second part of the patchset starts by replacing CFQ's engine with
BFQ's engine, and goes on by adding current BFQ improvements and extra
heuristics. Here is the thread in which we agreed on both this first
step, and the second and last step: [1]. Moreover, here is a direct
link to the email describing both steps: [2].
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.
Turning back to BFQ, its first version was submitted a few years ago
[3]. It is denoted as v0 in this patchset, to distinguish it from the
version I am submitting now, v8. In particular, the first two
patches concerned with BFQ introduce BFQ-v0, whereas the remaining
patches turn progressively BFQ-v0 into BFQ-v8. Here are some nice
features of BFQ-v8.
Low latency for interactive applications
According to our results, and regardless of the actual background
workload, 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 or written,
- 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.
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 half of the
parallel workloads considered in our tests. With the rest of the
workloads, and with all the workloads on flash-based devices, BFQ
achieves instead about the same throughput as the other schedulers.
Strong fairness guarantees (already provided by BFQ-v0)
As for long-term guarantees, BFQ distributes the device throughput
(and not just the device time) as desired among I/O-bound
applications, with any workload and regardless of the device
parameters.
BFQ achieves the above service properties thanks to the combination of
its accurate scheduling engine (patches 9-10), and a set of simple
heuristics and improvements (patches 11-22). 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 [4].
What BFQ can do in practice is shown, e.g., in this 8-minute demo with
an SSD: [5]. 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 [6],
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., 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.
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 [6] 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/2014/5/27/314
[2] https://lists.linux-foundation.org/pipermail/containers/2014-June/034704.html
[3] https://lkml.org/lkml/2008/4/1/234
[4] 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
[5] https://youtu.be/1cjZeaCXIyM
[6] http://algogroup.unimore.it/people/paolo/disk_sched/results.php
[7] https://lkml.org/lkml/2016/2/1/818
Arianna Avanzini (11):
block, cfq: remove queue merging for close cooperators
block, cfq: remove close-based preemption
block, cfq: remove deep seek queues logic
block, cfq: remove SSD-related logic
block, cfq: get rid of hierarchical support
block, cfq: get rid of queue preemption
block, cfq: get rid of workload type
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
Fabio Checconi (1):
block, cfq: replace CFQ with the BFQ-v0 I/O scheduler
Paolo Valente (10):
block, cfq: get rid of latency tunables
block, bfq: improve throughput boosting
block, bfq: modify the peak-rate estimator
block, bfq: add more fairness with writes and slow processes
block, bfq: improve responsiveness
block, bfq: reduce I/O latency for soft real-time applications
block, bfq: preserve a low latency also with NCQ-capable drives
block, bfq: reduce latency during request-pool saturation
block, bfq: boost the throughput on NCQ-capable flash-based devices
block, bfq: boost the throughput with random I/O on NCQ-capable HDDs
block/Kconfig.iosched | 19 +-
block/cfq-iosched.c | 10173 +++++++++++++++++++++++++++++++-----------------
2 files changed, 6610 insertions(+), 3582 deletions(-)
--
1.9.1
[toc] | [next] | [standalone]
| From | Paolo Valente <paolo.valente@linaro.org> |
|---|---|
| Date | 2016-07-27 18:20 +0200 |
| Subject | [PATCH RFC V8 12/22] block, bfq: modify the peak-rate estimator |
| Message-ID | <rZzIS-1FV-17@gated-at.bofh.it> |
| In reply to | #1451384 |
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.
To filter out spikes, the estimated peak rate is updated only on the
expiration of queues that have been served for a long-enough time. As
a first step, the estimator computes the device rate, R_meas, during
the service of the queue. After that, if R_est < R_meas, then R_est is
set to R_meas.
Unfortunately, our experiments highlighted the following two
problems. First, because of ZBR, depending on the locality of the
workload, the estimator may easily converge to a value that is
appropriate only for part of a disk. Second, R_est may jump (and
remain forever equal) to a much higher value than the actual device
peak rate, in case of hits in the drive cache, which may let sectors
be transferred in practice at bus rate.
To try to converge to the actual average peak rate over the disk
surface (in case of rotational devices), and to smooth the spikes
caused by the drive cache, this patch changes the estimator as
follows. In the description of the changes, we refer to a queue
containing random requests as 'seeky', according to the terminology
used in the code, and inherited from CFQ.
- First, now R_est may be updated also in case the just-expired queue,
despite not being detected as seeky, has not been however able to
consume all of its budget within the maximum time slice T_max. In
fact, this is an indication that B_max is too large. Since B_max =
T_max ∗ R_est, R_est is then probably too large, and should be
reduced.
- Second, to filter the spikes in R_meas, a discrete low-pass filter
is now used to update R_est instead of just keeping the highest rate
sampled. The rationale is that the average peak rate of a disk over
its surface is a relatively stable quantity, hence a low-pass filter
should converge more or less quickly to the right value.
With the current values of the constants used in the filter, the
latter seems to effectively smooth fluctuations and allow the
estimator to converge to the actual peak rate with all the devices we
tested.
Signed-off-by: Paolo Valente <paolo.valente@linaro.org>
Signed-off-by: Arianna Avanzini <avanzini.arianna@gmail.com>
---
block/cfq-iosched.c | 131 ++++++++++++++++++++++++++++++++++++----------------
1 file changed, 92 insertions(+), 39 deletions(-)
diff --git a/block/cfq-iosched.c b/block/cfq-iosched.c
index eed1628..4a4dfc5 100644
--- a/block/cfq-iosched.c
+++ b/block/cfq-iosched.c
@@ -3851,48 +3851,83 @@ 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)
+static unsigned long bfq_calc_max_budget(struct bfq_data *bfqd)
{
- 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;
+ return bfqd->peak_rate * 1000 * jiffies_to_msecs(bfqd->bfq_timeout) >>
+ BFQ_RATE_SHIFT;
}
/*
- * 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.
+ * Update the read peak rate (quantity used for auto-tuning) as a
+ * function of the rate at which bfqq has been served, and check
+ * whether the process associated with bfqq is "slow". Return true if
+ * the process is slow. The 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. More details in the body of the function.
+ *
+ * An important observation is in order: 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, the device may be 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,
+ * as written above, this sum is the quantity used in this function to
+ * evaluate the peak rate.
*/
static bool bfq_update_peak_rate(struct bfq_data *bfqd, struct bfq_queue *bfqq,
- bool compensate)
+ bool compensate, enum bfqq_expiration reason,
+ unsigned long *delta_ms)
{
- u64 bw, usecs, expected, timeout;
- ktime_t delta;
+ u64 expected;
+ u64 bw, bwdiv10, delta_usecs, delta_ms_tmp;
+ ktime_t delta_ktime;
int update = 0;
+ 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);
+ 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 (usecs < 100 || usecs >= LONG_MAX)
- return false;
+ if (delta_usecs < 1000 || delta_usecs >= LONG_MAX) {
+ if (blk_queue_nonrot(bfqd->queue))
+ *delta_ms = BFQ_MIN_TT; /*
+ * provide same worst-case
+ * guarantees as idling for
+ * seeky
+ */
+ else /* Charge at least one seek */
+ *delta_ms = jiffies_to_msecs(bfq_slice_idle);
+ return slow;
+ }
+
+ delta_ms_tmp = delta_usecs;
+ do_div(delta_ms_tmp, 1000);
+ *delta_ms = delta_ms_tmp;
/*
* Calculate the bandwidth for the last slice. We use a 64 bit
@@ -3901,19 +3936,38 @@ static bool bfq_update_peak_rate(struct bfq_data *bfqd, struct bfq_queue *bfqq,
* and to avoid overflows.
*/
bw = (u64)bfqq->entity.service << BFQ_RATE_SHIFT;
- do_div(bw, (unsigned long)usecs);
-
- timeout = jiffies_to_msecs(bfqd->bfq_timeout);
+ do_div(bw, (unsigned long)delta_usecs);
/*
* Use only long (> 20ms) intervals to filter out spikes for
* the peak rate estimation.
*/
- if (usecs > 20000) {
- if (bw > bfqd->peak_rate) {
- bfqd->peak_rate = bw;
+ if (delta_usecs > 20000) {
+ bool fully_sequential = bfqq->seek_history == 0;
+ bool consumed_large_budget =
+ reason == BFQ_BFQQ_BUDGET_EXHAUSTED &&
+ bfqq->entity.budget >= bfqd->bfq_max_budget * 2 / 3;
+ bool served_for_long_time =
+ reason == BFQ_BFQQ_BUDGET_TIMEOUT ||
+ consumed_large_budget;
+
+ if (bw > bfqd->peak_rate ||
+ (bfq_bfqq_sync(bfqq) && fully_sequential &&
+ served_for_long_time)) {
+ /*
+ * To smooth oscillations use a low-pass filter with
+ * alpha=9/10, i.e.,
+ * new_rate = (9/10) * old_rate + (1/10) * bw
+ */
+ bwdiv10 = bw;
+ do_div(bwdiv10, 10);
+ if (bwdiv10 == 0)
+ return false; /* bw too low to be used */
+ bfqd->peak_rate *= 9;
+ do_div(bfqd->peak_rate, 10);
+ bfqd->peak_rate += bwdiv10;
update = 1;
- bfq_log(bfqd, "new peak_rate=%llu", bw);
+ bfq_log(bfqd, "new peak_rate=%llu", bfqd->peak_rate);
}
update |= bfqd->peak_rate_samples == BFQ_PEAK_RATE_SAMPLES - 1;
@@ -3923,10 +3977,8 @@ static bool bfq_update_peak_rate(struct bfq_data *bfqd, struct bfq_queue *bfqq,
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 = bfq_calc_max_budget(bfqd);
+ bfq_log(bfqd, "new max_budget = %d",
bfqd->bfq_max_budget);
}
}
@@ -3939,7 +3991,8 @@ static bool bfq_update_peak_rate(struct bfq_data *bfqd, struct bfq_queue *bfqq,
* rate that would not be high enough to complete the budget
* before the budget timeout expiration.
*/
- expected = bw * 1000 * timeout >> BFQ_RATE_SHIFT;
+ expected = bw * 1000 * jiffies_to_msecs(bfqd->bfq_timeout)
+ >> BFQ_RATE_SHIFT;
/*
* Caveat: processes doing IO in the slower disk zones will
@@ -3997,12 +4050,14 @@ 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).
*/
- slow = bfq_update_peak_rate(bfqd, bfqq, compensate);
+ slow = bfq_update_peak_rate(bfqd, bfqq, compensate, reason, &delta);
/*
* As above explained, 'punish' slow (i.e., seeky), timed-out
@@ -4012,7 +4067,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,
@@ -5266,10 +5321,8 @@ static ssize_t bfq_weights_store(struct elevator_queue *e,
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);
+ return bfq_calc_max_budget(bfqd);
else
return bfq_default_max_budget;
}
--
1.9.1
[toc] | [prev] | [next] | [standalone]
| From | Paolo Valente <paolo.valente@linaro.org> |
|---|---|
| Date | 2016-07-27 18:20 +0200 |
| Subject | [PATCH RFC V8 04/22] block, cfq: remove SSD-related logic |
| Message-ID | <rZzIS-1FV-15@gated-at.bofh.it> |
| In reply to | #1451384 |
From: Arianna Avanzini <avanzini.arianna@gmail.com>
CFQ disables idling for SSD devices to achieve a higher throughput. As
for seeky queues (see the previous commit), BFQ makes idling decisions
for SSD devices in a more complex way, according to a unified strategy
for boosting the throughput while at the same preserving strong
throughput-distribution and latency guarantees. This commit then
removes the CFQ mechanism.
Signed-off-by: Arianna Avanzini <avanzini.arianna@gmail.com>
Signed-off-by: Paolo Valente <paolo.valente@linaro.org>
---
block/cfq-iosched.c | 18 ++----------------
1 file changed, 2 insertions(+), 16 deletions(-)
diff --git a/block/cfq-iosched.c b/block/cfq-iosched.c
index 870d1ba..fc53555 100644
--- a/block/cfq-iosched.c
+++ b/block/cfq-iosched.c
@@ -51,7 +51,6 @@ static const int cfq_hist_divisor = 4;
#define CFQQ_SEEK_THR (sector_t)(8 * 100)
#define CFQQ_CLOSE_THR (sector_t)(8 * 1024)
-#define CFQQ_SECT_THR_NONROT (sector_t)(2 * 32)
#define CFQQ_SEEKY(cfqq) (hweight32(cfqq->seek_history) > 32/8)
#define RQ_CIC(rq) icq_to_cic((rq)->elv.icq)
@@ -2695,8 +2694,7 @@ static bool cfq_should_idle(struct cfq_data *cfqd, struct cfq_queue *cfqq)
return false;
/* We do for queues that were marked with idle window flag. */
- if (cfq_cfqq_idle_window(cfqq) &&
- !(blk_queue_nonrot(cfqd->queue) && cfqd->hw_tag))
+ if (cfq_cfqq_idle_window(cfqq))
return true;
/*
@@ -2717,14 +2715,6 @@ static void cfq_arm_slice_timer(struct cfq_data *cfqd)
struct cfq_io_cq *cic;
unsigned long sl, group_idle = 0;
- /*
- * SSD device without seek penalty, disable idling. But only do so
- * for devices that support queuing, otherwise we still have a problem
- * with sync vs async workloads.
- */
- if (blk_queue_nonrot(cfqd->queue) && cfqd->hw_tag)
- return;
-
WARN_ON(!RB_EMPTY_ROOT(&cfqq->sort_list));
WARN_ON(cfq_cfqq_slice_new(cfqq));
@@ -3585,7 +3575,6 @@ cfq_update_io_seektime(struct cfq_data *cfqd, struct cfq_queue *cfqq,
struct request *rq)
{
sector_t sdist = 0;
- sector_t n_sec = blk_rq_sectors(rq);
if (cfqq->last_request_pos) {
if (cfqq->last_request_pos < blk_rq_pos(rq))
sdist = blk_rq_pos(rq) - cfqq->last_request_pos;
@@ -3594,10 +3583,7 @@ cfq_update_io_seektime(struct cfq_data *cfqd, struct cfq_queue *cfqq,
}
cfqq->seek_history <<= 1;
- if (blk_queue_nonrot(cfqd->queue))
- cfqq->seek_history |= (n_sec < CFQQ_SECT_THR_NONROT);
- else
- cfqq->seek_history |= (sdist > CFQQ_SEEK_THR);
+ cfqq->seek_history |= (sdist > CFQQ_SEEK_THR);
}
/*
--
1.9.1
[toc] | [prev] | [next] | [standalone]
| From | Paolo Valente <paolo.valente@linaro.org> |
|---|---|
| Date | 2016-07-27 18:20 +0200 |
| Subject | [PATCH RFC V8 17/22] block, bfq: reduce latency during request-pool saturation |
| Message-ID | <rZzIS-1FV-19@gated-at.bofh.it> |
| In reply to | #1451384 |
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/cfq-iosched.c | 66 ++++++++++++++++++++++++++++++++++++++++++++++++++---
1 file changed, 63 insertions(+), 3 deletions(-)
diff --git a/block/cfq-iosched.c b/block/cfq-iosched.c
index 5207ed8..980d321 100644
--- a/block/cfq-iosched.c
+++ b/block/cfq-iosched.c
@@ -368,6 +368,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 */
@@ -1980,6 +1982,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);
@@ -1996,6 +2001,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_CFQ_GROUP_IOSCHED) && defined(CONFIG_DEBUG_BLK_CGROUP)
@@ -3287,7 +3295,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;
}
/**
@@ -3749,6 +3766,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)
@@ -3947,6 +3965,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;
/*
@@ -4807,7 +4827,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;
@@ -4830,6 +4851,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
@@ -4903,7 +4962,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);
}
/*
@@ -6026,6 +6085,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
--
1.9.1
[toc] | [prev] | [next] | [standalone]
| From | Paolo Valente <paolo.valente@linaro.org> |
|---|---|
| Date | 2016-07-27 18:20 +0200 |
| Subject | [PATCH RFC V8 13/22] block, bfq: add more fairness with writes and slow processes |
| Message-ID | <rZzIS-1FV-13@gated-at.bofh.it> |
| In reply to | #1451384 |
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/cfq-iosched.c | 152 +++++++++++++++++++++++++++++++++-------------------
1 file changed, 96 insertions(+), 56 deletions(-)
diff --git a/block/cfq-iosched.c b/block/cfq-iosched.c
index 4a4dfc5..848eb09 100644
--- a/block/cfq-iosched.c
+++ b/block/cfq-iosched.c
@@ -678,6 +678,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;
@@ -1350,22 +1357,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));
}
/**
@@ -3092,10 +3129,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;
}
/**
@@ -3896,7 +3937,6 @@ static bool bfq_update_peak_rate(struct bfq_data *bfqd, struct bfq_queue *bfqq,
bool compensate, enum bfqq_expiration reason,
unsigned long *delta_ms)
{
- u64 expected;
u64 bw, bwdiv10, delta_usecs, delta_ms_tmp;
ktime_t delta_ktime;
int update = 0;
@@ -3981,28 +4021,19 @@ static bool bfq_update_peak_rate(struct bfq_data *bfqd, struct bfq_queue *bfqq,
bfq_log(bfqd, "new max_budget = %d",
bfqd->bfq_max_budget);
}
+ /*
+ * Caveat: processes doing IO 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 bw has been lower than half
+ * of the estimated peak rate.
+ */
+ slow = bw < bfqd->peak_rate / 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 * jiffies_to_msecs(bfqd->bfq_timeout)
- >> BFQ_RATE_SHIFT;
-
- /*
- * 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;
}
/*
@@ -4021,28 +4052,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,
@@ -4060,11 +4087,24 @@ static void bfq_bfqq_expire(struct bfq_data *bfqd,
slow = bfq_update_peak_rate(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)
--
1.9.1
[toc] | [prev] | [next] | [standalone]
| From | Paolo Valente <paolo.valente@linaro.org> |
|---|---|
| Date | 2016-07-27 18:20 +0200 |
| Subject | [PATCH RFC V8 08/22] block, cfq: get rid of latency tunables |
| Message-ID | <rZzIS-1FV-25@gated-at.bofh.it> |
| In reply to | #1451384 |
BFQ guarantees a low latency for interactive applications in a
completely different way with respect to CFQ. On the other hand, in
terms of interface and exactly as CFQ does, BFQ exports a boolean
low_latency tunable to switch low-latency heuristics on (in BFQ, these
heuristics lowers latency for interactive and soft real-time
applications). Finally, differently from CFQ, BFQ has not other
latency tunable.
Accordingly, this commit temporarily turns all latency tunables into
fake tunables, by turning the functions for reading and writing these
tunables into functions that just generate warnings. The commit
introducing low-latency heuristics in BFQ then restores only the
boolean low_latency tunable.
Signed-off-by: Paolo Valente <paolo.valente@linaro.org>
---
block/cfq-iosched.c | 31 +++++++++++++++++++------------
1 file changed, 19 insertions(+), 12 deletions(-)
diff --git a/block/cfq-iosched.c b/block/cfq-iosched.c
index df8fb826..47e23e5 100644
--- a/block/cfq-iosched.c
+++ b/block/cfq-iosched.c
@@ -30,7 +30,6 @@ static const int cfq_slice_sync = HZ / 10;
static int cfq_slice_async = HZ / 25;
static const int cfq_slice_async_rq = 2;
static int cfq_slice_idle = HZ / 125;
-static const int cfq_target_latency = HZ * 3/10; /* 300 ms */
static const int cfq_hist_divisor = 4;
/*
@@ -227,8 +226,6 @@ struct cfq_data {
unsigned int cfq_slice[2];
unsigned int cfq_slice_async_rq;
unsigned int cfq_slice_idle;
- unsigned int cfq_latency;
- unsigned int cfq_target_latency;
/*
* Fallback dummy cfqq for extreme OOM conditions
@@ -1463,7 +1460,7 @@ static bool cfq_may_dispatch(struct cfq_data *cfqd, struct cfq_queue *cfqq)
* We also ramp up the dispatch depth gradually for async IO,
* based on the last sync IO we serviced
*/
- if (!cfq_cfqq_sync(cfqq) && cfqd->cfq_latency) {
+ if (!cfq_cfqq_sync(cfqq)) {
unsigned long last_sync = jiffies - cfqd->last_delayed_sync;
unsigned int depth;
@@ -2269,10 +2266,8 @@ static int cfq_init_queue(struct request_queue *q, struct elevator_type *e)
cfqd->cfq_back_penalty = cfq_back_penalty;
cfqd->cfq_slice[0] = cfq_slice_async;
cfqd->cfq_slice[1] = cfq_slice_sync;
- cfqd->cfq_target_latency = cfq_target_latency;
cfqd->cfq_slice_async_rq = cfq_slice_async_rq;
cfqd->cfq_slice_idle = cfq_slice_idle;
- cfqd->cfq_latency = 1;
cfqd->hw_tag = -1;
/*
* we optimistically start assuming sync ops weren't delayed in last
@@ -2330,8 +2325,6 @@ SHOW_FUNCTION(cfq_slice_idle_show, cfqd->cfq_slice_idle, 1);
SHOW_FUNCTION(cfq_slice_sync_show, cfqd->cfq_slice[1], 1);
SHOW_FUNCTION(cfq_slice_async_show, cfqd->cfq_slice[0], 1);
SHOW_FUNCTION(cfq_slice_async_rq_show, cfqd->cfq_slice_async_rq, 0);
-SHOW_FUNCTION(cfq_low_latency_show, cfqd->cfq_latency, 0);
-SHOW_FUNCTION(cfq_target_latency_show, cfqd->cfq_target_latency, 1);
#undef SHOW_FUNCTION
#define STORE_FUNCTION(__FUNC, __PTR, MIN, MAX, __CONV) \
@@ -2363,13 +2356,27 @@ STORE_FUNCTION(cfq_slice_sync_store, &cfqd->cfq_slice[1], 1, UINT_MAX, 1);
STORE_FUNCTION(cfq_slice_async_store, &cfqd->cfq_slice[0], 1, UINT_MAX, 1);
STORE_FUNCTION(cfq_slice_async_rq_store, &cfqd->cfq_slice_async_rq, 1,
UINT_MAX, 0);
-STORE_FUNCTION(cfq_low_latency_store, &cfqd->cfq_latency, 0, 1, 0);
-STORE_FUNCTION(cfq_target_latency_store, &cfqd->cfq_target_latency, 1, UINT_MAX, 1);
#undef STORE_FUNCTION
+static ssize_t cfq_fake_lat_show(struct elevator_queue *e, char *page)
+{
+ pr_warn_once("CFQ I/O SCHED: tried to read removed latency tunable");
+ return sprintf(page, "0\n");
+}
+
+static ssize_t
+cfq_fake_lat_store(struct elevator_queue *e, const char *page, size_t count)
+{
+ pr_warn_once("CFQ I/O SCHED: tried to write removed latency tunable");
+ return count;
+}
+
#define CFQ_ATTR(name) \
__ATTR(name, S_IRUGO|S_IWUSR, cfq_##name##_show, cfq_##name##_store)
+#define CFQ_FAKE_LAT_ATTR(name) \
+ __ATTR(name, S_IRUGO|S_IWUSR, cfq_fake_lat_show, cfq_fake_lat_store)
+
static struct elv_fs_entry cfq_attrs[] = {
CFQ_ATTR(quantum),
CFQ_ATTR(fifo_expire_sync),
@@ -2380,8 +2387,8 @@ static struct elv_fs_entry cfq_attrs[] = {
CFQ_ATTR(slice_async),
CFQ_ATTR(slice_async_rq),
CFQ_ATTR(slice_idle),
- CFQ_ATTR(low_latency),
- CFQ_ATTR(target_latency),
+ CFQ_FAKE_LAT_ATTR(low_latency),
+ CFQ_FAKE_LAT_ATTR(target_latency),
__ATTR_NULL
};
--
1.9.1
[toc] | [prev] | [next] | [standalone]
| From | Paolo Valente <paolo.valente@linaro.org> |
|---|---|
| Date | 2016-07-27 18:20 +0200 |
| Subject | [PATCH RFC V8 20/22] block, bfq: boost the throughput on NCQ-capable flash-based devices |
| Message-ID | <rZzIS-1FV-31@gated-at.bofh.it> |
| In reply to | #1451384 |
This patch boosts the throughput on NCQ-capable flash-based devices, while still preserving latency guarantees for interactive and soft real-time applications. The throughput is boosted by just not idling the device when the in-service queue remains empty, even if the queue is sync and has a non-null idle window. This helps to keep the drive's internal queue full, which is necessary to achieve maximum performance. This solution to boost the throughput is a port of commits a68bbdd and f7d7b7a for CFQ. As already highlighted in a previous patch, allowing the device to prefetch and internally reorder requests trivially causes loss of control on the request service order, and hence on service guarantees. Fortunately, as discussed in detail in the comments on the function bfq_bfqq_may_idle(), if every process has to receive the same fraction of the throughput, then the service order enforced by the internal scheduler of a flash-based device is relatively close to that enforced by BFQ. In particular, it is close enough to let service guarantees be substantially preserved. Things change in an asymmetric scenario, i.e., if not every process has to receive the same fraction of the throughput. In this case, to guarantee the desired throughput distribution, the device must be prevented from prefetching requests. This is exactly what this patch does in asymmetric scenarios. Signed-off-by: Paolo Valente <paolo.valente@linaro.org> Signed-off-by: Arianna Avanzini <avanzini.arianna@gmail.com> --- block/cfq-iosched.c | 154 ++++++++++++++++++++++++++++++++++++---------------- 1 file changed, 106 insertions(+), 48 deletions(-) diff --git a/block/cfq-iosched.c b/block/cfq-iosched.c index b505535..7fee23b 100644 --- a/block/cfq-iosched.c +++ b/block/cfq-iosched.c @@ -5632,15 +5632,25 @@ static bool bfq_bfqq_may_idle(struct bfq_queue *bfqq) * The value of the variable is computed considering that * idling is usually beneficial for the throughput if: * (a) the device is not NCQ-capable, or - * (b) regardless of the presence of NCQ, the request pattern - * for bfqq is I/O-bound (possible throughput losses - * caused by granting idling to seeky queues are mitigated - * by the fact that, in all scenarios where boosting - * throughput is the best thing to do, i.e., in all - * symmetric scenarios, only a minimal idle time is - * allowed to seeky queues). + * (b) regardless of the presence of NCQ, the device is rotational + * and the request pattern for bfqq is I/O-bound (possible + * throughput losses caused by granting idling to seeky queues + * are mitigated by the fact that, in all scenarios where + * boosting throughput is the best thing to do, i.e., in all + * symmetric scenarios, only a minimal idle time is allowed to + * seeky queues). + * + * Secondly, and in contrast to the above item (b), idling an + * NCQ-capable flash-based device would not boost the + * throughput even with intense I/O; rather it would lower + * the throughput in proportion to how fast the device + * is. Accordingly, the next variable is true if any of the + * above conditions (a) and (b) is true, and, in particular, + * happens to be false if bfqd is an NCQ-capable flash-based + * device. */ - idling_boosts_thr = !bfqd->hw_tag || bfq_bfqq_IO_bound(bfqq); + idling_boosts_thr = !bfqd->hw_tag || + (!blk_queue_nonrot(bfqd->queue) && bfq_bfqq_IO_bound(bfqq)); /* * The value of the next variable, @@ -5681,14 +5691,16 @@ static bool bfq_bfqq_may_idle(struct bfq_queue *bfqq) bfqd->wr_busy_queues == 0; /* - * There is then a case where idling must be performed not for - * throughput concerns, but to preserve service guarantees. To - * introduce it, we can note that allowing the drive to - * enqueue more than one request at a time, and hence + * There is then a case where idling must be performed not + * for throughput concerns, but to preserve service + * guarantees. + * + * To introduce this case, we can note that allowing the drive + * to enqueue more than one request at a time, and hence * delegating de facto final scheduling decisions to the - * drive's internal scheduler, causes loss of control on the + * drive's internal scheduler, entails loss of control on the * actual request service order. In particular, the critical - * situation is when requests from different processes happens + * situation is when requests from different processes happen * to be present, at the same time, in the internal queue(s) * of the drive. In such a situation, the drive, by deciding * the service order of the internally-queued requests, does @@ -5699,51 +5711,97 @@ static bool bfq_bfqq_may_idle(struct bfq_queue *bfqq) * the service distribution enforced by the drive's internal * scheduler is likely to coincide with the desired * device-throughput distribution only in a completely - * symmetric scenario where: (i) each of these processes must - * get the same throughput as the others; (ii) all these - * processes have the same I/O pattern (either sequential or - * random). In fact, in such a scenario, the drive will tend - * to treat the requests of each of these processes in about - * the same way as the requests of the others, and thus to - * provide each of these processes with about the same - * throughput (which is exactly the desired throughput - * distribution). In contrast, in any asymmetric scenario, - * device idling is certainly needed to guarantee that bfqq - * receives its assigned fraction of the device throughput - * (see [1] for details). + * symmetric scenario where: + * (i) each of these processes must get the same throughput as + * the others; + * (ii) all these processes have the same I/O pattern + (either sequential or random). + * In fact, in such a scenario, the drive will tend to treat + * the requests of each of these processes in about the same + * way as the requests of the others, and thus to provide + * each of these processes with about the same throughput + * (which is exactly the desired throughput distribution). In + * contrast, in any asymmetric scenario, device idling is + * certainly needed to guarantee that bfqq receives its + * assigned fraction of the device throughput (see [1] for + * details). + * + * We address this issue by controlling, actually, only the + * symmetry sub-condition (i), i.e., provided that + * sub-condition (i) holds, idling is not performed, + * regardless of whether sub-condition (ii) holds. In other + * words, only if sub-condition (i) holds, then idling is + * allowed, and the device tends to be prevented from queueing + * many requests, possibly of several processes. The reason + * for not controlling also sub-condition (ii) is that we + * exploit preemption to preserve guarantees in case of + * symmetric scenarios, even if (ii) does not hold, as + * explained in the next two paragraphs. + * + * Even if a queue, say Q, is expired when it remains idle, Q + * can still preempt the new in-service queue if the next + * request of Q arrives soon (see the comments on + * bfq_bfqq_update_budg_for_activation). If all queues and + * groups have the same weight, this form of preemption, + * combined with the hole-recovery heuristic described in the + * comments on function bfq_bfqq_update_budg_for_activation, + * are enough to preserve a correct bandwidth distribution in + * the mid term, even without idling. In fact, even if not + * idling allows the internal queues of the device to contain + * many requests, and thus to reorder requests, we can rather + * safely assume that the internal scheduler still preserves a + * minimum of mid-term fairness. The motivation for using + * preemption instead of idling is that, by not idling, + * service guarantees are preserved without minimally + * sacrificing throughput. In other words, both a high + * throughput and its desired distribution are obtained. + * + * More precisely, this preemption-based, idleless approach + * provides fairness in terms of IOPS, and not sectors per + * second. This can be seen with a simple example. Suppose + * that there are two queues with the same weight, but that + * the first queue receives requests of 8 sectors, while the + * second queue receives requests of 1024 sectors. In + * addition, suppose that each of the two queues contains at + * most one request at a time, which implies that each queue + * always remains idle after it is served. Finally, after + * remaining idle, each queue receives very quickly a new + * request. It follows that the two queues are served + * alternatively, preempting each other if needed. This + * implies that, although both queues have the same weight, + * the queue with large requests receives a service that is + * 1024/8 times as high as the service received by the other + * queue. * - * As for sub-condition (i), actually we check only whether - * bfqq is being weight-raised. In fact, if bfqq is not being - * weight-raised, we have that: - * - if the process associated with bfqq is not I/O-bound, then - * it is not either latency- or throughput-critical; therefore - * idling is not needed for bfqq; - * - if the process asociated with bfqq is I/O-bound, then - * idling is already granted with bfqq (see the comments on - * idling_boosts_thr). + * On the other hand, device idling is performed, and thus + * pure sector-domain guarantees are provided, for the + * following queues, which are likely to need stronger + * throughput guarantees: weight-raised queues, and queues + * with a higher weight than other queues. When such queues + * are active, sub-condition (i) is false, which triggers + * device idling. * - * We do not check sub-condition (ii) at all, i.e., the next - * variable is true if and only if bfqq is being - * weight-raised. We do not need to control sub-condition (ii) - * for the following reason: - * - if bfqq is being weight-raised, then idling is already - * guaranteed to bfqq by sub-condition (i); - * - if bfqq is not being weight-raised, then idling is - * already guaranteed to bfqq (only) if it matters, i.e., if - * bfqq is associated to a currently I/O-bound process (see - * the above comment on sub-condition (i)). + * According to the above considerations, the next variable is + * true (only) if sub-condition (i) holds. To compute the + * value of this variable, we not only use the return value of + * the function bfq_symmetric_scenario(), but also check + * whether bfqq is being weight-raised, because + * bfq_symmetric_scenario() does not take into account also + * weight-raised queues (see comments on + * bfq_weights_tree_add()). * * As a side note, it is worth considering that the above * device-idling countermeasures may however fail in the * following unlucky scenario: if idling is (correctly) - * disabled in a time period during which the symmetry - * sub-condition holds, and hence the device is allowed to + * disabled in a time period during which all symmetry + * sub-conditions hold, and hence the device is allowed to * enqueue many requests, but at some later point in time some * sub-condition stops to hold, then it may become impossible * to let requests be served in the desired order until all * the requests already queued in the device have been served. */ - asymmetric_scenario = bfqq->wr_coeff > 1; + asymmetric_scenario = bfqq->wr_coeff > 1 || + !bfq_symmetric_scenario(bfqd); /* * We have now all the components we need to compute the return -- 1.9.1
[toc] | [prev] | [next] | [standalone]
| From | Paolo Valente <paolo.valente@linaro.org> |
|---|---|
| Date | 2016-07-27 18:20 +0200 |
| Subject | [PATCH RFC V8 19/22] block, bfq: reduce idling only in symmetric scenarios |
| Message-ID | <rZzIS-1FV-37@gated-at.bofh.it> |
| In reply to | #1451384 |
From: Arianna Avanzini <avanzini.arianna@gmail.com>
A seeky queue (i..e, a queue containing random requests) is assigned a
very small device-idling slice, for throughput issues. Unfortunately,
given the process associated with a seeky queue, this behavior causes
the following problem: if the process, say P, performs sync I/O and
has a higher weight than some other processes doing I/O and associated
with non-seeky queues, then BFQ may fail to guarantee to P its
reserved share of the throughput. The reason is that idling is key
for providing service guarantees to processes doing sync I/O [1].
This commit addresses this issue by allowing the device-idling slice
to be reduced for a seeky queue only if the scenario happens to be
symmetric, i.e., if all the queues are to receive the same share of
the throughput.
[1] P. Valente, A. Avanzini, "Evolution of the BFQ Storage I/O
Scheduler", Proceedings of the First Workshop on Mobile System
Technologies (MST-2015), May 2015.
http://algogroup.unimore.it/people/paolo/disk_sched/mst-2015.pdf
Signed-off-by: Arianna Avanzini <avanzini.arianna@gmail.com>
Signed-off-by: Riccardo Pizzetti <riccardo.pizzetti@gmail.com>
Signed-off-by: Samuele Zecchini <samuele.zecchini92@gmail.com>
Signed-off-by: Paolo Valente <paolo.valente@linaro.org>
---
block/cfq-iosched.c | 254 ++++++++++++++++++++++++++++++++++++++++++++++++++--
1 file changed, 248 insertions(+), 6 deletions(-)
diff --git a/block/cfq-iosched.c b/block/cfq-iosched.c
index 27b51a7..b505535 100644
--- a/block/cfq-iosched.c
+++ b/block/cfq-iosched.c
@@ -145,6 +145,20 @@ struct bfq_sched_data {
};
/**
+ * struct bfq_weight_counter - counter of the number of all active entities
+ * with a given weight.
+ */
+struct bfq_weight_counter {
+ short int weight; /* weight of the entities this counter refers to */
+ unsigned int num_active; /* nr of active entities with this weight */
+ /*
+ * Weights tree member (see bfq_data's @queue_weights_tree and
+ * @group_weights_tree)
+ */
+ struct rb_node weights_node;
+};
+
+/**
* struct bfq_entity - schedulable entity.
*
* A bfq_entity is used to represent either a bfq_queue (leaf node in the
@@ -173,6 +187,8 @@ struct bfq_sched_data {
*/
struct bfq_entity {
struct rb_node rb_node; /* service_tree member */
+ /* pointer to the weight counter associated with this entity */
+ struct bfq_weight_counter *weight_counter;
/*
* flag, true if the entity is on a tree (either the active or
@@ -395,6 +411,25 @@ struct bfq_data {
struct bfq_group *root_group;
/*
+ * rbtree of weight counters of @bfq_queues, sorted by
+ * weight. Used to keep track of whether all @bfq_queues have
+ * the same weight. The tree contains one counter for each
+ * distinct weight associated to some active and not
+ * weight-raised @bfq_queue (see the comments to the functions
+ * bfq_weights_tree_[add|remove] for further details).
+ */
+ struct rb_root queue_weights_tree;
+ /*
+ * rbtree of non-queue @bfq_entity weight counters, sorted by
+ * weight. Used to keep track of whether all @bfq_groups have
+ * the same weight. The tree contains one counter for each
+ * distinct weight associated to some active @bfq_group (see
+ * the comments to the functions bfq_weights_tree_[add|remove]
+ * for further details).
+ */
+ struct rb_root group_weights_tree;
+
+ /*
* Number of bfq_queues containing requests (including the
* queue in service, even if it is idling).
*/
@@ -692,6 +727,11 @@ struct bfq_group_data {
* to avoid too many special cases during group creation/
* migration.
* @stats: stats for this bfqg.
+ * @active_entities: number of active entities belonging to the group;
+ * unused for the root group. Used to know whether there
+ * are groups with more than one active @bfq_entity
+ * (see the comments to the function
+ * bfq_bfqq_may_idle()).
* @rq_pos_tree: rbtree sorted by next_request position, used when
* determining if two or more queues have interleaving
* requests (see bfq_find_close_cooperator()).
@@ -719,6 +759,8 @@ struct bfq_group {
struct bfq_entity *my_entity;
+ int active_entities;
+
struct rb_root rq_pos_tree;
struct bfqg_stats stats;
@@ -1224,6 +1266,15 @@ up:
goto up;
}
+static void bfq_weights_tree_add(struct bfq_data *bfqd,
+ struct bfq_entity *entity,
+ struct rb_root *root);
+
+static void bfq_weights_tree_remove(struct bfq_data *bfqd,
+ struct bfq_entity *entity,
+ struct rb_root *root);
+
+
/**
* bfq_active_insert - insert an entity in the active tree of its
* group/device.
@@ -1262,6 +1313,13 @@ static void bfq_active_insert(struct bfq_service_tree *st,
#endif
if (bfqq)
list_add(&bfqq->bfqq_list, &bfqq->bfqd->active_list);
+#ifdef CONFIG_CFQ_GROUP_IOSCHED
+ else /* bfq_group */
+ bfq_weights_tree_add(bfqd, entity, &bfqd->group_weights_tree);
+
+ if (bfqg != bfqd->root_group)
+ bfqg->active_entities++;
+#endif
}
/**
@@ -1357,6 +1415,14 @@ static void bfq_active_extract(struct bfq_service_tree *st,
#endif
if (bfqq)
list_del(&bfqq->bfqq_list);
+#ifdef CONFIG_CFQ_GROUP_IOSCHED
+ else /* bfq_group */
+ bfq_weights_tree_remove(bfqd, entity,
+ &bfqd->group_weights_tree);
+
+ if (bfqg != bfqd->root_group)
+ bfqg->active_entities--;
+#endif
}
/**
@@ -1454,6 +1520,7 @@ __bfq_entity_update_weight_prio(struct bfq_service_tree *old_st,
struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);
unsigned short prev_weight, new_weight;
struct bfq_data *bfqd = NULL;
+ struct rb_root *root;
#ifdef CONFIG_CFQ_GROUP_IOSCHED
struct bfq_sched_data *sd;
struct bfq_group *bfqg;
@@ -1503,7 +1570,26 @@ __bfq_entity_update_weight_prio(struct bfq_service_tree *old_st,
prev_weight = entity->weight;
new_weight = entity->orig_weight *
(bfqq ? bfqq->wr_coeff : 1);
+ /*
+ * If the weight of the entity changes, remove the entity
+ * from its old weight counter (if there is a counter
+ * associated with the entity), and add it to the counter
+ * associated with its new weight.
+ */
+ if (prev_weight != new_weight) {
+ root = bfqq ? &bfqd->queue_weights_tree :
+ &bfqd->group_weights_tree;
+ bfq_weights_tree_remove(bfqd, entity, root);
+ }
entity->weight = new_weight;
+ /*
+ * Add the entity to its weights tree only if it is
+ * not associated with a weight-raised queue.
+ */
+ if (prev_weight != new_weight &&
+ (bfqq ? bfqq->wr_coeff == 1 : 1))
+ /* If we get here, root has been initialized. */
+ bfq_weights_tree_add(bfqd, entity, root);
new_st->wsum += entity->weight;
@@ -2044,6 +2130,10 @@ static void bfq_del_bfqq_busy(struct bfq_data *bfqd, struct bfq_queue *bfqq,
bfqd->busy_queues--;
+ if (!bfqq->dispatched)
+ bfq_weights_tree_remove(bfqd, &bfqq->entity,
+ &bfqd->queue_weights_tree);
+
if (bfqq->wr_coeff > 1)
bfqd->wr_busy_queues--;
@@ -2064,6 +2154,11 @@ static void bfq_add_bfqq_busy(struct bfq_data *bfqd, struct bfq_queue *bfqq)
bfq_mark_bfqq_busy(bfqq);
bfqd->busy_queues++;
+ if (!bfqq->dispatched)
+ if (bfqq->wr_coeff == 1)
+ bfq_weights_tree_add(bfqd, &bfqq->entity,
+ &bfqd->queue_weights_tree);
+
if (bfqq->wr_coeff > 1)
bfqd->wr_busy_queues++;
}
@@ -2490,6 +2585,7 @@ static void bfq_pd_init(struct blkg_policy_data *pd)
* in bfq_init_queue()
*/
bfqg->bfqd = bfqd;
+ bfqg->active_entities = 0;
bfqg->rq_pos_tree = RB_ROOT;
}
@@ -3397,6 +3493,142 @@ static void bfq_pos_tree_add_move(struct bfq_data *bfqd, struct bfq_queue *bfqq)
bfqq->pos_root = NULL;
}
+/*
+ * Tell whether there are active queues or groups with differentiated weights.
+ */
+static bool bfq_differentiated_weights(struct bfq_data *bfqd)
+{
+ /*
+ * For weights to differ, at least one of the trees must contain
+ * at least two nodes.
+ */
+ return (!RB_EMPTY_ROOT(&bfqd->queue_weights_tree) &&
+ (bfqd->queue_weights_tree.rb_node->rb_left ||
+ bfqd->queue_weights_tree.rb_node->rb_right)
+#ifdef CONFIG_CFQ_GROUP_IOSCHED
+ ) ||
+ (!RB_EMPTY_ROOT(&bfqd->group_weights_tree) &&
+ (bfqd->group_weights_tree.rb_node->rb_left ||
+ bfqd->group_weights_tree.rb_node->rb_right)
+#endif
+ );
+}
+
+/*
+ * The following function returns true if every queue must receive the
+ * same share of the throughput (this condition is used when deciding
+ * whether idling may be disabled, see the comments in the function
+ * bfq_bfqq_may_idle()).
+ *
+ * Such a scenario occurs when:
+ * 1) all active queues have the same weight,
+ * 2) all active groups at the same level in the groups tree have the same
+ * weight,
+ * 3) all active groups at the same level in the groups tree have the same
+ * number of children.
+ *
+ * Unfortunately, keeping the necessary state for evaluating exactly the
+ * above symmetry conditions would be quite complex and time-consuming.
+ * Therefore this function evaluates, instead, the following stronger
+ * sub-conditions, for which it is much easier to maintain the needed
+ * state:
+ * 1) all active queues have the same weight,
+ * 2) all active groups have the same weight,
+ * 3) all active groups have at most one active child each.
+ * In particular, the last two conditions are always true if hierarchical
+ * support and the cgroups interface are not enabled, thus no state needs
+ * to be maintained in this case.
+ */
+static bool bfq_symmetric_scenario(struct bfq_data *bfqd)
+{
+ return !bfq_differentiated_weights(bfqd);
+}
+
+/*
+ * If the weight-counter tree passed as input contains no counter for
+ * the weight of the input entity, then add that counter; otherwise just
+ * increment the existing counter.
+ *
+ * Note that weight-counter trees contain few nodes in mostly symmetric
+ * scenarios. For example, if all queues have the same weight, then the
+ * weight-counter tree for the queues may contain at most one node.
+ * This holds even if low_latency is on, because weight-raised queues
+ * are not inserted in the tree.
+ * In most scenarios, the rate at which nodes are created/destroyed
+ * should be low too.
+ */
+static void bfq_weights_tree_add(struct bfq_data *bfqd,
+ struct bfq_entity *entity,
+ struct rb_root *root)
+{
+ struct rb_node **new = &(root->rb_node), *parent = NULL;
+
+ /*
+ * Do not insert if the entity is already associated with a
+ * counter, which happens if:
+ * 1) the entity is associated with a queue,
+ * 2) a request arrival has caused the queue to become both
+ * non-weight-raised, and hence change its weight, and
+ * backlogged; in this respect, each of the two events
+ * causes an invocation of this function,
+ * 3) this is the invocation of this function caused by the
+ * second event. This second invocation is actually useless,
+ * and we handle this fact by exiting immediately. More
+ * efficient or clearer solutions might possibly be adopted.
+ */
+ if (entity->weight_counter)
+ return;
+
+ while (*new) {
+ struct bfq_weight_counter *__counter = container_of(*new,
+ struct bfq_weight_counter,
+ weights_node);
+ parent = *new;
+
+ if (entity->weight == __counter->weight) {
+ entity->weight_counter = __counter;
+ goto inc_counter;
+ }
+ if (entity->weight < __counter->weight)
+ new = &((*new)->rb_left);
+ else
+ new = &((*new)->rb_right);
+ }
+
+ entity->weight_counter = kzalloc(sizeof(struct bfq_weight_counter),
+ GFP_ATOMIC);
+ entity->weight_counter->weight = entity->weight;
+ rb_link_node(&entity->weight_counter->weights_node, parent, new);
+ rb_insert_color(&entity->weight_counter->weights_node, root);
+
+inc_counter:
+ entity->weight_counter->num_active++;
+}
+
+/*
+ * Decrement the weight counter associated with the entity, and, if the
+ * counter reaches 0, remove the counter from the tree.
+ * See the comments to the function bfq_weights_tree_add() for considerations
+ * about overhead.
+ */
+static void bfq_weights_tree_remove(struct bfq_data *bfqd,
+ struct bfq_entity *entity,
+ struct rb_root *root)
+{
+ if (!entity->weight_counter)
+ return;
+
+ entity->weight_counter->num_active--;
+ if (entity->weight_counter->num_active > 0)
+ goto reset_entity_pointer;
+
+ rb_erase(&entity->weight_counter->weights_node, root);
+ kfree(entity->weight_counter);
+
+reset_entity_pointer:
+ entity->weight_counter = NULL;
+}
+
static struct request *bfq_find_next_rq(struct bfq_data *bfqd,
struct bfq_queue *bfqq,
struct request *last)
@@ -4676,13 +4908,17 @@ static void bfq_arm_slice_timer(struct bfq_data *bfqd)
*/
sl = bfqd->bfq_slice_idle;
/*
- * Unless the queue is being weight-raised, grant only minimum
- * idle time if the queue is seeky. A long idling is preserved
- * for a weight-raised queue, because it is needed for
- * guaranteeing to the queue its reserved share of the
- * throughput.
+ * Unless the queue is being weight-raised or the scenario is
+ * asymmetric, grant only minimum idle time if the queue
+ * is seeky. A long idling is preserved for a weight-raised
+ * queue, or, more in general, in an asymemtric scenario,
+ * because a long idling is needed for guaranteeing to a queue
+ * its reserved share of the throughput (in particular, it is
+ * needed if the queue has a higher weight than some other
+ * queue).
*/
- if (BFQQ_SEEKY(bfqq) && bfqq->wr_coeff == 1)
+ if (BFQQ_SEEKY(bfqq) && bfqq->wr_coeff == 1 &&
+ bfq_symmetric_scenario(bfqd))
sl = min(sl, msecs_to_jiffies(BFQ_MIN_TT));
bfqd->last_idling_start = ktime_get();
@@ -6326,6 +6562,9 @@ static void bfq_completed_request(struct request_queue *q, struct request *rq)
* mechanism).
*/
bfqq->budget_timeout = jiffies;
+
+ bfq_weights_tree_remove(bfqd, &bfqq->entity,
+ &bfqd->queue_weights_tree);
}
RQ_BIC(rq)->ttime.last_end_request = jiffies;
@@ -6726,6 +6965,9 @@ static int bfq_init_queue(struct request_queue *q, struct elevator_type *e)
bfqd->idle_slice_timer.function = bfq_idle_slice_timer;
bfqd->idle_slice_timer.data = (unsigned long)bfqd;
+ bfqd->queue_weights_tree = RB_ROOT;
+ bfqd->group_weights_tree = RB_ROOT;
+
INIT_WORK(&bfqd->unplug_work, bfq_kick_queue);
INIT_LIST_HEAD(&bfqd->active_list);
--
1.9.1
[toc] | [prev] | [next] | [standalone]
| From | Paolo Valente <paolo.valente@linaro.org> |
|---|---|
| Date | 2016-07-27 18:20 +0200 |
| Subject | [PATCH RFC V8 22/22] block, bfq: handle bursts of queue activations |
| Message-ID | <rZzIS-1FV-41@gated-at.bofh.it> |
| In reply to | #1451384 |
From: Arianna Avanzini <avanzini.arianna@gmail.com>
Many popular I/O-intensive services or applications spawn or
reactivate many parallel threads/processes during short time
intervals. Examples are systemd during boot or git grep. These
services or applications benefit mostly from a high throughput: the
quicker the I/O generated by their processes is cumulatively served,
the sooner the target job of these services or applications gets
completed. As a consequence, it is almost always counterproductive to
weight-raise any of the queues associated to the processes of these
services or applications: in most cases it would just lower the
throughput, mainly because weight-raising also implies device idling.
To address this issue, an I/O scheduler needs, first, to detect which
queues are associated with these services or applications. In this
respect, we have that, from the I/O-scheduler standpoint, these
services or applications cause bursts of activations, i.e.,
activations of different queues occurring shortly after each
other. However, a shorter burst of activations may be caused also by
the start of an application that does not consist in a lot of parallel
I/O-bound threads (see the comments on the function bfq_handle_burst
for details).
In view of these facts, this commit introduces:
1) an heuristic to detect (only) bursts of queue activations caused by
services or applications consisting in many parallel I/O-bound
threads;
2) the prevention of device idling and weight-raising for the queues
belonging to these bursts.
Signed-off-by: Arianna Avanzini <avanzini.arianna@gmail.com>
Signed-off-by: Paolo Valente <paolo.valente@linaro.org>
---
block/cfq-iosched.c | 399 ++++++++++++++++++++++++++++++++++++++++++++++++++--
1 file changed, 388 insertions(+), 11 deletions(-)
diff --git a/block/cfq-iosched.c b/block/cfq-iosched.c
index ae17421..d7731f2 100644
--- a/block/cfq-iosched.c
+++ b/block/cfq-iosched.c
@@ -40,7 +40,9 @@
* real-time. This feature enables BFQ to provide applications in
* these classes with a very low latency. Finally, BFQ also features
* additional heuristics for preserving both a low latency and a high
- * throughput on NCQ-capable, rotational or flash-based devices.
+ * throughput on NCQ-capable, rotational or flash-based devices, and
+ * to get the job done quickly for applications consisting in many
+ * I/O-bound processes.
*
* With respect to the version of BFQ presented in [1], and in the
* papers cited therein, this implementation adds a hierarchical
@@ -302,6 +304,10 @@ struct bfq_queue {
/* bit vector: a 1 for each seeky requests in history */
u32 seek_history;
+
+ /* node for the device's burst list */
+ struct hlist_node burst_list_node;
+
/* position of the last request enqueued */
sector_t last_request_pos;
@@ -393,6 +399,17 @@ struct bfq_io_cq {
* classification of a queue.
*/
bool saved_IO_bound;
+
+ /*
+ * Same purpose as the previous fields for the value of the
+ * field keeping the queue's belonging to a large burst
+ */
+ bool saved_in_large_burst;
+ /*
+ * True if the queue belonged to a burst list before its merge
+ * with another cooperating queue.
+ */
+ bool was_in_burst_list;
};
enum bfq_device_speed {
@@ -531,6 +548,36 @@ struct bfq_data {
*/
bool strict_guarantees;
+ /*
+ * Last time at which a queue entered the current burst of
+ * queues being activated shortly after each other; for more
+ * details about this and the following parameters related to
+ * a burst of activations, see the comments on the function
+ * bfq_handle_burst.
+ */
+ unsigned long last_ins_in_burst;
+ /*
+ * Reference time interval used to decide whether a queue has
+ * been activated shortly after @last_ins_in_burst.
+ */
+ unsigned long bfq_burst_interval;
+ /* number of queues in the current burst of queue activations */
+ int burst_size;
+
+ /* common parent entity for the queues in the burst */
+ struct bfq_entity *burst_parent_entity;
+ /* Maximum burst size above which the current queue-activation
+ * burst is deemed as 'large'.
+ */
+ unsigned long bfq_large_burst_thresh;
+ /* true if a large queue-activation burst is in progress */
+ bool large_burst;
+ /*
+ * Head of the burst list (as for the above fields, more
+ * details in the comments on the function bfq_handle_burst).
+ */
+ struct hlist_head burst_list;
+
/* if set to true, low-latency heuristics are enabled */
bool low_latency;
/*
@@ -570,7 +617,8 @@ struct bfq_data {
};
enum bfqq_state_flags {
- BFQ_BFQQ_FLAG_busy = 0, /* has requests or is in service */
+ BFQ_BFQQ_FLAG_just_created = 0, /* queue just allocated */
+ BFQ_BFQQ_FLAG_busy, /* has requests or is in service */
BFQ_BFQQ_FLAG_wait_request, /* waiting for a request */
BFQ_BFQQ_FLAG_non_blocking_wait_rq, /*
* waiting for a request
@@ -585,6 +633,10 @@ enum bfqq_state_flags {
* having consumed at most 2/10 of
* its budget
*/
+ BFQ_BFQQ_FLAG_in_large_burst, /*
+ * bfqq activated in a large burst,
+ * see comments to bfq_handle_burst.
+ */
BFQ_BFQQ_FLAG_softrt_update, /*
* may need softrt-next-start
* update
@@ -607,6 +659,7 @@ static int bfq_bfqq_##name(const struct bfq_queue *bfqq) \
return ((bfqq)->flags & (1 << BFQ_BFQQ_FLAG_##name)) != 0; \
}
+BFQ_BFQQ_FNS(just_created);
BFQ_BFQQ_FNS(busy);
BFQ_BFQQ_FNS(wait_request);
BFQ_BFQQ_FNS(non_blocking_wait_rq);
@@ -615,6 +668,7 @@ BFQ_BFQQ_FNS(fifo_expire);
BFQ_BFQQ_FNS(idle_window);
BFQ_BFQQ_FNS(sync);
BFQ_BFQQ_FNS(IO_bound);
+BFQ_BFQQ_FNS(in_large_burst);
BFQ_BFQQ_FNS(coop);
BFQ_BFQQ_FNS(split_coop);
BFQ_BFQQ_FNS(softrt_update);
@@ -3736,6 +3790,232 @@ static int bfqq_process_refs(struct bfq_queue *bfqq)
return process_refs;
}
+/* Empty burst list and add just bfqq (see comments on bfq_handle_burst) */
+static void bfq_reset_burst_list(struct bfq_data *bfqd, struct bfq_queue *bfqq)
+{
+ struct bfq_queue *item;
+ struct hlist_node *n;
+
+ hlist_for_each_entry_safe(item, n, &bfqd->burst_list, burst_list_node)
+ hlist_del_init(&item->burst_list_node);
+ hlist_add_head(&bfqq->burst_list_node, &bfqd->burst_list);
+ bfqd->burst_size = 1;
+ bfqd->burst_parent_entity = bfqq->entity.parent;
+}
+
+/* Add bfqq to the list of queues in current burst (see bfq_handle_burst) */
+static void bfq_add_to_burst(struct bfq_data *bfqd, struct bfq_queue *bfqq)
+{
+ /* Increment burst size to take into account also bfqq */
+ bfqd->burst_size++;
+
+ if (bfqd->burst_size == bfqd->bfq_large_burst_thresh) {
+ struct bfq_queue *pos, *bfqq_item;
+ struct hlist_node *n;
+
+ /*
+ * Enough queues have been activated shortly after each
+ * other to consider this burst as large.
+ */
+ bfqd->large_burst = true;
+
+ /*
+ * We can now mark all queues in the burst list as
+ * belonging to a large burst.
+ */
+ hlist_for_each_entry(bfqq_item, &bfqd->burst_list,
+ burst_list_node)
+ bfq_mark_bfqq_in_large_burst(bfqq_item);
+ bfq_mark_bfqq_in_large_burst(bfqq);
+
+ /*
+ * From now on, and until the current burst finishes, any
+ * new queue being activated shortly after the last queue
+ * was inserted in the burst can be immediately marked as
+ * belonging to a large burst. So the burst list is not
+ * needed any more. Remove it.
+ */
+ hlist_for_each_entry_safe(pos, n, &bfqd->burst_list,
+ burst_list_node)
+ hlist_del_init(&pos->burst_list_node);
+ } else /*
+ * Burst not yet large: add bfqq to the burst list. Do
+ * not increment the ref counter for bfqq, because bfqq
+ * is removed from the burst list before freeing bfqq
+ * in put_queue.
+ */
+ hlist_add_head(&bfqq->burst_list_node, &bfqd->burst_list);
+}
+
+/*
+ * If many queues belonging to the same group happen to be created
+ * shortly after each other, then the processes associated with these
+ * queues have typically a common goal. In particular, bursts of queue
+ * creations are usually caused by services or applications that spawn
+ * many parallel threads/processes. Examples are systemd during boot,
+ * or git grep. To help these processes get their job done as soon as
+ * possible, it is usually better to not grant either weight-raising
+ * or device idling to their queues.
+ *
+ * In this comment we describe, firstly, the reasons why this fact
+ * holds, and, secondly, the next function, which implements the main
+ * steps needed to properly mark these queues so that they can then be
+ * treated in a different way.
+ *
+ * The above services or applications benefit mostly from a high
+ * throughput: the quicker the requests of the activated queues are
+ * cumulatively served, the sooner the target job of these queues gets
+ * completed. As a consequence, weight-raising any of these queues,
+ * which also implies idling the device for it, is almost always
+ * counterproductive. In most cases it just lowers throughput.
+ *
+ * On the other hand, a burst of queue creations may be caused also by
+ * the start of an application that does not consist of a lot of
+ * parallel I/O-bound threads. In fact, with a complex application,
+ * several short processes may need to be executed to start-up the
+ * application. In this respect, to start an application as quickly as
+ * possible, the best thing to do is in any case to privilege the I/O
+ * related to the application with respect to all other
+ * I/O. Therefore, the best strategy to start as quickly as possible
+ * an application that causes a burst of queue creations is to
+ * weight-raise all the queues created during the burst. This is the
+ * exact opposite of the best strategy for the other type of bursts.
+ *
+ * In the end, to take the best action for each of the two cases, the
+ * two types of bursts need to be distinguished. Fortunately, this
+ * seems relatively easy, by looking at the sizes of the bursts. In
+ * particular, we found a threshold such that only bursts with a
+ * larger size than that threshold are apparently caused by
+ * services or commands such as systemd or git grep. For brevity,
+ * hereafter we call just 'large' these bursts. BFQ *does not*
+ * weight-raise queues whose creation occurs in a large burst. In
+ * addition, for each of these queues BFQ performs or does not perform
+ * idling depending on which choice boosts the throughput more. The
+ * exact choice depends on the device and request pattern at
+ * hand.
+ *
+ * Unfortunately, false positives may occur while an interactive task
+ * is starting (e.g., an application is being started). The
+ * consequence is that the queues associated with the task do not
+ * enjoy weight raising as expected. Fortunately these false positives
+ * are very rare. They typically occur if some service happens to
+ * start doing I/O exactly when the interactive task starts.
+ *
+ * Turning back to the next function, it implements all the steps
+ * needed to detect the occurrence of a large burst and to properly
+ * mark all the queues belonging to it (so that they can then be
+ * treated in a different way). This goal is achieved by maintaining a
+ * "burst list" that holds, temporarily, the queues that belong to the
+ * burst in progress. The list is then used to mark these queues as
+ * belonging to a large burst if the burst does become large. The main
+ * steps are the following.
+ *
+ * . when the very first queue is created, the queue is inserted into the
+ * list (as it could be the first queue in a possible burst)
+ *
+ * . if the current burst has not yet become large, and a queue Q that does
+ * not yet belong to the burst is activated shortly after the last time
+ * at which a new queue entered the burst list, then the function appends
+ * Q to the burst list
+ *
+ * . if, as a consequence of the previous step, the burst size reaches
+ * the large-burst threshold, then
+ *
+ * . all the queues in the burst list are marked as belonging to a
+ * large burst
+ *
+ * . the burst list is deleted; in fact, the burst list already served
+ * its purpose (keeping temporarily track of the queues in a burst,
+ * so as to be able to mark them as belonging to a large burst in the
+ * previous sub-step), and now is not needed any more
+ *
+ * . the device enters a large-burst mode
+ *
+ * . if a queue Q that does not belong to the burst is created while
+ * the device is in large-burst mode and shortly after the last time
+ * at which a queue either entered the burst list or was marked as
+ * belonging to the current large burst, then Q is immediately marked
+ * as belonging to a large burst.
+ *
+ * . if a queue Q that does not belong to the burst is created a while
+ * later, i.e., not shortly after, than the last time at which a queue
+ * either entered the burst list or was marked as belonging to the
+ * current large burst, then the current burst is deemed as finished and:
+ *
+ * . the large-burst mode is reset if set
+ *
+ * . the burst list is emptied
+ *
+ * . Q is inserted in the burst list, as Q may be the first queue
+ * in a possible new burst (then the burst list contains just Q
+ * after this step).
+ */
+static void bfq_handle_burst(struct bfq_data *bfqd, struct bfq_queue *bfqq)
+{
+ /*
+ * If bfqq is already in the burst list or is part of a large
+ * burst, or finally has just been split, then there is
+ * nothing else to do.
+ */
+ if (!hlist_unhashed(&bfqq->burst_list_node) ||
+ bfq_bfqq_in_large_burst(bfqq) ||
+ time_is_after_eq_jiffies(bfqq->split_time +
+ msecs_to_jiffies(10)))
+ return;
+
+ /*
+ * If bfqq's creation happens late enough, or bfqq belongs to
+ * a different group than the burst group, then the current
+ * burst is finished, and related data structures must be
+ * reset.
+ *
+ * In this respect, consider the special case where bfqq is
+ * the very first queue created after BFQ is selected for this
+ * device. In this case, last_ins_in_burst and
+ * burst_parent_entity are not yet significant when we get
+ * here. But it is easy to verify that, whether or not the
+ * following condition is true, bfqq will end up being
+ * inserted into the burst list. In particular the list will
+ * happen to contain only bfqq. And this is exactly what has
+ * to happen, as bfqq may be the first queue of the first
+ * burst.
+ */
+ if (time_is_before_jiffies(bfqd->last_ins_in_burst +
+ bfqd->bfq_burst_interval) ||
+ bfqq->entity.parent != bfqd->burst_parent_entity) {
+ bfqd->large_burst = false;
+ bfq_reset_burst_list(bfqd, bfqq);
+ goto end;
+ }
+
+ /*
+ * If we get here, then bfqq is being activated shortly after the
+ * last queue. So, if the current burst is also large, we can mark
+ * bfqq as belonging to this large burst immediately.
+ */
+ if (bfqd->large_burst) {
+ bfq_mark_bfqq_in_large_burst(bfqq);
+ goto end;
+ }
+
+ /*
+ * If we get here, then a large-burst state has not yet been
+ * reached, but bfqq is being activated shortly after the last
+ * queue. Then we add bfqq to the burst.
+ */
+ bfq_add_to_burst(bfqd, bfqq);
+end:
+ /*
+ * At this point, bfqq either has been added to the current
+ * burst or has caused the current burst to terminate and a
+ * possible new burst to start. In particular, in the second
+ * case, bfqq has become the first queue in the possible new
+ * burst. In both cases last_ins_in_burst needs to be moved
+ * forward.
+ */
+ bfqd->last_ins_in_burst = jiffies;
+}
+
static int bfq_bfqq_budget_left(struct bfq_queue *bfqq)
{
struct bfq_entity *entity = &bfqq->entity;
@@ -3949,6 +4229,7 @@ static void bfq_update_bfqq_wr_on_rq_arrival(struct bfq_data *bfqd,
unsigned int old_wr_coeff,
bool wr_or_deserves_wr,
bool interactive,
+ bool in_burst,
bool soft_rt)
{
if (old_wr_coeff == 1 && wr_or_deserves_wr) {
@@ -3975,6 +4256,8 @@ static void bfq_update_bfqq_wr_on_rq_arrival(struct bfq_data *bfqd,
} else if (old_wr_coeff > 1) {
if (interactive) /* update wr duration */
bfqq->wr_cur_max_time = bfq_wr_duration(bfqd);
+ else if (in_burst)
+ bfqq->wr_coeff = 1;
else if (time_before(
bfqq->last_wr_start_finish +
bfqq->wr_cur_max_time,
@@ -4046,7 +4329,8 @@ static void bfq_bfqq_handle_idle_busy_switch(struct bfq_data *bfqd,
struct request *rq,
bool *interactive)
{
- bool soft_rt, wr_or_deserves_wr, bfqq_wants_to_preempt,
+ bool soft_rt, in_burst, wr_or_deserves_wr,
+ bfqq_wants_to_preempt,
idle_for_long_time = bfq_bfqq_idle_for_long_time(bfqd, bfqq),
/*
* See the comments on
@@ -4063,12 +4347,15 @@ static void bfq_bfqq_handle_idle_busy_switch(struct bfq_data *bfqd,
/*
* bfqq deserves to be weight-raised if:
* - it is sync,
+ * - it does not belong to a large burst,
* - it has been idle for enough time or is soft real-time,
* - is linked to a bfq_io_cq (it is not shared in any sense).
*/
+ in_burst = bfq_bfqq_in_large_burst(bfqq);
soft_rt = bfqd->bfq_wr_max_softrt_rate > 0 &&
+ !in_burst &&
time_is_before_jiffies(bfqq->soft_rt_next_start);
- *interactive = idle_for_long_time;
+ *interactive = !in_burst && idle_for_long_time;
wr_or_deserves_wr = bfqd->low_latency &&
(bfqq->wr_coeff > 1 ||
(bfq_bfqq_sync(bfqq) &&
@@ -4083,6 +4370,31 @@ static void bfq_bfqq_handle_idle_busy_switch(struct bfq_data *bfqd,
arrived_in_time,
wr_or_deserves_wr);
+ /*
+ * If bfqq happened to be activated in a burst, but has been
+ * idle for much more than an interactive queue, then we
+ * assume that, in the overall I/O initiated in the burst, the
+ * I/O associated with bfqq is finished. So bfqq does not need
+ * to be treated as a queue belonging to a burst
+ * anymore. Accordingly, we reset bfqq's in_large_burst flag
+ * if set, and remove bfqq from the burst list if it's
+ * there. We do not decrement burst_size, because the fact
+ * that bfqq does not need to belong to the burst list any
+ * more does not invalidate the fact that bfqq was created in
+ * a burst.
+ */
+ if (likely(!bfq_bfqq_just_created(bfqq)) &&
+ idle_for_long_time &&
+ time_is_before_jiffies(
+ bfqq->budget_timeout +
+ msecs_to_jiffies(10000))) {
+ hlist_del_init(&bfqq->burst_list_node);
+ bfq_clear_bfqq_in_large_burst(bfqq);
+ }
+
+ bfq_clear_bfqq_just_created(bfqq);
+
+
if (!bfq_bfqq_IO_bound(bfqq)) {
if (arrived_in_time) {
bfqq->requests_within_timer++;
@@ -4105,6 +4417,7 @@ static void bfq_bfqq_handle_idle_busy_switch(struct bfq_data *bfqd,
old_wr_coeff,
wr_or_deserves_wr,
*interactive,
+ in_burst,
soft_rt);
if (old_wr_coeff != bfqq->wr_coeff)
@@ -4686,6 +4999,8 @@ static void bfq_bfqq_save_state(struct bfq_queue *bfqq)
bfqq->bic->saved_idle_window = bfq_bfqq_idle_window(bfqq);
bfqq->bic->saved_IO_bound = bfq_bfqq_IO_bound(bfqq);
+ bfqq->bic->saved_in_large_burst = bfq_bfqq_in_large_burst(bfqq);
+ bfqq->bic->was_in_burst_list = !hlist_unhashed(&bfqq->burst_list_node);
}
static void bfq_get_bic_reference(struct bfq_queue *bfqq)
@@ -4717,7 +5032,8 @@ bfq_merge_bfqqs(struct bfq_data *bfqd, struct bfq_io_cq *bic,
* where bfqq has just been created, but has not yet made it
* to be weight-raised (which may happen because EQM may merge
* bfqq even before bfq_add_request is executed for the first
- * time for bfqq).
+ * time for bfqq). Handling this case would however be very
+ * easy, thanks to the flag just_created.
*/
if (new_bfqq->wr_coeff == 1 && bfqq->wr_coeff > 1) {
new_bfqq->wr_coeff = bfqq->wr_coeff;
@@ -5622,6 +5938,7 @@ static bool bfq_bfqq_may_idle(struct bfq_queue *bfqq)
{
struct bfq_data *bfqd = bfqq->bfqd;
bool idling_boosts_thr, idling_boosts_thr_without_issues,
+ idling_needed_for_service_guarantees,
asymmetric_scenario;
if (bfqd->strict_guarantees)
@@ -5802,6 +6119,23 @@ static bool bfq_bfqq_may_idle(struct bfq_queue *bfqq)
!bfq_symmetric_scenario(bfqd);
/*
+ * Finally, there is a case where maximizing throughput is the
+ * best choice even if it may cause unfairness toward
+ * bfqq. Such a case is when bfqq became active in a burst of
+ * queue activations. Queues that became active during a large
+ * burst benefit only from throughput, as discussed in the
+ * comments on bfq_handle_burst. Thus, if bfqq became active
+ * in a burst and not idling the device maximizes throughput,
+ * then the device must no be idled, because not idling the
+ * device provides bfqq and all other queues in the burst with
+ * maximum benefit. Combining this and the above case, we can
+ * now establish when idling is actually needed to preserve
+ * service guarantees.
+ */
+ idling_needed_for_service_guarantees =
+ asymmetric_scenario && !bfq_bfqq_in_large_burst(bfqq);
+
+ /*
* We have now all the components we need to compute the return
* value of the function, which is true only if both the following
* conditions hold:
@@ -5810,7 +6144,8 @@ static bool bfq_bfqq_may_idle(struct bfq_queue *bfqq)
* is necessary to preserve service guarantees.
*/
return bfq_bfqq_sync(bfqq) &&
- (idling_boosts_thr_without_issues || asymmetric_scenario);
+ (idling_boosts_thr_without_issues ||
+ idling_needed_for_service_guarantees);
}
/*
@@ -5929,10 +6264,12 @@ static void bfq_update_wr_data(struct bfq_data *bfqd, struct bfq_queue *bfqq)
bfq_log_bfqq(bfqd, bfqq, "WARN: pending prio change");
/*
- * If too much time has elapsed from the beginning of
- * this weight-raising period, then end weight raising.
+ * If the queue was activated in a burst, or too much
+ * time has elapsed from the beginning of this
+ * weight-raising period, then end weight raising.
*/
- if (time_is_before_jiffies(bfqq->last_wr_start_finish +
+ if (bfq_bfqq_in_large_burst(bfqq) ||
+ 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,
@@ -6121,6 +6458,17 @@ static void bfq_put_queue(struct bfq_queue *bfqq)
if (bfqq->ref)
return;
+ if (bfq_bfqq_sync(bfqq))
+ /*
+ * The fact that this queue is being destroyed does not
+ * invalidate the fact that this queue may have been
+ * activated during the current burst. As a consequence,
+ * although the queue does not exist anymore, and hence
+ * needs to be removed from the burst list if there,
+ * the burst size has not to be decremented.
+ */
+ hlist_del_init(&bfqq->burst_list_node);
+
bfq_log_bfqq(bfqd, bfqq, "put_queue: %p freed", bfqq);
kmem_cache_free(bfq_pool, bfqq);
@@ -6271,6 +6619,7 @@ static void bfq_init_bfqq(struct bfq_data *bfqd, struct bfq_queue *bfqq,
{
RB_CLEAR_NODE(&bfqq->entity.rb_node);
INIT_LIST_HEAD(&bfqq->fifo);
+ INIT_HLIST_NODE(&bfqq->burst_list_node);
bfqq->ref = 0;
bfqq->bfqd = bfqd;
@@ -6282,6 +6631,7 @@ static void bfq_init_bfqq(struct bfq_data *bfqd, struct bfq_queue *bfqq,
if (!bfq_class_idle(bfqq))
bfq_mark_bfqq_idle_window(bfqq);
bfq_mark_bfqq_sync(bfqq);
+ bfq_mark_bfqq_just_created(bfqq);
} else
bfq_clear_bfqq_sync(bfqq);
bfq_mark_bfqq_IO_bound(bfqq);
@@ -6551,6 +6901,7 @@ static void bfq_insert_request(struct request_queue *q, struct request *rq)
new_bfqq->allocated[rq_data_dir(rq)]++;
bfqq->allocated[rq_data_dir(rq)]--;
new_bfqq->ref++;
+ bfq_clear_bfqq_just_created(bfqq);
bfq_put_queue(bfqq);
if (bic_to_bfqq(RQ_BIC(rq), 1) == bfqq)
bfq_merge_bfqqs(bfqd, RQ_BIC(rq),
@@ -6775,12 +7126,27 @@ new_queue:
bfq_put_queue(bfqq);
bfqq = bfq_get_queue(bfqd, bio, is_sync, bic);
bic_set_bfqq(bic, bfqq, is_sync);
- if (split && is_sync)
+ if (split && is_sync) {
+ if ((bic->was_in_burst_list && bfqd->large_burst) ||
+ bic->saved_in_large_burst)
+ bfq_mark_bfqq_in_large_burst(bfqq);
+ else {
+ bfq_clear_bfqq_in_large_burst(bfqq);
+ if (bic->was_in_burst_list)
+ hlist_add_head(&bfqq->burst_list_node,
+ &bfqd->burst_list);
+ }
bfqq->split_time = jiffies;
+ }
} else {
/* If the queue was seeky for too long, break it apart. */
if (bfq_bfqq_coop(bfqq) && bfq_bfqq_split_coop(bfqq)) {
bfq_log_bfqq(bfqd, bfqq, "breaking apart bfqq");
+
+ /* Update bic before losing reference to bfqq */
+ if (bfq_bfqq_in_large_burst(bfqq))
+ bic->saved_in_large_burst = true;
+
bfqq = bfq_split_bfqq(bic, bfqq);
split = true;
if (!bfqq)
@@ -6814,6 +7180,9 @@ new_queue:
}
}
+ if (unlikely(bfq_bfqq_just_created(bfqq)))
+ bfq_handle_burst(bfqd, bfqq);
+
spin_unlock_irqrestore(q->queue_lock, flags);
return 0;
@@ -6998,6 +7367,10 @@ static int bfq_init_queue(struct request_queue *q, struct elevator_type *e)
bfqd->oom_bfqq.new_ioprio_class = IOPRIO_CLASS_BE;
bfqd->oom_bfqq.entity.new_weight =
bfq_ioprio_to_weight(bfqd->oom_bfqq.new_ioprio);
+
+ /* oom_bfqq does not participate to bursts */
+ bfq_clear_bfqq_just_created(&bfqd->oom_bfqq);
+
/*
* Trigger weight initialization, according to ioprio, at the
* oom_bfqq's first activation. The oom_bfqq's ioprio and ioprio
@@ -7028,6 +7401,7 @@ static int bfq_init_queue(struct request_queue *q, struct elevator_type *e)
INIT_LIST_HEAD(&bfqd->active_list);
INIT_LIST_HEAD(&bfqd->idle_list);
+ INIT_HLIST_HEAD(&bfqd->burst_list);
bfqd->hw_tag = -1;
@@ -7043,6 +7417,9 @@ static int bfq_init_queue(struct request_queue *q, struct elevator_type *e)
bfqd->bfq_requests_within_timer = 120;
+ bfqd->bfq_large_burst_thresh = 8;
+ bfqd->bfq_burst_interval = msecs_to_jiffies(180);
+
bfqd->low_latency = true;
/*
@@ -7455,7 +7832,7 @@ static int __init bfq_init(void)
if (ret)
goto err_pol_unreg;
- pr_info("BFQ I/O-scheduler: v7r3");
+ pr_info("BFQ I/O-scheduler: v8");
return 0;
--
1.9.1
[toc] | [prev] | [next] | [standalone]
| From | Paolo Valente <paolo.valente@linaro.org> |
|---|---|
| Date | 2016-07-27 18:20 +0200 |
| Subject | [PATCH RFC V8 16/22] block, bfq: preserve a low latency also with NCQ-capable drives |
| Message-ID | <rZzIS-1FV-51@gated-at.bofh.it> |
| In reply to | #1451384 |
I/O schedulers typically allow NCQ-capable drives to prefetch I/O
requests, as NCQ boosts the throughput exactly by prefetching and
internally reordering requests.
Unfortunately, as discussed in detail and shown experimentally in [1],
this may cause fairness and latency guarantees to be violated. The
main problem is that the internal scheduler of an NCQ-capable drive
may postpone the service of some unlucky (prefetched) requests as long
as it deems serving other requests more appropriate to boost the
throughput.
This patch addresses this issue by not disabling device idling for
weight-raised queues, even if the device supports NCQ. This allows BFQ
to start serving a new queue, and therefore allows the drive to
prefetch new requests, only after the idling timeout expires. At that
time, all the outstanding requests of the expired queue have been most
certainly served.
[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/cfq-iosched.c | 3 ++-
1 file changed, 2 insertions(+), 1 deletion(-)
diff --git a/block/cfq-iosched.c b/block/cfq-iosched.c
index bdf97bc..5207ed8 100644
--- a/block/cfq-iosched.c
+++ b/block/cfq-iosched.c
@@ -5490,7 +5490,8 @@ static void bfq_update_idle_window(struct bfq_data *bfqd,
if (atomic_read(&bic->icq.ioc->active_ref) == 0 ||
bfqd->bfq_slice_idle == 0 ||
- (bfqd->hw_tag && BFQQ_SEEKY(bfqq)))
+ (bfqd->hw_tag && BFQQ_SEEKY(bfqq) &&
+ bfqq->wr_coeff == 1))
enable_idle = 0;
else if (bfq_sample_valid(bic->ttime.ttime_samples)) {
if (bic->ttime.ttime_mean > bfqd->bfq_slice_idle &&
--
1.9.1
[toc] | [prev] | [next] | [standalone]
| From | Paolo Valente <paolo.valente@linaro.org> |
|---|---|
| Date | 2016-07-27 18:20 +0200 |
| Subject | [PATCH RFC V8 11/22] block, bfq: improve throughput boosting |
| Message-ID | <rZzIT-1FV-53@gated-at.bofh.it> |
| In reply to | #1451384 |
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/cfq-iosched.c | 83 ++++++++++++++++++++++++++---------------------------
1 file changed, 41 insertions(+), 42 deletions(-)
diff --git a/block/cfq-iosched.c b/block/cfq-iosched.c
index ea63a7a..eed1628 100644
--- a/block/cfq-iosched.c
+++ b/block/cfq-iosched.c
@@ -693,9 +693,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
@@ -3585,36 +3582,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;
@@ -3757,13 +3724,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:
/*
@@ -3775,8 +3776,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:
/*
@@ -4501,9 +4501,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;
--
1.9.1
[toc] | [prev] | [next] | [standalone]
| From | Paolo Valente <paolo.valente@linaro.org> |
|---|---|
| Date | 2016-07-27 18:20 +0200 |
| Subject | [PATCH RFC V8 15/22] block, bfq: reduce I/O latency for soft real-time applications |
| Message-ID | <rZzIT-1FV-65@gated-at.bofh.it> |
| In reply to | #1451384 |
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 | 4 +-
block/cfq-iosched.c | 334 +++++++++++++++++++++++++++++++++++++++++++++++---
2 files changed, 320 insertions(+), 18 deletions(-)
diff --git a/block/Kconfig.iosched b/block/Kconfig.iosched
index ab2dc5a..9faf738 100644
--- a/block/Kconfig.iosched
+++ b/block/Kconfig.iosched
@@ -28,8 +28,8 @@ config IOSCHED_CFQ
The CFQ I/O scheduler, now internally replaced by BFQ, tries
to distribute bandwidth among all processes according to
their weights, regardless of the device parameters and with
- any workload. It also tries to guarantee a low latency to
- interactive applications.
+ any workload. It also tries to guarantee a low latency to
+ interactive and soft real-time applications.
This is the default I/O scheduler.
diff --git a/block/cfq-iosched.c b/block/cfq-iosched.c
index ae38bfb..bdf97bc 100644
--- a/block/cfq-iosched.c
+++ b/block/cfq-iosched.c
@@ -35,9 +35,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
@@ -289,6 +290,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.
@@ -296,6 +305,16 @@ 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;
};
/**
@@ -451,6 +470,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).
@@ -462,6 +484,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.
@@ -490,6 +515,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) \
@@ -514,6 +543,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. */
@@ -3510,13 +3540,17 @@ 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) /* update wr duration */
+ bfqq->wr_cur_max_time = bfq_wr_duration(bfqd);
+ else
+ bfqq->wr_cur_max_time =
+ bfqd->bfq_wr_rt_max_time;
/*
* If needed, further reduce budget to make sure it is
@@ -3531,8 +3565,61 @@ 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 duration */
+ bfqq->wr_cur_max_time = bfq_wr_duration(bfqd);
+ else if (time_before(
+ bfqq->last_wr_start_finish +
+ bfqq->wr_cur_max_time,
+ jiffies +
+ bfqd->bfq_wr_rt_max_time) &&
+ soft_rt) {
+ /*
+ * The remaining weight-raising time is lower
+ * than bfqd->bfq_wr_rt_max_time, which means
+ * that the application is enjoying weight
+ * raising either because deemed soft-rt in
+ * the near past, or because deemed interactive
+ * a long ago.
+ * In both cases, resetting now the current
+ * remaining weight-raising time for the
+ * application to the weight-raising duration
+ * for soft rt applications would not cause any
+ * latency increase for the application (as the
+ * new duration would be higher than the
+ * remaining time).
+ *
+ * In addition, the application is now meeting
+ * the requirements for being deemed soft rt.
+ * In the end we can 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.
+ */
+ bfqq->last_wr_start_finish = jiffies;
+ bfqq->wr_cur_max_time =
+ bfqd->bfq_wr_rt_max_time;
+ }
}
}
@@ -3551,7 +3638,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
@@ -3568,12 +3655,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
@@ -3598,12 +3687,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);
/*
@@ -3680,6 +3774,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))
@@ -3920,11 +4020,17 @@ static int bfq_allow_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,
@@ -3937,6 +4043,37 @@ static void __bfq_set_in_service_queue(struct bfq_data *bfqd,
bfqd->budgets_assigned = (bfqd->budgets_assigned*7 + 256) / 8;
+ if (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.
+ */
+ bfqq->last_wr_start_finish += jiffies -
+ bfqq->budget_timeout;
+ }
+
bfq_set_budget_timeout(bfqd, bfqq);
bfq_log_bfqq(bfqd, bfqq,
"set_in_service_queue, cur-budget = %d",
@@ -4319,6 +4456,13 @@ static bool bfq_update_peak_rate(struct bfq_data *bfqd, struct bfq_queue *bfqq,
*/
if (delta_usecs > 20000) {
bool fully_sequential = bfqq->seek_history == 0;
+ /*
+ * Soft real-time queues are not good candidates for
+ * evaluating bw, as they are likely to be slow even
+ * if sequential.
+ */
+ bool non_soft_rt = bfqq->wr_coeff == 1 ||
+ bfqq->wr_cur_max_time != bfqd->bfq_wr_rt_max_time;
bool consumed_large_budget =
reason == BFQ_BFQQ_BUDGET_EXHAUSTED &&
bfqq->entity.budget >= bfqd->bfq_max_budget * 2 / 3;
@@ -4327,7 +4471,7 @@ static bool bfq_update_peak_rate(struct bfq_data *bfqd, struct bfq_queue *bfqq,
consumed_large_budget;
if (bw > bfqd->peak_rate ||
- (bfq_bfqq_sync(bfqq) && fully_sequential &&
+ (bfq_bfqq_sync(bfqq) && fully_sequential && non_soft_rt &&
served_for_long_time)) {
/*
* To smooth oscillations use a low-pass filter with
@@ -4388,6 +4532,76 @@ static bool bfq_update_peak_rate(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 + 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.
*/
@@ -4438,6 +4652,17 @@ static void bfq_bfqq_expire(struct bfq_data *bfqd,
slow = bfq_update_peak_rate(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.
@@ -4465,6 +4690,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));
@@ -5092,6 +5359,12 @@ 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();
+ /*
+ * 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;
}
@@ -5381,6 +5654,20 @@ static void bfq_completed_request(struct request_queue *q, struct request *rq)
RQ_BIC(rq)->ttime.last_end_request = jiffies;
/*
+ * 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.
*/
@@ -5728,9 +6015,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
@@ -5852,9 +6146,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 STORE_FUNCTION(__FUNC, __PTR, MIN, MAX, __CONV) \
@@ -5884,10 +6180,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, 1);
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
static ssize_t bfq_fake_lat_show(struct elevator_queue *e, char *page)
@@ -6013,8 +6313,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),
BFQ_FAKE_LAT_ATTR(target_latency),
__ATTR_NULL
@@ -6118,7 +6420,7 @@ static int __init bfq_init(void)
if (ret)
goto err_pol_unreg;
- pr_info("BFQ I/O-scheduler: v1");
+ pr_info("BFQ I/O-scheduler: v2");
return 0;
--
1.9.1
[toc] | [prev] | [next] | [standalone]
| From | Paolo Valente <paolo.valente@linaro.org> |
|---|---|
| Date | 2016-07-27 18:20 +0200 |
| Subject | [PATCH RFC V8 02/22] block, cfq: remove close-based preemption |
| Message-ID | <rZzIT-1FV-71@gated-at.bofh.it> |
| In reply to | #1451384 |
From: Arianna Avanzini <avanzini.arianna@gmail.com>
CFQ may preempt the queue currently in service if a new request, for a
different queue, happens to be close to the last-dispatched
request. This boosts the throughput with processes that issue close
requests, but whose I/O patterns are not regularly interleaved enough
to trigger the activation of the queue-merging heuristic removed in
the previous commit. BFQ does not need to perform any such preemption,
because the queue-merging mechanism of BFQ (EQM) is reactive enough to
merge queues also in the presence of irregularly interleaved I/O.
Signed-off-by: Arianna Avanzini <avanzini.arianna@gmail.com>
Signed-off-by: Paolo Valente <paolo.valente@linaro.org>
---
block/cfq-iosched.c | 13 -------------
1 file changed, 13 deletions(-)
diff --git a/block/cfq-iosched.c b/block/cfq-iosched.c
index 18a7291..1b9fa10 100644
--- a/block/cfq-iosched.c
+++ b/block/cfq-iosched.c
@@ -2677,12 +2677,6 @@ static inline sector_t cfq_dist_from_last(struct cfq_data *cfqd,
return cfqd->last_position - blk_rq_pos(rq);
}
-static inline int cfq_rq_close(struct cfq_data *cfqd, struct cfq_queue *cfqq,
- struct request *rq)
-{
- return cfq_dist_from_last(cfqd, rq) <= CFQQ_CLOSE_THR;
-}
-
/*
* Determine whether we should enforce idle window for this queue.
*/
@@ -3724,13 +3718,6 @@ cfq_should_preempt(struct cfq_data *cfqd, struct cfq_queue *new_cfqq,
if (!cfqd->active_cic || !cfq_cfqq_wait_request(cfqq))
return false;
- /*
- * if this request is as-good as one we would expect from the
- * current cfqq, let it preempt
- */
- if (cfq_rq_close(cfqd, cfqq, rq))
- return true;
-
return false;
}
--
1.9.1
[toc] | [prev] | [next] | [standalone]
| From | Paolo Valente <paolo.valente@linaro.org> |
|---|---|
| Date | 2016-07-27 18:20 +0200 |
| Subject | [PATCH RFC V8 21/22] block, bfq: boost the throughput with random I/O on NCQ-capable HDDs |
| Message-ID | <rZzIT-1FV-67@gated-at.bofh.it> |
| In reply to | #1451384 |
This patch is basically the counterpart, for NCQ-capable rotational
devices, of the previous patch. Exactly as the previous patch does on
flash-based devices and for any workload, this patch disables device
idling on rotational devices, but only for random I/O. In fact, only
with these queues disabling idling boosts the throughput on
NCQ-capable rotational devices. To not break service guarantees,
idling is disabled for NCQ-enabled rotational devices only when the
same symmetry conditions considered in the previous patches hold.
Signed-off-by: Paolo Valente <paolo.valente@linaro.org>
Signed-off-by: Arianna Avanzini <avanzini.arianna@gmail.com>
---
block/cfq-iosched.c | 22 ++++++++++------------
1 file changed, 10 insertions(+), 12 deletions(-)
diff --git a/block/cfq-iosched.c b/block/cfq-iosched.c
index 7fee23b..ae17421 100644
--- a/block/cfq-iosched.c
+++ b/block/cfq-iosched.c
@@ -38,7 +38,9 @@
* 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.
+ * these classes with a very low latency. Finally, BFQ also features
+ * additional heuristics for preserving both a low latency and a high
+ * throughput on NCQ-capable, rotational or flash-based devices.
*
* With respect to the version of BFQ presented in [1], and in the
* papers cited therein, this implementation adds a hierarchical
@@ -5629,20 +5631,15 @@ static bool bfq_bfqq_may_idle(struct bfq_queue *bfqq)
* The next variable takes into account the cases where idling
* boosts the throughput.
*
- * The value of the variable is computed considering that
- * idling is usually beneficial for the throughput if:
+ * The value of the variable is computed considering, first, that
+ * idling is virtually always beneficial for the throughput if:
* (a) the device is not NCQ-capable, or
* (b) regardless of the presence of NCQ, the device is rotational
- * and the request pattern for bfqq is I/O-bound (possible
- * throughput losses caused by granting idling to seeky queues
- * are mitigated by the fact that, in all scenarios where
- * boosting throughput is the best thing to do, i.e., in all
- * symmetric scenarios, only a minimal idle time is allowed to
- * seeky queues).
+ * and the request pattern for bfqq is I/O-bound and sequential.
*
* Secondly, and in contrast to the above item (b), idling an
* NCQ-capable flash-based device would not boost the
- * throughput even with intense I/O; rather it would lower
+ * throughput even with sequential I/O; rather it would lower
* the throughput in proportion to how fast the device
* is. Accordingly, the next variable is true if any of the
* above conditions (a) and (b) is true, and, in particular,
@@ -5650,7 +5647,8 @@ static bool bfq_bfqq_may_idle(struct bfq_queue *bfqq)
* device.
*/
idling_boosts_thr = !bfqd->hw_tag ||
- (!blk_queue_nonrot(bfqd->queue) && bfq_bfqq_IO_bound(bfqq));
+ (!blk_queue_nonrot(bfqd->queue) && bfq_bfqq_IO_bound(bfqq) &&
+ bfq_bfqq_idle_window(bfqq));
/*
* The value of the next variable,
@@ -7457,7 +7455,7 @@ static int __init bfq_init(void)
if (ret)
goto err_pol_unreg;
- pr_info("BFQ I/O-scheduler: v6");
+ pr_info("BFQ I/O-scheduler: v7r3");
return 0;
--
1.9.1
[toc] | [prev] | [next] | [standalone]
| From | Paolo Valente <paolo.valente@linaro.org> |
|---|---|
| Date | 2016-07-27 18:20 +0200 |
| Subject | [PATCH RFC V8 18/22] block, bfq: add Early Queue Merge (EQM) |
| Message-ID | <rZzIT-1FV-61@gated-at.bofh.it> |
| In reply to | #1451384 |
From: Arianna Avanzini <avanzini.arianna@gmail.com>
A set of processes may happen to perform interleaved reads, i.e.,
read requests whose union would give rise to a sequential read pattern.
There are two typical cases: first, processes reading fixed-size chunks
of data at a fixed distance from each other; second, processes reading
variable-size chunks at variable distances. The latter case occurs for
example with QEMU, which splits the I/O generated by a guest into
multiple chunks, and lets these chunks be served by a pool of I/O
threads, iteratively assigning the next chunk of I/O to the first
available thread. CFQ denotes as 'cooperating' a set of processes that
are doing interleaved I/O, and when it detects cooperating processes,
it merges their queues to obtain a sequential I/O pattern from the union
of their I/O requests, and hence boost the throughput.
Unfortunately, in the following frequent case, the mechanism
implemented in CFQ for detecting cooperating processes and merging
their queues is not responsive enough to handle also the fluctuating
I/O pattern of the second type of processes. Suppose that one process
of the second type issues a request close to the next request to serve
of another process of the same type. At that time the two processes
would be considered as cooperating. But, if the request issued by the
first process is to be merged with some other already-queued request,
then, from the moment at which this request arrives, to the moment
when CFQ controls whether the two processes are cooperating, the two
processes are likely to be already doing I/O in distant zones of the
disk surface or device memory.
CFQ uses however preemption to get a sequential read pattern out of
the read requests performed by the second type of processes too. As a
consequence, CFQ uses two different mechanisms to achieve the same
goal: boosting the throughput with interleaved I/O.
This patch introduces Early Queue Merge (EQM), a unified mechanism to
get a sequential read pattern with both types of processes. The main
idea is to immediately check whether a newly-arrived request lets some
pair of processes become cooperating, both in the case of actual
request insertion and, to be responsive with the second type of
processes, in the case of request merge. Both types of processes are
then handled by just merging their queues.
Signed-off-by: Arianna Avanzini <avanzini.arianna@gmail.com>
Signed-off-by: Mauro Andreolini <mauro.andreolini@unimore.it>
Signed-off-by: Paolo Valente <paolo.valente@linaro.org>
---
block/cfq-iosched.c | 738 +++++++++++++++++++++++++++++++++++++++++++++++++---
1 file changed, 707 insertions(+), 31 deletions(-)
diff --git a/block/cfq-iosched.c b/block/cfq-iosched.c
index 980d321..27b51a7 100644
--- a/block/cfq-iosched.c
+++ b/block/cfq-iosched.c
@@ -225,11 +225,12 @@ struct bfq_group;
* struct bfq_queue - leaf schedulable entity.
*
* A bfq_queue is a leaf request queue; it can be associated with an
- * io_context or more, if it is async. @cgroup holds a reference to
- * the cgroup, to be sure that it does not disappear while a bfqq
- * still references it (mostly to avoid races between request issuing
- * and task migration followed by cgroup destruction). All the fields
- * are protected by the queue lock of the containing bfqd.
+ * io_context or more, if it is async or shared between cooperating
+ * processes. @cgroup holds a reference to the cgroup, to be sure that it
+ * does not disappear while a bfqq still references it (mostly to avoid
+ * races between request issuing and task migration followed by cgroup
+ * destruction).
+ * All the fields are protected by the queue lock of the containing bfqd.
*/
struct bfq_queue {
/* reference counter */
@@ -242,6 +243,16 @@ struct bfq_queue {
/* next ioprio and ioprio class if a change is in progress */
unsigned short new_ioprio, new_ioprio_class;
+ /*
+ * Shared bfq_queue if queue is cooperating with one or more
+ * other queues.
+ */
+ struct bfq_queue *new_bfqq;
+ /* request-position tree member (see bfq_group's @rq_pos_tree) */
+ struct rb_node pos_node;
+ /* request-position tree root (see bfq_group's @rq_pos_tree) */
+ struct rb_root *pos_root;
+
/* sorted list of pending requests */
struct rb_root sort_list;
/* if fifo isn't expired, next request to serve */
@@ -287,6 +298,12 @@ struct bfq_queue {
/* pid of the process owning the queue, used for logging purposes */
pid_t pid;
+ /*
+ * Pointer to the bfq_io_cq owning the bfq_queue, set to %NULL
+ * if the queue is shared.
+ */
+ struct bfq_io_cq *bic;
+
/* current maximum weight-raising time for this queue */
unsigned long wr_cur_max_time;
/*
@@ -315,6 +332,8 @@ struct bfq_queue {
* last transition from idle to backlogged.
*/
unsigned long service_from_backlogged;
+
+ unsigned long split_time; /* time of last split */
};
/**
@@ -344,6 +363,18 @@ struct bfq_io_cq {
#ifdef CONFIG_CFQ_GROUP_IOSCHED
uint64_t blkcg_serial_nr; /* the current blkcg serial */
#endif
+
+ /*
+ * Snapshot of the idle window before merging; taken to
+ * remember this value while the queue is merged, so as to be
+ * able to restore it in case of split.
+ */
+ bool saved_idle_window;
+ /*
+ * Same purpose as the previous two fields for the I/O bound
+ * classification of a queue.
+ */
+ bool saved_IO_bound;
};
enum bfq_device_speed {
@@ -521,6 +552,8 @@ enum bfqq_state_flags {
* may need softrt-next-start
* update
*/
+ BFQ_BFQQ_FLAG_coop, /* bfqq is shared */
+ BFQ_BFQQ_FLAG_split_coop /* shared bfqq will be split */
};
#define BFQ_BFQQ_FNS(name) \
@@ -545,6 +578,8 @@ BFQ_BFQQ_FNS(fifo_expire);
BFQ_BFQQ_FNS(idle_window);
BFQ_BFQQ_FNS(sync);
BFQ_BFQQ_FNS(IO_bound);
+BFQ_BFQQ_FNS(coop);
+BFQ_BFQQ_FNS(split_coop);
BFQ_BFQQ_FNS(softrt_update);
#undef BFQ_BFQQ_FNS
@@ -657,6 +692,9 @@ struct bfq_group_data {
* to avoid too many special cases during group creation/
* migration.
* @stats: stats for this bfqg.
+ * @rq_pos_tree: rbtree sorted by next_request position, used when
+ * determining if two or more queues have interleaving
+ * requests (see bfq_find_close_cooperator()).
*
* Each (device, cgroup) pair has its own bfq_group, i.e., for each cgroup
* there is a set of bfq_groups, each one collecting the lower-level
@@ -681,6 +719,8 @@ struct bfq_group {
struct bfq_entity *my_entity;
+ struct rb_root rq_pos_tree;
+
struct bfqg_stats stats;
};
@@ -724,6 +764,27 @@ static struct bfq_data *bic_to_bfqd(struct bfq_io_cq *bic)
return bic->icq.q->elevator->elevator_data;
}
+#ifdef CONFIG_CFQ_GROUP_IOSCHED
+
+static struct bfq_group *bfq_bfqq_to_bfqg(struct bfq_queue *bfqq)
+{
+ struct bfq_entity *group_entity = bfqq->entity.parent;
+
+ if (!group_entity)
+ group_entity = &bfqq->bfqd->root_group->entity;
+
+ return container_of(group_entity, struct bfq_group, entity);
+}
+
+#else
+
+static struct bfq_group *bfq_bfqq_to_bfqg(struct bfq_queue *bfqq)
+{
+ return bfqq->bfqd->root_group;
+}
+
+#endif
+
static void bfq_check_ioprio_change(struct bfq_io_cq *bic, struct bio *bio);
static void bfq_put_queue(struct bfq_queue *bfqq);
static void bfq_dispatch_insert(struct request_queue *q, struct request *rq);
@@ -773,6 +834,7 @@ struct kmem_cache *bfq_pool;
#define BFQ_HW_QUEUE_SAMPLES 32
#define BFQQ_SEEK_THR (sector_t)(8 * 100)
+#define BFQQ_CLOSE_THR (sector_t)(8 * 1024)
#define BFQQ_SEEKY(bfqq) (hweight32(bfqq->seek_history) > 32/8)
/* Min samples used for peak rate estimation (for autotuning). */
@@ -2428,6 +2490,7 @@ static void bfq_pd_init(struct blkg_policy_data *pd)
* in bfq_init_queue()
*/
bfqg->bfqd = bfqd;
+ bfqg->rq_pos_tree = RB_ROOT;
}
static void bfq_pd_free(struct blkg_policy_data *pd)
@@ -2496,12 +2559,13 @@ static struct bfq_group *bfq_find_alloc_group(struct bfq_data *bfqd,
return bfqg;
}
+static void bfq_pos_tree_add_move(struct bfq_data *bfqd,
+ struct bfq_queue *bfqq);
static void bfq_bfqq_expire(struct bfq_data *bfqd,
struct bfq_queue *bfqq,
bool compensate,
enum bfqq_expiration reason);
-
/**
* bfq_bfqq_move - migrate @bfqq to @bfqg.
* @bfqd: queue descriptor.
@@ -2545,8 +2609,10 @@ static void bfq_bfqq_move(struct bfq_data *bfqd, struct bfq_queue *bfqq,
entity->sched_data = &bfqg->sched_data;
bfqg_get(bfqg);
- if (bfq_bfqq_busy(bfqq))
+ if (bfq_bfqq_busy(bfqq)) {
+ bfq_pos_tree_add_move(bfqd, bfqq);
bfq_activate_bfqq(bfqd, bfqq);
+ }
if (!bfqd->in_service_queue && !bfqd->rq_in_driver)
bfq_schedule_dispatch(bfqd);
@@ -2584,8 +2650,7 @@ static struct bfq_group *__bfq_bic_change_cgroup(struct bfq_data *bfqd,
bic_set_bfqq(bic, NULL, 0);
bfq_log_bfqq(bfqd, async_bfqq,
"bic_change_group: %p %d",
- async_bfqq,
- async_bfqq->ref);
+ async_bfqq, async_bfqq->ref);
bfq_put_queue(async_bfqq);
}
}
@@ -3266,6 +3331,72 @@ static struct request *bfq_choose_req(struct bfq_data *bfqd,
}
}
+static struct bfq_queue *
+bfq_rq_pos_tree_lookup(struct bfq_data *bfqd, struct rb_root *root,
+ sector_t sector, struct rb_node **ret_parent,
+ struct rb_node ***rb_link)
+{
+ struct rb_node **p, *parent;
+ struct bfq_queue *bfqq = NULL;
+
+ parent = NULL;
+ p = &root->rb_node;
+ while (*p) {
+ struct rb_node **n;
+
+ parent = *p;
+ bfqq = rb_entry(parent, struct bfq_queue, pos_node);
+
+ /*
+ * Sort strictly based on sector. Smallest to the left,
+ * largest to the right.
+ */
+ if (sector > blk_rq_pos(bfqq->next_rq))
+ n = &(*p)->rb_right;
+ else if (sector < blk_rq_pos(bfqq->next_rq))
+ n = &(*p)->rb_left;
+ else
+ break;
+ p = n;
+ bfqq = NULL;
+ }
+
+ *ret_parent = parent;
+ if (rb_link)
+ *rb_link = p;
+
+ bfq_log(bfqd, "rq_pos_tree_lookup %llu: returning %d",
+ (unsigned long long)sector,
+ bfqq ? bfqq->pid : 0);
+
+ return bfqq;
+}
+
+static void bfq_pos_tree_add_move(struct bfq_data *bfqd, struct bfq_queue *bfqq)
+{
+ struct rb_node **p, *parent;
+ struct bfq_queue *__bfqq;
+
+ if (bfqq->pos_root) {
+ rb_erase(&bfqq->pos_node, bfqq->pos_root);
+ bfqq->pos_root = NULL;
+ }
+
+ if (bfq_class_idle(bfqq))
+ return;
+ if (!bfqq->next_rq)
+ return;
+
+ bfqq->pos_root = &bfq_bfqq_to_bfqg(bfqq)->rq_pos_tree;
+ __bfqq = bfq_rq_pos_tree_lookup(bfqd, bfqq->pos_root,
+ blk_rq_pos(bfqq->next_rq), &parent, &p);
+ if (!__bfqq) {
+ rb_link_node(&bfqq->pos_node, parent, p);
+ rb_insert_color(&bfqq->pos_node, bfqq->pos_root);
+ } else
+ bfqq->pos_root = NULL;
+}
+
static struct request *bfq_find_next_rq(struct bfq_data *bfqd,
struct bfq_queue *bfqq,
struct request *last)
@@ -3345,6 +3476,32 @@ static void bfq_updated_next_req(struct bfq_data *bfqd,
}
}
+static void
+bfq_bfqq_resume_state(struct bfq_queue *bfqq, struct bfq_io_cq *bic)
+{
+ if (bic->saved_idle_window)
+ bfq_mark_bfqq_idle_window(bfqq);
+ else
+ bfq_clear_bfqq_idle_window(bfqq);
+
+ if (bic->saved_IO_bound)
+ bfq_mark_bfqq_IO_bound(bfqq);
+ else
+ bfq_clear_bfqq_IO_bound(bfqq);
+}
+
+static int bfqq_process_refs(struct bfq_queue *bfqq)
+{
+ int process_refs, io_refs;
+
+ lockdep_assert_held(bfqq->bfqd->queue->queue_lock);
+
+ io_refs = bfqq->allocated[READ] + bfqq->allocated[WRITE];
+ process_refs = bfqq->ref - io_refs - bfqq->entity.on_st;
+
+ return process_refs;
+}
+
static int bfq_bfqq_budget_left(struct bfq_queue *bfqq)
{
struct bfq_entity *entity = &bfqq->entity;
@@ -3672,14 +3829,16 @@ 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 or is soft real-time.
+ * - it has been idle for enough time or is soft real-time,
+ * - is linked to a bfq_io_cq (it is not shared in any sense).
*/
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 || soft_rt)));
+ (bfq_bfqq_sync(bfqq) &&
+ bfqq->bic && (*interactive || soft_rt)));
/*
* Using the last flag, update budget and check whether bfqq
@@ -3701,14 +3860,22 @@ static void bfq_bfqq_handle_idle_busy_switch(struct bfq_data *bfqd,
}
if (bfqd->low_latency) {
- bfq_update_bfqq_wr_on_rq_arrival(bfqd, bfqq,
- old_wr_coeff,
- wr_or_deserves_wr,
- *interactive,
- soft_rt);
-
- if (old_wr_coeff != bfqq->wr_coeff)
- bfqq->entity.prio_changed = 1;
+ if (unlikely(time_is_after_jiffies(bfqq->split_time)))
+ /* wraparound */
+ bfqq->split_time =
+ jiffies - bfqd->bfq_wr_min_idle_time - 1;
+
+ if (time_is_before_jiffies(bfqq->split_time +
+ bfqd->bfq_wr_min_idle_time)) {
+ bfq_update_bfqq_wr_on_rq_arrival(bfqd, bfqq,
+ old_wr_coeff,
+ wr_or_deserves_wr,
+ *interactive,
+ soft_rt);
+
+ if (old_wr_coeff != bfqq->wr_coeff)
+ bfqq->entity.prio_changed = 1;
+ }
}
bfqq->last_idle_bklogged = jiffies;
@@ -3755,6 +3922,12 @@ static void bfq_add_request(struct request *rq)
next_rq = bfq_choose_req(bfqd, bfqq->next_rq, rq, bfqd->last_position);
bfqq->next_rq = next_rq;
+ /*
+ * Adjust priority tree position, if next_rq changes.
+ */
+ if (prev != bfqq->next_rq)
+ bfq_pos_tree_add_move(bfqd, bfqq);
+
if (!bfq_bfqq_busy(bfqq)) /* switching to busy ... */
bfq_bfqq_handle_idle_busy_switch(bfqd, bfqq, old_wr_coeff,
rq, &interactive);
@@ -3873,6 +4046,14 @@ static void bfq_remove_request(struct request *rq)
*/
bfqq->entity.budget = bfqq->entity.service = 0;
}
+
+ /*
+ * Remove queue from request-position tree as it is empty.
+ */
+ if (bfqq->pos_root) {
+ rb_erase(&bfqq->pos_node, bfqq->pos_root);
+ bfqq->pos_root = NULL;
+ }
}
if (rq->cmd_flags & REQ_META)
@@ -3917,11 +4098,14 @@ static void bfq_merged_request(struct request_queue *q, struct request *req,
bfqd->last_position);
bfqq->next_rq = next_rq;
/*
- * If next_rq changes, update the queue's budget to fit
- * the new request.
+ * If next_rq changes, update both the queue's budget to
+ * fit the new request and the queue's position in its
+ * rq_pos_tree.
*/
- if (prev != bfqq->next_rq)
+ if (prev != bfqq->next_rq) {
bfq_updated_next_req(bfqd, bfqq);
+ bfq_pos_tree_add_move(bfqd, bfqq);
+ }
}
}
@@ -4004,12 +4188,354 @@ static void bfq_end_wr(struct bfq_data *bfqd)
spin_unlock_irq(bfqd->queue->queue_lock);
}
+static sector_t bfq_io_struct_pos(void *io_struct, bool request)
+{
+ if (request)
+ return blk_rq_pos(io_struct);
+ else
+ return ((struct bio *)io_struct)->bi_iter.bi_sector;
+}
+
+static int bfq_rq_close_to_sector(void *io_struct, bool request,
+ sector_t sector)
+{
+ return abs(bfq_io_struct_pos(io_struct, request) - sector) <=
+ BFQQ_CLOSE_THR;
+}
+
+static struct bfq_queue *bfqq_find_close(struct bfq_data *bfqd,
+ struct bfq_queue *bfqq,
+ sector_t sector)
+{
+ struct rb_root *root = &bfq_bfqq_to_bfqg(bfqq)->rq_pos_tree;
+ struct rb_node *parent, *node;
+ struct bfq_queue *__bfqq;
+
+ if (RB_EMPTY_ROOT(root))
+ return NULL;
+
+ /*
+ * First, if we find a request starting at the end of the last
+ * request, choose it.
+ */
+ __bfqq = bfq_rq_pos_tree_lookup(bfqd, root, sector, &parent, NULL);
+ if (__bfqq)
+ return __bfqq;
+
+ /*
+ * If the exact sector wasn't found, the parent of the NULL leaf
+ * will contain the closest sector (rq_pos_tree sorted by
+ * next_request position).
+ */
+ __bfqq = rb_entry(parent, struct bfq_queue, pos_node);
+ if (bfq_rq_close_to_sector(__bfqq->next_rq, true, sector))
+ return __bfqq;
+
+ if (blk_rq_pos(__bfqq->next_rq) < sector)
+ node = rb_next(&__bfqq->pos_node);
+ else
+ node = rb_prev(&__bfqq->pos_node);
+ if (!node)
+ return NULL;
+
+ __bfqq = rb_entry(node, struct bfq_queue, pos_node);
+ if (bfq_rq_close_to_sector(__bfqq->next_rq, true, sector))
+ return __bfqq;
+
+ return NULL;
+}
+
+static struct bfq_queue *bfq_find_close_cooperator(struct bfq_data *bfqd,
+ struct bfq_queue *cur_bfqq,
+ sector_t sector)
+{
+ struct bfq_queue *bfqq;
+
+ /*
+ * We shall notice if some of the queues are cooperating,
+ * e.g., working closely on the same area of the device. In
+ * that case, we can group them together and: 1) don't waste
+ * time idling, and 2) serve the union of their requests in
+ * the best possible order for throughput.
+ */
+ bfqq = bfqq_find_close(bfqd, cur_bfqq, sector);
+ if (!bfqq || bfqq == cur_bfqq)
+ return NULL;
+
+ return bfqq;
+}
+
+static struct bfq_queue *
+bfq_setup_merge(struct bfq_queue *bfqq, struct bfq_queue *new_bfqq)
+{
+ int process_refs, new_process_refs;
+ struct bfq_queue *__bfqq;
+
+ /*
+ * If there are no process references on the new_bfqq, then it is
+ * unsafe to follow the ->new_bfqq chain as other bfqq's in the chain
+ * may have dropped their last reference (not just their last process
+ * reference).
+ */
+ if (!bfqq_process_refs(new_bfqq))
+ return NULL;
+
+ /* Avoid a circular list and skip interim queue merges. */
+ while ((__bfqq = new_bfqq->new_bfqq)) {
+ if (__bfqq == bfqq)
+ return NULL;
+ new_bfqq = __bfqq;
+ }
+
+ process_refs = bfqq_process_refs(bfqq);
+ new_process_refs = bfqq_process_refs(new_bfqq);
+ /*
+ * If the process for the bfqq has gone away, there is no
+ * sense in merging the queues.
+ */
+ if (process_refs == 0 || new_process_refs == 0)
+ return NULL;
+
+ bfq_log_bfqq(bfqq->bfqd, bfqq, "scheduling merge with queue %d",
+ new_bfqq->pid);
+
+ /*
+ * Merging is just a redirection: the requests of the process
+ * owning one of the two queues are redirected to the other queue.
+ * The latter queue, in its turn, is set as shared if this is the
+ * first time that the requests of some process are redirected to
+ * it.
+ *
+ * We redirect bfqq to new_bfqq and not the opposite, because we
+ * are in the context of the process owning bfqq, hence we have
+ * the io_cq of this process. So we can immediately configure this
+ * io_cq to redirect the requests of the process to new_bfqq.
+ *
+ * NOTE, even if new_bfqq coincides with the in-service queue, the
+ * io_cq of new_bfqq is not available, because, if the in-service
+ * queue is shared, bfqd->in_service_bic may not point to the
+ * io_cq of the in-service queue.
+ * Redirecting the requests of the process owning bfqq to the
+ * currently in-service queue is in any case the best option, as
+ * we feed the in-service queue with new requests close to the
+ * last request served and, by doing so, hopefully increase the
+ * throughput.
+ */
+ bfqq->new_bfqq = new_bfqq;
+ new_bfqq->ref += process_refs;
+ return new_bfqq;
+}
+
+static bool bfq_may_be_close_cooperator(struct bfq_queue *bfqq,
+ struct bfq_queue *new_bfqq)
+{
+ if (bfq_class_idle(bfqq) || bfq_class_idle(new_bfqq) ||
+ (bfqq->ioprio_class != new_bfqq->ioprio_class))
+ return false;
+
+ /*
+ * If either of the queues has already been detected as seeky,
+ * then merging it with the other queue is unlikely to lead to
+ * sequential I/O.
+ */
+ if (BFQQ_SEEKY(bfqq) || BFQQ_SEEKY(new_bfqq))
+ return false;
+
+ /*
+ * Interleaved I/O is known to be done by (some) applications
+ * only for reads, so it does not make sense to merge async
+ * queues.
+ */
+ if (!bfq_bfqq_sync(bfqq) || !bfq_bfqq_sync(new_bfqq))
+ return false;
+
+ return true;
+}
+
+/*
+ * If this function returns true, then bfqq cannot be merged. The idea
+ * is that true cooperation happens very early after processes start
+ * to do I/O. Usually, late cooperations are just accidental false
+ * positives. In case bfqq is weight-raised, such false positives
+ * would evidently degrade latency guarantees for bfqq.
+ */
+bool wr_from_too_long(struct bfq_queue *bfqq)
+{
+ return bfqq->wr_coeff > 1 &&
+ time_is_before_jiffies(bfqq->last_wr_start_finish +
+ msecs_to_jiffies(100));
+}
+
+/*
+ * Attempt to schedule a merge of bfqq with the currently in-service
+ * queue or with a close queue among the scheduled queues. Return
+ * NULL if no merge was scheduled, a pointer to the shared bfq_queue
+ * structure otherwise.
+ *
+ * The OOM queue is not allowed to participate to cooperation: in fact, since
+ * the requests temporarily redirected to the OOM queue could be redirected
+ * again to dedicated queues at any time, the state needed to correctly
+ * handle merging with the OOM queue would be quite complex and expensive
+ * to maintain. Besides, in such a critical condition as an out of memory,
+ * the benefits of queue merging may be little relevant, or even negligible.
+ *
+ * Weight-raised queues can be merged only if their weight-raising
+ * period has just started. In fact cooperating processes are usually
+ * started together. Thus, with this filter we avoid false positives
+ * that would jeopardize low-latency guarantees.
+ *
+ * WARNING: queue merging may impair fairness among non-weight raised
+ * queues, for at least two reasons: 1) the original weight of a
+ * merged queue may change during the merged state, 2) even being the
+ * weight the same, a merged queue may be bloated with many more
+ * requests than the ones produced by its originally-associated
+ * process.
+ */
+static struct bfq_queue *
+bfq_setup_cooperator(struct bfq_data *bfqd, struct bfq_queue *bfqq,
+ void *io_struct, bool request)
+{
+ struct bfq_queue *in_service_bfqq, *new_bfqq;
+
+ if (bfqq->new_bfqq)
+ return bfqq->new_bfqq;
+
+ if (!io_struct ||
+ wr_from_too_long(bfqq) ||
+ unlikely(bfqq == &bfqd->oom_bfqq))
+ return NULL;
+
+ /* If there is only one backlogged queue, don't search. */
+ if (bfqd->busy_queues == 1)
+ return NULL;
+
+ in_service_bfqq = bfqd->in_service_queue;
+
+ if (!in_service_bfqq || in_service_bfqq == bfqq ||
+ !bfqd->in_service_bic || wr_from_too_long(in_service_bfqq) ||
+ unlikely(in_service_bfqq == &bfqd->oom_bfqq))
+ goto check_scheduled;
+
+ if (bfq_rq_close_to_sector(io_struct, request, bfqd->last_position) &&
+ bfqq->entity.parent == in_service_bfqq->entity.parent &&
+ bfq_may_be_close_cooperator(bfqq, in_service_bfqq)) {
+ new_bfqq = bfq_setup_merge(bfqq, in_service_bfqq);
+ if (new_bfqq)
+ return new_bfqq;
+ }
+ /*
+ * Check whether there is a cooperator among currently scheduled
+ * queues. The only thing we need is that the bio/request is not
+ * NULL, as we need it to establish whether a cooperator exists.
+ */
+check_scheduled:
+ new_bfqq = bfq_find_close_cooperator(bfqd, bfqq,
+ bfq_io_struct_pos(io_struct, request));
+
+ if (new_bfqq && !wr_from_too_long(new_bfqq) &&
+ likely(new_bfqq != &bfqd->oom_bfqq) &&
+ bfq_may_be_close_cooperator(bfqq, new_bfqq))
+ return bfq_setup_merge(bfqq, new_bfqq);
+
+ return NULL;
+}
+
+static void bfq_bfqq_save_state(struct bfq_queue *bfqq)
+{
+ /*
+ * If !bfqq->bic, the queue is already shared or its requests
+ * have already been redirected to a shared queue; both idle window
+ * and weight raising state have already been saved. Do nothing.
+ */
+ if (!bfqq->bic)
+ return;
+
+ bfqq->bic->saved_idle_window = bfq_bfqq_idle_window(bfqq);
+ bfqq->bic->saved_IO_bound = bfq_bfqq_IO_bound(bfqq);
+}
+
+static void bfq_get_bic_reference(struct bfq_queue *bfqq)
+{
+ /*
+ * If bfqq->bic has a non-NULL value, the bic to which it belongs
+ * is about to begin using a shared bfq_queue.
+ */
+ if (bfqq->bic)
+ atomic_long_inc(&bfqq->bic->icq.ioc->refcount);
+}
+
+static void
+bfq_merge_bfqqs(struct bfq_data *bfqd, struct bfq_io_cq *bic,
+ struct bfq_queue *bfqq, struct bfq_queue *new_bfqq)
+{
+ bfq_log_bfqq(bfqd, bfqq, "merging with queue %lu",
+ (unsigned long)new_bfqq->pid);
+ /* Save weight raising and idle window of the merged queues */
+ bfq_bfqq_save_state(bfqq);
+ bfq_bfqq_save_state(new_bfqq);
+ if (bfq_bfqq_IO_bound(bfqq))
+ bfq_mark_bfqq_IO_bound(new_bfqq);
+ bfq_clear_bfqq_IO_bound(bfqq);
+
+ /*
+ * If bfqq is weight-raised, then let new_bfqq inherit
+ * weight-raising. To reduce false positives, neglect the case
+ * where bfqq has just been created, but has not yet made it
+ * to be weight-raised (which may happen because EQM may merge
+ * bfqq even before bfq_add_request is executed for the first
+ * time for bfqq).
+ */
+ if (new_bfqq->wr_coeff == 1 && bfqq->wr_coeff > 1) {
+ new_bfqq->wr_coeff = bfqq->wr_coeff;
+ new_bfqq->wr_cur_max_time = bfqq->wr_cur_max_time;
+ new_bfqq->last_wr_start_finish = bfqq->last_wr_start_finish;
+ if (bfq_bfqq_busy(new_bfqq))
+ bfqd->wr_busy_queues++;
+ new_bfqq->entity.prio_changed = 1;
+ }
+
+ if (bfqq->wr_coeff > 1) { /* bfqq has given its wr to new_bfqq */
+ bfqq->wr_coeff = 1;
+ bfqq->entity.prio_changed = 1;
+ if (bfq_bfqq_busy(bfqq))
+ bfqd->wr_busy_queues--;
+ }
+
+ bfq_log_bfqq(bfqd, new_bfqq, "merge_bfqqs: wr_busy %d",
+ bfqd->wr_busy_queues);
+
+ /*
+ * Grab a reference to the bic, to prevent it from being destroyed
+ * before being possibly touched by a bfq_split_bfqq().
+ */
+ bfq_get_bic_reference(bfqq);
+ bfq_get_bic_reference(new_bfqq);
+ /*
+ * Merge queues (that is, let bic redirect its requests to new_bfqq)
+ */
+ bic_set_bfqq(bic, new_bfqq, 1);
+ bfq_mark_bfqq_coop(new_bfqq);
+ /*
+ * new_bfqq now belongs to at least two bics (it is a shared queue):
+ * set new_bfqq->bic to NULL. bfqq either:
+ * - does not belong to any bic any more, and hence bfqq->bic must
+ * be set to NULL, or
+ * - is a queue whose owning bics have already been redirected to a
+ * different queue, hence the queue is destined to not belong to
+ * any bic soon and bfqq->bic is already NULL (therefore the next
+ * assignment causes no harm).
+ */
+ new_bfqq->bic = NULL;
+ bfqq->bic = NULL;
+ bfq_put_queue(bfqq);
+}
+
static int bfq_allow_merge(struct request_queue *q, struct request *rq,
struct bio *bio)
{
struct bfq_data *bfqd = q->elevator->elevator_data;
struct bfq_io_cq *bic;
- struct bfq_queue *bfqq;
+ struct bfq_queue *bfqq, *new_bfqq;
/*
* Disallow merge of a sync bio into an async request.
@@ -4027,6 +4553,22 @@ static int bfq_allow_merge(struct request_queue *q, struct request *rq,
return 0;
bfqq = bic_to_bfqq(bic, bfq_bio_sync(bio));
+ /*
+ * We take advantage of this function to perform an early merge
+ * of the queues of possible cooperating processes.
+ */
+ if (bfqq) {
+ new_bfqq = bfq_setup_cooperator(bfqd, bfqq, bio, false);
+ if (new_bfqq) {
+ bfq_merge_bfqqs(bfqd, bic, bfqq, new_bfqq);
+ /*
+ * If we get here, the bio will be queued in the
+ * shared queue, i.e., new_bfqq, so use new_bfqq
+ * to decide whether bio and rq can be merged.
+ */
+ bfqq = new_bfqq;
+ }
+ }
return bfqq == RQ_BFQQ(rq);
}
@@ -4200,6 +4742,15 @@ static void __bfq_bfqq_expire(struct bfq_data *bfqd, struct bfq_queue *bfqq)
{
__bfq_bfqd_reset_in_service(bfqd);
+ /*
+ * If this bfqq is shared between multiple processes, check
+ * to make sure that those processes are still issuing I/Os
+ * within the mean seek distance. If not, it may be time to
+ * break the queues apart again.
+ */
+ if (bfq_bfqq_coop(bfqq) && BFQQ_SEEKY(bfqq))
+ bfq_mark_bfqq_split_coop(bfqq);
+
if (RB_EMPTY_ROOT(&bfqq->sort_list)) {
if (bfqq->dispatched == 0)
/*
@@ -4211,8 +4762,13 @@ static void __bfq_bfqq_expire(struct bfq_data *bfqd, struct bfq_queue *bfqq)
bfqq->budget_timeout = jiffies;
bfq_del_bfqq_busy(bfqd, bfqq, 1);
- } else
+ } else {
bfq_activate_bfqq(bfqd, bfqq);
+ /*
+ * Resort priority tree of potential close cooperators.
+ */
+ bfq_pos_tree_add_move(bfqd, bfqq);
+ }
}
/**
@@ -5082,8 +5638,7 @@ static void bfq_update_wr_data(struct bfq_data *bfqd, struct bfq_queue *bfqq)
/*
* If too much time has elapsed from the beginning of
- * this weight-raising period, then end weight
- * raising.
+ * this weight-raising period, then end weight raising.
*/
if (time_is_before_jiffies(bfqq->last_wr_start_finish +
bfqq->wr_cur_max_time)) {
@@ -5282,6 +5837,25 @@ static void bfq_put_queue(struct bfq_queue *bfqq)
#endif
}
+static void bfq_put_cooperator(struct bfq_queue *bfqq)
+{
+ struct bfq_queue *__bfqq, *next;
+
+ /*
+ * If this queue was scheduled to merge with another queue, be
+ * sure to drop the reference taken on that queue (and others in
+ * the merge chain). See bfq_setup_merge and bfq_merge_bfqqs.
+ */
+ __bfqq = bfqq->new_bfqq;
+ while (__bfqq) {
+ if (__bfqq == bfqq)
+ break;
+ next = __bfqq->new_bfqq;
+ bfq_put_queue(__bfqq);
+ __bfqq = next;
+ }
+}
+
static void bfq_exit_bfqq(struct bfq_data *bfqd, struct bfq_queue *bfqq)
{
if (bfqq == bfqd->in_service_queue) {
@@ -5291,12 +5865,16 @@ static void bfq_exit_bfqq(struct bfq_data *bfqd, struct bfq_queue *bfqq)
bfq_log_bfqq(bfqd, bfqq, "exit_bfqq: %p, %d", bfqq, bfqq->ref);
+ bfq_put_cooperator(bfqq);
+
bfq_put_queue(bfqq);
}
static void bfq_init_icq(struct io_cq *icq)
{
- icq_to_bic(icq)->ttime.last_end_request = bfq_smallest_from_now();
+ struct bfq_io_cq *bic = icq_to_bic(icq);
+
+ bic->ttime.last_end_request = bfq_smallest_from_now();
}
static void bfq_exit_icq(struct io_cq *icq)
@@ -5310,8 +5888,15 @@ static void bfq_exit_icq(struct io_cq *icq)
}
if (bic_to_bfqq(bic, true)) {
- bfq_exit_bfqq(bfqd, bic->bfqq[BLK_RW_SYNC]);
- bic->bfqq[BLK_RW_SYNC] = NULL;
+ /*
+ * If the bic is using a shared queue, put the reference
+ * taken on the io_context when the bic started using a
+ * shared bfq_queue.
+ */
+ if (bfq_bfqq_coop(bic_to_bfqq(bic, true)))
+ put_io_context(icq->ioc);
+ bfq_exit_bfqq(bfqd, bic_to_bfqq(bic, true));
+ bic_set_bfqq(bic, NULL, true);
}
}
@@ -5417,6 +6002,7 @@ 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->split_time = bfq_smallest_from_now();
/*
* Set to the value for which bfqq will not be deemed as
@@ -5545,6 +6131,11 @@ static void bfq_update_idle_window(struct bfq_data *bfqd,
if (!bfq_bfqq_sync(bfqq) || bfq_class_idle(bfqq))
return;
+ /* Idle window just restored, statistics are meaningless. */
+ if (time_is_after_eq_jiffies(bfqq->split_time +
+ bfqd->bfq_wr_min_idle_time))
+ return;
+
enable_idle = bfq_bfqq_idle_window(bfqq);
if (atomic_read(&bic->icq.ioc->active_ref) == 0 ||
@@ -5647,10 +6238,36 @@ static void bfq_rq_enqueued(struct bfq_data *bfqd, struct bfq_queue *bfqq,
static void bfq_insert_request(struct request_queue *q, struct request *rq)
{
struct bfq_data *bfqd = q->elevator->elevator_data;
- struct bfq_queue *bfqq = RQ_BFQQ(rq);
+ struct bfq_queue *bfqq = RQ_BFQQ(rq), *new_bfqq;
assert_spin_locked(bfqd->queue->queue_lock);
+ /*
+ * An unplug may trigger a requeue of a request from the device
+ * driver: make sure we are in process context while trying to
+ * merge two bfq_queues.
+ */
+ if (!in_interrupt()) {
+ new_bfqq = bfq_setup_cooperator(bfqd, bfqq, rq, true);
+ if (new_bfqq) {
+ if (bic_to_bfqq(RQ_BIC(rq), 1) != bfqq)
+ new_bfqq = bic_to_bfqq(RQ_BIC(rq), 1);
+ /*
+ * Release the request's reference to the old bfqq
+ * and make sure one is taken to the shared queue.
+ */
+ new_bfqq->allocated[rq_data_dir(rq)]++;
+ bfqq->allocated[rq_data_dir(rq)]--;
+ new_bfqq->ref++;
+ bfq_put_queue(bfqq);
+ if (bic_to_bfqq(RQ_BIC(rq), 1) == bfqq)
+ bfq_merge_bfqqs(bfqd, RQ_BIC(rq),
+ bfqq, new_bfqq);
+ rq->elv.priv[1] = new_bfqq;
+ bfqq = new_bfqq;
+ }
+ }
+
bfq_add_request(rq);
rq->fifo_time = jiffies + bfqd->bfq_fifo_expire[rq_is_sync(rq)];
@@ -5808,6 +6425,32 @@ static void bfq_put_request(struct request *rq)
}
/*
+ * Returns NULL if a new bfqq should be allocated, or the old bfqq if this
+ * was the last process referring to that bfqq.
+ */
+static struct bfq_queue *
+bfq_split_bfqq(struct bfq_io_cq *bic, struct bfq_queue *bfqq)
+{
+ bfq_log_bfqq(bfqq->bfqd, bfqq, "splitting queue");
+
+ put_io_context(bic->icq.ioc);
+
+ if (bfqq_process_refs(bfqq) == 1) {
+ bfqq->pid = current->pid;
+ bfq_clear_bfqq_coop(bfqq);
+ bfq_clear_bfqq_split_coop(bfqq);
+ return bfqq;
+ }
+
+ bic_set_bfqq(bic, NULL, 1);
+
+ bfq_put_cooperator(bfqq);
+
+ bfq_put_queue(bfqq);
+ return NULL;
+}
+
+/*
* Allocate bfq data structures associated with this request.
*/
static int bfq_set_request(struct request_queue *q, struct request *rq,
@@ -5819,6 +6462,7 @@ static int bfq_set_request(struct request_queue *q, struct request *rq,
const int is_sync = rq_is_sync(rq);
struct bfq_queue *bfqq;
unsigned long flags;
+ bool split = false;
spin_lock_irqsave(q->queue_lock, flags);
@@ -5829,12 +6473,24 @@ static int bfq_set_request(struct request_queue *q, struct request *rq,
bfq_bic_update_cgroup(bic, bio);
+new_queue:
bfqq = bic_to_bfqq(bic, is_sync);
if (!bfqq || bfqq == &bfqd->oom_bfqq) {
if (bfqq)
bfq_put_queue(bfqq);
bfqq = bfq_get_queue(bfqd, bio, is_sync, bic);
bic_set_bfqq(bic, bfqq, is_sync);
+ if (split && is_sync)
+ bfqq->split_time = jiffies;
+ } else {
+ /* If the queue was seeky for too long, break it apart. */
+ if (bfq_bfqq_coop(bfqq) && bfq_bfqq_split_coop(bfqq)) {
+ bfq_log_bfqq(bfqd, bfqq, "breaking apart bfqq");
+ bfqq = bfq_split_bfqq(bic, bfqq);
+ split = true;
+ if (!bfqq)
+ goto new_queue;
+ }
}
bfqq->allocated[rw]++;
@@ -5844,6 +6500,25 @@ static int bfq_set_request(struct request_queue *q, struct request *rq,
rq->elv.priv[0] = bic;
rq->elv.priv[1] = bfqq;
+ /*
+ * If a bfq_queue has only one process reference, it is owned
+ * by only one bfq_io_cq: we can set the bic field of the
+ * bfq_queue to the address of that structure. Also, if the
+ * queue has just been split, mark a flag so that the
+ * information is available to the other scheduler hooks.
+ */
+ if (likely(bfqq != &bfqd->oom_bfqq) && bfqq_process_refs(bfqq) == 1) {
+ bfqq->bic = bic;
+ if (split) {
+ /*
+ * If the queue has just been split from a shared
+ * queue, restore the idle window and the possible
+ * weight raising period.
+ */
+ bfq_bfqq_resume_state(bfqq, bic);
+ }
+ }
+
spin_unlock_irqrestore(q->queue_lock, flags);
return 0;
@@ -5996,6 +6671,7 @@ static void bfq_init_root_group(struct bfq_group *root_group,
root_group->my_entity = NULL;
root_group->bfqd = bfqd;
#endif
+ root_group->rq_pos_tree = RB_ROOT;
for (i = 0; i < BFQ_IOPRIO_CLASSES; i++)
root_group->sched_data.service_tree[i] = BFQ_SERVICE_TREE_INIT;
}
@@ -6481,7 +7157,7 @@ static int __init bfq_init(void)
if (ret)
goto err_pol_unreg;
- pr_info("BFQ I/O-scheduler: v2");
+ pr_info("BFQ I/O-scheduler: v6");
return 0;
--
1.9.1
[toc] | [prev] | [next] | [standalone]
| From | Paolo Valente <paolo.valente@linaro.org> |
|---|---|
| Date | 2016-07-27 18:20 +0200 |
| Subject | [PATCH RFC V8 07/22] block, cfq: get rid of workload type |
| Message-ID | <rZzIS-1FV-49@gated-at.bofh.it> |
| In reply to | #1451384 |
From: Arianna Avanzini <avanzini.arianna@gmail.com>
CFQ selects the queue to serve also according to the type of workload
it is part of. This kind of heuristic has no match in BFQ, where a
high throughput, and, at the same time, provable service guarantees
are provided through a unified overall scheduling policy.
Signed-off-by: Arianna Avanzini <avanzini.arianna@gmail.com>
Signed-off-by: Paolo Valente <paolo.valente@linaro.org>
---
block/cfq-iosched.c | 131 +++++++++++-----------------------------------------
1 file changed, 26 insertions(+), 105 deletions(-)
diff --git a/block/cfq-iosched.c b/block/cfq-iosched.c
index 174dc94..df8fb826 100644
--- a/block/cfq-iosched.c
+++ b/block/cfq-iosched.c
@@ -155,15 +155,6 @@ enum wl_class_t {
CFQ_PRIO_NR,
};
-/*
- * Second index in the service_trees.
- */
-enum wl_type_t {
- ASYNC_WORKLOAD = 0,
- SYNC_NOIDLE_WORKLOAD = 1,
- SYNC_WORKLOAD = 2
-};
-
struct cfq_io_cq {
struct io_cq icq; /* must be the first member */
struct cfq_queue *cfqq[2];
@@ -179,20 +170,16 @@ struct cfq_data {
/*
* rr lists of queues with requests. We maintain service trees for
- * RT and BE classes. These trees are subdivided in subclasses
- * of SYNC, SYNC_NOIDLE and ASYNC based on workload type. For IDLE
- * class there is no subclassification and all the cfq queues go on
- * a single tree service_tree_idle.
+ * RT and BE classes.
* Counts are embedded in the cfq_rb_root
*/
- struct cfq_rb_root service_trees[2][3];
+ struct cfq_rb_root service_trees[2];
struct cfq_rb_root service_tree_idle;
/*
* The priority currently being served
*/
enum wl_class_t serving_wl_class;
- enum wl_type_t serving_wl_type;
unsigned long workload_expires;
unsigned int busy_queues;
@@ -291,9 +278,8 @@ CFQ_CFQQ_FNS(wait_busy);
#undef CFQ_CFQQ_FNS
#define cfq_log_cfqq(cfqd, cfqq, fmt, args...) \
- blk_add_trace_msg((cfqd)->queue, "cfq%d%c%c " fmt, (cfqq)->pid, \
+ blk_add_trace_msg((cfqd)->queue, "cfq%d%c " fmt, (cfqq)->pid, \
cfq_cfqq_sync((cfqq)) ? 'S' : 'A', \
- cfqq_type((cfqq)) == SYNC_NOIDLE_WORKLOAD ? 'N' : ' ',\
##args)
#define cfq_log(cfqd, fmt, args...) \
blk_add_trace_msg((cfqd)->queue, "cfq " fmt, ##args)
@@ -301,12 +287,12 @@ CFQ_CFQQ_FNS(wait_busy);
/* Traverses through cfq service trees */
#define for_each_st(cfqd, i, j, st) \
for (i = 0; i <= IDLE_WORKLOAD; i++) \
- for (j = 0, st = i < IDLE_WORKLOAD ? &cfqd->service_trees[i][j]\
+ for (j = 0, st = i < IDLE_WORKLOAD ? &cfqd->service_trees[i]\
: &cfqd->service_tree_idle; \
- (i < IDLE_WORKLOAD && j <= SYNC_WORKLOAD) || \
- (i == IDLE_WORKLOAD && j == 0); \
- j++, st = i < IDLE_WORKLOAD ? \
- &cfqd->service_trees[i][j] : NULL) \
+ (i < IDLE_WORKLOAD) || \
+ (i == IDLE_WORKLOAD); \
+ st = i < IDLE_WORKLOAD ? \
+ &cfqd->service_trees[i] : NULL) \
static inline bool cfq_io_thinktime_big(struct cfq_data *cfqd,
struct cfq_ttime *ttime)
@@ -327,33 +313,6 @@ static inline enum wl_class_t cfqq_class(struct cfq_queue *cfqq)
return BE_WORKLOAD;
}
-
-static enum wl_type_t cfqq_type(struct cfq_queue *cfqq)
-{
- if (!cfq_cfqq_sync(cfqq))
- return ASYNC_WORKLOAD;
- if (!cfq_cfqq_idle_window(cfqq))
- return SYNC_NOIDLE_WORKLOAD;
- return SYNC_WORKLOAD;
-}
-
-static inline int cfq_busy_queues_wl(enum wl_class_t wl_class,
- struct cfq_data *cfqd)
-{
- if (wl_class == IDLE_WORKLOAD)
- return cfqd->service_tree_idle.count;
-
- return cfqd->service_trees[wl_class][ASYNC_WORKLOAD].count +
- cfqd->service_trees[wl_class][SYNC_NOIDLE_WORKLOAD].count +
- cfqd->service_trees[wl_class][SYNC_WORKLOAD].count;
-}
-
-static inline int cfq_busy_async_queues(struct cfq_data *cfqd)
-{
- return cfqd->service_trees[RT_WORKLOAD][ASYNC_WORKLOAD].count +
- cfqd->service_trees[BE_WORKLOAD][ASYNC_WORKLOAD].count;
-}
-
static void cfq_dispatch_insert(struct request_queue *, struct request *);
static struct cfq_queue *cfq_get_queue(struct cfq_data *cfqd, bool is_sync,
struct cfq_io_cq *cic, struct bio *bio);
@@ -677,7 +636,7 @@ static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
int left;
int new_cfqq = 1;
- st = &cfqd->service_trees[cfqq_class(cfqq)][cfqq_type(cfqq)];
+ st = &cfqd->service_trees[cfqq_class(cfqq)];
if (cfq_class_idle(cfqq)) {
rb_key = CFQ_IDLE_DELAY;
parent = rb_last(&st->rb);
@@ -999,8 +958,8 @@ static void __cfq_set_active_queue(struct cfq_data *cfqd,
struct cfq_queue *cfqq)
{
if (cfqq) {
- cfq_log_cfqq(cfqd, cfqq, "set_active wl_class:%d wl_type:%d",
- cfqd->serving_wl_class, cfqd->serving_wl_type);
+ cfq_log_cfqq(cfqd, cfqq, "set_active wl_class:%d",
+ cfqd->serving_wl_class);
cfqq->slice_start = 0;
cfqq->dispatch_start = jiffies;
cfqq->allocated_slice = 0;
@@ -1073,9 +1032,7 @@ static inline void cfq_slice_expired(struct cfq_data *cfqd, bool timed_out)
*/
static struct cfq_queue *cfq_get_next_queue(struct cfq_data *cfqd)
{
- struct cfq_rb_root *st =
- &cfqd->service_trees[cfqd->serving_wl_class]
- [cfqd->serving_wl_type];
+ struct cfq_rb_root *st = &cfqd->service_trees[cfqd->serving_wl_class];
if (!cfqd->rq_queued)
return NULL;
@@ -1201,6 +1158,15 @@ static void cfq_arm_slice_timer(struct cfq_data *cfqd)
cfq_log_cfqq(cfqd, cfqq, "arm_idle: %lu", sl);
}
+static inline int cfq_busy_queues_wl(enum wl_class_t wl_class,
+ struct cfq_data *cfqd)
+{
+ if (wl_class == IDLE_WORKLOAD)
+ return cfqd->service_tree_idle.count;
+
+ return cfqd->service_trees[wl_class].count;
+}
+
/*
* Move request from internal lists to the request queue dispatch list.
*/
@@ -1253,29 +1219,6 @@ cfq_prio_to_maxrq(struct cfq_data *cfqd, struct cfq_queue *cfqq)
return 2 * base_rq * (IOPRIO_BE_NR - cfqq->ioprio);
}
-static enum wl_type_t cfq_choose_wl_type(struct cfq_data *cfqd,
- enum wl_class_t wl_class)
-{
- struct cfq_queue *queue;
- int i;
- bool key_valid = false;
- unsigned long lowest_key = 0;
- enum wl_type_t cur_best = SYNC_NOIDLE_WORKLOAD;
-
- for (i = 0; i <= SYNC_WORKLOAD; ++i) {
- /* select the one with lowest rb_key */
- queue = cfq_rb_first(&cfqd->service_trees[wl_class][i]);
- if (queue &&
- (!key_valid || time_before(queue->rb_key, lowest_key))) {
- lowest_key = queue->rb_key;
- cur_best = i;
- key_valid = true;
- }
- }
-
- return cur_best;
-}
-
static void
choose_wl_class_and_type(struct cfq_data *cfqd)
{
@@ -1298,13 +1241,7 @@ choose_wl_class_and_type(struct cfq_data *cfqd)
if (original_class != cfqd->serving_wl_class)
goto new_workload;
- /*
- * For RT and BE, we have to choose also the type
- * (SYNC, SYNC_NOIDLE, ASYNC), and to compute a workload
- * expiration time
- */
- st = &cfqd->service_trees[cfqd->serving_wl_class]
- [cfqd->serving_wl_type];
+ st = &cfqd->service_trees[cfqd->serving_wl_class];
count = st->count;
/*
@@ -1314,26 +1251,11 @@ choose_wl_class_and_type(struct cfq_data *cfqd)
return;
new_workload:
- /* otherwise select new workload type */
- cfqd->serving_wl_type = cfq_choose_wl_type(cfqd,
- cfqd->serving_wl_class);
- st = &cfqd->service_trees[cfqd->serving_wl_class]
- [cfqd->serving_wl_type];
+ st = &cfqd->service_trees[cfqd->serving_wl_class];
count = st->count;
- if (cfqd->serving_wl_type == ASYNC_WORKLOAD) {
- slice = cfqd->cfq_target_latency *
- cfq_busy_async_queues(cfqd);
- slice = slice/cfqd->busy_queues;
-
- /* async workload slice is scaled down according to
- * the sync/async slice ratio. */
- slice = slice * cfqd->cfq_slice[0] / cfqd->cfq_slice[1];
- } else
- /* sync workload slice is 2 * cfq_slice_idle */
- slice = 2 * cfqd->cfq_slice_idle;
-
- slice = max_t(unsigned, slice, CFQ_MIN_TT);
+ /* sync workload slice is 2 * cfq_slice_idle */
+ slice = max_t(unsigned int, 2 * cfqd->cfq_slice_idle, CFQ_MIN_TT);
cfq_log(cfqd, "workload slice:%d", slice);
cfqd->workload_expires = jiffies + slice;
}
@@ -2078,8 +2000,7 @@ static void cfq_completed_request(struct request_queue *q, struct request *rq)
if (cfq_cfqq_on_rr(cfqq))
st = cfqq->service_tree;
else
- st = &cfqd->service_trees[cfqq_class(cfqq)]
- [cfqq_type(cfqq)];
+ st = &cfqd->service_trees[cfqq_class(cfqq)];
st->ttime.last_end_request = now;
if (!time_after(rq->start_time + cfqd->cfq_fifo_expire[1], now))
--
1.9.1
[toc] | [prev] | [next] | [standalone]
| From | Paolo <paolo.valente@linaro.org> |
|---|---|
| Date | 2016-07-28 19:00 +0200 |
| Message-ID | <rZWP7-s6-7@gated-at.bofh.it> |
| In reply to | #1451384 |
Out of sync with HEAD (at the date of posting), sorry. Rebasing. Thanks, Paolo Il 27/07/2016 18:13, Paolo Valente ha scritto: > Hi, > this new version of the patchset contains all the improvements and bug > fixes recommended by Tejun [7], plus new features of BFQ-v8. Details > about old and new features in patch descriptions. For your > convenience, here is the usual description of the overall patchset. > > This patchset replaces CFQ with the last version of BFQ (which is a > proportional-share I/O scheduler). To make a smooth transition, this > patchset first brings CFQ back to its state at the time when BFQ was > forked from CFQ. Basically, this reduces CFQ to its engine, by > removing every heuristic and improvement that has nothing to do with > any heuristic or improvement in BFQ, and every heuristic and > improvement whose goal is achieved in a different way in BFQ. Then, > the second part of the patchset starts by replacing CFQ's engine with > BFQ's engine, and goes on by adding current BFQ improvements and extra > heuristics. Here is the thread in which we agreed on both this first > step, and the second and last step: [1]. Moreover, here is a direct > link to the email describing both steps: [2]. > > 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. > > Turning back to BFQ, its first version was submitted a few years ago > [3]. It is denoted as v0 in this patchset, to distinguish it from the > version I am submitting now, v8. In particular, the first two > patches concerned with BFQ introduce BFQ-v0, whereas the remaining > patches turn progressively BFQ-v0 into BFQ-v8. Here are some nice > features of BFQ-v8. > > Low latency for interactive applications > > According to our results, and regardless of the actual background > workload, 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 or written, > - 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. > > 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 half of the > parallel workloads considered in our tests. With the rest of the > workloads, and with all the workloads on flash-based devices, BFQ > achieves instead about the same throughput as the other schedulers. > > Strong fairness guarantees (already provided by BFQ-v0) > > As for long-term guarantees, BFQ distributes the device throughput > (and not just the device time) as desired among I/O-bound > applications, with any workload and regardless of the device > parameters. > > > BFQ achieves the above service properties thanks to the combination of > its accurate scheduling engine (patches 9-10), and a set of simple > heuristics and improvements (patches 11-22). 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 [4]. > > What BFQ can do in practice is shown, e.g., in this 8-minute demo with > an SSD: [5]. 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 [6], > 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., 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. > > 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 [6] 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/2014/5/27/314 > > [2] https://lists.linux-foundation.org/pipermail/containers/2014-June/034704.html > > [3] https://lkml.org/lkml/2008/4/1/234 > > [4] 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 > > [5] https://youtu.be/1cjZeaCXIyM > > [6] http://algogroup.unimore.it/people/paolo/disk_sched/results.php > > [7] https://lkml.org/lkml/2016/2/1/818 > > Arianna Avanzini (11): > block, cfq: remove queue merging for close cooperators > block, cfq: remove close-based preemption > block, cfq: remove deep seek queues logic > block, cfq: remove SSD-related logic > block, cfq: get rid of hierarchical support > block, cfq: get rid of queue preemption > block, cfq: get rid of workload type > 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 > > Fabio Checconi (1): > block, cfq: replace CFQ with the BFQ-v0 I/O scheduler > > Paolo Valente (10): > block, cfq: get rid of latency tunables > block, bfq: improve throughput boosting > block, bfq: modify the peak-rate estimator > block, bfq: add more fairness with writes and slow processes > block, bfq: improve responsiveness > block, bfq: reduce I/O latency for soft real-time applications > block, bfq: preserve a low latency also with NCQ-capable drives > block, bfq: reduce latency during request-pool saturation > block, bfq: boost the throughput on NCQ-capable flash-based devices > block, bfq: boost the throughput with random I/O on NCQ-capable HDDs > > block/Kconfig.iosched | 19 +- > block/cfq-iosched.c | 10173 +++++++++++++++++++++++++++++++----------------- > 2 files changed, 6610 insertions(+), 3582 deletions(-) >
[toc] | [prev] | [standalone]
Back to top | Article view | linux.kernel
csiph-web