Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1754561AbbLaLht (ORCPT ); Thu, 31 Dec 2015 06:37:49 -0500 Received: from mo4-p00-ob.smtp.rzone.de ([81.169.146.216]:49793 "EHLO mo4-p00-ob.smtp.rzone.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751432AbbLaLhS (ORCPT ); Thu, 31 Dec 2015 06:37:18 -0500 X-RZG-AUTH: :OH8QVVOrc/CP6za/qRmbF3BWedPGA1vjs2ejZCzW8NRdwTYefHi0LhjeQF0sTFwGWOFPJQ== X-RZG-CLASS-ID: mo00 From: Thomas Schoebel-Theuer To: linux-kernel@vger.kernel.org, tst@schoebel-theuer.de Subject: [RFC 10/31] mars: add new module lib_limiter Date: Thu, 31 Dec 2015 12:36:05 +0100 Message-Id: X-Mailer: git-send-email 2.6.4 In-Reply-To: References: In-Reply-To: References: Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 6242 Lines: 206 Signed-off-by: Thomas Schoebel-Theuer --- drivers/staging/mars/lib/lib_limiter.c | 129 +++++++++++++++++++++++++++++++++ include/linux/brick/lib_limiter.h | 49 +++++++++++++ 2 files changed, 178 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 0000000..12ac8de --- /dev/null +++ b/drivers/staging/mars/lib/lib_limiter.c @@ -0,0 +1,129 @@ +/* + * 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 + +#include +#include +#include +#include + +#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 != NULL) { + 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. + */ + lim->lim_total_ops++; + lim->lim_total_sum += amount; + + /* 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; + + /* Races are possible, but taken into account. + * There is no real harm from rarely lost updates. + */ + if (likely(amount > 0)) { + lim->lim_accu += amount; + lim->lim_cumul += amount; + lim->lim_count++; + } + + rate_raw = lim->lim_accu * LIMITER_TIME_RESOLUTION / window; + rate = rate_raw; + if (unlikely(rate_raw > INT_MAX)) + rate = INT_MAX; + lim->lim_rate = rate; + + /* limit exceeded? */ + if (lim->lim_max_rate > 0 && rate > lim->lim_max_rate) { + int this_delay = (window * rate / lim->lim_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_rate * window / LIMITER_TIME_RESOLUTION; + + if (used_up > 0) { + lim->lim_stamp += window; + lim->lim_accu -= used_up; + if (unlikely(lim->lim_accu < 0)) + lim->lim_accu = 0; + } + } + } else { /* reset, start over with new measurement cycle */ + if (unlikely(amount < 0)) + amount = 0; + lim->lim_accu = amount; + lim->lim_stamp = now - lim->lim_min_window * (LIMITER_TIME_RESOLUTION / 1000); + lim->lim_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 0000000..e14fa7e --- /dev/null +++ b/include/linux/brick/lib_limiter.h @@ -0,0 +1,49 @@ +/* + * 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 + +struct rate_limiter { + /* hierarchy tree */ + struct rate_limiter *lim_father; + + /* tunables */ + int lim_max_rate; + int lim_max_delay; + int lim_min_window; + int lim_max_window; + + /* readable */ + int lim_rate; + int lim_cumul; + int lim_count; + int lim_total_ops; + int lim_total_sum; + long long lim_stamp; + + /* internal */ + long long lim_accu; +}; + +extern int rate_limit(struct rate_limiter *lim, int amount); + +extern void rate_limit_sleep(struct rate_limiter *lim, int amount); + +#endif -- 2.6.4 -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/