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_NO
  30
  31 /**
  32  * Values we track for load calculations.
  33  */
  34 struct GNUNET_LOAD_Value
  35 {
  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
  83 static void
  84 internal_update (struct GNUNET_LOAD_Value *load)
  85 {
  86   struct GNUNET_TIME_Relative delta;
  87   unsigned int n;
  88
  89   if (load->autodecline.value == GNUNET_TIME_UNIT_FOREVER_REL.value)
  90     return;
  91   delta = GNUNET_TIME_absolute_get_duration (load->last_update);
  92   if (delta.value < load->autodecline.value)
  93     return;
  94   n = delta.value / load->autodecline.value;
  95   if (n > 16)
  96     {
  97       load->runavg_delay = 0.0;
  98       load->load = 0;
  99       return;
 100     }
 101   while (n > 0)
 102     {
 103       n--;
 104       load->runavg_delay = (load->runavg_delay * 7.0) / 8.0;
 105     }
 106 }
 107
 108
 109 /**
 110  * Create a new load value.
 111  *
 112  * @param autodecline speed at which this value should automatically
 113  *        decline in the absence of external events; at the given
 114  *        frequency, 0-load values will be added to the load
 115  * @return the new load value
 116  */
 117 struct GNUNET_LOAD_Value *
 118 GNUNET_LOAD_value_init (struct GNUNET_TIME_Relative autodecline)
 119 {
 120   struct GNUNET_LOAD_Value *ret;
 121
 122   GNUNET_assert (autodecline.value != 0);
 123   ret = GNUNET_malloc (sizeof (struct GNUNET_LOAD_Value));
 124   ret->autodecline = autodecline;
 125   ret->last_update = GNUNET_TIME_absolute_get ();
 126   return ret;
 127 }
 128
 129
 130 /**
 131  * Recalculate our load value.
 132  *
 133  * @param load load to update
 134  */
 135 static void
 136 calculate_load (struct GNUNET_LOAD_Value *load)
 137 {
 138   double stddev;
 139   double avgdel;
 140   double sum_val_i;
 141   double n;
 142   double nm1;
 143
 144   if (load->cummulative_request_count == 0)
 145     return;
 146   /* calcuate std dev of latency; we have for n values of "i" that:
 147
 148      avg = (sum val_i) / n
 149      stddev = (sum (val_i - avg)^2) / (n-1)
 150      = (sum (val_i^2 - 2 avg val_i + avg^2) / (n-1)
 151      = (sum (val_i^2) - 2 avg sum (val_i) + n * avg^2) / (n-1)
 152   */
 153   sum_val_i = (double) load->cummulative_delay;
 154   n = ((double) load->cummulative_request_count);
 155   nm1 = n - 1.0;
 156   avgdel = sum_val_i / n;
 157   stddev = (((double) load->cummulative_squared_delay) - 2.0 * avgdel * sum_val_i + n * avgdel * avgdel) / nm1;
 158   if (stddev <= 0)
 159     stddev = 0.01; /* must have been rounding error or zero; prevent division by zero */
 160   /* now calculate load based on how far out we are from
 161      std dev; or if we are below average, simply assume load zero */
 162   if (load->runavg_delay < avgdel)
 163     load->load = 0.0;
 164   else
 165     load->load = (load->runavg_delay - avgdel) / stddev;
 166 }
 167
 168
 169 /**
 170  * Get the current load.
 171  *
 172  * @param load load handle
 173  * @return zero for below-average load, otherwise
 174  *         number of std. devs we are above average;
 175  *         100 if the latest updates were so large
 176  *         that we could not do proper calculations
 177  */
 178 double
 179 GNUNET_LOAD_get_load (struct GNUNET_LOAD_Value *load)
 180 {
 181   internal_update (load);
 182   calculate_load (load);
 183   return load->load;
 184 }
 185
 186
 187 /**
 188  * Get the average value given to update so far.
 189  *
 190  * @param load load handle
 191  * @return zero if update was never called
 192  */
 193 double
 194 GNUNET_LOAD_get_average (struct GNUNET_LOAD_Value *load)
 195 {
 196   double n;
 197   double sum_val_i;
 198
 199   internal_update (load);
 200   if (load->cummulative_request_count == 0)
 201     return 0.0;
 202   n = ((double) load->cummulative_request_count);
 203   sum_val_i = (double) load->cummulative_delay;
 204   return sum_val_i / n;
 205 }
 206
 207
 208 /**
 209  * Update the current load.
 210  *
 211  * @param load to update
 212  * @param data latest measurement value (for example, delay)
 213  */
 214 void
 215 GNUNET_LOAD_update (struct GNUNET_LOAD_Value *load,
 216                     uint64_t data)
 217 {
 218   uint32_t dv;
 219
 220   internal_update (load);
 221   load->last_update = GNUNET_TIME_absolute_get ();
 222   if (data > 64 * 1024)
 223     {
 224       /* very large */
 225       load->load = 100.0;
 226       return;
 227     }
 228   dv = (uint32_t) data;
 229   load->cummulative_delay += dv;
 230   load->cummulative_squared_delay += dv * dv;
 231   load->cummulative_request_count++;
 232   load->runavg_delay = ((load->runavg_delay * 7.0) + dv) / 8.0;
 233 }
 234
 235
 236
 237 /* end of load.c */