From 4acf4de35680033d0a05463a7478bbfb4b407a94 Mon Sep 17 00:00:00 2001 From: Bart Polot Date: Sat, 12 Nov 2011 00:33:15 +0000 Subject: Changed tree library: now assumes own short ID == 1, refactored code in library and mesh service, adapted and extended library testcase --- src/mesh/gnunet-service-mesh.c | 12 ++-- src/mesh/mesh_tunnel_tree.c | 136 +++++++++++++++++------------------------ src/mesh/mesh_tunnel_tree.h | 47 ++++---------- src/mesh/test_mesh_tree_api.c | 97 +++++++++++++++++++++-------- 4 files changed, 146 insertions(+), 146 deletions(-) (limited to 'src/mesh') diff --git a/src/mesh/gnunet-service-mesh.c b/src/mesh/gnunet-service-mesh.c index 09eb8df1a..7665909e6 100644 --- a/src/mesh/gnunet-service-mesh.c +++ b/src/mesh/gnunet-service-mesh.c @@ -1278,7 +1278,7 @@ send_destroy_path (struct MeshTunnel *t, GNUNET_PEER_Id destination) { GNUNET_PEER_resolve (p->peers[i], &pi[i]); } - send_message (&msg->header, path_get_first_hop (t->tree, destination)); + send_message (&msg->header, tree_get_first_hop (t->tree, destination)); } path_destroy (p); } @@ -1888,12 +1888,10 @@ tunnel_add_path (struct MeshTunnel *t, struct MeshPeerPath *p, GNUNET_assert (0 != own_pos); tree_add_path (t->tree, p, NULL, NULL); - if (tree_get_me (t->tree) == 0) - tree_set_me (t->tree, p->peers[own_pos]); if (own_pos < p->length - 1) { GNUNET_PEER_resolve (p->peers[own_pos + 1], &id); - tree_update_first_hops (t->tree, tree_get_me (t->tree), &id); + tree_update_first_hops (t->tree, myid, &id); } } @@ -2019,7 +2017,6 @@ tunnel_send_multicast (struct MeshTunnel *t, GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "MESH: sending a multicast packet...\n"); #endif - GNUNET_assert (tree_get_me (t->tree) != 0); mdata = GNUNET_malloc (sizeof (struct MeshMulticastData)); mdata->data_len = ntohs (msg->size); mdata->reference_counter = GNUNET_malloc (sizeof (unsigned int)); @@ -2280,7 +2277,7 @@ send_core_create_path (void *cls, size_t size, void *buf) info->peer->core_transmit[info->pos] = GNUNET_CORE_notify_transmit_ready (core_handle, 0, 0, GNUNET_TIME_UNIT_FOREVER_REL, - path_get_first_hop (t->tree, + tree_get_first_hop (t->tree, peer->id), size_needed, &send_core_create_path, info); @@ -2851,7 +2848,7 @@ handle_mesh_data_unicast (void *cls, const struct GNUNET_PeerIdentity *peer, } GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "MESH: not for us, retransmitting...\n"); - send_message (message, path_get_first_hop (t->tree, pid)); + send_message (message, tree_get_first_hop (t->tree, pid)); return GNUNET_OK; } @@ -3565,7 +3562,6 @@ handle_local_tunnel_create (void *cls, struct GNUNET_SERVER_Client *client, return; } t->tree = tree_new (myid); - tree_set_me (t->tree, myid); GNUNET_SERVER_receive_done (client, GNUNET_OK); return; diff --git a/src/mesh/mesh_tunnel_tree.c b/src/mesh/mesh_tunnel_tree.c index 63f5aef58..98ff9be88 100644 --- a/src/mesh/mesh_tunnel_tree.c +++ b/src/mesh/mesh_tunnel_tree.c @@ -181,45 +181,6 @@ tree_node_update_first_hops (struct MeshTunnelTree *tree, struct MeshTunnelTreeNode *parent, struct GNUNET_PeerIdentity *hop); -/** - * Find the first peer whom to send a packet to go down this path - * - * @param t The tunnel tree to use - * @param peer The peerinfo of the peer we are trying to reach - * - * @return peerinfo of the peer who is the first hop in the tunnel - * NULL on error - */ -struct GNUNET_PeerIdentity * -path_get_first_hop (struct MeshTunnelTree *t, GNUNET_PEER_Id peer) -{ - struct GNUNET_PeerIdentity id; - struct GNUNET_PeerIdentity *r; - - GNUNET_PEER_resolve (peer, &id); - r = GNUNET_CONTAINER_multihashmap_get (t->first_hops, &id.hashPubKey); - if (NULL == r) - { - struct MeshTunnelTreeNode *n; - - n = tree_find_peer (t, peer); - if (NULL != t->me && NULL != n) - { - tree_node_update_first_hops (t, n, NULL); - r = GNUNET_CONTAINER_multihashmap_get (t->first_hops, &id.hashPubKey); - GNUNET_assert (NULL != r); - } - else - { - GNUNET_log (GNUNET_ERROR_TYPE_WARNING, - "Tree structure inconsistent! me: %p, n: %p", t->me, n); - GNUNET_break (0); - } - } - - return r; -} - /** * Get the length of a path @@ -360,8 +321,8 @@ tree_node_update_first_hops (struct MeshTunnelTree *tree, while (aux != tree->me) { #if MESH_TREE_DEBUG - GNUNET_PEER_resolve (old->peer, &id); - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "tree: ... its not %s.\n", + GNUNET_PEER_resolve (aux->peer, &id); + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "tree: ... checking %s.\n", GNUNET_i2s (&id)); #endif old = aux; @@ -482,35 +443,6 @@ tree_new (GNUNET_PEER_Id peer) } -/** - * Set own identity in the tree - * - * @param tree Tree. - * @param peer A short peer id of local peer. - */ -void -tree_set_me (struct MeshTunnelTree *tree, GNUNET_PEER_Id peer) -{ - tree->me = tree_find_peer (tree, peer); -} - - -/** - * Get the id of the local node of the tree. - * - * @param tree Tree whose local id we want to now. - * - * @return Short peer id of local peer. - */ -GNUNET_PEER_Id -tree_get_me (struct MeshTunnelTree *tree) -{ - if (NULL != tree->me) - return tree->me->peer; - else - return (GNUNET_PEER_Id) 0; -} - /** * Set the status of a node. * @@ -566,6 +498,46 @@ tree_get_predecessor (struct MeshTunnelTree *tree) } +/** + * Find the first peer whom to send a packet to go down this path + * + * @param t The tunnel tree to use + * @param peer The peerinfo of the peer we are trying to reach + * + * @return peerinfo of the peer who is the first hop in the tunnel + * NULL on error + */ +struct GNUNET_PeerIdentity * +tree_get_first_hop (struct MeshTunnelTree *t, GNUNET_PEER_Id peer) +{ + struct GNUNET_PeerIdentity id; + struct GNUNET_PeerIdentity *r; + + GNUNET_PEER_resolve (peer, &id); + r = GNUNET_CONTAINER_multihashmap_get (t->first_hops, &id.hashPubKey); + if (NULL == r) + { + struct MeshTunnelTreeNode *n; + + n = tree_find_peer (t, peer); + if (NULL != t->me && NULL != n) + { + tree_node_update_first_hops (t, n, NULL); + r = GNUNET_CONTAINER_multihashmap_get (t->first_hops, &id.hashPubKey); + GNUNET_assert (NULL != r); + } + else + { + GNUNET_log (GNUNET_ERROR_TYPE_WARNING, + "Tree structure inconsistent! me: %p, n: %p", t->me, n); + GNUNET_break (0); + } + } + + return r; +} + + /** * Find the given peer in the tree. * @@ -805,7 +777,6 @@ tree_add_path (struct MeshTunnelTree *t, const struct MeshPeerPath *p, struct MeshTunnelTreeNode *n; struct MeshTunnelTreeNode *c; struct GNUNET_PeerIdentity id; - GNUNET_PEER_Id myid; int me; unsigned int i; @@ -816,10 +787,6 @@ tree_add_path (struct MeshTunnelTree *t, const struct MeshPeerPath *p, GNUNET_i2s (&id)); #endif - if (NULL != t->me) - myid = t->me->peer; - else - myid = 0; GNUNET_assert (0 != p->length); parent = n = t->root; if (n->peer != p->peers[0]) @@ -836,7 +803,7 @@ tree_add_path (struct MeshTunnelTree *t, const struct MeshPeerPath *p, * - Length of the path is expected to be log N (size of whole network). * - Each level of the tree is expected to have log n children (size of tree). */ - me = t->root->peer == myid ? 0 : -1; + me = t->root->peer == 1 ? 0 : -1; for (i = 1; i < p->length; i++) { #if MESH_TREE_DEBUG @@ -845,7 +812,7 @@ tree_add_path (struct MeshTunnelTree *t, const struct MeshPeerPath *p, GNUNET_i2s (&id)); #endif parent = n; - if (p->peers[i] == myid) + if (p->peers[i] == 1) me = i; for (c = n->children_head; NULL != c; c = c->next) { @@ -901,14 +868,19 @@ tree_add_path (struct MeshTunnelTree *t, const struct MeshPeerPath *p, #endif n = tree_node_new (parent, p->peers[i]); n->status = MESH_PEER_RELAY; - if (n->peer == myid) + if (n->peer == 1) + { t->me = n; + me = i; + } } i++; parent = n; } n->status = MESH_PEER_SEARCHING; + GNUNET_break (-1 != me); + /* Add info about first hop into hashmap. */ if (-1 != me && me < p->length - 1) { @@ -918,9 +890,15 @@ tree_add_path (struct MeshTunnelTree *t, const struct MeshPeerPath *p, p->length - 1); #endif GNUNET_PEER_resolve (p->peers[me + 1], &id); - tree_update_first_hops (t, p->peers[p->length - 1], &id); + tree_update_first_hops (t, p->peers[me + 1], &id); } #if MESH_TREE_DEBUG + else + { + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "MESH: was last in path, not updating first hops (%d/%u)\n", + me, p->length - 1); + } GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "tree: New node added.\n"); #endif return GNUNET_OK; diff --git a/src/mesh/mesh_tunnel_tree.h b/src/mesh/mesh_tunnel_tree.h index 094a617cb..5060fa1a7 100644 --- a/src/mesh/mesh_tunnel_tree.h +++ b/src/mesh/mesh_tunnel_tree.h @@ -100,19 +100,6 @@ struct MeshPeerPath * path_duplicate (struct MeshPeerPath *path); -/** - * Find the first peer whom to send a packet to go down this path - * - * @param t The tunnel tree to use - * @param peer The peerinfo of the peer we are trying to reach - * - * @return peerinfo of the peer who is the first hop in the tunnel - * NULL on error - */ -struct GNUNET_PeerIdentity * -path_get_first_hop (struct MeshTunnelTree *t, GNUNET_PEER_Id peer); - - /** * Get the length of a path * @@ -171,27 +158,6 @@ struct MeshTunnelTree * tree_new (GNUNET_PEER_Id peer); -/** - * Set own identity in the tree - * - * @param tree Tree. - * @param peer A short peer id of local peer. - */ -void -tree_set_me (struct MeshTunnelTree *tree, GNUNET_PEER_Id peer); - - -/** - * Get the id of the local id of the tree. - * - * @param tree Tree whose local id we want to now. - * - * @return Short peer id of local peer. - */ -GNUNET_PEER_Id -tree_get_me (struct MeshTunnelTree *tree); - - /** * Set the status of a node. * @@ -225,6 +191,19 @@ GNUNET_PEER_Id tree_get_predecessor (struct MeshTunnelTree *tree); +/** + * Find the first peer whom to send a packet to go down this path + * + * @param t The tunnel tree to use + * @param peer The peerinfo of the peer we are trying to reach + * + * @return peerinfo of the peer who is the first hop in the tunnel + * NULL on error + */ +struct GNUNET_PeerIdentity * +tree_get_first_hop (struct MeshTunnelTree *t, GNUNET_PEER_Id peer); + + /** * Find the given peer in the tree. * diff --git a/src/mesh/test_mesh_tree_api.c b/src/mesh/test_mesh_tree_api.c index cbe694c11..77fd799bd 100644 --- a/src/mesh/test_mesh_tree_api.c +++ b/src/mesh/test_mesh_tree_api.c @@ -72,18 +72,21 @@ test_assert (GNUNET_PEER_Id peer_id, enum MeshPeerState status, unsigned int i; int pre_failed; + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "test: Checking peer %u\n", peer_id); pre_failed = failed; n = tree_find_peer (tree, peer_id); if (n->peer != peer_id) { GNUNET_log (GNUNET_ERROR_TYPE_WARNING, - "Retrieved peer has wrong ID! (%u, %u)\n", n->peer, peer_id); + "Retrieved peer has wrong ID! (Got %u, expected %u)\n", + n->peer, peer_id); failed++; } if (n->status != status) { GNUNET_log (GNUNET_ERROR_TYPE_WARNING, - "Retrieved peer has wrong status! (%u, %u)\n", n->status, + "Retrieved peer has wrong status! (Got %u, expected %u)\n", + n->status, status); failed++; } @@ -91,15 +94,15 @@ test_assert (GNUNET_PEER_Id peer_id, enum MeshPeerState status, if (i != children) { GNUNET_log (GNUNET_ERROR_TYPE_WARNING, - "Retrieved peer wrong has number of children! (%u, %u)\n", i, - children); + "Retrieved peer wrong has number of children! (Got %u, expected %u)\n", + i, children); failed++; } if (0 != first_hop && - GNUNET_PEER_search (path_get_first_hop (tree, peer_id)) != first_hop) + GNUNET_PEER_search (tree_get_first_hop (tree, peer_id)) != first_hop) { - GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "Wrong first hop! (%u, %u)\n", - GNUNET_PEER_search (path_get_first_hop (tree, peer_id)), + GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "Wrong first hop! (Got %u, expected %u)\n", + GNUNET_PEER_search (tree_get_first_hop (tree, peer_id)), first_hop); failed++; } @@ -109,7 +112,7 @@ test_assert (GNUNET_PEER_Id peer_id, enum MeshPeerState status, GNUNET_PEER_resolve (peer_id, &id); GNUNET_log (GNUNET_ERROR_TYPE_WARNING, - "*** Peer %s (%u) has failed %d checks! (real, expected)\n", + "*** Peer %s (%u) has failed %d checks!\n", GNUNET_i2s (&id), peer_id, failed - pre_failed); } } @@ -145,7 +148,6 @@ int main (int argc, char *argv[]) { struct MeshTunnelTreeNode *node; - struct MeshTunnelTreeNode *node2; struct MeshPeerPath *path; struct MeshPeerPath *path1; unsigned int i; @@ -201,7 +203,7 @@ main (int argc, char *argv[]) test_assert (2, MESH_PEER_RELAY, 1, 0); test_assert (1, MESH_PEER_ROOT, 1, 0); - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "test: Adding third path...\n"); + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "test: Adding third path 1 2 3 5\n"); path->length++; path->peers[3] = 5; tree_add_path (tree, path, &cb, NULL); @@ -213,18 +215,17 @@ main (int argc, char *argv[]) test_assert (2, MESH_PEER_RELAY, 1, 0); test_assert (1, MESH_PEER_ROOT, 1, 0); - node = tree_find_peer (tree, 5); - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "test: Deleting third path...\n"); - node->status = MESH_PEER_READY; + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "test: Deleting third path (5)\n"); + tree_set_status(tree, 5, MESH_PEER_READY); cb_call = 1; - node2 = tree_del_path (tree, 5, &cb, NULL); + node = tree_del_path (tree, 5, &cb, NULL); tree_debug (tree); if (cb_call != 0) { GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "%u callbacks missed!\n", cb_call); failed++; } - if (node2->peer != 5) + if (node->peer != 5) { GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "Retrieved peer != original\n"); failed++; @@ -236,7 +237,7 @@ main (int argc, char *argv[]) test_assert (1, MESH_PEER_ROOT, 1, 0); GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "test: Destroying node copy...\n"); - GNUNET_free (node2); + GNUNET_free (node); GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "test: Adding new shorter first path...\n"); @@ -261,30 +262,76 @@ main (int argc, char *argv[]) GNUNET_free (path); tree_destroy (tree); + /****************************************************************************/ + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "test:\n"); GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "test: Testing relay trees\n"); for (i = 0; i < 10; i++) { GNUNET_break (i + 1 == GNUNET_PEER_intern (pi[i])); } - tree = tree_new (1); - path = path_new (3); - path->peers[0] = 1; - path->peers[1] = 2; + tree = tree_new (2); + path = path_new (8); + path->peers[0] = 2; + path->peers[1] = 1; path->peers[2] = 3; path->length = 3; - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "test: Adding first path: 1 2 3\n"); + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "test: Adding first path: 2 1 3\n"); tree_add_path (tree, path, &cb, NULL); tree_debug (tree); - tree_set_me (tree, 2); test_assert (3, MESH_PEER_SEARCHING, 0, 3); - test_assert (2, MESH_PEER_RELAY, 1, 0); - test_assert (1, MESH_PEER_ROOT, 1, 0); + test_assert (1, MESH_PEER_RELAY, 1, 0); + test_assert (2, MESH_PEER_ROOT, 1, 0); + + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "test: Adding long path: 2 1 4 5 3\n"); + path->peers[2] = 4; + path->peers[3] = 5; + path->peers[4] = 3; + path->length = 5; + tree_add_path (tree, path, &cb, NULL); + tree_debug (tree); - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "test: Adding same path: 1 2 3\n"); + test_assert (3, MESH_PEER_SEARCHING, 0, 4); + test_assert (5, MESH_PEER_RELAY, 1, 4); + test_assert (4, MESH_PEER_RELAY, 1, 4); + test_assert (1, MESH_PEER_RELAY, 1, 0); + test_assert (2, MESH_PEER_ROOT, 1, 0); + + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "test: Even longer path: 2 6 1 7 8 4 5 3\n"); + path->peers[0] = 2; + path->peers[1] = 6; + path->peers[2] = 1; + path->peers[3] = 7; + path->peers[4] = 8; + path->peers[5] = 4; + path->peers[6] = 5; + path->peers[7] = 3; + path->length = 8; + tree_add_path (tree, path, &cb, NULL); + tree_debug (tree); + + test_assert (3, MESH_PEER_SEARCHING, 0, 7); + test_assert (5, MESH_PEER_RELAY, 1, 7); + test_assert (4, MESH_PEER_RELAY, 1, 7); + test_assert (8, MESH_PEER_RELAY, 1, 7); + test_assert (7, MESH_PEER_RELAY, 1, 7); + test_assert (1, MESH_PEER_RELAY, 1, 0); + test_assert (6, MESH_PEER_RELAY, 1, 0); + test_assert (2, MESH_PEER_ROOT, 1, 0); + + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "test: Adding first path: 2 1 3\n"); + path->peers[1] = 1; + path->peers[2] = 3; + path->length = 3; tree_add_path (tree, path, &cb, NULL); + tree_debug (tree); + + test_assert (3, MESH_PEER_SEARCHING, 0, 3); + test_assert (1, MESH_PEER_RELAY, 1, 0); + test_assert (2, MESH_PEER_ROOT, 1, 0); GNUNET_free (path->peers); GNUNET_free (path); -- cgit v1.2.3