From f6f7fbbe98c110867febbcca647da8308be123c7 Mon Sep 17 00:00:00 2001 From: Christian Grothoff Date: Mon, 20 Feb 2017 17:19:47 +0100 Subject: completed big block refactoring in preparation for SET-BLOCK integration --- src/fs/gnunet-service-fs_pr.c | 139 +++++++++++++++++++++++------------------- src/fs/plugin_block_fs.c | 95 +++++++++++++++++++---------- src/fs/test_plugin_block_fs.c | 6 +- 3 files changed, 142 insertions(+), 98 deletions(-) (limited to 'src/fs') diff --git a/src/fs/gnunet-service-fs_pr.c b/src/fs/gnunet-service-fs_pr.c index 63462f7dc..87e2d2ee1 100644 --- a/src/fs/gnunet-service-fs_pr.c +++ b/src/fs/gnunet-service-fs_pr.c @@ -97,9 +97,9 @@ struct GSF_PendingRequest struct GNUNET_HashCode *replies_seen; /** - * Bloomfilter masking replies we've already seen. + * Block group for filtering replies we've already seen. */ - struct GNUNET_CONTAINER_BloomFilter *bf; + struct GNUNET_BLOCK_Group *bg; /** * Entry for this pending request in the expiration heap, or NULL. @@ -189,11 +189,6 @@ struct GSF_PendingRequest */ unsigned int replies_seen_size; - /** - * Mingle value we currently use for the bf. - */ - uint32_t mingle; - /** * Do we have a first UID yet? */ @@ -248,18 +243,35 @@ static unsigned long long max_pending_requests = (32 * 1024); * fresh one of minimal size without problems) OR if our peer is the * initiator (in which case we may resize to larger than mimimum size). * + * @param type type of the request * @param pr request for which the BF is to be recomputed */ static void -refresh_bloomfilter (struct GSF_PendingRequest *pr) +refresh_bloomfilter (enum GNUNET_BLOCK_Type type, + struct GSF_PendingRequest *pr) { - 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_BLOCK_construct_bloomfilter (pr->mingle, pr->replies_seen, - pr->replies_seen_count); + if (NULL != pr->bg) + { + GNUNET_BLOCK_group_destroy (pr->bg); + pr->bg = NULL; + } + if (GNUNET_BLOCK_TYPE_FS_UBLOCK != type) + return; /* no need */ + pr->bg + = GNUNET_BLOCK_group_create (GSF_block_ctx, + type, + GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, + UINT32_MAX), + NULL, + 0, + "fs-seen-set-size", + pr->replies_seen_count); + if (NULL == pr->bg) + return; + GNUNET_break (GNUNET_OK == + GNUNET_BLOCK_group_set_seen (pr->bg, + pr->replies_seen, + pr->replies_seen_count)); } @@ -355,25 +367,30 @@ GSF_pending_request_create_ (enum GSF_PendingRequestOptions options, if (replies_seen_count > 0) { pr->replies_seen_size = replies_seen_count; - pr->replies_seen = - GNUNET_malloc (sizeof (struct GNUNET_HashCode) * pr->replies_seen_size); + pr->replies_seen = GNUNET_new_array (pr->replies_seen_size, + struct GNUNET_HashCode); GNUNET_memcpy (pr->replies_seen, - replies_seen, - replies_seen_count * sizeof (struct GNUNET_HashCode)); + replies_seen, + replies_seen_count * sizeof (struct GNUNET_HashCode)); pr->replies_seen_count = replies_seen_count; } - if (NULL != bf_data) + if ( (NULL != bf_data) && + (GNUNET_BLOCK_TYPE_FS_UBLOCK == pr->public_data.type) ) { - pr->bf = - GNUNET_CONTAINER_bloomfilter_init (bf_data, - bf_size, - GNUNET_CONSTANTS_BLOOMFILTER_K); - pr->mingle = mingle; + pr->bg + = GNUNET_BLOCK_group_create (GSF_block_ctx, + pr->public_data.type, + mingle, + bf_data, + bf_size, + "fs-seen-set-size", + 0); } else if ((replies_seen_count > 0) && (0 != (options & GSF_PRO_BLOOMFILTER_FULL_REFRESH))) { - refresh_bloomfilter (pr); + refresh_bloomfilter (pr->public_data.type, + pr); } GNUNET_CONTAINER_multihashmap_put (pr_map, &pr->public_data.query, @@ -461,46 +478,37 @@ GSF_pending_request_update_ (struct GSF_PendingRequest *pr, const struct GNUNET_HashCode * replies_seen, unsigned int replies_seen_count) { - unsigned int i; - struct GNUNET_HashCode mhash; - if (replies_seen_count + pr->replies_seen_count < pr->replies_seen_count) return; /* integer overflow */ if (0 != (pr->public_data.options & GSF_PRO_BLOOMFILTER_FULL_REFRESH)) { /* we're responsible for the BF, full refresh */ if (replies_seen_count + pr->replies_seen_count > pr->replies_seen_size) - GNUNET_array_grow (pr->replies_seen, pr->replies_seen_size, + GNUNET_array_grow (pr->replies_seen, + pr->replies_seen_size, replies_seen_count + pr->replies_seen_count); - GNUNET_memcpy (&pr->replies_seen[pr->replies_seen_count], replies_seen, - sizeof (struct GNUNET_HashCode) * replies_seen_count); + GNUNET_memcpy (&pr->replies_seen[pr->replies_seen_count], + replies_seen, + sizeof (struct GNUNET_HashCode) * replies_seen_count); pr->replies_seen_count += replies_seen_count; - refresh_bloomfilter (pr); + refresh_bloomfilter (pr->public_data.type, + pr); } else { - if (NULL == pr->bf) + if (NULL == pr->bg) { /* we're not the initiator, but the initiator did not give us * any bloom-filter, so we need to create one on-the-fly */ - pr->mingle = - GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, - UINT32_MAX); - pr->bf = - GNUNET_BLOCK_construct_bloomfilter (pr->mingle, - replies_seen, - replies_seen_count); + refresh_bloomfilter (pr->public_data.type, + pr); } else { - 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); - } + GNUNET_break (GNUNET_OK == + GNUNET_BLOCK_group_set_seen (pr->bg, + replies_seen, + pr->replies_seen_count)); } } if (NULL != pr->gh) @@ -530,6 +538,8 @@ GSF_pending_request_get_message_ (struct GSF_PendingRequest *pr) struct GNUNET_TIME_Absolute now; int64_t ttl; int do_route; + void *bf_data; + uint32_t bf_nonce; GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Building request message for `%s' of type %d\n", @@ -553,7 +563,15 @@ GSF_pending_request_get_message_ (struct GSF_PendingRequest *pr) bm |= GET_MESSAGE_BIT_TRANSMIT_TO; k++; } - bf_size = GNUNET_CONTAINER_bloomfilter_get_size (pr->bf); + if (GNUNET_OK != + GNUNET_BLOCK_group_serialize (pr->bg, + &bf_nonce, + &bf_data, + &bf_size)) + { + bf_size = 0; + bf_data = NULL; + } env = GNUNET_MQ_msg_extra (gm, bf_size + k * sizeof (struct GNUNET_PeerIdentity), GNUNET_MESSAGE_TYPE_FS_GET); @@ -571,7 +589,7 @@ GSF_pending_request_get_message_ (struct GSF_PendingRequest *pr) now = GNUNET_TIME_absolute_get (); ttl = (int64_t) (pr->public_data.ttl.abs_value_us - now.abs_value_us); gm->ttl = htonl (ttl / 1000LL / 1000LL); - gm->filter_mutator = htonl (pr->mingle); + gm->filter_mutator = htonl (bf_nonce); gm->hash_bitmap = htonl (bm); gm->query = pr->public_data.query; ext = (struct GNUNET_PeerIdentity *) &gm[1]; @@ -581,11 +599,10 @@ GSF_pending_request_get_message_ (struct GSF_PendingRequest *pr) &ext[k++]); if (NULL != pr->public_data.target) ext[k++] = *pr->public_data.target; - if (NULL != pr->bf) - GNUNET_assert (GNUNET_SYSERR != - GNUNET_CONTAINER_bloomfilter_get_raw_data (pr->bf, - (char *) &ext[k], - bf_size)); + GNUNET_memcpy (&ext[k], + bf_data, + bf_size); + GNUNET_free_non_null (bf_data); return env; } @@ -624,11 +641,8 @@ clean_request (void *cls, } GSF_plan_notify_request_done_ (pr); GNUNET_free_non_null (pr->replies_seen); - if (NULL != pr->bf) - { - GNUNET_CONTAINER_bloomfilter_free (pr->bf); - pr->bf = NULL; - } + GNUNET_BLOCK_group_destroy (pr->bg); + pr->bg = NULL; GNUNET_PEER_change_rc (pr->sender_pid, -1); pr->sender_pid = 0; GNUNET_PEER_change_rc (pr->origin_pid, -1); @@ -844,10 +858,9 @@ process_reply (void *cls, prq->eval = GNUNET_BLOCK_evaluate (GSF_block_ctx, prq->type, + pr->bg, prq->eo, key, - &pr->bf, - pr->mingle, NULL, 0, prq->data, diff --git a/src/fs/plugin_block_fs.c b/src/fs/plugin_block_fs.c index 038734082..6c574fca2 100644 --- a/src/fs/plugin_block_fs.c +++ b/src/fs/plugin_block_fs.c @@ -28,6 +28,7 @@ #include "gnunet_fs_service.h" #include "block_fs.h" #include "gnunet_signatures.h" +#include "gnunet_constants.h" #include "gnunet_block_group_lib.h" @@ -37,10 +38,36 @@ */ #define BLOOMFILTER_K 16 + /** - * How big is the BF we use for FS blocks? + * 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. + * + * @param entry_count expected number of entries in the Bloom filter + * @return must be a power of two and smaller or equal to 2^15. */ -#define FS_BF_SIZE 8 +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; +} /** @@ -51,16 +78,21 @@ * @param nonce random value used to seed the group creation * @param raw_data optional serialized prior state of the group, NULL if unavailable/fresh * @param raw_data_size number of bytes in @a raw_data, 0 if unavailable/fresh + * @param va variable arguments specific to @a type * @return block group handle, NULL if block groups are not supported * by this @a type of block (this is not an error) */ static struct GNUNET_BLOCK_Group * block_plugin_fs_create_group (void *cls, - enum GNUNET_BLOCK_Type type, - uint32_t nonce, - const void *raw_data, - size_t raw_data_size) + enum GNUNET_BLOCK_Type type, + uint32_t nonce, + const void *raw_data, + size_t raw_data_size, + va_list va) { + unsigned int size; + const char *guard; + switch (type) { case GNUNET_BLOCK_TYPE_FS_DBLOCK: @@ -68,8 +100,23 @@ block_plugin_fs_create_group (void *cls, case GNUNET_BLOCK_TYPE_FS_IBLOCK: return NULL; case GNUNET_BLOCK_TYPE_FS_UBLOCK: + guard = va_arg (va, const char *); + if (0 != memcmp (guard, + "fs-seen-set-size", + strlen ("fs-seen-set-size"))) + { + /* va-args invalid! bad bug, complain! */ + GNUNET_break (0); + size = 8; + } + else + { + size = compute_bloomfilter_size (va_arg (va, unsigned int)); + } + if (0 == size) + size = raw_data_size; /* not for us to determine, use what we got! */ return GNUNET_BLOCK_GROUP_bf_create (cls, - FS_BF_SIZE, + size, BLOOMFILTER_K, type, nonce, @@ -91,10 +138,9 @@ block_plugin_fs_create_group (void *cls, * * @param cls closure * @param type block type + * @param bg group to use for evaluation * @param eo control flags * @param query original query (hash) - * @param bf pointer to bloom filter associated with query; possibly updated (!) - * @param bf_mutator mutation value for @a bf * @param xquery extrended query data (can be NULL, depending on type) * @param xquery_size number of bytes in @a xquery * @param reply_block response to validate @@ -104,10 +150,9 @@ block_plugin_fs_create_group (void *cls, static enum GNUNET_BLOCK_EvaluationResult block_plugin_fs_evaluate (void *cls, enum GNUNET_BLOCK_Type type, + struct GNUNET_BLOCK_Group *bg, enum GNUNET_BLOCK_EvaluationOptions eo, const struct GNUNET_HashCode *query, - struct GNUNET_CONTAINER_BloomFilter **bf, - int32_t bf_mutator, const void *xquery, size_t xquery_size, const void *reply_block, @@ -116,7 +161,6 @@ block_plugin_fs_evaluate (void *cls, const struct UBlock *ub; struct GNUNET_HashCode hc; struct GNUNET_HashCode chash; - struct GNUNET_HashCode mhash; switch (type) { @@ -170,26 +214,13 @@ block_plugin_fs_evaluate (void *cls, GNUNET_break_op (0); return GNUNET_BLOCK_EVALUATION_RESULT_INVALID; } - if (NULL != bf) - { - GNUNET_CRYPTO_hash (reply_block, - reply_block_size, - &chash); - GNUNET_BLOCK_mingle_hash (&chash, - bf_mutator, - &mhash); - if (NULL != *bf) - { - if (GNUNET_YES == - GNUNET_CONTAINER_bloomfilter_test (*bf, &mhash)) - return GNUNET_BLOCK_EVALUATION_OK_DUPLICATE; - } - else - { - *bf = GNUNET_CONTAINER_bloomfilter_init (NULL, 8, BLOOMFILTER_K); - } - GNUNET_CONTAINER_bloomfilter_add (*bf, &mhash); - } + GNUNET_CRYPTO_hash (reply_block, + reply_block_size, + &chash); + if (GNUNET_YES == + GNUNET_BLOCK_GROUP_bf_test_and_set (bg, + &chash)) + return GNUNET_BLOCK_EVALUATION_OK_DUPLICATE; return GNUNET_BLOCK_EVALUATION_OK_MORE; default: return GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED; diff --git a/src/fs/test_plugin_block_fs.c b/src/fs/test_plugin_block_fs.c index 1fc9f2110..ba4f28bc5 100644 --- a/src/fs/test_plugin_block_fs.c +++ b/src/fs/test_plugin_block_fs.c @@ -40,28 +40,28 @@ test_fs (struct GNUNET_BLOCK_Context *ctx) if (GNUNET_BLOCK_EVALUATION_OK_LAST != GNUNET_BLOCK_evaluate (ctx, GNUNET_BLOCK_TYPE_FS_DBLOCK, + NULL, GNUNET_BLOCK_EO_NONE, &key, NULL, 0, - NULL, 0, block, sizeof (block))) return 2; if (GNUNET_BLOCK_EVALUATION_REQUEST_VALID != GNUNET_BLOCK_evaluate (ctx, GNUNET_BLOCK_TYPE_FS_DBLOCK, + NULL, GNUNET_BLOCK_EO_NONE, &key, NULL, 0, - NULL, 0, NULL, 0)) return 4; GNUNET_log_skip (1, GNUNET_NO); if (GNUNET_BLOCK_EVALUATION_REQUEST_INVALID != GNUNET_BLOCK_evaluate (ctx, GNUNET_BLOCK_TYPE_FS_DBLOCK, + NULL, GNUNET_BLOCK_EO_NONE, &key, - NULL, 0, "bogus", 5, NULL, 0)) return 8; -- cgit v1.2.3