X-Git-Url: https://git.librecmc.org/?a=blobdiff_plain;f=src%2Fdht%2Fgnunet-service-dht_routing.c;h=be3105c8eef71c71d5b355a3d176363a861ee8e5;hb=016f9c0b2e61c6dab0057a3b4618db5624badf51;hp=535a632678a60b75c27aeacc5a15c23e1206c13e;hpb=1f6511d450641f20c69f616dbdbbbb1badbbbc5a;p=oweals%2Fgnunet.git diff --git a/src/dht/gnunet-service-dht_routing.c b/src/dht/gnunet-service-dht_routing.c index 535a63267..be3105c8e 100644 --- a/src/dht/gnunet-service-dht_routing.c +++ b/src/dht/gnunet-service-dht_routing.c @@ -23,8 +23,10 @@ * @brief GNUnet DHT tracking of requests for routing replies * @author Christian Grothoff */ - +#include "platform.h" +#include "gnunet-service-dht_neighbours.h" #include "gnunet-service-dht_routing.h" +#include "gnunet-service-dht.h" /** @@ -45,6 +47,11 @@ struct RecentRequest */ struct GNUNET_PeerIdentity peer; + /** + * Key of this request. + */ + struct GNUNET_HashCode key; + /** * Position of this node in the min heap. */ @@ -55,17 +62,11 @@ struct RecentRequest */ struct GNUNET_CONTAINER_BloomFilter *reply_bf; - /** - * Timestamp of this request, for ordering - * the min heap. - */ - struct GNUNET_TIME_Absolute timestamp; - /** * Type of the requested block. */ enum GNUNET_BLOCK_Type type; - + /** * extended query (see gnunet_block_lib.h). Allocated at the * end of this struct. @@ -83,9 +84,9 @@ struct RecentRequest uint32_t reply_bf_mutator; /** - * Key of this request. + * Request options. */ - GNUNET_HashCode key; + enum GNUNET_DHT_RouteOption options; }; @@ -101,6 +102,156 @@ static struct GNUNET_CONTAINER_Heap *recent_heap; static struct GNUNET_CONTAINER_MultiHashMap *recent_map; +/** + * Closure for the 'process' function. + */ +struct ProcessContext +{ + /** + * Path of the original PUT + */ + const struct GNUNET_PeerIdentity *put_path; + + /** + * Path of the reply. + */ + const struct GNUNET_PeerIdentity *get_path; + + /** + * Payload of the reply. + */ + const void *data; + + /** + * Expiration time of the result. + */ + struct GNUNET_TIME_Absolute expiration_time; + + /** + * Number of entries in 'put_path'. + */ + unsigned int put_path_length; + + /** + * Number of entries in 'get_path'. + */ + unsigned int get_path_length; + + /** + * Number of bytes in 'data'. + */ + size_t data_size; + + /** + * Type of the reply. + */ + enum GNUNET_BLOCK_Type type; + +}; + + +/** + * Forward the result to the given peer if it matches the request. + * + * @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 + */ +static int +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; + 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 */ + + 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, 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: + 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; +} + + /** * Handle a reply (route to origin). Only forwards the reply back to * other peers waiting for it. Does not do local caching or @@ -113,22 +264,109 @@ static struct GNUNET_CONTAINER_MultiHashMap *recent_map; * @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, - GNUNET_TIME_Absolute expiration_time, - const GNUNET_HashCode *key, - unsigned int put_path_length, - struct GNUNET_PeerIdentity *put_path, - unsigned int get_path_length, - struct GNUNET_PeerIdentity *get_path, - const void *data, - size_t data_size) + 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) +{ + 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); +} + + +/** + * 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; } @@ -137,6 +375,7 @@ GDS_ROUTING_process (enum GNUNET_BLOCK_Type type, * * @param sender peer that originated the request * @param type type of the block + * @param options options for processing * @param key key for the content * @param xquery extended query * @param xquery_size number of bytes in xquery @@ -144,32 +383,46 @@ GDS_ROUTING_process (enum GNUNET_BLOCK_Type type, * @param reply_bf_mutator mutator for reply_bf */ void -GDS_ROUTING_add (const GNUNET_PeerIdentity *sender, - enum GNUNET_BLOCK_Type type, - const GNUNET_HashCode *key, - const void *xquery, - size_t xquery_size, - const struct GNUNET_CONTAINER_BloomFilter *reply_bf, - uint32_t reply_bf_mutator) +GDS_ROUTING_add (const struct GNUNET_PeerIdentity *sender, + enum GNUNET_BLOCK_Type type, + enum GNUNET_DHT_RouteOption options, + const struct GNUNET_HashCode * key, const void *xquery, + size_t xquery_size, + const struct GNUNET_CONTAINER_BloomFilter *reply_bf, + uint32_t reply_bf_mutator) { - if (GNUNET_CONTAINER_heap_get_size (recent_heap) >= DHT_MAX_RECENT) + 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->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)) { - recent_req = GNUNET_CONTAINER_heap_peek (recent_heap); - GNUNET_assert (recent_req != NULL); - GNUNET_SCHEDULER_cancel (recent_req->remove_task); - GNUNET_CONTAINER_heap_remove_node (recent_req->heap_node); - GNUNET_CONTAINER_bloomfilter_free (recent_req->bloom); - GNUNET_free (recent_req); + GNUNET_STATISTICS_update (GDS_stats, + gettext_noop + ("# DHT requests combined"), + 1, GNUNET_NO); + return; } - - recent_req = GNUNET_malloc (sizeof (struct RecentRequest)); - recent_req->uid = msg_ctx->unique_id; - memcpy (&recent_req->key, &msg_ctx->key, sizeof (GNUNET_HashCode)); recent_req->heap_node = - GNUNET_CONTAINER_heap_insert (recent_heap, recent_req, - GNUNET_TIME_absolute_get ().abs_value); - recent_req->bloom = - GNUNET_CONTAINER_bloomfilter_init (NULL, DHT_BLOOM_SIZE, DHT_BLOOM_K); + 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); } @@ -181,10 +434,8 @@ GDS_ROUTING_add (const GNUNET_PeerIdentity *sender, void GDS_ROUTING_init () { - recent_heap = - GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN); - recent_map = - GNUNET_CONTAINER_multihashmap_create (MAX_BUCKETS / 8); + recent_heap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN); + recent_map = GNUNET_CONTAINER_multihashmap_create (DHT_MAX_RECENT * 4 / 3, GNUNET_NO); } @@ -195,15 +446,11 @@ void GDS_ROUTING_done () { while (GNUNET_CONTAINER_heap_get_size (recent_heap) > 0) - { - 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->bloom); - 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; }