Merge branch 'master' of ssh://gnunet.org/gnunet
[oweals/gnunet.git] / 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 */