GNUnet  0.11.x
bg_bf.c
Go to the documentation of this file.
1 /*
2  This file is part of GNUnet
3  Copyright (C) 2017 GNUnet e.V.
4 
5  GNUnet is free software: you can redistribute it and/or modify it
6  under the terms of the GNU Affero General Public License as published
7  by the Free Software Foundation, either version 3 of the License,
8  or (at your option) any later version.
9 
10  GNUnet is distributed in the hope that it will be useful, but
11  WITHOUT ANY WARRANTY; without even the implied warranty of
12  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13  Affero General Public License for more details.
14 
15  You should have received a copy of the GNU Affero General Public License
16  along with this program. If not, see <http://www.gnu.org/licenses/>.
17 
18  SPDX-License-Identifier: AGPL3.0-or-later
19  */
26 #include "platform.h"
27 #include "gnunet_util_lib.h"
28 #include "gnunet_block_group_lib.h"
29 #include "gnunet_block_plugin.h"
30 
31 
36 {
41 
45  uint32_t bf_mutator;
46 
50  uint32_t bf_size;
51 };
52 
53 
64 static int
66  uint32_t *nonce,
67  void **raw_data,
68  size_t *raw_data_size)
69 {
70  struct BfGroupInternals *gi = bg->internal_cls;
71  char *raw;
72 
73  raw = GNUNET_malloc (gi->bf_size);
74  if (GNUNET_OK !=
76  raw,
77  gi->bf_size))
78  {
79  GNUNET_free (raw);
80  GNUNET_break (0);
81  return GNUNET_SYSERR;
82  }
83  *nonce = gi->bf_mutator;
84  *raw_data = raw;
85  *raw_data_size = gi->bf_size;
86  return GNUNET_OK;
87 }
88 
89 
98 static void
100  const struct GNUNET_HashCode *seen_results,
101  unsigned int seen_results_count)
102 {
103  struct BfGroupInternals *gi = bg->internal_cls;
104 
105  for (unsigned int i = 0; i < seen_results_count; i++)
106  {
107  struct GNUNET_HashCode mhash;
108 
109  GNUNET_BLOCK_mingle_hash (&seen_results[i],
110  gi->bf_mutator,
111  &mhash);
113  &mhash);
114  }
115 }
116 
117 
127 static int
129  const struct GNUNET_BLOCK_Group *bg2)
130 {
131  struct BfGroupInternals *gi1 = bg1->internal_cls;
132  struct BfGroupInternals *gi2 = bg2->internal_cls;
133 
134  if (gi1->bf_mutator != gi2->bf_mutator)
135  return GNUNET_NO;
136  if (gi1->bf_size != gi2->bf_size)
137  return GNUNET_NO;
139  gi2->bf);
140  return GNUNET_OK;
141 }
142 
143 
149 static void
151 {
152  struct BfGroupInternals *gi = bg->internal_cls;
153 
155  GNUNET_free (gi);
156  GNUNET_free (bg);
157 }
158 
159 
173 struct GNUNET_BLOCK_Group *
175  size_t bf_size,
176  unsigned int bf_k,
177  enum GNUNET_BLOCK_Type type,
178  uint32_t nonce,
179  const void *raw_data,
180  size_t raw_data_size)
181 {
182  struct BfGroupInternals *gi;
183  struct GNUNET_BLOCK_Group *bg;
184 
185  gi = GNUNET_new (struct BfGroupInternals);
186  gi->bf = GNUNET_CONTAINER_bloomfilter_init ((bf_size != raw_data_size) ?
187  NULL : raw_data,
188  bf_size,
189  bf_k);
190  gi->bf_mutator = nonce;
191  gi->bf_size = bf_size;
192  bg = GNUNET_new (struct GNUNET_BLOCK_Group);
193  bg->type = type;
198  bg->internal_cls = gi;
199  return bg;
200 }
201 
202 
213 int
215  const struct GNUNET_HashCode *hc)
216 {
217  struct BfGroupInternals *gi;
218  struct GNUNET_HashCode mhash;
219 
220  if (NULL == bg)
221  return GNUNET_NO;
222  gi = bg->internal_cls;
224  gi->bf_mutator,
225  &mhash);
226  if (GNUNET_YES ==
228  &mhash))
229  return GNUNET_YES;
231  &mhash);
232  return GNUNET_NO;
233 }
234 
235 
249 size_t
251  unsigned int k)
252 {
253  size_t size;
254  unsigned int ideal = (entry_count * k) / 4;
255  uint16_t max = 1 << 15;
256 
257  if (entry_count > max)
258  return max;
259  size = 8;
260  while ((size < max) && (size < ideal))
261  size *= 2;
262  if (size > max)
263  return max;
264  return size;
265 }
266 
267 
268 /* end of bg_bf.c */
struct GNUNET_CONTAINER_BloomFilter * GNUNET_CONTAINER_bloomfilter_init(const char *data, size_t size, unsigned int k)
Create a Bloom filter from raw bits.
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.
static int raw
raw output
Definition: gnunet-gns.c:55
GNUNET_BLOCK_GroupSerializeFunction serialize_cb
Serialize the block group data, can be NULL if not supported.
GNUNET_BLOCK_Type
Blocks in the datastore and the datacache must have a unique type.
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.
Definition: bg_bf.c:99
struct GNUNET_BLOCK_Group * GNUNET_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.
Definition: bg_bf.c:174
#define GNUNET_NO
Definition: gnunet_common.h:78
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:75
Internal data structure for a block group.
Definition: bg_bf.c:35
static void bf_group_destroy_cb(struct GNUNET_BLOCK_Group *bg)
Destroy resources used by a block group.
Definition: bg_bf.c:150
#define GNUNET_new(type)
Allocate a struct or union of the given type.
GNUNET_BLOCK_GroupDestroyFunction destroy_cb
Function to call to destroy the block group.
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).
Definition: bg_bf.c:250
enum GNUNET_BLOCK_Type type
Type for the block group.
#define GNUNET_break(cond)
Use this for internal assertion violations that are not fatal (can be handled) but should not occur...
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.
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.
Definition: bg_bf.c:65
int GNUNET_CONTAINER_bloomfilter_test(const struct GNUNET_CONTAINER_BloomFilter *bf, const struct GNUNET_HashCode *e)
Test if an element is in the filter.
A 512-bit hashcode.
#define GNUNET_SYSERR
Definition: gnunet_common.h:76
static unsigned int size
Size of the "table".
Definition: peer.c:67
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
GNUNET_BLOCK_GroupMergeFunction merge_cb
Function to call to merge two groups.
Block group data.
struct GNUNET_CONTAINER_BloomFilter * bf
A Bloom filter to weed out duplicate replies probabilistically.
Definition: bg_bf.c:40
enum GNUNET_TESTBED_UnderlayLinkModelType type
the type of this model
static int bf_group_merge_cb(struct GNUNET_BLOCK_Group *bg1, const struct GNUNET_BLOCK_Group *bg2)
Merge two groups, if possible.
Definition: bg_bf.c:128
#define GNUNET_YES
Definition: gnunet_common.h:77
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.
Definition: bg_bf.c:214
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...
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
#define GNUNET_malloc(size)
Wrapper around malloc.
#define GNUNET_free(ptr)
Wrapper around free.
GNUNET_BLOCK_GroupMarkSeenFunction mark_seen_cb
Function to call to mark elements as seen in the group.