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
   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.
   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      General Public License for more details.
  14
  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.
  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 /**
  56  * Serialize state of a block group.
  57  *
  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
  64  */
  65 static int
  66 bf_group_serialize_cb (struct GNUNET_BLOCK_Group *bg,
  67                        uint32_t *nonce,
  68                        void **raw_data,
  69                        size_t *raw_data_size)
  70 {
  71   struct BfGroupInternals *gi = bg->internal_cls;
  72   char *raw;
  73
  74   raw = GNUNET_malloc (gi->bf_size);
  75   if (GNUNET_OK !=
  76       GNUNET_CONTAINER_bloomfilter_get_raw_data (gi->bf,
  77                                                  raw,
  78                                                  gi->bf_size))
  79   {
  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) ? NULL : raw_data,
 187                                               bf_size,
 188                                               bf_k);
 189   gi->bf_mutator = nonce;
 190   gi->bf_size = bf_size;
 191   bg = GNUNET_new (struct GNUNET_BLOCK_Group);
 192   bg->type = type;
 193   bg->serialize_cb = &bf_group_serialize_cb;
 194   bg->mark_seen_cb = &bf_group_mark_seen_cb;
 195   bg->merge_cb = &bf_group_merge_cb;
 196   bg->destroy_cb = &bf_group_destroy_cb;
 197   bg->internal_cls = gi;
 198   return bg;
 199 }
 200
 201
 202 /**
 203  * Test if @a hc is contained in the Bloom filter of @a bg.  If so,
 204  * return #GNUNET_YES.  If not, add @a hc to the Bloom filter and
 205  * return #GNUNET_NO.
 206  *
 207  * @param bg block group to use for testing
 208  * @param hc hash of element to evaluate
 209  * @return #GNUNET_YES if @a hc is (likely) a duplicate
 210  *         #GNUNET_NO if @a hc was definitively not in @bg (but now is)
 211  */
 212 int
 213 GNUNET_BLOCK_GROUP_bf_test_and_set (struct GNUNET_BLOCK_Group *bg,
 214                                     const struct GNUNET_HashCode *hc)
 215 {
 216   struct BfGroupInternals *gi;
 217   struct GNUNET_HashCode mhash;
 218
 219   if (NULL == bg)
 220     return GNUNET_NO;
 221   gi = bg->internal_cls;
 222   GNUNET_BLOCK_mingle_hash (hc,
 223                             gi->bf_mutator,
 224                             &mhash);
 225   if (GNUNET_YES ==
 226       GNUNET_CONTAINER_bloomfilter_test (gi->bf,
 227                                          &mhash))
 228     return GNUNET_YES;
 229   GNUNET_CONTAINER_bloomfilter_add (gi->bf,
 230                                     &mhash);
 231   return GNUNET_NO;
 232 }
 233
 234
 235 /**
 236  * How many bytes should a bloomfilter be if we have already seen
 237  * entry_count responses?  Sized so that do not have to
 238  * re-size the filter too often (to keep it cheap).
 239  *
 240  * Since other peers will also add entries but not resize the filter,
 241  * we should generally pick a slightly larger size than what the
 242  * strict math would suggest.
 243  *
 244  * @param entry_count expected number of entries in the Bloom filter
 245  * @param k number of bits set per entry
 246  * @return must be a power of two and smaller or equal to 2^15.
 247  */
 248 size_t
 249 GNUNET_BLOCK_GROUP_compute_bloomfilter_size (unsigned int entry_count,
 250                                              unsigned int k)
 251 {
 252   size_t size;
 253   unsigned int ideal = (entry_count * k) / 4;
 254   uint16_t max = 1 << 15;
 255
 256   if (entry_count > max)
 257     return max;
 258   size = 8;
 259   while ((size < max) && (size < ideal))
 260     size *= 2;
 261   if (size > max)
 262     return max;
 263   return size;
 264 }
 265
 266
 267 /* end of bg_bf.c */