39 static unsigned int bfq_class_idx(struct bfq_entity *entity)  in bfq_class_idx()  argument
41 	struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);  in bfq_class_idx()
153 	struct bfq_entity *group_entity = bfqq->entity.parent;  in bfq_bfqq_to_bfqg()
156 		group_entity = &bfqq->bfqd->root_group->entity;  in bfq_bfqq_to_bfqg()
158 	return container_of(group_entity, struct bfq_group, entity);  in bfq_bfqq_to_bfqg()
210 static bool bfq_no_longer_next_in_service(struct bfq_entity *entity)  in bfq_no_longer_next_in_service()  argument
214 	if (bfq_entity_to_bfqq(entity))  in bfq_no_longer_next_in_service()
217 	bfqg = container_of(entity, struct bfq_group, entity);  in bfq_no_longer_next_in_service()
249 static bool bfq_no_longer_next_in_service(struct bfq_entity *entity)  in bfq_no_longer_next_in_service()  argument
265 struct bfq_queue *bfq_entity_to_bfqq(struct bfq_entity *entity)  in bfq_entity_to_bfqq()  argument
269 	if (!entity->my_sched_data)  in bfq_entity_to_bfqq()
270 		bfqq = container_of(entity, struct bfq_queue, entity);  in bfq_entity_to_bfqq()
294 static void bfq_calc_finish(struct bfq_entity *entity, unsigned long service)  in bfq_calc_finish()  argument
296 	struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);  in bfq_calc_finish()
298 	entity->finish = entity->start +  in bfq_calc_finish()
299 		bfq_delta(service, entity->weight);  in bfq_calc_finish()
304 			service, entity->weight);  in bfq_calc_finish()
307 			entity->start, entity->finish,  in bfq_calc_finish()
308 			bfq_delta(service, entity->weight));  in bfq_calc_finish()
323 	struct bfq_entity *entity = NULL;  in bfq_entity_of()  local
326 		entity = rb_entry(node, struct bfq_entity, rb_node);  in bfq_entity_of()
328 	return entity;  in bfq_entity_of()
336 static void bfq_extract(struct rb_root *root, struct bfq_entity *entity)  in bfq_extract()  argument
338 	entity->tree = NULL;  in bfq_extract()
339 	rb_erase(&entity->rb_node, root);  in bfq_extract()
348 			     struct bfq_entity *entity)  in bfq_idle_extract()  argument
350 	struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);  in bfq_idle_extract()
353 	if (entity == st->first_idle) {  in bfq_idle_extract()
354 		next = rb_next(&entity->rb_node);  in bfq_idle_extract()
358 	if (entity == st->last_idle) {  in bfq_idle_extract()
359 		next = rb_prev(&entity->rb_node);  in bfq_idle_extract()
363 	bfq_extract(&st->idle, entity);  in bfq_idle_extract()
377 static void bfq_insert(struct rb_root *root, struct bfq_entity *entity)  in bfq_insert()  argument
387 		if (bfq_gt(entry->finish, entity->finish))  in bfq_insert()
393 	rb_link_node(&entity->rb_node, parent, node);  in bfq_insert()
394 	rb_insert_color(&entity->rb_node, root);  in bfq_insert()
396 	entity->tree = root;  in bfq_insert()
409 static void bfq_update_min(struct bfq_entity *entity, struct rb_node *node)  in bfq_update_min()  argument
415 		if (bfq_gt(entity->min_start, child->min_start))  in bfq_update_min()
416 			entity->min_start = child->min_start;  in bfq_update_min()
430 	struct bfq_entity *entity = rb_entry(node, struct bfq_entity, rb_node);  in bfq_update_active_node()  local
432 	entity->min_start = entity->start;  in bfq_update_active_node()
433 	bfq_update_min(entity, node->rb_right);  in bfq_update_active_node()
434 	bfq_update_min(entity, node->rb_left);  in bfq_update_active_node()
479 			      struct bfq_entity *entity)  in bfq_active_insert()  argument
481 	struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);  in bfq_active_insert()
482 	struct rb_node *node = &entity->rb_node;  in bfq_active_insert()
489 	bfq_insert(&st->active, entity);  in bfq_active_insert()
499 	sd = entity->sched_data;  in bfq_active_insert()
534 static void bfq_get_entity(struct bfq_entity *entity)  in bfq_get_entity()  argument
536 	struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);  in bfq_get_entity()
581 			       struct bfq_entity *entity)  in bfq_active_extract()  argument
583 	struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);  in bfq_active_extract()
591 	node = bfq_find_deepest(&entity->rb_node);  in bfq_active_extract()
592 	bfq_extract(&st->active, entity);  in bfq_active_extract()
598 	sd = entity->sched_data;  in bfq_active_extract()
616 			    struct bfq_entity *entity)  in bfq_idle_insert()  argument
618 	struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);  in bfq_idle_insert()
622 	if (!first_idle || bfq_gt(first_idle->finish, entity->finish))  in bfq_idle_insert()
623 		st->first_idle = entity;  in bfq_idle_insert()
624 	if (!last_idle || bfq_gt(entity->finish, last_idle->finish))  in bfq_idle_insert()
625 		st->last_idle = entity;  in bfq_idle_insert()
627 	bfq_insert(&st->idle, entity);  in bfq_idle_insert()
649 			      struct bfq_entity *entity,  in bfq_forget_entity()  argument
652 	struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);  in bfq_forget_entity()
654 	entity->on_st = false;  in bfq_forget_entity()
655 	st->wsum -= entity->weight;  in bfq_forget_entity()
665 void bfq_put_idle_entity(struct bfq_service_tree *st, struct bfq_entity *entity)  in bfq_put_idle_entity()  argument
667 	bfq_idle_extract(st, entity);  in bfq_put_idle_entity()
668 	bfq_forget_entity(st, entity,  in bfq_put_idle_entity()
669 			  entity == entity->sched_data->in_service_entity);  in bfq_put_idle_entity()
697 struct bfq_service_tree *bfq_entity_service_tree(struct bfq_entity *entity)  in bfq_entity_service_tree()  argument
699 	struct bfq_sched_data *sched_data = entity->sched_data;  in bfq_entity_service_tree()
700 	unsigned int idx = bfq_class_idx(entity);  in bfq_entity_service_tree()
725 				struct bfq_entity *entity,  in __bfq_entity_update_weight_prio()  argument
730 	if (entity->prio_changed) {  in __bfq_entity_update_weight_prio()
731 		struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);  in __bfq_entity_update_weight_prio()
744 			sd = entity->my_sched_data;  in __bfq_entity_update_weight_prio()
750 		old_st->wsum -= entity->weight;  in __bfq_entity_update_weight_prio()
752 		if (entity->new_weight != entity->orig_weight) {  in __bfq_entity_update_weight_prio()
753 			if (entity->new_weight < BFQ_MIN_WEIGHT ||  in __bfq_entity_update_weight_prio()
754 			    entity->new_weight > BFQ_MAX_WEIGHT) {  in __bfq_entity_update_weight_prio()
756 					entity->new_weight);  in __bfq_entity_update_weight_prio()
757 				if (entity->new_weight < BFQ_MIN_WEIGHT)  in __bfq_entity_update_weight_prio()
758 					entity->new_weight = BFQ_MIN_WEIGHT;  in __bfq_entity_update_weight_prio()
760 					entity->new_weight = BFQ_MAX_WEIGHT;  in __bfq_entity_update_weight_prio()
762 			entity->orig_weight = entity->new_weight;  in __bfq_entity_update_weight_prio()
765 				  bfq_weight_to_ioprio(entity->orig_weight);  in __bfq_entity_update_weight_prio()
776 			entity->prio_changed = 0;  in __bfq_entity_update_weight_prio()
785 		new_st = bfq_entity_service_tree(entity);  in __bfq_entity_update_weight_prio()
787 		prev_weight = entity->weight;  in __bfq_entity_update_weight_prio()
788 		new_weight = entity->orig_weight *  in __bfq_entity_update_weight_prio()
799 			__bfq_weights_tree_remove(bfqd, entity, root);  in __bfq_entity_update_weight_prio()
801 		entity->weight = new_weight;  in __bfq_entity_update_weight_prio()
809 			bfq_weights_tree_add(bfqd, entity, root);  in __bfq_entity_update_weight_prio()
811 		new_st->wsum += entity->weight;  in __bfq_entity_update_weight_prio()
814 			entity->start = new_st->vtime;  in __bfq_entity_update_weight_prio()
832 	struct bfq_entity *entity = &bfqq->entity;  in bfq_bfqq_served()  local
842 	for_each_entity(entity) {  in bfq_bfqq_served()
843 		st = bfq_entity_service_tree(entity);  in bfq_bfqq_served()
845 		entity->service += served;  in bfq_bfqq_served()
883 	struct bfq_entity *entity = &bfqq->entity;  in bfq_bfqq_charge_time()  local
888 	int tot_serv_to_charge = max(serv_to_charge_for_time, entity->service);  in bfq_bfqq_charge_time()
891 	if (tot_serv_to_charge > entity->budget)  in bfq_bfqq_charge_time()
892 		entity->budget = tot_serv_to_charge;  in bfq_bfqq_charge_time()
895 			max_t(int, 0, tot_serv_to_charge - entity->service));  in bfq_bfqq_charge_time()
898 static void bfq_update_fin_time_enqueue(struct bfq_entity *entity,  in bfq_update_fin_time_enqueue()  argument
902 	struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);  in bfq_update_fin_time_enqueue()
909 	st = __bfq_entity_update_weight_prio(st, entity, true);  in bfq_update_fin_time_enqueue()
910 	bfq_calc_finish(entity, entity->budget);  in bfq_update_fin_time_enqueue()
945 	if (backshifted && bfq_gt(st->vtime, entity->finish)) {  in bfq_update_fin_time_enqueue()
946 		unsigned long delta = st->vtime - entity->finish;  in bfq_update_fin_time_enqueue()
951 		entity->start += delta;  in bfq_update_fin_time_enqueue()
952 		entity->finish += delta;  in bfq_update_fin_time_enqueue()
955 	bfq_active_insert(st, entity);  in bfq_update_fin_time_enqueue()
970 static void __bfq_activate_entity(struct bfq_entity *entity,  in __bfq_activate_entity()  argument
973 	struct bfq_service_tree *st = bfq_entity_service_tree(entity);  in __bfq_activate_entity()
978 	if (non_blocking_wait_rq && bfq_gt(st->vtime, entity->finish)) {  in __bfq_activate_entity()
980 		min_vstart = entity->finish;  in __bfq_activate_entity()
984 	if (entity->tree == &st->idle) {  in __bfq_activate_entity()
989 		bfq_idle_extract(st, entity);  in __bfq_activate_entity()
990 		entity->start = bfq_gt(min_vstart, entity->finish) ?  in __bfq_activate_entity()
991 			min_vstart : entity->finish;  in __bfq_activate_entity()
998 		entity->start = min_vstart;  in __bfq_activate_entity()
999 		st->wsum += entity->weight;  in __bfq_activate_entity()
1006 		bfq_get_entity(entity);  in __bfq_activate_entity()
1008 		entity->on_st = true;  in __bfq_activate_entity()
1012 	if (!bfq_entity_to_bfqq(entity)) { /* bfq_group */  in __bfq_activate_entity()
1014 			container_of(entity, struct bfq_group, entity);  in __bfq_activate_entity()
1016 		bfq_weights_tree_add(bfqg->bfqd, entity,  in __bfq_activate_entity()
1021 	bfq_update_fin_time_enqueue(entity, st, backshifted);  in __bfq_activate_entity()
1039 static void __bfq_requeue_entity(struct bfq_entity *entity)  in __bfq_requeue_entity()  argument
1041 	struct bfq_sched_data *sd = entity->sched_data;  in __bfq_requeue_entity()
1042 	struct bfq_service_tree *st = bfq_entity_service_tree(entity);  in __bfq_requeue_entity()
1044 	if (entity == sd->in_service_entity) {  in __bfq_requeue_entity()
1067 		bfq_calc_finish(entity, entity->service);  in __bfq_requeue_entity()
1068 		entity->start = entity->finish;  in __bfq_requeue_entity()
1082 		if (entity->tree)  in __bfq_requeue_entity()
1083 			bfq_active_extract(st, entity);  in __bfq_requeue_entity()
1099 		bfq_active_extract(st, entity);  in __bfq_requeue_entity()
1102 	bfq_update_fin_time_enqueue(entity, st, false);  in __bfq_requeue_entity()
1105 static void __bfq_activate_requeue_entity(struct bfq_entity *entity,  in __bfq_activate_requeue_entity()  argument
1109 	struct bfq_service_tree *st = bfq_entity_service_tree(entity);  in __bfq_activate_requeue_entity()
1111 	if (sd->in_service_entity == entity || entity->tree == &st->active)  in __bfq_activate_requeue_entity()
1116 		__bfq_requeue_entity(entity);  in __bfq_activate_requeue_entity()
1122 		__bfq_activate_entity(entity, non_blocking_wait_rq);  in __bfq_activate_requeue_entity()
1139 static void bfq_activate_requeue_entity(struct bfq_entity *entity,  in bfq_activate_requeue_entity()  argument
1145 	for_each_entity(entity) {  in bfq_activate_requeue_entity()
1146 		sd = entity->sched_data;  in bfq_activate_requeue_entity()
1147 		__bfq_activate_requeue_entity(entity, sd, non_blocking_wait_rq);  in bfq_activate_requeue_entity()
1149 		if (!bfq_update_next_in_service(sd, entity, expiration) &&  in bfq_activate_requeue_entity()
1166 bool __bfq_deactivate_entity(struct bfq_entity *entity, bool ins_into_idle_tree)  in __bfq_deactivate_entity()  argument
1168 	struct bfq_sched_data *sd = entity->sched_data;  in __bfq_deactivate_entity()
1172 	if (!entity->on_st) /* entity never activated, or already inactive */  in __bfq_deactivate_entity()
1181 	st = bfq_entity_service_tree(entity);  in __bfq_deactivate_entity()
1182 	is_in_service = entity == sd->in_service_entity;  in __bfq_deactivate_entity()
1185 		bfq_calc_finish(entity, entity->service);  in __bfq_deactivate_entity()
1189 	if (entity->tree == &st->active)  in __bfq_deactivate_entity()
1190 		bfq_active_extract(st, entity);  in __bfq_deactivate_entity()
1191 	else if (!is_in_service && entity->tree == &st->idle)  in __bfq_deactivate_entity()
1192 		bfq_idle_extract(st, entity);  in __bfq_deactivate_entity()
1194 	if (!ins_into_idle_tree || !bfq_gt(entity->finish, st->vtime))  in __bfq_deactivate_entity()
1195 		bfq_forget_entity(st, entity, is_in_service);  in __bfq_deactivate_entity()
1197 		bfq_idle_insert(st, entity);  in __bfq_deactivate_entity()
1209 static void bfq_deactivate_entity(struct bfq_entity *entity,  in bfq_deactivate_entity()  argument
1216 	for_each_entity_safe(entity, parent) {  in bfq_deactivate_entity()
1217 		sd = entity->sched_data;  in bfq_deactivate_entity()
1219 		if (!__bfq_deactivate_entity(entity, ins_into_idle_tree)) {  in bfq_deactivate_entity()
1230 		if (sd->next_in_service == entity)  in bfq_deactivate_entity()
1284 	entity = parent;  in bfq_deactivate_entity()
1285 	for_each_entity(entity) {  in bfq_deactivate_entity()
1292 		__bfq_requeue_entity(entity);  in bfq_deactivate_entity()
1294 		sd = entity->sched_data;  in bfq_deactivate_entity()
1295 		if (!bfq_update_next_in_service(sd, entity, expiration) &&  in bfq_deactivate_entity()
1397 	struct bfq_entity *entity;  in __bfq_lookup_next_entity()  local
1422 	entity = bfq_first_active_entity(st, new_vtime);  in __bfq_lookup_next_entity()
1424 	return entity;  in __bfq_lookup_next_entity()
1441 	struct bfq_entity *entity = NULL;  in bfq_lookup_next_entity()  local
1479 		entity = __bfq_lookup_next_entity(st + class_idx,  in bfq_lookup_next_entity()
1483 		if (entity)  in bfq_lookup_next_entity()
1487 	if (!entity)  in bfq_lookup_next_entity()
1490 	return entity;  in bfq_lookup_next_entity()
1505 	struct bfq_entity *entity = NULL;  in bfq_get_next_queue()  local
1518 	for (; sd ; sd = entity->my_sched_data) {  in bfq_get_next_queue()
1544 		entity = sd->next_in_service;  in bfq_get_next_queue()
1545 		sd->in_service_entity = entity;  in bfq_get_next_queue()
1555 		if (bfq_no_longer_next_in_service(entity))  in bfq_get_next_queue()
1556 			bfq_active_extract(bfq_entity_service_tree(entity),  in bfq_get_next_queue()
1557 					   entity);  in bfq_get_next_queue()
1579 	bfqq = bfq_entity_to_bfqq(entity);  in bfq_get_next_queue()
1585 	for_each_entity(entity) {  in bfq_get_next_queue()
1586 		struct bfq_sched_data *sd = entity->sched_data;  in bfq_get_next_queue()
1598 	struct bfq_entity *in_serv_entity = &in_serv_bfqq->entity;  in __bfq_bfqd_reset_in_service()
1599 	struct bfq_entity *entity = in_serv_entity;  in __bfq_bfqd_reset_in_service()  local
1611 	for_each_entity(entity)  in __bfq_bfqd_reset_in_service()
1612 		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()
1688 			bfq_weights_tree_add(bfqd, &bfqq->entity,  in bfq_add_bfqq_busy()