gnunet-service-setu_strata_estimator.c File Reference

#include "platform.h"
#include "gnunet_util_lib.h"
#include "ibf.h"
#include "gnunet-service-setu_strata_estimator.h"

Include dependency graph for gnunet-service-setu_strata_estimator.c:

Go to the source code of this file.

Macros
#define	FAIL_10_1_COMPATIBILTIY   1
	Should we try compressing the strata estimator? This will break compatibility with the 0.10.1-network. More...
#define	MULTI_SE_BASE_COUNT   8
	Number of strata estimators in memory NOT transmitted. More...
#define	AVG_BYTE_SIZE_SE   4221
	The avg size of 1 se Based on the bsc thesis of Elias Summermatter (2021) More...

Functions
uint8_t	determine_strata_count (uint64_t avg_element_size, uint64_t element_count)
	Calculates the optimal number of strata Estimators to send. More...
static void	salt_key (const struct IBF_Key *k_in, uint32_t salt, struct IBF_Key *k_out)
	Modify an IBF key k_in based on the salt, returning a salted key in k_out. More...
static void	unsalt_key (const struct IBF_Key *k_in, uint32_t salt, struct IBF_Key *k_out)
	Reverse modification done in the salt_key function. More...
size_t	strata_estimator_write (struct MultiStrataEstimator *se, uint16_t se_ibf_total_size, uint8_t number_se_send, void *buf)
	Write the given strata estimator to the buffer. More...
int	strata_estimator_read (const void *buf, size_t buf_len, int is_compressed, uint8_t number_se_received, uint16_t se_ibf_total_size, struct MultiStrataEstimator *se)
	Read strata from the buffer into the given strata estimator. More...
void	strata_estimator_insert (struct MultiStrataEstimator *se, struct IBF_Key key)
	Add a key to the strata estimator. More...
void	strata_estimator_remove (struct MultiStrataEstimator *se, struct IBF_Key key)
	Remove a key from the strata estimator. More...
struct MultiStrataEstimator *	strata_estimator_create (unsigned int strata_count, uint32_t ibf_size, uint8_t ibf_hashnum)
	Create a new strata estimator with the given parameters. More...
void	strata_estimator_difference (const struct MultiStrataEstimator *se1, const struct MultiStrataEstimator *se2)
	Estimate set difference with two strata estimators, i.e. More...
struct MultiStrataEstimator *	strata_estimator_dup (struct MultiStrataEstimator *se)
	Make a copy of a strata estimator. More...
void	strata_estimator_destroy (struct MultiStrataEstimator *se)
	Destroy a strata estimator, free all of its resources. More...

Macro Definition Documentation

FAIL_10_1_COMPATIBILTIY

#define FAIL_10_1_COMPATIBILTIY   1

Should we try compressing the strata estimator? This will break compatibility with the 0.10.1-network.

Definition at line 37 of file gnunet-service-setu_strata_estimator.c.

MULTI_SE_BASE_COUNT

#define MULTI_SE_BASE_COUNT   8

Number of strata estimators in memory NOT transmitted.

Definition at line 43 of file gnunet-service-setu_strata_estimator.c.

AVG_BYTE_SIZE_SE

#define AVG_BYTE_SIZE_SE   4221

The avg size of 1 se Based on the bsc thesis of Elias Summermatter (2021)

Definition at line 50 of file gnunet-service-setu_strata_estimator.c.

Function Documentation

determine_strata_count()

uint8_t determine_strata_count	(	uint64_t	avg_element_size,
		uint64_t	element_count
	)

Calculates the optimal number of strata Estimators to send.

Deteminate how many strata estimators in the message are necessary.

Parameters

avg_element_size
element_count

Returns

Definition at line 59 of file gnunet-service-setu_strata_estimator.c.

{
  uint64_t base_size = avg_element_size * element_count;
  /* >67kb total size of elements in set */
  if (base_size < AVG_BYTE_SIZE_SE * 16)
    return 1;
  /* >270kb total size of elements in set  */
  if (base_size < AVG_BYTE_SIZE_SE * 64)
    return 2;
  /* >1mb total size of elements in set */
  if (base_size < AVG_BYTE_SIZE_SE * 256)
    return 4;
  return 8;
}

References AVG_BYTE_SIZE_SE.

Referenced by handle_client_accept().

Here is the caller graph for this function:

salt_key()

static void salt_key ( const struct IBF_Key *  k_in, uint32_t  salt, struct IBF_Key *  k_out  )

static

Modify an IBF key k_in based on the salt, returning a salted key in k_out.

Definition at line 80 of file gnunet-service-setu_strata_estimator.c.

{
  int s = (salt * 7) % 64;
  uint64_t x = k_in->key_val;
 
  /* rotate ibf key */
  if (s > 0)
    x = (x >> s) | (x << (64 - s));
  k_out->key_val = x;
}

References IBF_Key::key_val, and salt.

Referenced by strata_estimator_insert().

Here is the caller graph for this function:

unsalt_key()

static void unsalt_key ( const struct IBF_Key *  k_in, uint32_t  salt, struct IBF_Key *  k_out  )

static

Reverse modification done in the salt_key function.

Definition at line 98 of file gnunet-service-setu_strata_estimator.c.

{
  int s = (salt * 7) % 64;
  uint64_t x = k_in->key_val;
 
  x = (x << s) | (x >> (64 - s));
  k_out->key_val = x;
}

References IBF_Key::key_val, and salt.

Referenced by strata_estimator_remove().

Here is the caller graph for this function:

strata_estimator_write()

size_t strata_estimator_write	(	struct MultiStrataEstimator *	se,
		uint16_t	se_ibf_total_size,
		uint8_t	number_se_send,
		void *	buf
	)

Write the given strata estimator to the buffer.

Parameters

	se	strata estimator to serialize
[out]	buf	buffer to write to, must be of appropriate size

Returns

number of bytes written to buf

Definition at line 118 of file gnunet-service-setu_strata_estimator.c.

{
  char *sbuf = buf;
  unsigned int i;
  size_t osize;
  uint64_t sbuf_offset = 0;
  se->size = number_se_send;
 
  GNUNET_assert (NULL != se);
  for (uint8_t strata_ctr = 0; strata_ctr < number_se_send; strata_ctr++)
  {
    for (i = 0; i < se->stratas[strata_ctr]->strata_count; i++)
    {
      ibf_write_slice (se->stratas[strata_ctr]->strata[i],
                       0,
                       se->stratas[strata_ctr]->ibf_size,
                       &sbuf[sbuf_offset],
                       8);
      sbuf_offset += se->stratas[strata_ctr]->ibf_size * IBF_BUCKET_SIZE;
    }
  }
  osize = ((se_ibf_total_size / 8) * number_se_send) * IBF_BUCKET_SIZE
          * se->stratas[0]->strata_count;
#if FAIL_10_1_COMPATIBILTIY
  {
    char *cbuf;
    size_t nsize;
 
    if (GNUNET_YES ==
        GNUNET_try_compression (buf,
                                osize,
                                &cbuf,
                                &nsize))
    {
      GNUNET_memcpy (buf,  cbuf, nsize);
      osize = nsize;
      GNUNET_free (cbuf);
    }
  }
#endif
  return osize;
}

References buf, GNUNET_assert, GNUNET_free, GNUNET_memcpy, GNUNET_try_compression(), GNUNET_YES, IBF_BUCKET_SIZE, StrataEstimator::ibf_size, ibf_write_slice(), MultiStrataEstimator::size, StrataEstimator::strata, StrataEstimator::strata_count, and MultiStrataEstimator::stratas.

Here is the call graph for this function:

strata_estimator_read()

int strata_estimator_read	(	const void *	buf,
		size_t	buf_len,
		int	is_compressed,
		uint8_t	number_se_received,
		uint16_t	se_ibf_total_size,
		struct MultiStrataEstimator *	se
	)

Read strata from the buffer into the given strata estimator.

The strata estimator must already be allocated.

Parameters

	buf	buffer to read from
	buf_len	number of bytes in buf
	is_compressed	is the data compressed?
[out]	se	strata estimator to write to

Returns

GNUNET_OK on success

Definition at line 176 of file gnunet-service-setu_strata_estimator.c.

{
  unsigned int i;
  size_t osize;
  char *dbuf;
 
  dbuf = NULL;
  if (GNUNET_YES == is_compressed)
  {
    osize = ((se_ibf_total_size / 8) * number_se_received) * IBF_BUCKET_SIZE
            * se->stratas[0]->strata_count;
    dbuf = GNUNET_decompress (buf,
                              buf_len,
                              osize);
    if (NULL == dbuf)
    {
      GNUNET_break_op (0);    /* bad compressed input data */
      return GNUNET_SYSERR;
    }
    buf = dbuf;
    buf_len = osize;
  }
 
  if (buf_len != se->stratas[0]->strata_count * ((se_ibf_total_size / 8)
                                                 * number_se_received)
      * IBF_BUCKET_SIZE)
  {
    GNUNET_break (0);  /* very odd error */
    GNUNET_free (dbuf);
    return GNUNET_SYSERR;
  }
 
  for (uint8_t strata_ctr = 0; strata_ctr < number_se_received; strata_ctr++)
  {
    for (i = 0; i < se->stratas[strata_ctr]->strata_count; i++)
    {
      ibf_read_slice (buf, 0, se->stratas[strata_ctr]->ibf_size,
                      se->stratas[strata_ctr]->strata[i], 8);
      buf += se->stratas[strata_ctr]->ibf_size * IBF_BUCKET_SIZE;
    }
  }
  se->size = number_se_received;
  GNUNET_free (dbuf);
  return GNUNET_OK;
}

References buf, GNUNET_break, GNUNET_break_op, GNUNET_decompress(), GNUNET_free, GNUNET_OK, GNUNET_SYSERR, GNUNET_YES, IBF_BUCKET_SIZE, ibf_read_slice(), StrataEstimator::ibf_size, MultiStrataEstimator::size, StrataEstimator::strata, StrataEstimator::strata_count, and MultiStrataEstimator::stratas.

Here is the call graph for this function:

strata_estimator_insert()

void strata_estimator_insert	(	struct MultiStrataEstimator *	se,
		struct IBF_Key	key
	)

Add a key to the strata estimator.

Parameters

se	strata estimator to add the key to
key	key to add

Definition at line 235 of file gnunet-service-setu_strata_estimator.c.

{
 
 
  /* count trailing '1'-bits of v */
  for (int strata_ctr = 0; strata_ctr < MULTI_SE_BASE_COUNT; strata_ctr++)
  {
    unsigned int i;
    uint64_t v;
 
    struct IBF_Key salted_key;
    salt_key (&key,
              strata_ctr * (64 / MULTI_SE_BASE_COUNT),
              &salted_key);
    v = salted_key.key_val;
    for (i = 0; v & 1; v >>= 1, i++)
    {
      ibf_insert (se->stratas[strata_ctr]->strata[i], salted_key);
    }
  }
  /* empty */;
 
}

References ibf_insert(), key, IBF_Key::key_val, MULTI_SE_BASE_COUNT, salt_key(), StrataEstimator::strata, and MultiStrataEstimator::stratas.

Here is the call graph for this function:

strata_estimator_remove()

void strata_estimator_remove	(	struct MultiStrataEstimator *	se,
		struct IBF_Key	key
	)

Remove a key from the strata estimator.

(NOT USED)

Parameters

se	strata estimator to remove the key from
key	key to remove

Definition at line 268 of file gnunet-service-setu_strata_estimator.c.

{
 
  /* count trailing '1'-bits of v */
  for (int strata_ctr = 0; strata_ctr < se->size; strata_ctr++)
  {
    uint64_t v;
    unsigned int i;
 
    struct IBF_Key unsalted_key;
    unsalt_key (&key,
                strata_ctr * (64 / MULTI_SE_BASE_COUNT),
                &unsalted_key);
 
    v = unsalted_key.key_val;
    for (i = 0; v & 1; v >>= 1, i++)
    {
      /* empty */;
      ibf_remove (se->stratas[strata_ctr]->strata[i], unsalted_key);
    }
  }
}

References ibf_remove(), key, IBF_Key::key_val, MULTI_SE_BASE_COUNT, MultiStrataEstimator::size, StrataEstimator::strata, MultiStrataEstimator::stratas, and unsalt_key().

Here is the call graph for this function:

strata_estimator_create()

struct MultiStrataEstimator* strata_estimator_create	(	unsigned int	strata_count,
		uint32_t	ibf_size,
		uint8_t	ibf_hashnum
	)

Create a new strata estimator with the given parameters.

Parameters

strata_count	number of stratas, that is, number of ibfs in the estimator
ibf_size	size of each ibf stratum
ibf_hashnum	hashnum parameter of each ibf

Returns

a freshly allocated, empty strata estimator, NULL on error

Definition at line 302 of file gnunet-service-setu_strata_estimator.c.

{
  struct MultiStrataEstimator *se;
  unsigned int i;
  unsigned int j;
  se = GNUNET_new (struct MultiStrataEstimator);
 
  se->size = MULTI_SE_BASE_COUNT;
  se->stratas = GNUNET_new_array (MULTI_SE_BASE_COUNT,struct StrataEstimator *);
 
  uint8_t ibf_prime_sizes[] = {79,79,79,79,79,79,79,79};
 
  for (uint8_t strata_ctr = 0; strata_ctr < MULTI_SE_BASE_COUNT; strata_ctr++)
  {
    se->stratas[strata_ctr] = GNUNET_new (struct StrataEstimator);
    se->stratas[strata_ctr]->strata_count = strata_count;
    se->stratas[strata_ctr]->ibf_size = ibf_prime_sizes[strata_ctr];
    se->stratas[strata_ctr]->strata = GNUNET_new_array (strata_count * 4,
                                                        struct
                                                        InvertibleBloomFilter *);
    for (i = 0; i < strata_count; i++)
    {
      se->stratas[strata_ctr]->strata[i] = ibf_create (
        ibf_prime_sizes[strata_ctr], ibf_hashnum);
      if (NULL == se->stratas[strata_ctr]->strata[i])
      {
        GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
                    "Failed to allocate memory for strata estimator\n");
        for (j = 0; j < i; j++)
          ibf_destroy (se->stratas[strata_ctr]->strata[i]);
        GNUNET_free (se);
        return NULL;
      }
    }
  }
  return se;
}

References GNUNET_ERROR_TYPE_ERROR, GNUNET_free, GNUNET_log, GNUNET_new, GNUNET_new_array, ibf_create(), ibf_destroy(), StrataEstimator::ibf_size, MULTI_SE_BASE_COUNT, MultiStrataEstimator::size, StrataEstimator::strata, StrataEstimator::strata_count, and MultiStrataEstimator::stratas.

Here is the call graph for this function:

strata_estimator_difference()

void strata_estimator_difference	(	const struct MultiStrataEstimator *	se1,
		const struct MultiStrataEstimator *	se2
	)

Estimate set difference with two strata estimators, i.e.

Get an estimation of the symmetric difference of the elements contained in both strata estimators.

arrays of IBFs. Does not not modify its arguments.

Parameters

se1	first strata estimator
se2	second strata estimator

Returns

the estimated difference

Definition at line 353 of file gnunet-service-setu_strata_estimator.c.

{
  int avg_local_diff = 0;
  int avg_remote_diff = 0;
  uint8_t number_of_estimators = se1->size;
 
  for (uint8_t strata_ctr = 0; strata_ctr < number_of_estimators; strata_ctr++)
  {
    GNUNET_assert (se1->stratas[strata_ctr]->strata_count ==
                   se2->stratas[strata_ctr]->strata_count);
 
 
    for (int i = se1->stratas[strata_ctr]->strata_count - 1; i >= 0; i--)
    {
      struct InvertibleBloomFilter *diff;
      /* number of keys decoded from the ibf */
 
      /* FIXME: implement this without always allocating new IBFs */
      diff = ibf_dup (se1->stratas[strata_ctr]->strata[i]);
      diff->local_decoded_count = 0;
      diff->remote_decoded_count = 0;
 
      ibf_subtract (diff, se2->stratas[strata_ctr]->strata[i]);
 
      for (int ibf_count = 0; GNUNET_YES; ibf_count++)
      {
        int more;
 
        more = ibf_decode (diff, NULL, NULL);
        if (GNUNET_NO == more)
        {
          se1->stratas[strata_ctr]->strata[0]->local_decoded_count +=
            diff->local_decoded_count;
          se1->stratas[strata_ctr]->strata[0]->remote_decoded_count +=
            diff->remote_decoded_count;
          break;
        }
        /* Estimate if decoding fails or would not terminate */
        if ((GNUNET_SYSERR == more) || (ibf_count > diff->size))
        {
          se1->stratas[strata_ctr]->strata[0]->local_decoded_count =
            se1->stratas[strata_ctr]->strata[0]->local_decoded_count * (1 << (i
                                                                              +
                                                                              1));
          se1->stratas[strata_ctr]->strata[0]->remote_decoded_count =
            se1->stratas[strata_ctr]->strata[0]->remote_decoded_count * (1 << (i
                                                                               +
                                                                               1));
          ibf_destroy (diff);
          goto break_all_counting_loops;
        }
      }
      ibf_destroy (diff);
    }
break_all_counting_loops:;
    avg_local_diff += se1->stratas[strata_ctr]->strata[0]->local_decoded_count;
    avg_remote_diff +=
      se1->stratas[strata_ctr]->strata[0]->remote_decoded_count;
  }
  se1->stratas[0]->strata[0]->local_decoded_count = avg_local_diff
                                                    / number_of_estimators;
  se1->stratas[0]->strata[0]->remote_decoded_count = avg_remote_diff
                                                     / number_of_estimators;
}

References GNUNET_assert, GNUNET_NO, GNUNET_SYSERR, GNUNET_YES, ibf_decode(), ibf_destroy(), ibf_dup(), ibf_subtract(), InvertibleBloomFilter::local_decoded_count, InvertibleBloomFilter::remote_decoded_count, InvertibleBloomFilter::size, MultiStrataEstimator::size, StrataEstimator::strata, StrataEstimator::strata_count, and MultiStrataEstimator::stratas.

Here is the call graph for this function:

strata_estimator_dup()

struct MultiStrataEstimator* strata_estimator_dup

(

struct MultiStrataEstimator *

se

)

Make a copy of a strata estimator.

Parameters

se	the strata estimator to copy

Returns

the copy

Definition at line 427 of file gnunet-service-setu_strata_estimator.c.

{
  struct MultiStrataEstimator *c;
  unsigned int i;
 
  c = GNUNET_new (struct MultiStrataEstimator);
  c->stratas = GNUNET_new_array (MULTI_SE_BASE_COUNT,struct StrataEstimator *);
  for (uint8_t strata_ctr = 0; strata_ctr < MULTI_SE_BASE_COUNT; strata_ctr++)
  {
    c->stratas[strata_ctr] = GNUNET_new (struct StrataEstimator);
    c->stratas[strata_ctr]->strata_count =
      se->stratas[strata_ctr]->strata_count;
    c->stratas[strata_ctr]->ibf_size = se->stratas[strata_ctr]->ibf_size;
    c->stratas[strata_ctr]->strata = GNUNET_new_array (
      se->stratas[strata_ctr]->strata_count,
      struct
      InvertibleBloomFilter *);
    for (i = 0; i < se->stratas[strata_ctr]->strata_count; i++)
      c->stratas[strata_ctr]->strata[i] = ibf_dup (
        se->stratas[strata_ctr]->strata[i]);
  }
  return c;
}

References GNUNET_new, GNUNET_new_array, ibf_dup(), StrataEstimator::ibf_size, MULTI_SE_BASE_COUNT, StrataEstimator::strata, StrataEstimator::strata_count, and MultiStrataEstimator::stratas.

Here is the call graph for this function:

strata_estimator_destroy()

void strata_estimator_destroy

(

struct MultiStrataEstimator *

se

)

Destroy a strata estimator, free all of its resources.

Parameters

se	strata estimator to destroy.

Definition at line 458 of file gnunet-service-setu_strata_estimator.c.

{
  unsigned int i;
  for (uint8_t strata_ctr = 0; strata_ctr < MULTI_SE_BASE_COUNT; strata_ctr++)
  {
    for (i = 0; i < se->stratas[strata_ctr]->strata_count; i++)
      ibf_destroy (se->stratas[strata_ctr]->strata[i]);
    GNUNET_free (se->stratas[strata_ctr]->strata);
  }
  GNUNET_free (se);
}

References GNUNET_free, ibf_destroy(), MULTI_SE_BASE_COUNT, StrataEstimator::strata, StrataEstimator::strata_count, and MultiStrataEstimator::stratas.

Here is the call graph for this function: