From 1c91d8d5152a33db3522cc98c0b44eeeffb7eaa0 Mon Sep 17 00:00:00 2001 From: Bart Polot Date: Wed, 2 Nov 2011 18:46:43 +0000 Subject: [PATCH] Changed tree library to be completely detached from mesh, adapted testcases --- src/mesh/Makefile.am | 12 +- src/mesh/gnunet-service-mesh.c | 191 +++++++-------- src/mesh/mesh.h | 5 + src/mesh/mesh_tunnel_tree.c | 417 ++++++++++++++++++++++++++------- src/mesh/mesh_tunnel_tree.h | 172 +++++++------- src/mesh/test_mesh_path_api.c | 314 ------------------------- 6 files changed, 520 insertions(+), 591 deletions(-) delete mode 100644 src/mesh/test_mesh_path_api.c diff --git a/src/mesh/Makefile.am b/src/mesh/Makefile.am index aebe06e6e..860e7a205 100644 --- a/src/mesh/Makefile.am +++ b/src/mesh/Makefile.am @@ -39,7 +39,7 @@ libgnunetmesh_la_LDFLAGS = \ check_PROGRAMS = \ test_mesh_api \ - test_mesh_path_api \ + test_mesh_tree_api \ test_mesh_local_1 \ test_mesh_local_2 \ test_mesh_small_unicast \ @@ -55,12 +55,12 @@ test_mesh_api_DEPENDENCIES = \ libgnunetmesh.la \ $(top_builddir)/src/util/libgnunetutil.la -test_mesh_path_api_SOURCES = \ - test_mesh_path_api.c mesh_tunnel_tree.c -test_mesh_path_api_LDADD = \ +test_mesh_tree_api_SOURCES = \ + test_mesh_tree_api.c +test_mesh_tree_api_LDADD = \ $(top_builddir)/src/util/libgnunetutil.la \ $(top_builddir)/src/dht/libgnunetdht.la -test_mesh_path_api_DEPENDENCIES = \ +test_mesh_tree_api_DEPENDENCIES = \ libgnunetmesh.la \ $(top_builddir)/src/dht/libgnunetdht.la @@ -109,7 +109,7 @@ test_mesh_small_multicast_DEPENDENCIES = \ if ENABLE_TEST_RUN -TESTS = test_0 test_mesh_api test_mesh_path_api test_mesh_local_1 test_mesh_local_2 test_1 test_mesh_small_unicast +TESTS = test_0 test_mesh_api test_mesh_tree_api test_mesh_local_1 test_mesh_local_2 test_1 test_mesh_small_unicast endif EXTRA_DIST = \ diff --git a/src/mesh/gnunet-service-mesh.c b/src/mesh/gnunet-service-mesh.c index bfcfec92b..4b1fca931 100644 --- a/src/mesh/gnunet-service-mesh.c +++ b/src/mesh/gnunet-service-mesh.c @@ -1883,7 +1883,7 @@ tunnel_add_peer (struct MeshTunnel *t, struct MeshPeerInfo *peer) tree_add_path (t->tree, best_p, ¬ify_peer_disconnected, t); if (GNUNET_SCHEDULER_NO_TASK == t->path_refresh_task) t->path_refresh_task = - GNUNET_SCHEDULER_add_delayed (t->tree->refresh, &path_refresh, t); + GNUNET_SCHEDULER_add_delayed (REFRESH_PATH_TIME, &path_refresh, t); } else { @@ -1911,12 +1911,14 @@ tunnel_add_path (struct MeshTunnel *t, GNUNET_assert (0 != own_pos); tree_add_path(t->tree, p, NULL, NULL); - if (NULL == t->tree->me) - t->tree->me = tree_find_peer(t->tree->root, p->peers[own_pos]); + 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, t->tree->me, &id); + tree_update_first_hops(t->tree, + tree_get_me (t->tree), + &id); } } @@ -1952,7 +1954,7 @@ tunnel_notify_connection_broken (struct MeshTunnel *t, } if (pid != myid) { - if (NULL != t->tree->me->parent) + if (tree_get_predecessor(t->tree) != 0) { /* We are the peer still connected, notify owner of the disconnection. */ struct GNUNET_MESH_PathBroken msg; @@ -1964,7 +1966,7 @@ tunnel_notify_connection_broken (struct MeshTunnel *t, msg.tid = htonl (t->id.tid); msg.peer1 = my_full_id; GNUNET_PEER_resolve (pid, &msg.peer2); - GNUNET_PEER_resolve (t->tree->me->parent->peer, &neighbor); + GNUNET_PEER_resolve (tree_get_predecessor (t->tree), &neighbor); send_message (&msg.header, &neighbor); } } @@ -1972,9 +1974,13 @@ tunnel_notify_connection_broken (struct MeshTunnel *t, } -struct AliasedData +struct MeshMulticastData { - unsigned int reference_counter; + struct MeshTunnel *t; + + GNUNET_SCHEDULER_TaskIdentifier *task; + + unsigned int *reference_counter; size_t data_len; @@ -1982,94 +1988,100 @@ struct AliasedData }; +/** + * Send a multicast packet to a neighbor. + */ +static void +tunnel_send_multicast_iterator (void *cls, + GNUNET_PEER_Id neighbor_id) +{ + struct MeshMulticastData *mdata = cls; + struct MeshDataDescriptor *info; + struct GNUNET_PeerIdentity neighbor; + unsigned int i; + + info = GNUNET_malloc (sizeof (struct MeshDataDescriptor)); + + info->data = mdata->data; + info->size = mdata->data_len; + info->copies = mdata->reference_counter; + (*(mdata->reference_counter))++; + + if (NULL != mdata->t->client) + { + info->client = mdata->t->client->handle; + info->timeout_task = mdata->task; + } + info->destination = neighbor_id; + GNUNET_PEER_resolve (neighbor_id, &neighbor); +#if MESH_DEBUG + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "MESH: sending to %s...\n", + GNUNET_i2s (&neighbor)); +#endif + info->peer = peer_info_get(&neighbor); + GNUNET_assert (NULL != info->peer); + i = peer_info_transmit_slot(info->peer); + info->handler_n = i; + info->peer->infos[i] = info; + info->peer->types[i] = GNUNET_MESSAGE_TYPE_MESH_MULTICAST; + info->peer->core_transmit[i] = + GNUNET_CORE_notify_transmit_ready (core_handle, + 0, + 0, + GNUNET_TIME_UNIT_FOREVER_REL, + &neighbor, + info->size, + &send_core_data_multicast, info); +} + /** * Send a message in a tunnel in multicast, sending a copy to each child node * down the local one in the tunnel tree. * * @param t Tunnel in which to send the data. * @param msg Message to be sent - * - * @return Number of copies sent. - * - * TODO: unifiy shared resources and reference counter management */ -static int +static void tunnel_send_multicast (struct MeshTunnel *t, const struct GNUNET_MessageHeader *msg) { - struct GNUNET_PeerIdentity neighbor; - struct MeshDataDescriptor *info; - struct MeshTunnelTreeNode *n; - struct MeshTunnelTreeNode *counter; - GNUNET_SCHEDULER_TaskIdentifier *task; - unsigned int *copies; - unsigned int i; - size_t size; - void *data; + struct MeshMulticastData *mdata; +#if MESH_DEBUG GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "MESH: sending a multicast packet...\n"); - size = ntohs (msg->size); - GNUNET_assert (NULL != t->tree->me); - n = t->tree->me->children_head; - if (NULL == n) - { - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, - "MESH: no children in the tree, no one to send.\n"); - return 0; - } - copies = GNUNET_malloc (sizeof (unsigned int)); - for (counter = n; NULL != counter; counter = counter->next) - (*copies)++; - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "MESH: (%u copies)\n", *copies); - data = GNUNET_malloc (size); - memcpy (data, msg, size); +#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)); + mdata->data = GNUNET_malloc (mdata->data_len); + memcpy (mdata->data, msg, mdata->data_len); if (NULL != t->client) { - task = GNUNET_malloc (sizeof (GNUNET_SCHEDULER_TaskIdentifier)); - *task = GNUNET_SCHEDULER_add_delayed (UNACKNOWLEDGED_WAIT, - &client_allow_send, - t->client->handle); + mdata->task = GNUNET_malloc (sizeof (GNUNET_SCHEDULER_TaskIdentifier)); + *(mdata->task) = GNUNET_SCHEDULER_add_delayed (UNACKNOWLEDGED_WAIT, + &client_allow_send, + t->client->handle); } - else - task = NULL; // So GCC shuts up about task being potentially uninitialized - while (NULL != n) - { - info = GNUNET_malloc (sizeof (struct MeshDataDescriptor)); - // info->shared_data = aliased_data; - // info->shared_data->reference_counter++; - - info->data = data; - info->size = size; - info->copies = copies; - if (NULL != t->client) + tree_iterate_children (t->tree, &tunnel_send_multicast_iterator, mdata); + if (*(mdata->reference_counter) == 0) + { + GNUNET_free (mdata->data); + GNUNET_free (mdata->reference_counter); + if (NULL != mdata->task) { - info->client = t->client->handle; - info->timeout_task = task; + GNUNET_free (mdata->task); } - info->destination = n->peer; - GNUNET_PEER_resolve (n->peer, &neighbor); - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, - "MESH: sending to %s...\n", - GNUNET_i2s (&neighbor)); - info->peer = peer_info_get(&neighbor); - GNUNET_assert (NULL != info->peer); - i = peer_info_transmit_slot(info->peer); - info->handler_n = i; - info->peer->infos[i] = info; - info->peer->types[i] = GNUNET_MESSAGE_TYPE_MESH_MULTICAST; - info->peer->core_transmit[i] = - GNUNET_CORE_notify_transmit_ready (core_handle, - 0, - 0, - GNUNET_TIME_UNIT_FOREVER_REL, - &neighbor, - size, - &send_core_data_multicast, info); - n = n->next; - } - return *copies; + } + GNUNET_free (mdata); +#if MESH_DEBUG + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "MESH: sending a multicast packet done\n"); +#endif + return; } @@ -2145,7 +2157,6 @@ tunnel_destroy (struct MeshTunnel *t) GNUNET_break (GNUNET_YES == GNUNET_CONTAINER_multihashmap_remove (incoming_tunnels, &hash, t)); } - if (NULL != t->peers) { GNUNET_CONTAINER_multihashmap_iterate(t->peers, @@ -2186,8 +2197,7 @@ static void tunnel_delete_peer (struct MeshTunnel *t, GNUNET_PEER_Id peer) { - GNUNET_break (GNUNET_OK == tree_del_peer (t->tree, peer, NULL, NULL)); - if (NULL == t->tree->root) + if (GNUNET_NO == tree_del_peer (t->tree, peer, NULL, NULL)) tunnel_destroy (t); } @@ -3039,7 +3049,7 @@ handle_mesh_data_to_orig (void *cls, const struct GNUNET_PeerIdentity *peer, GNUNET_break (0); return GNUNET_OK; } - GNUNET_PEER_resolve (t->tree->me->parent->peer, &id); + GNUNET_PEER_resolve (tree_get_predecessor(t->tree), &id); send_message (message, &id); return GNUNET_OK; @@ -3066,7 +3076,6 @@ handle_mesh_path_ack (void *cls, const struct GNUNET_PeerIdentity *peer, { struct GNUNET_MESH_PathACK *msg; struct GNUNET_PeerIdentity id; - struct MeshTunnelTreeNode *n; struct MeshPeerInfo *peer_info; struct MeshTunnel *t; @@ -3096,20 +3105,14 @@ handle_mesh_path_ack (void *cls, const struct GNUNET_PeerIdentity *peer, t->dht_get_type = NULL; } peer_info = peer_info_get (&msg->peer_id); - n = tree_find_peer(t->tree->root, peer_info->id); - if (NULL == n) - { - GNUNET_break_op (0); - return GNUNET_OK; - } - n->status = MESH_PEER_READY; + tree_set_status(t->tree, peer_info->id, MESH_PEER_READY); send_client_peer_connected(t, peer_info->id); return GNUNET_OK; } - + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "MESH: not for us, retransmitting...\n"); - GNUNET_PEER_resolve(t->tree->me->parent->peer, &id); + GNUNET_PEER_resolve(tree_get_predecessor(t->tree), &id); peer_info = peer_info_get (&msg->oid); if (NULL == peer_info) { @@ -3241,7 +3244,7 @@ path_refresh (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc) tunnel_send_multicast (t, &msg->header); t->path_refresh_task = - GNUNET_SCHEDULER_add_delayed (t->tree->refresh, &path_refresh, t); + GNUNET_SCHEDULER_add_delayed (REFRESH_PATH_TIME, &path_refresh, t); return; } @@ -3606,9 +3609,7 @@ handle_local_tunnel_create (void *cls, struct GNUNET_SERVER_Client *client, return; } t->tree = tree_new (myid); - t->tree->refresh = REFRESH_PATH_TIME; - t->tree->root->status = MESH_PEER_READY; - t->tree->me = t->tree->root; + tree_set_me(t->tree, myid); GNUNET_SERVER_receive_done (client, GNUNET_OK); return; diff --git a/src/mesh/mesh.h b/src/mesh/mesh.h index d0648bd3e..fcddb2eb9 100644 --- a/src/mesh/mesh.h +++ b/src/mesh/mesh.h @@ -220,6 +220,11 @@ struct GNUNET_MESH_ConnectPeerByType */ enum MeshPeerState { + /** + * Uninitialized status, should never appear in operation. + */ + MESH_PEER_INVALID, + /** * Peer is the root and owner of the tree */ diff --git a/src/mesh/mesh_tunnel_tree.c b/src/mesh/mesh_tunnel_tree.c index deb702604..332a022c1 100644 --- a/src/mesh/mesh_tunnel_tree.c +++ b/src/mesh/mesh_tunnel_tree.c @@ -30,6 +30,83 @@ #define MESH_TREE_DEBUG GNUNET_YES +/** + * Node of path tree for a tunnel + */ +struct MeshTunnelTreeNode +{ + /** + * Peer this node describes + */ + GNUNET_PEER_Id peer; + + /** + * Parent node in the tree + */ + struct MeshTunnelTreeNode *parent; + + /** + * DLL of siblings + */ + struct MeshTunnelTreeNode *next; + + /** + * DLL of siblings + */ + struct MeshTunnelTreeNode *prev; + + /** + * DLL of children + */ + struct MeshTunnelTreeNode *children_head; + + /** + * DLL of children + */ + struct MeshTunnelTreeNode *children_tail; + + /** + * Status of the peer in the tunnel + */ + enum MeshPeerState status; +}; + + +/** + * Tree to reach all peers in the tunnel + */ +struct MeshTunnelTree +{ + /** + * Root node of peer tree + */ + struct MeshTunnelTreeNode *root; + + /** + * Node that represents our position in the tree (for non local tunnels) + */ + struct MeshTunnelTreeNode *me; + + /** + * DLL of disconneted nodes + */ + struct MeshTunnelTreeNode *disconnected_head; + + /** + * DLL of disconneted nodes + */ + struct MeshTunnelTreeNode *disconnected_tail; + + /** + * Cache of all peers and the first hop to them. + * Indexed by PeerIdentity, contains a pointer to the PeerIdentity + * of 1st hop. + */ + struct GNUNET_CONTAINER_MultiHashMap *first_hops; + +}; + + /** * Create a new path * @@ -91,6 +168,19 @@ path_duplicate (struct MeshPeerPath *path) } +/** + * Recusively update the info about what is the first hop to reach the node + * + * @param tree Tree this nodes belongs to. + * @param parent_id Short ID from node form which to start updating. + * @param hop If known, ID of the first hop. + * If not known, NULL to find out and pass on children. + */ +static void +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 * @@ -112,10 +202,10 @@ path_get_first_hop (struct MeshTunnelTree *t, GNUNET_PEER_Id peer) { struct MeshTunnelTreeNode *n; - n = tree_find_peer(t->root, peer); + n = tree_find_peer(t, peer); if (NULL != t->me && NULL != n) { - tree_update_first_hops(t, n, NULL); + tree_node_update_first_hops(t, n, NULL); r = GNUNET_CONTAINER_multihashmap_get (t->first_hops, &id.hashPubKey); GNUNET_assert (NULL != r); } @@ -214,6 +304,103 @@ tree_node_new(struct MeshTunnelTreeNode *parent, GNUNET_PEER_Id peer) } +/** + * Recursively find the given peer. + * + * @param parent Node where to start looking. + * @param peer Peer to find. + * + * @return Pointer to the node of the peer. NULL if not found. + */ +static struct MeshTunnelTreeNode * +tree_node_find_peer (struct MeshTunnelTreeNode *parent, + GNUNET_PEER_Id peer_id) +{ + struct MeshTunnelTreeNode *n; + struct MeshTunnelTreeNode *r; + + if (parent->peer == peer_id) + return parent; + for (n = parent->children_head; NULL != n; n = n->next) + { + r = tree_node_find_peer (n, peer_id); + if (NULL != r) + return r; + } + return NULL; +} + + +/** + * Recusively update the info about what is the first hop to reach the node + * + * @param tree Tree this nodes belongs to. + * @param parent_id Short ID from node form which to start updating. + * @param hop If known, ID of the first hop. + * If not known, NULL to find out and pass on children. + */ +static void +tree_node_update_first_hops (struct MeshTunnelTree *tree, + struct MeshTunnelTreeNode *parent, + struct GNUNET_PeerIdentity *hop) +{ + struct GNUNET_PeerIdentity pi; + struct GNUNET_PeerIdentity *copy; + struct GNUNET_PeerIdentity id; + struct MeshTunnelTreeNode *n; + +#if MESH_TREE_DEBUG + GNUNET_PEER_resolve(parent->peer, &id); + GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, + "tree: Finding first hop for %s.\n", + GNUNET_i2s (&id)); +#endif + if (NULL == hop) + { + struct MeshTunnelTreeNode *aux; + struct MeshTunnelTreeNode *old; + + aux = old = parent; + 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_i2s (&id)); +#endif + old = aux; + aux = aux->parent; + GNUNET_assert(NULL != aux); + } +#if MESH_TREE_DEBUG + GNUNET_PEER_resolve(old->peer, &id); + GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, + "tree: It's %s!\n", + GNUNET_i2s (&id)); +#endif + hop = π + GNUNET_PEER_resolve(old->peer, hop); + } + GNUNET_PEER_resolve(parent->peer, &id); + copy = GNUNET_CONTAINER_multihashmap_get (tree->first_hops, &id.hashPubKey); + if (NULL == copy) + copy = GNUNET_malloc(sizeof(struct GNUNET_PeerIdentity)); + *copy = *hop; + + (void) GNUNET_CONTAINER_multihashmap_put( + tree->first_hops, + &id.hashPubKey, + copy, + GNUNET_CONTAINER_MULTIHASHMAPOPTION_REPLACE); + + for (n = parent->children_head; NULL != n; n = n->next) + { + tree_node_update_first_hops (tree, n, hop); + } +} + + static void tree_node_debug(struct MeshTunnelTreeNode *n, uint16_t level) { @@ -307,28 +494,102 @@ tree_new (GNUNET_PEER_Id peer) /** - * Recursively find the given peer in the tree. + * Set own identity in the tree * - * @param t Tunnel where to look for the peer. - * @param peer Peer to find + * @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. * - * @return Pointer to the node of the peer. NULL if not found. + * @param tree Tree whose local id we want to now. + * + * @return Short peer id of local peer. */ -struct MeshTunnelTreeNode * -tree_find_peer (struct MeshTunnelTreeNode *parent, GNUNET_PEER_Id peer_id) +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. + * + * @param tree Tree. + * @param peer A short peer id of local peer. + */ +void +tree_set_status (struct MeshTunnelTree *tree, + GNUNET_PEER_Id peer, + enum MeshPeerState status) { struct MeshTunnelTreeNode *n; - struct MeshTunnelTreeNode *r; - if (parent->peer == peer_id) - return parent; - for (n = parent->children_head; NULL != n; n = n->next) - { - r = tree_find_peer (n, peer_id); - if (NULL != r) - return r; - } - return NULL; + n = tree_find_peer(tree, peer); + if (NULL == n) + return; + n->status = status; +} + + +/** + * Get the status of a node. + * + * @param tree Tree whose local id we want to now. + * + * @return Short peer id of local peer. + */ +enum MeshPeerState +tree_get_status (struct MeshTunnelTree *tree, GNUNET_PEER_Id peer) +{ + struct MeshTunnelTreeNode *n; + + n = tree_find_peer(tree, peer); + if (NULL == n) + return MESH_PEER_INVALID; + return n->status; +} + + +/** + * Get the id of the predecessor of the local node. + * + * @param tree Tree whose local id we want to now. + * + * @return Short peer id of local peer. + */ +GNUNET_PEER_Id +tree_get_predecessor (struct MeshTunnelTree *tree) +{ + if (NULL != tree->me && NULL != tree->me->parent) + return tree->me->parent->peer; + else + return (GNUNET_PEER_Id) 0; +} + + +/** + * Find the given peer in the tree. + * + * @param tree Tree where to look for the peer. + * @param peer Peer to find. + * + * @return Pointer to the node of the peer. NULL if not found. + */ +struct MeshTunnelTreeNode * +tree_find_peer (struct MeshTunnelTree *tree, GNUNET_PEER_Id peer_id) +{ + return tree_node_find_peer(tree->root, peer_id); } @@ -342,7 +603,7 @@ tree_find_peer (struct MeshTunnelTreeNode *parent, GNUNET_PEER_Id peer_id) static void tree_mark_peers_disconnected (struct MeshTunnelTree *tree, struct MeshTunnelTreeNode *parent, - MeshNodeDisconnectCB cb, + MeshTreeCallback cb, void *cbcls) { struct GNUNET_PeerIdentity *pi; @@ -370,75 +631,50 @@ tree_mark_peers_disconnected (struct MeshTunnelTree *tree, /** - * Recusively update the info about what is the first hop to reach the node - * - * @param tree Tree this nodes belongs to - * @param parent Node to be start updating - * @param hop If known, ID of the first hop. - * If not known, NULL to find out and pass on children. + * Iterate over all children of the local node. + * + * @param tree Tree to use. Must have "me" set. + * @param cb Callback to call over each child. + * @param cls Closure. */ void -tree_update_first_hops (struct MeshTunnelTree *tree, - struct MeshTunnelTreeNode *parent, - struct GNUNET_PeerIdentity *hop) +tree_iterate_children (struct MeshTunnelTree *tree, + MeshTreeCallback cb, + void *cls) { - struct GNUNET_PeerIdentity pi; - struct GNUNET_PeerIdentity *copy; - struct GNUNET_PeerIdentity id; struct MeshTunnelTreeNode *n; -#if MESH_TREE_DEBUG - GNUNET_PEER_resolve(parent->peer, &id); - GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, - "tree: Finding first hop for %s.\n", - GNUNET_i2s (&id)); -#endif - if (NULL == hop) + if (NULL == tree->me) { - struct MeshTunnelTreeNode *aux; - struct MeshTunnelTreeNode *old; - - aux = old = parent; - 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_i2s (&id)); -#endif - old = aux; - aux = aux->parent; - GNUNET_assert(NULL != aux); - } -#if MESH_TREE_DEBUG - GNUNET_PEER_resolve(old->peer, &id); - GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, - "tree: It's %s!\n", - GNUNET_i2s (&id)); -#endif - hop = π - GNUNET_PEER_resolve(old->peer, hop); + GNUNET_break (0); + return; } - GNUNET_PEER_resolve(parent->peer, &id); - copy = GNUNET_CONTAINER_multihashmap_get (tree->first_hops, &id.hashPubKey); - if (NULL == copy) - copy = GNUNET_malloc(sizeof(struct GNUNET_PeerIdentity)); - *copy = *hop; - - (void) GNUNET_CONTAINER_multihashmap_put( - tree->first_hops, - &id.hashPubKey, - copy, - GNUNET_CONTAINER_MULTIHASHMAPOPTION_REPLACE); - - for (n = parent->children_head; NULL != n; n = n->next) + for (n = tree->me->children_head; NULL != n; n = n->next) { - tree_update_first_hops (tree, n, hop); + cb (cls, n->peer); } } +/** + * Recusively update the info about what is the first hop to reach the node + * + * @param tree Tree this nodes belongs to. + * @param parent_id Short ID from node form which to start updating. + * @param hop If known, ID of the first hop. + * If not known, NULL to find out and pass on children. + */ +void +tree_update_first_hops (struct MeshTunnelTree *tree, + GNUNET_PEER_Id parent_id, + struct GNUNET_PeerIdentity *hop) +{ + tree_node_update_first_hops(tree, + tree_find_peer(tree, parent_id), + hop); +} + + /** * Delete the current path to the peer, including all now unused relays. * The destination peer is NOT destroyed, it is returned in order to either set @@ -455,7 +691,7 @@ tree_update_first_hops (struct MeshTunnelTree *tree, struct MeshTunnelTreeNode * tree_del_path (struct MeshTunnelTree *t, GNUNET_PEER_Id peer_id, - MeshNodeDisconnectCB cb, + MeshTreeCallback cb, void *cbcls) { struct MeshTunnelTreeNode *parent; @@ -483,7 +719,7 @@ tree_del_path (struct MeshTunnelTree *t, return n; } } - n = tree_find_peer (t->root, peer_id); + n = tree_find_peer (t, peer_id); if (NULL == n) return NULL; node = n; @@ -534,7 +770,7 @@ tree_get_path_to_peer(struct MeshTunnelTree *t, GNUNET_PEER_Id peer) struct MeshPeerPath *p; GNUNET_PEER_Id myid = t->me->peer; - n = tree_find_peer(t->me, peer); + n = tree_find_peer(t, peer); if (NULL == n) return NULL; p = path_new(0); @@ -545,7 +781,8 @@ tree_get_path_to_peer(struct MeshTunnelTree *t, GNUNET_PEER_Id peer) GNUNET_array_append(p->peers, p->length, n->peer); GNUNET_PEER_change_rc(n->peer, 1); n = n->parent; - GNUNET_assert(NULL != n); + if (NULL == n) + return NULL; } GNUNET_array_append(p->peers, p->length, myid); GNUNET_PEER_change_rc(myid, 1); @@ -581,7 +818,7 @@ tree_get_path_to_peer(struct MeshTunnelTree *t, GNUNET_PEER_Id peer) int tree_add_path (struct MeshTunnelTree *t, const struct MeshPeerPath *p, - MeshNodeDisconnectCB cb, + MeshTreeCallback cb, void *cbcls) { struct MeshTunnelTreeNode *parent; @@ -683,7 +920,7 @@ tree_add_path (struct MeshTunnelTree *t, GNUNET_CONTAINER_DLL_insert(parent->children_head, parent->children_tail, oldnode); - tree_update_first_hops (t, oldnode, NULL); + tree_node_update_first_hops (t, oldnode, NULL); n = oldnode; } else @@ -711,7 +948,7 @@ tree_add_path (struct MeshTunnelTree *t, #endif GNUNET_PEER_resolve (p->peers[me + 1], &id); tree_update_first_hops(t, - tree_find_peer(t->root, p->peers[p->length - 1]), + p->peers[p->length - 1], &id); } #if MESH_TREE_DEBUG @@ -737,13 +974,13 @@ GNUNET_PEER_Id tree_notify_connection_broken (struct MeshTunnelTree *t, GNUNET_PEER_Id p1, GNUNET_PEER_Id p2, - MeshNodeDisconnectCB cb, + MeshTreeCallback cb, void *cbcls) { struct MeshTunnelTreeNode *n; struct MeshTunnelTreeNode *c; - n = tree_find_peer(t->me, p1); + n = tree_find_peer(t, p1); if (NULL == n) return 0; if (NULL != n->parent && n->parent->peer == p2) @@ -791,22 +1028,26 @@ tree_notify_connection_broken (struct MeshTunnelTree *t, int tree_del_peer (struct MeshTunnelTree *t, GNUNET_PEER_Id peer, - MeshNodeDisconnectCB cb, + MeshTreeCallback cb, void *cbcls) { struct MeshTunnelTreeNode *n; n = tree_del_path(t, peer, cb, cbcls); if (NULL == n) - return GNUNET_SYSERR; + { + GNUNET_break (0); + return GNUNET_YES; + } GNUNET_break_op (NULL == n->children_head); tree_node_destroy(n); if (NULL == t->root->children_head && t->me != t->root) { tree_node_destroy (t->root); t->root = NULL; + return GNUNET_NO; } - return GNUNET_OK; + return GNUNET_YES; } diff --git a/src/mesh/mesh_tunnel_tree.h b/src/mesh/mesh_tunnel_tree.h index 2cb28a28c..e946259da 100644 --- a/src/mesh/mesh_tunnel_tree.h +++ b/src/mesh/mesh_tunnel_tree.h @@ -58,83 +58,13 @@ struct MeshPeerPath /** * Node of path tree for a tunnel */ -struct MeshTunnelTreeNode -{ - /** - * Peer this node describes - */ - GNUNET_PEER_Id peer; - - /** - * Parent node in the tree - */ - struct MeshTunnelTreeNode *parent; - - /** - * DLL of siblings - */ - struct MeshTunnelTreeNode *next; - - /** - * DLL of siblings - */ - struct MeshTunnelTreeNode *prev; - - /** - * DLL of children - */ - struct MeshTunnelTreeNode *children_head; - - /** - * DLL of children - */ - struct MeshTunnelTreeNode *children_tail; - - /** - * Status of the peer in the tunnel - */ - enum MeshPeerState status; -}; +struct MeshTunnelTreeNode; /** * Tree to reach all peers in the tunnel */ -struct MeshTunnelTree -{ - /** - * How often to refresh the path - */ - struct GNUNET_TIME_Relative refresh; - - /** - * Root node of peer tree - */ - struct MeshTunnelTreeNode *root; - - /** - * Node that represents our position in the tree (for non local tunnels) - */ - struct MeshTunnelTreeNode *me; - - /** - * DLL of disconneted nodes - */ - struct MeshTunnelTreeNode *disconnected_head; - - /** - * DLL of disconneted nodes - */ - struct MeshTunnelTreeNode *disconnected_tail; - - /** - * Cache of all peers and the first hop to them. - * Indexed by PeerIdentity, contains a pointer to the PeerIdentity - * of 1st hop. - */ - struct GNUNET_CONTAINER_MultiHashMap *first_hops; - -}; +struct MeshTunnelTree; /******************************************************************************/ @@ -229,14 +159,13 @@ path_destroy (struct MeshPeerPath *p); * @param cls Closure. * @param peer_id short ID of peer that is no longer reachable. */ -typedef void (*MeshNodeDisconnectCB) (void *cls, - GNUNET_PEER_Id peer_id); +typedef void (*MeshTreeCallback) (void *cls, + GNUNET_PEER_Id peer_id); /** * 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 @@ -246,29 +175,96 @@ tree_new (GNUNET_PEER_Id peer); /** - * Recursively find the given peer in the tree. + * 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. + * + * @param tree Tree. + * @param peer A short peer id of local peer. + */ +void +tree_set_status (struct MeshTunnelTree *tree, + GNUNET_PEER_Id peer, + enum MeshPeerState status); + + +/** + * Get the status of a node. + * + * @param tree Tree whose local id we want to now. + * + * @return Short peer id of local peer. + */ +enum MeshPeerState +tree_get_status (struct MeshTunnelTree *tree, GNUNET_PEER_Id peer); + + +/** + * Get the id of the predecessor of the local node. * - * @param parent Parent node where to start looking. - * @param peer Short ID of peer to find. + * @param tree Tree whose local id we want to now. + * + * @return Short peer id of local peer. + */ +GNUNET_PEER_Id +tree_get_predecessor (struct MeshTunnelTree *tree); + + +/** + * Find the given peer in the tree. + * + * @param tree Tree where to look for the peer. + * @param peer Peer to find. * * @return Pointer to the node of the peer. NULL if not found. */ struct MeshTunnelTreeNode * -tree_find_peer (struct MeshTunnelTreeNode *parent, - GNUNET_PEER_Id peer); +tree_find_peer (struct MeshTunnelTree *tree, GNUNET_PEER_Id peer_id); + + +/** + * Iterate over all children of the local node. + * + * @param tree Tree to use. Must have "me" set. + * @param cb Callback to call over each child. + * @param cls Closure. + */ +void +tree_iterate_children (struct MeshTunnelTree *tree, + MeshTreeCallback cb, + void *cls); /** * Recusively update the info about what is the first hop to reach the node * - * @param tree Tree this nodes belongs to - * @param parent Node to be start updating + * @param tree Tree this nodes belongs to. + * @param parent_id Short ID from node form which to start updating. * @param hop If known, ID of the first hop. * If not known, NULL to find out and pass on children. */ void tree_update_first_hops (struct MeshTunnelTree *tree, - struct MeshTunnelTreeNode *parent, + GNUNET_PEER_Id parent_id, struct GNUNET_PeerIdentity *hop); /** @@ -288,7 +284,7 @@ tree_update_first_hops (struct MeshTunnelTree *tree, struct MeshTunnelTreeNode * tree_del_path (struct MeshTunnelTree *t, GNUNET_PEER_Id peer, - MeshNodeDisconnectCB cb, + MeshTreeCallback cb, void *cbcls); @@ -321,7 +317,7 @@ tree_get_path_to_peer(struct MeshTunnelTree *t, int tree_add_path (struct MeshTunnelTree *t, const struct MeshPeerPath *p, - MeshNodeDisconnectCB cb, + MeshTreeCallback cb, void *cbcls); @@ -341,7 +337,7 @@ GNUNET_PEER_Id tree_notify_connection_broken (struct MeshTunnelTree *t, GNUNET_PEER_Id p1, GNUNET_PEER_Id p2, - MeshNodeDisconnectCB cb, + MeshTreeCallback cb, void *cbcls); @@ -356,12 +352,12 @@ tree_notify_connection_broken (struct MeshTunnelTree *t, * @param cb Callback to notify client of disconnected peers. * @param cbcls Closure for cb. * - * @return GNUNET_OK or GNUNET_SYSERR + * @return GNUNET_YES if the tunnel still has nodes */ int tree_del_peer (struct MeshTunnelTree *t, GNUNET_PEER_Id peer, - MeshNodeDisconnectCB cb, + MeshTreeCallback cb, void *cbcls); /** diff --git a/src/mesh/test_mesh_path_api.c b/src/mesh/test_mesh_path_api.c deleted file mode 100644 index 45c4f3c14..000000000 --- a/src/mesh/test_mesh_path_api.c +++ /dev/null @@ -1,314 +0,0 @@ -/* - This file is part of GNUnet. - (C) 2011 Christian Grothoff (and other contributing authors) - - GNUnet is free software; you can redistribute it and/or modify - it under the terms of the GNU General Public License as published - by the Free Software Foundation; either version 3, or (at your - option) any later version. - - GNUnet is distributed in the hope that it will be useful, but - WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU - General Public License for more details. - - You should have received a copy of the GNU General Public License - along with GNUnet; see the file COPYING. If not, write to the - Free Software Foundation, Inc., 59 Temple Place - Suite 330, - Boston, MA 02111-1307, USA. -*/ - -/** - * @file mesh/test_mesh_path.c - * @brief test mesh path: test of path management api - * @author Bartlomiej Polot - */ - -#include "platform.h" -#include "gnunet_common.h" -#include "gnunet_util_lib.h" -#include "gnunet_dht_service.h" -#include "gnunet_mesh_service.h" -#include "mesh.h" -#include "mesh_tunnel_tree.h" - -#define VERBOSE 1 - -int failed; -int cb_call; -struct GNUNET_PeerIdentity* pi[10]; -struct MeshTunnelTree *tree; - -static void -cb (void *cls, GNUNET_PEER_Id peer_id) -{ - GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "test: CB: Disconnected %u\n", peer_id); - if(0 == cb_call) - { - GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "test: and it shouldn't!\n"); - failed++; - } - cb_call--; -} - - -/** - * Check if a node has all expected properties. - * - * @param peer_id Short ID of the peer to test. - * @param status Expected status of the peer. - * @param children Expected number of children of the peer. - * @param first_hop Short ID of the expected first hop towards the peer. - */ -static void -test_assert (GNUNET_PEER_Id peer_id, - enum MeshPeerState status, - unsigned int children, - GNUNET_PEER_Id first_hop) -{ - struct MeshTunnelTreeNode *n; - struct MeshTunnelTreeNode *c; - unsigned int i; - int pre_failed; - - pre_failed = failed; - n = tree_find_peer(tree->root, peer_id); - if (n->peer != peer_id) - { - GNUNET_log(GNUNET_ERROR_TYPE_WARNING, - "Retrieved peer != original (%u, %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, status); - failed++; - } - for (c = n->children_head, i = 0; NULL != c; c = c->next, i++); - if (i != children) - { - GNUNET_log(GNUNET_ERROR_TYPE_WARNING, - "Retrieved peer wrong has number of children! (%u, %u)\n", - i, children); - failed++; - } - if (0 != first_hop && - GNUNET_PEER_search(path_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)), - first_hop); - failed++; - } - if (pre_failed != failed) - { - struct GNUNET_PeerIdentity id; - GNUNET_PEER_resolve (peer_id, &id); - GNUNET_log(GNUNET_ERROR_TYPE_WARNING, - "*** Peer %s (%u) has failed %d checks! (real, expected)\n", - GNUNET_i2s (&id), peer_id, failed - pre_failed); - } -} - - -static void -finish(void) -{ - unsigned int i; - - GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "test: Finishing...\n"); - for (i = 0; i < 10; i++) - { - GNUNET_free(pi[i]); - } - exit(0); -} - -/** - * Convert an integer int to a peer identity - */ -static struct GNUNET_PeerIdentity * -get_pi (uint32_t id) -{ - struct GNUNET_PeerIdentity *pi; - - pi = GNUNET_malloc(sizeof(struct GNUNET_PeerIdentity)); - pi->hashPubKey.bits[0] = id + 1; - return pi; -} - - -int -main (int argc, char *argv[]) -{ - struct MeshTunnelTreeNode *node; - struct MeshTunnelTreeNode *node2; - struct MeshPeerPath *path; - struct MeshPeerPath *path1; - unsigned int i; - - failed = 0; - cb_call = 0; - GNUNET_log_setup ("test_mesh_api_path", -#if VERBOSE - "DEBUG", -#else - "WARNING", -#endif - NULL); - for (i = 0; i < 10; i++) - { - pi[i] = get_pi(i); - GNUNET_break (i + 1 == GNUNET_PEER_intern(pi[i])); - GNUNET_log(GNUNET_ERROR_TYPE_INFO, "Peer %u: %s\n", - i + 1, - GNUNET_h2s(&pi[i]->hashPubKey)); - } - tree = GNUNET_malloc(sizeof(struct MeshTunnelTree)); - tree->first_hops = GNUNET_CONTAINER_multihashmap_create(32); - tree->root = GNUNET_malloc(sizeof(struct MeshTunnelTreeNode)); - tree->root->peer = 1; - tree->me = tree->root; - path = path_new (4); - path->peers[0] = 1; - path->peers[1] = 2; - path->peers[2] = 3; - path->peers[3] = 4; - path->length = 4; - - GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "test: Adding first path: 1 2 3 4\n"); - tree_add_path(tree, path, &cb, NULL); - tree_debug(tree); - path1 = tree_get_path_to_peer(tree, 4); - if (path->length != path1->length || - memcmp(path->peers, path1->peers, path->length) != 0) - { - GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "Retrieved path != original\n"); - failed++; - } - path_destroy(path1); - test_assert (4, MESH_PEER_SEARCHING, 0, 2); - test_assert (3, MESH_PEER_RELAY, 1, 0); - test_assert (2, MESH_PEER_RELAY, 1, 0); - test_assert (1, MESH_PEER_ROOT, 1, 0); - - GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "test: Adding second path: 1 2 3\n"); - path->length--; - tree_add_path(tree, path, &cb, NULL); - tree_debug(tree); - - test_assert (4, MESH_PEER_SEARCHING, 0, 2); - test_assert (3, MESH_PEER_SEARCHING, 1, 2); - 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"); - path->length++; - path->peers[3] = 5; - tree_add_path(tree, path, &cb, NULL); - tree_debug(tree); - - test_assert (5, MESH_PEER_SEARCHING, 0, 2); - test_assert (4, MESH_PEER_SEARCHING, 0, 2); - test_assert (3, MESH_PEER_SEARCHING, 2, 2); - test_assert (2, MESH_PEER_RELAY, 1, 0); - test_assert (1, MESH_PEER_ROOT, 1, 0); - - node = tree_find_peer(tree->root, 5); - GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "test: Deleting third path...\n"); - node->status = MESH_PEER_READY; - cb_call = 1; - node2 = 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) - { - GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "Retrieved peer != original\n"); - failed++; - } - - test_assert (4, MESH_PEER_SEARCHING, 0, 2); - test_assert (3, MESH_PEER_SEARCHING, 1, 2); - test_assert (2, MESH_PEER_RELAY, 1, 0); - test_assert (1, MESH_PEER_ROOT, 1, 0); - - GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "test: Destroying node copy...\n"); - GNUNET_free (node2); - - GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, - "test: Adding new shorter first path...\n"); - path->length = 2; - path->peers[1] = 4; - cb_call = 1; - tree_find_peer(tree->root, 4)->status = MESH_PEER_READY; - tree_add_path(tree, path, &cb, NULL); - tree_debug(tree); - if (cb_call != 0) - { - GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "%u callbacks missed!\n", cb_call); - failed++; - } - - test_assert (4, MESH_PEER_SEARCHING, 0, 4); - test_assert (3, MESH_PEER_SEARCHING, 0, 2); - test_assert (2, MESH_PEER_RELAY, 1, 0); - test_assert (1, MESH_PEER_ROOT, 2, 0); - - GNUNET_free (path->peers); - 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++) - { - pi[i] = get_pi(i); - GNUNET_break (i + 1 == GNUNET_PEER_intern(pi[i])); - GNUNET_log(GNUNET_ERROR_TYPE_INFO, "Peer %u: %s\n", - i + 1, - GNUNET_h2s(&pi[i]->hashPubKey)); - } - tree = GNUNET_malloc(sizeof(struct MeshTunnelTree)); - tree->first_hops = GNUNET_CONTAINER_multihashmap_create(32); - tree->root = GNUNET_malloc(sizeof(struct MeshTunnelTreeNode)); - tree->root->peer = 1; - path = path_new (3); - path->peers[0] = 1; - path->peers[1] = 2; - path->peers[2] = 3; - path->length = 3; - - GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "test: Adding first path: 1 2 3\n"); - tree_add_path(tree, path, &cb, NULL); - tree_debug(tree); - tree->me = tree_find_peer (tree->root, 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); - - GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "test: Adding same path: 1 2 3\n"); - tree_add_path(tree, path, &cb, NULL); - - GNUNET_free (path->peers); - GNUNET_free (path); - tree_destroy (tree); - - if (failed > 0) - { - GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "%u tests failed\n", failed); - return 1; - } - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "test: OK\n"); - finish(); - - return 0; -} -- 2.25.1