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      SPDX-License-Identifier: AGPL3.0-or-later
  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    * The peer this request was received from.
  46    */
  47   struct GNUNET_PeerIdentity peer;
  48
  49   /**
  50    * Key of this request.
  51    */
  52   struct GNUNET_HashCode key;
  53
  54   /**
  55    * Position of this node in the min heap.
  56    */
  57   struct GNUNET_CONTAINER_HeapNode *heap_node;
  58
  59   /**
  60    * Block group for filtering replies.
  61    */
  62   struct GNUNET_BLOCK_Group *bg;
  63
  64   /**
  65    * Type of the requested block.
  66    */
  67   enum GNUNET_BLOCK_Type type;
  68
  69   /**
  70    * extended query (see gnunet_block_lib.h).  Allocated at the
  71    * end of this struct.
  72    */
  73   const void *xquery;
  74
  75   /**
  76    * Number of bytes in xquery.
  77    */
  78   size_t xquery_size;
  79
  80   /**
  81    * Request options.
  82    */
  83   enum GNUNET_DHT_RouteOption options;
  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  * Forward the result to the given peer if it matches the request.
 147  *
 148  * @param cls the `struct ProcessContext` with the result
 149  * @param key the query
 150  * @param value the `struct RecentRequest` with the request
 151  * @return #GNUNET_OK (continue to iterate),
 152  *         #GNUNET_SYSERR if the result is malformed or type unsupported
 153  */
 154 static int
 155 process (void *cls,
 156          const struct GNUNET_HashCode *key,
 157          void *value)
 158 {
 159   struct ProcessContext *pc = cls;
 160   struct RecentRequest *rr = value;
 161   enum GNUNET_BLOCK_EvaluationResult eval;
 162   unsigned int gpl;
 163   unsigned int ppl;
 164   struct GNUNET_HashCode hc;
 165   const struct GNUNET_HashCode *eval_key;
 166
 167   if ((rr->type != GNUNET_BLOCK_TYPE_ANY) &&
 168       (rr->type != pc->type))
 169     return GNUNET_OK;           /* type missmatch */
 170
 171   if (0 != (rr->options & GNUNET_DHT_RO_RECORD_ROUTE))
 172   {
 173     gpl = pc->get_path_length;
 174     ppl = pc->put_path_length;
 175   }
 176   else
 177   {
 178     gpl = 0;
 179     ppl = 0;
 180   }
 181   if ((0 != (rr->options & GNUNET_DHT_RO_FIND_PEER)) &&
 182       (pc->type == GNUNET_BLOCK_TYPE_DHT_HELLO))
 183   {
 184     /* key may not match HELLO, which is OK since
 185      * the search is approximate.  Still, the evaluation
 186      * would fail since the match is not exact.  So
 187      * we fake it by changing the key to the actual PID ... */
 188     GNUNET_BLOCK_get_key (GDS_block_context,
 189                           GNUNET_BLOCK_TYPE_DHT_HELLO,
 190                           pc->data,
 191                           pc->data_size,
 192                           &hc);
 193     eval_key = &hc;
 194   }
 195   else
 196   {
 197     eval_key = key;
 198   }
 199   eval
 200     = GNUNET_BLOCK_evaluate (GDS_block_context,
 201                              pc->type,
 202                              rr->bg,
 203                              GNUNET_BLOCK_EO_NONE,
 204                              eval_key,
 205                              rr->xquery,
 206                              rr->xquery_size,
 207                              pc->data,
 208                              pc->data_size);
 209   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 210               "Result for %s of type %d was evaluated as %d\n",
 211               GNUNET_h2s (key),
 212               pc->type,
 213               eval);
 214   switch (eval)
 215   {
 216   case GNUNET_BLOCK_EVALUATION_OK_MORE:
 217   case GNUNET_BLOCK_EVALUATION_OK_LAST:
 218     GNUNET_STATISTICS_update (GDS_stats,
 219                               gettext_noop
 220                                 ("# Good REPLIES matched against routing table"),
 221                               1, GNUNET_NO);
 222     GDS_NEIGHBOURS_handle_reply (&rr->peer,
 223                                  pc->type,
 224                                  pc->expiration_time,
 225                                  key,
 226                                  ppl, pc->put_path,
 227                                  gpl, pc->get_path,
 228                                  pc->data,
 229                                  pc->data_size);
 230     break;
 231
 232   case GNUNET_BLOCK_EVALUATION_OK_DUPLICATE:
 233     GNUNET_STATISTICS_update (GDS_stats,
 234                               gettext_noop
 235                               (
 236                                 "# Duplicate REPLIES matched against routing table"),
 237                               1, GNUNET_NO);
 238     return GNUNET_OK;
 239
 240   case GNUNET_BLOCK_EVALUATION_RESULT_INVALID:
 241     GNUNET_STATISTICS_update (GDS_stats,
 242                               gettext_noop
 243                               (
 244                                 "# Invalid REPLIES matched against routing table"),
 245                               1, GNUNET_NO);
 246     return GNUNET_SYSERR;
 247
 248   case GNUNET_BLOCK_EVALUATION_RESULT_IRRELEVANT:
 249     GNUNET_STATISTICS_update (GDS_stats,
 250                               gettext_noop
 251                               (
 252                                 "# Irrelevant REPLIES matched against routing table"),
 253                               1, GNUNET_NO);
 254     return GNUNET_OK;
 255
 256   case GNUNET_BLOCK_EVALUATION_REQUEST_VALID:
 257     GNUNET_break (0);
 258     return GNUNET_OK;
 259
 260   case GNUNET_BLOCK_EVALUATION_REQUEST_INVALID:
 261     GNUNET_break (0);
 262     return GNUNET_OK;
 263
 264   case GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED:
 265     GNUNET_STATISTICS_update (GDS_stats,
 266                               gettext_noop
 267                               (
 268                                 "# Unsupported REPLIES matched against routing table"),
 269                               1, GNUNET_NO);
 270     return GNUNET_SYSERR;
 271
 272   default:
 273     GNUNET_break (0);
 274     return GNUNET_SYSERR;
 275   }
 276   return GNUNET_OK;
 277 }
 278
 279
 280 /**
 281  * Handle a reply (route to origin).  Only forwards the reply back to
 282  * other peers waiting for it.  Does not do local caching or
 283  * forwarding to local clients.  Essentially calls
 284  * GDS_NEIGHBOURS_handle_reply for all peers that sent us a matching
 285  * request recently.
 286  *
 287  * @param type type of the block
 288  * @param expiration_time when does the content expire
 289  * @param key key for the content
 290  * @param put_path_length number of entries in @a put_path
 291  * @param put_path peers the original PUT traversed (if tracked)
 292  * @param get_path_length number of entries in @a get_path
 293  * @param get_path peers this reply has traversed so far (if tracked)
 294  * @param data payload of the reply
 295  * @param data_size number of bytes in data
 296  */
 297 void
 298 GDS_ROUTING_process (enum GNUNET_BLOCK_Type type,
 299                      struct GNUNET_TIME_Absolute expiration_time,
 300                      const struct GNUNET_HashCode *key,
 301                      unsigned int put_path_length,
 302                      const struct GNUNET_PeerIdentity *put_path,
 303                      unsigned int get_path_length,
 304                      const struct GNUNET_PeerIdentity *get_path,
 305                      const void *data,
 306                      size_t data_size)
 307 {
 308   struct ProcessContext pc;
 309
 310   pc.type = type;
 311   pc.expiration_time = expiration_time;
 312   pc.put_path_length = put_path_length;
 313   pc.put_path = put_path;
 314   pc.get_path_length = get_path_length;
 315   pc.get_path = get_path;
 316   pc.data = data;
 317   pc.data_size = data_size;
 318   if (NULL == data)
 319   {
 320     /* Some apps might have an 'empty' reply as a valid reply; however,
 321        'process' will call GNUNET_BLOCK_evaluate' which treats a 'NULL'
 322        reply as request-validation (but we need response-validation).
 323        So we set 'data' to a 0-byte non-NULL value just to be sure */
 324     GNUNET_break (0 == data_size);
 325     pc.data_size = 0;
 326     pc.data = "";   /* something not null */
 327   }
 328   GNUNET_CONTAINER_multihashmap_get_multiple (recent_map,
 329                                               key,
 330                                               &process,
 331                                               &pc);
 332 }
 333
 334
 335 /**
 336  * Remove the oldest entry from the DHT routing table.  Must only
 337  * be called if it is known that there is at least one entry
 338  * in the heap and hashmap.
 339  */
 340 static void
 341 expire_oldest_entry ()
 342 {
 343   struct RecentRequest *recent_req;
 344
 345   GNUNET_STATISTICS_update (GDS_stats,
 346                             gettext_noop
 347                               ("# Entries removed from routing table"), 1,
 348                             GNUNET_NO);
 349   recent_req = GNUNET_CONTAINER_heap_peek (recent_heap);
 350   GNUNET_assert (recent_req != NULL);
 351   GNUNET_CONTAINER_heap_remove_node (recent_req->heap_node);
 352   GNUNET_BLOCK_group_destroy (recent_req->bg);
 353   GNUNET_assert (GNUNET_YES ==
 354                  GNUNET_CONTAINER_multihashmap_remove (recent_map,
 355                                                        &recent_req->key,
 356                                                        recent_req));
 357   GNUNET_free (recent_req);
 358 }
 359
 360
 361 /**
 362  * Try to combine multiple recent requests for the same value
 363  * (if they come from the same peer).
 364  *
 365  * @param cls the new 'struct RecentRequest' (to discard upon successful combination)
 366  * @param key the query
 367  * @param value the existing 'struct RecentRequest' (to update upon successful combination)
 368  * @return #GNUNET_OK (continue to iterate),
 369  *         #GNUNET_SYSERR if the request was successfully combined
 370  */
 371 static int
 372 try_combine_recent (void *cls,
 373                     const struct GNUNET_HashCode *key,
 374                     void *value)
 375 {
 376   struct RecentRequest *in = cls;
 377   struct RecentRequest *rr = value;
 378
 379   if ((0 != GNUNET_memcmp (&in->peer,
 380                            &rr->peer)) ||
 381       (in->type != rr->type) ||
 382       (in->xquery_size != rr->xquery_size) ||
 383       (0 != memcmp (in->xquery,
 384                     rr->xquery,
 385                     in->xquery_size)))
 386     return GNUNET_OK;
 387   GNUNET_break (GNUNET_SYSERR !=
 388                 GNUNET_BLOCK_group_merge (in->bg,
 389                                           rr->bg));
 390   rr->bg = in->bg;
 391   GNUNET_free (in);
 392   return GNUNET_SYSERR;
 393 }
 394
 395
 396 /**
 397  * Add a new entry to our routing table.
 398  *
 399  * @param sender peer that originated the request
 400  * @param type type of the block
 401  * @param options options for processing
 402  * @param key key for the content
 403  * @param xquery extended query
 404  * @param xquery_size number of bytes in @a xquery
 405  * @param reply_bf bloomfilter to filter duplicates
 406  * @param reply_bf_mutator mutator for @a reply_bf
 407  */
 408 void
 409 GDS_ROUTING_add (const struct GNUNET_PeerIdentity *sender,
 410                  enum GNUNET_BLOCK_Type type,
 411                  struct GNUNET_BLOCK_Group *bg,
 412                  enum GNUNET_DHT_RouteOption options,
 413                  const struct GNUNET_HashCode *key,
 414                  const void *xquery,
 415                  size_t xquery_size)
 416 {
 417   struct RecentRequest *recent_req;
 418
 419   while (GNUNET_CONTAINER_heap_get_size (recent_heap) >= DHT_MAX_RECENT)
 420     expire_oldest_entry ();
 421   GNUNET_STATISTICS_update (GDS_stats,
 422                             gettext_noop ("# Entries added to routing table"),
 423                             1,
 424                             GNUNET_NO);
 425   recent_req = GNUNET_malloc (sizeof(struct RecentRequest) + xquery_size);
 426   recent_req->peer = *sender;
 427   recent_req->key = *key;
 428   recent_req->bg = bg;
 429   recent_req->type = type;
 430   recent_req->options = options;
 431   recent_req->xquery = &recent_req[1];
 432   GNUNET_memcpy (&recent_req[1],
 433                  xquery,
 434                  xquery_size);
 435   recent_req->xquery_size = xquery_size;
 436   if (GNUNET_SYSERR ==
 437       GNUNET_CONTAINER_multihashmap_get_multiple (recent_map,
 438                                                   key,
 439                                                   &try_combine_recent,
 440                                                   recent_req))
 441   {
 442     GNUNET_STATISTICS_update (GDS_stats,
 443                               gettext_noop
 444                                 ("# DHT requests combined"),
 445                               1, GNUNET_NO);
 446     return;
 447   }
 448   recent_req->heap_node
 449     = GNUNET_CONTAINER_heap_insert (recent_heap,
 450                                     recent_req,
 451                                     GNUNET_TIME_absolute_get ().abs_value_us);
 452   GNUNET_CONTAINER_multihashmap_put (recent_map,
 453                                      key,
 454                                      recent_req,
 455                                      GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE);
 456 }
 457
 458
 459 /**
 460  * Initialize routing subsystem.
 461  */
 462 void
 463 GDS_ROUTING_init ()
 464 {
 465   recent_heap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN);
 466   recent_map = GNUNET_CONTAINER_multihashmap_create (DHT_MAX_RECENT * 4 / 3,
 467                                                      GNUNET_NO);
 468 }
 469
 470
 471 /**
 472  * Shutdown routing subsystem.
 473  */
 474 void
 475 GDS_ROUTING_done ()
 476 {
 477   while (GNUNET_CONTAINER_heap_get_size (recent_heap) > 0)
 478     expire_oldest_entry ();
 479   GNUNET_assert (0 == GNUNET_CONTAINER_heap_get_size (recent_heap));
 480   GNUNET_CONTAINER_heap_destroy (recent_heap);
 481   recent_heap = NULL;
 482   GNUNET_assert (0 == GNUNET_CONTAINER_multihashmap_size (recent_map));
 483   GNUNET_CONTAINER_multihashmap_destroy (recent_map);
 484   recent_map = NULL;
 485 }
 486
 487
 488 /* end of gnunet-service-dht_routing.c */