aboutsummaryrefslogtreecommitdiff
path: root/src/util/container_bloomfilter.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/util/container_bloomfilter.c')
-rw-r--r--src/util/container_bloomfilter.c552
1 files changed, 275 insertions, 277 deletions
diff --git a/src/util/container_bloomfilter.c b/src/util/container_bloomfilter.c
index a4033defe..1bc559ba3 100644
--- a/src/util/container_bloomfilter.c
+++ b/src/util/container_bloomfilter.c
@@ -11,12 +11,12 @@
11 WITHOUT ANY WARRANTY; without even the implied warranty of 11 WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 Affero General Public License for more details. 13 Affero General Public License for more details.
14 14
15 You should have received a copy of the GNU Affero General Public License 15 You should have received a copy of the GNU Affero General Public License
16 along with this program. If not, see <http://www.gnu.org/licenses/>. 16 along with this program. If not, see <http://www.gnu.org/licenses/>.
17 17
18 SPDX-License-Identifier: AGPL3.0-or-later 18 SPDX-License-Identifier: AGPL3.0-or-later
19*/ 19 */
20/** 20/**
21 * @file util/container_bloomfilter.c 21 * @file util/container_bloomfilter.c
22 * @brief data structure used to reduce disk accesses. 22 * @brief data structure used to reduce disk accesses.
@@ -43,20 +43,18 @@
43#include "gnunet_util_lib.h" 43#include "gnunet_util_lib.h"
44 44
45#define LOG(kind, ...) \ 45#define LOG(kind, ...) \
46 GNUNET_log_from (kind, "util-container-bloomfilter", __VA_ARGS__) 46 GNUNET_log_from(kind, "util-container-bloomfilter", __VA_ARGS__)
47 47
48#define LOG_STRERROR(kind, syscall) \ 48#define LOG_STRERROR(kind, syscall) \
49 GNUNET_log_from_strerror (kind, "util-container-bloomfilter", syscall) 49 GNUNET_log_from_strerror(kind, "util-container-bloomfilter", syscall)
50 50
51#define LOG_STRERROR_FILE(kind, syscall, filename) \ 51#define LOG_STRERROR_FILE(kind, syscall, filename) \
52 GNUNET_log_from_strerror_file (kind, \ 52 GNUNET_log_from_strerror_file(kind, \
53 "util-container-bloomfilter", \ 53 "util-container-bloomfilter", \
54 syscall, \ 54 syscall, \
55 filename) 55 filename)
56
57struct GNUNET_CONTAINER_BloomFilter
58{
59 56
57struct GNUNET_CONTAINER_BloomFilter {
60 /** 58 /**
61 * The actual bloomfilter bit array 59 * The actual bloomfilter bit array
62 */ 60 */
@@ -91,7 +89,7 @@ struct GNUNET_CONTAINER_BloomFilter
91 * @return addresses set per element in the bf 89 * @return addresses set per element in the bf
92 */ 90 */
93size_t 91size_t
94GNUNET_CONTAINER_bloomfilter_get_element_addresses ( 92GNUNET_CONTAINER_bloomfilter_get_element_addresses(
95 const struct GNUNET_CONTAINER_BloomFilter *bf) 93 const struct GNUNET_CONTAINER_BloomFilter *bf)
96{ 94{
97 if (bf == NULL) 95 if (bf == NULL)
@@ -107,7 +105,7 @@ GNUNET_CONTAINER_bloomfilter_get_element_addresses (
107 * @return number of bytes used for the data of the bloom filter 105 * @return number of bytes used for the data of the bloom filter
108 */ 106 */
109size_t 107size_t
110GNUNET_CONTAINER_bloomfilter_get_size ( 108GNUNET_CONTAINER_bloomfilter_get_size(
111 const struct GNUNET_CONTAINER_BloomFilter *bf) 109 const struct GNUNET_CONTAINER_BloomFilter *bf)
112{ 110{
113 if (bf == NULL) 111 if (bf == NULL)
@@ -123,12 +121,12 @@ GNUNET_CONTAINER_bloomfilter_get_size (
123 * @return copy of the bf 121 * @return copy of the bf
124 */ 122 */
125struct GNUNET_CONTAINER_BloomFilter * 123struct GNUNET_CONTAINER_BloomFilter *
126GNUNET_CONTAINER_bloomfilter_copy ( 124GNUNET_CONTAINER_bloomfilter_copy(
127 const struct GNUNET_CONTAINER_BloomFilter *bf) 125 const struct GNUNET_CONTAINER_BloomFilter *bf)
128{ 126{
129 return GNUNET_CONTAINER_bloomfilter_init (bf->bitArray, 127 return GNUNET_CONTAINER_bloomfilter_init(bf->bitArray,
130 bf->bitArraySize, 128 bf->bitArraySize,
131 bf->addressesPerElement); 129 bf->addressesPerElement);
132} 130}
133 131
134 132
@@ -140,7 +138,7 @@ GNUNET_CONTAINER_bloomfilter_copy (
140 * @param bitIdx which bit to set 138 * @param bitIdx which bit to set
141 */ 139 */
142static void 140static void
143setBit (char *bitArray, unsigned int bitIdx) 141setBit(char *bitArray, unsigned int bitIdx)
144{ 142{
145 size_t arraySlot; 143 size_t arraySlot;
146 unsigned int targetBit; 144 unsigned int targetBit;
@@ -158,7 +156,7 @@ setBit (char *bitArray, unsigned int bitIdx)
158 * @param bitIdx which bit to unset 156 * @param bitIdx which bit to unset
159 */ 157 */
160static void 158static void
161clearBit (char *bitArray, unsigned int bitIdx) 159clearBit(char *bitArray, unsigned int bitIdx)
162{ 160{
163 size_t slot; 161 size_t slot;
164 unsigned int targetBit; 162 unsigned int targetBit;
@@ -176,7 +174,7 @@ clearBit (char *bitArray, unsigned int bitIdx)
176 * @return GNUNET_YES if the bit is set, GNUNET_NO if not. 174 * @return GNUNET_YES if the bit is set, GNUNET_NO if not.
177 */ 175 */
178static int 176static int
179testBit (char *bitArray, unsigned int bitIdx) 177testBit(char *bitArray, unsigned int bitIdx)
180{ 178{
181 size_t slot; 179 size_t slot;
182 unsigned int targetBit; 180 unsigned int targetBit;
@@ -199,9 +197,9 @@ testBit (char *bitArray, unsigned int bitIdx)
199 * @param fh A file to keep the 4 bit address usage counters in 197 * @param fh A file to keep the 4 bit address usage counters in
200 */ 198 */
201static void 199static void
202incrementBit (char *bitArray, 200incrementBit(char *bitArray,
203 unsigned int bitIdx, 201 unsigned int bitIdx,
204 const struct GNUNET_DISK_FileHandle *fh) 202 const struct GNUNET_DISK_FileHandle *fh)
205{ 203{
206 off_t fileSlot; 204 off_t fileSlot;
207 unsigned char value; 205 unsigned char value;
@@ -209,34 +207,34 @@ incrementBit (char *bitArray,
209 unsigned int low; 207 unsigned int low;
210 unsigned int targetLoc; 208 unsigned int targetLoc;
211 209
212 setBit (bitArray, bitIdx); 210 setBit(bitArray, bitIdx);
213 if (GNUNET_DISK_handle_invalid (fh)) 211 if (GNUNET_DISK_handle_invalid(fh))
214 return; 212 return;
215 /* Update the counter file on disk */ 213 /* Update the counter file on disk */
216 fileSlot = bitIdx / 2; 214 fileSlot = bitIdx / 2;
217 targetLoc = bitIdx % 2; 215 targetLoc = bitIdx % 2;
218 216
219 GNUNET_assert (fileSlot == 217 GNUNET_assert(fileSlot ==
220 GNUNET_DISK_file_seek (fh, fileSlot, GNUNET_DISK_SEEK_SET)); 218 GNUNET_DISK_file_seek(fh, fileSlot, GNUNET_DISK_SEEK_SET));
221 if (1 != GNUNET_DISK_file_read (fh, &value, 1)) 219 if (1 != GNUNET_DISK_file_read(fh, &value, 1))
222 value = 0; 220 value = 0;
223 low = value & 0xF; 221 low = value & 0xF;
224 high = (value & (~0xF)) >> 4; 222 high = (value & (~0xF)) >> 4;
225 223
226 if (targetLoc == 0) 224 if (targetLoc == 0)
227 { 225 {
228 if (low < 0xF) 226 if (low < 0xF)
229 low++; 227 low++;
230 } 228 }
231 else 229 else
232 { 230 {
233 if (high < 0xF) 231 if (high < 0xF)
234 high++; 232 high++;
235 } 233 }
236 value = ((high << 4) | low); 234 value = ((high << 4) | low);
237 GNUNET_assert (fileSlot == 235 GNUNET_assert(fileSlot ==
238 GNUNET_DISK_file_seek (fh, fileSlot, GNUNET_DISK_SEEK_SET)); 236 GNUNET_DISK_file_seek(fh, fileSlot, GNUNET_DISK_SEEK_SET));
239 GNUNET_assert (1 == GNUNET_DISK_file_write (fh, &value, 1)); 237 GNUNET_assert(1 == GNUNET_DISK_file_write(fh, &value, 1));
240} 238}
241 239
242/** 240/**
@@ -248,9 +246,9 @@ incrementBit (char *bitArray,
248 * @param fh A file to keep the 4bit address usage counters in 246 * @param fh A file to keep the 4bit address usage counters in
249 */ 247 */
250static void 248static void
251decrementBit (char *bitArray, 249decrementBit(char *bitArray,
252 unsigned int bitIdx, 250 unsigned int bitIdx,
253 const struct GNUNET_DISK_FileHandle *fh) 251 const struct GNUNET_DISK_FileHandle *fh)
254{ 252{
255 off_t fileslot; 253 off_t fileslot;
256 unsigned char value; 254 unsigned char value;
@@ -258,49 +256,49 @@ decrementBit (char *bitArray,
258 unsigned int low; 256 unsigned int low;
259 unsigned int targetLoc; 257 unsigned int targetLoc;
260 258
261 if (GNUNET_DISK_handle_invalid (fh)) 259 if (GNUNET_DISK_handle_invalid(fh))
262 return; /* cannot decrement! */ 260 return; /* cannot decrement! */
263 /* Each char slot in the counter file holds two 4 bit counters */ 261 /* Each char slot in the counter file holds two 4 bit counters */
264 fileslot = bitIdx / 2; 262 fileslot = bitIdx / 2;
265 targetLoc = bitIdx % 2; 263 targetLoc = bitIdx % 2;
266 if (GNUNET_SYSERR == 264 if (GNUNET_SYSERR ==
267 GNUNET_DISK_file_seek (fh, fileslot, GNUNET_DISK_SEEK_SET)) 265 GNUNET_DISK_file_seek(fh, fileslot, GNUNET_DISK_SEEK_SET))
268 { 266 {
269 GNUNET_log_strerror (GNUNET_ERROR_TYPE_ERROR, "seek"); 267 GNUNET_log_strerror(GNUNET_ERROR_TYPE_ERROR, "seek");
270 return; 268 return;
271 } 269 }
272 if (1 != GNUNET_DISK_file_read (fh, &value, 1)) 270 if (1 != GNUNET_DISK_file_read(fh, &value, 1))
273 value = 0; 271 value = 0;
274 low = value & 0xF; 272 low = value & 0xF;
275 high = (value & 0xF0) >> 4; 273 high = (value & 0xF0) >> 4;
276 274
277 /* decrement, but once we have reached the max, never go back! */ 275 /* decrement, but once we have reached the max, never go back! */
278 if (targetLoc == 0) 276 if (targetLoc == 0)
279 {
280 if ((low > 0) && (low < 0xF))
281 low--;
282 if (low == 0)
283 { 277 {
284 clearBit (bitArray, bitIdx); 278 if ((low > 0) && (low < 0xF))
279 low--;
280 if (low == 0)
281 {
282 clearBit(bitArray, bitIdx);
283 }
285 } 284 }
286 }
287 else 285 else
288 {
289 if ((high > 0) && (high < 0xF))
290 high--;
291 if (high == 0)
292 { 286 {
293 clearBit (bitArray, bitIdx); 287 if ((high > 0) && (high < 0xF))
288 high--;
289 if (high == 0)
290 {
291 clearBit(bitArray, bitIdx);
292 }
294 } 293 }
295 }
296 value = ((high << 4) | low); 294 value = ((high << 4) | low);
297 if (GNUNET_SYSERR == 295 if (GNUNET_SYSERR ==
298 GNUNET_DISK_file_seek (fh, fileslot, GNUNET_DISK_SEEK_SET)) 296 GNUNET_DISK_file_seek(fh, fileslot, GNUNET_DISK_SEEK_SET))
299 { 297 {
300 GNUNET_log_strerror (GNUNET_ERROR_TYPE_ERROR, "seek"); 298 GNUNET_log_strerror(GNUNET_ERROR_TYPE_ERROR, "seek");
301 return; 299 return;
302 } 300 }
303 GNUNET_assert (1 == GNUNET_DISK_file_write (fh, &value, 1)); 301 GNUNET_assert(1 == GNUNET_DISK_file_write(fh, &value, 1));
304} 302}
305 303
306#define BUFFSIZE 65536 304#define BUFFSIZE 65536
@@ -313,33 +311,33 @@ decrementBit (char *bitArray,
313 * @return GNUNET_OK if created ok, GNUNET_SYSERR otherwise 311 * @return GNUNET_OK if created ok, GNUNET_SYSERR otherwise
314 */ 312 */
315static int 313static int
316make_empty_file (const struct GNUNET_DISK_FileHandle *fh, size_t size) 314make_empty_file(const struct GNUNET_DISK_FileHandle *fh, size_t size)
317{ 315{
318 char buffer[BUFFSIZE]; 316 char buffer[BUFFSIZE];
319 size_t bytesleft = size; 317 size_t bytesleft = size;
320 int res = 0; 318 int res = 0;
321 319
322 if (GNUNET_DISK_handle_invalid (fh)) 320 if (GNUNET_DISK_handle_invalid(fh))
323 return GNUNET_SYSERR; 321 return GNUNET_SYSERR;
324 memset (buffer, 0, sizeof (buffer)); 322 memset(buffer, 0, sizeof(buffer));
325 GNUNET_DISK_file_seek (fh, 0, GNUNET_DISK_SEEK_SET); 323 GNUNET_DISK_file_seek(fh, 0, GNUNET_DISK_SEEK_SET);
326 while (bytesleft > 0) 324 while (bytesleft > 0)
327 {
328 if (bytesleft > sizeof (buffer))
329 {
330 res = GNUNET_DISK_file_write (fh, buffer, sizeof (buffer));
331 if (res >= 0)
332 bytesleft -= res;
333 }
334 else
335 { 325 {
336 res = GNUNET_DISK_file_write (fh, buffer, bytesleft); 326 if (bytesleft > sizeof(buffer))
337 if (res >= 0) 327 {
338 bytesleft -= res; 328 res = GNUNET_DISK_file_write(fh, buffer, sizeof(buffer));
329 if (res >= 0)
330 bytesleft -= res;
331 }
332 else
333 {
334 res = GNUNET_DISK_file_write(fh, buffer, bytesleft);
335 if (res >= 0)
336 bytesleft -= res;
337 }
338 if (GNUNET_SYSERR == res)
339 return GNUNET_SYSERR;
339 } 340 }
340 if (GNUNET_SYSERR == res)
341 return GNUNET_SYSERR;
342 }
343 return GNUNET_OK; 341 return GNUNET_OK;
344} 342}
345 343
@@ -370,10 +368,10 @@ typedef int (*BitIterator) (void *cls,
370 * @param key the key for which we iterate over the BF bits 368 * @param key the key for which we iterate over the BF bits
371 */ 369 */
372static void 370static void
373iterateBits (const struct GNUNET_CONTAINER_BloomFilter *bf, 371iterateBits(const struct GNUNET_CONTAINER_BloomFilter *bf,
374 BitIterator callback, 372 BitIterator callback,
375 void *arg, 373 void *arg,
376 const struct GNUNET_HashCode *key) 374 const struct GNUNET_HashCode *key)
377{ 375{
378 struct GNUNET_HashCode tmp[2]; 376 struct GNUNET_HashCode tmp[2];
379 int bitCount; 377 int bitCount;
@@ -383,32 +381,32 @@ iterateBits (const struct GNUNET_CONTAINER_BloomFilter *bf,
383 bitCount = bf->addressesPerElement; 381 bitCount = bf->addressesPerElement;
384 tmp[0] = *key; 382 tmp[0] = *key;
385 round = 0; 383 round = 0;
386 GNUNET_assert (bf->bitArraySize > 0); 384 GNUNET_assert(bf->bitArraySize > 0);
387 GNUNET_assert (bf->bitArraySize * 8LL > bf->bitArraySize); 385 GNUNET_assert(bf->bitArraySize * 8LL > bf->bitArraySize);
388 while (bitCount > 0) 386 while (bitCount > 0)
389 {
390 while (slot < (sizeof (struct GNUNET_HashCode) / sizeof (uint32_t)))
391 {
392 if (GNUNET_YES !=
393 callback (arg,
394 bf,
395 ntohl ((((uint32_t *) &tmp[round & 1])[slot])) %
396 ((bf->bitArraySize * 8LL))))
397 return;
398 slot++;
399 bitCount--;
400 if (bitCount == 0)
401 break;
402 }
403 if (bitCount > 0)
404 { 387 {
405 GNUNET_CRYPTO_hash (&tmp[round & 1], 388 while (slot < (sizeof(struct GNUNET_HashCode) / sizeof(uint32_t)))
406 sizeof (struct GNUNET_HashCode), 389 {
407 &tmp[(round + 1) & 1]); 390 if (GNUNET_YES !=
408 round++; 391 callback(arg,
409 slot = 0; 392 bf,
393 ntohl((((uint32_t *)&tmp[round & 1])[slot])) %
394 ((bf->bitArraySize * 8LL))))
395 return;
396 slot++;
397 bitCount--;
398 if (bitCount == 0)
399 break;
400 }
401 if (bitCount > 0)
402 {
403 GNUNET_CRYPTO_hash(&tmp[round & 1],
404 sizeof(struct GNUNET_HashCode),
405 &tmp[(round + 1) & 1]);
406 round++;
407 slot = 0;
408 }
410 } 409 }
411 }
412} 410}
413 411
414 412
@@ -421,13 +419,13 @@ iterateBits (const struct GNUNET_CONTAINER_BloomFilter *bf,
421 * @return GNUNET_YES 419 * @return GNUNET_YES
422 */ 420 */
423static int 421static int
424incrementBitCallback (void *cls, 422incrementBitCallback(void *cls,
425 const struct GNUNET_CONTAINER_BloomFilter *bf, 423 const struct GNUNET_CONTAINER_BloomFilter *bf,
426 unsigned int bit) 424 unsigned int bit)
427{ 425{
428 struct GNUNET_CONTAINER_BloomFilter *b = cls; 426 struct GNUNET_CONTAINER_BloomFilter *b = cls;
429 427
430 incrementBit (b->bitArray, bit, bf->fh); 428 incrementBit(b->bitArray, bit, bf->fh);
431 return GNUNET_YES; 429 return GNUNET_YES;
432} 430}
433 431
@@ -441,13 +439,13 @@ incrementBitCallback (void *cls,
441 * @return GNUNET_YES 439 * @return GNUNET_YES
442 */ 440 */
443static int 441static int
444decrementBitCallback (void *cls, 442decrementBitCallback(void *cls,
445 const struct GNUNET_CONTAINER_BloomFilter *bf, 443 const struct GNUNET_CONTAINER_BloomFilter *bf,
446 unsigned int bit) 444 unsigned int bit)
447{ 445{
448 struct GNUNET_CONTAINER_BloomFilter *b = cls; 446 struct GNUNET_CONTAINER_BloomFilter *b = cls;
449 447
450 decrementBit (b->bitArray, bit, bf->fh); 448 decrementBit(b->bitArray, bit, bf->fh);
451 return GNUNET_YES; 449 return GNUNET_YES;
452} 450}
453 451
@@ -461,17 +459,17 @@ decrementBitCallback (void *cls,
461 * @return YES if the bit is set, NO if not 459 * @return YES if the bit is set, NO if not
462 */ 460 */
463static int 461static int
464testBitCallback (void *cls, 462testBitCallback(void *cls,
465 const struct GNUNET_CONTAINER_BloomFilter *bf, 463 const struct GNUNET_CONTAINER_BloomFilter *bf,
466 unsigned int bit) 464 unsigned int bit)
467{ 465{
468 int *arg = cls; 466 int *arg = cls;
469 467
470 if (GNUNET_NO == testBit (bf->bitArray, bit)) 468 if (GNUNET_NO == testBit(bf->bitArray, bit))
471 { 469 {
472 *arg = GNUNET_NO; 470 *arg = GNUNET_NO;
473 return GNUNET_NO; 471 return GNUNET_NO;
474 } 472 }
475 return GNUNET_YES; 473 return GNUNET_YES;
476} 474}
477 475
@@ -489,9 +487,9 @@ testBitCallback (void *cls,
489 * @return the bloomfilter 487 * @return the bloomfilter
490 */ 488 */
491struct GNUNET_CONTAINER_BloomFilter * 489struct GNUNET_CONTAINER_BloomFilter *
492GNUNET_CONTAINER_bloomfilter_load (const char *filename, 490GNUNET_CONTAINER_bloomfilter_load(const char *filename,
493 size_t size, 491 size_t size,
494 unsigned int k) 492 unsigned int k)
495{ 493{
496 struct GNUNET_CONTAINER_BloomFilter *bf; 494 struct GNUNET_CONTAINER_BloomFilter *bf;
497 char *rbuff; 495 char *rbuff;
@@ -501,7 +499,7 @@ GNUNET_CONTAINER_bloomfilter_load (const char *filename,
501 off_t fsize; 499 off_t fsize;
502 int must_read; 500 int must_read;
503 501
504 GNUNET_assert (NULL != filename); 502 GNUNET_assert(NULL != filename);
505 if ((k == 0) || (size == 0)) 503 if ((k == 0) || (size == 0))
506 return NULL; 504 return NULL;
507 if (size < BUFFSIZE) 505 if (size < BUFFSIZE)
@@ -511,115 +509,115 @@ GNUNET_CONTAINER_bloomfilter_load (const char *filename,
511 ui *= 2; 509 ui *= 2;
512 size = ui; /* make sure it's a power of 2 */ 510 size = ui; /* make sure it's a power of 2 */
513 511
514 bf = GNUNET_new (struct GNUNET_CONTAINER_BloomFilter); 512 bf = GNUNET_new(struct GNUNET_CONTAINER_BloomFilter);
515 /* Try to open a bloomfilter file */ 513 /* Try to open a bloomfilter file */
516 if (GNUNET_YES == GNUNET_DISK_file_test (filename)) 514 if (GNUNET_YES == GNUNET_DISK_file_test(filename))
517 bf->fh = GNUNET_DISK_file_open (filename, 515 bf->fh = GNUNET_DISK_file_open(filename,
518 GNUNET_DISK_OPEN_READWRITE, 516 GNUNET_DISK_OPEN_READWRITE,
519 GNUNET_DISK_PERM_USER_READ | 517 GNUNET_DISK_PERM_USER_READ |
520 GNUNET_DISK_PERM_USER_WRITE); 518 GNUNET_DISK_PERM_USER_WRITE);
521 if (NULL != bf->fh) 519 if (NULL != bf->fh)
522 {
523 /* file existed, try to read it! */
524 must_read = GNUNET_YES;
525 if (GNUNET_OK != GNUNET_DISK_file_handle_size (bf->fh, &fsize))
526 {
527 GNUNET_DISK_file_close (bf->fh);
528 GNUNET_free (bf);
529 return NULL;
530 }
531 if (0 == fsize)
532 {
533 /* found existing empty file, just overwrite */
534 if (GNUNET_OK != make_empty_file (bf->fh, size * 4LL))
535 {
536 GNUNET_log_strerror (GNUNET_ERROR_TYPE_WARNING, "write");
537 GNUNET_DISK_file_close (bf->fh);
538 GNUNET_free (bf);
539 return NULL;
540 }
541 }
542 else if (fsize != ((off_t) size) * 4LL)
543 { 520 {
544 GNUNET_log ( 521 /* file existed, try to read it! */
545 GNUNET_ERROR_TYPE_ERROR, 522 must_read = GNUNET_YES;
546 _ ( 523 if (GNUNET_OK != GNUNET_DISK_file_handle_size(bf->fh, &fsize))
547 "Size of file on disk is incorrect for this Bloom filter (want %llu, have %llu)\n"), 524 {
548 (unsigned long long) (size * 4LL), 525 GNUNET_DISK_file_close(bf->fh);
549 (unsigned long long) fsize); 526 GNUNET_free(bf);
550 GNUNET_DISK_file_close (bf->fh); 527 return NULL;
551 GNUNET_free (bf); 528 }
552 return NULL; 529 if (0 == fsize)
530 {
531 /* found existing empty file, just overwrite */
532 if (GNUNET_OK != make_empty_file(bf->fh, size * 4LL))
533 {
534 GNUNET_log_strerror(GNUNET_ERROR_TYPE_WARNING, "write");
535 GNUNET_DISK_file_close(bf->fh);
536 GNUNET_free(bf);
537 return NULL;
538 }
539 }
540 else if (fsize != ((off_t)size) * 4LL)
541 {
542 GNUNET_log(
543 GNUNET_ERROR_TYPE_ERROR,
544 _(
545 "Size of file on disk is incorrect for this Bloom filter (want %llu, have %llu)\n"),
546 (unsigned long long)(size * 4LL),
547 (unsigned long long)fsize);
548 GNUNET_DISK_file_close(bf->fh);
549 GNUNET_free(bf);
550 return NULL;
551 }
553 } 552 }
554 }
555 else 553 else
556 {
557 /* file did not exist, don't read, just create */
558 must_read = GNUNET_NO;
559 bf->fh = GNUNET_DISK_file_open (filename,
560 GNUNET_DISK_OPEN_CREATE |
561 GNUNET_DISK_OPEN_READWRITE,
562 GNUNET_DISK_PERM_USER_READ |
563 GNUNET_DISK_PERM_USER_WRITE);
564 if (NULL == bf->fh)
565 { 554 {
566 GNUNET_free (bf); 555 /* file did not exist, don't read, just create */
567 return NULL; 556 must_read = GNUNET_NO;
557 bf->fh = GNUNET_DISK_file_open(filename,
558 GNUNET_DISK_OPEN_CREATE |
559 GNUNET_DISK_OPEN_READWRITE,
560 GNUNET_DISK_PERM_USER_READ |
561 GNUNET_DISK_PERM_USER_WRITE);
562 if (NULL == bf->fh)
563 {
564 GNUNET_free(bf);
565 return NULL;
566 }
567 if (GNUNET_OK != make_empty_file(bf->fh, size * 4LL))
568 {
569 GNUNET_log_strerror(GNUNET_ERROR_TYPE_WARNING, "write");
570 GNUNET_DISK_file_close(bf->fh);
571 GNUNET_free(bf);
572 return NULL;
573 }
568 } 574 }
569 if (GNUNET_OK != make_empty_file (bf->fh, size * 4LL)) 575 bf->filename = GNUNET_strdup(filename);
576 /* Alloc block */
577 bf->bitArray = GNUNET_malloc_large(size);
578 if (NULL == bf->bitArray)
570 { 579 {
571 GNUNET_log_strerror (GNUNET_ERROR_TYPE_WARNING, "write"); 580 if (NULL != bf->fh)
572 GNUNET_DISK_file_close (bf->fh); 581 GNUNET_DISK_file_close(bf->fh);
573 GNUNET_free (bf); 582 GNUNET_free(bf->filename);
583 GNUNET_free(bf);
574 return NULL; 584 return NULL;
575 } 585 }
576 }
577 bf->filename = GNUNET_strdup (filename);
578 /* Alloc block */
579 bf->bitArray = GNUNET_malloc_large (size);
580 if (NULL == bf->bitArray)
581 {
582 if (NULL != bf->fh)
583 GNUNET_DISK_file_close (bf->fh);
584 GNUNET_free (bf->filename);
585 GNUNET_free (bf);
586 return NULL;
587 }
588 bf->bitArraySize = size; 586 bf->bitArraySize = size;
589 bf->addressesPerElement = k; 587 bf->addressesPerElement = k;
590 if (GNUNET_YES != must_read) 588 if (GNUNET_YES != must_read)
591 return bf; /* already done! */ 589 return bf; /* already done! */
592 /* Read from the file what bits we can */ 590 /* Read from the file what bits we can */
593 rbuff = GNUNET_malloc (BUFFSIZE); 591 rbuff = GNUNET_malloc(BUFFSIZE);
594 pos = 0; 592 pos = 0;
595 while (pos < ((off_t) size) * 8LL) 593 while (pos < ((off_t)size) * 8LL)
596 {
597 int res;
598
599 res = GNUNET_DISK_file_read (bf->fh, rbuff, BUFFSIZE);
600 if (res == -1)
601 { 594 {
602 LOG_STRERROR_FILE (GNUNET_ERROR_TYPE_WARNING, "read", bf->filename); 595 int res;
603 GNUNET_free (rbuff); 596
604 GNUNET_free (bf->filename); 597 res = GNUNET_DISK_file_read(bf->fh, rbuff, BUFFSIZE);
605 GNUNET_DISK_file_close (bf->fh); 598 if (res == -1)
606 GNUNET_free (bf); 599 {
607 return NULL; 600 LOG_STRERROR_FILE(GNUNET_ERROR_TYPE_WARNING, "read", bf->filename);
608 } 601 GNUNET_free(rbuff);
609 if (res == 0) 602 GNUNET_free(bf->filename);
610 break; /* is ok! we just did not use that many bits yet */ 603 GNUNET_DISK_file_close(bf->fh);
611 for (i = 0; i < res; i++) 604 GNUNET_free(bf);
612 { 605 return NULL;
613 if ((rbuff[i] & 0x0F) != 0) 606 }
614 setBit (bf->bitArray, pos + i * 2); 607 if (res == 0)
615 if ((rbuff[i] & 0xF0) != 0) 608 break; /* is ok! we just did not use that many bits yet */
616 setBit (bf->bitArray, pos + i * 2 + 1); 609 for (i = 0; i < res; i++)
610 {
611 if ((rbuff[i] & 0x0F) != 0)
612 setBit(bf->bitArray, pos + i * 2);
613 if ((rbuff[i] & 0xF0) != 0)
614 setBit(bf->bitArray, pos + i * 2 + 1);
615 }
616 if (res < BUFFSIZE)
617 break;
618 pos += BUFFSIZE * 2; /* 2 bits per byte in the buffer */
617 } 619 }
618 if (res < BUFFSIZE) 620 GNUNET_free(rbuff);
619 break;
620 pos += BUFFSIZE * 2; /* 2 bits per byte in the buffer */
621 }
622 GNUNET_free (rbuff);
623 return bf; 621 return bf;
624} 622}
625 623
@@ -638,27 +636,27 @@ GNUNET_CONTAINER_bloomfilter_load (const char *filename,
638 * @return the bloomfilter 636 * @return the bloomfilter
639 */ 637 */
640struct GNUNET_CONTAINER_BloomFilter * 638struct GNUNET_CONTAINER_BloomFilter *
641GNUNET_CONTAINER_bloomfilter_init (const char *data, 639GNUNET_CONTAINER_bloomfilter_init(const char *data,
642 size_t size, 640 size_t size,
643 unsigned int k) 641 unsigned int k)
644{ 642{
645 struct GNUNET_CONTAINER_BloomFilter *bf; 643 struct GNUNET_CONTAINER_BloomFilter *bf;
646 644
647 if ((0 == k) || (0 == size)) 645 if ((0 == k) || (0 == size))
648 return NULL; 646 return NULL;
649 bf = GNUNET_new (struct GNUNET_CONTAINER_BloomFilter); 647 bf = GNUNET_new(struct GNUNET_CONTAINER_BloomFilter);
650 bf->filename = NULL; 648 bf->filename = NULL;
651 bf->fh = NULL; 649 bf->fh = NULL;
652 bf->bitArray = GNUNET_malloc_large (size); 650 bf->bitArray = GNUNET_malloc_large(size);
653 if (NULL == bf->bitArray) 651 if (NULL == bf->bitArray)
654 { 652 {
655 GNUNET_free (bf); 653 GNUNET_free(bf);
656 return NULL; 654 return NULL;
657 } 655 }
658 bf->bitArraySize = size; 656 bf->bitArraySize = size;
659 bf->addressesPerElement = k; 657 bf->addressesPerElement = k;
660 if (NULL != data) 658 if (NULL != data)
661 GNUNET_memcpy (bf->bitArray, data, size); 659 GNUNET_memcpy(bf->bitArray, data, size);
662 return bf; 660 return bf;
663} 661}
664 662
@@ -673,7 +671,7 @@ GNUNET_CONTAINER_bloomfilter_init (const char *data,
673 * @return #GNUNET_SYSERR if the data array is not big enough 671 * @return #GNUNET_SYSERR if the data array is not big enough
674 */ 672 */
675int 673int
676GNUNET_CONTAINER_bloomfilter_get_raw_data ( 674GNUNET_CONTAINER_bloomfilter_get_raw_data(
677 const struct GNUNET_CONTAINER_BloomFilter *bf, 675 const struct GNUNET_CONTAINER_BloomFilter *bf,
678 char *data, 676 char *data,
679 size_t size) 677 size_t size)
@@ -682,7 +680,7 @@ GNUNET_CONTAINER_bloomfilter_get_raw_data (
682 return GNUNET_SYSERR; 680 return GNUNET_SYSERR;
683 if (bf->bitArraySize != size) 681 if (bf->bitArraySize != size)
684 return GNUNET_SYSERR; 682 return GNUNET_SYSERR;
685 GNUNET_memcpy (data, bf->bitArray, size); 683 GNUNET_memcpy(data, bf->bitArray, size);
686 return GNUNET_OK; 684 return GNUNET_OK;
687} 685}
688 686
@@ -695,15 +693,15 @@ GNUNET_CONTAINER_bloomfilter_get_raw_data (
695 * @param bf the filter 693 * @param bf the filter
696 */ 694 */
697void 695void
698GNUNET_CONTAINER_bloomfilter_free (struct GNUNET_CONTAINER_BloomFilter *bf) 696GNUNET_CONTAINER_bloomfilter_free(struct GNUNET_CONTAINER_BloomFilter *bf)
699{ 697{
700 if (NULL == bf) 698 if (NULL == bf)
701 return; 699 return;
702 if (bf->fh != NULL) 700 if (bf->fh != NULL)
703 GNUNET_DISK_file_close (bf->fh); 701 GNUNET_DISK_file_close(bf->fh);
704 GNUNET_free_non_null (bf->filename); 702 GNUNET_free_non_null(bf->filename);
705 GNUNET_free (bf->bitArray); 703 GNUNET_free(bf->bitArray);
706 GNUNET_free (bf); 704 GNUNET_free(bf);
707} 705}
708 706
709 707
@@ -713,14 +711,14 @@ GNUNET_CONTAINER_bloomfilter_free (struct GNUNET_CONTAINER_BloomFilter *bf)
713 * @param bf the filter 711 * @param bf the filter
714 */ 712 */
715void 713void
716GNUNET_CONTAINER_bloomfilter_clear (struct GNUNET_CONTAINER_BloomFilter *bf) 714GNUNET_CONTAINER_bloomfilter_clear(struct GNUNET_CONTAINER_BloomFilter *bf)
717{ 715{
718 if (NULL == bf) 716 if (NULL == bf)
719 return; 717 return;
720 718
721 memset (bf->bitArray, 0, bf->bitArraySize); 719 memset(bf->bitArray, 0, bf->bitArraySize);
722 if (bf->filename != NULL) 720 if (bf->filename != NULL)
723 make_empty_file (bf->fh, bf->bitArraySize * 4LL); 721 make_empty_file(bf->fh, bf->bitArraySize * 4LL);
724} 722}
725 723
726 724
@@ -732,7 +730,7 @@ GNUNET_CONTAINER_bloomfilter_clear (struct GNUNET_CONTAINER_BloomFilter *bf)
732 * @return #GNUNET_YES if the element is in the filter, #GNUNET_NO if not 730 * @return #GNUNET_YES if the element is in the filter, #GNUNET_NO if not
733 */ 731 */
734int 732int
735GNUNET_CONTAINER_bloomfilter_test ( 733GNUNET_CONTAINER_bloomfilter_test(
736 const struct GNUNET_CONTAINER_BloomFilter *bf, 734 const struct GNUNET_CONTAINER_BloomFilter *bf,
737 const struct GNUNET_HashCode *e) 735 const struct GNUNET_HashCode *e)
738{ 736{
@@ -741,7 +739,7 @@ GNUNET_CONTAINER_bloomfilter_test (
741 if (NULL == bf) 739 if (NULL == bf)
742 return GNUNET_YES; 740 return GNUNET_YES;
743 res = GNUNET_YES; 741 res = GNUNET_YES;
744 iterateBits (bf, &testBitCallback, &res, e); 742 iterateBits(bf, &testBitCallback, &res, e);
745 return res; 743 return res;
746} 744}
747 745
@@ -753,12 +751,12 @@ GNUNET_CONTAINER_bloomfilter_test (
753 * @param e the element 751 * @param e the element
754 */ 752 */
755void 753void
756GNUNET_CONTAINER_bloomfilter_add (struct GNUNET_CONTAINER_BloomFilter *bf, 754GNUNET_CONTAINER_bloomfilter_add(struct GNUNET_CONTAINER_BloomFilter *bf,
757 const struct GNUNET_HashCode *e) 755 const struct GNUNET_HashCode *e)
758{ 756{
759 if (NULL == bf) 757 if (NULL == bf)
760 return; 758 return;
761 iterateBits (bf, &incrementBitCallback, bf, e); 759 iterateBits(bf, &incrementBitCallback, bf, e);
762} 760}
763 761
764 762
@@ -773,9 +771,9 @@ GNUNET_CONTAINER_bloomfilter_add (struct GNUNET_CONTAINER_BloomFilter *bf,
773 * @param size number of bytes in data 771 * @param size number of bytes in data
774 */ 772 */
775int 773int
776GNUNET_CONTAINER_bloomfilter_or (struct GNUNET_CONTAINER_BloomFilter *bf, 774GNUNET_CONTAINER_bloomfilter_or(struct GNUNET_CONTAINER_BloomFilter *bf,
777 const char *data, 775 const char *data,
778 size_t size) 776 size_t size)
779{ 777{
780 unsigned int i; 778 unsigned int i;
781 unsigned int n; 779 unsigned int n;
@@ -786,13 +784,13 @@ GNUNET_CONTAINER_bloomfilter_or (struct GNUNET_CONTAINER_BloomFilter *bf,
786 return GNUNET_YES; 784 return GNUNET_YES;
787 if (bf->bitArraySize != size) 785 if (bf->bitArraySize != size)
788 return GNUNET_SYSERR; 786 return GNUNET_SYSERR;
789 fc = (unsigned long long *) bf->bitArray; 787 fc = (unsigned long long *)bf->bitArray;
790 dc = (const unsigned long long *) data; 788 dc = (const unsigned long long *)data;
791 n = size / sizeof (unsigned long long); 789 n = size / sizeof(unsigned long long);
792 790
793 for (i = 0; i < n; i++) 791 for (i = 0; i < n; i++)
794 fc[i] |= dc[i]; 792 fc[i] |= dc[i];
795 for (i = n * sizeof (unsigned long long); i < size; i++) 793 for (i = n * sizeof(unsigned long long); i < size; i++)
796 bf->bitArray[i] |= data[i]; 794 bf->bitArray[i] |= data[i];
797 return GNUNET_OK; 795 return GNUNET_OK;
798} 796}
@@ -808,7 +806,7 @@ GNUNET_CONTAINER_bloomfilter_or (struct GNUNET_CONTAINER_BloomFilter *bf,
808 * @return #GNUNET_OK on success 806 * @return #GNUNET_OK on success
809 */ 807 */
810int 808int
811GNUNET_CONTAINER_bloomfilter_or2 ( 809GNUNET_CONTAINER_bloomfilter_or2(
812 struct GNUNET_CONTAINER_BloomFilter *bf, 810 struct GNUNET_CONTAINER_BloomFilter *bf,
813 const struct GNUNET_CONTAINER_BloomFilter *to_or) 811 const struct GNUNET_CONTAINER_BloomFilter *to_or)
814{ 812{
@@ -821,18 +819,18 @@ GNUNET_CONTAINER_bloomfilter_or2 (
821 if (NULL == bf) 819 if (NULL == bf)
822 return GNUNET_OK; 820 return GNUNET_OK;
823 if (bf->bitArraySize != to_or->bitArraySize) 821 if (bf->bitArraySize != to_or->bitArraySize)
824 { 822 {
825 GNUNET_break (0); 823 GNUNET_break(0);
826 return GNUNET_SYSERR; 824 return GNUNET_SYSERR;
827 } 825 }
828 size = bf->bitArraySize; 826 size = bf->bitArraySize;
829 fc = (unsigned long long *) bf->bitArray; 827 fc = (unsigned long long *)bf->bitArray;
830 dc = (const unsigned long long *) to_or->bitArray; 828 dc = (const unsigned long long *)to_or->bitArray;
831 n = size / sizeof (unsigned long long); 829 n = size / sizeof(unsigned long long);
832 830
833 for (i = 0; i < n; i++) 831 for (i = 0; i < n; i++)
834 fc[i] |= dc[i]; 832 fc[i] |= dc[i];
835 for (i = n * sizeof (unsigned long long); i < size; i++) 833 for (i = n * sizeof(unsigned long long); i < size; i++)
836 bf->bitArray[i] |= to_or->bitArray[i]; 834 bf->bitArray[i] |= to_or->bitArray[i];
837 return GNUNET_OK; 835 return GNUNET_OK;
838} 836}
@@ -845,14 +843,14 @@ GNUNET_CONTAINER_bloomfilter_or2 (
845 * @param e the element to remove 843 * @param e the element to remove
846 */ 844 */
847void 845void
848GNUNET_CONTAINER_bloomfilter_remove (struct GNUNET_CONTAINER_BloomFilter *bf, 846GNUNET_CONTAINER_bloomfilter_remove(struct GNUNET_CONTAINER_BloomFilter *bf,
849 const struct GNUNET_HashCode *e) 847 const struct GNUNET_HashCode *e)
850{ 848{
851 if (NULL == bf) 849 if (NULL == bf)
852 return; 850 return;
853 if (NULL == bf->filename) 851 if (NULL == bf->filename)
854 return; 852 return;
855 iterateBits (bf, &decrementBitCallback, bf, e); 853 iterateBits(bf, &decrementBitCallback, bf, e);
856} 854}
857 855
858/** 856/**
@@ -867,27 +865,27 @@ GNUNET_CONTAINER_bloomfilter_remove (struct GNUNET_CONTAINER_BloomFilter *bf,
867 * @param k the new number of GNUNET_CRYPTO_hash-function to apply per element 865 * @param k the new number of GNUNET_CRYPTO_hash-function to apply per element
868 */ 866 */
869void 867void
870GNUNET_CONTAINER_bloomfilter_resize (struct GNUNET_CONTAINER_BloomFilter *bf, 868GNUNET_CONTAINER_bloomfilter_resize(struct GNUNET_CONTAINER_BloomFilter *bf,
871 GNUNET_CONTAINER_HashCodeIterator iterator, 869 GNUNET_CONTAINER_HashCodeIterator iterator,
872 void *iterator_cls, 870 void *iterator_cls,
873 size_t size, 871 size_t size,
874 unsigned int k) 872 unsigned int k)
875{ 873{
876 struct GNUNET_HashCode hc; 874 struct GNUNET_HashCode hc;
877 unsigned int i; 875 unsigned int i;
878 876
879 GNUNET_free (bf->bitArray); 877 GNUNET_free(bf->bitArray);
880 i = 1; 878 i = 1;
881 while (i < size) 879 while (i < size)
882 i *= 2; 880 i *= 2;
883 size = i; /* make sure it's a power of 2 */ 881 size = i; /* make sure it's a power of 2 */
884 bf->addressesPerElement = k; 882 bf->addressesPerElement = k;
885 bf->bitArraySize = size; 883 bf->bitArraySize = size;
886 bf->bitArray = GNUNET_malloc (size); 884 bf->bitArray = GNUNET_malloc(size);
887 if (NULL != bf->filename) 885 if (NULL != bf->filename)
888 make_empty_file (bf->fh, bf->bitArraySize * 4LL); 886 make_empty_file(bf->fh, bf->bitArraySize * 4LL);
889 while (GNUNET_YES == iterator (iterator_cls, &hc)) 887 while (GNUNET_YES == iterator(iterator_cls, &hc))
890 GNUNET_CONTAINER_bloomfilter_add (bf, &hc); 888 GNUNET_CONTAINER_bloomfilter_add(bf, &hc);
891} 889}
892 890
893/* end of container_bloomfilter.c */ 891/* end of container_bloomfilter.c */