tokenbucket.hh

Go to the documentation of this file.

// -*- c-basic-offset: 4 -*-
#ifndef CLICK_TOKENBUCKET_HH
#define CLICK_TOKENBUCKET_HH
#include <click/timestamp.hh>
#include <click/bigint.hh>
CLICK_DECLS
 
template <typename P> class TokenRateX;
 
template <typename P>
class TokenRateX : public P { public:
 
    typedef P parameter_type;
 
    typedef typename P::token_type token_type;
 
    typedef typename P::time_point_type time_point_type;
 
    typedef typename make_unsigned<typename P::duration_type>::type ticks_type;
 
    enum {
        max_tokens = (token_type) -1
    };
 
    TokenRateX() {
        assign();
    }
 
    explicit TokenRateX(bool unlimited) {
        assign(unlimited);
    }
 
    TokenRateX(token_type rate, token_type capacity) {
        assign(rate, capacity);
    }
 
    inline void assign(bool unlimited = false);
 
    inline void assign(token_type rate, token_type capacity);
 
    bool unlimited() const {
        return _time_until_full == 0;
    }
 
    bool idle() const {
        return _tokens_per_tick == 0;
    }
 
    token_type rate() const;
 
    token_type capacity() const {
        return max_tokens / _token_scale;
    }
 
    token_type tokens_per_tick() const {
        return _tokens_per_tick;
    }
 
    token_type token_scale() const {
        return _token_scale;
    }
 
    ticks_type time_until_full() const {
        return _time_until_full;
    }
 
    time_point_type now() const {
        return P::now();
    }
 
    template <typename U>
    time_point_type time_point(U time) const {
        return P::time_point(time);
    }
 
    ticks_type time_monotonic_difference(time_point_type a, time_point_type b) const {
        return P::time_monotonic_difference(a, b);
    }
 
 
    typedef time_point_type epoch_type CLICK_DEPRECATED;
    inline token_type tokens_per_epoch() const CLICK_DEPRECATED;
    inline ticks_type epochs_until_full() const CLICK_DEPRECATED;
 private:
 
    token_type _tokens_per_tick;        // 0 iff idle()
    token_type _token_scale;
    ticks_type _time_until_full;        // 0 iff unlimited()
 
};
 
template <typename P>
void TokenRateX<P>::assign(bool unlimited)
{
    _token_scale = 1;
    if (unlimited) {
        _tokens_per_tick = max_tokens;
        _time_until_full = 0;
    } else {
        _tokens_per_tick = 0;
        _time_until_full = (ticks_type) -1;
    }
}
 
template <typename P>
void TokenRateX<P>::assign(token_type rate, token_type capacity)
{
    if (capacity == 0) {
        rate = 0;
        capacity = max_tokens;
    }
 
    token_type frequency = P::frequency();
    if (rate != 0) {
        // constrain capacity so _tokens_per_tick fits in 1 limb
        unsigned long long min_capacity = (rate - 1) / frequency + 1;
        if (capacity < min_capacity)
            capacity = min_capacity;
    }
    _token_scale = max_tokens / capacity;
 
    // XXX on non-64 bit types
    static_assert(sizeof(bigint::limb_type) == sizeof(token_type),
                  "bigint::limb_type should have the same size as token_type.");
    bigint::limb_type l[2] = { 0, 0 };
    bigint::limb_type a[2] = { rate, 0 };
    bigint::multiply_add(l, a, 2, _token_scale);
    (void) bigint::divide(l, l, 2, frequency);
    assert(l[1] == 0);
 
    if (rate != 0) {
        // constrain _tokens_per_tick to be at least 1
        _tokens_per_tick = (l[0] != 0 ? l[0] : 1);
        _time_until_full = (max_tokens - 1) / _tokens_per_tick + 1;
    } else {
        _tokens_per_tick = 0;
        _time_until_full = (ticks_type) -1;
    }
}
 
template <typename P>
typename P::token_type TokenRateX<P>::rate() const
{
    static_assert(sizeof(bigint::limb_type) == sizeof(token_type),
                  "bigint::limb_type should have the same size as token_type.");
    bigint::limb_type l[2] = { _tokens_per_tick / 2, 0 };
    bigint::limb_type a[2] = { _tokens_per_tick, 0 };
    bigint::multiply_add(l, a, 2, P::frequency());
    (void) bigint::divide(l, l, 2, token_scale());
    return l[1] ? (token_type) max_tokens : l[0];
}
 
template <typename P>
inline typename TokenRateX<P>::token_type TokenRateX<P>::tokens_per_epoch() const
{
    return tokens_per_tick();
}
 
template <typename P>
inline typename TokenRateX<P>::ticks_type TokenRateX<P>::epochs_until_full() const
{
    return time_until_full();
}
/* TokenRateConverter safely scales token counts according to an input rate.
   Template specializations let us make use of a fast int_multiply() when one
   is available. */
template<typename rate_type, bool FM> struct TokenRateConverter {
};
template<typename rate_type> struct TokenRateConverter<rate_type, true> {
    static bool cvt(const rate_type &rate, typename rate_type::token_type &t) {
        typename rate_type::token_type high;
        int_multiply(t, rate.token_scale(), t, high);
        if (high)
            t = rate_type::max_tokens;
        return !high;
    }
};
template<typename rate_type> struct TokenRateConverter<rate_type, false> {
    static bool cvt(const rate_type &rate, typename rate_type::token_type &t) {
        if (t <= rate.capacity()) {
            t *= rate.token_scale();
            return true;
        } else {
            t = rate_type::max_tokens;
            return false;
        }
    }
};
template <typename R>
class TokenCounterX { public:
 
    typedef R rate_type;
 
    typedef typename R::token_type token_type;
 
    typedef typename R::time_point_type time_point_type;
 
    typedef typename R::ticks_type ticks_type;
 
    enum {
        max_tokens = R::max_tokens
    };
 
    TokenCounterX()
        : _tokens(0), _time_point() {
    }
 
    explicit TokenCounterX(bool full)
        : _tokens(full ? (token_type) max_tokens : 0), _time_point() {
    }
 
    token_type size(const rate_type &rate) const {
        return _tokens / rate.token_scale();
    }
 
    token_type fraction() const {
        return _tokens;
    }
 
    bool empty() const {
        return _tokens == 0;
    }
 
    bool full() const {
        return _tokens == (token_type) max_tokens;
    }
 
    bool contains(const rate_type &rate, token_type t) const {
        return cvt_type::cvt(rate, t) && contains_fraction(t);
    }
 
    bool contains_fraction(token_type f) const {
        return f <= _tokens;
    }
 
    void clear() {
        _tokens = 0;
    }
 
    void set_full() {
        _tokens = max_tokens;
    }
 
    void set(const rate_type &rate, token_type t) {
        (void) cvt_type::cvt(rate, t);
        _tokens = t;
    }
 
    void set_fraction(token_type f) {
        _tokens = f;
    }
 
    void adjust(const rate_type &old_rate, const rate_type &new_rate) {
        if (old_rate.token_scale() != new_rate.token_scale()) {
            static_assert(sizeof(bigint::limb_type) == sizeof(token_type),
                          "bigint::limb_type should have the same size as token_type.");
            bigint::limb_type l[2] = { 0, 0 };
            bigint::limb_type a[2] = { _tokens, 0 };
            bigint::multiply_add(l, a, 2, new_rate.token_scale());
            (void) bigint::divide(l, l, 2, old_rate.token_scale());
            _tokens = l[1] ? (token_type) max_tokens : l[0];
        }
    }
 
    void refill(const rate_type &rate);
 
    void refill(const rate_type &rate, time_point_type time);
 
    template <typename U> void refill(const rate_type &rate, U time);
 
    void set_time_point(time_point_type time) {
        _time_point = time;
    }
 
    time_point_type time_point() {
            return _time_point;
    }
 
    void remove(const rate_type &rate, token_type t) {
        (void) cvt_type::cvt(rate, t);
        remove_fraction(t);
    }
 
    bool remove_if(const rate_type &rate, token_type t) {
        return cvt_type::cvt(rate, t) && remove_fraction_if(t);
    }
 
    void remove_fraction(token_type f) {
        _tokens = (f <= _tokens ? _tokens - f : 0);
    }
 
    bool remove_fraction_if(token_type f) {
        if (f <= _tokens) {
            _tokens -= f;
            return true;
        } else
            return false;
    }
 
    ticks_type time_until_contains(const rate_type &rate,
                                   token_type t) const {
        if (cvt_type::cvt(rate, t))
            return time_until_contains_fraction(rate, t);
        else
            return (ticks_type) -1;
    }
 
    ticks_type time_until_contains_fraction(const rate_type &rate,
                                            token_type f) const {
        if (f <= _tokens || rate.time_until_full() == 0)
            return 0;
        else if (rate.tokens_per_tick() == 0)
            return (ticks_type) -1;
        else
            return (f - _tokens - 1) / rate.tokens_per_tick() + 1;
    }
 
 
    inline ticks_type epochs_until_contains(const rate_type &rate, token_type t) const CLICK_DEPRECATED;
    inline ticks_type epochs_until_contains_fraction(const rate_type &rate, token_type f) const CLICK_DEPRECATED;
  private:
 
    token_type _tokens;
    time_point_type _time_point;
 
    typedef TokenRateConverter<rate_type, has_fast_int_multiply<token_type>::value> cvt_type;
 
};
 
template <typename R>
void TokenCounterX<R>::refill(const rate_type &rate, time_point_type time)
{
    ticks_type diff = rate.time_monotonic_difference(_time_point, time);
    if (diff >= rate.time_until_full()) {
        // ignore special case of idle rates -- we assume that
        // rate.time_monotonic_difference() will never return (ticks_type) -1,
        // and ensure that ticks_type is unsigned
        _tokens = max_tokens;
    } else if (diff > 0) {
        token_type new_tokens = _tokens + diff * rate.tokens_per_tick();
        _tokens = (new_tokens < _tokens ? (token_type) max_tokens : new_tokens);
    }
    _time_point = time;
}
 
template <typename R>
void TokenCounterX<R>::refill(const rate_type &rate)
{
    refill(rate, rate.now());
}
 
template <typename R> template <typename U>
void TokenCounterX<R>::refill(const rate_type &rate, U time)
{
    refill(rate, rate.time_point(time));
}
 
template <typename R>
inline typename TokenCounterX<R>::ticks_type TokenCounterX<R>::epochs_until_contains(const rate_type &rate, token_type t) const
{
    return time_until_contains(rate, t);
}
template <typename R>
inline typename TokenCounterX<R>::ticks_type TokenCounterX<R>::epochs_until_contains_fraction(const rate_type &rate, token_type f) const
{
    return time_until_contains_fraction(rate, f);
}
template <typename T>
class TokenBucketJiffyParameters { public:
 
    typedef T token_type;
 
    typedef click_jiffies_t time_point_type;
 
    typedef click_jiffies_difference_t duration_type;
 
    static time_point_type now() {
        return click_jiffies();
    }
 
    static time_point_type time_point(time_point_type t) {
        return t;
    }
 
    static duration_type time_monotonic_difference(time_point_type a, time_point_type b) {
#if CLICK_JIFFIES_MONOTONIC
        return b - a;
#else
        return (likely(a <= b) ? b - a : 0);
#endif
    }
 
    static bool time_less(time_point_type a, time_point_type b) {
        return click_jiffies_less(a, b);
    }
 
    static unsigned frequency() {
        return CLICK_HZ;
    }
 
    static Timestamp timestamp(time_point_type x) {
        return Timestamp::make_jiffies(x);
    }
 
    static Timestamp timestamp(duration_type x) {
        return Timestamp::make_jiffies(x);
    }
 
};
 
template <typename T>
class TokenBucketUsecParameters { public:
 
    typedef T token_type;
 
    typedef click_uintmax_t time_point_type;
 
    typedef click_intmax_t duration_type;
 
    static time_point_type now() {
        return Timestamp::now_steady().usecval();
    }
 
    static time_point_type time_point(time_point_type t) {
        return t;
    }
 
    static duration_type time_monotonic_difference(time_point_type a, time_point_type b) {
        return (likely(a <= b) ? b - a : 0);
    }
 
    static bool time_less(time_point_type a, time_point_type b) {
        return (duration_type) (a - b) < 0;
    }
 
    static unsigned frequency() {
        return 1000000;
    }
 
    static Timestamp timestamp(time_point_type x) {
        return Timestamp::make_usec(x);
    }
 
    static Timestamp timestamp(duration_type x) {
        return Timestamp::make_usec(x);
    }
 
};
 
template <typename P>
class TokenBucketX { public:
 
    typedef P parameter_type;
 
    typedef TokenRateX<P> rate_type;
 
    typedef TokenCounterX<rate_type> counter_type;
 
    typedef typename rate_type::token_type token_type;
 
    typedef typename rate_type::time_point_type time_point_type;
 
    typedef typename rate_type::ticks_type ticks_type;
 
    enum {
        max_tokens = rate_type::max_tokens
    };
 
    TokenBucketX() {
    }
 
    explicit TokenBucketX(bool unlimited)
        : _rate(unlimited), _bucket(unlimited) {
    }
 
    TokenBucketX(token_type rate, token_type capacity)
        : _rate(rate, capacity), _bucket(rate != 0 && capacity != 0) {
    }
 
    void assign(bool unlimited = false) {
        _rate.assign(unlimited);
    }
 
    void assign(token_type rate, token_type capacity) {
        _rate.assign(rate, capacity);
    }
 
    void assign_adjust(token_type rate, token_type capacity) {
        rate_type old_rate(_rate);
        _rate.assign(rate, capacity);
        _bucket.adjust(old_rate, _rate);
    }
 
    bool unlimited() const {
        return _rate.unlimited();
    }
 
    bool idle() const {
        return _rate.idle();
    }
 
    token_type rate() const {
        return _rate.rate();
    }
 
    token_type capacity() const {
        return _rate.capacity();
    }
 
    token_type size() const {
        return _bucket.size(_rate);
    }
 
    token_type fraction() const {
        return _bucket.fraction();
    }
 
    bool empty() const {
        return _bucket.empty();
    }
 
    bool full() const {
        return _bucket.full();
    }
 
    bool contains(token_type t) const {
        return _bucket.contains(_rate, t);
    }
 
    bool contains_fraction(token_type f) const {
        return _bucket.contains_fraction(f);
    }
 
    void clear() {
        _bucket.clear();
    }
 
    void set_full() {
        _bucket.set_full();
    }
 
    void set(token_type t) {
        _bucket.set(_rate, t);
    }
 
    void set_fraction(token_type f) {
        _bucket.set_fraction(f);
    }
 
    void refill() {
        _bucket.refill(_rate);
    }
 
    void refill(time_point_type time) {
        _bucket.refill(_rate, time);
    }
 
    template <typename U> void refill(U time) {
        _bucket.refill(_rate, time);
    }
 
    void set_time_point(time_point_type time) {
        _bucket.set_time_point(time);
    }
 
    time_point_type time_point() {
        return _bucket.time_point();
    }
 
    void remove(token_type t) {
        _bucket.remove(_rate, t);
    }
 
    bool remove_if(token_type t) {
        return _bucket.remove_if(_rate, t);
    }
 
    void remove_fraction(token_type f) {
        _bucket.remove_fraction(f);
    }
 
    bool remove_fraction_if(token_type f) {
        return _bucket.remove_fraction_if(f);
    }
 
    ticks_type time_until_contains(token_type t) const {
        return _bucket.time_until_contains(_rate, t);
    }
 
    ticks_type time_until_contains_fraction(ticks_type f) const {
        return _bucket.time_until_contains_fraction(_rate, f);
    }
 
 
    inline ticks_type epochs_until_contains(const rate_type &rate, token_type t) const CLICK_DEPRECATED;
    inline ticks_type epochs_until_contains_fraction(const rate_type &rate, token_type f) const CLICK_DEPRECATED;
  private:
 
    rate_type _rate;
    counter_type _bucket;
 
};
 
template <typename P>
inline typename TokenBucketX<P>::ticks_type TokenBucketX<P>::epochs_until_contains(const rate_type &rate, token_type t) const
{
    return time_until_contains(rate, t);
}
template <typename P>
inline typename TokenBucketX<P>::ticks_type TokenBucketX<P>::epochs_until_contains_fraction(const rate_type &rate, token_type f) const
{
    return time_until_contains_fraction(rate, f);
}
typedef TokenRateX<TokenBucketUsecParameters<unsigned long long> > TokenRate;
 
typedef TokenCounterX<TokenRate> TokenCounter;
 
typedef TokenBucketX<TokenBucketUsecParameters<unsigned long long> > TokenBucket;
 
CLICK_ENDDECLS
#endif