Lines Matching refs:entity
30 static unsigned int bfq_class_idx(struct bfq_entity *entity)
32 struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);
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
87 * just-modified entity has the same priority as
90 * condition holds, then the new entity becomes the new
104 * entity, then compare timestamps to decide whether
147 * become the next_in_service entity for its parent entity.
161 * is not the root group. We must not touch the root entity
162 * as it must never become an in-service entity.
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)
198 if (bfq_entity_to_bfqq(entity))
201 bfqg = container_of(entity, struct bfq_group, entity);
206 * not account for the in-service entity in case the latter is
221 static void bfq_inc_active_entities(struct bfq_entity *entity)
223 struct bfq_sched_data *sd = entity->sched_data;
230 static void bfq_dec_active_entities(struct bfq_entity *entity)
232 struct bfq_sched_data *sd = entity->sched_data;
246 static bool bfq_no_longer_next_in_service(struct bfq_entity *entity)
251 static void bfq_inc_active_entities(struct bfq_entity *entity)
255 static void bfq_dec_active_entities(struct bfq_entity *entity)
270 struct bfq_queue *bfq_entity_to_bfqq(struct bfq_entity *entity)
274 if (!entity->my_sched_data)
275 bfqq = container_of(entity, struct bfq_queue, entity);
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)
298 struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);
300 entity->finish = entity->start +
301 bfq_delta(service, entity->weight);
306 service, entity->weight);
309 entity->start, entity->finish,
310 bfq_delta(service, entity->weight));
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;
328 entity = rb_entry(node, struct bfq_entity, rb_node);
330 return entity;
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)
340 entity->tree = NULL;
341 rb_erase(&entity->rb_node, root);
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)
352 struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);
355 if (entity == st->first_idle) {
356 next = rb_next(&entity->rb_node);
360 if (entity == st->last_idle) {
361 next = rb_prev(&entity->rb_node);
365 bfq_extract(&st->idle, entity);
374 * @entity: entity to insert.
379 static void bfq_insert(struct rb_root *root, struct bfq_entity *entity)
389 if (bfq_gt(entry->finish, entity->finish))
395 rb_link_node(&entity->rb_node, parent, node);
396 rb_insert_color(&entity->rb_node, root);
398 entity->tree = root;
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)
417 if (bfq_gt(entity->min_start, child->min_start))
418 entity->min_start = child->min_start;
432 struct bfq_entity *entity = rb_entry(node, struct bfq_entity, rb_node);
434 entity->min_start = entity->start;
435 bfq_update_min(entity, node->rb_right);
436 bfq_update_min(entity, node->rb_left);
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)
483 struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);
484 struct rb_node *node = &entity->rb_node;
486 bfq_insert(&st->active, entity);
498 bfq_inc_active_entities(entity);
524 static void bfq_get_entity(struct bfq_entity *entity)
526 struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);
566 * bfq_active_extract - remove an entity from the active tree.
568 * @entity: the entity being removed.
571 struct bfq_entity *entity)
573 struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);
576 node = bfq_find_deepest(&entity->rb_node);
577 bfq_extract(&st->active, entity);
584 bfq_dec_active_entities(entity);
588 * bfq_idle_insert - insert an entity into the idle tree.
590 * @entity: the entity to insert.
593 struct bfq_entity *entity)
595 struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);
599 if (!first_idle || bfq_gt(first_idle->finish, entity->finish))
600 st->first_idle = entity;
601 if (!last_idle || bfq_gt(entity->finish, last_idle->finish))
602 st->last_idle = entity;
604 bfq_insert(&st->idle, entity);
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,
629 struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);
631 entity->on_st_or_in_serv = false;
632 st->wsum -= entity->weight;
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)
644 bfq_idle_extract(st, entity);
645 bfq_forget_entity(st, entity,
646 entity == entity->sched_data->in_service_entity);
674 struct bfq_service_tree *bfq_entity_service_tree(struct bfq_entity *entity)
676 struct bfq_sched_data *sched_data = entity->sched_data;
677 unsigned int idx = bfq_class_idx(entity);
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,
707 if (entity->prio_changed) {
708 struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);
713 old_st->wsum -= entity->weight;
715 if (entity->new_weight != entity->orig_weight) {
716 if (entity->new_weight < BFQ_MIN_WEIGHT ||
717 entity->new_weight > BFQ_MAX_WEIGHT) {
719 entity->new_weight);
720 if (entity->new_weight < BFQ_MIN_WEIGHT)
721 entity->new_weight = BFQ_MIN_WEIGHT;
723 entity->new_weight = BFQ_MAX_WEIGHT;
725 entity->orig_weight = entity->new_weight;
728 bfq_weight_to_ioprio(entity->orig_weight);
739 entity->prio_changed = 0;
746 * when entity->finish <= old_st->vtime).
748 new_st = bfq_entity_service_tree(entity);
750 prev_weight = entity->weight;
751 new_weight = entity->orig_weight *
754 * If the weight of the entity changes, and the entity is a
755 * queue, remove the entity from its old weight counter (if
756 * there is a counter associated with the entity).
760 entity->weight = new_weight;
762 * Add the entity, if it is not a weight-raised queue,
768 new_st->wsum += entity->weight;
771 entity->start = new_st->vtime;
789 struct bfq_entity *entity = &bfqq->entity;
799 for_each_entity(entity) {
800 st = bfq_entity_service_tree(entity);
802 entity->service += served;
840 struct bfq_entity *entity = &bfqq->entity;
845 int tot_serv_to_charge = max(serv_to_charge_for_time, entity->service);
848 if (tot_serv_to_charge > entity->budget)
849 entity->budget = tot_serv_to_charge;
852 max_t(int, 0, tot_serv_to_charge - entity->service));
855 static void bfq_update_fin_time_enqueue(struct bfq_entity *entity,
859 struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);
862 * When this function is invoked, entity is not in any service
866 st = __bfq_entity_update_weight_prio(st, entity, true);
867 bfq_calc_finish(entity, entity->budget);
889 * entity (only a queue can happen to have the backshifted
902 if (backshifted && bfq_gt(st->vtime, entity->finish)) {
903 unsigned long delta = st->vtime - entity->finish;
908 entity->start += delta;
909 entity->finish += delta;
912 bfq_active_insert(st, entity);
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,
930 struct bfq_service_tree *st = bfq_entity_service_tree(entity);
935 if (non_blocking_wait_rq && bfq_gt(st->vtime, entity->finish)) {
937 min_vstart = entity->finish;
941 if (entity->tree == &st->idle) {
946 bfq_idle_extract(st, entity);
947 entity->start = bfq_gt(min_vstart, entity->finish) ?
948 min_vstart : entity->finish;
951 * The finish time of the entity may be invalid, and
955 entity->start = min_vstart;
956 st->wsum += entity->weight;
958 * entity is about to be inserted into a service tree,
960 * sure entity does not disappear until it is no
963 bfq_get_entity(entity);
965 entity->on_st_or_in_serv = true;
968 bfq_update_fin_time_enqueue(entity, st, backshifted);
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)
988 struct bfq_sched_data *sd = entity->sched_data;
989 struct bfq_service_tree *st = bfq_entity_service_tree(entity);
991 if (entity == sd->in_service_entity) {
993 * We are requeueing the current in-service entity,
996 * - entity represents the in-service queue, and the
999 * - entity represents a group, and its budget has
1002 * reason; the timestamps of the entity need then to
1003 * be updated, and the entity needs to be enqueued
1007 * the entity must be moved forward to account for the
1008 * service that the entity has received while in
1012 * the entity.
1014 bfq_calc_finish(entity, entity->service);
1015 entity->start = entity->finish;
1017 * In addition, if the entity had more than one child
1020 * the entity in the active tree may need to be
1022 * time of the entity, and we will update its finish
1026 * entity here, 2) update the finish time and requeue
1027 * the entity according to the new timestamps below.
1029 if (entity->tree)
1030 bfq_active_extract(st, entity);
1031 } else { /* The entity is already active, and not in service */
1034 * next_in_service entity below this entity has
1036 * this entity to change, which, finally implies that
1037 * the finish time of this entity must be
1040 * entity to change. We handle this change by: 1)
1041 * dequeueing the entity here, 2) updating the finish
1042 * time and requeueing the entity according to the new
1044 * non-extracted-entity sub-case above.
1046 bfq_active_extract(st, entity);
1049 bfq_update_fin_time_enqueue(entity, st, false);
1052 static void __bfq_activate_requeue_entity(struct bfq_entity *entity,
1055 struct bfq_service_tree *st = bfq_entity_service_tree(entity);
1057 if (entity->sched_data->in_service_entity == entity ||
1058 entity->tree == &st->active)
1063 __bfq_requeue_entity(entity);
1069 __bfq_activate_entity(entity, non_blocking_wait_rq);
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,
1090 for_each_entity(entity) {
1091 __bfq_activate_requeue_entity(entity, non_blocking_wait_rq);
1092 if (!bfq_update_next_in_service(entity->sched_data, 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)
1110 struct bfq_sched_data *sd = entity->sched_data;
1114 if (!entity->on_st_or_in_serv) /*
1115 * entity never activated, or
1121 * If we get here, then entity is active, which implies that
1123 * represented by entity. Therefore, the field
1124 * entity->sched_data has been set, and we can safely use it.
1126 st = bfq_entity_service_tree(entity);
1127 is_in_service = entity == sd->in_service_entity;
1129 bfq_calc_finish(entity, entity->service);
1135 * Non in-service entity: nobody will take care of
1139 entity->service = 0;
1141 if (entity->tree == &st->active)
1142 bfq_active_extract(st, entity);
1143 else if (!is_in_service && entity->tree == &st->idle)
1144 bfq_idle_extract(st, entity);
1146 if (!ins_into_idle_tree || !bfq_gt(entity->finish, st->vtime))
1147 bfq_forget_entity(st, entity, is_in_service);
1149 bfq_idle_insert(st, 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,
1168 for_each_entity_safe(entity, parent) {
1169 sd = entity->sched_data;
1171 if (!__bfq_deactivate_entity(entity, ins_into_idle_tree)) {
1173 * entity is not in any tree any more, so
1182 if (sd->next_in_service == entity)
1184 * entity was the next_in_service entity,
1185 * then, since entity has just been
1192 * The parent entity is still active, because
1201 * although the parent entity is evidently
1202 * active. This happens if 1) the entity
1204 * active entity in the parent entity, and 2)
1236 entity = parent;
1237 for_each_entity(entity) {
1239 * Invoke __bfq_requeue_entity on entity, even if
1244 __bfq_requeue_entity(entity);
1246 sd = entity->sched_data;
1247 if (!bfq_update_next_in_service(sd, entity, expiration) &&
1251 * any change in entity->parent->sd, and no
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;
1359 * least one entity is eligible.
1364 * If there is no in-service entity for the sched_data this
1366 * up to the value that guarantees that at least one entity is
1367 * eligible. If, instead, there is an in-service entity, then
1369 * eligible entity, namely the in-service one (even if the
1370 * entity is not on st, because it was extracted when set in
1376 entity = bfq_first_active_entity(st, new_vtime);
1378 return 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;
1400 * bandwidth to this class (and if there is some active entity
1414 * Find the next entity to serve for the highest-priority
1433 entity = __bfq_lookup_next_entity(st + class_idx,
1437 if (entity)
1441 return entity;
1456 struct bfq_entity *entity = NULL;
1464 * Traverse the path from the root to the leaf entity to
1469 for (; sd ; sd = entity->my_sched_data) {
1471 * WARNING. We are about to set the in-service entity
1476 * activation or deactivation of an entity. In this
1479 * probability, yield a different entity than that
1481 * happens in case there was no CLASS_IDLE entity to
1484 * such entity.
1487 * such entity in CLASS_IDLE is postponed until the
1488 * service of the sd->next_in_service entity
1494 /* Make next_in_service entity become in_service_entity */
1495 entity = sd->next_in_service;
1496 sd->in_service_entity = entity;
1499 * If entity is no longer a candidate for next
1506 if (bfq_no_longer_next_in_service(entity))
1507 bfq_active_extract(bfq_entity_service_tree(entity),
1508 entity);
1511 * Even if entity is not to be extracted according to
1512 * the above check, a descendant entity may get
1516 * entity, and thus possibly back to this level.
1521 * the correct next-to-serve candidate entity for each
1522 * level, we need first to find the leaf entity to set
1524 * the next-to-serve leaf entity, we can discover
1525 * whether the parent entity of the leaf entity
1530 bfqq = bfq_entity_to_bfqq(entity);
1534 * path from the leaf entity just set in service to the root.
1536 for_each_entity(entity) {
1537 struct bfq_sched_data *sd = entity->sched_data;
1550 struct bfq_entity *in_serv_entity = &in_serv_bfqq->entity;
1551 struct bfq_entity *entity = in_serv_entity;
1561 * path from entity to the root.
1563 for_each_entity(entity)
1564 entity->sched_data->in_service_entity = NULL;
1590 struct bfq_entity *entity = &bfqq->entity;
1592 bfq_deactivate_entity(entity, ins_into_idle_tree, expiration);
1597 struct bfq_entity *entity = &bfqq->entity;
1599 bfq_activate_requeue_entity(entity, bfq_bfqq_non_blocking_wait_rq(bfqq),
1607 struct bfq_entity *entity = &bfqq->entity;
1609 bfq_activate_requeue_entity(entity, false,
1616 struct bfq_entity *entity = &bfqq->entity;
1618 if (!entity->in_groups_with_pending_reqs) {
1619 entity->in_groups_with_pending_reqs = true;
1629 struct bfq_entity *entity = &bfqq->entity;
1631 if (entity->in_groups_with_pending_reqs) {
1632 entity->in_groups_with_pending_reqs = false;