proportions.c

Go to the documentation of this file.

/*
 * Floating proportions
 *
 *  Copyright (C) 2007 Red Hat, Inc., Peter Zijlstra <[email protected]>
 *
 * Description:
 *
 * The floating proportion is a time derivative with an exponentially decaying
 * history:
 *
 *   p_{j} = \Sum_{i=0} (dx_{j}/dt_{-i}) / 2^(1+i)
 *
 * Where j is an element from {prop_local}, x_{j} is j's number of events,
 * and i the time period over which the differential is taken. So d/dt_{-i} is
 * the differential over the i-th last period.
 *
 * The decaying history gives smooth transitions. The time differential carries
 * the notion of speed.
 *
 * The denominator is 2^(1+i) because we want the series to be normalised, ie.
 *
 *   \Sum_{i=0} 1/2^(1+i) = 1
 *
 * Further more, if we measure time (t) in the same events as x; so that:
 *
 *   t = \Sum_{j} x_{j}
 *
 * we get that:
 *
 *   \Sum_{j} p_{j} = 1
 *
 * Writing this in an iterative fashion we get (dropping the 'd's):
 *
 *   if (++x_{j}, ++t > period)
 *     t /= 2;
 *     for_each (j)
 *       x_{j} /= 2;
 *
 * so that:
 *
 *   p_{j} = x_{j} / t;
 *
 * We optimize away the '/= 2' for the global time delta by noting that:
 *
 *   if (++t > period) t /= 2:
 *
 * Can be approximated by:
 *
 *   period/2 + (++t % period/2)
 *
 * [ Furthermore, when we choose period to be 2^n it can be written in terms of
 *   binary operations and wraparound artefacts disappear. ]
 *
 * Also note that this yields a natural counter of the elapsed periods:
 *
 *   c = t / (period/2)
 *
 * [ Its monotonic increasing property can be applied to mitigate the wrap-
 *   around issue. ]
 *
 * This allows us to do away with the loop over all prop_locals on each period
 * expiration. By remembering the period count under which it was last accessed
 * as c_{j}, we can obtain the number of 'missed' cycles from:
 *
 *   c - c_{j}
 *
 * We can then lazily catch up to the global period count every time we are
 * going to use x_{j}, by doing:
 *
 *   x_{j} /= 2^(c - c_{j}), c_{j} = c
 */

#include <linux/proportions.h>
#include <linux/rcupdate.h>

int prop_descriptor_init(struct prop_descriptor *pd, int shift)
{
    int err;

    if (shift > PROP_MAX_SHIFT)
        shift = PROP_MAX_SHIFT;

    pd->index = 0;
    pd->pg[0].shift = shift;
    mutex_init(&pd->mutex);
    err = percpu_counter_init(&pd->pg[0].events, 0);
    if (err)
        goto out;

    err = percpu_counter_init(&pd->pg[1].events, 0);
    if (err)
        percpu_counter_destroy(&pd->pg[0].events);

out:
    return err;
}

/*
 * We have two copies, and flip between them to make it seem like an atomic
 * update. The update is not really atomic wrt the events counter, but
 * it is internally consistent with the bit layout depending on shift.
 *
 * We copy the events count, move the bits around and flip the index.
 */
void prop_change_shift(struct prop_descriptor *pd, int shift)
{
    int index;
    int offset;
    u64 events;
    unsigned long flags;

    if (shift > PROP_MAX_SHIFT)
        shift = PROP_MAX_SHIFT;

    mutex_lock(&pd->mutex);

    index = pd->index ^ 1;
    offset = pd->pg[pd->index].shift - shift;
    if (!offset)
        goto out;

    pd->pg[index].shift = shift;

    local_irq_save(flags);
    events = percpu_counter_sum(&pd->pg[pd->index].events);
    if (offset < 0)
        events <<= -offset;
    else
        events >>= offset;
    percpu_counter_set(&pd->pg[index].events, events);

    /*
     * ensure the new pg is fully written before the switch
     */
    smp_wmb();
    pd->index = index;
    local_irq_restore(flags);

    synchronize_rcu();

out:
    mutex_unlock(&pd->mutex);
}

/*
 * wrap the access to the data in an rcu_read_lock() section;
 * this is used to track the active references.
 */
static struct prop_global *prop_get_global(struct prop_descriptor *pd)
__acquires(RCU)
{
    int index;

    rcu_read_lock();
    index = pd->index;
    /*
     * match the wmb from vcd_flip()
     */
    smp_rmb();
    return &pd->pg[index];
}

static void prop_put_global(struct prop_descriptor *pd, struct prop_global *pg)
__releases(RCU)
{
    rcu_read_unlock();
}

static void
prop_adjust_shift(int *pl_shift, unsigned long *pl_period, int new_shift)
{
    int offset = *pl_shift - new_shift;

    if (!offset)
        return;

    if (offset < 0)
        *pl_period <<= -offset;
    else
        *pl_period >>= offset;

    *pl_shift = new_shift;
}

/*
 * PERCPU
 */

#define PROP_BATCH (8*(1+ilog2(nr_cpu_ids)))

int prop_local_init_percpu(struct prop_local_percpu *pl)
{
    raw_spin_lock_init(&pl->lock);
    pl->shift = 0;
    pl->period = 0;
    return percpu_counter_init(&pl->events, 0);
}

void prop_local_destroy_percpu(struct prop_local_percpu *pl)
{
    percpu_counter_destroy(&pl->events);
}

/*
 * Catch up with missed period expirations.
 *
 *   until (c_{j} == c)
 *     x_{j} -= x_{j}/2;
 *     c_{j}++;
 */
static
void prop_norm_percpu(struct prop_global *pg, struct prop_local_percpu *pl)
{
    unsigned long period = 1UL << (pg->shift - 1);
    unsigned long period_mask = ~(period - 1);
    unsigned long global_period;
    unsigned long flags;

    global_period = percpu_counter_read(&pg->events);
    global_period &= period_mask;

    /*
     * Fast path - check if the local and global period count still match
     * outside of the lock.
     */
    if (pl->period == global_period)
        return;

    raw_spin_lock_irqsave(&pl->lock, flags);
    prop_adjust_shift(&pl->shift, &pl->period, pg->shift);

    /*
     * For each missed period, we half the local counter.
     * basically:
     *   pl->events >> (global_period - pl->period);
     */
    period = (global_period - pl->period) >> (pg->shift - 1);
    if (period < BITS_PER_LONG) {
        s64 val = percpu_counter_read(&pl->events);

        if (val < (nr_cpu_ids * PROP_BATCH))
            val = percpu_counter_sum(&pl->events);

        __percpu_counter_add(&pl->events, -val + (val >> period),
                    PROP_BATCH);
    } else
        percpu_counter_set(&pl->events, 0);

    pl->period = global_period;
    raw_spin_unlock_irqrestore(&pl->lock, flags);
}

/*
 *   ++x_{j}, ++t
 */
void __prop_inc_percpu(struct prop_descriptor *pd, struct prop_local_percpu *pl)
{
    struct prop_global *pg = prop_get_global(pd);

    prop_norm_percpu(pg, pl);
    __percpu_counter_add(&pl->events, 1, PROP_BATCH);
    percpu_counter_add(&pg->events, 1);
    prop_put_global(pd, pg);
}

/*
 * identical to __prop_inc_percpu, except that it limits this pl's fraction to
 * @frac/PROP_FRAC_BASE by ignoring events when this limit has been exceeded.
 */
void __prop_inc_percpu_max(struct prop_descriptor *pd,
               struct prop_local_percpu *pl, long frac)
{
    struct prop_global *pg = prop_get_global(pd);

    prop_norm_percpu(pg, pl);

    if (unlikely(frac != PROP_FRAC_BASE)) {
        unsigned long period_2 = 1UL << (pg->shift - 1);
        unsigned long counter_mask = period_2 - 1;
        unsigned long global_count;
        long numerator, denominator;

        numerator = percpu_counter_read_positive(&pl->events);
        global_count = percpu_counter_read(&pg->events);
        denominator = period_2 + (global_count & counter_mask);

        if (numerator > ((denominator * frac) >> PROP_FRAC_SHIFT))
            goto out_put;
    }

    percpu_counter_add(&pl->events, 1);
    percpu_counter_add(&pg->events, 1);

out_put:
    prop_put_global(pd, pg);
}

/*
 * Obtain a fraction of this proportion
 *
 *   p_{j} = x_{j} / (period/2 + t % period/2)
 */
void prop_fraction_percpu(struct prop_descriptor *pd,
        struct prop_local_percpu *pl,
        long *numerator, long *denominator)
{
    struct prop_global *pg = prop_get_global(pd);
    unsigned long period_2 = 1UL << (pg->shift - 1);
    unsigned long counter_mask = period_2 - 1;
    unsigned long global_count;

    prop_norm_percpu(pg, pl);
    *numerator = percpu_counter_read_positive(&pl->events);

    global_count = percpu_counter_read(&pg->events);
    *denominator = period_2 + (global_count & counter_mask);

    prop_put_global(pd, pg);
}

/*
 * SINGLE
 */

int prop_local_init_single(struct prop_local_single *pl)
{
    raw_spin_lock_init(&pl->lock);
    pl->shift = 0;
    pl->period = 0;
    pl->events = 0;
    return 0;
}

void prop_local_destroy_single(struct prop_local_single *pl)
{
}

/*
 * Catch up with missed period expirations.
 */
static
void prop_norm_single(struct prop_global *pg, struct prop_local_single *pl)
{
    unsigned long period = 1UL << (pg->shift - 1);
    unsigned long period_mask = ~(period - 1);
    unsigned long global_period;
    unsigned long flags;

    global_period = percpu_counter_read(&pg->events);
    global_period &= period_mask;

    /*
     * Fast path - check if the local and global period count still match
     * outside of the lock.
     */
    if (pl->period == global_period)
        return;

    raw_spin_lock_irqsave(&pl->lock, flags);
    prop_adjust_shift(&pl->shift, &pl->period, pg->shift);
    /*
     * For each missed period, we half the local counter.
     */
    period = (global_period - pl->period) >> (pg->shift - 1);
    if (likely(period < BITS_PER_LONG))
        pl->events >>= period;
    else
        pl->events = 0;
    pl->period = global_period;
    raw_spin_unlock_irqrestore(&pl->lock, flags);
}

/*
 *   ++x_{j}, ++t
 */
void __prop_inc_single(struct prop_descriptor *pd, struct prop_local_single *pl)
{
    struct prop_global *pg = prop_get_global(pd);

    prop_norm_single(pg, pl);
    pl->events++;
    percpu_counter_add(&pg->events, 1);
    prop_put_global(pd, pg);
}

/*
 * Obtain a fraction of this proportion
 *
 *   p_{j} = x_{j} / (period/2 + t % period/2)
 */
void prop_fraction_single(struct prop_descriptor *pd,
            struct prop_local_single *pl,
        long *numerator, long *denominator)
{
    struct prop_global *pg = prop_get_global(pd);
    unsigned long period_2 = 1UL << (pg->shift - 1);
    unsigned long counter_mask = period_2 - 1;
    unsigned long global_count;

    prop_norm_single(pg, pl);
    *numerator = pl->events;

    global_count = percpu_counter_read(&pg->events);
    *denominator = period_2 + (global_count & counter_mask);

    prop_put_global(pd, pg);
}