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 dependency graph for gnunet-service-dht_routing.c:

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 * 16)
	Number of requests we track at most (for routing replies). More...

Functions
static int	process (void cls, const struct GNUNET_HashCode key, void *value)
	Forward the result to the given peer if it matches the request. More...

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). More...

static void	expire_oldest_entry ()
	Remove the oldest entry from the DHT routing table. More...

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). 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_Heap *	recent_heap
	Recent requests by time inserted. More...

static struct GNUNET_CONTAINER_MultiHashMap *	recent_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 * 16)

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

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

Referenced by GDS_ROUTING_add(), and GDS_ROUTING_init().

Function Documentation

◆ process()

static int process	(	void *	cls,
		const struct GNUNET_HashCode *	key,
		void *	value
	)

static

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

Parameters

cls	the `struct ProcessContext` with the result
key	the query
value	the `struct RecentRequest` with the request

Returns: GNUNET_OK (continue to iterate), GNUNET_SYSERR if the result is malformed or type unsupported

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

Referenced by GDS_ROUTING_process().

 {
   struct ProcessContext *pc = cls;
   struct RecentRequest *rr = value;
   enum GNUNET_BLOCK_EvaluationResult eval;
   unsigned int gpl;
   unsigned int ppl;
   struct GNUNET_HashCode hc;
   const struct GNUNET_HashCode *eval_key;
 
   if ((rr->type != GNUNET_BLOCK_TYPE_ANY) &&
       (rr->type != pc->type))
     return GNUNET_OK;           /* type mismatch */
 
   if (0 != (rr->options & GNUNET_DHT_RO_RECORD_ROUTE))
   {
     gpl = pc->get_path_length;
     ppl = pc->put_path_length;
   }
   else
   {
     gpl = 0;
     ppl = 0;
   }
   if ((0 != (rr->options & GNUNET_DHT_RO_FIND_PEER)) &&
       (pc->type == GNUNET_BLOCK_TYPE_DHT_HELLO))
   {
     /* key may not match HELLO, which is OK since
      * the search is approximate.  Still, the evaluation
      * would fail since the match is not exact.  So
      * we fake it by changing the key to the actual PID ... */
     GNUNET_BLOCK_get_key (GDS_block_context,
                           GNUNET_BLOCK_TYPE_DHT_HELLO,
                           pc->data,
                           pc->data_size,
                           &hc);
     eval_key = &hc;
   }
   else
   {
     eval_key = key;
   }
   eval
     = GNUNET_BLOCK_evaluate (GDS_block_context,
                              pc->type,
                              rr->bg,
                              GNUNET_BLOCK_EO_NONE,
                              eval_key,
                              rr->xquery,
                              rr->xquery_size,
                              pc->data,
                              pc->data_size);
   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
               "Result for %s of type %d was evaluated as %d\n",
               GNUNET_h2s (key),
               pc->type,
               eval);
   switch (eval)
   {
   case GNUNET_BLOCK_EVALUATION_OK_MORE:
   case GNUNET_BLOCK_EVALUATION_OK_LAST:
     GNUNET_STATISTICS_update (GDS_stats,
                               gettext_noop
                                 ("# Good REPLIES matched against routing table"),
                               1, GNUNET_NO);
     GDS_NEIGHBOURS_handle_reply (&rr->peer,
                                  pc->type,
                                  pc->expiration_time,
                                  key,
                                  ppl, pc->put_path,
                                  gpl, pc->get_path,
                                  pc->data,
                                  pc->data_size);
     break;
 
   case GNUNET_BLOCK_EVALUATION_OK_DUPLICATE:
     GNUNET_STATISTICS_update (GDS_stats,
                               gettext_noop
                               (
                                 "# Duplicate REPLIES matched against routing table"),
                               1, GNUNET_NO);
     return GNUNET_OK;
 
   case GNUNET_BLOCK_EVALUATION_RESULT_INVALID:
     GNUNET_STATISTICS_update (GDS_stats,
                               gettext_noop
                               (
                                 "# Invalid REPLIES matched against routing table"),
                               1, GNUNET_NO);
     return GNUNET_SYSERR;
 
   case GNUNET_BLOCK_EVALUATION_RESULT_IRRELEVANT:
     GNUNET_STATISTICS_update (GDS_stats,
                               gettext_noop
                               (
                                 "# Irrelevant REPLIES matched against routing table"),
                               1, GNUNET_NO);
     return GNUNET_OK;
 
   case GNUNET_BLOCK_EVALUATION_REQUEST_VALID:
     GNUNET_break (0);
     return GNUNET_OK;
 
   case GNUNET_BLOCK_EVALUATION_REQUEST_INVALID:
     GNUNET_break (0);
     return GNUNET_OK;
 
   case GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED:
     GNUNET_STATISTICS_update (GDS_stats,
                               gettext_noop
                               (
                                 "# Unsupported REPLIES matched against routing table"),
                               1, GNUNET_NO);
     return GNUNET_SYSERR;
 
   default:
     GNUNET_break (0);
     return GNUNET_SYSERR;
   }
   return GNUNET_OK;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

◆ GDS_ROUTING_process()

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).

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

type	type of the block
expiration_time	when does the content expire
key	key for the content
put_path_length	number of entries in put_path
put_path	peers the original PUT traversed (if tracked)
get_path_length	number of entries in get_path
get_path	peers this reply has traversed so far (if tracked)
data	payload of the reply
data_size	number of bytes in data

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

References data, ProcessContext::data, ProcessContext::data_size, data_size, ProcessContext::expiration_time, ProcessContext::get_path, ProcessContext::get_path_length, GNUNET_break, GNUNET_CONTAINER_multihashmap_get_multiple(), process(), ProcessContext::put_path, ProcessContext::put_path_length, RecentRequest::type, and ProcessContext::type.

Referenced by process_reply_with_path().

 {
   struct ProcessContext pc;
 
   pc.type = type;
   pc.expiration_time = expiration_time;
   pc.put_path_length = put_path_length;
   pc.put_path = put_path;
   pc.get_path_length = get_path_length;
   pc.get_path = get_path;
   pc.data = data;
   pc.data_size = data_size;
   if (NULL == data)
   {
     /* Some apps might have an 'empty' reply as a valid reply; however,
        'process' will call GNUNET_BLOCK_evaluate' which treats a 'NULL'
        reply as request-validation (but we need response-validation).
        So we set 'data' to a 0-byte non-NULL value just to be sure */
     GNUNET_break (0 == data_size);
     pc.data_size = 0;
     pc.data = "";   /* something not null */
   }
   GNUNET_CONTAINER_multihashmap_get_multiple (recent_map,
                                               key,
                                               &process,
                                               &pc);
 }

Here is the call graph for this function:

Here is the caller graph for this function:

◆ expire_oldest_entry()

static void expire_oldest_entry ( )

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 341 of file gnunet-service-dht_routing.c.

References RecentRequest::bg, GDS_stats, gettext_noop, 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, and RecentRequest::key.

Referenced by GDS_ROUTING_add(), and GDS_ROUTING_done().

 {
   struct RecentRequest *recent_req;
 
   GNUNET_STATISTICS_update (GDS_stats,
                             gettext_noop
                               ("# Entries removed from routing table"), 1,
                             GNUNET_NO);
   recent_req = GNUNET_CONTAINER_heap_peek (recent_heap);
   GNUNET_assert (recent_req != NULL);
   GNUNET_CONTAINER_heap_remove_node (recent_req->heap_node);
   GNUNET_BLOCK_group_destroy (recent_req->bg);
   GNUNET_assert (GNUNET_YES ==
                  GNUNET_CONTAINER_multihashmap_remove (recent_map,
                                                        &recent_req->key,
                                                        recent_req));
   GNUNET_free (recent_req);
 }

Here is the call graph for this function:

Here is the caller graph for this function:

◆ try_combine_recent()

static int 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

cls	the new 'struct RecentRequest' (to discard upon successful combination)
key	the query
value	the 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 372 of file gnunet-service-dht_routing.c.

References RecentRequest::bg, GNUNET_BLOCK_group_merge(), GNUNET_break, GNUNET_free, GNUNET_memcmp, GNUNET_OK, GNUNET_SYSERR, RecentRequest::peer, RecentRequest::type, value, RecentRequest::xquery, and RecentRequest::xquery_size.

Referenced by GDS_ROUTING_add().

 {
   struct RecentRequest *in = cls;
   struct RecentRequest *rr = value;
 
   if ((0 != GNUNET_memcmp (&in->peer,
                            &rr->peer)) ||
       (in->type != rr->type) ||
       (in->xquery_size != rr->xquery_size) ||
       (0 != memcmp (in->xquery,
                     rr->xquery,
                     in->xquery_size)))
     return GNUNET_OK;
   GNUNET_break (GNUNET_SYSERR !=
                 GNUNET_BLOCK_group_merge (in->bg,
                                           rr->bg));
   rr->bg = in->bg;
   GNUNET_free (in);
   return GNUNET_SYSERR;
 }

Here is the call graph for this function:

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

sender	peer that originated the request
type	type of the block
options	options for processing
key	key for the content
xquery	extended query
xquery_size	number of bytes in xquery
reply_bf	bloomfilter to filter duplicates
reply_bf_mutator	mutator for reply_bf

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

References RecentRequest::bg, DHT_MAX_RECENT, expire_oldest_entry(), GDS_stats, gettext_noop, 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, RecentRequest::key, RecentRequest::options, RecentRequest::peer, try_combine_recent(), RecentRequest::type, RecentRequest::xquery, and RecentRequest::xquery_size.

Referenced by handle_dht_p2p_get().

 {
   struct RecentRequest *recent_req;
 
   while (GNUNET_CONTAINER_heap_get_size (recent_heap) >= DHT_MAX_RECENT)
     expire_oldest_entry ();
   GNUNET_STATISTICS_update (GDS_stats,
                             gettext_noop ("# Entries added to routing table"),
                             1,
                             GNUNET_NO);
   recent_req = GNUNET_malloc (sizeof(struct RecentRequest) + xquery_size);
   recent_req->peer = *sender;
   recent_req->key = *key;
   recent_req->bg = bg;
   recent_req->type = type;
   recent_req->options = options;
   recent_req->xquery = &recent_req[1];
   GNUNET_memcpy (&recent_req[1],
                  xquery,
                  xquery_size);
   recent_req->xquery_size = xquery_size;
   if (GNUNET_SYSERR ==
       GNUNET_CONTAINER_multihashmap_get_multiple (recent_map,
                                                   key,
                                                   &try_combine_recent,
                                                   recent_req))
   {
     GNUNET_STATISTICS_update (GDS_stats,
                               gettext_noop
                                 ("# DHT requests combined"),
                               1, GNUNET_NO);
     return;
   }
   recent_req->heap_node
     = GNUNET_CONTAINER_heap_insert (recent_heap,
                                     recent_req,
                                     GNUNET_TIME_absolute_get ().abs_value_us);
   GNUNET_CONTAINER_multihashmap_put (recent_map,
                                      key,
                                      recent_req,
                                      GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE);
 }

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 463 of file gnunet-service-dht_routing.c.

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

Referenced by run().

 {
   recent_heap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN);
   recent_map = GNUNET_CONTAINER_multihashmap_create (DHT_MAX_RECENT * 4 / 3,
                                                      GNUNET_NO);
 }

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 475 of file gnunet-service-dht_routing.c.

References expire_oldest_entry(), GNUNET_assert, GNUNET_CONTAINER_heap_destroy(), GNUNET_CONTAINER_heap_get_size(), GNUNET_CONTAINER_multihashmap_destroy(), and GNUNET_CONTAINER_multihashmap_size().

Referenced by shutdown_task().

 {
   while (GNUNET_CONTAINER_heap_get_size (recent_heap) > 0)
     expire_oldest_entry ();
   GNUNET_assert (0 == GNUNET_CONTAINER_heap_get_size (recent_heap));
   GNUNET_CONTAINER_heap_destroy (recent_heap);
   recent_heap = NULL;
   GNUNET_assert (0 == GNUNET_CONTAINER_multihashmap_size (recent_map));
   GNUNET_CONTAINER_multihashmap_destroy (recent_map);
   recent_map = NULL;
 }