diff options
Diffstat (limited to 'src/feature/dirclient/dlstatus.c')
| -rw-r--r-- | src/feature/dirclient/dlstatus.c | 422 |
1 files changed, 422 insertions, 0 deletions
diff --git a/src/feature/dirclient/dlstatus.c b/src/feature/dirclient/dlstatus.c new file mode 100644 index 0000000000..0842a2c676 --- /dev/null +++ b/src/feature/dirclient/dlstatus.c @@ -0,0 +1,422 @@ +/* Copyright (c) 2001-2004, Roger Dingledine. + * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. + * Copyright (c) 2007-2019, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +#define DLSTATUS_PRIVATE + +#include "core/or/or.h" + +#include "app/config/config.h" +#include "feature/client/entrynodes.h" +#include "feature/dirclient/dlstatus.h" +#include "feature/nodelist/networkstatus.h" +#include "feature/relay/routermode.h" +#include "lib/crypt_ops/crypto_rand.h" + +#include "feature/dirclient/download_status_st.h" + +/** Decide which download schedule we want to use based on descriptor type + * in <b>dls</b> and <b>options</b>. + * + * Then, return the initial delay for that download schedule, in seconds. + * + * Helper function for download_status_increment_failure(), + * download_status_reset(), and download_status_increment_attempt(). */ +STATIC int +find_dl_min_delay(const download_status_t *dls, const or_options_t *options) +{ + tor_assert(dls); + tor_assert(options); + + switch (dls->schedule) { + case DL_SCHED_GENERIC: + /* Any other directory document */ + if (dir_server_mode(options)) { + /* A directory authority or directory mirror */ + return options->TestingServerDownloadInitialDelay; + } else { + return options->TestingClientDownloadInitialDelay; + } + case DL_SCHED_CONSENSUS: + if (!networkstatus_consensus_can_use_multiple_directories(options)) { + /* A public relay */ + return options->TestingServerConsensusDownloadInitialDelay; + } else { + /* A client or bridge */ + if (networkstatus_consensus_is_bootstrapping(time(NULL))) { + /* During bootstrapping */ + if (!networkstatus_consensus_can_use_extra_fallbacks(options)) { + /* A bootstrapping client without extra fallback directories */ + return options-> + ClientBootstrapConsensusAuthorityOnlyDownloadInitialDelay; + } else if (dls->want_authority) { + /* A bootstrapping client with extra fallback directories, but + * connecting to an authority */ + return + options->ClientBootstrapConsensusAuthorityDownloadInitialDelay; + } else { + /* A bootstrapping client connecting to extra fallback directories + */ + return + options->ClientBootstrapConsensusFallbackDownloadInitialDelay; + } + } else { + /* A client with a reasonably live consensus, with or without + * certificates */ + return options->TestingClientConsensusDownloadInitialDelay; + } + } + case DL_SCHED_BRIDGE: + if (options->UseBridges && num_bridges_usable(0) > 0) { + /* A bridge client that is sure that one or more of its bridges are + * running can afford to wait longer to update bridge descriptors. */ + return options->TestingBridgeDownloadInitialDelay; + } else { + /* A bridge client which might have no running bridges, must try to + * get bridge descriptors straight away. */ + return options->TestingBridgeBootstrapDownloadInitialDelay; + } + default: + tor_assert(0); + } + + /* Impossible, but gcc will fail with -Werror without a `return`. */ + return 0; +} + +/** 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 *<b>low_bound_out</b>, and the high bound into + * *<b>high_bound_out</b>. 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 <b>base_delay</b> parameter is lowest possible delay time (can't be + * zero); the <b>backoff_position</b> parameter is the number of times we've + * generated a delay; and the <b>delay</b> argument is the most recently used + * delay. + */ +STATIC int +next_random_exponential_delay(int delay, + int base_delay) +{ + /* Check preconditions */ + if (BUG(delay < 0)) + delay = 0; + + if (base_delay < 1) + base_delay = 1; + + int low_bound=0, high_bound=INT_MAX; + + next_random_exponential_delay_range(&low_bound, &high_bound, + delay, base_delay); + + return crypto_rand_int_range(low_bound, high_bound); +} + +/** Find the current delay for dls based on min_delay. + * + * This function sets dls->next_attempt_at based on now, and returns the delay. + * Helper for download_status_increment_failure and + * download_status_increment_attempt. */ +STATIC int +download_status_schedule_get_delay(download_status_t *dls, + int min_delay, + time_t now) +{ + tor_assert(dls); + /* If we're using random exponential backoff, we do need min/max delay */ + tor_assert(min_delay >= 0); + + int delay = INT_MAX; + uint8_t dls_schedule_position = (dls->increment_on + == DL_SCHED_INCREMENT_ATTEMPT + ? dls->n_download_attempts + : dls->n_download_failures); + + /* Check if we missed a reset somehow */ + IF_BUG_ONCE(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) { + /* Do one increment step */ + delay = next_random_exponential_delay(delay, min_delay); + /* Update our position */ + ++(dls->last_backoff_position); + } + } else { + /* If we're just starting out, use the minimum delay */ + delay = min_delay; + } + + /* Clamp it within min/max if we have them */ + if (min_delay >= 0 && delay < min_delay) delay = min_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. */ + tor_assert(delay >= 0); + + /* Avoid now+delay overflowing TIME_MAX, by comparing with a subtraction + * that won't overflow (since delay is non-negative). */ + if (delay < INT_MAX && now <= TIME_MAX - delay) { + dls->next_attempt_at = now+delay; + } else { + dls->next_attempt_at = TIME_MAX; + } + + return delay; +} + +/* Log a debug message about item, which increments on increment_action, has + * incremented dls_n_download_increments times. The message varies based on + * was_schedule_incremented (if not, not_incremented_response is logged), and + * the values of increment, dls_next_attempt_at, and now. + * Helper for download_status_increment_failure and + * download_status_increment_attempt. */ +static void +download_status_log_helper(const char *item, int was_schedule_incremented, + const char *increment_action, + const char *not_incremented_response, + uint8_t dls_n_download_increments, int increment, + time_t dls_next_attempt_at, time_t now) +{ + if (item) { + if (!was_schedule_incremented) + log_debug(LD_DIR, "%s %s %d time(s); I'll try again %s.", + item, increment_action, (int)dls_n_download_increments, + not_incremented_response); + else if (increment == 0) + log_debug(LD_DIR, "%s %s %d time(s); I'll try again immediately.", + item, increment_action, (int)dls_n_download_increments); + else if (dls_next_attempt_at < TIME_MAX) + log_debug(LD_DIR, "%s %s %d time(s); I'll try again in %d seconds.", + item, increment_action, (int)dls_n_download_increments, + (int)(dls_next_attempt_at-now)); + else + log_debug(LD_DIR, "%s %s %d time(s); Giving up for a while.", + item, increment_action, (int)dls_n_download_increments); + } +} + +/** Determine when a failed download attempt should be retried. + * Called when an attempt to download <b>dls</b> has failed with HTTP status + * <b>status_code</b>. Increment the failure count (if the code indicates a + * real failure, or if we're a server) and set <b>dls</b>-\>next_attempt_at to + * an appropriate time in the future and return it. + * If <b>dls->increment_on</b> is DL_SCHED_INCREMENT_ATTEMPT, increment the + * failure count, and return a time in the far future for the next attempt (to + * avoid an immediate retry). */ +time_t +download_status_increment_failure(download_status_t *dls, int status_code, + const char *item, int server, time_t now) +{ + (void) status_code; // XXXX no longer used. + (void) server; // XXXX no longer used. + int increment = -1; + int min_delay = 0; + + tor_assert(dls); + + /* dls wasn't reset before it was used */ + if (dls->next_attempt_at == 0) { + download_status_reset(dls); + } + + /* count the failure */ + if (dls->n_download_failures < IMPOSSIBLE_TO_DOWNLOAD-1) { + ++dls->n_download_failures; + } + + if (dls->increment_on == DL_SCHED_INCREMENT_FAILURE) { + /* We don't find out that a failure-based schedule has attempted a + * connection until that connection fails. + * We'll never find out about successful connections, but this doesn't + * matter, because schedules are reset after a successful download. + */ + if (dls->n_download_attempts < IMPOSSIBLE_TO_DOWNLOAD-1) + ++dls->n_download_attempts; + + /* only return a failure retry time if this schedule increments on failures + */ + min_delay = find_dl_min_delay(dls, get_options()); + increment = download_status_schedule_get_delay(dls, min_delay, now); + } + + download_status_log_helper(item, !dls->increment_on, "failed", + "concurrently", dls->n_download_failures, + increment, + download_status_get_next_attempt_at(dls), + now); + + if (dls->increment_on == DL_SCHED_INCREMENT_ATTEMPT) { + /* stop this schedule retrying on failure, it will launch concurrent + * connections instead */ + return TIME_MAX; + } else { + return download_status_get_next_attempt_at(dls); + } +} + +/** Determine when the next download attempt should be made when using an + * attempt-based (potentially concurrent) download schedule. + * Called when an attempt to download <b>dls</b> is being initiated. + * Increment the attempt count and set <b>dls</b>-\>next_attempt_at to an + * appropriate time in the future and return it. + * If <b>dls->increment_on</b> is DL_SCHED_INCREMENT_FAILURE, don't increment + * the attempts, and return a time in the far future (to avoid launching a + * concurrent attempt). */ +time_t +download_status_increment_attempt(download_status_t *dls, const char *item, + time_t now) +{ + int delay = -1; + int min_delay = 0; + + tor_assert(dls); + + /* dls wasn't reset before it was used */ + if (dls->next_attempt_at == 0) { + download_status_reset(dls); + } + + if (dls->increment_on == DL_SCHED_INCREMENT_FAILURE) { + /* this schedule should retry on failure, and not launch any concurrent + attempts */ + log_warn(LD_BUG, "Tried to launch an attempt-based connection on a " + "failure-based schedule."); + return TIME_MAX; + } + + if (dls->n_download_attempts < IMPOSSIBLE_TO_DOWNLOAD-1) + ++dls->n_download_attempts; + + min_delay = find_dl_min_delay(dls, get_options()); + delay = download_status_schedule_get_delay(dls, min_delay, now); + + download_status_log_helper(item, dls->increment_on, "attempted", + "on failure", dls->n_download_attempts, + delay, download_status_get_next_attempt_at(dls), + now); + + return download_status_get_next_attempt_at(dls); +} + +static time_t +download_status_get_initial_delay_from_now(const download_status_t *dls) +{ + /* We use constant initial delays, even in exponential backoff + * schedules. */ + return time(NULL) + find_dl_min_delay(dls, get_options()); +} + +/** Reset <b>dls</b> so that it will be considered downloadable + * immediately, and/or to show that we don't need it anymore. + * + * Must be called to initialise a download schedule, otherwise the zeroth item + * in the schedule will never be used. + * + * (We find the zeroth element of the download schedule, and set + * next_attempt_at to be the appropriate offset from 'now'. In most + * cases this means setting it to 'now', so the item will be immediately + * downloadable; when using authorities with fallbacks, there is a few seconds' + * delay.) */ +void +download_status_reset(download_status_t *dls) +{ + if (dls->n_download_failures == IMPOSSIBLE_TO_DOWNLOAD + || dls->n_download_attempts == IMPOSSIBLE_TO_DOWNLOAD) + return; /* Don't reset this. */ + + dls->n_download_failures = 0; + dls->n_download_attempts = 0; + dls->next_attempt_at = download_status_get_initial_delay_from_now(dls); + dls->last_backoff_position = 0; + dls->last_delay_used = 0; + /* Don't reset dls->want_authority or dls->increment_on */ +} + +/** Return true iff, as of <b>now</b>, the resource tracked by <b>dls</b> is + * ready to get its download reattempted. */ +int +download_status_is_ready(download_status_t *dls, time_t now) +{ + /* dls wasn't reset before it was used */ + if (dls->next_attempt_at == 0) { + download_status_reset(dls); + } + + return download_status_get_next_attempt_at(dls) <= now; +} + +/** Mark <b>dl</b> as never downloadable. */ +void +download_status_mark_impossible(download_status_t *dl) +{ + dl->n_download_failures = IMPOSSIBLE_TO_DOWNLOAD; + dl->n_download_attempts = IMPOSSIBLE_TO_DOWNLOAD; +} + +/** Return the number of failures on <b>dls</b> since the last success (if + * any). */ +int +download_status_get_n_failures(const download_status_t *dls) +{ + return dls->n_download_failures; +} + +/** Return the number of attempts to download <b>dls</b> since the last success + * (if any). This can differ from download_status_get_n_failures() due to + * outstanding concurrent attempts. */ +int +download_status_get_n_attempts(const download_status_t *dls) +{ + return dls->n_download_attempts; +} + +/** Return the next time to attempt to download <b>dls</b>. */ +time_t +download_status_get_next_attempt_at(const download_status_t *dls) +{ + /* dls wasn't reset before it was used */ + if (dls->next_attempt_at == 0) { + /* so give the answer we would have given if it had been */ + return download_status_get_initial_delay_from_now(dls); + } + + return dls->next_attempt_at; +} |