r13243@catbus: nickm | 2007-06-04 15:17:15 -0400

 Start of code to compute consensus network-status stuff from a bunch of votes.  Strangely, it does not yet feel like an enormous ugly hack. 


svn:r10489

7 files changed, 546 insertions, 14 deletions

diff --git a/src/common/container.c b/src/common/container.c
index a3663c48f6..9333ccdb16 100644
--- a/src/common/container.c
+++ b/src/common/container.c
@@ -196,6 +196,18 @@ smartlist_string_isin(const smartlist_t *sl, const char *element)
   return 0;
 }
 
+/** DOCDOC */
+int
+smartlist_string_pos(const smartlist_t *sl, const char *element)
+{
+  int i;
+  if (!sl) return -1;
+  for (i=0; i < sl->num_used; i++)
+    if (strcmp((const char*)sl->list[i],element)==0)
+      return i;
+  return -1;
+}
+
 /** Return true iff <b>sl</b> has some element E such that
  * !strcasecmp(E,<b>element</b>)
  */
diff --git a/src/common/container.h b/src/common/container.h
index 735965358a..782c4a491f 100644
--- a/src/common/container.h
+++ b/src/common/container.h
@@ -40,6 +40,7 @@ void smartlist_string_remove(smartlist_t *sl, const char *element);
 int smartlist_isin(const smartlist_t *sl, const void *element) ATTR_PURE;
 int smartlist_string_isin(const smartlist_t *sl, const char *element)
   ATTR_PURE;
+int smartlist_string_pos(const smartlist_t *, const char *elt) ATTR_PURE;
 int smartlist_string_isin_case(const smartlist_t *sl, const char *element)
   ATTR_PURE;
 int smartlist_string_num_isin(const smartlist_t *sl, int num) ATTR_PURE;
diff --git a/src/or/dirserv.c b/src/or/dirserv.c
index 305fb246fd..616c8e4d41 100644
--- a/src/or/dirserv.c
+++ b/src/or/dirserv.c
@@ -1563,10 +1563,12 @@ dirserv_compute_performance_thresholds(routerlist_t *rl)
  * failure. */
 int
 routerstatus_format_entry(char *buf, size_t buf_len,
-                          routerstatus_t *rs, const char *platform)
+                          routerstatus_t *rs, const char *platform,
+                          int first_line_only)
 {
   int r;
   struct in_addr in;
+  char *cp;
 
   int f_authority;
   char published[ISO_TIME_LEN+1];
@@ -1583,16 +1585,24 @@ routerstatus_format_entry(char *buf, size_t buf_len,
   f_authority = router_digest_is_trusted_dir(rs->identity_digest);
 
   r = tor_snprintf(buf, buf_len,
-                   "r %s %s %s %s %s %d %d\n"
-                   "s%s%s%s%s%s%s%s%s%s%s\n",
+                   "r %s %s %s %s %s %d %d\n",
                    rs->nickname,
                    identity64,
                    digest64,
                    published,
                    ipaddr,
                    (int)rs->or_port,
-                   (int)rs->dir_port,
-                   /* These must stay in alphabetical order. */
+                   (int)rs->dir_port);
+  if (r<0) {
+    log_warn(LD_BUG, "Not enough space in buffer.");
+    return -1;
+  }
+  if (first_line_only)
+    return 0;
+  cp = buf + strlen(buf);
+  r = tor_snprintf(cp, buf_len - (cp-buf),
+                   "s%s%s%s%s%s%s%s%s%s%s\n",
+                  /* These must stay in alphabetical order. */
                    f_authority?" Authority":"",
                    rs->is_bad_exit?" BadExit":"",
                    rs->is_exit?" Exit":"",
@@ -1866,7 +1876,8 @@ generate_networkstatus_opinion(int v2)
       rs.or_port = ri->or_port;
       rs.dir_port = ri->dir_port;
 
-      if (routerstatus_format_entry(outp, endp-outp, &rs, ri->platform) < 0) {
+      if (routerstatus_format_entry(outp, endp-outp, &rs,
+                                    ri->platform, 0) < 0) {
         log_warn(LD_BUG, "Unable to print router status.");
         goto done;
       }
diff --git a/src/or/dirvote.c b/src/or/dirvote.c
index 413cc93640..c96fe4ff1b 100644
--- a/src/or/dirvote.c
+++ b/src/or/dirvote.c
@@ -46,3 +46,494 @@ networkstatus_vote_free(networkstatus_vote_t *ns)
   tor_free(ns);
 }
 
+/** DOCDOC */
+static int
+_compare_times(const void **_a, const void **_b)
+{
+  const time_t *a = *_a, *b = *_b;
+  if (*a<*b)
+    return -1;
+  else if (*a>*b)
+    return 1;
+  else
+    return 0;
+}
+
+/** DOCDOC */
+static int
+_compare_ints(const void **_a, const void **_b)
+{
+  const int *a = *_a, *b = *_b;
+  if (*a<*b)
+    return -1;
+  else if (*a>*b)
+    return 1;
+  else
+    return 0;
+}
+
+/** DOCDOC */
+static time_t
+median_time(smartlist_t *times)
+{
+  int idx;
+  smartlist_sort(times, _compare_times);
+  idx = (smartlist_len(times)-1)/2;
+  return *(time_t*)smartlist_get(times, idx);
+}
+
+/** DOCDOC */
+static int
+median_int(smartlist_t *ints)
+{
+  int idx;
+  smartlist_sort(ints, _compare_ints);
+  idx = (smartlist_len(ints)-1)/2;
+  return *(time_t*)smartlist_get(ints, idx);
+}
+
+/** DOCDOC */
+static int
+_compare_votes_by_authority_id(const void **_a, const void **_b)
+{
+  const networkstatus_vote_t *a = *_a, *b = *_b;
+  return memcmp(a->identity_digest, b->identity_digest, DIGEST_LEN);
+}
+
+/** DOCDOC */
+static void
+get_frequent_members(smartlist_t *out, smartlist_t *in, int min)
+{
+  char *cur = NULL;
+  int count = 0;
+  SMARTLIST_FOREACH(in, char *, cp,
+  {
+    if (cur && !strcmp(cp, cur)) {
+      ++count;
+    } else {
+      if (count > min)
+        smartlist_add(out, cur);
+      cur = cp;
+      count = 1;
+    }
+  });
+  if (count > min)
+    smartlist_add(out, cur);
+}
+
+/** DOCDOC */
+static const char *
+get_most_frequent_member(smartlist_t *lst)
+{
+  const char *most_frequent = NULL;
+  int most_frequent_count = 0;
+
+  const char *cur = NULL;
+  int count = 0;
+
+  SMARTLIST_FOREACH(lst, const char *, s,
+  {
+    if (cur && !strcmp(s, cur)) {
+      ++count;
+    } else {
+      if (count >= most_frequent_count) {
+        most_frequent = cur;
+        most_frequent_count = count;
+      }
+      cur = s;
+      count = 1;
+    }
+  });
+  if (count >= most_frequent_count) {
+    most_frequent = cur;
+    most_frequent_count = count;
+  }
+  return most_frequent;
+}
+
+/** DOCDOC */
+static int
+compare_votes(const vote_routerstatus_t *a, const vote_routerstatus_t *b)
+{
+  int r;
+  if ((r = memcmp(a->status.descriptor_digest, b->status.descriptor_digest,
+                  DIGEST_LEN)))
+    return r;
+  if ((r = (b->status.published_on - a->status.published_on)))
+    return r;
+  if ((r = (((int)b->status.or_port) - ((int)a->status.or_port))))
+    return r;
+  if ((r = (((int)b->status.dir_port) - ((int)a->status.dir_port))))
+    return r;
+  return 0;
+}
+
+/** DOCDOC */
+static int
+_compare_votes(const void **_a, const void **_b)
+{
+  const vote_routerstatus_t *a = *_a, *b = *_b;
+  return compare_votes(a,b);
+}
+
+/** DOCDOC */
+static vote_routerstatus_t *
+compute_routerstatus_consensus(smartlist_t *votes)
+{
+  vote_routerstatus_t *most = NULL, *cur = NULL;
+  int most_n = 0, cur_n = 0;
+  time_t most_published = 0;
+
+  smartlist_sort(votes, _compare_votes);
+  SMARTLIST_FOREACH(votes, vote_routerstatus_t *, rs,
+  {
+    if (cur && !compare_votes(cur, rs)) {
+      ++cur_n;
+    } else {
+      if (cur_n > most_n ||
+          (cur && cur_n == most_n && cur->status.published_on > most_published)) {
+        most = cur;
+        most_n = cur_n;
+        most_published = cur->status.published_on;
+      }
+      cur_n = 1;
+      cur = rs;
+    }
+  });
+
+  if (cur_n > most_n ||
+      (cur && cur_n == most_n && cur->status.published_on > most_published)) {
+    most = cur;
+    most_n = cur_n;
+    most_published = cur->status.published_on;
+  }
+
+  tor_assert(most);
+  return most;
+}
+
+
+/** DOCDOC */
+char *
+networkstatus_compute_consensus(smartlist_t *votes)
+{
+  int n_rs=0;
+  smartlist_t *chunks;
+
+  time_t valid_after, fresh_until, valid_until;
+  int vote_seconds, dist_seconds;
+  char *client_versions = NULL, *server_versions = NULL;
+  smartlist_t *flags;
+  int total_authorities = smartlist_len(votes); /*XXXX020 not right. */
+
+  if (!smartlist_len(votes)) {
+    log_warn(LD_DIR, "Can't compute a consensus from no votes.");
+    return NULL;
+  }
+  /* XXXX020 somebody needs to check vote authority. It could be this
+   * function, it could be somebody else. */
+
+  flags = smartlist_create();
+
+  /* Compute medians of time-related things, and figure out how many
+   * routers we might need to talk about. */
+  {
+    smartlist_t *va_times = smartlist_create();
+    smartlist_t *fu_times = smartlist_create();
+    smartlist_t *vu_times = smartlist_create();
+    smartlist_t *votesec_list = smartlist_create();
+    smartlist_t *distsec_list = smartlist_create();
+    int n_versioning_clients = 0, n_versioning_servers = 0;
+    smartlist_t *combined_client_versions = smartlist_create();
+    smartlist_t *combined_server_versions = smartlist_create();
+    int j;
+    SMARTLIST_FOREACH(votes, networkstatus_vote_t *, v,
+    {
+      n_rs += smartlist_len(v->routerstatus_list);
+      smartlist_add(va_times, &v->valid_after);
+      smartlist_add(fu_times, &v->fresh_until);
+      smartlist_add(vu_times, &v->valid_until);
+      smartlist_add(votesec_list, &v->vote_seconds);
+      smartlist_add(distsec_list, &v->dist_seconds);
+      if (v->client_versions) {
+        smartlist_t *cv = smartlist_create();
+        ++n_versioning_clients;
+        smartlist_split_string(cv, v->client_versions, ",",
+                               SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
+        sort_version_list(cv, 1);
+        smartlist_add_all(combined_client_versions, cv);
+        smartlist_free(cv); /* elements get freed later. */
+      }
+      if (v->server_versions) {
+        smartlist_t *sv = smartlist_create();
+        ++n_versioning_servers;
+        smartlist_split_string(sv, v->server_versions, ",",
+                               SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
+        sort_version_list(sv, 1);
+        smartlist_add_all(combined_server_versions, sv);
+        smartlist_free(sv); /* elements get freed later. */
+      }
+      for (j=0; v->known_flags[j]; ++j)
+        smartlist_add(flags, tor_strdup(v->known_flags[j]));
+    });
+    valid_after = median_time(va_times);
+    fresh_until = median_time(fu_times);
+    valid_until = median_time(vu_times);
+    vote_seconds = median_int(votesec_list);
+    dist_seconds = median_int(distsec_list);
+
+    for (j = 0; j < 2; ++j) {
+      smartlist_t *lst =
+        j ? combined_server_versions : combined_client_versions;
+      int min = (j ? n_versioning_servers : n_versioning_clients) / 2;
+      smartlist_t *good = smartlist_create();
+      char *res;
+      sort_version_list(lst, 0);
+      get_frequent_members(good, lst, min);
+      res = smartlist_join_strings(good, ",", 0, NULL);
+      if (j)
+        server_versions = res;
+      else
+        client_versions = res;
+      SMARTLIST_FOREACH(lst, char *, cp, tor_free(cp));
+      smartlist_free(good);
+      smartlist_free(lst);
+    }
+
+    smartlist_sort_strings(flags);
+    smartlist_uniq_strings(flags);
+
+    smartlist_free(va_times);
+    smartlist_free(fu_times);
+    smartlist_free(vu_times);
+    smartlist_free(votesec_list);
+    smartlist_free(distsec_list);
+  }
+
+  chunks = smartlist_create();
+
+  {
+    char buf[1024];
+    char va_buf[ISO_TIME_LEN+1], fu_buf[ISO_TIME_LEN+1],
+      vu_buf[ISO_TIME_LEN+1];
+    char *flaglist;
+    format_iso_time(va_buf, valid_after);
+    format_iso_time(fu_buf, fresh_until);
+    format_iso_time(vu_buf, valid_until);
+    flaglist = smartlist_join_strings(flags, " ", 0, NULL);
+
+    tor_snprintf(buf, sizeof(buf),
+                 "network-status-version 3\n"
+                 "vote-status consensus\n"
+                 "valid-after %s\n"
+                 "fresh-until %s\n"
+                 "valid-until %s\n"
+                 "voting-delay %d %d\n"
+                 "client-versions %s\n"
+                 "server-versions %s\n"
+                 "known-flags %s\n",
+                 va_buf, fu_buf, vu_buf,
+                 vote_seconds, dist_seconds,
+                 client_versions, server_versions, flaglist);
+    smartlist_add(chunks, tor_strdup(buf));
+
+    tor_free(flaglist);
+  }
+
+  /* Sort the votes. */
+  smartlist_sort(votes, _compare_votes_by_authority_id);
+  /* Add the authority sections. */
+  SMARTLIST_FOREACH(votes, networkstatus_vote_t *, v,
+  {
+    char buf[1024];
+    struct in_addr in;
+    char ip[INET_NTOA_BUF_LEN];
+    char fingerprint[HEX_DIGEST_LEN+1];
+    char votedigest[HEX_DIGEST_LEN+1];
+
+    in.s_addr = htonl(v->addr);
+    tor_inet_ntoa(&in, ip, sizeof(ip));
+    base16_encode(fingerprint, sizeof(fingerprint), v->identity_digest,
+                  DIGEST_LEN);
+    base16_encode(votedigest, sizeof(votedigest), v->vote_digest, DIGEST_LEN);
+
+    tor_snprintf(buf, sizeof(buf),
+                 "dir-source %s %s %s %s %d %d\n"
+                 "contact %s\n"
+                 "vote-digest %s\n",
+                 v->nickname, fingerprint, v->address, ip, v->dir_port,
+                    v->or_port,
+                 v->contact,
+                 votedigest);
+    smartlist_add(chunks, tor_strdup(buf));
+  });
+
+  /* Add the actual router entries. */
+  {
+    /* document these XXXX020 */
+    int *index;
+    int *size;
+    int *flag_counts;
+    int i;
+    smartlist_t *matching_descs = smartlist_create();
+    smartlist_t *chosen_flags = smartlist_create();
+    smartlist_t *versions = smartlist_create();
+
+    int *n_voter_flags; /* n_voter_flags[j] is the number of flags that
+                         * votes[j] knows about. */
+    int *n_flag_voters; /* n_flag_voters[f] is the number of votes that care
+                         * about flags[f]. */
+    int **flag_map; /* flag_map[j][b] is an index f such that flag_map[f]
+                     * is the same flag as votes[j]->known_flags[b]. */
+
+    index = tor_malloc_zero(sizeof(int)*smartlist_len(votes));
+    size = tor_malloc_zero(sizeof(int)*smartlist_len(votes));
+    n_voter_flags = tor_malloc_zero(sizeof(int) * smartlist_len(votes));
+    n_flag_voters = tor_malloc_zero(sizeof(int) * smartlist_len(flags));
+    flag_map = tor_malloc_zero(sizeof(int*) * smartlist_len(votes));
+    SMARTLIST_FOREACH(votes, networkstatus_vote_t *, v,
+    {
+      for (i = 0; v->known_flags[i]; ++i) {
+        int p = smartlist_string_pos(flags, v->known_flags[i]);
+        tor_assert(p >= 0);
+        flag_map[v_sl_idx][i] = p;
+        ++n_flag_voters[p];
+        /* XXXX020 somebody needs to make sure that there are no duplicate
+         * entries in anybody's flag list. */
+      }
+      tor_assert(!v->known_flags[i]);
+      n_voter_flags[v_sl_idx] = i;
+      size[v_sl_idx] = smartlist_len(v->routerstatus_list);
+    });
+
+    /* Now go through all the votes */
+    flag_counts = tor_malloc(sizeof(int) * smartlist_len(flags));
+    while (1) {
+      vote_routerstatus_t *rs;
+      routerstatus_t rs_out;
+      const char *lowest_id = NULL;
+      const char *chosen_version;
+      int n_listing = 0;
+      int i;
+      char buf[256];
+
+      SMARTLIST_FOREACH(votes, networkstatus_vote_t *, v, {
+        if (index[v_sl_idx] < size[v_sl_idx]) {
+          rs = smartlist_get(v->routerstatus_list, index[v_sl_idx]);
+          if (!lowest_id ||
+              memcmp(rs->status.identity_digest, lowest_id, DIGEST_LEN) < 0)
+            lowest_id = rs->status.identity_digest;
+        }
+      });
+      if (!lowest_id) /* we're out of routers. */
+        break;
+
+      memset(flag_counts, 0, sizeof(int)*smartlist_len(flags));
+      smartlist_clear(matching_descs);
+      smartlist_clear(chosen_flags);
+      smartlist_clear(versions);
+
+      /* Okay, go through all the entries for this digest. */
+      SMARTLIST_FOREACH(votes, networkstatus_vote_t *, v, {
+        if (index[v_sl_idx] >= size[v_sl_idx])
+          continue; /* out of entries. */
+        rs = smartlist_get(v->routerstatus_list, index[v_sl_idx]);
+        if (memcmp(rs->status.identity_digest, lowest_id, DIGEST_LEN))
+          continue; /* doesn't include this router. */
+        /* At this point, we know that we're looking at a routersatus with
+         * identity "lowest".
+         */
+        ++index[v_sl_idx];
+        ++n_listing;
+
+        smartlist_add(matching_descs, rs);
+        if (rs->version && rs->version[0])
+          smartlist_add(versions, rs->version);
+
+        /* Tally up all the flags. */
+        for (i = 0; i < n_voter_flags[v_sl_idx]; ++i) {
+          if (rs->flags & (U64_LITERAL(1) << i))
+            ++flag_counts[flag_map[v_sl_idx][i]];
+          /* XXXX020 named is special. */
+        }
+      });
+
+      /* We don't include this router at all unless more than half of
+       * the authorities we believe in list it. */
+      if (n_listing <= total_authorities/2)
+        continue;
+
+      /* Figure out the most popular opinion of what the most recent
+       * routerinfo and its contents are. */
+      rs = compute_routerstatus_consensus(matching_descs);
+      /* Copy bits of that into rs_out. */
+      tor_assert(!memcmp(lowest_id, rs->status.identity_digest, DIGEST_LEN));
+      memcpy(rs_out.identity_digest, lowest_id, DIGEST_LEN);
+      memcpy(rs_out.descriptor_digest, rs->status.descriptor_digest,
+             DIGEST_LEN);
+      rs_out.published_on = rs->status.published_on;
+      rs_out.dir_port = rs->status.dir_port;
+      rs_out.or_port = rs->status.or_port;
+
+      /* Set the flags. */
+      smartlist_add(chosen_flags, (char*)"s"); /* for the start of the line. */
+      SMARTLIST_FOREACH(flags, const char *, fl,
+      {
+        if (flag_counts[fl_sl_idx] > n_flag_voters[fl_sl_idx]/2)
+          smartlist_add(chosen_flags, (char*)fl);
+        /* XXXX020 named is special. */
+      });
+
+      /* XXXX020 set the nickname! */
+
+      /* Pick the version. */
+      if (smartlist_len(versions)) {
+        sort_version_list(versions, 0);
+        chosen_version = get_most_frequent_member(versions);
+      } else {
+        chosen_version = NULL;
+      }
+
+      /* Okay!! Now we can write the descriptor... */
+      /*     First line goes into "buf". */
+      routerstatus_format_entry(buf, sizeof(buf), &rs_out, NULL, 1);
+      smartlist_add(chunks, tor_strdup(buf));
+      /*     Second line is all flags.  The "\n" is missing. */
+      smartlist_add(chunks,
+                    smartlist_join_strings(chosen_flags, " ", 0, NULL));
+      /*     Now the version line. */
+      if (chosen_version) {
+        /* XXXX020 fails on very big version. */
+        tor_snprintf(buf, sizeof(buf), "\nv %s\n", chosen_version);
+        smartlist_add(chunks, tor_strdup(buf));
+      } else {
+        smartlist_add(chunks, tor_strdup("\n"));
+      }
+
+      /* And the loop is over and we move on to the next router */
+    }
+
+    tor_free(index);
+    tor_free(size);
+    tor_free(n_voter_flags);
+    tor_free(n_flag_voters);
+    for (i = 0; i < smartlist_len(votes); ++i)
+      tor_free(flag_map[i]);
+    tor_free(flag_map);
+    tor_free(flag_counts);
+    smartlist_free(matching_descs);
+    smartlist_free(chosen_flags);
+    smartlist_free(versions);
+  }
+
+  /* Concatenate everything. */
+
+  /* Add a signature. */
+
+  /* Free everything. */
+
+  tor_free(client_versions);
+  tor_free(server_versions);
+
+  return NULL;
+}
diff --git a/src/or/or.h b/src/or/or.h
index 7afa3eccc0..3b5f77ae5b 100644
--- a/src/or/or.h
+++ b/src/or/or.h
@@ -1324,6 +1324,8 @@ typedef struct networkstatus_vote_t {
 
   char *contact;
 
+  char vote_digest[DIGEST_LEN];
+
   smartlist_t *routerstatus_list;
 } networkstatus_vote_t;
 
@@ -2705,13 +2707,15 @@ int dirserv_statuses_are_old(smartlist_t *fps, time_t cutoff);
 size_t dirserv_estimate_data_size(smartlist_t *fps, int is_serverdescs,
                                   int compressed);
 int routerstatus_format_entry(char *buf, size_t buf_len,
-                              routerstatus_t *rs, const char *platform);
+                              routerstatus_t *rs, const char *platform,
+                              int first_line_only);
 void dirserv_free_all(void);
 void cached_dir_decref(cached_dir_t *d);
 
 /********************************* dirvote.c ************************/
 
 void networkstatus_vote_free(networkstatus_vote_t *ns);
+char *networkstatus_compute_consensus(smartlist_t *votes);
 
 /********************************* dns.c ***************************/
 
diff --git a/src/or/routerlist.c b/src/or/routerlist.c
index ab4775a636..0ea51b621b 100644
--- a/src/or/routerlist.c
+++ b/src/or/routerlist.c
@@ -3718,7 +3718,7 @@ compute_recommended_versions(time_t now, int client,
       } else {
         if (n_seen > n_versioning/2 && current)
           smartlist_add(recommended, current);
-        n_seen = 0;
+        n_seen = 0; /* XXXX020 shouldn't this be 1? */
         current = cp;
       }
     });
@@ -5071,7 +5071,7 @@ char *
 networkstatus_getinfo_helper_single(routerstatus_t *rs)
 {
   char buf[256];
-  routerstatus_format_entry(buf, sizeof(buf), rs, NULL);
+  routerstatus_format_entry(buf, sizeof(buf), rs, NULL, 0);
   return tor_strdup(buf);
 }
 
diff --git a/src/or/routerparse.c b/src/or/routerparse.c
index 9aac94d1e4..93f2366faf 100644
--- a/src/or/routerparse.c
+++ b/src/or/routerparse.c
@@ -303,7 +303,7 @@ static token_rule_t networkstatus_vote_token_table[] = {
 
   T0N("opt",                 K_OPT,             CONCAT_ARGS, OBJ_OK ),
   T1( "contact",             K_CONTACT,         CONCAT_ARGS, NO_OBJ ),
-  T1( "dir-source",          K_DIR_SOURCE,      GE(3),       NO_OBJ ),
+  T1( "dir-source",          K_DIR_SOURCE,      GE(6),       NO_OBJ ),
   T1( "dir-options",         K_DIR_OPTIONS,     ARGS,        NO_OBJ ),
   T1( "known-flags",         K_KNOWN_FLAGS,     CONCAT_ARGS, NO_OBJ ),
   T01("client-versions",     K_CLIENT_VERSIONS, CONCAT_ARGS, NO_OBJ ),
@@ -351,7 +351,6 @@ static token_rule_t networkstatus_vote_footer_token_table[] = {
   END_OF_TABLE
 };
 
-
 #undef T
 
 /* static function prototypes */
@@ -1798,6 +1797,7 @@ networkstatus_parse_vote_from_string(const char *s)
   directory_token_t *tok;
   int ok;
   struct in_addr in;
+  int i;
 
   if (router_get_networkstatus_v3_hash(s, ns_digest)) {
     log_warn(LD_DIR, "Unable to compute digest of network-status");
@@ -1872,7 +1872,7 @@ networkstatus_parse_vote_from_string(const char *s)
 
   tok = find_first_by_keyword(tokens, K_DIR_SOURCE);
   tor_assert(tok);
-  tor_assert(tok->n_args >= 5);
+  tor_assert(tok->n_args >= 6);
   ns->nickname = tor_strdup(tok->args[0]);
   if (strlen(tok->args[1]) != HEX_DIGEST_LEN ||
       base16_decode(ns->identity_digest, sizeof(ns->identity_digest),
@@ -1891,6 +1891,10 @@ networkstatus_parse_vote_from_string(const char *s)
     (int) tor_parse_long(tok->args[4], 10, 0, 65535, &ok, NULL);
   if (!ok)
     goto err;
+  ns->or_port = (uint64_t)
+    (int) tor_parse_long(tok->args[5], 10, 0, 65535, &ok, NULL);
+  if (!ok)
+    goto err;
 
   tok = find_first_by_keyword(tokens, K_CONTACT);
   if (tok) {
@@ -1910,6 +1914,16 @@ networkstatus_parse_vote_from_string(const char *s)
       tor_free(rs);
     }
   }
+  for (i = 1; i < smartlist_len(ns->routerstatus_list); ++i) {
+    vote_routerstatus_t *a = smartlist_get(ns->routerstatus_list, i-1);
+    vote_routerstatus_t *b = smartlist_get(ns->routerstatus_list, i);
+    if (memcmp(a->status.identity_digest, b->status.identity_digest,
+               DIGEST_LEN) >= 0) {
+      log_warn(LD_DIR, "Vote networkstatus entries not sorted by identity "
+               "digest");
+      goto err;
+    }
+  }
 
   /* Parse footer; check signature. */
   footer_tokens = smartlist_create();
@@ -1938,6 +1952,7 @@ networkstatus_parse_vote_from_string(const char *s)
              "network-status vote.", escaped(tok->args[1]));
     goto err;
   }
+  memcpy(ns->vote_digest, declared_digest, DIGEST_LEN);
   if (memcmp(declared_identity, ns->cert->cache_info.identity_digest,
              DIGEST_LEN)) {
     log_warn(LD_DIR, "Digest mismatch between declared and actual on "
@@ -1974,11 +1989,9 @@ networkstatus_parse_vote_from_string(const char *s)
     smartlist_free(footer_tokens);
   }
 
-
   return ns;
 }
 
-
 /** Parse the addr policy in the string <b>s</b> and return it.  If
  * assume_action is nonnegative, then insert its action (ADDR_POLICY_ACCEPT or
  * ADDR_POLICY_REJECT) for items that specify no action.