src/cadet/gnunet-service-cadet-new_paths.c

   1 /*
   2      This file is part of GNUnet.
   3      Copyright (C) 2001-2017 GNUnet e.V.
   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., 51 Franklin Street, Fifth Floor,
  18      Boston, MA 02110-1301, USA.
  19 */
  20 /**
  21  * @file cadet/gnunet-service-cadet-new_paths.c
  22  * @brief Information we track per path.
  23  * @author Bartlomiej Polot
  24  * @author Christian Grothoff
  25  *
  26  * TODO:
  27  * - path desirability score calculations are not done
  28  *   (and will be tricky to have during path changes)
  29  */
  30 #include "platform.h"
  31 #include "gnunet-service-cadet-new_connection.h"
  32 #include "gnunet-service-cadet-new_peer.h"
  33 #include "gnunet-service-cadet-new_paths.h"
  34
  35
  36 #define LOG(level, ...) GNUNET_log_from(level,"cadet-pat",__VA_ARGS__)
  37
  38
  39 /**
  40  * Information regarding a possible path to reach a peer.
  41  */
  42 struct CadetPeerPath
  43 {
  44
  45   /**
  46    * Array of all the peers on the path.  If @e hn is non-NULL, the
  47    * last one is our owner.
  48    */
  49   struct CadetPeerPathEntry **entries;
  50
  51   /**
  52    * Node of this path in the owner's heap.  Used to update our position
  53    * in the heap whenever our @e desirability changes.
  54    */
  55   struct GNUNET_CONTAINER_HeapNode *hn;
  56
  57   /**
  58    * Connections using this path, by destination peer
  59    * (each hop of the path could correspond to an
  60    * active connection).
  61    */
  62   struct GNUNET_CONTAINER_MultiPeerMap *connections;
  63
  64   /**
  65    * Desirability of the path. How unique is it for the various peers
  66    * on it?
  67    */
  68   GNUNET_CONTAINER_HeapCostType desirability;
  69
  70   /**
  71    * Length of the @e entries array.
  72    */
  73   unsigned int entries_length;
  74
  75 };
  76
  77
  78 /**
  79  * Return how much we like keeping the path.  This is an aggregate
  80  * score based on various factors, including the age of the path
  81  * (older == better), and the value of this path to all of its ajacent
  82  * peers.  For example, long paths that end at a peer that we have no
  83  * shorter way to reach are very desirable, while long paths that end
  84  * at a peer for which we have a shorter way as well are much less
  85  * desirable.  Higher values indicate more valuable paths.  The
  86  * returned value should be used to decide which paths to remember.
  87  *
  88  * @param path path to return the length for
  89  * @return desirability of the path, larger is more desirable
  90  */
  91 GNUNET_CONTAINER_HeapCostType
  92 GCPP_get_desirability (const struct CadetPeerPath *path)
  93 {
  94   return path->desirability;
  95 }
  96
  97
  98 /**
  99  * Return connection to @a destination using @a path, or return
 100  * NULL if no such connection exists.
 101  *
 102  * @param path path to traverse
 103  * @param destination destination node to get to, must be on path
 104  * @param off offset of @a destination on @a path
 105  * @return NULL if we have no existing connection
 106  *         otherwise connection from us to @a destination via @a path
 107  */
 108 struct CadetConnection *
 109 GCPP_get_connection (struct CadetPeerPath *path,
 110                      struct CadetPeer *destination,
 111                      unsigned int off)
 112 {
 113   struct CadetPeerPathEntry *entry;
 114
 115   GNUNET_assert (off < path->entries_length);
 116   entry = path->entries[off];
 117   GNUNET_assert (entry->peer == destination);
 118   return entry->cc;
 119 }
 120
 121
 122 /**
 123  * Notify @a path that it is used for connection @a cc
 124  * which ends at the path's offset @a off.
 125  *
 126  * @param path the path to remember the @a cc
 127  * @param off the offset where the @a cc ends
 128  * @param cc the connection to remember
 129  */
 130 void
 131 GCPP_add_connection (struct CadetPeerPath *path,
 132                      unsigned int off,
 133                      struct CadetConnection *cc)
 134 {
 135   struct CadetPeerPathEntry *entry;
 136
 137   LOG (GNUNET_ERROR_TYPE_DEBUG,
 138        "Adding connection %s to path %s at offset %u\n",
 139        GCC_2s (cc),
 140        GCPP_2s (path),
 141        off);
 142   GNUNET_assert (off < path->entries_length);
 143   entry = path->entries[off];
 144   GNUNET_assert (NULL == entry->cc);
 145   entry->cc = cc;
 146 }
 147
 148
 149
 150 /**
 151  * Notify @a path that it is no longer used for connection @a cc which
 152  * ended at the path's offset @a off.
 153  *
 154  * @param path the path to forget the @a cc
 155  * @param off the offset where the @a cc ended
 156  * @param cc the connection to forget
 157  */
 158 void
 159 GCPP_del_connection (struct CadetPeerPath *path,
 160                      unsigned int off,
 161                      struct CadetConnection *cc)
 162 {
 163   struct CadetPeerPathEntry *entry;
 164
 165   LOG (GNUNET_ERROR_TYPE_DEBUG,
 166        "Removing connection %s to path %s at offset %u\n",
 167        GCC_2s (cc),
 168        GCPP_2s (path),
 169        off);
 170   GNUNET_assert (off < path->entries_length);
 171   entry = path->entries[off];
 172   GNUNET_assert (cc == entry->cc);
 173   entry->cc = NULL;
 174 }
 175
 176
 177 /**
 178  * This path is no longer needed, free resources.
 179  *
 180  * @param path path resources to free
 181  */
 182 static void
 183 path_destroy (struct CadetPeerPath *path)
 184 {
 185   LOG (GNUNET_ERROR_TYPE_DEBUG,
 186        "Destroying path %s\n",
 187        GCPP_2s (path));
 188   GNUNET_assert (0 ==
 189                  GNUNET_CONTAINER_multipeermap_size (path->connections));
 190   GNUNET_CONTAINER_multipeermap_destroy (path->connections);
 191   for (unsigned int i=0;i<path->entries_length;i++)
 192     GNUNET_free (path->entries[i]);
 193   GNUNET_free (path->entries);
 194   GNUNET_free (path);
 195 }
 196
 197
 198 /**
 199  * The owning peer of this path is no longer interested in maintaining
 200  * it, so the path should be discarded or shortened (in case a
 201  * previous peer on the path finds the path desirable).
 202  *
 203  * @param path the path that is being released
 204  */
 205 void
 206 GCPP_release (struct CadetPeerPath *path)
 207 {
 208   struct CadetPeerPathEntry *entry;
 209
 210   LOG (GNUNET_ERROR_TYPE_DEBUG,
 211        "Owner releases path %s\n",
 212        GCPP_2s (path));
 213   path->hn = NULL;
 214   entry = path->entries[path->entries_length - 1];
 215   while (1)
 216   {
 217     /* cut 'off' end of path, verifying it is not in use */
 218     GNUNET_assert (NULL ==
 219                    GNUNET_CONTAINER_multipeermap_get (path->connections,
 220                                                       GCP_get_id (entry->peer)));
 221     GCP_path_entry_remove (entry->peer,
 222                            entry,
 223                            path->entries_length - 1);
 224     path->entries_length--; /* We don't bother shrinking the 'entries' array,
 225                                as it's probably not worth it. */
 226     GNUNET_free (entry);
 227     if (0 == path->entries_length)
 228       break; /* the end */
 229
 230     /* see if new peer at the end likes this path any better */
 231     entry = path->entries[path->entries_length - 1];
 232     path->hn = GCP_attach_path (entry->peer,
 233                                 path,
 234                                 path->entries_length,
 235                                 GNUNET_NO);
 236     if (NULL != path->hn)
 237       return; /* yep, got attached, we are done. */
 238   }
 239
 240   /* nobody wants us, discard the path */
 241   path_destroy (path);
 242 }
 243
 244
 245 /**
 246  * Updates the score for an entry on the path based
 247  * on our experiences with using @a path.
 248  *
 249  * @param path the path to update
 250  * @param off offset of the entry to update
 251  * @param delta change in the score to apply
 252  */
 253 void
 254 GCPP_update_score (struct CadetPeerPath *path,
 255                    unsigned int off,
 256                    int delta)
 257 {
 258   struct CadetPeerPathEntry *entry;
 259
 260   GNUNET_assert (off < path->entries_length);
 261   entry = path->entries[off];
 262
 263   /* Add delta, with checks for overflows */
 264   if (delta >= 0)
 265   {
 266     if (delta + entry->score < entry->score)
 267       entry->score = INT_MAX;
 268     else
 269       entry->score += delta;
 270   }
 271   else
 272   {
 273     if (delta + entry->score > entry->score)
 274       entry->score = INT_MIN;
 275     else
 276       entry->score += delta;
 277   }
 278
 279   /* FIXME: update path desirability! */
 280 }
 281
 282
 283 /**
 284  * Closure for #find_peer_at() and #check_match().
 285  */
 286 struct CheckMatchContext
 287 {
 288
 289   /**
 290    * Set to a matching path, if any.
 291    */
 292   struct CadetPeerPath *match;
 293
 294   /**
 295    * Array the combined paths.
 296    */
 297   struct CadetPeer **cpath;
 298
 299   /**
 300    * How long is the @e cpath array?
 301    */
 302   unsigned int cpath_length;
 303
 304 };
 305
 306
 307 /**
 308  * Check if the given path is identical on all of the
 309  * hops until @a off, and not longer than @a off.  If the
 310  * @a path matches, store it in `match`.
 311  *
 312  * @param cls the `struct CheckMatchContext` to check against
 313  * @param path the path to check
 314  * @param off offset to check at
 315  * @return #GNUNET_YES (continue to iterate), or if found #GNUNET_NO
 316  */
 317 static int
 318 check_match (void *cls,
 319              struct CadetPeerPath *path,
 320              unsigned int off)
 321 {
 322   struct CheckMatchContext *cm_ctx = cls;
 323
 324   GNUNET_assert (path->entries_length > off);
 325   if ( (path->entries_length != off + 1) &&
 326        (off + 1 != cm_ctx->cpath_length) )
 327     return GNUNET_YES; /* too long, goes somewhere else already, thus cannot be useful */
 328   for (unsigned int i=0;i<off;i++)
 329     if (cm_ctx->cpath[i] !=
 330         GCPP_get_peer_at_offset (path,
 331                                  i))
 332       return GNUNET_YES; /* missmatch, ignore */
 333   cm_ctx->match = path;
 334   return GNUNET_NO; /* match, we are done! */
 335 }
 336
 337
 338 /**
 339  * Extend path @a path by the @a num_peers from the @a peers
 340  * array, assuming the owners past the current owner want it.
 341  *
 342  * @param path path to extend
 343  * @param peers list of peers beyond the end of @a path
 344  * @param num_peers length of the @a peers array
 345  * @param force force attachment, even if we have other
 346  *        paths already
 347  */
 348 static void
 349 extend_path (struct CadetPeerPath *path,
 350              struct CadetPeer **peers,
 351              unsigned int num_peers,
 352              int force)
 353 {
 354   unsigned int old_len = path->entries_length;
 355   struct GNUNET_CONTAINER_HeapNode *hn;
 356   int i;
 357
 358   /* If we extend an existing path, detach it from the
 359      old owner and re-attach to the new one */
 360   hn = NULL;
 361   for (i=num_peers-1;i>=0;i--)
 362   {
 363     /* FIXME: note that path->desirability is used, but not yet updated here! */
 364     hn = GCP_attach_path (peers[i],
 365                           path,
 366                           old_len + (unsigned int) i,
 367                           GNUNET_YES);
 368     if (NULL != hn)
 369       break;
 370   }
 371   if (NULL == hn)
 372     return; /* none of the peers is interested in this path */
 373   GCP_detach_path (path->entries[old_len-1]->peer,
 374                    path,
 375                    path->hn);
 376   path->hn = hn;
 377   GNUNET_array_grow (path->entries,
 378                      path->entries_length,
 379                      old_len + i);
 380   for (;i >= 0;i--)
 381   {
 382     struct CadetPeerPathEntry *entry = GNUNET_new (struct CadetPeerPathEntry);
 383
 384     path->entries[old_len + i] = entry;
 385     entry->peer = peers[i];
 386     entry->path = path;
 387     GCP_path_entry_add (entry->peer,
 388                         entry,
 389                         old_len + i);
 390   }
 391   LOG (GNUNET_ERROR_TYPE_DEBUG,
 392        "Extended path %s\n",
 393        GCPP_2s (path));
 394 }
 395
 396
 397 /**
 398  * Create a peer path based on the result of a DHT lookup.  If we
 399  * already know this path, or one that is longer, simply return NULL.
 400  * Otherwise, we try to extend an existing path, or create a new one
 401  * if applicable.
 402  *
 403  * @param get_path path of the get request
 404  * @param get_path_length lenght of @a get_path
 405  * @param put_path path of the put request
 406  * @param put_path_length length of the @a put_path
 407  * @return a path through the network
 408  */
 409 void
 410 GCPP_try_path_from_dht (const struct GNUNET_PeerIdentity *get_path,
 411                         unsigned int get_path_length,
 412                         const struct GNUNET_PeerIdentity *put_path,
 413                         unsigned int put_path_length)
 414 {
 415   struct CadetPeer *cpath[get_path_length + put_path_length];
 416   struct CheckMatchContext cm_ctx;
 417   struct CadetPeerPath *path;
 418   struct GNUNET_CONTAINER_HeapNode *hn;
 419   int i;
 420
 421   /* precompute 'cpath' so we can avoid doing the lookups lots of times */
 422   for (unsigned int off=0;off<get_path_length + put_path_length;off++)
 423   {
 424     const struct GNUNET_PeerIdentity *pid;
 425
 426     pid = (off < get_path_length)
 427       ? &get_path[get_path_length - off]
 428       : &put_path[get_path_length + put_path_length - off];
 429     cpath[off] = GCP_get (pid,
 430                           GNUNET_YES);
 431   }
 432
 433   /* First figure out if this path is a subset of an existing path, an
 434      extension of an existing path, or a new path. */
 435   cm_ctx.cpath_length = get_path_length + put_path_length;
 436   cm_ctx.cpath = cpath;
 437   cm_ctx.match = NULL;
 438   for (i=get_path_length + put_path_length-1;i>=0;i--)
 439   {
 440     GCP_iterate_paths_at (cpath[i],
 441                           (unsigned int) i,
 442                           &check_match,
 443                           &cm_ctx);
 444     if (NULL != cm_ctx.match)
 445     {
 446       if (i == get_path_length + put_path_length - 1)
 447       {
 448         /* Existing path includes this one, nothing to do! */
 449         LOG (GNUNET_ERROR_TYPE_DEBUG,
 450              "Path discovered from DHT is already known\n");
 451         return;
 452       }
 453       if (cm_ctx.match->entries_length == i + 1)
 454       {
 455         /* Existing path ends in the middle of new path, extend it! */
 456         LOG (GNUNET_ERROR_TYPE_DEBUG,
 457              "Trying to extend existing path %s by additional links discovered from DHT\n",
 458              GCPP_2s (cm_ctx.match));
 459         extend_path (cm_ctx.match,
 460                      &cpath[i],
 461                      get_path_length + put_path_length - i,
 462                      GNUNET_NO);
 463         return;
 464       }
 465     }
 466   }
 467
 468   /* No match at all, create completely new path */
 469   path = GNUNET_new (struct CadetPeerPath);
 470
 471   /* First, try to attach it */
 472   hn = NULL;
 473   for (i=get_path_length + put_path_length-1;i>=0;i--)
 474   {
 475     path->entries_length = i + 1;
 476     /* FIXME: note that path->desirability is used, but not yet initialized here! */
 477     hn = GCP_attach_path (cpath[i],
 478                           path,
 479                           (unsigned int) i,
 480                           GNUNET_NO);
 481     if (NULL != hn)
 482       break;
 483   }
 484   if (NULL == hn)
 485   {
 486     /* None of the peers on the path care about it. */
 487     LOG (GNUNET_ERROR_TYPE_DEBUG,
 488          "Path discovered from DHT is not interesting to us\n");
 489     GNUNET_free (path);
 490     return;
 491   }
 492   path->hn = hn;
 493   path->entries_length = i + 1;
 494   path->entries = GNUNET_new_array (path->entries_length,
 495                                     struct CadetPeerPathEntry *);
 496   for (;i>=0;i--)
 497   {
 498     struct CadetPeerPathEntry *entry = GNUNET_new (struct CadetPeerPathEntry);
 499
 500     path->entries[i] = entry;
 501     entry->peer = cpath[i];
 502     entry->path = path;
 503     GCP_path_entry_add (entry->peer,
 504                         entry,
 505                         i);
 506   }
 507   LOG (GNUNET_ERROR_TYPE_DEBUG,
 508        "Created new path %s based on information from DHT\n",
 509        GCPP_2s (path));
 510 }
 511
 512
 513 /**
 514  * We got an incoming connection, obtain the corresponding path.
 515  *
 516  * @param path_length number of segments on the @a path
 517  * @param pids path through the network, in reverse order (we are at the end at index @a path_length)
 518  * @return corresponding path object
 519  */
 520 struct CadetPeerPath *
 521 GCPP_get_path_from_route (unsigned int path_length,
 522                           const struct GNUNET_PeerIdentity *pids)
 523 {
 524   struct CheckMatchContext cm_ctx;
 525   struct CadetPeer *cpath[path_length];
 526   struct CadetPeerPath *path;
 527
 528   /* precompute inverted 'cpath' so we can avoid doing the lookups and
 529      have the correct order */
 530   for (unsigned int off=0;off<path_length;off++)
 531     cpath[off] = GCP_get (&pids[path_length - 1 - off],
 532                           GNUNET_YES);
 533
 534   /* First figure out if this path is a subset of an existing path, an
 535      extension of an existing path, or a new path. */
 536   cm_ctx.cpath = cpath;
 537   cm_ctx.cpath_length = path_length;
 538   cm_ctx.match = NULL;
 539   for (int i=path_length-1;i>=0;i--)
 540   {
 541     GCP_iterate_paths_at (cpath[i],
 542                           (unsigned int) i,
 543                           &check_match,
 544                           &cm_ctx);
 545     if (NULL != cm_ctx.match)
 546     {
 547       if (i == path_length - 1)
 548       {
 549         /* Existing path includes this one, return the match! */
 550         LOG (GNUNET_ERROR_TYPE_DEBUG,
 551              "Returning existing path %s as inverse for incoming connection\n",
 552              GCPP_2s (cm_ctx.match));
 553         return cm_ctx.match;
 554       }
 555       if (cm_ctx.match->entries_length == i + 1)
 556       {
 557         /* Existing path ends in the middle of new path, extend it! */
 558         LOG (GNUNET_ERROR_TYPE_DEBUG,
 559              "Extending existing path %s to create inverse for incoming connection\n",
 560              GCPP_2s (cm_ctx.match));
 561         extend_path (cm_ctx.match,
 562                      &cpath[i],
 563                      path_length - i,
 564                      GNUNET_YES);
 565         /* Check that extension was successful */
 566         GNUNET_assert (cm_ctx.match->entries_length == path_length);
 567         return cm_ctx.match;
 568       }
 569       /* Eh, we found a match but couldn't use it? Something is wrong. */
 570       GNUNET_break (0);
 571     }
 572   }
 573
 574   /* No match at all, create completely new path */
 575   path = GNUNET_new (struct CadetPeerPath);
 576   path->entries_length = path_length;
 577   path->entries = GNUNET_new_array (path->entries_length,
 578                                     struct CadetPeerPathEntry *);
 579   for (int i=path_length-1;i>=0;i--)
 580   {
 581     struct CadetPeerPathEntry *entry = GNUNET_new (struct CadetPeerPathEntry);
 582
 583     path->entries[i] = entry;
 584     entry->peer = cpath[i];
 585     entry->path = path;
 586     GCP_path_entry_add (entry->peer,
 587                         entry,
 588                         i);
 589   }
 590   LOG (GNUNET_ERROR_TYPE_DEBUG,
 591        "Created new path %s to create inverse for incoming connection\n",
 592        GCPP_2s (path));
 593   path->hn = GCP_attach_path (cpath[path_length - 1],
 594                               path,
 595                               path_length - 1,
 596                               GNUNET_YES);
 597   return path;
 598 }
 599
 600
 601 /**
 602  * Return the length of the path.  Excludes one end of the
 603  * path, so the loopback path has length 0.
 604  *
 605  * @param path path to return the length for
 606  * @return number of peers on the path
 607  */
 608 unsigned int
 609 GCPP_get_length (struct CadetPeerPath *path)
 610 {
 611   return path->entries_length;
 612 }
 613
 614
 615 /**
 616  * Find peer's offset on path.
 617  *
 618  * @param path path to search
 619  * @param cp peer to look for
 620  * @return offset of @a cp on @a path, or UINT_MAX if not found
 621  */
 622 unsigned int
 623 GCPP_find_peer (struct CadetPeerPath *path,
 624                 struct CadetPeer *cp)
 625 {
 626   for (unsigned int off = 0;
 627        off < path->entries_length;
 628        off++)
 629     if (cp == GCPP_get_peer_at_offset (path,
 630                                        off))
 631       return off;
 632   return UINT_MAX;
 633 }
 634
 635
 636 /**
 637  * Obtain the peer at offset @a off in @a path.
 638  *
 639  * @param path peer path to inspect
 640  * @param off offset to return, must be smaller than path length
 641  * @return the peer at offset @a off
 642  */
 643 struct CadetPeer *
 644 GCPP_get_peer_at_offset (struct CadetPeerPath *path,
 645                          unsigned int off)
 646 {
 647   GNUNET_assert (off < path->entries_length);
 648   return path->entries[off]->peer;
 649 }
 650
 651
 652 /**
 653  * Convert a path to a human-readable string.
 654  *
 655  * @param path path to convert
 656  * @return string, to be freed by caller (unlike other *_2s APIs!)
 657  */
 658 const char *
 659 GCPP_2s (struct CadetPeerPath *path)
 660 {
 661   static char buf[2048];
 662   size_t off;
 663   const unsigned int max_plen = (sizeof(buf) - 16) / 5 - 2; /* 5 characters per entry */
 664
 665   off = 0;
 666   for (unsigned int i = 0;
 667        i < path->entries_length;
 668        i++)
 669   {
 670     if ( (path->entries_length > max_plen) &&
 671          (i == max_plen / 2) )
 672       off += GNUNET_snprintf (&buf[off],
 673                               sizeof (buf) - off,
 674                               "...-");
 675     if ( (path->entries_length > max_plen) &&
 676          (i > max_plen / 2) &&
 677          (i < path->entries_length - max_plen / 2) )
 678       continue;
 679     off += GNUNET_snprintf (&buf[off],
 680                             sizeof (buf) - off,
 681                             "%s%s",
 682                             GNUNET_i2s (GCP_get_id (GCPP_get_peer_at_offset (path,
 683                                                                              i))),
 684                             (i == path->entries_length -1) ? "" : "-");
 685   }
 686   GNUNET_snprintf (&buf[off],
 687                    sizeof (buf) - off,
 688                    "(%p)",
 689                    path);
 690   return buf;
 691 }
 692
 693
 694 /* end of gnunet-service-cadet-new_paths.c */