| 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
| ||
|
Date: Thu, 31 Dec 2015 12:36:04 +0100
From: Thomas Schoebel-Theuer <tst@...oebel-theuer.de>
To: linux-kernel@...r.kernel.org, tst@...oebel-theuer.de
Subject: [RFC 09/31] mars: add new module lib_rank
Signed-off-by: Thomas Schoebel-Theuer <tst@...oebel-theuer.de>
---
drivers/staging/mars/lib/lib_rank.c | 87 +++++++++++++++++++++++
include/linux/brick/lib_rank.h | 135 ++++++++++++++++++++++++++++++++++++
2 files changed, 222 insertions(+)
create mode 100644 drivers/staging/mars/lib/lib_rank.c
create mode 100644 include/linux/brick/lib_rank.h
diff --git a/drivers/staging/mars/lib/lib_rank.c b/drivers/staging/mars/lib/lib_rank.c
new file mode 100644
index 0000000..3bdd1d5
--- /dev/null
+++ b/drivers/staging/mars/lib/lib_rank.c
@@ -0,0 +1,87 @@
+/*
+ * 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.
+ */
+
+/* (c) 2012 Thomas Schoebel-Theuer */
+
+#include <linux/kernel.h>
+#include <linux/module.h>
+
+#include <linux/brick/lib_rank.h>
+
+void ranking_compute(struct rank_data *rkd, const struct rank_info rki[], int x)
+{
+ int points = 0;
+ int i;
+
+ for (i = 0; ; i++) {
+ int x0;
+ int x1;
+ int y0;
+ int y1;
+
+ x0 = rki[i].rki_x;
+ if (x < x0)
+ break;
+
+ x1 = rki[i+1].rki_x;
+
+ if (unlikely(x1 == RKI_DUMMY)) {
+ points = rki[i].rki_y;
+ break;
+ }
+
+ if (x > x1)
+ continue;
+
+ y0 = rki[i].rki_y;
+ y1 = rki[i+1].rki_y;
+
+ /* linear interpolation */
+ points = ((long long)(x - x0) * (long long)(y1 - y0)) / (x1 - x0) + y0;
+ break;
+ }
+ rkd->rkd_tmp += points;
+}
+
+int ranking_select(struct rank_data rkd[], int rkd_count)
+{
+ int res = -1;
+ long long max = LLONG_MIN / 2;
+ int i;
+
+ for (i = 0; i < rkd_count; i++) {
+ struct rank_data *tmp = &rkd[i];
+ long long rest = tmp->rkd_current_points;
+
+ if (rest <= 0)
+ continue;
+ /* rest -= tmp->rkd_got; */
+ if (rest > max) {
+ max = rest;
+ res = i;
+ }
+ }
+ /* Prevent underflow in the long term
+ * and reset the "clocks" after each round of
+ * weighted round-robin selection.
+ */
+ if (max < 0 && res >= 0) {
+ for (i = 0; i < rkd_count; i++)
+ rkd[i].rkd_got += max;
+ }
+ return res;
+}
diff --git a/include/linux/brick/lib_rank.h b/include/linux/brick/lib_rank.h
new file mode 100644
index 0000000..62f025e
--- /dev/null
+++ b/include/linux/brick/lib_rank.h
@@ -0,0 +1,135 @@
+/*
+ * 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.
+ */
+
+/* (c) 2012 Thomas Schoebel-Theuer */
+
+#ifndef LIB_RANK_H
+#define LIB_RANK_H
+
+/* Generic round-robin scheduler based on ranking information.
+ */
+
+#define RKI_DUMMY INT_MIN
+
+struct rank_info {
+ int rki_x;
+ int rki_y;
+};
+
+struct rank_data {
+ /* public readonly */
+ long long rkd_current_points;
+
+ /* private */
+ long long rkd_tmp;
+ long long rkd_got;
+};
+
+/* Ranking phase.
+ *
+ * Calls should follow the following usage pattern:
+ *
+ * ranking_start(...);
+ * for (...) {
+ * ranking_compute(&rkd[this_time], ...);
+ * // usually you need at least 1 call for each rkd[] element,
+ * // but you can call more often to include ranking information
+ * // from many different sources.
+ * // Note: instead / additionally, you may also use
+ * // ranking_add() or ranking_override().
+ * }
+ * ranking_stop(...);
+ *
+ * = > now the new ranking values are computed and already active
+ * for the round-robin ranking_select() mechanism described below.
+ *
+ * Important: the rki[] array describes a ranking function at some
+ * example points (x_i, y_i) which must be ordered according to x_i
+ * in ascending order. And, of course, you need to supply at least
+ * two sample points (otherwise a linear function cannot
+ * be described).
+ * The array _must_ always end with a dummy record where the x_i has the
+ * value RKI_DUMMY.
+ */
+
+extern inline
+void ranking_start(struct rank_data rkd[], int rkd_count)
+{
+ int i;
+
+ for (i = 0; i < rkd_count; i++)
+ rkd[i].rkd_tmp = 0;
+}
+
+extern void ranking_compute(struct rank_data *rkd, const struct rank_info rki[], int x);
+
+/* This may be used to (exceptionally) add some extra salt...
+ */
+extern inline
+void ranking_add(struct rank_data *rkd, int y)
+{
+ rkd->rkd_tmp += y;
+}
+
+/* This may be used to (exceptionally) override certain ranking values.
+ */
+extern inline
+void ranking_override(struct rank_data *rkd, int y)
+{
+ rkd->rkd_tmp = y;
+}
+
+extern inline
+void ranking_stop(struct rank_data rkd[], int rkd_count)
+{
+ int i;
+
+ for (i = 0; i < rkd_count; i++)
+ rkd[i].rkd_current_points = rkd[i].rkd_tmp;
+}
+
+/* This is a round-robin scheduler taking her weights
+ * from the previous ranking phase (the more ranking points,
+ * the more frequently a candidate will be selected).
+ *
+ * Typical usage pattern (independent from the above ranking phase
+ * usage pattern):
+ *
+ * while (__there_is_work_to_be_done(...)) {
+ * int winner = ranking_select(...);
+ * if (winner >= 0) {
+ * __do_something(winner);
+ * ranking_select_done(..., winner, 1); // or higher, winpoints >= 1 must hold
+ * }
+ * ...
+ * }
+ *
+ */
+
+extern int ranking_select(struct rank_data rkd[], int rkd_count);
+
+extern inline
+void ranking_select_done(struct rank_data rkd[], int winner, int win_points)
+{
+ if (winner >= 0) {
+ if (win_points < 1)
+ win_points = 1;
+ rkd[winner].rkd_got += win_points;
+ }
+}
+
+#endif
--
2.6.4
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Powered by blists - more mailing lists