X-Git-Url: https://git.librecmc.org/?a=blobdiff_plain;f=src%2Futil%2Fcontainer_bloomfilter.c;h=8c226f67d9581eee16d0b186133d8359ef2129c2;hb=8f654f30c3c4987c9ca1b564d6e6f2d75ae24862;hp=a3152000bcace7763d4593e200edb202e3c6d9c3;hpb=c6c111abd1e7ffec4c5dacbb25baf9ed6b9da695;p=oweals%2Fgnunet.git diff --git a/src/util/container_bloomfilter.c b/src/util/container_bloomfilter.c index a3152000b..8c226f67d 100644 --- a/src/util/container_bloomfilter.c +++ b/src/util/container_bloomfilter.c @@ -1,6 +1,6 @@ /* This file is part of GNUnet. - (C) 2001, 2002, 2003, 2004, 2006, 2008 Christian Grothoff (and other contributing authors) + (C) 2001, 2002, 2003, 2004, 2006, 2008, 2011, 2012 Christian Grothoff (and other contributing authors) GNUnet is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published @@ -44,6 +44,12 @@ #include "gnunet_container_lib.h" #include "gnunet_disk_lib.h" +#define LOG(kind,...) GNUNET_log_from (kind, "util", __VA_ARGS__) + +#define LOG_STRERROR(kind,syscall) GNUNET_log_from_strerror (kind, "util", syscall) + +#define LOG_STRERROR_FILE(kind,syscall,filename) GNUNET_log_from_strerror_file (kind, "util", syscall, filename) + struct GNUNET_CONTAINER_BloomFilter { @@ -177,7 +183,7 @@ static void incrementBit (char *bitArray, unsigned int bitIdx, const struct GNUNET_DISK_FileHandle *fh) { - off_t fileSlot; + OFF_T fileSlot; unsigned char value; unsigned int high; unsigned int low; @@ -225,7 +231,7 @@ static void decrementBit (char *bitArray, unsigned int bitIdx, const struct GNUNET_DISK_FileHandle *fh) { - off_t fileSlot; + OFF_T fileSlot; unsigned char value; unsigned int high; unsigned int low; @@ -276,33 +282,33 @@ decrementBit (char *bitArray, unsigned int bitIdx, * @return GNUNET_OK if created ok, GNUNET_SYSERR otherwise */ static int -makeEmptyFile (const struct GNUNET_DISK_FileHandle *fh, size_t size) +make_empty_file (const struct GNUNET_DISK_FileHandle *fh, size_t size) { - char *buffer; + char buffer[BUFFSIZE]; size_t bytesleft = size; int res = 0; if (GNUNET_DISK_handle_invalid (fh)) return GNUNET_SYSERR; - buffer = GNUNET_malloc (BUFFSIZE); - memset (buffer, 0, BUFFSIZE); + memset (buffer, 0, sizeof (buffer)); GNUNET_DISK_file_seek (fh, 0, GNUNET_DISK_SEEK_SET); - while (bytesleft > 0) { - if (bytesleft > BUFFSIZE) + if (bytesleft > sizeof (buffer)) { - res = GNUNET_DISK_file_write (fh, buffer, BUFFSIZE); - bytesleft -= BUFFSIZE; + res = GNUNET_DISK_file_write (fh, buffer, sizeof (buffer)); + if (res >= 0) + bytesleft -= res; } else { res = GNUNET_DISK_file_write (fh, buffer, bytesleft); - bytesleft = 0; + if (res >= 0) + bytesleft -= res; } - GNUNET_assert (res != GNUNET_SYSERR); + if (GNUNET_SYSERR == res) + return GNUNET_SYSERR; } - GNUNET_free (buffer); return GNUNET_OK; } @@ -316,10 +322,12 @@ makeEmptyFile (const struct GNUNET_DISK_FileHandle *fh, size_t size) * @param cls closure * @param bf the filter to manipulate * @param bit the current bit + * @return GNUNET_YES to continue, GNUNET_NO to stop early */ -typedef void (*BitIterator) (void *cls, - const struct GNUNET_CONTAINER_BloomFilter * bf, - unsigned int bit); +typedef int (*BitIterator) (void *cls, + const struct GNUNET_CONTAINER_BloomFilter * bf, + unsigned int bit); + /** * Call an iterator for each bit that the bloomfilter @@ -336,19 +344,23 @@ iterateBits (const struct GNUNET_CONTAINER_BloomFilter *bf, { GNUNET_HashCode tmp[2]; int bitCount; - int round; + unsigned int round; unsigned int slot = 0; bitCount = bf->addressesPerElement; tmp[0] = *key; round = 0; + GNUNET_assert (bf->bitArraySize > 0); + GNUNET_assert (bf->bitArraySize * 8LL > bf->bitArraySize); while (bitCount > 0) { while (slot < (sizeof (GNUNET_HashCode) / sizeof (uint32_t))) { - callback (arg, bf, - (((uint32_t *) & tmp[round & 1])[slot]) & - ((bf->bitArraySize * 8) - 1)); + if (GNUNET_YES != + callback (arg, bf, + (((uint32_t *) & tmp[round & 1])[slot]) % + ((bf->bitArraySize * 8LL)))) + return; slot++; bitCount--; if (bitCount == 0) @@ -364,53 +376,65 @@ iterateBits (const struct GNUNET_CONTAINER_BloomFilter *bf, } } + /** * Callback: increment bit * * @param cls pointer to writeable form of bf * @param bf the filter to manipulate * @param bit the bit to increment + * @return GNUNET_YES */ -static void +static int incrementBitCallback (void *cls, const struct GNUNET_CONTAINER_BloomFilter *bf, unsigned int bit) { struct GNUNET_CONTAINER_BloomFilter *b = cls; incrementBit (b->bitArray, bit, bf->fh); + return GNUNET_YES; } + /** * Callback: decrement bit * * @param cls pointer to writeable form of bf * @param bf the filter to manipulate * @param bit the bit to decrement + * @return GNUNET_YES */ -static void +static int decrementBitCallback (void *cls, const struct GNUNET_CONTAINER_BloomFilter *bf, unsigned int bit) { struct GNUNET_CONTAINER_BloomFilter *b = cls; decrementBit (b->bitArray, bit, bf->fh); + return GNUNET_YES; } + /** * Callback: test if all bits are set * * @param cls pointer set to GNUNET_NO if bit is not set * @param bf the filter * @param bit the bit to test + * @return YES if the bit is set, NO if not */ -static void +static int testBitCallback (void *cls, const struct GNUNET_CONTAINER_BloomFilter *bf, unsigned int bit) { int *arg = cls; if (GNUNET_NO == testBit (bf->bitArray, bit)) + { *arg = GNUNET_NO; + return GNUNET_NO; + } + return GNUNET_YES; } /* *********************** INTERFACE **************** */ @@ -420,7 +444,8 @@ testBitCallback (void *cls, const struct GNUNET_CONTAINER_BloomFilter *bf, * * @param filename the name of the file (or the prefix) * @param size the size of the bloom-filter (number of - * bytes of storage space to use) + * bytes of storage space to use); will be rounded up + * to next power of 2 * @param k the number of GNUNET_CRYPTO_hash-functions to apply per * element (number of bits set per element in the set) * @return the bloomfilter @@ -431,9 +456,11 @@ GNUNET_CONTAINER_bloomfilter_load (const char *filename, size_t size, { struct GNUNET_CONTAINER_BloomFilter *bf; char *rbuff; - off_t pos; + OFF_T pos; int i; size_t ui; + OFF_T fsize; + int must_read; GNUNET_assert (NULL != filename); if ((k == 0) || (size == 0)) @@ -441,22 +468,76 @@ GNUNET_CONTAINER_bloomfilter_load (const char *filename, size_t size, if (size < BUFFSIZE) size = BUFFSIZE; ui = 1; - while (ui < size) + while ( (ui < size) && + (ui * 2 > ui) ) ui *= 2; size = ui; /* make sure it's a power of 2 */ bf = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_BloomFilter)); /* Try to open a bloomfilter file */ - bf->fh = + if (GNUNET_YES == GNUNET_DISK_file_test (filename)) + bf->fh = GNUNET_DISK_file_open (filename, - GNUNET_DISK_OPEN_READWRITE | - GNUNET_DISK_OPEN_CREATE, + GNUNET_DISK_OPEN_READWRITE, GNUNET_DISK_PERM_USER_READ | GNUNET_DISK_PERM_USER_WRITE); - if (NULL == bf->fh) + if (NULL != bf->fh) { - GNUNET_free (bf); - return NULL; + /* file existed, try to read it! */ + must_read = GNUNET_YES; + if (GNUNET_OK != + GNUNET_DISK_file_handle_size (bf->fh, &fsize)) + { + GNUNET_DISK_file_close (bf->fh); + GNUNET_free (bf); + return NULL; + } + if (fsize == 0) + { + /* found existing empty file, just overwrite */ + if (GNUNET_OK != make_empty_file (bf->fh, size * 4LL)) + { + GNUNET_log_strerror (GNUNET_ERROR_TYPE_WARNING, + "write"); + GNUNET_DISK_file_close (bf->fh); + GNUNET_free (bf); + return NULL; + } + } + else if (fsize != size * 4LL) + { + GNUNET_log (GNUNET_ERROR_TYPE_ERROR, + _("Size of file on disk is incorrect for this Bloom filter (want %llu, have %llu)\n"), + (unsigned long long) (size * 4LL), + (unsigned long long) fsize); + GNUNET_DISK_file_close (bf->fh); + GNUNET_free (bf); + return NULL; + } + } + else + { + /* file did not exist, don't read, just create */ + must_read = GNUNET_NO; + bf->fh = + GNUNET_DISK_file_open (filename, + GNUNET_DISK_OPEN_CREATE | + GNUNET_DISK_OPEN_READWRITE, + GNUNET_DISK_PERM_USER_READ | + GNUNET_DISK_PERM_USER_WRITE); + if (NULL == bf->fh) + { + GNUNET_free (bf); + return NULL; + } + if (GNUNET_OK != make_empty_file (bf->fh, size * 4LL)) + { + GNUNET_log_strerror (GNUNET_ERROR_TYPE_WARNING, + "write"); + GNUNET_DISK_file_close (bf->fh); + GNUNET_free (bf); + return NULL; + } } bf->filename = GNUNET_strdup (filename); /* Alloc block */ @@ -471,20 +552,24 @@ GNUNET_CONTAINER_bloomfilter_load (const char *filename, size_t size, } bf->bitArraySize = size; bf->addressesPerElement = k; - memset (bf->bitArray, 0, bf->bitArraySize); - + if (GNUNET_YES != must_read) + return bf; /* already done! */ /* Read from the file what bits we can */ rbuff = GNUNET_malloc (BUFFSIZE); pos = 0; - while (pos < size * 8) + while (pos < size * 8LL) { int res; res = GNUNET_DISK_file_read (bf->fh, rbuff, BUFFSIZE); if (res == -1) { - GNUNET_log_strerror_file (GNUNET_ERROR_TYPE_WARNING, "read", - bf->filename); + LOG_STRERROR_FILE (GNUNET_ERROR_TYPE_WARNING, "read", bf->filename); + GNUNET_free (rbuff); + GNUNET_free (bf->filename); + GNUNET_DISK_file_close (bf->fh); + GNUNET_free (bf); + return NULL; } if (res == 0) break; /* is ok! we just did not use that many bits yet */ @@ -522,33 +607,22 @@ GNUNET_CONTAINER_bloomfilter_init (const char *data, size_t size, unsigned int k) { struct GNUNET_CONTAINER_BloomFilter *bf; - size_t ui; - if ((k == 0) || (size == 0)) + if ((0 == k) || (0 == size)) return NULL; - ui = 1; - while (ui < size) - ui *= 2; - if (size != ui) - { - GNUNET_break (0); - return NULL; - } bf = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_BloomFilter)); bf->filename = NULL; bf->fh = NULL; bf->bitArray = GNUNET_malloc_large (size); - if (bf->bitArray == NULL) + if (NULL == bf->bitArray) { GNUNET_free (bf); return NULL; } bf->bitArraySize = size; bf->addressesPerElement = k; - if (data != NULL) + if (NULL != data) memcpy (bf->bitArray, data, size); - else - memset (bf->bitArray, 0, bf->bitArraySize); return bf; } @@ -575,6 +649,7 @@ GNUNET_CONTAINER_bloomfilter_get_raw_data (const struct return GNUNET_OK; } + /** * Free the space associated with a filter * in memory, flush to drive if needed (do not @@ -594,6 +669,7 @@ GNUNET_CONTAINER_bloomfilter_free (struct GNUNET_CONTAINER_BloomFilter *bf) GNUNET_free (bf); } + /** * Reset a bloom filter to empty. Clears the file on disk. * @@ -607,7 +683,7 @@ GNUNET_CONTAINER_bloomfilter_clear (struct GNUNET_CONTAINER_BloomFilter *bf) memset (bf->bitArray, 0, bf->bitArraySize); if (bf->filename != NULL) - makeEmptyFile (bf->fh, bf->bitArraySize * 4); + make_empty_file (bf->fh, bf->bitArraySize * 4LL); } @@ -631,6 +707,7 @@ GNUNET_CONTAINER_bloomfilter_test (const struct GNUNET_CONTAINER_BloomFilter return res; } + /** * Add an element to the filter * @@ -641,7 +718,6 @@ void GNUNET_CONTAINER_bloomfilter_add (struct GNUNET_CONTAINER_BloomFilter *bf, const GNUNET_HashCode * e) { - if (NULL == bf) return; iterateBits (bf, &incrementBitCallback, bf, e); @@ -762,9 +838,8 @@ GNUNET_CONTAINER_bloomfilter_resize (struct GNUNET_CONTAINER_BloomFilter *bf, bf->bitArraySize = size; bf->bitArray = GNUNET_malloc (size); - memset (bf->bitArray, 0, bf->bitArraySize); if (bf->filename != NULL) - makeEmptyFile (bf->fh, bf->bitArraySize * 4); + make_empty_file (bf->fh, bf->bitArraySize * 4LL); while (GNUNET_YES == iterator (iterator_cls, &hc)) GNUNET_CONTAINER_bloomfilter_add (bf, &hc); }