From e66a9b07d76995c00dab4c62ef22c73d2a3d7aaf Mon Sep 17 00:00:00 2001 From: Christian Grothoff Date: Mon, 16 Jan 2017 19:31:31 +0100 Subject: [PATCH] finish logic to maintain paths --- src/cadet/gnunet-service-cadet-new_dht.c | 27 +-- src/cadet/gnunet-service-cadet-new_dht.h | 19 +- src/cadet/gnunet-service-cadet-new_paths.c | 240 ++++++++++++++++----- src/cadet/gnunet-service-cadet-new_paths.h | 40 +--- src/cadet/gnunet-service-cadet-new_peer.c | 73 +++++-- src/cadet/gnunet-service-cadet-new_peer.h | 38 +++- 6 files changed, 282 insertions(+), 155 deletions(-) diff --git a/src/cadet/gnunet-service-cadet-new_dht.c b/src/cadet/gnunet-service-cadet-new_dht.c index 8cd3a648e..3cf3f0301 100644 --- a/src/cadet/gnunet-service-cadet-new_dht.c +++ b/src/cadet/gnunet-service-cadet-new_dht.c @@ -47,16 +47,6 @@ struct GCD_search_handle */ struct GNUNET_DHT_GetHandle *dhtget; - /** - * Provided callback to call when a path is found. - */ - GCD_search_callback callback; - - /** - * Provided closure. - */ - void *cls; - }; @@ -86,7 +76,6 @@ static struct GNUNET_SCHEDULER_Task *announce_id_task; static struct GNUNET_TIME_Relative announce_delay; - /** * Function to process paths received for a new peer addition. The recorded * paths form the initial tunnel, which can be optimized later. @@ -114,19 +103,13 @@ dht_get_id_handler (void *cls, struct GNUNET_TIME_Absolute exp, size_t size, const void *data) { - struct GCD_search_handle *h = cls; const struct GNUNET_HELLO_Message *hello = data; - struct CadetPeerPath *p; struct CadetPeer *peer; - p = GCPP_path_from_dht (get_path, + GCPP_try_path_from_dht (get_path, get_path_length, put_path, put_path_length); - h->callback (h->cls, - p); - GCPP_path_destroy (p); - if ( (size >= sizeof (struct GNUNET_HELLO_Message)) && (ntohs (hello->header.size) == size) && (size == GNUNET_HELLO_size (hello)) ) @@ -280,14 +263,10 @@ GCD_shutdown (void) * Search DHT for paths to @a peeR_id * * @param peer_id peer to search for - * @param callback function to call with results - * @param callback_cls closure for @a callback * @return handle to abort search */ struct GCD_search_handle * -GCD_search (const struct GNUNET_PeerIdentity *peer_id, - GCD_search_callback callback, - void *callback_cls) +GCD_search (const struct GNUNET_PeerIdentity *peer_id) { struct GNUNET_HashCode phash; struct GCD_search_handle *h; @@ -307,8 +286,6 @@ GCD_search (const struct GNUNET_PeerIdentity *peer_id, sizeof (*peer_id)); h = GNUNET_new (struct GCD_search_handle); - h->callback = callback; - h->cls = callback_cls; h->dhtget = GNUNET_DHT_get_start (dht_handle, /* handle */ GNUNET_BLOCK_TYPE_DHT_HELLO, /* type */ &phash, /* key to search */ diff --git a/src/cadet/gnunet-service-cadet-new_dht.h b/src/cadet/gnunet-service-cadet-new_dht.h index ff3923790..81f16ae99 100644 --- a/src/cadet/gnunet-service-cadet-new_dht.h +++ b/src/cadet/gnunet-service-cadet-new_dht.h @@ -46,18 +46,6 @@ extern "C" struct GCD_search_handle; -/** - * Callback called on each path found over the DHT. - * - * @param cls Closure. - * @param path An unchecked, unoptimized path to the target node. - * After callback will no longer be valid, unless #GCPP_acquire() is called! - */ -typedef void -(*GCD_search_callback) (void *cls, - struct CadetPeerPath *path); - - /** * Initialize the DHT subsystem. * @@ -66,6 +54,7 @@ typedef void void GCD_init (const struct GNUNET_CONFIGURATION_Handle *c); + /** * Shut down the DHT subsystem. */ @@ -77,14 +66,10 @@ GCD_shutdown (void); * Search DHT for paths to @a peeR_id * * @param peer_id peer to search for - * @param callback function to call with results - * @param callback_cls closure for @a callback * @return handle to abort search */ struct GCD_search_handle * -GCD_search (const struct GNUNET_PeerIdentity *peer_id, - GCD_search_callback callback, - void *callback_cls); +GCD_search (const struct GNUNET_PeerIdentity *peer_id); /** diff --git a/src/cadet/gnunet-service-cadet-new_paths.c b/src/cadet/gnunet-service-cadet-new_paths.c index 005d8e807..96f32a87b 100644 --- a/src/cadet/gnunet-service-cadet-new_paths.c +++ b/src/cadet/gnunet-service-cadet-new_paths.c @@ -24,6 +24,10 @@ * @brief Information we track per path. * @author Bartlomiej Polot * @author Christian Grothoff + * + * TODO: + * - path desirability score calculations are not done + * (and will be tricky to have during path changes) */ #include "platform.h" #include "gnunet-service-cadet-new_peer.h" @@ -69,7 +73,6 @@ struct CadetPeerPath }; - /** * Return how much we like keeping the path. This is an aggregate * score based on various factors, including the age of the path @@ -86,27 +89,7 @@ struct CadetPeerPath GNUNET_CONTAINER_HeapCostType GCPP_get_desirability (const struct CadetPeerPath *path) { - GNUNET_break (0); - return 0; -} - - -/** - * The given peer @a cp used to own this @a 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). - * - * @param path the path that is being released - * @param node entry in the heap of @a cp where this path is anchored - * should be used for updates to the desirability of this path - */ -void -GCPP_acquire (struct CadetPeerPath *path, - struct GNUNET_CONTAINER_HeapNode *node) -{ - GNUNET_assert (NULL == path->hn); - path->hn = node; + return path->desirability; } @@ -226,7 +209,8 @@ GCPP_release (struct CadetPeerPath *path) /* see if new peer at the end likes this path any better */ entry = &path->entries[path->entries_length - 1]; path->hn = GCP_attach_path (entry->peer, - path); + path, + path->entries_length); if (NULL != path->hn) return; /* yep, got attached, we are done. */ } @@ -275,17 +259,109 @@ GCPP_update_score (struct CadetPeerPath *path, /** - * 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. + * Closure for #find_peer_at() and #check_match(). + */ +struct CheckMatchContext +{ + + /** + * Set to a matching path, if any. + */ + struct CadetPeerPath *match; + + /** + * Array the combined paths. + */ + struct CadetPeer **cpath; + +}; + + +/** + * Check if the given path is identical on all of the + * hops until @a off, and not longer than @a off. If the + * @a path matches, store it in `match`. * - * FIXME: change API completely! - * Should in here create path transiently, then call - * callback, and then do path destroy (if applicable) - * without returning in the middle. + * @param cls the `struct CheckMatchContext` to check against + * @param path the path to check + * @param off offset to check at + * @return #GNUNET_YES (continue to iterate), or if found #GNUNET_NO + */ +static int +check_match (void *cls, + struct CadetPeerPath *path, + unsigned int off) +{ + struct CheckMatchContext *cm_ctx = cls; + + if (path->entries_length > off) + return GNUNET_YES; /* too long, cannot be useful */ + for (unsigned int i=0;icpath[i] != + GCPP_get_peer_at_offset (path, + i)) + return GNUNET_YES; /* missmatch, ignore */ + cm_ctx->match = path; + return GNUNET_NO; /* match, we are done! */ +} + + +/** + * Extend path @a path by the @a num_peers from the @a peers + * array, assuming the owners past the current owner want it. * - * FIXME: also need to nicely handle case that this path - * extends (lengthens!) an existing path. + * @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 + */ +static void +extend_path (struct CadetPeerPath *path, + struct CadetPeer **peers, + unsigned int num_peers) +{ + unsigned int old_len = path->entries_length; + struct GNUNET_CONTAINER_HeapNode *hn; + int i; + + /* If we extend an existing path, detach it from the + old owner and re-attach to the new one */ + hn = NULL; + for (i=num_peers-1;i>=0;i--) + { + /* FIXME: note that path->desirability is used, but not yet updated here! */ + hn = GCP_attach_path (peers[i], + path, + old_len + (unsigned int) i); + if (NULL != hn) + break; + } + if (NULL == hn) + return; /* none of the peers is interested in this path */ + GCP_detach_path (path->entries[old_len-1].peer, + path, + path->hn); + path->hn = hn; + GNUNET_array_grow (path->entries, + path->entries_length, + old_len + i); + for (;i >= 0;i--) + { + struct CadetPeerPathEntry *entry = &path->entries[old_len + i]; + + entry->peer = peers[i]; + entry->path = path; + GCP_path_entry_add (entry->peer, + entry, + old_len + i); + } +} + + +/** + * 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. * * @param get_path path of the get request * @param get_path_length lenght of @a get_path @@ -293,47 +369,93 @@ GCPP_update_score (struct CadetPeerPath *path, * @param put_path_length length of the @a put_path * @return a path through the network */ -struct CadetPeerPath * -GCPP_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) +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) { + struct CheckMatchContext cm_ctx; + struct CadetPeer *cpath[get_path_length + put_path_length]; struct CadetPeerPath *path; + struct GNUNET_CONTAINER_HeapNode *hn; + int i; + + /* precompute 'cpath' so we can avoid doing the lookups lots of times */ + 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 == get_path_length + put_path_length - 1) + { + /* Existing path includes this one, nothing to do! */ + return; + } + 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], + get_path_length + put_path_length - i); + return; + } + } + } + + /* No match at all, create completely new path */ path = GNUNET_new (struct CadetPeerPath); - path->entries_length = get_path_length + put_path_length; + + /* First, try to attach it */ + hn = NULL; + for (i=get_path_length + put_path_length-1;i>=0;i--) + { + path->entries_length = i; + /* FIXME: note that path->desirability is used, but not yet initialized here! */ + hn = GCP_attach_path (cpath[i], + path, + (unsigned int) i); + if (NULL != hn) + break; + } + if (NULL == hn) + { + /* None of the peers on the path care about it. */ + GNUNET_free (path); + return; + } + path->hn = hn; + path->entries_length = i; path->entries = GNUNET_new_array (path->entries_length, struct CadetPeerPathEntry); - for (unsigned int i=0;i=0;i--) { struct CadetPeerPathEntry *entry = &path->entries[i]; - const struct GNUNET_PeerIdentity *pid; - pid = (i < get_path_length) ? &get_path[get_path_length - i] : &put_path[path->entries_length - i]; - entry->peer = GCP_get (pid, - GNUNET_YES); + entry->peer = cpath[i]; entry->path = path; GCP_path_entry_add (entry->peer, entry, i); } - GNUNET_break (0); - return NULL; -} - - -/** - * Destroy a path, we no longer need it. - * - * @param p path to destroy. - */ -void -GCPP_path_destroy (struct CadetPeerPath *path) -{ - if (NULL != path->hn) - return; /* path was attached, to be kept! */ - path_destroy (path); } diff --git a/src/cadet/gnunet-service-cadet-new_paths.h b/src/cadet/gnunet-service-cadet-new_paths.h index 4b47784a0..f08d4a705 100644 --- a/src/cadet/gnunet-service-cadet-new_paths.h +++ b/src/cadet/gnunet-service-cadet-new_paths.h @@ -32,30 +32,21 @@ #include "gnunet-service-cadet-new.h" /** - * 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. + * 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. * * @param get_path path of the get request * @param get_path_length lenght of @a get_path * @param put_path path of the put request * @param put_path_length length of the @a put_path - * @return a path through the network - */ -struct CadetPeerPath * -GCPP_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); - - -/** - * Destroy a path, we no longer need it. - * - * @param path path to destroy. */ void -GCPP_path_destroy (struct CadetPeerPath *path); +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); /** @@ -142,21 +133,6 @@ GNUNET_CONTAINER_HeapCostType GCPP_get_desirability (const struct CadetPeerPath *path); -/** - * The given peer @a cp used to own this @a 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). - * - * @param path the path that is being released - * @param node entry in the heap of @a cp where this path is anchored - * should be used for updates to the desirability of this path - */ -void -GCPP_acquire (struct CadetPeerPath *path, - struct GNUNET_CONTAINER_HeapNode *node); - - /** * The given peer @a cp used to own this @a path. However, it is no * longer interested in maintaining it, so the path should be diff --git a/src/cadet/gnunet-service-cadet-new_peer.c b/src/cadet/gnunet-service-cadet-new_peer.c index 8c8b23820..9878c540e 100644 --- a/src/cadet/gnunet-service-cadet-new_peer.c +++ b/src/cadet/gnunet-service-cadet-new_peer.c @@ -385,19 +385,22 @@ GCP_path_entry_remove (struct CadetPeer *cp, * has plenty of paths, return NULL. * * @param cp peer to which the @a path leads to - * @param path a path looking for an owner + * @param path a path looking for an owner; may not be fully initialized yet! + * @param off offset of @a cp in @a 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) + struct CadetPeerPath *path, + unsigned int off) { 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, @@ -443,24 +446,21 @@ GCP_attach_path (struct CadetPeer *cp, /** - * Function called when the DHT finds a @a path to the peer (@a cls). + * This peer can no longer own @a path as the path + * has been extended and a peer further down the line + * is now the new owner. * - * @param cls the `struct CadetPeer` - * @param path the path that was found + * @param cp old owner of the @a path + * @param path path where the ownership is lost + * @param hn note in @a cp's path heap that must be deleted */ -static void -dht_result_cb (void *cls, - struct CadetPeerPath *path) +void +GCP_detach_path (struct CadetPeer *cp, + struct CadetPeerPath *path, + struct GNUNET_CONTAINER_HeapNode *hn) { - struct CadetPeer *cp = cls; - struct GNUNET_CONTAINER_HeapNode *hn; - - hn = GCP_attach_path (cp, - path); - if (NULL == hn) - return; - GCPP_acquire (path, - hn); + GNUNET_assert (path == + GNUNET_CONTAINER_heap_remove_node (hn)); } @@ -502,9 +502,7 @@ consider_peer_activate (struct CadetPeer *cp) if ( (NULL == cp->search_h) && (DESIRED_CONNECTIONS_PER_TUNNEL < cp->num_paths) ) cp->search_h - = GCD_search (&cp->pid, - &dht_result_cb, - cp); + = GCD_search (&cp->pid); } else { @@ -639,6 +637,41 @@ GCP_iterate_paths (struct CadetPeer *peer, } +/** + * Iterate over the paths to @a peer where + * @a peer is at distance @a dist from us. + * + * @param peer Peer to get path info. + * @param dist desired distance of @a peer to us on the path + * @param callback Function to call for every path. + * @param callback_cls Closure for @a callback. + * @return Number of iterated paths. + */ +unsigned int +GCP_iterate_paths_at (struct CadetPeer *peer, + unsigned int dist, + GCP_PathIterator callback, + void *callback_cls) +{ + unsigned int ret = 0; + + if (distpath_dll_length) + return 0; + for (struct CadetPeerPathEntry *pe = peer->path_heads[dist]; + NULL != pe; + pe = pe->next) + { + if (GNUNET_NO == + callback (callback_cls, + pe->path, + dist)) + return ret; + ret++; + } + return ret; +} + + /** * Get the tunnel towards a peer. * diff --git a/src/cadet/gnunet-service-cadet-new_peer.h b/src/cadet/gnunet-service-cadet-new_peer.h index e1c8476d1..780640674 100644 --- a/src/cadet/gnunet-service-cadet-new_peer.h +++ b/src/cadet/gnunet-service-cadet-new_peer.h @@ -119,6 +119,23 @@ GCP_iterate_paths (struct CadetPeer *cp, void *callback_cls); +/** + * Iterate over the paths to @a peer where + * @a peer is at distance @a dist from us. + * + * @param peer Peer to get path info. + * @param dist desired distance of @a peer to us on the path + * @param callback Function to call for every path. + * @param callback_cls Closure for @a callback. + * @return Number of iterated paths. + */ +unsigned int +GCP_iterate_paths_at (struct CadetPeer *peer, + unsigned int dist, + GCP_PathIterator callback, + void *callback_cls); + + /** * Remove an entry from the DLL of all of the paths that this peer is on. * @@ -174,13 +191,30 @@ GCP_drop_tunnel (struct CadetPeer *cp, * has plenty of paths, return NULL. * * @param cp peer to which the @a path leads to - * @param path a path looking for an owner + * @param path a path looking for an owner; may not be fully initialized yet! + * @param off offset of @a cp in @a 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); + struct CadetPeerPath *path, + unsigned int off); + + +/** + * This peer can no longer own @a path as the path + * has been extended and a peer further down the line + * is now the new owner. + * + * @param cp old owner of the @a path + * @param path path where the ownership is lost + * @param hn note in @a cp's path heap that must be deleted + */ +void +GCP_detach_path (struct CadetPeer *cp, + struct CadetPeerPath *path, + struct GNUNET_CONTAINER_HeapNode *hn); /** -- 2.25.1