circuitbuild.c 143 KB
Newer Older
Roger Dingledine's avatar
Roger Dingledine committed
1
2
/* Copyright (c) 2001 Matej Pfajfar.
 * Copyright (c) 2001-2004, Roger Dingledine.
3
 * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
4
 * Copyright (c) 2007-2010, The Tor Project, Inc. */
5
6
7
8
9
10
11
/* See LICENSE for licensing information */

/**
 * \file circuitbuild.c
 * \brief The actual details of building circuits.
 **/

Mike Perry's avatar
Mike Perry committed
12
#define CIRCUIT_PRIVATE
13

Mike Perry's avatar
Mike Perry committed
14
15
#include "or.h"
#include "crypto.h"
16
17
#undef log
#include <math.h>
18

Roger Dingledine's avatar
Roger Dingledine committed
19
20
21
22
#ifndef MIN
#define MIN(a,b) ((a)<(b)?(a):(b))
#endif

23
/********* START VARIABLES **********/
24
/** Global list of circuit build times */
25
// FIXME: Add this as a member for entry_guard_t instead of global?
Mike Perry's avatar
Mike Perry committed
26
27
28
29
// Then we could do per-guard statistics, as guards are likely to
// vary in their own latency. The downside of this is that guards
// can change frequently, so we'd be building a lot more circuits
// most likely.
30
circuit_build_times_t circ_times;
31
32
33
34

/** A global list of all circuits at this hop. */
extern circuit_t *global_circuitlist;

35
/** An entry_guard_t represents our information about a chosen long-term
36
37
38
 * first hop, known as a "helper" node in the literature. We can't just
 * use a routerinfo_t, since we want to remember these even when we
 * don't have a directory. */
39
40
41
typedef struct {
  char nickname[MAX_NICKNAME_LEN+1];
  char identity[DIGEST_LEN];
42
43
44
45
  time_t chosen_on_date; /**< Approximately when was this guard added?
                          * "0" if we don't know. */
  char *chosen_by_version; /**< What tor version added this guard? NULL
                            * if we don't know. */
46
47
48
49
  unsigned int made_contact : 1; /**< 0 if we have never connected to this
                                  * router, 1 if we have. */
  unsigned int can_retry : 1; /**< Should we retry connecting to this entry,
                               * in spite of having it marked as unreachable?*/
50
51
52
53
54
55
  time_t bad_since; /**< 0 if this guard is currently usable, or the time at
                      * which it was observed to become (according to the
                      * directory or the user configuration) unusable. */
  time_t unreachable_since; /**< 0 if we can connect to this guard, or the
                             * time at which we first noticed we couldn't
                             * connect to it. */
56
57
  time_t last_attempted; /**< 0 if we can connect to this guard, or the time
                          * at which we last failed to connect to it. */
58
} entry_guard_t;
59

60
61
62
/** A list of our chosen entry guards. */
static smartlist_t *entry_guards = NULL;
/** A value of 1 means that the entry_guards list has changed
63
 * and those changes need to be flushed to disk. */
64
static int entry_guards_dirty = 0;
65

66
/** If set, we're running the unit tests: we should avoid clobbering
67
 * our state file or accessing get_options() or get_or_state() */
68
69
static int unit_tests = 0;

70
71
/********* END VARIABLES ************/

72
static int circuit_deliver_create_cell(circuit_t *circ,
73
                                       uint8_t cell_type, const char *payload);
74
static int onion_pick_cpath_exit(origin_circuit_t *circ, extend_info_t *exit);
75
static crypt_path_t *onion_next_hop_in_cpath(crypt_path_t *cpath);
Roger Dingledine's avatar
Roger Dingledine committed
76
static int onion_extend_cpath(origin_circuit_t *circ);
77
static int count_acceptable_routers(smartlist_t *routers);
78
static int onion_append_hop(crypt_path_t **head_ptr, extend_info_t *choice);
79

80
static void entry_guards_changed(void);
81

Mike Perry's avatar
Mike Perry committed
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
static int32_t
circuit_build_times_max_timeouts(void)
{
  int32_t num = networkstatus_get_param(NULL, "cbtmaxtimeouts",
          CBT_DEFAULT_MAX_RECENT_TIMEOUT_COUNT);
  return num;
}

static int32_t
circuit_build_times_min_circs_to_observe(void)
{
  int32_t num = networkstatus_get_param(NULL, "cbtmincircs",
                CBT_DEFAULT_MIN_CIRCUITS_TO_OBSERVE);
  return num;
}

double
circuit_build_times_quantile_cutoff(void)
{
  int32_t num = networkstatus_get_param(NULL, "cbtquantile",
                CBT_DEFAULT_QUANTILE_CUTOFF);
  return num/100.0;
}

static int32_t
circuit_build_times_test_frequency(void)
{
  int32_t num = networkstatus_get_param(NULL, "cbttestfreq",
                CBT_DEFAULT_TEST_FREQUENCY);
  return num;
}

static int32_t
circuit_build_times_min_timeout(void)
{
  int32_t num = networkstatus_get_param(NULL, "cbtmintimeout",
                CBT_DEFAULT_TIMEOUT_MIN_VALUE);
  return num;
}

int32_t
circuit_build_times_initial_timeout(void)
{
  int32_t num = networkstatus_get_param(NULL, "cbtinitialtimeout",
                CBT_DEFAULT_TIMEOUT_INITIAL_VALUE);
  return num;
}

static int32_t
circuit_build_times_recent_circuit_count(void)
{
  int32_t num = networkstatus_get_param(NULL, "cbtrecentcount",
                CBT_DEFAULT_RECENT_CIRCUITS);
  return num;
}

138
139
140
141
142
143
/**
 * This function is called when we get a consensus update.
 *
 * It checks to see if we have changed any consensus parameters
 * that require reallocation or discard of previous stats.
 */
Mike Perry's avatar
Mike Perry committed
144
145
146
147
148
149
150
151
152
153
154
155
156
157
void
circuit_build_times_new_consensus_params(circuit_build_times_t *cbt,
                                         networkstatus_t *ns)
{
  int32_t num = networkstatus_get_param(ns, "cbtrecentcount",
                   CBT_DEFAULT_RECENT_CIRCUITS);

  if (num != cbt->liveness.num_recent_circs) {
    int8_t *recent_circs;
    log_notice(LD_CIRC, "Changing recent timeout size from %d to %d",
               cbt->liveness.num_recent_circs, num);

    tor_assert(num > 0);
    tor_assert(cbt->liveness.timeouts_after_firsthop);
158
159
160
161
162
163
164
165
166
167
168
169
170

    /*
     * Technically this is a circular array that we are reallocating
     * and memcopying. However, since it only consists of either 1s
     * or 0s, and is only used in a statistical test to determine when
     * we should discard our history after a sufficient number of 1's
     * have been reached, it is fine if order is not preserved or
     * elements are lost.
     *
     * cbtrecentcount should only be changing in cases of severe network
     * distress anyway, so memory correctness here is paramount over
     * doing acrobatics to preserve the array.
     */
Mike Perry's avatar
Mike Perry committed
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
    recent_circs = tor_malloc_zero(sizeof(int8_t)*num);
    memcpy(recent_circs, cbt->liveness.timeouts_after_firsthop,
           sizeof(int8_t)*MIN(num, cbt->liveness.num_recent_circs));

    // Adjust the index if it needs it.
    if (num < cbt->liveness.num_recent_circs) {
      cbt->liveness.after_firsthop_idx = MIN(num-1,
              cbt->liveness.after_firsthop_idx);
    }

    tor_free(cbt->liveness.timeouts_after_firsthop);
    cbt->liveness.timeouts_after_firsthop = recent_circs;
    cbt->liveness.num_recent_circs = num;
  }
}

187
188
/** Make a note that we're running unit tests (rather than running Tor
 * itself), so we avoid clobbering our state file. */
189
190
191
192
193
194
void
circuitbuild_running_unit_tests(void)
{
  unit_tests = 1;
}

195
196
197
198
199
200
201
202
203
/**
 * Return the initial default or configured timeout in milliseconds
 */
static double
circuit_build_times_get_initial_timeout(void)
{
  double timeout;
  if (!unit_tests && get_options()->CircuitBuildTimeout) {
    timeout = get_options()->CircuitBuildTimeout*1000;
Mike Perry's avatar
Mike Perry committed
204
    if (timeout < circuit_build_times_min_timeout()) {
205
      log_warn(LD_CIRC, "Config CircuitBuildTimeout too low. Setting to %ds",
Mike Perry's avatar
Mike Perry committed
206
207
               circuit_build_times_min_timeout()/1000);
      timeout = circuit_build_times_min_timeout();
208
209
    }
  } else {
Mike Perry's avatar
Mike Perry committed
210
    timeout = circuit_build_times_initial_timeout();
211
212
213
214
  }
  return timeout;
}

Mike Perry's avatar
Mike Perry committed
215
216
217
/**
 * Reset the build time state.
 *
218
 * Leave estimated parameters, timeout and network liveness intact
Mike Perry's avatar
Mike Perry committed
219
220
 * for future use.
 */
221
222
223
224
225
226
227
void
circuit_build_times_reset(circuit_build_times_t *cbt)
{
  memset(cbt->circuit_build_times, 0, sizeof(cbt->circuit_build_times));
  cbt->pre_timeouts = 0;
  cbt->total_build_times = 0;
  cbt->build_times_idx = 0;
Mike Perry's avatar
Mike Perry committed
228
  cbt->have_computed_timeout = 0;
229
230
}

Mike Perry's avatar
Mike Perry committed
231
232
233
234
235
236
/**
 * Initialize the buildtimes structure for first use.
 *
 * Sets the initial timeout value based to either the
 * config setting or BUILD_TIMEOUT_INITIAL_VALUE.
 */
237
238
239
240
void
circuit_build_times_init(circuit_build_times_t *cbt)
{
  memset(cbt, 0, sizeof(*cbt));
Mike Perry's avatar
Mike Perry committed
241
242
243
  cbt->liveness.num_recent_circs = circuit_build_times_recent_circuit_count();
  cbt->liveness.timeouts_after_firsthop = tor_malloc_zero(sizeof(int8_t)*
                                      cbt->liveness.num_recent_circs);
244
  cbt->timeout_ms = circuit_build_times_get_initial_timeout();
245
  control_event_buildtimeout_set(cbt, BUILDTIMEOUT_SET_EVENT_RESET);
246
}
247

248
/**
249
 * Rewind our timeout history by n timeout positions.
250
251
252
253
254
255
256
 */
static void
circuit_build_times_rewind_history(circuit_build_times_t *cbt, int n)
{
  int i = 0;

  if (cbt->pre_timeouts) {
257
258
    /* If we have pre-timeouts, it means we're not yet storing
     * timeouts in our normal array. Only rewind the counter. */
259
260
261
262
    if (cbt->pre_timeouts > n) {
      cbt->pre_timeouts -= n;
    } else {
      cbt->pre_timeouts = 0;
263
    }
264
265
266
267
268
269
270
271
272
    log_info(LD_CIRC,
             "Rewound history by %d places. Current index: %d. Total: %d. "
             "Pre-timeouts: %d", n, cbt->build_times_idx,
             cbt->total_build_times, cbt->pre_timeouts);

    return;
  }

  cbt->build_times_idx -= n;
Mike Perry's avatar
Mike Perry committed
273
  cbt->build_times_idx %= CBT_NCIRCUITS_TO_OBSERVE;
274
275

  for (i = 0; i < n; i++) {
Mike Perry's avatar
Mike Perry committed
276
277
    cbt->circuit_build_times[(i+cbt->build_times_idx)
                             %CBT_NCIRCUITS_TO_OBSERVE]=0;
278
279
280
281
  }

  if (cbt->total_build_times > n) {
    cbt->total_build_times -= n;
282
  } else {
283
    cbt->total_build_times = 0;
284
  }
285
286
287
288

  log_info(LD_CIRC,
          "Rewound history by %d places. Current index: %d. "
          "Total: %d", n, cbt->build_times_idx, cbt->total_build_times);
289
290
}

291
/**
292
293
 * Add a new timeout value <b>time</b> to the set of build times. Time
 * units are milliseconds.
294
 *
295
 * circuit_build_times <b>cbt</a> is a circular array, so loop around when
Mike Perry's avatar
Mike Perry committed
296
 * array is full.
297
298
 */
int
299
circuit_build_times_add_time(circuit_build_times_t *cbt, build_time_t time)
300
{
Mike Perry's avatar
Mike Perry committed
301
  tor_assert(time <= CBT_BUILD_TIME_MAX);
302
303
  if (time <= 0) {
    log_warn(LD_CIRC, "Circuit build time is %u!", time);
304
    return -1;
305
  }
306

307
308
309
  // XXX: Probably want to demote this to debug for the release.
  log_info(LD_CIRC, "Adding circuit build time %u", time);

310
  cbt->circuit_build_times[cbt->build_times_idx] = time;
Mike Perry's avatar
Mike Perry committed
311
312
  cbt->build_times_idx = (cbt->build_times_idx + 1) % CBT_NCIRCUITS_TO_OBSERVE;
  if (cbt->total_build_times < CBT_NCIRCUITS_TO_OBSERVE)
313
    cbt->total_build_times++;
314

Mike Perry's avatar
Mike Perry committed
315
  if ((cbt->total_build_times % CBT_SAVE_STATE_EVERY) == 0) {
316
    /* Save state every n circuit builds */
317
    if (!unit_tests && !get_options()->AvoidDiskWrites)
Mike Perry's avatar
Mike Perry committed
318
319
320
      or_state_mark_dirty(get_or_state(), 0);
  }

321
322
323
324
  return 0;
}

/**
Mike Perry's avatar
Mike Perry committed
325
 * Return maximum circuit build time
326
 */
327
static build_time_t
328
circuit_build_times_max(circuit_build_times_t *cbt)
329
{
330
331
  int i = 0;
  build_time_t max_build_time = 0;
Mike Perry's avatar
Mike Perry committed
332
  for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
333
334
    if (cbt->circuit_build_times[i] > max_build_time)
      max_build_time = cbt->circuit_build_times[i];
335
336
337
338
  }
  return max_build_time;
}

339
#if 0
Mike Perry's avatar
Mike Perry committed
340
/** Return minimum circuit build time */
341
build_time_t
342
circuit_build_times_min(circuit_build_times_t *cbt)
343
344
{
  int i = 0;
Mike Perry's avatar
Mike Perry committed
345
346
  build_time_t min_build_time = CBT_BUILD_TIME_MAX;
  for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
347
    if (cbt->circuit_build_times[i] && /* 0 <-> uninitialized */
348
        cbt->circuit_build_times[i] < min_build_time)
349
350
      min_build_time = cbt->circuit_build_times[i];
  }
Mike Perry's avatar
Mike Perry committed
351
352
  if (min_build_time == CBT_BUILD_TIME_MAX) {
    log_warn(LD_CIRC, "No build times less than CBT_BUILD_TIME_MAX!");
353
354
355
  }
  return min_build_time;
}
356
#endif
357

358
/**
Mike Perry's avatar
Mike Perry committed
359
360
361
 * Calculate and return a histogram for the set of build times.
 *
 * Returns an allocated array of histrogram bins representing
Mike Perry's avatar
Mike Perry committed
362
 * the frequency of index*CBT_BIN_WIDTH millisecond
Mike Perry's avatar
Mike Perry committed
363
364
365
 * build times. Also outputs the number of bins in nbins.
 *
 * The return value must be freed by the caller.
366
367
368
369
370
371
372
373
374
 */
static uint32_t *
circuit_build_times_create_histogram(circuit_build_times_t *cbt,
                                     build_time_t *nbins)
{
  uint32_t *histogram;
  build_time_t max_build_time = circuit_build_times_max(cbt);
  int i, c;

Mike Perry's avatar
Mike Perry committed
375
  *nbins = 1 + (max_build_time / CBT_BIN_WIDTH);
376
377
378
  histogram = tor_malloc_zero(*nbins * sizeof(build_time_t));

  // calculate histogram
Mike Perry's avatar
Mike Perry committed
379
  for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
380
381
    if (cbt->circuit_build_times[i] == 0) continue; /* 0 <-> uninitialized */

Mike Perry's avatar
Mike Perry committed
382
    c = (cbt->circuit_build_times[i] / CBT_BIN_WIDTH);
383
384
385
386
387
388
    histogram[c]++;
  }

  return histogram;
}

Mike Perry's avatar
Mike Perry committed
389
/**
Mike Perry's avatar
Mike Perry committed
390
 * Return the most frequent build time (rounded to CBT_BIN_WIDTH ms).
Mike Perry's avatar
Mike Perry committed
391
392
393
 *
 * Ties go in favor of the slower time.
 */
394
395
396
397
398
399
400
static build_time_t
circuit_build_times_mode(circuit_build_times_t *cbt)
{
  build_time_t i, nbins, max_bin=0;
  uint32_t *histogram = circuit_build_times_create_histogram(cbt, &nbins);

  for (i = 0; i < nbins; i++) {
401
    if (histogram[i] >= histogram[max_bin]) {
402
403
404
405
      max_bin = i;
    }
  }

Mike Perry's avatar
Mike Perry committed
406
407
  tor_free(histogram);

Mike Perry's avatar
Mike Perry committed
408
  return max_bin*CBT_BIN_WIDTH+CBT_BIN_WIDTH/2;
409
410
}

411
/**
Mike Perry's avatar
Mike Perry committed
412
413
 * Output a histogram of current circuit build times to
 * the or_state_t state structure.
414
415
 */
void
416
circuit_build_times_update_state(circuit_build_times_t *cbt,
417
                                 or_state_t *state)
418
{
419
  uint32_t *histogram;
420
  build_time_t i = 0;
421
  build_time_t nbins = 0;
422
423
  config_line_t **next, *line;

424
  histogram = circuit_build_times_create_histogram(cbt, &nbins);
425
426
427
428
429
  // write to state
  config_free_lines(state->BuildtimeHistogram);
  next = &state->BuildtimeHistogram;
  *next = NULL;

430
  state->TotalBuildTimes = cbt->total_build_times;
431

432
  for (i = 0; i < nbins; i++) {
433
434
    // compress the histogram by skipping the blanks
    if (histogram[i] == 0) continue;
435
436
    *next = line = tor_malloc_zero(sizeof(config_line_t));
    line->key = tor_strdup("CircuitBuildTimeBin");
437
    line->value = tor_malloc(25);
438
    tor_snprintf(line->value, 25, "%d %d",
Mike Perry's avatar
Mike Perry committed
439
            i*CBT_BIN_WIDTH+CBT_BIN_WIDTH/2, histogram[i]);
440
441
    next = &(line->next);
  }
442

443
  if (!unit_tests) {
444
445
446
    if (!get_options()->AvoidDiskWrites)
      or_state_mark_dirty(get_or_state(), 0);
  }
447

448
  tor_free(histogram);
449
450
}

Mike Perry's avatar
Mike Perry committed
451
452
453
454
455
/**
 * Shuffle the build times array.
 *
 * Stolen from http://en.wikipedia.org/wiki/Fisher\u2013Yates_shuffle
 */
456
static void
457
458
459
circuit_build_times_shuffle_and_store_array(circuit_build_times_t *cbt,
                                            build_time_t *raw_times,
                                            int num_times)
460
{
461
  int n = num_times;
Mike Perry's avatar
Mike Perry committed
462
  if (num_times > CBT_NCIRCUITS_TO_OBSERVE) {
463
    log_notice(LD_CIRC, "Decreasing circuit_build_times size from %d to %d",
Mike Perry's avatar
Mike Perry committed
464
               num_times, CBT_NCIRCUITS_TO_OBSERVE);
465
466
467
468
469
470
471
472
473
474
  }

  /* This code can only be run on a compact array */
  while (n-- > 1) {
    int k = crypto_rand_int(n + 1); /* 0 <= k <= n. */
    build_time_t tmp = raw_times[k];
    raw_times[k] = raw_times[n];
    raw_times[n] = tmp;
  }

Mike Perry's avatar
Mike Perry committed
475
476
477
  /* Since the times are now shuffled, take a random CBT_NCIRCUITS_TO_OBSERVE
   * subset (ie the first CBT_NCIRCUITS_TO_OBSERVE values) */
  for (n = 0; n < MIN(num_times, CBT_NCIRCUITS_TO_OBSERVE); n++) {
478
479
    circuit_build_times_add_time(cbt, raw_times[n]);
  }
480
481
}

Mike Perry's avatar
Mike Perry committed
482
483
484
485
486
487
488
/**
 * Load histogram from <b>state</b>, shuffling the resulting array
 * after we do so. Use this result to estimate parameters and
 * calculate the timeout.
 *
 * Returns -1 and sets msg on error. Msg must be freed by the caller.
 */
489
int
490
491
circuit_build_times_parse_state(circuit_build_times_t *cbt,
                                or_state_t *state, char **msg)
492
{
493
494
  int tot_values = 0;
  uint32_t loaded_cnt = 0, N = 0;
495
  config_line_t *line;
496
  int i;
497
498
  build_time_t *loaded_times = tor_malloc(sizeof(build_time_t)
                                          * state->TotalBuildTimes);
499
  circuit_build_times_init(cbt);
500
  *msg = NULL;
501

502
  for (line = state->BuildtimeHistogram; line; line = line->next) {
503
    smartlist_t *args = smartlist_create();
504
    smartlist_split_string(args, line->value, " ",
505
                           SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
506
    if (smartlist_len(args) < 2) {
507
      *msg = tor_strdup("Unable to parse circuit build times: "
508
                        "Too few arguments to CircuitBuildTime");
Mike Perry's avatar
Mike Perry committed
509
510
      SMARTLIST_FOREACH(args, char*, cp, tor_free(cp));
      smartlist_free(args);
511
512
      break;
    } else {
513
514
      const char *ms_str = smartlist_get(args,0);
      const char *count_str = smartlist_get(args,1);
515
      uint32_t count, k;
516
      build_time_t ms;
517
      int ok;
518
      ms = (build_time_t)tor_parse_ulong(ms_str, 0, 0,
Mike Perry's avatar
Mike Perry committed
519
                                         CBT_BUILD_TIME_MAX, &ok, NULL);
520
521
522
      if (!ok) {
        *msg = tor_strdup("Unable to parse circuit build times: "
                          "Unparsable bin number");
Sebastian Hahn's avatar
Sebastian Hahn committed
523
524
        SMARTLIST_FOREACH(args, char*, cp, tor_free(cp));
        smartlist_free(args);
525
526
        break;
      }
527
528
      count = (uint32_t)tor_parse_ulong(count_str, 0, 0,
                                        UINT32_MAX, &ok, NULL);
529
530
531
      if (!ok) {
        *msg = tor_strdup("Unable to parse circuit build times: "
                          "Unparsable bin count");
Sebastian Hahn's avatar
Sebastian Hahn committed
532
533
        SMARTLIST_FOREACH(args, char*, cp, tor_free(cp));
        smartlist_free(args);
534
535
        break;
      }
536

537
538
539
540
541
      if (loaded_cnt+count > state->TotalBuildTimes) {
        log_warn(LD_CIRC,
                 "Too many build times in state file. "
                 "Stopping short before %d",
                 loaded_cnt+count);
542
543
        SMARTLIST_FOREACH(args, char*, cp, tor_free(cp));
        smartlist_free(args);
544
545
546
        break;
      }

547
      for (k = 0; k < count; k++) {
548
        loaded_times[loaded_cnt++] = ms;
549
      }
550
      N++;
Mike Perry's avatar
Mike Perry committed
551
552
      SMARTLIST_FOREACH(args, char*, cp, tor_free(cp));
      smartlist_free(args);
553
    }
554
  }
Mike Perry's avatar
Mike Perry committed
555

556
557
558
559
  if (loaded_cnt != state->TotalBuildTimes) {
    log_warn(LD_CIRC,
            "Corrupt state file? Build times count mismatch. "
            "Read %d, file says %d", loaded_cnt, state->TotalBuildTimes);
560
  }
561

562
  circuit_build_times_shuffle_and_store_array(cbt, loaded_times, loaded_cnt);
563
564

  /* Verify that we didn't overwrite any indexes */
Mike Perry's avatar
Mike Perry committed
565
  for (i=0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
566
567
568
569
570
571
572
    if (!cbt->circuit_build_times[i])
      break;
    tot_values++;
  }
  log_info(LD_CIRC,
           "Loaded %d/%d values from %d lines in circuit time histogram",
           tot_values, cbt->total_build_times, N);
573
  tor_assert(cbt->total_build_times == tot_values);
Mike Perry's avatar
Mike Perry committed
574
  tor_assert(cbt->total_build_times <= CBT_NCIRCUITS_TO_OBSERVE);
575
  circuit_build_times_set_timeout(cbt);
576
  tor_free(loaded_times);
577
  return *msg ? -1 : 0;
578
579
}

Mike Perry's avatar
Mike Perry committed
580
581
582
583
584
585
586
587
588
/**
 * Estimates the Xm and Alpha parameters using
 * http://en.wikipedia.org/wiki/Pareto_distribution#Parameter_estimation
 *
 * The notable difference is that we use mode instead of min to estimate Xm.
 * This is because our distribution is frechet-like. We claim this is
 * an acceptable approximation because we are only concerned with the
 * accuracy of the CDF of the tail.
 */
589
void
590
591
circuit_build_times_update_alpha(circuit_build_times_t *cbt)
{
592
  build_time_t *x=cbt->circuit_build_times;
593
594
595
596
  double a = 0;
  int n=0,i=0;

  /* http://en.wikipedia.org/wiki/Pareto_distribution#Parameter_estimation */
597
598
599
  /* We sort of cheat here and make our samples slightly more pareto-like
   * and less frechet-like. */
  cbt->Xm = circuit_build_times_mode(cbt);
600

Mike Perry's avatar
Mike Perry committed
601
  for (i=0; i< CBT_NCIRCUITS_TO_OBSERVE; i++) {
602
603
604
    if (!x[i]) {
      continue;
    }
605

606
    if (x[i] < cbt->Xm) {
607
      a += tor_mathlog(cbt->Xm);
608
    } else {
609
      a += tor_mathlog(x[i]);
610
    }
611
612
    n++;
  }
613

614
  if (n!=cbt->total_build_times) {
615
    log_err(LD_CIRC, "Discrepancy in build times count: %d vs %d", n,
616
617
            cbt->total_build_times);
  }
618
  tor_assert(n==cbt->total_build_times);
619

620
  a -= n*tor_mathlog(cbt->Xm);
621
622
623
624
  a = n/a;

  cbt->alpha = a;
}
625

626
627
/**
 * This is the Pareto Quantile Function. It calculates the point x
628
 * in the distribution such that F(x) = quantile (ie quantile*100%
629
630
 * of the mass of the density function is below x on the curve).
 *
Mike Perry's avatar
Mike Perry committed
631
632
 * We use it to calculate the timeout and also to generate synthetic
 * values of time for circuits that timeout before completion.
633
634
635
 *
 * See http://en.wikipedia.org/wiki/Quantile_function,
 * http://en.wikipedia.org/wiki/Inverse_transform_sampling and
636
637
 * http://en.wikipedia.org/wiki/Pareto_distribution#Generating_a_
 *     random_sample_from_Pareto_distribution
638
 * That's right. I'll cite wikipedia all day long.
639
640
 *
 * Return value is in milliseconds.
641
 */
642
double
643
644
645
circuit_build_times_calculate_timeout(circuit_build_times_t *cbt,
                                      double quantile)
{
646
647
648
649
650
651
  double ret;
  tor_assert(quantile >= 0);
  tor_assert(1.0-quantile > 0);
  tor_assert(cbt->Xm > 0);

  ret = cbt->Xm/pow(1.0-quantile,1.0/cbt->alpha);
652
653
654
655
656
657
658
  if (ret > INT32_MAX) {
    ret = INT32_MAX;
  }
  tor_assert(ret > 0);
  return ret;
}

Mike Perry's avatar
Mike Perry committed
659
/** Pareto CDF */
660
double
661
circuit_build_times_cdf(circuit_build_times_t *cbt, double x)
662
{
663
664
665
  double ret;
  tor_assert(cbt->Xm > 0);
  ret = 1.0-pow(cbt->Xm/x,cbt->alpha);
666
667
668
669
  tor_assert(0 <= ret && ret <= 1.0);
  return ret;
}

Mike Perry's avatar
Mike Perry committed
670
671
672
/**
 * Generate a synthetic time using our distribution parameters.
 *
673
 * The return value will be within the [q_lo, q_hi) quantile points
Mike Perry's avatar
Mike Perry committed
674
675
 * on the CDF.
 */
676
677
678
679
build_time_t
circuit_build_times_generate_sample(circuit_build_times_t *cbt,
                                    double q_lo, double q_hi)
{
680
  uint64_t r = crypto_rand_uint64(UINT64_MAX-1);
681
  build_time_t ret;
682
683
  double u;

684
685
686
  /* Generate between [q_lo, q_hi) */
  q_hi -= 1.0/(INT32_MAX);

687
688
  tor_assert(q_lo >= 0);
  tor_assert(q_hi < 1);
689
  tor_assert(q_lo < q_hi);
690
691

  u = q_lo + ((q_hi-q_lo)*r)/(1.0*UINT64_MAX);
692
693

  tor_assert(0 <= u && u < 1.0);
694
  /* circuit_build_times_calculate_timeout returns <= INT32_MAX */
695
696
  ret = (build_time_t)
    tor_lround(circuit_build_times_calculate_timeout(cbt, u));
697
698
  tor_assert(ret > 0);
  return ret;
699
}
700

Mike Perry's avatar
Mike Perry committed
701
/** Generate points in [cutoff, 1.0) on the CDF. */
702
void
Mike Perry's avatar
Mike Perry committed
703
704
circuit_build_times_add_timeout_worker(circuit_build_times_t *cbt,
                                       double quantile_cutoff)
705
{
706
707
708
  // XXX: This may be failing when the number of samples is small?
  // Keep getting values for the largest timeout bucket over and over
  // again... Probably because alpha is very very large in that case..
709
  build_time_t gentime = circuit_build_times_generate_sample(cbt,
Mike Perry's avatar
Mike Perry committed
710
              quantile_cutoff, CBT_MAX_SYNTHETIC_QUANTILE);
711

712
  if (gentime < (build_time_t)tor_lround(cbt->timeout_ms)) {
713
    log_warn(LD_CIRC,
714
             "Generated a synthetic timeout LESS than the current timeout: "
715
716
             "%ums vs %lfms using Xm: %d a: %lf, q: %lf",
             gentime, cbt->timeout_ms, cbt->Xm, cbt->alpha, quantile_cutoff);
Mike Perry's avatar
Mike Perry committed
717
  } else if (gentime > CBT_BUILD_TIME_MAX) {
718
    log_info(LD_CIRC,
719
720
             "Generated a synthetic timeout larger than the max: %u",
             gentime);
Mike Perry's avatar
Mike Perry committed
721
    gentime = CBT_BUILD_TIME_MAX;
722
  } else {
723
724
    log_info(LD_CIRC, "Generated synthetic circuit build time %u for timeout",
            gentime);
725
726
727
728
729
  }

  circuit_build_times_add_time(cbt, gentime);
}

Mike Perry's avatar
Mike Perry committed
730
731
732
733
/**
 * Estimate an initial alpha parameter by solving the quantile
 * function with a quantile point and a specific timeout value.
 */
734
735
void
circuit_build_times_initial_alpha(circuit_build_times_t *cbt,
736
                                  double quantile, double timeout_ms)
737
738
739
740
741
742
743
{
  // Q(u) = Xm/((1-u)^(1/a))
  // Q(0.8) = Xm/((1-0.8))^(1/a)) = CircBuildTimeout
  // CircBuildTimeout = Xm/((1-0.8))^(1/a))
  // CircBuildTimeout = Xm*((1-0.8))^(-1/a))
  // ln(CircBuildTimeout) = ln(Xm)+ln(((1-0.8)))*(-1/a)
  // -ln(1-0.8)/(ln(CircBuildTimeout)-ln(Xm))=a
744
  tor_assert(quantile >= 0);
745
  tor_assert(cbt->Xm > 0);
746
747
  cbt->alpha = tor_mathlog(1.0-quantile)/
    (tor_mathlog(cbt->Xm)-tor_mathlog(timeout_ms));
748
  tor_assert(cbt->alpha > 0);
749
750
}

Mike Perry's avatar
Mike Perry committed
751
752
753
754
/**
 * Generate synthetic timeout values for the timeouts
 * that have happened before we estimated our parameters.
 */
755
756
757
static void
circuit_build_times_count_pretimeouts(circuit_build_times_t *cbt)
{
758
759
  /* Store a timeout as a random position past the current
   * cutoff on the pareto curve */
760
  if (cbt->pre_timeouts) {
Mike Perry's avatar
Mike Perry committed
761
    double timeout_quantile = 1.0-
762
763
          ((double)cbt->pre_timeouts)/
                    (cbt->pre_timeouts+cbt->total_build_times);
Mike Perry's avatar
Mike Perry committed
764
    /* Make sure it doesn't exceed the synthetic max */
Mike Perry's avatar
Mike Perry committed
765
    timeout_quantile *= CBT_MAX_SYNTHETIC_QUANTILE;
766
    cbt->Xm = circuit_build_times_mode(cbt);
767
    tor_assert(cbt->Xm > 0);
768
    /* Use current timeout to get an estimate on alpha */
Mike Perry's avatar
Mike Perry committed
769
    circuit_build_times_initial_alpha(cbt, timeout_quantile,
770
                                      cbt->timeout_ms);
771
    while (cbt->pre_timeouts-- != 0) {
Mike Perry's avatar
Mike Perry committed
772
      circuit_build_times_add_timeout_worker(cbt, timeout_quantile);
773
774
775
776
777
    }
    cbt->pre_timeouts = 0;
  }
}

778
779
780
781
782
783
784
/**
 * Returns true if we need circuits to be built
 */
int
circuit_build_times_needs_circuits(circuit_build_times_t *cbt)
{
  /* Return true if < MIN_CIRCUITS_TO_OBSERVE */
Mike Perry's avatar
Mike Perry committed
785
  if (cbt->total_build_times < circuit_build_times_min_circs_to_observe())
786
787
788
789
    return 1;
  return 0;
}

Mike Perry's avatar
Mike Perry committed
790
791
792
793
/**
 * Returns true if we should build a timeout test circuit
 * right now.
 */
794
795
796
797
int
circuit_build_times_needs_circuits_now(circuit_build_times_t *cbt)
{
  return circuit_build_times_needs_circuits(cbt) &&
Mike Perry's avatar
Mike Perry committed
798
    approx_time()-cbt->last_circ_at > circuit_build_times_test_frequency();
799
800
}

Mike Perry's avatar
Mike Perry committed
801
802
/**
 * Called to indicate that the network showed some signs of liveness.
803
804
805
 *
 * This function is called every time we receive a cell. Avoid
 * syscalls, events, and other high-intensity work.
Mike Perry's avatar
Mike Perry committed
806
 */
807
808
809
void
circuit_build_times_network_is_live(circuit_build_times_t *cbt)
{
810
811
812
813
814
815
  cbt->liveness.network_last_live = approx_time();
  cbt->liveness.nonlive_discarded = 0;
  cbt->liveness.nonlive_timeouts = 0;
}

/**
816
817
 * Called to indicate that we completed a circuit. Because this circuit
 * succeeded, it doesn't count as a timeout-after-the-first-hop.
818
819
820
821
 */
void
circuit_build_times_network_circ_success(circuit_build_times_t *cbt)
{
822
823
  cbt->liveness.timeouts_after_firsthop[cbt->liveness.after_firsthop_idx] = 0;
  cbt->liveness.after_firsthop_idx++;
Mike Perry's avatar
Mike Perry committed
824
  cbt->liveness.after_firsthop_idx %= cbt->liveness.num_recent_circs;
825
826
827
}

/**
828
829
830
831
 * A circuit just timed out. If there has been no recent network activity
 * at all, but this circuit was launched back when we thought the network
 * was live, increment the number of "nonlive" circuit timeouts.
 *
832
833
834
 * Also distinguish between whether it failed before the first hop
 * and record that in our history for later deciding if the network has
 * changed.
835
 */
836
static void
837
838
839
circuit_build_times_network_timeout(circuit_build_times_t *cbt,
                                    int did_onehop, time_t start_time)
{
840
841
842
843
844
845
846
847
848
849
  time_t now = time(NULL);
  /*
   * Check if this is a timeout that was for a circuit that spent its
   * entire existence during a time where we have had no network activity.
   *
   * Also double check that it is a valid timeout after we have possibly
   * just recently reset cbt->timeout_ms.
   */
  if (cbt->liveness.network_last_live <= start_time &&
          start_time <= (now - cbt->timeout_ms/1000.0)) {
850
    cbt->liveness.nonlive_timeouts++;
851
852
  } else if (did_onehop) {
    /* Count a one-hop timeout */
853
854
    cbt->liveness.timeouts_after_firsthop[cbt->liveness.after_firsthop_idx]=1;
    cbt->liveness.after_firsthop_idx++;
Mike Perry's avatar
Mike Perry committed
855
    cbt->liveness.after_firsthop_idx %= cbt->liveness.num_recent_circs;
856
  }
857
858
}

Mike Perry's avatar
Mike Perry committed
859
/**
860
861
862
863
864
 * Returns false if the network has not received a cell or tls handshake
 * in the past NETWORK_NOTLIVE_TIMEOUT_COUNT circuits.
 *
 * Also has the side effect of rewinding the circuit time history
 * in the case of recent liveness changes.
Mike Perry's avatar
Mike Perry committed
865
 */
866
int
867
circuit_build_times_network_check_live(circuit_build_times_t *cbt)
868
869
{
  time_t now = approx_time();
Mike Perry's avatar
Mike Perry committed
870
  if (cbt->liveness.nonlive_timeouts >= CBT_NETWORK_NONLIVE_DISCARD_COUNT) {
871
872
    if (!cbt->liveness.nonlive_discarded) {
      cbt->liveness.nonlive_discarded = 1;
873
874
875
876
      log_notice(LD_CIRC, "Network is no longer live (too many recent "
                "circuit timeouts). Dead for %ld seconds.",
                (long int)(now - cbt->liveness.network_last_live));
      /* Only discard NETWORK_NONLIVE_TIMEOUT_COUNT-1 because we stopped
877
       * counting after that */
Mike Perry's avatar
Mike Perry committed
878
879
      circuit_build_times_rewind_history(cbt,
                     CBT_NETWORK_NONLIVE_TIMEOUT_COUNT-1);
880
      control_event_buildtimeout_set(cbt, BUILDTIMEOUT_SET_EVENT_DISCARD);
881
882
    }
    return 0;
Mike Perry's avatar
Mike Perry committed
883
884
  } else if (cbt->liveness.nonlive_timeouts >=
                CBT_NETWORK_NONLIVE_TIMEOUT_COUNT) {
885
886
887
888
889
    if (cbt->timeout_ms < circuit_build_times_get_initial_timeout()) {
      log_notice(LD_CIRC,
                "Network is flaky. No activity for %ld seconds. "
                "Temporarily raising timeout to %lds.",
                (long int)(now - cbt->liveness.network_last_live),
890
                tor_lround(circuit_build_times_get_initial_timeout()/1000));
891
      cbt->timeout_ms = circuit_build_times_get_initial_timeout();
892
893
      cbt->liveness.net_suspended = 1;
      control_event_buildtimeout_set(cbt, BUILDTIMEOUT_SET_EVENT_SUSPENDED);
894
895
    }

896
    return 0;
897
898
899
900
901
902
  } else if (cbt->liveness.net_suspended) {
    log_notice(LD_CIRC,
              "Network activity has resumed. "
              "Resuming circuit timeout calculations.");
    cbt->liveness.net_suspended = 0;
    control_event_buildtimeout_set(cbt, BUILDTIMEOUT_SET_EVENT_RESUME);
Mike Perry's avatar
Mike Perry committed
903
  }
904

905
906
907
  return 1;
}

Mike Perry's avatar
Mike Perry committed
908
/**
909
 * Returns true if we have seen more than MAX_RECENT_TIMEOUT_COUNT of
910
911
 * the past RECENT_CIRCUITS time out after the first hop. Used to detect
 * if the network connection has changed significantly.
Mike Perry's avatar
Mike Perry committed
912
913
914
915
916
 *
 * Also resets the entire timeout history in this case and causes us
 * to restart the process of building test circuits and estimating a
 * new timeout.
 */
917
int
918
circuit_build_times_network_check_changed(circuit_build_times_t *cbt)
919
{
920
921
  int total_build_times = cbt->total_build_times;
  int timeout_count=0;
922
923
  int i;

924
925
  /* how many of our recent circuits made it to the first hop but then
   * timed out? */
Mike Perry's avatar
Mike Perry committed
926
  for (i = 0; i < cbt->liveness.num_recent_circs; i++) {
927
    timeout_count += cbt->liveness.timeouts_after_firsthop[i];
928
929
  }

930
  /* If 80% of our recent circuits are timing out after the first hop,
931
   * we need to re-estimate a new initial alpha and timeout. */
Mike Perry's avatar
Mike Perry committed
932
  if (timeout_count < circuit_build_times_max_timeouts()) {
933
934
935
    return 0;
  }

936
  circuit_build_times_reset(cbt);
937
  memset(cbt->liveness.timeouts_after_firsthop, 0,
Mike Perry's avatar
Mike Perry committed
938
939
          sizeof(*cbt->liveness.timeouts_after_firsthop)*
          cbt->liveness.num_recent_circs);
940
  cbt->liveness.after_firsthop_idx = 0;
941
942
943
944
945
946
947

  /* Check to see if this has happened before. If so, double the timeout
   * to give people on abysmally bad network connections a shot at access */
  if (cbt->timeout_ms >= circuit_build_times_get_initial_timeout()) {
    cbt->timeout_ms *= 2;
  } else {
    cbt->timeout_ms = circuit_build_times_get_initial_timeout();
948
949
  }

950
951
  control_event_buildtimeout_set(cbt, BUILDTIMEOUT_SET_EVENT_RESET);

952
  log_notice(LD_CIRC,
953
            "Network connection speed appears to have changed. Resetting "
954
            "timeout to %lds after %d timeouts and %d buildtimes.",
955
956
            tor_lround(cbt->timeout_ms/1000), timeout_count,
            total_build_times);
957
958
959
960

  return 1;
}

961
/**
962
963
964
965
 * Store a timeout as a synthetic value.
 *
 * Returns true if the store was successful and we should possibly
 * update our timeout estimate.
966
 */
967
968
969
970
int
circuit_build_times_add_timeout(circuit_build_times_t *cbt,
                                int did_onehop,
                                time_t start_time)
971
{
972
973
  circuit_build_times_network_timeout(cbt, did_onehop, start_time);

974
  /* Only count timeouts if network is live.. */
975
976
  if (!circuit_build_times_network_check_live(cbt)) {
    return 0;
977
978
979
980
  }

  /* If there are a ton of timeouts, we should reduce
   * the circuit build timeout */
981
982
  if (circuit_build_times_network_check_changed(cbt)) {
    return 0;
983
984
  }

Mike Perry's avatar
Mike Perry committed
985
  if (!cbt->have_computed_timeout) {
986
    /* Store a timeout before we have enough data */
987
    cbt->pre_timeouts++;
988
989
    log_info(LD_CIRC,
             "Not enough circuits yet to calculate a new build timeout."