diff options
Diffstat (limited to 'src/rps/rps-sampler_client.c')
-rw-r--r-- | src/rps/rps-sampler_client.c | 175 |
1 files changed, 86 insertions, 89 deletions
diff --git a/src/rps/rps-sampler_client.c b/src/rps/rps-sampler_client.c index 64ae2dedd..b4ac5f6f8 100644 --- a/src/rps/rps-sampler_client.c +++ b/src/rps/rps-sampler_client.c | |||
@@ -11,12 +11,12 @@ | |||
11 | WITHOUT ANY WARRANTY; without even the implied warranty of | 11 | WITHOUT ANY WARRANTY; without even the implied warranty of |
12 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | 12 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
13 | Affero General Public License for more details. | 13 | Affero General Public License for more details. |
14 | 14 | ||
15 | You should have received a copy of the GNU Affero General Public License | 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/>. | 16 | along with this program. If not, see <http://www.gnu.org/licenses/>. |
17 | 17 | ||
18 | SPDX-License-Identifier: AGPL3.0-or-later | 18 | SPDX-License-Identifier: AGPL3.0-or-later |
19 | */ | 19 | */ |
20 | 20 | ||
21 | /** | 21 | /** |
22 | * @file rps/gnunet-service-rps_sampler.c | 22 | * @file rps/gnunet-service-rps_sampler.c |
@@ -37,7 +37,7 @@ | |||
37 | 37 | ||
38 | #include "rps-test_util.h" | 38 | #include "rps-test_util.h" |
39 | 39 | ||
40 | #define LOG(kind, ...) GNUNET_log_from(kind,"rps-sampler",__VA_ARGS__) | 40 | #define LOG(kind, ...) GNUNET_log_from(kind, "rps-sampler", __VA_ARGS__) |
41 | 41 | ||
42 | 42 | ||
43 | // multiple 'clients'? | 43 | // multiple 'clients'? |
@@ -49,8 +49,8 @@ | |||
49 | // hist_size_init, hist_size_max | 49 | // hist_size_init, hist_size_max |
50 | 50 | ||
51 | /*********************************************************************** | 51 | /*********************************************************************** |
52 | * WARNING: This section needs to be reviewed regarding the use of | 52 | * WARNING: This section needs to be reviewed regarding the use of |
53 | * functions providing (pseudo)randomness! | 53 | * functions providing (pseudo)randomness! |
54 | ***********************************************************************/ | 54 | ***********************************************************************/ |
55 | 55 | ||
56 | // TODO care about invalid input of the caller (size 0 or less...) | 56 | // TODO care about invalid input of the caller (size 0 or less...) |
@@ -68,8 +68,7 @@ typedef void | |||
68 | * | 68 | * |
69 | * Meant to be an entry in an DLL. | 69 | * Meant to be an entry in an DLL. |
70 | */ | 70 | */ |
71 | struct SamplerNotifyUpdateCTX | 71 | struct SamplerNotifyUpdateCTX { |
72 | { | ||
73 | /** | 72 | /** |
74 | * @brief The Callback to call on updates | 73 | * @brief The Callback to call on updates |
75 | */ | 74 | */ |
@@ -107,14 +106,13 @@ typedef void | |||
107 | * corrsponding peer to the client. | 106 | * corrsponding peer to the client. |
108 | */ | 107 | */ |
109 | static void | 108 | static void |
110 | sampler_mod_get_rand_peer (void *cls); | 109 | sampler_mod_get_rand_peer(void *cls); |
111 | 110 | ||
112 | 111 | ||
113 | /** | 112 | /** |
114 | * Closure to _get_n_rand_peers_ready_cb() | 113 | * Closure to _get_n_rand_peers_ready_cb() |
115 | */ | 114 | */ |
116 | struct RPS_SamplerRequestHandle | 115 | struct RPS_SamplerRequestHandle { |
117 | { | ||
118 | /** | 116 | /** |
119 | * DLL | 117 | * DLL |
120 | */ | 118 | */ |
@@ -162,8 +160,7 @@ struct RPS_SamplerRequestHandle | |||
162 | /** | 160 | /** |
163 | * Closure to _get_rand_peer_info() | 161 | * Closure to _get_rand_peer_info() |
164 | */ | 162 | */ |
165 | struct RPS_SamplerRequestHandleSingleInfo | 163 | struct RPS_SamplerRequestHandleSingleInfo { |
166 | { | ||
167 | /** | 164 | /** |
168 | * DLL | 165 | * DLL |
169 | */ | 166 | */ |
@@ -233,8 +230,8 @@ static uint32_t client_get_index; | |||
233 | * @return a handle to a sampler that consists of sampler elements. | 230 | * @return a handle to a sampler that consists of sampler elements. |
234 | */ | 231 | */ |
235 | struct RPS_Sampler * | 232 | struct RPS_Sampler * |
236 | RPS_sampler_mod_init (size_t init_size, | 233 | RPS_sampler_mod_init(size_t init_size, |
237 | struct GNUNET_TIME_Relative max_round_interval) | 234 | struct GNUNET_TIME_Relative max_round_interval) |
238 | { | 235 | { |
239 | struct RPS_Sampler *sampler; | 236 | struct RPS_Sampler *sampler; |
240 | 237 | ||
@@ -242,7 +239,7 @@ RPS_sampler_mod_init (size_t init_size, | |||
242 | min_size = 10; // TODO make input to _samplers_init() | 239 | min_size = 10; // TODO make input to _samplers_init() |
243 | max_size = 1000; // TODO make input to _samplers_init() | 240 | max_size = 1000; // TODO make input to _samplers_init() |
244 | 241 | ||
245 | sampler = GNUNET_new (struct RPS_Sampler); | 242 | sampler = GNUNET_new(struct RPS_Sampler); |
246 | sampler->max_round_interval = max_round_interval; | 243 | sampler->max_round_interval = max_round_interval; |
247 | sampler->get_peers = sampler_mod_get_rand_peer; | 244 | sampler->get_peers = sampler_mod_get_rand_peer; |
248 | //sampler->sampler_elements = GNUNET_new_array(init_size, struct GNUNET_PeerIdentity); | 245 | //sampler->sampler_elements = GNUNET_new_array(init_size, struct GNUNET_PeerIdentity); |
@@ -252,7 +249,7 @@ RPS_sampler_mod_init (size_t init_size, | |||
252 | 249 | ||
253 | //GNUNET_assert (init_size == sampler->sampler_size); | 250 | //GNUNET_assert (init_size == sampler->sampler_size); |
254 | 251 | ||
255 | RPS_sampler_resize (sampler, init_size); | 252 | RPS_sampler_resize(sampler, init_size); |
256 | 253 | ||
257 | return sampler; | 254 | return sampler; |
258 | } | 255 | } |
@@ -274,22 +271,22 @@ RPS_sampler_mod_init (size_t init_size, | |||
274 | * @return The estimated probability | 271 | * @return The estimated probability |
275 | */ | 272 | */ |
276 | static double | 273 | static double |
277 | prob_observed_n_peers (uint32_t num_peers_estim, | 274 | prob_observed_n_peers(uint32_t num_peers_estim, |
278 | uint32_t num_peers_observed, | 275 | uint32_t num_peers_observed, |
279 | double deficiency_factor) | 276 | double deficiency_factor) |
280 | { | 277 | { |
281 | uint32_t num_peers = num_peers_estim * (1/deficiency_factor); | 278 | uint32_t num_peers = num_peers_estim * (1 / deficiency_factor); |
282 | uint64_t sum = 0; | 279 | uint64_t sum = 0; |
283 | 280 | ||
284 | for (uint32_t i = 0; i < num_peers; i++) | 281 | for (uint32_t i = 0; i < num_peers; i++) |
285 | { | 282 | { |
286 | uint64_t a = pow (-1, num_peers-i); | 283 | uint64_t a = pow(-1, num_peers - i); |
287 | uint64_t b = binom (num_peers, i); | 284 | uint64_t b = binom(num_peers, i); |
288 | uint64_t c = pow (i, num_peers_observed); | 285 | uint64_t c = pow(i, num_peers_observed); |
289 | sum += a * b * c; | 286 | sum += a * b * c; |
290 | } | 287 | } |
291 | 288 | ||
292 | return sum / (double) pow (num_peers, num_peers_observed); | 289 | return sum / (double)pow(num_peers, num_peers_observed); |
293 | } | 290 | } |
294 | 291 | ||
295 | 292 | ||
@@ -299,7 +296,7 @@ prob_observed_n_peers (uint32_t num_peers_estim, | |||
299 | * This reinitialises the queried sampler element. | 296 | * This reinitialises the queried sampler element. |
300 | */ | 297 | */ |
301 | static void | 298 | static void |
302 | sampler_mod_get_rand_peer (void *cls) | 299 | sampler_mod_get_rand_peer(void *cls) |
303 | { | 300 | { |
304 | struct GetPeerCls *gpc = cls; | 301 | struct GetPeerCls *gpc = cls; |
305 | struct RPS_SamplerElement *s_elem; | 302 | struct RPS_SamplerElement *s_elem; |
@@ -310,72 +307,72 @@ sampler_mod_get_rand_peer (void *cls) | |||
310 | 307 | ||
311 | gpc->get_peer_task = NULL; | 308 | gpc->get_peer_task = NULL; |
312 | gpc->notify_ctx = NULL; | 309 | gpc->notify_ctx = NULL; |
313 | GNUNET_assert ( (NULL != gpc->req_handle) || | 310 | GNUNET_assert((NULL != gpc->req_handle) || |
314 | (NULL != gpc->req_single_info_handle) ); | 311 | (NULL != gpc->req_single_info_handle)); |
315 | if (NULL != gpc->req_handle) | 312 | if (NULL != gpc->req_handle) |
316 | sampler = gpc->req_handle->sampler; | 313 | sampler = gpc->req_handle->sampler; |
317 | else | 314 | else |
318 | sampler = gpc->req_single_info_handle->sampler; | 315 | sampler = gpc->req_single_info_handle->sampler; |
319 | 316 | ||
320 | LOG (GNUNET_ERROR_TYPE_DEBUG, "Single peer was requested\n"); | 317 | LOG(GNUNET_ERROR_TYPE_DEBUG, "Single peer was requested\n"); |
321 | 318 | ||
322 | /* Cycle the #client_get_index one step further */ | 319 | /* Cycle the #client_get_index one step further */ |
323 | client_get_index = (client_get_index + 1) % sampler->sampler_size; | 320 | client_get_index = (client_get_index + 1) % sampler->sampler_size; |
324 | 321 | ||
325 | s_elem = sampler->sampler_elements[client_get_index]; | 322 | s_elem = sampler->sampler_elements[client_get_index]; |
326 | *gpc->id = s_elem->peer_id; | 323 | *gpc->id = s_elem->peer_id; |
327 | GNUNET_assert (NULL != s_elem); | 324 | GNUNET_assert(NULL != s_elem); |
328 | 325 | ||
329 | if (EMPTY == s_elem->is_empty) | 326 | if (EMPTY == s_elem->is_empty) |
330 | { | 327 | { |
331 | LOG (GNUNET_ERROR_TYPE_DEBUG, | 328 | LOG(GNUNET_ERROR_TYPE_DEBUG, |
332 | "Sampler_mod element empty, rescheduling.\n"); | 329 | "Sampler_mod element empty, rescheduling.\n"); |
333 | GNUNET_assert (NULL == gpc->notify_ctx); | 330 | GNUNET_assert(NULL == gpc->notify_ctx); |
334 | gpc->notify_ctx = | 331 | gpc->notify_ctx = |
335 | sampler_notify_on_update (sampler, | 332 | sampler_notify_on_update(sampler, |
336 | &sampler_mod_get_rand_peer, | 333 | &sampler_mod_get_rand_peer, |
337 | gpc); | 334 | gpc); |
338 | return; | 335 | return; |
339 | } | 336 | } |
340 | 337 | ||
341 | /* Check whether we may use this sampler to give it back to the client */ | 338 | /* Check whether we may use this sampler to give it back to the client */ |
342 | if (GNUNET_TIME_UNIT_FOREVER_ABS.abs_value_us != s_elem->last_client_request.abs_value_us) | 339 | if (GNUNET_TIME_UNIT_FOREVER_ABS.abs_value_us != s_elem->last_client_request.abs_value_us) |
343 | { | ||
344 | // TODO remove this condition at least for the client sampler | ||
345 | last_request_diff = | ||
346 | GNUNET_TIME_absolute_get_difference (s_elem->last_client_request, | ||
347 | GNUNET_TIME_absolute_get ()); | ||
348 | /* We're not going to give it back now if it was | ||
349 | * already requested by a client this round */ | ||
350 | if (last_request_diff.rel_value_us < sampler->max_round_interval.rel_value_us) | ||
351 | { | 340 | { |
352 | LOG (GNUNET_ERROR_TYPE_DEBUG, | 341 | // TODO remove this condition at least for the client sampler |
353 | "Last client request on this sampler was less than max round interval ago -- scheduling for later\n"); | 342 | last_request_diff = |
354 | ///* How many time remains untile the next round has started? */ | 343 | GNUNET_TIME_absolute_get_difference(s_elem->last_client_request, |
355 | //inv_last_request_diff = | 344 | GNUNET_TIME_absolute_get()); |
356 | // GNUNET_TIME_absolute_get_difference (last_request_diff, | 345 | /* We're not going to give it back now if it was |
357 | // sampler->max_round_interval); | 346 | * already requested by a client this round */ |
358 | // add a little delay | 347 | if (last_request_diff.rel_value_us < sampler->max_round_interval.rel_value_us) |
359 | /* Schedule it one round later */ | 348 | { |
360 | GNUNET_assert (NULL == gpc->notify_ctx); | 349 | LOG(GNUNET_ERROR_TYPE_DEBUG, |
350 | "Last client request on this sampler was less than max round interval ago -- scheduling for later\n"); | ||
351 | ///* How many time remains untile the next round has started? */ | ||
352 | //inv_last_request_diff = | ||
353 | // GNUNET_TIME_absolute_get_difference (last_request_diff, | ||
354 | // sampler->max_round_interval); | ||
355 | // add a little delay | ||
356 | /* Schedule it one round later */ | ||
357 | GNUNET_assert(NULL == gpc->notify_ctx); | ||
358 | gpc->notify_ctx = | ||
359 | sampler_notify_on_update(sampler, | ||
360 | &sampler_mod_get_rand_peer, | ||
361 | gpc); | ||
362 | return; | ||
363 | } | ||
364 | } | ||
365 | if (2 > s_elem->num_peers) | ||
366 | { | ||
367 | LOG(GNUNET_ERROR_TYPE_DEBUG, | ||
368 | "This s_elem saw less than two peers -- scheduling for later\n"); | ||
369 | GNUNET_assert(NULL == gpc->notify_ctx); | ||
361 | gpc->notify_ctx = | 370 | gpc->notify_ctx = |
362 | sampler_notify_on_update (sampler, | 371 | sampler_notify_on_update(sampler, |
363 | &sampler_mod_get_rand_peer, | 372 | &sampler_mod_get_rand_peer, |
364 | gpc); | 373 | gpc); |
365 | return; | 374 | return; |
366 | } | 375 | } |
367 | } | ||
368 | if (2 > s_elem->num_peers) | ||
369 | { | ||
370 | LOG (GNUNET_ERROR_TYPE_DEBUG, | ||
371 | "This s_elem saw less than two peers -- scheduling for later\n"); | ||
372 | GNUNET_assert (NULL == gpc->notify_ctx); | ||
373 | gpc->notify_ctx = | ||
374 | sampler_notify_on_update (sampler, | ||
375 | &sampler_mod_get_rand_peer, | ||
376 | gpc); | ||
377 | return; | ||
378 | } | ||
379 | /* compute probability */ | 376 | /* compute probability */ |
380 | /* Currently disabled due to numerical limitations */ | 377 | /* Currently disabled due to numerical limitations */ |
381 | //prob_observed_n = prob_observed_n_peers (sampler->num_peers_estim, | 378 | //prob_observed_n = prob_observed_n_peers (sampler->num_peers_estim, |
@@ -413,23 +410,23 @@ sampler_mod_get_rand_peer (void *cls) | |||
413 | // GNUNET_NO); | 410 | // GNUNET_NO); |
414 | 411 | ||
415 | num_observed = s_elem->num_peers; | 412 | num_observed = s_elem->num_peers; |
416 | RPS_sampler_elem_reinit (s_elem); | 413 | RPS_sampler_elem_reinit(s_elem); |
417 | s_elem->last_client_request = GNUNET_TIME_absolute_get (); | 414 | s_elem->last_client_request = GNUNET_TIME_absolute_get(); |
418 | 415 | ||
419 | if (NULL != gpc->req_handle) | 416 | if (NULL != gpc->req_handle) |
420 | { | 417 | { |
421 | GNUNET_CONTAINER_DLL_remove (gpc->req_handle->gpc_head, | 418 | GNUNET_CONTAINER_DLL_remove(gpc->req_handle->gpc_head, |
422 | gpc->req_handle->gpc_tail, | 419 | gpc->req_handle->gpc_tail, |
423 | gpc); | 420 | gpc); |
424 | } | 421 | } |
425 | else | 422 | else |
426 | { | 423 | { |
427 | GNUNET_CONTAINER_DLL_remove (gpc->req_single_info_handle->gpc_head, | 424 | GNUNET_CONTAINER_DLL_remove(gpc->req_single_info_handle->gpc_head, |
428 | gpc->req_single_info_handle->gpc_tail, | 425 | gpc->req_single_info_handle->gpc_tail, |
429 | gpc); | 426 | gpc); |
430 | } | 427 | } |
431 | gpc->cont (gpc->cont_cls, gpc->id, prob_observed_n, num_observed); | 428 | gpc->cont(gpc->cont_cls, gpc->id, prob_observed_n, num_observed); |
432 | GNUNET_free (gpc); | 429 | GNUNET_free(gpc); |
433 | } | 430 | } |
434 | 431 | ||
435 | 432 | ||