30 static unsigned int bfq_class_idx(struct bfq_entity *entity)  in bfq_class_idx()  argument
32 	struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);  in bfq_class_idx()
194 static bool bfq_no_longer_next_in_service(struct bfq_entity *entity)  in bfq_no_longer_next_in_service()  argument
198 	if (bfq_entity_to_bfqq(entity))  in bfq_no_longer_next_in_service()
201 	bfqg = container_of(entity, struct bfq_group, entity);  in bfq_no_longer_next_in_service()
228 static bool bfq_no_longer_next_in_service(struct bfq_entity *entity)  in bfq_no_longer_next_in_service()  argument
244 struct bfq_queue *bfq_entity_to_bfqq(struct bfq_entity *entity)  in bfq_entity_to_bfqq()  argument
248 	if (!entity->my_sched_data)  in bfq_entity_to_bfqq()
249 		bfqq = container_of(entity, struct bfq_queue, entity);  in bfq_entity_to_bfqq()
270 static void bfq_calc_finish(struct bfq_entity *entity, unsigned long service)  in bfq_calc_finish()  argument
272 	struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);  in bfq_calc_finish()
274 	entity->finish = entity->start +  in bfq_calc_finish()
275 		bfq_delta(service, entity->weight);  in bfq_calc_finish()
280 			service, entity->weight);  in bfq_calc_finish()
283 			entity->start, entity->finish,  in bfq_calc_finish()
284 			bfq_delta(service, entity->weight));  in bfq_calc_finish()
299 	struct bfq_entity *entity = NULL;  in bfq_entity_of()  local
302 		entity = rb_entry(node, struct bfq_entity, rb_node);  in bfq_entity_of()
304 	return entity;  in bfq_entity_of()
312 static void bfq_extract(struct rb_root *root, struct bfq_entity *entity)  in bfq_extract()  argument
314 	entity->tree = NULL;  in bfq_extract()
315 	rb_erase(&entity->rb_node, root);  in bfq_extract()
324 			     struct bfq_entity *entity)  in bfq_idle_extract()  argument
326 	struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);  in bfq_idle_extract()
329 	if (entity == st->first_idle) {  in bfq_idle_extract()
330 		next = rb_next(&entity->rb_node);  in bfq_idle_extract()
334 	if (entity == st->last_idle) {  in bfq_idle_extract()
335 		next = rb_prev(&entity->rb_node);  in bfq_idle_extract()
339 	bfq_extract(&st->idle, entity);  in bfq_idle_extract()
353 static void bfq_insert(struct rb_root *root, struct bfq_entity *entity)  in bfq_insert()  argument
363 		if (bfq_gt(entry->finish, entity->finish))  in bfq_insert()
369 	rb_link_node(&entity->rb_node, parent, node);  in bfq_insert()
370 	rb_insert_color(&entity->rb_node, root);  in bfq_insert()
372 	entity->tree = root;  in bfq_insert()
385 static void bfq_update_min(struct bfq_entity *entity, struct rb_node *node)  in bfq_update_min()  argument
391 		if (bfq_gt(entity->min_start, child->min_start))  in bfq_update_min()
392 			entity->min_start = child->min_start;  in bfq_update_min()
406 	struct bfq_entity *entity = rb_entry(node, struct bfq_entity, rb_node);  in bfq_update_active_node()  local
408 	entity->min_start = entity->start;  in bfq_update_active_node()
409 	bfq_update_min(entity, node->rb_right);  in bfq_update_active_node()
410 	bfq_update_min(entity, node->rb_left);  in bfq_update_active_node()
455 			      struct bfq_entity *entity)  in bfq_active_insert()  argument
457 	struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);  in bfq_active_insert()
458 	struct rb_node *node = &entity->rb_node;  in bfq_active_insert()
465 	bfq_insert(&st->active, entity);  in bfq_active_insert()
475 	sd = entity->sched_data;  in bfq_active_insert()
510 static void bfq_get_entity(struct bfq_entity *entity)  in bfq_get_entity()  argument
512 	struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);  in bfq_get_entity()
557 			       struct bfq_entity *entity)  in bfq_active_extract()  argument
559 	struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);  in bfq_active_extract()
567 	node = bfq_find_deepest(&entity->rb_node);  in bfq_active_extract()
568 	bfq_extract(&st->active, entity);  in bfq_active_extract()
574 	sd = entity->sched_data;  in bfq_active_extract()
592 			    struct bfq_entity *entity)  in bfq_idle_insert()  argument
594 	struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);  in bfq_idle_insert()
598 	if (!first_idle || bfq_gt(first_idle->finish, entity->finish))  in bfq_idle_insert()
599 		st->first_idle = entity;  in bfq_idle_insert()
600 	if (!last_idle || bfq_gt(entity->finish, last_idle->finish))  in bfq_idle_insert()
601 		st->last_idle = entity;  in bfq_idle_insert()
603 	bfq_insert(&st->idle, entity);  in bfq_idle_insert()
625 			      struct bfq_entity *entity,  in bfq_forget_entity()  argument
628 	struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);  in bfq_forget_entity()
630 	entity->on_st_or_in_serv = false;  in bfq_forget_entity()
631 	st->wsum -= entity->weight;  in bfq_forget_entity()
641 void bfq_put_idle_entity(struct bfq_service_tree *st, struct bfq_entity *entity)  in bfq_put_idle_entity()  argument
643 	bfq_idle_extract(st, entity);  in bfq_put_idle_entity()
644 	bfq_forget_entity(st, entity,  in bfq_put_idle_entity()
645 			  entity == entity->sched_data->in_service_entity);  in bfq_put_idle_entity()
673 struct bfq_service_tree *bfq_entity_service_tree(struct bfq_entity *entity)  in bfq_entity_service_tree()  argument
675 	struct bfq_sched_data *sched_data = entity->sched_data;  in bfq_entity_service_tree()
676 	unsigned int idx = bfq_class_idx(entity);  in bfq_entity_service_tree()
701 				struct bfq_entity *entity,  in __bfq_entity_update_weight_prio()  argument
706 	if (entity->prio_changed) {  in __bfq_entity_update_weight_prio()
707 		struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);  in __bfq_entity_update_weight_prio()
720 			sd = entity->my_sched_data;  in __bfq_entity_update_weight_prio()
728 		old_st->wsum -= entity->weight;  in __bfq_entity_update_weight_prio()
730 		if (entity->new_weight != entity->orig_weight) {  in __bfq_entity_update_weight_prio()
731 			if (entity->new_weight < BFQ_MIN_WEIGHT ||  in __bfq_entity_update_weight_prio()
732 			    entity->new_weight > BFQ_MAX_WEIGHT) {  in __bfq_entity_update_weight_prio()
734 					entity->new_weight);  in __bfq_entity_update_weight_prio()
735 				if (entity->new_weight < BFQ_MIN_WEIGHT)  in __bfq_entity_update_weight_prio()
736 					entity->new_weight = BFQ_MIN_WEIGHT;  in __bfq_entity_update_weight_prio()
738 					entity->new_weight = BFQ_MAX_WEIGHT;  in __bfq_entity_update_weight_prio()
740 			entity->orig_weight = entity->new_weight;  in __bfq_entity_update_weight_prio()
743 				  bfq_weight_to_ioprio(entity->orig_weight);  in __bfq_entity_update_weight_prio()
754 			entity->prio_changed = 0;  in __bfq_entity_update_weight_prio()
763 		new_st = bfq_entity_service_tree(entity);  in __bfq_entity_update_weight_prio()
765 		prev_weight = entity->weight;  in __bfq_entity_update_weight_prio()
766 		new_weight = entity->orig_weight *  in __bfq_entity_update_weight_prio()
777 		entity->weight = new_weight;  in __bfq_entity_update_weight_prio()
787 		new_st->wsum += entity->weight;  in __bfq_entity_update_weight_prio()
790 			entity->start = new_st->vtime;  in __bfq_entity_update_weight_prio()
808 	struct bfq_entity *entity = &bfqq->entity;  in bfq_bfqq_served()  local
818 	for_each_entity(entity) {  in bfq_bfqq_served()
819 		st = bfq_entity_service_tree(entity);  in bfq_bfqq_served()
821 		entity->service += served;  in bfq_bfqq_served()
859 	struct bfq_entity *entity = &bfqq->entity;  in bfq_bfqq_charge_time()  local
864 	int tot_serv_to_charge = max(serv_to_charge_for_time, entity->service);  in bfq_bfqq_charge_time()
867 	if (tot_serv_to_charge > entity->budget)  in bfq_bfqq_charge_time()
868 		entity->budget = tot_serv_to_charge;  in bfq_bfqq_charge_time()
871 			max_t(int, 0, tot_serv_to_charge - entity->service));  in bfq_bfqq_charge_time()
874 static void bfq_update_fin_time_enqueue(struct bfq_entity *entity,  in bfq_update_fin_time_enqueue()  argument
878 	struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);  in bfq_update_fin_time_enqueue()
885 	st = __bfq_entity_update_weight_prio(st, entity, true);  in bfq_update_fin_time_enqueue()
886 	bfq_calc_finish(entity, entity->budget);  in bfq_update_fin_time_enqueue()
921 	if (backshifted && bfq_gt(st->vtime, entity->finish)) {  in bfq_update_fin_time_enqueue()
922 		unsigned long delta = st->vtime - entity->finish;  in bfq_update_fin_time_enqueue()
927 		entity->start += delta;  in bfq_update_fin_time_enqueue()
928 		entity->finish += delta;  in bfq_update_fin_time_enqueue()
931 	bfq_active_insert(st, entity);  in bfq_update_fin_time_enqueue()
946 static void __bfq_activate_entity(struct bfq_entity *entity,  in __bfq_activate_entity()  argument
949 	struct bfq_service_tree *st = bfq_entity_service_tree(entity);  in __bfq_activate_entity()
954 	if (non_blocking_wait_rq && bfq_gt(st->vtime, entity->finish)) {  in __bfq_activate_entity()
956 		min_vstart = entity->finish;  in __bfq_activate_entity()
960 	if (entity->tree == &st->idle) {  in __bfq_activate_entity()
965 		bfq_idle_extract(st, entity);  in __bfq_activate_entity()
966 		entity->start = bfq_gt(min_vstart, entity->finish) ?  in __bfq_activate_entity()
967 			min_vstart : entity->finish;  in __bfq_activate_entity()
974 		entity->start = min_vstart;  in __bfq_activate_entity()
975 		st->wsum += entity->weight;  in __bfq_activate_entity()
982 		bfq_get_entity(entity);  in __bfq_activate_entity()
984 		entity->on_st_or_in_serv = true;  in __bfq_activate_entity()
988 	if (!bfq_entity_to_bfqq(entity)) { /* bfq_group */  in __bfq_activate_entity()
990 			container_of(entity, struct bfq_group, entity);  in __bfq_activate_entity()
993 		if (!entity->in_groups_with_pending_reqs) {  in __bfq_activate_entity()
994 			entity->in_groups_with_pending_reqs = true;  in __bfq_activate_entity()
1000 	bfq_update_fin_time_enqueue(entity, st, backshifted);  in __bfq_activate_entity()
1018 static void __bfq_requeue_entity(struct bfq_entity *entity)  in __bfq_requeue_entity()  argument
1020 	struct bfq_sched_data *sd = entity->sched_data;  in __bfq_requeue_entity()
1021 	struct bfq_service_tree *st = bfq_entity_service_tree(entity);  in __bfq_requeue_entity()
1023 	if (entity == sd->in_service_entity) {  in __bfq_requeue_entity()
1046 		bfq_calc_finish(entity, entity->service);  in __bfq_requeue_entity()
1047 		entity->start = entity->finish;  in __bfq_requeue_entity()
1061 		if (entity->tree)  in __bfq_requeue_entity()
1062 			bfq_active_extract(st, entity);  in __bfq_requeue_entity()
1078 		bfq_active_extract(st, entity);  in __bfq_requeue_entity()
1081 	bfq_update_fin_time_enqueue(entity, st, false);  in __bfq_requeue_entity()
1084 static void __bfq_activate_requeue_entity(struct bfq_entity *entity,  in __bfq_activate_requeue_entity()  argument
1088 	struct bfq_service_tree *st = bfq_entity_service_tree(entity);  in __bfq_activate_requeue_entity()
1090 	if (sd->in_service_entity == entity || entity->tree == &st->active)  in __bfq_activate_requeue_entity()
1095 		__bfq_requeue_entity(entity);  in __bfq_activate_requeue_entity()
1101 		__bfq_activate_entity(entity, non_blocking_wait_rq);  in __bfq_activate_requeue_entity()
1118 static void bfq_activate_requeue_entity(struct bfq_entity *entity,  in bfq_activate_requeue_entity()  argument
1124 	for_each_entity(entity) {  in bfq_activate_requeue_entity()
1125 		sd = entity->sched_data;  in bfq_activate_requeue_entity()
1126 		__bfq_activate_requeue_entity(entity, sd, non_blocking_wait_rq);  in bfq_activate_requeue_entity()
1128 		if (!bfq_update_next_in_service(sd, entity, expiration) &&  in bfq_activate_requeue_entity()
1144 bool __bfq_deactivate_entity(struct bfq_entity *entity, bool ins_into_idle_tree)  in __bfq_deactivate_entity()  argument
1146 	struct bfq_sched_data *sd = entity->sched_data;  in __bfq_deactivate_entity()
1150 	if (!entity->on_st_or_in_serv) /*  in __bfq_deactivate_entity()
1162 	st = bfq_entity_service_tree(entity);  in __bfq_deactivate_entity()
1163 	is_in_service = entity == sd->in_service_entity;  in __bfq_deactivate_entity()
1165 	bfq_calc_finish(entity, entity->service);  in __bfq_deactivate_entity()
1175 		entity->service = 0;  in __bfq_deactivate_entity()
1177 	if (entity->tree == &st->active)  in __bfq_deactivate_entity()
1178 		bfq_active_extract(st, entity);  in __bfq_deactivate_entity()
1179 	else if (!is_in_service && entity->tree == &st->idle)  in __bfq_deactivate_entity()
1180 		bfq_idle_extract(st, entity);  in __bfq_deactivate_entity()
1182 	if (!ins_into_idle_tree || !bfq_gt(entity->finish, st->vtime))  in __bfq_deactivate_entity()
1183 		bfq_forget_entity(st, entity, is_in_service);  in __bfq_deactivate_entity()
1185 		bfq_idle_insert(st, entity);  in __bfq_deactivate_entity()
1197 static void bfq_deactivate_entity(struct bfq_entity *entity,  in bfq_deactivate_entity()  argument
1204 	for_each_entity_safe(entity, parent) {  in bfq_deactivate_entity()
1205 		sd = entity->sched_data;  in bfq_deactivate_entity()
1207 		if (!__bfq_deactivate_entity(entity, ins_into_idle_tree)) {  in bfq_deactivate_entity()
1218 		if (sd->next_in_service == entity)  in bfq_deactivate_entity()
1272 	entity = parent;  in bfq_deactivate_entity()
1273 	for_each_entity(entity) {  in bfq_deactivate_entity()
1280 		__bfq_requeue_entity(entity);  in bfq_deactivate_entity()
1282 		sd = entity->sched_data;  in bfq_deactivate_entity()
1283 		if (!bfq_update_next_in_service(sd, entity, expiration) &&  in bfq_deactivate_entity()
1387 	struct bfq_entity *entity;  in __bfq_lookup_next_entity()  local
1412 	entity = bfq_first_active_entity(st, new_vtime);  in __bfq_lookup_next_entity()
1414 	return entity;  in __bfq_lookup_next_entity()
1431 	struct bfq_entity *entity = NULL;  in bfq_lookup_next_entity()  local
1469 		entity = __bfq_lookup_next_entity(st + class_idx,  in bfq_lookup_next_entity()
1473 		if (entity)  in bfq_lookup_next_entity()
1477 	return entity;  in bfq_lookup_next_entity()
1492 	struct bfq_entity *entity = NULL;  in bfq_get_next_queue()  local
1505 	for (; sd ; sd = entity->my_sched_data) {  in bfq_get_next_queue()
1531 		entity = sd->next_in_service;  in bfq_get_next_queue()
1532 		sd->in_service_entity = entity;  in bfq_get_next_queue()
1542 		if (bfq_no_longer_next_in_service(entity))  in bfq_get_next_queue()
1543 			bfq_active_extract(bfq_entity_service_tree(entity),  in bfq_get_next_queue()
1544 					   entity);  in bfq_get_next_queue()
1566 	bfqq = bfq_entity_to_bfqq(entity);  in bfq_get_next_queue()
1572 	for_each_entity(entity) {  in bfq_get_next_queue()
1573 		struct bfq_sched_data *sd = entity->sched_data;  in bfq_get_next_queue()
1586 	struct bfq_entity *in_serv_entity = &in_serv_bfqq->entity;  in __bfq_bfqd_reset_in_service()
1587 	struct bfq_entity *entity = in_serv_entity;  in __bfq_bfqd_reset_in_service()  local
1599 	for_each_entity(entity)  in __bfq_bfqd_reset_in_service()
1600 		entity->sched_data->in_service_entity = NULL;  in __bfq_bfqd_reset_in_service()
1626 	struct bfq_entity *entity = &bfqq->entity;  in bfq_deactivate_bfqq()  local
1628 	bfq_deactivate_entity(entity, ins_into_idle_tree, expiration);  in bfq_deactivate_bfqq()
1633 	struct bfq_entity *entity = &bfqq->entity;  in bfq_activate_bfqq()  local
1635 	bfq_activate_requeue_entity(entity, bfq_bfqq_non_blocking_wait_rq(bfqq),  in bfq_activate_bfqq()
1643 	struct bfq_entity *entity = &bfqq->entity;  in bfq_requeue_bfqq()  local
1645 	bfq_activate_requeue_entity(entity, false,  in bfq_requeue_bfqq()