cregit-Linux how code gets into the kernel

Release 4.14 block/bfq-wf2q.c

Directory: block
/*
 * Hierarchical Budget Worst-case Fair Weighted Fair Queueing
 * (B-WF2Q+): hierarchical scheduling algorithm by which the BFQ I/O
 * scheduler schedules generic entities. The latter can represent
 * either single bfq queues (associated with processes) or groups of
 * bfq queues (associated with cgroups).
 *
 *  This program is free software; you can redistribute it and/or
 *  modify it under the terms of the GNU General Public License as
 *  published by the Free Software Foundation; either version 2 of the
 *  License, or (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 *  General Public License for more details.
 */
#include "bfq-iosched.h"

/**
 * bfq_gt - compare two timestamps.
 * @a: first ts.
 * @b: second ts.
 *
 * Return @a > @b, dealing with wrapping correctly.
 */

static int bfq_gt(u64 a, u64 b) { return (s64)(a - b) > 0; }

Contributors

PersonTokensPropCommitsCommitProp
Paolo Valente24100.00%1100.00%
Total24100.00%1100.00%


static struct bfq_entity *bfq_root_active_entity(struct rb_root *tree) { struct rb_node *node = tree->rb_node; return rb_entry(node, struct bfq_entity, rb_node); }

Contributors

PersonTokensPropCommitsCommitProp
Paolo Valente33100.00%1100.00%
Total33100.00%1100.00%


static unsigned int bfq_class_idx(struct bfq_entity *entity) { struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity); return bfqq ? bfqq->ioprio_class - 1 : BFQ_DEFAULT_GRP_CLASS - 1; }

Contributors

PersonTokensPropCommitsCommitProp
Paolo Valente35100.00%1100.00%
Total35100.00%1100.00%

static struct bfq_entity *bfq_lookup_next_entity(struct bfq_sched_data *sd, bool expiration); static bool bfq_update_parent_budget(struct bfq_entity *next_in_service); /** * bfq_update_next_in_service - update sd->next_in_service * @sd: sched_data for which to perform the update. * @new_entity: if not NULL, pointer to the entity whose activation, * requeueing or repositionig triggered the invocation of * this function. * @expiration: id true, this function is being invoked after the * expiration of the in-service entity * * This function is called to update sd->next_in_service, which, in * its turn, may change as a consequence of the insertion or * extraction of an entity into/from one of the active trees of * sd. These insertions/extractions occur as a consequence of * activations/deactivations of entities, with some activations being * 'true' activations, and other activations being requeueings (i.e., * implementing the second, requeueing phase of the mechanism used to * reposition an entity in its active tree; see comments on * __bfq_activate_entity and __bfq_requeue_entity for details). In * both the last two activation sub-cases, new_entity points to the * just activated or requeued entity. * * Returns true if sd->next_in_service changes in such a way that * entity->parent may become the next_in_service for its parent * entity. */
static bool bfq_update_next_in_service(struct bfq_sched_data *sd, struct bfq_entity *new_entity, bool expiration) { struct bfq_entity *next_in_service = sd->next_in_service; bool parent_sched_may_change = false; bool change_without_lookup = false; /* * If this update is triggered by the activation, requeueing * or repositiong of an entity that does not coincide with * sd->next_in_service, then a full lookup in the active tree * can be avoided. In fact, it is enough to check whether the * just-modified entity has the same priority as * sd->next_in_service, is eligible and has a lower virtual * finish time than sd->next_in_service. If this compound * condition holds, then the new entity becomes the new * next_in_service. Otherwise no change is needed. */ if (new_entity && new_entity != sd->next_in_service) { /* * Flag used to decide whether to replace * sd->next_in_service with new_entity. Tentatively * set to true, and left as true if * sd->next_in_service is NULL. */ change_without_lookup = true; /* * If there is already a next_in_service candidate * entity, then compare timestamps to decide whether * to replace sd->service_tree with new_entity. */ if (next_in_service) { unsigned int new_entity_class_idx = bfq_class_idx(new_entity); struct bfq_service_tree *st = sd->service_tree + new_entity_class_idx; change_without_lookup = (new_entity_class_idx == bfq_class_idx(next_in_service) && !bfq_gt(new_entity->start, st->vtime) && bfq_gt(next_in_service->finish, new_entity->finish)); } if (change_without_lookup) next_in_service = new_entity; } if (!change_without_lookup) /* lookup needed */ next_in_service = bfq_lookup_next_entity(sd, expiration); if (next_in_service) parent_sched_may_change = !sd->next_in_service || bfq_update_parent_budget(next_in_service); sd->next_in_service = next_in_service; if (!next_in_service) return parent_sched_may_change; return parent_sched_may_change; }

Contributors

PersonTokensPropCommitsCommitProp
Paolo Valente173100.00%4100.00%
Total173100.00%4100.00%

#ifdef CONFIG_BFQ_GROUP_IOSCHED
struct bfq_group *bfq_bfqq_to_bfqg(struct bfq_queue *bfqq) { struct bfq_entity *group_entity = bfqq->entity.parent; if (!group_entity) group_entity = &bfqq->bfqd->root_group->entity; return container_of(group_entity, struct bfq_group, entity); }

Contributors

PersonTokensPropCommitsCommitProp
Paolo Valente50100.00%1100.00%
Total50100.00%1100.00%

/* * Returns true if this budget changes may let next_in_service->parent * become the next_in_service entity for its parent entity. */
static bool bfq_update_parent_budget(struct bfq_entity *next_in_service) { struct bfq_entity *bfqg_entity; struct bfq_group *bfqg; struct bfq_sched_data *group_sd; bool ret = false; group_sd = next_in_service->sched_data; bfqg = container_of(group_sd, struct bfq_group, sched_data); /* * bfq_group's my_entity field is not NULL only if the group * is not the root group. We must not touch the root entity * as it must never become an in-service entity. */ bfqg_entity = bfqg->my_entity; if (bfqg_entity) { if (bfqg_entity->budget > next_in_service->budget) ret = true; bfqg_entity->budget = next_in_service->budget; } return ret; }

Contributors

PersonTokensPropCommitsCommitProp
Paolo Valente87100.00%1100.00%
Total87100.00%1100.00%

/* * This function tells whether entity stops being a candidate for next * service, according to the restrictive definition of the field * next_in_service. In particular, this function is invoked for an * entity that is about to be set in service. * * If entity is a queue, then the entity is no longer a candidate for * next service according to the that definition, because entity is * about to become the in-service queue. This function then returns * true if entity is a queue. * * In contrast, entity could still be a candidate for next service if * it is not a queue, and has more than one active child. In fact, * even if one of its children is about to be set in service, other * active children may still be the next to serve, for the parent * entity, even according to the above definition. As a consequence, a * non-queue entity is not a candidate for next-service only if it has * only one active child. And only if this condition holds, then this * function returns true for a non-queue entity. */
static bool bfq_no_longer_next_in_service(struct bfq_entity *entity) { struct bfq_group *bfqg; if (bfq_entity_to_bfqq(entity)) return true; bfqg = container_of(entity, struct bfq_group, entity); /* * The field active_entities does not always contain the * actual number of active children entities: it happens to * not account for the in-service entity in case the latter is * removed from its active tree (which may get done after * invoking the function bfq_no_longer_next_in_service in * bfq_get_next_queue). Fortunately, here, i.e., while * bfq_no_longer_next_in_service is not yet completed in * bfq_get_next_queue, bfq_active_extract has not yet been * invoked, and thus active_entities still coincides with the * actual number of active entities. */ if (bfqg->active_entities == 1) return true; return false; }

Contributors

PersonTokensPropCommitsCommitProp
Paolo Valente53100.00%2100.00%
Total53100.00%2100.00%

#else /* CONFIG_BFQ_GROUP_IOSCHED */
struct bfq_group *bfq_bfqq_to_bfqg(struct bfq_queue *bfqq) { return bfqq->bfqd->root_group; }

Contributors

PersonTokensPropCommitsCommitProp
Paolo Valente19100.00%1100.00%
Total19100.00%1100.00%


static bool bfq_update_parent_budget(struct bfq_entity *next_in_service) { return false; }

Contributors

PersonTokensPropCommitsCommitProp
Paolo Valente14100.00%1100.00%
Total14100.00%1100.00%


static bool bfq_no_longer_next_in_service(struct bfq_entity *entity) { return true; }

Contributors

PersonTokensPropCommitsCommitProp
Paolo Valente14100.00%1100.00%
Total14100.00%1100.00%

#endif /* CONFIG_BFQ_GROUP_IOSCHED */ /* * Shift for timestamp calculations. This actually limits the maximum * service allowed in one timestamp delta (small shift values increase it), * the maximum total weight that can be used for the queues in the system * (big shift values increase it), and the period of virtual time * wraparounds. */ #define WFQ_SERVICE_SHIFT 22
struct bfq_queue *bfq_entity_to_bfqq(struct bfq_entity *entity) { struct bfq_queue *bfqq = NULL; if (!entity->my_sched_data) bfqq = container_of(entity, struct bfq_queue, entity); return bfqq; }

Contributors

PersonTokensPropCommitsCommitProp
Paolo Valente41100.00%1100.00%
Total41100.00%1100.00%

/** * bfq_delta - map service into the virtual time domain. * @service: amount of service. * @weight: scale factor (weight of an entity or weight sum). */
static u64 bfq_delta(unsigned long service, unsigned long weight) { u64 d = (u64)service << WFQ_SERVICE_SHIFT; do_div(d, weight); return d; }

Contributors

PersonTokensPropCommitsCommitProp
Paolo Valente34100.00%1100.00%
Total34100.00%1100.00%

/** * bfq_calc_finish - assign the finish time to an entity. * @entity: the entity to act upon. * @service: the service to be charged to the entity. */
static void bfq_calc_finish(struct bfq_entity *entity, unsigned long service) { struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity); entity->finish = entity->start + bfq_delta(service, entity->weight); if (bfqq) { bfq_log_bfqq(bfqq->bfqd, bfqq, "calc_finish: serv %lu, w %d", service, entity->weight); bfq_log_bfqq(bfqq->bfqd, bfqq, "calc_finish: start %llu, finish %llu, delta %llu", entity->start, entity->finish, bfq_delta(service, entity->weight)); } }

Contributors

PersonTokensPropCommitsCommitProp
Paolo Valente93100.00%1100.00%
Total93100.00%1100.00%

/** * bfq_entity_of - get an entity from a node. * @node: the node field of the entity. * * Convert a node pointer to the relative entity. This is used only * to simplify the logic of some functions and not as the generic * conversion mechanism because, e.g., in the tree walking functions, * the check for a %NULL value would be redundant. */
struct bfq_entity *bfq_entity_of(struct rb_node *node) { struct bfq_entity *entity = NULL; if (node) entity = rb_entry(node, struct bfq_entity, rb_node); return entity; }

Contributors

PersonTokensPropCommitsCommitProp
Paolo Valente38100.00%1100.00%
Total38100.00%1100.00%

/** * bfq_extract - remove an entity from a tree. * @root: the tree root. * @entity: the entity to remove. */
static void bfq_extract(struct rb_root *root, struct bfq_entity *entity) { entity->tree = NULL; rb_erase(&entity->rb_node, root); }

Contributors

PersonTokensPropCommitsCommitProp
Paolo Valente32100.00%1100.00%
Total32100.00%1100.00%

/** * bfq_idle_extract - extract an entity from the idle tree. * @st: the service tree of the owning @entity. * @entity: the entity being removed. */
static void bfq_idle_extract(struct bfq_service_tree *st, struct bfq_entity *entity) { struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity); struct rb_node *next; if (entity == st->first_idle) { next = rb_next(&entity->rb_node); st->first_idle = bfq_entity_of(next); } if (entity == st->last_idle) { next = rb_prev(&entity->rb_node); st->last_idle = bfq_entity_of(next); } bfq_extract(&st->idle, entity); if (bfqq) list_del(&bfqq->bfqq_list); }

Contributors

PersonTokensPropCommitsCommitProp
Paolo Valente111100.00%1100.00%
Total111100.00%1100.00%

/** * bfq_insert - generic tree insertion. * @root: tree root. * @entity: entity to insert. * * This is used for the idle and the active tree, since they are both * ordered by finish time. */
static void bfq_insert(struct rb_root *root, struct bfq_entity *entity) { struct bfq_entity *entry; struct rb_node **node = &root->rb_node; struct rb_node *parent = NULL; while (*node) { parent = *node; entry = rb_entry(parent, struct bfq_entity, rb_node); if (bfq_gt(entry->finish, entity->finish)) node = &parent->rb_left; else node = &parent->rb_right; } rb_link_node(&entity->rb_node, parent, node); rb_insert_color(&entity->rb_node, root); entity->tree = root; }

Contributors

PersonTokensPropCommitsCommitProp
Paolo Valente119100.00%1100.00%
Total119100.00%1100.00%

/** * bfq_update_min - update the min_start field of a entity. * @entity: the entity to update. * @node: one of its children. * * This function is called when @entity may store an invalid value for * min_start due to updates to the active tree. The function assumes * that the subtree rooted at @node (which may be its left or its right * child) has a valid min_start value. */
static void bfq_update_min(struct bfq_entity *entity, struct rb_node *node) { struct bfq_entity *child; if (node) { child = rb_entry(node, struct bfq_entity, rb_node); if (bfq_gt(entity->min_start, child->min_start)) entity->min_start = child->min_start; } }

Contributors

PersonTokensPropCommitsCommitProp
Paolo Valente60100.00%1100.00%
Total60100.00%1100.00%

/** * bfq_update_active_node - recalculate min_start. * @node: the node to update. * * @node may have changed position or one of its children may have moved, * this function updates its min_start value. The left and right subtrees * are assumed to hold a correct min_start value. */
static void bfq_update_active_node(struct rb_node *node) { struct bfq_entity *entity = rb_entry(node, struct bfq_entity, rb_node); entity->min_start = entity->start; bfq_update_min(entity, node->rb_right); bfq_update_min(entity, node->rb_left); }

Contributors

PersonTokensPropCommitsCommitProp
Paolo Valente52100.00%1100.00%
Total52100.00%1100.00%

/** * bfq_update_active_tree - update min_start for the whole active tree. * @node: the starting node. * * @node must be the deepest modified node after an update. This function * updates its min_start using the values held by its children, assuming * that they did not change, and then updates all the nodes that may have * changed in the path to the root. The only nodes that may have changed * are the ones in the path or their siblings. */
static void bfq_update_active_tree(struct rb_node *node) { struct rb_node *parent; up: bfq_update_active_node(node); parent = rb_parent(node); if (!parent) return; if (node == parent->rb_left && parent->rb_right) bfq_update_active_node(parent->rb_right); else if (parent->rb_left) bfq_update_active_node(parent->rb_left); node = parent; goto up; }

Contributors

PersonTokensPropCommitsCommitProp
Paolo Valente76100.00%1100.00%
Total76100.00%1100.00%

/** * bfq_active_insert - insert an entity in the active tree of its * group/device. * @st: the service tree of the entity. * @entity: the entity being inserted. * * The active tree is ordered by finish time, but an extra key is kept * per each node, containing the minimum value for the start times of * its children (and the node itself), so it's possible to search for * the eligible node with the lowest finish time in logarithmic time. */
static void bfq_active_insert(struct bfq_service_tree *st, struct bfq_entity *entity) { struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity); struct rb_node *node = &entity->rb_node; #ifdef CONFIG_BFQ_GROUP_IOSCHED struct bfq_sched_data *sd = NULL; struct bfq_group *bfqg = NULL; struct bfq_data *bfqd = NULL; #endif bfq_insert(&st->active, entity); if (node->rb_left) node = node->rb_left; else if (node->rb_right) node = node->rb_right; bfq_update_active_tree(node); #ifdef CONFIG_BFQ_GROUP_IOSCHED sd = entity->sched_data; bfqg = container_of(sd, struct bfq_group, sched_data); bfqd = (struct bfq_data *)bfqg->bfqd; #endif if (bfqq) list_add(&bfqq->bfqq_list, &bfqq->bfqd->active_list); #ifdef CONFIG_BFQ_GROUP_IOSCHED else /* bfq_group */ bfq_weights_tree_add(bfqd, entity, &bfqd->group_weights_tree); if (bfqg != bfqd->root_group) bfqg->active_entities++; #endif }

Contributors

PersonTokensPropCommitsCommitProp
Paolo Valente187100.00%1100.00%
Total187100.00%1100.00%

/** * bfq_ioprio_to_weight - calc a weight from an ioprio. * @ioprio: the ioprio value to convert. */
unsigned short bfq_ioprio_to_weight(int ioprio) { return (IOPRIO_BE_NR - ioprio) * BFQ_WEIGHT_CONVERSION_COEFF; }

Contributors

PersonTokensPropCommitsCommitProp
Paolo Valente18100.00%1100.00%
Total18100.00%1100.00%

/** * bfq_weight_to_ioprio - calc an ioprio from a weight. * @weight: the weight value to convert. * * To preserve as much as possible the old only-ioprio user interface, * 0 is used as an escape ioprio value for weights (numerically) equal or * larger than IOPRIO_BE_NR * BFQ_WEIGHT_CONVERSION_COEFF. */
static unsigned short bfq_weight_to_ioprio(int weight) { return max_t(int, 0, IOPRIO_BE_NR * BFQ_WEIGHT_CONVERSION_COEFF - weight); }

Contributors

PersonTokensPropCommitsCommitProp
Paolo Valente24100.00%1100.00%
Total24100.00%1100.00%


static void bfq_get_entity(struct bfq_entity *entity) { struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity); if (bfqq) { bfqq->ref++; bfq_log_bfqq(bfqq->bfqd, bfqq, "get_entity: %p %d", bfqq, bfqq->ref); } }

Contributors

PersonTokensPropCommitsCommitProp
Paolo Valente49100.00%1100.00%
Total49100.00%1100.00%

/** * bfq_find_deepest - find the deepest node that an extraction can modify. * @node: the node being removed. * * Do the first step of an extraction in an rb tree, looking for the * node that will replace @node, and returning the deepest node that * the following modifications to the tree can touch. If @node is the * last node in the tree return %NULL. */
static struct rb_node *bfq_find_deepest(struct rb_node *node) { struct rb_node *deepest; if (!node->rb_right && !node->rb_left) deepest = rb_parent(node); else if (!node->rb_right) deepest = node->rb_left; else if (!node->rb_left) deepest = node->rb_right; else { deepest = rb_next(node); if (deepest->rb_right) deepest = deepest->rb_right; else if (rb_parent(deepest) != node) deepest = rb_parent(deepest); } return deepest; }

Contributors

PersonTokensPropCommitsCommitProp
Paolo Valente107100.00%1100.00%
Total107100.00%1100.00%

/** * bfq_active_extract - remove an entity from the active tree. * @st: the service_tree containing the tree. * @entity: the entity being removed. */
static void bfq_active_extract(struct bfq_service_tree *st, struct bfq_entity *entity) { struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity); struct rb_node *node; #ifdef CONFIG_BFQ_GROUP_IOSCHED struct bfq_sched_data *sd = NULL; struct bfq_group *bfqg = NULL; struct bfq_data *bfqd = NULL; #endif node = bfq_find_deepest(&entity->rb_node); bfq_extract(&st->active, entity); if (node) bfq_update_active_tree(node); #ifdef CONFIG_BFQ_GROUP_IOSCHED sd = entity->sched_data; bfqg = container_of(sd, struct bfq_group, sched_data); bfqd = (struct bfq_data *)bfqg->bfqd; #endif if (bfqq) list_del(&bfqq->bfqq_list); #ifdef CONFIG_BFQ_GROUP_IOSCHED else /* bfq_group */ bfq_weights_tree_remove(bfqd, entity, &bfqd->group_weights_tree); if (bfqg != bfqd->root_group) bfqg->active_entities--; #endif }

Contributors

PersonTokensPropCommitsCommitProp
Paolo Valente164100.00%1100.00%
Total164100.00%1100.00%

/** * bfq_idle_insert - insert an entity into the idle tree. * @st: the service tree containing the tree. * @entity: the entity to insert. */
static void bfq_idle_insert(struct bfq_service_tree *st, struct bfq_entity *entity) { struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity); struct bfq_entity *first_idle = st->first_idle; struct bfq_entity *last_idle = st->last_idle; if (!first_idle || bfq_gt(first_idle->finish, entity->finish)) st->first_idle = entity; if (!last_idle || bfq_gt(entity->finish, last_idle->finish)) st->last_idle = entity; bfq_insert(&st->idle, entity); if (bfqq) list_add(&bfqq->bfqq_list, &bfqq->bfqd->idle_list); }

Contributors

PersonTokensPropCommitsCommitProp
Paolo Valente117100.00%1100.00%
Total117100.00%1100.00%

/** * bfq_forget_entity - do not consider entity any longer for scheduling * @st: the service tree. * @entity: the entity being removed. * @is_in_service: true if entity is currently the in-service entity. * * Forget everything about @entity. In addition, if entity represents * a queue, and the latter is not in service, then release the service * reference to the queue (the one taken through bfq_get_entity). In * fact, in this case, there is really no more service reference to * the queue, as the latter is also outside any service tree. If, * instead, the queue is in service, then __bfq_bfqd_reset_in_service * will take care of putting the reference when the queue finally * stops being served. */
static void bfq_forget_entity(struct bfq_service_tree *st, struct bfq_entity *entity, bool is_in_service) { struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity); entity->on_st = false; st->wsum -= entity->weight; if (bfqq && !is_in_service) bfq_put_queue(bfqq); }

Contributors

PersonTokensPropCommitsCommitProp
Paolo Valente55100.00%1100.00%
Total55100.00%1100.00%

/** * bfq_put_idle_entity - release the idle tree ref of an entity. * @st: service tree for the entity. * @entity: the entity being released. */
void bfq_put_idle_entity(struct bfq_service_tree *st, struct bfq_entity *entity) { bfq_idle_extract(st, entity); bfq_forget_entity(st, entity, entity == entity->sched_data->in_service_entity); }

Contributors

PersonTokensPropCommitsCommitProp
Paolo Valente37100.00%1100.00%
Total37100.00%1100.00%

/** * bfq_forget_idle - update the idle tree if necessary. * @st: the service tree to act upon. * * To preserve the global O(log N) complexity we only remove one entry here; * as the idle tree will not grow indefinitely this can be done safely. */
static void bfq_forget_idle(struct bfq_service_tree *st) { struct bfq_entity *first_idle = st->first_idle; struct bfq_entity *last_idle = st->last_idle; if (RB_EMPTY_ROOT(&st->active) && last_idle && !bfq_gt(last_idle->finish, st->vtime)) { /* * Forget the whole idle tree, increasing the vtime past * the last finish time of idle entities. */ st->vtime = last_idle->finish; } if (first_idle && !bfq_gt(first_idle->finish, st->vtime)) bfq_put_idle_entity(st, first_idle); }

Contributors

PersonTokensPropCommitsCommitProp
Paolo Valente87100.00%1100.00%
Total87100.00%1100.00%


struct bfq_service_tree *bfq_entity_service_tree(struct bfq_entity *entity) { struct bfq_sched_data *sched_data = entity->sched_data; unsigned int idx = bfq_class_idx(entity); return sched_data->service_tree + idx; }

Contributors

PersonTokensPropCommitsCommitProp
Paolo Valente37100.00%1100.00%
Total37100.00%1100.00%

/* * Update weight and priority of entity. If update_class_too is true, * then update the ioprio_class of entity too. * * The reason why the update of ioprio_class is controlled through the * last parameter is as follows. Changing the ioprio class of an * entity implies changing the destination service trees for that * entity. If such a change occurred when the entity is already on one * of the service trees for its previous class, then the state of the * entity would become more complex: none of the new possible service * trees for the entity, according to bfq_entity_service_tree(), would * match any of the possible service trees on which the entity * is. Complex operations involving these trees, such as entity * activations and deactivations, should take into account this * additional complexity. To avoid this issue, this function is * invoked with update_class_too unset in the points in the code where * entity may happen to be on some tree. */
struct bfq_service_tree * __bfq_entity_update_weight_prio(struct bfq_service_tree *old_st, struct bfq_entity *entity, bool update_class_too) { struct bfq_service_tree *new_st = old_st; if (entity->prio_changed) { struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity); unsigned int prev_weight, new_weight; struct bfq_data *bfqd = NULL; struct rb_root *root; #ifdef CONFIG_BFQ_GROUP_IOSCHED struct bfq_sched_data *sd; struct bfq_group *bfqg; #endif if (bfqq) bfqd = bfqq->bfqd; #ifdef CONFIG_BFQ_GROUP_IOSCHED else { sd = entity->my_sched_data; bfqg = container_of(sd, struct bfq_group, sched_data); bfqd = (struct bfq_data *)bfqg->bfqd; } #endif old_st->wsum -= entity->weight; if (entity->new_weight != entity->orig_weight) { if (entity->new_weight < BFQ_MIN_WEIGHT || entity->new_weight > BFQ_MAX_WEIGHT) { pr_crit("update_weight_prio: new_weight %d\n", entity->new_weight); if (entity->new_weight < BFQ_MIN_WEIGHT) entity->new_weight = BFQ_MIN_WEIGHT; else entity->new_weight = BFQ_MAX_WEIGHT; } entity->orig_weight = entity->new_weight; if (bfqq) bfqq->ioprio = bfq_weight_to_ioprio(entity->orig_weight); } if (bfqq && update_class_too) bfqq->ioprio_class = bfqq->new_ioprio_class; /* * Reset prio_changed only if the ioprio_class change * is not pending any longer. */ if (!bfqq || bfqq->ioprio_class == bfqq->new_ioprio_class) entity->prio_changed = 0; /* * NOTE: here we may be changing the weight too early, * this will cause unfairness. The correct approach * would have required additional complexity to defer * weight changes to the proper time instants (i.e., * when entity->finish <= old_st->vtime). */ new_st = bfq_entity_service_tree(entity); prev_weight = entity->weight; new_weight = entity->orig_weight * (bfqq ? bfqq->wr_coeff : 1); /* * If the weight of the entity changes, remove the entity * from its old weight counter (if there is a counter * associated with the entity), and add it to the counter * associated with its new weight. */ if (prev_weight != new_weight) { root = bfqq ? &bfqd->queue_weights_tree : &bfqd->group_weights_tree; bfq_weights_tree_remove(bfqd, entity, root); } entity->weight = new_weight; /* * Add the entity to its weights tree only if it is * not associated with a weight-raised queue. */ if (prev_weight != new_weight && (bfqq ? bfqq->wr_coeff == 1 : 1)) /* If we get here, root has been initialized. */ bfq_weights_tree_add(bfqd, entity, root); new_st->wsum += entity->weight; if (new_st != old_st) entity->start = new_st->vtime; } return new_st; }

Contributors

PersonTokensPropCommitsCommitProp
Paolo Valente370100.00%2100.00%
Total370100.00%2100.00%

/** * bfq_bfqq_served - update the scheduler status after selection for * service. * @bfqq: the queue being served. * @served: bytes to transfer. * * NOTE: this can be optimized, as the timestamps of upper level entities * are synchronized every time a new bfqq is selected for service. By now, * we keep it to better check consistency. */
void bfq_bfqq_served(struct bfq_queue *bfqq, int served) { struct bfq_entity *entity = &bfqq->entity; struct bfq_service_tree *st; for_each_entity(entity) { st = bfq_entity_service_tree(entity); entity->service += served; st->vtime += bfq_delta(served, st->wsum); bfq_forget_idle(st); } bfqg_stats_set_start_empty_time(bfqq_group(bfqq)); bfq_log_bfqq(bfqq->bfqd, bfqq, "bfqq_served %d secs", served); }

Contributors

PersonTokensPropCommitsCommitProp
Paolo Valente86100.00%1100.00%
Total86100.00%1100.00%

/** * bfq_bfqq_charge_time - charge an amount of service equivalent to the length * of the time interval during which bfqq has been in * service. * @bfqd: the device * @bfqq: the queue that needs a service update. * @time_ms: the amount of time during which the queue has received service * * If a queue does not consume its budget fast enough, then providing * the queue with service fairness may impair throughput, more or less * severely. For this reason, queues that consume their budget slowly * are provided with time fairness instead of service fairness. This * goal is achieved through the BFQ scheduling engine, even if such an * engine works in the service, and not in the time domain. The trick * is charging these queues with an inflated amount of service, equal * to the amount of service that they would have received during their * service slot if they had been fast, i.e., if their requests had * been dispatched at a rate equal to the estimated peak rate. * * It is worth noting that time fairness can cause important * distortions in terms of bandwidth distribution, on devices with * internal queueing. The reason is that I/O requests dispatched * during the service slot of a queue may be served after that service * slot is finished, and may have a total processing time loosely * correlated with the duration of the service slot. This is * especially true for short service slots. */
void bfq_bfqq_charge_time(struct bfq_data *bfqd, struct bfq_queue *bfqq, unsigned long time_ms) { struct bfq_entity *entity = &bfqq->entity; int tot_serv_to_charge = entity->service; unsigned int timeout_ms = jiffies_to_msecs(bfq_timeout); if (time_ms > 0 && time_ms < timeout_ms) tot_serv_to_charge = (bfqd->bfq_max_budget * time_ms) / timeout_ms; if (tot_serv_to_charge < entity->service) tot_serv_to_charge = entity->service; /* Increase budget to avoid inconsistencies */ if (tot_serv_to_charge > entity->budget) entity->budget = tot_serv_to_charge; bfq_bfqq_served(bfqq, max_t(int, 0, tot_serv_to_charge - entity->service)); }

Contributors

PersonTokensPropCommitsCommitProp
Paolo Valente114100.00%1100.00%
Total114100.00%1100.00%


static void bfq_update_fin_time_enqueue(struct bfq_entity *entity, struct bfq_service_tree *st, bool backshifted) { struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity); /* * When this function is invoked, entity is not in any service * tree, then it is safe to invoke next function with the last * parameter set (see the comments on the function). */ st = __bfq_entity_update_weight_prio(st, entity, true); bfq_calc_finish(entity, entity->budget); /* * If some queues enjoy backshifting for a while, then their * (virtual) finish timestamps may happen to become lower and * lower than the system virtual time. In particular, if * these queues often happen to be idle for short time * periods, and during such time periods other queues with * higher timestamps happen to be busy, then the backshifted * timestamps of the former queues can become much lower than * the system virtual time. In fact, to serve the queues with * higher timestamps while the ones with lower timestamps are * idle, the system virtual time may be pushed-up to much * higher values than the finish timestamps of the idle * queues. As a consequence, the finish timestamps of all new * or newly activated queues may end up being much larger than * those of lucky queues with backshifted timestamps. The * latter queues may then monopolize the device for a lot of * time. This would simply break service guarantees. * * To reduce this problem, push up a little bit the * backshifted timestamps of the queue associated with this * entity (only a queue can happen to have the backshifted * flag set): just enough to let the finish timestamp of the * queue be equal to the current value of the system virtual * time. This may introduce a little unfairness among queues * with backshifted timestamps, but it does not break * worst-case fairness guarantees. * * As a special case, if bfqq is weight-raised, push up * timestamps much less, to keep very low the probability that * this push up causes the backshifted finish timestamps of * weight-raised queues to become higher than the backshifted * finish timestamps of non weight-raised queues. */ if (backshifted && bfq_gt(st->vtime, entity->finish)) { unsigned long delta = st->vtime - entity->finish; if (bfqq) delta /= bfqq->wr_coeff; entity->start += delta; entity->finish += delta; } bfq_active_insert(st, entity); }

Contributors

PersonTokensPropCommitsCommitProp
Paolo Valente109100.00%2100.00%
Total109100.00%2100.00%

/** * __bfq_activate_entity - handle activation of entity. * @entity: the entity being activated. * @non_blocking_wait_rq: true if entity was waiting for a request * * Called for a 'true' activation, i.e., if entity is not active and * one of its children receives a new request. * * Basically, this function updates the timestamps of entity and * inserts entity into its active tree, ater possibly extracting it * from its idle tree. */
static void __bfq_activate_entity(struct bfq_entity *entity, bool non_blocking_wait_rq) { struct bfq_service_tree *st = bfq_entity_service_tree(entity); bool backshifted = false; unsigned long long min_vstart; /* See comments on bfq_fqq_update_budg_for_activation */ if (non_blocking_wait_rq && bfq_gt(st->vtime, entity->finish)) { backshifted = true; min_vstart = entity->finish; } else min_vstart = st->vtime; if (