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