2 This file is part of GNUnet.
3 (C) 2011 - 2014 Christian Grothoff (and other contributing authors)
5 GNUnet is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published
7 by the Free Software Foundation; either version 3, or (at your
8 option) any later version.
10 GNUnet is distributed in the hope that it will be useful, but
11 WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 General Public License for more details.
15 You should have received a copy of the GNU General Public License
16 along with GNUnet; see the file COPYING. If not, write to the
17 Free Software Foundation, Inc., 59 Temple Place - Suite 330,
18 Boston, MA 02111-1307, USA.
22 * @file dht/gnunet-service-xdht_routing.c
23 * @brief GNUnet DHT tracking of requests for routing replies
24 * @author Supriti Singh
27 #include "gnunet-service-xdht_neighbours.h"
28 #include "gnunet-service-xdht_routing.h"
29 #include "gnunet-service-xdht.h"
33 * FIXME: Check if its better to store pointer to friend rather than storing
34 * peer identity next_hop or prev_hop.
35 * keep entries in destnation and source peer also. so when we send the trail
36 * teardown message then we don't know the source but if source gets the message
37 * then it shold remove that trail id from its finger table. But how does
38 * source know what is the desination finger ? It will whenevr contact a trail
39 * will do a lookup in routing table and if no trail id present the remove
40 * that trail of the finger and if only one trail then remove the finger.
41 * because of this use case of trail teardown I think trail compression
42 * and trail teardown should not be merged.
43 * 2. store a pointer to friendInfo in place o peer identity.
46 * Maximum number of entries in routing table.
48 #define ROUTING_TABLE_THRESHOLD 80000
51 * FIXME: Store friend pointer instead of peer identifier.
52 * Routing table entry .
57 * Global Unique identifier of the trail.
59 struct GNUNET_HashCode trail_id;
62 * The peer to which this request should be passed to.
64 struct GNUNET_PeerIdentity next_hop;
67 * Peer just before next hop in the trail.
69 struct GNUNET_PeerIdentity prev_hop;
73 * Routing table of the peer
75 static struct GNUNET_CONTAINER_MultiHashMap *routing_table;
78 * Update the prev. hop of the trail. Call made by trail compression where
79 * if you are the first friend now in the trail then you need to update
82 * @return #GNUNET_OK success
83 * #GNUNET_SYSERR in case no matching entry found in routing table.
86 GDS_ROUTING_update_trail_prev_hop (const struct GNUNET_HashCode trail_id,
87 struct GNUNET_PeerIdentity prev_hop)
89 struct RoutingTrail *trail;
91 trail = GNUNET_CONTAINER_multihashmap_get (routing_table, &trail_id);
96 trail->prev_hop = prev_hop;
101 * Update the next hop of the trail. Call made by trail compression where
102 * if you are source of the trail and now you have a new first friend, then
103 * you should update the trail.
105 * @return #GNUNET_OK success
106 * #GNUNET_SYSERR in case no matching entry found in routing table.
109 GDS_ROUTING_update_trail_next_hop (const struct GNUNET_HashCode trail_id,
110 struct GNUNET_PeerIdentity next_hop)
112 struct RoutingTrail *trail;
114 trail = GNUNET_CONTAINER_multihashmap_get (routing_table, &trail_id);
118 return GNUNET_SYSERR;
120 trail->next_hop = next_hop;
125 * Get the next hop for trail corresponding to trail_id
126 * @param trail_id Trail id to be searched.
127 * @return Next_hop if found
128 * NULL If next hop not found.
130 struct GNUNET_PeerIdentity *
131 GDS_ROUTING_get_next_hop (const struct GNUNET_HashCode trail_id,
132 enum GDS_ROUTING_trail_direction trail_direction)
134 struct RoutingTrail *trail;
136 trail = GNUNET_CONTAINER_multihashmap_get (routing_table, &trail_id);
139 /* If a friend got disconnected and we removed all the entry from the
140 routing table, then trail will be deleted and my identity will not know
141 and when it tries to reach to that finger it fails. thats why
142 assertion always fails in*/
145 switch (trail_direction)
147 case GDS_ROUTING_SRC_TO_DEST:
148 return &(trail->next_hop);
149 case GDS_ROUTING_DEST_TO_SRC:
150 return &(trail->prev_hop);
157 * Remove trail with trail_id
158 * @param trail_id Trail id to be removed
159 * @return #GNUNET_YES success
160 * #GNUNET_NO if entry not found.
163 GDS_ROUTING_remove_trail (const struct GNUNET_HashCode remove_trail_id)
165 struct RoutingTrail *remove_entry;
167 remove_entry = GNUNET_CONTAINER_multihashmap_get (routing_table, &remove_trail_id);
168 if (NULL == remove_entry)
171 if (GNUNET_YES == GNUNET_CONTAINER_multihashmap_remove (routing_table,
175 GNUNET_free (remove_entry);
184 * Iterate over routing table and remove entries with value as part of any trail.
187 * @param key current public key
188 * @param value value in the hash map
189 * @return #GNUNET_YES if we should continue to iterate,
192 static int remove_matching_trails (void *cls,
193 const struct GNUNET_HashCode *key,
196 struct RoutingTrail *remove_trail = value;
197 struct GNUNET_PeerIdentity *disconnected_peer = cls;
198 struct GNUNET_HashCode trail_id = *key;
199 struct GNUNET_PeerIdentity my_identity;
201 /* If disconnected_peer is next_hop, then send a trail teardown message through
202 * prev_hop in direction from destination to source. */
203 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&remove_trail->next_hop,
206 my_identity = GDS_NEIGHBOURS_get_my_id ();
207 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
208 &remove_trail->prev_hop))
210 GDS_NEIGHBOURS_send_trail_teardown (trail_id,
211 GDS_ROUTING_DEST_TO_SRC,
212 remove_trail->prev_hop);
216 /* If disconnected_peer is prev_hop, then send a trail teardown through
217 * next_hop in direction from Source to Destination. */
218 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&remove_trail->prev_hop,
221 my_identity = GDS_NEIGHBOURS_get_my_id ();
223 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
224 &remove_trail->next_hop))
226 GDS_NEIGHBOURS_send_trail_teardown (trail_id,
227 GDS_ROUTING_SRC_TO_DEST,
228 remove_trail->next_hop);
232 GNUNET_assert (GNUNET_YES ==
233 GNUNET_CONTAINER_multihashmap_remove (routing_table,
236 GNUNET_free (remove_trail);
243 * Remove after using.
246 GDS_ROUTING_test_print (void)
248 struct GNUNET_CONTAINER_MultiHashMapIterator *iter;
249 struct RoutingTrail *trail;
250 struct GNUNET_PeerIdentity print_peer;
251 struct GNUNET_HashCode key_ret;
254 struct GNUNET_PeerIdentity my_identity = GDS_NEIGHBOURS_get_my_id();
255 print_peer = my_identity;
256 FPRINTF (stderr,_("\nSUPU ***PRINTING ROUTING TABLE ***** of =%s"),GNUNET_i2s(&print_peer));
257 iter =GNUNET_CONTAINER_multihashmap_iterator_create (routing_table);
258 for (i = 0; i < GNUNET_CONTAINER_multihashmap_size(routing_table); i++)
260 if(GNUNET_YES == GNUNET_CONTAINER_multihashmap_iterator_next (iter,
262 (const void **)&trail))
264 FPRINTF (stderr,_("\nSUPU %s, %s, %d, trail->trail_id = %s"),
265 __FILE__, __func__,__LINE__, GNUNET_h2s(&trail->trail_id));
266 memcpy (&print_peer, &trail->next_hop, sizeof (struct GNUNET_PeerIdentity));
267 FPRINTF (stderr,_("\nSUPU %s, %s, %d, trail->next_hop = %s"),
268 __FILE__, __func__,__LINE__, GNUNET_i2s(&print_peer));
269 memcpy (&print_peer, &trail->prev_hop, sizeof (struct GNUNET_PeerIdentity));
270 FPRINTF (stderr,_("\nSUPU %s, %s, %d, trail->prev_hop = %s"),
271 __FILE__, __func__,__LINE__, GNUNET_i2s(&print_peer));
278 * Remove every trail where peer is either next_hop or prev_hop. Also send a
279 * trail teardown message in direction of hop which is not disconnected.
280 * @param peer Peer identity. Trail containing this peer should be removed.
283 GDS_ROUTING_remove_trail_by_peer (const struct GNUNET_PeerIdentity *peer)
288 /* No entries in my routing table. */
289 if (0 == GNUNET_CONTAINER_multihashmap_size(routing_table))
292 ret = GNUNET_CONTAINER_multihashmap_iterate (routing_table,
293 &remove_matching_trails,
300 * Add a new entry in routing table
301 * @param new_trail_id
304 * @return #GNUNET_OK success
305 * #GNUNET_SYSERR in case new_trail_id already exists in the network
306 * but with different prev_hop/next_hop
309 GDS_ROUTING_add (struct GNUNET_HashCode new_trail_id,
310 struct GNUNET_PeerIdentity prev_hop,
311 struct GNUNET_PeerIdentity next_hop)
313 struct RoutingTrail *new_entry;
315 new_entry = GNUNET_new (struct RoutingTrail);
316 new_entry->trail_id = new_trail_id;
317 new_entry->next_hop = next_hop;
318 new_entry->prev_hop = prev_hop;
321 return GNUNET_CONTAINER_multihashmap_put (routing_table,
322 &new_trail_id, new_entry,
323 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY);
329 * Check if the size of routing table has crossed ROUTING_TABLE_THRESHOLD.
330 * It means that I don't have any more space in my routing table and I can not
331 * be part of any more trails till there is free space in my routing table.
332 * @return #GNUNET_YES, if threshold crossed else #GNUNET_NO.
335 GDS_ROUTING_threshold_reached (void)
337 return (GNUNET_CONTAINER_multihashmap_size(routing_table) >
338 ROUTING_TABLE_THRESHOLD) ? GNUNET_YES:GNUNET_NO;
343 * Initialize routing subsystem.
346 GDS_ROUTING_init (void)
348 routing_table = GNUNET_CONTAINER_multihashmap_create (ROUTING_TABLE_THRESHOLD * 4 / 3,
354 * Shutdown routing subsystem.
357 GDS_ROUTING_done (void)
359 GNUNET_assert (0 == GNUNET_CONTAINER_multihashmap_size (routing_table));
360 GNUNET_CONTAINER_multihashmap_destroy (routing_table);
363 /* end of gnunet-service-xdht_routing.c */