From a44aa9923dd14613116939e659817f985cb89ef5 Mon Sep 17 00:00:00 2001 From: Bart Polot Date: Fri, 23 Sep 2011 10:17:48 +0000 Subject: [PATCH] Fixed bugs and completed API --- src/mesh/gnunet-service-mesh.c | 23 +--- src/mesh/mesh_tunnel_tree.c | 245 ++++++++++++++++++++------------- src/mesh/mesh_tunnel_tree.h | 124 +++++++++-------- src/mesh/test_mesh_path_api.c | 13 +- 4 files changed, 229 insertions(+), 176 deletions(-) diff --git a/src/mesh/gnunet-service-mesh.c b/src/mesh/gnunet-service-mesh.c index 77986f90c..9af81333a 100644 --- a/src/mesh/gnunet-service-mesh.c +++ b/src/mesh/gnunet-service-mesh.c @@ -818,7 +818,7 @@ path_build_from_dht (const struct GNUNET_PeerIdentity *const *get_path, GNUNET_PEER_Id id; int i; - p = GNUNET_malloc (sizeof (struct MeshPeerPath)); + p = path_new (0); for (i = 0; get_path[i] != NULL; i++) ; GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "MESH: GET has %d hops.\n", i); for (i--; i >= 0; i--) @@ -1606,9 +1606,7 @@ handle_mesh_path_create (void *cls, const struct GNUNET_PeerIdentity *peer, GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY); } - path = GNUNET_malloc (sizeof (struct MeshPeerPath)); - path->length = size; - path->peers = GNUNET_malloc (size * sizeof (GNUNET_PEER_Id)); + path = path_new (size); own_pos = 0; for (i = 0; i < size; i++) { @@ -1781,7 +1779,7 @@ handle_mesh_data_multicast (void *cls, const struct GNUNET_PeerIdentity *peer, * Using path here as just a collection of peers, not a path per se. */ neighbors.t = t; - neighbors.path = GNUNET_malloc (sizeof (struct MeshPeerPath)); + neighbors.path = path_new (0); GNUNET_CONTAINER_multihashmap_iterate (t->peers, &iterate_collect_neighbors, &neighbors); if (0 == neighbors.path->length) @@ -2459,14 +2457,9 @@ handle_local_tunnel_create (void *cls, struct GNUNET_SERVER_Client *client, GNUNET_SERVER_receive_done (client, GNUNET_SYSERR); return; } - t->tree = GNUNET_malloc (sizeof(struct MeshTunnelTree)); - t->tree->first_hops = GNUNET_CONTAINER_multihashmap_create(32); - t->tree->t = t; + t->tree = tree_new (t, myid); t->tree->refresh = REFRESH_PATH_TIME; - t->tree->root = GNUNET_malloc(sizeof(struct MeshTunnelTreeNode)); t->tree->root->status = MESH_PEER_READY; - t->tree->root->t = t; - t->tree->root->peer = myid; t->tree->me = t->tree->root; GNUNET_SERVER_receive_done (client, GNUNET_OK); @@ -2981,9 +2974,7 @@ core_connect (void *cls, const struct GNUNET_PeerIdentity *peer, GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "MESH: (self)\n"); return; } - path = GNUNET_malloc (sizeof (struct MeshPeerPath)); - path->length = 2; - path->peers = GNUNET_malloc (sizeof (GNUNET_PEER_Id) * 2); + path = path_new (2); path->peers[0] = myid; path->peers[1] = peer_info->id; path_add_to_peer (peer_info, path); @@ -3165,9 +3156,7 @@ run (void *cls, struct GNUNET_SERVER_Handle *server, /* Create a peer_info for the local peer */ peer = peer_info_get(&my_full_id); - p = GNUNET_malloc (sizeof (struct MeshPeerPath)); - p->peers = GNUNET_malloc (sizeof (GNUNET_PEER_Id)); - p->length = 1; + p = path_new (1); p->peers[0] = myid; path_add_to_peer(peer, p); diff --git a/src/mesh/mesh_tunnel_tree.c b/src/mesh/mesh_tunnel_tree.c index 766960dd4..748683a34 100644 --- a/src/mesh/mesh_tunnel_tree.c +++ b/src/mesh/mesh_tunnel_tree.c @@ -28,42 +28,28 @@ #include "mesh_tunnel_tree.h" -static void -debug_node(struct MeshTunnelTreeNode *n, uint16_t level) +/** + * Create a new path + * + * @param lenght How many hops will the path have. + * + * @return A newly allocated path with a peer array of the specified length. + */ +struct MeshPeerPath * +path_new (unsigned int length) { - struct MeshTunnelTreeNode *c; - uint16_t i; - - for (i = 0; i < level; i++) - fprintf(stderr, " "); - if (n->status == MESH_PEER_READY) - fprintf(stderr, "#"); - if (n->status == MESH_PEER_SEARCHING) - fprintf(stderr, "+"); - if (n->status == MESH_PEER_RELAY) - fprintf(stderr, "-"); - if (n->status == MESH_PEER_RECONNECTING) - fprintf(stderr, "*"); - - fprintf(stderr, "%u [%p] ", n->peer, n); - if (NULL != n->parent) - fprintf(stderr, "(-> %u)\n", n->parent->peer); - else - fprintf(stderr, "(root)\n"); - for (c = n->children_head; NULL != c; c = c->next) - debug_node(c, level + 1); -} - - + struct MeshPeerPath *p; -void -tree_debug(struct MeshTunnelTree *t) -{ - debug_node(t->root, 0); + p = GNUNET_malloc (sizeof(struct MeshPeerPath)); + if (length > 0) + { + p->length = length; + p->peers = GNUNET_malloc (length * sizeof(GNUNET_PEER_Id)); + } + return p; } - /** * Invert the path * @@ -84,22 +70,6 @@ path_invert (struct MeshPeerPath *path) } -/** - * Destroy the path and free any allocated resources linked to it - * - * @param p the path to destroy - * - * @return GNUNET_OK on success - */ -int -path_destroy (struct MeshPeerPath *p) -{ - GNUNET_PEER_decrement_rcs (p->peers, p->length); - GNUNET_free (p->peers); - GNUNET_free (p); - return GNUNET_OK; -} - /** * Find the first peer whom to send a packet to go down this path @@ -156,6 +126,129 @@ path_get_cost (struct MeshTunnelTree *t, struct MeshPeerPath *path) } +/** + * Destroy the path and free any allocated resources linked to it + * + * @param p the path to destroy + * + * @return GNUNET_OK on success + */ +int +path_destroy (struct MeshPeerPath *p) +{ + GNUNET_PEER_decrement_rcs (p->peers, p->length); + GNUNET_free (p->peers); + GNUNET_free (p); + return GNUNET_OK; +} + + + +/** + * Allocates and initializes a new node. + * Sets ID and parent of the new node and inserts it in the DLL of the parent + * + * @param parent Node that will be the parent from the new node, NULL for root + * @param peer Short Id of the new node + * + * @return Newly allocated node + */ +static struct MeshTunnelTreeNode * +tree_node_new(struct MeshTunnelTreeNode *parent, GNUNET_PEER_Id peer) +{ + struct MeshTunnelTreeNode *node; + + node = GNUNET_malloc(sizeof(struct MeshTunnelTreeNode)); + node->peer = peer; + GNUNET_PEER_change_rc(peer, 1); + node->parent = parent; + if (NULL != parent) + GNUNET_CONTAINER_DLL_insert(parent->children_head, + parent->children_tail, + node); + + return node; +} + + +static void +tree_node_debug(struct MeshTunnelTreeNode *n, uint16_t level) +{ + struct MeshTunnelTreeNode *c; + uint16_t i; + + for (i = 0; i < level; i++) + fprintf(stderr, " "); + if (n->status == MESH_PEER_READY) + fprintf(stderr, "#"); + if (n->status == MESH_PEER_SEARCHING) + fprintf(stderr, "+"); + if (n->status == MESH_PEER_RELAY) + fprintf(stderr, "-"); + if (n->status == MESH_PEER_RECONNECTING) + fprintf(stderr, "*"); + + fprintf(stderr, "%u [%p] ", n->peer, n); + if (NULL != n->parent) + fprintf(stderr, "(-> %u)\n", n->parent->peer); + else + fprintf(stderr, "(root)\n"); + for (c = n->children_head; NULL != c; c = c->next) + tree_node_debug(c, level + 1); +} + + +/** + * Destroys and frees the node and all children + * + * @param n Parent node to be destroyed + */ +static void +tree_node_destroy (struct MeshTunnelTreeNode *parent) +{ + struct MeshTunnelTreeNode *n; + struct MeshTunnelTreeNode *next; + + n = parent->children_head; + while (NULL != n) + { + next = n->next; + tree_node_destroy(n); + n = next; + } + GNUNET_PEER_change_rc(parent->peer, -1); + if (NULL != parent->parent) + GNUNET_CONTAINER_DLL_remove(parent->parent->children_head, + parent->parent->children_tail, + parent); + GNUNET_free(parent); +} + + + +/** + * Create a new tunnel tree associated to a tunnel + * + * @param t Tunnel this tree will represent + * @param peer A short peer id of the root of the tree + * + * @return A newly allocated and initialized tunnel tree + */ +struct MeshTunnelTree * +tree_new (struct MeshTunnel *t, GNUNET_PEER_Id peer) +{ + struct MeshTunnelTree *tree; + + tree = GNUNET_malloc(sizeof (struct MeshTunnelTree)); + tree->first_hops = GNUNET_CONTAINER_multihashmap_create(32); + tree->root = tree_node_new(NULL, peer); + tree->t = t; + tree->root->t = t; + + return tree; +} + + /** * Recursively find the given peer in the tree. * @@ -189,7 +282,7 @@ tree_find_peer (struct MeshTunnelTreeNode *parent, GNUNET_PEER_Id peer_id) * @param parent Node to be clean, potentially with children * @param cb Callback to use to notify about disconnected peers. */ -void +static void tree_mark_peers_disconnected (struct MeshTunnelTree *tree, struct MeshTunnelTreeNode *parent, MeshNodeDisconnectCB cb) @@ -225,7 +318,7 @@ tree_mark_peers_disconnected (struct MeshTunnelTree *tree, * @param hop If known, ID of the first hop. * If not known, NULL to find out and pass on children. */ -void +static void tree_update_first_hops (struct MeshTunnelTree *tree, struct MeshTunnelTreeNode *parent, struct GNUNET_PeerIdentity *hop) @@ -343,7 +436,7 @@ tree_get_path_to_peer(struct MeshTunnelTree *t, GNUNET_PEER_Id peer) GNUNET_PEER_Id myid = t->me->peer; n = tree_find_peer(t->me, peer); - p = GNUNET_malloc(sizeof(struct MeshPeerPath)); + p = path_new(0); /* Building the path (inverted!) */ while (n->peer != myid) @@ -496,56 +589,14 @@ tree_add_path (struct MeshTunnelTree *t, const struct MeshPeerPath *p, /** - * Allocates and initializes a new node. - * Sets ID and parent of the new node and inserts it in the DLL of the parent - * - * @param parent Node that will be the parent from the new node, NULL for root - * @param id Short Id of the new node + * Print the tree on stderr * - * @return Newly allocated node - */ -struct MeshTunnelTreeNode * -tree_node_new(struct MeshTunnelTreeNode *parent, GNUNET_PEER_Id id) -{ - struct MeshTunnelTreeNode *node; - - node = GNUNET_malloc(sizeof(struct MeshTunnelTreeNode)); - node->peer = id; - GNUNET_PEER_change_rc(id, 1); - node->parent = parent; - if (NULL != parent) - GNUNET_CONTAINER_DLL_insert(parent->children_head, - parent->children_tail, - node); - - return node; -} - - -/** - * Destroys and frees the node and all children - * - * @param n Parent node to be destroyed + * @param t The tree */ void -tree_node_destroy (struct MeshTunnelTreeNode *parent) +tree_debug(struct MeshTunnelTree *t) { - struct MeshTunnelTreeNode *n; - struct MeshTunnelTreeNode *next; - - n = parent->children_head; - while (NULL != n) - { - next = n->next; - tree_node_destroy(n); - n = next; - } - GNUNET_PEER_change_rc(parent->peer, -1); - if (NULL != parent->parent) - GNUNET_CONTAINER_DLL_remove(parent->parent->children_head, - parent->parent->children_tail, - parent); - GNUNET_free(parent); + tree_node_debug(t->root, 0); } @@ -578,4 +629,4 @@ tree_destroy (struct MeshTunnelTree *t) GNUNET_CONTAINER_multihashmap_iterate(t->first_hops, &iterate_free, NULL); GNUNET_CONTAINER_multihashmap_destroy(t->first_hops); GNUNET_free(t); -} \ No newline at end of file +} diff --git a/src/mesh/mesh_tunnel_tree.h b/src/mesh/mesh_tunnel_tree.h index a929f7a6d..252929549 100644 --- a/src/mesh/mesh_tunnel_tree.h +++ b/src/mesh/mesh_tunnel_tree.h @@ -141,13 +141,15 @@ struct MeshTunnelTree /************************* FUNCTIONS *****************************/ /******************************************************************************/ - /** - * Method called whenever a node has been marked as disconnected. + * Create a new path * - * @param node peer identity the tunnel stopped working with + * @param lenght How many hops will the path have. + * + * @return A newly allocated path with a peer array of the specified length. */ -typedef void (*MeshNodeDisconnectCB) (const struct MeshTunnelTreeNode * node); +struct MeshPeerPath * +path_new (unsigned int length); /** @@ -156,44 +158,33 @@ typedef void (*MeshNodeDisconnectCB) (const struct MeshTunnelTreeNode * node); * @param p the path to invert */ void -path_invert (struct MeshPeerPath *path); - - - -/** - * Destroy the path and free any allocated resources linked to it - * - * @param p the path to destroy - * - * @return GNUNET_OK on success - */ -int -path_destroy (struct MeshPeerPath *p); +path_invert (struct MeshPeerPath *p); /** * Find the first peer whom to send a packet to go down this path * - * @param t The tunnel to use + * @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); +path_get_first_hop (struct MeshTunnelTree *t, + GNUNET_PEER_Id peer); /** * Get the length of a path * - * @param path The path to measure, with the local peer at any point of it + * @param p The path to measure, with the local peer at any point of it * * @return Number of hops to reach destination * UINT_MAX in case the peer is not in the path */ unsigned int -path_get_length (struct MeshPeerPath *path); +path_get_length (struct MeshPeerPath *p); /** @@ -206,19 +197,54 @@ path_get_length (struct MeshPeerPath *path); * in the path */ unsigned int -path_get_cost (struct MeshTunnelTree *t, struct MeshPeerPath *path); +path_get_cost (struct MeshTunnelTree *t, + struct MeshPeerPath *path); + + +/** + * Destroy the path and free any allocated resources linked to it + * + * @param p the path to destroy + * + * @return GNUNET_OK on success + */ +int +path_destroy (struct MeshPeerPath *p); + + +/******************************************************************************/ + +/** + * Method called whenever a node has been marked as disconnected. + * + * @param node peer identity the tunnel stopped working with + */ +typedef void (*MeshNodeDisconnectCB) (const struct MeshTunnelTreeNode * node); + + +/** + * Create a new tunnel tree associated to a tunnel + * + * @param t Tunnel this tree will represent + * @param peer A short peer id of the root of the tree + * + * @return A newly allocated and initialized tunnel tree + */ +struct MeshTunnelTree * +tree_new (struct MeshTunnel *t, GNUNET_PEER_Id peer); /** * Recursively find the given peer in the tree. * - * @param t Tunnel where to look for the peer. - * @param peer Peer to find + * @param parent Parent node where to start looking. + * @param peer Short ID of peer to find. * * @return Pointer to the node of the peer. NULL if not found. */ struct MeshTunnelTreeNode * -tree_find_peer (struct MeshTunnelTreeNode *root, GNUNET_PEER_Id peer_id); +tree_find_peer (struct MeshTunnelTreeNode *parent, + GNUNET_PEER_Id peer); /** @@ -226,15 +252,18 @@ tree_find_peer (struct MeshTunnelTreeNode *root, GNUNET_PEER_Id peer_id); * The destination peer is NOT destroyed, it is returned in order to either set * a new path to it or destroy it explicitly, taking care of it's child nodes. * - * @param t Tunnel where to delete the path from. + * @param t Tunnel tree where to delete the path from. * @param peer Destination peer whose path we want to remove. - * @param cb Callback to use to notify about disconnected peers + * @param cb Callback to use to notify about which peers are going to be + * disconnected. * - * @return pointer to the pathless node, NULL on error + * @return pointer to the pathless node. + * NULL when not found */ struct MeshTunnelTreeNode * -tree_del_path (struct MeshTunnelTree *t, GNUNET_PEER_Id peer_id, - MeshNodeDisconnectCB cb); +tree_del_path (struct MeshTunnelTree *t, + GNUNET_PEER_Id peer, + MeshNodeDisconnectCB cb); /** @@ -242,13 +271,14 @@ tree_del_path (struct MeshTunnelTree *t, GNUNET_PEER_Id peer_id, * according to the path tree of some tunnel. * * @param t Tunnel from which to read the path tree - * @param peer_info Destination peer to whom we want a path + * @param peer Destination peer to whom we want a path * * @return A newly allocated individual path to reach the destination peer. * Path must be destroyed afterwards. */ struct MeshPeerPath * -tree_get_path_to_peer(struct MeshTunnelTree *t, GNUNET_PEER_Id peer); +tree_get_path_to_peer(struct MeshTunnelTree *t, + GNUNET_PEER_Id peer); /** @@ -262,40 +292,24 @@ tree_get_path_to_peer(struct MeshTunnelTree *t, GNUNET_PEER_Id peer); * GNUNET_SYSERR in case of error. */ int -tree_add_path (struct MeshTunnelTree *t, const struct MeshPeerPath *p, - MeshNodeDisconnectCB cb); +tree_add_path (struct MeshTunnelTree *t, + const struct MeshPeerPath *p, + MeshNodeDisconnectCB cb); /** - * Allocates and initializes a new node. - * Sets ID and parent of the new node and inserts it in the DLL of the parent - * - * @param parent Node that will be the parent from the new node, NULL for root - * @param id Short Id of the new node + * Print the tree on stderr * - * @return Newly allocated node - */ -struct MeshTunnelTreeNode * -tree_node_new(struct MeshTunnelTreeNode *parent, GNUNET_PEER_Id id); - - -/** - * Destroy the node and all children - * - * @param n Parent node to be destroyed + * @param t The tree */ void -tree_node_destroy (struct MeshTunnelTreeNode *n); +tree_debug(struct MeshTunnelTree *t); /** * Destroy the whole tree and free all used memory and Peer_Ids - * + * * @param t Tree to be destroyed */ void tree_destroy (struct MeshTunnelTree *t); - - -void -tree_debug(struct MeshTunnelTree *t); \ No newline at end of file diff --git a/src/mesh/test_mesh_path_api.c b/src/mesh/test_mesh_path_api.c index a397752e9..337ce35de 100644 --- a/src/mesh/test_mesh_path_api.c +++ b/src/mesh/test_mesh_path_api.c @@ -57,7 +57,7 @@ finish(void) { unsigned int i; - GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "test: Finishing...\n"); + GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "test: Finishing...\n"); for (i = 0; i < 10; i++) { GNUNET_free(pi[i]); @@ -340,11 +340,7 @@ main (int argc, char *argv[]) { GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "%u callbacks missed!\n", cb_call); failed++; - } - - path_destroy(path); - finish(); - + } node = tree_find_peer(tree->root, 2); if (node->peer != 2) { @@ -394,6 +390,9 @@ main (int argc, char *argv[]) GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "%u tests failed\n", failed); return 1; } - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "test ok\n"); + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "test: OK\n"); + path_destroy(path); + finish(); + return 0; } -- 2.25.1