aboutsummaryrefslogtreecommitdiff
path: root/src/rps
diff options
context:
space:
mode:
authorJulius Bünger <buenger@mytum.de>2015-07-23 18:21:45 +0000
committerJulius Bünger <buenger@mytum.de>2015-07-23 18:21:45 +0000
commit66fa52570d0d9f29d8b6bf8bd4667c18931b3806 (patch)
tree90134869b5cd862a14f9858a7c9d757e7d13a951 /src/rps
parent5103dcbd8d3b1974aab07f57d919ef7dc66322fd (diff)
downloadgnunet-66fa52570d0d9f29d8b6bf8bd4667c18931b3806.tar.gz
gnunet-66fa52570d0d9f29d8b6bf8bd4667c18931b3806.zip
-split up sampler and sampler element
Diffstat (limited to 'src/rps')
-rw-r--r--src/rps/Makefile.am1
-rw-r--r--src/rps/gnunet-service-rps_sampler.c224
-rw-r--r--src/rps/gnunet-service-rps_sampler_elem.c169
-rw-r--r--src/rps/gnunet-service-rps_sampler_elem.h134
4 files changed, 305 insertions, 223 deletions
diff --git a/src/rps/Makefile.am b/src/rps/Makefile.am
index b1fd3d47b..fc0b9848d 100644
--- a/src/rps/Makefile.am
+++ b/src/rps/Makefile.am
@@ -48,6 +48,7 @@ endif
48 48
49gnunet_service_rps_SOURCES = \ 49gnunet_service_rps_SOURCES = \
50 gnunet-service-rps_sampler.h gnunet-service-rps_sampler.c \ 50 gnunet-service-rps_sampler.h gnunet-service-rps_sampler.c \
51 gnunet-service-rps_sampler_elem.h gnunet-service-rps_sampler_elem.c \
51 rps-test_util.h rps-test_util.c \ 52 rps-test_util.h rps-test_util.c \
52 gnunet-service-rps.c 53 gnunet-service-rps.c
53 54
diff --git a/src/rps/gnunet-service-rps_sampler.c b/src/rps/gnunet-service-rps_sampler.c
index 2ff718d5e..f1b8f32cf 100644
--- a/src/rps/gnunet-service-rps_sampler.c
+++ b/src/rps/gnunet-service-rps_sampler.c
@@ -28,6 +28,7 @@
28#include "rps.h" 28#include "rps.h"
29 29
30#include "gnunet-service-rps_sampler.h" 30#include "gnunet-service-rps_sampler.h"
31#include "gnunet-service-rps_sampler_elem.h"
31 32
32#include <math.h> 33#include <math.h>
33#include <inttypes.h> 34#include <inttypes.h>
@@ -52,68 +53,6 @@
52 53
53// TODO care about invalid input of the caller (size 0 or less...) 54// TODO care about invalid input of the caller (size 0 or less...)
54 55
55enum RPS_SamplerEmpty
56{
57 NOT_EMPTY = 0x0,
58 EMPTY = 0x1
59};
60
61/**
62 * A sampler element sampling one PeerID at a time.
63 */
64struct RPS_SamplerElement
65{
66 /**
67 * Min-wise linear permutation used by this sampler.
68 *
69 * This is an key later used by a hmac.
70 */
71 struct GNUNET_CRYPTO_AuthKey auth_key;
72
73 /**
74 * The PeerID this sampler currently samples.
75 */
76 struct GNUNET_PeerIdentity peer_id;
77
78 /**
79 * The according hash value of this PeerID.
80 */
81 struct GNUNET_HashCode peer_id_hash;
82
83
84 /**
85 * Time of last request.
86 */
87 struct GNUNET_TIME_Absolute last_client_request;
88
89 /**
90 * Flag that indicates that we are not holding a valid PeerID right now.
91 */
92 enum RPS_SamplerEmpty is_empty;
93
94 /**
95 * 'Birth'
96 */
97 struct GNUNET_TIME_Absolute birth;
98
99 /**
100 * How many times a PeerID was put in this sampler.
101 */
102 uint32_t num_peers;
103
104 /**
105 * How many times this sampler changed the peer_id.
106 */
107 uint32_t num_change;
108
109 /**
110 * The file name this sampler element should log to
111 */
112 #ifdef TO_FILE
113 char *file_name;
114 #endif /* TO_FILE */
115};
116
117/** 56/**
118 * Callback that is called from _get_rand_peer() when the PeerID is ready. 57 * Callback that is called from _get_rand_peer() when the PeerID is ready.
119 * 58 *
@@ -214,25 +153,6 @@ struct RPS_Sampler
214 struct RPS_SamplerElement **sampler_elements; 153 struct RPS_SamplerElement **sampler_elements;
215 154
216 /** 155 /**
217 * Number of sampler elements trash can holds.
218 */
219 unsigned int trash_can_size;
220
221 /**
222 * Trash can for old sampler elements.
223 * We need this to evaluate the sampler.
224 * TODO remove after evaluation
225 * and undo changes in
226 * sampler_resize
227 * sampler_empty
228 * sampler_init
229 * sampler_remove?
230 * sampler_reinitialise_by_value
231 * sampler_update
232 */
233 struct RPS_SamplerElement **trash_can;
234
235 /**
236 * Maximum time a round takes 156 * Maximum time a round takes
237 * 157 *
238 * Used in the context of RPS 158 * Used in the context of RPS
@@ -353,129 +273,6 @@ check_n_peers_ready (void *cls,
353 273
354 274
355/** 275/**
356 * Reinitialise a previously initialised sampler element.
357 *
358 * @param sampler pointer to the memory that keeps the value.
359 */
360 static void
361RPS_sampler_elem_reinit (struct RPS_SamplerElement *sampler_el)
362{
363 sampler_el->is_empty = EMPTY;
364
365 // I guess I don't need to call GNUNET_CRYPTO_hmac_derive_key()...
366 GNUNET_CRYPTO_random_block(GNUNET_CRYPTO_QUALITY_STRONG,
367 &(sampler_el->auth_key.key),
368 GNUNET_CRYPTO_HASH_LENGTH);
369
370 #ifdef TO_FILE
371 /* Create a file(-name) to store internals to */
372 char *name_buf;
373 name_buf = auth_key_to_string (sampler_el->auth_key);
374
375 sampler_el->file_name = create_file (name_buf);
376 GNUNET_free (name_buf);
377 #endif /* TO_FILE */
378
379 sampler_el->last_client_request = GNUNET_TIME_UNIT_FOREVER_ABS;
380
381 sampler_el->birth = GNUNET_TIME_absolute_get ();
382 sampler_el->num_peers = 0;
383 sampler_el->num_change = 0;
384}
385
386
387/**
388 * (Re)Initialise given Sampler with random min-wise independent function.
389 *
390 * In this implementation this means choosing an auth_key for later use in
391 * a hmac at random.
392 *
393 * @return a newly created RPS_SamplerElement which currently holds no id.
394 */
395 struct RPS_SamplerElement *
396RPS_sampler_elem_create (void)
397{
398 struct RPS_SamplerElement *s;
399
400 s = GNUNET_new (struct RPS_SamplerElement);
401
402 RPS_sampler_elem_reinit (s);
403
404 return s;
405}
406
407
408/**
409 * Input an PeerID into the given sampler element.
410 *
411 * @param sampler the sampler the @a s_elem belongs to.
412 * Needed to know the
413 */
414static void
415RPS_sampler_elem_next (struct RPS_SamplerElement *s_elem,
416 struct RPS_Sampler *sampler, /* TODO remove? */
417 const struct GNUNET_PeerIdentity *other)
418{
419 struct GNUNET_HashCode other_hash;
420
421 s_elem->num_peers++;
422
423 to_file (s_elem->file_name,
424 "Got id %s",
425 GNUNET_i2s_full (other));
426
427 if (0 == GNUNET_CRYPTO_cmp_peer_identity (other, &(s_elem->peer_id)))
428 {
429 LOG (GNUNET_ERROR_TYPE_DEBUG, " Got PeerID %s\n",
430 GNUNET_i2s (other));
431 LOG (GNUNET_ERROR_TYPE_DEBUG, "Have already PeerID %s\n",
432 GNUNET_i2s (&(s_elem->peer_id)));
433 }
434 else
435 {
436 GNUNET_CRYPTO_hmac(&s_elem->auth_key,
437 other,
438 sizeof(struct GNUNET_PeerIdentity),
439 &other_hash);
440
441 if (EMPTY == s_elem->is_empty)
442 {
443 LOG (GNUNET_ERROR_TYPE_DEBUG,
444 "Got PeerID %s; Simply accepting (was empty previously).\n",
445 GNUNET_i2s(other));
446 s_elem->peer_id = *other;
447 s_elem->peer_id_hash = other_hash;
448
449 s_elem->num_change++;
450 }
451 else if (0 > GNUNET_CRYPTO_hash_cmp (&other_hash, &s_elem->peer_id_hash))
452 {
453 LOG (GNUNET_ERROR_TYPE_DEBUG, " Got PeerID %s\n",
454 GNUNET_i2s (other));
455 LOG (GNUNET_ERROR_TYPE_DEBUG, "Discarding old PeerID %s\n",
456 GNUNET_i2s (&s_elem->peer_id));
457 s_elem->peer_id = *other;
458 s_elem->peer_id_hash = other_hash;
459
460 s_elem->num_change++;
461 }
462 else
463 {
464 LOG (GNUNET_ERROR_TYPE_DEBUG, " Got PeerID %s\n",
465 GNUNET_i2s (other));
466 LOG (GNUNET_ERROR_TYPE_DEBUG, "Keeping old PeerID %s\n",
467 GNUNET_i2s (&s_elem->peer_id));
468 }
469 }
470 s_elem->is_empty = NOT_EMPTY;
471
472 to_file (s_elem->file_name,
473 "Now holding %s",
474 GNUNET_i2s_full (&s_elem->peer_id));
475}
476
477
478/**
479 * Get the size of the sampler. 276 * Get the size of the sampler.
480 * 277 *
481 * @param sampler the sampler to return the size of. 278 * @param sampler the sampler to return the size of.
@@ -517,19 +314,12 @@ sampler_resize (struct RPS_Sampler *sampler, unsigned int new_size)
517 old_size, 314 old_size,
518 new_size); 315 new_size);
519 316
520 /* TODO Temporary store those to properly call the removeCB on those later? */
521 GNUNET_array_grow (sampler->trash_can,
522 sampler->trash_can_size,
523 old_size - new_size);
524 for (i = new_size ; i < old_size ; i++) 317 for (i = new_size ; i < old_size ; i++)
525 { 318 {
526 to_file (sampler->file_name, 319 to_file (sampler->file_name,
527 "-%" PRIu32 ": %s", 320 "-%" PRIu32 ": %s",
528 i, 321 i,
529 sampler->sampler_elements[i]->file_name); 322 sampler->sampler_elements[i]->file_name);
530 to_file (sampler->sampler_elements[i]->file_name,
531 "--- non-active");
532 sampler->trash_can[i - new_size] = sampler->sampler_elements[i];
533 } 323 }
534 324
535 GNUNET_array_grow (sampler->sampler_elements, 325 GNUNET_array_grow (sampler->sampler_elements,
@@ -632,8 +422,6 @@ RPS_sampler_init (size_t init_size,
632 422
633 sampler->sampler_size = 0; 423 sampler->sampler_size = 0;
634 sampler->sampler_elements = NULL; 424 sampler->sampler_elements = NULL;
635 sampler->trash_can_size = 0;
636 sampler->trash_can = NULL;
637 sampler->max_round_interval = max_round_interval; 425 sampler->max_round_interval = max_round_interval;
638 sampler->get_peers = sampler_get_rand_peer; 426 sampler->get_peers = sampler_get_rand_peer;
639 sampler->gpc_head = NULL; 427 sampler->gpc_head = NULL;
@@ -693,16 +481,9 @@ RPS_sampler_update (struct RPS_Sampler *sampler,
693 for (i = 0 ; i < sampler->sampler_size ; i++) 481 for (i = 0 ; i < sampler->sampler_size ; i++)
694 { 482 {
695 RPS_sampler_elem_next (sampler->sampler_elements[i], 483 RPS_sampler_elem_next (sampler->sampler_elements[i],
696 sampler,
697 id); 484 id);
698 } 485 }
699 486
700 for (i = 0 ; i < sampler->trash_can_size ; i++)
701 {
702 RPS_sampler_elem_next (sampler->trash_can[i],
703 sampler,
704 id);
705 }
706} 487}
707 488
708 489
@@ -728,9 +509,6 @@ RPS_sampler_reinitialise_by_value (struct RPS_Sampler *sampler,
728 LOG (GNUNET_ERROR_TYPE_DEBUG, "Reinitialising sampler\n"); 509 LOG (GNUNET_ERROR_TYPE_DEBUG, "Reinitialising sampler\n");
729 trash_entry = GNUNET_new (struct RPS_SamplerElement); 510 trash_entry = GNUNET_new (struct RPS_SamplerElement);
730 *trash_entry = *(sampler->sampler_elements[i]); 511 *trash_entry = *(sampler->sampler_elements[i]);
731 GNUNET_array_append (sampler->trash_can,
732 sampler->trash_can_size,
733 trash_entry);
734 to_file (trash_entry->file_name, 512 to_file (trash_entry->file_name,
735 "--- non-active"); 513 "--- non-active");
736 RPS_sampler_elem_reinit (sampler->sampler_elements[i]); 514 RPS_sampler_elem_reinit (sampler->sampler_elements[i]);
diff --git a/src/rps/gnunet-service-rps_sampler_elem.c b/src/rps/gnunet-service-rps_sampler_elem.c
new file mode 100644
index 000000000..16b9cb39e
--- /dev/null
+++ b/src/rps/gnunet-service-rps_sampler_elem.c
@@ -0,0 +1,169 @@
1/*
2 This file is part of GNUnet.
3 Copyright (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., 51 Franklin Street, Fifth Floor,
18 Boston, MA 02110-1301, 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
29#include "gnunet-service-rps_sampler_elem.h"
30
31#include <inttypes.h>
32
33#include "rps-test_util.h"
34
35#define LOG(kind, ...) GNUNET_log_from(kind,"rps-sampler_elem",__VA_ARGS__)
36
37
38// TODO check for overflows
39
40/***********************************************************************
41 * WARNING: This section needs to be reviewed regarding the use of
42 * functions providing (pseudo)randomness!
43***********************************************************************/
44
45// TODO care about invalid input of the caller (size 0 or less...)
46
47
48/**
49 * Reinitialise a previously initialised sampler element.
50 *
51 * @param sampler pointer to the memory that keeps the value.
52 */
53void
54RPS_sampler_elem_reinit (struct RPS_SamplerElement *sampler_el)
55{
56 sampler_el->is_empty = EMPTY;
57
58 // I guess I don't need to call GNUNET_CRYPTO_hmac_derive_key()...
59 GNUNET_CRYPTO_random_block(GNUNET_CRYPTO_QUALITY_STRONG,
60 &(sampler_el->auth_key.key),
61 GNUNET_CRYPTO_HASH_LENGTH);
62
63 #ifdef TO_FILE
64 /* Create a file(-name) to store internals to */
65 char *name_buf;
66 name_buf = auth_key_to_string (sampler_el->auth_key);
67
68 sampler_el->file_name = create_file (name_buf);
69 GNUNET_free (name_buf);
70 #endif /* TO_FILE */
71
72 sampler_el->last_client_request = GNUNET_TIME_UNIT_FOREVER_ABS;
73
74 sampler_el->birth = GNUNET_TIME_absolute_get ();
75 sampler_el->num_peers = 0;
76 sampler_el->num_change = 0;
77}
78
79
80/**
81 * (Re)Initialise given Sampler with random min-wise independent function.
82 *
83 * In this implementation this means choosing an auth_key for later use in
84 * a hmac at random.
85 *
86 * @return a newly created RPS_SamplerElement which currently holds no id.
87 */
88struct RPS_SamplerElement *
89RPS_sampler_elem_create (void)
90{
91 struct RPS_SamplerElement *s;
92
93 s = GNUNET_new (struct RPS_SamplerElement);
94
95 RPS_sampler_elem_reinit (s);
96
97 return s;
98}
99
100
101/**
102 * Input an PeerID into the given sampler element.
103 *
104 * @param sampler the sampler the @a s_elem belongs to.
105 * Needed to know the
106 */
107void
108RPS_sampler_elem_next (struct RPS_SamplerElement *s_elem,
109 const struct GNUNET_PeerIdentity *other)
110{
111 struct GNUNET_HashCode other_hash;
112
113 s_elem->num_peers++;
114
115 to_file (s_elem->file_name,
116 "Got id %s",
117 GNUNET_i2s_full (other));
118
119 if (0 == GNUNET_CRYPTO_cmp_peer_identity (other, &(s_elem->peer_id)))
120 {
121 LOG (GNUNET_ERROR_TYPE_DEBUG, " Got PeerID %s\n",
122 GNUNET_i2s (other));
123 LOG (GNUNET_ERROR_TYPE_DEBUG, "Have already PeerID %s\n",
124 GNUNET_i2s (&(s_elem->peer_id)));
125 }
126 else
127 {
128 GNUNET_CRYPTO_hmac(&s_elem->auth_key,
129 other,
130 sizeof(struct GNUNET_PeerIdentity),
131 &other_hash);
132
133 if (EMPTY == s_elem->is_empty)
134 {
135 LOG (GNUNET_ERROR_TYPE_DEBUG,
136 "Got PeerID %s; Simply accepting (was empty previously).\n",
137 GNUNET_i2s(other));
138 s_elem->peer_id = *other;
139 s_elem->peer_id_hash = other_hash;
140
141 s_elem->num_change++;
142 }
143 else if (0 > GNUNET_CRYPTO_hash_cmp (&other_hash, &s_elem->peer_id_hash))
144 {
145 LOG (GNUNET_ERROR_TYPE_DEBUG, " Got PeerID %s\n",
146 GNUNET_i2s (other));
147 LOG (GNUNET_ERROR_TYPE_DEBUG, "Discarding old PeerID %s\n",
148 GNUNET_i2s (&s_elem->peer_id));
149 s_elem->peer_id = *other;
150 s_elem->peer_id_hash = other_hash;
151
152 s_elem->num_change++;
153 }
154 else
155 {
156 LOG (GNUNET_ERROR_TYPE_DEBUG, " Got PeerID %s\n",
157 GNUNET_i2s (other));
158 LOG (GNUNET_ERROR_TYPE_DEBUG, "Keeping old PeerID %s\n",
159 GNUNET_i2s (&s_elem->peer_id));
160 }
161 }
162 s_elem->is_empty = NOT_EMPTY;
163
164 to_file (s_elem->file_name,
165 "Now holding %s",
166 GNUNET_i2s_full (&s_elem->peer_id));
167}
168
169/* end of gnunet-service-rps.c */
diff --git a/src/rps/gnunet-service-rps_sampler_elem.h b/src/rps/gnunet-service-rps_sampler_elem.h
new file mode 100644
index 000000000..cb9506d69
--- /dev/null
+++ b/src/rps/gnunet-service-rps_sampler_elem.h
@@ -0,0 +1,134 @@
1/*
2 This file is part of GNUnet.
3 Copyright (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., 51 Franklin Street, Fifth Floor,
18 Boston, MA 02110-1301, USA.
19*/
20
21/**
22 * @file rps/gnunet-service-rps_sampler_elem.h
23 * @brief sampler element implementation
24 * @author Julius Bünger
25 */
26
27#ifndef RPS_SAMPLER_ELEM_H
28#define RPS_SAMPLER_ELEM_H
29#include <inttypes.h>
30
31
32/***********************************************************************
33 * WARNING: This section needs to be reviewed regarding the use of
34 * functions providing (pseudo)randomness!
35 ***********************************************************************/
36
37/**
38 * Used to indicate whether a sampler element is empty.
39 */
40enum RPS_SamplerEmpty
41{
42 NOT_EMPTY = 0x0,
43 EMPTY = 0x1
44};
45
46/**
47 * A sampler element sampling one PeerID at a time.
48 */
49struct RPS_SamplerElement
50{
51 /**
52 * Min-wise linear permutation used by this sampler.
53 *
54 * This is an key later used by a hmac.
55 */
56 struct GNUNET_CRYPTO_AuthKey auth_key;
57
58 /**
59 * The PeerID this sampler currently samples.
60 */
61 struct GNUNET_PeerIdentity peer_id;
62
63 /**
64 * The according hash value of this PeerID.
65 */
66 struct GNUNET_HashCode peer_id_hash;
67
68
69 /**
70 * Time of last request.
71 */
72 struct GNUNET_TIME_Absolute last_client_request;
73
74 /**
75 * Flag that indicates that we are not holding a valid PeerID right now.
76 */
77 enum RPS_SamplerEmpty is_empty;
78
79 /**
80 * 'Birth'
81 */
82 struct GNUNET_TIME_Absolute birth;
83
84 /**
85 * How many times a PeerID was put in this sampler.
86 */
87 uint32_t num_peers;
88
89 /**
90 * How many times this sampler changed the peer_id.
91 */
92 uint32_t num_change;
93
94 /**
95 * The file name this sampler element should log to
96 */
97 char *file_name;
98};
99
100
101/**
102 * Reinitialise a previously initialised sampler element.
103 *
104 * @param sampler pointer to the memory that keeps the value.
105 */
106void
107RPS_sampler_elem_reinit (struct RPS_SamplerElement *sampler_el);
108
109
110/**
111 * (Re)Initialise given Sampler with random min-wise independent function.
112 *
113 * In this implementation this means choosing an auth_key for later use in
114 * a hmac at random.
115 *
116 * @return a newly created RPS_SamplerElement which currently holds no id.
117 */
118struct RPS_SamplerElement *
119RPS_sampler_elem_create (void);
120
121
122/**
123 * Input an PeerID into the given sampler element.
124 *
125 * @param sampler the sampler the @a s_elem belongs to.
126 * Needed to know the
127 */
128void
129RPS_sampler_elem_next (struct RPS_SamplerElement *s_elem,
130 const struct GNUNET_PeerIdentity *new_ID);
131
132
133#endif /* RPS_SAMPLER_ELEM_H */
134/* end of gnunet-service-rps.c */