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 /* TODO
  32  1. to understand if we really need all the four fields.
  33  2. if we can merge remove_peer and remove_trail
  34  3. do we need next_hop to uniquely identify a trail in remove_trail. */
  35
  36 /**
  37  * Maximum number of entries in routing table.
  38  */
  39 #define ROUTING_TABLE_THRESHOLD 64
  40
  41 /**
  42  * Routing table entry .
  43  */
  44 struct RoutingTrail
  45 {
  46   /**
  47    * Source peer .
  48    */
  49   struct GNUNET_PeerIdentity source;
  50
  51   /**
  52    * Destination peer.
  53    */
  54   struct GNUNET_PeerIdentity destination;
  55
  56   /**
  57    * The peer to which this request should be passed to.
  58    */
  59   struct GNUNET_PeerIdentity next_hop;
  60
  61   /**
  62    * Peer just before next hop in the trail.
  63    */
  64   struct GNUNET_PeerIdentity prev_hop;
  65
  66 };
  67
  68
  69 /**
  70  * Routing table of the peer
  71  */
  72 static struct GNUNET_CONTAINER_MultiPeerMap *routing_table;
  73
  74
  75 /**
  76  * Get next hop from the trail with source peer, destination peer and next hop
  77  * same as the argument to this function.
  78  * @param source_peer  Source peer of the trail.
  79  * @param destination_peer Destination peer of the trail.
  80  * @param prev_hop Previous hop of the trail.
  81  * @return #GNUNET_YES if we found the matching trail.
  82  *         #GNUNET_NO if we found no matching trail.
  83  */
  84 static int
  85 get_next_hop (struct RoutingTrail *trail,
  86               struct GNUNET_PeerIdentity *source_peer,
  87               struct GNUNET_PeerIdentity *destination_peer,
  88               const struct GNUNET_PeerIdentity *prev_hop)
  89 {
  90   if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(trail->source),source_peer))
  91   {
  92     if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(trail->prev_hop),prev_hop))
  93     {
  94       return GNUNET_YES;
  95     }
  96     else
  97       return GNUNET_NO;
  98   }
  99   return GNUNET_NO;
 100 }
 101
 102
 103 /**
 104  * FIXME: How to ensure that with only 3 fields also we have a unique trail.
 105  * in case of redundant routes we can have different next hop.
 106  * in that case we have to call this function on each entry of routing table
 107  * and from multiple next hop we return one. Here also we are going to return one.
 108  * URGENT.
 109  * Assumption - there can be only on one trail with all these fields. But if
 110  * we consider only 3 fields then it is possible that next hop is differet.
 111  * Update prev_hop field to source_peer. Trail from source peer to destination
 112  * peer is compressed such that I am the first friend in the trail.
 113  * @param source_peer Source of the trail.
 114  * @param destination_peer Destination of the trail.
 115  * @param prev_hop Peer before me in the trail.
 116  * @return #GNUNET_YES trail is updated.
 117  *         #GNUNET_NO, trail not found.
 118  */
 119 int
 120 GDS_ROUTING_trail_update (struct GNUNET_PeerIdentity *source_peer,
 121                           struct GNUNET_PeerIdentity *destination_peer,
 122                           struct GNUNET_PeerIdentity *prev_hop)
 123 {
 124   /* 1. find the trail corresponding to these values.
 125    2. update the prev hop to source peer. */
 126   struct RoutingTrail *trail;
 127   struct GNUNET_CONTAINER_MultiPeerMapIterator *iterator;
 128   int i;
 129
 130   iterator = GNUNET_CONTAINER_multipeermap_iterator_create (routing_table);
 131   for (i = 0; i< GNUNET_CONTAINER_multipeermap_size(routing_table); i++)
 132   {
 133     if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (iterator, NULL,
 134                                                                  (const void **)&trail))
 135     {
 136       if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(trail->destination), destination_peer))
 137       {
 138         if (GNUNET_YES == get_next_hop (trail, source_peer, destination_peer, prev_hop))
 139         {
 140           memcpy (&(trail->prev_hop), source_peer, sizeof (struct GNUNET_PeerIdentity));
 141           return GNUNET_YES;
 142         }
 143       }
 144     }
 145   }
 146   return GNUNET_NO;
 147 }
 148
 149
 150 /**
 151  * Find the next hop to send packet to.
 152  * @param source_peer Source of the trail.
 153  * @param destination_peer Destination of the trail.
 154  * @param prev_hop Previous hop in the trail.
 155  * @return Next hop in the trail from source to destination.
 156  */
 157 struct GNUNET_PeerIdentity *
 158 GDS_ROUTING_search (struct GNUNET_PeerIdentity *source_peer,
 159                     struct GNUNET_PeerIdentity *destination_peer,
 160                     const struct GNUNET_PeerIdentity *prev_hop)
 161 {
 162   struct RoutingTrail *trail;
 163   struct GNUNET_CONTAINER_MultiPeerMapIterator *iterator;
 164   int i;
 165
 166   iterator = GNUNET_CONTAINER_multipeermap_iterator_create (routing_table);
 167   for (i = 0; i< GNUNET_CONTAINER_multipeermap_size(routing_table); i++)
 168   {
 169     if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (iterator, NULL,
 170                                                                  (const void **)&trail))
 171     {
 172       if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(trail->destination), destination_peer))
 173       {
 174         if (GNUNET_YES == get_next_hop (trail, source_peer, destination_peer, prev_hop))
 175         {
 176           return &(trail->next_hop);
 177         }
 178       }
 179     }
 180   }
 181   GNUNET_CONTAINER_multipeermap_iterator_destroy (iterator);
 182   return NULL;
 183 }
 184
 185
 186 /**
 187  * Add a new entry to our routing table.
 188  * @param source peer Source of the trail.
 189  * @param destintation Destination of the trail.
 190  * @param next_hop Next peer to forward the message to reach the destination.
 191  * @return GNUNET_YES
 192  *         GNUNET_SYSERR If the number of routing entries crossed thershold.
 193  */
 194 int
 195 GDS_ROUTING_add (const struct GNUNET_PeerIdentity *source,
 196                  const struct GNUNET_PeerIdentity *dest,
 197                  const struct GNUNET_PeerIdentity *next_hop,
 198                  struct GNUNET_PeerIdentity *prev_hop)
 199 {
 200   struct RoutingTrail *new_routing_entry;
 201
 202   if (GNUNET_CONTAINER_multipeermap_size(routing_table) > ROUTING_TABLE_THRESHOLD)
 203     return GNUNET_SYSERR;
 204
 205   new_routing_entry = GNUNET_malloc (sizeof (struct RoutingTrail));
 206   memcpy (&(new_routing_entry->source) , source, sizeof (struct GNUNET_PeerIdentity));
 207   memcpy (&(new_routing_entry->next_hop), next_hop, sizeof (struct GNUNET_PeerIdentity));
 208   memcpy (&(new_routing_entry->destination), dest, sizeof (struct GNUNET_PeerIdentity));
 209   memcpy (&(new_routing_entry->prev_hop), prev_hop, sizeof (struct GNUNET_PeerIdentity));
 210
 211   GNUNET_assert (GNUNET_OK ==
 212     GNUNET_CONTAINER_multipeermap_put (routing_table,
 213                                        dest, new_routing_entry,
 214                                        GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE));
 215
 216   return GNUNET_YES;
 217 }
 218
 219
 220 /**
 221  * Iterate over routing table and remove entries for which peer is a part.
 222  * @param cls closure
 223  * @param key current public key
 224  * @param value value in the hash map
 225  * @return #GNUNET_YES if we should continue to
 226  *         iterate,
 227  *         #GNUNET_NO if not.
 228  */
 229 static int
 230 remove_routing_entry (void *cls,
 231                       const struct GNUNET_PeerIdentity *key,
 232                       void *value)
 233 {
 234   struct RoutingTrail *remove_entry = value;
 235   const struct GNUNET_PeerIdentity *disconnected_peer = cls;
 236
 237   if ((0 == GNUNET_CRYPTO_cmp_peer_identity (&(remove_entry->source), disconnected_peer)) ||
 238       (0 == GNUNET_CRYPTO_cmp_peer_identity (&(remove_entry->destination), disconnected_peer)) ||
 239       (0 == GNUNET_CRYPTO_cmp_peer_identity (&(remove_entry->next_hop), disconnected_peer)) ||
 240       (0 == GNUNET_CRYPTO_cmp_peer_identity (&(remove_entry->prev_hop), disconnected_peer)))
 241   {
 242     GNUNET_assert (GNUNET_YES ==
 243                    GNUNET_CONTAINER_multipeermap_remove (routing_table,
 244                                                          key,
 245                                                          remove_entry));
 246   }
 247   return GNUNET_YES;
 248 }
 249
 250
 251 /**
 252  * FIXME: add a return value.
 253  * Iterate over routing table and remove all entries for which peer is a part.
 254  * @param peer Peer to be searched for in the trail to remove that trail.
 255  */
 256 void
 257 GDS_ROUTING_remove_entry (const struct GNUNET_PeerIdentity *peer)
 258 {
 259   GNUNET_CONTAINER_multipeermap_iterate (routing_table, &remove_routing_entry,
 260                                         (void *)peer);
 261 }
 262
 263
 264 /**
 265  * In response to trail teardown message, remove the trail with source peer,
 266  * destination peer and next hop same as the argument to this function.
 267  * Assumption - there can be only one possible trail with these 4 values.
 268  * @param source_peer Source of the trail.
 269  * @param destination_peer Destination of the trail.
 270  * @param next_hop Next hop
 271  * @param prev_hop Previous hop.
 272  * @return #GNUNET_YES Matching trail deleted from routing table.
 273  *         #GNUNET_NO No matching trail found.
 274  *
 275  */
 276 int
 277 GDS_ROUTING_remove_trail (struct GNUNET_PeerIdentity *source_peer,
 278                           struct GNUNET_PeerIdentity *destination_peer,
 279                           const struct GNUNET_PeerIdentity *prev_hop)
 280 {
 281   struct RoutingTrail *trail;
 282   struct GNUNET_CONTAINER_MultiPeerMapIterator *iterator;
 283   int i;
 284
 285   iterator = GNUNET_CONTAINER_multipeermap_iterator_create (routing_table);
 286   for (i = 0; i< GNUNET_CONTAINER_multipeermap_size(routing_table); i++)
 287   {
 288     if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (iterator, NULL,
 289                                                                  (const void **)&trail))
 290     {
 291       if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(trail->destination), destination_peer))
 292       {
 293         GNUNET_assert (GNUNET_YES ==
 294                        GNUNET_CONTAINER_multipeermap_remove (routing_table,
 295                                                              &(trail->destination),
 296                                                              trail));
 297         return GNUNET_YES;
 298       }
 299     }
 300   }
 301   GNUNET_CONTAINER_multipeermap_iterator_destroy (iterator);
 302   return GNUNET_NO;
 303 }
 304
 305
 306
 307 /**
 308  * Check if the size of routing table has crossed threshold.
 309  * @return #GNUNET_YES, if threshold crossed else #GNUNET_NO.
 310  */
 311 int
 312 GDS_ROUTING_check_threshold ()
 313 {
 314   return (GNUNET_CONTAINER_multipeermap_size(routing_table) > ROUTING_TABLE_THRESHOLD) ?
 315           GNUNET_YES:GNUNET_NO;
 316 }
 317
 318
 319 /**
 320  * Initialize routing subsystem.
 321  */
 322 void
 323 GDS_ROUTING_init (void)
 324 {
 325   routing_table = GNUNET_CONTAINER_multipeermap_create (ROUTING_TABLE_THRESHOLD * 4 / 3,
 326                                                         GNUNET_NO);
 327 }
 328
 329 /**
 330  * ONLY FOR TESTING.
 331  */
 332 void
 333 GDS_ROUTING_print (void)
 334 {
 335   struct RoutingTrail *trail;
 336   struct GNUNET_CONTAINER_MultiPeerMapIterator *iterator;
 337   int i;
 338
 339   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Routing table entries \n");
 340   iterator = GNUNET_CONTAINER_multipeermap_iterator_create (routing_table);
 341   for (i = 0; i< GNUNET_CONTAINER_multipeermap_size(routing_table); i++)
 342   {
 343     if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (iterator, NULL,
 344                                                                  (const void **)&trail))
 345     {
 346       GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Routing trail source \n", GNUNET_i2s (&(trail->source)));
 347       GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Routing trail source \n", GNUNET_i2s (&(trail->destination)));
 348       GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Routing trail source \n", GNUNET_i2s (&(trail->next_hop)));
 349       GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Routing trail source \n", GNUNET_i2s (&(trail->prev_hop)));
 350     }
 351   }
 352
 353 }
 354 /**
 355  * FIXME: here you can have routing table with size 0, only when you delete
 356  * the entries correctly. Possible scenarios where we delete the entries are
 357  * 1. when one of my friend gets disconnected then I remove any trail (does not
 358  * matter if that friend is source, destination, next hop or previous hop).
 359  * 2. if I get a trail teardown message then I remove the entry.
 360  * Is there any other case that I may have missed?
 361  * Shutdown routing subsystem.
 362  */
 363 void
 364 GDS_ROUTING_done (void)
 365 {
 366   GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (routing_table));
 367   GNUNET_CONTAINER_multipeermap_destroy (routing_table);
 368 }
 369
 370 /* end of gnunet-service-xdht_routing.c */