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  */
26 #include "platform.h"
27 #include "gnunet_util_lib.h"
28 #include "ibf.h"
30 
31 
39 size_t
41  void *buf)
42 {
43  char *sbuf = buf;
44  size_t osize;
45 
46  GNUNET_assert (NULL != se);
47  for (unsigned int i = 0; i < se->strata_count; i++)
48  {
49  ibf_write_slice (se->strata[i],
50  0,
51  se->ibf_size,
52  &sbuf[se->ibf_size * IBF_BUCKET_SIZE * i]);
53  }
54  osize = se->ibf_size * IBF_BUCKET_SIZE * se->strata_count;
55  {
56  char *cbuf;
57  size_t nsize;
58 
59  if (GNUNET_YES ==
61  osize,
62  &cbuf,
63  &nsize))
64  {
65  GNUNET_memcpy (buf,
66  cbuf,
67  nsize);
68  osize = nsize;
69  GNUNET_free (cbuf);
70  }
71  }
72  return osize;
73 }
74 
75 
86 int
88  size_t buf_len,
89  int is_compressed,
90  struct StrataEstimator *se)
91 {
92  size_t osize;
93  char *dbuf;
94 
95  dbuf = NULL;
96  if (GNUNET_YES == is_compressed)
97  {
98  osize = se->ibf_size * IBF_BUCKET_SIZE * se->strata_count;
99  dbuf = GNUNET_decompress (buf,
100  buf_len,
101  osize);
102  if (NULL == dbuf)
103  {
104  GNUNET_break_op (0); /* bad compressed input data */
105  return GNUNET_SYSERR;
106  }
107  buf = dbuf;
108  buf_len = osize;
109  }
110 
111  if (buf_len != se->strata_count * se->ibf_size * IBF_BUCKET_SIZE)
112  {
113  GNUNET_break (0); /* very odd error */
114  GNUNET_free (dbuf);
115  return GNUNET_SYSERR;
116  }
117 
118  for (unsigned int i = 0; i < se->strata_count; i++)
119  {
120  ibf_read_slice (buf, 0, se->ibf_size, se->strata[i]);
121  buf += se->ibf_size * IBF_BUCKET_SIZE;
122  }
123  GNUNET_free (dbuf);
124  return GNUNET_OK;
125 }
126 
127 
134 void
136  struct IBF_Key key)
137 {
138  uint64_t v;
139  unsigned int i;
140 
141  v = key.key_val;
142  /* count trailing '1'-bits of v */
143  for (i = 0; v & 1; v >>= 1, i++)
144  /* empty */;
145  ibf_insert (se->strata[i], key);
146 }
147 
148 
155 void
157  struct IBF_Key key)
158 {
159  uint64_t v;
160  unsigned int i;
161 
162  v = key.key_val;
163  /* count trailing '1'-bits of v */
164  for (i = 0; v & 1; v >>= 1, i++)
165  /* empty */;
166  ibf_remove (se->strata[i], key);
167 }
168 
169 
178 struct StrataEstimator *
180  uint32_t ibf_size,
181  uint8_t ibf_hashnum)
182 {
183  struct StrataEstimator *se;
184 
185  se = GNUNET_new (struct StrataEstimator);
187  se->ibf_size = ibf_size;
188  se->strata = GNUNET_new_array (strata_count,
189  struct InvertibleBloomFilter *);
190  for (unsigned int i = 0; i < strata_count; i++)
191  {
192  se->strata[i] = ibf_create (ibf_size, ibf_hashnum);
193  if (NULL == se->strata[i])
194  {
196  "Failed to allocate memory for strata estimator\n");
197  for (unsigned int j = 0; j < i; j++)
198  ibf_destroy (se->strata[i]);
199  GNUNET_free (se);
200  return NULL;
201  }
202  }
203  return se;
204 }
205 
206 
216 unsigned int
218  const struct StrataEstimator *se2)
219 {
220  unsigned int count;
221 
222  GNUNET_assert (se1->strata_count == se2->strata_count);
223  count = 0;
224  for (int i = se1->strata_count - 1; i >= 0; i--)
225  {
226  struct InvertibleBloomFilter *diff;
227  /* number of keys decoded from the ibf */
228 
229  /* FIXME: implement this without always allocating new IBFs */
230  diff = ibf_dup (se1->strata[i]);
231  ibf_subtract (diff,
232  se2->strata[i]);
233  for (int ibf_count = 0; GNUNET_YES; ibf_count++)
234  {
235  int more;
236 
237  more = ibf_decode (diff,
238  NULL,
239  NULL);
240  if (GNUNET_NO == more)
241  {
242  count += ibf_count;
243  break;
244  }
245  /* Estimate if decoding fails or would not terminate */
246  if ( (GNUNET_SYSERR == more) ||
247  (ibf_count > diff->size) )
248  {
249  ibf_destroy (diff);
250  return count * (1 << (i + 1));
251  }
252  }
253  ibf_destroy (diff);
254  }
255  return count;
256 }
257 
258 
265 struct StrataEstimator *
267 {
268  struct StrataEstimator *c;
269 
270  c = GNUNET_new (struct StrataEstimator);
271  c->strata_count = se->strata_count;
272  c->ibf_size = se->ibf_size;
274  struct InvertibleBloomFilter *);
275  for (unsigned int i = 0; i < se->strata_count; i++)
276  c->strata[i] = ibf_dup (se->strata[i]);
277  return c;
278 }
279 
280 
286 void
288 {
289  for (unsigned int i = 0; i < se->strata_count; i++)
290  ibf_destroy (se->strata[i]);
291  GNUNET_free (se->strata);
292  GNUNET_free (se);
293 }
void ibf_remove(struct InvertibleBloomFilter *ibf, struct IBF_Key key)
Remove a key from an IBF.
Definition: ibf.c:184
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.
void strata_estimator_destroy(struct StrataEstimator *se)
Destroy a strata estimator, free all of its resources.
struct StrataEstimator * strata_estimator_dup(struct StrataEstimator *se)
Make a copy of a strata estimator.
Invertible bloom filter (IBF).
Definition: ibf.h:82
size_t strata_estimator_write(const struct StrataEstimator *se, void *buf)
Write the given strata estimator to the buffer.
#define GNUNET_memcpy(dst, src, n)
Call memcpy() but check for n being 0 first.
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
#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:290
void strata_estimator_insert(struct StrataEstimator *se, struct IBF_Key key)
Add a key to the strata estimator.
#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 InvertibleBloomFilter * ibf_dup(const struct InvertibleBloomFilter *ibf)
Create a copy of an IBF, the copy has to be destroyed properly.
Definition: ibf.c:379
uint32_t size
How many cells does this IBF have?
Definition: ibf.h:87
static unsigned int ibf_size
#define GNUNET_break_op(cond)
Use this for assertion violations caused by other peers (i.e.
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
#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.
unsigned int strata_estimator_difference(const struct StrataEstimator *se1, const struct StrataEstimator *se2)
Estimate set difference with two strata estimators, i.e.
void ibf_subtract(struct InvertibleBloomFilter *ibf1, const struct InvertibleBloomFilter *ibf2)
Subtract ibf2 from ibf1, storing the result in ibf1.
Definition: ibf.c:356
unsigned int strata_count
Size of the IBF array in strata.
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
struct GNUNET_HashCode key
The key used in the DHT.
void ibf_destroy(struct InvertibleBloomFilter *ibf)
Destroy all resources associated with the invertible bloom filter.
Definition: ibf.c:403
struct InvertibleBloomFilter * ibf_create(uint32_t size, uint8_t hash_num)
Create an invertible bloom filter.
Definition: ibf.c:79
struct InvertibleBloomFilter ** strata
The IBFs of this strata estimator.
void ibf_insert(struct InvertibleBloomFilter *ibf, struct IBF_Key key)
Insert a key into an IBF.
Definition: ibf.c:167
#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.
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.
Keys that can be inserted into and removed from an IBF.
Definition: ibf.h:45
void strata_estimator_remove(struct StrataEstimator *se, struct IBF_Key key)
Remove a key from the strata estimator.
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)