src/regex/plugin_block_regex.c

   1 /*
   2      This file is part of GNUnet
   3      Copyright (C) 2013 GNUnet e.V.
   4
   5      GNUnet is free software; you can redistribute it and/or modify
   6      it under the terms of the GNU General Public License as published
   7      by the Free Software Foundation; either version 3, or (at your
   8      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      General Public License for more details.
  14
  15      You should have received a copy of the GNU General Public License
  16      along with GNUnet; see the file COPYING.  If not, write to the
  17      Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  18      Boston, MA 02110-1301, USA.
  19 */
  20
  21 /**
  22  * @file regex/plugin_block_regex.c
  23  * @brief blocks used for regex storage and search
  24  * @author Bartlomiej Polot
  25  */
  26 #include "platform.h"
  27 #include "gnunet_block_plugin.h"
  28 #include "gnunet_block_group_lib.h"
  29 #include "block_regex.h"
  30 #include "regex_block_lib.h"
  31 #include "gnunet_signatures.h"
  32
  33
  34
  35 /**
  36  * Number of bits we set per entry in the bloomfilter.
  37  * Do not change!
  38  */
  39 #define BLOOMFILTER_K 16
  40
  41
  42 /**
  43  * How big is the BF we use for REGEX blocks?
  44  */
  45 #define REGEX_BF_SIZE 8
  46
  47
  48 /**
  49  * How many bytes should a bloomfilter be if we have already seen
  50  * entry_count responses?  Note that #GNUNET_CONSTANTS_BLOOMFILTER_K
  51  * gives us the number of bits set per entry.  Furthermore, we should
  52  * not re-size the filter too often (to keep it cheap).
  53  *
  54  * Since other peers will also add entries but not resize the filter,
  55  * we should generally pick a slightly larger size than what the
  56  * strict math would suggest.
  57  *
  58  * @param entry_count expected number of entries in the Bloom filter
  59  * @return must be a power of two and smaller or equal to 2^15.
  60  */
  61 static size_t
  62 compute_bloomfilter_size (unsigned int entry_count)
  63 {
  64   size_t size;
  65   unsigned int ideal = (entry_count * BLOOMFILTER_K) / 4;
  66   uint16_t max = 1 << 15;
  67
  68   if (entry_count > max)
  69     return max;
  70   size = 8;
  71   while ((size < max) && (size < ideal))
  72     size *= 2;
  73   if (size > max)
  74     return max;
  75   return size;
  76 }
  77
  78
  79 /**
  80  * Create a new block group.
  81  *
  82  * @param ctx block context in which the block group is created
  83  * @param type type of the block for which we are creating the group
  84  * @param nonce random value used to seed the group creation
  85  * @param raw_data optional serialized prior state of the group, NULL if unavailable/fresh
  86  * @param raw_data_size number of bytes in @a raw_data, 0 if unavailable/fresh
  87  * @param va variable arguments specific to @a type
  88  * @return block group handle, NULL if block groups are not supported
  89  *         by this @a type of block (this is not an error)
  90  */
  91 static struct GNUNET_BLOCK_Group *
  92 block_plugin_regex_create_group (void *cls,
  93                                  enum GNUNET_BLOCK_Type type,
  94                                  uint32_t nonce,
  95                                  const void *raw_data,
  96                                  size_t raw_data_size,
  97                                  va_list va)
  98 {
  99   unsigned int bf_size;
 100   const char *guard;
 101
 102   guard = va_arg (va, const char *);
 103   if (0 == memcmp (guard,
 104                    "seen-set-size",
 105                    strlen ("seen-set-size")))
 106     bf_size = compute_bloomfilter_size (va_arg (va, unsigned int));
 107   else if (0 == memcmp (guard,
 108                         "filter-size",
 109                         strlen ("filter-size")))
 110     bf_size = va_arg (va, unsigned int);
 111   else
 112   {
 113     GNUNET_break (0);
 114     bf_size = REGEX_BF_SIZE;
 115   }
 116   GNUNET_break (NULL == va_arg (va, const char *));
 117   return GNUNET_BLOCK_GROUP_bf_create (cls,
 118                                        bf_size,
 119                                        BLOOMFILTER_K,
 120                                        type,
 121                                        nonce,
 122                                        raw_data,
 123                                        raw_data_size);
 124 }
 125
 126
 127 /**
 128  * Function called to validate a reply or a request of type
 129  * #GNUNET_BLOCK_TYPE_REGEX.
 130  * For request evaluation, pass "NULL" for the reply_block.
 131  * Note that it is assumed that the reply has already been
 132  * matched to the key (and signatures checked) as it would
 133  * be done with the #GNUNET_BLOCK_get_key() function.
 134  *
 135  * @param cls closure
 136  * @param type block type
 137  * @param bg block group to evaluate against
 138  * @param eo control flags
 139  * @param query original query (hash)
 140  * @param xquery extrended query data (can be NULL, depending on type)
 141  * @param xquery_size number of bytes in @a xquery
 142  * @param reply_block response to validate
 143  * @param reply_block_size number of bytes in @a reply_block
 144  * @return characterization of result
 145  */
 146 static enum GNUNET_BLOCK_EvaluationResult
 147 evaluate_block_regex (void *cls,
 148                       enum GNUNET_BLOCK_Type type,
 149                       struct GNUNET_BLOCK_Group *bg,
 150                       enum GNUNET_BLOCK_EvaluationOptions eo,
 151                       const struct GNUNET_HashCode *query,
 152                       const void *xquery,
 153                       size_t xquery_size,
 154                       const void *reply_block,
 155                       size_t reply_block_size)
 156 {
 157   struct GNUNET_HashCode chash;
 158
 159   if (NULL == reply_block)
 160   {
 161     if (0 != xquery_size)
 162       {
 163         const char *s;
 164
 165         s = (const char *) xquery;
 166         if ('\0' != s[xquery_size - 1]) /* must be valid 0-terminated string */
 167           {
 168             GNUNET_break_op (0);
 169             return GNUNET_BLOCK_EVALUATION_REQUEST_INVALID;
 170           }
 171       }
 172     return GNUNET_BLOCK_EVALUATION_REQUEST_VALID;
 173   }
 174   if (0 != xquery_size)
 175   {
 176     const char *s;
 177
 178     s = (const char *) xquery;
 179     if ('\0' != s[xquery_size - 1]) /* must be valid 0-terminated string */
 180     {
 181       GNUNET_break_op (0);
 182       return GNUNET_BLOCK_EVALUATION_REQUEST_INVALID;
 183     }
 184   }
 185   else if (NULL != query)
 186   {
 187     /* xquery is required for regex GETs, at least an empty string */
 188     GNUNET_break_op (0);
 189     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "type %d, query %p, xquery %p\n",
 190                 type, query, xquery);
 191     return GNUNET_BLOCK_EVALUATION_REQUEST_INVALID;
 192   }
 193   switch (REGEX_BLOCK_check (reply_block,
 194                              reply_block_size,
 195                              query,
 196                              xquery))
 197   {
 198     case GNUNET_SYSERR:
 199       GNUNET_break_op(0);
 200       return GNUNET_BLOCK_EVALUATION_RESULT_INVALID;
 201     case GNUNET_NO:
 202       /* xquery missmatch, can happen */
 203       return GNUNET_BLOCK_EVALUATION_RESULT_IRRELEVANT;
 204     default:
 205       break;
 206   }
 207   GNUNET_CRYPTO_hash (reply_block,
 208                       reply_block_size,
 209                       &chash);
 210   if (GNUNET_YES ==
 211       GNUNET_BLOCK_GROUP_bf_test_and_set (bg,
 212                                           &chash))
 213     return GNUNET_BLOCK_EVALUATION_OK_DUPLICATE;
 214   return GNUNET_BLOCK_EVALUATION_OK_MORE;
 215 }
 216
 217
 218 /**
 219  * Function called to validate a reply or a request of type
 220  * #GNUNET_BLOCK_TYPE_REGEX_ACCEPT.
 221  * For request evaluation, pass "NULL" for the reply_block.
 222  * Note that it is assumed that the reply has already been
 223  * matched to the key (and signatures checked) as it would
 224  * be done with the #GNUNET_BLOCK_get_key() function.
 225  *
 226  * @param cls closure
 227  * @param type block type
 228  * @param bg block group to evaluate against
 229  * @param eo control flags
 230  * @param query original query (hash)
 231  * @param xquery extrended query data (can be NULL, depending on type)
 232  * @param xquery_size number of bytes in @a xquery
 233  * @param reply_block response to validate
 234  * @param reply_block_size number of bytes in @a reply_block
 235  * @return characterization of result
 236  */
 237 static enum GNUNET_BLOCK_EvaluationResult
 238 evaluate_block_regex_accept (void *cls,
 239                              enum GNUNET_BLOCK_Type type,
 240                              struct GNUNET_BLOCK_Group *bg,
 241                              enum GNUNET_BLOCK_EvaluationOptions eo,
 242                              const struct GNUNET_HashCode *query,
 243                              const void *xquery,
 244                              size_t xquery_size, const void *reply_block,
 245                              size_t reply_block_size)
 246 {
 247   const struct RegexAcceptBlock *rba;
 248   struct GNUNET_HashCode chash;
 249
 250   if (0 != xquery_size)
 251   {
 252     GNUNET_break_op (0);
 253     return GNUNET_BLOCK_EVALUATION_REQUEST_INVALID;
 254   }
 255   if (NULL == reply_block)
 256     return GNUNET_BLOCK_EVALUATION_REQUEST_VALID;
 257   if (sizeof (struct RegexAcceptBlock) != reply_block_size)
 258   {
 259     GNUNET_break_op(0);
 260     return GNUNET_BLOCK_EVALUATION_RESULT_INVALID;
 261   }
 262   rba = reply_block;
 263   if (ntohl (rba->purpose.size) !=
 264       sizeof (struct GNUNET_CRYPTO_EccSignaturePurpose) +
 265       sizeof (struct GNUNET_TIME_AbsoluteNBO) +
 266       sizeof (struct GNUNET_HashCode))
 267   {
 268     GNUNET_break_op(0);
 269     return GNUNET_BLOCK_EVALUATION_RESULT_INVALID;
 270   }
 271   if (0 == GNUNET_TIME_absolute_get_remaining (GNUNET_TIME_absolute_ntoh (rba->expiration_time)).rel_value_us)
 272   {
 273     /* technically invalid, but can happen without an error, so
 274        we're nice by reporting it as a 'duplicate' */
 275     return GNUNET_BLOCK_EVALUATION_OK_DUPLICATE;
 276   }
 277   if (GNUNET_OK !=
 278       GNUNET_CRYPTO_eddsa_verify (GNUNET_SIGNATURE_PURPOSE_REGEX_ACCEPT,
 279                                 &rba->purpose,
 280                                 &rba->signature,
 281                                 &rba->peer.public_key))
 282   {
 283     GNUNET_break_op(0);
 284     return GNUNET_BLOCK_EVALUATION_RESULT_INVALID;
 285   }
 286   GNUNET_CRYPTO_hash (reply_block,
 287                       reply_block_size,
 288                       &chash);
 289   if (GNUNET_YES ==
 290       GNUNET_BLOCK_GROUP_bf_test_and_set (bg,
 291                                           &chash))
 292     return GNUNET_BLOCK_EVALUATION_OK_DUPLICATE;
 293   return GNUNET_BLOCK_EVALUATION_OK_MORE;
 294 }
 295
 296
 297 /**
 298  * Function called to validate a reply or a request.  For
 299  * request evaluation, simply pass "NULL" for the reply_block.
 300  * Note that it is assumed that the reply has already been
 301  * matched to the key (and signatures checked) as it would
 302  * be done with the #GNUNET_BLOCK_get_key() function.
 303  *
 304  * @param cls closure
 305  * @param type block type
 306  * @param bg group to evaluate against
 307  * @param eo control flags
 308  * @param query original query (hash)
 309  * @param xquery extrended query data (can be NULL, depending on type)
 310  * @param xquery_size number of bytes in xquery
 311  * @param reply_block response to validate
 312  * @param reply_block_size number of bytes in reply block
 313  * @return characterization of result
 314  */
 315 static enum GNUNET_BLOCK_EvaluationResult
 316 block_plugin_regex_evaluate (void *cls,
 317                              enum GNUNET_BLOCK_Type type,
 318                              struct GNUNET_BLOCK_Group *bg,
 319                              enum GNUNET_BLOCK_EvaluationOptions eo,
 320                              const struct GNUNET_HashCode *query,
 321                              const void *xquery,
 322                              size_t xquery_size,
 323                              const void *reply_block,
 324                              size_t reply_block_size)
 325 {
 326   enum GNUNET_BLOCK_EvaluationResult result;
 327
 328   switch (type)
 329   {
 330     case GNUNET_BLOCK_TYPE_REGEX:
 331       result = evaluate_block_regex (cls,
 332                                      type,
 333                                      bg,
 334                                      eo,
 335                                      query,
 336                                      xquery, xquery_size,
 337                                      reply_block, reply_block_size);
 338       break;
 339     case GNUNET_BLOCK_TYPE_REGEX_ACCEPT:
 340       result = evaluate_block_regex_accept (cls,
 341                                             type,
 342                                             bg,
 343                                             eo,
 344                                             query,
 345                                             xquery, xquery_size,
 346                                             reply_block, reply_block_size);
 347       break;
 348
 349     default:
 350       result = GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED;
 351   }
 352   return result;
 353 }
 354
 355
 356 /**
 357  * Function called to obtain the key for a block.
 358  *
 359  * @param cls closure
 360  * @param type block type
 361  * @param block block to get the key for
 362  * @param block_size number of bytes in @a block
 363  * @param key set to the key (query) for the given block
 364  * @return #GNUNET_OK on success, #GNUNET_SYSERR if type not supported
 365  *         (or if extracting a key from a block of this type does not work)
 366  */
 367 static int
 368 block_plugin_regex_get_key (void *cls,
 369                             enum GNUNET_BLOCK_Type type,
 370                             const void *block,
 371                             size_t block_size,
 372                             struct GNUNET_HashCode *key)
 373 {
 374   switch (type)
 375   {
 376     case GNUNET_BLOCK_TYPE_REGEX:
 377       if (GNUNET_OK !=
 378           REGEX_BLOCK_get_key (block, block_size,
 379                                key))
 380       {
 381         GNUNET_break_op (0);
 382         return GNUNET_NO;
 383       }
 384       return GNUNET_OK;
 385     case GNUNET_BLOCK_TYPE_REGEX_ACCEPT:
 386       if (sizeof (struct RegexAcceptBlock) != block_size)
 387       {
 388         GNUNET_break_op (0);
 389         return GNUNET_NO;
 390       }
 391       *key = ((struct RegexAcceptBlock *) block)->key;
 392       return GNUNET_OK;
 393     default:
 394       GNUNET_break (0);
 395       return GNUNET_SYSERR;
 396   }
 397 }
 398
 399
 400 /**
 401  * Entry point for the plugin.
 402  */
 403 void *
 404 libgnunet_plugin_block_regex_init (void *cls)
 405 {
 406   static enum GNUNET_BLOCK_Type types[] =
 407   {
 408     GNUNET_BLOCK_TYPE_REGEX,
 409     GNUNET_BLOCK_TYPE_REGEX_ACCEPT,
 410     GNUNET_BLOCK_TYPE_ANY       /* end of list */
 411   };
 412   struct GNUNET_BLOCK_PluginFunctions *api;
 413
 414   api = GNUNET_new (struct GNUNET_BLOCK_PluginFunctions);
 415   api->evaluate = &block_plugin_regex_evaluate;
 416   api->get_key = &block_plugin_regex_get_key;
 417   api->create_group = &block_plugin_regex_create_group;
 418   api->types = types;
 419   return api;
 420 }
 421
 422
 423 /**
 424  * Exit point from the plugin.
 425  */
 426 void *
 427 libgnunet_plugin_block_regex_done (void *cls)
 428 {
 429   struct GNUNET_TRANSPORT_PluginFunctions *api = cls;
 430
 431   GNUNET_free (api);
 432   return NULL;
 433 }
 434
 435 /* end of plugin_block_regex.c */