[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[taler-anastasis] branch master updated: implement 'optimal' policy gene
|
From: |
gnunet |
|
Subject: |
[taler-anastasis] branch master updated: implement 'optimal' policy generation, but with CPU cap to ensure it is virtually instant even for very complex policies; fixes #6830 |
|
Date: |
Mon, 28 Jun 2021 22:48:03 +0200 |
This is an automated email from the git hooks/post-receive script.
grothoff pushed a commit to branch master
in repository anastasis.
The following commit(s) were added to refs/heads/master by this push:
new 1241f52 implement 'optimal' policy generation, but with CPU cap to
ensure it is virtually instant even for very complex policies; fixes #6830
1241f52 is described below
commit 1241f5257542438057e0d3d4a2e29ba4b29e1f19
Author: Christian Grothoff <christian@grothoff.org>
AuthorDate: Mon Jun 28 22:48:00 2021 +0200
implement 'optimal' policy generation, but with CPU cap to ensure it is
virtually instant even for very complex policies; fixes #6830
---
...tasis_reducer_recovery_enter_user_attributes.sh | 28 +-
src/reducer/anastasis_api_backup_redux.c | 880 ++++++++++++++++++---
2 files changed, 777 insertions(+), 131 deletions(-)
diff --git a/src/cli/test_anastasis_reducer_recovery_enter_user_attributes.sh
b/src/cli/test_anastasis_reducer_recovery_enter_user_attributes.sh
index 716bc02..12e0197 100755
--- a/src/cli/test_anastasis_reducer_recovery_enter_user_attributes.sh
+++ b/src/cli/test_anastasis_reducer_recovery_enter_user_attributes.sh
@@ -416,13 +416,37 @@ echo -n "Running challenge logic ..."
UUID0=`jq -r -e .recovery_information.challenges[0].uuid < $R2FILE`
UUID1=`jq -r -e .recovery_information.challenges[1].uuid < $R2FILE`
+UUID2=`jq -r -e .recovery_information.challenges[2].uuid < $R2FILE`
+UUID0Q=`jq -r -e .recovery_information.challenges[0].instructions < $R2FILE`
+UUID1Q=`jq -r -e .recovery_information.challenges[1].instructions < $R2FILE`
+UUID2Q=`jq -r -e .recovery_information.challenges[2].instructions < $R2FILE`
+
+if test "$UUID2Q" = 'How old are you?'
+then
+ AGE_UUID=$UUID2
+elif test "$UUID1Q" = 'How old are you?'
+then
+ AGE_UUID=$UUID1
+else
+ AGE_UUID=$UUID0
+fi
+
+if test "$UUID2Q" = 'What is your name?'
+then
+ NAME_UUID=$UUID2
+elif test "$UUID1Q" = 'What is your name?'
+then
+ NAME_UUID=$UUID1
+else
+ NAME_UUID=$UUID0
+fi
anastasis-reducer -a \
"$(jq -n '
{
uuid: $UUID
}' \
- --arg UUID "$UUID0"
+ --arg UUID "$NAME_UUID"
)" \
select_challenge < $R2FILE > $R1FILE
@@ -434,7 +458,7 @@ anastasis-reducer -a \
{
uuid: $UUID
}' \
- --arg UUID "$UUID1"
+ --arg UUID "$AGE_UUID"
)" \
select_challenge < $R2FILE > $R1FILE
diff --git a/src/reducer/anastasis_api_backup_redux.c
b/src/reducer/anastasis_api_backup_redux.c
index f1f4a0d..ce214e8 100644
--- a/src/reducer/anastasis_api_backup_redux.c
+++ b/src/reducer/anastasis_api_backup_redux.c
@@ -26,6 +26,13 @@
#include "anastasis_api_redux.h"
#include <taler/taler_merchant_service.h>
+/**
+ * CPU limiter: do not evaluate more than 16k
+ * possible policy combinations to find the "best"
+ * policy.
+ */
+#define MAX_EVALUATIONS (1024 * 16)
+
#define GENERATE_STRING(STRING) #STRING,
static const char *backup_strings[] = {
@@ -391,6 +398,90 @@ struct Costs
};
+/**
+ * Which provider would be used for the given challenge,
+ * and at what cost?
+ */
+struct PolicyEntry
+{
+ /**
+ * URL of the provider.
+ */
+ const char *provider_name;
+
+ /**
+ * Recovery fee.
+ */
+ struct TALER_Amount usage_fee;
+};
+
+
+/**
+ * Map from challenges to providers.
+ */
+struct PolicyMap
+{
+ /**
+ * Kept in a DLL.
+ */
+ struct PolicyMap *next;
+
+ /**
+ * Kept in a DLL.
+ */
+ struct PolicyMap *prev;
+
+ /**
+ * Array of proividers selected for each challenge,
+ * with associated costs.
+ * Length of the array will be 'req_methods'.
+ */
+ struct PolicyEntry *providers;
+
+ /**
+ * Diversity score for this policy mapping.
+ */
+ unsigned int diversity;
+
+};
+
+
+/**
+ * Array of challenges for a policy, and DLL with
+ * possible mappings of challenges to providers.
+ */
+struct Policy
+{
+
+ /**
+ * Kept in DLL of all possible policies.
+ */
+ struct Policy *next;
+
+ /**
+ * Kept in DLL of all possible policies.
+ */
+ struct Policy *prev;
+
+ /**
+ * Head of DLL.
+ */
+ struct PolicyMap *pm_head;
+
+ /**
+ * Tail of DLL.
+ */
+ struct PolicyMap *pm_tail;
+
+ /**
+ * Challenges selected for this policy.
+ * Length of the array will be 'req_methods'.
+ */
+ unsigned int *challenges;
+
+};
+
+
/**
* Information for running done_authentication() logic.
*/
@@ -406,6 +497,16 @@ struct PolicyBuilder
*/
const json_t *methods;
+ /**
+ * Head of DLL of all possible policies.
+ */
+ struct Policy *p_head;
+
+ /**
+ * Tail of DLL of all possible policies.
+ */
+ struct Policy *p_tail;
+
/**
* Array of authentication policies to be computed.
*/
@@ -429,12 +530,36 @@ struct PolicyBuilder
*/
const char *hint;
+ /**
+ * Policy we are currently building maps for.
+ */
+ struct Policy *current_policy;
+
/**
* LL of costs associated with the currently preferred
* policy.
*/
struct Costs *best_cost;
+ /**
+ * Array of 'best' policy maps found so far,
+ * ordered by policy.
+ */
+ struct PolicyMap *best_map;
+
+ /**
+ * Array of the currency policy maps under evaluation
+ * by find_best_map().
+ */
+ struct PolicyMap *curr_map;
+
+ /**
+ * How many mappings have we evaluated so far?
+ * Used to limit the computation by aborting after
+ * #MAX_EVALUATIONS trials.
+ */
+ unsigned int evaluations;
+
/**
* Overall number of challenges provided by the user.
*/
@@ -452,6 +577,13 @@ struct PolicyBuilder
*/
unsigned int best_diversity;
+ /**
+ * Number of identical challenges duplicated at
+ * various providers in the best case. Smaller is
+ * better.
+ */
+ unsigned int best_duplicates;
+
/**
* Error code to return, #TALER_EC_NONE on success.
*/
@@ -475,6 +607,153 @@ free_costs (struct Costs *costs)
}
+/**
+ * Check if providers @a p1 and @a p2 have equivalent
+ * methods and cost structures.
+ *
+ * @return true if the providers are fully equivalent
+ */
+static bool
+equiv_provider (struct PolicyBuilder *pb,
+ const char *p1,
+ const char *p2)
+{
+ json_t *j1;
+ json_t *j2;
+ json_t *m1;
+ json_t *m2;
+ struct TALER_Amount uc1;
+ struct TALER_Amount uc2;
+
+ j1 = json_object_get (pb->providers,
+ p1);
+ j2 = json_object_get (pb->providers,
+ p2);
+ if ( (NULL == j1) ||
+ (NULL == j2) )
+ {
+ GNUNET_break (0);
+ return false;
+ }
+
+ {
+ struct GNUNET_JSON_Specification s1[] = {
+ GNUNET_JSON_spec_json ("methods",
+ &m1),
+ TALER_JSON_spec_amount ("truth_upload_fee",
+ &uc1),
+ GNUNET_JSON_spec_end ()
+ };
+
+ if (GNUNET_OK !=
+ GNUNET_JSON_parse (j1,
+ s1,
+ NULL, NULL))
+ {
+ GNUNET_break (0);
+ return false;
+ }
+ }
+
+ {
+ struct GNUNET_JSON_Specification s2[] = {
+ GNUNET_JSON_spec_json ("methods",
+ &m2),
+ TALER_JSON_spec_amount ("truth_upload_fee",
+ &uc2),
+ GNUNET_JSON_spec_end ()
+ };
+
+ if (GNUNET_OK !=
+ GNUNET_JSON_parse (j2,
+ s2,
+ NULL, NULL))
+ {
+ GNUNET_break (0);
+ return false;
+ }
+ }
+
+ if ( (GNUNET_OK !=
+ TALER_amount_cmp_currency (&uc1,
+ &uc2)) ||
+ (0 !=
+ TALER_amount_cmp (&uc1,
+ &uc2)) )
+ return false;
+
+ if (json_array_size (m1) != json_array_size (m2))
+ return false;
+ {
+ size_t idx1;
+ json_t *e1;
+
+ json_array_foreach (m1, idx1, e1)
+ {
+ const char *type1;
+ struct TALER_Amount fee1;
+ struct GNUNET_JSON_Specification s1[] = {
+ GNUNET_JSON_spec_string ("type",
+ &type1),
+ TALER_JSON_spec_amount ("usage_fee",
+ &fee1),
+ GNUNET_JSON_spec_end ()
+ };
+ bool matched = false;
+
+ if (GNUNET_OK !=
+ GNUNET_JSON_parse (e1,
+ s1,
+ NULL, NULL))
+ {
+ GNUNET_break (0);
+ return false;
+ }
+ {
+ size_t idx2;
+ json_t *e2;
+
+ json_array_foreach (m2, idx2, e2)
+ {
+ const char *type2;
+ struct TALER_Amount fee2;
+ struct GNUNET_JSON_Specification s2[] = {
+ GNUNET_JSON_spec_string ("type",
+ &type2),
+ TALER_JSON_spec_amount ("usage_fee",
+ &fee2),
+ GNUNET_JSON_spec_end ()
+ };
+
+ if (GNUNET_OK !=
+ GNUNET_JSON_parse (e2,
+ s2,
+ NULL, NULL))
+ {
+ GNUNET_break (0);
+ return false;
+ }
+ if ( (0 == strcmp (type1,
+ type2)) &&
+ (GNUNET_OK ==
+ TALER_amount_cmp_currency (&fee1,
+ &fee2)) &&
+ (0 == TALER_amount_cmp (&fee1,
+ &fee2)) )
+ {
+ matched = true;
+ break;
+ }
+ }
+ }
+ if (! matched)
+ return false;
+ }
+ }
+ return true;
+}
+
+
/**
* Evaluate the cost/benefit of the provider selection in @a prov_sel
* and if it is better then the best known one in @a pb, update @a pb.
@@ -487,9 +766,8 @@ eval_provider_selection (struct PolicyBuilder *pb,
const char *prov_sel[])
{
unsigned int curr_diversity;
- struct Costs *my_cost = NULL;
+ struct PolicyEntry policy_ent[pb->req_methods];
- /* calculate cost */
for (unsigned int i = 0; i < pb->req_methods; i++)
{
const json_t *method_obj = json_array_get (pb->methods,
@@ -502,11 +780,14 @@ eval_provider_selection (struct PolicyBuilder *pb,
size_t index;
bool found = false;
uint32_t size_limit_in_mb;
+ struct TALER_Amount upload_cost;
struct GNUNET_JSON_Specification pspec[] = {
GNUNET_JSON_spec_uint32 ("storage_limit_in_megabytes",
&size_limit_in_mb),
GNUNET_JSON_spec_json ("methods",
&provider_methods),
+ TALER_JSON_spec_amount ("truth_upload_fee",
+ &upload_cost),
GNUNET_JSON_spec_end ()
};
void *challenge;
@@ -520,6 +801,7 @@ eval_provider_selection (struct PolicyBuilder *pb,
GNUNET_JSON_spec_end ()
};
+ policy_ent[i].provider_name = prov_sel[i];
if (GNUNET_OK !=
GNUNET_JSON_parse (method_obj,
mspec,
@@ -570,28 +852,11 @@ eval_provider_selection (struct PolicyBuilder *pb,
(challenge_size_ok (size_limit_in_mb,
challenge_size) ) )
{
- struct Costs *pos = my_cost;
-
found = true;
- while ( (NULL != pos) &&
- (GNUNET_OK !=
- TALER_amount_cmp_currency (&pos->cost,
- &method_cost)) )
- pos = pos->next;
- if (NULL == pos)
- {
- pos = GNUNET_new (struct Costs);
- pos->cost = method_cost;
- pos->next = my_cost;
- my_cost = pos;
- }
- else
- {
- GNUNET_assert (0 <=
- TALER_amount_add (&pos->cost,
- &pos->cost,
- &method_cost));
- }
+ GNUNET_break (0 <=
+ TALER_amount_add (&policy_ent[i].usage_fee,
+ &method_cost,
+ &upload_cost));
}
}
if (! found)
@@ -600,14 +865,14 @@ eval_provider_selection (struct PolicyBuilder *pb,
Cost is basically 'infinite', but we simply then skip this. */
GNUNET_JSON_parse_free (pspec);
GNUNET_JSON_parse_free (mspec);
- free_costs (my_cost);
return;
}
GNUNET_JSON_parse_free (mspec);
GNUNET_JSON_parse_free (pspec);
}
- /* calculate provider diversity by counting number of different providers
selected */
+ /* calculate provider diversity by counting number of different
+ providers selected */
curr_diversity = 0;
for (unsigned int i = 0; i < pb->req_methods; i++)
{
@@ -624,79 +889,71 @@ eval_provider_selection (struct PolicyBuilder *pb,
if (! found)
curr_diversity++;
}
+#if DEBUG
+ fprintf (stderr,
+ "Diversity: %u (best: %u)\n",
+ curr_diversity,
+ pb->best_diversity);
+#endif
if (curr_diversity < pb->best_diversity)
+ return; /* do not allow combinations that are bad
+ for provider diversity */
+ if (curr_diversity > pb->best_diversity)
{
- free_costs (my_cost);
- return;
- }
- if (0 != pb->best_diversity)
- {
- int ranking = 0; /* lower is better for new cost */
+ /* drop existing policies, they are all worse */
+ struct PolicyMap *m;
- for (struct Costs *cmp = pb->best_cost;
- NULL != cmp;
- cmp = cmp->next)
+ while (NULL != (m = pb->current_policy->pm_head))
{
- bool found = false;
- for (struct Costs *pos = my_cost;
- NULL != pos;
- pos = pos->next)
- {
- if (GNUNET_OK !=
- TALER_amount_cmp_currency (&cmp->cost,
- &pos->cost))
- continue;
- found = true;
- }
- if (! found)
- ranking--; /* new policy has no cost in this currency */
+ GNUNET_CONTAINER_DLL_remove (pb->current_policy->pm_head,
+ pb->current_policy->pm_tail,
+ m);
+ GNUNET_free (m->providers);
+ GNUNET_free (m);
}
-
- for (struct Costs *pos = my_cost;
- NULL != pos;
- pos = pos->next)
+ pb->best_diversity = curr_diversity;
+ }
+ if (NULL == pb->p_head)
+ {
+ /* For the first policy, check for equivalent
+ policy mapping existing: we
+ do not want to do spend CPU time investigating
+ purely equivalent permutations */
+ for (struct PolicyMap *m = pb->current_policy->pm_head;
+ NULL != m;
+ m = m->next)
{
- bool found = false;
- for (struct Costs *cmp = pb->best_cost;
- NULL != cmp;
- cmp = cmp->next)
+ bool equiv = true;
+ for (unsigned int i = 0; i<pb->req_methods; i++)
{
- if (GNUNET_OK !=
- TALER_amount_cmp_currency (&cmp->cost,
- &pos->cost))
- continue;
- found = true;
- switch (TALER_amount_cmp (&cmp->cost,
- &pos->cost))
+ if (! equiv_provider (pb,
+ m->providers[i].provider_name,
+ policy_ent[i].provider_name))
{
- case -1: /* cmp < pos */
- ranking--;
- break;
- case 0:
- break;
- case 1: /* cmp > pos */
- ranking++;
+ equiv = false;
break;
}
- break;
}
- if (! found)
- ranking++; /* old policy has no cost in this currency */
- }
- if (ranking >= 0)
- {
- /* new method not clearly better, do not use it */
- free_costs (my_cost);
- return;
+ if (equiv)
+ return; /* equivalent to known allocation */
}
}
- memcpy (pb->best_sel,
- prov_sel,
- sizeof (const char *) * pb->req_methods);
- pb->best_diversity = curr_diversity;
- free_costs (pb->best_cost);
- pb->best_cost = my_cost;
+ /* Add possible mapping to result list */
+ {
+ struct PolicyMap *m;
+
+ m = GNUNET_new (struct PolicyMap);
+ m->providers = GNUNET_new_array (pb->req_methods,
+ struct PolicyEntry);
+ memcpy (m->providers,
+ policy_ent,
+ sizeof (struct PolicyEntry) * pb->req_methods);
+ m->diversity = curr_diversity;
+ GNUNET_CONTAINER_DLL_insert (pb->current_policy->pm_head,
+ pb->current_policy->pm_tail,
+ m);
+ }
}
@@ -746,40 +1003,25 @@ provider_candidate (struct PolicyBuilder *pb,
static void
go_with (struct PolicyBuilder *pb)
{
- const unsigned int *m_idx = pb->m_idx;
- const char *best_sel[pb->req_methods];
const char *prov_sel[pb->req_methods];
- json_t *method_arr;
-
- /* compute best provider selection (store in best_sel) */
+ struct Policy *policy;
+
+ /* compute provider selection */
+ policy = GNUNET_new (struct Policy);
+ policy->challenges = GNUNET_new_array (pb->req_methods,
+ unsigned int);
+ memcpy (policy->challenges,
+ pb->m_idx,
+ pb->req_methods * sizeof (unsigned int));
+ pb->current_policy = policy;
pb->best_diversity = 0;
- pb->best_sel = best_sel;
provider_candidate (pb,
prov_sel,
0);
- /* Convert best_sel to entry in 'policies' array */
- method_arr = json_array ();
- GNUNET_assert (NULL != method_arr);
- for (unsigned int i = 0; i < pb->req_methods; i++)
- {
- json_t *policy_method = json_pack ("{s:I, s:s}",
- "authentication_method",
- (json_int_t) m_idx[i],
- "provider",
- best_sel[i]);
- GNUNET_assert (0 ==
- json_array_append_new (method_arr,
- policy_method));
- }
- {
- json_t *policy = json_pack ("{s:o}",
- "methods",
- method_arr);
- GNUNET_assert (NULL != policy);
- GNUNET_assert (0 ==
- json_array_append_new (pb->policies,
- policy));
- }
+ GNUNET_CONTAINER_DLL_insert (pb->p_head,
+ pb->p_tail,
+ policy);
+ pb->current_policy = NULL;
}
@@ -795,23 +1037,31 @@ static void
method_candidate (struct PolicyBuilder *pb,
unsigned int i)
{
- unsigned int start = 0;
+ unsigned int start;
unsigned int *m_idx = pb->m_idx;
- if (i > 0)
- start = m_idx[i - 1] + 1;
+ start = (i > 0) ? m_idx[i - 1] + 1 : 0;
for (unsigned int j = start; j < pb->num_methods; j++)
{
m_idx[i] = j;
if (i == pb->req_methods - 1)
{
+#if DEBUG
+ fprintf (stderr,
+ "Suggesting: ");
+ for (unsigned int k = 0; k<pb->req_methods; k++)
+ {
+ fprintf (stderr,
+ "%u ",
+ m_idx[k]);
+ }
+ fprintf (stderr, "\n");
+#endif
go_with (pb);
+ continue;
}
- else
- {
- method_candidate (pb,
- i + 1);
- }
+ method_candidate (pb,
+ i + 1);
}
}
@@ -863,6 +1113,379 @@ lookup_salt (const json_t *state,
}
+/**
+ * Add costs from @a pe to @a my_cost list.
+ *
+ * @param[in,out] my_cost pointer to list to modify
+ * @param pe cost entry to add
+ */
+static void
+add_cost (struct Costs **my_cost,
+ const struct PolicyEntry *pe)
+{
+ for (struct Costs *pos = *my_cost;
+ NULL != pos;
+ pos = pos->next)
+ {
+ if (GNUNET_OK !=
+ TALER_amount_cmp_currency (&pos->cost,
+ &pe->usage_fee))
+ continue;
+ GNUNET_assert (0 <=
+ TALER_amount_add (&pos->cost,
+ &pos->cost,
+ &pe->usage_fee));
+ return;
+ }
+ {
+ struct Costs *nc;
+
+ nc = GNUNET_new (struct Costs);
+ nc->cost = pe->usage_fee;
+ nc->next = *my_cost;
+ *my_cost = nc;
+ }
+}
+
+
+/**
+ * Compare two cost lists.
+ *
+ * @param my cost to compare
+ * @param be cost to compare
+ * @return 0 if costs are estimated equal,
+ * 1 if @a me < @a be
+ * -1 if @a me > @a be
+ */
+static int
+compare_costs (const struct Costs *my,
+ const struct Costs *be)
+{
+ int ranking = 0;
+
+ for (const struct Costs *cmp = be;
+ NULL != cmp;
+ cmp = cmp->next)
+ {
+ bool found = false;
+
+ for (const struct Costs *pos = my;
+ NULL != pos;
+ pos = pos->next)
+ {
+ if (GNUNET_OK !=
+ TALER_amount_cmp_currency (&cmp->cost,
+ &pos->cost))
+ continue;
+ found = true;
+ }
+ if (! found)
+ ranking--; /* new policy has no cost in this currency */
+ }
+
+ for (const struct Costs *pos = my;
+ NULL != pos;
+ pos = pos->next)
+ {
+ bool found = false;
+
+ for (const struct Costs *cmp = be;
+ NULL != cmp;
+ cmp = cmp->next)
+ {
+ if (GNUNET_OK !=
+ TALER_amount_cmp_currency (&cmp->cost,
+ &pos->cost))
+ continue;
+ found = true;
+ switch (TALER_amount_cmp (&cmp->cost,
+ &pos->cost))
+ {
+ case -1: /* cmp < pos */
+ ranking--;
+ break;
+ case 0:
+ break;
+ case 1: /* cmp > pos */
+ ranking++;
+ break;
+ }
+ break;
+ }
+ if (! found)
+ ranking++; /* old policy has no cost in this currency */
+ }
+ if (0 == ranking)
+ return 0;
+ return (0 > ranking) ? -1 : 1;
+}
+
+
+/**
+ * Evaluate the combined policy map stack in the ``curr_map`` of @a pb
+ * and compare to the current best cost. If we are better, save the
+ * stack in the ``best_map``.
+ *
+ * @param[in,out] pb policy builder we evaluate for
+ * @param num_policies length of the ``curr_map`` array
+ */
+static void
+evaluate_map (struct PolicyBuilder *pb,
+ unsigned int num_policies)
+{
+ struct Costs *my_cost = NULL;
+ unsigned int i = 0;
+ unsigned int duplicates = 0;
+ int ccmp;
+
+#if DEBUG
+ fprintf (stderr,
+ "Checking...\n");
+#endif
+ /* calculate cost */
+ for (const struct Policy *p = pb->p_head;
+ NULL != p;
+ p = p->next)
+ {
+ const struct PolicyMap *pm = &pb->curr_map[i++];
+
+#if DEBUG
+ fprintf (stderr,
+ "Evaluating %p (%u): ",
+ p,
+ pm->diversity);
+ for (unsigned int k = 0; k<pb->req_methods; k++)
+ {
+ const struct PolicyEntry *pe = &pm->providers[k];
+
+ fprintf (stderr,
+ "%u->%s",
+ p->challenges[k],
+ pe->provider_name);
+ }
+ fprintf (stderr, "\n");
+#endif
+ for (unsigned int j = 0; j<pb->req_methods; j++)
+ {
+ const struct PolicyEntry *pe = &pm->providers[j];
+ unsigned int cv = p->challenges[j];
+ bool found = false;
+ unsigned int i2 = 0;
+
+ /* check for duplicates */
+ for (const struct Policy *p2 = pb->p_head;
+ p2 != p;
+ p2 = p2->next)
+ {
+ const struct PolicyMap *pm2 = &pb->curr_map[i2++];
+
+ for (unsigned int j2 = 0; j2<pb->req_methods; j2++)
+ {
+ const struct PolicyEntry *pe2 = &pm2->providers[j2];
+ unsigned int cv2 = p2->challenges[j2];
+
+ if (cv != cv2)
+ continue; /* different challenge */
+ if (0 == strcmp (pe->provider_name,
+ pe2->provider_name))
+ found = true; /* same challenge&provider! */
+ else
+ duplicates++; /* penalty for same challenge at two providers */
+ }
+ }
+ if (found)
+ continue; /* cost already included, do not add */
+ add_cost (&my_cost,
+ pe);
+ }
+ }
+
+ ccmp = -1; /* non-zero if 'best_duplicates' is UINT_MAX */
+ if ( (UINT_MAX != pb->best_duplicates) &&
+ (0 < (ccmp = compare_costs (my_cost,
+ pb->best_cost))) )
+ {
+ /* new method not clearly better, do not use it */
+ free_costs (my_cost);
+#if DEBUG
+ fprintf (stderr,
+ "... useless\n");
+#endif
+ return;
+ }
+ if ( (0 == ccmp) &&
+ (duplicates > pb->best_duplicates) )
+ {
+ /* new method is cost-equal, but looses on duplicates,
+ do not use it */
+ free_costs (my_cost);
+#if DEBUG
+ fprintf (stderr,
+ "... useless\n");
+#endif
+ return;
+ }
+ /* new method is better (or first), set as best */
+#if DEBUG
+ fprintf (stderr,
+ "New best: %u duplicates, %s cost\n",
+ duplicates,
+ TALER_amount2s (&my_cost->cost));
+#endif
+ free_costs (pb->best_cost);
+ pb->best_cost = my_cost;
+ pb->best_duplicates = duplicates;
+ memcpy (pb->best_map,
+ pb->curr_map,
+ sizeof (struct PolicyMap) * num_policies);
+}
+
+
+/**
+ * Try all policy maps for @a pos and evaluate the
+ * resulting total cost, saving the best result in
+ * @a pb.
+ *
+ * @param[in,out] pb policy builder context
+ * @param pos policy we are currently looking at maps for
+ * @param off index of @a pos for the policy map
+ */
+static void
+find_best_map (struct PolicyBuilder *pb,
+ struct Policy *pos,
+ unsigned int off)
+{
+ if (NULL == pos)
+ {
+ evaluate_map (pb,
+ off);
+ pb->evaluations++;
+ return;
+ }
+ for (struct PolicyMap *pm = pos->pm_head;
+ NULL != pm;
+ pm = pm->next)
+ {
+ pb->curr_map[off] = *pm;
+ find_best_map (pb,
+ pos->next,
+ off + 1);
+ if (pb->evaluations >= MAX_EVALUATIONS)
+ break;
+ }
+}
+
+
+/**
+ * Select cheapest policy combinations and add them to the JSON ``policies``
+ * array in @a pb
+ *
+ * @param[in,out] policy builder with our state
+ */
+static void
+select_policies (struct PolicyBuilder *pb)
+{
+ unsigned int cnt = 0;
+
+ for (struct Policy *p = pb->p_head;
+ NULL != p;
+ p = p->next)
+ cnt++;
+ {
+ struct PolicyMap best[cnt];
+ struct PolicyMap curr[cnt];
+ unsigned int i;
+
+ pb->best_map = best;
+ pb->curr_map = curr;
+ pb->best_duplicates = UINT_MAX; /* worst */
+ find_best_map (pb,
+ pb->p_head,
+ 0);
+ GNUNET_log (GNUNET_ERROR_TYPE_INFO,
+ "Assessed %u/%u policies\n",
+ pb->evaluations,
+ (unsigned int) MAX_EVALUATIONS);
+ i = 0;
+ for (struct Policy *p = pb->p_head;
+ NULL != p;
+ p = p->next)
+ {
+ struct PolicyMap *pm = &best[i++];
+ json_t *method_arr;
+
+#if DEBUG
+ fprintf (stderr,
+ "Best map (%u): ",
+ pm->diversity);
+ for (unsigned int k = 0; k<pb->req_methods; k++)
+ {
+ fprintf (stderr,
+ "%u->%s ",
+ p->challenges[k],
+ pm->providers[k].provider_name);
+ }
+ fprintf (stderr, "\n");
+#endif
+ /* Convert "best" selection into 'policies' array */
+ method_arr = json_array ();
+ GNUNET_assert (NULL != method_arr);
+ for (unsigned int i = 0; i < pb->req_methods; i++)
+ {
+ json_t *policy_method = json_pack ("{s:I, s:s}",
+ "authentication_method",
+ (json_int_t) p->challenges[i],
+ "provider",
+ pm->providers[i].provider_name);
+ GNUNET_assert (0 ==
+ json_array_append_new (method_arr,
+ policy_method));
+ }
+ {
+ json_t *policy = json_pack ("{s:o}",
+ "methods",
+ method_arr);
+ GNUNET_assert (NULL != policy);
+ GNUNET_assert (0 ==
+ json_array_append_new (pb->policies,
+ policy));
+ }
+ }
+ }
+}
+
+
+/**
+ * Clean up @a pb, in particular the policies DLL.
+ *
+ * @param[in] pb builder to clean up
+ */
+static void
+clean_pb (struct PolicyBuilder *pb)
+{
+ struct Policy *p;
+
+ while (NULL != (p = pb->p_head))
+ {
+ struct PolicyMap *pm;
+
+ while (NULL != (pm = p->pm_head))
+ {
+ GNUNET_CONTAINER_DLL_remove (p->pm_head,
+ p->pm_tail,
+ pm);
+ GNUNET_free (pm->providers);
+ GNUNET_free (pm);
+ }
+ GNUNET_CONTAINER_DLL_remove (pb->p_head,
+ pb->p_tail,
+ p);
+ GNUNET_free (p->challenges);
+ GNUNET_free (p);
+ }
+}
+
+
/**
* DispatchHandler/Callback function which is called for a
* "done_authentication" action. Automaticially computes policies
@@ -909,12 +1532,10 @@ done_authentication (json_t *state,
"'authentication_methods' must be provided");
return NULL;
}
- pb.policies = json_array ();
pb.num_methods = json_array_size (pb.methods);
switch (pb.num_methods)
{
case 0:
- json_decref (pb.policies);
ANASTASIS_redux_fail_ (cb,
cb_cls,
TALER_EC_ANASTASIS_REDUCER_STATE_INVALID,
@@ -936,7 +1557,10 @@ done_authentication (json_t *state,
pb.req_methods = pb.num_methods - 3;
break;
default:
- pb.req_methods = pb.num_methods / 2;
+ /* cap at 4 for auto-generation, algorithm
+ to compute mapping gets too expensive
+ otherwise. */
+ pb.req_methods = 4;
break;
}
{
@@ -947,7 +1571,9 @@ done_authentication (json_t *state,
method_candidate (&pb,
0);
}
- free_costs (pb.best_cost);
+ pb.policies = json_array ();
+ select_policies (&pb);
+ clean_pb (&pb);
if (TALER_EC_NONE != pb.ec)
{
json_decref (pb.policies);
@@ -961,7 +1587,6 @@ done_authentication (json_t *state,
json_object_set_new (state,
"policies",
pb.policies));
-
providers = json_object_get (arguments,
"providers");
if (NULL == providers)
@@ -2079,9 +2704,6 @@ share_secret (struct UploadContext *uc)
json_t *pdj = json_array_get (providers,
i);
struct GNUNET_JSON_Specification ispec[] = {
- /* FIXME #6842: this 'payment_secret' is currently never initialized
anywhere;
- this is a bug, because the provider should check for it, and not
- accept the request if it is missing! */
GNUNET_JSON_spec_mark_optional (
GNUNET_JSON_spec_fixed_auto ("payment_secret",
&pds[i].payment_secret)),
--
To stop receiving notification emails like this one, please contact
gnunet@gnunet.org.
| [Prev in Thread] |
Current Thread |
[Next in Thread] |
- [taler-anastasis] branch master updated: implement 'optimal' policy generation, but with CPU cap to ensure it is virtually instant even for very complex policies; fixes #6830,
gnunet <=