bg_bf.c

Go to the documentation of this file.

/*
     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 Affero General Public License as published
     by the Free Software Foundation, either version 3 of the License,
     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
     Affero General Public License for more details.
 
     You should have received a copy of the GNU Affero General Public License
     along with this program.  If not, see <http://www.gnu.org/licenses/>.
 
     SPDX-License-Identifier: AGPL3.0-or-later
 */
#include "platform.h"
#include "gnunet_util_lib.h"
#include "gnunet_block_group_lib.h"
#include "gnunet_block_plugin.h"
 
 
struct BfGroupInternals
{
  struct GNUNET_CONTAINER_BloomFilter *bf;
 
  uint32_t bf_mutator;
 
  uint32_t bf_size;
};
 
 
static enum GNUNET_GenericReturnValue
bf_group_serialize_cb (struct GNUNET_BLOCK_Group *bg,
                       void **raw_data,
                       size_t *raw_data_size)
{
  struct BfGroupInternals *gi = bg->internal_cls;
  void *raw;
 
  raw = GNUNET_malloc (gi->bf_size + sizeof (uint32_t));
  if (GNUNET_OK !=
      GNUNET_CONTAINER_bloomfilter_get_raw_data (gi->bf,
                                                 raw + sizeof (uint32_t),
                                                 gi->bf_size))
  {
    GNUNET_free (raw);
    GNUNET_break (0);
    return GNUNET_SYSERR;
  }
  memcpy (raw,
          &gi->bf_mutator,
          sizeof (uint32_t));
  *raw_data = raw;
  *raw_data_size = gi->bf_size + sizeof (uint32_t);
  return GNUNET_OK;
}
 
 
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);
  }
}
 
 
static enum GNUNET_GenericReturnValue
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;
}
 
 
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);
}
 
 
struct GNUNET_BLOCK_Group *
GNUNET_BLOCK_GROUP_bf_create (void *cls,
                              size_t bf_size,
                              unsigned int bf_k,
                              enum GNUNET_BLOCK_Type type,
                              const void *raw_data,
                              size_t raw_data_size)
{
  struct BfGroupInternals *gi;
  struct GNUNET_BLOCK_Group *bg;
  uint32_t nonce;
 
  if ( (NULL != raw_data) &&
       (raw_data_size < sizeof (nonce)) )
  {
    GNUNET_break_op (0);
    return NULL;
  }
  if (NULL != raw_data)
  {
    memcpy (&nonce,
            raw_data,
            sizeof (nonce));
    raw_data += sizeof (nonce);
    raw_data_size -= sizeof (nonce);
  }
  else
  {
    nonce = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_NONCE,
                                      UINT32_MAX);
  }
  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;
}
 
 
enum GNUNET_GenericReturnValue
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;
}
 
 
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 */