From 5bf979114ebbb73014761dfb20f985a561c4876e Mon Sep 17 00:00:00 2001 From: Christian Grothoff Date: Sat, 21 Jan 2017 23:50:32 +0100 Subject: [PATCH] implement get_path_from_route --- .../gnunet-service-cadet-new_connection.c | 7 +- src/cadet/gnunet-service-cadet-new_core.c | 2 +- src/cadet/gnunet-service-cadet-new_paths.c | 86 ++++++++++++++++--- src/cadet/gnunet-service-cadet-new_peer.c | 40 +++++---- src/cadet/gnunet-service-cadet-new_peer.h | 4 +- 5 files changed, 106 insertions(+), 33 deletions(-) diff --git a/src/cadet/gnunet-service-cadet-new_connection.c b/src/cadet/gnunet-service-cadet-new_connection.c index 55b33e224..e22202a59 100644 --- a/src/cadet/gnunet-service-cadet-new_connection.c +++ b/src/cadet/gnunet-service-cadet-new_connection.c @@ -294,15 +294,16 @@ send_create (void *cls) cc->task = NULL; GNUNET_assert (GNUNET_YES == cc->mqm_ready); - path_length = GCPP_get_length (cc->path); + path_length = GCPP_get_length (cc->path) + 1; env = GNUNET_MQ_msg_extra (create_msg, path_length * sizeof (struct GNUNET_PeerIdentity), GNUNET_MESSAGE_TYPE_CADET_CONNECTION_CREATE); create_msg->cid = cc->cid; pids = (struct GNUNET_PeerIdentity *) &create_msg[1]; - for (unsigned int i=0;ipath, - i)); + i - 1)); LOG (GNUNET_ERROR_TYPE_DEBUG, "Sending CONNECTION_CREATE message for connection %s\n", GCC_2s (cc)); diff --git a/src/cadet/gnunet-service-cadet-new_core.c b/src/cadet/gnunet-service-cadet-new_core.c index d857a577e..26952f616 100644 --- a/src/cadet/gnunet-service-cadet-new_core.c +++ b/src/cadet/gnunet-service-cadet-new_core.c @@ -427,7 +427,7 @@ handle_connection_create (void *cls, return; } - path = GCPP_get_path_from_route (path_length, + path = GCPP_get_path_from_route (path_length - 1, pids); origin = GCP_get (&pids[0], GNUNET_YES); diff --git a/src/cadet/gnunet-service-cadet-new_paths.c b/src/cadet/gnunet-service-cadet-new_paths.c index d945487d0..2bd62f436 100644 --- a/src/cadet/gnunet-service-cadet-new_paths.c +++ b/src/cadet/gnunet-service-cadet-new_paths.c @@ -1,4 +1,3 @@ - /* This file is part of GNUnet. Copyright (C) 2001-2017 GNUnet e.V. @@ -18,7 +17,6 @@ Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ - /** * @file cadet/gnunet-service-cadet-new_paths.c * @brief Information we track per path. @@ -213,7 +211,8 @@ GCPP_release (struct CadetPeerPath *path) entry = &path->entries[path->entries_length - 1]; path->hn = GCP_attach_path (entry->peer, path, - path->entries_length); + path->entries_length, + GNUNET_NO); if (NULL != path->hn) return; /* yep, got attached, we are done. */ } @@ -316,11 +315,14 @@ check_match (void *cls, * @param path path to extend * @param peers list of peers beyond the end of @a path * @param num_peers length of the @a peers array + * @param force force attachment, even if we have other + * paths already */ static void extend_path (struct CadetPeerPath *path, struct CadetPeer **peers, - unsigned int num_peers) + unsigned int num_peers, + int force) { unsigned int old_len = path->entries_length; struct GNUNET_CONTAINER_HeapNode *hn; @@ -334,7 +336,8 @@ extend_path (struct CadetPeerPath *path, /* FIXME: note that path->desirability is used, but not yet updated here! */ hn = GCP_attach_path (peers[i], path, - old_len + (unsigned int) i); + old_len + (unsigned int) i, + GNUNET_YES); if (NULL != hn) break; } @@ -378,8 +381,8 @@ GCPP_try_path_from_dht (const struct GNUNET_PeerIdentity *get_path, const struct GNUNET_PeerIdentity *put_path, unsigned int put_path_length) { - struct CheckMatchContext cm_ctx; struct CadetPeer *cpath[get_path_length + put_path_length]; + struct CheckMatchContext cm_ctx; struct CadetPeerPath *path; struct GNUNET_CONTAINER_HeapNode *hn; int i; @@ -418,7 +421,8 @@ GCPP_try_path_from_dht (const struct GNUNET_PeerIdentity *get_path, /* Existing path ends in the middle of new path, extend it! */ extend_path (cm_ctx.match, &cpath[i], - get_path_length + put_path_length - i); + get_path_length + put_path_length - i, + GNUNET_NO); return; } } @@ -435,7 +439,8 @@ GCPP_try_path_from_dht (const struct GNUNET_PeerIdentity *get_path, /* FIXME: note that path->desirability is used, but not yet initialized here! */ hn = GCP_attach_path (cpath[i], path, - (unsigned int) i); + (unsigned int) i, + GNUNET_NO); if (NULL != hn) break; } @@ -466,15 +471,74 @@ GCPP_try_path_from_dht (const struct GNUNET_PeerIdentity *get_path, * We got an incoming connection, obtain the corresponding path. * * @param path_length number of segments on the @a path - * @param path through the network, in reverse order (we are at the end!) + * @param pids path through the network, in reverse order (we are at the end at index @a path_length) * @return corresponding path object */ struct CadetPeerPath * GCPP_get_path_from_route (unsigned int path_length, const struct GNUNET_PeerIdentity *pids) { - GNUNET_assert (0); // FIXME! - return NULL; + 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=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! */ + return cm_ctx.match; + } + if (cm_ctx.match->entries_length == i + 1) + { + /* Existing path ends in the middle of new path, extend it! */ + extend_path (cm_ctx.match, + &cpath[i], + path_length - i, + GNUNET_YES); + /* Check that extension was successful */ + GNUNET_assert (cm_ctx.match->entries_length == path_length); + return cm_ctx.match; + } + } + } + + /* 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 = &path->entries[i]; + + entry->peer = cpath[i]; + entry->path = path; + GCP_path_entry_add (entry->peer, + entry, + i); + } + path->hn = GCP_attach_path (cpath[path_length - 1], + path, + path_length - 1, + GNUNET_YES); + return path; } diff --git a/src/cadet/gnunet-service-cadet-new_peer.c b/src/cadet/gnunet-service-cadet-new_peer.c index a6485b0ad..cb9ea091b 100644 --- a/src/cadet/gnunet-service-cadet-new_peer.c +++ b/src/cadet/gnunet-service-cadet-new_peer.c @@ -584,33 +584,38 @@ GCP_path_entry_remove (struct CadetPeer *cp, * @param cp peer to which the @a path leads to * @param path a path looking for an owner; may not be fully initialized yet! * @param off offset of @a cp in @a path + * @param force force attaching the path * @return NULL if this peer does not care to become a new owner, * otherwise the node in the peer's path heap for the @a path. */ struct GNUNET_CONTAINER_HeapNode * GCP_attach_path (struct CadetPeer *cp, struct CadetPeerPath *path, - unsigned int off) + unsigned int off, + int force) { GNUNET_CONTAINER_HeapCostType desirability; struct CadetPeerPath *root; GNUNET_CONTAINER_HeapCostType root_desirability; struct GNUNET_CONTAINER_HeapNode *hn; - /* FIXME: desirability is not yet initialized; tricky! */ - desirability = GCPP_get_desirability (path); - if (GNUNET_NO == - GNUNET_CONTAINER_heap_peek2 (cp->path_heap, - (void **) &root, - &root_desirability)) + if (GNUNET_NO == force) { - root = NULL; - root_desirability = 0; - } + /* FIXME: desirability is not yet initialized; tricky! */ + desirability = GCPP_get_desirability (path); + if (GNUNET_NO == + GNUNET_CONTAINER_heap_peek2 (cp->path_heap, + (void **) &root, + &root_desirability)) + { + root = NULL; + root_desirability = 0; + } - if ( (DESIRED_CONNECTIONS_PER_TUNNEL > cp->num_paths) && - (desirability < root_desirability) ) - return NULL; + if ( (DESIRED_CONNECTIONS_PER_TUNNEL > cp->num_paths) && + (desirability < root_desirability) ) + return NULL; + } /* Yes, we'd like to add this path, add to our heap */ hn = GNUNET_CONTAINER_heap_insert (cp->path_heap, @@ -626,10 +631,11 @@ GCP_attach_path (struct CadetPeer *cp, unused paths around in the hope that we might be able to switch, even if the number of paths exceeds the threshold.) */ root = GNUNET_CONTAINER_heap_peek (cp->path_heap); - if (NULL == - GCPP_get_connection (root, - cp, - GCPP_get_length (root) - 1)) + if ( (path != root) && + (NULL == + GCPP_get_connection (root, + cp, + GCPP_get_length (root) - 1)) ) { /* Got plenty of paths to this destination, and this is a low-quality one that we don't care, allow it to die. */ diff --git a/src/cadet/gnunet-service-cadet-new_peer.h b/src/cadet/gnunet-service-cadet-new_peer.h index b59a43b86..8a1d3ed5c 100644 --- a/src/cadet/gnunet-service-cadet-new_peer.h +++ b/src/cadet/gnunet-service-cadet-new_peer.h @@ -193,13 +193,15 @@ GCP_drop_tunnel (struct CadetPeer *cp, * @param cp peer to which the @a path leads to * @param path a path looking for an owner; may not be fully initialized yet! * @param off offset of @a cp in @a path + * @param force for attaching the path * @return NULL if this peer does not care to become a new owner, * otherwise the node in the peer's path heap for the @a path. */ struct GNUNET_CONTAINER_HeapNode * GCP_attach_path (struct CadetPeer *cp, struct CadetPeerPath *path, - unsigned int off); + unsigned int off, + int force); /** -- 2.25.1