From 1cd8dfd4aa8312fae7602a0951f291e89ee68c16 Mon Sep 17 00:00:00 2001 From: Christian Grothoff Date: Mon, 16 Jan 2017 12:06:17 +0100 Subject: [PATCH] more work on peer and paths structures --- src/cadet/gnunet-service-cadet-new.h | 12 +++ src/cadet/gnunet-service-cadet-new_dht.h | 4 +- src/cadet/gnunet-service-cadet-new_paths.c | 110 +++++++++++++++++++-- src/cadet/gnunet-service-cadet-new_paths.h | 6 +- src/cadet/gnunet-service-cadet-new_peer.c | 64 ++++++++++-- 5 files changed, 172 insertions(+), 24 deletions(-) diff --git a/src/cadet/gnunet-service-cadet-new.h b/src/cadet/gnunet-service-cadet-new.h index 694a5f7fd..2b68862b7 100644 --- a/src/cadet/gnunet-service-cadet-new.h +++ b/src/cadet/gnunet-service-cadet-new.h @@ -28,6 +28,8 @@ #ifndef GNUNET_SERVICE_CADET_H #define GNUNET_SERVICE_CADET_H +#include "gnunet_util_lib.h" + /** * A client to the CADET service. */ @@ -77,6 +79,16 @@ struct CadetPeerPathEntry * Path this entry belongs to. */ struct CadetPeerPath *path; + + /** + * Path's historic score up to this point. Basically, how often did + * we succeed or fail to use the path up to this entry in a + * connection. Positive values indicate good experiences, negative + * values bad experiences. Code updating the score must guard + * against overflows. + */ + int score; + }; diff --git a/src/cadet/gnunet-service-cadet-new_dht.h b/src/cadet/gnunet-service-cadet-new_dht.h index 70f834de5..ff3923790 100644 --- a/src/cadet/gnunet-service-cadet-new_dht.h +++ b/src/cadet/gnunet-service-cadet-new_dht.h @@ -51,11 +51,11 @@ struct GCD_search_handle; * * @param cls Closure. * @param path An unchecked, unoptimized path to the target node. - * After callback will no longer be valid! + * After callback will no longer be valid, unless #GCPP_acquire() is called! */ typedef void (*GCD_search_callback) (void *cls, - const struct CadetPeerPath *path); + struct CadetPeerPath *path); /** diff --git a/src/cadet/gnunet-service-cadet-new_paths.c b/src/cadet/gnunet-service-cadet-new_paths.c index baffb20d2..663ce317f 100644 --- a/src/cadet/gnunet-service-cadet-new_paths.c +++ b/src/cadet/gnunet-service-cadet-new_paths.c @@ -26,9 +26,49 @@ * @author Christian Grothoff */ #include "platform.h" +#include "gnunet-service-cadet-new_peer.h" #include "gnunet-service-cadet-new_paths.h" +/** + * Information regarding a possible path to reach a peer. + */ +struct CadetPeerPath +{ + + /** + * Array of all the peers on the path. If @e hn is non-NULL, the + * last one is our owner. + */ + struct CadetPeerPathEntry *entries; + + /** + * Node of this path in the owner's heap. Used to update our position + * in the heap whenever our @e desirability changes. + */ + struct GNUNET_CONTAINER_HeapNode *hn; + + /** + * Connections using this path, by destination peer + * (each hop of the path could correspond to an + * active connection). + */ + struct GNUNET_CONTAINER_MultiPeerMap *connections; + + /** + * Desirability of the path. How unique is it for the various peers + * on it? + */ + GNUNET_CONTAINER_HeapCostType desirability; + + /** + * Length of the @e entries array. + */ + unsigned int entries_length; + +}; + + /** * Return how much we like keeping the path. This is an aggregate @@ -44,7 +84,7 @@ * @return desirability of the path, larger is more desirable */ GNUNET_CONTAINER_HeapCostType -GCPP_get_desirability (struct CadetPeerPath *path) +GCPP_get_desirability (const struct CadetPeerPath *path) { GNUNET_assert (0); return 0; @@ -72,22 +112,57 @@ GCPP_acquire (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). + * 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). * * @param path the path that is being released - * @param cp original final destination of @a path */ void -GCPP_release (struct CadetPeerPath *path, - struct CadetPeer *cp) +GCPP_release (struct CadetPeerPath *path) { GNUNET_assert (0); } +/** + * Updates the score for an entry on the path based + * on our experiences with using @a path. + * + * @param path the path to update + * @param off offset of the entry to update + * @param delta change in the score to apply + */ +void +GCPP_update_score (struct CadetPeerPath *path, + unsigned int off, + int delta) +{ + struct CadetPeerPathEntry *entry; + + GNUNET_assert (off < path->entries_length); + entry = &path->entries[off]; + + /* Add delta, with checks for overflows */ + if (delta >= 0) + { + if (delta + entry->score < entry->score) + entry->score = INT_MAX; + else + entry->score += delta; + } + else + { + if (delta + entry->score > entry->score) + entry->score = INT_MIN; + else + entry->score += delta; + } + + /* FIXME: update path desirability! */ +} + + /** * Create a peer path based on the result of a DHT lookup. * @@ -103,6 +178,25 @@ GCPP_path_from_dht (const struct GNUNET_PeerIdentity *get_path, const struct GNUNET_PeerIdentity *put_path, unsigned int put_path_length) { + struct CadetPeerPath *path; + + path = GNUNET_new (struct CadetPeerPath); + path->entries_length = get_path_length + put_path_length; + path->entries = GNUNET_new_array (path->entries_length, + struct CadetPeerPathEntry); + for (unsigned int i=0;ientries[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->path = path; + GCP_path_entry_add (entry->peer, + entry, + i); + } GNUNET_break (0); return NULL; } diff --git a/src/cadet/gnunet-service-cadet-new_paths.h b/src/cadet/gnunet-service-cadet-new_paths.h index 55e521bbf..e00b05a3d 100644 --- a/src/cadet/gnunet-service-cadet-new_paths.h +++ b/src/cadet/gnunet-service-cadet-new_paths.h @@ -81,7 +81,7 @@ GCPP_get_length (struct CadetPeerPath *path); * @return desirability of the path, larger is more desirable */ GNUNET_CONTAINER_HeapCostType -GCPP_get_desirability (struct CadetPeerPath *path); +GCPP_get_desirability (const struct CadetPeerPath *path); /** @@ -108,11 +108,9 @@ GCPP_acquire (struct CadetPeerPath *path, * the path desirable). * * @param path the path that is being released - * @param cp original final destination of @a path */ void -GCPP_release (struct CadetPeerPath *path, - struct CadetPeer *cp); +GCPP_release (struct CadetPeerPath *path); /** diff --git a/src/cadet/gnunet-service-cadet-new_peer.c b/src/cadet/gnunet-service-cadet-new_peer.c index 43e375c75..0ef65b7b6 100644 --- a/src/cadet/gnunet-service-cadet-new_peer.c +++ b/src/cadet/gnunet-service-cadet-new_peer.c @@ -37,6 +37,7 @@ #include "gnunet-service-cadet-new.h" #include "gnunet-service-cadet-new_dht.h" #include "gnunet-service-cadet-new_peer.h" +#include "gnunet-service-cadet-new_paths.h" #include "gnunet-service-cadet-new_tunnels.h" /** @@ -44,6 +45,12 @@ */ #define IDLE_PEER_TIMEOUT GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_MINUTES, 5) +/** + * How long do we keep paths around if we no longer care about the peer? + */ +#define IDLE_PATH_TIMEOUT GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_MINUTES, 2) + + /** * Struct containing all information regarding a given peer */ @@ -72,7 +79,8 @@ struct CadetPeer struct CadetPeerPathEntry **path_tails; /** - * MIN-heap of paths ending at this peer. Ordered by desirability. + * MIN-heap of paths owned by this peer (they also end at this + * peer). Ordered by desirability. */ struct GNUNET_CONTAINER_Heap *path_heap; @@ -186,8 +194,6 @@ destroy_peer (void *cls) } /* FIXME: clean up search_delayedXXX! */ - GNUNET_CONTAINER_multihashmap_destroy (cp->connections); - GNUNET_free_non_null (cp->hello); if (NULL != cp->hello_offer) { GNUNET_TRANSPORT_offer_hello_cancel (cp->hello_offer); @@ -198,6 +204,9 @@ destroy_peer (void *cls) GNUNET_ATS_connectivity_suggest_cancel (cp->connectivity_suggestion); cp->connectivity_suggestion = NULL; } + GNUNET_CONTAINER_multihashmap_destroy (cp->connections); + GNUNET_CONTAINER_heap_destroy (cp->path_heap); + GNUNET_free_non_null (cp->hello); GNUNET_free (cp); } @@ -241,6 +250,34 @@ GCP_destroy_all_peers () } +/** + * This peer may no longer be needed, consider cleaning it up. + * + * @param cp peer to clean up + */ +static void +consider_peer_destroy (struct CadetPeer *cp); + + +/** + * We really no longere care about a peer, stop hogging memory with paths to it. + * Afterwards, see if there is more to be cleaned up about this peer. + * + * @param cls a `struct CadetPeer`. + */ +static void +drop_paths (void *cls) +{ + struct CadetPeer *cp = cls; + struct CadetPeerPath *path; + + cp->destroy_task = NULL; + while (NULL != (path = GNUNET_CONTAINER_heap_remove_root (cp->path_heap))) + GCPP_release (path); + consider_peer_destroy (cp); +} + + /** * This peer may no longer be needed, consider cleaning it up. * @@ -260,17 +297,24 @@ consider_peer_destroy (struct CadetPeer *cp) return; /* still relevant! */ if (NULL != cp->core_mq) return; /* still relevant! */ - if (0 != cp->path_dll_length) - return; /* still relevant! */ if (0 != GNUNET_CONTAINER_multihashmap_size (cp->connections)) return; /* still relevant! */ + if (0 < GNUNET_CONTAINER_heap_get_size (cp->path_heap)) + { + cp->destroy_task = GNUNET_SCHEDULER_add_delayed (IDLE_PATH_TIMEOUT, + &drop_paths, + cp); + return; + } + if (0 < cp->path_dll_length) + return; /* still relevant! */ if (NULL != cp->hello) { /* relevant only until HELLO expires */ exp = GNUNET_TIME_absolute_get_remaining (GNUNET_HELLO_get_last_expiration (cp->hello)); cp->destroy_task = GNUNET_SCHEDULER_add_delayed (exp, - &destroy_peer, - cp); + &destroy_peer, + cp); return; } cp->destroy_task = GNUNET_SCHEDULER_add_delayed (IDLE_PEER_TIMEOUT, @@ -337,7 +381,7 @@ GCP_path_entry_remove (struct CadetPeer *cp, */ static void dht_result_cb (void *cls, - const struct CadetPeerPath *path) + struct CadetPeerPath *path) { struct CadetPeer *cp = cls; GNUNET_CONTAINER_HeapCostType desirability; @@ -368,8 +412,7 @@ dht_result_cb (void *cls, { /* Now we have way too many, drop least desirable */ root = GNUNET_CONTAINER_heap_remove_root (cp->path_heap); - GCPP_release (path, - cp); + GCPP_release (path); } } @@ -464,6 +507,7 @@ GCP_get (const struct GNUNET_PeerIdentity *peer_id, cp->pid = *peer_id; cp->connections = GNUNET_CONTAINER_multihashmap_create (32, GNUNET_YES); + cp->path_heap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN); cp->search_h = NULL; // FIXME: start search immediately!? cp->connectivity_suggestion = NULL; // FIXME: request with ATS!? -- 2.25.1