GNUnet  0.11.x
gnunet-service-dht_routing.c
Go to the documentation of this file.
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 
26 #include "platform.h"
29 #include "gnunet-service-dht.h"
30 
31 
35 #define DHT_MAX_RECENT (1024 * 16)
36 
37 
43 {
48 
52  struct GNUNET_HashCode key;
53 
58 
63 
68 
73  const void *xquery;
74 
78  size_t xquery_size;
79 
84 };
85 
86 
91 
96 
97 
102 {
107 
112 
116  const void *data;
117 
122 
126  unsigned int put_path_length;
127 
131  unsigned int get_path_length;
132 
136  size_t data_size;
137 
141  enum GNUNET_BLOCK_Type type;
142 };
143 
144 
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;
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 ... */
190  pc->data,
191  pc->data_size,
192  &hc);
193  eval_key = &hc;
194  }
195  else
196  {
197  eval_key = key;
198  }
199  eval
201  pc->type,
202  rr->bg,
204  eval_key,
205  rr->xquery,
206  rr->xquery_size,
207  pc->data,
208  pc->data_size);
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  {
220  ("# Good REPLIES matched against routing table"),
221  1, GNUNET_NO);
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 
235  (
236  "# Duplicate REPLIES matched against routing table"),
237  1, GNUNET_NO);
238  return GNUNET_OK;
239 
243  (
244  "# Invalid REPLIES matched against routing table"),
245  1, GNUNET_NO);
246  return GNUNET_SYSERR;
247 
251  (
252  "# Irrelevant REPLIES matched against routing table"),
253  1, GNUNET_NO);
254  return GNUNET_OK;
255 
257  GNUNET_break (0);
258  return GNUNET_OK;
259 
261  GNUNET_break (0);
262  return GNUNET_OK;
263 
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 
297 void
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  }
329  key,
330  &process,
331  &pc);
332 }
333 
334 
340 static void
342 {
343  struct RecentRequest *recent_req;
344 
347  ("# Entries removed from routing table"), 1,
348  GNUNET_NO);
350  GNUNET_assert (recent_req != NULL);
352  GNUNET_BLOCK_group_destroy (recent_req->bg);
355  &recent_req->key,
356  recent_req));
357  GNUNET_free (recent_req);
358 }
359 
360 
371 static int
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;
389  rr->bg));
390  rr->bg = in->bg;
391  GNUNET_free (in);
392  return GNUNET_SYSERR;
393 }
394 
395 
408 void
409 GDS_ROUTING_add (const struct GNUNET_PeerIdentity *sender,
410  enum GNUNET_BLOCK_Type type,
411  struct GNUNET_BLOCK_Group *bg,
413  const struct GNUNET_HashCode *key,
414  const void *xquery,
415  size_t xquery_size)
416 {
417  struct RecentRequest *recent_req;
418 
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 ==
438  key,
440  recent_req))
441  {
444  ("# DHT requests combined"),
445  1, GNUNET_NO);
446  return;
447  }
448  recent_req->heap_node
450  recent_req,
451  GNUNET_TIME_absolute_get ().abs_value_us);
453  key,
454  recent_req,
456 }
457 
458 
462 void
464 {
467  GNUNET_NO);
468 }
469 
470 
474 void
476 {
481  recent_heap = NULL;
484  recent_map = NULL;
485 }
486 
487 
488 /* end of gnunet-service-dht_routing.c */
struct GNUNET_GETOPT_CommandLineOption options[]
Definition: 002.c:5
#define gettext_noop(String)
Definition: gettext.h:69
static size_t data_size
Number of bytes in data.
Definition: gnunet-abd.c:187
struct GNUNET_HashCode key
The key used in the DHT.
uint32_t data
The data value.
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.
void GDS_NEIGHBOURS_handle_reply(const struct GNUNET_PeerIdentity *target, enum GNUNET_BLOCK_Type type, struct GNUNET_TIME_Absolute expiration_time, const struct GNUNET_HashCode *key, unsigned int put_path_length, const struct GNUNET_PeerIdentity *put_path, unsigned int get_path_length, const struct GNUNET_PeerIdentity *get_path, const void *data, size_t data_size)
Handle a reply (route to origin).
GNUnet DHT routing code.
void GDS_ROUTING_process(enum GNUNET_BLOCK_Type type, struct GNUNET_TIME_Absolute expiration_time, const struct GNUNET_HashCode *key, unsigned int put_path_length, const struct GNUNET_PeerIdentity *put_path, unsigned int get_path_length, const struct GNUNET_PeerIdentity *get_path, const void *data, size_t data_size)
Handle a reply (route to origin).
static int 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).
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 struct GNUNET_CONTAINER_MultiHashMap * recent_map
Recently seen requests by key.
static struct GNUNET_CONTAINER_Heap * recent_heap
Recent requests by time inserted.
static void expire_oldest_entry()
Remove the oldest entry from the DHT routing table.
static int process(void *cls, const struct GNUNET_HashCode *key, void *value)
Forward the result to the given peer if it matches the request.
void GDS_ROUTING_init()
Initialize routing subsystem.
GNUnet DHT tracking of requests for routing replies.
#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_OK
Definition: gnunet_common.h:95
@ GNUNET_YES
Definition: gnunet_common.h:97
@ GNUNET_NO
Definition: gnunet_common.h:94
@ GNUNET_SYSERR
Definition: gnunet_common.h:93
void GNUNET_BLOCK_group_destroy(struct GNUNET_BLOCK_Group *bg)
Destroy resources used by a block group.
Definition: block.c:206
int GNUNET_BLOCK_get_key(struct GNUNET_BLOCK_Context *ctx, enum GNUNET_BLOCK_Type type, const void *block, size_t block_size, struct GNUNET_HashCode *key)
Function called to obtain the key for a block.
Definition: block.c:379
enum GNUNET_BLOCK_EvaluationResult GNUNET_BLOCK_evaluate(struct GNUNET_BLOCK_Context *ctx, enum GNUNET_BLOCK_Type type, struct GNUNET_BLOCK_Group *group, enum GNUNET_BLOCK_EvaluationOptions eo, 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 a reply or a request.
Definition: block.c:339
int GNUNET_BLOCK_group_merge(struct GNUNET_BLOCK_Group *bg1, struct GNUNET_BLOCK_Group *bg2)
Try merging two block groups.
Definition: block.c:227
GNUNET_BLOCK_EvaluationResult
Possible ways for how a block may relate to a query.
GNUNET_BLOCK_Type
Blocks in the datastore and the datacache must have a unique type.
@ GNUNET_BLOCK_EVALUATION_RESULT_INVALID
Block does not match query (invalid result)
@ GNUNET_BLOCK_EVALUATION_REQUEST_INVALID
Query format does not match block type (invalid query).
@ GNUNET_BLOCK_EVALUATION_OK_LAST
Last possible valid result.
@ GNUNET_BLOCK_EVALUATION_OK_MORE
Valid result, and there may be more.
@ GNUNET_BLOCK_EVALUATION_RESULT_IRRELEVANT
Block does not match xquery (valid result, not relevant for the request)
@ GNUNET_BLOCK_EVALUATION_OK_DUPLICATE
Valid result, but suppressed because it is a duplicate.
@ GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED
Specified block type not supported by this plugin.
@ GNUNET_BLOCK_EVALUATION_REQUEST_VALID
Query is valid, no reply given.
@ GNUNET_BLOCK_EO_NONE
Default behavior.
@ GNUNET_BLOCK_TYPE_ANY
Any type of block, used as a wildcard when searching.
@ GNUNET_BLOCK_TYPE_DHT_HELLO
Type of a block that contains a HELLO for a peer (for DHT and CADET find-peer operations).
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_PEER
This is a 'FIND-PEER' request, so approximate results are fine.
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.
int 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.
struct GNUNET_CONTAINER_MultiHashMap * GNUNET_CONTAINER_multihashmap_create(unsigned int len, int do_not_copy_keys)
Create a multi hash map.
int 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.
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_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:86
Block group data.
Handle to a node in a heap.
Internal representation of the hash map.
A 512-bit hashcode.
The identity of the host (wraps the signing key of the peer).
Time for absolute times used by GNUnet, in microseconds.
Closure for the 'process' function.
const struct GNUNET_PeerIdentity * put_path
Path of the original PUT.
const void * data
Payload of the reply.
struct GNUNET_TIME_Absolute expiration_time
Expiration time of the result.
unsigned int put_path_length
Number of entries in put_path.
size_t data_size
Number of bytes in data.
enum GNUNET_BLOCK_Type type
Type of the reply.
const struct GNUNET_PeerIdentity * get_path
Path of the reply.
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