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 /**
  16  * @file block/bg_bf.c
  17  * @brief implementation of a block group using a Bloom filter
  18  *        to drop duplicate blocks
  19  * @author Christian Grothoff
  20  */
  21 #include "platform.h"
  22 #include "gnunet_util_lib.h"
  23 #include "gnunet_block_group_lib.h"
  24 #include "gnunet_block_plugin.h"
  25
  26
  27 /**
  28  * Internal data structure for a block group.
  29  */
  30 struct BfGroupInternals
  31 {
  32   /**
  33    * A Bloom filter to weed out duplicate replies probabilistically.
  34    */
  35   struct GNUNET_CONTAINER_BloomFilter *bf;
  36
  37   /**
  38    * Set from the nonce to mingle the hashes before going into the @e bf.
  39    */
  40   uint32_t bf_mutator;
  41
  42   /**
  43    * Size of @a bf.
  44    */
  45   uint32_t bf_size;
  46
  47 };
  48
  49
  50 /**
  51  * Serialize state of a block group.
  52  *
  53  * @param bg group to serialize
  54  * @param[out] nonce set to the nonce of the @a bg
  55  * @param[out] raw_data set to the serialized state
  56  * @param[out] raw_data_size set to the number of bytes in @a raw_data
  57  * @return #GNUNET_OK on success, #GNUNET_NO if serialization is not
  58  *         supported, #GNUNET_SYSERR on error
  59  */
  60 static int
  61 bf_group_serialize_cb (struct GNUNET_BLOCK_Group *bg,
  62                        uint32_t *nonce,
  63                        void **raw_data,
  64                        size_t *raw_data_size)
  65 {
  66   struct BfGroupInternals *gi = bg->internal_cls;
  67   char *raw;
  68
  69   raw = GNUNET_malloc (gi->bf_size);
  70   if (GNUNET_OK !=
  71       GNUNET_CONTAINER_bloomfilter_get_raw_data (gi->bf,
  72                                                  raw,
  73                                                  gi->bf_size))
  74   {
  75     GNUNET_free (raw);
  76     GNUNET_break (0);
  77     return GNUNET_SYSERR;
  78   }
  79   *nonce = gi->bf_mutator;
  80   *raw_data = raw;
  81   *raw_data_size = gi->bf_size;
  82   return GNUNET_OK;
  83 }
  84
  85
  86 /**
  87  * Mark elements as "seen" using a hash of the element. Not supported
  88  * by all block plugins.
  89  *
  90  * @param bg group to update
  91  * @param seen_results results already seen
  92  * @param seen_results_count number of entries in @a seen_results
  93  */
  94 static void
  95 bf_group_mark_seen_cb (struct GNUNET_BLOCK_Group *bg,
  96                        const struct GNUNET_HashCode *seen_results,
  97                        unsigned int seen_results_count)
  98 {
  99   struct BfGroupInternals *gi = bg->internal_cls;
 100
 101   for (unsigned int i=0;i<seen_results_count;i++)
 102   {
 103     struct GNUNET_HashCode mhash;
 104
 105     GNUNET_BLOCK_mingle_hash (&seen_results[i],
 106                               gi->bf_mutator,
 107                               &mhash);
 108     GNUNET_CONTAINER_bloomfilter_add (gi->bf,
 109                                       &mhash);
 110   }
 111 }
 112
 113
 114 /**
 115  * Merge two groups, if possible. Not supported by all block plugins,
 116  * can also fail if the nonces were different.
 117  *
 118  * @param bg1 group to update
 119  * @param bg2 group to merge into @a bg1
 120  * @return #GNUNET_OK on success, #GNUNET_NO if the nonces were different and thus
 121  *         we failed.
 122  */
 123 static int
 124 bf_group_merge_cb (struct GNUNET_BLOCK_Group *bg1,
 125                    const struct GNUNET_BLOCK_Group *bg2)
 126 {
 127   struct BfGroupInternals *gi1 = bg1->internal_cls;
 128   struct BfGroupInternals *gi2 = bg2->internal_cls;
 129
 130   if (gi1->bf_mutator != gi2->bf_mutator)
 131     return GNUNET_NO;
 132   if (gi1->bf_size != gi2->bf_size)
 133     return GNUNET_NO;
 134   GNUNET_CONTAINER_bloomfilter_or2 (gi1->bf,
 135                                     gi2->bf);
 136   return GNUNET_OK;
 137 }
 138
 139
 140 /**
 141  * Destroy resources used by a block group.
 142  *
 143  * @param bg group to destroy, NULL is allowed
 144  */
 145 static void
 146 bf_group_destroy_cb (struct GNUNET_BLOCK_Group *bg)
 147 {
 148   struct BfGroupInternals *gi = bg->internal_cls;
 149
 150   GNUNET_CONTAINER_bloomfilter_free (gi->bf);
 151   GNUNET_free (gi);
 152   GNUNET_free (bg);
 153 }
 154
 155
 156 /**
 157  * Create a new block group that filters duplicates using a Bloom filter.
 158  *
 159  * @param ctx block context in which the block group is created
 160  * @param bf_size size of the Bloom filter
 161  * @param bf_k K-value for the Bloom filter
 162  * @param type block type
 163  * @param nonce random value used to seed the group creation
 164  * @param raw_data optional serialized prior state of the group, NULL if unavailable/fresh
 165  * @param raw_data_size number of bytes in @a raw_data, 0 if unavailable/fresh
 166  * @return block group handle, NULL if block groups are not supported
 167  *         by this @a type of block (this is not an error)
 168  */
 169 struct GNUNET_BLOCK_Group *
 170 GNUNET_BLOCK_GROUP_bf_create (void *cls,
 171                               size_t bf_size,
 172                               unsigned int bf_k,
 173                               enum GNUNET_BLOCK_Type type,
 174                               uint32_t nonce,
 175                               const void *raw_data,
 176                               size_t raw_data_size)
 177 {
 178   struct BfGroupInternals *gi;
 179   struct GNUNET_BLOCK_Group *bg;
 180
 181   gi = GNUNET_new (struct BfGroupInternals);
 182   gi->bf = GNUNET_CONTAINER_bloomfilter_init ((bf_size != raw_data_size) ? NULL : raw_data,
 183                                               bf_size,
 184                                               bf_k);
 185   gi->bf_mutator = nonce;
 186   gi->bf_size = bf_size;
 187   bg = GNUNET_new (struct GNUNET_BLOCK_Group);
 188   bg->type = type;
 189   bg->serialize_cb = &bf_group_serialize_cb;
 190   bg->mark_seen_cb = &bf_group_mark_seen_cb;
 191   bg->merge_cb = &bf_group_merge_cb;
 192   bg->destroy_cb = &bf_group_destroy_cb;
 193   bg->internal_cls = gi;
 194   return bg;
 195 }
 196
 197
 198 /**
 199  * Test if @a hc is contained in the Bloom filter of @a bg.  If so,
 200  * return #GNUNET_YES.  If not, add @a hc to the Bloom filter and
 201  * return #GNUNET_NO.
 202  *
 203  * @param bg block group to use for testing
 204  * @param hc hash of element to evaluate
 205  * @return #GNUNET_YES if @a hc is (likely) a duplicate
 206  *         #GNUNET_NO if @a hc was definitively not in @bg (but now is)
 207  */
 208 int
 209 GNUNET_BLOCK_GROUP_bf_test_and_set (struct GNUNET_BLOCK_Group *bg,
 210                                     const struct GNUNET_HashCode *hc)
 211 {
 212   struct BfGroupInternals *gi;
 213   struct GNUNET_HashCode mhash;
 214
 215   if (NULL == bg)
 216     return GNUNET_NO;
 217   gi = bg->internal_cls;
 218   GNUNET_BLOCK_mingle_hash (hc,
 219                             gi->bf_mutator,
 220                             &mhash);
 221   if (GNUNET_YES ==
 222       GNUNET_CONTAINER_bloomfilter_test (gi->bf,
 223                                          &mhash))
 224     return GNUNET_YES;
 225   GNUNET_CONTAINER_bloomfilter_add (gi->bf,
 226                                     &mhash);
 227   return GNUNET_NO;
 228 }
 229
 230
 231 /**
 232  * How many bytes should a bloomfilter be if we have already seen
 233  * entry_count responses?  Sized so that do not have to
 234  * re-size the filter too often (to keep it cheap).
 235  *
 236  * Since other peers will also add entries but not resize the filter,
 237  * we should generally pick a slightly larger size than what the
 238  * strict math would suggest.
 239  *
 240  * @param entry_count expected number of entries in the Bloom filter
 241  * @param k number of bits set per entry
 242  * @return must be a power of two and smaller or equal to 2^15.
 243  */
 244 size_t
 245 GNUNET_BLOCK_GROUP_compute_bloomfilter_size (unsigned int entry_count,
 246                                              unsigned int k)
 247 {
 248   size_t size;
 249   unsigned int ideal = (entry_count * k) / 4;
 250   uint16_t max = 1 << 15;
 251
 252   if (entry_count > max)
 253     return max;
 254   size = 8;
 255   while ((size < max) && (size < ideal))
 256     size *= 2;
 257   if (size > max)
 258     return max;
 259   return size;
 260 }
 261
 262
 263 /* end of bg_bf.c */