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  * Number of requests we track at most (for routing replies).
  38  */
  39 #define DHT_MAX_RECENT (1024 * 16)
  40
  41 /**
  42  * Maximum number of entries in routing table.
  43  */
  44 #define ROUTING_TABLE_THRESHOLD 64
  45
  46 /**
  47  * Routing table entry .
  48  */
  49 struct RoutingTrail
  50 {
  51   /**
  52    * Source peer .
  53    */
  54   struct GNUNET_PeerIdentity source;
  55
  56   /**
  57    * Destination peer.
  58    */
  59   struct GNUNET_PeerIdentity destination;
  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
  74 /**
  75  * Routing table of the peer
  76  */
  77 static struct GNUNET_CONTAINER_MultiPeerMap *routing_table;
  78
  79 /**
  80  * Iterate over routing table and remove entries for which peer is a part.
  81  * @param cls closure
  82  * @param key current public key
  83  * @param value value in the hash map
  84  * @return #GNUNET_YES if we should continue to
  85  *         iterate,
  86  *         #GNUNET_NO if not.
  87  */
  88 static int
  89 remove_routing_entry (void *cls,
  90                       const struct GNUNET_PeerIdentity *key,
  91                       void *value)
  92 {
  93   struct RoutingTrail *remove_entry = value;
  94   const struct GNUNET_PeerIdentity *disconnected_peer = cls;
  95
  96   if ((0 == GNUNET_CRYPTO_cmp_peer_identity (&(remove_entry->source), disconnected_peer)) ||
  97       (0 == GNUNET_CRYPTO_cmp_peer_identity (&(remove_entry->destination), disconnected_peer)) ||
  98       (0 == GNUNET_CRYPTO_cmp_peer_identity (&(remove_entry->next_hop), disconnected_peer)) ||
  99       (0 == GNUNET_CRYPTO_cmp_peer_identity (&(remove_entry->prev_hop), disconnected_peer)))
 100   {
 101     GNUNET_assert (GNUNET_YES ==
 102                    GNUNET_CONTAINER_multipeermap_remove (routing_table,
 103                                                          key,
 104                                                          remove_entry));
 105   }
 106   return GNUNET_YES;
 107 }
 108
 109
 110 /**
 111  * Iterate over multiple entries for same destination value and get
 112  * the correct next hop.
 113  * @param cls struct RoutingTrail
 114  * @param key Destination identity
 115  * @param value struct RoutingTrail
 116  * @return #GNUNET_YES to continue looking, #GNUNET_NO if we found the next hop
 117  */
 118 int
 119 get_next_hop (void *cls, const struct GNUNET_PeerIdentity *key, void *value)
 120 {
 121   /* Here you should match if source, prev hop matches if yes then send
 122    GNUNET_NO as you don't need to check more entries. */
 123   struct RoutingTrail *request = cls;
 124   struct RoutingTrail *existing_entry = (struct RoutingTrail *)value;
 125
 126   if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(request->source), &(existing_entry->source)))
 127   {
 128     if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(request->prev_hop), &(existing_entry->prev_hop)))
 129     {
 130       memcpy (&(request->next_hop), &(existing_entry->next_hop), sizeof (struct GNUNET_PeerIdentity));
 131       return GNUNET_YES;
 132     }
 133   }
 134   return GNUNET_NO;
 135 }
 136
 137
 138 /**
 139  * Add a new entry to our routing table.
 140  * @param source peer Source of the trail.
 141  * @param destintation Destination of the trail.
 142  * @param next_hop Next peer to forward the message to reach the destination.
 143  * @return GNUNET_YES
 144  *         GNUNET_SYSERR If the number of routing entries crossed thershold.
 145  */
 146 int
 147 GDS_ROUTING_add (const struct GNUNET_PeerIdentity *source,
 148                  const struct GNUNET_PeerIdentity *dest,
 149                  const struct GNUNET_PeerIdentity *next_hop,
 150                  struct GNUNET_PeerIdentity *prev_hop)
 151 {
 152   struct RoutingTrail *new_routing_entry;
 153
 154   if (GNUNET_CONTAINER_multipeermap_size(routing_table) > ROUTING_TABLE_THRESHOLD)
 155     return GNUNET_SYSERR;
 156
 157   new_routing_entry = GNUNET_malloc (sizeof (struct RoutingTrail));
 158   memcpy (&(new_routing_entry->source) , source, sizeof (struct GNUNET_PeerIdentity));
 159   memcpy (&(new_routing_entry->next_hop), next_hop, sizeof (struct GNUNET_PeerIdentity));
 160   memcpy (&(new_routing_entry->destination), dest, sizeof (struct GNUNET_PeerIdentity));
 161   memcpy (&(new_routing_entry->prev_hop), prev_hop, sizeof (struct GNUNET_PeerIdentity));
 162
 163   GNUNET_assert (GNUNET_OK ==
 164     GNUNET_CONTAINER_multipeermap_put (routing_table,
 165                                        dest, new_routing_entry,
 166                                        GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE));
 167
 168   return GNUNET_YES;
 169 }
 170
 171
 172 /**
 173  * Iterate over routing table and remove entries for which peer is a part.
 174  * @param peer
 175  * @return
 176  */
 177 void
 178 GDS_ROUTING_remove_entry (const struct GNUNET_PeerIdentity *peer)
 179 {
 180   GNUNET_CONTAINER_multipeermap_iterate (routing_table, &remove_routing_entry,
 181                                          (void *)peer);
 182 }
 183
 184
 185 /** FIXME:TODO URGNET  Need to understand if we need next hop to uniquely identify an entry
 186  * in routing table or not.
 187  * Remove the trail as result of trail tear down message.
 188  * @param source_peer Source of the trail.
 189  * @param destination_peer Destination of the trail.
 190  * @param next_hop Next hop
 191  * @param prev_hop Previous hop.
 192  */
 193 int
 194 GDS_ROUTING_remove_trail (struct GNUNET_PeerIdentity *source_peer,
 195                           struct GNUNET_PeerIdentity *destination_peer,
 196                           const struct GNUNET_PeerIdentity *prev_hop)
 197 {
 198   return GNUNET_NO;
 199 }
 200
 201 /**
 202  * Find the next hop to send packet to.
 203  * @param source_peer Source of the trail.
 204  * @param destination_peer Destination of the trail.
 205  * @param prev_hop Previous hop in the trail.
 206  * @return Next hop in the trail from source to destination.
 207  */
 208 struct GNUNET_PeerIdentity *
 209 GDS_ROUTING_search(struct GNUNET_PeerIdentity *source_peer,
 210                    struct GNUNET_PeerIdentity *destination_peer,
 211                    const struct GNUNET_PeerIdentity *prev_hop)
 212 {
 213   struct RoutingTrail *trail;
 214   trail = GNUNET_malloc (sizeof (struct RoutingTrail));
 215   memcpy (&(trail->destination), destination_peer, sizeof (struct GNUNET_PeerIdentity));
 216   memcpy (&(trail->source), source_peer, sizeof (struct GNUNET_PeerIdentity));
 217   memcpy (&(trail->prev_hop), prev_hop, sizeof (struct GNUNET_PeerIdentity));
 218
 219   GNUNET_CONTAINER_multipeermap_get_multiple (routing_table, destination_peer,
 220                                               get_next_hop, trail);
 221   if(trail != NULL)
 222     return &(trail->next_hop);
 223   else
 224     return NULL;
 225 }
 226
 227
 228 /**
 229  * FIXME:URGENT:Better name.
 230  * Check if the size of routing table has crossed threshold.
 231  * @return #GNUNET_YES, if threshold crossed else #GNUNET_NO.
 232  */
 233 int
 234 GDS_ROUTING_check_threshold ()
 235 {
 236   int ret;
 237   ret = (GNUNET_CONTAINER_multipeermap_size(routing_table) > ROUTING_TABLE_THRESHOLD) ? GNUNET_YES:GNUNET_NO;
 238   return ret;
 239 }
 240
 241
 242 /**
 243  * Initialize routing subsystem.
 244  */
 245 void
 246 GDS_ROUTING_init (void)
 247 {
 248   routing_table = GNUNET_CONTAINER_multipeermap_create (DHT_MAX_RECENT * 4 / 3, GNUNET_NO);
 249 }
 250
 251
 252 /**
 253  * Shutdown routing subsystem.
 254  */
 255 void
 256 GDS_ROUTING_done (void)
 257 {
 258   GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (routing_table));
 259   GNUNET_CONTAINER_multipeermap_destroy (routing_table);
 260 }
 261
 262 /* end of gnunet-service-xdht_routing.c */