src/dht/gnunet-service-dht_routing.c

   1 /*
   2      This file is part of GNUnet.
   3      Copyright (C) 2011 GNUnet e.V.
   4
   5      GNUnet is free software: you can redistribute it and/or modify it
   6      under the terms of the GNU Affero General Public License as published
   7      by the Free Software Foundation, either version 3 of the License,
   8      or (at your 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      Affero General Public License for more details.
  14
  15      You should have received a copy of the GNU Affero General Public License
  16      along with this program.  If not, see <http://www.gnu.org/licenses/>.
  17 */
  18
  19 /**
  20  * @file dht/gnunet-service-dht_routing.c
  21  * @brief GNUnet DHT tracking of requests for routing replies
  22  * @author Christian Grothoff
  23  */
  24 #include "platform.h"
  25 #include "gnunet-service-dht_neighbours.h"
  26 #include "gnunet-service-dht_routing.h"
  27 #include "gnunet-service-dht.h"
  28
  29
  30 /**
  31  * Number of requests we track at most (for routing replies).
  32  */
  33 #define DHT_MAX_RECENT (1024 * 16)
  34
  35
  36 /**
  37  * Information we keep about all recent GET requests
  38  * so that we can route replies.
  39  */
  40 struct RecentRequest
  41 {
  42
  43   /**
  44    * The peer this request was received from.
  45    */
  46   struct GNUNET_PeerIdentity peer;
  47
  48   /**
  49    * Key of this request.
  50    */
  51   struct GNUNET_HashCode key;
  52
  53   /**
  54    * Position of this node in the min heap.
  55    */
  56   struct GNUNET_CONTAINER_HeapNode *heap_node;
  57
  58   /**
  59    * Block group for filtering replies.
  60    */
  61   struct GNUNET_BLOCK_Group *bg;
  62
  63   /**
  64    * Type of the requested block.
  65    */
  66   enum GNUNET_BLOCK_Type type;
  67
  68   /**
  69    * extended query (see gnunet_block_lib.h).  Allocated at the
  70    * end of this struct.
  71    */
  72   const void *xquery;
  73
  74   /**
  75    * Number of bytes in xquery.
  76    */
  77   size_t xquery_size;
  78
  79   /**
  80    * Request options.
  81    */
  82   enum GNUNET_DHT_RouteOption options;
  83
  84 };
  85
  86
  87 /**
  88  * Recent requests by time inserted.
  89  */
  90 static struct GNUNET_CONTAINER_Heap *recent_heap;
  91
  92 /**
  93  * Recently seen requests by key.
  94  */
  95 static struct GNUNET_CONTAINER_MultiHashMap *recent_map;
  96
  97
  98 /**
  99  * Closure for the 'process' function.
 100  */
 101 struct ProcessContext
 102 {
 103   /**
 104    * Path of the original PUT
 105    */
 106   const struct GNUNET_PeerIdentity *put_path;
 107
 108   /**
 109    * Path of the reply.
 110    */
 111   const struct GNUNET_PeerIdentity *get_path;
 112
 113   /**
 114    * Payload of the reply.
 115    */
 116   const void *data;
 117
 118   /**
 119    * Expiration time of the result.
 120    */
 121   struct GNUNET_TIME_Absolute expiration_time;
 122
 123   /**
 124    * Number of entries in @e put_path.
 125    */
 126   unsigned int put_path_length;
 127
 128   /**
 129    * Number of entries in @e get_path.
 130    */
 131   unsigned int get_path_length;
 132
 133   /**
 134    * Number of bytes in @e data.
 135    */
 136   size_t data_size;
 137
 138   /**
 139    * Type of the reply.
 140    */
 141   enum GNUNET_BLOCK_Type type;
 142
 143 };
 144
 145
 146 /**
 147  * Forward the result to the given peer if it matches the request.
 148  *
 149  * @param cls the `struct ProcessContext` with the result
 150  * @param key the query
 151  * @param value the `struct RecentRequest` with the request
 152  * @return #GNUNET_OK (continue to iterate),
 153  *         #GNUNET_SYSERR if the result is malformed or type unsupported
 154  */
 155 static int
 156 process (void *cls,
 157          const struct GNUNET_HashCode *key,
 158          void *value)
 159 {
 160   struct ProcessContext *pc = cls;
 161   struct RecentRequest *rr = value;
 162   enum GNUNET_BLOCK_EvaluationResult eval;
 163   unsigned int gpl;
 164   unsigned int ppl;
 165   struct GNUNET_HashCode hc;
 166   const struct GNUNET_HashCode *eval_key;
 167
 168   if ( (rr->type != GNUNET_BLOCK_TYPE_ANY) &&
 169        (rr->type != pc->type) )
 170     return GNUNET_OK;           /* type missmatch */
 171
 172   if (0 != (rr->options & GNUNET_DHT_RO_RECORD_ROUTE))
 173   {
 174     gpl = pc->get_path_length;
 175     ppl = pc->put_path_length;
 176   }
 177   else
 178   {
 179     gpl = 0;
 180     ppl = 0;
 181   }
 182   if ( (0 != (rr->options & GNUNET_DHT_RO_FIND_PEER)) &&
 183        (pc->type == GNUNET_BLOCK_TYPE_DHT_HELLO) )
 184   {
 185     /* key may not match HELLO, which is OK since
 186      * the search is approximate.  Still, the evaluation
 187      * would fail since the match is not exact.  So
 188      * we fake it by changing the key to the actual PID ... */
 189     GNUNET_BLOCK_get_key (GDS_block_context,
 190                           GNUNET_BLOCK_TYPE_DHT_HELLO,
 191                           pc->data,
 192                           pc->data_size,
 193                           &hc);
 194     eval_key = &hc;
 195   }
 196   else
 197   {
 198     eval_key = key;
 199   }
 200   eval
 201     = GNUNET_BLOCK_evaluate (GDS_block_context,
 202                              pc->type,
 203                              rr->bg,
 204                              GNUNET_BLOCK_EO_NONE,
 205                              eval_key,
 206                              rr->xquery,
 207                              rr->xquery_size,
 208                              pc->data,
 209                              pc->data_size);
 210   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 211               "Result for %s of type %d was evaluated as %d\n",
 212               GNUNET_h2s (key),
 213               pc->type,
 214               eval);
 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
 221                               ("# Good REPLIES matched against routing table"),
 222                               1, GNUNET_NO);
 223     GDS_NEIGHBOURS_handle_reply (&rr->peer,
 224                                  pc->type,
 225                                  pc->expiration_time,
 226                                  key,
 227                                  ppl, pc->put_path,
 228                                  gpl, pc->get_path,
 229                                  pc->data,
 230                                  pc->data_size);
 231     break;
 232   case GNUNET_BLOCK_EVALUATION_OK_DUPLICATE:
 233     GNUNET_STATISTICS_update (GDS_stats,
 234                               gettext_noop
 235                               ("# Duplicate REPLIES matched against routing table"),
 236                               1, GNUNET_NO);
 237     return GNUNET_OK;
 238   case GNUNET_BLOCK_EVALUATION_RESULT_INVALID:
 239     GNUNET_STATISTICS_update (GDS_stats,
 240                               gettext_noop
 241                               ("# Invalid REPLIES matched against routing table"),
 242                               1, GNUNET_NO);
 243     return GNUNET_SYSERR;
 244   case GNUNET_BLOCK_EVALUATION_RESULT_IRRELEVANT:
 245     GNUNET_STATISTICS_update (GDS_stats,
 246                               gettext_noop
 247                               ("# Irrelevant REPLIES matched against routing table"),
 248                               1, GNUNET_NO);
 249     return GNUNET_OK;
 250   case GNUNET_BLOCK_EVALUATION_REQUEST_VALID:
 251     GNUNET_break (0);
 252     return GNUNET_OK;
 253   case GNUNET_BLOCK_EVALUATION_REQUEST_INVALID:
 254     GNUNET_break (0);
 255     return GNUNET_OK;
 256   case GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED:
 257     GNUNET_STATISTICS_update (GDS_stats,
 258                               gettext_noop
 259                               ("# Unsupported REPLIES matched against routing table"),
 260                               1, GNUNET_NO);
 261     return GNUNET_SYSERR;
 262   default:
 263     GNUNET_break (0);
 264     return GNUNET_SYSERR;
 265   }
 266   return GNUNET_OK;
 267 }
 268
 269
 270 /**
 271  * Handle a reply (route to origin).  Only forwards the reply back to
 272  * other peers waiting for it.  Does not do local caching or
 273  * forwarding to local clients.  Essentially calls
 274  * GDS_NEIGHBOURS_handle_reply for all peers that sent us a matching
 275  * request recently.
 276  *
 277  * @param type type of the block
 278  * @param expiration_time when does the content expire
 279  * @param key key for the content
 280  * @param put_path_length number of entries in @a put_path
 281  * @param put_path peers the original PUT traversed (if tracked)
 282  * @param get_path_length number of entries in @a get_path
 283  * @param get_path peers this reply has traversed so far (if tracked)
 284  * @param data payload of the reply
 285  * @param data_size number of bytes in data
 286  */
 287 void
 288 GDS_ROUTING_process (enum GNUNET_BLOCK_Type type,
 289                      struct GNUNET_TIME_Absolute expiration_time,
 290                      const struct GNUNET_HashCode *key,
 291                      unsigned int put_path_length,
 292                      const struct GNUNET_PeerIdentity *put_path,
 293                      unsigned int get_path_length,
 294                      const struct GNUNET_PeerIdentity *get_path,
 295                      const void *data,
 296                      size_t data_size)
 297 {
 298   struct ProcessContext pc;
 299
 300   pc.type = type;
 301   pc.expiration_time = expiration_time;
 302   pc.put_path_length = put_path_length;
 303   pc.put_path = put_path;
 304   pc.get_path_length = get_path_length;
 305   pc.get_path = get_path;
 306   pc.data = data;
 307   pc.data_size = data_size;
 308   if (NULL == data)
 309   {
 310     /* Some apps might have an 'empty' reply as a valid reply; however,
 311        'process' will call GNUNET_BLOCK_evaluate' which treats a 'NULL'
 312        reply as request-validation (but we need response-validation).
 313        So we set 'data' to a 0-byte non-NULL value just to be sure */
 314     GNUNET_break (0 == data_size);
 315     pc.data_size = 0;
 316     pc.data = ""; /* something not null */
 317   }
 318   GNUNET_CONTAINER_multihashmap_get_multiple (recent_map,
 319                                               key,
 320                                               &process,
 321                                               &pc);
 322 }
 323
 324
 325 /**
 326  * Remove the oldest entry from the DHT routing table.  Must only
 327  * be called if it is known that there is at least one entry
 328  * in the heap and hashmap.
 329  */
 330 static void
 331 expire_oldest_entry ()
 332 {
 333   struct RecentRequest *recent_req;
 334
 335   GNUNET_STATISTICS_update (GDS_stats,
 336                             gettext_noop
 337                             ("# Entries removed from routing table"), 1,
 338                             GNUNET_NO);
 339   recent_req = GNUNET_CONTAINER_heap_peek (recent_heap);
 340   GNUNET_assert (recent_req != NULL);
 341   GNUNET_CONTAINER_heap_remove_node (recent_req->heap_node);
 342   GNUNET_BLOCK_group_destroy (recent_req->bg);
 343   GNUNET_assert (GNUNET_YES ==
 344                  GNUNET_CONTAINER_multihashmap_remove (recent_map,
 345                                                        &recent_req->key,
 346                                                        recent_req));
 347   GNUNET_free (recent_req);
 348 }
 349
 350
 351 /**
 352  * Try to combine multiple recent requests for the same value
 353  * (if they come from the same peer).
 354  *
 355  * @param cls the new 'struct RecentRequest' (to discard upon successful combination)
 356  * @param key the query
 357  * @param value the existing 'struct RecentRequest' (to update upon successful combination)
 358  * @return #GNUNET_OK (continue to iterate),
 359  *         #GNUNET_SYSERR if the request was successfully combined
 360  */
 361 static int
 362 try_combine_recent (void *cls,
 363                     const struct GNUNET_HashCode *key,
 364                     void *value)
 365 {
 366   struct RecentRequest *in = cls;
 367   struct RecentRequest *rr = value;
 368
 369   if ( (0 != memcmp (&in->peer,
 370                      &rr->peer,
 371                      sizeof (struct GNUNET_PeerIdentity))) ||
 372        (in->type != rr->type) ||
 373        (in->xquery_size != rr->xquery_size) ||
 374        (0 != memcmp (in->xquery,
 375                      rr->xquery,
 376                      in->xquery_size)) )
 377     return GNUNET_OK;
 378   GNUNET_break (GNUNET_SYSERR !=
 379                 GNUNET_BLOCK_group_merge (in->bg,
 380                                           rr->bg));
 381   rr->bg = in->bg;
 382   GNUNET_free (in);
 383   return GNUNET_SYSERR;
 384 }
 385
 386
 387 /**
 388  * Add a new entry to our routing table.
 389  *
 390  * @param sender peer that originated the request
 391  * @param type type of the block
 392  * @param options options for processing
 393  * @param key key for the content
 394  * @param xquery extended query
 395  * @param xquery_size number of bytes in @a xquery
 396  * @param reply_bf bloomfilter to filter duplicates
 397  * @param reply_bf_mutator mutator for @a reply_bf
 398  */
 399 void
 400 GDS_ROUTING_add (const struct GNUNET_PeerIdentity *sender,
 401                  enum GNUNET_BLOCK_Type type,
 402                  struct GNUNET_BLOCK_Group *bg,
 403                  enum GNUNET_DHT_RouteOption options,
 404                  const struct GNUNET_HashCode *key,
 405                  const void *xquery,
 406                  size_t xquery_size)
 407 {
 408   struct RecentRequest *recent_req;
 409
 410   while (GNUNET_CONTAINER_heap_get_size (recent_heap) >= DHT_MAX_RECENT)
 411     expire_oldest_entry ();
 412   GNUNET_STATISTICS_update (GDS_stats,
 413                             gettext_noop ("# Entries added to routing table"),
 414                             1,
 415                             GNUNET_NO);
 416   recent_req = GNUNET_malloc (sizeof (struct RecentRequest) + xquery_size);
 417   recent_req->peer = *sender;
 418   recent_req->key = *key;
 419   recent_req->bg = bg;
 420   recent_req->type = type;
 421   recent_req->options = options;
 422   recent_req->xquery = &recent_req[1];
 423   GNUNET_memcpy (&recent_req[1],
 424                  xquery,
 425                  xquery_size);
 426   recent_req->xquery_size = xquery_size;
 427   if (GNUNET_SYSERR ==
 428       GNUNET_CONTAINER_multihashmap_get_multiple (recent_map,
 429                                                   key,
 430                                                   &try_combine_recent,
 431                                                   recent_req))
 432   {
 433     GNUNET_STATISTICS_update (GDS_stats,
 434                               gettext_noop
 435                               ("# DHT requests combined"),
 436                               1, GNUNET_NO);
 437     return;
 438   }
 439   recent_req->heap_node
 440     = GNUNET_CONTAINER_heap_insert (recent_heap,
 441                                     recent_req,
 442                                     GNUNET_TIME_absolute_get ().abs_value_us);
 443   GNUNET_CONTAINER_multihashmap_put (recent_map,
 444                                      key,
 445                                      recent_req,
 446                                      GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE);
 447 }
 448
 449
 450 /**
 451  * Initialize routing subsystem.
 452  */
 453 void
 454 GDS_ROUTING_init ()
 455 {
 456   recent_heap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN);
 457   recent_map = GNUNET_CONTAINER_multihashmap_create (DHT_MAX_RECENT * 4 / 3, GNUNET_NO);
 458 }
 459
 460
 461 /**
 462  * Shutdown routing subsystem.
 463  */
 464 void
 465 GDS_ROUTING_done ()
 466 {
 467   while (GNUNET_CONTAINER_heap_get_size (recent_heap) > 0)
 468     expire_oldest_entry ();
 469   GNUNET_assert (0 == GNUNET_CONTAINER_heap_get_size (recent_heap));
 470   GNUNET_CONTAINER_heap_destroy (recent_heap);
 471   recent_heap = NULL;
 472   GNUNET_assert (0 == GNUNET_CONTAINER_multihashmap_size (recent_map));
 473   GNUNET_CONTAINER_multihashmap_destroy (recent_map);
 474   recent_map = NULL;
 475 }
 476
 477 /* end of gnunet-service-dht_routing.c */