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