diff options
Diffstat (limited to 'src/nse/gnunet-service-nse.c')
-rw-r--r-- | src/nse/gnunet-service-nse.c | 1596 |
1 files changed, 0 insertions, 1596 deletions
diff --git a/src/nse/gnunet-service-nse.c b/src/nse/gnunet-service-nse.c deleted file mode 100644 index 8e9cd0c9d..000000000 --- a/src/nse/gnunet-service-nse.c +++ /dev/null | |||
@@ -1,1596 +0,0 @@ | |||
1 | /* | ||
2 | This file is part of GNUnet. | ||
3 | Copyright (C) 2009, 2010, 2011, 2012, 2013, 2016 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 nse/gnunet-service-nse.c | ||
23 | * @brief network size estimation service | ||
24 | * @author Nathan Evans | ||
25 | * @author Christian Grothoff | ||
26 | * | ||
27 | * The purpose of this service is to estimate the size of the network. | ||
28 | * Given a specified interval, each peer hashes the most recent | ||
29 | * timestamp which is evenly divisible by that interval. This hash is | ||
30 | * compared in distance to the peer identity to choose an offset. The | ||
31 | * closer the peer identity to the hashed timestamp, the earlier the | ||
32 | * peer sends out a "nearest peer" message. The closest peer's | ||
33 | * message should thus be received before any others, which stops | ||
34 | * those peer from sending their messages at a later duration. So | ||
35 | * every peer should receive the same nearest peer message, and from | ||
36 | * this can calculate the expected number of peers in the network. | ||
37 | */ | ||
38 | #include "platform.h" | ||
39 | #include <math.h> | ||
40 | #include "gnunet_util_lib.h" | ||
41 | #include "gnunet_constants.h" | ||
42 | #include "gnunet_protocols.h" | ||
43 | #include "gnunet_signatures.h" | ||
44 | #include "gnunet_statistics_service.h" | ||
45 | #include "gnunet_core_service.h" | ||
46 | #include "gnunet_nse_service.h" | ||
47 | #if ENABLE_NSE_HISTOGRAM | ||
48 | #include "gnunet_testbed_logger_service.h" | ||
49 | #endif | ||
50 | #include "nse.h" | ||
51 | #include <gcrypt.h> | ||
52 | |||
53 | |||
54 | /** | ||
55 | * Should messages be delayed randomly? This option should be set to | ||
56 | * #GNUNET_NO only for experiments, not in production. | ||
57 | */ | ||
58 | #define USE_RANDOM_DELAYS GNUNET_YES | ||
59 | |||
60 | /** | ||
61 | * Generate extensive debug-level log messages? | ||
62 | */ | ||
63 | #define DEBUG_NSE GNUNET_NO | ||
64 | |||
65 | /** | ||
66 | * Over how many values do we calculate the weighted average? | ||
67 | */ | ||
68 | #define HISTORY_SIZE 64 | ||
69 | |||
70 | /** | ||
71 | * Message priority to use. No real rush, reliability not | ||
72 | * required. Corking OK. | ||
73 | */ | ||
74 | #define NSE_PRIORITY \ | ||
75 | (GNUNET_MQ_PRIO_BACKGROUND | GNUNET_MQ_PREF_UNRELIABLE \ | ||
76 | | GNUNET_MQ_PREF_CORK_ALLOWED) | ||
77 | |||
78 | #ifdef BSD | ||
79 | #define log2(a) (log (a) / log (2)) | ||
80 | #endif | ||
81 | |||
82 | /** | ||
83 | * Amount of work required (W-bit collisions) for NSE proofs, in collision-bits. | ||
84 | */ | ||
85 | static unsigned long long nse_work_required; | ||
86 | |||
87 | /** | ||
88 | * Interval for sending network size estimation flood requests. | ||
89 | */ | ||
90 | static struct GNUNET_TIME_Relative gnunet_nse_interval; | ||
91 | |||
92 | /** | ||
93 | * Interval between proof find runs. | ||
94 | */ | ||
95 | static struct GNUNET_TIME_Relative proof_find_delay; | ||
96 | |||
97 | #if ENABLE_NSE_HISTOGRAM | ||
98 | |||
99 | /** | ||
100 | * Handle to test if testbed logger service is running or not | ||
101 | */ | ||
102 | struct GNUNET_CLIENT_TestHandle *logger_test; | ||
103 | |||
104 | /** | ||
105 | * Handle for writing when we received messages to disk. | ||
106 | */ | ||
107 | static struct GNUNET_TESTBED_LOGGER_Handle *lh; | ||
108 | |||
109 | /** | ||
110 | * Handle for writing message received timestamp information to disk. | ||
111 | */ | ||
112 | static struct GNUNET_BIO_WriteHandle *histogram; | ||
113 | |||
114 | #endif | ||
115 | |||
116 | /** | ||
117 | * Salt for PoW calcualations. | ||
118 | */ | ||
119 | static struct GNUNET_CRYPTO_PowSalt salt = { "gnunet-nse-proof" }; | ||
120 | |||
121 | |||
122 | /** | ||
123 | * Per-peer information. | ||
124 | */ | ||
125 | struct NSEPeerEntry | ||
126 | { | ||
127 | /** | ||
128 | * Core handle for sending messages to this peer. | ||
129 | */ | ||
130 | struct GNUNET_MQ_Handle *mq; | ||
131 | |||
132 | /** | ||
133 | * What is the identity of the peer? | ||
134 | */ | ||
135 | const struct GNUNET_PeerIdentity *id; | ||
136 | |||
137 | /** | ||
138 | * Task scheduled to send message to this peer. | ||
139 | */ | ||
140 | struct GNUNET_SCHEDULER_Task *transmit_task; | ||
141 | |||
142 | /** | ||
143 | * Did we receive or send a message about the previous round | ||
144 | * to this peer yet? #GNUNET_YES if the previous round has | ||
145 | * been taken care of. | ||
146 | */ | ||
147 | int previous_round; | ||
148 | |||
149 | #if ENABLE_NSE_HISTOGRAM | ||
150 | /** | ||
151 | * Amount of messages received from this peer on this round. | ||
152 | */ | ||
153 | unsigned int received_messages; | ||
154 | |||
155 | /** | ||
156 | * Amount of messages transmitted to this peer on this round. | ||
157 | */ | ||
158 | unsigned int transmitted_messages; | ||
159 | |||
160 | /** | ||
161 | * Which size did we tell the peer the network is? | ||
162 | */ | ||
163 | unsigned int last_transmitted_size; | ||
164 | #endif | ||
165 | }; | ||
166 | |||
167 | |||
168 | GNUNET_NETWORK_STRUCT_BEGIN | ||
169 | |||
170 | /** | ||
171 | * Network size estimate reply; sent when "this" | ||
172 | * peer's timer has run out before receiving a | ||
173 | * valid reply from another peer. | ||
174 | */ | ||
175 | struct GNUNET_NSE_FloodMessage | ||
176 | { | ||
177 | /** | ||
178 | * Type: #GNUNET_MESSAGE_TYPE_NSE_P2P_FLOOD | ||
179 | */ | ||
180 | struct GNUNET_MessageHeader header; | ||
181 | |||
182 | /** | ||
183 | * Number of hops this message has taken so far. | ||
184 | */ | ||
185 | uint32_t hop_count GNUNET_PACKED; | ||
186 | |||
187 | /** | ||
188 | * Purpose. | ||
189 | */ | ||
190 | struct GNUNET_CRYPTO_EccSignaturePurpose purpose; | ||
191 | |||
192 | /** | ||
193 | * The current timestamp value (which all | ||
194 | * peers should agree on). | ||
195 | */ | ||
196 | struct GNUNET_TIME_AbsoluteNBO timestamp; | ||
197 | |||
198 | /** | ||
199 | * Number of matching bits between the hash | ||
200 | * of timestamp and the initiator's public | ||
201 | * key. | ||
202 | */ | ||
203 | uint32_t matching_bits GNUNET_PACKED; | ||
204 | |||
205 | /** | ||
206 | * Public key of the originator. | ||
207 | */ | ||
208 | struct GNUNET_PeerIdentity origin; | ||
209 | |||
210 | /** | ||
211 | * Proof of work, causing leading zeros when hashed with pkey. | ||
212 | */ | ||
213 | uint64_t proof_of_work GNUNET_PACKED; | ||
214 | |||
215 | /** | ||
216 | * Signature (over range specified in purpose). | ||
217 | */ | ||
218 | struct GNUNET_CRYPTO_EddsaSignature signature; | ||
219 | }; | ||
220 | GNUNET_NETWORK_STRUCT_END | ||
221 | |||
222 | /** | ||
223 | * Handle to our current configuration. | ||
224 | */ | ||
225 | static const struct GNUNET_CONFIGURATION_Handle *cfg; | ||
226 | |||
227 | /** | ||
228 | * Handle to the statistics service. | ||
229 | */ | ||
230 | static struct GNUNET_STATISTICS_Handle *stats; | ||
231 | |||
232 | /** | ||
233 | * Handle to the core service. | ||
234 | */ | ||
235 | static struct GNUNET_CORE_Handle *core_api; | ||
236 | |||
237 | /** | ||
238 | * Map of all connected peers. | ||
239 | */ | ||
240 | static struct GNUNET_CONTAINER_MultiPeerMap *peers; | ||
241 | |||
242 | /** | ||
243 | * The current network size estimate. Number of bits matching on | ||
244 | * average thus far. | ||
245 | */ | ||
246 | static double current_size_estimate; | ||
247 | |||
248 | /** | ||
249 | * The standard deviation of the last #HISTORY_SIZE network | ||
250 | * size estimates. | ||
251 | */ | ||
252 | static double current_std_dev = NAN; | ||
253 | |||
254 | /** | ||
255 | * Current hop counter estimate (estimate for network diameter). | ||
256 | */ | ||
257 | static uint32_t hop_count_max; | ||
258 | |||
259 | /** | ||
260 | * Message for the next round, if we got any. | ||
261 | */ | ||
262 | static struct GNUNET_NSE_FloodMessage next_message; | ||
263 | |||
264 | /** | ||
265 | * Array of recent size estimate messages. | ||
266 | */ | ||
267 | static struct GNUNET_NSE_FloodMessage size_estimate_messages[HISTORY_SIZE]; | ||
268 | |||
269 | /** | ||
270 | * Index of most recent estimate. | ||
271 | */ | ||
272 | static unsigned int estimate_index; | ||
273 | |||
274 | /** | ||
275 | * Number of valid entries in the history. | ||
276 | */ | ||
277 | static unsigned int estimate_count; | ||
278 | |||
279 | /** | ||
280 | * Task scheduled to update our flood message for the next round. | ||
281 | */ | ||
282 | static struct GNUNET_SCHEDULER_Task *flood_task; | ||
283 | |||
284 | /** | ||
285 | * Task scheduled to compute our proof. | ||
286 | */ | ||
287 | static struct GNUNET_SCHEDULER_Task *proof_task; | ||
288 | |||
289 | /** | ||
290 | * Notification context, simplifies client broadcasts. | ||
291 | */ | ||
292 | static struct GNUNET_NotificationContext *nc; | ||
293 | |||
294 | /** | ||
295 | * The next major time. | ||
296 | */ | ||
297 | static struct GNUNET_TIME_Absolute next_timestamp; | ||
298 | |||
299 | /** | ||
300 | * The current major time. | ||
301 | */ | ||
302 | static struct GNUNET_TIME_Absolute current_timestamp; | ||
303 | |||
304 | /** | ||
305 | * The private key of this peer. | ||
306 | */ | ||
307 | static struct GNUNET_CRYPTO_EddsaPrivateKey *my_private_key; | ||
308 | |||
309 | /** | ||
310 | * The peer identity of this peer. | ||
311 | */ | ||
312 | static struct GNUNET_PeerIdentity my_identity; | ||
313 | |||
314 | /** | ||
315 | * Proof of work for this peer. | ||
316 | */ | ||
317 | static uint64_t my_proof; | ||
318 | |||
319 | |||
320 | /** | ||
321 | * Initialize a message to clients with the current network | ||
322 | * size estimate. | ||
323 | * | ||
324 | * @param em message to fill in | ||
325 | */ | ||
326 | static void | ||
327 | setup_estimate_message (struct GNUNET_NSE_ClientMessage *em) | ||
328 | { | ||
329 | double mean; | ||
330 | double sum; | ||
331 | double std_dev; | ||
332 | double variance; | ||
333 | double val; | ||
334 | double nsize; | ||
335 | |||
336 | #define WEST 1 | ||
337 | /* Weighted incremental algorithm for stddev according to West (1979) */ | ||
338 | #if WEST | ||
339 | double sumweight; | ||
340 | double weight; | ||
341 | double q; | ||
342 | double r; | ||
343 | double temp; | ||
344 | |||
345 | mean = 0.0; | ||
346 | sum = 0.0; | ||
347 | sumweight = 0.0; | ||
348 | variance = 0.0; | ||
349 | for (unsigned int i = 0; i < estimate_count; i++) | ||
350 | { | ||
351 | unsigned int j = (estimate_index - i + HISTORY_SIZE) % HISTORY_SIZE; | ||
352 | |||
353 | val = htonl (size_estimate_messages[j].matching_bits); | ||
354 | weight = estimate_count + 1 - i; | ||
355 | |||
356 | temp = weight + sumweight; | ||
357 | q = val - mean; | ||
358 | r = q * weight / temp; | ||
359 | mean += r; | ||
360 | sum += sumweight * q * r; | ||
361 | sumweight = temp; | ||
362 | } | ||
363 | if (estimate_count > 0) | ||
364 | variance = (sum / sumweight) * estimate_count / (estimate_count - 1.0); | ||
365 | #else | ||
366 | /* trivial version for debugging */ | ||
367 | double vsq; | ||
368 | |||
369 | /* non-weighted trivial version */ | ||
370 | sum = 0.0; | ||
371 | vsq = 0.0; | ||
372 | variance = 0.0; | ||
373 | mean = 0.0; | ||
374 | |||
375 | for (unsigned int i = 0; i < estimate_count; i++) | ||
376 | { | ||
377 | unsigned int j = (estimate_index - i + HISTORY_SIZE) % HISTORY_SIZE; | ||
378 | |||
379 | val = htonl (size_estimate_messages[j].matching_bits); | ||
380 | sum += val; | ||
381 | vsq += val * val; | ||
382 | } | ||
383 | if (0 != estimate_count) | ||
384 | { | ||
385 | mean = sum / estimate_count; | ||
386 | variance = (vsq - mean * sum) | ||
387 | / (estimate_count - 1.0); // terrible for numerical stability... | ||
388 | } | ||
389 | #endif | ||
390 | if (variance >= 0) | ||
391 | std_dev = sqrt (variance); | ||
392 | else | ||
393 | std_dev = variance; /* must be infinity due to estimate_count == 0 */ | ||
394 | current_std_dev = std_dev; | ||
395 | current_size_estimate = mean; | ||
396 | |||
397 | em->header.size = htons (sizeof(struct GNUNET_NSE_ClientMessage)); | ||
398 | em->header.type = htons (GNUNET_MESSAGE_TYPE_NSE_ESTIMATE); | ||
399 | em->reserved = htonl (0); | ||
400 | em->timestamp = GNUNET_TIME_absolute_hton (GNUNET_TIME_absolute_get ()); | ||
401 | { | ||
402 | double se = mean - 0.332747; | ||
403 | unsigned int j = GNUNET_CONTAINER_multipeermap_size (peers); | ||
404 | if (0 == j) | ||
405 | j = 1; /* Avoid log2(0); can only happen if CORE didn't report | ||
406 | connection to self yet */ | ||
407 | nsize = log2 (j); | ||
408 | em->size_estimate = GNUNET_hton_double (GNUNET_MAX (se, nsize)); | ||
409 | em->std_deviation = GNUNET_hton_double (std_dev); | ||
410 | GNUNET_STATISTICS_set (stats, | ||
411 | "# nodes in the network (estimate)", | ||
412 | (uint64_t) pow (2, GNUNET_MAX (se, nsize)), | ||
413 | GNUNET_NO); | ||
414 | } | ||
415 | } | ||
416 | |||
417 | |||
418 | /** | ||
419 | * Handler for START message from client, triggers an | ||
420 | * immediate current network estimate notification. | ||
421 | * Also, we remember the client for updates upon future | ||
422 | * estimate measurements. | ||
423 | * | ||
424 | * @param cls client who sent the message | ||
425 | * @param message the message received | ||
426 | */ | ||
427 | static void | ||
428 | handle_start (void *cls, const struct GNUNET_MessageHeader *message) | ||
429 | { | ||
430 | struct GNUNET_SERVICE_Client *client = cls; | ||
431 | struct GNUNET_MQ_Handle *mq; | ||
432 | struct GNUNET_NSE_ClientMessage em; | ||
433 | struct GNUNET_MQ_Envelope *env; | ||
434 | |||
435 | (void) message; | ||
436 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Received START message from client\n"); | ||
437 | mq = GNUNET_SERVICE_client_get_mq (client); | ||
438 | GNUNET_notification_context_add (nc, mq); | ||
439 | setup_estimate_message (&em); | ||
440 | env = GNUNET_MQ_msg_copy (&em.header); | ||
441 | GNUNET_MQ_send (mq, env); | ||
442 | GNUNET_SERVICE_client_continue (client); | ||
443 | } | ||
444 | |||
445 | |||
446 | /** | ||
447 | * How long should we delay a message to go the given number of | ||
448 | * matching bits? | ||
449 | * | ||
450 | * @param matching_bits number of matching bits to consider | ||
451 | */ | ||
452 | static double | ||
453 | get_matching_bits_delay (uint32_t matching_bits) | ||
454 | { | ||
455 | /* Calculated as: S + f/2 - (f / pi) * (atan(x - p')) */ | ||
456 | // S is next_timestamp (ignored in return value) | ||
457 | // f is frequency (gnunet_nse_interval) | ||
458 | // x is matching_bits | ||
459 | // p' is current_size_estimate | ||
460 | return ((double) gnunet_nse_interval.rel_value_us / (double) 2.0) | ||
461 | - ((gnunet_nse_interval.rel_value_us / M_PI) | ||
462 | * atan (matching_bits - current_size_estimate)); | ||
463 | } | ||
464 | |||
465 | |||
466 | /** | ||
467 | * What delay randomization should we apply for a given number of matching bits? | ||
468 | * | ||
469 | * @param matching_bits number of matching bits | ||
470 | * @return random delay to apply | ||
471 | */ | ||
472 | static struct GNUNET_TIME_Relative | ||
473 | get_delay_randomization (uint32_t matching_bits) | ||
474 | { | ||
475 | #if USE_RANDOM_DELAYS | ||
476 | struct GNUNET_TIME_Relative ret; | ||
477 | uint32_t i; | ||
478 | double d; | ||
479 | |||
480 | d = get_matching_bits_delay (matching_bits); | ||
481 | i = (uint32_t) (d / (double) (hop_count_max + 1)); | ||
482 | ret.rel_value_us = i; | ||
483 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | ||
484 | "Randomizing flood using latencies up to %s\n", | ||
485 | GNUNET_STRINGS_relative_time_to_string (ret, GNUNET_YES)); | ||
486 | ret.rel_value_us = | ||
487 | GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, i + 1); | ||
488 | return ret; | ||
489 | #else | ||
490 | return GNUNET_TIME_UNIT_ZERO; | ||
491 | #endif | ||
492 | } | ||
493 | |||
494 | |||
495 | /** | ||
496 | * Get the number of matching bits that the given timestamp has to the given peer ID. | ||
497 | * | ||
498 | * @param timestamp time to generate key | ||
499 | * @param id peer identity to compare with | ||
500 | * @return number of matching bits | ||
501 | */ | ||
502 | static uint32_t | ||
503 | get_matching_bits (struct GNUNET_TIME_Absolute timestamp, | ||
504 | const struct GNUNET_PeerIdentity *id) | ||
505 | { | ||
506 | struct GNUNET_HashCode timestamp_hash; | ||
507 | struct GNUNET_HashCode pid_hash; | ||
508 | |||
509 | GNUNET_CRYPTO_hash (×tamp.abs_value_us, | ||
510 | sizeof(timestamp.abs_value_us), | ||
511 | ×tamp_hash); | ||
512 | GNUNET_CRYPTO_hash (id, sizeof(struct GNUNET_PeerIdentity), &pid_hash); | ||
513 | return GNUNET_CRYPTO_hash_matching_bits (×tamp_hash, &pid_hash); | ||
514 | } | ||
515 | |||
516 | |||
517 | /** | ||
518 | * Get the transmission delay that should be applied for a | ||
519 | * particular round. | ||
520 | * | ||
521 | * @param round_offset -1 for the previous round (random delay between 0 and 50ms) | ||
522 | * 0 for the current round (based on our proximity to time key) | ||
523 | * @return delay that should be applied | ||
524 | */ | ||
525 | static struct GNUNET_TIME_Relative | ||
526 | get_transmit_delay (int round_offset) | ||
527 | { | ||
528 | struct GNUNET_TIME_Relative ret; | ||
529 | struct GNUNET_TIME_Absolute tgt; | ||
530 | double dist_delay; | ||
531 | uint32_t matching_bits; | ||
532 | |||
533 | switch (round_offset) | ||
534 | { | ||
535 | case -1: | ||
536 | /* previous round is randomized between 0 and 50 ms */ | ||
537 | #if USE_RANDOM_DELAYS | ||
538 | ret.rel_value_us = | ||
539 | GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK, 50); | ||
540 | #else | ||
541 | ret = GNUNET_TIME_UNIT_ZERO; | ||
542 | #endif | ||
543 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | ||
544 | "Transmitting previous round behind schedule in %s\n", | ||
545 | GNUNET_STRINGS_relative_time_to_string (ret, GNUNET_YES)); | ||
546 | return ret; | ||
547 | |||
548 | case 0: | ||
549 | /* current round is based on best-known matching_bits */ | ||
550 | matching_bits = | ||
551 | ntohl (size_estimate_messages[estimate_index].matching_bits); | ||
552 | dist_delay = get_matching_bits_delay (matching_bits); | ||
553 | dist_delay += get_delay_randomization (matching_bits).rel_value_us; | ||
554 | ret.rel_value_us = (uint64_t) dist_delay; | ||
555 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | ||
556 | "For round %s, delay for %u matching bits is %s\n", | ||
557 | GNUNET_STRINGS_absolute_time_to_string (current_timestamp), | ||
558 | (unsigned int) matching_bits, | ||
559 | GNUNET_STRINGS_relative_time_to_string (ret, GNUNET_YES)); | ||
560 | /* now consider round start time and add delay to it */ | ||
561 | tgt = GNUNET_TIME_absolute_add (current_timestamp, ret); | ||
562 | return GNUNET_TIME_absolute_get_remaining (tgt); | ||
563 | } | ||
564 | GNUNET_break (0); | ||
565 | return GNUNET_TIME_UNIT_FOREVER_REL; | ||
566 | } | ||
567 | |||
568 | |||
569 | /** | ||
570 | * Task that triggers a NSE P2P transmission. | ||
571 | * | ||
572 | * @param cls the `struct NSEPeerEntry *` | ||
573 | */ | ||
574 | static void | ||
575 | transmit_task_cb (void *cls) | ||
576 | { | ||
577 | struct NSEPeerEntry *peer_entry = cls; | ||
578 | unsigned int idx; | ||
579 | struct GNUNET_MQ_Envelope *env; | ||
580 | |||
581 | peer_entry->transmit_task = NULL; | ||
582 | idx = estimate_index; | ||
583 | if (GNUNET_NO == peer_entry->previous_round) | ||
584 | { | ||
585 | idx = (idx + HISTORY_SIZE - 1) % HISTORY_SIZE; | ||
586 | peer_entry->previous_round = GNUNET_YES; | ||
587 | peer_entry->transmit_task = | ||
588 | GNUNET_SCHEDULER_add_delayed (get_transmit_delay (0), | ||
589 | &transmit_task_cb, | ||
590 | peer_entry); | ||
591 | } | ||
592 | if ((0 == ntohl (size_estimate_messages[idx].hop_count)) && | ||
593 | (NULL != proof_task)) | ||
594 | { | ||
595 | GNUNET_STATISTICS_update (stats, | ||
596 | "# flood messages not generated (no proof yet)", | ||
597 | 1, | ||
598 | GNUNET_NO); | ||
599 | return; | ||
600 | } | ||
601 | if (0 == ntohs (size_estimate_messages[idx].header.size)) | ||
602 | { | ||
603 | GNUNET_STATISTICS_update (stats, | ||
604 | "# flood messages not generated (lack of history)", | ||
605 | 1, | ||
606 | GNUNET_NO); | ||
607 | return; | ||
608 | } | ||
609 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | ||
610 | "In round %s, sending to `%s' estimate with %u bits\n", | ||
611 | GNUNET_STRINGS_absolute_time_to_string ( | ||
612 | GNUNET_TIME_absolute_ntoh ( | ||
613 | size_estimate_messages[idx].timestamp)), | ||
614 | GNUNET_i2s (peer_entry->id), | ||
615 | (unsigned int) ntohl (size_estimate_messages[idx].matching_bits)); | ||
616 | if (0 == ntohl (size_estimate_messages[idx].hop_count)) | ||
617 | GNUNET_STATISTICS_update (stats, "# flood messages started", 1, GNUNET_NO); | ||
618 | GNUNET_STATISTICS_update (stats, | ||
619 | "# flood messages transmitted", | ||
620 | 1, | ||
621 | GNUNET_NO); | ||
622 | #if ENABLE_NSE_HISTOGRAM | ||
623 | peer_entry->transmitted_messages++; | ||
624 | peer_entry->last_transmitted_size = | ||
625 | ntohl (size_estimate_messages[idx].matching_bits); | ||
626 | #endif | ||
627 | env = GNUNET_MQ_msg_copy (&size_estimate_messages[idx].header); | ||
628 | GNUNET_MQ_send (peer_entry->mq, env); | ||
629 | } | ||
630 | |||
631 | |||
632 | /** | ||
633 | * We've sent on our flood message or one that we received which was | ||
634 | * validated and closer than ours. Update the global list of recent | ||
635 | * messages and the average. Also re-broadcast the message to any | ||
636 | * clients. | ||
637 | */ | ||
638 | static void | ||
639 | update_network_size_estimate () | ||
640 | { | ||
641 | struct GNUNET_NSE_ClientMessage em; | ||
642 | |||
643 | setup_estimate_message (&em); | ||
644 | GNUNET_notification_context_broadcast (nc, &em.header, GNUNET_YES); | ||
645 | } | ||
646 | |||
647 | |||
648 | /** | ||
649 | * Setup a flood message in our history array at the given | ||
650 | * slot offset for the given timestamp. | ||
651 | * | ||
652 | * @param slot index to use | ||
653 | * @param ts timestamp to use | ||
654 | */ | ||
655 | static void | ||
656 | setup_flood_message (unsigned int slot, struct GNUNET_TIME_Absolute ts) | ||
657 | { | ||
658 | struct GNUNET_NSE_FloodMessage *fm; | ||
659 | uint32_t matching_bits; | ||
660 | |||
661 | matching_bits = get_matching_bits (ts, &my_identity); | ||
662 | fm = &size_estimate_messages[slot]; | ||
663 | fm->header.size = htons (sizeof(struct GNUNET_NSE_FloodMessage)); | ||
664 | fm->header.type = htons (GNUNET_MESSAGE_TYPE_NSE_P2P_FLOOD); | ||
665 | fm->hop_count = htonl (0); | ||
666 | fm->purpose.purpose = htonl (GNUNET_SIGNATURE_PURPOSE_NSE_SEND); | ||
667 | fm->purpose.size = | ||
668 | htonl (sizeof(struct GNUNET_NSE_FloodMessage) | ||
669 | - sizeof(struct GNUNET_MessageHeader) - sizeof(uint32_t) | ||
670 | - sizeof(struct GNUNET_CRYPTO_EddsaSignature)); | ||
671 | fm->matching_bits = htonl (matching_bits); | ||
672 | fm->timestamp = GNUNET_TIME_absolute_hton (ts); | ||
673 | fm->origin = my_identity; | ||
674 | fm->proof_of_work = my_proof; | ||
675 | if (nse_work_required > 0) | ||
676 | GNUNET_assert (GNUNET_OK == | ||
677 | GNUNET_CRYPTO_eddsa_sign_ (my_private_key, | ||
678 | &fm->purpose, | ||
679 | &fm->signature)); | ||
680 | else | ||
681 | memset (&fm->signature, 0, sizeof(fm->signature)); | ||
682 | } | ||
683 | |||
684 | |||
685 | /** | ||
686 | * Schedule transmission for the given peer for the current round based | ||
687 | * on what we know about the desired delay. | ||
688 | * | ||
689 | * @param cls unused | ||
690 | * @param key hash of peer identity | ||
691 | * @param value the `struct NSEPeerEntry` | ||
692 | * @return #GNUNET_OK (continue to iterate) | ||
693 | */ | ||
694 | static int | ||
695 | schedule_current_round (void *cls, | ||
696 | const struct GNUNET_PeerIdentity *key, | ||
697 | void *value) | ||
698 | { | ||
699 | struct NSEPeerEntry *peer_entry = value; | ||
700 | struct GNUNET_TIME_Relative delay; | ||
701 | |||
702 | (void) cls; | ||
703 | (void) key; | ||
704 | if (NULL != peer_entry->transmit_task) | ||
705 | { | ||
706 | GNUNET_SCHEDULER_cancel (peer_entry->transmit_task); | ||
707 | peer_entry->previous_round = GNUNET_NO; | ||
708 | } | ||
709 | #if ENABLE_NSE_HISTOGRAM | ||
710 | if (peer_entry->received_messages > 1) | ||
711 | GNUNET_STATISTICS_update (stats, | ||
712 | "# extra messages", | ||
713 | peer_entry->received_messages - 1, | ||
714 | GNUNET_NO); | ||
715 | peer_entry->transmitted_messages = 0; | ||
716 | peer_entry->last_transmitted_size = 0; | ||
717 | peer_entry->received_messages = 0; | ||
718 | #endif | ||
719 | delay = | ||
720 | get_transmit_delay ((GNUNET_NO == peer_entry->previous_round) ? -1 : 0); | ||
721 | peer_entry->transmit_task = | ||
722 | GNUNET_SCHEDULER_add_delayed (delay, &transmit_task_cb, peer_entry); | ||
723 | return GNUNET_OK; | ||
724 | } | ||
725 | |||
726 | |||
727 | /** | ||
728 | * Update our flood message to be sent (and our timestamps). | ||
729 | * | ||
730 | * @param cls unused | ||
731 | */ | ||
732 | static void | ||
733 | update_flood_message (void *cls) | ||
734 | { | ||
735 | struct GNUNET_TIME_Relative offset; | ||
736 | |||
737 | (void) cls; | ||
738 | flood_task = NULL; | ||
739 | offset = GNUNET_TIME_absolute_get_remaining (next_timestamp); | ||
740 | if (0 != offset.rel_value_us) | ||
741 | { | ||
742 | /* somehow run early, delay more */ | ||
743 | flood_task = | ||
744 | GNUNET_SCHEDULER_add_delayed (offset, &update_flood_message, NULL); | ||
745 | return; | ||
746 | } | ||
747 | estimate_index = (estimate_index + 1) % HISTORY_SIZE; | ||
748 | if (estimate_count < HISTORY_SIZE) | ||
749 | estimate_count++; | ||
750 | current_timestamp = next_timestamp; | ||
751 | next_timestamp = | ||
752 | GNUNET_TIME_absolute_add (current_timestamp, gnunet_nse_interval); | ||
753 | if ((current_timestamp.abs_value_us == | ||
754 | GNUNET_TIME_absolute_ntoh (next_message.timestamp).abs_value_us) && | ||
755 | (get_matching_bits (current_timestamp, &my_identity) < | ||
756 | ntohl (next_message.matching_bits))) | ||
757 | { | ||
758 | /* we received a message for this round way early, use it! */ | ||
759 | size_estimate_messages[estimate_index] = next_message; | ||
760 | size_estimate_messages[estimate_index].hop_count = | ||
761 | htonl (1 + ntohl (next_message.hop_count)); | ||
762 | } | ||
763 | else | ||
764 | setup_flood_message (estimate_index, current_timestamp); | ||
765 | next_message.matching_bits = htonl (0); /* reset for 'next' round */ | ||
766 | hop_count_max = 0; | ||
767 | for (unsigned int i = 0; i < HISTORY_SIZE; i++) | ||
768 | hop_count_max = | ||
769 | GNUNET_MAX (ntohl (size_estimate_messages[i].hop_count), hop_count_max); | ||
770 | GNUNET_CONTAINER_multipeermap_iterate (peers, &schedule_current_round, NULL); | ||
771 | flood_task = | ||
772 | GNUNET_SCHEDULER_add_at (next_timestamp, &update_flood_message, NULL); | ||
773 | } | ||
774 | |||
775 | |||
776 | /** | ||
777 | * Count the leading zeroes in hash. | ||
778 | * | ||
779 | * @param hash to count leading zeros in | ||
780 | * @return the number of leading zero bits. | ||
781 | */ | ||
782 | static unsigned int | ||
783 | count_leading_zeroes (const struct GNUNET_HashCode *hash) | ||
784 | { | ||
785 | unsigned int hash_count; | ||
786 | |||
787 | hash_count = 0; | ||
788 | while (0 == GNUNET_CRYPTO_hash_get_bit_ltr (hash, hash_count)) | ||
789 | hash_count++; | ||
790 | return hash_count; | ||
791 | } | ||
792 | |||
793 | |||
794 | /** | ||
795 | * Check whether the given public key and integer are a valid proof of | ||
796 | * work. | ||
797 | * | ||
798 | * @param pkey the public key | ||
799 | * @param val the integer | ||
800 | * @return #GNUNET_YES if valid, #GNUNET_NO if not | ||
801 | */ | ||
802 | static int | ||
803 | check_proof_of_work (const struct GNUNET_CRYPTO_EddsaPublicKey *pkey, | ||
804 | uint64_t val) | ||
805 | { | ||
806 | char buf[sizeof(struct GNUNET_CRYPTO_EddsaPublicKey) | ||
807 | + sizeof(val)] GNUNET_ALIGN; | ||
808 | struct GNUNET_HashCode result; | ||
809 | |||
810 | GNUNET_memcpy (buf, &val, sizeof(val)); | ||
811 | GNUNET_memcpy (&buf[sizeof(val)], | ||
812 | pkey, | ||
813 | sizeof(struct GNUNET_CRYPTO_EddsaPublicKey)); | ||
814 | GNUNET_CRYPTO_pow_hash (&salt, | ||
815 | buf, | ||
816 | sizeof(buf), | ||
817 | &result); | ||
818 | return (count_leading_zeroes (&result) >= nse_work_required) ? GNUNET_YES | ||
819 | : GNUNET_NO; | ||
820 | } | ||
821 | |||
822 | |||
823 | /** | ||
824 | * Write our current proof to disk. | ||
825 | */ | ||
826 | static void | ||
827 | write_proof (void) | ||
828 | { | ||
829 | char *proof; | ||
830 | |||
831 | if (GNUNET_OK != | ||
832 | GNUNET_CONFIGURATION_get_value_filename (cfg, | ||
833 | "NSE", | ||
834 | "PROOFFILE", | ||
835 | &proof)) | ||
836 | return; | ||
837 | (void) GNUNET_DISK_directory_remove (proof); | ||
838 | if (GNUNET_OK != | ||
839 | GNUNET_DISK_fn_write (proof, | ||
840 | &my_proof, | ||
841 | sizeof(my_proof), | ||
842 | GNUNET_DISK_PERM_USER_READ | ||
843 | | GNUNET_DISK_PERM_USER_WRITE)) | ||
844 | GNUNET_log_strerror_file (GNUNET_ERROR_TYPE_WARNING, | ||
845 | "write", | ||
846 | proof); | ||
847 | GNUNET_free (proof); | ||
848 | } | ||
849 | |||
850 | |||
851 | /** | ||
852 | * Find our proof of work. | ||
853 | * | ||
854 | * @param cls closure (unused) | ||
855 | */ | ||
856 | static void | ||
857 | find_proof (void *cls) | ||
858 | { | ||
859 | #define ROUND_SIZE 10 | ||
860 | uint64_t counter; | ||
861 | char buf[sizeof(struct GNUNET_CRYPTO_EddsaPublicKey) | ||
862 | + sizeof(uint64_t)] GNUNET_ALIGN; | ||
863 | struct GNUNET_HashCode result; | ||
864 | unsigned int i; | ||
865 | |||
866 | (void) cls; | ||
867 | proof_task = NULL; | ||
868 | GNUNET_memcpy (&buf[sizeof(uint64_t)], | ||
869 | &my_identity, | ||
870 | sizeof(struct GNUNET_PeerIdentity)); | ||
871 | i = 0; | ||
872 | counter = my_proof; | ||
873 | while ((counter != UINT64_MAX) && (i < ROUND_SIZE)) | ||
874 | { | ||
875 | GNUNET_memcpy (buf, &counter, sizeof(uint64_t)); | ||
876 | GNUNET_CRYPTO_pow_hash (&salt, | ||
877 | buf, | ||
878 | sizeof(buf), | ||
879 | &result); | ||
880 | if (nse_work_required <= count_leading_zeroes (&result)) | ||
881 | { | ||
882 | my_proof = counter; | ||
883 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | ||
884 | "Proof of work found: %llu!\n", | ||
885 | (unsigned long long) GNUNET_ntohll (counter)); | ||
886 | write_proof (); | ||
887 | setup_flood_message (estimate_index, current_timestamp); | ||
888 | return; | ||
889 | } | ||
890 | counter++; | ||
891 | i++; | ||
892 | } | ||
893 | if (my_proof / (100 * ROUND_SIZE) < counter / (100 * ROUND_SIZE)) | ||
894 | { | ||
895 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | ||
896 | "Testing proofs currently at %llu\n", | ||
897 | (unsigned long long) counter); | ||
898 | /* remember progress every 100 rounds */ | ||
899 | my_proof = counter; | ||
900 | write_proof (); | ||
901 | } | ||
902 | else | ||
903 | { | ||
904 | my_proof = counter; | ||
905 | } | ||
906 | proof_task = | ||
907 | GNUNET_SCHEDULER_add_delayed_with_priority (proof_find_delay, | ||
908 | GNUNET_SCHEDULER_PRIORITY_IDLE, | ||
909 | &find_proof, | ||
910 | NULL); | ||
911 | } | ||
912 | |||
913 | |||
914 | /** | ||
915 | * An incoming flood message has been received which claims | ||
916 | * to have more bits matching than any we know in this time | ||
917 | * period. Verify the signature and/or proof of work. | ||
918 | * | ||
919 | * @param incoming_flood the message to verify | ||
920 | * @return #GNUNET_YES if the message is verified | ||
921 | * #GNUNET_NO if the key/signature don't verify | ||
922 | */ | ||
923 | static int | ||
924 | verify_message_crypto (const struct GNUNET_NSE_FloodMessage *incoming_flood) | ||
925 | { | ||
926 | if (GNUNET_YES != check_proof_of_work (&incoming_flood->origin.public_key, | ||
927 | incoming_flood->proof_of_work)) | ||
928 | { | ||
929 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | ||
930 | "Proof of work invalid: %llu!\n", | ||
931 | (unsigned long long) GNUNET_ntohll ( | ||
932 | incoming_flood->proof_of_work)); | ||
933 | GNUNET_break_op (0); | ||
934 | return GNUNET_NO; | ||
935 | } | ||
936 | if ((nse_work_required > 0) && | ||
937 | (GNUNET_OK != | ||
938 | GNUNET_CRYPTO_eddsa_verify_ (GNUNET_SIGNATURE_PURPOSE_NSE_SEND, | ||
939 | &incoming_flood->purpose, | ||
940 | &incoming_flood->signature, | ||
941 | &incoming_flood->origin.public_key))) | ||
942 | { | ||
943 | GNUNET_break_op (0); | ||
944 | return GNUNET_NO; | ||
945 | } | ||
946 | return GNUNET_YES; | ||
947 | } | ||
948 | |||
949 | |||
950 | /** | ||
951 | * Update transmissions for the given peer for the current round based | ||
952 | * on updated proximity information. | ||
953 | * | ||
954 | * @param cls peer entry to exclude from updates | ||
955 | * @param key hash of peer identity | ||
956 | * @param value the `struct NSEPeerEntry *` of a peer to transmit to | ||
957 | * @return #GNUNET_OK (continue to iterate) | ||
958 | */ | ||
959 | static int | ||
960 | update_flood_times (void *cls, | ||
961 | const struct GNUNET_PeerIdentity *key, | ||
962 | void *value) | ||
963 | { | ||
964 | struct NSEPeerEntry *exclude = cls; | ||
965 | struct NSEPeerEntry *peer_entry = value; | ||
966 | struct GNUNET_TIME_Relative delay; | ||
967 | |||
968 | (void) key; | ||
969 | if (peer_entry == exclude) | ||
970 | return GNUNET_OK; /* trigger of the update */ | ||
971 | if (GNUNET_NO == peer_entry->previous_round) | ||
972 | { | ||
973 | /* still stuck in previous round, no point to update, check that | ||
974 | * we are active here though... */ | ||
975 | if (NULL == peer_entry->transmit_task) | ||
976 | { | ||
977 | GNUNET_break (0); | ||
978 | } | ||
979 | return GNUNET_OK; | ||
980 | } | ||
981 | if (NULL != peer_entry->transmit_task) | ||
982 | { | ||
983 | GNUNET_SCHEDULER_cancel (peer_entry->transmit_task); | ||
984 | peer_entry->transmit_task = NULL; | ||
985 | } | ||
986 | delay = get_transmit_delay (0); | ||
987 | peer_entry->transmit_task = | ||
988 | GNUNET_SCHEDULER_add_delayed (delay, &transmit_task_cb, peer_entry); | ||
989 | return GNUNET_OK; | ||
990 | } | ||
991 | |||
992 | |||
993 | /** | ||
994 | * Core handler for size estimate flooding messages. | ||
995 | * | ||
996 | * @param cls peer this message is from | ||
997 | * @param incoming_flood received message | ||
998 | */ | ||
999 | static void | ||
1000 | handle_p2p_estimate (void *cls, | ||
1001 | const struct GNUNET_NSE_FloodMessage *incoming_flood) | ||
1002 | { | ||
1003 | struct NSEPeerEntry *peer_entry = cls; | ||
1004 | struct GNUNET_TIME_Absolute ts; | ||
1005 | uint32_t matching_bits; | ||
1006 | unsigned int idx; | ||
1007 | |||
1008 | #if ENABLE_NSE_HISTOGRAM | ||
1009 | { | ||
1010 | uint64_t t; | ||
1011 | |||
1012 | t = GNUNET_TIME_absolute_get ().abs_value_us; | ||
1013 | if (NULL != lh) | ||
1014 | GNUNET_TESTBED_LOGGER_write (lh, &t, sizeof(uint64_t)); | ||
1015 | if (NULL != histogram) | ||
1016 | GNUNET_BIO_write_int64 (histogram, "histogram-time", t); | ||
1017 | } | ||
1018 | #endif | ||
1019 | GNUNET_STATISTICS_update (stats, "# flood messages received", 1, GNUNET_NO); | ||
1020 | matching_bits = ntohl (incoming_flood->matching_bits); | ||
1021 | #if DEBUG_NSE | ||
1022 | { | ||
1023 | char origin[5]; | ||
1024 | char pred[5]; | ||
1025 | struct GNUNET_PeerIdentity os; | ||
1026 | |||
1027 | GNUNET_snprintf (origin, | ||
1028 | sizeof(origin), | ||
1029 | "%s", | ||
1030 | GNUNET_i2s (&incoming_flood->origin)); | ||
1031 | GNUNET_snprintf (pred, sizeof(pred), "%s", GNUNET_i2s (peer_entry->id)); | ||
1032 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | ||
1033 | "Flood at %s from `%s' via `%s' at `%s' with bits %u\n", | ||
1034 | GNUNET_STRINGS_absolute_time_to_string ( | ||
1035 | GNUNET_TIME_absolute_ntoh (incoming_flood->timestamp)), | ||
1036 | origin, | ||
1037 | pred, | ||
1038 | GNUNET_i2s (&my_identity), | ||
1039 | (unsigned int) matching_bits); | ||
1040 | } | ||
1041 | #endif | ||
1042 | |||
1043 | #if ENABLE_NSE_HISTOGRAM | ||
1044 | peer_entry->received_messages++; | ||
1045 | if ((peer_entry->transmitted_messages > 0) && | ||
1046 | (peer_entry->last_transmitted_size >= matching_bits) ) | ||
1047 | GNUNET_STATISTICS_update (stats, "# cross messages", 1, GNUNET_NO); | ||
1048 | #endif | ||
1049 | |||
1050 | ts = GNUNET_TIME_absolute_ntoh (incoming_flood->timestamp); | ||
1051 | if (ts.abs_value_us == current_timestamp.abs_value_us) | ||
1052 | idx = estimate_index; | ||
1053 | else if (ts.abs_value_us == | ||
1054 | current_timestamp.abs_value_us - gnunet_nse_interval.rel_value_us) | ||
1055 | idx = (estimate_index + HISTORY_SIZE - 1) % HISTORY_SIZE; | ||
1056 | else if (ts.abs_value_us == next_timestamp.abs_value_us) | ||
1057 | { | ||
1058 | if (matching_bits <= ntohl (next_message.matching_bits)) | ||
1059 | return; /* ignore, simply too early/late */ | ||
1060 | if (GNUNET_YES != verify_message_crypto (incoming_flood)) | ||
1061 | { | ||
1062 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, | ||
1063 | "Peer %s is likely ill-configured!\n", | ||
1064 | GNUNET_i2s (peer_entry->id)); | ||
1065 | GNUNET_break_op (0); | ||
1066 | return; | ||
1067 | } | ||
1068 | next_message = *incoming_flood; | ||
1069 | return; | ||
1070 | } | ||
1071 | else | ||
1072 | { | ||
1073 | GNUNET_STATISTICS_update (stats, | ||
1074 | "# flood messages discarded (clock skew too large)", | ||
1075 | 1, | ||
1076 | GNUNET_NO); | ||
1077 | return; | ||
1078 | } | ||
1079 | if (0 == (GNUNET_memcmp (peer_entry->id, &my_identity))) | ||
1080 | { | ||
1081 | /* send to self, update our own estimate IF this also comes from us! */ | ||
1082 | if (0 == GNUNET_memcmp (&incoming_flood->origin, &my_identity)) | ||
1083 | update_network_size_estimate (); | ||
1084 | return; | ||
1085 | } | ||
1086 | if (matching_bits == ntohl (size_estimate_messages[idx].matching_bits)) | ||
1087 | { | ||
1088 | /* Cancel transmission in the other direction, as this peer clearly has | ||
1089 | up-to-date information already. Even if we didn't talk to this peer in | ||
1090 | the previous round, we should no longer send it stale information as it | ||
1091 | told us about the current round! */ | ||
1092 | peer_entry->previous_round = GNUNET_YES; | ||
1093 | if (idx != estimate_index) | ||
1094 | { | ||
1095 | /* do not transmit information for the previous round to this peer | ||
1096 | anymore (but allow current round) */ | ||
1097 | return; | ||
1098 | } | ||
1099 | /* got up-to-date information for current round, cancel transmission to | ||
1100 | * this peer altogether */ | ||
1101 | if (NULL != peer_entry->transmit_task) | ||
1102 | { | ||
1103 | GNUNET_SCHEDULER_cancel (peer_entry->transmit_task); | ||
1104 | peer_entry->transmit_task = NULL; | ||
1105 | } | ||
1106 | return; | ||
1107 | } | ||
1108 | if (matching_bits < ntohl (size_estimate_messages[idx].matching_bits)) | ||
1109 | { | ||
1110 | if ((idx < estimate_index) && (peer_entry->previous_round == GNUNET_YES)) | ||
1111 | { | ||
1112 | peer_entry->previous_round = GNUNET_NO; | ||
1113 | } | ||
1114 | /* push back our result now, that peer is spreading bad information... */ | ||
1115 | if (NULL != peer_entry->transmit_task) | ||
1116 | GNUNET_SCHEDULER_cancel (peer_entry->transmit_task); | ||
1117 | peer_entry->transmit_task = | ||
1118 | GNUNET_SCHEDULER_add_now (&transmit_task_cb, peer_entry); | ||
1119 | /* Not closer than our most recent message, no need to do work here */ | ||
1120 | GNUNET_STATISTICS_update (stats, | ||
1121 | "# flood messages ignored (had closer already)", | ||
1122 | 1, | ||
1123 | GNUNET_NO); | ||
1124 | return; | ||
1125 | } | ||
1126 | if (GNUNET_YES != verify_message_crypto (incoming_flood)) | ||
1127 | { | ||
1128 | GNUNET_break_op (0); | ||
1129 | return; | ||
1130 | } | ||
1131 | GNUNET_assert (matching_bits > | ||
1132 | ntohl (size_estimate_messages[idx].matching_bits)); | ||
1133 | /* Cancel transmission in the other direction, as this peer clearly has | ||
1134 | * up-to-date information already. | ||
1135 | */ | ||
1136 | peer_entry->previous_round = GNUNET_YES; | ||
1137 | if (idx == estimate_index) | ||
1138 | { | ||
1139 | /* cancel any activity for current round */ | ||
1140 | if (NULL != peer_entry->transmit_task) | ||
1141 | { | ||
1142 | GNUNET_SCHEDULER_cancel (peer_entry->transmit_task); | ||
1143 | peer_entry->transmit_task = NULL; | ||
1144 | } | ||
1145 | } | ||
1146 | size_estimate_messages[idx] = *incoming_flood; | ||
1147 | size_estimate_messages[idx].hop_count = | ||
1148 | htonl (ntohl (incoming_flood->hop_count) + 1); | ||
1149 | hop_count_max = | ||
1150 | GNUNET_MAX (ntohl (incoming_flood->hop_count) + 1, hop_count_max); | ||
1151 | GNUNET_STATISTICS_set (stats, | ||
1152 | "# estimated network diameter", | ||
1153 | hop_count_max, | ||
1154 | GNUNET_NO); | ||
1155 | |||
1156 | /* have a new, better size estimate, inform clients */ | ||
1157 | update_network_size_estimate (); | ||
1158 | |||
1159 | /* flood to rest */ | ||
1160 | GNUNET_CONTAINER_multipeermap_iterate (peers, | ||
1161 | &update_flood_times, | ||
1162 | peer_entry); | ||
1163 | } | ||
1164 | |||
1165 | |||
1166 | /** | ||
1167 | * Method called whenever a peer connects. Sets up the PeerEntry and | ||
1168 | * schedules the initial size info transmission to this peer. | ||
1169 | * | ||
1170 | * @param cls closure | ||
1171 | * @param peer peer identity this notification is about | ||
1172 | */ | ||
1173 | static void * | ||
1174 | handle_core_connect (void *cls, | ||
1175 | const struct GNUNET_PeerIdentity *peer, | ||
1176 | struct GNUNET_MQ_Handle *mq) | ||
1177 | { | ||
1178 | struct NSEPeerEntry *peer_entry; | ||
1179 | |||
1180 | (void) cls; | ||
1181 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | ||
1182 | "Peer `%s' connected to us\n", | ||
1183 | GNUNET_i2s (peer)); | ||
1184 | /* set our default transmission options */ | ||
1185 | GNUNET_MQ_set_options (mq, NSE_PRIORITY); | ||
1186 | /* create our peer entry for this peer */ | ||
1187 | peer_entry = GNUNET_new (struct NSEPeerEntry); | ||
1188 | peer_entry->id = peer; | ||
1189 | peer_entry->mq = mq; | ||
1190 | GNUNET_assert (GNUNET_OK == | ||
1191 | GNUNET_CONTAINER_multipeermap_put ( | ||
1192 | peers, | ||
1193 | peer_entry->id, | ||
1194 | peer_entry, | ||
1195 | GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)); | ||
1196 | peer_entry->transmit_task = | ||
1197 | GNUNET_SCHEDULER_add_delayed (get_transmit_delay (-1), | ||
1198 | &transmit_task_cb, | ||
1199 | peer_entry); | ||
1200 | GNUNET_STATISTICS_update (stats, "# peers connected", 1, GNUNET_NO); | ||
1201 | return peer_entry; | ||
1202 | } | ||
1203 | |||
1204 | |||
1205 | /** | ||
1206 | * Method called whenever a peer disconnects. Deletes the PeerEntry and cancels | ||
1207 | * any pending transmission requests to that peer. | ||
1208 | * | ||
1209 | * @param cls closure | ||
1210 | * @param peer peer identity this notification is about | ||
1211 | * @parma internal_cls the `struct NSEPeerEntry` for the @a peer | ||
1212 | */ | ||
1213 | static void | ||
1214 | handle_core_disconnect (void *cls, | ||
1215 | const struct GNUNET_PeerIdentity *peer, | ||
1216 | void *internal_cls) | ||
1217 | { | ||
1218 | struct NSEPeerEntry *pos = internal_cls; | ||
1219 | |||
1220 | (void) cls; | ||
1221 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | ||
1222 | "Peer `%s' disconnected from us\n", | ||
1223 | GNUNET_i2s (peer)); | ||
1224 | GNUNET_assert (GNUNET_YES == | ||
1225 | GNUNET_CONTAINER_multipeermap_remove (peers, peer, pos)); | ||
1226 | if (NULL != pos->transmit_task) | ||
1227 | { | ||
1228 | GNUNET_SCHEDULER_cancel (pos->transmit_task); | ||
1229 | pos->transmit_task = NULL; | ||
1230 | } | ||
1231 | GNUNET_free (pos); | ||
1232 | GNUNET_STATISTICS_update (stats, "# peers connected", -1, GNUNET_NO); | ||
1233 | } | ||
1234 | |||
1235 | |||
1236 | #if ENABLE_NSE_HISTOGRAM | ||
1237 | /** | ||
1238 | * Functions of this type are called to notify a successful transmission of the | ||
1239 | * message to the logger service | ||
1240 | * | ||
1241 | * @param cls NULL | ||
1242 | * @param size the amount of data sent (ignored) | ||
1243 | */ | ||
1244 | static void | ||
1245 | flush_comp_cb (void *cls, size_t size) | ||
1246 | { | ||
1247 | (void) cls; | ||
1248 | (void) size; | ||
1249 | GNUNET_TESTBED_LOGGER_disconnect (lh); | ||
1250 | lh = NULL; | ||
1251 | } | ||
1252 | |||
1253 | |||
1254 | #endif | ||
1255 | |||
1256 | |||
1257 | /** | ||
1258 | * Task run during shutdown. | ||
1259 | * | ||
1260 | * @param cls unused | ||
1261 | */ | ||
1262 | static void | ||
1263 | shutdown_task (void *cls) | ||
1264 | { | ||
1265 | (void) cls; | ||
1266 | if (NULL != flood_task) | ||
1267 | { | ||
1268 | GNUNET_SCHEDULER_cancel (flood_task); | ||
1269 | flood_task = NULL; | ||
1270 | } | ||
1271 | if (NULL != proof_task) | ||
1272 | { | ||
1273 | GNUNET_SCHEDULER_cancel (proof_task); | ||
1274 | proof_task = NULL; | ||
1275 | write_proof (); /* remember progress */ | ||
1276 | } | ||
1277 | if (NULL != nc) | ||
1278 | { | ||
1279 | GNUNET_notification_context_destroy (nc); | ||
1280 | nc = NULL; | ||
1281 | } | ||
1282 | if (NULL != core_api) | ||
1283 | { | ||
1284 | GNUNET_CORE_disconnect (core_api); | ||
1285 | core_api = NULL; | ||
1286 | } | ||
1287 | if (NULL != stats) | ||
1288 | { | ||
1289 | GNUNET_STATISTICS_destroy (stats, GNUNET_NO); | ||
1290 | stats = NULL; | ||
1291 | } | ||
1292 | if (NULL != peers) | ||
1293 | { | ||
1294 | GNUNET_CONTAINER_multipeermap_destroy (peers); | ||
1295 | peers = NULL; | ||
1296 | } | ||
1297 | if (NULL != my_private_key) | ||
1298 | { | ||
1299 | GNUNET_free (my_private_key); | ||
1300 | my_private_key = NULL; | ||
1301 | } | ||
1302 | #if ENABLE_NSE_HISTOGRAM | ||
1303 | if (NULL != logger_test) | ||
1304 | { | ||
1305 | GNUNET_CLIENT_service_test_cancel (logger_test); | ||
1306 | logger_test = NULL; | ||
1307 | } | ||
1308 | if (NULL != lh) | ||
1309 | { | ||
1310 | GNUNET_TESTBED_LOGGER_flush (lh, &flush_comp_cb, NULL); | ||
1311 | } | ||
1312 | if (NULL != histogram) | ||
1313 | { | ||
1314 | GNUNET_BIO_write_close (histogram, NULL); | ||
1315 | histogram = NULL; | ||
1316 | } | ||
1317 | #endif | ||
1318 | } | ||
1319 | |||
1320 | |||
1321 | /** | ||
1322 | * Called on core init/fail. | ||
1323 | * | ||
1324 | * @param cls service closure | ||
1325 | * @param identity the public identity of this peer | ||
1326 | */ | ||
1327 | static void | ||
1328 | core_init (void *cls, const struct GNUNET_PeerIdentity *identity) | ||
1329 | { | ||
1330 | struct GNUNET_TIME_Absolute now; | ||
1331 | struct GNUNET_TIME_Absolute prev_time; | ||
1332 | |||
1333 | (void) cls; | ||
1334 | if (NULL == identity) | ||
1335 | { | ||
1336 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Connection to core FAILED!\n"); | ||
1337 | GNUNET_SCHEDULER_shutdown (); | ||
1338 | return; | ||
1339 | } | ||
1340 | GNUNET_assert (0 == GNUNET_memcmp (&my_identity, identity)); | ||
1341 | now = GNUNET_TIME_absolute_get (); | ||
1342 | current_timestamp.abs_value_us = | ||
1343 | (now.abs_value_us / gnunet_nse_interval.rel_value_us) | ||
1344 | * gnunet_nse_interval.rel_value_us; | ||
1345 | next_timestamp = | ||
1346 | GNUNET_TIME_absolute_add (current_timestamp, gnunet_nse_interval); | ||
1347 | estimate_index = HISTORY_SIZE - 1; | ||
1348 | estimate_count = 0; | ||
1349 | if (GNUNET_YES == check_proof_of_work (&my_identity.public_key, my_proof)) | ||
1350 | { | ||
1351 | int idx = (estimate_index + HISTORY_SIZE - 1) % HISTORY_SIZE; | ||
1352 | prev_time.abs_value_us = | ||
1353 | current_timestamp.abs_value_us - gnunet_nse_interval.rel_value_us; | ||
1354 | setup_flood_message (idx, prev_time); | ||
1355 | setup_flood_message (estimate_index, current_timestamp); | ||
1356 | estimate_count++; | ||
1357 | } | ||
1358 | flood_task = | ||
1359 | GNUNET_SCHEDULER_add_at (next_timestamp, &update_flood_message, NULL); | ||
1360 | } | ||
1361 | |||
1362 | |||
1363 | #if ENABLE_NSE_HISTOGRAM | ||
1364 | /** | ||
1365 | * Function called with the status of the testbed logger service | ||
1366 | * | ||
1367 | * @param cls NULL | ||
1368 | * @param status #GNUNET_YES if the service is running, | ||
1369 | * #GNUNET_NO if the service is not running | ||
1370 | * #GNUNET_SYSERR if the configuration is invalid | ||
1371 | */ | ||
1372 | static void | ||
1373 | status_cb (void *cls, int status) | ||
1374 | { | ||
1375 | (void) cls; | ||
1376 | logger_test = NULL; | ||
1377 | if (GNUNET_YES != status) | ||
1378 | { | ||
1379 | GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "Testbed logger not running\n"); | ||
1380 | return; | ||
1381 | } | ||
1382 | if (NULL == (lh = GNUNET_TESTBED_LOGGER_connect (cfg))) | ||
1383 | { | ||
1384 | GNUNET_log (GNUNET_ERROR_TYPE_WARNING, | ||
1385 | "Cannot connect to the testbed logger. Exiting.\n"); | ||
1386 | GNUNET_SCHEDULER_shutdown (); | ||
1387 | } | ||
1388 | } | ||
1389 | |||
1390 | |||
1391 | #endif | ||
1392 | |||
1393 | |||
1394 | /** | ||
1395 | * Handle network size estimate clients. | ||
1396 | * | ||
1397 | * @param cls closure | ||
1398 | * @param c configuration to use | ||
1399 | * @param service the initialized service | ||
1400 | */ | ||
1401 | static void | ||
1402 | run (void *cls, | ||
1403 | const struct GNUNET_CONFIGURATION_Handle *c, | ||
1404 | struct GNUNET_SERVICE_Handle *service) | ||
1405 | { | ||
1406 | struct GNUNET_MQ_MessageHandler core_handlers[] = | ||
1407 | { GNUNET_MQ_hd_fixed_size (p2p_estimate, | ||
1408 | GNUNET_MESSAGE_TYPE_NSE_P2P_FLOOD, | ||
1409 | struct GNUNET_NSE_FloodMessage, | ||
1410 | NULL), | ||
1411 | GNUNET_MQ_handler_end () }; | ||
1412 | char *proof; | ||
1413 | struct GNUNET_CRYPTO_EddsaPrivateKey *pk; | ||
1414 | |||
1415 | (void) cls; | ||
1416 | (void) service; | ||
1417 | cfg = c; | ||
1418 | if (GNUNET_OK != GNUNET_CONFIGURATION_get_value_time (cfg, | ||
1419 | "NSE", | ||
1420 | "INTERVAL", | ||
1421 | &gnunet_nse_interval)) | ||
1422 | { | ||
1423 | GNUNET_log_config_missing (GNUNET_ERROR_TYPE_ERROR, "NSE", "INTERVAL"); | ||
1424 | GNUNET_SCHEDULER_shutdown (); | ||
1425 | return; | ||
1426 | } | ||
1427 | if (GNUNET_OK != GNUNET_CONFIGURATION_get_value_time (cfg, | ||
1428 | "NSE", | ||
1429 | "WORKDELAY", | ||
1430 | &proof_find_delay)) | ||
1431 | { | ||
1432 | GNUNET_log_config_missing (GNUNET_ERROR_TYPE_ERROR, "NSE", "WORKDELAY"); | ||
1433 | GNUNET_SCHEDULER_shutdown (); | ||
1434 | return; | ||
1435 | } | ||
1436 | if (GNUNET_OK != GNUNET_CONFIGURATION_get_value_number (cfg, | ||
1437 | "NSE", | ||
1438 | "WORKBITS", | ||
1439 | &nse_work_required)) | ||
1440 | { | ||
1441 | GNUNET_log_config_missing (GNUNET_ERROR_TYPE_ERROR, "NSE", "WORKBITS"); | ||
1442 | GNUNET_SCHEDULER_shutdown (); | ||
1443 | return; | ||
1444 | } | ||
1445 | if (nse_work_required >= sizeof(struct GNUNET_HashCode) * 8) | ||
1446 | { | ||
1447 | GNUNET_log_config_invalid (GNUNET_ERROR_TYPE_ERROR, | ||
1448 | "NSE", | ||
1449 | "WORKBITS", | ||
1450 | _ ("Value is too large.\n")); | ||
1451 | GNUNET_SCHEDULER_shutdown (); | ||
1452 | return; | ||
1453 | } | ||
1454 | |||
1455 | #if ENABLE_NSE_HISTOGRAM | ||
1456 | { | ||
1457 | char *histogram_dir; | ||
1458 | char *histogram_fn; | ||
1459 | |||
1460 | if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_filename (cfg, | ||
1461 | "NSE", | ||
1462 | "HISTOGRAM_DIR", | ||
1463 | &histogram_dir)) | ||
1464 | { | ||
1465 | GNUNET_assert ( | ||
1466 | 0 < GNUNET_asprintf (&histogram_fn, "%s/timestamps", histogram_dir)); | ||
1467 | GNUNET_free (histogram_dir); | ||
1468 | histogram = GNUNET_BIO_write_open_file (histogram_fn); | ||
1469 | if (NULL == histogram) | ||
1470 | GNUNET_log (GNUNET_ERROR_TYPE_WARNING, | ||
1471 | "Unable to open histogram file `%s'\n", | ||
1472 | histogram_fn); | ||
1473 | GNUNET_free (histogram_fn); | ||
1474 | } | ||
1475 | logger_test = GNUNET_CLIENT_service_test ("testbed-logger", | ||
1476 | cfg, | ||
1477 | GNUNET_TIME_UNIT_SECONDS, | ||
1478 | &status_cb, | ||
1479 | NULL); | ||
1480 | } | ||
1481 | #endif | ||
1482 | |||
1483 | GNUNET_SCHEDULER_add_shutdown (&shutdown_task, NULL); | ||
1484 | pk = GNUNET_CRYPTO_eddsa_key_create_from_configuration (cfg); | ||
1485 | GNUNET_assert (NULL != pk); | ||
1486 | my_private_key = pk; | ||
1487 | GNUNET_CRYPTO_eddsa_key_get_public (my_private_key, &my_identity.public_key); | ||
1488 | if (GNUNET_OK != | ||
1489 | GNUNET_CONFIGURATION_get_value_filename (cfg, "NSE", "PROOFFILE", &proof)) | ||
1490 | { | ||
1491 | GNUNET_log_config_missing (GNUNET_ERROR_TYPE_ERROR, "NSE", "PROOFFILE"); | ||
1492 | GNUNET_free (my_private_key); | ||
1493 | my_private_key = NULL; | ||
1494 | GNUNET_SCHEDULER_shutdown (); | ||
1495 | return; | ||
1496 | } | ||
1497 | if ((GNUNET_YES != GNUNET_DISK_file_test (proof)) || | ||
1498 | (sizeof(my_proof) != | ||
1499 | GNUNET_DISK_fn_read (proof, &my_proof, sizeof(my_proof)))) | ||
1500 | my_proof = 0; | ||
1501 | GNUNET_free (proof); | ||
1502 | proof_task = | ||
1503 | GNUNET_SCHEDULER_add_with_priority (GNUNET_SCHEDULER_PRIORITY_IDLE, | ||
1504 | &find_proof, | ||
1505 | NULL); | ||
1506 | |||
1507 | peers = GNUNET_CONTAINER_multipeermap_create (128, GNUNET_YES); | ||
1508 | nc = GNUNET_notification_context_create (1); | ||
1509 | /* Connect to core service and register core handlers */ | ||
1510 | core_api = | ||
1511 | GNUNET_CORE_connect (cfg, /* Main configuration */ | ||
1512 | NULL, /* Closure passed to functions */ | ||
1513 | &core_init, /* Call core_init once connected */ | ||
1514 | &handle_core_connect, /* Handle connects */ | ||
1515 | &handle_core_disconnect, /* Handle disconnects */ | ||
1516 | core_handlers); /* Register these handlers */ | ||
1517 | if (NULL == core_api) | ||
1518 | { | ||
1519 | GNUNET_SCHEDULER_shutdown (); | ||
1520 | return; | ||
1521 | } | ||
1522 | stats = GNUNET_STATISTICS_create ("nse", cfg); | ||
1523 | } | ||
1524 | |||
1525 | |||
1526 | /** | ||
1527 | * Callback called when a client connects to the service. | ||
1528 | * | ||
1529 | * @param cls closure for the service | ||
1530 | * @param c the new client that connected to the service | ||
1531 | * @param mq the message queue used to send messages to the client | ||
1532 | * @return @a c | ||
1533 | */ | ||
1534 | static void * | ||
1535 | client_connect_cb (void *cls, | ||
1536 | struct GNUNET_SERVICE_Client *c, | ||
1537 | struct GNUNET_MQ_Handle *mq) | ||
1538 | { | ||
1539 | (void) cls; | ||
1540 | (void) mq; | ||
1541 | return c; | ||
1542 | } | ||
1543 | |||
1544 | |||
1545 | /** | ||
1546 | * Callback called when a client disconnected from the service | ||
1547 | * | ||
1548 | * @param cls closure for the service | ||
1549 | * @param c the client that disconnected | ||
1550 | * @param internal_cls should be equal to @a c | ||
1551 | */ | ||
1552 | static void | ||
1553 | client_disconnect_cb (void *cls, | ||
1554 | struct GNUNET_SERVICE_Client *c, | ||
1555 | void *internal_cls) | ||
1556 | { | ||
1557 | (void) cls; | ||
1558 | GNUNET_assert (c == internal_cls); | ||
1559 | } | ||
1560 | |||
1561 | |||
1562 | /** | ||
1563 | * Define "main" method using service macro. | ||
1564 | */ | ||
1565 | GNUNET_SERVICE_MAIN ("nse", | ||
1566 | GNUNET_SERVICE_OPTION_NONE, | ||
1567 | &run, | ||
1568 | &client_connect_cb, | ||
1569 | &client_disconnect_cb, | ||
1570 | NULL, | ||
1571 | GNUNET_MQ_hd_fixed_size (start, | ||
1572 | GNUNET_MESSAGE_TYPE_NSE_START, | ||
1573 | struct GNUNET_MessageHeader, | ||
1574 | NULL), | ||
1575 | GNUNET_MQ_handler_end ()); | ||
1576 | |||
1577 | |||
1578 | #if defined(__linux__) && defined(__GLIBC__) | ||
1579 | #include <malloc.h> | ||
1580 | |||
1581 | /** | ||
1582 | * MINIMIZE heap size (way below 128k) since this process doesn't need much. | ||
1583 | */ | ||
1584 | void __attribute__ ((constructor)) | ||
1585 | GNUNET_ARM_memory_init () | ||
1586 | { | ||
1587 | mallopt (M_TRIM_THRESHOLD, 4 * 1024); | ||
1588 | mallopt (M_TOP_PAD, 1 * 1024); | ||
1589 | malloc_trim (0); | ||
1590 | } | ||
1591 | |||
1592 | |||
1593 | #endif | ||
1594 | |||
1595 | |||
1596 | /* end of gnunet-service-nse.c */ | ||