From 926f5a24e5a30566a51effb0e1752c15b0fa1e88 Mon Sep 17 00:00:00 2001 From: Christian Grothoff Date: Tue, 27 Sep 2011 11:29:11 +0000 Subject: move bloomfilter recalculation to block library --- src/block/block.c | 45 ++++++++++++++++++++- src/fs/fs.h | 6 --- src/fs/gnunet-service-fs_pr.c | 84 +++++++++------------------------------- src/include/gnunet_constants.h | 7 ++++ src/include/gnunet_dht_service.h | 4 +- src/include/gnunet_protocols.h | 41 ++++++++++++++++++-- 6 files changed, 107 insertions(+), 80 deletions(-) (limited to 'src') diff --git a/src/block/block.c b/src/block/block.c index 7ab420f7a..8efb0d477 100644 --- a/src/block/block.c +++ b/src/block/block.c @@ -25,6 +25,7 @@ */ #include "platform.h" #include "gnunet_util_lib.h" +#include "gnunet_constants.h" #include "gnunet_signatures.h" #include "gnunet_block_lib.h" #include "gnunet_block_plugin.h" @@ -249,6 +250,35 @@ GNUNET_BLOCK_get_key (struct GNUNET_BLOCK_Context *ctx, } +/** + * How many bytes should a bloomfilter be if we have already seen + * entry_count responses? Note that GNUNET_CONSTANTS_BLOOMFILTER_K gives us the number + * of bits set per entry. Furthermore, we should not re-size the + * filter too often (to keep it cheap). + * + * Since other peers will also add entries but not resize the filter, + * we should generally pick a slightly larger size than what the + * strict math would suggest. + * + * @return must be a power of two and smaller or equal to 2^15. + */ +static size_t +compute_bloomfilter_size (unsigned int entry_count) +{ + size_t size; + unsigned int ideal = (entry_count * GNUNET_CONSTANTS_BLOOMFILTER_K) / 4; + uint16_t max = 1 << 15; + + if (entry_count > max) + return max; + size = 8; + while ((size < max) && (size < ideal)) + size *= 2; + if (size > max) + return max; + return size; +} + /** * Construct a bloom filter that would filter out the given @@ -265,8 +295,19 @@ GNUNET_BLOCK_construct_bloomfilter (int32_t bf_mutator, const GNUNET_HashCode *seen_results, unsigned int seen_results_count) { - GNUNET_break (0); - return NULL; + struct GNUNET_CONTAINER_BloomFilter *bf; + GNUNET_HashCode mhash; + unsigned int i; + size_t nsize; + + nsize = compute_bloomfilter_size (seen_results_count); + bf = GNUNET_CONTAINER_bloomfilter_init (NULL, nsize, GNUNET_CONSTANTS_BLOOMFILTER_K); + for (i = 0; i < seen_results_count; i++) + { + GNUNET_BLOCK_mingle_hash (&seen_results[i], bf_mutator, &mhash); + GNUNET_CONTAINER_bloomfilter_add (bf, &mhash); + } + return bf; } diff --git a/src/fs/fs.h b/src/fs/fs.h index ed74850b2..b5fdb1cc7 100644 --- a/src/fs/fs.h +++ b/src/fs/fs.h @@ -131,12 +131,6 @@ */ #define HASHING_BLOCKSIZE (1024 * 128) -/** - * Number of bits we set per entry in the bloomfilter. - * Do not change! - */ -#define BLOOMFILTER_K GNUNET_DHT_GET_BLOOMFILTER_K - /** * Number of availability trials we perform per search result. */ diff --git a/src/fs/gnunet-service-fs_pr.c b/src/fs/gnunet-service-fs_pr.c index f63c088c0..d47d28ce6 100644 --- a/src/fs/gnunet-service-fs_pr.c +++ b/src/fs/gnunet-service-fs_pr.c @@ -188,35 +188,6 @@ static struct GNUNET_CONTAINER_Heap *requests_by_expiration_heap; static unsigned long long max_pending_requests = (32 * 1024); -/** - * How many bytes should a bloomfilter be if we have already seen - * entry_count responses? Note that BLOOMFILTER_K gives us the number - * of bits set per entry. Furthermore, we should not re-size the - * filter too often (to keep it cheap). - * - * Since other peers will also add entries but not resize the filter, - * we should generally pick a slightly larger size than what the - * strict math would suggest. - * - * @return must be a power of two and smaller or equal to 2^15. - */ -static size_t -compute_bloomfilter_size (unsigned int entry_count) -{ - size_t size; - unsigned int ideal = (entry_count * BLOOMFILTER_K) / 4; - uint16_t max = 1 << 15; - - if (entry_count > max) - return max; - size = 8; - while ((size < max) && (size < ideal)) - size *= 2; - if (size > max) - return max; - return size; -} - /** * Recalculate our bloom filter for filtering replies. This function @@ -226,30 +197,17 @@ compute_bloomfilter_size (unsigned int entry_count) * initiator (in which case we may resize to larger than mimimum size). * * @param pr request for which the BF is to be recomputed - * @return GNUNET_YES if a refresh actually happened */ -static int +static void refresh_bloomfilter (struct GSF_PendingRequest *pr) { - unsigned int i; - size_t nsize; - GNUNET_HashCode mhash; - - nsize = compute_bloomfilter_size (pr->replies_seen_count); - if ((pr->bf != NULL) && - (nsize == GNUNET_CONTAINER_bloomfilter_get_size (pr->bf))) - return GNUNET_NO; /* size not changed */ if (pr->bf != NULL) GNUNET_CONTAINER_bloomfilter_free (pr->bf); pr->mingle = - GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, UINT32_MAX); - pr->bf = GNUNET_CONTAINER_bloomfilter_init (NULL, nsize, BLOOMFILTER_K); - for (i = 0; i < pr->replies_seen_count; i++) - { - GNUNET_BLOCK_mingle_hash (&pr->replies_seen[i], pr->mingle, &mhash); - GNUNET_CONTAINER_bloomfilter_add (pr->bf, &mhash); - } - return GNUNET_YES; + GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, UINT32_MAX); + pr->bf = GNUNET_BLOCK_construct_bloomfilter (pr->mingle, + pr->replies_seen, + pr->replies_seen_count); } @@ -346,13 +304,13 @@ GSF_pending_request_create_ (enum GSF_PendingRequestOptions options, if (NULL != bf_data) { pr->bf = - GNUNET_CONTAINER_bloomfilter_init (bf_data, bf_size, BLOOMFILTER_K); + GNUNET_CONTAINER_bloomfilter_init (bf_data, bf_size, GNUNET_CONSTANTS_BLOOMFILTER_K); pr->mingle = mingle; } else if ((replies_seen_count > 0) && (0 != (options & GSF_PRO_BLOOMFILTER_FULL_REFRESH))) { - GNUNET_assert (GNUNET_YES == refresh_bloomfilter (pr)); + refresh_bloomfilter (pr); } GNUNET_CONTAINER_multihashmap_put (pr_map, query, pr, GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE); @@ -449,15 +407,7 @@ GSF_pending_request_update_ (struct GSF_PendingRequest *pr, memcpy (&pr->replies_seen[pr->replies_seen_count], replies_seen, sizeof (GNUNET_HashCode) * replies_seen_count); pr->replies_seen_count += replies_seen_count; - if (GNUNET_NO == refresh_bloomfilter (pr)) - { - /* bf not recalculated, simply extend it with new bits */ - for (i = 0; i < replies_seen_count; i++) - { - GNUNET_BLOCK_mingle_hash (&replies_seen[i], pr->mingle, &mhash); - GNUNET_CONTAINER_bloomfilter_add (pr->bf, &mhash); - } - } + refresh_bloomfilter (pr); } else { @@ -468,15 +418,17 @@ GSF_pending_request_update_ (struct GSF_PendingRequest *pr, pr->mingle = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, UINT32_MAX); pr->bf = - GNUNET_CONTAINER_bloomfilter_init (NULL, - compute_bloomfilter_size - (replies_seen_count), - BLOOMFILTER_K); - } - for (i = 0; i < pr->replies_seen_count; i++) + GNUNET_BLOCK_construct_bloomfilter (pr->mingle, + replies_seen, + replies_seen_count); + } + else { - GNUNET_BLOCK_mingle_hash (&replies_seen[i], pr->mingle, &mhash); - GNUNET_CONTAINER_bloomfilter_add (pr->bf, &mhash); + for (i = 0; i < pr->replies_seen_count; i++) + { + GNUNET_BLOCK_mingle_hash (&replies_seen[i], pr->mingle, &mhash); + GNUNET_CONTAINER_bloomfilter_add (pr->bf, &mhash); + } } } } diff --git a/src/include/gnunet_constants.h b/src/include/gnunet_constants.h index 190cabbb0..7315c9c73 100644 --- a/src/include/gnunet_constants.h +++ b/src/include/gnunet_constants.h @@ -128,6 +128,13 @@ extern "C" #define GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE (63 * 1024) +/** + * K-value that must be used for the bloom filters in 'GET' + * queries. + */ +#define GNUNET_CONSTANTS_BLOOMFILTER_K 16 + + #if 0 /* keep Emacsens' auto-indent happy */ { diff --git a/src/include/gnunet_dht_service.h b/src/include/gnunet_dht_service.h index a8d4d67ec..4a5ab7684 100644 --- a/src/include/gnunet_dht_service.h +++ b/src/include/gnunet_dht_service.h @@ -46,10 +46,10 @@ extern "C" #define GNUNET_DHT_DEFAULT_REPUBLISH_FREQUENCY GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_MINUTES, 60) /** - * K-value that must be used for the bloom filter 'GET' + * K-value that must be used for the bloom filters in 'GET' * queries. */ -#define GNUNET_DHT_GET_BLOOMFILTER_K 16 +#define GNUNET_DHT_GET_BLOOMFILTER_K GNUNET_CONSTANTS_BLOOMFILTER_K /** * Non-intelligent default DHT GET replication. diff --git a/src/include/gnunet_protocols.h b/src/include/gnunet_protocols.h index a9a60dde6..68e78b5bb 100644 --- a/src/include/gnunet_protocols.h +++ b/src/include/gnunet_protocols.h @@ -624,17 +624,52 @@ extern "C" * DHT message types ******************************************************************************/ +/** + * Client wants to store item in DHT. + */ +#define GNUNET_MESSAGE_TYPE_DHT_CLIENT_PUT 142 + +/** + * Client wants to lookup item in DHT. + */ +#define GNUNET_MESSAGE_TYPE_DHT_CLIENT_GET 143 + +/** + * Client wants to stop search in DHT. + */ +#define GNUNET_MESSAGE_TYPE_DHT_CLIENT_GET_STOP 144 + +/** + * Service returns result to client. + */ +#define GNUNET_MESSAGE_TYPE_DHT_CLIENT_RESULT 145 + +/** + * Peer is storing data in DHT. + */ +#define GNUNET_MESSAGE_TYPE_DHT_P2P_PUT 146 + +/** + * Peer tries to find data in DHT. + */ +#define GNUNET_MESSAGE_TYPE_DHT_P2P_GET 147 + +/** + * Data is returned to peer from DHT. + */ +#define GNUNET_MESSAGE_TYPE_DHT_P2P_RESULT 148 + +// LEGACY types follow (pre3)...... + /** * Local DHT route request type */ #define GNUNET_MESSAGE_TYPE_DHT_LOCAL_ROUTE 142 -#define GNUNET_MESSAGE_TYPE_DHT_CLIENT_GET 142 /** * Local generic DHT route result type */ #define GNUNET_MESSAGE_TYPE_DHT_LOCAL_ROUTE_RESULT 143 -#define GNUNET_MESSAGE_TYPE_DHT_CLIENT_RESULT 142 /** * P2P DHT route request type @@ -650,14 +685,12 @@ extern "C" * Local generic DHT message stop type */ #define GNUNET_MESSAGE_TYPE_DHT_LOCAL_ROUTE_STOP 146 -#define GNUNET_MESSAGE_TYPE_DHT_CLIENT_GET_STOP 146 /** * Local and P2P DHT PUT message * (encapsulated in DHT_ROUTE message) */ #define GNUNET_MESSAGE_TYPE_DHT_PUT 147 -#define GNUNET_MESSAGE_TYPE_DHT_CLIENT_PUT 147 /** * Local and P2P DHT GET message -- cgit v1.2.3