tor  0.4.2.1-alpha-dev
dlstatus.c
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 #define DLSTATUS_PRIVATE
7 
8 #include "core/or/or.h"
9 
10 #include "app/config/config.h"
16 
17 #include "feature/dirclient/download_status_st.h"
18 
26 STATIC int
27 find_dl_min_delay(const download_status_t *dls, const or_options_t *options)
28 {
29  tor_assert(dls);
30  tor_assert(options);
31 
32  switch (dls->schedule) {
33  case DL_SCHED_GENERIC:
34  /* Any other directory document */
35  if (dir_server_mode(options)) {
36  /* A directory authority or directory mirror */
37  return options->TestingServerDownloadInitialDelay;
38  } else {
39  return options->TestingClientDownloadInitialDelay;
40  }
41  case DL_SCHED_CONSENSUS:
43  /* A public relay */
45  } else {
46  /* A client or bridge */
47  if (networkstatus_consensus_is_bootstrapping(time(NULL))) {
48  /* During bootstrapping */
49  if (!networkstatus_consensus_can_use_extra_fallbacks(options)) {
50  /* A bootstrapping client without extra fallback directories */
51  return options->
52  ClientBootstrapConsensusAuthorityOnlyDownloadInitialDelay;
53  } else if (dls->want_authority) {
54  /* A bootstrapping client with extra fallback directories, but
55  * connecting to an authority */
56  return
58  } else {
59  /* A bootstrapping client connecting to extra fallback directories
60  */
61  return
63  }
64  } else {
65  /* A client with a reasonably live consensus, with or without
66  * certificates */
68  }
69  }
70  case DL_SCHED_BRIDGE:
71  if (options->UseBridges && num_bridges_usable(0) > 0) {
72  /* A bridge client that is sure that one or more of its bridges are
73  * running can afford to wait longer to update bridge descriptors. */
74  return options->TestingBridgeDownloadInitialDelay;
75  } else {
76  /* A bridge client which might have no running bridges, must try to
77  * get bridge descriptors straight away. */
79  }
80  default:
81  tor_assert(0);
82  }
83 
84  /* Impossible, but gcc will fail with -Werror without a `return`. */
85  return 0;
86 }
87 
94 STATIC void
95 next_random_exponential_delay_range(int *low_bound_out,
96  int *high_bound_out,
97  int delay,
98  int base_delay)
99 {
100  // This is the "decorrelated jitter" approach, from
101  // https://www.awsarchitectureblog.com/2015/03/backoff.html
102  // The formula is
103  // sleep = min(cap, random_between(base, sleep * 3))
104 
105  const int delay_times_3 = delay < INT_MAX/3 ? delay * 3 : INT_MAX;
106  *low_bound_out = base_delay;
107  if (delay_times_3 > base_delay) {
108  *high_bound_out = delay_times_3;
109  } else {
110  *high_bound_out = base_delay+1;
111  }
112 }
113 
124 STATIC int
125 next_random_exponential_delay(int delay,
126  int base_delay)
127 {
128  /* Check preconditions */
129  if (BUG(delay < 0))
130  delay = 0;
131 
132  if (base_delay < 1)
133  base_delay = 1;
134 
135  int low_bound=0, high_bound=INT_MAX;
136 
137  next_random_exponential_delay_range(&low_bound, &high_bound,
138  delay, base_delay);
139 
140  return crypto_rand_int_range(low_bound, high_bound);
141 }
142 
148 STATIC int
149 download_status_schedule_get_delay(download_status_t *dls,
150  int min_delay,
151  time_t now)
152 {
153  tor_assert(dls);
154  /* If we're using random exponential backoff, we do need min/max delay */
155  tor_assert(min_delay >= 0);
156 
157  int delay = INT_MAX;
158  uint8_t dls_schedule_position = (dls->increment_on
159  == DL_SCHED_INCREMENT_ATTEMPT
160  ? dls->n_download_attempts
161  : dls->n_download_failures);
162 
163  /* Check if we missed a reset somehow */
164  IF_BUG_ONCE(dls->last_backoff_position > dls_schedule_position) {
165  dls->last_backoff_position = 0;
166  dls->last_delay_used = 0;
167  }
168 
169  if (dls_schedule_position > 0) {
170  delay = dls->last_delay_used;
171 
172  while (dls->last_backoff_position < dls_schedule_position) {
173  /* Do one increment step */
174  delay = next_random_exponential_delay(delay, min_delay);
175  /* Update our position */
176  ++(dls->last_backoff_position);
177  }
178  } else {
179  /* If we're just starting out, use the minimum delay */
180  delay = min_delay;
181  }
182 
183  /* Clamp it within min/max if we have them */
184  if (min_delay >= 0 && delay < min_delay) delay = min_delay;
185 
186  /* Store it for next time */
187  dls->last_backoff_position = dls_schedule_position;
188  dls->last_delay_used = delay;
189 
190  /* A negative delay makes no sense. Knowing that delay is
191  * non-negative allows us to safely do the wrapping check below. */
192  tor_assert(delay >= 0);
193 
194  /* Avoid now+delay overflowing TIME_MAX, by comparing with a subtraction
195  * that won't overflow (since delay is non-negative). */
196  if (delay < INT_MAX && now <= TIME_MAX - delay) {
197  dls->next_attempt_at = now+delay;
198  } else {
199  dls->next_attempt_at = TIME_MAX;
200  }
201 
202  return delay;
203 }
204 
205 /* Log a debug message about item, which increments on increment_action, has
206  * incremented dls_n_download_increments times. The message varies based on
207  * was_schedule_incremented (if not, not_incremented_response is logged), and
208  * the values of increment, dls_next_attempt_at, and now.
209  * Helper for download_status_increment_failure and
210  * download_status_increment_attempt. */
211 static void
212 download_status_log_helper(const char *item, int was_schedule_incremented,
213  const char *increment_action,
214  const char *not_incremented_response,
215  uint8_t dls_n_download_increments, int increment,
216  time_t dls_next_attempt_at, time_t now)
217 {
218  if (item) {
219  if (!was_schedule_incremented)
220  log_debug(LD_DIR, "%s %s %d time(s); I'll try again %s.",
221  item, increment_action, (int)dls_n_download_increments,
222  not_incremented_response);
223  else if (increment == 0)
224  log_debug(LD_DIR, "%s %s %d time(s); I'll try again immediately.",
225  item, increment_action, (int)dls_n_download_increments);
226  else if (dls_next_attempt_at < TIME_MAX)
227  log_debug(LD_DIR, "%s %s %d time(s); I'll try again in %d seconds.",
228  item, increment_action, (int)dls_n_download_increments,
229  (int)(dls_next_attempt_at-now));
230  else
231  log_debug(LD_DIR, "%s %s %d time(s); Giving up for a while.",
232  item, increment_action, (int)dls_n_download_increments);
233  }
234 }
235 
244 time_t
246  const char *item, int server, time_t now)
247 {
248  (void) status_code; // XXXX no longer used.
249  (void) server; // XXXX no longer used.
250  int increment = -1;
251  int min_delay = 0;
252 
253  tor_assert(dls);
254 
255  /* dls wasn't reset before it was used */
256  if (dls->next_attempt_at == 0) {
258  }
259 
260  /* count the failure */
262  ++dls->n_download_failures;
263  }
264 
265  if (dls->increment_on == DL_SCHED_INCREMENT_FAILURE) {
266  /* We don't find out that a failure-based schedule has attempted a
267  * connection until that connection fails.
268  * We'll never find out about successful connections, but this doesn't
269  * matter, because schedules are reset after a successful download.
270  */
272  ++dls->n_download_attempts;
273 
274  /* only return a failure retry time if this schedule increments on failures
275  */
276  min_delay = find_dl_min_delay(dls, get_options());
277  increment = download_status_schedule_get_delay(dls, min_delay, now);
278  }
279 
280  download_status_log_helper(item, !dls->increment_on, "failed",
281  "concurrently", dls->n_download_failures,
282  increment,
284  now);
285 
286  if (dls->increment_on == DL_SCHED_INCREMENT_ATTEMPT) {
287  /* stop this schedule retrying on failure, it will launch concurrent
288  * connections instead */
289  return TIME_MAX;
290  } else {
292  }
293 }
294 
303 time_t
305  time_t now)
306 {
307  int delay = -1;
308  int min_delay = 0;
309 
310  tor_assert(dls);
311 
312  /* dls wasn't reset before it was used */
313  if (dls->next_attempt_at == 0) {
315  }
316 
317  if (dls->increment_on == DL_SCHED_INCREMENT_FAILURE) {
318  /* this schedule should retry on failure, and not launch any concurrent
319  attempts */
320  log_warn(LD_BUG, "Tried to launch an attempt-based connection on a "
321  "failure-based schedule.");
322  return TIME_MAX;
323  }
324 
326  ++dls->n_download_attempts;
327 
328  min_delay = find_dl_min_delay(dls, get_options());
329  delay = download_status_schedule_get_delay(dls, min_delay, now);
330 
331  download_status_log_helper(item, dls->increment_on, "attempted",
332  "on failure", dls->n_download_attempts,
334  now);
335 
337 }
338 
339 static time_t
340 download_status_get_initial_delay_from_now(const download_status_t *dls)
341 {
342  /* We use constant initial delays, even in exponential backoff
343  * schedules. */
344  return time(NULL) + find_dl_min_delay(dls, get_options());
345 }
346 
358 void
360 {
363  return; /* Don't reset this. */
364 
365  dls->n_download_failures = 0;
366  dls->n_download_attempts = 0;
367  dls->next_attempt_at = download_status_get_initial_delay_from_now(dls);
368  dls->last_backoff_position = 0;
369  dls->last_delay_used = 0;
370  /* Don't reset dls->want_authority or dls->increment_on */
371 }
372 
375 int
377 {
378  /* dls wasn't reset before it was used */
379  if (dls->next_attempt_at == 0) {
381  }
382 
383  return download_status_get_next_attempt_at(dls) <= now;
384 }
385 
387 void
389 {
392 }
393 
396 int
398 {
399  return dls->n_download_failures;
400 }
401 
405 int
407 {
408  return dls->n_download_attempts;
409 }
410 
412 time_t
414 {
415  /* dls wasn't reset before it was used */
416  if (dls->next_attempt_at == 0) {
417  /* so give the answer we would have given if it had been */
418  return download_status_get_initial_delay_from_now(dls);
419  }
420 
421  return dls->next_attempt_at;
422 }
int ClientBootstrapConsensusFallbackDownloadInitialDelay
int download_status_get_n_failures(const download_status_t *dls)
Definition: dlstatus.c:397
Header file for circuitbuild.c.
Common functions for using (pseudo-)random number generators.
int dir_server_mode(const or_options_t *options)
Definition: routermode.c:20
void download_status_reset(download_status_t *dls)
Definition: dlstatus.c:359
time_t download_status_get_next_attempt_at(const download_status_t *dls)
Definition: dlstatus.c:413
int networkstatus_consensus_can_use_multiple_directories(const or_options_t *options)
Header file for config.c.
#define IMPOSSIBLE_TO_DOWNLOAD
Definition: or.h:798
int crypto_rand_int_range(unsigned int min, unsigned int max)
int download_status_is_ready(download_status_t *dls, time_t now)
Definition: dlstatus.c:376
time_t download_status_increment_attempt(download_status_t *dls, const char *item, time_t now)
Definition: dlstatus.c:304
download_schedule_bitfield_t schedule
tor_assert(buffer)
Header file for routermode.c.
void download_status_mark_impossible(download_status_t *dl)
Definition: dlstatus.c:388
Master header file for Tor-specific functionality.
int ClientBootstrapConsensusAuthorityDownloadInitialDelay
time_t download_status_increment_failure(download_status_t *dls, int status_code, const char *item, int server, time_t now)
Definition: dlstatus.c:245
int TestingServerConsensusDownloadInitialDelay
download_schedule_increment_bitfield_t increment_on
#define LD_DIR
Definition: log.h:86
int TestingBridgeDownloadInitialDelay
#define IF_BUG_ONCE(cond)
Definition: util_bug.h:234
int TestingBridgeBootstrapDownloadInitialDelay
download_want_authority_bitfield_t want_authority
Header file for dlstatus.c.
int download_status_get_n_attempts(const download_status_t *dls)
Definition: dlstatus.c:406
int TestingClientConsensusDownloadInitialDelay
int TestingClientDownloadInitialDelay
int TestingServerDownloadInitialDelay
Header file for networkstatus.c.
#define LD_BUG
Definition: log.h:84