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