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()
150 	struct bfq_entity *group_entity = bfqq->entity.parent;  in bfq_bfqq_to_bfqg()
153 		group_entity = &bfqq->bfqd->root_group->entity;  in bfq_bfqq_to_bfqg()
155 	return container_of(group_entity, struct bfq_group, entity);  in bfq_bfqq_to_bfqg()
160  * become the next_in_service entity for its parent entity.
174 	 * is not the root group. We must not touch the root entity  in bfq_update_parent_budget()
175 	 * as it must never become an in-service entity.  in bfq_update_parent_budget()
188  * This function tells whether entity stops being a candidate for next
191  * entity that is about to be set in service.
193  * If entity is a queue, then the entity is no longer a candidate for
194  * next service according to the that definition, because entity is
196  * true if entity is a queue.
198  * In contrast, entity could still be a candidate for next service if
202  * entity, even according to the above definition. As a consequence, a
203  * non-queue entity is not a candidate for next-service only if it has
205  * function returns true for a non-queue entity.
207 static bool bfq_no_longer_next_in_service(struct bfq_entity *entity)  in bfq_no_longer_next_in_service()  argument
211 	if (bfq_entity_to_bfqq(entity))  in bfq_no_longer_next_in_service()
214 	bfqg = container_of(entity, struct bfq_group, entity);  in bfq_no_longer_next_in_service()
219 	 * not account for the in-service entity in case the latter is  in bfq_no_longer_next_in_service()
246 static bool bfq_no_longer_next_in_service(struct bfq_entity *entity)  in bfq_no_longer_next_in_service()  argument
262 struct bfq_queue *bfq_entity_to_bfqq(struct bfq_entity *entity)  in bfq_entity_to_bfqq()  argument
266 	if (!entity->my_sched_data)  in bfq_entity_to_bfqq()
267 		bfqq = container_of(entity, struct bfq_queue, entity);  in bfq_entity_to_bfqq()
276  * @weight: scale factor (weight of an entity or weight sum).
284  * bfq_calc_finish - assign the finish time to an entity.
285  * @entity: the entity to act upon.
286  * @service: the service to be charged to the entity.
288 static void bfq_calc_finish(struct bfq_entity *entity, unsigned long service)  in bfq_calc_finish()  argument
290 	struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);  in bfq_calc_finish()
292 	entity->finish = entity->start +  in bfq_calc_finish()
293 		bfq_delta(service, entity->weight);  in bfq_calc_finish()
298 			service, entity->weight);  in bfq_calc_finish()
301 			entity->start, entity->finish,  in bfq_calc_finish()
302 			bfq_delta(service, entity->weight));  in bfq_calc_finish()
307  * bfq_entity_of - get an entity from a node.
308  * @node: the node field of the entity.
310  * Convert a node pointer to the relative entity.  This is used only
317 	struct bfq_entity *entity = NULL;  in bfq_entity_of()  local
320 		entity = rb_entry(node, struct bfq_entity, rb_node);  in bfq_entity_of()
322 	return entity;  in bfq_entity_of()
326  * bfq_extract - remove an entity from a tree.
328  * @entity: the entity to remove.
330 static void bfq_extract(struct rb_root *root, struct bfq_entity *entity)  in bfq_extract()  argument
332 	entity->tree = NULL;  in bfq_extract()
333 	rb_erase(&entity->rb_node, root);  in bfq_extract()
337  * bfq_idle_extract - extract an entity from the idle tree.
338  * @st: the service tree of the owning @entity.
339  * @entity: the entity being removed.
342 			     struct bfq_entity *entity)  in bfq_idle_extract()  argument
344 	struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);  in bfq_idle_extract()
347 	if (entity == st->first_idle) {  in bfq_idle_extract()
348 		next = rb_next(&entity->rb_node);  in bfq_idle_extract()
352 	if (entity == st->last_idle) {  in bfq_idle_extract()
353 		next = rb_prev(&entity->rb_node);  in bfq_idle_extract()
357 	bfq_extract(&st->idle, entity);  in bfq_idle_extract()
366  * @entity: entity to insert.
371 static void bfq_insert(struct rb_root *root, struct bfq_entity *entity)  in bfq_insert()  argument
381 		if (bfq_gt(entry->finish, entity->finish))  in bfq_insert()
387 	rb_link_node(&entity->rb_node, parent, node);  in bfq_insert()
388 	rb_insert_color(&entity->rb_node, root);  in bfq_insert()
390 	entity->tree = root;  in bfq_insert()
394  * bfq_update_min - update the min_start field of a entity.
395  * @entity: the entity to update.
398  * This function is called when @entity may store an invalid value for
403 static void bfq_update_min(struct bfq_entity *entity, struct rb_node *node)  in bfq_update_min()  argument
409 		if (bfq_gt(entity->min_start, child->min_start))  in bfq_update_min()
410 			entity->min_start = child->min_start;  in bfq_update_min()
424 	struct bfq_entity *entity = rb_entry(node, struct bfq_entity, rb_node);  in bfq_update_active_node()  local
426 	entity->min_start = entity->start;  in bfq_update_active_node()
427 	bfq_update_min(entity, node->rb_right);  in bfq_update_active_node()
428 	bfq_update_min(entity, node->rb_left);  in bfq_update_active_node()
462  * bfq_active_insert - insert an entity in the active tree of its
464  * @st: the service tree of the entity.
465  * @entity: the entity being inserted.
473 			      struct bfq_entity *entity)  in bfq_active_insert()  argument
475 	struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);  in bfq_active_insert()
476 	struct rb_node *node = &entity->rb_node;  in bfq_active_insert()
483 	bfq_insert(&st->active, entity);  in bfq_active_insert()
493 	sd = entity->sched_data;  in bfq_active_insert()
528 static void bfq_get_entity(struct bfq_entity *entity)  in bfq_get_entity()  argument
530 	struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);  in bfq_get_entity()
570  * bfq_active_extract - remove an entity from the active tree.
572  * @entity: the entity being removed.
575 			       struct bfq_entity *entity)  in bfq_active_extract()  argument
577 	struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);  in bfq_active_extract()
585 	node = bfq_find_deepest(&entity->rb_node);  in bfq_active_extract()
586 	bfq_extract(&st->active, entity);  in bfq_active_extract()
592 	sd = entity->sched_data;  in bfq_active_extract()
605  * bfq_idle_insert - insert an entity into the idle tree.
607  * @entity: the entity to insert.
610 			    struct bfq_entity *entity)  in bfq_idle_insert()  argument
612 	struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);  in bfq_idle_insert()
616 	if (!first_idle || bfq_gt(first_idle->finish, entity->finish))  in bfq_idle_insert()
617 		st->first_idle = entity;  in bfq_idle_insert()
618 	if (!last_idle || bfq_gt(entity->finish, last_idle->finish))  in bfq_idle_insert()
619 		st->last_idle = entity;  in bfq_idle_insert()
621 	bfq_insert(&st->idle, entity);  in bfq_idle_insert()
628  * bfq_forget_entity - do not consider entity any longer for scheduling
630  * @entity: the entity being removed.
631  * @is_in_service: true if entity is currently the in-service entity.
633  * Forget everything about @entity. In addition, if entity represents
643 			      struct bfq_entity *entity,  in bfq_forget_entity()  argument
646 	struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);  in bfq_forget_entity()
648 	entity->on_st_or_in_serv = false;  in bfq_forget_entity()
649 	st->wsum -= entity->weight;  in bfq_forget_entity()
655  * bfq_put_idle_entity - release the idle tree ref of an entity.
656  * @st: service tree for the entity.
657  * @entity: the entity being released.
659 void bfq_put_idle_entity(struct bfq_service_tree *st, struct bfq_entity *entity)  in bfq_put_idle_entity()  argument
661 	bfq_idle_extract(st, entity);  in bfq_put_idle_entity()
662 	bfq_forget_entity(st, entity,  in bfq_put_idle_entity()
663 			  entity == entity->sched_data->in_service_entity);  in bfq_put_idle_entity()
691 struct bfq_service_tree *bfq_entity_service_tree(struct bfq_entity *entity)  in bfq_entity_service_tree()  argument
693 	struct bfq_sched_data *sched_data = entity->sched_data;  in bfq_entity_service_tree()
694 	unsigned int idx = bfq_class_idx(entity);  in bfq_entity_service_tree()
700  * Update weight and priority of entity. If update_class_too is true,
701  * then update the ioprio_class of entity too.
705  * entity implies changing the destination service trees for that
706  * entity. If such a change occurred when the entity is already on one
708  * entity would become more complex: none of the new possible service
709  * trees for the entity, according to bfq_entity_service_tree(), would
710  * match any of the possible service trees on which the entity
711  * is. Complex operations involving these trees, such as entity
715  * entity may happen to be on some tree.
719 				struct bfq_entity *entity,  in __bfq_entity_update_weight_prio()  argument
724 	if (entity->prio_changed) {  in __bfq_entity_update_weight_prio()
725 		struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);  in __bfq_entity_update_weight_prio()
738 			sd = entity->my_sched_data;  in __bfq_entity_update_weight_prio()
746 		old_st->wsum -= entity->weight;  in __bfq_entity_update_weight_prio()
748 		if (entity->new_weight != entity->orig_weight) {  in __bfq_entity_update_weight_prio()
749 			if (entity->new_weight < BFQ_MIN_WEIGHT ||  in __bfq_entity_update_weight_prio()
750 			    entity->new_weight > BFQ_MAX_WEIGHT) {  in __bfq_entity_update_weight_prio()
752 					entity->new_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_MIN_WEIGHT;  in __bfq_entity_update_weight_prio()
756 					entity->new_weight = BFQ_MAX_WEIGHT;  in __bfq_entity_update_weight_prio()
758 			entity->orig_weight = entity->new_weight;  in __bfq_entity_update_weight_prio()
761 				  bfq_weight_to_ioprio(entity->orig_weight);  in __bfq_entity_update_weight_prio()
772 			entity->prio_changed = 0;  in __bfq_entity_update_weight_prio()
779 		 * when entity->finish <= old_st->vtime).  in __bfq_entity_update_weight_prio()
781 		new_st = bfq_entity_service_tree(entity);  in __bfq_entity_update_weight_prio()
783 		prev_weight = entity->weight;  in __bfq_entity_update_weight_prio()
784 		new_weight = entity->orig_weight *  in __bfq_entity_update_weight_prio()
787 		 * If the weight of the entity changes, and the entity is a  in __bfq_entity_update_weight_prio()
788 		 * queue, remove the entity from its old weight counter (if  in __bfq_entity_update_weight_prio()
789 		 * there is a counter associated with the entity).  in __bfq_entity_update_weight_prio()
795 		entity->weight = new_weight;  in __bfq_entity_update_weight_prio()
797 		 * Add the entity, if it is not a weight-raised queue,  in __bfq_entity_update_weight_prio()
805 		new_st->wsum += entity->weight;  in __bfq_entity_update_weight_prio()
808 			entity->start = new_st->vtime;  in __bfq_entity_update_weight_prio()
826 	struct bfq_entity *entity = &bfqq->entity;  in bfq_bfqq_served()  local
836 	for_each_entity(entity) {  in bfq_bfqq_served()
837 		st = bfq_entity_service_tree(entity);  in bfq_bfqq_served()
839 		entity->service += served;  in bfq_bfqq_served()
877 	struct bfq_entity *entity = &bfqq->entity;  in bfq_bfqq_charge_time()  local
882 	int tot_serv_to_charge = max(serv_to_charge_for_time, entity->service);  in bfq_bfqq_charge_time()
885 	if (tot_serv_to_charge > entity->budget)  in bfq_bfqq_charge_time()
886 		entity->budget = tot_serv_to_charge;  in bfq_bfqq_charge_time()
889 			max_t(int, 0, tot_serv_to_charge - entity->service));  in bfq_bfqq_charge_time()
892 static void bfq_update_fin_time_enqueue(struct bfq_entity *entity,  in bfq_update_fin_time_enqueue()  argument
896 	struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);  in bfq_update_fin_time_enqueue()
899 	 * When this function is invoked, entity is not in any service  in bfq_update_fin_time_enqueue()
903 	st = __bfq_entity_update_weight_prio(st, entity, true);  in bfq_update_fin_time_enqueue()
904 	bfq_calc_finish(entity, entity->budget);  in bfq_update_fin_time_enqueue()
926 	 * entity (only a queue can happen to have the backshifted  in bfq_update_fin_time_enqueue()
939 	if (backshifted && bfq_gt(st->vtime, entity->finish)) {  in bfq_update_fin_time_enqueue()
940 		unsigned long delta = st->vtime - entity->finish;  in bfq_update_fin_time_enqueue()
945 		entity->start += delta;  in bfq_update_fin_time_enqueue()
946 		entity->finish += delta;  in bfq_update_fin_time_enqueue()
949 	bfq_active_insert(st, entity);  in bfq_update_fin_time_enqueue()
953  * __bfq_activate_entity - handle activation of entity.
954  * @entity: the entity being activated.
955  * @non_blocking_wait_rq: true if entity was waiting for a request
957  * Called for a 'true' activation, i.e., if entity is not active and
960  * Basically, this function updates the timestamps of entity and
961  * inserts entity into its active tree, after possibly extracting it
964 static void __bfq_activate_entity(struct bfq_entity *entity,  in __bfq_activate_entity()  argument
967 	struct bfq_service_tree *st = bfq_entity_service_tree(entity);  in __bfq_activate_entity()
972 	if (non_blocking_wait_rq && bfq_gt(st->vtime, entity->finish)) {  in __bfq_activate_entity()
974 		min_vstart = entity->finish;  in __bfq_activate_entity()
978 	if (entity->tree == &st->idle) {  in __bfq_activate_entity()
983 		bfq_idle_extract(st, entity);  in __bfq_activate_entity()
984 		entity->start = bfq_gt(min_vstart, entity->finish) ?  in __bfq_activate_entity()
985 			min_vstart : entity->finish;  in __bfq_activate_entity()
988 		 * The finish time of the entity may be invalid, and  in __bfq_activate_entity()
992 		entity->start = min_vstart;  in __bfq_activate_entity()
993 		st->wsum += entity->weight;  in __bfq_activate_entity()
995 		 * entity is about to be inserted into a service tree,  in __bfq_activate_entity()
997 		 * sure entity does not disappear until it is no  in __bfq_activate_entity()
1000 		bfq_get_entity(entity);  in __bfq_activate_entity()
1002 		entity->on_st_or_in_serv = true;  in __bfq_activate_entity()
1006 	if (!bfq_entity_to_bfqq(entity)) { /* bfq_group */  in __bfq_activate_entity()
1008 			container_of(entity, struct bfq_group, entity);  in __bfq_activate_entity()
1011 		if (!entity->in_groups_with_pending_reqs) {  in __bfq_activate_entity()
1012 			entity->in_groups_with_pending_reqs = true;  in __bfq_activate_entity()
1018 	bfq_update_fin_time_enqueue(entity, st, backshifted);  in __bfq_activate_entity()
1022  * __bfq_requeue_entity - handle requeueing or repositioning of an entity.
1023  * @entity: the entity being requeued or repositioned.
1025  * Requeueing is needed if this entity stops being served, which
1026  * happens if a leaf descendant entity has expired. On the other hand,
1028  * entity has changed. See the comments inside the function for
1031  * Basically, this function: 1) removes entity from its active tree if
1032  * present there, 2) updates the timestamps of entity and 3) inserts
1033  * entity back into its active tree (in the new, right position for
1036 static void __bfq_requeue_entity(struct bfq_entity *entity)  in __bfq_requeue_entity()  argument
1038 	struct bfq_sched_data *sd = entity->sched_data;  in __bfq_requeue_entity()
1039 	struct bfq_service_tree *st = bfq_entity_service_tree(entity);  in __bfq_requeue_entity()
1041 	if (entity == sd->in_service_entity) {  in __bfq_requeue_entity()
1043 		 * We are requeueing the current in-service entity,  in __bfq_requeue_entity()
1046 		 * - entity represents the in-service queue, and the  in __bfq_requeue_entity()
1049 		 * - entity represents a group, and its budget has  in __bfq_requeue_entity()
1052 		 *   reason; the timestamps of the entity need then to  in __bfq_requeue_entity()
1053 		 *   be updated, and the entity needs to be enqueued  in __bfq_requeue_entity()
1057 		 * the entity must be moved forward to account for the  in __bfq_requeue_entity()
1058 		 * service that the entity has received while in  in __bfq_requeue_entity()
1062 		 * the entity.  in __bfq_requeue_entity()
1064 		bfq_calc_finish(entity, entity->service);  in __bfq_requeue_entity()
1065 		entity->start = entity->finish;  in __bfq_requeue_entity()
1067 		 * In addition, if the entity had more than one child  in __bfq_requeue_entity()
1070 		 * the entity in the active tree may need to be  in __bfq_requeue_entity()
1072 		 * time of the entity, and we will update its finish  in __bfq_requeue_entity()
1076 		 * entity here, 2) update the finish time and requeue  in __bfq_requeue_entity()
1077 		 * the entity according to the new timestamps below.  in __bfq_requeue_entity()
1079 		if (entity->tree)  in __bfq_requeue_entity()
1080 			bfq_active_extract(st, entity);  in __bfq_requeue_entity()
1081 	} else { /* The entity is already active, and not in service */  in __bfq_requeue_entity()
1084 		 * next_in_service entity below this entity has  in __bfq_requeue_entity()
1086 		 * this entity to change, which, finally implies that  in __bfq_requeue_entity()
1087 		 * the finish time of this entity must be  in __bfq_requeue_entity()
1090 		 * entity to change. We handle this change by: 1)  in __bfq_requeue_entity()
1091 		 * dequeueing the entity here, 2) updating the finish  in __bfq_requeue_entity()
1092 		 * time and requeueing the entity according to the new  in __bfq_requeue_entity()
1094 		 * non-extracted-entity sub-case above.  in __bfq_requeue_entity()
1096 		bfq_active_extract(st, entity);  in __bfq_requeue_entity()
1099 	bfq_update_fin_time_enqueue(entity, st, false);  in __bfq_requeue_entity()
1102 static void __bfq_activate_requeue_entity(struct bfq_entity *entity,  in __bfq_activate_requeue_entity()  argument
1106 	struct bfq_service_tree *st = bfq_entity_service_tree(entity);  in __bfq_activate_requeue_entity()
1108 	if (sd->in_service_entity == entity || entity->tree == &st->active)  in __bfq_activate_requeue_entity()
1113 		__bfq_requeue_entity(entity);  in __bfq_activate_requeue_entity()
1119 		__bfq_activate_entity(entity, non_blocking_wait_rq);  in __bfq_activate_requeue_entity()
1124  * bfq_activate_requeue_entity - activate or requeue an entity representing a
1128  * @entity: the entity to activate.
1129  * @non_blocking_wait_rq: true if this entity was waiting for a request
1136 static void bfq_activate_requeue_entity(struct bfq_entity *entity,  in bfq_activate_requeue_entity()  argument
1142 	for_each_entity(entity) {  in bfq_activate_requeue_entity()
1143 		sd = entity->sched_data;  in bfq_activate_requeue_entity()
1144 		__bfq_activate_requeue_entity(entity, sd, non_blocking_wait_rq);  in bfq_activate_requeue_entity()
1146 		if (!bfq_update_next_in_service(sd, entity, expiration) &&  in bfq_activate_requeue_entity()
1154  * entity, so as to represent entity as inactive
1155  * @entity: the entity being deactivated.
1156  * @ins_into_idle_tree: if false, the entity will not be put into the
1159  * If necessary and allowed, puts entity into the idle tree. NOTE:
1160  * entity may be on no tree if in service.
1162 bool __bfq_deactivate_entity(struct bfq_entity *entity, bool ins_into_idle_tree)  in __bfq_deactivate_entity()  argument
1164 	struct bfq_sched_data *sd = entity->sched_data;  in __bfq_deactivate_entity()
1168 	if (!entity->on_st_or_in_serv) /*  in __bfq_deactivate_entity()
1169 					* entity never activated, or  in __bfq_deactivate_entity()
1175 	 * If we get here, then entity is active, which implies that  in __bfq_deactivate_entity()
1177 	 * represented by entity. Therefore, the field  in __bfq_deactivate_entity()
1178 	 * entity->sched_data has been set, and we can safely use it.  in __bfq_deactivate_entity()
1180 	st = bfq_entity_service_tree(entity);  in __bfq_deactivate_entity()
1181 	is_in_service = entity == sd->in_service_entity;  in __bfq_deactivate_entity()
1183 	bfq_calc_finish(entity, entity->service);  in __bfq_deactivate_entity()
1189 		 * Non in-service entity: nobody will take care of  in __bfq_deactivate_entity()
1193 		entity->service = 0;  in __bfq_deactivate_entity()
1195 	if (entity->tree == &st->active)  in __bfq_deactivate_entity()
1196 		bfq_active_extract(st, entity);  in __bfq_deactivate_entity()
1197 	else if (!is_in_service && entity->tree == &st->idle)  in __bfq_deactivate_entity()
1198 		bfq_idle_extract(st, entity);  in __bfq_deactivate_entity()
1200 	if (!ins_into_idle_tree || !bfq_gt(entity->finish, st->vtime))  in __bfq_deactivate_entity()
1201 		bfq_forget_entity(st, entity, is_in_service);  in __bfq_deactivate_entity()
1203 		bfq_idle_insert(st, entity);  in __bfq_deactivate_entity()
1209  * bfq_deactivate_entity - deactivate an entity representing a bfq_queue.
1210  * @entity: the entity to deactivate.
1211  * @ins_into_idle_tree: true if the entity can be put into the idle tree
1215 static void bfq_deactivate_entity(struct bfq_entity *entity,  in bfq_deactivate_entity()  argument
1222 	for_each_entity_safe(entity, parent) {  in bfq_deactivate_entity()
1223 		sd = entity->sched_data;  in bfq_deactivate_entity()
1225 		if (!__bfq_deactivate_entity(entity, ins_into_idle_tree)) {  in bfq_deactivate_entity()
1227 			 * entity is not in any tree any more, so  in bfq_deactivate_entity()
1236 		if (sd->next_in_service == entity)  in bfq_deactivate_entity()
1238 			 * entity was the next_in_service entity,  in bfq_deactivate_entity()
1239 			 * then, since entity has just been  in bfq_deactivate_entity()
1246 			 * The parent entity is still active, because  in bfq_deactivate_entity()
1255 			 * although the parent entity is evidently  in bfq_deactivate_entity()
1256 			 * active. This happens if 1) the entity  in bfq_deactivate_entity()
1258 			 * active entity in the parent entity, and 2)  in bfq_deactivate_entity()
1290 	entity = parent;  in bfq_deactivate_entity()
1291 	for_each_entity(entity) {  in bfq_deactivate_entity()
1293 		 * Invoke __bfq_requeue_entity on entity, even if  in bfq_deactivate_entity()
1298 		__bfq_requeue_entity(entity);  in bfq_deactivate_entity()
1300 		sd = entity->sched_data;  in bfq_deactivate_entity()
1301 		if (!bfq_update_next_in_service(sd, entity, expiration) &&  in bfq_deactivate_entity()
1305 			 * any change in entity->parent->sd, and no  in bfq_deactivate_entity()
1315  *                       if needed, to have at least one entity eligible.
1339  * bfq_first_active_entity - find the eligible entity with
1344  * This function searches the first schedulable entity, starting from the
1346  * a subtree with at least one eligible (start <= vtime) entity. The path on
1348  * entities and b) no eligible entity has been found yet.
1379  * __bfq_lookup_next_entity - return the first eligible entity in @st.
1382  * If there is no in-service entity for the sched_data st belongs to,
1383  * then return the entity that will be set in service if:
1384  * 1) the parent entity this st belongs to is set in service;
1385  * 2) no entity belonging to such parent entity undergoes a state change
1386  * that would influence the timestamps of the entity (e.g., becomes idle,
1392  * In contrast, if there is an in-service entity, then return the
1393  * entity that would be set in service if not only the above
1395  * in-service entity, on expiration,
1403 	struct bfq_entity *entity;  in __bfq_lookup_next_entity()  local
1411 	 * least one entity is eligible.  in __bfq_lookup_next_entity()
1416 	 * If there is no in-service entity for the sched_data this  in __bfq_lookup_next_entity()
1418 	 * up to the value that guarantees that at least one entity is  in __bfq_lookup_next_entity()
1419 	 * eligible. If, instead, there is an in-service entity, then  in __bfq_lookup_next_entity()
1421 	 * eligible entity, namely the in-service one (even if the  in __bfq_lookup_next_entity()
1422 	 * entity is not on st, because it was extracted when set in  in __bfq_lookup_next_entity()
1428 	entity = bfq_first_active_entity(st, new_vtime);  in __bfq_lookup_next_entity()
1430 	return entity;  in __bfq_lookup_next_entity()
1434  * bfq_lookup_next_entity - return the first eligible entity in @sd.
1439  * for sd, and we need to know what is the new next entity to serve
1447 	struct bfq_entity *entity = NULL;  in bfq_lookup_next_entity()  local
1452 	 * bandwidth to this class (and if there is some active entity  in bfq_lookup_next_entity()
1466 	 * Find the next entity to serve for the highest-priority  in bfq_lookup_next_entity()
1485 		entity = __bfq_lookup_next_entity(st + class_idx,  in bfq_lookup_next_entity()
1489 		if (entity)  in bfq_lookup_next_entity()
1493 	if (!entity)  in bfq_lookup_next_entity()
1496 	return entity;  in bfq_lookup_next_entity()
1511 	struct bfq_entity *entity = NULL;  in bfq_get_next_queue()  local
1519 	 * Traverse the path from the root to the leaf entity to  in bfq_get_next_queue()
1524 	for (; sd ; sd = entity->my_sched_data) {  in bfq_get_next_queue()
1526 		 * WARNING. We are about to set the in-service entity  in bfq_get_next_queue()
1531 		 * activation or deactivation of an entity. In this  in bfq_get_next_queue()
1534 		 * probability, yield a different entity than that  in bfq_get_next_queue()
1536 		 * happens in case there was no CLASS_IDLE entity to  in bfq_get_next_queue()
1539 		 * such entity.  in bfq_get_next_queue()
1542 		 * such entity in CLASS_IDLE is postponed until the  in bfq_get_next_queue()
1543 		 * service of the sd->next_in_service entity  in bfq_get_next_queue()
1549 		/* Make next_in_service entity become in_service_entity */  in bfq_get_next_queue()
1550 		entity = sd->next_in_service;  in bfq_get_next_queue()
1551 		sd->in_service_entity = entity;  in bfq_get_next_queue()
1554 		 * If entity is no longer a candidate for next  in bfq_get_next_queue()
1561 		if (bfq_no_longer_next_in_service(entity))  in bfq_get_next_queue()
1562 			bfq_active_extract(bfq_entity_service_tree(entity),  in bfq_get_next_queue()
1563 					   entity);  in bfq_get_next_queue()
1566 		 * Even if entity is not to be extracted according to  in bfq_get_next_queue()
1567 		 * the above check, a descendant entity may get  in bfq_get_next_queue()
1571 		 * entity, and thus possibly back to this level.  in bfq_get_next_queue()
1576 		 * the correct next-to-serve candidate entity for each  in bfq_get_next_queue()
1577 		 * level, we need first to find the leaf entity to set  in bfq_get_next_queue()
1579 		 * the next-to-serve leaf entity, we can discover  in bfq_get_next_queue()
1580 		 * whether the parent entity of the leaf entity  in bfq_get_next_queue()
1585 	bfqq = bfq_entity_to_bfqq(entity);  in bfq_get_next_queue()
1589 	 * path from the leaf entity just set in service to the root.  in bfq_get_next_queue()
1591 	for_each_entity(entity) {  in bfq_get_next_queue()
1592 		struct bfq_sched_data *sd = entity->sched_data;  in bfq_get_next_queue()
1605 	struct bfq_entity *in_serv_entity = &in_serv_bfqq->entity;  in __bfq_bfqd_reset_in_service()
1606 	struct bfq_entity *entity = in_serv_entity;  in __bfq_bfqd_reset_in_service()  local
1616 	 * path from entity to the root.  in __bfq_bfqd_reset_in_service()
1618 	for_each_entity(entity)  in __bfq_bfqd_reset_in_service()
1619 		entity->sched_data->in_service_entity = NULL;  in __bfq_bfqd_reset_in_service()
1645 	struct bfq_entity *entity = &bfqq->entity;  in bfq_deactivate_bfqq()  local
1647 	bfq_deactivate_entity(entity, ins_into_idle_tree, expiration);  in bfq_deactivate_bfqq()
1652 	struct bfq_entity *entity = &bfqq->entity;  in bfq_activate_bfqq()  local
1654 	bfq_activate_requeue_entity(entity, bfq_bfqq_non_blocking_wait_rq(bfqq),  in bfq_activate_bfqq()
1662 	struct bfq_entity *entity = &bfqq->entity;  in bfq_requeue_bfqq()  local
1664 	bfq_activate_requeue_entity(entity, false,  in bfq_requeue_bfqq()