src/regex/regex_block_lib.c

   1 /*
   2      This file is part of GNUnet.
   3      Copyright (C) 2012,2013 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  */
  20 /**
  21  * @author Bartlomiej Polot
  22  * @file regex/regex_block_lib.c
  23  * @brief functions for manipulating non-accept blocks stored for
  24  *        regex in the DHT
  25  */
  26 #include "platform.h"
  27 #include "regex_block_lib.h"
  28 #include "gnunet_constants.h"
  29
  30 #define LOG(kind, ...) GNUNET_log_from(kind, "regex-bck", __VA_ARGS__)
  31
  32 GNUNET_NETWORK_STRUCT_BEGIN
  33
  34 /**
  35  * Information for each edge.
  36  */
  37 struct EdgeInfo {
  38   /**
  39    * Index of the destination of this edge in the
  40    * unique destinations array.
  41    */
  42   uint16_t destination_index GNUNET_PACKED;
  43
  44   /**
  45    * Number of bytes the token for this edge takes in the
  46    * token area.
  47    */
  48   uint16_t token_length GNUNET_PACKED;
  49 };
  50
  51
  52 /**
  53  * @brief Block to announce a regex state.
  54  */
  55 struct RegexBlock {
  56   /**
  57    * Length of the proof regex string.
  58    */
  59   uint16_t proof_len GNUNET_PACKED;
  60
  61   /**
  62    * Is this state an accepting state?
  63    */
  64   int16_t is_accepting GNUNET_PACKED;
  65
  66   /**
  67    * Number of edges parting from this state.
  68    */
  69   uint16_t num_edges GNUNET_PACKED;
  70
  71   /**
  72    * Nubmer of unique destinations reachable from this state.
  73    */
  74   uint16_t num_destinations GNUNET_PACKED;
  75
  76   /* followed by 'struct GNUNET_HashCode[num_destinations]' */
  77
  78   /* followed by 'struct EdgeInfo[edge_destination_indices]' */
  79
  80   /* followed by 'char proof[n_proof]', NOT 0-terminated */
  81
  82   /* followed by 'char tokens[num_edges][edge_info[k].token_length]';
  83      essentially all of the tokens one after the other in the
  84      order of the edges; tokens are NOT 0-terminated */
  85 };
  86
  87
  88 GNUNET_NETWORK_STRUCT_END
  89
  90
  91 /**
  92  * Test if this block is marked as being an accept state.
  93  *
  94  * @param block block to test
  95  * @param size number of bytes in block
  96  * @return #GNUNET_YES if the block is accepting, #GNUNET_NO if not
  97  */
  98 int
  99 GNUNET_BLOCK_is_accepting(const struct RegexBlock *block,
 100                           size_t size)
 101 {
 102   if (size < sizeof(struct RegexBlock))
 103     {
 104       GNUNET_break_op(0);
 105       return GNUNET_SYSERR;
 106     }
 107   return ntohs(block->is_accepting);
 108 }
 109
 110
 111 /**
 112  * Check if the given 'proof' matches the given 'key'.
 113  *
 114  * @param proof partial regex of a state
 115  * @param proof_len number of bytes in 'proof'
 116  * @param key hash of a state.
 117  * @return #GNUNET_OK if the proof is valid for the given key.
 118  */
 119 int
 120 REGEX_BLOCK_check_proof(const char *proof,
 121                         size_t proof_len,
 122                         const struct GNUNET_HashCode *key)
 123 {
 124   struct GNUNET_HashCode key_check;
 125
 126   if ((NULL == proof) || (NULL == key))
 127     {
 128       GNUNET_log(GNUNET_ERROR_TYPE_ERROR, "Proof check failed, was NULL.\n");
 129       return GNUNET_NO;
 130     }
 131   GNUNET_CRYPTO_hash(proof, proof_len, &key_check);
 132   return (0 ==
 133           GNUNET_CRYPTO_hash_cmp(key, &key_check)) ? GNUNET_OK : GNUNET_NO;
 134 }
 135
 136
 137 /**
 138  * Struct to keep track of the xquery while iterating all the edges in a block.
 139  */
 140 struct CheckEdgeContext {
 141   /**
 142    * Xquery: string we are looking for.
 143    */
 144   const char *xquery;
 145
 146   /**
 147    * Has any edge matched the xquery so far? (GNUNET_OK / GNUNET_NO)
 148    */
 149   int found;
 150 };
 151
 152
 153 /**
 154  * Iterator over all edges in a block, checking for a presence of a given query.
 155  *
 156  * @param cls Closure, (xquery context).
 157  * @param token Token that follows to next state.
 158  * @param len Lenght of token.
 159  * @param key Hash of next state.
 160  *
 161  * @return #GNUNET_YES, to keep iterating
 162  */
 163 static int
 164 check_edge(void *cls,
 165            const char *token,
 166            size_t len,
 167            const struct GNUNET_HashCode *key)
 168 {
 169   struct CheckEdgeContext *ctx = cls;
 170
 171   GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 172              "edge %.*s [%u]: %s\n",
 173              (int)len,
 174              token,
 175              (unsigned int)len,
 176              GNUNET_h2s(key));
 177   if (NULL == ctx->xquery)
 178     return GNUNET_YES;
 179   if (strlen(ctx->xquery) < len)
 180     return GNUNET_YES; /* too long */
 181   if (0 == strncmp(ctx->xquery, token, len))
 182     ctx->found = GNUNET_OK;
 183   return GNUNET_YES; /* keep checking for malformed data! */
 184 }
 185
 186
 187 /**
 188  * Check if the regex block is well formed, including all edges.
 189  *
 190  * @param block The start of the block.
 191  * @param size The size of the block.
 192  * @param query the query for the block
 193  * @param xquery String describing the edge we are looking for.
 194  *               Can be NULL in case this is a put block.
 195  * @return #GNUNET_OK in case it's fine.
 196  *         #GNUNET_NO in case the xquery exists and is not found (IRRELEVANT).
 197  *         #GNUNET_SYSERR if the block is invalid.
 198  */
 199 int
 200 REGEX_BLOCK_check(const struct RegexBlock *block,
 201                   size_t size,
 202                   const struct GNUNET_HashCode *query,
 203                   const char *xquery)
 204 {
 205   struct GNUNET_HashCode key;
 206   struct CheckEdgeContext ctx;
 207   int res;
 208
 209   LOG(GNUNET_ERROR_TYPE_DEBUG,
 210       "Block check\n");
 211   if (GNUNET_OK !=
 212       REGEX_BLOCK_get_key(block, size,
 213                           &key))
 214     {
 215       GNUNET_break_op(0);
 216       return GNUNET_SYSERR;
 217     }
 218   if (NULL != query &&
 219       0 != GNUNET_memcmp(&key,
 220                          query))
 221     {
 222       GNUNET_break_op(0);
 223       return GNUNET_SYSERR;
 224     }
 225   if ((GNUNET_YES == ntohs(block->is_accepting)) &&
 226       ((NULL == xquery) || ('\0' == xquery[0])))
 227     {
 228       LOG(GNUNET_ERROR_TYPE_DEBUG,
 229           "  out! Is accepting: %u, xquery %p\n",
 230           ntohs(block->is_accepting),
 231           xquery);
 232       return GNUNET_OK;
 233     }
 234   ctx.xquery = xquery;
 235   ctx.found = GNUNET_NO;
 236   res = REGEX_BLOCK_iterate(block, size, &check_edge, &ctx);
 237   if (GNUNET_SYSERR == res)
 238     return GNUNET_SYSERR;
 239   if (NULL == xquery)
 240     return GNUNET_YES;
 241   LOG(GNUNET_ERROR_TYPE_DEBUG, "Result %d\n", ctx.found);
 242   return ctx.found;
 243 }
 244
 245
 246 /**
 247  * Obtain the key that a particular block is to be stored under.
 248  *
 249  * @param block block to get the key from
 250  * @param block_len number of bytes in block
 251  * @param key where to store the key
 252  * @return #GNUNET_OK on success, #GNUNET_SYSERR if the block is malformed
 253  */
 254 int
 255 REGEX_BLOCK_get_key(const struct RegexBlock *block,
 256                     size_t block_len,
 257                     struct GNUNET_HashCode *key)
 258 {
 259   uint16_t len;
 260   const struct GNUNET_HashCode *destinations;
 261   const struct EdgeInfo *edges;
 262   uint16_t num_destinations;
 263   uint16_t num_edges;
 264   size_t total;
 265
 266   if (block_len < sizeof(struct RegexBlock))
 267     {
 268       GNUNET_break_op(0);
 269       return GNUNET_SYSERR;
 270     }
 271   num_destinations = ntohs(block->num_destinations);
 272   num_edges = ntohs(block->num_edges);
 273   len = ntohs(block->proof_len);
 274   destinations = (const struct GNUNET_HashCode *)&block[1];
 275   edges = (const struct EdgeInfo *)&destinations[num_destinations];
 276   total = sizeof(struct RegexBlock) + num_destinations * sizeof(struct GNUNET_HashCode) + num_edges * sizeof(struct EdgeInfo) + len;
 277   if (block_len < total)
 278     {
 279       GNUNET_break_op(0);
 280       return GNUNET_SYSERR;
 281     }
 282   GNUNET_CRYPTO_hash(&edges[num_edges], len, key);
 283   return GNUNET_OK;
 284 }
 285
 286
 287 /**
 288  * Iterate over all edges of a block of a regex state.
 289  *
 290  * @param block Block to iterate over.
 291  * @param size Size of @a block.
 292  * @param iterator Function to call on each edge in the block.
 293  * @param iter_cls Closure for the @a iterator.
 294  * @return #GNUNET_SYSERR if an error has been encountered.
 295  *         #GNUNET_OK if no error has been encountered.
 296  *           Note that if the iterator stops the iteration by returning
 297  *         #GNUNET_NO, the block will no longer be checked for further errors.
 298  *           The return value will be GNUNET_OK meaning that no errors were
 299  *         found until the edge last notified to the iterator, but there might
 300  *         be errors in further edges.
 301  */
 302 int
 303 REGEX_BLOCK_iterate(const struct RegexBlock *block,
 304                     size_t size,
 305                     REGEX_INTERNAL_EgdeIterator iterator,
 306                     void *iter_cls)
 307 {
 308   uint16_t len;
 309   const struct GNUNET_HashCode *destinations;
 310   const struct EdgeInfo *edges;
 311   const char *aux;
 312   uint16_t num_destinations;
 313   uint16_t num_edges;
 314   size_t total;
 315   unsigned int n;
 316   size_t off;
 317
 318   LOG(GNUNET_ERROR_TYPE_DEBUG, "Block iterate\n");
 319   if (size < sizeof(struct RegexBlock))
 320     {
 321       GNUNET_break_op(0);
 322       return GNUNET_SYSERR;
 323     }
 324   num_destinations = ntohs(block->num_destinations);
 325   num_edges = ntohs(block->num_edges);
 326   len = ntohs(block->proof_len);
 327   destinations = (const struct GNUNET_HashCode *)&block[1];
 328   edges = (const struct EdgeInfo *)&destinations[num_destinations];
 329   aux = (const char *)&edges[num_edges];
 330   total = sizeof(struct RegexBlock) + num_destinations * sizeof(struct GNUNET_HashCode) + num_edges * sizeof(struct EdgeInfo) + len;
 331   if (size < total)
 332     {
 333       GNUNET_break_op(0);
 334       return GNUNET_SYSERR;
 335     }
 336   for (n = 0; n < num_edges; n++)
 337     total += ntohs(edges[n].token_length);
 338   if (size != total)
 339     {
 340       fprintf(stderr, "Expected %u, got %u\n",
 341               (unsigned int)size,
 342               (unsigned int)total);
 343       GNUNET_break_op(0);
 344       return GNUNET_SYSERR;
 345     }
 346   off = len;
 347   LOG(GNUNET_ERROR_TYPE_DEBUG,
 348       "Start iterating block of size %u, proof %u, off %u edges %u\n",
 349       size, len, off, n);
 350   /* &aux[off] always points to our token */
 351   for (n = 0; n < num_edges; n++)
 352     {
 353       LOG(GNUNET_ERROR_TYPE_DEBUG,
 354           "Edge %u/%u, off %u tokenlen %u (%.*s)\n",
 355           n + 1, num_edges, off,
 356           ntohs(edges[n].token_length), ntohs(edges[n].token_length),
 357           &aux[off]);
 358       if (NULL != iterator)
 359         if (GNUNET_NO == iterator(iter_cls,
 360                                   &aux[off],
 361                                   ntohs(edges[n].token_length),
 362                                   &destinations[ntohs(edges[n].destination_index)]))
 363           return GNUNET_OK;
 364       off += ntohs(edges[n].token_length);
 365     }
 366   return GNUNET_OK;
 367 }
 368
 369
 370 /**
 371  * Construct a regex block to be stored in the DHT.
 372  *
 373  * @param proof proof string for the block
 374  * @param num_edges number of edges in the block
 375  * @param edges the edges of the block
 376  * @param accepting is this an accepting state
 377  * @param rsize set to the size of the returned block (OUT-only)
 378  * @return the regex block, NULL on error
 379  */
 380 struct RegexBlock *
 381 REGEX_BLOCK_create(const char *proof,
 382                    unsigned int num_edges,
 383                    const struct REGEX_BLOCK_Edge *edges,
 384                    int accepting,
 385                    size_t *rsize)
 386 {
 387   struct RegexBlock *block;
 388   struct GNUNET_HashCode destinations[1024]; /* 1024 = 64k/64 bytes/key == absolute MAX */
 389   uint16_t destination_indices[num_edges];
 390   struct GNUNET_HashCode *dests;
 391   struct EdgeInfo *edgeinfos;
 392   size_t off;
 393   size_t len;
 394   size_t total;
 395   size_t slen;
 396   unsigned int unique_destinations;
 397   unsigned int j;
 398   unsigned int i;
 399   char *aux;
 400
 401   len = strlen(proof);
 402   if (len > UINT16_MAX)
 403     {
 404       GNUNET_break(0);
 405       return NULL;
 406     }
 407   unique_destinations = 0;
 408   total = sizeof(struct RegexBlock) + len;
 409   for (i = 0; i < num_edges; i++)
 410     {
 411       slen = strlen(edges[i].label);
 412       if (slen > UINT16_MAX)
 413         {
 414           GNUNET_break(0);
 415           return NULL;
 416         }
 417       total += slen;
 418       for (j = 0; j < unique_destinations; j++)
 419         if (0 == memcmp(&destinations[j],
 420                         &edges[i].destination,
 421                         sizeof(struct GNUNET_HashCode)))
 422           break;
 423       if (j >= 1024)
 424         {
 425           GNUNET_break(0);
 426           return NULL;
 427         }
 428       destination_indices[i] = j;
 429       if (j == unique_destinations)
 430         destinations[unique_destinations++] = edges[i].destination;
 431     }
 432   total += num_edges * sizeof(struct EdgeInfo) + unique_destinations * sizeof(struct GNUNET_HashCode);
 433   if (total >= GNUNET_CONSTANTS_MAX_BLOCK_SIZE)
 434     {
 435       GNUNET_break(0);
 436       return NULL;
 437     }
 438   block = GNUNET_malloc(total);
 439   block->proof_len = htons(len);
 440   block->is_accepting = htons(accepting);
 441   block->num_edges = htons(num_edges);
 442   block->num_destinations = htons(unique_destinations);
 443   dests = (struct GNUNET_HashCode *)&block[1];
 444   GNUNET_memcpy(dests, destinations, sizeof(struct GNUNET_HashCode) * unique_destinations);
 445   edgeinfos = (struct EdgeInfo *)&dests[unique_destinations];
 446   aux = (char *)&edgeinfos[num_edges];
 447   off = len;
 448   GNUNET_memcpy(aux, proof, len);
 449   for (i = 0; i < num_edges; i++)
 450     {
 451       slen = strlen(edges[i].label);
 452       edgeinfos[i].token_length = htons((uint16_t)slen);
 453       edgeinfos[i].destination_index = htons(destination_indices[i]);
 454       GNUNET_memcpy(&aux[off],
 455                     edges[i].label,
 456                     slen);
 457       off += slen;
 458     }
 459   *rsize = total;
 460   return block;
 461 }
 462
 463
 464 /* end of regex_block_lib.c */