GNUnet  0.20.0
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  if (s > 0)
89  x = (x >> s) | (x << (64 - s));
90  k_out->key_val = x;
91 }
92 
93 
97 static void
98 unsalt_key (const struct IBF_Key *k_in,
99  uint32_t salt,
100  struct IBF_Key *k_out)
101 {
102  int s = (salt * 7) % 64;
103  uint64_t x = k_in->key_val;
104 
105  x = (x << s) | (x >> (64 - s));
106  k_out->key_val = x;
107 }
108 
109 
117 size_t
119  uint16_t se_ibf_total_size,
120  uint8_t number_se_send,
121  void *buf)
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 }
163 
164 
175 int
177  size_t buf_len,
178  int is_compressed,
179  uint8_t number_se_received,
180  uint16_t se_ibf_total_size,
181  struct MultiStrataEstimator *se)
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 }
226 
227 
234 void
236  struct IBF_Key key)
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 }
259 
260 
267 void
269  struct IBF_Key key)
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 }
291 
292 
301 struct MultiStrataEstimator *
302 strata_estimator_create (unsigned int strata_count,
303  uint32_t ibf_size,
304  uint8_t ibf_hashnum)
305 {
306  struct MultiStrataEstimator *se;
307  unsigned int i;
308  unsigned int j;
309  se = GNUNET_new (struct MultiStrataEstimator);
310 
313 
314  uint8_t ibf_prime_sizes[] = {79,79,79,79,79,79,79,79};
315 
316  for (uint8_t strata_ctr = 0; strata_ctr < MULTI_SE_BASE_COUNT; strata_ctr++)
317  {
318  se->stratas[strata_ctr] = GNUNET_new (struct StrataEstimator);
319  se->stratas[strata_ctr]->strata_count = strata_count;
320  se->stratas[strata_ctr]->ibf_size = ibf_prime_sizes[strata_ctr];
321  se->stratas[strata_ctr]->strata = GNUNET_new_array (strata_count * 4,
322  struct
324  for (i = 0; i < strata_count; i++)
325  {
326  se->stratas[strata_ctr]->strata[i] = ibf_create (
327  ibf_prime_sizes[strata_ctr], ibf_hashnum);
328  if (NULL == se->stratas[strata_ctr]->strata[i])
329  {
331  "Failed to allocate memory for strata estimator\n");
332  for (j = 0; j < i; j++)
333  ibf_destroy (se->stratas[strata_ctr]->strata[i]);
334  GNUNET_free (se);
335  return NULL;
336  }
337  }
338  }
339  return se;
340 }
341 
342 
352 void
354  const struct MultiStrataEstimator *se2)
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 }
418 
419 
426 struct MultiStrataEstimator *
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 }
450 
451 
457 void
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 }
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
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
#define GNUNET_log(kind,...)
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_OK
@ GNUNET_YES
@ GNUNET_NO
@ GNUNET_SYSERR
#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: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
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
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
struct InvertibleBloomFilter * ibf_create(uint32_t size, uint8_t hash_num)
Create an invertible bloom filter.
Definition: ibf.c:80
void ibf_insert(struct InvertibleBloomFilter *ibf, struct IBF_Key key)
Insert a key into an IBF.
Definition: ibf.c:168
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
void ibf_remove(struct InvertibleBloomFilter *ibf, struct IBF_Key key)
Remove a key from an IBF.
Definition: ibf.c:185
void ibf_destroy(struct InvertibleBloomFilter *ibf)
Destroy all resources associated with the invertible bloom filter.
Definition: ibf.c:404
#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.