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 
43 {
44 
49 
54 
59 
64 
69 
74  const void *xquery;
75 
79  size_t xquery_size;
80 
85 
86 };
87 
88 
93 
98 
99 
104 {
109 
114 
118  const void *data;
119 
123  struct GNUNET_TIME_Absolute expiration_time;
124 
128  unsigned int put_path_length;
129 
133  unsigned int get_path_length;
134 
138  size_t data_size;
139 
144 
145 };
146 
147 
157 static int
158 process (void *cls,
159  const struct GNUNET_HashCode *key,
160  void *value)
161 {
162  struct ProcessContext *pc = cls;
163  struct RecentRequest *rr = value;
165  unsigned int gpl;
166  unsigned int ppl;
167  struct GNUNET_HashCode hc;
168  const struct GNUNET_HashCode *eval_key;
169 
170  if ( (rr->type != GNUNET_BLOCK_TYPE_ANY) &&
171  (rr->type != pc->type) )
172  return GNUNET_OK; /* type missmatch */
173 
174  if (0 != (rr->options & GNUNET_DHT_RO_RECORD_ROUTE))
175  {
176  gpl = pc->get_path_length;
177  ppl = pc->put_path_length;
178  }
179  else
180  {
181  gpl = 0;
182  ppl = 0;
183  }
184  if ( (0 != (rr->options & GNUNET_DHT_RO_FIND_PEER)) &&
186  {
187  /* key may not match HELLO, which is OK since
188  * the search is approximate. Still, the evaluation
189  * would fail since the match is not exact. So
190  * we fake it by changing the key to the actual PID ... */
193  pc->data,
194  pc->data_size,
195  &hc);
196  eval_key = &hc;
197  }
198  else
199  {
200  eval_key = key;
201  }
202  eval
204  pc->type,
205  rr->bg,
207  eval_key,
208  rr->xquery,
209  rr->xquery_size,
210  pc->data,
211  pc->data_size);
213  "Result for %s of type %d was evaluated as %d\n",
214  GNUNET_h2s (key),
215  pc->type,
216  eval);
217  switch (eval)
218  {
223  ("# Good REPLIES matched against routing table"),
224  1, GNUNET_NO);
226  pc->type,
227  pc->expiration_time,
228  key,
229  ppl, pc->put_path,
230  gpl, pc->get_path,
231  pc->data,
232  pc->data_size);
233  break;
237  ("# Duplicate REPLIES matched against routing table"),
238  1, GNUNET_NO);
239  return GNUNET_OK;
243  ("# Invalid REPLIES matched against routing table"),
244  1, GNUNET_NO);
245  return GNUNET_SYSERR;
249  ("# Irrelevant REPLIES matched against routing table"),
250  1, GNUNET_NO);
251  return GNUNET_OK;
253  GNUNET_break (0);
254  return GNUNET_OK;
256  GNUNET_break (0);
257  return GNUNET_OK;
261  ("# Unsupported REPLIES matched against routing table"),
262  1, GNUNET_NO);
263  return GNUNET_SYSERR;
264  default:
265  GNUNET_break (0);
266  return GNUNET_SYSERR;
267  }
268  return GNUNET_OK;
269 }
270 
271 
289 void
291  struct GNUNET_TIME_Absolute expiration_time,
292  const struct GNUNET_HashCode *key,
293  unsigned int put_path_length,
294  const struct GNUNET_PeerIdentity *put_path,
295  unsigned int get_path_length,
296  const struct GNUNET_PeerIdentity *get_path,
297  const void *data,
298  size_t data_size)
299 {
300  struct ProcessContext pc;
301 
302  pc.type = type;
305  pc.put_path = put_path;
307  pc.get_path = get_path;
308  pc.data = data;
309  pc.data_size = data_size;
310  if (NULL == data)
311  {
312  /* Some apps might have an 'empty' reply as a valid reply; however,
313  'process' will call GNUNET_BLOCK_evaluate' which treats a 'NULL'
314  reply as request-validation (but we need response-validation).
315  So we set 'data' to a 0-byte non-NULL value just to be sure */
316  GNUNET_break (0 == data_size);
317  pc.data_size = 0;
318  pc.data = ""; /* something not null */
319  }
321  key,
322  &process,
323  &pc);
324 }
325 
326 
332 static void
334 {
335  struct RecentRequest *recent_req;
336 
339  ("# Entries removed from routing table"), 1,
340  GNUNET_NO);
341  recent_req = GNUNET_CONTAINER_heap_peek (recent_heap);
342  GNUNET_assert (recent_req != NULL);
344  GNUNET_BLOCK_group_destroy (recent_req->bg);
347  &recent_req->key,
348  recent_req));
349  GNUNET_free (recent_req);
350 }
351 
352 
363 static int
365  const struct GNUNET_HashCode *key,
366  void *value)
367 {
368  struct RecentRequest *in = cls;
369  struct RecentRequest *rr = value;
370 
371  if ( (0 != GNUNET_memcmp (&in->peer,
372  &rr->peer)) ||
373  (in->type != rr->type) ||
374  (in->xquery_size != rr->xquery_size) ||
375  (0 != memcmp (in->xquery,
376  rr->xquery,
377  in->xquery_size)) )
378  return GNUNET_OK;
381  rr->bg));
382  rr->bg = in->bg;
383  GNUNET_free (in);
384  return GNUNET_SYSERR;
385 }
386 
387 
400 void
401 GDS_ROUTING_add (const struct GNUNET_PeerIdentity *sender,
402  enum GNUNET_BLOCK_Type type,
403  struct GNUNET_BLOCK_Group *bg,
405  const struct GNUNET_HashCode *key,
406  const void *xquery,
407  size_t xquery_size)
408 {
409  struct RecentRequest *recent_req;
410 
411  while (GNUNET_CONTAINER_heap_get_size (recent_heap) >= DHT_MAX_RECENT)
414  gettext_noop ("# Entries added to routing table"),
415  1,
416  GNUNET_NO);
417  recent_req = GNUNET_malloc (sizeof (struct RecentRequest) + xquery_size);
418  recent_req->peer = *sender;
419  recent_req->key = *key;
420  recent_req->bg = bg;
421  recent_req->type = type;
422  recent_req->options = options;
423  recent_req->xquery = &recent_req[1];
424  GNUNET_memcpy (&recent_req[1],
425  xquery,
426  xquery_size);
427  recent_req->xquery_size = xquery_size;
428  if (GNUNET_SYSERR ==
430  key,
432  recent_req))
433  {
436  ("# DHT requests combined"),
437  1, GNUNET_NO);
438  return;
439  }
440  recent_req->heap_node
441  = GNUNET_CONTAINER_heap_insert (recent_heap,
442  recent_req,
443  GNUNET_TIME_absolute_get ().abs_value_us);
445  key,
446  recent_req,
448 }
449 
450 
454 void
456 {
459 }
460 
461 
465 void
467 {
468  while (GNUNET_CONTAINER_heap_get_size (recent_heap) > 0)
470  GNUNET_assert (0 == GNUNET_CONTAINER_heap_get_size (recent_heap));
471  GNUNET_CONTAINER_heap_destroy (recent_heap);
472  recent_heap = NULL;
475  recent_map = NULL;
476 }
477 
478 /* 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.
Block does not match xquery (valid result, not relevant for the request)
#define GNUNET_NO
Definition: gnunet_common.h:81
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:78
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:379
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:227
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.
#define GNUNET_memcpy(dst, src, n)
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:339
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:79
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_HashMapIterator 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:80
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:206
#define gettext_noop(String)
Definition: gettext.h:69
size_t xquery_size
Number of bytes in xquery.