linux-imx

// SPDX-License-Identifier: GPL-2.0-or-later

/*

 * 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).

 */

#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;

}

​

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);

}

​

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;

}

​

unsigned int bfq_tot_busy_queues(struct bfq_data *bfqd)

{

    return bfqd->busy_queues[0] + bfqd->busy_queues[1] +

        bfqd->busy_queues[2];

}

​

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 repositioning 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 repositioning 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.

     */