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