2 This file is part of GNUnet
3 Copyright (C) 2017 GNUnet e.V.
5 GNUnet is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published
7 by the Free Software Foundation; either version 3, or (at your
8 option) any later version.
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 General Public License for more details.
15 You should have received a copy of the GNU General Public License
16 along with GNUnet; see the file COPYING. If not, write to the
17 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
18 Boston, MA 02110-1301, USA.
22 * @brief implementation of a block group using a Bloom filter
23 * to drop duplicate blocks
24 * @author Christian Grothoff
27 #include "gnunet_util_lib.h"
28 #include "gnunet_block_group_lib.h"
29 #include "gnunet_block_plugin.h"
33 * Internal data structure for a block group.
35 struct BfGroupInternals
38 * A Bloom filter to weed out duplicate replies probabilistically.
40 struct GNUNET_CONTAINER_BloomFilter *bf;
43 * Set from the nonce to mingle the hashes before going into the @e bf.
56 * Serialize state of a block group.
58 * @param bg group to serialize
59 * @param[out] nonce set to the nonce of the @a bg
60 * @param[out] raw_data set to the serialized state
61 * @param[out] raw_data_size set to the number of bytes in @a raw_data
62 * @return #GNUNET_OK on success, #GNUNET_NO if serialization is not
63 * supported, #GNUNET_SYSERR on error
66 bf_group_serialize_cb (struct GNUNET_BLOCK_Group *bg,
69 size_t *raw_data_size)
71 struct BfGroupInternals *gi = bg->internal_cls;
74 raw = GNUNET_malloc (gi->bf_size);
76 GNUNET_CONTAINER_bloomfilter_get_raw_data (gi->bf,
84 *nonce = gi->bf_mutator;
86 *raw_data_size = gi->bf_size;
92 * Mark elements as "seen" using a hash of the element. Not supported
93 * by all block plugins.
95 * @param bg group to update
96 * @param seen_results results already seen
97 * @param seen_results_count number of entries in @a seen_results
100 bf_group_mark_seen_cb (struct GNUNET_BLOCK_Group *bg,
101 const struct GNUNET_HashCode *seen_results,
102 unsigned int seen_results_count)
104 struct BfGroupInternals *gi = bg->internal_cls;
106 for (unsigned int i=0;i<seen_results_count;i++)
108 struct GNUNET_HashCode mhash;
110 GNUNET_BLOCK_mingle_hash (&seen_results[i],
113 GNUNET_CONTAINER_bloomfilter_add (gi->bf,
120 * Merge two groups, if possible. Not supported by all block plugins,
121 * can also fail if the nonces were different.
123 * @param bg1 group to update
124 * @param bg2 group to merge into @a bg1
125 * @return #GNUNET_OK on success, #GNUNET_NO if the nonces were different and thus
129 bf_group_merge_cb (struct GNUNET_BLOCK_Group *bg1,
130 const struct GNUNET_BLOCK_Group *bg2)
132 struct BfGroupInternals *gi1 = bg1->internal_cls;
133 struct BfGroupInternals *gi2 = bg2->internal_cls;
135 if (gi1->bf_mutator != gi2->bf_mutator)
137 if (gi1->bf_size != gi2->bf_size)
139 GNUNET_CONTAINER_bloomfilter_or2 (gi1->bf,
146 * Destroy resources used by a block group.
148 * @param bg group to destroy, NULL is allowed
151 bf_group_destroy_cb (struct GNUNET_BLOCK_Group *bg)
153 struct BfGroupInternals *gi = bg->internal_cls;
155 GNUNET_CONTAINER_bloomfilter_free (gi->bf);
162 * Create a new block group that filters duplicates using a Bloom filter.
164 * @param ctx block context in which the block group is created
165 * @param bf_size size of the Bloom filter
166 * @param bf_k K-value for the Bloom filter
167 * @param type block type
168 * @param nonce random value used to seed the group creation
169 * @param raw_data optional serialized prior state of the group, NULL if unavailable/fresh
170 * @param raw_data_size number of bytes in @a raw_data, 0 if unavailable/fresh
171 * @return block group handle, NULL if block groups are not supported
172 * by this @a type of block (this is not an error)
174 struct GNUNET_BLOCK_Group *
175 GNUNET_BLOCK_GROUP_bf_create (void *cls,
178 enum GNUNET_BLOCK_Type type,
180 const void *raw_data,
181 size_t raw_data_size)
183 struct BfGroupInternals *gi;
184 struct GNUNET_BLOCK_Group *bg;
186 gi = GNUNET_new (struct BfGroupInternals);
187 gi->bf = GNUNET_CONTAINER_bloomfilter_init ((bf_size != raw_data_size) ? NULL : raw_data,
190 gi->bf_mutator = nonce;
191 gi->bf_size = bf_size;
192 bg = GNUNET_new (struct GNUNET_BLOCK_Group);
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;
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
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)
214 GNUNET_BLOCK_GROUP_bf_test_and_set (struct GNUNET_BLOCK_Group *bg,
215 const struct GNUNET_HashCode *hc)
217 struct BfGroupInternals *gi;
218 struct GNUNET_HashCode mhash;
222 gi = bg->internal_cls;
223 GNUNET_BLOCK_mingle_hash (hc,
227 GNUNET_CONTAINER_bloomfilter_test (gi->bf,
230 GNUNET_CONTAINER_bloomfilter_add (gi->bf,
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).
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.
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.
250 GNUNET_BLOCK_GROUP_compute_bloomfilter_size (unsigned int entry_count,
254 unsigned int ideal = (entry_count * k) / 4;
255 uint16_t max = 1 << 15;
257 if (entry_count > max)
260 while ((size < max) && (size < ideal))