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