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