src/set/gnunet-set-ibf-profiler.c

   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 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
  16 /**
  17  * @file set/gnunet-set-ibf-profiler.c
  18  * @brief tool for profiling the invertible bloom filter implementation
  19  * @author Florian Dold
  20  */
  21
  22 #include "platform.h"
  23 #include "gnunet_util_lib.h"
  24
  25 #include "ibf.h"
  26
  27 static unsigned int asize = 10;
  28 static unsigned int bsize = 10;
  29 static unsigned int csize = 10;
  30 static unsigned int hash_num = 4;
  31 static unsigned int ibf_size = 80;
  32
  33 /* FIXME: add parameter for this */
  34 static enum GNUNET_CRYPTO_Quality random_quality = GNUNET_CRYPTO_QUALITY_WEAK;
  35
  36 static struct GNUNET_CONTAINER_MultiHashMap *set_a;
  37 static struct GNUNET_CONTAINER_MultiHashMap *set_b;
  38 /* common elements in a and b */
  39 static struct GNUNET_CONTAINER_MultiHashMap *set_c;
  40
  41 static struct GNUNET_CONTAINER_MultiHashMap *key_to_hashcode;
  42
  43 static struct InvertibleBloomFilter *ibf_a;
  44 static struct InvertibleBloomFilter *ibf_b;
  45
  46
  47 static void
  48 register_hashcode (struct GNUNET_HashCode *hash)
  49 {
  50   struct GNUNET_HashCode replicated;
  51   struct IBF_Key key;
  52   key = ibf_key_from_hashcode (hash);
  53   ibf_hashcode_from_key (key, &replicated);
  54   (void) GNUNET_CONTAINER_multihashmap_put (key_to_hashcode,
  55                                             &replicated,
  56                                             GNUNET_memdup (hash, sizeof *hash),
  57                                             GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE);
  58 }
  59
  60
  61 static void
  62 iter_hashcodes (struct IBF_Key key,
  63                 GNUNET_CONTAINER_HashMapIterator iter,
  64                 void *cls)
  65 {
  66   struct GNUNET_HashCode replicated;
  67
  68   ibf_hashcode_from_key (key, &replicated);
  69   GNUNET_CONTAINER_multihashmap_get_multiple (key_to_hashcode,
  70                                               &replicated,
  71                                               iter, cls);
  72 }
  73
  74
  75 static int
  76 insert_iterator (void *cls,
  77                  const struct GNUNET_HashCode *key,
  78                  void *value)
  79 {
  80   struct InvertibleBloomFilter *ibf = cls;
  81
  82   ibf_insert (ibf, ibf_key_from_hashcode (key));
  83   return GNUNET_YES;
  84 }
  85
  86
  87 static int
  88 remove_iterator (void *cls,
  89                  const struct GNUNET_HashCode *key,
  90                  void *value)
  91 {
  92   struct GNUNET_CONTAINER_MultiHashMap *hashmap = cls;
  93   /* if remove fails, there just was a collision with another key */
  94   (void) GNUNET_CONTAINER_multihashmap_remove (hashmap, value, NULL);
  95   return GNUNET_YES;
  96 }
  97
  98
  99 static void
 100 run (void *cls,
 101      char *const *args,
 102      const char *cfgfile,
 103      const struct GNUNET_CONFIGURATION_Handle *cfg)
 104 {
 105   struct GNUNET_HashCode id;
 106   struct IBF_Key ibf_key;
 107   int i;
 108   int side;
 109   int res;
 110   struct GNUNET_TIME_Absolute start_time;
 111   struct GNUNET_TIME_Relative delta_time;
 112
 113   set_a = GNUNET_CONTAINER_multihashmap_create (((asize == 0) ? 1 : (asize + csize)),
 114                                                  GNUNET_NO);
 115   set_b = GNUNET_CONTAINER_multihashmap_create (((bsize == 0) ? 1 : (bsize + csize)),
 116                                                 GNUNET_NO);
 117   set_c = GNUNET_CONTAINER_multihashmap_create (((csize == 0) ? 1 : csize),
 118                                                 GNUNET_NO);
 119
 120   key_to_hashcode = GNUNET_CONTAINER_multihashmap_create (((asize+bsize+csize == 0) ? 1 : (asize+bsize+csize)),
 121                                                           GNUNET_NO);
 122
 123   printf ("hash-num=%u, size=%u, #(A-B)=%u, #(B-A)=%u, #(A&B)=%u\n",
 124           hash_num, ibf_size, asize, bsize, csize);
 125
 126   i = 0;
 127   while (i < asize)
 128   {
 129     GNUNET_CRYPTO_hash_create_random (random_quality, &id);
 130     if (GNUNET_YES == GNUNET_CONTAINER_multihashmap_contains (set_a, &id))
 131       continue;
 132     GNUNET_break (GNUNET_OK ==
 133                   GNUNET_CONTAINER_multihashmap_put (set_a, &id, NULL,
 134                                                      GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
 135     register_hashcode (&id);
 136     i++;
 137   }
 138   i = 0;
 139   while (i < bsize)
 140   {
 141     GNUNET_CRYPTO_hash_create_random (random_quality, &id);
 142     if (GNUNET_YES == GNUNET_CONTAINER_multihashmap_contains (set_a, &id))
 143       continue;
 144     if (GNUNET_YES == GNUNET_CONTAINER_multihashmap_contains (set_b, &id))
 145       continue;
 146     GNUNET_break (GNUNET_OK ==
 147                   GNUNET_CONTAINER_multihashmap_put (set_b, &id, NULL,
 148                                                      GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
 149     register_hashcode (&id);
 150     i++;
 151   }
 152   i = 0;
 153   while (i < csize)
 154   {
 155     GNUNET_CRYPTO_hash_create_random (random_quality, &id);
 156     if (GNUNET_YES == GNUNET_CONTAINER_multihashmap_contains (set_a, &id))
 157       continue;
 158     if (GNUNET_YES == GNUNET_CONTAINER_multihashmap_contains (set_b, &id))
 159       continue;
 160     if (GNUNET_YES == GNUNET_CONTAINER_multihashmap_contains (set_c, &id))
 161       continue;
 162     GNUNET_break (GNUNET_OK ==
 163                   GNUNET_CONTAINER_multihashmap_put (set_c, &id, NULL,
 164                                                      GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
 165     register_hashcode (&id);
 166     i++;
 167   }
 168
 169   ibf_a = ibf_create (ibf_size, hash_num);
 170   ibf_b = ibf_create (ibf_size, hash_num);
 171   if ( (NULL == ibf_a) ||
 172        (NULL == ibf_b) )
 173   {
 174     /* insufficient memory */
 175     GNUNET_break (0);
 176     GNUNET_SCHEDULER_shutdown ();
 177     return;
 178   }
 179
 180
 181   printf ("generated sets\n");
 182
 183   start_time = GNUNET_TIME_absolute_get ();
 184
 185   GNUNET_CONTAINER_multihashmap_iterate (set_a, &insert_iterator, ibf_a);
 186   GNUNET_CONTAINER_multihashmap_iterate (set_b, &insert_iterator, ibf_b);
 187   GNUNET_CONTAINER_multihashmap_iterate (set_c, &insert_iterator, ibf_a);
 188   GNUNET_CONTAINER_multihashmap_iterate (set_c, &insert_iterator, ibf_b);
 189
 190   delta_time = GNUNET_TIME_absolute_get_duration (start_time);
 191
 192   printf ("encoded in: %s\n",
 193           GNUNET_STRINGS_relative_time_to_string (delta_time,
 194                                                   GNUNET_NO));
 195
 196   ibf_subtract (ibf_a, ibf_b);
 197
 198
 199   start_time = GNUNET_TIME_absolute_get ();
 200
 201   for (i = 0; i <= asize + bsize; i++)
 202   {
 203     res = ibf_decode (ibf_a, &side, &ibf_key);
 204     if (GNUNET_SYSERR == res)
 205     {
 206       printf ("decode failed, %u/%u elements left\n",
 207          GNUNET_CONTAINER_multihashmap_size (set_a) + GNUNET_CONTAINER_multihashmap_size (set_b),
 208          asize + bsize);
 209       return;
 210     }
 211     if (GNUNET_NO == res)
 212     {
 213       if ((0 == GNUNET_CONTAINER_multihashmap_size (set_b)) &&
 214           (0 == GNUNET_CONTAINER_multihashmap_size (set_a)))
 215       {
 216         delta_time = GNUNET_TIME_absolute_get_duration (start_time);
 217         printf ("decoded successfully in: %s\n",
 218                 GNUNET_STRINGS_relative_time_to_string (delta_time,
 219                                                         GNUNET_NO));
 220       }
 221       else
 222       {
 223         printf ("decode missed elements (should never happen)\n");
 224       }
 225       return;
 226     }
 227
 228     if (side == 1)
 229       iter_hashcodes (ibf_key, remove_iterator, set_a);
 230     if (side == -1)
 231       iter_hashcodes (ibf_key, remove_iterator, set_b);
 232   }
 233   printf("cyclic IBF, %u/%u elements left\n",
 234          GNUNET_CONTAINER_multihashmap_size (set_a) + GNUNET_CONTAINER_multihashmap_size (set_b),
 235          asize + bsize);
 236 }
 237
 238
 239 int
 240 main (int argc, char **argv)
 241 {
 242   struct GNUNET_GETOPT_CommandLineOption options[] = {
 243
 244     GNUNET_GETOPT_option_uint ('A',
 245                                    "asize",
 246                                    NULL,
 247                                    gettext_noop ("number of element in set A-B"),
 248                                    &asize),
 249
 250     GNUNET_GETOPT_option_uint ('B',
 251                                    "bsize",
 252                                    NULL,
 253                                    gettext_noop ("number of element in set B-A"),
 254                                    &bsize),
 255
 256     GNUNET_GETOPT_option_uint ('C',
 257                                    "csize",
 258                                    NULL,
 259                                    gettext_noop ("number of common elements in A and B"),
 260                                    &csize),
 261
 262     GNUNET_GETOPT_option_uint ('k',
 263                                    "hash-num",
 264                                    NULL,
 265                                    gettext_noop ("hash num"),
 266                                    &hash_num),
 267
 268     GNUNET_GETOPT_option_uint ('s',
 269                                    "ibf-size",
 270                                    NULL,
 271                                    gettext_noop ("ibf size"),
 272                                    &ibf_size),
 273
 274     GNUNET_GETOPT_OPTION_END
 275   };
 276
 277   GNUNET_PROGRAM_run2 (argc, argv, "gnunet-consensus-ibf",
 278                       "help",
 279                       options, &run, NULL, GNUNET_YES);
 280   return 0;
 281 }