src/dht/gnunet-service-dht_routing.c

   1 /*
   2      This file is part of GNUnet.
   3      (C) 2011 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-dht_routing.c
  23  * @brief GNUnet DHT tracking of requests for routing replies
  24  * @author Christian Grothoff
  25  */
  26 #include "platform.h"
  27 #include "gnunet-service-dht_neighbours.h"
  28 #include "gnunet-service-dht_routing.h"
  29 #include "gnunet-service-dht.h"
  30
  31
  32 /**
  33  * Number of requests we track at most (for routing replies).
  34  */
  35 #define DHT_MAX_RECENT (1024 * 16)
  36
  37
  38 /**
  39  * Information we keep about all recent GET requests
  40  * so that we can route replies.
  41  */
  42 struct RecentRequest
  43 {
  44
  45   /**
  46    * The peer this request was received from.
  47    */
  48   struct GNUNET_PeerIdentity peer;
  49
  50   /**
  51    * Key of this request.
  52    */
  53   GNUNET_HashCode key;
  54
  55   /**
  56    * Position of this node in the min heap.
  57    */
  58   struct GNUNET_CONTAINER_HeapNode *heap_node;
  59
  60   /**
  61    * Bloomfilter for replies to drop.
  62    */
  63   struct GNUNET_CONTAINER_BloomFilter *reply_bf;
  64
  65   /**
  66    * Type of the requested block.
  67    */
  68   enum GNUNET_BLOCK_Type type;
  69
  70   /**
  71    * extended query (see gnunet_block_lib.h).  Allocated at the
  72    * end of this struct.
  73    */
  74   const void *xquery;
  75
  76   /**
  77    * Number of bytes in xquery.
  78    */
  79   size_t xquery_size;
  80
  81   /**
  82    * Mutator value for the reply_bf, see gnunet_block_lib.h
  83    */
  84   uint32_t reply_bf_mutator;
  85
  86   /**
  87    * Request options.
  88    */
  89   enum GNUNET_DHT_RouteOption options;
  90
  91 };
  92
  93
  94 /**
  95  * Recent requests by time inserted.
  96  */
  97 static struct GNUNET_CONTAINER_Heap *recent_heap;
  98
  99 /**
 100  * Recently seen requests by key.
 101  */
 102 static struct GNUNET_CONTAINER_MultiHashMap *recent_map;
 103
 104
 105 /**
 106  * Closure for the 'process' function.
 107  */
 108 struct ProcessContext
 109 {
 110   /**
 111    * Path of the original PUT
 112    */
 113   const struct GNUNET_PeerIdentity *put_path;
 114
 115   /**
 116    * Path of the reply.
 117    */
 118   const struct GNUNET_PeerIdentity *get_path;
 119
 120   /**
 121    * Payload of the reply.
 122    */
 123   const void *data;
 124
 125   /**
 126    * Expiration time of the result.
 127    */
 128   struct GNUNET_TIME_Absolute expiration_time;
 129
 130   /**
 131    * Number of entries in 'put_path'.
 132    */
 133   unsigned int put_path_length;
 134
 135   /**
 136    * Number of entries in 'get_path'.
 137    */
 138   unsigned int get_path_length;
 139
 140   /**
 141    * Number of bytes in 'data'.
 142    */
 143   size_t data_size;
 144
 145   /**
 146    * Type of the reply.
 147    */
 148   enum GNUNET_BLOCK_Type type;
 149
 150 };
 151
 152
 153 /**
 154  * Forward the result to the given peer if it matches the request.
 155  *
 156  * @param cls the 'struct ProcessContext' with the result
 157  * @param key the query
 158  * @param value the 'struct RecentRequest' with the request
 159  * @return GNUNET_OK (continue to iterate),
 160  *         GNUNET_SYSERR if the result is malformed or type unsupported
 161  */
 162 static int
 163 process (void *cls,
 164          const GNUNET_HashCode *key,
 165          void *value)
 166 {
 167   struct ProcessContext *pc = cls;
 168   struct RecentRequest *rr = value;
 169   enum GNUNET_BLOCK_EvaluationResult eval;
 170   unsigned int gpl;
 171   unsigned int ppl;
 172   GNUNET_HashCode hc;
 173   const GNUNET_HashCode *eval_key;
 174
 175   if ( (rr->type != GNUNET_BLOCK_TYPE_ANY) &&
 176        (rr->type != pc->type) )
 177     return GNUNET_OK; /* type missmatch */
 178
 179   if (0 != (rr->options & GNUNET_DHT_RO_RECORD_ROUTE))
 180   {
 181     gpl = pc->get_path_length;
 182     ppl = pc->put_path_length;
 183   }
 184   else
 185   {
 186     gpl = 0;
 187     ppl = 0;
 188   }
 189   if ( (0 != (rr->options & GNUNET_DHT_RO_FIND_PEER)) &&
 190        (pc->type == GNUNET_BLOCK_TYPE_DHT_HELLO) )
 191   {
 192     /* key may not match HELLO, which is OK since
 193        the search is approximate.  Still, the evaluation
 194        would fail since the match is not exact.  So
 195        we fake it by changing the key to the actual PID ... */
 196     GNUNET_BLOCK_get_key (GDS_block_context,
 197                           GNUNET_BLOCK_TYPE_DHT_HELLO,
 198                           pc->data, pc->data_size,
 199                           &hc);
 200     eval_key = &hc;
 201   }
 202   else
 203   {
 204     eval_key = key;
 205   }
 206   eval = GNUNET_BLOCK_evaluate (GDS_block_context,
 207                                 pc->type,
 208                                 eval_key,
 209                                 &rr->reply_bf,
 210                                 rr->reply_bf_mutator,
 211                                 rr->xquery,
 212                                 rr->xquery_size,
 213                                 pc->data,
 214                                 pc->data_size);
 215   switch (eval)
 216   {
 217   case GNUNET_BLOCK_EVALUATION_OK_MORE:
 218   case GNUNET_BLOCK_EVALUATION_OK_LAST:
 219     GNUNET_STATISTICS_update (GDS_stats,
 220                               gettext_noop ("# Good REPLIES matched against routing table"), 1,
 221                               GNUNET_NO);
 222     GDS_NEIGHBOURS_handle_reply (&rr->peer,
 223                                  pc->type,
 224                                  pc->expiration_time,
 225                                  key,
 226                                  ppl,
 227                                  pc->put_path,
 228                                  gpl,
 229                                  pc->get_path,
 230                                  pc->data,
 231                                  pc->data_size);
 232     break;
 233   case GNUNET_BLOCK_EVALUATION_OK_DUPLICATE:
 234     GNUNET_STATISTICS_update (GDS_stats,
 235                               gettext_noop ("# Duplicate REPLIES matched against routing table"), 1,
 236                               GNUNET_NO);
 237     return GNUNET_OK;
 238   case GNUNET_BLOCK_EVALUATION_RESULT_INVALID:
 239     GNUNET_STATISTICS_update (GDS_stats,
 240                               gettext_noop ("# Invalid REPLIES matched against routing table"), 1,
 241                               GNUNET_NO);
 242     return GNUNET_SYSERR;
 243   case GNUNET_BLOCK_EVALUATION_REQUEST_VALID:
 244   case GNUNET_BLOCK_EVALUATION_REQUEST_INVALID:
 245     GNUNET_break (0);
 246     return GNUNET_OK;
 247   case GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED:
 248     GNUNET_STATISTICS_update (GDS_stats,
 249                               gettext_noop ("# Unsupported REPLIES matched against routing table"), 1,
 250                               GNUNET_NO);
 251     return GNUNET_SYSERR;
 252   default:
 253     GNUNET_break (0);
 254     return GNUNET_SYSERR;
 255   }
 256   return GNUNET_OK;
 257 }
 258
 259
 260 /**
 261  * Handle a reply (route to origin).  Only forwards the reply back to
 262  * other peers waiting for it.  Does not do local caching or
 263  * forwarding to local clients.  Essentially calls
 264  * GDS_NEIGHBOURS_handle_reply for all peers that sent us a matching
 265  * request recently.
 266  *
 267  * @param type type of the block
 268  * @param expiration_time when does the content expire
 269  * @param key key for the content
 270  * @param put_path_length number of entries in put_path
 271  * @param put_path peers the original PUT traversed (if tracked)
 272  * @param get_path_length number of entries in put_path
 273  * @param get_path peers this reply has traversed so far (if tracked)
 274  * @param data payload of the reply
 275  * @param data_size number of bytes in data
 276  */
 277 void
 278 GDS_ROUTING_process (enum GNUNET_BLOCK_Type type,
 279                      struct GNUNET_TIME_Absolute expiration_time,
 280                      const GNUNET_HashCode *key,
 281                      unsigned int put_path_length,
 282                      const struct GNUNET_PeerIdentity *put_path,
 283                      unsigned int get_path_length,
 284                      const struct GNUNET_PeerIdentity *get_path,
 285                      const void *data,
 286                      size_t data_size)
 287 {
 288   struct ProcessContext pc;
 289
 290   pc.type = type;
 291   pc.expiration_time = expiration_time;
 292   pc.put_path_length = put_path_length;
 293   pc.put_path = put_path;
 294   pc.get_path_length = get_path_length;
 295   pc.get_path = get_path;
 296   pc.data = data;
 297   pc.data_size = data_size;
 298   GNUNET_CONTAINER_multihashmap_get_multiple (recent_map,
 299                                               key,
 300                                               &process,
 301                                               &pc);
 302 }
 303
 304
 305 /**
 306  * Add a new entry to our routing table.
 307  *
 308  * @param sender peer that originated the request
 309  * @param type type of the block
 310  * @param options options for processing
 311  * @param key key for the content
 312  * @param xquery extended query
 313  * @param xquery_size number of bytes in xquery
 314  * @param reply_bf bloomfilter to filter duplicates
 315  * @param reply_bf_mutator mutator for reply_bf
 316 */
 317 void
 318 GDS_ROUTING_add (const struct GNUNET_PeerIdentity *sender,
 319                  enum GNUNET_BLOCK_Type type,
 320                  enum GNUNET_DHT_RouteOption options,
 321                  const GNUNET_HashCode *key,
 322                  const void *xquery,
 323                  size_t xquery_size,
 324                  const struct GNUNET_CONTAINER_BloomFilter *reply_bf,
 325                  uint32_t reply_bf_mutator)
 326 {
 327   struct RecentRequest *recent_req;
 328
 329   while (GNUNET_CONTAINER_heap_get_size (recent_heap) >= DHT_MAX_RECENT)
 330   {
 331     GNUNET_STATISTICS_update (GDS_stats,
 332                               gettext_noop ("# Entries removed from routing table"), 1,
 333                               GNUNET_NO);
 334     recent_req = GNUNET_CONTAINER_heap_peek (recent_heap);
 335     GNUNET_assert (recent_req != NULL);
 336     GNUNET_CONTAINER_heap_remove_node (recent_req->heap_node);
 337     GNUNET_CONTAINER_bloomfilter_free (recent_req->reply_bf);
 338     GNUNET_free (recent_req);
 339   }
 340
 341   GNUNET_STATISTICS_update (GDS_stats,
 342                             gettext_noop ("# Entries added to routing table"), 1,
 343                             GNUNET_NO);
 344   recent_req = GNUNET_malloc (sizeof (struct RecentRequest) + xquery_size);
 345   recent_req->peer = *sender;
 346   recent_req->key = *key;
 347   recent_req->heap_node =
 348     GNUNET_CONTAINER_heap_insert (recent_heap, recent_req,
 349                                   GNUNET_TIME_absolute_get ().abs_value);
 350   recent_req->reply_bf =
 351     GNUNET_CONTAINER_bloomfilter_copy (reply_bf);
 352   recent_req->type = type;
 353   recent_req->options = options;
 354   recent_req->xquery = &recent_req[1];
 355   recent_req->xquery_size = xquery_size;
 356   recent_req->reply_bf_mutator = reply_bf_mutator;
 357   GNUNET_CONTAINER_multihashmap_put (recent_map,
 358                                      key,
 359                                      recent_req,
 360                                      GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE);
 361
 362
 363 }
 364
 365
 366 /**
 367  * Initialize routing subsystem.
 368  */
 369 void
 370 GDS_ROUTING_init ()
 371 {
 372   recent_heap =
 373     GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN);
 374   recent_map =
 375       GNUNET_CONTAINER_multihashmap_create (DHT_MAX_RECENT * 4 / 3);
 376 }
 377
 378
 379 /**
 380  * Shutdown routing subsystem.
 381  */
 382 void
 383 GDS_ROUTING_done ()
 384 {
 385   struct RecentRequest *recent_req;
 386
 387   while (GNUNET_CONTAINER_heap_get_size (recent_heap) > 0)
 388   {
 389     GNUNET_STATISTICS_update (GDS_stats,
 390                               gettext_noop ("# Entries removed from routing table"), 1,
 391                               GNUNET_NO);
 392     recent_req = GNUNET_CONTAINER_heap_peek (recent_heap);
 393     GNUNET_assert (recent_req != NULL);
 394     GNUNET_CONTAINER_heap_remove_node (recent_req->heap_node);
 395     GNUNET_CONTAINER_bloomfilter_free (recent_req->reply_bf);
 396     GNUNET_free (recent_req);
 397   }
 398   GNUNET_assert (0 == GNUNET_CONTAINER_heap_get_size (recent_heap));
 399   GNUNET_CONTAINER_heap_destroy (recent_heap);
 400   recent_heap = NULL;
 401   GNUNET_CONTAINER_multihashmap_destroy (recent_map);
 402   recent_map = NULL;
 403 }
 404
 405 /* end of gnunet-service-dht_routing.c */