Pick guards on the order they were sampled (prop310).

Co-authored-by: Florentin Rochet <florentin.rochet@uclouvain.be>

2 files changed, 83 insertions, 30 deletions

diff --git a/src/feature/client/entrynodes.c b/src/feature/client/entrynodes.c
index 3d2abd9205..64005c1e6c 100644
--- a/src/feature/client/entrynodes.c
+++ b/src/feature/client/entrynodes.c
@@ -47,8 +47,7 @@
  * As a persistent ordered list whose elements are taken from the
  * sampled set, we track a CONFIRMED GUARDS LIST.  A guard becomes
  * confirmed when we successfully build a circuit through it, and decide
- * to use that circuit.  We order the guards on this list by the order
- * in which they became confirmed.
+ * to use that circuit.
  *
  * And as a final group, we have an ordered list of PRIMARY GUARDS,
  * whose elements are taken from the filtered set. We prefer
@@ -59,7 +58,7 @@
  *
  * To build circuits, we take a primary guard if possible -- or a
  * reachable filtered confirmed guard if no primary guard is possible --
- * or a random reachable filtered guard otherwise.  If the guard is
+ * or the first (by sampled order) filtered guard otherwise.  If the guard is
  * primary, we can use the circuit immediately on success.  Otherwise,
  * the guard is now "pending" -- we won't use its circuit unless all
  * of the circuits we're trying to build through better guards have
@@ -92,14 +91,18 @@
  * [x] Whenever we remove a guard from the sample, remove it from the primary
  * and confirmed lists.
  *
- * [x] When we make a guard confirmed, update the primary list.
+ * [x] When we make a guard confirmed, update the primary list, and sort them
+ * by sampled order.
  *
  * [x] When we make a guard filtered or unfiltered, update the primary list.
  *
  * [x] When we are about to pick a guard, make sure that the primary list is
  * full.
  *
- * [x] Before calling sample_reachable_filtered_entry_guards(), make sure
+ * [x] When we update the confirmed list, or when we re-build the primary list
+ * and detect a change, we sort those lists by sampled_idx
+ *
+ * [x] Before calling first_reachable_filtered_entry_guard(), make sure
  * that the filtered, primary, and confirmed flags are up-to-date.
  *
  * [x] Call entry_guard_consider_retry every time we are about to check
@@ -172,6 +175,7 @@ static entry_guard_t *get_sampled_guard_by_bridge_addr(guard_selection_t *gs,
                                               const tor_addr_port_t *addrport);
 static int entry_guard_obeys_restriction(const entry_guard_t *guard,
                                          const entry_guard_restriction_t *rst);
+static int compare_guards_by_sampled_idx(const void **a_, const void **b_);
 
 /** Return 0 if we should apply guardfraction information found in the
  *  consensus. A specific consensus can be specified with the
@@ -890,6 +894,7 @@ entry_guard_add_to_sample_impl(guard_selection_t *gs,
   tor_free(guard->sampled_by_version);
   guard->sampled_by_version = tor_strdup(VERSION);
   guard->currently_listed = 1;
+  guard->sampled_idx = gs->next_sampled_idx++;
   guard->confirmed_idx = -1;
 
   /* non-persistent fields */
@@ -1383,7 +1388,7 @@ sampled_guards_prune_obsolete_entries(guard_selection_t *gs,
 
     if (rmv) {
       ++n_changes;
-      SMARTLIST_DEL_CURRENT(gs->sampled_entry_guards, guard);
+      SMARTLIST_DEL_CURRENT_KEEPORDER(gs->sampled_entry_guards, guard);
       remove_guard_from_confirmed_and_primary_lists(gs, guard);
       entry_guard_free(guard);
     }
@@ -1707,7 +1712,7 @@ entry_guards_update_filtered_sets(guard_selection_t *gs)
 }
 
 /**
- * Return a random guard from the reachable filtered sample guards
+ * Return the first sampled guard from the reachable filtered sample guards
  * in <b>gs</b>, subject to the exclusion rules listed in <b>flags</b>.
  * Return NULL if no such guard can be found.
  *
@@ -1718,7 +1723,7 @@ entry_guards_update_filtered_sets(guard_selection_t *gs)
  * violate it.
  **/
 STATIC entry_guard_t *
-sample_reachable_filtered_entry_guards(guard_selection_t *gs,
+first_reachable_filtered_entry_guard(guard_selection_t *gs,
                                        const entry_guard_restriction_t *rst,
                                        unsigned flags)
 {
@@ -1771,7 +1776,17 @@ sample_reachable_filtered_entry_guards(guard_selection_t *gs,
            flags, smartlist_len(reachable_filtered_sample));
 
   if (smartlist_len(reachable_filtered_sample)) {
-    result = smartlist_choose(reachable_filtered_sample);
+    /**
+     * Get the first guard of the filtered set builds from
+     * sampled_entry_guards. Proposal 310 suggests this design to overcome
+     * performance and security issues linked to the previous selection
+     * method. The guard selected here should be filtered out if this function
+     * is called again in the same context. I.e., if we filter guards to add
+     * them into some list X, then the guards from list X will be filtered out
+     * when this function is called again. Hence it requires setting exclude
+     * flags in a appropriate way (depending of the context of the caller).
+     */
+    result = smartlist_get(reachable_filtered_sample, 0);
     log_info(LD_GUARD, "  (Selected %s.)",
              result ? entry_guard_describe(result) : "<null>");
   }
@@ -1780,10 +1795,6 @@ sample_reachable_filtered_entry_guards(guard_selection_t *gs,
   return result;
 }
 
-/**
- * Helper: compare two entry_guard_t by their confirmed_idx values.
- * Used to sort the confirmed list.
- */
 static int
 compare_guards_by_confirmed_idx(const void **a_, const void **b_)
 {
@@ -1795,6 +1806,21 @@ compare_guards_by_confirmed_idx(const void **a_, const void **b_)
   else
     return 0;
 }
+/**
+ * Helper: compare two entry_guard_t by their sampled_idx values.
+ * Used to sort the sampled list
+ */
+static int
+compare_guards_by_sampled_idx(const void **a_, const void **b_)
+{
+  const entry_guard_t *a = *a_, *b = *b_;
+  if (a->sampled_idx < b->sampled_idx)
+    return -1;
+  else if (a->sampled_idx > b->sampled_idx)
+    return 1;
+  else
+    return 0;
+}
 
 /**
  * Find the confirmed guards from among the sampled guards in <b>gs</b>,
@@ -1811,7 +1837,7 @@ entry_guards_update_confirmed(guard_selection_t *gs)
   } SMARTLIST_FOREACH_END(guard);
 
   smartlist_sort(gs->confirmed_entry_guards, compare_guards_by_confirmed_idx);
-
+  /** Needed to keep a dense array of confirmed_idx */
   int any_changed = 0;
   SMARTLIST_FOREACH_BEGIN(gs->confirmed_entry_guards, entry_guard_t *, guard) {
     if (guard->confirmed_idx != guard_sl_idx) {
@@ -1821,6 +1847,8 @@ entry_guards_update_confirmed(guard_selection_t *gs)
   } SMARTLIST_FOREACH_END(guard);
 
   gs->next_confirmed_idx = smartlist_len(gs->confirmed_entry_guards);
+  // We need the confirmed list to always be give guards in sampled order
+  smartlist_sort(gs->confirmed_entry_guards, compare_guards_by_sampled_idx);
 
   if (any_changed) {
     entry_guards_changed_for_guard_selection(gs);
@@ -1849,6 +1877,9 @@ make_guard_confirmed(guard_selection_t *gs, entry_guard_t *guard)
 
   guard->confirmed_idx = gs->next_confirmed_idx++;
   smartlist_add(gs->confirmed_entry_guards, guard);
+  /** The confirmation ordering might not be the sample ording. We need to
+   * reorder */
+  smartlist_sort(gs->confirmed_entry_guards, compare_guards_by_sampled_idx);
 
   // This confirmed guard might kick something else out of the primary
   // guards.
@@ -1912,7 +1943,7 @@ entry_guards_update_primary(guard_selection_t *gs)
 
   /* Finally, fill out the list with sampled guards. */
   while (smartlist_len(new_primary_guards) < N_PRIMARY_GUARDS) {
-    entry_guard_t *guard = sample_reachable_filtered_entry_guards(gs, NULL,
+    entry_guard_t *guard = first_reachable_filtered_entry_guard(gs, NULL,
                                             SAMPLE_EXCLUDE_CONFIRMED|
                                             SAMPLE_EXCLUDE_PRIMARY|
                                             SAMPLE_NO_UPDATE_PRIMARY);
@@ -1943,6 +1974,7 @@ entry_guards_update_primary(guard_selection_t *gs)
                g->confirmed_idx >= 0 ? " (confirmed)" : "",
                g->is_filtered_guard ? "" : " (excluded by filter)");
     } SMARTLIST_FOREACH_END(g);
+    smartlist_sort(new_primary_guards, compare_guards_by_sampled_idx);
   }
 
   smartlist_free(old_primary_guards);
@@ -2055,10 +2087,15 @@ select_primary_guard_for_circuit(guard_selection_t *gs,
 
   SMARTLIST_FOREACH_BEGIN(gs->primary_entry_guards, entry_guard_t *, guard) {
     entry_guard_consider_retry(guard);
-    if (! entry_guard_obeys_restriction(guard, rst))
+    if (!entry_guard_obeys_restriction(guard, rst)) {
+      log_info(LD_GUARD, "Entry guard %s doesn't obey restriction, we test the"
+          " next one", entry_guard_describe(guard));
       continue;
+    }
     if (guard->is_reachable != GUARD_REACHABLE_NO) {
       if (need_descriptor && !guard_has_descriptor(guard)) {
+        log_info(LD_GUARD, "Guard %s does not have a descriptor",
+            entry_guard_describe(guard));
         continue;
       }
       *state_out = GUARD_CIRC_STATE_USABLE_ON_COMPLETION;
@@ -2071,9 +2108,11 @@ select_primary_guard_for_circuit(guard_selection_t *gs,
 
   if (smartlist_len(usable_primary_guards)) {
     chosen_guard = smartlist_choose(usable_primary_guards);
+    log_info(LD_GUARD,
+        "Selected primary guard %s for circuit from a list size of %d.",
+        entry_guard_describe(chosen_guard),
+        smartlist_len(usable_primary_guards));
     smartlist_free(usable_primary_guards);
-    log_info(LD_GUARD, "Selected primary guard %s for circuit.",
-             entry_guard_describe(chosen_guard));
   }
 
   smartlist_free(usable_primary_guards);
@@ -2118,10 +2157,10 @@ select_confirmed_guard_for_circuit(guard_selection_t *gs,
 }
 
 /**
- * For use with a circuit, pick a confirmed usable filtered guard
- * at random. Update the <b>last_tried_to_connect</b> time and the
- * <b>is_pending</b> fields of the guard as appropriate. Set <b>state_out</b>
- * to the new guard-state of the circuit.
+ * For use with a circuit, pick a usable filtered guard. Update the
+ * <b>last_tried_to_connect</b> time and the <b>is_pending</b> fields of the
+ * guard as appropriate. Set <b>state_out</b> to the new guard-state of the
+ * circuit.
  */
 static entry_guard_t *
 select_filtered_guard_for_circuit(guard_selection_t *gs,
@@ -2134,7 +2173,7 @@ select_filtered_guard_for_circuit(guard_selection_t *gs,
   unsigned flags = 0;
   if (need_descriptor)
     flags |= SAMPLE_EXCLUDE_NO_DESCRIPTOR;
-  chosen_guard = sample_reachable_filtered_entry_guards(gs,
+  chosen_guard = first_reachable_filtered_entry_guard(gs,
                                                  rst,
                                                  SAMPLE_EXCLUDE_CONFIRMED |
                                                  SAMPLE_EXCLUDE_PRIMARY |
@@ -2148,7 +2187,7 @@ select_filtered_guard_for_circuit(guard_selection_t *gs,
   chosen_guard->last_tried_to_connect = approx_time();
   *state_out = GUARD_CIRC_STATE_USABLE_IF_NO_BETTER_GUARD;
   log_info(LD_GUARD, "No primary or confirmed guards available. Selected "
-           "random guard %s for circuit. Will try other guards before "
+           "guard %s for circuit. Will try other guards before "
            "using this circuit.",
            entry_guard_describe(chosen_guard));
   return chosen_guard;
@@ -2189,8 +2228,8 @@ select_entry_guard_for_circuit(guard_selection_t *gs,
   if (chosen_guard)
     return chosen_guard;
 
-  /* "Otherwise, if there is no such entry, select a member at
-      random from {USABLE_FILTERED_GUARDS}." */
+  /* "Otherwise, if there is no such entry, select a member
+   * {USABLE_FILTERED_GUARDS} following the sample ordering" */
   chosen_guard = select_filtered_guard_for_circuit(gs, usage, rst, state_out);
 
   if (chosen_guard == NULL) {
diff --git a/src/feature/client/entrynodes.h b/src/feature/client/entrynodes.h
index 6eede2c8d4..a478b92d75 100644
--- a/src/feature/client/entrynodes.h
+++ b/src/feature/client/entrynodes.h
@@ -117,6 +117,13 @@ struct entry_guard_t {
    * confirmed guard. */
   time_t confirmed_on_date; /* 0 if not confirmed */
   /**
+   * In what order was this guard sampled? Guards with
+   * lower indices appear earlier on the sampled list, the confirmed list and
+   * the primary list as a result of Prop 310
+   */
+  int sampled_idx;
+
+  /**
    * In what order was this guard confirmed? Guards with lower indices
    * appear earlier on the confirmed list.  If the confirmed list is compacted,
    * this field corresponds to the index of this guard on the confirmed list.
@@ -242,8 +249,9 @@ struct guard_selection_t {
    * Ordered list (from highest to lowest priority) of guards that we
    * have successfully contacted and decided to use. Every member of
    * this list is a member of sampled_entry_guards. Every member should
-   * have confirmed_on_date set, and have confirmed_idx greater than
-   * any earlier member of the list.
+   * have confirmed_on_date set.
+   * The ordering of the list should be by sampled idx. The reasoning behind
+   * it is linked to Proposal 310.
    *
    * This list is persistent. It is a subset of the elements in
    * sampled_entry_guards, and its pointers point to elements of
@@ -271,6 +279,12 @@ struct guard_selection_t {
    * confirmed_entry_guards receive? */
   int next_confirmed_idx;
 
+  /** What sampled_idx value should the next-added member of
+   * sampled_entry_guards receive? This should follow the size of the sampled
+   * list until sampled relays get pruned for some reason
+   */
+  int next_sampled_idx;
+
 };
 
 struct entry_guard_handle_t;
@@ -523,7 +537,7 @@ STATIC void entry_guard_free_(entry_guard_t *e);
 STATIC void entry_guards_update_filtered_sets(guard_selection_t *gs);
 STATIC int entry_guards_all_primary_guards_are_down(guard_selection_t *gs);
 /**
- * @name Flags for sample_reachable_filtered_entry_guards()
+ * @name Flags for first_reachable_filtered_entry_guard()
  */
 /**@{*/
 #define SAMPLE_EXCLUDE_CONFIRMED   (1u<<0)
@@ -532,7 +546,7 @@ STATIC int entry_guards_all_primary_guards_are_down(guard_selection_t *gs);
 #define SAMPLE_NO_UPDATE_PRIMARY   (1u<<3)
 #define SAMPLE_EXCLUDE_NO_DESCRIPTOR (1u<<4)
 /**@}*/
-STATIC entry_guard_t *sample_reachable_filtered_entry_guards(
+STATIC entry_guard_t *first_reachable_filtered_entry_guard(
                                     guard_selection_t *gs,
                                     const entry_guard_restriction_t *rst,
                                     unsigned flags);