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