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