aboutsummaryrefslogtreecommitdiff
path: root/src/block/bg_bf.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/block/bg_bf.c')
-rw-r--r--src/block/bg_bf.c268
1 files changed, 0 insertions, 268 deletions
diff --git a/src/block/bg_bf.c b/src/block/bg_bf.c
deleted file mode 100644
index 601f605a2..000000000
--- a/src/block/bg_bf.c
+++ /dev/null
@@ -1,268 +0,0 @@
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 */
20/**
21 * @file block/bg_bf.c
22 * @brief implementation of a block group using a Bloom filter
23 * to drop duplicate blocks
24 * @author Christian Grothoff
25 */
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
32/**
33 * Internal data structure for a block group.
34 */
35struct BfGroupInternals
36{
37 /**
38 * A Bloom filter to weed out duplicate replies probabilistically.
39 */
40 struct GNUNET_CONTAINER_BloomFilter *bf;
41
42 /**
43 * Set from the nonce to mingle the hashes before going into the @e bf.
44 */
45 uint32_t bf_mutator;
46
47 /**
48 * Size of @a bf.
49 */
50 uint32_t bf_size;
51};
52
53
54/**
55 * Serialize state of a block group.
56 *
57 * @param bg group to serialize
58 * @param[out] nonce set to the nonce of the @a bg
59 * @param[out] raw_data set to the serialized state
60 * @param[out] raw_data_size set to the number of bytes in @a raw_data
61 * @return #GNUNET_OK on success, #GNUNET_NO if serialization is not
62 * supported, #GNUNET_SYSERR on error
63 */
64static enum GNUNET_GenericReturnValue
65bf_group_serialize_cb (struct GNUNET_BLOCK_Group *bg,
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 !=
75 GNUNET_CONTAINER_bloomfilter_get_raw_data (gi->bf,
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
90/**
91 * Mark elements as "seen" using a hash of the element. Not supported
92 * by all block plugins.
93 *
94 * @param bg group to update
95 * @param seen_results results already seen
96 * @param seen_results_count number of entries in @a seen_results
97 */
98static void
99bf_group_mark_seen_cb (struct GNUNET_BLOCK_Group *bg,
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);
112 GNUNET_CONTAINER_bloomfilter_add (gi->bf,
113 &mhash);
114 }
115}
116
117
118/**
119 * Merge two groups, if possible. Not supported by all block plugins,
120 * can also fail if the nonces were different.
121 *
122 * @param bg1 group to update
123 * @param bg2 group to merge into @a bg1
124 * @return #GNUNET_OK on success, #GNUNET_NO if the nonces were different and thus
125 * we failed.
126 */
127static enum GNUNET_GenericReturnValue
128bf_group_merge_cb (struct GNUNET_BLOCK_Group *bg1,
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;
138 GNUNET_CONTAINER_bloomfilter_or2 (gi1->bf,
139 gi2->bf);
140 return GNUNET_OK;
141}
142
143
144/**
145 * Destroy resources used by a block group.
146 *
147 * @param bg group to destroy, NULL is allowed
148 */
149static void
150bf_group_destroy_cb (struct GNUNET_BLOCK_Group *bg)
151{
152 struct BfGroupInternals *gi = bg->internal_cls;
153
154 GNUNET_CONTAINER_bloomfilter_free (gi->bf);
155 GNUNET_free (gi);
156 GNUNET_free (bg);
157}
158
159
160/**
161 * Create a new block group that filters duplicates using a Bloom filter.
162 *
163 * @param ctx block context in which the block group is created
164 * @param bf_size size of the Bloom filter
165 * @param bf_k K-value for the Bloom filter
166 * @param type block type
167 * @param nonce random value used to seed the group creation
168 * @param raw_data optional serialized prior state of the group, NULL if unavailable/fresh
169 * @param raw_data_size number of bytes in @a raw_data, 0 if unavailable/fresh
170 * @return block group handle, NULL if block groups are not supported
171 * by this @a type of block (this is not an error)
172 */
173struct GNUNET_BLOCK_Group *
174GNUNET_BLOCK_GROUP_bf_create (void *cls,
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;
194 bg->serialize_cb = &bf_group_serialize_cb;
195 bg->mark_seen_cb = &bf_group_mark_seen_cb;
196 bg->merge_cb = &bf_group_merge_cb;
197 bg->destroy_cb = &bf_group_destroy_cb;
198 bg->internal_cls = gi;
199 return bg;
200}
201
202
203/**
204 * Test if @a hc is contained in the Bloom filter of @a bg. If so,
205 * return #GNUNET_YES. If not, add @a hc to the Bloom filter and
206 * return #GNUNET_NO.
207 *
208 * @param bg block group to use for testing
209 * @param hc hash of element to evaluate
210 * @return #GNUNET_YES if @a hc is (likely) a duplicate
211 * #GNUNET_NO if @a hc was definitively not in @bg (but now is)
212 */
213int
214GNUNET_BLOCK_GROUP_bf_test_and_set (struct GNUNET_BLOCK_Group *bg,
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;
223 GNUNET_BLOCK_mingle_hash (hc,
224 gi->bf_mutator,
225 &mhash);
226 if (GNUNET_YES ==
227 GNUNET_CONTAINER_bloomfilter_test (gi->bf,
228 &mhash))
229 return GNUNET_YES;
230 GNUNET_CONTAINER_bloomfilter_add (gi->bf,
231 &mhash);
232 return GNUNET_NO;
233}
234
235
236/**
237 * How many bytes should a bloomfilter be if we have already seen
238 * entry_count responses? Sized so that do not have to
239 * re-size the filter too often (to keep it cheap).
240 *
241 * Since other peers will also add entries but not resize the filter,
242 * we should generally pick a slightly larger size than what the
243 * strict math would suggest.
244 *
245 * @param entry_count expected number of entries in the Bloom filter
246 * @param k number of bits set per entry
247 * @return must be a power of two and smaller or equal to 2^15.
248 */
249size_t
250GNUNET_BLOCK_GROUP_compute_bloomfilter_size (unsigned int entry_count,
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 */