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()
52  * @new_entity: if not NULL, pointer to the entity whose activation,
56  *             expiration of the in-service entity
60  * extraction of an entity into/from one of the active trees of
65  * reposition an entity in its active tree; see comments on
68  * just activated or requeued entity.
71  * entity->parent may become the next_in_service for its parent
72  * entity.
84 	 * or repositioning of an entity that does not coincide with  in bfq_update_next_in_service()
87 	 * just-modified entity has the same priority as  in bfq_update_next_in_service()
90 	 * condition holds, then the new entity becomes the new  in bfq_update_next_in_service()
104 		 * entity, then compare timestamps to decide whether  in bfq_update_next_in_service()
147  * become the next_in_service entity for its parent entity.
161 	 * is not the root group. We must not touch the root entity  in bfq_update_parent_budget()
162 	 * as it must never become an in-service entity.  in bfq_update_parent_budget()
175  * This function tells whether entity stops being a candidate for next
178  * entity that is about to be set in service.
180  * If entity is a queue, then the entity is no longer a candidate for
181  * next service according to the that definition, because entity is
183  * true if entity is a queue.
185  * In contrast, entity could still be a candidate for next service if
189  * entity, even according to the above definition. As a consequence, a
190  * non-queue entity is not a candidate for next-service only if it has
192  * function returns true for a non-queue entity.
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()
206 	 * not account for the in-service entity in case the latter is  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()
284  * @weight: scale factor (weight of an entity or weight sum).
292  * bfq_calc_finish - assign the finish time to an entity.
293  * @entity: the entity to act upon.
294  * @service: the service to be charged to the entity.
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()
315  * bfq_entity_of - get an entity from a node.
316  * @node: the node field of the entity.
318  * Convert a node pointer to the relative entity.  This is used only
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()
334  * bfq_extract - remove an entity from a tree.
336  * @entity: the entity to remove.
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()
345  * bfq_idle_extract - extract an entity from the idle tree.
346  * @st: the service tree of the owning @entity.
347  * @entity: the entity being removed.
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()
374  * @entity: entity to insert.
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()
402  * bfq_update_min - update the min_start field of a entity.
403  * @entity: the entity to update.
406  * This function is called when @entity may store an invalid value for
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()
470  * bfq_active_insert - insert an entity in the active tree of its
472  * @st: the service tree of the entity.
473  * @entity: the entity being inserted.
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()
566  * bfq_active_extract - remove an entity from the active tree.
568  * @entity: the entity being removed.
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()
588  * bfq_idle_insert - insert an entity into the idle tree.
590  * @entity: the entity to insert.
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()
611  * bfq_forget_entity - do not consider entity any longer for scheduling
613  * @entity: the entity being removed.
614  * @is_in_service: true if entity is currently the in-service entity.
616  * Forget everything about @entity. In addition, if entity represents
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()
638  * bfq_put_idle_entity - release the idle tree ref of an entity.
639  * @st: service tree for the entity.
640  * @entity: the entity being released.
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()
683  * Update weight and priority of entity. If update_class_too is true,
684  * then update the ioprio_class of entity too.
688  * entity implies changing the destination service trees for that
689  * entity. If such a change occurred when the entity is already on one
691  * entity would become more complex: none of the new possible service
692  * trees for the entity, according to bfq_entity_service_tree(), would
693  * match any of the possible service trees on which the entity
694  * is. Complex operations involving these trees, such as entity
698  * entity may happen to be on some 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()
746 		 * when entity->finish <= old_st->vtime).  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()
754 		 * If the weight of the entity changes, and the entity is a  in __bfq_entity_update_weight_prio()
755 		 * queue, remove the entity from its old weight counter (if  in __bfq_entity_update_weight_prio()
756 		 * there is a counter associated with the entity).  in __bfq_entity_update_weight_prio()
760 		entity->weight = new_weight;  in __bfq_entity_update_weight_prio()
762 		 * Add the entity, if it is not a weight-raised queue,  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()
862 	 * When this function is invoked, entity is not in any service  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()
889 	 * entity (only a queue can happen to have the backshifted  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()
916  * __bfq_activate_entity - handle activation of entity.
917  * @entity: the entity being activated.
918  * @non_blocking_wait_rq: true if entity was waiting for a request
920  * Called for a 'true' activation, i.e., if entity is not active and
923  * Basically, this function updates the timestamps of entity and
924  * inserts entity into its active tree, after possibly extracting it
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()
951 		 * The finish time of the entity may be invalid, and  in __bfq_activate_entity()
955 		entity->start = min_vstart;  in __bfq_activate_entity()
956 		st->wsum += entity->weight;  in __bfq_activate_entity()
958 		 * entity is about to be inserted into a service tree,  in __bfq_activate_entity()
960 		 * sure entity does not disappear until it is no  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()
972  * __bfq_requeue_entity - handle requeueing or repositioning of an entity.
973  * @entity: the entity being requeued or repositioned.
975  * Requeueing is needed if this entity stops being served, which
976  * happens if a leaf descendant entity has expired. On the other hand,
978  * entity has changed. See the comments inside the function for
981  * Basically, this function: 1) removes entity from its active tree if
982  * present there, 2) updates the timestamps of entity and 3) inserts
983  * entity back into its active tree (in the new, right position for
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()
993 		 * We are requeueing the current in-service entity,  in __bfq_requeue_entity()
996 		 * - entity represents the in-service queue, and the  in __bfq_requeue_entity()
999 		 * - entity represents a group, and its budget has  in __bfq_requeue_entity()
1002 		 *   reason; the timestamps of the entity need then to  in __bfq_requeue_entity()
1003 		 *   be updated, and the entity needs to be enqueued  in __bfq_requeue_entity()
1007 		 * the entity must be moved forward to account for the  in __bfq_requeue_entity()
1008 		 * service that the entity has received while in  in __bfq_requeue_entity()
1012 		 * the 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()
1017 		 * In addition, if the entity had more than one child  in __bfq_requeue_entity()
1020 		 * the entity in the active tree may need to be  in __bfq_requeue_entity()
1022 		 * time of the entity, and we will update its finish  in __bfq_requeue_entity()
1026 		 * entity here, 2) update the finish time and requeue  in __bfq_requeue_entity()
1027 		 * the entity according to the new timestamps below.  in __bfq_requeue_entity()
1029 		if (entity->tree)  in __bfq_requeue_entity()
1030 			bfq_active_extract(st, entity);  in __bfq_requeue_entity()
1031 	} else { /* The entity is already active, and not in service */  in __bfq_requeue_entity()
1034 		 * next_in_service entity below this entity has  in __bfq_requeue_entity()
1036 		 * this entity to change, which, finally implies that  in __bfq_requeue_entity()
1037 		 * the finish time of this entity must be  in __bfq_requeue_entity()
1040 		 * entity to change. We handle this change by: 1)  in __bfq_requeue_entity()
1041 		 * dequeueing the entity here, 2) updating the finish  in __bfq_requeue_entity()
1042 		 * time and requeueing the entity according to the new  in __bfq_requeue_entity()
1044 		 * non-extracted-entity sub-case above.  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()
1074  * bfq_activate_requeue_entity - activate or requeue an entity representing a
1078  * @entity: the entity to activate.
1079  * @non_blocking_wait_rq: true if this entity was waiting for a request
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()
1100  * entity, so as to represent entity as inactive
1101  * @entity: the entity being deactivated.
1102  * @ins_into_idle_tree: if false, the entity will not be put into the
1105  * If necessary and allowed, puts entity into the idle tree. NOTE:
1106  * entity may be on no tree if in service.
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()
1115 					* entity never activated, or  in __bfq_deactivate_entity()
1121 	 * If we get here, then entity is active, which implies that  in __bfq_deactivate_entity()
1123 	 * represented by entity. Therefore, the field  in __bfq_deactivate_entity()
1124 	 * entity->sched_data has been set, and we can safely use it.  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()
1135 		 * Non in-service entity: nobody will take care of  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()
1155  * bfq_deactivate_entity - deactivate an entity representing a bfq_queue.
1156  * @entity: the entity to deactivate.
1157  * @ins_into_idle_tree: true if the entity can be put into the idle tree
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()
1173 			 * entity is not in any tree any more, so  in bfq_deactivate_entity()
1182 		if (sd->next_in_service == entity)  in bfq_deactivate_entity()
1184 			 * entity was the next_in_service entity,  in bfq_deactivate_entity()
1185 			 * then, since entity has just been  in bfq_deactivate_entity()
1192 			 * The parent entity is still active, because  in bfq_deactivate_entity()
1201 			 * although the parent entity is evidently  in bfq_deactivate_entity()
1202 			 * active. This happens if 1) the entity  in bfq_deactivate_entity()
1204 			 * active entity in the parent entity, and 2)  in bfq_deactivate_entity()
1236 	entity = parent;  in bfq_deactivate_entity()
1237 	for_each_entity(entity) {  in bfq_deactivate_entity()
1239 		 * Invoke __bfq_requeue_entity on entity, even if  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()
1251 			 * any change in entity->parent->sd, and no  in bfq_deactivate_entity()
1261  *                       if needed, to have at least one entity eligible.
1285  * bfq_first_active_entity - find the eligible entity with
1290  * This function searches the first schedulable entity, starting from the
1292  * a subtree with at least one eligible (start <= vtime) entity. The path on
1294  * entities and b) no eligible entity has been found yet.
1325  * __bfq_lookup_next_entity - return the first eligible entity in @st.
1327  * @in_service: whether or not there is an in-service entity for the sched_data
1330  * If there is no in-service entity for the sched_data st belongs to,
1331  * then return the entity that will be set in service if:
1332  * 1) the parent entity this st belongs to is set in service;
1333  * 2) no entity belonging to such parent entity undergoes a state change
1334  * that would influence the timestamps of the entity (e.g., becomes idle,
1340  * In contrast, if there is an in-service entity, then return the
1341  * entity that would be set in service if not only the above
1343  * in-service entity, on expiration,
1351 	struct bfq_entity *entity;  in __bfq_lookup_next_entity()  local
1359 	 * least one entity is eligible.  in __bfq_lookup_next_entity()
1364 	 * If there is no in-service entity for the sched_data this  in __bfq_lookup_next_entity()
1366 	 * up to the value that guarantees that at least one entity is  in __bfq_lookup_next_entity()
1367 	 * eligible. If, instead, there is an in-service entity, then  in __bfq_lookup_next_entity()
1369 	 * eligible entity, namely the in-service one (even if the  in __bfq_lookup_next_entity()
1370 	 * entity is not on st, because it was extracted when set in  in __bfq_lookup_next_entity()
1376 	entity = bfq_first_active_entity(st, new_vtime);  in __bfq_lookup_next_entity()
1378 	return entity;  in __bfq_lookup_next_entity()
1382  * bfq_lookup_next_entity - return the first eligible entity in @sd.
1387  * for sd, and we need to know what is the new next entity to serve
1395 	struct bfq_entity *entity = NULL;  in bfq_lookup_next_entity()  local
1400 	 * bandwidth to this class (and if there is some active entity  in bfq_lookup_next_entity()
1414 	 * Find the next entity to serve for the highest-priority  in bfq_lookup_next_entity()
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
1464 	 * Traverse the path from the root to the leaf entity to  in bfq_get_next_queue()
1469 	for (; sd ; sd = entity->my_sched_data) {  in bfq_get_next_queue()
1471 		 * WARNING. We are about to set the in-service entity  in bfq_get_next_queue()
1476 		 * activation or deactivation of an entity. In this  in bfq_get_next_queue()
1479 		 * probability, yield a different entity than that  in bfq_get_next_queue()
1481 		 * happens in case there was no CLASS_IDLE entity to  in bfq_get_next_queue()
1484 		 * such entity.  in bfq_get_next_queue()
1487 		 * such entity in CLASS_IDLE is postponed until the  in bfq_get_next_queue()
1488 		 * service of the sd->next_in_service entity  in bfq_get_next_queue()
1494 		/* Make next_in_service entity become in_service_entity */  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()
1499 		 * If entity is no longer a candidate for next  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()
1511 		 * Even if entity is not to be extracted according to  in bfq_get_next_queue()
1512 		 * the above check, a descendant entity may get  in bfq_get_next_queue()
1516 		 * entity, and thus possibly back to this level.  in bfq_get_next_queue()
1521 		 * the correct next-to-serve candidate entity for each  in bfq_get_next_queue()
1522 		 * level, we need first to find the leaf entity to set  in bfq_get_next_queue()
1524 		 * the next-to-serve leaf entity, we can discover  in bfq_get_next_queue()
1525 		 * whether the parent entity of the leaf entity  in bfq_get_next_queue()
1530 	bfqq = bfq_entity_to_bfqq(entity);  in bfq_get_next_queue()
1534 	 * path from the leaf entity just set in service to the root.  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
1561 	 * path from entity to the root.  in __bfq_bfqd_reset_in_service()
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()