GNUnet  0.10.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 
42 struct RecentRequest {
47 
52 
57 
62 
67 
72  const void *xquery;
73 
77  size_t xquery_size;
78 
83 };
84 
85 
90 
95 
96 
105 
110 
114  const void *data;
115 
119  struct GNUNET_TIME_Absolute expiration_time;
120 
124  unsigned int put_path_length;
125 
129  unsigned int get_path_length;
130 
134  size_t data_size;
135 
140 };
141 
142 
152 static int
153 process(void *cls,
154  const struct GNUNET_HashCode *key,
155  void *value)
156 {
157  struct ProcessContext *pc = cls;
158  struct RecentRequest *rr = value;
160  unsigned int gpl;
161  unsigned int ppl;
162  struct GNUNET_HashCode hc;
163  const struct GNUNET_HashCode *eval_key;
164 
165  if ((rr->type != GNUNET_BLOCK_TYPE_ANY) &&
166  (rr->type != pc->type))
167  return GNUNET_OK; /* type missmatch */
168 
169  if (0 != (rr->options & GNUNET_DHT_RO_RECORD_ROUTE))
170  {
171  gpl = pc->get_path_length;
172  ppl = pc->put_path_length;
173  }
174  else
175  {
176  gpl = 0;
177  ppl = 0;
178  }
179  if ((0 != (rr->options & GNUNET_DHT_RO_FIND_PEER)) &&
181  {
182  /* key may not match HELLO, which is OK since
183  * the search is approximate. Still, the evaluation
184  * would fail since the match is not exact. So
185  * we fake it by changing the key to the actual PID ... */
188  pc->data,
189  pc->data_size,
190  &hc);
191  eval_key = &hc;
192  }
193  else
194  {
195  eval_key = key;
196  }
197  eval
199  pc->type,
200  rr->bg,
202  eval_key,
203  rr->xquery,
204  rr->xquery_size,
205  pc->data,
206  pc->data_size);
208  "Result for %s of type %d was evaluated as %d\n",
209  GNUNET_h2s(key),
210  pc->type,
211  eval);
212  switch (eval)
213  {
218  ("# Good REPLIES matched against routing table"),
219  1, GNUNET_NO);
221  pc->type,
222  pc->expiration_time,
223  key,
224  ppl, pc->put_path,
225  gpl, pc->get_path,
226  pc->data,
227  pc->data_size);
228  break;
229 
233  ("# Duplicate REPLIES matched against routing table"),
234  1, GNUNET_NO);
235  return GNUNET_OK;
236 
240  ("# Invalid REPLIES matched against routing table"),
241  1, GNUNET_NO);
242  return GNUNET_SYSERR;
243 
247  ("# Irrelevant REPLIES matched against routing table"),
248  1, GNUNET_NO);
249  return GNUNET_OK;
250 
252  GNUNET_break(0);
253  return GNUNET_OK;
254 
256  GNUNET_break(0);
257  return GNUNET_OK;
258 
262  ("# Unsupported REPLIES matched against routing table"),
263  1, GNUNET_NO);
264  return GNUNET_SYSERR;
265 
266  default:
267  GNUNET_break(0);
268  return GNUNET_SYSERR;
269  }
270  return GNUNET_OK;
271 }
272 
273 
291 void
293  struct GNUNET_TIME_Absolute expiration_time,
294  const struct GNUNET_HashCode *key,
295  unsigned int put_path_length,
296  const struct GNUNET_PeerIdentity *put_path,
297  unsigned int get_path_length,
298  const struct GNUNET_PeerIdentity *get_path,
299  const void *data,
300  size_t data_size)
301 {
302  struct ProcessContext pc;
303 
304  pc.type = type;
307  pc.put_path = put_path;
309  pc.get_path = get_path;
310  pc.data = data;
311  pc.data_size = data_size;
312  if (NULL == data)
313  {
314  /* Some apps might have an 'empty' reply as a valid reply; however,
315  'process' will call GNUNET_BLOCK_evaluate' which treats a 'NULL'
316  reply as request-validation (but we need response-validation).
317  So we set 'data' to a 0-byte non-NULL value just to be sure */
318  GNUNET_break(0 == data_size);
319  pc.data_size = 0;
320  pc.data = ""; /* something not null */
321  }
323  key,
324  &process,
325  &pc);
326 }
327 
328 
334 static void
336 {
337  struct RecentRequest *recent_req;
338 
341  ("# Entries removed from routing table"), 1,
342  GNUNET_NO);
343  recent_req = GNUNET_CONTAINER_heap_peek(recent_heap);
344  GNUNET_assert(recent_req != NULL);
346  GNUNET_BLOCK_group_destroy(recent_req->bg);
349  &recent_req->key,
350  recent_req));
351  GNUNET_free(recent_req);
352 }
353 
354 
365 static int
367  const struct GNUNET_HashCode *key,
368  void *value)
369 {
370  struct RecentRequest *in = cls;
371  struct RecentRequest *rr = value;
372 
373  if ((0 != GNUNET_memcmp(&in->peer,
374  &rr->peer)) ||
375  (in->type != rr->type) ||
376  (in->xquery_size != rr->xquery_size) ||
377  (0 != memcmp(in->xquery,
378  rr->xquery,
379  in->xquery_size)))
380  return GNUNET_OK;
383  rr->bg));
384  rr->bg = in->bg;
385  GNUNET_free(in);
386  return GNUNET_SYSERR;
387 }
388 
389 
402 void
404  enum GNUNET_BLOCK_Type type,
405  struct GNUNET_BLOCK_Group *bg,
407  const struct GNUNET_HashCode *key,
408  const void *xquery,
409  size_t xquery_size)
410 {
411  struct RecentRequest *recent_req;
412 
413  while (GNUNET_CONTAINER_heap_get_size(recent_heap) >= DHT_MAX_RECENT)
416  gettext_noop("# Entries added to routing table"),
417  1,
418  GNUNET_NO);
419  recent_req = GNUNET_malloc(sizeof(struct RecentRequest) + xquery_size);
420  recent_req->peer = *sender;
421  recent_req->key = *key;
422  recent_req->bg = bg;
423  recent_req->type = type;
424  recent_req->options = options;
425  recent_req->xquery = &recent_req[1];
426  GNUNET_memcpy(&recent_req[1],
427  xquery,
428  xquery_size);
429  recent_req->xquery_size = xquery_size;
430  if (GNUNET_SYSERR ==
432  key,
434  recent_req))
435  {
438  ("# DHT requests combined"),
439  1, GNUNET_NO);
440  return;
441  }
442  recent_req->heap_node
443  = GNUNET_CONTAINER_heap_insert(recent_heap,
444  recent_req,
445  GNUNET_TIME_absolute_get().abs_value_us);
447  key,
448  recent_req,
450 }
451 
452 
456 void
458 {
461 }
462 
463 
467 void
469 {
470  while (GNUNET_CONTAINER_heap_get_size(recent_heap) > 0)
473  GNUNET_CONTAINER_heap_destroy(recent_heap);
474  recent_heap = NULL;
477  recent_map = NULL;
478 }
479 
480 /* 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.
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:377
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:225
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:337
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.
static size_t data_size
Number of bytes in data.
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:204
#define gettext_noop(String)
Definition: gettext.h:69
size_t xquery_size
Number of bytes in xquery.