diff options
author | Julius Bünger <buenger@mytum.de> | 2015-01-06 23:48:24 +0000 |
---|---|---|
committer | Julius Bünger <buenger@mytum.de> | 2015-01-06 23:48:24 +0000 |
commit | 23660470add3cd0de11e3e599f14ec59f80ef5c3 (patch) | |
tree | 7e4998968317db71913e05d6508194843b48584a /src/rps/gnunet-service-rps_sampler.c | |
parent | 933428cef51a444d9fcba0ef2a36c626cb337fa5 (diff) | |
download | gnunet-23660470add3cd0de11e3e599f14ec59f80ef5c3.tar.gz gnunet-23660470add3cd0de11e3e599f14ec59f80ef5c3.zip |
moved sampler functionality in file of its own
Diffstat (limited to 'src/rps/gnunet-service-rps_sampler.c')
-rw-r--r-- | src/rps/gnunet-service-rps_sampler.c | 677 |
1 files changed, 677 insertions, 0 deletions
diff --git a/src/rps/gnunet-service-rps_sampler.c b/src/rps/gnunet-service-rps_sampler.c new file mode 100644 index 000000000..f80a70108 --- /dev/null +++ b/src/rps/gnunet-service-rps_sampler.c | |||
@@ -0,0 +1,677 @@ | |||
1 | /* | ||
2 | This file is part of GNUnet. | ||
3 | (C) | ||
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., 59 Temple Place - Suite 330, | ||
18 | Boston, MA 02111-1307, USA. | ||
19 | */ | ||
20 | |||
21 | /** | ||
22 | * @file rps/gnunet-service-rps_sampler.c | ||
23 | * @brief sampler implementation | ||
24 | * @author Julius Bünger | ||
25 | */ | ||
26 | #include "platform.h" | ||
27 | #include "gnunet_util_lib.h" | ||
28 | #include "rps.h" | ||
29 | |||
30 | #include "gnunet-service-rps_sampler.h" | ||
31 | |||
32 | #include <math.h> | ||
33 | #include <inttypes.h> | ||
34 | |||
35 | #define LOG(kind, ...) GNUNET_log(kind, __VA_ARGS__) | ||
36 | |||
37 | // multiple 'clients'? | ||
38 | |||
39 | // TODO check for overflows | ||
40 | |||
41 | // TODO align message structs | ||
42 | |||
43 | // hist_size_init, hist_size_max | ||
44 | |||
45 | /*********************************************************************** | ||
46 | * WARNING: This section needs to be reviewed regarding the use of | ||
47 | * functions providing (pseudo)randomness! | ||
48 | ***********************************************************************/ | ||
49 | |||
50 | // TODO care about invalid input of the caller (size 0 or less...) | ||
51 | |||
52 | enum RPS_SamplerEmpty | ||
53 | { | ||
54 | NOT_EMPTY = 0x0, | ||
55 | EMPTY = 0x1 | ||
56 | }; | ||
57 | |||
58 | /** | ||
59 | * A sampler element sampling one PeerID at a time. | ||
60 | */ | ||
61 | struct RPS_SamplerElement | ||
62 | { | ||
63 | /** | ||
64 | * Min-wise linear permutation used by this sampler. | ||
65 | * | ||
66 | * This is an key later used by a hmac. | ||
67 | */ | ||
68 | struct GNUNET_CRYPTO_AuthKey auth_key; | ||
69 | |||
70 | /** | ||
71 | * The PeerID this sampler currently samples. | ||
72 | */ | ||
73 | struct GNUNET_PeerIdentity peer_id; | ||
74 | |||
75 | /** | ||
76 | * The according hash value of this PeerID. | ||
77 | */ | ||
78 | struct GNUNET_HashCode peer_id_hash; | ||
79 | |||
80 | /** | ||
81 | * Time of last request. | ||
82 | */ | ||
83 | struct GNUNET_TIME_Absolute last_request; | ||
84 | |||
85 | /** | ||
86 | * Flag that indicates that we are not holding a valid PeerID right now. | ||
87 | */ | ||
88 | enum RPS_SamplerEmpty is_empty; | ||
89 | }; | ||
90 | |||
91 | /** | ||
92 | * Sampler with its own array of SamplerElements | ||
93 | */ | ||
94 | struct RPS_Sampler | ||
95 | { | ||
96 | /** | ||
97 | * Number of sampler elements we hold. | ||
98 | */ | ||
99 | unsigned int sampler_size; | ||
100 | //size_t size; | ||
101 | |||
102 | /** | ||
103 | * All Samplers in one array. | ||
104 | */ | ||
105 | struct RPS_SamplerElement **sampler_elements; | ||
106 | |||
107 | /** | ||
108 | * Index to a sampler element. | ||
109 | * | ||
110 | * Gets cycled on every hist_request. | ||
111 | */ | ||
112 | uint64_t sampler_elem_index; | ||
113 | |||
114 | /** | ||
115 | * Callback to be called when a peer gets inserted into a sampler. | ||
116 | */ | ||
117 | RPS_sampler_insert_cb insert_cb; | ||
118 | |||
119 | /** | ||
120 | * Closure to the insert_cb. | ||
121 | */ | ||
122 | void *insert_cls; | ||
123 | |||
124 | /** | ||
125 | * Callback to be called when a peer gets inserted into a sampler. | ||
126 | */ | ||
127 | RPS_sampler_remove_cb remove_cb; | ||
128 | |||
129 | /** | ||
130 | * Closure to the remove_cb. | ||
131 | */ | ||
132 | void *remove_cls; | ||
133 | }; | ||
134 | |||
135 | /** | ||
136 | * Global sampler variable. | ||
137 | */ | ||
138 | struct RPS_Sampler *sampler; | ||
139 | |||
140 | |||
141 | /** | ||
142 | * The minimal size for the extended sampler elements. | ||
143 | */ | ||
144 | static size_t min_size; | ||
145 | |||
146 | /** | ||
147 | * The maximal size the extended sampler elements should grow to. | ||
148 | */ | ||
149 | static size_t max_size; | ||
150 | |||
151 | /** | ||
152 | * The size the extended sampler elements currently have. | ||
153 | */ | ||
154 | static size_t extra_size; | ||
155 | |||
156 | /** | ||
157 | * Inedex to the sampler element that is the next to be returned | ||
158 | */ | ||
159 | static struct RPS_SamplerElement **extended_samplers_index; | ||
160 | |||
161 | /** | ||
162 | * Request counter. | ||
163 | * | ||
164 | * Only needed in the beginning to check how many of the 64 deltas | ||
165 | * we already have | ||
166 | */ | ||
167 | static unsigned int req_counter; | ||
168 | |||
169 | /** | ||
170 | * Time of the last request we received. | ||
171 | * | ||
172 | * Used to compute the expected request rate. | ||
173 | */ | ||
174 | static struct GNUNET_TIME_Absolute last_request; | ||
175 | |||
176 | /** | ||
177 | * Last 64 deltas between requests | ||
178 | */ | ||
179 | static struct GNUNET_TIME_Relative request_deltas[64]; | ||
180 | |||
181 | /** | ||
182 | * The prediction of the rate of requests | ||
183 | */ | ||
184 | static struct GNUNET_TIME_Relative request_rate; | ||
185 | |||
186 | |||
187 | /** | ||
188 | * Sum all time relatives of an array. | ||
189 | */ | ||
190 | struct GNUNET_TIME_Relative | ||
191 | T_relative_sum (const struct GNUNET_TIME_Relative *rel_array, uint64_t arr_size) | ||
192 | { | ||
193 | struct GNUNET_TIME_Relative sum; | ||
194 | uint64_t i; | ||
195 | |||
196 | sum = GNUNET_TIME_UNIT_ZERO; | ||
197 | for ( i = 0 ; i < arr_size ; i++ ) | ||
198 | { | ||
199 | sum = GNUNET_TIME_relative_add (sum, rel_array[i]); | ||
200 | } | ||
201 | return sum; | ||
202 | } | ||
203 | |||
204 | /** | ||
205 | * Compute the average of given time relatives. | ||
206 | */ | ||
207 | struct GNUNET_TIME_Relative | ||
208 | T_relative_avg (const struct GNUNET_TIME_Relative *rel_array, uint64_t arr_size) | ||
209 | { | ||
210 | return T_relative_sum (rel_array, arr_size); // FIXME find a way to devide that by arr_size | ||
211 | } | ||
212 | |||
213 | |||
214 | |||
215 | /** | ||
216 | * Reinitialise a previously initialised sampler element. | ||
217 | * | ||
218 | * @param sampler pointer to the memory that keeps the value. | ||
219 | */ | ||
220 | static void | ||
221 | RPS_sampler_elem_reinit (struct RPS_SamplerElement *sampler_el) | ||
222 | { | ||
223 | sampler_el->is_empty = EMPTY; | ||
224 | |||
225 | // I guess I don't need to call GNUNET_CRYPTO_hmac_derive_key()... | ||
226 | GNUNET_CRYPTO_random_block(GNUNET_CRYPTO_QUALITY_STRONG, | ||
227 | &(sampler_el->auth_key.key), | ||
228 | GNUNET_CRYPTO_HASH_LENGTH); | ||
229 | |||
230 | sampler_el->last_request = GNUNET_TIME_UNIT_FOREVER_ABS; | ||
231 | |||
232 | /* We might want to keep the previous peer */ | ||
233 | |||
234 | //GNUNET_CRYPTO_hmac(&sampler_el->auth_key, sampler_el->peer_id, | ||
235 | // sizeof(struct GNUNET_PeerIdentity), | ||
236 | // &sampler_el->peer_id_hash); | ||
237 | } | ||
238 | |||
239 | |||
240 | /** | ||
241 | * (Re)Initialise given Sampler with random min-wise independent function. | ||
242 | * | ||
243 | * In this implementation this means choosing an auth_key for later use in | ||
244 | * a hmac at random. | ||
245 | * | ||
246 | * @return a newly created RPS_SamplerElement which currently holds no id. | ||
247 | */ | ||
248 | struct RPS_SamplerElement * | ||
249 | RPS_sampler_elem_create (void) | ||
250 | { | ||
251 | struct RPS_SamplerElement *s; | ||
252 | |||
253 | s = GNUNET_new (struct RPS_SamplerElement); | ||
254 | |||
255 | RPS_sampler_elem_reinit (s); | ||
256 | LOG (GNUNET_ERROR_TYPE_DEBUG, "SAMPLER: initialised with empty PeerID\n"); | ||
257 | |||
258 | return s; | ||
259 | } | ||
260 | |||
261 | |||
262 | /** | ||
263 | * Input an PeerID into the given sampler. | ||
264 | */ | ||
265 | static void | ||
266 | RPS_sampler_elem_next (struct RPS_SamplerElement *s_elem, const struct GNUNET_PeerIdentity *other, | ||
267 | RPS_sampler_insert_cb insert_cb, void *insert_cls, | ||
268 | RPS_sampler_remove_cb remove_cb, void *remove_cls) | ||
269 | { | ||
270 | struct GNUNET_HashCode other_hash; | ||
271 | |||
272 | if ( 0 == GNUNET_CRYPTO_cmp_peer_identity(other, &(s_elem->peer_id)) ) | ||
273 | { | ||
274 | LOG(GNUNET_ERROR_TYPE_DEBUG, "SAMPLER: Got PeerID %s_elem\n", | ||
275 | GNUNET_i2s(other)); | ||
276 | LOG(GNUNET_ERROR_TYPE_DEBUG, "SAMPLER: Have already PeerID %s_elem\n", | ||
277 | GNUNET_i2s(&(s_elem->peer_id))); | ||
278 | } | ||
279 | else | ||
280 | { | ||
281 | GNUNET_CRYPTO_hmac(&s_elem->auth_key, | ||
282 | other, | ||
283 | sizeof(struct GNUNET_PeerIdentity), | ||
284 | &other_hash); | ||
285 | |||
286 | if ( EMPTY == s_elem->is_empty ) | ||
287 | { // Or whatever is a valid way to say | ||
288 | // "we have no PeerID at the moment" | ||
289 | LOG(GNUNET_ERROR_TYPE_DEBUG, "SAMPLER: Got PeerID %s_elem; Simply accepting (was empty previously).\n", | ||
290 | GNUNET_i2s(other)); | ||
291 | s_elem->peer_id = *other; | ||
292 | //s_elem->peer_id = other; | ||
293 | s_elem->peer_id_hash = other_hash; | ||
294 | if (NULL != sampler->insert_cb) | ||
295 | { | ||
296 | sampler->insert_cb(sampler->insert_cls, &(s_elem->peer_id)); | ||
297 | } | ||
298 | } | ||
299 | else if ( 0 > GNUNET_CRYPTO_hash_cmp(&other_hash, &s_elem->peer_id_hash) ) | ||
300 | { | ||
301 | LOG(GNUNET_ERROR_TYPE_DEBUG, "SAMPLER: Got PeerID %s_elem\n", | ||
302 | GNUNET_i2s(other)); | ||
303 | LOG(GNUNET_ERROR_TYPE_DEBUG, "SAMPLER: Discarding old PeerID %s_elem\n", | ||
304 | GNUNET_i2s(&s_elem->peer_id)); | ||
305 | |||
306 | if ( NULL != sampler->remove_cb ) | ||
307 | { | ||
308 | LOG(GNUNET_ERROR_TYPE_DEBUG, "SAMPLER: Removing old PeerID %s_elem with the remove callback.\n", | ||
309 | GNUNET_i2s(&s_elem->peer_id)); | ||
310 | sampler->remove_cb(sampler->remove_cls, &s_elem->peer_id); | ||
311 | } | ||
312 | |||
313 | memcpy(&s_elem->peer_id, other, sizeof(struct GNUNET_PeerIdentity)); | ||
314 | //s_elem->peer_id = other; | ||
315 | s_elem->peer_id_hash = other_hash; | ||
316 | |||
317 | if ( NULL != sampler->insert_cb ) | ||
318 | { | ||
319 | LOG(GNUNET_ERROR_TYPE_DEBUG, "SAMPLER: Inserting new PeerID %s_elem with the insert callback.\n", | ||
320 | GNUNET_i2s(&s_elem->peer_id)); | ||
321 | sampler->insert_cb(sampler->insert_cls, &s_elem->peer_id); | ||
322 | } | ||
323 | } | ||
324 | else | ||
325 | { | ||
326 | LOG(GNUNET_ERROR_TYPE_DEBUG, "SAMPLER: Got PeerID %s_elem\n", | ||
327 | GNUNET_i2s(other)); | ||
328 | LOG(GNUNET_ERROR_TYPE_DEBUG, "SAMPLER: Keeping old PeerID %s_elem\n", | ||
329 | GNUNET_i2s(&s_elem->peer_id)); | ||
330 | } | ||
331 | } | ||
332 | s_elem->is_empty = NOT_EMPTY; | ||
333 | } | ||
334 | |||
335 | |||
336 | /** | ||
337 | * Grow or shrink the size of the sampler. | ||
338 | * | ||
339 | * @param new_size the new size of the sampler | ||
340 | */ | ||
341 | void | ||
342 | RPS_sampler_resize (unsigned int new_size) | ||
343 | { | ||
344 | unsigned int old_size; | ||
345 | uint64_t i; | ||
346 | struct RPS_SamplerElement **rem_list; | ||
347 | |||
348 | // TODO check min and max size | ||
349 | |||
350 | old_size = sampler->sampler_size; | ||
351 | |||
352 | if (old_size > new_size*4 && | ||
353 | extra_size > new_size*4) | ||
354 | { /* Shrinking */ | ||
355 | |||
356 | new_size /= 2; | ||
357 | |||
358 | /* Temporary store those to properly call the removeCB on those later */ | ||
359 | rem_list = GNUNET_malloc ((old_size - new_size) * sizeof (struct RPS_SamplerElement *)); | ||
360 | memcpy (rem_list, | ||
361 | &sampler->sampler_elements[new_size], | ||
362 | (old_size - new_size) * sizeof(struct RPS_SamplerElement *)); | ||
363 | |||
364 | LOG (GNUNET_ERROR_TYPE_DEBUG, "SAMPLER: Shrinking sampler %d -> %d\n", old_size, new_size); | ||
365 | GNUNET_array_grow (sampler->sampler_elements, sampler->sampler_size, new_size); | ||
366 | LOG (GNUNET_ERROR_TYPE_DEBUG, | ||
367 | "SAMPLER: sampler->sampler_elements now points to %p\n", | ||
368 | sampler->sampler_elements); | ||
369 | |||
370 | // TODO move extended_samplers_index | ||
371 | for (i = new_size ; i < old_size ; i++) | ||
372 | {/* Remove unneeded rest */ | ||
373 | LOG (GNUNET_ERROR_TYPE_DEBUG, "SAMPLER: Removing %" PRIX64 ". sampler\n", i); | ||
374 | if (NULL != sampler->remove_cb) | ||
375 | sampler->remove_cb (sampler->remove_cls, &rem_list[i]->peer_id); | ||
376 | GNUNET_free (rem_list[i]); | ||
377 | } | ||
378 | } | ||
379 | else if (old_size < new_size)// || | ||
380 | //extra_size < new_size) // needed? | ||
381 | { /* Growing */ | ||
382 | new_size *= 2; // TODO check overflow | ||
383 | |||
384 | LOG (GNUNET_ERROR_TYPE_DEBUG, "SAMPLER: Growing sampler %d -> %d\n", old_size, new_size); | ||
385 | GNUNET_array_grow (sampler->sampler_elements, sampler->sampler_size, new_size); | ||
386 | LOG (GNUNET_ERROR_TYPE_DEBUG, | ||
387 | "SAMPLER: sampler->sampler_elements now points to %p\n", | ||
388 | sampler->sampler_elements); | ||
389 | |||
390 | // TODO move extended_samplers_index | ||
391 | |||
392 | for ( i = old_size ; i < new_size ; i++ ) | ||
393 | { /* Add new sampler elements */ | ||
394 | sampler->sampler_elements[i] = RPS_sampler_elem_create (); | ||
395 | if (NULL != sampler->insert_cb) | ||
396 | sampler->insert_cb (sampler->insert_cls, &sampler->sampler_elements[i]->peer_id); | ||
397 | LOG (GNUNET_ERROR_TYPE_DEBUG, | ||
398 | "SAMPLER: Added %" PRIX64 ". sampler, now pointing to %p, contains %s\n", | ||
399 | i, &sampler->sampler_elements[i], GNUNET_i2s (&sampler->sampler_elements[i]->peer_id)); | ||
400 | } | ||
401 | } | ||
402 | else | ||
403 | { | ||
404 | LOG (GNUNET_ERROR_TYPE_DEBUG, "SAMPLER: Size remains the same -- nothing to do\n"); | ||
405 | return; | ||
406 | } | ||
407 | |||
408 | GNUNET_assert(sampler->sampler_size == new_size); | ||
409 | LOG(GNUNET_ERROR_TYPE_DEBUG, "SAMPLER: Finished growing/shrinking.\n"); // remove | ||
410 | } | ||
411 | |||
412 | |||
413 | /** | ||
414 | * Initialise a tuple of sampler elements. | ||
415 | * | ||
416 | * @param init_size the size the sampler is initialised with | ||
417 | * @param id with which all newly created sampler elements are initialised | ||
418 | * @param ins_cb the callback that will be called on every PeerID that is | ||
419 | * newly inserted into a sampler element | ||
420 | * @param ins_cls the closure given to #ins_cb | ||
421 | * @param rem_cb the callback that will be called on every PeerID that is | ||
422 | * removed from a sampler element | ||
423 | * @param rem_cls the closure given to #rem_cb | ||
424 | */ | ||
425 | void | ||
426 | RPS_sampler_init (size_t init_size, const struct GNUNET_PeerIdentity *id, | ||
427 | RPS_sampler_insert_cb ins_cb, void *ins_cls, | ||
428 | RPS_sampler_remove_cb rem_cb, void *rem_cls) | ||
429 | { | ||
430 | //struct RPS_Sampler *sampler; | ||
431 | //uint64_t i; | ||
432 | |||
433 | /* Initialise context around extended sampler */ | ||
434 | min_size = 10; // TODO make input to _samplers_init() | ||
435 | max_size = 1000; // TODO make input to _samplers_init() | ||
436 | GNUNET_new_array (64, struct GNUNET_TIME_Relative); | ||
437 | |||
438 | sampler = GNUNET_new (struct RPS_Sampler); | ||
439 | sampler->sampler_size = 0; | ||
440 | sampler->sampler_elements = NULL; | ||
441 | sampler->insert_cb = ins_cb; | ||
442 | sampler->insert_cls = ins_cls; | ||
443 | sampler->remove_cb = rem_cb; | ||
444 | sampler->remove_cls = rem_cls; | ||
445 | //sampler->sampler_elements = GNUNET_new_array(init_size, struct GNUNET_PeerIdentity); | ||
446 | //GNUNET_array_grow (sampler->sampler_elements, sampler->sampler_size, min_size); | ||
447 | RPS_sampler_resize (init_size); | ||
448 | RPS_sampler_update_list (id); // no super nice desing but ok for the moment | ||
449 | |||
450 | extended_samplers_index = sampler->sampler_elements; | ||
451 | |||
452 | //GNUNET_assert (init_size == sampler->sampler_size); | ||
453 | } | ||
454 | |||
455 | |||
456 | /** | ||
457 | * A fuction to update every sampler in the given list | ||
458 | * | ||
459 | * @param id the PeerID that is put in the sampler | ||
460 | */ | ||
461 | void | ||
462 | RPS_sampler_update_list (const struct GNUNET_PeerIdentity *id) | ||
463 | { | ||
464 | uint64_t i; | ||
465 | |||
466 | for ( i = 0 ; i < sampler->sampler_size ; i++ ) | ||
467 | RPS_sampler_elem_next (sampler->sampler_elements[i], id, | ||
468 | sampler->insert_cb, sampler->insert_cls, | ||
469 | sampler->remove_cb, sampler->remove_cls); | ||
470 | } | ||
471 | |||
472 | |||
473 | /** | ||
474 | * Reinitialise all previously initialised sampler elements with the given value. | ||
475 | * | ||
476 | * Used to get rid of a PeerID. | ||
477 | * | ||
478 | * @param id the id of the sampler elements to update. | ||
479 | */ | ||
480 | void | ||
481 | RPS_sampler_reinitialise_by_value (const struct GNUNET_PeerIdentity *id) | ||
482 | { | ||
483 | uint64_t i; | ||
484 | |||
485 | for ( i = 0 ; i < sampler->sampler_size ; i++ ) | ||
486 | { | ||
487 | if ( 0 == GNUNET_CRYPTO_cmp_peer_identity(id, &(sampler->sampler_elements[i]->peer_id)) ) | ||
488 | { | ||
489 | LOG(GNUNET_ERROR_TYPE_DEBUG, "SAMPLER: Reinitialising sampler\n"); | ||
490 | RPS_sampler_elem_reinit (sampler->sampler_elements[i]); | ||
491 | } | ||
492 | } | ||
493 | } | ||
494 | |||
495 | |||
496 | /** | ||
497 | * Get one random peer out of the sampled peers. | ||
498 | * | ||
499 | * We might want to reinitialise this sampler after giving the | ||
500 | * corrsponding peer to the client. | ||
501 | * Only used internally | ||
502 | */ | ||
503 | const struct GNUNET_PeerIdentity * | ||
504 | RPS_sampler_get_rand_peer_ () | ||
505 | { | ||
506 | uint64_t r_index; | ||
507 | const struct GNUNET_PeerIdentity *peer; // do we have to malloc that? | ||
508 | |||
509 | // TODO implement extra logic | ||
510 | |||
511 | /**; | ||
512 | * Choose the r_index of the peer we want to return | ||
513 | * at random from the interval of the gossip list | ||
514 | */ | ||
515 | r_index = GNUNET_CRYPTO_random_u64(GNUNET_CRYPTO_QUALITY_STRONG, | ||
516 | sampler->sampler_size); | ||
517 | |||
518 | //if ( EMPTY == sampler->sampler_elements[r_index]->is_empty ) | ||
519 | // // TODO schedule for later | ||
520 | // peer = NULL; | ||
521 | //else | ||
522 | peer = &(sampler->sampler_elements[r_index]->peer_id); | ||
523 | sampler->sampler_elements[r_index]->last_request = GNUNET_TIME_absolute_get(); | ||
524 | LOG(GNUNET_ERROR_TYPE_DEBUG, "Sgrp: Returning PeerID %s\n", GNUNET_i2s(peer)); | ||
525 | |||
526 | |||
527 | return peer; | ||
528 | } | ||
529 | |||
530 | /** | ||
531 | * Get n random peers out of the sampled peers. | ||
532 | * | ||
533 | * We might want to reinitialise this sampler after giving the | ||
534 | * corrsponding peer to the client. | ||
535 | * Random with or without consumption? | ||
536 | * Only used internally | ||
537 | */ | ||
538 | const struct GNUNET_PeerIdentity * | ||
539 | RPS_sampler_get_n_rand_peers_ (uint64_t n) | ||
540 | { | ||
541 | if ( 0 == sampler->sampler_size ) | ||
542 | { | ||
543 | LOG (GNUNET_ERROR_TYPE_DEBUG, | ||
544 | "Sgrp: List empty - Returning NULL\n"); | ||
545 | return NULL; | ||
546 | } | ||
547 | else | ||
548 | { | ||
549 | // TODO check if we have too much (distinct) sampled peers | ||
550 | // If we are not ready yet maybe schedule for later | ||
551 | struct GNUNET_PeerIdentity *peers; | ||
552 | uint64_t i; | ||
553 | |||
554 | peers = GNUNET_malloc (n * sizeof(struct GNUNET_PeerIdentity)); | ||
555 | |||
556 | for ( i = 0 ; i < n ; i++ ) { | ||
557 | //peers[i] = RPS_sampler_get_rand_peer_(sampler->sampler_elements); | ||
558 | memcpy (&peers[i], RPS_sampler_get_rand_peer_ (), sizeof (struct GNUNET_PeerIdentity)); | ||
559 | } | ||
560 | return peers; | ||
561 | } | ||
562 | } | ||
563 | |||
564 | |||
565 | /** | ||
566 | * Get one random peer out of the sampled peers. | ||
567 | * | ||
568 | * We might want to reinitialise this sampler after giving the | ||
569 | * corrsponding peer to the client. | ||
570 | * | ||
571 | * @return a random PeerID of the PeerIDs previously put into the sampler. | ||
572 | */ | ||
573 | const struct GNUNET_PeerIdentity * | ||
574 | RPS_sampler_get_rand_peer () | ||
575 | { | ||
576 | struct GNUNET_PeerIdentity *peer; | ||
577 | |||
578 | if (64 > req_counter) | ||
579 | req_counter++; | ||
580 | if (1 < req_counter) | ||
581 | { | ||
582 | memcpy (&request_deltas[1], | ||
583 | request_deltas, | ||
584 | (req_counter - 1) * sizeof (struct GNUNET_TIME_Relative)); | ||
585 | request_deltas[0] = GNUNET_TIME_absolute_get_difference (last_request, | ||
586 | GNUNET_TIME_absolute_get ()); | ||
587 | request_rate = T_relative_avg (request_deltas, req_counter); | ||
588 | } | ||
589 | last_request = GNUNET_TIME_absolute_get(); | ||
590 | // TODO resize the size of the extended_samplers | ||
591 | |||
592 | // use _get_rand_peer_ ? | ||
593 | peer = GNUNET_new (struct GNUNET_PeerIdentity); | ||
594 | *peer = (*extended_samplers_index)->peer_id; | ||
595 | RPS_sampler_elem_reinit (*extended_samplers_index); | ||
596 | if ( extended_samplers_index == &sampler->sampler_elements[sampler->sampler_size -1] ) | ||
597 | extended_samplers_index = &sampler->sampler_elements[0]; | ||
598 | else | ||
599 | extended_samplers_index++; | ||
600 | // TODO | ||
601 | return peer; | ||
602 | } | ||
603 | |||
604 | |||
605 | /** | ||
606 | * Get n random peers out of the sampled peers. | ||
607 | * | ||
608 | * We might want to reinitialise this sampler after giving the | ||
609 | * corrsponding peer to the client. | ||
610 | * Random with or without consumption? | ||
611 | * | ||
612 | * @return n random PeerIDs of the PeerIDs previously put into the sampler. | ||
613 | */ | ||
614 | const struct GNUNET_PeerIdentity * | ||
615 | RPS_sampler_get_n_rand_peers (uint64_t n) | ||
616 | { | ||
617 | // use _get_rand_peers_ ? | ||
618 | if ( 0 == sampler->sampler_size ) | ||
619 | { | ||
620 | LOG (GNUNET_ERROR_TYPE_DEBUG, | ||
621 | "Sgrp: List empty - Returning NULL\n"); | ||
622 | return NULL; | ||
623 | } | ||
624 | else | ||
625 | { | ||
626 | // TODO check if we have too much (distinct) sampled peers | ||
627 | // If we are not ready yet maybe schedule for later | ||
628 | struct GNUNET_PeerIdentity *peers; | ||
629 | uint64_t i; | ||
630 | |||
631 | peers = GNUNET_malloc (n * sizeof(struct GNUNET_PeerIdentity)); | ||
632 | |||
633 | for ( i = 0 ; i < n ; i++ ) { | ||
634 | //peers[i] = RPS_sampler_get_rand_peer_(sampler->sampler_elements); | ||
635 | memcpy (&peers[i], RPS_sampler_get_rand_peer (), sizeof (struct GNUNET_PeerIdentity)); | ||
636 | } | ||
637 | return peers; | ||
638 | } | ||
639 | } | ||
640 | |||
641 | |||
642 | /** | ||
643 | * Counts how many Samplers currently hold a given PeerID. | ||
644 | * | ||
645 | * @param id the PeerID to count. | ||
646 | * | ||
647 | * @return the number of occurrences of id. | ||
648 | */ | ||
649 | uint64_t | ||
650 | RPS_sampler_count_id (const struct GNUNET_PeerIdentity *id) | ||
651 | { | ||
652 | uint64_t count; | ||
653 | uint64_t i; | ||
654 | |||
655 | count = 0; | ||
656 | for ( i = 0 ; i < sampler->sampler_size ; i++ ) | ||
657 | { | ||
658 | if ( 0 == GNUNET_CRYPTO_cmp_peer_identity (&sampler->sampler_elements[i]->peer_id, id) | ||
659 | && EMPTY != sampler->sampler_elements[i]->is_empty) | ||
660 | count++; | ||
661 | } | ||
662 | return count; | ||
663 | } | ||
664 | |||
665 | |||
666 | /** | ||
667 | * Cleans the sampler. | ||
668 | */ | ||
669 | void | ||
670 | RPS_sampler_destroy () | ||
671 | { | ||
672 | RPS_sampler_resize (0); | ||
673 | GNUNET_free (request_deltas); // _array_grow()? | ||
674 | GNUNET_array_grow (sampler->sampler_elements, sampler->sampler_size, 0); | ||
675 | } | ||
676 | |||
677 | /* end of gnunet-service-rps.c */ | ||