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