Tor  0.4.3.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-2019, 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  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  return options->TestingBridgeDownloadInitialDelay;
80  } else {
81  /* A bridge client which might have no running bridges, must try to
82  * get bridge descriptors straight away. */
84  }
85  default:
86  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
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  const int delay_times_3 = delay < INT_MAX/3 ? delay * 3 : INT_MAX;
111  *low_bound_out = base_delay;
112  if (delay_times_3 > base_delay) {
113  *high_bound_out = delay_times_3;
114  } else {
115  *high_bound_out = base_delay+1;
116  }
117 }
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
131  int base_delay)
132 {
133  /* Check preconditions */
134  if (BUG(delay < 0))
135  delay = 0;
136 
137  if (base_delay < 1)
138  base_delay = 1;
139 
140  int low_bound=0, high_bound=INT_MAX;
141 
142  next_random_exponential_delay_range(&low_bound, &high_bound,
143  delay, base_delay);
144 
145  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
155  int min_delay,
156  time_t now)
157 {
158  tor_assert(dls);
159  /* If we're using random exponential backoff, we do need min/max delay */
160  tor_assert(min_delay >= 0);
161 
162  int delay = INT_MAX;
163  uint8_t dls_schedule_position = (dls->increment_on
164  == DL_SCHED_INCREMENT_ATTEMPT
165  ? dls->n_download_attempts
166  : dls->n_download_failures);
167 
168  /* Check if we missed a reset somehow */
169  IF_BUG_ONCE(dls->last_backoff_position > dls_schedule_position) {
170  dls->last_backoff_position = 0;
171  dls->last_delay_used = 0;
172  }
173 
174  if (dls_schedule_position > 0) {
175  delay = dls->last_delay_used;
176 
177  while (dls->last_backoff_position < dls_schedule_position) {
178  /* Do one increment step */
179  delay = next_random_exponential_delay(delay, min_delay);
180  /* Update our position */
181  ++(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  if (min_delay >= 0 && delay < min_delay) delay = min_delay;
190 
191  /* Store it for next time */
192  dls->last_backoff_position = dls_schedule_position;
193  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  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  if (delay < INT_MAX && now <= TIME_MAX - delay) {
202  dls->next_attempt_at = now+delay;
203  } else {
204  dls->next_attempt_at = TIME_MAX;
205  }
206 
207  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 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  if (item) {
224  if (!was_schedule_incremented)
225  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  else if (increment == 0)
229  log_debug(LD_DIR, "%s %s %d time(s); I'll try again immediately.",
230  item, increment_action, (int)dls_n_download_increments);
231  else if (dls_next_attempt_at < TIME_MAX)
232  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  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 }
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
251  const char *item, int server, time_t now)
252 {
253  (void) status_code; // XXXX no longer used.
254  (void) server; // XXXX no longer used.
255  int increment = -1;
256  int min_delay = 0;
257 
258  tor_assert(dls);
259 
260  /* dls wasn't reset before it was used */
261  if (dls->next_attempt_at == 0) {
263  }
264 
265  /* count the failure */
267  ++dls->n_download_failures;
268  }
269 
270  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  */
277  ++dls->n_download_attempts;
278 
279  /* only return a failure retry time if this schedule increments on failures
280  */
281  min_delay = find_dl_min_delay(dls, get_options());
282  increment = download_status_schedule_get_delay(dls, min_delay, now);
283  }
284 
285  download_status_log_helper(item, !dls->increment_on, "failed",
286  "concurrently", dls->n_download_failures,
287  increment,
289  now);
290 
291  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 {
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
310  time_t now)
311 {
312  int delay = -1;
313  int min_delay = 0;
314 
315  tor_assert(dls);
316 
317  /* dls wasn't reset before it was used */
318  if (dls->next_attempt_at == 0) {
320  }
321 
322  if (dls->increment_on == DL_SCHED_INCREMENT_FAILURE) {
323  /* this schedule should retry on failure, and not launch any concurrent
324  attempts */
325  log_warn(LD_BUG, "Tried to launch an attempt-based connection on a "
326  "failure-based schedule.");
327  return TIME_MAX;
328  }
329 
331  ++dls->n_download_attempts;
332 
333  min_delay = find_dl_min_delay(dls, get_options());
334  delay = download_status_schedule_get_delay(dls, min_delay, now);
335 
336  download_status_log_helper(item, dls->increment_on, "attempted",
337  "on failure", dls->n_download_attempts,
339  now);
340 
342 }
343 
344 static time_t
345 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  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
365 {
368  return; /* Don't reset this. */
369 
370  dls->n_download_failures = 0;
371  dls->n_download_attempts = 0;
372  dls->next_attempt_at = download_status_get_initial_delay_from_now(dls);
373  dls->last_backoff_position = 0;
374  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
382 {
383  /* dls wasn't reset before it was used */
384  if (dls->next_attempt_at == 0) {
386  }
387 
388  return download_status_get_next_attempt_at(dls) <= now;
389 }
390 
391 /** Mark <b>dl</b> as never downloadable. */
392 void
394 {
397 }
398 
399 /** Return the number of failures on <b>dls</b> since the last success (if
400  * any). */
401 int
403 {
404  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
412 {
413  return dls->n_download_attempts;
414 }
415 
416 /** Return the next time to attempt to download <b>dls</b>. */
417 time_t
419 {
420  /* dls wasn't reset before it was used */
421  if (dls->next_attempt_at == 0) {
422  /* so give the answer we would have given if it had been */
423  return download_status_get_initial_delay_from_now(dls);
424  }
425 
426  return dls->next_attempt_at;
427 }
Header file for circuitbuild.c.
Common functions for using (pseudo-)random number generators.
int ClientBootstrapConsensusFallbackDownloadInitialDelay
int TestingClientDownloadInitialDelay
int TestingServerDownloadInitialDelay
int TestingBridgeBootstrapDownloadInitialDelay
int download_status_get_n_failures(const download_status_t *dls)
Definition: dlstatus.c:402
int download_status_get_n_attempts(const download_status_t *dls)
Definition: dlstatus.c:411
int networkstatus_consensus_can_use_multiple_directories(const or_options_t *options)
Header file for config.c.
const or_options_t * get_options(void)
Definition: config.c:941
#define tor_assert(expr)
Definition: util_bug.h:102
int TestingBridgeDownloadInitialDelay
#define IMPOSSIBLE_TO_DOWNLOAD
Definition: or.h:798
int crypto_rand_int_range(unsigned int min, unsigned int max)
time_t download_status_increment_attempt(download_status_t *dls, const char *item, time_t now)
Definition: dlstatus.c:309
int networkstatus_consensus_can_use_extra_fallbacks(const or_options_t *options)
int dir_server_mode(const or_options_t *options)
Definition: routermode.c:23
download_schedule_increment_bitfield_t increment_on
time_t download_status_increment_failure(download_status_t *dls, int status_code, const char *item, int server, time_t now)
Definition: dlstatus.c:250
#define STATIC
Definition: testsupport.h:32
STATIC int next_random_exponential_delay(int delay, int base_delay)
Definition: dlstatus.c:130
Header file for routermode.c.
int num_bridges_usable(int use_maybe_reachable)
Definition: entrynodes.c:3294
Master header file for Tor-specific functionality.
STATIC int download_status_schedule_get_delay(download_status_t *dls, int min_delay, time_t now)
Definition: dlstatus.c:154
void download_status_reset(download_status_t *dls)
Definition: dlstatus.c:364
int TestingClientConsensusDownloadInitialDelay
int TestingServerConsensusDownloadInitialDelay
#define LD_DIR
Definition: log.h:88
#define IF_BUG_ONCE(cond)
Definition: util_bug.h:239
STATIC int find_dl_min_delay(const download_status_t *dls, const or_options_t *options)
Definition: dlstatus.c:32
Header file for dlstatus.c.
int networkstatus_consensus_is_bootstrapping(time_t now)
int ClientBootstrapConsensusAuthorityDownloadInitialDelay
STATIC void next_random_exponential_delay_range(int *low_bound_out, int *high_bound_out, int delay, int base_delay)
Definition: dlstatus.c:100
download_want_authority_bitfield_t want_authority
void download_status_mark_impossible(download_status_t *dl)
Definition: dlstatus.c:393
int download_status_is_ready(download_status_t *dls, time_t now)
Definition: dlstatus.c:381
time_t download_status_get_next_attempt_at(const download_status_t *dls)
Definition: dlstatus.c:418
download_schedule_bitfield_t schedule
Header file for networkstatus.c.
#define LD_BUG
Definition: log.h:86
Directory download status/schedule structure.