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 
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 
121  struct GNUNET_TIME_Absolute expiration_time;
122 
126  unsigned int put_path_length;
127 
131  unsigned int get_path_length;
132 
136  size_t data_size;
137 
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 missmatch */
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)) &&
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;
313  pc.put_path = put_path;
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);
349  recent_req = GNUNET_CONTAINER_heap_peek (recent_heap);
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 
419  while (GNUNET_CONTAINER_heap_get_size (recent_heap) >= DHT_MAX_RECENT)
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
449  = GNUNET_CONTAINER_heap_insert (recent_heap,
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 {
477  while (GNUNET_CONTAINER_heap_get_size (recent_heap) > 0)
479  GNUNET_assert (0 == GNUNET_CONTAINER_heap_get_size (recent_heap));
480  GNUNET_CONTAINER_heap_destroy (recent_heap);
481  recent_heap = NULL;
484  recent_map = NULL;
485 }
486 
487 
488 /* end of gnunet-service-dht_routing.c */
Block does not match query (invalid result)
GNUnet DHT globals.
struct GNUNET_STATISTICS_Handle * GDS_stats
Handle for the statistics service.
We should keep track of the route that the message took in the P2P network.
unsigned int GNUNET_CONTAINER_multihashmap_size(const struct GNUNET_CONTAINER_MultiHashMap *map)
Get the number of key-value pairs in the map.
Information we keep about all recent GET requests so that we can route replies.
Any type of block, used as a wildcard when searching.
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.
GNUNET_BLOCK_Type
Blocks in the datastore and the datacache must have a unique type.
struct GNUNET_TIME_Absolute expiration_time
Expiration time of the result.
static size_t data_size
Number of bytes in data.
Definition: gnunet-abd.c:187
const void * data
Payload of the reply.
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
#define GNUNET_memcpy(dst, src, n)
Call memcpy() but check for n being 0 first.
Block does not match xquery (valid result, not relevant for the request)
#define GNUNET_NO
Definition: gnunet_common.h:78
const char * GNUNET_h2s(const struct GNUNET_HashCode *hc)
Convert a hash value to a string (for printing debug messages).
#define GNUNET_OK
Named constants for return values.
Definition: gnunet_common.h:75
size_t data_size
Number of bytes in data.
Default behavior.
struct GNUNET_HashCode key
Key of this request.
#define DHT_MAX_RECENT
Number of requests we track at most (for routing replies).
void GNUNET_STATISTICS_update(struct GNUNET_STATISTICS_Handle *handle, const char *name, int64_t delta, int make_persistent)
Set statistic value for the peer.
static int process(void *cls, const struct GNUNET_HashCode *key, void *value)
Forward the result to the given peer if it matches the request.
Internal representation of the hash map.
#define GNUNET_break(cond)
Use this for internal assertion violations that are not fatal (can be handled) but should not occur...
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:378
enum GNUNET_BLOCK_Type type
Type of the requested block.
int GNUNET_BLOCK_group_merge(struct GNUNET_BLOCK_Group *bg1, struct GNUNET_BLOCK_Group *bg2)
Try merging two block groups.
Definition: block.c:226
const struct GNUNET_PeerIdentity * get_path
Path of the reply.
struct GNUNET_BLOCK_Context * GDS_block_context
Our handle to the BLOCK library.
This is a &#39;FIND-PEER&#39; request, so approximate results are fine.
enum GNUNET_DHT_RouteOption options
Request options.
static struct GNUNET_CONTAINER_Heap * recent_heap
Recent requests by time inserted.
static char * value
Value of the record to add/remove.
Valid result, but suppressed because it is a duplicate.
void GNUNET_CONTAINER_multihashmap_destroy(struct GNUNET_CONTAINER_MultiHashMap *map)
Destroy a hash map.
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:338
unsigned int put_path_length
Number of entries in put_path.
void * GNUNET_CONTAINER_heap_peek(const struct GNUNET_CONTAINER_Heap *heap)
Get element stored at the root of heap.
static void expire_oldest_entry()
Remove the oldest entry from the DHT routing table.
Last possible valid result.
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.
Handle to a node in a heap.
GNUnet DHT tracking of requests for routing replies.
void GDS_ROUTING_init()
Initialize routing subsystem.
Heap with the minimum cost at the root.
void GNUNET_CONTAINER_heap_destroy(struct GNUNET_CONTAINER_Heap *heap)
Destroys the heap.
Type of a block that contains a HELLO for a peer (for DHT and CADET find-peer operations).
A 512-bit hashcode.
GNUNET_DHT_RouteOption
Options for routing.
struct GNUNET_TIME_Absolute GNUNET_TIME_absolute_get(void)
Get the current time.
Definition: time.c:118
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).
Node in the heap.
unsigned int GNUNET_CONTAINER_heap_get_size(const struct GNUNET_CONTAINER_Heap *heap)
Get the current size of the heap.
Valid result, and there may be more.
struct GNUNET_BLOCK_Group * bg
Block group for filtering replies.
#define GNUNET_SYSERR
Definition: gnunet_common.h:76
GNUNET_BLOCK_EvaluationResult
Possible ways for how a block may relate to a query.
GNUnet DHT routing code.
unsigned int get_path_length
Number of entries in get_path.
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.
struct GNUNET_CONTAINER_Heap * GNUNET_CONTAINER_heap_create(enum GNUNET_CONTAINER_HeapOrder order)
Create a new heap.
#define GNUNET_memcmp(a, b)
Compare memory in a and b, where both must be of the same pointer type.
Specified block type not supported by this plugin.
Allow multiple values with the same key.
Closure for the &#39;process&#39; function.
static struct GNUNET_FS_PublishContext * pc
Handle to FS-publishing operation.
The identity of the host (wraps the signing key of the peer).
struct GNUNET_PeerIdentity peer
The peer this request was received from.
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.
Query format does not match block type (invalid query).
#define GNUNET_log(kind,...)
Block group data.
struct GNUNET_CONTAINER_MultiHashMap * GNUNET_CONTAINER_multihashmap_create(unsigned int len, int do_not_copy_keys)
Create a multi hash map.
enum GNUNET_BLOCK_Type type
Type of the reply.
static struct GNUNET_CONTAINER_MultiHashMap * recent_map
Recently seen requests by key.
Time for absolute times used by GNUnet, in microseconds.
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 GNUNET_YES
Definition: gnunet_common.h:77
const struct GNUNET_PeerIdentity * put_path
Path of the original PUT.
void GDS_ROUTING_done()
Shutdown routing subsystem.
uint32_t data
The data value.
void * GNUNET_CONTAINER_heap_remove_node(struct GNUNET_CONTAINER_HeapNode *node)
Removes a node from the heap.
const void * xquery
extended query (see gnunet_block_lib.h).
Query is valid, no reply given.
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).
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)...
struct GNUNET_CONTAINER_HeapNode * heap_node
Position of this node in the min heap.
#define GNUNET_malloc(size)
Wrapper around malloc.
#define GNUNET_free(ptr)
Wrapper around free.
void GNUNET_BLOCK_group_destroy(struct GNUNET_BLOCK_Group *bg)
Destroy resources used by a block group.
Definition: block.c:205
#define gettext_noop(String)
Definition: gettext.h:69
size_t xquery_size
Number of bytes in xquery.