diff options
author | Christian Grothoff <christian@grothoff.org> | 2015-02-10 23:24:01 +0000 |
---|---|---|
committer | Christian Grothoff <christian@grothoff.org> | 2015-02-10 23:24:01 +0000 |
commit | 1c323bd4cbb388a9e7515a1f733a3062bf093aee (patch) | |
tree | 7cc525d79149d44840b9f7a0040aaf3e69ecd665 /src/ats/gnunet-service-ats_normalization.c | |
parent | aedaaed687db1ff20b447378f01ad7306921450c (diff) | |
download | gnunet-1c323bd4cbb388a9e7515a1f733a3062bf093aee.tar.gz gnunet-1c323bd4cbb388a9e7515a1f733a3062bf093aee.zip |
fixing #3657 (replace ATS_Information with struct), but WIHTOUT fixing ATS testcases yet
Diffstat (limited to 'src/ats/gnunet-service-ats_normalization.c')
-rw-r--r-- | src/ats/gnunet-service-ats_normalization.c | 299 |
1 files changed, 125 insertions, 174 deletions
diff --git a/src/ats/gnunet-service-ats_normalization.c b/src/ats/gnunet-service-ats_normalization.c index 936f8ca34..c10e5070f 100644 --- a/src/ats/gnunet-service-ats_normalization.c +++ b/src/ats/gnunet-service-ats_normalization.c | |||
@@ -37,103 +37,65 @@ | |||
37 | /** | 37 | /** |
38 | * Range information for normalization of quality properties. | 38 | * Range information for normalization of quality properties. |
39 | */ | 39 | */ |
40 | struct Property | 40 | struct PropertyRange |
41 | { | 41 | { |
42 | /** | 42 | /** |
43 | * Index into the properties array. | ||
44 | */ | ||
45 | uint32_t prop_type; | ||
46 | |||
47 | /** | ||
48 | * Corresponding enum value of the respective quality property. | ||
49 | */ | ||
50 | enum GNUNET_ATS_Property atsi_type; | ||
51 | |||
52 | /** | ||
53 | * Minimum value we see for this property across all addresses. | 43 | * Minimum value we see for this property across all addresses. |
54 | */ | 44 | */ |
55 | uint32_t min; | 45 | struct GNUNET_ATS_Properties min; |
56 | 46 | ||
57 | /** | 47 | /** |
58 | * Maximum value we see for this property across all addresses. | 48 | * Maximum value we see for this property across all addresses. |
59 | */ | 49 | */ |
60 | uint32_t max; | 50 | struct GNUNET_ATS_Properties max; |
61 | }; | 51 | }; |
62 | 52 | ||
63 | 53 | ||
64 | /** | 54 | /** |
65 | * Range information for all quality properties we see. | 55 | * Range information for all quality properties we see. |
66 | */ | 56 | */ |
67 | static struct Property properties[GNUNET_ATS_QualityPropertiesCount]; | 57 | static struct PropertyRange property_range; |
68 | |||
69 | 58 | ||
70 | 59 | ||
71 | /** | 60 | /** |
72 | * Add the value from @a atsi to the running average of the | 61 | * Add the value from @a atsi to the running average of the |
73 | * given @a ni quality property. | 62 | * given @a ni quality property. |
74 | * | 63 | * |
64 | * @param current_val the updated value | ||
75 | * @param ni normalization information to update | 65 | * @param ni normalization information to update |
76 | * @param atsi the ats information | ||
77 | */ | 66 | */ |
78 | static void | 67 | static void |
79 | property_average (struct GAS_NormalizationInfo *ni, | 68 | update_avg (uint64_t current_val, |
80 | const struct GNUNET_ATS_Information *atsi) | 69 | struct GAS_NormalizationInfo *ni) |
81 | { | 70 | { |
82 | uint32_t current_val; | 71 | double sum; |
83 | uint32_t res; | ||
84 | uint64_t sum; | ||
85 | uint32_t count; | 72 | uint32_t count; |
86 | unsigned int c1; | 73 | unsigned int c1; |
87 | 74 | ||
88 | current_val = ntohl (atsi->value); | ||
89 | GNUNET_assert (GNUNET_ATS_VALUE_UNDEFINED != current_val); | ||
90 | ni->atsi_abs[ni->avg_queue_index++] = current_val; | 75 | ni->atsi_abs[ni->avg_queue_index++] = current_val; |
91 | if (GAS_normalization_queue_length == ni->avg_queue_index) | 76 | if (GAS_normalization_queue_length == ni->avg_queue_index) |
92 | ni->avg_queue_index = 0; | 77 | ni->avg_queue_index = 0; |
93 | count = 0; | 78 | count = 0; |
94 | sum = 0; | 79 | sum = 0.0; |
95 | for (c1 = 0; c1 < GAS_normalization_queue_length; c1++) | 80 | for (c1 = 0; c1 < GAS_normalization_queue_length; c1++) |
96 | { | 81 | { |
97 | if (GNUNET_ATS_VALUE_UNDEFINED != ni->atsi_abs[c1]) | 82 | if (UINT64_MAX != ni->atsi_abs[c1]) |
98 | { | 83 | { |
99 | count++; | 84 | count++; |
100 | sum += ni->atsi_abs[c1]; | 85 | sum += (double) ni->atsi_abs[c1]; |
101 | } | 86 | } |
102 | } | 87 | } |
103 | GNUNET_assert (0 != count); | 88 | GNUNET_assert (0 != count); |
104 | res = sum / count; | 89 | ni->avg = sum / count; |
105 | ni->avg = res; | ||
106 | } | 90 | } |
107 | 91 | ||
108 | 92 | ||
109 | /** | 93 | /** |
110 | * Closure for #find_min_max_it(). | ||
111 | */ | ||
112 | struct FindMinMaxCtx | ||
113 | { | ||
114 | /** | ||
115 | * Property we are looking for. | ||
116 | */ | ||
117 | struct Property *p; | ||
118 | |||
119 | /** | ||
120 | * Set to mimimum value observed. | ||
121 | */ | ||
122 | uint32_t min; | ||
123 | |||
124 | /** | ||
125 | * Set to maximum value observed. | ||
126 | */ | ||
127 | uint32_t max; | ||
128 | }; | ||
129 | |||
130 | |||
131 | /** | ||
132 | * Function called for all addresses and peers to find the minimum and | 94 | * Function called for all addresses and peers to find the minimum and |
133 | * maximum (averaged) values for a given quality property. Given | 95 | * maximum (averaged) values for a given quality property. Given |
134 | * those, we can then calculate the normalized score. | 96 | * those, we can then calculate the normalized score. |
135 | * | 97 | * |
136 | * @param cls the `struct FindMinMaxCtx` | 98 | * @param cls the `struct PropertyRange` |
137 | * @param h which peer are we looking at (ignored) | 99 | * @param h which peer are we looking at (ignored) |
138 | * @param k the address for that peer | 100 | * @param k the address for that peer |
139 | * @return #GNUNET_OK (continue to iterate) | 101 | * @return #GNUNET_OK (continue to iterate) |
@@ -143,23 +105,55 @@ find_min_max_it (void *cls, | |||
143 | const struct GNUNET_PeerIdentity *h, | 105 | const struct GNUNET_PeerIdentity *h, |
144 | void *k) | 106 | void *k) |
145 | { | 107 | { |
146 | struct FindMinMaxCtx *find_res = cls; | 108 | struct PropertyRange *pr = cls; |
147 | const struct ATS_Address *a = k; | 109 | const struct ATS_Address *a = k; |
148 | 110 | ||
149 | find_res->max = GNUNET_MAX (find_res->max, | 111 | pr->max.utilization_out = GNUNET_MAX (pr->max.utilization_out, |
150 | a->atsin[find_res->p->prop_type].avg); | 112 | a->properties.utilization_out); |
151 | find_res->min = GNUNET_MIN (find_res->min, | 113 | pr->max.utilization_in = GNUNET_MAX (pr->max.utilization_in, |
152 | a->atsin[find_res->p->prop_type].avg); | 114 | a->properties.utilization_in); |
115 | pr->max.distance = GNUNET_MAX (pr->max.distance, | ||
116 | a->properties.distance); | ||
117 | pr->max.delay = GNUNET_TIME_relative_max (pr->max.delay, | ||
118 | a->properties.delay); | ||
119 | pr->min.utilization_out = GNUNET_MIN (pr->min.utilization_out, | ||
120 | a->properties.utilization_out); | ||
121 | pr->min.utilization_in = GNUNET_MIN (pr->min.utilization_in, | ||
122 | a->properties.utilization_in); | ||
123 | pr->min.distance = GNUNET_MIN (pr->min.distance, | ||
124 | a->properties.distance); | ||
125 | pr->min.delay = GNUNET_TIME_relative_min (pr->min.delay, | ||
126 | a->properties.delay); | ||
153 | return GNUNET_OK; | 127 | return GNUNET_OK; |
154 | } | 128 | } |
155 | 129 | ||
156 | 130 | ||
157 | /** | 131 | /** |
132 | * Compute the normalized value from the given @a ni range | ||
133 | * data and the average value. | ||
134 | * | ||
135 | * @param min minimum value | ||
136 | * @param max maximum value | ||
137 | * @param ni normalization information to update | ||
138 | */ | ||
139 | static void | ||
140 | update_norm (uint64_t min, | ||
141 | uint64_t max, | ||
142 | struct GAS_NormalizationInfo *ni) | ||
143 | { | ||
144 | /* max - 2 * min + avg_value / (max - min) */ | ||
145 | if (min < max) | ||
146 | ni->norm = DEFAULT_REL_QUALITY + (ni->avg - min) / (double) (max - min); | ||
147 | else | ||
148 | ni->norm = DEFAULT_REL_QUALITY; | ||
149 | } | ||
150 | |||
151 | |||
152 | /** | ||
158 | * Normalize the property value for a given address based | 153 | * Normalize the property value for a given address based |
159 | * on the range we know that property value has globally. | 154 | * on the range we know that property values have globally. |
160 | * | 155 | * |
161 | * @param cls the `struct Property` with details on the | 156 | * @param cls NULL |
162 | * property and its global range | ||
163 | * @param key which peer are we looking at (ignored) | 157 | * @param key which peer are we looking at (ignored) |
164 | * @param value the address for that peer, from where we get | 158 | * @param value the address for that peer, from where we get |
165 | * the original value and where we write the | 159 | * the original value and where we write the |
@@ -171,33 +165,20 @@ normalize_address (void *cls, | |||
171 | const struct GNUNET_PeerIdentity *key, | 165 | const struct GNUNET_PeerIdentity *key, |
172 | void *value) | 166 | void *value) |
173 | { | 167 | { |
174 | struct Property *p = cls; | ||
175 | struct ATS_Address *address = value; | 168 | struct ATS_Address *address = value; |
176 | double delta; | ||
177 | double update; | ||
178 | uint32_t avg_value; | ||
179 | |||
180 | avg_value = address->atsin[p->prop_type].avg; | ||
181 | delta = p->max - p->min; | ||
182 | /* max - 2 * min + avg_value / (max - min) */ | ||
183 | if (delta > DBL_EPSILON) | ||
184 | update = DEFAULT_REL_QUALITY + (avg_value - p->min) / delta; | ||
185 | else | ||
186 | update = DEFAULT_REL_QUALITY; | ||
187 | 169 | ||
188 | if (update == address->atsin[p->prop_type].norm) | 170 | update_norm (property_range.min.delay.rel_value_us, |
189 | return GNUNET_OK; | 171 | property_range.max.delay.rel_value_us, |
190 | address->atsin[p->prop_type].norm = update; | 172 | &address->norm_delay); |
191 | 173 | update_norm (property_range.min.distance, | |
192 | LOG (GNUNET_ERROR_TYPE_DEBUG, | 174 | property_range.max.distance, |
193 | "Normalize `%s' address %p's '%s' with value %u to range [%u..%u] = %.3f\n", | 175 | &address->norm_distance); |
194 | GNUNET_i2s (&address->peer), | 176 | update_norm (property_range.min.utilization_in, |
195 | address, | 177 | property_range.max.utilization_in, |
196 | GNUNET_ATS_print_property_type (p->atsi_type), | 178 | &address->norm_utilization_in); |
197 | address->atsin[p->prop_type].avg, | 179 | update_norm (property_range.min.utilization_out, |
198 | p->min, | 180 | property_range.max.utilization_out, |
199 | p->max, | 181 | &address->norm_utilization_out); |
200 | address->atsin[p->prop_type].norm); | ||
201 | return GNUNET_OK; | 182 | return GNUNET_OK; |
202 | } | 183 | } |
203 | 184 | ||
@@ -205,8 +186,7 @@ normalize_address (void *cls, | |||
205 | /** | 186 | /** |
206 | * Notify about change in normalized property. | 187 | * Notify about change in normalized property. |
207 | * | 188 | * |
208 | * @param cls the `struct Property` with details on the | 189 | * @param cls NULL |
209 | * property and its global range | ||
210 | * @param key which peer are we looking at (ignored) | 190 | * @param key which peer are we looking at (ignored) |
211 | * @param value the address for that peer | 191 | * @param value the address for that peer |
212 | * @return #GNUNET_OK (continue to iterate) | 192 | * @return #GNUNET_OK (continue to iterate) |
@@ -216,104 +196,84 @@ notify_change (void *cls, | |||
216 | const struct GNUNET_PeerIdentity *key, | 196 | const struct GNUNET_PeerIdentity *key, |
217 | void *value) | 197 | void *value) |
218 | { | 198 | { |
219 | struct Property *p = cls; | ||
220 | struct ATS_Address *address = value; | 199 | struct ATS_Address *address = value; |
221 | 200 | ||
222 | GAS_plugin_notify_property_changed (address, | 201 | GAS_plugin_notify_property_changed (address); |
223 | p->atsi_type, | ||
224 | address->atsin[p->prop_type].norm); | ||
225 | return GNUNET_OK; | 202 | return GNUNET_OK; |
226 | } | 203 | } |
227 | 204 | ||
228 | 205 | ||
229 | /** | 206 | /** |
207 | * Initialize property range to the values corresponding | ||
208 | * to an empty set. | ||
209 | * | ||
210 | * @param pr range to initialize | ||
211 | */ | ||
212 | static void | ||
213 | init_range (struct PropertyRange *pr) | ||
214 | { | ||
215 | memset (pr, 0, sizeof (struct PropertyRange)); | ||
216 | pr->min.utilization_out = UINT32_MAX; | ||
217 | pr->min.utilization_in = UINT32_MAX; | ||
218 | pr->min.distance = UINT32_MAX; | ||
219 | pr->min.delay = GNUNET_TIME_UNIT_FOREVER_REL; | ||
220 | } | ||
221 | |||
222 | |||
223 | /** | ||
230 | * Update and normalize atsi performance information | 224 | * Update and normalize atsi performance information |
231 | * | 225 | * |
232 | * @param address the address to update | 226 | * @param address the address to update |
233 | * @param atsi the array of performance information | ||
234 | * @param atsi_count the number of atsi information in the array | ||
235 | */ | 227 | */ |
236 | void | 228 | void |
237 | GAS_normalization_update_property (struct ATS_Address *address, | 229 | GAS_normalization_update_property (struct ATS_Address *address) |
238 | const struct GNUNET_ATS_Information *atsi, | ||
239 | uint32_t atsi_count) | ||
240 | { | 230 | { |
241 | unsigned int c1; | 231 | const struct GNUNET_ATS_Properties *prop = &address->properties; |
242 | unsigned int c2; | 232 | struct PropertyRange range; |
243 | uint32_t current_type; | ||
244 | uint32_t old; | ||
245 | struct FindMinMaxCtx find_ctx; | ||
246 | int range_changed; | 233 | int range_changed; |
247 | 234 | ||
248 | LOG (GNUNET_ERROR_TYPE_DEBUG, | 235 | LOG (GNUNET_ERROR_TYPE_DEBUG, |
249 | "Updating %u elements for peer `%s'\n", | 236 | "Updating properties for peer `%s'\n", |
250 | atsi_count, | ||
251 | GNUNET_i2s (&address->peer)); | 237 | GNUNET_i2s (&address->peer)); |
252 | GAS_plugin_solver_lock (); | 238 | GAS_plugin_solver_lock (); |
253 | for (c1 = 0; c1 < atsi_count; c1++) | 239 | update_avg (prop->delay.rel_value_us, |
240 | &address->norm_delay); | ||
241 | update_avg (prop->distance, | ||
242 | &address->norm_distance); | ||
243 | update_avg (prop->utilization_in, | ||
244 | &address->norm_utilization_in); | ||
245 | update_avg (prop->utilization_in, | ||
246 | &address->norm_utilization_out); | ||
247 | |||
248 | init_range (&range); | ||
249 | GNUNET_CONTAINER_multipeermap_iterate (GSA_addresses, | ||
250 | &find_min_max_it, | ||
251 | &range); | ||
252 | if (0 != memcmp (&range, | ||
253 | &property_range, | ||
254 | sizeof (struct PropertyRange))) | ||
254 | { | 255 | { |
255 | current_type = ntohl (atsi[c1].type); | 256 | /* limits changed, (re)normalize all addresses */ |
256 | 257 | property_range = range; | |
257 | for (c2 = 0; c2 < GNUNET_ATS_QualityPropertiesCount; c2++) | 258 | range_changed = GNUNET_YES; |
258 | if (current_type == properties[c2].atsi_type) | ||
259 | break; | ||
260 | if (GNUNET_ATS_QualityPropertiesCount == c2) | ||
261 | { | ||
262 | /* Not a quality property, continue with next element */ | ||
263 | continue; | ||
264 | } | ||
265 | /* Calculate running average */ | ||
266 | old = address->atsin[c2].avg; | ||
267 | property_average (&address->atsin[c2], | ||
268 | &atsi[c1]); | ||
269 | if (old == address->atsin[c2].avg) | ||
270 | continue; /* no change */ | ||
271 | range_changed = GNUNET_NO; | ||
272 | if ( (old == properties[c2].min) || | ||
273 | (old == properties[c2].max) || | ||
274 | (address->atsin[c2].avg < properties[c2].min) || | ||
275 | (address->atsin[c2].avg > properties[c2].max) ) | ||
276 | { | ||
277 | /* need to re-calculate min/max range, as it may have changed */ | ||
278 | find_ctx.p = &properties[c2]; | ||
279 | find_ctx.max = 0; | ||
280 | find_ctx.min = UINT32_MAX; | ||
281 | if (0 == | ||
282 | GNUNET_CONTAINER_multipeermap_iterate (GSA_addresses, | ||
283 | &find_min_max_it, | ||
284 | &find_ctx)) | ||
285 | { | ||
286 | GNUNET_break(0); | ||
287 | continue; | ||
288 | } | ||
289 | if ( (find_ctx.min != properties[c2].min) || | ||
290 | (find_ctx.max != properties[c2].max) ) | ||
291 | { | ||
292 | properties[c2].min = find_ctx.min; | ||
293 | properties[c2].max = find_ctx.max; | ||
294 | /* limits changed, (re)normalize all addresses */ | ||
295 | range_changed = GNUNET_YES; | ||
296 | } | ||
297 | } | ||
298 | if (GNUNET_YES == range_changed) | ||
299 | GNUNET_CONTAINER_multipeermap_iterate (GSA_addresses, | ||
300 | &normalize_address, | ||
301 | &properties[c2]); | ||
302 | else | ||
303 | normalize_address (&properties[c2], | ||
304 | &address->peer, | ||
305 | address); | ||
306 | /* after all peers have been updated, notify about changes */ | ||
307 | if (GNUNET_YES == range_changed) | ||
308 | GNUNET_CONTAINER_multipeermap_iterate (GSA_addresses, | ||
309 | ¬ify_change, | ||
310 | &properties[c2]); | ||
311 | else | ||
312 | notify_change (&properties[c2], | ||
313 | &address->peer, | ||
314 | address); | ||
315 | |||
316 | } | 259 | } |
260 | if (GNUNET_YES == range_changed) | ||
261 | GNUNET_CONTAINER_multipeermap_iterate (GSA_addresses, | ||
262 | &normalize_address, | ||
263 | NULL); | ||
264 | else | ||
265 | normalize_address (NULL, | ||
266 | &address->peer, | ||
267 | address); | ||
268 | /* after all peers have been updated, notify about changes */ | ||
269 | if (GNUNET_YES == range_changed) | ||
270 | GNUNET_CONTAINER_multipeermap_iterate (GSA_addresses, | ||
271 | ¬ify_change, | ||
272 | NULL); | ||
273 | else | ||
274 | notify_change (NULL, | ||
275 | &address->peer, | ||
276 | address); | ||
317 | GAS_plugin_solver_unlock (); | 277 | GAS_plugin_solver_unlock (); |
318 | } | 278 | } |
319 | 279 | ||
@@ -324,16 +284,7 @@ GAS_normalization_update_property (struct ATS_Address *address, | |||
324 | void | 284 | void |
325 | GAS_normalization_start () | 285 | GAS_normalization_start () |
326 | { | 286 | { |
327 | unsigned int c1; | 287 | init_range (&property_range); |
328 | const unsigned int existing_properties[] = GNUNET_ATS_QualityProperties; | ||
329 | |||
330 | for (c1 = 0; c1 < GNUNET_ATS_QualityPropertiesCount; c1++) | ||
331 | { | ||
332 | properties[c1].prop_type = c1; | ||
333 | properties[c1].atsi_type = existing_properties[c1]; | ||
334 | properties[c1].min = UINT32_MAX; | ||
335 | properties[c1].max = 0; | ||
336 | } | ||
337 | } | 288 | } |
338 | 289 | ||
339 | 290 | ||