Merge branch 'maint-0.4.4'

5 files changed, 326 insertions, 138 deletions

diff --git a/changes/ticket32088 b/changes/ticket32088
new file mode 100644
index 0000000000..0d4fc74754
--- /dev/null
+++ b/changes/ticket32088
@@ -0,0 +1,13 @@
+  o Major features (Proposal 310, performance + security):
+    - Implements Proposal 310 - Bandaid on guard selection.
+      Proposal 310 solves a load-balancing issue within Prop271 which strongly
+      impact experimental research with Shadow.
+      Security improvement: Proposal 310 prevents any newly Guard relay to
+      have a chance to get into the primary list of older Tor clients,
+      except if the N first sampled guards of these clients are unreachable.
+      Implements recommendation from 32088.
+      
+      Proposal 310 is linked to the CLAPS project researching optimal
+      client location-aware path selections. This project is a collaboration
+      between the UCLouvain Crypto Group, the U.S. Naval Research Laboratory and
+      Princeton University.
diff --git a/scripts/maint/practracker/exceptions.txt b/scripts/maint/practracker/exceptions.txt
index 9444dbdb66..154f43ee1f 100644
--- a/scripts/maint/practracker/exceptions.txt
+++ b/scripts/maint/practracker/exceptions.txt
@@ -182,10 +182,10 @@ problem function-size /src/feature/client/addressmap.c:addressmap_rewrite() 109
 problem function-size /src/feature/client/bridges.c:rewrite_node_address_for_bridge() 125
 problem function-size /src/feature/client/circpathbias.c:pathbias_measure_close_rate() 108
 problem function-size /src/feature/client/dnsserv.c:evdns_server_callback() 153
-problem file-size /src/feature/client/entrynodes.c 3827
+problem file-size /src/feature/client/entrynodes.c 4000
 problem function-size /src/feature/client/entrynodes.c:entry_guards_upgrade_waiting_circuits() 155
 problem function-size /src/feature/client/entrynodes.c:entry_guard_parse_from_state() 246
-problem file-size /src/feature/client/entrynodes.h 639
+problem file-size /src/feature/client/entrynodes.h 700
 problem function-size /src/feature/client/transports.c:handle_proxy_line() 108
 problem function-size /src/feature/client/transports.c:parse_method_line_helper() 110
 problem function-size /src/feature/client/transports.c:create_managed_proxy_environment() 111
diff --git a/src/feature/client/entrynodes.c b/src/feature/client/entrynodes.c
index ded7db969a..2a000a47b6 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) {
@@ -2773,10 +2812,12 @@ entry_guards_update_all(guard_selection_t *gs)
 
 /**
  * Return a newly allocated string for encoding the persistent parts of
- * <b>guard</b> to the state file.
+ * <b>guard</b> to the state file. <b>dense_sampled_idx</b> refers to the
+ * sampled_idx made dense for this <b>guard</b>. Encoding all guards should
+ * lead to a dense array of sampled_idx in the state file.
  */
 STATIC char *
-entry_guard_encode_for_state(entry_guard_t *guard)
+entry_guard_encode_for_state(entry_guard_t *guard, int dense_sampled_idx)
 {
   /*
    * The meta-format we use is K=V K=V K=V... where K can be any
@@ -2805,7 +2846,8 @@ entry_guard_encode_for_state(entry_guard_t *guard)
 
   format_iso_time_nospace(tbuf, guard->sampled_on_date);
   smartlist_add_asprintf(result, "sampled_on=%s", tbuf);
-
+  // Replacing the sampled_idx by dense array
+  smartlist_add_asprintf(result, "sampled_idx=%d", dense_sampled_idx);
   if (guard->sampled_by_version) {
     smartlist_add_asprintf(result, "sampled_by=%s",
                            guard->sampled_by_version);
@@ -2861,6 +2903,78 @@ entry_guard_encode_for_state(entry_guard_t *guard)
 }
 
 /**
+ * Extract key=val from the state string <b>s</b> and duplicate the value to
+ * some string target declared in entry_guard_parse_from_state
+ */
+static void
+parse_from_state_set_vals(const char *s, smartlist_t *entries, smartlist_t
+    *extra, strmap_t *vals)
+{
+    smartlist_split_string(entries, s, " ",
+                           SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
+
+    SMARTLIST_FOREACH_BEGIN(entries, char *, entry) {
+      const char *eq = strchr(entry, '=');
+      if (!eq) {
+        smartlist_add(extra, entry);
+        continue;
+      }
+      char *key = tor_strndup(entry, eq-entry);
+      char **target = strmap_get(vals, key);
+      if (target == NULL || *target != NULL) {
+        /* unrecognized or already set */
+        smartlist_add(extra, entry);
+        tor_free(key);
+        continue;
+      }
+
+      *target = tor_strdup(eq+1);
+      tor_free(key);
+      tor_free(entry);
+    } SMARTLIST_FOREACH_END(entry);
+}
+
+/**
+ * Handle part of the parsing state file logic, focused on time related things
+ */
+static void
+parse_from_state_handle_time(entry_guard_t *guard, char *sampled_on, char
+    *unlisted_since, char *confirmed_on)
+{
+#define HANDLE_TIME(field) do {                                 \
+    if (field) {                                                \
+      int r = parse_iso_time_nospace(field, &field ## _time);   \
+      if (r < 0) {                                              \
+        log_warn(LD_CIRC, "Unable to parse %s %s from guard",   \
+                 #field, escaped(field));                       \
+        field##_time = -1;                                      \
+      }                                                         \
+    }                                                           \
+  } while (0)
+
+  time_t sampled_on_time = 0;
+  time_t unlisted_since_time = 0;
+  time_t confirmed_on_time = 0;
+
+  HANDLE_TIME(sampled_on);
+  HANDLE_TIME(unlisted_since);
+  HANDLE_TIME(confirmed_on);
+
+  if (sampled_on_time <= 0)
+    sampled_on_time = approx_time();
+  if (unlisted_since_time < 0)
+    unlisted_since_time = 0;
+  if (confirmed_on_time < 0)
+    confirmed_on_time = 0;
+
+  #undef HANDLE_TIME
+
+  guard->sampled_on_date = sampled_on_time;
+  guard->unlisted_since_date = unlisted_since_time;
+  guard->confirmed_on_date = confirmed_on_time;
+}
+
+/**
  * Given a string generated by entry_guard_encode_for_state(), parse it
  * (if possible) and return an entry_guard_t object for it.  Return NULL
  * on complete failure.
@@ -2876,6 +2990,7 @@ entry_guard_parse_from_state(const char *s)
   char *rsa_id = NULL;
   char *nickname = NULL;
   char *sampled_on = NULL;
+  char *sampled_idx = NULL;
   char *sampled_by = NULL;
   char *unlisted_since = NULL;
   char *listed  = NULL;
@@ -2892,6 +3007,7 @@ entry_guard_parse_from_state(const char *s)
   char *pb_collapsed_circuits = NULL;
   char *pb_unusable_circuits = NULL;
   char *pb_timeouts = NULL;
+  int invalid_sampled_idx = get_max_sample_size_absolute();
 
   /* Split up the entries.  Put the ones we know about in strings and the
    * rest in "extra". */
@@ -2905,6 +3021,7 @@ entry_guard_parse_from_state(const char *s)
     FIELD(rsa_id);
     FIELD(nickname);
     FIELD(sampled_on);
+    FIELD(sampled_idx);
     FIELD(sampled_by);
     FIELD(unlisted_since);
     FIELD(listed);
@@ -2920,29 +3037,8 @@ entry_guard_parse_from_state(const char *s)
     FIELD(pb_unusable_circuits);
     FIELD(pb_timeouts);
 #undef FIELD
-
-    smartlist_split_string(entries, s, " ",
-                           SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
-
-    SMARTLIST_FOREACH_BEGIN(entries, char *, entry) {
-      const char *eq = strchr(entry, '=');
-      if (!eq) {
-        smartlist_add(extra, entry);
-        continue;
-      }
-      char *key = tor_strndup(entry, eq-entry);
-      char **target = strmap_get(vals, key);
-      if (target == NULL || *target != NULL) {
-        /* unrecognized or already set */
-        smartlist_add(extra, entry);
-        tor_free(key);
-        continue;
-      }
-
-      *target = tor_strdup(eq+1);
-      tor_free(key);
-      tor_free(entry);
-    } SMARTLIST_FOREACH_END(entry);
+    /* Extract from s the key=val that we recognize, put the others in extra*/
+    parse_from_state_set_vals(s, entries, extra, vals);
 
     smartlist_free(entries);
     strmap_free(vals, NULL);
@@ -2990,43 +3086,12 @@ entry_guard_parse_from_state(const char *s)
   }
 
   /* Process the various time fields. */
-
-#define HANDLE_TIME(field) do {                                 \
-    if (field) {                                                \
-      int r = parse_iso_time_nospace(field, &field ## _time);   \
-      if (r < 0) {                                              \
-        log_warn(LD_CIRC, "Unable to parse %s %s from guard",   \
-                 #field, escaped(field));                       \
-        field##_time = -1;                                      \
-      }                                                         \
-    }                                                           \
-  } while (0)
-
-  time_t sampled_on_time = 0;
-  time_t unlisted_since_time = 0;
-  time_t confirmed_on_time = 0;
-
-  HANDLE_TIME(sampled_on);
-  HANDLE_TIME(unlisted_since);
-  HANDLE_TIME(confirmed_on);
-
-  if (sampled_on_time <= 0)
-    sampled_on_time = approx_time();
-  if (unlisted_since_time < 0)
-    unlisted_since_time = 0;
-  if (confirmed_on_time < 0)
-    confirmed_on_time = 0;
-
-  #undef HANDLE_TIME
-
-  guard->sampled_on_date = sampled_on_time;
-  guard->unlisted_since_date = unlisted_since_time;
-  guard->confirmed_on_date = confirmed_on_time;
+  parse_from_state_handle_time(guard, sampled_on, unlisted_since,
+      confirmed_on);
 
   /* Take sampled_by_version verbatim. */
   guard->sampled_by_version = sampled_by;
   sampled_by = NULL; /* prevent free */
-
   /* Listed is a boolean */
   if (listed && strcmp(listed, "0"))
     guard->currently_listed = 1;
@@ -3044,6 +3109,29 @@ entry_guard_parse_from_state(const char *s)
     }
   }
 
+  if (sampled_idx) {
+    int ok = 1;
+    long idx = tor_parse_long(sampled_idx, 10, 0, INT_MAX, &ok, NULL);
+    if (!ok) {
+      log_warn(LD_GUARD, "Guard has invalid sampled_idx %s",
+          escaped(sampled_idx));
+      /* set it to a idx higher than the max sample size */
+      guard->sampled_idx = invalid_sampled_idx++;
+    } else {
+      guard->sampled_idx = (int)idx;
+    }
+  } else if (confirmed_idx) {
+    /* This state has been written by an older Tor version which did not have
+     * sample ordering  */
+
+    guard->sampled_idx = guard->confirmed_idx;
+  } else {
+    log_warn(LD_GUARD, "The state file seems to be into a status that could"
+        " yield to weird entry node selection: we're missing both a"
+        " sampled_idx and a confirmed_idx.");
+    guard->sampled_idx = invalid_sampled_idx++;
+  }
+
   /* Anything we didn't recognize gets crammed together */
   if (smartlist_len(extra) > 0) {
     guard->extra_state_fields = smartlist_join_strings(extra, " ", 0, NULL);
@@ -3098,6 +3186,7 @@ entry_guard_parse_from_state(const char *s)
   tor_free(listed);
   tor_free(confirmed_on);
   tor_free(confirmed_idx);
+  tor_free(sampled_idx);
   tor_free(bridge_addr);
   tor_free(pb_use_attempts);
   tor_free(pb_use_successes);
@@ -3127,13 +3216,15 @@ entry_guards_update_guards_in_state(or_state_t *state)
   config_line_t **nextline = &lines;
 
   SMARTLIST_FOREACH_BEGIN(guard_contexts, guard_selection_t *, gs) {
+    int i = 0;
     SMARTLIST_FOREACH_BEGIN(gs->sampled_entry_guards, entry_guard_t *, guard) {
       if (guard->is_persistent == 0)
         continue;
       *nextline = tor_malloc_zero(sizeof(config_line_t));
       (*nextline)->key = tor_strdup("Guard");
-      (*nextline)->value = entry_guard_encode_for_state(guard);
+      (*nextline)->value = entry_guard_encode_for_state(guard, i);
       nextline = &(*nextline)->next;
+      i++;
     } SMARTLIST_FOREACH_END(guard);
   } SMARTLIST_FOREACH_END(gs);
 
@@ -3186,6 +3277,14 @@ entry_guards_load_guards_from_state(or_state_t *state, int set)
       tor_assert(gs);
       smartlist_add(gs->sampled_entry_guards, guard);
       guard->in_selection = gs;
+      /* Recompute the next_sampled_id from the state. We do not assume that
+       * sampled guards appear in the correct order within the file, and we
+       * need to know what would be the next sampled idx to give to any
+       * new sampled guard (i.e., max of guard->sampled_idx + 1)*/
+      if (gs->next_sampled_idx <= guard->sampled_idx) {
+        gs->next_sampled_idx = guard->sampled_idx + 1;
+      }
+
     } else {
       entry_guard_free(guard);
     }
@@ -3193,6 +3292,10 @@ entry_guards_load_guards_from_state(or_state_t *state, int set)
 
   if (set) {
     SMARTLIST_FOREACH_BEGIN(guard_contexts, guard_selection_t *, gs) {
+      /** Guards should be in sample order within the file, but it is maybe
+       * better NOT to assume that. Let's order them before updating lists
+       */
+      smartlist_sort(gs->sampled_entry_guards, compare_guards_by_sampled_idx);
       entry_guards_update_all(gs);
     } SMARTLIST_FOREACH_END(gs);
   }
diff --git a/src/feature/client/entrynodes.h b/src/feature/client/entrynodes.h
index 6eede2c8d4..4b236dc80c 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;
@@ -515,7 +529,8 @@ MOCK_DECL(STATIC circuit_guard_state_t *,
 STATIC entry_guard_t *entry_guard_add_to_sample(guard_selection_t *gs,
                                                 const node_t *node);
 STATIC entry_guard_t *entry_guards_expand_sample(guard_selection_t *gs);
-STATIC char *entry_guard_encode_for_state(entry_guard_t *guard);
+STATIC char *entry_guard_encode_for_state(entry_guard_t *guard, int
+    dense_sampled_index);
 STATIC entry_guard_t *entry_guard_parse_from_state(const char *s);
 #define entry_guard_free(e) \
   FREE_AND_NULL(entry_guard_t, entry_guard_free_, (e))
@@ -523,7 +538,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 +547,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);
diff --git a/src/test/test_entrynodes.c b/src/test/test_entrynodes.c
index 12b4fcde3c..5ddd1a3db0 100644
--- a/src/test/test_entrynodes.c
+++ b/src/test/test_entrynodes.c
@@ -390,12 +390,13 @@ test_entry_guard_encode_for_state_minimal(void *arg)
   eg->confirmed_idx = -1;
 
   char *s = NULL;
-  s = entry_guard_encode_for_state(eg);
+  s = entry_guard_encode_for_state(eg, 0);
 
   tt_str_op(s, OP_EQ,
             "in=wubwub "
             "rsa_id=706C75727079666C75727079736C75727079646F "
             "sampled_on=2016-11-14T00:00:00 "
+            "sampled_idx=0 "
             "listed=0");
 
  done:
@@ -421,10 +422,11 @@ test_entry_guard_encode_for_state_maximal(void *arg)
   eg->currently_listed = 1;
   eg->confirmed_on_date = 1479081690;
   eg->confirmed_idx = 333;
+  eg->sampled_idx = 42;
   eg->extra_state_fields = tor_strdup("and the green grass grew all around");
 
   char *s = NULL;
-  s = entry_guard_encode_for_state(eg);
+  s = entry_guard_encode_for_state(eg, 0);
 
   tt_str_op(s, OP_EQ,
             "in=default "
@@ -432,6 +434,7 @@ test_entry_guard_encode_for_state_maximal(void *arg)
             "bridge_addr=8.8.4.4:9999 "
             "nickname=Fred "
             "sampled_on=2016-11-14T00:00:00 "
+            "sampled_idx=0 "
             "sampled_by=1.2.3 "
             "unlisted_since=2016-11-14T00:00:45 "
             "listed=1 "
@@ -621,39 +624,47 @@ test_entry_guard_parse_from_state_full(void *arg)
   const char STATE[] =
   "Guard in=default rsa_id=214F44BD5B638E8C817D47FF7C97397790BF0345 "
     "nickname=TotallyNinja sampled_on=2016-11-12T19:32:49 "
+    "sampled_idx=0 "
     "sampled_by=0.3.0.0-alpha-dev "
     "listed=1\n"
   "Guard in=default rsa_id=052900AB0EA3ED54BAB84AE8A99E74E8693CE2B2 "
     "nickname=5OfNovember sampled_on=2016-11-20T04:32:05 "
+    "sampled_idx=1 "
     "sampled_by=0.3.0.0-alpha-dev "
     "listed=1 confirmed_on=2016-11-22T08:13:28 confirmed_idx=0 "
     "pb_circ_attempts=4.000000 pb_circ_successes=2.000000 "
     "pb_successful_circuits_closed=2.000000\n"
   "Guard in=default rsa_id=7B700C0C207EBD0002E00F499BE265519AC3C25A "
     "nickname=dc6jgk11 sampled_on=2016-11-28T11:50:13 "
+    "sampled_idx=2 "
     "sampled_by=0.3.0.0-alpha-dev "
     "listed=1 confirmed_on=2016-11-24T08:45:30 confirmed_idx=4 "
     "pb_circ_attempts=5.000000 pb_circ_successes=5.000000 "
     "pb_successful_circuits_closed=5.000000\n"
   "Guard in=wobblesome rsa_id=7B700C0C207EBD0002E00F499BE265519AC3C25A "
     "nickname=dc6jgk11 sampled_on=2016-11-28T11:50:13 "
+    "sampled_idx=0 "
     "sampled_by=0.3.0.0-alpha-dev "
     "listed=1\n"
   "Guard in=default rsa_id=E9025AD60D86875D5F11548D536CC6AF60F0EF5E "
     "nickname=maibrunn sampled_on=2016-11-25T22:36:38 "
+    "sampled_idx=3 "
     "sampled_by=0.3.0.0-alpha-dev listed=1\n"
   "Guard in=default rsa_id=DCD30B90BA3A792DA75DC54A327EF353FB84C38E "
     "nickname=Unnamed sampled_on=2016-11-25T14:34:00 "
+    "sampled_idx=10 "
     "sampled_by=0.3.0.0-alpha-dev listed=1\n"
   "Guard in=bridges rsa_id=8FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF2E "
     "bridge_addr=24.1.1.1:443 sampled_on=2016-11-25T06:44:14 "
+    "sampled_idx=0 "
     "sampled_by=0.3.0.0-alpha-dev listed=1 "
     "confirmed_on=2016-11-29T10:36:06 confirmed_idx=0 "
     "pb_circ_attempts=8.000000 pb_circ_successes=8.000000 "
     "pb_successful_circuits_closed=13.000000\n"
   "Guard in=bridges rsa_id=5800000000000000000000000000000000000000 "
     "bridge_addr=37.218.246.143:28366 "
-    "sampled_on=2016-11-18T15:07:34 sampled_by=0.3.0.0-alpha-dev listed=1\n";
+    "sampled_on=2016-11-18T15:07:34 sampled_idx=1 "
+    "sampled_by=0.3.0.0-alpha-dev listed=1\n";
 
   config_line_t *lines = NULL;
   or_state_t *state = tor_malloc_zero(sizeof(or_state_t));
@@ -729,35 +740,42 @@ test_entry_guard_parse_from_state_full(void *arg)
   tt_str_op(joined, OP_EQ,
   "Guard in=default rsa_id=052900AB0EA3ED54BAB84AE8A99E74E8693CE2B2 "
     "nickname=5OfNovember sampled_on=2016-11-20T04:32:05 "
+    "sampled_idx=0 "
     "sampled_by=0.3.0.0-alpha-dev "
     "listed=1 confirmed_on=2016-11-22T08:13:28 confirmed_idx=0 "
     "pb_circ_attempts=4.000000 pb_circ_successes=2.000000 "
     "pb_successful_circuits_closed=2.000000\n"
   "Guard in=default rsa_id=7B700C0C207EBD0002E00F499BE265519AC3C25A "
     "nickname=dc6jgk11 sampled_on=2016-11-28T11:50:13 "
+    "sampled_idx=1 "
     "sampled_by=0.3.0.0-alpha-dev "
     "listed=1 confirmed_on=2016-11-24T08:45:30 confirmed_idx=1 "
     "pb_circ_attempts=5.000000 pb_circ_successes=5.000000 "
     "pb_successful_circuits_closed=5.000000\n"
   "Guard in=default rsa_id=E9025AD60D86875D5F11548D536CC6AF60F0EF5E "
     "nickname=maibrunn sampled_on=2016-11-25T22:36:38 "
+    "sampled_idx=2 "
     "sampled_by=0.3.0.0-alpha-dev listed=1\n"
   "Guard in=default rsa_id=DCD30B90BA3A792DA75DC54A327EF353FB84C38E "
     "nickname=Unnamed sampled_on=2016-11-25T14:34:00 "
+    "sampled_idx=3 "
     "sampled_by=0.3.0.0-alpha-dev listed=1\n"
   "Guard in=wobblesome rsa_id=7B700C0C207EBD0002E00F499BE265519AC3C25A "
     "nickname=dc6jgk11 sampled_on=2016-11-28T11:50:13 "
+    "sampled_idx=0 "
     "sampled_by=0.3.0.0-alpha-dev "
     "listed=1\n"
   "Guard in=bridges rsa_id=8FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF2E "
     "bridge_addr=24.1.1.1:443 sampled_on=2016-11-25T06:44:14 "
+    "sampled_idx=0 "
     "sampled_by=0.3.0.0-alpha-dev listed=1 "
     "confirmed_on=2016-11-29T10:36:06 confirmed_idx=0 "
     "pb_circ_attempts=8.000000 pb_circ_successes=8.000000 "
     "pb_successful_circuits_closed=13.000000\n"
   "Guard in=bridges rsa_id=5800000000000000000000000000000000000000 "
     "bridge_addr=37.218.246.143:28366 "
-    "sampled_on=2016-11-18T15:07:34 sampled_by=0.3.0.0-alpha-dev listed=1\n");
+    "sampled_on=2016-11-18T15:07:34 sampled_idx=1 "
+    "sampled_by=0.3.0.0-alpha-dev listed=1\n");
 
  done:
   config_free_lines(lines);
@@ -1461,8 +1479,8 @@ test_entry_guard_confirming_guards(void *arg)
   tt_i64_op(g1->confirmed_on_date, OP_EQ, start+10);
   tt_i64_op(g2->confirmed_on_date, OP_EQ, start);
   tt_i64_op(g3->confirmed_on_date, OP_EQ, start+10);
-  tt_ptr_op(smartlist_get(gs->confirmed_entry_guards, 0), OP_EQ, g2);
-  tt_ptr_op(smartlist_get(gs->confirmed_entry_guards, 1), OP_EQ, g1);
+  tt_ptr_op(smartlist_get(gs->confirmed_entry_guards, 0), OP_EQ, g1);
+  tt_ptr_op(smartlist_get(gs->confirmed_entry_guards, 1), OP_EQ, g2);
   tt_ptr_op(smartlist_get(gs->confirmed_entry_guards, 2), OP_EQ, g3);
 
   /* Now make sure we can regenerate the confirmed_entry_guards list. */
@@ -1474,8 +1492,8 @@ test_entry_guard_confirming_guards(void *arg)
   tt_int_op(g1->confirmed_idx, OP_EQ, 1);
   tt_int_op(g2->confirmed_idx, OP_EQ, 0);
   tt_int_op(g3->confirmed_idx, OP_EQ, 2);
-  tt_ptr_op(smartlist_get(gs->confirmed_entry_guards, 0), OP_EQ, g2);
-  tt_ptr_op(smartlist_get(gs->confirmed_entry_guards, 1), OP_EQ, g1);
+  tt_ptr_op(smartlist_get(gs->confirmed_entry_guards, 0), OP_EQ, g1);
+  tt_ptr_op(smartlist_get(gs->confirmed_entry_guards, 1), OP_EQ, g2);
   tt_ptr_op(smartlist_get(gs->confirmed_entry_guards, 2), OP_EQ, g3);
 
   /* Now make sure we can regenerate the confirmed_entry_guards list if
@@ -1492,9 +1510,9 @@ test_entry_guard_confirming_guards(void *arg)
   g1 = smartlist_get(gs->confirmed_entry_guards, 0);
   g2 = smartlist_get(gs->confirmed_entry_guards, 1);
   g3 = smartlist_get(gs->confirmed_entry_guards, 2);
-  tt_int_op(g1->confirmed_idx, OP_EQ, 0);
-  tt_int_op(g2->confirmed_idx, OP_EQ, 1);
-  tt_int_op(g3->confirmed_idx, OP_EQ, 2);
+  tt_int_op(g1->sampled_idx, OP_EQ, 0);
+  tt_int_op(g2->sampled_idx, OP_EQ, 1);
+  tt_int_op(g3->sampled_idx, OP_EQ, 8);
   tt_assert(g1 != g2);
   tt_assert(g1 != g3);
   tt_assert(g2 != g3);
@@ -1510,9 +1528,6 @@ test_entry_guard_sample_reachable_filtered(void *arg)
   (void)arg;
   guard_selection_t *gs = guard_selection_new("default", GS_TYPE_NORMAL);
   entry_guards_expand_sample(gs);
-  const int N = 10000;
-  bitarray_t *selected = NULL;
-  int i, j;
 
   /* We've got a sampled list now; let's make one non-usable-filtered; some
    * confirmed, some primary, some pending.
@@ -1547,32 +1562,21 @@ test_entry_guard_sample_reachable_filtered(void *arg)
     { SAMPLE_EXCLUDE_PENDING, 0 },
     { -1, -1},
   };
-
+  int j;
   for (j = 0; tests[j].flag >= 0; ++j) {
-    selected = bitarray_init_zero(n_guards);
     const int excluded_flags = tests[j].flag;
     const int excluded_idx = tests[j].idx;
-    for (i = 0; i < N; ++i) {
-      g = sample_reachable_filtered_entry_guards(gs, NULL, excluded_flags);
-      tor_assert(g);
-      int pos = smartlist_pos(gs->sampled_entry_guards, g);
-      tt_int_op(smartlist_len(gs->sampled_entry_guards), OP_EQ, n_guards);
-      tt_int_op(pos, OP_GE, 0);
-      tt_int_op(pos, OP_LT, n_guards);
-      bitarray_set(selected, pos);
-    }
-    for (i = 0; i < n_guards; ++i) {
-      const int should_be_set = (i != excluded_idx &&
-                                 i != 3); // filtered out.
-      tt_int_op(!!bitarray_is_set(selected, i), OP_EQ, should_be_set);
-    }
-    bitarray_free(selected);
-    selected = NULL;
+    g = first_reachable_filtered_entry_guard(gs, NULL, excluded_flags);
+    tor_assert(g);
+    int pos = smartlist_pos(gs->sampled_entry_guards, g);
+    tt_int_op(smartlist_len(gs->sampled_entry_guards), OP_EQ, n_guards);
+    const int should_be_set = (pos != excluded_idx &&
+                                 pos != 3); // filtered out.
+    tt_int_op(1, OP_EQ, should_be_set);
   }
 
  done:
   guard_selection_free(gs);
-  bitarray_free(selected);
 }
 
 static void
@@ -1584,7 +1588,7 @@ test_entry_guard_sample_reachable_filtered_empty(void *arg)
   SMARTLIST_FOREACH(big_fake_net_nodes, node_t *, n,
                     n->is_possible_guard = 0);
 
-  entry_guard_t *g = sample_reachable_filtered_entry_guards(gs, NULL, 0);
+  entry_guard_t *g = first_reachable_filtered_entry_guard(gs, NULL, 0);
   tt_ptr_op(g, OP_EQ, NULL);
 
  done:
@@ -1675,10 +1679,13 @@ test_entry_guard_manage_primary(void *arg)
     tt_ptr_op(g, OP_EQ, smartlist_get(prev_guards, g_sl_idx));
   });
 
-  /* If we have one confirmed guard, that guards becomes the first primary
-   * guard, and the other primary guards get kept. */
+  /**
+   * If we have one confirmed guard, that guards becomes the first primary
+   * only if its sampled_idx is smaller
+   * */
 
-  /* find a non-primary guard... */
+  /* find a non-primary guard... it should have a sampled_idx higher than
+   * existing primary guards */
   entry_guard_t *confirmed = NULL;
   SMARTLIST_FOREACH(gs->sampled_entry_guards, entry_guard_t *, g, {
     if (! g->is_primary) {
@@ -1694,15 +1701,13 @@ test_entry_guard_manage_primary(void *arg)
   smartlist_add_all(prev_guards, gs->primary_entry_guards);
   entry_guards_update_primary(gs);
 
-  /*  and see what's primary now! */
+  /* the confirmed guard should be at the end of the primary list! Hopefully,
+   * one of the primary guards with a lower sampled_idx will confirm soon :)
+   * Doing this won't make the client switches between primaries depending on
+   * the order of confirming events */
   tt_int_op(smartlist_len(gs->primary_entry_guards), OP_EQ, n_primary);
-  tt_ptr_op(smartlist_get(gs->primary_entry_guards, 0), OP_EQ, confirmed);
-  SMARTLIST_FOREACH(gs->primary_entry_guards, entry_guard_t *, g, {
-    tt_assert(g->is_primary);
-    if (g_sl_idx == 0)
-      continue;
-    tt_ptr_op(g, OP_EQ, smartlist_get(prev_guards, g_sl_idx - 1));
-  });
+  tt_ptr_op(smartlist_get(gs->primary_entry_guards,
+        smartlist_len(gs->primary_entry_guards)-1), OP_EQ, confirmed);
   {
     entry_guard_t *prev_last_guard = smartlist_get(prev_guards, n_primary-1);
     tt_assert(! prev_last_guard->is_primary);
@@ -1793,6 +1798,57 @@ test_entry_guard_guard_preferred(void *arg)
 }
 
 static void
+test_entry_guard_correct_cascading_order(void *arg)
+{
+  (void)arg;
+  smartlist_t *old_primary_guards = smartlist_new();
+  guard_selection_t *gs = guard_selection_new("default", GS_TYPE_NORMAL);
+  entry_guards_expand_sample(gs);
+  /** First, a test in which the primary guards need be pulled from different
+   * lists to fill up the primary list -- this may happen, if for example, not
+   * enough guards have confirmed yet */
+  entry_guard_t *g;
+  /** just one confirmed */
+  g = smartlist_get(gs->sampled_entry_guards, 2);
+  make_guard_confirmed(gs, g);
+  entry_guards_update_primary(gs);
+  g = smartlist_get(gs->primary_entry_guards, 0);
+  tt_int_op(g->sampled_idx, OP_EQ, 0);
+  g = smartlist_get(gs->primary_entry_guards, 1);
+  tt_int_op(g->sampled_idx, OP_EQ, 1);
+  g = smartlist_get(gs->primary_entry_guards, 2);
+  tt_int_op(g->sampled_idx, OP_EQ, 2);
+
+  /** Now the primaries get all confirmed, and the primary list should not
+   * change */
+  make_guard_confirmed(gs, smartlist_get(gs->primary_entry_guards, 0));
+  make_guard_confirmed(gs, smartlist_get(gs->primary_entry_guards, 1));
+  smartlist_add_all(old_primary_guards, gs->primary_entry_guards);
+  entry_guards_update_primary(gs);
+  smartlist_ptrs_eq(gs->primary_entry_guards, old_primary_guards);
+  /** the confirmed guards should also have the same set of guards, in the same
+   * order :-) */
+  smartlist_ptrs_eq(gs->confirmed_entry_guards, gs->primary_entry_guards);
+  /** Now select a guard for a circuit, and make sure it is the first primary
+   * guard */
+  unsigned state = 9999;
+  g = select_entry_guard_for_circuit(gs, GUARD_USAGE_TRAFFIC, NULL, &state);
+  tt_ptr_op(g, OP_EQ, smartlist_get(gs->primary_entry_guards, 0));
+  /** Now, let's mark this guard as unreachable and let's update the lists */
+  g->is_reachable = GUARD_REACHABLE_NO;
+  g->failing_since = approx_time() - 10;
+  g->last_tried_to_connect = approx_time() - 10;
+  state = 9999;
+  entry_guards_update_primary(gs);
+  g = select_entry_guard_for_circuit(gs, GUARD_USAGE_TRAFFIC, NULL, &state);
+  /** we should have switched to the next one is sampled order */
+  tt_int_op(g->sampled_idx, OP_EQ, 1);
+ done:
+  smartlist_free(old_primary_guards);
+  guard_selection_free(gs);
+}
+
+static void
 test_entry_guard_select_for_circuit_no_confirmed(void *arg)
 {
   /* Simpler cases: no gaurds are confirmed yet. */
@@ -3094,6 +3150,7 @@ struct testcase_t entrynodes_tests[] = {
   BFN_TEST(sample_reachable_filtered_empty),
   BFN_TEST(retry_unreachable),
   BFN_TEST(manage_primary),
+  BFN_TEST(correct_cascading_order),
 
   EN_TEST_FORK(guard_preferred),