diff options
author | Christian Grothoff <christian@grothoff.org> | 2017-02-26 22:42:40 +0100 |
---|---|---|
committer | Christian Grothoff <christian@grothoff.org> | 2017-02-26 22:42:40 +0100 |
commit | 8d7c29c4684f807d5e9a3004bbbab132b158c5aa (patch) | |
tree | 9eca177e00a387d0c18395fde7dbf91289272d98 /src | |
parent | e87663cf00dd102e8bb60f400db4bad6d82b3b6c (diff) | |
download | gnunet-8d7c29c4684f807d5e9a3004bbbab132b158c5aa.tar.gz gnunet-8d7c29c4684f807d5e9a3004bbbab132b158c5aa.zip |
ensure all plugins properly use BF, move shared logic to shared library
Diffstat (limited to 'src')
-rw-r--r-- | src/block/bg_bf.c | 32 | ||||
-rw-r--r-- | src/block/plugin_block_template.c | 34 | ||||
-rw-r--r-- | src/block/plugin_block_test.c | 34 | ||||
-rw-r--r-- | src/dht/plugin_block_dht.c | 34 | ||||
-rw-r--r-- | src/dns/plugin_block_dns.c | 66 | ||||
-rw-r--r-- | src/fs/plugin_block_fs.c | 34 | ||||
-rw-r--r-- | src/gns/plugin_block_gns.c | 34 | ||||
-rw-r--r-- | src/include/gnunet_block_group_lib.h | 18 | ||||
-rw-r--r-- | src/regex/plugin_block_regex.c | 35 |
9 files changed, 127 insertions, 194 deletions
diff --git a/src/block/bg_bf.c b/src/block/bg_bf.c index 9c4dc9060..1a17ec84e 100644 --- a/src/block/bg_bf.c +++ b/src/block/bg_bf.c | |||
@@ -232,4 +232,36 @@ GNUNET_BLOCK_GROUP_bf_test_and_set (struct GNUNET_BLOCK_Group *bg, | |||
232 | } | 232 | } |
233 | 233 | ||
234 | 234 | ||
235 | /** | ||
236 | * How many bytes should a bloomfilter be if we have already seen | ||
237 | * entry_count responses? Sized so that do not have to | ||
238 | * re-size the filter too often (to keep it cheap). | ||
239 | * | ||
240 | * Since other peers will also add entries but not resize the filter, | ||
241 | * we should generally pick a slightly larger size than what the | ||
242 | * strict math would suggest. | ||
243 | * | ||
244 | * @param entry_count expected number of entries in the Bloom filter | ||
245 | * @param k number of bits set per entry | ||
246 | * @return must be a power of two and smaller or equal to 2^15. | ||
247 | */ | ||
248 | size_t | ||
249 | GNUNET_BLOCK_GROUP_compute_bloomfilter_size (unsigned int entry_count, | ||
250 | unsigned int k) | ||
251 | { | ||
252 | size_t size; | ||
253 | unsigned int ideal = (entry_count * k) / 4; | ||
254 | uint16_t max = 1 << 15; | ||
255 | |||
256 | if (entry_count > max) | ||
257 | return max; | ||
258 | size = 8; | ||
259 | while ((size < max) && (size < ideal)) | ||
260 | size *= 2; | ||
261 | if (size > max) | ||
262 | return max; | ||
263 | return size; | ||
264 | } | ||
265 | |||
266 | |||
235 | /* end of bg_bf.c */ | 267 | /* end of bg_bf.c */ |
diff --git a/src/block/plugin_block_template.c b/src/block/plugin_block_template.c index 87adae7e9..b714b6858 100644 --- a/src/block/plugin_block_template.c +++ b/src/block/plugin_block_template.c | |||
@@ -44,37 +44,6 @@ | |||
44 | 44 | ||
45 | 45 | ||
46 | /** | 46 | /** |
47 | * How many bytes should a bloomfilter be if we have already seen | ||
48 | * entry_count responses? Note that #GNUNET_CONSTANTS_BLOOMFILTER_K | ||
49 | * gives us the number of bits set per entry. Furthermore, we should | ||
50 | * not re-size the filter too often (to keep it cheap). | ||
51 | * | ||
52 | * Since other peers will also add entries but not resize the filter, | ||
53 | * we should generally pick a slightly larger size than what the | ||
54 | * strict math would suggest. | ||
55 | * | ||
56 | * @param entry_count expected number of entries in the Bloom filter | ||
57 | * @return must be a power of two and smaller or equal to 2^15. | ||
58 | */ | ||
59 | static size_t | ||
60 | compute_bloomfilter_size (unsigned int entry_count) | ||
61 | { | ||
62 | size_t size; | ||
63 | unsigned int ideal = (entry_count * BLOOMFILTER_K) / 4; | ||
64 | uint16_t max = 1 << 15; | ||
65 | |||
66 | if (entry_count > max) | ||
67 | return max; | ||
68 | size = 8; | ||
69 | while ((size < max) && (size < ideal)) | ||
70 | size *= 2; | ||
71 | if (size > max) | ||
72 | return max; | ||
73 | return size; | ||
74 | } | ||
75 | |||
76 | |||
77 | /** | ||
78 | * Create a new block group. | 47 | * Create a new block group. |
79 | * | 48 | * |
80 | * @param ctx block context in which the block group is created | 49 | * @param ctx block context in which the block group is created |
@@ -100,7 +69,8 @@ block_plugin_template_create_group (void *cls, | |||
100 | guard = va_arg (va, const char *); | 69 | guard = va_arg (va, const char *); |
101 | if (0 == strcmp (guard, | 70 | if (0 == strcmp (guard, |
102 | "seen-set-size")) | 71 | "seen-set-size")) |
103 | bf_size = compute_bloomfilter_size (va_arg (va, unsigned int)); | 72 | bf_size = GNUNET_BLOCK_GROUP_compute_bloomfilter_size (va_arg (va, unsigned int), |
73 | BLOOMFILTER_K); | ||
104 | else if (0 == strcmp (guard, | 74 | else if (0 == strcmp (guard, |
105 | "filter-size")) | 75 | "filter-size")) |
106 | bf_size = va_arg (va, unsigned int); | 76 | bf_size = va_arg (va, unsigned int); |
diff --git a/src/block/plugin_block_test.c b/src/block/plugin_block_test.c index 31112e5dd..b9f71cacb 100644 --- a/src/block/plugin_block_test.c +++ b/src/block/plugin_block_test.c | |||
@@ -42,37 +42,6 @@ | |||
42 | 42 | ||
43 | 43 | ||
44 | /** | 44 | /** |
45 | * How many bytes should a bloomfilter be if we have already seen | ||
46 | * entry_count responses? Note that #GNUNET_CONSTANTS_BLOOMFILTER_K | ||
47 | * gives us the number of bits set per entry. Furthermore, we should | ||
48 | * not re-size the filter too often (to keep it cheap). | ||
49 | * | ||
50 | * Since other peers will also add entries but not resize the filter, | ||
51 | * we should generally pick a slightly larger size than what the | ||
52 | * strict math would suggest. | ||
53 | * | ||
54 | * @param entry_count expected number of entries in the Bloom filter | ||
55 | * @return must be a power of two and smaller or equal to 2^15. | ||
56 | */ | ||
57 | static size_t | ||
58 | compute_bloomfilter_size (unsigned int entry_count) | ||
59 | { | ||
60 | size_t size; | ||
61 | unsigned int ideal = (entry_count * BLOOMFILTER_K) / 4; | ||
62 | uint16_t max = 1 << 15; | ||
63 | |||
64 | if (entry_count > max) | ||
65 | return max; | ||
66 | size = 8; | ||
67 | while ((size < max) && (size < ideal)) | ||
68 | size *= 2; | ||
69 | if (size > max) | ||
70 | return max; | ||
71 | return size; | ||
72 | } | ||
73 | |||
74 | |||
75 | /** | ||
76 | * Create a new block group. | 45 | * Create a new block group. |
77 | * | 46 | * |
78 | * @param ctx block context in which the block group is created | 47 | * @param ctx block context in which the block group is created |
@@ -98,7 +67,8 @@ block_plugin_test_create_group (void *cls, | |||
98 | guard = va_arg (va, const char *); | 67 | guard = va_arg (va, const char *); |
99 | if (0 == strcmp (guard, | 68 | if (0 == strcmp (guard, |
100 | "seen-set-size")) | 69 | "seen-set-size")) |
101 | bf_size = compute_bloomfilter_size (va_arg (va, unsigned int)); | 70 | bf_size = GNUNET_BLOCK_GROUP_compute_bloomfilter_size (va_arg (va, unsigned int), |
71 | BLOOMFILTER_K); | ||
102 | else if (0 == strcmp (guard, | 72 | else if (0 == strcmp (guard, |
103 | "filter-size")) | 73 | "filter-size")) |
104 | bf_size = va_arg (va, unsigned int); | 74 | bf_size = va_arg (va, unsigned int); |
diff --git a/src/dht/plugin_block_dht.c b/src/dht/plugin_block_dht.c index 29c08dd50..74498746c 100644 --- a/src/dht/plugin_block_dht.c +++ b/src/dht/plugin_block_dht.c | |||
@@ -41,37 +41,6 @@ | |||
41 | 41 | ||
42 | 42 | ||
43 | /** | 43 | /** |
44 | * How many bytes should a bloomfilter be if we have already seen | ||
45 | * entry_count responses? Note that #GNUNET_CONSTANTS_BLOOMFILTER_K | ||
46 | * gives us the number of bits set per entry. Furthermore, we should | ||
47 | * not re-size the filter too often (to keep it cheap). | ||
48 | * | ||
49 | * Since other peers will also add entries but not resize the filter, | ||
50 | * we should generally pick a slightly larger size than what the | ||
51 | * strict math would suggest. | ||
52 | * | ||
53 | * @param entry_count expected number of entries in the Bloom filter | ||
54 | * @return must be a power of two and smaller or equal to 2^15. | ||
55 | */ | ||
56 | static size_t | ||
57 | compute_bloomfilter_size (unsigned int entry_count) | ||
58 | { | ||
59 | size_t size; | ||
60 | unsigned int ideal = (entry_count * BLOOMFILTER_K) / 4; | ||
61 | uint16_t max = 1 << 15; | ||
62 | |||
63 | if (entry_count > max) | ||
64 | return max; | ||
65 | size = 8; | ||
66 | while ((size < max) && (size < ideal)) | ||
67 | size *= 2; | ||
68 | if (size > max) | ||
69 | return max; | ||
70 | return size; | ||
71 | } | ||
72 | |||
73 | |||
74 | /** | ||
75 | * Create a new block group. | 44 | * Create a new block group. |
76 | * | 45 | * |
77 | * @param ctx block context in which the block group is created | 46 | * @param ctx block context in which the block group is created |
@@ -97,7 +66,8 @@ block_plugin_dht_create_group (void *cls, | |||
97 | guard = va_arg (va, const char *); | 66 | guard = va_arg (va, const char *); |
98 | if (0 == strcmp (guard, | 67 | if (0 == strcmp (guard, |
99 | "seen-set-size")) | 68 | "seen-set-size")) |
100 | bf_size = compute_bloomfilter_size (va_arg (va, unsigned int)); | 69 | bf_size = GNUNET_BLOCK_GROUP_compute_bloomfilter_size (va_arg (va, unsigned int), |
70 | BLOOMFILTER_K); | ||
101 | else if (0 == strcmp (guard, | 71 | else if (0 == strcmp (guard, |
102 | "filter-size")) | 72 | "filter-size")) |
103 | bf_size = va_arg (va, unsigned int); | 73 | bf_size = va_arg (va, unsigned int); |
diff --git a/src/dns/plugin_block_dns.c b/src/dns/plugin_block_dns.c index 65da0de63..fe416e450 100644 --- a/src/dns/plugin_block_dns.c +++ b/src/dns/plugin_block_dns.c | |||
@@ -1,6 +1,6 @@ | |||
1 | /* | 1 | /* |
2 | This file is part of GNUnet | 2 | This file is part of GNUnet |
3 | Copyright (C) 2013 GNUnet e.V. | 3 | Copyright (C) 2013, 2017 GNUnet e.V. |
4 | 4 | ||
5 | GNUnet is free software; you can redistribute it and/or modify | 5 | GNUnet is free software; you can redistribute it and/or modify |
6 | it under the terms of the GNU General Public License as published | 6 | it under the terms of the GNU General Public License as published |
@@ -31,6 +31,61 @@ | |||
31 | #include "gnunet_block_plugin.h" | 31 | #include "gnunet_block_plugin.h" |
32 | #include "block_dns.h" | 32 | #include "block_dns.h" |
33 | #include "gnunet_signatures.h" | 33 | #include "gnunet_signatures.h" |
34 | #include "gnunet_block_group_lib.h" | ||
35 | |||
36 | |||
37 | /** | ||
38 | * Number of bits we set per entry in the bloomfilter. | ||
39 | * Do not change! | ||
40 | */ | ||
41 | #define BLOOMFILTER_K 16 | ||
42 | |||
43 | |||
44 | /** | ||
45 | * Create a new block group. | ||
46 | * | ||
47 | * @param ctx block context in which the block group is created | ||
48 | * @param type type of the block for which we are creating the group | ||
49 | * @param nonce random value used to seed the group creation | ||
50 | * @param raw_data optional serialized prior state of the group, NULL if unavailable/fresh | ||
51 | * @param raw_data_size number of bytes in @a raw_data, 0 if unavailable/fresh | ||
52 | * @param va variable arguments specific to @a type | ||
53 | * @return block group handle, NULL if block groups are not supported | ||
54 | * by this @a type of block (this is not an error) | ||
55 | */ | ||
56 | static struct GNUNET_BLOCK_Group * | ||
57 | block_plugin_dns_create_group (void *cls, | ||
58 | enum GNUNET_BLOCK_Type type, | ||
59 | uint32_t nonce, | ||
60 | const void *raw_data, | ||
61 | size_t raw_data_size, | ||
62 | va_list va) | ||
63 | { | ||
64 | unsigned int bf_size; | ||
65 | const char *guard; | ||
66 | |||
67 | guard = va_arg (va, const char *); | ||
68 | if (0 == strcmp (guard, | ||
69 | "seen-set-size")) | ||
70 | bf_size = GNUNET_BLOCK_GROUP_compute_bloomfilter_size (va_arg (va, unsigned int), | ||
71 | BLOOMFILTER_K); | ||
72 | else if (0 == strcmp (guard, | ||
73 | "filter-size")) | ||
74 | bf_size = va_arg (va, unsigned int); | ||
75 | else | ||
76 | { | ||
77 | GNUNET_break (0); | ||
78 | bf_size = 8; | ||
79 | } | ||
80 | GNUNET_break (NULL == va_arg (va, const char *)); | ||
81 | return GNUNET_BLOCK_GROUP_bf_create (cls, | ||
82 | bf_size, | ||
83 | BLOOMFILTER_K, | ||
84 | type, | ||
85 | nonce, | ||
86 | raw_data, | ||
87 | raw_data_size); | ||
88 | } | ||
34 | 89 | ||
35 | 90 | ||
36 | /** | 91 | /** |
@@ -60,6 +115,7 @@ block_plugin_dns_evaluate (void *cls, | |||
60 | size_t reply_block_size) | 115 | size_t reply_block_size) |
61 | { | 116 | { |
62 | const struct GNUNET_DNS_Advertisement *ad; | 117 | const struct GNUNET_DNS_Advertisement *ad; |
118 | struct GNUNET_HashCode phash; | ||
63 | 119 | ||
64 | switch (type) | 120 | switch (type) |
65 | { | 121 | { |
@@ -101,6 +157,13 @@ block_plugin_dns_evaluate (void *cls, | |||
101 | GNUNET_break_op (0); | 157 | GNUNET_break_op (0); |
102 | return GNUNET_BLOCK_EVALUATION_RESULT_INVALID; | 158 | return GNUNET_BLOCK_EVALUATION_RESULT_INVALID; |
103 | } | 159 | } |
160 | GNUNET_CRYPTO_hash (reply_block, | ||
161 | reply_block_size, | ||
162 | &phash); | ||
163 | if (GNUNET_YES == | ||
164 | GNUNET_BLOCK_GROUP_bf_test_and_set (bg, | ||
165 | &phash)) | ||
166 | return GNUNET_BLOCK_EVALUATION_OK_DUPLICATE; | ||
104 | return GNUNET_BLOCK_EVALUATION_OK_MORE; | 167 | return GNUNET_BLOCK_EVALUATION_OK_MORE; |
105 | default: | 168 | default: |
106 | return GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED; | 169 | return GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED; |
@@ -147,6 +210,7 @@ libgnunet_plugin_block_dns_init (void *cls) | |||
147 | api = GNUNET_new (struct GNUNET_BLOCK_PluginFunctions); | 210 | api = GNUNET_new (struct GNUNET_BLOCK_PluginFunctions); |
148 | api->evaluate = &block_plugin_dns_evaluate; | 211 | api->evaluate = &block_plugin_dns_evaluate; |
149 | api->get_key = &block_plugin_dns_get_key; | 212 | api->get_key = &block_plugin_dns_get_key; |
213 | api->create_group = &block_plugin_dns_create_group; | ||
150 | api->types = types; | 214 | api->types = types; |
151 | return api; | 215 | return api; |
152 | } | 216 | } |
diff --git a/src/fs/plugin_block_fs.c b/src/fs/plugin_block_fs.c index 996c06dcb..b6749b418 100644 --- a/src/fs/plugin_block_fs.c +++ b/src/fs/plugin_block_fs.c | |||
@@ -39,37 +39,6 @@ | |||
39 | 39 | ||
40 | 40 | ||
41 | /** | 41 | /** |
42 | * How many bytes should a bloomfilter be if we have already seen | ||
43 | * entry_count responses? Note that #GNUNET_CONSTANTS_BLOOMFILTER_K | ||
44 | * gives us the number of bits set per entry. Furthermore, we should | ||
45 | * not re-size the filter too often (to keep it cheap). | ||
46 | * | ||
47 | * Since other peers will also add entries but not resize the filter, | ||
48 | * we should generally pick a slightly larger size than what the | ||
49 | * strict math would suggest. | ||
50 | * | ||
51 | * @param entry_count expected number of entries in the Bloom filter | ||
52 | * @return must be a power of two and smaller or equal to 2^15. | ||
53 | */ | ||
54 | static size_t | ||
55 | compute_bloomfilter_size (unsigned int entry_count) | ||
56 | { | ||
57 | size_t size; | ||
58 | unsigned int ideal = (entry_count * BLOOMFILTER_K) / 4; | ||
59 | uint16_t max = 1 << 15; | ||
60 | |||
61 | if (entry_count > max) | ||
62 | return max; | ||
63 | size = 8; | ||
64 | while ((size < max) && (size < ideal)) | ||
65 | size *= 2; | ||
66 | if (size > max) | ||
67 | return max; | ||
68 | return size; | ||
69 | } | ||
70 | |||
71 | |||
72 | /** | ||
73 | * Create a new block group. | 42 | * Create a new block group. |
74 | * | 43 | * |
75 | * @param ctx block context in which the block group is created | 44 | * @param ctx block context in which the block group is created |
@@ -111,7 +80,8 @@ block_plugin_fs_create_group (void *cls, | |||
111 | } | 80 | } |
112 | else | 81 | else |
113 | { | 82 | { |
114 | size = compute_bloomfilter_size (va_arg (va, unsigned int)); | 83 | size = GNUNET_BLOCK_GROUP_compute_bloomfilter_size (va_arg (va, unsigned int), |
84 | BLOOMFILTER_K); | ||
115 | } | 85 | } |
116 | if (0 == size) | 86 | if (0 == size) |
117 | size = raw_data_size; /* not for us to determine, use what we got! */ | 87 | size = raw_data_size; /* not for us to determine, use what we got! */ |
diff --git a/src/gns/plugin_block_gns.c b/src/gns/plugin_block_gns.c index 8ce2d85da..2ef48f094 100644 --- a/src/gns/plugin_block_gns.c +++ b/src/gns/plugin_block_gns.c | |||
@@ -44,37 +44,6 @@ | |||
44 | 44 | ||
45 | 45 | ||
46 | /** | 46 | /** |
47 | * How many bytes should a bloomfilter be if we have already seen | ||
48 | * entry_count responses? Note that #GNUNET_CONSTANTS_BLOOMFILTER_K | ||
49 | * gives us the number of bits set per entry. Furthermore, we should | ||
50 | * not re-size the filter too often (to keep it cheap). | ||
51 | * | ||
52 | * Since other peers will also add entries but not resize the filter, | ||
53 | * we should generally pick a slightly larger size than what the | ||
54 | * strict math would suggest. | ||
55 | * | ||
56 | * @param entry_count expected number of entries in the Bloom filter | ||
57 | * @return must be a power of two and smaller or equal to 2^15. | ||
58 | */ | ||
59 | static size_t | ||
60 | compute_bloomfilter_size (unsigned int entry_count) | ||
61 | { | ||
62 | size_t size; | ||
63 | unsigned int ideal = (entry_count * BLOOMFILTER_K) / 4; | ||
64 | uint16_t max = 1 << 15; | ||
65 | |||
66 | if (entry_count > max) | ||
67 | return max; | ||
68 | size = 8; | ||
69 | while ((size < max) && (size < ideal)) | ||
70 | size *= 2; | ||
71 | if (size > max) | ||
72 | return max; | ||
73 | return size; | ||
74 | } | ||
75 | |||
76 | |||
77 | /** | ||
78 | * Create a new block group. | 47 | * Create a new block group. |
79 | * | 48 | * |
80 | * @param ctx block context in which the block group is created | 49 | * @param ctx block context in which the block group is created |
@@ -100,7 +69,8 @@ block_plugin_gns_create_group (void *cls, | |||
100 | guard = va_arg (va, const char *); | 69 | guard = va_arg (va, const char *); |
101 | if (0 == strcmp (guard, | 70 | if (0 == strcmp (guard, |
102 | "seen-set-size")) | 71 | "seen-set-size")) |
103 | bf_size = compute_bloomfilter_size (va_arg (va, unsigned int)); | 72 | bf_size = GNUNET_BLOCK_GROUP_compute_bloomfilter_size (va_arg (va, unsigned int), |
73 | BLOOMFILTER_K); | ||
104 | else if (0 == strcmp (guard, | 74 | else if (0 == strcmp (guard, |
105 | "filter-size")) | 75 | "filter-size")) |
106 | bf_size = va_arg (va, unsigned int); | 76 | bf_size = va_arg (va, unsigned int); |
diff --git a/src/include/gnunet_block_group_lib.h b/src/include/gnunet_block_group_lib.h index a1ea807f6..3a3dfb2e2 100644 --- a/src/include/gnunet_block_group_lib.h +++ b/src/include/gnunet_block_group_lib.h | |||
@@ -44,6 +44,24 @@ extern "C" | |||
44 | 44 | ||
45 | 45 | ||
46 | /** | 46 | /** |
47 | * How many bytes should a bloomfilter be if we have already seen | ||
48 | * entry_count responses? Sized so that do not have to | ||
49 | * re-size the filter too often (to keep it cheap). | ||
50 | * | ||
51 | * Since other peers will also add entries but not resize the filter, | ||
52 | * we should generally pick a slightly larger size than what the | ||
53 | * strict math would suggest. | ||
54 | * | ||
55 | * @param entry_count expected number of entries in the Bloom filter | ||
56 | * @param k number of bits set per entry | ||
57 | * @return must be a power of two and smaller or equal to 2^15. | ||
58 | */ | ||
59 | size_t | ||
60 | GNUNET_BLOCK_GROUP_compute_bloomfilter_size (unsigned int entry_count, | ||
61 | unsigned int k); | ||
62 | |||
63 | |||
64 | /** | ||
47 | * Create a new block group that filters duplicates using a Bloom filter. | 65 | * Create a new block group that filters duplicates using a Bloom filter. |
48 | * | 66 | * |
49 | * @param ctx block context in which the block group is created | 67 | * @param ctx block context in which the block group is created |
diff --git a/src/regex/plugin_block_regex.c b/src/regex/plugin_block_regex.c index 19335e815..a345dfedb 100644 --- a/src/regex/plugin_block_regex.c +++ b/src/regex/plugin_block_regex.c | |||
@@ -31,7 +31,6 @@ | |||
31 | #include "gnunet_signatures.h" | 31 | #include "gnunet_signatures.h" |
32 | 32 | ||
33 | 33 | ||
34 | |||
35 | /** | 34 | /** |
36 | * Number of bits we set per entry in the bloomfilter. | 35 | * Number of bits we set per entry in the bloomfilter. |
37 | * Do not change! | 36 | * Do not change! |
@@ -46,37 +45,6 @@ | |||
46 | 45 | ||
47 | 46 | ||
48 | /** | 47 | /** |
49 | * How many bytes should a bloomfilter be if we have already seen | ||
50 | * entry_count responses? Note that #GNUNET_CONSTANTS_BLOOMFILTER_K | ||
51 | * gives us the number of bits set per entry. Furthermore, we should | ||
52 | * not re-size the filter too often (to keep it cheap). | ||
53 | * | ||
54 | * Since other peers will also add entries but not resize the filter, | ||
55 | * we should generally pick a slightly larger size than what the | ||
56 | * strict math would suggest. | ||
57 | * | ||
58 | * @param entry_count expected number of entries in the Bloom filter | ||
59 | * @return must be a power of two and smaller or equal to 2^15. | ||
60 | */ | ||
61 | static size_t | ||
62 | compute_bloomfilter_size (unsigned int entry_count) | ||
63 | { | ||
64 | size_t size; | ||
65 | unsigned int ideal = (entry_count * BLOOMFILTER_K) / 4; | ||
66 | uint16_t max = 1 << 15; | ||
67 | |||
68 | if (entry_count > max) | ||
69 | return max; | ||
70 | size = 8; | ||
71 | while ((size < max) && (size < ideal)) | ||
72 | size *= 2; | ||
73 | if (size > max) | ||
74 | return max; | ||
75 | return size; | ||
76 | } | ||
77 | |||
78 | |||
79 | /** | ||
80 | * Create a new block group. | 48 | * Create a new block group. |
81 | * | 49 | * |
82 | * @param ctx block context in which the block group is created | 50 | * @param ctx block context in which the block group is created |
@@ -102,7 +70,8 @@ block_plugin_regex_create_group (void *cls, | |||
102 | guard = va_arg (va, const char *); | 70 | guard = va_arg (va, const char *); |
103 | if (0 == strcmp (guard, | 71 | if (0 == strcmp (guard, |
104 | "seen-set-size")) | 72 | "seen-set-size")) |
105 | bf_size = compute_bloomfilter_size (va_arg (va, unsigned int)); | 73 | bf_size = GNUNET_BLOCK_GROUP_compute_bloomfilter_size (va_arg (va, unsigned int), |
74 | BLOOMFILTER_K); | ||
106 | else if (0 == strcmp (guard, | 75 | else if (0 == strcmp (guard, |
107 | "filter-size")) | 76 | "filter-size")) |
108 | bf_size = va_arg (va, unsigned int); | 77 | bf_size = va_arg (va, unsigned int); |