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  */
  24 #include "platform.h"
  25 #include "regex_block_lib.h"
  26
  27
  28 /**
  29  * Struct to keep track of the xquery while iterating all the edges in a block.
  30  */
  31 struct regex_block_xquery_ctx
  32 {
  33   /**
  34    * Xquery: string we are looking for.
  35    */
  36   const char *xquery;
  37
  38   /**
  39    * Has any edge matched the xquery so far? (GNUNET_OK / GNUNET_NO)
  40    */
  41   int found;
  42 };
  43
  44
  45 /**
  46  * Iterator over all edges in a block, checking for a presence of a given query.
  47  *
  48  * @param cls Closure, (xquery context).
  49  * @param token Token that follows to next state.
  50  * @param len Lenght of token.
  51  * @param key Hash of next state.
  52  *
  53  * @return GNUNET_YES, to keep iterating
  54  */
  55 static int
  56 check_edge (void *cls,
  57             const char *token,
  58             size_t len,
  59             const struct GNUNET_HashCode *key)
  60 {
  61   struct regex_block_xquery_ctx *ctx = cls;
  62
  63   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "  edge %.*s [%u]\n",
  64               (int) len, token, len);
  65   if (strlen (ctx->xquery) < len)
  66   {
  67     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "  too long!\n");
  68     return GNUNET_YES;
  69   }
  70   if (0 == strncmp (ctx->xquery, token, len))
  71   {
  72     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "  OK!\n");
  73     ctx->found = GNUNET_OK;
  74   }
  75   else
  76   {
  77     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "  KO!\n");
  78   }
  79
  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  *
  91  * @return GNUNET_OK in case it's fine.
  92  *         GNUNET_NO in case the xquery is not found.
  93  *         GNUNET_SYSERR if the block is invalid.
  94  */
  95 int
  96 GNUNET_REGEX_block_check (const struct RegexBlock *block,
  97                                 size_t size,
  98                                 const char *xquery)
  99 {
 100   int res;
 101   struct regex_block_xquery_ctx ctx;
 102
 103     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 104                 "* Checking block with xquery \"%s\"\n",
 105                 xquery);
 106   if ( (GNUNET_YES == ntohl(block->accepting)) && ('\0' == xquery[0]) )
 107     return GNUNET_OK;
 108   ctx.xquery = xquery;
 109   ctx.found = GNUNET_NO;
 110   res = GNUNET_REGEX_block_iterate (block, size, &check_edge, &ctx);
 111   if (GNUNET_SYSERR == res)
 112     return GNUNET_SYSERR;
 113   return ctx.found;
 114 }
 115
 116
 117 /**
 118  * Iterate over all edges of a block of a regex state.
 119  *
 120  * @param block Block to iterate over.
 121  * @param size Size of block.
 122  * @param iterator Function to call on each edge in the block.
 123  * @param iter_cls Closure for the iterator.
 124  *
 125  * @return How many bytes of block have been processed
 126  */
 127 int
 128 GNUNET_REGEX_block_iterate (const struct RegexBlock *block,
 129                                   size_t size,
 130                                   GNUNET_REGEX_EgdeIterator iterator,
 131                                   void *iter_cls)
 132 {
 133   struct RegexEdge *edge;
 134   unsigned int n;
 135   unsigned int n_token;
 136   unsigned int i;
 137   size_t offset;
 138   char *aux;
 139
 140   offset = sizeof (struct RegexBlock);
 141   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 142               "* Start iterating block of size %u, off %u\n",
 143               size, offset);
 144   if (offset > size) // Is it safe to access the regex block?
 145   {
 146     GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
 147               "*   Block is smaller than struct RegexBlock, END\n");
 148     GNUNET_break_op (0);
 149     return GNUNET_SYSERR;
 150   }
 151   n = ntohl (block->n_proof);
 152   offset += n;
 153   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 154               "*  Proof length: %u, off %u\n", n, offset);
 155   if (offset > size) // Is it safe to access the regex proof?
 156   {
 157     GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
 158                 "*   Block is smaller than Block + proof, END\n");
 159     GNUNET_break_op (0);
 160     return GNUNET_SYSERR;
 161   }
 162   aux = (char *) &block[1];  // Skip regex block
 163   aux = &aux[n];             // Skip regex proof
 164   n = ntohl (block->n_edges);
 165   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "*  Edges: %u\n", n);
 166   for (i = 0; i < n; i++) // aux always points at the end of the previous block
 167   {
 168     offset += sizeof (struct RegexEdge);
 169     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "*   Edge %u, off %u\n", i, offset);
 170     if (offset > size) // Is it safe to access the next edge block?
 171     {
 172       GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
 173                   "*   Size not enough for RegexEdge, END\n");
 174       GNUNET_break_op (0);
 175       return GNUNET_SYSERR;
 176     }
 177     edge = (struct RegexEdge *) aux;
 178     n_token = ntohl (edge->n_token);
 179     offset += n_token;
 180     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 181                 "*    Token lenght %u, off %u\n", n_token, offset);
 182     if (offset > size) // Is it safe to access the edge token?
 183     {
 184       GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
 185                   "*   Size not enough for edge token, END\n");
 186       GNUNET_break_op (0);
 187       return GNUNET_SYSERR;
 188     }
 189     aux = (char *) &edge[1]; // Skip edge block
 190     if (NULL != iterator)
 191         if (GNUNET_NO == iterator (iter_cls, aux, n_token, &edge->key))
 192             return GNUNET_OK;
 193     aux = &aux[n_token];     // Skip edge token
 194   }
 195   // The total size should be exactly the size of (regex + all edges) blocks
 196   // If size == -1, block is from cache and therefore previously checked and
 197   // assumed correct.
 198   if (offset == size || SIZE_MAX == size)
 199   {
 200     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 201                   "* Block processed, END OK\n");
 202     return GNUNET_OK;
 203   }
 204   GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
 205               "*   Size %u (%d), read %u END KO\n", size, size, offset);
 206   GNUNET_break_op (0);
 207   return GNUNET_SYSERR;
 208 }
 209
 210 /* end of regex_block_lib.c */