diff options
Diffstat (limited to 'src/nse/gnunet-service-nse.c')
-rw-r--r-- | src/nse/gnunet-service-nse.c | 1587 |
1 files changed, 0 insertions, 1587 deletions
diff --git a/src/nse/gnunet-service-nse.c b/src/nse/gnunet-service-nse.c deleted file mode 100644 index 56014752d..000000000 --- a/src/nse/gnunet-service-nse.c +++ /dev/null | |||
@@ -1,1587 +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; /* return NaN (due to estimate_count == 0 causing 0.0/0.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 | struct GNUNET_HashCode xor; | ||
509 | |||
510 | GNUNET_CRYPTO_hash (×tamp.abs_value_us, | ||
511 | sizeof(timestamp.abs_value_us), | ||
512 | ×tamp_hash); | ||
513 | GNUNET_CRYPTO_hash (id, | ||
514 | sizeof(struct GNUNET_PeerIdentity), | ||
515 | &pid_hash); | ||
516 | GNUNET_CRYPTO_hash_xor (&pid_hash, | ||
517 | ×tamp_hash, | ||
518 | &xor); | ||
519 | return GNUNET_CRYPTO_hash_count_leading_zeros (&xor); | ||
520 | } | ||
521 | |||
522 | |||
523 | /** | ||
524 | * Get the transmission delay that should be applied for a | ||
525 | * particular round. | ||
526 | * | ||
527 | * @param round_offset -1 for the previous round (random delay between 0 and 50ms) | ||
528 | * 0 for the current round (based on our proximity to time key) | ||
529 | * @return delay that should be applied | ||
530 | */ | ||
531 | static struct GNUNET_TIME_Relative | ||
532 | get_transmit_delay (int round_offset) | ||
533 | { | ||
534 | struct GNUNET_TIME_Relative ret; | ||
535 | struct GNUNET_TIME_Absolute tgt; | ||
536 | double dist_delay; | ||
537 | uint32_t matching_bits; | ||
538 | |||
539 | switch (round_offset) | ||
540 | { | ||
541 | case -1: | ||
542 | /* previous round is randomized between 0 and 50 ms */ | ||
543 | #if USE_RANDOM_DELAYS | ||
544 | ret.rel_value_us = | ||
545 | GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK, 50); | ||
546 | #else | ||
547 | ret = GNUNET_TIME_UNIT_ZERO; | ||
548 | #endif | ||
549 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | ||
550 | "Transmitting previous round behind schedule in %s\n", | ||
551 | GNUNET_STRINGS_relative_time_to_string (ret, GNUNET_YES)); | ||
552 | return ret; | ||
553 | |||
554 | case 0: | ||
555 | /* current round is based on best-known matching_bits */ | ||
556 | matching_bits = | ||
557 | ntohl (size_estimate_messages[estimate_index].matching_bits); | ||
558 | dist_delay = get_matching_bits_delay (matching_bits); | ||
559 | dist_delay += get_delay_randomization (matching_bits).rel_value_us; | ||
560 | ret.rel_value_us = (uint64_t) dist_delay; | ||
561 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | ||
562 | "For round %s, delay for %u matching bits is %s\n", | ||
563 | GNUNET_STRINGS_absolute_time_to_string (current_timestamp), | ||
564 | (unsigned int) matching_bits, | ||
565 | GNUNET_STRINGS_relative_time_to_string (ret, GNUNET_YES)); | ||
566 | /* now consider round start time and add delay to it */ | ||
567 | tgt = GNUNET_TIME_absolute_add (current_timestamp, ret); | ||
568 | return GNUNET_TIME_absolute_get_remaining (tgt); | ||
569 | } | ||
570 | GNUNET_break (0); | ||
571 | return GNUNET_TIME_UNIT_FOREVER_REL; | ||
572 | } | ||
573 | |||
574 | |||
575 | /** | ||
576 | * Task that triggers a NSE P2P transmission. | ||
577 | * | ||
578 | * @param cls the `struct NSEPeerEntry *` | ||
579 | */ | ||
580 | static void | ||
581 | transmit_task_cb (void *cls) | ||
582 | { | ||
583 | struct NSEPeerEntry *peer_entry = cls; | ||
584 | unsigned int idx; | ||
585 | struct GNUNET_MQ_Envelope *env; | ||
586 | |||
587 | peer_entry->transmit_task = NULL; | ||
588 | idx = estimate_index; | ||
589 | if (GNUNET_NO == peer_entry->previous_round) | ||
590 | { | ||
591 | idx = (idx + HISTORY_SIZE - 1) % HISTORY_SIZE; | ||
592 | peer_entry->previous_round = GNUNET_YES; | ||
593 | peer_entry->transmit_task = | ||
594 | GNUNET_SCHEDULER_add_delayed (get_transmit_delay (0), | ||
595 | &transmit_task_cb, | ||
596 | peer_entry); | ||
597 | } | ||
598 | if ((0 == ntohl (size_estimate_messages[idx].hop_count)) && | ||
599 | (NULL != proof_task)) | ||
600 | { | ||
601 | GNUNET_STATISTICS_update (stats, | ||
602 | "# flood messages not generated (no proof yet)", | ||
603 | 1, | ||
604 | GNUNET_NO); | ||
605 | return; | ||
606 | } | ||
607 | if (0 == ntohs (size_estimate_messages[idx].header.size)) | ||
608 | { | ||
609 | GNUNET_STATISTICS_update (stats, | ||
610 | "# flood messages not generated (lack of history)", | ||
611 | 1, | ||
612 | GNUNET_NO); | ||
613 | return; | ||
614 | } | ||
615 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | ||
616 | "In round %s, sending to `%s' estimate with %u bits\n", | ||
617 | GNUNET_STRINGS_absolute_time_to_string ( | ||
618 | GNUNET_TIME_absolute_ntoh ( | ||
619 | size_estimate_messages[idx].timestamp)), | ||
620 | GNUNET_i2s (peer_entry->id), | ||
621 | (unsigned int) ntohl (size_estimate_messages[idx].matching_bits)); | ||
622 | if (0 == ntohl (size_estimate_messages[idx].hop_count)) | ||
623 | GNUNET_STATISTICS_update (stats, "# flood messages started", 1, GNUNET_NO); | ||
624 | GNUNET_STATISTICS_update (stats, | ||
625 | "# flood messages transmitted", | ||
626 | 1, | ||
627 | GNUNET_NO); | ||
628 | #if ENABLE_NSE_HISTOGRAM | ||
629 | peer_entry->transmitted_messages++; | ||
630 | peer_entry->last_transmitted_size = | ||
631 | ntohl (size_estimate_messages[idx].matching_bits); | ||
632 | #endif | ||
633 | env = GNUNET_MQ_msg_copy (&size_estimate_messages[idx].header); | ||
634 | GNUNET_MQ_send (peer_entry->mq, env); | ||
635 | } | ||
636 | |||
637 | |||
638 | /** | ||
639 | * We've sent on our flood message or one that we received which was | ||
640 | * validated and closer than ours. Update the global list of recent | ||
641 | * messages and the average. Also re-broadcast the message to any | ||
642 | * clients. | ||
643 | */ | ||
644 | static void | ||
645 | update_network_size_estimate () | ||
646 | { | ||
647 | struct GNUNET_NSE_ClientMessage em; | ||
648 | |||
649 | setup_estimate_message (&em); | ||
650 | GNUNET_notification_context_broadcast (nc, &em.header, GNUNET_YES); | ||
651 | } | ||
652 | |||
653 | |||
654 | /** | ||
655 | * Setup a flood message in our history array at the given | ||
656 | * slot offset for the given timestamp. | ||
657 | * | ||
658 | * @param slot index to use | ||
659 | * @param ts timestamp to use | ||
660 | */ | ||
661 | static void | ||
662 | setup_flood_message (unsigned int slot, struct GNUNET_TIME_Absolute ts) | ||
663 | { | ||
664 | struct GNUNET_NSE_FloodMessage *fm; | ||
665 | uint32_t matching_bits; | ||
666 | |||
667 | matching_bits = get_matching_bits (ts, &my_identity); | ||
668 | fm = &size_estimate_messages[slot]; | ||
669 | fm->header.size = htons (sizeof(struct GNUNET_NSE_FloodMessage)); | ||
670 | fm->header.type = htons (GNUNET_MESSAGE_TYPE_NSE_P2P_FLOOD); | ||
671 | fm->hop_count = htonl (0); | ||
672 | fm->purpose.purpose = htonl (GNUNET_SIGNATURE_PURPOSE_NSE_SEND); | ||
673 | fm->purpose.size = | ||
674 | htonl (sizeof(struct GNUNET_NSE_FloodMessage) | ||
675 | - sizeof(struct GNUNET_MessageHeader) - sizeof(uint32_t) | ||
676 | - sizeof(struct GNUNET_CRYPTO_EddsaSignature)); | ||
677 | fm->matching_bits = htonl (matching_bits); | ||
678 | fm->timestamp = GNUNET_TIME_absolute_hton (ts); | ||
679 | fm->origin = my_identity; | ||
680 | fm->proof_of_work = my_proof; | ||
681 | if (nse_work_required > 0) | ||
682 | GNUNET_assert (GNUNET_OK == | ||
683 | GNUNET_CRYPTO_eddsa_sign_ (my_private_key, | ||
684 | &fm->purpose, | ||
685 | &fm->signature)); | ||
686 | else | ||
687 | memset (&fm->signature, 0, sizeof(fm->signature)); | ||
688 | } | ||
689 | |||
690 | |||
691 | /** | ||
692 | * Schedule transmission for the given peer for the current round based | ||
693 | * on what we know about the desired delay. | ||
694 | * | ||
695 | * @param cls unused | ||
696 | * @param key hash of peer identity | ||
697 | * @param value the `struct NSEPeerEntry` | ||
698 | * @return #GNUNET_OK (continue to iterate) | ||
699 | */ | ||
700 | static int | ||
701 | schedule_current_round (void *cls, | ||
702 | const struct GNUNET_PeerIdentity *key, | ||
703 | void *value) | ||
704 | { | ||
705 | struct NSEPeerEntry *peer_entry = value; | ||
706 | struct GNUNET_TIME_Relative delay; | ||
707 | |||
708 | (void) cls; | ||
709 | (void) key; | ||
710 | if (NULL != peer_entry->transmit_task) | ||
711 | { | ||
712 | GNUNET_SCHEDULER_cancel (peer_entry->transmit_task); | ||
713 | peer_entry->previous_round = GNUNET_NO; | ||
714 | } | ||
715 | #if ENABLE_NSE_HISTOGRAM | ||
716 | if (peer_entry->received_messages > 1) | ||
717 | GNUNET_STATISTICS_update (stats, | ||
718 | "# extra messages", | ||
719 | peer_entry->received_messages - 1, | ||
720 | GNUNET_NO); | ||
721 | peer_entry->transmitted_messages = 0; | ||
722 | peer_entry->last_transmitted_size = 0; | ||
723 | peer_entry->received_messages = 0; | ||
724 | #endif | ||
725 | delay = | ||
726 | get_transmit_delay ((GNUNET_NO == peer_entry->previous_round) ? -1 : 0); | ||
727 | peer_entry->transmit_task = | ||
728 | GNUNET_SCHEDULER_add_delayed (delay, &transmit_task_cb, peer_entry); | ||
729 | return GNUNET_OK; | ||
730 | } | ||
731 | |||
732 | |||
733 | /** | ||
734 | * Update our flood message to be sent (and our timestamps). | ||
735 | * | ||
736 | * @param cls unused | ||
737 | */ | ||
738 | static void | ||
739 | update_flood_message (void *cls) | ||
740 | { | ||
741 | struct GNUNET_TIME_Relative offset; | ||
742 | |||
743 | (void) cls; | ||
744 | flood_task = NULL; | ||
745 | offset = GNUNET_TIME_absolute_get_remaining (next_timestamp); | ||
746 | if (0 != offset.rel_value_us) | ||
747 | { | ||
748 | /* somehow run early, delay more */ | ||
749 | flood_task = | ||
750 | GNUNET_SCHEDULER_add_delayed (offset, &update_flood_message, NULL); | ||
751 | return; | ||
752 | } | ||
753 | estimate_index = (estimate_index + 1) % HISTORY_SIZE; | ||
754 | if (estimate_count < HISTORY_SIZE) | ||
755 | estimate_count++; | ||
756 | current_timestamp = next_timestamp; | ||
757 | next_timestamp = | ||
758 | GNUNET_TIME_absolute_add (current_timestamp, gnunet_nse_interval); | ||
759 | if ((current_timestamp.abs_value_us == | ||
760 | GNUNET_TIME_absolute_ntoh (next_message.timestamp).abs_value_us) && | ||
761 | (get_matching_bits (current_timestamp, &my_identity) < | ||
762 | ntohl (next_message.matching_bits))) | ||
763 | { | ||
764 | /* we received a message for this round way early, use it! */ | ||
765 | size_estimate_messages[estimate_index] = next_message; | ||
766 | size_estimate_messages[estimate_index].hop_count = | ||
767 | htonl (1 + ntohl (next_message.hop_count)); | ||
768 | } | ||
769 | else | ||
770 | setup_flood_message (estimate_index, current_timestamp); | ||
771 | next_message.matching_bits = htonl (0); /* reset for 'next' round */ | ||
772 | hop_count_max = 0; | ||
773 | for (unsigned int i = 0; i < HISTORY_SIZE; i++) | ||
774 | hop_count_max = | ||
775 | GNUNET_MAX (ntohl (size_estimate_messages[i].hop_count), hop_count_max); | ||
776 | GNUNET_CONTAINER_multipeermap_iterate (peers, &schedule_current_round, NULL); | ||
777 | flood_task = | ||
778 | GNUNET_SCHEDULER_add_at (next_timestamp, &update_flood_message, NULL); | ||
779 | } | ||
780 | |||
781 | |||
782 | /** | ||
783 | * Check whether the given public key and integer are a valid proof of | ||
784 | * work. | ||
785 | * | ||
786 | * @param pkey the public key | ||
787 | * @param val the integer | ||
788 | * @return #GNUNET_YES if valid, #GNUNET_NO if not | ||
789 | */ | ||
790 | static enum GNUNET_GenericReturnValue | ||
791 | check_proof_of_work (const struct GNUNET_CRYPTO_EddsaPublicKey *pkey, | ||
792 | uint64_t val) | ||
793 | { | ||
794 | char buf[sizeof(struct GNUNET_CRYPTO_EddsaPublicKey) | ||
795 | + sizeof(val)] GNUNET_ALIGN; | ||
796 | struct GNUNET_HashCode result; | ||
797 | |||
798 | GNUNET_memcpy (buf, &val, sizeof(val)); | ||
799 | GNUNET_memcpy (&buf[sizeof(val)], | ||
800 | pkey, | ||
801 | sizeof(struct GNUNET_CRYPTO_EddsaPublicKey)); | ||
802 | GNUNET_CRYPTO_pow_hash (&salt, | ||
803 | buf, | ||
804 | sizeof(buf), | ||
805 | &result); | ||
806 | return (GNUNET_CRYPTO_hash_count_leading_zeros (&result) >= | ||
807 | nse_work_required) | ||
808 | ? GNUNET_YES | ||
809 | : GNUNET_NO; | ||
810 | } | ||
811 | |||
812 | |||
813 | /** | ||
814 | * Write our current proof to disk. | ||
815 | */ | ||
816 | static void | ||
817 | write_proof (void) | ||
818 | { | ||
819 | char *proof; | ||
820 | |||
821 | if (GNUNET_OK != | ||
822 | GNUNET_CONFIGURATION_get_value_filename (cfg, | ||
823 | "NSE", | ||
824 | "PROOFFILE", | ||
825 | &proof)) | ||
826 | return; | ||
827 | (void) GNUNET_DISK_directory_remove (proof); | ||
828 | if (GNUNET_OK != | ||
829 | GNUNET_DISK_fn_write (proof, | ||
830 | &my_proof, | ||
831 | sizeof(my_proof), | ||
832 | GNUNET_DISK_PERM_USER_READ | ||
833 | | GNUNET_DISK_PERM_USER_WRITE)) | ||
834 | GNUNET_log_strerror_file (GNUNET_ERROR_TYPE_WARNING, | ||
835 | "write", | ||
836 | proof); | ||
837 | GNUNET_free (proof); | ||
838 | } | ||
839 | |||
840 | |||
841 | /** | ||
842 | * Find our proof of work. | ||
843 | * | ||
844 | * @param cls closure (unused) | ||
845 | */ | ||
846 | static void | ||
847 | find_proof (void *cls) | ||
848 | { | ||
849 | #define ROUND_SIZE 10 | ||
850 | uint64_t counter; | ||
851 | char buf[sizeof(struct GNUNET_CRYPTO_EddsaPublicKey) | ||
852 | + sizeof(uint64_t)] GNUNET_ALIGN; | ||
853 | struct GNUNET_HashCode result; | ||
854 | unsigned int i; | ||
855 | |||
856 | (void) cls; | ||
857 | proof_task = NULL; | ||
858 | GNUNET_memcpy (&buf[sizeof(uint64_t)], | ||
859 | &my_identity, | ||
860 | sizeof(struct GNUNET_PeerIdentity)); | ||
861 | i = 0; | ||
862 | counter = my_proof; | ||
863 | while ((counter != UINT64_MAX) && (i < ROUND_SIZE)) | ||
864 | { | ||
865 | GNUNET_memcpy (buf, &counter, sizeof(uint64_t)); | ||
866 | GNUNET_CRYPTO_pow_hash (&salt, | ||
867 | buf, | ||
868 | sizeof(buf), | ||
869 | &result); | ||
870 | if (nse_work_required <= | ||
871 | GNUNET_CRYPTO_hash_count_leading_zeros (&result)) | ||
872 | { | ||
873 | my_proof = counter; | ||
874 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | ||
875 | "Proof of work found: %llu!\n", | ||
876 | (unsigned long long) GNUNET_ntohll (counter)); | ||
877 | write_proof (); | ||
878 | setup_flood_message (estimate_index, current_timestamp); | ||
879 | return; | ||
880 | } | ||
881 | counter++; | ||
882 | i++; | ||
883 | } | ||
884 | if (my_proof / (100 * ROUND_SIZE) < counter / (100 * ROUND_SIZE)) | ||
885 | { | ||
886 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | ||
887 | "Testing proofs currently at %llu\n", | ||
888 | (unsigned long long) counter); | ||
889 | /* remember progress every 100 rounds */ | ||
890 | my_proof = counter; | ||
891 | write_proof (); | ||
892 | } | ||
893 | else | ||
894 | { | ||
895 | my_proof = counter; | ||
896 | } | ||
897 | proof_task = | ||
898 | GNUNET_SCHEDULER_add_delayed_with_priority (proof_find_delay, | ||
899 | GNUNET_SCHEDULER_PRIORITY_IDLE, | ||
900 | &find_proof, | ||
901 | NULL); | ||
902 | } | ||
903 | |||
904 | |||
905 | /** | ||
906 | * An incoming flood message has been received which claims | ||
907 | * to have more bits matching than any we know in this time | ||
908 | * period. Verify the signature and/or proof of work. | ||
909 | * | ||
910 | * @param incoming_flood the message to verify | ||
911 | * @return #GNUNET_YES if the message is verified | ||
912 | * #GNUNET_NO if the key/signature don't verify | ||
913 | */ | ||
914 | static int | ||
915 | verify_message_crypto (const struct GNUNET_NSE_FloodMessage *incoming_flood) | ||
916 | { | ||
917 | if (GNUNET_YES != check_proof_of_work (&incoming_flood->origin.public_key, | ||
918 | incoming_flood->proof_of_work)) | ||
919 | { | ||
920 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | ||
921 | "Proof of work invalid: %llu!\n", | ||
922 | (unsigned long long) GNUNET_ntohll ( | ||
923 | incoming_flood->proof_of_work)); | ||
924 | GNUNET_break_op (0); | ||
925 | return GNUNET_NO; | ||
926 | } | ||
927 | if ((nse_work_required > 0) && | ||
928 | (GNUNET_OK != | ||
929 | GNUNET_CRYPTO_eddsa_verify_ (GNUNET_SIGNATURE_PURPOSE_NSE_SEND, | ||
930 | &incoming_flood->purpose, | ||
931 | &incoming_flood->signature, | ||
932 | &incoming_flood->origin.public_key))) | ||
933 | { | ||
934 | GNUNET_break_op (0); | ||
935 | return GNUNET_NO; | ||
936 | } | ||
937 | return GNUNET_YES; | ||
938 | } | ||
939 | |||
940 | |||
941 | /** | ||
942 | * Update transmissions for the given peer for the current round based | ||
943 | * on updated proximity information. | ||
944 | * | ||
945 | * @param cls peer entry to exclude from updates | ||
946 | * @param key hash of peer identity | ||
947 | * @param value the `struct NSEPeerEntry *` of a peer to transmit to | ||
948 | * @return #GNUNET_OK (continue to iterate) | ||
949 | */ | ||
950 | static int | ||
951 | update_flood_times (void *cls, | ||
952 | const struct GNUNET_PeerIdentity *key, | ||
953 | void *value) | ||
954 | { | ||
955 | struct NSEPeerEntry *exclude = cls; | ||
956 | struct NSEPeerEntry *peer_entry = value; | ||
957 | struct GNUNET_TIME_Relative delay; | ||
958 | |||
959 | (void) key; | ||
960 | if (peer_entry == exclude) | ||
961 | return GNUNET_OK; /* trigger of the update */ | ||
962 | if (GNUNET_NO == peer_entry->previous_round) | ||
963 | { | ||
964 | /* still stuck in previous round, no point to update, check that | ||
965 | * we are active here though... */ | ||
966 | if (NULL == peer_entry->transmit_task) | ||
967 | { | ||
968 | GNUNET_break (0); | ||
969 | } | ||
970 | return GNUNET_OK; | ||
971 | } | ||
972 | if (NULL != peer_entry->transmit_task) | ||
973 | { | ||
974 | GNUNET_SCHEDULER_cancel (peer_entry->transmit_task); | ||
975 | peer_entry->transmit_task = NULL; | ||
976 | } | ||
977 | delay = get_transmit_delay (0); | ||
978 | peer_entry->transmit_task = | ||
979 | GNUNET_SCHEDULER_add_delayed (delay, &transmit_task_cb, peer_entry); | ||
980 | return GNUNET_OK; | ||
981 | } | ||
982 | |||
983 | |||
984 | /** | ||
985 | * Core handler for size estimate flooding messages. | ||
986 | * | ||
987 | * @param cls peer this message is from | ||
988 | * @param incoming_flood received message | ||
989 | */ | ||
990 | static void | ||
991 | handle_p2p_estimate (void *cls, | ||
992 | const struct GNUNET_NSE_FloodMessage *incoming_flood) | ||
993 | { | ||
994 | struct NSEPeerEntry *peer_entry = cls; | ||
995 | struct GNUNET_TIME_Absolute ts; | ||
996 | uint32_t matching_bits; | ||
997 | unsigned int idx; | ||
998 | |||
999 | #if ENABLE_NSE_HISTOGRAM | ||
1000 | { | ||
1001 | uint64_t t; | ||
1002 | |||
1003 | t = GNUNET_TIME_absolute_get ().abs_value_us; | ||
1004 | if (NULL != lh) | ||
1005 | GNUNET_TESTBED_LOGGER_write (lh, &t, sizeof(uint64_t)); | ||
1006 | if (NULL != histogram) | ||
1007 | GNUNET_BIO_write_int64 (histogram, "histogram-time", t); | ||
1008 | } | ||
1009 | #endif | ||
1010 | GNUNET_STATISTICS_update (stats, "# flood messages received", 1, GNUNET_NO); | ||
1011 | matching_bits = ntohl (incoming_flood->matching_bits); | ||
1012 | #if DEBUG_NSE | ||
1013 | { | ||
1014 | char origin[5]; | ||
1015 | char pred[5]; | ||
1016 | struct GNUNET_PeerIdentity os; | ||
1017 | |||
1018 | GNUNET_snprintf (origin, | ||
1019 | sizeof(origin), | ||
1020 | "%s", | ||
1021 | GNUNET_i2s (&incoming_flood->origin)); | ||
1022 | GNUNET_snprintf (pred, sizeof(pred), "%s", GNUNET_i2s (peer_entry->id)); | ||
1023 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | ||
1024 | "Flood at %s from `%s' via `%s' at `%s' with bits %u\n", | ||
1025 | GNUNET_STRINGS_absolute_time_to_string ( | ||
1026 | GNUNET_TIME_absolute_ntoh (incoming_flood->timestamp)), | ||
1027 | origin, | ||
1028 | pred, | ||
1029 | GNUNET_i2s (&my_identity), | ||
1030 | (unsigned int) matching_bits); | ||
1031 | } | ||
1032 | #endif | ||
1033 | |||
1034 | #if ENABLE_NSE_HISTOGRAM | ||
1035 | peer_entry->received_messages++; | ||
1036 | if ((peer_entry->transmitted_messages > 0) && | ||
1037 | (peer_entry->last_transmitted_size >= matching_bits) ) | ||
1038 | GNUNET_STATISTICS_update (stats, "# cross messages", 1, GNUNET_NO); | ||
1039 | #endif | ||
1040 | |||
1041 | ts = GNUNET_TIME_absolute_ntoh (incoming_flood->timestamp); | ||
1042 | if (ts.abs_value_us == current_timestamp.abs_value_us) | ||
1043 | idx = estimate_index; | ||
1044 | else if (ts.abs_value_us == | ||
1045 | current_timestamp.abs_value_us - gnunet_nse_interval.rel_value_us) | ||
1046 | idx = (estimate_index + HISTORY_SIZE - 1) % HISTORY_SIZE; | ||
1047 | else if (ts.abs_value_us == next_timestamp.abs_value_us) | ||
1048 | { | ||
1049 | if (matching_bits <= ntohl (next_message.matching_bits)) | ||
1050 | return; /* ignore, simply too early/late */ | ||
1051 | if (GNUNET_YES != verify_message_crypto (incoming_flood)) | ||
1052 | { | ||
1053 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, | ||
1054 | "Peer %s is likely ill-configured!\n", | ||
1055 | GNUNET_i2s (peer_entry->id)); | ||
1056 | GNUNET_break_op (0); | ||
1057 | return; | ||
1058 | } | ||
1059 | next_message = *incoming_flood; | ||
1060 | return; | ||
1061 | } | ||
1062 | else | ||
1063 | { | ||
1064 | GNUNET_STATISTICS_update (stats, | ||
1065 | "# flood messages discarded (clock skew too large)", | ||
1066 | 1, | ||
1067 | GNUNET_NO); | ||
1068 | return; | ||
1069 | } | ||
1070 | if (0 == (GNUNET_memcmp (peer_entry->id, &my_identity))) | ||
1071 | { | ||
1072 | /* send to self, update our own estimate IF this also comes from us! */ | ||
1073 | if (0 == GNUNET_memcmp (&incoming_flood->origin, &my_identity)) | ||
1074 | update_network_size_estimate (); | ||
1075 | return; | ||
1076 | } | ||
1077 | if (matching_bits == ntohl (size_estimate_messages[idx].matching_bits)) | ||
1078 | { | ||
1079 | /* Cancel transmission in the other direction, as this peer clearly has | ||
1080 | up-to-date information already. Even if we didn't talk to this peer in | ||
1081 | the previous round, we should no longer send it stale information as it | ||
1082 | told us about the current round! */ | ||
1083 | peer_entry->previous_round = GNUNET_YES; | ||
1084 | if (idx != estimate_index) | ||
1085 | { | ||
1086 | /* do not transmit information for the previous round to this peer | ||
1087 | anymore (but allow current round) */ | ||
1088 | return; | ||
1089 | } | ||
1090 | /* got up-to-date information for current round, cancel transmission to | ||
1091 | * this peer altogether */ | ||
1092 | if (NULL != peer_entry->transmit_task) | ||
1093 | { | ||
1094 | GNUNET_SCHEDULER_cancel (peer_entry->transmit_task); | ||
1095 | peer_entry->transmit_task = NULL; | ||
1096 | } | ||
1097 | return; | ||
1098 | } | ||
1099 | if (matching_bits < ntohl (size_estimate_messages[idx].matching_bits)) | ||
1100 | { | ||
1101 | if ((idx < estimate_index) && (peer_entry->previous_round == GNUNET_YES)) | ||
1102 | { | ||
1103 | peer_entry->previous_round = GNUNET_NO; | ||
1104 | } | ||
1105 | /* push back our result now, that peer is spreading bad information... */ | ||
1106 | if (NULL != peer_entry->transmit_task) | ||
1107 | GNUNET_SCHEDULER_cancel (peer_entry->transmit_task); | ||
1108 | peer_entry->transmit_task = | ||
1109 | GNUNET_SCHEDULER_add_now (&transmit_task_cb, peer_entry); | ||
1110 | /* Not closer than our most recent message, no need to do work here */ | ||
1111 | GNUNET_STATISTICS_update (stats, | ||
1112 | "# flood messages ignored (had closer already)", | ||
1113 | 1, | ||
1114 | GNUNET_NO); | ||
1115 | return; | ||
1116 | } | ||
1117 | if (GNUNET_YES != verify_message_crypto (incoming_flood)) | ||
1118 | { | ||
1119 | GNUNET_break_op (0); | ||
1120 | return; | ||
1121 | } | ||
1122 | GNUNET_assert (matching_bits > | ||
1123 | ntohl (size_estimate_messages[idx].matching_bits)); | ||
1124 | /* Cancel transmission in the other direction, as this peer clearly has | ||
1125 | * up-to-date information already. | ||
1126 | */ | ||
1127 | peer_entry->previous_round = GNUNET_YES; | ||
1128 | if (idx == estimate_index) | ||
1129 | { | ||
1130 | /* cancel any activity for current round */ | ||
1131 | if (NULL != peer_entry->transmit_task) | ||
1132 | { | ||
1133 | GNUNET_SCHEDULER_cancel (peer_entry->transmit_task); | ||
1134 | peer_entry->transmit_task = NULL; | ||
1135 | } | ||
1136 | } | ||
1137 | size_estimate_messages[idx] = *incoming_flood; | ||
1138 | size_estimate_messages[idx].hop_count = | ||
1139 | htonl (ntohl (incoming_flood->hop_count) + 1); | ||
1140 | hop_count_max = | ||
1141 | GNUNET_MAX (ntohl (incoming_flood->hop_count) + 1, hop_count_max); | ||
1142 | GNUNET_STATISTICS_set (stats, | ||
1143 | "# estimated network diameter", | ||
1144 | hop_count_max, | ||
1145 | GNUNET_NO); | ||
1146 | |||
1147 | /* have a new, better size estimate, inform clients */ | ||
1148 | update_network_size_estimate (); | ||
1149 | |||
1150 | /* flood to rest */ | ||
1151 | GNUNET_CONTAINER_multipeermap_iterate (peers, | ||
1152 | &update_flood_times, | ||
1153 | peer_entry); | ||
1154 | } | ||
1155 | |||
1156 | |||
1157 | /** | ||
1158 | * Method called whenever a peer connects. Sets up the PeerEntry and | ||
1159 | * schedules the initial size info transmission to this peer. | ||
1160 | * | ||
1161 | * @param cls closure | ||
1162 | * @param peer peer identity this notification is about | ||
1163 | */ | ||
1164 | static void * | ||
1165 | handle_core_connect (void *cls, | ||
1166 | const struct GNUNET_PeerIdentity *peer, | ||
1167 | struct GNUNET_MQ_Handle *mq) | ||
1168 | { | ||
1169 | struct NSEPeerEntry *peer_entry; | ||
1170 | |||
1171 | (void) cls; | ||
1172 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | ||
1173 | "Peer `%s' connected to us\n", | ||
1174 | GNUNET_i2s (peer)); | ||
1175 | /* set our default transmission options */ | ||
1176 | GNUNET_MQ_set_options (mq, NSE_PRIORITY); | ||
1177 | /* create our peer entry for this peer */ | ||
1178 | peer_entry = GNUNET_new (struct NSEPeerEntry); | ||
1179 | peer_entry->id = peer; | ||
1180 | peer_entry->mq = mq; | ||
1181 | GNUNET_assert (GNUNET_OK == | ||
1182 | GNUNET_CONTAINER_multipeermap_put ( | ||
1183 | peers, | ||
1184 | peer_entry->id, | ||
1185 | peer_entry, | ||
1186 | GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)); | ||
1187 | peer_entry->transmit_task = | ||
1188 | GNUNET_SCHEDULER_add_delayed (get_transmit_delay (-1), | ||
1189 | &transmit_task_cb, | ||
1190 | peer_entry); | ||
1191 | GNUNET_STATISTICS_update (stats, "# peers connected", 1, GNUNET_NO); | ||
1192 | return peer_entry; | ||
1193 | } | ||
1194 | |||
1195 | |||
1196 | /** | ||
1197 | * Method called whenever a peer disconnects. Deletes the PeerEntry and cancels | ||
1198 | * any pending transmission requests to that peer. | ||
1199 | * | ||
1200 | * @param cls closure | ||
1201 | * @param peer peer identity this notification is about | ||
1202 | * @parma internal_cls the `struct NSEPeerEntry` for the @a peer | ||
1203 | */ | ||
1204 | static void | ||
1205 | handle_core_disconnect (void *cls, | ||
1206 | const struct GNUNET_PeerIdentity *peer, | ||
1207 | void *internal_cls) | ||
1208 | { | ||
1209 | struct NSEPeerEntry *pos = internal_cls; | ||
1210 | |||
1211 | (void) cls; | ||
1212 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | ||
1213 | "Peer `%s' disconnected from us\n", | ||
1214 | GNUNET_i2s (peer)); | ||
1215 | GNUNET_assert (GNUNET_YES == | ||
1216 | GNUNET_CONTAINER_multipeermap_remove (peers, peer, pos)); | ||
1217 | if (NULL != pos->transmit_task) | ||
1218 | { | ||
1219 | GNUNET_SCHEDULER_cancel (pos->transmit_task); | ||
1220 | pos->transmit_task = NULL; | ||
1221 | } | ||
1222 | GNUNET_free (pos); | ||
1223 | GNUNET_STATISTICS_update (stats, "# peers connected", -1, GNUNET_NO); | ||
1224 | } | ||
1225 | |||
1226 | |||
1227 | #if ENABLE_NSE_HISTOGRAM | ||
1228 | /** | ||
1229 | * Functions of this type are called to notify a successful transmission of the | ||
1230 | * message to the logger service | ||
1231 | * | ||
1232 | * @param cls NULL | ||
1233 | * @param size the amount of data sent (ignored) | ||
1234 | */ | ||
1235 | static void | ||
1236 | flush_comp_cb (void *cls, size_t size) | ||
1237 | { | ||
1238 | (void) cls; | ||
1239 | (void) size; | ||
1240 | GNUNET_TESTBED_LOGGER_disconnect (lh); | ||
1241 | lh = NULL; | ||
1242 | } | ||
1243 | |||
1244 | |||
1245 | #endif | ||
1246 | |||
1247 | |||
1248 | /** | ||
1249 | * Task run during shutdown. | ||
1250 | * | ||
1251 | * @param cls unused | ||
1252 | */ | ||
1253 | static void | ||
1254 | shutdown_task (void *cls) | ||
1255 | { | ||
1256 | (void) cls; | ||
1257 | if (NULL != flood_task) | ||
1258 | { | ||
1259 | GNUNET_SCHEDULER_cancel (flood_task); | ||
1260 | flood_task = NULL; | ||
1261 | } | ||
1262 | if (NULL != proof_task) | ||
1263 | { | ||
1264 | GNUNET_SCHEDULER_cancel (proof_task); | ||
1265 | proof_task = NULL; | ||
1266 | write_proof (); /* remember progress */ | ||
1267 | } | ||
1268 | if (NULL != nc) | ||
1269 | { | ||
1270 | GNUNET_notification_context_destroy (nc); | ||
1271 | nc = NULL; | ||
1272 | } | ||
1273 | if (NULL != core_api) | ||
1274 | { | ||
1275 | GNUNET_CORE_disconnect (core_api); | ||
1276 | core_api = NULL; | ||
1277 | } | ||
1278 | if (NULL != stats) | ||
1279 | { | ||
1280 | GNUNET_STATISTICS_destroy (stats, GNUNET_NO); | ||
1281 | stats = NULL; | ||
1282 | } | ||
1283 | if (NULL != peers) | ||
1284 | { | ||
1285 | GNUNET_CONTAINER_multipeermap_destroy (peers); | ||
1286 | peers = NULL; | ||
1287 | } | ||
1288 | if (NULL != my_private_key) | ||
1289 | { | ||
1290 | GNUNET_free (my_private_key); | ||
1291 | my_private_key = NULL; | ||
1292 | } | ||
1293 | #if ENABLE_NSE_HISTOGRAM | ||
1294 | if (NULL != logger_test) | ||
1295 | { | ||
1296 | GNUNET_CLIENT_service_test_cancel (logger_test); | ||
1297 | logger_test = NULL; | ||
1298 | } | ||
1299 | if (NULL != lh) | ||
1300 | { | ||
1301 | GNUNET_TESTBED_LOGGER_flush (lh, &flush_comp_cb, NULL); | ||
1302 | } | ||
1303 | if (NULL != histogram) | ||
1304 | { | ||
1305 | GNUNET_BIO_write_close (histogram, NULL); | ||
1306 | histogram = NULL; | ||
1307 | } | ||
1308 | #endif | ||
1309 | } | ||
1310 | |||
1311 | |||
1312 | /** | ||
1313 | * Called on core init/fail. | ||
1314 | * | ||
1315 | * @param cls service closure | ||
1316 | * @param identity the public identity of this peer | ||
1317 | */ | ||
1318 | static void | ||
1319 | core_init (void *cls, const struct GNUNET_PeerIdentity *identity) | ||
1320 | { | ||
1321 | struct GNUNET_TIME_Absolute now; | ||
1322 | struct GNUNET_TIME_Absolute prev_time; | ||
1323 | |||
1324 | (void) cls; | ||
1325 | if (NULL == identity) | ||
1326 | { | ||
1327 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Connection to core FAILED!\n"); | ||
1328 | GNUNET_SCHEDULER_shutdown (); | ||
1329 | return; | ||
1330 | } | ||
1331 | GNUNET_assert (0 == GNUNET_memcmp (&my_identity, identity)); | ||
1332 | now = GNUNET_TIME_absolute_get (); | ||
1333 | current_timestamp.abs_value_us = | ||
1334 | (now.abs_value_us / gnunet_nse_interval.rel_value_us) | ||
1335 | * gnunet_nse_interval.rel_value_us; | ||
1336 | next_timestamp = | ||
1337 | GNUNET_TIME_absolute_add (current_timestamp, gnunet_nse_interval); | ||
1338 | estimate_index = HISTORY_SIZE - 1; | ||
1339 | estimate_count = 0; | ||
1340 | if (GNUNET_YES == check_proof_of_work (&my_identity.public_key, my_proof)) | ||
1341 | { | ||
1342 | int idx = (estimate_index + HISTORY_SIZE - 1) % HISTORY_SIZE; | ||
1343 | prev_time.abs_value_us = | ||
1344 | current_timestamp.abs_value_us - gnunet_nse_interval.rel_value_us; | ||
1345 | setup_flood_message (idx, prev_time); | ||
1346 | setup_flood_message (estimate_index, current_timestamp); | ||
1347 | estimate_count++; | ||
1348 | } | ||
1349 | flood_task = | ||
1350 | GNUNET_SCHEDULER_add_at (next_timestamp, &update_flood_message, NULL); | ||
1351 | } | ||
1352 | |||
1353 | |||
1354 | #if ENABLE_NSE_HISTOGRAM | ||
1355 | /** | ||
1356 | * Function called with the status of the testbed logger service | ||
1357 | * | ||
1358 | * @param cls NULL | ||
1359 | * @param status #GNUNET_YES if the service is running, | ||
1360 | * #GNUNET_NO if the service is not running | ||
1361 | * #GNUNET_SYSERR if the configuration is invalid | ||
1362 | */ | ||
1363 | static void | ||
1364 | status_cb (void *cls, int status) | ||
1365 | { | ||
1366 | (void) cls; | ||
1367 | logger_test = NULL; | ||
1368 | if (GNUNET_YES != status) | ||
1369 | { | ||
1370 | GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "Testbed logger not running\n"); | ||
1371 | return; | ||
1372 | } | ||
1373 | if (NULL == (lh = GNUNET_TESTBED_LOGGER_connect (cfg))) | ||
1374 | { | ||
1375 | GNUNET_log (GNUNET_ERROR_TYPE_WARNING, | ||
1376 | "Cannot connect to the testbed logger. Exiting.\n"); | ||
1377 | GNUNET_SCHEDULER_shutdown (); | ||
1378 | } | ||
1379 | } | ||
1380 | |||
1381 | |||
1382 | #endif | ||
1383 | |||
1384 | |||
1385 | /** | ||
1386 | * Handle network size estimate clients. | ||
1387 | * | ||
1388 | * @param cls closure | ||
1389 | * @param c configuration to use | ||
1390 | * @param service the initialized service | ||
1391 | */ | ||
1392 | static void | ||
1393 | run (void *cls, | ||
1394 | const struct GNUNET_CONFIGURATION_Handle *c, | ||
1395 | struct GNUNET_SERVICE_Handle *service) | ||
1396 | { | ||
1397 | struct GNUNET_MQ_MessageHandler core_handlers[] = | ||
1398 | { GNUNET_MQ_hd_fixed_size (p2p_estimate, | ||
1399 | GNUNET_MESSAGE_TYPE_NSE_P2P_FLOOD, | ||
1400 | struct GNUNET_NSE_FloodMessage, | ||
1401 | NULL), | ||
1402 | GNUNET_MQ_handler_end () }; | ||
1403 | char *proof; | ||
1404 | struct GNUNET_CRYPTO_EddsaPrivateKey *pk; | ||
1405 | |||
1406 | (void) cls; | ||
1407 | (void) service; | ||
1408 | cfg = c; | ||
1409 | if (GNUNET_OK != GNUNET_CONFIGURATION_get_value_time (cfg, | ||
1410 | "NSE", | ||
1411 | "INTERVAL", | ||
1412 | &gnunet_nse_interval)) | ||
1413 | { | ||
1414 | GNUNET_log_config_missing (GNUNET_ERROR_TYPE_ERROR, "NSE", "INTERVAL"); | ||
1415 | GNUNET_SCHEDULER_shutdown (); | ||
1416 | return; | ||
1417 | } | ||
1418 | if (GNUNET_OK != GNUNET_CONFIGURATION_get_value_time (cfg, | ||
1419 | "NSE", | ||
1420 | "WORKDELAY", | ||
1421 | &proof_find_delay)) | ||
1422 | { | ||
1423 | GNUNET_log_config_missing (GNUNET_ERROR_TYPE_ERROR, "NSE", "WORKDELAY"); | ||
1424 | GNUNET_SCHEDULER_shutdown (); | ||
1425 | return; | ||
1426 | } | ||
1427 | if (GNUNET_OK != GNUNET_CONFIGURATION_get_value_number (cfg, | ||
1428 | "NSE", | ||
1429 | "WORKBITS", | ||
1430 | &nse_work_required)) | ||
1431 | { | ||
1432 | GNUNET_log_config_missing (GNUNET_ERROR_TYPE_ERROR, "NSE", "WORKBITS"); | ||
1433 | GNUNET_SCHEDULER_shutdown (); | ||
1434 | return; | ||
1435 | } | ||
1436 | if (nse_work_required >= sizeof(struct GNUNET_HashCode) * 8) | ||
1437 | { | ||
1438 | GNUNET_log_config_invalid (GNUNET_ERROR_TYPE_ERROR, | ||
1439 | "NSE", | ||
1440 | "WORKBITS", | ||
1441 | _ ("Value is too large.\n")); | ||
1442 | GNUNET_SCHEDULER_shutdown (); | ||
1443 | return; | ||
1444 | } | ||
1445 | |||
1446 | #if ENABLE_NSE_HISTOGRAM | ||
1447 | { | ||
1448 | char *histogram_dir; | ||
1449 | char *histogram_fn; | ||
1450 | |||
1451 | if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_filename (cfg, | ||
1452 | "NSE", | ||
1453 | "HISTOGRAM_DIR", | ||
1454 | &histogram_dir)) | ||
1455 | { | ||
1456 | GNUNET_assert ( | ||
1457 | 0 < GNUNET_asprintf (&histogram_fn, "%s/timestamps", histogram_dir)); | ||
1458 | GNUNET_free (histogram_dir); | ||
1459 | histogram = GNUNET_BIO_write_open_file (histogram_fn); | ||
1460 | if (NULL == histogram) | ||
1461 | GNUNET_log (GNUNET_ERROR_TYPE_WARNING, | ||
1462 | "Unable to open histogram file `%s'\n", | ||
1463 | histogram_fn); | ||
1464 | GNUNET_free (histogram_fn); | ||
1465 | } | ||
1466 | logger_test = GNUNET_CLIENT_service_test ("testbed-logger", | ||
1467 | cfg, | ||
1468 | GNUNET_TIME_UNIT_SECONDS, | ||
1469 | &status_cb, | ||
1470 | NULL); | ||
1471 | } | ||
1472 | #endif | ||
1473 | |||
1474 | GNUNET_SCHEDULER_add_shutdown (&shutdown_task, NULL); | ||
1475 | pk = GNUNET_CRYPTO_eddsa_key_create_from_configuration (cfg); | ||
1476 | GNUNET_assert (NULL != pk); | ||
1477 | my_private_key = pk; | ||
1478 | GNUNET_CRYPTO_eddsa_key_get_public (my_private_key, &my_identity.public_key); | ||
1479 | if (GNUNET_OK != | ||
1480 | GNUNET_CONFIGURATION_get_value_filename (cfg, "NSE", "PROOFFILE", &proof)) | ||
1481 | { | ||
1482 | GNUNET_log_config_missing (GNUNET_ERROR_TYPE_ERROR, "NSE", "PROOFFILE"); | ||
1483 | GNUNET_free (my_private_key); | ||
1484 | my_private_key = NULL; | ||
1485 | GNUNET_SCHEDULER_shutdown (); | ||
1486 | return; | ||
1487 | } | ||
1488 | if ((GNUNET_YES != GNUNET_DISK_file_test (proof)) || | ||
1489 | (sizeof(my_proof) != | ||
1490 | GNUNET_DISK_fn_read (proof, &my_proof, sizeof(my_proof)))) | ||
1491 | my_proof = 0; | ||
1492 | GNUNET_free (proof); | ||
1493 | proof_task = | ||
1494 | GNUNET_SCHEDULER_add_with_priority (GNUNET_SCHEDULER_PRIORITY_IDLE, | ||
1495 | &find_proof, | ||
1496 | NULL); | ||
1497 | |||
1498 | peers = GNUNET_CONTAINER_multipeermap_create (128, GNUNET_YES); | ||
1499 | nc = GNUNET_notification_context_create (1); | ||
1500 | /* Connect to core service and register core handlers */ | ||
1501 | core_api = | ||
1502 | GNUNET_CORE_connect (cfg, /* Main configuration */ | ||
1503 | NULL, /* Closure passed to functions */ | ||
1504 | &core_init, /* Call core_init once connected */ | ||
1505 | &handle_core_connect, /* Handle connects */ | ||
1506 | &handle_core_disconnect, /* Handle disconnects */ | ||
1507 | core_handlers); /* Register these handlers */ | ||
1508 | if (NULL == core_api) | ||
1509 | { | ||
1510 | GNUNET_SCHEDULER_shutdown (); | ||
1511 | return; | ||
1512 | } | ||
1513 | stats = GNUNET_STATISTICS_create ("nse", cfg); | ||
1514 | } | ||
1515 | |||
1516 | |||
1517 | /** | ||
1518 | * Callback called when a client connects to the service. | ||
1519 | * | ||
1520 | * @param cls closure for the service | ||
1521 | * @param c the new client that connected to the service | ||
1522 | * @param mq the message queue used to send messages to the client | ||
1523 | * @return @a c | ||
1524 | */ | ||
1525 | static void * | ||
1526 | client_connect_cb (void *cls, | ||
1527 | struct GNUNET_SERVICE_Client *c, | ||
1528 | struct GNUNET_MQ_Handle *mq) | ||
1529 | { | ||
1530 | (void) cls; | ||
1531 | (void) mq; | ||
1532 | return c; | ||
1533 | } | ||
1534 | |||
1535 | |||
1536 | /** | ||
1537 | * Callback called when a client disconnected from the service | ||
1538 | * | ||
1539 | * @param cls closure for the service | ||
1540 | * @param c the client that disconnected | ||
1541 | * @param internal_cls should be equal to @a c | ||
1542 | */ | ||
1543 | static void | ||
1544 | client_disconnect_cb (void *cls, | ||
1545 | struct GNUNET_SERVICE_Client *c, | ||
1546 | void *internal_cls) | ||
1547 | { | ||
1548 | (void) cls; | ||
1549 | GNUNET_assert (c == internal_cls); | ||
1550 | } | ||
1551 | |||
1552 | |||
1553 | /** | ||
1554 | * Define "main" method using service macro. | ||
1555 | */ | ||
1556 | GNUNET_SERVICE_MAIN ("nse", | ||
1557 | GNUNET_SERVICE_OPTION_NONE, | ||
1558 | &run, | ||
1559 | &client_connect_cb, | ||
1560 | &client_disconnect_cb, | ||
1561 | NULL, | ||
1562 | GNUNET_MQ_hd_fixed_size (start, | ||
1563 | GNUNET_MESSAGE_TYPE_NSE_START, | ||
1564 | struct GNUNET_MessageHeader, | ||
1565 | NULL), | ||
1566 | GNUNET_MQ_handler_end ()); | ||
1567 | |||
1568 | |||
1569 | #if defined(__linux__) && defined(__GLIBC__) | ||
1570 | #include <malloc.h> | ||
1571 | |||
1572 | /** | ||
1573 | * MINIMIZE heap size (way below 128k) since this process doesn't need much. | ||
1574 | */ | ||
1575 | void __attribute__ ((constructor)) | ||
1576 | GNUNET_ARM_memory_init () | ||
1577 | { | ||
1578 | mallopt (M_TRIM_THRESHOLD, 4 * 1024); | ||
1579 | mallopt (M_TOP_PAD, 1 * 1024); | ||
1580 | malloc_trim (0); | ||
1581 | } | ||
1582 | |||
1583 | |||
1584 | #endif | ||
1585 | |||
1586 | |||
1587 | /* end of gnunet-service-nse.c */ | ||