aboutsummaryrefslogtreecommitdiff
path: root/src/dht/gnunet-service-dht_routing.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/dht/gnunet-service-dht_routing.c')
-rw-r--r--src/dht/gnunet-service-dht_routing.c431
1 files changed, 0 insertions, 431 deletions
diff --git a/src/dht/gnunet-service-dht_routing.c b/src/dht/gnunet-service-dht_routing.c
deleted file mode 100644
index 8f87751bb..000000000
--- a/src/dht/gnunet-service-dht_routing.c
+++ /dev/null
@@ -1,431 +0,0 @@
1/*
2 This file is part of GNUnet.
3 Copyright (C) 2011, 2022 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#include "gnunet_block_group_lib.h"
31
32
33/**
34 * Number of requests we track at most (for routing replies).
35 * TODO: make configurable!
36 */
37#define DHT_MAX_RECENT (1024 * 128)
38
39
40/**
41 * Information we keep about all recent GET requests
42 * so that we can route replies.
43 */
44struct RecentRequest
45{
46 /**
47 * The peer this request was received from.
48 */
49 struct GNUNET_PeerIdentity peer;
50
51 /**
52 * Key of this request.
53 */
54 struct GNUNET_HashCode key;
55
56 /**
57 * Position of this node in the min heap.
58 */
59 struct GNUNET_CONTAINER_HeapNode *heap_node;
60
61 /**
62 * Block group for filtering replies.
63 */
64 struct GNUNET_BLOCK_Group *bg;
65
66 /**
67 * extended query (see gnunet_block_lib.h). Allocated at the
68 * end of this struct.
69 */
70 const void *xquery;
71
72 /**
73 * Number of bytes in xquery.
74 */
75 size_t xquery_size;
76
77 /**
78 * Type of the requested block.
79 */
80 enum GNUNET_BLOCK_Type type;
81
82 /**
83 * Request options.
84 */
85 enum GNUNET_DHT_RouteOption options;
86};
87
88
89/**
90 * Recent requests by time inserted.
91 */
92static struct GNUNET_CONTAINER_Heap *recent_heap;
93
94/**
95 * Recently seen requests by key.
96 */
97static struct GNUNET_CONTAINER_MultiHashMap *recent_map;
98
99
100/**
101 * Closure for the process() function.
102 */
103struct ProcessContext
104{
105 /**
106 * Block data.
107 */
108 const struct GNUNET_DATACACHE_Block *bd;
109
110 /**
111 * Path of the reply.
112 */
113 const struct GNUNET_DHT_PathElement *get_path;
114
115 /**
116 * Number of entries in @e get_path.
117 */
118 unsigned int get_path_length;
119
120};
121
122
123/**
124 * Forward the result to the given peer if it matches the request.
125 *
126 * @param cls the `struct ProcessContext` with the result
127 * @param query_hash the hash from the original query
128 * @param value the `struct RecentRequest` with the request
129 * @return #GNUNET_OK (continue to iterate)
130 */
131static enum GNUNET_GenericReturnValue
132process (void *cls,
133 const struct GNUNET_HashCode *query_hash,
134 void *value)
135{
136 struct ProcessContext *pc = cls;
137 struct RecentRequest *rr = value;
138 enum GNUNET_BLOCK_ReplyEvaluationResult eval;
139 unsigned int get_path_length;
140 struct GNUNET_DATACACHE_Block bdx = *pc->bd;
141
142 if ( (rr->type != GNUNET_BLOCK_TYPE_ANY) &&
143 (rr->type != pc->bd->type) )
144 return GNUNET_OK; /* type mismatch */
145 if (0 != (rr->options & GNUNET_DHT_RO_RECORD_ROUTE))
146 {
147 get_path_length = pc->get_path_length;
148 }
149 else
150 {
151 get_path_length = 0;
152 bdx.put_path_length = 0;
153 bdx.put_path = NULL;
154 }
155 if ( (0 == (rr->options & GNUNET_DHT_RO_FIND_APPROXIMATE)) &&
156 (0 != GNUNET_memcmp (query_hash,
157 &bdx.key)) )
158 {
159 GNUNET_STATISTICS_update (GDS_stats,
160 "# Inexact matches discarded in exact search",
161 1,
162 GNUNET_NO);
163 return GNUNET_OK; /* exact search, but inexact match */
164 }
165 eval = GNUNET_BLOCK_check_reply (GDS_block_context,
166 bdx.type,
167 rr->bg,
168 &bdx.key,
169 rr->xquery,
170 rr->xquery_size,
171 bdx.data,
172 bdx.data_size);
173 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
174 "Result for %s of type %d was evaluated as %d\n",
175 GNUNET_h2s (&bdx.key),
176 bdx.type,
177 eval);
178 if (GNUNET_BLOCK_REPLY_TYPE_NOT_SUPPORTED == eval)
179 {
180 /* If we do not know the block type, we still filter
181 exact duplicates by the block content */
182 struct GNUNET_HashCode chash;
183
184 GNUNET_CRYPTO_hash (bdx.data,
185 bdx.data_size,
186 &chash);
187 if (GNUNET_YES ==
188 GNUNET_BLOCK_GROUP_bf_test_and_set (rr->bg,
189 &chash))
190 eval = GNUNET_BLOCK_REPLY_OK_DUPLICATE;
191 else
192 eval = GNUNET_BLOCK_REPLY_OK_MORE;
193 }
194 switch (eval)
195 {
196 case GNUNET_BLOCK_REPLY_OK_MORE:
197 case GNUNET_BLOCK_REPLY_OK_LAST:
198 case GNUNET_BLOCK_REPLY_TYPE_NOT_SUPPORTED:
199 {
200 struct PeerInfo *pi;
201
202 GNUNET_STATISTICS_update (GDS_stats,
203 "# Good REPLIES matched against routing table",
204 1,
205 GNUNET_NO);
206 pi = GDS_NEIGHBOURS_lookup_peer (&rr->peer);
207 if (NULL == pi)
208 {
209 /* peer disconnected in the meantime, drop reply */
210 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
211 "No matching peer for reply for key %s\n",
212 GNUNET_h2s (query_hash));
213 return GNUNET_OK;
214 }
215 GNUNET_break (GDS_NEIGHBOURS_handle_reply (pi,
216 &bdx,
217 query_hash,
218 get_path_length,
219 pc->get_path));
220 }
221 break;
222 case GNUNET_BLOCK_REPLY_OK_DUPLICATE:
223 GNUNET_STATISTICS_update (GDS_stats,
224 "# Duplicate REPLIES matched against routing table",
225 1,
226 GNUNET_NO);
227 return GNUNET_OK;
228 case GNUNET_BLOCK_REPLY_IRRELEVANT:
229 GNUNET_STATISTICS_update (GDS_stats,
230 "# Irrelevant REPLIES matched against routing table",
231 1,
232 GNUNET_NO);
233 return GNUNET_OK;
234 default:
235 GNUNET_break (0);
236 return GNUNET_OK;
237 }
238 return GNUNET_OK;
239}
240
241
242/**
243 * Handle a reply (route to origin). Only forwards the reply back to
244 * other peers waiting for it. Does not do local caching or
245 * forwarding to local clients. Essentially calls
246 * GDS_NEIGHBOURS_handle_reply() for all peers that sent us a matching
247 * request recently.
248 *
249 * @param bd block details
250 * @param query_hash query used in the inquiry
251 * @param get_path_length number of entries in @a get_path
252 * @param get_path peers this reply has traversed so far (if tracked)
253 */
254void
255GDS_ROUTING_process (const struct GNUNET_DATACACHE_Block *bd,
256 const struct GNUNET_HashCode *query_hash,
257 unsigned int get_path_length,
258 const struct GNUNET_DHT_PathElement *get_path)
259{
260 struct ProcessContext pc = {
261 .bd = bd,
262 .get_path = get_path,
263 .get_path_length = get_path_length
264 };
265
266 GNUNET_CONTAINER_multihashmap_get_multiple (recent_map,
267 query_hash,
268 &process,
269 &pc);
270}
271
272
273/**
274 * Remove the oldest entry from the DHT routing table. Must only
275 * be called if it is known that there is at least one entry
276 * in the heap and hashmap.
277 */
278static void
279expire_oldest_entry (void)
280{
281 struct RecentRequest *recent_req;
282
283 GNUNET_STATISTICS_update (GDS_stats,
284 "# Old entries removed from routing table",
285 1,
286 GNUNET_NO);
287 recent_req = GNUNET_CONTAINER_heap_peek (recent_heap);
288 GNUNET_assert (recent_req != NULL);
289 GNUNET_CONTAINER_heap_remove_node (recent_req->heap_node);
290 GNUNET_BLOCK_group_destroy (recent_req->bg);
291 GNUNET_assert (GNUNET_YES ==
292 GNUNET_CONTAINER_multihashmap_remove (recent_map,
293 &recent_req->key,
294 recent_req));
295 GNUNET_free (recent_req);
296}
297
298
299/**
300 * Try to combine multiple recent requests for the same value
301 * (if they come from the same peer).
302 *
303 * @param cls the new `struct RecentRequest` (to discard upon successful combination)
304 * @param key the query
305 * @param value the existing `struct RecentRequest` (to update upon successful combination)
306 * @return #GNUNET_OK (continue to iterate),
307 * #GNUNET_SYSERR if the request was successfully combined
308 */
309static enum GNUNET_GenericReturnValue
310try_combine_recent (void *cls,
311 const struct GNUNET_HashCode *key,
312 void *value)
313{
314 struct RecentRequest *in = cls;
315 struct RecentRequest *rr = value;
316
317 if ( (0 != GNUNET_memcmp (&in->peer,
318 &rr->peer)) ||
319 (in->type != rr->type) ||
320 (in->xquery_size != rr->xquery_size) ||
321 (0 != memcmp (in->xquery,
322 rr->xquery,
323 in->xquery_size) ) )
324 return GNUNET_OK;
325 GNUNET_break (GNUNET_SYSERR !=
326 GNUNET_BLOCK_group_merge (in->bg,
327 rr->bg));
328 rr->bg = in->bg;
329 GNUNET_free (in);
330 return GNUNET_SYSERR;
331}
332
333
334/**
335 * Add a new entry to our routing table.
336 *
337 * @param sender peer that originated the request
338 * @param type type of the block
339 * @param[in] bg block group for filtering duplicate replies
340 * @param options options for processing
341 * @param key key for the content
342 * @param xquery extended query
343 * @param xquery_size number of bytes in @a xquery
344 * @param reply_bf bloomfilter to filter duplicates
345 * @param reply_bf_mutator mutator for @a reply_bf
346 */
347void
348GDS_ROUTING_add (const struct GNUNET_PeerIdentity *sender,
349 enum GNUNET_BLOCK_Type type,
350 struct GNUNET_BLOCK_Group *bg,
351 enum GNUNET_DHT_RouteOption options,
352 const struct GNUNET_HashCode *key,
353 const void *xquery,
354 size_t xquery_size)
355{
356 struct RecentRequest *recent_req;
357
358 while (GNUNET_CONTAINER_heap_get_size (recent_heap) >= DHT_MAX_RECENT)
359 expire_oldest_entry ();
360 GNUNET_STATISTICS_update (GDS_stats,
361 "# Entries added to routing table",
362 1,
363 GNUNET_NO);
364 recent_req = GNUNET_malloc (sizeof(struct RecentRequest) + xquery_size);
365 recent_req->peer = *sender;
366 recent_req->key = *key;
367 recent_req->bg = bg;
368 recent_req->type = type;
369 recent_req->options = options;
370 recent_req->xquery = &recent_req[1];
371 GNUNET_memcpy (&recent_req[1],
372 xquery,
373 xquery_size);
374 recent_req->xquery_size = xquery_size;
375 if (GNUNET_SYSERR ==
376 GNUNET_CONTAINER_multihashmap_get_multiple (recent_map,
377 key,
378 &try_combine_recent,
379 recent_req))
380 {
381 GNUNET_STATISTICS_update (GDS_stats,
382 "# DHT requests combined",
383 1,
384 GNUNET_NO);
385 return;
386 }
387 recent_req->heap_node
388 = GNUNET_CONTAINER_heap_insert (
389 recent_heap,
390 recent_req,
391 GNUNET_TIME_absolute_get ().abs_value_us);
392 (void) GNUNET_CONTAINER_multihashmap_put (
393 recent_map,
394 key,
395 recent_req,
396 GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE);
397}
398
399
400/**
401 * Initialize routing subsystem.
402 */
403void
404GDS_ROUTING_init ()
405{
406 recent_heap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN);
407 recent_map = GNUNET_CONTAINER_multihashmap_create (DHT_MAX_RECENT * 4 / 3,
408 GNUNET_NO);
409}
410
411
412/**
413 * Shutdown routing subsystem.
414 */
415void
416GDS_ROUTING_done ()
417{
418 while (GNUNET_CONTAINER_heap_get_size (recent_heap) > 0)
419 expire_oldest_entry ();
420 GNUNET_assert (0 ==
421 GNUNET_CONTAINER_heap_get_size (recent_heap));
422 GNUNET_CONTAINER_heap_destroy (recent_heap);
423 recent_heap = NULL;
424 GNUNET_assert (0 ==
425 GNUNET_CONTAINER_multihashmap_size (recent_map));
426 GNUNET_CONTAINER_multihashmap_destroy (recent_map);
427 recent_map = NULL;
428}
429
430
431/* end of gnunet-service-dht_routing.c */
generated by cgit v1.2.3 (git 2.39.1) at 2024-04-20 05:36:43 +0000