src/dht/gnunet-service-xdht_routing.c

   1 /*
   2      This file is part of GNUnet.
   3      Copyright (C) 2011 - 2014 GNUnet e.V.
   4
   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.
   9
  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.
  14
  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., 51 Franklin Street, Fifth Floor,
  18      Boston, MA 02110-1301, USA.
  19 */
  20
  21 /**
  22  * @file dht/gnunet-service-xdht_routing.c
  23  * @brief GNUnet DHT tracking of requests for routing replies
  24  * @author Supriti Singh
  25  */
  26 #include "platform.h"
  27 #include "gnunet-service-xdht_neighbours.h"
  28 #include "gnunet-service-xdht_routing.h"
  29 #include "gnunet-service-xdht.h"
  30
  31
  32 /**
  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.
  44  */
  45 /**
  46  * Maximum number of entries in routing table.
  47  */
  48 #define ROUTING_TABLE_THRESHOLD 80000
  49
  50 /**
  51  * FIXME: Store friend pointer instead of peer identifier.
  52  * Routing table entry .
  53  */
  54 struct RoutingTrail
  55 {
  56   /**
  57    * Global Unique identifier of the trail.
  58    */
  59   struct GNUNET_HashCode trail_id;
  60
  61   /**
  62    * The peer to which this request should be passed to.
  63    */
  64   struct GNUNET_PeerIdentity next_hop;
  65
  66   /**
  67    * Peer just before next hop in the trail.
  68    */
  69   struct GNUNET_PeerIdentity prev_hop;
  70 };
  71
  72 /**
  73  * Routing table of the peer
  74  */
  75 static struct GNUNET_CONTAINER_MultiHashMap *routing_table;
  76
  77 /**
  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
  80  * your prev. hop.
  81  * @param trail_id
  82  * @return #GNUNET_OK success
  83  *         #GNUNET_SYSERR in case no matching entry found in routing table.
  84  */
  85 int
  86 GDS_ROUTING_update_trail_prev_hop (const struct GNUNET_HashCode *trail_id,
  87                                    const struct GNUNET_PeerIdentity *prev_hop)
  88 {
  89   struct RoutingTrail *trail;
  90
  91   trail = GNUNET_CONTAINER_multihashmap_get (routing_table,
  92                                              trail_id);
  93
  94   if (NULL == trail)
  95     return GNUNET_SYSERR;
  96   trail->prev_hop = *prev_hop;
  97   return GNUNET_OK;
  98 }
  99
 100
 101 /**
 102  * Update the next hop of the trail. Call made by trail compression where
 103  * if you are source of the trail and now you have a new first friend, then
 104  * you should update the trail.
 105  * @param trail_id
 106  * @return #GNUNET_OK success
 107  *         #GNUNET_SYSERR in case no matching entry found in routing table.
 108  */
 109 int
 110 GDS_ROUTING_update_trail_next_hop (const struct GNUNET_HashCode *trail_id,
 111                                    const struct GNUNET_PeerIdentity *next_hop)
 112 {
 113   struct RoutingTrail *trail;
 114
 115   trail = GNUNET_CONTAINER_multihashmap_get (routing_table,
 116                                              trail_id);
 117   if (NULL == trail)
 118     return GNUNET_SYSERR;
 119   trail->next_hop = *next_hop;
 120   return GNUNET_OK;
 121 }
 122
 123
 124 /**
 125  * Get the next hop for trail corresponding to trail_id
 126  *
 127  * @param trail_id Trail id to be searched.
 128  * @return Next_hop if found
 129  *         NULL If next hop not found.
 130  */
 131 const struct GNUNET_PeerIdentity *
 132 GDS_ROUTING_get_next_hop (const struct GNUNET_HashCode *trail_id,
 133                           enum GDS_ROUTING_trail_direction trail_direction)
 134 {
 135   struct RoutingTrail *trail;
 136
 137   trail = GNUNET_CONTAINER_multihashmap_get (routing_table,
 138                                              trail_id);
 139   if (NULL == trail)
 140   {
 141     /* If a friend got disconnected and we removed all the entry from the
 142      routing table, then trail will be deleted and my identity will not know
 143      and when it tries to reach to that finger it fails. thats why
 144      assertion always fails in*/
 145     return NULL;
 146   }
 147   switch (trail_direction)
 148   {
 149     case GDS_ROUTING_SRC_TO_DEST:
 150       return &trail->next_hop;
 151     case GDS_ROUTING_DEST_TO_SRC:
 152       return &trail->prev_hop;
 153   }
 154   return NULL;
 155 }
 156
 157
 158 /**
 159  * Remove trail with trail_id
 160  * @param trail_id Trail id to be removed
 161  * @return #GNUNET_YES success
 162  *         #GNUNET_NO if entry not found.
 163  */
 164 int
 165 GDS_ROUTING_remove_trail (const struct GNUNET_HashCode *remove_trail_id)
 166 {
 167   struct RoutingTrail *remove_entry;
 168
 169   remove_entry = GNUNET_CONTAINER_multihashmap_get (routing_table,
 170                                                     remove_trail_id);
 171   if (NULL == remove_entry)
 172     return GNUNET_NO;
 173
 174   if (GNUNET_YES ==
 175       GNUNET_CONTAINER_multihashmap_remove (routing_table,
 176                                             remove_trail_id,
 177                                             remove_entry))
 178   {
 179     GNUNET_free (remove_entry);
 180     return GNUNET_YES;
 181   }
 182   return GNUNET_NO;
 183 }
 184
 185
 186 /**
 187  * Iterate over routing table and remove entries with value as part of any trail.
 188  *
 189  * @param cls closure
 190  * @param key current public key
 191  * @param value value in the hash map
 192  * @return #GNUNET_YES if we should continue to iterate,
 193  *         #GNUNET_NO if not.
 194  */
 195 static int
 196 remove_matching_trails (void *cls,
 197                         const struct GNUNET_HashCode *key,
 198                         void *value)
 199 {
 200   struct RoutingTrail *remove_trail = value;
 201   struct GNUNET_PeerIdentity *disconnected_peer = cls;
 202   struct GNUNET_HashCode trail_id = *key;
 203   struct GNUNET_PeerIdentity my_identity;
 204
 205   /* If disconnected_peer is next_hop, then send a trail teardown message through
 206    * prev_hop in direction from destination to source. */
 207   if (0 == GNUNET_CRYPTO_cmp_peer_identity (&remove_trail->next_hop,
 208                                             disconnected_peer))
 209   {
 210     my_identity = GDS_NEIGHBOURS_get_my_id ();
 211     if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
 212                                               &remove_trail->prev_hop))
 213     {
 214       GDS_NEIGHBOURS_send_trail_teardown (&trail_id,
 215                                           GDS_ROUTING_DEST_TO_SRC,
 216                                           &remove_trail->prev_hop);
 217     }
 218   }
 219
 220   /* If disconnected_peer is prev_hop, then send a trail teardown through
 221    * next_hop in direction from Source to Destination. */
 222   if (0 == GNUNET_CRYPTO_cmp_peer_identity (&remove_trail->prev_hop,
 223                                             disconnected_peer))
 224   {
 225     my_identity = GDS_NEIGHBOURS_get_my_id ();
 226
 227     if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
 228                                               &remove_trail->next_hop))
 229     {
 230       GDS_NEIGHBOURS_send_trail_teardown (&trail_id,
 231                                           GDS_ROUTING_SRC_TO_DEST,
 232                                           &remove_trail->next_hop);
 233     }
 234   }
 235
 236   GNUNET_assert (GNUNET_YES ==
 237                    GNUNET_CONTAINER_multihashmap_remove (routing_table,
 238                                                          &trail_id,
 239                                                          remove_trail));
 240   GNUNET_free (remove_trail);
 241   return GNUNET_YES;
 242 }
 243
 244 #if 0
 245 /**
 246  * TEST FUNCTION
 247  * Remove after using.
 248  */
 249 void
 250 GDS_ROUTING_test_print (void)
 251 {
 252   struct GNUNET_CONTAINER_MultiHashMapIterator *iter;
 253   struct RoutingTrail *trail;
 254   struct GNUNET_PeerIdentity print_peer;
 255   struct GNUNET_HashCode key_ret;
 256   int i;
 257
 258   struct GNUNET_PeerIdentity my_identity = GDS_NEIGHBOURS_get_my_id();
 259   print_peer = my_identity;
 260    FPRINTF (stderr,_("\nSUPU ***PRINTING ROUTING TABLE ***** of =%s"),GNUNET_i2s(&print_peer));
 261   iter =GNUNET_CONTAINER_multihashmap_iterator_create (routing_table);
 262   for (i = 0; i < GNUNET_CONTAINER_multihashmap_size(routing_table); i++)
 263   {
 264     if(GNUNET_YES == GNUNET_CONTAINER_multihashmap_iterator_next (iter,
 265                                                                   &key_ret,
 266                                                                   (const void **)&trail))
 267     {
 268       FPRINTF (stderr,_("\nSUPU %s, %s, %d, trail->trail_id = %s"),
 269               __FILE__, __func__,__LINE__, GNUNET_h2s(&trail->trail_id));
 270       GNUNET_memcpy (&print_peer, &trail->next_hop, sizeof (struct GNUNET_PeerIdentity));
 271       FPRINTF (stderr,_("\nSUPU %s, %s, %d, trail->next_hop = %s"),
 272               __FILE__, __func__,__LINE__, GNUNET_i2s(&print_peer));
 273       GNUNET_memcpy (&print_peer, &trail->prev_hop, sizeof (struct GNUNET_PeerIdentity));
 274       FPRINTF (stderr,_("\nSUPU %s, %s, %d, trail->prev_hop = %s"),
 275               __FILE__, __func__,__LINE__, GNUNET_i2s(&print_peer));
 276     }
 277   }
 278 }
 279 #endif
 280
 281 /**
 282  * Remove every trail where peer is either next_hop or prev_hop. Also send a
 283  * trail teardown message in direction of hop which is not disconnected.
 284  * @param peer Peer identity. Trail containing this peer should be removed.
 285  */
 286 int
 287 GDS_ROUTING_remove_trail_by_peer (const struct GNUNET_PeerIdentity *peer)
 288 {
 289   int ret;
 290
 291
 292   /* No entries in my routing table. */
 293   if (0 == GNUNET_CONTAINER_multihashmap_size(routing_table))
 294     return GNUNET_YES;
 295
 296   ret = GNUNET_CONTAINER_multihashmap_iterate (routing_table,
 297                                                &remove_matching_trails,
 298                                                (void *)peer);
 299   return ret;
 300 }
 301
 302
 303 /**
 304  * Add a new entry in routing table
 305  * @param new_trail_id
 306  * @param prev_hop
 307  * @param next_hop
 308  * @return #GNUNET_OK success
 309  *         #GNUNET_SYSERR in case new_trail_id already exists in the network
 310  *                         but with different prev_hop/next_hop
 311  */
 312 int
 313 GDS_ROUTING_add (const struct GNUNET_HashCode *new_trail_id,
 314                  const struct GNUNET_PeerIdentity *prev_hop,
 315                  const struct GNUNET_PeerIdentity *next_hop)
 316 {
 317   struct RoutingTrail *new_entry;
 318
 319   new_entry = GNUNET_new (struct RoutingTrail);
 320   new_entry->trail_id = *new_trail_id;
 321   new_entry->next_hop = *next_hop;
 322   new_entry->prev_hop = *prev_hop;
 323
 324   // FIXME: this leaks memory if the put fails!
 325   return GNUNET_CONTAINER_multihashmap_put (routing_table,
 326                                             &new_entry->trail_id,
 327                                             new_entry,
 328                                             GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY);
 329 }
 330
 331
 332 /**
 333  * Check if the size of routing table has crossed ROUTING_TABLE_THRESHOLD.
 334  * It means that I don't have any more space in my routing table and I can not
 335  * be part of any more trails till there is free space in my routing table.
 336  * @return #GNUNET_YES, if threshold crossed else #GNUNET_NO.
 337  */
 338 int
 339 GDS_ROUTING_threshold_reached (void)
 340 {
 341   return (GNUNET_CONTAINER_multihashmap_size(routing_table) >
 342           ROUTING_TABLE_THRESHOLD) ? GNUNET_YES:GNUNET_NO;
 343 }
 344
 345
 346 /**
 347  * Initialize routing subsystem.
 348  */
 349 void
 350 GDS_ROUTING_init (void)
 351 {
 352   routing_table = GNUNET_CONTAINER_multihashmap_create (ROUTING_TABLE_THRESHOLD * 4 / 3,
 353                                                         GNUNET_NO);
 354 }
 355
 356
 357 /**
 358  * Shutdown routing subsystem.
 359  */
 360 void
 361 GDS_ROUTING_done (void)
 362 {
 363   GNUNET_assert (0 == GNUNET_CONTAINER_multihashmap_size (routing_table));
 364   GNUNET_CONTAINER_multihashmap_destroy (routing_table);
 365 }
 366
 367 /* end of gnunet-service-xdht_routing.c */