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