linux/block/bfq-iosched.c
<<
>>
Prefs
   1// SPDX-License-Identifier: GPL-2.0-or-later
   2/*
   3 * Budget Fair Queueing (BFQ) I/O scheduler.
   4 *
   5 * Based on ideas and code from CFQ:
   6 * Copyright (C) 2003 Jens Axboe <axboe@kernel.dk>
   7 *
   8 * Copyright (C) 2008 Fabio Checconi <fabio@gandalf.sssup.it>
   9 *                    Paolo Valente <paolo.valente@unimore.it>
  10 *
  11 * Copyright (C) 2010 Paolo Valente <paolo.valente@unimore.it>
  12 *                    Arianna Avanzini <avanzini@google.com>
  13 *
  14 * Copyright (C) 2017 Paolo Valente <paolo.valente@linaro.org>
  15 *
  16 * BFQ is a proportional-share I/O scheduler, with some extra
  17 * low-latency capabilities. BFQ also supports full hierarchical
  18 * scheduling through cgroups. Next paragraphs provide an introduction
  19 * on BFQ inner workings. Details on BFQ benefits, usage and
  20 * limitations can be found in Documentation/block/bfq-iosched.rst.
  21 *
  22 * BFQ is a proportional-share storage-I/O scheduling algorithm based
  23 * on the slice-by-slice service scheme of CFQ. But BFQ assigns
  24 * budgets, measured in number of sectors, to processes instead of
  25 * time slices. The device is not granted to the in-service process
  26 * for a given time slice, but until it has exhausted its assigned
  27 * budget. This change from the time to the service domain enables BFQ
  28 * to distribute the device throughput among processes as desired,
  29 * without any distortion due to throughput fluctuations, or to device
  30 * internal queueing. BFQ uses an ad hoc internal scheduler, called
  31 * B-WF2Q+, to schedule processes according to their budgets. More
  32 * precisely, BFQ schedules queues associated with processes. Each
  33 * process/queue is assigned a user-configurable weight, and B-WF2Q+
  34 * guarantees that each queue receives a fraction of the throughput
  35 * proportional to its weight. Thanks to the accurate policy of
  36 * B-WF2Q+, BFQ can afford to assign high budgets to I/O-bound
  37 * processes issuing sequential requests (to boost the throughput),
  38 * and yet guarantee a low latency to interactive and soft real-time
  39 * applications.
  40 *
  41 * In particular, to provide these low-latency guarantees, BFQ
  42 * explicitly privileges the I/O of two classes of time-sensitive
  43 * applications: interactive and soft real-time. In more detail, BFQ
  44 * behaves this way if the low_latency parameter is set (default
  45 * configuration). This feature enables BFQ to provide applications in
  46 * these classes with a very low latency.
  47 *
  48 * To implement this feature, BFQ constantly tries to detect whether
  49 * the I/O requests in a bfq_queue come from an interactive or a soft
  50 * real-time application. For brevity, in these cases, the queue is
  51 * said to be interactive or soft real-time. In both cases, BFQ
  52 * privileges the service of the queue, over that of non-interactive
  53 * and non-soft-real-time queues. This privileging is performed,
  54 * mainly, by raising the weight of the queue. So, for brevity, we
  55 * call just weight-raising periods the time periods during which a
  56 * queue is privileged, because deemed interactive or soft real-time.
  57 *
  58 * The detection of soft real-time queues/applications is described in
  59 * detail in the comments on the function
  60 * bfq_bfqq_softrt_next_start. On the other hand, the detection of an
  61 * interactive queue works as follows: a queue is deemed interactive
  62 * if it is constantly non empty only for a limited time interval,
  63 * after which it does become empty. The queue may be deemed
  64 * interactive again (for a limited time), if it restarts being
  65 * constantly non empty, provided that this happens only after the
  66 * queue has remained empty for a given minimum idle time.
  67 *
  68 * By default, BFQ computes automatically the above maximum time
  69 * interval, i.e., the time interval after which a constantly
  70 * non-empty queue stops being deemed interactive. Since a queue is
  71 * weight-raised while it is deemed interactive, this maximum time
  72 * interval happens to coincide with the (maximum) duration of the
  73 * weight-raising for interactive queues.
  74 *
  75 * Finally, BFQ also features additional heuristics for
  76 * preserving both a low latency and a high throughput on NCQ-capable,
  77 * rotational or flash-based devices, and to get the job done quickly
  78 * for applications consisting in many I/O-bound processes.
  79 *
  80 * NOTE: if the main or only goal, with a given device, is to achieve
  81 * the maximum-possible throughput at all times, then do switch off
  82 * all low-latency heuristics for that device, by setting low_latency
  83 * to 0.
  84 *
  85 * BFQ is described in [1], where also a reference to the initial,
  86 * more theoretical paper on BFQ can be found. The interested reader
  87 * can find in the latter paper full details on the main algorithm, as
  88 * well as formulas of the guarantees and formal proofs of all the
  89 * properties.  With respect to the version of BFQ presented in these
  90 * papers, this implementation adds a few more heuristics, such as the
  91 * ones that guarantee a low latency to interactive and soft real-time
  92 * applications, and a hierarchical extension based on H-WF2Q+.
  93 *
  94 * B-WF2Q+ is based on WF2Q+, which is described in [2], together with
  95 * H-WF2Q+, while the augmented tree used here to implement B-WF2Q+
  96 * with O(log N) complexity derives from the one introduced with EEVDF
  97 * in [3].
  98 *
  99 * [1] P. Valente, A. Avanzini, "Evolution of the BFQ Storage I/O
 100 *     Scheduler", Proceedings of the First Workshop on Mobile System
 101 *     Technologies (MST-2015), May 2015.
 102 *     http://algogroup.unimore.it/people/paolo/disk_sched/mst-2015.pdf
 103 *
 104 * [2] Jon C.R. Bennett and H. Zhang, "Hierarchical Packet Fair Queueing
 105 *     Algorithms", IEEE/ACM Transactions on Networking, 5(5):675-689,
 106 *     Oct 1997.
 107 *
 108 * http://www.cs.cmu.edu/~hzhang/papers/TON-97-Oct.ps.gz
 109 *
 110 * [3] I. Stoica and H. Abdel-Wahab, "Earliest Eligible Virtual Deadline
 111 *     First: A Flexible and Accurate Mechanism for Proportional Share
 112 *     Resource Allocation", technical report.
 113 *
 114 * http://www.cs.berkeley.edu/~istoica/papers/eevdf-tr-95.pdf
 115 */
 116#include <linux/module.h>
 117#include <linux/slab.h>
 118#include <linux/blkdev.h>
 119#include <linux/cgroup.h>
 120#include <linux/elevator.h>
 121#include <linux/ktime.h>
 122#include <linux/rbtree.h>
 123#include <linux/ioprio.h>
 124#include <linux/sbitmap.h>
 125#include <linux/delay.h>
 126#include <linux/backing-dev.h>
 127
 128#include <trace/events/block.h>
 129
 130#include "blk.h"
 131#include "blk-mq.h"
 132#include "blk-mq-tag.h"
 133#include "blk-mq-sched.h"
 134#include "bfq-iosched.h"
 135#include "blk-wbt.h"
 136
 137#define BFQ_BFQQ_FNS(name)                                              \
 138void bfq_mark_bfqq_##name(struct bfq_queue *bfqq)                       \
 139{                                                                       \
 140        __set_bit(BFQQF_##name, &(bfqq)->flags);                        \
 141}                                                                       \
 142void bfq_clear_bfqq_##name(struct bfq_queue *bfqq)                      \
 143{                                                                       \
 144        __clear_bit(BFQQF_##name, &(bfqq)->flags);              \
 145}                                                                       \
 146int bfq_bfqq_##name(const struct bfq_queue *bfqq)                       \
 147{                                                                       \
 148        return test_bit(BFQQF_##name, &(bfqq)->flags);          \
 149}
 150
 151BFQ_BFQQ_FNS(just_created);
 152BFQ_BFQQ_FNS(busy);
 153BFQ_BFQQ_FNS(wait_request);
 154BFQ_BFQQ_FNS(non_blocking_wait_rq);
 155BFQ_BFQQ_FNS(fifo_expire);
 156BFQ_BFQQ_FNS(has_short_ttime);
 157BFQ_BFQQ_FNS(sync);
 158BFQ_BFQQ_FNS(IO_bound);
 159BFQ_BFQQ_FNS(in_large_burst);
 160BFQ_BFQQ_FNS(coop);
 161BFQ_BFQQ_FNS(split_coop);
 162BFQ_BFQQ_FNS(softrt_update);
 163#undef BFQ_BFQQ_FNS                                             \
 164
 165/* Expiration time of async (0) and sync (1) requests, in ns. */
 166static const u64 bfq_fifo_expire[2] = { NSEC_PER_SEC / 4, NSEC_PER_SEC / 8 };
 167
 168/* Maximum backwards seek (magic number lifted from CFQ), in KiB. */
 169static const int bfq_back_max = 16 * 1024;
 170
 171/* Penalty of a backwards seek, in number of sectors. */
 172static const int bfq_back_penalty = 2;
 173
 174/* Idling period duration, in ns. */
 175static u64 bfq_slice_idle = NSEC_PER_SEC / 125;
 176
 177/* Minimum number of assigned budgets for which stats are safe to compute. */
 178static const int bfq_stats_min_budgets = 194;
 179
 180/* Default maximum budget values, in sectors and number of requests. */
 181static const int bfq_default_max_budget = 16 * 1024;
 182
 183/*
 184 * When a sync request is dispatched, the queue that contains that
 185 * request, and all the ancestor entities of that queue, are charged
 186 * with the number of sectors of the request. In contrast, if the
 187 * request is async, then the queue and its ancestor entities are
 188 * charged with the number of sectors of the request, multiplied by
 189 * the factor below. This throttles the bandwidth for async I/O,
 190 * w.r.t. to sync I/O, and it is done to counter the tendency of async
 191 * writes to steal I/O throughput to reads.
 192 *
 193 * The current value of this parameter is the result of a tuning with
 194 * several hardware and software configurations. We tried to find the
 195 * lowest value for which writes do not cause noticeable problems to
 196 * reads. In fact, the lower this parameter, the stabler I/O control,
 197 * in the following respect.  The lower this parameter is, the less
 198 * the bandwidth enjoyed by a group decreases
 199 * - when the group does writes, w.r.t. to when it does reads;
 200 * - when other groups do reads, w.r.t. to when they do writes.
 201 */
 202static const int bfq_async_charge_factor = 3;
 203
 204/* Default timeout values, in jiffies, approximating CFQ defaults. */
 205const int bfq_timeout = HZ / 8;
 206
 207/*
 208 * Time limit for merging (see comments in bfq_setup_cooperator). Set
 209 * to the slowest value that, in our tests, proved to be effective in
 210 * removing false positives, while not causing true positives to miss
 211 * queue merging.
 212 *
 213 * As can be deduced from the low time limit below, queue merging, if
 214 * successful, happens at the very beginning of the I/O of the involved
 215 * cooperating processes, as a consequence of the arrival of the very
 216 * first requests from each cooperator.  After that, there is very
 217 * little chance to find cooperators.
 218 */
 219static const unsigned long bfq_merge_time_limit = HZ/10;
 220
 221static struct kmem_cache *bfq_pool;
 222
 223/* Below this threshold (in ns), we consider thinktime immediate. */
 224#define BFQ_MIN_TT              (2 * NSEC_PER_MSEC)
 225
 226/* hw_tag detection: parallel requests threshold and min samples needed. */
 227#define BFQ_HW_QUEUE_THRESHOLD  3
 228#define BFQ_HW_QUEUE_SAMPLES    32
 229
 230#define BFQQ_SEEK_THR           (sector_t)(8 * 100)
 231#define BFQQ_SECT_THR_NONROT    (sector_t)(2 * 32)
 232#define BFQ_RQ_SEEKY(bfqd, last_pos, rq) \
 233        (get_sdist(last_pos, rq) >                      \
 234         BFQQ_SEEK_THR &&                               \
 235         (!blk_queue_nonrot(bfqd->queue) ||             \
 236          blk_rq_sectors(rq) < BFQQ_SECT_THR_NONROT))
 237#define BFQQ_CLOSE_THR          (sector_t)(8 * 1024)
 238#define BFQQ_SEEKY(bfqq)        (hweight32(bfqq->seek_history) > 19)
 239/*
 240 * Sync random I/O is likely to be confused with soft real-time I/O,
 241 * because it is characterized by limited throughput and apparently
 242 * isochronous arrival pattern. To avoid false positives, queues
 243 * containing only random (seeky) I/O are prevented from being tagged
 244 * as soft real-time.
 245 */
 246#define BFQQ_TOTALLY_SEEKY(bfqq)        (bfqq->seek_history == -1)
 247
 248/* Min number of samples required to perform peak-rate update */
 249#define BFQ_RATE_MIN_SAMPLES    32
 250/* Min observation time interval required to perform a peak-rate update (ns) */
 251#define BFQ_RATE_MIN_INTERVAL   (300*NSEC_PER_MSEC)
 252/* Target observation time interval for a peak-rate update (ns) */
 253#define BFQ_RATE_REF_INTERVAL   NSEC_PER_SEC
 254
 255/*
 256 * Shift used for peak-rate fixed precision calculations.
 257 * With
 258 * - the current shift: 16 positions
 259 * - the current type used to store rate: u32
 260 * - the current unit of measure for rate: [sectors/usec], or, more precisely,
 261 *   [(sectors/usec) / 2^BFQ_RATE_SHIFT] to take into account the shift,
 262 * the range of rates that can be stored is
 263 * [1 / 2^BFQ_RATE_SHIFT, 2^(32 - BFQ_RATE_SHIFT)] sectors/usec =
 264 * [1 / 2^16, 2^16] sectors/usec = [15e-6, 65536] sectors/usec =
 265 * [15, 65G] sectors/sec
 266 * Which, assuming a sector size of 512B, corresponds to a range of
 267 * [7.5K, 33T] B/sec
 268 */
 269#define BFQ_RATE_SHIFT          16
 270
 271/*
 272 * When configured for computing the duration of the weight-raising
 273 * for interactive queues automatically (see the comments at the
 274 * beginning of this file), BFQ does it using the following formula:
 275 * duration = (ref_rate / r) * ref_wr_duration,
 276 * where r is the peak rate of the device, and ref_rate and
 277 * ref_wr_duration are two reference parameters.  In particular,
 278 * ref_rate is the peak rate of the reference storage device (see
 279 * below), and ref_wr_duration is about the maximum time needed, with
 280 * BFQ and while reading two files in parallel, to load typical large
 281 * applications on the reference device (see the comments on
 282 * max_service_from_wr below, for more details on how ref_wr_duration
 283 * is obtained).  In practice, the slower/faster the device at hand
 284 * is, the more/less it takes to load applications with respect to the
 285 * reference device.  Accordingly, the longer/shorter BFQ grants
 286 * weight raising to interactive applications.
 287 *
 288 * BFQ uses two different reference pairs (ref_rate, ref_wr_duration),
 289 * depending on whether the device is rotational or non-rotational.
 290 *
 291 * In the following definitions, ref_rate[0] and ref_wr_duration[0]
 292 * are the reference values for a rotational device, whereas
 293 * ref_rate[1] and ref_wr_duration[1] are the reference values for a
 294 * non-rotational device. The reference rates are not the actual peak
 295 * rates of the devices used as a reference, but slightly lower
 296 * values. The reason for using slightly lower values is that the
 297 * peak-rate estimator tends to yield slightly lower values than the
 298 * actual peak rate (it can yield the actual peak rate only if there
 299 * is only one process doing I/O, and the process does sequential
 300 * I/O).
 301 *
 302 * The reference peak rates are measured in sectors/usec, left-shifted
 303 * by BFQ_RATE_SHIFT.
 304 */
 305static int ref_rate[2] = {14000, 33000};
 306/*
 307 * To improve readability, a conversion function is used to initialize
 308 * the following array, which entails that the array can be
 309 * initialized only in a function.
 310 */
 311static int ref_wr_duration[2];
 312
 313/*
 314 * BFQ uses the above-detailed, time-based weight-raising mechanism to
 315 * privilege interactive tasks. This mechanism is vulnerable to the
 316 * following false positives: I/O-bound applications that will go on
 317 * doing I/O for much longer than the duration of weight
 318 * raising. These applications have basically no benefit from being
 319 * weight-raised at the beginning of their I/O. On the opposite end,
 320 * while being weight-raised, these applications
 321 * a) unjustly steal throughput to applications that may actually need
 322 * low latency;
 323 * b) make BFQ uselessly perform device idling; device idling results
 324 * in loss of device throughput with most flash-based storage, and may
 325 * increase latencies when used purposelessly.
 326 *
 327 * BFQ tries to reduce these problems, by adopting the following
 328 * countermeasure. To introduce this countermeasure, we need first to
 329 * finish explaining how the duration of weight-raising for
 330 * interactive tasks is computed.
 331 *
 332 * For a bfq_queue deemed as interactive, the duration of weight
 333 * raising is dynamically adjusted, as a function of the estimated
 334 * peak rate of the device, so as to be equal to the time needed to
 335 * execute the 'largest' interactive task we benchmarked so far. By
 336 * largest task, we mean the task for which each involved process has
 337 * to do more I/O than for any of the other tasks we benchmarked. This
 338 * reference interactive task is the start-up of LibreOffice Writer,
 339 * and in this task each process/bfq_queue needs to have at most ~110K
 340 * sectors transferred.
 341 *
 342 * This last piece of information enables BFQ to reduce the actual
 343 * duration of weight-raising for at least one class of I/O-bound
 344 * applications: those doing sequential or quasi-sequential I/O. An
 345 * example is file copy. In fact, once started, the main I/O-bound
 346 * processes of these applications usually consume the above 110K
 347 * sectors in much less time than the processes of an application that
 348 * is starting, because these I/O-bound processes will greedily devote
 349 * almost all their CPU cycles only to their target,
 350 * throughput-friendly I/O operations. This is even more true if BFQ
 351 * happens to be underestimating the device peak rate, and thus
 352 * overestimating the duration of weight raising. But, according to
 353 * our measurements, once transferred 110K sectors, these processes
 354 * have no right to be weight-raised any longer.
 355 *
 356 * Basing on the last consideration, BFQ ends weight-raising for a
 357 * bfq_queue if the latter happens to have received an amount of
 358 * service at least equal to the following constant. The constant is
 359 * set to slightly more than 110K, to have a minimum safety margin.
 360 *
 361 * This early ending of weight-raising reduces the amount of time
 362 * during which interactive false positives cause the two problems
 363 * described at the beginning of these comments.
 364 */
 365static const unsigned long max_service_from_wr = 120000;
 366
 367/*
 368 * Maximum time between the creation of two queues, for stable merge
 369 * to be activated (in ms)
 370 */
 371static const unsigned long bfq_activation_stable_merging = 600;
 372/*
 373 * Minimum time to be waited before evaluating delayed stable merge (in ms)
 374 */
 375static const unsigned long bfq_late_stable_merging = 600;
 376
 377#define RQ_BIC(rq)              icq_to_bic((rq)->elv.priv[0])
 378#define RQ_BFQQ(rq)             ((rq)->elv.priv[1])
 379
 380struct bfq_queue *bic_to_bfqq(struct bfq_io_cq *bic, bool is_sync)
 381{
 382        return bic->bfqq[is_sync];
 383}
 384
 385static void bfq_put_stable_ref(struct bfq_queue *bfqq);
 386
 387void bic_set_bfqq(struct bfq_io_cq *bic, struct bfq_queue *bfqq, bool is_sync)
 388{
 389        /*
 390         * If bfqq != NULL, then a non-stable queue merge between
 391         * bic->bfqq and bfqq is happening here. This causes troubles
 392         * in the following case: bic->bfqq has also been scheduled
 393         * for a possible stable merge with bic->stable_merge_bfqq,
 394         * and bic->stable_merge_bfqq == bfqq happens to
 395         * hold. Troubles occur because bfqq may then undergo a split,
 396         * thereby becoming eligible for a stable merge. Yet, if
 397         * bic->stable_merge_bfqq points exactly to bfqq, then bfqq
 398         * would be stably merged with itself. To avoid this anomaly,
 399         * we cancel the stable merge if
 400         * bic->stable_merge_bfqq == bfqq.
 401         */
 402        bic->bfqq[is_sync] = bfqq;
 403
 404        if (bfqq && bic->stable_merge_bfqq == bfqq) {
 405                /*
 406                 * Actually, these same instructions are executed also
 407                 * in bfq_setup_cooperator, in case of abort or actual
 408                 * execution of a stable merge. We could avoid
 409                 * repeating these instructions there too, but if we
 410                 * did so, we would nest even more complexity in this
 411                 * function.
 412                 */
 413                bfq_put_stable_ref(bic->stable_merge_bfqq);
 414
 415                bic->stable_merge_bfqq = NULL;
 416        }
 417}
 418
 419struct bfq_data *bic_to_bfqd(struct bfq_io_cq *bic)
 420{
 421        return bic->icq.q->elevator->elevator_data;
 422}
 423
 424/**
 425 * icq_to_bic - convert iocontext queue structure to bfq_io_cq.
 426 * @icq: the iocontext queue.
 427 */
 428static struct bfq_io_cq *icq_to_bic(struct io_cq *icq)
 429{
 430        /* bic->icq is the first member, %NULL will convert to %NULL */
 431        return container_of(icq, struct bfq_io_cq, icq);
 432}
 433
 434/**
 435 * bfq_bic_lookup - search into @ioc a bic associated to @bfqd.
 436 * @bfqd: the lookup key.
 437 * @ioc: the io_context of the process doing I/O.
 438 * @q: the request queue.
 439 */
 440static struct bfq_io_cq *bfq_bic_lookup(struct bfq_data *bfqd,
 441                                        struct io_context *ioc,
 442                                        struct request_queue *q)
 443{
 444        if (ioc) {
 445                unsigned long flags;
 446                struct bfq_io_cq *icq;
 447
 448                spin_lock_irqsave(&q->queue_lock, flags);
 449                icq = icq_to_bic(ioc_lookup_icq(ioc, q));
 450                spin_unlock_irqrestore(&q->queue_lock, flags);
 451
 452                return icq;
 453        }
 454
 455        return NULL;
 456}
 457
 458/*
 459 * Scheduler run of queue, if there are requests pending and no one in the
 460 * driver that will restart queueing.
 461 */
 462void bfq_schedule_dispatch(struct bfq_data *bfqd)
 463{
 464        if (bfqd->queued != 0) {
 465                bfq_log(bfqd, "schedule dispatch");
 466                blk_mq_run_hw_queues(bfqd->queue, true);
 467        }
 468}
 469
 470#define bfq_class_idle(bfqq)    ((bfqq)->ioprio_class == IOPRIO_CLASS_IDLE)
 471
 472#define bfq_sample_valid(samples)       ((samples) > 80)
 473
 474/*
 475 * Lifted from AS - choose which of rq1 and rq2 that is best served now.
 476 * We choose the request that is closer to the head right now.  Distance
 477 * behind the head is penalized and only allowed to a certain extent.
 478 */
 479static struct request *bfq_choose_req(struct bfq_data *bfqd,
 480                                      struct request *rq1,
 481                                      struct request *rq2,
 482                                      sector_t last)
 483{
 484        sector_t s1, s2, d1 = 0, d2 = 0;
 485        unsigned long back_max;
 486#define BFQ_RQ1_WRAP    0x01 /* request 1 wraps */
 487#define BFQ_RQ2_WRAP    0x02 /* request 2 wraps */
 488        unsigned int wrap = 0; /* bit mask: requests behind the disk head? */
 489
 490        if (!rq1 || rq1 == rq2)
 491                return rq2;
 492        if (!rq2)
 493                return rq1;
 494
 495        if (rq_is_sync(rq1) && !rq_is_sync(rq2))
 496                return rq1;
 497        else if (rq_is_sync(rq2) && !rq_is_sync(rq1))
 498                return rq2;
 499        if ((rq1->cmd_flags & REQ_META) && !(rq2->cmd_flags & REQ_META))
 500                return rq1;
 501        else if ((rq2->cmd_flags & REQ_META) && !(rq1->cmd_flags & REQ_META))
 502                return rq2;
 503
 504        s1 = blk_rq_pos(rq1);
 505        s2 = blk_rq_pos(rq2);
 506
 507        /*
 508         * By definition, 1KiB is 2 sectors.
 509         */
 510        back_max = bfqd->bfq_back_max * 2;
 511
 512        /*
 513         * Strict one way elevator _except_ in the case where we allow
 514         * short backward seeks which are biased as twice the cost of a
 515         * similar forward seek.
 516         */
 517        if (s1 >= last)
 518                d1 = s1 - last;
 519        else if (s1 + back_max >= last)
 520                d1 = (last - s1) * bfqd->bfq_back_penalty;
 521        else
 522                wrap |= BFQ_RQ1_WRAP;
 523
 524        if (s2 >= last)
 525                d2 = s2 - last;
 526        else if (s2 + back_max >= last)
 527                d2 = (last - s2) * bfqd->bfq_back_penalty;
 528        else
 529                wrap |= BFQ_RQ2_WRAP;
 530
 531        /* Found required data */
 532
 533        /*
 534         * By doing switch() on the bit mask "wrap" we avoid having to
 535         * check two variables for all permutations: --> faster!
 536         */
 537        switch (wrap) {
 538        case 0: /* common case for CFQ: rq1 and rq2 not wrapped */
 539                if (d1 < d2)
 540                        return rq1;
 541                else if (d2 < d1)
 542                        return rq2;
 543
 544                if (s1 >= s2)
 545                        return rq1;
 546                else
 547                        return rq2;
 548
 549        case BFQ_RQ2_WRAP:
 550                return rq1;
 551        case BFQ_RQ1_WRAP:
 552                return rq2;
 553        case BFQ_RQ1_WRAP|BFQ_RQ2_WRAP: /* both rqs wrapped */
 554        default:
 555                /*
 556                 * Since both rqs are wrapped,
 557                 * start with the one that's further behind head
 558                 * (--> only *one* back seek required),
 559                 * since back seek takes more time than forward.
 560                 */
 561                if (s1 <= s2)
 562                        return rq1;
 563                else
 564                        return rq2;
 565        }
 566}
 567
 568/*
 569 * Async I/O can easily starve sync I/O (both sync reads and sync
 570 * writes), by consuming all tags. Similarly, storms of sync writes,
 571 * such as those that sync(2) may trigger, can starve sync reads.
 572 * Limit depths of async I/O and sync writes so as to counter both
 573 * problems.
 574 */
 575static void bfq_limit_depth(unsigned int op, struct blk_mq_alloc_data *data)
 576{
 577        struct bfq_data *bfqd = data->q->elevator->elevator_data;
 578
 579        if (op_is_sync(op) && !op_is_write(op))
 580                return;
 581
 582        data->shallow_depth =
 583                bfqd->word_depths[!!bfqd->wr_busy_queues][op_is_sync(op)];
 584
 585        bfq_log(bfqd, "[%s] wr_busy %d sync %d depth %u",
 586                        __func__, bfqd->wr_busy_queues, op_is_sync(op),
 587                        data->shallow_depth);
 588}
 589
 590static struct bfq_queue *
 591bfq_rq_pos_tree_lookup(struct bfq_data *bfqd, struct rb_root *root,
 592                     sector_t sector, struct rb_node **ret_parent,
 593                     struct rb_node ***rb_link)
 594{
 595        struct rb_node **p, *parent;
 596        struct bfq_queue *bfqq = NULL;
 597
 598        parent = NULL;
 599        p = &root->rb_node;
 600        while (*p) {
 601                struct rb_node **n;
 602
 603                parent = *p;
 604                bfqq = rb_entry(parent, struct bfq_queue, pos_node);
 605
 606                /*
 607                 * Sort strictly based on sector. Smallest to the left,
 608                 * largest to the right.
 609                 */
 610                if (sector > blk_rq_pos(bfqq->next_rq))
 611                        n = &(*p)->rb_right;
 612                else if (sector < blk_rq_pos(bfqq->next_rq))
 613                        n = &(*p)->rb_left;
 614                else
 615                        break;
 616                p = n;
 617                bfqq = NULL;
 618        }
 619
 620        *ret_parent = parent;
 621        if (rb_link)
 622                *rb_link = p;
 623
 624        bfq_log(bfqd, "rq_pos_tree_lookup %llu: returning %d",
 625                (unsigned long long)sector,
 626                bfqq ? bfqq->pid : 0);
 627
 628        return bfqq;
 629}
 630
 631static bool bfq_too_late_for_merging(struct bfq_queue *bfqq)
 632{
 633        return bfqq->service_from_backlogged > 0 &&
 634                time_is_before_jiffies(bfqq->first_IO_time +
 635                                       bfq_merge_time_limit);
 636}
 637
 638/*
 639 * The following function is not marked as __cold because it is
 640 * actually cold, but for the same performance goal described in the
 641 * comments on the likely() at the beginning of
 642 * bfq_setup_cooperator(). Unexpectedly, to reach an even lower
 643 * execution time for the case where this function is not invoked, we
 644 * had to add an unlikely() in each involved if().
 645 */
 646void __cold
 647bfq_pos_tree_add_move(struct bfq_data *bfqd, struct bfq_queue *bfqq)
 648{
 649        struct rb_node **p, *parent;
 650        struct bfq_queue *__bfqq;
 651
 652        if (bfqq->pos_root) {
 653                rb_erase(&bfqq->pos_node, bfqq->pos_root);
 654                bfqq->pos_root = NULL;
 655        }
 656
 657        /* oom_bfqq does not participate in queue merging */
 658        if (bfqq == &bfqd->oom_bfqq)
 659                return;
 660
 661        /*
 662         * bfqq cannot be merged any longer (see comments in
 663         * bfq_setup_cooperator): no point in adding bfqq into the
 664         * position tree.
 665         */
 666        if (bfq_too_late_for_merging(bfqq))
 667                return;
 668
 669        if (bfq_class_idle(bfqq))
 670                return;
 671        if (!bfqq->next_rq)
 672                return;
 673
 674        bfqq->pos_root = &bfq_bfqq_to_bfqg(bfqq)->rq_pos_tree;
 675        __bfqq = bfq_rq_pos_tree_lookup(bfqd, bfqq->pos_root,
 676                        blk_rq_pos(bfqq->next_rq), &parent, &p);
 677        if (!__bfqq) {
 678                rb_link_node(&bfqq->pos_node, parent, p);
 679                rb_insert_color(&bfqq->pos_node, bfqq->pos_root);
 680        } else
 681                bfqq->pos_root = NULL;
 682}
 683
 684/*
 685 * The following function returns false either if every active queue
 686 * must receive the same share of the throughput (symmetric scenario),
 687 * or, as a special case, if bfqq must receive a share of the
 688 * throughput lower than or equal to the share that every other active
 689 * queue must receive.  If bfqq does sync I/O, then these are the only
 690 * two cases where bfqq happens to be guaranteed its share of the
 691 * throughput even if I/O dispatching is not plugged when bfqq remains
 692 * temporarily empty (for more details, see the comments in the
 693 * function bfq_better_to_idle()). For this reason, the return value
 694 * of this function is used to check whether I/O-dispatch plugging can
 695 * be avoided.
 696 *
 697 * The above first case (symmetric scenario) occurs when:
 698 * 1) all active queues have the same weight,
 699 * 2) all active queues belong to the same I/O-priority class,
 700 * 3) all active groups at the same level in the groups tree have the same
 701 *    weight,
 702 * 4) all active groups at the same level in the groups tree have the same
 703 *    number of children.
 704 *
 705 * Unfortunately, keeping the necessary state for evaluating exactly
 706 * the last two symmetry sub-conditions above would be quite complex
 707 * and time consuming. Therefore this function evaluates, instead,
 708 * only the following stronger three sub-conditions, for which it is
 709 * much easier to maintain the needed state:
 710 * 1) all active queues have the same weight,
 711 * 2) all active queues belong to the same I/O-priority class,
 712 * 3) there are no active groups.
 713 * In particular, the last condition is always true if hierarchical
 714 * support or the cgroups interface are not enabled, thus no state
 715 * needs to be maintained in this case.
 716 */
 717static bool bfq_asymmetric_scenario(struct bfq_data *bfqd,
 718                                   struct bfq_queue *bfqq)
 719{
 720        bool smallest_weight = bfqq &&
 721                bfqq->weight_counter &&
 722                bfqq->weight_counter ==
 723                container_of(
 724                        rb_first_cached(&bfqd->queue_weights_tree),
 725                        struct bfq_weight_counter,
 726                        weights_node);
 727
 728        /*
 729         * For queue weights to differ, queue_weights_tree must contain
 730         * at least two nodes.
 731         */
 732        bool varied_queue_weights = !smallest_weight &&
 733                !RB_EMPTY_ROOT(&bfqd->queue_weights_tree.rb_root) &&
 734                (bfqd->queue_weights_tree.rb_root.rb_node->rb_left ||
 735                 bfqd->queue_weights_tree.rb_root.rb_node->rb_right);
 736
 737        bool multiple_classes_busy =
 738                (bfqd->busy_queues[0] && bfqd->busy_queues[1]) ||
 739                (bfqd->busy_queues[0] && bfqd->busy_queues[2]) ||
 740                (bfqd->busy_queues[1] && bfqd->busy_queues[2]);
 741
 742        return varied_queue_weights || multiple_classes_busy
 743#ifdef CONFIG_BFQ_GROUP_IOSCHED
 744               || bfqd->num_groups_with_pending_reqs > 0
 745#endif
 746                ;
 747}
 748
 749/*
 750 * If the weight-counter tree passed as input contains no counter for
 751 * the weight of the input queue, then add that counter; otherwise just
 752 * increment the existing counter.
 753 *
 754 * Note that weight-counter trees contain few nodes in mostly symmetric
 755 * scenarios. For example, if all queues have the same weight, then the
 756 * weight-counter tree for the queues may contain at most one node.
 757 * This holds even if low_latency is on, because weight-raised queues
 758 * are not inserted in the tree.
 759 * In most scenarios, the rate at which nodes are created/destroyed
 760 * should be low too.
 761 */
 762void bfq_weights_tree_add(struct bfq_data *bfqd, struct bfq_queue *bfqq,
 763                          struct rb_root_cached *root)
 764{
 765        struct bfq_entity *entity = &bfqq->entity;
 766        struct rb_node **new = &(root->rb_root.rb_node), *parent = NULL;
 767        bool leftmost = true;
 768
 769        /*
 770         * Do not insert if the queue is already associated with a
 771         * counter, which happens if:
 772         *   1) a request arrival has caused the queue to become both
 773         *      non-weight-raised, and hence change its weight, and
 774         *      backlogged; in this respect, each of the two events
 775         *      causes an invocation of this function,
 776         *   2) this is the invocation of this function caused by the
 777         *      second event. This second invocation is actually useless,
 778         *      and we handle this fact by exiting immediately. More
 779         *      efficient or clearer solutions might possibly be adopted.
 780         */
 781        if (bfqq->weight_counter)
 782                return;
 783
 784        while (*new) {
 785                struct bfq_weight_counter *__counter = container_of(*new,
 786                                                struct bfq_weight_counter,
 787                                                weights_node);
 788                parent = *new;
 789
 790                if (entity->weight == __counter->weight) {
 791                        bfqq->weight_counter = __counter;
 792                        goto inc_counter;
 793                }
 794                if (entity->weight < __counter->weight)
 795                        new = &((*new)->rb_left);
 796                else {
 797                        new = &((*new)->rb_right);
 798                        leftmost = false;
 799                }
 800        }
 801
 802        bfqq->weight_counter = kzalloc(sizeof(struct bfq_weight_counter),
 803                                       GFP_ATOMIC);
 804
 805        /*
 806         * In the unlucky event of an allocation failure, we just
 807         * exit. This will cause the weight of queue to not be
 808         * considered in bfq_asymmetric_scenario, which, in its turn,
 809         * causes the scenario to be deemed wrongly symmetric in case
 810         * bfqq's weight would have been the only weight making the
 811         * scenario asymmetric.  On the bright side, no unbalance will
 812         * however occur when bfqq becomes inactive again (the
 813         * invocation of this function is triggered by an activation
 814         * of queue).  In fact, bfq_weights_tree_remove does nothing
 815         * if !bfqq->weight_counter.
 816         */
 817        if (unlikely(!bfqq->weight_counter))
 818                return;
 819
 820        bfqq->weight_counter->weight = entity->weight;
 821        rb_link_node(&bfqq->weight_counter->weights_node, parent, new);
 822        rb_insert_color_cached(&bfqq->weight_counter->weights_node, root,
 823                                leftmost);
 824
 825inc_counter:
 826        bfqq->weight_counter->num_active++;
 827        bfqq->ref++;
 828}
 829
 830/*
 831 * Decrement the weight counter associated with the queue, and, if the
 832 * counter reaches 0, remove the counter from the tree.
 833 * See the comments to the function bfq_weights_tree_add() for considerations
 834 * about overhead.
 835 */
 836void __bfq_weights_tree_remove(struct bfq_data *bfqd,
 837                               struct bfq_queue *bfqq,
 838                               struct rb_root_cached *root)
 839{
 840        if (!bfqq->weight_counter)
 841                return;
 842
 843        bfqq->weight_counter->num_active--;
 844        if (bfqq->weight_counter->num_active > 0)
 845                goto reset_entity_pointer;
 846
 847        rb_erase_cached(&bfqq->weight_counter->weights_node, root);
 848        kfree(bfqq->weight_counter);
 849
 850reset_entity_pointer:
 851        bfqq->weight_counter = NULL;
 852        bfq_put_queue(bfqq);
 853}
 854
 855/*
 856 * Invoke __bfq_weights_tree_remove on bfqq and decrement the number
 857 * of active groups for each queue's inactive parent entity.
 858 */
 859void bfq_weights_tree_remove(struct bfq_data *bfqd,
 860                             struct bfq_queue *bfqq)
 861{
 862        struct bfq_entity *entity = bfqq->entity.parent;
 863
 864        for_each_entity(entity) {
 865                struct bfq_sched_data *sd = entity->my_sched_data;
 866
 867                if (sd->next_in_service || sd->in_service_entity) {
 868                        /*
 869                         * entity is still active, because either
 870                         * next_in_service or in_service_entity is not
 871                         * NULL (see the comments on the definition of
 872                         * next_in_service for details on why
 873                         * in_service_entity must be checked too).
 874                         *
 875                         * As a consequence, its parent entities are
 876                         * active as well, and thus this loop must
 877                         * stop here.
 878                         */
 879                        break;
 880                }
 881
 882                /*
 883                 * The decrement of num_groups_with_pending_reqs is
 884                 * not performed immediately upon the deactivation of
 885                 * entity, but it is delayed to when it also happens
 886                 * that the first leaf descendant bfqq of entity gets
 887                 * all its pending requests completed. The following
 888                 * instructions perform this delayed decrement, if
 889                 * needed. See the comments on
 890                 * num_groups_with_pending_reqs for details.
 891                 */
 892                if (entity->in_groups_with_pending_reqs) {
 893                        entity->in_groups_with_pending_reqs = false;
 894                        bfqd->num_groups_with_pending_reqs--;
 895                }
 896        }
 897
 898        /*
 899         * Next function is invoked last, because it causes bfqq to be
 900         * freed if the following holds: bfqq is not in service and
 901         * has no dispatched request. DO NOT use bfqq after the next
 902         * function invocation.
 903         */
 904        __bfq_weights_tree_remove(bfqd, bfqq,
 905                                  &bfqd->queue_weights_tree);
 906}
 907
 908/*
 909 * Return expired entry, or NULL to just start from scratch in rbtree.
 910 */
 911static struct request *bfq_check_fifo(struct bfq_queue *bfqq,
 912                                      struct request *last)
 913{
 914        struct request *rq;
 915
 916        if (bfq_bfqq_fifo_expire(bfqq))
 917                return NULL;
 918
 919        bfq_mark_bfqq_fifo_expire(bfqq);
 920
 921        rq = rq_entry_fifo(bfqq->fifo.next);
 922
 923        if (rq == last || ktime_get_ns() < rq->fifo_time)
 924                return NULL;
 925
 926        bfq_log_bfqq(bfqq->bfqd, bfqq, "check_fifo: returned %p", rq);
 927        return rq;
 928}
 929
 930static struct request *bfq_find_next_rq(struct bfq_data *bfqd,
 931                                        struct bfq_queue *bfqq,
 932                                        struct request *last)
 933{
 934        struct rb_node *rbnext = rb_next(&last->rb_node);
 935        struct rb_node *rbprev = rb_prev(&last->rb_node);
 936        struct request *next, *prev = NULL;
 937
 938        /* Follow expired path, else get first next available. */
 939        next = bfq_check_fifo(bfqq, last);
 940        if (next)
 941                return next;
 942
 943        if (rbprev)
 944                prev = rb_entry_rq(rbprev);
 945
 946        if (rbnext)
 947                next = rb_entry_rq(rbnext);
 948        else {
 949                rbnext = rb_first(&bfqq->sort_list);
 950                if (rbnext && rbnext != &last->rb_node)
 951                        next = rb_entry_rq(rbnext);
 952        }
 953
 954        return bfq_choose_req(bfqd, next, prev, blk_rq_pos(last));
 955}
 956
 957/* see the definition of bfq_async_charge_factor for details */
 958static unsigned long bfq_serv_to_charge(struct request *rq,
 959                                        struct bfq_queue *bfqq)
 960{
 961        if (bfq_bfqq_sync(bfqq) || bfqq->wr_coeff > 1 ||
 962            bfq_asymmetric_scenario(bfqq->bfqd, bfqq))
 963                return blk_rq_sectors(rq);
 964
 965        return blk_rq_sectors(rq) * bfq_async_charge_factor;
 966}
 967
 968/**
 969 * bfq_updated_next_req - update the queue after a new next_rq selection.
 970 * @bfqd: the device data the queue belongs to.
 971 * @bfqq: the queue to update.
 972 *
 973 * If the first request of a queue changes we make sure that the queue
 974 * has enough budget to serve at least its first request (if the
 975 * request has grown).  We do this because if the queue has not enough
 976 * budget for its first request, it has to go through two dispatch
 977 * rounds to actually get it dispatched.
 978 */
 979static void bfq_updated_next_req(struct bfq_data *bfqd,
 980                                 struct bfq_queue *bfqq)
 981{
 982        struct bfq_entity *entity = &bfqq->entity;
 983        struct request *next_rq = bfqq->next_rq;
 984        unsigned long new_budget;
 985
 986        if (!next_rq)
 987                return;
 988
 989        if (bfqq == bfqd->in_service_queue)
 990                /*
 991                 * In order not to break guarantees, budgets cannot be
 992                 * changed after an entity has been selected.
 993                 */
 994                return;
 995
 996        new_budget = max_t(unsigned long,
 997                           max_t(unsigned long, bfqq->max_budget,
 998                                 bfq_serv_to_charge(next_rq, bfqq)),
 999                           entity->service);
1000        if (entity->budget != new_budget) {
1001                entity->budget = new_budget;
1002                bfq_log_bfqq(bfqd, bfqq, "updated next rq: new budget %lu",
1003                                         new_budget);
1004                bfq_requeue_bfqq(bfqd, bfqq, false);
1005        }
1006}
1007
1008static unsigned int bfq_wr_duration(struct bfq_data *bfqd)
1009{
1010        u64 dur;
1011
1012        if (bfqd->bfq_wr_max_time > 0)
1013                return bfqd->bfq_wr_max_time;
1014
1015        dur = bfqd->rate_dur_prod;
1016        do_div(dur, bfqd->peak_rate);
1017
1018        /*
1019         * Limit duration between 3 and 25 seconds. The upper limit
1020         * has been conservatively set after the following worst case:
1021         * on a QEMU/KVM virtual machine
1022         * - running in a slow PC
1023         * - with a virtual disk stacked on a slow low-end 5400rpm HDD
1024         * - serving a heavy I/O workload, such as the sequential reading
1025         *   of several files
1026         * mplayer took 23 seconds to start, if constantly weight-raised.
1027         *
1028         * As for higher values than that accommodating the above bad
1029         * scenario, tests show that higher values would often yield
1030         * the opposite of the desired result, i.e., would worsen
1031         * responsiveness by allowing non-interactive applications to
1032         * preserve weight raising for too long.
1033         *
1034         * On the other end, lower values than 3 seconds make it
1035         * difficult for most interactive tasks to complete their jobs
1036         * before weight-raising finishes.
1037         */
1038        return clamp_val(dur, msecs_to_jiffies(3000), msecs_to_jiffies(25000));
1039}
1040
1041/* switch back from soft real-time to interactive weight raising */
1042static void switch_back_to_interactive_wr(struct bfq_queue *bfqq,
1043                                          struct bfq_data *bfqd)
1044{
1045        bfqq->wr_coeff = bfqd->bfq_wr_coeff;
1046        bfqq->wr_cur_max_time = bfq_wr_duration(bfqd);
1047        bfqq->last_wr_start_finish = bfqq->wr_start_at_switch_to_srt;
1048}
1049
1050static void
1051bfq_bfqq_resume_state(struct bfq_queue *bfqq, struct bfq_data *bfqd,
1052                      struct bfq_io_cq *bic, bool bfq_already_existing)
1053{
1054        unsigned int old_wr_coeff = 1;
1055        bool busy = bfq_already_existing && bfq_bfqq_busy(bfqq);
1056
1057        if (bic->saved_has_short_ttime)
1058                bfq_mark_bfqq_has_short_ttime(bfqq);
1059        else
1060                bfq_clear_bfqq_has_short_ttime(bfqq);
1061
1062        if (bic->saved_IO_bound)
1063                bfq_mark_bfqq_IO_bound(bfqq);
1064        else
1065                bfq_clear_bfqq_IO_bound(bfqq);
1066
1067        bfqq->last_serv_time_ns = bic->saved_last_serv_time_ns;
1068        bfqq->inject_limit = bic->saved_inject_limit;
1069        bfqq->decrease_time_jif = bic->saved_decrease_time_jif;
1070
1071        bfqq->entity.new_weight = bic->saved_weight;
1072        bfqq->ttime = bic->saved_ttime;
1073        bfqq->io_start_time = bic->saved_io_start_time;
1074        bfqq->tot_idle_time = bic->saved_tot_idle_time;
1075        /*
1076         * Restore weight coefficient only if low_latency is on
1077         */
1078        if (bfqd->low_latency) {
1079                old_wr_coeff = bfqq->wr_coeff;
1080                bfqq->wr_coeff = bic->saved_wr_coeff;
1081        }
1082        bfqq->service_from_wr = bic->saved_service_from_wr;
1083        bfqq->wr_start_at_switch_to_srt = bic->saved_wr_start_at_switch_to_srt;
1084        bfqq->last_wr_start_finish = bic->saved_last_wr_start_finish;
1085        bfqq->wr_cur_max_time = bic->saved_wr_cur_max_time;
1086
1087        if (bfqq->wr_coeff > 1 && (bfq_bfqq_in_large_burst(bfqq) ||
1088            time_is_before_jiffies(bfqq->last_wr_start_finish +
1089                                   bfqq->wr_cur_max_time))) {
1090                if (bfqq->wr_cur_max_time == bfqd->bfq_wr_rt_max_time &&
1091                    !bfq_bfqq_in_large_burst(bfqq) &&
1092                    time_is_after_eq_jiffies(bfqq->wr_start_at_switch_to_srt +
1093                                             bfq_wr_duration(bfqd))) {
1094                        switch_back_to_interactive_wr(bfqq, bfqd);
1095                } else {
1096                        bfqq->wr_coeff = 1;
1097                        bfq_log_bfqq(bfqq->bfqd, bfqq,
1098                                     "resume state: switching off wr");
1099                }
1100        }
1101
1102        /* make sure weight will be updated, however we got here */
1103        bfqq->entity.prio_changed = 1;
1104
1105        if (likely(!busy))
1106                return;
1107
1108        if (old_wr_coeff == 1 && bfqq->wr_coeff > 1)
1109                bfqd->wr_busy_queues++;
1110        else if (old_wr_coeff > 1 && bfqq->wr_coeff == 1)
1111                bfqd->wr_busy_queues--;
1112}
1113
1114static int bfqq_process_refs(struct bfq_queue *bfqq)
1115{
1116        return bfqq->ref - bfqq->allocated - bfqq->entity.on_st_or_in_serv -
1117                (bfqq->weight_counter != NULL) - bfqq->stable_ref;
1118}
1119
1120/* Empty burst list and add just bfqq (see comments on bfq_handle_burst) */
1121static void bfq_reset_burst_list(struct bfq_data *bfqd, struct bfq_queue *bfqq)
1122{
1123        struct bfq_queue *item;
1124        struct hlist_node *n;
1125
1126        hlist_for_each_entry_safe(item, n, &bfqd->burst_list, burst_list_node)
1127                hlist_del_init(&item->burst_list_node);
1128
1129        /*
1130         * Start the creation of a new burst list only if there is no
1131         * active queue. See comments on the conditional invocation of
1132         * bfq_handle_burst().
1133         */
1134        if (bfq_tot_busy_queues(bfqd) == 0) {
1135                hlist_add_head(&bfqq->burst_list_node, &bfqd->burst_list);
1136                bfqd->burst_size = 1;
1137        } else
1138                bfqd->burst_size = 0;
1139
1140        bfqd->burst_parent_entity = bfqq->entity.parent;
1141}
1142
1143/* Add bfqq to the list of queues in current burst (see bfq_handle_burst) */
1144static void bfq_add_to_burst(struct bfq_data *bfqd, struct bfq_queue *bfqq)
1145{
1146        /* Increment burst size to take into account also bfqq */
1147        bfqd->burst_size++;
1148
1149        if (bfqd->burst_size == bfqd->bfq_large_burst_thresh) {
1150                struct bfq_queue *pos, *bfqq_item;
1151                struct hlist_node *n;
1152
1153                /*
1154                 * Enough queues have been activated shortly after each
1155                 * other to consider this burst as large.
1156                 */
1157                bfqd->large_burst = true;
1158
1159                /*
1160                 * We can now mark all queues in the burst list as
1161                 * belonging to a large burst.
1162                 */
1163                hlist_for_each_entry(bfqq_item, &bfqd->burst_list,
1164                                     burst_list_node)
1165                        bfq_mark_bfqq_in_large_burst(bfqq_item);
1166                bfq_mark_bfqq_in_large_burst(bfqq);
1167
1168                /*
1169                 * From now on, and until the current burst finishes, any
1170                 * new queue being activated shortly after the last queue
1171                 * was inserted in the burst can be immediately marked as
1172                 * belonging to a large burst. So the burst list is not
1173                 * needed any more. Remove it.
1174                 */
1175                hlist_for_each_entry_safe(pos, n, &bfqd->burst_list,
1176                                          burst_list_node)
1177                        hlist_del_init(&pos->burst_list_node);
1178        } else /*
1179                * Burst not yet large: add bfqq to the burst list. Do
1180                * not increment the ref counter for bfqq, because bfqq
1181                * is removed from the burst list before freeing bfqq
1182                * in put_queue.
1183                */
1184                hlist_add_head(&bfqq->burst_list_node, &bfqd->burst_list);
1185}
1186
1187/*
1188 * If many queues belonging to the same group happen to be created
1189 * shortly after each other, then the processes associated with these
1190 * queues have typically a common goal. In particular, bursts of queue
1191 * creations are usually caused by services or applications that spawn
1192 * many parallel threads/processes. Examples are systemd during boot,
1193 * or git grep. To help these processes get their job done as soon as
1194 * possible, it is usually better to not grant either weight-raising
1195 * or device idling to their queues, unless these queues must be
1196 * protected from the I/O flowing through other active queues.
1197 *
1198 * In this comment we describe, firstly, the reasons why this fact
1199 * holds, and, secondly, the next function, which implements the main
1200 * steps needed to properly mark these queues so that they can then be
1201 * treated in a different way.
1202 *
1203 * The above services or applications benefit mostly from a high
1204 * throughput: the quicker the requests of the activated queues are
1205 * cumulatively served, the sooner the target job of these queues gets
1206 * completed. As a consequence, weight-raising any of these queues,
1207 * which also implies idling the device for it, is almost always
1208 * counterproductive, unless there are other active queues to isolate
1209 * these new queues from. If there no other active queues, then
1210 * weight-raising these new queues just lowers throughput in most
1211 * cases.
1212 *
1213 * On the other hand, a burst of queue creations may be caused also by
1214 * the start of an application that does not consist of a lot of
1215 * parallel I/O-bound threads. In fact, with a complex application,
1216 * several short processes may need to be executed to start-up the
1217 * application. In this respect, to start an application as quickly as
1218 * possible, the best thing to do is in any case to privilege the I/O
1219 * related to the application with respect to all other
1220 * I/O. Therefore, the best strategy to start as quickly as possible
1221 * an application that causes a burst of queue creations is to
1222 * weight-raise all the queues created during the burst. This is the
1223 * exact opposite of the best strategy for the other type of bursts.
1224 *
1225 * In the end, to take the best action for each of the two cases, the
1226 * two types of bursts need to be distinguished. Fortunately, this
1227 * seems relatively easy, by looking at the sizes of the bursts. In
1228 * particular, we found a threshold such that only bursts with a
1229 * larger size than that threshold are apparently caused by
1230 * services or commands such as systemd or git grep. For brevity,
1231 * hereafter we call just 'large' these bursts. BFQ *does not*
1232 * weight-raise queues whose creation occurs in a large burst. In
1233 * addition, for each of these queues BFQ performs or does not perform
1234 * idling depending on which choice boosts the throughput more. The
1235 * exact choice depends on the device and request pattern at
1236 * hand.
1237 *
1238 * Unfortunately, false positives may occur while an interactive task
1239 * is starting (e.g., an application is being started). The
1240 * consequence is that the queues associated with the task do not
1241 * enjoy weight raising as expected. Fortunately these false positives
1242 * are very rare. They typically occur if some service happens to
1243 * start doing I/O exactly when the interactive task starts.
1244 *
1245 * Turning back to the next function, it is invoked only if there are
1246 * no active queues (apart from active queues that would belong to the
1247 * same, possible burst bfqq would belong to), and it implements all
1248 * the steps needed to detect the occurrence of a large burst and to
1249 * properly mark all the queues belonging to it (so that they can then
1250 * be treated in a different way). This goal is achieved by
1251 * maintaining a "burst list" that holds, temporarily, the queues that
1252 * belong to the burst in progress. The list is then used to mark
1253 * these queues as belonging to a large burst if the burst does become
1254 * large. The main steps are the following.
1255 *
1256 * . when the very first queue is created, the queue is inserted into the
1257 *   list (as it could be the first queue in a possible burst)
1258 *
1259 * . if the current burst has not yet become large, and a queue Q that does
1260 *   not yet belong to the burst is activated shortly after the last time
1261 *   at which a new queue entered the burst list, then the function appends
1262 *   Q to the burst list
1263 *
1264 * . if, as a consequence of the previous step, the burst size reaches
1265 *   the large-burst threshold, then
1266 *
1267 *     . all the queues in the burst list are marked as belonging to a
1268 *       large burst
1269 *
1270 *     . the burst list is deleted; in fact, the burst list already served
1271 *       its purpose (keeping temporarily track of the queues in a burst,
1272 *       so as to be able to mark them as belonging to a large burst in the
1273 *       previous sub-step), and now is not needed any more
1274 *
1275 *     . the device enters a large-burst mode
1276 *
1277 * . if a queue Q that does not belong to the burst is created while
1278 *   the device is in large-burst mode and shortly after the last time
1279 *   at which a queue either entered the burst list or was marked as
1280 *   belonging to the current large burst, then Q is immediately marked
1281 *   as belonging to a large burst.
1282 *
1283 * . if a queue Q that does not belong to the burst is created a while
1284 *   later, i.e., not shortly after, than the last time at which a queue
1285 *   either entered the burst list or was marked as belonging to the
1286 *   current large burst, then the current burst is deemed as finished and:
1287 *
1288 *        . the large-burst mode is reset if set
1289 *
1290 *        . the burst list is emptied
1291 *
1292 *        . Q is inserted in the burst list, as Q may be the first queue
1293 *          in a possible new burst (then the burst list contains just Q
1294 *          after this step).
1295 */
1296static void bfq_handle_burst(struct bfq_data *bfqd, struct bfq_queue *bfqq)
1297{
1298        /*
1299         * If bfqq is already in the burst list or is part of a large
1300         * burst, or finally has just been split, then there is
1301         * nothing else to do.
1302         */
1303        if (!hlist_unhashed(&bfqq->burst_list_node) ||
1304            bfq_bfqq_in_large_burst(bfqq) ||
1305            time_is_after_eq_jiffies(bfqq->split_time +
1306                                     msecs_to_jiffies(10)))
1307                return;
1308
1309        /*
1310         * If bfqq's creation happens late enough, or bfqq belongs to
1311         * a different group than the burst group, then the current
1312         * burst is finished, and related data structures must be
1313         * reset.
1314         *
1315         * In this respect, consider the special case where bfqq is
1316         * the very first queue created after BFQ is selected for this
1317         * device. In this case, last_ins_in_burst and
1318         * burst_parent_entity are not yet significant when we get
1319         * here. But it is easy to verify that, whether or not the
1320         * following condition is true, bfqq will end up being
1321         * inserted into the burst list. In particular the list will
1322         * happen to contain only bfqq. And this is exactly what has
1323         * to happen, as bfqq may be the first queue of the first
1324         * burst.
1325         */
1326        if (time_is_before_jiffies(bfqd->last_ins_in_burst +
1327            bfqd->bfq_burst_interval) ||
1328            bfqq->entity.parent != bfqd->burst_parent_entity) {
1329                bfqd->large_burst = false;
1330                bfq_reset_burst_list(bfqd, bfqq);
1331                goto end;
1332        }
1333
1334        /*
1335         * If we get here, then bfqq is being activated shortly after the
1336         * last queue. So, if the current burst is also large, we can mark
1337         * bfqq as belonging to this large burst immediately.
1338         */
1339        if (bfqd->large_burst) {
1340                bfq_mark_bfqq_in_large_burst(bfqq);
1341                goto end;
1342        }
1343
1344        /*
1345         * If we get here, then a large-burst state has not yet been
1346         * reached, but bfqq is being activated shortly after the last
1347         * queue. Then we add bfqq to the burst.
1348         */
1349        bfq_add_to_burst(bfqd, bfqq);
1350end:
1351        /*
1352         * At this point, bfqq either has been added to the current
1353         * burst or has caused the current burst to terminate and a
1354         * possible new burst to start. In particular, in the second
1355         * case, bfqq has become the first queue in the possible new
1356         * burst.  In both cases last_ins_in_burst needs to be moved
1357         * forward.
1358         */
1359        bfqd->last_ins_in_burst = jiffies;
1360}
1361
1362static int bfq_bfqq_budget_left(struct bfq_queue *bfqq)
1363{
1364        struct bfq_entity *entity = &bfqq->entity;
1365
1366        return entity->budget - entity->service;
1367}
1368
1369/*
1370 * If enough samples have been computed, return the current max budget
1371 * stored in bfqd, which is dynamically updated according to the
1372 * estimated disk peak rate; otherwise return the default max budget
1373 */
1374static int bfq_max_budget(struct bfq_data *bfqd)
1375{
1376        if (bfqd->budgets_assigned < bfq_stats_min_budgets)
1377                return bfq_default_max_budget;
1378        else
1379                return bfqd->bfq_max_budget;
1380}
1381
1382/*
1383 * Return min budget, which is a fraction of the current or default
1384 * max budget (trying with 1/32)
1385 */
1386static int bfq_min_budget(struct bfq_data *bfqd)
1387{
1388        if (bfqd->budgets_assigned < bfq_stats_min_budgets)
1389                return bfq_default_max_budget / 32;
1390        else
1391                return bfqd->bfq_max_budget / 32;
1392}
1393
1394/*
1395 * The next function, invoked after the input queue bfqq switches from
1396 * idle to busy, updates the budget of bfqq. The function also tells
1397 * whether the in-service queue should be expired, by returning
1398 * true. The purpose of expiring the in-service queue is to give bfqq
1399 * the chance to possibly preempt the in-service queue, and the reason
1400 * for preempting the in-service queue is to achieve one of the two
1401 * goals below.
1402 *
1403 * 1. Guarantee to bfqq its reserved bandwidth even if bfqq has
1404 * expired because it has remained idle. In particular, bfqq may have
1405 * expired for one of the following two reasons:
1406 *
1407 * - BFQQE_NO_MORE_REQUESTS bfqq did not enjoy any device idling
1408 *   and did not make it to issue a new request before its last
1409 *   request was served;
1410 *
1411 * - BFQQE_TOO_IDLE bfqq did enjoy device idling, but did not issue
1412 *   a new request before the expiration of the idling-time.
1413 *
1414 * Even if bfqq has expired for one of the above reasons, the process
1415 * associated with the queue may be however issuing requests greedily,
1416 * and thus be sensitive to the bandwidth it receives (bfqq may have
1417 * remained idle for other reasons: CPU high load, bfqq not enjoying
1418 * idling, I/O throttling somewhere in the path from the process to
1419 * the I/O scheduler, ...). But if, after every expiration for one of
1420 * the above two reasons, bfqq has to wait for the service of at least
1421 * one full budget of another queue before being served again, then
1422 * bfqq is likely to get a much lower bandwidth or resource time than
1423 * its reserved ones. To address this issue, two countermeasures need
1424 * to be taken.
1425 *
1426 * First, the budget and the timestamps of bfqq need to be updated in
1427 * a special way on bfqq reactivation: they need to be updated as if
1428 * bfqq did not remain idle and did not expire. In fact, if they are
1429 * computed as if bfqq expired and remained idle until reactivation,
1430 * then the process associated with bfqq is treated as if, instead of
1431 * being greedy, it stopped issuing requests when bfqq remained idle,
1432 * and restarts issuing requests only on this reactivation. In other
1433 * words, the scheduler does not help the process recover the "service
1434 * hole" between bfqq expiration and reactivation. As a consequence,
1435 * the process receives a lower bandwidth than its reserved one. In
1436 * contrast, to recover this hole, the budget must be updated as if
1437 * bfqq was not expired at all before this reactivation, i.e., it must
1438 * be set to the value of the remaining budget when bfqq was
1439 * expired. Along the same line, timestamps need to be assigned the
1440 * value they had the last time bfqq was selected for service, i.e.,
1441 * before last expiration. Thus timestamps need to be back-shifted
1442 * with respect to their normal computation (see [1] for more details
1443 * on this tricky aspect).
1444 *
1445 * Secondly, to allow the process to recover the hole, the in-service
1446 * queue must be expired too, to give bfqq the chance to preempt it
1447 * immediately. In fact, if bfqq has to wait for a full budget of the
1448 * in-service queue to be completed, then it may become impossible to
1449 * let the process recover the hole, even if the back-shifted
1450 * timestamps of bfqq are lower than those of the in-service queue. If
1451 * this happens for most or all of the holes, then the process may not
1452 * receive its reserved bandwidth. In this respect, it is worth noting
1453 * that, being the service of outstanding requests unpreemptible, a
1454 * little fraction of the holes may however be unrecoverable, thereby
1455 * causing a little loss of bandwidth.
1456 *
1457 * The last important point is detecting whether bfqq does need this
1458 * bandwidth recovery. In this respect, the next function deems the
1459 * process associated with bfqq greedy, and thus allows it to recover
1460 * the hole, if: 1) the process is waiting for the arrival of a new
1461 * request (which implies that bfqq expired for one of the above two
1462 * reasons), and 2) such a request has arrived soon. The first
1463 * condition is controlled through the flag non_blocking_wait_rq,
1464 * while the second through the flag arrived_in_time. If both
1465 * conditions hold, then the function computes the budget in the
1466 * above-described special way, and signals that the in-service queue
1467 * should be expired. Timestamp back-shifting is done later in
1468 * __bfq_activate_entity.
1469 *
1470 * 2. Reduce latency. Even if timestamps are not backshifted to let
1471 * the process associated with bfqq recover a service hole, bfqq may
1472 * however happen to have, after being (re)activated, a lower finish
1473 * timestamp than the in-service queue.  That is, the next budget of
1474 * bfqq may have to be completed before the one of the in-service
1475 * queue. If this is the case, then preempting the in-service queue
1476 * allows this goal to be achieved, apart from the unpreemptible,
1477 * outstanding requests mentioned above.
1478 *
1479 * Unfortunately, regardless of which of the above two goals one wants
1480 * to achieve, service trees need first to be updated to know whether
1481 * the in-service queue must be preempted. To have service trees
1482 * correctly updated, the in-service queue must be expired and
1483 * rescheduled, and bfqq must be scheduled too. This is one of the
1484 * most costly operations (in future versions, the scheduling
1485 * mechanism may be re-designed in such a way to make it possible to
1486 * know whether preemption is needed without needing to update service
1487 * trees). In addition, queue preemptions almost always cause random
1488 * I/O, which may in turn cause loss of throughput. Finally, there may
1489 * even be no in-service queue when the next function is invoked (so,
1490 * no queue to compare timestamps with). Because of these facts, the
1491 * next function adopts the following simple scheme to avoid costly
1492 * operations, too frequent preemptions and too many dependencies on
1493 * the state of the scheduler: it requests the expiration of the
1494 * in-service queue (unconditionally) only for queues that need to
1495 * recover a hole. Then it delegates to other parts of the code the
1496 * responsibility of handling the above case 2.
1497 */
1498static bool bfq_bfqq_update_budg_for_activation(struct bfq_data *bfqd,
1499                                                struct bfq_queue *bfqq,
1500                                                bool arrived_in_time)
1501{
1502        struct bfq_entity *entity = &bfqq->entity;
1503
1504        /*
1505         * In the next compound condition, we check also whether there
1506         * is some budget left, because otherwise there is no point in
1507         * trying to go on serving bfqq with this same budget: bfqq
1508         * would be expired immediately after being selected for
1509         * service. This would only cause useless overhead.
1510         */
1511        if (bfq_bfqq_non_blocking_wait_rq(bfqq) && arrived_in_time &&
1512            bfq_bfqq_budget_left(bfqq) > 0) {
1513                /*
1514                 * We do not clear the flag non_blocking_wait_rq here, as
1515                 * the latter is used in bfq_activate_bfqq to signal
1516                 * that timestamps need to be back-shifted (and is
1517                 * cleared right after).
1518                 */
1519
1520                /*
1521                 * In next assignment we rely on that either
1522                 * entity->service or entity->budget are not updated
1523                 * on expiration if bfqq is empty (see
1524                 * __bfq_bfqq_recalc_budget). Thus both quantities
1525                 * remain unchanged after such an expiration, and the
1526                 * following statement therefore assigns to
1527                 * entity->budget the remaining budget on such an
1528                 * expiration.
1529                 */
1530                entity->budget = min_t(unsigned long,
1531                                       bfq_bfqq_budget_left(bfqq),
1532                                       bfqq->max_budget);
1533
1534                /*
1535                 * At this point, we have used entity->service to get
1536                 * the budget left (needed for updating
1537                 * entity->budget). Thus we finally can, and have to,
1538                 * reset entity->service. The latter must be reset
1539                 * because bfqq would otherwise be charged again for
1540                 * the service it has received during its previous
1541                 * service slot(s).
1542                 */
1543                entity->service = 0;
1544
1545                return true;
1546        }
1547
1548        /*
1549         * We can finally complete expiration, by setting service to 0.
1550         */
1551        entity->service = 0;
1552        entity->budget = max_t(unsigned long, bfqq->max_budget,
1553                               bfq_serv_to_charge(bfqq->next_rq, bfqq));
1554        bfq_clear_bfqq_non_blocking_wait_rq(bfqq);
1555        return false;
1556}
1557
1558/*
1559 * Return the farthest past time instant according to jiffies
1560 * macros.
1561 */
1562static unsigned long bfq_smallest_from_now(void)
1563{
1564        return jiffies - MAX_JIFFY_OFFSET;
1565}
1566
1567static void bfq_update_bfqq_wr_on_rq_arrival(struct bfq_data *bfqd,
1568                                             struct bfq_queue *bfqq,
1569                                             unsigned int old_wr_coeff,
1570                                             bool wr_or_deserves_wr,
1571                                             bool interactive,
1572                                             bool in_burst,
1573                                             bool soft_rt)
1574{
1575        if (old_wr_coeff == 1 && wr_or_deserves_wr) {
1576                /* start a weight-raising period */
1577                if (interactive) {
1578                        bfqq->service_from_wr = 0;
1579                        bfqq->wr_coeff = bfqd->bfq_wr_coeff;
1580                        bfqq->wr_cur_max_time = bfq_wr_duration(bfqd);
1581                } else {
1582                        /*
1583                         * No interactive weight raising in progress
1584                         * here: assign minus infinity to
1585                         * wr_start_at_switch_to_srt, to make sure
1586                         * that, at the end of the soft-real-time
1587                         * weight raising periods that is starting
1588                         * now, no interactive weight-raising period
1589                         * may be wrongly considered as still in
1590                         * progress (and thus actually started by
1591                         * mistake).
1592                         */
1593                        bfqq->wr_start_at_switch_to_srt =
1594                                bfq_smallest_from_now();
1595                        bfqq->wr_coeff = bfqd->bfq_wr_coeff *
1596                                BFQ_SOFTRT_WEIGHT_FACTOR;
1597                        bfqq->wr_cur_max_time =
1598                                bfqd->bfq_wr_rt_max_time;
1599                }
1600
1601                /*
1602                 * If needed, further reduce budget to make sure it is
1603                 * close to bfqq's backlog, so as to reduce the
1604                 * scheduling-error component due to a too large
1605                 * budget. Do not care about throughput consequences,
1606                 * but only about latency. Finally, do not assign a
1607                 * too small budget either, to avoid increasing
1608                 * latency by causing too frequent expirations.
1609                 */
1610                bfqq->entity.budget = min_t(unsigned long,
1611                                            bfqq->entity.budget,
1612                                            2 * bfq_min_budget(bfqd));
1613        } else if (old_wr_coeff > 1) {
1614                if (interactive) { /* update wr coeff and duration */
1615                        bfqq->wr_coeff = bfqd->bfq_wr_coeff;
1616                        bfqq->wr_cur_max_time = bfq_wr_duration(bfqd);
1617                } else if (in_burst)
1618                        bfqq->wr_coeff = 1;
1619                else if (soft_rt) {
1620                        /*
1621                         * The application is now or still meeting the
1622                         * requirements for being deemed soft rt.  We
1623                         * can then correctly and safely (re)charge
1624                         * the weight-raising duration for the
1625                         * application with the weight-raising
1626                         * duration for soft rt applications.
1627                         *
1628                         * In particular, doing this recharge now, i.e.,
1629                         * before the weight-raising period for the
1630                         * application finishes, reduces the probability
1631                         * of the following negative scenario:
1632                         * 1) the weight of a soft rt application is
1633                         *    raised at startup (as for any newly
1634                         *    created application),
1635                         * 2) since the application is not interactive,
1636                         *    at a certain time weight-raising is
1637                         *    stopped for the application,
1638                         * 3) at that time the application happens to
1639                         *    still have pending requests, and hence
1640                         *    is destined to not have a chance to be
1641                         *    deemed soft rt before these requests are
1642                         *    completed (see the comments to the
1643                         *    function bfq_bfqq_softrt_next_start()
1644                         *    for details on soft rt detection),
1645                         * 4) these pending requests experience a high
1646                         *    latency because the application is not
1647                         *    weight-raised while they are pending.
1648                         */
1649                        if (bfqq->wr_cur_max_time !=
1650                                bfqd->bfq_wr_rt_max_time) {
1651                                bfqq->wr_start_at_switch_to_srt =
1652                                        bfqq->last_wr_start_finish;
1653
1654                                bfqq->wr_cur_max_time =
1655                                        bfqd->bfq_wr_rt_max_time;
1656                                bfqq->wr_coeff = bfqd->bfq_wr_coeff *
1657                                        BFQ_SOFTRT_WEIGHT_FACTOR;
1658                        }
1659                        bfqq->last_wr_start_finish = jiffies;
1660                }
1661        }
1662}
1663
1664static bool bfq_bfqq_idle_for_long_time(struct bfq_data *bfqd,
1665                                        struct bfq_queue *bfqq)
1666{
1667        return bfqq->dispatched == 0 &&
1668                time_is_before_jiffies(
1669                        bfqq->budget_timeout +
1670                        bfqd->bfq_wr_min_idle_time);
1671}
1672
1673
1674/*
1675 * Return true if bfqq is in a higher priority class, or has a higher
1676 * weight than the in-service queue.
1677 */
1678static bool bfq_bfqq_higher_class_or_weight(struct bfq_queue *bfqq,
1679                                            struct bfq_queue *in_serv_bfqq)
1680{
1681        int bfqq_weight, in_serv_weight;
1682
1683        if (bfqq->ioprio_class < in_serv_bfqq->ioprio_class)
1684                return true;
1685
1686        if (in_serv_bfqq->entity.parent == bfqq->entity.parent) {
1687                bfqq_weight = bfqq->entity.weight;
1688                in_serv_weight = in_serv_bfqq->entity.weight;
1689        } else {
1690                if (bfqq->entity.parent)
1691                        bfqq_weight = bfqq->entity.parent->weight;
1692                else
1693                        bfqq_weight = bfqq->entity.weight;
1694                if (in_serv_bfqq->entity.parent)
1695                        in_serv_weight = in_serv_bfqq->entity.parent->weight;
1696                else
1697                        in_serv_weight = in_serv_bfqq->entity.weight;
1698        }
1699
1700        return bfqq_weight > in_serv_weight;
1701}
1702
1703static bool bfq_better_to_idle(struct bfq_queue *bfqq);
1704
1705static void bfq_bfqq_handle_idle_busy_switch(struct bfq_data *bfqd,
1706                                             struct bfq_queue *bfqq,
1707                                             int old_wr_coeff,
1708                                             struct request *rq,
1709                                             bool *interactive)
1710{
1711        bool soft_rt, in_burst, wr_or_deserves_wr,
1712                bfqq_wants_to_preempt,
1713                idle_for_long_time = bfq_bfqq_idle_for_long_time(bfqd, bfqq),
1714                /*
1715                 * See the comments on
1716                 * bfq_bfqq_update_budg_for_activation for
1717                 * details on the usage of the next variable.
1718                 */
1719                arrived_in_time =  ktime_get_ns() <=
1720                        bfqq->ttime.last_end_request +
1721                        bfqd->bfq_slice_idle * 3;
1722
1723
1724        /*
1725         * bfqq deserves to be weight-raised if:
1726         * - it is sync,
1727         * - it does not belong to a large burst,
1728         * - it has been idle for enough time or is soft real-time,
1729         * - is linked to a bfq_io_cq (it is not shared in any sense),
1730         * - has a default weight (otherwise we assume the user wanted
1731         *   to control its weight explicitly)
1732         */
1733        in_burst = bfq_bfqq_in_large_burst(bfqq);
1734        soft_rt = bfqd->bfq_wr_max_softrt_rate > 0 &&
1735                !BFQQ_TOTALLY_SEEKY(bfqq) &&
1736                !in_burst &&
1737                time_is_before_jiffies(bfqq->soft_rt_next_start) &&
1738                bfqq->dispatched == 0 &&
1739                bfqq->entity.new_weight == 40;
1740        *interactive = !in_burst && idle_for_long_time &&
1741                bfqq->entity.new_weight == 40;
1742        /*
1743         * Merged bfq_queues are kept out of weight-raising
1744         * (low-latency) mechanisms. The reason is that these queues
1745         * are usually created for non-interactive and
1746         * non-soft-real-time tasks. Yet this is not the case for
1747         * stably-merged queues. These queues are merged just because
1748         * they are created shortly after each other. So they may
1749         * easily serve the I/O of an interactive or soft-real time
1750         * application, if the application happens to spawn multiple
1751         * processes. So let also stably-merged queued enjoy weight
1752         * raising.
1753         */
1754        wr_or_deserves_wr = bfqd->low_latency &&
1755                (bfqq->wr_coeff > 1 ||
1756                 (bfq_bfqq_sync(bfqq) &&
1757                  (bfqq->bic || RQ_BIC(rq)->stably_merged) &&
1758                   (*interactive || soft_rt)));
1759
1760        /*
1761         * Using the last flag, update budget and check whether bfqq
1762         * may want to preempt the in-service queue.
1763         */
1764        bfqq_wants_to_preempt =
1765                bfq_bfqq_update_budg_for_activation(bfqd, bfqq,
1766                                                    arrived_in_time);
1767
1768        /*
1769         * If bfqq happened to be activated in a burst, but has been
1770         * idle for much more than an interactive queue, then we
1771         * assume that, in the overall I/O initiated in the burst, the
1772         * I/O associated with bfqq is finished. So bfqq does not need
1773         * to be treated as a queue belonging to a burst
1774         * anymore. Accordingly, we reset bfqq's in_large_burst flag
1775         * if set, and remove bfqq from the burst list if it's
1776         * there. We do not decrement burst_size, because the fact
1777         * that bfqq does not need to belong to the burst list any
1778         * more does not invalidate the fact that bfqq was created in
1779         * a burst.
1780         */
1781        if (likely(!bfq_bfqq_just_created(bfqq)) &&
1782            idle_for_long_time &&
1783            time_is_before_jiffies(
1784                    bfqq->budget_timeout +
1785                    msecs_to_jiffies(10000))) {
1786                hlist_del_init(&bfqq->burst_list_node);
1787                bfq_clear_bfqq_in_large_burst(bfqq);
1788        }
1789
1790        bfq_clear_bfqq_just_created(bfqq);
1791
1792        if (bfqd->low_latency) {
1793                if (unlikely(time_is_after_jiffies(bfqq->split_time)))
1794                        /* wraparound */
1795                        bfqq->split_time =
1796                                jiffies - bfqd->bfq_wr_min_idle_time - 1;
1797
1798                if (time_is_before_jiffies(bfqq->split_time +
1799                                           bfqd->bfq_wr_min_idle_time)) {
1800                        bfq_update_bfqq_wr_on_rq_arrival(bfqd, bfqq,
1801                                                         old_wr_coeff,
1802                                                         wr_or_deserves_wr,
1803                                                         *interactive,
1804                                                         in_burst,
1805                                                         soft_rt);
1806
1807                        if (old_wr_coeff != bfqq->wr_coeff)
1808                                bfqq->entity.prio_changed = 1;
1809                }
1810        }
1811
1812        bfqq->last_idle_bklogged = jiffies;
1813        bfqq->service_from_backlogged = 0;
1814        bfq_clear_bfqq_softrt_update(bfqq);
1815
1816        bfq_add_bfqq_busy(bfqd, bfqq);
1817
1818        /*
1819         * Expire in-service queue if preemption may be needed for
1820         * guarantees or throughput. As for guarantees, we care
1821         * explicitly about two cases. The first is that bfqq has to
1822         * recover a service hole, as explained in the comments on
1823         * bfq_bfqq_update_budg_for_activation(), i.e., that
1824         * bfqq_wants_to_preempt is true. However, if bfqq does not
1825         * carry time-critical I/O, then bfqq's bandwidth is less
1826         * important than that of queues that carry time-critical I/O.
1827         * So, as a further constraint, we consider this case only if
1828         * bfqq is at least as weight-raised, i.e., at least as time
1829         * critical, as the in-service queue.
1830         *
1831         * The second case is that bfqq is in a higher priority class,
1832         * or has a higher weight than the in-service queue. If this
1833         * condition does not hold, we don't care because, even if
1834         * bfqq does not start to be served immediately, the resulting
1835         * delay for bfqq's I/O is however lower or much lower than
1836         * the ideal completion time to be guaranteed to bfqq's I/O.
1837         *
1838         * In both cases, preemption is needed only if, according to
1839         * the timestamps of both bfqq and of the in-service queue,
1840         * bfqq actually is the next queue to serve. So, to reduce
1841         * useless preemptions, the return value of
1842         * next_queue_may_preempt() is considered in the next compound
1843         * condition too. Yet next_queue_may_preempt() just checks a
1844         * simple, necessary condition for bfqq to be the next queue
1845         * to serve. In fact, to evaluate a sufficient condition, the
1846         * timestamps of the in-service queue would need to be
1847         * updated, and this operation is quite costly (see the
1848         * comments on bfq_bfqq_update_budg_for_activation()).
1849         *
1850         * As for throughput, we ask bfq_better_to_idle() whether we
1851         * still need to plug I/O dispatching. If bfq_better_to_idle()
1852         * says no, then plugging is not needed any longer, either to
1853         * boost throughput or to perserve service guarantees. Then
1854         * the best option is to stop plugging I/O, as not doing so
1855         * would certainly lower throughput. We may end up in this
1856         * case if: (1) upon a dispatch attempt, we detected that it
1857         * was better to plug I/O dispatch, and to wait for a new
1858         * request to arrive for the currently in-service queue, but
1859         * (2) this switch of bfqq to busy changes the scenario.
1860         */
1861        if (bfqd->in_service_queue &&
1862            ((bfqq_wants_to_preempt &&
1863              bfqq->wr_coeff >= bfqd->in_service_queue->wr_coeff) ||
1864             bfq_bfqq_higher_class_or_weight(bfqq, bfqd->in_service_queue) ||
1865             !bfq_better_to_idle(bfqd->in_service_queue)) &&
1866            next_queue_may_preempt(bfqd))
1867                bfq_bfqq_expire(bfqd, bfqd->in_service_queue,
1868                                false, BFQQE_PREEMPTED);
1869}
1870
1871static void bfq_reset_inject_limit(struct bfq_data *bfqd,
1872                                   struct bfq_queue *bfqq)
1873{
1874        /* invalidate baseline total service time */
1875        bfqq->last_serv_time_ns = 0;
1876
1877        /*
1878         * Reset pointer in case we are waiting for
1879         * some request completion.
1880         */
1881        bfqd->waited_rq = NULL;
1882
1883        /*
1884         * If bfqq has a short think time, then start by setting the
1885         * inject limit to 0 prudentially, because the service time of
1886         * an injected I/O request may be higher than the think time
1887         * of bfqq, and therefore, if one request was injected when
1888         * bfqq remains empty, this injected request might delay the
1889         * service of the next I/O request for bfqq significantly. In
1890         * case bfqq can actually tolerate some injection, then the
1891         * adaptive update will however raise the limit soon. This
1892         * lucky circumstance holds exactly because bfqq has a short
1893         * think time, and thus, after remaining empty, is likely to
1894         * get new I/O enqueued---and then completed---before being
1895         * expired. This is the very pattern that gives the
1896         * limit-update algorithm the chance to measure the effect of
1897         * injection on request service times, and then to update the
1898         * limit accordingly.
1899         *
1900         * However, in the following special case, the inject limit is
1901         * left to 1 even if the think time is short: bfqq's I/O is
1902         * synchronized with that of some other queue, i.e., bfqq may
1903         * receive new I/O only after the I/O of the other queue is
1904         * completed. Keeping the inject limit to 1 allows the
1905         * blocking I/O to be served while bfqq is in service. And
1906         * this is very convenient both for bfqq and for overall
1907         * throughput, as explained in detail in the comments in
1908         * bfq_update_has_short_ttime().
1909         *
1910         * On the opposite end, if bfqq has a long think time, then
1911         * start directly by 1, because:
1912         * a) on the bright side, keeping at most one request in
1913         * service in the drive is unlikely to cause any harm to the
1914         * latency of bfqq's requests, as the service time of a single
1915         * request is likely to be lower than the think time of bfqq;
1916         * b) on the downside, after becoming empty, bfqq is likely to
1917         * expire before getting its next request. With this request
1918         * arrival pattern, it is very hard to sample total service
1919         * times and update the inject limit accordingly (see comments
1920         * on bfq_update_inject_limit()). So the limit is likely to be
1921         * never, or at least seldom, updated.  As a consequence, by
1922         * setting the limit to 1, we avoid that no injection ever
1923         * occurs with bfqq. On the downside, this proactive step
1924         * further reduces chances to actually compute the baseline
1925         * total service time. Thus it reduces chances to execute the
1926         * limit-update algorithm and possibly raise the limit to more
1927         * than 1.
1928         */
1929        if (bfq_bfqq_has_short_ttime(bfqq))
1930                bfqq->inject_limit = 0;
1931        else
1932                bfqq->inject_limit = 1;
1933
1934        bfqq->decrease_time_jif = jiffies;
1935}
1936
1937static void bfq_update_io_intensity(struct bfq_queue *bfqq, u64 now_ns)
1938{
1939        u64 tot_io_time = now_ns - bfqq->io_start_time;
1940
1941        if (RB_EMPTY_ROOT(&bfqq->sort_list) && bfqq->dispatched == 0)
1942                bfqq->tot_idle_time +=
1943                        now_ns - bfqq->ttime.last_end_request;
1944
1945        if (unlikely(bfq_bfqq_just_created(bfqq)))
1946                return;
1947
1948        /*
1949         * Must be busy for at least about 80% of the time to be
1950         * considered I/O bound.
1951         */
1952        if (bfqq->tot_idle_time * 5 > tot_io_time)
1953                bfq_clear_bfqq_IO_bound(bfqq);
1954        else
1955                bfq_mark_bfqq_IO_bound(bfqq);
1956
1957        /*
1958         * Keep an observation window of at most 200 ms in the past
1959         * from now.
1960         */
1961        if (tot_io_time > 200 * NSEC_PER_MSEC) {
1962                bfqq->io_start_time = now_ns - (tot_io_time>>1);
1963                bfqq->tot_idle_time >>= 1;
1964        }
1965}
1966
1967/*
1968 * Detect whether bfqq's I/O seems synchronized with that of some
1969 * other queue, i.e., whether bfqq, after remaining empty, happens to
1970 * receive new I/O only right after some I/O request of the other
1971 * queue has been completed. We call waker queue the other queue, and
1972 * we assume, for simplicity, that bfqq may have at most one waker
1973 * queue.
1974 *
1975 * A remarkable throughput boost can be reached by unconditionally
1976 * injecting the I/O of the waker queue, every time a new
1977 * bfq_dispatch_request happens to be invoked while I/O is being
1978 * plugged for bfqq.  In addition to boosting throughput, this
1979 * unblocks bfqq's I/O, thereby improving bandwidth and latency for
1980 * bfqq. Note that these same results may be achieved with the general
1981 * injection mechanism, but less effectively. For details on this
1982 * aspect, see the comments on the choice of the queue for injection
1983 * in bfq_select_queue().
1984 *
1985 * Turning back to the detection of a waker queue, a queue Q is deemed
1986 * as a waker queue for bfqq if, for three consecutive times, bfqq
1987 * happens to become non empty right after a request of Q has been
1988 * completed. In this respect, even if bfqq is empty, we do not check
1989 * for a waker if it still has some in-flight I/O. In fact, in this
1990 * case bfqq is actually still being served by the drive, and may
1991 * receive new I/O on the completion of some of the in-flight
1992 * requests. In particular, on the first time, Q is tentatively set as
1993 * a candidate waker queue, while on the third consecutive time that Q
1994 * is detected, the field waker_bfqq is set to Q, to confirm that Q is
1995 * a waker queue for bfqq. These detection steps are performed only if
1996 * bfqq has a long think time, so as to make it more likely that
1997 * bfqq's I/O is actually being blocked by a synchronization. This
1998 * last filter, plus the above three-times requirement, make false
1999 * positives less likely.
2000 *
2001 * NOTE
2002 *
2003 * The sooner a waker queue is detected, the sooner throughput can be
2004 * boosted by injecting I/O from the waker queue. Fortunately,
2005 * detection is likely to be actually fast, for the following
2006 * reasons. While blocked by synchronization, bfqq has a long think
2007 * time. This implies that bfqq's inject limit is at least equal to 1
2008 * (see the comments in bfq_update_inject_limit()). So, thanks to
2009 * injection, the waker queue is likely to be served during the very
2010 * first I/O-plugging time interval for bfqq. This triggers the first
2011 * step of the detection mechanism. Thanks again to injection, the
2012 * candidate waker queue is then likely to be confirmed no later than
2013 * during the next I/O-plugging interval for bfqq.
2014 *
2015 * ISSUE
2016 *
2017 * On queue merging all waker information is lost.
2018 */
2019static void bfq_check_waker(struct bfq_data *bfqd, struct bfq_queue *bfqq,
2020                            u64 now_ns)
2021{
2022        if (!bfqd->last_completed_rq_bfqq ||
2023            bfqd->last_completed_rq_bfqq == bfqq ||
2024            bfq_bfqq_has_short_ttime(bfqq) ||
2025            bfqq->dispatched > 0 ||
2026            now_ns - bfqd->last_completion >= 4 * NSEC_PER_MSEC ||
2027            bfqd->last_completed_rq_bfqq == bfqq->waker_bfqq)
2028                return;
2029
2030        if (bfqd->last_completed_rq_bfqq !=
2031            bfqq->tentative_waker_bfqq) {
2032                /*
2033                 * First synchronization detected with a
2034                 * candidate waker queue, or with a different
2035                 * candidate waker queue from the current one.
2036                 */
2037                bfqq->tentative_waker_bfqq =
2038                        bfqd->last_completed_rq_bfqq;
2039                bfqq->num_waker_detections = 1;
2040        } else /* Same tentative waker queue detected again */
2041                bfqq->num_waker_detections++;
2042
2043        if (bfqq->num_waker_detections == 3) {
2044                bfqq->waker_bfqq = bfqd->last_completed_rq_bfqq;
2045                bfqq->tentative_waker_bfqq = NULL;
2046
2047                /*
2048                 * If the waker queue disappears, then
2049                 * bfqq->waker_bfqq must be reset. To
2050                 * this goal, we maintain in each
2051                 * waker queue a list, woken_list, of
2052                 * all the queues that reference the
2053                 * waker queue through their
2054                 * waker_bfqq pointer. When the waker
2055                 * queue exits, the waker_bfqq pointer
2056                 * of all the queues in the woken_list
2057                 * is reset.
2058                 *
2059                 * In addition, if bfqq is already in
2060                 * the woken_list of a waker queue,
2061                 * then, before being inserted into
2062                 * the woken_list of a new waker
2063                 * queue, bfqq must be removed from
2064                 * the woken_list of the old waker
2065                 * queue.
2066                 */
2067                if (!hlist_unhashed(&bfqq->woken_list_node))
2068                        hlist_del_init(&bfqq->woken_list_node);
2069                hlist_add_head(&bfqq->woken_list_node,
2070                               &bfqd->last_completed_rq_bfqq->woken_list);
2071        }
2072}
2073
2074static void bfq_add_request(struct request *rq)
2075{
2076        struct bfq_queue *bfqq = RQ_BFQQ(rq);
2077        struct bfq_data *bfqd = bfqq->bfqd;
2078        struct request *next_rq, *prev;
2079        unsigned int old_wr_coeff = bfqq->wr_coeff;
2080        bool interactive = false;
2081        u64 now_ns = ktime_get_ns();
2082
2083        bfq_log_bfqq(bfqd, bfqq, "add_request %d", rq_is_sync(rq));
2084        bfqq->queued[rq_is_sync(rq)]++;
2085        bfqd->queued++;
2086
2087        if (RB_EMPTY_ROOT(&bfqq->sort_list) && bfq_bfqq_sync(bfqq)) {
2088                bfq_check_waker(bfqd, bfqq, now_ns);
2089
2090                /*
2091                 * Periodically reset inject limit, to make sure that
2092                 * the latter eventually drops in case workload
2093                 * changes, see step (3) in the comments on
2094                 * bfq_update_inject_limit().
2095                 */
2096                if (time_is_before_eq_jiffies(bfqq->decrease_time_jif +
2097                                             msecs_to_jiffies(1000)))
2098                        bfq_reset_inject_limit(bfqd, bfqq);
2099
2100                /*
2101                 * The following conditions must hold to setup a new
2102                 * sampling of total service time, and then a new
2103                 * update of the inject limit:
2104                 * - bfqq is in service, because the total service
2105                 *   time is evaluated only for the I/O requests of
2106                 *   the queues in service;
2107                 * - this is the right occasion to compute or to
2108                 *   lower the baseline total service time, because
2109                 *   there are actually no requests in the drive,
2110                 *   or
2111                 *   the baseline total service time is available, and
2112                 *   this is the right occasion to compute the other
2113                 *   quantity needed to update the inject limit, i.e.,
2114                 *   the total service time caused by the amount of
2115                 *   injection allowed by the current value of the
2116                 *   limit. It is the right occasion because injection
2117                 *   has actually been performed during the service
2118                 *   hole, and there are still in-flight requests,
2119                 *   which are very likely to be exactly the injected
2120                 *   requests, or part of them;
2121                 * - the minimum interval for sampling the total
2122                 *   service time and updating the inject limit has
2123                 *   elapsed.
2124                 */
2125                if (bfqq == bfqd->in_service_queue &&
2126                    (bfqd->rq_in_driver == 0 ||
2127                     (bfqq->last_serv_time_ns > 0 &&
2128                      bfqd->rqs_injected && bfqd->rq_in_driver > 0)) &&
2129                    time_is_before_eq_jiffies(bfqq->decrease_time_jif +
2130                                              msecs_to_jiffies(10))) {
2131                        bfqd->last_empty_occupied_ns = ktime_get_ns();
2132                        /*
2133                         * Start the state machine for measuring the
2134                         * total service time of rq: setting
2135                         * wait_dispatch will cause bfqd->waited_rq to
2136                         * be set when rq will be dispatched.
2137                         */
2138                        bfqd->wait_dispatch = true;
2139                        /*
2140                         * If there is no I/O in service in the drive,
2141                         * then possible injection occurred before the
2142                         * arrival of rq will not affect the total
2143                         * service time of rq. So the injection limit
2144                         * must not be updated as a function of such
2145                         * total service time, unless new injection
2146                         * occurs before rq is completed. To have the
2147                         * injection limit updated only in the latter
2148                         * case, reset rqs_injected here (rqs_injected
2149                         * will be set in case injection is performed
2150                         * on bfqq before rq is completed).
2151                         */
2152                        if (bfqd->rq_in_driver == 0)
2153                                bfqd->rqs_injected = false;
2154                }
2155        }
2156
2157        if (bfq_bfqq_sync(bfqq))
2158                bfq_update_io_intensity(bfqq, now_ns);
2159
2160        elv_rb_add(&bfqq->sort_list, rq);
2161
2162        /*
2163         * Check if this request is a better next-serve candidate.
2164         */
2165        prev = bfqq->next_rq;
2166        next_rq = bfq_choose_req(bfqd, bfqq->next_rq, rq, bfqd->last_position);
2167        bfqq->next_rq = next_rq;
2168
2169        /*
2170         * Adjust priority tree position, if next_rq changes.
2171         * See comments on bfq_pos_tree_add_move() for the unlikely().
2172         */
2173        if (unlikely(!bfqd->nonrot_with_queueing && prev != bfqq->next_rq))
2174                bfq_pos_tree_add_move(bfqd, bfqq);
2175
2176        if (!bfq_bfqq_busy(bfqq)) /* switching to busy ... */
2177                bfq_bfqq_handle_idle_busy_switch(bfqd, bfqq, old_wr_coeff,
2178                                                 rq, &interactive);
2179        else {
2180                if (bfqd->low_latency && old_wr_coeff == 1 && !rq_is_sync(rq) &&
2181                    time_is_before_jiffies(
2182                                bfqq->last_wr_start_finish +
2183                                bfqd->bfq_wr_min_inter_arr_async)) {
2184                        bfqq->wr_coeff = bfqd->bfq_wr_coeff;
2185                        bfqq->wr_cur_max_time = bfq_wr_duration(bfqd);
2186
2187                        bfqd->wr_busy_queues++;
2188                        bfqq->entity.prio_changed = 1;
2189                }
2190                if (prev != bfqq->next_rq)
2191                        bfq_updated_next_req(bfqd, bfqq);
2192        }
2193
2194        /*
2195         * Assign jiffies to last_wr_start_finish in the following
2196         * cases:
2197         *
2198         * . if bfqq is not going to be weight-raised, because, for
2199         *   non weight-raised queues, last_wr_start_finish stores the
2200         *   arrival time of the last request; as of now, this piece
2201         *   of information is used only for deciding whether to
2202         *   weight-raise async queues
2203         *
2204         * . if bfqq is not weight-raised, because, if bfqq is now
2205         *   switching to weight-raised, then last_wr_start_finish
2206         *   stores the time when weight-raising starts
2207         *
2208         * . if bfqq is interactive, because, regardless of whether
2209         *   bfqq is currently weight-raised, the weight-raising
2210         *   period must start or restart (this case is considered
2211         *   separately because it is not detected by the above
2212         *   conditions, if bfqq is already weight-raised)
2213         *
2214         * last_wr_start_finish has to be updated also if bfqq is soft
2215         * real-time, because the weight-raising period is constantly
2216         * restarted on idle-to-busy transitions for these queues, but
2217         * this is already done in bfq_bfqq_handle_idle_busy_switch if
2218         * needed.
2219         */
2220        if (bfqd->low_latency &&
2221                (old_wr_coeff == 1 || bfqq->wr_coeff == 1 || interactive))
2222                bfqq->last_wr_start_finish = jiffies;
2223}
2224
2225static struct request *bfq_find_rq_fmerge(struct bfq_data *bfqd,
2226                                          struct bio *bio,
2227                                          struct request_queue *q)
2228{
2229        struct bfq_queue *bfqq = bfqd->bio_bfqq;
2230
2231
2232        if (bfqq)
2233                return elv_rb_find(&bfqq->sort_list, bio_end_sector(bio));
2234
2235        return NULL;
2236}
2237
2238static sector_t get_sdist(sector_t last_pos, struct request *rq)
2239{
2240        if (last_pos)
2241                return abs(blk_rq_pos(rq) - last_pos);
2242
2243        return 0;
2244}
2245
2246#if 0 /* Still not clear if we can do without next two functions */
2247static void bfq_activate_request(struct request_queue *q, struct request *rq)
2248{
2249        struct bfq_data *bfqd = q->elevator->elevator_data;
2250
2251        bfqd->rq_in_driver++;
2252}
2253
2254static void bfq_deactivate_request(struct request_queue *q, struct request *rq)
2255{
2256        struct bfq_data *bfqd = q->elevator->elevator_data;
2257
2258        bfqd->rq_in_driver--;
2259}
2260#endif
2261
2262static void bfq_remove_request(struct request_queue *q,
2263                               struct request *rq)
2264{
2265        struct bfq_queue *bfqq = RQ_BFQQ(rq);
2266        struct bfq_data *bfqd = bfqq->bfqd;
2267        const int sync = rq_is_sync(rq);
2268
2269        if (bfqq->next_rq == rq) {
2270                bfqq->next_rq = bfq_find_next_rq(bfqd, bfqq, rq);
2271                bfq_updated_next_req(bfqd, bfqq);
2272        }
2273
2274        if (rq->queuelist.prev != &rq->queuelist)
2275                list_del_init(&rq->queuelist);
2276        bfqq->queued[sync]--;
2277        bfqd->queued--;
2278        elv_rb_del(&bfqq->sort_list, rq);
2279
2280        elv_rqhash_del(q, rq);
2281        if (q->last_merge == rq)
2282                q->last_merge = NULL;
2283
2284        if (RB_EMPTY_ROOT(&bfqq->sort_list)) {
2285                bfqq->next_rq = NULL;
2286
2287                if (bfq_bfqq_busy(bfqq) && bfqq != bfqd->in_service_queue) {
2288                        bfq_del_bfqq_busy(bfqd, bfqq, false);
2289                        /*
2290                         * bfqq emptied. In normal operation, when
2291                         * bfqq is empty, bfqq->entity.service and
2292                         * bfqq->entity.budget must contain,
2293                         * respectively, the service received and the
2294                         * budget used last time bfqq emptied. These
2295                         * facts do not hold in this case, as at least
2296                         * this last removal occurred while bfqq is
2297                         * not in service. To avoid inconsistencies,
2298                         * reset both bfqq->entity.service and
2299                         * bfqq->entity.budget, if bfqq has still a
2300                         * process that may issue I/O requests to it.
2301                         */
2302                        bfqq->entity.budget = bfqq->entity.service = 0;
2303                }
2304
2305                /*
2306                 * Remove queue from request-position tree as it is empty.
2307                 */
2308                if (bfqq->pos_root) {
2309                        rb_erase(&bfqq->pos_node, bfqq->pos_root);
2310                        bfqq->pos_root = NULL;
2311                }
2312        } else {
2313                /* see comments on bfq_pos_tree_add_move() for the unlikely() */
2314                if (unlikely(!bfqd->nonrot_with_queueing))
2315                        bfq_pos_tree_add_move(bfqd, bfqq);
2316        }
2317
2318        if (rq->cmd_flags & REQ_META)
2319                bfqq->meta_pending--;
2320
2321}
2322
2323static bool bfq_bio_merge(struct request_queue *q, struct bio *bio,
2324                unsigned int nr_segs)
2325{
2326        struct bfq_data *bfqd = q->elevator->elevator_data;
2327        struct request *free = NULL;
2328        /*
2329         * bfq_bic_lookup grabs the queue_lock: invoke it now and
2330         * store its return value for later use, to avoid nesting
2331         * queue_lock inside the bfqd->lock. We assume that the bic
2332         * returned by bfq_bic_lookup does not go away before
2333         * bfqd->lock is taken.
2334         */
2335        struct bfq_io_cq *bic = bfq_bic_lookup(bfqd, current->io_context, q);
2336        bool ret;
2337
2338        spin_lock_irq(&bfqd->lock);
2339
2340        if (bic)
2341                bfqd->bio_bfqq = bic_to_bfqq(bic, op_is_sync(bio->bi_opf));
2342        else
2343                bfqd->bio_bfqq = NULL;
2344        bfqd->bio_bic = bic;
2345
2346        ret = blk_mq_sched_try_merge(q, bio, nr_segs, &free);
2347
2348        spin_unlock_irq(&bfqd->lock);
2349        if (free)
2350                blk_mq_free_request(free);
2351
2352        return ret;
2353}
2354
2355static int bfq_request_merge(struct request_queue *q, struct request **req,
2356                             struct bio *bio)
2357{
2358        struct bfq_data *bfqd = q->elevator->elevator_data;
2359        struct request *__rq;
2360
2361        __rq = bfq_find_rq_fmerge(bfqd, bio, q);
2362        if (__rq && elv_bio_merge_ok(__rq, bio)) {
2363                *req = __rq;
2364                return ELEVATOR_FRONT_MERGE;
2365        }
2366
2367        return ELEVATOR_NO_MERGE;
2368}
2369
2370static struct bfq_queue *bfq_init_rq(struct request *rq);
2371
2372static void bfq_request_merged(struct request_queue *q, struct request *req,
2373                               enum elv_merge type)
2374{
2375        if (type == ELEVATOR_FRONT_MERGE &&
2376            rb_prev(&req->rb_node) &&
2377            blk_rq_pos(req) <
2378            blk_rq_pos(container_of(rb_prev(&req->rb_node),
2379                                    struct request, rb_node))) {
2380                struct bfq_queue *bfqq = bfq_init_rq(req);
2381                struct bfq_data *bfqd;
2382                struct request *prev, *next_rq;
2383
2384                if (!bfqq)
2385                        return;
2386
2387                bfqd = bfqq->bfqd;
2388
2389                /* Reposition request in its sort_list */
2390                elv_rb_del(&bfqq->sort_list, req);
2391                elv_rb_add(&bfqq->sort_list, req);
2392
2393                /* Choose next request to be served for bfqq */
2394                prev = bfqq->next_rq;
2395                next_rq = bfq_choose_req(bfqd, bfqq->next_rq, req,
2396                                         bfqd->last_position);
2397                bfqq->next_rq = next_rq;
2398                /*
2399                 * If next_rq changes, update both the queue's budget to
2400                 * fit the new request and the queue's position in its
2401                 * rq_pos_tree.
2402                 */
2403                if (prev != bfqq->next_rq) {
2404                        bfq_updated_next_req(bfqd, bfqq);
2405                        /*
2406                         * See comments on bfq_pos_tree_add_move() for
2407                         * the unlikely().
2408                         */
2409                        if (unlikely(!bfqd->nonrot_with_queueing))
2410                                bfq_pos_tree_add_move(bfqd, bfqq);
2411                }
2412        }
2413}
2414
2415/*
2416 * This function is called to notify the scheduler that the requests
2417 * rq and 'next' have been merged, with 'next' going away.  BFQ
2418 * exploits this hook to address the following issue: if 'next' has a
2419 * fifo_time lower that rq, then the fifo_time of rq must be set to
2420 * the value of 'next', to not forget the greater age of 'next'.
2421 *
2422 * NOTE: in this function we assume that rq is in a bfq_queue, basing
2423 * on that rq is picked from the hash table q->elevator->hash, which,
2424 * in its turn, is filled only with I/O requests present in
2425 * bfq_queues, while BFQ is in use for the request queue q. In fact,
2426 * the function that fills this hash table (elv_rqhash_add) is called
2427 * only by bfq_insert_request.
2428 */
2429static void bfq_requests_merged(struct request_queue *q, struct request *rq,
2430                                struct request *next)
2431{
2432        struct bfq_queue *bfqq = bfq_init_rq(rq),
2433                *next_bfqq = bfq_init_rq(next);
2434
2435        if (!bfqq)
2436                goto remove;
2437
2438        /*
2439         * If next and rq belong to the same bfq_queue and next is older
2440         * than rq, then reposition rq in the fifo (by substituting next
2441         * with rq). Otherwise, if next and rq belong to different
2442         * bfq_queues, never reposition rq: in fact, we would have to
2443         * reposition it with respect to next's position in its own fifo,
2444         * which would most certainly be too expensive with respect to
2445         * the benefits.
2446         */
2447        if (bfqq == next_bfqq &&
2448            !list_empty(&rq->queuelist) && !list_empty(&next->queuelist) &&
2449            next->fifo_time < rq->fifo_time) {
2450                list_del_init(&rq->queuelist);
2451                list_replace_init(&next->queuelist, &rq->queuelist);
2452                rq->fifo_time = next->fifo_time;
2453        }
2454
2455        if (bfqq->next_rq == next)
2456                bfqq->next_rq = rq;
2457
2458        bfqg_stats_update_io_merged(bfqq_group(bfqq), next->cmd_flags);
2459remove:
2460        /* Merged request may be in the IO scheduler. Remove it. */
2461        if (!RB_EMPTY_NODE(&next->rb_node)) {
2462                bfq_remove_request(next->q, next);
2463                if (next_bfqq)
2464                        bfqg_stats_update_io_remove(bfqq_group(next_bfqq),
2465                                                    next->cmd_flags);
2466        }
2467}
2468
2469/* Must be called with bfqq != NULL */
2470static void bfq_bfqq_end_wr(struct bfq_queue *bfqq)
2471{
2472        /*
2473         * If bfqq has been enjoying interactive weight-raising, then
2474         * reset soft_rt_next_start. We do it for the following
2475         * reason. bfqq may have been conveying the I/O needed to load
2476         * a soft real-time application. Such an application actually
2477         * exhibits a soft real-time I/O pattern after it finishes
2478         * loading, and finally starts doing its job. But, if bfqq has
2479         * been receiving a lot of bandwidth so far (likely to happen
2480         * on a fast device), then soft_rt_next_start now contains a
2481         * high value that. So, without this reset, bfqq would be
2482         * prevented from being possibly considered as soft_rt for a
2483         * very long time.
2484         */
2485
2486        if (bfqq->wr_cur_max_time !=
2487            bfqq->bfqd->bfq_wr_rt_max_time)
2488                bfqq->soft_rt_next_start = jiffies;
2489
2490        if (bfq_bfqq_busy(bfqq))
2491                bfqq->bfqd->wr_busy_queues--;
2492        bfqq->wr_coeff = 1;
2493        bfqq->wr_cur_max_time = 0;
2494        bfqq->last_wr_start_finish = jiffies;
2495        /*
2496         * Trigger a weight change on the next invocation of
2497         * __bfq_entity_update_weight_prio.
2498         */
2499        bfqq->entity.prio_changed = 1;
2500}
2501
2502void bfq_end_wr_async_queues(struct bfq_data *bfqd,
2503                             struct bfq_group *bfqg)
2504{
2505        int i, j;
2506
2507        for (i = 0; i < 2; i++)
2508                for (j = 0; j < IOPRIO_BE_NR; j++)
2509                        if (bfqg->async_bfqq[i][j])
2510                                bfq_bfqq_end_wr(bfqg->async_bfqq[i][j]);
2511        if (bfqg->async_idle_bfqq)
2512                bfq_bfqq_end_wr(bfqg->async_idle_bfqq);
2513}
2514
2515static void bfq_end_wr(struct bfq_data *bfqd)
2516{
2517        struct bfq_queue *bfqq;
2518
2519        spin_lock_irq(&bfqd->lock);
2520
2521        list_for_each_entry(bfqq, &bfqd->active_list, bfqq_list)
2522                bfq_bfqq_end_wr(bfqq);
2523        list_for_each_entry(bfqq, &bfqd->idle_list, bfqq_list)
2524                bfq_bfqq_end_wr(bfqq);
2525        bfq_end_wr_async(bfqd);
2526
2527        spin_unlock_irq(&bfqd->lock);
2528}
2529
2530static sector_t bfq_io_struct_pos(void *io_struct, bool request)
2531{
2532        if (request)
2533                return blk_rq_pos(io_struct);
2534        else
2535                return ((struct bio *)io_struct)->bi_iter.bi_sector;
2536}
2537
2538static int bfq_rq_close_to_sector(void *io_struct, bool request,
2539                                  sector_t sector)
2540{
2541        return abs(bfq_io_struct_pos(io_struct, request) - sector) <=
2542               BFQQ_CLOSE_THR;
2543}
2544
2545static struct bfq_queue *bfqq_find_close(struct bfq_data *bfqd,
2546                                         struct bfq_queue *bfqq,
2547                                         sector_t sector)
2548{
2549        struct rb_root *root = &bfq_bfqq_to_bfqg(bfqq)->rq_pos_tree;
2550        struct rb_node *parent, *node;
2551        struct bfq_queue *__bfqq;
2552
2553        if (RB_EMPTY_ROOT(root))
2554                return NULL;
2555
2556        /*
2557         * First, if we find a request starting at the end of the last
2558         * request, choose it.
2559         */
2560        __bfqq = bfq_rq_pos_tree_lookup(bfqd, root, sector, &parent, NULL);
2561        if (__bfqq)
2562                return __bfqq;
2563
2564        /*
2565         * If the exact sector wasn't found, the parent of the NULL leaf
2566         * will contain the closest sector (rq_pos_tree sorted by
2567         * next_request position).
2568         */
2569        __bfqq = rb_entry(parent, struct bfq_queue, pos_node);
2570        if (bfq_rq_close_to_sector(__bfqq->next_rq, true, sector))
2571                return __bfqq;
2572
2573        if (blk_rq_pos(__bfqq->next_rq) < sector)
2574                node = rb_next(&__bfqq->pos_node);
2575        else
2576                node = rb_prev(&__bfqq->pos_node);
2577        if (!node)
2578                return NULL;
2579
2580        __bfqq = rb_entry(node, struct bfq_queue, pos_node);
2581        if (bfq_rq_close_to_sector(__bfqq->next_rq, true, sector))
2582                return __bfqq;
2583
2584        return NULL;
2585}
2586
2587static struct bfq_queue *bfq_find_close_cooperator(struct bfq_data *bfqd,
2588                                                   struct bfq_queue *cur_bfqq,
2589                                                   sector_t sector)
2590{
2591        struct bfq_queue *bfqq;
2592
2593        /*
2594         * We shall notice if some of the queues are cooperating,
2595         * e.g., working closely on the same area of the device. In
2596         * that case, we can group them together and: 1) don't waste
2597         * time idling, and 2) serve the union of their requests in
2598         * the best possible order for throughput.
2599         */
2600        bfqq = bfqq_find_close(bfqd, cur_bfqq, sector);
2601        if (!bfqq || bfqq == cur_bfqq)
2602                return NULL;
2603
2604        return bfqq;
2605}
2606
2607static struct bfq_queue *
2608bfq_setup_merge(struct bfq_queue *bfqq, struct bfq_queue *new_bfqq)
2609{
2610        int process_refs, new_process_refs;
2611        struct bfq_queue *__bfqq;
2612
2613        /*
2614         * If there are no process references on the new_bfqq, then it is
2615         * unsafe to follow the ->new_bfqq chain as other bfqq's in the chain
2616         * may have dropped their last reference (not just their last process
2617         * reference).
2618         */
2619        if (!bfqq_process_refs(new_bfqq))
2620                return NULL;
2621
2622        /* Avoid a circular list and skip interim queue merges. */
2623        while ((__bfqq = new_bfqq->new_bfqq)) {
2624                if (__bfqq == bfqq)
2625                        return NULL;
2626                new_bfqq = __bfqq;
2627        }
2628
2629        process_refs = bfqq_process_refs(bfqq);
2630        new_process_refs = bfqq_process_refs(new_bfqq);
2631        /*
2632         * If the process for the bfqq has gone away, there is no
2633         * sense in merging the queues.
2634         */
2635        if (process_refs == 0 || new_process_refs == 0)
2636                return NULL;
2637
2638        bfq_log_bfqq(bfqq->bfqd, bfqq, "scheduling merge with queue %d",
2639                new_bfqq->pid);
2640
2641        /*
2642         * Merging is just a redirection: the requests of the process
2643         * owning one of the two queues are redirected to the other queue.
2644         * The latter queue, in its turn, is set as shared if this is the
2645         * first time that the requests of some process are redirected to
2646         * it.
2647         *
2648         * We redirect bfqq to new_bfqq and not the opposite, because
2649         * we are in the context of the process owning bfqq, thus we
2650         * have the io_cq of this process. So we can immediately
2651         * configure this io_cq to redirect the requests of the
2652         * process to new_bfqq. In contrast, the io_cq of new_bfqq is
2653         * not available any more (new_bfqq->bic == NULL).
2654         *
2655         * Anyway, even in case new_bfqq coincides with the in-service
2656         * queue, redirecting requests the in-service queue is the
2657         * best option, as we feed the in-service queue with new
2658         * requests close to the last request served and, by doing so,
2659         * are likely to increase the throughput.
2660         */
2661        bfqq->new_bfqq = new_bfqq;
2662        new_bfqq->ref += process_refs;
2663        return new_bfqq;
2664}
2665
2666static bool bfq_may_be_close_cooperator(struct bfq_queue *bfqq,
2667                                        struct bfq_queue *new_bfqq)
2668{
2669        if (bfq_too_late_for_merging(new_bfqq))
2670                return false;
2671
2672        if (bfq_class_idle(bfqq) || bfq_class_idle(new_bfqq) ||
2673            (bfqq->ioprio_class != new_bfqq->ioprio_class))
2674                return false;
2675
2676        /*
2677         * If either of the queues has already been detected as seeky,
2678         * then merging it with the other queue is unlikely to lead to
2679         * sequential I/O.
2680         */
2681        if (BFQQ_SEEKY(bfqq) || BFQQ_SEEKY(new_bfqq))
2682                return false;
2683
2684        /*
2685         * Interleaved I/O is known to be done by (some) applications
2686         * only for reads, so it does not make sense to merge async
2687         * queues.
2688         */
2689        if (!bfq_bfqq_sync(bfqq) || !bfq_bfqq_sync(new_bfqq))
2690                return false;
2691
2692        return true;
2693}
2694
2695static bool idling_boosts_thr_without_issues(struct bfq_data *bfqd,
2696                                             struct bfq_queue *bfqq);
2697
2698/*
2699 * Attempt to schedule a merge of bfqq with the currently in-service
2700 * queue or with a close queue among the scheduled queues.  Return
2701 * NULL if no merge was scheduled, a pointer to the shared bfq_queue
2702 * structure otherwise.
2703 *
2704 * The OOM queue is not allowed to participate to cooperation: in fact, since
2705 * the requests temporarily redirected to the OOM queue could be redirected
2706 * again to dedicated queues at any time, the state needed to correctly
2707 * handle merging with the OOM queue would be quite complex and expensive
2708 * to maintain. Besides, in such a critical condition as an out of memory,
2709 * the benefits of queue merging may be little relevant, or even negligible.
2710 *
2711 * WARNING: queue merging may impair fairness among non-weight raised
2712 * queues, for at least two reasons: 1) the original weight of a
2713 * merged queue may change during the merged state, 2) even being the
2714 * weight the same, a merged queue may be bloated with many more
2715 * requests than the ones produced by its originally-associated
2716 * process.
2717 */
2718static struct bfq_queue *
2719bfq_setup_cooperator(struct bfq_data *bfqd, struct bfq_queue *bfqq,
2720                     void *io_struct, bool request, struct bfq_io_cq *bic)
2721{
2722        struct bfq_queue *in_service_bfqq, *new_bfqq;
2723
2724        /*
2725         * Check delayed stable merge for rotational or non-queueing
2726         * devs. For this branch to be executed, bfqq must not be
2727         * currently merged with some other queue (i.e., bfqq->bic
2728         * must be non null). If we considered also merged queues,
2729         * then we should also check whether bfqq has already been
2730         * merged with bic->stable_merge_bfqq. But this would be
2731         * costly and complicated.
2732         */
2733        if (unlikely(!bfqd->nonrot_with_queueing)) {
2734                /*
2735                 * Make sure also that bfqq is sync, because
2736                 * bic->stable_merge_bfqq may point to some queue (for
2737                 * stable merging) also if bic is associated with a
2738                 * sync queue, but this bfqq is async
2739                 */
2740                if (bfq_bfqq_sync(bfqq) && bic->stable_merge_bfqq &&
2741                    !bfq_bfqq_just_created(bfqq) &&
2742                    time_is_before_jiffies(bfqq->split_time +
2743                                          msecs_to_jiffies(bfq_late_stable_merging)) &&
2744                    time_is_before_jiffies(bfqq->creation_time +
2745                                           msecs_to_jiffies(bfq_late_stable_merging))) {
2746                        struct bfq_queue *stable_merge_bfqq =
2747                                bic->stable_merge_bfqq;
2748                        int proc_ref = min(bfqq_process_refs(bfqq),
2749                                           bfqq_process_refs(stable_merge_bfqq));
2750
2751                        /* deschedule stable merge, because done or aborted here */
2752                        bfq_put_stable_ref(stable_merge_bfqq);
2753
2754                        bic->stable_merge_bfqq = NULL;
2755
2756                        if (!idling_boosts_thr_without_issues(bfqd, bfqq) &&
2757                            proc_ref > 0) {
2758                                /* next function will take at least one ref */
2759                                struct bfq_queue *new_bfqq =
2760                                        bfq_setup_merge(bfqq, stable_merge_bfqq);
2761
2762                                bic->stably_merged = true;
2763                                if (new_bfqq && new_bfqq->bic)
2764                                        new_bfqq->bic->stably_merged = true;
2765                                return new_bfqq;
2766                        } else
2767                                return NULL;
2768                }
2769        }
2770
2771        /*
2772         * Do not perform queue merging if the device is non
2773         * rotational and performs internal queueing. In fact, such a
2774         * device reaches a high speed through internal parallelism
2775         * and pipelining. This means that, to reach a high
2776         * throughput, it must have many requests enqueued at the same
2777         * time. But, in this configuration, the internal scheduling
2778         * algorithm of the device does exactly the job of queue
2779         * merging: it reorders requests so as to obtain as much as
2780         * possible a sequential I/O pattern. As a consequence, with
2781         * the workload generated by processes doing interleaved I/O,
2782         * the throughput reached by the device is likely to be the
2783         * same, with and without queue merging.
2784         *
2785         * Disabling merging also provides a remarkable benefit in
2786         * terms of throughput. Merging tends to make many workloads
2787         * artificially more uneven, because of shared queues
2788         * remaining non empty for incomparably more time than
2789         * non-merged queues. This may accentuate workload
2790         * asymmetries. For example, if one of the queues in a set of
2791         * merged queues has a higher weight than a normal queue, then
2792         * the shared queue may inherit such a high weight and, by
2793         * staying almost always active, may force BFQ to perform I/O
2794         * plugging most of the time. This evidently makes it harder
2795         * for BFQ to let the device reach a high throughput.
2796         *
2797         * Finally, the likely() macro below is not used because one
2798         * of the two branches is more likely than the other, but to
2799         * have the code path after the following if() executed as
2800         * fast as possible for the case of a non rotational device
2801         * with queueing. We want it because this is the fastest kind
2802         * of device. On the opposite end, the likely() may lengthen
2803         * the execution time of BFQ for the case of slower devices
2804         * (rotational or at least without queueing). But in this case
2805         * the execution time of BFQ matters very little, if not at
2806         * all.
2807         */
2808        if (likely(bfqd->nonrot_with_queueing))
2809                return NULL;
2810
2811        /*
2812         * Prevent bfqq from being merged if it has been created too
2813         * long ago. The idea is that true cooperating processes, and
2814         * thus their associated bfq_queues, are supposed to be
2815         * created shortly after each other. This is the case, e.g.,
2816         * for KVM/QEMU and dump I/O threads. Basing on this
2817         * assumption, the following filtering greatly reduces the
2818         * probability that two non-cooperating processes, which just
2819         * happen to do close I/O for some short time interval, have
2820         * their queues merged by mistake.
2821         */
2822        if (bfq_too_late_for_merging(bfqq))
2823                return NULL;
2824
2825        if (bfqq->new_bfqq)
2826                return bfqq->new_bfqq;
2827
2828        if (!io_struct || unlikely(bfqq == &bfqd->oom_bfqq))
2829                return NULL;
2830
2831        /* If there is only one backlogged queue, don't search. */
2832        if (bfq_tot_busy_queues(bfqd) == 1)
2833                return NULL;
2834
2835        in_service_bfqq = bfqd->in_service_queue;
2836
2837        if (in_service_bfqq && in_service_bfqq != bfqq &&
2838            likely(in_service_bfqq != &bfqd->oom_bfqq) &&
2839            bfq_rq_close_to_sector(io_struct, request,
2840                                   bfqd->in_serv_last_pos) &&
2841            bfqq->entity.parent == in_service_bfqq->entity.parent &&
2842            bfq_may_be_close_cooperator(bfqq, in_service_bfqq)) {
2843                new_bfqq = bfq_setup_merge(bfqq, in_service_bfqq);
2844                if (new_bfqq)
2845                        return new_bfqq;
2846        }
2847        /*
2848         * Check whether there is a cooperator among currently scheduled
2849         * queues. The only thing we need is that the bio/request is not
2850         * NULL, as we need it to establish whether a cooperator exists.
2851         */
2852        new_bfqq = bfq_find_close_cooperator(bfqd, bfqq,
2853                        bfq_io_struct_pos(io_struct, request));
2854
2855        if (new_bfqq && likely(new_bfqq != &bfqd->oom_bfqq) &&
2856            bfq_may_be_close_cooperator(bfqq, new_bfqq))
2857                return bfq_setup_merge(bfqq, new_bfqq);
2858
2859        return NULL;
2860}
2861
2862static void bfq_bfqq_save_state(struct bfq_queue *bfqq)
2863{
2864        struct bfq_io_cq *bic = bfqq->bic;
2865
2866        /*
2867         * If !bfqq->bic, the queue is already shared or its requests
2868         * have already been redirected to a shared queue; both idle window
2869         * and weight raising state have already been saved. Do nothing.
2870         */
2871        if (!bic)
2872                return;
2873
2874        bic->saved_last_serv_time_ns = bfqq->last_serv_time_ns;
2875        bic->saved_inject_limit = bfqq->inject_limit;
2876        bic->saved_decrease_time_jif = bfqq->decrease_time_jif;
2877
2878        bic->saved_weight = bfqq->entity.orig_weight;
2879        bic->saved_ttime = bfqq->ttime;
2880        bic->saved_has_short_ttime = bfq_bfqq_has_short_ttime(bfqq);
2881        bic->saved_IO_bound = bfq_bfqq_IO_bound(bfqq);
2882        bic->saved_io_start_time = bfqq->io_start_time;
2883        bic->saved_tot_idle_time = bfqq->tot_idle_time;
2884        bic->saved_in_large_burst = bfq_bfqq_in_large_burst(bfqq);
2885        bic->was_in_burst_list = !hlist_unhashed(&bfqq->burst_list_node);
2886        if (unlikely(bfq_bfqq_just_created(bfqq) &&
2887                     !bfq_bfqq_in_large_burst(bfqq) &&
2888                     bfqq->bfqd->low_latency)) {
2889                /*
2890                 * bfqq being merged right after being created: bfqq
2891                 * would have deserved interactive weight raising, but
2892                 * did not make it to be set in a weight-raised state,
2893                 * because of this early merge. Store directly the
2894                 * weight-raising state that would have been assigned
2895                 * to bfqq, so that to avoid that bfqq unjustly fails
2896                 * to enjoy weight raising if split soon.
2897                 */
2898                bic->saved_wr_coeff = bfqq->bfqd->bfq_wr_coeff;
2899                bic->saved_wr_start_at_switch_to_srt = bfq_smallest_from_now();
2900                bic->saved_wr_cur_max_time = bfq_wr_duration(bfqq->bfqd);
2901                bic->saved_last_wr_start_finish = jiffies;
2902        } else {
2903                bic->saved_wr_coeff = bfqq->wr_coeff;
2904                bic->saved_wr_start_at_switch_to_srt =
2905                        bfqq->wr_start_at_switch_to_srt;
2906                bic->saved_service_from_wr = bfqq->service_from_wr;
2907                bic->saved_last_wr_start_finish = bfqq->last_wr_start_finish;
2908                bic->saved_wr_cur_max_time = bfqq->wr_cur_max_time;
2909        }
2910}
2911
2912
2913static void
2914bfq_reassign_last_bfqq(struct bfq_queue *cur_bfqq, struct bfq_queue *new_bfqq)
2915{
2916        if (cur_bfqq->entity.parent &&
2917            cur_bfqq->entity.parent->last_bfqq_created == cur_bfqq)
2918                cur_bfqq->entity.parent->last_bfqq_created = new_bfqq;
2919        else if (cur_bfqq->bfqd && cur_bfqq->bfqd->last_bfqq_created == cur_bfqq)
2920                cur_bfqq->bfqd->last_bfqq_created = new_bfqq;
2921}
2922
2923void bfq_release_process_ref(struct bfq_data *bfqd, struct bfq_queue *bfqq)
2924{
2925        /*
2926         * To prevent bfqq's service guarantees from being violated,
2927         * bfqq may be left busy, i.e., queued for service, even if
2928         * empty (see comments in __bfq_bfqq_expire() for
2929         * details). But, if no process will send requests to bfqq any
2930         * longer, then there is no point in keeping bfqq queued for
2931         * service. In addition, keeping bfqq queued for service, but
2932         * with no process ref any longer, may have caused bfqq to be
2933         * freed when dequeued from service. But this is assumed to
2934         * never happen.
2935         */
2936        if (bfq_bfqq_busy(bfqq) && RB_EMPTY_ROOT(&bfqq->sort_list) &&
2937            bfqq != bfqd->in_service_queue)
2938                bfq_del_bfqq_busy(bfqd, bfqq, false);
2939
2940        bfq_reassign_last_bfqq(bfqq, NULL);
2941
2942        bfq_put_queue(bfqq);
2943}
2944
2945static void
2946bfq_merge_bfqqs(struct bfq_data *bfqd, struct bfq_io_cq *bic,
2947                struct bfq_queue *bfqq, struct bfq_queue *new_bfqq)
2948{
2949        bfq_log_bfqq(bfqd, bfqq, "merging with queue %lu",
2950                (unsigned long)new_bfqq->pid);
2951        /* Save weight raising and idle window of the merged queues */
2952        bfq_bfqq_save_state(bfqq);
2953        bfq_bfqq_save_state(new_bfqq);
2954        if (bfq_bfqq_IO_bound(bfqq))
2955                bfq_mark_bfqq_IO_bound(new_bfqq);
2956        bfq_clear_bfqq_IO_bound(bfqq);
2957
2958        /*
2959         * The processes associated with bfqq are cooperators of the
2960         * processes associated with new_bfqq. So, if bfqq has a
2961         * waker, then assume that all these processes will be happy
2962         * to let bfqq's waker freely inject I/O when they have no
2963         * I/O.
2964         */
2965        if (bfqq->waker_bfqq && !new_bfqq->waker_bfqq &&
2966            bfqq->waker_bfqq != new_bfqq) {
2967                new_bfqq->waker_bfqq = bfqq->waker_bfqq;
2968                new_bfqq->tentative_waker_bfqq = NULL;
2969
2970                /*
2971                 * If the waker queue disappears, then
2972                 * new_bfqq->waker_bfqq must be reset. So insert
2973                 * new_bfqq into the woken_list of the waker. See
2974                 * bfq_check_waker for details.
2975                 */
2976                hlist_add_head(&new_bfqq->woken_list_node,
2977                               &new_bfqq->waker_bfqq->woken_list);
2978
2979        }
2980
2981        /*
2982         * If bfqq is weight-raised, then let new_bfqq inherit
2983         * weight-raising. To reduce false positives, neglect the case
2984         * where bfqq has just been created, but has not yet made it
2985         * to be weight-raised (which may happen because EQM may merge
2986         * bfqq even before bfq_add_request is executed for the first
2987         * time for bfqq). Handling this case would however be very
2988         * easy, thanks to the flag just_created.
2989         */
2990        if (new_bfqq->wr_coeff == 1 && bfqq->wr_coeff > 1) {
2991                new_bfqq->wr_coeff = bfqq->wr_coeff;
2992                new_bfqq->wr_cur_max_time = bfqq->wr_cur_max_time;
2993                new_bfqq->last_wr_start_finish = bfqq->last_wr_start_finish;
2994                new_bfqq->wr_start_at_switch_to_srt =
2995                        bfqq->wr_start_at_switch_to_srt;
2996                if (bfq_bfqq_busy(new_bfqq))
2997                        bfqd->wr_busy_queues++;
2998                new_bfqq->entity.prio_changed = 1;
2999        }
3000
3001        if (bfqq->wr_coeff > 1) { /* bfqq has given its wr to new_bfqq */
3002                bfqq->wr_coeff = 1;
3003                bfqq->entity.prio_changed = 1;
3004                if (bfq_bfqq_busy(bfqq))
3005                        bfqd->wr_busy_queues--;
3006        }
3007
3008        bfq_log_bfqq(bfqd, new_bfqq, "merge_bfqqs: wr_busy %d",
3009                     bfqd->wr_busy_queues);
3010
3011        /*
3012         * Merge queues (that is, let bic redirect its requests to new_bfqq)
3013         */
3014        bic_set_bfqq(bic, new_bfqq, 1);
3015        bfq_mark_bfqq_coop(new_bfqq);
3016        /*
3017         * new_bfqq now belongs to at least two bics (it is a shared queue):
3018         * set new_bfqq->bic to NULL. bfqq either:
3019         * - does not belong to any bic any more, and hence bfqq->bic must
3020         *   be set to NULL, or
3021         * - is a queue whose owning bics have already been redirected to a
3022         *   different queue, hence the queue is destined to not belong to
3023         *   any bic soon and bfqq->bic is already NULL (therefore the next
3024         *   assignment causes no harm).
3025         */
3026        new_bfqq->bic = NULL;
3027        /*
3028         * If the queue is shared, the pid is the pid of one of the associated
3029         * processes. Which pid depends on the exact sequence of merge events
3030         * the queue underwent. So printing such a pid is useless and confusing
3031         * because it reports a random pid between those of the associated
3032         * processes.
3033         * We mark such a queue with a pid -1, and then print SHARED instead of
3034         * a pid in logging messages.
3035         */
3036        new_bfqq->pid = -1;
3037        bfqq->bic = NULL;
3038
3039        bfq_reassign_last_bfqq(bfqq, new_bfqq);
3040
3041        bfq_release_process_ref(bfqd, bfqq);
3042}
3043
3044static bool bfq_allow_bio_merge(struct request_queue *q, struct request *rq,
3045                                struct bio *bio)
3046{
3047        struct bfq_data *bfqd = q->elevator->elevator_data;
3048        bool is_sync = op_is_sync(bio->bi_opf);
3049        struct bfq_queue *bfqq = bfqd->bio_bfqq, *new_bfqq;
3050
3051        /*
3052         * Disallow merge of a sync bio into an async request.
3053         */
3054        if (is_sync && !rq_is_sync(rq))
3055                return false;
3056
3057        /*
3058         * Lookup the bfqq that this bio will be queued with. Allow
3059         * merge only if rq is queued there.
3060         */
3061        if (!bfqq)
3062                return false;
3063
3064        /*
3065         * We take advantage of this function to perform an early merge
3066         * of the queues of possible cooperating processes.
3067         */
3068        new_bfqq = bfq_setup_cooperator(bfqd, bfqq, bio, false, bfqd->bio_bic);
3069        if (new_bfqq) {
3070                /*
3071                 * bic still points to bfqq, then it has not yet been
3072                 * redirected to some other bfq_queue, and a queue
3073                 * merge between bfqq and new_bfqq can be safely
3074                 * fulfilled, i.e., bic can be redirected to new_bfqq
3075                 * and bfqq can be put.
3076                 */
3077                bfq_merge_bfqqs(bfqd, bfqd->bio_bic, bfqq,
3078                                new_bfqq);
3079                /*
3080                 * If we get here, bio will be queued into new_queue,
3081                 * so use new_bfqq to decide whether bio and rq can be
3082                 * merged.
3083                 */
3084                bfqq = new_bfqq;
3085
3086                /*
3087                 * Change also bqfd->bio_bfqq, as
3088                 * bfqd->bio_bic now points to new_bfqq, and
3089                 * this function may be invoked again (and then may
3090                 * use again bqfd->bio_bfqq).
3091                 */
3092                bfqd->bio_bfqq = bfqq;
3093        }
3094
3095        return bfqq == RQ_BFQQ(rq);
3096}
3097
3098/*
3099 * Set the maximum time for the in-service queue to consume its
3100 * budget. This prevents seeky processes from lowering the throughput.
3101 * In practice, a time-slice service scheme is used with seeky
3102 * processes.
3103 */
3104static void bfq_set_budget_timeout(struct bfq_data *bfqd,
3105                                   struct bfq_queue *bfqq)
3106{
3107        unsigned int timeout_coeff;
3108
3109        if (bfqq->wr_cur_max_time == bfqd->bfq_wr_rt_max_time)
3110                timeout_coeff = 1;
3111        else
3112                timeout_coeff = bfqq->entity.weight / bfqq->entity.orig_weight;
3113
3114        bfqd->last_budget_start = ktime_get();
3115
3116        bfqq->budget_timeout = jiffies +
3117                bfqd->bfq_timeout * timeout_coeff;
3118}
3119
3120static void __bfq_set_in_service_queue(struct bfq_data *bfqd,
3121                                       struct bfq_queue *bfqq)
3122{
3123        if (bfqq) {
3124                bfq_clear_bfqq_fifo_expire(bfqq);
3125
3126                bfqd->budgets_assigned = (bfqd->budgets_assigned * 7 + 256) / 8;
3127
3128                if (time_is_before_jiffies(bfqq->last_wr_start_finish) &&
3129                    bfqq->wr_coeff > 1 &&
3130                    bfqq->wr_cur_max_time == bfqd->bfq_wr_rt_max_time &&
3131                    time_is_before_jiffies(bfqq->budget_timeout)) {
3132                        /*
3133                         * For soft real-time queues, move the start
3134                         * of the weight-raising period forward by the
3135                         * time the queue has not received any
3136                         * service. Otherwise, a relatively long
3137                         * service delay is likely to cause the
3138                         * weight-raising period of the queue to end,
3139                         * because of the short duration of the
3140                         * weight-raising period of a soft real-time
3141                         * queue.  It is worth noting that this move
3142                         * is not so dangerous for the other queues,
3143                         * because soft real-time queues are not
3144                         * greedy.
3145                         *
3146                         * To not add a further variable, we use the
3147                         * overloaded field budget_timeout to
3148                         * determine for how long the queue has not
3149                         * received service, i.e., how much time has
3150                         * elapsed since the queue expired. However,
3151                         * this is a little imprecise, because
3152                         * budget_timeout is set to jiffies if bfqq
3153                         * not only expires, but also remains with no
3154                         * request.
3155                         */
3156                        if (time_after(bfqq->budget_timeout,
3157                                       bfqq->last_wr_start_finish))
3158                                bfqq->last_wr_start_finish +=
3159                                        jiffies - bfqq->budget_timeout;
3160                        else
3161                                bfqq->last_wr_start_finish = jiffies;
3162                }
3163
3164                bfq_set_budget_timeout(bfqd, bfqq);
3165                bfq_log_bfqq(bfqd, bfqq,
3166                             "set_in_service_queue, cur-budget = %d",
3167                             bfqq->entity.budget);
3168        }
3169
3170        bfqd->in_service_queue = bfqq;
3171        bfqd->in_serv_last_pos = 0;
3172}
3173
3174/*
3175 * Get and set a new queue for service.
3176 */
3177static struct bfq_queue *bfq_set_in_service_queue(struct bfq_data *bfqd)
3178{
3179        struct bfq_queue *bfqq = bfq_get_next_queue(bfqd);
3180
3181        __bfq_set_in_service_queue(bfqd, bfqq);
3182        return bfqq;
3183}
3184
3185static void bfq_arm_slice_timer(struct bfq_data *bfqd)
3186{
3187        struct bfq_queue *bfqq = bfqd->in_service_queue;
3188        u32 sl;
3189
3190        bfq_mark_bfqq_wait_request(bfqq);
3191
3192        /*
3193         * We don't want to idle for seeks, but we do want to allow
3194         * fair distribution of slice time for a process doing back-to-back
3195         * seeks. So allow a little bit of time for him to submit a new rq.
3196         */
3197        sl = bfqd->bfq_slice_idle;
3198        /*
3199         * Unless the queue is being weight-raised or the scenario is
3200         * asymmetric, grant only minimum idle time if the queue
3201         * is seeky. A long idling is preserved for a weight-raised
3202         * queue, or, more in general, in an asymmetric scenario,
3203         * because a long idling is needed for guaranteeing to a queue
3204         * its reserved share of the throughput (in particular, it is
3205         * needed if the queue has a higher weight than some other
3206         * queue).
3207         */
3208        if (BFQQ_SEEKY(bfqq) && bfqq->wr_coeff == 1 &&
3209            !bfq_asymmetric_scenario(bfqd, bfqq))
3210                sl = min_t(u64, sl, BFQ_MIN_TT);
3211        else if (bfqq->wr_coeff > 1)
3212                sl = max_t(u32, sl, 20ULL * NSEC_PER_MSEC);
3213
3214        bfqd->last_idling_start = ktime_get();
3215        bfqd->last_idling_start_jiffies = jiffies;
3216
3217        hrtimer_start(&bfqd->idle_slice_timer, ns_to_ktime(sl),
3218                      HRTIMER_MODE_REL);
3219        bfqg_stats_set_start_idle_time(bfqq_group(bfqq));
3220}
3221
3222/*
3223 * In autotuning mode, max_budget is dynamically recomputed as the
3224 * amount of sectors transferred in timeout at the estimated peak
3225 * rate. This enables BFQ to utilize a full timeslice with a full
3226 * budget, even if the in-service queue is served at peak rate. And
3227 * this maximises throughput with sequential workloads.
3228 */
3229static unsigned long bfq_calc_max_budget(struct bfq_data *bfqd)
3230{
3231        return (u64)bfqd->peak_rate * USEC_PER_MSEC *
3232                jiffies_to_msecs(bfqd->bfq_timeout)>>BFQ_RATE_SHIFT;
3233}
3234
3235/*
3236 * Update parameters related to throughput and responsiveness, as a
3237 * function of the estimated peak rate. See comments on
3238 * bfq_calc_max_budget(), and on the ref_wr_duration array.
3239 */
3240static void update_thr_responsiveness_params(struct bfq_data *bfqd)
3241{
3242        if (bfqd->bfq_user_max_budget == 0) {
3243                bfqd->bfq_max_budget =
3244                        bfq_calc_max_budget(bfqd);
3245                bfq_log(bfqd, "new max_budget = %d", bfqd->bfq_max_budget);
3246        }
3247}
3248
3249static void bfq_reset_rate_computation(struct bfq_data *bfqd,
3250                                       struct request *rq)
3251{
3252        if (rq != NULL) { /* new rq dispatch now, reset accordingly */
3253                bfqd->last_dispatch = bfqd->first_dispatch = ktime_get_ns();
3254                bfqd->peak_rate_samples = 1;
3255                bfqd->sequential_samples = 0;
3256                bfqd->tot_sectors_dispatched = bfqd->last_rq_max_size =
3257                        blk_rq_sectors(rq);
3258        } else /* no new rq dispatched, just reset the number of samples */
3259                bfqd->peak_rate_samples = 0; /* full re-init on next disp. */
3260
3261        bfq_log(bfqd,
3262                "reset_rate_computation at end, sample %u/%u tot_sects %llu",
3263                bfqd->peak_rate_samples, bfqd->sequential_samples,
3264                bfqd->tot_sectors_dispatched);
3265}
3266
3267static void bfq_update_rate_reset(struct bfq_data *bfqd, struct request *rq)
3268{
3269        u32 rate, weight, divisor;
3270
3271        /*
3272         * For the convergence property to hold (see comments on
3273         * bfq_update_peak_rate()) and for the assessment to be
3274         * reliable, a minimum number of samples must be present, and
3275         * a minimum amount of time must have elapsed. If not so, do
3276         * not compute new rate. Just reset parameters, to get ready
3277         * for a new evaluation attempt.
3278         */
3279        if (bfqd->peak_rate_samples < BFQ_RATE_MIN_SAMPLES ||
3280            bfqd->delta_from_first < BFQ_RATE_MIN_INTERVAL)
3281                goto reset_computation;
3282
3283        /*
3284         * If a new request completion has occurred after last
3285         * dispatch, then, to approximate the rate at which requests
3286         * have been served by the device, it is more precise to
3287         * extend the observation interval to the last completion.
3288         */
3289        bfqd->delta_from_first =
3290                max_t(u64, bfqd->delta_from_first,
3291                      bfqd->last_completion - bfqd->first_dispatch);
3292
3293        /*
3294         * Rate computed in sects/usec, and not sects/nsec, for
3295         * precision issues.
3296         */
3297        rate = div64_ul(bfqd->tot_sectors_dispatched<<BFQ_RATE_SHIFT,
3298                        div_u64(bfqd->delta_from_first, NSEC_PER_USEC));
3299
3300        /*
3301         * Peak rate not updated if:
3302         * - the percentage of sequential dispatches is below 3/4 of the
3303         *   total, and rate is below the current estimated peak rate
3304         * - rate is unreasonably high (> 20M sectors/sec)
3305         */
3306        if ((bfqd->sequential_samples < (3 * bfqd->peak_rate_samples)>>2 &&
3307             rate <= bfqd->peak_rate) ||
3308                rate > 20<<BFQ_RATE_SHIFT)
3309                goto reset_computation;
3310
3311        /*
3312         * We have to update the peak rate, at last! To this purpose,
3313         * we use a low-pass filter. We compute the smoothing constant
3314         * of the filter as a function of the 'weight' of the new
3315         * measured rate.
3316         *
3317         * As can be seen in next formulas, we define this weight as a
3318         * quantity proportional to how sequential the workload is,
3319         * and to how long the observation time interval is.
3320         *
3321         * The weight runs from 0 to 8. The maximum value of the
3322         * weight, 8, yields the minimum value for the smoothing
3323         * constant. At this minimum value for the smoothing constant,
3324         * the measured rate contributes for half of the next value of
3325         * the estimated peak rate.
3326         *
3327         * So, the first step is to compute the weight as a function
3328         * of how sequential the workload is. Note that the weight
3329         * cannot reach 9, because bfqd->sequential_samples cannot
3330         * become equal to bfqd->peak_rate_samples, which, in its
3331         * turn, holds true because bfqd->sequential_samples is not
3332         * incremented for the first sample.
3333         */
3334        weight = (9 * bfqd->sequential_samples) / bfqd->peak_rate_samples;
3335
3336        /*
3337         * Second step: further refine the weight as a function of the
3338         * duration of the observation interval.
3339         */
3340        weight = min_t(u32, 8,
3341                       div_u64(weight * bfqd->delta_from_first,
3342                               BFQ_RATE_REF_INTERVAL));
3343
3344        /*
3345         * Divisor ranging from 10, for minimum weight, to 2, for
3346         * maximum weight.
3347         */
3348        divisor = 10 - weight;
3349
3350        /*
3351         * Finally, update peak rate:
3352         *
3353         * peak_rate = peak_rate * (divisor-1) / divisor  +  rate / divisor
3354         */
3355        bfqd->peak_rate *= divisor-1;
3356        bfqd->peak_rate /= divisor;
3357        rate /= divisor; /* smoothing constant alpha = 1/divisor */
3358
3359        bfqd->peak_rate += rate;
3360
3361        /*
3362         * For a very slow device, bfqd->peak_rate can reach 0 (see
3363         * the minimum representable values reported in the comments
3364         * on BFQ_RATE_SHIFT). Push to 1 if this happens, to avoid
3365         * divisions by zero where bfqd->peak_rate is used as a
3366         * divisor.
3367         */
3368        bfqd->peak_rate = max_t(u32, 1, bfqd->peak_rate);
3369
3370        update_thr_responsiveness_params(bfqd);
3371
3372reset_computation:
3373        bfq_reset_rate_computation(bfqd, rq);
3374}
3375
3376/*
3377 * Update the read/write peak rate (the main quantity used for
3378 * auto-tuning, see update_thr_responsiveness_params()).
3379 *
3380 * It is not trivial to estimate the peak rate (correctly): because of
3381 * the presence of sw and hw queues between the scheduler and the
3382 * device components that finally serve I/O requests, it is hard to
3383 * say exactly when a given dispatched request is served inside the
3384 * device, and for how long. As a consequence, it is hard to know
3385 * precisely at what rate a given set of requests is actually served
3386 * by the device.
3387 *
3388 * On the opposite end, the dispatch time of any request is trivially
3389 * available, and, from this piece of information, the "dispatch rate"
3390 * of requests can be immediately computed. So, the idea in the next
3391 * function is to use what is known, namely request dispatch times
3392 * (plus, when useful, request completion times), to estimate what is
3393 * unknown, namely in-device request service rate.
3394 *
3395 * The main issue is that, because of the above facts, the rate at
3396 * which a certain set of requests is dispatched over a certain time
3397 * interval can vary greatly with respect to the rate at which the
3398 * same requests are then served. But, since the size of any
3399 * intermediate queue is limited, and the service scheme is lossless
3400 * (no request is silently dropped), the following obvious convergence
3401 * property holds: the number of requests dispatched MUST become
3402 * closer and closer to the number of requests completed as the
3403 * observation interval grows. This is the key property used in
3404 * the next function to estimate the peak service rate as a function
3405 * of the observed dispatch rate. The function assumes to be invoked
3406 * on every request dispatch.
3407 */
3408static void bfq_update_peak_rate(struct bfq_data *bfqd, struct request *rq)
3409{
3410        u64 now_ns = ktime_get_ns();
3411
3412        if (bfqd->peak_rate_samples == 0) { /* first dispatch */
3413                bfq_log(bfqd, "update_peak_rate: goto reset, samples %d",
3414                        bfqd->peak_rate_samples);
3415                bfq_reset_rate_computation(bfqd, rq);
3416                goto update_last_values; /* will add one sample */
3417        }
3418
3419        /*
3420         * Device idle for very long: the observation interval lasting
3421         * up to this dispatch cannot be a valid observation interval
3422         * for computing a new peak rate (similarly to the late-
3423         * completion event in bfq_completed_request()). Go to
3424         * update_rate_and_reset to have the following three steps
3425         * taken:
3426         * - close the observation interval at the last (previous)
3427         *   request dispatch or completion
3428         * - compute rate, if possible, for that observation interval
3429         * - start a new observation interval with this dispatch
3430         */
3431        if (now_ns - bfqd->last_dispatch > 100*NSEC_PER_MSEC &&
3432            bfqd->rq_in_driver == 0)
3433                goto update_rate_and_reset;
3434
3435        /* Update sampling information */
3436        bfqd->peak_rate_samples++;
3437
3438        if ((bfqd->rq_in_driver > 0 ||
3439                now_ns - bfqd->last_completion < BFQ_MIN_TT)
3440            && !BFQ_RQ_SEEKY(bfqd, bfqd->last_position, rq))
3441                bfqd->sequential_samples++;
3442
3443        bfqd->tot_sectors_dispatched += blk_rq_sectors(rq);
3444
3445        /* Reset max observed rq size every 32 dispatches */
3446        if (likely(bfqd->peak_rate_samples % 32))
3447                bfqd->last_rq_max_size =
3448                        max_t(u32, blk_rq_sectors(rq), bfqd->last_rq_max_size);
3449        else
3450                bfqd->last_rq_max_size = blk_rq_sectors(rq);
3451
3452        bfqd->delta_from_first = now_ns - bfqd->first_dispatch;
3453
3454        /* Target observation interval not yet reached, go on sampling */
3455        if (bfqd->delta_from_first < BFQ_RATE_REF_INTERVAL)
3456                goto update_last_values;
3457
3458update_rate_and_reset:
3459        bfq_update_rate_reset(bfqd, rq);
3460update_last_values:
3461        bfqd->last_position = blk_rq_pos(rq) + blk_rq_sectors(rq);
3462        if (RQ_BFQQ(rq) == bfqd->in_service_queue)
3463                bfqd->in_serv_last_pos = bfqd->last_position;
3464        bfqd->last_dispatch = now_ns;
3465}
3466
3467/*
3468 * Remove request from internal lists.
3469 */
3470static void bfq_dispatch_remove(struct request_queue *q, struct request *rq)
3471{
3472        struct bfq_queue *bfqq = RQ_BFQQ(rq);
3473
3474        /*
3475         * For consistency, the next instruction should have been
3476         * executed after removing the request from the queue and
3477         * dispatching it.  We execute instead this instruction before
3478         * bfq_remove_request() (and hence introduce a temporary
3479         * inconsistency), for efficiency.  In fact, should this
3480         * dispatch occur for a non in-service bfqq, this anticipated
3481         * increment prevents two counters related to bfqq->dispatched
3482         * from risking to be, first, uselessly decremented, and then
3483         * incremented again when the (new) value of bfqq->dispatched
3484         * happens to be taken into account.
3485         */
3486        bfqq->dispatched++;
3487        bfq_update_peak_rate(q->elevator->elevator_data, rq);
3488
3489        bfq_remove_request(q, rq);
3490}
3491
3492/*
3493 * There is a case where idling does not have to be performed for
3494 * throughput concerns, but to preserve the throughput share of
3495 * the process associated with bfqq.
3496 *
3497 * To introduce this case, we can note that allowing the drive
3498 * to enqueue more than one request at a time, and hence
3499 * delegating de facto final scheduling decisions to the
3500 * drive's internal scheduler, entails loss of control on the
3501 * actual request service order. In particular, the critical
3502 * situation is when requests from different processes happen
3503 * to be present, at the same time, in the internal queue(s)
3504 * of the drive. In such a situation, the drive, by deciding
3505 * the service order of the internally-queued requests, does
3506 * determine also the actual throughput distribution among
3507 * these processes. But the drive typically has no notion or
3508 * concern about per-process throughput distribution, and
3509 * makes its decisions only on a per-request basis. Therefore,
3510 * the service distribution enforced by the drive's internal
3511 * scheduler is likely to coincide with the desired throughput
3512 * distribution only in a completely symmetric, or favorably
3513 * skewed scenario where:
3514 * (i-a) each of these processes must get the same throughput as
3515 *       the others,
3516 * (i-b) in case (i-a) does not hold, it holds that the process
3517 *       associated with bfqq must receive a lower or equal
3518 *       throughput than any of the other processes;
3519 * (ii)  the I/O of each process has the same properties, in
3520 *       terms of locality (sequential or random), direction
3521 *       (reads or writes), request sizes, greediness
3522 *       (from I/O-bound to sporadic), and so on;
3523
3524 * In fact, in such a scenario, the drive tends to treat the requests
3525 * of each process in about the same way as the requests of the
3526 * others, and thus to provide each of these processes with about the
3527 * same throughput.  This is exactly the desired throughput
3528 * distribution if (i-a) holds, or, if (i-b) holds instead, this is an
3529 * even more convenient distribution for (the process associated with)
3530 * bfqq.
3531 *
3532 * In contrast, in any asymmetric or unfavorable scenario, device
3533 * idling (I/O-dispatch plugging) is certainly needed to guarantee
3534 * that bfqq receives its assigned fraction of the device throughput
3535 * (see [1] for details).
3536 *
3537 * The problem is that idling may significantly reduce throughput with
3538 * certain combinations of types of I/O and devices. An important
3539 * example is sync random I/O on flash storage with command
3540 * queueing. So, unless bfqq falls in cases where idling also boosts
3541 * throughput, it is important to check conditions (i-a), i(-b) and
3542 * (ii) accurately, so as to avoid idling when not strictly needed for
3543 * service guarantees.
3544 *
3545 * Unfortunately, it is extremely difficult to thoroughly check
3546 * condition (ii). And, in case there are active groups, it becomes
3547 * very difficult to check conditions (i-a) and (i-b) too.  In fact,
3548 * if there are active groups, then, for conditions (i-a) or (i-b) to
3549 * become false 'indirectly', it is enough that an active group
3550 * contains more active processes or sub-groups than some other active
3551 * group. More precisely, for conditions (i-a) or (i-b) to become
3552 * false because of such a group, it is not even necessary that the
3553 * group is (still) active: it is sufficient that, even if the group
3554 * has become inactive, some of its descendant processes still have
3555 * some request already dispatched but still waiting for
3556 * completion. In fact, requests have still to be guaranteed their
3557 * share of the throughput even after being dispatched. In this
3558 * respect, it is easy to show that, if a group frequently becomes
3559 * inactive while still having in-flight requests, and if, when this
3560 * happens, the group is not considered in the calculation of whether
3561 * the scenario is asymmetric, then the group may fail to be
3562 * guaranteed its fair share of the throughput (basically because
3563 * idling may not be performed for the descendant processes of the
3564 * group, but it had to be).  We address this issue with the following
3565 * bi-modal behavior, implemented in the function
3566 * bfq_asymmetric_scenario().
3567 *
3568 * If there are groups with requests waiting for completion
3569 * (as commented above, some of these groups may even be
3570 * already inactive), then the scenario is tagged as
3571 * asymmetric, conservatively, without checking any of the
3572 * conditions (i-a), (i-b) or (ii). So the device is idled for bfqq.
3573 * This behavior matches also the fact that groups are created
3574 * exactly if controlling I/O is a primary concern (to
3575 * preserve bandwidth and latency guarantees).
3576 *
3577 * On the opposite end, if there are no groups with requests waiting
3578 * for completion, then only conditions (i-a) and (i-b) are actually
3579 * controlled, i.e., provided that conditions (i-a) or (i-b) holds,
3580 * idling is not performed, regardless of whether condition (ii)
3581 * holds.  In other words, only if conditions (i-a) and (i-b) do not
3582 * hold, then idling is allowed, and the device tends to be prevented
3583 * from queueing many requests, possibly of several processes. Since
3584 * there are no groups with requests waiting for completion, then, to
3585 * control conditions (i-a) and (i-b) it is enough to check just
3586 * whether all the queues with requests waiting for completion also
3587 * have the same weight.
3588 *
3589 * Not checking condition (ii) evidently exposes bfqq to the
3590 * risk of getting less throughput than its fair share.
3591 * However, for queues with the same weight, a further
3592 * mechanism, preemption, mitigates or even eliminates this
3593 * problem. And it does so without consequences on overall
3594 * throughput. This mechanism and its benefits are explained
3595 * in the next three paragraphs.
3596 *
3597 * Even if a queue, say Q, is expired when it remains idle, Q
3598 * can still preempt the new in-service queue if the next
3599 * request of Q arrives soon (see the comments on
3600 * bfq_bfqq_update_budg_for_activation). If all queues and
3601 * groups have the same weight, this form of preemption,
3602 * combined with the hole-recovery heuristic described in the
3603 * comments on function bfq_bfqq_update_budg_for_activation,
3604 * are enough to preserve a correct bandwidth distribution in
3605 * the mid term, even without idling. In fact, even if not
3606 * idling allows the internal queues of the device to contain
3607 * many requests, and thus to reorder requests, we can rather
3608 * safely assume that the internal scheduler still preserves a
3609 * minimum of mid-term fairness.
3610 *
3611 * More precisely, this preemption-based, idleless approach
3612 * provides fairness in terms of IOPS, and not sectors per
3613 * second. This can be seen with a simple example. Suppose
3614 * that there are two queues with the same weight, but that
3615 * the first queue receives requests of 8 sectors, while the
3616 * second queue receives requests of 1024 sectors. In
3617 * addition, suppose that each of the two queues contains at
3618 * most one request at a time, which implies that each queue
3619 * always remains idle after it is served. Finally, after
3620 * remaining idle, each queue receives very quickly a new
3621 * request. It follows that the two queues are served
3622 * alternatively, preempting each other if needed. This
3623 * implies that, although both queues have the same weight,
3624 * the queue with large requests receives a service that is
3625 * 1024/8 times as high as the service received by the other
3626 * queue.
3627 *
3628 * The motivation for using preemption instead of idling (for
3629 * queues with the same weight) is that, by not idling,
3630 * service guarantees are preserved (completely or at least in
3631 * part) without minimally sacrificing throughput. And, if
3632 * there is no active group, then the primary expectation for
3633 * this device is probably a high throughput.
3634 *
3635 * We are now left only with explaining the two sub-conditions in the
3636 * additional compound condition that is checked below for deciding
3637 * whether the scenario is asymmetric. To explain the first
3638 * sub-condition, we need to add that the function
3639 * bfq_asymmetric_scenario checks the weights of only
3640 * non-weight-raised queues, for efficiency reasons (see comments on
3641 * bfq_weights_tree_add()). Then the fact that bfqq is weight-raised
3642 * is checked explicitly here. More precisely, the compound condition
3643 * below takes into account also the fact that, even if bfqq is being
3644 * weight-raised, the scenario is still symmetric if all queues with
3645 * requests waiting for completion happen to be
3646 * weight-raised. Actually, we should be even more precise here, and
3647 * differentiate between interactive weight raising and soft real-time
3648 * weight raising.
3649 *
3650 * The second sub-condition checked in the compound condition is
3651 * whether there is a fair amount of already in-flight I/O not
3652 * belonging to bfqq. If so, I/O dispatching is to be plugged, for the
3653 * following reason. The drive may decide to serve in-flight
3654 * non-bfqq's I/O requests before bfqq's ones, thereby delaying the
3655 * arrival of new I/O requests for bfqq (recall that bfqq is sync). If
3656 * I/O-dispatching is not plugged, then, while bfqq remains empty, a
3657 * basically uncontrolled amount of I/O from other queues may be
3658 * dispatched too, possibly causing the service of bfqq's I/O to be
3659 * delayed even longer in the drive. This problem gets more and more
3660 * serious as the speed and the queue depth of the drive grow,
3661 * because, as these two quantities grow, the probability to find no
3662 * queue busy but many requests in flight grows too. By contrast,
3663 * plugging I/O dispatching minimizes the delay induced by already
3664 * in-flight I/O, and enables bfqq to recover the bandwidth it may
3665 * lose because of this delay.
3666 *
3667 * As a side note, it is worth considering that the above
3668 * device-idling countermeasures may however fail in the following
3669 * unlucky scenario: if I/O-dispatch plugging is (correctly) disabled
3670 * in a time period during which all symmetry sub-conditions hold, and
3671 * therefore the device is allowed to enqueue many requests, but at
3672 * some later point in time some sub-condition stops to hold, then it
3673 * may become impossible to make requests be served in the desired
3674 * order until all the requests already queued in the device have been
3675 * served. The last sub-condition commented above somewhat mitigates
3676 * this problem for weight-raised queues.
3677 *
3678 * However, as an additional mitigation for this problem, we preserve
3679 * plugging for a special symmetric case that may suddenly turn into
3680 * asymmetric: the case where only bfqq is busy. In this case, not
3681 * expiring bfqq does not cause any harm to any other queues in terms
3682 * of service guarantees. In contrast, it avoids the following unlucky
3683 * sequence of events: (1) bfqq is expired, (2) a new queue with a
3684 * lower weight than bfqq becomes busy (or more queues), (3) the new
3685 * queue is served until a new request arrives for bfqq, (4) when bfqq
3686 * is finally served, there are so many requests of the new queue in
3687 * the drive that the pending requests for bfqq take a lot of time to
3688 * be served. In particular, event (2) may case even already
3689 * dispatched requests of bfqq to be delayed, inside the drive. So, to
3690 * avoid this series of events, the scenario is preventively declared
3691 * as asymmetric also if bfqq is the only busy queues
3692 */
3693static bool idling_needed_for_service_guarantees(struct bfq_data *bfqd,
3694                                                 struct bfq_queue *bfqq)
3695{
3696        int tot_busy_queues = bfq_tot_busy_queues(bfqd);
3697
3698        /* No point in idling for bfqq if it won't get requests any longer */
3699        if (unlikely(!bfqq_process_refs(bfqq)))
3700                return false;
3701
3702        return (bfqq->wr_coeff > 1 &&
3703                (bfqd->wr_busy_queues <
3704                 tot_busy_queues ||
3705                 bfqd->rq_in_driver >=
3706                 bfqq->dispatched + 4)) ||
3707                bfq_asymmetric_scenario(bfqd, bfqq) ||
3708                tot_busy_queues == 1;
3709}
3710
3711static bool __bfq_bfqq_expire(struct bfq_data *bfqd, struct bfq_queue *bfqq,
3712                              enum bfqq_expiration reason)
3713{
3714        /*
3715         * If this bfqq is shared between multiple processes, check
3716         * to make sure that those processes are still issuing I/Os
3717         * within the mean seek distance. If not, it may be time to
3718         * break the queues apart again.
3719         */
3720        if (bfq_bfqq_coop(bfqq) && BFQQ_SEEKY(bfqq))
3721                bfq_mark_bfqq_split_coop(bfqq);
3722
3723        /*
3724         * Consider queues with a higher finish virtual time than
3725         * bfqq. If idling_needed_for_service_guarantees(bfqq) returns
3726         * true, then bfqq's bandwidth would be violated if an
3727         * uncontrolled amount of I/O from these queues were
3728         * dispatched while bfqq is waiting for its new I/O to
3729         * arrive. This is exactly what may happen if this is a forced
3730         * expiration caused by a preemption attempt, and if bfqq is
3731         * not re-scheduled. To prevent this from happening, re-queue
3732         * bfqq if it needs I/O-dispatch plugging, even if it is
3733         * empty. By doing so, bfqq is granted to be served before the
3734         * above queues (provided that bfqq is of course eligible).
3735         */
3736        if (RB_EMPTY_ROOT(&bfqq->sort_list) &&
3737            !(reason == BFQQE_PREEMPTED &&
3738              idling_needed_for_service_guarantees(bfqd, bfqq))) {
3739                if (bfqq->dispatched == 0)
3740                        /*
3741                         * Overloading budget_timeout field to store
3742                         * the time at which the queue remains with no
3743                         * backlog and no outstanding request; used by
3744                         * the weight-raising mechanism.
3745                         */
3746                        bfqq->budget_timeout = jiffies;
3747
3748                bfq_del_bfqq_busy(bfqd, bfqq, true);
3749        } else {
3750                bfq_requeue_bfqq(bfqd, bfqq, true);
3751                /*
3752                 * Resort priority tree of potential close cooperators.
3753                 * See comments on bfq_pos_tree_add_move() for the unlikely().
3754                 */
3755                if (unlikely(!bfqd->nonrot_with_queueing &&
3756                             !RB_EMPTY_ROOT(&bfqq->sort_list)))
3757                        bfq_pos_tree_add_move(bfqd, bfqq);
3758        }
3759
3760        /*
3761         * All in-service entities must have been properly deactivated
3762         * or requeued before executing the next function, which
3763         * resets all in-service entities as no more in service. This
3764         * may cause bfqq to be freed. If this happens, the next
3765         * function returns true.
3766         */
3767        return __bfq_bfqd_reset_in_service(bfqd);
3768}
3769
3770/**
3771 * __bfq_bfqq_recalc_budget - try to adapt the budget to the @bfqq behavior.
3772 * @bfqd: device data.
3773 * @bfqq: queue to update.
3774 * @reason: reason for expiration.
3775 *
3776 * Handle the feedback on @bfqq budget at queue expiration.
3777 * See the body for detailed comments.
3778 */
3779static void __bfq_bfqq_recalc_budget(struct bfq_data *bfqd,
3780                                     struct bfq_queue *bfqq,
3781                                     enum bfqq_expiration reason)
3782{
3783        struct request *next_rq;
3784        int budget, min_budget;
3785
3786        min_budget = bfq_min_budget(bfqd);
3787
3788        if (bfqq->wr_coeff == 1)
3789                budget = bfqq->max_budget;
3790        else /*
3791              * Use a constant, low budget for weight-raised queues,
3792              * to help achieve a low latency. Keep it slightly higher
3793              * than the minimum possible budget, to cause a little
3794              * bit fewer expirations.
3795              */
3796                budget = 2 * min_budget;
3797
3798        bfq_log_bfqq(bfqd, bfqq, "recalc_budg: last budg %d, budg left %d",
3799                bfqq->entity.budget, bfq_bfqq_budget_left(bfqq));
3800        bfq_log_bfqq(bfqd, bfqq, "recalc_budg: last max_budg %d, min budg %d",
3801                budget, bfq_min_budget(bfqd));
3802        bfq_log_bfqq(bfqd, bfqq, "recalc_budg: sync %d, seeky %d",
3803                bfq_bfqq_sync(bfqq), BFQQ_SEEKY(bfqd->in_service_queue));
3804
3805        if (bfq_bfqq_sync(bfqq) && bfqq->wr_coeff == 1) {
3806                switch (reason) {
3807                /*
3808                 * Caveat: in all the following cases we trade latency
3809                 * for throughput.
3810                 */
3811                case BFQQE_TOO_IDLE:
3812                        /*
3813                         * This is the only case where we may reduce
3814                         * the budget: if there is no request of the
3815                         * process still waiting for completion, then
3816                         * we assume (tentatively) that the timer has
3817                         * expired because the batch of requests of
3818                         * the process could have been served with a
3819                         * smaller budget.  Hence, betting that
3820                         * process will behave in the same way when it
3821                         * becomes backlogged again, we reduce its
3822                         * next budget.  As long as we guess right,
3823                         * this budget cut reduces the latency
3824                         * experienced by the process.
3825                         *
3826                         * However, if there are still outstanding
3827                         * requests, then the process may have not yet
3828                         * issued its next request just because it is
3829                         * still waiting for the completion of some of
3830                         * the still outstanding ones.  So in this
3831                         * subcase we do not reduce its budget, on the
3832                         * contrary we increase it to possibly boost
3833                         * the throughput, as discussed in the
3834                         * comments to the BUDGET_TIMEOUT case.
3835                         */
3836                        if (bfqq->dispatched > 0) /* still outstanding reqs */
3837                                budget = min(budget * 2, bfqd->bfq_max_budget);
3838                        else {
3839                                if (budget > 5 * min_budget)
3840                                        budget -= 4 * min_budget;
3841                                else
3842                                        budget = min_budget;
3843                        }
3844                        break;
3845                case BFQQE_BUDGET_TIMEOUT:
3846                        /*
3847                         * We double the budget here because it gives
3848                         * the chance to boost the throughput if this
3849                         * is not a seeky process (and has bumped into
3850                         * this timeout because of, e.g., ZBR).
3851                         */
3852                        budget = min(budget * 2, bfqd->bfq_max_budget);
3853                        break;
3854                case BFQQE_BUDGET_EXHAUSTED:
3855                        /*
3856                         * The process still has backlog, and did not
3857                         * let either the budget timeout or the disk
3858                         * idling timeout expire. Hence it is not
3859                         * seeky, has a short thinktime and may be
3860                         * happy with a higher budget too. So
3861                         * definitely increase the budget of this good
3862                         * candidate to boost the disk throughput.
3863                         */
3864                        budget = min(budget * 4, bfqd->bfq_max_budget);
3865                        break;
3866                case BFQQE_NO_MORE_REQUESTS:
3867                        /*
3868                         * For queues that expire for this reason, it
3869                         * is particularly important to keep the
3870                         * budget close to the actual service they
3871                         * need. Doing so reduces the timestamp
3872                         * misalignment problem described in the
3873                         * comments in the body of
3874                         * __bfq_activate_entity. In fact, suppose
3875                         * that a queue systematically expires for
3876                         * BFQQE_NO_MORE_REQUESTS and presents a
3877                         * new request in time to enjoy timestamp
3878                         * back-shifting. The larger the budget of the
3879                         * queue is with respect to the service the
3880                         * queue actually requests in each service
3881                         * slot, the more times the queue can be
3882                         * reactivated with the same virtual finish
3883                         * time. It follows that, even if this finish
3884                         * time is pushed to the system virtual time
3885                         * to reduce the consequent timestamp
3886                         * misalignment, the queue unjustly enjoys for
3887                         * many re-activations a lower finish time
3888                         * than all newly activated queues.
3889                         *
3890                         * The service needed by bfqq is measured
3891                         * quite precisely by bfqq->entity.service.
3892                         * Since bfqq does not enjoy device idling,
3893                         * bfqq->entity.service is equal to the number
3894                         * of sectors that the process associated with
3895                         * bfqq requested to read/write before waiting
3896                         * for request completions, or blocking for
3897                         * other reasons.
3898                         */
3899                        budget = max_t(int, bfqq->entity.service, min_budget);
3900                        break;
3901                default:
3902                        return;
3903                }
3904        } else if (!bfq_bfqq_sync(bfqq)) {
3905                /*
3906                 * Async queues get always the maximum possible
3907                 * budget, as for them we do not care about latency
3908                 * (in addition, their ability to dispatch is limited
3909                 * by the charging factor).
3910                 */
3911                budget = bfqd->bfq_max_budget;
3912        }
3913
3914        bfqq->max_budget = budget;
3915
3916        if (bfqd->budgets_assigned >= bfq_stats_min_budgets &&
3917            !bfqd->bfq_user_max_budget)
3918                bfqq->max_budget = min(bfqq->max_budget, bfqd->bfq_max_budget);
3919
3920        /*
3921         * If there is still backlog, then assign a new budget, making
3922         * sure that it is large enough for the next request.  Since
3923         * the finish time of bfqq must be kept in sync with the
3924         * budget, be sure to call __bfq_bfqq_expire() *after* this
3925         * update.
3926         *
3927         * If there is no backlog, then no need to update the budget;
3928         * it will be updated on the arrival of a new request.
3929         */
3930        next_rq = bfqq->next_rq;
3931        if (next_rq)
3932                bfqq->entity.budget = max_t(unsigned long, bfqq->max_budget,
3933                                            bfq_serv_to_charge(next_rq, bfqq));
3934
3935        bfq_log_bfqq(bfqd, bfqq, "head sect: %u, new budget %d",
3936                        next_rq ? blk_rq_sectors(next_rq) : 0,
3937                        bfqq->entity.budget);
3938}
3939
3940/*
3941 * Return true if the process associated with bfqq is "slow". The slow
3942 * flag is used, in addition to the budget timeout, to reduce the
3943 * amount of service provided to seeky processes, and thus reduce
3944 * their chances to lower the throughput. More details in the comments
3945 * on the function bfq_bfqq_expire().
3946 *
3947 * An important observation is in order: as discussed in the comments
3948 * on the function bfq_update_peak_rate(), with devices with internal
3949 * queues, it is hard if ever possible to know when and for how long
3950 * an I/O request is processed by the device (apart from the trivial
3951 * I/O pattern where a new request is dispatched only after the
3952 * previous one has been completed). This makes it hard to evaluate
3953 * the real rate at which the I/O requests of each bfq_queue are
3954 * served.  In fact, for an I/O scheduler like BFQ, serving a
3955 * bfq_queue means just dispatching its requests during its service
3956 * slot (i.e., until the budget of the queue is exhausted, or the
3957 * queue remains idle, or, finally, a timeout fires). But, during the
3958 * service slot of a bfq_queue, around 100 ms at most, the device may
3959 * be even still processing requests of bfq_queues served in previous
3960 * service slots. On the opposite end, the requests of the in-service
3961 * bfq_queue may be completed after the service slot of the queue
3962 * finishes.
3963 *
3964 * Anyway, unless more sophisticated solutions are used
3965 * (where possible), the sum of the sizes of the requests dispatched
3966 * during the service slot of a bfq_queue is probably the only
3967 * approximation available for the service received by the bfq_queue
3968 * during its service slot. And this sum is the quantity used in this
3969 * function to evaluate the I/O speed of a process.
3970 */
3971static bool bfq_bfqq_is_slow(struct bfq_data *bfqd, struct bfq_queue *bfqq,
3972                                 bool compensate, enum bfqq_expiration reason,
3973                                 unsigned long *delta_ms)
3974{
3975        ktime_t delta_ktime;
3976        u32 delta_usecs;
3977        bool slow = BFQQ_SEEKY(bfqq); /* if delta too short, use seekyness */
3978
3979        if (!bfq_bfqq_sync(bfqq))
3980                return false;
3981
3982        if (compensate)
3983                delta_ktime = bfqd->last_idling_start;
3984        else
3985                delta_ktime = ktime_get();
3986        delta_ktime = ktime_sub(delta_ktime, bfqd->last_budget_start);
3987        delta_usecs = ktime_to_us(delta_ktime);
3988
3989        /* don't use too short time intervals */
3990        if (delta_usecs < 1000) {
3991                if (blk_queue_nonrot(bfqd->queue))
3992                         /*
3993                          * give same worst-case guarantees as idling
3994                          * for seeky
3995                          */
3996                        *delta_ms = BFQ_MIN_TT / NSEC_PER_MSEC;
3997                else /* charge at least one seek */
3998                        *delta_ms = bfq_slice_idle / NSEC_PER_MSEC;
3999
4000                return slow;
4001        }
4002
4003        *delta_ms = delta_usecs / USEC_PER_MSEC;
4004
4005        /*
4006         * Use only long (> 20ms) intervals to filter out excessive
4007         * spikes in service rate estimation.
4008         */
4009        if (delta_usecs > 20000) {
4010                /*
4011                 * Caveat for rotational devices: processes doing I/O
4012                 * in the slower disk zones tend to be slow(er) even
4013                 * if not seeky. In this respect, the estimated peak
4014                 * rate is likely to be an average over the disk
4015                 * surface. Accordingly, to not be too harsh with
4016                 * unlucky processes, a process is deemed slow only if
4017                 * its rate has been lower than half of the estimated
4018                 * peak rate.
4019                 */
4020                slow = bfqq->entity.service < bfqd->bfq_max_budget / 2;
4021        }
4022
4023        bfq_log_bfqq(bfqd, bfqq, "bfq_bfqq_is_slow: slow %d", slow);
4024
4025        return slow;
4026}
4027
4028/*
4029 * To be deemed as soft real-time, an application must meet two
4030 * requirements. First, the application must not require an average
4031 * bandwidth higher than the approximate bandwidth required to playback or
4032 * record a compressed high-definition video.
4033 * The next function is invoked on the completion of the last request of a
4034 * batch, to compute the next-start time instant, soft_rt_next_start, such
4035 * that, if the next request of the application does not arrive before
4036 * soft_rt_next_start, then the above requirement on the bandwidth is met.
4037 *
4038 * The second requirement is that the request pattern of the application is
4039 * isochronous, i.e., that, after issuing a request or a batch of requests,
4040 * the application stops issuing new requests until all its pending requests
4041 * have been completed. After that, the application may issue a new batch,
4042 * and so on.
4043 * For this reason the next function is invoked to compute
4044 * soft_rt_next_start only for applications that meet this requirement,
4045 * whereas soft_rt_next_start is set to infinity for applications that do
4046 * not.
4047 *
4048 * Unfortunately, even a greedy (i.e., I/O-bound) application may
4049 * happen to meet, occasionally or systematically, both the above
4050 * bandwidth and isochrony requirements. This may happen at least in
4051 * the following circumstances. First, if the CPU load is high. The
4052 * application may stop issuing requests while the CPUs are busy
4053 * serving other processes, then restart, then stop again for a while,
4054 * and so on. The other circumstances are related to the storage
4055 * device: the storage device is highly loaded or reaches a low-enough
4056 * throughput with the I/O of the application (e.g., because the I/O
4057 * is random and/or the device is slow). In all these cases, the
4058 * I/O of the application may be simply slowed down enough to meet
4059 * the bandwidth and isochrony requirements. To reduce the probability
4060 * that greedy applications are deemed as soft real-time in these
4061 * corner cases, a further rule is used in the computation of
4062 * soft_rt_next_start: the return value of this function is forced to
4063 * be higher than the maximum between the following two quantities.
4064 *
4065 * (a) Current time plus: (1) the maximum time for which the arrival
4066 *     of a request is waited for when a sync queue becomes idle,
4067 *     namely bfqd->bfq_slice_idle, and (2) a few extra jiffies. We
4068 *     postpone for a moment the reason for adding a few extra
4069 *     jiffies; we get back to it after next item (b).  Lower-bounding
4070 *     the return value of this function with the current time plus
4071 *     bfqd->bfq_slice_idle tends to filter out greedy applications,
4072 *     because the latter issue their next request as soon as possible
4073 *     after the last one has been completed. In contrast, a soft
4074 *     real-time application spends some time processing data, after a
4075 *     batch of its requests has been completed.
4076 *
4077 * (b) Current value of bfqq->soft_rt_next_start. As pointed out
4078 *     above, greedy applications may happen to meet both the
4079 *     bandwidth and isochrony requirements under heavy CPU or
4080 *     storage-device load. In more detail, in these scenarios, these
4081 *     applications happen, only for limited time periods, to do I/O
4082 *     slowly enough to meet all the requirements described so far,
4083 *     including the filtering in above item (a). These slow-speed
4084 *     time intervals are usually interspersed between other time
4085 *     intervals during which these applications do I/O at a very high
4086 *     speed. Fortunately, exactly because of the high speed of the
4087 *     I/O in the high-speed intervals, the values returned by this
4088 *     function happen to be so high, near the end of any such
4089 *     high-speed interval, to be likely to fall *after* the end of
4090 *     the low-speed time interval that follows. These high values are
4091 *     stored in bfqq->soft_rt_next_start after each invocation of
4092 *     this function. As a consequence, if the last value of
4093 *     bfqq->soft_rt_next_start is constantly used to lower-bound the
4094 *     next value that this function may return, then, from the very
4095 *     beginning of a low-speed interval, bfqq->soft_rt_next_start is
4096 *     likely to be constantly kept so high that any I/O request
4097 *     issued during the low-speed interval is considered as arriving
4098 *     to soon for the application to be deemed as soft
4099 *     real-time. Then, in the high-speed interval that follows, the
4100 *     application will not be deemed as soft real-time, just because
4101 *     it will do I/O at a high speed. And so on.
4102 *
4103 * Getting back to the filtering in item (a), in the following two
4104 * cases this filtering might be easily passed by a greedy
4105 * application, if the reference quantity was just
4106 * bfqd->bfq_slice_idle:
4107 * 1) HZ is so low that the duration of a jiffy is comparable to or
4108 *    higher than bfqd->bfq_slice_idle. This happens, e.g., on slow
4109 *    devices with HZ=100. The time granularity may be so coarse
4110 *    that the approximation, in jiffies, of bfqd->bfq_slice_idle
4111 *    is rather lower than the exact value.
4112 * 2) jiffies, instead of increasing at a constant rate, may stop increasing
4113 *    for a while, then suddenly 'jump' by several units to recover the lost
4114 *    increments. This seems to happen, e.g., inside virtual machines.
4115 * To address this issue, in the filtering in (a) we do not use as a
4116 * reference time interval just bfqd->bfq_slice_idle, but
4117 * bfqd->bfq_slice_idle plus a few jiffies. In particular, we add the
4118 * minimum number of jiffies for which the filter seems to be quite
4119 * precise also in embedded systems and KVM/QEMU virtual machines.
4120 */
4121static unsigned long bfq_bfqq_softrt_next_start(struct bfq_data *bfqd,
4122                                                struct bfq_queue *bfqq)
4123{
4124        return max3(bfqq->soft_rt_next_start,
4125                    bfqq->last_idle_bklogged +
4126                    HZ * bfqq->service_from_backlogged /
4127                    bfqd->bfq_wr_max_softrt_rate,
4128                    jiffies + nsecs_to_jiffies(bfqq->bfqd->bfq_slice_idle) + 4);
4129}
4130
4131/**
4132 * bfq_bfqq_expire - expire a queue.
4133 * @bfqd: device owning the queue.
4134 * @bfqq: the queue to expire.
4135 * @compensate: if true, compensate for the time spent idling.
4136 * @reason: the reason causing the expiration.
4137 *
4138 * If the process associated with bfqq does slow I/O (e.g., because it
4139 * issues random requests), we charge bfqq with the time it has been
4140 * in service instead of the service it has received (see
4141 * bfq_bfqq_charge_time for details on how this goal is achieved). As
4142 * a consequence, bfqq will typically get higher timestamps upon
4143 * reactivation, and hence it will be rescheduled as if it had
4144 * received more service than what it has actually received. In the
4145 * end, bfqq receives less service in proportion to how slowly its
4146 * associated process consumes its budgets (and hence how seriously it
4147 * tends to lower the throughput). In addition, this time-charging
4148 * strategy guarantees time fairness among slow processes. In
4149 * contrast, if the process associated with bfqq is not slow, we
4150 * charge bfqq exactly with the service it has received.
4151 *
4152 * Charging time to the first type of queues and the exact service to
4153 * the other has the effect of using the WF2Q+ policy to schedule the
4154 * former on a timeslice basis, without violating service domain
4155 * guarantees among the latter.
4156 */
4157void bfq_bfqq_expire(struct bfq_data *bfqd,
4158                     struct bfq_queue *bfqq,
4159                     bool compensate,
4160                     enum bfqq_expiration reason)
4161{
4162        bool slow;
4163        unsigned long delta = 0;
4164        struct bfq_entity *entity = &bfqq->entity;
4165
4166        /*
4167         * Check whether the process is slow (see bfq_bfqq_is_slow).
4168         */
4169        slow = bfq_bfqq_is_slow(bfqd, bfqq, compensate, reason, &delta);
4170
4171        /*
4172         * As above explained, charge slow (typically seeky) and
4173         * timed-out queues with the time and not the service
4174         * received, to favor sequential workloads.
4175         *
4176         * Processes doing I/O in the slower disk zones will tend to
4177         * be slow(er) even if not seeky. Therefore, since the
4178         * estimated peak rate is actually an average over the disk
4179         * surface, these processes may timeout just for bad luck. To
4180         * avoid punishing them, do not charge time to processes that
4181         * succeeded in consuming at least 2/3 of their budget. This
4182         * allows BFQ to preserve enough elasticity to still perform
4183         * bandwidth, and not time, distribution with little unlucky
4184         * or quasi-sequential processes.
4185         */
4186        if (bfqq->wr_coeff == 1 &&
4187            (slow ||
4188             (reason == BFQQE_BUDGET_TIMEOUT &&
4189              bfq_bfqq_budget_left(bfqq) >=  entity->budget / 3)))
4190                bfq_bfqq_charge_time(bfqd, bfqq, delta);
4191
4192        if (bfqd->low_latency && bfqq->wr_coeff == 1)
4193                bfqq->last_wr_start_finish = jiffies;
4194
4195        if (bfqd->low_latency && bfqd->bfq_wr_max_softrt_rate > 0 &&
4196            RB_EMPTY_ROOT(&bfqq->sort_list)) {
4197                /*
4198                 * If we get here, and there are no outstanding
4199                 * requests, then the request pattern is isochronous
4200                 * (see the comments on the function
4201                 * bfq_bfqq_softrt_next_start()). Therefore we can
4202                 * compute soft_rt_next_start.
4203                 *
4204                 * If, instead, the queue still has outstanding
4205                 * requests, then we have to wait for the completion
4206                 * of all the outstanding requests to discover whether
4207                 * the request pattern is actually isochronous.
4208                 */
4209                if (bfqq->dispatched == 0)
4210                        bfqq->soft_rt_next_start =
4211                                bfq_bfqq_softrt_next_start(bfqd, bfqq);
4212                else if (bfqq->dispatched > 0) {
4213                        /*
4214                         * Schedule an update of soft_rt_next_start to when
4215                         * the task may be discovered to be isochronous.
4216                         */
4217                        bfq_mark_bfqq_softrt_update(bfqq);
4218                }
4219        }
4220
4221        bfq_log_bfqq(bfqd, bfqq,
4222                "expire (%d, slow %d, num_disp %d, short_ttime %d)", reason,
4223                slow, bfqq->dispatched, bfq_bfqq_has_short_ttime(bfqq));
4224
4225        /*
4226         * bfqq expired, so no total service time needs to be computed
4227         * any longer: reset state machine for measuring total service
4228         * times.
4229         */
4230        bfqd->rqs_injected = bfqd->wait_dispatch = false;
4231        bfqd->waited_rq = NULL;
4232
4233        /*
4234         * Increase, decrease or leave budget unchanged according to
4235         * reason.
4236         */
4237        __bfq_bfqq_recalc_budget(bfqd, bfqq, reason);
4238        if (__bfq_bfqq_expire(bfqd, bfqq, reason))
4239                /* bfqq is gone, no more actions on it */
4240                return;
4241
4242        /* mark bfqq as waiting a request only if a bic still points to it */
4243        if (!bfq_bfqq_busy(bfqq) &&
4244            reason != BFQQE_BUDGET_TIMEOUT &&
4245            reason != BFQQE_BUDGET_EXHAUSTED) {
4246                bfq_mark_bfqq_non_blocking_wait_rq(bfqq);
4247                /*
4248                 * Not setting service to 0, because, if the next rq
4249                 * arrives in time, the queue will go on receiving
4250                 * service with this same budget (as if it never expired)
4251                 */
4252        } else
4253                entity->service = 0;
4254
4255        /*
4256         * Reset the received-service counter for every parent entity.
4257         * Differently from what happens with bfqq->entity.service,
4258         * the resetting of this counter never needs to be postponed
4259         * for parent entities. In fact, in case bfqq may have a
4260         * chance to go on being served using the last, partially
4261         * consumed budget, bfqq->entity.service needs to be kept,
4262         * because if bfqq then actually goes on being served using
4263         * the same budget, the last value of bfqq->entity.service is
4264         * needed to properly decrement bfqq->entity.budget by the
4265         * portion already consumed. In contrast, it is not necessary
4266         * to keep entity->service for parent entities too, because
4267         * the bubble up of the new value of bfqq->entity.budget will
4268         * make sure that the budgets of parent entities are correct,
4269         * even in case bfqq and thus parent entities go on receiving
4270         * service with the same budget.
4271         */
4272        entity = entity->parent;
4273        for_each_entity(entity)
4274                entity->service = 0;
4275}
4276
4277/*
4278 * Budget timeout is not implemented through a dedicated timer, but
4279 * just checked on request arrivals and completions, as well as on
4280 * idle timer expirations.
4281 */
4282static bool bfq_bfqq_budget_timeout(struct bfq_queue *bfqq)
4283{
4284        return time_is_before_eq_jiffies(bfqq->budget_timeout);
4285}
4286
4287/*
4288 * If we expire a queue that is actively waiting (i.e., with the
4289 * device idled) for the arrival of a new request, then we may incur
4290 * the timestamp misalignment problem described in the body of the
4291 * function __bfq_activate_entity. Hence we return true only if this
4292 * condition does not hold, or if the queue is slow enough to deserve
4293 * only to be kicked off for preserving a high throughput.
4294 */
4295static bool bfq_may_expire_for_budg_timeout(struct bfq_queue *bfqq)
4296{
4297        bfq_log_bfqq(bfqq->bfqd, bfqq,
4298                "may_budget_timeout: wait_request %d left %d timeout %d",
4299                bfq_bfqq_wait_request(bfqq),
4300                        bfq_bfqq_budget_left(bfqq) >=  bfqq->entity.budget / 3,
4301                bfq_bfqq_budget_timeout(bfqq));
4302
4303        return (!bfq_bfqq_wait_request(bfqq) ||
4304                bfq_bfqq_budget_left(bfqq) >=  bfqq->entity.budget / 3)
4305                &&
4306                bfq_bfqq_budget_timeout(bfqq);
4307}
4308
4309static bool idling_boosts_thr_without_issues(struct bfq_data *bfqd,
4310                                             struct bfq_queue *bfqq)
4311{
4312        bool rot_without_queueing =
4313                !blk_queue_nonrot(bfqd->queue) && !bfqd->hw_tag,
4314                bfqq_sequential_and_IO_bound,
4315                idling_boosts_thr;
4316
4317        /* No point in idling for bfqq if it won't get requests any longer */
4318        if (unlikely(!bfqq_process_refs(bfqq)))
4319                return false;
4320
4321        bfqq_sequential_and_IO_bound = !BFQQ_SEEKY(bfqq) &&
4322                bfq_bfqq_IO_bound(bfqq) && bfq_bfqq_has_short_ttime(bfqq);
4323
4324        /*
4325         * The next variable takes into account the cases where idling
4326         * boosts the throughput.
4327         *
4328         * The value of the variable is computed considering, first, that
4329         * idling is virtually always beneficial for the throughput if:
4330         * (a) the device is not NCQ-capable and rotational, or
4331         * (b) regardless of the presence of NCQ, the device is rotational and
4332         *     the request pattern for bfqq is I/O-bound and sequential, or
4333         * (c) regardless of whether it is rotational, the device is
4334         *     not NCQ-capable and the request pattern for bfqq is
4335         *     I/O-bound and sequential.
4336         *
4337         * Secondly, and in contrast to the above item (b), idling an
4338         * NCQ-capable flash-based device would not boost the
4339         * throughput even with sequential I/O; rather it would lower
4340         * the throughput in proportion to how fast the device
4341         * is. Accordingly, the next variable is true if any of the
4342         * above conditions (a), (b) or (c) is true, and, in
4343         * particular, happens to be false if bfqd is an NCQ-capable
4344         * flash-based device.
4345         */
4346        idling_boosts_thr = rot_without_queueing ||
4347                ((!blk_queue_nonrot(bfqd->queue) || !bfqd->hw_tag) &&
4348                 bfqq_sequential_and_IO_bound);
4349
4350        /*
4351         * The return value of this function is equal to that of
4352         * idling_boosts_thr, unless a special case holds. In this
4353         * special case, described below, idling may cause problems to
4354         * weight-raised queues.
4355         *
4356         * When the request pool is saturated (e.g., in the presence
4357         * of write hogs), if the processes associated with
4358         * non-weight-raised queues ask for requests at a lower rate,
4359         * then processes associated with weight-raised queues have a
4360         * higher probability to get a request from the pool
4361         * immediately (or at least soon) when they need one. Thus
4362         * they have a higher probability to actually get a fraction
4363         * of the device throughput proportional to their high
4364         * weight. This is especially true with NCQ-capable drives,
4365         * which enqueue several requests in advance, and further
4366         * reorder internally-queued requests.
4367         *
4368         * For this reason, we force to false the return value if
4369         * there are weight-raised busy queues. In this case, and if
4370         * bfqq is not weight-raised, this guarantees that the device
4371         * is not idled for bfqq (if, instead, bfqq is weight-raised,
4372         * then idling will be guaranteed by another variable, see
4373         * below). Combined with the timestamping rules of BFQ (see
4374         * [1] for details), this behavior causes bfqq, and hence any
4375         * sync non-weight-raised queue, to get a lower number of
4376         * requests served, and thus to ask for a lower number of
4377         * requests from the request pool, before the busy
4378         * weight-raised queues get served again. This often mitigates
4379         * starvation problems in the presence of heavy write
4380         * workloads and NCQ, thereby guaranteeing a higher
4381         * application and system responsiveness in these hostile
4382         * scenarios.
4383         */
4384        return idling_boosts_thr &&
4385                bfqd->wr_busy_queues == 0;
4386}
4387
4388/*
4389 * For a queue that becomes empty, device idling is allowed only if
4390 * this function returns true for that queue. As a consequence, since
4391 * device idling plays a critical role for both throughput boosting
4392 * and service guarantees, the return value of this function plays a
4393 * critical role as well.
4394 *
4395 * In a nutshell, this function returns true only if idling is
4396 * beneficial for throughput or, even if detrimental for throughput,
4397 * idling is however necessary to preserve service guarantees (low
4398 * latency, desired throughput distribution, ...). In particular, on
4399 * NCQ-capable devices, this function tries to return false, so as to
4400 * help keep the drives' internal queues full, whenever this helps the
4401 * device boost the throughput without causing any service-guarantee
4402 * issue.
4403 *
4404 * Most of the issues taken into account to get the return value of
4405 * this function are not trivial. We discuss these issues in the two
4406 * functions providing the main pieces of information needed by this
4407 * function.
4408 */
4409static bool bfq_better_to_idle(struct bfq_queue *bfqq)
4410{
4411        struct bfq_data *bfqd = bfqq->bfqd;
4412        bool idling_boosts_thr_with_no_issue, idling_needed_for_service_guar;
4413
4414        /* No point in idling for bfqq if it won't get requests any longer */
4415        if (unlikely(!bfqq_process_refs(bfqq)))
4416                return false;
4417
4418        if (unlikely(bfqd->strict_guarantees))
4419                return true;
4420
4421        /*
4422         * Idling is performed only if slice_idle > 0. In addition, we
4423         * do not idle if
4424         * (a) bfqq is async
4425         * (b) bfqq is in the idle io prio class: in this case we do
4426         * not idle because we want to minimize the bandwidth that
4427         * queues in this class can steal to higher-priority queues
4428         */
4429        if (bfqd->bfq_slice_idle == 0 || !bfq_bfqq_sync(bfqq) ||
4430           bfq_class_idle(bfqq))
4431                return false;
4432
4433        idling_boosts_thr_with_no_issue =
4434                idling_boosts_thr_without_issues(bfqd, bfqq);
4435
4436        idling_needed_for_service_guar =
4437                idling_needed_for_service_guarantees(bfqd, bfqq);
4438
4439        /*
4440         * We have now the two components we need to compute the
4441         * return value of the function, which is true only if idling
4442         * either boosts the throughput (without issues), or is
4443         * necessary to preserve service guarantees.
4444         */
4445        return idling_boosts_thr_with_no_issue ||
4446                idling_needed_for_service_guar;
4447}
4448
4449/*
4450 * If the in-service queue is empty but the function bfq_better_to_idle
4451 * returns true, then:
4452 * 1) the queue must remain in service and cannot be expired, and
4453 * 2) the device must be idled to wait for the possible arrival of a new
4454 *    request for the queue.
4455 * See the comments on the function bfq_better_to_idle for the reasons
4456 * why performing device idling is the best choice to boost the throughput
4457 * and preserve service guarantees when bfq_better_to_idle itself
4458 * returns true.
4459 */
4460static bool bfq_bfqq_must_idle(struct bfq_queue *bfqq)
4461{
4462        return RB_EMPTY_ROOT(&bfqq->sort_list) && bfq_better_to_idle(bfqq);
4463}
4464
4465/*
4466 * This function chooses the queue from which to pick the next extra
4467 * I/O request to inject, if it finds a compatible queue. See the
4468 * comments on bfq_update_inject_limit() for details on the injection
4469 * mechanism, and for the definitions of the quantities mentioned
4470 * below.
4471 */
4472static struct bfq_queue *
4473bfq_choose_bfqq_for_injection(struct bfq_data *bfqd)
4474{
4475        struct bfq_queue *bfqq, *in_serv_bfqq = bfqd->in_service_queue;
4476        unsigned int limit = in_serv_bfqq->inject_limit;
4477        /*
4478         * If
4479         * - bfqq is not weight-raised and therefore does not carry
4480         *   time-critical I/O,
4481         * or
4482         * - regardless of whether bfqq is weight-raised, bfqq has
4483         *   however a long think time, during which it can absorb the
4484         *   effect of an appropriate number of extra I/O requests
4485         *   from other queues (see bfq_update_inject_limit for
4486         *   details on the computation of this number);
4487         * then injection can be performed without restrictions.
4488         */
4489        bool in_serv_always_inject = in_serv_bfqq->wr_coeff == 1 ||
4490                !bfq_bfqq_has_short_ttime(in_serv_bfqq);
4491
4492        /*
4493         * If
4494         * - the baseline total service time could not be sampled yet,
4495         *   so the inject limit happens to be still 0, and
4496         * - a lot of time has elapsed since the plugging of I/O
4497         *   dispatching started, so drive speed is being wasted
4498         *   significantly;
4499         * then temporarily raise inject limit to one request.
4500         */
4501        if (limit == 0 && in_serv_bfqq->last_serv_time_ns == 0 &&
4502            bfq_bfqq_wait_request(in_serv_bfqq) &&
4503            time_is_before_eq_jiffies(bfqd->last_idling_start_jiffies +
4504                                      bfqd->bfq_slice_idle)
4505                )
4506                limit = 1;
4507
4508        if (bfqd->rq_in_driver >= limit)
4509                return NULL;
4510
4511        /*
4512         * Linear search of the source queue for injection; but, with
4513         * a high probability, very few steps are needed to find a
4514         * candidate queue, i.e., a queue with enough budget left for
4515         * its next request. In fact:
4516         * - BFQ dynamically updates the budget of every queue so as
4517         *   to accommodate the expected backlog of the queue;
4518         * - if a queue gets all its requests dispatched as injected
4519         *   service, then the queue is removed from the active list
4520         *   (and re-added only if it gets new requests, but then it
4521         *   is assigned again enough budget for its new backlog).
4522         */
4523        list_for_each_entry(bfqq, &bfqd->active_list, bfqq_list)
4524                if (!RB_EMPTY_ROOT(&bfqq->sort_list) &&
4525                    (in_serv_always_inject || bfqq->wr_coeff > 1) &&
4526                    bfq_serv_to_charge(bfqq->next_rq, bfqq) <=
4527                    bfq_bfqq_budget_left(bfqq)) {
4528                        /*
4529                         * Allow for only one large in-flight request
4530                         * on non-rotational devices, for the
4531                         * following reason. On non-rotationl drives,
4532                         * large requests take much longer than
4533                         * smaller requests to be served. In addition,
4534                         * the drive prefers to serve large requests
4535                         * w.r.t. to small ones, if it can choose. So,
4536                         * having more than one large requests queued
4537                         * in the drive may easily make the next first
4538                         * request of the in-service queue wait for so
4539                         * long to break bfqq's service guarantees. On
4540                         * the bright side, large requests let the
4541                         * drive reach a very high throughput, even if
4542                         * there is only one in-flight large request
4543                         * at a time.
4544                         */
4545                        if (blk_queue_nonrot(bfqd->queue) &&
4546                            blk_rq_sectors(bfqq->next_rq) >=
4547                            BFQQ_SECT_THR_NONROT)
4548                                limit = min_t(unsigned int, 1, limit);
4549                        else
4550                                limit = in_serv_bfqq->inject_limit;
4551
4552                        if (bfqd->rq_in_driver < limit) {
4553                                bfqd->rqs_injected = true;
4554                                return bfqq;
4555                        }
4556                }
4557
4558        return NULL;
4559}
4560
4561/*
4562 * Select a queue for service.  If we have a current queue in service,
4563 * check whether to continue servicing it, or retrieve and set a new one.
4564 */
4565static struct bfq_queue *bfq_select_queue(struct bfq_data *bfqd)
4566{
4567        struct bfq_queue *bfqq;
4568        struct request *next_rq;
4569        enum bfqq_expiration reason = BFQQE_BUDGET_TIMEOUT;
4570
4571        bfqq = bfqd->in_service_queue;
4572        if (!bfqq)
4573                goto new_queue;
4574
4575        bfq_log_bfqq(bfqd, bfqq, "select_queue: already in-service queue");
4576
4577        /*
4578         * Do not expire bfqq for budget timeout if bfqq may be about
4579         * to enjoy device idling. The reason why, in this case, we
4580         * prevent bfqq from expiring is the same as in the comments
4581         * on the case where bfq_bfqq_must_idle() returns true, in
4582         * bfq_completed_request().
4583         */
4584        if (bfq_may_expire_for_budg_timeout(bfqq) &&
4585            !bfq_bfqq_must_idle(bfqq))
4586                goto expire;
4587
4588check_queue:
4589        /*
4590         * This loop is rarely executed more than once. Even when it
4591         * happens, it is much more convenient to re-execute this loop
4592         * than to return NULL and trigger a new dispatch to get a
4593         * request served.
4594         */
4595        next_rq = bfqq->next_rq;
4596        /*
4597         * If bfqq has requests queued and it has enough budget left to
4598         * serve them, keep the queue, otherwise expire it.
4599         */
4600        if (next_rq) {
4601                if (bfq_serv_to_charge(next_rq, bfqq) >
4602                        bfq_bfqq_budget_left(bfqq)) {
4603                        /*
4604                         * Expire the queue for budget exhaustion,
4605                         * which makes sure that the next budget is
4606                         * enough to serve the next request, even if
4607                         * it comes from the fifo expired path.
4608                         */
4609                        reason = BFQQE_BUDGET_EXHAUSTED;
4610                        goto expire;
4611                } else {
4612                        /*
4613                         * The idle timer may be pending because we may
4614                         * not disable disk idling even when a new request
4615                         * arrives.
4616                         */
4617                        if (bfq_bfqq_wait_request(bfqq)) {
4618                                /*
4619                                 * If we get here: 1) at least a new request
4620                                 * has arrived but we have not disabled the
4621                                 * timer because the request was too small,
4622                                 * 2) then the block layer has unplugged
4623                                 * the device, causing the dispatch to be
4624                                 * invoked.
4625                                 *
4626                                 * Since the device is unplugged, now the
4627                                 * requests are probably large enough to
4628                                 * provide a reasonable throughput.
4629                                 * So we disable idling.
4630                                 */
4631                                bfq_clear_bfqq_wait_request(bfqq);
4632                                hrtimer_try_to_cancel(&bfqd->idle_slice_timer);
4633                        }
4634                        goto keep_queue;
4635                }
4636        }
4637
4638        /*
4639         * No requests pending. However, if the in-service queue is idling
4640         * for a new request, or has requests waiting for a completion and
4641         * may idle after their completion, then keep it anyway.
4642         *
4643         * Yet, inject service from other queues if it boosts
4644         * throughput and is possible.
4645         */
4646        if (bfq_bfqq_wait_request(bfqq) ||
4647            (bfqq->dispatched != 0 && bfq_better_to_idle(bfqq))) {
4648                struct bfq_queue *async_bfqq =
4649                        bfqq->bic && bfqq->bic->bfqq[0] &&
4650                        bfq_bfqq_busy(bfqq->bic->bfqq[0]) &&
4651                        bfqq->bic->bfqq[0]->next_rq ?
4652                        bfqq->bic->bfqq[0] : NULL;
4653                struct bfq_queue *blocked_bfqq =
4654                        !hlist_empty(&bfqq->woken_list) ?
4655                        container_of(bfqq->woken_list.first,
4656                                     struct bfq_queue,
4657                                     woken_list_node)
4658                        : NULL;
4659
4660                /*
4661                 * The next four mutually-exclusive ifs decide
4662                 * whether to try injection, and choose the queue to
4663                 * pick an I/O request from.
4664                 *
4665                 * The first if checks whether the process associated
4666                 * with bfqq has also async I/O pending. If so, it
4667                 * injects such I/O unconditionally. Injecting async
4668                 * I/O from the same process can cause no harm to the
4669                 * process. On the contrary, it can only increase
4670                 * bandwidth and reduce latency for the process.
4671                 *
4672                 * The second if checks whether there happens to be a
4673                 * non-empty waker queue for bfqq, i.e., a queue whose
4674                 * I/O needs to be completed for bfqq to receive new
4675                 * I/O. This happens, e.g., if bfqq is associated with
4676                 * a process that does some sync. A sync generates
4677                 * extra blocking I/O, which must be completed before
4678                 * the process associated with bfqq can go on with its
4679                 * I/O. If the I/O of the waker queue is not served,
4680                 * then bfqq remains empty, and no I/O is dispatched,
4681                 * until the idle timeout fires for bfqq. This is
4682                 * likely to result in lower bandwidth and higher
4683                 * latencies for bfqq, and in a severe loss of total
4684                 * throughput. The best action to take is therefore to
4685                 * serve the waker queue as soon as possible. So do it
4686                 * (without relying on the third alternative below for
4687                 * eventually serving waker_bfqq's I/O; see the last
4688                 * paragraph for further details). This systematic
4689                 * injection of I/O from the waker queue does not
4690                 * cause any delay to bfqq's I/O. On the contrary,
4691                 * next bfqq's I/O is brought forward dramatically,
4692                 * for it is not blocked for milliseconds.
4693                 *
4694                 * The third if checks whether there is a queue woken
4695                 * by bfqq, and currently with pending I/O. Such a
4696                 * woken queue does not steal bandwidth from bfqq,
4697                 * because it remains soon without I/O if bfqq is not
4698                 * served. So there is virtually no risk of loss of
4699                 * bandwidth for bfqq if this woken queue has I/O
4700                 * dispatched while bfqq is waiting for new I/O.
4701                 *
4702                 * The fourth if checks whether bfqq is a queue for
4703                 * which it is better to avoid injection. It is so if
4704                 * bfqq delivers more throughput when served without
4705                 * any further I/O from other queues in the middle, or
4706                 * if the service times of bfqq's I/O requests both
4707                 * count more than overall throughput, and may be
4708                 * easily increased by injection (this happens if bfqq
4709                 * has a short think time). If none of these
4710                 * conditions holds, then a candidate queue for
4711                 * injection is looked for through
4712                 * bfq_choose_bfqq_for_injection(). Note that the
4713                 * latter may return NULL (for example if the inject
4714                 * limit for bfqq is currently 0).
4715                 *
4716                 * NOTE: motivation for the second alternative
4717                 *
4718                 * Thanks to the way the inject limit is updated in
4719                 * bfq_update_has_short_ttime(), it is rather likely
4720                 * that, if I/O is being plugged for bfqq and the
4721                 * waker queue has pending I/O requests that are
4722                 * blocking bfqq's I/O, then the fourth alternative
4723                 * above lets the waker queue get served before the
4724                 * I/O-plugging timeout fires. So one may deem the
4725                 * second alternative superfluous. It is not, because
4726                 * the fourth alternative may be way less effective in
4727                 * case of a synchronization. For two main
4728                 * reasons. First, throughput may be low because the
4729                 * inject limit may be too low to guarantee the same
4730                 * amount of injected I/O, from the waker queue or
4731                 * other queues, that the second alternative
4732                 * guarantees (the second alternative unconditionally
4733                 * injects a pending I/O request of the waker queue
4734                 * for each bfq_dispatch_request()). Second, with the
4735                 * fourth alternative, the duration of the plugging,
4736                 * i.e., the time before bfqq finally receives new I/O,
4737                 * may not be minimized, because the waker queue may
4738                 * happen to be served only after other queues.
4739                 */
4740                if (async_bfqq &&
4741                    icq_to_bic(async_bfqq->next_rq->elv.icq) == bfqq->bic &&
4742                    bfq_serv_to_charge(async_bfqq->next_rq, async_bfqq) <=
4743                    bfq_bfqq_budget_left(async_bfqq))
4744                        bfqq = bfqq->bic->bfqq[0];
4745                else if (bfqq->waker_bfqq &&
4746                           bfq_bfqq_busy(bfqq->waker_bfqq) &&
4747                           bfqq->waker_bfqq->next_rq &&
4748                           bfq_serv_to_charge(bfqq->waker_bfqq->next_rq,
4749                                              bfqq->waker_bfqq) <=
4750                           bfq_bfqq_budget_left(bfqq->waker_bfqq)
4751                        )
4752                        bfqq = bfqq->waker_bfqq;
4753                else if (blocked_bfqq &&
4754                           bfq_bfqq_busy(blocked_bfqq) &&
4755                           blocked_bfqq->next_rq &&
4756                           bfq_serv_to_charge(blocked_bfqq->next_rq,
4757                                              blocked_bfqq) <=
4758                           bfq_bfqq_budget_left(blocked_bfqq)
4759                        )
4760                        bfqq = blocked_bfqq;
4761                else if (!idling_boosts_thr_without_issues(bfqd, bfqq) &&
4762                         (bfqq->wr_coeff == 1 || bfqd->wr_busy_queues > 1 ||
4763                          !bfq_bfqq_has_short_ttime(bfqq)))
4764                        bfqq = bfq_choose_bfqq_for_injection(bfqd);
4765                else
4766                        bfqq = NULL;
4767
4768                goto keep_queue;
4769        }
4770
4771        reason = BFQQE_NO_MORE_REQUESTS;
4772expire:
4773        bfq_bfqq_expire(bfqd, bfqq, false, reason);
4774new_queue:
4775        bfqq = bfq_set_in_service_queue(bfqd);
4776        if (bfqq) {
4777                bfq_log_bfqq(bfqd, bfqq, "select_queue: checking new queue");
4778                goto check_queue;
4779        }
4780keep_queue:
4781        if (bfqq)
4782                bfq_log_bfqq(bfqd, bfqq, "select_queue: returned this queue");
4783        else
4784                bfq_log(bfqd, "select_queue: no queue returned");
4785
4786        return bfqq;
4787}
4788
4789static void bfq_update_wr_data(struct bfq_data *bfqd, struct bfq_queue *bfqq)
4790{
4791        struct bfq_entity *entity = &bfqq->entity;
4792
4793        if (bfqq->wr_coeff > 1) { /* queue is being weight-raised */
4794                bfq_log_bfqq(bfqd, bfqq,
4795                        "raising period dur %u/%u msec, old coeff %u, w %d(%d)",
4796                        jiffies_to_msecs(jiffies - bfqq->last_wr_start_finish),
4797                        jiffies_to_msecs(bfqq->wr_cur_max_time),
4798                        bfqq->wr_coeff,
4799                        bfqq->entity.weight, bfqq->entity.orig_weight);
4800
4801                if (entity->prio_changed)
4802                        bfq_log_bfqq(bfqd, bfqq, "WARN: pending prio change");
4803
4804                /*
4805                 * If the queue was activated in a burst, or too much
4806                 * time has elapsed from the beginning of this
4807                 * weight-raising period, then end weight raising.
4808                 */
4809                if (bfq_bfqq_in_large_burst(bfqq))
4810                        bfq_bfqq_end_wr(bfqq);
4811                else if (time_is_before_jiffies(bfqq->last_wr_start_finish +
4812                                                bfqq->wr_cur_max_time)) {
4813                        if (bfqq->wr_cur_max_time != bfqd->bfq_wr_rt_max_time ||
4814                        time_is_before_jiffies(bfqq->wr_start_at_switch_to_srt +
4815                                               bfq_wr_duration(bfqd))) {
4816                                /*
4817                                 * Either in interactive weight
4818                                 * raising, or in soft_rt weight
4819                                 * raising with the
4820                                 * interactive-weight-raising period
4821                                 * elapsed (so no switch back to
4822                                 * interactive weight raising).
4823                                 */
4824                                bfq_bfqq_end_wr(bfqq);
4825                        } else { /*
4826                                  * soft_rt finishing while still in
4827                                  * interactive period, switch back to
4828                                  * interactive weight raising
4829                                  */
4830                                switch_back_to_interactive_wr(bfqq, bfqd);
4831                                bfqq->entity.prio_changed = 1;
4832                        }
4833                }
4834                if (bfqq->wr_coeff > 1 &&
4835                    bfqq->wr_cur_max_time != bfqd->bfq_wr_rt_max_time &&
4836                    bfqq->service_from_wr > max_service_from_wr) {
4837                        /* see comments on max_service_from_wr */
4838                        bfq_bfqq_end_wr(bfqq);
4839                }
4840        }
4841        /*
4842         * To improve latency (for this or other queues), immediately
4843         * update weight both if it must be raised and if it must be
4844         * lowered. Since, entity may be on some active tree here, and
4845         * might have a pending change of its ioprio class, invoke
4846         * next function with the last parameter unset (see the
4847         * comments on the function).
4848         */
4849        if ((entity->weight > entity->orig_weight) != (bfqq->wr_coeff > 1))
4850                __bfq_entity_update_weight_prio(bfq_entity_service_tree(entity),
4851                                                entity, false);
4852}
4853
4854/*
4855 * Dispatch next request from bfqq.
4856 */
4857static struct request *bfq_dispatch_rq_from_bfqq(struct bfq_data *bfqd,
4858                                                 struct bfq_queue *bfqq)
4859{
4860        struct request *rq = bfqq->next_rq;
4861        unsigned long service_to_charge;
4862
4863        service_to_charge = bfq_serv_to_charge(rq, bfqq);
4864
4865        bfq_bfqq_served(bfqq, service_to_charge);
4866
4867        if (bfqq == bfqd->in_service_queue && bfqd->wait_dispatch) {
4868                bfqd->wait_dispatch = false;
4869                bfqd->waited_rq = rq;
4870        }
4871
4872        bfq_dispatch_remove(bfqd->queue, rq);
4873
4874        if (bfqq != bfqd->in_service_queue)
4875                goto return_rq;
4876
4877        /*
4878         * If weight raising has to terminate for bfqq, then next
4879         * function causes an immediate update of bfqq's weight,
4880         * without waiting for next activation. As a consequence, on
4881         * expiration, bfqq will be timestamped as if has never been
4882         * weight-raised during this service slot, even if it has
4883         * received part or even most of the service as a
4884         * weight-raised queue. This inflates bfqq's timestamps, which
4885         * is beneficial, as bfqq is then more willing to leave the
4886         * device immediately to possible other weight-raised queues.
4887         */
4888        bfq_update_wr_data(bfqd, bfqq);
4889
4890        /*
4891         * Expire bfqq, pretending that its budget expired, if bfqq
4892         * belongs to CLASS_IDLE and other queues are waiting for
4893         * service.
4894         */
4895        if (!(bfq_tot_busy_queues(bfqd) > 1 && bfq_class_idle(bfqq)))
4896                goto return_rq;
4897
4898        bfq_bfqq_expire(bfqd, bfqq, false, BFQQE_BUDGET_EXHAUSTED);
4899
4900return_rq:
4901        return rq;
4902}
4903
4904static bool bfq_has_work(struct blk_mq_hw_ctx *hctx)
4905{
4906        struct bfq_data *bfqd = hctx->queue->elevator->elevator_data;
4907
4908        /*
4909         * Avoiding lock: a race on bfqd->busy_queues should cause at
4910         * most a call to dispatch for nothing
4911         */
4912        return !list_empty_careful(&bfqd->dispatch) ||
4913                bfq_tot_busy_queues(bfqd) > 0;
4914}
4915
4916static struct request *__bfq_dispatch_request(struct blk_mq_hw_ctx *hctx)
4917{
4918        struct bfq_data *bfqd = hctx->queue->elevator->elevator_data;
4919        struct request *rq = NULL;
4920        struct bfq_queue *bfqq = NULL;
4921
4922        if (!list_empty(&bfqd->dispatch)) {
4923                rq = list_first_entry(&bfqd->dispatch, struct request,
4924                                      queuelist);
4925                list_del_init(&rq->queuelist);
4926
4927                bfqq = RQ_BFQQ(rq);
4928
4929                if (bfqq) {
4930                        /*
4931                         * Increment counters here, because this
4932                         * dispatch does not follow the standard
4933                         * dispatch flow (where counters are
4934                         * incremented)
4935                         */
4936                        bfqq->dispatched++;
4937
4938                        goto inc_in_driver_start_rq;
4939                }
4940
4941                /*
4942                 * We exploit the bfq_finish_requeue_request hook to
4943                 * decrement rq_in_driver, but
4944                 * bfq_finish_requeue_request will not be invoked on
4945                 * this request. So, to avoid unbalance, just start
4946                 * this request, without incrementing rq_in_driver. As
4947                 * a negative consequence, rq_in_driver is deceptively
4948                 * lower than it should be while this request is in
4949                 * service. This may cause bfq_schedule_dispatch to be
4950                 * invoked uselessly.
4951                 *
4952                 * As for implementing an exact solution, the
4953                 * bfq_finish_requeue_request hook, if defined, is
4954                 * probably invoked also on this request. So, by
4955                 * exploiting this hook, we could 1) increment
4956                 * rq_in_driver here, and 2) decrement it in
4957                 * bfq_finish_requeue_request. Such a solution would
4958                 * let the value of the counter be always accurate,
4959                 * but it would entail using an extra interface
4960                 * function. This cost seems higher than the benefit,
4961                 * being the frequency of non-elevator-private
4962                 * requests very low.
4963                 */
4964                goto start_rq;
4965        }
4966
4967        bfq_log(bfqd, "dispatch requests: %d busy queues",
4968                bfq_tot_busy_queues(bfqd));
4969
4970        if (bfq_tot_busy_queues(bfqd) == 0)
4971                goto exit;
4972
4973        /*
4974         * Force device to serve one request at a time if
4975         * strict_guarantees is true. Forcing this service scheme is
4976         * currently the ONLY way to guarantee that the request
4977         * service order enforced by the scheduler is respected by a
4978         * queueing device. Otherwise the device is free even to make
4979         * some unlucky request wait for as long as the device
4980         * wishes.
4981         *
4982         * Of course, serving one request at a time may cause loss of
4983         * throughput.
4984         */
4985        if (bfqd->strict_guarantees && bfqd->rq_in_driver > 0)
4986                goto exit;
4987
4988        bfqq = bfq_select_queue(bfqd);
4989        if (!bfqq)
4990                goto exit;
4991
4992        rq = bfq_dispatch_rq_from_bfqq(bfqd, bfqq);
4993
4994        if (rq) {
4995inc_in_driver_start_rq:
4996                bfqd->rq_in_driver++;
4997start_rq:
4998                rq->rq_flags |= RQF_STARTED;
4999        }
5000exit:
5001        return rq;
5002}
5003
5004#ifdef CONFIG_BFQ_CGROUP_DEBUG
5005static void bfq_update_dispatch_stats(struct request_queue *q,
5006                                      struct request *rq,
5007                                      struct bfq_queue *in_serv_queue,
5008                                      bool idle_timer_disabled)
5009{
5010        struct bfq_queue *bfqq = rq ? RQ_BFQQ(rq) : NULL;
5011
5012        if (!idle_timer_disabled && !bfqq)
5013                return;
5014
5015        /*
5016         * rq and bfqq are guaranteed to exist until this function
5017         * ends, for the following reasons. First, rq can be
5018         * dispatched to the device, and then can be completed and
5019         * freed, only after this function ends. Second, rq cannot be
5020         * merged (and thus freed because of a merge) any longer,
5021         * because it has already started. Thus rq cannot be freed
5022         * before this function ends, and, since rq has a reference to
5023         * bfqq, the same guarantee holds for bfqq too.
5024         *
5025         * In addition, the following queue lock guarantees that
5026         * bfqq_group(bfqq) exists as well.
5027         */
5028        spin_lock_irq(&q->queue_lock);
5029        if (idle_timer_disabled)
5030                /*
5031                 * Since the idle timer has been disabled,
5032                 * in_serv_queue contained some request when
5033                 * __bfq_dispatch_request was invoked above, which
5034                 * implies that rq was picked exactly from
5035                 * in_serv_queue. Thus in_serv_queue == bfqq, and is
5036                 * therefore guaranteed to exist because of the above
5037                 * arguments.
5038                 */
5039                bfqg_stats_update_idle_time(bfqq_group(in_serv_queue));
5040        if (bfqq) {
5041                struct bfq_group *bfqg = bfqq_group(bfqq);
5042
5043                bfqg_stats_update_avg_queue_size(bfqg);
5044                bfqg_stats_set_start_empty_time(bfqg);
5045                bfqg_stats_update_io_remove(bfqg, rq->cmd_flags);
5046        }
5047        spin_unlock_irq(&q->queue_lock);
5048}
5049#else
5050static inline void bfq_update_dispatch_stats(struct request_queue *q,
5051                                             struct request *rq,
5052                                             struct bfq_queue *in_serv_queue,
5053                                             bool idle_timer_disabled) {}
5054#endif /* CONFIG_BFQ_CGROUP_DEBUG */
5055
5056static struct request *bfq_dispatch_request(struct blk_mq_hw_ctx *hctx)
5057{
5058        struct bfq_data *bfqd = hctx->queue->elevator->elevator_data;
5059        struct request *rq;
5060        struct bfq_queue *in_serv_queue;
5061        bool waiting_rq, idle_timer_disabled;
5062
5063        spin_lock_irq(&bfqd->lock);
5064
5065        in_serv_queue = bfqd->in_service_queue;
5066        waiting_rq = in_serv_queue && bfq_bfqq_wait_request(in_serv_queue);
5067
5068        rq = __bfq_dispatch_request(hctx);
5069
5070        idle_timer_disabled =
5071                waiting_rq && !bfq_bfqq_wait_request(in_serv_queue);
5072
5073        spin_unlock_irq(&bfqd->lock);
5074
5075        bfq_update_dispatch_stats(hctx->queue, rq, in_serv_queue,
5076                                  idle_timer_disabled);
5077
5078        return rq;
5079}
5080
5081/*
5082 * Task holds one reference to the queue, dropped when task exits.  Each rq
5083 * in-flight on this queue also holds a reference, dropped when rq is freed.
5084 *
5085 * Scheduler lock must be held here. Recall not to use bfqq after calling
5086 * this function on it.
5087 */
5088void bfq_put_queue(struct bfq_queue *bfqq)
5089{
5090        struct bfq_queue *item;
5091        struct hlist_node *n;
5092        struct bfq_group *bfqg = bfqq_group(bfqq);
5093
5094        if (bfqq->bfqd)
5095                bfq_log_bfqq(bfqq->bfqd, bfqq, "put_queue: %p %d",
5096                             bfqq, bfqq->ref);
5097
5098        bfqq->ref--;
5099        if (bfqq->ref)
5100                return;
5101
5102        if (!hlist_unhashed(&bfqq->burst_list_node)) {
5103                hlist_del_init(&bfqq->burst_list_node);
5104                /*
5105                 * Decrement also burst size after the removal, if the
5106                 * process associated with bfqq is exiting, and thus
5107                 * does not contribute to the burst any longer. This
5108                 * decrement helps filter out false positives of large
5109                 * bursts, when some short-lived process (often due to
5110                 * the execution of commands by some service) happens
5111                 * to start and exit while a complex application is
5112                 * starting, and thus spawning several processes that
5113                 * do I/O (and that *must not* be treated as a large
5114                 * burst, see comments on bfq_handle_burst).
5115                 *
5116                 * In particular, the decrement is performed only if:
5117                 * 1) bfqq is not a merged queue, because, if it is,
5118                 * then this free of bfqq is not triggered by the exit
5119                 * of the process bfqq is associated with, but exactly
5120                 * by the fact that bfqq has just been merged.
5121                 * 2) burst_size is greater than 0, to handle
5122                 * unbalanced decrements. Unbalanced decrements may
5123                 * happen in te following case: bfqq is inserted into
5124                 * the current burst list--without incrementing
5125                 * bust_size--because of a split, but the current
5126                 * burst list is not the burst list bfqq belonged to
5127                 * (see comments on the case of a split in
5128                 * bfq_set_request).
5129                 */
5130                if (bfqq->bic && bfqq->bfqd->burst_size > 0)
5131                        bfqq->bfqd->burst_size--;
5132        }
5133
5134        /*
5135         * bfqq does not exist any longer, so it cannot be woken by
5136         * any other queue, and cannot wake any other queue. Then bfqq
5137         * must be removed from the woken list of its possible waker
5138         * queue, and all queues in the woken list of bfqq must stop
5139         * having a waker queue. Strictly speaking, these updates
5140         * should be performed when bfqq remains with no I/O source
5141         * attached to it, which happens before bfqq gets freed. In
5142         * particular, this happens when the last process associated
5143         * with bfqq exits or gets associated with a different
5144         * queue. However, both events lead to bfqq being freed soon,
5145         * and dangling references would come out only after bfqq gets
5146         * freed. So these updates are done here, as a simple and safe
5147         * way to handle all cases.
5148         */
5149        /* remove bfqq from woken list */
5150        if (!hlist_unhashed(&bfqq->woken_list_node))
5151                hlist_del_init(&bfqq->woken_list_node);
5152
5153        /* reset waker for all queues in woken list */
5154        hlist_for_each_entry_safe(item, n, &bfqq->woken_list,
5155                                  woken_list_node) {
5156                item->waker_bfqq = NULL;
5157                hlist_del_init(&item->woken_list_node);
5158        }
5159
5160        if (bfqq->bfqd && bfqq->bfqd->last_completed_rq_bfqq == bfqq)
5161                bfqq->bfqd->last_completed_rq_bfqq = NULL;
5162
5163        kmem_cache_free(bfq_pool, bfqq);
5164        bfqg_and_blkg_put(bfqg);
5165}
5166
5167static void bfq_put_stable_ref(struct bfq_queue *bfqq)
5168{
5169        bfqq->stable_ref--;
5170        bfq_put_queue(bfqq);
5171}
5172
5173static void bfq_put_cooperator(struct bfq_queue *bfqq)
5174{
5175        struct bfq_queue *__bfqq, *next;
5176
5177        /*
5178         * If this queue was scheduled to merge with another queue, be
5179         * sure to drop the reference taken on that queue (and others in
5180         * the merge chain). See bfq_setup_merge and bfq_merge_bfqqs.
5181         */
5182        __bfqq = bfqq->new_bfqq;
5183        while (__bfqq) {
5184                if (__bfqq == bfqq)
5185                        break;
5186                next = __bfqq->new_bfqq;
5187                bfq_put_queue(__bfqq);
5188                __bfqq = next;
5189        }
5190}
5191
5192static void bfq_exit_bfqq(struct bfq_data *bfqd, struct bfq_queue *bfqq)
5193{
5194        if (bfqq == bfqd->in_service_queue) {
5195                __bfq_bfqq_expire(bfqd, bfqq, BFQQE_BUDGET_TIMEOUT);
5196                bfq_schedule_dispatch(bfqd);
5197        }
5198
5199        bfq_log_bfqq(bfqd, bfqq, "exit_bfqq: %p, %d", bfqq, bfqq->ref);
5200
5201        bfq_put_cooperator(bfqq);
5202
5203        bfq_release_process_ref(bfqd, bfqq);
5204}
5205
5206static void bfq_exit_icq_bfqq(struct bfq_io_cq *bic, bool is_sync)
5207{
5208        struct bfq_queue *bfqq = bic_to_bfqq(bic, is_sync);
5209        struct bfq_data *bfqd;
5210
5211        if (bfqq)
5212                bfqd = bfqq->bfqd; /* NULL if scheduler already exited */
5213
5214        if (bfqq && bfqd) {
5215                unsigned long flags;
5216
5217                spin_lock_irqsave(&bfqd->lock, flags);
5218                bfqq->bic = NULL;
5219                bfq_exit_bfqq(bfqd, bfqq);
5220                bic_set_bfqq(bic, NULL, is_sync);
5221                spin_unlock_irqrestore(&bfqd->lock, flags);
5222        }
5223}
5224
5225static void bfq_exit_icq(struct io_cq *icq)
5226{
5227        struct bfq_io_cq *bic = icq_to_bic(icq);
5228
5229        if (bic->stable_merge_bfqq) {
5230                struct bfq_data *bfqd = bic->stable_merge_bfqq->bfqd;
5231
5232                /*
5233                 * bfqd is NULL if scheduler already exited, and in
5234                 * that case this is the last time bfqq is accessed.
5235                 */
5236                if (bfqd) {
5237                        unsigned long flags;
5238
5239                        spin_lock_irqsave(&bfqd->lock, flags);
5240                        bfq_put_stable_ref(bic->stable_merge_bfqq);
5241                        spin_unlock_irqrestore(&bfqd->lock, flags);
5242                } else {
5243                        bfq_put_stable_ref(bic->stable_merge_bfqq);
5244                }
5245        }
5246
5247        bfq_exit_icq_bfqq(bic, true);
5248        bfq_exit_icq_bfqq(bic, false);
5249}
5250
5251/*
5252 * Update the entity prio values; note that the new values will not
5253 * be used until the next (re)activation.
5254 */
5255static void
5256bfq_set_next_ioprio_data(struct bfq_queue *bfqq, struct bfq_io_cq *bic)
5257{
5258        struct task_struct *tsk = current;
5259        int ioprio_class;
5260        struct bfq_data *bfqd = bfqq->bfqd;
5261
5262        if (!bfqd)
5263                return;
5264
5265        ioprio_class = IOPRIO_PRIO_CLASS(bic->ioprio);
5266        switch (ioprio_class) {
5267        default:
5268                pr_err("bdi %s: bfq: bad prio class %d\n",
5269                                bdi_dev_name(bfqq->bfqd->queue->backing_dev_info),
5270                                ioprio_class);
5271                fallthrough;
5272        case IOPRIO_CLASS_NONE:
5273                /*
5274                 * No prio set, inherit CPU scheduling settings.
5275                 */
5276                bfqq->new_ioprio = task_nice_ioprio(tsk);
5277                bfqq->new_ioprio_class = task_nice_ioclass(tsk);
5278                break;
5279        case IOPRIO_CLASS_RT:
5280                bfqq->new_ioprio = IOPRIO_PRIO_DATA(bic->ioprio);
5281                bfqq->new_ioprio_class = IOPRIO_CLASS_RT;
5282                break;
5283        case IOPRIO_CLASS_BE:
5284                bfqq->new_ioprio = IOPRIO_PRIO_DATA(bic->ioprio);
5285                bfqq->new_ioprio_class = IOPRIO_CLASS_BE;
5286                break;
5287        case IOPRIO_CLASS_IDLE:
5288                bfqq->new_ioprio_class = IOPRIO_CLASS_IDLE;
5289                bfqq->new_ioprio = 7;
5290                break;
5291        }
5292
5293        if (bfqq->new_ioprio >= IOPRIO_BE_NR) {
5294                pr_crit("bfq_set_next_ioprio_data: new_ioprio %d\n",
5295                        bfqq->new_ioprio);
5296                bfqq->new_ioprio = IOPRIO_BE_NR;
5297        }
5298
5299        bfqq->entity.new_weight = bfq_ioprio_to_weight(bfqq->new_ioprio);
5300        bfq_log_bfqq(bfqd, bfqq, "new_ioprio %d new_weight %d",
5301                     bfqq->new_ioprio, bfqq->entity.new_weight);
5302        bfqq->entity.prio_changed = 1;
5303}
5304
5305static struct bfq_queue *bfq_get_queue(struct bfq_data *bfqd,
5306                                       struct bio *bio, bool is_sync,
5307                                       struct bfq_io_cq *bic,
5308                                       bool respawn);
5309
5310static void bfq_check_ioprio_change(struct bfq_io_cq *bic, struct bio *bio)
5311{
5312        struct bfq_data *bfqd = bic_to_bfqd(bic);
5313        struct bfq_queue *bfqq;
5314        int ioprio = bic->icq.ioc->ioprio;
5315
5316        /*
5317         * This condition may trigger on a newly created bic, be sure to
5318         * drop the lock before returning.
5319         */
5320        if (unlikely(!bfqd) || likely(bic->ioprio == ioprio))
5321                return;
5322
5323        bic->ioprio = ioprio;
5324
5325        bfqq = bic_to_bfqq(bic, false);
5326        if (bfqq) {
5327                bfq_release_process_ref(bfqd, bfqq);
5328                bfqq = bfq_get_queue(bfqd, bio, BLK_RW_ASYNC, bic, true);
5329                bic_set_bfqq(bic, bfqq, false);
5330        }
5331
5332        bfqq = bic_to_bfqq(bic, true);
5333        if (bfqq)
5334                bfq_set_next_ioprio_data(bfqq, bic);
5335}
5336
5337static void bfq_init_bfqq(struct bfq_data *bfqd, struct bfq_queue *bfqq,
5338                          struct bfq_io_cq *bic, pid_t pid, int is_sync)
5339{
5340        u64 now_ns = ktime_get_ns();
5341
5342        RB_CLEAR_NODE(&bfqq->entity.rb_node);
5343        INIT_LIST_HEAD(&bfqq->fifo);
5344        INIT_HLIST_NODE(&bfqq->burst_list_node);
5345        INIT_HLIST_NODE(&bfqq->woken_list_node);
5346        INIT_HLIST_HEAD(&bfqq->woken_list);
5347
5348        bfqq->ref = 0;
5349        bfqq->bfqd = bfqd;
5350
5351        if (bic)
5352                bfq_set_next_ioprio_data(bfqq, bic);
5353
5354        if (is_sync) {
5355                /*
5356                 * No need to mark as has_short_ttime if in
5357                 * idle_class, because no device idling is performed
5358                 * for queues in idle class
5359                 */
5360                if (!bfq_class_idle(bfqq))
5361                        /* tentatively mark as has_short_ttime */
5362                        bfq_mark_bfqq_has_short_ttime(bfqq);
5363                bfq_mark_bfqq_sync(bfqq);
5364                bfq_mark_bfqq_just_created(bfqq);
5365        } else
5366                bfq_clear_bfqq_sync(bfqq);
5367
5368        /* set end request to minus infinity from now */
5369        bfqq->ttime.last_end_request = now_ns + 1;
5370
5371        bfqq->creation_time = jiffies;
5372
5373        bfqq->io_start_time = now_ns;
5374
5375        bfq_mark_bfqq_IO_bound(bfqq);
5376
5377        bfqq->pid = pid;
5378
5379        /* Tentative initial value to trade off between thr and lat */
5380        bfqq->max_budget = (2 * bfq_max_budget(bfqd)) / 3;
5381        bfqq->budget_timeout = bfq_smallest_from_now();
5382
5383        bfqq->wr_coeff = 1;
5384        bfqq->last_wr_start_finish = jiffies;
5385        bfqq->wr_start_at_switch_to_srt = bfq_smallest_from_now();
5386        bfqq->split_time = bfq_smallest_from_now();
5387
5388        /*
5389         * To not forget the possibly high bandwidth consumed by a
5390         * process/queue in the recent past,
5391         * bfq_bfqq_softrt_next_start() returns a value at least equal
5392         * to the current value of bfqq->soft_rt_next_start (see
5393         * comments on bfq_bfqq_softrt_next_start).  Set
5394         * soft_rt_next_start to now, to mean that bfqq has consumed
5395         * no bandwidth so far.
5396         */
5397        bfqq->soft_rt_next_start = jiffies;
5398
5399        /* first request is almost certainly seeky */
5400        bfqq->seek_history = 1;
5401}
5402
5403static struct bfq_queue **bfq_async_queue_prio(struct bfq_data *bfqd,
5404                                               struct bfq_group *bfqg,
5405                                               int ioprio_class, int ioprio)
5406{
5407        switch (ioprio_class) {
5408        case IOPRIO_CLASS_RT:
5409                return &bfqg->async_bfqq[0][ioprio];
5410        case IOPRIO_CLASS_NONE:
5411                ioprio = IOPRIO_NORM;
5412                fallthrough;
5413        case IOPRIO_CLASS_BE:
5414                return &bfqg->async_bfqq[1][ioprio];
5415        case IOPRIO_CLASS_IDLE:
5416                return &bfqg->async_idle_bfqq;
5417        default:
5418                return NULL;
5419        }
5420}
5421
5422static struct bfq_queue *
5423bfq_do_early_stable_merge(struct bfq_data *bfqd, struct bfq_queue *bfqq,
5424                          struct bfq_io_cq *bic,
5425                          struct bfq_queue *last_bfqq_created)
5426{
5427        struct bfq_queue *new_bfqq =
5428                bfq_setup_merge(bfqq, last_bfqq_created);
5429
5430        if (!new_bfqq)
5431                return bfqq;
5432
5433        if (new_bfqq->bic)
5434                new_bfqq->bic->stably_merged = true;
5435        bic->stably_merged = true;
5436
5437        /*
5438         * Reusing merge functions. This implies that
5439         * bfqq->bic must be set too, for
5440         * bfq_merge_bfqqs to correctly save bfqq's
5441         * state before killing it.
5442         */
5443        bfqq->bic = bic;
5444        bfq_merge_bfqqs(bfqd, bic, bfqq, new_bfqq);
5445
5446        return new_bfqq;
5447}
5448
5449/*
5450 * Many throughput-sensitive workloads are made of several parallel
5451 * I/O flows, with all flows generated by the same application, or
5452 * more generically by the same task (e.g., system boot). The most
5453 * counterproductive action with these workloads is plugging I/O
5454 * dispatch when one of the bfq_queues associated with these flows
5455 * remains temporarily empty.
5456 *
5457 * To avoid this plugging, BFQ has been using a burst-handling
5458 * mechanism for years now. This mechanism has proven effective for
5459 * throughput, and not detrimental for service guarantees. The
5460 * following function pushes this mechanism a little bit further,
5461 * basing on the following two facts.
5462 *
5463 * First, all the I/O flows of a the same application or task
5464 * contribute to the execution/completion of that common application
5465 * or task. So the performance figures that matter are total
5466 * throughput of the flows and task-wide I/O latency.  In particular,
5467 * these flows do not need to be protected from each other, in terms
5468 * of individual bandwidth or latency.
5469 *
5470 * Second, the above fact holds regardless of the number of flows.
5471 *
5472 * Putting these two facts together, this commits merges stably the
5473 * bfq_queues associated with these I/O flows, i.e., with the
5474 * processes that generate these IO/ flows, regardless of how many the
5475 * involved processes are.
5476 *
5477 * To decide whether a set of bfq_queues is actually associated with
5478 * the I/O flows of a common application or task, and to merge these
5479 * queues stably, this function operates as follows: given a bfq_queue,
5480 * say Q2, currently being created, and the last bfq_queue, say Q1,
5481 * created before Q2, Q2 is merged stably with Q1 if
5482 * - very little time has elapsed since when Q1 was created
5483 * - Q2 has the same ioprio as Q1
5484 * - Q2 belongs to the same group as Q1
5485 *
5486 * Merging bfq_queues also reduces scheduling overhead. A fio test
5487 * with ten random readers on /dev/nullb shows a throughput boost of
5488 * 40%, with a quadcore. Since BFQ's execution time amounts to ~50% of
5489 * the total per-request processing time, the above throughput boost
5490 * implies that BFQ's overhead is reduced by more than 50%.
5491 *
5492 * This new mechanism most certainly obsoletes the current
5493 * burst-handling heuristics. We keep those heuristics for the moment.
5494 */
5495static struct bfq_queue *bfq_do_or_sched_stable_merge(struct bfq_data *bfqd,
5496                                                      struct bfq_queue *bfqq,
5497                                                      struct bfq_io_cq *bic)
5498{
5499        struct bfq_queue **source_bfqq = bfqq->entity.parent ?
5500                &bfqq->entity.parent->last_bfqq_created :
5501                &bfqd->last_bfqq_created;
5502
5503        struct bfq_queue *last_bfqq_created = *source_bfqq;
5504
5505        /*
5506         * If last_bfqq_created has not been set yet, then init it. If
5507         * it has been set already, but too long ago, then move it
5508         * forward to bfqq. Finally, move also if bfqq belongs to a
5509         * different group than last_bfqq_created, or if bfqq has a
5510         * different ioprio or ioprio_class. If none of these
5511         * conditions holds true, then try an early stable merge or
5512         * schedule a delayed stable merge.
5513         *
5514         * A delayed merge is scheduled (instead of performing an
5515         * early merge), in case bfqq might soon prove to be more
5516         * throughput-beneficial if not merged. Currently this is
5517         * possible only if bfqd is rotational with no queueing. For
5518         * such a drive, not merging bfqq is better for throughput if
5519         * bfqq happens to contain sequential I/O. So, we wait a
5520         * little bit for enough I/O to flow through bfqq. After that,
5521         * if such an I/O is sequential, then the merge is
5522         * canceled. Otherwise the merge is finally performed.
5523         */
5524        if (!last_bfqq_created ||
5525            time_before(last_bfqq_created->creation_time +
5526                        msecs_to_jiffies(bfq_activation_stable_merging),
5527                        bfqq->creation_time) ||
5528                bfqq->entity.parent != last_bfqq_created->entity.parent ||
5529                bfqq->ioprio != last_bfqq_created->ioprio ||
5530                bfqq->ioprio_class != last_bfqq_created->ioprio_class)
5531                *source_bfqq = bfqq;
5532        else if (time_after_eq(last_bfqq_created->creation_time +
5533                                 bfqd->bfq_burst_interval,
5534                                 bfqq->creation_time)) {
5535                if (likely(bfqd->nonrot_with_queueing))
5536                        /*
5537                         * With this type of drive, leaving
5538                         * bfqq alone may provide no
5539                         * throughput benefits compared with
5540                         * merging bfqq. So merge bfqq now.
5541                         */
5542                        bfqq = bfq_do_early_stable_merge(bfqd, bfqq,
5543                                                         bic,
5544                                                         last_bfqq_created);
5545                else { /* schedule tentative stable merge */
5546                        /*
5547                         * get reference on last_bfqq_created,
5548                         * to prevent it from being freed,
5549                         * until we decide whether to merge
5550                         */
5551                        last_bfqq_created->ref++;
5552                        /*
5553                         * need to keep track of stable refs, to
5554                         * compute process refs correctly
5555                         */
5556                        last_bfqq_created->stable_ref++;
5557                        /*
5558                         * Record the bfqq to merge to.
5559                         */
5560                        bic->stable_merge_bfqq = last_bfqq_created;
5561                }
5562        }
5563
5564        return bfqq;
5565}
5566
5567
5568static struct bfq_queue *bfq_get_queue(struct bfq_data *bfqd,
5569                                       struct bio *bio, bool is_sync,
5570                                       struct bfq_io_cq *bic,
5571                                       bool respawn)
5572{
5573        const int ioprio = IOPRIO_PRIO_DATA(bic->ioprio);
5574        const int ioprio_class = IOPRIO_PRIO_CLASS(bic->ioprio);
5575        struct bfq_queue **async_bfqq = NULL;
5576        struct bfq_queue *bfqq;
5577        struct bfq_group *bfqg;
5578
5579        rcu_read_lock();
5580
5581        bfqg = bfq_find_set_group(bfqd, __bio_blkcg(bio));
5582        if (!bfqg) {
5583                bfqq = &bfqd->oom_bfqq;
5584                goto out;
5585        }
5586
5587        if (!is_sync) {
5588                async_bfqq = bfq_async_queue_prio(bfqd, bfqg, ioprio_class,
5589                                                  ioprio);
5590                bfqq = *async_bfqq;
5591                if (bfqq)
5592                        goto out;
5593        }
5594
5595        bfqq = kmem_cache_alloc_node(bfq_pool,
5596                                     GFP_NOWAIT | __GFP_ZERO | __GFP_NOWARN,
5597                                     bfqd->queue->node);
5598
5599        if (bfqq) {
5600                bfq_init_bfqq(bfqd, bfqq, bic, current->pid,
5601                              is_sync);
5602                bfq_init_entity(&bfqq->entity, bfqg);
5603                bfq_log_bfqq(bfqd, bfqq, "allocated");
5604        } else {
5605                bfqq = &bfqd->oom_bfqq;
5606                bfq_log_bfqq(bfqd, bfqq, "using oom bfqq");
5607                goto out;
5608        }
5609
5610        /*
5611         * Pin the queue now that it's allocated, scheduler exit will
5612         * prune it.
5613         */
5614        if (async_bfqq) {
5615                bfqq->ref++; /*
5616                              * Extra group reference, w.r.t. sync
5617                              * queue. This extra reference is removed
5618                              * only if bfqq->bfqg disappears, to
5619                              * guarantee that this queue is not freed
5620                              * until its group goes away.
5621                              */
5622                bfq_log_bfqq(bfqd, bfqq, "get_queue, bfqq not in async: %p, %d",
5623                             bfqq, bfqq->ref);
5624                *async_bfqq = bfqq;
5625        }
5626
5627out:
5628        bfqq->ref++; /* get a process reference to this queue */
5629
5630        if (bfqq != &bfqd->oom_bfqq && is_sync && !respawn)
5631                bfqq = bfq_do_or_sched_stable_merge(bfqd, bfqq, bic);
5632
5633        rcu_read_unlock();
5634        return bfqq;
5635}
5636
5637static void bfq_update_io_thinktime(struct bfq_data *bfqd,
5638                                    struct bfq_queue *bfqq)
5639{
5640        struct bfq_ttime *ttime = &bfqq->ttime;
5641        u64 elapsed;
5642
5643        /*
5644         * We are really interested in how long it takes for the queue to
5645         * become busy when there is no outstanding IO for this queue. So
5646         * ignore cases when the bfq queue has already IO queued.
5647         */
5648        if (bfqq->dispatched || bfq_bfqq_busy(bfqq))
5649                return;
5650        elapsed = ktime_get_ns() - bfqq->ttime.last_end_request;
5651        elapsed = min_t(u64, elapsed, 2ULL * bfqd->bfq_slice_idle);
5652
5653        ttime->ttime_samples = (7*ttime->ttime_samples + 256) / 8;
5654        ttime->ttime_total = div_u64(7*ttime->ttime_total + 256*elapsed,  8);
5655        ttime->ttime_mean = div64_ul(ttime->ttime_total + 128,
5656                                     ttime->ttime_samples);
5657}
5658
5659static void
5660bfq_update_io_seektime(struct bfq_data *bfqd, struct bfq_queue *bfqq,
5661                       struct request *rq)
5662{
5663        bfqq->seek_history <<= 1;
5664        bfqq->seek_history |= BFQ_RQ_SEEKY(bfqd, bfqq->last_request_pos, rq);
5665
5666        if (bfqq->wr_coeff > 1 &&
5667            bfqq->wr_cur_max_time == bfqd->bfq_wr_rt_max_time &&
5668            BFQQ_TOTALLY_SEEKY(bfqq)) {
5669                if (time_is_before_jiffies(bfqq->wr_start_at_switch_to_srt +
5670                                           bfq_wr_duration(bfqd))) {
5671                        /*
5672                         * In soft_rt weight raising with the
5673                         * interactive-weight-raising period
5674                         * elapsed (so no switch back to
5675                         * interactive weight raising).
5676                         */
5677                        bfq_bfqq_end_wr(bfqq);
5678                } else { /*
5679                          * stopping soft_rt weight raising
5680                          * while still in interactive period,
5681                          * switch back to interactive weight
5682                          * raising
5683                          */
5684                        switch_back_to_interactive_wr(bfqq, bfqd);
5685                        bfqq->entity.prio_changed = 1;
5686                }
5687        }
5688}
5689
5690static void bfq_update_has_short_ttime(struct bfq_data *bfqd,
5691                                       struct bfq_queue *bfqq,
5692                                       struct bfq_io_cq *bic)
5693{
5694        bool has_short_ttime = true, state_changed;
5695
5696        /*
5697         * No need to update has_short_ttime if bfqq is async or in
5698         * idle io prio class, or if bfq_slice_idle is zero, because
5699         * no device idling is performed for bfqq in this case.
5700         */
5701        if (!bfq_bfqq_sync(bfqq) || bfq_class_idle(bfqq) ||
5702            bfqd->bfq_slice_idle == 0)
5703                return;
5704
5705        /* Idle window just restored, statistics are meaningless. */
5706        if (time_is_after_eq_jiffies(bfqq->split_time +
5707                                     bfqd->bfq_wr_min_idle_time))
5708                return;
5709
5710        /* Think time is infinite if no process is linked to
5711         * bfqq. Otherwise check average think time to decide whether
5712         * to mark as has_short_ttime. To this goal, compare average
5713         * think time with half the I/O-plugging timeout.
5714         */
5715        if (atomic_read(&bic->icq.ioc->active_ref) == 0 ||
5716            (bfq_sample_valid(bfqq->ttime.ttime_samples) &&
5717             bfqq->ttime.ttime_mean > bfqd->bfq_slice_idle>>1))
5718                has_short_ttime = false;
5719
5720        state_changed = has_short_ttime != bfq_bfqq_has_short_ttime(bfqq);
5721
5722        if (has_short_ttime)
5723                bfq_mark_bfqq_has_short_ttime(bfqq);
5724        else
5725                bfq_clear_bfqq_has_short_ttime(bfqq);
5726
5727        /*
5728         * Until the base value for the total service time gets
5729         * finally computed for bfqq, the inject limit does depend on
5730         * the think-time state (short|long). In particular, the limit
5731         * is 0 or 1 if the think time is deemed, respectively, as
5732         * short or long (details in the comments in
5733         * bfq_update_inject_limit()). Accordingly, the next
5734         * instructions reset the inject limit if the think-time state
5735         * has changed and the above base value is still to be
5736         * computed.
5737         *
5738         * However, the reset is performed only if more than 100 ms
5739         * have elapsed since the last update of the inject limit, or
5740         * (inclusive) if the change is from short to long think
5741         * time. The reason for this waiting is as follows.
5742         *
5743         * bfqq may have a long think time because of a
5744         * synchronization with some other queue, i.e., because the
5745         * I/O of some other queue may need to be completed for bfqq
5746         * to receive new I/O. Details in the comments on the choice
5747         * of the queue for injection in bfq_select_queue().
5748         *
5749         * As stressed in those comments, if such a synchronization is
5750         * actually in place, then, without injection on bfqq, the
5751         * blocking I/O cannot happen to served while bfqq is in
5752         * service. As a consequence, if bfqq is granted
5753         * I/O-dispatch-plugging, then bfqq remains empty, and no I/O
5754         * is dispatched, until the idle timeout fires. This is likely
5755         * to result in lower bandwidth and higher latencies for bfqq,
5756         * and in a severe loss of total throughput.
5757         *
5758         * On the opposite end, a non-zero inject limit may allow the
5759         * I/O that blocks bfqq to be executed soon, and therefore
5760         * bfqq to receive new I/O soon.
5761         *
5762         * But, if the blocking gets actually eliminated, then the
5763         * next think-time sample for bfqq may be very low. This in
5764         * turn may cause bfqq's think time to be deemed
5765         * short. Without the 100 ms barrier, this new state change
5766         * would cause the body of the next if to be executed
5767         * immediately. But this would set to 0 the inject
5768         * limit. Without injection, the blocking I/O would cause the
5769         * think time of bfqq to become long again, and therefore the
5770         * inject limit to be raised again, and so on. The only effect
5771         * of such a steady oscillation between the two think-time
5772         * states would be to prevent effective injection on bfqq.
5773         *
5774         * In contrast, if the inject limit is not reset during such a
5775         * long time interval as 100 ms, then the number of short
5776         * think time samples can grow significantly before the reset
5777         * is performed. As a consequence, the think time state can
5778         * become stable before the reset. Therefore there will be no
5779         * state change when the 100 ms elapse, and no reset of the
5780         * inject limit. The inject limit remains steadily equal to 1
5781         * both during and after the 100 ms. So injection can be
5782         * performed at all times, and throughput gets boosted.
5783         *
5784         * An inject limit equal to 1 is however in conflict, in
5785         * general, with the fact that the think time of bfqq is
5786         * short, because injection may be likely to delay bfqq's I/O
5787         * (as explained in the comments in
5788         * bfq_update_inject_limit()). But this does not happen in
5789         * this special case, because bfqq's low think time is due to
5790         * an effective handling of a synchronization, through
5791         * injection. In this special case, bfqq's I/O does not get
5792         * delayed by injection; on the contrary, bfqq's I/O is
5793         * brought forward, because it is not blocked for
5794         * milliseconds.
5795         *
5796         * In addition, serving the blocking I/O much sooner, and much
5797         * more frequently than once per I/O-plugging timeout, makes