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 GNUNET_DATACACHE_Block *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_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 * 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

cls	the struct ProcessContext with the result
query_hash	the hash from the original query
value	the struct RecentRequest with the request

Returns

GNUNET_OK (continue to iterate)

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

{
  struct ProcessContext *pc = cls;
  struct RecentRequest *rr = value;
  enum GNUNET_BLOCK_ReplyEvaluationResult eval;
  unsigned int get_path_length;
  struct GNUNET_DATACACHE_Block bdx = *pc->bd;
 
  if ( (rr->type != GNUNET_BLOCK_TYPE_ANY) &&
       (rr->type != pc->bd->type) )
    return GNUNET_OK;           /* type mismatch */
  if (0 != (rr->options & GNUNET_DHT_RO_RECORD_ROUTE))
  {
    get_path_length = pc->get_path_length;
  }
  else
  {
    get_path_length = 0;
    bdx.put_path_length = 0;
    bdx.put_path = NULL;
  }
  if ( (0 == (rr->options & GNUNET_DHT_RO_FIND_APPROXIMATE)) &&
       (0 != GNUNET_memcmp (query_hash,
                            &bdx.key)) )
  {
    GNUNET_STATISTICS_update (GDS_stats,
                              "# Inexact matches discarded in exact search",
                              1,
                              GNUNET_NO);
    return GNUNET_OK; /* exact search, but inexact match */
  }
  eval = GNUNET_BLOCK_check_reply (GDS_block_context,
                                   bdx.type,
                                   rr->bg,
                                   &bdx.key,
                                   rr->xquery,
                                   rr->xquery_size,
                                   bdx.data,
                                   bdx.data_size);
  GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
              "Result for %s of type %d was evaluated as %d\n",
              GNUNET_h2s (&bdx.key),
              bdx.type,
              eval);
  if (GNUNET_BLOCK_REPLY_TYPE_NOT_SUPPORTED == eval)
  {
    /* If we do not know the block type, we still filter
       exact duplicates by the block content */
    struct GNUNET_HashCode chash;
    
    GNUNET_CRYPTO_hash (bdx.data,
                        bdx.data_size,
                        &chash);
    if (GNUNET_YES ==
        GNUNET_BLOCK_GROUP_bf_test_and_set (rr->bg,
                                            &chash))
      eval = GNUNET_BLOCK_REPLY_OK_DUPLICATE;
    else
      eval = GNUNET_BLOCK_REPLY_OK_MORE;
  }
  switch (eval)
  {
  case GNUNET_BLOCK_REPLY_OK_MORE:
  case GNUNET_BLOCK_REPLY_OK_LAST:
  case GNUNET_BLOCK_REPLY_TYPE_NOT_SUPPORTED:
    {
      struct PeerInfo *pi;
 
      GNUNET_STATISTICS_update (GDS_stats,
                                "# Good REPLIES matched against routing table",
                                1,
                                GNUNET_NO);
      pi = GDS_NEIGHBOURS_lookup_peer (&rr->peer);
      if (NULL == pi)
      {
        /* peer disconnected in the meantime, drop reply */
        GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
                    "No matching peer for reply for key %s\n",
                    GNUNET_h2s (query_hash));
        return GNUNET_OK;
      }
      GNUNET_break (GDS_NEIGHBOURS_handle_reply (pi,
                                                 &bdx,
                                                 query_hash,
                                                 get_path_length,
                                                 pc->get_path));
    }
    break;
  case GNUNET_BLOCK_REPLY_OK_DUPLICATE:
    GNUNET_STATISTICS_update (GDS_stats,
                              "# Duplicate REPLIES matched against routing table",
                              1,
                              GNUNET_NO);
    return GNUNET_OK;
  case GNUNET_BLOCK_REPLY_IRRELEVANT:
    GNUNET_STATISTICS_update (GDS_stats,
                              "# Irrelevant REPLIES matched against routing table",
                              1,
                              GNUNET_NO);
    return GNUNET_OK;
  default:
    GNUNET_break (0);
    return GNUNET_OK;
  }
  return GNUNET_OK;
}

References RecentRequest::bg, GNUNET_DATACACHE_Block::data, GNUNET_DATACACHE_Block::data_size, GDS_block_context, GDS_NEIGHBOURS_handle_reply(), GDS_NEIGHBOURS_lookup_peer(), GDS_stats, GNUNET_BLOCK_check_reply(), GNUNET_BLOCK_GROUP_bf_test_and_set(), GNUNET_BLOCK_REPLY_IRRELEVANT, GNUNET_BLOCK_REPLY_OK_DUPLICATE, GNUNET_BLOCK_REPLY_OK_LAST, GNUNET_BLOCK_REPLY_OK_MORE, GNUNET_BLOCK_REPLY_TYPE_NOT_SUPPORTED, GNUNET_BLOCK_TYPE_ANY, GNUNET_break, GNUNET_CRYPTO_hash(), GNUNET_DHT_RO_FIND_APPROXIMATE, GNUNET_DHT_RO_RECORD_ROUTE, GNUNET_ERROR_TYPE_DEBUG, GNUNET_h2s(), GNUNET_log, GNUNET_memcmp, GNUNET_NO, GNUNET_OK, GNUNET_STATISTICS_update(), GNUNET_YES, GNUNET_DATACACHE_Block::key, RecentRequest::options, pc, RecentRequest::peer, GNUNET_DATACACHE_Block::put_path, GNUNET_DATACACHE_Block::put_path_length, GNUNET_DATACACHE_Block::type, RecentRequest::type, value, RecentRequest::xquery, and RecentRequest::xquery_size.

Referenced by GDS_ROUTING_process().

Here is the call graph for this function:

Here is the caller graph for this function:

GDS_ROUTING_process()

void GDS_ROUTING_process	(	const struct GNUNET_DATACACHE_Block *	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

bd	block details
query_hash	query used in the inquiry
get_path_length	number of entries in get_path
get_path	peers this reply has traversed so far (if tracked)

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

{
  struct ProcessContext pc = {
    .bd = bd,
    .get_path = get_path,
    .get_path_length = get_path_length
  };
 
  GNUNET_CONTAINER_multihashmap_get_multiple (recent_map,
                                              query_hash,
                                              &process,
                                              &pc);
}

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

Referenced by process_reply_with_path().

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.

{
  struct RecentRequest *recent_req;
 
  GNUNET_STATISTICS_update (GDS_stats,
                            "# Old 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);
}

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(), and GDS_ROUTING_done().

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

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

{
  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;
}

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

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
[in]	bg	block group for filtering duplicate replies
	options	options for processing
	key	key for the content
	xquery	extended query
	xquery_size	number of bytes in xquery

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

{
  struct RecentRequest *recent_req;
 
  while (GNUNET_CONTAINER_heap_get_size (recent_heap) >= DHT_MAX_RECENT)
    expire_oldest_entry ();
  GNUNET_STATISTICS_update (GDS_stats,
                            "# 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,
                              "# 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);
  (void) GNUNET_CONTAINER_multihashmap_put (
    recent_map,
    key,
    recent_req,
    GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE);
}

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(), type, RecentRequest::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 402 of file gnunet-service-dht_routing.c.

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

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

{
  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;
}

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

Referenced by shutdown_task().

Here is the call graph for this function:

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(), GDS_ROUTING_done(), 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_done(), GDS_ROUTING_init(), and GDS_ROUTING_process().