From 62cf5f2f6da72d38adac69e239400edd501ef9cb Mon Sep 17 00:00:00 2001 From: Bart Polot Date: Tue, 20 Sep 2011 17:22:58 +0000 Subject: [PATCH] Cleaned and fixed refactoring to improve separation, only 3 structs are now shared --- src/mesh/gnunet-service-mesh.c | 440 ++++++++++++++++++++++++++++++++- src/mesh/mesh.h | 381 ---------------------------- src/mesh/mesh_tunnel_tree.c | 234 +++++------------- src/mesh/mesh_tunnel_tree.h | 176 +++++++++---- src/mesh/test_mesh_path_api.c | 2 +- 5 files changed, 616 insertions(+), 617 deletions(-) diff --git a/src/mesh/gnunet-service-mesh.c b/src/mesh/gnunet-service-mesh.c index 75fa973e0..811553e08 100644 --- a/src/mesh/gnunet-service-mesh.c +++ b/src/mesh/gnunet-service-mesh.c @@ -62,6 +62,298 @@ GNUNET_TIME_UNIT_SECONDS,\ 5) + +/******************************************************************************/ +/************************ DATA STRUCTURES ****************************/ +/******************************************************************************/ + +/** FWD declaration */ +struct MeshPeerInfo; + +/** + * Struct containing all info possibly needed to build a package when called + * back by core. + */ +struct MeshDataDescriptor +{ + /** ID of the tunnel this packet travels in */ + struct MESH_TunnelID *origin; + + /** Ultimate destination of the packet */ + GNUNET_PEER_Id destination; + + /** Number of identical messages sent to different hops (multicast) */ + unsigned int copies; + + /** Size of the data */ + size_t size; + + /** Client that asked for the transmission, if any */ + struct GNUNET_SERVER_Client *client; + + /** Who was is message being sent to */ + struct MeshPeerInfo *peer; + + /** Which handler was used to request the transmission */ + unsigned int handler_n; + + /* Data at the end */ +}; + + +/** + * Struct containing all information regarding a given peer + */ +struct MeshPeerInfo +{ + /** + * ID of the peer + */ + GNUNET_PEER_Id id; + + /** + * Last time we heard from this peer + */ + struct GNUNET_TIME_Absolute last_contact; + + /** + * Number of attempts to reconnect so far + */ + int n_reconnect_attempts; + + /** + * Paths to reach the peer, ordered by ascending hop count + */ + struct MeshPeerPath *path_head; + + /** + * Paths to reach the peer, ordered by ascending hop count + */ + struct MeshPeerPath *path_tail; + + /** + * Handle to stop the DHT search for a path to this peer + */ + struct GNUNET_DHT_GetHandle *dhtget; + + /** + * Handles to stop queued transmissions for this peer + */ + struct GNUNET_CORE_TransmitHandle *core_transmit[CORE_QUEUE_SIZE]; + + /** + * Pointer to info stuctures used as cls for queued transmissions + */ + struct MeshDataDescriptor *infos[CORE_QUEUE_SIZE]; + + /** + * Array of tunnels this peer participates in + * (most probably a small amount, therefore not a hashmap) + * When the path to the peer changes, notify these tunnels to let them + * re-adjust their path trees. + */ + struct MeshTunnel **tunnels; + + /** + * Number of tunnels above + */ + unsigned int ntunnels; +}; + + +/** + * Data scheduled to transmit (to local client or remote peer) + */ +struct MeshQueue +{ + /** + * Double linked list + */ + struct MeshQueue *next; + struct MeshQueue *prev; + + /** + * Target of the data (NULL if target is client) + */ + struct MeshPeerInfo *peer; + + /** + * Client to send the data to (NULL if target is peer) + */ + struct MeshClient *client; + + /** + * Size of the message to transmit + */ + unsigned int size; + + /** + * How old is the data? + */ + struct GNUNET_TIME_Absolute timestamp; + + /** + * Data itself + */ + struct GNUNET_MessageHeader *data; +}; + +/** + * Globally unique tunnel identification (owner + number) + * DO NOT USE OVER THE NETWORK + */ +struct MESH_TunnelID +{ + /** + * Node that owns the tunnel + */ + GNUNET_PEER_Id oid; + + /** + * Tunnel number to differentiate all the tunnels owned by the node oid + * ( tid < GNUNET_MESH_LOCAL_TUNNEL_ID_CLI ) + */ + MESH_TunnelNumber tid; +}; + + +struct MeshClient; /* FWD declaration */ + +/** + * Struct containing all information regarding a tunnel + * For an intermediate node the improtant info used will be: + * - id Tunnel unique identification + * - paths[0] To know where to send it next + * - metainfo: ready, speeds, accounting + */ +struct MeshTunnel +{ + /** + * Tunnel ID + */ + struct MESH_TunnelID id; + + /** + * Local tunnel number ( >= GNUNET_MESH_LOCAL_TUNNEL_ID_CLI or 0 ) + */ + MESH_TunnelNumber local_tid; + + /** + * Last time the tunnel was used + */ + struct GNUNET_TIME_Absolute timestamp; + + /** + * Peers in the tunnel, indexed by PeerIdentity -> (MeshPeerInfo) + */ + struct GNUNET_CONTAINER_MultiHashMap *peers; + + /** + * Number of peers that are connected and potentially ready to receive data + */ + unsigned int peers_ready; + + /** + * Number of peers that have been added to the tunnel + */ + unsigned int peers_total; + + /** + * Client owner of the tunnel, if any + */ + struct MeshClient *client; + + /** + * Messages ready to transmit + */ + struct MeshQueue *queue_head; + struct MeshQueue *queue_tail; + + /** + * Tunnel paths + */ + struct MeshTunnelTree *tree; + + /** + * Task to keep the used paths alive + */ + GNUNET_SCHEDULER_TaskIdentifier path_refresh_task; +}; + + +/** + * Info needed to work with tunnel paths and peers + */ +struct MeshPathInfo +{ + /** + * Tunnel + */ + struct MeshTunnel *t; + + /** + * Destination peer + */ + struct MeshPeerInfo *peer; + + /** + * Path itself + */ + struct MeshPeerPath *path; +}; + + +/** + * Struct containing information about a client of the service + */ +struct MeshClient +{ + /** + * Linked list + */ + struct MeshClient *next; + struct MeshClient *prev; + + /** + * Tunnels that belong to this client, indexed by local id + */ + struct GNUNET_CONTAINER_MultiHashMap *tunnels; + + /** + * Handle to communicate with the client + */ + struct GNUNET_SERVER_Client *handle; + + /** + * Applications that this client has claimed to provide + */ + struct GNUNET_CONTAINER_MultiHashMap *apps; + + /** + * Messages that this client has declared interest in + */ + struct GNUNET_CONTAINER_MultiHashMap *types; + + /** + * Used to search peers offering a service + */ + struct GNUNET_DHT_GetHandle *dht_get_type; + +#if MESH_DEBUG + /** + * ID of the client, for debug messages + */ + unsigned int id; +#endif + +}; + + + +/******************************************************************************/ +/************************ DEBUG FUNCTIONS ****************************/ +/******************************************************************************/ + #if MESH_DEBUG /** * GNUNET_SCHEDULER_Task for printing a message after some operation is done @@ -199,7 +491,7 @@ iterate_collect_neighbors (void *cls, const GNUNET_HashCode * key, void *value) { return GNUNET_YES; } - id = path_get_first_hop (neighbors->t, peer_info); + id = path_get_first_hop (neighbors->t->tree, peer_info->id); peer_id = GNUNET_PEER_search(id); for (i = 0; i < neighbors->path->length; i++) { @@ -442,6 +734,54 @@ path_remove_from_peer (struct MeshPeerInfo *peer, GNUNET_PEER_Id p1, } +/** + * Add the path to the peer and update the path used to reach it in case this + * is the shortest. + * + * @param peer_info Destination peer to add the path to. + * @param path New path to add. Last peer must be the peer in arg 1. + * Path will be either used of freed if already known. + * + * TODO: trim the part from origin to us? Add it as path to origin? + */ +void +path_add_to_peer (struct MeshPeerInfo *peer_info, struct MeshPeerPath *path) +{ + struct MeshPeerPath *aux; + unsigned int l; + unsigned int l2; + + if (NULL == peer_info || NULL == path) + { + GNUNET_break (0); + return; + } + + l = path_get_length (path); + + for (aux = peer_info->path_head; aux != NULL; aux = aux->next) + { + l2 = path_get_length (aux); + if (l2 > l) + { + GNUNET_CONTAINER_DLL_insert_before (peer_info->path_head, + peer_info->path_tail, aux, path); + } + else + { + if (l2 == l && memcmp(path->peers, aux->peers, l) == 0) + { + path_destroy(path); + return; + } + } + } + GNUNET_CONTAINER_DLL_insert_tail (peer_info->path_head, peer_info->path_tail, + path); + return; +} + + /** * Add the path to the origin peer and update the path used to reach it in case * this is the shortest. @@ -530,6 +870,41 @@ path_build_from_dht (const struct GNUNET_PeerIdentity *const *get_path, } +/** + * Send keepalive packets for a peer + * + * @param cls unused + * @param tc unused + * + * FIXME path + */ +void +path_refresh (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc) +{ + struct MeshTunnel *t = cls; + +// struct GNUNET_PeerIdentity id; + + if (tc->reason == GNUNET_SCHEDULER_REASON_SHUTDOWN) + { + return; + } + /* FIXME implement multicast keepalive. Just an empty multicast packet? */ +// GNUNET_PEER_resolve (path_get_first_hop (path->t, path->peer)->id, &id); +// GNUNET_CORE_notify_transmit_ready (core_handle, 0, 0, +// GNUNET_TIME_UNIT_FOREVER_REL, &id, +// sizeof (struct GNUNET_MESH_ManipulatePath) +// + +// (path->path->length * +// sizeof (struct GNUNET_PeerIdentity)), +// &send_core_create_path, +// t); + t->path_refresh_task = + GNUNET_SCHEDULER_add_delayed (t->tree->refresh, &path_refresh, t); + return; +} + + /** * Check if client has registered with the service and has not disconnected * @@ -628,6 +1003,51 @@ tunnel_get (struct GNUNET_PeerIdentity *oid, MESH_TunnelNumber tid) } +void +notify_peer_disconnected (struct MeshTunnelTreeNode *n) +{ + +} + + +/** + * Add a peer to a tunnel, accomodating paths accordingly and initializing all + * needed rescources. + * + * @param t Tunnel we want to add a new peer to + * @param peer PeerInfo of the peer being added + * + */ +void +tunnel_add_peer (struct MeshTunnel *t, struct MeshPeerInfo *peer) +{ + struct MeshPeerPath *p; + struct MeshPeerPath *best_p; + unsigned int best_cost; + unsigned int cost; + + GNUNET_array_append (peer->tunnels, peer->ntunnels, t); + if (NULL == (p = peer->path_head)) + return; + + best_p = p; + best_cost = UINT_MAX; + while (NULL != p) + { + if ((cost = path_get_cost (t->tree, p)) < best_cost) + { + best_cost = cost; + best_p = p; + } + p = p->next; + } + tunnel_add_path (t->tree, best_p, ¬ify_peer_disconnected); + if (GNUNET_SCHEDULER_NO_TASK == t->path_refresh_task) + t->path_refresh_task = + GNUNET_SCHEDULER_add_delayed (t->tree->refresh, &path_refresh, t); +} + + /** * Notify a tunnel that a connection has broken that affects at least * some of its peers. @@ -656,7 +1076,7 @@ tunnel_notify_connection_broken (struct MeshTunnel *t, * @return GNUNET_OK on success */ static void -tunnel_destroy_tree_node (struct MeshTunnelPathNode *n) +tunnel_destroy_tree_node (struct MeshTunnelTreeNode *n) { unsigned int i; @@ -784,7 +1204,7 @@ send_core_create_path (void *cls, size_t size, void *buf) GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "MESH: Retransmitting create path\n"); GNUNET_CORE_notify_transmit_ready (core_handle, 0, 0, GNUNET_TIME_UNIT_FOREVER_REL, - path_get_first_hop (t, peer), + path_get_first_hop (t->tree, peer->id), size_needed, &send_core_create_path, info); return 0; @@ -1310,7 +1730,8 @@ handle_mesh_data_unicast (void *cls, const struct GNUNET_PeerIdentity *peer, memcpy (msg, message, size); GNUNET_CORE_notify_transmit_ready (core_handle, 0, 0, GNUNET_TIME_UNIT_FOREVER_REL, - path_get_first_hop (t, pi), size, + path_get_first_hop (t->tree, pi->id), + size, &send_core_data_raw, msg); return GNUNET_OK; } @@ -1537,7 +1958,8 @@ handle_mesh_path_ack (void *cls, const struct GNUNET_PeerIdentity *peer, memcpy (msg, message, sizeof (struct GNUNET_MESH_PathACK)); GNUNET_CORE_notify_transmit_ready (core_handle, 0, 0, GNUNET_TIME_UNIT_FOREVER_REL, - path_get_first_hop (t, peer_info), + path_get_first_hop (t->tree, + peer_info->id), sizeof (struct GNUNET_MESH_PathACK), &send_core_data_raw, msg); return GNUNET_OK; @@ -1755,7 +2177,7 @@ dht_get_type_handler (void *cls, struct GNUNET_TIME_Absolute exp, p = path_build_from_dht (get_path, put_path); path_add_to_peer (peer_info, p); tunnel_add_peer(t, peer_info); - p = tunnel_get_path_to_peer(t, peer_info); + p = tunnel_get_path_to_peer(t->tree, peer_info->id); #if MESH_DEBUG GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "MESH: new route for tunnel 0x%x found, has %u hops\n", @@ -2045,11 +2467,11 @@ 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 MeshTunnelPath)); + t->tree = GNUNET_malloc (sizeof(struct MeshTunnelTree)); t->tree->first_hops = GNUNET_CONTAINER_multihashmap_create(32); t->tree->t = t; t->tree->refresh = REFRESH_PATH_TIME; - t->tree->root = GNUNET_malloc(sizeof(struct MeshTunnelPathNode)); + 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; @@ -2428,7 +2850,7 @@ handle_local_unicast (void *cls, struct GNUNET_SERVER_Client *client, info->client = client; GNUNET_CORE_notify_transmit_ready (core_handle, 0, 0, GNUNET_TIME_UNIT_FOREVER_REL, - path_get_first_hop (t, pi), + path_get_first_hop (t->tree, pi->id), /* FIXME re-check types */ data_size + sizeof (struct GNUNET_MESH_Unicast), diff --git a/src/mesh/mesh.h b/src/mesh/mesh.h index 2a7133a55..e816e5ddc 100644 --- a/src/mesh/mesh.h +++ b/src/mesh/mesh.h @@ -246,386 +246,5 @@ enum MeshPeerState }; -/******************************************************************************/ -/************************ DATA STRUCTURES ****************************/ -/******************************************************************************/ - -/** - * Information regarding a possible path to reach a single peer - */ -struct MeshPeerPath -{ - - /** - * Linked list - */ - struct MeshPeerPath *next; - struct MeshPeerPath *prev; - - /** - * List of all the peers that form the path from origin to target. - */ - GNUNET_PEER_Id *peers; - - /** - * Number of peers (hops) in the path - */ - unsigned int length; - -}; - - -/** - * Node of path tree for a tunnel - */ -struct MeshTunnelPathNode -{ - /** - * Tunnel this node belongs to (and therefore tree) - */ - struct MeshTunnel *t; - - /** - * Peer this node describes - */ - GNUNET_PEER_Id peer; - - /** - * Parent node in the tree - */ - struct MeshTunnelPathNode *parent; - - /** - * Array of children - */ - struct MeshTunnelPathNode *children; - - /** - * Number of children - */ - unsigned int nchildren; - - /** - * Status of the peer in the tunnel - */ - enum MeshPeerState status; -}; - - -/** - * Tree to reach all peers in the tunnel - */ -struct MeshTunnelPath -{ - /** - * How often to refresh the path - */ - struct GNUNET_TIME_Relative refresh; - - /** - * Tunnel this path belongs to - */ - struct MeshTunnel *t; - - /** - * Root node of peer tree - */ - struct MeshTunnelPathNode *root; - - /** - * Node that represents our position in the tree (for non local tunnels) - */ - struct MeshTunnelPathNode *me; - - /** - * Cache of all peers and the first hop to them. - * Indexed by Peer_Identity, contains a pointer to the PeerIdentity - * of 1st hop. - */ - struct GNUNET_CONTAINER_MultiHashMap *first_hops; - -}; - - -/** FWD declaration */ -struct MeshPeerInfo; - -/** - * Struct containing all info possibly needed to build a package when called - * back by core. - */ -struct MeshDataDescriptor -{ - /** ID of the tunnel this packet travels in */ - struct MESH_TunnelID *origin; - - /** Ultimate destination of the packet */ - GNUNET_PEER_Id destination; - - /** Number of identical messages sent to different hops (multicast) */ - unsigned int copies; - - /** Size of the data */ - size_t size; - - /** Client that asked for the transmission, if any */ - struct GNUNET_SERVER_Client *client; - - /** Who was is message being sent to */ - struct MeshPeerInfo *peer; - - /** Which handler was used to request the transmission */ - unsigned int handler_n; - - /* Data at the end */ -}; - - -/** - * Struct containing all information regarding a given peer - */ -struct MeshPeerInfo -{ - /** - * ID of the peer - */ - GNUNET_PEER_Id id; - - /** - * Last time we heard from this peer - */ - struct GNUNET_TIME_Absolute last_contact; - - /** - * Number of attempts to reconnect so far - */ - int n_reconnect_attempts; - - /** - * Paths to reach the peer, ordered by ascending hop count - */ - struct MeshPeerPath *path_head; - - /** - * Paths to reach the peer, ordered by ascending hop count - */ - struct MeshPeerPath *path_tail; - - /** - * Handle to stop the DHT search for a path to this peer - */ - struct GNUNET_DHT_GetHandle *dhtget; - - /** - * Handles to stop queued transmissions for this peer - */ - struct GNUNET_CORE_TransmitHandle *core_transmit[CORE_QUEUE_SIZE]; - - /** - * Pointer to info stuctures used as cls for queued transmissions - */ - struct MeshDataDescriptor *infos[CORE_QUEUE_SIZE]; - - /** - * Array of tunnels this peer participates in - * (most probably a small amount, therefore not a hashmap) - * When the path to the peer changes, notify these tunnels to let them - * re-adjust their path trees. - */ - struct MeshTunnel **tunnels; - - /** - * Number of tunnels above - */ - unsigned int ntunnels; -}; - - -/** - * Data scheduled to transmit (to local client or remote peer) - */ -struct MeshQueue -{ - /** - * Double linked list - */ - struct MeshQueue *next; - struct MeshQueue *prev; - - /** - * Target of the data (NULL if target is client) - */ - struct MeshPeerInfo *peer; - - /** - * Client to send the data to (NULL if target is peer) - */ - struct MeshClient *client; - - /** - * Size of the message to transmit - */ - unsigned int size; - - /** - * How old is the data? - */ - struct GNUNET_TIME_Absolute timestamp; - - /** - * Data itself - */ - struct GNUNET_MessageHeader *data; -}; - -/** - * Globally unique tunnel identification (owner + number) - * DO NOT USE OVER THE NETWORK - */ -struct MESH_TunnelID -{ - /** - * Node that owns the tunnel - */ - GNUNET_PEER_Id oid; - - /** - * Tunnel number to differentiate all the tunnels owned by the node oid - * ( tid < GNUNET_MESH_LOCAL_TUNNEL_ID_CLI ) - */ - MESH_TunnelNumber tid; -}; - - -struct MeshClient; /* FWD declaration */ - -/** - * Struct containing all information regarding a tunnel - * For an intermediate node the improtant info used will be: - * - id Tunnel unique identification - * - paths[0] To know where to send it next - * - metainfo: ready, speeds, accounting - */ -struct MeshTunnel -{ - /** - * Tunnel ID - */ - struct MESH_TunnelID id; - - /** - * Local tunnel number ( >= GNUNET_MESH_LOCAL_TUNNEL_ID_CLI or 0 ) - */ - MESH_TunnelNumber local_tid; - - /** - * Last time the tunnel was used - */ - struct GNUNET_TIME_Absolute timestamp; - - /** - * Peers in the tunnel, indexed by PeerIdentity -> (MeshPeerInfo) - */ - struct GNUNET_CONTAINER_MultiHashMap *peers; - - /** - * Number of peers that are connected and potentially ready to receive data - */ - unsigned int peers_ready; - - /** - * Number of peers that have been added to the tunnel - */ - unsigned int peers_total; - - /** - * Client owner of the tunnel, if any - */ - struct MeshClient *client; - - /** - * Messages ready to transmit - */ - struct MeshQueue *queue_head; - struct MeshQueue *queue_tail; - - /** - * Tunnel paths - */ - struct MeshTunnelPath *tree; - - /** - * Task to keep the used paths alive - */ - GNUNET_SCHEDULER_TaskIdentifier path_refresh_task; -}; - - -/** - * Info needed to work with tunnel paths and peers - */ -struct MeshPathInfo -{ - /** - * Tunnel - */ - struct MeshTunnel *t; - - /** - * Destination peer - */ - struct MeshPeerInfo *peer; - - /** - * Path itself - */ - struct MeshPeerPath *path; -}; - - -/** - * Struct containing information about a client of the service - */ -struct MeshClient -{ - /** - * Linked list - */ - struct MeshClient *next; - struct MeshClient *prev; - - /** - * Tunnels that belong to this client, indexed by local id - */ - struct GNUNET_CONTAINER_MultiHashMap *tunnels; - - /** - * Handle to communicate with the client - */ - struct GNUNET_SERVER_Client *handle; - - /** - * Applications that this client has claimed to provide - */ - struct GNUNET_CONTAINER_MultiHashMap *apps; - - /** - * Messages that this client has declared interest in - */ - struct GNUNET_CONTAINER_MultiHashMap *types; - - /** - * Used to search peers offering a service - */ - struct GNUNET_DHT_GetHandle *dht_get_type; - -#if MESH_DEBUG - /** - * ID of the client, for debug messages - */ - unsigned int id; -#endif - -}; #endif diff --git a/src/mesh/mesh_tunnel_tree.c b/src/mesh/mesh_tunnel_tree.c index 10298ca5a..e838cefc1 100644 --- a/src/mesh/mesh_tunnel_tree.c +++ b/src/mesh/mesh_tunnel_tree.c @@ -28,10 +28,6 @@ #include "mesh_tunnel_tree.h" -extern GNUNET_PEER_Id myid; -extern struct GNUNET_PeerIdentity my_full_id; - - /** * Invert the path * @@ -72,19 +68,19 @@ path_destroy (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 MeshTunnel *t, struct MeshPeerInfo *peer) +path_get_first_hop (struct MeshTunnelTree *t, GNUNET_PEER_Id peer) { struct GNUNET_PeerIdentity id; - GNUNET_PEER_resolve (peer->id, &id); - return GNUNET_CONTAINER_multihashmap_get (t->tree->first_hops, + GNUNET_PEER_resolve (peer, &id); + return GNUNET_CONTAINER_multihashmap_get (t->first_hops, &id.hashPubKey); } @@ -109,7 +105,7 @@ path_get_length (struct MeshPeerPath *path) /** * Get the cost of the path relative to the already built tunnel tree * - * @param t The tunnel to which compare + * @param t The tunnel tree to which compare * @param path The individual path to reach a peer * * @return Number of hops to reach destination, UINT_MAX in case the peer is not @@ -118,96 +114,12 @@ path_get_length (struct MeshPeerPath *path) * TODO: remove dummy implementation, look into the tunnel tree */ unsigned int -path_get_cost (struct MeshTunnel *t, struct MeshPeerPath *path) +path_get_cost (struct MeshTunnelTree *t, struct MeshPeerPath *path) { return path_get_length (path); } -/** - * Add the path to the peer and update the path used to reach it in case this - * is the shortest. - * - * @param peer_info Destination peer to add the path to. - * @param path New path to add. Last peer must be the peer in arg 1. - * Path will be either used of freed if already known. - * - * TODO: trim the part from origin to us? Add it as path to origin? - */ -void -path_add_to_peer (struct MeshPeerInfo *peer_info, struct MeshPeerPath *path) -{ - struct MeshPeerPath *aux; - unsigned int l; - unsigned int l2; - - if (NULL == peer_info || NULL == path) - { - GNUNET_break (0); - return; - } - - l = path_get_length (path); - - for (aux = peer_info->path_head; aux != NULL; aux = aux->next) - { - l2 = path_get_length (aux); - if (l2 > l) - { - GNUNET_CONTAINER_DLL_insert_before (peer_info->path_head, - peer_info->path_tail, aux, path); - } - else - { - if (l2 == l && memcmp(path->peers, aux->peers, l) == 0) - { - path_destroy(path); - return; - } - } - } - GNUNET_CONTAINER_DLL_insert_tail (peer_info->path_head, peer_info->path_tail, - path); - return; -} - - -/** - * Send keepalive packets for a peer - * - * @param cls unused - * @param tc unused - * - * FIXME path - */ -void -path_refresh (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc) -{ - struct MeshTunnel *t = cls; - -// struct GNUNET_PeerIdentity id; - - if (tc->reason == GNUNET_SCHEDULER_REASON_SHUTDOWN) - { - return; - } - /* FIXME implement multicast keepalive. Just an empty multicast packet? */ -// GNUNET_PEER_resolve (path_get_first_hop (path->t, path->peer)->id, &id); -// GNUNET_CORE_notify_transmit_ready (core_handle, 0, 0, -// GNUNET_TIME_UNIT_FOREVER_REL, &id, -// sizeof (struct GNUNET_MESH_ManipulatePath) -// + -// (path->path->length * -// sizeof (struct GNUNET_PeerIdentity)), -// &send_core_create_path, -// t); - t->path_refresh_task = - GNUNET_SCHEDULER_add_delayed (t->tree->refresh, &path_refresh, t); - return; -} - - - /** * Recursively find the given peer in the tree. * @@ -216,10 +128,10 @@ path_refresh (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc) * * @return Pointer to the node of the peer. NULL if not found. */ -struct MeshTunnelPathNode * -tunnel_find_peer (struct MeshTunnelPathNode *root, GNUNET_PEER_Id peer_id) +struct MeshTunnelTreeNode * +tunnel_find_peer (struct MeshTunnelTreeNode *root, GNUNET_PEER_Id peer_id) { - struct MeshTunnelPathNode *n; + struct MeshTunnelTreeNode *n; unsigned int i; if (root->peer == peer_id) @@ -238,30 +150,34 @@ tunnel_find_peer (struct MeshTunnelPathNode *root, GNUNET_PEER_Id peer_id) * Recusively mark peer and children as disconnected, notify client * * @param parent Node to be clean, potentially with children - * @param nc Notification context to use to alert the client + * @param cb Callback to use to notify about disconnected peers. */ void -tunnel_mark_peers_disconnected (struct MeshTunnelPathNode *parent, - struct GNUNET_SERVER_NotificationContext *nc) +tunnel_mark_peers_disconnected (struct MeshTunnelTreeNode *parent, + MeshNodeDisconnectCB cb) { - struct GNUNET_MESH_PeerControl msg; unsigned int i; + if (MESH_PEER_READY == parent->status) + { + cb (parent); + } parent->status = MESH_PEER_RECONNECTING; for (i = 0; i < parent->nchildren; i++) { - tunnel_mark_peers_disconnected (&parent->children[i], nc); + tunnel_mark_peers_disconnected (&parent->children[i], cb); } - if (NULL == parent->t->client) - return; - msg.header.size = htons (sizeof (msg)); - msg.header.type = htons (GNUNET_MESSAGE_TYPE_MESH_LOCAL_PEER_DEL); - msg.tunnel_id = htonl (parent->t->local_tid); - GNUNET_PEER_resolve (parent->peer, &msg.peer); - if (NULL == nc) - return; - GNUNET_SERVER_notification_context_unicast (nc, parent->t->client->handle, - &msg.header, GNUNET_NO); +// struct GNUNET_MESH_PeerControl msg; +// if (NULL == parent->t->client) +// return; +// msg.header.size = htons (sizeof (msg)); +// msg.header.type = htons (GNUNET_MESSAGE_TYPE_MESH_LOCAL_PEER_DEL); +// msg.tunnel_id = htonl (parent->t->local_tid); +// GNUNET_PEER_resolve (parent->peer, &msg.peer); +// if (NULL == nc) +// return; +// GNUNET_SERVER_notification_context_unicast (nc, parent->t->client->handle, +// &msg.header, GNUNET_NO); } @@ -272,23 +188,23 @@ tunnel_mark_peers_disconnected (struct MeshTunnelPathNode *parent, * 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 nc Notification context to alert the client of disconnected peers. + * @param cb Callback to use to notify about disconnected peers. * * @return pointer to the pathless node, NULL on error */ -struct MeshTunnelPathNode * -tunnel_del_path (struct MeshTunnel *t, GNUNET_PEER_Id peer_id, - struct GNUNET_SERVER_NotificationContext *nc) +struct MeshTunnelTreeNode * +tunnel_del_path (struct MeshTunnelTree *t, GNUNET_PEER_Id peer_id, + MeshNodeDisconnectCB cb) { - struct MeshTunnelPathNode *parent; - struct MeshTunnelPathNode *node; - struct MeshTunnelPathNode *n; + struct MeshTunnelTreeNode *parent; + struct MeshTunnelTreeNode *node; + struct MeshTunnelTreeNode *n; - if (peer_id == t->tree->root->peer) + if (peer_id == t->root->peer) return NULL; - node = n = tunnel_find_peer (t->tree->me, peer_id); + node = n = tunnel_find_peer (t->me, peer_id); if (NULL == n) return NULL; parent = n->parent; @@ -306,7 +222,7 @@ tunnel_del_path (struct MeshTunnel *t, GNUNET_PEER_Id peer_id, parent->nchildren--; parent->children = GNUNET_realloc (parent->children, parent->nchildren); - tunnel_mark_peers_disconnected (node, nc); + tunnel_mark_peers_disconnected (node, cb); return node; } @@ -323,13 +239,13 @@ tunnel_del_path (struct MeshTunnel *t, GNUNET_PEER_Id peer_id, * Path must be destroyed afterwards. */ struct MeshPeerPath * -tunnel_get_path_to_peer(struct MeshTunnel *t, struct MeshPeerInfo *peer_info) +tunnel_get_path_to_peer(struct MeshTunnelTree *t, GNUNET_PEER_Id peer) { - struct MeshTunnelPathNode *n; + struct MeshTunnelTreeNode *n; struct MeshPeerPath *p; - GNUNET_PEER_Id myid = t->tree->me->peer; + GNUNET_PEER_Id myid = t->me->peer; - n = tunnel_find_peer(t->tree->me, peer_info->id); + n = tunnel_find_peer(t->me, peer); p = GNUNET_malloc(sizeof(struct MeshPeerPath)); /* Building the path (inverted!) */ @@ -354,8 +270,7 @@ tunnel_get_path_to_peer(struct MeshTunnel *t, struct MeshPeerInfo *peer_info) * * @param t Tunnel where to add the new path. * @param p Path to be integrated. - * @param nc Notification context to alert clients of peers - * temporarily disconnected + * @param cb Callback to use to notify about peers temporarily disconnecting * * @return GNUNET_OK in case of success. * GNUNET_SYSERR in case of error. @@ -365,20 +280,21 @@ tunnel_get_path_to_peer(struct MeshTunnel *t, struct MeshPeerInfo *peer_info) * - do not disconnect peers until new path is created & connected */ int -tunnel_add_path (struct MeshTunnel *t, const struct MeshPeerPath *p) +tunnel_add_path (struct MeshTunnelTree *t, const struct MeshPeerPath *p, + MeshNodeDisconnectCB cb) { - struct MeshTunnelPathNode *parent; - struct MeshTunnelPathNode *oldnode; - struct MeshTunnelPathNode *n; + struct MeshTunnelTreeNode *parent; + struct MeshTunnelTreeNode *oldnode; + struct MeshTunnelTreeNode *n; struct GNUNET_PeerIdentity id; struct GNUNET_PeerIdentity *hop; - GNUNET_PEER_Id myid = t->tree->me->peer; + GNUNET_PEER_Id myid = t->me->peer; int me; unsigned int i; unsigned int j; GNUNET_assert(0 != p->length); - n = t->tree->root; + n = t->root; if (n->peer != p->peers[0]) { GNUNET_break (0); @@ -386,7 +302,7 @@ tunnel_add_path (struct MeshTunnel *t, const struct MeshPeerPath *p) } if (1 == p->length) return GNUNET_OK; - oldnode = tunnel_del_path (t, p->peers[p->length - 1], NULL); + oldnode = tunnel_del_path (t, p->peers[p->length - 1], cb); /* Look for the first node that is not already present in the tree * * Assuming that the tree is somewhat balanced, O(log n * log N). @@ -423,17 +339,17 @@ tunnel_add_path (struct MeshTunnel *t, const struct MeshPeerPath *p) parent->nchildren++; parent->children = GNUNET_realloc (parent->children, parent->nchildren * - sizeof(struct MeshTunnelPathNode)); + sizeof(struct MeshTunnelTreeNode)); n = &parent->children[parent->nchildren - 1]; if (i == p->length - 1 && NULL != oldnode) { /* Assignation and free can be misleading, using explicit mempcy */ - memcpy (n, oldnode, sizeof (struct MeshTunnelPathNode)); + memcpy (n, oldnode, sizeof (struct MeshTunnelTreeNode)); GNUNET_free (oldnode); } else { - n->t = t; + n->t = t->t; n->status = MESH_PEER_RELAY; n->peer = p->peers[i]; } @@ -448,47 +364,9 @@ tunnel_add_path (struct MeshTunnel *t, const struct MeshPeerPath *p) GNUNET_PEER_resolve (p->peers[p->length - 1], &id); hop = GNUNET_malloc(sizeof(struct GNUNET_PeerIdentity)); GNUNET_PEER_resolve (p->peers[me + 1], hop); - GNUNET_CONTAINER_multihashmap_put (t->tree->first_hops, &id.hashPubKey, + GNUNET_CONTAINER_multihashmap_put (t->first_hops, &id.hashPubKey, hop, GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST); } return GNUNET_OK; } - - -/** - * Add a peer to a tunnel, accomodating paths accordingly and initializing all - * needed rescources. - * - * @param t Tunnel we want to add a new peer to - * @param peer PeerInfo of the peer being added - * - */ -void -tunnel_add_peer (struct MeshTunnel *t, struct MeshPeerInfo *peer) -{ - struct MeshPeerPath *p; - struct MeshPeerPath *best_p; - unsigned int best_cost; - unsigned int cost; - - GNUNET_array_append (peer->tunnels, peer->ntunnels, t); - if (NULL == (p = peer->path_head)) - return; - - best_p = p; - best_cost = UINT_MAX; - while (NULL != p) - { - if ((cost = path_get_cost (t, p)) < best_cost) - { - best_cost = cost; - best_p = p; - } - p = p->next; - } - tunnel_add_path (t, best_p); - if (GNUNET_SCHEDULER_NO_TASK == t->path_refresh_task) - t->path_refresh_task = - GNUNET_SCHEDULER_add_delayed (t->tree->refresh, &path_refresh, t); -} diff --git a/src/mesh/mesh_tunnel_tree.h b/src/mesh/mesh_tunnel_tree.h index be4509c9c..fddc9b46d 100644 --- a/src/mesh/mesh_tunnel_tree.h +++ b/src/mesh/mesh_tunnel_tree.h @@ -26,6 +26,119 @@ #include "mesh.h" +/******************************************************************************/ +/************************ DATA STRUCTURES ****************************/ +/******************************************************************************/ + +/** + * Information regarding a possible path to reach a single peer + */ +struct MeshPeerPath +{ + + /** + * Linked list + */ + struct MeshPeerPath *next; + struct MeshPeerPath *prev; + + /** + * List of all the peers that form the path from origin to target. + */ + GNUNET_PEER_Id *peers; + + /** + * Number of peers (hops) in the path + */ + unsigned int length; + +}; + + +/** + * Node of path tree for a tunnel + */ +struct MeshTunnelTreeNode +{ + /** + * Tunnel this node belongs to (and therefore tree) + */ + struct MeshTunnel *t; + + /** + * Peer this node describes + */ + GNUNET_PEER_Id peer; + + /** + * Parent node in the tree + */ + struct MeshTunnelTreeNode *parent; + + /** + * Array of children + */ + struct MeshTunnelTreeNode *children; + + /** + * Number of children + */ + unsigned int nchildren; + + /** + * Status of the peer in the tunnel + */ + enum MeshPeerState status; +}; + + +/** + * Tree to reach all peers in the tunnel + */ +struct MeshTunnelTree +{ + /** + * How often to refresh the path + */ + struct GNUNET_TIME_Relative refresh; + + /** + * Tunnel this path belongs to + */ + struct MeshTunnel *t; + + /** + * Root node of peer tree + */ + struct MeshTunnelTreeNode *root; + + /** + * Node that represents our position in the tree (for non local tunnels) + */ + struct MeshTunnelTreeNode *me; + + /** + * Cache of all peers and the first hop to them. + * Indexed by Peer_Identity, contains a pointer to the PeerIdentity + * of 1st hop. + */ + struct GNUNET_CONTAINER_MultiHashMap *first_hops; + +}; + + +/******************************************************************************/ +/************************* FUNCTIONS *****************************/ +/******************************************************************************/ + + +/** + * 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); + /** * Invert the path @@ -58,7 +171,7 @@ path_destroy (struct MeshPeerPath *p); * NULL on error */ struct GNUNET_PeerIdentity * -path_get_first_hop (struct MeshTunnel *t, struct MeshPeerInfo *peer); +path_get_first_hop (struct MeshTunnelTree *t, GNUNET_PEER_Id peer); /** @@ -83,28 +196,7 @@ path_get_length (struct MeshPeerPath *path); * in the path */ unsigned int -path_get_cost (struct MeshTunnel *t, struct MeshPeerPath *path); - -/** - * Add the path to the peer and update the path used to reach it in case this - * is the shortest. - * - * @param peer_info Destination peer to add the path to. - * @param path New path to add. Last peer must be the peer in arg 1. - * Path will be either used of freed if already known. - */ -void -path_add_to_peer (struct MeshPeerInfo *peer_info, struct MeshPeerPath *path); - - -/** - * Send keepalive packets for a peer - * - * @param cls unused - * @param tc unused - */ -void -path_refresh (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc); +path_get_cost (struct MeshTunnelTree *t, struct MeshPeerPath *path); /** @@ -115,19 +207,19 @@ path_refresh (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc); * * @return Pointer to the node of the peer. NULL if not found. */ -struct MeshTunnelPathNode * -tunnel_find_peer (struct MeshTunnelPathNode *root, GNUNET_PEER_Id peer_id); +struct MeshTunnelTreeNode * +tunnel_find_peer (struct MeshTunnelTreeNode *root, GNUNET_PEER_Id peer_id); /** * Recusively mark peer and children as disconnected, notify client * * @param parent Node to be clean, potentially with children - * @param nc Notification context to use to alert the client + * @param cb Callback to use to notify about disconnected peers */ void -tunnel_mark_peers_disconnected (struct MeshTunnelPathNode *parent, - struct GNUNET_SERVER_NotificationContext *nc); +tunnel_mark_peers_disconnected (struct MeshTunnelTreeNode *parent, + MeshNodeDisconnectCB cb); /** @@ -137,13 +229,13 @@ tunnel_mark_peers_disconnected (struct MeshTunnelPathNode *parent, * * @param t Tunnel where to delete the path from. * @param peer Destination peer whose path we want to remove. - * @param nc Notification context to alert the client of disconnected peers. + * @param cb Callback to use to notify about disconnected peers * * @return pointer to the pathless node, NULL on error */ -struct MeshTunnelPathNode * -tunnel_del_path (struct MeshTunnel *t, GNUNET_PEER_Id peer_id, - struct GNUNET_SERVER_NotificationContext *nc); +struct MeshTunnelTreeNode * +tunnel_del_path (struct MeshTunnelTree *t, GNUNET_PEER_Id peer_id, + MeshNodeDisconnectCB cb); /** @@ -157,7 +249,7 @@ tunnel_del_path (struct MeshTunnel *t, GNUNET_PEER_Id peer_id, * Path must be destroyed afterwards. */ struct MeshPeerPath * -tunnel_get_path_to_peer(struct MeshTunnel *t, struct MeshPeerInfo *peer_info); +tunnel_get_path_to_peer(struct MeshTunnelTree *t, GNUNET_PEER_Id peer); /** @@ -165,23 +257,11 @@ tunnel_get_path_to_peer(struct MeshTunnel *t, struct MeshPeerInfo *peer_info); * * @param t Tunnel where to add the new path. * @param p Path to be integrated. - * @param nc Notification context to alert clients of peers - * temporarily disconnected + * @param cb Callback to use to notify about peers temporarily disconnecting * * @return GNUNET_OK in case of success. * GNUNET_SYSERR in case of error. */ int -tunnel_add_path (struct MeshTunnel *t, const struct MeshPeerPath *p); - - -/** - * Add a peer to a tunnel, accomodating paths accordingly and initializing all - * needed rescources. - * - * @param t Tunnel we want to add a new peer to - * @param peer PeerInfo of the peer being added - * - */ -void -tunnel_add_peer (struct MeshTunnel *t, struct MeshPeerInfo *peer); \ No newline at end of file +tunnel_add_path (struct MeshTunnelTree *t, const struct MeshPeerPath *p, + MeshNodeDisconnectCB cb); \ 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 d14d15958..cc0cbc558 100644 --- a/src/mesh/test_mesh_path_api.c +++ b/src/mesh/test_mesh_path_api.c @@ -51,7 +51,6 @@ int main (int argc, char *argv[]) { struct GNUNET_PeerIdentity* pi; -// struct MeshTunnel *t; int result; GNUNET_log_setup ("test_mesh_api_path", @@ -61,6 +60,7 @@ main (int argc, char *argv[]) "WARNING", #endif NULL); + pi = get_pi(1); GNUNET_log(GNUNET_ERROR_TYPE_INFO, "Peer 1: %s\n", GNUNET_h2s(&pi->hashPubKey)); -- 2.25.1