| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Message-Id: <4501f2b7c183696a142aa22ac3633f96085d27a4.1483138400.git.tst@schoebel-theuer.de>
Date: Fri, 30 Dec 2016 23:57:36 +0100
From: Thomas Schoebel-Theuer <tst@...oebel-theuer.de>
To: linux-kernel@...r.kernel.org, tst@...oebel-theuer.de
Subject: [RFC 10/32] mars: add new module lib_limiter
Signed-off-by: Thomas Schoebel-Theuer <tst@...oebel-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
Powered by blists - more mailing lists