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_BloomFilter *	GNUNET_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_BloomFilter *	GNUNET_CONTAINER_bloomfilter_load (const char *filename, size_t size, unsigned int k)
	Load a Bloom filter from a file. More...
struct GNUNET_CONTAINER_BloomFilter *	GNUNET_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:

  GNUNET_log_from_strerror_file (kind,                         \
                                 "util-container-bloomfilter", \
                                 syscall,                      \
                                 filename)

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

cls	closure
bf	the filter to manipulate
bit	the 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

bitArray	memory area to set the bit in
bitIdx	which bit to set

Definition at line 125 of file container_bloomfilter.c.

{
  size_t arraySlot;
  unsigned int targetBit;
 
  arraySlot = bitIdx / 8;
  targetBit = (1L << (bitIdx % 8));
  bitArray[arraySlot] |= targetBit;
}

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

bitArray	memory area to set the bit in
bitIdx	which bit to unset

Definition at line 145 of file container_bloomfilter.c.

{
  size_t slot;
  unsigned int targetBit;
 
  slot = bitIdx / 8;
  targetBit = (1L << (bitIdx % 8));
  bitArray[slot] = bitArray[slot] & (~targetBit);
}

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

bitArray	memory area to set the bit in
bitIdx	which bit to test

Returns

true if the bit is set, false if not.

Definition at line 164 of file container_bloomfilter.c.

{
  size_t slot;
  unsigned int targetBit;
 
  slot = bitIdx / 8;
  targetBit = (1L << (bitIdx % 8));
  if (bitArray[slot] & targetBit)
    return true;
  return false;
}

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

bitArray	memory area to set the bit in
bitIdx	which bit to test
fh	A file to keep the 4 bit address usage counters in

Definition at line 188 of file container_bloomfilter.c.

{
  off_t fileSlot;
  unsigned char value;
  unsigned int high;
  unsigned int low;
  unsigned int targetLoc;
 
  setBit (bitArray,
          bitIdx);
  if (GNUNET_DISK_handle_invalid (fh))
    return;
  /* Update the counter file on disk */
  fileSlot = bitIdx / 2;
  targetLoc = bitIdx % 2;
 
  GNUNET_assert (fileSlot ==
                 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++;
  }
  else
  {
    if (high < 0xF)
      high++;
  }
  value = ((high << 4) | low);
  GNUNET_assert (fileSlot ==
                 GNUNET_DISK_file_seek (fh, fileSlot, GNUNET_DISK_SEEK_SET));
  GNUNET_assert (1 == GNUNET_DISK_file_write (fh, &value, 1));
}

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

bitArray	memory area to set the bit in
bitIdx	which bit to test
fh	A file to keep the 4bit address usage counters in

Definition at line 239 of file container_bloomfilter.c.

{
  off_t fileslot;
  unsigned char value;
  unsigned int high;
  unsigned int low;
  unsigned int targetLoc;
 
  if (GNUNET_DISK_handle_invalid (fh))
    return; /* cannot decrement! */
  /* Each char slot in the counter file holds two 4 bit counters */
  fileslot = bitIdx / 2;
  targetLoc = bitIdx % 2;
  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;
  high = (value & 0xF0) >> 4;
 
  /* decrement, but once we have reached the max, never go back! */
  if (targetLoc == 0)
  {
    if ((low > 0) && (low < 0xF))
      low--;
    if (low == 0)
    {
      clearBit (bitArray, bitIdx);
    }
  }
  else
  {
    if ((high > 0) && (high < 0xF))
      high--;
    if (high == 0)
    {
      clearBit (bitArray, bitIdx);
    }
  }
  value = ((high << 4) | low);
  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));
}

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

fh	the file handle
size	the size of the file

Returns

GNUNET_OK if created ok, GNUNET_SYSERR otherwise

Definition at line 239 of file container_bloomfilter.c.

{
  char buffer[BUFFSIZE];
  size_t bytesleft = size;
  int res = 0;
 
  if (GNUNET_DISK_handle_invalid (fh))
    return GNUNET_SYSERR;
  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
    {
      res = GNUNET_DISK_file_write (fh, buffer, bytesleft);
      if (res >= 0)
        bytesleft -= res;
    }
    if (GNUNET_SYSERR == res)
      return GNUNET_SYSERR;
  }
  return GNUNET_OK;
}

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

bf	the filter
callback	the method to call
arg	extra argument to callback
key	the key for which we iterate over the BF bits

Definition at line 365 of file container_bloomfilter.c.

{
  struct GNUNET_HashCode tmp = *key;
  int bitCount;
  unsigned int slot = 0;
 
  bitCount = bf->addressesPerElement;
  GNUNET_assert (bf->bitArraySize > 0);
  GNUNET_assert (bf->bitArraySize * 8LL > bf->bitArraySize);
  while (bitCount > 0)
  {
    while ( (0 != bitCount) &&
            (slot < (sizeof(struct GNUNET_HashCode) / sizeof(uint32_t))) )
    {
      if (GNUNET_YES !=
          callback (arg,
                    bf,
                    ntohl ((((uint32_t *) &tmp)[slot]))
                    % ((bf->bitArraySize * 8LL))))
        return;
      slot++;
      bitCount--;
    }
    if (0 == bitCount)
      break;
    GNUNET_CRYPTO_hash (&tmp,
                        sizeof(tmp),
                        &tmp);
    slot = 0;
  }
}

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

cls	pointer to writeable form of bf
bf	the filter to manipulate
bit	the bit to increment

Returns

GNUNET_YES

Definition at line 365 of file container_bloomfilter.c.

{
  struct GNUNET_CONTAINER_BloomFilter *b = cls;
 
  incrementBit (b->bitArray,
                bit,
                bf->fh);
  return GNUNET_YES;
}

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

cls	pointer to writeable form of bf
bf	the filter to manipulate
bit	the bit to decrement

Returns

GNUNET_YES

Definition at line 365 of file container_bloomfilter.c.

{
  struct GNUNET_CONTAINER_BloomFilter *b = cls;
 
  decrementBit (b->bitArray,
                bit,
                bf->fh);
  return GNUNET_YES;
}

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

cls	pointer set to false if bit is not set
bf	the filter
bit	the bit to test

Returns

GNUNET_YES if the bit is set, GNUNET_NO if not

Definition at line 365 of file container_bloomfilter.c.

{
  bool *arg = cls;
 
  if (! testBit (bf->bitArray, bit))
  {
    *arg = false;
    return GNUNET_NO;
  }
  return GNUNET_YES;
}

Referenced by GNUNET_CONTAINER_bloomfilter_test().

Here is the caller graph for this function: