GNUnet  0.10.x
Data Structures | Macros | Functions
gnunet-service-cadet_paths.c File Reference

Information we track per path. More...

#include "platform.h"
#include "gnunet-service-cadet_connection.h"
#include "gnunet-service-cadet_tunnels.h"
#include "gnunet-service-cadet_peer.h"
#include "gnunet-service-cadet_paths.h"
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_PeerIdentity *get_path, unsigned int get_path_length, const struct GNUNET_PeerIdentity *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__)

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 71 of file gnunet-service-cadet_paths.c.

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().

72 {
73  double result = 0.0;
74 
75  for (unsigned int i = 0; i < path->entries_length; i++)
76  {
77  struct CadetPeer *cp = path->entries[i]->peer;
78 
79  result += GCP_get_desirability_of_path(cp,
80  i);
81  }
83 }
Peer description.
struct CadetPeer * peer
The peer at this offset of the path.
static int result
Global testing status.
GNUNET_CONTAINER_HeapCostType desirability
Desirability of the path.
uint64_t GNUNET_CONTAINER_HeapCostType
Cost by which elements in a heap can be ordered.
struct CadetPeerPathEntry ** entries
Array of all the peers on the path.
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.
unsigned int entries_length
Length of the entries array.
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 ajacent 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 100 of file gnunet-service-cadet_paths.c.

References CadetPeerPath::desirability.

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

101 {
102  return path->desirability;
103 }
GNUNET_CONTAINER_HeapCostType desirability
Desirability of the 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 117 of file gnunet-service-cadet_paths.c.

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

Referenced by GCC_create_inbound(), and path_heap_cleanup().

120 {
121  struct CadetPeerPathEntry *entry;
122 
123  GNUNET_assert(off < path->entries_length);
124  entry = path->entries[off];
125  GNUNET_assert(entry->peer == destination);
126  return entry->cc;
127 }
struct CadetPeer * peer
The peer at this offset of the path.
struct CadetConnection * cc
Connection using this path, or NULL for none.
Entry in a peer path.
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
struct CadetPeerPathEntry ** entries
Array of all the peers on the path.
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 139 of file gnunet-service-cadet_paths.c.

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

Referenced by connection_create().

142 {
143  struct CadetPeerPathEntry *entry;
144 
146  "Adding %s to path %s at offset %u\n",
147  GCC_2s(cc),
148  GCPP_2s(path),
149  off);
150  GNUNET_assert(off < path->entries_length);
151  entry = path->entries[off];
152  GNUNET_assert(NULL == entry->cc);
153  GNUNET_assert(NULL != cc);
154  entry->cc = cc;
155 }
struct CadetConnection * cc
Connection using this path, or NULL for none.
const char * GCC_2s(const struct CadetConnection *cc)
Get a (static) string for a connection.
Entry in a peer path.
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
const char * GCPP_2s(struct CadetPeerPath *path)
Convert a path to a human-readable string.
#define LOG(level,...)
struct CadetPeerPathEntry ** entries
Array of all the peers on the path.
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.

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

Referenced by GCC_destroy().

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 }
struct CadetConnection * cc
Connection using this path, or NULL for none.
const char * GCC_2s(const struct CadetConnection *cc)
Get a (static) string for a connection.
Entry in a peer path.
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
const char * GCPP_2s(struct CadetPeerPath *path)
Convert a path to a human-readable string.
#define LOG(level,...)
struct CadetPeerPathEntry ** entries
Array of all the peers on the path.
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.

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::peer, and recalculate_path_desirability().

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

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);
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. */
230  path->entries_length,
231  path->entries_length);
232 }
struct GNUNET_CONTAINER_HeapNode * hn
Node of this path in the owner&#39;s heap.
static void recalculate_path_desirability(struct CadetPeerPath *path)
Calculate the path&#39;s desirability score.
static int end
Set if we are to shutdown all services (including ARM).
Definition: gnunet-arm.c:34
struct CadetPeer * peer
The peer at this offset of the path.
struct CadetConnection * cc
Connection using this path, or NULL for none.
Entry in a peer path.
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
#define GNUNET_NO
Definition: gnunet_common.h:78
struct GNUNET_CONTAINER_HeapNode * GCP_attach_path(struct CadetPeer *cp, struct CadetPeerPath *path, unsigned int off, int force)
Try adding a path to this peer.
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.
#define GNUNET_array_grow(arr, size, tsize)
Grow a well-typed (!) array.
struct CadetPeerPathEntry ** entries
Array of all the peers on the path.
#define GNUNET_YES
Definition: gnunet_common.h:77
unsigned int entries_length
Length of the entries array.
#define GNUNET_free(ptr)
Wrapper around free.
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.

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().

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 */
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 */
266  GNUNET_assert(0 == path->entries_length);
267  GNUNET_assert(NULL == path->entries);
268  GNUNET_free(path);
269  }
270 }
struct GNUNET_CONTAINER_HeapNode * hn
Node of this path in the owner&#39;s heap.
struct CadetPeer * peer
The peer at this offset of the path.
struct CadetConnection * cc
Connection using this path, or NULL for none.
Entry in a peer path.
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
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.
const char * GCPP_2s(struct CadetPeerPath *path)
Convert a path to a human-readable string.
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.
struct CadetPeerPath * path
Path this entry belongs to.
#define LOG(level,...)
struct CadetPeerPathEntry ** entries
Array of all the peers on the path.
unsigned int entries_length
Length of the entries array.
#define GNUNET_free(ptr)
Wrapper around free.
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.

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

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 }
static struct GNUNET_TIME_Relative delta
Definition: speedup.c:35
static void recalculate_path_desirability(struct CadetPeerPath *path)
Calculate the path&#39;s desirability score.
Entry in a peer path.
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
#define INT_MAX
int score
Path&#39;s historic score up to this point.
struct CadetPeerPathEntry ** entries
Array of all the peers on the path.
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 342 of file gnunet-service-cadet_paths.c.

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().

345 {
346  struct CheckMatchContext *cm_ctx = cls;
347 
348  GNUNET_assert(path->entries_length > off);
349  if ((path->entries_length != off + 1) &&
350  (off + 1 != cm_ctx->cpath_length))
351  {
353  "check_match mismatch because path %s is too long (%u vs. %u vs. %u)\n",
354  GCPP_2s(path),
355  path->entries_length,
356  off + 1,
357  cm_ctx->cpath_length);
358  return GNUNET_YES; /* too long, goes somewhere else already, thus cannot be useful */
359  }
360  for (unsigned int i = 0; i < off; i++)
361  if (cm_ctx->cpath[i] !=
363  i))
364  {
366  "check_match path %s mismatches at offset %u\n",
367  GCPP_2s(path),
368  i);
369  return GNUNET_YES; /* mismatch, ignore */
370  }
372  "check_match found match with path %s\n",
373  GCPP_2s(path));
374  cm_ctx->match = path;
375  return GNUNET_NO; /* match, we are done! */
376 }
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
struct CadetPeer ** cpath
Array the combined paths.
#define GNUNET_NO
Definition: gnunet_common.h:78
struct CadetPeerPath * match
Set to a matching path, if any.
const char * GCPP_2s(struct CadetPeerPath *path)
Convert a path to a human-readable string.
#define LOG(level,...)
unsigned int cpath_length
How long is the cpath array?
struct CadetPeer * GCPP_get_peer_at_offset(struct CadetPeerPath *path, unsigned int off)
Obtain the peer at offset off in path.
#define GNUNET_YES
Definition: gnunet_common.h:77
unsigned int entries_length
Length of the entries array.
Closure for #find_peer_at() and check_match().
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 390 of file gnunet-service-cadet_paths.c.

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, and CadetPeerPathEntry::peer.

Referenced by GCPP_get_path_from_route(), and GCPP_try_path_from_dht().

394 {
395  unsigned int old_len = path->entries_length;
396  int i;
397 
398  /* Expand path */
400  path->entries_length,
401  old_len + num_peers);
402  for (i = num_peers - 1; i >= 0; i--)
403  {
404  struct CadetPeerPathEntry *entry = GNUNET_new(struct CadetPeerPathEntry);
405 
406  path->entries[old_len + i] = entry;
407  entry->peer = peers[i];
408  entry->path = path;
409  }
410  for (i = num_peers - 1; i >= 0; i--)
411  {
412  struct CadetPeerPathEntry *entry = path->entries[old_len + i];
413 
414  GCP_path_entry_add(entry->peer,
415  entry,
416  old_len + i);
417  }
418 
419  /* If we extend an existing path, detach it from the
420  old owner and re-attach to the new one */
421  GCP_detach_path(path->entries[old_len - 1]->peer,
422  path,
423  path->hn);
424  path->hn = NULL;
425  path->entries_length = old_len + num_peers;
426  if (GNUNET_YES == force)
427  {
428  int end = path->entries_length - 1;
429 
430  path->hn = GCP_attach_path(path->entries[end]->peer,
431  path,
432  end,
433  GNUNET_YES);
434  }
435  else
436  {
437  attach_path(path, old_len);
438  }
439  if (NULL == path->hn)
440  {
441  /* none of the peers is interested in this path;
442  re-attach. */
443  GNUNET_assert(old_len == path->entries_length);
444  path->hn = GCP_attach_path(path->entries[old_len - 1]->peer,
445  path,
446  old_len - 1,
447  GNUNET_YES);
448  GNUNET_assert(NULL != path->hn);
449  return;
450  }
452  "Extended path %s\n",
453  GCPP_2s(path));
454 }
struct GNUNET_CONTAINER_HeapNode * hn
Node of this path in the owner&#39;s heap.
static int end
Set if we are to shutdown all services (including ARM).
Definition: gnunet-arm.c:34
struct CadetPeer * peer
The peer at this offset of the path.
Entry in a peer path.
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
struct GNUNET_CONTAINER_HeapNode * GCP_attach_path(struct CadetPeer *cp, struct CadetPeerPath *path, unsigned int off, int force)
Try adding a path to this peer.
#define GNUNET_new(type)
Allocate a struct or union of the given type.
const char * GCPP_2s(struct CadetPeerPath *path)
Convert a path to a human-readable string.
#define GNUNET_array_grow(arr, size, tsize)
Grow a well-typed (!) array.
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.
struct CadetPeerPath * path
Path this entry belongs to.
#define LOG(level,...)
static unsigned int num_peers
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.
struct CadetPeerPathEntry ** entries
Array of all the peers on the path.
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...
#define GNUNET_YES
Definition: gnunet_common.h:77
unsigned int entries_length
Length of the entries array.
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_PeerIdentity get_path,
unsigned int  get_path_length,
const struct GNUNET_PeerIdentity 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_lengthlenght 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 470 of file gnunet-service-cadet_paths.c.

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().

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

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().

606 {
607  struct CheckMatchContext cm_ctx;
608  struct CadetPeer *cpath[path_length];
609  struct CadetPeerPath *path;
610 
611  /* precompute inverted 'cpath' so we can avoid doing the lookups and
612  have the correct order */
613  for (unsigned int off = 0; off < path_length; off++)
614  cpath[off] = GCP_get(&pids[path_length - 1 - off],
615  GNUNET_YES);
616 
617  /* First figure out if this path is a subset of an existing path, an
618  extension of an existing path, or a new path. */
619  cm_ctx.cpath = cpath;
620  cm_ctx.cpath_length = path_length;
621  cm_ctx.match = NULL;
622  for (int i = path_length - 1; i >= 0; i--)
623  {
624  GCP_iterate_paths_at(cpath[i],
625  (unsigned int)i,
626  &check_match,
627  &cm_ctx);
628  if (NULL != cm_ctx.match)
629  {
630  if (i == path_length - 1)
631  {
632  /* Existing path includes this one, return the match! */
634  "Returning existing path %s as inverse for incoming connection\n",
635  GCPP_2s(cm_ctx.match));
636  return cm_ctx.match;
637  }
638  if (cm_ctx.match->entries_length == i + 1)
639  {
640  /* Existing path ends in the middle of new path, extend it! */
642  "Extending existing path %s to create inverse for incoming connection\n",
643  GCPP_2s(cm_ctx.match));
644  extend_path(cm_ctx.match,
645  &cpath[i + 1],
646  path_length - i - 1,
647  GNUNET_YES);
648  /* Check that extension was successful */
649  GNUNET_assert(cm_ctx.match->entries_length == path_length);
650  return cm_ctx.match;
651  }
652  /* Eh, we found a match but couldn't use it? Something is wrong. */
653  GNUNET_break(0);
654  }
655  }
656 
657  /* No match at all, create completely new path */
658  path = GNUNET_new(struct CadetPeerPath);
659  path->entries_length = path_length;
661  struct CadetPeerPathEntry *);
662  for (int i = path_length - 1; i >= 0; i--)
663  {
664  struct CadetPeerPathEntry *entry = GNUNET_new(struct CadetPeerPathEntry);
665 
666  path->entries[i] = entry;
667  entry->peer = cpath[i];
668  entry->path = path;
669  }
670  for (int i = path_length - 1; i >= 0; i--)
671  {
672  struct CadetPeerPathEntry *entry = path->entries[i];
673 
674  GCP_path_entry_add(entry->peer,
675  entry,
676  i);
677  }
680  "Created new path %s to create inverse for incoming connection\n",
681  GCPP_2s(path));
682  path->hn = GCP_attach_path(cpath[path_length - 1],
683  path,
684  path_length - 1,
685  GNUNET_YES);
686  return path;
687 }
struct GNUNET_CONTAINER_HeapNode * hn
Node of this path in the owner&#39;s heap.
Peer description.
static void recalculate_path_desirability(struct CadetPeerPath *path)
Calculate the path&#39;s desirability score.
struct CadetPeer * peer
The peer at this offset of the path.
Entry in a peer path.
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
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...
struct GNUNET_CONTAINER_HeapNode * GCP_attach_path(struct CadetPeer *cp, struct CadetPeerPath *path, unsigned int off, int force)
Try adding a path to this peer.
#define GNUNET_new(type)
Allocate a struct or union of the given type.
#define GNUNET_break(cond)
Use this for internal assertion violations that are not fatal (can be handled) but should not occur...
const char * GCPP_2s(struct CadetPeerPath *path)
Convert a path to a human-readable string.
struct CadetPeerPath * path
Path this entry belongs to.
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...
#define GNUNET_new_array(n, type)
Allocate a size n array with structs or unions of the given type.
#define LOG(level,...)
unsigned int GCP_iterate_paths_at(struct CadetPeer *cp, unsigned int dist, GCP_PathIterator callback, void *callback_cls)
Iterate over the paths to cp where cp is at distance dist from us.
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.
struct CadetPeer * GCP_get(const struct GNUNET_PeerIdentity *peer_id, int create)
Retrieve the CadetPeer stucture associated with the peer.
struct CadetPeerPathEntry ** entries
Array of all the peers on the path.
#define GNUNET_YES
Definition: gnunet_common.h:77
unsigned int entries_length
Length of the entries array.
Closure for #find_peer_at() and check_match().
Information regarding a possible path to reach a peer.
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 698 of file gnunet-service-cadet_paths.c.

References CadetPeerPath::entries_length.

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

699 {
700  return path->entries_length;
701 }
unsigned int entries_length
Length of the entries array.
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 712 of file gnunet-service-cadet_paths.c.

References CadetPeerPath::entries_length, and GCPP_get_peer_at_offset().

Referenced by GCC_create_inbound().

714 {
715  for (unsigned int off = 0;
716  off < path->entries_length;
717  off++)
718  if (cp == GCPP_get_peer_at_offset(path,
719  off))
720  return off;
721  return UINT_MAX;
722 }
struct CadetPeer * GCPP_get_peer_at_offset(struct CadetPeerPath *path, unsigned int off)
Obtain the peer at offset off in path.
unsigned int entries_length
Length of the entries array.
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
the peer at offset off

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

References CadetPeerPath::entries, CadetPeerPath::entries_length, 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().

735 {
736  GNUNET_assert(off < path->entries_length);
737  return path->entries[off]->peer;
738 }
struct CadetPeer * peer
The peer at this offset of the path.
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
struct CadetPeerPathEntry ** entries
Array of all the peers on the path.
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 748 of file gnunet-service-cadet_paths.c.

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(), GCC_debug(), 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().

749 {
750  static char buf[2048];
751  size_t off;
752  const unsigned int max_plen = (sizeof(buf) - 16) / 5 - 2; /* 5 characters per entry */
753 
754  off = 0;
755  for (unsigned int i = 0;
756  i < path->entries_length;
757  i++)
758  {
759  if ((path->entries_length > max_plen) &&
760  (i == max_plen / 2))
761  off += GNUNET_snprintf(&buf[off],
762  sizeof(buf) - off,
763  "...-");
764  if ((path->entries_length > max_plen) &&
765  (i > max_plen / 2) &&
766  (i < path->entries_length - max_plen / 2))
767  continue;
768  off += GNUNET_snprintf(&buf[off],
769  sizeof(buf) - off,
770  "%s%s",
772  i))),
773  (i == path->entries_length - 1) ? "" : "-");
774  }
775  GNUNET_snprintf(&buf[off],
776  sizeof(buf) - off,
777  "(%p)",
778  path);
779  return buf;
780 }
int GNUNET_snprintf(char *buf, size_t size, const char *format,...)
Like snprintf, just aborts if the buffer is of insufficient size.
static char buf[2048]
struct CadetPeer * GCPP_get_peer_at_offset(struct CadetPeerPath *path, unsigned int off)
Obtain the peer at offset off in path.
unsigned int entries_length
Length of the entries array.
const char * GNUNET_i2s(const struct GNUNET_PeerIdentity *pid)
Convert a peer identity to a string (for printing debug messages).
const struct GNUNET_PeerIdentity * GCP_get_id(struct CadetPeer *cp)
Obtain the peer identity for a struct CadetPeer.
Here is the call graph for this function:
Here is the caller graph for this function: