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