src/mesh/gnunet-service-mesh_peer.c

   1 /*
   2      This file is part of GNUnet.
   3      (C) 2013 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 #include "platform.h"
  23 #include "gnunet_util_lib.h"
  24
  25 #include "gnunet-service-mesh_peer.h"
  26 #include "gnunet-service-mesh_dht.h"
  27 #include "mesh_path.h"
  28
  29 /******************************************************************************/
  30 /********************************   STRUCTS  **********************************/
  31 /******************************************************************************/
  32
  33 /**
  34  * Struct containing all information regarding a given peer
  35  */
  36 struct MeshPeer
  37 {
  38     /**
  39      * ID of the peer
  40      */
  41   GNUNET_PEER_Id id;
  42
  43     /**
  44      * Last time we heard from this peer
  45      */
  46   struct GNUNET_TIME_Absolute last_contact;
  47
  48     /**
  49      * Paths to reach the peer, ordered by ascending hop count
  50      */
  51   struct MeshPeerPath *path_head;
  52
  53     /**
  54      * Paths to reach the peer, ordered by ascending hop count
  55      */
  56   struct MeshPeerPath *path_tail;
  57
  58     /**
  59      * Handle to stop the DHT search for paths to this peer
  60      */
  61   struct GNUNET_DHT_GetHandle *dhtget;
  62
  63     /**
  64      * Tunnel to this peer, if any.
  65      */
  66   struct MeshTunnel2 *tunnel;
  67
  68     /**
  69      * Connections that go through this peer, indexed by tid;
  70      */
  71   struct GNUNET_CONTAINER_MultiHashMap *connections;
  72
  73     /**
  74      * Handle for queued transmissions
  75      */
  76   struct GNUNET_CORE_TransmitHandle *core_transmit;
  77
  78   /**
  79    * Transmission queue to core DLL head
  80    */
  81   struct MeshPeerQueue *queue_head;
  82
  83   /**
  84    * Transmission queue to core DLL tail
  85    */
  86   struct MeshPeerQueue *queue_tail;
  87
  88   /**
  89    * How many messages are in the queue to this peer.
  90    */
  91   unsigned int queue_n;
  92 };
  93
  94
  95 /******************************************************************************/
  96 /*******************************   GLOBALS  ***********************************/
  97 /******************************************************************************/
  98
  99 /**
 100  * Peers known, indexed by PeerIdentity (MeshPeer).
 101  */
 102 static struct GNUNET_CONTAINER_MultiPeerMap *peers;
 103
 104 /**
 105  * How many peers do we want to remember?
 106  */
 107 static unsigned long long max_peers;
 108
 109
 110 /******************************************************************************/
 111 /********************************   STATIC  ***********************************/
 112 /******************************************************************************/
 113
 114 /**
 115  * Iterator over tunnel hash map entries to destroy the tunnel during shutdown.
 116  *
 117  * @param cls closure
 118  * @param key current key code
 119  * @param value value in the hash map
 120  * @return #GNUNET_YES if we should continue to iterate,
 121  *         #GNUNET_NO if not.
 122  */
 123 static int
 124 shutdown_tunnel (void *cls,
 125                  const struct GNUNET_PeerIdentity *key,
 126                  void *value)
 127 {
 128   struct MeshPeer *p = value;
 129   struct MeshTunnel2 *t = p->tunnel;
 130
 131   if (NULL != t)
 132     GMT_destroy (t);
 133   return GNUNET_YES;
 134 }
 135
 136
 137
 138 /**
 139  * Destroy the peer_info and free any allocated resources linked to it
 140  *
 141  * @param peer The peer_info to destroy.
 142  *
 143  * @return GNUNET_OK on success
 144  */
 145 static int
 146 peer_destroy (struct MeshPeer *peer)
 147 {
 148   struct GNUNET_PeerIdentity id;
 149   struct MeshPeerPath *p;
 150   struct MeshPeerPath *nextp;
 151
 152   GNUNET_PEER_resolve (peer->id, &id);
 153   GNUNET_PEER_change_rc (peer->id, -1);
 154
 155   if (GNUNET_YES !=
 156     GNUNET_CONTAINER_multipeermap_remove (peers, &id, peer))
 157   {
 158     GNUNET_break (0);
 159     GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
 160                 "removing peer %s, not in peermap\n", GNUNET_i2s (&id));
 161   }
 162     if (NULL != peer->dhtget)
 163     {
 164       GNUNET_DHT_get_stop (peer->dhtget);
 165     }
 166       p = peer->path_head;
 167       while (NULL != p)
 168       {
 169         nextp = p->next;
 170         GNUNET_CONTAINER_DLL_remove (peer->path_head, peer->path_tail, p);
 171         path_destroy (p);
 172         p = nextp;
 173       }
 174         tunnel_destroy_empty (peer->tunnel);
 175         GNUNET_free (peer);
 176         return GNUNET_OK;
 177 }
 178
 179
 180 /**
 181  * Returns if peer is used (has a tunnel, is neighbor).
 182  *
 183  * @peer Peer to check.
 184  *
 185  * @return GNUNET_YES if peer is in use.
 186  */
 187 static int
 188 peer_is_used (struct MeshPeer *peer)
 189 {
 190   struct MeshPeerPath *p;
 191
 192   if (NULL != peer->tunnel)
 193     return GNUNET_YES;
 194
 195   for (p = peer->path_head; NULL != p; p = p->next)
 196   {
 197     if (p->length < 3)
 198       return GNUNET_YES;
 199   }
 200     return GNUNET_NO;
 201 }
 202
 203
 204 /**
 205  * Iterator over all the peers to get the oldest timestamp.
 206  *
 207  * @param cls Closure (unsued).
 208  * @param key ID of the peer.
 209  * @param value Peer_Info of the peer.
 210  */
 211 static int
 212 peer_get_oldest (void *cls,
 213                  const struct GNUNET_PeerIdentity *key,
 214                  void *value)
 215 {
 216   struct MeshPeer *p = value;
 217   struct GNUNET_TIME_Absolute *abs = cls;
 218
 219   /* Don't count active peers */
 220   if (GNUNET_YES == peer_is_used (p))
 221     return GNUNET_YES;
 222
 223   if (abs->abs_value_us < p->last_contact.abs_value_us)
 224     abs->abs_value_us = p->last_contact.abs_value_us;
 225
 226   return GNUNET_YES;
 227 }
 228
 229
 230 /**
 231  * Iterator over all the peers to remove the oldest entry.
 232  *
 233  * @param cls Closure (unsued).
 234  * @param key ID of the peer.
 235  * @param value Peer_Info of the peer.
 236  */
 237 static int
 238 peer_timeout (void *cls,
 239               const struct GNUNET_PeerIdentity *key,
 240               void *value)
 241 {
 242   struct MeshPeer *p = value;
 243   struct GNUNET_TIME_Absolute *abs = cls;
 244
 245   if (p->last_contact.abs_value_us == abs->abs_value_us &&
 246     GNUNET_NO == peer_is_used (p))
 247   {
 248     peer_destroy (p);
 249     return GNUNET_NO;
 250   }
 251     return GNUNET_YES;
 252 }
 253
 254
 255 /**
 256  * Delete oldest unused peer.
 257  */
 258 static void
 259 peer_delete_oldest (void)
 260 {
 261   struct GNUNET_TIME_Absolute abs;
 262
 263   abs = GNUNET_TIME_UNIT_FOREVER_ABS;
 264
 265   GNUNET_CONTAINER_multipeermap_iterate (peers,
 266                                          &peer_get_oldest,
 267                                          &abs);
 268   GNUNET_CONTAINER_multipeermap_iterate (peers,
 269                                          &peer_timeout,
 270                                          &abs);
 271 }
 272
 273
 274 /**
 275  * Retrieve the MeshPeer stucture associated with the peer, create one
 276  * and insert it in the appropriate structures if the peer is not known yet.
 277  *
 278  * @param peer Full identity of the peer.
 279  *
 280  * @return Existing or newly created peer info.
 281  */
 282 static struct MeshPeer *
 283 peer_get (const struct GNUNET_PeerIdentity *peer_id)
 284 {
 285   struct MeshPeer *peer;
 286
 287   peer = GNUNET_CONTAINER_multipeermap_get (peers, peer_id);
 288   if (NULL == peer)
 289   {
 290     peer = GNUNET_new (struct MeshPeer);
 291     if (GNUNET_CONTAINER_multipeermap_size (peers) > max_peers)
 292     {
 293       peer_delete_oldest ();
 294     }
 295         GNUNET_CONTAINER_multipeermap_put (peers, peer_id, peer,
 296                                            GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST);
 297         peer->id = GNUNET_PEER_intern (peer_id);
 298   }
 299     peer->last_contact = GNUNET_TIME_absolute_get();
 300
 301     return peer;
 302 }
 303
 304
 305 /**
 306  * Retrieve the MeshPeer stucture associated with the peer, create one
 307  * and insert it in the appropriate structures if the peer is not known yet.
 308  *
 309  * @param peer Short identity of the peer.
 310  *
 311  * @return Existing or newly created peer info.
 312  */
 313 static struct MeshPeer *
 314 peer_get_short (const GNUNET_PEER_Id peer)
 315 {
 316   return peer_get (GNUNET_PEER_resolve2 (peer));
 317 }
 318
 319
 320 /**
 321  * Get a cost of a path for a peer considering existing tunnel connections.
 322  *
 323  * @param peer Peer towards which the path is considered.
 324  * @param path Candidate path.
 325  *
 326  * @return Cost of the path (path length + number of overlapping nodes)
 327  */
 328 static unsigned int
 329 peer_get_path_cost (const struct MeshPeer *peer,
 330                     const struct MeshPeerPath *path)
 331 {
 332   struct MeshConnection *c;
 333   unsigned int overlap;
 334   unsigned int i;
 335   unsigned int j;
 336
 337   if (NULL == path)
 338     return 0;
 339
 340   overlap = 0;
 341   GNUNET_assert (NULL != peer->tunnel);
 342
 343   for (i = 0; i < path->length; i++)
 344   {
 345     for (c = peer->tunnel->connection_head; NULL != c; c = c->next)
 346     {
 347       for (j = 0; j < c->path->length; j++)
 348       {
 349         if (path->peers[i] == c->path->peers[j])
 350         {
 351           overlap++;
 352           break;
 353         }
 354       }
 355     }
 356   }
 357   return (path->length + overlap) * (path->score * -1);
 358 }
 359
 360
 361 /**
 362  * Choose the best path towards a peer considering the tunnel properties.
 363  *
 364  * @param peer The destination peer.
 365  *
 366  * @return Best current known path towards the peer, if any.
 367  */
 368 static struct MeshPeerPath *
 369 peer_get_best_path (const struct MeshPeer *peer)
 370 {
 371   struct MeshPeerPath *best_p;
 372   struct MeshPeerPath *p;
 373   struct MeshConnection *c;
 374   unsigned int best_cost;
 375   unsigned int cost;
 376
 377   best_cost = UINT_MAX;
 378   best_p = NULL;
 379   for (p = peer->path_head; NULL != p; p = p->next)
 380   {
 381     for (c = peer->tunnel->connection_head; NULL != c; c = c->next)
 382       if (c->path == p)
 383         break;
 384       if (NULL != c)
 385         continue; /* If path is in use in a connection, skip it. */
 386
 387             if ((cost = peer_get_path_cost (peer, p)) < best_cost)
 388             {
 389               best_cost = cost;
 390               best_p = p;
 391             }
 392   }
 393     return best_p;
 394 }
 395
 396
 397 /**
 398  * Add the path to the peer and update the path used to reach it in case this
 399  * is the shortest.
 400  *
 401  * @param peer_info Destination peer to add the path to.
 402  * @param path New path to add. Last peer must be the peer in arg 1.
 403  *             Path will be either used of freed if already known.
 404  * @param trusted Do we trust that this path is real?
 405  */
 406 void
 407 peer_add_path (struct MeshPeer *peer_info, struct MeshPeerPath *path,
 408                int trusted)
 409 {
 410   struct MeshPeerPath *aux;
 411   unsigned int l;
 412   unsigned int l2;
 413
 414   if ((NULL == peer_info) || (NULL == path))
 415   {
 416     GNUNET_break (0);
 417     path_destroy (path);
 418     return;
 419   }
 420     if (path->peers[path->length - 1] != peer_info->id)
 421     {
 422       GNUNET_break (0);
 423       path_destroy (path);
 424       return;
 425     }
 426       if (2 >= path->length && GNUNET_NO == trusted)
 427       {
 428         /* Only allow CORE to tell us about direct paths */
 429         path_destroy (path);
 430         return;
 431       }
 432         for (l = 1; l < path->length; l++)
 433         {
 434           if (path->peers[l] == myid)
 435           {
 436             GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "shortening path by %u\n", l);
 437             for (l2 = 0; l2 < path->length - l; l2++)
 438             {
 439               path->peers[l2] = path->peers[l + l2];
 440             }
 441                   path->length -= l;
 442                   l = 1;
 443                   path->peers =
 444                             GNUNET_realloc (path->peers, path->length * sizeof (GNUNET_PEER_Id));
 445           }
 446         }
 447
 448           GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "adding path [%u] to peer %s\n",
 449                       path->length, peer2s (peer_info));
 450
 451           l = path_get_length (path);
 452           if (0 == l)
 453           {
 454             path_destroy (path);
 455             return;
 456           }
 457
 458             GNUNET_assert (peer_info->id == path->peers[path->length - 1]);
 459             for (aux = peer_info->path_head; aux != NULL; aux = aux->next)
 460             {
 461               l2 = path_get_length (aux);
 462               if (l2 > l)
 463               {
 464                 GNUNET_CONTAINER_DLL_insert_before (peer_info->path_head,
 465                                                     peer_info->path_tail, aux, path);
 466                 return;
 467               }
 468                   else
 469                   {
 470                     if (l2 == l && memcmp (path->peers, aux->peers, l) == 0)
 471                     {
 472                       path_destroy (path);
 473                       return;
 474                     }
 475                   }
 476             }
 477               GNUNET_CONTAINER_DLL_insert_tail (peer_info->path_head, peer_info->path_tail,
 478                                                 path);
 479               return;
 480 }
 481
 482
 483 /**
 484  * Add the path to the origin peer and update the path used to reach it in case
 485  * this is the shortest.
 486  * The path is given in peer_info -> destination, therefore we turn the path
 487  * upside down first.
 488  *
 489  * @param peer_info Peer to add the path to, being the origin of the path.
 490  * @param path New path to add after being inversed.
 491  *             Path will be either used or freed.
 492  * @param trusted Do we trust that this path is real?
 493  */
 494 static void
 495 peer_add_path_to_origin (struct MeshPeer *peer_info,
 496                          struct MeshPeerPath *path, int trusted)
 497 {
 498   if (NULL == path)
 499     return;
 500   path_invert (path);
 501   peer_add_path (peer_info, path, trusted);
 502 }
 503
 504
 505 /******************************************************************************/
 506 /********************************    API    ***********************************/
 507 /******************************************************************************/
 508
 509 /**
 510  * Initialize the peer subsystem.
 511  *
 512  * @param c Configuration.
 513  */
 514 void
 515 GMP_init (const struct GNUNET_CONFIGURATION_Handle *c)
 516 {
 517   peers = GNUNET_CONTAINER_multipeermap_create (128, GNUNET_NO);
 518   if (GNUNET_OK !=
 519       GNUNET_CONFIGURATION_get_value_number (c, "MESH", "MAX_PEERS",
 520                                              &max_peers))
 521   {
 522     GNUNET_log_config_invalid (GNUNET_ERROR_TYPE_WARNING,
 523                                "MESH", "MAX_PEERS", "USING DEFAULT");
 524     max_peers = 1000;
 525   }
 526 }
 527
 528 /**
 529  * Shut down the peer subsystem.
 530  */
 531 void
 532 GMP_shutdown (void)
 533 {
 534   GNUNET_CONTAINER_multipeermap_iterate (peers, &shutdown_tunnel, NULL);
 535 }
 536
 537
 538 /**
 539  * Try to establish a new connection to this peer in the given tunnel.
 540  * If the peer doesn't have any path to it yet, try to get one.
 541  * If the peer already has some path, send a CREATE CONNECTION towards it.
 542  *
 543  * @param peer PeerInfo of the peer.
 544  */
 545 void
 546 GMP_connect (struct MeshPeer *peer)
 547 {
 548   struct MeshTunnel2 *t;
 549   struct MeshPeerPath *p;
 550   struct MeshConnection *c;
 551   int rerun_dhtget;
 552
 553   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 554               "peer_connect towards %s\n",
 555               peer2s (peer));
 556   t = peer->tunnel;
 557   c = NULL;
 558   rerun_dhtget = GNUNET_NO;
 559
 560   if (NULL != peer->path_head)
 561   {
 562     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "path exists\n");
 563     p = peer_get_best_path (peer);
 564     if (NULL != p)
 565     {
 566       GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "  %u hops\n", p->length);
 567       c = tunnel_use_path (t, p);
 568       if (NULL == c)
 569       {
 570         /* This case can happen when the path includes a first hop that is
 571          * not yet known to be connected.
 572          *
 573          * This happens quite often during testing when running mesh
 574          * under valgrind: core connect notifications come very late and the
 575          * DHT result has already come and created a valid path.
 576          * In this case, the peer->connections hashmap will be NULL and
 577          * tunnel_use_path will not be able to create a connection from that
 578          * path.
 579          *
 580          * Re-running the DHT GET should give core time to callback.
 581          */
 582         GNUNET_break(0);
 583         rerun_dhtget = GNUNET_YES;
 584       }
 585       else
 586       {
 587         send_connection_create (c);
 588         return;
 589       }
 590     }
 591   }
 592
 593   if (NULL != peer->dhtget && GNUNET_YES == rerun_dhtget)
 594   {
 595     GNUNET_DHT_get_stop (peer->dhtget);
 596     peer->dhtget = NULL;
 597     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 598                 "  Stopping DHT GET for peer %s\n", peer2s (peer));
 599   }
 600
 601   if (NULL == peer->dhtget)
 602   {
 603     const struct GNUNET_PeerIdentity *id;
 604     struct GNUNET_HashCode phash;
 605
 606     id = GNUNET_PEER_resolve2 (peer->id);
 607     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 608                 "  Starting DHT GET for peer %s\n", peer2s (peer));
 609     GNUNET_CRYPTO_hash (&id, sizeof (struct GNUNET_PeerIdentity), &phash);
 610     peer->dhtget = GNUNET_DHT_get_start (dht_handle,    /* handle */
 611                                           GNUNET_BLOCK_TYPE_MESH_PEER, /* type */
 612                                           &phash,     /* key to search */
 613                                           dht_replication_level, /* replication level */
 614                                           GNUNET_DHT_RO_RECORD_ROUTE |
 615                                           GNUNET_DHT_RO_DEMULTIPLEX_EVERYWHERE,
 616                                           NULL,       /* xquery */
 617                                           0,     /* xquery bits */
 618                                           &dht_get_id_handler, peer);
 619     if (MESH_TUNNEL_NEW == t->state)
 620       tunnel_change_state (t, MESH_TUNNEL_SEARCHING);
 621   }
 622 }