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     GDS_NEIGHBOURS_handle_reply (&rr->peer,
 220                                  pc->type,
 221                                  pc->expiration_time,
 222                                  key,
 223                                  ppl,
 224                                  pc->put_path,
 225                                  gpl,
 226                                  pc->get_path,
 227                                  pc->data,
 228                                  pc->data_size);
 229     break;
 230   case GNUNET_BLOCK_EVALUATION_OK_DUPLICATE:
 231     return GNUNET_OK;
 232   case GNUNET_BLOCK_EVALUATION_RESULT_INVALID:
 233     GNUNET_break_op (0);
 234     return GNUNET_SYSERR;
 235   case GNUNET_BLOCK_EVALUATION_REQUEST_VALID:
 236   case GNUNET_BLOCK_EVALUATION_REQUEST_INVALID:
 237     GNUNET_break (0);
 238     return GNUNET_OK;
 239   case GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED:
 240     return GNUNET_SYSERR;
 241   default:
 242     GNUNET_break (0);
 243     return GNUNET_SYSERR;
 244   }
 245   return GNUNET_OK;
 246 }
 247
 248
 249 /**
 250  * Handle a reply (route to origin).  Only forwards the reply back to
 251  * other peers waiting for it.  Does not do local caching or
 252  * forwarding to local clients.  Essentially calls
 253  * GDS_NEIGHBOURS_handle_reply for all peers that sent us a matching
 254  * request recently.
 255  *
 256  * @param type type of the block
 257  * @param expiration_time when does the content expire
 258  * @param key key for the content
 259  * @param put_path_length number of entries in put_path
 260  * @param put_path peers the original PUT traversed (if tracked)
 261  * @param get_path_length number of entries in put_path
 262  * @param get_path peers this reply has traversed so far (if tracked)
 263  * @param data payload of the reply
 264  * @param data_size number of bytes in data
 265  */
 266 void
 267 GDS_ROUTING_process (enum GNUNET_BLOCK_Type type,
 268                      struct GNUNET_TIME_Absolute expiration_time,
 269                      const GNUNET_HashCode *key,
 270                      unsigned int put_path_length,
 271                      const struct GNUNET_PeerIdentity *put_path,
 272                      unsigned int get_path_length,
 273                      const struct GNUNET_PeerIdentity *get_path,
 274                      const void *data,
 275                      size_t data_size)
 276 {
 277   struct ProcessContext pc;
 278
 279   pc.type = type;
 280   pc.expiration_time = expiration_time;
 281   pc.put_path_length = put_path_length;
 282   pc.put_path = put_path;
 283   pc.get_path_length = get_path_length;
 284   pc.get_path = get_path;
 285   pc.data = data;
 286   pc.data_size = data_size;
 287   GNUNET_CONTAINER_multihashmap_get_multiple (recent_map,
 288                                               key,
 289                                               &process,
 290                                               &pc);
 291 }
 292
 293
 294 /**
 295  * Add a new entry to our routing table.
 296  *
 297  * @param sender peer that originated the request
 298  * @param type type of the block
 299  * @param options options for processing
 300  * @param key key for the content
 301  * @param xquery extended query
 302  * @param xquery_size number of bytes in xquery
 303  * @param reply_bf bloomfilter to filter duplicates
 304  * @param reply_bf_mutator mutator for reply_bf
 305 */
 306 void
 307 GDS_ROUTING_add (const struct GNUNET_PeerIdentity *sender,
 308                  enum GNUNET_BLOCK_Type type,
 309                  enum GNUNET_DHT_RouteOption options,
 310                  const GNUNET_HashCode *key,
 311                  const void *xquery,
 312                  size_t xquery_size,
 313                  const struct GNUNET_CONTAINER_BloomFilter *reply_bf,
 314                  uint32_t reply_bf_mutator)
 315 {
 316   struct RecentRequest *recent_req;
 317
 318   while (GNUNET_CONTAINER_heap_get_size (recent_heap) >= DHT_MAX_RECENT)
 319   {
 320     recent_req = GNUNET_CONTAINER_heap_peek (recent_heap);
 321     GNUNET_assert (recent_req != NULL);
 322     GNUNET_CONTAINER_heap_remove_node (recent_req->heap_node);
 323     GNUNET_CONTAINER_bloomfilter_free (recent_req->reply_bf);
 324     GNUNET_free (recent_req);
 325   }
 326
 327   recent_req = GNUNET_malloc (sizeof (struct RecentRequest) + xquery_size);
 328   recent_req->peer = *sender;
 329   recent_req->key = *key;
 330   recent_req->heap_node =
 331     GNUNET_CONTAINER_heap_insert (recent_heap, recent_req,
 332                                   GNUNET_TIME_absolute_get ().abs_value);
 333   recent_req->reply_bf =
 334     GNUNET_CONTAINER_bloomfilter_copy (reply_bf);
 335   recent_req->type = type;
 336   recent_req->options = options;
 337   recent_req->xquery = &recent_req[1];
 338   recent_req->xquery_size = xquery_size;
 339   recent_req->reply_bf_mutator = reply_bf_mutator;
 340   GNUNET_CONTAINER_multihashmap_put (recent_map,
 341                                      key,
 342                                      recent_req,
 343                                      GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE);
 344
 345
 346 }
 347
 348
 349 /**
 350  * Initialize routing subsystem.
 351  */
 352 void
 353 GDS_ROUTING_init ()
 354 {
 355   recent_heap =
 356     GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN);
 357   recent_map =
 358       GNUNET_CONTAINER_multihashmap_create (DHT_MAX_RECENT * 4 / 3);
 359 }
 360
 361
 362 /**
 363  * Shutdown routing subsystem.
 364  */
 365 void
 366 GDS_ROUTING_done ()
 367 {
 368   struct RecentRequest *recent_req;
 369
 370   while (GNUNET_CONTAINER_heap_get_size (recent_heap) > 0)
 371   {
 372     recent_req = GNUNET_CONTAINER_heap_peek (recent_heap);
 373     GNUNET_assert (recent_req != NULL);
 374     GNUNET_CONTAINER_heap_remove_node (recent_req->heap_node);
 375     GNUNET_CONTAINER_bloomfilter_free (recent_req->reply_bf);
 376     GNUNET_free (recent_req);
 377   }
 378   GNUNET_assert (0 == GNUNET_CONTAINER_heap_get_size (recent_heap));
 379   GNUNET_CONTAINER_heap_destroy (recent_heap);
 380   recent_heap = NULL;
 381   GNUNET_CONTAINER_multihashmap_destroy (recent_map);
 382   recent_map = NULL;
 383 }
 384
 385 /* end of gnunet-service-dht_routing.c */