src/util/load.c

   1 /*
   2      This file is part of GNUnet.
   3      Copyright (C) 2010, 2013 GNUnet e.V.
   4
   5      GNUnet is free software: you can redistribute it and/or modify it
   6      under the terms of the GNU Affero General Public License as published
   7      by the Free Software Foundation, either version 3 of the License,
   8      or (at your option) any later version.
   9
  10      GNUnet is distributed in the hope that it will be useful, but
  11      WITHOUT ANY WARRANTY; without even the implied warranty of
  12      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13      Affero General Public License for more details.
  14
  15      You should have received a copy of the GNU Affero General Public License
  16      along with this program.  If not, see <http://www.gnu.org/licenses/>.
  17
  18      SPDX-License-Identifier: AGPL3.0-or-later
  19  */
  20
  21 /**
  22  * @file util/load.c
  23  * @brief functions related to load calculations
  24  * @author Christian Grothoff
  25  */
  26 #include "platform.h"
  27 #include "gnunet_util_lib.h"
  28
  29
  30 #define LOG(kind, ...) GNUNET_log_from (kind, "util-load", __VA_ARGS__)
  31
  32 /**
  33  * Values we track for load calculations.
  34  */
  35 struct GNUNET_LOAD_Value
  36 {
  37   /**
  38    * How fast should the load decline if no values are added?
  39    */
  40   struct GNUNET_TIME_Relative autodecline;
  41
  42   /**
  43    * Last time this load value was updated by an event.
  44    */
  45   struct GNUNET_TIME_Absolute last_update;
  46
  47   /**
  48    * Sum of all datastore delays ever observed (in ms).  Note that
  49    * delays above 64k ms are excluded (to avoid overflow within
  50    * first 4 billion requests).
  51    */
  52   uint64_t cummulative_delay;
  53
  54   /**
  55    * Sum of squares of all datastore delays ever observed (in ms).   Note that
  56    * delays above 64k ms are excluded (to avoid overflow within
  57    * first 4 billion requests).
  58    */
  59   uint64_t cummulative_squared_delay;
  60
  61   /**
  62    * Total number of requests included in the cummulative datastore delay values.
  63    */
  64   uint64_t cummulative_request_count;
  65
  66   /**
  67    * Current running average datastore delay.  Its relation to the
  68    * average datastore delay and it std. dev. (as calcualted from the
  69    * cummulative values) tells us our current load.
  70    */
  71   double runavg_delay;
  72
  73   /**
  74    * How high is the load?  0 for below average, otherwise
  75    * the number of std. devs we are above average, or 100 if the
  76    * load is so high that we currently cannot calculate it.
  77    */
  78   double load;
  79 };
  80
  81
  82 static void
  83 internal_update (struct GNUNET_LOAD_Value *load)
  84 {
  85   struct GNUNET_TIME_Relative delta;
  86   unsigned int n;
  87
  88   if (load->autodecline.rel_value_us ==
  89       GNUNET_TIME_UNIT_FOREVER_REL.rel_value_us)
  90     return;
  91   delta = GNUNET_TIME_absolute_get_duration (load->last_update);
  92   if (delta.rel_value_us < load->autodecline.rel_value_us)
  93     return;
  94   if (0 == load->autodecline.rel_value_us)
  95   {
  96     load->runavg_delay = 0.0;
  97     load->load = 0;
  98     return;
  99   }
 100   n = delta.rel_value_us / load->autodecline.rel_value_us;
 101   if (n > 16)
 102   {
 103     load->runavg_delay = 0.0;
 104     load->load = 0;
 105     return;
 106   }
 107   while (n > 0)
 108   {
 109     n--;
 110     load->runavg_delay = (load->runavg_delay * 7.0) / 8.0;
 111   }
 112 }
 113
 114
 115 /**
 116  * Create a new load value.
 117  *
 118  * @param autodecline speed at which this value should automatically
 119  *        decline in the absence of external events; at the given
 120  *        frequency, 0-load values will be added to the load
 121  * @return the new load value
 122  */
 123 struct GNUNET_LOAD_Value *
 124 GNUNET_LOAD_value_init (struct GNUNET_TIME_Relative autodecline)
 125 {
 126   struct GNUNET_LOAD_Value *ret;
 127
 128   ret = GNUNET_new (struct GNUNET_LOAD_Value);
 129   ret->autodecline = autodecline;
 130   ret->last_update = GNUNET_TIME_absolute_get ();
 131   return ret;
 132 }
 133
 134
 135 /**
 136  * Change the value by which the load automatically declines.
 137  *
 138  * @param load load to update
 139  * @param autodecline frequency of load decline
 140  */
 141 void
 142 GNUNET_LOAD_value_set_decline (struct GNUNET_LOAD_Value *load,
 143                                struct GNUNET_TIME_Relative autodecline)
 144 {
 145   internal_update (load);
 146   load->autodecline = autodecline;
 147 }
 148
 149
 150 /**
 151  * Recalculate our load value.
 152  *
 153  * @param load load to update
 154  */
 155 static void
 156 calculate_load (struct GNUNET_LOAD_Value *load)
 157 {
 158   double stddev;
 159   double avgdel;
 160   double sum_val_i;
 161   double n;
 162   double nm1;
 163
 164   if (load->cummulative_request_count <= 1)
 165     return;
 166   /* calcuate std dev of latency; we have for n values of "i" that:
 167    *
 168    * avg = (sum val_i) / n
 169    * stddev = (sum (val_i - avg)^2) / (n-1)
 170    * = (sum (val_i^2 - 2 avg val_i + avg^2) / (n-1)
 171    * = (sum (val_i^2) - 2 avg sum (val_i) + n * avg^2) / (n-1)
 172    */sum_val_i = (double) load->cummulative_delay;
 173   n = ((double) load->cummulative_request_count);
 174   nm1 = n - 1.0;
 175   avgdel = sum_val_i / n;
 176   stddev =
 177     (((double) load->cummulative_squared_delay) - 2.0 * avgdel * sum_val_i
 178      + n * avgdel * avgdel) / nm1;
 179   if (stddev <= 0)
 180     stddev = 0.01;              /* must have been rounding error or zero; prevent division by zero */
 181   /* now calculate load based on how far out we are from
 182    * std dev; or if we are below average, simply assume load zero */
 183   if (load->runavg_delay < avgdel)
 184     load->load = 0.0;
 185   else
 186     load->load = (load->runavg_delay - avgdel) / stddev;
 187 }
 188
 189
 190 /**
 191  * Get the current load.
 192  *
 193  * @param load load handle
 194  * @return zero for below-average load, otherwise
 195  *         number of std. devs we are above average;
 196  *         100 if the latest updates were so large
 197  *         that we could not do proper calculations
 198  */
 199 double
 200 GNUNET_LOAD_get_load (struct GNUNET_LOAD_Value *load)
 201 {
 202   internal_update (load);
 203   calculate_load (load);
 204   return load->load;
 205 }
 206
 207
 208 /**
 209  * Get the average value given to update so far.
 210  *
 211  * @param load load handle
 212  * @return zero if update was never called
 213  */
 214 double
 215 GNUNET_LOAD_get_average (struct GNUNET_LOAD_Value *load)
 216 {
 217   double n;
 218   double sum_val_i;
 219
 220   internal_update (load);
 221   if (load->cummulative_request_count == 0)
 222     return 0.0;
 223   n = ((double) load->cummulative_request_count);
 224   sum_val_i = (double) load->cummulative_delay;
 225   return sum_val_i / n;
 226 }
 227
 228
 229 /**
 230  * Update the current load.
 231  *
 232  * @param load to update
 233  * @param data latest measurement value (for example, delay)
 234  */
 235 void
 236 GNUNET_LOAD_update (struct GNUNET_LOAD_Value *load, uint64_t data)
 237 {
 238   uint32_t dv;
 239
 240   internal_update (load);
 241   load->last_update = GNUNET_TIME_absolute_get ();
 242   if (data > 64 * 1024)
 243   {
 244     /* very large */
 245     load->load = 100.0;
 246     return;
 247   }
 248   dv = (uint32_t) data;
 249   load->cummulative_delay += dv;
 250   load->cummulative_squared_delay += dv * dv;
 251   load->cummulative_request_count++;
 252   load->runavg_delay = ((load->runavg_delay * 7.0) + dv) / 8.0;
 253 }
 254
 255
 256 /* end of load.c */