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