1 // SPDX-License-Identifier: GPL-2.0-or-later
16  * BFQ is a proportional-share I/O scheduler, with some extra
17  * low-latency capabilities. BFQ also supports full hierarchical
20  * limitations can be found in Documentation/block/bfq-iosched.rst.
22  * BFQ is a proportional-share storage-I/O scheduling algorithm based
23  * on the slice-by-slice service scheme of CFQ. But BFQ assigns
25  * time slices. The device is not granted to the in-service process
31  * B-WF2Q+, to schedule processes according to their budgets. More
33  * process/queue is assigned a user-configurable weight, and B-WF2Q+
36  * B-WF2Q+, BFQ can afford to assign high budgets to I/O-bound
38  * and yet guarantee a low latency to interactive and soft real-time
41  * In particular, to provide these low-latency guarantees, BFQ
42  * explicitly privileges the I/O of two classes of time-sensitive
43  * applications: interactive and soft real-time. In more detail, BFQ
50  * real-time application. For brevity, in these cases, the queue is
51  * said to be interactive or soft real-time. In both cases, BFQ
52  * privileges the service of the queue, over that of non-interactive
53  * and non-soft-real-time queues. This privileging is performed,
55  * call just weight-raising periods the time periods during which a
56  * queue is privileged, because deemed interactive or soft real-time.
58  * The detection of soft real-time queues/applications is described in
70  * non-empty queue stops being deemed interactive. Since a queue is
71  * weight-raised while it is deemed interactive, this maximum time
73  * weight-raising for interactive queues.
76  * preserving both a low latency and a high throughput on NCQ-capable,
77  * rotational or flash-based devices, and to get the job done quickly
78  * for applications consisting in many I/O-bound processes.
81  * the maximum-possible throughput at all times, then do switch off
82  * all low-latency heuristics for that device, by setting low_latency
91  * ones that guarantee a low latency to interactive and soft real-time
92  * applications, and a hierarchical extension based on H-WF2Q+.
94  * B-WF2Q+ is based on WF2Q+, which is described in [2], together with
95  * H-WF2Q+, while the augmented tree used here to implement B-WF2Q+
101  *     Technologies (MST-2015), May 2015.
102  *     http://algogroup.unimore.it/people/paolo/disk_sched/mst-2015.pdf
105  *     Algorithms", IEEE/ACM Transactions on Networking, 5(5):675-689,
108  * http://www.cs.cmu.edu/~hzhang/papers/TON-97-Oct.ps.gz
110  * [3] I. Stoica and H. Abdel-Wahab, "Earliest Eligible Virtual Deadline
114  * http://www.cs.berkeley.edu/~istoica/papers/eevdf-tr-95.pdf
125 #include <linux/backing-dev.h>
131 #include "blk-mq.h"
132 #include "blk-mq-sched.h"
133 #include "bfq-iosched.h"
134 #include "blk-wbt.h"
139 	__set_bit(BFQQF_##name, &(bfqq)->flags);			\
143 	__clear_bit(BFQQF_##name, &(bfqq)->flags);		\
147 	return test_bit(BFQQF_##name, &(bfqq)->flags);		\
192  * The current value of this parameter is the result of a tuning with
198  * - when the group does writes, w.r.t. to when it does reads;
199  * - when other groups do reads, w.r.t. to when they do writes.
207  * Time limit for merging (see comments in bfq_setup_cooperator). Set
212  * As can be deduced from the low time limit below, queue merging, if
234 	 (!blk_queue_nonrot(bfqd->queue) ||		\
237 #define BFQQ_SEEKY(bfqq)	(hweight32(bfqq->seek_history) > 19)
239  * Sync random I/O is likely to be confused with soft real-time I/O,
243  * as soft real-time.
245 #define BFQQ_TOTALLY_SEEKY(bfqq)	(bfqq->seek_history == -1)
247 /* Min number of samples required to perform peak-rate update */
249 /* Min observation time interval required to perform a peak-rate update (ns) */
251 /* Target observation time interval for a peak-rate update (ns) */
255  * Shift used for peak-rate fixed precision calculations.
257  * - the current shift: 16 positions
258  * - the current type used to store rate: u32
259  * - the current unit of measure for rate: [sectors/usec], or, more precisely,
262  * [1 / 2^BFQ_RATE_SHIFT, 2^(32 - BFQ_RATE_SHIFT)] sectors/usec =
263  * [1 / 2^16, 2^16] sectors/usec = [15e-6, 65536] sectors/usec =
271  * When configured for computing the duration of the weight-raising
288  * depending on whether the device is rotational or non-rotational.
293  * non-rotational device. The reference rates are not the actual peak
296  * peak-rate estimator tends to yield slightly lower values than the
301  * The reference peak rates are measured in sectors/usec, left-shifted
313  * BFQ uses the above-detailed, time-based weight-raising mechanism to
315  * following false positives: I/O-bound applications that will go on
317  * raising. These applications have basically no benefit from being
318  * weight-raised at the beginning of their I/O. On the opposite end,
319  * while being weight-raised, these applications
323  * in loss of device throughput with most flash-based storage, and may
328  * finish explaining how the duration of weight-raising for
337  * reference interactive task is the start-up of LibreOffice Writer,
342  * duration of weight-raising for at least one class of I/O-bound
343  * applications: those doing sequential or quasi-sequential I/O. An
344  * example is file copy. In fact, once started, the main I/O-bound
347  * is starting, because these I/O-bound processes will greedily devote
349  * throughput-friendly I/O operations. This is even more true if BFQ
353  * have no right to be weight-raised any longer.
355  * Basing on the last consideration, BFQ ends weight-raising for a
360  * This early ending of weight-raising reduces the amount of time
376 #define RQ_BIC(rq)		((struct bfq_io_cq *)((rq)->elv.priv[0]))
377 #define RQ_BFQQ(rq)		((rq)->elv.priv[1])
383 		return bic->bfqq[1][actuator_idx];  in bic_to_bfqq()
385 	return bic->bfqq[0][actuator_idx];  in bic_to_bfqq()
395 	struct bfq_queue *old_bfqq = bic->bfqq[is_sync][actuator_idx];  in bic_set_bfqq()
398 	 * If bfqq != NULL, then a non-stable queue merge between  in bic_set_bfqq()
399 	 * bic->bfqq and bfqq is happening here. This causes troubles  in bic_set_bfqq()
400 	 * in the following case: bic->bfqq has also been scheduled  in bic_set_bfqq()
401 	 * for a possible stable merge with bic->stable_merge_bfqq,  in bic_set_bfqq()
402 	 * and bic->stable_merge_bfqq == bfqq happens to  in bic_set_bfqq()
405 	 * bic->stable_merge_bfqq points exactly to bfqq, then bfqq  in bic_set_bfqq()
408 	 * bic->stable_merge_bfqq == bfqq.  in bic_set_bfqq()
410 	struct bfq_iocq_bfqq_data *bfqq_data = &bic->bfqq_data[actuator_idx];  in bic_set_bfqq()
413 	if (old_bfqq && old_bfqq->bic == bic)  in bic_set_bfqq()
414 		old_bfqq->bic = NULL;  in bic_set_bfqq()
417 		bic->bfqq[1][actuator_idx] = bfqq;  in bic_set_bfqq()
419 		bic->bfqq[0][actuator_idx] = bfqq;  in bic_set_bfqq()
421 	if (bfqq && bfqq_data->stable_merge_bfqq == bfqq) {  in bic_set_bfqq()
430 		bfq_put_stable_ref(bfqq_data->stable_merge_bfqq);  in bic_set_bfqq()
432 		bfqq_data->stable_merge_bfqq = NULL;  in bic_set_bfqq()
438 	return bic->icq.q->elevator->elevator_data;  in bic_to_bfqd()
442  * icq_to_bic - convert iocontext queue structure to bfq_io_cq.
447 	/* bic->icq is the first member, %NULL will convert to %NULL */  in icq_to_bic()
452  * bfq_bic_lookup - search into @ioc a bic associated to @bfqd.
460 	if (!current->io_context)  in bfq_bic_lookup()
463 	spin_lock_irqsave(&q->queue_lock, flags);  in bfq_bic_lookup()
465 	spin_unlock_irqrestore(&q->queue_lock, flags);  in bfq_bic_lookup()
471  * Scheduler run of queue, if there are requests pending and no one in the
476 	lockdep_assert_held(&bfqd->lock);  in bfq_schedule_dispatch()
478 	if (bfqd->queued != 0) {  in bfq_schedule_dispatch()
480 		blk_mq_run_hw_queues(bfqd->queue, true);  in bfq_schedule_dispatch()
484 #define bfq_class_idle(bfqq)	((bfqq)->ioprio_class == IOPRIO_CLASS_IDLE)
489  * Lifted from AS - choose which of rq1 and rq2 that is best served now.
513 	if ((rq1->cmd_flags & REQ_META) && !(rq2->cmd_flags & REQ_META))  in bfq_choose_req()
515 	else if ((rq2->cmd_flags & REQ_META) && !(rq1->cmd_flags & REQ_META))  in bfq_choose_req()
524 	back_max = bfqd->bfq_back_max * 2;  in bfq_choose_req()
532 		d1 = s1 - last;  in bfq_choose_req()
534 		d1 = (last - s1) * bfqd->bfq_back_penalty;  in bfq_choose_req()
539 		d2 = s2 - last;  in bfq_choose_req()
541 		d2 = (last - s2) * bfqd->bfq_back_penalty;  in bfq_choose_req()
549 	 * check two variables for all permutations: --> faster!  in bfq_choose_req()
572 		 * (--> only *one* back seek required),  in bfq_choose_req()
585 static bool bfqq_request_over_limit(struct bfq_queue *bfqq, int limit)  in bfqq_request_over_limit()  argument
587 	struct bfq_data *bfqd = bfqq->bfqd;  in bfqq_request_over_limit()
588 	struct bfq_entity *entity = &bfqq->entity;  in bfqq_request_over_limit()
592 	int class_idx = bfqq->ioprio_class - 1;  in bfqq_request_over_limit()
597 	if (!entity->on_st_or_in_serv)  in bfqq_request_over_limit()
601 	spin_lock_irq(&bfqd->lock);  in bfqq_request_over_limit()
603 	depth = bfqg_to_blkg(bfqq_group(bfqq))->blkcg->css.cgroup->level + 1;  in bfqq_request_over_limit()
605 		spin_unlock_irq(&bfqd->lock);  in bfqq_request_over_limit()
615 	sched_data = entity->sched_data;  in bfqq_request_over_limit()
624 		if (!entity->on_st_or_in_serv)  in bfqq_request_over_limit()
632 	for (level--; level >= 0; level--) {  in bfqq_request_over_limit()
635 			wsum = bfq_entity_service_tree(entity)->wsum;  in bfqq_request_over_limit()
648 					sched_data->service_tree[i].wsum;  in bfqq_request_over_limit()
653 		limit = DIV_ROUND_CLOSEST(limit * entity->weight, wsum);  in bfqq_request_over_limit()
654 		if (entity->allocated >= limit) {  in bfqq_request_over_limit()
655 			bfq_log_bfqq(bfqq->bfqd, bfqq,  in bfqq_request_over_limit()
656 				"too many requests: allocated %d limit %d level %d",  in bfqq_request_over_limit()
657 				entity->allocated, limit, level);  in bfqq_request_over_limit()
663 	spin_unlock_irq(&bfqd->lock);  in bfqq_request_over_limit()
669 static bool bfqq_request_over_limit(struct bfq_queue *bfqq, int limit)  in bfqq_request_over_limit()  argument
679  * Limit depths of async I/O and sync writes so as to counter both
692 	struct bfq_data *bfqd = data->q->elevator->elevator_data;  in bfq_limit_depth()
693 	struct bfq_io_cq *bic = bfq_bic_lookup(data->q);  in bfq_limit_depth()
695 	unsigned limit = data->q->nr_requests;  in bfq_limit_depth()  local
702 		depth = bfqd->word_depths[!!bfqd->wr_busy_queues][op_is_sync(opf)];  in bfq_limit_depth()
703 		limit = (limit * depth) >> bfqd->full_depth_shift;  in bfq_limit_depth()
706 	for (act_idx = 0; bic && act_idx < bfqd->num_actuators; act_idx++) {  in bfq_limit_depth()
713 		 * limit depth so that it cannot consume more  in bfq_limit_depth()
716 		if (bfqq && bfqq_request_over_limit(bfqq, limit)) {  in bfq_limit_depth()
722 		__func__, bfqd->wr_busy_queues, op_is_sync(opf), depth);  in bfq_limit_depth()
724 		data->shallow_depth = depth;  in bfq_limit_depth()
736 	p = &root->rb_node;  in bfq_rq_pos_tree_lookup()
747 		if (sector > blk_rq_pos(bfqq->next_rq))  in bfq_rq_pos_tree_lookup()
748 			n = &(*p)->rb_right;  in bfq_rq_pos_tree_lookup()
749 		else if (sector < blk_rq_pos(bfqq->next_rq))  in bfq_rq_pos_tree_lookup()
750 			n = &(*p)->rb_left;  in bfq_rq_pos_tree_lookup()
763 		bfqq ? bfqq->pid : 0);  in bfq_rq_pos_tree_lookup()
770 	return bfqq->service_from_backlogged > 0 &&  in bfq_too_late_for_merging()
771 		time_is_before_jiffies(bfqq->first_IO_time +  in bfq_too_late_for_merging()
789 	if (bfqq->pos_root) {  in bfq_pos_tree_add_move()
790 		rb_erase(&bfqq->pos_node, bfqq->pos_root);  in bfq_pos_tree_add_move()
791 		bfqq->pos_root = NULL;  in bfq_pos_tree_add_move()
795 	if (bfqq == &bfqd->oom_bfqq)  in bfq_pos_tree_add_move()
800 	 * bfq_setup_cooperator): no point in adding bfqq into the  in bfq_pos_tree_add_move()
808 	if (!bfqq->next_rq)  in bfq_pos_tree_add_move()
811 	bfqq->pos_root = &bfqq_group(bfqq)->rq_pos_tree;  in bfq_pos_tree_add_move()
812 	__bfqq = bfq_rq_pos_tree_lookup(bfqd, bfqq->pos_root,  in bfq_pos_tree_add_move()
813 			blk_rq_pos(bfqq->next_rq), &parent, &p);  in bfq_pos_tree_add_move()
815 		rb_link_node(&bfqq->pos_node, parent, p);  in bfq_pos_tree_add_move()
816 		rb_insert_color(&bfqq->pos_node, bfqq->pos_root);  in bfq_pos_tree_add_move()
818 		bfqq->pos_root = NULL;  in bfq_pos_tree_add_move()
831  * of this function is used to check whether I/O-dispatch plugging can
836  * 2) all active queues belong to the same I/O-priority class,
843  * the last two symmetry sub-conditions above would be quite complex
845  * only the following stronger three sub-conditions, for which it is
848  * 2) all active queues belong to the same I/O-priority class,
851  * support or the cgroups interface are not enabled, thus no state
858 		bfqq->weight_counter &&  in bfq_asymmetric_scenario()
859 		bfqq->weight_counter ==  in bfq_asymmetric_scenario()
861 			rb_first_cached(&bfqd->queue_weights_tree),  in bfq_asymmetric_scenario()
870 		!RB_EMPTY_ROOT(&bfqd->queue_weights_tree.rb_root) &&  in bfq_asymmetric_scenario()
871 		(bfqd->queue_weights_tree.rb_root.rb_node->rb_left ||  in bfq_asymmetric_scenario()
872 		 bfqd->queue_weights_tree.rb_root.rb_node->rb_right);  in bfq_asymmetric_scenario()
875 		(bfqd->busy_queues[0] && bfqd->busy_queues[1]) ||  in bfq_asymmetric_scenario()
876 		(bfqd->busy_queues[0] && bfqd->busy_queues[2]) ||  in bfq_asymmetric_scenario()
877 		(bfqd->busy_queues[1] && bfqd->busy_queues[2]);  in bfq_asymmetric_scenario()
881 	       || bfqd->num_groups_with_pending_reqs > 1  in bfq_asymmetric_scenario()
887  * If the weight-counter tree passed as input contains no counter for
891  * Note that weight-counter trees contain few nodes in mostly symmetric
893  * weight-counter tree for the queues may contain at most one node.
894  * This holds even if low_latency is on, because weight-raised queues
901 	struct rb_root_cached *root = &bfqq->bfqd->queue_weights_tree;  in bfq_weights_tree_add()
902 	struct bfq_entity *entity = &bfqq->entity;  in bfq_weights_tree_add()
903 	struct rb_node **new = &(root->rb_root.rb_node), *parent = NULL;  in bfq_weights_tree_add()
910 	 *      non-weight-raised, and hence change its weight, and  in bfq_weights_tree_add()
918 	if (bfqq->weight_counter)  in bfq_weights_tree_add()
927 		if (entity->weight == __counter->weight) {  in bfq_weights_tree_add()
928 			bfqq->weight_counter = __counter;  in bfq_weights_tree_add()
931 		if (entity->weight < __counter->weight)  in bfq_weights_tree_add()
932 			new = &((*new)->rb_left);  in bfq_weights_tree_add()
934 			new = &((*new)->rb_right);  in bfq_weights_tree_add()
939 	bfqq->weight_counter = kzalloc(sizeof(struct bfq_weight_counter),  in bfq_weights_tree_add()
948 	 * scenario asymmetric.  On the bright side, no unbalance will  in bfq_weights_tree_add()
952 	 * if !bfqq->weight_counter.  in bfq_weights_tree_add()
954 	if (unlikely(!bfqq->weight_counter))  in bfq_weights_tree_add()
957 	bfqq->weight_counter->weight = entity->weight;  in bfq_weights_tree_add()
958 	rb_link_node(&bfqq->weight_counter->weights_node, parent, new);  in bfq_weights_tree_add()
959 	rb_insert_color_cached(&bfqq->weight_counter->weights_node, root,  in bfq_weights_tree_add()
963 	bfqq->weight_counter->num_active++;  in bfq_weights_tree_add()
964 	bfqq->ref++;  in bfq_weights_tree_add()
977 	if (!bfqq->weight_counter)  in bfq_weights_tree_remove()
980 	root = &bfqq->bfqd->queue_weights_tree;  in bfq_weights_tree_remove()
981 	bfqq->weight_counter->num_active--;  in bfq_weights_tree_remove()
982 	if (bfqq->weight_counter->num_active > 0)  in bfq_weights_tree_remove()
985 	rb_erase_cached(&bfqq->weight_counter->weights_node, root);  in bfq_weights_tree_remove()
986 	kfree(bfqq->weight_counter);  in bfq_weights_tree_remove()
989 	bfqq->weight_counter = NULL;  in bfq_weights_tree_remove()
1006 	rq = rq_entry_fifo(bfqq->fifo.next);  in bfq_check_fifo()
1008 	if (rq == last || blk_time_get_ns() < rq->fifo_time)  in bfq_check_fifo()
1011 	bfq_log_bfqq(bfqq->bfqd, bfqq, "check_fifo: returned %p", rq);  in bfq_check_fifo()
1019 	struct rb_node *rbnext = rb_next(&last->rb_node);  in bfq_find_next_rq()
1020 	struct rb_node *rbprev = rb_prev(&last->rb_node);  in bfq_find_next_rq()
1034 		rbnext = rb_first(&bfqq->sort_list);  in bfq_find_next_rq()
1035 		if (rbnext && rbnext != &last->rb_node)  in bfq_find_next_rq()
1046 	if (bfq_bfqq_sync(bfqq) || bfqq->wr_coeff > 1 ||  in bfq_serv_to_charge()
1047 	    bfq_asymmetric_scenario(bfqq->bfqd, bfqq))  in bfq_serv_to_charge()
1054  * bfq_updated_next_req - update the queue after a new next_rq selection.
1067 	struct bfq_entity *entity = &bfqq->entity;  in bfq_updated_next_req()
1068 	struct request *next_rq = bfqq->next_rq;  in bfq_updated_next_req()
1074 	if (bfqq == bfqd->in_service_queue)  in bfq_updated_next_req()
1082 			   max_t(unsigned long, bfqq->max_budget,  in bfq_updated_next_req()
1084 			   entity->service);  in bfq_updated_next_req()
1085 	if (entity->budget != new_budget) {  in bfq_updated_next_req()
1086 		entity->budget = new_budget;  in bfq_updated_next_req()
1097 	dur = bfqd->rate_dur_prod;  in bfq_wr_duration()
1098 	do_div(dur, bfqd->peak_rate);  in bfq_wr_duration()
1101 	 * Limit duration between 3 and 25 seconds. The upper limit  in bfq_wr_duration()
1104 	 * - running in a slow PC  in bfq_wr_duration()
1105 	 * - with a virtual disk stacked on a slow low-end 5400rpm HDD  in bfq_wr_duration()
1106 	 * - serving a heavy I/O workload, such as the sequential reading  in bfq_wr_duration()
1108 	 * mplayer took 23 seconds to start, if constantly weight-raised.  in bfq_wr_duration()
1113 	 * responsiveness by allowing non-interactive applications to  in bfq_wr_duration()
1118 	 * before weight-raising finishes.  in bfq_wr_duration()
1123 /* switch back from soft real-time to interactive weight raising */
1127 	bfqq->wr_coeff = bfqd->bfq_wr_coeff;  in switch_back_to_interactive_wr()
1128 	bfqq->wr_cur_max_time = bfq_wr_duration(bfqd);  in switch_back_to_interactive_wr()
1129 	bfqq->last_wr_start_finish = bfqq->wr_start_at_switch_to_srt;  in switch_back_to_interactive_wr()
1138 	unsigned int a_idx = bfqq->actuator_idx;  in bfq_bfqq_resume_state()
1139 	struct bfq_iocq_bfqq_data *bfqq_data = &bic->bfqq_data[a_idx];  in bfq_bfqq_resume_state()
1141 	if (bfqq_data->saved_has_short_ttime)  in bfq_bfqq_resume_state()
1146 	if (bfqq_data->saved_IO_bound)  in bfq_bfqq_resume_state()
1151 	bfqq->last_serv_time_ns = bfqq_data->saved_last_serv_time_ns;  in bfq_bfqq_resume_state()
1152 	bfqq->inject_limit = bfqq_data->saved_inject_limit;  in bfq_bfqq_resume_state()
1153 	bfqq->decrease_time_jif = bfqq_data->saved_decrease_time_jif;  in bfq_bfqq_resume_state()
1155 	bfqq->entity.new_weight = bfqq_data->saved_weight;  in bfq_bfqq_resume_state()
1156 	bfqq->ttime = bfqq_data->saved_ttime;  in bfq_bfqq_resume_state()
1157 	bfqq->io_start_time = bfqq_data->saved_io_start_time;  in bfq_bfqq_resume_state()
1158 	bfqq->tot_idle_time = bfqq_data->saved_tot_idle_time;  in bfq_bfqq_resume_state()
1162 	if (bfqd->low_latency) {  in bfq_bfqq_resume_state()
1163 		old_wr_coeff = bfqq->wr_coeff;  in bfq_bfqq_resume_state()
1164 		bfqq->wr_coeff = bfqq_data->saved_wr_coeff;  in bfq_bfqq_resume_state()
1166 	bfqq->service_from_wr = bfqq_data->saved_service_from_wr;  in bfq_bfqq_resume_state()
1167 	bfqq->wr_start_at_switch_to_srt =  in bfq_bfqq_resume_state()
1168 		bfqq_data->saved_wr_start_at_switch_to_srt;  in bfq_bfqq_resume_state()
1169 	bfqq->last_wr_start_finish = bfqq_data->saved_last_wr_start_finish;  in bfq_bfqq_resume_state()
1170 	bfqq->wr_cur_max_time = bfqq_data->saved_wr_cur_max_time;  in bfq_bfqq_resume_state()
1172 	if (bfqq->wr_coeff > 1 && (bfq_bfqq_in_large_burst(bfqq) ||  in bfq_bfqq_resume_state()
1173 	    time_is_before_jiffies(bfqq->last_wr_start_finish +  in bfq_bfqq_resume_state()
1174 				   bfqq->wr_cur_max_time))) {  in bfq_bfqq_resume_state()
1175 		if (bfqq->wr_cur_max_time == bfqd->bfq_wr_rt_max_time &&  in bfq_bfqq_resume_state()
1177 		    time_is_after_eq_jiffies(bfqq->wr_start_at_switch_to_srt +  in bfq_bfqq_resume_state()
1181 			bfqq->wr_coeff = 1;  in bfq_bfqq_resume_state()
1182 			bfq_log_bfqq(bfqq->bfqd, bfqq,  in bfq_bfqq_resume_state()
1188 	bfqq->entity.prio_changed = 1;  in bfq_bfqq_resume_state()
1193 	if (old_wr_coeff == 1 && bfqq->wr_coeff > 1)  in bfq_bfqq_resume_state()
1194 		bfqd->wr_busy_queues++;  in bfq_bfqq_resume_state()
1195 	else if (old_wr_coeff > 1 && bfqq->wr_coeff == 1)  in bfq_bfqq_resume_state()
1196 		bfqd->wr_busy_queues--;  in bfq_bfqq_resume_state()
1201 	return bfqq->ref - bfqq->entity.allocated -  in bfqq_process_refs()
1202 		bfqq->entity.on_st_or_in_serv -  in bfqq_process_refs()
1203 		(bfqq->weight_counter != NULL) - bfqq->stable_ref;  in bfqq_process_refs()
1212 	hlist_for_each_entry_safe(item, n, &bfqd->burst_list, burst_list_node)  in bfq_reset_burst_list()
1213 		hlist_del_init(&item->burst_list_node);  in bfq_reset_burst_list()
1216 	 * Start the creation of a new burst list only if there is no  in bfq_reset_burst_list()
1221 		hlist_add_head(&bfqq->burst_list_node, &bfqd->burst_list);  in bfq_reset_burst_list()
1222 		bfqd->burst_size = 1;  in bfq_reset_burst_list()
1224 		bfqd->burst_size = 0;  in bfq_reset_burst_list()
1226 	bfqd->burst_parent_entity = bfqq->entity.parent;  in bfq_reset_burst_list()
1229 /* Add bfqq to the list of queues in current burst (see bfq_handle_burst) */
1233 	bfqd->burst_size++;  in bfq_add_to_burst()
1235 	if (bfqd->burst_size == bfqd->bfq_large_burst_thresh) {  in bfq_add_to_burst()
1243 		bfqd->large_burst = true;  in bfq_add_to_burst()
1249 		hlist_for_each_entry(bfqq_item, &bfqd->burst_list,  in bfq_add_to_burst()
1255 		 * From now on, and until the current burst finishes, any  in bfq_add_to_burst()
1261 		hlist_for_each_entry_safe(pos, n, &bfqd->burst_list,  in bfq_add_to_burst()
1263 			hlist_del_init(&pos->burst_list_node);  in bfq_add_to_burst()
1266 		* not increment the ref counter for bfqq, because bfqq  in bfq_add_to_burst()
1270 		hlist_add_head(&bfqq->burst_list_node, &bfqd->burst_list);  in bfq_add_to_burst()
1280  * possible, it is usually better to not grant either weight-raising
1292  * completed. As a consequence, weight-raising any of these queues,
1295  * these new queues from. If there no other active queues, then
1296  * weight-raising these new queues just lowers throughput in most
1301  * parallel I/O-bound threads. In fact, with a complex application,
1302  * several short processes may need to be executed to start-up the
1308  * weight-raise all the queues created during the burst. This is the
1318  * weight-raise queues whose creation occurs in a large burst. In
1332  * no active queues (apart from active queues that would belong to the
1345  * . if the current burst has not yet become large, and a queue Q that does
1351  *   the large-burst threshold, then
1359  *       previous sub-step), and now is not needed any more
1361  *     . the device enters a large-burst mode
1364  *   the device is in large-burst mode and shortly after the last time
1366  *   belonging to the current large burst, then Q is immediately marked
1372  *   current large burst, then the current burst is deemed as finished and:
1374  *        . the large-burst mode is reset if set
1389 	if (!hlist_unhashed(&bfqq->burst_list_node) ||  in bfq_handle_burst()
1391 	    time_is_after_eq_jiffies(bfqq->split_time +  in bfq_handle_burst()
1397 	 * a different group than the burst group, then the current  in bfq_handle_burst()
1412 	if (time_is_before_jiffies(bfqd->last_ins_in_burst +  in bfq_handle_burst()
1413 	    bfqd->bfq_burst_interval) ||  in bfq_handle_burst()
1414 	    bfqq->entity.parent != bfqd->burst_parent_entity) {  in bfq_handle_burst()
1415 		bfqd->large_burst = false;  in bfq_handle_burst()
1422 	 * last queue. So, if the current burst is also large, we can mark  in bfq_handle_burst()
1425 	if (bfqd->large_burst) {  in bfq_handle_burst()
1431 	 * If we get here, then a large-burst state has not yet been  in bfq_handle_burst()
1438 	 * At this point, bfqq either has been added to the current  in bfq_handle_burst()
1439 	 * burst or has caused the current burst to terminate and a  in bfq_handle_burst()
1445 	bfqd->last_ins_in_burst = jiffies;  in bfq_handle_burst()
1450 	struct bfq_entity *entity = &bfqq->entity;  in bfq_bfqq_budget_left()
1452 	return entity->budget - entity->service;  in bfq_bfqq_budget_left()
1456  * If enough samples have been computed, return the current max budget
1462 	if (bfqd->budgets_assigned < bfq_stats_min_budgets)  in bfq_max_budget()
1465 		return bfqd->bfq_max_budget;  in bfq_max_budget()
1469  * Return min budget, which is a fraction of the current or default
1474 	if (bfqd->budgets_assigned < bfq_stats_min_budgets)  in bfq_min_budget()
1477 		return bfqd->bfq_max_budget / 32;  in bfq_min_budget()
1483  * whether the in-service queue should be expired, by returning
1484  * true. The purpose of expiring the in-service queue is to give bfqq
1485  * the chance to possibly preempt the in-service queue, and the reason
1486  * for preempting the in-service queue is to achieve one of the two
1493  * - BFQQE_NO_MORE_REQUESTS bfqq did not enjoy any device idling
1497  * - BFQQE_TOO_IDLE bfqq did enjoy device idling, but did not issue
1498  *   a new request before the expiration of the idling-time.
1527  * before last expiration. Thus timestamps need to be back-shifted
1531  * Secondly, to allow the process to recover the hole, the in-service
1534  * in-service queue to be completed, then it may become impossible to
1535  * let the process recover the hole, even if the back-shifted
1536  * timestamps of bfqq are lower than those of the in-service queue. If
1552  * above-described special way, and signals that the in-service queue
1553  * should be expired. Timestamp back-shifting is done later in
1559  * timestamp than the in-service queue.	 That is, the next budget of
1560  * bfqq may have to be completed before the one of the in-service
1561  * queue. If this is the case, then preempting the in-service queue
1567  * the in-service queue must be preempted. To have service trees
1568  * correctly updated, the in-service queue must be expired and
1571  * mechanism may be re-designed in such a way to make it possible to
1575  * even be no in-service queue when the next function is invoked (so,
1576  * no queue to compare timestamps with). Because of these facts, the
1580  * in-service queue (unconditionally) only for queues that need to
1588 	struct bfq_entity *entity = &bfqq->entity;  in bfq_bfqq_update_budg_for_activation()
1592 	 * is some budget left, because otherwise there is no point in  in bfq_bfqq_update_budg_for_activation()
1602 		 * that timestamps need to be back-shifted (and is  in bfq_bfqq_update_budg_for_activation()
1608 		 * entity->service or entity->budget are not updated  in bfq_bfqq_update_budg_for_activation()
1613 		 * entity->budget the remaining budget on such an  in bfq_bfqq_update_budg_for_activation()
1616 		entity->budget = min_t(unsigned long,  in bfq_bfqq_update_budg_for_activation()
1618 				       bfqq->max_budget);  in bfq_bfqq_update_budg_for_activation()
1621 		 * At this point, we have used entity->service to get  in bfq_bfqq_update_budg_for_activation()
1623 		 * entity->budget). Thus we finally can, and have to,  in bfq_bfqq_update_budg_for_activation()
1624 		 * reset entity->service. The latter must be reset  in bfq_bfqq_update_budg_for_activation()
1629 		entity->service = 0;  in bfq_bfqq_update_budg_for_activation()
1637 	entity->service = 0;  in bfq_bfqq_update_budg_for_activation()
1638 	entity->budget = max_t(unsigned long, bfqq->max_budget,  in bfq_bfqq_update_budg_for_activation()
1639 			       bfq_serv_to_charge(bfqq->next_rq, bfqq));  in bfq_bfqq_update_budg_for_activation()
1650 	return jiffies - MAX_JIFFY_OFFSET;  in bfq_smallest_from_now()
1662 		/* start a weight-raising period */  in bfq_update_bfqq_wr_on_rq_arrival()
1664 			bfqq->service_from_wr = 0;  in bfq_update_bfqq_wr_on_rq_arrival()
1665 			bfqq->wr_coeff = bfqd->bfq_wr_coeff;  in bfq_update_bfqq_wr_on_rq_arrival()
1666 			bfqq->wr_cur_max_time = bfq_wr_duration(bfqd);  in bfq_update_bfqq_wr_on_rq_arrival()
1669 			 * No interactive weight raising in progress  in bfq_update_bfqq_wr_on_rq_arrival()
1672 			 * that, at the end of the soft-real-time  in bfq_update_bfqq_wr_on_rq_arrival()
1674 			 * now, no interactive weight-raising period  in bfq_update_bfqq_wr_on_rq_arrival()
1679 			bfqq->wr_start_at_switch_to_srt =  in bfq_update_bfqq_wr_on_rq_arrival()
1681 			bfqq->wr_coeff = bfqd->bfq_wr_coeff *  in bfq_update_bfqq_wr_on_rq_arrival()
1683 			bfqq->wr_cur_max_time =  in bfq_update_bfqq_wr_on_rq_arrival()
1684 				bfqd->bfq_wr_rt_max_time;  in bfq_update_bfqq_wr_on_rq_arrival()
1690 		 * scheduling-error component due to a too large  in bfq_update_bfqq_wr_on_rq_arrival()
1696 		bfqq->entity.budget = min_t(unsigned long,  in bfq_update_bfqq_wr_on_rq_arrival()
1697 					    bfqq->entity.budget,  in bfq_update_bfqq_wr_on_rq_arrival()
1701 			bfqq->wr_coeff = bfqd->bfq_wr_coeff;  in bfq_update_bfqq_wr_on_rq_arrival()
1702 			bfqq->wr_cur_max_time = bfq_wr_duration(bfqd);  in bfq_update_bfqq_wr_on_rq_arrival()
1704 			bfqq->wr_coeff = 1;  in bfq_update_bfqq_wr_on_rq_arrival()
1710 			 * the weight-raising duration for the  in bfq_update_bfqq_wr_on_rq_arrival()
1711 			 * application with the weight-raising  in bfq_update_bfqq_wr_on_rq_arrival()
1715 			 * before the weight-raising period for the  in bfq_update_bfqq_wr_on_rq_arrival()
1722 			 *    at a certain time weight-raising is  in bfq_update_bfqq_wr_on_rq_arrival()
1733 			 *    weight-raised while they are pending.  in bfq_update_bfqq_wr_on_rq_arrival()
1735 			if (bfqq->wr_cur_max_time !=  in bfq_update_bfqq_wr_on_rq_arrival()
1736 				bfqd->bfq_wr_rt_max_time) {  in bfq_update_bfqq_wr_on_rq_arrival()
1737 				bfqq->wr_start_at_switch_to_srt =  in bfq_update_bfqq_wr_on_rq_arrival()
1738 					bfqq->last_wr_start_finish;  in bfq_update_bfqq_wr_on_rq_arrival()
1740 				bfqq->wr_cur_max_time =  in bfq_update_bfqq_wr_on_rq_arrival()
1741 					bfqd->bfq_wr_rt_max_time;  in bfq_update_bfqq_wr_on_rq_arrival()
1742 				bfqq->wr_coeff = bfqd->bfq_wr_coeff *  in bfq_update_bfqq_wr_on_rq_arrival()
1745 			bfqq->last_wr_start_finish = jiffies;  in bfq_update_bfqq_wr_on_rq_arrival()
1753 	return bfqq->dispatched == 0 &&  in bfq_bfqq_idle_for_long_time()
1755 			bfqq->budget_timeout +  in bfq_bfqq_idle_for_long_time()
1756 			bfqd->bfq_wr_min_idle_time);  in bfq_bfqq_idle_for_long_time()
1762  * weight than the in-service queue.
1769 	if (bfqq->ioprio_class < in_serv_bfqq->ioprio_class)  in bfq_bfqq_higher_class_or_weight()
1772 	if (in_serv_bfqq->entity.parent == bfqq->entity.parent) {  in bfq_bfqq_higher_class_or_weight()
1773 		bfqq_weight = bfqq->entity.weight;  in bfq_bfqq_higher_class_or_weight()
1774 		in_serv_weight = in_serv_bfqq->entity.weight;  in bfq_bfqq_higher_class_or_weight()
1776 		if (bfqq->entity.parent)  in bfq_bfqq_higher_class_or_weight()
1777 			bfqq_weight = bfqq->entity.parent->weight;  in bfq_bfqq_higher_class_or_weight()
1779 			bfqq_weight = bfqq->entity.weight;  in bfq_bfqq_higher_class_or_weight()
1780 		if (in_serv_bfqq->entity.parent)  in bfq_bfqq_higher_class_or_weight()
1781 			in_serv_weight = in_serv_bfqq->entity.parent->weight;  in bfq_bfqq_higher_class_or_weight()
1783 			in_serv_weight = in_serv_bfqq->entity.weight;  in bfq_bfqq_higher_class_or_weight()
1797 	/* no search needed if one or zero ranges present */  in bfq_actuator_index()
1798 	if (bfqd->num_actuators == 1)  in bfq_actuator_index()
1802 	end = bio_end_sector(bio) - 1;  in bfq_actuator_index()
1804 	for (i = 0; i < bfqd->num_actuators; i++) {  in bfq_actuator_index()
1805 		if (end >= bfqd->sector[i] &&  in bfq_actuator_index()
1806 		    end < bfqd->sector[i] + bfqd->nr_sectors[i])  in bfq_actuator_index()
1833 			bfqq->ttime.last_end_request +  in bfq_bfqq_handle_idle_busy_switch()
1834 			bfqd->bfq_slice_idle * 3;  in bfq_bfqq_handle_idle_busy_switch()
1835 	unsigned int act_idx = bfq_actuator_index(bfqd, rq->bio);  in bfq_bfqq_handle_idle_busy_switch()
1837 		bfqq->bic || RQ_BIC(rq)->bfqq_data[act_idx].stably_merged;  in bfq_bfqq_handle_idle_busy_switch()
1840 	 * bfqq deserves to be weight-raised if:  in bfq_bfqq_handle_idle_busy_switch()
1841 	 * - it is sync,  in bfq_bfqq_handle_idle_busy_switch()
1842 	 * - it does not belong to a large burst,  in bfq_bfqq_handle_idle_busy_switch()
1843 	 * - it has been idle for enough time or is soft real-time,  in bfq_bfqq_handle_idle_busy_switch()
1844 	 * - is linked to a bfq_io_cq (it is not shared in any sense),  in bfq_bfqq_handle_idle_busy_switch()
1845 	 * - has a default weight (otherwise we assume the user wanted  in bfq_bfqq_handle_idle_busy_switch()
1849 	soft_rt = bfqd->bfq_wr_max_softrt_rate > 0 &&  in bfq_bfqq_handle_idle_busy_switch()
1852 		time_is_before_jiffies(bfqq->soft_rt_next_start) &&  in bfq_bfqq_handle_idle_busy_switch()
1853 		bfqq->dispatched == 0 &&  in bfq_bfqq_handle_idle_busy_switch()
1854 		bfqq->entity.new_weight == 40;  in bfq_bfqq_handle_idle_busy_switch()
1856 		bfqq->entity.new_weight == 40;  in bfq_bfqq_handle_idle_busy_switch()
1858 	 * Merged bfq_queues are kept out of weight-raising  in bfq_bfqq_handle_idle_busy_switch()
1859 	 * (low-latency) mechanisms. The reason is that these queues  in bfq_bfqq_handle_idle_busy_switch()
1860 	 * are usually created for non-interactive and  in bfq_bfqq_handle_idle_busy_switch()
1861 	 * non-soft-real-time tasks. Yet this is not the case for  in bfq_bfqq_handle_idle_busy_switch()
1862 	 * stably-merged queues. These queues are merged just because  in bfq_bfqq_handle_idle_busy_switch()
1864 	 * easily serve the I/O of an interactive or soft-real time  in bfq_bfqq_handle_idle_busy_switch()
1866 	 * processes. So let also stably-merged queued enjoy weight  in bfq_bfqq_handle_idle_busy_switch()
1869 	wr_or_deserves_wr = bfqd->low_latency &&  in bfq_bfqq_handle_idle_busy_switch()
1870 		(bfqq->wr_coeff > 1 ||  in bfq_bfqq_handle_idle_busy_switch()
1876 	 * may want to preempt the in-service queue.  in bfq_bfqq_handle_idle_busy_switch()
1898 		    bfqq->budget_timeout +  in bfq_bfqq_handle_idle_busy_switch()
1900 		hlist_del_init(&bfqq->burst_list_node);  in bfq_bfqq_handle_idle_busy_switch()
1906 	if (bfqd->low_latency) {  in bfq_bfqq_handle_idle_busy_switch()
1907 		if (unlikely(time_is_after_jiffies(bfqq->split_time)))  in bfq_bfqq_handle_idle_busy_switch()
1909 			bfqq->split_time =  in bfq_bfqq_handle_idle_busy_switch()
1910 				jiffies - bfqd->bfq_wr_min_idle_time - 1;  in bfq_bfqq_handle_idle_busy_switch()
1912 		if (time_is_before_jiffies(bfqq->split_time +  in bfq_bfqq_handle_idle_busy_switch()
1913 					   bfqd->bfq_wr_min_idle_time)) {  in bfq_bfqq_handle_idle_busy_switch()
1921 			if (old_wr_coeff != bfqq->wr_coeff)  in bfq_bfqq_handle_idle_busy_switch()
1922 				bfqq->entity.prio_changed = 1;  in bfq_bfqq_handle_idle_busy_switch()
1926 	bfqq->last_idle_bklogged = jiffies;  in bfq_bfqq_handle_idle_busy_switch()
1927 	bfqq->service_from_backlogged = 0;  in bfq_bfqq_handle_idle_busy_switch()
1933 	 * Expire in-service queue if preemption may be needed for  in bfq_bfqq_handle_idle_busy_switch()
1939 	 * carry time-critical I/O, then bfqq's bandwidth is less  in bfq_bfqq_handle_idle_busy_switch()
1940 	 * important than that of queues that carry time-critical I/O.  in bfq_bfqq_handle_idle_busy_switch()
1942 	 * bfqq is at least as weight-raised, i.e., at least as time  in bfq_bfqq_handle_idle_busy_switch()
1943 	 * critical, as the in-service queue.  in bfq_bfqq_handle_idle_busy_switch()
1946 	 * or has a higher weight than the in-service queue. If this  in bfq_bfqq_handle_idle_busy_switch()
1953 	 * the timestamps of both bfqq and of the in-service queue,  in bfq_bfqq_handle_idle_busy_switch()
1960 	 * timestamps of the in-service queue would need to be  in bfq_bfqq_handle_idle_busy_switch()
1966 	 * says no, then plugging is not needed any longer, either to  in bfq_bfqq_handle_idle_busy_switch()
1972 	 * request to arrive for the currently in-service queue, but  in bfq_bfqq_handle_idle_busy_switch()
1975 	if (bfqd->in_service_queue &&  in bfq_bfqq_handle_idle_busy_switch()
1977 	      bfqq->wr_coeff >= bfqd->in_service_queue->wr_coeff) ||  in bfq_bfqq_handle_idle_busy_switch()
1978 	     bfq_bfqq_higher_class_or_weight(bfqq, bfqd->in_service_queue) ||  in bfq_bfqq_handle_idle_busy_switch()
1979 	     !bfq_better_to_idle(bfqd->in_service_queue)) &&  in bfq_bfqq_handle_idle_busy_switch()
1981 		bfq_bfqq_expire(bfqd, bfqd->in_service_queue,  in bfq_bfqq_handle_idle_busy_switch()
1989 	bfqq->last_serv_time_ns = 0;  in bfq_reset_inject_limit()
1995 	bfqd->waited_rq = NULL;  in bfq_reset_inject_limit()
1999 	 * inject limit to 0 prudentially, because the service time of  in bfq_reset_inject_limit()
2005 	 * adaptive update will however raise the limit soon. This  in bfq_reset_inject_limit()
2008 	 * get new I/O enqueued---and then completed---before being  in bfq_reset_inject_limit()
2010 	 * limit-update algorithm the chance to measure the effect of  in bfq_reset_inject_limit()
2012 	 * limit accordingly.  in bfq_reset_inject_limit()
2014 	 * However, in the following special case, the inject limit is  in bfq_reset_inject_limit()
2018 	 * completed. Keeping the inject limit to 1 allows the  in bfq_reset_inject_limit()
2033 	 * times and update the inject limit accordingly (see comments  in bfq_reset_inject_limit()
2034 	 * on bfq_update_inject_limit()). So the limit is likely to be  in bfq_reset_inject_limit()
2036 	 * setting the limit to 1, we avoid that no injection ever  in bfq_reset_inject_limit()
2040 	 * limit-update algorithm and possibly raise the limit to more  in bfq_reset_inject_limit()
2044 		bfqq->inject_limit = 0;  in bfq_reset_inject_limit()
2046 		bfqq->inject_limit = 1;  in bfq_reset_inject_limit()
2048 	bfqq->decrease_time_jif = jiffies;  in bfq_reset_inject_limit()
2053 	u64 tot_io_time = now_ns - bfqq->io_start_time;  in bfq_update_io_intensity()
2055 	if (RB_EMPTY_ROOT(&bfqq->sort_list) && bfqq->dispatched == 0)  in bfq_update_io_intensity()
2056 		bfqq->tot_idle_time +=  in bfq_update_io_intensity()
2057 			now_ns - bfqq->ttime.last_end_request;  in bfq_update_io_intensity()
2066 	if (bfqq->tot_idle_time * 5 > tot_io_time)  in bfq_update_io_intensity()
2076 		bfqq->io_start_time = now_ns - (tot_io_time>>1);  in bfq_update_io_intensity()
2077 		bfqq->tot_idle_time >>= 1;  in bfq_update_io_intensity()
2103  * if it still has some in-flight I/O. In fact, in this case bfqq is actually
2105  * of some of the in-flight requests. In particular, on the first time, Q is
2111  * above three-times requirement and time limit for detection, make false
2120  * time. This implies that bfqq's inject limit is at least equal to 1
2123  * first I/O-plugging time interval for bfqq. This triggers the first
2125  * candidate waker queue is then likely to be confirmed no later than
2126  * during the next I/O-plugging interval for bfqq.
2137 	if (!bfqd->last_completed_rq_bfqq ||  in bfq_check_waker()
2138 	    bfqd->last_completed_rq_bfqq == bfqq ||  in bfq_check_waker()
2140 	    now_ns - bfqd->last_completion >= 4 * NSEC_PER_MSEC ||  in bfq_check_waker()
2141 	    bfqd->last_completed_rq_bfqq == &bfqd->oom_bfqq ||  in bfq_check_waker()
2142 	    bfqq == &bfqd->oom_bfqq)  in bfq_check_waker()
2151 	if (bfqd->last_completed_rq_bfqq !=  in bfq_check_waker()
2152 	    bfqq->tentative_waker_bfqq ||  in bfq_check_waker()
2153 	    now_ns > bfqq->waker_detection_started +  in bfq_check_waker()
2154 					128 * (u64)bfqd->bfq_slice_idle) {  in bfq_check_waker()
2158 		 * candidate waker queue from the current one.  in bfq_check_waker()
2160 		bfqq->tentative_waker_bfqq =  in bfq_check_waker()
2161 			bfqd->last_completed_rq_bfqq;  in bfq_check_waker()
2162 		bfqq->num_waker_detections = 1;  in bfq_check_waker()
2163 		bfqq->waker_detection_started = now_ns;  in bfq_check_waker()
2164 		bfq_bfqq_name(bfqq->tentative_waker_bfqq, waker_name,  in bfq_check_waker()
2168 		bfqq->num_waker_detections++;  in bfq_check_waker()
2170 	if (bfqq->num_waker_detections == 3) {  in bfq_check_waker()
2171 		bfqq->waker_bfqq = bfqd->last_completed_rq_bfqq;  in bfq_check_waker()
2172 		bfqq->tentative_waker_bfqq = NULL;  in bfq_check_waker()
2173 		bfq_bfqq_name(bfqq->waker_bfqq, waker_name,  in bfq_check_waker()
2179 		 * bfqq->waker_bfqq must be reset. To  in bfq_check_waker()
2197 		if (!hlist_unhashed(&bfqq->woken_list_node))  in bfq_check_waker()
2198 			hlist_del_init(&bfqq->woken_list_node);  in bfq_check_waker()
2199 		hlist_add_head(&bfqq->woken_list_node,  in bfq_check_waker()
2200 			       &bfqd->last_completed_rq_bfqq->woken_list);  in bfq_check_waker()
2207 	struct bfq_data *bfqd = bfqq->bfqd;  in bfq_add_request()
2209 	unsigned int old_wr_coeff = bfqq->wr_coeff;  in bfq_add_request()
2214 	bfqq->queued[rq_is_sync(rq)]++;  in bfq_add_request()
2216 	 * Updating of 'bfqd->queued' is protected by 'bfqd->lock', however, it  in bfq_add_request()
2219 	WRITE_ONCE(bfqd->queued, bfqd->queued + 1);  in bfq_add_request()
2221 	if (bfq_bfqq_sync(bfqq) && RQ_BIC(rq)->requests <= 1) {  in bfq_add_request()
2225 		 * Periodically reset inject limit, to make sure that  in bfq_add_request()
2230 		if (time_is_before_eq_jiffies(bfqq->decrease_time_jif +  in bfq_add_request()
2237 		 * update of the inject limit:  in bfq_add_request()
2238 		 * - bfqq is in service, because the total service  in bfq_add_request()
2241 		 * - this is the right occasion to compute or to  in bfq_add_request()
2243 		 *   there are actually no requests in the drive,  in bfq_add_request()
2247 		 *   quantity needed to update the inject limit, i.e.,  in bfq_add_request()
2249 		 *   injection allowed by the current value of the  in bfq_add_request()
2250 		 *   limit. It is the right occasion because injection  in bfq_add_request()
2252 		 *   hole, and there are still in-flight requests,  in bfq_add_request()
2255 		 * - the minimum interval for sampling the total  in bfq_add_request()
2256 		 *   service time and updating the inject limit has  in bfq_add_request()
2259 		if (bfqq == bfqd->in_service_queue &&  in bfq_add_request()
2260 		    (bfqd->tot_rq_in_driver == 0 ||  in bfq_add_request()
2261 		     (bfqq->last_serv_time_ns > 0 &&  in bfq_add_request()
2262 		      bfqd->rqs_injected && bfqd->tot_rq_in_driver > 0)) &&  in bfq_add_request()
2263 		    time_is_before_eq_jiffies(bfqq->decrease_time_jif +  in bfq_add_request()
2265 			bfqd->last_empty_occupied_ns = blk_time_get_ns();  in bfq_add_request()
2269 			 * wait_dispatch will cause bfqd->waited_rq to  in bfq_add_request()
2272 			bfqd->wait_dispatch = true;  in bfq_add_request()
2274 			 * If there is no I/O in service in the drive,  in bfq_add_request()
2277 			 * service time of rq. So the injection limit  in bfq_add_request()
2281 			 * injection limit updated only in the latter  in bfq_add_request()
2286 			if (bfqd->tot_rq_in_driver == 0)  in bfq_add_request()
2287 				bfqd->rqs_injected = false;  in bfq_add_request()
2294 	elv_rb_add(&bfqq->sort_list, rq);  in bfq_add_request()
2297 	 * Check if this request is a better next-serve candidate.  in bfq_add_request()
2299 	prev = bfqq->next_rq;  in bfq_add_request()
2300 	next_rq = bfq_choose_req(bfqd, bfqq->next_rq, rq, bfqd->last_position);  in bfq_add_request()
2301 	bfqq->next_rq = next_rq;  in bfq_add_request()
2307 	if (unlikely(!bfqd->nonrot_with_queueing && prev != bfqq->next_rq))  in bfq_add_request()
2314 		if (bfqd->low_latency && old_wr_coeff == 1 && !rq_is_sync(rq) &&  in bfq_add_request()
2316 				bfqq->last_wr_start_finish +  in bfq_add_request()
2317 				bfqd->bfq_wr_min_inter_arr_async)) {  in bfq_add_request()
2318 			bfqq->wr_coeff = bfqd->bfq_wr_coeff;  in bfq_add_request()
2319 			bfqq->wr_cur_max_time = bfq_wr_duration(bfqd);  in bfq_add_request()
2321 			bfqd->wr_busy_queues++;  in bfq_add_request()
2322 			bfqq->entity.prio_changed = 1;  in bfq_add_request()
2324 		if (prev != bfqq->next_rq)  in bfq_add_request()
2332 	 * . if bfqq is not going to be weight-raised, because, for  in bfq_add_request()
2333 	 *   non weight-raised queues, last_wr_start_finish stores the  in bfq_add_request()
2336 	 *   weight-raise async queues  in bfq_add_request()
2338 	 * . if bfqq is not weight-raised, because, if bfqq is now  in bfq_add_request()
2339 	 *   switching to weight-raised, then last_wr_start_finish  in bfq_add_request()
2340 	 *   stores the time when weight-raising starts  in bfq_add_request()
2343 	 *   bfqq is currently weight-raised, the weight-raising  in bfq_add_request()
2346 	 *   conditions, if bfqq is already weight-raised)  in bfq_add_request()
2349 	 * real-time, because the weight-raising period is constantly  in bfq_add_request()
2350 	 * restarted on idle-to-busy transitions for these queues, but  in bfq_add_request()
2354 	if (bfqd->low_latency &&  in bfq_add_request()
2355 		(old_wr_coeff == 1 || bfqq->wr_coeff == 1 || interactive))  in bfq_add_request()
2356 		bfqq->last_wr_start_finish = jiffies;  in bfq_add_request()
2363 	struct bfq_queue *bfqq = bfqd->bio_bfqq;  in bfq_find_rq_fmerge()
2367 		return elv_rb_find(&bfqq->sort_list, bio_end_sector(bio));  in bfq_find_rq_fmerge()
2375 		return abs(blk_rq_pos(rq) - last_pos);  in get_sdist()
2384 	struct bfq_data *bfqd = bfqq->bfqd;  in bfq_remove_request()
2387 	if (bfqq->next_rq == rq) {  in bfq_remove_request()
2388 		bfqq->next_rq = bfq_find_next_rq(bfqd, bfqq, rq);  in bfq_remove_request()
2392 	if (rq->queuelist.prev != &rq->queuelist)  in bfq_remove_request()
2393 		list_del_init(&rq->queuelist);  in bfq_remove_request()
2394 	bfqq->queued[sync]--;  in bfq_remove_request()
2396 	 * Updating of 'bfqd->queued' is protected by 'bfqd->lock', however, it  in bfq_remove_request()
2399 	WRITE_ONCE(bfqd->queued, bfqd->queued - 1);  in bfq_remove_request()
2400 	elv_rb_del(&bfqq->sort_list, rq);  in bfq_remove_request()
2403 	if (q->last_merge == rq)  in bfq_remove_request()
2404 		q->last_merge = NULL;  in bfq_remove_request()
2406 	if (RB_EMPTY_ROOT(&bfqq->sort_list)) {  in bfq_remove_request()
2407 		bfqq->next_rq = NULL;  in bfq_remove_request()
2409 		if (bfq_bfqq_busy(bfqq) && bfqq != bfqd->in_service_queue) {  in bfq_remove_request()
2413 			 * bfqq is empty, bfqq->entity.service and  in bfq_remove_request()
2414 			 * bfqq->entity.budget must contain,  in bfq_remove_request()
2420 			 * reset both bfqq->entity.service and  in bfq_remove_request()
2421 			 * bfqq->entity.budget, if bfqq has still a  in bfq_remove_request()
2424 			bfqq->entity.budget = bfqq->entity.service = 0;  in bfq_remove_request()
2428 		 * Remove queue from request-position tree as it is empty.  in bfq_remove_request()
2430 		if (bfqq->pos_root) {  in bfq_remove_request()
2431 			rb_erase(&bfqq->pos_node, bfqq->pos_root);  in bfq_remove_request()
2432 			bfqq->pos_root = NULL;  in bfq_remove_request()
2436 		if (unlikely(!bfqd->nonrot_with_queueing))  in bfq_remove_request()
2440 	if (rq->cmd_flags & REQ_META)  in bfq_remove_request()
2441 		bfqq->meta_pending--;  in bfq_remove_request()
2448 	struct bfq_data *bfqd = q->elevator->elevator_data;  in bfq_bio_merge()
2453 	 * queue_lock inside the bfqd->lock. We assume that the bic  in bfq_bio_merge()
2455 	 * bfqd->lock is taken.  in bfq_bio_merge()
2460 	spin_lock_irq(&bfqd->lock);  in bfq_bio_merge()
2464 		 * Make sure cgroup info is uptodate for current process before  in bfq_bio_merge()
2469 		bfqd->bio_bfqq = bic_to_bfqq(bic, op_is_sync(bio->bi_opf),  in bfq_bio_merge()
2472 		bfqd->bio_bfqq = NULL;  in bfq_bio_merge()
2474 	bfqd->bio_bic = bic;  in bfq_bio_merge()
2478 	spin_unlock_irq(&bfqd->lock);  in bfq_bio_merge()
2488 	struct bfq_data *bfqd = q->elevator->elevator_data;  in bfq_request_merge()
2507 	    rb_prev(&req->rb_node) &&  in bfq_request_merged()
2509 	    blk_rq_pos(container_of(rb_prev(&req->rb_node),  in bfq_request_merged()
2518 		bfqd = bfqq->bfqd;  in bfq_request_merged()
2521 		elv_rb_del(&bfqq->sort_list, req);  in bfq_request_merged()
2522 		elv_rb_add(&bfqq->sort_list, req);  in bfq_request_merged()
2525 		prev = bfqq->next_rq;  in bfq_request_merged()
2526 		next_rq = bfq_choose_req(bfqd, bfqq->next_rq, req,  in bfq_request_merged()
2527 					 bfqd->last_position);  in bfq_request_merged()
2528 		bfqq->next_rq = next_rq;  in bfq_request_merged()
2534 		if (prev != bfqq->next_rq) {  in bfq_request_merged()
2540 			if (unlikely(!bfqd->nonrot_with_queueing))  in bfq_request_merged()
2554  * on that rq is picked from the hash table q->elevator->hash, which,
2579 	    !list_empty(&rq->queuelist) && !list_empty(&next->queuelist) &&  in bfq_requests_merged()
2580 	    next->fifo_time < rq->fifo_time) {  in bfq_requests_merged()
2581 		list_del_init(&rq->queuelist);  in bfq_requests_merged()
2582 		list_replace_init(&next->queuelist, &rq->queuelist);  in bfq_requests_merged()
2583 		rq->fifo_time = next->fifo_time;  in bfq_requests_merged()
2586 	if (bfqq->next_rq == next)  in bfq_requests_merged()
2587 		bfqq->next_rq = rq;  in bfq_requests_merged()
2589 	bfqg_stats_update_io_merged(bfqq_group(bfqq), next->cmd_flags);  in bfq_requests_merged()
2592 	if (!RB_EMPTY_NODE(&next->rb_node)) {  in bfq_requests_merged()
2593 		bfq_remove_request(next->q, next);  in bfq_requests_merged()
2596 						    next->cmd_flags);  in bfq_requests_merged()
2604 	 * If bfqq has been enjoying interactive weight-raising, then  in bfq_bfqq_end_wr()
2607 	 * a soft real-time application. Such an application actually  in bfq_bfqq_end_wr()
2608 	 * exhibits a soft real-time I/O pattern after it finishes  in bfq_bfqq_end_wr()
2617 	if (bfqq->wr_cur_max_time !=  in bfq_bfqq_end_wr()
2618 	    bfqq->bfqd->bfq_wr_rt_max_time)  in bfq_bfqq_end_wr()
2619 		bfqq->soft_rt_next_start = jiffies;  in bfq_bfqq_end_wr()
2622 		bfqq->bfqd->wr_busy_queues--;  in bfq_bfqq_end_wr()
2623 	bfqq->wr_coeff = 1;  in bfq_bfqq_end_wr()
2624 	bfqq->wr_cur_max_time = 0;  in bfq_bfqq_end_wr()
2625 	bfqq->last_wr_start_finish = jiffies;  in bfq_bfqq_end_wr()
2630 	bfqq->entity.prio_changed = 1;  in bfq_bfqq_end_wr()
2638 	for (k = 0; k < bfqd->num_actuators; k++) {  in bfq_end_wr_async_queues()
2641 				if (bfqg->async_bfqq[i][j][k])  in bfq_end_wr_async_queues()
2642 					bfq_bfqq_end_wr(bfqg->async_bfqq[i][j][k]);  in bfq_end_wr_async_queues()
2643 		if (bfqg->async_idle_bfqq[k])  in bfq_end_wr_async_queues()
2644 			bfq_bfqq_end_wr(bfqg->async_idle_bfqq[k]);  in bfq_end_wr_async_queues()
2653 	spin_lock_irq(&bfqd->lock);  in bfq_end_wr()
2655 	for (i = 0; i < bfqd->num_actuators; i++) {  in bfq_end_wr()
2656 		list_for_each_entry(bfqq, &bfqd->active_list[i], bfqq_list)  in bfq_end_wr()
2659 	list_for_each_entry(bfqq, &bfqd->idle_list, bfqq_list)  in bfq_end_wr()
2663 	spin_unlock_irq(&bfqd->lock);  in bfq_end_wr()
2671 		return ((struct bio *)io_struct)->bi_iter.bi_sector;  in bfq_io_struct_pos()
2677 	return abs(bfq_io_struct_pos(io_struct, request) - sector) <=  in bfq_rq_close_to_sector()
2685 	struct rb_root *root = &bfqq_group(bfqq)->rq_pos_tree;  in bfqq_find_close()
2706 	if (bfq_rq_close_to_sector(__bfqq->next_rq, true, sector))  in bfqq_find_close()
2709 	if (blk_rq_pos(__bfqq->next_rq) < sector)  in bfqq_find_close()
2710 		node = rb_next(&__bfqq->pos_node);  in bfqq_find_close()
2712 		node = rb_prev(&__bfqq->pos_node);  in bfqq_find_close()
2717 	if (bfq_rq_close_to_sector(__bfqq->next_rq, true, sector))  in bfqq_find_close()
2750 	 * If there are no process references on the new_bfqq, then it is  in bfq_setup_merge()
2751 	 * unsafe to follow the ->new_bfqq chain as other bfqq's in the chain  in bfq_setup_merge()
2759 	while ((__bfqq = new_bfqq->new_bfqq)) {  in bfq_setup_merge()
2768 	 * If the process for the bfqq has gone away, there is no  in bfq_setup_merge()
2779 	if (new_bfqq->entity.parent != bfqq->entity.parent)  in bfq_setup_merge()
2782 	bfq_log_bfqq(bfqq->bfqd, bfqq, "scheduling merge with queue %d",  in bfq_setup_merge()
2783 		new_bfqq->pid);  in bfq_setup_merge()
2797 	 * not available any more (new_bfqq->bic == NULL).  in bfq_setup_merge()
2799 	 * Anyway, even in case new_bfqq coincides with the in-service  in bfq_setup_merge()
2800 	 * queue, redirecting requests the in-service queue is the  in bfq_setup_merge()
2801 	 * best option, as we feed the in-service queue with new  in bfq_setup_merge()
2805 	bfqq->new_bfqq = new_bfqq;  in bfq_setup_merge()
2810 	 * associated with new_bfqq. Here we increases new_bfqq->ref  in bfq_setup_merge()
2815 	new_bfqq->ref += process_refs;  in bfq_setup_merge()
2826 	    (bfqq->ioprio_class != new_bfqq->ioprio_class))  in bfq_may_be_close_cooperator()
2860 	bfqq_data->stable_merge_bfqq = NULL;  in bfq_setup_stable_merge()
2864 	/* next function will take at least one ref */  in bfq_setup_stable_merge()
2868 		bfqq_data->stably_merged = true;  in bfq_setup_stable_merge()
2869 		if (new_bfqq->bic) {  in bfq_setup_stable_merge()
2870 			unsigned int new_a_idx = new_bfqq->actuator_idx;  in bfq_setup_stable_merge()
2872 				&new_bfqq->bic->bfqq_data[new_a_idx];  in bfq_setup_stable_merge()
2874 			new_bfqq_data->stably_merged = true;  in bfq_setup_stable_merge()
2886  * Attempt to schedule a merge of bfqq with the currently in-service
2888  * NULL if no merge was scheduled, a pointer to the shared bfq_queue
2898  * WARNING: queue merging may impair fairness among non-weight raised
2902  * requests than the ones produced by its originally-associated
2910 	unsigned int a_idx = bfqq->actuator_idx;  in bfq_setup_cooperator()
2911 	struct bfq_iocq_bfqq_data *bfqq_data = &bic->bfqq_data[a_idx];  in bfq_setup_cooperator()
2914 	new_bfqq = bfqq->new_bfqq;  in bfq_setup_cooperator()
2916 		while (new_bfqq->new_bfqq)  in bfq_setup_cooperator()
2917 			new_bfqq = new_bfqq->new_bfqq;  in bfq_setup_cooperator()
2922 	 * Check delayed stable merge for rotational or non-queueing  in bfq_setup_cooperator()
2924 	 * currently merged with some other queue (i.e., bfqq->bic  in bfq_setup_cooperator()
2927 	 * merged with bic->stable_merge_bfqq. But this would be  in bfq_setup_cooperator()
2930 	if (unlikely(!bfqd->nonrot_with_queueing)) {  in bfq_setup_cooperator()
2933 		 * bic->stable_merge_bfqq may point to some queue (for  in bfq_setup_cooperator()
2937 		if (bfq_bfqq_sync(bfqq) && bfqq_data->stable_merge_bfqq &&  in bfq_setup_cooperator()
2939 		    time_is_before_jiffies(bfqq->split_time +  in bfq_setup_cooperator()
2941 		    time_is_before_jiffies(bfqq->creation_time +  in bfq_setup_cooperator()
2944 				bfqq_data->stable_merge_bfqq;  in bfq_setup_cooperator()
2970 	 * non-merged queues. This may accentuate workload  in bfq_setup_cooperator()
2989 	if (likely(bfqd->nonrot_with_queueing))  in bfq_setup_cooperator()
2999 	 * probability that two non-cooperating processes, which just  in bfq_setup_cooperator()
3006 	if (!io_struct || unlikely(bfqq == &bfqd->oom_bfqq))  in bfq_setup_cooperator()
3013 	in_service_bfqq = bfqd->in_service_queue;  in bfq_setup_cooperator()
3016 	    likely(in_service_bfqq != &bfqd->oom_bfqq) &&  in bfq_setup_cooperator()
3018 				   bfqd->in_serv_last_pos) &&  in bfq_setup_cooperator()
3019 	    bfqq->entity.parent == in_service_bfqq->entity.parent &&  in bfq_setup_cooperator()
3033 	if (new_bfqq && likely(new_bfqq != &bfqd->oom_bfqq) &&  in bfq_setup_cooperator()
3042 	struct bfq_io_cq *bic = bfqq->bic;  in bfq_bfqq_save_state()
3043 	unsigned int a_idx = bfqq->actuator_idx;  in bfq_bfqq_save_state()
3044 	struct bfq_iocq_bfqq_data *bfqq_data = &bic->bfqq_data[a_idx];  in bfq_bfqq_save_state()
3047 	 * If !bfqq->bic, the queue is already shared or its requests  in bfq_bfqq_save_state()
3054 	bfqq_data->saved_last_serv_time_ns = bfqq->last_serv_time_ns;  in bfq_bfqq_save_state()
3055 	bfqq_data->saved_inject_limit =	bfqq->inject_limit;  in bfq_bfqq_save_state()
3056 	bfqq_data->saved_decrease_time_jif = bfqq->decrease_time_jif;  in bfq_bfqq_save_state()
3058 	bfqq_data->saved_weight = bfqq->entity.orig_weight;  in bfq_bfqq_save_state()
3059 	bfqq_data->saved_ttime = bfqq->ttime;  in bfq_bfqq_save_state()
3060 	bfqq_data->saved_has_short_ttime =  in bfq_bfqq_save_state()
3062 	bfqq_data->saved_IO_bound = bfq_bfqq_IO_bound(bfqq);  in bfq_bfqq_save_state()
3063 	bfqq_data->saved_io_start_time = bfqq->io_start_time;  in bfq_bfqq_save_state()
3064 	bfqq_data->saved_tot_idle_time = bfqq->tot_idle_time;  in bfq_bfqq_save_state()
3065 	bfqq_data->saved_in_large_burst = bfq_bfqq_in_large_burst(bfqq);  in bfq_bfqq_save_state()
3066 	bfqq_data->was_in_burst_list =  in bfq_bfqq_save_state()
3067 		!hlist_unhashed(&bfqq->burst_list_node);  in bfq_bfqq_save_state()
3071 		     bfqq->bfqd->low_latency)) {  in bfq_bfqq_save_state()
3075 		 * did not make it to be set in a weight-raised state,  in bfq_bfqq_save_state()
3077 		 * weight-raising state that would have been assigned  in bfq_bfqq_save_state()
3081 		bfqq_data->saved_wr_coeff = bfqq->bfqd->bfq_wr_coeff;  in bfq_bfqq_save_state()
3082 		bfqq_data->saved_wr_start_at_switch_to_srt =  in bfq_bfqq_save_state()
3084 		bfqq_data->saved_wr_cur_max_time =  in bfq_bfqq_save_state()
3085 			bfq_wr_duration(bfqq->bfqd);  in bfq_bfqq_save_state()
3086 		bfqq_data->saved_last_wr_start_finish = jiffies;  in bfq_bfqq_save_state()
3088 		bfqq_data->saved_wr_coeff = bfqq->wr_coeff;  in bfq_bfqq_save_state()
3089 		bfqq_data->saved_wr_start_at_switch_to_srt =  in bfq_bfqq_save_state()
3090 			bfqq->wr_start_at_switch_to_srt;  in bfq_bfqq_save_state()
3091 		bfqq_data->saved_service_from_wr =  in bfq_bfqq_save_state()
3092 			bfqq->service_from_wr;  in bfq_bfqq_save_state()
3093 		bfqq_data->saved_last_wr_start_finish =  in bfq_bfqq_save_state()
3094 			bfqq->last_wr_start_finish;  in bfq_bfqq_save_state()
3095 		bfqq_data->saved_wr_cur_max_time = bfqq->wr_cur_max_time;  in bfq_bfqq_save_state()
3103 	if (cur_bfqq->entity.parent &&  in bfq_reassign_last_bfqq()
3104 	    cur_bfqq->entity.parent->last_bfqq_created == cur_bfqq)  in bfq_reassign_last_bfqq()
3105 		cur_bfqq->entity.parent->last_bfqq_created = new_bfqq;  in bfq_reassign_last_bfqq()
3106 	else if (cur_bfqq->bfqd && cur_bfqq->bfqd->last_bfqq_created == cur_bfqq)  in bfq_reassign_last_bfqq()
3107 		cur_bfqq->bfqd->last_bfqq_created = new_bfqq;  in bfq_reassign_last_bfqq()
3116 	 * details). But, if no process will send requests to bfqq any  in bfq_release_process_ref()
3117 	 * longer, then there is no point in keeping bfqq queued for  in bfq_release_process_ref()
3119 	 * with no process ref any longer, may have caused bfqq to be  in bfq_release_process_ref()
3123 	if (bfq_bfqq_busy(bfqq) && RB_EMPTY_ROOT(&bfqq->sort_list) &&  in bfq_release_process_ref()
3124 	    bfqq != bfqd->in_service_queue)  in bfq_release_process_ref()
3136 	struct bfq_queue *new_bfqq = bfqq->new_bfqq;  in bfq_merge_bfqqs()
3139 		(unsigned long)new_bfqq->pid);  in bfq_merge_bfqqs()
3151 	 * to let bfqq's waker freely inject I/O when they have no  in bfq_merge_bfqqs()
3154 	if (bfqq->waker_bfqq && !new_bfqq->waker_bfqq &&  in bfq_merge_bfqqs()
3155 	    bfqq->waker_bfqq != new_bfqq) {  in bfq_merge_bfqqs()
3156 		new_bfqq->waker_bfqq = bfqq->waker_bfqq;  in bfq_merge_bfqqs()
3157 		new_bfqq->tentative_waker_bfqq = NULL;  in bfq_merge_bfqqs()
3161 		 * new_bfqq->waker_bfqq must be reset. So insert  in bfq_merge_bfqqs()
3165 		hlist_add_head(&new_bfqq->woken_list_node,  in bfq_merge_bfqqs()
3166 			       &new_bfqq->waker_bfqq->woken_list);  in bfq_merge_bfqqs()
3171 	 * If bfqq is weight-raised, then let new_bfqq inherit  in bfq_merge_bfqqs()
3172 	 * weight-raising. To reduce false positives, neglect the case  in bfq_merge_bfqqs()
3174 	 * to be weight-raised (which may happen because EQM may merge  in bfq_merge_bfqqs()
3179 	if (new_bfqq->wr_coeff == 1 && bfqq->wr_coeff > 1) {  in bfq_merge_bfqqs()
3180 		new_bfqq->wr_coeff = bfqq->wr_coeff;  in bfq_merge_bfqqs()
3181 		new_bfqq->wr_cur_max_time = bfqq->wr_cur_max_time;  in bfq_merge_bfqqs()
3182 		new_bfqq->last_wr_start_finish = bfqq->last_wr_start_finish;  in bfq_merge_bfqqs()
3183 		new_bfqq->wr_start_at_switch_to_srt =  in bfq_merge_bfqqs()
3184 			bfqq->wr_start_at_switch_to_srt;  in bfq_merge_bfqqs()
3186 			bfqd->wr_busy_queues++;  in bfq_merge_bfqqs()
3187 		new_bfqq->entity.prio_changed = 1;  in bfq_merge_bfqqs()
3190 	if (bfqq->wr_coeff > 1) { /* bfqq has given its wr to new_bfqq */  in bfq_merge_bfqqs()
3191 		bfqq->wr_coeff = 1;  in bfq_merge_bfqqs()
3192 		bfqq->entity.prio_changed = 1;  in bfq_merge_bfqqs()
3194 			bfqd->wr_busy_queues--;  in bfq_merge_bfqqs()
3198 		     bfqd->wr_busy_queues);  in bfq_merge_bfqqs()
3203 	bic_set_bfqq(bic, new_bfqq, true, bfqq->actuator_idx);  in bfq_merge_bfqqs()
3207 	 * set new_bfqq->bic to NULL. bfqq either:  in bfq_merge_bfqqs()
3208 	 * - does not belong to any bic any more, and hence bfqq->bic must  in bfq_merge_bfqqs()
3210 	 * - is a queue whose owning bics have already been redirected to a  in bfq_merge_bfqqs()
3212 	 *   any bic soon and bfqq->bic is already NULL (therefore the next  in bfq_merge_bfqqs()
3213 	 *   assignment causes no harm).  in bfq_merge_bfqqs()
3215 	new_bfqq->bic = NULL;  in bfq_merge_bfqqs()
3222 	 * We mark such a queue with a pid -1, and then print SHARED instead of  in bfq_merge_bfqqs()
3225 	new_bfqq->pid = -1;  in bfq_merge_bfqqs()
3226 	bfqq->bic = NULL;  in bfq_merge_bfqqs()
3238 	struct bfq_data *bfqd = q->elevator->elevator_data;  in bfq_allow_bio_merge()
3239 	bool is_sync = op_is_sync(bio->bi_opf);  in bfq_allow_bio_merge()
3240 	struct bfq_queue *bfqq = bfqd->bio_bfqq, *new_bfqq;  in bfq_allow_bio_merge()
3259 	new_bfqq = bfq_setup_cooperator(bfqd, bfqq, bio, false, bfqd->bio_bic);  in bfq_allow_bio_merge()
3269 			bfqq = bfq_merge_bfqqs(bfqd, bfqd->bio_bic, bfqq);  in bfq_allow_bio_merge()
3272 		 * Change also bqfd->bio_bfqq, as  in bfq_allow_bio_merge()
3273 		 * bfqd->bio_bic now points to new_bfqq, and  in bfq_allow_bio_merge()
3275 		 * use again bqfd->bio_bfqq).  in bfq_allow_bio_merge()
3277 		bfqd->bio_bfqq = bfqq;  in bfq_allow_bio_merge()
3284  * Set the maximum time for the in-service queue to consume its
3286  * In practice, a time-slice service scheme is used with seeky
3294 	if (bfqq->wr_cur_max_time == bfqd->bfq_wr_rt_max_time)  in bfq_set_budget_timeout()
3297 		timeout_coeff = bfqq->entity.weight / bfqq->entity.orig_weight;  in bfq_set_budget_timeout()
3299 	bfqd->last_budget_start = blk_time_get();  in bfq_set_budget_timeout()
3301 	bfqq->budget_timeout = jiffies +  in bfq_set_budget_timeout()
3302 		bfqd->bfq_timeout * timeout_coeff;  in bfq_set_budget_timeout()
3311 		bfqd->budgets_assigned = (bfqd->budgets_assigned * 7 + 256) / 8;  in __bfq_set_in_service_queue()
3313 		if (time_is_before_jiffies(bfqq->last_wr_start_finish) &&  in __bfq_set_in_service_queue()
3314 		    bfqq->wr_coeff > 1 &&  in __bfq_set_in_service_queue()
3315 		    bfqq->wr_cur_max_time == bfqd->bfq_wr_rt_max_time &&  in __bfq_set_in_service_queue()
3316 		    time_is_before_jiffies(bfqq->budget_timeout)) {  in __bfq_set_in_service_queue()
3318 			 * For soft real-time queues, move the start  in __bfq_set_in_service_queue()
3319 			 * of the weight-raising period forward by the  in __bfq_set_in_service_queue()
3323 			 * weight-raising period of the queue to end,  in __bfq_set_in_service_queue()
3325 			 * weight-raising period of a soft real-time  in __bfq_set_in_service_queue()
3328 			 * because soft real-time queues are not  in __bfq_set_in_service_queue()
3338 			 * not only expires, but also remains with no  in __bfq_set_in_service_queue()
3341 			if (time_after(bfqq->budget_timeout,  in __bfq_set_in_service_queue()
3342 				       bfqq->last_wr_start_finish))  in __bfq_set_in_service_queue()
3343 				bfqq->last_wr_start_finish +=  in __bfq_set_in_service_queue()
3344 					jiffies - bfqq->budget_timeout;  in __bfq_set_in_service_queue()
3346 				bfqq->last_wr_start_finish = jiffies;  in __bfq_set_in_service_queue()
3351 			     "set_in_service_queue, cur-budget = %d",  in __bfq_set_in_service_queue()
3352 			     bfqq->entity.budget);  in __bfq_set_in_service_queue()
3355 	bfqd->in_service_queue = bfqq;  in __bfq_set_in_service_queue()
3356 	bfqd->in_serv_last_pos = 0;  in __bfq_set_in_service_queue()
3372 	struct bfq_queue *bfqq = bfqd->in_service_queue;  in bfq_arm_slice_timer()
3379 	 * fair distribution of slice time for a process doing back-to-back  in bfq_arm_slice_timer()
3382 	sl = bfqd->bfq_slice_idle;  in bfq_arm_slice_timer()
3384 	 * Unless the queue is being weight-raised or the scenario is  in bfq_arm_slice_timer()
3386 	 * is seeky. A long idling is preserved for a weight-raised  in bfq_arm_slice_timer()
3393 	if (BFQQ_SEEKY(bfqq) && bfqq->wr_coeff == 1 &&  in bfq_arm_slice_timer()
3396 	else if (bfqq->wr_coeff > 1)  in bfq_arm_slice_timer()
3399 	bfqd->last_idling_start = blk_time_get();  in bfq_arm_slice_timer()
3400 	bfqd->last_idling_start_jiffies = jiffies;  in bfq_arm_slice_timer()
3402 	hrtimer_start(&bfqd->idle_slice_timer, ns_to_ktime(sl),  in bfq_arm_slice_timer()
3411  * budget, even if the in-service queue is served at peak rate. And
3416 	return (u64)bfqd->peak_rate * USEC_PER_MSEC *  in bfq_calc_max_budget()
3417 		jiffies_to_msecs(bfqd->bfq_timeout)>>BFQ_RATE_SHIFT;  in bfq_calc_max_budget()
3427 	if (bfqd->bfq_user_max_budget == 0) {  in update_thr_responsiveness_params()
3428 		bfqd->bfq_max_budget =  in update_thr_responsiveness_params()
3430 		bfq_log(bfqd, "new max_budget = %d", bfqd->bfq_max_budget);  in update_thr_responsiveness_params()
3438 		bfqd->last_dispatch = bfqd->first_dispatch = blk_time_get_ns();  in bfq_reset_rate_computation()
3439 		bfqd->peak_rate_samples = 1;  in bfq_reset_rate_computation()
3440 		bfqd->sequential_samples = 0;  in bfq_reset_rate_computation()
3441 		bfqd->tot_sectors_dispatched = bfqd->last_rq_max_size =  in bfq_reset_rate_computation()
3443 	} else /* no new rq dispatched, just reset the number of samples */  in bfq_reset_rate_computation()
3444 		bfqd->peak_rate_samples = 0; /* full re-init on next disp. */  in bfq_reset_rate_computation()
3448 		bfqd->peak_rate_samples, bfqd->sequential_samples,  in bfq_reset_rate_computation()
3449 		bfqd->tot_sectors_dispatched);  in bfq_reset_rate_computation()
3464 	if (bfqd->peak_rate_samples < BFQ_RATE_MIN_SAMPLES ||  in bfq_update_rate_reset()
3465 	    bfqd->delta_from_first < BFQ_RATE_MIN_INTERVAL)  in bfq_update_rate_reset()
3474 	bfqd->delta_from_first =  in bfq_update_rate_reset()
3475 		max_t(u64, bfqd->delta_from_first,  in bfq_update_rate_reset()
3476 		      bfqd->last_completion - bfqd->first_dispatch);  in bfq_update_rate_reset()
3482 	rate = div64_ul(bfqd->tot_sectors_dispatched<<BFQ_RATE_SHIFT,  in bfq_update_rate_reset()
3483 			div_u64(bfqd->delta_from_first, NSEC_PER_USEC));  in bfq_update_rate_reset()
3487 	 * - the percentage of sequential dispatches is below 3/4 of the  in bfq_update_rate_reset()
3488 	 *   total, and rate is below the current estimated peak rate  in bfq_update_rate_reset()
3489 	 * - rate is unreasonably high (> 20M sectors/sec)  in bfq_update_rate_reset()
3491 	if ((bfqd->sequential_samples < (3 * bfqd->peak_rate_samples)>>2 &&  in bfq_update_rate_reset()
3492 	     rate <= bfqd->peak_rate) ||  in bfq_update_rate_reset()
3498 	 * we use a low-pass filter. We compute the smoothing constant  in bfq_update_rate_reset()
3514 	 * cannot reach 9, because bfqd->sequential_samples cannot  in bfq_update_rate_reset()
3515 	 * become equal to bfqd->peak_rate_samples, which, in its  in bfq_update_rate_reset()
3516 	 * turn, holds true because bfqd->sequential_samples is not  in bfq_update_rate_reset()
3519 	weight = (9 * bfqd->sequential_samples) / bfqd->peak_rate_samples;  in bfq_update_rate_reset()
3526 		       div_u64(weight * bfqd->delta_from_first,  in bfq_update_rate_reset()
3533 	divisor = 10 - weight;  in bfq_update_rate_reset()
3538 	 * peak_rate = peak_rate * (divisor-1) / divisor  +  rate / divisor  in bfq_update_rate_reset()
3540 	bfqd->peak_rate *= divisor-1;  in bfq_update_rate_reset()
3541 	bfqd->peak_rate /= divisor;  in bfq_update_rate_reset()
3544 	bfqd->peak_rate += rate;  in bfq_update_rate_reset()
3547 	 * For a very slow device, bfqd->peak_rate can reach 0 (see  in bfq_update_rate_reset()
3550 	 * divisions by zero where bfqd->peak_rate is used as a  in bfq_update_rate_reset()
3553 	bfqd->peak_rate = max_t(u32, 1, bfqd->peak_rate);  in bfq_update_rate_reset()
3563  * auto-tuning, see update_thr_responsiveness_params()).
3578  * unknown, namely in-device request service rate.
3585  * (no request is silently dropped), the following obvious convergence
3597 	if (bfqd->peak_rate_samples == 0) { /* first dispatch */  in bfq_update_peak_rate()
3599 			bfqd->peak_rate_samples);  in bfq_update_peak_rate()
3607 	 * for computing a new peak rate (similarly to the late-  in bfq_update_peak_rate()
3611 	 * - close the observation interval at the last (previous)  in bfq_update_peak_rate()
3613 	 * - compute rate, if possible, for that observation interval  in bfq_update_peak_rate()
3614 	 * - start a new observation interval with this dispatch  in bfq_update_peak_rate()
3616 	if (now_ns - bfqd->last_dispatch > 100*NSEC_PER_MSEC &&  in bfq_update_peak_rate()
3617 	    bfqd->tot_rq_in_driver == 0)  in bfq_update_peak_rate()
3621 	bfqd->peak_rate_samples++;  in bfq_update_peak_rate()
3623 	if ((bfqd->tot_rq_in_driver > 0 ||  in bfq_update_peak_rate()
3624 		now_ns - bfqd->last_completion < BFQ_MIN_TT)  in bfq_update_peak_rate()
3625 	    && !BFQ_RQ_SEEKY(bfqd, bfqd->last_position, rq))  in bfq_update_peak_rate()
3626 		bfqd->sequential_samples++;  in bfq_update_peak_rate()
3628 	bfqd->tot_sectors_dispatched += blk_rq_sectors(rq);  in bfq_update_peak_rate()
3631 	if (likely(bfqd->peak_rate_samples % 32))  in bfq_update_peak_rate()
3632 		bfqd->last_rq_max_size =  in bfq_update_peak_rate()
3633 			max_t(u32, blk_rq_sectors(rq), bfqd->last_rq_max_size);  in bfq_update_peak_rate()
3635 		bfqd->last_rq_max_size = blk_rq_sectors(rq);  in bfq_update_peak_rate()
3637 	bfqd->delta_from_first = now_ns - bfqd->first_dispatch;  in bfq_update_peak_rate()
3640 	if (bfqd->delta_from_first < BFQ_RATE_REF_INTERVAL)  in bfq_update_peak_rate()
3646 	bfqd->last_position = blk_rq_pos(rq) + blk_rq_sectors(rq);  in bfq_update_peak_rate()
3647 	if (RQ_BFQQ(rq) == bfqd->in_service_queue)  in bfq_update_peak_rate()
3648 		bfqd->in_serv_last_pos = bfqd->last_position;  in bfq_update_peak_rate()
3649 	bfqd->last_dispatch = now_ns;  in bfq_update_peak_rate()
3665 	 * dispatch occur for a non in-service bfqq, this anticipated  in bfq_dispatch_remove()
3666 	 * increment prevents two counters related to bfqq->dispatched  in bfq_dispatch_remove()
3668 	 * incremented again when the (new) value of bfqq->dispatched  in bfq_dispatch_remove()
3671 	bfqq->dispatched++;  in bfq_dispatch_remove()
3672 	bfq_update_peak_rate(q->elevator->elevator_data, rq);  in bfq_dispatch_remove()
3690  * the service order of the internally-queued requests, does
3692  * these processes. But the drive typically has no notion or
3693  * concern about per-process throughput distribution, and
3694  * makes its decisions only on a per-request basis. Therefore,
3699  * (i-a) each of these processes must get the same throughput as
3701  * (i-b) in case (i-a) does not hold, it holds that the process
3707  *       (from I/O-bound to sporadic), and so on;
3713  * distribution if (i-a) holds, or, if (i-b) holds instead, this is an
3718  * idling (I/O-dispatch plugging) is certainly needed to guarantee
3726  * throughput, it is important to check conditions (i-a), i(-b) and
3732  * very difficult to check conditions (i-a) and (i-b) too.  In fact,
3733  * if there are active groups, then, for conditions (i-a) or (i-b) to
3735  * contains more active processes or sub-groups than some other active
3736  * group. More precisely, for conditions (i-a) or (i-b) to become
3744  * inactive while still having in-flight requests, and if, when this
3750  * bi-modal behavior, implemented in the function
3757  * conditions (i-a), (i-b) or (ii). So the device is idled for bfqq.
3762  * On the opposite end, if there are no groups with requests waiting
3763  * for completion, then only conditions (i-a) and (i-b) are actually
3764  * controlled, i.e., provided that conditions (i-a) or (i-b) holds,
3766  * holds.  In other words, only if conditions (i-a) and (i-b) do not
3769  * there are no groups with requests waiting for completion, then, to
3770  * control conditions (i-a) and (i-b) it is enough to check just
3783  * can still preempt the new in-service queue if the next
3787  * combined with the hole-recovery heuristic described in the
3794  * minimum of mid-term fairness.
3796  * More precisely, this preemption-based, idleless approach
3817  * there is no active group, then the primary expectation for
3820  * We are now left only with explaining the two sub-conditions in the
3823  * sub-condition, we need to add that the function
3825  * non-weight-raised queues, for efficiency reasons (see comments on
3826  * bfq_weights_tree_add()). Then the fact that bfqq is weight-raised
3829  * weight-raised, the scenario is still symmetric if all queues with
3831  * weight-raised. Actually, we should be even more precise here, and
3832  * differentiate between interactive weight raising and soft real-time
3835  * The second sub-condition checked in the compound condition is
3836  * whether there is a fair amount of already in-flight I/O not
3838  * following reason. The drive may decide to serve in-flight
3839  * non-bfqq's I/O requests before bfqq's ones, thereby delaying the
3841  * I/O-dispatching is not plugged, then, while bfqq remains empty, a
3846  * because, as these two quantities grow, the probability to find no
3849  * in-flight I/O, and enables bfqq to recover the bandwidth it may
3853  * device-idling countermeasures may however fail in the following
3854  * unlucky scenario: if I/O-dispatch plugging is (correctly) disabled
3855  * in a time period during which all symmetry sub-conditions hold, and
3857  * some later point in time some sub-condition stops to hold, then it
3860  * served. The last sub-condition commented above somewhat mitigates
3861  * this problem for weight-raised queues.
3883 	/* No point in idling for bfqq if it won't get requests any longer */  in idling_needed_for_service_guarantees()
3887 	return (bfqq->wr_coeff > 1 &&  in idling_needed_for_service_guarantees()
3888 		(bfqd->wr_busy_queues < tot_busy_queues ||  in idling_needed_for_service_guarantees()
3889 		 bfqd->tot_rq_in_driver >= bfqq->dispatched + 4)) ||  in idling_needed_for_service_guarantees()
3914 	 * not re-scheduled. To prevent this from happening, re-queue  in __bfq_bfqq_expire()
3915 	 * bfqq if it needs I/O-dispatch plugging, even if it is  in __bfq_bfqq_expire()
3919 	if (RB_EMPTY_ROOT(&bfqq->sort_list) &&  in __bfq_bfqq_expire()
3922 		if (bfqq->dispatched == 0)  in __bfq_bfqq_expire()
3925 			 * the time at which the queue remains with no  in __bfq_bfqq_expire()
3926 			 * backlog and no outstanding request; used by  in __bfq_bfqq_expire()
3927 			 * the weight-raising mechanism.  in __bfq_bfqq_expire()
3929 			bfqq->budget_timeout = jiffies;  in __bfq_bfqq_expire()
3938 		if (unlikely(!bfqd->nonrot_with_queueing &&  in __bfq_bfqq_expire()
3939 			     !RB_EMPTY_ROOT(&bfqq->sort_list)))  in __bfq_bfqq_expire()
3944 	 * All in-service entities must have been properly deactivated  in __bfq_bfqq_expire()
3946 	 * resets all in-service entities as no more in service. This  in __bfq_bfqq_expire()
3954  * __bfq_bfqq_recalc_budget - try to adapt the budget to the @bfqq behavior.
3971 	if (bfqq->wr_coeff == 1)  in __bfq_bfqq_recalc_budget()
3972 		budget = bfqq->max_budget;  in __bfq_bfqq_recalc_budget()
3974 	      * Use a constant, low budget for weight-raised queues,  in __bfq_bfqq_recalc_budget()
3982 		bfqq->entity.budget, bfq_bfqq_budget_left(bfqq));  in __bfq_bfqq_recalc_budget()
3986 		bfq_bfqq_sync(bfqq), BFQQ_SEEKY(bfqd->in_service_queue));  in __bfq_bfqq_recalc_budget()
3988 	if (bfq_bfqq_sync(bfqq) && bfqq->wr_coeff == 1) {  in __bfq_bfqq_recalc_budget()
3997 			 * the budget: if there is no request of the  in __bfq_bfqq_recalc_budget()
4019 			if (bfqq->dispatched > 0) /* still outstanding reqs */  in __bfq_bfqq_recalc_budget()
4020 				budget = min(budget * 2, bfqd->bfq_max_budget);  in __bfq_bfqq_recalc_budget()
4023 					budget -= 4 * min_budget;  in __bfq_bfqq_recalc_budget()
4035 			budget = min(budget * 2, bfqd->bfq_max_budget);  in __bfq_bfqq_recalc_budget()
4047 			budget = min(budget * 4, bfqd->bfq_max_budget);  in __bfq_bfqq_recalc_budget()
4061 			 * back-shifting. The larger the budget of the  in __bfq_bfqq_recalc_budget()
4070 			 * many re-activations a lower finish time  in __bfq_bfqq_recalc_budget()
4074 			 * quite precisely by bfqq->entity.service.  in __bfq_bfqq_recalc_budget()
4076 			 * bfqq->entity.service is equal to the number  in __bfq_bfqq_recalc_budget()
4082 			budget = max_t(int, bfqq->entity.service, min_budget);  in __bfq_bfqq_recalc_budget()
4094 		budget = bfqd->bfq_max_budget;  in __bfq_bfqq_recalc_budget()
4097 	bfqq->max_budget = budget;  in __bfq_bfqq_recalc_budget()
4099 	if (bfqd->budgets_assigned >= bfq_stats_min_budgets &&  in __bfq_bfqq_recalc_budget()
4100 	    !bfqd->bfq_user_max_budget)  in __bfq_bfqq_recalc_budget()
4101 		bfqq->max_budget = min(bfqq->max_budget, bfqd->bfq_max_budget);  in __bfq_bfqq_recalc_budget()
4110 	 * If there is no backlog, then no need to update the budget;  in __bfq_bfqq_recalc_budget()
4113 	next_rq = bfqq->next_rq;  in __bfq_bfqq_recalc_budget()
4115 		bfqq->entity.budget = max_t(unsigned long, bfqq->max_budget,  in __bfq_bfqq_recalc_budget()
4120 			bfqq->entity.budget);  in __bfq_bfqq_recalc_budget()
4143  * service slots. On the opposite end, the requests of the in-service
4165 		delta_ktime = bfqd->last_idling_start;  in bfq_bfqq_is_slow()
4168 	delta_ktime = ktime_sub(delta_ktime, bfqd->last_budget_start);  in bfq_bfqq_is_slow()
4173 		if (blk_queue_nonrot(bfqd->queue))  in bfq_bfqq_is_slow()
4175 			  * give same worst-case guarantees as idling  in bfq_bfqq_is_slow()
4202 		slow = bfqq->entity.service < bfqd->bfq_max_budget / 2;  in bfq_bfqq_is_slow()
4211  * To be deemed as soft real-time, an application must meet two
4214  * record a compressed high-definition video.
4216  * batch, to compute the next-start time instant, soft_rt_next_start, such
4230  * Unfortunately, even a greedy (i.e., I/O-bound) application may
4237  * device: the storage device is highly loaded or reaches a low-enough
4242  * that greedy applications are deemed as soft real-time in these
4247  * (a) Current time plus: (1) the maximum time for which the arrival
4249  *     namely bfqd->bfq_slice_idle, and (2) a few extra jiffies. We
4251  *     jiffies; we get back to it after next item (b).  Lower-bounding
4252  *     the return value of this function with the current time plus
4253  *     bfqd->bfq_slice_idle tends to filter out greedy applications,
4256  *     real-time application spends some time processing data, after a
4259  * (b) Current value of bfqq->soft_rt_next_start. As pointed out
4262  *     storage-device load. In more detail, in these scenarios, these
4265  *     including the filtering in above item (a). These slow-speed
4269  *     I/O in the high-speed intervals, the values returned by this
4271  *     high-speed interval, to be likely to fall *after* the end of
4272  *     the low-speed time interval that follows. These high values are
4273  *     stored in bfqq->soft_rt_next_start after each invocation of
4275  *     bfqq->soft_rt_next_start is constantly used to lower-bound the
4277  *     beginning of a low-speed interval, bfqq->soft_rt_next_start is
4279  *     issued during the low-speed interval is considered as arriving
4281  *     real-time. Then, in the high-speed interval that follows, the
4282  *     application will not be deemed as soft real-time, just because
4288  * bfqd->bfq_slice_idle:
4290  *    higher than bfqd->bfq_slice_idle. This happens, e.g., on slow
4292  *    that the approximation, in jiffies, of bfqd->bfq_slice_idle
4298  * reference time interval just bfqd->bfq_slice_idle, but
4299  * bfqd->bfq_slice_idle plus a few jiffies. In particular, we add the
4306 	return max3(bfqq->soft_rt_next_start,  in bfq_bfqq_softrt_next_start()
4307 		    bfqq->last_idle_bklogged +  in bfq_bfqq_softrt_next_start()
4308 		    HZ * bfqq->service_from_backlogged /  in bfq_bfqq_softrt_next_start()
4309 		    bfqd->bfq_wr_max_softrt_rate,  in bfq_bfqq_softrt_next_start()
4310 		    jiffies + nsecs_to_jiffies(bfqq->bfqd->bfq_slice_idle) + 4);  in bfq_bfqq_softrt_next_start()
4314  * bfq_bfqq_expire - expire a queue.
4329  * tends to lower the throughput). In addition, this time-charging
4346 	struct bfq_entity *entity = &bfqq->entity;  in bfq_bfqq_expire()
4355 	 * timed-out queues with the time and not the service  in bfq_bfqq_expire()
4366 	 * or quasi-sequential processes.  in bfq_bfqq_expire()
4368 	if (bfqq->wr_coeff == 1 &&  in bfq_bfqq_expire()
4371 	      bfq_bfqq_budget_left(bfqq) >=  entity->budget / 3)))  in bfq_bfqq_expire()
4374 	if (bfqd->low_latency && bfqq->wr_coeff == 1)  in bfq_bfqq_expire()
4375 		bfqq->last_wr_start_finish = jiffies;  in bfq_bfqq_expire()
4377 	if (bfqd->low_latency && bfqd->bfq_wr_max_softrt_rate > 0 &&  in bfq_bfqq_expire()
4378 	    RB_EMPTY_ROOT(&bfqq->sort_list)) {  in bfq_bfqq_expire()
4380 		 * If we get here, and there are no outstanding  in bfq_bfqq_expire()
4391 		if (bfqq->dispatched == 0)  in bfq_bfqq_expire()
4392 			bfqq->soft_rt_next_start =  in bfq_bfqq_expire()
4394 		else if (bfqq->dispatched > 0) {  in bfq_bfqq_expire()
4405 		slow, bfqq->dispatched, bfq_bfqq_has_short_ttime(bfqq));  in bfq_bfqq_expire()
4408 	 * bfqq expired, so no total service time needs to be computed  in bfq_bfqq_expire()
4412 	bfqd->rqs_injected = bfqd->wait_dispatch = false;  in bfq_bfqq_expire()
4413 	bfqd->waited_rq = NULL;  in bfq_bfqq_expire()
4421 		/* bfqq is gone, no more actions on it */  in bfq_bfqq_expire()
4435 		entity->service = 0;  in bfq_bfqq_expire()
4438 	 * Reset the received-service counter for every parent entity.  in bfq_bfqq_expire()
4439 	 * Differently from what happens with bfqq->entity.service,  in bfq_bfqq_expire()
4443 	 * consumed budget, bfqq->entity.service needs to be kept,  in bfq_bfqq_expire()
4445 	 * the same budget, the last value of bfqq->entity.service is  in bfq_bfqq_expire()
4446 	 * needed to properly decrement bfqq->entity.budget by the  in bfq_bfqq_expire()
4448 	 * to keep entity->service for parent entities too, because  in bfq_bfqq_expire()
4449 	 * the bubble up of the new value of bfqq->entity.budget will  in bfq_bfqq_expire()
4454 	entity = entity->parent;  in bfq_bfqq_expire()
4456 		entity->service = 0;  in bfq_bfqq_expire()
4466 	return time_is_before_eq_jiffies(bfqq->budget_timeout);  in bfq_bfqq_budget_timeout()
4479 	bfq_log_bfqq(bfqq->bfqd, bfqq,  in bfq_may_expire_for_budg_timeout()
4482 			bfq_bfqq_budget_left(bfqq) >=  bfqq->entity.budget / 3,  in bfq_may_expire_for_budg_timeout()
4486 		bfq_bfqq_budget_left(bfqq) >=  bfqq->entity.budget / 3)  in bfq_may_expire_for_budg_timeout()
4495 		!blk_queue_nonrot(bfqd->queue) && !bfqd->hw_tag,  in idling_boosts_thr_without_issues()
4499 	/* No point in idling for bfqq if it won't get requests any longer */  in idling_boosts_thr_without_issues()
4512 	 * (a) the device is not NCQ-capable and rotational, or  in idling_boosts_thr_without_issues()
4514 	 *     the request pattern for bfqq is I/O-bound and sequential, or  in idling_boosts_thr_without_issues()
4516 	 *     not NCQ-capable and the request pattern for bfqq is  in idling_boosts_thr_without_issues()
4517 	 *     I/O-bound and sequential.  in idling_boosts_thr_without_issues()
4520 	 * NCQ-capable flash-based device would not boost the  in idling_boosts_thr_without_issues()
4525 	 * particular, happens to be false if bfqd is an NCQ-capable  in idling_boosts_thr_without_issues()
4526 	 * flash-based device.  in idling_boosts_thr_without_issues()
4529 		((!blk_queue_nonrot(bfqd->queue) || !bfqd->hw_tag) &&  in idling_boosts_thr_without_issues()
4536 	 * weight-raised queues.  in idling_boosts_thr_without_issues()
4540 	 * non-weight-raised queues ask for requests at a lower rate,  in idling_boosts_thr_without_issues()
4541 	 * then processes associated with weight-raised queues have a  in idling_boosts_thr_without_issues()
4546 	 * weight. This is especially true with NCQ-capable drives,  in idling_boosts_thr_without_issues()
4548 	 * reorder internally-queued requests.  in idling_boosts_thr_without_issues()
4551 	 * there are weight-raised busy queues. In this case, and if  in idling_boosts_thr_without_issues()
4552 	 * bfqq is not weight-raised, this guarantees that the device  in idling_boosts_thr_without_issues()
4553 	 * is not idled for bfqq (if, instead, bfqq is weight-raised,  in idling_boosts_thr_without_issues()
4557 	 * sync non-weight-raised queue, to get a lower number of  in idling_boosts_thr_without_issues()
4560 	 * weight-raised queues get served again. This often mitigates  in idling_boosts_thr_without_issues()
4567 		bfqd->wr_busy_queues == 0;  in idling_boosts_thr_without_issues()
4581  * NCQ-capable devices, this function tries to return false, so as to
4583  * device boost the throughput without causing any service-guarantee
4593 	struct bfq_data *bfqd = bfqq->bfqd;  in bfq_better_to_idle()
4596 	/* No point in idling for bfqq if it won't get requests any longer */  in bfq_better_to_idle()
4600 	if (unlikely(bfqd->strict_guarantees))  in bfq_better_to_idle()
4609 	 * queues in this class can steal to higher-priority queues  in bfq_better_to_idle()
4611 	if (bfqd->bfq_slice_idle == 0 || !bfq_bfqq_sync(bfqq) ||  in bfq_better_to_idle()
4632  * If the in-service queue is empty but the function bfq_better_to_idle
4644 	return RB_EMPTY_ROOT(&bfqq->sort_list) && bfq_better_to_idle(bfqq);  in bfq_bfqq_must_idle()
4657 	struct bfq_queue *bfqq, *in_serv_bfqq = bfqd->in_service_queue;  in bfq_choose_bfqq_for_injection()
4658 	unsigned int limit = in_serv_bfqq->inject_limit;  in bfq_choose_bfqq_for_injection()  local
4663 	 * - bfqq is not weight-raised and therefore does not carry  in bfq_choose_bfqq_for_injection()
4664 	 *   time-critical I/O,  in bfq_choose_bfqq_for_injection()
4666 	 * - regardless of whether bfqq is weight-raised, bfqq has  in bfq_choose_bfqq_for_injection()
4673 	bool in_serv_always_inject = in_serv_bfqq->wr_coeff == 1 ||  in bfq_choose_bfqq_for_injection()
4678 	 * - the baseline total service time could not be sampled yet,  in bfq_choose_bfqq_for_injection()
4679 	 *   so the inject limit happens to be still 0, and  in bfq_choose_bfqq_for_injection()
4680 	 * - a lot of time has elapsed since the plugging of I/O  in bfq_choose_bfqq_for_injection()
4683 	 * then temporarily raise inject limit to one request.  in bfq_choose_bfqq_for_injection()
4685 	if (limit == 0 && in_serv_bfqq->last_serv_time_ns == 0 &&  in bfq_choose_bfqq_for_injection()
4687 	    time_is_before_eq_jiffies(bfqd->last_idling_start_jiffies +  in bfq_choose_bfqq_for_injection()
4688 				      bfqd->bfq_slice_idle)  in bfq_choose_bfqq_for_injection()
4690 		limit = 1;  in bfq_choose_bfqq_for_injection()
4692 	if (bfqd->tot_rq_in_driver >= limit)  in bfq_choose_bfqq_for_injection()
4700 	 * - BFQ dynamically updates the budget of every queue so as  in bfq_choose_bfqq_for_injection()
4702 	 * - if a queue gets all its requests dispatched as injected  in bfq_choose_bfqq_for_injection()
4704 	 *   (and re-added only if it gets new requests, but then it  in bfq_choose_bfqq_for_injection()
4707 	for (i = 0; i < bfqd->num_actuators; i++) {  in bfq_choose_bfqq_for_injection()
4708 		list_for_each_entry(bfqq, &bfqd->active_list[i], bfqq_list)  in bfq_choose_bfqq_for_injection()
4709 			if (!RB_EMPTY_ROOT(&bfqq->sort_list) &&  in bfq_choose_bfqq_for_injection()
4710 				(in_serv_always_inject || bfqq->wr_coeff > 1) &&  in bfq_choose_bfqq_for_injection()
4711 				bfq_serv_to_charge(bfqq->next_rq, bfqq) <=  in bfq_choose_bfqq_for_injection()
4714 			 * Allow for only one large in-flight request  in bfq_choose_bfqq_for_injection()
4715 			 * on non-rotational devices, for the  in bfq_choose_bfqq_for_injection()
4716 			 * following reason. On non-rotationl drives,  in bfq_choose_bfqq_for_injection()
4723 			 * request of the in-service queue wait for so  in bfq_choose_bfqq_for_injection()
4727 			 * there is only one in-flight large request  in bfq_choose_bfqq_for_injection()
4730 			if (blk_queue_nonrot(bfqd->queue) &&  in bfq_choose_bfqq_for_injection()
4731 			    blk_rq_sectors(bfqq->next_rq) >=  in bfq_choose_bfqq_for_injection()
4733 			    bfqd->tot_rq_in_driver >= 1)  in bfq_choose_bfqq_for_injection()
4736 				bfqd->rqs_injected = true;  in bfq_choose_bfqq_for_injection()
4750 	if (bfqd->in_service_queue &&  in bfq_find_active_bfqq_for_actuator()
4751 	    bfqd->in_service_queue->actuator_idx == idx)  in bfq_find_active_bfqq_for_actuator()
4752 		return bfqd->in_service_queue;  in bfq_find_active_bfqq_for_actuator()
4754 	list_for_each_entry(bfqq, &bfqd->active_list[idx], bfqq_list) {  in bfq_find_active_bfqq_for_actuator()
4755 		if (!RB_EMPTY_ROOT(&bfqq->sort_list) &&  in bfq_find_active_bfqq_for_actuator()
4756 			bfq_serv_to_charge(bfqq->next_rq, bfqq) <=  in bfq_find_active_bfqq_for_actuator()
4783 	for (i = 0 ; i < bfqd->num_actuators; i++) {  in bfq_find_bfqq_for_underused_actuator()
4784 		if (bfqd->rq_in_driver[i] < bfqd->actuator_load_threshold &&  in bfq_find_bfqq_for_underused_actuator()
4785 		    (i == bfqd->num_actuators - 1 ||  in bfq_find_bfqq_for_underused_actuator()
4786 		     bfqd->rq_in_driver[i] < bfqd->rq_in_driver[i+1])) {  in bfq_find_bfqq_for_underused_actuator()
4800  * Select a queue for service.  If we have a current queue in service,
4809 	bfqq = bfqd->in_service_queue;  in bfq_select_queue()
4813 	bfq_log_bfqq(bfqd, bfqq, "select_queue: already in-service queue");  in bfq_select_queue()
4828 	 *  If some actuator is underutilized, but the in-service  in bfq_select_queue()
4838 	 * happens, it is much more convenient to re-execute this loop  in bfq_select_queue()
4842 	next_rq = bfqq->next_rq;  in bfq_select_queue()
4879 				hrtimer_try_to_cancel(&bfqd->idle_slice_timer);  in bfq_select_queue()
4886 	 * No requests pending. However, if the in-service queue is idling  in bfq_select_queue()
4894 	    (bfqq->dispatched != 0 && bfq_better_to_idle(bfqq))) {  in bfq_select_queue()
4895 		unsigned int act_idx = bfqq->actuator_idx;  in bfq_select_queue()
4898 			!hlist_empty(&bfqq->woken_list) ?  in bfq_select_queue()
4899 			container_of(bfqq->woken_list.first,  in bfq_select_queue()
4904 		if (bfqq->bic && bfqq->bic->bfqq[0][act_idx] &&  in bfq_select_queue()
4905 		    bfq_bfqq_busy(bfqq->bic->bfqq[0][act_idx]) &&  in bfq_select_queue()
4906 		    bfqq->bic->bfqq[0][act_idx]->next_rq)  in bfq_select_queue()
4907 			async_bfqq = bfqq->bic->bfqq[0][act_idx];  in bfq_select_queue()
4909 		 * The next four mutually-exclusive ifs decide  in bfq_select_queue()
4916 		 * I/O from the same process can cause no harm to the  in bfq_select_queue()
4921 		 * non-empty waker queue for bfqq, i.e., a queue whose  in bfq_select_queue()
4928 		 * then bfqq remains empty, and no I/O is dispatched,  in bfq_select_queue()
4946 		 * served. So there is virtually no risk of loss of  in bfq_select_queue()
4962 		 * limit for bfqq is currently 0).  in bfq_select_queue()
4966 		 * Thanks to the way the inject limit is updated in  in bfq_select_queue()
4972 		 * I/O-plugging timeout fires. So one may deem the  in bfq_select_queue()
4977 		 * inject limit may be too low to guarantee the same  in bfq_select_queue()
4989 		    icq_to_bic(async_bfqq->next_rq->elv.icq) == bfqq->bic &&  in bfq_select_queue()
4990 		    bfq_serv_to_charge(async_bfqq->next_rq, async_bfqq) <=  in bfq_select_queue()
4993 		else if (bfqq->waker_bfqq &&  in bfq_select_queue()
4994 			   bfq_bfqq_busy(bfqq->waker_bfqq) &&  in bfq_select_queue()
4995 			   bfqq->waker_bfqq->next_rq &&  in bfq_select_queue()
4996 			   bfq_serv_to_charge(bfqq->waker_bfqq->next_rq,  in bfq_select_queue()
4997 					      bfqq->waker_bfqq) <=  in bfq_select_queue()
4998 			   bfq_bfqq_budget_left(bfqq->waker_bfqq)  in bfq_select_queue()
5000 			bfqq = bfqq->waker_bfqq;  in bfq_select_queue()
5003 			   blocked_bfqq->next_rq &&  in bfq_select_queue()
5004 			   bfq_serv_to_charge(blocked_bfqq->next_rq,  in bfq_select_queue()
5010 			 (bfqq->wr_coeff == 1 || bfqd->wr_busy_queues > 1 ||  in bfq_select_queue()
5032 		bfq_log(bfqd, "select_queue: no queue returned");  in bfq_select_queue()
5039 	struct bfq_entity *entity = &bfqq->entity;  in bfq_update_wr_data()
5041 	if (bfqq->wr_coeff > 1) { /* queue is being weight-raised */  in bfq_update_wr_data()
5044 			jiffies_to_msecs(jiffies - bfqq->last_wr_start_finish),  in bfq_update_wr_data()
5045 			jiffies_to_msecs(bfqq->wr_cur_max_time),  in bfq_update_wr_data()
5046 			bfqq->wr_coeff,  in bfq_update_wr_data()
5047 			bfqq->entity.weight, bfqq->entity.orig_weight);  in bfq_update_wr_data()
5049 		if (entity->prio_changed)  in bfq_update_wr_data()
5055 		 * weight-raising period, then end weight raising.  in bfq_update_wr_data()
5059 		else if (time_is_before_jiffies(bfqq->last_wr_start_finish +  in bfq_update_wr_data()
5060 						bfqq->wr_cur_max_time)) {  in bfq_update_wr_data()
5061 			if (bfqq->wr_cur_max_time != bfqd->bfq_wr_rt_max_time ||  in bfq_update_wr_data()
5062 			time_is_before_jiffies(bfqq->wr_start_at_switch_to_srt +  in bfq_update_wr_data()
5068 				 * interactive-weight-raising period  in bfq_update_wr_data()
5069 				 * elapsed (so no switch back to  in bfq_update_wr_data()
5079 				bfqq->entity.prio_changed = 1;  in bfq_update_wr_data()
5082 		if (bfqq->wr_coeff > 1 &&  in bfq_update_wr_data()
5083 		    bfqq->wr_cur_max_time != bfqd->bfq_wr_rt_max_time &&  in bfq_update_wr_data()
5084 		    bfqq->service_from_wr > max_service_from_wr) {  in bfq_update_wr_data()
5097 	if ((entity->weight > entity->orig_weight) != (bfqq->wr_coeff > 1))  in bfq_update_wr_data()
5108 	struct request *rq = bfqq->next_rq;  in bfq_dispatch_rq_from_bfqq()
5115 	if (bfqq == bfqd->in_service_queue && bfqd->wait_dispatch) {  in bfq_dispatch_rq_from_bfqq()
5116 		bfqd->wait_dispatch = false;  in bfq_dispatch_rq_from_bfqq()
5117 		bfqd->waited_rq = rq;  in bfq_dispatch_rq_from_bfqq()
5120 	bfq_dispatch_remove(bfqd->queue, rq);  in bfq_dispatch_rq_from_bfqq()
5122 	if (bfqq != bfqd->in_service_queue)  in bfq_dispatch_rq_from_bfqq()
5130 	 * weight-raised during this service slot, even if it has  in bfq_dispatch_rq_from_bfqq()
5132 	 * weight-raised queue. This inflates bfqq's timestamps, which  in bfq_dispatch_rq_from_bfqq()
5134 	 * device immediately to possible other weight-raised queues.  in bfq_dispatch_rq_from_bfqq()
5151 	struct bfq_data *bfqd = hctx->queue->elevator->elevator_data;  in bfq_has_work()
5154 	 * Avoiding lock: a race on bfqd->queued should cause at  in bfq_has_work()
5157 	return !list_empty_careful(&bfqd->dispatch) ||  in bfq_has_work()
5158 		READ_ONCE(bfqd->queued);  in bfq_has_work()
5163 	struct bfq_data *bfqd = hctx->queue->elevator->elevator_data;  in __bfq_dispatch_request()
5167 	if (!list_empty(&bfqd->dispatch)) {  in __bfq_dispatch_request()
5168 		rq = list_first_entry(&bfqd->dispatch, struct request,  in __bfq_dispatch_request()
5170 		list_del_init(&rq->queuelist);  in __bfq_dispatch_request()
5181 			bfqq->dispatched++;  in __bfq_dispatch_request()
5206 		 * being the frequency of non-elevator-private  in __bfq_dispatch_request()
5230 	if (bfqd->strict_guarantees && bfqd->tot_rq_in_driver > 0)  in __bfq_dispatch_request()
5241 		bfqd->rq_in_driver[bfqq->actuator_idx]++;  in __bfq_dispatch_request()
5242 		bfqd->tot_rq_in_driver++;  in __bfq_dispatch_request()
5244 		rq->rq_flags |= RQF_STARTED;  in __bfq_dispatch_request()
5274 	spin_lock_irq(&q->queue_lock);  in bfq_update_dispatch_stats()
5291 		bfqg_stats_update_io_remove(bfqg, rq->cmd_flags);  in bfq_update_dispatch_stats()
5293 	spin_unlock_irq(&q->queue_lock);  in bfq_update_dispatch_stats()
5304 	struct bfq_data *bfqd = hctx->queue->elevator->elevator_data;  in bfq_dispatch_request()
5309 	spin_lock_irq(&bfqd->lock);  in bfq_dispatch_request()
5311 	in_serv_queue = bfqd->in_service_queue;  in bfq_dispatch_request()
5315 	if (in_serv_queue == bfqd->in_service_queue) {  in bfq_dispatch_request()
5320 	spin_unlock_irq(&bfqd->lock);  in bfq_dispatch_request()
5321 	bfq_update_dispatch_stats(hctx->queue, rq,  in bfq_dispatch_request()
5330  * in-flight on this queue also holds a reference, dropped when rq is freed.
5341 	bfq_log_bfqq(bfqq->bfqd, bfqq, "put_queue: %p %d", bfqq, bfqq->ref);  in bfq_put_queue()
5343 	bfqq->ref--;  in bfq_put_queue()
5344 	if (bfqq->ref)  in bfq_put_queue()
5347 	if (!hlist_unhashed(&bfqq->burst_list_node)) {  in bfq_put_queue()
5348 		hlist_del_init(&bfqq->burst_list_node);  in bfq_put_queue()
5354 		 * bursts, when some short-lived process (often due to  in bfq_put_queue()
5369 		 * the current burst list--without incrementing  in bfq_put_queue()
5370 		 * bust_size--because of a split, but the current  in bfq_put_queue()
5375 		if (bfqq->bic && bfqq->bfqd->burst_size > 0)  in bfq_put_queue()
5376 			bfqq->bfqd->burst_size--;  in bfq_put_queue()
5385 	 * should be performed when bfqq remains with no I/O source  in bfq_put_queue()
5395 	if (!hlist_unhashed(&bfqq->woken_list_node))  in bfq_put_queue()
5396 		hlist_del_init(&bfqq->woken_list_node);  in bfq_put_queue()
5399 	hlist_for_each_entry_safe(item, n, &bfqq->woken_list,  in bfq_put_queue()
5401 		item->waker_bfqq = NULL;  in bfq_put_queue()
5402 		hlist_del_init(&item->woken_list_node);  in bfq_put_queue()
5405 	if (bfqq->bfqd->last_completed_rq_bfqq == bfqq)  in bfq_put_queue()
5406 		bfqq->bfqd->last_completed_rq_bfqq = NULL;  in bfq_put_queue()
5408 	WARN_ON_ONCE(!list_empty(&bfqq->fifo));  in bfq_put_queue()
5409 	WARN_ON_ONCE(!RB_EMPTY_ROOT(&bfqq->sort_list));  in bfq_put_queue()
5410 	WARN_ON_ONCE(bfqq->dispatched);  in bfq_put_queue()
5418 	bfqq->stable_ref--;  in bfq_put_stable_ref()
5431 	__bfqq = bfqq->new_bfqq;  in bfq_put_cooperator()
5433 		next = __bfqq->new_bfqq;  in bfq_put_cooperator()
5438 	bfq_release_process_ref(bfqq->bfqd, bfqq);  in bfq_put_cooperator()
5443 	if (bfqq == bfqd->in_service_queue) {  in bfq_exit_bfqq()
5448 	bfq_log_bfqq(bfqd, bfqq, "exit_bfqq: %p, %d", bfqq, bfqq->ref);  in bfq_exit_bfqq()
5460 		bfqd = bfqq->bfqd; /* NULL if scheduler already exited */  in bfq_exit_icq_bfqq()
5470 	struct bfq_iocq_bfqq_data *bfqq_data = bic->bfqq_data;  in _bfq_exit_icq()
5489 	 * If bfqd and thus bfqd->num_actuators is not available any  in bfq_exit_icq()
5490 	 * longer, then cycle over all possible per-actuator bfqqs in  in bfq_exit_icq()
5492 	 * therefore on its unused per-actuator fields being NULL.  in bfq_exit_icq()
5498 		spin_lock_irqsave(&bfqd->lock, flags);  in bfq_exit_icq()
5499 		_bfq_exit_icq(bic, bfqd->num_actuators);  in bfq_exit_icq()
5500 		spin_unlock_irqrestore(&bfqd->lock, flags);  in bfq_exit_icq()
5513 	struct task_struct *tsk = current;  in bfq_set_next_ioprio_data()
5515 	struct bfq_data *bfqd = bfqq->bfqd;  in bfq_set_next_ioprio_data()
5520 	ioprio_class = IOPRIO_PRIO_CLASS(bic->ioprio);  in bfq_set_next_ioprio_data()
5524 			bdi_dev_name(bfqq->bfqd->queue->disk->bdi),  in bfq_set_next_ioprio_data()
5529 		 * No prio set, inherit CPU scheduling settings.  in bfq_set_next_ioprio_data()
5531 		bfqq->new_ioprio = task_nice_ioprio(tsk);  in bfq_set_next_ioprio_data()
5532 		bfqq->new_ioprio_class = task_nice_ioclass(tsk);  in bfq_set_next_ioprio_data()
5535 		bfqq->new_ioprio = IOPRIO_PRIO_LEVEL(bic->ioprio);  in bfq_set_next_ioprio_data()
5536 		bfqq->new_ioprio_class = IOPRIO_CLASS_RT;  in bfq_set_next_ioprio_data()
5539 		bfqq->new_ioprio = IOPRIO_PRIO_LEVEL(bic->ioprio);  in bfq_set_next_ioprio_data()
5540 		bfqq->new_ioprio_class = IOPRIO_CLASS_BE;  in bfq_set_next_ioprio_data()
5543 		bfqq->new_ioprio_class = IOPRIO_CLASS_IDLE;  in bfq_set_next_ioprio_data()
5544 		bfqq->new_ioprio = IOPRIO_NR_LEVELS - 1;  in bfq_set_next_ioprio_data()
5548 	if (bfqq->new_ioprio >= IOPRIO_NR_LEVELS) {  in bfq_set_next_ioprio_data()
5550 			bfqq->new_ioprio);  in bfq_set_next_ioprio_data()
5551 		bfqq->new_ioprio = IOPRIO_NR_LEVELS - 1;  in bfq_set_next_ioprio_data()
5554 	bfqq->entity.new_weight = bfq_ioprio_to_weight(bfqq->new_ioprio);  in bfq_set_next_ioprio_data()
5556 		     bfqq->new_ioprio, bfqq->entity.new_weight);  in bfq_set_next_ioprio_data()
5557 	bfqq->entity.prio_changed = 1;  in bfq_set_next_ioprio_data()
5569 	int ioprio = bic->icq.ioc->ioprio;  in bfq_check_ioprio_change()
5575 	if (unlikely(!bfqd) || likely(bic->ioprio == ioprio))  in bfq_check_ioprio_change()
5578 	bic->ioprio = ioprio;  in bfq_check_ioprio_change()
5600 	bfqq->actuator_idx = act_idx;  in bfq_init_bfqq()
5601 	RB_CLEAR_NODE(&bfqq->entity.rb_node);  in bfq_init_bfqq()
5602 	INIT_LIST_HEAD(&bfqq->fifo);  in bfq_init_bfqq()
5603 	INIT_HLIST_NODE(&bfqq->burst_list_node);  in bfq_init_bfqq()
5604 	INIT_HLIST_NODE(&bfqq->woken_list_node);  in bfq_init_bfqq()
5605 	INIT_HLIST_HEAD(&bfqq->woken_list);  in bfq_init_bfqq()
5607 	bfqq->ref = 0;  in bfq_init_bfqq()
5608 	bfqq->bfqd = bfqd;  in bfq_init_bfqq()
5615 		 * No need to mark as has_short_ttime if in  in bfq_init_bfqq()
5616 		 * idle_class, because no device idling is performed  in bfq_init_bfqq()
5628 	bfqq->ttime.last_end_request = now_ns + 1;  in bfq_init_bfqq()
5630 	bfqq->creation_time = jiffies;  in bfq_init_bfqq()
5632 	bfqq->io_start_time = now_ns;  in bfq_init_bfqq()
5636 	bfqq->pid = pid;  in bfq_init_bfqq()
5639 	bfqq->max_budget = (2 * bfq_max_budget(bfqd)) / 3;  in bfq_init_bfqq()
5640 	bfqq->budget_timeout = bfq_smallest_from_now();  in bfq_init_bfqq()
5642 	bfqq->wr_coeff = 1;  in bfq_init_bfqq()
5643 	bfqq->last_wr_start_finish = jiffies;  in bfq_init_bfqq()
5644 	bfqq->wr_start_at_switch_to_srt = bfq_smallest_from_now();  in bfq_init_bfqq()
5645 	bfqq->split_time = bfq_smallest_from_now();  in bfq_init_bfqq()
5651 	 * to the current value of bfqq->soft_rt_next_start (see  in bfq_init_bfqq()
5654 	 * no bandwidth so far.  in bfq_init_bfqq()
5656 	bfqq->soft_rt_next_start = jiffies;  in bfq_init_bfqq()
5659 	bfqq->seek_history = 1;  in bfq_init_bfqq()
5661 	bfqq->decrease_time_jif = jiffies;  in bfq_init_bfqq()
5670 		return &bfqg->async_bfqq[0][ioprio][act_idx];  in bfq_async_queue_prio()
5675 		return &bfqg->async_bfqq[1][ioprio][act_idx];  in bfq_async_queue_prio()
5677 		return &bfqg->async_idle_bfqq[act_idx];  in bfq_async_queue_prio()
5688 	unsigned int a_idx = last_bfqq_created->actuator_idx;  in bfq_do_early_stable_merge()
5695 	if (new_bfqq->bic)  in bfq_do_early_stable_merge()
5696 		new_bfqq->bic->bfqq_data[a_idx].stably_merged = true;  in bfq_do_early_stable_merge()
5697 	bic->bfqq_data[a_idx].stably_merged = true;  in bfq_do_early_stable_merge()
5701 	 * bfqq->bic must be set too, for  in bfq_do_early_stable_merge()
5705 	bfqq->bic = bic;  in bfq_do_early_stable_merge()
5710  * Many throughput-sensitive workloads are made of several parallel
5717  * To avoid this plugging, BFQ has been using a burst-handling
5726  * throughput of the flows and task-wide I/O latency.  In particular,
5742  * - very little time has elapsed since when Q1 was created
5743  * - Q2 has the same ioprio as Q1
5744  * - Q2 belongs to the same group as Q1
5749  * the total per-request processing time, the above throughput boost
5752  * This new mechanism most certainly obsoletes the current
5753  * burst-handling heuristics. We keep those heuristics for the moment.
5759 	struct bfq_queue **source_bfqq = bfqq->entity.parent ?  in bfq_do_or_sched_stable_merge()
5760 		&bfqq->entity.parent->last_bfqq_created :  in bfq_do_or_sched_stable_merge()
5761 		&bfqd->last_bfqq_created;  in bfq_do_or_sched_stable_merge()
5780 	 * throughput-beneficial if not merged. Currently this is  in bfq_do_or_sched_stable_merge()
5781 	 * possible only if bfqd is rotational with no queueing. For  in bfq_do_or_sched_stable_merge()
5789 	    time_before(last_bfqq_created->creation_time +  in bfq_do_or_sched_stable_merge()
5791 			bfqq->creation_time) ||  in bfq_do_or_sched_stable_merge()
5792 		bfqq->entity.parent != last_bfqq_created->entity.parent ||  in bfq_do_or_sched_stable_merge()
5793 		bfqq->ioprio != last_bfqq_created->ioprio ||  in bfq_do_or_sched_stable_merge()
5794 		bfqq->ioprio_class != last_bfqq_created->ioprio_class ||  in bfq_do_or_sched_stable_merge()
5795 		bfqq->actuator_idx != last_bfqq_created->actuator_idx)  in bfq_do_or_sched_stable_merge()
5797 	else if (time_after_eq(last_bfqq_created->creation_time +  in bfq_do_or_sched_stable_merge()
5798 				 bfqd->bfq_burst_interval,  in bfq_do_or_sched_stable_merge()
5799 				 bfqq->creation_time)) {  in bfq_do_or_sched_stable_merge()
5800 		if (likely(bfqd->nonrot_with_queueing))  in bfq_do_or_sched_stable_merge()
5803 			 * bfqq alone may provide no  in bfq_do_or_sched_stable_merge()
5816 			last_bfqq_created->ref++;  in bfq_do_or_sched_stable_merge()
5821 			last_bfqq_created->stable_ref++;  in bfq_do_or_sched_stable_merge()
5825 			bic->bfqq_data[last_bfqq_created->actuator_idx].stable_merge_bfqq =  in bfq_do_or_sched_stable_merge()
5839 	const int ioprio = IOPRIO_PRIO_LEVEL(bic->ioprio);  in bfq_get_queue()
5840 	const int ioprio_class = IOPRIO_PRIO_CLASS(bic->ioprio);  in bfq_get_queue()
5857 				     bfqd->queue->node);  in bfq_get_queue()
5860 		bfq_init_bfqq(bfqd, bfqq, bic, current->pid,  in bfq_get_queue()
5862 		bfq_init_entity(&bfqq->entity, bfqg);  in bfq_get_queue()
5865 		bfqq = &bfqd->oom_bfqq;  in bfq_get_queue()
5875 		bfqq->ref++; /*  in bfq_get_queue()
5878 			      * only if bfqq->bfqg disappears, to  in bfq_get_queue()
5883 			     bfqq, bfqq->ref);  in bfq_get_queue()
5888 	bfqq->ref++; /* get a process reference to this queue */  in bfq_get_queue()
5890 	if (bfqq != &bfqd->oom_bfqq && is_sync && !respawn)  in bfq_get_queue()
5898 	struct bfq_ttime *ttime = &bfqq->ttime;  in bfq_update_io_thinktime()
5903 	 * become busy when there is no outstanding IO for this queue. So  in bfq_update_io_thinktime()
5906 	if (bfqq->dispatched || bfq_bfqq_busy(bfqq))  in bfq_update_io_thinktime()
5908 	elapsed = blk_time_get_ns() - bfqq->ttime.last_end_request;  in bfq_update_io_thinktime()
5909 	elapsed = min_t(u64, elapsed, 2ULL * bfqd->bfq_slice_idle);  in bfq_update_io_thinktime()
5911 	ttime->ttime_samples = (7*ttime->ttime_samples + 256) / 8;  in bfq_update_io_thinktime()
5912 	ttime->ttime_total = div_u64(7*ttime->ttime_total + 256*elapsed,  8);  in bfq_update_io_thinktime()
5913 	ttime->ttime_mean = div64_ul(ttime->ttime_total + 128,  in bfq_update_io_thinktime()
5914 				     ttime->ttime_samples);  in bfq_update_io_thinktime()
5921 	bfqq->seek_history <<= 1;  in bfq_update_io_seektime()
5922 	bfqq->seek_history |= BFQ_RQ_SEEKY(bfqd, bfqq->last_request_pos, rq);  in bfq_update_io_seektime()
5924 	if (bfqq->wr_coeff > 1 &&  in bfq_update_io_seektime()
5925 	    bfqq->wr_cur_max_time == bfqd->bfq_wr_rt_max_time &&  in bfq_update_io_seektime()
5927 		if (time_is_before_jiffies(bfqq->wr_start_at_switch_to_srt +  in bfq_update_io_seektime()
5931 			 * interactive-weight-raising period  in bfq_update_io_seektime()
5932 			 * elapsed (so no switch back to  in bfq_update_io_seektime()
5943 			bfqq->entity.prio_changed = 1;  in bfq_update_io_seektime()
5955 	 * No need to update has_short_ttime if bfqq is async or in  in bfq_update_has_short_ttime()
5957 	 * no device idling is performed for bfqq in this case.  in bfq_update_has_short_ttime()
5960 	    bfqd->bfq_slice_idle == 0)  in bfq_update_has_short_ttime()
5964 	if (time_is_after_eq_jiffies(bfqq->split_time +  in bfq_update_has_short_ttime()
5965 				     bfqd->bfq_wr_min_idle_time))  in bfq_update_has_short_ttime()
5968 	/* Think time is infinite if no process is linked to  in bfq_update_has_short_ttime()
5971 	 * think time with half the I/O-plugging timeout.  in bfq_update_has_short_ttime()
5973 	if (atomic_read(&bic->icq.ioc->active_ref) == 0 ||  in bfq_update_has_short_ttime()
5974 	    (bfq_sample_valid(bfqq->ttime.ttime_samples) &&  in bfq_update_has_short_ttime()
5975 	     bfqq->ttime.ttime_mean > bfqd->bfq_slice_idle>>1))  in bfq_update_has_short_ttime()
5987 	 * finally computed for bfqq, the inject limit does depend on  in bfq_update_has_short_ttime()
5988 	 * the think-time state (short|long). In particular, the limit  in bfq_update_has_short_ttime()
5992 	 * instructions reset the inject limit if the think-time state  in bfq_update_has_short_ttime()
5997 	 * have elapsed since the last update of the inject limit, or  in bfq_update_has_short_ttime()
6011 	 * I/O-dispatch-plugging, then bfqq remains empty, and no I/O  in bfq_update_has_short_ttime()
6016 	 * On the opposite end, a non-zero inject limit may allow the  in bfq_update_has_short_ttime()
6021 	 * next think-time sample for bfqq may be very low. This in  in bfq_update_has_short_ttime()
6026 	 * limit. Without injection, the blocking I/O would cause the  in bfq_update_has_short_ttime()
6028 	 * inject limit to be raised again, and so on. The only effect  in bfq_update_has_short_ttime()
6029 	 * of such a steady oscillation between the two think-time  in bfq_update_has_short_ttime()
6032 	 * In contrast, if the inject limit is not reset during such a  in bfq_update_has_short_ttime()
6036 	 * become stable before the reset. Therefore there will be no  in bfq_update_has_short_ttime()
6037 	 * state change when the 100 ms elapse, and no reset of the  in bfq_update_has_short_ttime()
6038 	 * inject limit. The inject limit remains steadily equal to 1  in bfq_update_has_short_ttime()
6042 	 * An inject limit equal to 1 is however in conflict, in  in bfq_update_has_short_ttime()
6055 	 * more frequently than once per I/O-plugging timeout, makes  in bfq_update_has_short_ttime()
6064 	 * limit before 100 ms is that, during this time interval, the  in bfq_update_has_short_ttime()
6066 	 * finally computed for bfqq, freeing the inject limit from  in bfq_update_has_short_ttime()
6069 	if (state_changed && bfqq->last_serv_time_ns == 0 &&  in bfq_update_has_short_ttime()
6070 	    (time_is_before_eq_jiffies(bfqq->decrease_time_jif +  in bfq_update_has_short_ttime()
6083 	if (rq->cmd_flags & REQ_META)  in bfq_rq_enqueued()
6084 		bfqq->meta_pending++;  in bfq_rq_enqueued()
6086 	bfqq->last_request_pos = blk_rq_pos(rq) + blk_rq_sectors(rq);  in bfq_rq_enqueued()
6088 	if (bfqq == bfqd->in_service_queue && bfq_bfqq_wait_request(bfqq)) {  in bfq_rq_enqueued()
6089 		bool small_req = bfqq->queued[rq_is_sync(rq)] == 1 &&  in bfq_rq_enqueued()
6095 		 * - the request is small, and  in bfq_rq_enqueued()
6096 		 * - we are idling to boost throughput, and  in bfq_rq_enqueued()
6097 		 * - the queue is not to be expired,  in bfq_rq_enqueued()
6101 		 * for a new request from the in-service queue, we  in bfq_rq_enqueued()
6121 		hrtimer_try_to_cancel(&bfqd->idle_slice_timer);  in bfq_rq_enqueued()
6138 	struct bfq_entity *entity = &bfqq->entity;  in bfqq_request_allocated()
6141 		entity->allocated++;  in bfqq_request_allocated()
6146 	struct bfq_entity *entity = &bfqq->entity;  in bfqq_request_freed()
6149 		entity->allocated--;  in bfqq_request_freed()
6168 		new_bfqq->ref++;  in __bfq_insert_request()
6178 				bfq_actuator_index(bfqd, rq->bio)) == bfqq) {  in __bfq_insert_request()
6189 		rq->elv.priv[1] = new_bfqq;  in __bfq_insert_request()
6200 	rq->fifo_time = blk_time_get_ns() + bfqd->bfq_fifo_expire[rq_is_sync(rq)];  in __bfq_insert_request()
6201 	list_add_tail(&rq->queuelist, &bfqq->fifo);  in __bfq_insert_request()
6227 	spin_lock_irq(&q->queue_lock);  in bfq_update_insert_stats()
6231 	spin_unlock_irq(&q->queue_lock);  in bfq_update_insert_stats()
6245 	struct request_queue *q = hctx->queue;  in bfq_insert_request()
6246 	struct bfq_data *bfqd = q->elevator->elevator_data;  in bfq_insert_request()
6253 	if (!cgroup_subsys_on_dfl(io_cgrp_subsys) && rq->bio)  in bfq_insert_request()
6256 	spin_lock_irq(&bfqd->lock);  in bfq_insert_request()
6259 		spin_unlock_irq(&bfqd->lock);  in bfq_insert_request()
6267 		list_add(&rq->queuelist, &bfqd->dispatch);  in bfq_insert_request()
6269 		list_add_tail(&rq->queuelist, &bfqd->dispatch);  in bfq_insert_request()
6281 			if (!q->last_merge)  in bfq_insert_request()
6282 				q->last_merge = rq;  in bfq_insert_request()
6291 	cmd_flags = rq->cmd_flags;  in bfq_insert_request()
6292 	spin_unlock_irq(&bfqd->lock);  in bfq_insert_request()
6306 		list_del_init(&rq->queuelist);  in bfq_insert_requests()
6313 	struct bfq_queue *bfqq = bfqd->in_service_queue;  in bfq_update_hw_tag()
6315 	bfqd->max_rq_in_driver = max_t(int, bfqd->max_rq_in_driver,  in bfq_update_hw_tag()
6316 				       bfqd->tot_rq_in_driver);  in bfq_update_hw_tag()
6318 	if (bfqd->hw_tag == 1)  in bfq_update_hw_tag()
6327 	if (bfqd->tot_rq_in_driver + bfqd->queued <= BFQ_HW_QUEUE_THRESHOLD)  in bfq_update_hw_tag()
6336 	    bfqq->dispatched + bfqq->queued[0] + bfqq->queued[1] <  in bfq_update_hw_tag()
6338 	    bfqd->tot_rq_in_driver < BFQ_HW_QUEUE_THRESHOLD)  in bfq_update_hw_tag()
6341 	if (bfqd->hw_tag_samples++ < BFQ_HW_QUEUE_SAMPLES)  in bfq_update_hw_tag()
6344 	bfqd->hw_tag = bfqd->max_rq_in_driver > BFQ_HW_QUEUE_THRESHOLD;  in bfq_update_hw_tag()
6345 	bfqd->max_rq_in_driver = 0;  in bfq_update_hw_tag()
6346 	bfqd->hw_tag_samples = 0;  in bfq_update_hw_tag()
6348 	bfqd->nonrot_with_queueing =  in bfq_update_hw_tag()
6349 		blk_queue_nonrot(bfqd->queue) && bfqd->hw_tag;  in bfq_update_hw_tag()
6359 	bfqd->rq_in_driver[bfqq->actuator_idx]--;  in bfq_completed_request()
6360 	bfqd->tot_rq_in_driver--;  in bfq_completed_request()
6361 	bfqq->dispatched--;  in bfq_completed_request()
6363 	if (!bfqq->dispatched && !bfq_bfqq_busy(bfqq)) {  in bfq_completed_request()
6366 		 * time at which the queue remains with no backlog and  in bfq_completed_request()
6367 		 * no outstanding request; used by the weight-raising  in bfq_completed_request()
6370 		bfqq->budget_timeout = jiffies;  in bfq_completed_request()
6378 	bfqq->ttime.last_end_request = now_ns;  in bfq_completed_request()
6384 	delta_us = div_u64(now_ns - bfqd->last_completion, NSEC_PER_USEC);  in bfq_completed_request()
6395 	 * - close the observation interval at the last (previous)  in bfq_completed_request()
6397 	 * - compute rate, if possible, for that observation interval  in bfq_completed_request()
6398 	 * - reset to zero samples, which will trigger a proper  in bfq_completed_request()
6399 	 *   re-initialization of the observation interval on next  in bfq_completed_request()
6403 	   (bfqd->last_rq_max_size<<BFQ_RATE_SHIFT)/delta_us <  in bfq_completed_request()
6404 			1UL<<(BFQ_RATE_SHIFT - 10))  in bfq_completed_request()
6406 	bfqd->last_completion = now_ns;  in bfq_completed_request()
6417 		bfqd->last_completed_rq_bfqq = bfqq;  in bfq_completed_request()
6419 		bfqd->last_completed_rq_bfqq = NULL;  in bfq_completed_request()
6430 	 * expires, if it still has in-flight requests.  in bfq_completed_request()
6432 	if (bfq_bfqq_softrt_update(bfqq) && bfqq->dispatched == 0 &&  in bfq_completed_request()
6433 	    RB_EMPTY_ROOT(&bfqq->sort_list) &&  in bfq_completed_request()
6434 	    bfqq->wr_coeff != bfqd->bfq_wr_coeff)  in bfq_completed_request()
6435 		bfqq->soft_rt_next_start =  in bfq_completed_request()
6439 	 * If this is the in-service queue, check if it needs to be expired,  in bfq_completed_request()
6440 	 * or if we want to idle in case it has no pending requests.  in bfq_completed_request()
6442 	if (bfqd->in_service_queue == bfqq) {  in bfq_completed_request()
6444 			if (bfqq->dispatched == 0)  in bfq_completed_request()
6448 			 * if bfqq was in budget timeout or had no  in bfq_completed_request()
6453 			 * Here bfqq->dispatched > 0 holds, but  in bfq_completed_request()
6455 			 * implies that, even if no request arrives  in bfq_completed_request()
6456 			 * for bfqq before bfqq->dispatched reaches 0,  in bfq_completed_request()
6458 			 * completion event that causes bfqq->dispatch  in bfq_completed_request()
6461 			 * (I/O-dispatch plugging).  in bfq_completed_request()
6465 			 * when bfqq->dispatched finally reaches  in bfq_completed_request()
6473 		else if (RB_EMPTY_ROOT(&bfqq->sort_list) &&  in bfq_completed_request()
6474 			 (bfqq->dispatched == 0 ||  in bfq_completed_request()
6480 	if (!bfqd->tot_rq_in_driver)  in bfq_completed_request()
6493  * allowed to switch to another queue---because bfqq is sync and
6494  * I/O-dispatch needs to be plugged while bfqq is temporarily
6495  * empty---then, during the service of bfqq, there will be frequent
6508  * guarantees. In this respect, the mechanism maintains a per-queue
6509  * inject limit, computed as below. While bfqq is empty, the injection
6511  * of I/O requests in flight---i.e., already dispatched but not yet
6512  * completed---remains lower than this limit.
6515  * which the inject limit is computed.  We define as first request for
6517  * service, and causes bfqq to switch from empty to non-empty. The
6518  * algorithm updates the limit as a function of the effect of
6542  * The limit-update algorithm works as follows. On the arrival of a
6545  * case, it updates the limit as described below:
6547  * (1) If there is no in-flight request. This gives a baseline for the
6549  *     not been computed yet, then, after computing it, the limit is
6555  * (2) If the limit is higher than 0 and there are in-flight
6558  *     current value of the limit is inflating the total service
6560  *     is assumed to be suffering from no perceivable loss of its
6561  *     service guarantees, and the limit is even tentatively
6563  *     limit is decreased. Due to the lack of any hysteresis, this
6564  *     logic makes the limit oscillate even in steady workload
6566  *     the best value for the limit, as a function of the current I/O
6568  *     short time interval after the limit happens to be decreased.
6570  * (3) Periodically, after resetting the limit, to make sure that the
6571  *     limit eventually drops in case the workload changes. This is
6572  *     needed because, after the limit has gone safely up for a
6577  *     injection only once, and then to reset/lower the limit only if
6578  *     the total service time with the current limit does happen to be
6591 	u64 tot_time_ns = blk_time_get_ns() - bfqd->last_empty_occupied_ns;  in bfq_update_inject_limit()
6592 	unsigned int old_limit = bfqq->inject_limit;  in bfq_update_inject_limit()
6594 	if (bfqq->last_serv_time_ns > 0 && bfqd->rqs_injected) {  in bfq_update_inject_limit()
6595 		u64 threshold = (bfqq->last_serv_time_ns * 3)>>1;  in bfq_update_inject_limit()
6598 			bfqq->inject_limit--;  in bfq_update_inject_limit()
6599 			bfqq->decrease_time_jif = jiffies;  in bfq_update_inject_limit()
6601 			   old_limit <= bfqd->max_rq_in_driver)  in bfq_update_inject_limit()
6602 			bfqq->inject_limit++;  in bfq_update_inject_limit()
6611 	 * NOTE: (bfqd->tot_rq_in_driver == 1) means that there is no I/O  in bfq_update_inject_limit()
6615 	 * bfqd->tot_rq_in_driver is decremented in such a code path.  in bfq_update_inject_limit()
6617 	if ((bfqq->last_serv_time_ns == 0 && bfqd->tot_rq_in_driver == 1) ||  in bfq_update_inject_limit()
6618 	    tot_time_ns < bfqq->last_serv_time_ns) {  in bfq_update_inject_limit()
6619 		if (bfqq->last_serv_time_ns == 0) {  in bfq_update_inject_limit()
6624 			bfqq->inject_limit = max_t(unsigned int, 1, old_limit);  in bfq_update_inject_limit()
6626 		bfqq->last_serv_time_ns = tot_time_ns;  in bfq_update_inject_limit()
6627 	} else if (!bfqd->rqs_injected && bfqd->tot_rq_in_driver == 1)  in bfq_update_inject_limit()
6629 		 * No I/O injected and no request still in service in  in bfq_update_inject_limit()
6637 		bfqq->last_serv_time_ns = tot_time_ns;  in bfq_update_inject_limit()
6641 	bfqd->waited_rq = NULL;  in bfq_update_inject_limit()
6642 	bfqd->rqs_injected = false;  in bfq_update_inject_limit()
6659 	 * requeued request that has not (yet) been re-inserted into  in bfq_finish_requeue_request()
6662 	if (!rq->elv.icq || !bfqq)  in bfq_finish_requeue_request()
6665 	bfqd = bfqq->bfqd;  in bfq_finish_requeue_request()
6667 	if (rq->rq_flags & RQF_STARTED)  in bfq_finish_requeue_request()
6669 					     rq->start_time_ns,  in bfq_finish_requeue_request()
6670 					     rq->io_start_time_ns,  in bfq_finish_requeue_request()
6671 					     rq->cmd_flags);  in bfq_finish_requeue_request()
6673 	spin_lock_irqsave(&bfqd->lock, flags);  in bfq_finish_requeue_request()
6674 	if (likely(rq->rq_flags & RQF_STARTED)) {  in bfq_finish_requeue_request()
6675 		if (rq == bfqd->waited_rq)  in bfq_finish_requeue_request()
6682 	RQ_BIC(rq)->requests--;  in bfq_finish_requeue_request()
6683 	spin_unlock_irqrestore(&bfqd->lock, flags);  in bfq_finish_requeue_request()
6690 	 * design would be to prevent blk-mq from invoking the requeue  in bfq_finish_requeue_request()
6695 	 * request-insertion logic if rq is re-inserted into a bfq  in bfq_finish_requeue_request()
6696 	 * internal queue, without a re-preparation. Here we assume  in bfq_finish_requeue_request()
6697 	 * that re-insertions of requeued requests, without  in bfq_finish_requeue_request()
6698 	 * re-preparation, can happen only for pass_through or at_head  in bfq_finish_requeue_request()
6699 	 * requests (which are not re-inserted into bfq internal  in bfq_finish_requeue_request()
6702 	rq->elv.priv[0] = NULL;  in bfq_finish_requeue_request()
6703 	rq->elv.priv[1] = NULL;  in bfq_finish_requeue_request()
6710 	if (rq->elv.icq) {  in bfq_finish_request()
6711 		put_io_context(rq->elv.icq->ioc);  in bfq_finish_request()
6712 		rq->elv.icq = NULL;  in bfq_finish_request()
6717  * Removes the association between the current task and bfqq, assuming
6725 	bfq_log_bfqq(bfqq->bfqd, bfqq, "splitting queue");  in bfq_split_bfqq()
6727 	if (bfqq_process_refs(bfqq) == 1 && !bfqq->new_bfqq) {  in bfq_split_bfqq()
6728 		bfqq->pid = current->pid;  in bfq_split_bfqq()
6734 	bic_set_bfqq(bic, NULL, true, bfqq->actuator_idx);  in bfq_split_bfqq()
6747 	struct bfq_iocq_bfqq_data *bfqq_data = &bic->bfqq_data[act_idx];  in __bfq_get_bfqq_handle_split()
6749 	if (likely(bfqq && bfqq != &bfqd->oom_bfqq))  in __bfq_get_bfqq_handle_split()
6761 		if ((bfqq_data->was_in_burst_list && bfqd->large_burst) ||  in __bfq_get_bfqq_handle_split()
6762 		    bfqq_data->saved_in_large_burst)  in __bfq_get_bfqq_handle_split()
6766 			if (bfqq_data->was_in_burst_list)  in __bfq_get_bfqq_handle_split()
6768 				 * If bfqq was in the current  in __bfq_get_bfqq_handle_split()
6781 				 * current burst list is still  in __bfq_get_bfqq_handle_split()
6787 				 * bfqq to the current burst  in __bfq_get_bfqq_handle_split()
6795 				hlist_add_head(&bfqq->burst_list_node,  in __bfq_get_bfqq_handle_split()
6796 					       &bfqd->burst_list);  in __bfq_get_bfqq_handle_split()
6798 		bfqq->split_time = jiffies;  in __bfq_get_bfqq_handle_split()
6812 	rq->elv.icq = ioc_find_get_icq(rq->q);  in bfq_prepare_request()
6819 	rq->elv.priv[0] = rq->elv.priv[1] = NULL;  in bfq_prepare_request()
6824 	struct bfq_queue *new_bfqq = bfqq->new_bfqq;  in bfq_waker_bfqq()
6825 	struct bfq_queue *waker_bfqq = bfqq->waker_bfqq;  in bfq_waker_bfqq()
6833 			 * If waker_bfqq is in the merge chain, and current  in bfq_waker_bfqq()
6841 		new_bfqq = new_bfqq->new_bfqq;  in bfq_waker_bfqq()
6864 	    bic->bfqq_data[idx].stably_merged)  in bfq_get_bfqq_handle_split()
6871 		bic->bfqq_data[idx].saved_in_large_burst = true;  in bfq_get_bfqq_handle_split()
6880 	if (unlikely(bfqq == &bfqd->oom_bfqq))  in bfq_get_bfqq_handle_split()
6884 	bfqq->waker_bfqq = waker_bfqq;  in bfq_get_bfqq_handle_split()
6885 	bfqq->tentative_waker_bfqq = NULL;  in bfq_get_bfqq_handle_split()
6888 	 * If the waker queue disappears, then new_bfqq->waker_bfqq must be  in bfq_get_bfqq_handle_split()
6894 		hlist_add_head(&bfqq->woken_list_node,  in bfq_get_bfqq_handle_split()
6895 			       &bfqq->waker_bfqq->woken_list);  in bfq_get_bfqq_handle_split()
6911  * rq, rq may still be transformed into a request with no icq, i.e., a
6912  * request not associated with any queue. No bfq hook is invoked to
6919  * counters back. In contrast, no transformation can still happen for
6925 	struct request_queue *q = rq->q;  in bfq_init_rq()
6926 	struct bio *bio = rq->bio;  in bfq_init_rq()
6927 	struct bfq_data *bfqd = q->elevator->elevator_data;  in bfq_init_rq()
6933 	if (unlikely(!rq->elv.icq))  in bfq_init_rq()
6946 	bic = icq_to_bic(rq->elv.icq);  in bfq_init_rq()
6952 	bfqq->ref++;  in bfq_init_rq()
6953 	bic->requests++;  in bfq_init_rq()
6955 		     rq, bfqq, bfqq->ref);  in bfq_init_rq()
6957 	rq->elv.priv[0] = bic;  in bfq_init_rq()
6958 	rq->elv.priv[1] = bfqq;  in bfq_init_rq()
6962 	 * by only this bic: we can then set bfqq->bic = bic. in  in bfq_init_rq()
6966 	if (likely(bfqq != &bfqd->oom_bfqq) && !bfqq->new_bfqq &&  in bfq_init_rq()
6968 		bfqq->bic = bic;  in bfq_init_rq()
6973 	 * 1) A burst is actually happening (bfqd->burst_size > 0)  in bfq_init_rq()
6975 	 * 2) There is no other active queue. In fact, if, in  in bfq_init_rq()
6977 	 *    possible burst bfqq may belong to, then there is no gain  in bfq_init_rq()
6979 	 *    therefore in not weight-raising bfqq. See comments on  in bfq_init_rq()
6991 		     (bfqd->burst_size > 0 ||  in bfq_init_rq()
7004 	spin_lock_irqsave(&bfqd->lock, flags);  in bfq_idle_slice_timer_body()
7013 	if (bfqq != bfqd->in_service_queue) {  in bfq_idle_slice_timer_body()
7014 		spin_unlock_irqrestore(&bfqd->lock, flags);  in bfq_idle_slice_timer_body()
7027 	else if (bfqq->queued[0] == 0 && bfqq->queued[1] == 0)  in bfq_idle_slice_timer_body()
7031 		 * first request of the in-service queue arrives  in bfq_idle_slice_timer_body()
7042 	spin_unlock_irqrestore(&bfqd->lock, flags);  in bfq_idle_slice_timer_body()
7046  * Handler of the expiration of the timer running if the in-service queue
7053 	struct bfq_queue *bfqq = bfqd->in_service_queue;  in bfq_idle_slice_timer()
7056 	 * Theoretical race here: the in-service queue can be NULL or  in bfq_idle_slice_timer()
7058 	 * arrives for the current queue and there is a full dispatch  in bfq_idle_slice_timer()
7059 	 * cycle that changes the in-service queue.  This can hardly  in bfq_idle_slice_timer()
7076 		bfq_bfqq_move(bfqd, bfqq, bfqd->root_group);  in __bfq_put_async_bfqq()
7079 			     bfqq, bfqq->ref);  in __bfq_put_async_bfqq()
7095 	for (k = 0; k < bfqd->num_actuators; k++) {  in bfq_put_async_queues()
7098 				__bfq_put_async_bfqq(bfqd, &bfqg->async_bfqq[i][j][k]);  in bfq_put_async_queues()
7100 		__bfq_put_async_bfqq(bfqd, &bfqg->async_idle_bfqq[k]);  in bfq_put_async_queues()
7110 	unsigned int depth = 1U << bt->sb.shift;  in bfq_update_depths()
7112 	bfqd->full_depth_shift = bt->sb.shift;  in bfq_update_depths()
7114 	 * In-word depths if no bfq_queue is being weight-raised:  in bfq_update_depths()
7117 	 * In next formulas, right-shift the value  in bfq_update_depths()
7118 	 * (1U<<bt->sb.shift), instead of computing directly  in bfq_update_depths()
7119 	 * (1U<<(bt->sb.shift - something)), to be robust against  in bfq_update_depths()
7120 	 * any possible value of bt->sb.shift, without having to  in bfq_update_depths()
7121 	 * limit 'something'.  in bfq_update_depths()
7123 	/* no more than 50% of tags for async I/O */  in bfq_update_depths()
7124 	bfqd->word_depths[0][0] = max(depth >> 1, 1U);  in bfq_update_depths()
7126 	 * no more than 75% of tags for sync writes (25% extra tags  in bfq_update_depths()
7130 	bfqd->word_depths[0][1] = max((depth * 3) >> 2, 1U);  in bfq_update_depths()
7133 	 * In-word depths in case some bfq_queue is being weight-  in bfq_update_depths()
7136 	 * start-up times didn't suffer from any regression due to tag  in bfq_update_depths()
7139 	/* no more than ~18% of tags for async I/O */  in bfq_update_depths()
7140 	bfqd->word_depths[1][0] = max((depth * 3) >> 4, 1U);  in bfq_update_depths()
7141 	/* no more than ~37% of tags for sync writes (~20% extra tags) */  in bfq_update_depths()
7142 	bfqd->word_depths[1][1] = max((depth * 6) >> 4, 1U);  in bfq_update_depths()
7147 	struct bfq_data *bfqd = hctx->queue->elevator->elevator_data;  in bfq_depth_updated()
7148 	struct blk_mq_tags *tags = hctx->sched_tags;  in bfq_depth_updated()
7150 	bfq_update_depths(bfqd, &tags->bitmap_tags);  in bfq_depth_updated()
7151 	sbitmap_queue_min_shallow_depth(&tags->bitmap_tags, 1);  in bfq_depth_updated()
7162 	struct bfq_data *bfqd = e->elevator_data;  in bfq_exit_queue()
7166 	hrtimer_cancel(&bfqd->idle_slice_timer);  in bfq_exit_queue()
7168 	spin_lock_irq(&bfqd->lock);  in bfq_exit_queue()
7169 	list_for_each_entry_safe(bfqq, n, &bfqd->idle_list, bfqq_list)  in bfq_exit_queue()
7171 	spin_unlock_irq(&bfqd->lock);  in bfq_exit_queue()
7173 	for (actuator = 0; actuator < bfqd->num_actuators; actuator++)  in bfq_exit_queue()
7174 		WARN_ON_ONCE(bfqd->rq_in_driver[actuator]);  in bfq_exit_queue()
7175 	WARN_ON_ONCE(bfqd->tot_rq_in_driver);  in bfq_exit_queue()
7177 	hrtimer_cancel(&bfqd->idle_slice_timer);  in bfq_exit_queue()
7179 	/* release oom-queue reference to root group */  in bfq_exit_queue()
7180 	bfqg_and_blkg_put(bfqd->root_group);  in bfq_exit_queue()
7183 	blkcg_deactivate_policy(bfqd->queue->disk, &blkcg_policy_bfq);  in bfq_exit_queue()
7185 	spin_lock_irq(&bfqd->lock);  in bfq_exit_queue()
7186 	bfq_put_async_queues(bfqd, bfqd->root_group);  in bfq_exit_queue()
7187 	kfree(bfqd->root_group);  in bfq_exit_queue()
7188 	spin_unlock_irq(&bfqd->lock);  in bfq_exit_queue()
7191 	blk_stat_disable_accounting(bfqd->queue);  in bfq_exit_queue()
7192 	clear_bit(ELEVATOR_FLAG_DISABLE_WBT, &e->flags);  in bfq_exit_queue()
7193 	wbt_enable_default(bfqd->queue->disk);  in bfq_exit_queue()
7204 	root_group->entity.parent = NULL;  in bfq_init_root_group()
7205 	root_group->my_entity = NULL;  in bfq_init_root_group()
7206 	root_group->bfqd = bfqd;  in bfq_init_root_group()
7208 	root_group->rq_pos_tree = RB_ROOT;  in bfq_init_root_group()
7210 		root_group->sched_data.service_tree[i] = BFQ_SERVICE_TREE_INIT;  in bfq_init_root_group()
7211 	root_group->sched_data.bfq_class_idle_last_service = jiffies;  in bfq_init_root_group()
7219 	struct blk_independent_access_ranges *ia_ranges = q->disk->ia_ranges;  in bfq_init_queue()
7223 		return -ENOMEM;  in bfq_init_queue()
7225 	bfqd = kzalloc_node(sizeof(*bfqd), GFP_KERNEL, q->node);  in bfq_init_queue()
7227 		kobject_put(&eq->kobj);  in bfq_init_queue()
7228 		return -ENOMEM;  in bfq_init_queue()
7230 	eq->elevator_data = bfqd;  in bfq_init_queue()
7232 	spin_lock_irq(&q->queue_lock);  in bfq_init_queue()
7233 	q->elevator = eq;  in bfq_init_queue()
7234 	spin_unlock_irq(&q->queue_lock);  in bfq_init_queue()
7243 	bfq_init_bfqq(bfqd, &bfqd->oom_bfqq, NULL, 1, 0, 0);  in bfq_init_queue()
7244 	bfqd->oom_bfqq.ref++;  in bfq_init_queue()
7245 	bfqd->oom_bfqq.new_ioprio = BFQ_DEFAULT_QUEUE_IOPRIO;  in bfq_init_queue()
7246 	bfqd->oom_bfqq.new_ioprio_class = IOPRIO_CLASS_BE;  in bfq_init_queue()
7247 	bfqd->oom_bfqq.entity.new_weight =  in bfq_init_queue()
7248 		bfq_ioprio_to_weight(bfqd->oom_bfqq.new_ioprio);  in bfq_init_queue()
7251 	bfq_clear_bfqq_just_created(&bfqd->oom_bfqq);  in bfq_init_queue()
7258 	bfqd->oom_bfqq.entity.prio_changed = 1;  in bfq_init_queue()
7260 	bfqd->queue = q;  in bfq_init_queue()
7262 	bfqd->num_actuators = 1;  in bfq_init_queue()
7267 	spin_lock_irq(&q->queue_lock);  in bfq_init_queue()
7270 		 * Check if the disk ia_ranges size exceeds the current bfq  in bfq_init_queue()
7271 		 * actuator limit.  in bfq_init_queue()
7273 		if (ia_ranges->nr_ia_ranges > BFQ_MAX_ACTUATORS) {  in bfq_init_queue()
7274 			pr_crit("nr_ia_ranges higher than act limit: iars=%d, max=%d.\n",  in bfq_init_queue()
7275 				ia_ranges->nr_ia_ranges, BFQ_MAX_ACTUATORS);  in bfq_init_queue()
7278 			bfqd->num_actuators = ia_ranges->nr_ia_ranges;  in bfq_init_queue()
7280 			for (i = 0; i < bfqd->num_actuators; i++) {  in bfq_init_queue()
7281 				bfqd->sector[i] = ia_ranges->ia_range[i].sector;  in bfq_init_queue()
7282 				bfqd->nr_sectors[i] =  in bfq_init_queue()
7283 					ia_ranges->ia_range[i].nr_sectors;  in bfq_init_queue()
7288 	/* Otherwise use single-actuator dev info */  in bfq_init_queue()
7289 	if (bfqd->num_actuators == 1) {  in bfq_init_queue()
7290 		bfqd->sector[0] = 0;  in bfq_init_queue()
7291 		bfqd->nr_sectors[0] = get_capacity(q->disk);  in bfq_init_queue()
7293 	spin_unlock_irq(&q->queue_lock);  in bfq_init_queue()
7295 	INIT_LIST_HEAD(&bfqd->dispatch);  in bfq_init_queue()
7297 	hrtimer_init(&bfqd->idle_slice_timer, CLOCK_MONOTONIC,  in bfq_init_queue()
7299 	bfqd->idle_slice_timer.function = bfq_idle_slice_timer;  in bfq_init_queue()
7301 	bfqd->queue_weights_tree = RB_ROOT_CACHED;  in bfq_init_queue()
7303 	bfqd->num_groups_with_pending_reqs = 0;  in bfq_init_queue()
7306 	INIT_LIST_HEAD(&bfqd->active_list[0]);  in bfq_init_queue()
7307 	INIT_LIST_HEAD(&bfqd->active_list[1]);  in bfq_init_queue()
7308 	INIT_LIST_HEAD(&bfqd->idle_list);  in bfq_init_queue()
7309 	INIT_HLIST_HEAD(&bfqd->burst_list);  in bfq_init_queue()
7311 	bfqd->hw_tag = -1;  in bfq_init_queue()
7312 	bfqd->nonrot_with_queueing = blk_queue_nonrot(bfqd->queue);  in bfq_init_queue()
7314 	bfqd->bfq_max_budget = bfq_default_max_budget;  in bfq_init_queue()
7316 	bfqd->bfq_fifo_expire[0] = bfq_fifo_expire[0];  in bfq_init_queue()
7317 	bfqd->bfq_fifo_expire[1] = bfq_fifo_expire[1];  in bfq_init_queue()
7318 	bfqd->bfq_back_max = bfq_back_max;  in bfq_init_queue()
7319 	bfqd->bfq_back_penalty = bfq_back_penalty;  in bfq_init_queue()
7320 	bfqd->bfq_slice_idle = bfq_slice_idle;  in bfq_init_queue()
7321 	bfqd->bfq_timeout = bfq_timeout;  in bfq_init_queue()
7323 	bfqd->bfq_large_burst_thresh = 8;  in bfq_init_queue()
7324 	bfqd->bfq_burst_interval = msecs_to_jiffies(180);  in bfq_init_queue()
7326 	bfqd->low_latency = true;  in bfq_init_queue()
7329 	 * Trade-off between responsiveness and fairness.  in bfq_init_queue()
7331 	bfqd->bfq_wr_coeff = 30;  in bfq_init_queue()
7332 	bfqd->bfq_wr_rt_max_time = msecs_to_jiffies(300);  in bfq_init_queue()
7333 	bfqd->bfq_wr_min_idle_time = msecs_to_jiffies(2000);  in bfq_init_queue()
7334 	bfqd->bfq_wr_min_inter_arr_async = msecs_to_jiffies(500);  in bfq_init_queue()
7335 	bfqd->bfq_wr_max_softrt_rate = 7000; /*  in bfq_init_queue()
7338 					      * high-definition compressed  in bfq_init_queue()
7341 	bfqd->wr_busy_queues = 0;  in bfq_init_queue()
7347 	bfqd->rate_dur_prod = ref_rate[blk_queue_nonrot(bfqd->queue)] *  in bfq_init_queue()
7348 		ref_wr_duration[blk_queue_nonrot(bfqd->queue)];  in bfq_init_queue()
7349 	bfqd->peak_rate = ref_rate[blk_queue_nonrot(bfqd->queue)] * 2 / 3;  in bfq_init_queue()
7352 	bfqd->actuator_load_threshold = 4;  in bfq_init_queue()
7354 	spin_lock_init(&bfqd->lock);  in bfq_init_queue()
7359 	 * (bfq_create_group_hierarchy->blkcg_activate_policy->  in bfq_init_queue()
7367 	 * other inconsistencies, the blk-mq stack must then refrain  in bfq_init_queue()
7371 	bfqd->root_group = bfq_create_group_hierarchy(bfqd, q->node);  in bfq_init_queue()
7372 	if (!bfqd->root_group)  in bfq_init_queue()
7374 	bfq_init_root_group(bfqd->root_group, bfqd);  in bfq_init_queue()
7375 	bfq_init_entity(&bfqd->oom_bfqq.entity, bfqd->root_group);  in bfq_init_queue()
7380 	set_bit(ELEVATOR_FLAG_DISABLE_WBT, &eq->flags);  in bfq_init_queue()
7381 	wbt_disable_default(q->disk);  in bfq_init_queue()
7388 	kobject_put(&eq->kobj);  in bfq_init_queue()
7389 	return -ENOMEM;  in bfq_init_queue()
7401 		return -ENOMEM;  in bfq_slab_setup()
7424 	struct bfq_data *bfqd = e->elevator_data;			\
7432 SHOW_FUNCTION(bfq_fifo_expire_sync_show, bfqd->bfq_fifo_expire[1], 2);
7433 SHOW_FUNCTION(bfq_fifo_expire_async_show, bfqd->bfq_fifo_expire[0], 2);
7434 SHOW_FUNCTION(bfq_back_seek_max_show, bfqd->bfq_back_max, 0);
7435 SHOW_FUNCTION(bfq_back_seek_penalty_show, bfqd->bfq_back_penalty, 0);
7436 SHOW_FUNCTION(bfq_slice_idle_show, bfqd->bfq_slice_idle, 2);
7437 SHOW_FUNCTION(bfq_max_budget_show, bfqd->bfq_user_max_budget, 0);
7438 SHOW_FUNCTION(bfq_timeout_sync_show, bfqd->bfq_timeout, 1);
7439 SHOW_FUNCTION(bfq_strict_guarantees_show, bfqd->strict_guarantees, 0);
7440 SHOW_FUNCTION(bfq_low_latency_show, bfqd->low_latency, 0);
7446 	struct bfq_data *bfqd = e->elevator_data;			\
7451 USEC_SHOW_FUNCTION(bfq_slice_idle_us_show, bfqd->bfq_slice_idle);
7458 	struct bfq_data *bfqd = e->elevator_data;			\
7477 STORE_FUNCTION(bfq_fifo_expire_sync_store, &bfqd->bfq_fifo_expire[1], 1,
7479 STORE_FUNCTION(bfq_fifo_expire_async_store, &bfqd->bfq_fifo_expire[0], 1,
7481 STORE_FUNCTION(bfq_back_seek_max_store, &bfqd->bfq_back_max, 0, INT_MAX, 0);
7482 STORE_FUNCTION(bfq_back_seek_penalty_store, &bfqd->bfq_back_penalty, 1,
7484 STORE_FUNCTION(bfq_slice_idle_store, &bfqd->bfq_slice_idle, 0, INT_MAX, 2);
7490 	struct bfq_data *bfqd = e->elevator_data;			\
7504 USEC_STORE_FUNCTION(bfq_slice_idle_us_store, &bfqd->bfq_slice_idle, 0,
7511 	struct bfq_data *bfqd = e->elevator_data;  in bfq_max_budget_store()
7520 		bfqd->bfq_max_budget = bfq_calc_max_budget(bfqd);  in bfq_max_budget_store()
7524 		bfqd->bfq_max_budget = __data;  in bfq_max_budget_store()
7527 	bfqd->bfq_user_max_budget = __data;  in bfq_max_budget_store()
7539 	struct bfq_data *bfqd = e->elevator_data;  in bfq_timeout_sync_store()
7552 	bfqd->bfq_timeout = msecs_to_jiffies(__data);  in bfq_timeout_sync_store()
7553 	if (bfqd->bfq_user_max_budget == 0)  in bfq_timeout_sync_store()
7554 		bfqd->bfq_max_budget = bfq_calc_max_budget(bfqd);  in bfq_timeout_sync_store()
7562 	struct bfq_data *bfqd = e->elevator_data;  in bfq_strict_guarantees_store()
7572 	if (!bfqd->strict_guarantees && __data == 1  in bfq_strict_guarantees_store()
7573 	    && bfqd->bfq_slice_idle < 8 * NSEC_PER_MSEC)  in bfq_strict_guarantees_store()
7574 		bfqd->bfq_slice_idle = 8 * NSEC_PER_MSEC;  in bfq_strict_guarantees_store()
7576 	bfqd->strict_guarantees = __data;  in bfq_strict_guarantees_store()
7584 	struct bfq_data *bfqd = e->elevator_data;  in bfq_low_latency_store()
7594 	if (__data == 0 && bfqd->low_latency != 0)  in bfq_low_latency_store()
7596 	bfqd->low_latency = __data;  in bfq_low_latency_store()
7647 MODULE_ALIAS("bfq-iosched");
7659 	ret = -ENOMEM;  in bfq_init()
7673 	 * scheduler cannot rely on a peak-rate-evaluation workload to  in bfq_init()