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  * Create a new path
  35  *
  36  * @param lenght How many hops will the path have.
  37  *
  38  * @return A newly allocated path with a peer array of the specified length.
  39  */
  40 struct MeshPeerPath *
  41 path_new (unsigned int length)
  42 {
  43   struct MeshPeerPath *p;
  44
  45   p = GNUNET_malloc (sizeof(struct MeshPeerPath));
  46   if (length > 0)
  47   {
  48     p->length = length;
  49     p->peers = GNUNET_malloc (length * sizeof(GNUNET_PEER_Id));
  50   }
  51   return p;
  52 }
  53
  54
  55 /**
  56  * Invert the path
  57  *
  58  * @param p the path to invert
  59  */
  60 void
  61 path_invert (struct MeshPeerPath *path)
  62 {
  63   GNUNET_PEER_Id aux;
  64   unsigned int i;
  65
  66   for (i = 0; i < path->length / 2; i++)
  67   {
  68     aux = path->peers[i];
  69     path->peers[i] = path->peers[path->length - i - 1];
  70     path->peers[path->length - i - 1] = aux;
  71   }
  72 }
  73
  74
  75 /**
  76  * Duplicate a path, incrementing short peer's rc.
  77  *
  78  * @param p The path to duplicate.
  79  */
  80 struct MeshPeerPath *
  81 path_duplicate (struct MeshPeerPath *path)
  82 {
  83   struct MeshPeerPath *aux;
  84   unsigned int i;
  85
  86   aux = path_new(path->length);
  87   memcpy (aux->peers, path->peers, path->length * sizeof(GNUNET_PEER_Id));
  88   for (i = 0; i < path->length; i++)
  89     GNUNET_PEER_change_rc(path->peers[i], 1);
  90   return aux;
  91 }
  92
  93
  94 /**
  95  * Find the first peer whom to send a packet to go down this path
  96  *
  97  * @param t The tunnel tree to use
  98  * @param peer The peerinfo of the peer we are trying to reach
  99  *
 100  * @return peerinfo of the peer who is the first hop in the tunnel
 101  *         NULL on error
 102  */
 103 struct GNUNET_PeerIdentity *
 104 path_get_first_hop (struct MeshTunnelTree *t, GNUNET_PEER_Id peer)
 105 {
 106   struct GNUNET_PeerIdentity id;
 107   struct GNUNET_PeerIdentity *r;
 108
 109   GNUNET_PEER_resolve (peer, &id);
 110   r = GNUNET_CONTAINER_multihashmap_get (t->first_hops, &id.hashPubKey);
 111   if (NULL == r)
 112   {
 113     struct MeshTunnelTreeNode *n;
 114
 115     n = tree_find_peer(t->root, peer);
 116     if (NULL != t->me && NULL != n)
 117     {
 118       tree_update_first_hops(t, n, NULL);
 119       r = GNUNET_CONTAINER_multihashmap_get (t->first_hops, &id.hashPubKey);
 120       GNUNET_assert (NULL != r);
 121     }
 122     else
 123     {
 124       GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
 125                   "Tree structure inconsistent! me: %p, n: %p",
 126                   t->me, n);
 127       GNUNET_break (0);
 128     }
 129   }
 130
 131   return r;
 132 }
 133
 134
 135 /**
 136  * Get the length of a path
 137  *
 138  * @param path The path to measure, with the local peer at any point of it
 139  *
 140  * @return Number of hops to reach destination
 141  *         UINT_MAX in case the peer is not in the path
 142  */
 143 unsigned int
 144 path_get_length (struct MeshPeerPath *path)
 145 {
 146   if (NULL == path)
 147     return UINT_MAX;
 148   return path->length;
 149 }
 150
 151
 152 /**
 153  * Get the cost of the path relative to the already built tunnel tree
 154  *
 155  * @param t The tunnel tree to which compare
 156  * @param path The individual path to reach a peer
 157  *
 158  * @return Number of hops to reach destination, UINT_MAX in case the peer is not
 159  * in the path
 160  *
 161  * TODO: remove dummy implementation, look into the tunnel tree
 162  */
 163 unsigned int
 164 path_get_cost (struct MeshTunnelTree *t, struct MeshPeerPath *path)
 165 {
 166   return path_get_length (path);
 167 }
 168
 169
 170 /**
 171  * Destroy the path and free any allocated resources linked to it
 172  *
 173  * @param p the path to destroy
 174  *
 175  * @return GNUNET_OK on success
 176  */
 177 int
 178 path_destroy (struct MeshPeerPath *p)
 179 {
 180   if (NULL == p)
 181     return GNUNET_OK;
 182   GNUNET_PEER_decrement_rcs (p->peers, p->length);
 183   GNUNET_free (p->peers);
 184   GNUNET_free (p);
 185   return GNUNET_OK;
 186 }
 187
 188
 189
 190 /**
 191  * Allocates and initializes a new node.
 192  * Sets ID and parent of the new node and inserts it in the DLL of the parent
 193  *
 194  * @param parent Node that will be the parent from the new node, NULL for root
 195  * @param peer Short Id of the new node
 196  *
 197  * @return Newly allocated node
 198  */
 199 static struct MeshTunnelTreeNode *
 200 tree_node_new(struct MeshTunnelTreeNode *parent, GNUNET_PEER_Id peer)
 201 {
 202   struct MeshTunnelTreeNode *node;
 203
 204   node = GNUNET_malloc(sizeof(struct MeshTunnelTreeNode));
 205   node->peer = peer;
 206   GNUNET_PEER_change_rc(peer, 1);
 207   node->parent = parent;
 208   if (NULL != parent)
 209     GNUNET_CONTAINER_DLL_insert(parent->children_head,
 210                                 parent->children_tail,
 211                                 node);
 212
 213   return node;
 214 }
 215
 216
 217 static void
 218 tree_node_debug(struct MeshTunnelTreeNode *n, uint16_t level)
 219 {
 220   struct MeshTunnelTreeNode *c;
 221   struct GNUNET_PeerIdentity id;;
 222   uint16_t i;
 223
 224   for (i = 0; i < level; i++)
 225     fprintf(stderr, "  ");
 226   if (n->status == MESH_PEER_READY)
 227     fprintf(stderr, "#");
 228   if (n->status == MESH_PEER_SEARCHING)
 229     fprintf(stderr, "+");
 230   if (n->status == MESH_PEER_RELAY)
 231     fprintf(stderr, "-");
 232   if (n->status == MESH_PEER_RECONNECTING)
 233     fprintf(stderr, "*");
 234
 235   GNUNET_PEER_resolve(n->peer, &id);
 236   fprintf(stderr, "%s, [%u, %p] ", GNUNET_i2s (&id), n->peer, n);
 237   if (NULL != n->parent)
 238   {
 239     GNUNET_PEER_resolve(n->parent->peer, &id);
 240     fprintf(stderr, "(-> %s [%u])\n", GNUNET_i2s(&id), n->parent->peer);
 241   }
 242   else
 243     fprintf(stderr, "(root)\n");
 244   for (c = n->children_head; NULL != c; c = c->next)
 245     tree_node_debug(c, level + 1);
 246 }
 247
 248
 249 /**
 250  * Destroys and frees the node and all children
 251  *
 252  * @param n Parent node to be destroyed
 253  */
 254 static void
 255 tree_node_destroy (struct MeshTunnelTreeNode *parent)
 256 {
 257   struct MeshTunnelTreeNode *n;
 258   struct MeshTunnelTreeNode *next;
 259 #if MESH_TREE_DEBUG
 260   struct GNUNET_PeerIdentity id;
 261
 262   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 263               "tree: Destroying node %u\n",
 264               parent->peer);
 265   GNUNET_PEER_resolve (parent->peer, &id);
 266   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 267               "tree:   (%s)\n",
 268               GNUNET_i2s (&id));
 269 #endif
 270   n = parent->children_head;
 271   while (NULL != n)
 272   {
 273     next = n->next;
 274     tree_node_destroy(n);
 275     n = next;
 276   }
 277   GNUNET_PEER_change_rc(parent->peer, -1);
 278   if (NULL != parent->parent)
 279     GNUNET_CONTAINER_DLL_remove(parent->parent->children_head,
 280                                 parent->parent->children_tail,
 281                                 parent);
 282   GNUNET_free(parent);
 283 }
 284
 285
 286
 287 /**
 288  * Create a new tunnel tree associated to a tunnel
 289  *
 290  * @param t Tunnel this tree will represent
 291  * @param peer A short peer id of the root of the tree
 292  *
 293  * @return A newly allocated and initialized tunnel tree
 294  */
 295 struct MeshTunnelTree *
 296 tree_new (struct MeshTunnel *t, GNUNET_PEER_Id peer)
 297 {
 298   struct MeshTunnelTree *tree;
 299
 300   tree = GNUNET_malloc(sizeof (struct MeshTunnelTree));
 301   tree->first_hops = GNUNET_CONTAINER_multihashmap_create(32);
 302   tree->root = tree_node_new(NULL, peer);
 303   tree->root->status = MESH_PEER_ROOT;
 304   tree->t = t;
 305   tree->root->t = t;
 306
 307   return tree;
 308 }
 309
 310
 311 /**
 312  * Recursively find the given peer in the tree.
 313  *
 314  * @param t Tunnel where to look for the peer.
 315  * @param peer Peer to find
 316  *
 317  * @return Pointer to the node of the peer. NULL if not found.
 318  */
 319 struct MeshTunnelTreeNode *
 320 tree_find_peer (struct MeshTunnelTreeNode *parent, GNUNET_PEER_Id peer_id)
 321 {
 322   struct MeshTunnelTreeNode *n;
 323   struct MeshTunnelTreeNode *r;
 324
 325   if (parent->peer == peer_id)
 326     return parent;
 327   for (n = parent->children_head; NULL != n; n = n->next)
 328   {
 329     r = tree_find_peer (n, peer_id);
 330     if (NULL != r)
 331       return r;
 332   }
 333   return NULL;
 334 }
 335
 336
 337 /**
 338  * Recusively mark peer and children as disconnected, notify client
 339  *
 340  * @param tree Tree this node belongs to
 341  * @param parent Node to be clean, potentially with children
 342  * @param cb Callback to use to notify about disconnected peers.
 343  */
 344 static void
 345 tree_mark_peers_disconnected (struct MeshTunnelTree *tree,
 346                               struct MeshTunnelTreeNode *parent,
 347                               MeshNodeDisconnectCB cb)
 348 {
 349   struct GNUNET_PeerIdentity *pi;
 350   struct GNUNET_PeerIdentity id;
 351   struct MeshTunnelTreeNode *n;
 352
 353   for (n = parent->children_head; NULL != n; n = n->next)
 354   {
 355     tree_mark_peers_disconnected (tree, n, cb);
 356   }
 357   if (MESH_PEER_READY == parent->status)
 358   {
 359     if (NULL != cb)
 360       cb (parent);
 361     parent->status = MESH_PEER_RECONNECTING;
 362   }
 363
 364   /* Remove and free info about first hop */
 365   GNUNET_PEER_resolve(parent->peer, &id);
 366   pi = GNUNET_CONTAINER_multihashmap_get(tree->first_hops, &id.hashPubKey);
 367   GNUNET_CONTAINER_multihashmap_remove_all(tree->first_hops, &id.hashPubKey);
 368   if (NULL != pi)
 369     GNUNET_free(pi);
 370 }
 371
 372
 373 /**
 374  * Recusively update the info about what is the first hop to reach the node
 375  *
 376  * @param tree Tree this nodes belongs to
 377  * @param parent Node to be start updating
 378  * @param hop If known, ID of the first hop.
 379  *            If not known, NULL to find out and pass on children.
 380  */
 381 void
 382 tree_update_first_hops (struct MeshTunnelTree *tree,
 383                         struct MeshTunnelTreeNode *parent,
 384                         struct GNUNET_PeerIdentity *hop)
 385 {
 386   struct GNUNET_PeerIdentity pi;
 387   struct GNUNET_PeerIdentity *copy;
 388   struct GNUNET_PeerIdentity id;
 389   struct MeshTunnelTreeNode *n;
 390
 391 #if MESH_TREE_DEBUG
 392   GNUNET_PEER_resolve(parent->peer, &id);
 393   GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 394           "tree:   Finding first hop for %s.\n",
 395           GNUNET_i2s (&id));
 396 #endif
 397   if (NULL == hop)
 398   {
 399     struct MeshTunnelTreeNode *aux;
 400     struct MeshTunnelTreeNode *old;
 401
 402     aux = old = parent;
 403     while (aux != tree->me)
 404     {
 405 #if MESH_TREE_DEBUG
 406       GNUNET_PEER_resolve(old->peer, &id);
 407       GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 408              "tree:   ... its not %s.\n",
 409              GNUNET_i2s (&id));
 410 #endif
 411       old = aux;
 412       aux = aux->parent;
 413       GNUNET_assert(NULL != aux);
 414     }
 415 #if MESH_TREE_DEBUG
 416     GNUNET_PEER_resolve(old->peer, &id);
 417     GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 418                "tree:   It's %s!\n",
 419                GNUNET_i2s (&id));
 420 #endif
 421     hop = &pi;
 422     GNUNET_PEER_resolve(old->peer, hop);
 423   }
 424   GNUNET_PEER_resolve(parent->peer, &id);
 425   copy = GNUNET_CONTAINER_multihashmap_get (tree->first_hops, &id.hashPubKey);
 426   if (NULL == copy)
 427     copy = GNUNET_malloc(sizeof(struct GNUNET_PeerIdentity));
 428   *copy = *hop;
 429
 430   (void) GNUNET_CONTAINER_multihashmap_put(
 431     tree->first_hops,
 432     &id.hashPubKey,
 433     copy,
 434     GNUNET_CONTAINER_MULTIHASHMAPOPTION_REPLACE);
 435
 436   for (n = parent->children_head; NULL != n; n = n->next)
 437   {
 438     tree_update_first_hops (tree, n, hop);
 439   }
 440 }
 441
 442
 443 /**
 444  * Delete the current path to the peer, including all now unused relays.
 445  * The destination peer is NOT destroyed, it is returned in order to either set
 446  * a new path to it or destroy it explicitly, taking care of it's child nodes.
 447  *
 448  * @param t Tunnel tree where to delete the path from.
 449  * @param peer Destination peer whose path we want to remove.
 450  * @param cb Callback to use to notify about disconnected peers.
 451  *
 452  * @return pointer to the pathless node.
 453  *         NULL when not found
 454  */
 455 struct MeshTunnelTreeNode *
 456 tree_del_path (struct MeshTunnelTree *t,
 457                GNUNET_PEER_Id peer_id,
 458                MeshNodeDisconnectCB cb)
 459 {
 460   struct MeshTunnelTreeNode *parent;
 461   struct MeshTunnelTreeNode *node;
 462   struct MeshTunnelTreeNode *n;
 463
 464 #if MESH_TREE_DEBUG
 465   struct GNUNET_PeerIdentity id;
 466   GNUNET_PEER_resolve(peer_id, &id);
 467   GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 468           "tree:   Deleting path to %s.\n",
 469           GNUNET_i2s (&id));
 470 #endif
 471   if (peer_id == t->root->peer)
 472     return NULL;
 473
 474   for (n = t->disconnected_head; NULL != n; n = n->next)
 475   {
 476     if (n->peer == peer_id)
 477     {
 478       /* Was already pathless, waiting for reconnection */
 479       GNUNET_CONTAINER_DLL_remove (t->disconnected_head,
 480                                    t->disconnected_tail,
 481                                    n);
 482       return n;
 483     }
 484   }
 485   n = tree_find_peer (t->root, peer_id);
 486   if (NULL == n)
 487     return NULL;
 488   node = n;
 489
 490   parent = n->parent;
 491   GNUNET_CONTAINER_DLL_remove(parent->children_head, parent->children_tail, n);
 492   n->parent = NULL;
 493
 494   while (MESH_PEER_RELAY == parent->status && NULL == parent->children_head)
 495   {
 496 #if MESH_TREE_DEBUG
 497     GNUNET_PEER_resolve(parent->peer, &id);
 498     GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 499               "tree:   Deleting node %s.\n",
 500               GNUNET_i2s (&id));
 501 #endif
 502     n = parent->parent;
 503     tree_node_destroy(parent);
 504     parent = n;
 505   }
 506 #if MESH_TREE_DEBUG
 507   GNUNET_PEER_resolve(parent->peer, &id);
 508   GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 509              "tree:   Not deleted peer %s.\n",
 510              GNUNET_i2s (&id));
 511 #endif
 512
 513   tree_mark_peers_disconnected (t, node, cb);
 514
 515   return node;
 516 }
 517
 518
 519 /**
 520  * Return a newly allocated individual path to reach a peer from the local peer,
 521  * according to the path tree of some tunnel.
 522  *
 523  * @param t Tunnel from which to read the path tree
 524  * @param peer_info Destination peer to whom we want a path
 525  *
 526  * @return A newly allocated individual path to reach the destination peer.
 527  *         Path must be destroyed afterwards.
 528  */
 529 struct MeshPeerPath *
 530 tree_get_path_to_peer(struct MeshTunnelTree *t, GNUNET_PEER_Id peer)
 531 {
 532   struct MeshTunnelTreeNode *n;
 533   struct MeshPeerPath *p;
 534   GNUNET_PEER_Id myid = t->me->peer;
 535
 536   n = tree_find_peer(t->me, peer);
 537   if (NULL == n)
 538     return NULL;
 539   p = path_new(0);
 540
 541   /* Building the path (inverted!) */
 542   while (n->peer != myid)
 543   {
 544     GNUNET_array_append(p->peers, p->length, n->peer);
 545     GNUNET_PEER_change_rc(n->peer, 1);
 546     n = n->parent;
 547     GNUNET_assert(NULL != n);
 548   }
 549   GNUNET_array_append(p->peers, p->length, myid);
 550   GNUNET_PEER_change_rc(myid, 1);
 551
 552   path_invert(p);
 553
 554   return p;
 555 }
 556
 557
 558
 559 /**
 560  * Integrate a stand alone path into the tunnel tree.
 561  * If the peer toward which the new path is already in the tree, the peer
 562  * and its children will be maked as disconnected and the callback
 563  * will be called on each one of them. They will be maked as online only after
 564  * receiving a PATH ACK for the new path for each one of them, so the caller
 565  * should take care of sending a new CREATE PATH message for each disconnected
 566  * peer.
 567  *
 568  * @param t Tunnel where to add the new path.
 569  * @param p Path to be integrated.
 570  * @param cb Callback to use to notify about peers temporarily disconnecting
 571  *
 572  * @return GNUNET_OK in case of success.
 573  *         GNUNET_SYSERR in case of error.
 574  *
 575  * TODO: optimize
 576  * - go backwards on path looking for each peer in the present tree
 577  * - do not disconnect peers until new path is created & connected
 578  */
 579 int
 580 tree_add_path (struct MeshTunnelTree *t,
 581                const struct MeshPeerPath *p,
 582                MeshNodeDisconnectCB cb)
 583 {
 584   struct MeshTunnelTreeNode *parent;
 585   struct MeshTunnelTreeNode *oldnode;
 586   struct MeshTunnelTreeNode *n;
 587   struct MeshTunnelTreeNode *c;
 588   struct GNUNET_PeerIdentity id;
 589   GNUNET_PEER_Id myid;
 590   int me;
 591   unsigned int i;
 592
 593 #if MESH_TREE_DEBUG
 594   GNUNET_PEER_resolve(p->peers[p->length - 1], &id);
 595   GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 596              "tree:   Adding path [%u] towards peer %s.\n",
 597             p->length,
 598             GNUNET_i2s (&id));
 599 #endif
 600
 601   if (NULL != t->me)
 602     myid = t->me->peer;
 603   else
 604     myid = 0;
 605   GNUNET_assert(0 != p->length);
 606   parent = n = t->root;
 607   if (n->peer != p->peers[0])
 608   {
 609     GNUNET_break (0);
 610     return GNUNET_SYSERR;
 611   }
 612   if (1 == p->length)
 613     return GNUNET_OK;
 614   oldnode = tree_del_path (t, p->peers[p->length - 1], cb);
 615   /* Look for the first node that is not already present in the tree
 616    *
 617    * Assuming that the tree is somewhat balanced, O(log n * log N).
 618    * - Length of the path is expected to be log N (size of whole network).
 619    * - Each level of the tree is expected to have log n children (size of tree).
 620    */
 621   me = t->root->peer == myid ? 0 : -1;
 622   for (i = 1; i < p->length; i++)
 623   {
 624 #if MESH_TREE_DEBUG
 625     GNUNET_PEER_resolve(p->peers[i], &id);
 626     GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 627                "tree:   Looking for peer %s.\n",
 628                GNUNET_i2s (&id));
 629 #endif
 630     parent = n;
 631     if (p->peers[i] == myid)
 632       me = i;
 633     for (c = n->children_head; NULL != c; c = c->next)
 634     {
 635       if (c->peer == p->peers[i])
 636       {
 637 #if MESH_TREE_DEBUG
 638         GNUNET_PEER_resolve(parent->peer, &id);
 639         GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 640                    "tree:   Found in children of %s.\n",
 641                    GNUNET_i2s (&id));
 642 #endif
 643         n = c;
 644         break;
 645       }
 646     }
 647     /*  If we couldn't find a child equal to path[i], we have reached the end
 648      * of the common path. */
 649     if (parent == n)
 650       break;
 651   }
 652 #if MESH_TREE_DEBUG
 653   GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 654              "tree:   All childen visited.\n");
 655 #endif
 656   /* Add the rest of the path as a branch from parent. */
 657   while (i < p->length)
 658   {
 659 #if MESH_TREE_DEBUG
 660     GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 661                "tree:   Adding peer %u to %u.\n",
 662                p->peers[i], parent->peer);
 663     GNUNET_PEER_resolve(p->peers[i], &id);
 664     GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 665                "tree:   Adding peer %s.\n",
 666                GNUNET_i2s (&id));
 667     GNUNET_PEER_resolve(parent->peer, &id);
 668     GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 669                "tree:     to %s.\n",
 670                GNUNET_i2s (&id));
 671 #endif
 672
 673     if (i == p->length - 1 && NULL != oldnode)
 674     {
 675 #if MESH_TREE_DEBUG
 676       GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 677                  "tree:   Putting old node into place.\n");
 678 #endif
 679       oldnode->parent = parent;
 680       GNUNET_CONTAINER_DLL_insert(parent->children_head,
 681                                   parent->children_tail,
 682                                   oldnode);
 683       tree_update_first_hops (t, oldnode, NULL);
 684       n = oldnode;
 685     }
 686     else
 687     {
 688 #if MESH_TREE_DEBUG
 689       GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "tree:   Creating new node.\n");
 690 #endif
 691       n = tree_node_new(parent, p->peers[i]);
 692       n->t = t->t;
 693       n->status = MESH_PEER_RELAY;
 694       if (n->peer == myid)
 695         t->me = n;
 696     }
 697     i++;
 698     parent = n;
 699   }
 700   n->status = MESH_PEER_SEARCHING;
 701
 702   /* Add info about first hop into hashmap. */
 703   if (-1 != me && me < p->length - 1)
 704   {
 705 #if MESH_TREE_DEBUG
 706     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 707                 "MESH:   finding first hop (own pos %d/%u)\n",
 708                 me, p->length - 1);
 709 #endif
 710     GNUNET_PEER_resolve (p->peers[me + 1], &id);
 711     tree_update_first_hops(t,
 712                            tree_find_peer(t->root, p->peers[p->length - 1]),
 713                            &id);
 714   }
 715 #if MESH_TREE_DEBUG
 716   GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "tree:   New node added.\n");
 717 #endif
 718   return GNUNET_OK;
 719 }
 720
 721
 722 /**
 723  * Notifies a tree that a connection it might be using is broken.
 724  * Marks all peers down the paths as disconnected and notifies the client.
 725  *
 726  * @param t Tree to use.
 727  * @param p1 Short id of one of the peers (order unimportant)
 728  * @param p2 Short id of one of the peers (order unimportant)
 729  * @param cb Function to call for every peer that is marked as disconnected.
 730  *
 731  * @return Short ID of the first disconnected peer in the tree.
 732  */
 733 GNUNET_PEER_Id
 734 tree_notify_connection_broken (struct MeshTunnelTree *t,
 735                                GNUNET_PEER_Id p1,
 736                                GNUNET_PEER_Id p2,
 737                                MeshNodeDisconnectCB cb)
 738 {
 739   struct MeshTunnelTreeNode *n;
 740   struct MeshTunnelTreeNode *c;
 741
 742   n = tree_find_peer(t->me, p1);
 743   if (NULL == n)
 744     return 0;
 745   if (NULL != n->parent && n->parent->peer == p2)
 746   {
 747     tree_mark_peers_disconnected(t, n, cb);
 748     GNUNET_CONTAINER_DLL_remove(n->parent->children_head,
 749                                 n->parent->children_tail,
 750                                 n);
 751     GNUNET_CONTAINER_DLL_insert(t->disconnected_head,
 752                                 t->disconnected_tail,
 753                                 n);
 754     return p1;
 755   }
 756   for (c = n->children_head; NULL != c; c = c->next)
 757   {
 758     if (c->peer == p2)
 759     {
 760       tree_mark_peers_disconnected(t, c, cb);
 761       GNUNET_CONTAINER_DLL_remove(n->children_head,
 762                                   n->children_tail,
 763                                   c);
 764       GNUNET_CONTAINER_DLL_insert(t->disconnected_head,
 765                                   t->disconnected_tail,
 766                                   c);
 767       return p2;
 768     }
 769   }
 770   return 0;
 771 }
 772
 773
 774 /**
 775  * Deletes a peer from a tunnel, liberating all unused resources on the path to
 776  * it. It shouldn't have children, if it has they will be destroyed as well.
 777  * If the tree is not local and no longer has any paths, the root node will be
 778  * destroyed and marked as NULL.
 779  *
 780  * @param t Tunnel tree to use.
 781  * @param peer Short ID of the peer to remove from the tunnel tree.
 782  * @param cb Callback to notify client of disconnected peers.
 783  *
 784  * @return GNUNET_OK or GNUNET_SYSERR
 785  */
 786 int
 787 tree_del_peer (struct MeshTunnelTree *t,
 788                GNUNET_PEER_Id peer,
 789                MeshNodeDisconnectCB cb)
 790 {
 791   struct MeshTunnelTreeNode *n;
 792
 793   n = tree_del_path(t, peer, cb);
 794   if (NULL == n)
 795     return GNUNET_SYSERR;
 796   GNUNET_break_op (NULL == n->children_head);
 797   tree_node_destroy(n);
 798   if (NULL == t->root->children_head && t->me != t->root)
 799   {
 800     tree_node_destroy (t->root);
 801     t->root = NULL;
 802   }
 803   return GNUNET_OK;
 804 }
 805
 806
 807 /**
 808  * Print the tree on stderr
 809  *
 810  * @param t The tree
 811  */
 812 void
 813 tree_debug(struct MeshTunnelTree *t)
 814 {
 815   tree_node_debug(t->root, 0);
 816 }
 817
 818
 819 /**
 820  * Iterator over hash map peer entries and frees all data in it.
 821  * Used prior to destroying a hashmap. Makes you miss anonymous functions in C.
 822  *
 823  * @param cls closure
 824  * @param key current key code (will no longer contain valid data!!)
 825  * @param value value in the hash map (treated as void *)
 826  * @return GNUNET_YES if we should continue to iterate, GNUNET_NO if not.
 827  */
 828 static int
 829 iterate_free (void *cls, const GNUNET_HashCode * key, void *value)
 830 {
 831   GNUNET_free(value);
 832   return GNUNET_YES;
 833 }
 834
 835
 836 /**
 837  * Destroy the whole tree and free all used memory and Peer_Ids
 838  *
 839  * @param t Tree to be destroyed
 840  */
 841 void
 842 tree_destroy (struct MeshTunnelTree *t)
 843 {
 844 #if MESH_TREE_DEBUG
 845   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "tree: Destroying tree\n");
 846 #endif
 847   tree_node_destroy(t->root);
 848   GNUNET_CONTAINER_multihashmap_iterate(t->first_hops, &iterate_free, NULL);
 849   GNUNET_CONTAINER_multihashmap_destroy(t->first_hops);
 850   GNUNET_free(t);
 851 }