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