Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1754681AbcL3XDv (ORCPT ); Fri, 30 Dec 2016 18:03:51 -0500 Received: from mo4-p00-ob.smtp.rzone.de ([81.169.146.217]:35319 "EHLO mo4-p00-ob.smtp.rzone.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1754025AbcL3W6F (ORCPT ); Fri, 30 Dec 2016 17:58:05 -0500 X-RZG-AUTH: :OH8QVVOrc/CP6za/qRmbF3BWedPGA1vjs2ejZCzW8NRdwTYefHi0L5RzHLEjAZn5asq7vKs= X-RZG-CLASS-ID: mo00 From: Thomas Schoebel-Theuer To: linux-kernel@vger.kernel.org, tst@schoebel-theuer.de Subject: [RFC 09/32] mars: add new module lib_rank Date: Fri, 30 Dec 2016 23:57:35 +0100 Message-Id: X-Mailer: git-send-email 2.11.0 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: 6451 Lines: 245 Signed-off-by: Thomas Schoebel-Theuer --- drivers/staging/mars/lib/lib_rank.c | 87 +++++++++++++++++++++++ include/linux/brick/lib_rank.h | 136 ++++++++++++++++++++++++++++++++++++ 2 files changed, 223 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 000000000000..6327479039b6 --- /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 +#include + +#include + +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 000000000000..fa18fdf15597 --- /dev/null +++ b/include/linux/brick/lib_rank.h @@ -0,0 +1,136 @@ +/* + * 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.11.0