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 (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
 305   return tree;
 306 }
 307
 308
 309 /**
 310  * Recursively find the given peer in the tree.
 311  *
 312  * @param t Tunnel where to look for the peer.
 313  * @param peer Peer to find
 314  *
 315  * @return Pointer to the node of the peer. NULL if not found.
 316  */
 317 struct MeshTunnelTreeNode *
 318 tree_find_peer (struct MeshTunnelTreeNode *parent, GNUNET_PEER_Id peer_id)
 319 {
 320   struct MeshTunnelTreeNode *n;
 321   struct MeshTunnelTreeNode *r;
 322
 323   if (parent->peer == peer_id)
 324     return parent;
 325   for (n = parent->children_head; NULL != n; n = n->next)
 326   {
 327     r = tree_find_peer (n, peer_id);
 328     if (NULL != r)
 329       return r;
 330   }
 331   return NULL;
 332 }
 333
 334
 335 /**
 336  * Recusively mark peer and children as disconnected, notify client
 337  *
 338  * @param tree Tree this node belongs to
 339  * @param parent Node to be clean, potentially with children
 340  * @param cb Callback to use to notify about disconnected peers.
 341  */
 342 static void
 343 tree_mark_peers_disconnected (struct MeshTunnelTree *tree,
 344                               struct MeshTunnelTreeNode *parent,
 345                               MeshNodeDisconnectCB cb,
 346                               void *cbcls)
 347 {
 348   struct GNUNET_PeerIdentity *pi;
 349   struct GNUNET_PeerIdentity id;
 350   struct MeshTunnelTreeNode *n;
 351
 352   for (n = parent->children_head; NULL != n; n = n->next)
 353   {
 354     tree_mark_peers_disconnected (tree, n, cb, cbcls);
 355   }
 356   if (MESH_PEER_READY == parent->status)
 357   {
 358     if (NULL != cb)
 359       cb (cbcls, parent->peer);
 360     parent->status = MESH_PEER_RECONNECTING;
 361   }
 362
 363   /* Remove and free info about first hop */
 364   GNUNET_PEER_resolve(parent->peer, &id);
 365   pi = GNUNET_CONTAINER_multihashmap_get(tree->first_hops, &id.hashPubKey);
 366   GNUNET_CONTAINER_multihashmap_remove_all(tree->first_hops, &id.hashPubKey);
 367   if (NULL != pi)
 368     GNUNET_free(pi);
 369 }
 370
 371
 372 /**
 373  * Recusively update the info about what is the first hop to reach the node
 374  *
 375  * @param tree Tree this nodes belongs to
 376  * @param parent Node to be start updating
 377  * @param hop If known, ID of the first hop.
 378  *            If not known, NULL to find out and pass on children.
 379  */
 380 void
 381 tree_update_first_hops (struct MeshTunnelTree *tree,
 382                         struct MeshTunnelTreeNode *parent,
 383                         struct GNUNET_PeerIdentity *hop)
 384 {
 385   struct GNUNET_PeerIdentity pi;
 386   struct GNUNET_PeerIdentity *copy;
 387   struct GNUNET_PeerIdentity id;
 388   struct MeshTunnelTreeNode *n;
 389
 390 #if MESH_TREE_DEBUG
 391   GNUNET_PEER_resolve(parent->peer, &id);
 392   GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 393           "tree:   Finding first hop for %s.\n",
 394           GNUNET_i2s (&id));
 395 #endif
 396   if (NULL == hop)
 397   {
 398     struct MeshTunnelTreeNode *aux;
 399     struct MeshTunnelTreeNode *old;
 400
 401     aux = old = parent;
 402     while (aux != tree->me)
 403     {
 404 #if MESH_TREE_DEBUG
 405       GNUNET_PEER_resolve(old->peer, &id);
 406       GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 407              "tree:   ... its not %s.\n",
 408              GNUNET_i2s (&id));
 409 #endif
 410       old = aux;
 411       aux = aux->parent;
 412       GNUNET_assert(NULL != aux);
 413     }
 414 #if MESH_TREE_DEBUG
 415     GNUNET_PEER_resolve(old->peer, &id);
 416     GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 417                "tree:   It's %s!\n",
 418                GNUNET_i2s (&id));
 419 #endif
 420     hop = &pi;
 421     GNUNET_PEER_resolve(old->peer, hop);
 422   }
 423   GNUNET_PEER_resolve(parent->peer, &id);
 424   copy = GNUNET_CONTAINER_multihashmap_get (tree->first_hops, &id.hashPubKey);
 425   if (NULL == copy)
 426     copy = GNUNET_malloc(sizeof(struct GNUNET_PeerIdentity));
 427   *copy = *hop;
 428
 429   (void) GNUNET_CONTAINER_multihashmap_put(
 430     tree->first_hops,
 431     &id.hashPubKey,
 432     copy,
 433     GNUNET_CONTAINER_MULTIHASHMAPOPTION_REPLACE);
 434
 435   for (n = parent->children_head; NULL != n; n = n->next)
 436   {
 437     tree_update_first_hops (tree, n, hop);
 438   }
 439 }
 440
 441
 442 /**
 443  * Delete the current path to the peer, including all now unused relays.
 444  * The destination peer is NOT destroyed, it is returned in order to either set
 445  * a new path to it or destroy it explicitly, taking care of it's child nodes.
 446  *
 447  * @param t Tunnel tree where to delete the path from.
 448  * @param peer Destination peer whose path we want to remove.
 449  * @param cb Callback to use to notify about disconnected peers.
 450  * @param cbcls Closure for cb.
 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                void *cbcls)
 460 {
 461   struct MeshTunnelTreeNode *parent;
 462   struct MeshTunnelTreeNode *node;
 463   struct MeshTunnelTreeNode *n;
 464
 465 #if MESH_TREE_DEBUG
 466   struct GNUNET_PeerIdentity id;
 467   GNUNET_PEER_resolve(peer_id, &id);
 468   GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 469           "tree:   Deleting path to %s.\n",
 470           GNUNET_i2s (&id));
 471 #endif
 472   if (peer_id == t->root->peer)
 473     return NULL;
 474
 475   for (n = t->disconnected_head; NULL != n; n = n->next)
 476   {
 477     if (n->peer == peer_id)
 478     {
 479       /* Was already pathless, waiting for reconnection */
 480       GNUNET_CONTAINER_DLL_remove (t->disconnected_head,
 481                                    t->disconnected_tail,
 482                                    n);
 483       return n;
 484     }
 485   }
 486   n = tree_find_peer (t->root, peer_id);
 487   if (NULL == n)
 488     return NULL;
 489   node = n;
 490
 491   parent = n->parent;
 492   GNUNET_CONTAINER_DLL_remove(parent->children_head, parent->children_tail, n);
 493   n->parent = NULL;
 494
 495   while (MESH_PEER_RELAY == parent->status && NULL == parent->children_head)
 496   {
 497 #if MESH_TREE_DEBUG
 498     GNUNET_PEER_resolve(parent->peer, &id);
 499     GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 500               "tree:   Deleting node %s.\n",
 501               GNUNET_i2s (&id));
 502 #endif
 503     n = parent->parent;
 504     tree_node_destroy(parent);
 505     parent = n;
 506   }
 507 #if MESH_TREE_DEBUG
 508   GNUNET_PEER_resolve(parent->peer, &id);
 509   GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 510              "tree:   Not deleted peer %s.\n",
 511              GNUNET_i2s (&id));
 512 #endif
 513
 514   tree_mark_peers_disconnected (t, node, cb, cbcls);
 515
 516   return node;
 517 }
 518
 519
 520 /**
 521  * Return a newly allocated individual path to reach a peer from the local peer,
 522  * according to the path tree of some tunnel.
 523  *
 524  * @param t Tunnel from which to read the path tree
 525  * @param peer_info Destination peer to whom we want a path
 526  *
 527  * @return A newly allocated individual path to reach the destination peer.
 528  *         Path must be destroyed afterwards.
 529  */
 530 struct MeshPeerPath *
 531 tree_get_path_to_peer(struct MeshTunnelTree *t, GNUNET_PEER_Id peer)
 532 {
 533   struct MeshTunnelTreeNode *n;
 534   struct MeshPeerPath *p;
 535   GNUNET_PEER_Id myid = t->me->peer;
 536
 537   n = tree_find_peer(t->me, peer);
 538   if (NULL == n)
 539     return NULL;
 540   p = path_new(0);
 541
 542   /* Building the path (inverted!) */
 543   while (n->peer != myid)
 544   {
 545     GNUNET_array_append(p->peers, p->length, n->peer);
 546     GNUNET_PEER_change_rc(n->peer, 1);
 547     n = n->parent;
 548     GNUNET_assert(NULL != n);
 549   }
 550   GNUNET_array_append(p->peers, p->length, myid);
 551   GNUNET_PEER_change_rc(myid, 1);
 552
 553   path_invert(p);
 554
 555   return p;
 556 }
 557
 558
 559
 560 /**
 561  * Integrate a stand alone path into the tunnel tree.
 562  * If the peer toward which the new path is already in the tree, the peer
 563  * and its children will be maked as disconnected and the callback
 564  * will be called on each one of them. They will be maked as online only after
 565  * receiving a PATH ACK for the new path for each one of them, so the caller
 566  * should take care of sending a new CREATE PATH message for each disconnected
 567  * peer.
 568  *
 569  * @param t Tunnel where to add the new path.
 570  * @param p Path to be integrated.
 571  * @param cb Callback to use to notify about peers temporarily disconnecting.
 572  * @param cbcls Closure for cb.
 573  *
 574  * @return GNUNET_OK in case of success.
 575  *         GNUNET_SYSERR in case of error.
 576  *
 577  * TODO: optimize
 578  * - go backwards on path looking for each peer in the present tree
 579  * - do not disconnect peers until new path is created & connected
 580  */
 581 int
 582 tree_add_path (struct MeshTunnelTree *t,
 583                const struct MeshPeerPath *p,
 584                MeshNodeDisconnectCB cb,
 585                void *cbcls)
 586 {
 587   struct MeshTunnelTreeNode *parent;
 588   struct MeshTunnelTreeNode *oldnode;
 589   struct MeshTunnelTreeNode *n;
 590   struct MeshTunnelTreeNode *c;
 591   struct GNUNET_PeerIdentity id;
 592   GNUNET_PEER_Id myid;
 593   int me;
 594   unsigned int i;
 595
 596 #if MESH_TREE_DEBUG
 597   GNUNET_PEER_resolve(p->peers[p->length - 1], &id);
 598   GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 599              "tree:   Adding path [%u] towards peer %s.\n",
 600             p->length,
 601             GNUNET_i2s (&id));
 602 #endif
 603
 604   if (NULL != t->me)
 605     myid = t->me->peer;
 606   else
 607     myid = 0;
 608   GNUNET_assert(0 != p->length);
 609   parent = n = t->root;
 610   if (n->peer != p->peers[0])
 611   {
 612     GNUNET_break (0);
 613     return GNUNET_SYSERR;
 614   }
 615   if (1 == p->length)
 616     return GNUNET_OK;
 617   oldnode = tree_del_path (t, p->peers[p->length - 1], cb, cbcls);
 618   /* Look for the first node that is not already present in the tree
 619    *
 620    * Assuming that the tree is somewhat balanced, O(log n * log N).
 621    * - Length of the path is expected to be log N (size of whole network).
 622    * - Each level of the tree is expected to have log n children (size of tree).
 623    */
 624   me = t->root->peer == myid ? 0 : -1;
 625   for (i = 1; i < p->length; i++)
 626   {
 627 #if MESH_TREE_DEBUG
 628     GNUNET_PEER_resolve(p->peers[i], &id);
 629     GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 630                "tree:   Looking for peer %s.\n",
 631                GNUNET_i2s (&id));
 632 #endif
 633     parent = n;
 634     if (p->peers[i] == myid)
 635       me = i;
 636     for (c = n->children_head; NULL != c; c = c->next)
 637     {
 638       if (c->peer == p->peers[i])
 639       {
 640 #if MESH_TREE_DEBUG
 641         GNUNET_PEER_resolve(parent->peer, &id);
 642         GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 643                    "tree:   Found in children of %s.\n",
 644                    GNUNET_i2s (&id));
 645 #endif
 646         n = c;
 647         break;
 648       }
 649     }
 650     /*  If we couldn't find a child equal to path[i], we have reached the end
 651      * of the common path. */
 652     if (parent == n)
 653       break;
 654   }
 655 #if MESH_TREE_DEBUG
 656   GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 657              "tree:   All childen visited.\n");
 658 #endif
 659   /* Add the rest of the path as a branch from parent. */
 660   while (i < p->length)
 661   {
 662 #if MESH_TREE_DEBUG
 663     GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 664                "tree:   Adding peer %u to %u.\n",
 665                p->peers[i], parent->peer);
 666     GNUNET_PEER_resolve(p->peers[i], &id);
 667     GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 668                "tree:   Adding peer %s.\n",
 669                GNUNET_i2s (&id));
 670     GNUNET_PEER_resolve(parent->peer, &id);
 671     GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 672                "tree:     to %s.\n",
 673                GNUNET_i2s (&id));
 674 #endif
 675
 676     if (i == p->length - 1 && NULL != oldnode)
 677     {
 678 #if MESH_TREE_DEBUG
 679       GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 680                  "tree:   Putting old node into place.\n");
 681 #endif
 682       oldnode->parent = parent;
 683       GNUNET_CONTAINER_DLL_insert(parent->children_head,
 684                                   parent->children_tail,
 685                                   oldnode);
 686       tree_update_first_hops (t, oldnode, NULL);
 687       n = oldnode;
 688     }
 689     else
 690     {
 691 #if MESH_TREE_DEBUG
 692       GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "tree:   Creating new node.\n");
 693 #endif
 694       n = tree_node_new(parent, p->peers[i]);
 695       n->status = MESH_PEER_RELAY;
 696       if (n->peer == myid)
 697         t->me = n;
 698     }
 699     i++;
 700     parent = n;
 701   }
 702   n->status = MESH_PEER_SEARCHING;
 703
 704   /* Add info about first hop into hashmap. */
 705   if (-1 != me && me < p->length - 1)
 706   {
 707 #if MESH_TREE_DEBUG
 708     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 709                 "MESH:   finding first hop (own pos %d/%u)\n",
 710                 me, p->length - 1);
 711 #endif
 712     GNUNET_PEER_resolve (p->peers[me + 1], &id);
 713     tree_update_first_hops(t,
 714                            tree_find_peer(t->root, p->peers[p->length - 1]),
 715                            &id);
 716   }
 717 #if MESH_TREE_DEBUG
 718   GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "tree:   New node added.\n");
 719 #endif
 720   return GNUNET_OK;
 721 }
 722
 723
 724 /**
 725  * Notifies a tree that a connection it might be using is broken.
 726  * Marks all peers down the paths as disconnected and notifies the client.
 727  *
 728  * @param t Tree to use.
 729  * @param p1 Short id of one of the peers (order unimportant)
 730  * @param p2 Short id of one of the peers (order unimportant)
 731  * @param cb Function to call for every peer that is marked as disconnected.
 732  * @param cbcls Closure for cb.
 733  *
 734  * @return Short ID of the first disconnected peer in the tree.
 735  */
 736 GNUNET_PEER_Id
 737 tree_notify_connection_broken (struct MeshTunnelTree *t,
 738                                GNUNET_PEER_Id p1,
 739                                GNUNET_PEER_Id p2,
 740                                MeshNodeDisconnectCB cb,
 741                                void *cbcls)
 742 {
 743   struct MeshTunnelTreeNode *n;
 744   struct MeshTunnelTreeNode *c;
 745
 746   n = tree_find_peer(t->me, p1);
 747   if (NULL == n)
 748     return 0;
 749   if (NULL != n->parent && n->parent->peer == p2)
 750   {
 751     tree_mark_peers_disconnected(t, n, cb, cbcls);
 752     GNUNET_CONTAINER_DLL_remove(n->parent->children_head,
 753                                 n->parent->children_tail,
 754                                 n);
 755     GNUNET_CONTAINER_DLL_insert(t->disconnected_head,
 756                                 t->disconnected_tail,
 757                                 n);
 758     return p1;
 759   }
 760   for (c = n->children_head; NULL != c; c = c->next)
 761   {
 762     if (c->peer == p2)
 763     {
 764       tree_mark_peers_disconnected(t, c, cb, cbcls);
 765       GNUNET_CONTAINER_DLL_remove(n->children_head,
 766                                   n->children_tail,
 767                                   c);
 768       GNUNET_CONTAINER_DLL_insert(t->disconnected_head,
 769                                   t->disconnected_tail,
 770                                   c);
 771       return p2;
 772     }
 773   }
 774   return 0;
 775 }
 776
 777
 778 /**
 779  * Deletes a peer from a tunnel, liberating all unused resources on the path to
 780  * it. It shouldn't have children, if it has they will be destroyed as well.
 781  * If the tree is not local and no longer has any paths, the root node will be
 782  * destroyed and marked as NULL.
 783  *
 784  * @param t Tunnel tree to use.
 785  * @param peer Short ID of the peer to remove from the tunnel tree.
 786  * @param cb Callback to notify client of disconnected peers.
 787  * @param cbcls Closure for cb.
 788  *
 789  * @return GNUNET_OK or GNUNET_SYSERR
 790  */
 791 int
 792 tree_del_peer (struct MeshTunnelTree *t,
 793                GNUNET_PEER_Id peer,
 794                MeshNodeDisconnectCB cb,
 795                void *cbcls)
 796 {
 797   struct MeshTunnelTreeNode *n;
 798
 799   n = tree_del_path(t, peer, cb, cbcls);
 800   if (NULL == n)
 801     return GNUNET_SYSERR;
 802   GNUNET_break_op (NULL == n->children_head);
 803   tree_node_destroy(n);
 804   if (NULL == t->root->children_head && t->me != t->root)
 805   {
 806     tree_node_destroy (t->root);
 807     t->root = NULL;
 808   }
 809   return GNUNET_OK;
 810 }
 811
 812
 813 /**
 814  * Print the tree on stderr
 815  *
 816  * @param t The tree
 817  */
 818 void
 819 tree_debug(struct MeshTunnelTree *t)
 820 {
 821   tree_node_debug(t->root, 0);
 822 }
 823
 824
 825 /**
 826  * Iterator over hash map peer entries and frees all data in it.
 827  * Used prior to destroying a hashmap. Makes you miss anonymous functions in C.
 828  *
 829  * @param cls closure
 830  * @param key current key code (will no longer contain valid data!!)
 831  * @param value value in the hash map (treated as void *)
 832  * @return GNUNET_YES if we should continue to iterate, GNUNET_NO if not.
 833  */
 834 static int
 835 iterate_free (void *cls, const GNUNET_HashCode * key, void *value)
 836 {
 837   GNUNET_free(value);
 838   return GNUNET_YES;
 839 }
 840
 841
 842 /**
 843  * Destroy the whole tree and free all used memory and Peer_Ids
 844  *
 845  * @param t Tree to be destroyed
 846  */
 847 void
 848 tree_destroy (struct MeshTunnelTree *t)
 849 {
 850 #if MESH_TREE_DEBUG
 851   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "tree: Destroying tree\n");
 852 #endif
 853   tree_node_destroy(t->root);
 854   GNUNET_CONTAINER_multihashmap_iterate(t->first_hops, &iterate_free, NULL);
 855   GNUNET_CONTAINER_multihashmap_destroy(t->first_hops);
 856   GNUNET_free(t);
 857 }