gnunet-service-cadet_paths.h File Reference

#include "gnunet_util_lib.h"
#include "gnunet_dht_service.h"
#include "gnunet-service-cadet.h"

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

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Functions
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 CadetPeerPath *	GCPP_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...
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. 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...
unsigned int	GCPP_find_peer (struct CadetPeerPath *path, struct CadetPeer *cp)
	Find peer's offset on path. More...
GNUNET_CONTAINER_HeapCostType	GCPP_get_desirability (const struct CadetPeerPath *path)
	Return how much we like keeping the path. More...
void	GCPP_release (struct CadetPeerPath *path)
	The given peer cp used to own this path. More...
struct CadetPeer *	GCPP_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 *p)
	Convert a path to a human-readable string. More...

Function Documentation

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_path	path of the get request
get_path_length	length of get_path
put_path	path of the put request
put_path_length	length of the put_path

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_path	path of the get request
get_path_length	length of get_path
put_path	path of the put request
put_path_length	length of the put_path

Returns

a path through the network

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

{
  struct CadetPeer *cpath[get_path_length + put_path_length];
  struct CheckMatchContext cm_ctx;
  struct CadetPeerPath *path;
  unsigned int skip;
  unsigned int total_len;
 
  /* precompute 'cpath' so we can avoid doing the lookups lots of times */
  skip = 0;
  memset (cpath,
          0,
          sizeof(cpath));  /* Just to trigger harder errors later. */
  total_len = get_path_length + put_path_length;
  for (unsigned int off = 0; off < total_len; off++)
  {
    const struct GNUNET_PeerIdentity *pid;
 
    pid = (off < get_path_length)
          ? &get_path[get_path_length - off - 1].pred
          : &put_path[get_path_length + put_path_length - off - 1].pred;
    /* Check that I am not in the path */
    if (0 == GNUNET_memcmp (&my_full_id,
                            pid))
    {
      skip = off + 1;
      continue;
    }
    cpath[off - skip] = GCP_get (pid,
                                 GNUNET_YES);
    /* Check that no peer is twice on the path */
    for (unsigned int i = 0; i < off - skip; i++)
    {
      if (cpath[i] == cpath[off - skip])
      {
        skip = off - i;
        break;
      }
    }
  }
  if (skip >= total_len)
  {
    LOG (GNUNET_ERROR_TYPE_DEBUG,
         "Path discovered from DHT is one big cycle?\n");
    return;
  }
  total_len -= skip;
 
  /* First figure out if this path is a subset of an existing path, an
     extension of an existing path, or a new path. */
  cm_ctx.cpath_length = total_len;
  cm_ctx.cpath = cpath;
  cm_ctx.match = NULL;
  for (int i = total_len - 1; i >= 0; i--)
  {
    GCP_iterate_paths_at (cpath[i],
                          (unsigned int) i,
                          &check_match,
                          &cm_ctx);
    if (NULL != cm_ctx.match)
    {
      if (i == total_len - 1)
      {
        /* Existing path includes this one, nothing to do! */
        LOG (GNUNET_ERROR_TYPE_DEBUG,
             "Path discovered from DHT is already known\n");
        return;
      }
      if (cm_ctx.match->entries_length == i + 1)
      {
        /* Existing path ends in the middle of new path, extend it! */
        LOG (GNUNET_ERROR_TYPE_DEBUG,
             "Trying to extend existing path %s by additional links discovered from DHT\n",
             GCPP_2s (cm_ctx.match));
        extend_path (cm_ctx.match,
                     &cpath[i + 1],
                     total_len - i - 1,
                     GNUNET_NO);
        return;
      }
    }
  }
 
  /* No match at all, create completely new path */
  path = GNUNET_new (struct CadetPeerPath);
  path->entries_length = total_len;
  path->entries = GNUNET_new_array (path->entries_length,
                                    struct CadetPeerPathEntry *);
  for (int i = path->entries_length - 1; i >= 0; i--)
  {
    struct CadetPeerPathEntry *entry = GNUNET_new (struct CadetPeerPathEntry);
 
    path->entries[i] = entry;
    entry->peer = cpath[i];
    entry->path = path;
  }
  for (int i = path->entries_length - 1; i >= 0; i--)
  {
    struct CadetPeerPathEntry *entry = path->entries[i];
 
    GCP_path_entry_add (entry->peer,
                        entry,
                        i);
  }
 
  /* Finally, try to attach it */
  attach_path (path, 0);
  if (NULL == path->hn)
  {
    /* None of the peers on the path care about it. */
    LOG (GNUNET_ERROR_TYPE_DEBUG,
         "Path discovered from DHT is not interesting to us\n");
    GNUNET_assert (0 == path->entries_length);
    GNUNET_assert (NULL == path->entries);
    GNUNET_free (path);
    return;
  }
  LOG (GNUNET_ERROR_TYPE_DEBUG,
       "Created new path %s based on information from DHT\n",
       GCPP_2s (path));
}

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_length	number of segments on the path
pids	path 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.

{
  struct CheckMatchContext cm_ctx;
  struct CadetPeer *cpath[path_length];
  struct CadetPeerPath *path;
 
  /* precompute inverted 'cpath' so we can avoid doing the lookups and
     have the correct order */
  for (unsigned int off = 0; off < path_length; off++)
    cpath[off] = GCP_get (&pids[path_length - 1 - off],
                          GNUNET_YES);
 
  /* First figure out if this path is a subset of an existing path, an
     extension of an existing path, or a new path. */
  cm_ctx.cpath = cpath;
  cm_ctx.cpath_length = path_length;
  cm_ctx.match = NULL;
  for (int i = path_length - 1; i >= 0; i--)
  {
    GCP_iterate_paths_at (cpath[i],
                          (unsigned int) i,
                          &check_match,
                          &cm_ctx);
    if (NULL != cm_ctx.match)
    {
      if (i == path_length - 1)
      {
        /* Existing path includes this one, return the match! */
        LOG (GNUNET_ERROR_TYPE_DEBUG,
             "Returning existing path %s as inverse for incoming connection\n",
             GCPP_2s (cm_ctx.match));
        return cm_ctx.match;
      }
      if (cm_ctx.match->entries_length == i + 1)
      {
        /* Existing path ends in the middle of new path, extend it! */
        LOG (GNUNET_ERROR_TYPE_DEBUG,
             "Extending existing path %s to create inverse for incoming connection\n",
             GCPP_2s (cm_ctx.match));
        extend_path (cm_ctx.match,
                     &cpath[i + 1],
                     path_length - i - 1,
                     GNUNET_YES);
        /* Check that extension was successful */
        GNUNET_assert (cm_ctx.match->entries_length == path_length);
        return cm_ctx.match;
      }
      /* Eh, we found a match but couldn't use it? Something is wrong. */
      GNUNET_break (0);
    }
  }
 
  /* No match at all, create completely new path */
  path = GNUNET_new (struct CadetPeerPath);
  path->entries_length = path_length;
  path->entries = GNUNET_new_array (path->entries_length,
                                    struct CadetPeerPathEntry *);
  for (int i = path_length - 1; i >= 0; i--)
  {
    struct CadetPeerPathEntry *entry = GNUNET_new (struct CadetPeerPathEntry);
 
    path->entries[i] = entry;
    entry->peer = cpath[i];
    entry->path = path;
  }
  for (int i = path_length - 1; i >= 0; i--)
  {
    struct CadetPeerPathEntry *entry = path->entries[i];
 
    GCP_path_entry_add (entry->peer,
                        entry,
                        i);
  }
  recalculate_path_desirability (path);
  LOG (GNUNET_ERROR_TYPE_DEBUG,
       "Created new path %s to create inverse for incoming connection\n",
       GCPP_2s (path));
  path->hn = GCP_attach_path (cpath[path_length - 1],
                              path,
                              path_length - 1,
                              GNUNET_YES);
  return path;
}

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

path	path to return the length for

Returns

number of peers on the path

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

{
  return path->entries_length;
}

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_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

path	path to traverse
destination	destination node to get to, must be on path
off	offset 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.

{
  struct CadetPeerPathEntry *entry;
 
  GNUNET_assert (off < path->entries_length);
  entry = path->entries[off];
  GNUNET_assert (entry->peer == destination);
  return entry->cc;
}

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

path	the path to remember the cc
off	the offset where the cc ends
cc	the connection to remember

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

{
  struct CadetPeerPathEntry *entry;
 
  LOG (GNUNET_ERROR_TYPE_DEBUG,
       "Adding %s to path %s at offset %u\n",
       GCC_2s (cc),
       GCPP_2s (path),
       off);
  GNUNET_assert (off < path->entries_length);
  entry = path->entries[off];
  GNUNET_assert (NULL == entry->cc);
  GNUNET_assert (NULL != cc);
  entry->cc = cc;
}

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

path	the path to forget the cc
off	the offset where the cc ended
cc	the connection to forget

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

{
  struct CadetPeerPathEntry *entry;
 
  LOG (GNUNET_ERROR_TYPE_DEBUG,
       "Removing connection %s to path %s at offset %u\n",
       GCC_2s (cc),
       GCPP_2s (path),
       off);
  GNUNET_assert (off < path->entries_length);
  entry = path->entries[off];
  GNUNET_assert (cc == entry->cc);
  entry->cc = NULL;
}

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:

GCPP_find_peer()

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

Find peer's offset on path.

Parameters

path	path to search
cp	peer 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.

{
  for (unsigned int off = 0;
       off < path->entries_length;
       off++)
    if (cp == GCPP_get_peer_at_offset (path,
                                       off))
      return off;
  return UINT_MAX;
}

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_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

path	path 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.

{
  return path->desirability;
}

References CadetPeerPath::desirability.

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

Here is the caller graph for this function:

GCPP_release()

void GCPP_release

(

struct CadetPeerPath *

path

)

The given peer cp used to own this path.

However, it 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).

Parameters

path	the path that is being released

The given peer cp used to own this path.

Parameters

path	the path that is being released

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

{
  struct CadetPeerPathEntry *entry;
 
  LOG (GNUNET_ERROR_TYPE_DEBUG,
       "Owner releases path %s\n",
       GCPP_2s (path));
  path->hn = NULL;
  entry = path->entries[path->entries_length - 1];
  GNUNET_assert (path == entry->path);
  GNUNET_assert (NULL == entry->cc);
  /* cut 'off' end of path */
  GCP_path_entry_remove (entry->peer,
                         entry,
                         path->entries_length - 1);
  GNUNET_free (entry);
  path->entries[path->entries_length - 1] = NULL;
  path->entries_length--;
  /* see if new peer at the end likes this path any better */
  attach_path (path, 0);
  if (NULL == path->hn)
  {
    /* nobody wants us, discard the path */
    GNUNET_assert (0 == path->entries_length);
    GNUNET_assert (NULL == path->entries);
    GNUNET_free (path);
  }
}

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_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

path	peer path to inspect
off	offset to return, must be smaller than path length

Returns

peer at offset off

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

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

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

path	path to convert

Returns

string, statically allocated

Parameters

path	path to convert

Returns

string, to be freed by caller (unlike other *_2s APIs!)

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

{
  static char buf[2048];
  size_t off;
  const unsigned int max_plen = (sizeof(buf) - 16) / 5 - 2; /* 5 characters per entry */
 
  off = 0;
  for (unsigned int i = 0;
       i < path->entries_length;
       i++)
  {
    if ((path->entries_length > max_plen) &&
        (i == max_plen / 2))
      off += GNUNET_snprintf (&buf[off],
                              sizeof(buf) - off,
                              "...-");
    if ((path->entries_length > max_plen) &&
        (i > max_plen / 2) &&
        (i < path->entries_length - max_plen / 2))
      continue;
    off += GNUNET_snprintf (&buf[off],
                            sizeof(buf) - off,
                            "%s%s",
                            GNUNET_i2s (GCP_get_id (GCPP_get_peer_at_offset (
                                                      path,
                                                      i))),
                            (i == path->entries_length - 1) ? "" : "-");
  }
  GNUNET_snprintf (&buf[off],
                   sizeof(buf) - off,
                   "(%p)",
                   path);
  return buf;
}

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

Here is the call graph for this function:

Here is the caller graph for this function: