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 int
  85 REGEX_BLOCK_check (const struct RegexBlock *block,
  86                             size_t size,
  87                             const char *xquery)
  88 {
  89   int res;
  90   struct regex_block_xquery_ctx ctx;
  91
  92   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
  93               "Checking block with xquery `%s'\n",
  94               NULL != xquery ? xquery : "NULL");
  95   if ( (GNUNET_YES == ntohl (block->accepting)) &&
  96        ( (NULL == xquery) || ('\0' == xquery[0]) ) )
  97     return GNUNET_OK;
  98   ctx.xquery = xquery;
  99   ctx.found = GNUNET_NO;
 100   ctx.key = GNUNET_strdup (GNUNET_h2s (&block->key));
 101   res = REGEX_BLOCK_iterate (block, size, &check_edge, &ctx);
 102   GNUNET_free (ctx.key);
 103   if (GNUNET_SYSERR == res)
 104     return GNUNET_SYSERR;
 105   if (NULL == xquery)
 106     return GNUNET_YES;
 107   return ctx.found;
 108 }
 109
 110
 111 int
 112 REGEX_BLOCK_iterate (const struct RegexBlock *block,
 113                             size_t size,
 114                             REGEX_INTERNAL_EgdeIterator iterator,
 115                             void *iter_cls)
 116 {
 117   struct RegexEdge *edge;
 118   unsigned int n;
 119   unsigned int n_token;
 120   unsigned int i;
 121   size_t offset;
 122   char *aux;
 123
 124   offset = sizeof (struct RegexBlock);
 125   if (offset >= size) /* Is it safe to access the regex block? */
 126   {
 127     GNUNET_break_op (0);
 128     return GNUNET_SYSERR;
 129   }
 130   n = ntohl (block->n_proof);
 131   offset += n;
 132   if (offset >= size) /* Is it safe to access the regex proof? */
 133   {
 134     GNUNET_break_op (0);
 135     return GNUNET_SYSERR;
 136   }
 137   aux = (char *) &block[1];  /* Skip regex block */
 138   aux = &aux[n];             /* Skip regex proof */
 139   n = ntohl (block->n_edges);
 140   LOG (GNUNET_ERROR_TYPE_DEBUG,
 141        "Start iterating block of size %u, proof %u, off %u edges %u\n",
 142        size, ntohl (block->n_proof), offset, n);
 143   /* aux always points at the end of the previous block */
 144   for (i = 0; i < n; i++)
 145   {
 146     offset += sizeof (struct RegexEdge);
 147     LOG (GNUNET_ERROR_TYPE_DEBUG, "*   Edge %u, off %u\n", i, offset);
 148     if (offset >= size) /* Is it safe to access the next edge block? */
 149     {
 150       LOG (GNUNET_ERROR_TYPE_WARNING,
 151            "*   Size not enough for RegexEdge, END\n");
 152       GNUNET_break_op (0);
 153       return GNUNET_SYSERR;
 154     }
 155     edge = (struct RegexEdge *) aux;
 156     n_token = ntohl (edge->n_token);
 157     offset += n_token;
 158     LOG (GNUNET_ERROR_TYPE_DEBUG,
 159          "*    Token length %u, off %u\n", n_token, offset);
 160     if (offset > size) /* Is it safe to access the edge token? */
 161     {
 162       LOG (GNUNET_ERROR_TYPE_WARNING,
 163            "*   Size not enough for edge token, END\n");
 164       GNUNET_break_op (0);
 165       return GNUNET_SYSERR;
 166     }
 167     aux = (char *) &edge[1]; /* Skip edge block */
 168     if (NULL != iterator)
 169         if (GNUNET_NO == iterator (iter_cls, aux, n_token, &edge->key))
 170             return GNUNET_OK;
 171     aux = &aux[n_token];     /* Skip edge token */
 172   }
 173   /* The total size should be exactly the size of (regex + all edges) blocks
 174    * If size == -1, block is from cache and therefore previously checked and
 175    * assumed correct. */
 176   if ( (offset != size) && (SIZE_MAX != size) )
 177   {
 178     GNUNET_break_op (0);
 179     return GNUNET_SYSERR;
 180   }
 181   return GNUNET_OK;
 182 }
 183
 184
 185 /**
 186  * Construct a regex block to be stored in the DHT.
 187  *
 188  * @param proof proof string for the block
 189  * @param num_edges number of edges in the block
 190  * @param edges the edges of the block
 191  * @return the regex block
 192  */
 193 struct RegexBlock *
 194 REGEX_BLOCK_create (const struct GNUNET_HashCode *key,
 195                              const char *proof,
 196                              unsigned int num_edges,
 197                              const struct REGEX_BLOCK_Edge *edges,
 198                              int accepting,
 199                              size_t *rsize)
 200 {
 201   struct RegexBlock *block;
 202   struct RegexEdge *block_edge;
 203   size_t size;
 204   size_t len;
 205   unsigned int i;
 206   unsigned int offset;
 207   char *aux;
 208
 209   len = strlen(proof);
 210   size = sizeof (struct RegexBlock) + len;
 211   block = GNUNET_malloc (size);
 212   block->key = *key;
 213   block->n_proof = htonl (len);
 214   block->n_edges = htonl (num_edges);
 215   block->accepting = htonl (accepting);
 216
 217   /* Store the proof at the end of the block. */
 218   aux = (char *) &block[1];
 219   memcpy (aux, proof, len);
 220   aux = &aux[len];
 221
 222   /* Store each edge in a variable length MeshEdge struct at the
 223    * very end of the MeshRegexBlock structure.
 224    */
 225   for (i = 0; i < num_edges; i++)
 226   {
 227     /* aux points at the end of the last block */
 228     len = strlen (edges[i].label);
 229     size += sizeof (struct RegexEdge) + len;
 230     // Calculate offset FIXME is this ok? use size instead?
 231     offset = aux - (char *) block;
 232     block = GNUNET_realloc (block, size);
 233     aux = &((char *) block)[offset];
 234     block_edge = (struct RegexEdge *) aux;
 235     block_edge->key = edges[i].destination;
 236     block_edge->n_token = htonl (len);
 237     aux = (char *) &block_edge[1];
 238     memcpy (aux, edges[i].label, len);
 239     aux = &aux[len];
 240   }
 241   *rsize = size;
 242   return block;
 243 }
 244
 245
 246 /* end of regex_block_lib.c */