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