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