GNUnet  0.10.x
Functions | Variables
gnunet-set-ibf-profiler.c File Reference

tool for profiling the invertible bloom filter implementation More...

#include "platform.h"
#include "gnunet_util_lib.h"
#include "ibf.h"
Include dependency graph for gnunet-set-ibf-profiler.c:

Go to the source code of this file.

Functions

static void register_hashcode (struct GNUNET_HashCode *hash)
 
static void iter_hashcodes (struct IBF_Key key, GNUNET_CONTAINER_MulitHashMapIteratorCallback iter, void *cls)
 
static int insert_iterator (void *cls, const struct GNUNET_HashCode *key, void *value)
 
static int remove_iterator (void *cls, const struct GNUNET_HashCode *key, void *value)
 
static void run (void *cls, char *const *args, const char *cfgfile, const struct GNUNET_CONFIGURATION_Handle *cfg)
 
int main (int argc, char **argv)
 

Variables

static unsigned int asize = 10
 
static unsigned int bsize = 10
 
static unsigned int csize = 10
 
static unsigned int hash_num = 4
 
static unsigned int ibf_size = 80
 
static enum GNUNET_CRYPTO_Quality random_quality = GNUNET_CRYPTO_QUALITY_WEAK
 
static struct GNUNET_CONTAINER_MultiHashMapset_a
 
static struct GNUNET_CONTAINER_MultiHashMapset_b
 
static struct GNUNET_CONTAINER_MultiHashMapset_c
 
static struct GNUNET_CONTAINER_MultiHashMapkey_to_hashcode
 
static struct InvertibleBloomFilteribf_a
 
static struct InvertibleBloomFilteribf_b
 

Detailed Description

tool for profiling the invertible bloom filter implementation

Author
Florian Dold

Definition in file gnunet-set-ibf-profiler.c.

Function Documentation

◆ register_hashcode()

static void register_hashcode ( struct GNUNET_HashCode hash)
static

Definition at line 53 of file gnunet-set-ibf-profiler.c.

References GNUNET_CONTAINER_multihashmap_put(), GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE, GNUNET_memdup, ibf_hashcode_from_key(), and ibf_key_from_hashcode().

Referenced by run().

54 {
55  struct GNUNET_HashCode replicated;
56  struct IBF_Key key;
57 
58  key = ibf_key_from_hashcode(hash);
59  ibf_hashcode_from_key(key, &replicated);
62  &replicated,
63  GNUNET_memdup(hash, sizeof *hash),
65 }
static struct GNUNET_CONTAINER_MultiHashMap * key_to_hashcode
#define GNUNET_memdup(buf, size)
Allocate and initialize a block of memory.
void ibf_hashcode_from_key(struct IBF_Key key, struct GNUNET_HashCode *dst)
Create a hashcode from a key, by replicating the key until the hascode is filled. ...
Definition: ibf.c:55
A 512-bit hashcode.
struct GNUNET_HashCode key
The key used in the DHT.
int GNUNET_CONTAINER_multihashmap_put(struct GNUNET_CONTAINER_MultiHashMap *map, const struct GNUNET_HashCode *key, void *value, enum GNUNET_CONTAINER_MultiHashMapOption opt)
Store a key-value pair in the map.
Allow multiple values with the same key.
struct IBF_Key ibf_key_from_hashcode(const struct GNUNET_HashCode *hash)
Create a key from a hashcode.
Definition: ibf.c:42
Keys that can be inserted into and removed from an IBF.
Definition: ibf.h:45
Here is the call graph for this function:
Here is the caller graph for this function:

◆ iter_hashcodes()

static void iter_hashcodes ( struct IBF_Key  key,
GNUNET_CONTAINER_MulitHashMapIteratorCallback  iter,
void *  cls 
)
static

Definition at line 69 of file gnunet-set-ibf-profiler.c.

References GNUNET_CONTAINER_multihashmap_get_multiple(), and ibf_hashcode_from_key().

Referenced by run().

72 {
73  struct GNUNET_HashCode replicated;
74 
75  ibf_hashcode_from_key(key, &replicated);
77  &replicated,
78  iter,
79  cls);
80 }
static struct GNUNET_CONTAINER_MultiHashMap * key_to_hashcode
void ibf_hashcode_from_key(struct IBF_Key key, struct GNUNET_HashCode *dst)
Create a hashcode from a key, by replicating the key until the hascode is filled. ...
Definition: ibf.c:55
A 512-bit hashcode.
int GNUNET_CONTAINER_multihashmap_get_multiple(struct GNUNET_CONTAINER_MultiHashMap *map, const struct GNUNET_HashCode *key, GNUNET_CONTAINER_MulitHashMapIteratorCallback it, void *it_cls)
Iterate over all entries in the map that match a particular key.
Here is the call graph for this function:
Here is the caller graph for this function:

◆ insert_iterator()

static int insert_iterator ( void *  cls,
const struct GNUNET_HashCode key,
void *  value 
)
static

Definition at line 84 of file gnunet-set-ibf-profiler.c.

References GNUNET_YES, ibf_insert(), and ibf_key_from_hashcode().

Referenced by run().

85 {
86  struct InvertibleBloomFilter *ibf = cls;
87 
89  return GNUNET_YES;
90 }
Invertible bloom filter (IBF).
Definition: ibf.h:79
void ibf_insert(struct InvertibleBloomFilter *ibf, struct IBF_Key key)
Insert a key into an IBF.
Definition: ibf.c:164
#define GNUNET_YES
Definition: gnunet_common.h:77
struct IBF_Key ibf_key_from_hashcode(const struct GNUNET_HashCode *hash)
Create a key from a hashcode.
Definition: ibf.c:42
Here is the call graph for this function:
Here is the caller graph for this function:

◆ remove_iterator()

static int remove_iterator ( void *  cls,
const struct GNUNET_HashCode key,
void *  value 
)
static

Definition at line 94 of file gnunet-set-ibf-profiler.c.

References GNUNET_CONTAINER_multihashmap_remove(), and GNUNET_YES.

Referenced by run().

95 {
96  struct GNUNET_CONTAINER_MultiHashMap *hashmap = cls;
97 
98  /* if remove fails, there just was a collision with another key */
99  (void)GNUNET_CONTAINER_multihashmap_remove(hashmap, value, NULL);
100  return GNUNET_YES;
101 }
Internal representation of the hash map.
static char * value
Value of the record to add/remove.
int GNUNET_CONTAINER_multihashmap_remove(struct GNUNET_CONTAINER_MultiHashMap *map, const struct GNUNET_HashCode *key, const void *value)
Remove the given key-value pair from the map.
#define GNUNET_YES
Definition: gnunet_common.h:77
Here is the call graph for this function:
Here is the caller graph for this function:

◆ run()

static void run ( void *  cls,
char *const *  args,
const char *  cfgfile,
const struct GNUNET_CONFIGURATION_Handle cfg 
)
static

Definition at line 105 of file gnunet-set-ibf-profiler.c.

References asize, bsize, csize, GNUNET_break, GNUNET_CONTAINER_multihashmap_contains(), GNUNET_CONTAINER_multihashmap_create(), GNUNET_CONTAINER_multihashmap_iterate(), GNUNET_CONTAINER_multihashmap_put(), GNUNET_CONTAINER_multihashmap_size(), GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY, GNUNET_CRYPTO_hash_create_random(), GNUNET_NO, GNUNET_OK, GNUNET_SCHEDULER_shutdown(), GNUNET_STRINGS_relative_time_to_string(), GNUNET_SYSERR, GNUNET_TIME_absolute_get(), GNUNET_TIME_absolute_get_duration(), GNUNET_YES, hash_num, ibf_create(), ibf_decode(), ibf_size, ibf_subtract(), insert_iterator(), iter_hashcodes(), random_quality, register_hashcode(), remove_iterator(), and res.

Referenced by main().

109 {
110  struct GNUNET_HashCode id;
111  struct IBF_Key ibf_key;
112  int i;
113  int side;
114  int res;
116  struct GNUNET_TIME_Relative delta_time;
117 
118  set_a =
120  GNUNET_NO);
121  set_b =
123  GNUNET_NO);
125  GNUNET_NO);
126 
129  ? 1
130  : (asize + bsize + csize)),
131  GNUNET_NO);
132 
133  printf("hash-num=%u, size=%u, #(A-B)=%u, #(B-A)=%u, #(A&B)=%u\n",
134  hash_num,
135  ibf_size,
136  asize,
137  bsize,
138  csize);
139 
140  i = 0;
141  while (i < asize)
142  {
145  continue;
148  set_a,
149  &id,
150  NULL,
152  register_hashcode(&id);
153  i++;
154  }
155  i = 0;
156  while (i < bsize)
157  {
160  continue;
162  continue;
165  set_b,
166  &id,
167  NULL,
169  register_hashcode(&id);
170  i++;
171  }
172  i = 0;
173  while (i < csize)
174  {
177  continue;
179  continue;
181  continue;
184  set_c,
185  &id,
186  NULL,
188  register_hashcode(&id);
189  i++;
190  }
191 
194  if ((NULL == ibf_a) || (NULL == ibf_b))
195  {
196  /* insufficient memory */
197  GNUNET_break(0);
199  return;
200  }
201 
202 
203  printf("generated sets\n");
204 
206 
211 
213 
214  printf("encoded in: %s\n",
216 
218 
219 
221 
222  for (i = 0; i <= asize + bsize; i++)
223  {
224  res = ibf_decode(ibf_a, &side, &ibf_key);
225  if (GNUNET_SYSERR == res)
226  {
227  printf("decode failed, %u/%u elements left\n",
230  asize + bsize);
231  return;
232  }
233  if (GNUNET_NO == res)
234  {
237  {
239  printf("decoded successfully in: %s\n",
241  }
242  else
243  {
244  printf("decode missed elements (should never happen)\n");
245  }
246  return;
247  }
248 
249  if (side == 1)
250  iter_hashcodes(ibf_key, remove_iterator, set_a);
251  if (side == -1)
253  }
254  printf("cyclic IBF, %u/%u elements left\n",
257  asize + bsize);
258 }
static struct GNUNET_CONTAINER_MultiHashMap * set_b
unsigned int GNUNET_CONTAINER_multihashmap_size(const struct GNUNET_CONTAINER_MultiHashMap *map)
Get the number of key-value pairs in the map.
static void iter_hashcodes(struct IBF_Key key, GNUNET_CONTAINER_MulitHashMapIteratorCallback iter, void *cls)
static enum GNUNET_CRYPTO_Quality random_quality
static struct GNUNET_CONTAINER_MultiHashMap * key_to_hashcode
#define GNUNET_NO
Definition: gnunet_common.h:78
static struct GNUNET_IDENTITY_Handle * id
Handle to identity service.
#define GNUNET_OK
Named constants for return values.
Definition: gnunet_common.h:75
int GNUNET_CONTAINER_multihashmap_contains(const struct GNUNET_CONTAINER_MultiHashMap *map, const struct GNUNET_HashCode *key)
Check if the map contains any value under the given key (including values that are NULL)...
void GNUNET_SCHEDULER_shutdown(void)
Request the shutdown of a scheduler.
Definition: scheduler.c:517
#define GNUNET_break(cond)
Use this for internal assertion violations that are not fatal (can be handled) but should not occur...
static unsigned int ibf_size
static struct InvertibleBloomFilter * ibf_a
static unsigned int csize
void GNUNET_CRYPTO_hash_create_random(enum GNUNET_CRYPTO_Quality mode, struct GNUNET_HashCode *result)
Create a random hash code.
Definition: crypto_hash.c:138
static int remove_iterator(void *cls, const struct GNUNET_HashCode *key, void *value)
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:225
const char * GNUNET_STRINGS_relative_time_to_string(struct GNUNET_TIME_Relative delta, int do_round)
Give relative time in human-readable fancy format.
Definition: strings.c:686
static int insert_iterator(void *cls, const struct GNUNET_HashCode *key, void *value)
static unsigned int asize
static struct GNUNET_CONTAINER_MultiHashMap * set_c
static void register_hashcode(struct GNUNET_HashCode *hash)
void ibf_subtract(struct InvertibleBloomFilter *ibf1, const struct InvertibleBloomFilter *ibf2)
Subtract ibf2 from ibf1, storing the result in ibf1.
Definition: ibf.c:349
static unsigned int bsize
A 512-bit hashcode.
static int res
struct GNUNET_TIME_Absolute GNUNET_TIME_absolute_get(void)
Get the current time.
Definition: time.c:118
static struct GNUNET_TIME_Absolute start_time
Start time of the current round; used to determine how long one iteration takes (which influences how...
There must only be one value per key; storing a value should fail if a value under the same key alrea...
#define GNUNET_SYSERR
Definition: gnunet_common.h:76
static unsigned int hash_num
struct InvertibleBloomFilter * ibf_create(uint32_t size, uint8_t hash_num)
Create an invertible bloom filter.
Definition: ibf.c:76
int GNUNET_CONTAINER_multihashmap_put(struct GNUNET_CONTAINER_MultiHashMap *map, const struct GNUNET_HashCode *key, void *value, enum GNUNET_CONTAINER_MultiHashMapOption opt)
Store a key-value pair in the map.
struct GNUNET_TIME_Relative GNUNET_TIME_absolute_get_duration(struct GNUNET_TIME_Absolute whence)
Get the duration of an operation as the difference of the current time and the given start time "henc...
Definition: time.c:373
struct GNUNET_CONTAINER_MultiHashMap * GNUNET_CONTAINER_multihashmap_create(unsigned int len, int do_not_copy_keys)
Create a multi hash map.
Time for absolute times used by GNUnet, in microseconds.
#define GNUNET_YES
Definition: gnunet_common.h:77
static struct GNUNET_CONTAINER_MultiHashMap * set_a
Keys that can be inserted into and removed from an IBF.
Definition: ibf.h:45
int GNUNET_CONTAINER_multihashmap_iterate(struct GNUNET_CONTAINER_MultiHashMap *map, GNUNET_CONTAINER_MulitHashMapIteratorCallback it, void *it_cls)
Iterate over all entries in the map.
static struct InvertibleBloomFilter * ibf_b
Time for relative time used by GNUnet, in microseconds.
Here is the call graph for this function:
Here is the caller graph for this function:

◆ main()

int main ( int  argc,
char **  argv 
)

Definition at line 262 of file gnunet-set-ibf-profiler.c.

References asize, bsize, csize, gettext_noop, GNUNET_GETOPT_OPTION_END, GNUNET_GETOPT_option_uint(), GNUNET_PROGRAM_run2(), GNUNET_YES, hash_num, ibf_size, and run().

263 {
266  "asize",
267  NULL,
268  gettext_noop("number of element in set A-B"),
269  &asize),
270 
272  "bsize",
273  NULL,
274  gettext_noop("number of element in set B-A"),
275  &bsize),
276 
278  "csize",
279  NULL,
280  gettext_noop(
281  "number of common elements in A and B"),
282  &csize),
283 
285  "hash-num",
286  NULL,
287  gettext_noop("hash num"),
288  &hash_num),
289 
291  "ibf-size",
292  NULL,
293  gettext_noop("ibf size"),
294  &ibf_size),
295 
297  };
298 
299  GNUNET_PROGRAM_run2(argc,
300  argv,
301  "gnunet-consensus-ibf",
302  "help",
303  options,
304  &run,
305  NULL,
306  GNUNET_YES);
307  return 0;
308 }
int GNUNET_PROGRAM_run2(int argc, char *const *argv, const char *binaryName, const char *binaryHelp, const struct GNUNET_GETOPT_CommandLineOption *options, GNUNET_PROGRAM_Main task, void *task_cls, int run_without_scheduler)
Run a standard GNUnet command startup sequence (initialize loggers and configuration, parse options).
Definition: program.c:140
struct GNUNET_GETOPT_CommandLineOption options[]
Definition: 002.c:5
Definition of a command line option.
static void run(void *cls, char *const *args, const char *cfgfile, const struct GNUNET_CONFIGURATION_Handle *cfg)
struct GNUNET_GETOPT_CommandLineOption GNUNET_GETOPT_OPTION_END
Definition: 002.c:13
static unsigned int ibf_size
static unsigned int csize
static unsigned int asize
static unsigned int bsize
static unsigned int hash_num
#define GNUNET_YES
Definition: gnunet_common.h:77
struct GNUNET_GETOPT_CommandLineOption GNUNET_GETOPT_option_uint(char shortName, const char *name, const char *argumentHelp, const char *description, unsigned int *val)
Allow user to specify an unsigned int.
#define gettext_noop(String)
Definition: gettext.h:69
Here is the call graph for this function:

Variable Documentation

◆ asize

unsigned int asize = 10
static

Definition at line 32 of file gnunet-set-ibf-profiler.c.

Referenced by main(), and run().

◆ bsize

unsigned int bsize = 10
static

◆ csize

unsigned int csize = 10
static

◆ hash_num

unsigned int hash_num = 4
static

Definition at line 35 of file gnunet-set-ibf-profiler.c.

Referenced by ibf_create(), main(), and run().

◆ ibf_size

unsigned int ibf_size = 80
static

Definition at line 36 of file gnunet-set-ibf-profiler.c.

Referenced by main(), run(), and strata_estimator_create().

◆ random_quality

enum GNUNET_CRYPTO_Quality random_quality = GNUNET_CRYPTO_QUALITY_WEAK
static

Definition at line 39 of file gnunet-set-ibf-profiler.c.

Referenced by run().

◆ set_a

struct GNUNET_CONTAINER_MultiHashMap* set_a
static

Definition at line 41 of file gnunet-set-ibf-profiler.c.

◆ set_b

struct GNUNET_CONTAINER_MultiHashMap* set_b
static

Definition at line 42 of file gnunet-set-ibf-profiler.c.

◆ set_c

struct GNUNET_CONTAINER_MultiHashMap* set_c
static

Definition at line 44 of file gnunet-set-ibf-profiler.c.

◆ key_to_hashcode

struct GNUNET_CONTAINER_MultiHashMap* key_to_hashcode
static

Definition at line 46 of file gnunet-set-ibf-profiler.c.

◆ ibf_a

struct InvertibleBloomFilter* ibf_a
static

Definition at line 48 of file gnunet-set-ibf-profiler.c.

◆ ibf_b

struct InvertibleBloomFilter* ibf_b
static

Definition at line 49 of file gnunet-set-ibf-profiler.c.