2 This file is part of GNUnet.
3 (C) 2011 Christian Grothoff (and other contributing authors)
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.
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.
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.
22 * @file dht/gnunet-service-dht_routing.c
23 * @brief GNUnet DHT tracking of requests for routing replies
24 * @author Christian Grothoff
27 #include "gnunet-service-dht_neighbours.h"
28 #include "gnunet-service-dht_routing.h"
29 #include "gnunet-service-dht.h"
33 * Number of requests we track at most (for routing replies).
35 #define DHT_MAX_RECENT (1024 * 16)
39 * Information we keep about all recent GET requests
40 * so that we can route replies.
46 * The peer this request was received from.
48 struct GNUNET_PeerIdentity peer;
51 * Key of this request.
56 * Position of this node in the min heap.
58 struct GNUNET_CONTAINER_HeapNode *heap_node;
61 * Bloomfilter for replies to drop.
63 struct GNUNET_CONTAINER_BloomFilter *reply_bf;
66 * Type of the requested block.
68 enum GNUNET_BLOCK_Type type;
71 * extended query (see gnunet_block_lib.h). Allocated at the
77 * Number of bytes in xquery.
82 * Mutator value for the reply_bf, see gnunet_block_lib.h
84 uint32_t reply_bf_mutator;
89 enum GNUNET_DHT_RouteOption options;
95 * Recent requests by time inserted.
97 static struct GNUNET_CONTAINER_Heap *recent_heap;
100 * Recently seen requests by key.
102 static struct GNUNET_CONTAINER_MultiHashMap *recent_map;
106 * Closure for the 'process' function.
108 struct ProcessContext
111 * Path of the original PUT
113 const struct GNUNET_PeerIdentity *put_path;
118 const struct GNUNET_PeerIdentity *get_path;
121 * Payload of the reply.
126 * Expiration time of the result.
128 struct GNUNET_TIME_Absolute expiration_time;
131 * Number of entries in 'put_path'.
133 unsigned int put_path_length;
136 * Number of entries in 'get_path'.
138 unsigned int get_path_length;
141 * Number of bytes in 'data'.
148 enum GNUNET_BLOCK_Type type;
154 * Forward the result to the given peer if it matches the request.
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
164 const GNUNET_HashCode *key,
167 struct ProcessContext *pc = cls;
168 struct RecentRequest *rr = value;
169 enum GNUNET_BLOCK_EvaluationResult eval;
173 const GNUNET_HashCode *eval_key;
175 if ( (rr->type != GNUNET_BLOCK_TYPE_ANY) &&
176 (rr->type != pc->type) )
177 return GNUNET_OK; /* type missmatch */
179 if (0 != (rr->options & GNUNET_DHT_RO_RECORD_ROUTE))
181 gpl = pc->get_path_length;
182 ppl = pc->put_path_length;
189 if ( (0 != (rr->options & GNUNET_DHT_RO_FIND_PEER)) &&
190 (pc->type == GNUNET_BLOCK_TYPE_DHT_HELLO) )
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,
206 eval = GNUNET_BLOCK_evaluate (GDS_block_context,
210 rr->reply_bf_mutator,
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,
222 GDS_NEIGHBOURS_handle_reply (&rr->peer,
233 case GNUNET_BLOCK_EVALUATION_OK_DUPLICATE:
234 GNUNET_STATISTICS_update (GDS_stats,
235 gettext_noop ("# Duplicate REPLIES matched against routing table"), 1,
238 case GNUNET_BLOCK_EVALUATION_RESULT_INVALID:
239 GNUNET_STATISTICS_update (GDS_stats,
240 gettext_noop ("# Invalid REPLIES matched against routing table"), 1,
242 return GNUNET_SYSERR;
243 case GNUNET_BLOCK_EVALUATION_REQUEST_VALID:
244 case GNUNET_BLOCK_EVALUATION_REQUEST_INVALID:
247 case GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED:
248 GNUNET_STATISTICS_update (GDS_stats,
249 gettext_noop ("# Unsupported REPLIES matched against routing table"), 1,
251 return GNUNET_SYSERR;
254 return GNUNET_SYSERR;
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
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
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,
288 struct ProcessContext pc;
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;
297 pc.data_size = data_size;
298 GNUNET_CONTAINER_multihashmap_get_multiple (recent_map,
306 * Add a new entry to our routing table.
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
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,
324 const struct GNUNET_CONTAINER_BloomFilter *reply_bf,
325 uint32_t reply_bf_mutator)
327 struct RecentRequest *recent_req;
329 while (GNUNET_CONTAINER_heap_get_size (recent_heap) >= DHT_MAX_RECENT)
331 GNUNET_STATISTICS_update (GDS_stats,
332 gettext_noop ("# Entries removed from routing table"), 1,
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);
341 GNUNET_STATISTICS_update (GDS_stats,
342 gettext_noop ("# Entries added to routing table"), 1,
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,
360 GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE);
367 * Initialize routing subsystem.
373 GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN);
375 GNUNET_CONTAINER_multihashmap_create (DHT_MAX_RECENT * 4 / 3);
380 * Shutdown routing subsystem.
385 struct RecentRequest *recent_req;
387 while (GNUNET_CONTAINER_heap_get_size (recent_heap) > 0)
389 GNUNET_STATISTICS_update (GDS_stats,
390 gettext_noop ("# Entries removed from routing table"), 1,
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);
398 GNUNET_assert (0 == GNUNET_CONTAINER_heap_get_size (recent_heap));
399 GNUNET_CONTAINER_heap_destroy (recent_heap);
401 GNUNET_CONTAINER_multihashmap_destroy (recent_map);
405 /* end of gnunet-service-dht_routing.c */