regex_block_lib.c

Go to the documentation of this file.

/*
     This file is part of GNUnet.
     Copyright (C) 2012,2013 GNUnet e.V.
 
     GNUnet is free software: you can redistribute it and/or modify it
     under the terms of the GNU Affero General Public License as published
     by the Free Software Foundation, either version 3 of the License,
     or (at your option) any later version.
 
     GNUnet is distributed in the hope that it will be useful, but
     WITHOUT ANY WARRANTY; without even the implied warranty of
     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
     Affero General Public License for more details.
 
     You should have received a copy of the GNU Affero General Public License
     along with this program.  If not, see <http://www.gnu.org/licenses/>.
 
     SPDX-License-Identifier: AGPL3.0-or-later
 */
#include "platform.h"
#include "regex_block_lib.h"
#include "gnunet_constants.h"
 
#define LOG(kind, ...) GNUNET_log_from (kind, "regex-bck", __VA_ARGS__)
 
GNUNET_NETWORK_STRUCT_BEGIN
 
struct EdgeInfo
{
  uint16_t destination_index GNUNET_PACKED;
 
  uint16_t token_length GNUNET_PACKED;
};
 
 
struct RegexBlock
{
  uint16_t proof_len GNUNET_PACKED;
 
  int16_t is_accepting GNUNET_PACKED;
 
  uint16_t num_edges GNUNET_PACKED;
 
  uint16_t num_destinations GNUNET_PACKED;
 
  /* followed by 'struct GNUNET_HashCode[num_destinations]' */
 
  /* followed by 'struct EdgeInfo[edge_destination_indices]' */
 
  /* followed by 'char proof[n_proof]', NOT 0-terminated */
 
  /* followed by 'char tokens[num_edges][edge_info[k].token_length]';
     essentially all of the tokens one after the other in the
     order of the edges; tokens are NOT 0-terminated */
};
 
 
GNUNET_NETWORK_STRUCT_END
 
 
int
GNUNET_BLOCK_is_accepting (const struct RegexBlock *block,
                           size_t size)
{
  if (size < sizeof(struct RegexBlock))
  {
    GNUNET_break_op (0);
    return GNUNET_SYSERR;
  }
  return ntohs (block->is_accepting);
}
 
 
int
REGEX_BLOCK_check_proof (const char *proof,
                         size_t proof_len,
                         const struct GNUNET_HashCode *key)
{
  struct GNUNET_HashCode key_check;
 
  if ((NULL == proof) || (NULL == key))
  {
    GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Proof check failed, was NULL.\n");
    return GNUNET_NO;
  }
  GNUNET_CRYPTO_hash (proof, proof_len, &key_check);
  return (0 ==
          GNUNET_CRYPTO_hash_cmp (key, &key_check)) ? GNUNET_OK : GNUNET_NO;
}
 
 
struct CheckEdgeContext
{
  const char *xquery;
 
  int found;
};
 
 
static int
check_edge (void *cls,
            const char *token,
            size_t len,
            const struct GNUNET_HashCode *key)
{
  struct CheckEdgeContext *ctx = cls;
 
  GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
              "edge %.*s [%u]: %s\n",
              (int) len,
              token,
              (unsigned int) len,
              GNUNET_h2s (key));
  if (NULL == ctx->xquery)
    return GNUNET_YES;
  if (strlen (ctx->xquery) < len)
    return GNUNET_YES; /* too long */
  if (0 == strncmp (ctx->xquery, token, len))
    ctx->found = GNUNET_OK;
  return GNUNET_YES; /* keep checking for malformed data! */
}
 
 
int
REGEX_BLOCK_check (const struct RegexBlock *block,
                   size_t size,
                   const struct GNUNET_HashCode *query,
                   const char *xquery)
{
  struct GNUNET_HashCode key;
  struct CheckEdgeContext ctx;
  int res;
 
  LOG (GNUNET_ERROR_TYPE_DEBUG,
       "Block check\n");
  if (GNUNET_OK !=
      REGEX_BLOCK_get_key (block, size,
                           &key))
  {
    GNUNET_break_op (0);
    return GNUNET_SYSERR;
  }
  if ((NULL != query) &&
      (0 != GNUNET_memcmp (&key,
                           query)) )
  {
    GNUNET_break_op (0);
    return GNUNET_SYSERR;
  }
  if ((GNUNET_YES == ntohs (block->is_accepting)) &&
      ((NULL == xquery) || ('\0' == xquery[0])))
  {
    LOG (GNUNET_ERROR_TYPE_DEBUG,
         "  out! Is accepting: %u, xquery %p\n",
         ntohs (block->is_accepting),
         xquery);
    return GNUNET_OK;
  }
  ctx.xquery = xquery;
  ctx.found = GNUNET_NO;
  res = REGEX_BLOCK_iterate (block, size, &check_edge, &ctx);
  if (GNUNET_SYSERR == res)
    return GNUNET_SYSERR;
  if (NULL == xquery)
    return GNUNET_YES;
  LOG (GNUNET_ERROR_TYPE_DEBUG, "Result %d\n", ctx.found);
  return ctx.found;
}
 
 
int
REGEX_BLOCK_get_key (const struct RegexBlock *block,
                     size_t block_len,
                     struct GNUNET_HashCode *key)
{
  uint16_t len;
  const struct GNUNET_HashCode *destinations;
  const struct EdgeInfo *edges;
  uint16_t num_destinations;
  uint16_t num_edges;
  size_t total;
 
  if (block_len < sizeof(struct RegexBlock))
  {
    GNUNET_break_op (0);
    return GNUNET_SYSERR;
  }
  num_destinations = ntohs (block->num_destinations);
  num_edges = ntohs (block->num_edges);
  len = ntohs (block->proof_len);
  destinations = (const struct GNUNET_HashCode *) &block[1];
  edges = (const struct EdgeInfo *) &destinations[num_destinations];
  total = sizeof(struct RegexBlock) + num_destinations * sizeof(struct
                                                                GNUNET_HashCode)
          + num_edges * sizeof(struct EdgeInfo) + len;
  if (block_len < total)
  {
    GNUNET_break_op (0);
    return GNUNET_SYSERR;
  }
  GNUNET_CRYPTO_hash (&edges[num_edges], len, key);
  return GNUNET_OK;
}
 
 
int
REGEX_BLOCK_iterate (const struct RegexBlock *block,
                     size_t size,
                     REGEX_INTERNAL_EgdeIterator iterator,
                     void *iter_cls)
{
  uint16_t len;
  const struct GNUNET_HashCode *destinations;
  const struct EdgeInfo *edges;
  const char *aux;
  uint16_t num_destinations;
  uint16_t num_edges;
  size_t total;
  unsigned int n;
  size_t off;
 
  LOG (GNUNET_ERROR_TYPE_DEBUG, "Block iterate\n");
  if (size < sizeof(struct RegexBlock))
  {
    GNUNET_break_op (0);
    return GNUNET_SYSERR;
  }
  num_destinations = ntohs (block->num_destinations);
  num_edges = ntohs (block->num_edges);
  len = ntohs (block->proof_len);
  destinations = (const struct GNUNET_HashCode *) &block[1];
  edges = (const struct EdgeInfo *) &destinations[num_destinations];
  aux = (const char *) &edges[num_edges];
  total = sizeof(struct RegexBlock) + num_destinations * sizeof(struct
                                                                GNUNET_HashCode)
          + num_edges * sizeof(struct EdgeInfo) + len;
  if (size < total)
  {
    GNUNET_break_op (0);
    return GNUNET_SYSERR;
  }
  for (n = 0; n < num_edges; n++)
    total += ntohs (edges[n].token_length);
  if (size != total)
  {
    fprintf (stderr, "Expected %u, got %u\n",
             (unsigned int) size,
             (unsigned int) total);
    GNUNET_break_op (0);
    return GNUNET_SYSERR;
  }
  off = len;
  LOG (GNUNET_ERROR_TYPE_DEBUG,
       "Start iterating block of size %lu, proof %u, off %lu edges %u\n",
       (unsigned long) size, len, (unsigned long) off, n);
  /* &aux[off] always points to our token */
  for (n = 0; n < num_edges; n++)
  {
    LOG (GNUNET_ERROR_TYPE_DEBUG,
         "Edge %u/%u, off %lu tokenlen %u (%.*s)\n",
         n + 1, num_edges, (unsigned long) off,
         ntohs (edges[n].token_length), ntohs (edges[n].token_length),
         &aux[off]);
    if (NULL != iterator)
      if (GNUNET_NO == iterator (iter_cls,
                                 &aux[off],
                                 ntohs (edges[n].token_length),
                                 &destinations[ntohs (
                                                 edges[n].destination_index)]))
        return GNUNET_OK;
    off += ntohs (edges[n].token_length);
  }
  return GNUNET_OK;
}
 
 
struct RegexBlock *
REGEX_BLOCK_create (const char *proof,
                    unsigned int num_edges,
                    const struct REGEX_BLOCK_Edge *edges,
                    int accepting,
                    size_t *rsize)
{
  struct RegexBlock *block;
  struct GNUNET_HashCode destinations[1024]; /* 1024 = 64k/64 bytes/key == absolute MAX */
  uint16_t destination_indices[num_edges];
  struct GNUNET_HashCode *dests;
  struct EdgeInfo *edgeinfos;
  size_t off;
  size_t len;
  size_t total;
  size_t slen;
  unsigned int unique_destinations;
  unsigned int j;
  unsigned int i;
  char *aux;
 
  len = strlen (proof);
  if (len > UINT16_MAX)
  {
    GNUNET_break (0);
    return NULL;
  }
  unique_destinations = 0;
  total = sizeof(struct RegexBlock) + len;
  for (i = 0; i < num_edges; i++)
  {
    slen = strlen (edges[i].label);
    if (slen > UINT16_MAX)
    {
      GNUNET_break (0);
      return NULL;
    }
    total += slen;
    for (j = 0; j < unique_destinations; j++)
      if (0 == memcmp (&destinations[j],
                       &edges[i].destination,
                       sizeof(struct GNUNET_HashCode)))
        break;
    if (j >= 1024)
    {
      GNUNET_break (0);
      return NULL;
    }
    destination_indices[i] = j;
    if (j == unique_destinations)
      destinations[unique_destinations++] = edges[i].destination;
  }
  total += num_edges * sizeof(struct EdgeInfo) + unique_destinations
           * sizeof(struct GNUNET_HashCode);
  if (total >= GNUNET_CONSTANTS_MAX_BLOCK_SIZE)
  {
    GNUNET_break (0);
    return NULL;
  }
  block = GNUNET_malloc (total);
  block->proof_len = htons (len);
  block->is_accepting = htons (accepting);
  block->num_edges = htons (num_edges);
  block->num_destinations = htons (unique_destinations);
  dests = (struct GNUNET_HashCode *) &block[1];
  GNUNET_memcpy (dests, destinations, sizeof(struct GNUNET_HashCode)
                 * unique_destinations);
  edgeinfos = (struct EdgeInfo *) &dests[unique_destinations];
  aux = (char *) &edgeinfos[num_edges];
  off = len;
  GNUNET_memcpy (aux, proof, len);
  for (i = 0; i < num_edges; i++)
  {
    slen = strlen (edges[i].label);
    edgeinfos[i].token_length = htons ((uint16_t) slen);
    edgeinfos[i].destination_index = htons (destination_indices[i]);
    GNUNET_memcpy (&aux[off],
                   edges[i].label,
                   slen);
    off += slen;
  }
  *rsize = total;
  return block;
}
 
 
/* end of regex_block_lib.c */