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 #include "gnunet_constants.h"
  29
  30 #define LOG(kind,...) GNUNET_log_from (kind,"regex-bck",__VA_ARGS__)
  31
  32 GNUNET_NETWORK_STRUCT_BEGIN
  33
  34 /**
  35  * Information for each edge.
  36  */
  37 struct EdgeInfo
  38 {
  39   /**
  40    * Index of the destination of this edge in the
  41    * unique destinations array.
  42    */
  43   uint16_t destination_index GNUNET_PACKED;
  44
  45   /**
  46    * Number of bytes the token for this edge takes in the
  47    * token area.
  48    */
  49   uint16_t token_length GNUNET_PACKED;
  50 };
  51
  52
  53 /**
  54  * @brief Block to announce a regex state.
  55  */
  56 struct RegexBlock
  57 {
  58
  59   /**
  60    * Length of the proof regex string.
  61    */
  62   uint16_t proof_len GNUNET_PACKED;
  63
  64   /**
  65    * Is this state an accepting state?
  66    */
  67   int16_t is_accepting GNUNET_PACKED;
  68
  69   /**
  70    * Number of edges parting from this state.
  71    */
  72   uint16_t num_edges GNUNET_PACKED;
  73
  74   /**
  75    * Nubmer of unique destinations reachable from this state.
  76    */
  77   uint16_t num_destinations GNUNET_PACKED;
  78
  79   /* followed by 'struct GNUNET_HashCode[num_destinations]' */
  80
  81   /* followed by 'struct EdgeInfo[edge_destination_indices]' */
  82
  83   /* followed by 'char proof[n_proof]', NOT 0-terminated */
  84
  85   /* followed by 'char tokens[num_edges][edge_info[k].token_length]';
  86      essentially all of the tokens one after the other in the
  87      order of the edges; tokens are NOT 0-terminated */
  88
  89 };
  90
  91
  92 GNUNET_NETWORK_STRUCT_END
  93
  94
  95 /**
  96  * Test if this block is marked as being an accept state.
  97  *
  98  * @param block block to test
  99  * @return GNUNET_YES if the block is accepting, GNUNET_NO if not
 100  */
 101 int
 102 GNUNET_BLOCK_is_accepting (const struct RegexBlock *block)
 103 {
 104   return ntohs (block->is_accepting);
 105 }
 106
 107
 108 /**
 109  * Check if the given 'proof' matches the given 'key'.
 110  *
 111  * @param proof partial regex of a state
 112  * @param proof_len number of bytes in 'proof'
 113  * @param key hash of a state.
 114  *
 115  * @return GNUNET_OK if the proof is valid for the given key.
 116  */
 117 int
 118 REGEX_BLOCK_check_proof (const char *proof,
 119                          size_t proof_len,
 120                          const struct GNUNET_HashCode *key)
 121 {
 122   struct GNUNET_HashCode key_check;
 123
 124   if ( (NULL == proof) || (NULL == key))
 125   {
 126     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Proof check failed, was NULL.\n");
 127     return GNUNET_NO;
 128   }
 129   GNUNET_CRYPTO_hash (proof, proof_len, &key_check);
 130   return (0 ==
 131           GNUNET_CRYPTO_hash_cmp (key, &key_check)) ? GNUNET_OK : GNUNET_NO;
 132 }
 133
 134
 135 /**
 136  * Struct to keep track of the xquery while iterating all the edges in a block.
 137  */
 138 struct CheckEdgeContext
 139 {
 140   /**
 141    * Xquery: string we are looking for.
 142    */
 143   const char *xquery;
 144
 145   /**
 146    * Has any edge matched the xquery so far? (GNUNET_OK / GNUNET_NO)
 147    */
 148   int found;
 149
 150 };
 151
 152
 153 /**
 154  * Iterator over all edges in a block, checking for a presence of a given query.
 155  *
 156  * @param cls Closure, (xquery context).
 157  * @param token Token that follows to next state.
 158  * @param len Lenght of token.
 159  * @param key Hash of next state.
 160  *
 161  * @return GNUNET_YES, to keep iterating
 162  */
 163 static int
 164 check_edge (void *cls,
 165             const char *token,
 166             size_t len,
 167             const struct GNUNET_HashCode *key)
 168 {
 169   struct CheckEdgeContext *ctx = cls;
 170
 171   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 172               "edge %.*s [%u]: %s->%s\n",
 173               (int) len, token, len, GNUNET_h2s(key));
 174   if (NULL == ctx->xquery)
 175     return GNUNET_YES;
 176   if (strlen (ctx->xquery) < len)
 177     return GNUNET_YES; /* too long */
 178   if (0 == strncmp (ctx->xquery, token, len))
 179     ctx->found = GNUNET_OK;
 180   return GNUNET_YES; /* keep checking for malformed data! */
 181 }
 182
 183
 184 /**
 185  * Check if the regex block is well formed, including all edges.
 186  *
 187  * @param block The start of the block.
 188  * @param size The size of the block.
 189  * @param query the query for the block
 190  * @param xquery String describing the edge we are looking for.
 191  *               Can be NULL in case this is a put block.
 192  *
 193  * @return GNUNET_OK in case it's fine.
 194  *         GNUNET_NO in case the xquery exists and is not found (IRRELEVANT).
 195  *         GNUNET_SYSERR if the block is invalid.
 196  */
 197 int
 198 REGEX_BLOCK_check (const struct RegexBlock *block,
 199                    size_t size,
 200                    const struct GNUNET_HashCode *query,
 201                    const char *xquery)
 202 {
 203   struct GNUNET_HashCode key;
 204   struct CheckEdgeContext ctx;
 205   int res;
 206
 207   if (GNUNET_OK !=
 208       REGEX_BLOCK_get_key (block, size,
 209                            &key))
 210   {
 211     GNUNET_break_op (0);
 212     return GNUNET_SYSERR;
 213   }
 214   if (0 != memcmp (&key,
 215                    query,
 216                    sizeof (struct GNUNET_HashCode)))
 217   {
 218     GNUNET_break_op (0);
 219     return GNUNET_SYSERR;
 220   }
 221   if ( (GNUNET_YES == ntohs (block->is_accepting)) &&
 222        ( (NULL == xquery) || ('\0' == xquery[0]) ) )
 223     return GNUNET_OK;
 224   ctx.xquery = xquery;
 225   ctx.found = GNUNET_NO;
 226   res = REGEX_BLOCK_iterate (block, size, &check_edge, &ctx);
 227   if (GNUNET_SYSERR == res)
 228     return GNUNET_SYSERR;
 229   if (NULL == xquery)
 230     return GNUNET_YES;
 231   return ctx.found;
 232 }
 233
 234
 235 /**
 236  * Obtain the key that a particular block is to be stored under.
 237  *
 238  * @param block block to get the key from
 239  * @param block_len number of bytes in block
 240  * @param query where to store the key
 241  * @return GNUNET_OK on success, GNUNET_SYSERR if the block is malformed
 242  */
 243 int
 244 REGEX_BLOCK_get_key (const struct RegexBlock *block,
 245                      size_t block_len,
 246                      struct GNUNET_HashCode *key)
 247 {
 248   uint16_t len;
 249   const struct GNUNET_HashCode *destinations;
 250   const struct EdgeInfo *edges;
 251   uint16_t num_destinations;
 252   uint16_t num_edges;
 253   size_t total;
 254
 255   if (block_len < sizeof (struct RegexBlock))
 256   {
 257     GNUNET_break_op (0);
 258     return GNUNET_SYSERR;
 259   }
 260   num_destinations = ntohs (block->num_destinations);
 261   num_edges = ntohs (block->num_edges);
 262   len = ntohs (block->proof_len);
 263   destinations = (const struct GNUNET_HashCode *) &block[1];
 264   edges = (const struct EdgeInfo *) &destinations[num_destinations];
 265   total = sizeof (struct RegexBlock) + num_destinations * sizeof (struct GNUNET_HashCode) + num_edges + sizeof (struct EdgeInfo) + len;
 266   if (block_len < total)
 267   {
 268     GNUNET_break_op (0);
 269     return GNUNET_SYSERR;
 270   }
 271   GNUNET_CRYPTO_hash (&edges[num_edges], len, key);
 272   return GNUNET_OK;
 273 }
 274
 275
 276 /**
 277  * Iterate over all edges of a block of a regex state.
 278  *
 279  * @param block Block to iterate over.
 280  * @param size Size of block.
 281  * @param iterator Function to call on each edge in the block.
 282  * @param iter_cls Closure for the iterator.
 283  *
 284  * @return GNUNET_SYSERR if an error has been encountered.
 285  *         GNUNET_OK if no error has been encountered.
 286  *           Note that if the iterator stops the iteration by returning
 287  *         GNUNET_NO, the block will no longer be checked for further errors.
 288  *           The return value will be GNUNET_OK meaning that no errors were
 289  *         found until the edge last notified to the iterator, but there might
 290  *         be errors in further edges.
 291  */
 292 int
 293 REGEX_BLOCK_iterate (const struct RegexBlock *block,
 294                      size_t size,
 295                      REGEX_INTERNAL_EgdeIterator iterator,
 296                      void *iter_cls)
 297 {
 298   uint16_t len;
 299   const struct GNUNET_HashCode *destinations;
 300   const struct EdgeInfo *edges;
 301   const char *aux;
 302   uint16_t num_destinations;
 303   uint16_t num_edges;
 304   size_t total;
 305   unsigned int n;
 306   size_t off;
 307
 308   if (size < sizeof (struct RegexBlock))
 309   {
 310     GNUNET_break_op (0);
 311     return GNUNET_SYSERR;
 312   }
 313   num_destinations = ntohs (block->num_destinations);
 314   num_edges = ntohs (block->num_edges);
 315   len = ntohs (block->proof_len);
 316   destinations = (const struct GNUNET_HashCode *) &block[1];
 317   edges = (const struct EdgeInfo *) &destinations[num_destinations];
 318   aux = (const char *) &edges[num_edges];
 319   total = sizeof (struct RegexBlock) + num_destinations * sizeof (struct GNUNET_HashCode) + num_edges + sizeof (struct EdgeInfo) + len;
 320   if (size < total)
 321   {
 322     GNUNET_break_op (0);
 323     return GNUNET_SYSERR;
 324   }
 325   for (n=0;n<num_edges;n++)
 326     total += ntohs (edges[n].token_length);
 327   if (size != total)
 328   {
 329     GNUNET_break_op (0);
 330     return GNUNET_SYSERR;
 331   }
 332   off = len;
 333   LOG (GNUNET_ERROR_TYPE_DEBUG,
 334        "Start iterating block of size %u, proof %u, off %u edges %u\n",
 335        size, len, off, n);
 336   /* &aux[off] always points to our token */
 337   for (n=0;n<num_edges;n++)
 338   {
 339     LOG (GNUNET_ERROR_TYPE_DEBUG,
 340          "Edge %u, off %u tokenlen %u\n", n, off,
 341          ntohs (edges[n].token_length));
 342     if (NULL != iterator)
 343       if (GNUNET_NO == iterator (iter_cls,
 344                                  &aux[off],
 345                                  ntohs (edges[n].token_length),
 346                                  &destinations[ntohs (edges[n].destination_index)]))
 347         return GNUNET_OK;
 348     off += ntohs (edges[n].token_length);
 349   }
 350   return GNUNET_OK;
 351 }
 352
 353
 354 /**
 355  * Construct a regex block to be stored in the DHT.
 356  *
 357  * @param proof proof string for the block
 358  * @param num_edges number of edges in the block
 359  * @param edges the edges of the block
 360  * @param accepting is this an accepting state
 361  * @param rsize set to the size of the returned block (OUT-only)
 362  * @return the regex block, NULL on error
 363  */
 364 struct RegexBlock *
 365 REGEX_BLOCK_create (const char *proof,
 366                     unsigned int num_edges,
 367                     const struct REGEX_BLOCK_Edge *edges,
 368                     int accepting,
 369                     size_t *rsize)
 370 {
 371   struct RegexBlock *block;
 372   struct GNUNET_HashCode destinations[1024]; /* 1024 = 64k/64 bytes/key == absolute MAX */
 373   uint16_t destination_indices[num_edges];
 374   struct GNUNET_HashCode *dests;
 375   struct EdgeInfo *edgeinfos;
 376   size_t off;
 377   size_t len;
 378   size_t total;
 379   size_t slen;
 380   unsigned int unique_destinations;
 381   unsigned int j;
 382   unsigned int i;
 383   char *aux;
 384
 385   len = strlen (proof);
 386   if (len > UINT16_MAX)
 387   {
 388     GNUNET_break (0);
 389     return NULL;
 390   }
 391   unique_destinations = 0;
 392   total = sizeof (struct RegexBlock) + len;
 393   for (i=0;i<num_edges;i++)
 394   {
 395     slen = strlen (edges[i].label);
 396     if (len > UINT16_MAX)
 397     {
 398       GNUNET_break (0);
 399       return NULL;
 400     }
 401     total += slen;
 402     for (j=0;j<unique_destinations;j++)
 403       if (0 == memcmp (&destinations[j],
 404                        &edges[i].destination,
 405                        sizeof (struct GNUNET_HashCode)))
 406         break;
 407     if (j >= 1024)
 408     {
 409       GNUNET_break (0);
 410       return NULL;
 411     }
 412     destination_indices[i] = j;
 413     if (j == unique_destinations)
 414       destinations[unique_destinations++] = edges[i].destination;
 415   }
 416   total += num_edges * sizeof (struct EdgeInfo) + unique_destinations * sizeof (struct GNUNET_HashCode);
 417   if (total >= GNUNET_CONSTANTS_MAX_BLOCK_SIZE)
 418   {
 419     GNUNET_break (0);
 420     return NULL;
 421   }
 422   block = GNUNET_malloc (total);
 423   block->proof_len = htons (len);
 424   block->is_accepting = htons (accepting);
 425   block->num_edges = htons (num_edges);
 426   block->num_destinations = htons (unique_destinations);
 427   dests = (struct GNUNET_HashCode *) &block[1];
 428   memcpy (dests, destinations, sizeof (struct GNUNET_HashCode) * unique_destinations);
 429   edgeinfos = (struct EdgeInfo *) &dests[unique_destinations];
 430   aux = (char *) &edgeinfos[num_edges];
 431   off = len;
 432   memcpy (aux, proof, len);
 433   for (i=0;i<num_edges;i++)
 434   {
 435     slen = strlen (edges[i].label);
 436     edgeinfos[i].token_length = htons ((uint16_t) slen);
 437     edgeinfos[i].destination_index = htons (destination_indices[i]);
 438     memcpy (&aux[off],
 439             edges[i].label,
 440             slen);
 441     off += slen;
 442   }
 443   *rsize = total;
 444   return block;
 445 }
 446
 447
 448 /* end of regex_block_lib.c */