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