144 void bfq_mark_bfqq_##name(struct bfq_queue *bfqq)			\
146 	__set_bit(BFQQF_##name, &(bfqq)->flags);			\
148 void bfq_clear_bfqq_##name(struct bfq_queue *bfqq)			\
150 	__clear_bit(BFQQF_##name, &(bfqq)->flags);		\
152 int bfq_bfqq_##name(const struct bfq_queue *bfqq)			\
154 	return test_bit(BFQQF_##name, &(bfqq)->flags);		\
239 #define BFQQ_SEEKY(bfqq)	(hweight32(bfqq->seek_history) > 19)  argument
365 	return bic->bfqq[is_sync];  in bic_to_bfqq()
368 void bic_set_bfqq(struct bfq_io_cq *bic, struct bfq_queue *bfqq, bool is_sync)  in bic_set_bfqq()  argument
370 	bic->bfqq[is_sync] = bfqq;  in bic_set_bfqq()
424 #define bfq_class_idle(bfqq)	((bfqq)->ioprio_class == IOPRIO_CLASS_IDLE)  argument
425 #define bfq_class_rt(bfqq)	((bfqq)->ioprio_class == IOPRIO_CLASS_RT)  argument
551 	struct bfq_queue *bfqq = NULL;  in bfq_rq_pos_tree_lookup()  local
559 		bfqq = rb_entry(parent, struct bfq_queue, pos_node);  in bfq_rq_pos_tree_lookup()
565 		if (sector > blk_rq_pos(bfqq->next_rq))  in bfq_rq_pos_tree_lookup()
567 		else if (sector < blk_rq_pos(bfqq->next_rq))  in bfq_rq_pos_tree_lookup()
572 		bfqq = NULL;  in bfq_rq_pos_tree_lookup()
581 		bfqq ? bfqq->pid : 0);  in bfq_rq_pos_tree_lookup()
583 	return bfqq;  in bfq_rq_pos_tree_lookup()
586 static bool bfq_too_late_for_merging(struct bfq_queue *bfqq)  in bfq_too_late_for_merging()  argument
588 	return bfqq->service_from_backlogged > 0 &&  in bfq_too_late_for_merging()
589 		time_is_before_jiffies(bfqq->first_IO_time +  in bfq_too_late_for_merging()
593 void bfq_pos_tree_add_move(struct bfq_data *bfqd, struct bfq_queue *bfqq)  in bfq_pos_tree_add_move()  argument
598 	if (bfqq->pos_root) {  in bfq_pos_tree_add_move()
599 		rb_erase(&bfqq->pos_node, bfqq->pos_root);  in bfq_pos_tree_add_move()
600 		bfqq->pos_root = NULL;  in bfq_pos_tree_add_move()
608 	if (bfq_too_late_for_merging(bfqq))  in bfq_pos_tree_add_move()
611 	if (bfq_class_idle(bfqq))  in bfq_pos_tree_add_move()
613 	if (!bfqq->next_rq)  in bfq_pos_tree_add_move()
616 	bfqq->pos_root = &bfq_bfqq_to_bfqg(bfqq)->rq_pos_tree;  in bfq_pos_tree_add_move()
617 	__bfqq = bfq_rq_pos_tree_lookup(bfqd, bfqq->pos_root,  in bfq_pos_tree_add_move()
618 			blk_rq_pos(bfqq->next_rq), &parent, &p);  in bfq_pos_tree_add_move()
620 		rb_link_node(&bfqq->pos_node, parent, p);  in bfq_pos_tree_add_move()
621 		rb_insert_color(&bfqq->pos_node, bfqq->pos_root);  in bfq_pos_tree_add_move()
623 		bfqq->pos_root = NULL;  in bfq_pos_tree_add_move()
782 			     struct bfq_queue *bfqq)  in bfq_weights_tree_remove()  argument
784 	struct bfq_entity *entity = bfqq->entity.parent;  in bfq_weights_tree_remove()
786 	__bfq_weights_tree_remove(bfqd, &bfqq->entity,  in bfq_weights_tree_remove()
817 static struct request *bfq_check_fifo(struct bfq_queue *bfqq,  in bfq_check_fifo()  argument
822 	if (bfq_bfqq_fifo_expire(bfqq))  in bfq_check_fifo()
825 	bfq_mark_bfqq_fifo_expire(bfqq);  in bfq_check_fifo()
827 	rq = rq_entry_fifo(bfqq->fifo.next);  in bfq_check_fifo()
832 	bfq_log_bfqq(bfqq->bfqd, bfqq, "check_fifo: returned %p", rq);  in bfq_check_fifo()
837 					struct bfq_queue *bfqq,  in bfq_find_next_rq()  argument
845 	next = bfq_check_fifo(bfqq, last);  in bfq_find_next_rq()
855 		rbnext = rb_first(&bfqq->sort_list);  in bfq_find_next_rq()
865 					struct bfq_queue *bfqq)  in bfq_serv_to_charge()  argument
867 	if (bfq_bfqq_sync(bfqq) || bfqq->wr_coeff > 1)  in bfq_serv_to_charge()
885 				 struct bfq_queue *bfqq)  in bfq_updated_next_req()  argument
887 	struct bfq_entity *entity = &bfqq->entity;  in bfq_updated_next_req()
888 	struct request *next_rq = bfqq->next_rq;  in bfq_updated_next_req()
894 	if (bfqq == bfqd->in_service_queue)  in bfq_updated_next_req()
901 	new_budget = max_t(unsigned long, bfqq->max_budget,  in bfq_updated_next_req()
902 			   bfq_serv_to_charge(next_rq, bfqq));  in bfq_updated_next_req()
905 		bfq_log_bfqq(bfqd, bfqq, "updated next rq: new budget %lu",  in bfq_updated_next_req()
907 		bfq_requeue_bfqq(bfqd, bfqq, false);  in bfq_updated_next_req()
945 static void switch_back_to_interactive_wr(struct bfq_queue *bfqq,  in switch_back_to_interactive_wr()  argument
948 	bfqq->wr_coeff = bfqd->bfq_wr_coeff;  in switch_back_to_interactive_wr()
949 	bfqq->wr_cur_max_time = bfq_wr_duration(bfqd);  in switch_back_to_interactive_wr()
950 	bfqq->last_wr_start_finish = bfqq->wr_start_at_switch_to_srt;  in switch_back_to_interactive_wr()
954 bfq_bfqq_resume_state(struct bfq_queue *bfqq, struct bfq_data *bfqd,  in bfq_bfqq_resume_state()  argument
957 	unsigned int old_wr_coeff = bfqq->wr_coeff;  in bfq_bfqq_resume_state()
958 	bool busy = bfq_already_existing && bfq_bfqq_busy(bfqq);  in bfq_bfqq_resume_state()
961 		bfq_mark_bfqq_has_short_ttime(bfqq);  in bfq_bfqq_resume_state()
963 		bfq_clear_bfqq_has_short_ttime(bfqq);  in bfq_bfqq_resume_state()
966 		bfq_mark_bfqq_IO_bound(bfqq);  in bfq_bfqq_resume_state()
968 		bfq_clear_bfqq_IO_bound(bfqq);  in bfq_bfqq_resume_state()
970 	bfqq->ttime = bic->saved_ttime;  in bfq_bfqq_resume_state()
971 	bfqq->wr_coeff = bic->saved_wr_coeff;  in bfq_bfqq_resume_state()
972 	bfqq->wr_start_at_switch_to_srt = bic->saved_wr_start_at_switch_to_srt;  in bfq_bfqq_resume_state()
973 	bfqq->last_wr_start_finish = bic->saved_last_wr_start_finish;  in bfq_bfqq_resume_state()
974 	bfqq->wr_cur_max_time = bic->saved_wr_cur_max_time;  in bfq_bfqq_resume_state()
976 	if (bfqq->wr_coeff > 1 && (bfq_bfqq_in_large_burst(bfqq) ||  in bfq_bfqq_resume_state()
977 	    time_is_before_jiffies(bfqq->last_wr_start_finish +  in bfq_bfqq_resume_state()
978 				   bfqq->wr_cur_max_time))) {  in bfq_bfqq_resume_state()
979 		if (bfqq->wr_cur_max_time == bfqd->bfq_wr_rt_max_time &&  in bfq_bfqq_resume_state()
980 		    !bfq_bfqq_in_large_burst(bfqq) &&  in bfq_bfqq_resume_state()
981 		    time_is_after_eq_jiffies(bfqq->wr_start_at_switch_to_srt +  in bfq_bfqq_resume_state()
983 			switch_back_to_interactive_wr(bfqq, bfqd);  in bfq_bfqq_resume_state()
985 			bfqq->wr_coeff = 1;  in bfq_bfqq_resume_state()
986 			bfq_log_bfqq(bfqq->bfqd, bfqq,  in bfq_bfqq_resume_state()
992 	bfqq->entity.prio_changed = 1;  in bfq_bfqq_resume_state()
997 	if (old_wr_coeff == 1 && bfqq->wr_coeff > 1)  in bfq_bfqq_resume_state()
999 	else if (old_wr_coeff > 1 && bfqq->wr_coeff == 1)  in bfq_bfqq_resume_state()
1003 static int bfqq_process_refs(struct bfq_queue *bfqq)  in bfqq_process_refs()  argument
1005 	return bfqq->ref - bfqq->allocated - bfqq->entity.on_st;  in bfqq_process_refs()
1009 static void bfq_reset_burst_list(struct bfq_data *bfqd, struct bfq_queue *bfqq)  in bfq_reset_burst_list()  argument
1016 	hlist_add_head(&bfqq->burst_list_node, &bfqd->burst_list);  in bfq_reset_burst_list()
1018 	bfqd->burst_parent_entity = bfqq->entity.parent;  in bfq_reset_burst_list()
1022 static void bfq_add_to_burst(struct bfq_data *bfqd, struct bfq_queue *bfqq)  in bfq_add_to_burst()  argument
1044 		bfq_mark_bfqq_in_large_burst(bfqq);  in bfq_add_to_burst()
1062 		hlist_add_head(&bfqq->burst_list_node, &bfqd->burst_list);  in bfq_add_to_burst()
1168 static void bfq_handle_burst(struct bfq_data *bfqd, struct bfq_queue *bfqq)  in bfq_handle_burst()  argument
1175 	if (!hlist_unhashed(&bfqq->burst_list_node) ||  in bfq_handle_burst()
1176 	    bfq_bfqq_in_large_burst(bfqq) ||  in bfq_handle_burst()
1177 	    time_is_after_eq_jiffies(bfqq->split_time +  in bfq_handle_burst()
1200 	    bfqq->entity.parent != bfqd->burst_parent_entity) {  in bfq_handle_burst()
1202 		bfq_reset_burst_list(bfqd, bfqq);  in bfq_handle_burst()
1212 		bfq_mark_bfqq_in_large_burst(bfqq);  in bfq_handle_burst()
1221 	bfq_add_to_burst(bfqd, bfqq);  in bfq_handle_burst()
1234 static int bfq_bfqq_budget_left(struct bfq_queue *bfqq)  in bfq_bfqq_budget_left()  argument
1236 	struct bfq_entity *entity = &bfqq->entity;  in bfq_bfqq_budget_left()
1368 						struct bfq_queue *bfqq,  in bfq_bfqq_update_budg_for_activation()  argument
1372 	struct bfq_entity *entity = &bfqq->entity;  in bfq_bfqq_update_budg_for_activation()
1374 	if (bfq_bfqq_non_blocking_wait_rq(bfqq) && arrived_in_time) {  in bfq_bfqq_update_budg_for_activation()
1393 				       bfq_bfqq_budget_left(bfqq),  in bfq_bfqq_update_budg_for_activation()
1394 				       bfqq->max_budget);  in bfq_bfqq_update_budg_for_activation()
1414 	entity->budget = max_t(unsigned long, bfqq->max_budget,  in bfq_bfqq_update_budg_for_activation()
1415 			       bfq_serv_to_charge(bfqq->next_rq, bfqq));  in bfq_bfqq_update_budg_for_activation()
1416 	bfq_clear_bfqq_non_blocking_wait_rq(bfqq);  in bfq_bfqq_update_budg_for_activation()
1430 					     struct bfq_queue *bfqq,  in bfq_update_bfqq_wr_on_rq_arrival()  argument
1440 			bfqq->service_from_wr = 0;  in bfq_update_bfqq_wr_on_rq_arrival()
1441 			bfqq->wr_coeff = bfqd->bfq_wr_coeff;  in bfq_update_bfqq_wr_on_rq_arrival()
1442 			bfqq->wr_cur_max_time = bfq_wr_duration(bfqd);  in bfq_update_bfqq_wr_on_rq_arrival()
1455 			bfqq->wr_start_at_switch_to_srt =  in bfq_update_bfqq_wr_on_rq_arrival()
1457 			bfqq->wr_coeff = bfqd->bfq_wr_coeff *  in bfq_update_bfqq_wr_on_rq_arrival()
1459 			bfqq->wr_cur_max_time =  in bfq_update_bfqq_wr_on_rq_arrival()
1472 		bfqq->entity.budget = min_t(unsigned long,  in bfq_update_bfqq_wr_on_rq_arrival()
1473 					    bfqq->entity.budget,  in bfq_update_bfqq_wr_on_rq_arrival()
1477 			bfqq->wr_coeff = bfqd->bfq_wr_coeff;  in bfq_update_bfqq_wr_on_rq_arrival()
1478 			bfqq->wr_cur_max_time = bfq_wr_duration(bfqd);  in bfq_update_bfqq_wr_on_rq_arrival()
1480 			bfqq->wr_coeff = 1;  in bfq_update_bfqq_wr_on_rq_arrival()
1511 			if (bfqq->wr_cur_max_time !=  in bfq_update_bfqq_wr_on_rq_arrival()
1513 				bfqq->wr_start_at_switch_to_srt =  in bfq_update_bfqq_wr_on_rq_arrival()
1514 					bfqq->last_wr_start_finish;  in bfq_update_bfqq_wr_on_rq_arrival()
1516 				bfqq->wr_cur_max_time =  in bfq_update_bfqq_wr_on_rq_arrival()
1518 				bfqq->wr_coeff = bfqd->bfq_wr_coeff *  in bfq_update_bfqq_wr_on_rq_arrival()
1521 			bfqq->last_wr_start_finish = jiffies;  in bfq_update_bfqq_wr_on_rq_arrival()
1527 					struct bfq_queue *bfqq)  in bfq_bfqq_idle_for_long_time()  argument
1529 	return bfqq->dispatched == 0 &&  in bfq_bfqq_idle_for_long_time()
1531 			bfqq->budget_timeout +  in bfq_bfqq_idle_for_long_time()
1536 					     struct bfq_queue *bfqq,  in bfq_bfqq_handle_idle_busy_switch()  argument
1543 		idle_for_long_time = bfq_bfqq_idle_for_long_time(bfqd, bfqq),  in bfq_bfqq_handle_idle_busy_switch()
1550 			bfqq->ttime.last_end_request +  in bfq_bfqq_handle_idle_busy_switch()
1561 	in_burst = bfq_bfqq_in_large_burst(bfqq);  in bfq_bfqq_handle_idle_busy_switch()
1564 		time_is_before_jiffies(bfqq->soft_rt_next_start) &&  in bfq_bfqq_handle_idle_busy_switch()
1565 		bfqq->dispatched == 0;  in bfq_bfqq_handle_idle_busy_switch()
1568 		(bfqq->wr_coeff > 1 ||  in bfq_bfqq_handle_idle_busy_switch()
1569 		 (bfq_bfqq_sync(bfqq) &&  in bfq_bfqq_handle_idle_busy_switch()
1570 		  bfqq->bic && (*interactive || soft_rt)));  in bfq_bfqq_handle_idle_busy_switch()
1577 		bfq_bfqq_update_budg_for_activation(bfqd, bfqq,  in bfq_bfqq_handle_idle_busy_switch()
1594 	if (likely(!bfq_bfqq_just_created(bfqq)) &&  in bfq_bfqq_handle_idle_busy_switch()
1597 		    bfqq->budget_timeout +  in bfq_bfqq_handle_idle_busy_switch()
1599 		hlist_del_init(&bfqq->burst_list_node);  in bfq_bfqq_handle_idle_busy_switch()
1600 		bfq_clear_bfqq_in_large_burst(bfqq);  in bfq_bfqq_handle_idle_busy_switch()
1603 	bfq_clear_bfqq_just_created(bfqq);  in bfq_bfqq_handle_idle_busy_switch()
1606 	if (!bfq_bfqq_IO_bound(bfqq)) {  in bfq_bfqq_handle_idle_busy_switch()
1608 			bfqq->requests_within_timer++;  in bfq_bfqq_handle_idle_busy_switch()
1609 			if (bfqq->requests_within_timer >=  in bfq_bfqq_handle_idle_busy_switch()
1611 				bfq_mark_bfqq_IO_bound(bfqq);  in bfq_bfqq_handle_idle_busy_switch()
1613 			bfqq->requests_within_timer = 0;  in bfq_bfqq_handle_idle_busy_switch()
1617 		if (unlikely(time_is_after_jiffies(bfqq->split_time)))  in bfq_bfqq_handle_idle_busy_switch()
1619 			bfqq->split_time =  in bfq_bfqq_handle_idle_busy_switch()
1622 		if (time_is_before_jiffies(bfqq->split_time +  in bfq_bfqq_handle_idle_busy_switch()
1624 			bfq_update_bfqq_wr_on_rq_arrival(bfqd, bfqq,  in bfq_bfqq_handle_idle_busy_switch()
1631 			if (old_wr_coeff != bfqq->wr_coeff)  in bfq_bfqq_handle_idle_busy_switch()
1632 				bfqq->entity.prio_changed = 1;  in bfq_bfqq_handle_idle_busy_switch()
1636 	bfqq->last_idle_bklogged = jiffies;  in bfq_bfqq_handle_idle_busy_switch()
1637 	bfqq->service_from_backlogged = 0;  in bfq_bfqq_handle_idle_busy_switch()
1638 	bfq_clear_bfqq_softrt_update(bfqq);  in bfq_bfqq_handle_idle_busy_switch()
1640 	bfq_add_bfqq_busy(bfqd, bfqq);  in bfq_bfqq_handle_idle_busy_switch()
1653 	    bfqd->in_service_queue->wr_coeff < bfqq->wr_coeff &&  in bfq_bfqq_handle_idle_busy_switch()
1661 	struct bfq_queue *bfqq = RQ_BFQQ(rq);  in bfq_add_request()  local
1662 	struct bfq_data *bfqd = bfqq->bfqd;  in bfq_add_request()
1664 	unsigned int old_wr_coeff = bfqq->wr_coeff;  in bfq_add_request()
1667 	bfq_log_bfqq(bfqd, bfqq, "add_request %d", rq_is_sync(rq));  in bfq_add_request()
1668 	bfqq->queued[rq_is_sync(rq)]++;  in bfq_add_request()
1671 	elv_rb_add(&bfqq->sort_list, rq);  in bfq_add_request()
1676 	prev = bfqq->next_rq;  in bfq_add_request()
1677 	next_rq = bfq_choose_req(bfqd, bfqq->next_rq, rq, bfqd->last_position);  in bfq_add_request()
1678 	bfqq->next_rq = next_rq;  in bfq_add_request()
1683 	if (prev != bfqq->next_rq)  in bfq_add_request()
1684 		bfq_pos_tree_add_move(bfqd, bfqq);  in bfq_add_request()
1686 	if (!bfq_bfqq_busy(bfqq)) /* switching to busy ... */  in bfq_add_request()
1687 		bfq_bfqq_handle_idle_busy_switch(bfqd, bfqq, old_wr_coeff,  in bfq_add_request()
1692 				bfqq->last_wr_start_finish +  in bfq_add_request()
1694 			bfqq->wr_coeff = bfqd->bfq_wr_coeff;  in bfq_add_request()
1695 			bfqq->wr_cur_max_time = bfq_wr_duration(bfqd);  in bfq_add_request()
1698 			bfqq->entity.prio_changed = 1;  in bfq_add_request()
1700 		if (prev != bfqq->next_rq)  in bfq_add_request()
1701 			bfq_updated_next_req(bfqd, bfqq);  in bfq_add_request()
1731 		(old_wr_coeff == 1 || bfqq->wr_coeff == 1 || interactive))  in bfq_add_request()
1732 		bfqq->last_wr_start_finish = jiffies;  in bfq_add_request()
1739 	struct bfq_queue *bfqq = bfqd->bio_bfqq;  in bfq_find_rq_fmerge()  local
1742 	if (bfqq)  in bfq_find_rq_fmerge()
1743 		return elv_rb_find(&bfqq->sort_list, bio_end_sector(bio));  in bfq_find_rq_fmerge()
1775 	struct bfq_queue *bfqq = RQ_BFQQ(rq);  in bfq_remove_request()  local
1776 	struct bfq_data *bfqd = bfqq->bfqd;  in bfq_remove_request()
1779 	if (bfqq->next_rq == rq) {  in bfq_remove_request()
1780 		bfqq->next_rq = bfq_find_next_rq(bfqd, bfqq, rq);  in bfq_remove_request()
1781 		bfq_updated_next_req(bfqd, bfqq);  in bfq_remove_request()
1786 	bfqq->queued[sync]--;  in bfq_remove_request()
1788 	elv_rb_del(&bfqq->sort_list, rq);  in bfq_remove_request()
1794 	if (RB_EMPTY_ROOT(&bfqq->sort_list)) {  in bfq_remove_request()
1795 		bfqq->next_rq = NULL;  in bfq_remove_request()
1797 		if (bfq_bfqq_busy(bfqq) && bfqq != bfqd->in_service_queue) {  in bfq_remove_request()
1798 			bfq_del_bfqq_busy(bfqd, bfqq, false);  in bfq_remove_request()
1812 			bfqq->entity.budget = bfqq->entity.service = 0;  in bfq_remove_request()
1818 		if (bfqq->pos_root) {  in bfq_remove_request()
1819 			rb_erase(&bfqq->pos_node, bfqq->pos_root);  in bfq_remove_request()
1820 			bfqq->pos_root = NULL;  in bfq_remove_request()
1823 		bfq_pos_tree_add_move(bfqd, bfqq);  in bfq_remove_request()
1827 		bfqq->meta_pending--;  in bfq_remove_request()
1888 		struct bfq_queue *bfqq = bfq_init_rq(req);  in bfq_request_merged()  local
1889 		struct bfq_data *bfqd = bfqq->bfqd;  in bfq_request_merged()
1893 		elv_rb_del(&bfqq->sort_list, req);  in bfq_request_merged()
1894 		elv_rb_add(&bfqq->sort_list, req);  in bfq_request_merged()
1897 		prev = bfqq->next_rq;  in bfq_request_merged()
1898 		next_rq = bfq_choose_req(bfqd, bfqq->next_rq, req,  in bfq_request_merged()
1900 		bfqq->next_rq = next_rq;  in bfq_request_merged()
1906 		if (prev != bfqq->next_rq) {  in bfq_request_merged()
1907 			bfq_updated_next_req(bfqd, bfqq);  in bfq_request_merged()
1908 			bfq_pos_tree_add_move(bfqd, bfqq);  in bfq_request_merged()
1930 	struct bfq_queue *bfqq = bfq_init_rq(rq),  in bfq_requests_merged()  local
1942 	if (bfqq == next_bfqq &&  in bfq_requests_merged()
1950 	if (bfqq->next_rq == next)  in bfq_requests_merged()
1951 		bfqq->next_rq = rq;  in bfq_requests_merged()
1953 	bfqg_stats_update_io_merged(bfqq_group(bfqq), next->cmd_flags);  in bfq_requests_merged()
1957 static void bfq_bfqq_end_wr(struct bfq_queue *bfqq)  in bfq_bfqq_end_wr()  argument
1959 	if (bfq_bfqq_busy(bfqq))  in bfq_bfqq_end_wr()
1960 		bfqq->bfqd->wr_busy_queues--;  in bfq_bfqq_end_wr()
1961 	bfqq->wr_coeff = 1;  in bfq_bfqq_end_wr()
1962 	bfqq->wr_cur_max_time = 0;  in bfq_bfqq_end_wr()
1963 	bfqq->last_wr_start_finish = jiffies;  in bfq_bfqq_end_wr()
1968 	bfqq->entity.prio_changed = 1;  in bfq_bfqq_end_wr()
1986 	struct bfq_queue *bfqq;  in bfq_end_wr()  local
1990 	list_for_each_entry(bfqq, &bfqd->active_list, bfqq_list)  in bfq_end_wr()
1991 		bfq_bfqq_end_wr(bfqq);  in bfq_end_wr()
1992 	list_for_each_entry(bfqq, &bfqd->idle_list, bfqq_list)  in bfq_end_wr()
1993 		bfq_bfqq_end_wr(bfqq);  in bfq_end_wr()
2015 					 struct bfq_queue *bfqq,  in bfqq_find_close()
2018 	struct rb_root *root = &bfq_bfqq_to_bfqg(bfqq)->rq_pos_tree;  in bfqq_find_close()
2060 	struct bfq_queue *bfqq;  in bfq_find_close_cooperator()  local
2069 	bfqq = bfqq_find_close(bfqd, cur_bfqq, sector);  in bfq_find_close_cooperator()
2070 	if (!bfqq || bfqq == cur_bfqq)  in bfq_find_close_cooperator()
2073 	return bfqq;  in bfq_find_close_cooperator()
2077 bfq_setup_merge(struct bfq_queue *bfqq, struct bfq_queue *new_bfqq)  in bfq_setup_merge()  argument
2093 		if (__bfqq == bfqq)  in bfq_setup_merge()
2098 	process_refs = bfqq_process_refs(bfqq);  in bfq_setup_merge()
2107 	bfq_log_bfqq(bfqq->bfqd, bfqq, "scheduling merge with queue %d",  in bfq_setup_merge()
2130 	bfqq->new_bfqq = new_bfqq;  in bfq_setup_merge()
2135 static bool bfq_may_be_close_cooperator(struct bfq_queue *bfqq,  in bfq_may_be_close_cooperator()  argument
2141 	if (bfq_class_idle(bfqq) || bfq_class_idle(new_bfqq) ||  in bfq_may_be_close_cooperator()
2142 	    (bfqq->ioprio_class != new_bfqq->ioprio_class))  in bfq_may_be_close_cooperator()
2150 	if (BFQQ_SEEKY(bfqq) || BFQQ_SEEKY(new_bfqq))  in bfq_may_be_close_cooperator()
2158 	if (!bfq_bfqq_sync(bfqq) || !bfq_bfqq_sync(new_bfqq))  in bfq_may_be_close_cooperator()
2185 bfq_setup_cooperator(struct bfq_data *bfqd, struct bfq_queue *bfqq,  in bfq_setup_cooperator()  argument
2201 	if (bfq_too_late_for_merging(bfqq))  in bfq_setup_cooperator()
2204 	if (bfqq->new_bfqq)  in bfq_setup_cooperator()
2205 		return bfqq->new_bfqq;  in bfq_setup_cooperator()
2207 	if (!io_struct || unlikely(bfqq == &bfqd->oom_bfqq))  in bfq_setup_cooperator()
2216 	if (in_service_bfqq && in_service_bfqq != bfqq &&  in bfq_setup_cooperator()
2219 	    bfqq->entity.parent == in_service_bfqq->entity.parent &&  in bfq_setup_cooperator()
2220 	    bfq_may_be_close_cooperator(bfqq, in_service_bfqq)) {  in bfq_setup_cooperator()
2221 		new_bfqq = bfq_setup_merge(bfqq, in_service_bfqq);  in bfq_setup_cooperator()
2230 	new_bfqq = bfq_find_close_cooperator(bfqd, bfqq,  in bfq_setup_cooperator()
2234 	    bfq_may_be_close_cooperator(bfqq, new_bfqq))  in bfq_setup_cooperator()
2235 		return bfq_setup_merge(bfqq, new_bfqq);  in bfq_setup_cooperator()
2240 static void bfq_bfqq_save_state(struct bfq_queue *bfqq)  in bfq_bfqq_save_state()  argument
2242 	struct bfq_io_cq *bic = bfqq->bic;  in bfq_bfqq_save_state()
2252 	bic->saved_ttime = bfqq->ttime;  in bfq_bfqq_save_state()
2253 	bic->saved_has_short_ttime = bfq_bfqq_has_short_ttime(bfqq);  in bfq_bfqq_save_state()
2254 	bic->saved_IO_bound = bfq_bfqq_IO_bound(bfqq);  in bfq_bfqq_save_state()
2255 	bic->saved_in_large_burst = bfq_bfqq_in_large_burst(bfqq);  in bfq_bfqq_save_state()
2256 	bic->was_in_burst_list = !hlist_unhashed(&bfqq->burst_list_node);  in bfq_bfqq_save_state()
2257 	if (unlikely(bfq_bfqq_just_created(bfqq) &&  in bfq_bfqq_save_state()
2258 		     !bfq_bfqq_in_large_burst(bfqq) &&  in bfq_bfqq_save_state()
2259 		     bfqq->bfqd->low_latency)) {  in bfq_bfqq_save_state()
2269 		bic->saved_wr_coeff = bfqq->bfqd->bfq_wr_coeff;  in bfq_bfqq_save_state()
2270 		bic->saved_wr_cur_max_time = bfq_wr_duration(bfqq->bfqd);  in bfq_bfqq_save_state()
2273 		bic->saved_wr_coeff = bfqq->wr_coeff;  in bfq_bfqq_save_state()
2275 			bfqq->wr_start_at_switch_to_srt;  in bfq_bfqq_save_state()
2276 		bic->saved_last_wr_start_finish = bfqq->last_wr_start_finish;  in bfq_bfqq_save_state()
2277 		bic->saved_wr_cur_max_time = bfqq->wr_cur_max_time;  in bfq_bfqq_save_state()
2283 		struct bfq_queue *bfqq, struct bfq_queue *new_bfqq)  in bfq_merge_bfqqs()  argument
2285 	bfq_log_bfqq(bfqd, bfqq, "merging with queue %lu",  in bfq_merge_bfqqs()
2288 	bfq_bfqq_save_state(bfqq);  in bfq_merge_bfqqs()
2290 	if (bfq_bfqq_IO_bound(bfqq))  in bfq_merge_bfqqs()
2292 	bfq_clear_bfqq_IO_bound(bfqq);  in bfq_merge_bfqqs()
2303 	if (new_bfqq->wr_coeff == 1 && bfqq->wr_coeff > 1) {  in bfq_merge_bfqqs()
2304 		new_bfqq->wr_coeff = bfqq->wr_coeff;  in bfq_merge_bfqqs()
2305 		new_bfqq->wr_cur_max_time = bfqq->wr_cur_max_time;  in bfq_merge_bfqqs()
2306 		new_bfqq->last_wr_start_finish = bfqq->last_wr_start_finish;  in bfq_merge_bfqqs()
2308 			bfqq->wr_start_at_switch_to_srt;  in bfq_merge_bfqqs()
2314 	if (bfqq->wr_coeff > 1) { /* bfqq has given its wr to new_bfqq */  in bfq_merge_bfqqs()
2315 		bfqq->wr_coeff = 1;  in bfq_merge_bfqqs()
2316 		bfqq->entity.prio_changed = 1;  in bfq_merge_bfqqs()
2317 		if (bfq_bfqq_busy(bfqq))  in bfq_merge_bfqqs()
2340 	bfqq->bic = NULL;  in bfq_merge_bfqqs()
2342 	bfq_put_queue(bfqq);  in bfq_merge_bfqqs()
2350 	struct bfq_queue *bfqq = bfqd->bio_bfqq, *new_bfqq;  in bfq_allow_bio_merge()  local
2362 	if (!bfqq)  in bfq_allow_bio_merge()
2369 	new_bfqq = bfq_setup_cooperator(bfqd, bfqq, bio, false);  in bfq_allow_bio_merge()
2378 		bfq_merge_bfqqs(bfqd, bfqd->bio_bic, bfqq,  in bfq_allow_bio_merge()
2385 		bfqq = new_bfqq;  in bfq_allow_bio_merge()
2393 		bfqd->bio_bfqq = bfqq;  in bfq_allow_bio_merge()
2396 	return bfqq == RQ_BFQQ(rq);  in bfq_allow_bio_merge()
2406 				   struct bfq_queue *bfqq)  in bfq_set_budget_timeout()  argument
2410 	if (bfqq->wr_cur_max_time == bfqd->bfq_wr_rt_max_time)  in bfq_set_budget_timeout()
2413 		timeout_coeff = bfqq->entity.weight / bfqq->entity.orig_weight;  in bfq_set_budget_timeout()
2417 	bfqq->budget_timeout = jiffies +  in bfq_set_budget_timeout()
2422 				       struct bfq_queue *bfqq)  in __bfq_set_in_service_queue()  argument
2424 	if (bfqq) {  in __bfq_set_in_service_queue()
2425 		bfq_clear_bfqq_fifo_expire(bfqq);  in __bfq_set_in_service_queue()
2429 		if (time_is_before_jiffies(bfqq->last_wr_start_finish) &&  in __bfq_set_in_service_queue()
2430 		    bfqq->wr_coeff > 1 &&  in __bfq_set_in_service_queue()
2431 		    bfqq->wr_cur_max_time == bfqd->bfq_wr_rt_max_time &&  in __bfq_set_in_service_queue()
2432 		    time_is_before_jiffies(bfqq->budget_timeout)) {  in __bfq_set_in_service_queue()
2457 			if (time_after(bfqq->budget_timeout,  in __bfq_set_in_service_queue()
2458 				       bfqq->last_wr_start_finish))  in __bfq_set_in_service_queue()
2459 				bfqq->last_wr_start_finish +=  in __bfq_set_in_service_queue()
2460 					jiffies - bfqq->budget_timeout;  in __bfq_set_in_service_queue()
2462 				bfqq->last_wr_start_finish = jiffies;  in __bfq_set_in_service_queue()
2465 		bfq_set_budget_timeout(bfqd, bfqq);  in __bfq_set_in_service_queue()
2466 		bfq_log_bfqq(bfqd, bfqq,  in __bfq_set_in_service_queue()
2468 			     bfqq->entity.budget);  in __bfq_set_in_service_queue()
2471 	bfqd->in_service_queue = bfqq;  in __bfq_set_in_service_queue()
2479 	struct bfq_queue *bfqq = bfq_get_next_queue(bfqd);  in bfq_set_in_service_queue()  local
2481 	__bfq_set_in_service_queue(bfqd, bfqq);  in bfq_set_in_service_queue()
2482 	return bfqq;  in bfq_set_in_service_queue()
2487 	struct bfq_queue *bfqq = bfqd->in_service_queue;  in bfq_arm_slice_timer()  local
2490 	bfq_mark_bfqq_wait_request(bfqq);  in bfq_arm_slice_timer()
2508 	if (BFQQ_SEEKY(bfqq) && bfqq->wr_coeff == 1 &&  in bfq_arm_slice_timer()
2515 	bfqg_stats_set_start_idle_time(bfqq_group(bfqq));  in bfq_arm_slice_timer()
2766 	struct bfq_queue *bfqq = RQ_BFQQ(rq);  in bfq_dispatch_remove()  local
2780 	bfqq->dispatched++;  in bfq_dispatch_remove()
2786 static void __bfq_bfqq_expire(struct bfq_data *bfqd, struct bfq_queue *bfqq)  in __bfq_bfqq_expire()  argument
2794 	if (bfq_bfqq_coop(bfqq) && BFQQ_SEEKY(bfqq))  in __bfq_bfqq_expire()
2795 		bfq_mark_bfqq_split_coop(bfqq);  in __bfq_bfqq_expire()
2797 	if (RB_EMPTY_ROOT(&bfqq->sort_list)) {  in __bfq_bfqq_expire()
2798 		if (bfqq->dispatched == 0)  in __bfq_bfqq_expire()
2805 			bfqq->budget_timeout = jiffies;  in __bfq_bfqq_expire()
2807 		bfq_del_bfqq_busy(bfqd, bfqq, true);  in __bfq_bfqq_expire()
2809 		bfq_requeue_bfqq(bfqd, bfqq, true);  in __bfq_bfqq_expire()
2813 		bfq_pos_tree_add_move(bfqd, bfqq);  in __bfq_bfqq_expire()
2834 				     struct bfq_queue *bfqq,  in __bfq_bfqq_recalc_budget()  argument
2842 	if (bfqq->wr_coeff == 1)  in __bfq_bfqq_recalc_budget()
2843 		budget = bfqq->max_budget;  in __bfq_bfqq_recalc_budget()
2852 	bfq_log_bfqq(bfqd, bfqq, "recalc_budg: last budg %d, budg left %d",  in __bfq_bfqq_recalc_budget()
2853 		bfqq->entity.budget, bfq_bfqq_budget_left(bfqq));  in __bfq_bfqq_recalc_budget()
2854 	bfq_log_bfqq(bfqd, bfqq, "recalc_budg: last max_budg %d, min budg %d",  in __bfq_bfqq_recalc_budget()
2856 	bfq_log_bfqq(bfqd, bfqq, "recalc_budg: sync %d, seeky %d",  in __bfq_bfqq_recalc_budget()
2857 		bfq_bfqq_sync(bfqq), BFQQ_SEEKY(bfqd->in_service_queue));  in __bfq_bfqq_recalc_budget()
2859 	if (bfq_bfqq_sync(bfqq) && bfqq->wr_coeff == 1) {  in __bfq_bfqq_recalc_budget()
2890 			if (bfqq->dispatched > 0) /* still outstanding reqs */  in __bfq_bfqq_recalc_budget()
2953 			budget = max_t(int, bfqq->entity.service, min_budget);  in __bfq_bfqq_recalc_budget()
2958 	} else if (!bfq_bfqq_sync(bfqq)) {  in __bfq_bfqq_recalc_budget()
2968 	bfqq->max_budget = budget;  in __bfq_bfqq_recalc_budget()
2972 		bfqq->max_budget = min(bfqq->max_budget, bfqd->bfq_max_budget);  in __bfq_bfqq_recalc_budget()
2984 	next_rq = bfqq->next_rq;  in __bfq_bfqq_recalc_budget()
2986 		bfqq->entity.budget = max_t(unsigned long, bfqq->max_budget,  in __bfq_bfqq_recalc_budget()
2987 					    bfq_serv_to_charge(next_rq, bfqq));  in __bfq_bfqq_recalc_budget()
2989 	bfq_log_bfqq(bfqd, bfqq, "head sect: %u, new budget %d",  in __bfq_bfqq_recalc_budget()
2991 			bfqq->entity.budget);  in __bfq_bfqq_recalc_budget()
3025 static bool bfq_bfqq_is_slow(struct bfq_data *bfqd, struct bfq_queue *bfqq,  in bfq_bfqq_is_slow()  argument
3031 	bool slow = BFQQ_SEEKY(bfqq); /* if delta too short, use seekyness */  in bfq_bfqq_is_slow()
3033 	if (!bfq_bfqq_sync(bfqq))  in bfq_bfqq_is_slow()
3074 		slow = bfqq->entity.service < bfqd->bfq_max_budget / 2;  in bfq_bfqq_is_slow()
3077 	bfq_log_bfqq(bfqd, bfqq, "bfq_bfqq_is_slow: slow %d", slow);  in bfq_bfqq_is_slow()
3176 						struct bfq_queue *bfqq)  in bfq_bfqq_softrt_next_start()  argument
3178 	return max3(bfqq->soft_rt_next_start,  in bfq_bfqq_softrt_next_start()
3179 		    bfqq->last_idle_bklogged +  in bfq_bfqq_softrt_next_start()
3180 		    HZ * bfqq->service_from_backlogged /  in bfq_bfqq_softrt_next_start()
3182 		    jiffies + nsecs_to_jiffies(bfqq->bfqd->bfq_slice_idle) + 4);  in bfq_bfqq_softrt_next_start()
3212 		     struct bfq_queue *bfqq,  in bfq_bfqq_expire()  argument
3218 	struct bfq_entity *entity = &bfqq->entity;  in bfq_bfqq_expire()
3224 	slow = bfq_bfqq_is_slow(bfqd, bfqq, compensate, reason, &delta);  in bfq_bfqq_expire()
3241 	if (bfqq->wr_coeff == 1 &&  in bfq_bfqq_expire()
3244 	      bfq_bfqq_budget_left(bfqq) >=  entity->budget / 3)))  in bfq_bfqq_expire()
3245 		bfq_bfqq_charge_time(bfqd, bfqq, delta);  in bfq_bfqq_expire()
3249 		bfq_clear_bfqq_IO_bound(bfqq);  in bfq_bfqq_expire()
3251 	if (bfqd->low_latency && bfqq->wr_coeff == 1)  in bfq_bfqq_expire()
3252 		bfqq->last_wr_start_finish = jiffies;  in bfq_bfqq_expire()
3255 	    RB_EMPTY_ROOT(&bfqq->sort_list)) {  in bfq_bfqq_expire()
3267 		if (bfqq->dispatched == 0)  in bfq_bfqq_expire()
3268 			bfqq->soft_rt_next_start =  in bfq_bfqq_expire()
3269 				bfq_bfqq_softrt_next_start(bfqd, bfqq);  in bfq_bfqq_expire()
3275 			bfq_mark_bfqq_softrt_update(bfqq);  in bfq_bfqq_expire()
3279 	bfq_log_bfqq(bfqd, bfqq,  in bfq_bfqq_expire()
3281 		slow, bfqq->dispatched, bfq_bfqq_has_short_ttime(bfqq));  in bfq_bfqq_expire()
3287 	__bfq_bfqq_recalc_budget(bfqd, bfqq, reason);  in bfq_bfqq_expire()
3288 	ref = bfqq->ref;  in bfq_bfqq_expire()
3289 	__bfq_bfqq_expire(bfqd, bfqq);  in bfq_bfqq_expire()
3295 	if (!bfq_bfqq_busy(bfqq) &&  in bfq_bfqq_expire()
3298 		bfq_mark_bfqq_non_blocking_wait_rq(bfqq);  in bfq_bfqq_expire()
3334 static bool bfq_bfqq_budget_timeout(struct bfq_queue *bfqq)  in bfq_bfqq_budget_timeout()  argument
3336 	return time_is_before_eq_jiffies(bfqq->budget_timeout);  in bfq_bfqq_budget_timeout()
3347 static bool bfq_may_expire_for_budg_timeout(struct bfq_queue *bfqq)  in bfq_may_expire_for_budg_timeout()  argument
3349 	bfq_log_bfqq(bfqq->bfqd, bfqq,  in bfq_may_expire_for_budg_timeout()
3351 		bfq_bfqq_wait_request(bfqq),  in bfq_may_expire_for_budg_timeout()
3352 			bfq_bfqq_budget_left(bfqq) >=  bfqq->entity.budget / 3,  in bfq_may_expire_for_budg_timeout()
3353 		bfq_bfqq_budget_timeout(bfqq));  in bfq_may_expire_for_budg_timeout()
3355 	return (!bfq_bfqq_wait_request(bfqq) ||  in bfq_may_expire_for_budg_timeout()
3356 		bfq_bfqq_budget_left(bfqq) >=  bfqq->entity.budget / 3)  in bfq_may_expire_for_budg_timeout()
3358 		bfq_bfqq_budget_timeout(bfqq);  in bfq_may_expire_for_budg_timeout()
3384 static bool bfq_better_to_idle(struct bfq_queue *bfqq)  in bfq_better_to_idle()  argument
3386 	struct bfq_data *bfqd = bfqq->bfqd;  in bfq_better_to_idle()
3405 	if (bfqd->bfq_slice_idle == 0 || !bfq_bfqq_sync(bfqq) ||  in bfq_better_to_idle()
3406 	    bfq_class_idle(bfqq))  in bfq_better_to_idle()
3409 	bfqq_sequential_and_IO_bound = !BFQQ_SEEKY(bfqq) &&  in bfq_better_to_idle()
3410 		bfq_bfqq_IO_bound(bfqq) && bfq_bfqq_has_short_ttime(bfqq);  in bfq_better_to_idle()
3586 	asymmetric_scenario = bfqq->wr_coeff > 1 ||  in bfq_better_to_idle()
3604 		asymmetric_scenario && !bfq_bfqq_in_large_burst(bfqq);  in bfq_better_to_idle()
3627 static bool bfq_bfqq_must_idle(struct bfq_queue *bfqq)  in bfq_bfqq_must_idle()  argument
3629 	return RB_EMPTY_ROOT(&bfqq->sort_list) && bfq_better_to_idle(bfqq);  in bfq_bfqq_must_idle()
3638 	struct bfq_queue *bfqq;  in bfq_select_queue()  local
3642 	bfqq = bfqd->in_service_queue;  in bfq_select_queue()
3643 	if (!bfqq)  in bfq_select_queue()
3646 	bfq_log_bfqq(bfqd, bfqq, "select_queue: already in-service queue");  in bfq_select_queue()
3655 	if (bfq_may_expire_for_budg_timeout(bfqq) &&  in bfq_select_queue()
3656 	    !bfq_bfqq_must_idle(bfqq))  in bfq_select_queue()
3666 	next_rq = bfqq->next_rq;  in bfq_select_queue()
3672 		if (bfq_serv_to_charge(next_rq, bfqq) >  in bfq_select_queue()
3673 			bfq_bfqq_budget_left(bfqq)) {  in bfq_select_queue()
3688 			if (bfq_bfqq_wait_request(bfqq)) {  in bfq_select_queue()
3702 				bfq_clear_bfqq_wait_request(bfqq);  in bfq_select_queue()
3714 	if (bfq_bfqq_wait_request(bfqq) ||  in bfq_select_queue()
3715 	    (bfqq->dispatched != 0 && bfq_better_to_idle(bfqq))) {  in bfq_select_queue()
3716 		bfqq = NULL;  in bfq_select_queue()
3722 	bfq_bfqq_expire(bfqd, bfqq, false, reason);  in bfq_select_queue()
3724 	bfqq = bfq_set_in_service_queue(bfqd);  in bfq_select_queue()
3725 	if (bfqq) {  in bfq_select_queue()
3726 		bfq_log_bfqq(bfqd, bfqq, "select_queue: checking new queue");  in bfq_select_queue()
3730 	if (bfqq)  in bfq_select_queue()
3731 		bfq_log_bfqq(bfqd, bfqq, "select_queue: returned this queue");  in bfq_select_queue()
3735 	return bfqq;  in bfq_select_queue()
3738 static void bfq_update_wr_data(struct bfq_data *bfqd, struct bfq_queue *bfqq)  in bfq_update_wr_data()  argument
3740 	struct bfq_entity *entity = &bfqq->entity;  in bfq_update_wr_data()
3742 	if (bfqq->wr_coeff > 1) { /* queue is being weight-raised */  in bfq_update_wr_data()
3743 		bfq_log_bfqq(bfqd, bfqq,  in bfq_update_wr_data()
3745 			jiffies_to_msecs(jiffies - bfqq->last_wr_start_finish),  in bfq_update_wr_data()
3746 			jiffies_to_msecs(bfqq->wr_cur_max_time),  in bfq_update_wr_data()
3747 			bfqq->wr_coeff,  in bfq_update_wr_data()
3748 			bfqq->entity.weight, bfqq->entity.orig_weight);  in bfq_update_wr_data()
3751 			bfq_log_bfqq(bfqd, bfqq, "WARN: pending prio change");  in bfq_update_wr_data()
3758 		if (bfq_bfqq_in_large_burst(bfqq))  in bfq_update_wr_data()
3759 			bfq_bfqq_end_wr(bfqq);  in bfq_update_wr_data()
3760 		else if (time_is_before_jiffies(bfqq->last_wr_start_finish +  in bfq_update_wr_data()
3761 						bfqq->wr_cur_max_time)) {  in bfq_update_wr_data()
3762 			if (bfqq->wr_cur_max_time != bfqd->bfq_wr_rt_max_time ||  in bfq_update_wr_data()
3763 			time_is_before_jiffies(bfqq->wr_start_at_switch_to_srt +  in bfq_update_wr_data()
3765 				bfq_bfqq_end_wr(bfqq);  in bfq_update_wr_data()
3767 				switch_back_to_interactive_wr(bfqq, bfqd);  in bfq_update_wr_data()
3768 				bfqq->entity.prio_changed = 1;  in bfq_update_wr_data()
3771 		if (bfqq->wr_coeff > 1 &&  in bfq_update_wr_data()
3772 		    bfqq->wr_cur_max_time != bfqd->bfq_wr_rt_max_time &&  in bfq_update_wr_data()
3773 		    bfqq->service_from_wr > max_service_from_wr) {  in bfq_update_wr_data()
3775 			bfq_bfqq_end_wr(bfqq);  in bfq_update_wr_data()
3786 	if ((entity->weight > entity->orig_weight) != (bfqq->wr_coeff > 1))  in bfq_update_wr_data()
3795 						 struct bfq_queue *bfqq)  in bfq_dispatch_rq_from_bfqq()  argument
3797 	struct request *rq = bfqq->next_rq;  in bfq_dispatch_rq_from_bfqq()
3800 	service_to_charge = bfq_serv_to_charge(rq, bfqq);  in bfq_dispatch_rq_from_bfqq()
3802 	bfq_bfqq_served(bfqq, service_to_charge);  in bfq_dispatch_rq_from_bfqq()
3817 	bfq_update_wr_data(bfqd, bfqq);  in bfq_dispatch_rq_from_bfqq()
3824 	if (bfqd->busy_queues > 1 && bfq_class_idle(bfqq))  in bfq_dispatch_rq_from_bfqq()
3830 	bfq_bfqq_expire(bfqd, bfqq, false, BFQQE_BUDGET_EXHAUSTED);  in bfq_dispatch_rq_from_bfqq()
3850 	struct bfq_queue *bfqq = NULL;  in __bfq_dispatch_request()  local
3857 		bfqq = RQ_BFQQ(rq);  in __bfq_dispatch_request()
3859 		if (bfqq) {  in __bfq_dispatch_request()
3866 			bfqq->dispatched++;  in __bfq_dispatch_request()
3917 	bfqq = bfq_select_queue(bfqd);  in __bfq_dispatch_request()
3918 	if (!bfqq)  in __bfq_dispatch_request()
3921 	rq = bfq_dispatch_rq_from_bfqq(bfqd, bfqq);  in __bfq_dispatch_request()
3939 	struct bfq_queue *bfqq = rq ? RQ_BFQQ(rq) : NULL;  in bfq_update_dispatch_stats()  local
3941 	if (!idle_timer_disabled && !bfqq)  in bfq_update_dispatch_stats()
3969 	if (bfqq) {  in bfq_update_dispatch_stats()
3970 		struct bfq_group *bfqg = bfqq_group(bfqq);  in bfq_update_dispatch_stats()
4017 void bfq_put_queue(struct bfq_queue *bfqq)  in bfq_put_queue()  argument
4020 	struct bfq_group *bfqg = bfqq_group(bfqq);  in bfq_put_queue()
4023 	if (bfqq->bfqd)  in bfq_put_queue()
4024 		bfq_log_bfqq(bfqq->bfqd, bfqq, "put_queue: %p %d",  in bfq_put_queue()
4025 			     bfqq, bfqq->ref);  in bfq_put_queue()
4027 	bfqq->ref--;  in bfq_put_queue()
4028 	if (bfqq->ref)  in bfq_put_queue()
4031 	if (!hlist_unhashed(&bfqq->burst_list_node)) {  in bfq_put_queue()
4032 		hlist_del_init(&bfqq->burst_list_node);  in bfq_put_queue()
4059 		if (bfqq->bic && bfqq->bfqd->burst_size > 0)  in bfq_put_queue()
4060 			bfqq->bfqd->burst_size--;  in bfq_put_queue()
4063 	kmem_cache_free(bfq_pool, bfqq);  in bfq_put_queue()
4069 static void bfq_put_cooperator(struct bfq_queue *bfqq)  in bfq_put_cooperator()  argument
4078 	__bfqq = bfqq->new_bfqq;  in bfq_put_cooperator()
4080 		if (__bfqq == bfqq)  in bfq_put_cooperator()
4088 static void bfq_exit_bfqq(struct bfq_data *bfqd, struct bfq_queue *bfqq)  in bfq_exit_bfqq()  argument
4090 	if (bfqq == bfqd->in_service_queue) {  in bfq_exit_bfqq()
4091 		__bfq_bfqq_expire(bfqd, bfqq);  in bfq_exit_bfqq()
4095 	bfq_log_bfqq(bfqd, bfqq, "exit_bfqq: %p, %d", bfqq, bfqq->ref);  in bfq_exit_bfqq()
4097 	bfq_put_cooperator(bfqq);  in bfq_exit_bfqq()
4099 	bfq_put_queue(bfqq); /* release process reference */  in bfq_exit_bfqq()
4104 	struct bfq_queue *bfqq = bic_to_bfqq(bic, is_sync);  in bfq_exit_icq_bfqq()  local
4107 	if (bfqq)  in bfq_exit_icq_bfqq()
4108 		bfqd = bfqq->bfqd; /* NULL if scheduler already exited */  in bfq_exit_icq_bfqq()
4110 	if (bfqq && bfqd) {  in bfq_exit_icq_bfqq()
4114 		bfq_exit_bfqq(bfqd, bfqq);  in bfq_exit_icq_bfqq()
4133 bfq_set_next_ioprio_data(struct bfq_queue *bfqq, struct bfq_io_cq *bic)  in bfq_set_next_ioprio_data()  argument
4137 	struct bfq_data *bfqd = bfqq->bfqd;  in bfq_set_next_ioprio_data()
4145 		dev_err(bfqq->bfqd->queue->backing_dev_info->dev,  in bfq_set_next_ioprio_data()
4152 		bfqq->new_ioprio = task_nice_ioprio(tsk);  in bfq_set_next_ioprio_data()
4153 		bfqq->new_ioprio_class = task_nice_ioclass(tsk);  in bfq_set_next_ioprio_data()
4156 		bfqq->new_ioprio = IOPRIO_PRIO_DATA(bic->ioprio);  in bfq_set_next_ioprio_data()
4157 		bfqq->new_ioprio_class = IOPRIO_CLASS_RT;  in bfq_set_next_ioprio_data()
4160 		bfqq->new_ioprio = IOPRIO_PRIO_DATA(bic->ioprio);  in bfq_set_next_ioprio_data()
4161 		bfqq->new_ioprio_class = IOPRIO_CLASS_BE;  in bfq_set_next_ioprio_data()
4164 		bfqq->new_ioprio_class = IOPRIO_CLASS_IDLE;  in bfq_set_next_ioprio_data()
4165 		bfqq->new_ioprio = 7;  in bfq_set_next_ioprio_data()
4169 	if (bfqq->new_ioprio >= IOPRIO_BE_NR) {  in bfq_set_next_ioprio_data()
4171 			bfqq->new_ioprio);  in bfq_set_next_ioprio_data()
4172 		bfqq->new_ioprio = IOPRIO_BE_NR;  in bfq_set_next_ioprio_data()
4175 	bfqq->entity.new_weight = bfq_ioprio_to_weight(bfqq->new_ioprio);  in bfq_set_next_ioprio_data()
4176 	bfqq->entity.prio_changed = 1;  in bfq_set_next_ioprio_data()
4186 	struct bfq_queue *bfqq;  in bfq_check_ioprio_change()  local
4198 	bfqq = bic_to_bfqq(bic, false);  in bfq_check_ioprio_change()
4199 	if (bfqq) {  in bfq_check_ioprio_change()
4201 		bfq_put_queue(bfqq);  in bfq_check_ioprio_change()
4202 		bfqq = bfq_get_queue(bfqd, bio, BLK_RW_ASYNC, bic);  in bfq_check_ioprio_change()
4203 		bic_set_bfqq(bic, bfqq, false);  in bfq_check_ioprio_change()
4206 	bfqq = bic_to_bfqq(bic, true);  in bfq_check_ioprio_change()
4207 	if (bfqq)  in bfq_check_ioprio_change()
4208 		bfq_set_next_ioprio_data(bfqq, bic);  in bfq_check_ioprio_change()
4211 static void bfq_init_bfqq(struct bfq_data *bfqd, struct bfq_queue *bfqq,  in bfq_init_bfqq()  argument
4214 	RB_CLEAR_NODE(&bfqq->entity.rb_node);  in bfq_init_bfqq()
4215 	INIT_LIST_HEAD(&bfqq->fifo);  in bfq_init_bfqq()
4216 	INIT_HLIST_NODE(&bfqq->burst_list_node);  in bfq_init_bfqq()
4218 	bfqq->ref = 0;  in bfq_init_bfqq()
4219 	bfqq->bfqd = bfqd;  in bfq_init_bfqq()
4222 		bfq_set_next_ioprio_data(bfqq, bic);  in bfq_init_bfqq()
4230 		if (!bfq_class_idle(bfqq))  in bfq_init_bfqq()
4232 			bfq_mark_bfqq_has_short_ttime(bfqq);  in bfq_init_bfqq()
4233 		bfq_mark_bfqq_sync(bfqq);  in bfq_init_bfqq()
4234 		bfq_mark_bfqq_just_created(bfqq);  in bfq_init_bfqq()
4236 		bfq_clear_bfqq_sync(bfqq);  in bfq_init_bfqq()
4239 	bfqq->ttime.last_end_request = ktime_get_ns() + 1;  in bfq_init_bfqq()
4241 	bfq_mark_bfqq_IO_bound(bfqq);  in bfq_init_bfqq()
4243 	bfqq->pid = pid;  in bfq_init_bfqq()
4246 	bfqq->max_budget = (2 * bfq_max_budget(bfqd)) / 3;  in bfq_init_bfqq()
4247 	bfqq->budget_timeout = bfq_smallest_from_now();  in bfq_init_bfqq()
4249 	bfqq->wr_coeff = 1;  in bfq_init_bfqq()
4250 	bfqq->last_wr_start_finish = jiffies;  in bfq_init_bfqq()
4251 	bfqq->wr_start_at_switch_to_srt = bfq_smallest_from_now();  in bfq_init_bfqq()
4252 	bfqq->split_time = bfq_smallest_from_now();  in bfq_init_bfqq()
4263 	bfqq->soft_rt_next_start = jiffies;  in bfq_init_bfqq()
4266 	bfqq->seek_history = 1;  in bfq_init_bfqq()
4295 	struct bfq_queue *bfqq;  in bfq_get_queue()  local
4302 		bfqq = &bfqd->oom_bfqq;  in bfq_get_queue()
4309 		bfqq = *async_bfqq;  in bfq_get_queue()
4310 		if (bfqq)  in bfq_get_queue()
4314 	bfqq = kmem_cache_alloc_node(bfq_pool,  in bfq_get_queue()
4318 	if (bfqq) {  in bfq_get_queue()
4319 		bfq_init_bfqq(bfqd, bfqq, bic, current->pid,  in bfq_get_queue()
4321 		bfq_init_entity(&bfqq->entity, bfqg);  in bfq_get_queue()
4322 		bfq_log_bfqq(bfqd, bfqq, "allocated");  in bfq_get_queue()
4324 		bfqq = &bfqd->oom_bfqq;  in bfq_get_queue()
4325 		bfq_log_bfqq(bfqd, bfqq, "using oom bfqq");  in bfq_get_queue()
4334 		bfqq->ref++; /*  in bfq_get_queue()
4341 		bfq_log_bfqq(bfqd, bfqq, "get_queue, bfqq not in async: %p, %d",  in bfq_get_queue()
4342 			     bfqq, bfqq->ref);  in bfq_get_queue()
4343 		*async_bfqq = bfqq;  in bfq_get_queue()
4347 	bfqq->ref++; /* get a process reference to this queue */  in bfq_get_queue()
4348 	bfq_log_bfqq(bfqd, bfqq, "get_queue, at end: %p, %d", bfqq, bfqq->ref);  in bfq_get_queue()
4350 	return bfqq;  in bfq_get_queue()
4354 				    struct bfq_queue *bfqq)  in bfq_update_io_thinktime()  argument
4356 	struct bfq_ttime *ttime = &bfqq->ttime;  in bfq_update_io_thinktime()
4357 	u64 elapsed = ktime_get_ns() - bfqq->ttime.last_end_request;  in bfq_update_io_thinktime()
4361 	ttime->ttime_samples = (7*bfqq->ttime.ttime_samples + 256) / 8;  in bfq_update_io_thinktime()
4368 bfq_update_io_seektime(struct bfq_data *bfqd, struct bfq_queue *bfqq,  in bfq_update_io_seektime()  argument
4371 	bfqq->seek_history <<= 1;  in bfq_update_io_seektime()
4372 	bfqq->seek_history |=  in bfq_update_io_seektime()
4373 		get_sdist(bfqq->last_request_pos, rq) > BFQQ_SEEK_THR &&  in bfq_update_io_seektime()
4379 				       struct bfq_queue *bfqq,  in bfq_update_has_short_ttime()  argument
4389 	if (!bfq_bfqq_sync(bfqq) || bfq_class_idle(bfqq) ||  in bfq_update_has_short_ttime()
4394 	if (time_is_after_eq_jiffies(bfqq->split_time +  in bfq_update_has_short_ttime()
4403 	    (bfq_sample_valid(bfqq->ttime.ttime_samples) &&  in bfq_update_has_short_ttime()
4404 	     bfqq->ttime.ttime_mean > bfqd->bfq_slice_idle))  in bfq_update_has_short_ttime()
4407 	bfq_log_bfqq(bfqd, bfqq, "update_has_short_ttime: has_short_ttime %d",  in bfq_update_has_short_ttime()
4411 		bfq_mark_bfqq_has_short_ttime(bfqq);  in bfq_update_has_short_ttime()
4413 		bfq_clear_bfqq_has_short_ttime(bfqq);  in bfq_update_has_short_ttime()
4420 static void bfq_rq_enqueued(struct bfq_data *bfqd, struct bfq_queue *bfqq,  in bfq_rq_enqueued()  argument
4426 		bfqq->meta_pending++;  in bfq_rq_enqueued()
4428 	bfq_update_io_thinktime(bfqd, bfqq);  in bfq_rq_enqueued()
4429 	bfq_update_has_short_ttime(bfqd, bfqq, bic);  in bfq_rq_enqueued()
4430 	bfq_update_io_seektime(bfqd, bfqq, rq);  in bfq_rq_enqueued()
4432 	bfq_log_bfqq(bfqd, bfqq,  in bfq_rq_enqueued()
4434 		     bfq_bfqq_has_short_ttime(bfqq), BFQQ_SEEKY(bfqq));  in bfq_rq_enqueued()
4436 	bfqq->last_request_pos = blk_rq_pos(rq) + blk_rq_sectors(rq);  in bfq_rq_enqueued()
4438 	if (bfqq == bfqd->in_service_queue && bfq_bfqq_wait_request(bfqq)) {  in bfq_rq_enqueued()
4439 		bool small_req = bfqq->queued[rq_is_sync(rq)] == 1 &&  in bfq_rq_enqueued()
4441 		bool budget_timeout = bfq_bfqq_budget_timeout(bfqq);  in bfq_rq_enqueued()
4467 		bfq_clear_bfqq_wait_request(bfqq);  in bfq_rq_enqueued()
4478 			bfq_bfqq_expire(bfqd, bfqq, false,  in bfq_rq_enqueued()
4486 	struct bfq_queue *bfqq = RQ_BFQQ(rq),  in __bfq_insert_request()  local
4487 		*new_bfqq = bfq_setup_cooperator(bfqd, bfqq, rq, true);  in __bfq_insert_request()
4491 		if (bic_to_bfqq(RQ_BIC(rq), 1) != bfqq)  in __bfq_insert_request()
4498 		bfqq->allocated--;  in __bfq_insert_request()
4508 		if (bic_to_bfqq(RQ_BIC(rq), 1) == bfqq)  in __bfq_insert_request()
4510 					bfqq, new_bfqq);  in __bfq_insert_request()
4512 		bfq_clear_bfqq_just_created(bfqq);  in __bfq_insert_request()
4517 		bfq_put_queue(bfqq);  in __bfq_insert_request()
4519 		bfqq = new_bfqq;  in __bfq_insert_request()
4522 	waiting = bfqq && bfq_bfqq_wait_request(bfqq);  in __bfq_insert_request()
4524 	idle_timer_disabled = waiting && !bfq_bfqq_wait_request(bfqq);  in __bfq_insert_request()
4527 	list_add_tail(&rq->queuelist, &bfqq->fifo);  in __bfq_insert_request()
4529 	bfq_rq_enqueued(bfqd, bfqq, rq);  in __bfq_insert_request()
4536 				    struct bfq_queue *bfqq,  in bfq_update_insert_stats()  argument
4540 	if (!bfqq)  in bfq_update_insert_stats()
4554 	bfqg_stats_update_io_add(bfqq_group(bfqq), bfqq, cmd_flags);  in bfq_update_insert_stats()
4556 		bfqg_stats_update_idle_time(bfqq_group(bfqq));  in bfq_update_insert_stats()
4561 					   struct bfq_queue *bfqq,  in bfq_update_insert_stats()  argument
4571 	struct bfq_queue *bfqq;  in bfq_insert_request()  local
4586 	bfqq = bfq_init_rq(rq);  in bfq_insert_request()
4599 		bfqq = RQ_BFQQ(rq);  in bfq_insert_request()
4617 	bfq_update_insert_stats(q, bfqq, idle_timer_disabled,  in bfq_insert_request()
4658 static void bfq_completed_request(struct bfq_queue *bfqq, struct bfq_data *bfqd)  in bfq_completed_request()  argument
4666 	bfqq->dispatched--;  in bfq_completed_request()
4668 	if (!bfqq->dispatched && !bfq_bfqq_busy(bfqq)) {  in bfq_completed_request()
4675 		bfqq->budget_timeout = jiffies;  in bfq_completed_request()
4677 		bfq_weights_tree_remove(bfqd, bfqq);  in bfq_completed_request()
4682 	bfqq->ttime.last_end_request = now_ns;  in bfq_completed_request()
4721 	if (bfq_bfqq_softrt_update(bfqq) && bfqq->dispatched == 0 &&  in bfq_completed_request()
4722 	    RB_EMPTY_ROOT(&bfqq->sort_list))  in bfq_completed_request()
4723 		bfqq->soft_rt_next_start =  in bfq_completed_request()
4724 			bfq_bfqq_softrt_next_start(bfqd, bfqq);  in bfq_completed_request()
4730 	if (bfqd->in_service_queue == bfqq) {  in bfq_completed_request()
4731 		if (bfq_bfqq_must_idle(bfqq)) {  in bfq_completed_request()
4732 			if (bfqq->dispatched == 0)  in bfq_completed_request()
4758 		} else if (bfq_may_expire_for_budg_timeout(bfqq))  in bfq_completed_request()
4759 			bfq_bfqq_expire(bfqd, bfqq, false,  in bfq_completed_request()
4761 		else if (RB_EMPTY_ROOT(&bfqq->sort_list) &&  in bfq_completed_request()
4762 			 (bfqq->dispatched == 0 ||  in bfq_completed_request()
4763 			  !bfq_better_to_idle(bfqq)))  in bfq_completed_request()
4764 			bfq_bfqq_expire(bfqd, bfqq, false,  in bfq_completed_request()
4772 static void bfq_finish_requeue_request_body(struct bfq_queue *bfqq)  in bfq_finish_requeue_request_body()  argument
4774 	bfqq->allocated--;  in bfq_finish_requeue_request_body()
4776 	bfq_put_queue(bfqq);  in bfq_finish_requeue_request_body()
4787 	struct bfq_queue *bfqq = RQ_BFQQ(rq);  in bfq_finish_requeue_request()  local
4807 	if (!rq->elv.icq || !bfqq)  in bfq_finish_requeue_request()
4810 	bfqd = bfqq->bfqd;  in bfq_finish_requeue_request()
4813 		bfqg_stats_update_completion(bfqq_group(bfqq),  in bfq_finish_requeue_request()
4823 		bfq_completed_request(bfqq, bfqd);  in bfq_finish_requeue_request()
4824 		bfq_finish_requeue_request_body(bfqq);  in bfq_finish_requeue_request()
4843 			bfqg_stats_update_io_remove(bfqq_group(bfqq),  in bfq_finish_requeue_request()
4846 		bfq_finish_requeue_request_body(bfqq);  in bfq_finish_requeue_request()
4875 bfq_split_bfqq(struct bfq_io_cq *bic, struct bfq_queue *bfqq)  in bfq_split_bfqq()  argument
4877 	bfq_log_bfqq(bfqq->bfqd, bfqq, "splitting queue");  in bfq_split_bfqq()
4879 	if (bfqq_process_refs(bfqq) == 1) {  in bfq_split_bfqq()
4880 		bfqq->pid = current->pid;  in bfq_split_bfqq()
4881 		bfq_clear_bfqq_coop(bfqq);  in bfq_split_bfqq()
4882 		bfq_clear_bfqq_split_coop(bfqq);  in bfq_split_bfqq()
4883 		return bfqq;  in bfq_split_bfqq()
4888 	bfq_put_cooperator(bfqq);  in bfq_split_bfqq()
4890 	bfq_put_queue(bfqq);  in bfq_split_bfqq()
4900 	struct bfq_queue *bfqq = bic_to_bfqq(bic, is_sync);  in bfq_get_bfqq_handle_split()  local
4902 	if (likely(bfqq && bfqq != &bfqd->oom_bfqq))  in bfq_get_bfqq_handle_split()
4903 		return bfqq;  in bfq_get_bfqq_handle_split()
4908 	if (bfqq)  in bfq_get_bfqq_handle_split()
4909 		bfq_put_queue(bfqq);  in bfq_get_bfqq_handle_split()
4910 	bfqq = bfq_get_queue(bfqd, bio, is_sync, bic);  in bfq_get_bfqq_handle_split()
4912 	bic_set_bfqq(bic, bfqq, is_sync);  in bfq_get_bfqq_handle_split()
4916 			bfq_mark_bfqq_in_large_burst(bfqq);  in bfq_get_bfqq_handle_split()
4918 			bfq_clear_bfqq_in_large_burst(bfqq);  in bfq_get_bfqq_handle_split()
4948 				hlist_add_head(&bfqq->burst_list_node,  in bfq_get_bfqq_handle_split()
4951 		bfqq->split_time = jiffies;  in bfq_get_bfqq_handle_split()
4954 	return bfqq;  in bfq_get_bfqq_handle_split()
5003 	struct bfq_queue *bfqq;  in bfq_init_rq()  local
5026 	bfqq = bfq_get_bfqq_handle_split(bfqd, bic, bio, false, is_sync,  in bfq_init_rq()
5031 		if (bfq_bfqq_coop(bfqq) && bfq_bfqq_split_coop(bfqq)) {  in bfq_init_rq()
5032 			bfq_log_bfqq(bfqd, bfqq, "breaking apart bfqq");  in bfq_init_rq()
5035 			if (bfq_bfqq_in_large_burst(bfqq))  in bfq_init_rq()
5038 			bfqq = bfq_split_bfqq(bic, bfqq);  in bfq_init_rq()
5041 			if (!bfqq)  in bfq_init_rq()
5042 				bfqq = bfq_get_bfqq_handle_split(bfqd, bic, bio,  in bfq_init_rq()
5050 	bfqq->allocated++;  in bfq_init_rq()
5051 	bfqq->ref++;  in bfq_init_rq()
5052 	bfq_log_bfqq(bfqd, bfqq, "get_request %p: bfqq %p, %d",  in bfq_init_rq()
5053 		     rq, bfqq, bfqq->ref);  in bfq_init_rq()
5056 	rq->elv.priv[1] = bfqq;  in bfq_init_rq()
5064 	if (likely(bfqq != &bfqd->oom_bfqq) && bfqq_process_refs(bfqq) == 1) {  in bfq_init_rq()
5065 		bfqq->bic = bic;  in bfq_init_rq()
5072 			bfq_bfqq_resume_state(bfqq, bfqd, bic,  in bfq_init_rq()
5077 	if (unlikely(bfq_bfqq_just_created(bfqq)))  in bfq_init_rq()
5078 		bfq_handle_burst(bfqd, bfqq);  in bfq_init_rq()
5080 	return bfqq;  in bfq_init_rq()
5083 static void bfq_idle_slice_timer_body(struct bfq_queue *bfqq)  in bfq_idle_slice_timer_body()  argument
5085 	struct bfq_data *bfqd = bfqq->bfqd;  in bfq_idle_slice_timer_body()
5090 	bfq_clear_bfqq_wait_request(bfqq);  in bfq_idle_slice_timer_body()
5092 	if (bfqq != bfqd->in_service_queue) {  in bfq_idle_slice_timer_body()
5097 	if (bfq_bfqq_budget_timeout(bfqq))  in bfq_idle_slice_timer_body()
5104 	else if (bfqq->queued[0] == 0 && bfqq->queued[1] == 0)  in bfq_idle_slice_timer_body()
5115 	bfq_bfqq_expire(bfqd, bfqq, true, reason);  in bfq_idle_slice_timer_body()
5130 	struct bfq_queue *bfqq = bfqd->in_service_queue;  in bfq_idle_slice_timer()  local
5140 	if (bfqq)  in bfq_idle_slice_timer()
5141 		bfq_idle_slice_timer_body(bfqq);  in bfq_idle_slice_timer()
5149 	struct bfq_queue *bfqq = *bfqq_ptr;  in __bfq_put_async_bfqq()  local
5151 	bfq_log(bfqd, "put_async_bfqq: %p", bfqq);  in __bfq_put_async_bfqq()
5152 	if (bfqq) {  in __bfq_put_async_bfqq()
5153 		bfq_bfqq_move(bfqd, bfqq, bfqd->root_group);  in __bfq_put_async_bfqq()
5155 		bfq_log_bfqq(bfqd, bfqq, "put_async_bfqq: putting %p, %d",  in __bfq_put_async_bfqq()
5156 			     bfqq, bfqq->ref);  in __bfq_put_async_bfqq()
5157 		bfq_put_queue(bfqq);  in __bfq_put_async_bfqq()
5240 	struct bfq_queue *bfqq, *n;  in bfq_exit_queue()  local
5245 	list_for_each_entry_safe(bfqq, n, &bfqd->idle_list, bfqq_list)  in bfq_exit_queue()
5246 		bfq_deactivate_bfqq(bfqd, bfqq, false, false);  in bfq_exit_queue()