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