diff options
Diffstat (limited to 'src/cadet/gnunet-service-cadet_paths.c')
-rw-r--r-- | src/cadet/gnunet-service-cadet_paths.c | 785 |
1 files changed, 0 insertions, 785 deletions
diff --git a/src/cadet/gnunet-service-cadet_paths.c b/src/cadet/gnunet-service-cadet_paths.c deleted file mode 100644 index aa31aaa74..000000000 --- a/src/cadet/gnunet-service-cadet_paths.c +++ /dev/null | |||
@@ -1,785 +0,0 @@ | |||
1 | /* | ||
2 | This file is part of GNUnet. | ||
3 | Copyright (C) 2001-2017 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 | * @file cadet/gnunet-service-cadet_paths.c | ||
22 | * @brief Information we track per path. | ||
23 | * @author Bartlomiej Polot | ||
24 | * @author Christian Grothoff | ||
25 | */ | ||
26 | #include "platform.h" | ||
27 | #include "gnunet-service-cadet_connection.h" | ||
28 | #include "gnunet-service-cadet_tunnels.h" | ||
29 | #include "gnunet-service-cadet_peer.h" | ||
30 | #include "gnunet-service-cadet_paths.h" | ||
31 | |||
32 | |||
33 | #define LOG(level, ...) GNUNET_log_from (level, "cadet-pat", __VA_ARGS__) | ||
34 | |||
35 | |||
36 | /** | ||
37 | * Information regarding a possible path to reach a peer. | ||
38 | */ | ||
39 | struct CadetPeerPath | ||
40 | { | ||
41 | /** | ||
42 | * Array of all the peers on the path. If @e hn is non-NULL, the | ||
43 | * last one is our owner. | ||
44 | */ | ||
45 | struct CadetPeerPathEntry **entries; | ||
46 | |||
47 | /** | ||
48 | * Node of this path in the owner's heap. Used to update our position | ||
49 | * in the heap whenever our @e desirability changes. | ||
50 | */ | ||
51 | struct GNUNET_CONTAINER_HeapNode *hn; | ||
52 | |||
53 | /** | ||
54 | * Desirability of the path. How unique is it for the various peers | ||
55 | * on it? | ||
56 | */ | ||
57 | GNUNET_CONTAINER_HeapCostType desirability; | ||
58 | |||
59 | /** | ||
60 | * Length of the @e entries array. | ||
61 | */ | ||
62 | unsigned int entries_length; | ||
63 | }; | ||
64 | |||
65 | |||
66 | /** | ||
67 | * Calculate the path's desirability score. | ||
68 | * | ||
69 | * @param path path to calculate the score for | ||
70 | */ | ||
71 | static void | ||
72 | recalculate_path_desirability (struct CadetPeerPath *path) | ||
73 | { | ||
74 | double result = 0.0; | ||
75 | |||
76 | for (unsigned int i = 0; i < path->entries_length; i++) | ||
77 | { | ||
78 | struct CadetPeer *cp = path->entries[i]->peer; | ||
79 | |||
80 | result += GCP_get_desirability_of_path (cp, | ||
81 | i); | ||
82 | } | ||
83 | path->desirability = (GNUNET_CONTAINER_HeapCostType) result; | ||
84 | } | ||
85 | |||
86 | |||
87 | /** | ||
88 | * Return how much we like keeping the path. This is an aggregate | ||
89 | * score based on various factors, including the age of the path | ||
90 | * (older == better), and the value of this path to all of its adjacent | ||
91 | * peers. For example, long paths that end at a peer that we have no | ||
92 | * shorter way to reach are very desirable, while long paths that end | ||
93 | * at a peer for which we have a shorter way as well are much less | ||
94 | * desirable. Higher values indicate more valuable paths. The | ||
95 | * returned value should be used to decide which paths to remember. | ||
96 | * | ||
97 | * @param path path to return the length for | ||
98 | * @return desirability of the path, larger is more desirable | ||
99 | */ | ||
100 | GNUNET_CONTAINER_HeapCostType | ||
101 | GCPP_get_desirability (const struct CadetPeerPath *path) | ||
102 | { | ||
103 | return path->desirability; | ||
104 | } | ||
105 | |||
106 | |||
107 | /** | ||
108 | * Return connection to @a destination using @a path, or return | ||
109 | * NULL if no such connection exists. | ||
110 | * | ||
111 | * @param path path to traverse | ||
112 | * @param destination destination node to get to, must be on path | ||
113 | * @param off offset of @a destination on @a path | ||
114 | * @return NULL if we have no existing connection | ||
115 | * otherwise connection from us to @a destination via @a path | ||
116 | */ | ||
117 | struct CadetConnection * | ||
118 | GCPP_get_connection (struct CadetPeerPath *path, | ||
119 | struct CadetPeer *destination, | ||
120 | unsigned int off) | ||
121 | { | ||
122 | struct CadetPeerPathEntry *entry; | ||
123 | |||
124 | GNUNET_assert (off < path->entries_length); | ||
125 | entry = path->entries[off]; | ||
126 | GNUNET_assert (entry->peer == destination); | ||
127 | return entry->cc; | ||
128 | } | ||
129 | |||
130 | |||
131 | /** | ||
132 | * Notify @a path that it is used for connection @a cc | ||
133 | * which ends at the path's offset @a off. | ||
134 | * | ||
135 | * @param path the path to remember the @a cc | ||
136 | * @param off the offset where the @a cc ends | ||
137 | * @param cc the connection to remember | ||
138 | */ | ||
139 | void | ||
140 | GCPP_add_connection (struct CadetPeerPath *path, | ||
141 | unsigned int off, | ||
142 | struct CadetConnection *cc) | ||
143 | { | ||
144 | struct CadetPeerPathEntry *entry; | ||
145 | |||
146 | LOG (GNUNET_ERROR_TYPE_DEBUG, | ||
147 | "Adding %s to path %s at offset %u\n", | ||
148 | GCC_2s (cc), | ||
149 | GCPP_2s (path), | ||
150 | off); | ||
151 | GNUNET_assert (off < path->entries_length); | ||
152 | entry = path->entries[off]; | ||
153 | GNUNET_assert (NULL == entry->cc); | ||
154 | GNUNET_assert (NULL != cc); | ||
155 | entry->cc = cc; | ||
156 | } | ||
157 | |||
158 | |||
159 | /** | ||
160 | * Notify @a path that it is no longer used for connection @a cc which | ||
161 | * ended at the path's offset @a off. | ||
162 | * | ||
163 | * @param path the path to forget the @a cc | ||
164 | * @param off the offset where the @a cc ended | ||
165 | * @param cc the connection to forget | ||
166 | */ | ||
167 | void | ||
168 | GCPP_del_connection (struct CadetPeerPath *path, | ||
169 | unsigned int off, | ||
170 | struct CadetConnection *cc) | ||
171 | { | ||
172 | struct CadetPeerPathEntry *entry; | ||
173 | |||
174 | LOG (GNUNET_ERROR_TYPE_DEBUG, | ||
175 | "Removing connection %s to path %s at offset %u\n", | ||
176 | GCC_2s (cc), | ||
177 | GCPP_2s (path), | ||
178 | off); | ||
179 | GNUNET_assert (off < path->entries_length); | ||
180 | entry = path->entries[off]; | ||
181 | GNUNET_assert (cc == entry->cc); | ||
182 | entry->cc = NULL; | ||
183 | } | ||
184 | |||
185 | |||
186 | /** | ||
187 | * Tries to attach @a path to a peer, working backwards from the end | ||
188 | * and stopping at @a stop_at. If path->hn is NULL on return then the | ||
189 | * path was not attached and you can assume that path->entries_length | ||
190 | * is equal to @a stop_at. | ||
191 | * | ||
192 | * @param path the path to attach | ||
193 | * @param stop_at the path length at which to stop trying | ||
194 | */ | ||
195 | static void | ||
196 | attach_path (struct CadetPeerPath *path, unsigned int stop_at) | ||
197 | { | ||
198 | GNUNET_assert (NULL == path->hn); | ||
199 | |||
200 | /* Try to attach this path to a peer, working backwards from the end. */ | ||
201 | while (path->entries_length > stop_at) | ||
202 | { | ||
203 | unsigned int end = path->entries_length - 1; | ||
204 | struct CadetPeerPathEntry *entry = path->entries[end]; | ||
205 | int force = GNUNET_NO; | ||
206 | |||
207 | recalculate_path_desirability (path); | ||
208 | /* If the entry already has a connection using it, force attach. */ | ||
209 | if (NULL != entry->cc) | ||
210 | force = GNUNET_YES; | ||
211 | path->hn = GCP_attach_path (entry->peer, | ||
212 | path, | ||
213 | end, | ||
214 | force); | ||
215 | if (NULL != path->hn) | ||
216 | break; | ||
217 | |||
218 | /* Attach failed, trim this entry from the path. */ | ||
219 | GNUNET_assert (NULL == entry->cc); | ||
220 | GCP_path_entry_remove (entry->peer, | ||
221 | entry, | ||
222 | end); | ||
223 | GNUNET_free (entry); | ||
224 | path->entries[end] = NULL; | ||
225 | path->entries_length--; | ||
226 | } | ||
227 | |||
228 | /* Shrink array to actual path length. */ | ||
229 | GNUNET_array_grow (path->entries, | ||
230 | path->entries_length, | ||
231 | path->entries_length); | ||
232 | } | ||
233 | |||
234 | |||
235 | /** | ||
236 | * The owning peer of this path is no longer interested in maintaining | ||
237 | * it, so the path should be discarded or shortened (in case a | ||
238 | * previous peer on the path finds the path desirable). | ||
239 | * | ||
240 | * @param path the path that is being released | ||
241 | */ | ||
242 | void | ||
243 | GCPP_release (struct CadetPeerPath *path) | ||
244 | { | ||
245 | struct CadetPeerPathEntry *entry; | ||
246 | |||
247 | LOG (GNUNET_ERROR_TYPE_DEBUG, | ||
248 | "Owner releases path %s\n", | ||
249 | GCPP_2s (path)); | ||
250 | path->hn = NULL; | ||
251 | entry = path->entries[path->entries_length - 1]; | ||
252 | GNUNET_assert (path == entry->path); | ||
253 | GNUNET_assert (NULL == entry->cc); | ||
254 | /* cut 'off' end of path */ | ||
255 | GCP_path_entry_remove (entry->peer, | ||
256 | entry, | ||
257 | path->entries_length - 1); | ||
258 | GNUNET_free (entry); | ||
259 | path->entries[path->entries_length - 1] = NULL; | ||
260 | path->entries_length--; | ||
261 | /* see if new peer at the end likes this path any better */ | ||
262 | attach_path (path, 0); | ||
263 | if (NULL == path->hn) | ||
264 | { | ||
265 | /* nobody wants us, discard the path */ | ||
266 | GNUNET_assert (0 == path->entries_length); | ||
267 | GNUNET_assert (NULL == path->entries); | ||
268 | GNUNET_free (path); | ||
269 | } | ||
270 | } | ||
271 | |||
272 | |||
273 | /** | ||
274 | * Updates the score for an entry on the path based | ||
275 | * on our experiences with using @a path. | ||
276 | * | ||
277 | * @param path the path to update | ||
278 | * @param off offset of the entry to update | ||
279 | * @param delta change in the score to apply | ||
280 | */ | ||
281 | void | ||
282 | GCPP_update_score (struct CadetPeerPath *path, | ||
283 | unsigned int off, | ||
284 | int delta) | ||
285 | { | ||
286 | struct CadetPeerPathEntry *entry; | ||
287 | |||
288 | GNUNET_assert (off < path->entries_length); | ||
289 | entry = path->entries[off]; | ||
290 | |||
291 | /* Add delta, with checks for overflows */ | ||
292 | if (delta >= 0) | ||
293 | { | ||
294 | if (delta + entry->score < entry->score) | ||
295 | entry->score = INT_MAX; | ||
296 | else | ||
297 | entry->score += delta; | ||
298 | } | ||
299 | else | ||
300 | { | ||
301 | if (delta + entry->score > entry->score) | ||
302 | entry->score = INT_MIN; | ||
303 | else | ||
304 | entry->score += delta; | ||
305 | } | ||
306 | recalculate_path_desirability (path); | ||
307 | } | ||
308 | |||
309 | |||
310 | /** | ||
311 | * Closure for #find_peer_at() and #check_match(). | ||
312 | */ | ||
313 | struct CheckMatchContext | ||
314 | { | ||
315 | /** | ||
316 | * Set to a matching path, if any. | ||
317 | */ | ||
318 | struct CadetPeerPath *match; | ||
319 | |||
320 | /** | ||
321 | * Array the combined paths. | ||
322 | */ | ||
323 | struct CadetPeer **cpath; | ||
324 | |||
325 | /** | ||
326 | * How long is the @e cpath array? | ||
327 | */ | ||
328 | unsigned int cpath_length; | ||
329 | }; | ||
330 | |||
331 | |||
332 | /** | ||
333 | * Check if the given path is identical on all of the | ||
334 | * hops until @a off, and not longer than @a off. If the | ||
335 | * @a path matches, store it in `match`. | ||
336 | * | ||
337 | * @param cls the `struct CheckMatchContext` to check against | ||
338 | * @param path the path to check | ||
339 | * @param off offset to check at | ||
340 | * @return #GNUNET_YES (continue to iterate), or if found #GNUNET_NO | ||
341 | */ | ||
342 | static int | ||
343 | check_match (void *cls, | ||
344 | struct CadetPeerPath *path, | ||
345 | unsigned int off) | ||
346 | { | ||
347 | struct CheckMatchContext *cm_ctx = cls; | ||
348 | |||
349 | GNUNET_assert (path->entries_length > off); | ||
350 | if ((path->entries_length != off + 1) && | ||
351 | (off + 1 != cm_ctx->cpath_length)) | ||
352 | { | ||
353 | LOG (GNUNET_ERROR_TYPE_DEBUG, | ||
354 | "check_match mismatch because path %s is too long (%u vs. %u vs. %u)\n", | ||
355 | GCPP_2s (path), | ||
356 | path->entries_length, | ||
357 | off + 1, | ||
358 | cm_ctx->cpath_length); | ||
359 | return GNUNET_YES; /* too long, goes somewhere else already, thus cannot be useful */ | ||
360 | } | ||
361 | for (unsigned int i = 0; i < off; i++) | ||
362 | if (cm_ctx->cpath[i] != | ||
363 | GCPP_get_peer_at_offset (path, | ||
364 | i)) | ||
365 | { | ||
366 | LOG (GNUNET_ERROR_TYPE_DEBUG, | ||
367 | "check_match path %s mismatches at offset %u\n", | ||
368 | GCPP_2s (path), | ||
369 | i); | ||
370 | return GNUNET_YES; /* mismatch, ignore */ | ||
371 | } | ||
372 | LOG (GNUNET_ERROR_TYPE_DEBUG, | ||
373 | "check_match found match with path %s\n", | ||
374 | GCPP_2s (path)); | ||
375 | cm_ctx->match = path; | ||
376 | return GNUNET_NO; /* match, we are done! */ | ||
377 | } | ||
378 | |||
379 | |||
380 | /** | ||
381 | * Extend path @a path by the @a num_peers from the @a peers | ||
382 | * array, assuming the owners past the current owner want it. | ||
383 | * | ||
384 | * @param path path to extend | ||
385 | * @param peers list of peers beyond the end of @a path | ||
386 | * @param num_peers length of the @a peers array | ||
387 | * @param force force attachment, even if we have other | ||
388 | * paths already | ||
389 | */ | ||
390 | static void | ||
391 | extend_path (struct CadetPeerPath *path, | ||
392 | struct CadetPeer **peers, | ||
393 | unsigned int num_peers, | ||
394 | int force) | ||
395 | { | ||
396 | unsigned int old_len = path->entries_length; | ||
397 | int i; | ||
398 | |||
399 | /* Expand path */ | ||
400 | GNUNET_array_grow (path->entries, | ||
401 | path->entries_length, | ||
402 | old_len + num_peers); | ||
403 | for (i = num_peers - 1; i >= 0; i--) | ||
404 | { | ||
405 | struct CadetPeerPathEntry *entry = GNUNET_new (struct CadetPeerPathEntry); | ||
406 | |||
407 | path->entries[old_len + i] = entry; | ||
408 | entry->peer = peers[i]; | ||
409 | entry->path = path; | ||
410 | } | ||
411 | for (i = num_peers - 1; i >= 0; i--) | ||
412 | { | ||
413 | struct CadetPeerPathEntry *entry = path->entries[old_len + i]; | ||
414 | |||
415 | GCP_path_entry_add (entry->peer, | ||
416 | entry, | ||
417 | old_len + i); | ||
418 | } | ||
419 | |||
420 | /* If we extend an existing path, detach it from the | ||
421 | old owner and re-attach to the new one */ | ||
422 | GCP_detach_path (path->entries[old_len - 1]->peer, | ||
423 | path, | ||
424 | path->hn); | ||
425 | path->hn = NULL; | ||
426 | path->entries_length = old_len + num_peers; | ||
427 | if (GNUNET_YES == force) | ||
428 | { | ||
429 | int end = path->entries_length - 1; | ||
430 | |||
431 | path->hn = GCP_attach_path (path->entries[end]->peer, | ||
432 | path, | ||
433 | end, | ||
434 | GNUNET_YES); | ||
435 | } | ||
436 | else | ||
437 | { | ||
438 | attach_path (path, old_len); | ||
439 | } | ||
440 | if (NULL == path->hn) | ||
441 | { | ||
442 | /* none of the peers is interested in this path; | ||
443 | re-attach. */ | ||
444 | GNUNET_assert (old_len == path->entries_length); | ||
445 | path->hn = GCP_attach_path (path->entries[old_len - 1]->peer, | ||
446 | path, | ||
447 | old_len - 1, | ||
448 | GNUNET_YES); | ||
449 | GNUNET_assert (NULL != path->hn); | ||
450 | return; | ||
451 | } | ||
452 | LOG (GNUNET_ERROR_TYPE_DEBUG, | ||
453 | "Extended path %s\n", | ||
454 | GCPP_2s (path)); | ||
455 | } | ||
456 | |||
457 | |||
458 | /** | ||
459 | * Create a peer path based on the result of a DHT lookup. If we | ||
460 | * already know this path, or one that is longer, simply return NULL. | ||
461 | * Otherwise, we try to extend an existing path, or create a new one | ||
462 | * if applicable. | ||
463 | * | ||
464 | * @param get_path path of the get request | ||
465 | * @param get_path_length length of @a get_path | ||
466 | * @param put_path path of the put request | ||
467 | * @param put_path_length length of the @a put_path | ||
468 | * @return a path through the network | ||
469 | */ | ||
470 | void | ||
471 | GCPP_try_path_from_dht (const struct GNUNET_DHT_PathElement *get_path, | ||
472 | unsigned int get_path_length, | ||
473 | const struct GNUNET_DHT_PathElement *put_path, | ||
474 | unsigned int put_path_length) | ||
475 | { | ||
476 | struct CadetPeer *cpath[get_path_length + put_path_length]; | ||
477 | struct CheckMatchContext cm_ctx; | ||
478 | struct CadetPeerPath *path; | ||
479 | unsigned int skip; | ||
480 | unsigned int total_len; | ||
481 | |||
482 | /* precompute 'cpath' so we can avoid doing the lookups lots of times */ | ||
483 | skip = 0; | ||
484 | memset (cpath, | ||
485 | 0, | ||
486 | sizeof(cpath)); /* Just to trigger harder errors later. */ | ||
487 | total_len = get_path_length + put_path_length; | ||
488 | for (unsigned int off = 0; off < total_len; off++) | ||
489 | { | ||
490 | const struct GNUNET_PeerIdentity *pid; | ||
491 | |||
492 | pid = (off < get_path_length) | ||
493 | ? &get_path[get_path_length - off - 1].pred | ||
494 | : &put_path[get_path_length + put_path_length - off - 1].pred; | ||
495 | /* Check that I am not in the path */ | ||
496 | if (0 == GNUNET_memcmp (&my_full_id, | ||
497 | pid)) | ||
498 | { | ||
499 | skip = off + 1; | ||
500 | continue; | ||
501 | } | ||
502 | cpath[off - skip] = GCP_get (pid, | ||
503 | GNUNET_YES); | ||
504 | /* Check that no peer is twice on the path */ | ||
505 | for (unsigned int i = 0; i < off - skip; i++) | ||
506 | { | ||
507 | if (cpath[i] == cpath[off - skip]) | ||
508 | { | ||
509 | skip = off - i; | ||
510 | break; | ||
511 | } | ||
512 | } | ||
513 | } | ||
514 | if (skip >= total_len) | ||
515 | { | ||
516 | LOG (GNUNET_ERROR_TYPE_DEBUG, | ||
517 | "Path discovered from DHT is one big cycle?\n"); | ||
518 | return; | ||
519 | } | ||
520 | total_len -= skip; | ||
521 | |||
522 | /* First figure out if this path is a subset of an existing path, an | ||
523 | extension of an existing path, or a new path. */ | ||
524 | cm_ctx.cpath_length = total_len; | ||
525 | cm_ctx.cpath = cpath; | ||
526 | cm_ctx.match = NULL; | ||
527 | for (int i = total_len - 1; i >= 0; i--) | ||
528 | { | ||
529 | GCP_iterate_paths_at (cpath[i], | ||
530 | (unsigned int) i, | ||
531 | &check_match, | ||
532 | &cm_ctx); | ||
533 | if (NULL != cm_ctx.match) | ||
534 | { | ||
535 | if (i == total_len - 1) | ||
536 | { | ||
537 | /* Existing path includes this one, nothing to do! */ | ||
538 | LOG (GNUNET_ERROR_TYPE_DEBUG, | ||
539 | "Path discovered from DHT is already known\n"); | ||
540 | return; | ||
541 | } | ||
542 | if (cm_ctx.match->entries_length == i + 1) | ||
543 | { | ||
544 | /* Existing path ends in the middle of new path, extend it! */ | ||
545 | LOG (GNUNET_ERROR_TYPE_DEBUG, | ||
546 | "Trying to extend existing path %s by additional links discovered from DHT\n", | ||
547 | GCPP_2s (cm_ctx.match)); | ||
548 | extend_path (cm_ctx.match, | ||
549 | &cpath[i + 1], | ||
550 | total_len - i - 1, | ||
551 | GNUNET_NO); | ||
552 | return; | ||
553 | } | ||
554 | } | ||
555 | } | ||
556 | |||
557 | /* No match at all, create completely new path */ | ||
558 | path = GNUNET_new (struct CadetPeerPath); | ||
559 | path->entries_length = total_len; | ||
560 | path->entries = GNUNET_new_array (path->entries_length, | ||
561 | struct CadetPeerPathEntry *); | ||
562 | for (int i = path->entries_length - 1; i >= 0; i--) | ||
563 | { | ||
564 | struct CadetPeerPathEntry *entry = GNUNET_new (struct CadetPeerPathEntry); | ||
565 | |||
566 | path->entries[i] = entry; | ||
567 | entry->peer = cpath[i]; | ||
568 | entry->path = path; | ||
569 | } | ||
570 | for (int i = path->entries_length - 1; i >= 0; i--) | ||
571 | { | ||
572 | struct CadetPeerPathEntry *entry = path->entries[i]; | ||
573 | |||
574 | GCP_path_entry_add (entry->peer, | ||
575 | entry, | ||
576 | i); | ||
577 | } | ||
578 | |||
579 | /* Finally, try to attach it */ | ||
580 | attach_path (path, 0); | ||
581 | if (NULL == path->hn) | ||
582 | { | ||
583 | /* None of the peers on the path care about it. */ | ||
584 | LOG (GNUNET_ERROR_TYPE_DEBUG, | ||
585 | "Path discovered from DHT is not interesting to us\n"); | ||
586 | GNUNET_assert (0 == path->entries_length); | ||
587 | GNUNET_assert (NULL == path->entries); | ||
588 | GNUNET_free (path); | ||
589 | return; | ||
590 | } | ||
591 | LOG (GNUNET_ERROR_TYPE_DEBUG, | ||
592 | "Created new path %s based on information from DHT\n", | ||
593 | GCPP_2s (path)); | ||
594 | } | ||
595 | |||
596 | |||
597 | /** | ||
598 | * We got an incoming connection, obtain the corresponding path. | ||
599 | * | ||
600 | * @param path_length number of segments on the @a path | ||
601 | * @param pids path through the network, in reverse order (we are at the end at index @a path_length) | ||
602 | * @return corresponding path object | ||
603 | */ | ||
604 | struct CadetPeerPath * | ||
605 | GCPP_get_path_from_route (unsigned int path_length, | ||
606 | const struct GNUNET_PeerIdentity *pids) | ||
607 | { | ||
608 | struct CheckMatchContext cm_ctx; | ||
609 | struct CadetPeer *cpath[path_length]; | ||
610 | struct CadetPeerPath *path; | ||
611 | |||
612 | /* precompute inverted 'cpath' so we can avoid doing the lookups and | ||
613 | have the correct order */ | ||
614 | for (unsigned int off = 0; off < path_length; off++) | ||
615 | cpath[off] = GCP_get (&pids[path_length - 1 - off], | ||
616 | GNUNET_YES); | ||
617 | |||
618 | /* First figure out if this path is a subset of an existing path, an | ||
619 | extension of an existing path, or a new path. */ | ||
620 | cm_ctx.cpath = cpath; | ||
621 | cm_ctx.cpath_length = path_length; | ||
622 | cm_ctx.match = NULL; | ||
623 | for (int i = path_length - 1; i >= 0; i--) | ||
624 | { | ||
625 | GCP_iterate_paths_at (cpath[i], | ||
626 | (unsigned int) i, | ||
627 | &check_match, | ||
628 | &cm_ctx); | ||
629 | if (NULL != cm_ctx.match) | ||
630 | { | ||
631 | if (i == path_length - 1) | ||
632 | { | ||
633 | /* Existing path includes this one, return the match! */ | ||
634 | LOG (GNUNET_ERROR_TYPE_DEBUG, | ||
635 | "Returning existing path %s as inverse for incoming connection\n", | ||
636 | GCPP_2s (cm_ctx.match)); | ||
637 | return cm_ctx.match; | ||
638 | } | ||
639 | if (cm_ctx.match->entries_length == i + 1) | ||
640 | { | ||
641 | /* Existing path ends in the middle of new path, extend it! */ | ||
642 | LOG (GNUNET_ERROR_TYPE_DEBUG, | ||
643 | "Extending existing path %s to create inverse for incoming connection\n", | ||
644 | GCPP_2s (cm_ctx.match)); | ||
645 | extend_path (cm_ctx.match, | ||
646 | &cpath[i + 1], | ||
647 | path_length - i - 1, | ||
648 | GNUNET_YES); | ||
649 | /* Check that extension was successful */ | ||
650 | GNUNET_assert (cm_ctx.match->entries_length == path_length); | ||
651 | return cm_ctx.match; | ||
652 | } | ||
653 | /* Eh, we found a match but couldn't use it? Something is wrong. */ | ||
654 | GNUNET_break (0); | ||
655 | } | ||
656 | } | ||
657 | |||
658 | /* No match at all, create completely new path */ | ||
659 | path = GNUNET_new (struct CadetPeerPath); | ||
660 | path->entries_length = path_length; | ||
661 | path->entries = GNUNET_new_array (path->entries_length, | ||
662 | struct CadetPeerPathEntry *); | ||
663 | for (int i = path_length - 1; i >= 0; i--) | ||
664 | { | ||
665 | struct CadetPeerPathEntry *entry = GNUNET_new (struct CadetPeerPathEntry); | ||
666 | |||
667 | path->entries[i] = entry; | ||
668 | entry->peer = cpath[i]; | ||
669 | entry->path = path; | ||
670 | } | ||
671 | for (int i = path_length - 1; i >= 0; i--) | ||
672 | { | ||
673 | struct CadetPeerPathEntry *entry = path->entries[i]; | ||
674 | |||
675 | GCP_path_entry_add (entry->peer, | ||
676 | entry, | ||
677 | i); | ||
678 | } | ||
679 | recalculate_path_desirability (path); | ||
680 | LOG (GNUNET_ERROR_TYPE_DEBUG, | ||
681 | "Created new path %s to create inverse for incoming connection\n", | ||
682 | GCPP_2s (path)); | ||
683 | path->hn = GCP_attach_path (cpath[path_length - 1], | ||
684 | path, | ||
685 | path_length - 1, | ||
686 | GNUNET_YES); | ||
687 | return path; | ||
688 | } | ||
689 | |||
690 | |||
691 | /** | ||
692 | * Return the length of the path. Excludes one end of the | ||
693 | * path, so the loopback path has length 0. | ||
694 | * | ||
695 | * @param path path to return the length for | ||
696 | * @return number of peers on the path | ||
697 | */ | ||
698 | unsigned int | ||
699 | GCPP_get_length (struct CadetPeerPath *path) | ||
700 | { | ||
701 | return path->entries_length; | ||
702 | } | ||
703 | |||
704 | |||
705 | /** | ||
706 | * Find peer's offset on path. | ||
707 | * | ||
708 | * @param path path to search | ||
709 | * @param cp peer to look for | ||
710 | * @return offset of @a cp on @a path, or UINT_MAX if not found | ||
711 | */ | ||
712 | unsigned int | ||
713 | GCPP_find_peer (struct CadetPeerPath *path, | ||
714 | struct CadetPeer *cp) | ||
715 | { | ||
716 | for (unsigned int off = 0; | ||
717 | off < path->entries_length; | ||
718 | off++) | ||
719 | if (cp == GCPP_get_peer_at_offset (path, | ||
720 | off)) | ||
721 | return off; | ||
722 | return UINT_MAX; | ||
723 | } | ||
724 | |||
725 | |||
726 | /** | ||
727 | * Obtain the peer at offset @a off in @a path. | ||
728 | * | ||
729 | * @param path peer path to inspect | ||
730 | * @param off offset to return, must be smaller than path length | ||
731 | * @return the peer at offset @a off | ||
732 | */ | ||
733 | struct CadetPeer * | ||
734 | GCPP_get_peer_at_offset (struct CadetPeerPath *path, | ||
735 | unsigned int off) | ||
736 | { | ||
737 | GNUNET_assert (off < path->entries_length); | ||
738 | return path->entries[off]->peer; | ||
739 | } | ||
740 | |||
741 | |||
742 | /** | ||
743 | * Convert a path to a human-readable string. | ||
744 | * | ||
745 | * @param path path to convert | ||
746 | * @return string, to be freed by caller (unlike other *_2s APIs!) | ||
747 | */ | ||
748 | const char * | ||
749 | GCPP_2s (struct CadetPeerPath *path) | ||
750 | { | ||
751 | static char buf[2048]; | ||
752 | size_t off; | ||
753 | const unsigned int max_plen = (sizeof(buf) - 16) / 5 - 2; /* 5 characters per entry */ | ||
754 | |||
755 | off = 0; | ||
756 | for (unsigned int i = 0; | ||
757 | i < path->entries_length; | ||
758 | i++) | ||
759 | { | ||
760 | if ((path->entries_length > max_plen) && | ||
761 | (i == max_plen / 2)) | ||
762 | off += GNUNET_snprintf (&buf[off], | ||
763 | sizeof(buf) - off, | ||
764 | "...-"); | ||
765 | if ((path->entries_length > max_plen) && | ||
766 | (i > max_plen / 2) && | ||
767 | (i < path->entries_length - max_plen / 2)) | ||
768 | continue; | ||
769 | off += GNUNET_snprintf (&buf[off], | ||
770 | sizeof(buf) - off, | ||
771 | "%s%s", | ||
772 | GNUNET_i2s (GCP_get_id (GCPP_get_peer_at_offset ( | ||
773 | path, | ||
774 | i))), | ||
775 | (i == path->entries_length - 1) ? "" : "-"); | ||
776 | } | ||
777 | GNUNET_snprintf (&buf[off], | ||
778 | sizeof(buf) - off, | ||
779 | "(%p)", | ||
780 | path); | ||
781 | return buf; | ||
782 | } | ||
783 | |||
784 | |||
785 | /* end of gnunet-service-cadet-new_paths.c */ | ||