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