src/block/bg_bf.c

   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  */
  35 struct 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  */
  64 static int
  65 bf_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  */
  98 static void
  99 bf_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  */
 127 static int
 128 bf_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  */
 149 static void
 150 bf_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  */
 173 struct GNUNET_BLOCK_Group *
 174 GNUNET_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  */
 213 int
 214 GNUNET_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  */
 249 size_t
 250 GNUNET_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 */