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 tunnel_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 = tunnel_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 parent Node to be clean, potentially with children
 153  * @param cb Callback to use to notify about disconnected peers.
 154  */
 155 void
 156 tunnel_mark_peers_disconnected (struct MeshTunnelTreeNode *parent,
 157                                 MeshNodeDisconnectCB cb)
 158 {
 159   unsigned int i;
 160
 161   if (MESH_PEER_READY == parent->status)
 162   {
 163     cb (parent);
 164   }
 165   parent->status = MESH_PEER_RECONNECTING;
 166   for (i = 0; i < parent->nchildren; i++)
 167   {
 168     tunnel_mark_peers_disconnected (&parent->children[i], cb);
 169   }
 170 //   struct GNUNET_MESH_PeerControl msg;
 171 //   if (NULL == parent->t->client)
 172 //     return;
 173 //   msg.header.size = htons (sizeof (msg));
 174 //   msg.header.type = htons (GNUNET_MESSAGE_TYPE_MESH_LOCAL_PEER_DEL);
 175 //   msg.tunnel_id = htonl (parent->t->local_tid);
 176 //   GNUNET_PEER_resolve (parent->peer, &msg.peer);
 177 //   if (NULL == nc)
 178 //     return;
 179 //   GNUNET_SERVER_notification_context_unicast (nc, parent->t->client->handle,
 180 //                                               &msg.header, GNUNET_NO);
 181 }
 182
 183
 184
 185
 186 /**
 187  * Delete the current path to the peer, including all now unused relays.
 188  * The destination peer is NOT destroyed, it is returned in order to either set
 189  * a new path to it or destroy it explicitly, taking care of it's child nodes.
 190  *
 191  * @param t Tunnel tree where to delete the path from.
 192  * @param peer Destination peer whose path we want to remove.
 193  * @param cb Callback to use to notify about disconnected peers.
 194  *
 195  * @return pointer to the pathless node, NULL on error
 196  */
 197 struct MeshTunnelTreeNode *
 198 tunnel_del_path (struct MeshTunnelTree *t, GNUNET_PEER_Id peer_id,
 199                  MeshNodeDisconnectCB cb)
 200 {
 201   struct MeshTunnelTreeNode *parent;
 202   struct MeshTunnelTreeNode *node;
 203   struct MeshTunnelTreeNode *n;
 204
 205   if (peer_id == t->root->peer)
 206     return NULL;
 207   node = n = tunnel_find_peer (t->me, peer_id);
 208   if (NULL == n)
 209     return NULL;
 210   parent = n->parent;
 211   n->parent = NULL;
 212   while (NULL != parent && MESH_PEER_RELAY == parent->status &&
 213          1 == parent->nchildren)
 214   {
 215     n = parent;
 216     GNUNET_free (parent->children);
 217     parent = parent->parent;
 218   }
 219   if (NULL == parent)
 220     return node;
 221   *n = parent->children[parent->nchildren - 1];
 222   parent->nchildren--;
 223   parent->children = GNUNET_realloc (parent->children, parent->nchildren);
 224
 225   tunnel_mark_peers_disconnected (node, cb);
 226
 227   return node;
 228 }
 229
 230
 231 /**
 232  * Return a newly allocated individual path to reach a peer from the local peer,
 233  * according to the path tree of some tunnel.
 234  *
 235  * @param t Tunnel from which to read the path tree
 236  * @param peer_info Destination peer to whom we want a path
 237  *
 238  * @return A newly allocated individual path to reach the destination peer.
 239  *         Path must be destroyed afterwards.
 240  */
 241 struct MeshPeerPath *
 242 tunnel_get_path_to_peer(struct MeshTunnelTree *t, GNUNET_PEER_Id peer)
 243 {
 244   struct MeshTunnelTreeNode *n;
 245   struct MeshPeerPath *p;
 246   GNUNET_PEER_Id myid = t->me->peer;
 247
 248   n = tunnel_find_peer(t->me, peer);
 249   p = GNUNET_malloc(sizeof(struct MeshPeerPath));
 250
 251   /* Building the path (inverted!) */
 252   while (n->peer != myid)
 253   {
 254     GNUNET_array_append(p->peers, p->length, n->peer);
 255     GNUNET_PEER_change_rc(n->peer, 1);
 256     n = n->parent;
 257     GNUNET_assert(NULL != n);
 258   }
 259   GNUNET_array_append(p->peers, p->length, myid);
 260   GNUNET_PEER_change_rc(myid, 1);
 261
 262   path_invert(p);
 263
 264   return p;
 265 }
 266
 267
 268 /**
 269  * Integrate a stand alone path into the tunnel tree.
 270  *
 271  * @param t Tunnel where to add the new path.
 272  * @param p Path to be integrated.
 273  * @param cb Callback to use to notify about peers temporarily disconnecting
 274  *
 275  * @return GNUNET_OK in case of success.
 276  *         GNUNET_SYSERR in case of error.
 277  *
 278  * TODO: optimize
 279  * - go backwards on path looking for each peer in the present tree
 280  * - do not disconnect peers until new path is created & connected
 281  */
 282 int
 283 tunnel_add_path (struct MeshTunnelTree *t, const struct MeshPeerPath *p,
 284                  MeshNodeDisconnectCB cb)
 285 {
 286   struct MeshTunnelTreeNode *parent;
 287   struct MeshTunnelTreeNode *oldnode;
 288   struct MeshTunnelTreeNode *n;
 289   struct GNUNET_PeerIdentity id;
 290   struct GNUNET_PeerIdentity *hop;
 291   GNUNET_PEER_Id myid = t->me->peer;
 292   int me;
 293   unsigned int i;
 294   unsigned int j;
 295
 296   GNUNET_assert(0 != p->length);
 297   n = t->root;
 298   if (n->peer != p->peers[0])
 299   {
 300     GNUNET_break (0);
 301     return GNUNET_SYSERR;
 302   }
 303   if (1 == p->length)
 304     return GNUNET_OK;
 305   oldnode = tunnel_del_path (t, p->peers[p->length - 1], cb);
 306   /* Look for the first node that is not already present in the tree
 307    *
 308    * Assuming that the tree is somewhat balanced, O(log n * log N).
 309    * - Length of the path is expected to be log N (size of whole network).
 310    * - Each level of the tree is expected to have log n children (size of tree).
 311    */
 312   for (i = 0, me = -1; i < p->length; i++)
 313   {
 314     parent = n;
 315     if (p->peers[i] == myid)
 316       me = i;
 317     for (j = 0; j < n->nchildren; j++)
 318     {
 319       if (n->children[j].peer == p->peers[i])
 320       {
 321         n = &n->children[j];
 322         break;
 323       }
 324     }
 325     /*  If we couldn't find a child equal to path[i], we have reached the end
 326      * of the common path. */
 327     if (parent == n)
 328       break;
 329   }
 330   if (-1 == me)
 331   {
 332     /* New path deviates from tree before reaching us. What happened? */
 333     GNUNET_break (0);
 334     return GNUNET_SYSERR;
 335   }
 336   /* Add the rest of the path as a branch from parent. */
 337   while (i < p->length)
 338   {
 339     parent->nchildren++;
 340     parent->children = GNUNET_realloc (parent->children,
 341                                        parent->nchildren *
 342                                        sizeof(struct MeshTunnelTreeNode));
 343     n = &parent->children[parent->nchildren - 1];
 344     if (i == p->length - 1 && NULL != oldnode)
 345     {
 346       /* Assignation and free can be misleading, using explicit mempcy */
 347       memcpy (n, oldnode, sizeof (struct MeshTunnelTreeNode));
 348       GNUNET_free (oldnode);
 349     }
 350     else
 351     {
 352       n->t = t->t;
 353       n->status = MESH_PEER_RELAY;
 354       n->peer = p->peers[i];
 355     }
 356     n->parent = parent;
 357     i++;
 358     parent = n;
 359   }
 360   n->status = MESH_PEER_SEARCHING;
 361
 362   /* Add info about first hop into hashmap. */
 363   if (me < p->length - 1)
 364   {
 365     GNUNET_PEER_resolve (p->peers[p->length - 1], &id);
 366     hop = GNUNET_malloc(sizeof(struct GNUNET_PeerIdentity));
 367     GNUNET_PEER_resolve (p->peers[me + 1], hop);
 368     GNUNET_CONTAINER_multihashmap_put (t->first_hops, &id.hashPubKey,
 369                                        hop,
 370                                        GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST);
 371   }
 372   return GNUNET_OK;
 373 }