GNUnet  0.10.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 
40 
44  uint32_t bf_mutator;
45 
49  uint32_t bf_size;
50 };
51 
52 
63 static int
65  uint32_t *nonce,
66  void **raw_data,
67  size_t *raw_data_size)
68 {
69  struct BfGroupInternals *gi = bg->internal_cls;
70  char *raw;
71 
72  raw = GNUNET_malloc(gi->bf_size);
73  if (GNUNET_OK !=
75  raw,
76  gi->bf_size))
77  {
78  GNUNET_free(raw);
79  GNUNET_break(0);
80  return GNUNET_SYSERR;
81  }
82  *nonce = gi->bf_mutator;
83  *raw_data = raw;
84  *raw_data_size = gi->bf_size;
85  return GNUNET_OK;
86 }
87 
88 
97 static void
99  const struct GNUNET_HashCode *seen_results,
100  unsigned int seen_results_count)
101 {
102  struct BfGroupInternals *gi = bg->internal_cls;
103 
104  for (unsigned int i = 0; i < seen_results_count; i++)
105  {
106  struct GNUNET_HashCode mhash;
107 
108  GNUNET_BLOCK_mingle_hash(&seen_results[i],
109  gi->bf_mutator,
110  &mhash);
112  &mhash);
113  }
114 }
115 
116 
126 static int
128  const struct GNUNET_BLOCK_Group *bg2)
129 {
130  struct BfGroupInternals *gi1 = bg1->internal_cls;
131  struct BfGroupInternals *gi2 = bg2->internal_cls;
132 
133  if (gi1->bf_mutator != gi2->bf_mutator)
134  return GNUNET_NO;
135  if (gi1->bf_size != gi2->bf_size)
136  return GNUNET_NO;
138  gi2->bf);
139  return GNUNET_OK;
140 }
141 
142 
148 static void
150 {
151  struct BfGroupInternals *gi = bg->internal_cls;
152 
154  GNUNET_free(gi);
155  GNUNET_free(bg);
156 }
157 
158 
172 struct GNUNET_BLOCK_Group *
174  size_t bf_size,
175  unsigned int bf_k,
176  enum GNUNET_BLOCK_Type type,
177  uint32_t nonce,
178  const void *raw_data,
179  size_t raw_data_size)
180 {
181  struct BfGroupInternals *gi;
182  struct GNUNET_BLOCK_Group *bg;
183 
184  gi = GNUNET_new(struct BfGroupInternals);
185  gi->bf = GNUNET_CONTAINER_bloomfilter_init((bf_size != raw_data_size) ? NULL : raw_data,
186  bf_size,
187  bf_k);
188  gi->bf_mutator = nonce;
189  gi->bf_size = bf_size;
190  bg = GNUNET_new(struct GNUNET_BLOCK_Group);
191  bg->type = type;
196  bg->internal_cls = gi;
197  return bg;
198 }
199 
200 
211 int
213  const struct GNUNET_HashCode *hc)
214 {
215  struct BfGroupInternals *gi;
216  struct GNUNET_HashCode mhash;
217 
218  if (NULL == bg)
219  return GNUNET_NO;
220  gi = bg->internal_cls;
222  gi->bf_mutator,
223  &mhash);
224  if (GNUNET_YES ==
226  &mhash))
227  return GNUNET_YES;
229  &mhash);
230  return GNUNET_NO;
231 }
232 
233 
247 size_t
249  unsigned int k)
250 {
251  size_t size;
252  unsigned int ideal = (entry_count * k) / 4;
253  uint16_t max = 1 << 15;
254 
255  if (entry_count > max)
256  return max;
257  size = 8;
258  while ((size < max) && (size < ideal))
259  size *= 2;
260  if (size > max)
261  return max;
262  return size;
263 }
264 
265 
266 /* 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:98
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:173
#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:44
#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:149
#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:248
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:64
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:66
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:49
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:39
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:127
#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:212
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:79
#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.