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 CheckEdgeContext
  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 CheckEdgeContext *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   struct CheckEdgeContext ctx;
 102   int res;
 103
 104   // FIXME: fails to check the proof!
 105   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 106               "Checking block with xquery `%s'\n",
 107               NULL != xquery ? xquery : "NULL");
 108   if ( (GNUNET_YES == ntohl (block->accepting)) &&
 109        ( (NULL == xquery) || ('\0' == xquery[0]) ) )
 110     return GNUNET_OK;
 111   ctx.xquery = xquery;
 112   ctx.found = GNUNET_NO;
 113   ctx.key = GNUNET_strdup (GNUNET_h2s (&block->key));
 114   res = REGEX_BLOCK_iterate (block, size, &check_edge, &ctx);
 115   GNUNET_free (ctx.key);
 116   if (GNUNET_SYSERR == res)
 117     return GNUNET_SYSERR;
 118   if (NULL == xquery)
 119     return GNUNET_YES;
 120   return ctx.found;
 121 }
 122
 123
 124 /**
 125  * Iterate over all edges of a block of a regex state.
 126  *
 127  * @param block Block to iterate over.
 128  * @param size Size of block.
 129  * @param iterator Function to call on each edge in the block.
 130  * @param iter_cls Closure for the iterator.
 131  *
 132  * @return GNUNET_SYSERR if an error has been encountered.
 133  *         GNUNET_OK if no error has been encountered.
 134  *           Note that if the iterator stops the iteration by returning
 135  *         GNUNET_NO, the block will no longer be checked for further errors.
 136  *           The return value will be GNUNET_OK meaning that no errors were
 137  *         found until the edge last notified to the iterator, but there might
 138  *         be errors in further edges.
 139  */
 140 int
 141 REGEX_BLOCK_iterate (const struct RegexBlock *block,
 142                             size_t size,
 143                             REGEX_INTERNAL_EgdeIterator iterator,
 144                             void *iter_cls)
 145 {
 146   struct RegexEdge *edge;
 147   unsigned int n;
 148   unsigned int n_token;
 149   unsigned int i;
 150   size_t offset;
 151   char *aux;
 152
 153   offset = sizeof (struct RegexBlock);
 154   if (offset >= size) /* Is it safe to access the regex block? */
 155   {
 156     GNUNET_break_op (0);
 157     return GNUNET_SYSERR;
 158   }
 159   n = ntohl (block->n_proof);
 160   offset += n;
 161   if (offset >= size) /* Is it safe to access the regex proof? */
 162   {
 163     GNUNET_break_op (0);
 164     return GNUNET_SYSERR;
 165   }
 166   aux = (char *) &block[1];  /* Skip regex block */
 167   aux = &aux[n];             /* Skip regex proof */
 168   n = ntohl (block->n_edges);
 169   LOG (GNUNET_ERROR_TYPE_DEBUG,
 170        "Start iterating block of size %u, proof %u, off %u edges %u\n",
 171        size, ntohl (block->n_proof), offset, n);
 172   /* aux always points at the end of the previous block */
 173   for (i = 0; i < n; i++)
 174   {
 175     offset += sizeof (struct RegexEdge);
 176     LOG (GNUNET_ERROR_TYPE_DEBUG, "*   Edge %u, off %u\n", i, offset);
 177     if (offset >= size) /* Is it safe to access the next edge block? */
 178     {
 179       LOG (GNUNET_ERROR_TYPE_WARNING,
 180            "*   Size not enough for RegexEdge, END\n");
 181       GNUNET_break_op (0);
 182       return GNUNET_SYSERR;
 183     }
 184     edge = (struct RegexEdge *) aux;
 185     n_token = ntohl (edge->n_token);
 186     offset += n_token;
 187     LOG (GNUNET_ERROR_TYPE_DEBUG,
 188          "*    Token length %u, off %u\n", n_token, offset);
 189     if (offset > size) /* Is it safe to access the edge token? */
 190     {
 191       LOG (GNUNET_ERROR_TYPE_WARNING,
 192            "*   Size not enough for edge token, END\n");
 193       GNUNET_break_op (0);
 194       return GNUNET_SYSERR;
 195     }
 196     aux = (char *) &edge[1]; /* Skip edge block */
 197     if (NULL != iterator)
 198         if (GNUNET_NO == iterator (iter_cls, aux, n_token, &edge->key))
 199             return GNUNET_OK;
 200     aux = &aux[n_token];     /* Skip edge token */
 201   }
 202   /* The total size should be exactly the size of (regex + all edges) blocks
 203    * If size == -1, block is from cache and therefore previously checked and
 204    * assumed correct. */
 205   if ( (offset != size) && (SIZE_MAX != size) )
 206   {
 207     GNUNET_break_op (0);
 208     return GNUNET_SYSERR;
 209   }
 210   return GNUNET_OK;
 211 }
 212
 213
 214 /**
 215  * Construct a regex block to be stored in the DHT.
 216  *
 217  * @param proof proof string for the block
 218  * @param num_edges number of edges in the block
 219  * @param edges the edges of the block
 220  * @return the regex block
 221  */
 222 struct RegexBlock *
 223 REGEX_BLOCK_create (const struct GNUNET_HashCode *key,
 224                              const char *proof,
 225                              unsigned int num_edges,
 226                              const struct REGEX_BLOCK_Edge *edges,
 227                              int accepting,
 228                              size_t *rsize)
 229 {
 230   struct RegexBlock *block;
 231   struct RegexEdge *block_edge;
 232   size_t size;
 233   size_t len;
 234   unsigned int i;
 235   unsigned int offset;
 236   char *aux;
 237
 238   len = strlen(proof);
 239   size = sizeof (struct RegexBlock) + len;
 240   block = GNUNET_malloc (size);
 241   block->key = *key;
 242   block->n_proof = htonl (len);
 243   block->n_edges = htonl (num_edges);
 244   block->accepting = htonl (accepting);
 245
 246   /* Store the proof at the end of the block. */
 247   aux = (char *) &block[1];
 248   memcpy (aux, proof, len);
 249   aux = &aux[len];
 250
 251   /* Store each edge in a variable length MeshEdge struct at the
 252    * very end of the MeshRegexBlock structure.
 253    */
 254   for (i = 0; i < num_edges; i++)
 255   {
 256     /* aux points at the end of the last block */
 257     len = strlen (edges[i].label);
 258     size += sizeof (struct RegexEdge) + len;
 259     // Calculate offset FIXME is this ok? use size instead?
 260     offset = aux - (char *) block;
 261     block = GNUNET_realloc (block, size);
 262     aux = &((char *) block)[offset];
 263     block_edge = (struct RegexEdge *) aux;
 264     block_edge->key = edges[i].destination;
 265     block_edge->n_token = htonl (len);
 266     aux = (char *) &block_edge[1];
 267     memcpy (aux, edges[i].label, len);
 268     aux = &aux[len];
 269   }
 270   *rsize = size;
 271   return block;
 272 }
 273
 274
 275 /* end of regex_block_lib.c */