circuitbuild.c 196 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-2012, 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
#include "or.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
15
#include "circuitbuild.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
16
#include "circuitlist.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
17
#include "circuituse.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
18
#include "config.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
19
#include "connection.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
20
#include "connection_edge.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
21
#include "connection_or.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
22
#include "control.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
23
#include "directory.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
24
#include "main.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
25
#include "networkstatus.h"
26
#include "nodelist.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
27
#include "onion.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
28
#include "policies.h"
29
#include "transports.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
30
#include "relay.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
31
#include "rephist.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
32
#include "router.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
33
#include "routerlist.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
34
#include "routerparse.h"
Mike Perry's avatar
Mike Perry committed
35
#include "crypto.h"
36
37
#undef log
#include <math.h>
38

Roger Dingledine's avatar
Roger Dingledine committed
39
40
41
42
#ifndef MIN
#define MIN(a,b) ((a)<(b)?(a):(b))
#endif

43
44
#define CBT_BIN_TO_MS(bin) ((bin)*CBT_BIN_WIDTH + (CBT_BIN_WIDTH/2))

45
/********* START VARIABLES **********/
46
/** Global list of circuit build times */
47
// XXXX: Add this as a member for entry_guard_t instead of global?
Mike Perry's avatar
Mike Perry committed
48
49
50
51
// 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.
52
/* XXXX024 Make this static; add accessor functions. */
53
circuit_build_times_t circ_times;
54
55
56
57

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

58
/** An entry_guard_t represents our information about a chosen long-term
59
 * first hop, known as a "helper" node in the literature. We can't just
60
61
 * use a node_t, since we want to remember these even when we
 * don't have any directory info. */
62
63
64
typedef struct {
  char nickname[MAX_NICKNAME_LEN+1];
  char identity[DIGEST_LEN];
65
66
67
68
  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. */
69
70
71
72
  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?*/
73
74
75
76
  unsigned int path_bias_notice : 1; /**< Did we alert the user about path bias
                                      * for this node already? */
  unsigned int path_bias_disabled : 1; /**< Have we disabled this node because
                                        * of path bias issues? */
77
78
79
80
81
82
  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. */
83
84
  time_t last_attempted; /**< 0 if we can connect to this guard, or the time
                          * at which we last failed to connect to it. */
85
86
87
88

  unsigned first_hops; /**< Number of first hops this guard has completed */
  unsigned circuit_successes; /**< Number of successfully built circuits using
                               * this guard as first hop. */
89
} entry_guard_t;
90

91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
/** Information about a configured bridge. Currently this just matches the
 * ones in the torrc file, but one day we may be able to learn about new
 * bridges on our own, and remember them in the state file. */
typedef struct {
  /** Address of the bridge. */
  tor_addr_t addr;
  /** TLS port for the bridge. */
  uint16_t port;
  /** Boolean: We are re-parsing our bridge list, and we are going to remove
   * this one if we don't find it in the list of configured bridges. */
  unsigned marked_for_removal : 1;
  /** Expected identity digest, or all zero bytes if we don't know what the
   * digest should be. */
  char identity[DIGEST_LEN];

  /** Name of pluggable transport protocol taken from its config line. */
  char *transport_name;

  /** When should we next try to fetch a descriptor for this bridge? */
  download_status_t fetch_status;
} bridge_info_t;

113
114
115
/** 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
116
 * and those changes need to be flushed to disk. */
117
static int entry_guards_dirty = 0;
118

119
/** If set, we're running the unit tests: we should avoid clobbering
120
 * our state file or accessing get_options() or get_or_state() */
121
122
static int unit_tests = 0;

123
124
/********* END VARIABLES ************/

125
static int circuit_deliver_create_cell(circuit_t *circ,
126
                                       uint8_t cell_type, const char *payload);
127
static int onion_pick_cpath_exit(origin_circuit_t *circ, extend_info_t *exit);
128
static crypt_path_t *onion_next_hop_in_cpath(crypt_path_t *cpath);
Roger Dingledine's avatar
Roger Dingledine committed
129
static int onion_extend_cpath(origin_circuit_t *circ);
130
static int count_acceptable_nodes(smartlist_t *routers);
131
static int onion_append_hop(crypt_path_t **head_ptr, extend_info_t *choice);
132

133
static void entry_guards_changed(void);
134
static entry_guard_t *entry_guard_get_by_id_digest(const char *digest);
135

136
static void bridge_free(bridge_info_t *bridge);
137

138
139
140
static int entry_guard_inc_first_hop_count(entry_guard_t *guard);
static void pathbias_count_success(origin_circuit_t *circ);

Mike Perry's avatar
Mike Perry committed
141
142
143
144
145
146
147
148
149
/**
 * This function decides if CBT learning should be disabled. It returns
 * true if one or more of the following four conditions are met:
 *
 *  1. If the cbtdisabled consensus parameter is set.
 *  2. If the torrc option LearnCircuitBuildTimeout is false.
 *  3. If we are a directory authority
 *  4. If we fail to write circuit build time history to our state file.
 */
150
151
152
static int
circuit_build_times_disabled(void)
{
Mike Perry's avatar
Mike Perry committed
153
  if (unit_tests) {
154
    return 0;
Mike Perry's avatar
Mike Perry committed
155
156
  } else {
    int consensus_disabled = networkstatus_get_param(NULL, "cbtdisabled",
157
                                                     0, 0, 1);
Mike Perry's avatar
Mike Perry committed
158
159
    int config_disabled = !get_options()->LearnCircuitBuildTimeout;
    int dirauth_disabled = get_options()->AuthoritativeDir;
160
    int state_disabled = did_last_state_file_write_fail() ? 1 : 0;
Mike Perry's avatar
Mike Perry committed
161
162
163

    if (consensus_disabled || config_disabled || dirauth_disabled ||
           state_disabled) {
164
      log_debug(LD_CIRC,
Mike Perry's avatar
Mike Perry committed
165
166
167
168
169
170
               "CircuitBuildTime learning is disabled. "
               "Consensus=%d, Config=%d, AuthDir=%d, StateFile=%d",
               consensus_disabled, config_disabled, dirauth_disabled,
               state_disabled);
      return 1;
    } else {
171
      log_debug(LD_CIRC,
172
173
174
175
                "CircuitBuildTime learning is not disabled. "
                "Consensus=%d, Config=%d, AuthDir=%d, StateFile=%d",
                consensus_disabled, config_disabled, dirauth_disabled,
                state_disabled);
Mike Perry's avatar
Mike Perry committed
176
177
      return 0;
    }
178
179
180
  }
}

Mike Perry's avatar
Mike Perry committed
181
182
183
184
185
186
187
/**
 * Retrieve and bounds-check the cbtmaxtimeouts consensus paramter.
 *
 * Effect: When this many timeouts happen in the last 'cbtrecentcount'
 * circuit attempts, the client should discard all of its history and
 * begin learning a fresh timeout value.
 */
Mike Perry's avatar
Mike Perry committed
188
189
190
static int32_t
circuit_build_times_max_timeouts(void)
{
191
192
193
  int32_t cbt_maxtimeouts;

  cbt_maxtimeouts = networkstatus_get_param(NULL, "cbtmaxtimeouts",
194
195
196
                                 CBT_DEFAULT_MAX_RECENT_TIMEOUT_COUNT,
                                 CBT_MIN_MAX_RECENT_TIMEOUT_COUNT,
                                 CBT_MAX_MAX_RECENT_TIMEOUT_COUNT);
197
198
199
200
201
202
203
204
205

  if (!(get_options()->LearnCircuitBuildTimeout)) {
    log_debug(LD_BUG,
              "circuit_build_times_max_timeouts() called, cbtmaxtimeouts is"
              " %d",
              cbt_maxtimeouts);
  }

  return cbt_maxtimeouts;
Mike Perry's avatar
Mike Perry committed
206
207
}

Mike Perry's avatar
Mike Perry committed
208
209
210
211
212
213
214
215
216
/**
 * Retrieve and bounds-check the cbtnummodes consensus paramter.
 *
 * Effect: This value governs how many modes to use in the weighted
 * average calculation of Pareto parameter Xm. A value of 3 introduces
 * some bias (2-5% of CDF) under ideal conditions, but allows for better
 * performance in the event that a client chooses guard nodes of radically
 * different performance characteristics.
 */
217
218
219
220
static int32_t
circuit_build_times_default_num_xm_modes(void)
{
  int32_t num = networkstatus_get_param(NULL, "cbtnummodes",
221
222
223
                                        CBT_DEFAULT_NUM_XM_MODES,
                                        CBT_MIN_NUM_XM_MODES,
                                        CBT_MAX_NUM_XM_MODES);
224
225
226
227
228
229
230
231

  if (!(get_options()->LearnCircuitBuildTimeout)) {
    log_debug(LD_BUG,
              "circuit_build_times_default_num_xm_modes() called, cbtnummodes"
              " is %d",
              num);
  }

232
233
234
  return num;
}

Mike Perry's avatar
Mike Perry committed
235
236
237
238
239
240
/**
 * Retrieve and bounds-check the cbtmincircs consensus paramter.
 *
 * Effect: This is the minimum number of circuits to build before
 * computing a timeout.
 */
Mike Perry's avatar
Mike Perry committed
241
242
243
244
static int32_t
circuit_build_times_min_circs_to_observe(void)
{
  int32_t num = networkstatus_get_param(NULL, "cbtmincircs",
245
246
247
                                        CBT_DEFAULT_MIN_CIRCUITS_TO_OBSERVE,
                                        CBT_MIN_MIN_CIRCUITS_TO_OBSERVE,
                                        CBT_MAX_MIN_CIRCUITS_TO_OBSERVE);
248
249
250
251
252
253
254
255

  if (!(get_options()->LearnCircuitBuildTimeout)) {
    log_debug(LD_BUG,
              "circuit_build_times_min_circs_to_observe() called, cbtmincircs"
              " is %d",
              num);
  }

Mike Perry's avatar
Mike Perry committed
256
257
258
  return num;
}

259
260
261
262
263
264
265
266
/** Return true iff <b>cbt</b> has recorded enough build times that we
 * want to start acting on the timeout it implies. */
int
circuit_build_times_enough_to_compute(circuit_build_times_t *cbt)
{
  return cbt->total_build_times >= circuit_build_times_min_circs_to_observe();
}

Mike Perry's avatar
Mike Perry committed
267
268
269
270
271
272
/**
 * Retrieve and bounds-check the cbtquantile consensus paramter.
 *
 * Effect: This is the position on the quantile curve to use to set the
 * timeout value. It is a percent (10-99).
 */
Mike Perry's avatar
Mike Perry committed
273
274
275
276
double
circuit_build_times_quantile_cutoff(void)
{
  int32_t num = networkstatus_get_param(NULL, "cbtquantile",
277
278
279
                                        CBT_DEFAULT_QUANTILE_CUTOFF,
                                        CBT_MIN_QUANTILE_CUTOFF,
                                        CBT_MAX_QUANTILE_CUTOFF);
280
281
282
283
284
285
286
287

  if (!(get_options()->LearnCircuitBuildTimeout)) {
    log_debug(LD_BUG,
              "circuit_build_times_quantile_cutoff() called, cbtquantile"
              " is %d",
              num);
  }

Mike Perry's avatar
Mike Perry committed
288
289
290
  return num/100.0;
}

291
/* DOCDOC circuit_build_times_get_bw_scale */
292
293
294
295
296
297
298
299
300
int
circuit_build_times_get_bw_scale(networkstatus_t *ns)
{
  return networkstatus_get_param(ns, "bwweightscale",
                                 BW_WEIGHT_SCALE,
                                 BW_MIN_WEIGHT_SCALE,
                                 BW_MAX_WEIGHT_SCALE);
}

Mike Perry's avatar
Mike Perry committed
301
302
303
304
305
306
307
/**
 * Retrieve and bounds-check the cbtclosequantile consensus paramter.
 *
 * Effect: This is the position on the quantile curve to use to set the
 * timeout value to use to actually close circuits. It is a percent
 * (0-99).
 */
308
309
310
static double
circuit_build_times_close_quantile(void)
{
311
312
313
314
  int32_t param;
  /* Cast is safe - circuit_build_times_quantile_cutoff() is capped */
  int32_t min = (int)tor_lround(100*circuit_build_times_quantile_cutoff());
  param = networkstatus_get_param(NULL, "cbtclosequantile",
315
             CBT_DEFAULT_CLOSE_QUANTILE,
316
317
             CBT_MIN_CLOSE_QUANTILE,
             CBT_MAX_CLOSE_QUANTILE);
318
319
320
321
322
323
324

  if (!(get_options()->LearnCircuitBuildTimeout)) {
    log_debug(LD_BUG,
              "circuit_build_times_close_quantile() called, cbtclosequantile"
              " is %d", param);
  }

325
326
327
328
329
330
  if (param < min) {
    log_warn(LD_DIR, "Consensus parameter cbtclosequantile is "
             "too small, raising to %d", min);
    param = min;
  }
  return param / 100.0;
331
332
}

Mike Perry's avatar
Mike Perry committed
333
334
335
336
337
338
339
/**
 * Retrieve and bounds-check the cbttestfreq consensus paramter.
 *
 * Effect: Describes how often in seconds to build a test circuit to
 * gather timeout values. Only applies if less than 'cbtmincircs'
 * have been recorded.
 */
Mike Perry's avatar
Mike Perry committed
340
341
342
343
static int32_t
circuit_build_times_test_frequency(void)
{
  int32_t num = networkstatus_get_param(NULL, "cbttestfreq",
344
345
346
                                        CBT_DEFAULT_TEST_FREQUENCY,
                                        CBT_MIN_TEST_FREQUENCY,
                                        CBT_MAX_TEST_FREQUENCY);
347
348
349
350
351
352
353

  if (!(get_options()->LearnCircuitBuildTimeout)) {
    log_debug(LD_BUG,
              "circuit_build_times_test_frequency() called, cbttestfreq is %d",
              num);
  }

Mike Perry's avatar
Mike Perry committed
354
355
356
  return num;
}

Mike Perry's avatar
Mike Perry committed
357
/**
358
 * Retrieve and bounds-check the cbtmintimeout consensus parameter.
Mike Perry's avatar
Mike Perry committed
359
360
361
362
363
 *
 * Effect: This is the minimum allowed timeout value in milliseconds.
 * The minimum is to prevent rounding to 0 (we only check once
 * per second).
 */
Mike Perry's avatar
Mike Perry committed
364
365
366
367
static int32_t
circuit_build_times_min_timeout(void)
{
  int32_t num = networkstatus_get_param(NULL, "cbtmintimeout",
368
369
370
                                        CBT_DEFAULT_TIMEOUT_MIN_VALUE,
                                        CBT_MIN_TIMEOUT_MIN_VALUE,
                                        CBT_MAX_TIMEOUT_MIN_VALUE);
371
372
373
374
375
376
377

  if (!(get_options()->LearnCircuitBuildTimeout)) {
    log_debug(LD_BUG,
              "circuit_build_times_min_timeout() called, cbtmintimeout is %d",
              num);
  }

Mike Perry's avatar
Mike Perry committed
378
379
380
  return num;
}

Mike Perry's avatar
Mike Perry committed
381
382
383
384
385
386
/**
 * Retrieve and bounds-check the cbtinitialtimeout consensus paramter.
 *
 * Effect: This is the timeout value to use before computing a timeout,
 * in milliseconds.
 */
Mike Perry's avatar
Mike Perry committed
387
388
389
int32_t
circuit_build_times_initial_timeout(void)
{
390
391
392
393
394
  int32_t min = circuit_build_times_min_timeout();
  int32_t param = networkstatus_get_param(NULL, "cbtinitialtimeout",
                                          CBT_DEFAULT_TIMEOUT_INITIAL_VALUE,
                                          CBT_MIN_TIMEOUT_INITIAL_VALUE,
                                          CBT_MAX_TIMEOUT_INITIAL_VALUE);
395
396
397
398
399
400
401
402

  if (!(get_options()->LearnCircuitBuildTimeout)) {
    log_debug(LD_BUG,
              "circuit_build_times_initial_timeout() called, "
              "cbtinitialtimeout is %d",
              param);
  }

403
404
405
406
407
408
  if (param < min) {
    log_warn(LD_DIR, "Consensus parameter cbtinitialtimeout is too small, "
             "raising to %d", min);
    param = min;
  }
  return param;
Mike Perry's avatar
Mike Perry committed
409
410
}

Mike Perry's avatar
Mike Perry committed
411
412
413
414
415
416
417
/**
 * Retrieve and bounds-check the cbtrecentcount consensus paramter.
 *
 * Effect: This is the number of circuit build times to keep track of
 * for deciding if we hit cbtmaxtimeouts and need to reset our state
 * and learn a new timeout.
 */
Mike Perry's avatar
Mike Perry committed
418
static int32_t
419
circuit_build_times_recent_circuit_count(networkstatus_t *ns)
Mike Perry's avatar
Mike Perry committed
420
{
421
422
423
424
425
426
427
428
429
430
431
432
433
434
  int32_t num;
  num = networkstatus_get_param(ns, "cbtrecentcount",
                                CBT_DEFAULT_RECENT_CIRCUITS,
                                CBT_MIN_RECENT_CIRCUITS,
                                CBT_MAX_RECENT_CIRCUITS);

  if (!(get_options()->LearnCircuitBuildTimeout)) {
    log_debug(LD_BUG,
              "circuit_build_times_recent_circuit_count() called, "
              "cbtrecentcount is %d",
              num);
  }

  return num;
Mike Perry's avatar
Mike Perry committed
435
436
}

437
438
439
440
441
442
/**
 * 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
443
444
445
446
void
circuit_build_times_new_consensus_params(circuit_build_times_t *cbt,
                                         networkstatus_t *ns)
{
447
  int32_t num;
Mike Perry's avatar
Mike Perry committed
448

449
450
451
452
  /*
   * First check if we're doing adaptive timeouts at all; nothing to
   * update if we aren't.
   */
Mike Perry's avatar
Mike Perry committed
453

454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
  if (!circuit_build_times_disabled()) {
    num = circuit_build_times_recent_circuit_count(ns);

    if (num > 0) {
      if (num != cbt->liveness.num_recent_circs) {
        int8_t *recent_circs;
        log_notice(LD_CIRC, "The Tor Directory Consensus has changed how many "
                   "circuits we must track to detect network failures from %d "
                   "to %d.", cbt->liveness.num_recent_circs, num);

        tor_assert(cbt->liveness.timeouts_after_firsthop ||
                   cbt->liveness.num_recent_circs == 0);

        /*
         * 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.
         */
        recent_circs = tor_malloc_zero(sizeof(int8_t)*num);
        if (cbt->liveness.timeouts_after_firsthop &&
            cbt->liveness.num_recent_circs > 0) {
          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;
      }
      /* else no change, nothing to do */
Andrea Shepard's avatar
Andrea Shepard committed
497
    } else { /* num == 0 */
498
499
500
501
502
503
504
505
506
507
      /*
       * Weird.  This probably shouldn't happen, so log a warning, but try
       * to do something sensible anyway.
       */

      log_warn(LD_CIRC,
               "The cbtrecentcircs consensus parameter came back zero!  "
               "This disables adaptive timeouts since we can't keep track of "
               "any recent circuits.");

508
      circuit_build_times_free_timeouts(cbt);
509
    }
Andrea Shepard's avatar
Andrea Shepard committed
510
  } else {
511
    /*
512
513
514
515
516
     * Adaptive timeouts are disabled; this might be because of the
     * LearnCircuitBuildTimes config parameter, and hence permanent, or
     * the cbtdisabled consensus parameter, so it may be a new condition.
     * Treat it like getting num == 0 above and free the circuit history
     * if we have any.
517
     */
518

519
    circuit_build_times_free_timeouts(cbt);
Mike Perry's avatar
Mike Perry committed
520
521
522
  }
}

523
524
/** Make a note that we're running unit tests (rather than running Tor
 * itself), so we avoid clobbering our state file. */
525
526
527
528
529
530
void
circuitbuild_running_unit_tests(void)
{
  unit_tests = 1;
}

531
532
533
534
535
536
537
/**
 * Return the initial default or configured timeout in milliseconds
 */
static double
circuit_build_times_get_initial_timeout(void)
{
  double timeout;
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552

  /*
   * Check if we have LearnCircuitBuildTimeout, and if we don't,
   * always use CircuitBuildTimeout, no questions asked.
   */
  if (get_options()->LearnCircuitBuildTimeout) {
    if (!unit_tests && get_options()->CircuitBuildTimeout) {
      timeout = get_options()->CircuitBuildTimeout*1000;
      if (timeout < circuit_build_times_min_timeout()) {
        log_warn(LD_CIRC, "Config CircuitBuildTimeout too low. Setting to %ds",
                 circuit_build_times_min_timeout()/1000);
        timeout = circuit_build_times_min_timeout();
      }
    } else {
      timeout = circuit_build_times_initial_timeout();
553
    }
Andrea Shepard's avatar
Andrea Shepard committed
554
  } else {
555
556
557
    timeout = get_options()->CircuitBuildTimeout*1000;
  }

558
559
560
  return timeout;
}

Mike Perry's avatar
Mike Perry committed
561
562
563
/**
 * Reset the build time state.
 *
564
 * Leave estimated parameters, timeout and network liveness intact
Mike Perry's avatar
Mike Perry committed
565
566
 * for future use.
 */
567
568
569
570
571
572
void
circuit_build_times_reset(circuit_build_times_t *cbt)
{
  memset(cbt->circuit_build_times, 0, sizeof(cbt->circuit_build_times));
  cbt->total_build_times = 0;
  cbt->build_times_idx = 0;
Mike Perry's avatar
Mike Perry committed
573
  cbt->have_computed_timeout = 0;
574
575
}

Mike Perry's avatar
Mike Perry committed
576
577
578
/**
 * Initialize the buildtimes structure for first use.
 *
579
580
 * Sets the initial timeout values based on either the config setting,
 * the consensus param, or the default (CBT_DEFAULT_TIMEOUT_INITIAL_VALUE).
Mike Perry's avatar
Mike Perry committed
581
 */
582
583
584
585
void
circuit_build_times_init(circuit_build_times_t *cbt)
{
  memset(cbt, 0, sizeof(*cbt));
586
587
588
589
590
591
  /*
   * Check if we really are using adaptive timeouts, and don't keep
   * track of this stuff if not.
   */
  if (!circuit_build_times_disabled()) {
    cbt->liveness.num_recent_circs =
592
      circuit_build_times_recent_circuit_count(NULL);
593
594
    cbt->liveness.timeouts_after_firsthop =
      tor_malloc_zero(sizeof(int8_t)*cbt->liveness.num_recent_circs);
Andrea Shepard's avatar
Andrea Shepard committed
595
  } else {
596
597
598
    cbt->liveness.num_recent_circs = 0;
    cbt->liveness.timeouts_after_firsthop = NULL;
  }
599
  cbt->close_ms = cbt->timeout_ms = circuit_build_times_get_initial_timeout();
600
  control_event_buildtimeout_set(cbt, BUILDTIMEOUT_SET_EVENT_RESET);
601
}
602

603
604
605
606
607
/**
 * Free the saved timeouts, if the cbtdisabled consensus parameter got turned
 * on or something.
 */

Andrea Shepard's avatar
Andrea Shepard committed
608
609
610
void
circuit_build_times_free_timeouts(circuit_build_times_t *cbt)
{
611
612
613
614
615
616
617
618
619
  if (!cbt) return;

  if (cbt->liveness.timeouts_after_firsthop) {
    tor_free(cbt->liveness.timeouts_after_firsthop);
  }

  cbt->liveness.num_recent_circs = 0;
}

620
#if 0
621
/**
622
 * Rewind our build time history by n positions.
623
624
625
626
627
628
629
 */
static void
circuit_build_times_rewind_history(circuit_build_times_t *cbt, int n)
{
  int i = 0;

  cbt->build_times_idx -= n;
Mike Perry's avatar
Mike Perry committed
630
  cbt->build_times_idx %= CBT_NCIRCUITS_TO_OBSERVE;
631
632

  for (i = 0; i < n; i++) {
Mike Perry's avatar
Mike Perry committed
633
634
    cbt->circuit_build_times[(i+cbt->build_times_idx)
                             %CBT_NCIRCUITS_TO_OBSERVE]=0;
635
636
637
638
  }

  if (cbt->total_build_times > n) {
    cbt->total_build_times -= n;
639
  } else {
640
    cbt->total_build_times = 0;
641
  }
642
643
644
645

  log_info(LD_CIRC,
          "Rewound history by %d places. Current index: %d. "
          "Total: %d", n, cbt->build_times_idx, cbt->total_build_times);
646
}
647
#endif
648

649
/**
650
 * Add a new build time value <b>time</b> to the set of build times. Time
651
 * units are milliseconds.
652
 *
653
 * circuit_build_times <b>cbt</b> is a circular array, so loop around when
Mike Perry's avatar
Mike Perry committed
654
 * array is full.
655
656
 */
int
657
circuit_build_times_add_time(circuit_build_times_t *cbt, build_time_t time)
658
{
659
  if (time <= 0 || time > CBT_BUILD_TIME_MAX) {
660
661
    log_warn(LD_BUG, "Circuit build time is too large (%u)."
                      "This is probably a bug.", time);
662
    tor_fragile_assert();
663
    return -1;
664
  }
665

666
  log_debug(LD_CIRC, "Adding circuit build time %u", time);
667

668
  cbt->circuit_build_times[cbt->build_times_idx] = time;
Mike Perry's avatar
Mike Perry committed
669
670
  cbt->build_times_idx = (cbt->build_times_idx + 1) % CBT_NCIRCUITS_TO_OBSERVE;
  if (cbt->total_build_times < CBT_NCIRCUITS_TO_OBSERVE)
671
    cbt->total_build_times++;
672

Mike Perry's avatar
Mike Perry committed
673
  if ((cbt->total_build_times % CBT_SAVE_STATE_EVERY) == 0) {
674
    /* Save state every n circuit builds */
675
    if (!unit_tests && !get_options()->AvoidDiskWrites)
Mike Perry's avatar
Mike Perry committed
676
677
678
      or_state_mark_dirty(get_or_state(), 0);
  }

679
680
681
682
  return 0;
}

/**
Mike Perry's avatar
Mike Perry committed
683
 * Return maximum circuit build time
684
 */
685
static build_time_t
686
circuit_build_times_max(circuit_build_times_t *cbt)
687
{
688
689
  int i = 0;
  build_time_t max_build_time = 0;
Mike Perry's avatar
Mike Perry committed
690
  for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
691
    if (cbt->circuit_build_times[i] > max_build_time
692
            && cbt->circuit_build_times[i] != CBT_BUILD_ABANDONED)
693
      max_build_time = cbt->circuit_build_times[i];
694
695
696
697
  }
  return max_build_time;
}

698
#if 0
Mike Perry's avatar
Mike Perry committed
699
/** Return minimum circuit build time */
700
build_time_t
701
circuit_build_times_min(circuit_build_times_t *cbt)
702
703
{
  int i = 0;
Mike Perry's avatar
Mike Perry committed
704
705
  build_time_t min_build_time = CBT_BUILD_TIME_MAX;
  for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
706
    if (cbt->circuit_build_times[i] && /* 0 <-> uninitialized */
707
        cbt->circuit_build_times[i] < min_build_time)
708
709
      min_build_time = cbt->circuit_build_times[i];
  }
Mike Perry's avatar
Mike Perry committed
710
711
  if (min_build_time == CBT_BUILD_TIME_MAX) {
    log_warn(LD_CIRC, "No build times less than CBT_BUILD_TIME_MAX!");
712
713
714
  }
  return min_build_time;
}
715
#endif
716

717
/**
Mike Perry's avatar
Mike Perry committed
718
719
720
 * 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
721
 * the frequency of index*CBT_BIN_WIDTH millisecond
Mike Perry's avatar
Mike Perry committed
722
723
724
 * build times. Also outputs the number of bins in nbins.
 *
 * The return value must be freed by the caller.
725
726
727
728
729
730
731
732
733
 */
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
734
  *nbins = 1 + (max_build_time / CBT_BIN_WIDTH);
735
736
737
  histogram = tor_malloc_zero(*nbins * sizeof(build_time_t));

  // calculate histogram
Mike Perry's avatar
Mike Perry committed
738
  for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
739
    if (cbt->circuit_build_times[i] == 0
740
            || cbt->circuit_build_times[i] == CBT_BUILD_ABANDONED)
741
      continue; /* 0 <-> uninitialized */
742

Mike Perry's avatar
Mike Perry committed
743
    c = (cbt->circuit_build_times[i] / CBT_BIN_WIDTH);
744
745
746
747
748
749
    histogram[c]++;
  }

  return histogram;
}

Mike Perry's avatar
Mike Perry committed
750
/**
751
 * Return the Pareto start-of-curve parameter Xm.
Mike Perry's avatar
Mike Perry committed
752
 *
753
 * Because we are not a true Pareto curve, we compute this as the
754
755
756
 * weighted average of the N most frequent build time bins. N is either
 * 1 if we don't have enough circuit build time data collected, or
 * determined by the consensus parameter cbtnummodes (default 3).
Mike Perry's avatar
Mike Perry committed
757
 */
758
static build_time_t
759
circuit_build_times_get_xm(circuit_build_times_t *cbt)
760
{
761
  build_time_t i, nbins;
762
  build_time_t *nth_max_bin;
763
764
  int32_t bin_counts=0;
  build_time_t ret = 0;
765
  uint32_t *histogram = circuit_build_times_create_histogram(cbt, &nbins);
766
  int n=0;
767
  int num_modes = circuit_build_times_default_num_xm_modes();
768

769
770
771
  tor_assert(nbins > 0);
  tor_assert(num_modes > 0);

772
773
774
775
  // Only use one mode if < 1000 buildtimes. Not enough data
  // for multiple.
  if (cbt->total_build_times < CBT_NCIRCUITS_TO_OBSERVE)
    num_modes = 1;
776

777
  nth_max_bin = (build_time_t*)tor_malloc_zero(num_modes*sizeof(build_time_t));
778

779
  /* Determine the N most common build times */
780
  for (i = 0; i < nbins; i++) {
781
782
    if (histogram[i] >= histogram[nth_max_bin[0]]) {
      nth_max_bin[0] = i;
783
    }
784
785
786
787
788
789
790

    for (n = 1; n < num_modes; n++) {
      if (histogram[i] >= histogram[nth_max_bin[n]] &&
           (!histogram[nth_max_bin[n-1]]
               || histogram[i] < histogram[nth_max_bin[n-1]])) {
        nth_max_bin[n] = i;
      }
791
792
793
    }
  }

794
795
796
797
798
  for (n = 0; n < num_modes; n++) {
    bin_counts += histogram[nth_max_bin[n]];
    ret += CBT_BIN_TO_MS(nth_max_bin[n])*histogram[nth_max_bin[n]];
    log_info(LD_CIRC, "Xm mode #%d: %u %u", n, CBT_BIN_TO_MS(nth_max_bin[n]),
             histogram[nth_max_bin[n]]);
799
800
  }

801
802
803
804
  /* The following assert is safe, because we don't get called when we
   * haven't observed at least CBT_MIN_MIN_CIRCUITS_TO_OBSERVE circuits. */
  tor_assert(bin_counts > 0);

805
  ret /= bin_counts;
Mike Perry's avatar
Mike Perry committed
806
  tor_free(histogram);
807
  tor_free(nth_max_bin);
Mike Perry's avatar
Mike Perry committed
808

809
  return ret;
810
811
}

812
/**
Mike Perry's avatar
Mike Perry committed
813
814
 * Output a histogram of current circuit build times to
 * the or_state_t state structure.
815
816
 */
void
817
circuit_build_times_update_state(circuit_build_times_t *cbt,
818
                                 or_state_t *state)
819
{
820
  uint32_t *histogram;
821
  build_time_t i = 0;
822
  build_time_t nbins = 0;
823
824
  config_line_t **next, *line;

825
  histogram = circuit_build_times_create_histogram(cbt, &nbins);
826
827
828
829
830
  // write to state
  config_free_lines(state->BuildtimeHistogram);
  next = &state->BuildtimeHistogram;
  *next = NULL;

831
  state->TotalBuildTimes = cbt->total_build_times;
832
  state->CircuitBuildAbandonedCount = 0;
Mike Perry's avatar
Mike Perry committed
833
834

  for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
835
836
    if (cbt->circuit_build_times[i] == CBT_BUILD_ABANDONED)
      state->CircuitBuildAbandonedCount++;
Mike Perry's avatar
Mike Perry committed
837
  }
838

839
  for (i = 0; i < nbins; i++) {
840
841
    // compress the histogram by skipping the blanks
    if (histogram[i] == 0) continue;
842
843
    *next = line = tor_malloc_zero(sizeof(config_line_t));
    line->key = tor_strdup("CircuitBuildTimeBin");
844
    tor_asprintf(&line->value, "%d %d",
845
            CBT_BIN_TO_MS(i), histogram[i]);
846
847
    next = &(line->next);
  }
848

849
  if (!unit_tests) {
850
851
852
    if (!get_options()->AvoidDiskWrites)
      or_state_mark_dirty(get_or_state(), 0);
  }
853

854
  tor_free(histogram);
855
856
}

Mike Perry's avatar
Mike Perry committed
857
858
859
/**
 * Shuffle the build times array.
 *
860
 * Adapted from http://en.wikipedia.org/wiki/Fisher-Yates_shuffle
Mike Perry's avatar
Mike Perry committed
861
 */
862
static void
863
864
circuit_build_times_shuffle_and_store_array(circuit_build_times_t *cbt,
                                            build_time_t *raw_times,
865
                                            uint32_t num_times)
866
{
867
  uint32_t n = num_times;
Mike Perry's avatar
Mike Perry committed
868
  if (num_times > CBT_NCIRCUITS_TO_OBSERVE) {
869
870
871
    log_notice(LD_CIRC, "The number of circuit times that this Tor version "
               "uses to calculate build times is less than the number stored "
               "in your state file. Decreasing the circuit time history from "
872
873
874
875
876
877
878
879
880
               "%lu to %d.", (unsigned long)num_times,
               CBT_NCIRCUITS_TO_OBSERVE);
  }

  if (n > INT_MAX-1) {
    log_warn(LD_CIRC, "For some insane reasons, you had %lu circuit build "
             "observations in your state file. That's far too many; probably "
             "there's a bug here.", (unsigned long)n);
    n = INT_MAX-1;
881
882
883
884
885
886
887
888
889
890
  }

  /* 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
891
892
893
  /* 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++) {
894
895
    circuit_build_times_add_time(cbt, raw_times[n]);
  }
896
897
}

Mike Perry's avatar
Mike Perry committed
898
899
/**
 * Filter old synthetic timeouts that were created before the
900
901
902
903
 * new right-censored Pareto calculation was deployed.
 *
 * Once all clients before 0.2.1.13-alpha are gone, this code
 * will be unused.
Mike Perry's avatar
Mike Perry committed
904
905
906
907
908
909
910
911
912
 */
static int
circuit_build_times_filter_timeouts(circuit_build_times_t *cbt)
{
  int num_filtered=0, i=0;
  double timeout_rate = 0;
  build_time_t max_timeout = 0;

  timeout_rate = circuit_build_times_timeout_rate(cbt);
913
  max_timeout = (build_time_t)cbt->close_ms;
Mike Perry's avatar
Mike Perry committed
914
915
916
917
918

  for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
    if (cbt->circuit_build_times[i] > max_timeout) {
      build_time_t replaced = cbt->circuit_build_times[i];
      num_filtered++;
919
      cbt->circuit_build_times[i] = CBT_BUILD_ABANDONED;
Mike Perry's avatar
Mike Perry committed
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934

      log_debug(LD_CIRC, "Replaced timeout %d with %d", replaced,
               cbt->circuit_build_times[i]);
    }
  }

  log_info(LD_CIRC,
           "We had %d timeouts out of %d build times, "
           "and filtered %d above the max of %u",
          (int)(cbt->total_build_times*timeout_rate),
          cbt->total_build_times, num_filtered, max_timeout);

  return num_filtered;
}

Mike Perry's avatar
Mike Perry committed
935
936
937
938
939
/**
 * Load histogram from <b>state</b>, shuffling the resulting array
 * after we do so. Use this result to estimate parameters and
 * calculate the timeout.
 *
940
 * Return -1 on error.
Mike Perry's avatar
Mike Perry committed
941
 */
942
int
943
circuit_build_times_parse_state(circuit_build_times_t *cbt,
944
                                or_state_t *state)
945
{
946
947
  int tot_values = 0;
  uint32_t loaded_cnt = 0, N = 0;
948
  config_line_t *line;
Mike Perry's avatar
Mike Perry committed
949
  unsigned int i;
950
  build_time_t *loaded_times;
951
  int err = 0;
952
  circuit_build_times_init(cbt);
953

954
955
956
957
  if (circuit_build_times_disabled()) {
    return 0;
  }

958
959
  /* build_time_t 0 means uninitialized */
  loaded_times = tor_malloc_zero(sizeof(build_time_t)*state->TotalBuildTimes);
960

961
  for (line = state->BuildtimeHistogram; line; line = line->next) {
962
    smartlist_t *args = smartlist_new();
963
    smartlist_split_string(args, line->value, " ",
964
                           SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
965
    if (smartlist_len(args) < 2) {
966
967
968
      log_warn(LD_GENERAL, "Unable to parse circuit build times: "
                           "Too few arguments to CircuitBuildTime");
      err = 1;
Mike Perry's avatar
Mike Perry committed
969
970
      SMARTLIST_FOREACH(args, char*, cp, tor_free(cp));
      smartlist_free(args);
971
972
      break;
    } else {
973
974
      const char *ms_str = smartlist_get(args,0);
      const char *count_str = smartlist_get(args,1);
975
      uint32_t count, k;
976
      build_time_t ms;
977
      int ok;
978
      ms = (build_time_t)tor_parse_ulong(ms_str, 0, 0,
Mike Perry's avatar
Mike Perry committed
979
                                         CBT_BUILD_TIME_MAX, &ok, NULL);
980
      if (!ok) {
981
982
983
        log_warn(LD_GENERAL, "Unable to parse circuit build times: "
                             "Unparsable bin number");
        err = 1;
Sebastian Hahn's avatar
Sebastian Hahn committed
984
985
        SMARTLIST_FOREACH(args, char*, cp, tor_free(cp));
        smartlist_free(args);
986
987
        break;
      }
988
989
      count = (uint32_t)tor_parse_ulong(count_str, 0, 0,
                                        UINT32_MAX, &ok, NULL);
990
      if (!ok) {
991
992
993
        log_warn(LD_GENERAL, "Unable to parse circuit build times: "
                             "Unparsable bin count");
        err = 1;
Sebastian Hahn's avatar
Sebastian Hahn committed
994
995
        SMARTLIST_FOREACH(args, char*, cp, tor_free(cp));
        smartlist_free(args);
996
997
        break;
      }
998

999
      if (loaded_cnt+count+state->CircuitBuildAbandonedCount
Mike Perry's avatar
Mike Perry committed
1000
            > state->TotalBuildTimes) {
For faster browsing, not all history is shown. View entire blame