GNUnet 0.22.1
gnunet-service-cadet_paths.h File Reference
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 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...
 
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...
 
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 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 *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_pathpath of the get request
get_path_lengthlength of get_path
put_pathpath of the put request
put_path_lengthlength 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_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,
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;
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);
589 return;
590 }
592 "Created new path %s based on information from DHT\n",
593 GCPP_2s (path));
594}
static struct GNUNET_PeerIdentity my_full_id
Peer identity.
Definition: gnunet-core.c:65
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.
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.
static void extend_path(struct CadetPeerPath *path, struct CadetPeer **peers_ext, 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 LOG(level,...)
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 structure associated with the peer.
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.
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.
@ GNUNET_YES
@ GNUNET_NO
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
@ GNUNET_ERROR_TYPE_DEBUG
#define GNUNET_new(type)
Allocate a struct or union of the given type.
#define GNUNET_new_array(n, type)
Allocate a size n array with structs or unions of the given type.
#define GNUNET_free(ptr)
Wrapper around free.
Entry in a peer path.
struct CadetPeer * peer
The peer at this offset of the path.
struct CadetPeerPath * path
Path this entry belongs to.
Information regarding a possible path to reach a peer.
unsigned int entries_length
Length of the entries array.
struct CadetPeerPathEntry ** entries
Array of all the peers on the path.
struct GNUNET_CONTAINER_HeapNode * hn
Node of this path in the owner's heap.
Struct containing all information regarding a given peer.
Closure for #find_peer_at() and check_match().
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,
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;
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}
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.
#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_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}
struct CadetConnection * cc
Connection using this path, or NULL for none.

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.

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:

◆ 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}
struct CadetPeer * GCPP_get_peer_at_offset(struct CadetPeerPath *path, unsigned int off)
Obtain the peer at offset off in path.

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
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}
GNUNET_CONTAINER_HeapCostType desirability
Desirability of the path.

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
paththe path that is being released

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 */
256 entry,
257 path->entries_length - 1);
258 GNUNET_free (entry);
259 path->entries[path->entries_length - 1] = NULL;
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);
269 }
270}
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.

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
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, statically allocated
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.
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 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: