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
  27 #include "gnunet-service-dht_routing.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    * Position of this node in the min heap.
  50    */
  51   struct GNUNET_CONTAINER_HeapNode *heap_node;
  52
  53   /**
  54    * Bloomfilter for replies to drop.
  55    */
  56   struct GNUNET_CONTAINER_BloomFilter *reply_bf;
  57
  58   /**
  59    * Timestamp of this request, for ordering
  60    * the min heap.
  61    */
  62   struct GNUNET_TIME_Absolute timestamp;
  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    * Mutator value for the reply_bf, see gnunet_block_lib.h
  82    */
  83   uint32_t reply_bf_mutator;
  84
  85   /**
  86    * Key of this request.
  87    */
  88   GNUNET_HashCode key;
  89
  90 };
  91
  92
  93 /**
  94  * Recent requests by time inserted.
  95  */
  96 static struct GNUNET_CONTAINER_Heap *recent_heap;
  97
  98 /**
  99  * Recently seen requests by key.
 100  */
 101 static struct GNUNET_CONTAINER_MultiHashMap *recent_map;
 102
 103
 104 /**
 105  * Handle a reply (route to origin).  Only forwards the reply back to
 106  * other peers waiting for it.  Does not do local caching or
 107  * forwarding to local clients.  Essentially calls
 108  * GDS_NEIGHBOURS_handle_reply for all peers that sent us a matching
 109  * request recently.
 110  *
 111  * @param type type of the block
 112  * @param expiration_time when does the content expire
 113  * @param key key for the content
 114  * @param put_path_length number of entries in put_path
 115  * @param put_path peers the original PUT traversed (if tracked)
 116  * @param get_path_length number of entries in put_path
 117  * @param get_path peers this reply has traversed so far (if tracked)
 118  * @param data payload of the reply
 119  * @param data_size number of bytes in data
 120  */
 121 void
 122 GDS_ROUTING_process (enum GNUNET_BLOCK_Type type,
 123                      GNUNET_TIME_Absolute expiration_time,
 124                      const GNUNET_HashCode *key,
 125                      unsigned int put_path_length,
 126                      struct GNUNET_PeerIdentity *put_path,
 127                      unsigned int get_path_length,
 128                      struct GNUNET_PeerIdentity *get_path,
 129                      const void *data,
 130                      size_t data_size)
 131 {
 132 }
 133
 134
 135 /**
 136  * Add a new entry to our routing table.
 137  *
 138  * @param sender peer that originated the request
 139  * @param type type of the block
 140  * @param key key for the content
 141  * @param xquery extended query
 142  * @param xquery_size number of bytes in xquery
 143  * @param reply_bf bloomfilter to filter duplicates
 144  * @param reply_bf_mutator mutator for reply_bf
 145 */
 146 void
 147 GDS_ROUTING_add (const GNUNET_PeerIdentity *sender,
 148                  enum GNUNET_BLOCK_Type type,
 149                  const GNUNET_HashCode *key,
 150                  const void *xquery,
 151                  size_t xquery_size,
 152                  const struct GNUNET_CONTAINER_BloomFilter *reply_bf,
 153                  uint32_t reply_bf_mutator)
 154 {
 155   if (GNUNET_CONTAINER_heap_get_size (recent_heap) >= DHT_MAX_RECENT)
 156   {
 157     recent_req = GNUNET_CONTAINER_heap_peek (recent_heap);
 158     GNUNET_assert (recent_req != NULL);
 159     GNUNET_SCHEDULER_cancel (recent_req->remove_task);
 160     GNUNET_CONTAINER_heap_remove_node (recent_req->heap_node);
 161     GNUNET_CONTAINER_bloomfilter_free (recent_req->bloom);
 162     GNUNET_free (recent_req);
 163   }
 164
 165   recent_req = GNUNET_malloc (sizeof (struct RecentRequest));
 166   recent_req->uid = msg_ctx->unique_id;
 167   memcpy (&recent_req->key, &msg_ctx->key, sizeof (GNUNET_HashCode));
 168   recent_req->heap_node =
 169     GNUNET_CONTAINER_heap_insert (recent_heap, recent_req,
 170                                   GNUNET_TIME_absolute_get ().abs_value);
 171   recent_req->bloom =
 172     GNUNET_CONTAINER_bloomfilter_init (NULL, DHT_BLOOM_SIZE, DHT_BLOOM_K);
 173
 174
 175 }
 176
 177
 178 /**
 179  * Initialize routing subsystem.
 180  */
 181 void
 182 GDS_ROUTING_init ()
 183 {
 184   recent_heap =
 185     GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN);
 186   recent_map =
 187       GNUNET_CONTAINER_multihashmap_create (MAX_BUCKETS / 8);
 188 }
 189
 190
 191 /**
 192  * Shutdown routing subsystem.
 193  */
 194 void
 195 GDS_ROUTING_done ()
 196 {
 197   while (GNUNET_CONTAINER_heap_get_size (recent_heap) > 0)
 198   {
 199     recent_req = GNUNET_CONTAINER_heap_peek (recent_heap);
 200     GNUNET_assert (recent_req != NULL);
 201     GNUNET_CONTAINER_heap_remove_node (recent_req->heap_node);
 202     GNUNET_CONTAINER_bloomfilter_free (recent_req->bloom);
 203     GNUNET_free (recent_req);
 204   }
 205   GNUNET_CONTAINER_heap_destroy (recent_heap);
 206   recent_heap = NULL;
 207   GNUNET_CONTAINER_multihashmap_destroy (recent_map);
 208   recent_map = NULL;
 209 }
 210
 211 /* end of gnunet-service-dht_routing.c */