GNUnet  0.16.x
Data Structures | Macros | Functions | Variables
gnunet-service-dht_routing.c File Reference

GNUnet DHT tracking of requests for routing replies. More...

#include "platform.h"
#include "gnunet-service-dht_neighbours.h"
#include "gnunet-service-dht_routing.h"
#include "gnunet-service-dht.h"
#include "gnunet_block_group_lib.h"
Include dependency graph for gnunet-service-dht_routing.c:

Go to the source code of this file.

Data Structures

struct  RecentRequest
 Information we keep about all recent GET requests so that we can route replies. More...
 
struct  ProcessContext
 Closure for the process() function. More...
 

Macros

#define DHT_MAX_RECENT   (1024 * 128)
 Number of requests we track at most (for routing replies). More...
 

Functions

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. More...
 
void GDS_ROUTING_process (const struct GDS_DATACACHE_BlockData *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). More...
 
static void expire_oldest_entry (void)
 Remove the oldest entry from the DHT routing table. More...
 
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). More...
 
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. More...
 
void GDS_ROUTING_init ()
 Initialize routing subsystem. More...
 
void GDS_ROUTING_done ()
 Shutdown routing subsystem. More...
 

Variables

static struct GNUNET_CONTAINER_Heaprecent_heap
 Recent requests by time inserted. More...
 
static struct GNUNET_CONTAINER_MultiHashMaprecent_map
 Recently seen requests by key. More...
 

Detailed Description

GNUnet DHT tracking of requests for routing replies.

Author
Christian Grothoff

Definition in file gnunet-service-dht_routing.c.

Macro Definition Documentation

◆ DHT_MAX_RECENT

#define DHT_MAX_RECENT   (1024 * 128)

Number of requests we track at most (for routing replies).

TODO: make configurable!

Definition at line 37 of file gnunet-service-dht_routing.c.

Function Documentation

◆ process()

static enum GNUNET_GenericReturnValue process ( void *  cls,
const struct GNUNET_HashCode query_hash,
void *  value 
)
static

Forward the result to the given peer if it matches the request.

Parameters
clsthe struct ProcessContext with the result
query_hashthe hash from the original query
valuethe struct RecentRequest with the request
Returns
GNUNET_OK (continue to iterate)

Definition at line 97 of file gnunet-service-dht_routing.c.

135 {
136  struct ProcessContext *pc = cls;
137  struct RecentRequest *rr = value;
139  unsigned int get_path_length;
140  struct GDS_DATACACHE_BlockData 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 }
static struct GNUNET_PEERINFO_Handle * pi
Handle to peerinfo service.
static char * value
Value of the record to add/remove.
static struct GNUNET_FS_PublishContext * pc
Handle to FS-publishing operation.
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 GDS_DATACACHE_BlockData *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.
#define GNUNET_log(kind,...)
#define GNUNET_memcmp(a, b)
Compare memory in a and b, where both must be of the same pointer type.
@ GNUNET_OK
Definition: gnunet_common.h:95
@ GNUNET_YES
Definition: gnunet_common.h:97
@ GNUNET_NO
Definition: gnunet_common.h:94
@ GNUNET_BLOCK_TYPE_ANY
Identifier for any block.
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:317
int 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:214
GNUNET_BLOCK_ReplyEvaluationResult
Possible ways for how a block may relate to a query.
@ 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_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
#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
void GNUNET_STATISTICS_update(struct GNUNET_STATISTICS_Handle *handle, const char *name, int64_t delta, int make_persistent)
Set statistic value for the peer.
Information about a block stored in the datacache.
const void * data
Actual block data.
size_t data_size
Number of bytes in data.
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.
unsigned int put_path_length
Length of the put_path array.
struct GNUNET_HashCode key
Key of the block.
A 512-bit hashcode.
Entry for a peer in a bucket.
Closure for the process() function.
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_BLOCK_Group * bg
Block group for filtering replies.
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).

Referenced by GDS_ROUTING_process().

Here is the caller graph for this function:

◆ GDS_ROUTING_process()

void GDS_ROUTING_process ( const struct GDS_DATACACHE_BlockData 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).

Only forwards the reply back to other peers waiting for it. Does not do local caching or forwarding to local clients. Essentially calls GDS_NEIGHBOURS_handle_reply() for all peers that sent us a matching request recently.

Parameters
bdblock details
query_hashquery used in the inquiry
get_path_lengthnumber of entries in get_path
get_pathpeers this reply has traversed so far (if tracked)

Definition at line 255 of file gnunet-service-dht_routing.c.

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 }
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.
static struct GNUNET_CONTAINER_MultiHashMap * recent_map
Recently seen requests by key.
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.
const struct GNUNET_DHT_PathElement * get_path
Path of the reply.
const struct GDS_DATACACHE_BlockData * bd
Block data.
unsigned int get_path_length
Number of entries in get_path.

References ProcessContext::bd, ProcessContext::get_path, ProcessContext::get_path_length, GNUNET_CONTAINER_multihashmap_get_multiple(), pc, process(), and recent_map.

Referenced by check_dht_p2p_result().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ expire_oldest_entry()

static void expire_oldest_entry ( void  )
static

Remove the oldest entry from the DHT routing table.

Must only be called if it is known that there is at least one entry in the heap and hashmap.

Definition at line 279 of file gnunet-service-dht_routing.c.

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 }
static struct GNUNET_CONTAINER_Heap * recent_heap
Recent requests by time inserted.
void GNUNET_BLOCK_group_destroy(struct GNUNET_BLOCK_Group *bg)
Destroy resources used by a block group.
Definition: block.c:173
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.
void * GNUNET_CONTAINER_heap_remove_node(struct GNUNET_CONTAINER_HeapNode *node)
Removes a node from the heap.
void * GNUNET_CONTAINER_heap_peek(const struct GNUNET_CONTAINER_Heap *heap)
Get element stored at the root of heap.
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
#define GNUNET_free(ptr)
Wrapper around free.
struct GNUNET_HashCode key
Key of this request.
struct GNUNET_CONTAINER_HeapNode * heap_node
Position of this node in the min heap.

References RecentRequest::bg, GDS_stats, GNUNET_assert, GNUNET_BLOCK_group_destroy(), GNUNET_CONTAINER_heap_peek(), GNUNET_CONTAINER_heap_remove_node(), GNUNET_CONTAINER_multihashmap_remove(), GNUNET_free, GNUNET_NO, GNUNET_STATISTICS_update(), GNUNET_YES, RecentRequest::heap_node, RecentRequest::key, recent_heap, and recent_map.

Referenced by GDS_ROUTING_add().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ try_combine_recent()

static enum GNUNET_GenericReturnValue try_combine_recent ( void *  cls,
const struct GNUNET_HashCode key,
void *  value 
)
static

Try to combine multiple recent requests for the same value (if they come from the same peer).

Parameters
clsthe new struct RecentRequest (to discard upon successful combination)
keythe query
valuethe existing struct RecentRequest (to update upon successful combination)
Returns
GNUNET_OK (continue to iterate), GNUNET_SYSERR if the request was successfully combined

Definition at line 279 of file gnunet-service-dht_routing.c.

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 }
@ GNUNET_SYSERR
Definition: gnunet_common.h:93
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:182

Referenced by GDS_ROUTING_add().

Here is the caller graph for this function:

◆ GDS_ROUTING_add()

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.

Parameters
senderpeer that originated the request
typetype of the block
[in]bgblock group for filtering duplicate replies
optionsoptions for processing
keykey for the content
xqueryextended query
xquery_sizenumber of bytes in xquery
reply_bfbloomfilter to filter duplicates
reply_bf_mutatormutator for reply_bf

Definition at line 348 of file gnunet-service-dht_routing.c.

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 }
struct GNUNET_GETOPT_CommandLineOption options[]
Definition: 002.c:5
struct GNUNET_HashCode key
The key used in the DHT.
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).
#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.
#define GNUNET_memcpy(dst, src, n)
Call memcpy() but check for n being 0 first.
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.
@ GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE
Allow multiple values with the same key.
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.
unsigned int GNUNET_CONTAINER_heap_get_size(const struct GNUNET_CONTAINER_Heap *heap)
Get the current size of the heap.
#define GNUNET_malloc(size)
Wrapper around malloc.
struct GNUNET_TIME_Absolute GNUNET_TIME_absolute_get(void)
Get the current time.
Definition: time.c:110
enum GNUNET_TESTBED_UnderlayLinkModelType type
the type of this model

References RecentRequest::bg, DHT_MAX_RECENT, expire_oldest_entry(), GDS_stats, GNUNET_CONTAINER_heap_get_size(), GNUNET_CONTAINER_heap_insert(), GNUNET_CONTAINER_multihashmap_get_multiple(), GNUNET_CONTAINER_multihashmap_put(), GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE, GNUNET_malloc, GNUNET_memcpy, GNUNET_NO, GNUNET_STATISTICS_update(), GNUNET_SYSERR, GNUNET_TIME_absolute_get(), RecentRequest::heap_node, key, RecentRequest::key, options, RecentRequest::options, RecentRequest::peer, recent_heap, recent_map, try_combine_recent(), RecentRequest::type, type, RecentRequest::xquery, and RecentRequest::xquery_size.

Referenced by handle_dht_p2p_get().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ GDS_ROUTING_init()

void GDS_ROUTING_init ( void  )

Initialize routing subsystem.

Definition at line 404 of file gnunet-service-dht_routing.c.

405 {
408  GNUNET_NO);
409 }
struct GNUNET_CONTAINER_MultiHashMap * GNUNET_CONTAINER_multihashmap_create(unsigned int len, int do_not_copy_keys)
Create a multi hash map.
struct GNUNET_CONTAINER_Heap * GNUNET_CONTAINER_heap_create(enum GNUNET_CONTAINER_HeapOrder order)
Create a new heap.
@ GNUNET_CONTAINER_HEAP_ORDER_MIN
Heap with the minimum cost at the root.

References DHT_MAX_RECENT, GNUNET_CONTAINER_heap_create(), GNUNET_CONTAINER_HEAP_ORDER_MIN, GNUNET_CONTAINER_multihashmap_create(), GNUNET_NO, recent_heap, and recent_map.

Referenced by run().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ GDS_ROUTING_done()

void GDS_ROUTING_done ( void  )

Shutdown routing subsystem.

Definition at line 416 of file gnunet-service-dht_routing.c.

417 {
420  GNUNET_assert (0 ==
423  recent_heap = NULL;
424  GNUNET_assert (0 ==
427  recent_map = NULL;
428 }
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.
void GNUNET_CONTAINER_heap_destroy(struct GNUNET_CONTAINER_Heap *heap)
Destroys the heap.

Referenced by shutdown_task().

Here is the caller graph for this function:

Variable Documentation

◆ recent_heap

struct GNUNET_CONTAINER_Heap* recent_heap
static

Recent requests by time inserted.

Definition at line 92 of file gnunet-service-dht_routing.c.

Referenced by expire_oldest_entry(), GDS_ROUTING_add(), and GDS_ROUTING_init().

◆ recent_map

struct GNUNET_CONTAINER_MultiHashMap* recent_map
static

Recently seen requests by key.

Definition at line 97 of file gnunet-service-dht_routing.c.

Referenced by expire_oldest_entry(), GDS_ROUTING_add(), GDS_ROUTING_init(), and GDS_ROUTING_process().