Bloom filter

Probabilistic set tests. More...

Collaboration diagram for Bloom filter:

Typedefs
typedef int(*	GNUNET_CONTAINER_HashCodeIterator) (void *cls, struct GNUNET_HashCode *next)
	Iterator over struct GNUNET_HashCode. More...

Functions
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...
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...
void	GNUNET_CONTAINER_bloomfilter_remove (struct GNUNET_CONTAINER_BloomFilter *bf, const struct GNUNET_HashCode *e)
	Remove an element from the filter. More...
struct GNUNET_CONTAINER_BloomFilter *	GNUNET_CONTAINER_bloomfilter_copy (const struct GNUNET_CONTAINER_BloomFilter *bf)
	Create a copy of a bloomfilter. 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...
size_t	GNUNET_CONTAINER_bloomfilter_get_size (const struct GNUNET_CONTAINER_BloomFilter *bf)
	Get size of the bloom filter. More...
void	GNUNET_CONTAINER_bloomfilter_clear (struct GNUNET_CONTAINER_BloomFilter *bf)
	Reset a Bloom filter to empty. 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_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

Probabilistic set tests.

Typedef Documentation

GNUNET_CONTAINER_HashCodeIterator

typedef int(* GNUNET_CONTAINER_HashCodeIterator) (void *cls, struct GNUNET_HashCode *next)

Iterator over struct GNUNET_HashCode.

Parameters

cls	closure
next	set to the next hash code

Returns

GNUNET_YES if next was updated GNUNET_NO if there are no more entries

Definition at line 130 of file gnunet_container_lib.h.

Function Documentation

GNUNET_CONTAINER_bloomfilter_load()

struct GNUNET_CONTAINER_BloomFilter * GNUNET_CONTAINER_bloomfilter_load	(	const char *	filename,
		size_t	size,
		unsigned int	k
	)

Load a Bloom filter from a file.

Parameters

filename	the name of the file (or the prefix)
size	the size of the bloom-filter (number of bytes of storage space to use); will be rounded up to next power of 2
k	the number of GNUNET_CRYPTO_hash-functions to apply per element (number of bits set per element in the set)

Returns

the bloomfilter

Definition at line 472 of file container_bloomfilter.c.

{
  struct GNUNET_CONTAINER_BloomFilter *bf;
  char *rbuff;
  off_t pos;
  int i;
  size_t ui;
  off_t fsize;
  int must_read;
 
  GNUNET_assert (NULL != filename);
  if ((k == 0) || (size == 0))
    return NULL;
  if (size < BUFFSIZE)
    size = BUFFSIZE;
  ui = 1;
  while ((ui < size) && (ui * 2 > ui))
    ui *= 2;
  size = ui; /* make sure it's a power of 2 */
 
  bf = GNUNET_new (struct GNUNET_CONTAINER_BloomFilter);
  /* Try to open a bloomfilter file */
  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;
    }
    if (0 == fsize)
    {
      /* 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 != ((off_t) 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 (NULL == bf->bitArray)
  {
    if (NULL != bf->fh)
      GNUNET_DISK_file_close (bf->fh);
    GNUNET_free (bf->filename);
    GNUNET_free (bf);
    return NULL;
  }
  bf->bitArraySize = size;
  bf->addressesPerElement = k;
  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 < ((off_t) 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++)
    {
      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;
}

References _, GNUNET_CONTAINER_BloomFilter::addressesPerElement, GNUNET_CONTAINER_BloomFilter::bitArray, GNUNET_CONTAINER_BloomFilter::bitArraySize, BUFFSIZE, GNUNET_CONTAINER_BloomFilter::fh, filename, GNUNET_CONTAINER_BloomFilter::filename, GNUNET_assert, GNUNET_DISK_file_close(), GNUNET_DISK_file_handle_size(), GNUNET_DISK_file_open(), GNUNET_DISK_file_read(), GNUNET_DISK_file_test(), GNUNET_DISK_OPEN_CREATE, GNUNET_DISK_OPEN_READWRITE, GNUNET_DISK_PERM_USER_READ, GNUNET_DISK_PERM_USER_WRITE, GNUNET_ERROR_TYPE_ERROR, GNUNET_ERROR_TYPE_WARNING, GNUNET_free, GNUNET_log, GNUNET_log_strerror, GNUNET_malloc, GNUNET_malloc_large, GNUNET_new, GNUNET_NO, GNUNET_OK, GNUNET_strdup, GNUNET_YES, LOG_STRERROR_FILE, make_empty_file(), res, setBit(), and size.

Referenced by GNUNET_DATACACHE_create(), and run().

Here is the call graph for this function:

Here is the caller graph for this function:

GNUNET_CONTAINER_bloomfilter_init()

struct GNUNET_CONTAINER_BloomFilter * GNUNET_CONTAINER_bloomfilter_init	(	const char *	data,
		size_t	size,
		unsigned int	k
	)

Create a Bloom filter from raw bits.

Parameters

data	the raw bits in memory (maybe NULL, in which case all bits should be considered to be zero).
size	the size of the bloom-filter (number of bytes of storage space to use); also size of data – unless data is NULL. Must be a power of 2.
k	the number of GNUNET_CRYPTO_hash-functions to apply per element (number of bits set per element in the set)

Returns

the bloomfilter

Definition at line 613 of file container_bloomfilter.c.

{
  struct GNUNET_CONTAINER_BloomFilter *bf;
 
  if ((0 == k) || (0 == size))
    return NULL;
  bf = GNUNET_new (struct GNUNET_CONTAINER_BloomFilter);
  bf->filename = NULL;
  bf->fh = NULL;
  bf->bitArray = GNUNET_malloc_large (size);
  if (NULL == bf->bitArray)
  {
    GNUNET_free (bf);
    return NULL;
  }
  bf->bitArraySize = size;
  bf->addressesPerElement = k;
  if (NULL != data)
    GNUNET_memcpy (bf->bitArray, data, size);
  return bf;
}

References GNUNET_CONTAINER_BloomFilter::addressesPerElement, GNUNET_CONTAINER_BloomFilter::bitArray, GNUNET_CONTAINER_BloomFilter::bitArraySize, data, GNUNET_CONTAINER_BloomFilter::fh, GNUNET_CONTAINER_BloomFilter::filename, GNUNET_free, GNUNET_malloc_large, GNUNET_memcpy, GNUNET_new, and size.

Referenced by GNUNET_BLOCK_GROUP_bf_create(), GNUNET_CONTAINER_bloomfilter_copy(), GNUNET_DATACACHE_create(), handle_dht_local_put(), handle_dht_p2p_get(), handle_dht_p2p_put(), handle_intersection_p2p_bf(), run(), send_bloomfilter(), send_find_peer_message(), setup_filter(), and transmit_request().

Here is the caller graph for this function:

GNUNET_CONTAINER_bloomfilter_get_raw_data()

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.

Parameters

data	where to write the data
size	the size of the given data array

Returns

GNUNET_SYSERR if the data array of the wrong size

Definition at line 639 of file container_bloomfilter.c.

{
  if (NULL == bf)
    return GNUNET_SYSERR;
  if (bf->bitArraySize != size)
    return GNUNET_SYSERR;
  GNUNET_memcpy (data, bf->bitArray, size);
  return GNUNET_OK;
}

References GNUNET_CONTAINER_BloomFilter::bitArray, GNUNET_CONTAINER_BloomFilter::bitArraySize, data, GNUNET_memcpy, GNUNET_OK, GNUNET_SYSERR, and size.

Referenced by bf_group_serialize_cb(), GDS_NEIGHBOURS_handle_get(), GDS_NEIGHBOURS_handle_put(), and send_bloomfilter().

Here is the caller graph for this function:

GNUNET_CONTAINER_bloomfilter_test()

bool GNUNET_CONTAINER_bloomfilter_test	(	const struct GNUNET_CONTAINER_BloomFilter *	bf,
		const struct GNUNET_HashCode *	e
	)

Test if an element is in the filter.

Parameters

e	the element
bf	the filter

Returns

true if the element is in the filter, false if not

Definition at line 679 of file container_bloomfilter.c.

{
  bool res;
 
  if (NULL == bf)
    return true;
  res = true;
  iterateBits (bf,
               &testBitCallback,
               &res,
               e);
  return res;
}

References iterateBits(), res, and testBitCallback().

Referenced by filtered_map_initialization(), find_advertisable_hello(), GDS_am_closest_peer(), GDS_NEIGHBOURS_handle_get(), GDS_NEIGHBOURS_handle_put(), get_target_peers(), GNUNET_BLOCK_GROUP_bf_test_and_set(), GNUNET_DATACACHE_get(), handle_dht_p2p_get(), handle_dht_p2p_put(), handle_get_key(), handle_put(), iterator_bf_reduce(), and select_peer().

Here is the call graph for this function:

Here is the caller graph for this function:

GNUNET_CONTAINER_bloomfilter_add()

void GNUNET_CONTAINER_bloomfilter_add	(	struct GNUNET_CONTAINER_BloomFilter *	bf,
		const struct GNUNET_HashCode *	e
	)

Add an element to the filter.

Parameters

bf	the filter
e	the element

Definition at line 697 of file container_bloomfilter.c.

{
  if (NULL == bf)
    return;
  iterateBits (bf,
               &incrementBitCallback,
               bf,
               e);
}

References incrementBitCallback(), and iterateBits().

Referenced by add_key_to_bloomfilter(), bf_group_mark_seen_cb(), GDS_NEIGHBOURS_handle_get(), GDS_NEIGHBOURS_handle_put(), get_target_peers(), GNUNET_BLOCK_GROUP_bf_test_and_set(), GNUNET_CONTAINER_bloomfilter_resize(), GNUNET_DATACACHE_put(), iterator_bf_create(), put_continuation(), schedule_next_hello(), and setup_filter().

Here is the call graph for this function:

Here is the caller graph for this function:

GNUNET_CONTAINER_bloomfilter_remove()

void GNUNET_CONTAINER_bloomfilter_remove	(	struct GNUNET_CONTAINER_BloomFilter *	bf,
		const struct GNUNET_HashCode *	e
	)

Remove an element from the filter.

Parameters

bf	the filter
e	the element to remove

Definition at line 767 of file container_bloomfilter.c.

{
  if (NULL == bf)
    return;
  if (NULL == bf->filename)
    return;
  iterateBits (bf,
               &decrementBitCallback,
               bf,
               e);
}

References decrementBitCallback(), GNUNET_CONTAINER_BloomFilter::filename, and iterateBits().

Referenced by env_delete_notify(), expired_processor(), quota_processor(), and remove_continuation().

Here is the call graph for this function:

Here is the caller graph for this function:

GNUNET_CONTAINER_bloomfilter_copy()

struct GNUNET_CONTAINER_BloomFilter * GNUNET_CONTAINER_bloomfilter_copy

(

const struct GNUNET_CONTAINER_BloomFilter *

bf

)

Create a copy of a bloomfilter.

Parameters

bf	the filter

Returns

copy of bf

Definition at line 108 of file container_bloomfilter.c.

{
  return GNUNET_CONTAINER_bloomfilter_init (bf->bitArray,
                                            bf->bitArraySize,
                                            bf->addressesPerElement);
}

References GNUNET_CONTAINER_BloomFilter::addressesPerElement, GNUNET_CONTAINER_BloomFilter::bitArray, GNUNET_CONTAINER_BloomFilter::bitArraySize, and GNUNET_CONTAINER_bloomfilter_init().

Here is the call graph for this function:

GNUNET_CONTAINER_bloomfilter_free()

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).

Parameters

bf	the filter

Definition at line 654 of file container_bloomfilter.c.

{
  if (NULL == bf)
    return;
  if (bf->fh != NULL)
    GNUNET_DISK_file_close (bf->fh);
  GNUNET_free (bf->filename);
  GNUNET_free (bf->bitArray);
  GNUNET_free (bf);
}

References GNUNET_CONTAINER_BloomFilter::bitArray, GNUNET_CONTAINER_BloomFilter::fh, GNUNET_CONTAINER_BloomFilter::filename, GNUNET_DISK_file_close(), and GNUNET_free.

Referenced by _GSS_operation_destroy(), bf_group_destroy_cb(), cleaning_task(), consider_for_advertising(), find_advertisable_hello(), free_peer(), GNUNET_DATACACHE_destroy(), handle_dht_local_put(), handle_dht_p2p_get(), handle_dht_p2p_put(), intersection_op_cancel(), process_bf(), process_peer(), process_stat_done(), send_bloomfilter(), send_find_peer_message(), and transmit_request().

Here is the call graph for this function:

Here is the caller graph for this function:

GNUNET_CONTAINER_bloomfilter_get_size()

size_t GNUNET_CONTAINER_bloomfilter_get_size

(

const struct GNUNET_CONTAINER_BloomFilter *

bf

)

Get size of the bloom filter.

Parameters

bf	the filter

Returns

number of bytes used for the data of the bloom filter

Definition at line 98 of file container_bloomfilter.c.

{
  if (bf == NULL)
    return 0;
  return bf->bitArraySize;
}

References GNUNET_CONTAINER_BloomFilter::bitArraySize.

GNUNET_CONTAINER_bloomfilter_clear()

void GNUNET_CONTAINER_bloomfilter_clear

(

struct GNUNET_CONTAINER_BloomFilter *

bf

)

Reset a Bloom filter to empty.

Parameters

bf	the filter

Definition at line 667 of file container_bloomfilter.c.

{
  if (NULL == bf)
    return;
 
  memset (bf->bitArray, 0, bf->bitArraySize);
  if (bf->filename != NULL)
    make_empty_file (bf->fh, bf->bitArraySize * 4LL);
}

References GNUNET_CONTAINER_BloomFilter::bitArray, GNUNET_CONTAINER_BloomFilter::bitArraySize, GNUNET_CONTAINER_BloomFilter::fh, GNUNET_CONTAINER_BloomFilter::filename, and make_empty_file().

Here is the call graph for this function:

GNUNET_CONTAINER_bloomfilter_or()

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.

Assumes that the size of the data array and the current filter match.

Parameters

bf	the filter
data	data to OR-in
size	size of data

Returns

GNUNET_OK on success

Definition at line 710 of file container_bloomfilter.c.

{
  unsigned int i;
  unsigned int n;
  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;
  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++)
    bf->bitArray[i] |= data[i];
  return GNUNET_OK;
}

References GNUNET_CONTAINER_BloomFilter::bitArray, GNUNET_CONTAINER_BloomFilter::bitArraySize, data, dc, GNUNET_OK, GNUNET_SYSERR, GNUNET_YES, and size.

GNUNET_CONTAINER_bloomfilter_or2()

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.

Assumes that the size of the two filters matches.

Parameters

bf	the filter
to_or	the bloomfilter to or-in

Returns

GNUNET_OK on success

Definition at line 736 of file container_bloomfilter.c.

{
  unsigned int i;
  unsigned int n;
  unsigned long long *fc;
  const unsigned long long *dc;
  size_t size;
 
  if (NULL == bf)
    return GNUNET_OK;
  if (bf->bitArraySize != to_or->bitArraySize)
  {
    GNUNET_break (0);
    return GNUNET_SYSERR;
  }
  size = bf->bitArraySize;
  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++)
    bf->bitArray[i] |= to_or->bitArray[i];
  return GNUNET_OK;
}

References GNUNET_CONTAINER_BloomFilter::bitArray, GNUNET_CONTAINER_BloomFilter::bitArraySize, dc, GNUNET_break, GNUNET_OK, GNUNET_SYSERR, and size.

Referenced by bf_group_merge_cb().

Here is the caller graph for this function:

GNUNET_CONTAINER_bloomfilter_resize()

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.

Note that this operation is pretty costly. Essentially, the Bloom filter needs to be completely re-build.

Parameters

bf	the filter
iterator	an iterator over all elements stored in the BF
iterator_cls	closure for iterator
size	the new size for the filter
k	the new number of GNUNET_CRYPTO_hash-function to apply per element

Definition at line 782 of file container_bloomfilter.c.

{
  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 */
  bf->addressesPerElement = k;
  bf->bitArraySize = size;
  bf->bitArray = GNUNET_malloc (size);
  if (NULL != bf->filename)
    make_empty_file (bf->fh, bf->bitArraySize * 4LL);
  while (GNUNET_YES == iterator (iterator_cls, &hc))
    GNUNET_CONTAINER_bloomfilter_add (bf, &hc);
}

References GNUNET_CONTAINER_BloomFilter::addressesPerElement, GNUNET_CONTAINER_BloomFilter::bitArray, GNUNET_CONTAINER_BloomFilter::bitArraySize, GNUNET_CONTAINER_BloomFilter::fh, GNUNET_CONTAINER_BloomFilter::filename, GNUNET_CONTAINER_bloomfilter_add(), GNUNET_free, GNUNET_malloc, GNUNET_YES, make_empty_file(), and size.

Here is the call graph for this function: