From 4ba0fa6ba9f9be044c8c96ddd4d909e7d84403b5 Mon Sep 17 00:00:00 2001 From: Christian Grothoff Date: Wed, 22 Feb 2017 13:41:33 +0100 Subject: [PATCH] support BF size adjustments in other plugins --- po/POTFILES.in | 1 + src/block/plugin_block_template.c | 49 +++++++++++++++++++ src/block/plugin_block_test.c | 51 +++++++++++++++++++- src/dht/gnunet-service-dht_clients.c | 3 +- src/dht/gnunet-service-dht_neighbours.c | 6 ++- src/dht/plugin_block_dht.c | 1 + src/fs/gnunet-service-fs_pr.c | 10 ++-- src/fs/plugin_block_fs.c | 8 +++- src/gns/plugin_block_gns.c | 51 +++++++++++++++++++- src/regex/plugin_block_regex.c | 62 +++++++++++++++++++++++-- 10 files changed, 228 insertions(+), 14 deletions(-) diff --git a/po/POTFILES.in b/po/POTFILES.in index a1fd41d82..03eca63fa 100644 --- a/po/POTFILES.in +++ b/po/POTFILES.in @@ -41,6 +41,7 @@ src/cadet/cadet_api_new.c src/cadet/cadet_common.c src/cadet/cadet_path.c src/cadet/cadet_test_lib.c +src/cadet/cadet_test_lib_new.c src/cadet/desirability_table.c src/cadet/gnunet-cadet.c src/cadet/gnunet-cadet-profiler.c diff --git a/src/block/plugin_block_template.c b/src/block/plugin_block_template.c index 0e8107af2..f11d5ee76 100644 --- a/src/block/plugin_block_template.c +++ b/src/block/plugin_block_template.c @@ -43,6 +43,37 @@ #define TEMPLATE_BF_SIZE 8 +/** + * 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. + */ +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; +} + + /** * Create a new block group. * @@ -63,6 +94,24 @@ block_plugin_template_create_group (void *cls, size_t raw_data_size, va_list va) { + unsigned int bf_size; + const char *guard; + + guard = va_arg (va, const char *); + if (0 == memcmp (guard, + "seen-set-size", + strlen ("seen-set-size"))) + bf_size = compute_bloomfilter_size (va_arg (va, unsigned int)); + else if (0 == memcmp (guard, + "filter-size", + strlen ("filter-size"))) + bf_size = va_arg (va, unsigned int); + else + { + GNUNET_break (0); + bf_size = TEMPLATE_BF_SIZE; + } + GNUNET_break (NULL == va_arg (va, const char *)); return GNUNET_BLOCK_GROUP_bf_create (cls, TEMPLATE_BF_SIZE, BLOOMFILTER_K, diff --git a/src/block/plugin_block_test.c b/src/block/plugin_block_test.c index 615f1571b..c5483f26e 100644 --- a/src/block/plugin_block_test.c +++ b/src/block/plugin_block_test.c @@ -41,6 +41,37 @@ #define TEST_BF_SIZE 8 +/** + * 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. + */ +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; +} + + /** * Create a new block group. * @@ -61,8 +92,26 @@ block_plugin_test_create_group (void *cls, size_t raw_data_size, va_list va) { + unsigned int bf_size; + const char *guard; + + guard = va_arg (va, const char *); + if (0 == memcmp (guard, + "seen-set-size", + strlen ("seen-set-size"))) + bf_size = compute_bloomfilter_size (va_arg (va, unsigned int)); + else if (0 == memcmp (guard, + "filter-size", + strlen ("filter-size"))) + bf_size = va_arg (va, unsigned int); + else + { + GNUNET_break (0); + bf_size = TEST_BF_SIZE; + } + GNUNET_break (NULL == va_arg (va, const char *)); return GNUNET_BLOCK_GROUP_bf_create (cls, - TEST_BF_SIZE, + bf_size, BLOOMFILTER_K, type, nonce, diff --git a/src/dht/gnunet-service-dht_clients.c b/src/dht/gnunet-service-dht_clients.c index c304f2e54..0f521a401 100644 --- a/src/dht/gnunet-service-dht_clients.c +++ b/src/dht/gnunet-service-dht_clients.c @@ -376,7 +376,8 @@ transmit_request (struct ClientQueryRecord *cqr) NULL, 0, "seen-set-size", - cqr->seen_replies_count); + cqr->seen_replies_count, + NULL); GNUNET_BLOCK_group_set_seen (bg, cqr->seen_replies, cqr->seen_replies_count); diff --git a/src/dht/gnunet-service-dht_neighbours.c b/src/dht/gnunet-service-dht_neighbours.c index 6eef05c20..9e1cecfcd 100644 --- a/src/dht/gnunet-service-dht_neighbours.c +++ b/src/dht/gnunet-service-dht_neighbours.c @@ -663,7 +663,8 @@ send_find_peer_message (void *cls) NULL, 0, "filter-size", - DHT_BLOOM_SIZE); + DHT_BLOOM_SIZE, + NULL); GNUNET_CONTAINER_multipeermap_iterate (all_connected_peers, &add_known_to_bloom, bg); @@ -2091,7 +2092,8 @@ handle_dht_p2p_get (void *cls, &xquery[xquery_size], reply_bf_size, "filter-size", - reply_bf_size); + reply_bf_size, + NULL); /* remember request for routing replies */ GDS_ROUTING_add (peer->id, type, diff --git a/src/dht/plugin_block_dht.c b/src/dht/plugin_block_dht.c index 26975e125..72480536c 100644 --- a/src/dht/plugin_block_dht.c +++ b/src/dht/plugin_block_dht.c @@ -108,6 +108,7 @@ block_plugin_dht_create_group (void *cls, GNUNET_break (0); bf_size = 8; } + GNUNET_break (NULL == va_arg (va, const char *)); return GNUNET_BLOCK_GROUP_bf_create (cls, bf_size, BLOOMFILTER_K, diff --git a/src/fs/gnunet-service-fs_pr.c b/src/fs/gnunet-service-fs_pr.c index 87e2d2ee1..b0fda24b5 100644 --- a/src/fs/gnunet-service-fs_pr.c +++ b/src/fs/gnunet-service-fs_pr.c @@ -264,8 +264,9 @@ refresh_bloomfilter (enum GNUNET_BLOCK_Type type, UINT32_MAX), NULL, 0, - "fs-seen-set-size", - pr->replies_seen_count); + "seen-set-size", + pr->replies_seen_count, + NULL); if (NULL == pr->bg) return; GNUNET_break (GNUNET_OK == @@ -383,8 +384,9 @@ GSF_pending_request_create_ (enum GSF_PendingRequestOptions options, mingle, bf_data, bf_size, - "fs-seen-set-size", - 0); + "seen-set-size", + 0, + NULL); } else if ((replies_seen_count > 0) && (0 != (options & GSF_PRO_BLOOMFILTER_FULL_REFRESH))) diff --git a/src/fs/plugin_block_fs.c b/src/fs/plugin_block_fs.c index 5ccbd237e..bea6b148c 100644 --- a/src/fs/plugin_block_fs.c +++ b/src/fs/plugin_block_fs.c @@ -95,14 +95,16 @@ block_plugin_fs_create_group (void *cls, switch (type) { case GNUNET_BLOCK_TYPE_FS_DBLOCK: + GNUNET_break (NULL == va_arg (va, const char *)); return NULL; case GNUNET_BLOCK_TYPE_FS_IBLOCK: + GNUNET_break (NULL == va_arg (va, const char *)); 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"))) + "seen-set-size", + strlen ("seen-set-size"))) { /* va-args invalid! bad bug, complain! */ GNUNET_break (0); @@ -114,6 +116,7 @@ block_plugin_fs_create_group (void *cls, } if (0 == size) size = raw_data_size; /* not for us to determine, use what we got! */ + GNUNET_break (NULL == va_arg (va, const char *)); return GNUNET_BLOCK_GROUP_bf_create (cls, size, BLOOMFILTER_K, @@ -122,6 +125,7 @@ block_plugin_fs_create_group (void *cls, raw_data, raw_data_size); default: + GNUNET_break (NULL == va_arg (va, const char *)); GNUNET_break (0); return NULL; } diff --git a/src/gns/plugin_block_gns.c b/src/gns/plugin_block_gns.c index 94222e32b..300dbc020 100644 --- a/src/gns/plugin_block_gns.c +++ b/src/gns/plugin_block_gns.c @@ -43,6 +43,37 @@ #define GNS_BF_SIZE 8 +/** + * 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. + */ +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; +} + + /** * Create a new block group. * @@ -63,8 +94,26 @@ block_plugin_gns_create_group (void *cls, size_t raw_data_size, va_list va) { + unsigned int bf_size; + const char *guard; + + guard = va_arg (va, const char *); + if (0 == memcmp (guard, + "seen-set-size", + strlen ("seen-set-size"))) + bf_size = compute_bloomfilter_size (va_arg (va, unsigned int)); + else if (0 == memcmp (guard, + "filter-size", + strlen ("filter-size"))) + bf_size = va_arg (va, unsigned int); + else + { + GNUNET_break (0); + bf_size = GNS_BF_SIZE; + } + GNUNET_break (NULL == va_arg (va, const char *)); return GNUNET_BLOCK_GROUP_bf_create (cls, - GNS_BF_SIZE, + bf_size, BLOOMFILTER_K, type, nonce, diff --git a/src/regex/plugin_block_regex.c b/src/regex/plugin_block_regex.c index 6636f3cdb..b9814c737 100644 --- a/src/regex/plugin_block_regex.c +++ b/src/regex/plugin_block_regex.c @@ -28,16 +28,54 @@ #include "gnunet_block_group_lib.h" #include "block_regex.h" #include "regex_block_lib.h" -#include "gnunet_constants.h" #include "gnunet_signatures.h" + +/** + * Number of bits we set per entry in the bloomfilter. + * Do not change! + */ +#define BLOOMFILTER_K 16 + + /** * How big is the BF we use for REGEX blocks? */ #define REGEX_BF_SIZE 8 +/** + * 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. + */ +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; +} + + /** * Create a new block group. * @@ -58,9 +96,27 @@ block_plugin_regex_create_group (void *cls, size_t raw_data_size, va_list va) { + unsigned int bf_size; + const char *guard; + + guard = va_arg (va, const char *); + if (0 == memcmp (guard, + "seen-set-size", + strlen ("seen-set-size"))) + bf_size = compute_bloomfilter_size (va_arg (va, unsigned int)); + else if (0 == memcmp (guard, + "filter-size", + strlen ("filter-size"))) + bf_size = va_arg (va, unsigned int); + else + { + GNUNET_break (0); + bf_size = REGEX_BF_SIZE; + } + GNUNET_break (NULL == va_arg (va, const char *)); return GNUNET_BLOCK_GROUP_bf_create (cls, - REGEX_BF_SIZE, - GNUNET_CONSTANTS_BLOOMFILTER_K, + bf_size, + BLOOMFILTER_K, type, nonce, raw_data, -- 2.25.1