Lines Matching defs: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
150 struct bfq_entity *group_entity = bfqq->entity.parent;
153 group_entity = &bfqq->bfqd->root_group->entity;
155 return container_of(group_entity, struct bfq_group, entity);
160 * become the next_in_service entity for its parent entity.
174 * is not the root group. We must not touch the root entity
175 * as it must never become an in-service entity.
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)
211 if (bfq_entity_to_bfqq(entity))
214 bfqg = container_of(entity, struct bfq_group, entity);
219 * not account for the in-service entity in case the latter is
246 static bool bfq_no_longer_next_in_service(struct bfq_entity *entity)
262 struct bfq_queue *bfq_entity_to_bfqq(struct bfq_entity *entity)
266 if (!entity->my_sched_data)
267 bfqq = container_of(entity, struct bfq_queue, entity);
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)
290 struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);
292 entity->finish = entity->start +
293 bfq_delta(service, entity->weight);
298 service, entity->weight);
301 entity->start, entity->finish,
302 bfq_delta(service, entity->weight));
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;
320 entity = rb_entry(node, struct bfq_entity, rb_node);
322 return entity;
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)
332 entity->tree = NULL;
333 rb_erase(&entity->rb_node, root);
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)
344 struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);
347 if (entity == st->first_idle) {
348 next = rb_next(&entity->rb_node);
352 if (entity == st->last_idle) {
353 next = rb_prev(&entity->rb_node);
357 bfq_extract(&st->idle, entity);
366 * @entity: entity to insert.
371 static void bfq_insert(struct rb_root *root, struct bfq_entity *entity)
381 if (bfq_gt(entry->finish, entity->finish))
387 rb_link_node(&entity->rb_node, parent, node);
388 rb_insert_color(&entity->rb_node, root);
390 entity->tree = root;
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)
409 if (bfq_gt(entity->min_start, child->min_start))
410 entity->min_start = child->min_start;
424 struct bfq_entity *entity = rb_entry(node, struct bfq_entity, rb_node);
426 entity->min_start = entity->start;
427 bfq_update_min(entity, node->rb_right);
428 bfq_update_min(entity, node->rb_left);
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)
475 struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);
476 struct rb_node *node = &entity->rb_node;
483 bfq_insert(&st->active, entity);
493 sd = entity->sched_data;
528 static void bfq_get_entity(struct bfq_entity *entity)
530 struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);
570 * bfq_active_extract - remove an entity from the active tree.
572 * @entity: the entity being removed.
575 struct bfq_entity *entity)
577 struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);
585 node = bfq_find_deepest(&entity->rb_node);
586 bfq_extract(&st->active, entity);
592 sd = entity->sched_data;
605 * bfq_idle_insert - insert an entity into the idle tree.
607 * @entity: the entity to insert.
610 struct bfq_entity *entity)
612 struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);
616 if (!first_idle || bfq_gt(first_idle->finish, entity->finish))
617 st->first_idle = entity;
618 if (!last_idle || bfq_gt(entity->finish, last_idle->finish))
619 st->last_idle = entity;
621 bfq_insert(&st->idle, entity);
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,
646 struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);
648 entity->on_st_or_in_serv = false;
649 st->wsum -= entity->weight;
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)
661 bfq_idle_extract(st, entity);
662 bfq_forget_entity(st, entity,
663 entity == entity->sched_data->in_service_entity);
691 struct bfq_service_tree *bfq_entity_service_tree(struct bfq_entity *entity)
693 struct bfq_sched_data *sched_data = entity->sched_data;
694 unsigned int idx = bfq_class_idx(entity);
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,
724 if (entity->prio_changed) {
725 struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);
738 sd = entity->my_sched_data;
746 old_st->wsum -= entity->weight;
748 if (entity->new_weight != entity->orig_weight) {
749 if (entity->new_weight < BFQ_MIN_WEIGHT ||
750 entity->new_weight > BFQ_MAX_WEIGHT) {
752 entity->new_weight);
753 if (entity->new_weight < BFQ_MIN_WEIGHT)
754 entity->new_weight = BFQ_MIN_WEIGHT;
756 entity->new_weight = BFQ_MAX_WEIGHT;
758 entity->orig_weight = entity->new_weight;
761 bfq_weight_to_ioprio(entity->orig_weight);
772 entity->prio_changed = 0;
779 * when entity->finish <= old_st->vtime).
781 new_st = bfq_entity_service_tree(entity);
783 prev_weight = entity->weight;
784 new_weight = entity->orig_weight *
787 * If the weight of the entity changes, and the entity is a
788 * queue, remove the entity from its old weight counter (if
789 * there is a counter associated with the entity).
795 entity->weight = new_weight;
797 * Add the entity, if it is not a weight-raised queue,
805 new_st->wsum += entity->weight;
808 entity->start = new_st->vtime;
826 struct bfq_entity *entity = &bfqq->entity;
836 for_each_entity(entity) {
837 st = bfq_entity_service_tree(entity);
839 entity->service += served;
877 struct bfq_entity *entity = &bfqq->entity;
882 int tot_serv_to_charge = max(serv_to_charge_for_time, entity->service);
885 if (tot_serv_to_charge > entity->budget)
886 entity->budget = tot_serv_to_charge;
889 max_t(int, 0, tot_serv_to_charge - entity->service));
892 static void bfq_update_fin_time_enqueue(struct bfq_entity *entity,
896 struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);
899 * When this function is invoked, entity is not in any service
903 st = __bfq_entity_update_weight_prio(st, entity, true);
904 bfq_calc_finish(entity, entity->budget);
926 * entity (only a queue can happen to have the backshifted
939 if (backshifted && bfq_gt(st->vtime, entity->finish)) {
940 unsigned long delta = st->vtime - entity->finish;
945 entity->start += delta;
946 entity->finish += delta;
949 bfq_active_insert(st, entity);
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,
967 struct bfq_service_tree *st = bfq_entity_service_tree(entity);
972 if (non_blocking_wait_rq && bfq_gt(st->vtime, entity->finish)) {
974 min_vstart = entity->finish;
978 if (entity->tree == &st->idle) {
983 bfq_idle_extract(st, entity);
984 entity->start = bfq_gt(min_vstart, entity->finish) ?
985 min_vstart : entity->finish;
988 * The finish time of the entity may be invalid, and
992 entity->start = min_vstart;
993 st->wsum += entity->weight;
995 * entity is about to be inserted into a service tree,
997 * sure entity does not disappear until it is no
1000 bfq_get_entity(entity);
1002 entity->on_st_or_in_serv = true;
1006 if (!bfq_entity_to_bfqq(entity)) { /* bfq_group */
1008 container_of(entity, struct bfq_group, entity);
1011 if (!entity->in_groups_with_pending_reqs) {
1012 entity->in_groups_with_pending_reqs = true;
1018 bfq_update_fin_time_enqueue(entity, st, backshifted);
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)
1038 struct bfq_sched_data *sd = entity->sched_data;
1039 struct bfq_service_tree *st = bfq_entity_service_tree(entity);
1041 if (entity == sd->in_service_entity) {
1043 * We are requeueing the current in-service entity,
1046 * - entity represents the in-service queue, and the
1049 * - entity represents a group, and its budget has
1052 * reason; the timestamps of the entity need then to
1053 * be updated, and the entity needs to be enqueued
1057 * the entity must be moved forward to account for the
1058 * service that the entity has received while in
1062 * the entity.
1064 bfq_calc_finish(entity, entity->service);
1065 entity->start = entity->finish;
1067 * In addition, if the entity had more than one child
1070 * the entity in the active tree may need to be
1072 * time of the entity, and we will update its finish
1076 * entity here, 2) update the finish time and requeue
1077 * the entity according to the new timestamps below.
1079 if (entity->tree)
1080 bfq_active_extract(st, entity);
1081 } else { /* The entity is already active, and not in service */
1084 * next_in_service entity below this entity has
1086 * this entity to change, which, finally implies that
1087 * the finish time of this entity must be
1090 * entity to change. We handle this change by: 1)
1091 * dequeueing the entity here, 2) updating the finish
1092 * time and requeueing the entity according to the new
1094 * non-extracted-entity sub-case above.
1096 bfq_active_extract(st, entity);
1099 bfq_update_fin_time_enqueue(entity, st, false);
1102 static void __bfq_activate_requeue_entity(struct bfq_entity *entity,
1106 struct bfq_service_tree *st = bfq_entity_service_tree(entity);
1108 if (sd->in_service_entity == entity || entity->tree == &st->active)
1113 __bfq_requeue_entity(entity);
1119 __bfq_activate_entity(entity, non_blocking_wait_rq);
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,
1142 for_each_entity(entity) {
1143 sd = entity->sched_data;
1144 __bfq_activate_requeue_entity(entity, sd, non_blocking_wait_rq);
1146 if (!bfq_update_next_in_service(sd, entity, expiration) &&
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)
1164 struct bfq_sched_data *sd = entity->sched_data;
1168 if (!entity->on_st_or_in_serv) /*
1169 * entity never activated, or
1175 * If we get here, then entity is active, which implies that
1177 * represented by entity. Therefore, the field
1178 * entity->sched_data has been set, and we can safely use it.
1180 st = bfq_entity_service_tree(entity);
1181 is_in_service = entity == sd->in_service_entity;
1183 bfq_calc_finish(entity, entity->service);
1189 * Non in-service entity: nobody will take care of
1193 entity->service = 0;
1195 if (entity->tree == &st->active)
1196 bfq_active_extract(st, entity);
1197 else if (!is_in_service && entity->tree == &st->idle)
1198 bfq_idle_extract(st, entity);
1200 if (!ins_into_idle_tree || !bfq_gt(entity->finish, st->vtime))
1201 bfq_forget_entity(st, entity, is_in_service);
1203 bfq_idle_insert(st, 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,
1222 for_each_entity_safe(entity, parent) {
1223 sd = entity->sched_data;
1225 if (!__bfq_deactivate_entity(entity, ins_into_idle_tree)) {
1227 * entity is not in any tree any more, so
1236 if (sd->next_in_service == entity)
1238 * entity was the next_in_service entity,
1239 * then, since entity has just been
1246 * The parent entity is still active, because
1255 * although the parent entity is evidently
1256 * active. This happens if 1) the entity
1258 * active entity in the parent entity, and 2)
1290 entity = parent;
1291 for_each_entity(entity) {
1293 * Invoke __bfq_requeue_entity on entity, even if
1298 __bfq_requeue_entity(entity);
1300 sd = entity->sched_data;
1301 if (!bfq_update_next_in_service(sd, entity, expiration) &&
1305 * any change in entity->parent->sd, and no
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;
1411 * least one entity is eligible.
1416 * If there is no in-service entity for the sched_data this
1418 * up to the value that guarantees that at least one entity is
1419 * eligible. If, instead, there is an in-service entity, then
1421 * eligible entity, namely the in-service one (even if the
1422 * entity is not on st, because it was extracted when set in
1428 entity = bfq_first_active_entity(st, new_vtime);
1430 return 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;
1452 * bandwidth to this class (and if there is some active entity
1466 * Find the next entity to serve for the highest-priority
1485 entity = __bfq_lookup_next_entity(st + class_idx,
1489 if (entity)
1493 if (!entity)
1496 return entity;
1511 struct bfq_entity *entity = NULL;
1519 * Traverse the path from the root to the leaf entity to
1524 for (; sd ; sd = entity->my_sched_data) {
1526 * WARNING. We are about to set the in-service entity
1531 * activation or deactivation of an entity. In this
1534 * probability, yield a different entity than that
1536 * happens in case there was no CLASS_IDLE entity to
1539 * such entity.
1542 * such entity in CLASS_IDLE is postponed until the
1543 * service of the sd->next_in_service entity
1549 /* Make next_in_service entity become in_service_entity */
1550 entity = sd->next_in_service;
1551 sd->in_service_entity = entity;
1554 * If entity is no longer a candidate for next
1561 if (bfq_no_longer_next_in_service(entity))
1562 bfq_active_extract(bfq_entity_service_tree(entity),
1563 entity);
1566 * Even if entity is not to be extracted according to
1567 * the above check, a descendant entity may get
1571 * entity, and thus possibly back to this level.
1576 * the correct next-to-serve candidate entity for each
1577 * level, we need first to find the leaf entity to set
1579 * the next-to-serve leaf entity, we can discover
1580 * whether the parent entity of the leaf entity
1585 bfqq = bfq_entity_to_bfqq(entity);
1589 * path from the leaf entity just set in service to the root.
1591 for_each_entity(entity) {
1592 struct bfq_sched_data *sd = entity->sched_data;
1605 struct bfq_entity *in_serv_entity = &in_serv_bfqq->entity;
1606 struct bfq_entity *entity = in_serv_entity;
1616 * path from entity to the root.
1618 for_each_entity(entity)
1619 entity->sched_data->in_service_entity = NULL;
1645 struct bfq_entity *entity = &bfqq->entity;
1647 bfq_deactivate_entity(entity, ins_into_idle_tree, expiration);
1652 struct bfq_entity *entity = &bfqq->entity;
1654 bfq_activate_requeue_entity(entity, bfq_bfqq_non_blocking_wait_rq(bfqq),
1662 struct bfq_entity *entity = &bfqq->entity;
1664 bfq_activate_requeue_entity(entity, false,