Merge commit 'mikeperry/bandwidth-voting-final'

11 files changed, 520 insertions, 84 deletions

diff --git a/doc/spec/dir-spec.txt b/doc/spec/dir-spec.txt
index 0a3b0c11bc..4bec7b00d0 100644
--- a/doc/spec/dir-spec.txt
+++ b/doc/spec/dir-spec.txt
@@ -1029,13 +1029,20 @@
         descriptors if they would cause "v" lines to be over 128 characters
         long.
 
-    "w" SP "Bandwidth=" INT NL
+    "w" SP "Bandwidth=" INT [SP "Measured=" INT] NL
 
         [At most once.]
 
         An estimate of the bandwidth of this server, in an arbitrary
         unit (currently kilobytes per second).  Used to weight router
-        selection.  Other weighting keywords may be added later.
+        selection. 
+
+        Additionally, the Measured= keyword is present in votes by 
+        participating bandwidth measurement authorites to indicate
+        a measured bandwidth currently produced by measuring stream 
+        capacities. 
+
+        Other weighting keywords may be added later.
         Clients MUST ignore keywords they do not recognize.
 
     "p" SP ("accept" / "reject") SP PortList NL
@@ -1178,6 +1185,13 @@
    rate limit from the router descriptor.  It is given in kilobytes
    per second, and capped at some arbitrary value (currently 10 MB/s).
 
+   The Measured= keyword on a "w" line vote is currently computed
+   by multiplying the previous published consensus bandwidth by the 
+   ratio of the measured average node stream capacity to the network 
+   average. If 3 or more authorities provide a Measured= keyword for 
+   a router, the authorites produce a consensus containing a "w" 
+   Bandwidth= keyword equal to the median of the Measured= votes.
+
    The ports listed in a "p" line should be taken as those ports for
    which the router's exit policy permits 'most' addresses, ignoring any
    accept not for all addresses, ignoring all rejects for private
@@ -1260,6 +1274,11 @@
           one, breaking ties in favor of the lexicographically larger
           vote.)  The port list is encoded as specified in 3.4.2.
 
+        * If consensus-method 6 or later is in use and if 3 or more 
+          authorities provide a Measured= keyword in their votes for 
+          a router, the authorities produce a consensus containing a 
+          Bandwidth= keyword equal to the median of the Measured= votes.
+
      The signatures at the end of a consensus document are sorted in
      ascending order by identity digest.
 
@@ -1280,6 +1299,7 @@
      "3" -- Added legacy ID key support to aid in authority ID key rollovers
      "4" -- No longer list routers that are not running in the consensus
      "5" -- adds support for "w" and "p" lines.
+     "6" -- Prefers measured bandwidth values rather than advertised
 
    Before generating a consensus, an authority must decide which consensus
    method to use.  To do this, it looks for the highest version number
diff --git a/src/common/compat.c b/src/common/compat.c
index d62b1ce1f4..29425c2492 100644
--- a/src/common/compat.c
+++ b/src/common/compat.c
@@ -398,6 +398,37 @@ const char TOR_TOLOWER_TABLE[256] = {
   240,241,242,243,244,245,246,247,248,249,250,251,252,253,254,255,
 };
 
+/** Implementation of strtok_r for platforms whose coders haven't figured out
+ * how to write one.  Hey guys!  You can use this code here for free! */
+char *
+tor_strtok_r_impl(char *str, const char *sep, char **lasts)
+{
+  char *cp, *start;
+  if (str)
+    start = cp = *lasts = str;
+  else if (!*lasts)
+    return NULL;
+  else
+    start = cp = *lasts;
+
+  tor_assert(*sep);
+  if (sep[1]) {
+    while (*cp && !strchr(sep, *cp))
+      ++cp;
+  } else {
+    tor_assert(strlen(sep) == 1);
+    cp = strchr(cp, *sep);
+  }
+
+  if (!cp || !*cp) {
+    *lasts = NULL;
+  } else {
+    *cp++ = '\0';
+    *lasts = cp;
+  }
+  return start;
+}
+
 #ifdef MS_WINDOWS
 /** Take a filename and return a pointer to its final element.  This
  * function is called on __FILE__ to fix a MSVC nit where __FILE__
diff --git a/src/common/compat.h b/src/common/compat.h
index 4d5a016cf2..edd09d8683 100644
--- a/src/common/compat.h
+++ b/src/common/compat.h
@@ -267,6 +267,13 @@ extern const char TOR_TOLOWER_TABLE[];
 #define TOR_TOLOWER(c) (TOR_TOLOWER_TABLE[(uint8_t)c])
 #define TOR_TOUPPER(c) (TOR_TOUPPER_TABLE[(uint8_t)c])
 
+char *tor_strtok_r_impl(char *str, const char *sep, char **lasts);
+#ifdef HAVE_STRTOK_R
+#define tor_strtok_r(str, sep, lasts) strtok_r(str, sep, lasts)
+#else
+#define tor_strtok_r(str, sep, lasts) tor_strtok_r_impl(str, sep, lasts)
+#endif
+
 #ifdef MS_WINDOWS
 #define _SHORT_FILE_ (tor_fix_source_file(__FILE__))
 const char *tor_fix_source_file(const char *fname);
diff --git a/src/or/config.c b/src/or/config.c
index 0b580876fb..de6bfcf680 100644
--- a/src/or/config.c
+++ b/src/or/config.c
@@ -338,6 +338,7 @@ static config_var_t _option_vars[] = {
   V(V3AuthDistDelay,             INTERVAL, "5 minutes"),
   V(V3AuthNIntervalsValid,       UINT,     "3"),
   V(V3AuthUseLegacyKey,          BOOL,     "0"),
+  V(V3BandwidthsFile,            FILENAME, NULL),
   VAR("VersioningAuthoritativeDirectory",BOOL,VersioningAuthoritativeDir, "0"),
   V(VirtualAddrNetwork,          STRING,   "127.192.0.0/10"),
   V(WarnPlaintextPorts,          CSV,      "23,109,110,143"),
@@ -3210,6 +3211,10 @@ options_validate(or_options_t *old_options, or_options_t *options,
           options->V3AuthoritativeDir))
       REJECT("AuthoritativeDir is set, but none of "
              "(Bridge/HS/V1/V2/V3)AuthoritativeDir is set.");
+    /* If we have a v3bandwidthsfile and it's broken, complain on startup */
+    if (options->V3BandwidthsFile && !old_options) {
+      dirserv_read_measured_bandwidths(options->V3BandwidthsFile, NULL);
+    }
   }
 
   if (options->AuthoritativeDir && !options->DirPort)
diff --git a/src/or/dirserv.c b/src/or/dirserv.c
index a731e334c8..a240fd4bbb 100644
--- a/src/or/dirserv.c
+++ b/src/or/dirserv.c
@@ -63,6 +63,9 @@ static signed_descriptor_t *get_signed_descriptor_by_fp(const char *fp,
                                                         time_t publish_cutoff);
 static int dirserv_add_extrainfo(extrainfo_t *ei, const char **msg);
 
+/************** Measured Bandwidth parsing code ******/
+#define MAX_MEASUREMENT_AGE (3*24*60*60) /* 3 days */
+
 /************** Fingerprint handling code ************/
 
 #define FP_NAMED   1  /**< Listed in fingerprint file. */
@@ -1855,16 +1858,18 @@ version_from_platform(const char *platform)
  * which has at least <b>buf_len</b> free characters.  Do NUL-termination.
  * Use the same format as in network-status documents.  If <b>version</b> is
  * non-NULL, add a "v" line for the platform.  Return 0 on success, -1 on
- * failure.  If <b>first_line_only</b> is true, don't include any flags
- * or version line.
+ * failure.
+ *
+ * The format argument has three possible values:
+ *   NS_V2 - Output an entry suitable for a V2 NS opinion document
+ *   NS_V3_CONSENSUS - Output the first portion of a V3 NS consensus entry
+ *   NS_V3_VOTE - Output a complete V3 NS vote
+ *   NS_CONTROL_PORT - Output a NS docunent for the control port
  */
 int
 routerstatus_format_entry(char *buf, size_t buf_len,
                           routerstatus_t *rs, const char *version,
-                          int first_line_only, int v2_format)
-/* XXX: first_line_only and v2_format should probably be be both
- *      replaced by a single purpose parameter.
- */
+                          routerstatus_format_type_t format)
 {
   int r;
   struct in_addr in;
@@ -1895,7 +1900,12 @@ routerstatus_format_entry(char *buf, size_t buf_len,
     log_warn(LD_BUG, "Not enough space in buffer.");
     return -1;
   }
-  if (first_line_only)
+
+  /* TODO: Maybe we want to pass in what we need to build the rest of
+   * this here, instead of in the caller. Then we could use the
+   * networkstatus_type_t values, with an additional control port value
+   * added -MP */
+  if (format == NS_V3_CONSENSUS)
     return 0;
 
   cp = buf + strlen(buf);
@@ -1932,62 +1942,87 @@ routerstatus_format_entry(char *buf, size_t buf_len,
     cp += strlen(cp);
   }
 
-  if (!v2_format) {
+  if (format != NS_V2) {
     routerinfo_t* desc = router_get_by_digest(rs->identity_digest);
+    uint32_t bw;
+
+    if (format != NS_CONTROL_PORT) {
+      /* Blow up more or less nicely if we didn't get anything or not the
+       * thing we expected.
+       */
+      if (!desc) {
+        char id[HEX_DIGEST_LEN+1];
+        char dd[HEX_DIGEST_LEN+1];
+
+        base16_encode(id, sizeof(id), rs->identity_digest, DIGEST_LEN);
+        base16_encode(dd, sizeof(dd), rs->descriptor_digest, DIGEST_LEN);
+        log_warn(LD_BUG, "Cannot get any descriptor for %s "
+            "(wanted descriptor %s).",
+            id, dd);
+        return -1;
+      };
+
+      /* This assert can fire for the control port, because
+       * it can request NS documents before all descriptors
+       * have been fetched. */
+      if (memcmp(desc->cache_info.signed_descriptor_digest,
+            rs->descriptor_digest,
+            DIGEST_LEN)) {
+        char rl_d[HEX_DIGEST_LEN+1];
+        char rs_d[HEX_DIGEST_LEN+1];
+        char id[HEX_DIGEST_LEN+1];
+
+        base16_encode(rl_d, sizeof(rl_d),
+            desc->cache_info.signed_descriptor_digest, DIGEST_LEN);
+        base16_encode(rs_d, sizeof(rs_d), rs->descriptor_digest, DIGEST_LEN);
+        base16_encode(id, sizeof(id), rs->identity_digest, DIGEST_LEN);
+        log_err(LD_BUG, "descriptor digest in routerlist does not match "
+            "the one in routerstatus: %s vs %s "
+            "(router %s)\n",
+            rl_d, rs_d, id);
+
+        tor_assert(!memcmp(desc->cache_info.signed_descriptor_digest,
+              rs->descriptor_digest,
+              DIGEST_LEN));
+      };
+    }
 
-    /* Blow up more or less nicely if we didn't get anything or not the
-     * thing we expected.
-     */
-    if (!desc) {
-      char id[HEX_DIGEST_LEN+1];
-      char dd[HEX_DIGEST_LEN+1];
-
-      base16_encode(id, sizeof(id), rs->identity_digest, DIGEST_LEN);
-      base16_encode(dd, sizeof(dd), rs->descriptor_digest, DIGEST_LEN);
-      log_warn(LD_BUG, "Cannot get any descriptor for %s "
-                       "(wanted descriptor %s).",
-               id, dd);
-      return -1;
-    };
-    if (memcmp(desc->cache_info.signed_descriptor_digest,
-               rs->descriptor_digest,
-               DIGEST_LEN)) {
-      char rl_d[HEX_DIGEST_LEN+1];
-      char rs_d[HEX_DIGEST_LEN+1];
-      char id[HEX_DIGEST_LEN+1];
-
-      base16_encode(rl_d, sizeof(rl_d),
-                    desc->cache_info.signed_descriptor_digest, DIGEST_LEN);
-      base16_encode(rs_d, sizeof(rs_d), rs->descriptor_digest, DIGEST_LEN);
-      base16_encode(id, sizeof(id), rs->identity_digest, DIGEST_LEN);
-      log_err(LD_BUG, "descriptor digest in routerlist does not match "
-                      "the one in routerstatus: %s vs %s "
-                      "(router %s)\n",
-              rl_d, rs_d, id);
-
-      tor_assert(!memcmp(desc->cache_info.signed_descriptor_digest,
-                       rs->descriptor_digest,
-                       DIGEST_LEN));
-    };
-
+    if (format == NS_CONTROL_PORT && rs->has_bandwidth) {
+      bw = rs->bandwidth;
+    } else {
+      tor_assert(desc);
+      bw = router_get_advertised_bandwidth_capped(desc) / 1000;
+    }
     r = tor_snprintf(cp, buf_len - (cp-buf),
-                     "w Bandwidth=%d\n",
-                     router_get_advertised_bandwidth_capped(desc) / 1024);
+                     "w Bandwidth=%d\n", bw);
+
     if (r<0) {
       log_warn(LD_BUG, "Not enough space in buffer.");
       return -1;
     }
     cp += strlen(cp);
+    if (format == NS_V3_VOTE && rs->has_measured_bw) {
+      *--cp = '\0'; /* Kill "\n" */
+      r = tor_snprintf(cp, buf_len - (cp-buf),
+                       " Measured=%d\n", rs->measured_bw);
+      if (r<0) {
+        log_warn(LD_BUG, "Not enough space in buffer for weight line.");
+        return -1;
+      }
+      cp += strlen(cp);
+    }
 
-    summary = policy_summarize(desc->exit_policy);
-    r = tor_snprintf(cp, buf_len - (cp-buf), "p %s\n", summary);
-    if (r<0) {
-      log_warn(LD_BUG, "Not enough space in buffer.");
+    if (desc) {
+      summary = policy_summarize(desc->exit_policy);
+      r = tor_snprintf(cp, buf_len - (cp-buf), "p %s\n", summary);
+      if (r<0) {
+        log_warn(LD_BUG, "Not enough space in buffer.");
+        tor_free(summary);
+        return -1;
+      }
+      cp += strlen(cp);
       tor_free(summary);
-      return -1;
     }
-    cp += strlen(cp);
-    tor_free(summary);
   }
 
   return 0;
@@ -2190,6 +2225,177 @@ router_clear_status_flags(routerinfo_t *router)
     router->is_bad_exit = router->is_bad_directory = 0;
 }
 
+/**
+ * Helper function to parse out a line in the measured bandwidth file
+ * into a measured_bw_line_t output structure. Returns -1 on failure
+ * or 0 on success.
+ */
+int
+measured_bw_line_parse(measured_bw_line_t *out, const char *orig_line)
+{
+  char *line = tor_strdup(orig_line);
+  char *cp = line;
+  int got_bw = 0;
+  int got_node_id = 0;
+  char *strtok_state; /* lame sauce d'jour */
+  cp = tor_strtok_r(cp, " \t", &strtok_state);
+
+  if (!cp) {
+    log_warn(LD_DIRSERV, "Invalid line in bandwidth file: %s",
+             escaped(orig_line));
+    tor_free(line);
+    return -1;
+  }
+
+  if (orig_line[strlen(orig_line)-1] != '\n') {
+    log_warn(LD_DIRSERV, "Incomplete line in bandwidth file: %s",
+             escaped(orig_line));
+    tor_free(line);
+    return -1;
+  }
+
+  do {
+    if (strcmpstart(cp, "bw=") == 0) {
+      int parse_ok = 0;
+      char *endptr;
+      if (got_bw) {
+        log_warn(LD_DIRSERV, "Double bw= in bandwidth file line: %s",
+                 escaped(orig_line));
+        tor_free(line);
+        return -1;
+      }
+      cp+=strlen("bw=");
+
+      out->bw = tor_parse_long(cp, 0, 0, LONG_MAX, &parse_ok, &endptr);
+      if (!parse_ok || (*endptr && !TOR_ISSPACE(*endptr))) {
+        log_warn(LD_DIRSERV, "Invalid bandwidth in bandwidth file line: %s",
+                 escaped(orig_line));
+        tor_free(line);
+        return -1;
+      }
+      got_bw=1;
+    } else if (strcmpstart(cp, "node_id=$") == 0) {
+      if (got_node_id) {
+        log_warn(LD_DIRSERV, "Double node_id= in bandwidth file line: %s",
+                 escaped(orig_line));
+        tor_free(line);
+        return -1;
+      }
+      cp+=strlen("node_id=$");
+
+      if (strlen(cp) != HEX_DIGEST_LEN ||
+          base16_decode(out->node_id, DIGEST_LEN, cp, HEX_DIGEST_LEN)) {
+        log_warn(LD_DIRSERV, "Invalid node_id in bandwidth file line: %s",
+                 escaped(orig_line));
+        tor_free(line);
+        return -1;
+      }
+      strncpy(out->node_hex, cp, sizeof(out->node_hex));
+      got_node_id=1;
+    }
+  } while ((cp = tor_strtok_r(NULL, " \t", &strtok_state)));
+
+  if (got_bw && got_node_id) {
+    tor_free(line);
+    return 0;
+  } else {
+    log_warn(LD_DIRSERV, "Incomplete line in bandwidth file: %s",
+             escaped(orig_line));
+    tor_free(line);
+    return -1;
+  }
+}
+
+/**
+ * Helper function to apply a parsed measurement line to a list
+ * of bandwidth statuses. Returns true if a line is found,
+ * false otherwise.
+ */
+int
+measured_bw_line_apply(measured_bw_line_t *parsed_line,
+                       smartlist_t *routerstatuses)
+{
+  routerstatus_t *rs = NULL;
+  if (!routerstatuses)
+    return 0;
+
+  rs = smartlist_bsearch(routerstatuses, parsed_line->node_id,
+                         compare_digest_to_routerstatus_entry);
+
+  if (rs) {
+    rs->has_measured_bw = 1;
+    rs->measured_bw = parsed_line->bw;
+  } else {
+    log_info(LD_DIRSERV, "Node ID %s not found in routerstatus list",
+             parsed_line->node_hex);
+  }
+
+  return rs != NULL;
+}
+
+/**
+ * Read the measured bandwidth file and apply it to the list of
+ * routerstatuses. Returns -1 on error, 0 otherwise.
+ */
+int
+dirserv_read_measured_bandwidths(const char *from_file,
+                                 smartlist_t *routerstatuses)
+{
+  char line[256];
+  FILE *fp = fopen(from_file, "r");
+  int applied_lines = 0;
+  time_t file_time;
+  int ok;
+  if (fp == NULL) {
+    log_warn(LD_CONFIG, "Can't open bandwidth file at configured location: %s",
+             from_file);
+    return -1;
+  }
+
+  if (!fgets(line, sizeof(line), fp)
+          || !strlen(line) || line[strlen(line)-1] != '\n') {
+    log_warn(LD_DIRSERV, "Long or truncated time in bandwidth file: %s",
+             escaped(line));
+    fclose(fp);
+    return -1;
+  }
+
+  line[strlen(line)-1] = '\0';
+  file_time = tor_parse_ulong(line, 10, 0, ULONG_MAX, &ok, NULL);
+  if (!ok) {
+    log_warn(LD_DIRSERV, "Non-integer time in bandwidth file: %s",
+             escaped(line));
+    fclose(fp);
+    return -1;
+  }
+
+  if ((time(NULL) - file_time) > MAX_MEASUREMENT_AGE) {
+    log_warn(LD_DIRSERV, "Bandwidth measurement file stale. Age: %u",
+             (unsigned)(time(NULL) - file_time));
+    fclose(fp);
+    return -1;
+  }
+
+  if (routerstatuses)
+    smartlist_sort(routerstatuses, compare_routerstatus_entries);
+
+  while (!feof(fp)) {
+    measured_bw_line_t parsed_line;
+    if (fgets(line, sizeof(line), fp) && strlen(line)) {
+      if (measured_bw_line_parse(&parsed_line, line) != -1) {
+        if (measured_bw_line_apply(&parsed_line, routerstatuses) > 0)
+          applied_lines++;
+      }
+    }
+  }
+
+  fclose(fp);
+  log_notice(LD_DIRSERV,
+             "Bandwidth measurement file successfully read. "
+             "Applied %d measurements.", applied_lines);
+  return 0;
+}
+
 /** Return a new networkstatus_t* containing our current opinion. (For v3
  * authorities) */
 networkstatus_t *
@@ -2289,9 +2495,15 @@ dirserv_generate_networkstatus_vote_obj(crypto_pk_env_t *private_key,
       smartlist_add(routerstatuses, vrs);
     }
   });
+
   smartlist_free(routers);
   digestmap_free(omit_as_sybil, NULL);
 
+  if (options->V3BandwidthsFile) {
+    dirserv_read_measured_bandwidths(options->V3BandwidthsFile,
+                                     routerstatuses);
+  }
+
   v3_out = tor_malloc_zero(sizeof(networkstatus_t));
 
   v3_out->type = NS_TYPE_VOTE;
@@ -2495,7 +2707,7 @@ generate_v2_networkstatus_opinion(void)
       if (digestmap_get(omit_as_sybil, ri->cache_info.identity_digest))
         clear_status_flags_on_sybil(&rs);
 
-      if (routerstatus_format_entry(outp, endp-outp, &rs, version, 0, 1)) {
+      if (routerstatus_format_entry(outp, endp-outp, &rs, version, NS_V2)) {
         log_warn(LD_BUG, "Unable to print router status.");
         tor_free(version);
         goto done;
diff --git a/src/or/dirvote.c b/src/or/dirvote.c
index 409c2fed69..aadece9096 100644
--- a/src/or/dirvote.c
+++ b/src/or/dirvote.c
@@ -103,7 +103,10 @@ format_networkstatus_vote(crypto_pk_env_t *private_signing_key,
     tor_snprintf(status, len,
                  "network-status-version 3\n"
                  "vote-status %s\n"
-                 "consensus-methods 1 2 3 4 5\n"
+                 /* XXX: If you change this value, you also need to
+                  * change consensus_method_is_supported().
+                  * Perhaps we should unify these somehow? */
+                 "consensus-methods 1 2 3 4 5 6\n"
                  "published %s\n"
                  "valid-after %s\n"
                  "fresh-until %s\n"
@@ -142,7 +145,7 @@ format_networkstatus_vote(crypto_pk_env_t *private_signing_key,
   SMARTLIST_FOREACH(v3_ns->routerstatus_list, vote_routerstatus_t *, vrs,
   {
     if (routerstatus_format_entry(outp, endp-outp, &vrs->status,
-                                  vrs->version, 0, 0) < 0) {
+                                  vrs->version, NS_V3_VOTE) < 0) {
       log_warn(LD_BUG, "Unable to print router status.");
       goto err;
     }
@@ -455,7 +458,10 @@ compute_consensus_method(smartlist_t *votes)
 static int
 consensus_method_is_supported(int method)
 {
-  return (method >= 1) && (method <= 5);
+  /* XXX: If you change this value, you also need to change
+   * format_networkstatus_vote(). Perhaps we should unify
+   * these somehow? */
+  return (method >= 1) && (method <= 6);
 }
 
 /** Helper: given <b>lst</b>, a list of version strings such that every
@@ -701,7 +707,10 @@ networkstatus_compute_consensus(smartlist_t *votes,
     smartlist_t *versions = smartlist_create();
     smartlist_t *exitsummaries = smartlist_create();
     uint32_t *bandwidths = tor_malloc(sizeof(uint32_t) * smartlist_len(votes));
+    uint32_t *measured_bws = tor_malloc(sizeof(uint32_t) *
+                                        smartlist_len(votes));
     int num_bandwidths;
+    int num_mbws;
 
     int *n_voter_flags; /* n_voter_flags[j] is the number of flags that
                          * votes[j] knows about. */
@@ -835,6 +844,7 @@ networkstatus_compute_consensus(smartlist_t *votes,
       smartlist_clear(chosen_flags);
       smartlist_clear(versions);
       num_bandwidths = 0;
+      num_mbws = 0;
 
       /* Okay, go through all the entries for this digest. */
       SMARTLIST_FOREACH_BEGIN(votes, networkstatus_t *, v) {
@@ -868,6 +878,9 @@ networkstatus_compute_consensus(smartlist_t *votes,
         }
 
         /* count bandwidths */
+        if (rs->status.has_measured_bw)
+          measured_bws[num_mbws++] = rs->status.measured_bw;
+
         if (rs->status.has_bandwidth)
           bandwidths[num_bandwidths++] = rs->status.bandwidth;
       } SMARTLIST_FOREACH_END(v);
@@ -945,7 +958,10 @@ networkstatus_compute_consensus(smartlist_t *votes,
       }
 
       /* Pick a bandwidth */
-      if (consensus_method >= 5 && num_bandwidths > 0) {
+      if (consensus_method >= 6 && num_mbws > 2) {
+        rs_out.has_bandwidth = 1;
+        rs_out.bandwidth = median_uint32(measured_bws, num_mbws);
+      } else if (consensus_method >= 5 && num_bandwidths > 0) {
         rs_out.has_bandwidth = 1;
         rs_out.bandwidth = median_uint32(bandwidths, num_bandwidths);
       }
@@ -1036,7 +1052,8 @@ networkstatus_compute_consensus(smartlist_t *votes,
 
       /* Okay!! Now we can write the descriptor... */
       /*     First line goes into "buf". */
-      routerstatus_format_entry(buf, sizeof(buf), &rs_out, NULL, 1, 0);
+      routerstatus_format_entry(buf, sizeof(buf), &rs_out, NULL,
+                                NS_V3_CONSENSUS);
       smartlist_add(chunks, tor_strdup(buf));
       /*     Second line is all flags.  The "\n" is missing. */
       smartlist_add(chunks,
@@ -1055,8 +1072,10 @@ networkstatus_compute_consensus(smartlist_t *votes,
           log_warn(LD_BUG, "Not enough space in buffer for weight line.");
           *buf = '\0';
         }
+
         smartlist_add(chunks, tor_strdup(buf));
       };
+
       /*     Now the exitpolicy summary line. */
       if (rs_out.has_exitsummary) {
         char buf[MAX_POLICY_LINE_LEN+1];
diff --git a/src/or/eventdns.c b/src/or/eventdns.c
index 9578b24cae..b413b6ae97 100644
--- a/src/or/eventdns.c
+++ b/src/or/eventdns.c
@@ -2889,14 +2889,6 @@ evdns_resolv_set_defaults(int flags) {
 	if (flags & DNS_OPTION_NAMESERVERS) evdns_nameserver_ip_add("127.0.0.1");
 }
 
-#ifndef HAVE_STRTOK_R
-static char *
-strtok_r(char *s, const char *delim, char **state) {
-	(void)state;
-	return strtok(s, delim);
-}
-#endif
-
 /* helper version of atoi which returns -1 on error */
 static int
 strtoint(const char *const str) {
@@ -2973,9 +2965,9 @@ static void
 resolv_conf_parse_line(char *const start, int flags) {
 	char *strtok_state;
 	static const char *const delims = " \t";
-#define NEXT_TOKEN strtok_r(NULL, delims, &strtok_state)
+#define NEXT_TOKEN tor_strtok_r(NULL, delims, &strtok_state)
 
-	char *const first_token = strtok_r(start, delims, &strtok_state);
+	char *const first_token = tor_strtok_r(start, delims, &strtok_state);
 	if (!first_token) return;
 
 	if (!strcmp(first_token, "nameserver") && (flags & DNS_OPTION_NAMESERVERS)) {
diff --git a/src/or/networkstatus.c b/src/or/networkstatus.c
index 97353c01da..b022999607 100644
--- a/src/or/networkstatus.c
+++ b/src/or/networkstatus.c
@@ -780,8 +780,8 @@ networkstatus_v2_list_clean(time_t now)
 
 /** Helper for bsearching a list of routerstatus_t pointers: compare a
  * digest in the key to the identity digest of a routerstatus_t. */
-static int
-_compare_digest_to_routerstatus_entry(const void *_key, const void **_member)
+int
+compare_digest_to_routerstatus_entry(const void *_key, const void **_member)
 {
   const char *key = _key;
   const routerstatus_t *rs = *_member;
@@ -794,7 +794,7 @@ routerstatus_t *
 networkstatus_v2_find_entry(networkstatus_v2_t *ns, const char *digest)
 {
   return smartlist_bsearch(ns->entries, digest,
-                           _compare_digest_to_routerstatus_entry);
+                           compare_digest_to_routerstatus_entry);
 }
 
 /** Return the entry in <b>ns</b> for the identity digest <b>digest</b>, or
@@ -803,7 +803,7 @@ routerstatus_t *
 networkstatus_vote_find_entry(networkstatus_t *ns, const char *digest)
 {
   return smartlist_bsearch(ns->routerstatus_list, digest,
-                           _compare_digest_to_routerstatus_entry);
+                           compare_digest_to_routerstatus_entry);
 }
 
 /*XXXX make this static once functions are moved into this file. */
@@ -815,7 +815,7 @@ networkstatus_vote_find_entry_idx(networkstatus_t *ns,
                                   const char *digest, int *found_out)
 {
   return smartlist_bsearch_idx(ns->routerstatus_list, digest,
-                               _compare_digest_to_routerstatus_entry,
+                               compare_digest_to_routerstatus_entry,
                                found_out);
 }
 
@@ -868,7 +868,7 @@ router_get_consensus_status_by_id(const char *digest)
   if (!current_consensus)
     return NULL;
   return smartlist_bsearch(current_consensus->routerstatus_list, digest,
-                           _compare_digest_to_routerstatus_entry);
+                           compare_digest_to_routerstatus_entry);
 }
 
 /** Given a nickname (possibly verbose, possibly a hexadecimal digest), return
@@ -1827,7 +1827,7 @@ char *
 networkstatus_getinfo_helper_single(routerstatus_t *rs)
 {
   char buf[RS_ENTRY_LEN+1];
-  routerstatus_format_entry(buf, sizeof(buf), rs, NULL, 0, 1);
+  routerstatus_format_entry(buf, sizeof(buf), rs, NULL, NS_CONTROL_PORT);
   return tor_strdup(buf);
 }
 
diff --git a/src/or/or.h b/src/or/or.h
index 253e89af85..7ece877504 100644
--- a/src/or/or.h
+++ b/src/or/or.h
@@ -1509,6 +1509,9 @@ typedef struct routerstatus_t {
 
   unsigned int has_bandwidth:1; /**< The vote/consensus had bw info */
   unsigned int has_exitsummary:1; /**< The vote/consensus had exit summaries */
+  unsigned int has_measured_bw:1; /**< The vote/consensus had a measured bw */
+
+  uint32_t measured_bw; /**< Measured bandwidth (capacity) of the router */
 
   uint32_t bandwidth; /**< Bandwidth (capacity) of the router as reported in
                        * the vote/consensus, in kilobytes/sec. */
@@ -2546,6 +2549,9 @@ typedef struct {
    * migration purposes? */
   int V3AuthUseLegacyKey;
 
+  /** Location of bandwidth measurement file */
+  char *V3BandwidthsFile;
+
   /** The length of time that we think an initial consensus should be fresh.
    * Only altered on testing networks. */
   int TestingV3AuthInitialVotingInterval;
@@ -3444,8 +3450,8 @@ download_status_mark_impossible(download_status_t *dl)
  * Running Stable Unnamed V2Dir Valid\n". */
 #define MAX_FLAG_LINE_LEN 96
 /** Length of "w" line for weighting.  Currently at most
- * "w Bandwidth=<uint32t>\n" */
-#define MAX_WEIGHT_LINE_LEN (13+10)
+ * "w Bandwidth=<uint32t> Measured=<uint32t>\n" */
+#define MAX_WEIGHT_LINE_LEN (12+10+10+10+1)
 /** Maximum length of an exit policy summary line. */
 #define MAX_POLICY_LINE_LEN (3+MAX_EXITPOLICY_SUMMARY_LEN)
 /** Amount of space to allocate for each entry: r, s, and v lines. */
@@ -3528,13 +3534,32 @@ int dirserv_remove_old_statuses(smartlist_t *fps, time_t cutoff);
 int dirserv_have_any_serverdesc(smartlist_t *fps, int spool_src);
 size_t dirserv_estimate_data_size(smartlist_t *fps, int is_serverdescs,
                                   int compressed);
+typedef enum {
+  NS_V2, NS_V3_CONSENSUS, NS_V3_VOTE, NS_CONTROL_PORT
+} routerstatus_format_type_t;
 int routerstatus_format_entry(char *buf, size_t buf_len,
                               routerstatus_t *rs, const char *platform,
-                              int first_line_only, int v2_format);
+                              routerstatus_format_type_t format);
 void dirserv_free_all(void);
 void cached_dir_decref(cached_dir_t *d);
 cached_dir_t *new_cached_dir(char *s, time_t published);
 
+#ifdef DIRSERV_PRIVATE
+typedef struct measured_bw_line_t {
+  char node_id[DIGEST_LEN];
+  char node_hex[MAX_HEX_NICKNAME_LEN+1];
+  long int bw;
+} measured_bw_line_t;
+
+int measured_bw_line_parse(measured_bw_line_t *out, const char *line);
+
+int measured_bw_line_apply(measured_bw_line_t *parsed_line,
+                           smartlist_t *routerstatuses);
+#endif
+
+int dirserv_read_measured_bandwidths(const char *from_file,
+                                     smartlist_t *routerstatuses);
+
 /********************************* dirvote.c ************************/
 
 /** Lowest allowable value for VoteSeconds. */
@@ -3848,6 +3873,8 @@ int router_set_networkstatus_v2(const char *s, time_t arrived_at,
                              v2_networkstatus_source_t source,
                              smartlist_t *requested_fingerprints);
 void networkstatus_v2_list_clean(time_t now);
+int compare_digest_to_routerstatus_entry(const void *_key,
+                                         const void **_member);
 routerstatus_t *networkstatus_v2_find_entry(networkstatus_v2_t *ns,
                                          const char *digest);
 routerstatus_t *networkstatus_vote_find_entry(networkstatus_t *ns,
@@ -4712,6 +4739,7 @@ void sort_version_list(smartlist_t *lst, int remove_duplicates);
 void assert_addr_policy_ok(smartlist_t *t);
 void dump_distinct_digest_count(int severity);
 
+int compare_routerstatus_entries(const void **_a, const void **_b);
 networkstatus_v2_t *networkstatus_v2_parse_from_string(const char *s);
 networkstatus_t *networkstatus_parse_vote_from_string(const char *s,
                                                  const char **eos_out,
diff --git a/src/or/routerparse.c b/src/or/routerparse.c
index 8021158e31..c1a7fbcfae 100644
--- a/src/or/routerparse.c
+++ b/src/or/routerparse.c
@@ -1924,6 +1924,16 @@ routerstatus_parse_entry_from_string(memarea_t *area,
           goto err;
         }
         rs->has_bandwidth = 1;
+      } else if (!strcmpstart(tok->args[i], "Measured=")) {
+        int ok;
+        rs->measured_bw = tor_parse_ulong(strchr(tok->args[i], '=')+1, 10,
+                                          0, UINT32_MAX, &ok, NULL);
+        if (!ok) {
+          log_warn(LD_DIR, "Invalid Measured Bandwidth %s",
+                   escaped(tok->args[i]));
+          goto err;
+        }
+        rs->has_measured_bw = 1;
       }
     }
   }
@@ -1966,8 +1976,8 @@ routerstatus_parse_entry_from_string(memarea_t *area,
 }
 
 /** Helper to sort a smartlist of pointers to routerstatus_t */
-static int
-_compare_routerstatus_entries(const void **_a, const void **_b)
+int
+compare_routerstatus_entries(const void **_a, const void **_b)
 {
   const routerstatus_t *a = *_a, *b = *_b;
   return memcmp(a->identity_digest, b->identity_digest, DIGEST_LEN);
@@ -2114,8 +2124,8 @@ networkstatus_v2_parse_from_string(const char *s)
                                                    NULL, NULL, 0)))
       smartlist_add(ns->entries, rs);
   }
-  smartlist_sort(ns->entries, _compare_routerstatus_entries);
-  smartlist_uniq(ns->entries, _compare_routerstatus_entries,
+  smartlist_sort(ns->entries, compare_routerstatus_entries);
+  smartlist_uniq(ns->entries, compare_routerstatus_entries,
                  _free_duplicate_routerstatus_entry);
 
   if (tokenize_string(area,s, NULL, footer_tokens, dir_footer_token_table,0)) {
diff --git a/src/or/test.c b/src/or/test.c
index dffb0a5ade..b86ced723a 100644
--- a/src/or/test.c
+++ b/src/or/test.c
@@ -3232,6 +3232,72 @@ test_dirutil(void)
   smartlist_free(sl);
 }
 
+static void
+test_dirutil_measured_bw(void)
+{
+  measured_bw_line_t mbwl;
+  int i;
+  const char *lines_pass[] = {
+    "node_id=$557365204145532d32353620696e73746561642e bw=1024\n",
+    "node_id=$557365204145532d32353620696e73746561642e\t  bw=1024 \n",
+    " node_id=$557365204145532d32353620696e73746561642e  bw=1024\n",
+    "\tnoise\tnode_id=$557365204145532d32353620696e73746561642e  "
+                "bw=1024 junk=007\n",
+    "misc=junk node_id=$557365204145532d32353620696e73746561642e  "
+                "bw=1024 junk=007\n",
+    "end"
+  };
+  const char *lines_fail[] = {
+    /* Test possible python stupidity on input */
+    "node_id=None bw=1024\n",
+    "node_id=$None bw=1024\n",
+    "node_id=$557365204145532d32353620696e73746561642e bw=None\n",
+    "node_id=$557365204145532d32353620696e73746561642e bw=1024.0\n",
+    "node_id=$557365204145532d32353620696e73746561642e bw=.1024\n",
+    "node_id=$557365204145532d32353620696e73746561642e bw=1.024\n",
+    "node_id=$557365204145532d32353620696e73746561642e bw=1024 bw=0\n",
+    "node_id=$557365204145532d32353620696e73746561642e bw=1024 bw=None\n",
+    "node_id=$557365204145532d32353620696e73746561642e bw=-1024\n",
+    /* Test incomplete writes due to race conditions, partial copies, etc */
+    "node_i",
+    "node_i\n",
+    "node_id=",
+    "node_id=\n",
+    "node_id=$557365204145532d32353620696e73746561642e bw=",
+    "node_id=$557365204145532d32353620696e73746561642e bw=1024",
+    "node_id=$557365204145532d32353620696e73746561642e bw=\n",
+    "node_id=$557365204145532d32353620696e7374",
+    "node_id=$557365204145532d32353620696e7374\n",
+    "",
+    "\n",
+    " \n ",
+    " \n\n",
+    /* Test assorted noise */
+    " node_id= ",
+    "node_id==$557365204145532d32353620696e73746561642e bw==1024\n",
+    "node_id=$55736520414552d32353620696e73746561642e bw=1024\n",
+    "node_id=557365204145532d32353620696e73746561642e bw=1024\n",
+    "node_id= $557365204145532d32353620696e73746561642e bw=0.23\n",
+    "end"
+  };
+
+  for (i = 0; strcmp(lines_fail[i], "end"); i++) {
+    //fprintf(stderr, "Testing: %s\n", lines_fail[i]);
+    test_assert(measured_bw_line_parse(&mbwl, lines_fail[i]) == -1);
+  }
+
+  for (i = 0; strcmp(lines_pass[i], "end"); i++) {
+    //fprintf(stderr, "Testing: %s %d\n", lines_pass[i], TOR_ISSPACE('\n'));
+    test_assert(measured_bw_line_parse(&mbwl, lines_pass[i]) == 0);
+    test_assert(mbwl.bw == 1024);
+    test_assert(strcmp(mbwl.node_hex,
+                "557365204145532d32353620696e73746561642e") == 0);
+  }
+
+done:
+  return;
+}
+
 extern const char AUTHORITY_CERT_1[];
 extern const char AUTHORITY_SIGNKEY_1[];
 extern const char AUTHORITY_CERT_2[];
@@ -3512,6 +3578,17 @@ test_v3_networkstatus(void)
   test_eq(rs->dir_port, 0);
   test_eq(vrs->flags, U64_LITERAL(254)); // all flags except "authority."
 
+  {
+    measured_bw_line_t mbw;
+    memset(mbw.node_id, 33, sizeof(mbw.node_id));
+    mbw.bw = 1024;
+    test_assert(measured_bw_line_apply(&mbw,
+                v1->routerstatus_list) == 1);
+    vrs = smartlist_get(v1->routerstatus_list, 2);
+    test_assert(vrs->status.has_measured_bw &&
+                vrs->status.measured_bw == 1024);
+  }
+
   /* Generate second vote. It disagrees on some of the times,
    * and doesn't list versions, and knows some crazy flags */
   vote->published = now+1;
@@ -4284,6 +4361,39 @@ test_util_datadir(void)
   tor_free(f);
 }
 
+static void
+test_util_strtok(void)
+{
+  char buf[128];
+  char buf2[128];
+  char *cp1, *cp2;
+  strlcpy(buf, "Graved on the dark in gestures of descent", sizeof(buf));
+  strlcpy(buf2, "they.seemed;their!own;most.perfect;monument", sizeof(buf2));
+  /*  -- "Year's End", Richard Wilbur */
+
+  test_streq("Graved", tor_strtok_r_impl(buf, " ", &cp1));
+  test_streq("they", tor_strtok_r_impl(buf2, ".!..;!", &cp2));
+#define S1() tor_strtok_r_impl(NULL, " ", &cp1)
+#define S2() tor_strtok_r_impl(NULL, ".!..;!", &cp2)
+  test_streq("on", S1());
+  test_streq("the", S1());
+  test_streq("dark", S1());
+  test_streq("seemed", S2());
+  test_streq("their", S2());
+  test_streq("own", S2());
+  test_streq("in", S1());
+  test_streq("gestures", S1());
+  test_streq("of", S1());
+  test_streq("most", S2());
+  test_streq("perfect", S2());
+  test_streq("descent", S1());
+  test_streq("monument", S2());
+  test_assert(NULL == S1());
+  test_assert(NULL == S2());
+ done:
+  ;
+}
+
 /** Test AES-CTR encryption and decryption with IV. */
 static void
 test_crypto_aes_iv(void)
@@ -4692,9 +4802,11 @@ static struct {
   SUBENT(util, threads),
   SUBENT(util, order_functions),
   SUBENT(util, sscanf),
+  SUBENT(util, strtok),
   ENT(onion_handshake),
   ENT(dir_format),
   ENT(dirutil),
+  SUBENT(dirutil, measured_bw),
   ENT(v3_networkstatus),
   ENT(policies),
   ENT(rend_fns),