/*
This file is part of GNUnet.
- (C) 2011 Christian Grothoff (and other contributing authors)
+ Copyright (C) 2011 GNUnet e.V.
GNUnet is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published
You should have received a copy of the GNU General Public License
along with GNUnet; see the file COPYING. If not, write to the
- Free Software Foundation, Inc., 59 Temple Place - Suite 330,
- Boston, MA 02111-1307, USA.
+ Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
+ Boston, MA 02110-1301, USA.
*/
/**
/**
* Key of this request.
*/
- GNUNET_HashCode key;
+ struct GNUNET_HashCode key;
/**
* Position of this node in the min heap.
/**
* Forward the result to the given peer if it matches the request.
*
- * @param cls the 'struct ProcessContext' with the result
+ * @param cls the `struct ProcessContext` with the result
* @param key the query
- * @param value the 'struct RecentRequest' with the request
- * @return GNUNET_OK (continue to iterate),
- * GNUNET_SYSERR if the result is malformed or type unsupported
+ * @param value the `struct RecentRequest` with the request
+ * @return #GNUNET_OK (continue to iterate),
+ * #GNUNET_SYSERR if the result is malformed or type unsupported
*/
static int
-process (void *cls, const GNUNET_HashCode * key, void *value)
+process (void *cls, const struct GNUNET_HashCode * key, void *value)
{
struct ProcessContext *pc = cls;
struct RecentRequest *rr = value;
enum GNUNET_BLOCK_EvaluationResult eval;
unsigned int gpl;
unsigned int ppl;
- GNUNET_HashCode hc;
- const GNUNET_HashCode *eval_key;
+ 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 missmatch */
eval_key = key;
}
eval =
- GNUNET_BLOCK_evaluate (GDS_block_context, pc->type, eval_key,
- &rr->reply_bf, rr->reply_bf_mutator, rr->xquery,
- rr->xquery_size, pc->data, pc->data_size);
+ GNUNET_BLOCK_evaluate (GDS_block_context,
+ pc->type,
+ GNUNET_BLOCK_EO_NONE,
+ eval_key,
+ &rr->reply_bf,
+ rr->reply_bf_mutator,
+ rr->xquery,
+ rr->xquery_size,
+ pc->data,
+ pc->data_size);
switch (eval)
{
case GNUNET_BLOCK_EVALUATION_OK_MORE:
("# 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;
* @param key key for the content
* @param put_path_length number of entries in put_path
* @param put_path peers the original PUT traversed (if tracked)
- * @param get_path_length number of entries in put_path
+ * @param get_path_length number of entries in get_path
* @param get_path peers this reply has traversed so far (if tracked)
* @param data payload of the reply
* @param data_size number of bytes in data
void
GDS_ROUTING_process (enum GNUNET_BLOCK_Type type,
struct GNUNET_TIME_Absolute expiration_time,
- const GNUNET_HashCode * key, unsigned int put_path_length,
+ 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,
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);
}
+/**
+ * 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.
+ */
+static void
+expire_oldest_entry ()
+{
+ 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_CONTAINER_bloomfilter_free (recent_req->reply_bf);
+ GNUNET_assert (GNUNET_YES ==
+ GNUNET_CONTAINER_multihashmap_remove (recent_map,
+ &recent_req->key,
+ recent_req));
+ GNUNET_free (recent_req);
+}
+
+
+/**
+ * Try to combine multiple recent requests for the same value
+ * (if they come from the same peer).
+ *
+ * @param cls the new 'struct RecentRequest' (to discard upon successful combination)
+ * @param key the query
+ * @param value the existing 'struct RecentRequest' (to update upon successful combination)
+ * @return GNUNET_OK (continue to iterate),
+ * GNUNET_SYSERR if the request was successfully combined
+ */
+static int
+try_combine_recent (void *cls, const struct GNUNET_HashCode * key, void *value)
+{
+ struct RecentRequest *in = cls;
+ struct RecentRequest *rr = value;
+
+ if ( (0 != memcmp (&in->peer,
+ &rr->peer,
+ sizeof (struct GNUNET_PeerIdentity))) ||
+ (in->type != rr->type) ||
+ (in->xquery_size != rr->xquery_size) ||
+ (0 != memcmp (in->xquery,
+ rr->xquery,
+ in->xquery_size)) )
+ return GNUNET_OK;
+ if (in->reply_bf_mutator != rr->reply_bf_mutator)
+ {
+ rr->reply_bf_mutator = in->reply_bf_mutator;
+ GNUNET_CONTAINER_bloomfilter_free (rr->reply_bf);
+ rr->reply_bf = in->reply_bf;
+ }
+ else
+ {
+ GNUNET_CONTAINER_bloomfilter_or2 (rr->reply_bf,
+ in->reply_bf);
+ GNUNET_CONTAINER_bloomfilter_free (in->reply_bf);
+ }
+ GNUNET_free (in);
+ return GNUNET_SYSERR;
+}
+
+
/**
* Add a new entry to our routing table.
*
* @param options options for processing
* @param key key for the content
* @param xquery extended query
- * @param xquery_size number of bytes in xquery
+ * @param xquery_size number of bytes in @a xquery
* @param reply_bf bloomfilter to filter duplicates
- * @param reply_bf_mutator mutator for reply_bf
-*/
+ * @param reply_bf_mutator mutator for @a reply_bf
+ */
void
GDS_ROUTING_add (const struct GNUNET_PeerIdentity *sender,
enum GNUNET_BLOCK_Type type,
enum GNUNET_DHT_RouteOption options,
- const GNUNET_HashCode * key, const void *xquery,
+ const struct GNUNET_HashCode * key, const void *xquery,
size_t xquery_size,
const struct GNUNET_CONTAINER_BloomFilter *reply_bf,
uint32_t reply_bf_mutator)
struct RecentRequest *recent_req;
while (GNUNET_CONTAINER_heap_get_size (recent_heap) >= DHT_MAX_RECENT)
- {
- 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_CONTAINER_bloomfilter_free (recent_req->reply_bf);
- GNUNET_free (recent_req);
- }
-
+ 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->heap_node =
- GNUNET_CONTAINER_heap_insert (recent_heap, recent_req,
- GNUNET_TIME_absolute_get ().abs_value);
recent_req->reply_bf = GNUNET_CONTAINER_bloomfilter_copy (reply_bf);
recent_req->type = type;
recent_req->options = options;
recent_req->xquery = &recent_req[1];
+ memcpy (&recent_req[1], xquery, xquery_size);
recent_req->xquery_size = xquery_size;
recent_req->reply_bf_mutator = reply_bf_mutator;
+ 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);
GDS_ROUTING_init ()
{
recent_heap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN);
- recent_map = GNUNET_CONTAINER_multihashmap_create (DHT_MAX_RECENT * 4 / 3);
+ recent_map = GNUNET_CONTAINER_multihashmap_create (DHT_MAX_RECENT * 4 / 3, GNUNET_NO);
}
void
GDS_ROUTING_done ()
{
- struct RecentRequest *recent_req;
-
while (GNUNET_CONTAINER_heap_get_size (recent_heap) > 0)
- {
- 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_CONTAINER_bloomfilter_free (recent_req->reply_bf);
- GNUNET_free (recent_req);
- }
+ 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;
}