diff options
-rw-r--r-- | src/block/block.c | 45 | ||||
-rw-r--r-- | src/fs/fs.h | 6 | ||||
-rw-r--r-- | src/fs/gnunet-service-fs_pr.c | 84 | ||||
-rw-r--r-- | src/include/gnunet_constants.h | 7 | ||||
-rw-r--r-- | src/include/gnunet_dht_service.h | 4 | ||||
-rw-r--r-- | src/include/gnunet_protocols.h | 41 |
6 files changed, 107 insertions, 80 deletions
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 @@ | |||
25 | */ | 25 | */ |
26 | #include "platform.h" | 26 | #include "platform.h" |
27 | #include "gnunet_util_lib.h" | 27 | #include "gnunet_util_lib.h" |
28 | #include "gnunet_constants.h" | ||
28 | #include "gnunet_signatures.h" | 29 | #include "gnunet_signatures.h" |
29 | #include "gnunet_block_lib.h" | 30 | #include "gnunet_block_lib.h" |
30 | #include "gnunet_block_plugin.h" | 31 | #include "gnunet_block_plugin.h" |
@@ -249,6 +250,35 @@ GNUNET_BLOCK_get_key (struct GNUNET_BLOCK_Context *ctx, | |||
249 | } | 250 | } |
250 | 251 | ||
251 | 252 | ||
253 | /** | ||
254 | * How many bytes should a bloomfilter be if we have already seen | ||
255 | * entry_count responses? Note that GNUNET_CONSTANTS_BLOOMFILTER_K gives us the number | ||
256 | * of bits set per entry. Furthermore, we should not re-size the | ||
257 | * filter too often (to keep it cheap). | ||
258 | * | ||
259 | * Since other peers will also add entries but not resize the filter, | ||
260 | * we should generally pick a slightly larger size than what the | ||
261 | * strict math would suggest. | ||
262 | * | ||
263 | * @return must be a power of two and smaller or equal to 2^15. | ||
264 | */ | ||
265 | static size_t | ||
266 | compute_bloomfilter_size (unsigned int entry_count) | ||
267 | { | ||
268 | size_t size; | ||
269 | unsigned int ideal = (entry_count * GNUNET_CONSTANTS_BLOOMFILTER_K) / 4; | ||
270 | uint16_t max = 1 << 15; | ||
271 | |||
272 | if (entry_count > max) | ||
273 | return max; | ||
274 | size = 8; | ||
275 | while ((size < max) && (size < ideal)) | ||
276 | size *= 2; | ||
277 | if (size > max) | ||
278 | return max; | ||
279 | return size; | ||
280 | } | ||
281 | |||
252 | 282 | ||
253 | /** | 283 | /** |
254 | * Construct a bloom filter that would filter out the given | 284 | * Construct a bloom filter that would filter out the given |
@@ -265,8 +295,19 @@ GNUNET_BLOCK_construct_bloomfilter (int32_t bf_mutator, | |||
265 | const GNUNET_HashCode *seen_results, | 295 | const GNUNET_HashCode *seen_results, |
266 | unsigned int seen_results_count) | 296 | unsigned int seen_results_count) |
267 | { | 297 | { |
268 | GNUNET_break (0); | 298 | struct GNUNET_CONTAINER_BloomFilter *bf; |
269 | return NULL; | 299 | GNUNET_HashCode mhash; |
300 | unsigned int i; | ||
301 | size_t nsize; | ||
302 | |||
303 | nsize = compute_bloomfilter_size (seen_results_count); | ||
304 | bf = GNUNET_CONTAINER_bloomfilter_init (NULL, nsize, GNUNET_CONSTANTS_BLOOMFILTER_K); | ||
305 | for (i = 0; i < seen_results_count; i++) | ||
306 | { | ||
307 | GNUNET_BLOCK_mingle_hash (&seen_results[i], bf_mutator, &mhash); | ||
308 | GNUNET_CONTAINER_bloomfilter_add (bf, &mhash); | ||
309 | } | ||
310 | return bf; | ||
270 | } | 311 | } |
271 | 312 | ||
272 | 313 | ||
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 | |||
@@ -132,12 +132,6 @@ | |||
132 | #define HASHING_BLOCKSIZE (1024 * 128) | 132 | #define HASHING_BLOCKSIZE (1024 * 128) |
133 | 133 | ||
134 | /** | 134 | /** |
135 | * Number of bits we set per entry in the bloomfilter. | ||
136 | * Do not change! | ||
137 | */ | ||
138 | #define BLOOMFILTER_K GNUNET_DHT_GET_BLOOMFILTER_K | ||
139 | |||
140 | /** | ||
141 | * Number of availability trials we perform per search result. | 135 | * Number of availability trials we perform per search result. |
142 | */ | 136 | */ |
143 | #define AVAILABILITY_TRIALS_MAX 8 | 137 | #define AVAILABILITY_TRIALS_MAX 8 |
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; | |||
188 | static unsigned long long max_pending_requests = (32 * 1024); | 188 | static unsigned long long max_pending_requests = (32 * 1024); |
189 | 189 | ||
190 | 190 | ||
191 | /** | ||
192 | * How many bytes should a bloomfilter be if we have already seen | ||
193 | * entry_count responses? Note that BLOOMFILTER_K gives us the number | ||
194 | * of bits set per entry. Furthermore, we should not re-size the | ||
195 | * filter too often (to keep it cheap). | ||
196 | * | ||
197 | * Since other peers will also add entries but not resize the filter, | ||
198 | * we should generally pick a slightly larger size than what the | ||
199 | * strict math would suggest. | ||
200 | * | ||
201 | * @return must be a power of two and smaller or equal to 2^15. | ||
202 | */ | ||
203 | static size_t | ||
204 | compute_bloomfilter_size (unsigned int entry_count) | ||
205 | { | ||
206 | size_t size; | ||
207 | unsigned int ideal = (entry_count * BLOOMFILTER_K) / 4; | ||
208 | uint16_t max = 1 << 15; | ||
209 | |||
210 | if (entry_count > max) | ||
211 | return max; | ||
212 | size = 8; | ||
213 | while ((size < max) && (size < ideal)) | ||
214 | size *= 2; | ||
215 | if (size > max) | ||
216 | return max; | ||
217 | return size; | ||
218 | } | ||
219 | |||
220 | 191 | ||
221 | /** | 192 | /** |
222 | * Recalculate our bloom filter for filtering replies. This function | 193 | * Recalculate our bloom filter for filtering replies. This function |
@@ -226,30 +197,17 @@ compute_bloomfilter_size (unsigned int entry_count) | |||
226 | * initiator (in which case we may resize to larger than mimimum size). | 197 | * initiator (in which case we may resize to larger than mimimum size). |
227 | * | 198 | * |
228 | * @param pr request for which the BF is to be recomputed | 199 | * @param pr request for which the BF is to be recomputed |
229 | * @return GNUNET_YES if a refresh actually happened | ||
230 | */ | 200 | */ |
231 | static int | 201 | static void |
232 | refresh_bloomfilter (struct GSF_PendingRequest *pr) | 202 | refresh_bloomfilter (struct GSF_PendingRequest *pr) |
233 | { | 203 | { |
234 | unsigned int i; | ||
235 | size_t nsize; | ||
236 | GNUNET_HashCode mhash; | ||
237 | |||
238 | nsize = compute_bloomfilter_size (pr->replies_seen_count); | ||
239 | if ((pr->bf != NULL) && | ||
240 | (nsize == GNUNET_CONTAINER_bloomfilter_get_size (pr->bf))) | ||
241 | return GNUNET_NO; /* size not changed */ | ||
242 | if (pr->bf != NULL) | 204 | if (pr->bf != NULL) |
243 | GNUNET_CONTAINER_bloomfilter_free (pr->bf); | 205 | GNUNET_CONTAINER_bloomfilter_free (pr->bf); |
244 | pr->mingle = | 206 | pr->mingle = |
245 | GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, UINT32_MAX); | 207 | GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, UINT32_MAX); |
246 | pr->bf = GNUNET_CONTAINER_bloomfilter_init (NULL, nsize, BLOOMFILTER_K); | 208 | pr->bf = GNUNET_BLOCK_construct_bloomfilter (pr->mingle, |
247 | for (i = 0; i < pr->replies_seen_count; i++) | 209 | pr->replies_seen, |
248 | { | 210 | pr->replies_seen_count); |
249 | GNUNET_BLOCK_mingle_hash (&pr->replies_seen[i], pr->mingle, &mhash); | ||
250 | GNUNET_CONTAINER_bloomfilter_add (pr->bf, &mhash); | ||
251 | } | ||
252 | return GNUNET_YES; | ||
253 | } | 211 | } |
254 | 212 | ||
255 | 213 | ||
@@ -346,13 +304,13 @@ GSF_pending_request_create_ (enum GSF_PendingRequestOptions options, | |||
346 | if (NULL != bf_data) | 304 | if (NULL != bf_data) |
347 | { | 305 | { |
348 | pr->bf = | 306 | pr->bf = |
349 | GNUNET_CONTAINER_bloomfilter_init (bf_data, bf_size, BLOOMFILTER_K); | 307 | GNUNET_CONTAINER_bloomfilter_init (bf_data, bf_size, GNUNET_CONSTANTS_BLOOMFILTER_K); |
350 | pr->mingle = mingle; | 308 | pr->mingle = mingle; |
351 | } | 309 | } |
352 | else if ((replies_seen_count > 0) && | 310 | else if ((replies_seen_count > 0) && |
353 | (0 != (options & GSF_PRO_BLOOMFILTER_FULL_REFRESH))) | 311 | (0 != (options & GSF_PRO_BLOOMFILTER_FULL_REFRESH))) |
354 | { | 312 | { |
355 | GNUNET_assert (GNUNET_YES == refresh_bloomfilter (pr)); | 313 | refresh_bloomfilter (pr); |
356 | } | 314 | } |
357 | GNUNET_CONTAINER_multihashmap_put (pr_map, query, pr, | 315 | GNUNET_CONTAINER_multihashmap_put (pr_map, query, pr, |
358 | GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE); | 316 | GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE); |
@@ -449,15 +407,7 @@ GSF_pending_request_update_ (struct GSF_PendingRequest *pr, | |||
449 | memcpy (&pr->replies_seen[pr->replies_seen_count], replies_seen, | 407 | memcpy (&pr->replies_seen[pr->replies_seen_count], replies_seen, |
450 | sizeof (GNUNET_HashCode) * replies_seen_count); | 408 | sizeof (GNUNET_HashCode) * replies_seen_count); |
451 | pr->replies_seen_count += replies_seen_count; | 409 | pr->replies_seen_count += replies_seen_count; |
452 | if (GNUNET_NO == refresh_bloomfilter (pr)) | 410 | refresh_bloomfilter (pr); |
453 | { | ||
454 | /* bf not recalculated, simply extend it with new bits */ | ||
455 | for (i = 0; i < replies_seen_count; i++) | ||
456 | { | ||
457 | GNUNET_BLOCK_mingle_hash (&replies_seen[i], pr->mingle, &mhash); | ||
458 | GNUNET_CONTAINER_bloomfilter_add (pr->bf, &mhash); | ||
459 | } | ||
460 | } | ||
461 | } | 411 | } |
462 | else | 412 | else |
463 | { | 413 | { |
@@ -468,15 +418,17 @@ GSF_pending_request_update_ (struct GSF_PendingRequest *pr, | |||
468 | pr->mingle = | 418 | pr->mingle = |
469 | GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, UINT32_MAX); | 419 | GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, UINT32_MAX); |
470 | pr->bf = | 420 | pr->bf = |
471 | GNUNET_CONTAINER_bloomfilter_init (NULL, | 421 | GNUNET_BLOCK_construct_bloomfilter (pr->mingle, |
472 | compute_bloomfilter_size | 422 | replies_seen, |
473 | (replies_seen_count), | 423 | replies_seen_count); |
474 | BLOOMFILTER_K); | 424 | } |
475 | } | 425 | else |
476 | for (i = 0; i < pr->replies_seen_count; i++) | ||
477 | { | 426 | { |
478 | GNUNET_BLOCK_mingle_hash (&replies_seen[i], pr->mingle, &mhash); | 427 | for (i = 0; i < pr->replies_seen_count; i++) |
479 | GNUNET_CONTAINER_bloomfilter_add (pr->bf, &mhash); | 428 | { |
429 | GNUNET_BLOCK_mingle_hash (&replies_seen[i], pr->mingle, &mhash); | ||
430 | GNUNET_CONTAINER_bloomfilter_add (pr->bf, &mhash); | ||
431 | } | ||
480 | } | 432 | } |
481 | } | 433 | } |
482 | } | 434 | } |
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" | |||
128 | #define GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE (63 * 1024) | 128 | #define GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE (63 * 1024) |
129 | 129 | ||
130 | 130 | ||
131 | /** | ||
132 | * K-value that must be used for the bloom filters in 'GET' | ||
133 | * queries. | ||
134 | */ | ||
135 | #define GNUNET_CONSTANTS_BLOOMFILTER_K 16 | ||
136 | |||
137 | |||
131 | 138 | ||
132 | #if 0 /* keep Emacsens' auto-indent happy */ | 139 | #if 0 /* keep Emacsens' auto-indent happy */ |
133 | { | 140 | { |
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" | |||
46 | #define GNUNET_DHT_DEFAULT_REPUBLISH_FREQUENCY GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_MINUTES, 60) | 46 | #define GNUNET_DHT_DEFAULT_REPUBLISH_FREQUENCY GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_MINUTES, 60) |
47 | 47 | ||
48 | /** | 48 | /** |
49 | * K-value that must be used for the bloom filter 'GET' | 49 | * K-value that must be used for the bloom filters in 'GET' |
50 | * queries. | 50 | * queries. |
51 | */ | 51 | */ |
52 | #define GNUNET_DHT_GET_BLOOMFILTER_K 16 | 52 | #define GNUNET_DHT_GET_BLOOMFILTER_K GNUNET_CONSTANTS_BLOOMFILTER_K |
53 | 53 | ||
54 | /** | 54 | /** |
55 | * Non-intelligent default DHT GET replication. | 55 | * 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 | |||
@@ -625,16 +625,51 @@ extern "C" | |||
625 | ******************************************************************************/ | 625 | ******************************************************************************/ |
626 | 626 | ||
627 | /** | 627 | /** |
628 | * Client wants to store item in DHT. | ||
629 | */ | ||
630 | #define GNUNET_MESSAGE_TYPE_DHT_CLIENT_PUT 142 | ||
631 | |||
632 | /** | ||
633 | * Client wants to lookup item in DHT. | ||
634 | */ | ||
635 | #define GNUNET_MESSAGE_TYPE_DHT_CLIENT_GET 143 | ||
636 | |||
637 | /** | ||
638 | * Client wants to stop search in DHT. | ||
639 | */ | ||
640 | #define GNUNET_MESSAGE_TYPE_DHT_CLIENT_GET_STOP 144 | ||
641 | |||
642 | /** | ||
643 | * Service returns result to client. | ||
644 | */ | ||
645 | #define GNUNET_MESSAGE_TYPE_DHT_CLIENT_RESULT 145 | ||
646 | |||
647 | /** | ||
648 | * Peer is storing data in DHT. | ||
649 | */ | ||
650 | #define GNUNET_MESSAGE_TYPE_DHT_P2P_PUT 146 | ||
651 | |||
652 | /** | ||
653 | * Peer tries to find data in DHT. | ||
654 | */ | ||
655 | #define GNUNET_MESSAGE_TYPE_DHT_P2P_GET 147 | ||
656 | |||
657 | /** | ||
658 | * Data is returned to peer from DHT. | ||
659 | */ | ||
660 | #define GNUNET_MESSAGE_TYPE_DHT_P2P_RESULT 148 | ||
661 | |||
662 | // LEGACY types follow (pre3)...... | ||
663 | |||
664 | /** | ||
628 | * Local DHT route request type | 665 | * Local DHT route request type |
629 | */ | 666 | */ |
630 | #define GNUNET_MESSAGE_TYPE_DHT_LOCAL_ROUTE 142 | 667 | #define GNUNET_MESSAGE_TYPE_DHT_LOCAL_ROUTE 142 |
631 | #define GNUNET_MESSAGE_TYPE_DHT_CLIENT_GET 142 | ||
632 | 668 | ||
633 | /** | 669 | /** |
634 | * Local generic DHT route result type | 670 | * Local generic DHT route result type |
635 | */ | 671 | */ |
636 | #define GNUNET_MESSAGE_TYPE_DHT_LOCAL_ROUTE_RESULT 143 | 672 | #define GNUNET_MESSAGE_TYPE_DHT_LOCAL_ROUTE_RESULT 143 |
637 | #define GNUNET_MESSAGE_TYPE_DHT_CLIENT_RESULT 142 | ||
638 | 673 | ||
639 | /** | 674 | /** |
640 | * P2P DHT route request type | 675 | * P2P DHT route request type |
@@ -650,14 +685,12 @@ extern "C" | |||
650 | * Local generic DHT message stop type | 685 | * Local generic DHT message stop type |
651 | */ | 686 | */ |
652 | #define GNUNET_MESSAGE_TYPE_DHT_LOCAL_ROUTE_STOP 146 | 687 | #define GNUNET_MESSAGE_TYPE_DHT_LOCAL_ROUTE_STOP 146 |
653 | #define GNUNET_MESSAGE_TYPE_DHT_CLIENT_GET_STOP 146 | ||
654 | 688 | ||
655 | /** | 689 | /** |
656 | * Local and P2P DHT PUT message | 690 | * Local and P2P DHT PUT message |
657 | * (encapsulated in DHT_ROUTE message) | 691 | * (encapsulated in DHT_ROUTE message) |
658 | */ | 692 | */ |
659 | #define GNUNET_MESSAGE_TYPE_DHT_PUT 147 | 693 | #define GNUNET_MESSAGE_TYPE_DHT_PUT 147 |
660 | #define GNUNET_MESSAGE_TYPE_DHT_CLIENT_PUT 147 | ||
661 | 694 | ||
662 | /** | 695 | /** |
663 | * Local and P2P DHT GET message | 696 | * Local and P2P DHT GET message |