lkml.org 
[lkml]   [2016]   [Dec]   [30]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    Patch in this message
    /
    From
    Subject[RFC 10/32] mars: add new module lib_limiter
    Date
    Signed-off-by: Thomas Schoebel-Theuer <tst@schoebel-theuer.de>
    ---
    drivers/staging/mars/lib/lib_limiter.c | 163 +++++++++++++++++++++++++++++++++
    include/linux/brick/lib_limiter.h | 52 +++++++++++
    2 files changed, 215 insertions(+)
    create mode 100644 drivers/staging/mars/lib/lib_limiter.c
    create mode 100644 include/linux/brick/lib_limiter.h

    diff --git a/drivers/staging/mars/lib/lib_limiter.c b/drivers/staging/mars/lib/lib_limiter.c
    new file mode 100644
    index 000000000000..e77b74a0eae7
    --- /dev/null
    +++ b/drivers/staging/mars/lib/lib_limiter.c
    @@ -0,0 +1,163 @@
    +/*
    + * MARS Long Distance Replication Software
    + *
    + * Copyright (C) 2010-2014 Thomas Schoebel-Theuer
    + * Copyright (C) 2011-2014 1&1 Internet AG
    + *
    + * 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 <linux/brick/lib_limiter.h>
    +
    +#include <linux/kernel.h>
    +#include <linux/module.h>
    +#include <linux/jiffies.h>
    +#include <linux/sched.h>
    +
    +#define LIMITER_TIME_RESOLUTION NSEC_PER_SEC
    +
    +int rate_limit(struct rate_limiter *lim, int amount)
    +{
    + int delay = 0;
    + long long now;
    +
    + now = cpu_clock(raw_smp_processor_id());
    +
    + /* Compute the maximum delay along the path
    + * down to the root of the hierarchy tree.
    + */
    + while (lim) {
    + long long window = now - lim->lim_stamp;
    +
    + /* Sometimes, raw CPU clocks may do weired things...
    + * Smaller windows in the denominator than 1s could fake unrealistic rates.
    + */
    + if (unlikely(lim->lim_min_window <= 0))
    + lim->lim_min_window = 1000;
    + if (unlikely(lim->lim_max_window <= lim->lim_min_window))
    + lim->lim_max_window = lim->lim_min_window + 8000;
    + if (unlikely(window < (long long)lim->lim_min_window * (LIMITER_TIME_RESOLUTION / 1000)))
    + window = (long long)lim->lim_min_window * (LIMITER_TIME_RESOLUTION / 1000);
    +
    + /* Update total statistics.
    + * They will intentionally wrap around.
    + * Userspace must take care of that.
    + */
    + if (likely(amount > 0)) {
    + lim->lim_total_amount += amount;
    + lim->lim_total_ops++;
    + }
    +
    + /* Only use incremental accumulation at repeated calls, but
    + * never after longer pauses.
    + */
    + if (likely(lim->lim_stamp &&
    + window < (long long)lim->lim_max_window * (LIMITER_TIME_RESOLUTION / 1000))) {
    + long long rate_raw;
    + int rate;
    + int max_rate;
    +
    + /* Races are possible, but taken into account.
    + * There is no real harm from rarely lost updates.
    + */
    + if (likely(amount > 0)) {
    + lim->lim_amount_accu += amount;
    + lim->lim_amount_cumul += amount;
    + lim->lim_ops_accu++;
    + lim->lim_ops_cumul++;
    + }
    +
    + /* compute amount values */
    + rate_raw = lim->lim_amount_accu * LIMITER_TIME_RESOLUTION / window;
    + rate = rate_raw;
    + if (unlikely(rate_raw > INT_MAX))
    + rate = INT_MAX;
    + lim->lim_amount_rate = rate;
    +
    + /* amount limit exceeded? */
    + max_rate = lim->lim_max_amount_rate;
    + if (max_rate > 0 && rate > max_rate) {
    + int this_delay = (
    +
    + window * rate / max_rate - window) / (LIMITER_TIME_RESOLUTION / 1000);
    + /* compute maximum */
    + if (this_delay > delay && this_delay > 0)
    + delay = this_delay;
    + }
    +
    + /* compute ops values */
    + rate_raw = lim->lim_ops_accu * LIMITER_TIME_RESOLUTION / window;
    + rate = rate_raw;
    + if (unlikely(rate_raw > INT_MAX))
    + rate = INT_MAX;
    + lim->lim_ops_rate = rate;
    +
    + /* ops limit exceeded? */
    + max_rate = lim->lim_max_ops_rate;
    + if (max_rate > 0 && rate > max_rate) {
    + int this_delay = (
    +
    + window * rate / max_rate - window) / (LIMITER_TIME_RESOLUTION / 1000);
    + /* compute maximum */
    + if (this_delay > delay && this_delay > 0)
    + delay = this_delay;
    + }
    +
    + /* Try to keep the next window below min_window
    + */
    + window -= lim->lim_min_window * (LIMITER_TIME_RESOLUTION / 1000);
    + if (window > 0) {
    + long long used_up = (long long)lim->lim_amount_rate * window / LIMITER_TIME_RESOLUTION;
    +
    + if (used_up > 0) {
    + lim->lim_stamp += window;
    + lim->lim_amount_accu -= used_up;
    + if (unlikely(lim->lim_amount_accu < 0))
    + lim->lim_amount_accu = 0;
    + }
    + used_up = (long long)lim->lim_ops_rate * window / LIMITER_TIME_RESOLUTION;
    + if (used_up > 0) {
    + lim->lim_stamp += window;
    + lim->lim_ops_accu -= used_up;
    + if (unlikely(lim->lim_ops_accu < 0))
    + lim->lim_ops_accu = 0;
    + }
    + }
    + } else { /* reset, start over with new measurement cycle */
    + if (unlikely(amount < 0))
    + amount = 0;
    + lim->lim_ops_accu = 1;
    + lim->lim_amount_accu = amount;
    + lim->lim_stamp = now - lim->lim_min_window * (LIMITER_TIME_RESOLUTION / 1000);
    + lim->lim_ops_rate = 0;
    + lim->lim_amount_rate = 0;
    + }
    + lim = lim->lim_father;
    + }
    + return delay;
    +}
    +
    +void rate_limit_sleep(struct rate_limiter *lim, int amount)
    +{
    + int sleep = rate_limit(lim, amount);
    +
    + if (sleep > 0) {
    + unsigned long timeout;
    +
    + if (unlikely(lim->lim_max_delay <= 0))
    + lim->lim_max_delay = 1000;
    + if (sleep > lim->lim_max_delay)
    + sleep = lim->lim_max_delay;
    + timeout = msecs_to_jiffies(sleep);
    + while ((long)timeout > 0)
    + timeout = schedule_timeout_uninterruptible(timeout);
    + }
    +}
    diff --git a/include/linux/brick/lib_limiter.h b/include/linux/brick/lib_limiter.h
    new file mode 100644
    index 000000000000..fab0c0e1858f
    --- /dev/null
    +++ b/include/linux/brick/lib_limiter.h
    @@ -0,0 +1,52 @@
    +/*
    + * MARS Long Distance Replication Software
    + *
    + * Copyright (C) 2010-2014 Thomas Schoebel-Theuer
    + * Copyright (C) 2011-2014 1&1 Internet AG
    + *
    + * 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.
    + */
    +
    +#ifndef LIB_LIMITER_H
    +#define LIB_LIMITER_H
    +
    +#include <linux/utsname.h>
    +
    +struct rate_limiter {
    + /* hierarchy tree */
    + struct rate_limiter *lim_father;
    +
    + /* tunables */
    + int lim_max_ops_rate;
    + int lim_max_amount_rate;
    + int lim_max_delay;
    + int lim_min_window;
    + int lim_max_window;
    +
    + /* readable */
    + int lim_ops_rate;
    + int lim_amount_rate;
    + int lim_ops_cumul;
    + int lim_amount_cumul;
    + int lim_total_ops;
    + int lim_total_amount;
    + long long lim_stamp;
    +
    + /* internal */
    + long long lim_ops_accu;
    + long long lim_amount_accu;
    +};
    +
    +extern int rate_limit(struct rate_limiter *lim, int amount);
    +
    +extern void rate_limit_sleep(struct rate_limiter *lim, int amount);
    +
    +#endif
    --
    2.11.0
    \
     
     \ /
      Last update: 2016-12-31 00:01    [W:3.700 / U:0.768 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site