commit 695b0bd1d5aca52a05df1a697a6b23a20be529d4 Author: Andrea Shepard andrea@torproject.org Date: Sun Jun 12 19:07:11 2016 +0000
Implement DL_SCHED_RANDOM_EXPONENTIAL support for download_status_t --- src/or/directory.c | 112 +++++++++++++++++++++++++++++++++++++++++++++---- src/or/directory.h | 4 ++ src/or/networkstatus.c | 8 ++-- src/or/or.h | 16 +++++++ src/or/routerlist.c | 3 ++ 5 files changed, 130 insertions(+), 13 deletions(-)
diff --git a/src/or/directory.c b/src/or/directory.c index 6caca11..5b890ca 100644 --- a/src/or/directory.c +++ b/src/or/directory.c @@ -3762,6 +3762,28 @@ find_dl_schedule(download_status_t *dls, const or_options_t *options) return NULL; }
+/** Decide which minimum and maximum delay step we want to use based on + * descriptor type in <b>dls</b> and <b>options</b>. + * Helper function for download_status_schedule_get_delay(). */ +STATIC void +find_dl_min_and_max_delay(download_status_t *dls, const or_options_t *options, + int *min, int *max) +{ + tor_assert(dls); + tor_assert(options); + tor_assert(min); + tor_assert(max); + + /* + * For now, just use the existing schedule config stuff and pick the + * first/last entries off to get min/max delay for backoff purposes + */ + const smartlist_t *schedule = find_dl_schedule(dls, options); + tor_assert(schedule != NULL && smartlist_len(schedule) >= 2); + *min = *((int *)(smartlist_get(schedule, 0))); + *max = *((int *)((smartlist_get(schedule, smartlist_len(schedule) - 1)))); +} + /* Find the current delay for dls based on schedule. * Set dls->next_attempt_at based on now, and return the delay. * Helper for download_status_increment_failure and @@ -3769,23 +3791,85 @@ find_dl_schedule(download_status_t *dls, const or_options_t *options) STATIC int download_status_schedule_get_delay(download_status_t *dls, const smartlist_t *schedule, + int min_delay, int max_delay, time_t now) { tor_assert(dls); - tor_assert(schedule); + /* We don't need a schedule if we're using random exponential backoff */ + tor_assert(dls->backoff == DL_SCHED_RANDOM_EXPONENTIAL || + schedule != NULL); + /* If we're using random exponential backoff, we do need min/max delay */ + tor_assert(dls->backoff != DL_SCHED_RANDOM_EXPONENTIAL || + (min_delay >= 0 && max_delay >= min_delay && + max_delay <= INT_MAX));
int delay = INT_MAX; + int delay_increment, i; uint8_t dls_schedule_position = (dls->increment_on == DL_SCHED_INCREMENT_ATTEMPT ? dls->n_download_attempts : dls->n_download_failures); + uint8_t entropy;
- if (dls_schedule_position < smartlist_len(schedule)) - delay = *(int *)smartlist_get(schedule, dls_schedule_position); - else if (dls_schedule_position == IMPOSSIBLE_TO_DOWNLOAD) - delay = INT_MAX; - else - delay = *(int *)smartlist_get(schedule, smartlist_len(schedule) - 1); + if (dls->backoff == DL_SCHED_DETERMINISTIC) { + if (dls_schedule_position < smartlist_len(schedule)) + delay = *(int *)smartlist_get(schedule, dls_schedule_position); + else if (dls_schedule_position == IMPOSSIBLE_TO_DOWNLOAD) + delay = INT_MAX; + else + delay = *(int *)smartlist_get(schedule, smartlist_len(schedule) - 1); + } else if (dls->backoff == DL_SCHED_RANDOM_EXPONENTIAL) { + /* Check if we missed a reset somehow */ + if (dls->last_backoff_position > dls_schedule_position) { + dls->last_backoff_position = 0; + dls->last_delay_used = 0; + } + + if (dls_schedule_position > 0) { + delay = dls->last_delay_used; + + while (dls->last_backoff_position < dls_schedule_position) { + /* + * Backoff step: we want to multiply by something ~1.5, and then add + * 1 with non-zero probability so we can't get stuck at zero even if + * we start out with zero delay. To do this, pick a uint8_t of + * entropy in the range [0,255], and use it to construct an + * increment. + */ + delay_increment = 0; + /* Get a byte of entropy */ + crypto_rand((char *)(&entropy), sizeof(entropy)); + /* Clamp it just to be sure */ + entropy &= 0xff; + /* If we have non-zero delay; otherwise this is a no-op */ + if (delay > 0) { + /* Use the low 7 bits for the increment */ + for (i = 0; i < 7; ++i) { + if (entropy & (0x1 << i)) delay_increment += (delay >> (i + 1)); + } + } + /* + * Using the remaining bit of entropy, add 1 with probability 50% so + * we can't get stuck at 0 + */ + if (entropy & 0x80) delay_increment += 1; + /* Increment delay, make sure to saturate if we would wrap around */ + if (delay_increment < max_delay - delay) delay += delay_increment; + else delay = max_delay; + ++(dls->last_backoff_position); + } + } else { + delay = min_delay; + } + + /* Clamp it within min/max if we have them */ + if (min_delay >= 0 && delay < min_delay) delay = min_delay; + if (max_delay != INT_MAX && delay > max_delay) delay = max_delay; + + /* Store it for next time */ + dls->last_backoff_position = dls_schedule_position; + dls->last_delay_used = delay; + }
/* A negative delay makes no sense. Knowing that delay is * non-negative allows us to safely do the wrapping check below. */ @@ -3846,6 +3930,8 @@ download_status_increment_failure(download_status_t *dls, int status_code, const char *item, int server, time_t now) { int increment = -1; + int min_delay = 0, max_delay = INT_MAX; + tor_assert(dls);
/* only count the failure if it's permanent, or we're a server */ @@ -3866,7 +3952,9 @@ download_status_increment_failure(download_status_t *dls, int status_code, /* only return a failure retry time if this schedule increments on failures */ const smartlist_t *schedule = find_dl_schedule(dls, get_options()); - increment = download_status_schedule_get_delay(dls, schedule, now); + find_dl_min_and_max_delay(dls, get_options(), &min_delay, &max_delay); + increment = download_status_schedule_get_delay(dls, schedule, + min_delay, max_delay, now); }
download_status_log_helper(item, !dls->increment_on, "failed", @@ -3895,6 +3983,8 @@ download_status_increment_attempt(download_status_t *dls, const char *item, time_t now) { int delay = -1; + int min_delay = 0, max_delay = INT_MAX; + tor_assert(dls);
if (dls->increment_on == DL_SCHED_INCREMENT_FAILURE) { @@ -3909,7 +3999,9 @@ download_status_increment_attempt(download_status_t *dls, const char *item, ++dls->n_download_attempts;
const smartlist_t *schedule = find_dl_schedule(dls, get_options()); - delay = download_status_schedule_get_delay(dls, schedule, now); + find_dl_min_and_max_delay(dls, get_options(), &min_delay, &max_delay); + delay = download_status_schedule_get_delay(dls, schedule, + min_delay, max_delay, now);
download_status_log_helper(item, dls->increment_on, "attempted", "on failure", dls->n_download_attempts, @@ -3941,6 +4033,8 @@ download_status_reset(download_status_t *dls) dls->n_download_failures = 0; dls->n_download_attempts = 0; dls->next_attempt_at = time(NULL) + *(int *)smartlist_get(schedule, 0); + dls->last_backoff_position = 0; + dls->last_delay_used = 0; /* Don't reset dls->want_authority or dls->increment_on */ }
diff --git a/src/or/directory.h b/src/or/directory.h index 7646cac..d867aa3 100644 --- a/src/or/directory.h +++ b/src/or/directory.h @@ -146,6 +146,7 @@ STATIC int directory_handle_command_get(dir_connection_t *conn, size_t req_body_len); STATIC int download_status_schedule_get_delay(download_status_t *dls, const smartlist_t *schedule, + int min_delay, int max_delay, time_t now);
STATIC char* authdir_type_to_string(dirinfo_type_t auth); @@ -154,6 +155,9 @@ STATIC int should_use_directory_guards(const or_options_t *options); STATIC zlib_compression_level_t choose_compression_level(ssize_t n_bytes); STATIC const smartlist_t *find_dl_schedule(download_status_t *dls, const or_options_t *options); +STATIC void find_dl_min_and_max_delay(download_status_t *dls, + const or_options_t *options, + int *min, int *max); #endif
#endif diff --git a/src/or/networkstatus.c b/src/or/networkstatus.c index 5a91dda..db4ed85 100644 --- a/src/or/networkstatus.c +++ b/src/or/networkstatus.c @@ -86,9 +86,9 @@ static time_t time_to_download_next_consensus[N_CONSENSUS_FLAVORS]; static download_status_t consensus_dl_status[N_CONSENSUS_FLAVORS] = { { 0, 0, 0, DL_SCHED_CONSENSUS, DL_WANT_ANY_DIRSERVER, - DL_SCHED_INCREMENT_FAILURE }, + DL_SCHED_INCREMENT_FAILURE, DL_SCHED_DETERMINISTIC, 0, 0 }, { 0, 0, 0, DL_SCHED_CONSENSUS, DL_WANT_ANY_DIRSERVER, - DL_SCHED_INCREMENT_FAILURE }, + DL_SCHED_INCREMENT_FAILURE, DL_SCHED_DETERMINISTIC, 0, 0 }, };
#define N_CONSENSUS_BOOTSTRAP_SCHEDULES 2 @@ -105,10 +105,10 @@ static download_status_t consensus_bootstrap_dl_status[N_CONSENSUS_BOOTSTRAP_SCHEDULES] = { { 0, 0, 0, DL_SCHED_CONSENSUS, DL_WANT_AUTHORITY, - DL_SCHED_INCREMENT_ATTEMPT }, + DL_SCHED_INCREMENT_ATTEMPT, DL_SCHED_DETERMINISTIC, 0, 0 }, /* During bootstrap, DL_WANT_ANY_DIRSERVER means "use fallbacks". */ { 0, 0, 0, DL_SCHED_CONSENSUS, DL_WANT_ANY_DIRSERVER, - DL_SCHED_INCREMENT_ATTEMPT }, + DL_SCHED_INCREMENT_ATTEMPT, DL_SCHED_DETERMINISTIC, 0, 0 }, };
/** True iff we have logged a warning about this OR's version being older than diff --git a/src/or/or.h b/src/or/or.h index 5a19f9a..efe5680 100644 --- a/src/or/or.h +++ b/src/or/or.h @@ -1987,6 +1987,15 @@ typedef enum { #define download_schedule_increment_bitfield_t \ ENUM_BF(download_schedule_increment_t)
+/** Enumeration: do we want to use the random exponential backoff + * mechanism? */ +typedef enum { + DL_SCHED_DETERMINISTIC = 0, + DL_SCHED_RANDOM_EXPONENTIAL = 1, +} download_schedule_backoff_t; +#define download_schedule_backoff_bitfield_t \ + ENUM_BF(download_schedule_backoff_t) + /** Information about our plans for retrying downloads for a downloadable * directory object. * Each type of downloadable directory object has a corresponding retry @@ -2033,6 +2042,13 @@ typedef struct download_status_t { download_schedule_increment_bitfield_t increment_on : 1; /**< does this * schedule increment on each attempt, * or after each failure? */ + download_schedule_backoff_bitfield_t backoff : 1; /**< do we use the + * deterministic schedule, or random + * exponential backoffs? */ + uint8_t last_backoff_position; /**< number of attempts/failures, depending + * on increment_on, when we last recalculated + * the delay. */ + int last_delay_used; /**< last delay used for random exponential backoff */ } download_status_t;
/** If n_download_failures is this high, the download can never happen. */ diff --git a/src/or/routerlist.c b/src/or/routerlist.c index aaa8fad..6721925 100644 --- a/src/or/routerlist.c +++ b/src/or/routerlist.c @@ -159,6 +159,9 @@ download_status_cert_init(download_status_t *dlstatus) dlstatus->schedule = DL_SCHED_CONSENSUS; dlstatus->want_authority = DL_WANT_ANY_DIRSERVER; dlstatus->increment_on = DL_SCHED_INCREMENT_FAILURE; + dlstatus->backoff = DL_SCHED_DETERMINISTIC; + dlstatus->last_backoff_position = 0; + dlstatus->last_delay_used = 0;
/* Use the new schedule to set next_attempt_at */ download_status_reset(dlstatus);