X-Git-Url: https://git.librecmc.org/?a=blobdiff_plain;f=src%2Futil%2Fcontainer_bloomfilter.c;h=d6c2cb8b9cddf385d6485c0c67fdcabb7be1186b;hb=72c8645af31896829b674b575c5375706f362a30;hp=a33b619ffbf9b2fa0bb82024218651d59c618f65;hpb=d9d94d0e53d26af75ec8241383d166544ebd79f3;p=oweals%2Fgnunet.git diff --git a/src/util/container_bloomfilter.c b/src/util/container_bloomfilter.c index a33b619ff..d6c2cb8b9 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 @@ -89,8 +89,8 @@ struct GNUNET_CONTAINER_BloomFilter * @return number of bytes used for the data of the bloom filter */ size_t -GNUNET_CONTAINER_bloomfilter_get_size (const struct - GNUNET_CONTAINER_BloomFilter *bf) +GNUNET_CONTAINER_bloomfilter_get_size (const struct GNUNET_CONTAINER_BloomFilter + *bf) { if (bf == NULL) return 0; @@ -106,10 +106,10 @@ GNUNET_CONTAINER_bloomfilter_get_size (const struct */ struct GNUNET_CONTAINER_BloomFilter * GNUNET_CONTAINER_bloomfilter_copy (const struct GNUNET_CONTAINER_BloomFilter - *bf) + *bf) { return GNUNET_CONTAINER_bloomfilter_init (bf->bitArray, bf->bitArraySize, - bf->addressesPerElement); + bf->addressesPerElement); } @@ -181,9 +181,9 @@ testBit (char *bitArray, unsigned int bitIdx) */ static void incrementBit (char *bitArray, unsigned int bitIdx, - const struct GNUNET_DISK_FileHandle *fh) + const struct GNUNET_DISK_FileHandle *fh) { - off_t fileSlot; + OFF_T fileSlot; unsigned char value; unsigned int high; unsigned int low; @@ -197,25 +197,25 @@ incrementBit (char *bitArray, unsigned int bitIdx, targetLoc = bitIdx % 2; GNUNET_assert (fileSlot == - GNUNET_DISK_file_seek (fh, fileSlot, GNUNET_DISK_SEEK_SET)); + GNUNET_DISK_file_seek (fh, fileSlot, GNUNET_DISK_SEEK_SET)); if (1 != GNUNET_DISK_file_read (fh, &value, 1)) value = 0; low = value & 0xF; 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_DISK_file_seek (fh, fileSlot, GNUNET_DISK_SEEK_SET)); GNUNET_assert (1 == GNUNET_DISK_file_write (fh, &value, 1)); } @@ -229,20 +229,24 @@ incrementBit (char *bitArray, unsigned int bitIdx, */ static void decrementBit (char *bitArray, unsigned int bitIdx, - const struct GNUNET_DISK_FileHandle *fh) + const struct GNUNET_DISK_FileHandle *fh) { - off_t fileSlot; + OFF_T fileslot; unsigned char value; unsigned int high; unsigned int low; unsigned int targetLoc; if (GNUNET_DISK_handle_invalid (fh)) - return; /* cannot decrement! */ + return; /* cannot decrement! */ /* Each char slot in the counter file holds two 4 bit counters */ - fileSlot = bitIdx / 2; + fileslot = bitIdx / 2; targetLoc = bitIdx % 2; - GNUNET_DISK_file_seek (fh, fileSlot, GNUNET_DISK_SEEK_SET); + if (GNUNET_SYSERR == GNUNET_DISK_file_seek (fh, fileslot, GNUNET_DISK_SEEK_SET)) + { + GNUNET_log_strerror (GNUNET_ERROR_TYPE_ERROR, "seek"); + return; + } if (1 != GNUNET_DISK_file_read (fh, &value, 1)) value = 0; low = value & 0xF; @@ -250,25 +254,29 @@ 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); + if (GNUNET_SYSERR == GNUNET_DISK_file_seek (fh, fileslot, GNUNET_DISK_SEEK_SET)) + { + GNUNET_log_strerror (GNUNET_ERROR_TYPE_ERROR, "seek"); + return; + } GNUNET_assert (1 == GNUNET_DISK_file_write (fh, &value, 1)); } @@ -282,33 +290,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; } @@ -325,8 +333,8 @@ makeEmptyFile (const struct GNUNET_DISK_FileHandle *fh, size_t size) * @return GNUNET_YES to continue, GNUNET_NO to stop early */ typedef int (*BitIterator) (void *cls, - const struct GNUNET_CONTAINER_BloomFilter * bf, - unsigned int bit); + const struct GNUNET_CONTAINER_BloomFilter * bf, + unsigned int bit); /** @@ -340,9 +348,9 @@ typedef int (*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 struct GNUNET_HashCode *key) { - GNUNET_HashCode tmp[2]; + struct GNUNET_HashCode tmp[2]; int bitCount; unsigned int round; unsigned int slot = 0; @@ -350,28 +358,30 @@ iterateBits (const struct GNUNET_CONTAINER_BloomFilter *bf, 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 (struct GNUNET_HashCode) / sizeof (uint32_t))) { - while (slot < (sizeof (GNUNET_HashCode) / sizeof (uint32_t))) - { - 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; - } + if (GNUNET_YES != + callback (arg, bf, + ntohl ((((uint32_t *) & tmp[round & 1])[slot])) % + ((bf->bitArraySize * 8LL)))) + return; + slot++; + bitCount--; + if (bitCount == 0) + break; } + if (bitCount > 0) + { + GNUNET_CRYPTO_hash (&tmp[round & 1], sizeof (struct GNUNET_HashCode), + &tmp[(round + 1) & 1]); + round++; + slot = 0; + } + } } @@ -384,9 +394,8 @@ iterateBits (const struct GNUNET_CONTAINER_BloomFilter *bf, * @return GNUNET_YES */ static int -incrementBitCallback (void *cls, - const struct GNUNET_CONTAINER_BloomFilter *bf, - unsigned int bit) +incrementBitCallback (void *cls, const struct GNUNET_CONTAINER_BloomFilter *bf, + unsigned int bit) { struct GNUNET_CONTAINER_BloomFilter *b = cls; @@ -404,9 +413,8 @@ incrementBitCallback (void *cls, * @return GNUNET_YES */ static int -decrementBitCallback (void *cls, - const struct GNUNET_CONTAINER_BloomFilter *bf, - unsigned int bit) +decrementBitCallback (void *cls, const struct GNUNET_CONTAINER_BloomFilter *bf, + unsigned int bit) { struct GNUNET_CONTAINER_BloomFilter *b = cls; @@ -425,15 +433,15 @@ decrementBitCallback (void *cls, */ static int testBitCallback (void *cls, const struct GNUNET_CONTAINER_BloomFilter *bf, - unsigned int bit) + unsigned int bit) { int *arg = cls; if (GNUNET_NO == testBit (bf->bitArray, bit)) - { - *arg = GNUNET_NO; - return GNUNET_NO; - } + { + *arg = GNUNET_NO; + return GNUNET_NO; + } return GNUNET_YES; } @@ -444,20 +452,23 @@ 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 */ struct GNUNET_CONTAINER_BloomFilter * GNUNET_CONTAINER_bloomfilter_load (const char *filename, size_t size, - unsigned int k) + 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)) @@ -465,63 +476,122 @@ 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 */ + 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) { - int res; - - res = GNUNET_DISK_file_read (bf->fh, rbuff, BUFFSIZE); - if (res == -1) - { - 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 */ + 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++) + { + 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; } @@ -542,36 +612,25 @@ GNUNET_CONTAINER_bloomfilter_load (const char *filename, size_t size, */ struct GNUNET_CONTAINER_BloomFilter * GNUNET_CONTAINER_bloomfilter_init (const char *data, size_t size, - unsigned int k) + 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) - { - GNUNET_free (bf); - return 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; } @@ -587,8 +646,8 @@ GNUNET_CONTAINER_bloomfilter_init (const char *data, size_t size, */ int GNUNET_CONTAINER_bloomfilter_get_raw_data (const struct - GNUNET_CONTAINER_BloomFilter *bf, - char *data, size_t size) + GNUNET_CONTAINER_BloomFilter *bf, + char *data, size_t size) { if (NULL == bf) return GNUNET_SYSERR; @@ -632,7 +691,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); } @@ -645,7 +704,7 @@ GNUNET_CONTAINER_bloomfilter_clear (struct GNUNET_CONTAINER_BloomFilter *bf) */ int GNUNET_CONTAINER_bloomfilter_test (const struct GNUNET_CONTAINER_BloomFilter - *bf, const GNUNET_HashCode * e) + *bf, const struct GNUNET_HashCode * e) { int res; @@ -665,7 +724,7 @@ GNUNET_CONTAINER_bloomfilter_test (const struct GNUNET_CONTAINER_BloomFilter */ void GNUNET_CONTAINER_bloomfilter_add (struct GNUNET_CONTAINER_BloomFilter *bf, - const GNUNET_HashCode * e) + const struct GNUNET_HashCode * e) { if (NULL == bf) return; @@ -685,7 +744,7 @@ GNUNET_CONTAINER_bloomfilter_add (struct GNUNET_CONTAINER_BloomFilter *bf, */ int GNUNET_CONTAINER_bloomfilter_or (struct GNUNET_CONTAINER_BloomFilter *bf, - const char *data, size_t size) + const char *data, size_t size) { unsigned int i; unsigned int n; @@ -719,8 +778,8 @@ 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; @@ -750,7 +809,7 @@ GNUNET_CONTAINER_bloomfilter_or2 (struct GNUNET_CONTAINER_BloomFilter *bf, */ void GNUNET_CONTAINER_bloomfilter_remove (struct GNUNET_CONTAINER_BloomFilter *bf, - const GNUNET_HashCode * e) + const struct GNUNET_HashCode * e) { if (NULL == bf) return; @@ -772,24 +831,23 @@ 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) + GNUNET_HashCodeIterator iterator, + void *iterator_cls, size_t size, + unsigned int k) { - GNUNET_HashCode hc; + struct GNUNET_HashCode hc; unsigned int i; GNUNET_free (bf->bitArray); i = 1; while (i < size) i *= 2; - size = i; /* make sure it's a power of 2 */ + size = i; /* make sure it's a power of 2 */ 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); }