From cb67c0bb1e6f2a5bae0295a75bc1f4b1b9f9f765 Mon Sep 17 00:00:00 2001 From: Supriti Singh Date: Wed, 14 May 2014 14:06:29 +0000 Subject: - Fixes in routing table functions --- src/dht/gnunet-service-xdht_neighbours.c | 188 +++++++++------------- src/dht/gnunet-service-xdht_routing.c | 268 ++++++++++++++++++++++--------- src/dht/gnunet-service-xdht_routing.h | 5 + 3 files changed, 269 insertions(+), 192 deletions(-) diff --git a/src/dht/gnunet-service-xdht_neighbours.c b/src/dht/gnunet-service-xdht_neighbours.c index 00b4580c7..f56abf093 100644 --- a/src/dht/gnunet-service-xdht_neighbours.c +++ b/src/dht/gnunet-service-xdht_neighbours.c @@ -47,12 +47,7 @@ /* TODO: 1. to randomly choose one of the routes in case there are multiple routes to reach to the finger. - 2. Use a global array of all known peers in find_successor, Only when - a new peer is added in finger or friend peer map, then re calculate - the array. Or else use the old one. The benefit of having this list is something - I am not sure. only when the code is complete and working I will do this part. 3. Structure alignment. - 4. Check where do you set all_friends_trail_threshold? In select_random_friend? 5. In put, we don't have anything like put result. so we are not adding anything in the routing table. */ @@ -597,6 +592,19 @@ struct FriendInfo */ unsigned int pending_count; + /** + * FIXME: Refer to time.c and gnunet_time_lib.h for correct functions. + * in handle_dht_p2p_trail_rejection, you should update these values + * and whenever you are selecting a friend in select_random_friend() + * and find_successor(), you should check congestion_duration = 0, + * then proceed else if congestion_duration < your current time then also + * proceed. + * struct GNUNET_TIME_Absolute start = GNUNET_TIME_absolute_get(); + * struct GNUNET_TIME_Relative congestion_timeout = + * congestion_duration = GNUNET_TIME_absolute_add (start,congestion_timeout); + */ + struct GNUNET_TIME_Absolute congestion_duration; + /** * Head of pending messages to be sent to this friend. */ @@ -1591,6 +1599,9 @@ send_find_finger_trail_message (void *cls, /** + * FIXME: You need to handle the case of predecessor in case you don't get + * the call from finger table add then you should not send a trail teardown message + * because no one has added that in their trail. * Scan the trail to check if any of my own friend is part of trail. If yes * then shortcut the trail, send a trail teardown for the discarded trail, * update trail list and trail_length. @@ -1607,20 +1618,24 @@ scan_and_compress_trail (struct GNUNET_PeerIdentity *trail, { int i; struct FriendInfo *target_friend; - - /* If finger is my friend, then send a trail teardown message and then set - * trail_length = 0; */ + + if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,finger)) + { + *trail_length = 0; + trail = NULL; + return; + } if (GNUNET_CONTAINER_multipeermap_get (friend_peermap, finger)) { int discarded_trail_length = *trail_length; target_friend = GNUNET_CONTAINER_multipeermap_get(friend_peermap, &trail[0]); GDS_NEIGHBOURS_send_trail_teardown (&my_identity, finger, trail, discarded_trail_length, target_friend, finger); - trail_length = 0; + *trail_length = 0; trail = NULL; return; } - + i = *trail_length - 1; while (i > 1) { @@ -1646,7 +1661,6 @@ scan_and_compress_trail (struct GNUNET_PeerIdentity *trail, discarded_trail = GNUNET_malloc (discarded_trail_length * sizeof (struct GNUNET_PeerIdentity)); memcpy (discarded_trail, trail, discarded_trail_length * sizeof (struct GNUNET_PeerIdentity)); target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &trail[0]); - GDS_NEIGHBOURS_send_trail_teardown (&my_identity, finger, discarded_trail, discarded_trail_length, target_friend, &trail[i]); @@ -1726,7 +1740,7 @@ void send_trail_teardown (struct FingerInfo *removed_finger) finger_trail = finger_trail->next; i++; } - + GDS_NEIGHBOURS_send_trail_teardown (&my_identity, &(removed_finger->finger_identity), peer_list, removed_finger_trail_length, friend, &(removed_finger->finger_identity)); @@ -2024,7 +2038,7 @@ int select_closest_finger (struct FingerInfo *existing_finger, this case you don't need to check the trails. Exit. */ return GNUNET_NO; } - if (trail_length > 1) + if (trail_length > 0) { scan_and_compress_trail (trail, &trail_length, new_finger); } @@ -2056,8 +2070,10 @@ int select_closest_finger (struct FingerInfo *existing_finger, decrement_friend_trail_count (existing_finger); free_finger (existing_finger); - if (trail_length > 1) + if (trail_length > 0) + { scan_and_compress_trail (trail, &trail_length, new_finger); + } return GNUNET_YES; } else if (GNUNET_NO == select_finger (existing_finger, new_finger,finger_map_index)) @@ -2090,6 +2106,7 @@ compare_and_update_predecessor (const struct GNUNET_PeerIdentity *peer, struct FingerInfo *new_finger_entry; struct FriendInfo *first_friend_trail; int i; + int old_entry_found = GNUNET_NO; finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap); for (i= 0; i < GNUNET_CONTAINER_multipeermap_size (finger_peermap); i++) @@ -2099,6 +2116,7 @@ compare_and_update_predecessor (const struct GNUNET_PeerIdentity *peer, { if (PREDECESSOR_FINGER_ID == existing_finger->finger_map_index) { + old_entry_found = GNUNET_YES; if( GNUNET_NO == select_closest_finger (existing_finger, peer, trail, trail_length,PREDECESSOR_FINGER_ID)) return GNUNET_NO; @@ -2108,6 +2126,11 @@ compare_and_update_predecessor (const struct GNUNET_PeerIdentity *peer, } } GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter); + if(GNUNET_NO == old_entry_found) + { + trail_length = 0; + trail = NULL; + } new_finger_entry = GNUNET_malloc (sizeof (struct FingerInfo)); memcpy (&(new_finger_entry->finger_identity), peer, sizeof (struct GNUNET_PeerIdentity)); @@ -2115,7 +2138,7 @@ compare_and_update_predecessor (const struct GNUNET_PeerIdentity *peer, new_finger_entry->first_trail_length = trail_length; new_finger_entry->trail_count = 1; - if (trail != NULL) /* finger_trail is NULL in case I am my own finger identity. */ + if (0 != GNUNET_CRYPTO_cmp_peer_identity(&my_identity,peer)) /* finger_trail is NULL in case I am my own finger identity. */ { /* FIXME: Currently we are not handling the second trail. In that case, finger trail count = min (first_friend, second_friend) trail count. */ @@ -2239,7 +2262,7 @@ add_new_entry (const struct GNUNET_PeerIdentity *finger_identity, new_finger_entry->first_trail_length = finger_trail_length; new_finger_entry->trail_count = 1; - if (finger_trail != NULL) /* finger_trail is NULL in case I am my own finger identity. */ + if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,finger_identity)) /* finger_trail is NULL in case I am my own finger identity. */ { /* Incrementing the friend trails count. */ if (finger_trail_length > 0) @@ -2303,6 +2326,7 @@ int finger_table_add (const struct GNUNET_PeerIdentity *finger_identity, struct FingerInfo *existing_finger; struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter; int i; + int old_entry_found = GNUNET_NO; int new_entry_added = GNUNET_NO; if (PREDECESSOR_FINGER_ID == finger_map_index) @@ -2324,6 +2348,7 @@ int finger_table_add (const struct GNUNET_PeerIdentity *finger_identity, { if (existing_finger->finger_map_index == finger_map_index) { + old_entry_found = GNUNET_YES; if ( GNUNET_NO == select_closest_finger (existing_finger, finger_identity, finger_trail, finger_trail_length, finger_map_index)) @@ -2334,6 +2359,14 @@ int finger_table_add (const struct GNUNET_PeerIdentity *finger_identity, } } GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter); + + if (GNUNET_NO == old_entry_found) + { + if (finger_trail_length > 0) + { + scan_and_compress_trail (finger_trail, &finger_trail_length, finger_identity); + } + } /* SUPU: in this case you get GNUNET_NO, only when insertion fails in the peer map. so its an error as we already have decided to add the entry into finger peer map. */ if(GNUNET_OK == add_new_entry (finger_identity,finger_trail,finger_trail_length, finger_map_index)) @@ -2357,7 +2390,6 @@ int finger_table_add (const struct GNUNET_PeerIdentity *finger_identity, current_search_finger_index = current_search_finger_index - 1; } - return new_entry_added; } @@ -2947,11 +2979,12 @@ handle_dht_p2p_put (void *cls, const struct GNUNET_PeerIdentity *peer, memcpy (&key_value, &(put->key), sizeof (uint64_t)); if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_destination, &my_identity))) { - next_hop = GDS_ROUTING_search (¤t_source, ¤t_destination, peer); - if (next_hop == NULL) - { + GDS_ROUTING_print(); + next_hop = GDS_ROUTING_search (¤t_source, ¤t_destination, peer); + if (next_hop == NULL) + { /* refer to handle_dht_p2p_trail_setup. */ - } + } } else { @@ -3044,11 +3077,12 @@ handle_dht_p2p_get (void *cls, const struct GNUNET_PeerIdentity *peer, memcpy (&key_value, &(get->key), sizeof (uint64_t)); if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_destination, &my_identity))) { - next_hop = GDS_ROUTING_search (¤t_source, ¤t_destination, peer); - if (next_hop == NULL) - { + GDS_ROUTING_print(); + next_hop = GDS_ROUTING_search (¤t_source, ¤t_destination, peer); + if (next_hop == NULL) + { /* refer to handle_dht_p2p_trail_setup. */ - } + } } else { @@ -3245,6 +3279,7 @@ handle_dht_p2p_trail_setup (void *cls, const struct GNUNET_PeerIdentity *peer, /* Check if you are current_destination or not. */ if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_destination, &my_identity))) { + GDS_ROUTING_print(); next_hop = GDS_ROUTING_search (¤t_source, ¤t_destination, peer); /* OPTIMIZATION: Choose a peer from find_successor and choose the closest one. In case the closest one is from routing table and it is NULL, then update @@ -3282,7 +3317,6 @@ handle_dht_p2p_trail_setup (void *cls, const struct GNUNET_PeerIdentity *peer, } target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer); - /* ! HAVE A PREDECESSOR || (source_peer closer than existing PREDECESOR) */ if (PREDECESSOR_FINGER_ID != finger_map_index) { @@ -3305,7 +3339,6 @@ handle_dht_p2p_trail_setup (void *cls, const struct GNUNET_PeerIdentity *peer, memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity)); peer_list[trail_length] = my_identity; trail_length++; - target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop); GDS_NEIGHBOURS_send_trail_setup (&source, destination_finger_value, @@ -3386,8 +3419,13 @@ handle_dht_p2p_trail_setup_result(void *cls, const struct GNUNET_PeerIdentity *p if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&(trail_result->destination_peer), &(trail_result->finger_identity)))) { + /* FIXME: First call GDS_ROUTING_search, only if it returns NULL, call + GDS_ROUTING_add. But in case we have same 3 fields but 1 different next hop + then we should add the entry but in current implementation of GDS_ROUTNG_search + we don't handle it. */ GDS_ROUTING_add (&(trail_result->destination_peer), &(trail_result->finger_identity), peer, &next_hop); + GDS_ROUTING_print(); } target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop); @@ -3551,6 +3589,12 @@ handle_dht_p2p_verify_successor(void *cls, const struct GNUNET_PeerIdentity *pee { int my_index; + if (trail_length == 0) + { + GNUNET_break (0); + return GNUNET_SYSERR; + } + my_index = search_my_index (trail_peer_list, trail_length); if (my_index == GNUNET_SYSERR) { @@ -3999,9 +4043,10 @@ int handle_dht_p2p_trail_teardown(void *cls, const struct GNUNET_PeerIdentity *p my_index = search_my_index (discarded_trail, discarded_trail_length); if(GNUNET_SYSERR == my_index) return GNUNET_SYSERR; - + + GDS_ROUTING_print(); if (GNUNET_NO == GDS_ROUTING_remove_trail (&(trail_teardown->source_peer), - &(trail_teardown->destination_peer),peer)) + &(trail_teardown->destination_peer),peer)) { /* Here we get GNUNET_NO, only if there is no matching entry found in routing table. */ @@ -4011,7 +4056,6 @@ int handle_dht_p2p_trail_teardown(void *cls, const struct GNUNET_PeerIdentity *p memcpy (&next_hop, &discarded_trail[my_index + 1], sizeof (struct GNUNET_PeerIdentity)); target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop); - GDS_NEIGHBOURS_send_trail_teardown (&(trail_teardown->source_peer), &(trail_teardown->destination_peer), discarded_trail, discarded_trail_length, @@ -4022,87 +4066,6 @@ int handle_dht_p2p_trail_teardown(void *cls, const struct GNUNET_PeerIdentity *p } -#if 0 -/** - * FIXME: we don't send trail teardown to finger for which the trail was setup. - * Trail teardown only aim is to remove entries from the routing table. Destination - * finger does not have any entry in its routing table. So, it does not need - * a trail teardown. - * Core handle for p2p trail tear down messages. - * @param cls closure - * @param message message - * @param peer peer identity this notification is about - * @return GNUNET_OK on success, GNUNET_SYSERR on error - */ -static -int handle_dht_p2p_trail_teardown (void *cls, const struct GNUNET_PeerIdentity *peer, - const struct GNUNET_MessageHeader *message) -{ - struct PeerTrailTearDownMessage *trail_teardown; - struct GNUNET_PeerIdentity *trail_peer_list; - struct GNUNET_PeerIdentity next_hop; - struct FriendInfo *target_friend; - uint32_t trail_length; - size_t msize; - int my_index; - - msize = ntohs (message->size); - if (msize < sizeof (struct PeerTrailTearDownMessage)) - { - GNUNET_break_op (0); - return GNUNET_YES; - } - - trail_teardown = (struct PeerTrailTearDownMessage *) message; - trail_length = ntohl (trail_teardown->trail_length); - - if ((msize < sizeof (struct PeerTrailTearDownMessage) + - trail_length * sizeof (struct GNUNET_PeerIdentity)) || - (trail_length > - GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity))) - { - GNUNET_break_op (0); - return GNUNET_YES; - } - - trail_peer_list = (struct GNUNET_PeerIdentity *) &trail_teardown[1]; - - if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(trail_teardown->destination_peer), &my_identity))) - { - /* I am the destination of the trail, but I am not part of trail. I don't - need to remove any entry from my routing table. So, I should not get this - message. */ - GNUNET_break (0); - return GNUNET_YES; - } - - my_index = search_my_index (trail_peer_list, trail_length); - if(GNUNET_SYSERR == my_index) - return GNUNET_SYSERR; - - if (GNUNET_NO == GDS_ROUTING_remove_trail (&(trail_teardown->source_peer), - &(trail_teardown->destination_peer),peer)) - { - /* Here we get GNUNET_NO, only if there is no matching entry found in routing - table. */ - GNUNET_break (0); - return GNUNET_YES; - } - - /* I am the last element of the trail. */ - if(my_index == trail_length - 1) - return GNUNET_YES; - - memcpy (&next_hop, &trail_peer_list[my_index + 1], sizeof (struct GNUNET_PeerIdentity)); - target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop); - /* FIXME:add a new field new_first_friend. */ - GDS_NEIGHBOURS_send_trail_teardown (&(trail_teardown->source_peer), - &(trail_teardown->destination_peer), - trail_peer_list, trail_length, target_friend); - return GNUNET_YES; -} -#endif - /** * Iterate over finger_peermap, and remove entries with peer as the first element * of their trail. @@ -4170,6 +4133,7 @@ handle_core_disconnect (void *cls, * FIXME: Here do we only remove the entry from our own routing table * or do we also inform other peers which are part of trail. It seems to be * too much of messages exchanged. */ + GDS_ROUTING_print(); GDS_ROUTING_remove_entry (peer); /* Remove the peer from friend_peermap. */ @@ -4330,4 +4294,4 @@ GDS_NEIGHBOURS_get_my_id (void) } -/* end of gnunet-service-xdht_neighbours.c */ +/* end of gnunet-service-xdht_neighbours.c */ \ No newline at end of file diff --git a/src/dht/gnunet-service-xdht_routing.c b/src/dht/gnunet-service-xdht_routing.c index 3601a4186..7bf96e9d0 100644 --- a/src/dht/gnunet-service-xdht_routing.c +++ b/src/dht/gnunet-service-xdht_routing.c @@ -33,11 +33,6 @@ 2. if we can merge remove_peer and remove_trail 3. do we need next_hop to uniquely identify a trail in remove_trail. */ -/** - * Number of requests we track at most (for routing replies). - */ -#define DHT_MAX_RECENT (1024 * 16) - /** * Maximum number of entries in routing table. */ @@ -76,65 +71,118 @@ struct RoutingTrail */ static struct GNUNET_CONTAINER_MultiPeerMap *routing_table; + /** - * Iterate over routing table and remove entries for which peer is a part. - * @param cls closure - * @param key current public key - * @param value value in the hash map - * @return #GNUNET_YES if we should continue to - * iterate, - * #GNUNET_NO if not. + * Get next hop from the trail with source peer, destination peer and next hop + * same as the argument to this function. + * @param source_peer Source peer of the trail. + * @param destination_peer Destination peer of the trail. + * @param prev_hop Previous hop of the trail. + * @return #GNUNET_YES if we found the matching trail. + * #GNUNET_NO if we found no matching trail. */ static int -remove_routing_entry (void *cls, - const struct GNUNET_PeerIdentity *key, - void *value) +get_next_hop (struct RoutingTrail *trail, + struct GNUNET_PeerIdentity *source_peer, + struct GNUNET_PeerIdentity *destination_peer, + const struct GNUNET_PeerIdentity *prev_hop) { - struct RoutingTrail *remove_entry = value; - const struct GNUNET_PeerIdentity *disconnected_peer = cls; - - if ((0 == GNUNET_CRYPTO_cmp_peer_identity (&(remove_entry->source), disconnected_peer)) || - (0 == GNUNET_CRYPTO_cmp_peer_identity (&(remove_entry->destination), disconnected_peer)) || - (0 == GNUNET_CRYPTO_cmp_peer_identity (&(remove_entry->next_hop), disconnected_peer)) || - (0 == GNUNET_CRYPTO_cmp_peer_identity (&(remove_entry->prev_hop), disconnected_peer))) + if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(trail->source),source_peer)) { - GNUNET_assert (GNUNET_YES == - GNUNET_CONTAINER_multipeermap_remove (routing_table, - key, - remove_entry)); + if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(trail->prev_hop),prev_hop)) + { + return GNUNET_YES; + } + else + return GNUNET_NO; } - return GNUNET_YES; + return GNUNET_NO; } /** - * Iterate over multiple entries for same destination value and get - * the correct next hop. - * @param cls struct RoutingTrail - * @param key Destination identity - * @param value struct RoutingTrail - * @return #GNUNET_YES to continue looking, #GNUNET_NO if we found the next hop + * FIXME: How to ensure that with only 3 fields also we have a unique trail. + * in case of redundant routes we can have different next hop. + * in that case we have to call this function on each entry of routing table + * and from multiple next hop we return one. Here also we are going to return one. + * URGENT. + * Assumption - there can be only on one trail with all these fields. But if + * we consider only 3 fields then it is possible that next hop is differet. + * Update prev_hop field to source_peer. Trail from source peer to destination + * peer is compressed such that I am the first friend in the trail. + * @param source_peer Source of the trail. + * @param destination_peer Destination of the trail. + * @param prev_hop Peer before me in the trail. + * @return #GNUNET_YES trail is updated. + * #GNUNET_NO, trail not found. */ int -get_next_hop (void *cls, const struct GNUNET_PeerIdentity *key, void *value) +GDS_ROUTING_trail_update (struct GNUNET_PeerIdentity *source_peer, + struct GNUNET_PeerIdentity *destination_peer, + struct GNUNET_PeerIdentity *prev_hop) { - /* Here you should match if source, prev hop matches if yes then send - GNUNET_NO as you don't need to check more entries. */ - struct RoutingTrail *request = cls; - struct RoutingTrail *existing_entry = (struct RoutingTrail *)value; + /* 1. find the trail corresponding to these values. + 2. update the prev hop to source peer. */ + struct RoutingTrail *trail; + struct GNUNET_CONTAINER_MultiPeerMapIterator *iterator; + int i; - if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(request->source), &(existing_entry->source))) + iterator = GNUNET_CONTAINER_multipeermap_iterator_create (routing_table); + for (i = 0; i< GNUNET_CONTAINER_multipeermap_size(routing_table); i++) { - if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(request->prev_hop), &(existing_entry->prev_hop))) + if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (iterator, NULL, + (const void **)&trail)) { - memcpy (&(request->next_hop), &(existing_entry->next_hop), sizeof (struct GNUNET_PeerIdentity)); - return GNUNET_YES; + if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(trail->destination), destination_peer)) + { + if (GNUNET_YES == get_next_hop (trail, source_peer, destination_peer, prev_hop)) + { + memcpy (&(trail->prev_hop), source_peer, sizeof (struct GNUNET_PeerIdentity)); + return GNUNET_YES; + } + } } } return GNUNET_NO; } +/** + * Find the next hop to send packet to. + * @param source_peer Source of the trail. + * @param destination_peer Destination of the trail. + * @param prev_hop Previous hop in the trail. + * @return Next hop in the trail from source to destination. + */ +struct GNUNET_PeerIdentity * +GDS_ROUTING_search (struct GNUNET_PeerIdentity *source_peer, + struct GNUNET_PeerIdentity *destination_peer, + const struct GNUNET_PeerIdentity *prev_hop) +{ + struct RoutingTrail *trail; + struct GNUNET_CONTAINER_MultiPeerMapIterator *iterator; + int i; + + iterator = GNUNET_CONTAINER_multipeermap_iterator_create (routing_table); + for (i = 0; i< GNUNET_CONTAINER_multipeermap_size(routing_table); i++) + { + if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (iterator, NULL, + (const void **)&trail)) + { + if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(trail->destination), destination_peer)) + { + if (GNUNET_YES == get_next_hop (trail, source_peer, destination_peer, prev_hop)) + { + return &(trail->next_hop); + } + } + } + } + GNUNET_CONTAINER_multipeermap_iterator_destroy (iterator); + return NULL; +} + + /** * Add a new entry to our routing table. * @param source peer Source of the trail. @@ -171,71 +219,100 @@ GDS_ROUTING_add (const struct GNUNET_PeerIdentity *source, /** * Iterate over routing table and remove entries for which peer is a part. - * @param peer - * @return + * @param cls closure + * @param key current public key + * @param value value in the hash map + * @return #GNUNET_YES if we should continue to + * iterate, + * #GNUNET_NO if not. + */ +static int +remove_routing_entry (void *cls, + const struct GNUNET_PeerIdentity *key, + void *value) +{ + struct RoutingTrail *remove_entry = value; + const struct GNUNET_PeerIdentity *disconnected_peer = cls; + + if ((0 == GNUNET_CRYPTO_cmp_peer_identity (&(remove_entry->source), disconnected_peer)) || + (0 == GNUNET_CRYPTO_cmp_peer_identity (&(remove_entry->destination), disconnected_peer)) || + (0 == GNUNET_CRYPTO_cmp_peer_identity (&(remove_entry->next_hop), disconnected_peer)) || + (0 == GNUNET_CRYPTO_cmp_peer_identity (&(remove_entry->prev_hop), disconnected_peer))) + { + GNUNET_assert (GNUNET_YES == + GNUNET_CONTAINER_multipeermap_remove (routing_table, + key, + remove_entry)); + } + return GNUNET_YES; +} + + +/** + * FIXME: add a return value. + * Iterate over routing table and remove all entries for which peer is a part. + * @param peer Peer to be searched for in the trail to remove that trail. */ void GDS_ROUTING_remove_entry (const struct GNUNET_PeerIdentity *peer) { GNUNET_CONTAINER_multipeermap_iterate (routing_table, &remove_routing_entry, - (void *)peer); + (void *)peer); } -/** FIXME:TODO URGNET Need to understand if we need next hop to uniquely identify an entry - * in routing table or not. - * Remove the trail as result of trail tear down message. +/** + * In response to trail teardown message, remove the trail with source peer, + * destination peer and next hop same as the argument to this function. + * Assumption - there can be only one possible trail with these 4 values. * @param source_peer Source of the trail. * @param destination_peer Destination of the trail. * @param next_hop Next hop - * @param prev_hop Previous hop. + * @param prev_hop Previous hop. + * @return #GNUNET_YES Matching trail deleted from routing table. + * #GNUNET_NO No matching trail found. + * */ int GDS_ROUTING_remove_trail (struct GNUNET_PeerIdentity *source_peer, struct GNUNET_PeerIdentity *destination_peer, const struct GNUNET_PeerIdentity *prev_hop) { + struct RoutingTrail *trail; + struct GNUNET_CONTAINER_MultiPeerMapIterator *iterator; + int i; + + iterator = GNUNET_CONTAINER_multipeermap_iterator_create (routing_table); + for (i = 0; i< GNUNET_CONTAINER_multipeermap_size(routing_table); i++) + { + if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (iterator, NULL, + (const void **)&trail)) + { + if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(trail->destination), destination_peer)) + { + GNUNET_assert (GNUNET_YES == + GNUNET_CONTAINER_multipeermap_remove (routing_table, + &(trail->destination), + trail)); + return GNUNET_YES; + } + } + } + GNUNET_CONTAINER_multipeermap_iterator_destroy (iterator); return GNUNET_NO; } -/** - * Find the next hop to send packet to. - * @param source_peer Source of the trail. - * @param destination_peer Destination of the trail. - * @param prev_hop Previous hop in the trail. - * @return Next hop in the trail from source to destination. - */ -struct GNUNET_PeerIdentity * -GDS_ROUTING_search(struct GNUNET_PeerIdentity *source_peer, - struct GNUNET_PeerIdentity *destination_peer, - const struct GNUNET_PeerIdentity *prev_hop) -{ - struct RoutingTrail *trail; - trail = GNUNET_malloc (sizeof (struct RoutingTrail)); - memcpy (&(trail->destination), destination_peer, sizeof (struct GNUNET_PeerIdentity)); - memcpy (&(trail->source), source_peer, sizeof (struct GNUNET_PeerIdentity)); - memcpy (&(trail->prev_hop), prev_hop, sizeof (struct GNUNET_PeerIdentity)); - - GNUNET_CONTAINER_multipeermap_get_multiple (routing_table, destination_peer, - get_next_hop, trail); - if(trail != NULL) - return &(trail->next_hop); - else - return NULL; -} /** - * FIXME:URGENT:Better name. * Check if the size of routing table has crossed threshold. * @return #GNUNET_YES, if threshold crossed else #GNUNET_NO. */ int GDS_ROUTING_check_threshold () { - int ret; - ret = (GNUNET_CONTAINER_multipeermap_size(routing_table) > ROUTING_TABLE_THRESHOLD) ? GNUNET_YES:GNUNET_NO; - return ret; + return (GNUNET_CONTAINER_multipeermap_size(routing_table) > ROUTING_TABLE_THRESHOLD) ? + GNUNET_YES:GNUNET_NO; } @@ -245,11 +322,42 @@ GDS_ROUTING_check_threshold () void GDS_ROUTING_init (void) { - routing_table = GNUNET_CONTAINER_multipeermap_create (DHT_MAX_RECENT * 4 / 3, GNUNET_NO); + routing_table = GNUNET_CONTAINER_multipeermap_create (ROUTING_TABLE_THRESHOLD * 4 / 3, + GNUNET_NO); } - /** + * ONLY FOR TESTING. + */ +void +GDS_ROUTING_print (void) +{ + struct RoutingTrail *trail; + struct GNUNET_CONTAINER_MultiPeerMapIterator *iterator; + int i; + + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Routing table entries \n"); + iterator = GNUNET_CONTAINER_multipeermap_iterator_create (routing_table); + for (i = 0; i< GNUNET_CONTAINER_multipeermap_size(routing_table); i++) + { + if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (iterator, NULL, + (const void **)&trail)) + { + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Routing trail source \n", GNUNET_i2s (&(trail->source))); + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Routing trail source \n", GNUNET_i2s (&(trail->destination))); + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Routing trail source \n", GNUNET_i2s (&(trail->next_hop))); + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Routing trail source \n", GNUNET_i2s (&(trail->prev_hop))); + } + } + +} +/** + * FIXME: here you can have routing table with size 0, only when you delete + * the entries correctly. Possible scenarios where we delete the entries are + * 1. when one of my friend gets disconnected then I remove any trail (does not + * matter if that friend is source, destination, next hop or previous hop). + * 2. if I get a trail teardown message then I remove the entry. + * Is there any other case that I may have missed? * Shutdown routing subsystem. */ void diff --git a/src/dht/gnunet-service-xdht_routing.h b/src/dht/gnunet-service-xdht_routing.h index 63007c7e4..0b0c80862 100644 --- a/src/dht/gnunet-service-xdht_routing.h +++ b/src/dht/gnunet-service-xdht_routing.h @@ -78,6 +78,11 @@ GDS_ROUTING_remove_trail (struct GNUNET_PeerIdentity *source_peer, struct GNUNET_PeerIdentity *destination_peer, const struct GNUNET_PeerIdentity *prev_hop); +/** + * FOR TESTING. + */ +void +GDS_ROUTING_print (void); /** * Check if size of routing table is greater than threshold or not. -- cgit v1.2.3