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