diff options
-rw-r--r-- | src/cadet/cadet_tunnel_tree.c | 1174 | ||||
-rw-r--r-- | src/cadet/cadet_tunnel_tree.h | 382 |
2 files changed, 0 insertions, 1556 deletions
diff --git a/src/cadet/cadet_tunnel_tree.c b/src/cadet/cadet_tunnel_tree.c deleted file mode 100644 index 81a38e4e8..000000000 --- a/src/cadet/cadet_tunnel_tree.c +++ /dev/null | |||
@@ -1,1174 +0,0 @@ | |||
1 | /* | ||
2 | This file is part of GNUnet. | ||
3 | Copyright (C) 2001 - 2011 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 | /** | ||
22 | * @file cadet/cadet_tunnel_tree.c | ||
23 | * @brief Tunnel tree handling functions | ||
24 | * @author Bartlomiej Polot | ||
25 | */ | ||
26 | |||
27 | #include "cadet.h" | ||
28 | #include "cadet_tunnel_tree.h" | ||
29 | |||
30 | #define CADET_TREE_DEBUG GNUNET_YES | ||
31 | |||
32 | |||
33 | /** | ||
34 | * Node of path tree for a tunnel | ||
35 | */ | ||
36 | struct CadetTunnelTreeNode | ||
37 | { | ||
38 | /** | ||
39 | * Peer this node describes | ||
40 | */ | ||
41 | GNUNET_PEER_Id peer; | ||
42 | |||
43 | /** | ||
44 | * Parent node in the tree | ||
45 | */ | ||
46 | struct CadetTunnelTreeNode *parent; | ||
47 | |||
48 | /** | ||
49 | * DLL of siblings | ||
50 | */ | ||
51 | struct CadetTunnelTreeNode *next; | ||
52 | |||
53 | /** | ||
54 | * DLL of siblings | ||
55 | */ | ||
56 | struct CadetTunnelTreeNode *prev; | ||
57 | |||
58 | /** | ||
59 | * DLL of children | ||
60 | */ | ||
61 | struct CadetTunnelTreeNode *children_head; | ||
62 | |||
63 | /** | ||
64 | * DLL of children | ||
65 | */ | ||
66 | struct CadetTunnelTreeNode *children_tail; | ||
67 | |||
68 | /** | ||
69 | * Status of the peer in the tunnel | ||
70 | */ | ||
71 | enum CadetPeerState status; | ||
72 | }; | ||
73 | |||
74 | |||
75 | /** | ||
76 | * Tree to reach all peers in the tunnel | ||
77 | */ | ||
78 | struct CadetTunnelTree | ||
79 | { | ||
80 | /** | ||
81 | * Root node of peer tree | ||
82 | */ | ||
83 | struct CadetTunnelTreeNode *root; | ||
84 | |||
85 | /** | ||
86 | * Node that represents our position in the tree (for non local tunnels) | ||
87 | */ | ||
88 | struct CadetTunnelTreeNode *me; | ||
89 | |||
90 | /** | ||
91 | * DLL of disconneted nodes | ||
92 | */ | ||
93 | struct CadetTunnelTreeNode *disconnected_head; | ||
94 | |||
95 | /** | ||
96 | * DLL of disconneted nodes | ||
97 | */ | ||
98 | struct CadetTunnelTreeNode *disconnected_tail; | ||
99 | |||
100 | /** | ||
101 | * Cache of all peers and the first hop to them. | ||
102 | * Indexed by PeerIdentity, contains a pointer to the PeerIdentity | ||
103 | * of 1st hop. | ||
104 | */ | ||
105 | struct GNUNET_CONTAINER_MultiHashMap *first_hops; | ||
106 | |||
107 | }; | ||
108 | |||
109 | |||
110 | /** | ||
111 | * Create a new path | ||
112 | * | ||
113 | * @param length How many hops will the path have. | ||
114 | * | ||
115 | * @return A newly allocated path with a peer array of the specified length. | ||
116 | */ | ||
117 | struct CadetPeerPath * | ||
118 | path_new (unsigned int length) | ||
119 | { | ||
120 | struct CadetPeerPath *p; | ||
121 | |||
122 | p = GNUNET_new (struct CadetPeerPath); | ||
123 | if (length > 0) | ||
124 | { | ||
125 | p->length = length; | ||
126 | p->peers = GNUNET_malloc (length * sizeof (GNUNET_PEER_Id)); | ||
127 | } | ||
128 | return p; | ||
129 | } | ||
130 | |||
131 | |||
132 | /** | ||
133 | * Invert the path | ||
134 | * | ||
135 | * @param path the path to invert | ||
136 | */ | ||
137 | void | ||
138 | path_invert (struct CadetPeerPath *path) | ||
139 | { | ||
140 | GNUNET_PEER_Id aux; | ||
141 | unsigned int i; | ||
142 | |||
143 | for (i = 0; i < path->length / 2; i++) | ||
144 | { | ||
145 | aux = path->peers[i]; | ||
146 | path->peers[i] = path->peers[path->length - i - 1]; | ||
147 | path->peers[path->length - i - 1] = aux; | ||
148 | } | ||
149 | } | ||
150 | |||
151 | |||
152 | /** | ||
153 | * Duplicate a path, incrementing short peer's rc. | ||
154 | * | ||
155 | * @param path The path to duplicate. | ||
156 | */ | ||
157 | struct CadetPeerPath * | ||
158 | path_duplicate (struct CadetPeerPath *path) | ||
159 | { | ||
160 | struct CadetPeerPath *aux; | ||
161 | unsigned int i; | ||
162 | |||
163 | aux = path_new (path->length); | ||
164 | GNUNET_memcpy (aux->peers, path->peers, path->length * sizeof (GNUNET_PEER_Id)); | ||
165 | for (i = 0; i < path->length; i++) | ||
166 | GNUNET_PEER_change_rc (path->peers[i], 1); | ||
167 | return aux; | ||
168 | } | ||
169 | |||
170 | |||
171 | /** | ||
172 | * Recusively update the info about what is the first hop to reach the node | ||
173 | * | ||
174 | * @param tree Tree this nodes belongs to. | ||
175 | * @param parent The node form which to start updating. | ||
176 | * @param hop If known, ID of the first hop. | ||
177 | * If not known, NULL to find out and pass on children. | ||
178 | */ | ||
179 | static void | ||
180 | tree_node_update_first_hops (struct CadetTunnelTree *tree, | ||
181 | struct CadetTunnelTreeNode *parent, | ||
182 | struct GNUNET_PeerIdentity *hop); | ||
183 | |||
184 | |||
185 | /** | ||
186 | * Get the length of a path. | ||
187 | * | ||
188 | * @param path The path to measure, with the local peer at any point of it. | ||
189 | * | ||
190 | * @return Number of hops to reach destination. | ||
191 | * UINT_MAX in case the peer is not in the path. | ||
192 | */ | ||
193 | unsigned int | ||
194 | path_get_length (struct CadetPeerPath *path) | ||
195 | { | ||
196 | if (NULL == path) | ||
197 | return UINT_MAX; | ||
198 | return path->length; | ||
199 | } | ||
200 | |||
201 | |||
202 | /** | ||
203 | * Destroy the path and free any allocated resources linked to it | ||
204 | * | ||
205 | * @param p the path to destroy | ||
206 | * | ||
207 | * @return GNUNET_OK on success | ||
208 | */ | ||
209 | int | ||
210 | path_destroy (struct CadetPeerPath *p) | ||
211 | { | ||
212 | if (NULL == p) | ||
213 | return GNUNET_OK; | ||
214 | GNUNET_PEER_decrement_rcs (p->peers, p->length); | ||
215 | GNUNET_free_non_null (p->peers); | ||
216 | GNUNET_free (p); | ||
217 | return GNUNET_OK; | ||
218 | } | ||
219 | |||
220 | |||
221 | |||
222 | /** | ||
223 | * Allocates and initializes a new node. | ||
224 | * Sets ID and parent of the new node and inserts it in the DLL of the parent | ||
225 | * | ||
226 | * @param parent Node that will be the parent from the new node, NULL for root | ||
227 | * @param peer Short Id of the new node | ||
228 | * | ||
229 | * @return Newly allocated node | ||
230 | */ | ||
231 | static struct CadetTunnelTreeNode * | ||
232 | tree_node_new (struct CadetTunnelTreeNode *parent, GNUNET_PEER_Id peer) | ||
233 | { | ||
234 | struct CadetTunnelTreeNode *node; | ||
235 | |||
236 | node = GNUNET_new (struct CadetTunnelTreeNode); | ||
237 | node->peer = peer; | ||
238 | GNUNET_PEER_change_rc (peer, 1); | ||
239 | node->parent = parent; | ||
240 | if (NULL != parent) | ||
241 | GNUNET_CONTAINER_DLL_insert (parent->children_head, parent->children_tail, | ||
242 | node); | ||
243 | |||
244 | return node; | ||
245 | } | ||
246 | |||
247 | |||
248 | /** | ||
249 | * Recursively find the given peer. | ||
250 | * | ||
251 | * @param parent Node where to start looking. | ||
252 | * @param peer_id Short ID of the peer to find. | ||
253 | * | ||
254 | * @return Pointer to the node of the peer. NULL if not found. | ||
255 | */ | ||
256 | static struct CadetTunnelTreeNode * | ||
257 | tree_node_find_peer (struct CadetTunnelTreeNode *parent, GNUNET_PEER_Id peer_id) | ||
258 | { | ||
259 | struct CadetTunnelTreeNode *n; | ||
260 | struct CadetTunnelTreeNode *r; | ||
261 | |||
262 | if (parent->peer == peer_id) | ||
263 | return parent; | ||
264 | for (n = parent->children_head; NULL != n; n = n->next) | ||
265 | { | ||
266 | r = tree_node_find_peer (n, peer_id); | ||
267 | if (NULL != r) | ||
268 | return r; | ||
269 | } | ||
270 | return NULL; | ||
271 | } | ||
272 | |||
273 | |||
274 | /** | ||
275 | * Recusively update the info about what is the first hop to reach the node | ||
276 | * | ||
277 | * @param tree Tree this nodes belongs to. | ||
278 | * @param parent ID from node form which to start updating. | ||
279 | * @param hop If known, ID of the first hop. | ||
280 | * If not known, NULL to find out and pass on children. | ||
281 | */ | ||
282 | static void | ||
283 | tree_node_update_first_hops (struct CadetTunnelTree *tree, | ||
284 | struct CadetTunnelTreeNode *parent, | ||
285 | struct GNUNET_PeerIdentity *hop) | ||
286 | { | ||
287 | struct GNUNET_PeerIdentity pi; | ||
288 | struct GNUNET_PeerIdentity *copy; | ||
289 | struct GNUNET_PeerIdentity id; | ||
290 | struct CadetTunnelTreeNode *n; | ||
291 | |||
292 | #if CADET_TREE_DEBUG | ||
293 | GNUNET_PEER_resolve (parent->peer, &id); | ||
294 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "tree: Finding first hop for %s.\n", | ||
295 | GNUNET_i2s (&id)); | ||
296 | #endif | ||
297 | if (NULL == hop) | ||
298 | { | ||
299 | struct CadetTunnelTreeNode *aux; | ||
300 | struct CadetTunnelTreeNode *old; | ||
301 | |||
302 | aux = old = parent; | ||
303 | while (aux != tree->me) | ||
304 | { | ||
305 | #if CADET_TREE_DEBUG | ||
306 | GNUNET_PEER_resolve (aux->peer, &id); | ||
307 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "tree: ... checking %s.\n", | ||
308 | GNUNET_i2s (&id)); | ||
309 | #endif | ||
310 | old = aux; | ||
311 | aux = aux->parent; | ||
312 | GNUNET_assert (NULL != aux); | ||
313 | } | ||
314 | #if CADET_TREE_DEBUG | ||
315 | GNUNET_PEER_resolve (old->peer, &id); | ||
316 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "tree: It's %s!\n", | ||
317 | GNUNET_i2s (&id)); | ||
318 | #endif | ||
319 | hop = π | ||
320 | GNUNET_PEER_resolve (old->peer, hop); | ||
321 | } | ||
322 | GNUNET_PEER_resolve (parent->peer, &id); | ||
323 | copy = GNUNET_CONTAINER_multihashmap_get (tree->first_hops, &id.hashPubKey); | ||
324 | if (NULL == copy) | ||
325 | copy = GNUNET_new (struct GNUNET_PeerIdentity); | ||
326 | *copy = *hop; | ||
327 | |||
328 | (void) GNUNET_CONTAINER_multihashmap_put (tree->first_hops, &id.hashPubKey, | ||
329 | copy, | ||
330 | GNUNET_CONTAINER_MULTIHASHMAPOPTION_REPLACE); | ||
331 | |||
332 | for (n = parent->children_head; NULL != n; n = n->next) | ||
333 | { | ||
334 | tree_node_update_first_hops (tree, n, hop); | ||
335 | } | ||
336 | } | ||
337 | |||
338 | |||
339 | static void | ||
340 | tree_node_debug (struct CadetTunnelTreeNode *n, uint16_t level) | ||
341 | { | ||
342 | struct CadetTunnelTreeNode *c; | ||
343 | struct GNUNET_PeerIdentity id;; | ||
344 | uint16_t i; | ||
345 | |||
346 | for (i = 0; i < level; i++) | ||
347 | FPRINTF (stderr, "%s", " "); | ||
348 | if (n->status == CADET_PEER_READY) | ||
349 | FPRINTF (stderr, "%s", "#"); | ||
350 | if (n->status == CADET_PEER_SEARCHING) | ||
351 | FPRINTF (stderr, "%s", "+"); | ||
352 | if (n->status == CADET_PEER_RELAY) | ||
353 | FPRINTF (stderr, "%s", "-"); | ||
354 | if (n->status == CADET_PEER_RECONNECTING) | ||
355 | FPRINTF (stderr, "%s", "*"); | ||
356 | |||
357 | GNUNET_PEER_resolve (n->peer, &id); | ||
358 | FPRINTF (stderr, "%s, [%u, %p] ", GNUNET_i2s (&id), n->peer, n); | ||
359 | if (NULL != n->parent) | ||
360 | { | ||
361 | GNUNET_PEER_resolve (n->parent->peer, &id); | ||
362 | FPRINTF (stderr, "(-> %s [%u])\n", GNUNET_i2s (&id), n->parent->peer); | ||
363 | } | ||
364 | else | ||
365 | FPRINTF (stderr, "%s", "(root)\n"); | ||
366 | for (c = n->children_head; NULL != c; c = c->next) | ||
367 | tree_node_debug (c, level + 1); | ||
368 | } | ||
369 | |||
370 | |||
371 | /** | ||
372 | * Destroys and frees the node and all children | ||
373 | * | ||
374 | * @param parent Parent node to be destroyed | ||
375 | */ | ||
376 | static void | ||
377 | tree_node_destroy (struct CadetTunnelTreeNode *parent) | ||
378 | { | ||
379 | struct CadetTunnelTreeNode *n; | ||
380 | struct CadetTunnelTreeNode *next; | ||
381 | |||
382 | if (NULL == parent) | ||
383 | return; | ||
384 | #if CADET_TREE_DEBUG | ||
385 | struct GNUNET_PeerIdentity id; | ||
386 | |||
387 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "tree: Destroying node %u\n", | ||
388 | parent->peer); | ||
389 | GNUNET_PEER_resolve (parent->peer, &id); | ||
390 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "tree: (%s)\n", GNUNET_i2s (&id)); | ||
391 | #endif | ||
392 | n = parent->children_head; | ||
393 | while (NULL != n) | ||
394 | { | ||
395 | next = n->next; | ||
396 | tree_node_destroy (n); | ||
397 | n = next; | ||
398 | } | ||
399 | GNUNET_PEER_change_rc (parent->peer, -1); | ||
400 | if (NULL != parent->parent) | ||
401 | GNUNET_CONTAINER_DLL_remove (parent->parent->children_head, | ||
402 | parent->parent->children_tail, parent); | ||
403 | GNUNET_free (parent); | ||
404 | } | ||
405 | |||
406 | |||
407 | |||
408 | /** | ||
409 | * Create a new tree. | ||
410 | * | ||
411 | * @param peer A short peer id of the root of the tree. | ||
412 | * | ||
413 | * @return A newly allocated and initialized tunnel tree. | ||
414 | */ | ||
415 | struct CadetTunnelTree * | ||
416 | tree_new (GNUNET_PEER_Id peer) | ||
417 | { | ||
418 | struct CadetTunnelTree *tree; | ||
419 | |||
420 | tree = GNUNET_new (struct CadetTunnelTree); | ||
421 | tree->first_hops = GNUNET_CONTAINER_multihashmap_create (32, GNUNET_NO); | ||
422 | tree->root = tree_node_new (NULL, peer); | ||
423 | tree->root->status = CADET_PEER_ROOT; | ||
424 | |||
425 | if (1 == peer) | ||
426 | { | ||
427 | tree->me = tree->root; | ||
428 | } | ||
429 | |||
430 | return tree; | ||
431 | } | ||
432 | |||
433 | |||
434 | /** | ||
435 | * Set the status of a node. | ||
436 | * | ||
437 | * @param tree Tree. | ||
438 | * @param peer A short peer id of the node. | ||
439 | * @param status New status to set. | ||
440 | */ | ||
441 | void | ||
442 | tree_set_status (struct CadetTunnelTree *tree, GNUNET_PEER_Id peer, | ||
443 | enum CadetPeerState status) | ||
444 | { | ||
445 | struct CadetTunnelTreeNode *n; | ||
446 | |||
447 | n = tree_find_peer (tree, peer); | ||
448 | if (NULL == n) | ||
449 | return; | ||
450 | n->status = status; | ||
451 | } | ||
452 | |||
453 | |||
454 | /** | ||
455 | * Get the status of a node. | ||
456 | * | ||
457 | * @param tree Tree whose node's status we want to now. | ||
458 | * @param peer A short peer id of the node. | ||
459 | * | ||
460 | * @return Status of the peer. | ||
461 | */ | ||
462 | enum CadetPeerState | ||
463 | tree_get_status (struct CadetTunnelTree *tree, GNUNET_PEER_Id peer) | ||
464 | { | ||
465 | struct CadetTunnelTreeNode *n; | ||
466 | |||
467 | n = tree_find_peer (tree, peer); | ||
468 | if (NULL == n) | ||
469 | return CADET_PEER_INVALID; | ||
470 | return n->status; | ||
471 | } | ||
472 | |||
473 | |||
474 | /** | ||
475 | * Get the id of the predecessor of the local node. | ||
476 | * | ||
477 | * @param tree Tree whose local id we want to now. | ||
478 | * | ||
479 | * @return Short peer id of local peer. | ||
480 | */ | ||
481 | GNUNET_PEER_Id | ||
482 | tree_get_predecessor (struct CadetTunnelTree *tree) | ||
483 | { | ||
484 | if (NULL != tree->me && NULL != tree->me->parent) | ||
485 | return tree->me->parent->peer; | ||
486 | else | ||
487 | return (GNUNET_PEER_Id) 0; | ||
488 | } | ||
489 | |||
490 | |||
491 | /** | ||
492 | * Find the first peer whom to send a packet to go down this path | ||
493 | * | ||
494 | * @param t The tunnel tree to use | ||
495 | * @param peer The peerinfo of the peer we are trying to reach | ||
496 | * | ||
497 | * @return peerinfo of the peer who is the first hop in the tunnel | ||
498 | * NULL on error | ||
499 | * | ||
500 | * FIXME use PEER_Id | ||
501 | */ | ||
502 | struct GNUNET_PeerIdentity * | ||
503 | tree_get_first_hop (struct CadetTunnelTree *t, GNUNET_PEER_Id peer) | ||
504 | { | ||
505 | struct GNUNET_PeerIdentity id; | ||
506 | struct GNUNET_PeerIdentity *r; | ||
507 | |||
508 | GNUNET_PEER_resolve (peer, &id); | ||
509 | r = GNUNET_CONTAINER_multihashmap_get (t->first_hops, &id.hashPubKey); | ||
510 | if (NULL == r) | ||
511 | { | ||
512 | struct CadetTunnelTreeNode *n; | ||
513 | |||
514 | n = tree_find_peer (t, peer); | ||
515 | if (NULL != t->me && NULL != n) | ||
516 | { | ||
517 | tree_node_update_first_hops (t, n, NULL); | ||
518 | r = GNUNET_CONTAINER_multihashmap_get (t->first_hops, &id.hashPubKey); | ||
519 | GNUNET_assert (NULL != r); | ||
520 | } | ||
521 | else | ||
522 | { | ||
523 | GNUNET_log (GNUNET_ERROR_TYPE_WARNING, | ||
524 | "Tree structure inconsistent! me: %p, n: %p", t->me, n); | ||
525 | GNUNET_break (0); | ||
526 | } | ||
527 | } | ||
528 | |||
529 | return r; | ||
530 | } | ||
531 | |||
532 | |||
533 | /** | ||
534 | * Find the given peer in the tree. | ||
535 | * | ||
536 | * @param tree Tree where to look for the peer. | ||
537 | * @param peer_id Short ID of the peer to find. | ||
538 | * | ||
539 | * @return Pointer to the node of the peer. NULL if not found. | ||
540 | */ | ||
541 | struct CadetTunnelTreeNode * | ||
542 | tree_find_peer (struct CadetTunnelTree *tree, GNUNET_PEER_Id peer_id) | ||
543 | { | ||
544 | return tree_node_find_peer (tree->root, peer_id); | ||
545 | } | ||
546 | |||
547 | |||
548 | /** | ||
549 | * Recusively mark peer and children as disconnected, notify client | ||
550 | * | ||
551 | * @param tree Tree this node belongs to | ||
552 | * @param parent Node to be clean, potentially with children | ||
553 | * @param cb Callback to use to notify about disconnected peers. | ||
554 | * @param cbcls Closure for cb. | ||
555 | */ | ||
556 | static void | ||
557 | tree_mark_peers_disconnected (struct CadetTunnelTree *tree, | ||
558 | struct CadetTunnelTreeNode *parent, | ||
559 | CadetTreeCallback cb, void *cbcls) | ||
560 | { | ||
561 | struct GNUNET_PeerIdentity *pi; | ||
562 | struct GNUNET_PeerIdentity id; | ||
563 | struct CadetTunnelTreeNode *n; | ||
564 | |||
565 | for (n = parent->children_head; NULL != n; n = n->next) | ||
566 | { | ||
567 | tree_mark_peers_disconnected (tree, n, cb, cbcls); | ||
568 | } | ||
569 | if (CADET_PEER_READY == parent->status) | ||
570 | { | ||
571 | if (NULL != cb) | ||
572 | cb (cbcls, parent->peer); | ||
573 | parent->status = CADET_PEER_RECONNECTING; | ||
574 | } | ||
575 | |||
576 | /* Remove and free info about first hop */ | ||
577 | GNUNET_PEER_resolve (parent->peer, &id); | ||
578 | pi = GNUNET_CONTAINER_multihashmap_get (tree->first_hops, &id.hashPubKey); | ||
579 | GNUNET_CONTAINER_multihashmap_remove_all (tree->first_hops, &id.hashPubKey); | ||
580 | if (NULL != pi) | ||
581 | GNUNET_free (pi); | ||
582 | } | ||
583 | |||
584 | |||
585 | /** | ||
586 | * Iterate over all children of the local node. | ||
587 | * | ||
588 | * @param tree Tree to use. Must have "me" set. | ||
589 | * @param cb Callback to call over each child. | ||
590 | * @param cb_cls Closure for @c cb. | ||
591 | */ | ||
592 | void | ||
593 | tree_iterate_children (struct CadetTunnelTree *tree, CadetTreeCallback cb, | ||
594 | void *cb_cls) | ||
595 | { | ||
596 | struct CadetTunnelTreeNode *n; | ||
597 | |||
598 | if (NULL == tree->me) | ||
599 | return; | ||
600 | for (n = tree->me->children_head; NULL != n; n = n->next) | ||
601 | { | ||
602 | cb (cb_cls, n->peer); | ||
603 | } | ||
604 | } | ||
605 | |||
606 | |||
607 | /** | ||
608 | * Struct to contain a list of pending nodes when iterating a tree. | ||
609 | */ | ||
610 | struct CadetTreePendingNode { | ||
611 | |||
612 | /** | ||
613 | * DLL next. | ||
614 | */ | ||
615 | struct CadetTreePendingNode *next; | ||
616 | |||
617 | /** | ||
618 | * DLL prev. | ||
619 | */ | ||
620 | struct CadetTreePendingNode *prev; | ||
621 | |||
622 | /** | ||
623 | * Pending node. | ||
624 | */ | ||
625 | struct CadetTunnelTreeNode *node; | ||
626 | }; | ||
627 | |||
628 | |||
629 | /** | ||
630 | * Iterate over all nodes in the tree. | ||
631 | * | ||
632 | * @param tree Tree to use.. | ||
633 | * @param cb Callback to call over each child. | ||
634 | * @param cb_cls Closure for @c cb. | ||
635 | * | ||
636 | * TODO: recursive implementation? (s/heap/stack/g) | ||
637 | */ | ||
638 | void | ||
639 | tree_iterate_all (struct CadetTunnelTree *tree, | ||
640 | CadetWholeTreeCallback cb, | ||
641 | void *cb_cls) | ||
642 | { | ||
643 | struct CadetTunnelTreeNode *parent; | ||
644 | struct CadetTunnelTreeNode *n; | ||
645 | struct CadetTreePendingNode *head; | ||
646 | struct CadetTreePendingNode *tail; | ||
647 | struct CadetTreePendingNode *pending; | ||
648 | |||
649 | cb (cb_cls, tree->root->peer, 0); | ||
650 | pending = GNUNET_new (struct CadetTreePendingNode); | ||
651 | pending->node = tree->root; | ||
652 | head = tail = NULL; | ||
653 | GNUNET_CONTAINER_DLL_insert (head, tail, pending); | ||
654 | |||
655 | while (NULL != head) | ||
656 | { | ||
657 | pending = head; | ||
658 | parent = pending->node; | ||
659 | GNUNET_CONTAINER_DLL_remove (head, tail, pending); | ||
660 | GNUNET_free (pending); | ||
661 | for (n = parent->children_head; NULL != n; n = n->next) | ||
662 | { | ||
663 | cb (cb_cls, n->peer, parent->peer); | ||
664 | pending = GNUNET_new (struct CadetTreePendingNode); | ||
665 | pending->node = n; | ||
666 | /* Insert_tail: breadth first, Insert: depth first */ | ||
667 | GNUNET_CONTAINER_DLL_insert (head, tail, pending); | ||
668 | } | ||
669 | } | ||
670 | } | ||
671 | |||
672 | |||
673 | /** | ||
674 | * Iterator to count the children in a tree. | ||
675 | */ | ||
676 | static void | ||
677 | count_children_cb (void *cls, GNUNET_PEER_Id peer) | ||
678 | { | ||
679 | unsigned int *i = cls; | ||
680 | |||
681 | (*i)++; | ||
682 | } | ||
683 | |||
684 | |||
685 | /** | ||
686 | * Count how many children does the local node have in the tree. | ||
687 | * | ||
688 | * @param tree Tree to use. Must have "me" set. | ||
689 | */ | ||
690 | unsigned int | ||
691 | tree_count_children (struct CadetTunnelTree *tree) | ||
692 | { | ||
693 | unsigned int i; | ||
694 | |||
695 | i = 0; | ||
696 | tree_iterate_children(tree, &count_children_cb, &i); | ||
697 | return i; | ||
698 | } | ||
699 | |||
700 | |||
701 | /** | ||
702 | * Recusively update the info about what is the first hop to reach the node | ||
703 | * | ||
704 | * @param tree Tree this nodes belongs to. | ||
705 | * @param parent_id Short ID from node form which to start updating. | ||
706 | * @param hop If known, ID of the first hop. | ||
707 | * If not known, NULL to find out and pass on children. | ||
708 | */ | ||
709 | void | ||
710 | tree_update_first_hops (struct CadetTunnelTree *tree, GNUNET_PEER_Id parent_id, | ||
711 | struct GNUNET_PeerIdentity *hop) | ||
712 | { | ||
713 | tree_node_update_first_hops (tree, tree_find_peer (tree, parent_id), hop); | ||
714 | } | ||
715 | |||
716 | |||
717 | /** | ||
718 | * Delete the current path to the peer, including all now unused relays. | ||
719 | * The destination peer is NOT destroyed, it is returned in order to either set | ||
720 | * a new path to it or destroy it explicitly, taking care of it's child nodes. | ||
721 | * | ||
722 | * @param t Tunnel tree where to delete the path from. | ||
723 | * @param peer_id Short ID of the destination peer whose path we want to remove. | ||
724 | * @param cb Callback to use to notify about disconnected peers. | ||
725 | * @param cbcls Closure for cb. | ||
726 | * | ||
727 | * @return pointer to the pathless node. | ||
728 | * NULL when not found | ||
729 | */ | ||
730 | struct CadetTunnelTreeNode * | ||
731 | tree_del_path (struct CadetTunnelTree *t, GNUNET_PEER_Id peer_id, | ||
732 | CadetTreeCallback cb, void *cbcls) | ||
733 | { | ||
734 | struct CadetTunnelTreeNode *parent; | ||
735 | struct CadetTunnelTreeNode *node; | ||
736 | struct CadetTunnelTreeNode *n; | ||
737 | |||
738 | #if CADET_TREE_DEBUG | ||
739 | struct GNUNET_PeerIdentity id; | ||
740 | |||
741 | GNUNET_PEER_resolve (peer_id, &id); | ||
742 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "tree: Deleting path to %s.\n", | ||
743 | GNUNET_i2s (&id)); | ||
744 | #endif | ||
745 | if (NULL == t->root || peer_id == t->root->peer) | ||
746 | return NULL; | ||
747 | |||
748 | for (n = t->disconnected_head; NULL != n; n = n->next) | ||
749 | { | ||
750 | if (n->peer == peer_id) | ||
751 | { | ||
752 | /* Was already pathless, waiting for reconnection */ | ||
753 | GNUNET_CONTAINER_DLL_remove (t->disconnected_head, t->disconnected_tail, | ||
754 | n); | ||
755 | return n; | ||
756 | } | ||
757 | } | ||
758 | n = tree_find_peer (t, peer_id); | ||
759 | if (NULL == n) | ||
760 | return NULL; | ||
761 | node = n; | ||
762 | |||
763 | parent = n->parent; | ||
764 | GNUNET_CONTAINER_DLL_remove (parent->children_head, parent->children_tail, n); | ||
765 | n->parent = NULL; | ||
766 | |||
767 | while (CADET_PEER_RELAY == parent->status && | ||
768 | NULL == parent->children_head) | ||
769 | { | ||
770 | #if CADET_TREE_DEBUG | ||
771 | GNUNET_PEER_resolve (parent->peer, &id); | ||
772 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "tree: Deleting node %s.\n", | ||
773 | GNUNET_i2s (&id)); | ||
774 | #endif | ||
775 | n = parent->parent; | ||
776 | if (parent == t->me) | ||
777 | t->me = NULL; | ||
778 | tree_node_destroy (parent); | ||
779 | parent = n; | ||
780 | } | ||
781 | #if CADET_TREE_DEBUG | ||
782 | GNUNET_PEER_resolve (parent->peer, &id); | ||
783 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "tree: Not deleted peer %s.\n", | ||
784 | GNUNET_i2s (&id)); | ||
785 | #endif | ||
786 | |||
787 | tree_mark_peers_disconnected (t, node, cb, cbcls); | ||
788 | |||
789 | return node; | ||
790 | } | ||
791 | |||
792 | |||
793 | /** | ||
794 | * Return a newly allocated individual path to reach a peer from the local peer, | ||
795 | * according to the path tree of some tunnel. | ||
796 | * | ||
797 | * @param t Tunnel from which to read the path tree. | ||
798 | * @param peer Short ID of the destination peer to whom we want a path. | ||
799 | * | ||
800 | * @return A newly allocated individual path to reach the destination peer. | ||
801 | * Path must be destroyed afterwards. | ||
802 | */ | ||
803 | struct CadetPeerPath * | ||
804 | tree_get_path_to_peer (struct CadetTunnelTree *t, GNUNET_PEER_Id peer) | ||
805 | { | ||
806 | struct CadetTunnelTreeNode *n; | ||
807 | struct CadetPeerPath *p; | ||
808 | |||
809 | n = tree_find_peer (t, peer); | ||
810 | if (NULL == n) | ||
811 | { | ||
812 | GNUNET_break (0); | ||
813 | return NULL; | ||
814 | } | ||
815 | p = path_new (0); | ||
816 | |||
817 | /* Building the path (inverted!) */ | ||
818 | while (n->peer != 1) | ||
819 | { | ||
820 | GNUNET_array_append (p->peers, p->length, n->peer); | ||
821 | GNUNET_PEER_change_rc (n->peer, 1); | ||
822 | n = n->parent; | ||
823 | if (NULL == n) | ||
824 | { | ||
825 | GNUNET_break (0); | ||
826 | path_destroy (p); | ||
827 | return NULL; | ||
828 | } | ||
829 | } | ||
830 | GNUNET_array_append (p->peers, p->length, 1); | ||
831 | GNUNET_PEER_change_rc (1, 1); | ||
832 | |||
833 | path_invert (p); | ||
834 | |||
835 | return p; | ||
836 | } | ||
837 | |||
838 | |||
839 | |||
840 | /** | ||
841 | * Integrate a stand alone path into the tunnel tree. | ||
842 | * If the peer toward which the new path is already in the tree, the peer | ||
843 | * and its children will be maked as disconnected and the callback | ||
844 | * will be called on each one of them. They will be maked as online only after | ||
845 | * receiving a PATH ACK for the new path for each one of them, so the caller | ||
846 | * should take care of sending a new CREATE PATH message for each disconnected | ||
847 | * peer. | ||
848 | * | ||
849 | * @param t Tunnel where to add the new path. | ||
850 | * @param p Path to be integrated. | ||
851 | * @param cb Callback to use to notify about peers temporarily disconnecting. | ||
852 | * @param cbcls Closure for cb. | ||
853 | * | ||
854 | * @return GNUNET_OK in case of success. | ||
855 | * GNUNET_SYSERR in case of error. | ||
856 | * | ||
857 | * TODO: optimize | ||
858 | * - go backwards on path looking for each peer in the present tree | ||
859 | * - do not disconnect peers until new path is created & connected | ||
860 | */ | ||
861 | int | ||
862 | tree_add_path (struct CadetTunnelTree *t, const struct CadetPeerPath *p, | ||
863 | CadetTreeCallback cb, void *cbcls) | ||
864 | { | ||
865 | struct CadetTunnelTreeNode *parent; | ||
866 | struct CadetTunnelTreeNode *oldnode; | ||
867 | struct CadetTunnelTreeNode *n; | ||
868 | struct CadetTunnelTreeNode *c; | ||
869 | struct GNUNET_PeerIdentity id; | ||
870 | int me; | ||
871 | unsigned int i; | ||
872 | |||
873 | #if CADET_TREE_DEBUG | ||
874 | GNUNET_PEER_resolve (p->peers[p->length - 1], &id); | ||
875 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | ||
876 | "tree: Adding path [%u] towards peer %s.\n", p->length, | ||
877 | GNUNET_i2s (&id)); | ||
878 | #endif | ||
879 | |||
880 | GNUNET_assert (0 != p->length); | ||
881 | parent = n = t->root; | ||
882 | if (n->peer != p->peers[0]) | ||
883 | { | ||
884 | GNUNET_break (0); | ||
885 | return GNUNET_SYSERR; | ||
886 | } | ||
887 | if (1 == p->length) | ||
888 | return GNUNET_OK; | ||
889 | oldnode = tree_del_path (t, p->peers[p->length - 1], cb, cbcls); | ||
890 | /* Look for the first node that is not already present in the tree | ||
891 | * | ||
892 | * Assuming that the tree is somewhat balanced, O(log n * log N). | ||
893 | * - Length of the path is expected to be log N (size of whole network). | ||
894 | * - Each level of the tree is expected to have log n children (size of tree). | ||
895 | */ | ||
896 | me = t->root->peer == 1 ? 0 : -1; | ||
897 | for (i = 1; i < p->length; i++) | ||
898 | { | ||
899 | #if CADET_TREE_DEBUG | ||
900 | GNUNET_PEER_resolve (p->peers[i], &id); | ||
901 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "tree: Looking for peer %s.\n", | ||
902 | GNUNET_i2s (&id)); | ||
903 | #endif | ||
904 | parent = n; | ||
905 | if (p->peers[i] == 1) | ||
906 | me = i; | ||
907 | for (c = n->children_head; NULL != c; c = c->next) | ||
908 | { | ||
909 | if (c->peer == p->peers[i]) | ||
910 | { | ||
911 | #if CADET_TREE_DEBUG | ||
912 | GNUNET_PEER_resolve (parent->peer, &id); | ||
913 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | ||
914 | "tree: Found in children of %s.\n", GNUNET_i2s (&id)); | ||
915 | #endif | ||
916 | n = c; | ||
917 | break; | ||
918 | } | ||
919 | } | ||
920 | /* If we couldn't find a child equal to path[i], we have reached the end | ||
921 | * of the common path. */ | ||
922 | if (parent == n) | ||
923 | break; | ||
924 | } | ||
925 | #if CADET_TREE_DEBUG | ||
926 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "tree: All childen visited.\n"); | ||
927 | #endif | ||
928 | /* Add the rest of the path as a branch from parent. */ | ||
929 | while (i < p->length) | ||
930 | { | ||
931 | #if CADET_TREE_DEBUG | ||
932 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "tree: Adding peer %u to %u.\n", | ||
933 | p->peers[i], parent->peer); | ||
934 | GNUNET_PEER_resolve (p->peers[i], &id); | ||
935 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "tree: Adding peer %s.\n", | ||
936 | GNUNET_i2s (&id)); | ||
937 | GNUNET_PEER_resolve (parent->peer, &id); | ||
938 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "tree: to %s.\n", | ||
939 | GNUNET_i2s (&id)); | ||
940 | #endif | ||
941 | |||
942 | if (i == p->length - 1 && NULL != oldnode) | ||
943 | { | ||
944 | #if CADET_TREE_DEBUG | ||
945 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | ||
946 | "tree: Putting old node into place.\n"); | ||
947 | #endif | ||
948 | oldnode->parent = parent; | ||
949 | GNUNET_CONTAINER_DLL_insert (parent->children_head, parent->children_tail, | ||
950 | oldnode); | ||
951 | tree_node_update_first_hops (t, oldnode, NULL); | ||
952 | n = oldnode; | ||
953 | } | ||
954 | else | ||
955 | { | ||
956 | #if CADET_TREE_DEBUG | ||
957 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "tree: Creating new node.\n"); | ||
958 | #endif | ||
959 | n = tree_node_new (parent, p->peers[i]); | ||
960 | n->status = CADET_PEER_RELAY; | ||
961 | } | ||
962 | if (n->peer == 1) | ||
963 | { | ||
964 | t->me = n; | ||
965 | me = i; | ||
966 | } | ||
967 | i++; | ||
968 | parent = n; | ||
969 | } | ||
970 | n->status = CADET_PEER_SEARCHING; | ||
971 | |||
972 | GNUNET_break (-1 != me); | ||
973 | |||
974 | /* Add info about first hop into hashmap. */ | ||
975 | if (-1 != me && me < p->length - 1) | ||
976 | { | ||
977 | #if CADET_TREE_DEBUG | ||
978 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | ||
979 | "CADET: finding first hop (own pos %d/%u)\n", me, | ||
980 | p->length - 1); | ||
981 | #endif | ||
982 | GNUNET_PEER_resolve (p->peers[me + 1], &id); | ||
983 | tree_update_first_hops (t, p->peers[me + 1], &id); | ||
984 | } | ||
985 | #if CADET_TREE_DEBUG | ||
986 | else | ||
987 | { | ||
988 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | ||
989 | "CADET: was last in path, not updating first hops (%d/%u)\n", | ||
990 | me, p->length - 1); | ||
991 | } | ||
992 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "tree: New node added.\n"); | ||
993 | #endif | ||
994 | if (NULL == t->me) | ||
995 | t->me = tree_find_peer (t, 1); | ||
996 | return GNUNET_OK; | ||
997 | } | ||
998 | |||
999 | |||
1000 | /** | ||
1001 | * Notifies a tree that a connection it might be using is broken. | ||
1002 | * Marks all peers down the paths as disconnected and notifies the client. | ||
1003 | * | ||
1004 | * @param t Tree to use. | ||
1005 | * @param p1 Short id of one of the peers (order unimportant) | ||
1006 | * @param p2 Short id of one of the peers (order unimportant) | ||
1007 | * @param cb Function to call for every peer that is marked as disconnected. | ||
1008 | * @param cbcls Closure for cb. | ||
1009 | * | ||
1010 | * @return Short ID of the first disconnected peer in the tree. | ||
1011 | */ | ||
1012 | GNUNET_PEER_Id | ||
1013 | tree_notify_connection_broken (struct CadetTunnelTree *t, GNUNET_PEER_Id p1, | ||
1014 | GNUNET_PEER_Id p2, CadetTreeCallback cb, | ||
1015 | void *cbcls) | ||
1016 | { | ||
1017 | struct CadetTunnelTreeNode *n; | ||
1018 | struct CadetTunnelTreeNode *c; | ||
1019 | |||
1020 | n = tree_find_peer (t, p1); | ||
1021 | if (NULL == n) | ||
1022 | return 0; | ||
1023 | if (NULL != n->parent && n->parent->peer == p2) | ||
1024 | { | ||
1025 | tree_mark_peers_disconnected (t, n, cb, cbcls); | ||
1026 | GNUNET_CONTAINER_DLL_remove (n->parent->children_head, | ||
1027 | n->parent->children_tail, n); | ||
1028 | GNUNET_CONTAINER_DLL_insert (t->disconnected_head, t->disconnected_tail, n); | ||
1029 | return p1; | ||
1030 | } | ||
1031 | for (c = n->children_head; NULL != c; c = c->next) | ||
1032 | { | ||
1033 | if (c->peer == p2) | ||
1034 | { | ||
1035 | tree_mark_peers_disconnected (t, c, cb, cbcls); | ||
1036 | GNUNET_CONTAINER_DLL_remove (n->children_head, n->children_tail, c); | ||
1037 | GNUNET_CONTAINER_DLL_insert (t->disconnected_head, t->disconnected_tail, | ||
1038 | c); | ||
1039 | return p2; | ||
1040 | } | ||
1041 | } | ||
1042 | return 0; | ||
1043 | } | ||
1044 | |||
1045 | |||
1046 | /** | ||
1047 | * Deletes a peer from a tunnel, liberating all unused resources on the path to | ||
1048 | * it. It shouldn't have children, if it has they will be destroyed as well. | ||
1049 | * If the tree is not local and no longer has any paths, the root node will be | ||
1050 | * destroyed and marked as NULL. | ||
1051 | * | ||
1052 | * @param t Tunnel tree to use. | ||
1053 | * @param peer Short ID of the peer to remove from the tunnel tree. | ||
1054 | * @param cb Callback to notify client of disconnected peers. | ||
1055 | * @param cbcls Closure for cb. | ||
1056 | * | ||
1057 | * @return GNUNET_OK or GNUNET_SYSERR | ||
1058 | */ | ||
1059 | int | ||
1060 | tree_del_peer (struct CadetTunnelTree *t, GNUNET_PEER_Id peer, | ||
1061 | CadetTreeCallback cb, void *cbcls) | ||
1062 | { | ||
1063 | struct CadetTunnelTreeNode *n; | ||
1064 | |||
1065 | n = tree_del_path (t, peer, cb, cbcls); | ||
1066 | if (NULL == n) | ||
1067 | { | ||
1068 | GNUNET_break (0); | ||
1069 | return GNUNET_YES; | ||
1070 | } | ||
1071 | tree_node_destroy (n); | ||
1072 | if (NULL == t->root->children_head && t->me != t->root) | ||
1073 | { | ||
1074 | tree_node_destroy (t->root); | ||
1075 | t->root = NULL; | ||
1076 | return GNUNET_NO; | ||
1077 | } | ||
1078 | return GNUNET_YES; | ||
1079 | } | ||
1080 | |||
1081 | |||
1082 | |||
1083 | /** | ||
1084 | * Get the cost of the path relative to the already built tunnel tree. | ||
1085 | * | ||
1086 | * @param t The tunnel tree to which compare. | ||
1087 | * @param path The individual path to reach a peer. It has to start at the | ||
1088 | * root of the tree to be comparable. | ||
1089 | * | ||
1090 | * @return Number of hops to reach destination, UINT_MAX in case the peer is not | ||
1091 | * in the path. | ||
1092 | * | ||
1093 | * TODO: adapt to allow any start / root combination | ||
1094 | * TODO: take in account state of the nodes | ||
1095 | */ | ||
1096 | unsigned int | ||
1097 | tree_get_path_cost (struct CadetTunnelTree *t, struct CadetPeerPath *path) | ||
1098 | { | ||
1099 | struct CadetTunnelTreeNode *n; | ||
1100 | struct CadetTunnelTreeNode *p; | ||
1101 | unsigned int i; | ||
1102 | unsigned int l; | ||
1103 | |||
1104 | l = path_get_length (path); | ||
1105 | p = t->root; | ||
1106 | if (t->root->peer != path->peers[0]) | ||
1107 | { | ||
1108 | GNUNET_break (0); | ||
1109 | return UINT_MAX; | ||
1110 | } | ||
1111 | for (i = 1; i < l; i++) | ||
1112 | { | ||
1113 | for (n = p->children_head; NULL != n; n = n->next) | ||
1114 | { | ||
1115 | if (path->peers[i] == n->peer) | ||
1116 | { | ||
1117 | break; | ||
1118 | } | ||
1119 | } | ||
1120 | if (NULL == n) | ||
1121 | return l - i; | ||
1122 | p = n; | ||
1123 | } | ||
1124 | return l - i; | ||
1125 | } | ||
1126 | |||
1127 | |||
1128 | /** | ||
1129 | * Print the tree on stderr | ||
1130 | * | ||
1131 | * @param t The tree | ||
1132 | */ | ||
1133 | void | ||
1134 | tree_debug (struct CadetTunnelTree *t) | ||
1135 | { | ||
1136 | tree_node_debug (t->root, 0); | ||
1137 | FPRINTF (stderr, "root: %p\n", t->root); | ||
1138 | FPRINTF (stderr, "me: %p\n", t->me); | ||
1139 | } | ||
1140 | |||
1141 | |||
1142 | /** | ||
1143 | * Iterator over hash map peer entries and frees all data in it. | ||
1144 | * Used prior to destroying a hashmap. Makes you miss anonymous functions in C. | ||
1145 | * | ||
1146 | * @param cls closure | ||
1147 | * @param key current key code (will no longer contain valid data!!) | ||
1148 | * @param value value in the hash map (treated as void *) | ||
1149 | * @return GNUNET_YES if we should continue to iterate, GNUNET_NO if not. | ||
1150 | */ | ||
1151 | static int | ||
1152 | iterate_free (void *cls, const struct GNUNET_HashCode * key, void *value) | ||
1153 | { | ||
1154 | GNUNET_free (value); | ||
1155 | return GNUNET_YES; | ||
1156 | } | ||
1157 | |||
1158 | |||
1159 | /** | ||
1160 | * Destroy the whole tree and free all used memory and Peer_Ids | ||
1161 | * | ||
1162 | * @param t Tree to be destroyed | ||
1163 | */ | ||
1164 | void | ||
1165 | tree_destroy (struct CadetTunnelTree *t) | ||
1166 | { | ||
1167 | #if CADET_TREE_DEBUG | ||
1168 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "tree: Destroying tree\n"); | ||
1169 | #endif | ||
1170 | tree_node_destroy (t->root); | ||
1171 | GNUNET_CONTAINER_multihashmap_iterate (t->first_hops, &iterate_free, NULL); | ||
1172 | GNUNET_CONTAINER_multihashmap_destroy (t->first_hops); | ||
1173 | GNUNET_free (t); | ||
1174 | } | ||
diff --git a/src/cadet/cadet_tunnel_tree.h b/src/cadet/cadet_tunnel_tree.h deleted file mode 100644 index 54dc6144f..000000000 --- a/src/cadet/cadet_tunnel_tree.h +++ /dev/null | |||
@@ -1,382 +0,0 @@ | |||
1 | /* | ||
2 | This file is part of GNUnet. | ||
3 | Copyright (C) 2001 - 2011 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 | /** | ||
22 | * @file cadet/cadet_tunnel_tree.h | ||
23 | * @brief Tunnel tree handling functions | ||
24 | * @author Bartlomiej Polot | ||
25 | */ | ||
26 | |||
27 | #include "cadet.h" | ||
28 | |||
29 | /******************************************************************************/ | ||
30 | /************************ DATA STRUCTURES ****************************/ | ||
31 | /******************************************************************************/ | ||
32 | |||
33 | /** | ||
34 | * Information regarding a possible path to reach a single peer | ||
35 | */ | ||
36 | struct CadetPeerPath | ||
37 | { | ||
38 | |||
39 | /** | ||
40 | * Linked list | ||
41 | */ | ||
42 | struct CadetPeerPath *next; | ||
43 | struct CadetPeerPath *prev; | ||
44 | |||
45 | /** | ||
46 | * List of all the peers that form the path from origin to target. | ||
47 | */ | ||
48 | GNUNET_PEER_Id *peers; | ||
49 | |||
50 | /** | ||
51 | * Number of peers (hops) in the path | ||
52 | */ | ||
53 | unsigned int length; | ||
54 | |||
55 | }; | ||
56 | |||
57 | |||
58 | /** | ||
59 | * Node of path tree for a tunnel | ||
60 | */ | ||
61 | struct CadetTunnelTreeNode; | ||
62 | |||
63 | |||
64 | /** | ||
65 | * Tree to reach all peers in the tunnel | ||
66 | */ | ||
67 | struct CadetTunnelTree; | ||
68 | |||
69 | |||
70 | /******************************************************************************/ | ||
71 | /************************* FUNCTIONS *****************************/ | ||
72 | /******************************************************************************/ | ||
73 | |||
74 | /** | ||
75 | * Create a new path. | ||
76 | * | ||
77 | * @param length How many hops will the path have. | ||
78 | * | ||
79 | * @return A newly allocated path with a peer array of the specified length. | ||
80 | */ | ||
81 | struct CadetPeerPath * | ||
82 | path_new (unsigned int length); | ||
83 | |||
84 | |||
85 | /** | ||
86 | * Invert the path. | ||
87 | * | ||
88 | * @param path The path to invert. | ||
89 | */ | ||
90 | void | ||
91 | path_invert (struct CadetPeerPath *path); | ||
92 | |||
93 | |||
94 | /** | ||
95 | * Duplicate a path, incrementing short peer's rc. | ||
96 | * | ||
97 | * @param path The path to duplicate. | ||
98 | */ | ||
99 | struct CadetPeerPath * | ||
100 | path_duplicate (struct CadetPeerPath *path); | ||
101 | |||
102 | |||
103 | /** | ||
104 | * Get the length of a path. | ||
105 | * | ||
106 | * @param path The path to measure, with the local peer at any point of it. | ||
107 | * | ||
108 | * @return Number of hops to reach destination. | ||
109 | * UINT_MAX in case the peer is not in the path. | ||
110 | */ | ||
111 | unsigned int | ||
112 | path_get_length (struct CadetPeerPath *path); | ||
113 | |||
114 | |||
115 | /** | ||
116 | * Destroy the path and free any allocated resources linked to it | ||
117 | * | ||
118 | * @param p the path to destroy | ||
119 | * | ||
120 | * @return GNUNET_OK on success | ||
121 | */ | ||
122 | int | ||
123 | path_destroy (struct CadetPeerPath *p); | ||
124 | |||
125 | |||
126 | /******************************************************************************/ | ||
127 | |||
128 | /** | ||
129 | * Iterator over all children of a node. | ||
130 | * | ||
131 | * @param cls Closure. | ||
132 | * @param peer_id Short ID of the peer. | ||
133 | */ | ||
134 | typedef void (*CadetTreeCallback) (void *cls, GNUNET_PEER_Id peer_id); | ||
135 | |||
136 | |||
137 | /** | ||
138 | * Iterator over all nodes in a tree. | ||
139 | * | ||
140 | * @param cls Closure. | ||
141 | * @param peer_id Short ID of the peer. | ||
142 | * @param peer_id Short ID of the parent of the peer. | ||
143 | */ | ||
144 | typedef void (*CadetWholeTreeCallback) (void *cls, | ||
145 | GNUNET_PEER_Id peer_id, | ||
146 | GNUNET_PEER_Id parent_id); | ||
147 | |||
148 | /** | ||
149 | * Create a new tunnel tree associated to a tunnel | ||
150 | * | ||
151 | * @param peer A short peer id of the root of the tree | ||
152 | * | ||
153 | * @return A newly allocated and initialized tunnel tree | ||
154 | */ | ||
155 | struct CadetTunnelTree * | ||
156 | tree_new (GNUNET_PEER_Id peer); | ||
157 | |||
158 | |||
159 | /** | ||
160 | * Set the status of a node. | ||
161 | * | ||
162 | * @param tree Tree. | ||
163 | * @param peer A short peer id of the node. | ||
164 | * @param status New status to set. | ||
165 | */ | ||
166 | void | ||
167 | tree_set_status (struct CadetTunnelTree *tree, GNUNET_PEER_Id peer, | ||
168 | enum CadetPeerState status); | ||
169 | |||
170 | |||
171 | /** | ||
172 | * Get the status of a node. | ||
173 | * | ||
174 | * @param tree Tree whose local id we want to now. | ||
175 | * @param peer A short peer id of the node. | ||
176 | * | ||
177 | * @return Short peer id of local peer. | ||
178 | */ | ||
179 | enum CadetPeerState | ||
180 | tree_get_status (struct CadetTunnelTree *tree, GNUNET_PEER_Id peer); | ||
181 | |||
182 | |||
183 | /** | ||
184 | * Get the id of the predecessor of the local node. | ||
185 | * | ||
186 | * @param tree Tree whose local id we want to now. | ||
187 | * | ||
188 | * @return Short peer id of local peer. | ||
189 | */ | ||
190 | GNUNET_PEER_Id | ||
191 | tree_get_predecessor (struct CadetTunnelTree *tree); | ||
192 | |||
193 | |||
194 | /** | ||
195 | * Find the first peer whom to send a packet to go down this path | ||
196 | * | ||
197 | * @param t The tunnel tree to use | ||
198 | * @param peer The peerinfo of the peer we are trying to reach | ||
199 | * | ||
200 | * @return peerinfo of the peer who is the first hop in the tunnel | ||
201 | * NULL on error | ||
202 | */ | ||
203 | struct GNUNET_PeerIdentity * | ||
204 | tree_get_first_hop (struct CadetTunnelTree *t, GNUNET_PEER_Id peer); | ||
205 | |||
206 | |||
207 | /** | ||
208 | * Find the given peer in the tree. | ||
209 | * | ||
210 | * @param tree Tree where to look for the peer. | ||
211 | * @param peer_id Peer to find. | ||
212 | * | ||
213 | * @return Pointer to the node of the peer. NULL if not found. | ||
214 | */ | ||
215 | struct CadetTunnelTreeNode * | ||
216 | tree_find_peer (struct CadetTunnelTree *tree, GNUNET_PEER_Id peer_id); | ||
217 | |||
218 | |||
219 | /** | ||
220 | * Iterate over all children of the local node. | ||
221 | * | ||
222 | * @param tree Tree to use. Must have "me" set. | ||
223 | * @param cb Callback to call over each child. | ||
224 | * @param cb_cls Closure for @c cb. | ||
225 | */ | ||
226 | void | ||
227 | tree_iterate_children (struct CadetTunnelTree *tree, | ||
228 | CadetTreeCallback cb, | ||
229 | void *cb_cls); | ||
230 | |||
231 | |||
232 | /** | ||
233 | * Iterate over all nodes in the tree. | ||
234 | * | ||
235 | * @param tree Tree to use.. | ||
236 | * @param cb Callback to call over each child. | ||
237 | * @param cb_cls Closure for @c cb. | ||
238 | * | ||
239 | * TODO: recursive implementation? (s/heap/stack/g) | ||
240 | */ | ||
241 | void | ||
242 | tree_iterate_all (struct CadetTunnelTree *tree, | ||
243 | CadetWholeTreeCallback cb, | ||
244 | void *cb_cls); | ||
245 | |||
246 | /** | ||
247 | * Count how many children does the local node have in the tree. | ||
248 | * | ||
249 | * @param tree Tree to use. Must have "me" set. | ||
250 | */ | ||
251 | unsigned int | ||
252 | tree_count_children (struct CadetTunnelTree *tree); | ||
253 | |||
254 | |||
255 | /** | ||
256 | * Recusively update the info about what is the first hop to reach the node | ||
257 | * | ||
258 | * @param tree Tree this nodes belongs to. | ||
259 | * @param parent_id Short ID from node form which to start updating. | ||
260 | * @param hop If known, ID of the first hop. | ||
261 | * If not known, NULL to find out and pass on children. | ||
262 | */ | ||
263 | void | ||
264 | tree_update_first_hops (struct CadetTunnelTree *tree, GNUNET_PEER_Id parent_id, | ||
265 | struct GNUNET_PeerIdentity *hop); | ||
266 | |||
267 | /** | ||
268 | * Delete the current path to the peer, including all now unused relays. | ||
269 | * The destination peer is NOT destroyed, it is returned in order to either set | ||
270 | * a new path to it or destroy it explicitly, taking care of it's child nodes. | ||
271 | * | ||
272 | * @param t Tunnel tree where to delete the path from. | ||
273 | * @param peer_id Short ID of the destination peer whose path we want to remove. | ||
274 | * @param cb Callback to use to notify about which peers are going to be | ||
275 | * disconnected. | ||
276 | * @param cbcls Closure for cb. | ||
277 | * | ||
278 | * @return pointer to the pathless node. | ||
279 | * NULL when not found | ||
280 | */ | ||
281 | struct CadetTunnelTreeNode * | ||
282 | tree_del_path (struct CadetTunnelTree *t, GNUNET_PEER_Id peer_id, | ||
283 | CadetTreeCallback cb, void *cbcls); | ||
284 | |||
285 | |||
286 | /** | ||
287 | * Return a newly allocated individual path to reach a peer from the local peer, | ||
288 | * according to the path tree of some tunnel. | ||
289 | * | ||
290 | * @param t Tunnel from which to read the path tree | ||
291 | * @param peer Destination peer to whom we want a path | ||
292 | * | ||
293 | * @return A newly allocated individual path to reach the destination peer. | ||
294 | * Path must be destroyed afterwards. | ||
295 | */ | ||
296 | struct CadetPeerPath * | ||
297 | tree_get_path_to_peer (struct CadetTunnelTree *t, GNUNET_PEER_Id peer); | ||
298 | |||
299 | |||
300 | /** | ||
301 | * Integrate a stand alone path into the tunnel tree. | ||
302 | * | ||
303 | * @param t Tunnel where to add the new path. | ||
304 | * @param p Path to be integrated. | ||
305 | * @param cb Callback to use to notify about peers temporarily disconnecting. | ||
306 | * @param cbcls Closure for cb. | ||
307 | * | ||
308 | * @return GNUNET_OK in case of success. | ||
309 | * GNUNET_SYSERR in case of error. | ||
310 | */ | ||
311 | int | ||
312 | tree_add_path (struct CadetTunnelTree *t, const struct CadetPeerPath *p, | ||
313 | CadetTreeCallback cb, void *cbcls); | ||
314 | |||
315 | |||
316 | /** | ||
317 | * Notifies a tree that a connection it might be using is broken. | ||
318 | * Marks all peers down the paths as disconnected and notifies the client. | ||
319 | * | ||
320 | * @param t Tree to use. | ||
321 | * @param p1 Short id of one of the peers (order unimportant) | ||
322 | * @param p2 Short id of one of the peers (order unimportant) | ||
323 | * @param cb Function to call for every peer that is marked as disconnected. | ||
324 | * @param cbcls Closure for cb. | ||
325 | * | ||
326 | * @return Short ID of the first disconnected peer in the tree. | ||
327 | */ | ||
328 | GNUNET_PEER_Id | ||
329 | tree_notify_connection_broken (struct CadetTunnelTree *t, GNUNET_PEER_Id p1, | ||
330 | GNUNET_PEER_Id p2, CadetTreeCallback cb, | ||
331 | void *cbcls); | ||
332 | |||
333 | |||
334 | /** | ||
335 | * Deletes a peer from a tunnel, liberating all unused resources on the path to | ||
336 | * it. It shouldn't have children, if it has they will be destroyed as well. | ||
337 | * If the tree is not local and no longer has any paths, the root node will be | ||
338 | * destroyed and marked as NULL. | ||
339 | * | ||
340 | * FIXME: dont destroy the root | ||
341 | * | ||
342 | * @param t Tunnel tree to use. | ||
343 | * @param peer Short ID of the peer to remove from the tunnel tree. | ||
344 | * @param cb Callback to notify client of disconnected peers. | ||
345 | * @param cbcls Closure for cb. | ||
346 | * | ||
347 | * @return GNUNET_YES if the tunnel still has nodes | ||
348 | */ | ||
349 | int | ||
350 | tree_del_peer (struct CadetTunnelTree *t, GNUNET_PEER_Id peer, | ||
351 | CadetTreeCallback cb, void *cbcls); | ||
352 | |||
353 | |||
354 | /** | ||
355 | * Get the cost of the path relative to the already built tunnel tree | ||
356 | * | ||
357 | * @param t The tunnel tree to which compare | ||
358 | * @param path The individual path to reach a peer | ||
359 | * | ||
360 | * @return Number of hops to reach destination, UINT_MAX in case the peer is not | ||
361 | * in the path | ||
362 | */ | ||
363 | unsigned int | ||
364 | tree_get_path_cost (struct CadetTunnelTree *t, struct CadetPeerPath *path); | ||
365 | |||
366 | |||
367 | /** | ||
368 | * Print the tree on stderr | ||
369 | * | ||
370 | * @param t The tree | ||
371 | */ | ||
372 | void | ||
373 | tree_debug (struct CadetTunnelTree *t); | ||
374 | |||
375 | |||
376 | /** | ||
377 | * Destroy the whole tree and free all used memory and Peer_Ids | ||
378 | * | ||
379 | * @param t Tree to be destroyed | ||
380 | */ | ||
381 | void | ||
382 | tree_destroy (struct CadetTunnelTree *t); | ||