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 
36 {
41 
45  uint32_t bf_mutator;
46 
50  uint32_t bf_size;
51 
52 };
53 
54 
65 static int
67  uint32_t *nonce,
68  void **raw_data,
69  size_t *raw_data_size)
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 }
89 
90 
99 static void
101  const struct GNUNET_HashCode *seen_results,
102  unsigned int seen_results_count)
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 }
117 
118 
128 static int
130  const struct GNUNET_BLOCK_Group *bg2)
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 }
143 
144 
150 static void
152 {
153  struct BfGroupInternals *gi = bg->internal_cls;
154 
156  GNUNET_free (gi);
157  GNUNET_free (bg);
158 }
159 
160 
174 struct GNUNET_BLOCK_Group *
176  size_t bf_size,
177  unsigned int bf_k,
178  enum GNUNET_BLOCK_Type type,
179  uint32_t nonce,
180  const void *raw_data,
181  size_t raw_data_size)
182 {
183  struct BfGroupInternals *gi;
184  struct GNUNET_BLOCK_Group *bg;
185 
186  gi = GNUNET_new (struct BfGroupInternals);
187  gi->bf = GNUNET_CONTAINER_bloomfilter_init ((bf_size != raw_data_size) ? 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:100
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:175
#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
static void bf_group_destroy_cb(struct GNUNET_BLOCK_Group *bg)
Destroy resources used by a block group.
Definition: bg_bf.c:151
#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:66
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:79
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:129
#define GNUNET_YES
Definition: gnunet_common.h:80
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.