src/util/load.c

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