From 3dfe0b93bba61ca11519adca8a901fd07563612c Mon Sep 17 00:00:00 2001 From: Bart Polot Date: Wed, 15 Oct 2014 00:55:38 +0000 Subject: Use optimizaiton of paths on store from DHT as well as on receipt from CONN_CREATE --- src/cadet/cadet_path.c | 66 ++++++++++++++++++++++++ src/cadet/cadet_path.h | 16 ++++++ src/cadet/gnunet-service-cadet_connection.c | 65 +----------------------- src/cadet/gnunet-service-cadet_dht.c | 78 ++++++----------------------- 4 files changed, 98 insertions(+), 127 deletions(-) diff --git a/src/cadet/cadet_path.c b/src/cadet/cadet_path.c index f378e124e..7e950a5ce 100644 --- a/src/cadet/cadet_path.c +++ b/src/cadet/cadet_path.c @@ -28,6 +28,9 @@ #include "cadet_path.h" #include "gnunet-service-cadet_peer.h" +#define LOG(level, ...) GNUNET_log_from (level,"cadet-pth",__VA_ARGS__) + + /** * @brief Destroy a path after some time has past. * @@ -146,6 +149,69 @@ path_invalidate (struct CadetPeerPath *p) } +/** + * Builds a path from a PeerIdentity array. + * + * @param peers PeerIdentity array. + * @param size Size of the @c peers array. + * @param myid ID of local peer, to find @c own_pos. + * @param own_pos Output parameter: own position in the path. + * + * @return Fixed and shortened path. + */ +struct CadetPeerPath * +path_build_from_peer_ids (struct GNUNET_PeerIdentity *peers, + unsigned int size, + GNUNET_PEER_Id myid, + unsigned int *own_pos) +{ + struct CadetPeerPath *path; + GNUNET_PEER_Id shortid; + unsigned int i; + unsigned int j; + unsigned int offset; + + /* Create path */ + LOG (GNUNET_ERROR_TYPE_DEBUG, " Creating path...\n"); + path = path_new (size); + *own_pos = 0; + offset = 0; + for (i = 0; i < size; i++) + { + LOG (GNUNET_ERROR_TYPE_DEBUG, " - %u: taking %s\n", + i, GNUNET_i2s (&peers[i])); + shortid = GNUNET_PEER_intern (&peers[i]); + + /* Check for loops / duplicates */ + for (j = 0; j < i - offset; j++) + { + if (path->peers[j] == shortid) + { + LOG (GNUNET_ERROR_TYPE_DEBUG, " already exists at pos %u\n", j); + offset = i - j; + LOG (GNUNET_ERROR_TYPE_DEBUG, " offset now %u\n", offset); + GNUNET_PEER_change_rc (shortid, -1); + } + } + LOG (GNUNET_ERROR_TYPE_DEBUG, " storing at %u\n", i - offset); + path->peers[i - offset] = shortid; + if (path->peers[i - offset] == myid) + *own_pos = i - offset; + } + path->length -= offset; + + if (path->peers[*own_pos] != myid) + { + /* create path: self not found in path through self */ + GNUNET_break_op (0); + path_destroy (path); + return NULL; + } + + return path; +} + + /** * Test if a path is valid (or at least not known to be invalid). * diff --git a/src/cadet/cadet_path.h b/src/cadet/cadet_path.h index 9991b380d..6281ddc05 100644 --- a/src/cadet/cadet_path.h +++ b/src/cadet/cadet_path.h @@ -158,6 +158,22 @@ path_is_valid (const struct CadetPeerPath *path); int path_destroy (struct CadetPeerPath *p); +/** + * Builds a path from a PeerIdentity array. + * + * @param peers PeerIdentity array. + * @param size Size of the @c peers array. + * @param myid ID of local peer, to find @c own_pos. + * @param own_pos Output parameter: own position in the path. + * + * @return Fixed and shortened path. + */ +struct CadetPeerPath * +path_build_from_peer_ids (struct GNUNET_PeerIdentity *peers, + unsigned int size, + GNUNET_PEER_Id myid, + unsigned int *own_pos); + /** * Path -> allocated one line string. Caller must free. * diff --git a/src/cadet/gnunet-service-cadet_connection.c b/src/cadet/gnunet-service-cadet_connection.c index a7a3b9121..147bf1e8e 100644 --- a/src/cadet/gnunet-service-cadet_connection.c +++ b/src/cadet/gnunet-service-cadet_connection.c @@ -1516,67 +1516,6 @@ add_to_peer (struct CadetConnection *c, struct CadetPeer *peer) } -/** - * Builds a path from a PeerIdentity array. - * - * @param peers PeerIdentity array. - * @param size Size of the @c peers array. - * @param own_pos Output parameter: own position in the path. - * - * @return Fixed and shortened path. - */ -static struct CadetPeerPath * -build_path_from_peer_ids (struct GNUNET_PeerIdentity *peers, - unsigned int size, - unsigned int *own_pos) -{ - struct CadetPeerPath *path; - GNUNET_PEER_Id shortid; - unsigned int i; - unsigned int j; - unsigned int offset; - - /* Create path */ - LOG (GNUNET_ERROR_TYPE_DEBUG, " Creating path...\n"); - path = path_new (size); - *own_pos = 0; - offset = 0; - for (i = 0; i < size; i++) - { - LOG (GNUNET_ERROR_TYPE_DEBUG, " - %u: taking %s\n", - i, GNUNET_i2s (&peers[i])); - shortid = GNUNET_PEER_intern (&peers[i]); - - /* Check for loops / duplicates */ - for (j = 0; j < i - offset; j++) - { - if (path->peers[j] == shortid) - { - LOG (GNUNET_ERROR_TYPE_DEBUG, " already exists at pos %u\n", j); - offset = i - j; - LOG (GNUNET_ERROR_TYPE_DEBUG, " offset now %u\n", offset); - GNUNET_PEER_change_rc (shortid, -1); - } - } - LOG (GNUNET_ERROR_TYPE_DEBUG, " storing at %u\n", i - offset); - path->peers[i - offset] = shortid; - if (path->peers[i - offset] == myid) - *own_pos = i - offset; - } - path->length -= offset; - - if (path->peers[*own_pos] != myid) - { - /* create path: self not found in path through self */ - GNUNET_break_op (0); - path_destroy (path); - return NULL; - } - - return path; -} - - /** * Log receipt of message on stderr (INFO level). * @@ -1656,8 +1595,8 @@ GCC_handle_create (void *cls, const struct GNUNET_PeerIdentity *peer, c = connection_get (cid); if (NULL == c) { - path = build_path_from_peer_ids ((struct GNUNET_PeerIdentity *) &msg[1], - size, &own_pos); + path = path_build_from_peer_ids ((struct GNUNET_PeerIdentity *) &msg[1], + size, myid, &own_pos); if (NULL == path) return GNUNET_OK; diff --git a/src/cadet/gnunet-service-cadet_dht.c b/src/cadet/gnunet-service-cadet_dht.c index 7d31603df..f18e868e3 100644 --- a/src/cadet/gnunet-service-cadet_dht.c +++ b/src/cadet/gnunet-service-cadet_dht.c @@ -119,77 +119,27 @@ path_build_from_dht (const struct GNUNET_PeerIdentity *get_path, const struct GNUNET_PeerIdentity *put_path, unsigned int put_path_length) { + size_t size = get_path_length + put_path_length; + struct GNUNET_PeerIdentity peers[size]; + const struct GNUNET_PeerIdentity *peer; struct CadetPeerPath *p; - GNUNET_PEER_Id id; + unsigned int own_pos; int i; - p = path_new (1); - p->peers[0] = myid; - GNUNET_PEER_change_rc (myid, 1); - i = get_path_length; - LOG (GNUNET_ERROR_TYPE_DEBUG, " GET has %d hops.\n", i); - for (i--; i >= 0; i--) + LOG (GNUNET_ERROR_TYPE_DEBUG, " GET has %d hops.\n", get_path_length); + for (i = 0 ; i < get_path_length; i++) { - id = GNUNET_PEER_intern (&get_path[i]); - if (p->length > 0 && id == p->peers[p->length - 1]) - { - LOG (GNUNET_ERROR_TYPE_DEBUG, " Optimizing 1 hop out.\n"); - GNUNET_PEER_change_rc (id, -1); - } - else - { - LOG (GNUNET_ERROR_TYPE_DEBUG, " Adding from GET: %s.\n", - GNUNET_i2s (&get_path[i])); - p->length++; - p->peers = GNUNET_realloc (p->peers, sizeof (GNUNET_PEER_Id) * p->length); - p->peers[p->length - 1] = id; - } + peer = &get_path[get_path_length - i - 1]; + LOG (GNUNET_ERROR_TYPE_DEBUG, " From GET: %s\n", GNUNET_i2s (peer)); + peers[i] = *peer; } - i = put_path_length; - LOG (GNUNET_ERROR_TYPE_DEBUG, " PUT has %d hops.\n", i); - for (i--; i >= 0; i--) + for (i = 0 ; i < put_path_length; i++) { - id = GNUNET_PEER_intern (&put_path[i]); - if (id == myid) - { - /* PUT path went through us, so discard the path up until now and start - * from here to get a much shorter (and loop-free) path. - */ - path_destroy (p); - p = path_new (0); - } - if (p->length > 0 && id == p->peers[p->length - 1]) - { - LOG (GNUNET_ERROR_TYPE_DEBUG, " Optimizing 1 hop out.\n"); - GNUNET_PEER_change_rc (id, -1); - } - else - { - LOG (GNUNET_ERROR_TYPE_DEBUG, " Adding from PUT: %s.\n", - GNUNET_i2s (&put_path[i])); - p->length++; - p->peers = GNUNET_realloc (p->peers, sizeof (GNUNET_PEER_Id) * p->length); - p->peers[p->length - 1] = id; - } + peer = &put_path[put_path_length - i - 1]; + LOG (GNUNET_ERROR_TYPE_DEBUG, " From PUT: %s\n", GNUNET_i2s (peer)); + peers[i + get_path_length] = *peer; } -#if CADET_DEBUG - if (get_path_length > 0) - LOG (GNUNET_ERROR_TYPE_DEBUG, " (first of GET: %s)\n", - GNUNET_i2s (&get_path[0])); - if (put_path_length > 0) - LOG (GNUNET_ERROR_TYPE_DEBUG, " (first of PUT: %s)\n", - GNUNET_i2s (&put_path[0])); - LOG (GNUNET_ERROR_TYPE_DEBUG, " In total: %d hops\n", - p->length); - for (i = 0; i < p->length; i++) - { - struct GNUNET_PeerIdentity peer_id; - - GNUNET_PEER_resolve (p->peers[i], &peer_id); - LOG (GNUNET_ERROR_TYPE_DEBUG, " %u: %s\n", p->peers[i], - GNUNET_i2s (&peer_id)); - } -#endif + p = path_build_from_peer_ids (peers, size, myid, &own_pos); return p; } -- cgit v1.2.3