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
  31 /**
  32  * Invert the path
  33  *
  34  * @param p the path to invert
  35  */
  36 void
  37 path_invert (struct MeshPeerPath *path)
  38 {
  39   GNUNET_PEER_Id aux;
  40   unsigned int i;
  41
  42   for (i = 0; i < path->length / 2; i++)
  43   {
  44     aux = path->peers[i];
  45     path->peers[i] = path->peers[path->length - i - 1];
  46     path->peers[path->length - i - 1] = aux;
  47   }
  48 }
  49
  50
  51 /**
  52  * Destroy the path and free any allocated resources linked to it
  53  *
  54  * @param p the path to destroy
  55  *
  56  * @return GNUNET_OK on success
  57  */
  58 int
  59 path_destroy (struct MeshPeerPath *p)
  60 {
  61   GNUNET_PEER_decrement_rcs (p->peers, p->length);
  62   GNUNET_free (p->peers);
  63   GNUNET_free (p);
  64   return GNUNET_OK;
  65 }
  66
  67
  68 /**
  69  * Find the first peer whom to send a packet to go down this path
  70  *
  71  * @param t The tunnel tree to use
  72  * @param peer The peerinfo of the peer we are trying to reach
  73  *
  74  * @return peerinfo of the peer who is the first hop in the tunnel
  75  *         NULL on error
  76  */
  77 struct GNUNET_PeerIdentity *
  78 path_get_first_hop (struct MeshTunnelTree *t, GNUNET_PEER_Id peer)
  79 {
  80   struct GNUNET_PeerIdentity id;
  81
  82   GNUNET_PEER_resolve (peer, &id);
  83   return GNUNET_CONTAINER_multihashmap_get (t->first_hops,
  84                                             &id.hashPubKey);
  85 }
  86
  87
  88 /**
  89  * Get the length of a path
  90  *
  91  * @param path The path to measure, with the local peer at any point of it
  92  *
  93  * @return Number of hops to reach destination
  94  *         UINT_MAX in case the peer is not in the path
  95  */
  96 unsigned int
  97 path_get_length (struct MeshPeerPath *path)
  98 {
  99   if (NULL == path)
 100     return UINT_MAX;
 101   return path->length;
 102 }
 103
 104
 105 /**
 106  * Get the cost of the path relative to the already built tunnel tree
 107  *
 108  * @param t The tunnel tree to which compare
 109  * @param path The individual path to reach a peer
 110  *
 111  * @return Number of hops to reach destination, UINT_MAX in case the peer is not
 112  * in the path
 113  *
 114  * TODO: remove dummy implementation, look into the tunnel tree
 115  */
 116 unsigned int
 117 path_get_cost (struct MeshTunnelTree *t, struct MeshPeerPath *path)
 118 {
 119   return path_get_length (path);
 120 }
 121
 122
 123 /**
 124  * Recursively find the given peer in the tree.
 125  *
 126  * @param t Tunnel where to look for the peer.
 127  * @param peer Peer to find
 128  *
 129  * @return Pointer to the node of the peer. NULL if not found.
 130  */
 131 struct MeshTunnelTreeNode *
 132 tree_find_peer (struct MeshTunnelTreeNode *root, GNUNET_PEER_Id peer_id)
 133 {
 134   struct MeshTunnelTreeNode *n;
 135   unsigned int i;
 136
 137   if (root->peer == peer_id)
 138     return root;
 139   for (i = 0; i < root->nchildren; i++)
 140   {
 141     n = tree_find_peer (&root->children[i], peer_id);
 142     if (NULL != n)
 143       return n;
 144   }
 145   return NULL;
 146 }
 147
 148
 149 /**
 150  * Recusively mark peer and children as disconnected, notify client
 151  *
 152  * @param tree Tree this node belongs to
 153  * @param parent Node to be clean, potentially with children
 154  * @param cb Callback to use to notify about disconnected peers.
 155  */
 156 void
 157 tree_mark_peers_disconnected (struct MeshTunnelTree *tree,
 158                               struct MeshTunnelTreeNode *parent,
 159                               MeshNodeDisconnectCB cb)
 160 {
 161   struct GNUNET_PeerIdentity *pi;
 162   struct GNUNET_PeerIdentity id;
 163   unsigned int i;
 164
 165   for (i = 0; i < parent->nchildren; i++)
 166   {
 167     tree_mark_peers_disconnected (tree, &parent->children[i], cb);
 168   }
 169   if (MESH_PEER_READY == parent->status)
 170   {
 171     cb (parent);
 172   }
 173   parent->status = MESH_PEER_RECONNECTING;
 174
 175   /* Remove and free info about first hop */
 176   GNUNET_PEER_resolve(parent->peer, &id);
 177   pi = GNUNET_CONTAINER_multihashmap_get(tree->first_hops, &id.hashPubKey);
 178   GNUNET_CONTAINER_multihashmap_remove_all(tree->first_hops, &id.hashPubKey);
 179   if (NULL != pi)
 180     GNUNET_free(pi);
 181 //   struct GNUNET_MESH_PeerControl msg;
 182 //   if (NULL == parent->t->client)
 183 //     return;
 184 //   msg.header.size = htons (sizeof (msg));
 185 //   msg.header.type = htons (GNUNET_MESSAGE_TYPE_MESH_LOCAL_PEER_DEL);
 186 //   msg.tunnel_id = htonl (parent->t->local_tid);
 187 //   GNUNET_PEER_resolve (parent->peer, &msg.peer);
 188 //   if (NULL == nc)
 189 //     return;
 190 //   GNUNET_SERVER_notification_context_unicast (nc, parent->t->client->handle,
 191 //                                               &msg.header, GNUNET_NO);
 192 }
 193
 194
 195
 196
 197 /**
 198  * Delete the current path to the peer, including all now unused relays.
 199  * The destination peer is NOT destroyed, it is returned in order to either set
 200  * a new path to it or destroy it explicitly, taking care of it's child nodes.
 201  *
 202  * @param t Tunnel tree where to delete the path from.
 203  * @param peer Destination peer whose path we want to remove.
 204  * @param cb Callback to use to notify about disconnected peers.
 205  *
 206  * @return pointer to the pathless node, NULL on error
 207  */
 208 struct MeshTunnelTreeNode *
 209 tree_del_path (struct MeshTunnelTree *t, GNUNET_PEER_Id peer_id,
 210                  MeshNodeDisconnectCB cb)
 211 {
 212   struct MeshTunnelTreeNode *parent;
 213   struct MeshTunnelTreeNode *node;
 214   struct MeshTunnelTreeNode *n;
 215
 216   GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "Deleting path to %u.\n", peer_id);
 217   if (peer_id == t->root->peer)
 218     return NULL;
 219   n = tree_find_peer (t->me, peer_id);
 220   if (NULL == n)
 221     return NULL;
 222   node = GNUNET_malloc(sizeof(struct MeshTunnelTreeNode));
 223   *node = *n;
 224   parent = n->parent;
 225   parent->nchildren--;
 226   n->parent = NULL;
 227   *n = parent->children[parent->nchildren];
 228   parent->children = GNUNET_realloc(parent->children,
 229                                     parent->nchildren
 230                                     * sizeof(struct MeshTunnelTreeNode));
 231   while (t->root != parent && MESH_PEER_RELAY == parent->status &&
 232          0 == parent->nchildren)
 233   {
 234     GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "Deleting node %u.\n", parent->peer);
 235     n = parent->parent;
 236     tree_node_destroy(parent);
 237     parent = n;
 238   }
 239
 240   tree_mark_peers_disconnected (t, node, cb);
 241
 242   return node;
 243 }
 244
 245
 246 /**
 247  * Return a newly allocated individual path to reach a peer from the local peer,
 248  * according to the path tree of some tunnel.
 249  *
 250  * @param t Tunnel from which to read the path tree
 251  * @param peer_info Destination peer to whom we want a path
 252  *
 253  * @return A newly allocated individual path to reach the destination peer.
 254  *         Path must be destroyed afterwards.
 255  */
 256 struct MeshPeerPath *
 257 tree_get_path_to_peer(struct MeshTunnelTree *t, GNUNET_PEER_Id peer)
 258 {
 259   struct MeshTunnelTreeNode *n;
 260   struct MeshPeerPath *p;
 261   GNUNET_PEER_Id myid = t->me->peer;
 262
 263   n = tree_find_peer(t->me, peer);
 264   p = GNUNET_malloc(sizeof(struct MeshPeerPath));
 265
 266   /* Building the path (inverted!) */
 267   while (n->peer != myid)
 268   {
 269     GNUNET_array_append(p->peers, p->length, n->peer);
 270     GNUNET_PEER_change_rc(n->peer, 1);
 271     n = n->parent;
 272     GNUNET_assert(NULL != n);
 273   }
 274   GNUNET_array_append(p->peers, p->length, myid);
 275   GNUNET_PEER_change_rc(myid, 1);
 276
 277   path_invert(p);
 278
 279   return p;
 280 }
 281
 282
 283 /**
 284  * Integrate a stand alone path into the tunnel tree.
 285  *
 286  * @param t Tunnel where to add the new path.
 287  * @param p Path to be integrated.
 288  * @param cb Callback to use to notify about peers temporarily disconnecting
 289  *
 290  * @return GNUNET_OK in case of success.
 291  *         GNUNET_SYSERR in case of error.
 292  *
 293  * TODO: optimize
 294  * - go backwards on path looking for each peer in the present tree
 295  * - do not disconnect peers until new path is created & connected
 296  */
 297 int
 298 tree_add_path (struct MeshTunnelTree *t, const struct MeshPeerPath *p,
 299                  MeshNodeDisconnectCB cb)
 300 {
 301   struct MeshTunnelTreeNode *parent;
 302   struct MeshTunnelTreeNode *oldnode;
 303   struct MeshTunnelTreeNode *n;
 304   struct GNUNET_PeerIdentity id;
 305   struct GNUNET_PeerIdentity *hop;
 306   GNUNET_PEER_Id myid = t->me->peer;
 307   int me;
 308   unsigned int i;
 309   unsigned int j;
 310
 311   GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 312              "Adding path [%u] towards peer %u to peer %u.\n",
 313              p->length,
 314              p->peers[p->length - 1],
 315              t->me->peer);
 316   GNUNET_assert(0 != p->length);
 317   parent = n = t->root;
 318   if (n->peer != p->peers[0])
 319   {
 320     GNUNET_break (0);
 321     return GNUNET_SYSERR;
 322   }
 323   if (1 == p->length)
 324     return GNUNET_OK;
 325   oldnode = tree_del_path (t, p->peers[p->length - 1], cb);
 326   /* Look for the first node that is not already present in the tree
 327    *
 328    * Assuming that the tree is somewhat balanced, O(log n * log N).
 329    * - Length of the path is expected to be log N (size of whole network).
 330    * - Each level of the tree is expected to have log n children (size of tree).
 331    */
 332   me = t->root->peer == myid ? 0 : -1;
 333   for (i = 1; i < p->length; i++)
 334   {
 335     GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 336              "Looking for peer %u.\n",
 337              p->peers[i]);
 338     parent = n;
 339     if (p->peers[i] == myid)
 340       me = i;
 341     for (j = 0; j < n->nchildren; j++)
 342     {
 343       if (n->children[j].peer == p->peers[i])
 344       {
 345         n = &n->children[j];
 346         break;
 347       }
 348     }
 349     /*  If we couldn't find a child equal to path[i], we have reached the end
 350      * of the common path. */
 351     if (parent == n)
 352       break;
 353   }
 354   GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 355              "All childen visited.\n");
 356   if (-1 == me)
 357   {
 358     /* New path deviates from tree before reaching us. What happened? */
 359     GNUNET_break (0);
 360     return GNUNET_SYSERR;
 361   }
 362   /* Add the rest of the path as a branch from parent. */
 363   while (i < p->length)
 364   {
 365     GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 366                "Adding  peer %u, to %u.\n",
 367                p->peers[i],
 368                parent->peer);
 369     parent->nchildren++;
 370     parent->children = GNUNET_realloc (parent->children,
 371                                        parent->nchildren *
 372                                        sizeof(struct MeshTunnelTreeNode));
 373     n = &parent->children[parent->nchildren - 1];
 374     if (i == p->length - 1 && NULL != oldnode)
 375     {
 376       GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "Putting old note into place.\n");
 377       /* Assignation and free can be misleading, using explicit mempcy */
 378       memcpy (n, oldnode, sizeof (struct MeshTunnelTreeNode));
 379       GNUNET_free (oldnode);
 380       for (j = 0; j < n->nchildren; j++)
 381       {
 382         n->children[j].parent = n;
 383       }
 384     }
 385     else
 386     {
 387       GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "Creating new node.\n");
 388       n->t = t->t;
 389       n->status = MESH_PEER_RELAY;
 390       n->peer = p->peers[i];
 391       n->nchildren = 0;
 392       n->children = NULL;
 393     }
 394     n->parent = parent;
 395     i++;
 396     parent = n;
 397   }
 398   n->status = MESH_PEER_SEARCHING;
 399
 400   /* Add info about first hop into hashmap. */
 401   if (me < p->length - 1)
 402   {
 403     GNUNET_PEER_resolve (p->peers[p->length - 1], &id);
 404     hop = GNUNET_CONTAINER_multihashmap_get(t->first_hops, &id.hashPubKey);
 405     if (NULL != hop)
 406       GNUNET_free(hop);
 407     hop = GNUNET_malloc(sizeof(struct GNUNET_PeerIdentity));
 408     GNUNET_PEER_resolve (p->peers[me + 1], hop);
 409     GNUNET_CONTAINER_multihashmap_put (t->first_hops, &id.hashPubKey,
 410                                        hop,
 411                                        GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST);
 412   }
 413   GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "New node added.\n");
 414   return GNUNET_OK;
 415 }
 416
 417
 418 /**
 419  * Destroy the node and all children
 420  *
 421  * @param n Parent node to be destroyed
 422  */
 423 void
 424 tree_node_destroy (struct MeshTunnelTreeNode *n)
 425 {
 426   struct MeshTunnelTreeNode *parent;
 427   unsigned int i;
 428
 429   if (n->nchildren != 0)
 430   {
 431     for (i = 0; i < n->nchildren; i++)
 432     {
 433       tree_node_destroy(&n->children[i]);
 434     }
 435     if (n->children != NULL)
 436       GNUNET_free(n->children);
 437   }
 438   GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "Destroying node %u.\n", n->peer);
 439   if (NULL == (parent = n->parent))
 440     return;
 441   i = (n - parent->children) / sizeof(struct MeshTunnelTreeNode);
 442   parent->children[i] = parent->children[parent->nchildren - 1];
 443   parent->nchildren--;
 444   parent->children = realloc(parent->children,
 445                              parent->nchildren
 446                              * sizeof(struct MeshTunnelTreeNode));
 447
 448   GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "Destroyed.\n");
 449 }
 450
 451
 452 /**
 453  * Iterator over hash map peer entries and frees all data in it.
 454  * Used prior to destroying a hashmap. Makes you miss anonymous functions in C.
 455  *
 456  * @param cls closure
 457  * @param key current key code (will no longer contain valid data!!)
 458  * @param value value in the hash map (treated as void *)
 459  * @return GNUNET_YES if we should continue to iterate, GNUNET_NO if not.
 460  */
 461 static int
 462 iterate_free (void *cls, const GNUNET_HashCode * key, void *value)
 463 {
 464   GNUNET_free(value);
 465   return GNUNET_YES;
 466 }
 467
 468
 469 /**
 470  * Destroy the whole tree and free all used memory and Peer_Ids
 471  *
 472  * @param t Tree to be destroyed
 473  */
 474 void
 475 tree_destroy (struct MeshTunnelTree *t)
 476 {
 477   tree_node_destroy(t->root);
 478   GNUNET_free(t->root);
 479   GNUNET_CONTAINER_multihashmap_iterate(t->first_hops, &iterate_free, NULL);
 480   GNUNET_CONTAINER_multihashmap_destroy(t->first_hops);
 481 }