GNUnet  0.17.6
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 
63 static enum GNUNET_GenericReturnValue
65  void **raw_data,
66  size_t *raw_data_size)
67 {
68  struct BfGroupInternals *gi = bg->internal_cls;
69  void *raw;
70 
71  raw = GNUNET_malloc (gi->bf_size + sizeof (uint32_t));
72  if (GNUNET_OK !=
74  raw + sizeof (uint32_t),
75  gi->bf_size))
76  {
77  GNUNET_free (raw);
78  GNUNET_break (0);
79  return GNUNET_SYSERR;
80  }
81  memcpy (raw,
82  &gi->bf_mutator,
83  sizeof (uint32_t));
84  *raw_data = raw;
85  *raw_data_size = gi->bf_size + sizeof (uint32_t);
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 enum GNUNET_GenericReturnValue
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 
172 struct GNUNET_BLOCK_Group *
174  size_t bf_size,
175  unsigned int bf_k,
176  enum GNUNET_BLOCK_Type type,
177  const void *raw_data,
178  size_t raw_data_size)
179 {
180  struct BfGroupInternals *gi;
181  struct GNUNET_BLOCK_Group *bg;
182  uint32_t nonce;
183 
184  if ( (NULL != raw_data) &&
185  (raw_data_size < sizeof (nonce)) )
186  {
187  GNUNET_break_op (0);
188  return NULL;
189  }
190  if (NULL != raw_data)
191  {
192  memcpy (&nonce,
193  raw_data,
194  sizeof (nonce));
195  raw_data += sizeof (nonce);
196  raw_data_size -= sizeof (nonce);
197  }
198  else
199  {
201  UINT32_MAX);
202  }
203  gi = GNUNET_new (struct BfGroupInternals);
204  gi->bf = GNUNET_CONTAINER_bloomfilter_init ((bf_size != raw_data_size) ?
205  NULL : raw_data,
206  bf_size,
207  bf_k);
208  gi->bf_mutator = nonce;
209  gi->bf_size = bf_size;
210  bg = GNUNET_new (struct GNUNET_BLOCK_Group);
211  bg->type = type;
216  bg->internal_cls = gi;
217  return bg;
218 }
219 
220 
233  const struct GNUNET_HashCode *hc)
234 {
235  struct BfGroupInternals *gi;
236  struct GNUNET_HashCode mhash;
237 
238  if (NULL == bg)
239  return GNUNET_NO;
240  gi = bg->internal_cls;
242  gi->bf_mutator,
243  &mhash);
244  if (GNUNET_YES ==
246  &mhash))
247  return GNUNET_YES;
249  &mhash);
250  return GNUNET_NO;
251 }
252 
253 
267 size_t
269  unsigned int k)
270 {
271  size_t size;
272  unsigned int ideal = (entry_count * k) / 4;
273  uint16_t max = 1 << 15;
274 
275  if (entry_count > max)
276  return max;
277  size = 8;
278  while ((size < max) && (size < ideal))
279  size *= 2;
280  if (size > max)
281  return max;
282  return size;
283 }
284 
285 
286 /* end of bg_bf.c */
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
static enum GNUNET_GenericReturnValue bf_group_serialize_cb(struct GNUNET_BLOCK_Group *bg, void **raw_data, size_t *raw_data_size)
Serialize state of a block group.
Definition: bg_bf.c:64
static void bf_group_destroy_cb(struct GNUNET_BLOCK_Group *bg)
Destroy resources used by a block group.
Definition: bg_bf.c:150
static enum GNUNET_GenericReturnValue 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
GNUNET_BLOCK_Type
WARNING: This header is generated! In order to add DHT block types, you must register them in GANA,...
static int raw
raw output
Definition: gnunet-gns.c:79
API for block plugins.
enum GNUNET_GenericReturnValue 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:232
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?...
Definition: bg_bf.c:268
struct GNUNET_BLOCK_Group * GNUNET_BLOCK_GROUP_bf_create(void *cls, size_t bf_size, unsigned int bf_k, enum GNUNET_BLOCK_Type type, 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:173
GNUNET_NETWORK_STRUCT_END 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:96
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.
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.
void GNUNET_CONTAINER_bloomfilter_add(struct GNUNET_CONTAINER_BloomFilter *bf, const struct GNUNET_HashCode *e)
Add an element to the filter.
bool GNUNET_CONTAINER_bloomfilter_test(const struct GNUNET_CONTAINER_BloomFilter *bf, const struct GNUNET_HashCode *e)
Test if an element is in the filter.
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 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...
uint32_t GNUNET_CRYPTO_random_u32(enum GNUNET_CRYPTO_Quality mode, uint32_t i)
Produce a random value.
@ GNUNET_CRYPTO_QUALITY_NONCE
Randomness for IVs etc.
GNUNET_GenericReturnValue
Named constants for return values.
Definition: gnunet_common.h:96
@ GNUNET_OK
Definition: gnunet_common.h:99
@ GNUNET_YES
@ GNUNET_NO
Definition: gnunet_common.h:98
@ GNUNET_SYSERR
Definition: gnunet_common.h:97
#define GNUNET_break_op(cond)
Use this for assertion violations caused by other peers (i.e.
#define GNUNET_break(cond)
Use this for internal assertion violations that are not fatal (can be handled) but should not occur.
#define GNUNET_new(type)
Allocate a struct or union of the given type.
#define GNUNET_malloc(size)
Wrapper around malloc.
#define GNUNET_free(ptr)
Wrapper around free.
#define max(x, y)
static unsigned int size
Size of the "table".
Definition: peer.c:67
Internal data structure for a block group.
Definition: bg_bf.c:36
uint32_t bf_size
Size of bf.
Definition: bg_bf.c:50
uint32_t bf_mutator
Set from the nonce to mingle the hashes before going into the bf.
Definition: bg_bf.c:45
struct GNUNET_CONTAINER_BloomFilter * bf
A Bloom filter to weed out duplicate replies probabilistically.
Definition: bg_bf.c:40
Block group data.
GNUNET_BLOCK_GroupMergeFunction merge_cb
Function to call to merge two groups.
GNUNET_BLOCK_GroupDestroyFunction destroy_cb
Function to call to destroy the block group.
GNUNET_BLOCK_GroupMarkSeenFunction mark_seen_cb
Function to call to mark elements as seen in the group.
void * internal_cls
Internal data structure of the plugin.
GNUNET_BLOCK_GroupSerializeFunction serialize_cb
Serialize the block group data, can be NULL if not supported.
enum GNUNET_BLOCK_Type type
Type for the block group.
A 512-bit hashcode.
enum GNUNET_TESTBED_UnderlayLinkModelType type
the type of this model