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