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