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

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