summaryrefslogtreecommitdiff
path: root/src/block/bg_bf.c
blob: 3e7d38892dc209d7b25fa697147b9236d3e27401 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
/*
     This file is part of GNUnet
     Copyright (C) 2017 GNUnet e.V.

     GNUnet is free software; you can redistribute it and/or modify
     it under the terms of the GNU General Public License as published
     by the Free Software Foundation; either version 3, or (at your
     option) any later version.

     GNUnet is distributed in the hope that it will be useful, but
     WITHOUT ANY WARRANTY; without even the implied warranty of
     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
     General Public License for more details.

     You should have received a copy of the GNU General Public License
     along with GNUnet; see the file COPYING.  If not, write to the
     Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
     Boston, MA 02110-1301, USA.
*/
/**
 * @file block/bg_bf.c
 * @brief implementation of a block group using a Bloom filter
 *        to drop duplicate blocks
 * @author Christian Grothoff
 */
#include "platform.h"
#include "gnunet_util_lib.h"
#include "gnunet_block_group_lib.h"
#include "gnunet_block_plugin.h"


/**
 * Internal data structure for a block group.
 */
struct BfGroupInternals
{
  /**
   * A Bloom filter to weed out duplicate replies probabilistically.
   */
  struct GNUNET_CONTAINER_BloomFilter *bf;

  /**
   * Set from the nonce to mingle the hashes before going into the @e bf.
   */
  uint32_t bf_mutator;

  /**
   * Size of @a bf.
   */
  uint32_t bf_size;

};


/**
 * Serialize state of a block group.
 *
 * @param bg group to serialize
 * @param[out] nonce set to the nonce of the @a bg
 * @param[out] raw_data set to the serialized state
 * @param[out] raw_data_size set to the number of bytes in @a raw_data
 * @return #GNUNET_OK on success, #GNUNET_NO if serialization is not
 *         supported, #GNUNET_SYSERR on error
 */
static int
bf_group_serialize_cb (struct GNUNET_BLOCK_Group *bg,
                       uint32_t *nonce,
                       void **raw_data,
                       size_t *raw_data_size)
{
  struct BfGroupInternals *gi = bg->internal_cls;
  char *raw;

  raw = GNUNET_malloc (gi->bf_size);
  if (GNUNET_OK !=
      GNUNET_CONTAINER_bloomfilter_get_raw_data (gi->bf,
                                                 raw,
                                                 gi->bf_size))
  {
    GNUNET_free (raw);
    GNUNET_break (0);
    return GNUNET_SYSERR;
  }
  *nonce = gi->bf_mutator;
  *raw_data = raw;
  *raw_data_size = gi->bf_size;
  return GNUNET_OK;
}


/**
 * Mark elements as "seen" using a hash of the element. Not supported
 * by all block plugins.
 *
 * @param bg group to update
 * @param seen_results results already seen
 * @param seen_results_count number of entries in @a seen_results
 */
static void
bf_group_mark_seen_cb (struct GNUNET_BLOCK_Group *bg,
                       const struct GNUNET_HashCode *seen_results,
                       unsigned int seen_results_count)
{
  struct BfGroupInternals *gi = bg->internal_cls;

  for (unsigned int i=0;i<seen_results_count;i++)
  {
    struct GNUNET_HashCode mhash;

    GNUNET_BLOCK_mingle_hash (&seen_results[i],
                              gi->bf_mutator,
                              &mhash);
    GNUNET_CONTAINER_bloomfilter_add (gi->bf,
                                      &mhash);
  }
}


/**
 * Merge two groups, if possible. Not supported by all block plugins,
 * can also fail if the nonces were different.
 *
 * @param bg1 group to update
 * @param bg2 group to merge into @a bg1
 * @return #GNUNET_OK on success, #GNUNET_NO if the nonces were different and thus
 *         we failed.
 */
static int
bf_group_merge_cb (struct GNUNET_BLOCK_Group *bg1,
                   const struct GNUNET_BLOCK_Group *bg2)
{
  struct BfGroupInternals *gi1 = bg1->internal_cls;
  struct BfGroupInternals *gi2 = bg2->internal_cls;

  if (gi1->bf_mutator != gi2->bf_mutator)
    return GNUNET_NO;
  if (gi1->bf_size != gi2->bf_size)
    return GNUNET_NO;
  GNUNET_CONTAINER_bloomfilter_or2 (gi1->bf,
                                    gi2->bf);
  return GNUNET_OK;
}


/**
 * Destroy resources used by a block group.
 *
 * @param bg group to destroy, NULL is allowed
 */
static void
bf_group_destroy_cb (struct GNUNET_BLOCK_Group *bg)
{
  struct BfGroupInternals *gi = bg->internal_cls;

  GNUNET_CONTAINER_bloomfilter_free (gi->bf);
  GNUNET_free (gi);
  GNUNET_free (bg);
}


/**
 * Create a new block group that filters duplicates using a Bloom filter.
 *
 * @param ctx block context in which the block group is created
 * @param bf_size size of the Bloom filter
 * @param bf_k K-value for the Bloom filter
 * @param type block type
 * @param nonce random value used to seed the group creation
 * @param raw_data optional serialized prior state of the group, NULL if unavailable/fresh
 * @param raw_data_size number of bytes in @a raw_data, 0 if unavailable/fresh
 * @return block group handle, NULL if block groups are not supported
 *         by this @a type of block (this is not an error)
 */
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)
{
  struct BfGroupInternals *gi;
  struct GNUNET_BLOCK_Group *bg;

  gi = GNUNET_new (struct BfGroupInternals);
  gi->bf = GNUNET_CONTAINER_bloomfilter_init ((bf_size != raw_data_size) ? NULL : raw_data,
                                              bf_size,
                                              bf_k);
  gi->bf_mutator = nonce;
  gi->bf_size = bf_size;
  bg = GNUNET_new (struct GNUNET_BLOCK_Group);
  bg->type = type;
  bg->serialize_cb = &bf_group_serialize_cb;
  bg->mark_seen_cb = &bf_group_mark_seen_cb;
  bg->merge_cb = &bf_group_merge_cb;
  bg->destroy_cb = &bf_group_destroy_cb;
  bg->internal_cls = gi;
  return bg;
}


/**
 * Test if @a hc is contained in the Bloom filter of @a bg.  If so,
 * return #GNUNET_YES.  If not, add @a hc to the Bloom filter and
 * return #GNUNET_NO.
 *
 * @param bg block group to use for testing
 * @param hc hash of element to evaluate
 * @return #GNUNET_YES if @a hc is (likely) a duplicate
 *         #GNUNET_NO if @a hc was definitively not in @bg (but now is)
 */
int
GNUNET_BLOCK_GROUP_bf_test_and_set (struct GNUNET_BLOCK_Group *bg,
                                    const struct GNUNET_HashCode *hc)
{
  struct BfGroupInternals *gi;
  struct GNUNET_HashCode mhash;

  if (NULL == bg)
    return GNUNET_NO;
  gi = bg->internal_cls;
  GNUNET_BLOCK_mingle_hash (hc,
                            gi->bf_mutator,
                            &mhash);
  if (GNUNET_YES ==
      GNUNET_CONTAINER_bloomfilter_test (gi->bf,
                                         &mhash))
    return GNUNET_YES;
  GNUNET_CONTAINER_bloomfilter_add (gi->bf,
                                    &mhash);
  return GNUNET_NO;
}


/**
 * 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).
 *
 * Since other peers will also add entries but not resize the filter,
 * we should generally pick a slightly larger size than what the
 * strict math would suggest.
 *
 * @param entry_count expected number of entries in the Bloom filter
 * @param k number of bits set per entry
 * @return must be a power of two and smaller or equal to 2^15.
 */
size_t
GNUNET_BLOCK_GROUP_compute_bloomfilter_size (unsigned int entry_count,
                                             unsigned int k)
{
  size_t size;
  unsigned int ideal = (entry_count * k) / 4;
  uint16_t max = 1 << 15;

  if (entry_count > max)
    return max;
  size = 8;
  while ((size < max) && (size < ideal))
    size *= 2;
  if (size > max)
    return max;
  return size;
}


/* end of bg_bf.c */