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                                    struct GNUNET_PeerIdentity prev_hop)
  88 {
  89   struct RoutingTrail *trail;
  90
  91   trail = GNUNET_CONTAINER_multihashmap_get (routing_table, &trail_id);
  92
  93   if (NULL == trail)
  94     return GNUNET_SYSERR;
  95
  96   trail->prev_hop = prev_hop;
  97   return GNUNET_OK;
  98 }
  99
 100 /**
 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.
 104  * @param trail_id
 105  * @return #GNUNET_OK success
 106  *         #GNUNET_SYSERR in case no matching entry found in routing table.
 107  */
 108 int
 109 GDS_ROUTING_update_trail_next_hop (const struct GNUNET_HashCode trail_id,
 110                                    struct GNUNET_PeerIdentity next_hop)
 111 {
 112   struct RoutingTrail *trail;
 113
 114   trail = GNUNET_CONTAINER_multihashmap_get (routing_table, &trail_id);
 115
 116   if (NULL == trail)
 117
 118     return GNUNET_SYSERR;
 119
 120   trail->next_hop = next_hop;
 121   return GNUNET_OK;
 122 }
 123
 124 /**
 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.
 129  */
 130 struct GNUNET_PeerIdentity *
 131 GDS_ROUTING_get_next_hop (const struct GNUNET_HashCode trail_id,
 132                           enum GDS_ROUTING_trail_direction trail_direction)
 133 {
 134   struct RoutingTrail *trail;
 135
 136   trail = GNUNET_CONTAINER_multihashmap_get (routing_table, &trail_id);
 137   if (NULL == trail)
 138   {
 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*/
 143     return NULL;
 144   }
 145   switch (trail_direction)
 146   {
 147     case GDS_ROUTING_SRC_TO_DEST:
 148       return &(trail->next_hop);
 149     case GDS_ROUTING_DEST_TO_SRC:
 150       return &(trail->prev_hop);
 151   }
 152   return NULL;
 153 }
 154
 155
 156 /**
 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.
 161  */
 162 int
 163 GDS_ROUTING_remove_trail (const struct GNUNET_HashCode remove_trail_id)
 164 {
 165   struct RoutingTrail *remove_entry;
 166
 167   remove_entry = GNUNET_CONTAINER_multihashmap_get (routing_table, &remove_trail_id);
 168   if (NULL == remove_entry)
 169     return GNUNET_NO;
 170
 171   if (GNUNET_YES == GNUNET_CONTAINER_multihashmap_remove (routing_table,
 172                                                           &remove_trail_id,
 173                                                           remove_entry))
 174   {
 175     GNUNET_free (remove_entry);
 176     return GNUNET_YES;
 177   }
 178
 179   return GNUNET_NO;
 180 }
 181
 182
 183 /**
 184  * Iterate over routing table and remove entries with value as part of any trail.
 185  *
 186  * @param cls closure
 187  * @param key current public key
 188  * @param value value in the hash map
 189  * @return #GNUNET_YES if we should continue to iterate,
 190  *         #GNUNET_NO if not.
 191  */
 192 static int remove_matching_trails (void *cls,
 193                                    const struct GNUNET_HashCode *key,
 194                                    void *value)
 195 {
 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;
 200
 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,
 204                                             disconnected_peer))
 205   {
 206     my_identity = GDS_NEIGHBOURS_get_my_id ();
 207     if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
 208                                               &remove_trail->prev_hop))
 209     {
 210       GDS_NEIGHBOURS_send_trail_teardown (&trail_id,
 211                                           GDS_ROUTING_DEST_TO_SRC,
 212                                           &remove_trail->prev_hop);
 213     }
 214   }
 215
 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,
 219                                             disconnected_peer))
 220   {
 221     my_identity = GDS_NEIGHBOURS_get_my_id ();
 222
 223     if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
 224                                               &remove_trail->next_hop))
 225     {
 226       GDS_NEIGHBOURS_send_trail_teardown (&trail_id,
 227                                           GDS_ROUTING_SRC_TO_DEST,
 228                                           &remove_trail->next_hop);
 229     }
 230   }
 231
 232   GNUNET_assert (GNUNET_YES ==
 233                    GNUNET_CONTAINER_multihashmap_remove (routing_table,
 234                                                          &trail_id,
 235                                                          remove_trail));
 236   GNUNET_free (remove_trail);
 237   return GNUNET_YES;
 238 }
 239
 240 #if 0
 241 /**
 242  * TEST FUNCTION
 243  * Remove after using.
 244  */
 245 void
 246 GDS_ROUTING_test_print (void)
 247 {
 248   struct GNUNET_CONTAINER_MultiHashMapIterator *iter;
 249   struct RoutingTrail *trail;
 250   struct GNUNET_PeerIdentity print_peer;
 251   struct GNUNET_HashCode key_ret;
 252   int i;
 253
 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++)
 259   {
 260     if(GNUNET_YES == GNUNET_CONTAINER_multihashmap_iterator_next (iter,
 261                                                                   &key_ret,
 262                                                                   (const void **)&trail))
 263     {
 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));
 272     }
 273   }
 274 }
 275 #endif
 276
 277 /**
 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.
 281  */
 282 int
 283 GDS_ROUTING_remove_trail_by_peer (const struct GNUNET_PeerIdentity *peer)
 284 {
 285   int ret;
 286
 287
 288   /* No entries in my routing table. */
 289   if (0 == GNUNET_CONTAINER_multihashmap_size(routing_table))
 290     return GNUNET_YES;
 291
 292   ret = GNUNET_CONTAINER_multihashmap_iterate (routing_table,
 293                                                &remove_matching_trails,
 294                                                (void *)peer);
 295   return ret;
 296 }
 297
 298
 299 /**
 300  * Add a new entry in routing table
 301  * @param new_trail_id
 302  * @param prev_hop
 303  * @param next_hop
 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
 307  */
 308 int
 309 GDS_ROUTING_add (struct GNUNET_HashCode new_trail_id,
 310                  struct GNUNET_PeerIdentity prev_hop,
 311                  struct GNUNET_PeerIdentity next_hop)
 312 {
 313   struct RoutingTrail *new_entry;
 314
 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;
 319
 320
 321   return GNUNET_CONTAINER_multihashmap_put (routing_table,
 322                                             &new_trail_id, new_entry,
 323                                             GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY);
 324
 325 }
 326
 327
 328 /**
 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.
 333  */
 334 int
 335 GDS_ROUTING_threshold_reached (void)
 336 {
 337   return (GNUNET_CONTAINER_multihashmap_size(routing_table) >
 338           ROUTING_TABLE_THRESHOLD) ? GNUNET_YES:GNUNET_NO;
 339 }
 340
 341
 342 /**
 343  * Initialize routing subsystem.
 344  */
 345 void
 346 GDS_ROUTING_init (void)
 347 {
 348   routing_table = GNUNET_CONTAINER_multihashmap_create (ROUTING_TABLE_THRESHOLD * 4 / 3,
 349                                                         GNUNET_NO);
 350 }
 351
 352
 353 /**
 354  * Shutdown routing subsystem.
 355  */
 356 void
 357 GDS_ROUTING_done (void)
 358 {
 359   GNUNET_assert (0 == GNUNET_CONTAINER_multihashmap_size (routing_table));
 360   GNUNET_CONTAINER_multihashmap_destroy (routing_table);
 361 }
 362
 363 /* end of gnunet-service-xdht_routing.c */