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