src/regex/regex_block_lib.c

   1 /*
   2      This file is part of GNUnet.
   3      (C) 2012,2013 Christian Grothoff (and other contributing authors)
   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., 59 Temple Place - Suite 330,
  18      Boston, MA 02111-1307, USA.
  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
  29 #define LOG(kind,...) GNUNET_log_from (kind,"regex-bck",__VA_ARGS__)
  30
  31 GNUNET_NETWORK_STRUCT_BEGIN
  32
  33 /**
  34  * @brief Block to announce a regex state.
  35  */
  36 struct RegexBlock
  37 {
  38
  39   /**
  40    * Length of the proof regex string.
  41    */
  42   uint16_t proof_len GNUNET_PACKED;
  43
  44   /**
  45    * Is this state an accepting state?
  46    */
  47   int16_t is_accepting GNUNET_PACKED;
  48
  49   /**
  50    * Numer of edges parting from this state.
  51    */
  52   uint32_t n_edges GNUNET_PACKED;
  53
  54   /* char proof[n_proof] */
  55   /* struct RegexEdge edges[n_edges] */
  56 };
  57
  58
  59 /**
  60  * @brief A RegexBlock contains one or more of this struct in the payload.
  61  */
  62 struct RegexEdge
  63 {
  64   /**
  65    * Destination of this edge.
  66    */
  67   struct GNUNET_HashCode key;
  68
  69   /**
  70    * Length of the token towards the new state.
  71    */
  72   uint32_t n_token GNUNET_PACKED;
  73
  74   /* char token[n_token] */
  75 };
  76
  77
  78 GNUNET_NETWORK_STRUCT_END
  79
  80
  81 /**
  82  * Test if this block is marked as being an accept state.
  83  *
  84  * @param block block to test
  85  * @return GNUNET_YES if the block is accepting, GNUNET_NO if not
  86  */
  87 int
  88 GNUNET_BLOCK_is_accepting (const struct RegexBlock *block)
  89 {
  90   return ntohs (block->is_accepting);
  91 }
  92
  93
  94 /**
  95  * Check if the given 'proof' matches the given 'key'.
  96  *
  97  * @param proof partial regex of a state
  98  * @param proof_len number of bytes in 'proof'
  99  * @param key hash of a state.
 100  *
 101  * @return GNUNET_OK if the proof is valid for the given key.
 102  */
 103 int
 104 REGEX_BLOCK_check_proof (const char *proof,
 105                          size_t proof_len,
 106                          const struct GNUNET_HashCode *key)
 107 {
 108   struct GNUNET_HashCode key_check;
 109
 110   if ( (NULL == proof) || (NULL == key))
 111   {
 112     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Proof check failed, was NULL.\n");
 113     return GNUNET_NO;
 114   }
 115   GNUNET_CRYPTO_hash (proof, proof_len, &key_check);
 116   return (0 ==
 117           GNUNET_CRYPTO_hash_cmp (key, &key_check)) ? GNUNET_OK : GNUNET_NO;
 118 }
 119
 120
 121 /**
 122  * Struct to keep track of the xquery while iterating all the edges in a block.
 123  */
 124 struct CheckEdgeContext
 125 {
 126   /**
 127    * Xquery: string we are looking for.
 128    */
 129   const char *xquery;
 130
 131   /**
 132    * Has any edge matched the xquery so far? (GNUNET_OK / GNUNET_NO)
 133    */
 134   int found;
 135
 136 };
 137
 138
 139 /**
 140  * Iterator over all edges in a block, checking for a presence of a given query.
 141  *
 142  * @param cls Closure, (xquery context).
 143  * @param token Token that follows to next state.
 144  * @param len Lenght of token.
 145  * @param key Hash of next state.
 146  *
 147  * @return GNUNET_YES, to keep iterating
 148  */
 149 static int
 150 check_edge (void *cls,
 151             const char *token,
 152             size_t len,
 153             const struct GNUNET_HashCode *key)
 154 {
 155   struct CheckEdgeContext *ctx = cls;
 156
 157   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 158               "edge %.*s [%u]: %s->%s\n",
 159               (int) len, token, len, GNUNET_h2s(key));
 160   if (NULL == ctx->xquery)
 161     return GNUNET_YES;
 162   if (strlen (ctx->xquery) < len)
 163     return GNUNET_YES; /* too long */
 164   if (0 == strncmp (ctx->xquery, token, len))
 165     ctx->found = GNUNET_OK;
 166   return GNUNET_YES; /* keep checking for malformed data! */
 167 }
 168
 169
 170 /**
 171  * Check if the regex block is well formed, including all edges.
 172  *
 173  * @param block The start of the block.
 174  * @param size The size of the block.
 175  * @param query the query for the block
 176  * @param xquery String describing the edge we are looking for.
 177  *               Can be NULL in case this is a put block.
 178  *
 179  * @return GNUNET_OK in case it's fine.
 180  *         GNUNET_NO in case the xquery exists and is not found (IRRELEVANT).
 181  *         GNUNET_SYSERR if the block is invalid.
 182  */
 183 int
 184 REGEX_BLOCK_check (const struct RegexBlock *block,
 185                    size_t size,
 186                    const struct GNUNET_HashCode *query,
 187                    const char *xquery)
 188 {
 189   struct CheckEdgeContext ctx;
 190   int res;
 191   uint16_t len;
 192
 193   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 194               "Checking block with xquery `%s'\n",
 195               NULL != xquery ? xquery : "NULL");
 196   len = ntohs (block->proof_len);
 197   if (size < sizeof (struct RegexBlock) + len)
 198   {
 199     GNUNET_break_op (0);
 200     return GNUNET_SYSERR;
 201   }
 202   if (GNUNET_OK != REGEX_BLOCK_check_proof ((const char *) &block[1], len, query))
 203   {
 204     GNUNET_break_op (0);
 205     return GNUNET_SYSERR;
 206   }
 207   if ( (GNUNET_YES == ntohs (block->is_accepting)) &&
 208        ( (NULL == xquery) || ('\0' == xquery[0]) ) )
 209     return GNUNET_OK;
 210   ctx.xquery = xquery;
 211   ctx.found = GNUNET_NO;
 212   res = REGEX_BLOCK_iterate (block, size, &check_edge, &ctx);
 213   if (GNUNET_SYSERR == res)
 214     return GNUNET_SYSERR;
 215   if (NULL == xquery)
 216     return GNUNET_YES;
 217   return ctx.found;
 218 }
 219
 220
 221 /**
 222  * Obtain the key that a particular block is to be stored under.
 223  *
 224  * @param block block to get the key from
 225  * @param block_len number of bytes in block
 226  * @param query where to store the key
 227  * @return GNUNET_OK on success, GNUNET_SYSERR if the block is malformed
 228  */
 229 int
 230 REGEX_BLOCK_get_key (const struct RegexBlock *block,
 231                      size_t block_len,
 232                      struct GNUNET_HashCode *key)
 233 {
 234   uint16_t len;
 235
 236   len = ntohs (block->proof_len);
 237   if (block_len < sizeof (struct RegexBlock) + len)
 238   {
 239     GNUNET_break_op (0);
 240     return GNUNET_SYSERR;
 241   }
 242   GNUNET_CRYPTO_hash (&block[1], len, key);
 243   return GNUNET_OK;
 244 }
 245
 246
 247 /**
 248  * Iterate over all edges of a block of a regex state.
 249  *
 250  * @param block Block to iterate over.
 251  * @param size Size of block.
 252  * @param iterator Function to call on each edge in the block.
 253  * @param iter_cls Closure for the iterator.
 254  *
 255  * @return GNUNET_SYSERR if an error has been encountered.
 256  *         GNUNET_OK if no error has been encountered.
 257  *           Note that if the iterator stops the iteration by returning
 258  *         GNUNET_NO, the block will no longer be checked for further errors.
 259  *           The return value will be GNUNET_OK meaning that no errors were
 260  *         found until the edge last notified to the iterator, but there might
 261  *         be errors in further edges.
 262  */
 263 int
 264 REGEX_BLOCK_iterate (const struct RegexBlock *block,
 265                      size_t size,
 266                      REGEX_INTERNAL_EgdeIterator iterator,
 267                      void *iter_cls)
 268 {
 269   struct RegexEdge *edge;
 270   unsigned int n;
 271   unsigned int n_token;
 272   unsigned int i;
 273   size_t offset;
 274   char *aux;
 275
 276   offset = sizeof (struct RegexBlock);
 277   if (offset >= size) /* Is it safe to access the regex block? */
 278   {
 279     GNUNET_break_op (0);
 280     return GNUNET_SYSERR;
 281   }
 282   n = ntohs (block->proof_len);
 283   offset += n;
 284   if (offset >= size) /* Is it safe to access the regex proof? */
 285   {
 286     GNUNET_break_op (0);
 287     return GNUNET_SYSERR;
 288   }
 289   aux = (char *) &block[1];  /* Skip regex block */
 290   aux = &aux[n];             /* Skip regex proof */
 291   n = ntohl (block->n_edges);
 292   LOG (GNUNET_ERROR_TYPE_DEBUG,
 293        "Start iterating block of size %u, proof %u, off %u edges %u\n",
 294        size, ntohs (block->proof_len), offset, n);
 295   /* aux always points at the end of the previous block */
 296   for (i = 0; i < n; i++)
 297   {
 298     offset += sizeof (struct RegexEdge);
 299     LOG (GNUNET_ERROR_TYPE_DEBUG, "*   Edge %u, off %u\n", i, offset);
 300     if (offset >= size) /* Is it safe to access the next edge block? */
 301     {
 302       LOG (GNUNET_ERROR_TYPE_WARNING,
 303            "*   Size not enough for RegexEdge, END\n");
 304       GNUNET_break_op (0);
 305       return GNUNET_SYSERR;
 306     }
 307     edge = (struct RegexEdge *) aux;
 308     n_token = ntohl (edge->n_token);
 309     offset += n_token;
 310     LOG (GNUNET_ERROR_TYPE_DEBUG,
 311          "*    Token length %u, off %u\n", n_token, offset);
 312     if (offset > size) /* Is it safe to access the edge token? */
 313     {
 314       LOG (GNUNET_ERROR_TYPE_WARNING,
 315            "*   Size not enough for edge token, END\n");
 316       GNUNET_break_op (0);
 317       return GNUNET_SYSERR;
 318     }
 319     aux = (char *) &edge[1]; /* Skip edge block */
 320     if (NULL != iterator)
 321         if (GNUNET_NO == iterator (iter_cls, aux, n_token, &edge->key))
 322             return GNUNET_OK;
 323     aux = &aux[n_token];     /* Skip edge token */
 324   }
 325   /* The total size should be exactly the size of (regex + all edges) blocks
 326    * If size == -1, block is from cache and therefore previously checked and
 327    * assumed correct. */
 328   if ( (offset != size) && (SIZE_MAX != size) )
 329   {
 330     GNUNET_break_op (0);
 331     return GNUNET_SYSERR;
 332   }
 333   return GNUNET_OK;
 334 }
 335
 336
 337 /**
 338  * Construct a regex block to be stored in the DHT.
 339  *
 340  * @param proof proof string for the block
 341  * @param num_edges number of edges in the block
 342  * @param edges the edges of the block
 343  * @param accepting is this an accepting state
 344  * @param rsize set to the size of the returned block (OUT-only)
 345  * @return the regex block, NULL on error
 346  */
 347 struct RegexBlock *
 348 REGEX_BLOCK_create (const char *proof,
 349                     unsigned int num_edges,
 350                     const struct REGEX_BLOCK_Edge *edges,
 351                     int accepting,
 352                     size_t *rsize)
 353 {
 354   struct RegexBlock *block;
 355   struct RegexEdge *block_edge;
 356   size_t size;
 357   size_t len;
 358   unsigned int i;
 359   unsigned int offset;
 360   char *aux;
 361
 362   len = strlen (proof);
 363   if (len > UINT16_MAX)
 364     {
 365       GNUNET_break (0);
 366       return NULL;
 367     }
 368   size = sizeof (struct RegexBlock) + len;
 369   block = GNUNET_malloc (size);
 370   block->proof_len = htons (len);
 371   block->n_edges = htonl (num_edges);
 372   block->is_accepting = htons (accepting);
 373
 374   /* Store the proof at the end of the block. */
 375   aux = (char *) &block[1];
 376   memcpy (aux, proof, len);
 377   aux = &aux[len];
 378
 379   /* Store each edge in a variable length MeshEdge struct at the
 380    * very end of the MeshRegexBlock structure.
 381    */
 382   for (i = 0; i < num_edges; i++)
 383   {
 384     /* aux points at the end of the last block */
 385     len = strlen (edges[i].label);
 386     size += sizeof (struct RegexEdge) + len;
 387     // Calculate offset FIXME is this ok? use size instead?
 388     offset = aux - (char *) block;
 389     block = GNUNET_realloc (block, size);
 390     aux = &((char *) block)[offset];
 391     block_edge = (struct RegexEdge *) aux;
 392     block_edge->key = edges[i].destination;
 393     block_edge->n_token = htonl (len);
 394     aux = (char *) &block_edge[1];
 395     memcpy (aux, edges[i].label, len);
 396     aux = &aux[len];
 397   }
 398   *rsize = size;
 399   return block;
 400 }
 401
 402
 403 /* end of regex_block_lib.c */