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()
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()
258  * @weight: scale factor (weight of an entity or weight sum).
266  * bfq_calc_finish - assign the finish time to an entity.
267  * @entity: the entity to act upon.
268  * @service: the service to be charged to the entity.
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()
289  * bfq_entity_of - get an entity from a node.
290  * @node: the node field of the entity.
292  * Convert a node pointer to the relative entity.  This is used only
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()
308  * bfq_extract - remove an entity from a tree.
310  * @entity: the entity to remove.
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()
319  * bfq_idle_extract - extract an entity from the idle tree.
320  * @st: the service tree of the owning @entity.
321  * @entity: the entity being removed.
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()
348  * @entity: entity to insert.
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()
376  * bfq_update_min - update the min_start field of a entity.
377  * @entity: the entity to update.
380  * This function is called when @entity may store an invalid value for
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()
444  * bfq_active_insert - insert an entity in the active tree of its
446  * @st: the service tree of the entity.
447  * @entity: the entity being inserted.
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()
552  * bfq_active_extract - remove an entity from the active tree.
554  * @entity: the entity being removed.
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()
587  * bfq_idle_insert - insert an entity into the idle tree.
589  * @entity: the entity to insert.
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()
610  * bfq_forget_entity - do not consider entity any longer for scheduling
612  * @entity: the entity being removed.
613  * @is_in_service: true if entity is currently the in-service entity.
615  * Forget everything about @entity. In addition, if entity represents
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()
637  * bfq_put_idle_entity - release the idle tree ref of an entity.
638  * @st: service tree for the entity.
639  * @entity: the entity being released.
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()
682  * Update weight and priority of entity. If update_class_too is true,
683  * then update the ioprio_class of entity too.
687  * entity implies changing the destination service trees for that
688  * entity. If such a change occurred when the entity is already on one
690  * entity would become more complex: none of the new possible service
691  * trees for the entity, according to bfq_entity_service_tree(), would
692  * match any of the possible service trees on which the entity
693  * is. Complex operations involving these trees, such as entity
697  * entity may happen to be on some 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()
761 		 * when entity->finish <= old_st->vtime).  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()
769 		 * If the weight of the entity changes, and the entity is a  in __bfq_entity_update_weight_prio()
770 		 * queue, remove the entity from its old weight counter (if  in __bfq_entity_update_weight_prio()
771 		 * there is a counter associated with the entity).  in __bfq_entity_update_weight_prio()
777 		entity->weight = new_weight;  in __bfq_entity_update_weight_prio()
779 		 * Add the entity, if it is not a weight-raised queue,  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()
881 	 * When this function is invoked, entity is not in any service  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()
908 	 * entity (only a queue can happen to have the backshifted  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()
935  * __bfq_activate_entity - handle activation of entity.
936  * @entity: the entity being activated.
937  * @non_blocking_wait_rq: true if entity was waiting for a request
939  * Called for a 'true' activation, i.e., if entity is not active and
942  * Basically, this function updates the timestamps of entity and
943  * inserts entity into its active tree, after possibly extracting it
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()
970 		 * The finish time of the entity may be invalid, and  in __bfq_activate_entity()
974 		entity->start = min_vstart;  in __bfq_activate_entity()
975 		st->wsum += entity->weight;  in __bfq_activate_entity()
977 		 * entity is about to be inserted into a service tree,  in __bfq_activate_entity()
979 		 * sure entity does not disappear until it is no  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()
1004  * __bfq_requeue_entity - handle requeueing or repositioning of an entity.
1005  * @entity: the entity being requeued or repositioned.
1007  * Requeueing is needed if this entity stops being served, which
1008  * happens if a leaf descendant entity has expired. On the other hand,
1010  * entity has changed. See the comments inside the function for
1013  * Basically, this function: 1) removes entity from its active tree if
1014  * present there, 2) updates the timestamps of entity and 3) inserts
1015  * entity back into its active tree (in the new, right position for
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()
1025 		 * We are requeueing the current in-service entity,  in __bfq_requeue_entity()
1028 		 * - entity represents the in-service queue, and the  in __bfq_requeue_entity()
1031 		 * - entity represents a group, and its budget has  in __bfq_requeue_entity()
1034 		 *   reason; the timestamps of the entity need then to  in __bfq_requeue_entity()
1035 		 *   be updated, and the entity needs to be enqueued  in __bfq_requeue_entity()
1039 		 * the entity must be moved forward to account for the  in __bfq_requeue_entity()
1040 		 * service that the entity has received while in  in __bfq_requeue_entity()
1044 		 * the 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()
1049 		 * In addition, if the entity had more than one child  in __bfq_requeue_entity()
1052 		 * the entity in the active tree may need to be  in __bfq_requeue_entity()
1054 		 * time of the entity, and we will update its finish  in __bfq_requeue_entity()
1058 		 * entity here, 2) update the finish time and requeue  in __bfq_requeue_entity()
1059 		 * the entity according to the new timestamps below.  in __bfq_requeue_entity()
1061 		if (entity->tree)  in __bfq_requeue_entity()
1062 			bfq_active_extract(st, entity);  in __bfq_requeue_entity()
1063 	} else { /* The entity is already active, and not in service */  in __bfq_requeue_entity()
1066 		 * next_in_service entity below this entity has  in __bfq_requeue_entity()
1068 		 * this entity to change, which, finally implies that  in __bfq_requeue_entity()
1069 		 * the finish time of this entity must be  in __bfq_requeue_entity()
1072 		 * entity to change. We handle this change by: 1)  in __bfq_requeue_entity()
1073 		 * dequeueing the entity here, 2) updating the finish  in __bfq_requeue_entity()
1074 		 * time and requeueing the entity according to the new  in __bfq_requeue_entity()
1076 		 * non-extracted-entity sub-case above.  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()
1106  * bfq_activate_requeue_entity - activate or requeue an entity representing a
1110  * @entity: the entity to activate.
1111  * @non_blocking_wait_rq: true if this entity was waiting for a request
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()
1136  * entity, so as to represent entity as inactive
1137  * @entity: the entity being deactivated.
1138  * @ins_into_idle_tree: if false, the entity will not be put into the
1141  * If necessary and allowed, puts entity into the idle tree. NOTE:
1142  * entity may be on no tree if in service.
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()
1151 					* entity never activated, or  in __bfq_deactivate_entity()
1157 	 * If we get here, then entity is active, which implies that  in __bfq_deactivate_entity()
1159 	 * represented by entity. Therefore, the field  in __bfq_deactivate_entity()
1160 	 * entity->sched_data has been set, and we can safely use it.  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()
1171 		 * Non in-service entity: nobody will take care of  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()
1191  * bfq_deactivate_entity - deactivate an entity representing a bfq_queue.
1192  * @entity: the entity to deactivate.
1193  * @ins_into_idle_tree: true if the entity can be put into the idle tree
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()
1209 			 * entity is not in any tree any more, so  in bfq_deactivate_entity()
1218 		if (sd->next_in_service == entity)  in bfq_deactivate_entity()
1220 			 * entity was the next_in_service entity,  in bfq_deactivate_entity()
1221 			 * then, since entity has just been  in bfq_deactivate_entity()
1228 			 * The parent entity is still active, because  in bfq_deactivate_entity()
1237 			 * although the parent entity is evidently  in bfq_deactivate_entity()
1238 			 * active. This happens if 1) the entity  in bfq_deactivate_entity()
1240 			 * active entity in the parent entity, and 2)  in bfq_deactivate_entity()
1272 	entity = parent;  in bfq_deactivate_entity()
1273 	for_each_entity(entity) {  in bfq_deactivate_entity()
1275 		 * Invoke __bfq_requeue_entity on entity, even if  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()
1287 			 * any change in entity->parent->sd, and no  in bfq_deactivate_entity()
1297  *                       if needed, to have at least one entity eligible.
1321  * bfq_first_active_entity - find the eligible entity with
1326  * This function searches the first schedulable entity, starting from the
1328  * a subtree with at least one eligible (start <= vtime) entity. The path on
1330  * entities and b) no eligible entity has been found yet.
1361  * __bfq_lookup_next_entity - return the first eligible entity in @st.
1363  * @in_service: whether or not there is an in-service entity for the sched_data
1366  * If there is no in-service entity for the sched_data st belongs to,
1367  * then return the entity that will be set in service if:
1368  * 1) the parent entity this st belongs to is set in service;
1369  * 2) no entity belonging to such parent entity undergoes a state change
1370  * that would influence the timestamps of the entity (e.g., becomes idle,
1376  * In contrast, if there is an in-service entity, then return the
1377  * entity that would be set in service if not only the above
1379  * in-service entity, on expiration,
1387 	struct bfq_entity *entity;  in __bfq_lookup_next_entity()  local
1395 	 * least one entity is eligible.  in __bfq_lookup_next_entity()
1400 	 * If there is no in-service entity for the sched_data this  in __bfq_lookup_next_entity()
1402 	 * up to the value that guarantees that at least one entity is  in __bfq_lookup_next_entity()
1403 	 * eligible. If, instead, there is an in-service entity, then  in __bfq_lookup_next_entity()
1405 	 * eligible entity, namely the in-service one (even if the  in __bfq_lookup_next_entity()
1406 	 * entity is not on st, because it was extracted when set in  in __bfq_lookup_next_entity()
1412 	entity = bfq_first_active_entity(st, new_vtime);  in __bfq_lookup_next_entity()
1414 	return entity;  in __bfq_lookup_next_entity()
1418  * bfq_lookup_next_entity - return the first eligible entity in @sd.
1423  * for sd, and we need to know what is the new next entity to serve
1431 	struct bfq_entity *entity = NULL;  in bfq_lookup_next_entity()  local
1436 	 * bandwidth to this class (and if there is some active entity  in bfq_lookup_next_entity()
1450 	 * Find the next entity to serve for the highest-priority  in bfq_lookup_next_entity()
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
1500 	 * Traverse the path from the root to the leaf entity to  in bfq_get_next_queue()
1505 	for (; sd ; sd = entity->my_sched_data) {  in bfq_get_next_queue()
1507 		 * WARNING. We are about to set the in-service entity  in bfq_get_next_queue()
1512 		 * activation or deactivation of an entity. In this  in bfq_get_next_queue()
1515 		 * probability, yield a different entity than that  in bfq_get_next_queue()
1517 		 * happens in case there was no CLASS_IDLE entity to  in bfq_get_next_queue()
1520 		 * such entity.  in bfq_get_next_queue()
1523 		 * such entity in CLASS_IDLE is postponed until the  in bfq_get_next_queue()
1524 		 * service of the sd->next_in_service entity  in bfq_get_next_queue()
1530 		/* Make next_in_service entity become in_service_entity */  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()
1535 		 * If entity is no longer a candidate for next  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()
1547 		 * Even if entity is not to be extracted according to  in bfq_get_next_queue()
1548 		 * the above check, a descendant entity may get  in bfq_get_next_queue()
1552 		 * entity, and thus possibly back to this level.  in bfq_get_next_queue()
1557 		 * the correct next-to-serve candidate entity for each  in bfq_get_next_queue()
1558 		 * level, we need first to find the leaf entity to set  in bfq_get_next_queue()
1560 		 * the next-to-serve leaf entity, we can discover  in bfq_get_next_queue()
1561 		 * whether the parent entity of the leaf entity  in bfq_get_next_queue()
1566 	bfqq = bfq_entity_to_bfqq(entity);  in bfq_get_next_queue()
1570 	 * path from the leaf entity just set in service to the root.  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
1597 	 * path from entity to the root.  in __bfq_bfqd_reset_in_service()
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()