1 files changed, 257 insertions, 0 deletions

diff --git a/src/lib/util/load.c b/src/lib/util/load.c
new file mode 100644
index 000000000..a64171bd4
--- /dev/null
+++ b/src/lib/util/load.c
@@ -0,0 +1,257 @@
+/*
+     This file is part of GNUnet.
+     Copyright (C) 2010, 2013 GNUnet e.V.
+
+     GNUnet is free software: you can redistribute it and/or modify it
+     under the terms of the GNU Affero General Public License as published
+     by the Free Software Foundation, either version 3 of the License,
+     or (at your option) any later version.
+
+     GNUnet 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
+     Affero General Public License for more details.
+
+     You should have received a copy of the GNU Affero General Public License
+     along with this program.  If not, see <http://www.gnu.org/licenses/>.
+
+     SPDX-License-Identifier: AGPL3.0-or-later
+ */
+
+/**
+ * @file util/load.c
+ * @brief functions related to load calculations
+ * @author Christian Grothoff
+ */
+
+#include "platform.h"
+#include "gnunet_util_lib.h"
+
+
+#define LOG(kind, ...) GNUNET_log_from (kind, "util-load", __VA_ARGS__)
+
+/**
+ * Values we track for load calculations.
+ */
+struct GNUNET_LOAD_Value
+{
+  /**
+   * How fast should the load decline if no values are added?
+   */
+  struct GNUNET_TIME_Relative autodecline;
+
+  /**
+   * Last time this load value was updated by an event.
+   */
+  struct GNUNET_TIME_Absolute last_update;
+
+  /**
+   * Sum of all datastore delays ever observed (in ms).  Note that
+   * delays above 64k ms are excluded (to avoid overflow within
+   * first 4 billion requests).
+   */
+  uint64_t cummulative_delay;
+
+  /**
+   * Sum of squares of all datastore delays ever observed (in ms).   Note that
+   * delays above 64k ms are excluded (to avoid overflow within
+   * first 4 billion requests).
+   */
+  uint64_t cummulative_squared_delay;
+
+  /**
+   * Total number of requests included in the cumulative datastore delay values.
+   */
+  uint64_t cummulative_request_count;
+
+  /**
+   * Current running average datastore delay.  Its relation to the
+   * average datastore delay and it std. dev. (as calculated from the
+   * cumulative values) tells us our current load.
+   */
+  double runavg_delay;
+
+  /**
+   * How high is the load?  0 for below average, otherwise
+   * the number of std. devs we are above average, or 100 if the
+   * load is so high that we currently cannot calculate it.
+   */
+  double load;
+};
+
+
+static void
+internal_update (struct GNUNET_LOAD_Value *load)
+{
+  struct GNUNET_TIME_Relative delta;
+  unsigned int n;
+
+  if (load->autodecline.rel_value_us ==
+      GNUNET_TIME_UNIT_FOREVER_REL.rel_value_us)
+    return;
+  delta = GNUNET_TIME_absolute_get_duration (load->last_update);
+  if (delta.rel_value_us < load->autodecline.rel_value_us)
+    return;
+  if (0 == load->autodecline.rel_value_us)
+  {
+    load->runavg_delay = 0.0;
+    load->load = 0;
+    return;
+  }
+  n = delta.rel_value_us / load->autodecline.rel_value_us;
+  if (n > 16)
+  {
+    load->runavg_delay = 0.0;
+    load->load = 0;
+    return;
+  }
+  while (n > 0)
+  {
+    n--;
+    load->runavg_delay = (load->runavg_delay * 7.0) / 8.0;
+  }
+}
+
+
+/**
+ * Create a new load value.
+ *
+ * @param autodecline speed at which this value should automatically
+ *        decline in the absence of external events; at the given
+ *        frequency, 0-load values will be added to the load
+ * @return the new load value
+ */
+struct GNUNET_LOAD_Value *
+GNUNET_LOAD_value_init (struct GNUNET_TIME_Relative autodecline)
+{
+  struct GNUNET_LOAD_Value *ret;
+
+  ret = GNUNET_new (struct GNUNET_LOAD_Value);
+  ret->autodecline = autodecline;
+  ret->last_update = GNUNET_TIME_absolute_get ();
+  return ret;
+}
+
+
+/**
+ * Change the value by which the load automatically declines.
+ *
+ * @param load load to update
+ * @param autodecline frequency of load decline
+ */
+void
+GNUNET_LOAD_value_set_decline (struct GNUNET_LOAD_Value *load,
+                               struct GNUNET_TIME_Relative autodecline)
+{
+  internal_update (load);
+  load->autodecline = autodecline;
+}
+
+
+/**
+ * Recalculate our load value.
+ *
+ * @param load load to update
+ */
+static void
+calculate_load (struct GNUNET_LOAD_Value *load)
+{
+  double stddev;
+  double avgdel;
+  double sum_val_i;
+  double n;
+  double nm1;
+
+  if (load->cummulative_request_count <= 1)
+    return;
+  /* calculate std dev of latency; we have for n values of "i" that:
+   *
+   * avg = (sum val_i) / n
+   * stddev = (sum (val_i - avg)^2) / (n-1)
+   * = (sum (val_i^2 - 2 avg val_i + avg^2) / (n-1)
+   * = (sum (val_i^2) - 2 avg sum (val_i) + n * avg^2) / (n-1)
+   */sum_val_i = (double) load->cummulative_delay;
+  n = ((double) load->cummulative_request_count);
+  nm1 = n - 1.0;
+  avgdel = sum_val_i / n;
+  stddev =
+    (((double) load->cummulative_squared_delay) - 2.0 * avgdel * sum_val_i
+     + n * avgdel * avgdel) / nm1;
+  if (stddev <= 0)
+    stddev = 0.01;              /* must have been rounding error or zero; prevent division by zero */
+  /* now calculate load based on how far out we are from
+   * std dev; or if we are below average, simply assume load zero */
+  if (load->runavg_delay < avgdel)
+    load->load = 0.0;
+  else
+    load->load = (load->runavg_delay - avgdel) / stddev;
+}
+
+
+/**
+ * Get the current load.
+ *
+ * @param load load handle
+ * @return zero for below-average load, otherwise
+ *         number of std. devs we are above average;
+ *         100 if the latest updates were so large
+ *         that we could not do proper calculations
+ */
+double
+GNUNET_LOAD_get_load (struct GNUNET_LOAD_Value *load)
+{
+  internal_update (load);
+  calculate_load (load);
+  return load->load;
+}
+
+
+/**
+ * Get the average value given to update so far.
+ *
+ * @param load load handle
+ * @return zero if update was never called
+ */
+double
+GNUNET_LOAD_get_average (struct GNUNET_LOAD_Value *load)
+{
+  double n;
+  double sum_val_i;
+
+  internal_update (load);
+  if (load->cummulative_request_count == 0)
+    return 0.0;
+  n = ((double) load->cummulative_request_count);
+  sum_val_i = (double) load->cummulative_delay;
+  return sum_val_i / n;
+}
+
+
+/**
+ * Update the current load.
+ *
+ * @param load to update
+ * @param data latest measurement value (for example, delay)
+ */
+void
+GNUNET_LOAD_update (struct GNUNET_LOAD_Value *load, uint64_t data)
+{
+  uint32_t dv;
+
+  internal_update (load);
+  load->last_update = GNUNET_TIME_absolute_get ();
+  if (data > 64 * 1024)
+  {
+    /* very large */
+    load->load = 100.0;
+    return;
+  }
+  dv = (uint32_t) data;
+  load->cummulative_delay += dv;
+  load->cummulative_squared_delay += dv * dv;
+  load->cummulative_request_count++;
+  load->runavg_delay = ((load->runavg_delay * 7.0) + dv) / 8.0;
+}
+
+
+/* end of load.c */