GNUnet  0.11.x
gnunet-service-setu_strata_estimator.c
Go to the documentation of this file.
1 /*
2  This file is part of GNUnet
3  Copyright (C) 2012 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  SPDX-License-Identifier: AGPL3.0-or-later
19  */
27 #include "platform.h"
28 #include "gnunet_util_lib.h"
29 #include "ibf.h"
31 
32 
37 #define FAIL_10_1_COMPATIBILTIY 1
38 
43 #define MULTI_SE_BASE_COUNT 8
44 
50 #define AVG_BYTE_SIZE_SE 4221
51 
58 uint8_t
59 determine_strata_count (uint64_t avg_element_size, uint64_t element_count)
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 }
73 
74 
79 static void
80 salt_key (const struct IBF_Key *k_in,
81  uint32_t salt,
82  struct IBF_Key *k_out)
83 {
84  int s = (salt * 7) % 64;
85  uint64_t x = k_in->key_val;
86 
87  /* rotate ibf key */
88  x = (x >> s) | (x << (64 - s));
89  k_out->key_val = x;
90 }
91 
92 
96 static void
97 unsalt_key (const struct IBF_Key *k_in,
98  uint32_t salt,
99  struct IBF_Key *k_out)
100 {
101  int s = (salt * 7) % 64;
102  uint64_t x = k_in->key_val;
103 
104  x = (x << s) | (x >> (64 - s));
105  k_out->key_val = x;
106 }
107 
108 
116 size_t
118  uint16_t se_ibf_total_size,
119  uint8_t number_se_send,
120  void *buf)
121 {
122  char *sbuf = buf;
123  unsigned int i;
124  size_t osize;
125  uint64_t sbuf_offset = 0;
126  se->size = number_se_send;
127 
128  GNUNET_assert (NULL != se);
129  for (uint8_t strata_ctr = 0; strata_ctr < number_se_send; strata_ctr++)
130  {
131  for (i = 0; i < se->stratas[strata_ctr]->strata_count; i++)
132  {
133  ibf_write_slice (se->stratas[strata_ctr]->strata[i],
134  0,
135  se->stratas[strata_ctr]->ibf_size,
136  &sbuf[sbuf_offset],
137  8);
138  sbuf_offset += se->stratas[strata_ctr]->ibf_size * IBF_BUCKET_SIZE;
139  }
140  }
141  osize = ((se_ibf_total_size / 8) * number_se_send) * IBF_BUCKET_SIZE
142  * se->stratas[0]->strata_count;
143 #if FAIL_10_1_COMPATIBILTIY
144  {
145  char *cbuf;
146  size_t nsize;
147 
148  if (GNUNET_YES ==
150  osize,
151  &cbuf,
152  &nsize))
153  {
154  GNUNET_memcpy (buf, cbuf, nsize);
155  osize = nsize;
156  GNUNET_free (cbuf);
157  }
158  }
159 #endif
160  return osize;
161 }
162 
163 
174 int
176  size_t buf_len,
177  int is_compressed,
178  uint8_t number_se_received,
179  uint16_t se_ibf_total_size,
180  struct MultiStrataEstimator *se)
181 {
182  unsigned int i;
183  size_t osize;
184  char *dbuf;
185 
186  dbuf = NULL;
187  if (GNUNET_YES == is_compressed)
188  {
189  osize = ((se_ibf_total_size / 8) * number_se_received) * IBF_BUCKET_SIZE
190  * se->stratas[0]->strata_count;
191  dbuf = GNUNET_decompress (buf,
192  buf_len,
193  osize);
194  if (NULL == dbuf)
195  {
196  GNUNET_break_op (0); /* bad compressed input data */
197  return GNUNET_SYSERR;
198  }
199  buf = dbuf;
200  buf_len = osize;
201  }
202 
203  if (buf_len != se->stratas[0]->strata_count * ((se_ibf_total_size / 8)
204  * number_se_received)
205  * IBF_BUCKET_SIZE)
206  {
207  GNUNET_break (0); /* very odd error */
208  GNUNET_free (dbuf);
209  return GNUNET_SYSERR;
210  }
211 
212  for (uint8_t strata_ctr = 0; strata_ctr < number_se_received; strata_ctr++)
213  {
214  for (i = 0; i < se->stratas[strata_ctr]->strata_count; i++)
215  {
216  ibf_read_slice (buf, 0, se->stratas[strata_ctr]->ibf_size,
217  se->stratas[strata_ctr]->strata[i], 8);
218  buf += se->stratas[strata_ctr]->ibf_size * IBF_BUCKET_SIZE;
219  }
220  }
221  se->size = number_se_received;
222  GNUNET_free (dbuf);
223  return GNUNET_OK;
224 }
225 
226 
233 void
235  struct IBF_Key key)
236 {
237 
238 
239  /* count trailing '1'-bits of v */
240  for (int strata_ctr = 0; strata_ctr < MULTI_SE_BASE_COUNT; strata_ctr++)
241  {
242  unsigned int i;
243  uint64_t v;
244 
245  struct IBF_Key salted_key;
246  salt_key (&key,
247  strata_ctr * (64 / MULTI_SE_BASE_COUNT),
248  &salted_key);
249  v = salted_key.key_val;
250  for (i = 0; v & 1; v >>= 1, i++)
251  {
252  ibf_insert (se->stratas[strata_ctr]->strata[i], salted_key);
253  }
254  }
255  /* empty */;
256 
257 }
258 
259 
266 void
268  struct IBF_Key key)
269 {
270 
271  /* count trailing '1'-bits of v */
272  for (int strata_ctr = 0; strata_ctr < se->size; strata_ctr++)
273  {
274  uint64_t v;
275  unsigned int i;
276 
277  struct IBF_Key unsalted_key;
278  unsalt_key (&key,
279  strata_ctr * (64 / MULTI_SE_BASE_COUNT),
280  &unsalted_key);
281 
282  v = unsalted_key.key_val;
283  for (i = 0; v & 1; v >>= 1, i++)
284  {
285  /* empty */;
286  ibf_remove (se->stratas[strata_ctr]->strata[i], unsalted_key);
287  }
288  }
289 }
290 
291 
300 struct MultiStrataEstimator *
301 strata_estimator_create (unsigned int strata_count,
302  uint32_t ibf_size,
303  uint8_t ibf_hashnum)
304 {
305  struct MultiStrataEstimator *se;
306  unsigned int i;
307  unsigned int j;
308  se = GNUNET_new (struct MultiStrataEstimator);
309 
312 
313  uint8_t ibf_prime_sizes[] = {79,79,79,79,79,79,79,79};
314 
315  for (uint8_t strata_ctr = 0; strata_ctr < MULTI_SE_BASE_COUNT; strata_ctr++)
316  {
317  se->stratas[strata_ctr] = GNUNET_new (struct StrataEstimator);
318  se->stratas[strata_ctr]->strata_count = strata_count;
319  se->stratas[strata_ctr]->ibf_size = ibf_prime_sizes[strata_ctr];
320  se->stratas[strata_ctr]->strata = GNUNET_new_array (strata_count * 4,
321  struct
323  for (i = 0; i < strata_count; i++)
324  {
325  se->stratas[strata_ctr]->strata[i] = ibf_create (
326  ibf_prime_sizes[strata_ctr], ibf_hashnum);
327  if (NULL == se->stratas[strata_ctr]->strata[i])
328  {
330  "Failed to allocate memory for strata estimator\n");
331  for (j = 0; j < i; j++)
332  ibf_destroy (se->stratas[strata_ctr]->strata[i]);
333  GNUNET_free (se);
334  return NULL;
335  }
336  }
337  }
338  return se;
339 }
340 
341 
351 void
353  const struct MultiStrataEstimator *se2)
354 {
355  int avg_local_diff = 0;
356  int avg_remote_diff = 0;
357  uint8_t number_of_estimators = se1->size;
358 
359  for (uint8_t strata_ctr = 0; strata_ctr < number_of_estimators; strata_ctr++)
360  {
361  GNUNET_assert (se1->stratas[strata_ctr]->strata_count ==
362  se2->stratas[strata_ctr]->strata_count);
363 
364 
365  for (int i = se1->stratas[strata_ctr]->strata_count - 1; i >= 0; i--)
366  {
367  struct InvertibleBloomFilter *diff;
368  /* number of keys decoded from the ibf */
369 
370  /* FIXME: implement this without always allocating new IBFs */
371  diff = ibf_dup (se1->stratas[strata_ctr]->strata[i]);
372  diff->local_decoded_count = 0;
373  diff->remote_decoded_count = 0;
374 
375  ibf_subtract (diff, se2->stratas[strata_ctr]->strata[i]);
376 
377  for (int ibf_count = 0; GNUNET_YES; ibf_count++)
378  {
379  int more;
380 
381  more = ibf_decode (diff, NULL, NULL);
382  if (GNUNET_NO == more)
383  {
384  se1->stratas[strata_ctr]->strata[0]->local_decoded_count +=
385  diff->local_decoded_count;
386  se1->stratas[strata_ctr]->strata[0]->remote_decoded_count +=
387  diff->remote_decoded_count;
388  break;
389  }
390  /* Estimate if decoding fails or would not terminate */
391  if ((GNUNET_SYSERR == more) || (ibf_count > diff->size))
392  {
393  se1->stratas[strata_ctr]->strata[0]->local_decoded_count =
394  se1->stratas[strata_ctr]->strata[0]->local_decoded_count * (1 << (i
395  +
396  1));
397  se1->stratas[strata_ctr]->strata[0]->remote_decoded_count =
398  se1->stratas[strata_ctr]->strata[0]->remote_decoded_count * (1 << (i
399  +
400  1));
401  ibf_destroy (diff);
402  goto break_all_counting_loops;
403  }
404  }
405  ibf_destroy (diff);
406  }
407 break_all_counting_loops:;
408  avg_local_diff += se1->stratas[strata_ctr]->strata[0]->local_decoded_count;
409  avg_remote_diff +=
410  se1->stratas[strata_ctr]->strata[0]->remote_decoded_count;
411  }
412  se1->stratas[0]->strata[0]->local_decoded_count = avg_local_diff
413  / number_of_estimators;
414  se1->stratas[0]->strata[0]->remote_decoded_count = avg_remote_diff
415  / number_of_estimators;
416 }
417 
418 
425 struct MultiStrataEstimator *
427 {
428  struct MultiStrataEstimator *c;
429  unsigned int i;
430 
431  c = GNUNET_new (struct MultiStrataEstimator);
433  for (uint8_t strata_ctr = 0; strata_ctr < MULTI_SE_BASE_COUNT; strata_ctr++)
434  {
435  c->stratas[strata_ctr] = GNUNET_new (struct StrataEstimator);
436  c->stratas[strata_ctr]->strata_count =
437  se->stratas[strata_ctr]->strata_count;
438  c->stratas[strata_ctr]->ibf_size = se->stratas[strata_ctr]->ibf_size;
439  c->stratas[strata_ctr]->strata = GNUNET_new_array (
440  se->stratas[strata_ctr]->strata_count,
441  struct
443  for (i = 0; i < se->stratas[strata_ctr]->strata_count; i++)
444  c->stratas[strata_ctr]->strata[i] = ibf_dup (
445  se->stratas[strata_ctr]->strata[i]);
446  }
447  return c;
448 }
449 
450 
456 void
458 {
459  unsigned int i;
460  for (uint8_t strata_ctr = 0; strata_ctr < MULTI_SE_BASE_COUNT; strata_ctr++)
461  {
462  for (i = 0; i < se->stratas[strata_ctr]->strata_count; i++)
463  ibf_destroy (se->stratas[strata_ctr]->strata[i]);
464  GNUNET_free (se->stratas[strata_ctr]->strata);
465  }
466  GNUNET_free (se);
467 }
struct GNUNET_HashCode key
The key used in the DHT.
static struct GNUNET_CRYPTO_PowSalt salt
Salt for PoW calcualations.
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.
struct MultiStrataEstimator * strata_estimator_dup(struct MultiStrataEstimator *se)
Make a copy of a strata estimator.
#define AVG_BYTE_SIZE_SE
The avg size of 1 se Based on the bsc thesis of Elias Summermatter (2021)
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.
void strata_estimator_destroy(struct MultiStrataEstimator *se)
Destroy a strata estimator, free all of its resources.
uint8_t determine_strata_count(uint64_t avg_element_size, uint64_t element_count)
Calculates the optimal number of strata Estimators to send.
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.
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.
void strata_estimator_insert(struct MultiStrataEstimator *se, struct IBF_Key key)
Add a key to the strata estimator.
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.
void strata_estimator_difference(const struct MultiStrataEstimator *se1, const struct MultiStrataEstimator *se2)
Estimate set difference with two strata estimators, i.e.
#define MULTI_SE_BASE_COUNT
Number of strata estimators in memory NOT transmitted.
void strata_estimator_remove(struct MultiStrataEstimator *se, struct IBF_Key key)
Remove a key from the strata estimator.
static char buf[2048]
static unsigned int ibf_size
#define GNUNET_log(kind,...)
#define GNUNET_memcpy(dst, src, n)
Call memcpy() but check for n being 0 first.
@ GNUNET_OK
Definition: gnunet_common.h:95
@ GNUNET_YES
Definition: gnunet_common.h:97
@ GNUNET_NO
Definition: gnunet_common.h:94
@ GNUNET_SYSERR
Definition: gnunet_common.h:93
char * GNUNET_decompress(const char *input, size_t input_size, size_t output_size)
Decompress input, return the decompressed data as output.
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.
#define GNUNET_break_op(cond)
Use this for assertion violations caused by other peers (i.e.
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
#define GNUNET_break(cond)
Use this for internal assertion violations that are not fatal (can be handled) but should not occur.
@ 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.
#define GNUNET_free(ptr)
Wrapper around free.
void ibf_subtract(struct InvertibleBloomFilter *ibf1, const struct InvertibleBloomFilter *ibf2)
Subtract ibf2 from ibf1, storing the result in ibf1.
Definition: ibf.c:356
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:228
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:323
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:290
struct InvertibleBloomFilter * ibf_create(uint32_t size, uint8_t hash_num)
Create an invertible bloom filter.
Definition: ibf.c:79
void ibf_insert(struct InvertibleBloomFilter *ibf, struct IBF_Key key)
Insert a key into an IBF.
Definition: ibf.c:167
struct InvertibleBloomFilter * ibf_dup(const struct InvertibleBloomFilter *ibf)
Create a copy of an IBF, the copy has to be destroyed properly.
Definition: ibf.c:379
void ibf_remove(struct InvertibleBloomFilter *ibf, struct IBF_Key key)
Remove a key from an IBF.
Definition: ibf.c:184
void ibf_destroy(struct InvertibleBloomFilter *ibf)
Destroy all resources associated with the invertible bloom filter.
Definition: ibf.c:403
#define IBF_BUCKET_SIZE
Size of one ibf bucket in bytes.
Definition: ibf.h:72
Keys that can be inserted into and removed from an IBF.
Definition: ibf.h:46
uint64_t key_val
Definition: ibf.h:47
Invertible bloom filter (IBF).
Definition: ibf.h:83
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
uint8_t size
Number of strata estimators in struct.
struct StrataEstimator ** stratas
Array of strata estimators.
A handle to a strata estimator.
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.