Initial code to parse/encode/sample prop271 guards

The encoding code is very straightforward.  The decoding code is a
bit tricky, but clean-ish.  The sampling code is untested and
probably needs more work.

1 files changed, 309 insertions, 1 deletions

diff --git a/src/or/entrynodes.c b/src/or/entrynodes.c
index c96ff095da..9af71404de 100644
--- a/src/or/entrynodes.c
+++ b/src/or/entrynodes.c
@@ -77,6 +77,11 @@ struct guard_selection_s {
   int dirty;
 
   /**
+   * A list of the sampled entry guards, as entry_guard_t structures.
+   * Not in any particular order. */
+  smartlist_t *sampled_entry_guards;
+
+  /**
    * A list of our chosen entry guards, as entry_guard_t structures; this
    * preserves the pre-Prop271 behavior.
    */
@@ -87,6 +92,8 @@ struct guard_selection_s {
    * config's EntryNodes first?  This was formerly a global.
    */
   int should_add_entry_nodes;
+
+  int filtered_up_to_date;
 };
 
 static smartlist_t *guard_contexts = NULL;
@@ -118,6 +125,7 @@ guard_selection_new(void)
 
   gs = tor_malloc_zero(sizeof(*gs));
   gs->chosen_entry_guards = smartlist_new();
+  gs->sampled_entry_guards = smartlist_new();
 
   return gs;
 }
@@ -191,6 +199,293 @@ entry_guard_get_pathbias_state(entry_guard_t *guard)
   return &guard->pb;
 }
 
+/** Return an interval betweeen 'now' and 'max_backdate' seconds in the past,
+ * chosen uniformly at random. */
+STATIC time_t
+randomize_time(time_t now, time_t max_backdate)
+{
+  tor_assert(max_backdate > 0);
+
+  time_t earliest = now - max_backdate;
+  time_t latest = now;
+  if (earliest <= 0)
+    earliest = 1;
+  if (latest <= earliest)
+    latest = earliest + 1;
+
+  return crypto_rand_time_range(earliest, latest);
+}
+
+/**
+ * DOCDOC
+ */
+STATIC void
+entry_guard_add_to_sample(guard_selection_t *gs,
+                          node_t *node)
+{
+  (void) entry_guard_add_to_sample; // XXXX prop271 remove -- unused
+  const int GUARD_LIFETIME = 90 * 86400; // xxxx prop271
+  tor_assert(gs);
+  tor_assert(node);
+
+  // XXXX prop271 take ed25519 identity here too.
+
+  /* make sure that the guard is not already sampled. */
+   SMARTLIST_FOREACH_BEGIN(gs->sampled_entry_guards,
+                           entry_guard_t *, sampled) {
+    if (BUG(tor_memeq(node->identity, sampled->identity, DIGEST_LEN))) {
+      return;
+    }
+  } SMARTLIST_FOREACH_END(sampled);
+
+  entry_guard_t *guard = tor_malloc_zero(sizeof(entry_guard_t));
+
+  /* persistent fields */
+  memcpy(guard->identity, node->identity, DIGEST_LEN);
+  strlcpy(guard->nickname, node_get_nickname(node), sizeof(guard->nickname));
+  guard->sampled_on_date = randomize_time(approx_time(), GUARD_LIFETIME/10);
+  tor_free(guard->sampled_by_version);
+  guard->sampled_by_version = tor_strdup(VERSION);
+  guard->confirmed_idx = -1;
+
+  /* non-persistent fields */
+  guard->is_reachable = GUARD_REACHABLE_MAYBE;
+
+  smartlist_add(gs->sampled_entry_guards, guard);
+  gs->filtered_up_to_date = 0;
+
+  entry_guards_changed_for_guard_selection(gs);
+}
+
+/**
+ * Return a newly allocated string for encoding the persistent parts of
+ * <b>guard</b> to the state file.
+ */
+STATIC char *
+entry_guard_encode_for_state(entry_guard_t *guard)
+{
+  /*
+   * The meta-format we use is K=V K=V K=V... where K can be any
+   * characters excepts space and =, and V can be any characters except
+   * space.  The order of entries is not allowed to matter.
+   * Unrecognized K=V entries are persisted; recognized but erroneous
+   * entries are corrected.
+   */
+
+  smartlist_t *result = smartlist_new();
+  char tbuf[ISO_TIME_LEN+1];
+
+  tor_assert(guard);
+
+  smartlist_add_asprintf(result, "rsa_id=%s",
+                         hex_str(guard->identity, DIGEST_LEN));
+  if (strlen(guard->nickname)) {
+    smartlist_add_asprintf(result, "nickname=%s", guard->nickname);
+  }
+
+  format_iso_time_nospace(tbuf, guard->sampled_on_date);
+  smartlist_add_asprintf(result, "sampled_on=%s", tbuf);
+
+  if (guard->sampled_by_version) {
+    smartlist_add_asprintf(result, "sampled_by=%s",
+                           guard->sampled_by_version);
+  }
+
+  if (guard->unlisted_since_date > 0) {
+    format_iso_time_nospace(tbuf, guard->unlisted_since_date);
+    smartlist_add_asprintf(result, "unlisted_since=%s", tbuf);
+  }
+
+  smartlist_add_asprintf(result, "listed=%d",
+                         (int)guard->currently_listed);
+
+  if (guard->confirmed_idx >= 0) {
+    format_iso_time_nospace(tbuf, guard->confirmed_on_date);
+    smartlist_add_asprintf(result, "confirmed_on=%s", tbuf);
+
+    smartlist_add_asprintf(result, "confirmed_idx=%d", guard->confirmed_idx);
+  }
+
+  if (guard->extra_state_fields)
+    smartlist_add_strdup(result, guard->extra_state_fields);
+
+  char *joined = smartlist_join_strings(result, " ", 0, NULL);
+  SMARTLIST_FOREACH(result, char *, cp, tor_free(cp));
+  smartlist_free(result);
+
+  return joined;
+}
+
+/**
+ * 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.
+ */
+STATIC entry_guard_t *
+entry_guard_parse_from_state(const char *s)
+{
+  /* Unrecognized entries get put in here. */
+  smartlist_t *extra = smartlist_new();
+
+  /* These fields get parsed from the string. */
+  char *rsa_id = NULL;
+  char *nickname = NULL;
+  char *sampled_on = NULL;
+  char *sampled_by = NULL;
+  char *unlisted_since = NULL;
+  char *listed  = NULL;
+  char *confirmed_on = NULL;
+  char *confirmed_idx = NULL;
+
+  /* Split up the entries.  Put the ones we know about in strings and the
+   * rest in "extra". */
+  {
+    smartlist_t *entries = smartlist_new();
+
+    strmap_t *vals = strmap_new(); // Maps keyword to location
+    strmap_set(vals, "rsa_id", &rsa_id);
+    strmap_set(vals, "nickname", &nickname);
+    strmap_set(vals, "sampled_on", &sampled_on);
+    strmap_set(vals, "sampled_by", &sampled_by);
+    strmap_set(vals, "unlisted_since", &unlisted_since);
+    strmap_set(vals, "listed", &listed);
+    strmap_set(vals, "confirmed_on", &confirmed_on);
+    strmap_set(vals, "confirmed_idx", &confirmed_idx);
+
+    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);
+
+    smartlist_free(entries);
+    strmap_free(vals, NULL);
+  }
+
+  entry_guard_t *guard = tor_malloc_zero(sizeof(entry_guard_t));
+
+  if (rsa_id == NULL) {
+    log_warn(LD_CIRC, "Guard missing RSA ID field");
+    goto err;
+  }
+
+  /* Process the identity and nickname. */
+  if (base16_decode(guard->identity, sizeof(guard->identity),
+                    rsa_id, strlen(rsa_id)) != DIGEST_LEN) {
+    log_warn(LD_CIRC, "Unable to decode guard identity %s", escaped(rsa_id));
+    goto err;
+  }
+
+  if (nickname) {
+    strlcpy(guard->nickname, nickname, sizeof(guard->nickname));
+  } else {
+    guard->nickname[0]='$';
+    base16_encode(guard->nickname+1, sizeof(guard->nickname)-1,
+                  guard->identity, DIGEST_LEN);
+  }
+
+  /* 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;
+
+  /* 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;
+
+  /* The index is a nonnegative integer. */
+  guard->confirmed_idx = -1;
+  if (confirmed_idx) {
+    int ok=1;
+    long idx = tor_parse_long(confirmed_idx, 10, 0, INT_MAX, &ok, NULL);
+    if (! ok) {
+      log_warn(LD_CIRC, "Guard has invalid confirmed_idx %s",
+               escaped(confirmed_idx));
+    } else {
+      guard->confirmed_idx = (int)idx;
+    }
+  }
+
+  /* Anything we didn't recognize gets crammed together */
+  if (smartlist_len(extra) > 0) {
+    guard->extra_state_fields = smartlist_join_strings(extra, " ", 0, NULL);
+  }
+
+  /* initialize non-persistent fields */
+  guard->is_reachable = GUARD_REACHABLE_MAYBE;
+
+  goto done;
+
+ err:
+  // only consider it an error if the guard state was totally unparseable.
+  entry_guard_free(guard);
+  guard = NULL;
+
+ done:
+  tor_free(rsa_id);
+  tor_free(nickname);
+  tor_free(sampled_on);
+  tor_free(sampled_by);
+  tor_free(unlisted_since);
+  tor_free(listed);
+  tor_free(confirmed_on);
+  tor_free(confirmed_idx);
+  SMARTLIST_FOREACH(extra, char *, cp, tor_free(cp));
+  smartlist_free(extra);
+
+  return guard;
+}
+
 /** Check whether the entry guard <b>e</b> is usable, given the directory
  * authorities' opinion about the router (stored in <b>ri</b>) and the user's
  * configuration (in <b>options</b>). Set <b>e</b>->bad_since
@@ -677,13 +972,14 @@ pick_entry_guards(guard_selection_t *gs,
 #define ENTRY_GUARD_REMOVE_AFTER (30*24*60*60)
 
 /** Release all storage held by <b>e</b>. */
-static void
+STATIC void
 entry_guard_free(entry_guard_t *e)
 {
   if (!e)
     return;
   tor_free(e->chosen_by_version);
   tor_free(e->sampled_by_version);
+  tor_free(e->extra_state_fields);
   tor_free(e);
 }
 
@@ -1452,6 +1748,9 @@ entry_guards_parse_state_for_guard_selection(
   const char *state_version = state->TorVersion;
   digestmap_t *added_by = digestmap_new();
 
+  if (0) entry_guard_parse_from_state(NULL); // XXXX prop271 remove -- unused
+  if (0) entry_guard_add_to_sample(NULL, NULL); // XXXX prop271 remove
+
   tor_assert(gs != NULL);
 
   *msg = NULL;
@@ -1777,6 +2076,8 @@ entry_guards_update_state(or_state_t *state)
   config_line_t **next, *line;
   guard_selection_t *gs = get_guard_selection_info();
 
+  if (0) entry_guard_encode_for_state(NULL); // XXXX prop271 remove -- unused
+
   tor_assert(gs != NULL);
   tor_assert(gs->chosen_entry_guards != NULL);
 
@@ -2837,6 +3138,13 @@ guard_selection_free(guard_selection_t *gs)
     gs->chosen_entry_guards = NULL;
   }
 
+  if (gs->sampled_entry_guards) {
+    SMARTLIST_FOREACH(gs->sampled_entry_guards, entry_guard_t *, e,
+                      entry_guard_free(e));
+    smartlist_free(gs->sampled_entry_guards);
+    gs->sampled_entry_guards = NULL;
+  }
+
   tor_free(gs);
 }