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 64
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);
117 return GNUNET_SYSERR;
119 trail->next_hop = next_hop;
124 * Get the next hop for trail corresponding to trail_id
125 * @param trail_id Trail id to be searched.
126 * @return Next_hop if found
127 * NULL If next hop not found.
129 struct GNUNET_PeerIdentity *
130 GDS_ROUTING_get_next_hop (const struct GNUNET_HashCode trail_id,
131 enum GDS_ROUTING_trail_direction trail_direction)
133 struct RoutingTrail *trail;
135 trail = GNUNET_CONTAINER_multihashmap_get (routing_table, &trail_id);
140 switch (trail_direction)
142 case GDS_ROUTING_SRC_TO_DEST:
143 return &(trail->next_hop);
144 case GDS_ROUTING_DEST_TO_SRC:
145 return &(trail->prev_hop);
152 * Remove trail with trail_id
153 * @param trail_id Trail id to be removed
154 * @return #GNUNET_YES success
155 * #GNUNET_NO if entry not found.
158 GDS_ROUTING_remove_trail (const struct GNUNET_HashCode remove_trail_id)
160 struct RoutingTrail *remove_entry;
162 remove_entry = GNUNET_CONTAINER_multihashmap_get (routing_table, &remove_trail_id);
164 if (NULL == remove_entry)
167 if (GNUNET_YES == GNUNET_CONTAINER_multihashmap_remove (routing_table,
171 GNUNET_free (remove_entry);
179 * Iterate over routing table and remove entries with value as part of any trail.
182 * @param key current public key
183 * @param value value in the hash map
184 * @return #GNUNET_YES if we should continue to iterate,
187 static int remove_matching_trails (void *cls,
188 const struct GNUNET_HashCode *key,
191 struct RoutingTrail *remove_trail = value;
192 struct GNUNET_PeerIdentity *disconnected_peer = cls;
193 struct GNUNET_HashCode trail_id = *key;
194 struct GNUNET_PeerIdentity my_identity;
196 /* If disconnected_peer is next_hop, then send a trail teardown message through
197 * prev_hop in direction from destination to source. */
198 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&remove_trail->next_hop,
201 my_identity = GDS_NEIGHBOURS_get_my_id ();
202 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
203 &remove_trail->prev_hop))
205 GDS_NEIGHBOURS_send_trail_teardown (trail_id,
206 GDS_ROUTING_DEST_TO_SRC,
207 remove_trail->prev_hop);
211 /* If disconnected_peer is prev_hop, then send a trail teardown through
212 * next_hop in direction from Source to Destination. */
213 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&remove_trail->prev_hop,
216 my_identity = GDS_NEIGHBOURS_get_my_id ();
217 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
218 &remove_trail->next_hop))
220 GDS_NEIGHBOURS_send_trail_teardown (trail_id,
221 GDS_ROUTING_SRC_TO_DEST,
222 remove_trail->next_hop);
226 GNUNET_assert (GNUNET_YES ==
227 GNUNET_CONTAINER_multihashmap_remove (routing_table,
230 GNUNET_free (remove_trail);
237 * Remove after using.
240 GDS_ROUTING_test_print (void)
242 struct GNUNET_CONTAINER_MultiHashMapIterator *iter;
243 struct RoutingTrail *trail;
244 struct GNUNET_PeerIdentity print_peer;
245 struct GNUNET_HashCode key_ret;
248 FPRINTF (stderr,_("\nSUPU ***PRINTING ROUTING TABLE *****"));
249 iter =GNUNET_CONTAINER_multihashmap_iterator_create (routing_table);
250 for (i = 0; i < GNUNET_CONTAINER_multihashmap_size(routing_table); i++)
252 if(GNUNET_YES == GNUNET_CONTAINER_multihashmap_iterator_next (iter,
254 (const void **)&trail))
256 FPRINTF (stderr,_("\nSUPU %s, %s, %d, trail->trail_id = %s"),
257 __FILE__, __func__,__LINE__, GNUNET_h2s(&trail->trail_id));
258 memcpy (&print_peer, &trail->next_hop, sizeof (struct GNUNET_PeerIdentity));
259 FPRINTF (stderr,_("\nSUPU %s, %s, %d, trail->next_hop = %s"),
260 __FILE__, __func__,__LINE__, GNUNET_i2s(&print_peer));
261 memcpy (&print_peer, &trail->prev_hop, sizeof (struct GNUNET_PeerIdentity));
262 FPRINTF (stderr,_("\nSUPU %s, %s, %d, trail->prev_hop = %s"),
263 __FILE__, __func__,__LINE__, GNUNET_i2s(&print_peer));
270 * Remove every trail where peer is either next_hop or prev_hop. Also send a
271 * trail teardown message in direction of hop which is not disconnected.
272 * @param peer Peer identity. Trail containing this peer should be removed.
275 GDS_ROUTING_remove_trail_by_peer (const struct GNUNET_PeerIdentity *peer)
278 /* No entries in my routing table. */
279 if (0 == GNUNET_CONTAINER_multihashmap_size(routing_table))
282 ret = GNUNET_CONTAINER_multihashmap_iterate (routing_table,
283 &remove_matching_trails,
290 * Add a new entry in routing table
291 * @param new_trail_id
294 * @return #GNUNET_OK success
295 * #GNUNET_SYSERR in case new_trail_id already exists in the network
296 * but with different prev_hop/next_hop
299 GDS_ROUTING_add (struct GNUNET_HashCode new_trail_id,
300 struct GNUNET_PeerIdentity prev_hop,
301 struct GNUNET_PeerIdentity next_hop)
303 struct RoutingTrail *new_entry;
305 new_entry = GNUNET_new (struct RoutingTrail);
306 new_entry->trail_id = new_trail_id;
307 new_entry->next_hop = next_hop;
308 new_entry->prev_hop = prev_hop;
310 return GNUNET_CONTAINER_multihashmap_put (routing_table,
311 &new_trail_id, new_entry,
312 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY);
317 * Check if the size of routing table has crossed ROUTING_TABLE_THRESHOLD.
318 * It means that I don't have any more space in my routing table and I can not
319 * be part of any more trails till there is free space in my routing table.
320 * @return #GNUNET_YES, if threshold crossed else #GNUNET_NO.
323 GDS_ROUTING_threshold_reached (void)
325 return (GNUNET_CONTAINER_multihashmap_size(routing_table) >
326 ROUTING_TABLE_THRESHOLD) ? GNUNET_YES:GNUNET_NO;
331 * Initialize routing subsystem.
334 GDS_ROUTING_init (void)
336 routing_table = GNUNET_CONTAINER_multihashmap_create (ROUTING_TABLE_THRESHOLD * 4 / 3,
342 * Shutdown routing subsystem.
345 GDS_ROUTING_done (void)
347 GNUNET_assert (0 == GNUNET_CONTAINER_multihashmap_size (routing_table));
348 GNUNET_CONTAINER_multihashmap_destroy (routing_table);
351 /* end of gnunet-service-xdht_routing.c */