GNUnet  0.20.0
container_bloomfilter.c File Reference

data structure used to reduce disk accesses. More...

#include "platform.h"
#include "gnunet_util_lib.h"
Include dependency graph for container_bloomfilter.c:

Go to the source code of this file.

Data Structures

struct  GNUNET_CONTAINER_BloomFilter
 

Macros

#define LOG(kind, ...)    GNUNET_log_from (kind, "util-container-bloomfilter", __VA_ARGS__)
 
#define LOG_STRERROR(kind, syscall)    GNUNET_log_from_strerror (kind, "util-container-bloomfilter", syscall)
 
#define LOG_STRERROR_FILE(kind, syscall, filename)
 
#define BUFFSIZE   65536
 

Typedefs

typedef enum GNUNET_GenericReturnValue(* BitIterator) (void *cls, const struct GNUNET_CONTAINER_BloomFilter *bf, unsigned int bit)
 Iterator (callback) method to be called by the bloomfilter iterator on each bit that is to be set or tested for the key. More...
 

Functions

size_t GNUNET_CONTAINER_bloomfilter_get_element_addresses (const struct GNUNET_CONTAINER_BloomFilter *bf)
 Get the number of the addresses set per element in the bloom filter. More...
 
size_t GNUNET_CONTAINER_bloomfilter_get_size (const struct GNUNET_CONTAINER_BloomFilter *bf)
 Get size of the bloom filter. More...
 
struct GNUNET_CONTAINER_BloomFilterGNUNET_CONTAINER_bloomfilter_copy (const struct GNUNET_CONTAINER_BloomFilter *bf)
 Create a copy of a bloomfilter. More...
 
static void setBit (char *bitArray, unsigned int bitIdx)
 Sets a bit active in the bitArray. More...
 
static void clearBit (char *bitArray, unsigned int bitIdx)
 Clears a bit from bitArray. More...
 
static bool testBit (char *bitArray, unsigned int bitIdx)
 Checks if a bit is active in the bitArray. More...
 
static void incrementBit (char *bitArray, unsigned int bitIdx, const struct GNUNET_DISK_FileHandle *fh)
 Sets a bit active in the bitArray and increments bit-specific usage counter on disk (but only if the counter was below 4 bit max (==15)). More...
 
static void decrementBit (char *bitArray, unsigned int bitIdx, const struct GNUNET_DISK_FileHandle *fh)
 Clears a bit from bitArray if the respective usage counter on the disk hits/is zero. More...
 
static enum GNUNET_GenericReturnValue make_empty_file (const struct GNUNET_DISK_FileHandle *fh, size_t size)
 Creates a file filled with zeroes. More...
 
static void iterateBits (const struct GNUNET_CONTAINER_BloomFilter *bf, BitIterator callback, void *arg, const struct GNUNET_HashCode *key)
 Call an iterator for each bit that the bloomfilter must test or set for this element. More...
 
static enum GNUNET_GenericReturnValue incrementBitCallback (void *cls, const struct GNUNET_CONTAINER_BloomFilter *bf, unsigned int bit)
 Callback: increment bit. More...
 
static enum GNUNET_GenericReturnValue decrementBitCallback (void *cls, const struct GNUNET_CONTAINER_BloomFilter *bf, unsigned int bit)
 Callback: decrement bit. More...
 
static enum GNUNET_GenericReturnValue testBitCallback (void *cls, const struct GNUNET_CONTAINER_BloomFilter *bf, unsigned int bit)
 Callback: test if all bits are set. More...
 
struct GNUNET_CONTAINER_BloomFilterGNUNET_CONTAINER_bloomfilter_load (const char *filename, size_t size, unsigned int k)
 Load a Bloom filter from a file. More...
 
struct GNUNET_CONTAINER_BloomFilterGNUNET_CONTAINER_bloomfilter_init (const char *data, size_t size, unsigned int k)
 Create a Bloom filter from raw bits. More...
 
enum GNUNET_GenericReturnValue GNUNET_CONTAINER_bloomfilter_get_raw_data (const struct GNUNET_CONTAINER_BloomFilter *bf, char *data, size_t size)
 Copy the raw data of this Bloom filter into the given data array. More...
 
void GNUNET_CONTAINER_bloomfilter_free (struct GNUNET_CONTAINER_BloomFilter *bf)
 Free the space associated with a filter in memory, flush to drive if needed (do not free the space on the drive). More...
 
void GNUNET_CONTAINER_bloomfilter_clear (struct GNUNET_CONTAINER_BloomFilter *bf)
 Reset a Bloom filter to empty. More...
 
bool GNUNET_CONTAINER_bloomfilter_test (const struct GNUNET_CONTAINER_BloomFilter *bf, const struct GNUNET_HashCode *e)
 Test if an element is in the filter. More...
 
void GNUNET_CONTAINER_bloomfilter_add (struct GNUNET_CONTAINER_BloomFilter *bf, const struct GNUNET_HashCode *e)
 Add an element to the filter. More...
 
enum GNUNET_GenericReturnValue GNUNET_CONTAINER_bloomfilter_or (struct GNUNET_CONTAINER_BloomFilter *bf, const char *data, size_t size)
 "or" the entries of the given raw data array with the data of the given Bloom filter. More...
 
enum GNUNET_GenericReturnValue GNUNET_CONTAINER_bloomfilter_or2 (struct GNUNET_CONTAINER_BloomFilter *bf, const struct GNUNET_CONTAINER_BloomFilter *to_or)
 "or" the entries of the given raw data array with the data of the given Bloom filter. More...
 
void GNUNET_CONTAINER_bloomfilter_remove (struct GNUNET_CONTAINER_BloomFilter *bf, const struct GNUNET_HashCode *e)
 Remove an element from the filter. More...
 
void GNUNET_CONTAINER_bloomfilter_resize (struct GNUNET_CONTAINER_BloomFilter *bf, GNUNET_CONTAINER_HashCodeIterator iterator, void *iterator_cls, size_t size, unsigned int k)
 Resize a bloom filter. More...
 

Detailed Description

data structure used to reduce disk accesses.

The idea basically: Create a signature for each element in the database. Add those signatures to a bit array. When doing a lookup, check if the bit array matches the signature of the requested element. If yes, address the disk, otherwise return 'not found'.

A property of the bloom filter is that sometimes we will have a match even if the element is not on the disk (then we do an unnecessary disk access), but what's most important is that we never get a single "false negative".

To be able to delete entries from the bloom filter, we maintain a 4 bit counter in the file on the drive (we still use only one bit in memory).

Author
Igor Wronsky
Christian Grothoff

Definition in file container_bloomfilter.c.

Macro Definition Documentation

◆ LOG

#define LOG (   kind,
  ... 
)     GNUNET_log_from (kind, "util-container-bloomfilter", __VA_ARGS__)

Definition at line 46 of file container_bloomfilter.c.

◆ LOG_STRERROR

#define LOG_STRERROR (   kind,
  syscall 
)     GNUNET_log_from_strerror (kind, "util-container-bloomfilter", syscall)

Definition at line 49 of file container_bloomfilter.c.

◆ LOG_STRERROR_FILE

#define LOG_STRERROR_FILE (   kind,
  syscall,
  filename 
)
Value:
"util-container-bloomfilter", \
syscall, \
static char * filename
#define GNUNET_log_from_strerror_file(level, component, cmd, filename)
Log an error message at log-level 'level' that indicates a failure of the command 'cmd' with the mess...

Definition at line 52 of file container_bloomfilter.c.

◆ BUFFSIZE

#define BUFFSIZE   65536

Definition at line 295 of file container_bloomfilter.c.

Typedef Documentation

◆ BitIterator

typedef enum GNUNET_GenericReturnValue(* BitIterator) (void *cls, const struct GNUNET_CONTAINER_BloomFilter *bf, unsigned int bit)

Iterator (callback) method to be called by the bloomfilter iterator on each bit that is to be set or tested for the key.

Parameters
clsclosure
bfthe filter to manipulate
bitthe current bit
Returns
GNUNET_YES to continue, GNUNET_NO to stop early

Definition at line 239 of file container_bloomfilter.c.

Function Documentation

◆ setBit()

static void setBit ( char *  bitArray,
unsigned int  bitIdx 
)
static

Sets a bit active in the bitArray.

Increment bit-specific usage counter on disk only if below 4bit max (==15).

Parameters
bitArraymemory area to set the bit in
bitIdxwhich bit to set

Definition at line 125 of file container_bloomfilter.c.

127 {
128  size_t arraySlot;
129  unsigned int targetBit;
130 
131  arraySlot = bitIdx / 8;
132  targetBit = (1L << (bitIdx % 8));
133  bitArray[arraySlot] |= targetBit;
134 }

References GNUNET_CONTAINER_BloomFilter::bitArray.

Referenced by GNUNET_CONTAINER_bloomfilter_load(), and incrementBit().

Here is the caller graph for this function:

◆ clearBit()

static void clearBit ( char *  bitArray,
unsigned int  bitIdx 
)
static

Clears a bit from bitArray.

Bit is cleared from the array only if the respective usage counter on the disk hits/is zero.

Parameters
bitArraymemory area to set the bit in
bitIdxwhich bit to unset

Definition at line 145 of file container_bloomfilter.c.

146 {
147  size_t slot;
148  unsigned int targetBit;
149 
150  slot = bitIdx / 8;
151  targetBit = (1L << (bitIdx % 8));
152  bitArray[slot] = bitArray[slot] & (~targetBit);
153 }

References GNUNET_CONTAINER_BloomFilter::bitArray.

◆ testBit()

static bool testBit ( char *  bitArray,
unsigned int  bitIdx 
)
static

Checks if a bit is active in the bitArray.

Parameters
bitArraymemory area to set the bit in
bitIdxwhich bit to test
Returns
true if the bit is set, false if not.

Definition at line 164 of file container_bloomfilter.c.

166 {
167  size_t slot;
168  unsigned int targetBit;
169 
170  slot = bitIdx / 8;
171  targetBit = (1L << (bitIdx % 8));
172  if (bitArray[slot] & targetBit)
173  return true;
174  return false;
175 }

References GNUNET_CONTAINER_BloomFilter::bitArray.

◆ incrementBit()

static void incrementBit ( char *  bitArray,
unsigned int  bitIdx,
const struct GNUNET_DISK_FileHandle fh 
)
static

Sets a bit active in the bitArray and increments bit-specific usage counter on disk (but only if the counter was below 4 bit max (==15)).

Parameters
bitArraymemory area to set the bit in
bitIdxwhich bit to test
fhA file to keep the 4 bit address usage counters in

Definition at line 188 of file container_bloomfilter.c.

191 {
192  off_t fileSlot;
193  unsigned char value;
194  unsigned int high;
195  unsigned int low;
196  unsigned int targetLoc;
197 
198  setBit (bitArray,
199  bitIdx);
201  return;
202  /* Update the counter file on disk */
203  fileSlot = bitIdx / 2;
204  targetLoc = bitIdx % 2;
205 
206  GNUNET_assert (fileSlot ==
208  if (1 != GNUNET_DISK_file_read (fh, &value, 1))
209  value = 0;
210  low = value & 0xF;
211  high = (value & (~0xF)) >> 4;
212 
213  if (targetLoc == 0)
214  {
215  if (low < 0xF)
216  low++;
217  }
218  else
219  {
220  if (high < 0xF)
221  high++;
222  }
223  value = ((high << 4) | low);
224  GNUNET_assert (fileSlot ==
227 }
static void setBit(char *bitArray, unsigned int bitIdx)
Sets a bit active in the bitArray.
static char * value
Value of the record to add/remove.
static struct GNUNET_DISK_FileHandle * fh
File handle to STDIN, for reading restart/quit commands.
ssize_t GNUNET_DISK_file_write(const struct GNUNET_DISK_FileHandle *h, const void *buffer, size_t n)
Write a buffer to a file.
Definition: disk.c:686
off_t GNUNET_DISK_file_seek(const struct GNUNET_DISK_FileHandle *h, off_t offset, enum GNUNET_DISK_Seek whence)
Move the read/write pointer in a file.
Definition: disk.c:205
enum GNUNET_GenericReturnValue GNUNET_DISK_handle_invalid(const struct GNUNET_DISK_FileHandle *h)
Checks whether a handle is invalid.
Definition: disk.c:185
ssize_t GNUNET_DISK_file_read(const struct GNUNET_DISK_FileHandle *h, void *result, size_t len)
Read the contents of a binary file into a buffer.
Definition: disk.c:622
@ GNUNET_DISK_SEEK_SET
Seek an absolute position (from the start of the file).
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.

References GNUNET_CONTAINER_BloomFilter::bitArray, fh, GNUNET_assert, GNUNET_DISK_file_read(), GNUNET_DISK_file_seek(), GNUNET_DISK_file_write(), GNUNET_DISK_handle_invalid(), GNUNET_DISK_SEEK_SET, setBit(), and value.

Here is the call graph for this function:

◆ decrementBit()

static void decrementBit ( char *  bitArray,
unsigned int  bitIdx,
const struct GNUNET_DISK_FileHandle fh 
)
static

Clears a bit from bitArray if the respective usage counter on the disk hits/is zero.

Parameters
bitArraymemory area to set the bit in
bitIdxwhich bit to test
fhA file to keep the 4bit address usage counters in

Definition at line 239 of file container_bloomfilter.c.

242 {
243  off_t fileslot;
244  unsigned char value;
245  unsigned int high;
246  unsigned int low;
247  unsigned int targetLoc;
248 
250  return; /* cannot decrement! */
251  /* Each char slot in the counter file holds two 4 bit counters */
252  fileslot = bitIdx / 2;
253  targetLoc = bitIdx % 2;
254  if (GNUNET_SYSERR ==
256  {
258  return;
259  }
260  if (1 != GNUNET_DISK_file_read (fh, &value, 1))
261  value = 0;
262  low = value & 0xF;
263  high = (value & 0xF0) >> 4;
264 
265  /* decrement, but once we have reached the max, never go back! */
266  if (targetLoc == 0)
267  {
268  if ((low > 0) && (low < 0xF))
269  low--;
270  if (low == 0)
271  {
272  clearBit (bitArray, bitIdx);
273  }
274  }
275  else
276  {
277  if ((high > 0) && (high < 0xF))
278  high--;
279  if (high == 0)
280  {
281  clearBit (bitArray, bitIdx);
282  }
283  }
284  value = ((high << 4) | low);
285  if (GNUNET_SYSERR ==
287  {
289  return;
290  }
292 }
static void clearBit(char *bitArray, unsigned int bitIdx)
Clears a bit from bitArray.
@ GNUNET_SYSERR
#define GNUNET_log_strerror(level, cmd)
Log an error message at log-level 'level' that indicates a failure of the command 'cmd' with the mess...
@ GNUNET_ERROR_TYPE_ERROR

◆ make_empty_file()

static enum GNUNET_GenericReturnValue make_empty_file ( const struct GNUNET_DISK_FileHandle fh,
size_t  size 
)
static

Creates a file filled with zeroes.

Parameters
fhthe file handle
sizethe size of the file
Returns
GNUNET_OK if created ok, GNUNET_SYSERR otherwise

Definition at line 239 of file container_bloomfilter.c.

307 {
308  char buffer[BUFFSIZE];
309  size_t bytesleft = size;
310  int res = 0;
311 
313  return GNUNET_SYSERR;
314  memset (buffer, 0, sizeof(buffer));
316  while (bytesleft > 0)
317  {
318  if (bytesleft > sizeof(buffer))
319  {
320  res = GNUNET_DISK_file_write (fh, buffer, sizeof(buffer));
321  if (res >= 0)
322  bytesleft -= res;
323  }
324  else
325  {
326  res = GNUNET_DISK_file_write (fh, buffer, bytesleft);
327  if (res >= 0)
328  bytesleft -= res;
329  }
330  if (GNUNET_SYSERR == res)
331  return GNUNET_SYSERR;
332  }
333  return GNUNET_OK;
334 }
#define BUFFSIZE
static int res
@ GNUNET_OK
static unsigned int size
Size of the "table".
Definition: peer.c:68

Referenced by GNUNET_CONTAINER_bloomfilter_clear(), GNUNET_CONTAINER_bloomfilter_load(), and GNUNET_CONTAINER_bloomfilter_resize().

Here is the caller graph for this function:

◆ iterateBits()

static void iterateBits ( const struct GNUNET_CONTAINER_BloomFilter bf,
BitIterator  callback,
void *  arg,
const struct GNUNET_HashCode key 
)
static

Call an iterator for each bit that the bloomfilter must test or set for this element.

Parameters
bfthe filter
callbackthe method to call
argextra argument to callback
keythe key for which we iterate over the BF bits

Definition at line 365 of file container_bloomfilter.c.

369 {
370  struct GNUNET_HashCode tmp = *key;
371  int bitCount;
372  unsigned int slot = 0;
373 
374  bitCount = bf->addressesPerElement;
375  GNUNET_assert (bf->bitArraySize > 0);
376  GNUNET_assert (bf->bitArraySize * 8LL > bf->bitArraySize);
377  while (bitCount > 0)
378  {
379  while ( (0 != bitCount) &&
380  (slot < (sizeof(struct GNUNET_HashCode) / sizeof(uint32_t))) )
381  {
382  if (GNUNET_YES !=
383  callback (arg,
384  bf,
385  ntohl ((((uint32_t *) &tmp)[slot]))
386  % ((bf->bitArraySize * 8LL))))
387  return;
388  slot++;
389  bitCount--;
390  }
391  if (0 == bitCount)
392  break;
393  GNUNET_CRYPTO_hash (&tmp,
394  sizeof(tmp),
395  &tmp);
396  slot = 0;
397  }
398 }
struct GNUNET_HashCode key
The key used in the DHT.
void GNUNET_CRYPTO_hash(const void *block, size_t size, struct GNUNET_HashCode *ret)
Compute hash of a given block.
Definition: crypto_hash.c:41
@ GNUNET_YES
size_t bitArraySize
Size of bitArray in bytes.
unsigned int addressesPerElement
How many bits we set for each stored element.
A 512-bit hashcode.

Referenced by GNUNET_CONTAINER_bloomfilter_add(), GNUNET_CONTAINER_bloomfilter_remove(), and GNUNET_CONTAINER_bloomfilter_test().

Here is the caller graph for this function:

◆ incrementBitCallback()

static enum GNUNET_GenericReturnValue incrementBitCallback ( void *  cls,
const struct GNUNET_CONTAINER_BloomFilter bf,
unsigned int  bit 
)
static

Callback: increment bit.

Parameters
clspointer to writeable form of bf
bfthe filter to manipulate
bitthe bit to increment
Returns
GNUNET_YES

Definition at line 365 of file container_bloomfilter.c.

413 {
414  struct GNUNET_CONTAINER_BloomFilter *b = cls;
415 
417  bit,
418  bf->fh);
419  return GNUNET_YES;
420 }
static void incrementBit(char *bitArray, unsigned int bitIdx, const struct GNUNET_DISK_FileHandle *fh)
Sets a bit active in the bitArray and increments bit-specific usage counter on disk (but only if the ...
struct GNUNET_DISK_FileHandle * fh
The bit counter file on disk.
char * bitArray
The actual bloomfilter bit array.

Referenced by GNUNET_CONTAINER_bloomfilter_add().

Here is the caller graph for this function:

◆ decrementBitCallback()

static enum GNUNET_GenericReturnValue decrementBitCallback ( void *  cls,
const struct GNUNET_CONTAINER_BloomFilter bf,
unsigned int  bit 
)
static

Callback: decrement bit.

Parameters
clspointer to writeable form of bf
bfthe filter to manipulate
bitthe bit to decrement
Returns
GNUNET_YES

Definition at line 365 of file container_bloomfilter.c.

435 {
436  struct GNUNET_CONTAINER_BloomFilter *b = cls;
437 
439  bit,
440  bf->fh);
441  return GNUNET_YES;
442 }
static void decrementBit(char *bitArray, unsigned int bitIdx, const struct GNUNET_DISK_FileHandle *fh)
Clears a bit from bitArray if the respective usage counter on the disk hits/is zero.

References GNUNET_CONTAINER_BloomFilter::addressesPerElement, find_typedefs::arg, GNUNET_CONTAINER_BloomFilter::bitArraySize, GNUNET_assert, GNUNET_CRYPTO_hash(), GNUNET_YES, and key.

Referenced by GNUNET_CONTAINER_bloomfilter_remove().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ testBitCallback()

static enum GNUNET_GenericReturnValue testBitCallback ( void *  cls,
const struct GNUNET_CONTAINER_BloomFilter bf,
unsigned int  bit 
)
static

Callback: test if all bits are set.

Parameters
clspointer set to false if bit is not set
bfthe filter
bitthe bit to test
Returns
GNUNET_YES if the bit is set, GNUNET_NO if not

Definition at line 365 of file container_bloomfilter.c.

457 {
458  bool *arg = cls;
459 
460  if (! testBit (bf->bitArray, bit))
461  {
462  *arg = false;
463  return GNUNET_NO;
464  }
465  return GNUNET_YES;
466 }
static bool testBit(char *bitArray, unsigned int bitIdx)
Checks if a bit is active in the bitArray.
@ GNUNET_NO

Referenced by GNUNET_CONTAINER_bloomfilter_test().

Here is the caller graph for this function: