November 2017 - tor-commits - lists.torproject.org

[tor/release-0.3.2] Replace our random-exponential-delay algorithm.
by nickm＠torproject.org 08 Nov '17

08 Nov '17

commit cb29687e93169e9615de3bc5adcbf6d31551b32c Author: Nick Mathewson <nickm(a)torproject.org> Date: Tue Oct 17 13:24:40 2017 -0400 Replace our random-exponential-delay algorithm. This patch has implementations of the "decorrelated" and "full" algorithms from https://www.awsarchitectureblog.com/2015/03/backoff.html --- changes/bug23816 | 6 +++++ src/or/directory.c | 77 ++++++++++++++++++++++++++++++++--------------------- src/or/directory.h | 10 +++++-- src/test/test_dir.c | 42 ++++++++++++++++++++++++++--- 4 files changed, 98 insertions(+), 37 deletions(-) diff --git a/changes/bug23816 b/changes/bug23816 new file mode 100644 index 000000000..6139dec9e --- /dev/null +++ b/changes/bug23816 @@ -0,0 +1,6 @@ + o Minor bugfixes (directory client): + - On failure to download directory information, delay retry attempts + by a random amount based on the "decorrelated jitter" algorithm. + Our previous delay algorithm tended to produce extra-long delays too + easily. Fixes bug 23816; bugfix on 0.2.9.1-alpha. + diff --git a/src/or/directory.c b/src/or/directory.c index fce48c6e9..758a29b05 100644 --- a/src/or/directory.c +++ b/src/or/directory.c @@ -3776,53 +3776,68 @@ find_dl_min_and_max_delay(download_status_t *dls, const or_options_t *options, *max = INT_MAX; } -/** Advance one delay step. The algorithm is to use the previous delay to - * compute an increment, we construct a value uniformly at random between - * delay and MAX(delay*2,delay+1). We then clamp that value to be no larger - * than max_delay, and return it. +/** As next_random_exponential_delay() below, but does not compute a random + * value. Instead, compute the range of values that + * next_random_exponential_delay() should use when computing its random value. + * Store the low bound into *low_bound_out, and the high bound into + * *high_bound_out. Guarantees that the low bound is strictly less + * than the high bound. */ +STATIC void +next_random_exponential_delay_range(int *low_bound_out, + int *high_bound_out, + int delay, + int base_delay) +{ + // This is the "decorrelated jitter" approach, from + // https://www.awsarchitectureblog.com/2015/03/backoff.html + // The formula is + // sleep = min(cap, random_between(base, sleep * 3)) + + const int delay_times_3 = delay < INT_MAX/3 ? delay * 3 : INT_MAX; + *low_bound_out = base_delay; + if (delay_times_3 > base_delay) { + *high_bound_out = delay_times_3; + } else { + *high_bound_out = base_delay+1; + } +} + +/** Advance one delay step. The algorithm will generate a random delay, + * such that each failure is possibly (random) longer than the ones before. + * + * We then clamp that value to be no larger than max_delay, and return it. + * + * The base_delay parameter is lowest possible delay time (can't be + * zero); the backoff_position parameter is the number of times we've + * generated a delay; and the delay argument is the most recently used + * delay. * * Requires that delay is less than INT_MAX, and delay is in [0,max_delay]. */ STATIC int -next_random_exponential_delay(int delay, int max_delay) +next_random_exponential_delay(int delay, + int base_delay, + int max_delay) { /* Check preconditions */ if (BUG(max_delay < 0)) max_delay = 0; if (BUG(delay > max_delay)) delay = max_delay; - if (delay == INT_MAX) - return INT_MAX; /* prevent overflow */ if (BUG(delay < 0)) delay = 0; - /* How much are we willing to add to the delay? */ - int max_increment; - int multiplier = 3; /* no more than quadruple the previous delay */ - if (get_options()->TestingTorNetwork) { - /* Decrease the multiplier in testing networks. This reduces the variance, - * so that bootstrap is more reliable. */ - multiplier = 2; /* no more than triple the previous delay */ - } + if (base_delay < 1) + base_delay = 1; - if (delay && delay < (INT_MAX-1) / multiplier) { - max_increment = delay * multiplier; - } else if (delay) { - max_increment = INT_MAX-1; - } else { - max_increment = 1; - } + int low_bound=0, high_bound=max_delay; - if (BUG(max_increment < 1)) - max_increment = 1; + next_random_exponential_delay_range(&low_bound, &high_bound, + delay, base_delay); - /* the + 1 here is so that we always wait longer than last time. */ - int increment = crypto_rand_int(max_increment)+1; + int rand_delay = crypto_rand_int_range(low_bound, high_bound); - if (increment < max_delay - delay) - return delay + increment; - else - return max_delay; + return MIN(rand_delay, max_delay); } /** Find the current delay for dls based on schedule or min_delay/ @@ -3871,7 +3886,7 @@ download_status_schedule_get_delay(download_status_t *dls, while (dls->last_backoff_position < dls_schedule_position) { /* Do one increment step */ - delay = next_random_exponential_delay(delay, max_delay); + delay = next_random_exponential_delay(delay, min_delay, max_delay); /* Update our position */ ++(dls->last_backoff_position); } diff --git a/src/or/directory.h b/src/or/directory.h index 629b3ead9..c055e60d9 100644 --- a/src/or/directory.h +++ b/src/or/directory.h @@ -167,8 +167,14 @@ STATIC const smartlist_t *find_dl_schedule(download_status_t *dls, STATIC void find_dl_min_and_max_delay(download_status_t *dls, const or_options_t *options, int *min, int *max); -STATIC int next_random_exponential_delay(int delay, int max_delay); - +STATIC int next_random_exponential_delay(int delay, + int base_delay, + int max_delay); + +STATIC void next_random_exponential_delay_range(int *low_bound_out, + int *high_bound_out, + int delay, + int base_delay); #endif #endif diff --git a/src/test/test_dir.c b/src/test/test_dir.c index cdc56acb8..1c6662147 100644 --- a/src/test/test_dir.c +++ b/src/test/test_dir.c @@ -3617,6 +3617,7 @@ test_dir_download_status_random_backoff(void *arg) /* Check the random backoff cases */ old_increment = 0; + int n_attempts = 0; do { increment = download_status_schedule_get_delay(&dls_random, NULL, @@ -3625,9 +3626,9 @@ test_dir_download_status_random_backoff(void *arg) /* Test */ tt_int_op(increment, OP_GE, min_delay); tt_int_op(increment, OP_LE, max_delay); - tt_int_op(increment, OP_GE, old_increment); - /* We at most quadruple, and maybe add one */ - tt_int_op(increment, OP_LE, 4 * old_increment + 1); + + if (old_increment) + tt_int_op(increment, OP_LE, old_increment * 3); /* Advance */ current_time += increment; @@ -3636,13 +3637,45 @@ test_dir_download_status_random_backoff(void *arg) /* Try another maybe */ old_increment = increment; - } while (increment < max_delay); + } while (increment < max_delay && ++n_attempts < 1000); done: return; } static void +test_dir_download_status_random_backoff_ranges(void *arg) +{ + (void)arg; + int lo, hi; + next_random_exponential_delay_range(&lo, &hi, 0, 10); + tt_int_op(lo, OP_EQ, 10); + tt_int_op(hi, OP_EQ, 11); + + next_random_exponential_delay_range(&lo, &hi, 6, 10); + tt_int_op(lo, OP_EQ, 10); + tt_int_op(hi, OP_EQ, 6*3); + + next_random_exponential_delay_range(&lo, &hi, 13, 10); + tt_int_op(lo, OP_EQ, 10); + tt_int_op(hi, OP_EQ, 13 * 3); + + next_random_exponential_delay_range(&lo, &hi, 37, 10); + tt_int_op(lo, OP_EQ, 10); + tt_int_op(hi, OP_EQ, 111); + + next_random_exponential_delay_range(&lo, &hi, 123, 10); + tt_int_op(lo, OP_EQ, 10); + tt_int_op(hi, OP_EQ, 369); + + next_random_exponential_delay_range(&lo, &hi, INT_MAX-5, 10); + tt_int_op(lo, OP_EQ, 10); + tt_int_op(hi, OP_EQ, INT_MAX); + done: + ; +} + +static void test_dir_download_status_increment(void *arg) { (void)arg; @@ -5475,6 +5508,7 @@ struct testcase_t dir_tests[] = { DIR(packages, 0), DIR(download_status_schedule, 0), DIR(download_status_random_backoff, 0), + DIR(download_status_random_backoff_ranges, 0), DIR(download_status_increment, 0), DIR(authdir_type_to_string, 0), DIR(conn_purpose_to_string, 0),

1 0

[tor/maint-0.3.2] Replace our random-exponential-delay algorithm.
by nickm＠torproject.org 08 Nov '17

08 Nov '17

commit cb29687e93169e9615de3bc5adcbf6d31551b32c Author: Nick Mathewson <nickm(a)torproject.org> Date: Tue Oct 17 13:24:40 2017 -0400 Replace our random-exponential-delay algorithm. This patch has implementations of the "decorrelated" and "full" algorithms from https://www.awsarchitectureblog.com/2015/03/backoff.html --- changes/bug23816 | 6 +++++ src/or/directory.c | 77 ++++++++++++++++++++++++++++++++--------------------- src/or/directory.h | 10 +++++-- src/test/test_dir.c | 42 ++++++++++++++++++++++++++--- 4 files changed, 98 insertions(+), 37 deletions(-) diff --git a/changes/bug23816 b/changes/bug23816 new file mode 100644 index 000000000..6139dec9e --- /dev/null +++ b/changes/bug23816 @@ -0,0 +1,6 @@ + o Minor bugfixes (directory client): + - On failure to download directory information, delay retry attempts + by a random amount based on the "decorrelated jitter" algorithm. + Our previous delay algorithm tended to produce extra-long delays too + easily. Fixes bug 23816; bugfix on 0.2.9.1-alpha. + diff --git a/src/or/directory.c b/src/or/directory.c index fce48c6e9..758a29b05 100644 --- a/src/or/directory.c +++ b/src/or/directory.c @@ -3776,53 +3776,68 @@ find_dl_min_and_max_delay(download_status_t *dls, const or_options_t *options, *max = INT_MAX; } -/** Advance one delay step. The algorithm is to use the previous delay to - * compute an increment, we construct a value uniformly at random between - * delay and MAX(delay*2,delay+1). We then clamp that value to be no larger - * than max_delay, and return it. +/** As next_random_exponential_delay() below, but does not compute a random + * value. Instead, compute the range of values that + * next_random_exponential_delay() should use when computing its random value. + * Store the low bound into *low_bound_out, and the high bound into + * *high_bound_out. Guarantees that the low bound is strictly less + * than the high bound. */ +STATIC void +next_random_exponential_delay_range(int *low_bound_out, + int *high_bound_out, + int delay, + int base_delay) +{ + // This is the "decorrelated jitter" approach, from + // https://www.awsarchitectureblog.com/2015/03/backoff.html + // The formula is + // sleep = min(cap, random_between(base, sleep * 3)) + + const int delay_times_3 = delay < INT_MAX/3 ? delay * 3 : INT_MAX; + *low_bound_out = base_delay; + if (delay_times_3 > base_delay) { + *high_bound_out = delay_times_3; + } else { + *high_bound_out = base_delay+1; + } +} + +/** Advance one delay step. The algorithm will generate a random delay, + * such that each failure is possibly (random) longer than the ones before. + * + * We then clamp that value to be no larger than max_delay, and return it. + * + * The base_delay parameter is lowest possible delay time (can't be + * zero); the backoff_position parameter is the number of times we've + * generated a delay; and the delay argument is the most recently used + * delay. * * Requires that delay is less than INT_MAX, and delay is in [0,max_delay]. */ STATIC int -next_random_exponential_delay(int delay, int max_delay) +next_random_exponential_delay(int delay, + int base_delay, + int max_delay) { /* Check preconditions */ if (BUG(max_delay < 0)) max_delay = 0; if (BUG(delay > max_delay)) delay = max_delay; - if (delay == INT_MAX) - return INT_MAX; /* prevent overflow */ if (BUG(delay < 0)) delay = 0; - /* How much are we willing to add to the delay? */ - int max_increment; - int multiplier = 3; /* no more than quadruple the previous delay */ - if (get_options()->TestingTorNetwork) { - /* Decrease the multiplier in testing networks. This reduces the variance, - * so that bootstrap is more reliable. */ - multiplier = 2; /* no more than triple the previous delay */ - } + if (base_delay < 1) + base_delay = 1; - if (delay && delay < (INT_MAX-1) / multiplier) { - max_increment = delay * multiplier; - } else if (delay) { - max_increment = INT_MAX-1; - } else { - max_increment = 1; - } + int low_bound=0, high_bound=max_delay; - if (BUG(max_increment < 1)) - max_increment = 1; + next_random_exponential_delay_range(&low_bound, &high_bound, + delay, base_delay); - /* the + 1 here is so that we always wait longer than last time. */ - int increment = crypto_rand_int(max_increment)+1; + int rand_delay = crypto_rand_int_range(low_bound, high_bound); - if (increment < max_delay - delay) - return delay + increment; - else - return max_delay; + return MIN(rand_delay, max_delay); } /** Find the current delay for dls based on schedule or min_delay/ @@ -3871,7 +3886,7 @@ download_status_schedule_get_delay(download_status_t *dls, while (dls->last_backoff_position < dls_schedule_position) { /* Do one increment step */ - delay = next_random_exponential_delay(delay, max_delay); + delay = next_random_exponential_delay(delay, min_delay, max_delay); /* Update our position */ ++(dls->last_backoff_position); } diff --git a/src/or/directory.h b/src/or/directory.h index 629b3ead9..c055e60d9 100644 --- a/src/or/directory.h +++ b/src/or/directory.h @@ -167,8 +167,14 @@ STATIC const smartlist_t *find_dl_schedule(download_status_t *dls, STATIC void find_dl_min_and_max_delay(download_status_t *dls, const or_options_t *options, int *min, int *max); -STATIC int next_random_exponential_delay(int delay, int max_delay); - +STATIC int next_random_exponential_delay(int delay, + int base_delay, + int max_delay); + +STATIC void next_random_exponential_delay_range(int *low_bound_out, + int *high_bound_out, + int delay, + int base_delay); #endif #endif diff --git a/src/test/test_dir.c b/src/test/test_dir.c index cdc56acb8..1c6662147 100644 --- a/src/test/test_dir.c +++ b/src/test/test_dir.c @@ -3617,6 +3617,7 @@ test_dir_download_status_random_backoff(void *arg) /* Check the random backoff cases */ old_increment = 0; + int n_attempts = 0; do { increment = download_status_schedule_get_delay(&dls_random, NULL, @@ -3625,9 +3626,9 @@ test_dir_download_status_random_backoff(void *arg) /* Test */ tt_int_op(increment, OP_GE, min_delay); tt_int_op(increment, OP_LE, max_delay); - tt_int_op(increment, OP_GE, old_increment); - /* We at most quadruple, and maybe add one */ - tt_int_op(increment, OP_LE, 4 * old_increment + 1); + + if (old_increment) + tt_int_op(increment, OP_LE, old_increment * 3); /* Advance */ current_time += increment; @@ -3636,13 +3637,45 @@ test_dir_download_status_random_backoff(void *arg) /* Try another maybe */ old_increment = increment; - } while (increment < max_delay); + } while (increment < max_delay && ++n_attempts < 1000); done: return; } static void +test_dir_download_status_random_backoff_ranges(void *arg) +{ + (void)arg; + int lo, hi; + next_random_exponential_delay_range(&lo, &hi, 0, 10); + tt_int_op(lo, OP_EQ, 10); + tt_int_op(hi, OP_EQ, 11); + + next_random_exponential_delay_range(&lo, &hi, 6, 10); + tt_int_op(lo, OP_EQ, 10); + tt_int_op(hi, OP_EQ, 6*3); + + next_random_exponential_delay_range(&lo, &hi, 13, 10); + tt_int_op(lo, OP_EQ, 10); + tt_int_op(hi, OP_EQ, 13 * 3); + + next_random_exponential_delay_range(&lo, &hi, 37, 10); + tt_int_op(lo, OP_EQ, 10); + tt_int_op(hi, OP_EQ, 111); + + next_random_exponential_delay_range(&lo, &hi, 123, 10); + tt_int_op(lo, OP_EQ, 10); + tt_int_op(hi, OP_EQ, 369); + + next_random_exponential_delay_range(&lo, &hi, INT_MAX-5, 10); + tt_int_op(lo, OP_EQ, 10); + tt_int_op(hi, OP_EQ, INT_MAX); + done: + ; +} + +static void test_dir_download_status_increment(void *arg) { (void)arg; @@ -5475,6 +5508,7 @@ struct testcase_t dir_tests[] = { DIR(packages, 0), DIR(download_status_schedule, 0), DIR(download_status_random_backoff, 0), + DIR(download_status_random_backoff_ranges, 0), DIR(download_status_increment, 0), DIR(authdir_type_to_string, 0), DIR(conn_purpose_to_string, 0),

1 0

[tor/master] Merge branch 'maint-0.3.2'
by nickm＠torproject.org 08 Nov '17

08 Nov '17

commit c2c1fa6b95dacbfd4b128c40032286d798aa5893 Merge: b780e84f2 e5a83062e Author: Nick Mathewson <nickm(a)torproject.org> Date: Wed Nov 8 08:13:14 2017 -0500 Merge branch 'maint-0.3.2' changes/bug23816 | 6 +++++ src/or/directory.c | 76 +++++++++++++++++++++++++++++++---------------------- src/or/directory.h | 10 ++++++- src/test/test_dir.c | 69 +++++++++++++++++++++++++++--------------------- 4 files changed, 99 insertions(+), 62 deletions(-)

1 0

[tor/maint-0.3.2] Merge branch 'bug23816_029_squashed' into maint-0.3.2
by nickm＠torproject.org 08 Nov '17

08 Nov '17

commit e5a83062ed4e9e6b908efc6b75f13ab269f97377 Merge: 3dc61a5d7 cb29687e9 Author: Nick Mathewson <nickm(a)torproject.org> Date: Wed Nov 8 08:11:22 2017 -0500 Merge branch 'bug23816_029_squashed' into maint-0.3.2 changes/bug23816 | 6 +++++ src/or/directory.c | 76 +++++++++++++++++++++++++++++++---------------------- src/or/directory.h | 10 ++++++- src/test/test_dir.c | 69 +++++++++++++++++++++++++++--------------------- 4 files changed, 99 insertions(+), 62 deletions(-) diff --cc src/or/directory.h index 79984be32,c055e60d9..d26d83537 --- a/src/or/directory.h +++ b/src/or/directory.h @@@ -226,23 -167,15 +226,31 @@@ STATIC const smartlist_t *find_dl_sched STATIC void find_dl_min_and_max_delay(download_status_t *dls, const or_options_t *options, int *min, int *max); - STATIC int next_random_exponential_delay(int delay, int max_delay); ++ + STATIC int next_random_exponential_delay(int delay, + int base_delay, + int max_delay); + + STATIC void next_random_exponential_delay_range(int *low_bound_out, + int *high_bound_out, + int delay, + int base_delay); -#endif -#endif +STATIC int parse_hs_version_from_post(const char *url, const char *prefix, + const char **end_pos); + +STATIC unsigned parse_accept_encoding_header(const char *h); +#endif /* defined(TOR_UNIT_TESTS) */ + +#if defined(TOR_UNIT_TESTS) || defined(DIRECTORY_PRIVATE) +/* Used only by directory.c and test_dir.c */ + +/* no more than quadruple the previous delay (multiplier + 1) */ +#define DIR_DEFAULT_RANDOM_MULTIPLIER (3) +/* no more than triple the previous delay */ +#define DIR_TEST_NET_RANDOM_MULTIPLIER (2) + +#endif /* defined(TOR_UNIT_TESTS) || defined(DIRECTORY_PRIVATE) */ + +#endif /* !defined(TOR_DIRECTORY_H) */ diff --cc src/test/test_dir.c index 87b86c38b,1c6662147..ee4a9780b --- a/src/test/test_dir.c +++ b/src/test/test_dir.c @@@ -4124,11 -3608,16 +4124,11 @@@ download_status_random_backoff_helper(i { 0, 0, 0, DL_SCHED_GENERIC, DL_WANT_AUTHORITY, DL_SCHED_INCREMENT_FAILURE, DL_SCHED_RANDOM_EXPONENTIAL, 0, 0 }; int increment = -1; - int old_increment; + int old_increment = -1; time_t current_time = time(NULL); - const int exponent = DIR_DEFAULT_RANDOM_MULTIPLIER + 1; - const int min_delay = 0; - const int max_delay = 1000000; - - (void)arg; /* Check the random backoff cases */ - old_increment = 0; + int n_attempts = 0; do { increment = download_status_schedule_get_delay(&dls_random, NULL, @@@ -4148,33 -3626,14 +4148,12 @@@ /* Test */ tt_int_op(increment, OP_GE, min_delay); tt_int_op(increment, OP_LE, max_delay); - if (dls_random.last_backoff_position == 0) { - /* regression tests for 17750 - * Always use the minimum delay for the first increment */ - tt_int_op(increment, OP_EQ, min_delay); - } else { - /* It's times like these I'd love a good saturating arithmetic - * implementation */ - int min_inc = INT_MAX; - if (old_increment <= INT_MAX - 1) { - min_inc = old_increment + 1; - } - - int max_inc = INT_MAX; - if (old_increment <= (INT_MAX - 1)/exponent) { - max_inc = (exponent * old_increment) + 1; - } - - /* Regression test for 20534 and friends: - * increment must always increase after the first */ - tt_int_op(increment, OP_GE, min_inc); - /* We at most quadruple, and always add one */ - tt_int_op(increment, OP_LE, max_inc); - } - if (old_increment) - tt_int_op(increment, OP_LE, old_increment * 3); - /* Advance */ - current_time += increment; -- ++(dls_random.n_download_attempts); -- ++(dls_random.n_download_failures); ++ if (dls_random.n_download_attempts < IMPOSSIBLE_TO_DOWNLOAD - 1) { ++ ++(dls_random.n_download_attempts); ++ ++(dls_random.n_download_failures); ++ } /* Try another maybe */ old_increment = increment; @@@ -4188,27 -3644,38 +4164,59 @@@ } static void +test_dir_download_status_random_backoff(void *arg) +{ + (void)arg; + + /* Do a standard test */ + download_status_random_backoff_helper(0, 1000000); + /* Regression test for 20534 and friends: + * try tighter bounds */ + download_status_random_backoff_helper(0, 100); + /* regression tests for 17750: initial delay */ + download_status_random_backoff_helper(10, 1000); + download_status_random_backoff_helper(20, 30); + + /* Pathological cases */ + download_status_random_backoff_helper(0, 0); + download_status_random_backoff_helper(1, 1); + download_status_random_backoff_helper(0, INT_MAX); + download_status_random_backoff_helper(INT_MAX/2, INT_MAX); +} + +static void + test_dir_download_status_random_backoff_ranges(void *arg) + { + (void)arg; + int lo, hi; + next_random_exponential_delay_range(&lo, &hi, 0, 10); + tt_int_op(lo, OP_EQ, 10); + tt_int_op(hi, OP_EQ, 11); + + next_random_exponential_delay_range(&lo, &hi, 6, 10); + tt_int_op(lo, OP_EQ, 10); + tt_int_op(hi, OP_EQ, 6*3); + + next_random_exponential_delay_range(&lo, &hi, 13, 10); + tt_int_op(lo, OP_EQ, 10); + tt_int_op(hi, OP_EQ, 13 * 3); + + next_random_exponential_delay_range(&lo, &hi, 37, 10); + tt_int_op(lo, OP_EQ, 10); + tt_int_op(hi, OP_EQ, 111); + + next_random_exponential_delay_range(&lo, &hi, 123, 10); + tt_int_op(lo, OP_EQ, 10); + tt_int_op(hi, OP_EQ, 369); + + next_random_exponential_delay_range(&lo, &hi, INT_MAX-5, 10); + tt_int_op(lo, OP_EQ, 10); + tt_int_op(hi, OP_EQ, INT_MAX); + done: + ; + } + + static void test_dir_download_status_increment(void *arg) { (void)arg;

1 0

[tor/master] Merge branch 'bug23816_029_squashed' into maint-0.3.2
by nickm＠torproject.org 08 Nov '17

08 Nov '17

commit e5a83062ed4e9e6b908efc6b75f13ab269f97377 Merge: 3dc61a5d7 cb29687e9 Author: Nick Mathewson <nickm(a)torproject.org> Date: Wed Nov 8 08:11:22 2017 -0500 Merge branch 'bug23816_029_squashed' into maint-0.3.2 changes/bug23816 | 6 +++++ src/or/directory.c | 76 +++++++++++++++++++++++++++++++---------------------- src/or/directory.h | 10 ++++++- src/test/test_dir.c | 69 +++++++++++++++++++++++++++--------------------- 4 files changed, 99 insertions(+), 62 deletions(-) diff --cc src/or/directory.h index 79984be32,c055e60d9..d26d83537 --- a/src/or/directory.h +++ b/src/or/directory.h @@@ -226,23 -167,15 +226,31 @@@ STATIC const smartlist_t *find_dl_sched STATIC void find_dl_min_and_max_delay(download_status_t *dls, const or_options_t *options, int *min, int *max); - STATIC int next_random_exponential_delay(int delay, int max_delay); ++ + STATIC int next_random_exponential_delay(int delay, + int base_delay, + int max_delay); + + STATIC void next_random_exponential_delay_range(int *low_bound_out, + int *high_bound_out, + int delay, + int base_delay); -#endif -#endif +STATIC int parse_hs_version_from_post(const char *url, const char *prefix, + const char **end_pos); + +STATIC unsigned parse_accept_encoding_header(const char *h); +#endif /* defined(TOR_UNIT_TESTS) */ + +#if defined(TOR_UNIT_TESTS) || defined(DIRECTORY_PRIVATE) +/* Used only by directory.c and test_dir.c */ + +/* no more than quadruple the previous delay (multiplier + 1) */ +#define DIR_DEFAULT_RANDOM_MULTIPLIER (3) +/* no more than triple the previous delay */ +#define DIR_TEST_NET_RANDOM_MULTIPLIER (2) + +#endif /* defined(TOR_UNIT_TESTS) || defined(DIRECTORY_PRIVATE) */ + +#endif /* !defined(TOR_DIRECTORY_H) */ diff --cc src/test/test_dir.c index 87b86c38b,1c6662147..ee4a9780b --- a/src/test/test_dir.c +++ b/src/test/test_dir.c @@@ -4124,11 -3608,16 +4124,11 @@@ download_status_random_backoff_helper(i { 0, 0, 0, DL_SCHED_GENERIC, DL_WANT_AUTHORITY, DL_SCHED_INCREMENT_FAILURE, DL_SCHED_RANDOM_EXPONENTIAL, 0, 0 }; int increment = -1; - int old_increment; + int old_increment = -1; time_t current_time = time(NULL); - const int exponent = DIR_DEFAULT_RANDOM_MULTIPLIER + 1; - const int min_delay = 0; - const int max_delay = 1000000; - - (void)arg; /* Check the random backoff cases */ - old_increment = 0; + int n_attempts = 0; do { increment = download_status_schedule_get_delay(&dls_random, NULL, @@@ -4148,33 -3626,14 +4148,12 @@@ /* Test */ tt_int_op(increment, OP_GE, min_delay); tt_int_op(increment, OP_LE, max_delay); - if (dls_random.last_backoff_position == 0) { - /* regression tests for 17750 - * Always use the minimum delay for the first increment */ - tt_int_op(increment, OP_EQ, min_delay); - } else { - /* It's times like these I'd love a good saturating arithmetic - * implementation */ - int min_inc = INT_MAX; - if (old_increment <= INT_MAX - 1) { - min_inc = old_increment + 1; - } - - int max_inc = INT_MAX; - if (old_increment <= (INT_MAX - 1)/exponent) { - max_inc = (exponent * old_increment) + 1; - } - - /* Regression test for 20534 and friends: - * increment must always increase after the first */ - tt_int_op(increment, OP_GE, min_inc); - /* We at most quadruple, and always add one */ - tt_int_op(increment, OP_LE, max_inc); - } - if (old_increment) - tt_int_op(increment, OP_LE, old_increment * 3); - /* Advance */ - current_time += increment; -- ++(dls_random.n_download_attempts); -- ++(dls_random.n_download_failures); ++ if (dls_random.n_download_attempts < IMPOSSIBLE_TO_DOWNLOAD - 1) { ++ ++(dls_random.n_download_attempts); ++ ++(dls_random.n_download_failures); ++ } /* Try another maybe */ old_increment = increment; @@@ -4188,27 -3644,38 +4164,59 @@@ } static void +test_dir_download_status_random_backoff(void *arg) +{ + (void)arg; + + /* Do a standard test */ + download_status_random_backoff_helper(0, 1000000); + /* Regression test for 20534 and friends: + * try tighter bounds */ + download_status_random_backoff_helper(0, 100); + /* regression tests for 17750: initial delay */ + download_status_random_backoff_helper(10, 1000); + download_status_random_backoff_helper(20, 30); + + /* Pathological cases */ + download_status_random_backoff_helper(0, 0); + download_status_random_backoff_helper(1, 1); + download_status_random_backoff_helper(0, INT_MAX); + download_status_random_backoff_helper(INT_MAX/2, INT_MAX); +} + +static void + test_dir_download_status_random_backoff_ranges(void *arg) + { + (void)arg; + int lo, hi; + next_random_exponential_delay_range(&lo, &hi, 0, 10); + tt_int_op(lo, OP_EQ, 10); + tt_int_op(hi, OP_EQ, 11); + + next_random_exponential_delay_range(&lo, &hi, 6, 10); + tt_int_op(lo, OP_EQ, 10); + tt_int_op(hi, OP_EQ, 6*3); + + next_random_exponential_delay_range(&lo, &hi, 13, 10); + tt_int_op(lo, OP_EQ, 10); + tt_int_op(hi, OP_EQ, 13 * 3); + + next_random_exponential_delay_range(&lo, &hi, 37, 10); + tt_int_op(lo, OP_EQ, 10); + tt_int_op(hi, OP_EQ, 111); + + next_random_exponential_delay_range(&lo, &hi, 123, 10); + tt_int_op(lo, OP_EQ, 10); + tt_int_op(hi, OP_EQ, 369); + + next_random_exponential_delay_range(&lo, &hi, INT_MAX-5, 10); + tt_int_op(lo, OP_EQ, 10); + tt_int_op(hi, OP_EQ, INT_MAX); + done: + ; + } + + static void test_dir_download_status_increment(void *arg) { (void)arg;

1 0

[tor/release-0.3.2] Merge branch 'maint-0.3.2' into release-0.3.2
by nickm＠torproject.org 08 Nov '17

08 Nov '17

commit 94752b3fa6b133cda02465b24890b3d218cb1fd8 Merge: 059c441d2 e5a83062e Author: Nick Mathewson <nickm(a)torproject.org> Date: Wed Nov 8 08:13:14 2017 -0500 Merge branch 'maint-0.3.2' into release-0.3.2 changes/bug23816 | 6 +++++ src/or/directory.c | 76 +++++++++++++++++++++++++++++++---------------------- src/or/directory.h | 10 ++++++- src/test/test_dir.c | 69 +++++++++++++++++++++++++++--------------------- 4 files changed, 99 insertions(+), 62 deletions(-)

1 0

[tor/release-0.3.2] Merge branch 'bug23816_029_squashed' into maint-0.3.2
by nickm＠torproject.org 08 Nov '17

08 Nov '17

commit e5a83062ed4e9e6b908efc6b75f13ab269f97377 Merge: 3dc61a5d7 cb29687e9 Author: Nick Mathewson <nickm(a)torproject.org> Date: Wed Nov 8 08:11:22 2017 -0500 Merge branch 'bug23816_029_squashed' into maint-0.3.2 changes/bug23816 | 6 +++++ src/or/directory.c | 76 +++++++++++++++++++++++++++++++---------------------- src/or/directory.h | 10 ++++++- src/test/test_dir.c | 69 +++++++++++++++++++++++++++--------------------- 4 files changed, 99 insertions(+), 62 deletions(-) diff --cc src/or/directory.h index 79984be32,c055e60d9..d26d83537 --- a/src/or/directory.h +++ b/src/or/directory.h @@@ -226,23 -167,15 +226,31 @@@ STATIC const smartlist_t *find_dl_sched STATIC void find_dl_min_and_max_delay(download_status_t *dls, const or_options_t *options, int *min, int *max); - STATIC int next_random_exponential_delay(int delay, int max_delay); ++ + STATIC int next_random_exponential_delay(int delay, + int base_delay, + int max_delay); + + STATIC void next_random_exponential_delay_range(int *low_bound_out, + int *high_bound_out, + int delay, + int base_delay); -#endif -#endif +STATIC int parse_hs_version_from_post(const char *url, const char *prefix, + const char **end_pos); + +STATIC unsigned parse_accept_encoding_header(const char *h); +#endif /* defined(TOR_UNIT_TESTS) */ + +#if defined(TOR_UNIT_TESTS) || defined(DIRECTORY_PRIVATE) +/* Used only by directory.c and test_dir.c */ + +/* no more than quadruple the previous delay (multiplier + 1) */ +#define DIR_DEFAULT_RANDOM_MULTIPLIER (3) +/* no more than triple the previous delay */ +#define DIR_TEST_NET_RANDOM_MULTIPLIER (2) + +#endif /* defined(TOR_UNIT_TESTS) || defined(DIRECTORY_PRIVATE) */ + +#endif /* !defined(TOR_DIRECTORY_H) */ diff --cc src/test/test_dir.c index 87b86c38b,1c6662147..ee4a9780b --- a/src/test/test_dir.c +++ b/src/test/test_dir.c @@@ -4124,11 -3608,16 +4124,11 @@@ download_status_random_backoff_helper(i { 0, 0, 0, DL_SCHED_GENERIC, DL_WANT_AUTHORITY, DL_SCHED_INCREMENT_FAILURE, DL_SCHED_RANDOM_EXPONENTIAL, 0, 0 }; int increment = -1; - int old_increment; + int old_increment = -1; time_t current_time = time(NULL); - const int exponent = DIR_DEFAULT_RANDOM_MULTIPLIER + 1; - const int min_delay = 0; - const int max_delay = 1000000; - - (void)arg; /* Check the random backoff cases */ - old_increment = 0; + int n_attempts = 0; do { increment = download_status_schedule_get_delay(&dls_random, NULL, @@@ -4148,33 -3626,14 +4148,12 @@@ /* Test */ tt_int_op(increment, OP_GE, min_delay); tt_int_op(increment, OP_LE, max_delay); - if (dls_random.last_backoff_position == 0) { - /* regression tests for 17750 - * Always use the minimum delay for the first increment */ - tt_int_op(increment, OP_EQ, min_delay); - } else { - /* It's times like these I'd love a good saturating arithmetic - * implementation */ - int min_inc = INT_MAX; - if (old_increment <= INT_MAX - 1) { - min_inc = old_increment + 1; - } - - int max_inc = INT_MAX; - if (old_increment <= (INT_MAX - 1)/exponent) { - max_inc = (exponent * old_increment) + 1; - } - - /* Regression test for 20534 and friends: - * increment must always increase after the first */ - tt_int_op(increment, OP_GE, min_inc); - /* We at most quadruple, and always add one */ - tt_int_op(increment, OP_LE, max_inc); - } - if (old_increment) - tt_int_op(increment, OP_LE, old_increment * 3); - /* Advance */ - current_time += increment; -- ++(dls_random.n_download_attempts); -- ++(dls_random.n_download_failures); ++ if (dls_random.n_download_attempts < IMPOSSIBLE_TO_DOWNLOAD - 1) { ++ ++(dls_random.n_download_attempts); ++ ++(dls_random.n_download_failures); ++ } /* Try another maybe */ old_increment = increment; @@@ -4188,27 -3644,38 +4164,59 @@@ } static void +test_dir_download_status_random_backoff(void *arg) +{ + (void)arg; + + /* Do a standard test */ + download_status_random_backoff_helper(0, 1000000); + /* Regression test for 20534 and friends: + * try tighter bounds */ + download_status_random_backoff_helper(0, 100); + /* regression tests for 17750: initial delay */ + download_status_random_backoff_helper(10, 1000); + download_status_random_backoff_helper(20, 30); + + /* Pathological cases */ + download_status_random_backoff_helper(0, 0); + download_status_random_backoff_helper(1, 1); + download_status_random_backoff_helper(0, INT_MAX); + download_status_random_backoff_helper(INT_MAX/2, INT_MAX); +} + +static void + test_dir_download_status_random_backoff_ranges(void *arg) + { + (void)arg; + int lo, hi; + next_random_exponential_delay_range(&lo, &hi, 0, 10); + tt_int_op(lo, OP_EQ, 10); + tt_int_op(hi, OP_EQ, 11); + + next_random_exponential_delay_range(&lo, &hi, 6, 10); + tt_int_op(lo, OP_EQ, 10); + tt_int_op(hi, OP_EQ, 6*3); + + next_random_exponential_delay_range(&lo, &hi, 13, 10); + tt_int_op(lo, OP_EQ, 10); + tt_int_op(hi, OP_EQ, 13 * 3); + + next_random_exponential_delay_range(&lo, &hi, 37, 10); + tt_int_op(lo, OP_EQ, 10); + tt_int_op(hi, OP_EQ, 111); + + next_random_exponential_delay_range(&lo, &hi, 123, 10); + tt_int_op(lo, OP_EQ, 10); + tt_int_op(hi, OP_EQ, 369); + + next_random_exponential_delay_range(&lo, &hi, INT_MAX-5, 10); + tt_int_op(lo, OP_EQ, 10); + tt_int_op(hi, OP_EQ, INT_MAX); + done: + ; + } + + static void test_dir_download_status_increment(void *arg) { (void)arg;

1 0

[tor-browser-bundle/maint-7.0] Update Changelog
by gk＠torproject.org 08 Nov '17

08 Nov '17

commit 95f7f4b699e357349b00ed52655b4b0a96fbf50b Author: Georg Koppen <gk(a)torproject.org> Date: Wed Nov 8 11:45:51 2017 +0000 Update Changelog --- Bundle-Data/Docs/ChangeLog.txt | 1 + 1 file changed, 1 insertion(+) diff --git a/Bundle-Data/Docs/ChangeLog.txt b/Bundle-Data/Docs/ChangeLog.txt index cf394ef..cecf4e9 100644 --- a/Bundle-Data/Docs/ChangeLog.txt +++ b/Bundle-Data/Docs/ChangeLog.txt @@ -6,6 +6,7 @@ Tor Browser 7.0.10 -- November 14 2017 * Bug 23997: Add link to Tor Browser manual for de, nl, tr, vi * Translations update * Update HTTPS-Everywhere to 2017.10.30 + * Bug 24178: Use make.sh for building HTTPS-Everywhere * Update NoScript to 5.1.5 * Bug 23968: NoScript icon jumps to the right after update * Windows

1 0

[tor-browser-bundle/maint-7.0] Bug 24178: Use make.sh for building HTTPS-Everywhere
by gk＠torproject.org 08 Nov '17

08 Nov '17

commit b07c02f2b218dbdd6de80b1e23cfa164d3735b93 Author: Georg Koppen <gk(a)torproject.org> Date: Wed Nov 8 11:44:43 2017 +0000 Bug 24178: Use make.sh for building HTTPS-Everywhere --- gitian/descriptors/linux/gitian-bundle.yml | 2 +- gitian/descriptors/mac/gitian-bundle.yml | 2 +- gitian/descriptors/windows/gitian-bundle.yml | 2 +- 3 files changed, 3 insertions(+), 3 deletions(-) diff --git a/gitian/descriptors/linux/gitian-bundle.yml b/gitian/descriptors/linux/gitian-bundle.yml index b08fbcc..e650671 100644 --- a/gitian/descriptors/linux/gitian-bundle.yml +++ b/gitian/descriptors/linux/gitian-bundle.yml @@ -107,7 +107,7 @@ script: | # |./makexpi.sh foo| to build tag |foo| is a) trying to download the sources # during build time (again) and b) broken due to a certificate error. rm -f .git/refs/heads/master - ./makexpi.sh + ./make.sh # Since 5.0.2 a .xpi for AMO is built, too. We don't need it. rm pkg/*-amo.xpi cp pkg/*.xpi ../${TB_STAGE_DIR}/Browser/TorBrowser/Data/Browser/profile.default/extensions/https-everywhere-eff(a)eff.org.xpi diff --git a/gitian/descriptors/mac/gitian-bundle.yml b/gitian/descriptors/mac/gitian-bundle.yml index 662e4da..f928dff 100644 --- a/gitian/descriptors/mac/gitian-bundle.yml +++ b/gitian/descriptors/mac/gitian-bundle.yml @@ -137,7 +137,7 @@ script: | # |./makexpi.sh foo| to build tag |foo| is a) trying to download the sources # during build time (again) and b) broken due to a certificate error. rm -f .git/refs/heads/master - ./makexpi.sh + ./make.sh # Since 5.0.2 a .xpi for AMO is built, too. We don't need it. rm pkg/*-amo.xpi cp pkg/*.xpi ../$TORBROWSER_NAME.app/$EXTSPATH/https-everywhere-eff(a)eff.org.xpi diff --git a/gitian/descriptors/windows/gitian-bundle.yml b/gitian/descriptors/windows/gitian-bundle.yml index e563308..5acb13f 100644 --- a/gitian/descriptors/windows/gitian-bundle.yml +++ b/gitian/descriptors/windows/gitian-bundle.yml @@ -107,7 +107,7 @@ script: | # |./makexpi.sh foo| to build tag |foo| is a) trying to download the sources # during build time (again) and b) broken due to a certificate error. rm -f .git/refs/heads/master - ./makexpi.sh + ./make.sh # Since 5.0.2 a .xpi for AMO is built, too. We don't need it. rm pkg/*-amo.xpi cp pkg/*.xpi ../tbb-windows-installer/"Tor Browser"/Browser/TorBrowser/Data/Browser/profile.default/extensions/https-everywhere-eff(a)eff.org.xpi

1 0

[onionoo/master] Skip unrecognized descriptors when importing archives.
by karsten＠torproject.org 08 Nov '17

08 Nov '17

commit ffc949ea54ce294c87b48b3ee8d08198a9e5d9b7 Author: Karsten Loesing <karsten.loesing(a)gmx.net> Date: Fri Nov 3 22:33:02 2017 +0100 Skip unrecognized descriptors when importing archives. --- CHANGELOG.md | 2 ++ src/main/java/org/torproject/onionoo/updater/DescriptorSource.java | 5 ++--- 2 files changed, 4 insertions(+), 3 deletions(-) diff --git a/CHANGELOG.md b/CHANGELOG.md index 74f29b7..12b0741 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -2,6 +2,8 @@ * Medium changes - Support quoted qualified search terms. + - Skip unrecognized descriptors when importing archives rather than + aborting the entire import. # Changes in version 4.2-1.6.1 - 2017-10-26 diff --git a/src/main/java/org/torproject/onionoo/updater/DescriptorSource.java b/src/main/java/org/torproject/onionoo/updater/DescriptorSource.java index d32727f..07ae4f8 100644 --- a/src/main/java/org/torproject/onionoo/updater/DescriptorSource.java +++ b/src/main/java/org/torproject/onionoo/updater/DescriptorSource.java @@ -170,9 +170,8 @@ public class DescriptorSource { if (descriptorType == null) { log.warn("Unrecognized descriptor in " + this.inArchiveDir.getAbsolutePath() + " with annotations " - + descriptor.getAnnotations() + ". Not reading any further" - + "archived descriptors."); - break; + + descriptor.getAnnotations() + ". Skipping descriptor."); + continue; } for (DescriptorListener descriptorListener : this.descriptorListeners.get(descriptorType)) {

1 0