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                           const 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  * It can happen that a particular peer removed the entry because one of the peers
 152  * (source, destination, next , prev) was friend which got disconnected. So,
 153  * no matching trail is found. In this case we return NULL. Its on calling function
 154  * to handle the return value.
 155  * Find the next hop to send packet to.
 156  * @param source_peer Source of the trail.
 157  * @param destination_peer Destination of the trail.
 158  * @param prev_hop Previous hop in the trail.
 159  * @return Next hop in the trail from source to destination.
 160  *         NULL in case no matching trail found in routing table.
 161  */
 162 struct GNUNET_PeerIdentity *
 163 GDS_ROUTING_search (struct GNUNET_PeerIdentity *source_peer,
 164                     struct GNUNET_PeerIdentity *destination_peer,
 165                     const struct GNUNET_PeerIdentity *prev_hop)
 166 {
 167   struct RoutingTrail *trail;
 168   struct GNUNET_CONTAINER_MultiPeerMapIterator *iterator;
 169   int i;
 170
 171   iterator = GNUNET_CONTAINER_multipeermap_iterator_create (routing_table);
 172   for (i = 0; i< GNUNET_CONTAINER_multipeermap_size(routing_table); i++)
 173   {
 174     if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (iterator, NULL,
 175                                                                  (const void **)&trail))
 176     {
 177       if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(trail->destination), destination_peer))
 178       {
 179         if (GNUNET_YES == get_next_hop (trail, source_peer, destination_peer, prev_hop))
 180         {
 181           return &(trail->next_hop);
 182         }
 183       }
 184     }
 185   }
 186   GNUNET_CONTAINER_multipeermap_iterator_destroy (iterator);
 187   return NULL;
 188 }
 189
 190
 191 /**
 192  * FIXME: first search in routing table and if same entry found then don't add
 193  * it.
 194  * Add a new entry to our routing table.
 195  * @param source peer Source of the trail.
 196  * @param destintation Destination of the trail.
 197  * @param next_hop Next peer to forward the message to reach the destination.
 198  * @return GNUNET_YES
 199  *         GNUNET_SYSERR If the number of routing entries crossed thershold.
 200  */
 201 int
 202 GDS_ROUTING_add (const struct GNUNET_PeerIdentity *source,
 203                  const struct GNUNET_PeerIdentity *dest,
 204                  const struct GNUNET_PeerIdentity *next_hop,
 205                  const struct GNUNET_PeerIdentity *prev_hop)
 206 {
 207   struct RoutingTrail *new_routing_entry;
 208
 209   if (GNUNET_CONTAINER_multipeermap_size(routing_table) > ROUTING_TABLE_THRESHOLD)
 210     return GNUNET_SYSERR;
 211
 212   new_routing_entry = GNUNET_malloc (sizeof (struct RoutingTrail));
 213   memcpy (&(new_routing_entry->source) , source, sizeof (struct GNUNET_PeerIdentity));
 214   memcpy (&(new_routing_entry->next_hop), next_hop, sizeof (struct GNUNET_PeerIdentity));
 215   memcpy (&(new_routing_entry->destination), dest, sizeof (struct GNUNET_PeerIdentity));
 216   memcpy (&(new_routing_entry->prev_hop), prev_hop, sizeof (struct GNUNET_PeerIdentity));
 217
 218   GNUNET_assert (GNUNET_OK ==
 219     GNUNET_CONTAINER_multipeermap_put (routing_table,
 220                                        dest, new_routing_entry,
 221                                        GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE));
 222
 223   return GNUNET_YES;
 224 }
 225
 226
 227 /**
 228  * Iterate over routing table and remove entries for which peer is a part.
 229  * @param cls closure
 230  * @param key current public key
 231  * @param value value in the hash map
 232  * @return #GNUNET_YES if we should continue to
 233  *         iterate,
 234  *         #GNUNET_NO if not.
 235  */
 236 static int
 237 remove_routing_entry (void *cls,
 238                       const struct GNUNET_PeerIdentity *key,
 239                       void *value)
 240 {
 241   struct RoutingTrail *remove_entry = value;
 242   const struct GNUNET_PeerIdentity *disconnected_peer = cls;
 243
 244   if ((0 == GNUNET_CRYPTO_cmp_peer_identity (&(remove_entry->source), disconnected_peer)) ||
 245       (0 == GNUNET_CRYPTO_cmp_peer_identity (&(remove_entry->destination), disconnected_peer)) ||
 246       (0 == GNUNET_CRYPTO_cmp_peer_identity (&(remove_entry->next_hop), disconnected_peer)) ||
 247       (0 == GNUNET_CRYPTO_cmp_peer_identity (&(remove_entry->prev_hop), disconnected_peer)))
 248   {
 249     GNUNET_assert (GNUNET_YES ==
 250                    GNUNET_CONTAINER_multipeermap_remove (routing_table,
 251                                                          key,
 252                                                          remove_entry));
 253   }
 254   return GNUNET_YES;
 255 }
 256
 257
 258 /**
 259  * FIXME: add a return value.
 260  * Iterate over routing table and remove all entries for which peer is a part.
 261  * @param peer Peer to be searched for in the trail to remove that trail.
 262  */
 263 void
 264 GDS_ROUTING_remove_entry (const struct GNUNET_PeerIdentity *peer)
 265 {
 266   GNUNET_CONTAINER_multipeermap_iterate (routing_table, &remove_routing_entry,
 267                                         (void *)peer);
 268 }
 269
 270
 271 /**
 272  * In response to trail teardown message, remove the trail with source peer,
 273  * destination peer and next hop same as the argument to this function.
 274  * Assumption - there can be only one possible trail with these 4 values.
 275  * @param source_peer Source of the trail.
 276  * @param destination_peer Destination of the trail.
 277  * @param next_hop Next hop
 278  * @param prev_hop Previous hop.
 279  * @return #GNUNET_YES Matching trail deleted from routing table.
 280  *         #GNUNET_NO No matching trail found.
 281  *
 282  */
 283 int
 284 GDS_ROUTING_remove_trail (struct GNUNET_PeerIdentity *source_peer,
 285                           struct GNUNET_PeerIdentity *destination_peer,
 286                           const struct GNUNET_PeerIdentity *prev_hop)
 287 {
 288   struct RoutingTrail *trail;
 289   struct GNUNET_CONTAINER_MultiPeerMapIterator *iterator;
 290   int i;
 291
 292   iterator = GNUNET_CONTAINER_multipeermap_iterator_create (routing_table);
 293   for (i = 0; i< GNUNET_CONTAINER_multipeermap_size(routing_table); i++)
 294   {
 295     if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (iterator, NULL,
 296                                                                  (const void **)&trail))
 297     {
 298       if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(trail->destination), destination_peer))
 299       {
 300         GNUNET_assert (GNUNET_YES ==
 301                        GNUNET_CONTAINER_multipeermap_remove (routing_table,
 302                                                              &(trail->destination),
 303                                                              trail));
 304         return GNUNET_YES;
 305       }
 306     }
 307   }
 308   GNUNET_CONTAINER_multipeermap_iterator_destroy (iterator);
 309   return GNUNET_NO;
 310 }
 311
 312
 313
 314 /**
 315  * Check if the size of routing table has crossed threshold.
 316  * @return #GNUNET_YES, if threshold crossed else #GNUNET_NO.
 317  */
 318 int
 319 GDS_ROUTING_check_threshold ()
 320 {
 321   return (GNUNET_CONTAINER_multipeermap_size(routing_table) > ROUTING_TABLE_THRESHOLD) ?
 322           GNUNET_YES:GNUNET_NO;
 323 }
 324
 325
 326 /**
 327  * Initialize routing subsystem.
 328  */
 329 void
 330 GDS_ROUTING_init (void)
 331 {
 332   routing_table = GNUNET_CONTAINER_multipeermap_create (ROUTING_TABLE_THRESHOLD * 4 / 3,
 333                                                         GNUNET_NO);
 334 }
 335
 336
 337 /**
 338  * FIXME: here you can have routing table with size 0, only when you delete
 339  * the entries correctly. Possible scenarios where we delete the entries are
 340  * 1. when one of my friend gets disconnected then I remove any trail (does not
 341  * matter if that friend is source, destination, next hop or previous hop).
 342  * 2. if I get a trail teardown message then I remove the entry.
 343  * Is there any other case that I may have missed?
 344  * Shutdown routing subsystem.
 345  */
 346 void
 347 GDS_ROUTING_done (void)
 348 {
 349   GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (routing_table));
 350   GNUNET_CONTAINER_multipeermap_destroy (routing_table);
 351 }
 352
 353 /* end of gnunet-service-xdht_routing.c */