GNUnet  0.10.x
Data Structures | Functions
bg_bf.c File Reference

implementation of a block group using a Bloom filter to drop duplicate blocks More...

#include "platform.h"
#include "gnunet_util_lib.h"
#include "gnunet_block_group_lib.h"
#include "gnunet_block_plugin.h"
Include dependency graph for bg_bf.c:

Go to the source code of this file.

Data Structures

struct  BfGroupInternals
 Internal data structure for a block group. More...
 

Functions

static int bf_group_serialize_cb (struct GNUNET_BLOCK_Group *bg, uint32_t *nonce, void **raw_data, size_t *raw_data_size)
 Serialize state of a block group. More...
 
static void bf_group_mark_seen_cb (struct GNUNET_BLOCK_Group *bg, const struct GNUNET_HashCode *seen_results, unsigned int seen_results_count)
 Mark elements as "seen" using a hash of the element. More...
 
static int bf_group_merge_cb (struct GNUNET_BLOCK_Group *bg1, const struct GNUNET_BLOCK_Group *bg2)
 Merge two groups, if possible. More...
 
static void bf_group_destroy_cb (struct GNUNET_BLOCK_Group *bg)
 Destroy resources used by a block group. More...
 
struct GNUNET_BLOCK_GroupGNUNET_BLOCK_GROUP_bf_create (void *cls, size_t bf_size, unsigned int bf_k, enum GNUNET_BLOCK_Type type, uint32_t nonce, const void *raw_data, size_t raw_data_size)
 Create a new block group that filters duplicates using a Bloom filter. More...
 
int GNUNET_BLOCK_GROUP_bf_test_and_set (struct GNUNET_BLOCK_Group *bg, const struct GNUNET_HashCode *hc)
 Test if hc is contained in the Bloom filter of bg. More...
 
size_t GNUNET_BLOCK_GROUP_compute_bloomfilter_size (unsigned int entry_count, unsigned int k)
 How many bytes should a bloomfilter be if we have already seen entry_count responses? Sized so that do not have to re-size the filter too often (to keep it cheap). More...
 

Detailed Description

implementation of a block group using a Bloom filter to drop duplicate blocks

Author
Christian Grothoff

Definition in file bg_bf.c.

Function Documentation

◆ bf_group_serialize_cb()

static int bf_group_serialize_cb ( struct GNUNET_BLOCK_Group bg,
uint32_t *  nonce,
void **  raw_data,
size_t *  raw_data_size 
)
static

Serialize state of a block group.

Parameters
bggroup to serialize
[out]nonceset to the nonce of the bg
[out]raw_dataset to the serialized state
[out]raw_data_sizeset to the number of bytes in raw_data
Returns
GNUNET_OK on success, GNUNET_NO if serialization is not supported, GNUNET_SYSERR on error

Definition at line 66 of file bg_bf.c.

References BfGroupInternals::bf, BfGroupInternals::bf_mutator, BfGroupInternals::bf_size, GNUNET_break, GNUNET_CONTAINER_bloomfilter_get_raw_data(), GNUNET_free, GNUNET_malloc, GNUNET_OK, GNUNET_SYSERR, GNUNET_BLOCK_Group::internal_cls, and raw.

Referenced by GNUNET_BLOCK_GROUP_bf_create().

70 {
71  struct BfGroupInternals *gi = bg->internal_cls;
72  char *raw;
73 
74  raw = GNUNET_malloc (gi->bf_size);
75  if (GNUNET_OK !=
77  raw,
78  gi->bf_size))
79  {
80  GNUNET_free (raw);
81  GNUNET_break (0);
82  return GNUNET_SYSERR;
83  }
84  *nonce = gi->bf_mutator;
85  *raw_data = raw;
86  *raw_data_size = gi->bf_size;
87  return GNUNET_OK;
88 }
void * internal_cls
Internal data structure of the plugin.
static int raw
raw output
Definition: gnunet-gns.c:55
uint32_t bf_mutator
Set from the nonce to mingle the hashes before going into the bf.
Definition: bg_bf.c:45
#define GNUNET_OK
Named constants for return values.
Definition: gnunet_common.h:78
Internal data structure for a block group.
Definition: bg_bf.c:35
#define GNUNET_break(cond)
Use this for internal assertion violations that are not fatal (can be handled) but should not occur...
#define GNUNET_SYSERR
Definition: gnunet_common.h:79
int 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.
uint32_t bf_size
Size of bf.
Definition: bg_bf.c:50
struct GNUNET_CONTAINER_BloomFilter * bf
A Bloom filter to weed out duplicate replies probabilistically.
Definition: bg_bf.c:40
#define GNUNET_malloc(size)
Wrapper around malloc.
#define GNUNET_free(ptr)
Wrapper around free.
Here is the call graph for this function:
Here is the caller graph for this function:

◆ bf_group_mark_seen_cb()

static void bf_group_mark_seen_cb ( struct GNUNET_BLOCK_Group bg,
const struct GNUNET_HashCode seen_results,
unsigned int  seen_results_count 
)
static

Mark elements as "seen" using a hash of the element.

Not supported by all block plugins.

Parameters
bggroup to update
seen_resultsresults already seen
seen_results_countnumber of entries in seen_results

Definition at line 100 of file bg_bf.c.

References BfGroupInternals::bf, BfGroupInternals::bf_mutator, GNUNET_BLOCK_mingle_hash(), GNUNET_CONTAINER_bloomfilter_add(), and GNUNET_BLOCK_Group::internal_cls.

Referenced by GNUNET_BLOCK_GROUP_bf_create().

103 {
104  struct BfGroupInternals *gi = bg->internal_cls;
105 
106  for (unsigned int i=0;i<seen_results_count;i++)
107  {
108  struct GNUNET_HashCode mhash;
109 
110  GNUNET_BLOCK_mingle_hash (&seen_results[i],
111  gi->bf_mutator,
112  &mhash);
114  &mhash);
115  }
116 }
void * internal_cls
Internal data structure of the plugin.
void GNUNET_CONTAINER_bloomfilter_add(struct GNUNET_CONTAINER_BloomFilter *bf, const struct GNUNET_HashCode *e)
Add an element to the filter.
uint32_t bf_mutator
Set from the nonce to mingle the hashes before going into the bf.
Definition: bg_bf.c:45
Internal data structure for a block group.
Definition: bg_bf.c:35
A 512-bit hashcode.
struct GNUNET_CONTAINER_BloomFilter * bf
A Bloom filter to weed out duplicate replies probabilistically.
Definition: bg_bf.c:40
void GNUNET_BLOCK_mingle_hash(const struct GNUNET_HashCode *in, uint32_t mingle_number, struct GNUNET_HashCode *hc)
Mingle hash with the mingle_number to produce different bits.
Definition: block.c:81
Here is the call graph for this function:
Here is the caller graph for this function:

◆ bf_group_merge_cb()

static int bf_group_merge_cb ( struct GNUNET_BLOCK_Group bg1,
const struct GNUNET_BLOCK_Group bg2 
)
static

Merge two groups, if possible.

Not supported by all block plugins, can also fail if the nonces were different.

Parameters
bg1group to update
bg2group to merge into bg1
Returns
GNUNET_OK on success, GNUNET_NO if the nonces were different and thus we failed.

Definition at line 129 of file bg_bf.c.

References BfGroupInternals::bf, BfGroupInternals::bf_mutator, BfGroupInternals::bf_size, GNUNET_CONTAINER_bloomfilter_or2(), GNUNET_NO, GNUNET_OK, and GNUNET_BLOCK_Group::internal_cls.

Referenced by GNUNET_BLOCK_GROUP_bf_create().

131 {
132  struct BfGroupInternals *gi1 = bg1->internal_cls;
133  struct BfGroupInternals *gi2 = bg2->internal_cls;
134 
135  if (gi1->bf_mutator != gi2->bf_mutator)
136  return GNUNET_NO;
137  if (gi1->bf_size != gi2->bf_size)
138  return GNUNET_NO;
140  gi2->bf);
141  return GNUNET_OK;
142 }
void * internal_cls
Internal data structure of the plugin.
#define GNUNET_NO
Definition: gnunet_common.h:81
uint32_t bf_mutator
Set from the nonce to mingle the hashes before going into the bf.
Definition: bg_bf.c:45
#define GNUNET_OK
Named constants for return values.
Definition: gnunet_common.h:78
Internal data structure for a block group.
Definition: bg_bf.c:35
int 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.
uint32_t bf_size
Size of bf.
Definition: bg_bf.c:50
struct GNUNET_CONTAINER_BloomFilter * bf
A Bloom filter to weed out duplicate replies probabilistically.
Definition: bg_bf.c:40
Here is the call graph for this function:
Here is the caller graph for this function:

◆ bf_group_destroy_cb()

static void bf_group_destroy_cb ( struct GNUNET_BLOCK_Group bg)
static

Destroy resources used by a block group.

Parameters
bggroup to destroy, NULL is allowed

Definition at line 151 of file bg_bf.c.

References BfGroupInternals::bf, GNUNET_CONTAINER_bloomfilter_free(), GNUNET_free, and GNUNET_BLOCK_Group::internal_cls.

Referenced by GNUNET_BLOCK_GROUP_bf_create().

152 {
153  struct BfGroupInternals *gi = bg->internal_cls;
154 
156  GNUNET_free (gi);
157  GNUNET_free (bg);
158 }
void * internal_cls
Internal data structure of the plugin.
Internal data structure for a block group.
Definition: bg_bf.c:35
struct GNUNET_CONTAINER_BloomFilter * bf
A Bloom filter to weed out duplicate replies probabilistically.
Definition: bg_bf.c:40
void GNUNET_CONTAINER_bloomfilter_free(struct GNUNET_CONTAINER_BloomFilter *bf)
Free the space associcated with a filter in memory, flush to drive if needed (do not free the space o...
#define GNUNET_free(ptr)
Wrapper around free.
Here is the call graph for this function:
Here is the caller graph for this function: