src/mesh/mesh_tunnel_tree.c

   1 /*
   2      This file is part of GNUnet.
   3      (C) 2001 - 2011 Christian Grothoff (and other contributing authors)
   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., 59 Temple Place - Suite 330,
  18      Boston, MA 02111-1307, USA.
  19 */
  20
  21 /**
  22  * @file mesh/mesh_tunnel_tree.c
  23  * @brief Tunnel tree handling functions
  24  * @author Bartlomiej Polot
  25  */
  26
  27 #include "mesh.h"
  28 #include "mesh_tunnel_tree.h"
  29
  30 #define MESH_TREE_DEBUG GNUNET_YES
  31
  32
  33 /**
  34  * Node of path tree for a tunnel
  35  */
  36 struct MeshTunnelTreeNode
  37 {
  38   /**
  39    * Peer this node describes
  40    */
  41   GNUNET_PEER_Id peer;
  42
  43   /**
  44    * Parent node in the tree
  45    */
  46   struct MeshTunnelTreeNode *parent;
  47
  48   /**
  49    * DLL of siblings
  50    */
  51   struct MeshTunnelTreeNode *next;
  52
  53   /**
  54    * DLL of siblings
  55    */
  56   struct MeshTunnelTreeNode *prev;
  57
  58   /**
  59    * DLL of children
  60    */
  61   struct MeshTunnelTreeNode *children_head;
  62
  63   /**
  64    * DLL of children
  65    */
  66   struct MeshTunnelTreeNode *children_tail;
  67
  68     /**
  69      * Status of the peer in the tunnel
  70      */
  71   enum MeshPeerState status;
  72 };
  73
  74
  75 /**
  76  * Tree to reach all peers in the tunnel
  77  */
  78 struct MeshTunnelTree
  79 {
  80   /**
  81    * Root node of peer tree
  82    */
  83   struct MeshTunnelTreeNode *root;
  84
  85   /**
  86    * Node that represents our position in the tree (for non local tunnels)
  87    */
  88   struct MeshTunnelTreeNode *me;
  89
  90   /**
  91    * DLL of disconneted nodes
  92    */
  93   struct MeshTunnelTreeNode *disconnected_head;
  94
  95   /**
  96    * DLL of disconneted nodes
  97    */
  98   struct MeshTunnelTreeNode *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 lenght 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 MeshPeerPath *
 118 path_new (unsigned int length)
 119 {
 120   struct MeshPeerPath *p;
 121
 122   p = GNUNET_malloc (sizeof (struct MeshPeerPath));
 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 p the path to invert
 136  */
 137 void
 138 path_invert (struct MeshPeerPath *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 p The path to duplicate.
 156  */
 157 struct MeshPeerPath *
 158 path_duplicate (struct MeshPeerPath *path)
 159 {
 160   struct MeshPeerPath *aux;
 161   unsigned int i;
 162
 163   aux = path_new (path->length);
 164   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_id Short ID from 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 MeshTunnelTree *tree,
 181                              struct MeshTunnelTreeNode *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 MeshPeerPath *path)
 195 {
 196   if (NULL == path)
 197     return UINT_MAX;
 198   return path->length;
 199 }
 200
 201
 202 /**
 203  * Get the cost of the path relative to the already built tunnel tree
 204  *
 205  * @param t The tunnel tree to which compare
 206  * @param path The individual path to reach a peer
 207  *
 208  * @return Number of hops to reach destination, UINT_MAX in case the peer is not
 209  * in the path
 210  *
 211  * TODO: remove dummy implementation, look into the tunnel tree
 212  */
 213 unsigned int
 214 path_get_cost (struct MeshTunnelTree *t, struct MeshPeerPath *path)
 215 {
 216   return path_get_length (path);
 217 }
 218
 219
 220 /**
 221  * Destroy the path and free any allocated resources linked to it
 222  *
 223  * @param p the path to destroy
 224  *
 225  * @return GNUNET_OK on success
 226  */
 227 int
 228 path_destroy (struct MeshPeerPath *p)
 229 {
 230   if (NULL == p)
 231     return GNUNET_OK;
 232   GNUNET_PEER_decrement_rcs (p->peers, p->length);
 233   GNUNET_free_non_null (p->peers);
 234   GNUNET_free (p);
 235   return GNUNET_OK;
 236 }
 237
 238
 239
 240 /**
 241  * Allocates and initializes a new node.
 242  * Sets ID and parent of the new node and inserts it in the DLL of the parent
 243  *
 244  * @param parent Node that will be the parent from the new node, NULL for root
 245  * @param peer Short Id of the new node
 246  *
 247  * @return Newly allocated node
 248  */
 249 static struct MeshTunnelTreeNode *
 250 tree_node_new (struct MeshTunnelTreeNode *parent, GNUNET_PEER_Id peer)
 251 {
 252   struct MeshTunnelTreeNode *node;
 253
 254   node = GNUNET_malloc (sizeof (struct MeshTunnelTreeNode));
 255   node->peer = peer;
 256   GNUNET_PEER_change_rc (peer, 1);
 257   node->parent = parent;
 258   if (NULL != parent)
 259     GNUNET_CONTAINER_DLL_insert (parent->children_head, parent->children_tail,
 260                                  node);
 261
 262   return node;
 263 }
 264
 265
 266 /**
 267  * Recursively find the given peer.
 268  *
 269  * @param parent Node where to start looking.
 270  * @param peer Peer to find.
 271  *
 272  * @return Pointer to the node of the peer. NULL if not found.
 273  */
 274 static struct MeshTunnelTreeNode *
 275 tree_node_find_peer (struct MeshTunnelTreeNode *parent, GNUNET_PEER_Id peer_id)
 276 {
 277   struct MeshTunnelTreeNode *n;
 278   struct MeshTunnelTreeNode *r;
 279
 280   if (parent->peer == peer_id)
 281     return parent;
 282   for (n = parent->children_head; NULL != n; n = n->next)
 283   {
 284     r = tree_node_find_peer (n, peer_id);
 285     if (NULL != r)
 286       return r;
 287   }
 288   return NULL;
 289 }
 290
 291
 292 /**
 293  * Recusively update the info about what is the first hop to reach the node
 294  *
 295  * @param tree Tree this nodes belongs to.
 296  * @param parent_id Short ID from node form which to start updating.
 297  * @param hop If known, ID of the first hop.
 298  *            If not known, NULL to find out and pass on children.
 299  */
 300 static void
 301 tree_node_update_first_hops (struct MeshTunnelTree *tree,
 302                              struct MeshTunnelTreeNode *parent,
 303                              struct GNUNET_PeerIdentity *hop)
 304 {
 305   struct GNUNET_PeerIdentity pi;
 306   struct GNUNET_PeerIdentity *copy;
 307   struct GNUNET_PeerIdentity id;
 308   struct MeshTunnelTreeNode *n;
 309
 310 #if MESH_TREE_DEBUG
 311   GNUNET_PEER_resolve (parent->peer, &id);
 312   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "tree:   Finding first hop for %s.\n",
 313               GNUNET_i2s (&id));
 314 #endif
 315   if (NULL == hop)
 316   {
 317     struct MeshTunnelTreeNode *aux;
 318     struct MeshTunnelTreeNode *old;
 319
 320     aux = old = parent;
 321     while (aux != tree->me)
 322     {
 323 #if MESH_TREE_DEBUG
 324       GNUNET_PEER_resolve (aux->peer, &id);
 325       GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "tree:   ... checking %s.\n",
 326                   GNUNET_i2s (&id));
 327 #endif
 328       old = aux;
 329       aux = aux->parent;
 330       GNUNET_assert (NULL != aux);
 331     }
 332 #if MESH_TREE_DEBUG
 333     GNUNET_PEER_resolve (old->peer, &id);
 334     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "tree:   It's %s!\n",
 335                 GNUNET_i2s (&id));
 336 #endif
 337     hop = &pi;
 338     GNUNET_PEER_resolve (old->peer, hop);
 339   }
 340   GNUNET_PEER_resolve (parent->peer, &id);
 341   copy = GNUNET_CONTAINER_multihashmap_get (tree->first_hops, &id.hashPubKey);
 342   if (NULL == copy)
 343     copy = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
 344   *copy = *hop;
 345
 346   (void) GNUNET_CONTAINER_multihashmap_put (tree->first_hops, &id.hashPubKey,
 347                                             copy,
 348                                             GNUNET_CONTAINER_MULTIHASHMAPOPTION_REPLACE);
 349
 350   for (n = parent->children_head; NULL != n; n = n->next)
 351   {
 352     tree_node_update_first_hops (tree, n, hop);
 353   }
 354 }
 355
 356
 357 static void
 358 tree_node_debug (struct MeshTunnelTreeNode *n, uint16_t level)
 359 {
 360   struct MeshTunnelTreeNode *c;
 361   struct GNUNET_PeerIdentity id;;
 362   uint16_t i;
 363
 364   for (i = 0; i < level; i++)
 365     fprintf (stderr, "  ");
 366   if (n->status == MESH_PEER_READY)
 367     fprintf (stderr, "#");
 368   if (n->status == MESH_PEER_SEARCHING)
 369     fprintf (stderr, "+");
 370   if (n->status == MESH_PEER_RELAY)
 371     fprintf (stderr, "-");
 372   if (n->status == MESH_PEER_RECONNECTING)
 373     fprintf (stderr, "*");
 374
 375   GNUNET_PEER_resolve (n->peer, &id);
 376   fprintf (stderr, "%s, [%u, %p] ", GNUNET_i2s (&id), n->peer, n);
 377   if (NULL != n->parent)
 378   {
 379     GNUNET_PEER_resolve (n->parent->peer, &id);
 380     fprintf (stderr, "(-> %s [%u])\n", GNUNET_i2s (&id), n->parent->peer);
 381   }
 382   else
 383     fprintf (stderr, "(root)\n");
 384   for (c = n->children_head; NULL != c; c = c->next)
 385     tree_node_debug (c, level + 1);
 386 }
 387
 388
 389 /**
 390  * Destroys and frees the node and all children
 391  *
 392  * @param n Parent node to be destroyed
 393  */
 394 static void
 395 tree_node_destroy (struct MeshTunnelTreeNode *parent)
 396 {
 397   struct MeshTunnelTreeNode *n;
 398   struct MeshTunnelTreeNode *next;
 399
 400 #if MESH_TREE_DEBUG
 401   struct GNUNET_PeerIdentity id;
 402
 403   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "tree: Destroying node %u\n",
 404               parent->peer);
 405   GNUNET_PEER_resolve (parent->peer, &id);
 406   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "tree:   (%s)\n", GNUNET_i2s (&id));
 407 #endif
 408   n = parent->children_head;
 409   while (NULL != n)
 410   {
 411     next = n->next;
 412     tree_node_destroy (n);
 413     n = next;
 414   }
 415   GNUNET_PEER_change_rc (parent->peer, -1);
 416   if (NULL != parent->parent)
 417     GNUNET_CONTAINER_DLL_remove (parent->parent->children_head,
 418                                  parent->parent->children_tail, parent);
 419   GNUNET_free (parent);
 420 }
 421
 422
 423
 424 /**
 425  * Create a new tunnel tree associated to a tunnel
 426  *
 427  * @param t Tunnel this tree will represent
 428  * @param peer A short peer id of the root of the tree
 429  *
 430  * @return A newly allocated and initialized tunnel tree
 431  */
 432 struct MeshTunnelTree *
 433 tree_new (GNUNET_PEER_Id peer)
 434 {
 435   struct MeshTunnelTree *tree;
 436
 437   tree = GNUNET_malloc (sizeof (struct MeshTunnelTree));
 438   tree->first_hops = GNUNET_CONTAINER_multihashmap_create (32);
 439   tree->root = tree_node_new (NULL, peer);
 440   tree->root->status = MESH_PEER_ROOT;
 441
 442   return tree;
 443 }
 444
 445
 446 /**
 447  * Set the status of a node.
 448  *
 449  * @param tree Tree.
 450  * @param peer A short peer id of local peer.
 451  */
 452 void
 453 tree_set_status (struct MeshTunnelTree *tree, GNUNET_PEER_Id peer,
 454                  enum MeshPeerState status)
 455 {
 456   struct MeshTunnelTreeNode *n;
 457
 458   n = tree_find_peer (tree, peer);
 459   if (NULL == n)
 460     return;
 461   n->status = status;
 462 }
 463
 464
 465 /**
 466  * Get the status of a node.
 467  *
 468  * @param tree Tree whose local id we want to now.
 469  *
 470  * @return Short peer id of local peer.
 471  */
 472 enum MeshPeerState
 473 tree_get_status (struct MeshTunnelTree *tree, GNUNET_PEER_Id peer)
 474 {
 475   struct MeshTunnelTreeNode *n;
 476
 477   n = tree_find_peer (tree, peer);
 478   if (NULL == n)
 479     return MESH_PEER_INVALID;
 480   return n->status;
 481 }
 482
 483
 484 /**
 485  * Get the id of the predecessor of the local node.
 486  *
 487  * @param tree Tree whose local id we want to now.
 488  *
 489  * @return Short peer id of local peer.
 490  */
 491 GNUNET_PEER_Id
 492 tree_get_predecessor (struct MeshTunnelTree *tree)
 493 {
 494   if (NULL != tree->me && NULL != tree->me->parent)
 495     return tree->me->parent->peer;
 496   else
 497     return (GNUNET_PEER_Id) 0;
 498 }
 499
 500
 501 /**
 502  * Find the first peer whom to send a packet to go down this path
 503  *
 504  * @param t The tunnel tree to use
 505  * @param peer The peerinfo of the peer we are trying to reach
 506  *
 507  * @return peerinfo of the peer who is the first hop in the tunnel
 508  *         NULL on error
 509  */
 510 struct GNUNET_PeerIdentity *
 511 tree_get_first_hop (struct MeshTunnelTree *t, GNUNET_PEER_Id peer)
 512 {
 513   struct GNUNET_PeerIdentity id;
 514   struct GNUNET_PeerIdentity *r;
 515
 516   GNUNET_PEER_resolve (peer, &id);
 517   r = GNUNET_CONTAINER_multihashmap_get (t->first_hops, &id.hashPubKey);
 518   if (NULL == r)
 519   {
 520     struct MeshTunnelTreeNode *n;
 521
 522     n = tree_find_peer (t, peer);
 523     if (NULL != t->me && NULL != n)
 524     {
 525       tree_node_update_first_hops (t, n, NULL);
 526       r = GNUNET_CONTAINER_multihashmap_get (t->first_hops, &id.hashPubKey);
 527       GNUNET_assert (NULL != r);
 528     }
 529     else
 530     {
 531       GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
 532                   "Tree structure inconsistent! me: %p, n: %p", t->me, n);
 533       GNUNET_break (0);
 534     }
 535   }
 536
 537   return r;
 538 }
 539
 540
 541 /**
 542  * Find the given peer in the tree.
 543  *
 544  * @param tree Tree where to look for the peer.
 545  * @param peer Peer to find.
 546  *
 547  * @return Pointer to the node of the peer. NULL if not found.
 548  */
 549 struct MeshTunnelTreeNode *
 550 tree_find_peer (struct MeshTunnelTree *tree, GNUNET_PEER_Id peer_id)
 551 {
 552   return tree_node_find_peer (tree->root, peer_id);
 553 }
 554
 555
 556 /**
 557  * Recusively mark peer and children as disconnected, notify client
 558  *
 559  * @param tree Tree this node belongs to
 560  * @param parent Node to be clean, potentially with children
 561  * @param cb Callback to use to notify about disconnected peers.
 562  */
 563 static void
 564 tree_mark_peers_disconnected (struct MeshTunnelTree *tree,
 565                               struct MeshTunnelTreeNode *parent,
 566                               MeshTreeCallback cb, void *cbcls)
 567 {
 568   struct GNUNET_PeerIdentity *pi;
 569   struct GNUNET_PeerIdentity id;
 570   struct MeshTunnelTreeNode *n;
 571
 572   for (n = parent->children_head; NULL != n; n = n->next)
 573   {
 574     tree_mark_peers_disconnected (tree, n, cb, cbcls);
 575   }
 576   if (MESH_PEER_READY == parent->status)
 577   {
 578     if (NULL != cb)
 579       cb (cbcls, parent->peer);
 580     parent->status = MESH_PEER_RECONNECTING;
 581   }
 582
 583   /* Remove and free info about first hop */
 584   GNUNET_PEER_resolve (parent->peer, &id);
 585   pi = GNUNET_CONTAINER_multihashmap_get (tree->first_hops, &id.hashPubKey);
 586   GNUNET_CONTAINER_multihashmap_remove_all (tree->first_hops, &id.hashPubKey);
 587   if (NULL != pi)
 588     GNUNET_free (pi);
 589 }
 590
 591
 592 /**
 593  * Iterate over all children of the local node.
 594  *
 595  * @param tree Tree to use. Must have "me" set.
 596  * @param cb Callback to call over each child.
 597  * @param cls Closure.
 598  */
 599 void
 600 tree_iterate_children (struct MeshTunnelTree *tree, MeshTreeCallback cb,
 601                        void *cls)
 602 {
 603   struct MeshTunnelTreeNode *n;
 604
 605   if (NULL == tree->me)
 606   {
 607     GNUNET_break (0);
 608     return;
 609   }
 610   for (n = tree->me->children_head; NULL != n; n = n->next)
 611   {
 612     cb (cls, n->peer);
 613   }
 614 }
 615
 616
 617 /**
 618  * Recusively update the info about what is the first hop to reach the node
 619  *
 620  * @param tree Tree this nodes belongs to.
 621  * @param parent_id Short ID from node form which to start updating.
 622  * @param hop If known, ID of the first hop.
 623  *            If not known, NULL to find out and pass on children.
 624  */
 625 void
 626 tree_update_first_hops (struct MeshTunnelTree *tree, GNUNET_PEER_Id parent_id,
 627                         struct GNUNET_PeerIdentity *hop)
 628 {
 629   tree_node_update_first_hops (tree, tree_find_peer (tree, parent_id), hop);
 630 }
 631
 632
 633 /**
 634  * Delete the current path to the peer, including all now unused relays.
 635  * The destination peer is NOT destroyed, it is returned in order to either set
 636  * a new path to it or destroy it explicitly, taking care of it's child nodes.
 637  *
 638  * @param t Tunnel tree where to delete the path from.
 639  * @param peer Destination peer whose path we want to remove.
 640  * @param cb Callback to use to notify about disconnected peers.
 641  * @param cbcls Closure for cb.
 642  *
 643  * @return pointer to the pathless node.
 644  *         NULL when not found
 645  */
 646 struct MeshTunnelTreeNode *
 647 tree_del_path (struct MeshTunnelTree *t, GNUNET_PEER_Id peer_id,
 648                MeshTreeCallback cb, void *cbcls)
 649 {
 650   struct MeshTunnelTreeNode *parent;
 651   struct MeshTunnelTreeNode *node;
 652   struct MeshTunnelTreeNode *n;
 653
 654 #if MESH_TREE_DEBUG
 655   struct GNUNET_PeerIdentity id;
 656
 657   GNUNET_PEER_resolve (peer_id, &id);
 658   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "tree:   Deleting path to %s.\n",
 659               GNUNET_i2s (&id));
 660 #endif
 661   if (peer_id == t->root->peer)
 662     return NULL;
 663
 664   for (n = t->disconnected_head; NULL != n; n = n->next)
 665   {
 666     if (n->peer == peer_id)
 667     {
 668       /* Was already pathless, waiting for reconnection */
 669       GNUNET_CONTAINER_DLL_remove (t->disconnected_head, t->disconnected_tail,
 670                                    n);
 671       return n;
 672     }
 673   }
 674   n = tree_find_peer (t, peer_id);
 675   if (NULL == n)
 676     return NULL;
 677   node = n;
 678
 679   parent = n->parent;
 680   GNUNET_CONTAINER_DLL_remove (parent->children_head, parent->children_tail, n);
 681   n->parent = NULL;
 682
 683   while (MESH_PEER_RELAY == parent->status && NULL == parent->children_head)
 684   {
 685 #if MESH_TREE_DEBUG
 686     GNUNET_PEER_resolve (parent->peer, &id);
 687     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "tree:   Deleting node %s.\n",
 688                 GNUNET_i2s (&id));
 689 #endif
 690     n = parent->parent;
 691     tree_node_destroy (parent);
 692     parent = n;
 693   }
 694 #if MESH_TREE_DEBUG
 695   GNUNET_PEER_resolve (parent->peer, &id);
 696   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "tree:   Not deleted peer %s.\n",
 697               GNUNET_i2s (&id));
 698 #endif
 699
 700   tree_mark_peers_disconnected (t, node, cb, cbcls);
 701
 702   return node;
 703 }
 704
 705
 706 /**
 707  * Return a newly allocated individual path to reach a peer from the local peer,
 708  * according to the path tree of some tunnel.
 709  *
 710  * @param t Tunnel from which to read the path tree
 711  * @param peer_info Destination peer to whom we want a path
 712  *
 713  * @return A newly allocated individual path to reach the destination peer.
 714  *         Path must be destroyed afterwards.
 715  */
 716 struct MeshPeerPath *
 717 tree_get_path_to_peer (struct MeshTunnelTree *t, GNUNET_PEER_Id peer)
 718 {
 719   struct MeshTunnelTreeNode *n;
 720   struct MeshPeerPath *p;
 721   GNUNET_PEER_Id myid = t->me->peer;
 722
 723   n = tree_find_peer (t, peer);
 724   if (NULL == n)
 725     return NULL;
 726   p = path_new (0);
 727
 728   /* Building the path (inverted!) */
 729   while (n->peer != myid)
 730   {
 731     GNUNET_array_append (p->peers, p->length, n->peer);
 732     GNUNET_PEER_change_rc (n->peer, 1);
 733     n = n->parent;
 734     if (NULL == n)
 735     {
 736       path_destroy (p);
 737       return NULL;
 738     }
 739   }
 740   GNUNET_array_append (p->peers, p->length, myid);
 741   GNUNET_PEER_change_rc (myid, 1);
 742
 743   path_invert (p);
 744
 745   return p;
 746 }
 747
 748
 749
 750 /**
 751  * Integrate a stand alone path into the tunnel tree.
 752  * If the peer toward which the new path is already in the tree, the peer
 753  * and its children will be maked as disconnected and the callback
 754  * will be called on each one of them. They will be maked as online only after
 755  * receiving a PATH ACK for the new path for each one of them, so the caller
 756  * should take care of sending a new CREATE PATH message for each disconnected
 757  * peer.
 758  *
 759  * @param t Tunnel where to add the new path.
 760  * @param p Path to be integrated.
 761  * @param cb Callback to use to notify about peers temporarily disconnecting.
 762  * @param cbcls Closure for cb.
 763  *
 764  * @return GNUNET_OK in case of success.
 765  *         GNUNET_SYSERR in case of error.
 766  *
 767  * TODO: optimize
 768  * - go backwards on path looking for each peer in the present tree
 769  * - do not disconnect peers until new path is created & connected
 770  */
 771 int
 772 tree_add_path (struct MeshTunnelTree *t, const struct MeshPeerPath *p,
 773                MeshTreeCallback cb, void *cbcls)
 774 {
 775   struct MeshTunnelTreeNode *parent;
 776   struct MeshTunnelTreeNode *oldnode;
 777   struct MeshTunnelTreeNode *n;
 778   struct MeshTunnelTreeNode *c;
 779   struct GNUNET_PeerIdentity id;
 780   int me;
 781   unsigned int i;
 782
 783 #if MESH_TREE_DEBUG
 784   GNUNET_PEER_resolve (p->peers[p->length - 1], &id);
 785   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 786               "tree:   Adding path [%u] towards peer %s.\n", p->length,
 787               GNUNET_i2s (&id));
 788 #endif
 789
 790   GNUNET_assert (0 != p->length);
 791   parent = n = t->root;
 792   if (n->peer != p->peers[0])
 793   {
 794     GNUNET_break (0);
 795     return GNUNET_SYSERR;
 796   }
 797   if (1 == p->length)
 798     return GNUNET_OK;
 799   oldnode = tree_del_path (t, p->peers[p->length - 1], cb, cbcls);
 800   /* Look for the first node that is not already present in the tree
 801    *
 802    * Assuming that the tree is somewhat balanced, O(log n * log N).
 803    * - Length of the path is expected to be log N (size of whole network).
 804    * - Each level of the tree is expected to have log n children (size of tree).
 805    */
 806   me = t->root->peer == 1 ? 0 : -1;
 807   for (i = 1; i < p->length; i++)
 808   {
 809 #if MESH_TREE_DEBUG
 810     GNUNET_PEER_resolve (p->peers[i], &id);
 811     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "tree:   Looking for peer %s.\n",
 812                 GNUNET_i2s (&id));
 813 #endif
 814     parent = n;
 815     if (p->peers[i] == 1)
 816       me = i;
 817     for (c = n->children_head; NULL != c; c = c->next)
 818     {
 819       if (c->peer == p->peers[i])
 820       {
 821 #if MESH_TREE_DEBUG
 822         GNUNET_PEER_resolve (parent->peer, &id);
 823         GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 824                     "tree:   Found in children of %s.\n", GNUNET_i2s (&id));
 825 #endif
 826         n = c;
 827         break;
 828       }
 829     }
 830     /*  If we couldn't find a child equal to path[i], we have reached the end
 831      * of the common path. */
 832     if (parent == n)
 833       break;
 834   }
 835 #if MESH_TREE_DEBUG
 836   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "tree:   All childen visited.\n");
 837 #endif
 838   /* Add the rest of the path as a branch from parent. */
 839   while (i < p->length)
 840   {
 841 #if MESH_TREE_DEBUG
 842     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "tree:   Adding peer %u to %u.\n",
 843                 p->peers[i], parent->peer);
 844     GNUNET_PEER_resolve (p->peers[i], &id);
 845     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "tree:   Adding peer %s.\n",
 846                 GNUNET_i2s (&id));
 847     GNUNET_PEER_resolve (parent->peer, &id);
 848     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "tree:     to %s.\n",
 849                 GNUNET_i2s (&id));
 850 #endif
 851
 852     if (i == p->length - 1 && NULL != oldnode)
 853     {
 854 #if MESH_TREE_DEBUG
 855       GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 856                   "tree:   Putting old node into place.\n");
 857 #endif
 858       oldnode->parent = parent;
 859       GNUNET_CONTAINER_DLL_insert (parent->children_head, parent->children_tail,
 860                                    oldnode);
 861       tree_node_update_first_hops (t, oldnode, NULL);
 862       n = oldnode;
 863     }
 864     else
 865     {
 866 #if MESH_TREE_DEBUG
 867       GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "tree:   Creating new node.\n");
 868 #endif
 869       n = tree_node_new (parent, p->peers[i]);
 870       n->status = MESH_PEER_RELAY;
 871       if (n->peer == 1)
 872       {
 873         t->me = n;
 874         me = i;
 875       }
 876     }
 877     i++;
 878     parent = n;
 879   }
 880   n->status = MESH_PEER_SEARCHING;
 881
 882   GNUNET_break (-1 != me);
 883
 884   /* Add info about first hop into hashmap. */
 885   if (-1 != me && me < p->length - 1)
 886   {
 887 #if MESH_TREE_DEBUG
 888     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 889                 "MESH:   finding first hop (own pos %d/%u)\n", me,
 890                 p->length - 1);
 891 #endif
 892     GNUNET_PEER_resolve (p->peers[me + 1], &id);
 893     tree_update_first_hops (t, p->peers[me + 1], &id);
 894   }
 895 #if MESH_TREE_DEBUG
 896   else
 897   {
 898     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 899                 "MESH:   was last in path, not updating first hops (%d/%u)\n",
 900                 me, p->length - 1);
 901   }
 902   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "tree:   New node added.\n");
 903 #endif
 904   return GNUNET_OK;
 905 }
 906
 907
 908 /**
 909  * Notifies a tree that a connection it might be using is broken.
 910  * Marks all peers down the paths as disconnected and notifies the client.
 911  *
 912  * @param t Tree to use.
 913  * @param p1 Short id of one of the peers (order unimportant)
 914  * @param p2 Short id of one of the peers (order unimportant)
 915  * @param cb Function to call for every peer that is marked as disconnected.
 916  * @param cbcls Closure for cb.
 917  *
 918  * @return Short ID of the first disconnected peer in the tree.
 919  */
 920 GNUNET_PEER_Id
 921 tree_notify_connection_broken (struct MeshTunnelTree *t, GNUNET_PEER_Id p1,
 922                                GNUNET_PEER_Id p2, MeshTreeCallback cb,
 923                                void *cbcls)
 924 {
 925   struct MeshTunnelTreeNode *n;
 926   struct MeshTunnelTreeNode *c;
 927
 928   n = tree_find_peer (t, p1);
 929   if (NULL == n)
 930     return 0;
 931   if (NULL != n->parent && n->parent->peer == p2)
 932   {
 933     tree_mark_peers_disconnected (t, n, cb, cbcls);
 934     GNUNET_CONTAINER_DLL_remove (n->parent->children_head,
 935                                  n->parent->children_tail, n);
 936     GNUNET_CONTAINER_DLL_insert (t->disconnected_head, t->disconnected_tail, n);
 937     return p1;
 938   }
 939   for (c = n->children_head; NULL != c; c = c->next)
 940   {
 941     if (c->peer == p2)
 942     {
 943       tree_mark_peers_disconnected (t, c, cb, cbcls);
 944       GNUNET_CONTAINER_DLL_remove (n->children_head, n->children_tail, c);
 945       GNUNET_CONTAINER_DLL_insert (t->disconnected_head, t->disconnected_tail,
 946                                    c);
 947       return p2;
 948     }
 949   }
 950   return 0;
 951 }
 952
 953
 954 /**
 955  * Deletes a peer from a tunnel, liberating all unused resources on the path to
 956  * it. It shouldn't have children, if it has they will be destroyed as well.
 957  * If the tree is not local and no longer has any paths, the root node will be
 958  * destroyed and marked as NULL.
 959  *
 960  * @param t Tunnel tree to use.
 961  * @param peer Short ID of the peer to remove from the tunnel tree.
 962  * @param cb Callback to notify client of disconnected peers.
 963  * @param cbcls Closure for cb.
 964  *
 965  * @return GNUNET_OK or GNUNET_SYSERR
 966  */
 967 int
 968 tree_del_peer (struct MeshTunnelTree *t, GNUNET_PEER_Id peer,
 969                MeshTreeCallback cb, void *cbcls)
 970 {
 971   struct MeshTunnelTreeNode *n;
 972
 973   n = tree_del_path (t, peer, cb, cbcls);
 974   if (NULL == n)
 975   {
 976     GNUNET_break (0);
 977     return GNUNET_YES;
 978   }
 979   GNUNET_break_op (NULL == n->children_head);
 980   tree_node_destroy (n);
 981   if (NULL == t->root->children_head && t->me != t->root)
 982   {
 983     tree_node_destroy (t->root);
 984     t->root = NULL;
 985     return GNUNET_NO;
 986   }
 987   return GNUNET_YES;
 988 }
 989
 990
 991 /**
 992  * Print the tree on stderr
 993  *
 994  * @param t The tree
 995  */
 996 void
 997 tree_debug (struct MeshTunnelTree *t)
 998 {
 999   tree_node_debug (t->root, 0);
1000 }
1001
1002
1003 /**
1004  * Iterator over hash map peer entries and frees all data in it.
1005  * Used prior to destroying a hashmap. Makes you miss anonymous functions in C.
1006  *
1007  * @param cls closure
1008  * @param key current key code (will no longer contain valid data!!)
1009  * @param value value in the hash map (treated as void *)
1010  * @return GNUNET_YES if we should continue to iterate, GNUNET_NO if not.
1011  */
1012 static int
1013 iterate_free (void *cls, const GNUNET_HashCode * key, void *value)
1014 {
1015   GNUNET_free (value);
1016   return GNUNET_YES;
1017 }
1018
1019
1020 /**
1021  * Destroy the whole tree and free all used memory and Peer_Ids
1022  *
1023  * @param t Tree to be destroyed
1024  */
1025 void
1026 tree_destroy (struct MeshTunnelTree *t)
1027 {
1028 #if MESH_TREE_DEBUG
1029   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "tree: Destroying tree\n");
1030 #endif
1031   tree_node_destroy (t->root);
1032   GNUNET_CONTAINER_multihashmap_iterate (t->first_hops, &iterate_free, NULL);
1033   GNUNET_CONTAINER_multihashmap_destroy (t->first_hops);
1034   GNUNET_free (t);
1035 }