X-Git-Url: https://git.librecmc.org/?a=blobdiff_plain;f=src%2Futil%2Fcontainer_bloomfilter.c;h=84aab6b17865dd9484911136bec62ec725738c8a;hb=f491ac4fab469421986f77df0bbf79fefc417786;hp=b4c3ad08da0b20a8751ea94877d94338e1264fc5;hpb=134924d50bf7b1efa08ff2622c4d09576a9f9a39;p=oweals%2Fgnunet.git diff --git a/src/util/container_bloomfilter.c b/src/util/container_bloomfilter.c index b4c3ad08d..84aab6b17 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 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 { @@ -82,9 +88,9 @@ struct GNUNET_CONTAINER_BloomFilter * @param bf the filter * @return number of bytes used for the data of the bloom filter */ -size_t +size_t GNUNET_CONTAINER_bloomfilter_get_size (const struct GNUNET_CONTAINER_BloomFilter - *bf) + *bf) { if (bf == NULL) return 0; @@ -99,11 +105,11 @@ GNUNET_CONTAINER_bloomfilter_get_size (const struct GNUNET_CONTAINER_BloomFilter * @return copy of the bf */ struct GNUNET_CONTAINER_BloomFilter * -GNUNET_CONTAINER_bloomfilter_copy (const struct GNUNET_CONTAINER_BloomFilter *bf) +GNUNET_CONTAINER_bloomfilter_copy (const struct GNUNET_CONTAINER_BloomFilter + *bf) { - return GNUNET_CONTAINER_bloomfilter_init (bf->bitArray, - bf->bitArraySize, - bf->addressesPerElement); + return GNUNET_CONTAINER_bloomfilter_init (bf->bitArray, bf->bitArraySize, + bf->addressesPerElement); } @@ -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; @@ -198,19 +204,18 @@ incrementBit (char *bitArray, unsigned int bitIdx, high = (value & (~0xF)) >> 4; if (targetLoc == 0) - { - if (low < 0xF) - low++; - } + { + if (low < 0xF) + low++; + } else - { - if (high < 0xF) - high++; - } + { + if (high < 0xF) + high++; + } value = ((high << 4) | low); - GNUNET_assert (fileSlot == GNUNET_DISK_file_seek (fh, - fileSlot, - GNUNET_DISK_SEEK_SET)); + GNUNET_assert (fileSlot == + GNUNET_DISK_file_seek (fh, fileSlot, GNUNET_DISK_SEEK_SET)); GNUNET_assert (1 == GNUNET_DISK_file_write (fh, &value, 1)); } @@ -226,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; @@ -245,23 +250,23 @@ decrementBit (char *bitArray, unsigned int bitIdx, /* decrement, but once we have reached the max, never go back! */ if (targetLoc == 0) + { + if ((low > 0) && (low < 0xF)) + low--; + if (low == 0) { - if ((low > 0) && (low < 0xF)) - low--; - if (low == 0) - { - clearBit (bitArray, bitIdx); - } + clearBit (bitArray, bitIdx); } + } else + { + if ((high > 0) && (high < 0xF)) + high--; + if (high == 0) { - if ((high > 0) && (high < 0xF)) - high--; - if (high == 0) - { - clearBit (bitArray, bitIdx); - } + clearBit (bitArray, bitIdx); } + } value = ((high << 4) | low); GNUNET_DISK_file_seek (fh, fileSlot, GNUNET_DISK_SEEK_SET); GNUNET_assert (1 == GNUNET_DISK_file_write (fh, &value, 1)); @@ -277,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 > sizeof (buffer)) + { + res = GNUNET_DISK_file_write (fh, buffer, sizeof (buffer)); + if (res >= 0) + bytesleft -= res; + } + else { - if (bytesleft > BUFFSIZE) - { - res = GNUNET_DISK_file_write (fh, buffer, BUFFSIZE); - bytesleft -= BUFFSIZE; - } - else - { - res = GNUNET_DISK_file_write (fh, buffer, bytesleft); - bytesleft = 0; - } - GNUNET_assert (res != GNUNET_SYSERR); + res = GNUNET_DISK_file_write (fh, buffer, bytesleft); + if (res >= 0) + bytesleft -= res; } - GNUNET_free (buffer); + if (GNUNET_SYSERR == res) + return GNUNET_SYSERR; + } return GNUNET_OK; } @@ -317,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 @@ -333,86 +340,99 @@ typedef void (*BitIterator) (void *cls, */ static void iterateBits (const struct GNUNET_CONTAINER_BloomFilter *bf, - BitIterator callback, void *arg, const GNUNET_HashCode *key) + BitIterator callback, void *arg, const GNUNET_HashCode * key) { GNUNET_HashCode tmp[2]; int bitCount; - int round; + unsigned int round; unsigned int slot = 0; bitCount = bf->addressesPerElement; - memcpy (&tmp[0], key, sizeof (GNUNET_HashCode)); + tmp[0] = *key; round = 0; while (bitCount > 0) + { + while (slot < (sizeof (GNUNET_HashCode) / sizeof (uint32_t))) { - while (slot < (sizeof (GNUNET_HashCode) / sizeof (uint32_t))) - { - callback (arg, - bf, - (((uint32_t *) &tmp[round & 1])[slot]) & - ((bf->bitArraySize * 8) - 1)); - slot++; - bitCount--; - if (bitCount == 0) - break; - } - if (bitCount > 0) - { - GNUNET_CRYPTO_hash (&tmp[round & 1], sizeof (GNUNET_HashCode), - &tmp[(round + 1) & 1]); - round++; - slot = 0; - } + if (GNUNET_YES != + callback (arg, bf, + (((uint32_t *) & tmp[round & 1])[slot]) & + ((bf->bitArraySize * 8) - 1))) + return; + slot++; + bitCount--; + if (bitCount == 0) + break; } + if (bitCount > 0) + { + GNUNET_CRYPTO_hash (&tmp[round & 1], sizeof (GNUNET_HashCode), + &tmp[(round + 1) & 1]); + round++; + slot = 0; + } + } } + /** * 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 -incrementBitCallback (void *cls, - const struct GNUNET_CONTAINER_BloomFilter *bf, +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 -decrementBitCallback (void *cls, - const struct GNUNET_CONTAINER_BloomFilter *bf, +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 -testBitCallback (void *cls, - const struct GNUNET_CONTAINER_BloomFilter *bf, - unsigned int bit) +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 **************** */ @@ -428,14 +448,16 @@ testBitCallback (void *cls, * @return the bloomfilter */ struct GNUNET_CONTAINER_BloomFilter * -GNUNET_CONTAINER_bloomfilter_load (const char *filename, - size_t size, unsigned int k) +GNUNET_CONTAINER_bloomfilter_load (const char *filename, size_t size, + unsigned int k) { 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)) @@ -443,62 +465,124 @@ GNUNET_CONTAINER_bloomfilter_load (const char *filename, 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 = GNUNET_DISK_file_open (filename, GNUNET_DISK_OPEN_READWRITE - | GNUNET_DISK_OPEN_CREATE, - GNUNET_DISK_PERM_USER_READ | - GNUNET_DISK_PERM_USER_WRITE); - if (NULL == bf->fh) + if (GNUNET_YES == GNUNET_DISK_file_test (filename)) + bf->fh = + GNUNET_DISK_file_open (filename, + GNUNET_DISK_OPEN_READWRITE, + GNUNET_DISK_PERM_USER_READ | + GNUNET_DISK_PERM_USER_WRITE); + if (NULL != bf->fh) + { + /* 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; } - bf->filename = GNUNET_strdup (filename); - /* Alloc block */ - bf->bitArray = GNUNET_malloc_large (size); - if (bf->bitArray == NULL) + if (fsize == 0) { - if (bf->fh != NULL) + /* 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->filename); + 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 */ + bf->bitArray = GNUNET_malloc_large (size); + if (bf->bitArray == NULL) + { + if (bf->fh != NULL) + GNUNET_DISK_file_close (bf->fh); + GNUNET_free (bf->filename); + GNUNET_free (bf); + return NULL; + } 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) + { + 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 */ + for (i = 0; i < res; i++) { - 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); - } - if (res == 0) - break; /* is ok! we just did not use that many bits yet */ - for (i = 0; i < res; i++) - { - if ((rbuff[i] & 0x0F) != 0) - setBit (bf->bitArray, pos + i * 2); - if ((rbuff[i] & 0xF0) != 0) - setBit (bf->bitArray, pos + i * 2 + 1); - } - if (res < BUFFSIZE) - break; - pos += BUFFSIZE * 2; /* 2 bits per byte in the buffer */ + if ((rbuff[i] & 0x0F) != 0) + setBit (bf->bitArray, pos + i * 2); + if ((rbuff[i] & 0xF0) != 0) + setBit (bf->bitArray, pos + i * 2 + 1); } + if (res < BUFFSIZE) + break; + pos += BUFFSIZE * 2; /* 2 bits per byte in the buffer */ + } GNUNET_free (rbuff); return bf; } @@ -518,8 +602,8 @@ GNUNET_CONTAINER_bloomfilter_load (const char *filename, * @return the bloomfilter */ struct GNUNET_CONTAINER_BloomFilter * -GNUNET_CONTAINER_bloomfilter_init (const char *data, - size_t size, unsigned int k) +GNUNET_CONTAINER_bloomfilter_init (const char *data, size_t size, + unsigned int k) { struct GNUNET_CONTAINER_BloomFilter *bf; size_t ui; @@ -530,19 +614,19 @@ GNUNET_CONTAINER_bloomfilter_init (const char *data, while (ui < size) ui *= 2; if (size != ui) - { - GNUNET_break (0); - return NULL; - } + { + 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) - { - GNUNET_free (bf); - return NULL; - } + { + GNUNET_free (bf); + return NULL; + } bf->bitArraySize = size; bf->addressesPerElement = k; if (data != NULL) @@ -563,8 +647,9 @@ GNUNET_CONTAINER_bloomfilter_init (const char *data, * @return GNUNET_SYSERR if the data array is not big enough */ int -GNUNET_CONTAINER_bloomfilter_get_raw_data (const struct GNUNET_CONTAINER_BloomFilter - *bf, char *data, size_t size) +GNUNET_CONTAINER_bloomfilter_get_raw_data (const struct + GNUNET_CONTAINER_BloomFilter *bf, + char *data, size_t size) { if (NULL == bf) return GNUNET_SYSERR; @@ -574,6 +659,7 @@ GNUNET_CONTAINER_bloomfilter_get_raw_data (const struct GNUNET_CONTAINER_BloomFi return GNUNET_OK; } + /** * Free the space associated with a filter * in memory, flush to drive if needed (do not @@ -593,6 +679,7 @@ GNUNET_CONTAINER_bloomfilter_free (struct GNUNET_CONTAINER_BloomFilter *bf) GNUNET_free (bf); } + /** * Reset a bloom filter to empty. Clears the file on disk. * @@ -606,7 +693,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); } @@ -618,8 +705,8 @@ GNUNET_CONTAINER_bloomfilter_clear (struct GNUNET_CONTAINER_BloomFilter *bf) * @return GNUNET_YES if the element is in the filter, GNUNET_NO if not */ int -GNUNET_CONTAINER_bloomfilter_test (const struct GNUNET_CONTAINER_BloomFilter *bf, - const GNUNET_HashCode * e) +GNUNET_CONTAINER_bloomfilter_test (const struct GNUNET_CONTAINER_BloomFilter + *bf, const GNUNET_HashCode * e) { int res; @@ -630,6 +717,7 @@ GNUNET_CONTAINER_bloomfilter_test (const struct GNUNET_CONTAINER_BloomFilter *bf return res; } + /** * Add an element to the filter * @@ -640,7 +728,6 @@ void GNUNET_CONTAINER_bloomfilter_add (struct GNUNET_CONTAINER_BloomFilter *bf, const GNUNET_HashCode * e) { - if (NULL == bf) return; iterateBits (bf, &incrementBitCallback, bf, e); @@ -663,20 +750,20 @@ GNUNET_CONTAINER_bloomfilter_or (struct GNUNET_CONTAINER_BloomFilter *bf, { unsigned int i; unsigned int n; - unsigned long long* fc; - const unsigned long long* dc; + unsigned long long *fc; + const unsigned long long *dc; if (NULL == bf) return GNUNET_YES; if (bf->bitArraySize != size) return GNUNET_SYSERR; - fc = (unsigned long long*) bf->bitArray; - dc = (const unsigned long long*) data; + fc = (unsigned long long *) bf->bitArray; + dc = (const unsigned long long *) data; n = size / sizeof (unsigned long long); for (i = 0; i < n; i++) fc[i] |= dc[i]; - for (i = n * sizeof(unsigned long long); i < size; i++) + for (i = n * sizeof (unsigned long long); i < size; i++) bf->bitArray[i] |= data[i]; return GNUNET_OK; } @@ -693,25 +780,25 @@ GNUNET_CONTAINER_bloomfilter_or (struct GNUNET_CONTAINER_BloomFilter *bf, */ int GNUNET_CONTAINER_bloomfilter_or2 (struct GNUNET_CONTAINER_BloomFilter *bf, - const struct GNUNET_CONTAINER_BloomFilter *to_or, - size_t size) + const struct GNUNET_CONTAINER_BloomFilter + *to_or, size_t size) { unsigned int i; unsigned int n; - unsigned long long* fc; - const unsigned long long* dc; + unsigned long long *fc; + const unsigned long long *dc; if (NULL == bf) return GNUNET_YES; if (bf->bitArraySize != size) return GNUNET_SYSERR; - fc = (unsigned long long*) bf->bitArray; - dc = (const unsigned long long*) to_or->bitArray; + fc = (unsigned long long *) bf->bitArray; + dc = (const unsigned long long *) to_or->bitArray; n = size / sizeof (unsigned long long); for (i = 0; i < n; i++) fc[i] |= dc[i]; - for (i = n * sizeof(unsigned long long); i < size; i++) + for (i = n * sizeof (unsigned long long); i < size; i++) bf->bitArray[i] |= to_or->bitArray[i]; return GNUNET_OK; } @@ -747,8 +834,8 @@ GNUNET_CONTAINER_bloomfilter_remove (struct GNUNET_CONTAINER_BloomFilter *bf, void GNUNET_CONTAINER_bloomfilter_resize (struct GNUNET_CONTAINER_BloomFilter *bf, GNUNET_HashCodeIterator iterator, - void *iterator_cls, - size_t size, unsigned int k) + void *iterator_cls, size_t size, + unsigned int k) { GNUNET_HashCode hc; unsigned int i; @@ -763,7 +850,7 @@ GNUNET_CONTAINER_bloomfilter_resize (struct GNUNET_CONTAINER_BloomFilter *bf, 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); }