diff options
Diffstat (limited to 'src/dht/gnunet-service-dht_routing.c')
-rw-r--r-- | src/dht/gnunet-service-dht_routing.c | 488 |
1 files changed, 0 insertions, 488 deletions
diff --git a/src/dht/gnunet-service-dht_routing.c b/src/dht/gnunet-service-dht_routing.c deleted file mode 100644 index b05fb76d3..000000000 --- a/src/dht/gnunet-service-dht_routing.c +++ /dev/null | |||
@@ -1,488 +0,0 @@ | |||
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 mismatch */ | ||
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 */ | ||