^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1) // SPDX-License-Identifier: GPL-2.0-or-later
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 2) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 3) * Hierarchical Budget Worst-case Fair Weighted Fair Queueing
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 4) * (B-WF2Q+): hierarchical scheduling algorithm by which the BFQ I/O
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 5) * scheduler schedules generic entities. The latter can represent
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 6) * either single bfq queues (associated with processes) or groups of
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 7) * bfq queues (associated with cgroups).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 8) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 9) #include "bfq-iosched.h"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 10)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 11) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 12) * bfq_gt - compare two timestamps.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 13) * @a: first ts.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 14) * @b: second ts.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 15) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 16) * Return @a > @b, dealing with wrapping correctly.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 17) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 18) static int bfq_gt(u64 a, u64 b)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 19) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 20) return (s64)(a - b) > 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 21) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 22)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 23) static struct bfq_entity *bfq_root_active_entity(struct rb_root *tree)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 24) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 25) struct rb_node *node = tree->rb_node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 26)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 27) return rb_entry(node, struct bfq_entity, rb_node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 28) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 29)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 30) static unsigned int bfq_class_idx(struct bfq_entity *entity)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 31) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 32) struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 33)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 34) return bfqq ? bfqq->ioprio_class - 1 :
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 35) BFQ_DEFAULT_GRP_CLASS - 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 36) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 37)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 38) unsigned int bfq_tot_busy_queues(struct bfq_data *bfqd)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 39) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 40) return bfqd->busy_queues[0] + bfqd->busy_queues[1] +
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 41) bfqd->busy_queues[2];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 42) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 43)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 44) static struct bfq_entity *bfq_lookup_next_entity(struct bfq_sched_data *sd,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 45) bool expiration);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 46)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 47) static bool bfq_update_parent_budget(struct bfq_entity *next_in_service);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 48)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 49) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 50) * bfq_update_next_in_service - update sd->next_in_service
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 51) * @sd: sched_data for which to perform the update.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 52) * @new_entity: if not NULL, pointer to the entity whose activation,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 53) * requeueing or repositioning triggered the invocation of
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 54) * this function.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 55) * @expiration: id true, this function is being invoked after the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 56) * expiration of the in-service entity
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 57) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 58) * This function is called to update sd->next_in_service, which, in
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 59) * its turn, may change as a consequence of the insertion or
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 60) * extraction of an entity into/from one of the active trees of
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 61) * sd. These insertions/extractions occur as a consequence of
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 62) * activations/deactivations of entities, with some activations being
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 63) * 'true' activations, and other activations being requeueings (i.e.,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 64) * implementing the second, requeueing phase of the mechanism used to
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 65) * reposition an entity in its active tree; see comments on
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 66) * __bfq_activate_entity and __bfq_requeue_entity for details). In
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 67) * both the last two activation sub-cases, new_entity points to the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 68) * just activated or requeued entity.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 69) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 70) * Returns true if sd->next_in_service changes in such a way that
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 71) * entity->parent may become the next_in_service for its parent
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 72) * entity.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 73) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 74) static bool bfq_update_next_in_service(struct bfq_sched_data *sd,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 75) struct bfq_entity *new_entity,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 76) bool expiration)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 77) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 78) struct bfq_entity *next_in_service = sd->next_in_service;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 79) bool parent_sched_may_change = false;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 80) bool change_without_lookup = false;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 81)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 82) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 83) * If this update is triggered by the activation, requeueing
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 84) * or repositioning of an entity that does not coincide with
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 85) * sd->next_in_service, then a full lookup in the active tree
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 86) * can be avoided. In fact, it is enough to check whether the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 87) * just-modified entity has the same priority as
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 88) * sd->next_in_service, is eligible and has a lower virtual
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 89) * finish time than sd->next_in_service. If this compound
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 90) * condition holds, then the new entity becomes the new
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 91) * next_in_service. Otherwise no change is needed.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 92) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 93) if (new_entity && new_entity != sd->next_in_service) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 94) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 95) * Flag used to decide whether to replace
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 96) * sd->next_in_service with new_entity. Tentatively
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 97) * set to true, and left as true if
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 98) * sd->next_in_service is NULL.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 99) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 100) change_without_lookup = true;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 101)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 102) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 103) * If there is already a next_in_service candidate
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 104) * entity, then compare timestamps to decide whether
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 105) * to replace sd->service_tree with new_entity.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 106) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 107) if (next_in_service) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 108) unsigned int new_entity_class_idx =
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 109) bfq_class_idx(new_entity);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 110) struct bfq_service_tree *st =
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 111) sd->service_tree + new_entity_class_idx;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 112)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 113) change_without_lookup =
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 114) (new_entity_class_idx ==
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 115) bfq_class_idx(next_in_service)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 116) &&
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 117) !bfq_gt(new_entity->start, st->vtime)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 118) &&
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 119) bfq_gt(next_in_service->finish,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 120) new_entity->finish));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 121) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 122)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 123) if (change_without_lookup)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 124) next_in_service = new_entity;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 125) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 126)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 127) if (!change_without_lookup) /* lookup needed */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 128) next_in_service = bfq_lookup_next_entity(sd, expiration);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 129)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 130) if (next_in_service) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 131) bool new_budget_triggers_change =
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 132) bfq_update_parent_budget(next_in_service);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 133)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 134) parent_sched_may_change = !sd->next_in_service ||
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 135) new_budget_triggers_change;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 136) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 137)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 138) sd->next_in_service = next_in_service;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 139)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 140) if (!next_in_service)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 141) return parent_sched_may_change;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 142)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 143) return parent_sched_may_change;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 144) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 145)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 146) #ifdef CONFIG_BFQ_GROUP_IOSCHED
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 147)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 148) struct bfq_group *bfq_bfqq_to_bfqg(struct bfq_queue *bfqq)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 149) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 150) struct bfq_entity *group_entity = bfqq->entity.parent;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 151)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 152) if (!group_entity)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 153) group_entity = &bfqq->bfqd->root_group->entity;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 154)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 155) return container_of(group_entity, struct bfq_group, entity);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 156) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 157)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 158) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 159) * Returns true if this budget changes may let next_in_service->parent
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 160) * become the next_in_service entity for its parent entity.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 161) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 162) static bool bfq_update_parent_budget(struct bfq_entity *next_in_service)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 163) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 164) struct bfq_entity *bfqg_entity;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 165) struct bfq_group *bfqg;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 166) struct bfq_sched_data *group_sd;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 167) bool ret = false;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 168)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 169) group_sd = next_in_service->sched_data;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 170)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 171) bfqg = container_of(group_sd, struct bfq_group, sched_data);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 172) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 173) * bfq_group's my_entity field is not NULL only if the group
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 174) * is not the root group. We must not touch the root entity
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 175) * as it must never become an in-service entity.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 176) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 177) bfqg_entity = bfqg->my_entity;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 178) if (bfqg_entity) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 179) if (bfqg_entity->budget > next_in_service->budget)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 180) ret = true;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 181) bfqg_entity->budget = next_in_service->budget;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 182) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 183)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 184) return ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 185) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 186)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 187) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 188) * This function tells whether entity stops being a candidate for next
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 189) * service, according to the restrictive definition of the field
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 190) * next_in_service. In particular, this function is invoked for an
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 191) * entity that is about to be set in service.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 192) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 193) * If entity is a queue, then the entity is no longer a candidate for
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 194) * next service according to the that definition, because entity is
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 195) * about to become the in-service queue. This function then returns
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 196) * true if entity is a queue.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 197) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 198) * In contrast, entity could still be a candidate for next service if
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 199) * it is not a queue, and has more than one active child. In fact,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 200) * even if one of its children is about to be set in service, other
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 201) * active children may still be the next to serve, for the parent
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 202) * entity, even according to the above definition. As a consequence, a
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 203) * non-queue entity is not a candidate for next-service only if it has
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 204) * only one active child. And only if this condition holds, then this
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 205) * function returns true for a non-queue entity.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 206) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 207) static bool bfq_no_longer_next_in_service(struct bfq_entity *entity)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 208) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 209) struct bfq_group *bfqg;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 210)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 211) if (bfq_entity_to_bfqq(entity))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 212) return true;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 213)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 214) bfqg = container_of(entity, struct bfq_group, entity);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 215)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 216) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 217) * The field active_entities does not always contain the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 218) * actual number of active children entities: it happens to
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 219) * not account for the in-service entity in case the latter is
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 220) * removed from its active tree (which may get done after
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 221) * invoking the function bfq_no_longer_next_in_service in
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 222) * bfq_get_next_queue). Fortunately, here, i.e., while
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 223) * bfq_no_longer_next_in_service is not yet completed in
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 224) * bfq_get_next_queue, bfq_active_extract has not yet been
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 225) * invoked, and thus active_entities still coincides with the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 226) * actual number of active entities.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 227) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 228) if (bfqg->active_entities == 1)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 229) return true;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 230)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 231) return false;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 232) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 233)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 234) #else /* CONFIG_BFQ_GROUP_IOSCHED */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 235)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 236) struct bfq_group *bfq_bfqq_to_bfqg(struct bfq_queue *bfqq)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 237) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 238) return bfqq->bfqd->root_group;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 239) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 240)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 241) static bool bfq_update_parent_budget(struct bfq_entity *next_in_service)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 242) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 243) return false;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 244) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 245)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 246) static bool bfq_no_longer_next_in_service(struct bfq_entity *entity)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 247) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 248) return true;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 249) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 250)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 251) #endif /* CONFIG_BFQ_GROUP_IOSCHED */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 252)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 253) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 254) * Shift for timestamp calculations. This actually limits the maximum
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 255) * service allowed in one timestamp delta (small shift values increase it),
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 256) * the maximum total weight that can be used for the queues in the system
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 257) * (big shift values increase it), and the period of virtual time
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 258) * wraparounds.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 259) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 260) #define WFQ_SERVICE_SHIFT 22
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 261)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 262) struct bfq_queue *bfq_entity_to_bfqq(struct bfq_entity *entity)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 263) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 264) struct bfq_queue *bfqq = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 265)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 266) if (!entity->my_sched_data)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 267) bfqq = container_of(entity, struct bfq_queue, entity);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 268)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 269) return bfqq;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 270) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 271)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 272)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 273) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 274) * bfq_delta - map service into the virtual time domain.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 275) * @service: amount of service.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 276) * @weight: scale factor (weight of an entity or weight sum).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 277) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 278) static u64 bfq_delta(unsigned long service, unsigned long weight)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 279) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 280) return div64_ul((u64)service << WFQ_SERVICE_SHIFT, weight);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 281) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 282)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 283) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 284) * bfq_calc_finish - assign the finish time to an entity.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 285) * @entity: the entity to act upon.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 286) * @service: the service to be charged to the entity.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 287) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 288) static void bfq_calc_finish(struct bfq_entity *entity, unsigned long service)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 289) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 290) struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 291)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 292) entity->finish = entity->start +
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 293) bfq_delta(service, entity->weight);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 294)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 295) if (bfqq) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 296) bfq_log_bfqq(bfqq->bfqd, bfqq,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 297) "calc_finish: serv %lu, w %d",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 298) service, entity->weight);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 299) bfq_log_bfqq(bfqq->bfqd, bfqq,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 300) "calc_finish: start %llu, finish %llu, delta %llu",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 301) entity->start, entity->finish,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 302) bfq_delta(service, entity->weight));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 303) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 304) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 305)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 306) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 307) * bfq_entity_of - get an entity from a node.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 308) * @node: the node field of the entity.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 309) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 310) * Convert a node pointer to the relative entity. This is used only
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 311) * to simplify the logic of some functions and not as the generic
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 312) * conversion mechanism because, e.g., in the tree walking functions,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 313) * the check for a %NULL value would be redundant.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 314) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 315) struct bfq_entity *bfq_entity_of(struct rb_node *node)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 316) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 317) struct bfq_entity *entity = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 318)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 319) if (node)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 320) entity = rb_entry(node, struct bfq_entity, rb_node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 321)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 322) return entity;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 323) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 324)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 325) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 326) * bfq_extract - remove an entity from a tree.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 327) * @root: the tree root.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 328) * @entity: the entity to remove.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 329) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 330) static void bfq_extract(struct rb_root *root, struct bfq_entity *entity)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 331) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 332) entity->tree = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 333) rb_erase(&entity->rb_node, root);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 334) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 335)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 336) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 337) * bfq_idle_extract - extract an entity from the idle tree.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 338) * @st: the service tree of the owning @entity.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 339) * @entity: the entity being removed.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 340) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 341) static void bfq_idle_extract(struct bfq_service_tree *st,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 342) struct bfq_entity *entity)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 343) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 344) struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 345) struct rb_node *next;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 346)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 347) if (entity == st->first_idle) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 348) next = rb_next(&entity->rb_node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 349) st->first_idle = bfq_entity_of(next);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 350) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 351)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 352) if (entity == st->last_idle) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 353) next = rb_prev(&entity->rb_node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 354) st->last_idle = bfq_entity_of(next);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 355) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 356)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 357) bfq_extract(&st->idle, entity);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 358)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 359) if (bfqq)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 360) list_del(&bfqq->bfqq_list);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 361) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 362)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 363) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 364) * bfq_insert - generic tree insertion.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 365) * @root: tree root.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 366) * @entity: entity to insert.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 367) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 368) * This is used for the idle and the active tree, since they are both
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 369) * ordered by finish time.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 370) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 371) static void bfq_insert(struct rb_root *root, struct bfq_entity *entity)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 372) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 373) struct bfq_entity *entry;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 374) struct rb_node **node = &root->rb_node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 375) struct rb_node *parent = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 376)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 377) while (*node) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 378) parent = *node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 379) entry = rb_entry(parent, struct bfq_entity, rb_node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 380)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 381) if (bfq_gt(entry->finish, entity->finish))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 382) node = &parent->rb_left;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 383) else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 384) node = &parent->rb_right;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 385) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 386)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 387) rb_link_node(&entity->rb_node, parent, node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 388) rb_insert_color(&entity->rb_node, root);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 389)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 390) entity->tree = root;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 391) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 392)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 393) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 394) * bfq_update_min - update the min_start field of a entity.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 395) * @entity: the entity to update.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 396) * @node: one of its children.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 397) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 398) * This function is called when @entity may store an invalid value for
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 399) * min_start due to updates to the active tree. The function assumes
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 400) * that the subtree rooted at @node (which may be its left or its right
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 401) * child) has a valid min_start value.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 402) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 403) static void bfq_update_min(struct bfq_entity *entity, struct rb_node *node)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 404) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 405) struct bfq_entity *child;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 406)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 407) if (node) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 408) child = rb_entry(node, struct bfq_entity, rb_node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 409) if (bfq_gt(entity->min_start, child->min_start))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 410) entity->min_start = child->min_start;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 411) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 412) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 413)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 414) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 415) * bfq_update_active_node - recalculate min_start.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 416) * @node: the node to update.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 417) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 418) * @node may have changed position or one of its children may have moved,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 419) * this function updates its min_start value. The left and right subtrees
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 420) * are assumed to hold a correct min_start value.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 421) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 422) static void bfq_update_active_node(struct rb_node *node)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 423) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 424) struct bfq_entity *entity = rb_entry(node, struct bfq_entity, rb_node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 425)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 426) entity->min_start = entity->start;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 427) bfq_update_min(entity, node->rb_right);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 428) bfq_update_min(entity, node->rb_left);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 429) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 430)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 431) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 432) * bfq_update_active_tree - update min_start for the whole active tree.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 433) * @node: the starting node.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 434) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 435) * @node must be the deepest modified node after an update. This function
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 436) * updates its min_start using the values held by its children, assuming
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 437) * that they did not change, and then updates all the nodes that may have
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 438) * changed in the path to the root. The only nodes that may have changed
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 439) * are the ones in the path or their siblings.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 440) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 441) static void bfq_update_active_tree(struct rb_node *node)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 442) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 443) struct rb_node *parent;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 444)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 445) up:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 446) bfq_update_active_node(node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 447)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 448) parent = rb_parent(node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 449) if (!parent)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 450) return;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 451)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 452) if (node == parent->rb_left && parent->rb_right)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 453) bfq_update_active_node(parent->rb_right);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 454) else if (parent->rb_left)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 455) bfq_update_active_node(parent->rb_left);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 456)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 457) node = parent;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 458) goto up;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 459) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 460)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 461) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 462) * bfq_active_insert - insert an entity in the active tree of its
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 463) * group/device.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 464) * @st: the service tree of the entity.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 465) * @entity: the entity being inserted.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 466) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 467) * The active tree is ordered by finish time, but an extra key is kept
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 468) * per each node, containing the minimum value for the start times of
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 469) * its children (and the node itself), so it's possible to search for
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 470) * the eligible node with the lowest finish time in logarithmic time.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 471) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 472) static void bfq_active_insert(struct bfq_service_tree *st,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 473) struct bfq_entity *entity)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 474) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 475) struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 476) struct rb_node *node = &entity->rb_node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 477) #ifdef CONFIG_BFQ_GROUP_IOSCHED
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 478) struct bfq_sched_data *sd = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 479) struct bfq_group *bfqg = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 480) struct bfq_data *bfqd = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 481) #endif
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 482)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 483) bfq_insert(&st->active, entity);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 484)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 485) if (node->rb_left)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 486) node = node->rb_left;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 487) else if (node->rb_right)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 488) node = node->rb_right;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 489)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 490) bfq_update_active_tree(node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 491)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 492) #ifdef CONFIG_BFQ_GROUP_IOSCHED
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 493) sd = entity->sched_data;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 494) bfqg = container_of(sd, struct bfq_group, sched_data);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 495) bfqd = (struct bfq_data *)bfqg->bfqd;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 496) #endif
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 497) if (bfqq)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 498) list_add(&bfqq->bfqq_list, &bfqq->bfqd->active_list);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 499) #ifdef CONFIG_BFQ_GROUP_IOSCHED
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 500) if (bfqg != bfqd->root_group)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 501) bfqg->active_entities++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 502) #endif
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 503) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 504)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 505) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 506) * bfq_ioprio_to_weight - calc a weight from an ioprio.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 507) * @ioprio: the ioprio value to convert.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 508) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 509) unsigned short bfq_ioprio_to_weight(int ioprio)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 510) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 511) return (IOPRIO_BE_NR - ioprio) * BFQ_WEIGHT_CONVERSION_COEFF;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 512) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 513)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 514) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 515) * bfq_weight_to_ioprio - calc an ioprio from a weight.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 516) * @weight: the weight value to convert.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 517) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 518) * To preserve as much as possible the old only-ioprio user interface,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 519) * 0 is used as an escape ioprio value for weights (numerically) equal or
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 520) * larger than IOPRIO_BE_NR * BFQ_WEIGHT_CONVERSION_COEFF.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 521) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 522) static unsigned short bfq_weight_to_ioprio(int weight)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 523) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 524) return max_t(int, 0,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 525) IOPRIO_BE_NR * BFQ_WEIGHT_CONVERSION_COEFF - weight);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 526) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 527)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 528) static void bfq_get_entity(struct bfq_entity *entity)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 529) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 530) struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 531)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 532) if (bfqq) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 533) bfqq->ref++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 534) bfq_log_bfqq(bfqq->bfqd, bfqq, "get_entity: %p %d",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 535) bfqq, bfqq->ref);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 536) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 537) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 538)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 539) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 540) * bfq_find_deepest - find the deepest node that an extraction can modify.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 541) * @node: the node being removed.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 542) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 543) * Do the first step of an extraction in an rb tree, looking for the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 544) * node that will replace @node, and returning the deepest node that
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 545) * the following modifications to the tree can touch. If @node is the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 546) * last node in the tree return %NULL.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 547) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 548) static struct rb_node *bfq_find_deepest(struct rb_node *node)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 549) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 550) struct rb_node *deepest;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 551)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 552) if (!node->rb_right && !node->rb_left)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 553) deepest = rb_parent(node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 554) else if (!node->rb_right)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 555) deepest = node->rb_left;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 556) else if (!node->rb_left)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 557) deepest = node->rb_right;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 558) else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 559) deepest = rb_next(node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 560) if (deepest->rb_right)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 561) deepest = deepest->rb_right;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 562) else if (rb_parent(deepest) != node)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 563) deepest = rb_parent(deepest);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 564) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 565)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 566) return deepest;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 567) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 568)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 569) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 570) * bfq_active_extract - remove an entity from the active tree.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 571) * @st: the service_tree containing the tree.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 572) * @entity: the entity being removed.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 573) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 574) static void bfq_active_extract(struct bfq_service_tree *st,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 575) struct bfq_entity *entity)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 576) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 577) struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 578) struct rb_node *node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 579) #ifdef CONFIG_BFQ_GROUP_IOSCHED
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 580) struct bfq_sched_data *sd = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 581) struct bfq_group *bfqg = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 582) struct bfq_data *bfqd = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 583) #endif
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 584)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 585) node = bfq_find_deepest(&entity->rb_node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 586) bfq_extract(&st->active, entity);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 587)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 588) if (node)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 589) bfq_update_active_tree(node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 590)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 591) #ifdef CONFIG_BFQ_GROUP_IOSCHED
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 592) sd = entity->sched_data;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 593) bfqg = container_of(sd, struct bfq_group, sched_data);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 594) bfqd = (struct bfq_data *)bfqg->bfqd;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 595) #endif
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 596) if (bfqq)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 597) list_del(&bfqq->bfqq_list);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 598) #ifdef CONFIG_BFQ_GROUP_IOSCHED
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 599) if (bfqg != bfqd->root_group)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 600) bfqg->active_entities--;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 601) #endif
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 602) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 603)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 604) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 605) * bfq_idle_insert - insert an entity into the idle tree.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 606) * @st: the service tree containing the tree.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 607) * @entity: the entity to insert.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 608) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 609) static void bfq_idle_insert(struct bfq_service_tree *st,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 610) struct bfq_entity *entity)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 611) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 612) struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 613) struct bfq_entity *first_idle = st->first_idle;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 614) struct bfq_entity *last_idle = st->last_idle;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 615)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 616) if (!first_idle || bfq_gt(first_idle->finish, entity->finish))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 617) st->first_idle = entity;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 618) if (!last_idle || bfq_gt(entity->finish, last_idle->finish))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 619) st->last_idle = entity;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 620)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 621) bfq_insert(&st->idle, entity);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 622)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 623) if (bfqq)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 624) list_add(&bfqq->bfqq_list, &bfqq->bfqd->idle_list);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 625) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 626)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 627) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 628) * bfq_forget_entity - do not consider entity any longer for scheduling
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 629) * @st: the service tree.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 630) * @entity: the entity being removed.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 631) * @is_in_service: true if entity is currently the in-service entity.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 632) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 633) * Forget everything about @entity. In addition, if entity represents
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 634) * a queue, and the latter is not in service, then release the service
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 635) * reference to the queue (the one taken through bfq_get_entity). In
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 636) * fact, in this case, there is really no more service reference to
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 637) * the queue, as the latter is also outside any service tree. If,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 638) * instead, the queue is in service, then __bfq_bfqd_reset_in_service
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 639) * will take care of putting the reference when the queue finally
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 640) * stops being served.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 641) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 642) static void bfq_forget_entity(struct bfq_service_tree *st,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 643) struct bfq_entity *entity,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 644) bool is_in_service)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 645) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 646) struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 647)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 648) entity->on_st_or_in_serv = false;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 649) st->wsum -= entity->weight;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 650) if (bfqq && !is_in_service)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 651) bfq_put_queue(bfqq);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 652) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 653)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 654) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 655) * bfq_put_idle_entity - release the idle tree ref of an entity.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 656) * @st: service tree for the entity.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 657) * @entity: the entity being released.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 658) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 659) void bfq_put_idle_entity(struct bfq_service_tree *st, struct bfq_entity *entity)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 660) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 661) bfq_idle_extract(st, entity);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 662) bfq_forget_entity(st, entity,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 663) entity == entity->sched_data->in_service_entity);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 664) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 665)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 666) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 667) * bfq_forget_idle - update the idle tree if necessary.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 668) * @st: the service tree to act upon.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 669) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 670) * To preserve the global O(log N) complexity we only remove one entry here;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 671) * as the idle tree will not grow indefinitely this can be done safely.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 672) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 673) static void bfq_forget_idle(struct bfq_service_tree *st)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 674) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 675) struct bfq_entity *first_idle = st->first_idle;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 676) struct bfq_entity *last_idle = st->last_idle;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 677)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 678) if (RB_EMPTY_ROOT(&st->active) && last_idle &&
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 679) !bfq_gt(last_idle->finish, st->vtime)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 680) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 681) * Forget the whole idle tree, increasing the vtime past
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 682) * the last finish time of idle entities.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 683) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 684) st->vtime = last_idle->finish;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 685) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 686)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 687) if (first_idle && !bfq_gt(first_idle->finish, st->vtime))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 688) bfq_put_idle_entity(st, first_idle);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 689) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 690)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 691) struct bfq_service_tree *bfq_entity_service_tree(struct bfq_entity *entity)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 692) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 693) struct bfq_sched_data *sched_data = entity->sched_data;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 694) unsigned int idx = bfq_class_idx(entity);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 695)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 696) return sched_data->service_tree + idx;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 697) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 698)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 699) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 700) * Update weight and priority of entity. If update_class_too is true,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 701) * then update the ioprio_class of entity too.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 702) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 703) * The reason why the update of ioprio_class is controlled through the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 704) * last parameter is as follows. Changing the ioprio class of an
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 705) * entity implies changing the destination service trees for that
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 706) * entity. If such a change occurred when the entity is already on one
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 707) * of the service trees for its previous class, then the state of the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 708) * entity would become more complex: none of the new possible service
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 709) * trees for the entity, according to bfq_entity_service_tree(), would
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 710) * match any of the possible service trees on which the entity
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 711) * is. Complex operations involving these trees, such as entity
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 712) * activations and deactivations, should take into account this
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 713) * additional complexity. To avoid this issue, this function is
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 714) * invoked with update_class_too unset in the points in the code where
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 715) * entity may happen to be on some tree.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 716) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 717) struct bfq_service_tree *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 718) __bfq_entity_update_weight_prio(struct bfq_service_tree *old_st,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 719) struct bfq_entity *entity,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 720) bool update_class_too)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 721) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 722) struct bfq_service_tree *new_st = old_st;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 723)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 724) if (entity->prio_changed) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 725) struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 726) unsigned int prev_weight, new_weight;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 727) struct bfq_data *bfqd = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 728) struct rb_root_cached *root;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 729) #ifdef CONFIG_BFQ_GROUP_IOSCHED
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 730) struct bfq_sched_data *sd;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 731) struct bfq_group *bfqg;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 732) #endif
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 733)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 734) if (bfqq)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 735) bfqd = bfqq->bfqd;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 736) #ifdef CONFIG_BFQ_GROUP_IOSCHED
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 737) else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 738) sd = entity->my_sched_data;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 739) bfqg = container_of(sd, struct bfq_group, sched_data);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 740) bfqd = (struct bfq_data *)bfqg->bfqd;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 741) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 742) #endif
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 743)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 744) /* Matches the smp_wmb() in bfq_group_set_weight. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 745) smp_rmb();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 746) old_st->wsum -= entity->weight;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 747)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 748) if (entity->new_weight != entity->orig_weight) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 749) if (entity->new_weight < BFQ_MIN_WEIGHT ||
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 750) entity->new_weight > BFQ_MAX_WEIGHT) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 751) pr_crit("update_weight_prio: new_weight %d\n",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 752) entity->new_weight);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 753) if (entity->new_weight < BFQ_MIN_WEIGHT)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 754) entity->new_weight = BFQ_MIN_WEIGHT;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 755) else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 756) entity->new_weight = BFQ_MAX_WEIGHT;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 757) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 758) entity->orig_weight = entity->new_weight;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 759) if (bfqq)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 760) bfqq->ioprio =
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 761) bfq_weight_to_ioprio(entity->orig_weight);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 762) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 763)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 764) if (bfqq && update_class_too)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 765) bfqq->ioprio_class = bfqq->new_ioprio_class;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 766)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 767) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 768) * Reset prio_changed only if the ioprio_class change
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 769) * is not pending any longer.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 770) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 771) if (!bfqq || bfqq->ioprio_class == bfqq->new_ioprio_class)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 772) entity->prio_changed = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 773)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 774) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 775) * NOTE: here we may be changing the weight too early,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 776) * this will cause unfairness. The correct approach
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 777) * would have required additional complexity to defer
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 778) * weight changes to the proper time instants (i.e.,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 779) * when entity->finish <= old_st->vtime).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 780) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 781) new_st = bfq_entity_service_tree(entity);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 782)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 783) prev_weight = entity->weight;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 784) new_weight = entity->orig_weight *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 785) (bfqq ? bfqq->wr_coeff : 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 786) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 787) * If the weight of the entity changes, and the entity is a
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 788) * queue, remove the entity from its old weight counter (if
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 789) * there is a counter associated with the entity).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 790) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 791) if (prev_weight != new_weight && bfqq) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 792) root = &bfqd->queue_weights_tree;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 793) __bfq_weights_tree_remove(bfqd, bfqq, root);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 794) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 795) entity->weight = new_weight;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 796) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 797) * Add the entity, if it is not a weight-raised queue,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 798) * to the counter associated with its new weight.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 799) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 800) if (prev_weight != new_weight && bfqq && bfqq->wr_coeff == 1) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 801) /* If we get here, root has been initialized. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 802) bfq_weights_tree_add(bfqd, bfqq, root);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 803) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 804)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 805) new_st->wsum += entity->weight;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 806)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 807) if (new_st != old_st)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 808) entity->start = new_st->vtime;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 809) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 810)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 811) return new_st;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 812) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 813)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 814) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 815) * bfq_bfqq_served - update the scheduler status after selection for
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 816) * service.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 817) * @bfqq: the queue being served.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 818) * @served: bytes to transfer.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 819) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 820) * NOTE: this can be optimized, as the timestamps of upper level entities
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 821) * are synchronized every time a new bfqq is selected for service. By now,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 822) * we keep it to better check consistency.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 823) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 824) void bfq_bfqq_served(struct bfq_queue *bfqq, int served)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 825) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 826) struct bfq_entity *entity = &bfqq->entity;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 827) struct bfq_service_tree *st;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 828)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 829) if (!bfqq->service_from_backlogged)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 830) bfqq->first_IO_time = jiffies;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 831)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 832) if (bfqq->wr_coeff > 1)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 833) bfqq->service_from_wr += served;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 834)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 835) bfqq->service_from_backlogged += served;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 836) for_each_entity(entity) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 837) st = bfq_entity_service_tree(entity);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 838)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 839) entity->service += served;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 840)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 841) st->vtime += bfq_delta(served, st->wsum);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 842) bfq_forget_idle(st);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 843) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 844) bfq_log_bfqq(bfqq->bfqd, bfqq, "bfqq_served %d secs", served);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 845) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 846)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 847) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 848) * bfq_bfqq_charge_time - charge an amount of service equivalent to the length
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 849) * of the time interval during which bfqq has been in
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 850) * service.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 851) * @bfqd: the device
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 852) * @bfqq: the queue that needs a service update.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 853) * @time_ms: the amount of time during which the queue has received service
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 854) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 855) * If a queue does not consume its budget fast enough, then providing
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 856) * the queue with service fairness may impair throughput, more or less
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 857) * severely. For this reason, queues that consume their budget slowly
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 858) * are provided with time fairness instead of service fairness. This
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 859) * goal is achieved through the BFQ scheduling engine, even if such an
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 860) * engine works in the service, and not in the time domain. The trick
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 861) * is charging these queues with an inflated amount of service, equal
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 862) * to the amount of service that they would have received during their
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 863) * service slot if they had been fast, i.e., if their requests had
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 864) * been dispatched at a rate equal to the estimated peak rate.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 865) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 866) * It is worth noting that time fairness can cause important
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 867) * distortions in terms of bandwidth distribution, on devices with
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 868) * internal queueing. The reason is that I/O requests dispatched
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 869) * during the service slot of a queue may be served after that service
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 870) * slot is finished, and may have a total processing time loosely
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 871) * correlated with the duration of the service slot. This is
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 872) * especially true for short service slots.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 873) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 874) void bfq_bfqq_charge_time(struct bfq_data *bfqd, struct bfq_queue *bfqq,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 875) unsigned long time_ms)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 876) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 877) struct bfq_entity *entity = &bfqq->entity;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 878) unsigned long timeout_ms = jiffies_to_msecs(bfq_timeout);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 879) unsigned long bounded_time_ms = min(time_ms, timeout_ms);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 880) int serv_to_charge_for_time =
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 881) (bfqd->bfq_max_budget * bounded_time_ms) / timeout_ms;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 882) int tot_serv_to_charge = max(serv_to_charge_for_time, entity->service);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 883)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 884) /* Increase budget to avoid inconsistencies */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 885) if (tot_serv_to_charge > entity->budget)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 886) entity->budget = tot_serv_to_charge;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 887)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 888) bfq_bfqq_served(bfqq,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 889) max_t(int, 0, tot_serv_to_charge - entity->service));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 890) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 891)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 892) static void bfq_update_fin_time_enqueue(struct bfq_entity *entity,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 893) struct bfq_service_tree *st,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 894) bool backshifted)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 895) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 896) struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 897)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 898) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 899) * When this function is invoked, entity is not in any service
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 900) * tree, then it is safe to invoke next function with the last
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 901) * parameter set (see the comments on the function).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 902) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 903) st = __bfq_entity_update_weight_prio(st, entity, true);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 904) bfq_calc_finish(entity, entity->budget);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 905)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 906) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 907) * If some queues enjoy backshifting for a while, then their
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 908) * (virtual) finish timestamps may happen to become lower and
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 909) * lower than the system virtual time. In particular, if
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 910) * these queues often happen to be idle for short time
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 911) * periods, and during such time periods other queues with
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 912) * higher timestamps happen to be busy, then the backshifted
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 913) * timestamps of the former queues can become much lower than
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 914) * the system virtual time. In fact, to serve the queues with
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 915) * higher timestamps while the ones with lower timestamps are
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 916) * idle, the system virtual time may be pushed-up to much
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 917) * higher values than the finish timestamps of the idle
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 918) * queues. As a consequence, the finish timestamps of all new
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 919) * or newly activated queues may end up being much larger than
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 920) * those of lucky queues with backshifted timestamps. The
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 921) * latter queues may then monopolize the device for a lot of
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 922) * time. This would simply break service guarantees.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 923) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 924) * To reduce this problem, push up a little bit the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 925) * backshifted timestamps of the queue associated with this
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 926) * entity (only a queue can happen to have the backshifted
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 927) * flag set): just enough to let the finish timestamp of the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 928) * queue be equal to the current value of the system virtual
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 929) * time. This may introduce a little unfairness among queues
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 930) * with backshifted timestamps, but it does not break
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 931) * worst-case fairness guarantees.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 932) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 933) * As a special case, if bfqq is weight-raised, push up
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 934) * timestamps much less, to keep very low the probability that
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 935) * this push up causes the backshifted finish timestamps of
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 936) * weight-raised queues to become higher than the backshifted
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 937) * finish timestamps of non weight-raised queues.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 938) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 939) if (backshifted && bfq_gt(st->vtime, entity->finish)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 940) unsigned long delta = st->vtime - entity->finish;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 941)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 942) if (bfqq)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 943) delta /= bfqq->wr_coeff;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 944)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 945) entity->start += delta;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 946) entity->finish += delta;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 947) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 948)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 949) bfq_active_insert(st, entity);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 950) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 951)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 952) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 953) * __bfq_activate_entity - handle activation of entity.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 954) * @entity: the entity being activated.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 955) * @non_blocking_wait_rq: true if entity was waiting for a request
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 956) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 957) * Called for a 'true' activation, i.e., if entity is not active and
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 958) * one of its children receives a new request.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 959) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 960) * Basically, this function updates the timestamps of entity and
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 961) * inserts entity into its active tree, after possibly extracting it
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 962) * from its idle tree.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 963) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 964) static void __bfq_activate_entity(struct bfq_entity *entity,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 965) bool non_blocking_wait_rq)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 966) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 967) struct bfq_service_tree *st = bfq_entity_service_tree(entity);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 968) bool backshifted = false;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 969) unsigned long long min_vstart;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 970)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 971) /* See comments on bfq_fqq_update_budg_for_activation */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 972) if (non_blocking_wait_rq && bfq_gt(st->vtime, entity->finish)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 973) backshifted = true;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 974) min_vstart = entity->finish;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 975) } else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 976) min_vstart = st->vtime;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 977)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 978) if (entity->tree == &st->idle) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 979) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 980) * Must be on the idle tree, bfq_idle_extract() will
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 981) * check for that.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 982) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 983) bfq_idle_extract(st, entity);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 984) entity->start = bfq_gt(min_vstart, entity->finish) ?
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 985) min_vstart : entity->finish;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 986) } else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 987) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 988) * The finish time of the entity may be invalid, and
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 989) * it is in the past for sure, otherwise the queue
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 990) * would have been on the idle tree.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 991) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 992) entity->start = min_vstart;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 993) st->wsum += entity->weight;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 994) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 995) * entity is about to be inserted into a service tree,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 996) * and then set in service: get a reference to make
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 997) * sure entity does not disappear until it is no
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 998) * longer in service or scheduled for service.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 999) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1000) bfq_get_entity(entity);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1001)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1002) entity->on_st_or_in_serv = true;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1003) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1004)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1005) #ifdef CONFIG_BFQ_GROUP_IOSCHED
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1006) if (!bfq_entity_to_bfqq(entity)) { /* bfq_group */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1007) struct bfq_group *bfqg =
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1008) container_of(entity, struct bfq_group, entity);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1009) struct bfq_data *bfqd = bfqg->bfqd;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1010)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1011) if (!entity->in_groups_with_pending_reqs) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1012) entity->in_groups_with_pending_reqs = true;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1013) bfqd->num_groups_with_pending_reqs++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1014) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1015) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1016) #endif
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1017)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1018) bfq_update_fin_time_enqueue(entity, st, backshifted);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1019) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1020)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1021) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1022) * __bfq_requeue_entity - handle requeueing or repositioning of an entity.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1023) * @entity: the entity being requeued or repositioned.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1024) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1025) * Requeueing is needed if this entity stops being served, which
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1026) * happens if a leaf descendant entity has expired. On the other hand,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1027) * repositioning is needed if the next_inservice_entity for the child
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1028) * entity has changed. See the comments inside the function for
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1029) * details.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1030) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1031) * Basically, this function: 1) removes entity from its active tree if
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1032) * present there, 2) updates the timestamps of entity and 3) inserts
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1033) * entity back into its active tree (in the new, right position for
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1034) * the new values of the timestamps).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1035) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1036) static void __bfq_requeue_entity(struct bfq_entity *entity)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1037) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1038) struct bfq_sched_data *sd = entity->sched_data;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1039) struct bfq_service_tree *st = bfq_entity_service_tree(entity);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1040)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1041) if (entity == sd->in_service_entity) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1042) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1043) * We are requeueing the current in-service entity,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1044) * which may have to be done for one of the following
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1045) * reasons:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1046) * - entity represents the in-service queue, and the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1047) * in-service queue is being requeued after an
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1048) * expiration;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1049) * - entity represents a group, and its budget has
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1050) * changed because one of its child entities has
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1051) * just been either activated or requeued for some
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1052) * reason; the timestamps of the entity need then to
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1053) * be updated, and the entity needs to be enqueued
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1054) * or repositioned accordingly.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1055) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1056) * In particular, before requeueing, the start time of
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1057) * the entity must be moved forward to account for the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1058) * service that the entity has received while in
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1059) * service. This is done by the next instructions. The
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1060) * finish time will then be updated according to this
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1061) * new value of the start time, and to the budget of
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1062) * the entity.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1063) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1064) bfq_calc_finish(entity, entity->service);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1065) entity->start = entity->finish;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1066) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1067) * In addition, if the entity had more than one child
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1068) * when set in service, then it was not extracted from
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1069) * the active tree. This implies that the position of
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1070) * the entity in the active tree may need to be
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1071) * changed now, because we have just updated the start
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1072) * time of the entity, and we will update its finish
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1073) * time in a moment (the requeueing is then, more
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1074) * precisely, a repositioning in this case). To
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1075) * implement this repositioning, we: 1) dequeue the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1076) * entity here, 2) update the finish time and requeue
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1077) * the entity according to the new timestamps below.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1078) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1079) if (entity->tree)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1080) bfq_active_extract(st, entity);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1081) } else { /* The entity is already active, and not in service */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1082) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1083) * In this case, this function gets called only if the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1084) * next_in_service entity below this entity has
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1085) * changed, and this change has caused the budget of
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1086) * this entity to change, which, finally implies that
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1087) * the finish time of this entity must be
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1088) * updated. Such an update may cause the scheduling,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1089) * i.e., the position in the active tree, of this
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1090) * entity to change. We handle this change by: 1)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1091) * dequeueing the entity here, 2) updating the finish
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1092) * time and requeueing the entity according to the new
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1093) * timestamps below. This is the same approach as the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1094) * non-extracted-entity sub-case above.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1095) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1096) bfq_active_extract(st, entity);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1097) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1098)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1099) bfq_update_fin_time_enqueue(entity, st, false);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1100) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1101)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1102) static void __bfq_activate_requeue_entity(struct bfq_entity *entity,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1103) struct bfq_sched_data *sd,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1104) bool non_blocking_wait_rq)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1105) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1106) struct bfq_service_tree *st = bfq_entity_service_tree(entity);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1107)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1108) if (sd->in_service_entity == entity || entity->tree == &st->active)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1109) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1110) * in service or already queued on the active tree,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1111) * requeue or reposition
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1112) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1113) __bfq_requeue_entity(entity);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1114) else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1115) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1116) * Not in service and not queued on its active tree:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1117) * the activity is idle and this is a true activation.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1118) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1119) __bfq_activate_entity(entity, non_blocking_wait_rq);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1120) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1121)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1122)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1123) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1124) * bfq_activate_requeue_entity - activate or requeue an entity representing a
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1125) * bfq_queue, and activate, requeue or reposition
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1126) * all ancestors for which such an update becomes
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1127) * necessary.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1128) * @entity: the entity to activate.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1129) * @non_blocking_wait_rq: true if this entity was waiting for a request
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1130) * @requeue: true if this is a requeue, which implies that bfqq is
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1131) * being expired; thus ALL its ancestors stop being served and must
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1132) * therefore be requeued
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1133) * @expiration: true if this function is being invoked in the expiration path
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1134) * of the in-service queue
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1135) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1136) static void bfq_activate_requeue_entity(struct bfq_entity *entity,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1137) bool non_blocking_wait_rq,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1138) bool requeue, bool expiration)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1139) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1140) struct bfq_sched_data *sd;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1141)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1142) for_each_entity(entity) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1143) sd = entity->sched_data;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1144) __bfq_activate_requeue_entity(entity, sd, non_blocking_wait_rq);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1145)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1146) if (!bfq_update_next_in_service(sd, entity, expiration) &&
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1147) !requeue)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1148) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1149) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1150) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1151)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1152) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1153) * __bfq_deactivate_entity - update sched_data and service trees for
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1154) * entity, so as to represent entity as inactive
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1155) * @entity: the entity being deactivated.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1156) * @ins_into_idle_tree: if false, the entity will not be put into the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1157) * idle tree.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1158) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1159) * If necessary and allowed, puts entity into the idle tree. NOTE:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1160) * entity may be on no tree if in service.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1161) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1162) bool __bfq_deactivate_entity(struct bfq_entity *entity, bool ins_into_idle_tree)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1163) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1164) struct bfq_sched_data *sd = entity->sched_data;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1165) struct bfq_service_tree *st;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1166) bool is_in_service;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1167)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1168) if (!entity->on_st_or_in_serv) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1169) * entity never activated, or
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1170) * already inactive
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1171) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1172) return false;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1173)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1174) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1175) * If we get here, then entity is active, which implies that
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1176) * bfq_group_set_parent has already been invoked for the group
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1177) * represented by entity. Therefore, the field
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1178) * entity->sched_data has been set, and we can safely use it.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1179) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1180) st = bfq_entity_service_tree(entity);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1181) is_in_service = entity == sd->in_service_entity;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1182)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1183) bfq_calc_finish(entity, entity->service);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1184)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1185) if (is_in_service)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1186) sd->in_service_entity = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1187) else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1188) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1189) * Non in-service entity: nobody will take care of
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1190) * resetting its service counter on expiration. Do it
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1191) * now.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1192) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1193) entity->service = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1194)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1195) if (entity->tree == &st->active)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1196) bfq_active_extract(st, entity);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1197) else if (!is_in_service && entity->tree == &st->idle)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1198) bfq_idle_extract(st, entity);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1199)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1200) if (!ins_into_idle_tree || !bfq_gt(entity->finish, st->vtime))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1201) bfq_forget_entity(st, entity, is_in_service);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1202) else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1203) bfq_idle_insert(st, entity);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1204)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1205) return true;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1206) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1207)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1208) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1209) * bfq_deactivate_entity - deactivate an entity representing a bfq_queue.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1210) * @entity: the entity to deactivate.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1211) * @ins_into_idle_tree: true if the entity can be put into the idle tree
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1212) * @expiration: true if this function is being invoked in the expiration path
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1213) * of the in-service queue
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1214) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1215) static void bfq_deactivate_entity(struct bfq_entity *entity,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1216) bool ins_into_idle_tree,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1217) bool expiration)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1218) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1219) struct bfq_sched_data *sd;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1220) struct bfq_entity *parent = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1221)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1222) for_each_entity_safe(entity, parent) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1223) sd = entity->sched_data;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1224)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1225) if (!__bfq_deactivate_entity(entity, ins_into_idle_tree)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1226) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1227) * entity is not in any tree any more, so
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1228) * this deactivation is a no-op, and there is
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1229) * nothing to change for upper-level entities
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1230) * (in case of expiration, this can never
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1231) * happen).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1232) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1233) return;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1234) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1235)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1236) if (sd->next_in_service == entity)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1237) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1238) * entity was the next_in_service entity,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1239) * then, since entity has just been
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1240) * deactivated, a new one must be found.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1241) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1242) bfq_update_next_in_service(sd, NULL, expiration);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1243)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1244) if (sd->next_in_service || sd->in_service_entity) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1245) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1246) * The parent entity is still active, because
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1247) * either next_in_service or in_service_entity
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1248) * is not NULL. So, no further upwards
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1249) * deactivation must be performed. Yet,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1250) * next_in_service has changed. Then the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1251) * schedule does need to be updated upwards.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1252) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1253) * NOTE If in_service_entity is not NULL, then
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1254) * next_in_service may happen to be NULL,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1255) * although the parent entity is evidently
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1256) * active. This happens if 1) the entity
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1257) * pointed by in_service_entity is the only
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1258) * active entity in the parent entity, and 2)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1259) * according to the definition of
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1260) * next_in_service, the in_service_entity
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1261) * cannot be considered as
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1262) * next_in_service. See the comments on the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1263) * definition of next_in_service for details.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1264) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1265) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1266) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1267)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1268) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1269) * If we get here, then the parent is no more
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1270) * backlogged and we need to propagate the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1271) * deactivation upwards. Thus let the loop go on.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1272) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1273)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1274) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1275) * Also let parent be queued into the idle tree on
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1276) * deactivation, to preserve service guarantees, and
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1277) * assuming that who invoked this function does not
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1278) * need parent entities too to be removed completely.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1279) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1280) ins_into_idle_tree = true;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1281) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1282)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1283) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1284) * If the deactivation loop is fully executed, then there are
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1285) * no more entities to touch and next loop is not executed at
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1286) * all. Otherwise, requeue remaining entities if they are
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1287) * about to stop receiving service, or reposition them if this
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1288) * is not the case.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1289) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1290) entity = parent;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1291) for_each_entity(entity) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1292) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1293) * Invoke __bfq_requeue_entity on entity, even if
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1294) * already active, to requeue/reposition it in the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1295) * active tree (because sd->next_in_service has
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1296) * changed)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1297) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1298) __bfq_requeue_entity(entity);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1299)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1300) sd = entity->sched_data;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1301) if (!bfq_update_next_in_service(sd, entity, expiration) &&
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1302) !expiration)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1303) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1304) * next_in_service unchanged or not causing
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1305) * any change in entity->parent->sd, and no
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1306) * requeueing needed for expiration: stop
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1307) * here.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1308) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1309) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1310) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1311) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1312)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1313) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1314) * bfq_calc_vtime_jump - compute the value to which the vtime should jump,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1315) * if needed, to have at least one entity eligible.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1316) * @st: the service tree to act upon.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1317) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1318) * Assumes that st is not empty.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1319) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1320) static u64 bfq_calc_vtime_jump(struct bfq_service_tree *st)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1321) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1322) struct bfq_entity *root_entity = bfq_root_active_entity(&st->active);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1323)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1324) if (bfq_gt(root_entity->min_start, st->vtime))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1325) return root_entity->min_start;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1326)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1327) return st->vtime;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1328) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1329)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1330) static void bfq_update_vtime(struct bfq_service_tree *st, u64 new_value)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1331) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1332) if (new_value > st->vtime) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1333) st->vtime = new_value;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1334) bfq_forget_idle(st);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1335) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1336) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1337)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1338) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1339) * bfq_first_active_entity - find the eligible entity with
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1340) * the smallest finish time
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1341) * @st: the service tree to select from.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1342) * @vtime: the system virtual to use as a reference for eligibility
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1343) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1344) * This function searches the first schedulable entity, starting from the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1345) * root of the tree and going on the left every time on this side there is
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1346) * a subtree with at least one eligible (start <= vtime) entity. The path on
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1347) * the right is followed only if a) the left subtree contains no eligible
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1348) * entities and b) no eligible entity has been found yet.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1349) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1350) static struct bfq_entity *bfq_first_active_entity(struct bfq_service_tree *st,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1351) u64 vtime)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1352) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1353) struct bfq_entity *entry, *first = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1354) struct rb_node *node = st->active.rb_node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1355)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1356) while (node) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1357) entry = rb_entry(node, struct bfq_entity, rb_node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1358) left:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1359) if (!bfq_gt(entry->start, vtime))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1360) first = entry;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1361)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1362) if (node->rb_left) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1363) entry = rb_entry(node->rb_left,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1364) struct bfq_entity, rb_node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1365) if (!bfq_gt(entry->min_start, vtime)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1366) node = node->rb_left;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1367) goto left;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1368) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1369) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1370) if (first)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1371) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1372) node = node->rb_right;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1373) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1374)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1375) return first;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1376) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1377)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1378) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1379) * __bfq_lookup_next_entity - return the first eligible entity in @st.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1380) * @st: the service tree.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1381) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1382) * If there is no in-service entity for the sched_data st belongs to,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1383) * then return the entity that will be set in service if:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1384) * 1) the parent entity this st belongs to is set in service;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1385) * 2) no entity belonging to such parent entity undergoes a state change
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1386) * that would influence the timestamps of the entity (e.g., becomes idle,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1387) * becomes backlogged, changes its budget, ...).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1388) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1389) * In this first case, update the virtual time in @st too (see the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1390) * comments on this update inside the function).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1391) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1392) * In contrast, if there is an in-service entity, then return the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1393) * entity that would be set in service if not only the above
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1394) * conditions, but also the next one held true: the currently
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1395) * in-service entity, on expiration,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1396) * 1) gets a finish time equal to the current one, or
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1397) * 2) is not eligible any more, or
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1398) * 3) is idle.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1399) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1400) static struct bfq_entity *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1401) __bfq_lookup_next_entity(struct bfq_service_tree *st, bool in_service)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1402) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1403) struct bfq_entity *entity;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1404) u64 new_vtime;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1405)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1406) if (RB_EMPTY_ROOT(&st->active))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1407) return NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1408)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1409) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1410) * Get the value of the system virtual time for which at
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1411) * least one entity is eligible.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1412) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1413) new_vtime = bfq_calc_vtime_jump(st);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1414)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1415) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1416) * If there is no in-service entity for the sched_data this
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1417) * active tree belongs to, then push the system virtual time
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1418) * up to the value that guarantees that at least one entity is
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1419) * eligible. If, instead, there is an in-service entity, then
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1420) * do not make any such update, because there is already an
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1421) * eligible entity, namely the in-service one (even if the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1422) * entity is not on st, because it was extracted when set in
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1423) * service).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1424) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1425) if (!in_service)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1426) bfq_update_vtime(st, new_vtime);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1427)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1428) entity = bfq_first_active_entity(st, new_vtime);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1429)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1430) return entity;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1431) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1432)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1433) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1434) * bfq_lookup_next_entity - return the first eligible entity in @sd.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1435) * @sd: the sched_data.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1436) * @expiration: true if we are on the expiration path of the in-service queue
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1437) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1438) * This function is invoked when there has been a change in the trees
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1439) * for sd, and we need to know what is the new next entity to serve
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1440) * after this change.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1441) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1442) static struct bfq_entity *bfq_lookup_next_entity(struct bfq_sched_data *sd,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1443) bool expiration)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1444) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1445) struct bfq_service_tree *st = sd->service_tree;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1446) struct bfq_service_tree *idle_class_st = st + (BFQ_IOPRIO_CLASSES - 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1447) struct bfq_entity *entity = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1448) int class_idx = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1449)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1450) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1451) * Choose from idle class, if needed to guarantee a minimum
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1452) * bandwidth to this class (and if there is some active entity
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1453) * in idle class). This should also mitigate
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1454) * priority-inversion problems in case a low priority task is
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1455) * holding file system resources.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1456) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1457) if (time_is_before_jiffies(sd->bfq_class_idle_last_service +
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1458) BFQ_CL_IDLE_TIMEOUT)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1459) if (!RB_EMPTY_ROOT(&idle_class_st->active))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1460) class_idx = BFQ_IOPRIO_CLASSES - 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1461) /* About to be served if backlogged, or not yet backlogged */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1462) sd->bfq_class_idle_last_service = jiffies;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1463) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1464)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1465) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1466) * Find the next entity to serve for the highest-priority
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1467) * class, unless the idle class needs to be served.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1468) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1469) for (; class_idx < BFQ_IOPRIO_CLASSES; class_idx++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1470) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1471) * If expiration is true, then bfq_lookup_next_entity
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1472) * is being invoked as a part of the expiration path
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1473) * of the in-service queue. In this case, even if
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1474) * sd->in_service_entity is not NULL,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1475) * sd->in_service_entity at this point is actually not
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1476) * in service any more, and, if needed, has already
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1477) * been properly queued or requeued into the right
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1478) * tree. The reason why sd->in_service_entity is still
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1479) * not NULL here, even if expiration is true, is that
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1480) * sd->in_service_entity is reset as a last step in the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1481) * expiration path. So, if expiration is true, tell
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1482) * __bfq_lookup_next_entity that there is no
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1483) * sd->in_service_entity.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1484) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1485) entity = __bfq_lookup_next_entity(st + class_idx,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1486) sd->in_service_entity &&
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1487) !expiration);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1488)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1489) if (entity)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1490) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1491) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1492)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1493) if (!entity)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1494) return NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1495)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1496) return entity;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1497) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1498)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1499) bool next_queue_may_preempt(struct bfq_data *bfqd)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1500) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1501) struct bfq_sched_data *sd = &bfqd->root_group->sched_data;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1502)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1503) return sd->next_in_service != sd->in_service_entity;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1504) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1505)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1506) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1507) * Get next queue for service.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1508) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1509) struct bfq_queue *bfq_get_next_queue(struct bfq_data *bfqd)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1510) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1511) struct bfq_entity *entity = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1512) struct bfq_sched_data *sd;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1513) struct bfq_queue *bfqq;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1514)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1515) if (bfq_tot_busy_queues(bfqd) == 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1516) return NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1517)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1518) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1519) * Traverse the path from the root to the leaf entity to
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1520) * serve. Set in service all the entities visited along the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1521) * way.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1522) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1523) sd = &bfqd->root_group->sched_data;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1524) for (; sd ; sd = entity->my_sched_data) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1525) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1526) * WARNING. We are about to set the in-service entity
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1527) * to sd->next_in_service, i.e., to the (cached) value
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1528) * returned by bfq_lookup_next_entity(sd) the last
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1529) * time it was invoked, i.e., the last time when the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1530) * service order in sd changed as a consequence of the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1531) * activation or deactivation of an entity. In this
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1532) * respect, if we execute bfq_lookup_next_entity(sd)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1533) * in this very moment, it may, although with low
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1534) * probability, yield a different entity than that
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1535) * pointed to by sd->next_in_service. This rare event
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1536) * happens in case there was no CLASS_IDLE entity to
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1537) * serve for sd when bfq_lookup_next_entity(sd) was
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1538) * invoked for the last time, while there is now one
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1539) * such entity.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1540) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1541) * If the above event happens, then the scheduling of
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1542) * such entity in CLASS_IDLE is postponed until the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1543) * service of the sd->next_in_service entity
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1544) * finishes. In fact, when the latter is expired,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1545) * bfq_lookup_next_entity(sd) gets called again,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1546) * exactly to update sd->next_in_service.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1547) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1548)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1549) /* Make next_in_service entity become in_service_entity */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1550) entity = sd->next_in_service;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1551) sd->in_service_entity = entity;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1552)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1553) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1554) * If entity is no longer a candidate for next
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1555) * service, then it must be extracted from its active
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1556) * tree, so as to make sure that it won't be
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1557) * considered when computing next_in_service. See the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1558) * comments on the function
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1559) * bfq_no_longer_next_in_service() for details.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1560) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1561) if (bfq_no_longer_next_in_service(entity))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1562) bfq_active_extract(bfq_entity_service_tree(entity),
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1563) entity);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1564)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1565) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1566) * Even if entity is not to be extracted according to
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1567) * the above check, a descendant entity may get
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1568) * extracted in one of the next iterations of this
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1569) * loop. Such an event could cause a change in
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1570) * next_in_service for the level of the descendant
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1571) * entity, and thus possibly back to this level.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1572) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1573) * However, we cannot perform the resulting needed
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1574) * update of next_in_service for this level before the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1575) * end of the whole loop, because, to know which is
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1576) * the correct next-to-serve candidate entity for each
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1577) * level, we need first to find the leaf entity to set
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1578) * in service. In fact, only after we know which is
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1579) * the next-to-serve leaf entity, we can discover
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1580) * whether the parent entity of the leaf entity
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1581) * becomes the next-to-serve, and so on.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1582) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1583) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1584)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1585) bfqq = bfq_entity_to_bfqq(entity);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1586)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1587) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1588) * We can finally update all next-to-serve entities along the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1589) * path from the leaf entity just set in service to the root.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1590) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1591) for_each_entity(entity) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1592) struct bfq_sched_data *sd = entity->sched_data;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1593)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1594) if (!bfq_update_next_in_service(sd, NULL, false))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1595) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1596) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1597)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1598) return bfqq;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1599) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1600)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1601) /* returns true if the in-service queue gets freed */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1602) bool __bfq_bfqd_reset_in_service(struct bfq_data *bfqd)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1603) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1604) struct bfq_queue *in_serv_bfqq = bfqd->in_service_queue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1605) struct bfq_entity *in_serv_entity = &in_serv_bfqq->entity;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1606) struct bfq_entity *entity = in_serv_entity;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1607)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1608) bfq_clear_bfqq_wait_request(in_serv_bfqq);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1609) hrtimer_try_to_cancel(&bfqd->idle_slice_timer);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1610) bfqd->in_service_queue = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1611)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1612) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1613) * When this function is called, all in-service entities have
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1614) * been properly deactivated or requeued, so we can safely
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1615) * execute the final step: reset in_service_entity along the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1616) * path from entity to the root.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1617) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1618) for_each_entity(entity)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1619) entity->sched_data->in_service_entity = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1620)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1621) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1622) * in_serv_entity is no longer in service, so, if it is in no
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1623) * service tree either, then release the service reference to
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1624) * the queue it represents (taken with bfq_get_entity).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1625) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1626) if (!in_serv_entity->on_st_or_in_serv) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1627) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1628) * If no process is referencing in_serv_bfqq any
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1629) * longer, then the service reference may be the only
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1630) * reference to the queue. If this is the case, then
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1631) * bfqq gets freed here.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1632) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1633) int ref = in_serv_bfqq->ref;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1634) bfq_put_queue(in_serv_bfqq);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1635) if (ref == 1)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1636) return true;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1637) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1638)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1639) return false;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1640) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1641)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1642) void bfq_deactivate_bfqq(struct bfq_data *bfqd, struct bfq_queue *bfqq,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1643) bool ins_into_idle_tree, bool expiration)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1644) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1645) struct bfq_entity *entity = &bfqq->entity;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1646)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1647) bfq_deactivate_entity(entity, ins_into_idle_tree, expiration);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1648) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1649)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1650) void bfq_activate_bfqq(struct bfq_data *bfqd, struct bfq_queue *bfqq)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1651) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1652) struct bfq_entity *entity = &bfqq->entity;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1653)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1654) bfq_activate_requeue_entity(entity, bfq_bfqq_non_blocking_wait_rq(bfqq),
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1655) false, false);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1656) bfq_clear_bfqq_non_blocking_wait_rq(bfqq);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1657) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1658)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1659) void bfq_requeue_bfqq(struct bfq_data *bfqd, struct bfq_queue *bfqq,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1660) bool expiration)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1661) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1662) struct bfq_entity *entity = &bfqq->entity;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1663)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1664) bfq_activate_requeue_entity(entity, false,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1665) bfqq == bfqd->in_service_queue, expiration);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1666) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1667)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1668) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1669) * Called when the bfqq no longer has requests pending, remove it from
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1670) * the service tree. As a special case, it can be invoked during an
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1671) * expiration.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1672) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1673) void bfq_del_bfqq_busy(struct bfq_data *bfqd, struct bfq_queue *bfqq,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1674) bool expiration)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1675) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1676) bfq_log_bfqq(bfqd, bfqq, "del from busy");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1677)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1678) bfq_clear_bfqq_busy(bfqq);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1679)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1680) bfqd->busy_queues[bfqq->ioprio_class - 1]--;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1681)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1682) if (bfqq->wr_coeff > 1)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1683) bfqd->wr_busy_queues--;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1684)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1685) bfqg_stats_update_dequeue(bfqq_group(bfqq));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1686)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1687) bfq_deactivate_bfqq(bfqd, bfqq, true, expiration);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1688)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1689) if (!bfqq->dispatched)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1690) bfq_weights_tree_remove(bfqd, bfqq);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1691) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1692)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1693) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1694) * Called when an inactive queue receives a new request.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1695) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1696) void bfq_add_bfqq_busy(struct bfq_data *bfqd, struct bfq_queue *bfqq)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1697) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1698) bfq_log_bfqq(bfqd, bfqq, "add to busy");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1699)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1700) bfq_activate_bfqq(bfqd, bfqq);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1701)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1702) bfq_mark_bfqq_busy(bfqq);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1703) bfqd->busy_queues[bfqq->ioprio_class - 1]++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1704)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1705) if (!bfqq->dispatched)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1706) if (bfqq->wr_coeff == 1)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1707) bfq_weights_tree_add(bfqd, bfqq,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1708) &bfqd->queue_weights_tree);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1709)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1710) if (bfqq->wr_coeff > 1)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1711) bfqd->wr_busy_queues++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1712) }
Orange Pi5 kernel
Deprecated Linux kernel 5.10.110 for OrangePi 5/5B/5+ boards
3 Commits
0 Branches
0 Tags