September 2012 - tor-commits - lists.torproject.org

[tor/master] hot: we fixed incancations to be intancations.
by arma＠torproject.org 12 Sep '12

12 Sep '12

commit 5977da6c60bcde2dee97e443984da3e9a5808bb9 Author: Roger Dingledine <arma(a)torproject.org> Date: Wed Sep 12 02:51:33 2012 -0400 hot: we fixed incancations to be intancations. --- src/common/util.c | 6 +++--- 1 files changed, 3 insertions(+), 3 deletions(-) diff --git a/src/common/util.c b/src/common/util.c index e79e73a..84b3150 100644 --- a/src/common/util.c +++ b/src/common/util.c @@ -332,9 +332,9 @@ tor_mathlog(double d) return log(d); } -/** Return the long integer closest to d. We define this wrapper here so - * that not all users of math.h need to use the right intancations to get - * the c99 functions. */ +/** Return the long integer closest to d. We define this wrapper + * here so that not all users of math.h need to use the right incantations + * to get the c99 functions. */ long tor_lround(double d) {

1 0

[tor/master] Use a smarter fix for bug 1203.
by nickm＠torproject.org 11 Sep '12

11 Sep '12

commit 50aecc68ca33f53f7de086990d5b1856c4d40ab8 Author: Nick Mathewson <nickm(a)torproject.org> Date: Thu Aug 9 12:41:28 2012 -0400 Use a smarter fix for bug 1203. Previously, we had incremented rand_bw so that when we later tested "tmp >= rand_bw", we wouldn't have an off-by-one error. But instead, it makes more sense to leave rand_bw alone and test "tmp > rand_bw". Note that this is still safe. To take the example from the bug1203 writeup: Suppose that we have 3 nodes with bandwidth 1. So the bandwidth array is { 1, 1, 1 }, and the total bandwidth is 3. We choose rand_bw == 0, 1, or 2. With the first iteration of the loop, tmp is now 1; with the second, tmp is 2; with the third, tmp is 3. Now that our check is tmp > rand_bw, we will set i in the first iteration of the loop iff rand_bw == 0; in the second iteration of the loop iff rand_bw == 1, and in the third iff rand_bw == 2. That's what we want. Incidentally, this change makes the bug 6538 fix more ironclad: once rand_bw is set to UINT64_MAX, tmp > rand_bw is obviously false regardless of the value of tmp. --- src/or/routerlist.c | 8 ++------ 1 files changed, 2 insertions(+), 6 deletions(-) diff --git a/src/or/routerlist.c b/src/or/routerlist.c index 75cb3f2..67ad2df 100644 --- a/src/or/routerlist.c +++ b/src/or/routerlist.c @@ -1875,15 +1875,13 @@ smartlist_choose_node_by_bandwidth_weights(smartlist_t *sl, } rand_bw = crypto_rand_uint64(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 */ i_chosen = (unsigned)smartlist_len(sl); tmp = 0; for (i=0; i < (unsigned)smartlist_len(sl); i++) { tmp += bandwidths[i]; - if (tmp >= rand_bw) { + if (tmp > rand_bw) { i_chosen = i; rand_bw = UINT64_MAX; } @@ -2118,8 +2116,6 @@ smartlist_choose_node_by_bandwidth(smartlist_t *sl, /* Almost done: choose a random value from the bandwidth weights. */ rand_bw = crypto_rand_uint64(total_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; @@ -2138,7 +2134,7 @@ smartlist_choose_node_by_bandwidth(smartlist_t *sl, else tmp += bandwidths[i]; - if (tmp >= rand_bw) { + if (tmp > rand_bw) { i_chosen = i; rand_bw = UINT64_MAX; }

1 0

[tor/master] Remove remaining timing-dependency in choosing nodes by bandwidth
by nickm＠torproject.org 11 Sep '12

11 Sep '12

commit 640a51684ce5a6cdae5c5f92cd2f932922380c00 Author: Nick Mathewson <nickm(a)torproject.org> Date: Thu Aug 9 12:37:40 2012 -0400 Remove remaining timing-dependency in choosing nodes by bandwidth The old approach, because of its "tmp >= rand_bw && !i_has_been_chosen" check, would run through the second part of the loop slightly slower than the first part. Now, we remove i_has_been_chosen, and instead set rand_bw = UINT64_MAX, so that every instance of the loop will do exactly the same amount of work regardless of the initial value of rand_bw. Fix for bug 6538. --- changes/bug6538 | 8 ++++++++ src/or/routerlist.c | 12 ++++-------- 2 files changed, 12 insertions(+), 8 deletions(-) diff --git a/changes/bug6538 b/changes/bug6538 index 1e882eb..fc9e583 100644 --- a/changes/bug6538 +++ b/changes/bug6538 @@ -2,3 +2,11 @@ - Switch weighted node selection rule from using a list of doubles to using a list of int64_t. This should make the process slightly easier to debug and maintain. Needed for fix for bug 6538. + + o Security features: + - Switch to a completely time-invariant approach for picking nodes + weighted by bandwidth. Our old approach would run through the + part of the loop after it had made its choice slightly slower + than it ran through the part of the loop before it had made its + choice. Fix for bug 6538. + diff --git a/src/or/routerlist.c b/src/or/routerlist.c index 382d457..75cb3f2 100644 --- a/src/or/routerlist.c +++ b/src/or/routerlist.c @@ -1710,7 +1710,6 @@ smartlist_choose_node_by_bandwidth_weights(smartlist_t *sl, uint64_t tmp; unsigned int i; unsigned int i_chosen; - unsigned int i_has_been_chosen; int have_unknown = 0; /* true iff sl contains element not in consensus. */ /* Can't choose exit and guard at same time */ @@ -1881,13 +1880,12 @@ smartlist_choose_node_by_bandwidth_weights(smartlist_t *sl, /* Last, count through sl until we get to the element we picked */ i_chosen = (unsigned)smartlist_len(sl); - i_has_been_chosen = 0; tmp = 0; for (i=0; i < (unsigned)smartlist_len(sl); i++) { tmp += bandwidths[i]; - if (tmp >= rand_bw && !i_has_been_chosen) { + if (tmp >= rand_bw) { i_chosen = i; - i_has_been_chosen = 1; + rand_bw = UINT64_MAX; } } i = i_chosen; @@ -1926,7 +1924,6 @@ smartlist_choose_node_by_bandwidth(smartlist_t *sl, { unsigned int i; unsigned int i_chosen; - unsigned int i_has_been_chosen; int32_t *bandwidths; int is_exit; int is_guard; @@ -2127,7 +2124,6 @@ smartlist_choose_node_by_bandwidth(smartlist_t *sl, /* Last, count through sl until we get to the element we picked */ tmp = 0; i_chosen = (unsigned)smartlist_len(sl); - i_has_been_chosen = 0; for (i=0; i < (unsigned)smartlist_len(sl); i++) { is_exit = bitarray_is_set(exit_bits, i); is_guard = bitarray_is_set(guard_bits, i); @@ -2142,9 +2138,9 @@ smartlist_choose_node_by_bandwidth(smartlist_t *sl, else tmp += bandwidths[i]; - if (tmp >= rand_bw && !i_has_been_chosen) { + if (tmp >= rand_bw) { i_chosen = i; - i_has_been_chosen = 1; + rand_bw = UINT64_MAX; } } i = i_chosen;

1 0

[tor/master] Change smartlist_choose_node_by_bandwidth to avoid double
by nickm＠torproject.org 11 Sep '12

11 Sep '12

commit e106812a778f53760c819ab20a214ac3222b3b15 Author: Nick Mathewson <nickm(a)torproject.org> Date: Thu Aug 9 12:21:37 2012 -0400 Change smartlist_choose_node_by_bandwidth to avoid double This should make our preferred solution to #6538 easier to implement, avoid a bunch of potential nastiness with excessive int-vs-double math, and generally make the code there a little less scary. "But wait!" you say. "Is it really safe to do this? Won't the results come out differently?" Yes, but not much. We now round every weighted bandwidth to the nearest byte before computing on it. This will make every node that had a fractional part of its weighted bandwidth before either slighty more likely or slightly less likely. Further, the rand_bw value was only ever set with integer precision, so it can't accurately sample routers with tiny fractional bandwidth values anyway. Finally, doing repeated double-vs-uint64 comparisons is just plain sad; it will involve an implicit cast to double, which is never a fun thing. --- changes/bug6538 | 4 ++++ configure.in | 1 + src/common/util.c | 15 +++++++++++++++ src/common/util.h | 1 + src/or/routerlist.c | 48 ++++++++++++++++++++++++++++-------------------- 5 files changed, 49 insertions(+), 20 deletions(-) diff --git a/changes/bug6538 b/changes/bug6538 new file mode 100644 index 0000000..1e882eb --- /dev/null +++ b/changes/bug6538 @@ -0,0 +1,4 @@ + o Minor bugfixes: + - Switch weighted node selection rule from using a list of doubles + to using a list of int64_t. This should make the process slightly + easier to debug and maintain. Needed for fix for bug 6538. diff --git a/configure.in b/configure.in index 1db7d08..f5f8eac 100644 --- a/configure.in +++ b/configure.in @@ -300,6 +300,7 @@ AC_CHECK_FUNCS( gmtime_r \ inet_aton \ ioctl \ + llround \ localtime_r \ lround \ memmem \ diff --git a/src/common/util.c b/src/common/util.c index a0dff2e..60222f4 100644 --- a/src/common/util.c +++ b/src/common/util.c @@ -378,6 +378,21 @@ tor_lround(double d) #endif } +/** Return the 64-bit integer closest to d. We define this wrapper here so + * that not all users of math.h need to use the right incancations to get the + * c99 functions. */ +int64_t +tor_llround(double d) +{ +#if defined(HAVE_LLROUND) + return (int64_t)llround(d); +#elif defined(HAVE_RINT) + return (int64_t)rint(d); +#else + return (int64_t)(d > 0 ? d + 0.5 : ceil(d - 0.5)); +#endif +} + /** Returns floor(log2(u64)). If u64 is 0, (incorrectly) returns 0. */ int tor_log2(uint64_t u64) diff --git a/src/common/util.h b/src/common/util.h index a2ab0cc..f700e9f 100644 --- a/src/common/util.h +++ b/src/common/util.h @@ -161,6 +161,7 @@ void tor_log_mallinfo(int severity); /* Math functions */ double tor_mathlog(double d) ATTR_CONST; long tor_lround(double d) ATTR_CONST; +int64_t tor_llround(double d) ATTR_CONST; int tor_log2(uint64_t u64) ATTR_CONST; uint64_t round_to_power_of_2(uint64_t u64); unsigned round_to_next_multiple_of(unsigned number, unsigned divisor); diff --git a/src/or/routerlist.c b/src/or/routerlist.c index 4979b93..382d457 100644 --- a/src/or/routerlist.c +++ b/src/or/routerlist.c @@ -1702,12 +1702,12 @@ smartlist_choose_node_by_bandwidth_weights(smartlist_t *sl, bandwidth_weight_rule_t rule) { int64_t weight_scale; - int64_t rand_bw; + uint64_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, unweighted_bw = 0; - double *bandwidths; - double tmp = 0; + uint64_t weighted_bw = 0, unweighted_bw = 0; + uint64_t *bandwidths; + uint64_t tmp; unsigned int i; unsigned int i_chosen; unsigned int i_has_been_chosen; @@ -1792,7 +1792,7 @@ smartlist_choose_node_by_bandwidth_weights(smartlist_t *sl, Web /= weight_scale; Wdb /= weight_scale; - bandwidths = tor_malloc_zero(sizeof(double)*smartlist_len(sl)); + bandwidths = tor_malloc_zero(sizeof(uint64_t)*smartlist_len(sl)); // Cycle through smartlist and total the bandwidth. SMARTLIST_FOREACH_BEGIN(sl, const node_t *, node) { @@ -1831,24 +1831,30 @@ smartlist_choose_node_by_bandwidth_weights(smartlist_t *sl, } else { // middle weight = (is_dir ? Wmb*Wm : Wm); } - - bandwidths[node_sl_idx] = weight*this_bw; - weighted_bw += weight*this_bw; + /* These should be impossible; but overflows here would be bad, so let's + * make sure. */ + if (this_bw < 0) + this_bw = 0; + if (weight < 0.0) + weight = 0.0; + + bandwidths[node_sl_idx] = tor_llround(weight*this_bw + 0.5); + weighted_bw += bandwidths[node_sl_idx]; unweighted_bw += this_bw; if (is_me) - sl_last_weighted_bw_of_me = weight*this_bw; + sl_last_weighted_bw_of_me = bandwidths[node_sl_idx]; } SMARTLIST_FOREACH_END(node); /* XXXX this is a kludge to expose these values. */ sl_last_total_weighted_bw = weighted_bw; log_debug(LD_CIRC, "Choosing node for rule %s based on weights " - "Wg=%f Wm=%f We=%f Wd=%f with total bw %f", + "Wg=%f Wm=%f We=%f Wd=%f with total bw "U64_FORMAT, bandwidth_weight_rule_to_string(rule), - Wg, Wm, We, Wd, weighted_bw); + Wg, Wm, We, Wd, U64_PRINTF_ARG(weighted_bw)); /* If there is no bandwidth, choose at random */ - if (DBL_TO_U64(weighted_bw) == 0) { + if (weighted_bw == 0) { /* Don't warn when using bridges/relays not in the consensus */ if (!have_unknown) { #define ZERO_BANDWIDTH_WARNING_INTERVAL (15) @@ -1858,24 +1864,25 @@ smartlist_choose_node_by_bandwidth_weights(smartlist_t *sl, if ((msg = rate_limit_log(&zero_bandwidth_warning_limit, approx_time()))) { log_warn(LD_CIRC, - "Weighted bandwidth is %f in node selection for rule %s " - "(unweighted was %f) %s", - weighted_bw, bandwidth_weight_rule_to_string(rule), - unweighted_bw, msg); + "Weighted bandwidth is "U64_FORMAT" in node selection for " + "rule %s (unweighted was "U64_FORMAT") %s", + U64_PRINTF_ARG(weighted_bw), + bandwidth_weight_rule_to_string(rule), + U64_PRINTF_ARG(unweighted_bw), msg); } } tor_free(bandwidths); return smartlist_choose(sl); } - rand_bw = crypto_rand_uint64(DBL_TO_U64(weighted_bw)); + rand_bw = crypto_rand_uint64(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 */ i_chosen = (unsigned)smartlist_len(sl); i_has_been_chosen = 0; - tmp = 0.0; + tmp = 0; for (i=0; i < (unsigned)smartlist_len(sl); i++) { tmp += bandwidths[i]; if (tmp >= rand_bw && !i_has_been_chosen) { @@ -1892,8 +1899,9 @@ smartlist_choose_node_by_bandwidth_weights(smartlist_t *sl, --i; log_warn(LD_BUG, "Round-off error in computing bandwidth had an effect on " " which router we chose. Please tell the developers. " - "%f " U64_FORMAT " %f", tmp, U64_PRINTF_ARG(rand_bw), - weighted_bw); + U64_FORMAT" "U64_FORMAT" "U64_FORMAT, + U64_PRINTF_ARG(tmp), U64_PRINTF_ARG(rand_bw), + U64_PRINTF_ARG(weighted_bw)); } tor_free(bandwidths); return smartlist_get(sl, i);

1 0

[tor/master] Refactor smartlist_choose_node_by_bandwidth to be less horrible.
by nickm＠torproject.org 11 Sep '12

11 Sep '12

commit 9bfb274abb9f9e5d445a75f0b67b433be823a730 Author: Nick Mathewson <nickm(a)torproject.org> Date: Thu Aug 9 12:59:04 2012 -0400 Refactor smartlist_choose_node_by_bandwidth to be less horrible. With this patch, I dump the old kludge of using magic negative numbers to indicate unknown bandwidths. I also compute each node's weighted bandwidth exactly once, rather than computing it once in a loop to compute the total weighted bandwidth and a second time in a loop to find which one we picked. --- src/or/routerlist.c | 69 ++++++++++++++++++++------------------------------- 1 files changed, 27 insertions(+), 42 deletions(-) diff --git a/src/or/routerlist.c b/src/or/routerlist.c index 67ad2df..801c496 100644 --- a/src/or/routerlist.c +++ b/src/or/routerlist.c @@ -1922,15 +1922,17 @@ smartlist_choose_node_by_bandwidth(smartlist_t *sl, { unsigned int i; unsigned int i_chosen; - int32_t *bandwidths; + uint64_t *bandwidths; int is_exit; int is_guard; + int is_fast; uint64_t total_nonexit_bw = 0, total_exit_bw = 0, total_bw = 0; uint64_t total_nonguard_bw = 0, total_guard_bw = 0; uint64_t rand_bw, tmp; double exit_weight; double guard_weight; int n_unknown = 0; + bitarray_t *fast_bits; bitarray_t *exit_bits; bitarray_t *guard_bits; int me_idx = -1; @@ -1954,10 +1956,9 @@ smartlist_choose_node_by_bandwidth(smartlist_t *sl, } /* First count the total bandwidth weight, and make a list - * of each value. <0 means "unknown; no routerinfo." We use the - * bits of negative values to remember whether the router was fast (-x)&1 - * and whether it was an exit (-x)&2 or guard (-x)&4. Yes, it's a hack. */ - bandwidths = tor_malloc(sizeof(int32_t)*smartlist_len(sl)); + * of each value. We use UINT64_MAX to indicate "unknown". */ + bandwidths = tor_malloc_zero(sizeof(uint64_t)*smartlist_len(sl)); + fast_bits = bitarray_init_zero(smartlist_len(sl)); exit_bits = bitarray_init_zero(smartlist_len(sl)); guard_bits = bitarray_init_zero(smartlist_len(sl)); @@ -1965,7 +1966,6 @@ smartlist_choose_node_by_bandwidth(smartlist_t *sl, SMARTLIST_FOREACH_BEGIN(sl, const node_t *, node) { /* first, learn what bandwidth we think i has */ int is_known = 1; - int32_t flags = 0; uint32_t this_bw = 0; i = node_sl_idx; @@ -1978,12 +1978,7 @@ smartlist_choose_node_by_bandwidth(smartlist_t *sl, if (node->rs->has_bandwidth) { this_bw = kb_to_bytes(node->rs->bandwidth); } else { /* guess */ - /* XXX024 once consensuses always list bandwidths, we can take - * this guessing business out. -RD */ is_known = 0; - flags = node->rs->is_fast ? 1 : 0; - flags |= is_exit ? 2 : 0; - flags |= is_guard ? 4 : 0; } } else if (node->ri) { /* Must be a bridge if we're willing to use it */ @@ -1994,12 +1989,11 @@ smartlist_choose_node_by_bandwidth(smartlist_t *sl, bitarray_set(exit_bits, i); if (is_guard) bitarray_set(guard_bits, i); + if (node->is_fast) + bitarray_set(fast_bits, i); + if (is_known) { - bandwidths[i] = (int32_t) this_bw; - /* Casting this_bw to int32_t is safe because both kb_to_bytes - and bridge_get_advertised_bandwidth_bounded limit it to below - INT32_MAX. */ - tor_assert(bandwidths[i] >= 0); + bandwidths[i] = this_bw; if (is_guard) total_guard_bw += this_bw; else @@ -2010,7 +2004,7 @@ smartlist_choose_node_by_bandwidth(smartlist_t *sl, total_nonexit_bw += this_bw; } else { ++n_unknown; - bandwidths[node_sl_idx] = -flags; + bandwidths[i] = UINT64_MAX; } } SMARTLIST_FOREACH_END(node); @@ -2028,12 +2022,12 @@ smartlist_choose_node_by_bandwidth(smartlist_t *sl, avg_slow = 20000; } for (i=0; i<(unsigned)smartlist_len(sl); ++i) { - int32_t bw = bandwidths[i]; - if (bw>=0) + if (bandwidths[i] != UINT64_MAX) continue; - is_exit = ((-bw)&2); - is_guard = ((-bw)&4); - bandwidths[i] = ((-bw)&1) ? avg_fast : avg_slow; + is_fast = bitarray_is_set(fast_bits, i); + is_exit = bitarray_is_set(exit_bits, i); + is_guard = bitarray_is_set(guard_bits, i); + bandwidths[i] = is_fast ? avg_fast : avg_slow; if (is_exit) total_exit_bw += bandwidths[i]; else @@ -2048,6 +2042,7 @@ smartlist_choose_node_by_bandwidth(smartlist_t *sl, /* If there's no bandwidth at all, pick at random. */ if (!(total_exit_bw+total_nonexit_bw)) { tor_free(bandwidths); + tor_free(fast_bits); tor_free(exit_bits); tor_free(guard_bits); return smartlist_choose(sl); @@ -2081,20 +2076,20 @@ smartlist_choose_node_by_bandwidth(smartlist_t *sl, total_bw = 0; sl_last_weighted_bw_of_me = 0; for (i=0; i < (unsigned)smartlist_len(sl); i++) { - uint64_t bw; + tor_assert(bandwidths[i] < UINT64_MAX); + is_exit = bitarray_is_set(exit_bits, i); is_guard = bitarray_is_set(guard_bits, i); if (is_exit && is_guard) - bw = ((uint64_t)(bandwidths[i] * exit_weight * guard_weight)); + bandwidths[i] = tor_llround(bandwidths[i] * exit_weight * guard_weight); else if (is_guard) - bw = ((uint64_t)(bandwidths[i] * guard_weight)); + bandwidths[i] = tor_llround(bandwidths[i] * guard_weight); else if (is_exit) - bw = ((uint64_t)(bandwidths[i] * exit_weight)); - else - bw = bandwidths[i]; - total_bw += bw; + bandwidths[i] = tor_llround(bandwidths[i] * exit_weight); + + total_bw += bandwidths[i]; if (i == (unsigned) me_idx) - sl_last_weighted_bw_of_me = bw; + sl_last_weighted_bw_of_me = bandwidths[i]; } } @@ -2121,18 +2116,7 @@ smartlist_choose_node_by_bandwidth(smartlist_t *sl, tmp = 0; i_chosen = (unsigned)smartlist_len(sl); for (i=0; i < (unsigned)smartlist_len(sl); i++) { - is_exit = bitarray_is_set(exit_bits, i); - is_guard = bitarray_is_set(guard_bits, i); - - /* Weights can be 0 if not counting guards/exits */ - if (is_exit && is_guard) - tmp += ((uint64_t)(bandwidths[i] * exit_weight * guard_weight)); - else if (is_guard) - tmp += ((uint64_t)(bandwidths[i] * guard_weight)); - else if (is_exit) - tmp += ((uint64_t)(bandwidths[i] * exit_weight)); - else - tmp += bandwidths[i]; + tmp += bandwidths[i]; if (tmp > rand_bw) { i_chosen = i; @@ -2151,6 +2135,7 @@ smartlist_choose_node_by_bandwidth(smartlist_t *sl, U64_PRINTF_ARG(rand_bw), U64_PRINTF_ARG(total_bw)); } tor_free(bandwidths); + tor_free(fast_bits); tor_free(exit_bits); tor_free(guard_bits); return smartlist_get(sl, i);

1 0

[tor/master] Refactor the core of choosing by weights into a function
by nickm＠torproject.org 11 Sep '12

11 Sep '12

commit 07df4dd52d3ab2eea2e8a8fc3222a5d297d077de Author: Nick Mathewson <nickm(a)torproject.org> Date: Thu Aug 9 13:47:42 2012 -0400 Refactor the core of choosing by weights into a function This eliminates duplicated code, and lets us test a hairy piece of functionality. --- changes/bug6538 | 4 + src/or/routerlist.c | 162 +++++++++++++++++++++------------------------------ src/or/routerlist.h | 5 ++ src/test/test.h | 4 + src/test/test_dir.c | 81 +++++++++++++++++++++++++ 5 files changed, 160 insertions(+), 96 deletions(-) diff --git a/changes/bug6538 b/changes/bug6538 index fc9e583..03c168b 100644 --- a/changes/bug6538 +++ b/changes/bug6538 @@ -10,3 +10,7 @@ than it ran through the part of the loop before it had made its choice. Fix for bug 6538. + o Code simplifications and refactoring: + - Move the core of our "choose a weighted element at random" logic + into its own function, and give it unit tests. Now the logic is + testable, and a little less fragile too. diff --git a/src/or/routerlist.c b/src/or/routerlist.c index 801c496..1c0aca8 100644 --- a/src/or/routerlist.c +++ b/src/or/routerlist.c @@ -11,6 +11,7 @@ * servers. **/ +#define ROUTERLIST_PRIVATE #include "or.h" #include "circuitbuild.h" #include "config.h" @@ -1652,6 +1653,53 @@ router_get_advertised_bandwidth_capped(const routerinfo_t *router) return result; } +/** Pick a random element of n_entries-element array entries, + * choosing each element with a probability proportional to its value, and + * return the index of that element. If all elements are 0, choose an index + * at random. If total_out is provided, set it to the sum of all + * elements in the array. Return -1 on error. + */ +/* private */ int +choose_array_element_by_weight(const uint64_t *entries, int n_entries, + uint64_t *total_out) +{ + int i, i_chosen=-1, n_chosen=0; + uint64_t total_so_far = 0; + uint64_t rand_val; + uint64_t total = 0; + + for (i = 0; i < n_entries; ++i) + total += entries[i]; + + if (total_out) + *total_out = total; + + if (n_entries < 1) + return -1; + + if (total == 0) + return crypto_rand_int(n_entries); + + rand_val = crypto_rand_uint64(total); + + for (i = 0; i < n_entries; ++i) { + total_so_far += entries[i]; + if (total_so_far > rand_val) { + i_chosen = i; + n_chosen++; + /* Set rand_val to UINT_MAX rather than stopping the loop. This way, + * the time we spend in the loop does not leak which element we chose. */ + rand_val = UINT64_MAX; + } + } + tor_assert(total_so_far == total); + tor_assert(n_chosen == 1); + tor_assert(i_chosen >= 0); + tor_assert(i_chosen < n_entries); + + return i_chosen; +} + /** When weighting bridges, enforce these values as lower and upper * bound for believable bandwidth, because there is no way for us * to verify a bridge's bandwidth currently. */ @@ -1702,15 +1750,10 @@ smartlist_choose_node_by_bandwidth_weights(smartlist_t *sl, bandwidth_weight_rule_t rule) { int64_t weight_scale; - uint64_t rand_bw; double Wg = -1, Wm = -1, We = -1, Wd = -1; double Wgb = -1, Wmb = -1, Web = -1, Wdb = -1; - uint64_t weighted_bw = 0, unweighted_bw = 0; + uint64_t weighted_bw = 0; uint64_t *bandwidths; - uint64_t tmp; - unsigned int i; - unsigned int i_chosen; - int have_unknown = 0; /* true iff sl contains element not in consensus. */ /* Can't choose exit and guard at same time */ tor_assert(rule == NO_WEIGHTING || @@ -1814,7 +1857,6 @@ smartlist_choose_node_by_bandwidth_weights(smartlist_t *sl, } else if (node->ri) { /* bridge or other descriptor not in our consensus */ this_bw = bridge_get_advertised_bandwidth_bounded(node->ri); - have_unknown = 1; } else { /* We can't use this one. */ continue; @@ -1838,69 +1880,22 @@ smartlist_choose_node_by_bandwidth_weights(smartlist_t *sl, weight = 0.0; bandwidths[node_sl_idx] = tor_llround(weight*this_bw + 0.5); - weighted_bw += bandwidths[node_sl_idx]; - unweighted_bw += this_bw; if (is_me) sl_last_weighted_bw_of_me = bandwidths[node_sl_idx]; } SMARTLIST_FOREACH_END(node); - /* XXXX this is a kludge to expose these values. */ - sl_last_total_weighted_bw = weighted_bw; - log_debug(LD_CIRC, "Choosing node for rule %s based on weights " "Wg=%f Wm=%f We=%f Wd=%f with total bw "U64_FORMAT, bandwidth_weight_rule_to_string(rule), Wg, Wm, We, Wd, U64_PRINTF_ARG(weighted_bw)); - /* If there is no bandwidth, choose at random */ - if (weighted_bw == 0) { - /* Don't warn when using bridges/relays not in the consensus */ - if (!have_unknown) { -#define ZERO_BANDWIDTH_WARNING_INTERVAL (15) - static ratelim_t zero_bandwidth_warning_limit = - RATELIM_INIT(ZERO_BANDWIDTH_WARNING_INTERVAL); - char *msg; - if ((msg = rate_limit_log(&zero_bandwidth_warning_limit, - approx_time()))) { - log_warn(LD_CIRC, - "Weighted bandwidth is "U64_FORMAT" in node selection for " - "rule %s (unweighted was "U64_FORMAT") %s", - U64_PRINTF_ARG(weighted_bw), - bandwidth_weight_rule_to_string(rule), - U64_PRINTF_ARG(unweighted_bw), msg); - } - } + { + int idx = choose_array_element_by_weight(bandwidths, + smartlist_len(sl), + &sl_last_total_weighted_bw); tor_free(bandwidths); - return smartlist_choose(sl); - } - - rand_bw = crypto_rand_uint64(weighted_bw); - - /* Last, count through sl until we get to the element we picked */ - i_chosen = (unsigned)smartlist_len(sl); - tmp = 0; - for (i=0; i < (unsigned)smartlist_len(sl); i++) { - tmp += bandwidths[i]; - if (tmp > rand_bw) { - i_chosen = i; - rand_bw = UINT64_MAX; - } - } - i = i_chosen; - - 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. " - U64_FORMAT" "U64_FORMAT" "U64_FORMAT, - U64_PRINTF_ARG(tmp), U64_PRINTF_ARG(rand_bw), - U64_PRINTF_ARG(weighted_bw)); + return idx < 0 ? NULL : smartlist_get(sl, idx); } - tor_free(bandwidths); - return smartlist_get(sl, i); } /** Helper function: @@ -1921,14 +1916,12 @@ smartlist_choose_node_by_bandwidth(smartlist_t *sl, bandwidth_weight_rule_t rule) { unsigned int i; - unsigned int i_chosen; uint64_t *bandwidths; int is_exit; int is_guard; int is_fast; - uint64_t total_nonexit_bw = 0, total_exit_bw = 0, total_bw = 0; + uint64_t total_nonexit_bw = 0, total_exit_bw = 0; uint64_t total_nonguard_bw = 0, total_guard_bw = 0; - uint64_t rand_bw, tmp; double exit_weight; double guard_weight; int n_unknown = 0; @@ -2073,7 +2066,6 @@ smartlist_choose_node_by_bandwidth(smartlist_t *sl, if (guard_weight <= 0.0) guard_weight = 0.0; - total_bw = 0; sl_last_weighted_bw_of_me = 0; for (i=0; i < (unsigned)smartlist_len(sl); i++) { tor_assert(bandwidths[i] < UINT64_MAX); @@ -2087,15 +2079,12 @@ smartlist_choose_node_by_bandwidth(smartlist_t *sl, else if (is_exit) bandwidths[i] = tor_llround(bandwidths[i] * exit_weight); - total_bw += bandwidths[i]; if (i == (unsigned) me_idx) sl_last_weighted_bw_of_me = bandwidths[i]; } } - /* XXXX this is a kludge to expose these values. */ - sl_last_total_weighted_bw = total_bw; - +#if 0 log_debug(LD_CIRC, "Total weighted bw = "U64_FORMAT ", exit bw = "U64_FORMAT ", nonexit bw = "U64_FORMAT", exit weight = %f " @@ -2108,37 +2097,18 @@ smartlist_choose_node_by_bandwidth(smartlist_t *sl, exit_weight, (int)(rule == WEIGHT_FOR_EXIT), U64_PRINTF_ARG(total_guard_bw), U64_PRINTF_ARG(total_nonguard_bw), guard_weight, (int)(rule == WEIGHT_FOR_GUARD)); +#endif - /* Almost done: choose a random value from the bandwidth weights. */ - rand_bw = crypto_rand_uint64(total_bw); - - /* Last, count through sl until we get to the element we picked */ - tmp = 0; - i_chosen = (unsigned)smartlist_len(sl); - for (i=0; i < (unsigned)smartlist_len(sl); i++) { - tmp += bandwidths[i]; - - if (tmp > rand_bw) { - i_chosen = i; - rand_bw = UINT64_MAX; - } + { + int idx = choose_array_element_by_weight(bandwidths, + smartlist_len(sl), + &sl_last_total_weighted_bw); + tor_free(bandwidths); + tor_free(fast_bits); + tor_free(exit_bits); + tor_free(guard_bits); + return idx < 0 ? NULL : smartlist_get(sl, idx); } - i = i_chosen; - 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. " - U64_FORMAT " " U64_FORMAT " " U64_FORMAT, U64_PRINTF_ARG(tmp), - U64_PRINTF_ARG(rand_bw), U64_PRINTF_ARG(total_bw)); - } - tor_free(bandwidths); - tor_free(fast_bits); - tor_free(exit_bits); - tor_free(guard_bits); - return smartlist_get(sl, i); } /** Choose a random element of status list sl, weighted by diff --git a/src/or/routerlist.h b/src/or/routerlist.h index 8dcc6eb..0b9b297 100644 --- a/src/or/routerlist.h +++ b/src/or/routerlist.h @@ -216,5 +216,10 @@ int hex_digest_nickname_decode(const char *hexdigest, char *nickname_qualifier_out, char *nickname_out); +#ifdef ROUTERLIST_PRIVATE +int choose_array_element_by_weight(const uint64_t *entries, int n_entries, + uint64_t *total_out); +#endif + #endif diff --git a/src/test/test.h b/src/test/test.h index 0b6e6c6..6dcb949 100644 --- a/src/test/test.h +++ b/src/test/test.h @@ -65,6 +65,10 @@ #define test_memeq_hex(expr1, hex) test_mem_op_hex(expr1, ==, hex) +#define tt_double_op(a,op,b) \ + tt_assert_test_type(a,b,#a" "#op" "#b,double,(val1_ op val2_),"%f", \ + TT_EXIT_TEST_FUNCTION) + const char *get_fname(const char *name); crypto_pk_t *pk_generate(int idx); diff --git a/src/test/test_dir.c b/src/test/test_dir.c index 83c6120..ed0c5a1 100644 --- a/src/test/test_dir.c +++ b/src/test/test_dir.c @@ -7,6 +7,7 @@ #define DIRSERV_PRIVATE #define DIRVOTE_PRIVATE #define ROUTER_PRIVATE +#define ROUTERLIST_PRIVATE #define HIBERNATE_PRIVATE #include "or.h" #include "directory.h" @@ -1381,6 +1382,85 @@ test_dir_v3_networkstatus(void) ns_detached_signatures_free(dsig2); } +static void +test_dir_random_weighted(void *testdata) +{ + int histogram[10]; + uint64_t vals[10] = {3,1,2,4,6,0,7,5,8,9}, total=0; + uint64_t zeros[5] = {0,0,0,0,0}; + int i, choice; + const int n = 50000; + double max_sq_error; + (void) testdata; + + /* Try a ten-element array with values from 0 through 10. The values are + * in a scrambled order to make sure we don't depend on order. */ + memset(histogram,0,sizeof(histogram)); + for (i=0; i<10; ++i) + total += vals[i]; + tt_int_op(total, ==, 45); + for (i=0; i<n; ++i) { + uint64_t t; + choice = choose_array_element_by_weight(vals, 10, &t); + tt_int_op(t, ==, total); + tt_int_op(choice, >=, 0); + tt_int_op(choice, <, 10); + histogram[choice]++; + } + + /* Now see if we chose things about frequently enough. */ + max_sq_error = 0; + for (i=0; i<10; ++i) { + int expected = (int)(n*vals[i]/total); + double frac_diff = 0, sq; + TT_BLATHER((" %d : %5d vs %5d\n", (int)vals[i], histogram[i], expected)); + if (expected) + frac_diff = (histogram[i] - expected) / ((double)expected); + else + tt_int_op(histogram[i], ==, 0); + + sq = frac_diff * frac_diff; + if (sq > max_sq_error) + max_sq_error = sq; + } + /* It should almost always be much much less than this. If you want to + * figure out the odds, please feel free. */ + tt_double_op(max_sq_error, <, .05); + + /* Now try a singleton; do we choose it? */ + for (i = 0; i < 100; ++i) { + choice = choose_array_element_by_weight(vals, 1, NULL); + tt_int_op(choice, ==, 0); + } + + /* Now try an array of zeros. We should choose randomly. */ + memset(histogram,0,sizeof(histogram)); + for (i = 0; i < n; ++i) { + uint64_t t; + choice = choose_array_element_by_weight(zeros, 5, &t); + tt_int_op(t, ==, 0); + tt_int_op(choice, >=, 0); + tt_int_op(choice, <, 5); + histogram[choice]++; + } + /* Now see if we chose things about frequently enough. */ + max_sq_error = 0; + for (i=0; i<5; ++i) { + int expected = n/5; + double frac_diff = 0, sq; + TT_BLATHER((" %d : %5d vs %5d\n", (int)vals[i], histogram[i], expected)); + frac_diff = (histogram[i] - expected) / ((double)expected); + sq = frac_diff * frac_diff; + if (sq > max_sq_error) + max_sq_error = sq; + } + /* It should almost always be much much less than this. If you want to + * figure out the odds, please feel free. */ + tt_double_op(max_sq_error, <, .05); + done: + ; +} + #define DIR_LEGACY(name) \ { #name, legacy_test_helper, TT_FORK, &legacy_setup, test_dir_ ## name } @@ -1396,6 +1476,7 @@ struct testcase_t dir_tests[] = { DIR_LEGACY(measured_bw), DIR_LEGACY(param_voting), DIR_LEGACY(v3_networkstatus), + DIR(random_weighted), END_OF_TESTCASES };

1 0

[tor/master] In choose-by-bw, scale to better use the range of uint64
by nickm＠torproject.org 11 Sep '12

11 Sep '12

commit 5c3199cda72fbdcf8f801219a0f9932673801da5 Author: Nick Mathewson <nickm(a)torproject.org> Date: Mon Aug 27 17:37:56 2012 -0400 In choose-by-bw, scale to better use the range of uint64 The smart part of this is based on an approach and a suggestion by rransom. The unsmart part is my own fault. --- src/or/routerlist.c | 109 ++++++++++++++++++++++++++++++++------------------- src/or/routerlist.h | 13 +++++- src/test/test_dir.c | 60 ++++++++++++++++++++++++---- 3 files changed, 131 insertions(+), 51 deletions(-) diff --git a/src/or/routerlist.c b/src/or/routerlist.c index 1c0aca8..185abf5 100644 --- a/src/or/routerlist.c +++ b/src/or/routerlist.c @@ -1653,15 +1653,41 @@ router_get_advertised_bandwidth_capped(const routerinfo_t *router) return result; } +/** Given an array of double/uint64_t unions that are currently being used as + * doubles, convert them to uint64_t, and try to scale them linearly so as to + * much of the range of uint64_t. If total_out is provided, set it to + * the sum of all elements in the array _before_ scaling. */ +/* private */ void +scale_array_elements_to_u64(u64_dbl_t *entries, int n_entries, + uint64_t *total_out) +{ + double total = 0.0; + double scale_factor; + int i; + /* big, but far away from overflowing an int64_t */ +#define SCALE_TO_U64_MAX (INT64_MAX / 4) + + for (i = 0; i < n_entries; ++i) + total += entries[i].dbl; + + scale_factor = SCALE_TO_U64_MAX / total; + + for (i = 0; i < n_entries; ++i) + entries[i].u64 = tor_llround(entries[i].dbl * scale_factor); + + if (total_out) + *total_out = (uint64_t) total; + +#undef SCALE_TO_U64_MAX +} + /** Pick a random element of n_entries-element array entries, - * choosing each element with a probability proportional to its value, and - * return the index of that element. If all elements are 0, choose an index - * at random. If total_out is provided, set it to the sum of all - * elements in the array. Return -1 on error. + * choosing each element with a probability proportional to its (uint64_t) + * value, and return the index of that element. If all elements are 0, choose + * an index at random. Return -1 on error. */ /* private */ int -choose_array_element_by_weight(const uint64_t *entries, int n_entries, - uint64_t *total_out) +choose_array_element_by_weight(const u64_dbl_t *entries, int n_entries) { int i, i_chosen=-1, n_chosen=0; uint64_t total_so_far = 0; @@ -1669,10 +1695,7 @@ choose_array_element_by_weight(const uint64_t *entries, int n_entries, uint64_t total = 0; for (i = 0; i < n_entries; ++i) - total += entries[i]; - - if (total_out) - *total_out = total; + total += entries[i].u64; if (n_entries < 1) return -1; @@ -1683,7 +1706,7 @@ choose_array_element_by_weight(const uint64_t *entries, int n_entries, rand_val = crypto_rand_uint64(total); for (i = 0; i < n_entries; ++i) { - total_so_far += entries[i]; + total_so_far += entries[i].u64; if (total_so_far > rand_val) { i_chosen = i; n_chosen++; @@ -1753,7 +1776,7 @@ smartlist_choose_node_by_bandwidth_weights(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; - uint64_t *bandwidths; + u64_dbl_t *bandwidths; /* Can't choose exit and guard at same time */ tor_assert(rule == NO_WEIGHTING || @@ -1834,7 +1857,7 @@ smartlist_choose_node_by_bandwidth_weights(smartlist_t *sl, Web /= weight_scale; Wdb /= weight_scale; - bandwidths = tor_malloc_zero(sizeof(uint64_t)*smartlist_len(sl)); + bandwidths = tor_malloc_zero(sizeof(u64_dbl_t)*smartlist_len(sl)); // Cycle through smartlist and total the bandwidth. SMARTLIST_FOREACH_BEGIN(sl, const node_t *, node) { @@ -1879,9 +1902,9 @@ smartlist_choose_node_by_bandwidth_weights(smartlist_t *sl, if (weight < 0.0) weight = 0.0; - bandwidths[node_sl_idx] = tor_llround(weight*this_bw + 0.5); + bandwidths[node_sl_idx].dbl = weight*this_bw + 0.5; if (is_me) - sl_last_weighted_bw_of_me = bandwidths[node_sl_idx]; + sl_last_weighted_bw_of_me = (uint64_t) bandwidths[node_sl_idx].dbl; } SMARTLIST_FOREACH_END(node); log_debug(LD_CIRC, "Choosing node for rule %s based on weights " @@ -1889,10 +1912,12 @@ smartlist_choose_node_by_bandwidth_weights(smartlist_t *sl, bandwidth_weight_rule_to_string(rule), Wg, Wm, We, Wd, U64_PRINTF_ARG(weighted_bw)); + scale_array_elements_to_u64(bandwidths, smartlist_len(sl), + &sl_last_total_weighted_bw); + { int idx = choose_array_element_by_weight(bandwidths, - smartlist_len(sl), - &sl_last_total_weighted_bw); + smartlist_len(sl)); tor_free(bandwidths); return idx < 0 ? NULL : smartlist_get(sl, idx); } @@ -1916,12 +1941,12 @@ smartlist_choose_node_by_bandwidth(smartlist_t *sl, bandwidth_weight_rule_t rule) { unsigned int i; - uint64_t *bandwidths; + u64_dbl_t *bandwidths; int is_exit; int is_guard; int is_fast; - uint64_t total_nonexit_bw = 0, total_exit_bw = 0; - uint64_t total_nonguard_bw = 0, total_guard_bw = 0; + double total_nonexit_bw = 0, total_exit_bw = 0; + double total_nonguard_bw = 0, total_guard_bw = 0; double exit_weight; double guard_weight; int n_unknown = 0; @@ -1950,7 +1975,7 @@ smartlist_choose_node_by_bandwidth(smartlist_t *sl, /* First count the total bandwidth weight, and make a list * of each value. We use UINT64_MAX to indicate "unknown". */ - bandwidths = tor_malloc_zero(sizeof(uint64_t)*smartlist_len(sl)); + bandwidths = tor_malloc_zero(sizeof(u64_dbl_t)*smartlist_len(sl)); fast_bits = bitarray_init_zero(smartlist_len(sl)); exit_bits = bitarray_init_zero(smartlist_len(sl)); guard_bits = bitarray_init_zero(smartlist_len(sl)); @@ -1986,7 +2011,7 @@ smartlist_choose_node_by_bandwidth(smartlist_t *sl, bitarray_set(fast_bits, i); if (is_known) { - bandwidths[i] = this_bw; + bandwidths[i].dbl = this_bw; if (is_guard) total_guard_bw += this_bw; else @@ -1997,14 +2022,16 @@ smartlist_choose_node_by_bandwidth(smartlist_t *sl, total_nonexit_bw += this_bw; } else { ++n_unknown; - bandwidths[i] = UINT64_MAX; + bandwidths[i].dbl = -1.0; } } SMARTLIST_FOREACH_END(node); +#define EPSILON .1 + /* Now, fill in the unknown values. */ if (n_unknown) { int32_t avg_fast, avg_slow; - if (total_exit_bw+total_nonexit_bw) { + if (total_exit_bw+total_nonexit_bw < EPSILON) { /* if there's some bandwidth, there's at least one known router, * so no worries about div by 0 here */ int n_known = smartlist_len(sl)-n_unknown; @@ -2015,25 +2042,25 @@ smartlist_choose_node_by_bandwidth(smartlist_t *sl, avg_slow = 20000; } for (i=0; i<(unsigned)smartlist_len(sl); ++i) { - if (bandwidths[i] != UINT64_MAX) + if (bandwidths[i].dbl >= 0.0) continue; is_fast = bitarray_is_set(fast_bits, i); is_exit = bitarray_is_set(exit_bits, i); is_guard = bitarray_is_set(guard_bits, i); - bandwidths[i] = is_fast ? avg_fast : avg_slow; + bandwidths[i].dbl = is_fast ? avg_fast : avg_slow; if (is_exit) - total_exit_bw += bandwidths[i]; + total_exit_bw += bandwidths[i].dbl; else - total_nonexit_bw += bandwidths[i]; + total_nonexit_bw += bandwidths[i].dbl; if (is_guard) - total_guard_bw += bandwidths[i]; + total_guard_bw += bandwidths[i].dbl; else - total_nonguard_bw += bandwidths[i]; + total_nonguard_bw += bandwidths[i].dbl; } } /* If there's no bandwidth at all, pick at random. */ - if (!(total_exit_bw+total_nonexit_bw)) { + if (total_exit_bw+total_nonexit_bw < EPSILON) { tor_free(bandwidths); tor_free(fast_bits); tor_free(exit_bits); @@ -2050,12 +2077,12 @@ smartlist_choose_node_by_bandwidth(smartlist_t *sl, * For detailed derivation of this formula, see * http://archives.seul.org/or/dev/Jul-2007/msg00056.html */ - if (rule == WEIGHT_FOR_EXIT || !total_exit_bw) + if (rule == WEIGHT_FOR_EXIT || total_exit_bw<EPSILON) exit_weight = 1.0; else exit_weight = 1.0 - all_bw/(3.0*exit_bw); - if (rule == WEIGHT_FOR_GUARD || !total_guard_bw) + if (rule == WEIGHT_FOR_GUARD || total_guard_bw<EPSILON) guard_weight = 1.0; else guard_weight = 1.0 - all_bw/(3.0*guard_bw); @@ -2068,19 +2095,19 @@ smartlist_choose_node_by_bandwidth(smartlist_t *sl, sl_last_weighted_bw_of_me = 0; for (i=0; i < (unsigned)smartlist_len(sl); i++) { - tor_assert(bandwidths[i] < UINT64_MAX); + tor_assert(bandwidths[i].dbl >= 0.0); is_exit = bitarray_is_set(exit_bits, i); is_guard = bitarray_is_set(guard_bits, i); if (is_exit && is_guard) - bandwidths[i] = tor_llround(bandwidths[i] * exit_weight * guard_weight); + bandwidths[i].dbl *= exit_weight * guard_weight; else if (is_guard) - bandwidths[i] = tor_llround(bandwidths[i] * guard_weight); + bandwidths[i].dbl *= guard_weight; else if (is_exit) - bandwidths[i] = tor_llround(bandwidths[i] * exit_weight); + bandwidths[i].dbl *= exit_weight; if (i == (unsigned) me_idx) - sl_last_weighted_bw_of_me = bandwidths[i]; + sl_last_weighted_bw_of_me = (uint64_t) bandwidths[i].dbl; } } @@ -2099,10 +2126,12 @@ smartlist_choose_node_by_bandwidth(smartlist_t *sl, guard_weight, (int)(rule == WEIGHT_FOR_GUARD)); #endif + scale_array_elements_to_u64(bandwidths, smartlist_len(sl), + &sl_last_total_weighted_bw); + { int idx = choose_array_element_by_weight(bandwidths, - smartlist_len(sl), - &sl_last_total_weighted_bw); + smartlist_len(sl)); tor_free(bandwidths); tor_free(fast_bits); tor_free(exit_bits); diff --git a/src/or/routerlist.h b/src/or/routerlist.h index 0b9b297..2072611 100644 --- a/src/or/routerlist.h +++ b/src/or/routerlist.h @@ -217,8 +217,17 @@ int hex_digest_nickname_decode(const char *hexdigest, char *nickname_out); #ifdef ROUTERLIST_PRIVATE -int choose_array_element_by_weight(const uint64_t *entries, int n_entries, - uint64_t *total_out); +/** Helper type for choosing routers by bandwidth: contains a union of + * double and uint64_t. Before we call scale_array_elements_to_u64, it holds + * a double; after, it holds a uint64_t. */ +typedef union u64_dbl_t { + uint64_t u64; + double dbl; +} u64_dbl_t; + +int choose_array_element_by_weight(const u64_dbl_t *entries, int n_entries); +void scale_array_elements_to_u64(u64_dbl_t *entries, int n_entries, + uint64_t *total_out); #endif #endif diff --git a/src/test/test_dir.c b/src/test/test_dir.c index ed0c5a1..3f78ece 100644 --- a/src/test/test_dir.c +++ b/src/test/test_dir.c @@ -4,6 +4,8 @@ /* See LICENSE for licensing information */ #include "orconfig.h" +#include <math.h> + #define DIRSERV_PRIVATE #define DIRVOTE_PRIVATE #define ROUTER_PRIVATE @@ -1383,11 +1385,50 @@ test_dir_v3_networkstatus(void) } static void +test_dir_scale_bw(void *testdata) +{ + double v[8] = { 2.0/3, + 7.0, + 1.0, + 3.0, + 1.0/5, + 1.0/7, + 12.0, + 24.0 }; + u64_dbl_t vals[8]; + uint64_t total; + int i; + + (void) testdata; + + for (i=0; i<8; ++i) + vals[i].dbl = v[i]; + + scale_array_elements_to_u64(vals, 8, &total); + + tt_int_op((int)total, ==, 48); + total = 0; + for (i=0; i<8; ++i) { + total += vals[i].u64; + } + tt_assert(total >= (U64_LITERAL(1)<<60)); + tt_assert(total <= (U64_LITERAL(1)<<62)); + + for (i=0; i<8; ++i) { + double ratio = ((double)vals[i].u64) / vals[2].u64; + tt_double_op(fabs(ratio - v[i]), <, .00001); + } + + done: + ; +} + +static void test_dir_random_weighted(void *testdata) { int histogram[10]; uint64_t vals[10] = {3,1,2,4,6,0,7,5,8,9}, total=0; - uint64_t zeros[5] = {0,0,0,0,0}; + u64_dbl_t inp[10]; int i, choice; const int n = 50000; double max_sq_error; @@ -1396,13 +1437,13 @@ test_dir_random_weighted(void *testdata) /* Try a ten-element array with values from 0 through 10. The values are * in a scrambled order to make sure we don't depend on order. */ memset(histogram,0,sizeof(histogram)); - for (i=0; i<10; ++i) + for (i=0; i<10; ++i) { + inp[i].u64 = vals[i]; total += vals[i]; + } tt_int_op(total, ==, 45); for (i=0; i<n; ++i) { - uint64_t t; - choice = choose_array_element_by_weight(vals, 10, &t); - tt_int_op(t, ==, total); + choice = choose_array_element_by_weight(inp, 10); tt_int_op(choice, >=, 0); tt_int_op(choice, <, 10); histogram[choice]++; @@ -1429,16 +1470,16 @@ test_dir_random_weighted(void *testdata) /* Now try a singleton; do we choose it? */ for (i = 0; i < 100; ++i) { - choice = choose_array_element_by_weight(vals, 1, NULL); + choice = choose_array_element_by_weight(inp, 1); tt_int_op(choice, ==, 0); } /* Now try an array of zeros. We should choose randomly. */ memset(histogram,0,sizeof(histogram)); + for (i = 0; i < 5; ++i) + inp[i].u64 = 0; for (i = 0; i < n; ++i) { - uint64_t t; - choice = choose_array_element_by_weight(zeros, 5, &t); - tt_int_op(t, ==, 0); + choice = choose_array_element_by_weight(inp, 5); tt_int_op(choice, >=, 0); tt_int_op(choice, <, 5); histogram[choice]++; @@ -1477,6 +1518,7 @@ struct testcase_t dir_tests[] = { DIR_LEGACY(param_voting), DIR_LEGACY(v3_networkstatus), DIR(random_weighted), + DIR(scale_bw), END_OF_TESTCASES };

1 0

[tor/master] Use a time-invariant comparison in choose_array_element_by_weight
by nickm＠torproject.org 11 Sep '12

11 Sep '12

commit 9982122f3448293e80adf83cb28c7ab66bc04da9 Author: Nick Mathewson <nickm(a)torproject.org> Date: Tue Aug 28 12:42:21 2012 -0400 Use a time-invariant comparison in choose_array_element_by_weight --- src/or/routerlist.c | 22 +++++++++++++++++++--- 1 files changed, 19 insertions(+), 3 deletions(-) diff --git a/src/or/routerlist.c b/src/or/routerlist.c index 185abf5..7dc430b 100644 --- a/src/or/routerlist.c +++ b/src/or/routerlist.c @@ -1681,6 +1681,20 @@ scale_array_elements_to_u64(u64_dbl_t *entries, int n_entries, #undef SCALE_TO_U64_MAX } +/** Time-invariant 64-bit greater-than; works on two integers in the range + * (0,INT64_MAX). */ +#if SIZEOF_VOID_P == 8 +#define gt_i64_timei(a,b) ((a) > (b)) +#else +static INLINE int +gt_i64_timei(uint64_t a, uint64_t b) +{ + int64_t diff = (int64_t) (b - a); + int res = diff >> 63; + return res & 1; +} +#endif + /** Pick a random element of n_entries-element array entries, * choosing each element with a probability proportional to its (uint64_t) * value, and return the index of that element. If all elements are 0, choose @@ -1703,16 +1717,18 @@ choose_array_element_by_weight(const u64_dbl_t *entries, int n_entries) if (total == 0) return crypto_rand_int(n_entries); + tor_assert(total < INT64_MAX); + rand_val = crypto_rand_uint64(total); for (i = 0; i < n_entries; ++i) { total_so_far += entries[i].u64; - if (total_so_far > rand_val) { + if (gt_i64_timei(total_so_far, rand_val)) { i_chosen = i; n_chosen++; - /* Set rand_val to UINT_MAX rather than stopping the loop. This way, + /* Set rand_val to INT64_MAX rather than stopping the loop. This way, * the time we spend in the loop does not leak which element we chose. */ - rand_val = UINT64_MAX; + rand_val = INT64_MAX; } } tor_assert(total_so_far == total);

1 0

[tor/master] Spelling fix in util.c comments
by nickm＠torproject.org 11 Sep '12

11 Sep '12

commit ef628649c85c9a996b22dfbad494f1757b091d45 Author: Nick Mathewson <nickm(a)torproject.org> Date: Mon Aug 27 16:44:54 2012 -0400 Spelling fix in util.c comments --- src/common/util.c | 4 ++-- 1 files changed, 2 insertions(+), 2 deletions(-) diff --git a/src/common/util.c b/src/common/util.c index 60222f4..cea63e5 100644 --- a/src/common/util.c +++ b/src/common/util.c @@ -364,7 +364,7 @@ tor_mathlog(double d) } /** Return the long integer closest to d. We define this wrapper here so - * that not all users of math.h need to use the right incancations to get + * that not all users of math.h need to use the right intancations to get * the c99 functions. */ long tor_lround(double d) @@ -379,7 +379,7 @@ tor_lround(double d) } /** Return the 64-bit integer closest to d. We define this wrapper here so - * that not all users of math.h need to use the right incancations to get the + * that not all users of math.h need to use the right incantations to get the * c99 functions. */ int64_t tor_llround(double d)

1 0

[tor/master] Merge remote-tracking branch 'public/bug6538'
by nickm＠torproject.org 11 Sep '12

11 Sep '12

commit 75c9ccd4f851bac6d32cb08ded557ac207bc8002 Merge: b8f93c5 9982122 Author: Nick Mathewson <nickm(a)torproject.org> Date: Tue Sep 11 17:51:36 2012 -0400 Merge remote-tracking branch 'public/bug6538' Conflicts: configure.ac changes/bug6538 | 16 +++ configure.ac | 1 + src/common/util.c | 17 +++- src/common/util.h | 1 + src/or/routerlist.c | 314 +++++++++++++++++++++++++------------------------- src/or/routerlist.h | 14 +++ src/test/test.h | 4 + src/test/test_dir.c | 123 ++++++++++++++++++++ 8 files changed, 332 insertions(+), 158 deletions(-) diff --cc configure.ac index ab291b1,0000000..7f33828 mode 100644,000000..100644 --- a/configure.ac +++ b/configure.ac @@@ -1,1325 -1,0 +1,1326 @@@ +dnl Copyright (c) 2001-2004, Roger Dingledine +dnl Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson +dnl Copyright (c) 2007-2012, The Tor Project, Inc. +dnl See LICENSE for licensing information + +AC_INIT([tor],[0.2.4.2-alpha-dev]) +AC_CONFIG_SRCDIR([src/or/main.c]) +AM_INIT_AUTOMAKE +m4_ifdef([AM_SILENT_RULES], [AM_SILENT_RULES([yes])]) +AC_CONFIG_HEADERS([orconfig.h]) + +AC_CANONICAL_HOST + +if test -f /etc/redhat-release ; then + if test -f /usr/kerberos/include ; then + CPPFLAGS="$CPPFLAGS -I/usr/kerberos/include" + fi +fi + +# Not a no-op; we want to make sure that CPPFLAGS is set before we use +# the += operator on it in src/or/Makefile.am +CPPFLAGS="$CPPFLAGS -I\${top_srcdir}/src/common" + +#XXXX020 We should make these enabled or not, before 0.2.0.x-final +AC_ARG_ENABLE(buf-freelists, + AS_HELP_STRING(--disable-buf-freelists, disable freelists for buffer RAM)) +AC_ARG_ENABLE(openbsd-malloc, + AS_HELP_STRING(--enable-openbsd-malloc, Use malloc code from openbsd. Linux only)) +AC_ARG_ENABLE(instrument-downloads, + AS_HELP_STRING(--enable-instrument-downloads, Instrument downloads of directory resources etc.)) +AC_ARG_ENABLE(static-openssl, + AS_HELP_STRING(--enable-static-openssl, Link against a static openssl library. Requires --with-openssl-dir)) +AC_ARG_ENABLE(static-libevent, + AS_HELP_STRING(--enable-static-libevent, Link against a static libevent library. Requires --with-libevent-dir)) +AC_ARG_ENABLE(static-zlib, + AS_HELP_STRING(--enable-static-zlib, Link against a static zlib library. Requires --with-zlib-dir)) +AC_ARG_ENABLE(static-tor, + AS_HELP_STRING(--enable-static-tor, Create an entirely static Tor binary. Requires --with-openssl-dir and --with-libevent-dir and --with-zlib-dir)) + +if test "$enable_static_tor" = "yes"; then + enable_static_libevent="yes"; + enable_static_openssl="yes"; + enable_static_zlib="yes"; + CFLAGS="$CFLAGS -static" +fi + +if test x$enable_buf_freelists != xno; then + AC_DEFINE(ENABLE_BUF_FREELISTS, 1, + [Defined if we try to use freelists for buffer RAM chunks]) +fi +AM_CONDITIONAL(USE_OPENBSD_MALLOC, test x$enable_openbsd_malloc = xyes) +if test x$enable_instrument_downloads = xyes; then + AC_DEFINE(INSTRUMENT_DOWNLOADS, 1, + [Defined if we want to keep track of how much of each kind of resource we download.]) +fi + +AC_ARG_ENABLE(transparent, + AS_HELP_STRING(--disable-transparent, disable transparent proxy support), + [case "${enableval}" in + yes) transparent=true ;; + no) transparent=false ;; + *) AC_MSG_ERROR(bad value for --enable-transparent) ;; + esac], [transparent=true]) + +AC_ARG_ENABLE(asciidoc, + AS_HELP_STRING(--disable-asciidoc, don't use asciidoc (disables building of manpages)), + [case "${enableval}" in + yes) asciidoc=true ;; + no) asciidoc=false ;; + *) AC_MSG_ERROR(bad value for --disable-asciidoc) ;; + esac], [asciidoc=true]) + +# By default, we're not ready to ship a NAT-PMP aware Tor +AC_ARG_ENABLE(nat-pmp, + AS_HELP_STRING(--enable-nat-pmp, enable NAT-PMP support), + [case "${enableval}" in + yes) natpmp=true ;; + no) natpmp=false ;; + * ) AC_MSG_ERROR(bad value for --enable-nat-pmp) ;; + esac], [natpmp=false]) + +# By default, we're not ready to ship a UPnP aware Tor +AC_ARG_ENABLE(upnp, + AS_HELP_STRING(--enable-upnp, enable UPnP support), + [case "${enableval}" in + yes) upnp=true ;; + no) upnp=false ;; + * ) AC_MSG_ERROR(bad value for --enable-upnp) ;; + esac], [upnp=false]) + + +AC_ARG_ENABLE(threads, + AS_HELP_STRING(--disable-threads, disable multi-threading support)) + +if test x$enable_threads = x; then + case $host in + *-*-solaris* ) + # Don't try multithreading on solaris -- cpuworkers seem to lock. + AC_MSG_NOTICE([You are running Solaris; Sometimes threading makes +cpu workers lock up here, so I will disable threads.]) + enable_threads="no";; + *) + enable_threads="yes";; + esac +fi + +if test "$enable_threads" = "yes"; then + AC_DEFINE(ENABLE_THREADS, 1, [Defined if we will try to use multithreading]) +fi + +case $host in + *-*-solaris* ) + AC_DEFINE(_REENTRANT, 1, [Define on some platforms to activate x_r() functions in time.h]) + ;; +esac + +AC_ARG_ENABLE(gcc-warnings, + AS_HELP_STRING(--enable-gcc-warnings, enable verbose warnings)) +AC_ARG_ENABLE(gcc-warnings-advisory, + AS_HELP_STRING(--enable-gcc-warnings-advisory, [enable verbose warnings, excluding -Werror])) + +dnl Adam shostack suggests the following for Windows: +dnl -D_FORTIFY_SOURCE=2 -fstack-protector-all +dnl Others suggest '/gs /safeseh /nxcompat /dynamicbase' for non-gcc on Windows +dnl This requires that we use gcc and that we add -O2 to the CFLAGS. +AC_ARG_ENABLE(gcc-hardening, + AS_HELP_STRING(--disable-gcc-hardening, disable compiler security checks)) + +dnl Linker hardening options +dnl Currently these options are ELF specific - you can't use this with MacOSX +AC_ARG_ENABLE(linker-hardening, + AS_HELP_STRING(--disable-linker-hardening, disable linker security fixups)) + +AC_ARG_ENABLE(local-appdata, + AS_HELP_STRING(--enable-local-appdata, default to host local application data paths on Windows)) +if test "$enable_local_appdata" = "yes"; then + AC_DEFINE(ENABLE_LOCAL_APPDATA, 1, + [Defined if we default to host local appdata paths on Windows]) +fi + +# Tor2web mode flag +AC_ARG_ENABLE(tor2web-mode, + AS_HELP_STRING(--enable-tor2web-mode, support tor2web non-anonymous mode), +[if test x$enableval = xyes; then + CFLAGS="$CFLAGS -D ENABLE_TOR2WEB_MODE=1" +fi]) + +AC_ARG_ENABLE(bufferevents, + AS_HELP_STRING(--enable-bufferevents, use Libevent's buffered IO.)) + +dnl check for the correct "ar" when cross-compiling +AN_MAKEVAR([AR], [AC_PROG_AR]) +AN_PROGRAM([ar], [AC_PROG_AR]) +AC_DEFUN([AC_PROG_AR], [AC_CHECK_TOOL([AR], [ar], [ar])]) +AC_PROG_AR + +AC_PROG_CC +AC_PROG_CPP +AC_PROG_MAKE_SET +AC_PROG_RANLIB + +dnl autoconf 2.59 appears not to support AC_PROG_SED +AC_CHECK_PROG([SED],[sed],[sed],[/bin/false]) + +dnl check for asciidoc and a2x +AC_PATH_PROG([ASCIIDOC], [asciidoc], none) +AC_PATH_PROG([A2X], [a2x], none) + +AM_CONDITIONAL(USE_ASCIIDOC, test x$asciidoc = xtrue) + +AM_CONDITIONAL(USE_FW_HELPER, test x$natpmp = xtrue || test x$upnp = xtrue) +AM_CONDITIONAL(NAT_PMP, test x$natpmp = xtrue) +AM_CONDITIONAL(MINIUPNPC, test x$upnp = xtrue) +AM_PROG_CC_C_O + +ifdef([AC_C_FLEXIBLE_ARRAY_MEMBER], [ +AC_C_FLEXIBLE_ARRAY_MEMBER +], [ + dnl Maybe we've got an old autoconf... + AC_CACHE_CHECK([for flexible array members], + tor_cv_c_flexarray, + [AC_COMPILE_IFELSE( + AC_LANG_PROGRAM([ + struct abc { int a; char b[]; }; +], [ + struct abc *def = malloc(sizeof(struct abc)+sizeof(char)); + def->b[0] = 33; +]), + [tor_cv_c_flexarray=yes], + [tor_cv_c_flexarray=no])]) + if test $tor_cv_flexarray = yes ; then + AC_DEFINE([FLEXIBLE_ARRAY_MEMBER], [], [Define to nothing if C supports flexible array members, and to 1 if it does not.]) + else + AC_DEFINE([FLEXIBLE_ARRAY_MEMBER], [1], [Define to nothing if C supports flexible array members, and to 1 if it does not.]) + fi +]) + +AC_PATH_PROG([SHA1SUM], [sha1sum], none) +AC_PATH_PROG([OPENSSL], [openssl], none) + +TORUSER=_tor +AC_ARG_WITH(tor-user, + [ --with-tor-user=NAME Specify username for tor daemon ], + [ + TORUSER=$withval + ] +) +AC_SUBST(TORUSER) + +TORGROUP=_tor +AC_ARG_WITH(tor-group, + [ --with-tor-group=NAME Specify group name for tor daemon ], + [ + TORGROUP=$withval + ] +) +AC_SUBST(TORGROUP) + + +dnl If _WIN32 is defined and non-zero, we are building for win32 +AC_MSG_CHECKING([for win32]) +AC_RUN_IFELSE([AC_LANG_SOURCE([ +int main(int c, char **v) { +#ifdef _WIN32 +#if _WIN32 + return 0; +#else + return 1; +#endif +#else + return 2; +#endif +}])], +bwin32=true; AC_MSG_RESULT([yes]), +bwin32=false; AC_MSG_RESULT([no]), +bwin32=cross; AC_MSG_RESULT([cross]) +) + +if test "$bwin32" = cross; then +AC_MSG_CHECKING([for win32 (cross)]) +AC_COMPILE_IFELSE([AC_LANG_SOURCE([ +#ifdef _WIN32 +int main(int c, char **v) {return 0;} +#else +#error +int main(int c, char **v) {return x(y);} +#endif +])], +bwin32=true; AC_MSG_RESULT([yes]), +bwin32=false; AC_MSG_RESULT([no])) +fi + +AM_CONDITIONAL(BUILD_NT_SERVICES, test x$bwin32 = xtrue) + +dnl Enable C99 when compiling with MIPSpro +AC_MSG_CHECKING([for MIPSpro compiler]) +AC_COMPILE_IFELSE([AC_LANG_PROGRAM(, [ +#if (defined(__sgi) && defined(_COMPILER_VERSION)) +#error + return x(y); +#endif +])], +bmipspro=false; AC_MSG_RESULT(no), +bmipspro=true; AC_MSG_RESULT(yes)) + +if test "$bmipspro" = true; then + CFLAGS="$CFLAGS -c99" +fi + +AC_C_BIGENDIAN + +AC_SEARCH_LIBS(socket, [socket network]) +AC_SEARCH_LIBS(gethostbyname, [nsl]) +AC_SEARCH_LIBS(dlopen, [dl]) +AC_SEARCH_LIBS(inet_aton, [resolv]) +saved_LIBS="$LIBS" +AC_SEARCH_LIBS([clock_gettime], [rt]) +if test "$LIBS" != "$saved_LIBS"; then + # Looks like we need -lrt for clock_gettime(). + have_rt=yes +fi + +if test "$enable_threads" = "yes"; then + AC_SEARCH_LIBS(pthread_create, [pthread]) + AC_SEARCH_LIBS(pthread_detach, [pthread]) +fi + +dnl ------------------------------------------------------------------- +dnl Check for functions before libevent, since libevent-1.2 apparently +dnl exports strlcpy without defining it in a header. + +AC_CHECK_FUNCS( + _NSGetEnviron \ + accept4 \ + clock_gettime \ + flock \ + ftime \ + getaddrinfo \ + getifaddrs \ + getrlimit \ + gettimeofday \ + gmtime_r \ + inet_aton \ + ioctl \ + issetugid \ ++ llround \ + localtime_r \ + lround \ + memmem \ + prctl \ + rint \ + socketpair \ + strlcat \ + strlcpy \ + strptime \ + strtok_r \ + strtoull \ + sysconf \ + uname \ + vasprintf \ +) + +if test "$enable_threads" = "yes"; then + AC_CHECK_HEADERS(pthread.h) + AC_CHECK_FUNCS(pthread_create) +fi + +dnl ------------------------------------------------------ +dnl Where do you live, libevent? And how do we call you? + +if test "$bwin32" = true; then + TOR_LIB_WS32=-lws2_32 + TOR_LIB_IPHLPAPI=-liphlpapi + # Some of the cargo-cults recommend -lwsock32 as well, but I don't + # think it's actually necessary. + TOR_LIB_GDI=-lgdi32 +else + TOR_LIB_WS32= + TOR_LIB_GDI= +fi +AC_SUBST(TOR_LIB_WS32) +AC_SUBST(TOR_LIB_GDI) +AC_SUBST(TOR_LIB_IPHLPAPI) + +dnl We need to do this before we try our disgusting hack below. +AC_CHECK_HEADERS([sys/types.h]) + +dnl This is a disgusting hack so we safely include older libevent headers. +AC_CHECK_TYPE(u_int64_t, unsigned long long) +AC_CHECK_TYPE(u_int32_t, unsigned long) +AC_CHECK_TYPE(u_int16_t, unsigned short) +AC_CHECK_TYPE(u_int8_t, unsigned char) + +tor_libevent_pkg_redhat="libevent" +tor_libevent_pkg_debian="libevent-dev" +tor_libevent_devpkg_redhat="libevent-devel" +tor_libevent_devpkg_debian="libevent-dev" + +dnl On Gnu/Linux or any place we require it, we'll add librt to the Libevent +dnl linking for static builds. +STATIC_LIBEVENT_FLAGS="" +if test "$enable_static_libevent" = "yes"; then + if test "$have_rt" = yes; then + STATIC_LIBEVENT_FLAGS=" -lrt " + fi +fi + +TOR_SEARCH_LIBRARY(libevent, $trylibeventdir, [-levent $STATIC_LIBEVENT_FLAGS $TOR_LIB_WS32], [ +#ifdef _WIN32 +#include <winsock2.h> +#endif +#include <stdlib.h> +#include <sys/time.h> +#include <sys/types.h> +#include <event.h>], [ +#ifdef _WIN32 +#include <winsock2.h> +#endif +void exit(int); void *event_init(void);], + [ +#ifdef _WIN32 +{WSADATA d; WSAStartup(0x101,&d); } +#endif +event_init(); exit(0); +], [--with-libevent-dir], [/opt/libevent]) + +dnl Now check for particular libevent functions. +save_LIBS="$LIBS" +save_LDFLAGS="$LDFLAGS" +save_CPPFLAGS="$CPPFLAGS" +LIBS="-levent $STATIC_LIBEVENT_FLAGS $TOR_LIB_WS32 $LIBS" +LDFLAGS="$TOR_LDFLAGS_libevent $LDFLAGS" +CPPFLAGS="$TOR_CPPFLAGS_libevent $CPPFLAGS" +AC_CHECK_FUNCS(event_get_version event_get_version_number event_get_method event_set_log_callback evdns_set_outgoing_bind_address event_base_loopexit) +AC_CHECK_MEMBERS([struct event.min_heap_idx], , , +[#include <event.h> +]) + +AC_CHECK_HEADERS(event2/event.h event2/dns.h event2/bufferevent_ssl.h) + +LIBS="$save_LIBS" +LDFLAGS="$save_LDFLAGS" +CPPFLAGS="$save_CPPFLAGS" + + +AM_CONDITIONAL(USE_EXTERNAL_EVDNS, test x$ac_cv_header_event2_dns_h = xyes) + +if test "$enable_static_libevent" = "yes"; then + if test "$tor_cv_library_libevent_dir" = "(system)"; then + AC_MSG_ERROR("You must specify an explicit --with-libevent-dir=x option when using --enable-static-libevent") + else + TOR_LIBEVENT_LIBS="$TOR_LIBDIR_libevent/libevent.a $STATIC_LIBEVENT_FLAGS" + fi +else + TOR_LIBEVENT_LIBS="-levent" +fi + +dnl This isn't the best test for Libevent 2.0.3-alpha. Once it's released, +dnl we can do much better. +if test "$enable_bufferevents" = "yes" ; then + if test "$ac_cv_header_event2_bufferevent_ssl_h" != "yes" ; then + AC_MSG_ERROR([You've asked for bufferevent support, but you're using a version of Libevent without SSL support. This won't work. We need Libevent 2.0.8-rc or later, and you don't seem to even have Libevent 2.0.3-alpha.]) + else + + CPPFLAGS="$CPPFLAGS $TOR_CPPFLAGS_libevent" + + # Check for the right version. First see if version detection works. + AC_MSG_CHECKING([whether we can detect the Libevent version]) + AC_COMPILE_IFELSE([AC_LANG_SOURCE([ +#include <event2/event.h> +#if !defined(LIBEVENT_VERSION_NUMBER) || LIBEVENT_VERSION_NUMBER < 10 +#error +int x = y(zz); +#else +int x = 1; +#endif + ])], [event_version_number_works=yes; AC_MSG_RESULT([yes]) ], + [event_version_number_works=no; AC_MSG_RESULT([no])]) + if test "$event_version_number_works" != 'yes'; then + AC_MSG_WARN([Version detection on Libevent seems broken. Your Libevent installation is probably screwed up or very old.]) + else + AC_MSG_CHECKING([whether Libevent is new enough for bufferevents]) + AC_COMPILE_IFELSE([AC_LANG_SOURCE([ +#include <event2/event.h> +#if !defined(LIBEVENT_VERSION_NUMBER) || LIBEVENT_VERSION_NUMBER < 0x02000d00 +#error +int x = y(zz); +#else +int x = 1; +#endif + ])], [ AC_MSG_RESULT([yes]) ], + [ AC_MSG_RESULT([no]) + AC_MSG_ERROR([Libevent does not seem new enough to support bufferevents. We require 2.0.13-stable or later]) ] ) + fi + fi +fi + +LIBS="$save_LIBS" +LDFLAGS="$save_LDFLAGS" +CPPFLAGS="$save_CPPFLAGS" + +AM_CONDITIONAL(USE_BUFFEREVENTS, test "$enable_bufferevents" = "yes") +if test "$enable_bufferevents" = "yes"; then + AC_DEFINE(USE_BUFFEREVENTS, 1, [Defined if we're going to use Libevent's buffered IO API]) + if test "$enable_static_libevent" = "yes"; then + TOR_LIBEVENT_LIBS="$TOR_LIBDIR_libevent/libevent_openssl.a $TOR_LIBEVENT_LIBS" + else + TOR_LIBEVENT_LIBS="-levent_openssl $TOR_LIBEVENT_LIBS" + fi +fi +AC_SUBST(TOR_LIBEVENT_LIBS) + +dnl ------------------------------------------------------ +dnl Where do you live, libm? + +dnl On some platforms (Haiku/BeOS) the math library is +dnl part of libroot. In which case don't link against lm +TOR_LIB_MATH="" +save_LIBS="$LIBS" +AC_SEARCH_LIBS(pow, [m], , AC_MSG_ERROR([Could not find pow in libm or libc.])) +if test "$ac_cv_search_pow" != "none required"; then + TOR_LIB_MATH="$ac_cv_search_pow" +fi +LIBS="$save_LIBS" +AC_SUBST(TOR_LIB_MATH) + +dnl ------------------------------------------------------ +dnl Where do you live, openssl? And how do we call you? + +tor_openssl_pkg_redhat="openssl" +tor_openssl_pkg_debian="libssl" +tor_openssl_devpkg_redhat="openssl-devel" +tor_openssl_devpkg_debian="libssl-dev" + +ALT_openssl_WITHVAL="" +AC_ARG_WITH(ssl-dir, + [ --with-ssl-dir=PATH Obsolete alias for --with-openssl-dir ], + [ + if test "x$withval" != xno && test "x$withval" != "x" ; then + ALT_openssl_WITHVAL="$withval" + fi + ]) + +TOR_SEARCH_LIBRARY(openssl, $tryssldir, [-lssl -lcrypto $TOR_LIB_GDI], + [#include <openssl/rand.h>], + [void RAND_add(const void *buf, int num, double entropy);], + [RAND_add((void*)0,0,0); exit(0);], [], + [/usr/local/openssl /usr/lib/openssl /usr/local/ssl /usr/lib/ssl /usr/local /usr/athena /opt/openssl]) + +dnl XXXX check for OPENSSL_VERSION_NUMBER == SSLeay() + +if test "$enable_static_openssl" = "yes"; then + if test "$tor_cv_library_openssl_dir" = "(system)"; then + AC_MSG_ERROR("You must specify an explicit --with-openssl-dir=x option when using --enable-static-openssl") + else + TOR_OPENSSL_LIBS="$TOR_LIBDIR_openssl/libssl.a $TOR_LIBDIR_openssl/libcrypto.a" + fi +else + TOR_OPENSSL_LIBS="-lssl -lcrypto" +fi +AC_SUBST(TOR_OPENSSL_LIBS) + +dnl ------------------------------------------------------ +dnl Where do you live, zlib? And how do we call you? + +tor_zlib_pkg_redhat="zlib" +tor_zlib_pkg_debian="zlib1g" +tor_zlib_devpkg_redhat="zlib-devel" +tor_zlib_devpkg_debian="zlib1g-dev" + +TOR_SEARCH_LIBRARY(zlib, $tryzlibdir, [-lz], + [#include <zlib.h>], + [const char * zlibVersion(void);], + [zlibVersion(); exit(0);], [--with-zlib-dir], + [/opt/zlib]) + +if test "$enable_static_zlib" = "yes"; then + if test "$tor_cv_library_zlib_dir" = "(system)"; then + AC_MSG_ERROR("You must specify an explicit --with-zlib-dir=x option when + using --enable-static-zlib") + else + TOR_ZLIB_LIBS="$TOR_LIBDIR_zlib/libz.a" + fi +else + TOR_ZLIB_LIBS="-lz" +fi +AC_SUBST(TOR_ZLIB_LIBS) + +dnl --------------------------------------------------------------------- +dnl Now that we know about our major libraries, we can check for compiler +dnl and linker hardening options. We need to do this with the libraries known, +dnl since sometimes the linker will like an option but not be willing to +dnl use it with a build of a library. + +all_ldflags_for_check="$TOR_LDFLAGS_zlib $TOR_LDFLAGS_openssl $TOR_LDFLAGS_libevent" +all_libs_for_check="$TOR_ZLIB_LIBS $TOR_LIB_MATH $TOR_LIBEVENT_LIBS $TOR_OPENSSL_LIBS $TOR_LIB_WS32 $TOR_LIB_GDI" + +AC_COMPILE_IFELSE([AC_LANG_PROGRAM([], [ +#if !defined(__clang__) +#error +#endif])], have_clang=yes, have_clang=no) + +if test x$enable_gcc_hardening != xno; then + CFLAGS="$CFLAGS -D_FORTIFY_SOURCE=2" + if test x$have_clang = xyes; then + TOR_CHECK_CFLAGS(-Qunused-arguments) + fi + TOR_CHECK_CFLAGS(-fstack-protector-all) + TOR_CHECK_CFLAGS(-Wstack-protector) + TOR_CHECK_CFLAGS(-fwrapv) + TOR_CHECK_CFLAGS(--param ssp-buffer-size=1) + if test "$bwin32" = "false"; then + TOR_CHECK_CFLAGS(-fPIE) + TOR_CHECK_LDFLAGS(-pie, "$all_ldflags_for_check", "$all_libs_for_check") + fi +fi + +if test x$enable_linker_hardening != xno; then + TOR_CHECK_LDFLAGS(-z relro -z now, "$all_ldflags_for_check", "$all_libs_for_check") +fi + +dnl ------------------------------------------------------ +dnl Where do you live, libnatpmp? And how do we call you? +dnl There are no packages for Debian or Redhat as of this patch + +if test "$natpmp" = "true"; then + AC_DEFINE(NAT_PMP, 1, [Define to 1 if we are building with nat-pmp.]) + TOR_SEARCH_LIBRARY(libnatpmp, $trylibnatpmpdir, [-lnatpmp $TOR_LIB_WS32 $TOR_LIB_IPHLPAPI], + [#include <natpmp.h>], + [#ifdef _WIN32 + #define STATICLIB + #endif + #include <natpmp.h>], + [ int r; + natpmp_t natpmp; + natpmpresp_t response; + r = initnatpmp(&natpmp, 0, 0);], + [printf("initnatpmp() returned %d (%s)\n", r, r?"FAILED":"SUCCESS"); + exit(0);], + [--with-libnatpmp-dir], + [/usr/lib/]) +fi + + +dnl ------------------------------------------------------ +dnl Where do you live, libminiupnpc? And how do we call you? +dnl There are no packages for Debian or Redhat as of this patch + +if test "$upnp" = "true"; then + AC_DEFINE(MINIUPNPC, 1, [Define to 1 if we are building with UPnP.]) + + dnl Before we call TOR_SEARCH_LIBRARY we'll do a quick compile test + dnl to see if we have miniupnpc-1.5 or -1.6 + AC_COMPILE_IFELSE([AC_LANG_PROGRAM([#include <miniupnpc/miniupnpc.h>], + [upnpDiscover(1, 0, 0, 0);exit(0);])],[miniupnpc15="true"],[miniupnpc15="false"]) + + if test "$miniupnpc15" = "true" ; then + AC_DEFINE([MINIUPNPC15],[1],[libminiupnpc version 1.5 found]) + TOR_SEARCH_LIBRARY(libminiupnpc, $trylibminiupnpcdir, [-lminiupnpc $TOR_LIB_WS32 $TOR_LIB_IPHLPAPI], + [#include <miniupnpc/miniwget.h> + #include <miniupnpc/miniupnpc.h> + #include <miniupnpc/upnpcommands.h>], + [void upnpDiscover(int delay, const char * multicastif, + const char * minissdpdsock, int sameport);], + [upnpDiscover(1, 0, 0, 0); exit(0);], + [--with-libminiupnpc-dir], + [/usr/lib/]) + else + TOR_SEARCH_LIBRARY(libminiupnpc, $trylibminiupnpcdir, [-lminiupnpc $TOR_LIB_WS32 $TOR_LIB_IPHLPAPI], + [#include <miniupnpc/miniwget.h> + #include <miniupnpc/miniupnpc.h> + #include <miniupnpc/upnpcommands.h>], + [void upnpDiscover(int delay, const char * multicastif, + const char * minissdpdsock, int sameport, int ipv6, int * error);], + [upnpDiscover(1, 0, 0, 0, 0, 0); exit(0);], + [--with-libminiupnpc-dir], + [/usr/lib/]) + fi +fi + +dnl Make sure to enable support for large off_t if available. +AC_SYS_LARGEFILE + +AC_CHECK_HEADERS( + assert.h \ + errno.h \ + fcntl.h \ + signal.h \ + string.h \ + sys/fcntl.h \ + sys/stat.h \ + sys/time.h \ + sys/types.h \ + time.h \ + unistd.h + , , AC_MSG_WARN(Some headers were not found, compilation may fail. If compilation succeeds, please send your orconfig.h to the developers so we can fix this warning.)) + +dnl These headers are not essential + +AC_CHECK_HEADERS( + arpa/inet.h \ + crt_externs.h \ + grp.h \ + ifaddrs.h \ + inttypes.h \ + limits.h \ + linux/types.h \ + machine/limits.h \ + malloc.h \ + malloc/malloc.h \ + malloc_np.h \ + netdb.h \ + netinet/in.h \ + netinet/in6.h \ + pwd.h \ + stdint.h \ + sys/file.h \ + sys/ioctl.h \ + sys/limits.h \ + sys/mman.h \ + sys/param.h \ + sys/prctl.h \ + sys/resource.h \ + sys/socket.h \ + sys/syslimits.h \ + sys/time.h \ + sys/types.h \ + sys/un.h \ + sys/utime.h \ + sys/wait.h \ + syslog.h \ + utime.h +) + +AC_CHECK_HEADERS(sys/param.h) + +AC_CHECK_HEADERS(net/if.h, net_if_found=1, net_if_found=0, +[#ifdef HAVE_SYS_TYPES_H +#include <sys/types.h> +#endif +#ifdef HAVE_SYS_SOCKET_H +#include <sys/socket.h> +#endif]) +AC_CHECK_HEADERS(net/pfvar.h, net_pfvar_found=1, net_pfvar_found=0, +[#ifdef HAVE_SYS_TYPES_H +#include <sys/types.h> +#endif +#ifdef HAVE_SYS_SOCKET_H +#include <sys/socket.h> +#endif +#ifdef HAVE_NET_IF_H +#include <net/if.h> +#endif]) +AC_CHECK_HEADERS(linux/netfilter_ipv4.h, + linux_netfilter_ipv4=1, linux_netfilter_ipv4=0, +[#ifdef HAVE_SYS_TYPES_H +#include <sys/types.h> +#endif +#ifdef HAVE_SYS_SOCKET_H +#include <sys/socket.h> +#endif +#ifdef HAVE_LIMITS_H +#include <limits.h> +#endif +#ifdef HAVE_LINUX_TYPES_H +#include <linux/types.h> +#endif +#ifdef HAVE_NETINET_IN6_H +#include <netinet/in6.h> +#endif +#ifdef HAVE_NETINET_IN_H +#include <netinet/in.h> +#endif]) + +if test x$transparent = xtrue ; then + transparent_ok=0 + if test x$net_if_found = x1 && test x$net_pfvar_found = x1 ; then + transparent_ok=1 + fi + if test x$linux_netfilter_ipv4 = x1 ; then + transparent_ok=1 + fi + if test x$transparent_ok = x1 ; then + AC_DEFINE(USE_TRANSPARENT, 1, "Define to enable transparent proxy support") + case $host in + *-*-openbsd*) + AC_DEFINE(OPENBSD, 1, "Define to handle pf on OpenBSD properly") ;; + esac + else + AC_MSG_NOTICE([Transparent proxy support enabled, but missing headers.]) + fi +fi + +AC_CHECK_MEMBERS([struct timeval.tv_sec], , , +[#ifdef HAVE_SYS_TYPES_H +#include <sys/types.h> +#endif +#ifdef HAVE_SYS_TIME_H +#include <sys/time.h> +#endif]) + +dnl In case we aren't given a working stdint.h, we'll need to grow our own. +dnl Watch out. + +AC_CHECK_SIZEOF(int8_t) +AC_CHECK_SIZEOF(int16_t) +AC_CHECK_SIZEOF(int32_t) +AC_CHECK_SIZEOF(int64_t) +AC_CHECK_SIZEOF(uint8_t) +AC_CHECK_SIZEOF(uint16_t) +AC_CHECK_SIZEOF(uint32_t) +AC_CHECK_SIZEOF(uint64_t) +AC_CHECK_SIZEOF(intptr_t) +AC_CHECK_SIZEOF(uintptr_t) + +dnl AC_CHECK_TYPES([int8_t, int16_t, int32_t, int64_t, uint8_t, uint16_t, uint32_t, uint64_t, intptr_t, uintptr_t]) + +AC_CHECK_SIZEOF(char) +AC_CHECK_SIZEOF(short) +AC_CHECK_SIZEOF(int) +AC_CHECK_SIZEOF(long) +AC_CHECK_SIZEOF(long long) +AC_CHECK_SIZEOF(__int64) +AC_CHECK_SIZEOF(void *) +AC_CHECK_SIZEOF(time_t) +AC_CHECK_SIZEOF(size_t) + +AC_CHECK_TYPES([uint, u_char, ssize_t]) + +dnl used to include sockaddr_storage, but everybody has that. +AC_CHECK_TYPES([struct in6_addr, struct sockaddr_in6, sa_family_t], , , +[#ifdef HAVE_SYS_TYPES_H +#include <sys/types.h> +#endif +#ifdef HAVE_NETINET_IN_H +#include <netinet/in.h> +#endif +#ifdef HAVE_NETINET_IN6_H +#include <netinet/in6.h> +#endif +#ifdef HAVE_SYS_SOCKET_H +#include <sys/socket.h> +#endif +#ifdef _WIN32 +#define _WIN32_WINNT 0x0501 +#define WIN32_LEAN_AND_MEAN +#if defined(_MSC_VER) && (_MSC_VER < 1300) +#include <winsock.h> +#else +#include <winsock2.h> +#include <ws2tcpip.h> +#endif +#endif +]) +AC_CHECK_MEMBERS([struct in6_addr.s6_addr32, struct in6_addr.s6_addr16, struct sockaddr_in.sin_len, struct sockaddr_in6.sin6_len], , , +[#ifdef HAVE_SYS_TYPES_H +#include <sys/types.h> +#endif +#ifdef HAVE_NETINET_IN_H +#include <netinet/in.h> +#endif +#ifdef HAVE_NETINET_IN6_H +#include <netinet/in6.h> +#endif +#ifdef HAVE_SYS_SOCKET_H +#include <sys/socket.h> +#endif +#ifdef _WIN32 +#define _WIN32_WINNT 0x0501 +#define WIN32_LEAN_AND_MEAN +#if defined(_MSC_VER) && (_MSC_VER < 1300) +#include <winsock.h> +#else +#include <winsock2.h> +#include <ws2tcpip.h> +#endif +#endif +]) + +AC_CHECK_TYPES([rlim_t], , , +[#ifdef HAVE_SYS_TYPES_H +#include <sys/types.h> +#endif +#ifdef HAVE_SYS_TIME_H +#include <sys/time.h> +#endif +#ifdef HAVE_SYS_RESOURCE_H +#include <sys/resource.h> +#endif +]) + +AC_CACHE_CHECK([whether time_t is signed], tor_cv_time_t_signed, [ +AC_RUN_IFELSE([AC_LANG_SOURCE([ +#ifdef HAVE_SYS_TYPES_H +#include <sys/types.h> +#endif +#ifdef HAVE_SYS_TIME_H +#include <sys/time.h> +#endif +#ifdef HAVE_TIME_H +#include <time.h> +#endif +int main(int c, char**v) { if (((time_t)-1)<0) return 1; else return 0; }])], + tor_cv_time_t_signed=no, tor_cv_time_t_signed=yes, tor_cv_time_t_signed=cross) +]) + +if test "$tor_cv_time_t_signed" = cross; then + AC_MSG_NOTICE([Cross compiling: assuming that time_t is signed.]) +fi + +if test "$tor_cv_time_t_signed" != no; then + AC_DEFINE([TIME_T_IS_SIGNED], 1, + [Define to 1 iff time_t is signed]) +fi + +AC_CACHE_CHECK([whether size_t is signed], tor_cv_size_t_signed, [ +AC_RUN_IFELSE([AC_LANG_SOURCE([ +#ifdef HAVE_SYS_TYPES_H +#include <sys/types.h> +#endif +int main(int c, char**v) { if (((size_t)-1)<0) return 1; else return 0; }])], + tor_cv_size_t_signed=no, tor_cv_size_t_signed=yes, tor_cv_size_t_signed=cross) +]) + +if test "$tor_cv_size_t_signed" = cross; then + AC_MSG_NOTICE([Cross compiling: assuming that size_t is not signed.]) +fi + +if test "$tor_cv_size_t_signed" = yes; then + AC_MSG_ERROR([You have a signed size_t; that's grossly nonconformant.]) +fi + +AC_CHECK_SIZEOF(socklen_t, , [AC_INCLUDES_DEFAULT() +#ifdef HAVE_SYS_SOCKET_H +#include <sys/socket.h> +#endif +]) + +# We want to make sure that we _don't_ have a cell_t defined, like IRIX does. + +AC_CHECK_SIZEOF(cell_t) + +# Now make sure that NULL can be represented as zero bytes. +AC_CACHE_CHECK([whether memset(0) sets pointers to NULL], tor_cv_null_is_zero, +[AC_RUN_IFELSE([AC_LANG_SOURCE( +[[#include <stdlib.h> +#include <string.h> +#include <stdio.h> +#ifdef HAVE_STDDEF_H +#include <stddef.h> +#endif +int main () { char *p1,*p2; p1=NULL; memset(&p2,0,sizeof(p2)); +return memcmp(&p1,&p2,sizeof(char*))?1:0; }]])], + [tor_cv_null_is_zero=yes], + [tor_cv_null_is_zero=no], + [tor_cv_null_is_zero=cross])]) + +if test "$tor_cv_null_is_zero" = cross ; then + # Cross-compiling; let's hope that the target isn't raving mad. + AC_MSG_NOTICE([Cross-compiling: we'll assume that NULL is represented as a sequence of 0-valued bytes.]) +fi + +if test "$tor_cv_null_is_zero" != no; then + AC_DEFINE([NULL_REP_IS_ZERO_BYTES], 1, + [Define to 1 iff memset(0) sets pointers to NULL]) +fi + +# And what happens when we malloc zero? +AC_CACHE_CHECK([whether we can malloc(0) safely.], tor_cv_malloc_zero_works, +[AC_RUN_IFELSE([AC_LANG_SOURCE( +[[#include <stdlib.h> +#include <string.h> +#include <stdio.h> +#ifdef HAVE_STDDEF_H +#include <stddef.h> +#endif +int main () { return malloc(0)?0:1; }]])], + [tor_cv_malloc_zero_works=yes], + [tor_cv_malloc_zero_works=no], + [tor_cv_malloc_zero_works=cross])]) + +if test "$tor_cv_malloc_zero_works" = cross; then + # Cross-compiling; let's hope that the target isn't raving mad. + AC_MSG_NOTICE([Cross-compiling: we'll assume that we need to check malloc() arguments for 0.]) +fi + +if test "$tor_cv_malloc_zero_works" = yes; then + AC_DEFINE([MALLOC_ZERO_WORKS], 1, + [Define to 1 iff malloc(0) returns a pointer]) +fi + +# whether we seem to be in a 2s-complement world. +AC_CACHE_CHECK([whether we are using 2s-complement arithmetic], tor_cv_twos_complement, +[AC_RUN_IFELSE([AC_LANG_SOURCE( +[[int main () { int problem = ((-99) != (~99)+1); +return problem ? 1 : 0; }]])], + [tor_cv_twos_complement=yes], + [tor_cv_twos_complement=no], + [tor_cv_twos_complement=cross])]) + +if test "$tor_cv_twos_complement" = cross ; then + # Cross-compiling; let's hope that the target isn't raving mad. + AC_MSG_NOTICE([Cross-compiling: we'll assume that negative integers are represented with two's complement.]) +fi + +if test "$tor_cv_twos_complement" != no ; then + AC_DEFINE([USING_TWOS_COMPLEMENT], 1, + [Define to 1 iff we represent negative integers with two's complement]) +fi + +# What does shifting a negative value do? +AC_CACHE_CHECK([whether right-shift on negative values does sign-extension], tor_cv_sign_extend, +[AC_RUN_IFELSE([AC_LANG_SOURCE( +[[int main () { int okay = (-60 >> 8) == -1; return okay ? 0 : 1; }]])], + [tor_cv_sign_extend=yes], + [tor_cv_sign_extend=no], + [tor_cv_sign_extend=cross])]) + +if test "$tor_cv_sign_extend" = cross ; then + # Cross-compiling; let's hope that the target isn't raving mad. + AC_MSG_NOTICE([Cross-compiling: we'll assume that right-shifting negative integers causes sign-extension]) +fi + +if test "$tor_cv_sign_extend" != no ; then + AC_DEFINE([RSHIFT_DOES_SIGN_EXTEND], 1, + [Define to 1 iff right-shifting a negative value performs sign-extension]) +fi + +# Whether we should use the dmalloc memory allocation debugging library. +AC_MSG_CHECKING(whether to use dmalloc (debug memory allocation library)) +AC_ARG_WITH(dmalloc, +[ --with-dmalloc Use debug memory allocation library. ], +[if [[ "$withval" = "yes" ]]; then + dmalloc=1 + AC_MSG_RESULT(yes) +else + dmalloc=1 + AC_MSG_RESULT(no) +fi], [ dmalloc=0; AC_MSG_RESULT(no) ] +) + +if [[ $dmalloc -eq 1 ]]; then + AC_CHECK_HEADERS(dmalloc.h, , AC_MSG_ERROR(dmalloc header file not found. Do you have the development files for dmalloc installed?)) + AC_SEARCH_LIBS(dmalloc_malloc, [dmallocth dmalloc], , AC_MSG_ERROR(Libdmalloc library not found. If you enable it you better have it installed.)) + AC_DEFINE(USE_DMALLOC, 1, [Debug memory allocation library]) + AC_DEFINE(DMALLOC_FUNC_CHECK, 1, [Enable dmalloc's malloc function check]) + AC_CHECK_FUNCS(dmalloc_strdup dmalloc_strndup) +fi + +AC_ARG_WITH(tcmalloc, +[ --with-tcmalloc Use tcmalloc memory allocation library. ], +[ tcmalloc=yes ], [ tcmalloc=no ]) + +if test x$tcmalloc = xyes ; then + LDFLAGS="-ltcmalloc $LDFLAGS" +fi + +using_custom_malloc=no +if test x$enable_openbsd_malloc = xyes ; then + using_custom_malloc=yes +fi +if test x$tcmalloc = xyes ; then + using_custom_malloc=yes +fi +if test $using_custom_malloc = no ; then + AC_CHECK_FUNCS(mallinfo) +fi + +# By default, we're going to assume we don't have mlockall() +# bionic and other platforms have various broken mlockall subsystems. +# Some systems don't have a working mlockall, some aren't linkable, +# and some have it but don't declare it. +AC_CHECK_FUNCS(mlockall) +AC_CHECK_DECLS([mlockall], , , [ +#ifdef HAVE_SYS_MMAN_H +#include <sys/mman.h> +#endif]) + +# Allow user to specify an alternate syslog facility +AC_ARG_WITH(syslog-facility, +[ --with-syslog-facility=LOG syslog facility to use (default=LOG_DAEMON)], +syslog_facility="$withval", syslog_facility="LOG_DAEMON") +AC_DEFINE_UNQUOTED(LOGFACILITY,$syslog_facility,[name of the syslog facility]) +AC_SUBST(LOGFACILITY) + +# Check if we have getresuid and getresgid +AC_CHECK_FUNCS(getresuid getresgid) + +# Check for gethostbyname_r in all its glorious incompatible versions. +# (This logic is based on that in Python's configure.in) +AH_TEMPLATE(HAVE_GETHOSTBYNAME_R, + [Define this if you have any gethostbyname_r()]) + +AC_CHECK_FUNC(gethostbyname_r, [ + AC_MSG_CHECKING([how many arguments gethostbyname_r() wants]) + OLD_CFLAGS=$CFLAGS + CFLAGS="$CFLAGS $MY_CPPFLAGS $MY_THREAD_CPPFLAGS $MY_CFLAGS" + AC_COMPILE_IFELSE([AC_LANG_PROGRAM([ +#include <netdb.h> + ], [[ + char *cp1, *cp2; + struct hostent *h1, *h2; + int i1, i2; + (void)gethostbyname_r(cp1,h1,cp2,i1,&h2,&i2); + ]])],[ + AC_DEFINE(HAVE_GETHOSTBYNAME_R) + AC_DEFINE(HAVE_GETHOSTBYNAME_R_6_ARG, 1, + [Define this if gethostbyname_r takes 6 arguments]) + AC_MSG_RESULT(6) + ], [ + AC_TRY_COMPILE([ +#include <netdb.h> + ], [ + char *cp1, *cp2; + struct hostent *h1; + int i1, i2; + (void)gethostbyname_r(cp1,h1,cp2,i1,&i2); + ], [ + AC_DEFINE(HAVE_GETHOSTBYNAME_R) + AC_DEFINE(HAVE_GETHOSTBYNAME_R_5_ARG, 1, + [Define this if gethostbyname_r takes 5 arguments]) + AC_MSG_RESULT(5) + ], [ + AC_TRY_COMPILE([ +#include <netdb.h> + ], [ + char *cp1; + struct hostent *h1; + struct hostent_data hd; + (void) gethostbyname_r(cp1,h1,&hd); + ], [ + AC_DEFINE(HAVE_GETHOSTBYNAME_R) + AC_DEFINE(HAVE_GETHOSTBYNAME_R_3_ARG, 1, + [Define this if gethostbyname_r takes 3 arguments]) + AC_MSG_RESULT(3) + ], [ + AC_MSG_RESULT(0) + ]) + ]) + ]) + CFLAGS=$OLD_CFLAGS +]) + +AC_CACHE_CHECK([whether the C compiler supports __func__], + tor_cv_have_func_macro, + AC_COMPILE_IFELSE([AC_LANG_SOURCE([ +#include <stdio.h> +int main(int c, char **v) { puts(__func__); }])], + tor_cv_have_func_macro=yes, + tor_cv_have_func_macro=no)) + +AC_CACHE_CHECK([whether the C compiler supports __FUNC__], + tor_cv_have_FUNC_macro, + AC_COMPILE_IFELSE([AC_LANG_SOURCE([ +#include <stdio.h> +int main(int c, char **v) { puts(__FUNC__); }])], + tor_cv_have_FUNC_macro=yes, + tor_cv_have_FUNC_macro=no)) + +AC_CACHE_CHECK([whether the C compiler supports __FUNCTION__], + tor_cv_have_FUNCTION_macro, + AC_COMPILE_IFELSE([AC_LANG_SOURCE([ +#include <stdio.h> +int main(int c, char **v) { puts(__FUNCTION__); }])], + tor_cv_have_FUNCTION_macro=yes, + tor_cv_have_FUNCTION_macro=no)) + +AC_CACHE_CHECK([whether we have extern char **environ already declared], + tor_cv_have_environ_declared, + AC_COMPILE_IFELSE([AC_LANG_SOURCE([ +/* We define _GNU_SOURCE here because it is also defined in compat.c. + * Without it environ doesn't get declared. */ +#define _GNU_SOURCE +#ifdef HAVE_UNISTD_H +#include <unistd.h> +#endif +#include <stdlib.h> +int main(int c, char **v) { char **t = environ; }])], + tor_cv_have_environ_declared=yes, + tor_cv_have_environ_declared=no)) + +if test "$tor_cv_have_func_macro" = 'yes'; then + AC_DEFINE(HAVE_MACRO__func__, 1, [Defined if the compiler supports __func__]) +fi + +if test "$tor_cv_have_FUNC_macro" = 'yes'; then + AC_DEFINE(HAVE_MACRO__FUNC__, 1, [Defined if the compiler supports __FUNC__]) +fi + +if test "$tor_cv_have_FUNCTION_macro" = 'yes'; then + AC_DEFINE(HAVE_MACRO__FUNCTION__, 1, + [Defined if the compiler supports __FUNCTION__]) +fi + +if test "$tor_cv_have_environ_declared" = 'yes'; then + AC_DEFINE(HAVE_EXTERN_ENVIRON_DECLARED, 1, + [Defined if we have extern char **environ already declared]) +fi + +# $prefix stores the value of the --prefix command line option, or +# NONE if the option wasn't set. In the case that it wasn't set, make +# it be the default, so that we can use it to expand directories now. +if test "x$prefix" = "xNONE"; then + prefix=$ac_default_prefix +fi + +# and similarly for $exec_prefix +if test "x$exec_prefix" = "xNONE"; then + exec_prefix=$prefix +fi + +if test "x$BUILDDIR" = "x"; then + BUILDDIR=`pwd` +fi +AC_SUBST(BUILDDIR) +AH_TEMPLATE([BUILDDIR],[tor's build directory]) +AC_DEFINE_UNQUOTED(BUILDDIR,"$BUILDDIR") + +if test "x$CONFDIR" = "x"; then + CONFDIR=`eval echo $sysconfdir/tor` +fi +AC_SUBST(CONFDIR) +AH_TEMPLATE([CONFDIR],[tor's configuration directory]) +AC_DEFINE_UNQUOTED(CONFDIR,"$CONFDIR") + +BINDIR=`eval echo $bindir` +AC_SUBST(BINDIR) +LOCALSTATEDIR=`eval echo $localstatedir` +AC_SUBST(LOCALSTATEDIR) + +if test "$bwin32" = true; then + # Test if the linker supports the --nxcompat and --dynamicbase options + # for Windows + save_LDFLAGS="$LDFLAGS" + LDFLAGS="-Wl,--nxcompat -Wl,--dynamicbase" + AC_MSG_CHECKING([whether the linker supports DllCharacteristics]) + AC_LINK_IFELSE([AC_LANG_PROGRAM([])], + [AC_MSG_RESULT([yes])] + [save_LDFLAGS="$save_LDFLAGS $LDFLAGS"], + [AC_MSG_RESULT([no])] + ) + LDFLAGS="$save_LDFLAGS" +fi + +# Set CFLAGS _after_ all the above checks, since our warnings are stricter +# than autoconf's macros like. +if test "$GCC" = yes; then + # Disable GCC's strict aliasing checks. They are an hours-to-debug + # accident waiting to happen. + CFLAGS="$CFLAGS -Wall -fno-strict-aliasing" +else + # Autoconf sets -g -O2 by default. Override optimization level + # for non-gcc compilers + CFLAGS="$CFLAGS -O" + enable_gcc_warnings=no + enable_gcc_warnings_advisory=no +fi + +# OS X Lion started deprecating the system openssl. Let's just disable +# all deprecation warnings on OS X. Also, to potentially make the binary +# a little smaller, let's enable dead_strip. +case "$host_os" in + + darwin*) + CFLAGS="$CFLAGS -Wno-deprecated-declarations" + LDFLAGS="$LDFLAGS -dead_strip" ;; +esac + +# Add some more warnings which we use in development but not in the +# released versions. (Some relevant gcc versions can't handle these.) +if test x$enable_gcc_warnings = xyes || test x$enable_gcc_warnings_advisory = xyes; then + + AC_COMPILE_IFELSE([AC_LANG_PROGRAM([], [ +#if !defined(__GNUC__) || (__GNUC__ < 4) +#error +#endif])], have_gcc4=yes, have_gcc4=no) + + AC_COMPILE_IFELSE([AC_LANG_PROGRAM([], [ +#if !defined(__GNUC__) || (__GNUC__ < 4) || (__GNUC__ == 4 && __GNUC_MINOR__ < 2) +#error +#endif])], have_gcc42=yes, have_gcc42=no) + + AC_COMPILE_IFELSE([AC_LANG_PROGRAM([], [ +#if !defined(__GNUC__) || (__GNUC__ < 4) || (__GNUC__ == 4 && __GNUC_MINOR__ < 3) +#error +#endif])], have_gcc43=yes, have_gcc43=no) + + save_CFLAGS="$CFLAGS" + CFLAGS="$CFLAGS -Wshorten-64-to-32" + AC_COMPILE_IFELSE([AC_LANG_PROGRAM([], [])], have_shorten64_flag=yes, + have_shorten64_flag=no) + CFLAGS="$save_CFLAGS" + + case $host in + *-*-openbsd*) + # Some OpenBSD versions (like 4.8) have -Wsystem-headers by default. + # That's fine, except that the headers don't pass -Wredundant-decls. + # Therefore, let's disable -Wsystem-headers when we're building + # with maximal warnings on OpenBSD. + CFLAGS="$CFLAGS -Wno-system-headers" ;; + esac + + CFLAGS="$CFLAGS -W -Wfloat-equal -Wundef -Wpointer-arith" + CFLAGS="$CFLAGS -Wstrict-prototypes -Wmissing-prototypes -Wwrite-strings" + CFLAGS="$CFLAGS -Wredundant-decls -Wchar-subscripts -Wcomment -Wformat=2" + CFLAGS="$CFLAGS -Wwrite-strings -Wmissing-declarations -Wredundant-decls" + CFLAGS="$CFLAGS -Wnested-externs -Wbad-function-cast -Wswitch-enum" + + if test x$enable_gcc_warnings = xyes; then + CFLAGS="$CFLAGS -Werror" + fi + + # Disabled, so we can use mallinfo(): -Waggregate-return + + if test x$have_gcc4 = xyes ; then + # These warnings break gcc 3.3.5 and work on gcc 4.0.2 + CFLAGS="$CFLAGS -Winit-self -Wmissing-field-initializers -Wdeclaration-after-statement -Wold-style-definition" + fi + + if test x$have_gcc42 = xyes ; then + # These warnings break gcc 4.0.2 and work on gcc 4.2 + # XXXX020 See if any of these work with earlier versions. + CFLAGS="$CFLAGS -Waddress -Wmissing-noreturn -Wstrict-overflow=1" + + # We used to use -Wstrict-overflow=5, but that breaks us heavily under 4.3. + fi + + if test x$have_gcc42 = xyes && test x$have_clang = xno; then + # These warnings break gcc 4.0.2 and clang, but work on gcc 4.2 + CFLAGS="$CFLAGS -Wnormalized=id -Woverride-init" + fi + + if test x$have_gcc43 = xyes ; then + # These warnings break gcc 4.2 and work on gcc 4.3 + # XXXX020 See if any of these work with earlier versions. + CFLAGS="$CFLAGS -Wextra -Warray-bounds" + fi + + if test x$have_shorten64_flag = xyes ; then + CFLAGS="$CFLAGS -Wshorten-64-to-32" + fi + +##This will break the world on some 64-bit architectures +# CFLAGS="$CFLAGS -Winline" +fi + + + +CPPFLAGS="$CPPFLAGS $TOR_CPPFLAGS_libevent $TOR_CPPFLAGS_openssl $TOR_CPPFLAGS_zlib" + +AC_CONFIG_FILES([ + Doxyfile + Makefile + contrib/suse/tor.sh + contrib/tor.logrotate + contrib/tor.sh + contrib/torctl + contrib/torify + src/config/torrc.sample +]) + +AC_OUTPUT + +if test -x /usr/bin/perl && test -x ./contrib/updateVersions.pl ; then + ./contrib/updateVersions.pl +fi

1 0