Add parsing+verification for bw weight values.

1 files changed, 378 insertions, 0 deletions

diff --git a/src/or/routerparse.c b/src/or/routerparse.c
index f4af7cd5e2..1212907e4e 100644
--- a/src/or/routerparse.c
+++ b/src/or/routerparse.c
@@ -11,6 +11,8 @@
 
 #include "or.h"
 #include "memarea.h"
+#undef log
+#include <math.h>
 
 /****************************************************************************/
 
@@ -104,6 +106,7 @@ typedef enum {
 
   K_KNOWN_FLAGS,
   K_PARAMS,
+  K_BW_WEIGHTS,
   K_VOTE_DIGEST,
   K_CONSENSUS_DIGEST,
   K_ADDITIONAL_DIGEST,
@@ -485,6 +488,7 @@ static token_rule_t networkstatus_consensus_token_table[] = {
 /** List of tokens allowable in the footer of v1/v2 directory/networkstatus
  * footers. */
 static token_rule_t networkstatus_vote_footer_token_table[] = {
+  T01("bandwidth-weights",   K_BW_WEIGHTS,          ARGS,        NO_OBJ ),
   T(  "directory-signature", K_DIRECTORY_SIGNATURE, GE(2),   NEED_OBJ ),
   END_OF_TABLE
 };
@@ -2327,6 +2331,360 @@ networkstatus_v2_parse_from_string(const char *s)
   return ns;
 }
 
+/** Verify the bandwidth weights of a network status document */
+int
+networkstatus_verify_bw_weights(networkstatus_t *ns)
+{
+  int64_t weight_scale;
+  int64_t G=0, M=0, E=0, D=0, T=0;
+  double Wgg, Wgm, Wgd, Wmg, Wmm, Wme, Wmd, Weg, Wem, Wee, Wed;
+  double Gtotal=0, Mtotal=0, Etotal=0;
+  const char *casename = NULL;
+  int valid = 1;
+
+  weight_scale = networkstatus_get_param(ns, "bwweightscale", BW_WEIGHT_SCALE);
+  Wgg = networkstatus_get_bw_weight(ns, "Wgg", -1);
+  Wgm = networkstatus_get_bw_weight(ns, "Wgm", -1);
+  Wgd = networkstatus_get_bw_weight(ns, "Wgd", -1);
+  Wmg = networkstatus_get_bw_weight(ns, "Wmg", -1);
+  Wmm = networkstatus_get_bw_weight(ns, "Wmm", -1);
+  Wme = networkstatus_get_bw_weight(ns, "Wme", -1);
+  Wmd = networkstatus_get_bw_weight(ns, "Wmd", -1);
+  Weg = networkstatus_get_bw_weight(ns, "Weg", -1);
+  Wem = networkstatus_get_bw_weight(ns, "Wem", -1);
+  Wee = networkstatus_get_bw_weight(ns, "Wee", -1);
+  Wed = networkstatus_get_bw_weight(ns, "Wed", -1);
+
+  if (Wgg<0 || Wgm<0 || Wgd<0 || Wmg<0 || Wmm<0 || Wme<0 || Wmd<0 || Weg<0
+          || Wem<0 || Wee<0 || Wed<0) {
+    log_warn(LD_BUG, "No bandwidth weights produced in consensus!");
+    return 0;
+  }
+
+  // First, sanity check basic summing properties that hold for all cases
+  // We use > 1 as the check for these because they are computed as integers.
+  // Sometimes there are rounding errors.
+  if (fabs(Wmm - weight_scale) > 1) {
+    log_warn(LD_BUG, "Wmm=%lf != "I64_FORMAT, Wmm, weight_scale);
+    valid = 0;
+  }
+
+  if (fabs(Wem - Wee) > 1) {
+    log_warn(LD_BUG, "Wem=%lf != Wee=%lf", Wem, Wee);
+    valid = 0;
+  }
+
+  if (fabs(Wgm - Wgg) > 1) {
+    log_warn(LD_BUG, "Wgm=%lf != Wgg=%lf", Wgm, Wgg);
+    valid = 0;
+  }
+
+  if (fabs(Weg - Wed) > 1) {
+    log_warn(LD_BUG, "Wed=%lf != Weg=%lf", Wed, Weg);
+    valid = 0;
+  }
+
+  if (fabs(Wgg + Wmg - weight_scale) > 0.001*weight_scale) {
+    log_warn(LD_BUG, "Wgg=%lf != "I64_FORMAT" - Wmg=%lf", Wgg,
+             weight_scale, Wmg);
+    valid = 0;
+  }
+
+  if (fabs(Wee + Wme - weight_scale) > 0.001*weight_scale) {
+    log_warn(LD_BUG, "Wee=%lf != "I64_FORMAT" - Wme=%lf", Wee,
+             weight_scale, Wme);
+    valid = 0;
+  }
+
+  if (fabs(Wgd + Wmd + Wed - weight_scale) > 0.001*weight_scale) {
+    log_warn(LD_BUG, "Wgd=%lf + Wmd=%lf + Wed=%lf != "I64_FORMAT,
+             Wgd, Wmd, Wed, weight_scale);
+    valid = 0;
+  }
+
+  Wgg /= weight_scale;
+  Wgm /= weight_scale;
+  Wgd /= weight_scale;
+
+  Wmg /= weight_scale;
+  Wmm /= weight_scale;
+  Wme /= weight_scale;
+  Wmd /= weight_scale;
+
+  Weg /= weight_scale;
+  Wem /= weight_scale;
+  Wee /= weight_scale;
+  Wed /= weight_scale;
+
+  // Then, gather G, M, E, D, T to determine case
+  SMARTLIST_FOREACH_BEGIN(ns->routerstatus_list, routerstatus_t *, rs) {
+    if (rs->has_bandwidth) {
+      T += rs->bandwidth;
+      if (rs->is_exit && rs->is_possible_guard) {
+        D += rs->bandwidth;
+        Gtotal += Wgd*rs->bandwidth;
+        Mtotal += Wmd*rs->bandwidth;
+        Etotal += Wed*rs->bandwidth;
+      } else if (rs->is_exit) {
+        E += rs->bandwidth;
+        Mtotal += Wme*rs->bandwidth;
+        Etotal += Wee*rs->bandwidth;
+      } else if (rs->is_possible_guard) {
+        G += rs->bandwidth;
+        Gtotal += Wgg*rs->bandwidth;
+        Mtotal += Wmg*rs->bandwidth;
+      } else {
+        M += rs->bandwidth;
+        Mtotal += Wmm*rs->bandwidth;
+      }
+    } else {
+      log_warn(LD_BUG, "Missing consensus bandwidth for router %s",
+          rs->nickname);
+    }
+  } SMARTLIST_FOREACH_END(rs);
+
+  // Finally, check equality conditions depending upon case 1, 2 or 3
+  // Full equality cases: 1, 3b
+  // Partial equality cases: 2b (E=G), 3a (M=E)
+  // Fully unknown: 2a
+  if (3*E >= T && 3*G >= T) {
+    // Case 1: Neither are scarce
+    casename = "Case 1";
+    if (fabs(Etotal-Mtotal) > 0.01*MAX(Etotal,Mtotal)) {
+      log_warn(LD_DIR,
+               "Bw Weight Failure for %s: Etotal %lf != Mtotal %lf. "
+               "G="I64_FORMAT" M="I64_FORMAT" E="I64_FORMAT" D="I64_FORMAT
+               " T="I64_FORMAT". "
+               "Wgg=%lf Wgd=%lf Wmg=%lf Wme=%lf Wmd=%lf Wee=%lf Wed=%lf",
+               casename, Etotal, Mtotal, G, M, E, D, T,
+               Wgg, Wgd, Wmg, Wme, Wmd, Wee, Wed);
+      valid = 0;
+    }
+    if (fabs(Etotal-Gtotal) > 0.01*MAX(Etotal,Gtotal)) {
+      log_warn(LD_DIR,
+               "Bw Weight Failure for %s: Etotal %lf != Gtotal %lf. "
+               "G="I64_FORMAT" M="I64_FORMAT" E="I64_FORMAT" D="I64_FORMAT
+               " T="I64_FORMAT". "
+               "Wgg=%lf Wgd=%lf Wmg=%lf Wme=%lf Wmd=%lf Wee=%lf Wed=%lf",
+               casename, Etotal, Gtotal, G, M, E, D, T,
+               Wgg, Wgd, Wmg, Wme, Wmd, Wee, Wed);
+      valid = 0;
+    }
+    if (fabs(Gtotal-Mtotal) > 0.01*MAX(Gtotal,Mtotal)) {
+      log_warn(LD_DIR,
+               "Bw Weight Failure for %s: Mtotal %lf != Gtotal %lf. "
+               "G="I64_FORMAT" M="I64_FORMAT" E="I64_FORMAT" D="I64_FORMAT
+               " T="I64_FORMAT". "
+               "Wgg=%lf Wgd=%lf Wmg=%lf Wme=%lf Wmd=%lf Wee=%lf Wed=%lf",
+               casename, Mtotal, Gtotal, G, M, E, D, T,
+               Wgg, Wgd, Wmg, Wme, Wmd, Wee, Wed);
+      valid = 0;
+    }
+  } else if (3*E < T && 3*G < T) {
+    int64_t R = MIN(E, G);
+    int64_t S = MAX(E, G);
+    /*
+     * Case 2: Both Guards and Exits are scarce
+     * Balance D between E and G, depending upon
+     * D capacity and scarcity. Devote no extra
+     * bandwidth to middle nodes.
+     */
+    if (R+D < S) { // Subcase a
+      double Rtotal, Stotal;
+      if (E < G) {
+        Rtotal = Etotal;
+        Stotal = Gtotal;
+      } else {
+        Rtotal = Gtotal;
+        Stotal = Etotal;
+      }
+      casename = "Case 2a";
+      // Rtotal < Stotal
+      if (Rtotal > Stotal) {
+        log_warn(LD_DIR,
+                   "Bw Weight Failure for %s: Rtotal %lf > Stotal %lf. "
+                   "G="I64_FORMAT" M="I64_FORMAT" E="I64_FORMAT" D="I64_FORMAT
+                   " T="I64_FORMAT". "
+                   "Wgg=%lf Wgd=%lf Wmg=%lf Wme=%lf Wmd=%lf Wee=%lf Wed=%lf",
+                   casename, Rtotal, Stotal, G, M, E, D, T,
+                   Wgg, Wgd, Wmg, Wme, Wmd, Wee, Wed);
+        valid = 0;
+      }
+      // Rtotal < T/3
+      if (3*Rtotal > T) {
+        log_warn(LD_DIR,
+                   "Bw Weight Failure for %s: 3*Rtotal %lf > T "
+                   I64_FORMAT". G="I64_FORMAT" M="I64_FORMAT" E="I64_FORMAT
+                   " D="I64_FORMAT" T="I64_FORMAT". "
+                   "Wgg=%lf Wgd=%lf Wmg=%lf Wme=%lf Wmd=%lf Wee=%lf Wed=%lf",
+                   casename, Rtotal*3, T, G, M, E, D, T,
+                   Wgg, Wgd, Wmg, Wme, Wmd, Wee, Wed);
+        valid = 0;
+      }
+      // Stotal < T/3
+      if (3*Stotal > T) {
+        log_warn(LD_DIR,
+                   "Bw Weight Failure for %s: 3*Stotal %lf > T "
+                   I64_FORMAT". G="I64_FORMAT" M="I64_FORMAT" E="I64_FORMAT
+                   " D="I64_FORMAT" T="I64_FORMAT". "
+                   "Wgg=%lf Wgd=%lf Wmg=%lf Wme=%lf Wmd=%lf Wee=%lf Wed=%lf",
+                   casename, Stotal*3, T, G, M, E, D, T,
+                   Wgg, Wgd, Wmg, Wme, Wmd, Wee, Wed);
+        valid = 0;
+      }
+      // Mtotal > T/3
+      if (3*Mtotal < T) {
+        log_warn(LD_DIR,
+                   "Bw Weight Failure for %s: 3*Mtotal %lf < T "
+                   I64_FORMAT". "
+                   "G="I64_FORMAT" M="I64_FORMAT" E="I64_FORMAT" D="I64_FORMAT
+                   " T="I64_FORMAT". "
+                   "Wgg=%lf Wgd=%lf Wmg=%lf Wme=%lf Wmd=%lf Wee=%lf Wed=%lf",
+                   casename, Mtotal*3, T, G, M, E, D, T,
+                   Wgg, Wgd, Wmg, Wme, Wmd, Wee, Wed);
+        valid = 0;
+      }
+    } else { // Subcase b: R+D > S
+      casename = "Case 2b";
+
+      /* Check the rare-M redirect case. */
+      if (D != 0 && 3*M < T) {
+        casename = "Case 2b (balanced)";
+        if (fabs(Etotal-Mtotal) > 0.01*MAX(Etotal,Mtotal)) {
+          log_warn(LD_DIR,
+                   "Bw Weight Failure for %s: Etotal %lf != Mtotal %lf. "
+                   "G="I64_FORMAT" M="I64_FORMAT" E="I64_FORMAT" D="I64_FORMAT
+                   " T="I64_FORMAT". "
+                   "Wgg=%lf Wgd=%lf Wmg=%lf Wme=%lf Wmd=%lf Wee=%lf Wed=%lf",
+                   casename, Etotal, Mtotal, G, M, E, D, T,
+                   Wgg, Wgd, Wmg, Wme, Wmd, Wee, Wed);
+          valid = 0;
+        }
+        if (fabs(Etotal-Gtotal) > 0.01*MAX(Etotal,Gtotal)) {
+          log_warn(LD_DIR,
+                   "Bw Weight Failure for %s: Etotal %lf != Gtotal %lf. "
+                   "G="I64_FORMAT" M="I64_FORMAT" E="I64_FORMAT" D="I64_FORMAT
+                   " T="I64_FORMAT". "
+                   "Wgg=%lf Wgd=%lf Wmg=%lf Wme=%lf Wmd=%lf Wee=%lf Wed=%lf",
+                   casename, Etotal, Gtotal, G, M, E, D, T,
+                   Wgg, Wgd, Wmg, Wme, Wmd, Wee, Wed);
+          valid = 0;
+        }
+        if (fabs(Gtotal-Mtotal) > 0.01*MAX(Gtotal,Mtotal)) {
+          log_warn(LD_DIR,
+                   "Bw Weight Failure for %s: Mtotal %lf != Gtotal %lf. "
+                   "G="I64_FORMAT" M="I64_FORMAT" E="I64_FORMAT" D="I64_FORMAT
+                   " T="I64_FORMAT". "
+                   "Wgg=%lf Wgd=%lf Wmg=%lf Wme=%lf Wmd=%lf Wee=%lf Wed=%lf",
+                   casename, Mtotal, Gtotal, G, M, E, D, T,
+                   Wgg, Wgd, Wmg, Wme, Wmd, Wee, Wed);
+          valid = 0;
+        }
+      } else {
+        if (fabs(Etotal-Gtotal) > 0.01*MAX(Etotal,Gtotal)) {
+          log_warn(LD_DIR,
+                   "Bw Weight Failure for %s: Etotal %lf != Gtotal %lf. "
+                   "G="I64_FORMAT" M="I64_FORMAT" E="I64_FORMAT" D="I64_FORMAT
+                   " T="I64_FORMAT". "
+                   "Wgg=%lf Wgd=%lf Wmg=%lf Wme=%lf Wmd=%lf Wee=%lf Wed=%lf",
+                   casename, Etotal, Gtotal, G, M, E, D, T,
+                   Wgg, Wgd, Wmg, Wme, Wmd, Wee, Wed);
+          valid = 0;
+        }
+      }
+    }
+  } else { // if (E < T/3 || G < T/3) {
+    int64_t S = MIN(E, G);
+    int64_t NS = MAX(E, G);
+    if (3*(S+D) < T) { // Subcase a:
+      double Stotal;
+      double NStotal;
+      if (G < E) {
+        casename = "Case 3a (G scarce)";
+        Stotal = Gtotal;
+        NStotal = Etotal;
+      } else { // if (G >= E) {
+        casename = "Case 3a (E scarce)";
+        NStotal = Gtotal;
+        Stotal = Etotal;
+      }
+      // Stotal < T/3
+      if (3*Stotal > T) {
+        log_warn(LD_DIR,
+                   "Bw Weight Failure for %s: 3*Stotal %lf > T "
+                   I64_FORMAT". G="I64_FORMAT" M="I64_FORMAT" E="I64_FORMAT
+                   " D="I64_FORMAT" T="I64_FORMAT". "
+                   "Wgg=%lf Wgd=%lf Wmg=%lf Wme=%lf Wmd=%lf Wee=%lf Wed=%lf",
+                   casename, Stotal*3, T, G, M, E, D, T,
+                   Wgg, Wgd, Wmg, Wme, Wmd, Wee, Wed);
+        valid = 0;
+      }
+      if (NS >= M) {
+        if (fabs(NStotal-Mtotal) > 0.01*MAX(NStotal,Mtotal)) {
+          log_warn(LD_DIR,
+                   "Bw Weight Failure for %s: NStotal %lf != Mtotal %lf. "
+                   "G="I64_FORMAT" M="I64_FORMAT" E="I64_FORMAT" D="I64_FORMAT
+                   " T="I64_FORMAT". "
+                   "Wgg=%lf Wgd=%lf Wmg=%lf Wme=%lf Wmd=%lf Wee=%lf Wed=%lf",
+                   casename, NStotal, Mtotal, G, M, E, D, T,
+                   Wgg, Wgd, Wmg, Wme, Wmd, Wee, Wed);
+          valid = 0;
+        }
+      } else {
+        // if NS < M, NStotal > T/3 because only one of G or E is scarce
+        if (3*NStotal < T) {
+          log_warn(LD_DIR,
+                     "Bw Weight Failure for %s: 3*NStotal %lf < T "
+                     I64_FORMAT". G="I64_FORMAT" M="I64_FORMAT
+                     " E="I64_FORMAT" D="I64_FORMAT" T="I64_FORMAT". "
+                     "Wgg=%lf Wgd=%lf Wmg=%lf Wme=%lf Wmd=%lf Wee=%lf Wed=%lf",
+                     casename, NStotal*3, T, G, M, E, D, T,
+                     Wgg, Wgd, Wmg, Wme, Wmd, Wee, Wed);
+          valid = 0;
+        }
+      }
+    } else { // Subcase b: S+D >= T/3
+      casename = "Case 3b";
+      if (fabs(Etotal-Mtotal) > 0.01*MAX(Etotal,Mtotal)) {
+        log_warn(LD_DIR,
+                 "Bw Weight Failure for %s: Etotal %lf != Mtotal %lf. "
+                 "G="I64_FORMAT" M="I64_FORMAT" E="I64_FORMAT" D="I64_FORMAT
+                 " T="I64_FORMAT". "
+                 "Wgg=%lf Wgd=%lf Wmg=%lf Wme=%lf Wmd=%lf Wee=%lf Wed=%lf",
+                 casename, Etotal, Mtotal, G, M, E, D, T,
+                 Wgg, Wgd, Wmg, Wme, Wmd, Wee, Wed);
+        valid = 0;
+      }
+      if (fabs(Etotal-Gtotal) > 0.01*MAX(Etotal,Gtotal)) {
+        log_warn(LD_DIR,
+                 "Bw Weight Failure for %s: Etotal %lf != Gtotal %lf. "
+                 "G="I64_FORMAT" M="I64_FORMAT" E="I64_FORMAT" D="I64_FORMAT
+                 " T="I64_FORMAT". "
+                 "Wgg=%lf Wgd=%lf Wmg=%lf Wme=%lf Wmd=%lf Wee=%lf Wed=%lf",
+                 casename, Etotal, Gtotal, G, M, E, D, T,
+                 Wgg, Wgd, Wmg, Wme, Wmd, Wee, Wed);
+        valid = 0;
+      }
+      if (fabs(Gtotal-Mtotal) > 0.01*MAX(Gtotal,Mtotal)) {
+        log_warn(LD_DIR,
+                 "Bw Weight Failure for %s: Mtotal %lf != Gtotal %lf. "
+                 "G="I64_FORMAT" M="I64_FORMAT" E="I64_FORMAT" D="I64_FORMAT
+                 " T="I64_FORMAT". "
+                 "Wgg=%lf Wgd=%lf Wmg=%lf Wme=%lf Wmd=%lf Wee=%lf Wed=%lf",
+                 casename, Mtotal, Gtotal, G, M, E, D, T,
+                 Wgg, Wgd, Wmg, Wme, Wmd, Wee, Wed);
+        valid = 0;
+      }
+    }
+  }
+
+  if (valid)
+    log_notice(LD_DIR, "Bandwidth-weight %s is verified and valid.",
+               casename);
+
+  return valid;
+}
+
 /** Parse a v3 networkstatus vote, opinion, or consensus (depending on
  * ns_type), from <b>s</b>, and return the result.  Return NULL on failure. */
 networkstatus_t *
@@ -2675,6 +3033,26 @@ networkstatus_parse_vote_from_string(const char *s, const char **eos_out,
     goto err;
   }
 
+  tok = find_opt_by_keyword(footer_tokens, K_BW_WEIGHTS);
+  if (tok) {
+    ns->weight_params = smartlist_create();
+    for (i = 0; i < tok->n_args; ++i) {
+      int ok=0;
+      char *eq = strchr(tok->args[i], '=');
+      if (!eq) {
+        log_warn(LD_DIR, "Bad element '%s' in weight params",
+                 escaped(tok->args[i]));
+        goto err;
+      }
+      tor_parse_long(eq+1, 10, INT32_MIN, INT32_MAX, &ok, NULL);
+      if (!ok) {
+        log_warn(LD_DIR, "Bad element '%s' in params", escaped(tok->args[i]));
+        goto err;
+      }
+      smartlist_add(ns->weight_params, tor_strdup(tok->args[i]));
+    }
+  }
+
   SMARTLIST_FOREACH_BEGIN(footer_tokens, directory_token_t *, _tok) {
     char declared_identity[DIGEST_LEN];
     networkstatus_voter_info_t *v;