GNUnet  0.20.0
gnunet-service-setu_strata_estimator.h File Reference
#include "platform.h"
#include "gnunet_common.h"
#include "gnunet_util_lib.h"
Include dependency graph for gnunet-service-setu_strata_estimator.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures

struct  StrataEstimator
 A handle to a strata estimator. More...
 
struct  MultiStrataEstimator
 

Functions

uint8_t determine_strata_count (uint64_t avg_element_size, uint64_t element_count)
 Deteminate how many strata estimators in the message are necessary. 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...
 
struct MultiStrataEstimatorstrata_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)
 Get an estimation of the symmetric difference of the elements contained in both strata estimators. 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...
 
void strata_estimator_destroy (struct MultiStrataEstimator *se)
 Destroy a strata estimator, free all of its resources. More...
 
struct MultiStrataEstimatorstrata_estimator_dup (struct MultiStrataEstimator *se)
 Make a copy of a strata estimator. More...
 

Function Documentation

◆ determine_strata_count()

uint8_t determine_strata_count ( uint64_t  avg_element_size,
uint64_t  element_count 
)

Deteminate how many strata estimators in the message are necessary.

Parameters
avg_element_size
element_count
Returns
number of strata's

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.

60 {
61  uint64_t base_size = avg_element_size * element_count;
62  /* >67kb total size of elements in set */
63  if (base_size < AVG_BYTE_SIZE_SE * 16)
64  return 1;
65  /* >270kb total size of elements in set */
66  if (base_size < AVG_BYTE_SIZE_SE * 64)
67  return 2;
68  /* >1mb total size of elements in set */
69  if (base_size < AVG_BYTE_SIZE_SE * 256)
70  return 4;
71  return 8;
72 }
#define AVG_BYTE_SIZE_SE
The avg size of 1 se Based on the bsc thesis of Elias Summermatter (2021)

References AVG_BYTE_SIZE_SE.

Referenced by handle_client_accept().

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
sestrata estimator to serialize
[out]bufbuffer 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.

122 {
123  char *sbuf = buf;
124  unsigned int i;
125  size_t osize;
126  uint64_t sbuf_offset = 0;
127  se->size = number_se_send;
128 
129  GNUNET_assert (NULL != se);
130  for (uint8_t strata_ctr = 0; strata_ctr < number_se_send; strata_ctr++)
131  {
132  for (i = 0; i < se->stratas[strata_ctr]->strata_count; i++)
133  {
134  ibf_write_slice (se->stratas[strata_ctr]->strata[i],
135  0,
136  se->stratas[strata_ctr]->ibf_size,
137  &sbuf[sbuf_offset],
138  8);
139  sbuf_offset += se->stratas[strata_ctr]->ibf_size * IBF_BUCKET_SIZE;
140  }
141  }
142  osize = ((se_ibf_total_size / 8) * number_se_send) * IBF_BUCKET_SIZE
143  * se->stratas[0]->strata_count;
144 #if FAIL_10_1_COMPATIBILTIY
145  {
146  char *cbuf;
147  size_t nsize;
148 
149  if (GNUNET_YES ==
151  osize,
152  &cbuf,
153  &nsize))
154  {
155  GNUNET_memcpy (buf, cbuf, nsize);
156  osize = nsize;
157  GNUNET_free (cbuf);
158  }
159  }
160 #endif
161  return osize;
162 }
static char buf[2048]
int GNUNET_try_compression(const char *data, size_t old_size, char **result, size_t *new_size)
Try to compress the given block of data using libz.
Definition: compress.c:33
#define GNUNET_memcpy(dst, src, n)
Call memcpy() but check for n being 0 first.
@ GNUNET_YES
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
#define GNUNET_free(ptr)
Wrapper around free.
void ibf_write_slice(const struct InvertibleBloomFilter *ibf, uint32_t start, uint32_t count, void *buf)
Write buckets from an ibf to a buffer.
Definition: ibf.c:291
#define IBF_BUCKET_SIZE
Size of one ibf bucket in bytes.
Definition: ibf.h:72
uint8_t size
Number of strata estimators in struct.
struct StrataEstimator ** stratas
Array of strata estimators.
unsigned int ibf_size
Size of each IBF stratum (in bytes)
struct InvertibleBloomFilter ** strata
The IBFs of this strata estimator.
unsigned int strata_count
Size of the IBF array in strata.

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
bufbuffer to read from
buf_lennumber of bytes in buf
is_compressedis the data compressed?
[out]sestrata estimator to write to
Returns
GNUNET_OK on success

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

182 {
183  unsigned int i;
184  size_t osize;
185  char *dbuf;
186 
187  dbuf = NULL;
188  if (GNUNET_YES == is_compressed)
189  {
190  osize = ((se_ibf_total_size / 8) * number_se_received) * IBF_BUCKET_SIZE
191  * se->stratas[0]->strata_count;
192  dbuf = GNUNET_decompress (buf,
193  buf_len,
194  osize);
195  if (NULL == dbuf)
196  {
197  GNUNET_break_op (0); /* bad compressed input data */
198  return GNUNET_SYSERR;
199  }
200  buf = dbuf;
201  buf_len = osize;
202  }
203 
204  if (buf_len != se->stratas[0]->strata_count * ((se_ibf_total_size / 8)
205  * number_se_received)
206  * IBF_BUCKET_SIZE)
207  {
208  GNUNET_break (0); /* very odd error */
209  GNUNET_free (dbuf);
210  return GNUNET_SYSERR;
211  }
212 
213  for (uint8_t strata_ctr = 0; strata_ctr < number_se_received; strata_ctr++)
214  {
215  for (i = 0; i < se->stratas[strata_ctr]->strata_count; i++)
216  {
217  ibf_read_slice (buf, 0, se->stratas[strata_ctr]->ibf_size,
218  se->stratas[strata_ctr]->strata[i], 8);
219  buf += se->stratas[strata_ctr]->ibf_size * IBF_BUCKET_SIZE;
220  }
221  }
222  se->size = number_se_received;
223  GNUNET_free (dbuf);
224  return GNUNET_OK;
225 }
char * GNUNET_decompress(const char *input, size_t input_size, size_t output_size)
Decompress input, return the decompressed data as output.
Definition: compress.c:70
@ GNUNET_OK
@ GNUNET_SYSERR
#define GNUNET_break_op(cond)
Use this for assertion violations caused by other peers (i.e.
#define GNUNET_break(cond)
Use this for internal assertion violations that are not fatal (can be handled) but should not occur.
void ibf_read_slice(const void *buf, uint32_t start, uint32_t count, struct InvertibleBloomFilter *ibf)
Read buckets from a buffer into an ibf.
Definition: ibf.c:324

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_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_countnumber of stratas, that is, number of ibfs in the estimator
ibf_sizesize of each ibf stratum
ibf_hashnumhashnum parameter of each ibf
Returns
a freshly allocated, empty strata estimator, NULL on error

Definition at line 182 of file gnunet-service-set_union_strata_estimator.c.

185 {
186  struct StrataEstimator *se;
187  unsigned int i;
188  unsigned int j;
189 
190  se = GNUNET_new (struct StrataEstimator);
192  se->ibf_size = ibf_size;
194  struct InvertibleBloomFilter *);
195  for (i = 0; i < strata_count; i++)
196  {
197  se->strata[i] = ibf_create (ibf_size, ibf_hashnum);
198  if (NULL == se->strata[i])
199  {
201  "Failed to allocate memory for strata estimator\n");
202  for (j = 0; j < i; j++)
203  ibf_destroy (se->strata[i]);
204  GNUNET_free (se);
205  return NULL;
206  }
207  }
208  return se;
209 }
static unsigned int ibf_size
#define GNUNET_log(kind,...)
@ GNUNET_ERROR_TYPE_ERROR
#define GNUNET_new(type)
Allocate a struct or union of the given type.
#define GNUNET_new_array(n, type)
Allocate a size n array with structs or unions of the given type.
struct InvertibleBloomFilter * ibf_create(uint32_t size, uint8_t hash_num)
Create an invertible bloom filter.
Definition: ibf.c:80
void ibf_destroy(struct InvertibleBloomFilter *ibf)
Destroy all resources associated with the invertible bloom filter.
Definition: ibf.c:404
Invertible bloom filter (IBF).
Definition: ibf.h:83
A handle to a strata estimator.

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

Referenced by handle_client_create_set(), handle_union_p2p_strata_estimator(), and union_set_create().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ strata_estimator_difference()

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

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

Parameters
se1first strata estimator
se2second strata estimator
Returns
nothing

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
se1first strata estimator
se2second strata estimator
Returns
the estimated difference

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

355 {
356  int avg_local_diff = 0;
357  int avg_remote_diff = 0;
358  uint8_t number_of_estimators = se1->size;
359 
360  for (uint8_t strata_ctr = 0; strata_ctr < number_of_estimators; strata_ctr++)
361  {
362  GNUNET_assert (se1->stratas[strata_ctr]->strata_count ==
363  se2->stratas[strata_ctr]->strata_count);
364 
365 
366  for (int i = se1->stratas[strata_ctr]->strata_count - 1; i >= 0; i--)
367  {
368  struct InvertibleBloomFilter *diff;
369  /* number of keys decoded from the ibf */
370 
371  /* FIXME: implement this without always allocating new IBFs */
372  diff = ibf_dup (se1->stratas[strata_ctr]->strata[i]);
373  diff->local_decoded_count = 0;
374  diff->remote_decoded_count = 0;
375 
376  ibf_subtract (diff, se2->stratas[strata_ctr]->strata[i]);
377 
378  for (int ibf_count = 0; GNUNET_YES; ibf_count++)
379  {
380  int more;
381 
382  more = ibf_decode (diff, NULL, NULL);
383  if (GNUNET_NO == more)
384  {
385  se1->stratas[strata_ctr]->strata[0]->local_decoded_count +=
386  diff->local_decoded_count;
387  se1->stratas[strata_ctr]->strata[0]->remote_decoded_count +=
388  diff->remote_decoded_count;
389  break;
390  }
391  /* Estimate if decoding fails or would not terminate */
392  if ((GNUNET_SYSERR == more) || (ibf_count > diff->size))
393  {
394  se1->stratas[strata_ctr]->strata[0]->local_decoded_count =
395  se1->stratas[strata_ctr]->strata[0]->local_decoded_count * (1 << (i
396  +
397  1));
398  se1->stratas[strata_ctr]->strata[0]->remote_decoded_count =
399  se1->stratas[strata_ctr]->strata[0]->remote_decoded_count * (1 << (i
400  +
401  1));
402  ibf_destroy (diff);
403  goto break_all_counting_loops;
404  }
405  }
406  ibf_destroy (diff);
407  }
408 break_all_counting_loops:;
409  avg_local_diff += se1->stratas[strata_ctr]->strata[0]->local_decoded_count;
410  avg_remote_diff +=
411  se1->stratas[strata_ctr]->strata[0]->remote_decoded_count;
412  }
413  se1->stratas[0]->strata[0]->local_decoded_count = avg_local_diff
414  / number_of_estimators;
415  se1->stratas[0]->strata[0]->remote_decoded_count = avg_remote_diff
416  / number_of_estimators;
417 }
@ GNUNET_NO
void ibf_subtract(struct InvertibleBloomFilter *ibf1, const struct InvertibleBloomFilter *ibf2)
Subtract ibf2 from ibf1, storing the result in ibf1.
Definition: ibf.c:357
int ibf_decode(struct InvertibleBloomFilter *ibf, int *ret_side, struct IBF_Key *ret_id)
Decode and remove an element from the IBF, if possible.
Definition: ibf.c:229
struct InvertibleBloomFilter * ibf_dup(const struct InvertibleBloomFilter *ibf)
Create a copy of an IBF, the copy has to be destroyed properly.
Definition: ibf.c:380
int remote_decoded_count
If an IBF is decoded this count stores how many elements are on the remote site.
Definition: ibf.h:108
int local_decoded_count
If an IBF is decoded this count stores how many elements are on the local site.
Definition: ibf.h:101
uint32_t size
How many cells does this IBF have?
Definition: ibf.h:87

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_insert()

void strata_estimator_insert ( struct MultiStrataEstimator se,
struct IBF_Key  key 
)

Add a key to the strata estimator.

Parameters
sestrata estimator to add the key to
keykey to add

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

237 {
238 
239 
240  /* count trailing '1'-bits of v */
241  for (int strata_ctr = 0; strata_ctr < MULTI_SE_BASE_COUNT; strata_ctr++)
242  {
243  unsigned int i;
244  uint64_t v;
245 
246  struct IBF_Key salted_key;
247  salt_key (&key,
248  strata_ctr * (64 / MULTI_SE_BASE_COUNT),
249  &salted_key);
250  v = salted_key.key_val;
251  for (i = 0; v & 1; v >>= 1, i++)
252  {
253  ibf_insert (se->stratas[strata_ctr]->strata[i], salted_key);
254  }
255  }
256  /* empty */;
257 
258 }
struct GNUNET_HashCode key
The key used in the DHT.
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.
#define MULTI_SE_BASE_COUNT
Number of strata estimators in memory NOT transmitted.
void ibf_insert(struct InvertibleBloomFilter *ibf, struct IBF_Key key)
Insert a key into an IBF.
Definition: ibf.c:168
Keys that can be inserted into and removed from an IBF.
Definition: ibf.h:46

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.

Parameters
sestrata estimator to remove the key from
keykey to remove

(NOT USED)

Parameters
sestrata estimator to remove the key from
keykey to remove

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

270 {
271 
272  /* count trailing '1'-bits of v */
273  for (int strata_ctr = 0; strata_ctr < se->size; strata_ctr++)
274  {
275  uint64_t v;
276  unsigned int i;
277 
278  struct IBF_Key unsalted_key;
279  unsalt_key (&key,
280  strata_ctr * (64 / MULTI_SE_BASE_COUNT),
281  &unsalted_key);
282 
283  v = unsalted_key.key_val;
284  for (i = 0; v & 1; v >>= 1, i++)
285  {
286  /* empty */;
287  ibf_remove (se->stratas[strata_ctr]->strata[i], unsalted_key);
288  }
289  }
290 }
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.
void ibf_remove(struct InvertibleBloomFilter *ibf, struct IBF_Key key)
Remove a key from an IBF.
Definition: ibf.c:185

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_destroy()

void strata_estimator_destroy ( struct MultiStrataEstimator se)

Destroy a strata estimator, free all of its resources.

Parameters
sestrata estimator to destroy.

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

459 {
460  unsigned int i;
461  for (uint8_t strata_ctr = 0; strata_ctr < MULTI_SE_BASE_COUNT; strata_ctr++)
462  {
463  for (i = 0; i < se->stratas[strata_ctr]->strata_count; i++)
464  ibf_destroy (se->stratas[strata_ctr]->strata[i]);
465  GNUNET_free (se->stratas[strata_ctr]->strata);
466  }
467  GNUNET_free (se);
468 }

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:

◆ strata_estimator_dup()

struct MultiStrataEstimator* strata_estimator_dup ( struct MultiStrataEstimator se)

Make a copy of a strata estimator.

Parameters
sethe strata estimator to copy
Returns
the copy

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

428 {
429  struct MultiStrataEstimator *c;
430  unsigned int i;
431 
432  c = GNUNET_new (struct MultiStrataEstimator);
434  for (uint8_t strata_ctr = 0; strata_ctr < MULTI_SE_BASE_COUNT; strata_ctr++)
435  {
436  c->stratas[strata_ctr] = GNUNET_new (struct StrataEstimator);
437  c->stratas[strata_ctr]->strata_count =
438  se->stratas[strata_ctr]->strata_count;
439  c->stratas[strata_ctr]->ibf_size = se->stratas[strata_ctr]->ibf_size;
440  c->stratas[strata_ctr]->strata = GNUNET_new_array (
441  se->stratas[strata_ctr]->strata_count,
442  struct
444  for (i = 0; i < se->stratas[strata_ctr]->strata_count; i++)
445  c->stratas[strata_ctr]->strata[i] = ibf_dup (
446  se->stratas[strata_ctr]->strata[i]);
447  }
448  return c;
449 }

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: