Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1754385AbbLaLho (ORCPT ); Thu, 31 Dec 2015 06:37:44 -0500 Received: from mo4-p00-ob.smtp.rzone.de ([81.169.146.220]:41537 "EHLO mo4-p00-ob.smtp.rzone.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751405AbbLaLhS (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 09/31] mars: add new module lib_rank Date: Thu, 31 Dec 2015 12:36:04 +0100 Message-Id: <9859a1b2a2463daa3e40a5fb10f418be373623f1.1451558672.git.tst@schoebel-theuer.de> 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: 6669 Lines: 250 Signed-off-by: Thomas Schoebel-Theuer --- 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 +#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 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@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/