GNUnet  0.17.6
gnunet-service-dht_routing.c
Go to the documentation of this file.
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 
26 #include "platform.h"
29 #include "gnunet-service-dht.h"
30 #include "gnunet_block_group_lib.h"
31 
32 
37 #define DHT_MAX_RECENT (1024 * 128)
38 
39 
45 {
50 
54  struct GNUNET_HashCode key;
55 
60 
65 
70  const void *xquery;
71 
75  size_t xquery_size;
76 
81 
86 };
87 
88 
93 
98 
99 
104 {
108  const struct GNUNET_DATACACHE_Block *bd;
109 
114 
118  unsigned int get_path_length;
119 
120 };
121 
122 
131 static enum GNUNET_GenericReturnValue
132 process (void *cls,
133  const struct GNUNET_HashCode *query_hash,
134  void *value)
135 {
136  struct ProcessContext *pc = cls;
137  struct RecentRequest *rr = value;
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  {
160  "# Inexact matches discarded in exact search",
161  1,
162  GNUNET_NO);
163  return GNUNET_OK; /* exact search, but inexact match */
164  }
166  bdx.type,
167  rr->bg,
168  &bdx.key,
169  rr->xquery,
170  rr->xquery_size,
171  bdx.data,
172  bdx.data_size);
174  "Result for %s of type %d was evaluated as %d\n",
175  GNUNET_h2s (&bdx.key),
176  bdx.type,
177  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 
185  bdx.data_size,
186  &chash);
187  if (GNUNET_YES ==
189  &chash))
191  else
193  }
194  switch (eval)
195  {
199  {
200  struct PeerInfo *pi;
201 
203  "# Good REPLIES matched against routing table",
204  1,
205  GNUNET_NO);
207  if (NULL == pi)
208  {
209  /* peer disconnected in the meantime, drop reply */
211  "No matching peer for reply for key %s\n",
212  GNUNET_h2s (query_hash));
213  return GNUNET_OK;
214  }
216  &bdx,
217  query_hash,
218  get_path_length,
219  pc->get_path));
220  }
221  break;
224  "# Duplicate REPLIES matched against routing table",
225  1,
226  GNUNET_NO);
227  return GNUNET_OK;
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 
254 void
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 
267  query_hash,
268  &process,
269  &pc);
270 }
271 
272 
278 static void
280 {
281  struct RecentRequest *recent_req;
282 
284  "# Old entries removed from routing table",
285  1,
286  GNUNET_NO);
288  GNUNET_assert (recent_req != NULL);
290  GNUNET_BLOCK_group_destroy (recent_req->bg);
293  &recent_req->key,
294  recent_req));
295  GNUNET_free (recent_req);
296 }
297 
298 
309 static enum GNUNET_GenericReturnValue
310 try_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;
327  rr->bg));
328  rr->bg = in->bg;
329  GNUNET_free (in);
330  return GNUNET_SYSERR;
331 }
332 
333 
347 void
348 GDS_ROUTING_add (const struct GNUNET_PeerIdentity *sender,
349  enum GNUNET_BLOCK_Type type,
350  struct GNUNET_BLOCK_Group *bg,
352  const struct GNUNET_HashCode *key,
353  const void *xquery,
354  size_t xquery_size)
355 {
356  struct RecentRequest *recent_req;
357 
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 ==
377  key,
379  recent_req))
380  {
382  "# DHT requests combined",
383  1,
384  GNUNET_NO);
385  return;
386  }
387  recent_req->heap_node
389  recent_heap,
390  recent_req,
391  GNUNET_TIME_absolute_get ().abs_value_us);
393  recent_map,
394  key,
395  recent_req,
397 }
398 
399 
403 void
405 {
408  GNUNET_NO);
409 }
410 
411 
415 void
417 {
420  GNUNET_assert (0 ==
423  recent_heap = NULL;
424  GNUNET_assert (0 ==
427  recent_map = NULL;
428 }
429 
430 
431 /* end of gnunet-service-dht_routing.c */
struct GNUNET_GETOPT_CommandLineOption options[]
Definition: 002.c:5
GNUNET_BLOCK_Type
WARNING: This header is generated! In order to add DHT block types, you must register them in GANA,...
@ GNUNET_BLOCK_TYPE_ANY
Identifier for any block.
static struct GNUNET_PEERINFO_Handle * pi
Handle to peerinfo service.
struct GNUNET_HashCode key
The key used in the DHT.
static char * value
Value of the record to add/remove.
static struct GNUNET_FS_PublishContext * pc
Handle to FS-publishing operation.
GNUnet DHT globals.
struct GNUNET_STATISTICS_Handle * GDS_stats
Handle for the statistics service.
struct GNUNET_BLOCK_Context * GDS_block_context
Our handle to the BLOCK library.
bool GDS_NEIGHBOURS_handle_reply(struct PeerInfo *pi, const struct GNUNET_DATACACHE_Block *bd, const struct GNUNET_HashCode *query_hash, unsigned int get_path_length, const struct GNUNET_DHT_PathElement *get_path)
Handle a reply (route to origin).
struct PeerInfo * GDS_NEIGHBOURS_lookup_peer(const struct GNUNET_PeerIdentity *target)
Lookup peer by peer's identity.
GNUnet DHT routing code.
static enum GNUNET_GenericReturnValue try_combine_recent(void *cls, const struct GNUNET_HashCode *key, void *value)
Try to combine multiple recent requests for the same value (if they come from the same peer).
static enum GNUNET_GenericReturnValue process(void *cls, const struct GNUNET_HashCode *query_hash, void *value)
Forward the result to the given peer if it matches the request.
void GDS_ROUTING_done()
Shutdown routing subsystem.
void GDS_ROUTING_add(const struct GNUNET_PeerIdentity *sender, enum GNUNET_BLOCK_Type type, struct GNUNET_BLOCK_Group *bg, enum GNUNET_DHT_RouteOption options, const struct GNUNET_HashCode *key, const void *xquery, size_t xquery_size)
Add a new entry to our routing table.
#define DHT_MAX_RECENT
Number of requests we track at most (for routing replies).
static void expire_oldest_entry(void)
Remove the oldest entry from the DHT routing table.
static struct GNUNET_CONTAINER_MultiHashMap * recent_map
Recently seen requests by key.
static struct GNUNET_CONTAINER_Heap * recent_heap
Recent requests by time inserted.
void GDS_ROUTING_process(const struct GNUNET_DATACACHE_Block *bd, const struct GNUNET_HashCode *query_hash, unsigned int get_path_length, const struct GNUNET_DHT_PathElement *get_path)
Handle a reply (route to origin).
void GDS_ROUTING_init()
Initialize routing subsystem.
GNUnet DHT tracking of requests for routing replies.
enum GNUNET_BLOCK_ReplyEvaluationResult GNUNET_BLOCK_check_reply(struct GNUNET_BLOCK_Context *ctx, enum GNUNET_BLOCK_Type type, struct GNUNET_BLOCK_Group *group, const struct GNUNET_HashCode *query, const void *xquery, size_t xquery_size, const void *reply_block, size_t reply_block_size)
Function called to validate if a reply is good for a particular query.
Definition: block.c:334
enum GNUNET_GenericReturnValue GNUNET_BLOCK_GROUP_bf_test_and_set(struct GNUNET_BLOCK_Group *bg, const struct GNUNET_HashCode *hc)
Test if hc is contained in the Bloom filter of bg.
Definition: bg_bf.c:232
GNUNET_BLOCK_ReplyEvaluationResult
Possible ways for how a block may relate to a query.
enum GNUNET_GenericReturnValue GNUNET_BLOCK_group_merge(struct GNUNET_BLOCK_Group *bg1, struct GNUNET_BLOCK_Group *bg2)
Try merging two block groups.
Definition: block.c:201
void GNUNET_BLOCK_group_destroy(struct GNUNET_BLOCK_Group *bg)
Destroy resources used by a block group.
Definition: block.c:192
@ GNUNET_BLOCK_REPLY_OK_MORE
Valid result, and there may be more.
@ GNUNET_BLOCK_REPLY_OK_DUPLICATE
Valid result, but suppressed because it is a duplicate.
@ GNUNET_BLOCK_REPLY_OK_LAST
Last possible valid result.
@ GNUNET_BLOCK_REPLY_TYPE_NOT_SUPPORTED
Specified block type not supported by any plugin.
@ GNUNET_BLOCK_REPLY_IRRELEVANT
Block does not match xquery (valid result, not relevant for the request)
GNUNET_DHT_RouteOption
Options for routing.
@ GNUNET_DHT_RO_RECORD_ROUTE
We should keep track of the route that the message took in the P2P network.
@ GNUNET_DHT_RO_FIND_APPROXIMATE
Approximate results are fine.
void GNUNET_CRYPTO_hash(const void *block, size_t size, struct GNUNET_HashCode *ret)
Compute hash of a given block.
Definition: crypto_hash.c:41
int GNUNET_CONTAINER_multihashmap_get_multiple(struct GNUNET_CONTAINER_MultiHashMap *map, const struct GNUNET_HashCode *key, GNUNET_CONTAINER_MulitHashMapIteratorCallback it, void *it_cls)
Iterate over all entries in the map that match a particular key.
enum GNUNET_GenericReturnValue GNUNET_CONTAINER_multihashmap_remove(struct GNUNET_CONTAINER_MultiHashMap *map, const struct GNUNET_HashCode *key, const void *value)
Remove the given key-value pair from the map.
enum GNUNET_GenericReturnValue GNUNET_CONTAINER_multihashmap_put(struct GNUNET_CONTAINER_MultiHashMap *map, const struct GNUNET_HashCode *key, void *value, enum GNUNET_CONTAINER_MultiHashMapOption opt)
Store a key-value pair in the map.
struct GNUNET_CONTAINER_MultiHashMap * GNUNET_CONTAINER_multihashmap_create(unsigned int len, int do_not_copy_keys)
Create a multi hash map.
unsigned int GNUNET_CONTAINER_multihashmap_size(const struct GNUNET_CONTAINER_MultiHashMap *map)
Get the number of key-value pairs in the map.
void GNUNET_CONTAINER_multihashmap_destroy(struct GNUNET_CONTAINER_MultiHashMap *map)
Destroy a hash map.
@ GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE
Allow multiple values with the same key.
void * GNUNET_CONTAINER_heap_remove_node(struct GNUNET_CONTAINER_HeapNode *node)
Removes a node from the heap.
struct GNUNET_CONTAINER_HeapNode * GNUNET_CONTAINER_heap_insert(struct GNUNET_CONTAINER_Heap *heap, void *element, GNUNET_CONTAINER_HeapCostType cost)
Inserts a new element into the heap.
void * GNUNET_CONTAINER_heap_peek(const struct GNUNET_CONTAINER_Heap *heap)
Get element stored at the root of heap.
unsigned int GNUNET_CONTAINER_heap_get_size(const struct GNUNET_CONTAINER_Heap *heap)
Get the current size of the heap.
struct GNUNET_CONTAINER_Heap * GNUNET_CONTAINER_heap_create(enum GNUNET_CONTAINER_HeapOrder order)
Create a new heap.
void GNUNET_CONTAINER_heap_destroy(struct GNUNET_CONTAINER_Heap *heap)
Destroys the heap.
@ GNUNET_CONTAINER_HEAP_ORDER_MIN
Heap with the minimum cost at the root.
#define GNUNET_log(kind,...)
#define GNUNET_memcmp(a, b)
Compare memory in a and b, where both must be of the same pointer type.
#define GNUNET_memcpy(dst, src, n)
Call memcpy() but check for n being 0 first.
GNUNET_GenericReturnValue
Named constants for return values.
Definition: gnunet_common.h:96
@ GNUNET_OK
Definition: gnunet_common.h:99
@ GNUNET_YES
@ GNUNET_NO
Definition: gnunet_common.h:98
@ GNUNET_SYSERR
Definition: gnunet_common.h:97
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
#define GNUNET_break(cond)
Use this for internal assertion violations that are not fatal (can be handled) but should not occur.
const char * GNUNET_h2s(const struct GNUNET_HashCode *hc)
Convert a hash value to a string (for printing debug messages).
@ GNUNET_ERROR_TYPE_DEBUG
#define GNUNET_malloc(size)
Wrapper around malloc.
#define GNUNET_free(ptr)
Wrapper around free.
void GNUNET_STATISTICS_update(struct GNUNET_STATISTICS_Handle *handle, const char *name, int64_t delta, int make_persistent)
Set statistic value for the peer.
struct GNUNET_TIME_Absolute GNUNET_TIME_absolute_get(void)
Get the current time.
Definition: time.c:110
Block group data.
Handle to a node in a heap.
Internal representation of the hash map.
Information about a block stored in the datacache.
const struct GNUNET_DHT_PathElement * put_path
PUT path taken by the block, array of peer identities.
enum GNUNET_BLOCK_Type type
Type of the block.
const void * data
Actual block data.
struct GNUNET_HashCode key
Key of the block.
size_t data_size
Number of bytes in data.
unsigned int put_path_length
Length of the put_path array.
A (signed) path tracking a block's flow through the DHT is represented by an array of path elements,...
A 512-bit hashcode.
The identity of the host (wraps the signing key of the peer).
Entry for a peer in a bucket.
Closure for the process() function.
const struct GNUNET_DHT_PathElement * get_path
Path of the reply.
const struct GNUNET_DATACACHE_Block * bd
Block data.
unsigned int get_path_length
Number of entries in get_path.
Information we keep about all recent GET requests so that we can route replies.
size_t xquery_size
Number of bytes in xquery.
enum GNUNET_BLOCK_Type type
Type of the requested block.
struct GNUNET_HashCode key
Key of this request.
struct GNUNET_BLOCK_Group * bg
Block group for filtering replies.
struct GNUNET_CONTAINER_HeapNode * heap_node
Position of this node in the min heap.
enum GNUNET_DHT_RouteOption options
Request options.
struct GNUNET_PeerIdentity peer
The peer this request was received from.
const void * xquery
extended query (see gnunet_block_lib.h).
enum GNUNET_TESTBED_UnderlayLinkModelType type
the type of this model