implement parallel deduplicating optional attribute brute-forcing discovery process on top of reducer state, but as a side-activity

5 files changed, 545 insertions, 78 deletions

diff --git a/src/reducer/Makefile.am b/src/reducer/Makefile.am
index 3b7edb6..7aa389e 100644
--- a/src/reducer/Makefile.am
+++ b/src/reducer/Makefile.am
@@ -15,6 +15,7 @@ libanastasisredux_la_LDFLAGS = \
   -version-info 0:0:0 \
   -no-undefined
 libanastasisredux_la_SOURCES = \
+  anastasis_api_discovery.c \
   anastasis_api_redux.c anastasis_api_redux.h \
   anastasis_api_recovery_redux.c \
   anastasis_api_backup_redux.c \
diff --git a/src/reducer/anastasis_api_backup_redux.c b/src/reducer/anastasis_api_backup_redux.c
index eee1b70..fb30cbc 100644
--- a/src/reducer/anastasis_api_backup_redux.c
+++ b/src/reducer/anastasis_api_backup_redux.c
@@ -1276,69 +1276,6 @@ method_candidate (struct PolicyBuilder *pb,
 
 
 /**
- * Lookup @a salt of @a provider_url in @a state.
- *
- * @param state the state to inspect
- * @param provider_url provider to look into
- * @param[out] salt value to extract
- * @return #GNUNET_OK on success
- */
-static enum GNUNET_GenericReturnValue
-lookup_salt (const json_t *state,
-             const char *provider_url,
-             struct ANASTASIS_CRYPTO_ProviderSaltP *salt)
-{
-  const json_t *aps;
-  const json_t *cfg;
-  uint32_t http_status = 0;
-  bool disabled = false;
-  struct GNUNET_JSON_Specification spec[] = {
-    GNUNET_JSON_spec_mark_optional (
-      GNUNET_JSON_spec_bool ("disabled",
-                             &disabled)),
-    GNUNET_JSON_spec_mark_optional (
-      GNUNET_JSON_spec_uint32 ("http_status",
-                               &http_status)),
-    GNUNET_JSON_spec_mark_optional (
-      GNUNET_JSON_spec_fixed_auto ("salt",
-                                   salt)),
-    GNUNET_JSON_spec_end ()
-  };
-
-  aps = json_object_get (state,
-                         "authentication_providers");
-  if (NULL == aps)
-  {
-    GNUNET_break (0);
-    return GNUNET_SYSERR;
-  }
-  cfg = json_object_get (aps,
-                         provider_url);
-  if (NULL == cfg)
-  {
-    GNUNET_break (0);
-    return GNUNET_SYSERR;
-  }
-  if (GNUNET_OK !=
-      GNUNET_JSON_parse (cfg,
-                         spec,
-                         NULL, NULL))
-  {
-    /* provider not working */
-    GNUNET_break_op (0);
-    return GNUNET_NO;
-  }
-  if (disabled)
-    return GNUNET_NO;
-  if (NULL ==
-      json_object_get (cfg,
-                       "salt"))
-    return GNUNET_NO;
-  return GNUNET_OK;
-}
-
-
-/**
  * Compare two cost lists.
  *
  * @param my cost to compare
@@ -1806,9 +1743,9 @@ done_authentication (json_t *state,
       struct ANASTASIS_CRYPTO_ProviderSaltP salt;
 
       if (GNUNET_OK !=
-          lookup_salt (state,
-                       url,
-                       &salt))
+          ANASTASIS_reducer_lookup_salt_ (state,
+                                          url,
+                                          &salt))
         continue; /* skip providers that are down */
       provider = GNUNET_JSON_PACK (
         GNUNET_JSON_pack_string ("provider_url",
@@ -1835,9 +1772,9 @@ done_authentication (json_t *state,
       url_str = json_string_value (url);
       if ( (NULL == url_str) ||
            (GNUNET_OK !=
-            lookup_salt (state,
-                         url_str,
-                         &salt)) )
+            ANASTASIS_reducer_lookup_salt_ (state,
+                                            url_str,
+                                            &salt)) )
       {
         GNUNET_break (0);
         ANASTASIS_redux_fail_ (cb,
@@ -3437,9 +3374,9 @@ share_secret (struct UploadContext *uc)
                                ispec,
                                NULL, NULL)) ||
            (GNUNET_OK !=
-            lookup_salt (uc->state,
-                         pds[i].provider_url,
-                         &pds[i].provider_salt)) )
+            ANASTASIS_reducer_lookup_salt_ (uc->state,
+                                            pds[i].provider_url,
+                                            &pds[i].provider_salt)) )
       {
         GNUNET_break (0);
         ANASTASIS_redux_fail_ (uc->cb,
@@ -3722,9 +3659,9 @@ add_truth_object (struct UploadContext *uc,
     };
 
     if (GNUNET_OK !=
-        lookup_salt (uc->state,
-                     provider_url,
-                     &salt))
+        ANASTASIS_reducer_lookup_salt_ (uc->state,
+                                        provider_url,
+                                        &salt))
     {
       GNUNET_break (0);
       return GNUNET_SYSERR;
@@ -3891,9 +3828,9 @@ check_truth_upload (struct UploadContext *uc,
     tue->am_idx = am_idx;
     tue->policies_length = 1;
     if (GNUNET_OK !=
-        lookup_salt (uc->state,
-                     provider_url,
-                     &provider_salt))
+        ANASTASIS_reducer_lookup_salt_ (uc->state,
+                                        provider_url,
+                                        &provider_salt))
     {
       GNUNET_break (0);
       GNUNET_JSON_parse_free (spec);
diff --git a/src/reducer/anastasis_api_discovery.c b/src/reducer/anastasis_api_discovery.c
new file mode 100644
index 0000000..8ae7692
--- /dev/null
+++ b/src/reducer/anastasis_api_discovery.c
@@ -0,0 +1,452 @@
+/*
+  This file is part of Anastasis
+  Copyright (C) 2022 Anastasis SARL
+
+  Anastasis is free software; you can redistribute it and/or modify it under the
+  terms of the GNU General Public License as published by the Free Software
+  Foundation; either version 3, or (at your option) any later version.
+
+  Anastasis 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 General Public License for more details.
+
+  You should have received a copy of the GNU General Public License along with
+  Anastasis; see the file COPYING.GPL.  If not, see <http://www.gnu.org/licenses/>
+*/
+/**
+ * @file reducer/anastasis_api_discovery.c
+ * @brief anastasis recovery policy discovery api
+ * @author Christian Grothoff
+ */
+#include <platform.h>
+#include <jansson.h>
+#include "anastasis_redux.h"
+#include "anastasis_error_codes.h"
+#include <taler/taler_json_lib.h>
+#include "anastasis_api_redux.h"
+#include <dlfcn.h>
+
+
+/**
+ * Handle for one request we are doing at a specific provider.
+ */
+struct ProviderOperation
+{
+  /**
+   * Kept in a DLL.
+   */
+  struct ProviderOperation *next;
+
+  /**
+   * Kept in a DLL.
+   */
+  struct ProviderOperation *prev;
+
+  /**
+   * Base URL of the provider.
+   */
+  char *provider_url;
+
+  /**
+   * Handle to the version check operation we are performing.
+   */
+  struct ANASTASIS_VersionCheck *vc;
+
+  /**
+   * Handle discovery operation we this is a part of.
+   */
+  struct ANASTASIS_PolicyDiscovery *pd;
+
+  /**
+   * Attribute mask applied to the identity attributes
+   * for this operation.
+   */
+  json_int_t attribute_mask;
+};
+
+
+/**
+ * Handle for a discovery operation.
+ */
+struct ANASTASIS_PolicyDiscovery
+{
+  /**
+   * Head of HTTP requests, kept in a DLL.
+   */
+  struct ProviderOperation *po_head;
+
+  /**
+   * Tail of HTTP requests, kept in a DLL.
+   */
+  struct ProviderOperation *po_tail;
+
+  /**
+   * Function to call with results.
+   */
+  ANASTASIS_PolicyDiscoveryCallback cb;
+
+  /**
+   * Closure for @e cb.
+   */
+  void *cb_cls;
+
+  /**
+   * Map for duplicate detection, maps hashes of policies we
+   * have already seen to the value "dummy".
+   */
+  struct GNUNET_CONTAINER_MultiHashMap *dd_map;
+};
+
+
+/**
+ * Callback which passes back meta data about one of the
+ * recovery documents available at the provider.
+ *
+ * @param cls our `struct ProviderOperation *`
+ * @param version version number of the policy document,
+ *                0 for the end of the list
+ * @param server_time time of the backup at the provider
+ * @param recdoc_id hash of the compressed recovery document, uniquely
+ *                  identifies the document; NULL for the end of the list
+ * @param secret_name name of the secret as chosen by the user,
+ *                  or NULL if the user did not provide a name
+ */
+static void
+meta_cb (void *cls,
+         uint32_t version,
+         struct GNUNET_TIME_Timestamp server_time,
+         const struct GNUNET_HashCode *recdoc_id,
+         const char *secret_name)
+{
+  struct ProviderOperation *po = cls;
+  struct ANASTASIS_PolicyDiscovery *pd = po->pd;
+
+  if (NULL == recdoc_id)
+  {
+    po->vc = NULL;
+    GNUNET_CONTAINER_DLL_remove (pd->po_head,
+                                 pd->po_tail,
+                                 po);
+    GNUNET_free (po->provider_url);
+    GNUNET_free (po);
+    if (NULL == pd->po_head)
+    {
+      pd->cb (pd->cb_cls,
+              NULL,
+              NULL,
+              0,
+              0,
+              GNUNET_TIME_UNIT_ZERO_TS,
+              NULL);
+      ANASTASIS_policy_discovery_stop (pd);
+      return;
+    }
+    return;
+  }
+  if (GNUNET_YES ==
+      GNUNET_CONTAINER_multihashmap_contains (pd->dd_map,
+                                              recdoc_id))
+    return;
+  GNUNET_assert (
+    GNUNET_OK ==
+    GNUNET_CONTAINER_multihashmap_put (
+      pd->dd_map,
+      recdoc_id,
+      "dummy",
+      GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
+  pd->cb (pd->cb_cls,
+          recdoc_id,
+          po->provider_url,
+          version,
+          po->attribute_mask,
+          server_time,
+          secret_name);
+}
+
+
+/**
+ * Start policy operation for @a pd using identity @a id_data
+ * at provider @a provider_url.
+ *
+ * @param pd policy discovery operation
+ * @param id_data our identity data, derived using @a mask
+ * @param mask the mask describing which optional attributes were removed
+ * @param provider_url which provider to query
+ * @param state state machine state
+ * @param cursor cursor telling us from where to query
+ */
+static void
+start_po (struct ANASTASIS_PolicyDiscovery *pd,
+          const json_t *id_data,
+          json_int_t mask,
+          const char *provider_url,
+          const json_t *state,
+          const json_t *cursor)
+{
+  struct ProviderOperation *po;
+  uint32_t max_version = UINT32_MAX;
+  struct ANASTASIS_CRYPTO_ProviderSaltP provider_salt;
+
+  if (NULL != cursor)
+  {
+    size_t i;
+    json_t *obj;
+
+    json_array_foreach ((json_t *) cursor, i, obj)
+    {
+      const char *url;
+      uint64_t cmask;
+      uint32_t mv;
+      struct GNUNET_JSON_Specification spec[] = {
+        GNUNET_JSON_spec_string ("provider_url",
+                                 &url),
+        GNUNET_JSON_spec_uint64 ("mask",
+                                 &cmask),
+        GNUNET_JSON_spec_uint32 ("max_version",
+                                 &mv),
+        GNUNET_JSON_spec_end ()
+      };
+
+      if (GNUNET_OK !=
+          GNUNET_JSON_parse (obj,
+                             spec,
+                             NULL, NULL))
+      {
+        /* cursor invalid */
+        GNUNET_break (0);
+        return;
+      }
+      if ( (cmask == mask) &&
+           (0 == strcmp (url,
+                         provider_url)) )
+      {
+        max_version = mv;
+        break;
+      }
+    }
+  }
+
+  if (GNUNET_OK !=
+      ANASTASIS_reducer_lookup_salt_ (state,
+                                      provider_url,
+                                      &provider_salt))
+  {
+    GNUNET_break (0);
+    return;
+  }
+  po = GNUNET_new (struct ProviderOperation);
+  po->pd = pd;
+  po->attribute_mask = mask;
+  po->vc = ANASTASIS_recovery_get_versions (ANASTASIS_REDUX_ctx_,
+                                            id_data,
+                                            max_version,
+                                            provider_url,
+                                            &provider_salt,
+                                            &meta_cb,
+                                            po);
+  if (NULL == po->vc)
+  {
+    GNUNET_free (po);
+  }
+  else
+  {
+    GNUNET_CONTAINER_DLL_insert (pd->po_head,
+                                 pd->po_tail,
+                                 po);
+  }
+}
+
+
+struct ANASTASIS_PolicyDiscovery *
+ANASTASIS_policy_discovery_start (const json_t *state,
+                                  const json_t *cursor,
+                                  ANASTASIS_PolicyDiscoveryCallback cb,
+                                  void *cb_cls)
+{
+  struct ANASTASIS_PolicyDiscovery *pd;
+  json_t *master_id = json_object_get (state,
+                                       "identity_attributes");
+  json_t *providers = json_object_get (state,
+                                       "authentication_providers");
+  json_t *required_attributes = json_object_get (state,
+                                                 "required_attributes");
+  unsigned int opt_cnt;
+
+  if ( (NULL == master_id) ||
+       (! json_is_object (master_id)) )
+  {
+    GNUNET_break (0);
+    return NULL;
+  }
+  if ( (NULL == providers) ||
+       (! json_is_object (providers)) )
+  {
+    GNUNET_break (0);
+    return NULL;
+  }
+  if ( (NULL == required_attributes) ||
+       (! json_is_array (required_attributes)) )
+  {
+    GNUNET_break (0);
+    return NULL;
+  }
+
+  /* count optional attributes present in 'master_id' */
+  opt_cnt = 0;
+  {
+    size_t index;
+    json_t *required_attribute;
+
+    json_array_foreach (required_attributes, index, required_attribute)
+    {
+      const char *name;
+      int optional = false;
+      struct GNUNET_JSON_Specification spec[] = {
+        GNUNET_JSON_spec_string ("name",
+                                 &name),
+        GNUNET_JSON_spec_mark_optional (
+          GNUNET_JSON_spec_boolean ("optional",
+                                    &optional)),
+        GNUNET_JSON_spec_end ()
+      };
+      bool present;
+
+      if (GNUNET_OK !=
+          GNUNET_JSON_parse (required_attribute,
+                             spec,
+                             NULL, NULL))
+      {
+        GNUNET_break (0);
+        return NULL;
+      }
+      present = (NULL !=
+                 json_object_get (master_id,
+                                  name));
+      if ((! present) && (! optional))
+      {
+        GNUNET_break (0);
+        return NULL;
+      }
+      if (present && optional)
+        opt_cnt++;
+    }
+  }
+
+  pd = GNUNET_new (struct ANASTASIS_PolicyDiscovery);
+  pd->dd_map = GNUNET_CONTAINER_multihashmap_create (128,
+                                                     GNUNET_NO);
+  pd->cb = cb;
+  pd->cb_cls = cb_cls;
+
+  /* Compute 'id_data' for all possible masks, and then
+     start downloads at all providers for 'id_data' */
+  for (json_int_t mask = 0; mask < (1LL << opt_cnt); mask++)
+  {
+    json_t *id_data = ANASTASIS_mask_id_data (state,
+                                              master_id,
+                                              mask);
+    json_t *value;
+    const char *url;
+
+    json_object_foreach (providers, url, value)
+    {
+      start_po (pd,
+                id_data,
+                mask,
+                url,
+                state,
+                cursor);
+    }
+    json_decref (id_data);
+  }
+  if (NULL == pd->po_head)
+  {
+    GNUNET_break (0);
+    ANASTASIS_policy_discovery_stop (pd);
+    return NULL;
+  }
+  return pd;
+}
+
+
+void
+ANASTASIS_policy_discovery_stop (struct ANASTASIS_PolicyDiscovery *pd)
+{
+  struct ProviderOperation *po;
+
+  while (NULL != (po = pd->po_head))
+  {
+    GNUNET_CONTAINER_DLL_remove (pd->po_head,
+                                 pd->po_tail,
+                                 po);
+    ANASTASIS_recovery_get_versions_cancel (po->vc);
+    GNUNET_free (po->provider_url);
+    GNUNET_free (po);
+  }
+  GNUNET_CONTAINER_multihashmap_destroy (pd->dd_map);
+  GNUNET_free (pd);
+}
+
+
+json_t *
+ANASTASIS_mask_id_data (const json_t *state,
+                        const json_t *master_id,
+                        json_int_t mask)
+{
+  json_t *required_attributes = json_object_get (state,
+                                                 "required_attributes");
+  size_t index;
+  json_t *required_attribute;
+  json_t *ret = json_deep_copy (master_id);
+  unsigned int bit = 0;
+
+  if ( (NULL == required_attributes) ||
+       (! json_is_array (required_attributes)) )
+  {
+    GNUNET_break (0);
+    return NULL;
+  }
+
+  json_array_foreach (required_attributes, index, required_attribute)
+  {
+    const char *name;
+    int optional = false;
+    struct GNUNET_JSON_Specification spec[] = {
+      GNUNET_JSON_spec_string ("name",
+                               &name),
+      GNUNET_JSON_spec_mark_optional (
+        GNUNET_JSON_spec_boolean ("optional",
+                                  &optional)),
+      GNUNET_JSON_spec_end ()
+    };
+    bool present;
+
+    if (GNUNET_OK !=
+        GNUNET_JSON_parse (required_attribute,
+                           spec,
+                           NULL, NULL))
+    {
+      GNUNET_break (0);
+      return NULL;
+    }
+    present = (NULL !=
+               json_object_get (master_id,
+                                name));
+    if ((! present) && (! optional))
+    {
+      GNUNET_break (0);
+      return NULL;
+    }
+    if (present && optional)
+    {
+      if (0 != ((1LL << bit) & mask))
+      {
+        GNUNET_assert (0 ==
+                       json_object_del (ret,
+                                        name));
+      }
+      bit++;
+    }
+  }
+  return ret;
+}
diff --git a/src/reducer/anastasis_api_redux.c b/src/reducer/anastasis_api_redux.c
index 66aabe1..a83b86b 100644
--- a/src/reducer/anastasis_api_redux.c
+++ b/src/reducer/anastasis_api_redux.c
@@ -2004,3 +2004,66 @@ ANASTASIS_REDUX_load_continents_ ()
     GNUNET_JSON_pack_array_steal ("continents",
                                   continents));
 }
+
+
+/**
+ * Lookup @a salt of @a provider_url in @a state.
+ *
+ * @param state the state to inspect
+ * @param provider_url provider to look into
+ * @param[out] salt value to extract
+ * @return #GNUNET_OK on success
+ */
+enum GNUNET_GenericReturnValue
+ANASTASIS_reducer_lookup_salt_ (const json_t *state,
+                                const char *provider_url,
+                                struct ANASTASIS_CRYPTO_ProviderSaltP *salt)
+{
+  const json_t *aps;
+  const json_t *cfg;
+  uint32_t http_status = 0;
+  bool disabled = false;
+  struct GNUNET_JSON_Specification spec[] = {
+    GNUNET_JSON_spec_mark_optional (
+      GNUNET_JSON_spec_bool ("disabled",
+                             &disabled)),
+    GNUNET_JSON_spec_mark_optional (
+      GNUNET_JSON_spec_uint32 ("http_status",
+                               &http_status)),
+    GNUNET_JSON_spec_mark_optional (
+      GNUNET_JSON_spec_fixed_auto ("salt",
+                                   salt)),
+    GNUNET_JSON_spec_end ()
+  };
+
+  aps = json_object_get (state,
+                         "authentication_providers");
+  if (NULL == aps)
+  {
+    GNUNET_break (0);
+    return GNUNET_SYSERR;
+  }
+  cfg = json_object_get (aps,
+                         provider_url);
+  if (NULL == cfg)
+  {
+    GNUNET_break (0);
+    return GNUNET_SYSERR;
+  }
+  if (GNUNET_OK !=
+      GNUNET_JSON_parse (cfg,
+                         spec,
+                         NULL, NULL))
+  {
+    /* provider not working */
+    GNUNET_break_op (0);
+    return GNUNET_NO;
+  }
+  if (disabled)
+    return GNUNET_NO;
+  if (NULL ==
+      json_object_get (cfg,
+                       "salt"))
+    return GNUNET_NO;
+  return GNUNET_OK;
+}
diff --git a/src/reducer/anastasis_api_redux.h b/src/reducer/anastasis_api_redux.h
index f161d61..81fbeed 100644
--- a/src/reducer/anastasis_api_redux.h
+++ b/src/reducer/anastasis_api_redux.h
@@ -168,6 +168,20 @@ ANASTASIS_recovery_state_to_string_ (enum ANASTASIS_RecoveryState rs);
 
 
 /**
+ * Lookup @a salt of @a provider_url in @a state.
+ *
+ * @param state the state to inspect
+ * @param provider_url provider to look into
+ * @param[out] salt value to extract
+ * @return #GNUNET_OK on success
+ */
+enum GNUNET_GenericReturnValue
+ANASTASIS_reducer_lookup_salt_ (const json_t *state,
+                                const char *provider_url,
+                                struct ANASTASIS_CRYPTO_ProviderSaltP *salt);
+
+
+/**
  * Function to return a json error response.
  *
  * @param cb callback to give error to