src/regex/regex_block_lib.c

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