src/dht/gnunet-service-xdht_routing.c

   1 /*
   2      This file is part of GNUnet.
   3      (C) 2011 - 2014 Christian Grothoff (and other contributing authors)
   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., 59 Temple Place - Suite 330,
  18      Boston, MA 02111-1307, 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 1000
  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
 138   if (NULL == trail)
 139   {
 140     /* If a friend got disconnected and we removed all the entry from the
 141      routing table, then trail will be deleted and my identity will not know
 142      and when it tries to reach to that finger it fails. thats why
 143      assertion always fails in*/
 144     return NULL;
 145   }
 146   switch (trail_direction)
 147   {
 148     case GDS_ROUTING_SRC_TO_DEST:
 149       return &(trail->next_hop);
 150     case GDS_ROUTING_DEST_TO_SRC:
 151       return &(trail->prev_hop);
 152   }
 153   return NULL;
 154 }
 155
 156
 157 /**
 158  * Remove trail with trail_id
 159  * @param trail_id Trail id to be removed
 160  * @return #GNUNET_YES success
 161  *         #GNUNET_NO if entry not found.
 162  */
 163 int
 164 GDS_ROUTING_remove_trail (const struct GNUNET_HashCode remove_trail_id)
 165 {
 166   struct RoutingTrail *remove_entry;
 167
 168   remove_entry = GNUNET_CONTAINER_multihashmap_get (routing_table, &remove_trail_id);
 169
 170   if (NULL == remove_entry)
 171     return GNUNET_NO;
 172
 173   if (GNUNET_YES == GNUNET_CONTAINER_multihashmap_remove (routing_table,
 174                                                           &remove_trail_id,
 175                                                           remove_entry))
 176   {
 177     GNUNET_free (remove_entry);
 178     return GNUNET_YES;
 179   }
 180
 181   return GNUNET_NO;
 182 }
 183
 184
 185 /**
 186  * Iterate over routing table and remove entries with value as part of any trail.
 187  *
 188  * @param cls closure
 189  * @param key current public key
 190  * @param value value in the hash map
 191  * @return #GNUNET_YES if we should continue to iterate,
 192  *         #GNUNET_NO if not.
 193  */
 194 static int remove_matching_trails (void *cls,
 195                                    const struct GNUNET_HashCode *key,
 196                                    void *value)
 197 {
 198   struct RoutingTrail *remove_trail = value;
 199   struct GNUNET_PeerIdentity *disconnected_peer = cls;
 200   struct GNUNET_HashCode trail_id = *key;
 201   struct GNUNET_PeerIdentity my_identity;
 202
 203   /* If disconnected_peer is next_hop, then send a trail teardown message through
 204    * prev_hop in direction from destination to source. */
 205   if (0 == GNUNET_CRYPTO_cmp_peer_identity (&remove_trail->next_hop,
 206                                             disconnected_peer))
 207   {
 208     my_identity = GDS_NEIGHBOURS_get_my_id ();
 209     if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
 210                                               &remove_trail->prev_hop))
 211     {
 212       GDS_NEIGHBOURS_send_trail_teardown (trail_id,
 213                                           GDS_ROUTING_DEST_TO_SRC,
 214                                           remove_trail->prev_hop);
 215     }
 216   }
 217
 218   /* If disconnected_peer is prev_hop, then send a trail teardown through
 219    * next_hop in direction from Source to Destination. */
 220   if (0 == GNUNET_CRYPTO_cmp_peer_identity (&remove_trail->prev_hop,
 221                                             disconnected_peer))
 222   {
 223     my_identity = GDS_NEIGHBOURS_get_my_id ();
 224
 225     if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
 226                                               &remove_trail->next_hop))
 227     {
 228       GDS_NEIGHBOURS_send_trail_teardown (trail_id,
 229                                           GDS_ROUTING_SRC_TO_DEST,
 230                                           remove_trail->next_hop);
 231     }
 232   }
 233
 234   GNUNET_assert (GNUNET_YES ==
 235                    GNUNET_CONTAINER_multihashmap_remove (routing_table,
 236                                                          &trail_id,
 237                                                          remove_trail));
 238   GNUNET_free (remove_trail);
 239   return GNUNET_YES;
 240 }
 241
 242 #if 0
 243 /**
 244  * TEST FUNCTION
 245  * Remove after using.
 246  */
 247 void
 248 GDS_ROUTING_test_print (void)
 249 {
 250   struct GNUNET_CONTAINER_MultiHashMapIterator *iter;
 251   struct RoutingTrail *trail;
 252   struct GNUNET_PeerIdentity print_peer;
 253   struct GNUNET_HashCode key_ret;
 254   int i;
 255
 256   struct GNUNET_PeerIdentity my_identity = GDS_NEIGHBOURS_get_my_id();
 257   print_peer = my_identity;
 258    FPRINTF (stderr,_("\nSUPU ***PRINTING ROUTING TABLE ***** of =%s"),GNUNET_i2s(&print_peer));
 259   iter =GNUNET_CONTAINER_multihashmap_iterator_create (routing_table);
 260   for (i = 0; i < GNUNET_CONTAINER_multihashmap_size(routing_table); i++)
 261   {
 262     if(GNUNET_YES == GNUNET_CONTAINER_multihashmap_iterator_next (iter,
 263                                                                   &key_ret,
 264                                                                   (const void **)&trail))
 265     {
 266       FPRINTF (stderr,_("\nSUPU %s, %s, %d, trail->trail_id = %s"),
 267               __FILE__, __func__,__LINE__, GNUNET_h2s(&trail->trail_id));
 268       memcpy (&print_peer, &trail->next_hop, sizeof (struct GNUNET_PeerIdentity));
 269       FPRINTF (stderr,_("\nSUPU %s, %s, %d, trail->next_hop = %s"),
 270               __FILE__, __func__,__LINE__, GNUNET_i2s(&print_peer));
 271       memcpy (&print_peer, &trail->prev_hop, sizeof (struct GNUNET_PeerIdentity));
 272       FPRINTF (stderr,_("\nSUPU %s, %s, %d, trail->prev_hop = %s"),
 273               __FILE__, __func__,__LINE__, GNUNET_i2s(&print_peer));
 274     }
 275   }
 276 }
 277 #endif
 278
 279 /**
 280  * Remove every trail where peer is either next_hop or prev_hop. Also send a
 281  * trail teardown message in direction of hop which is not disconnected.
 282  * @param peer Peer identity. Trail containing this peer should be removed.
 283  */
 284 int
 285 GDS_ROUTING_remove_trail_by_peer (const struct GNUNET_PeerIdentity *peer)
 286 {
 287   int ret;
 288
 289
 290   /* No entries in my routing table. */
 291   if (0 == GNUNET_CONTAINER_multihashmap_size(routing_table))
 292     return GNUNET_YES;
 293
 294   ret = GNUNET_CONTAINER_multihashmap_iterate (routing_table,
 295                                                &remove_matching_trails,
 296                                                (void *)peer);
 297   return ret;
 298 }
 299
 300
 301 /**
 302  * Add a new entry in routing table
 303  * @param new_trail_id
 304  * @param prev_hop
 305  * @param next_hop
 306  * @return #GNUNET_OK success
 307  *         #GNUNET_SYSERR in case new_trail_id already exists in the network
 308  *                         but with different prev_hop/next_hop
 309  */
 310 int
 311 GDS_ROUTING_add (struct GNUNET_HashCode new_trail_id,
 312                  struct GNUNET_PeerIdentity prev_hop,
 313                  struct GNUNET_PeerIdentity next_hop)
 314 {
 315   struct RoutingTrail *new_entry;
 316
 317   new_entry = GNUNET_new (struct RoutingTrail);
 318   new_entry->trail_id = new_trail_id;
 319   new_entry->next_hop = next_hop;
 320   new_entry->prev_hop = prev_hop;
 321
 322
 323   return GNUNET_CONTAINER_multihashmap_put (routing_table,
 324                                             &new_trail_id, new_entry,
 325                                             GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY);
 326
 327 }
 328
 329
 330 /**
 331  * Check if the size of routing table has crossed ROUTING_TABLE_THRESHOLD.
 332  * It means that I don't have any more space in my routing table and I can not
 333  * be part of any more trails till there is free space in my routing table.
 334  * @return #GNUNET_YES, if threshold crossed else #GNUNET_NO.
 335  */
 336 int
 337 GDS_ROUTING_threshold_reached (void)
 338 {
 339   return (GNUNET_CONTAINER_multihashmap_size(routing_table) >
 340           ROUTING_TABLE_THRESHOLD) ? GNUNET_YES:GNUNET_NO;
 341 }
 342
 343
 344 /**
 345  * Initialize routing subsystem.
 346  */
 347 void
 348 GDS_ROUTING_init (void)
 349 {
 350   routing_table = GNUNET_CONTAINER_multihashmap_create (ROUTING_TABLE_THRESHOLD * 4 / 3,
 351                                                         GNUNET_NO);
 352 }
 353
 354
 355 /**
 356  * Shutdown routing subsystem.
 357  */
 358 void
 359 GDS_ROUTING_done (void)
 360 {
 361   GNUNET_assert (0 == GNUNET_CONTAINER_multihashmap_size (routing_table));
 362   GNUNET_CONTAINER_multihashmap_destroy (routing_table);
 363 }
 364
 365 /* end of gnunet-service-xdht_routing.c */