diff options
Diffstat (limited to 'src/lib/util/load.c')
-rw-r--r-- | src/lib/util/load.c | 257 |
1 files changed, 257 insertions, 0 deletions
diff --git a/src/lib/util/load.c b/src/lib/util/load.c new file mode 100644 index 000000000..a64171bd4 --- /dev/null +++ b/src/lib/util/load.c | |||
@@ -0,0 +1,257 @@ | |||
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 | You should have received a copy of the GNU Affero General Public License | ||
16 | along with this program. If not, see <http://www.gnu.org/licenses/>. | ||
17 | |||
18 | SPDX-License-Identifier: AGPL3.0-or-later | ||
19 | */ | ||
20 | |||
21 | /** | ||
22 | * @file util/load.c | ||
23 | * @brief functions related to load calculations | ||
24 | * @author Christian Grothoff | ||
25 | */ | ||
26 | |||
27 | #include "platform.h" | ||
28 | #include "gnunet_util_lib.h" | ||
29 | |||
30 | |||
31 | #define LOG(kind, ...) GNUNET_log_from (kind, "util-load", __VA_ARGS__) | ||
32 | |||
33 | /** | ||
34 | * Values we track for load calculations. | ||
35 | */ | ||
36 | struct GNUNET_LOAD_Value | ||
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 cumulative 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 calculated from the | ||
70 | * cumulative 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 | 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.rel_value_us == | ||
90 | 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 | /* calculate 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 | */sum_val_i = (double) load->cummulative_delay; | ||
174 | n = ((double) load->cummulative_request_count); | ||
175 | nm1 = n - 1.0; | ||
176 | avgdel = sum_val_i / n; | ||
177 | stddev = | ||
178 | (((double) load->cummulative_squared_delay) - 2.0 * avgdel * sum_val_i | ||
179 | + n * avgdel * avgdel) / nm1; | ||
180 | if (stddev <= 0) | ||
181 | stddev = 0.01; /* must have been rounding error or zero; prevent division by zero */ | ||
182 | /* now calculate load based on how far out we are from | ||
183 | * std dev; or if we are below average, simply assume load zero */ | ||
184 | if (load->runavg_delay < avgdel) | ||
185 | load->load = 0.0; | ||
186 | else | ||
187 | load->load = (load->runavg_delay - avgdel) / stddev; | ||
188 | } | ||
189 | |||
190 | |||
191 | /** | ||
192 | * Get the current load. | ||
193 | * | ||
194 | * @param load load handle | ||
195 | * @return zero for below-average load, otherwise | ||
196 | * number of std. devs we are above average; | ||
197 | * 100 if the latest updates were so large | ||
198 | * that we could not do proper calculations | ||
199 | */ | ||
200 | double | ||
201 | GNUNET_LOAD_get_load (struct GNUNET_LOAD_Value *load) | ||
202 | { | ||
203 | internal_update (load); | ||
204 | calculate_load (load); | ||
205 | return load->load; | ||
206 | } | ||
207 | |||
208 | |||
209 | /** | ||
210 | * Get the average value given to update so far. | ||
211 | * | ||
212 | * @param load load handle | ||
213 | * @return zero if update was never called | ||
214 | */ | ||
215 | double | ||
216 | GNUNET_LOAD_get_average (struct GNUNET_LOAD_Value *load) | ||
217 | { | ||
218 | double n; | ||
219 | double sum_val_i; | ||
220 | |||
221 | internal_update (load); | ||
222 | if (load->cummulative_request_count == 0) | ||
223 | return 0.0; | ||
224 | n = ((double) load->cummulative_request_count); | ||
225 | sum_val_i = (double) load->cummulative_delay; | ||
226 | return sum_val_i / n; | ||
227 | } | ||
228 | |||
229 | |||
230 | /** | ||
231 | * Update the current load. | ||
232 | * | ||
233 | * @param load to update | ||
234 | * @param data latest measurement value (for example, delay) | ||
235 | */ | ||
236 | void | ||
237 | GNUNET_LOAD_update (struct GNUNET_LOAD_Value *load, uint64_t data) | ||
238 | { | ||
239 | uint32_t dv; | ||
240 | |||
241 | internal_update (load); | ||
242 | load->last_update = GNUNET_TIME_absolute_get (); | ||
243 | if (data > 64 * 1024) | ||
244 | { | ||
245 | /* very large */ | ||
246 | load->load = 100.0; | ||
247 | return; | ||
248 | } | ||
249 | dv = (uint32_t) data; | ||
250 | load->cummulative_delay += dv; | ||
251 | load->cummulative_squared_delay += dv * dv; | ||
252 | load->cummulative_request_count++; | ||
253 | load->runavg_delay = ((load->runavg_delay * 7.0) + dv) / 8.0; | ||
254 | } | ||
255 | |||
256 | |||
257 | /* end of load.c */ | ||