Line data Source code
1 : /* Copyright (c) 2001-2004, Roger Dingledine.
2 : * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
3 : * Copyright (c) 2007-2021, The Tor Project, Inc. */
4 : /* See LICENSE for licensing information */
5 :
6 : /**
7 : * @file dlstatus.c
8 : * @brief Track status and retry schedule of a downloadable object.
9 : **/
10 :
11 : #define DLSTATUS_PRIVATE
12 :
13 : #include "core/or/or.h"
14 :
15 : #include "app/config/config.h"
16 : #include "feature/client/entrynodes.h"
17 : #include "feature/dirclient/dlstatus.h"
18 : #include "feature/nodelist/networkstatus.h"
19 : #include "feature/relay/routermode.h"
20 : #include "lib/crypt_ops/crypto_rand.h"
21 :
22 : #include "feature/dirclient/download_status_st.h"
23 :
24 : /** Decide which download schedule we want to use based on descriptor type
25 : * in <b>dls</b> and <b>options</b>.
26 : *
27 : * Then, return the initial delay for that download schedule, in seconds.
28 : *
29 : * Helper function for download_status_increment_failure(),
30 : * download_status_reset(), and download_status_increment_attempt(). */
31 : STATIC int
32 158 : find_dl_min_delay(const download_status_t *dls, const or_options_t *options)
33 : {
34 158 : tor_assert(dls);
35 158 : tor_assert(options);
36 :
37 158 : switch (dls->schedule) {
38 99 : case DL_SCHED_GENERIC:
39 : /* Any other directory document */
40 99 : if (dir_server_mode(options)) {
41 : /* A directory authority or directory mirror */
42 8 : return options->TestingServerDownloadInitialDelay;
43 : } else {
44 91 : return options->TestingClientDownloadInitialDelay;
45 : }
46 51 : case DL_SCHED_CONSENSUS:
47 51 : if (!networkstatus_consensus_can_use_multiple_directories(options)) {
48 : /* A public relay */
49 8 : return options->TestingServerConsensusDownloadInitialDelay;
50 : } else {
51 : /* A client or bridge */
52 43 : if (networkstatus_consensus_is_bootstrapping(time(NULL))) {
53 : /* During bootstrapping */
54 28 : if (!networkstatus_consensus_can_use_extra_fallbacks(options)) {
55 : /* A bootstrapping client without extra fallback directories */
56 20 : return options->
57 : ClientBootstrapConsensusAuthorityOnlyDownloadInitialDelay;
58 8 : } else if (dls->want_authority) {
59 : /* A bootstrapping client with extra fallback directories, but
60 : * connecting to an authority */
61 4 : return
62 4 : options->ClientBootstrapConsensusAuthorityDownloadInitialDelay;
63 : } else {
64 : /* A bootstrapping client connecting to extra fallback directories
65 : */
66 4 : return
67 4 : options->ClientBootstrapConsensusFallbackDownloadInitialDelay;
68 : }
69 : } else {
70 : /* A client with a reasonably live consensus, with or without
71 : * certificates */
72 15 : return options->TestingClientConsensusDownloadInitialDelay;
73 : }
74 : }
75 8 : case DL_SCHED_BRIDGE:
76 8 : if (options->UseBridges && num_bridges_usable(0) > 0) {
77 : /* A bridge client that is sure that one or more of its bridges are
78 : * running can afford to wait longer to update bridge descriptors. */
79 4 : return options->TestingBridgeDownloadInitialDelay;
80 : } else {
81 : /* A bridge client which might have no running bridges, must try to
82 : * get bridge descriptors straight away. */
83 4 : return options->TestingBridgeBootstrapDownloadInitialDelay;
84 : }
85 : default:
86 0 : tor_assert(0);
87 : }
88 :
89 : /* Impossible, but gcc will fail with -Werror without a `return`. */
90 : return 0;
91 : }
92 :
93 : /** As next_random_exponential_delay() below, but does not compute a random
94 : * value. Instead, compute the range of values that
95 : * next_random_exponential_delay() should use when computing its random value.
96 : * Store the low bound into *<b>low_bound_out</b>, and the high bound into
97 : * *<b>high_bound_out</b>. Guarantees that the low bound is strictly less
98 : * than the high bound. */
99 : STATIC void
100 1026 : next_random_exponential_delay_range(int *low_bound_out,
101 : int *high_bound_out,
102 : int delay,
103 : int base_delay)
104 : {
105 : // This is the "decorrelated jitter" approach, from
106 : // https://www.awsarchitectureblog.com/2015/03/backoff.html
107 : // The formula is
108 : // sleep = min(cap, random_between(base, sleep * 3))
109 :
110 1026 : const int delay_times_3 = delay < INT_MAX/3 ? delay * 3 : INT_MAX;
111 1026 : *low_bound_out = base_delay;
112 1026 : if (delay_times_3 > base_delay) {
113 1020 : *high_bound_out = delay_times_3;
114 : } else {
115 6 : *high_bound_out = base_delay+1;
116 : }
117 1026 : }
118 :
119 : /** Advance one delay step. The algorithm will generate a random delay,
120 : * such that each failure is possibly (random) longer than the ones before.
121 : *
122 : * We then clamp that value to be no larger than max_delay, and return it.
123 : *
124 : * The <b>base_delay</b> parameter is lowest possible delay time (can't be
125 : * zero); the <b>backoff_position</b> parameter is the number of times we've
126 : * generated a delay; and the <b>delay</b> argument is the most recently used
127 : * delay.
128 : */
129 : STATIC int
130 1020 : next_random_exponential_delay(int delay,
131 : int base_delay)
132 : {
133 : /* Check preconditions */
134 1020 : if (BUG(delay < 0))
135 : delay = 0;
136 :
137 1020 : if (base_delay < 1)
138 : base_delay = 1;
139 :
140 1020 : int low_bound=0, high_bound=INT_MAX;
141 :
142 1020 : next_random_exponential_delay_range(&low_bound, &high_bound,
143 : delay, base_delay);
144 :
145 1020 : return crypto_rand_int_range(low_bound, high_bound);
146 : }
147 :
148 : /** Find the current delay for dls based on min_delay.
149 : *
150 : * This function sets dls->next_attempt_at based on now, and returns the delay.
151 : * Helper for download_status_increment_failure and
152 : * download_status_increment_attempt. */
153 : STATIC int
154 4004 : download_status_schedule_get_delay(download_status_t *dls,
155 : int min_delay,
156 : time_t now)
157 : {
158 4004 : tor_assert(dls);
159 : /* If we're using random exponential backoff, we do need min/max delay */
160 4004 : tor_assert(min_delay >= 0);
161 :
162 4004 : int delay = INT_MAX;
163 4004 : uint8_t dls_schedule_position = (dls->increment_on
164 4004 : == DL_SCHED_INCREMENT_ATTEMPT
165 : ? dls->n_download_attempts
166 : : dls->n_download_failures);
167 :
168 : /* Check if we missed a reset somehow */
169 4004 : IF_BUG_ONCE(dls->last_backoff_position > dls_schedule_position) {
170 0 : dls->last_backoff_position = 0;
171 0 : dls->last_delay_used = 0;
172 : }
173 :
174 4004 : if (dls_schedule_position > 0) {
175 4000 : delay = dls->last_delay_used;
176 :
177 5020 : while (dls->last_backoff_position < dls_schedule_position) {
178 : /* Do one increment step */
179 1020 : delay = next_random_exponential_delay(delay, min_delay);
180 : /* Update our position */
181 1020 : ++(dls->last_backoff_position);
182 : }
183 : } else {
184 : /* If we're just starting out, use the minimum delay */
185 : delay = min_delay;
186 : }
187 :
188 : /* Clamp it within min/max if we have them */
189 4004 : if (min_delay >= 0 && delay < min_delay) delay = min_delay;
190 :
191 : /* Store it for next time */
192 4004 : dls->last_backoff_position = dls_schedule_position;
193 4004 : dls->last_delay_used = delay;
194 :
195 : /* A negative delay makes no sense. Knowing that delay is
196 : * non-negative allows us to safely do the wrapping check below. */
197 4004 : tor_assert(delay >= 0);
198 :
199 : /* Avoid now+delay overflowing TIME_MAX, by comparing with a subtraction
200 : * that won't overflow (since delay is non-negative). */
201 4004 : if (delay < INT_MAX && now <= TIME_MAX - delay) {
202 4004 : dls->next_attempt_at = now+delay;
203 : } else {
204 0 : dls->next_attempt_at = TIME_MAX;
205 : }
206 :
207 4004 : return delay;
208 : }
209 :
210 : /* Log a debug message about item, which increments on increment_action, has
211 : * incremented dls_n_download_increments times. The message varies based on
212 : * was_schedule_incremented (if not, not_incremented_response is logged), and
213 : * the values of increment, dls_next_attempt_at, and now.
214 : * Helper for download_status_increment_failure and
215 : * download_status_increment_attempt. */
216 : static void
217 4 : download_status_log_helper(const char *item, int was_schedule_incremented,
218 : const char *increment_action,
219 : const char *not_incremented_response,
220 : uint8_t dls_n_download_increments, int increment,
221 : time_t dls_next_attempt_at, time_t now)
222 : {
223 4 : if (item) {
224 0 : if (!was_schedule_incremented)
225 0 : log_debug(LD_DIR, "%s %s %d time(s); I'll try again %s.",
226 : item, increment_action, (int)dls_n_download_increments,
227 : not_incremented_response);
228 0 : else if (increment == 0)
229 0 : log_debug(LD_DIR, "%s %s %d time(s); I'll try again immediately.",
230 : item, increment_action, (int)dls_n_download_increments);
231 0 : else if (dls_next_attempt_at < TIME_MAX)
232 0 : log_debug(LD_DIR, "%s %s %d time(s); I'll try again in %d seconds.",
233 : item, increment_action, (int)dls_n_download_increments,
234 : (int)(dls_next_attempt_at-now));
235 : else
236 0 : log_debug(LD_DIR, "%s %s %d time(s); Giving up for a while.",
237 : item, increment_action, (int)dls_n_download_increments);
238 : }
239 4 : }
240 :
241 : /** Determine when a failed download attempt should be retried.
242 : * Called when an attempt to download <b>dls</b> has failed with HTTP status
243 : * <b>status_code</b>. Increment the failure count (if the code indicates a
244 : * real failure, or if we're a server) and set <b>dls</b>-\>next_attempt_at to
245 : * an appropriate time in the future and return it.
246 : * If <b>dls->increment_on</b> is DL_SCHED_INCREMENT_ATTEMPT, increment the
247 : * failure count, and return a time in the far future for the next attempt (to
248 : * avoid an immediate retry). */
249 : time_t
250 4 : download_status_increment_failure(download_status_t *dls, int status_code,
251 : const char *item, int server, time_t now)
252 : {
253 4 : (void) status_code; // XXXX no longer used.
254 4 : (void) server; // XXXX no longer used.
255 4 : int increment = -1;
256 4 : int min_delay = 0;
257 :
258 4 : tor_assert(dls);
259 :
260 : /* dls wasn't reset before it was used */
261 4 : if (dls->next_attempt_at == 0) {
262 4 : download_status_reset(dls);
263 : }
264 :
265 : /* count the failure */
266 4 : if (dls->n_download_failures < IMPOSSIBLE_TO_DOWNLOAD-1) {
267 4 : ++dls->n_download_failures;
268 : }
269 :
270 4 : if (dls->increment_on == DL_SCHED_INCREMENT_FAILURE) {
271 : /* We don't find out that a failure-based schedule has attempted a
272 : * connection until that connection fails.
273 : * We'll never find out about successful connections, but this doesn't
274 : * matter, because schedules are reset after a successful download.
275 : */
276 4 : if (dls->n_download_attempts < IMPOSSIBLE_TO_DOWNLOAD-1)
277 4 : ++dls->n_download_attempts;
278 :
279 : /* only return a failure retry time if this schedule increments on failures
280 : */
281 4 : min_delay = find_dl_min_delay(dls, get_options());
282 4 : increment = download_status_schedule_get_delay(dls, min_delay, now);
283 : }
284 :
285 4 : download_status_log_helper(item, !dls->increment_on, "failed",
286 4 : "concurrently", dls->n_download_failures,
287 : increment,
288 : download_status_get_next_attempt_at(dls),
289 : now);
290 :
291 4 : if (dls->increment_on == DL_SCHED_INCREMENT_ATTEMPT) {
292 : /* stop this schedule retrying on failure, it will launch concurrent
293 : * connections instead */
294 : return TIME_MAX;
295 : } else {
296 4 : return download_status_get_next_attempt_at(dls);
297 : }
298 : }
299 :
300 : /** Determine when the next download attempt should be made when using an
301 : * attempt-based (potentially concurrent) download schedule.
302 : * Called when an attempt to download <b>dls</b> is being initiated.
303 : * Increment the attempt count and set <b>dls</b>-\>next_attempt_at to an
304 : * appropriate time in the future and return it.
305 : * If <b>dls->increment_on</b> is DL_SCHED_INCREMENT_FAILURE, don't increment
306 : * the attempts, and return a time in the far future (to avoid launching a
307 : * concurrent attempt). */
308 : time_t
309 0 : download_status_increment_attempt(download_status_t *dls, const char *item,
310 : time_t now)
311 : {
312 0 : int delay = -1;
313 0 : int min_delay = 0;
314 :
315 0 : tor_assert(dls);
316 :
317 : /* dls wasn't reset before it was used */
318 0 : if (dls->next_attempt_at == 0) {
319 0 : download_status_reset(dls);
320 : }
321 :
322 0 : if (dls->increment_on == DL_SCHED_INCREMENT_FAILURE) {
323 : /* this schedule should retry on failure, and not launch any concurrent
324 : attempts */
325 0 : log_warn(LD_BUG, "Tried to launch an attempt-based connection on a "
326 : "failure-based schedule.");
327 0 : return TIME_MAX;
328 : }
329 :
330 0 : if (dls->n_download_attempts < IMPOSSIBLE_TO_DOWNLOAD-1)
331 0 : ++dls->n_download_attempts;
332 :
333 0 : min_delay = find_dl_min_delay(dls, get_options());
334 0 : delay = download_status_schedule_get_delay(dls, min_delay, now);
335 :
336 0 : download_status_log_helper(item, dls->increment_on, "attempted",
337 0 : "on failure", dls->n_download_attempts,
338 : delay, download_status_get_next_attempt_at(dls),
339 : now);
340 :
341 0 : return download_status_get_next_attempt_at(dls);
342 : }
343 :
344 : static time_t
345 102 : download_status_get_initial_delay_from_now(const download_status_t *dls)
346 : {
347 : /* We use constant initial delays, even in exponential backoff
348 : * schedules. */
349 102 : return time(NULL) + find_dl_min_delay(dls, get_options());
350 : }
351 :
352 : /** Reset <b>dls</b> so that it will be considered downloadable
353 : * immediately, and/or to show that we don't need it anymore.
354 : *
355 : * Must be called to initialise a download schedule, otherwise the zeroth item
356 : * in the schedule will never be used.
357 : *
358 : * (We find the zeroth element of the download schedule, and set
359 : * next_attempt_at to be the appropriate offset from 'now'. In most
360 : * cases this means setting it to 'now', so the item will be immediately
361 : * downloadable; when using authorities with fallbacks, there is a few seconds'
362 : * delay.) */
363 : void
364 98 : download_status_reset(download_status_t *dls)
365 : {
366 98 : if (dls->n_download_failures == IMPOSSIBLE_TO_DOWNLOAD
367 98 : || dls->n_download_attempts == IMPOSSIBLE_TO_DOWNLOAD)
368 : return; /* Don't reset this. */
369 :
370 98 : dls->n_download_failures = 0;
371 98 : dls->n_download_attempts = 0;
372 98 : dls->next_attempt_at = download_status_get_initial_delay_from_now(dls);
373 98 : dls->last_backoff_position = 0;
374 98 : dls->last_delay_used = 0;
375 : /* Don't reset dls->want_authority or dls->increment_on */
376 : }
377 :
378 : /** Return true iff, as of <b>now</b>, the resource tracked by <b>dls</b> is
379 : * ready to get its download reattempted. */
380 : int
381 79 : download_status_is_ready(download_status_t *dls, time_t now)
382 : {
383 : /* dls wasn't reset before it was used */
384 79 : if (dls->next_attempt_at == 0) {
385 79 : download_status_reset(dls);
386 : }
387 :
388 79 : return download_status_get_next_attempt_at(dls) <= now;
389 : }
390 :
391 : /** Mark <b>dl</b> as never downloadable. */
392 : void
393 6 : download_status_mark_impossible(download_status_t *dl)
394 : {
395 6 : dl->n_download_failures = IMPOSSIBLE_TO_DOWNLOAD;
396 6 : dl->n_download_attempts = IMPOSSIBLE_TO_DOWNLOAD;
397 6 : }
398 :
399 : /** Return the number of failures on <b>dls</b> since the last success (if
400 : * any). */
401 : int
402 2 : download_status_get_n_failures(const download_status_t *dls)
403 : {
404 2 : return dls->n_download_failures;
405 : }
406 :
407 : /** Return the number of attempts to download <b>dls</b> since the last success
408 : * (if any). This can differ from download_status_get_n_failures() due to
409 : * outstanding concurrent attempts. */
410 : int
411 2 : download_status_get_n_attempts(const download_status_t *dls)
412 : {
413 2 : return dls->n_download_attempts;
414 : }
415 :
416 : /** Return the next time to attempt to download <b>dls</b>. */
417 : time_t
418 107 : download_status_get_next_attempt_at(const download_status_t *dls)
419 : {
420 : /* dls wasn't reset before it was used */
421 107 : if (dls->next_attempt_at == 0) {
422 : /* so give the answer we would have given if it had been */
423 4 : return download_status_get_initial_delay_from_now(dls);
424 : }
425 :
426 : return dls->next_attempt_at;
427 : }
|
