Merge branch 'bug9321_rerebase'

Conflicts:
	src/or/dirvote.h
	src/test/include.am
	src/test/test_entrynodes.c

11 files changed, 666 insertions, 20 deletions

diff --git a/src/or/config.c b/src/or/config.c
index 92a1ce1f22..f2c6221c35 100644
--- a/src/or/config.c
+++ b/src/or/config.c
@@ -417,6 +417,7 @@ static config_var_t option_vars_[] = {
   V(UseBridges,                  BOOL,     "0"),
   V(UseEntryGuards,              BOOL,     "1"),
   V(UseEntryGuardsAsDirGuards,   BOOL,     "1"),
+  V(UseGuardFraction,            AUTOBOOL, "auto"),
   V(UseMicrodescriptors,         AUTOBOOL, "auto"),
   V(UseNTorHandshake,            AUTOBOOL, "1"),
   V(User,                        STRING,   NULL),
@@ -434,6 +435,7 @@ static config_var_t option_vars_[] = {
   V(V3AuthNIntervalsValid,       UINT,     "3"),
   V(V3AuthUseLegacyKey,          BOOL,     "0"),
   V(V3BandwidthsFile,            FILENAME, NULL),
+  V(GuardfractionFile,           FILENAME, NULL),
   VAR("VersioningAuthoritativeDirectory",BOOL,VersioningAuthoritativeDir, "0"),
   V(VirtualAddrNetworkIPv4,      STRING,   "127.192.0.0/10"),
   V(VirtualAddrNetworkIPv6,      STRING,   "[FE80::]/10"),
@@ -2790,6 +2792,10 @@ options_validate(or_options_t *old_options, or_options_t *options,
     if (options->V3BandwidthsFile && !old_options) {
       dirserv_read_measured_bandwidths(options->V3BandwidthsFile, NULL);
     }
+    /* same for guardfraction file */
+    if (options->GuardfractionFile && !old_options) {
+      dirserv_read_guardfraction_file(options->GuardfractionFile, NULL);
+    }
   }
 
   if (options->AuthoritativeDir && !options->DirPort_set)
diff --git a/src/or/dirserv.c b/src/or/dirserv.c
index 7bc91985a2..114b26163d 100644
--- a/src/or/dirserv.c
+++ b/src/or/dirserv.c
@@ -1915,6 +1915,13 @@ routerstatus_format_entry(const routerstatus_t *rs, const char *version,
       smartlist_add_asprintf(chunks,
                        " Measured=%d", vrs->measured_bw_kb);
     }
+    /* Write down guardfraction information if we have it. */
+    if (format == NS_V3_VOTE && vrs && vrs->status.has_guardfraction) {
+      smartlist_add_asprintf(chunks,
+                             " GuardFraction=%d",
+                             vrs->status.guardfraction_percentage);
+    }
+
     smartlist_add(chunks, tor_strdup("\n"));
 
     if (desc) {
@@ -2144,6 +2151,319 @@ clear_status_flags_on_sybil(routerstatus_t *rs)
    * forget to add it to this clause. */
 }
 
+/** The guardfraction of the guard with identity fingerprint <b>guard_id</b>
+ *  is <b>guardfraction_percentage</b>. See if we have a vote routerstatus for
+ *  this guard in <b>vote_routerstatuses</b>, and if we do, register the
+ *  information to it.
+ *
+ *  Return 1 if we applied the information and 0 if we couldn't find a
+ *  matching guard.
+ *
+ * Requires that <b>vote_routerstatuses</b> be sorted.
+ */
+static int
+guardfraction_line_apply(const char *guard_id,
+                      uint32_t guardfraction_percentage,
+                      smartlist_t *vote_routerstatuses)
+{
+  vote_routerstatus_t *vrs = NULL;
+
+  tor_assert(vote_routerstatuses);
+
+  vrs = smartlist_bsearch(vote_routerstatuses, guard_id,
+                         compare_digest_to_vote_routerstatus_entry);
+
+  if (!vrs) {
+    return 0;
+  }
+
+  vrs->status.has_guardfraction = 1;
+  vrs->status.guardfraction_percentage = guardfraction_percentage;
+
+  return 1;
+}
+
+/* Given a guard line from a guardfraction file, parse it and register
+ * its information to <b>vote_routerstatuses</b>.
+ *
+ * Return:
+ * * 1 if the line was proper and its information got registered.
+ * * 0 if the line was proper but no currently active guard was found
+ *     to register the guardfraction information to.
+ * * -1 if the line could not be parsed and set <b>err_msg</b> to a
+      newly allocated string containing the error message.
+ */
+static int
+guardfraction_file_parse_guard_line(const char *guard_line,
+                                    smartlist_t *vote_routerstatuses,
+                                    char **err_msg)
+{
+  char guard_id[DIGEST_LEN];
+  uint32_t guardfraction;
+  char *inputs_tmp = NULL;
+  int num_ok = 1;
+
+  smartlist_t *sl = smartlist_new();
+  int retval = -1;
+
+  tor_assert(err_msg);
+
+  /* guard_line should contain something like this:
+     <hex digest> <guardfraction> <appearances> */
+  smartlist_split_string(sl, guard_line, " ",
+                         SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 3);
+  if (smartlist_len(sl) < 3) {
+    tor_asprintf(err_msg, "bad line '%s'", guard_line);
+    goto done;
+  }
+
+  inputs_tmp = smartlist_get(sl, 0);
+  if (strlen(inputs_tmp) != HEX_DIGEST_LEN ||
+      base16_decode(guard_id, DIGEST_LEN, inputs_tmp, HEX_DIGEST_LEN)) {
+    tor_asprintf(err_msg, "bad digest '%s'", inputs_tmp);
+    goto done;
+  }
+
+  inputs_tmp = smartlist_get(sl, 1);
+  /* Guardfraction is an integer in [0, 100]. */
+  guardfraction =
+    (uint32_t) tor_parse_long(inputs_tmp, 10, 0, 100, &num_ok, NULL);
+  if (!num_ok) {
+    tor_asprintf(err_msg, "wrong percentage '%s'", inputs_tmp);
+    goto done;
+  }
+
+  /* If routerstatuses were provided, apply this info to actual routers. */
+  if (vote_routerstatuses) {
+    retval = guardfraction_line_apply(guard_id, guardfraction,
+                                      vote_routerstatuses);
+  } else {
+    retval = 0; /* If we got this far, line was correctly formatted. */
+  }
+
+ done:
+
+  SMARTLIST_FOREACH(sl, char *, cp, tor_free(cp));
+  smartlist_free(sl);
+
+  return retval;
+}
+
+/** Given an inputs line from a guardfraction file, parse it and
+ *  register its information to <b>total_consensuses</b> and
+ *  <b>total_days</b>.
+ *
+ *  Return 0 if it parsed well. Return -1 if there was an error, and
+ *  set <b>err_msg</b> to a newly allocated string containing the
+ *  error message.
+ */
+static int
+guardfraction_file_parse_inputs_line(const char *inputs_line,
+                                     int *total_consensuses,
+                                     int *total_days,
+                                     char **err_msg)
+{
+  int retval = -1;
+  char *inputs_tmp = NULL;
+  int num_ok = 1;
+  smartlist_t *sl = smartlist_new();
+
+  tor_assert(err_msg);
+
+  /* Second line is inputs information:
+   *   n-inputs <total_consensuses> <total_days>. */
+  smartlist_split_string(sl, inputs_line, " ",
+                         SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 3);
+  if (smartlist_len(sl) < 2) {
+    tor_asprintf(err_msg, "incomplete line '%s'", inputs_line);
+    goto done;
+  }
+
+  inputs_tmp = smartlist_get(sl, 0);
+  *total_consensuses =
+    (int) tor_parse_long(inputs_tmp, 10, 0, INT_MAX, &num_ok, NULL);
+  if (!num_ok) {
+    tor_asprintf(err_msg, "unparseable consensus '%s'", inputs_tmp);
+    goto done;
+  }
+
+  inputs_tmp = smartlist_get(sl, 1);
+  *total_days =
+    (int) tor_parse_long(inputs_tmp, 10, 0, INT_MAX, &num_ok, NULL);
+  if (!num_ok) {
+    tor_asprintf(err_msg, "unparseable days '%s'", inputs_tmp);
+    goto done;
+  }
+
+  retval = 0;
+
+ done:
+  SMARTLIST_FOREACH(sl, char *, cp, tor_free(cp));
+  smartlist_free(sl);
+
+  return retval;
+}
+
+/* Maximum age of a guardfraction file that we are willing to accept. */
+#define MAX_GUARDFRACTION_FILE_AGE (7*24*60*60) /* approx a week */
+
+/** Static strings of guardfraction files. */
+#define GUARDFRACTION_DATE_STR "written-at"
+#define GUARDFRACTION_INPUTS "n-inputs"
+#define GUARDFRACTION_GUARD "guard-seen"
+#define GUARDFRACTION_VERSION "guardfraction-file-version"
+
+/** Given a guardfraction file in a string, parse it and register the
+ *  guardfraction information to the provided vote routerstatuses.
+ *
+ *  This is the rough format of the guardfraction file:
+ *
+ *      guardfraction-file-version 1
+ *      written-at <date and time>
+ *      n-inputs <number of consesuses parsed> <number of days considered>
+ *
+ *      guard-seen <fpr 1> <guardfraction percentage> <consensus appearances>
+ *      guard-seen <fpr 2> <guardfraction percentage> <consensus appearances>
+ *      guard-seen <fpr 3> <guardfraction percentage> <consensus appearances>
+ *      guard-seen <fpr 4> <guardfraction percentage> <consensus appearances>
+ *      guard-seen <fpr 5> <guardfraction percentage> <consensus appearances>
+ *      ...
+ *
+ *  Return -1 if the parsing failed and 0 if it went smoothly. Parsing
+ *  should tolerate errors in all lines but the written-at header.
+ */
+STATIC int
+dirserv_read_guardfraction_file_from_str(const char *guardfraction_file_str,
+                                      smartlist_t *vote_routerstatuses)
+{
+  config_line_t *front=NULL, *line;
+  int ret_tmp;
+  int retval = -1;
+  int current_line_n = 0; /* line counter for better log messages */
+
+  /* Guardfraction info to be parsed */
+  int total_consensuses = 0;
+  int total_days = 0;
+
+  /* Stats */
+  int guards_read_n = 0;
+  int guards_applied_n = 0;
+
+  /* Parse file and split it in lines */
+  ret_tmp = config_get_lines(guardfraction_file_str, &front, 0);
+  if (ret_tmp < 0) {
+    log_warn(LD_CONFIG, "Error reading from guardfraction file");
+    goto done;
+  }
+
+  /* Sort routerstatuses (needed later when applying guardfraction info) */
+  if (vote_routerstatuses)
+    smartlist_sort(vote_routerstatuses, compare_vote_routerstatus_entries);
+
+  for (line = front; line; line=line->next) {
+    current_line_n++;
+
+    if (!strcmp(line->key, GUARDFRACTION_VERSION)) {
+      int num_ok = 1;
+      unsigned int version;
+
+      version =
+        (unsigned int) tor_parse_long(line->value,
+                                      10, 0, INT_MAX, &num_ok, NULL);
+
+      if (!num_ok || version != 1) {
+        log_warn(LD_GENERAL, "Got unknown guardfraction version %d.", version);
+        goto done;
+      }
+    } else if (!strcmp(line->key, GUARDFRACTION_DATE_STR)) {
+      time_t file_written_at;
+      time_t now = time(NULL);
+
+      /* First line is 'written-at <date>' */
+      if (parse_iso_time(line->value, &file_written_at) < 0) {
+        log_warn(LD_CONFIG, "Guardfraction:%d: Bad date '%s'. Ignoring",
+                 current_line_n, line->value);
+        goto done; /* don't tolerate failure here. */
+      }
+      if (file_written_at < now - MAX_GUARDFRACTION_FILE_AGE) {
+        log_warn(LD_CONFIG, "Guardfraction:%d: was written very long ago '%s'",
+                 current_line_n, line->value);
+        goto done; /* don't tolerate failure here. */
+      }
+    } else if (!strcmp(line->key, GUARDFRACTION_INPUTS)) {
+      char *err_msg = NULL;
+
+      if (guardfraction_file_parse_inputs_line(line->value,
+                                               &total_consensuses,
+                                               &total_days,
+                                               &err_msg) < 0) {
+        log_warn(LD_CONFIG, "Guardfraction:%d: %s",
+                 current_line_n, err_msg);
+        tor_free(err_msg);
+        continue;
+      }
+
+    } else if (!strcmp(line->key, GUARDFRACTION_GUARD)) {
+      char *err_msg = NULL;
+
+      ret_tmp = guardfraction_file_parse_guard_line(line->value,
+                                                    vote_routerstatuses,
+                                                    &err_msg);
+      if (ret_tmp < 0) { /* failed while parsing the guard line */
+        log_warn(LD_CONFIG, "Guardfraction:%d: %s",
+                 current_line_n, err_msg);
+        tor_free(err_msg);
+        continue;
+      }
+
+      /* Successfully parsed guard line. Check if it was applied properly. */
+      guards_read_n++;
+      if (ret_tmp > 0) {
+        guards_applied_n++;
+      }
+    } else {
+      log_warn(LD_CONFIG, "Unknown guardfraction line %d (%s %s)",
+               current_line_n, line->key, line->value);
+    }
+  }
+
+  retval = 0;
+
+  log_info(LD_CONFIG,
+           "Successfully parsed guardfraction file with %d consensuses over "
+           "%d days. Parsed %d nodes and applied %d of them%s.",
+           total_consensuses, total_days, guards_read_n, guards_applied_n,
+           vote_routerstatuses ? "" : " (no routerstatus provided)" );
+
+ done:
+  config_free_lines(front);
+
+  if (retval < 0) {
+    return retval;
+  } else {
+    return guards_read_n;
+  }
+}
+
+/** Read a guardfraction file at <b>fname</b> and load all its
+ *  information to <b>vote_routerstatuses</b>. */
+int
+dirserv_read_guardfraction_file(const char *fname,
+                             smartlist_t *vote_routerstatuses)
+{
+  char *guardfraction_file_str;
+
+  /* Read file to a string */
+  guardfraction_file_str = read_file_to_str(fname, RFTS_IGNORE_MISSING, NULL);
+  if (!guardfraction_file_str) {
+      log_warn(LD_FS, "Cannot open guardfraction file '%s'. Failing.", fname);
+      return -1;
+  }
+
+  return dirserv_read_guardfraction_file_from_str(guardfraction_file_str,
+                                               vote_routerstatuses);
+}
+
 /**
  * Helper function to parse out a line in the measured bandwidth file
  * into a measured_bw_line_t output structure. Returns -1 on failure
@@ -2456,6 +2776,12 @@ dirserv_generate_networkstatus_vote_obj(crypto_pk_t *private_key,
   smartlist_free(routers);
   digestmap_free(omit_as_sybil, NULL);
 
+  /* Apply guardfraction information to routerstatuses. */
+  if (options->GuardfractionFile) {
+    dirserv_read_guardfraction_file(options->GuardfractionFile,
+                                    routerstatuses);
+  }
+
   /* This pass through applies the measured bw lines to the routerstatuses */
   if (options->V3BandwidthsFile) {
     dirserv_read_measured_bandwidths(options->V3BandwidthsFile,
diff --git a/src/or/dirserv.h b/src/or/dirserv.h
index 514ec444e6..311a513dbe 100644
--- a/src/or/dirserv.h
+++ b/src/or/dirserv.h
@@ -125,10 +125,17 @@ STATIC int dirserv_query_measured_bw_cache_kb(const char *node_id,
                                               long *bw_out,
                                               time_t *as_of_out);
 STATIC int dirserv_has_measured_bw(const char *node_id);
+
+STATIC int
+dirserv_read_guardfraction_file_from_str(const char *guardfraction_file_str,
+                                      smartlist_t *vote_routerstatuses);
 #endif
 
 int dirserv_read_measured_bandwidths(const char *from_file,
                                      smartlist_t *routerstatuses);
 
+int dirserv_read_guardfraction_file(const char *fname,
+                                 smartlist_t *vote_routerstatuses);
+
 #endif
 
diff --git a/src/or/dirvote.c b/src/or/dirvote.c
index 7739c52d15..b54049d5de 100644
--- a/src/or/dirvote.c
+++ b/src/or/dirvote.c
@@ -16,6 +16,7 @@
 #include "router.h"
 #include "routerlist.h"
 #include "routerparse.h"
+#include "entrynodes.h" /* needed for guardfraction methods */
 
 /**
  * \file dirvote.c
@@ -1023,6 +1024,86 @@ networkstatus_compute_bw_weights_v10(smartlist_t *chunks, int64_t G,
   return 1;
 }
 
+/** Update total bandwidth weights (G/M/E/D/T) with the bandwidth of
+ *  the router in <b>rs</b>. */
+static void
+update_total_bandwidth_weights(const routerstatus_t *rs,
+                               int is_exit, int is_guard,
+                               int64_t *G, int64_t *M, int64_t *E, int64_t *D,
+                               int64_t *T)
+{
+  int default_bandwidth = rs->bandwidth_kb;
+  int guardfraction_bandwidth = 0;
+
+  if (!rs->has_bandwidth) {
+    log_info(LD_BUG, "Missing consensus bandwidth for router %s",
+             rs->nickname);
+    return;
+  }
+
+  /* If this routerstatus represents a guard that we have
+   * guardfraction information on, use it to calculate its actual
+   * bandwidth. From proposal236:
+   *
+   *    Similarly, when calculating the bandwidth-weights line as in
+   *    section 3.8.3 of dir-spec.txt, directory authorities should treat N
+   *    as if fraction F of its bandwidth has the guard flag and (1-F) does
+   *    not.  So when computing the totals G,M,E,D, each relay N with guard
+   *    visibility fraction F and bandwidth B should be added as follows:
+   *
+   *    G' = G + F*B, if N does not have the exit flag
+   *    M' = M + (1-F)*B, if N does not have the exit flag
+   *
+   *    or
+   *
+   *    D' = D + F*B, if N has the exit flag
+   *    E' = E + (1-F)*B, if N has the exit flag
+   *
+   * In this block of code, we prepare the bandwidth values by setting
+   * the default_bandwidth to F*B and guardfraction_bandwidth to (1-F)*B. */
+  if (rs->has_guardfraction) {
+    guardfraction_bandwidth_t guardfraction_bw;
+
+    tor_assert(is_guard);
+
+    guard_get_guardfraction_bandwidth(&guardfraction_bw,
+                                      rs->bandwidth_kb,
+                                      rs->guardfraction_percentage);
+
+    default_bandwidth = guardfraction_bw.guard_bw;
+    guardfraction_bandwidth = guardfraction_bw.non_guard_bw;
+  }
+
+  /* Now calculate the total bandwidth weights with or without
+     guardfraction. Depending on the flags of the relay, add its
+     bandwidth to the appropriate weight pool. If it's a guard and
+     guardfraction is enabled, add its bandwidth to both pools as
+     indicated by the previous comment. */
+  *T += default_bandwidth;
+  if (is_exit && is_guard) {
+
+    *D += default_bandwidth;
+    if (rs->has_guardfraction) {
+      *E += guardfraction_bandwidth;
+    }
+
+  } else if (is_exit) {
+
+    *E += default_bandwidth;
+
+  } else if (is_guard) {
+
+    *G += default_bandwidth;
+    if (rs->has_guardfraction) {
+      *M += guardfraction_bandwidth;
+    }
+
+  } else {
+
+    *M += default_bandwidth;
+  }
+}
+
 /** Given a list of vote networkstatus_t in <b>votes</b>, our public
  * authority <b>identity_key</b>, our private authority <b>signing_key</b>,
  * and the number of <b>total_authorities</b> that we believe exist in our
@@ -1291,8 +1372,11 @@ networkstatus_compute_consensus(smartlist_t *votes,
                                          sizeof(uint32_t));
     uint32_t *measured_bws_kb = tor_calloc(smartlist_len(votes),
                                            sizeof(uint32_t));
+    uint32_t *measured_guardfraction = tor_calloc(smartlist_len(votes),
+                                                  sizeof(uint32_t));
     int num_bandwidths;
     int num_mbws;
+    int num_guardfraction_inputs;
 
     int *n_voter_flags; /* n_voter_flags[j] is the number of flags that
                          * votes[j] knows about. */
@@ -1401,7 +1485,7 @@ networkstatus_compute_consensus(smartlist_t *votes,
 
     /* We need to know how many votes measure bandwidth. */
     n_authorities_measuring_bandwidth = 0;
-    SMARTLIST_FOREACH(votes, networkstatus_t *, v,
+    SMARTLIST_FOREACH(votes, const networkstatus_t *, v,
        if (v->has_measured_bws) {
          ++n_authorities_measuring_bandwidth;
        }
@@ -1443,6 +1527,7 @@ networkstatus_compute_consensus(smartlist_t *votes,
       smartlist_clear(versions);
       num_bandwidths = 0;
       num_mbws = 0;
+      num_guardfraction_inputs = 0;
 
       /* Okay, go through all the entries for this digest. */
       SMARTLIST_FOREACH_BEGIN(votes, networkstatus_t *, v) {
@@ -1476,6 +1561,12 @@ networkstatus_compute_consensus(smartlist_t *votes,
           chosen_name = rs->status.nickname;
         }
 
+        /* Count guardfraction votes and note down the values. */
+        if (rs->status.has_guardfraction) {
+          measured_guardfraction[num_guardfraction_inputs++] =
+            rs->status.guardfraction_percentage;
+        }
+
         /* count bandwidths */
         if (rs->has_measured_bw)
           measured_bws_kb[num_mbws++] = rs->measured_bw_kb;
@@ -1565,6 +1656,17 @@ networkstatus_compute_consensus(smartlist_t *votes,
         chosen_version = NULL;
       }
 
+      /* If it's a guard and we have enough guardfraction votes,
+         calculate its consensus guardfraction value. */
+      if (is_guard && num_guardfraction_inputs > 2 &&
+          consensus_method >= MIN_METHOD_FOR_GUARDFRACTION) {
+        rs_out.has_guardfraction = 1;
+        rs_out.guardfraction_percentage = median_uint32(measured_guardfraction,
+                                                     num_guardfraction_inputs);
+        /* final value should be an integer percentage! */
+        tor_assert(rs_out.guardfraction_percentage <= 100);
+      }
+
       /* Pick a bandwidth */
       if (num_mbws > 2) {
         rs_out.has_bandwidth = 1;
@@ -1586,21 +1688,11 @@ networkstatus_compute_consensus(smartlist_t *votes,
       /* Fix bug 2203: Do not count BadExit nodes as Exits for bw weights */
       is_exit = is_exit && !is_bad_exit;
 
+      /* Update total bandwidth weights with the bandwidths of this router. */
       {
-        if (rs_out.has_bandwidth) {
-          T += rs_out.bandwidth_kb;
-          if (is_exit && is_guard)
-            D += rs_out.bandwidth_kb;
-          else if (is_exit)
-            E += rs_out.bandwidth_kb;
-          else if (is_guard)
-            G += rs_out.bandwidth_kb;
-          else
-            M += rs_out.bandwidth_kb;
-        } else {
-          log_warn(LD_BUG, "Missing consensus bandwidth for router %s",
-              rs_out.nickname);
-        }
+        update_total_bandwidth_weights(&rs_out,
+                                       is_exit, is_guard,
+                                       &G, &M, &E, &D, &T);
       }
 
       /* Ok, we already picked a descriptor digest we want to list
@@ -1719,11 +1811,21 @@ networkstatus_compute_consensus(smartlist_t *votes,
       smartlist_add(chunks, tor_strdup("\n"));
       /*     Now the weight line. */
       if (rs_out.has_bandwidth) {
+        char *guardfraction_str = NULL;
         int unmeasured = rs_out.bw_is_unmeasured &&
           consensus_method >= MIN_METHOD_TO_CLIP_UNMEASURED_BW;
-        smartlist_add_asprintf(chunks, "w Bandwidth=%d%s\n",
+
+        /* If we have guardfraction info, include it in the 'w' line. */
+        if (rs_out.has_guardfraction) {
+          tor_asprintf(&guardfraction_str,
+                       " GuardFraction=%u", rs_out.guardfraction_percentage);
+        }
+        smartlist_add_asprintf(chunks, "w Bandwidth=%d%s%s\n",
                                rs_out.bandwidth_kb,
-                               unmeasured?" Unmeasured=1":"");
+                               unmeasured?" Unmeasured=1":"",
+                               guardfraction_str ? guardfraction_str : "");
+
+        tor_free(guardfraction_str);
       }
 
       /*     Now the exitpolicy summary line. */
diff --git a/src/or/dirvote.h b/src/or/dirvote.h
index 20dcbcd5b6..542563b708 100644
--- a/src/or/dirvote.h
+++ b/src/or/dirvote.h
@@ -55,7 +55,7 @@
 #define MIN_SUPPORTED_CONSENSUS_METHOD 13
 
 /** The highest consensus method that we currently support. */
-#define MAX_SUPPORTED_CONSENSUS_METHOD 19
+#define MAX_SUPPORTED_CONSENSUS_METHOD 20
 
 /** Lowest consensus method where microdesc consensuses omit any entry
  * with no microdesc. */
@@ -82,8 +82,13 @@
 /** Lowest consensus method where we include "package" lines*/
 #define MIN_METHOD_FOR_PACKAGE_LINES 19
 
+/** Lowest consensus method where authorities may include
+ * GuardFraction information in microdescriptors. */
+#define MIN_METHOD_FOR_GUARDFRACTION 20
+
 /** Default bandwidth to clip unmeasured bandwidths to using method >=
- * MIN_METHOD_TO_CLIP_UNMEASURED_BW */
+ * MIN_METHOD_TO_CLIP_UNMEASURED_BW.  (This is not a consensus method; do not
+ * get confused with the above macros.) */
 #define DEFAULT_MAX_UNMEASURED_BW_KB 20
 
 void dirvote_free_all(void);
diff --git a/src/or/entrynodes.c b/src/or/entrynodes.c
index 5a12170b0c..9b838b5b2a 100644
--- a/src/or/entrynodes.c
+++ b/src/or/entrynodes.c
@@ -1697,6 +1697,63 @@ getinfo_helper_entry_guards(control_connection_t *conn,
   return 0;
 }
 
+/** Return 0 if we should apply guardfraction information found in the
+ *  consensus. A specific consensus can be specified with the
+ *  <b>ns</b> argument, if NULL the most recent one will be picked.*/
+int
+should_apply_guardfraction(const networkstatus_t *ns)
+{
+  /* We need to check the corresponding torrc option and the consensus
+   * parameter if we need to. */
+  const or_options_t *options = get_options();
+
+  /* If UseGuardFraction is 'auto' then check the same-named consensus
+   * parameter. If the consensus parameter is not present, default to
+   * "off". */
+  if (options->UseGuardFraction == -1) {
+    return networkstatus_get_param(ns, "UseGuardFraction",
+                                   0, /* default to "off" */
+                                   0, 1);
+  }
+
+  return options->UseGuardFraction;
+}
+
+/* Given the original bandwidth of a guard and its guardfraction,
+ * calculate how much bandwidth the guard should have as a guard and
+ * as a non-guard.
+ *
+ * Quoting from proposal236:
+ *
+ *   Let Wpf denote the weight from the 'bandwidth-weights' line a
+ *   client would apply to N for position p if it had the guard
+ *   flag, Wpn the weight if it did not have the guard flag, and B the
+ *   measured bandwidth of N in the consensus.  Then instead of choosing
+ *   N for position p proportionally to Wpf*B or Wpn*B, clients should
+ *   choose N proportionally to F*Wpf*B + (1-F)*Wpn*B.
+ *
+ * This function fills the <b>guardfraction_bw</b> structure. It sets
+ * <b>guard_bw</b> to F*B and <b>non_guard_bw</b> to (1-F)*B.
+ */
+void
+guard_get_guardfraction_bandwidth(guardfraction_bandwidth_t *guardfraction_bw,
+                                  int orig_bandwidth,
+                                  uint32_t guardfraction_percentage)
+{
+  double guardfraction_fraction;
+
+  /* Turn the percentage into a fraction. */
+  tor_assert(guardfraction_percentage <= 100);
+  guardfraction_fraction = guardfraction_percentage / 100.0;
+
+  long guard_bw = tor_lround(guardfraction_fraction * orig_bandwidth);
+  tor_assert(guard_bw <= INT_MAX);
+
+  guardfraction_bw->guard_bw = (int) guard_bw;
+
+  guardfraction_bw->non_guard_bw = orig_bandwidth - guard_bw;
+}
+
 /** A list of configured bridges. Whenever we actually get a descriptor
  * for one, we add it as an entry guard.  Note that the order of bridges
  * in this list does not necessarily correspond to the order of bridges
diff --git a/src/or/entrynodes.h b/src/or/entrynodes.h
index 7f3a4fb29c..35bd748d0d 100644
--- a/src/or/entrynodes.h
+++ b/src/or/entrynodes.h
@@ -160,5 +160,21 @@ int validate_pluggable_transports_config(void);
 double pathbias_get_close_success_count(entry_guard_t *guard);
 double pathbias_get_use_success_count(entry_guard_t *guard);
 
+/** Contains the bandwidth of a relay as a guard and as a non-guard
+ *  after the guardfraction has been considered.  */
+typedef struct guardfraction_bandwidth_t {
+  /* Bandwidth as a guard after guardfraction has been considered. */
+  int guard_bw;
+  /* Bandwidth as a non-guard after guardfraction has been considered. */
+  int non_guard_bw;
+} guardfraction_bandwidth_t;
+
+int should_apply_guardfraction(const networkstatus_t *ns);
+
+void
+guard_get_guardfraction_bandwidth(guardfraction_bandwidth_t *guardfraction_bw,
+                                  int orig_bandwidth,
+                                  uint32_t guardfraction_percentage);
+
 #endif
 
diff --git a/src/or/or.h b/src/or/or.h
index d1961b5bb4..6723f93f77 100644
--- a/src/or/or.h
+++ b/src/or/or.h
@@ -2145,6 +2145,12 @@ typedef struct routerstatus_t {
 
   uint32_t bandwidth_kb; /**< Bandwidth (capacity) of the router as reported in
                        * the vote/consensus, in kilobytes/sec. */
+
+  /** The consensus has guardfraction information for this router. */
+  unsigned int has_guardfraction:1;
+  /** The guardfraction value of this router. */
+  uint32_t guardfraction_percentage;
+
   char *exitsummary; /**< exit policy summary -
                       * XXX weasel: this probably should not stay a string. */
 
@@ -3816,6 +3822,12 @@ typedef struct {
   int NumEntryGuards; /**< How many entry guards do we try to establish? */
   int UseEntryGuardsAsDirGuards; /** Boolean: Do we try to get directory info
                                   * from a smallish number of fixed nodes? */
+
+  /** If 1, we use any guardfraction information we see in the
+   * consensus.  If 0, we don't.  If -1, let the consensus parameter
+   * decide. */
+  int UseGuardFraction;
+
   int NumDirectoryGuards; /**< How many dir guards do we try to establish?
                            * If 0, use value from NumEntryGuards. */
   int RephistTrackTime; /**< How many seconds do we keep rephist info? */
@@ -3951,6 +3963,9 @@ typedef struct {
   /** Location of bandwidth measurement file */
   char *V3BandwidthsFile;
 
+  /** Location of guardfraction file */
+  char *GuardfractionFile;
+
   /** Authority only: key=value pairs that we add to our networkstatus
    * consensus vote on the 'params' line. */
   char *ConsensusParams;
diff --git a/src/or/routerlist.c b/src/or/routerlist.c
index 64c43c298b..d53265c726 100644
--- a/src/or/routerlist.c
+++ b/src/or/routerlist.c
@@ -2003,6 +2003,7 @@ compute_weighted_bandwidths(const smartlist_t *sl,
   double Wg = -1, Wm = -1, We = -1, Wd = -1;
   double Wgb = -1, Wmb = -1, Web = -1, Wdb = -1;
   uint64_t weighted_bw = 0;
+  guardfraction_bandwidth_t guardfraction_bw;
   u64_dbl_t *bandwidths;
 
   /* Can't choose exit and guard at same time */
@@ -2092,6 +2093,8 @@ compute_weighted_bandwidths(const smartlist_t *sl,
   SMARTLIST_FOREACH_BEGIN(sl, const node_t *, node) {
     int is_exit = 0, is_guard = 0, is_dir = 0, this_bw = 0;
     double weight = 1;
+    double weight_without_guard_flag = 0; /* Used for guardfraction */
+    double final_weight = 0;
     is_exit = node->is_exit && ! node->is_bad_exit;
     is_guard = node->is_possible_guard;
     is_dir = node_is_dir(node);
@@ -2119,8 +2122,10 @@ compute_weighted_bandwidths(const smartlist_t *sl,
 
     if (is_guard && is_exit) {
       weight = (is_dir ? Wdb*Wd : Wd);
+      weight_without_guard_flag = (is_dir ? Web*We : We);
     } else if (is_guard) {
       weight = (is_dir ? Wgb*Wg : Wg);
+      weight_without_guard_flag = (is_dir ? Wmb*Wm : Wm);
     } else if (is_exit) {
       weight = (is_dir ? Web*We : We);
     } else { // middle
@@ -2132,8 +2137,43 @@ compute_weighted_bandwidths(const smartlist_t *sl,
       this_bw = 0;
     if (weight < 0.0)
       weight = 0.0;
+    if (weight_without_guard_flag < 0.0)
+      weight_without_guard_flag = 0.0;
 
-    bandwidths[node_sl_idx].dbl = weight*this_bw + 0.5;
+    /* If guardfraction information is available in the consensus, we
+     * want to calculate this router's bandwidth according to its
+     * guardfraction. Quoting from proposal236:
+     *
+     *    Let Wpf denote the weight from the 'bandwidth-weights' line a
+     *    client would apply to N for position p if it had the guard
+     *    flag, Wpn the weight if it did not have the guard flag, and B the
+     *    measured bandwidth of N in the consensus.  Then instead of choosing
+     *    N for position p proportionally to Wpf*B or Wpn*B, clients should
+     *    choose N proportionally to F*Wpf*B + (1-F)*Wpn*B.
+     */
+    if (node->rs && node->rs->has_guardfraction && rule != WEIGHT_FOR_GUARD) {
+      /* XXX The assert should actually check for is_guard. However,
+       * that crashes dirauths because of #13297. This should be
+       * equivalent: */
+      tor_assert(node->rs->is_possible_guard);
+
+      guard_get_guardfraction_bandwidth(&guardfraction_bw,
+                                        this_bw,
+                                        node->rs->guardfraction_percentage);
+
+      /* Calculate final_weight = F*Wpf*B + (1-F)*Wpn*B */
+      final_weight =
+        guardfraction_bw.guard_bw * weight +
+        guardfraction_bw.non_guard_bw * weight_without_guard_flag;
+
+      log_debug(LD_GENERAL, "%s: Guardfraction weight %f instead of %f (%s)",
+                node->rs->nickname, final_weight, weight*this_bw,
+                bandwidth_weight_rule_to_string(rule));
+    } else { /* no guardfraction information. calculate the weight normally. */
+      final_weight = weight*this_bw;
+    }
+
+    bandwidths[node_sl_idx].dbl = final_weight + 0.5;
   } SMARTLIST_FOREACH_END(node);
 
   log_debug(LD_CIRC, "Generated weighted bandwidths for rule %s based "
diff --git a/src/or/routerparse.c b/src/or/routerparse.c
index f7687e0e40..0e8bf8dbe1 100644
--- a/src/or/routerparse.c
+++ b/src/or/routerparse.c
@@ -9,6 +9,8 @@
  * \brief Code to parse and validate router descriptors and directories.
  **/
 
+#define ROUTERPARSE_PRIVATE
+
 #include "or.h"
 #include "config.h"
 #include "circuitstats.h"
@@ -23,6 +25,7 @@
 #include "networkstatus.h"
 #include "rephist.h"
 #include "routerparse.h"
+#include "entrynodes.h"
 #undef log
 #include <math.h>
 
@@ -1794,6 +1797,63 @@ find_start_of_next_routerstatus(const char *s)
     return eos;
 }
 
+/** Parse the GuardFraction string from a consensus or vote.
+ *
+ *  If <b>vote</b> or <b>vote_rs</b> are set the document getting
+ *  parsed is a vote routerstatus. Otherwise it's a consensus. This is
+ *  the same semantic as in routerstatus_parse_entry_from_string(). */
+STATIC int
+routerstatus_parse_guardfraction(const char *guardfraction_str,
+                                 networkstatus_t *vote,
+                                 vote_routerstatus_t *vote_rs,
+                                 routerstatus_t *rs)
+{
+  int ok;
+  const char *end_of_header = NULL;
+  int is_consensus = !vote_rs;
+  uint32_t guardfraction;
+
+  tor_assert(bool_eq(vote, vote_rs));
+
+  /* If this info comes from a consensus, but we should't apply
+     guardfraction, just exit. */
+  if (is_consensus && !should_apply_guardfraction(NULL)) {
+    return 0;
+  }
+
+  end_of_header = strchr(guardfraction_str, '=');
+  if (!end_of_header) {
+    return -1;
+  }
+
+  guardfraction = (uint32_t)tor_parse_ulong(end_of_header+1,
+                                         10, 0, 100, &ok, NULL);
+  if (!ok) {
+    log_warn(LD_DIR, "Invalid GuardFraction %s", escaped(guardfraction_str));
+    return -1;
+  }
+
+  log_debug(LD_GENERAL, "[*] Parsed %s guardfraction '%s' for '%s'.",
+            is_consensus ? "consensus" : "vote",
+            guardfraction_str, rs->nickname);
+
+  if (!is_consensus) { /* We are parsing a vote */
+    vote_rs->status.guardfraction_percentage = guardfraction;
+    vote_rs->status.has_guardfraction = 1;
+  } else {
+    /* We are parsing a consensus. Only apply guardfraction to guards. */
+    if (rs->is_possible_guard) {
+      rs->guardfraction_percentage = guardfraction;
+      rs->has_guardfraction = 1;
+    } else {
+      log_warn(LD_BUG, "Got GuardFraction for non-guard %s. "
+               "This is not supposed to happen. Not applying. ", rs->nickname);
+    }
+  }
+
+  return 0;
+}
+
 /** Given a string at *<b>s</b>, containing a routerstatus object, and an
  * empty smartlist at <b>tokens</b>, parse and return the first router status
  * object in the string, and advance *<b>s</b> to just after the end of the
@@ -1996,6 +2056,11 @@ routerstatus_parse_entry_from_string(memarea_t *area,
         vote->has_measured_bws = 1;
       } else if (!strcmpstart(tok->args[i], "Unmeasured=1")) {
         rs->bw_is_unmeasured = 1;
+      } else if (!strcmpstart(tok->args[i], "GuardFraction=")) {
+        if (routerstatus_parse_guardfraction(tok->args[i],
+                                             vote, vote_rs, rs) < 0) {
+          goto err;
+        }
       }
     }
   }
diff --git a/src/or/routerparse.h b/src/or/routerparse.h
index 18a7d2563c..fc21cb1041 100644
--- a/src/or/routerparse.h
+++ b/src/or/routerparse.h
@@ -85,5 +85,12 @@ int rend_parse_introduction_points(rend_service_descriptor_t *parsed,
                                    size_t intro_points_encoded_size);
 int rend_parse_client_keys(strmap_t *parsed_clients, const char *str);
 
+#ifdef ROUTERPARSE_PRIVATE
+STATIC int routerstatus_parse_guardfraction(const char *guardfraction_str,
+                                            networkstatus_t *vote,
+                                            vote_routerstatus_t *vote_rs,
+                                            routerstatus_t *rs);
+#endif
+
 #endif