aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--ChangeLog15
-rwxr-xr-xcontrib/checkSpace.pl12
-rw-r--r--doc/spec/dir-spec.txt197
-rw-r--r--doc/spec/path-spec.txt52
-rw-r--r--src/common/compat.c1
-rw-r--r--src/common/compat.h2
-rw-r--r--src/or/circuitbuild.c3
-rw-r--r--src/or/dirvote.c472
-rw-r--r--src/or/networkstatus.c49
-rw-r--r--src/or/or.h18
-rw-r--r--src/or/rephist.c4
-rw-r--r--src/or/routerlist.c223
-rw-r--r--src/or/routerparse.c394
-rw-r--r--src/test/test.c1
14 files changed, 1373 insertions, 70 deletions
diff --git a/ChangeLog b/ChangeLog
index f09671f17..c8369fc38 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,4 +1,18 @@
Changes in version 0.2.2.10-alpha - 2010-??-??
+ o Major features (performance):
+ - Alter the client path selection to use new consensus-generated
+ weightings to alter bandwidths when selecting Guard, Middle, Exit,
+ and Guard+Exit flagged nodes for entry, middle, and exit positions.
+ This should more evenly distribute the network load across these
+ different types of nodes, and give us the flexibility to globally
+ alter our node selection algorithms in the future.
+
+ o Minor features (performance):
+ - Always perform router selections using weighted node bandwidth,
+ even if we don't need a high capacity circuit at the time. Non-fast
+ circuits now only differ from fast ones in that they can use nodes
+ not marked with the Fast flag.
+
o Minor bugfixes:
- Fix a memleak in the EXTENDCIRCUIT logic. Spotted by coverity.
Bugfix on 0.2.2.9-alpha.
@@ -12,6 +26,7 @@ Changes in version 0.2.2.10-alpha - 2010-??-??
- Fix some urls in the exit notice file and make it XHTML1.1 strict
compliant. Based on a patch from Christian Kujau.
+
Changes in version 0.2.2.9-alpha - 2010-02-22
o Directory authority changes:
- Change IP address for dannenberg (v3 directory authority), and
diff --git a/contrib/checkSpace.pl b/contrib/checkSpace.pl
index db061a082..b694abff6 100755
--- a/contrib/checkSpace.pl
+++ b/contrib/checkSpace.pl
@@ -28,11 +28,15 @@ for $fn (@ARGV) {
if ($C && /\s(?:if|while|for|switch)\(/) {
print " KW(:$fn:$.\n";
}
- ## Warn about #else #if instead of #elif.
- if (($lastline =~ /^\# *else/) and ($_ =~ /^\# *if/)) {
+ ## Warn about #else #if instead of #elif.
+ if (($lastline =~ /^\# *else/) and ($_ =~ /^\# *if/)) {
print " #else#if:$fn:$.\n";
- }
- $lastline = $_;
+ }
+ $lastline = $_;
+ ## Warn about unnecessary empty lines.
+ if ($lastnil && /^\s*}\n/) {
+ print " UnnecNL:$fn:$.\n";
+ }
## Warn about multiple empty lines.
if ($lastnil && /^$/) {
print " DoubleNL:$fn:$.\n";
diff --git a/doc/spec/dir-spec.txt b/doc/spec/dir-spec.txt
index 19a32027a..442e7d582 100644
--- a/doc/spec/dir-spec.txt
+++ b/doc/spec/dir-spec.txt
@@ -1304,8 +1304,57 @@
or does not support (if 'reject') for exit to "most
addresses".
- The signature section contains the following item, which appears
- Exactly Once for a vote, and At Least Once for a consensus.
+ The footer section is delineated in all votes and consensuses supporting
+ consensus method 9 and above with the following:
+
+ "directory-footer" NL
+
+ It contains two subsections, a bandwidths-weights line and a
+ directory-signature.
+
+ The bandwidths-weights line appears At Most Once for a consensus. It does
+ not appear in votes.
+
+ "bandwidth-weights" SP
+ "Wbd=" INT SP "Wbe=" INT SP "Wbg=" INT SP "Wbm=" INT SP
+ "Wdb=" INT SP
+ "Web=" INT SP "Wed=" INT SP "Wee=" INT SP "Weg=" INT SP "Wem=" INT SP
+ "Wgb=" INT SP "Wgd=" INT SP "Wgg=" INT SP "Wgm=" INT SP
+ "Wmb=" INT SP "Wmd=" INT SP "Wme=" INT SP "Wmg=" INT SP "Wmm=" INT NL
+
+ These values represent the weights to apply to router bandwidths during
+ path selection. They are sorted in alphabetical order in the list. The
+ integer values are divided by BW_WEIGHT_SCALE=10000 or the consensus
+ param "bwweightscale". They are:
+
+ Wgg - Weight for Guard-flagged nodes in the guard position
+ Wgm - Weight for non-flagged nodes in the guard Position
+ Wgd - Weight for Guard+Exit-flagged nodes in the guard Position
+
+ Wmg - Weight for Guard-flagged nodes in the middle Position
+ Wmm - Weight for non-flagged nodes in the middle Position
+ Wme - Weight for Exit-flagged nodes in the middle Position
+ Wmd - Weight for Guard+Exit flagged nodes in the middle Position
+
+ Weg - Weight for Guard flagged nodes in the exit Position
+ Wem - Weight for non-flagged nodes in the exit Position
+ Wee - Weight for Exit-flagged nodes in the exit Position
+ Wed - Weight for Guard+Exit-flagged nodes in the exit Position
+
+ Wgb - Weight for BEGIN_DIR-supporting Guard-flagged nodes
+ Wmb - Weight for BEGIN_DIR-supporting non-flagged nodes
+ Web - Weight for BEGIN_DIR-supporting Exit-flagged nodes
+ Wdb - Weight for BEGIN_DIR-supporting Guard+Exit-flagged nodes
+
+ Wbg - Weight for Guard+Exit-flagged nodes for BEGIN_DIR requests
+ Wbm - Weight for Guard+Exit-flagged nodes for BEGIN_DIR requests
+ Wbe - Weight for Guard+Exit-flagged nodes for BEGIN_DIR requests
+ Wbd - Weight for Guard+Exit-flagged nodes for BEGIN_DIR requests
+
+ These values are calculated as specified in Section 3.4.3.
+
+ The signature contains the following item, which appears Exactly Once
+ for a vote, and At Least Once for a consensus.
"directory-signature" SP identity SP signing-key-digest NL Signature
@@ -1554,6 +1603,9 @@
"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
+ "7" -- Provides keyword=integer pairs of consensus parameters
+ "8" -- Provides microdescriptor summaries
+ "9" -- Provides weights for selecting flagged routers in paths
Before generating a consensus, an authority must decide which consensus
method to use. To do this, it looks for the highest version number
@@ -1586,6 +1638,147 @@
use an accept-style summary and list as much of the port list as is
possible within these 1000 bytes. [XXXX be more specific.]
+3.4.3. Computing Bandwidth Weights
+
+ Let weight_scale = 10000
+
+ Let G be the total bandwidth for Guard-flagged nodes.
+ Let M be the total bandwidth for non-flagged nodes.
+ Let E be the total bandwidth for Exit-flagged nodes.
+ Let D be the total bandwidth for Guard+Exit-flagged nodes.
+ Let T = G+M+E+D
+
+ Let Wgd be the weight for choosing a Guard+Exit for the guard position.
+ Let Wmd be the weight for choosing a Guard+Exit for the middle position.
+ Let Wed be the weight for choosing a Guard+Exit for the exit position.
+
+ Let Wme be the weight for choosing an Exit for the middle position.
+ Let Wmg be the weight for choosing a Guard for the middle position.
+
+ Let Wgg be the weight for choosing a Guard for the guard position.
+ Let Wee be the weight for choosing an Exit for the exit position.
+
+ Balanced network conditions then arise from solutions to the following
+ system of equations:
+
+ Wgg*G + Wgd*D == M + Wmd*D + Wme*E + Wmg*G (guard bw = middle bw)
+ Wgg*G + Wgd*D == Wee*E + Wed*D (guard bw = exit bw)
+ Wed*D + Wmd*D + Wgd*D == D (aka: Wed+Wmd+Wdg = 1)
+ Wmg*G + Wgg*G == G (aka: Wgg = 1-Wmg)
+ Wme*E + Wee*E == E (aka: Wee = 1-Wme)
+
+ We are short 2 constraints with the above set. The remaining constraints
+ come from examining different cases of network load.
+
+ Case 1: E >= T/3 && G >= T/3 (Neither Exit nor Guard Scarce)
+
+ In this case, the additional two constraints are: Wme*E == Wmd*D and
+ Wgd == 0, which maximizes Exit-flagged bandwidth in the middle position.
+
+ This leads to the solution:
+
+ Wgg = (weight_scale*(D+E+G+M))/(3*G)
+ Wmd = (weight_scale*(2*D + 2*E - G - M))/(6*D)
+ Wme = (weight_scale*(2*D + 2*E - G - M))/(6*E)
+ Wee = (weight_scale*(-2*D + 4*E + G + M))/(6*E)
+ Wmg = weight_scale - Wgg
+ Wed = weight_scale - Wmd
+ Wgd = 0
+
+ Case 2: E < T/3 && G < T/3 (Both are scarce)
+
+ Let R denote the more scarce class (Rare) between Guard vs Exit.
+ Let S denote the less scarce class.
+
+ Subcase a: R+D < S
+
+ In this subcase, we simply devote all of D bandwidth to the
+ scarce class.
+
+ Wgg = Wee = weight_scale
+ Wmg = Wme = Wmd = 0;
+ if E < G:
+ Wed = weight_scale
+ Wgd = 0
+ else:
+ Wed = 0
+ Wgd = weight_scale
+
+ Subcase b: R+D >= S
+
+ In this case, if M <= T/3, we have enough bandwidth to try to achieve
+ a balancing condition, and add the constraints Wgg == 1 and
+ Wme*E == Wmd*D:
+
+ Wgg = weight_scale
+ Wgd = (weight_scale*(D + E - 2*G + M))/(3*D) (T/3 >= G (Ok))
+ Wmd = (weight_scale*(D + E + G - 2*M))/(6*D) (T/3 >= M)
+ Wme = (weight_scale*(D + E + G - 2*M))/(6*E)
+ Wee = (weight_scale*(-D + 5*E - G + 2*M))/(6*E) (2E+M >= T/3)
+ Wmg = 0;
+ Wed = weight_scale - Wgd - Wmd
+
+ If M >= T/3, the above solution will not be valid (one of the weights
+ will be < 0 or > 1). In this case, we use:
+
+ Wgg = weight_scale
+ Wee = weight_scale
+ Wmg = Wme = Wmd = 0
+ Wgd = (weight_scale*(D+E-G))/(2*D)
+ Wed = weight_scale - Wgd
+
+ Case 3: One of E < T/3 or G < T/3
+
+ Let S be the scarce class (of E or G).
+
+ Subcase a: (S+D) < T/3:
+ if G=S:
+ Wgg = Wgd = weight_scale;
+ Wmd = Wed = Wmg = 0;
+ Wme = (weight_scale*(E-M))/(2*E);
+ Wee = weight_scale-Wme;
+ if E=S:
+ Wee = Wed = weight_scale;
+ Wmd = Wgd = Wmg = 0;
+ Wmg = (weight_scale*(G-M))/(2*G);
+ Wgg = weight_scale-Wmg;
+
+ Subcase b: (S+D) >= T/3
+ if G=S:
+ Add constraints Wmg = 0, Wme*E == Wmd*D to maximize exit bandwidth
+ in the middle position:
+ Wgd = (weight_scale*(D + E - 2*G + M))/(3*D);
+ Wmd = (weight_scale*(D + E + G - 2*M))/(6*D);
+ Wme = (weight_scale*(D + E + G - 2*M))/(6*E);
+ Wee = (weight_scale*(-D + 5*E - G + 2*M))/(6*E);
+ Wgg = weight_scale;
+ Wmg = 0;
+ Wed = weight_scale - Wgd - Wmd;
+ if E=S:
+ Add constraints Wgd = 0, Wme*E == Wmd*D:
+ Wgg = (weight_scale*(D + E + G + M))/(3*G);
+ Wmd = (weight_scale*(2*D + 2*E - G - M))/(6*D);
+ Wme = (weight_scale*(2*D + 2*E - G - M))/(6*E);
+ Wee = (weight_scale*(-2*D + 4*E + G + M))/(6*E);
+ Wgd = 0;
+ Wmg = weight_scale - Wgg;
+ Wed = weight_scale - Wmd;
+
+ To ensure consensus, all calculations are performed using integer math
+ with a fixed precision determined by the bwweightscale consensus
+ parameter (defaults at 10000).
+
+ For future balancing improvements, Tor clients support 11 additional weights
+ for directory requests and middle weighting. These weights are currently
+ set at weight_scale, with the exception of the following groups of
+ assignments:
+
+ Directory requests use middle weights:
+ Wbd=Wmd, Wbg=Wmg, Wbe=Wme, Wbm=Wmm
+
+ Handle bridges and strange exit policies:
+ Wgm=Wgg, Wem=Wee, Weg=Wed
+
3.5. Detached signatures
Assuming full connectivity, every authority should compute and sign the
diff --git a/doc/spec/path-spec.txt b/doc/spec/path-spec.txt
index 78f3b63bc..8a85718a0 100644
--- a/doc/spec/path-spec.txt
+++ b/doc/spec/path-spec.txt
@@ -192,23 +192,41 @@ of their choices.
below)
- XXXX Choosing the length
- For circuits that do not need to be "fast", when choosing among
- multiple candidates for a path element, we choose randomly.
-
- For "fast" circuits, we pick a given router as an exit with probability
- proportional to its bandwidth.
-
- For non-exit positions on "fast" circuits, we pick routers as above, but
- we weight the bandwidth of Exit-flagged nodes depending
- on the fraction of bandwidth available from non-Exit nodes. Call the
- total bandwidth for Exit nodes under consideration E,
- and the total bandwidth for all nodes under
- consideration T. If E<T/3, we do not consider Exit-flagged nodes.
- Otherwise, we weight their bandwidth with the factor (E-T/3)/E. This
- ensures that bandwidth is evenly distributed over nodes in 3-hop paths.
-
- Similarly, guard nodes are weighted by the factor (G-T/3)/G, and not
- considered for non-guard positions if this value is less than 0.
+ For "fast" circuits, we only choose nodes with the Fast flag. For
+ non-"fast" circuits, all nodes are eligible.
+
+ For all circuits, we weight node selection according to router bandwidth.
+
+ We also weight the bandwidth of Exit and Guard flagged nodes depending on
+ the fraction of total bandwidth that they make up and depending upon the
+ position they are being selected for.
+
+ These weights are published in the consensus, and are computed as described
+ in Section 3.4.3 of dir-spec.txt. They are:
+
+ Wgg - Weight for Guard-flagged nodes in the guard position
+ Wgm - Weight for non-flagged nodes in the guard Position
+ Wgd - Weight for Guard+Exit-flagged nodes in the guard Position
+
+ Wmg - Weight for Guard-flagged nodes in the middle Position
+ Wmm - Weight for non-flagged nodes in the middle Position
+ Wme - Weight for Exit-flagged nodes in the middle Position
+ Wmd - Weight for Guard+Exit flagged nodes in the middle Position
+
+ Weg - Weight for Guard flagged nodes in the exit Position
+ Wem - Weight for non-flagged nodes in the exit Position
+ Wee - Weight for Exit-flagged nodes in the exit Position
+ Wed - Weight for Guard+Exit-flagged nodes in the exit Position
+
+ Wgb - Weight for BEGIN_DIR-supporting Guard-flagged nodes
+ Wmb - Weight for BEGIN_DIR-supporting non-flagged nodes
+ Web - Weight for BEGIN_DIR-supporting Exit-flagged nodes
+ Wdb - Weight for BEGIN_DIR-supporting Guard+Exit-flagged nodes
+
+ Wbg - Weight for Guard+Exit-flagged nodes for BEGIN_DIR requests
+ Wbm - Weight for Guard+Exit-flagged nodes for BEGIN_DIR requests
+ Wbe - Weight for Guard+Exit-flagged nodes for BEGIN_DIR requests
+ Wbd - Weight for Guard+Exit-flagged nodes for BEGIN_DIR requests
Additionally, we may be building circuits with one or more requests in
mind. Each kind of request puts certain constraints on paths:
diff --git a/src/common/compat.c b/src/common/compat.c
index 406d74eb2..33e32d433 100644
--- a/src/common/compat.c
+++ b/src/common/compat.c
@@ -1789,7 +1789,6 @@ spawn_exit(void)
* call _exit, not exit, from child processes. */
_exit(0);
#endif
-
}
/** Set *timeval to the current time of day. On error, log and terminate.
diff --git a/src/common/compat.h b/src/common/compat.h
index 554ae8919..60fb1cb65 100644
--- a/src/common/compat.h
+++ b/src/common/compat.h
@@ -206,8 +206,10 @@ size_t strlcpy(char *dst, const char *src, size_t siz) ATTR_NONNULL((1,2));
/** The formatting string used to put a uint64_t value in a printf() or
* scanf() function. See also U64_PRINTF_ARG and U64_SCANF_ARG. */
#define U64_FORMAT "%I64u"
+#define I64_FORMAT "%I64d"
#else
#define U64_FORMAT "%llu"
+#define I64_FORMAT "%lld"
#endif
/** Represents an mmaped file. Allocated via tor_mmap_file; freed with
diff --git a/src/or/circuitbuild.c b/src/or/circuitbuild.c
index 08ee58416..5780e6dcd 100644
--- a/src/or/circuitbuild.c
+++ b/src/or/circuitbuild.c
@@ -1030,7 +1030,6 @@ circuit_build_times_set_timeout(circuit_build_times_t *cbt)
"Set circuit build timeout to %lds (%lfms, Xm: %d, a: %lf) "
"based on %d circuit times", tor_lround(cbt->timeout_ms/1000),
cbt->timeout_ms, cbt->Xm, cbt->alpha, cbt->total_build_times);
-
}
/** Iterate over values of circ_id, starting from conn-\>next_circ_id,
@@ -2133,6 +2132,8 @@ circuit_all_predicted_ports_handled(time_t now, int *need_uptime,
smartlist_t *LongLivedServices = get_options()->LongLivedPorts;
tor_assert(need_uptime);
tor_assert(need_capacity);
+ // Always predict need_capacity
+ *need_capacity = 1;
enough = (smartlist_len(sl) == 0);
for (i = 0; i < smartlist_len(sl); ++i) {
port = smartlist_get(sl, i);
diff --git a/src/or/dirvote.c b/src/or/dirvote.c
index 7227ac974..8643ef367 100644
--- a/src/or/dirvote.c
+++ b/src/or/dirvote.c
@@ -39,8 +39,15 @@ static int dirvote_publish_consensus(void);
static char *make_consensus_method_list(int low, int high, const char *sep);
/** The highest consensus method that we currently support. */
-#define MAX_SUPPORTED_CONSENSUS_METHOD 8
+#define MAX_SUPPORTED_CONSENSUS_METHOD 9
+/** Lowest consensus method that contains a 'directory-footer' marker */
+#define MIN_METHOD_FOR_FOOTER 9
+
+/** Lowest consensus method that contains bandwidth weights */
+#define MIN_METHOD_FOR_BW_WEIGHTS 9
+
+/** Lowest consensus method that contains consensus params */
#define MIN_METHOD_FOR_PARAMS 7
/** Lowest consensus method that generates microdescriptors */
@@ -71,6 +78,7 @@ format_networkstatus_vote(crypto_pk_env_t *private_signing_key,
uint32_t addr;
routerlist_t *rl = router_get_routerlist();
char *version_lines = NULL;
+ int r;
networkstatus_voter_info_t *voter;
tor_assert(private_signing_key);
@@ -97,13 +105,22 @@ format_networkstatus_vote(crypto_pk_env_t *private_signing_key,
version_lines = tor_malloc(v_len);
cp = version_lines;
if (client_versions) {
- tor_snprintf(cp, v_len-(cp-version_lines),
+ r = tor_snprintf(cp, v_len-(cp-version_lines),
"client-versions %s\n", client_versions);
+ if (r < 0) {
+ log_err(LD_BUG, "Insufficient memory for client-versions line");
+ tor_assert(0);
+ }
cp += strlen(cp);
}
- if (server_versions)
- tor_snprintf(cp, v_len-(cp-version_lines),
+ if (server_versions) {
+ r = tor_snprintf(cp, v_len-(cp-version_lines),
"server-versions %s\n", server_versions);
+ if (r < 0) {
+ log_err(LD_BUG, "Insufficient memory for server-versions line");
+ tor_assert(0);
+ }
+ }
} else {
version_lines = tor_strdup("");
}
@@ -111,6 +128,7 @@ format_networkstatus_vote(crypto_pk_env_t *private_signing_key,
len = 8192;
len += strlen(version_lines);
len += (RS_ENTRY_LEN+MICRODESC_LINE_LEN)*smartlist_len(rl->routers);
+ len += strlen("\ndirectory-footer\n");
len += v3_ns->cert->cache_info.signed_descriptor_len;
status = tor_malloc(len);
@@ -135,7 +153,7 @@ format_networkstatus_vote(crypto_pk_env_t *private_signing_key,
params = tor_strdup("");
tor_assert(cert);
- tor_snprintf(status, len,
+ r = tor_snprintf(status, len,
"network-status-version 3\n"
"vote-status %s\n"
"consensus-methods %s\n"
@@ -159,6 +177,11 @@ format_networkstatus_vote(crypto_pk_env_t *private_signing_key,
voter->nickname, fingerprint, voter->address,
ipaddr, voter->dir_port, voter->or_port, voter->contact);
+ if (r < 0) {
+ log_err(LD_BUG, "Insufficient memory for network status line");
+ tor_assert(0);
+ }
+
tor_free(params);
tor_free(flags);
tor_free(methods);
@@ -168,7 +191,11 @@ format_networkstatus_vote(crypto_pk_env_t *private_signing_key,
if (!tor_digest_is_zero(voter->legacy_id_digest)) {
char fpbuf[HEX_DIGEST_LEN+1];
base16_encode(fpbuf, sizeof(fpbuf), voter->legacy_id_digest, DIGEST_LEN);
- tor_snprintf(outp, endp-outp, "legacy-dir-key %s\n", fpbuf);
+ r = tor_snprintf(outp, endp-outp, "legacy-dir-key %s\n", fpbuf);
+ if (r < 0) {
+ log_err(LD_BUG, "Insufficient memory for legacy-dir-key line");
+ tor_assert(0);
+ }
outp += strlen(outp);
}
@@ -199,6 +226,13 @@ format_networkstatus_vote(crypto_pk_env_t *private_signing_key,
}
} SMARTLIST_FOREACH_END(vrs);
+ r = tor_snprintf(outp, endp-outp, "directory-footer\n");
+ if (r < 0) {
+ log_err(LD_BUG, "Insufficient memory for directory-footer line");
+ tor_assert(0);
+ }
+ outp += strlen(outp);
+
{
char signing_key_fingerprint[FINGERPRINT_LEN+1];
if (tor_snprintf(outp, endp-outp, "directory-signature ")<0) {
@@ -648,6 +682,358 @@ dirvote_compute_params(smartlist_t *votes)
return result;
}
+#define RANGE_CHECK(a,b,c,d,e,f,g,mx) \
+ ((a) >= 0 && (a) <= (mx) && (b) >= 0 && (b) <= (mx) && \
+ (c) >= 0 && (c) <= (mx) && (d) >= 0 && (d) <= (mx) && \
+ (e) >= 0 && (e) <= (mx) && (f) >= 0 && (f) <= (mx) && \
+ (g) >= 0 && (g) <= (mx))
+
+#define CHECK_EQ(a, b, margin) \
+ ((a)-(b) >= 0 ? (a)-(b) <= (margin) : (b)-(a) <= (margin))
+
+typedef enum {
+ BW_WEIGHTS_NO_ERROR = 0,
+ BW_WEIGHTS_RANGE_ERROR = 1,
+ BW_WEIGHTS_SUMG_ERROR = 2,
+ BW_WEIGHTS_SUME_ERROR = 3,
+ BW_WEIGHTS_SUMD_ERROR = 4,
+ BW_WEIGHTS_BALANCE_MID_ERROR = 5,
+ BW_WEIGHTS_BALANCE_EG_ERROR = 6
+} bw_weights_error_t;
+
+/**
+ * Verify that any weightings satisfy the balanced formulas.
+ */
+static bw_weights_error_t
+networkstatus_check_weights(int64_t Wgg, int64_t Wgd, int64_t Wmg,
+ int64_t Wme, int64_t Wmd, int64_t Wee,
+ int64_t Wed, int64_t scale, int64_t G,
+ int64_t M, int64_t E, int64_t D, int64_t T,
+ int64_t margin, int do_balance) {
+ bw_weights_error_t berr = BW_WEIGHTS_NO_ERROR;
+
+ // Wed + Wmd + Wgd == 1
+ if (!CHECK_EQ(Wed + Wmd + Wgd, scale, margin)) {
+ berr = BW_WEIGHTS_SUMD_ERROR;
+ goto out;
+ }
+
+ // Wmg + Wgg == 1
+ if (!CHECK_EQ(Wmg + Wgg, scale, margin)) {
+ berr = BW_WEIGHTS_SUMG_ERROR;
+ goto out;
+ }
+
+ // Wme + Wee == 1
+ if (!CHECK_EQ(Wme + Wee, scale, margin)) {
+ berr = BW_WEIGHTS_SUME_ERROR;
+ goto out;
+ }
+
+ // Verify weights within range 0->1
+ if (!RANGE_CHECK(Wgg, Wgd, Wmg, Wme, Wmd, Wed, Wee, scale)) {
+ berr = BW_WEIGHTS_RANGE_ERROR;
+ goto out;
+ }
+
+ if (do_balance) {
+ // Wgg*G + Wgd*D == Wee*E + Wed*D, already scaled
+ if (!CHECK_EQ(Wgg*G + Wgd*D, Wee*E + Wed*D, (margin*T)/3)) {
+ berr = BW_WEIGHTS_BALANCE_EG_ERROR;
+ goto out;
+ }
+
+ // Wgg*G + Wgd*D == M*scale + Wmd*D + Wme*E + Wmg*G, already scaled
+ if (!CHECK_EQ(Wgg*G + Wgd*D, M*scale + Wmd*D + Wme*E + Wmg*G,
+ (margin*T)/3)) {
+ berr = BW_WEIGHTS_BALANCE_MID_ERROR;
+ goto out;
+ }
+ }
+
+out:
+ if (berr) {
+ log_info(LD_DIR,
+ "Bw weight mismatch %d. G="I64_FORMAT" M="I64_FORMAT
+ " E="I64_FORMAT" D="I64_FORMAT" T="I64_FORMAT,
+ berr, G, M, E, D, T);
+ }
+
+ return berr;
+}
+
+static void
+networkstatus_compute_bw_weights_v9(smartlist_t *chunks, int64_t G, int64_t M,
+ int64_t E, int64_t D, int64_t T,
+ int64_t weight_scale)
+{
+ int64_t Wgg = -1, Wgd = -1;
+ int64_t Wmg = -1, Wme = -1, Wmd = -1;
+ int64_t Wed = -1, Wee = -1;
+ const char *casename;
+ char buf[512];
+ int r;
+
+ if (G <= 0 || M <= 0 || E <= 0 || D <= 0) {
+ log_warn(LD_DIR, "Consensus with empty bandwidth: "
+ "G="I64_FORMAT" M="I64_FORMAT" E="I64_FORMAT
+ " D="I64_FORMAT" T="I64_FORMAT,
+ G, M, E, D, T);
+ return;
+ }
+
+ /*
+ * Computed from cases in 3.4.3 of dir-spec.txt
+ *
+ * 1. Neither are scarce
+ * 2. Both Guard and Exit are scarce
+ * a. R+D <= S
+ * b. R+D > S
+ * 3. One of Guard or Exit is scarce
+ * a. S+D < T/3
+ * b. S+D >= T/3
+ */
+ if (3*E >= T && 3*G >= T) { // E >= T/3 && G >= T/3
+ bw_weights_error_t berr = 0;
+ /* Case 1: Neither are scarce.
+ *
+ * Attempt to ensure that we have a large amount of exit bandwidth
+ * in the middle position.
+ */
+ casename = "Case 1 (Wme*E = Wmd*D)";
+ Wgg = (weight_scale*(D+E+G+M))/(3*G);
+ if (D==0) Wmd = 0;
+ else Wmd = (weight_scale*(2*D + 2*E - G - M))/(6*D);
+ Wme = (weight_scale*(2*D + 2*E - G - M))/(6*E);
+ Wee = (weight_scale*(-2*D + 4*E + G + M))/(6*E);
+ Wgd = 0;
+ Wmg = weight_scale - Wgg;
+ Wed = weight_scale - Wmd;
+
+ berr = networkstatus_check_weights(Wgg, Wgd, Wmg, Wme, Wmd, Wee, Wed,
+ weight_scale, G, M, E, D, T, 10, 1);
+
+ if (berr) {
+ log_warn(LD_DIR, "Bw Weights error %d for case %s. "
+ "G="I64_FORMAT" M="I64_FORMAT" E="I64_FORMAT
+ " D="I64_FORMAT" T="I64_FORMAT,
+ berr, casename, G, M, E, D, T);
+ }
+ } else if (3*E < T && 3*G < T) { // E < T/3 && G < T/3
+ 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.
+ */
+ if (R+D < S) { // Subcase a
+ Wgg = weight_scale;
+ Wee = weight_scale;
+ Wmg = 0;
+ Wme = 0;
+ Wmd = 0;
+ if (E < G) {
+ casename = "Case 2a (E scarce)";
+ Wed = weight_scale;
+ Wgd = 0;
+ } else if (E >= G) {
+ casename = "Case 2a (G scarce)";
+ Wed = 0;
+ Wgd = weight_scale;
+ }
+ } else { // Subcase b: R+D > S
+ bw_weights_error_t berr = 0;
+ casename = "Case 2b (Wme*E == Wmd*D)";
+ if (D != 0) {
+ Wgg = weight_scale;
+ Wgd = (weight_scale*(D + E - 2*G + M))/(3*D); // T/3 >= G (Ok)
+ Wmd = (weight_scale*(D + E + G - 2*M))/(6*D); // T/3 >= M
+ Wme = (weight_scale*(D + E + G - 2*M))/(6*E);
+ Wee = (weight_scale*(-D + 5*E - G + 2*M))/(6*E); // 2E+M >= T/3
+ Wmg = 0;
+ Wed = weight_scale - Wgd - Wmd;
+
+ berr = networkstatus_check_weights(Wgg, Wgd, Wmg, Wme, Wmd, Wee, Wed,
+ weight_scale, G, M, E, D, T, 10, 1);
+ }
+
+ if (D == 0 || berr) { // Can happen if M > T/3
+ casename = "Case 2b (E=G)";
+ Wgg = weight_scale;
+ Wee = weight_scale;
+ Wmg = 0;
+ Wme = 0;
+ Wmd = 0;
+ if (D == 0) Wgd = 0;
+ else Wgd = (weight_scale*(D+E-G))/(2*D);
+ Wed = weight_scale - Wgd;
+ berr = networkstatus_check_weights(Wgg, Wgd, Wmg, Wme, Wmd, Wee,
+ Wed, weight_scale, G, M, E, D, T, 10, 1);
+ }
+ if (berr != BW_WEIGHTS_NO_ERROR &&
+ berr != BW_WEIGHTS_BALANCE_MID_ERROR) {
+ log_warn(LD_DIR, "Bw Weights error %d for case %s. "
+ "G="I64_FORMAT" M="I64_FORMAT" E="I64_FORMAT
+ " D="I64_FORMAT" T="I64_FORMAT,
+ berr, casename, G, M, E, D, T);
+ }
+ }
+ } else { // if (E < T/3 || G < T/3) {
+ int64_t S = MIN(E, G);
+ // Case 3: Exactly one of Guard or Exit is scarce
+ if (!(3*E < T || 3*G < T) || !(3*G >= T || 3*E >= T)) {
+ log_warn(LD_BUG,
+ "Bw-Weights Case 3 but with G="I64_FORMAT" M="
+ I64_FORMAT" E="I64_FORMAT" D="I64_FORMAT" T="I64_FORMAT,
+ G, M, E, D, T);
+ }
+
+ if (3*(S+D) < T) { // Subcase a: S+D < T/3
+ if (G < E) {
+ casename = "Case 3a (G scarce)";
+ Wgg = Wgd = weight_scale;
+ Wmd = Wed = Wmg = 0;
+ // Minor subcase, if E is more scarce than M,
+ // keep its bandwidth in place.
+ if (E < M) Wme = 0;
+ else Wme = (weight_scale*(E-M))/(2*E);
+ Wee = weight_scale-Wme;
+ } else { // G >= E
+ casename = "Case 3a (E scarce)";
+ Wee = Wed = weight_scale;
+ Wmd = Wgd = Wme = 0;
+ // Minor subcase, if G is more scarce than M,
+ // keep its bandwidth in place.
+ if (G < M) Wmg = 0;
+ else Wmg = (weight_scale*(G-M))/(2*G);
+ Wgg = weight_scale-Wmg;
+ }
+ } else { // Subcase b: S+D >= T/3
+ bw_weights_error_t berr = 0;
+ // D != 0 because S+D >= T/3
+ if (G < E) {
+ casename = "Case 3b (G scarce, Wme*E == Wmd*D)";
+ Wgd = (weight_scale*(D + E - 2*G + M))/(3*D);
+ Wmd = (weight_scale*(D + E + G - 2*M))/(6*D);
+ Wme = (weight_scale*(D + E + G - 2*M))/(6*E);
+ Wee = (weight_scale*(-D + 5*E - G + 2*M))/(6*E);
+ Wgg = weight_scale;
+ Wmg = 0;
+ Wed = weight_scale - Wgd - Wmd;
+
+ berr = networkstatus_check_weights(Wgg, Wgd, Wmg, Wme, Wmd, Wee,
+ Wed, weight_scale, G, M, E, D, T, 10, 1);
+ } else { // G >= E
+ casename = "Case 3b (E scarce, Wme*E == Wmd*D)";
+ Wgg = (weight_scale*(D + E + G + M))/(3*G);
+ Wmd = (weight_scale*(2*D + 2*E - G - M))/(6*D);
+ Wme = (weight_scale*(2*D + 2*E - G - M))/(6*E);
+ Wee = (weight_scale*(-2*D + 4*E + G + M))/(6*E);
+ Wgd = 0;
+ Wmg = weight_scale - Wgg;
+ Wed = weight_scale - Wmd;
+
+ berr = networkstatus_check_weights(Wgg, Wgd, Wmg, Wme, Wmd, Wee,
+ Wed, weight_scale, G, M, E, D, T, 10, 1);
+ }
+ if (berr) {
+ log_warn(LD_DIR, "Bw Weights error %d for case %s. "
+ "G="I64_FORMAT" M="I64_FORMAT
+ " E="I64_FORMAT" D="I64_FORMAT" T="I64_FORMAT,
+ berr, casename, G, M, E, D, T);
+ }
+ }
+ }
+
+ /* We cast down the weights to 32 bit ints on the assumption that
+ * weight_scale is ~= 10000. We need to ensure a rogue authority
+ * doesn't break this assumption to rig our weights */
+ tor_assert(0 < weight_scale && weight_scale < INT32_MAX);
+
+ if (Wgg < 0 || Wgg > weight_scale) {
+ log_warn(LD_DIR, "Bw %s: Wgg="I64_FORMAT"! G="I64_FORMAT
+ " M="I64_FORMAT" E="I64_FORMAT" D="I64_FORMAT
+ " T="I64_FORMAT,
+ casename, Wgg, G, M, E, D, T);
+ Wgg = MAX(MIN(Wgg, weight_scale), 0);
+ }
+ if (Wgd < 0 || Wgd > weight_scale) {
+ log_warn(LD_DIR, "Bw %s: Wgd="I64_FORMAT"! G="I64_FORMAT
+ " M="I64_FORMAT" E="I64_FORMAT" D="I64_FORMAT
+ " T="I64_FORMAT,
+ casename, Wgd, G, M, E, D, T);
+ Wgd = MAX(MIN(Wgd, weight_scale), 0);
+ }
+ if (Wmg < 0 || Wmg > weight_scale) {
+ log_warn(LD_DIR, "Bw %s: Wmg="I64_FORMAT"! G="I64_FORMAT
+ " M="I64_FORMAT" E="I64_FORMAT" D="I64_FORMAT
+ " T="I64_FORMAT,
+ casename, Wmg, G, M, E, D, T);
+ Wmg = MAX(MIN(Wmg, weight_scale), 0);
+ }
+ if (Wme < 0 || Wme > weight_scale) {
+ log_warn(LD_DIR, "Bw %s: Wme="I64_FORMAT"! G="I64_FORMAT
+ " M="I64_FORMAT" E="I64_FORMAT" D="I64_FORMAT
+ " T="I64_FORMAT,
+ casename, Wme, G, M, E, D, T);
+ Wme = MAX(MIN(Wme, weight_scale), 0);
+ }
+ if (Wmd < 0 || Wmd > weight_scale) {
+ log_warn(LD_DIR, "Bw %s: Wmd="I64_FORMAT"! G="I64_FORMAT
+ " M="I64_FORMAT" E="I64_FORMAT" D="I64_FORMAT
+ " T="I64_FORMAT,
+ casename, Wmd, G, M, E, D, T);
+ Wmd = MAX(MIN(Wmd, weight_scale), 0);
+ }
+ if (Wee < 0 || Wee > weight_scale) {
+ log_warn(LD_DIR, "Bw %s: Wee="I64_FORMAT"! G="I64_FORMAT
+ " M="I64_FORMAT" E="I64_FORMAT" D="I64_FORMAT
+ " T="I64_FORMAT,
+ casename, Wee, G, M, E, D, T);
+ Wee = MAX(MIN(Wee, weight_scale), 0);
+ }
+ if (Wed < 0 || Wed > weight_scale) {
+ log_warn(LD_DIR, "Bw %s: Wed="I64_FORMAT"! G="I64_FORMAT
+ " M="I64_FORMAT" E="I64_FORMAT" D="I64_FORMAT
+ " T="I64_FORMAT,
+ casename, Wed, G, M, E, D, T);
+ Wed = MAX(MIN(Wed, weight_scale), 0);
+ }
+
+ // Add consensus weight keywords
+ smartlist_add(chunks, tor_strdup("bandwidth-weights "));
+ /*
+ * Provide Wgm=Wgg, Wmm=1, Wem=Wee, Weg=Wed. May later determine
+ * that middle nodes need different bandwidth weights for dirport traffic,
+ * or that weird exit policies need special weight, or that bridges
+ * need special weight.
+ *
+ * NOTE: This list is sorted.
+ */
+ r = tor_snprintf(buf, sizeof(buf),
+ "Wbd=%d Wbe=%d Wbg=%d Wbm=%d "
+ "Wdb=%d "
+ "Web=%d Wed=%d Wee=%d Weg=%d Wem=%d "
+ "Wgb=%d Wgd=%d Wgg=%d Wgm=%d "
+ "Wmb=%d Wmd=%d Wme=%d Wmg=%d Wmm=%d\n",
+ (int)Wmd, (int)Wme, (int)Wmg, (int)weight_scale,
+ (int)weight_scale,
+ (int)weight_scale, (int)Wed, (int)Wee, (int)Wed, (int)Wee,
+ (int)weight_scale, (int)Wgd, (int)Wgg, (int)Wgg,
+ (int)weight_scale, (int)Wmd, (int)Wme, (int)Wmg, (int)weight_scale);
+ if (r<0) {
+ log_warn(LD_BUG,
+ "Not enough space in buffer for bandwidth-weights line.");
+ *buf = '\0';
+ }
+ smartlist_add(chunks, tor_strdup(buf));
+ log_notice(LD_CIRC, "Computed bandwidth weights for %s: "
+ "G="I64_FORMAT" M="I64_FORMAT" E="I64_FORMAT" D="I64_FORMAT
+ " T="I64_FORMAT,
+ casename, G, M, E, D, T);
+}
+
/** 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
@@ -673,9 +1059,10 @@ networkstatus_compute_consensus(smartlist_t *votes,
char *client_versions = NULL, *server_versions = NULL;
smartlist_t *flags;
const char *flavor_name;
+ int64_t G=0, M=0, E=0, D=0, T=0; /* For bandwidth weights */
const routerstatus_format_type_t rs_format =
flavor == FLAV_NS ? NS_V3_CONSENSUS : NS_V3_CONSENSUS_MICRODESC;
-
+ char *params = NULL;
tor_assert(flavor == FLAV_NS || flavor == FLAV_MICRODESC);
tor_assert(total_authorities >= smartlist_len(votes));
@@ -812,7 +1199,7 @@ networkstatus_compute_consensus(smartlist_t *votes,
}
if (consensus_method >= MIN_METHOD_FOR_PARAMS) {
- char *params = dirvote_compute_params(votes);
+ params = dirvote_compute_params(votes);
if (params) {
smartlist_add(chunks, tor_strdup("params "));
smartlist_add(chunks, params);
@@ -1008,6 +1395,7 @@ networkstatus_compute_consensus(smartlist_t *votes,
const char *chosen_name = NULL;
int exitsummary_disagreement = 0;
int is_named = 0, is_unnamed = 0, is_running = 0;
+ int is_guard = 0, is_exit = 0;
int naming_conflict = 0;
int n_listing = 0;
int i;
@@ -1127,7 +1515,11 @@ networkstatus_compute_consensus(smartlist_t *votes,
} else {
if (flag_counts[fl_sl_idx] > n_flag_voters[fl_sl_idx]/2) {
smartlist_add(chosen_flags, (char*)fl);
- if (!strcmp(fl, "Running"))
+ if (!strcmp(fl, "Exit"))
+ is_exit = 1;
+ else if (!strcmp(fl, "Guard"))
+ is_guard = 1;
+ else if (!strcmp(fl, "Running"))
is_running = 1;
}
}
@@ -1155,6 +1547,23 @@ networkstatus_compute_consensus(smartlist_t *votes,
rs_out.bandwidth = median_uint32(bandwidths, num_bandwidths);
}
+ if (consensus_method >= MIN_METHOD_FOR_BW_WEIGHTS) {
+ if (rs_out.has_bandwidth) {
+ T += rs_out.bandwidth;
+ if (is_exit && is_guard)
+ D += rs_out.bandwidth;
+ else if (is_exit)
+ E += rs_out.bandwidth;
+ else if (is_guard)
+ G += rs_out.bandwidth;
+ else
+ M += rs_out.bandwidth;
+ } else {
+ log_warn(LD_BUG, "Missing consensus bandwidth for router %s",
+ rs_out.nickname);
+ }
+ }
+
/* Ok, we already picked a descriptor digest we want to list
* previously. Now we want to use the exit policy summary from
* that descriptor. If everybody plays nice all the voters who
@@ -1308,6 +1717,45 @@ networkstatus_compute_consensus(smartlist_t *votes,
tor_free(measured_bws);
}
+ if (consensus_method >= MIN_METHOD_FOR_FOOTER) {
+ /* Starting with consensus method 9, we clearly mark the directory
+ * footer region */
+ smartlist_add(chunks, tor_strdup("directory-footer\n"));
+ }
+
+ if (consensus_method >= MIN_METHOD_FOR_BW_WEIGHTS) {
+ int64_t weight_scale = BW_WEIGHT_SCALE;
+ char *bw_weight_param = NULL;
+
+ // Parse params, extract BW_WEIGHT_SCALE if present
+ // DO NOT use consensus_param_bw_weight_scale() in this code!
+ // The consensus is not formed yet!
+ if (strcmpstart(params, "bwweightscale=") == 0)
+ bw_weight_param = params;
+ else
+ bw_weight_param = strstr(params, " bwweightscale=");
+
+ if (bw_weight_param) {
+ int ok=0;
+ char *eq = strchr(bw_weight_param, '=');
+ if (eq) {
+ weight_scale = tor_parse_long(eq+1, 10, INT32_MIN, INT32_MAX, &ok,
+ NULL);
+ if (!ok) {
+ log_warn(LD_DIR, "Bad element '%s' in bw weight param",
+ escaped(bw_weight_param));
+ weight_scale = BW_WEIGHT_SCALE;
+ }
+ } else {
+ log_warn(LD_DIR, "Bad element '%s' in bw weight param",
+ escaped(bw_weight_param));
+ weight_scale = BW_WEIGHT_SCALE;
+ }
+ }
+
+ networkstatus_compute_bw_weights_v9(chunks, G, M, E, D, T, weight_scale);
+ }
+
/* Add a signature. */
{
char digest[DIGEST256_LEN];
@@ -1382,11 +1830,15 @@ networkstatus_compute_consensus(smartlist_t *votes,
networkstatus_t *c;
if (!(c = networkstatus_parse_vote_from_string(result, NULL,
NS_TYPE_CONSENSUS))) {
- log_err(LD_BUG,"Generated a networkstatus consensus we couldn't "
+ log_err(LD_BUG, "Generated a networkstatus consensus we couldn't "
"parse.");
tor_free(result);
return NULL;
}
+ // Verify balancing parameters
+ if (consensus_method >= MIN_METHOD_FOR_BW_WEIGHTS) {
+ networkstatus_verify_bw_weights(c);
+ }
networkstatus_vote_free(c);
}
diff --git a/src/or/networkstatus.c b/src/or/networkstatus.c
index a507f1be2..9023bc620 100644
--- a/src/or/networkstatus.c
+++ b/src/or/networkstatus.c
@@ -1264,7 +1264,6 @@ update_consensus_networkstatus_fetch_time(time_t now)
time_to_download_next_consensus = now;
log_info(LD_DIR, "No live consensus; we should fetch one immediately.");
}
-
}
/** Return 1 if there's a reason we shouldn't try any directory
@@ -2038,6 +2037,25 @@ networkstatus_dump_bridge_status_to_file(time_t now)
tor_free(status);
}
+int32_t
+get_net_param_from_list(smartlist_t *net_params, const char *param_name,
+ int default_val)
+{
+ size_t name_len = strlen(param_name);
+
+ SMARTLIST_FOREACH_BEGIN(net_params, const char *, p) {
+ if (!strcmpstart(p, param_name) && p[name_len] == '=') {
+ int ok=0;
+ long v = tor_parse_long(p+name_len+1, 10, INT32_MIN,
+ INT32_MAX, &ok, NULL);
+ if (ok)
+ return (int32_t) v;
+ }
+ } SMARTLIST_FOREACH_END(p);
+
+ return default_val;
+}
+
/** Return the value of a integer parameter from the networkstatus <b>ns</b>
* whose name is <b>param_name</b>. If <b>ns</b> is NULL, try loading the
* latest consensus ourselves. Return <b>default_val</b> if no latest
@@ -2046,27 +2064,30 @@ int32_t
networkstatus_get_param(networkstatus_t *ns, const char *param_name,
int32_t default_val)
{
- size_t name_len;
-
if (!ns) /* if they pass in null, go find it ourselves */
ns = networkstatus_get_latest_consensus();
if (!ns || !ns->net_params)
return default_val;
- name_len = strlen(param_name);
+ return get_net_param_from_list(ns->net_params, param_name, default_val);
+}
- SMARTLIST_FOREACH_BEGIN(ns->net_params, const char *, p) {
- if (!strcmpstart(p, param_name) && p[name_len] == '=') {
- int ok=0;
- long v = tor_parse_long(p+name_len+1, 10, INT32_MIN,
- INT32_MAX, &ok, NULL);
- if (ok)
- return (int32_t) v;
- }
- } SMARTLIST_FOREACH_END(p);
+/** Return the value of a integer bw weight parameter from the networkstatus
+ * <b>ns</b> whose name is <b>weight_name</b>. If <b>ns</b> is NULL, try
+ * loading the latest consensus ourselves. Return <b>default_val</b> if no
+ * latest consensus, or if it has no parameter called <b>param_name</b>. */
+int32_t
+networkstatus_get_bw_weight(networkstatus_t *ns, const char *weight_name,
+ int32_t default_val)
+{
+ if (!ns) /* if they pass in null, go find it ourselves */
+ ns = networkstatus_get_latest_consensus();
- return default_val;
+ if (!ns || !ns->weight_params)
+ return default_val;
+
+ return get_net_param_from_list(ns->weight_params, weight_name, default_val);
}
/** Return the name of the consensus flavor <b>flav</b> as used to identify
diff --git a/src/or/or.h b/src/or/or.h
index 434de7819..428195cb2 100644
--- a/src/or/or.h
+++ b/src/or/or.h
@@ -1771,6 +1771,10 @@ typedef struct networkstatus_t {
* consensus, sorted by key. */
smartlist_t *net_params;
+ /** List of key=value strings for the bw weight parameters in the
+ * consensus. */
+ smartlist_t *weight_params;
+
/** List of networkstatus_voter_info_t. For a vote, only one element
* is included. For a consensus, one element is included for every voter
* whose vote contributed to the consensus. */
@@ -3950,6 +3954,9 @@ int dirserv_read_measured_bandwidths(const char *from_file,
/** Smallest allowable voting interval. */
#define MIN_VOTE_INTERVAL 300
+/** Precision multiplier for the Bw weights */
+#define BW_WEIGHT_SCALE 10000
+
void dirvote_free_all(void);
/* vote manipulation */
@@ -4345,10 +4352,14 @@ void signed_descs_update_status_from_consensus_networkstatus(
char *networkstatus_getinfo_helper_single(routerstatus_t *rs);
char *networkstatus_getinfo_by_purpose(const char *purpose_string, time_t now);
void networkstatus_dump_bridge_status_to_file(time_t now);
+int32_t get_net_param_from_list(smartlist_t *net_params, const char *name,
+ int default_val);
int32_t networkstatus_get_param(networkstatus_t *ns, const char *param_name,
int32_t default_val);
int getinfo_helper_networkstatus(control_connection_t *conn,
const char *question, char **answer);
+int32_t networkstatus_get_bw_weight(networkstatus_t *ns, const char *weight,
+ int32_t default_val);
const char *networkstatus_get_flavor_name(consensus_flavor_t flav);
int networkstatus_parse_flavor_name(const char *flavname);
void document_signature_free(document_signature_t *sig);
@@ -4947,11 +4958,13 @@ uint32_t router_get_advertised_bandwidth_capped(routerinfo_t *router);
/** Possible ways to weight routers when choosing one randomly. See
* routerlist_sl_choose_by_bandwidth() for more information.*/
typedef enum {
- NO_WEIGHTING, WEIGHT_FOR_EXIT, WEIGHT_FOR_GUARD
+ NO_WEIGHTING, WEIGHT_FOR_EXIT, WEIGHT_FOR_MID, WEIGHT_FOR_GUARD,
+ WEIGHT_FOR_DIR
} bandwidth_weight_rule_t;
routerinfo_t *routerlist_sl_choose_by_bandwidth(smartlist_t *sl,
bandwidth_weight_rule_t rule);
-routerstatus_t *routerstatus_sl_choose_by_bandwidth(smartlist_t *sl);
+routerstatus_t *routerstatus_sl_choose_by_bandwidth(smartlist_t *sl,
+ bandwidth_weight_rule_t rule);
/** Flags to be passed to control router_choose_random_node() to indicate what
* kind of nodes to pick according to what algorithm. */
@@ -5177,6 +5190,7 @@ 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);
+int networkstatus_verify_bw_weights(networkstatus_t *ns);
networkstatus_t *networkstatus_parse_vote_from_string(const char *s,
const char **eos_out,
networkstatus_type_t ns_type);
diff --git a/src/or/rephist.c b/src/or/rephist.c
index e606db3b7..8729a1208 100644
--- a/src/or/rephist.c
+++ b/src/or/rephist.c
@@ -1909,8 +1909,8 @@ rep_hist_get_predicted_internal(time_t now, int *need_uptime,
return 0; /* too long ago */
if (predicted_internal_uptime_time + PREDICTED_CIRCS_RELEVANCE_TIME >= now)
*need_uptime = 1;
- if (predicted_internal_capacity_time + PREDICTED_CIRCS_RELEVANCE_TIME >= now)
- *need_capacity = 1;
+ // Always predict that we need capacity.
+ *need_capacity = 1;
return 1;
}
diff --git a/src/or/routerlist.c b/src/or/routerlist.c
index 1b9df5603..80229f214 100644
--- a/src/or/routerlist.c
+++ b/src/or/routerlist.c
@@ -1096,9 +1096,10 @@ router_pick_directory_server_impl(authority_type_t type, int flags)
} SMARTLIST_FOREACH_END(status);
if (smartlist_len(tunnel)) {
- result = routerstatus_sl_choose_by_bandwidth(tunnel);
+ result = routerstatus_sl_choose_by_bandwidth(tunnel, WEIGHT_FOR_DIR);
} else if (smartlist_len(overloaded_tunnel)) {
- result = routerstatus_sl_choose_by_bandwidth(overloaded_tunnel);
+ result = routerstatus_sl_choose_by_bandwidth(overloaded_tunnel,
+ WEIGHT_FOR_DIR);
} else if (smartlist_len(trusted_tunnel)) {
/* FFFF We don't distinguish between trusteds and overloaded trusteds
* yet. Maybe one day we should. */
@@ -1106,9 +1107,10 @@ router_pick_directory_server_impl(authority_type_t type, int flags)
* is a feature, but it could easily be a bug. -RD */
result = smartlist_choose(trusted_tunnel);
} else if (smartlist_len(direct)) {
- result = routerstatus_sl_choose_by_bandwidth(direct);
+ result = routerstatus_sl_choose_by_bandwidth(direct, WEIGHT_FOR_DIR);
} else if (smartlist_len(overloaded_direct)) {
- result = routerstatus_sl_choose_by_bandwidth(overloaded_direct);
+ result = routerstatus_sl_choose_by_bandwidth(overloaded_direct,
+ WEIGHT_FOR_DIR);
} else {
result = smartlist_choose(trusted_direct);
}
@@ -1538,6 +1540,188 @@ kb_to_bytes(uint32_t bw)
/** Helper function:
* choose a random element of smartlist <b>sl</b>, weighted by
+ * the advertised bandwidth of each element using the consensus
+ * bandwidth weights.
+ *
+ * If <b>statuses</b> is zero, then <b>sl</b> is a list of
+ * routerinfo_t's. Otherwise it's a list of routerstatus_t's.
+ *
+ * If <b>rule</b>==WEIGHT_FOR_EXIT. we're picking an exit node: consider all
+ * nodes' bandwidth equally regardless of their Exit status, since there may
+ * be some in the list because they exit to obscure ports. If
+ * <b>rule</b>==NO_WEIGHTING, we're picking a non-exit node: weight
+ * exit-node's bandwidth less depending on the smallness of the fraction of
+ * Exit-to-total bandwidth. If <b>rule</b>==WEIGHT_FOR_GUARD, we're picking a
+ * guard node: consider all guard's bandwidth equally. Otherwise, weight
+ * guards proportionally less.
+ */
+static void *
+smartlist_choose_by_bandwidth_weights(smartlist_t *sl,
+ bandwidth_weight_rule_t rule,
+ int statuses)
+{
+ int64_t weight_scale;
+ int64_t rand_bw;
+ double Wg = -1, Wm = -1, We = -1, Wd = -1;
+ double Wgb = -1, Wmb = -1, Web = -1, Wdb = -1;
+ double weighted_bw = 0;
+ double *bandwidths;
+ double tmp = 0;
+ unsigned int i;
+
+ /* Can't choose exit and guard at same time */
+ tor_assert(rule == NO_WEIGHTING ||
+ rule == WEIGHT_FOR_EXIT ||
+ rule == WEIGHT_FOR_GUARD ||
+ rule == WEIGHT_FOR_MID ||
+ rule == WEIGHT_FOR_DIR);
+
+ weight_scale = networkstatus_get_param(NULL, "bwweightscale",
+ BW_WEIGHT_SCALE);
+
+ if (rule == WEIGHT_FOR_GUARD) {
+ Wg = networkstatus_get_bw_weight(NULL, "Wgg", -1);
+ Wm = networkstatus_get_bw_weight(NULL, "Wgm", -1); /* Bridges */
+ We = 0;
+ Wd = networkstatus_get_bw_weight(NULL, "Wgd", -1);
+
+ Wgb = networkstatus_get_bw_weight(NULL, "Wgb", -1);
+ Wmb = networkstatus_get_bw_weight(NULL, "Wmb", -1);
+ Web = networkstatus_get_bw_weight(NULL, "Web", -1);
+ Wdb = networkstatus_get_bw_weight(NULL, "Wdb", -1);
+ } else if (rule == WEIGHT_FOR_MID) {
+ Wg = networkstatus_get_bw_weight(NULL, "Wmg", -1);
+ Wm = networkstatus_get_bw_weight(NULL, "Wmm", -1);
+ We = networkstatus_get_bw_weight(NULL, "Wme", -1);
+ Wd = networkstatus_get_bw_weight(NULL, "Wmd", -1);
+
+ Wgb = networkstatus_get_bw_weight(NULL, "Wgb", -1);
+ Wmb = networkstatus_get_bw_weight(NULL, "Wmb", -1);
+ Web = networkstatus_get_bw_weight(NULL, "Web", -1);
+ Wdb = networkstatus_get_bw_weight(NULL, "Wdb", -1);
+ } else if (rule == WEIGHT_FOR_EXIT) {
+ // Guards CAN be exits if they have weird exit policies
+ // They are d then I guess...
+ We = networkstatus_get_bw_weight(NULL, "Wee", -1);
+ Wm = networkstatus_get_bw_weight(NULL, "Wem", -1); /* Odd exit policies */
+ Wd = networkstatus_get_bw_weight(NULL, "Wed", -1);
+ Wg = networkstatus_get_bw_weight(NULL, "Weg", -1); /* Odd exit policies */
+
+ Wgb = networkstatus_get_bw_weight(NULL, "Wgb", -1);
+ Wmb = networkstatus_get_bw_weight(NULL, "Wmb", -1);
+ Web = networkstatus_get_bw_weight(NULL, "Web", -1);
+ Wdb = networkstatus_get_bw_weight(NULL, "Wdb", -1);
+ } else if (rule == WEIGHT_FOR_DIR) {
+ We = networkstatus_get_bw_weight(NULL, "Wbe", -1);
+ Wm = networkstatus_get_bw_weight(NULL, "Wbm", -1);
+ Wd = networkstatus_get_bw_weight(NULL, "Wbd", -1);
+ Wg = networkstatus_get_bw_weight(NULL, "Wbg", -1);
+
+ Wgb = Wmb = Web = Wdb = weight_scale;
+ } else if (rule == NO_WEIGHTING) {
+ Wg = Wm = We = Wd = weight_scale;
+ Wgb = Wmb = Web = Wdb = weight_scale;
+ }
+
+ if (Wg < 0 || Wm < 0 || We < 0 || Wd < 0 || Wgb < 0 || Wmb < 0 || Wdb < 0
+ || Web < 0) {
+ log_debug(LD_CIRC,
+ "Got negative bandwidth weights. Defaulting to old selection"
+ " algorithm.");
+ return NULL; // Use old algorithm.
+ }
+
+ Wg /= weight_scale;
+ Wm /= weight_scale;
+ We /= weight_scale;
+ Wd /= weight_scale;
+
+ Wgb /= weight_scale;
+ Wmb /= weight_scale;
+ Web /= weight_scale;
+ Wdb /= weight_scale;
+
+ bandwidths = tor_malloc_zero(sizeof(double)*smartlist_len(sl));
+
+ // Cycle through smartlist and total the bandwidth.
+ for (i = 0; i < (unsigned)smartlist_len(sl); ++i) {
+ int is_exit = 0, is_guard = 0, is_dir = 0, this_bw = 0;
+ double weight = 1;
+ if (statuses) {
+ routerstatus_t *status = smartlist_get(sl, i);
+ is_exit = status->is_exit;
+ is_guard = status->is_possible_guard;
+ is_dir = (status->dir_port != 0);
+ if (!status->has_bandwidth) {
+ tor_free(bandwidths);
+ /* This should never happen, unless all the authorites downgrade
+ * to 0.2.0 or rogue routerstatuses get inserted into our consensus. */
+ log_warn(LD_BUG,
+ "Consensus is not listing bandwidths. Defaulting back to "
+ "old router selection algorithm.");
+ return NULL;
+ }
+ this_bw = kb_to_bytes(status->bandwidth);
+ } else {
+ routerstatus_t *rs;
+ routerinfo_t *router = smartlist_get(sl, i);
+ rs = router_get_consensus_status_by_id(
+ router->cache_info.identity_digest);
+ is_exit = router->is_exit;
+ is_guard = router->is_possible_guard;
+ is_dir = (router->dir_port != 0);
+ if (rs && rs->has_bandwidth) {
+ this_bw = kb_to_bytes(rs->bandwidth);
+ } else { /* bridge or other descriptor not in our consensus */
+ this_bw = router_get_advertised_bandwidth_capped(router);
+ }
+ }
+ if (is_guard && is_exit) {
+ weight = (is_dir ? Wdb*Wd : Wd);
+ } else if (is_guard) {
+ weight = (is_dir ? Wgb*Wg : Wg);
+ } else if (is_exit) {
+ weight = (is_dir ? Web*We : We);
+ } else { // middle
+ weight = (is_dir ? Wmb*Wm : Wm);
+ }
+
+ bandwidths[i] = weight*this_bw;
+ weighted_bw += weight*this_bw;
+ }
+
+ log_debug(LD_CIRC, "Choosing node for rule %d based on weights "
+ "Wg=%lf Wm=%lf We=%lf Wd=%lf with total bw %lf", rule,
+ Wg, Wm, We, Wd, weighted_bw);
+
+ rand_bw = crypto_rand_uint64(DBL_TO_U64(weighted_bw));
+ rand_bw++; /* crypto_rand_uint64() counts from 0, and we need to count
+ * from 1 below. See bug 1203 for details. */
+
+ /* Last, count through sl until we get to the element we picked */
+ tmp = 0.0;
+ for (i=0; i < (unsigned)smartlist_len(sl); i++) {
+ tmp += bandwidths[i];
+ if (tmp >= rand_bw)
+ break;
+ }
+
+ if (i == (unsigned)smartlist_len(sl)) {
+ /* This was once possible due to round-off error, but shouldn't be able
+ * to occur any longer. */
+ tor_fragile_assert();
+ --i;
+ log_warn(LD_BUG, "Round-off error in computing bandwidth had an effect on "
+ " which router we chose. Please tell the developers. "
+ "%lf " U64_FORMAT " %lf", tmp, U64_PRINTF_ARG(rand_bw),
+ weighted_bw);
+ }
+ tor_free(bandwidths);
+ return smartlist_get(sl, i);
+}
+
+/** Helper function:
+ * choose a random element of smartlist <b>sl</b>, weighted by
* the advertised bandwidth of each element.
*
* If <b>statuses</b> is zero, then <b>sl</b> is a list of
@@ -1572,6 +1756,12 @@ smartlist_choose_by_bandwidth(smartlist_t *sl, bandwidth_weight_rule_t rule,
bitarray_t *guard_bits;
int me_idx = -1;
+ // This function does not support WEIGHT_FOR_DIR
+ // or WEIGHT_FOR_MID
+ if (rule == WEIGHT_FOR_DIR || rule == WEIGHT_FOR_MID) {
+ rule = NO_WEIGHTING;
+ }
+
/* Can't choose exit and guard at same time */
tor_assert(rule == NO_WEIGHTING ||
rule == WEIGHT_FOR_EXIT ||
@@ -1797,17 +1987,28 @@ routerinfo_t *
routerlist_sl_choose_by_bandwidth(smartlist_t *sl,
bandwidth_weight_rule_t rule)
{
- return smartlist_choose_by_bandwidth(sl, rule, 0);
+ routerinfo_t *ret;
+ if ((ret = smartlist_choose_by_bandwidth_weights(sl, rule, 0))) {
+ return ret;
+ } else {
+ return smartlist_choose_by_bandwidth(sl, rule, 0);
+ }
}
/** Choose a random element of status list <b>sl</b>, weighted by
* the advertised bandwidth of each status.
*/
routerstatus_t *
-routerstatus_sl_choose_by_bandwidth(smartlist_t *sl)
+routerstatus_sl_choose_by_bandwidth(smartlist_t *sl,
+ bandwidth_weight_rule_t rule)
{
/* We are choosing neither exit nor guard here. Weight accordingly. */
- return smartlist_choose_by_bandwidth(sl, NO_WEIGHTING, 1);
+ routerstatus_t *ret;
+ if ((ret = smartlist_choose_by_bandwidth_weights(sl, rule, 1))) {
+ return ret;
+ } else {
+ return smartlist_choose_by_bandwidth(sl, rule, 1);
+ }
}
/** Return a random running router from the routerlist. Never
@@ -1843,7 +2044,7 @@ router_choose_random_node(smartlist_t *excludedsmartlist,
tor_assert(!(weight_for_exit && need_guard));
rule = weight_for_exit ? WEIGHT_FOR_EXIT :
- (need_guard ? WEIGHT_FOR_GUARD : NO_WEIGHTING);
+ (need_guard ? WEIGHT_FOR_GUARD : WEIGHT_FOR_MID);
/* Exclude relays that allow single hop exit circuits, if the user
* wants to (such relays might be risky) */
@@ -1869,10 +2070,8 @@ router_choose_random_node(smartlist_t *excludedsmartlist,
if (excludedset)
routerset_subtract_routers(sl,excludedset);
- if (need_capacity || need_guard)
- choice = routerlist_sl_choose_by_bandwidth(sl, rule);
- else
- choice = smartlist_choose(sl);
+ // Always weight by bandwidth
+ choice = routerlist_sl_choose_by_bandwidth(sl, rule);
smartlist_free(sl);
if (!choice && (need_uptime || need_capacity || need_guard)) {
diff --git a/src/or/routerparse.c b/src/or/routerparse.c
index f4af7cd5e..082bf2ef0 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
};
@@ -1866,22 +1870,30 @@ authority_cert_parse_from_string(const char *s, const char **end_of_string)
/** Helper: given a string <b>s</b>, return the start of the next router-status
* object (starting with "r " at the start of a line). If none is found,
- * return the start of the next directory signature. If none is found, return
- * the end of the string. */
+ * return the start of the directory footer, or the next directory signature.
+ * If none is found, return the end of the string. */
static INLINE const char *
find_start_of_next_routerstatus(const char *s)
{
const char *eos = strstr(s, "\nr ");
if (eos) {
- const char *eos2 = tor_memstr(s, eos-s, "\ndirectory-signature");
+ const char *eos2 = tor_memstr(s, eos-s, "\ndirectory-footer\n");
+ if (eos2) eos2 += strlen("\ndirectory-footer");
+ else eos2 = tor_memstr(s, eos-s, "\ndirectory-signature");
+ /* Technically we are returning either the start of the next
+ * routerstatus AFTER the \n, or the start of the next consensus
+ * line AT the \n. This seems asymmetric, but leaving it that way
+ * for now for stability. */
if (eos2 && eos2 < eos)
return eos2;
else
return eos+1;
} else {
+ if ((eos = strstr(s, "\ndirectory-footer\n")))
+ return eos+strlen("\ndirectory-footer\n");
if ((eos = strstr(s, "\ndirectory-signature")))
return eos+1;
- return s + strlen(s);
+ return s + strlen(s);
}
}
@@ -2327,6 +2339,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 +3041,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;
diff --git a/src/test/test.c b/src/test/test.c
index 760558b65..c8e4441c7 100644
--- a/src/test/test.c
+++ b/src/test/test.c
@@ -607,7 +607,6 @@ test_circuit_timeout(void)
if (circuit_build_times_add_timeout(&final, 1, approx_time()-1))
final.have_computed_timeout = 1;
-
}
done:
generated by cgit v1.2.3 (git 2.45.0) at 2024-11-26 17:52:05 +0000