circuitbuild.c 136 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.
Karsten Loesing's avatar
Karsten Loesing committed
4
 * Copyright (c) 2007-2009, 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

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

Mike Perry's avatar
Mike Perry committed
21
22
23
24
25
26
/*
 * This madness is needed because if we simply #undef log
 * before including or.h or log.h, we get linker collisions
 * and random segfaults due to memory corruption (and
 * not even at calls to log() either!)
 */
27
28
 /* XXX022 somebody should rename Tor's log() function, so we can
  * remove this wart. -RD */
Mike Perry's avatar
Mike Perry committed
29
30
31
#undef log

/*
32
33
 * Linux doesn't provide lround in math.h by default, but mac os does...
 * It's best just to leave math.h out of the picture entirely.
Mike Perry's avatar
Mike Perry committed
34
35
36
37
 */
//#define log math_h_log
//#include <math.h>
//#undef log
38
long int lround(double x);
39
double ln(double x);
Mike Perry's avatar
Mike Perry committed
40
41
double log(double x);
double pow(double x, double y);
42
43
44
45
46
47
48

double
ln(double x)
{
  return log(x);
}

Mike Perry's avatar
Mike Perry committed
49
#define log _log
50
51

/********* START VARIABLES **********/
52
/** Global list of circuit build times */
53
// FIXME: Add this as a member for entry_guard_t instead of global?
Mike Perry's avatar
Mike Perry committed
54
55
56
57
// 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.
58
circuit_build_times_t circ_times;
59
60
61
62

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

63
/** An entry_guard_t represents our information about a chosen long-term
64
65
66
 * 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. */
67
68
69
typedef struct {
  char nickname[MAX_NICKNAME_LEN+1];
  char identity[DIGEST_LEN];
70
71
72
73
  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. */
74
75
76
77
  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?*/
78
79
80
81
82
83
  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. */
84
85
  time_t last_attempted; /**< 0 if we can connect to this guard, or the time
                          * at which we last failed to connect to it. */
86
} entry_guard_t;
87

88
89
90
/** 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
91
 * and those changes need to be flushed to disk. */
92
static int entry_guards_dirty = 0;
93

94
/** If set, we're running the unit tests: we should avoid clobbering
95
 * our state file or accessing get_options() or get_or_state() */
96
97
static int unit_tests = 0;

98
99
/********* END VARIABLES ************/

100
static int circuit_deliver_create_cell(circuit_t *circ,
101
                                       uint8_t cell_type, const char *payload);
102
static int onion_pick_cpath_exit(origin_circuit_t *circ, extend_info_t *exit);
103
static crypt_path_t *onion_next_hop_in_cpath(crypt_path_t *cpath);
Roger Dingledine's avatar
Roger Dingledine committed
104
static int onion_extend_cpath(origin_circuit_t *circ);
105
static int count_acceptable_routers(smartlist_t *routers);
106
static int onion_append_hop(crypt_path_t **head_ptr, extend_info_t *choice);
107

108
static void entry_guards_changed(void);
109
static time_t start_of_month(time_t when);
110

111
112
/** Make a note that we're running unit tests (rather than running Tor
 * itself), so we avoid clobbering our state file. */
113
114
115
116
117
118
void
circuitbuild_running_unit_tests(void)
{
  unit_tests = 1;
}

119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
/**
 * 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;
    if (timeout < BUILD_TIMEOUT_MIN_VALUE) {
      log_warn(LD_CIRC, "Config CircuitBuildTimeout too low. Setting to %ds",
               BUILD_TIMEOUT_MIN_VALUE/1000);
      timeout = BUILD_TIMEOUT_MIN_VALUE;
    }
  } else {
    timeout = BUILD_TIMEOUT_INITIAL_VALUE;
  }
  return timeout;
}

Mike Perry's avatar
Mike Perry committed
139
140
141
/**
 * Reset the build time state.
 *
142
 * Leave estimated parameters, timeout and network liveness intact
Mike Perry's avatar
Mike Perry committed
143
144
 * for future use.
 */
145
146
147
148
149
150
151
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
152
  cbt->have_computed_timeout = 0;
153
154
}

Mike Perry's avatar
Mike Perry committed
155
156
157
158
159
160
/**
 * Initialize the buildtimes structure for first use.
 *
 * Sets the initial timeout value based to either the
 * config setting or BUILD_TIMEOUT_INITIAL_VALUE.
 */
161
162
163
164
void
circuit_build_times_init(circuit_build_times_t *cbt)
{
  memset(cbt, 0, sizeof(*cbt));
165
166
  cbt->timeout_ms = circuit_build_times_get_initial_timeout();
}
167

168
/**
169
 * Rewind our timeout history by n timeout positions.
170
171
172
173
174
175
176
 */
static void
circuit_build_times_rewind_history(circuit_build_times_t *cbt, int n)
{
  int i = 0;

  if (cbt->pre_timeouts) {
177
178
    /* If we have pre-timeouts, it means we're not yet storing
     * timeouts in our normal array. Only rewind the counter. */
179
180
181
182
    if (cbt->pre_timeouts > n) {
      cbt->pre_timeouts -= n;
    } else {
      cbt->pre_timeouts = 0;
183
    }
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
    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;
  cbt->build_times_idx %= NCIRCUITS_TO_OBSERVE;

  for (i = 0; i < n; i++) {
    cbt->circuit_build_times[(i+cbt->build_times_idx)%NCIRCUITS_TO_OBSERVE]=0;
  }

  if (cbt->total_build_times > n) {
    cbt->total_build_times -= n;
201
  } else {
202
    cbt->total_build_times = 0;
203
  }
204
205
206
207

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

210
/**
211
212
 * Add a new timeout value <b>time</b> to the set of build times. Time
 * units are milliseconds.
213
 *
214
 * circuit_build_times <b>cbt</a> is a circular array, so loop around when
Mike Perry's avatar
Mike Perry committed
215
 * array is full.
216
217
 */
int
218
circuit_build_times_add_time(circuit_build_times_t *cbt, build_time_t time)
219
{
220
221
222
  tor_assert(time <= BUILD_TIME_MAX);
  if (time <= 0) {
    log_warn(LD_CIRC, "Circuit build time is %u!", time);
223
    return -1;
224
  }
225

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

229
230
  cbt->circuit_build_times[cbt->build_times_idx] = time;
  cbt->build_times_idx = (cbt->build_times_idx + 1) % NCIRCUITS_TO_OBSERVE;
231
  if (cbt->total_build_times < NCIRCUITS_TO_OBSERVE)
232
    cbt->total_build_times++;
233

Mike Perry's avatar
Mike Perry committed
234
  if ((cbt->total_build_times % BUILD_TIMES_SAVE_STATE_EVERY) == 0) {
235
    /* Save state every n circuit builds */
236
    if (!unit_tests && !get_options()->AvoidDiskWrites)
Mike Perry's avatar
Mike Perry committed
237
238
239
      or_state_mark_dirty(get_or_state(), 0);
  }

240
241
242
243
  return 0;
}

/**
Mike Perry's avatar
Mike Perry committed
244
 * Return maximum circuit build time
245
 */
246
static build_time_t
247
circuit_build_times_max(circuit_build_times_t *cbt)
248
{
249
250
  int i = 0;
  build_time_t max_build_time = 0;
251
252
253
  for (i = 0; i < NCIRCUITS_TO_OBSERVE; i++) {
    if (cbt->circuit_build_times[i] > max_build_time)
      max_build_time = cbt->circuit_build_times[i];
254
255
256
257
  }
  return max_build_time;
}

258
#if 0
Mike Perry's avatar
Mike Perry committed
259
/** Return minimum circuit build time */
260
build_time_t
261
circuit_build_times_min(circuit_build_times_t *cbt)
262
263
{
  int i = 0;
264
  build_time_t min_build_time = BUILD_TIME_MAX;
265
266
  for (i = 0; i < NCIRCUITS_TO_OBSERVE; i++) {
    if (cbt->circuit_build_times[i] && /* 0 <-> uninitialized */
267
        cbt->circuit_build_times[i] < min_build_time)
268
269
      min_build_time = cbt->circuit_build_times[i];
  }
270
271
  if (min_build_time == BUILD_TIME_MAX) {
    log_warn(LD_CIRC, "No build times less than BUILD_TIME_MAX!");
272
273
274
  }
  return min_build_time;
}
275
#endif
276

277
/**
Mike Perry's avatar
Mike Perry committed
278
279
280
281
282
283
284
 * Calculate and return a histogram for the set of build times.
 *
 * Returns an allocated array of histrogram bins representing
 * the frequency of index*BUILDTIME_BIN_WIDTH millisecond
 * build times. Also outputs the number of bins in nbins.
 *
 * The return value must be freed by the caller.
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
 */
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;

  *nbins = 1 + (max_build_time / BUILDTIME_BIN_WIDTH);
  histogram = tor_malloc_zero(*nbins * sizeof(build_time_t));

  // calculate histogram
  for (i = 0; i < NCIRCUITS_TO_OBSERVE; i++) {
    if (cbt->circuit_build_times[i] == 0) continue; /* 0 <-> uninitialized */

    c = (cbt->circuit_build_times[i] / BUILDTIME_BIN_WIDTH);
    histogram[c]++;
  }

  return histogram;
}

Mike Perry's avatar
Mike Perry committed
308
309
310
311
312
/**
 * Return the most frequent build time (rounded to BUILDTIME_BIN_WIDTH ms).
 *
 * Ties go in favor of the slower time.
 */
313
314
315
316
317
318
319
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++) {
320
    if (histogram[i] >= histogram[max_bin]) {
321
322
323
324
      max_bin = i;
    }
  }

Mike Perry's avatar
Mike Perry committed
325
326
  tor_free(histogram);

327
  return max_bin*BUILDTIME_BIN_WIDTH+BUILDTIME_BIN_WIDTH/2;
328
329
}

330
/**
Mike Perry's avatar
Mike Perry committed
331
332
 * Output a histogram of current circuit build times to
 * the or_state_t state structure.
333
334
 */
void
335
circuit_build_times_update_state(circuit_build_times_t *cbt,
336
                                 or_state_t *state)
337
{
338
  uint32_t *histogram;
339
  build_time_t i = 0;
340
  build_time_t nbins = 0;
341
342
  config_line_t **next, *line;

343
  histogram = circuit_build_times_create_histogram(cbt, &nbins);
344
345
346
347
348
  // write to state
  config_free_lines(state->BuildtimeHistogram);
  next = &state->BuildtimeHistogram;
  *next = NULL;

349
  state->TotalBuildTimes = cbt->total_build_times;
350

351
  for (i = 0; i < nbins; i++) {
352
353
    // compress the histogram by skipping the blanks
    if (histogram[i] == 0) continue;
354
355
    *next = line = tor_malloc_zero(sizeof(config_line_t));
    line->key = tor_strdup("CircuitBuildTimeBin");
356
    line->value = tor_malloc(25);
357
358
    tor_snprintf(line->value, 25, "%d %d",
            i*BUILDTIME_BIN_WIDTH+BUILDTIME_BIN_WIDTH/2, histogram[i]);
359
360
    next = &(line->next);
  }
361

362
  if (!unit_tests) {
363
364
365
    if (!get_options()->AvoidDiskWrites)
      or_state_mark_dirty(get_or_state(), 0);
  }
366

367
  if (histogram) tor_free(histogram);
368
369
}

Mike Perry's avatar
Mike Perry committed
370
371
372
373
374
/**
 * Shuffle the build times array.
 *
 * Stolen from http://en.wikipedia.org/wiki/Fisher\u2013Yates_shuffle
 */
375
static void
376
377
378
circuit_build_times_shuffle_and_store_array(circuit_build_times_t *cbt,
                                            build_time_t *raw_times,
                                            int num_times)
379
{
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
  int n = num_times;
  if (num_times > NCIRCUITS_TO_OBSERVE) {
    log_notice(LD_CIRC, "Decreasing circuit_build_times size from %d to %d",
               num_times, NCIRCUITS_TO_OBSERVE);
  }

  /* 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;
  }

  /* Since the times are now shuffled, take a random NCIRCUITS_TO_OBSERVE
   * subset (ie the first NCIRCUITS_TO_OBSERVE values) */
  for (n = 0; n < MIN(num_times, NCIRCUITS_TO_OBSERVE); n++) {
    circuit_build_times_add_time(cbt, raw_times[n]);
  }
399
400
}

Mike Perry's avatar
Mike Perry committed
401
402
403
404
405
406
407
/**
 * 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.
 */
408
int
409
410
circuit_build_times_parse_state(circuit_build_times_t *cbt,
                                or_state_t *state, char **msg)
411
{
412
413
  int tot_values = 0;
  uint32_t loaded_cnt = 0, N = 0;
414
  config_line_t *line;
415
  int i;
416
417
  build_time_t *loaded_times = tor_malloc(sizeof(build_time_t)
                                          * state->TotalBuildTimes);
418
  circuit_build_times_init(cbt);
419
  *msg = NULL;
420

421
  for (line = state->BuildtimeHistogram; line; line = line->next) {
422
    smartlist_t *args = smartlist_create();
423
    smartlist_split_string(args, line->value, " ",
424
                           SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
425
    if (smartlist_len(args) < 2) {
426
      *msg = tor_strdup("Unable to parse circuit build times: "
427
                        "Too few arguments to CircuitBuildTime");
Mike Perry's avatar
Mike Perry committed
428
429
      SMARTLIST_FOREACH(args, char*, cp, tor_free(cp));
      smartlist_free(args);
430
431
      break;
    } else {
432
433
      const char *ms_str = smartlist_get(args,0);
      const char *count_str = smartlist_get(args,1);
434
      uint32_t count, k;
435
      build_time_t ms;
436
      int ok;
437
438
      ms = (build_time_t)tor_parse_ulong(ms_str, 0, 0,
                                         BUILD_TIME_MAX, &ok, NULL);
439
440
441
      if (!ok) {
        *msg = tor_strdup("Unable to parse circuit build times: "
                          "Unparsable bin number");
Sebastian Hahn's avatar
Sebastian Hahn committed
442
443
        SMARTLIST_FOREACH(args, char*, cp, tor_free(cp));
        smartlist_free(args);
444
445
        break;
      }
446
447
      count = (uint32_t)tor_parse_ulong(count_str, 0, 0,
                                        UINT32_MAX, &ok, NULL);
448
449
450
      if (!ok) {
        *msg = tor_strdup("Unable to parse circuit build times: "
                          "Unparsable bin count");
Sebastian Hahn's avatar
Sebastian Hahn committed
451
452
        SMARTLIST_FOREACH(args, char*, cp, tor_free(cp));
        smartlist_free(args);
453
454
        break;
      }
455

456
457
458
459
460
      if (loaded_cnt+count > state->TotalBuildTimes) {
        log_warn(LD_CIRC,
                 "Too many build times in state file. "
                 "Stopping short before %d",
                 loaded_cnt+count);
461
462
        SMARTLIST_FOREACH(args, char*, cp, tor_free(cp));
        smartlist_free(args);
463
464
465
        break;
      }

466
      for (k = 0; k < count; k++) {
467
        loaded_times[loaded_cnt++] = ms;
468
      }
469
      N++;
Mike Perry's avatar
Mike Perry committed
470
471
      SMARTLIST_FOREACH(args, char*, cp, tor_free(cp));
      smartlist_free(args);
472
    }
473
  }
Mike Perry's avatar
Mike Perry committed
474

475
476
477
478
  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);
479
  }
480

481
  circuit_build_times_shuffle_and_store_array(cbt, loaded_times, loaded_cnt);
482
483
484
485
486
487
488
489
490
491

  /* Verify that we didn't overwrite any indexes */
  for (i=0; i < NCIRCUITS_TO_OBSERVE; i++) {
    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);
492
493
  tor_assert(cbt->total_build_times == tot_values);
  tor_assert(cbt->total_build_times <= NCIRCUITS_TO_OBSERVE);
494
  circuit_build_times_set_timeout(cbt);
495
  tor_free(loaded_times);
496
  return *msg ? -1 : 0;
497
498
}

Mike Perry's avatar
Mike Perry committed
499
500
501
502
503
504
505
506
507
/**
 * 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.
 */
508
void
509
510
circuit_build_times_update_alpha(circuit_build_times_t *cbt)
{
511
  build_time_t *x=cbt->circuit_build_times;
512
513
514
515
  double a = 0;
  int n=0,i=0;

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

  for (i=0; i< NCIRCUITS_TO_OBSERVE; i++) {
521
522
523
    if (!x[i]) {
      continue;
    }
524

525
526
527
528
529
    if (x[i] < cbt->Xm) {
      a += ln(cbt->Xm);
    } else {
      a += ln(x[i]);
    }
530
531
    n++;
  }
532

533
  if (n!=cbt->total_build_times) {
534
    log_err(LD_CIRC, "Discrepancy in build times count: %d vs %d", n,
535
536
            cbt->total_build_times);
  }
537
  tor_assert(n==cbt->total_build_times);
538

539
540
541
542
543
  a -= n*ln(cbt->Xm);
  a = n/a;

  cbt->alpha = a;
}
544

545
546
/**
 * This is the Pareto Quantile Function. It calculates the point x
547
 * in the distribution such that F(x) = quantile (ie quantile*100%
548
549
 * of the mass of the density function is below x on the curve).
 *
Mike Perry's avatar
Mike Perry committed
550
551
 * We use it to calculate the timeout and also to generate synthetic
 * values of time for circuits that timeout before completion.
552
553
554
 *
 * See http://en.wikipedia.org/wiki/Quantile_function,
 * http://en.wikipedia.org/wiki/Inverse_transform_sampling and
555
556
 * http://en.wikipedia.org/wiki/Pareto_distribution#Generating_a_
 *     random_sample_from_Pareto_distribution
557
 * That's right. I'll cite wikipedia all day long.
558
559
 *
 * Return value is in milliseconds.
560
 */
561
double
562
563
564
circuit_build_times_calculate_timeout(circuit_build_times_t *cbt,
                                      double quantile)
{
565
566
567
568
569
570
  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);
571
572
573
574
575
576
577
  if (ret > INT32_MAX) {
    ret = INT32_MAX;
  }
  tor_assert(ret > 0);
  return ret;
}

Mike Perry's avatar
Mike Perry committed
578
/** Pareto CDF */
579
double
580
circuit_build_times_cdf(circuit_build_times_t *cbt, double x)
581
{
582
583
584
  double ret;
  tor_assert(cbt->Xm > 0);
  ret = 1.0-pow(cbt->Xm/x,cbt->alpha);
585
586
587
588
  tor_assert(0 <= ret && ret <= 1.0);
  return ret;
}

Mike Perry's avatar
Mike Perry committed
589
590
591
/**
 * Generate a synthetic time using our distribution parameters.
 *
592
 * The return value will be within the [q_lo, q_hi) quantile points
Mike Perry's avatar
Mike Perry committed
593
594
 * on the CDF.
 */
595
596
597
598
build_time_t
circuit_build_times_generate_sample(circuit_build_times_t *cbt,
                                    double q_lo, double q_hi)
{
599
  uint64_t r = crypto_rand_uint64(UINT64_MAX-1);
600
  build_time_t ret;
601
602
  double u;

603
604
605
  /* Generate between [q_lo, q_hi) */
  q_hi -= 1.0/(INT32_MAX);

606
607
  tor_assert(q_lo >= 0);
  tor_assert(q_hi < 1);
608
  tor_assert(q_lo < q_hi);
609
610

  u = q_lo + ((q_hi-q_lo)*r)/(1.0*UINT64_MAX);
611
612

  tor_assert(0 <= u && u < 1.0);
613
  /* circuit_build_times_calculate_timeout returns <= INT32_MAX */
614
  ret = (build_time_t)lround(circuit_build_times_calculate_timeout(cbt, u));
615
616
  tor_assert(ret > 0);
  return ret;
617
}
618

Mike Perry's avatar
Mike Perry committed
619
/** Generate points in [cutoff, 1.0) on the CDF. */
620
void
Mike Perry's avatar
Mike Perry committed
621
622
circuit_build_times_add_timeout_worker(circuit_build_times_t *cbt,
                                       double quantile_cutoff)
623
{
624
  build_time_t gentime = circuit_build_times_generate_sample(cbt,
625
              quantile_cutoff, MAX_SYNTHETIC_QUANTILE);
626

627
  if (gentime < (build_time_t)lround(cbt->timeout_ms)) {
628
    log_warn(LD_CIRC,
629
             "Generated a synthetic timeout LESS than the current timeout: "
630
631
             "%ums vs %lfms using Xm: %d a: %lf, q: %lf",
             gentime, cbt->timeout_ms, cbt->Xm, cbt->alpha, quantile_cutoff);
632
  } else if (gentime > BUILD_TIME_MAX) {
633
    log_info(LD_CIRC,
634
635
             "Generated a synthetic timeout larger than the max: %u",
             gentime);
636
    gentime = BUILD_TIME_MAX;
637
  } else {
638
639
    log_info(LD_CIRC, "Generated synthetic circuit build time %u for timeout",
            gentime);
640
641
642
643
644
  }

  circuit_build_times_add_time(cbt, gentime);
}

Mike Perry's avatar
Mike Perry committed
645
646
647
648
/**
 * Estimate an initial alpha parameter by solving the quantile
 * function with a quantile point and a specific timeout value.
 */
649
650
void
circuit_build_times_initial_alpha(circuit_build_times_t *cbt,
651
                                  double quantile, double timeout_ms)
652
653
654
655
656
657
658
{
  // 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
659
  tor_assert(quantile >= 0);
660
  tor_assert(cbt->Xm > 0);
661
  cbt->alpha = ln(1.0-quantile)/(ln(cbt->Xm)-ln(timeout_ms));
662
  tor_assert(cbt->alpha > 0);
663
664
}

Mike Perry's avatar
Mike Perry committed
665
666
667
668
/**
 * Generate synthetic timeout values for the timeouts
 * that have happened before we estimated our parameters.
 */
669
670
671
static void
circuit_build_times_count_pretimeouts(circuit_build_times_t *cbt)
{
672
673
  /* Store a timeout as a random position past the current
   * cutoff on the pareto curve */
674
  if (cbt->pre_timeouts) {
Mike Perry's avatar
Mike Perry committed
675
    double timeout_quantile = 1.0-
676
677
          ((double)cbt->pre_timeouts)/
                    (cbt->pre_timeouts+cbt->total_build_times);
Mike Perry's avatar
Mike Perry committed
678
679
    /* Make sure it doesn't exceed the synthetic max */
    timeout_quantile *= MAX_SYNTHETIC_QUANTILE;
680
    cbt->Xm = circuit_build_times_mode(cbt);
681
    tor_assert(cbt->Xm > 0);
682
    /* Use current timeout to get an estimate on alpha */
Mike Perry's avatar
Mike Perry committed
683
    circuit_build_times_initial_alpha(cbt, timeout_quantile,
684
                                      cbt->timeout_ms);
685
    while (cbt->pre_timeouts-- != 0) {
Mike Perry's avatar
Mike Perry committed
686
      circuit_build_times_add_timeout_worker(cbt, timeout_quantile);
687
688
689
690
691
    }
    cbt->pre_timeouts = 0;
  }
}

692
693
694
695
696
697
698
699
700
701
702
703
/**
 * 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 */
  if (cbt->total_build_times < MIN_CIRCUITS_TO_OBSERVE)
    return 1;
  return 0;
}

Mike Perry's avatar
Mike Perry committed
704
705
706
707
/**
 * Returns true if we should build a timeout test circuit
 * right now.
 */
708
709
710
711
int
circuit_build_times_needs_circuits_now(circuit_build_times_t *cbt)
{
  return circuit_build_times_needs_circuits(cbt) &&
712
    approx_time()-cbt->last_circ_at > BUILD_TIMES_TEST_FREQUENCY;
713
714
}

Mike Perry's avatar
Mike Perry committed
715
716
717
/**
 * Called to indicate that the network showed some signs of liveness.
 */
718
719
720
void
circuit_build_times_network_is_live(circuit_build_times_t *cbt)
{
721
722
723
724
725
726
  cbt->liveness.network_last_live = approx_time();
  cbt->liveness.nonlive_discarded = 0;
  cbt->liveness.nonlive_timeouts = 0;
}

/**
727
728
 * Called to indicate that we completed a circuit. Because this circuit
 * succeeded, it doesn't count as a timeout-after-the-first-hop.
729
730
731
732
 */
void
circuit_build_times_network_circ_success(circuit_build_times_t *cbt)
{
733
734
735
  cbt->liveness.timeouts_after_firsthop[cbt->liveness.after_firsthop_idx] = 0;
  cbt->liveness.after_firsthop_idx++;
  cbt->liveness.after_firsthop_idx %= RECENT_CIRCUITS;
736
737
738
}

/**
739
740
741
742
 * 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.
 *
743
744
745
 * Also distinguish between whether it failed before the first hop
 * and record that in our history for later deciding if the network has
 * changed.
746
 */
747
static void
748
749
750
circuit_build_times_network_timeout(circuit_build_times_t *cbt,
                                    int did_onehop, time_t start_time)
{
751
752
753
754
755
756
757
758
759
760
  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)) {
761
    cbt->liveness.nonlive_timeouts++;
762
763
  } else if (did_onehop) {
    /* Count a one-hop timeout */
764
765
766
    cbt->liveness.timeouts_after_firsthop[cbt->liveness.after_firsthop_idx]=1;
    cbt->liveness.after_firsthop_idx++;
    cbt->liveness.after_firsthop_idx %= RECENT_CIRCUITS;
767
  }
768
769
}

Mike Perry's avatar
Mike Perry committed
770
/**
771
772
773
774
775
 * 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
776
 */
777
int
778
circuit_build_times_network_check_live(circuit_build_times_t *cbt)
779
780
{
  time_t now = approx_time();
781
782
783
  if (cbt->liveness.nonlive_timeouts >= NETWORK_NONLIVE_DISCARD_COUNT) {
    if (!cbt->liveness.nonlive_discarded) {
      cbt->liveness.nonlive_discarded = 1;
784
785
786
787
      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
788
789
790
791
792
793
794
795
796
797
798
799
800
801
       * counting after that */
      circuit_build_times_rewind_history(cbt, NETWORK_NONLIVE_TIMEOUT_COUNT-1);
    }
    return 0;
  } else if (cbt->liveness.nonlive_timeouts >= NETWORK_NONLIVE_TIMEOUT_COUNT) {
    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),
                lround(circuit_build_times_get_initial_timeout()/1000));
      cbt->timeout_ms = circuit_build_times_get_initial_timeout();
    }

802
    return 0;
Mike Perry's avatar
Mike Perry committed
803
  }
804

805
806
807
  return 1;
}

Mike Perry's avatar
Mike Perry committed
808
/**
809
 * Returns true if we have seen more than MAX_RECENT_TIMEOUT_COUNT of
810
811
 * 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
812
813
814
815
816
 *
 * 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.
 */
817
int
818
circuit_build_times_network_check_changed(circuit_build_times_t *cbt)
819
{
820
821
  int total_build_times = cbt->total_build_times;
  int timeout_count=0;
822
823
  int i;

824
825
  /* how many of our recent circuits made it to the first hop but then
   * timed out? */
826
  for (i = 0; i < RECENT_CIRCUITS; i++) {
827
    timeout_count += cbt->liveness.timeouts_after_firsthop[i];
828
829
  }

830
  /* If 80% of our recent circuits are timing out after the first hop,
831
   * we need to re-estimate a new initial alpha and timeout. */
832
  if (timeout_count < MAX_RECENT_TIMEOUT_COUNT) {
833
834
835
    return 0;
  }

836
  circuit_build_times_reset(cbt);
837
838
839
  memset(cbt->liveness.timeouts_after_firsthop, 0,
          sizeof(cbt->liveness.timeouts_after_firsthop));
  cbt->liveness.after_firsthop_idx = 0;
840
841
842
843
844
845
846

  /* 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();
847
848
  }

849
  log_notice(LD_CIRC,
850
            "Network connection speed appears to have changed. Resetting "
851
            "timeout to %lds after %d timeouts and %d buildtimes.",
852
            lround(cbt->timeout_ms/1000), timeout_count, total_build_times);
853
854
855
856

  return 1;
}

857
/**
858
859
860
861
 * Store a timeout as a synthetic value.
 *
 * Returns true if the store was successful and we should possibly
 * update our timeout estimate.
862
 */
863
864
865
866
int
circuit_build_times_add_timeout(circuit_build_times_t *cbt,
                                int did_onehop,
                                time_t start_time)
867
{
868
869
  circuit_build_times_network_timeout(cbt, did_onehop, start_time);

870
  /* Only count timeouts if network is live.. */
871
872
  if (!circuit_build_times_network_check_live(cbt)) {
    return 0;
873
874
875
876
  }

  /* If there are a ton of timeouts, we should reduce
   * the circuit build timeout */
877
878
  if (circuit_build_times_network_check_changed(cbt)) {
    return 0;
879
880
  }

Mike Perry's avatar
Mike Perry committed
881
  if (!cbt->have_computed_timeout) {
882
    /* Store a timeout before we have enough data */
883
    cbt->pre_timeouts++;
884
885
886
887
888
    log_info(LD_CIRC,
             "Not enough circuits yet to calculate a new build timeout."
             " Need %d more.",
             MIN_CIRCUITS_TO_OBSERVE-cbt->total_build_times);
    return 0;
889
890
  }

891
  circuit_build_times_count_pretimeouts(cbt);
Mike Perry's avatar
Mike Perry committed
892
  circuit_build_times_add_timeout_worker(cbt, BUILDTIMEOUT_QUANTILE_CUTOFF);
893
894

  return 1;
895
896
}

Mike Perry's avatar
Mike Perry committed
897
898
899
900
/**
 * Estimate a new timeout based on history and set our timeout
 * variable accordingly.
 */
901
902
903
904
905
906
907
void
circuit_build_times_set_timeout(circuit_build_times_t *cbt)
{
  if (cbt->total_build_times < MIN_CIRCUITS_TO_OBSERVE) {
    return;
  }

908
  circuit_build_times_count_pretimeouts(cbt);
909
  circuit_build_times_update_alpha(cbt);
910

911
  cbt->timeout_ms = circuit_build_times_calculate_timeout(cbt,
912
913
                                BUILDTIMEOUT_QUANTILE_CUTOFF);

Mike Perry's avatar
Mike Perry committed
914
  cbt->have_computed_timeout = 1;
915

916
917
918
919
  if (cbt->timeout_ms < BUILD_TIMEOUT_MIN_VALUE) {
    log_warn(LD_CIRC, "Set buildtimeout to low value %lfms. Setting to %dms",
             cbt->timeout_ms, BUILD_TIMEOUT_MIN_VALUE);
    cbt->timeout_ms = BUILD_TIMEOUT_MIN_VALUE;
920
921
  }

922
  log_info(LD_CIRC,
923
924
925
           "Set circuit build timeout to %lds (%lfms, Xm: %d, a: %lf) "
           "based on %d circuit times", lround(cbt->timeout_ms/1000),
           cbt->timeout_ms, cbt->Xm, cbt->alpha, cbt->total_build_times);
Mike Perry's avatar
Mike Perry committed
926

927
}
928

929
/** Iterate over values of circ_id, starting from conn-\>next_circ_id,
Roger Dingledine's avatar
Roger Dingledine committed
930
931
 * and with the high bit specified by conn-\>circ_id_type, until we get
 * a circ_id that is not in use by any other circuit on that conn.
932
933
934
 *
 * Return it, or 0 if can't get a unique circ_id.
 */
935
static circid_t
936
get_unique_circ_id_by_conn(or_connection_t *conn)
937
{
938
939
940
  circid_t test_circ_id;
  circid_t attempts=0;
  circid_t high_bit;
941

942
  tor_assert(conn);
943
  if (conn->circ_id_type == CIRC_ID_TYPE_NEITHER) {
944
    log_warn(LD_BUG, "Trying to pick a circuit ID for a connection from "
945
946
947
             "a client with no identity.");
    return 0;
  }
948
  high_bit = (conn->circ_id_type == CIRC_ID_TYPE_HIGHER) ? 1<<15 : 0;
949
950
951
952
953
954
955
956
  do {
    /* Sequentially iterate over test_circ_id=1...1<<15-1 until we find a
     * circID such that (high_bit|test_circ_id) is not already used. */
    test_circ_id = conn->next_circ_id++;
    if (test_circ_id == 0 || test_circ_id >= 1<<15) {
      test_circ_id = 1;
      conn->next_circ_id = 2;
    }
957
    if (++attempts > 1<<15) {
958
      /* Make sure we don't loop forever if all circ_id's are used. This
Roger Dingledine's avatar
Roger Dingledine committed
959
       * matters because it's an external DoS opportunity.
960
       */
961
      log_warn(LD_CIRC,"No unused circ IDs. Failing.");
962
963
964
      return 0;
    }
    test_circ_id |= high_bit;
965
  } while (circuit_id_in_use_on_orconn(test_circ_id, conn));
966
967
968
  return test_circ_id;
}

969
970
971
972
/** If <b>verbose</b> is false, allocate and return a comma-separated list of
 * the currently built elements of circuit_t.  If <b>verbose</b> is true, also
 * list information about link status in a more verbose format using spaces.
 * If <b>verbose_names</b> is false, give nicknames for Named routers and hex
973
974
 * digests for others; if <b>verbose_names</b> is true, use $DIGEST=Name style
 * names.
975
 */
976
977
static char *
circuit_list_path_impl(origin_circuit_t *circ, int verbose, int verbose_names)
978
{
979
  crypt_path_t *hop;
980
  smartlist_t *elements;
981
982
  const char *states[] = {"closed", "waiting for keys", "open"};
  char buf[128];
983
984
985
986
  char *s;

  elements = smartlist_create();

987
  if (verbose) {
988
    const char *nickname = build_state_get_exit_nickname(circ->build_state);
989
    tor_snprintf(buf, sizeof(buf), "%s%s circ (length %d%s%s):",
990
991
                 circ->build_state->is_internal ? "internal" : "exit",
                 circ->build_state->need_uptime ? " (high-uptime)" : "",
992
                 circ->build_state->desired_path_len,
993
994
                 circ->_base.state == CIRCUIT_STATE_OPEN ? "" : ", exit ",
                 circ->_base.state == CIRCUIT_STATE_OPEN ? "" :
995
                 (nickname?nickname:"*unnamed*"));