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  * Routing table entry .
  52  */
  53 struct RoutingTrail
  54 {
  55   /**
  56    * Global Unique identifier of the trail.
  57    */
  58   struct GNUNET_HashCode trail_id;
  59
  60   /**
  61    * The peer to which this request should be passed to.
  62    */
  63   struct GNUNET_PeerIdentity next_hop;
  64
  65   /**
  66    * Peer just before next hop in the trail.
  67    */
  68   struct GNUNET_PeerIdentity prev_hop;
  69 };
  70
  71 /**
  72  * Routing table of the peer
  73  */
  74 static struct GNUNET_CONTAINER_MultiHashMap *routing_table;
  75
  76 /**
  77  * Update the prev. hop of the trail. Call made by trail teardown where
  78  * if you are the first friend now in the trail then you need to update
  79  * your prev. hop.
  80  * @param trail_id
  81  * @return #GNUNET_OK success
  82  *         #GNUNET_SYSERR in case no matching entry found in routing table.
  83  */
  84 int
  85 GDS_ROUTING_update_trail_prev_hop (const struct GNUNET_HashCode trail_id,
  86                                    struct GNUNET_PeerIdentity prev_hop)
  87 {
  88   struct RoutingTrail *trail;
  89
  90   trail = GNUNET_CONTAINER_multihashmap_get (routing_table, &trail_id);
  91
  92   if (NULL == trail)
  93     return GNUNET_SYSERR;
  94
  95   trail->prev_hop = prev_hop;
  96   return GNUNET_OK;
  97 }
  98
  99
 100
 101 /**
 102  * Get the next hop for trail corresponding to trail_id
 103  * @param trail_id Trail id to be searched.
 104  * @return Next_hop if found
 105  *         NULL If next hop not found.
 106  */
 107 struct GNUNET_PeerIdentity *
 108 GDS_ROUTING_get_next_hop (const struct GNUNET_HashCode trail_id,
 109                           enum GDS_ROUTING_trail_direction trail_direction)
 110 {
 111   struct RoutingTrail *trail;
 112
 113   trail = GNUNET_CONTAINER_multihashmap_get (routing_table, &trail_id);
 114
 115   if (NULL == trail)
 116     return NULL;
 117
 118   switch (trail_direction)
 119   {
 120     case GDS_ROUTING_SRC_TO_DEST:
 121       return &(trail->next_hop);
 122     case GDS_ROUTING_DEST_TO_SRC:
 123       return &(trail->prev_hop);
 124   }
 125   return NULL;
 126 }
 127
 128
 129 /**
 130  * Remove trail with trail_id
 131  * @param trail_id Trail id to be removed
 132  * @return #GNUNET_YES success
 133  *         #GNUNET_NO if entry not found.
 134  */
 135 int
 136 GDS_ROUTING_remove_trail (const struct GNUNET_HashCode remove_trail_id)
 137 {
 138   struct RoutingTrail *remove_entry;
 139
 140   remove_entry = GNUNET_CONTAINER_multihashmap_get (routing_table, &remove_trail_id);
 141
 142   if (NULL == remove_entry)
 143     return GNUNET_NO;
 144
 145   if (GNUNET_YES == GNUNET_CONTAINER_multihashmap_remove (routing_table,
 146                                                           &remove_trail_id,
 147                                                           remove_entry))
 148   {
 149     GNUNET_free (remove_entry);
 150     return GNUNET_YES;
 151   }
 152   return GNUNET_NO;
 153 }
 154
 155
 156 /**
 157  * Iterate over routing table and remove entries with value as part of any trail.
 158  *
 159  * @param cls closure
 160  * @param key current public key
 161  * @param value value in the hash map
 162  * @return #GNUNET_YES if we should continue to iterate,
 163  *         #GNUNET_NO if not.
 164  */
 165 static int remove_matching_trails (void *cls,
 166                                    const struct GNUNET_HashCode *key,
 167                                    void *value)
 168 {
 169   struct RoutingTrail *remove_trail = cls;
 170   struct GNUNET_PeerIdentity *disconnected_peer = value;
 171
 172   /* If disconnected_peer is next_hop, then send a trail teardown message through
 173    * prev_hop in direction from destination to source. */
 174   if (0 == GNUNET_CRYPTO_cmp_peer_identity (&remove_trail->next_hop,
 175                                             disconnected_peer))
 176   {
 177     GDS_NEIGHBOURS_send_trail_teardown (remove_trail->trail_id,
 178                                         GDS_ROUTING_DEST_TO_SRC,
 179                                         &remove_trail->prev_hop);
 180   }
 181
 182   /* If disconnected_peer is prev_hop, then send a trail teardown through
 183    * next_hop in direction from Source to Destination. */
 184   if (0 == GNUNET_CRYPTO_cmp_peer_identity (&remove_trail->prev_hop,
 185                                             disconnected_peer))
 186   {
 187     GDS_NEIGHBOURS_send_trail_teardown (remove_trail->trail_id,
 188                                         GDS_ROUTING_SRC_TO_DEST,
 189                                         &remove_trail->next_hop);
 190   }
 191
 192   GNUNET_assert (GNUNET_YES ==
 193                    GNUNET_CONTAINER_multihashmap_remove (routing_table,
 194                                                          &remove_trail->trail_id,
 195                                                          remove_trail));
 196   GNUNET_free (remove_trail);
 197   return GNUNET_YES;
 198 }
 199
 200 #if 0
 201 /**
 202  * TEST FUNCTION
 203  * Remove after using.
 204  */
 205 void
 206 GDS_ROUTING_test_print (void)
 207 {
 208   struct GNUNET_CONTAINER_MultiHashMapIterator *iter;
 209   struct RoutingTrail *trail;
 210   struct GNUNET_PeerIdentity print_peer;
 211   struct GNUNET_HashCode key_ret;
 212   int i;
 213
 214    FPRINTF (stderr,_("\nSUPU ***PRINTING ROUTING TABLE *****"));
 215   iter =GNUNET_CONTAINER_multihashmap_iterator_create (routing_table);
 216   for (i = 0; i < GNUNET_CONTAINER_multihashmap_size(routing_table); i++)
 217   {
 218     if(GNUNET_YES == GNUNET_CONTAINER_multihashmap_iterator_next (iter,
 219                                                                   &key_ret,
 220                                                                   (const void **)&trail))
 221     {
 222       FPRINTF (stderr,_("\nSUPU %s, %s, %d, trail->trail_id = %s"),
 223               __FILE__, __func__,__LINE__, GNUNET_h2s(&trail->trail_id));
 224       memcpy (&print_peer, &trail->next_hop, sizeof (struct GNUNET_PeerIdentity));
 225       FPRINTF (stderr,_("\nSUPU %s, %s, %d, trail->next_hop = %s"),
 226               __FILE__, __func__,__LINE__, GNUNET_i2s(&print_peer));
 227       memcpy (&print_peer, &trail->prev_hop, sizeof (struct GNUNET_PeerIdentity));
 228       FPRINTF (stderr,_("\nSUPU %s, %s, %d, trail->prev_hop = %s"),
 229               __FILE__, __func__,__LINE__, GNUNET_i2s(&print_peer));
 230     }
 231   }
 232 }
 233 #endif
 234 /**
 235  * Remove every trail where peer is either next_hop or prev_hop. Also send a
 236  * trail teardown message in direction of hop which is not disconnected.
 237  * @param peer Peer identity. Trail containing this peer should be removed.
 238  */
 239 void
 240 GDS_ROUTING_remove_trail_by_peer (const struct GNUNET_PeerIdentity *peer)
 241 {
 242   GNUNET_CONTAINER_multihashmap_iterate (routing_table, &remove_matching_trails,
 243                                          (void *)peer);
 244 }
 245
 246
 247 /**
 248  * Add a new entry in routing table
 249  * @param new_trail_id
 250  * @param prev_hop
 251  * @param next_hop
 252  * @return #GNUNET_OK success
 253  *         #GNUNET_SYSERR in case new_trail_id already exists in the network
 254  *                         but with different prev_hop/next_hop
 255  */
 256 int
 257 GDS_ROUTING_add (struct GNUNET_HashCode new_trail_id,
 258                  struct GNUNET_PeerIdentity prev_hop,
 259                  struct GNUNET_PeerIdentity next_hop)
 260 {
 261   struct RoutingTrail *new_entry;
 262
 263   new_entry = GNUNET_malloc (sizeof (struct RoutingTrail));
 264   new_entry->trail_id = new_trail_id;
 265   new_entry->next_hop = next_hop;
 266   new_entry->prev_hop = prev_hop;
 267   return GNUNET_CONTAINER_multihashmap_put (routing_table,
 268                                             &new_trail_id, new_entry,
 269                                             GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY);
 270 }
 271
 272
 273 /**
 274  * Check if the size of routing table has crossed ROUTING_TABLE_THRESHOLD.
 275  * It means that I don't have any more space in my routing table and I can not
 276  * be part of any more trails till there is free space in my routing table.
 277  * @return #GNUNET_YES, if threshold crossed else #GNUNET_NO.
 278  */
 279 int
 280 GDS_ROUTING_threshold_reached (void)
 281 {
 282   return (GNUNET_CONTAINER_multihashmap_size(routing_table) >
 283           ROUTING_TABLE_THRESHOLD) ? GNUNET_YES:GNUNET_NO;
 284 }
 285
 286
 287 /**
 288  * Initialize routing subsystem.
 289  */
 290 void
 291 GDS_ROUTING_init (void)
 292 {
 293   routing_table = GNUNET_CONTAINER_multihashmap_create (ROUTING_TABLE_THRESHOLD * 4 / 3,
 294                                                         GNUNET_NO);
 295 }
 296
 297
 298 /**
 299  * Shutdown routing subsystem.
 300  */
 301 void
 302 GDS_ROUTING_done (void)
 303 {
 304   GNUNET_assert (0 == GNUNET_CONTAINER_multihashmap_size (routing_table));
 305   GNUNET_CONTAINER_multihashmap_destroy (routing_table);
 306 }
 307
 308 /* end of gnunet-service-xdht_routing.c */