linux-imx

// SPDX-License-Identifier: GPL-2.0

/*

 *  Floating proportions with flexible aging period

 *

 *   Copyright (C) 2011, SUSE, Jan Kara <jack@suse.cz>

 *

 * The goal of this code is: Given different types of event, measure proportion

 * of each type of event over time. The proportions are measured with

 * exponentially decaying history to give smooth transitions. A formula

 * expressing proportion of event of type 'j' is:

 *

 *   p_{j} = (\Sum_{i>=0} x_{i,j}/2^{i+1})/(\Sum_{i>=0} x_i/2^{i+1})

 *

 * Where x_{i,j} is j's number of events in i-th last time period and x_i is

 * total number of events in i-th last time period.

 *

 * Note that p_{j}'s are normalised, i.e.

 *

 *   \Sum_{j} p_{j} = 1,

 *

 * This formula can be straightforwardly computed by maintaining denominator

 * (let's call it 'd') and for each event type its numerator (let's call it

 * 'n_j'). When an event of type 'j' happens, we simply need to do:

 *   n_j++; d++;

 *

 * When a new period is declared, we could do:

 *   d /= 2

 *   for each j

 *     n_j /= 2

 *

 * To avoid iteration over all event types, we instead shift numerator of event

 * j lazily when someone asks for a proportion of event j or when event j

 * occurs. This can bit trivially implemented by remembering last period in

 * which something happened with proportion of type j.

 */

#include <linux/flex_proportions.h>

​

int fprop_global_init(struct fprop_global *p, gfp_t gfp)

{

    int err;

​

    p->period = 0;

    /* Use 1 to avoid dealing with periods with 0 events... */

    err = percpu_counter_init(&p->events, 1, gfp);

    if (err)

        return err;

    seqcount_init(&p->sequence);

    return 0;

}

​

void fprop_global_destroy(struct fprop_global *p)

{

    percpu_counter_destroy(&p->events);

}

​

/*

 * Declare @periods new periods. It is upto the caller to make sure period

 * transitions cannot happen in parallel.

 *

 * The function returns true if the proportions are still defined and false

 * if aging zeroed out all events. This can be used to detect whether declaring

 * further periods has any effect.

 */

bool fprop_new_period(struct fprop_global *p, int periods)

{

    s64 events;

    unsigned long flags;

​

    local_irq_save(flags);

    events = percpu_counter_sum(&p->events);

    /*

     * Don't do anything if there are no events.

     */

    if (events <= 1) {

        local_irq_restore(flags);

        return false;

    }

    write_seqcount_begin(&p->sequence);

    if (periods < 64)

        events -= events >> periods;

    /* Use addition to avoid losing events happening between sum and set */

    percpu_counter_add(&p->events, -events);

    p->period += periods;

    write_seqcount_end(&p->sequence);

    local_irq_restore(flags);

​

    return true;

}

​

/*

 * ---- SINGLE ----

 */