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   {
 328     LOG (GNUNET_ERROR_TYPE_DEBUG,
 329          "check_match missmatch because path %s is too long (%u vs. %u vs. %u)\n",
 330          GCPP_2s (path),
 331          path->entries_length,
 332          off + 1,
 333          cm_ctx->cpath_length);
 334     return GNUNET_YES; /* too long, goes somewhere else already, thus cannot be useful */
 335   }
 336   for (unsigned int i=0;i<off;i++)
 337     if (cm_ctx->cpath[i] !=
 338         GCPP_get_peer_at_offset (path,
 339                                  i))
 340     {
 341       LOG (GNUNET_ERROR_TYPE_DEBUG,
 342            "check_match path %s missmatches at offset %u\n",
 343            GCPP_2s (path),
 344            i);
 345       return GNUNET_YES; /* missmatch, ignore */
 346     }
 347   LOG (GNUNET_ERROR_TYPE_DEBUG,
 348        "check_match found match with path %s\n",
 349        GCPP_2s (path));
 350   cm_ctx->match = path;
 351   return GNUNET_NO; /* match, we are done! */
 352 }
 353
 354
 355 /**
 356  * Extend path @a path by the @a num_peers from the @a peers
 357  * array, assuming the owners past the current owner want it.
 358  *
 359  * @param path path to extend
 360  * @param peers list of peers beyond the end of @a path
 361  * @param num_peers length of the @a peers array
 362  * @param force force attachment, even if we have other
 363  *        paths already
 364  */
 365 static void
 366 extend_path (struct CadetPeerPath *path,
 367              struct CadetPeer **peers,
 368              unsigned int num_peers,
 369              int force)
 370 {
 371   unsigned int old_len = path->entries_length;
 372   struct GNUNET_CONTAINER_HeapNode *hn;
 373   int i;
 374
 375   /* If we extend an existing path, detach it from the
 376      old owner and re-attach to the new one */
 377   hn = NULL;
 378   for (i=num_peers-1;i>=0;i--)
 379   {
 380     /* FIXME: note that path->desirability is used, but not yet updated here! */
 381     hn = GCP_attach_path (peers[i],
 382                           path,
 383                           old_len + (unsigned int) i,
 384                           GNUNET_YES);
 385     if (NULL != hn)
 386       break;
 387   }
 388   if (NULL == hn)
 389     return; /* none of the peers is interested in this path */
 390   GCP_detach_path (path->entries[old_len-1]->peer,
 391                    path,
 392                    path->hn);
 393   path->hn = hn;
 394   GNUNET_array_grow (path->entries,
 395                      path->entries_length,
 396                      old_len + i);
 397   for (;i >= 0;i--)
 398   {
 399     struct CadetPeerPathEntry *entry = GNUNET_new (struct CadetPeerPathEntry);
 400
 401     path->entries[old_len + i] = entry;
 402     entry->peer = peers[i];
 403     entry->path = path;
 404     GCP_path_entry_add (entry->peer,
 405                         entry,
 406                         old_len + i);
 407   }
 408   LOG (GNUNET_ERROR_TYPE_DEBUG,
 409        "Extended path %s\n",
 410        GCPP_2s (path));
 411 }
 412
 413
 414 /**
 415  * Create a peer path based on the result of a DHT lookup.  If we
 416  * already know this path, or one that is longer, simply return NULL.
 417  * Otherwise, we try to extend an existing path, or create a new one
 418  * if applicable.
 419  *
 420  * @param get_path path of the get request
 421  * @param get_path_length lenght of @a get_path
 422  * @param put_path path of the put request
 423  * @param put_path_length length of the @a put_path
 424  * @return a path through the network
 425  */
 426 void
 427 GCPP_try_path_from_dht (const struct GNUNET_PeerIdentity *get_path,
 428                         unsigned int get_path_length,
 429                         const struct GNUNET_PeerIdentity *put_path,
 430                         unsigned int put_path_length)
 431 {
 432   struct CadetPeer *cpath[get_path_length + put_path_length];
 433   struct CheckMatchContext cm_ctx;
 434   struct CadetPeerPath *path;
 435   struct GNUNET_CONTAINER_HeapNode *hn;
 436   int i;
 437
 438   /* precompute 'cpath' so we can avoid doing the lookups lots of times */
 439   for (unsigned int off=0;off<get_path_length + put_path_length;off++)
 440   {
 441     const struct GNUNET_PeerIdentity *pid;
 442
 443     pid = (off < get_path_length)
 444       ? &get_path[get_path_length - off]
 445       : &put_path[get_path_length + put_path_length - off];
 446     cpath[off] = GCP_get (pid,
 447                           GNUNET_YES);
 448   }
 449
 450   /* First figure out if this path is a subset of an existing path, an
 451      extension of an existing path, or a new path. */
 452   cm_ctx.cpath_length = get_path_length + put_path_length;
 453   cm_ctx.cpath = cpath;
 454   cm_ctx.match = NULL;
 455   for (i=get_path_length + put_path_length-1;i>=0;i--)
 456   {
 457     GCP_iterate_paths_at (cpath[i],
 458                           (unsigned int) i,
 459                           &check_match,
 460                           &cm_ctx);
 461     if (NULL != cm_ctx.match)
 462     {
 463       if (i == get_path_length + put_path_length - 1)
 464       {
 465         /* Existing path includes this one, nothing to do! */
 466         LOG (GNUNET_ERROR_TYPE_DEBUG,
 467              "Path discovered from DHT is already known\n");
 468         return;
 469       }
 470       if (cm_ctx.match->entries_length == i + 1)
 471       {
 472         /* Existing path ends in the middle of new path, extend it! */
 473         LOG (GNUNET_ERROR_TYPE_DEBUG,
 474              "Trying to extend existing path %s by additional links discovered from DHT\n",
 475              GCPP_2s (cm_ctx.match));
 476         extend_path (cm_ctx.match,
 477                      &cpath[i],
 478                      get_path_length + put_path_length - i,
 479                      GNUNET_NO);
 480         return;
 481       }
 482     }
 483   }
 484
 485   /* No match at all, create completely new path */
 486   path = GNUNET_new (struct CadetPeerPath);
 487
 488   /* First, try to attach it */
 489   hn = NULL;
 490   for (i=get_path_length + put_path_length-1;i>=0;i--)
 491   {
 492     path->entries_length = i + 1;
 493     /* FIXME: note that path->desirability is used, but not yet initialized here! */
 494     hn = GCP_attach_path (cpath[i],
 495                           path,
 496                           (unsigned int) i,
 497                           GNUNET_NO);
 498     if (NULL != hn)
 499       break;
 500   }
 501   if (NULL == hn)
 502   {
 503     /* None of the peers on the path care about it. */
 504     LOG (GNUNET_ERROR_TYPE_DEBUG,
 505          "Path discovered from DHT is not interesting to us\n");
 506     GNUNET_free (path);
 507     return;
 508   }
 509   path->hn = hn;
 510   path->entries_length = i + 1;
 511   path->entries = GNUNET_new_array (path->entries_length,
 512                                     struct CadetPeerPathEntry *);
 513   for (;i>=0;i--)
 514   {
 515     struct CadetPeerPathEntry *entry = GNUNET_new (struct CadetPeerPathEntry);
 516
 517     path->entries[i] = entry;
 518     entry->peer = cpath[i];
 519     entry->path = path;
 520     GCP_path_entry_add (entry->peer,
 521                         entry,
 522                         i);
 523   }
 524   LOG (GNUNET_ERROR_TYPE_DEBUG,
 525        "Created new path %s based on information from DHT\n",
 526        GCPP_2s (path));
 527 }
 528
 529
 530 /**
 531  * We got an incoming connection, obtain the corresponding path.
 532  *
 533  * @param path_length number of segments on the @a path
 534  * @param pids path through the network, in reverse order (we are at the end at index @a path_length)
 535  * @return corresponding path object
 536  */
 537 struct CadetPeerPath *
 538 GCPP_get_path_from_route (unsigned int path_length,
 539                           const struct GNUNET_PeerIdentity *pids)
 540 {
 541   struct CheckMatchContext cm_ctx;
 542   struct CadetPeer *cpath[path_length];
 543   struct CadetPeerPath *path;
 544
 545   /* precompute inverted 'cpath' so we can avoid doing the lookups and
 546      have the correct order */
 547   for (unsigned int off=0;off<path_length;off++)
 548     cpath[off] = GCP_get (&pids[path_length - 1 - off],
 549                           GNUNET_YES);
 550
 551   /* First figure out if this path is a subset of an existing path, an
 552      extension of an existing path, or a new path. */
 553   cm_ctx.cpath = cpath;
 554   cm_ctx.cpath_length = path_length;
 555   cm_ctx.match = NULL;
 556   for (int i=path_length-1;i>=0;i--)
 557   {
 558     GCP_iterate_paths_at (cpath[i],
 559                           (unsigned int) i,
 560                           &check_match,
 561                           &cm_ctx);
 562     if (NULL != cm_ctx.match)
 563     {
 564       if (i == path_length - 1)
 565       {
 566         /* Existing path includes this one, return the match! */
 567         LOG (GNUNET_ERROR_TYPE_DEBUG,
 568              "Returning existing path %s as inverse for incoming connection\n",
 569              GCPP_2s (cm_ctx.match));
 570         return cm_ctx.match;
 571       }
 572       if (cm_ctx.match->entries_length == i + 1)
 573       {
 574         /* Existing path ends in the middle of new path, extend it! */
 575         LOG (GNUNET_ERROR_TYPE_DEBUG,
 576              "Extending existing path %s to create inverse for incoming connection\n",
 577              GCPP_2s (cm_ctx.match));
 578         extend_path (cm_ctx.match,
 579                      &cpath[i],
 580                      path_length - i,
 581                      GNUNET_YES);
 582         /* Check that extension was successful */
 583         GNUNET_assert (cm_ctx.match->entries_length == path_length);
 584         return cm_ctx.match;
 585       }
 586       /* Eh, we found a match but couldn't use it? Something is wrong. */
 587       GNUNET_break (0);
 588     }
 589   }
 590
 591   /* No match at all, create completely new path */
 592   path = GNUNET_new (struct CadetPeerPath);
 593   path->entries_length = path_length;
 594   path->entries = GNUNET_new_array (path->entries_length,
 595                                     struct CadetPeerPathEntry *);
 596   for (int i=path_length-1;i>=0;i--)
 597   {
 598     struct CadetPeerPathEntry *entry = GNUNET_new (struct CadetPeerPathEntry);
 599
 600     path->entries[i] = entry;
 601     entry->peer = cpath[i];
 602     entry->path = path;
 603     GCP_path_entry_add (entry->peer,
 604                         entry,
 605                         i);
 606   }
 607   LOG (GNUNET_ERROR_TYPE_DEBUG,
 608        "Created new path %s to create inverse for incoming connection\n",
 609        GCPP_2s (path));
 610   path->hn = GCP_attach_path (cpath[path_length - 1],
 611                               path,
 612                               path_length - 1,
 613                               GNUNET_YES);
 614   return path;
 615 }
 616
 617
 618 /**
 619  * Return the length of the path.  Excludes one end of the
 620  * path, so the loopback path has length 0.
 621  *
 622  * @param path path to return the length for
 623  * @return number of peers on the path
 624  */
 625 unsigned int
 626 GCPP_get_length (struct CadetPeerPath *path)
 627 {
 628   return path->entries_length;
 629 }
 630
 631
 632 /**
 633  * Find peer's offset on path.
 634  *
 635  * @param path path to search
 636  * @param cp peer to look for
 637  * @return offset of @a cp on @a path, or UINT_MAX if not found
 638  */
 639 unsigned int
 640 GCPP_find_peer (struct CadetPeerPath *path,
 641                 struct CadetPeer *cp)
 642 {
 643   for (unsigned int off = 0;
 644        off < path->entries_length;
 645        off++)
 646     if (cp == GCPP_get_peer_at_offset (path,
 647                                        off))
 648       return off;
 649   return UINT_MAX;
 650 }
 651
 652
 653 /**
 654  * Obtain the peer at offset @a off in @a path.
 655  *
 656  * @param path peer path to inspect
 657  * @param off offset to return, must be smaller than path length
 658  * @return the peer at offset @a off
 659  */
 660 struct CadetPeer *
 661 GCPP_get_peer_at_offset (struct CadetPeerPath *path,
 662                          unsigned int off)
 663 {
 664   GNUNET_assert (off < path->entries_length);
 665   return path->entries[off]->peer;
 666 }
 667
 668
 669 /**
 670  * Convert a path to a human-readable string.
 671  *
 672  * @param path path to convert
 673  * @return string, to be freed by caller (unlike other *_2s APIs!)
 674  */
 675 const char *
 676 GCPP_2s (struct CadetPeerPath *path)
 677 {
 678   static char buf[2048];
 679   size_t off;
 680   const unsigned int max_plen = (sizeof(buf) - 16) / 5 - 2; /* 5 characters per entry */
 681
 682   off = 0;
 683   for (unsigned int i = 0;
 684        i < path->entries_length;
 685        i++)
 686   {
 687     if ( (path->entries_length > max_plen) &&
 688          (i == max_plen / 2) )
 689       off += GNUNET_snprintf (&buf[off],
 690                               sizeof (buf) - off,
 691                               "...-");
 692     if ( (path->entries_length > max_plen) &&
 693          (i > max_plen / 2) &&
 694          (i < path->entries_length - max_plen / 2) )
 695       continue;
 696     off += GNUNET_snprintf (&buf[off],
 697                             sizeof (buf) - off,
 698                             "%s%s",
 699                             GNUNET_i2s (GCP_get_id (GCPP_get_peer_at_offset (path,
 700                                                                              i))),
 701                             (i == path->entries_length -1) ? "" : "-");
 702   }
 703   GNUNET_snprintf (&buf[off],
 704                    sizeof (buf) - off,
 705                    "(%p)",
 706                    path);
 707   return buf;
 708 }
 709
 710
 711 /* end of gnunet-service-cadet-new_paths.c */