GNUnet  0.10.x
gnunet-service-set_union_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 */
26 #include "platform.h"
27 #include "gnunet_util_lib.h"
28 #include "ibf.h"
30 
31 
36 #define FAIL_10_1_COMPATIBILTIY 1
37 
38 
46 size_t
48  void *buf)
49 {
50  char *sbuf = buf;
51  unsigned int i;
52  size_t osize;
53 
54  GNUNET_assert (NULL != se);
55  for (i = 0; i < se->strata_count; i++)
56  {
57  ibf_write_slice (se->strata[i],
58  0,
59  se->ibf_size,
60  &sbuf[se->ibf_size * IBF_BUCKET_SIZE * i]);
61  }
62  osize = se->ibf_size * IBF_BUCKET_SIZE * se->strata_count;
63 #if FAIL_10_1_COMPATIBILTIY
64  {
65  char *cbuf;
66  size_t nsize;
67 
68  if (GNUNET_YES ==
70  osize,
71  &cbuf,
72  &nsize))
73  {
74  GNUNET_memcpy (buf, cbuf, nsize);
75  osize = nsize;
76  GNUNET_free (cbuf);
77  }
78  }
79 #endif
80  return osize;
81 }
82 
83 
94 int
96  size_t buf_len,
97  int is_compressed,
98  struct StrataEstimator *se)
99 {
100  unsigned int i;
101  size_t osize;
102  char *dbuf;
103 
104  dbuf = NULL;
105  if (GNUNET_YES == is_compressed)
106  {
107  osize = se->ibf_size * IBF_BUCKET_SIZE * se->strata_count;
108  dbuf = GNUNET_decompress (buf,
109  buf_len,
110  osize);
111  if (NULL == dbuf)
112  {
113  GNUNET_break_op (0); /* bad compressed input data */
114  return GNUNET_SYSERR;
115  }
116  buf = dbuf;
117  buf_len = osize;
118  }
119 
120  if (buf_len != se->strata_count * se->ibf_size * IBF_BUCKET_SIZE)
121  {
122  GNUNET_break (0); /* very odd error */
123  GNUNET_free_non_null (dbuf);
124  return GNUNET_SYSERR;
125  }
126 
127  for (i = 0; i < se->strata_count; i++)
128  {
129  ibf_read_slice (buf, 0, se->ibf_size, se->strata[i]);
130  buf += se->ibf_size * IBF_BUCKET_SIZE;
131  }
132  GNUNET_free_non_null (dbuf);
133  return GNUNET_OK;
134 }
135 
136 
143 void
145  struct IBF_Key key)
146 {
147  uint64_t v;
148  unsigned int i;
149 
150  v = key.key_val;
151  /* count trailing '1'-bits of v */
152  for (i = 0; v & 1; v>>=1, i++)
153  /* empty */;
154  ibf_insert (se->strata[i], key);
155 }
156 
157 
164 void
166  struct IBF_Key key)
167 {
168  uint64_t v;
169  unsigned int i;
170 
171  v = key.key_val;
172  /* count trailing '1'-bits of v */
173  for (i = 0; v & 1; v>>=1, i++)
174  /* empty */;
175  ibf_remove (se->strata[i], key);
176 }
177 
178 
187 struct StrataEstimator *
189  uint32_t ibf_size,
190  uint8_t ibf_hashnum)
191 {
192  struct StrataEstimator *se;
193  unsigned int i;
194  unsigned int j;
195 
196  se = GNUNET_new (struct StrataEstimator);
198  se->ibf_size = ibf_size;
199  se->strata = GNUNET_new_array (strata_count,
200  struct InvertibleBloomFilter *);
201  for (i = 0; i < strata_count; i++)
202  {
203  se->strata[i] = ibf_create (ibf_size, ibf_hashnum);
204  if (NULL == se->strata[i])
205  {
207  "Failed to allocate memory for strata estimator\n");
208  for (j = 0; j < i; j++)
209  ibf_destroy (se->strata[i]);
210  GNUNET_free (se);
211  return NULL;
212  }
213  }
214  return se;
215 }
216 
217 
227 unsigned int
229  const struct StrataEstimator *se2)
230 {
231  unsigned int count;
232 
233  GNUNET_assert (se1->strata_count == se2->strata_count);
234  count = 0;
235  for (int i = se1->strata_count - 1; i >= 0; i--)
236  {
237  struct InvertibleBloomFilter *diff;
238  /* number of keys decoded from the ibf */
239 
240  /* FIXME: implement this without always allocating new IBFs */
241  diff = ibf_dup (se1->strata[i]);
242  ibf_subtract (diff, se2->strata[i]);
243  for (int ibf_count = 0; GNUNET_YES; ibf_count++)
244  {
245  int more;
246 
247  more = ibf_decode (diff, NULL, NULL);
248  if (GNUNET_NO == more)
249  {
250  count += ibf_count;
251  break;
252  }
253  /* Estimate if decoding fails or would not terminate */
254  if ((GNUNET_SYSERR == more) || (ibf_count > diff->size))
255  {
256  ibf_destroy (diff);
257  return count * (1 << (i + 1));
258  }
259  }
260  ibf_destroy (diff);
261  }
262  return count;
263 }
264 
265 
272 struct StrataEstimator *
274 {
275  struct StrataEstimator *c;
276  unsigned int i;
277 
278  c = GNUNET_new (struct StrataEstimator);
279  c->strata_count = se->strata_count;
280  c->ibf_size = se->ibf_size;
282  struct InvertibleBloomFilter *);
283  for (i = 0; i < se->strata_count; i++)
284  c->strata[i] = ibf_dup (se->strata[i]);
285  return c;
286 }
287 
288 
294 void
296 {
297  unsigned int i;
298 
299  for (i = 0; i < se->strata_count; i++)
300  ibf_destroy (se->strata[i]);
301  GNUNET_free (se->strata);
302  GNUNET_free (se);
303 }
void ibf_remove(struct InvertibleBloomFilter *ibf, struct IBF_Key key)
Remove a key from an IBF.
Definition: ibf.c:180
struct StrataEstimator * strata_estimator_create(unsigned int strata_count, uint32_t ibf_size, uint8_t ibf_hashnum)
Create a new strata estimator with the given parameters.
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
Invertible bloom filter (IBF).
Definition: ibf.h:82
#define GNUNET_NO
Definition: gnunet_common.h:81
#define GNUNET_OK
Named constants for return values.
Definition: gnunet_common.h:78
void strata_estimator_remove(struct StrataEstimator *se, struct IBF_Key key)
Remove a key from the strata estimator.
#define GNUNET_free_non_null(ptr)
Free the memory pointed to by ptr if ptr is not NULL.
#define GNUNET_new(type)
Allocate a struct or union of the given type.
uint64_t key_val
Definition: ibf.h:47
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:284
#define GNUNET_break(cond)
Use this for internal assertion violations that are not fatal (can be handled) but should not occur...
A handle to a strata estimator.
struct StrataEstimator * strata_estimator_dup(struct StrataEstimator *se)
Make a copy of a strata estimator.
struct InvertibleBloomFilter * ibf_dup(const struct InvertibleBloomFilter *ibf)
Create a copy of an IBF, the copy has to be destroyed properly.
Definition: ibf.c:368
uint32_t size
How many cells does this IBF have?
Definition: ibf.h:87
static unsigned int ibf_size
#define GNUNET_memcpy(dst, src, n)
#define GNUNET_break_op(cond)
Use this for assertion violations caused by other peers (i.e.
void strata_estimator_destroy(struct StrataEstimator *se)
Destroy a strata estimator, free all of its resources.
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:222
#define IBF_BUCKET_SIZE
Size of one ibf bucket in bytes.
Definition: ibf.h:72
static char buf[2048]
#define GNUNET_new_array(n, type)
Allocate a size n array with structs or unions of the given type.
void ibf_subtract(struct InvertibleBloomFilter *ibf1, const struct InvertibleBloomFilter *ibf2)
Subtract ibf2 from ibf1, storing the result in ibf1.
Definition: ibf.c:346
unsigned int strata_count
Size of the IBF array in strata.
void strata_estimator_insert(struct StrataEstimator *se, struct IBF_Key key)
Add a key to the strata estimator.
size_t strata_estimator_write(const struct StrataEstimator *se, void *buf)
Write the given strata estimator to the buffer.
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:315
struct GNUNET_HashCode key
The key used in the DHT.
int strata_estimator_read(const void *buf, size_t buf_len, int is_compressed, struct StrataEstimator *se)
Read strata from the buffer into the given strata estimator.
#define GNUNET_SYSERR
Definition: gnunet_common.h:79
invertible bloom filter
void ibf_destroy(struct InvertibleBloomFilter *ibf)
Destroy all resources associated with the invertible bloom filter.
Definition: ibf.c:388
struct InvertibleBloomFilter * ibf_create(uint32_t size, uint8_t hash_num)
Create an invertible bloom filter.
Definition: ibf.c:76
unsigned int strata_estimator_difference(const struct StrataEstimator *se1, const struct StrataEstimator *se2)
Estimate set difference with two strata estimators, i.e.
void ibf_insert(struct InvertibleBloomFilter *ibf, struct IBF_Key key)
Insert a key into an IBF.
Definition: ibf.c:164
#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.
#define GNUNET_YES
Definition: gnunet_common.h:80
struct InvertibleBloomFilter ** strata
The IBFs of this strata estimator.
Keys that can be inserted into and removed from an IBF.
Definition: ibf.h:45
struct IBF_Count * count
How many times has a bucket been hit? Can be negative, as a result of IBF subtraction.
Definition: ibf.h:112
char * GNUNET_decompress(const char *input, size_t input_size, size_t output_size)
Decompress input, return the decompressed data as output.
#define GNUNET_free(ptr)
Wrapper around free.
unsigned int ibf_size
Size of each IBF stratum (in bytes)