GNUnet  0.20.0
gnunet-service-cadet_paths.c File Reference

Information we track per path. More...

Include dependency graph for gnunet-service-cadet_paths.c:

Go to the source code of this file.

Data Structures

struct  CadetPeerPath
 Information regarding a possible path to reach a peer. More...
 
struct  CheckMatchContext
 Closure for #find_peer_at() and check_match(). More...
 

Macros

#define LOG(level, ...)   GNUNET_log_from (level, "cadet-pat", __VA_ARGS__)
 

Functions

static void recalculate_path_desirability (struct CadetPeerPath *path)
 Calculate the path's desirability score. More...
 
GNUNET_CONTAINER_HeapCostType GCPP_get_desirability (const struct CadetPeerPath *path)
 Return how much we like keeping the path. More...
 
struct CadetConnectionGCPP_get_connection (struct CadetPeerPath *path, struct CadetPeer *destination, unsigned int off)
 Return connection to destination using path, or return NULL if no such connection exists. More...
 
void GCPP_add_connection (struct CadetPeerPath *path, unsigned int off, struct CadetConnection *cc)
 Notify path that it is used for connection cc which ends at the path's offset off. More...
 
void GCPP_del_connection (struct CadetPeerPath *path, unsigned int off, struct CadetConnection *cc)
 Notify path that it is no longer used for connection cc which ended at the path's offset off. More...
 
static void attach_path (struct CadetPeerPath *path, unsigned int stop_at)
 Tries to attach path to a peer, working backwards from the end and stopping at stop_at. More...
 
void GCPP_release (struct CadetPeerPath *path)
 The owning peer of this path is no longer interested in maintaining it, so the path should be discarded or shortened (in case a previous peer on the path finds the path desirable). More...
 
void GCPP_update_score (struct CadetPeerPath *path, unsigned int off, int delta)
 Updates the score for an entry on the path based on our experiences with using path. More...
 
static int check_match (void *cls, struct CadetPeerPath *path, unsigned int off)
 Check if the given path is identical on all of the hops until off, and not longer than off. More...
 
static void extend_path (struct CadetPeerPath *path, struct CadetPeer **peers, unsigned int num_peers, int force)
 Extend path path by the num_peers from the peers array, assuming the owners past the current owner want it. More...
 
void GCPP_try_path_from_dht (const struct GNUNET_DHT_PathElement *get_path, unsigned int get_path_length, const struct GNUNET_DHT_PathElement *put_path, unsigned int put_path_length)
 Create a peer path based on the result of a DHT lookup. More...
 
struct CadetPeerPathGCPP_get_path_from_route (unsigned int path_length, const struct GNUNET_PeerIdentity *pids)
 We got an incoming connection, obtain the corresponding path. More...
 
unsigned int GCPP_get_length (struct CadetPeerPath *path)
 Return the length of the path. More...
 
unsigned int GCPP_find_peer (struct CadetPeerPath *path, struct CadetPeer *cp)
 Find peer's offset on path. More...
 
struct CadetPeerGCPP_get_peer_at_offset (struct CadetPeerPath *path, unsigned int off)
 Obtain the peer at offset off in path. More...
 
const char * GCPP_2s (struct CadetPeerPath *path)
 Convert a path to a human-readable string. More...
 

Detailed Description

Information we track per path.

Author
Bartlomiej Polot
Christian Grothoff

Definition in file gnunet-service-cadet_paths.c.

Macro Definition Documentation

◆ LOG

#define LOG (   level,
  ... 
)    GNUNET_log_from (level, "cadet-pat", __VA_ARGS__)

Definition at line 33 of file gnunet-service-cadet_paths.c.

Function Documentation

◆ recalculate_path_desirability()

static void recalculate_path_desirability ( struct CadetPeerPath path)
static

Calculate the path's desirability score.

Parameters
pathpath to calculate the score for

Definition at line 72 of file gnunet-service-cadet_paths.c.

73 {
74  double result = 0.0;
75 
76  for (unsigned int i = 0; i < path->entries_length; i++)
77  {
78  struct CadetPeer *cp = path->entries[i]->peer;
79 
81  i);
82  }
84 }
static int result
Global testing status.
double GCP_get_desirability_of_path(struct CadetPeer *cp, unsigned int off)
Calculate how desirable a path is for cp if cp is at offset off in the path.
uint64_t GNUNET_CONTAINER_HeapCostType
Cost by which elements in a heap can be ordered.
struct CadetPeer * peer
The peer at this offset of the path.
unsigned int entries_length
Length of the entries array.
struct CadetPeerPathEntry ** entries
Array of all the peers on the path.
GNUNET_CONTAINER_HeapCostType desirability
Desirability of the path.
Peer description.

References CadetPeerPath::desirability, CadetPeerPath::entries, CadetPeerPath::entries_length, GCP_get_desirability_of_path(), CadetPeerPathEntry::peer, and result.

Referenced by attach_path(), GCPP_get_path_from_route(), and GCPP_update_score().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ GCPP_get_desirability()

GNUNET_CONTAINER_HeapCostType GCPP_get_desirability ( const struct CadetPeerPath path)

Return how much we like keeping the path.

This is an aggregate score based on various factors, including the age of the path (older == better), and the value of this path to all of its adjacent peers. For example, long paths that end at a peer that we have no shorter way to reach are very desirable, while long paths that end at a peer for which we have a shorter way as well are much less desirable. Higher values indicate more valuable paths. The returned value should be used to decide which paths to remember.

Parameters
pathpath to return the length for
Returns
desirability of the path, larger is more desirable

Definition at line 101 of file gnunet-service-cadet_paths.c.

102 {
103  return path->desirability;
104 }

References CadetPeerPath::desirability.

Referenced by consider_path_cb(), evaluate_connection(), and GCP_attach_path().

Here is the caller graph for this function:

◆ GCPP_get_connection()

struct CadetConnection* GCPP_get_connection ( struct CadetPeerPath path,
struct CadetPeer destination,
unsigned int  off 
)

Return connection to destination using path, or return NULL if no such connection exists.

Parameters
pathpath to traverse
destinationdestination node to get to, must be on path
offoffset of destination on path
Returns
NULL if we have no existing connection otherwise connection from us to destination via path

Definition at line 118 of file gnunet-service-cadet_paths.c.

121 {
122  struct CadetPeerPathEntry *entry;
123 
124  GNUNET_assert (off < path->entries_length);
125  entry = path->entries[off];
126  GNUNET_assert (entry->peer == destination);
127  return entry->cc;
128 }
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
Entry in a peer path.
struct CadetConnection * cc
Connection using this path, or NULL for none.
struct CadetPeerPath * path
Path this entry belongs to.

References CadetPeerPathEntry::cc, CadetPeerPath::entries, GNUNET_assert, CadetPeerPathEntry::path, and CadetPeerPathEntry::peer.

Referenced by GCC_create_inbound(), and path_heap_cleanup().

Here is the caller graph for this function:

◆ GCPP_add_connection()

void GCPP_add_connection ( struct CadetPeerPath path,
unsigned int  off,
struct CadetConnection cc 
)

Notify path that it is used for connection cc which ends at the path's offset off.

Parameters
paththe path to remember the cc
offthe offset where the cc ends
ccthe connection to remember

Definition at line 140 of file gnunet-service-cadet_paths.c.

143 {
144  struct CadetPeerPathEntry *entry;
145 
147  "Adding %s to path %s at offset %u\n",
148  GCC_2s (cc),
149  GCPP_2s (path),
150  off);
151  GNUNET_assert (off < path->entries_length);
152  entry = path->entries[off];
153  GNUNET_assert (NULL == entry->cc);
154  GNUNET_assert (NULL != cc);
155  entry->cc = cc;
156 }
const char * GCC_2s(const struct CadetConnection *cc)
Get a (static) string for a connection.
const char * GCPP_2s(struct CadetPeerPath *path)
Convert a path to a human-readable string.
#define LOG(level,...)
@ GNUNET_ERROR_TYPE_DEBUG

References CadetPeerPathEntry::cc, CadetPeerPath::entries, GCC_2s(), GCPP_2s(), GNUNET_assert, GNUNET_ERROR_TYPE_DEBUG, LOG, and CadetPeerPathEntry::path.

Referenced by connection_create().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ GCPP_del_connection()

void GCPP_del_connection ( struct CadetPeerPath path,
unsigned int  off,
struct CadetConnection cc 
)

Notify path that it is no longer used for connection cc which ended at the path's offset off.

Parameters
paththe path to forget the cc
offthe offset where the cc ended
ccthe connection to forget

Definition at line 168 of file gnunet-service-cadet_paths.c.

171 {
172  struct CadetPeerPathEntry *entry;
173 
175  "Removing connection %s to path %s at offset %u\n",
176  GCC_2s (cc),
177  GCPP_2s (path),
178  off);
179  GNUNET_assert (off < path->entries_length);
180  entry = path->entries[off];
181  GNUNET_assert (cc == entry->cc);
182  entry->cc = NULL;
183 }

References CadetPeerPathEntry::cc, CadetPeerPath::entries, GCC_2s(), GCPP_2s(), GNUNET_assert, GNUNET_ERROR_TYPE_DEBUG, LOG, and CadetPeerPathEntry::path.

Referenced by GCC_destroy().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ attach_path()

static void attach_path ( struct CadetPeerPath path,
unsigned int  stop_at 
)
static

Tries to attach path to a peer, working backwards from the end and stopping at stop_at.

If path->hn is NULL on return then the path was not attached and you can assume that path->entries_length is equal to stop_at.

Parameters
paththe path to attach
stop_atthe path length at which to stop trying

Definition at line 196 of file gnunet-service-cadet_paths.c.

197 {
198  GNUNET_assert (NULL == path->hn);
199 
200  /* Try to attach this path to a peer, working backwards from the end. */
201  while (path->entries_length > stop_at)
202  {
203  unsigned int end = path->entries_length - 1;
204  struct CadetPeerPathEntry *entry = path->entries[end];
205  int force = GNUNET_NO;
206 
208  /* If the entry already has a connection using it, force attach. */
209  if (NULL != entry->cc)
210  force = GNUNET_YES;
211  path->hn = GCP_attach_path (entry->peer,
212  path,
213  end,
214  force);
215  if (NULL != path->hn)
216  break;
217 
218  /* Attach failed, trim this entry from the path. */
219  GNUNET_assert (NULL == entry->cc);
220  GCP_path_entry_remove (entry->peer,
221  entry,
222  end);
223  GNUNET_free (entry);
224  path->entries[end] = NULL;
225  path->entries_length--;
226  }
227 
228  /* Shrink array to actual path length. */
232 }
static int end
Set if we are to shutdown all services (including ARM).
Definition: gnunet-arm.c:34
static void recalculate_path_desirability(struct CadetPeerPath *path)
Calculate the path's desirability score.
struct GNUNET_CONTAINER_HeapNode * GCP_attach_path(struct CadetPeer *cp, struct CadetPeerPath *path, unsigned int off, int force)
Try adding a path to this cp.
void GCP_path_entry_remove(struct CadetPeer *cp, struct CadetPeerPathEntry *entry, unsigned int off)
Remove an entry from the DLL of all of the paths that this peer is on.
@ GNUNET_YES
@ GNUNET_NO
#define GNUNET_array_grow(arr, size, tsize)
Grow a well-typed (!) array.
#define GNUNET_free(ptr)
Wrapper around free.
struct GNUNET_CONTAINER_HeapNode * hn
Node of this path in the owner's heap.

References CadetPeerPathEntry::cc, end, CadetPeerPath::entries, CadetPeerPath::entries_length, GCP_attach_path(), GCP_path_entry_remove(), GNUNET_array_grow, GNUNET_assert, GNUNET_free, GNUNET_NO, GNUNET_YES, CadetPeerPath::hn, CadetPeerPathEntry::path, CadetPeerPathEntry::peer, and recalculate_path_desirability().

Referenced by extend_path(), GCPP_release(), and GCPP_try_path_from_dht().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ GCPP_release()

void GCPP_release ( struct CadetPeerPath path)

The owning peer of this path is no longer interested in maintaining it, so the path should be discarded or shortened (in case a previous peer on the path finds the path desirable).

The given peer cp used to own this path.

Parameters
paththe path that is being released

Definition at line 243 of file gnunet-service-cadet_paths.c.

244 {
245  struct CadetPeerPathEntry *entry;
246 
248  "Owner releases path %s\n",
249  GCPP_2s (path));
250  path->hn = NULL;
251  entry = path->entries[path->entries_length - 1];
252  GNUNET_assert (path == entry->path);
253  GNUNET_assert (NULL == entry->cc);
254  /* cut 'off' end of path */
255  GCP_path_entry_remove (entry->peer,
256  entry,
257  path->entries_length - 1);
258  GNUNET_free (entry);
259  path->entries[path->entries_length - 1] = NULL;
260  path->entries_length--;
261  /* see if new peer at the end likes this path any better */
262  attach_path (path, 0);
263  if (NULL == path->hn)
264  {
265  /* nobody wants us, discard the path */
267  GNUNET_assert (NULL == path->entries);
268  GNUNET_free (path);
269  }
270 }
static void attach_path(struct CadetPeerPath *path, unsigned int stop_at)
Tries to attach path to a peer, working backwards from the end and stopping at stop_at.

References attach_path(), CadetPeerPathEntry::cc, CadetPeerPath::entries, CadetPeerPath::entries_length, GCP_path_entry_remove(), GCPP_2s(), GNUNET_assert, GNUNET_ERROR_TYPE_DEBUG, GNUNET_free, CadetPeerPath::hn, LOG, CadetPeerPathEntry::path, and CadetPeerPathEntry::peer.

Referenced by drop_paths(), GCP_drop_owned_paths(), and path_heap_cleanup().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ GCPP_update_score()

void GCPP_update_score ( struct CadetPeerPath path,
unsigned int  off,
int  delta 
)

Updates the score for an entry on the path based on our experiences with using path.

Parameters
paththe path to update
offoffset of the entry to update
deltachange in the score to apply

Definition at line 282 of file gnunet-service-cadet_paths.c.

285 {
286  struct CadetPeerPathEntry *entry;
287 
288  GNUNET_assert (off < path->entries_length);
289  entry = path->entries[off];
290 
291  /* Add delta, with checks for overflows */
292  if (delta >= 0)
293  {
294  if (delta + entry->score < entry->score)
295  entry->score = INT_MAX;
296  else
297  entry->score += delta;
298  }
299  else
300  {
301  if (delta + entry->score > entry->score)
302  entry->score = INT_MIN;
303  else
304  entry->score += delta;
305  }
307 }
#define INT_MAX
static struct GNUNET_TIME_Relative delta
Definition: speedup.c:36
int score
Path's historic score up to this point.

References delta, CadetPeerPath::entries, GNUNET_assert, INT_MAX, CadetPeerPathEntry::path, recalculate_path_desirability(), and CadetPeerPathEntry::score.

Here is the call graph for this function:

◆ check_match()

static int check_match ( void *  cls,
struct CadetPeerPath path,
unsigned int  off 
)
static

Check if the given path is identical on all of the hops until off, and not longer than off.

If the path matches, store it in match.

Parameters
clsthe struct CheckMatchContext to check against
paththe path to check
offoffset to check at
Returns
GNUNET_YES (continue to iterate), or if found GNUNET_NO

Definition at line 343 of file gnunet-service-cadet_paths.c.

346 {
347  struct CheckMatchContext *cm_ctx = cls;
348 
349  GNUNET_assert (path->entries_length > off);
350  if ((path->entries_length != off + 1) &&
351  (off + 1 != cm_ctx->cpath_length))
352  {
354  "check_match mismatch because path %s is too long (%u vs. %u vs. %u)\n",
355  GCPP_2s (path),
356  path->entries_length,
357  off + 1,
358  cm_ctx->cpath_length);
359  return GNUNET_YES; /* too long, goes somewhere else already, thus cannot be useful */
360  }
361  for (unsigned int i = 0; i < off; i++)
362  if (cm_ctx->cpath[i] !=
364  i))
365  {
367  "check_match path %s mismatches at offset %u\n",
368  GCPP_2s (path),
369  i);
370  return GNUNET_YES; /* mismatch, ignore */
371  }
373  "check_match found match with path %s\n",
374  GCPP_2s (path));
375  cm_ctx->match = path;
376  return GNUNET_NO; /* match, we are done! */
377 }
struct CadetPeer * GCPP_get_peer_at_offset(struct CadetPeerPath *path, unsigned int off)
Obtain the peer at offset off in path.
Closure for #find_peer_at() and check_match().
struct CadetPeerPath * match
Set to a matching path, if any.
unsigned int cpath_length
How long is the cpath array?
struct CadetPeer ** cpath
Array the combined paths.

References CheckMatchContext::cpath, CheckMatchContext::cpath_length, CadetPeerPath::entries_length, GCPP_2s(), GCPP_get_peer_at_offset(), GNUNET_assert, GNUNET_ERROR_TYPE_DEBUG, GNUNET_NO, GNUNET_YES, LOG, and CheckMatchContext::match.

Referenced by GCPP_get_path_from_route(), and GCPP_try_path_from_dht().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ extend_path()

static void extend_path ( struct CadetPeerPath path,
struct CadetPeer **  peers,
unsigned int  num_peers,
int  force 
)
static

Extend path path by the num_peers from the peers array, assuming the owners past the current owner want it.

Parameters
pathpath to extend
peerslist of peers beyond the end of path
num_peerslength of the peers array
forceforce attachment, even if we have other paths already

Definition at line 391 of file gnunet-service-cadet_paths.c.

395 {
396  unsigned int old_len = path->entries_length;
397  int i;
398 
399  /* Expand path */
400  GNUNET_array_grow (path->entries,
401  path->entries_length,
402  old_len + num_peers);
403  for (i = num_peers - 1; i >= 0; i--)
404  {
405  struct CadetPeerPathEntry *entry = GNUNET_new (struct CadetPeerPathEntry);
406 
407  path->entries[old_len + i] = entry;
408  entry->peer = peers[i];
409  entry->path = path;
410  }
411  for (i = num_peers - 1; i >= 0; i--)
412  {
413  struct CadetPeerPathEntry *entry = path->entries[old_len + i];
414 
415  GCP_path_entry_add (entry->peer,
416  entry,
417  old_len + i);
418  }
419 
420  /* If we extend an existing path, detach it from the
421  old owner and re-attach to the new one */
422  GCP_detach_path (path->entries[old_len - 1]->peer,
423  path,
424  path->hn);
425  path->hn = NULL;
426  path->entries_length = old_len + num_peers;
427  if (GNUNET_YES == force)
428  {
429  int end = path->entries_length - 1;
430 
432  path,
433  end,
434  GNUNET_YES);
435  }
436  else
437  {
438  attach_path (path, old_len);
439  }
440  if (NULL == path->hn)
441  {
442  /* none of the peers is interested in this path;
443  re-attach. */
444  GNUNET_assert (old_len == path->entries_length);
445  path->hn = GCP_attach_path (path->entries[old_len - 1]->peer,
446  path,
447  old_len - 1,
448  GNUNET_YES);
449  GNUNET_assert (NULL != path->hn);
450  return;
451  }
453  "Extended path %s\n",
454  GCPP_2s (path));
455 }
static struct CadetPeer * peers
Operation to get peer ids.
static unsigned int num_peers
void GCP_detach_path(struct CadetPeer *cp, struct CadetPeerPath *path, struct GNUNET_CONTAINER_HeapNode *hn)
This peer can no longer own path as the path has been extended and a peer further down the line is no...
void GCP_path_entry_add(struct CadetPeer *cp, struct CadetPeerPathEntry *entry, unsigned int off)
Add an entry to the DLL of all of the paths that this peer is on.
#define GNUNET_new(type)
Allocate a struct or union of the given type.

References attach_path(), end, CadetPeerPath::entries, CadetPeerPath::entries_length, GCP_attach_path(), GCP_detach_path(), GCP_path_entry_add(), GCPP_2s(), GNUNET_array_grow, GNUNET_assert, GNUNET_ERROR_TYPE_DEBUG, GNUNET_new, GNUNET_YES, CadetPeerPath::hn, LOG, num_peers, CadetPeerPathEntry::path, CadetPeerPathEntry::peer, and peers.

Referenced by GCPP_get_path_from_route(), and GCPP_try_path_from_dht().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ GCPP_try_path_from_dht()

void GCPP_try_path_from_dht ( const struct GNUNET_DHT_PathElement get_path,
unsigned int  get_path_length,
const struct GNUNET_DHT_PathElement put_path,
unsigned int  put_path_length 
)

Create a peer path based on the result of a DHT lookup.

If we already know this path, or one that is longer, simply return NULL. Otherwise, we try to extend an existing path, or create a new one if applicable.

Parameters
get_pathpath of the get request
get_path_lengthlength of get_path
put_pathpath of the put request
put_path_lengthlength of the put_path
Returns
a path through the network

Definition at line 471 of file gnunet-service-cadet_paths.c.

475 {
476  struct CadetPeer *cpath[get_path_length + put_path_length];
477  struct CheckMatchContext cm_ctx;
478  struct CadetPeerPath *path;
479  unsigned int skip;
480  unsigned int total_len;
481 
482  /* precompute 'cpath' so we can avoid doing the lookups lots of times */
483  skip = 0;
484  memset (cpath,
485  0,
486  sizeof(cpath)); /* Just to trigger harder errors later. */
487  total_len = get_path_length + put_path_length;
488  for (unsigned int off = 0; off < total_len; off++)
489  {
490  const struct GNUNET_PeerIdentity *pid;
491 
492  pid = (off < get_path_length)
493  ? &get_path[get_path_length - off - 1].pred
494  : &put_path[get_path_length + put_path_length - off - 1].pred;
495  /* Check that I am not in the path */
496  if (0 == GNUNET_memcmp (&my_full_id,
497  pid))
498  {
499  skip = off + 1;
500  continue;
501  }
502  cpath[off - skip] = GCP_get (pid,
503  GNUNET_YES);
504  /* Check that no peer is twice on the path */
505  for (unsigned int i = 0; i < off - skip; i++)
506  {
507  if (cpath[i] == cpath[off - skip])
508  {
509  skip = off - i;
510  break;
511  }
512  }
513  }
514  if (skip >= total_len)
515  {
517  "Path discovered from DHT is one big cycle?\n");
518  return;
519  }
520  total_len -= skip;
521 
522  /* First figure out if this path is a subset of an existing path, an
523  extension of an existing path, or a new path. */
524  cm_ctx.cpath_length = total_len;
525  cm_ctx.cpath = cpath;
526  cm_ctx.match = NULL;
527  for (int i = total_len - 1; i >= 0; i--)
528  {
529  GCP_iterate_paths_at (cpath[i],
530  (unsigned int) i,
531  &check_match,
532  &cm_ctx);
533  if (NULL != cm_ctx.match)
534  {
535  if (i == total_len - 1)
536  {
537  /* Existing path includes this one, nothing to do! */
539  "Path discovered from DHT is already known\n");
540  return;
541  }
542  if (cm_ctx.match->entries_length == i + 1)
543  {
544  /* Existing path ends in the middle of new path, extend it! */
546  "Trying to extend existing path %s by additional links discovered from DHT\n",
547  GCPP_2s (cm_ctx.match));
548  extend_path (cm_ctx.match,
549  &cpath[i + 1],
550  total_len - i - 1,
551  GNUNET_NO);
552  return;
553  }
554  }
555  }
556 
557  /* No match at all, create completely new path */
558  path = GNUNET_new (struct CadetPeerPath);
559  path->entries_length = total_len;
560  path->entries = GNUNET_new_array (path->entries_length,
561  struct CadetPeerPathEntry *);
562  for (int i = path->entries_length - 1; i >= 0; i--)
563  {
564  struct CadetPeerPathEntry *entry = GNUNET_new (struct CadetPeerPathEntry);
565 
566  path->entries[i] = entry;
567  entry->peer = cpath[i];
568  entry->path = path;
569  }
570  for (int i = path->entries_length - 1; i >= 0; i--)
571  {
572  struct CadetPeerPathEntry *entry = path->entries[i];
573 
574  GCP_path_entry_add (entry->peer,
575  entry,
576  i);
577  }
578 
579  /* Finally, try to attach it */
580  attach_path (path, 0);
581  if (NULL == path->hn)
582  {
583  /* None of the peers on the path care about it. */
585  "Path discovered from DHT is not interesting to us\n");
587  GNUNET_assert (NULL == path->entries);
588  GNUNET_free (path);
589  return;
590  }
592  "Created new path %s based on information from DHT\n",
593  GCPP_2s (path));
594 }
struct GNUNET_PeerIdentity my_full_id
Local peer own ID.
static int check_match(void *cls, struct CadetPeerPath *path, unsigned int off)
Check if the given path is identical on all of the hops until off, and not longer than off.
static void extend_path(struct CadetPeerPath *path, struct CadetPeer **peers, unsigned int num_peers, int force)
Extend path path by the num_peers from the peers array, assuming the owners past the current owner wa...
unsigned int GCP_iterate_paths_at(struct CadetPeer *cp, unsigned int dist, GCP_PathIterator callback, void *callback_cls)
Iterate over the paths to peer where peer is at distance dist from us.
struct CadetPeer * GCP_get(const struct GNUNET_PeerIdentity *peer_id, int create)
Retrieve the CadetPeer structure associated with the peer.
static struct GNUNET_PeerIdentity pid
Identity of the peer we transmit to / connect to.
#define GNUNET_memcmp(a, b)
Compare memory in a and b, where both must be of the same pointer type.
#define GNUNET_new_array(n, type)
Allocate a size n array with structs or unions of the given type.
Information regarding a possible path to reach a peer.
The identity of the host (wraps the signing key of the peer).

References attach_path(), check_match(), CheckMatchContext::cpath, CheckMatchContext::cpath_length, CadetPeerPath::entries, CadetPeerPath::entries_length, extend_path(), GCP_get(), GCP_iterate_paths_at(), GCP_path_entry_add(), GCPP_2s(), GNUNET_assert, GNUNET_ERROR_TYPE_DEBUG, GNUNET_free, GNUNET_memcmp, GNUNET_new, GNUNET_new_array, GNUNET_NO, GNUNET_YES, CadetPeerPath::hn, LOG, CheckMatchContext::match, my_full_id, CadetPeerPathEntry::path, CadetPeerPathEntry::peer, and pid.

Referenced by dht_get_id_handler().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ GCPP_get_path_from_route()

struct CadetPeerPath* GCPP_get_path_from_route ( unsigned int  path_length,
const struct GNUNET_PeerIdentity pids 
)

We got an incoming connection, obtain the corresponding path.

Parameters
path_lengthnumber of segments on the path
pidspath through the network, in reverse order (we are at the end, at index path_length)
Returns
corresponding path object

Definition at line 598 of file gnunet-service-cadet_paths.c.

600 {
601  struct CheckMatchContext cm_ctx;
602  struct CadetPeer *cpath[path_length];
603  struct CadetPeerPath *path;
604 
605  /* precompute inverted 'cpath' so we can avoid doing the lookups and
606  have the correct order */
607  for (unsigned int off = 0; off < path_length; off++)
608  cpath[off] = GCP_get (&pids[path_length - 1 - off],
609  GNUNET_YES);
610 
611  /* First figure out if this path is a subset of an existing path, an
612  extension of an existing path, or a new path. */
613  cm_ctx.cpath = cpath;
614  cm_ctx.cpath_length = path_length;
615  cm_ctx.match = NULL;
616  for (int i = path_length - 1; i >= 0; i--)
617  {
618  GCP_iterate_paths_at (cpath[i],
619  (unsigned int) i,
620  &check_match,
621  &cm_ctx);
622  if (NULL != cm_ctx.match)
623  {
624  if (i == path_length - 1)
625  {
626  /* Existing path includes this one, return the match! */
628  "Returning existing path %s as inverse for incoming connection\n",
629  GCPP_2s (cm_ctx.match));
630  return cm_ctx.match;
631  }
632  if (cm_ctx.match->entries_length == i + 1)
633  {
634  /* Existing path ends in the middle of new path, extend it! */
636  "Extending existing path %s to create inverse for incoming connection\n",
637  GCPP_2s (cm_ctx.match));
638  extend_path (cm_ctx.match,
639  &cpath[i + 1],
640  path_length - i - 1,
641  GNUNET_YES);
642  /* Check that extension was successful */
643  GNUNET_assert (cm_ctx.match->entries_length == path_length);
644  return cm_ctx.match;
645  }
646  /* Eh, we found a match but couldn't use it? Something is wrong. */
647  GNUNET_break (0);
648  }
649  }
650 
651  /* No match at all, create completely new path */
652  path = GNUNET_new (struct CadetPeerPath);
653  path->entries_length = path_length;
654  path->entries = GNUNET_new_array (path->entries_length,
655  struct CadetPeerPathEntry *);
656  for (int i = path_length - 1; i >= 0; i--)
657  {
658  struct CadetPeerPathEntry *entry = GNUNET_new (struct CadetPeerPathEntry);
659 
660  path->entries[i] = entry;
661  entry->peer = cpath[i];
662  entry->path = path;
663  }
664  for (int i = path_length - 1; i >= 0; i--)
665  {
666  struct CadetPeerPathEntry *entry = path->entries[i];
667 
668  GCP_path_entry_add (entry->peer,
669  entry,
670  i);
671  }
674  "Created new path %s to create inverse for incoming connection\n",
675  GCPP_2s (path));
676  path->hn = GCP_attach_path (cpath[path_length - 1],
677  path,
678  path_length - 1,
679  GNUNET_YES);
680  return path;
681 }
#define GNUNET_break(cond)
Use this for internal assertion violations that are not fatal (can be handled) but should not occur.

References check_match(), CheckMatchContext::cpath, CheckMatchContext::cpath_length, CadetPeerPath::entries, CadetPeerPath::entries_length, extend_path(), GCP_attach_path(), GCP_get(), GCP_iterate_paths_at(), GCP_path_entry_add(), GCPP_2s(), GNUNET_assert, GNUNET_break, GNUNET_ERROR_TYPE_DEBUG, GNUNET_new, GNUNET_new_array, GNUNET_YES, CadetPeerPath::hn, LOG, CheckMatchContext::match, CadetPeerPathEntry::path, CadetPeerPathEntry::peer, and recalculate_path_desirability().

Referenced by GCP_iterate_paths(), GCP_set_mq(), and handle_connection_create().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ GCPP_get_length()

unsigned int GCPP_get_length ( struct CadetPeerPath path)

Return the length of the path.

Excludes one end of the path, so the loopback path has length 0.

Parameters
pathpath to return the length for
Returns
number of peers on the path

Definition at line 692 of file gnunet-service-cadet_paths.c.

693 {
694  return path->entries_length;
695 }

References CadetPeerPath::entries_length, and CadetPeerPathEntry::path.

Referenced by consider_path_cb(), evaluate_connection(), GCP_attach_path(), path_heap_cleanup(), and path_info_iterator().

Here is the caller graph for this function:

◆ GCPP_find_peer()

unsigned int GCPP_find_peer ( struct CadetPeerPath path,
struct CadetPeer cp 
)

Find peer's offset on path.

Parameters
pathpath to search
cppeer to look for
Returns
offset of cp on path, or UINT_MAX if not found

Definition at line 706 of file gnunet-service-cadet_paths.c.

708 {
709  for (unsigned int off = 0;
710  off < path->entries_length;
711  off++)
712  if (cp == GCPP_get_peer_at_offset (path,
713  off))
714  return off;
715  return UINT_MAX;
716 }

References CadetPeerPath::entries_length, GCPP_get_peer_at_offset(), and CadetPeerPathEntry::path.

Referenced by GCC_create_inbound().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ GCPP_get_peer_at_offset()

struct CadetPeer* GCPP_get_peer_at_offset ( struct CadetPeerPath path,
unsigned int  off 
)

Obtain the peer at offset off in path.

Parameters
pathpeer path to inspect
offoffset to return, must be smaller than path length
Returns
peer at offset off

Definition at line 720 of file gnunet-service-cadet_paths.c.

722 {
723  GNUNET_assert (off < path->entries_length);
724  return path->entries[off]->peer;
725 }

References CadetPeerPath::entries, GNUNET_assert, and CadetPeerPathEntry::peer.

Referenced by check_match(), connection_create(), consider_path_cb(), evaluate_connection(), GCC_destroy(), GCP_attach_path(), GCP_path_entry_add(), GCPP_2s(), GCPP_find_peer(), handle_connection_broken(), handle_connection_create_ack(), handle_connection_destroy(), handle_tunnel_encrypted(), handle_tunnel_kx(), handle_tunnel_kx_auth(), path_info_iterator(), and send_create().

Here is the caller graph for this function:

◆ GCPP_2s()

const char* GCPP_2s ( struct CadetPeerPath path)

Convert a path to a human-readable string.

Parameters
pathpath to convert
Returns
string, to be freed by caller (unlike other *_2s APIs!)

Definition at line 735 of file gnunet-service-cadet_paths.c.

736 {
737  static char buf[2048];
738  size_t off;
739  const unsigned int max_plen = (sizeof(buf) - 16) / 5 - 2; /* 5 characters per entry */
740 
741  off = 0;
742  for (unsigned int i = 0;
743  i < path->entries_length;
744  i++)
745  {
746  if ((path->entries_length > max_plen) &&
747  (i == max_plen / 2))
748  off += GNUNET_snprintf (&buf[off],
749  sizeof(buf) - off,
750  "...-");
751  if ((path->entries_length > max_plen) &&
752  (i > max_plen / 2) &&
753  (i < path->entries_length - max_plen / 2))
754  continue;
755  off += GNUNET_snprintf (&buf[off],
756  sizeof(buf) - off,
757  "%s%s",
759  path,
760  i))),
761  (i == path->entries_length - 1) ? "" : "-");
762  }
763  GNUNET_snprintf (&buf[off],
764  sizeof(buf) - off,
765  "(%p)",
766  path);
767  return buf;
768 }
const struct GNUNET_PeerIdentity * GCP_get_id(struct CadetPeer *cp)
Obtain the peer identity for a struct CadetPeer.
static char buf[2048]
const char * GNUNET_i2s(const struct GNUNET_PeerIdentity *pid)
Convert a peer identity to a string (for printing debug messages).
int GNUNET_snprintf(char *buf, size_t size, const char *format,...) __attribute__((format(printf
Like snprintf, just aborts if the buffer is of insufficient size.

References buf, CadetPeerPath::entries_length, GCP_get_id(), GCPP_get_peer_at_offset(), GNUNET_i2s(), and GNUNET_snprintf().

Referenced by check_match(), connection_create(), consider_path_cb(), evaluate_connection(), extend_path(), GCC_create_inbound(), GCP_attach_path(), GCP_detach_path(), GCP_path_entry_add(), GCP_path_entry_remove(), GCPP_add_connection(), GCPP_del_connection(), GCPP_get_path_from_route(), GCPP_release(), GCPP_try_path_from_dht(), GCT_consider_path(), and handle_connection_create().

Here is the call graph for this function:
Here is the caller graph for this function: