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()
221 static void bfq_inc_active_entities(struct bfq_entity *entity)  in bfq_inc_active_entities()  argument
223 	struct bfq_sched_data *sd = entity->sched_data;  in bfq_inc_active_entities()
230 static void bfq_dec_active_entities(struct bfq_entity *entity)  in bfq_dec_active_entities()  argument
232 	struct bfq_sched_data *sd = entity->sched_data;  in bfq_dec_active_entities()
246 static bool bfq_no_longer_next_in_service(struct bfq_entity *entity)  in bfq_no_longer_next_in_service()  argument
251 static void bfq_inc_active_entities(struct bfq_entity *entity)  in bfq_inc_active_entities()  argument
255 static void bfq_dec_active_entities(struct bfq_entity *entity)  in bfq_dec_active_entities()  argument
270 struct bfq_queue *bfq_entity_to_bfqq(struct bfq_entity *entity)  in bfq_entity_to_bfqq()  argument
274 	if (!entity->my_sched_data)  in bfq_entity_to_bfqq()
275 		bfqq = container_of(entity, struct bfq_queue, entity);  in bfq_entity_to_bfqq()
296 static void bfq_calc_finish(struct bfq_entity *entity, unsigned long service)  in bfq_calc_finish()  argument
298 	struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);  in bfq_calc_finish()
300 	entity->finish = entity->start +  in bfq_calc_finish()
301 		bfq_delta(service, entity->weight);  in bfq_calc_finish()
306 			service, entity->weight);  in bfq_calc_finish()
309 			entity->start, entity->finish,  in bfq_calc_finish()
310 			bfq_delta(service, entity->weight));  in bfq_calc_finish()
325 	struct bfq_entity *entity = NULL;  in bfq_entity_of()  local
328 		entity = rb_entry(node, struct bfq_entity, rb_node);  in bfq_entity_of()
330 	return entity;  in bfq_entity_of()
338 static void bfq_extract(struct rb_root *root, struct bfq_entity *entity)  in bfq_extract()  argument
340 	entity->tree = NULL;  in bfq_extract()
341 	rb_erase(&entity->rb_node, root);  in bfq_extract()
350 			     struct bfq_entity *entity)  in bfq_idle_extract()  argument
352 	struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);  in bfq_idle_extract()
355 	if (entity == st->first_idle) {  in bfq_idle_extract()
356 		next = rb_next(&entity->rb_node);  in bfq_idle_extract()
360 	if (entity == st->last_idle) {  in bfq_idle_extract()
361 		next = rb_prev(&entity->rb_node);  in bfq_idle_extract()
365 	bfq_extract(&st->idle, entity);  in bfq_idle_extract()
379 static void bfq_insert(struct rb_root *root, struct bfq_entity *entity)  in bfq_insert()  argument
389 		if (bfq_gt(entry->finish, entity->finish))  in bfq_insert()
395 	rb_link_node(&entity->rb_node, parent, node);  in bfq_insert()
396 	rb_insert_color(&entity->rb_node, root);  in bfq_insert()
398 	entity->tree = root;  in bfq_insert()
411 static void bfq_update_min(struct bfq_entity *entity, struct rb_node *node)  in bfq_update_min()  argument
417 		if (bfq_gt(entity->min_start, child->min_start))  in bfq_update_min()
418 			entity->min_start = child->min_start;  in bfq_update_min()
432 	struct bfq_entity *entity = rb_entry(node, struct bfq_entity, rb_node);  in bfq_update_active_node()  local
434 	entity->min_start = entity->start;  in bfq_update_active_node()
435 	bfq_update_min(entity, node->rb_right);  in bfq_update_active_node()
436 	bfq_update_min(entity, node->rb_left);  in bfq_update_active_node()
481 			      struct bfq_entity *entity)  in bfq_active_insert()  argument
483 	struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);  in bfq_active_insert()
484 	struct rb_node *node = &entity->rb_node;  in bfq_active_insert()
486 	bfq_insert(&st->active, entity);  in bfq_active_insert()
498 	bfq_inc_active_entities(entity);  in bfq_active_insert()
524 static void bfq_get_entity(struct bfq_entity *entity)  in bfq_get_entity()  argument
526 	struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);  in bfq_get_entity()
571 			       struct bfq_entity *entity)  in bfq_active_extract()  argument
573 	struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);  in bfq_active_extract()
576 	node = bfq_find_deepest(&entity->rb_node);  in bfq_active_extract()
577 	bfq_extract(&st->active, entity);  in bfq_active_extract()
584 	bfq_dec_active_entities(entity);  in bfq_active_extract()
593 			    struct bfq_entity *entity)  in bfq_idle_insert()  argument
595 	struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);  in bfq_idle_insert()
599 	if (!first_idle || bfq_gt(first_idle->finish, entity->finish))  in bfq_idle_insert()
600 		st->first_idle = entity;  in bfq_idle_insert()
601 	if (!last_idle || bfq_gt(entity->finish, last_idle->finish))  in bfq_idle_insert()
602 		st->last_idle = entity;  in bfq_idle_insert()
604 	bfq_insert(&st->idle, entity);  in bfq_idle_insert()
626 			      struct bfq_entity *entity,  in bfq_forget_entity()  argument
629 	struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);  in bfq_forget_entity()
631 	entity->on_st_or_in_serv = false;  in bfq_forget_entity()
632 	st->wsum -= entity->weight;  in bfq_forget_entity()
642 void bfq_put_idle_entity(struct bfq_service_tree *st, struct bfq_entity *entity)  in bfq_put_idle_entity()  argument
644 	bfq_idle_extract(st, entity);  in bfq_put_idle_entity()
645 	bfq_forget_entity(st, entity,  in bfq_put_idle_entity()
646 			  entity == entity->sched_data->in_service_entity);  in bfq_put_idle_entity()
674 struct bfq_service_tree *bfq_entity_service_tree(struct bfq_entity *entity)  in bfq_entity_service_tree()  argument
676 	struct bfq_sched_data *sched_data = entity->sched_data;  in bfq_entity_service_tree()
677 	unsigned int idx = bfq_class_idx(entity);  in bfq_entity_service_tree()
702 				struct bfq_entity *entity,  in __bfq_entity_update_weight_prio()  argument
707 	if (entity->prio_changed) {  in __bfq_entity_update_weight_prio()
708 		struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);  in __bfq_entity_update_weight_prio()
713 		old_st->wsum -= entity->weight;  in __bfq_entity_update_weight_prio()
715 		if (entity->new_weight != entity->orig_weight) {  in __bfq_entity_update_weight_prio()
716 			if (entity->new_weight < BFQ_MIN_WEIGHT ||  in __bfq_entity_update_weight_prio()
717 			    entity->new_weight > BFQ_MAX_WEIGHT) {  in __bfq_entity_update_weight_prio()
719 					entity->new_weight);  in __bfq_entity_update_weight_prio()
720 				if (entity->new_weight < BFQ_MIN_WEIGHT)  in __bfq_entity_update_weight_prio()
721 					entity->new_weight = BFQ_MIN_WEIGHT;  in __bfq_entity_update_weight_prio()
723 					entity->new_weight = BFQ_MAX_WEIGHT;  in __bfq_entity_update_weight_prio()
725 			entity->orig_weight = entity->new_weight;  in __bfq_entity_update_weight_prio()
728 				  bfq_weight_to_ioprio(entity->orig_weight);  in __bfq_entity_update_weight_prio()
739 			entity->prio_changed = 0;  in __bfq_entity_update_weight_prio()
748 		new_st = bfq_entity_service_tree(entity);  in __bfq_entity_update_weight_prio()
750 		prev_weight = entity->weight;  in __bfq_entity_update_weight_prio()
751 		new_weight = entity->orig_weight *  in __bfq_entity_update_weight_prio()
760 		entity->weight = new_weight;  in __bfq_entity_update_weight_prio()
768 		new_st->wsum += entity->weight;  in __bfq_entity_update_weight_prio()
771 			entity->start = new_st->vtime;  in __bfq_entity_update_weight_prio()
789 	struct bfq_entity *entity = &bfqq->entity;  in bfq_bfqq_served()  local
799 	for_each_entity(entity) {  in bfq_bfqq_served()
800 		st = bfq_entity_service_tree(entity);  in bfq_bfqq_served()
802 		entity->service += served;  in bfq_bfqq_served()
840 	struct bfq_entity *entity = &bfqq->entity;  in bfq_bfqq_charge_time()  local
845 	int tot_serv_to_charge = max(serv_to_charge_for_time, entity->service);  in bfq_bfqq_charge_time()
848 	if (tot_serv_to_charge > entity->budget)  in bfq_bfqq_charge_time()
849 		entity->budget = tot_serv_to_charge;  in bfq_bfqq_charge_time()
852 			max_t(int, 0, tot_serv_to_charge - entity->service));  in bfq_bfqq_charge_time()
855 static void bfq_update_fin_time_enqueue(struct bfq_entity *entity,  in bfq_update_fin_time_enqueue()  argument
859 	struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);  in bfq_update_fin_time_enqueue()
866 	st = __bfq_entity_update_weight_prio(st, entity, true);  in bfq_update_fin_time_enqueue()
867 	bfq_calc_finish(entity, entity->budget);  in bfq_update_fin_time_enqueue()
902 	if (backshifted && bfq_gt(st->vtime, entity->finish)) {  in bfq_update_fin_time_enqueue()
903 		unsigned long delta = st->vtime - entity->finish;  in bfq_update_fin_time_enqueue()
908 		entity->start += delta;  in bfq_update_fin_time_enqueue()
909 		entity->finish += delta;  in bfq_update_fin_time_enqueue()
912 	bfq_active_insert(st, entity);  in bfq_update_fin_time_enqueue()
927 static void __bfq_activate_entity(struct bfq_entity *entity,  in __bfq_activate_entity()  argument
930 	struct bfq_service_tree *st = bfq_entity_service_tree(entity);  in __bfq_activate_entity()
935 	if (non_blocking_wait_rq && bfq_gt(st->vtime, entity->finish)) {  in __bfq_activate_entity()
937 		min_vstart = entity->finish;  in __bfq_activate_entity()
941 	if (entity->tree == &st->idle) {  in __bfq_activate_entity()
946 		bfq_idle_extract(st, entity);  in __bfq_activate_entity()
947 		entity->start = bfq_gt(min_vstart, entity->finish) ?  in __bfq_activate_entity()
948 			min_vstart : entity->finish;  in __bfq_activate_entity()
955 		entity->start = min_vstart;  in __bfq_activate_entity()
956 		st->wsum += entity->weight;  in __bfq_activate_entity()
963 		bfq_get_entity(entity);  in __bfq_activate_entity()
965 		entity->on_st_or_in_serv = true;  in __bfq_activate_entity()
968 	bfq_update_fin_time_enqueue(entity, st, backshifted);  in __bfq_activate_entity()
986 static void __bfq_requeue_entity(struct bfq_entity *entity)  in __bfq_requeue_entity()  argument
988 	struct bfq_sched_data *sd = entity->sched_data;  in __bfq_requeue_entity()
989 	struct bfq_service_tree *st = bfq_entity_service_tree(entity);  in __bfq_requeue_entity()
991 	if (entity == sd->in_service_entity) {  in __bfq_requeue_entity()
1014 		bfq_calc_finish(entity, entity->service);  in __bfq_requeue_entity()
1015 		entity->start = entity->finish;  in __bfq_requeue_entity()
1029 		if (entity->tree)  in __bfq_requeue_entity()
1030 			bfq_active_extract(st, entity);  in __bfq_requeue_entity()
1046 		bfq_active_extract(st, entity);  in __bfq_requeue_entity()
1049 	bfq_update_fin_time_enqueue(entity, st, false);  in __bfq_requeue_entity()
1052 static void __bfq_activate_requeue_entity(struct bfq_entity *entity,  in __bfq_activate_requeue_entity()  argument
1055 	struct bfq_service_tree *st = bfq_entity_service_tree(entity);  in __bfq_activate_requeue_entity()
1057 	if (entity->sched_data->in_service_entity == entity ||  in __bfq_activate_requeue_entity()
1058 	    entity->tree == &st->active)  in __bfq_activate_requeue_entity()
1063 		__bfq_requeue_entity(entity);  in __bfq_activate_requeue_entity()
1069 		__bfq_activate_entity(entity, non_blocking_wait_rq);  in __bfq_activate_requeue_entity()
1086 static void bfq_activate_requeue_entity(struct bfq_entity *entity,  in bfq_activate_requeue_entity()  argument
1090 	for_each_entity(entity) {  in bfq_activate_requeue_entity()
1091 		__bfq_activate_requeue_entity(entity, non_blocking_wait_rq);  in bfq_activate_requeue_entity()
1092 		if (!bfq_update_next_in_service(entity->sched_data, entity,  in bfq_activate_requeue_entity()
1108 bool __bfq_deactivate_entity(struct bfq_entity *entity, bool ins_into_idle_tree)  in __bfq_deactivate_entity()  argument
1110 	struct bfq_sched_data *sd = entity->sched_data;  in __bfq_deactivate_entity()
1114 	if (!entity->on_st_or_in_serv) /*  in __bfq_deactivate_entity()
1126 	st = bfq_entity_service_tree(entity);  in __bfq_deactivate_entity()
1127 	is_in_service = entity == sd->in_service_entity;  in __bfq_deactivate_entity()
1129 	bfq_calc_finish(entity, entity->service);  in __bfq_deactivate_entity()
1139 		entity->service = 0;  in __bfq_deactivate_entity()
1141 	if (entity->tree == &st->active)  in __bfq_deactivate_entity()
1142 		bfq_active_extract(st, entity);  in __bfq_deactivate_entity()
1143 	else if (!is_in_service && entity->tree == &st->idle)  in __bfq_deactivate_entity()
1144 		bfq_idle_extract(st, entity);  in __bfq_deactivate_entity()
1146 	if (!ins_into_idle_tree || !bfq_gt(entity->finish, st->vtime))  in __bfq_deactivate_entity()
1147 		bfq_forget_entity(st, entity, is_in_service);  in __bfq_deactivate_entity()
1149 		bfq_idle_insert(st, entity);  in __bfq_deactivate_entity()
1161 static void bfq_deactivate_entity(struct bfq_entity *entity,  in bfq_deactivate_entity()  argument
1168 	for_each_entity_safe(entity, parent) {  in bfq_deactivate_entity()
1169 		sd = entity->sched_data;  in bfq_deactivate_entity()
1171 		if (!__bfq_deactivate_entity(entity, ins_into_idle_tree)) {  in bfq_deactivate_entity()
1182 		if (sd->next_in_service == entity)  in bfq_deactivate_entity()
1236 	entity = parent;  in bfq_deactivate_entity()
1237 	for_each_entity(entity) {  in bfq_deactivate_entity()
1244 		__bfq_requeue_entity(entity);  in bfq_deactivate_entity()
1246 		sd = entity->sched_data;  in bfq_deactivate_entity()
1247 		if (!bfq_update_next_in_service(sd, entity, expiration) &&  in bfq_deactivate_entity()
1351 	struct bfq_entity *entity;  in __bfq_lookup_next_entity()  local
1376 	entity = bfq_first_active_entity(st, new_vtime);  in __bfq_lookup_next_entity()
1378 	return entity;  in __bfq_lookup_next_entity()
1395 	struct bfq_entity *entity = NULL;  in bfq_lookup_next_entity()  local
1433 		entity = __bfq_lookup_next_entity(st + class_idx,  in bfq_lookup_next_entity()
1437 		if (entity)  in bfq_lookup_next_entity()
1441 	return entity;  in bfq_lookup_next_entity()
1456 	struct bfq_entity *entity = NULL;  in bfq_get_next_queue()  local
1469 	for (; sd ; sd = entity->my_sched_data) {  in bfq_get_next_queue()
1495 		entity = sd->next_in_service;  in bfq_get_next_queue()
1496 		sd->in_service_entity = entity;  in bfq_get_next_queue()
1506 		if (bfq_no_longer_next_in_service(entity))  in bfq_get_next_queue()
1507 			bfq_active_extract(bfq_entity_service_tree(entity),  in bfq_get_next_queue()
1508 					   entity);  in bfq_get_next_queue()
1530 	bfqq = bfq_entity_to_bfqq(entity);  in bfq_get_next_queue()
1536 	for_each_entity(entity) {  in bfq_get_next_queue()
1537 		struct bfq_sched_data *sd = entity->sched_data;  in bfq_get_next_queue()
1550 	struct bfq_entity *in_serv_entity = &in_serv_bfqq->entity;  in __bfq_bfqd_reset_in_service()
1551 	struct bfq_entity *entity = in_serv_entity;  in __bfq_bfqd_reset_in_service()  local
1563 	for_each_entity(entity)  in __bfq_bfqd_reset_in_service()
1564 		entity->sched_data->in_service_entity = NULL;  in __bfq_bfqd_reset_in_service()
1590 	struct bfq_entity *entity = &bfqq->entity;  in bfq_deactivate_bfqq()  local
1592 	bfq_deactivate_entity(entity, ins_into_idle_tree, expiration);  in bfq_deactivate_bfqq()
1597 	struct bfq_entity *entity = &bfqq->entity;  in bfq_activate_bfqq()  local
1599 	bfq_activate_requeue_entity(entity, bfq_bfqq_non_blocking_wait_rq(bfqq),  in bfq_activate_bfqq()
1607 	struct bfq_entity *entity = &bfqq->entity;  in bfq_requeue_bfqq()  local
1609 	bfq_activate_requeue_entity(entity, false,  in bfq_requeue_bfqq()
1616 	struct bfq_entity *entity = &bfqq->entity;  in bfq_add_bfqq_in_groups_with_pending_reqs()  local
1618 	if (!entity->in_groups_with_pending_reqs) {  in bfq_add_bfqq_in_groups_with_pending_reqs()
1619 		entity->in_groups_with_pending_reqs = true;  in bfq_add_bfqq_in_groups_with_pending_reqs()
1629 	struct bfq_entity *entity = &bfqq->entity;  in bfq_del_bfqq_in_groups_with_pending_reqs()  local
1631 	if (entity->in_groups_with_pending_reqs) {  in bfq_del_bfqq_in_groups_with_pending_reqs()
1632 		entity->in_groups_with_pending_reqs = false;  in bfq_del_bfqq_in_groups_with_pending_reqs()