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