regex_internal_dht.c

Go to the documentation of this file.

/*
     This file is part of GNUnet
     Copyright (C) 2012, 2015 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_internal_lib.h"
#include "regex_block_lib.h"
#include "gnunet_dht_service.h"
#include "gnunet_statistics_service.h"
#include "gnunet_constants.h"
#include "gnunet_signatures.h"


#define LOG(kind, ...) GNUNET_log_from (kind, "regex-dht", __VA_ARGS__)

#define DHT_REPLICATION 5

#define DHT_TTL         GNUNET_TIME_UNIT_HOURS

#define DHT_OPT         GNUNET_DHT_RO_DEMULTIPLEX_EVERYWHERE


struct REGEX_INTERNAL_Announcement
{
  struct GNUNET_DHT_Handle *dht;

  const char *regex;

  struct REGEX_INTERNAL_Automaton *dfa;

  const struct GNUNET_CRYPTO_EddsaPrivateKey *priv;

  struct GNUNET_STATISTICS_Handle *stats;
};


static void
regex_iterator (void *cls,
                const struct GNUNET_HashCode *key,
                const char *proof,
                int accepting,
                unsigned int num_edges,
                const struct REGEX_BLOCK_Edge *edges)
{
  struct REGEX_INTERNAL_Announcement *h = cls;
  struct RegexBlock *block;
  size_t size;
  unsigned int i;

  LOG (GNUNET_ERROR_TYPE_INFO,
       "DHT PUT for state %s with proof `%s' and %u edges:\n",
       GNUNET_h2s (key),
       proof,
       num_edges);
  for (i = 0; i < num_edges; i++)
  {
    LOG (GNUNET_ERROR_TYPE_INFO,
         "Edge %u `%s' towards %s\n",
         i,
         edges[i].label,
         GNUNET_h2s (&edges[i].destination));
  }
  if (GNUNET_YES == accepting)
  {
    struct RegexAcceptBlock ab;

    LOG (GNUNET_ERROR_TYPE_INFO,
         "State %s is accepting, putting own id\n",
         GNUNET_h2s (key));
    size = sizeof(struct RegexAcceptBlock);
    ab.purpose.size = ntohl (sizeof(struct GNUNET_CRYPTO_EccSignaturePurpose)
                             + sizeof(struct GNUNET_TIME_AbsoluteNBO)
                             + sizeof(struct GNUNET_HashCode));
    ab.purpose.purpose = ntohl (GNUNET_SIGNATURE_PURPOSE_REGEX_ACCEPT);
    ab.expiration_time = GNUNET_TIME_absolute_hton (
      GNUNET_TIME_relative_to_absolute (GNUNET_CONSTANTS_DHT_MAX_EXPIRATION));
    ab.key = *key;
    GNUNET_CRYPTO_eddsa_key_get_public (h->priv,
                                        &ab.peer.public_key);
    GNUNET_assert (GNUNET_OK ==
                   GNUNET_CRYPTO_eddsa_sign_ (h->priv,
                                              &ab.purpose,
                                              &ab.signature));

    GNUNET_STATISTICS_update (h->stats, "# regex accepting blocks stored",
                              1, GNUNET_NO);
    GNUNET_STATISTICS_update (h->stats, "# regex accepting block bytes stored",
                              sizeof(struct RegexAcceptBlock), GNUNET_NO);
    (void)
    GNUNET_DHT_put (h->dht, key,
                    DHT_REPLICATION,
                    DHT_OPT | GNUNET_DHT_RO_RECORD_ROUTE,
                    GNUNET_BLOCK_TYPE_REGEX_ACCEPT,
                    size,
                    &ab,
                    GNUNET_TIME_relative_to_absolute (DHT_TTL),
                    NULL, NULL);
  }
  block = REGEX_BLOCK_create (proof,
                              num_edges,
                              edges,
                              accepting,
                              &size);
  if (NULL == block)
    return;
  (void) GNUNET_DHT_put (h->dht,
                         key,
                         DHT_REPLICATION,
                         DHT_OPT,
                         GNUNET_BLOCK_TYPE_REGEX,
                         size,
                         block,
                         GNUNET_TIME_relative_to_absolute (DHT_TTL),
                         NULL,
                         NULL);
  GNUNET_STATISTICS_update (h->stats,
                            "# regex blocks stored",
                            1,
                            GNUNET_NO);
  GNUNET_STATISTICS_update (h->stats,
                            "# regex block bytes stored",
                            size,
                            GNUNET_NO);
  GNUNET_free (block);
}


struct REGEX_INTERNAL_Announcement *
REGEX_INTERNAL_announce (struct GNUNET_DHT_Handle *dht,
                         const struct GNUNET_CRYPTO_EddsaPrivateKey *priv,
                         const char *regex,
                         uint16_t compression,
                         struct GNUNET_STATISTICS_Handle *stats)
{
  struct REGEX_INTERNAL_Announcement *h;

  GNUNET_assert (NULL != dht);
  h = GNUNET_new (struct REGEX_INTERNAL_Announcement);
  h->regex = regex;
  h->dht = dht;
  h->stats = stats;
  h->priv = priv;
  h->dfa = REGEX_INTERNAL_construct_dfa (regex, strlen (regex), compression);
  REGEX_INTERNAL_reannounce (h);
  return h;
}


void
REGEX_INTERNAL_reannounce (struct REGEX_INTERNAL_Announcement *h)
{
  GNUNET_assert (NULL != h->dfa);  /* make sure to call announce first */
  LOG (GNUNET_ERROR_TYPE_INFO,
       "REGEX_INTERNAL_reannounce: %s\n",
       h->regex);
  REGEX_INTERNAL_iterate_reachable_edges (h->dfa,
                                          &regex_iterator,
                                          h);
}


void
REGEX_INTERNAL_announce_cancel (struct REGEX_INTERNAL_Announcement *h)
{
  REGEX_INTERNAL_automaton_destroy (h->dfa);
  GNUNET_free (h);
}


/******************************************************************************/


struct RegexSearchContext
{
  size_t position;

  struct REGEX_INTERNAL_Search *info;

  unsigned int longest_match;

  struct GNUNET_HashCode hash;
};


struct Result
{
  size_t size;

  const void *data;
};


struct REGEX_INTERNAL_Search
{
  struct GNUNET_DHT_Handle *dht;

  struct GNUNET_STATISTICS_Handle *stats;

  char *description;

  struct GNUNET_CONTAINER_MultiHashMap *dht_get_handles;

  struct GNUNET_CONTAINER_MultiHashMap *dht_get_results;

  struct RegexSearchContext **contexts;

  unsigned int n_contexts;

  REGEX_INTERNAL_Found callback;

  void *callback_cls;
};


static void
regex_next_edge (const struct RegexBlock *block,
                 size_t size,
                 struct RegexSearchContext *ctx);


static void
dht_get_string_accept_handler (void *cls, struct GNUNET_TIME_Absolute exp,
                               const struct GNUNET_HashCode *key,
                               const struct GNUNET_PeerIdentity *get_path,
                               unsigned int get_path_length,
                               const struct GNUNET_PeerIdentity *put_path,
                               unsigned int put_path_length,
                               enum GNUNET_BLOCK_Type type,
                               size_t size, const void *data)
{
  const struct RegexAcceptBlock *block = data;
  struct RegexSearchContext *ctx = cls;
  struct REGEX_INTERNAL_Search *info = ctx->info;

  LOG (GNUNET_ERROR_TYPE_DEBUG,
       "Regex result accept for %s (key %s)\n",
       info->description, GNUNET_h2s (key));

  GNUNET_STATISTICS_update (info->stats,
                            "# regex accepting blocks found",
                            1, GNUNET_NO);
  GNUNET_STATISTICS_update (info->stats,
                            "# regex accepting block bytes found",
                            size, GNUNET_NO);
  info->callback (info->callback_cls,
                  &block->peer,
                  get_path, get_path_length,
                  put_path, put_path_length);
}


static void
regex_find_path (const struct GNUNET_HashCode *key,
                 struct RegexSearchContext *ctx)
{
  struct GNUNET_DHT_GetHandle *get_h;

  LOG (GNUNET_ERROR_TYPE_DEBUG,
       "Accept state found, now searching for paths to %s\n",
       GNUNET_h2s (key));
  get_h = GNUNET_DHT_get_start (ctx->info->dht,     /* handle */
                                GNUNET_BLOCK_TYPE_REGEX_ACCEPT, /* type */
                                key,     /* key to search */
                                DHT_REPLICATION, /* replication level */
                                DHT_OPT | GNUNET_DHT_RO_RECORD_ROUTE,
                                NULL, /* xquery */       // FIXME BLOOMFILTER
                                0, /* xquery bits */     // FIXME BLOOMFILTER SIZE
                                &dht_get_string_accept_handler, ctx);
  GNUNET_break (GNUNET_OK ==
                GNUNET_CONTAINER_multihashmap_put (ctx->info->dht_get_handles,
                                                   key,
                                                   get_h,
                                                   GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE));
}


static void
dht_get_string_handler (void *cls, struct GNUNET_TIME_Absolute exp,
                        const struct GNUNET_HashCode *key,
                        const struct GNUNET_PeerIdentity *get_path,
                        unsigned int get_path_length,
                        const struct GNUNET_PeerIdentity *put_path,
                        unsigned int put_path_length,
                        enum GNUNET_BLOCK_Type type,
                        size_t size, const void *data)
{
  const struct RegexBlock *block = data;
  struct RegexSearchContext *ctx = cls;
  struct REGEX_INTERNAL_Search *info = ctx->info;
  size_t len;
  struct Result *copy;

  LOG (GNUNET_ERROR_TYPE_INFO,
       "DHT GET result for %s (%s)\n",
       GNUNET_h2s (key), ctx->info->description);
  copy = GNUNET_malloc (sizeof(struct Result) + size);
  copy->size = size;
  copy->data = &copy[1];
  GNUNET_memcpy (&copy[1], block, size);
  GNUNET_break (GNUNET_OK ==
                GNUNET_CONTAINER_multihashmap_put (info->dht_get_results,
                                                   key, copy,
                                                   GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE));
  len = strlen (info->description);
  if (len == ctx->position) // String processed
  {
    if (GNUNET_YES == GNUNET_BLOCK_is_accepting (block, size))
    {
      regex_find_path (key, ctx);
    }
    else
    {
      LOG (GNUNET_ERROR_TYPE_INFO, "block not accepting!\n");
      /* FIXME REGEX this block not successful, wait for more? start timeout? */
    }
    return;
  }
  regex_next_edge (block, size, ctx);
}


static int
regex_result_iterator (void *cls,
                       const struct GNUNET_HashCode *key,
                       void *value)
{
  struct Result *result = value;
  const struct RegexBlock *block = result->data;
  struct RegexSearchContext *ctx = cls;

  if ((GNUNET_YES ==
       GNUNET_BLOCK_is_accepting (block, result->size)) &&
      (ctx->position == strlen (ctx->info->description)))
  {
    LOG (GNUNET_ERROR_TYPE_INFO,
         "Found accepting known block\n");
    regex_find_path (key, ctx);
    return GNUNET_YES;   // We found an accept state!
  }
  LOG (GNUNET_ERROR_TYPE_DEBUG,
       "* %lu, %lu, [%u]\n",
       (unsigned long) ctx->position,
       strlen (ctx->info->description),
       GNUNET_BLOCK_is_accepting (block, result->size));
  regex_next_edge (block, result->size, ctx);

  GNUNET_STATISTICS_update (ctx->info->stats, "# regex cadet blocks iterated",
                            1, GNUNET_NO);

  return GNUNET_YES;
}


static int
regex_edge_iterator (void *cls,
                     const char *token,
                     size_t len,
                     const struct GNUNET_HashCode *key)
{
  struct RegexSearchContext *ctx = cls;
  struct REGEX_INTERNAL_Search *info = ctx->info;
  const char *current;
  size_t current_len;

  GNUNET_STATISTICS_update (info->stats, "# regex edges iterated",
                            1, GNUNET_NO);
  current = &info->description[ctx->position];
  current_len = strlen (info->description) - ctx->position;
  if (len > current_len)
  {
    LOG (GNUNET_ERROR_TYPE_DEBUG, "Token too long, END\n");
    return GNUNET_YES;
  }
  if (0 != strncmp (current, token, len))
  {
    LOG (GNUNET_ERROR_TYPE_DEBUG, "Token doesn't match, END\n");
    return GNUNET_YES;
  }

  if (len > ctx->longest_match)
  {
    LOG (GNUNET_ERROR_TYPE_DEBUG, "Token is longer, KEEP\n");
    ctx->longest_match = len;
    ctx->hash = *key;
  }
  else
  {
    LOG (GNUNET_ERROR_TYPE_DEBUG, "Token is not longer, IGNORE\n");
  }

  LOG (GNUNET_ERROR_TYPE_DEBUG, "*    End of regex edge iterator\n");
  return GNUNET_YES;
}


static void
regex_next_edge (const struct RegexBlock *block,
                 size_t size,
                 struct RegexSearchContext *ctx)
{
  struct RegexSearchContext *new_ctx;
  struct REGEX_INTERNAL_Search *info = ctx->info;
  struct GNUNET_DHT_GetHandle *get_h;
  struct GNUNET_HashCode *hash;
  const char *rest;
  int result;

  LOG (GNUNET_ERROR_TYPE_DEBUG, "Next edge\n");
  /* Find the longest match for the current string position,
   * among tokens in the given block */
  ctx->longest_match = 0;
  result = REGEX_BLOCK_iterate (block, size,
                                &regex_edge_iterator, ctx);
  GNUNET_break (GNUNET_OK == result);

  /* Did anything match? */
  if (0 == ctx->longest_match)
  {
    LOG (GNUNET_ERROR_TYPE_DEBUG,
         "no match in block\n");
    return;
  }

  hash = &ctx->hash;
  new_ctx = GNUNET_new (struct RegexSearchContext);
  new_ctx->info = info;
  new_ctx->position = ctx->position + ctx->longest_match;
  GNUNET_array_append (info->contexts, info->n_contexts, new_ctx);

  /* Check whether we already have a DHT GET running for it */
  if (GNUNET_YES ==
      GNUNET_CONTAINER_multihashmap_contains (info->dht_get_handles, hash))
  {
    LOG (GNUNET_ERROR_TYPE_DEBUG,
         "GET for %s running, END\n",
         GNUNET_h2s (hash));
    GNUNET_CONTAINER_multihashmap_get_multiple (info->dht_get_results,
                                                hash,
                                                &regex_result_iterator,
                                                new_ctx);
    return;   /* We are already looking for it */
  }

  GNUNET_STATISTICS_update (info->stats, "# regex nodes traversed",
                            1, GNUNET_NO);

  LOG (GNUNET_ERROR_TYPE_DEBUG,
       "Following edges at %s for offset %u in `%s'\n",
       GNUNET_h2s (hash),
       (unsigned int) ctx->position,
       info->description);
  rest = &new_ctx->info->description[new_ctx->position];
  get_h =
    GNUNET_DHT_get_start (info->dht,       /* handle */
                          GNUNET_BLOCK_TYPE_REGEX,   /* type */
                          hash,       /* key to search */
                          DHT_REPLICATION,   /* replication level */
                          DHT_OPT,
                          rest,   /* xquery */
                          strlen (rest) + 1,       /* xquery bits */
                          &dht_get_string_handler, new_ctx);
  if (GNUNET_OK !=
      GNUNET_CONTAINER_multihashmap_put (info->dht_get_handles,
                                         hash,
                                         get_h,
                                         GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST))
  {
    GNUNET_break (0);
    return;
  }
}


struct REGEX_INTERNAL_Search *
REGEX_INTERNAL_search (struct GNUNET_DHT_Handle *dht,
                       const char *string,
                       REGEX_INTERNAL_Found callback,
                       void *callback_cls,
                       struct GNUNET_STATISTICS_Handle *stats)
{
  struct REGEX_INTERNAL_Search *h;
  struct GNUNET_DHT_GetHandle *get_h;
  struct RegexSearchContext *ctx;
  struct GNUNET_HashCode key;
  size_t size;
  size_t len;

  /* Initialize handle */
  GNUNET_assert (NULL != dht);
  GNUNET_assert (NULL != callback);
  h = GNUNET_new (struct REGEX_INTERNAL_Search);
  h->dht = dht;
  h->description = GNUNET_strdup (string);
  h->callback = callback;
  h->callback_cls = callback_cls;
  h->stats = stats;
  h->dht_get_handles = GNUNET_CONTAINER_multihashmap_create (32, GNUNET_NO);
  h->dht_get_results = GNUNET_CONTAINER_multihashmap_create (32, GNUNET_NO);

  /* Initialize context */
  len = strlen (string);
  size = REGEX_INTERNAL_get_first_key (string, len, &key);
  LOG (GNUNET_ERROR_TYPE_INFO,
       "Initial key for `%s' is %s (based on `%.*s')\n",
       string,
       GNUNET_h2s (&key),
       (int) size,
       string);
  ctx = GNUNET_new (struct RegexSearchContext);
  ctx->position = size;
  ctx->info = h;
  GNUNET_array_append (h->contexts,
                       h->n_contexts,
                       ctx);
  /* Start search in DHT */
  get_h = GNUNET_DHT_get_start (h->dht,     /* handle */
                                GNUNET_BLOCK_TYPE_REGEX, /* type */
                                &key,     /* key to search */
                                DHT_REPLICATION, /* replication level */
                                DHT_OPT,
                                &h->description[size],           /* xquery */
                                // FIXME add BLOOMFILTER to exclude filtered peers
                                len + 1 - size,                /* xquery bits */
                                // FIXME add BLOOMFILTER SIZE
                                &dht_get_string_handler, ctx);
  GNUNET_break (
    GNUNET_OK ==
    GNUNET_CONTAINER_multihashmap_put (h->dht_get_handles,
                                       &key,
                                       get_h,
                                       GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST)
    );

  return h;
}


static int
regex_cancel_dht_get (void *cls,
                      const struct GNUNET_HashCode *key,
                      void *value)
{
  struct GNUNET_DHT_GetHandle *h = value;

  GNUNET_DHT_get_stop (h);
  return GNUNET_YES;
}


static int
regex_free_result (void *cls,
                   const struct GNUNET_HashCode *key,
                   void *value)
{
  GNUNET_free (value);
  return GNUNET_YES;
}


void
REGEX_INTERNAL_search_cancel (struct REGEX_INTERNAL_Search *h)
{
  unsigned int i;

  GNUNET_free (h->description);
  GNUNET_CONTAINER_multihashmap_iterate (h->dht_get_handles,
                                         &regex_cancel_dht_get, NULL);
  GNUNET_CONTAINER_multihashmap_iterate (h->dht_get_results,
                                         &regex_free_result, NULL);
  GNUNET_CONTAINER_multihashmap_destroy (h->dht_get_results);
  GNUNET_CONTAINER_multihashmap_destroy (h->dht_get_handles);
  if (0 < h->n_contexts)
  {
    for (i = 0; i < h->n_contexts; i++)
      GNUNET_free (h->contexts[i]);
    GNUNET_free (h->contexts);
  }
  GNUNET_free (h);
}


/* end of regex_internal_dht.c */