circuitstats.c 62.1 KB
Newer Older
1
2
3
/* Copyright (c) 2001 Matej Pfajfar.
 * Copyright (c) 2001-2004, Roger Dingledine.
 * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
Nick Mathewson's avatar
Nick Mathewson committed
4
 * Copyright (c) 2007-2018, The Tor Project, Inc. */
5
6
/* See LICENSE for licensing information */

7
8
9
10
11
/**
 * \file circuitstats.c
 *
 * \brief Maintains and analyzes statistics about circuit built times, so we
 * can tell how long we may need to wait for a fast circuit to be constructed.
12
13
14
15
16
17
18
19
20
21
22
23
 *
 * By keeping these statistics, a client learns when it should time out a slow
 * circuit for being too slow, and when it should keep a circuit open in order
 * to wait for it to complete.
 *
 * The information here is kept in a circuit_built_times_t structure, which is
 * currently a singleton, but doesn't need to be.  It's updated by calls to
 * circuit_build_times_count_timeout() from circuituse.c,
 * circuit_build_times_count_close() from circuituse.c, and
 * circuit_build_times_add_time() from circuitbuild.c, and inspected by other
 * calls into this module, mostly from circuitlist.c.  Observations are
 * persisted to disk via the or_state_t-related calls.
24
25
 */

26
27
#define CIRCUITSTATS_PRIVATE

28
29
30
31
32
33
#include "core/or/or.h"
#include "core/or/circuitbuild.h"
#include "core/or/circuitstats.h"
#include "app/config/config.h"
#include "app/config/confparse.h"
#include "feature/control/control.h"
34
#include "lib/crypt_ops/crypto_rand.h"
35
#include "core/mainloop/mainloop.h"
36
37
38
39
40
41
42
#include "feature/nodelist/networkstatus.h"
#include "feature/rend/rendclient.h"
#include "feature/rend/rendservice.h"
#include "feature/relay/router.h"
#include "app/config/statefile.h"
#include "core/or/circuitlist.h"
#include "core/or/circuituse.h"
43
#include "lib/math/fp.h"
44
#include "lib/time/tvdiff.h"
45
#include "lib/encoding/confline.h"
Nick Mathewson's avatar
Nick Mathewson committed
46

47
48
49
#include "core/or/crypt_path_st.h"
#include "core/or/origin_circuit_st.h"
#include "app/config/or_state_st.h"
50

51
52
53
#undef log
#include <math.h>

54
55
56
static void cbt_control_event_buildtimeout_set(
                                  const circuit_build_times_t *cbt,
                                  buildtimeout_set_event_t type);
57
static void circuit_build_times_scale_circ_counts(circuit_build_times_t *cbt);
58

59
60
61
62
63
64
65
66
#define CBT_BIN_TO_MS(bin) ((bin)*CBT_BIN_WIDTH + (CBT_BIN_WIDTH/2))

/** Global list of circuit build times */
// XXXX: Add this as a member for entry_guard_t instead of global?
// 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.
67
static circuit_build_times_t circ_times;
68

69
#ifdef TOR_UNIT_TESTS
70
71
72
/** If set, we're running the unit tests: we should avoid clobbering
 * our state file or accessing get_options() or get_or_state() */
static int unit_tests = 0;
73
74
#else
#define unit_tests 0
75
#endif /* defined(TOR_UNIT_TESTS) */
76

77
78
/** Return a pointer to the data structure describing our current circuit
 * build time history and computations. */
79
const circuit_build_times_t *
80
81
82
83
84
get_circuit_build_times(void)
{
  return &circ_times;
}

85
/** As get_circuit_build_times, but return a mutable pointer. */
86
87
88
89
90
91
circuit_build_times_t *
get_circuit_build_times_mutable(void)
{
  return &circ_times;
}

92
93
/** Return the time to wait before actually closing an under-construction, in
 * milliseconds. */
94
double
95
get_circuit_build_close_time_ms(void)
96
97
98
99
{
  return circ_times.close_ms;
}

100
101
/** Return the time to wait before giving up on an under-construction circuit,
 * in milliseconds. */
102
double
103
get_circuit_build_timeout_ms(void)
104
105
106
107
{
  return circ_times.timeout_ms;
}

108
109
/**
 * This function decides if CBT learning should be disabled. It returns
110
 * true if one or more of the following conditions are met:
111
112
113
114
115
 *
 *  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.
David Goulet's avatar
David Goulet committed
116
 *  5. If we are configured in Single Onion mode
117
118
 */
int
119
circuit_build_times_disabled(const or_options_t *options)
120
{
121
  return circuit_build_times_disabled_(options, 0);
122
123
124
125
126
127
}

/** As circuit_build_times_disabled, but take options as an argument. */
int
circuit_build_times_disabled_(const or_options_t *options,
                              int ignore_consensus)
128
129
130
131
{
  if (unit_tests) {
    return 0;
  } else {
132
133
    int consensus_disabled =
      ignore_consensus ? 0 : networkstatus_get_param(NULL, "cbtdisabled",
134
                                                     0, 0, 1);
135
    int config_disabled = !options->LearnCircuitBuildTimeout;
136
    int dirauth_disabled = authdir_mode(options);
137
    int state_disabled = did_last_state_file_write_fail() ? 1 : 0;
David Goulet's avatar
David Goulet committed
138
    /* LearnCircuitBuildTimeout and Single Onion Services are
139
140
141
142
143
144
145
146
147
148
149
150
151
     * incompatible in two ways:
     *
     * - LearnCircuitBuildTimeout results in a low CBT, which
     *   Single Onion use of one-hop intro and rendezvous circuits lowers
     *   much further, producing *far* too many timeouts.
     *
     * - The adaptive CBT code does not update its timeout estimate
     *   using build times for single-hop circuits.
     *
     * If we fix both of these issues someday, we should test
     * these modes with LearnCircuitBuildTimeout on again. */
    int single_onion_disabled = rend_service_allow_non_anonymous_connection(
                                                                      options);
152
153

    if (consensus_disabled || config_disabled || dirauth_disabled ||
David Goulet's avatar
David Goulet committed
154
        state_disabled || single_onion_disabled) {
155
#if 0
156
157
158
159
160
      log_debug(LD_CIRC,
               "CircuitBuildTime learning is disabled. "
               "Consensus=%d, Config=%d, AuthDir=%d, StateFile=%d",
               consensus_disabled, config_disabled, dirauth_disabled,
               state_disabled);
161
#endif /* 0 */
162
163
      return 1;
    } else {
164
#if 0
165
166
167
168
169
      log_debug(LD_CIRC,
                "CircuitBuildTime learning is not disabled. "
                "Consensus=%d, Config=%d, AuthDir=%d, StateFile=%d",
                consensus_disabled, config_disabled, dirauth_disabled,
                state_disabled);
170
#endif /* 0 */
171
172
173
174
175
176
      return 0;
    }
  }
}

/**
177
 * Retrieve and bounds-check the cbtmaxtimeouts consensus parameter.
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
 *
 * 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.
 */
static int32_t
circuit_build_times_max_timeouts(void)
{
  int32_t cbt_maxtimeouts;

  cbt_maxtimeouts = networkstatus_get_param(NULL, "cbtmaxtimeouts",
                                 CBT_DEFAULT_MAX_RECENT_TIMEOUT_COUNT,
                                 CBT_MIN_MAX_RECENT_TIMEOUT_COUNT,
                                 CBT_MAX_MAX_RECENT_TIMEOUT_COUNT);

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

  return cbt_maxtimeouts;
}

/**
204
 * Retrieve and bounds-check the cbtnummodes consensus parameter.
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
 *
 * 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.
 */
static int32_t
circuit_build_times_default_num_xm_modes(void)
{
  int32_t num = networkstatus_get_param(NULL, "cbtnummodes",
                                        CBT_DEFAULT_NUM_XM_MODES,
                                        CBT_MIN_NUM_XM_MODES,
                                        CBT_MAX_NUM_XM_MODES);

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

  return num;
}

/**
231
 * Retrieve and bounds-check the cbtmincircs consensus parameter.
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
 *
 * Effect: This is the minimum number of circuits to build before
 * computing a timeout.
 */
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,
                                        CBT_MIN_MIN_CIRCUITS_TO_OBSERVE,
                                        CBT_MAX_MIN_CIRCUITS_TO_OBSERVE);

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

  return num;
}

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

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

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

  return num/100.0;
}

/**
287
 * Retrieve and bounds-check the cbtclosequantile consensus parameter.
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
 *
 * 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).
 */
static double
circuit_build_times_close_quantile(void)
{
  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",
             CBT_DEFAULT_CLOSE_QUANTILE,
             CBT_MIN_CLOSE_QUANTILE,
             CBT_MAX_CLOSE_QUANTILE);

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

  if (param < min) {
    log_warn(LD_DIR, "Consensus parameter cbtclosequantile is "
             "too small, raising to %d", min);
    param = min;
  }
  return param / 100.0;
}

/**
319
 * Retrieve and bounds-check the cbttestfreq consensus parameter.
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
 *
 * Effect: Describes how often in seconds to build a test circuit to
 * gather timeout values. Only applies if less than 'cbtmincircs'
 * have been recorded.
 */
static int32_t
circuit_build_times_test_frequency(void)
{
  int32_t num = networkstatus_get_param(NULL, "cbttestfreq",
                                        CBT_DEFAULT_TEST_FREQUENCY,
                                        CBT_MIN_TEST_FREQUENCY,
                                        CBT_MAX_TEST_FREQUENCY);

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

  return num;
}

/**
 * Retrieve and bounds-check the cbtmintimeout consensus parameter.
 *
 * Effect: This is the minimum allowed timeout value in milliseconds.
 * The minimum is to prevent rounding to 0 (we only check once
 * per second).
 */
static int32_t
circuit_build_times_min_timeout(void)
{
  int32_t num = networkstatus_get_param(NULL, "cbtmintimeout",
                                        CBT_DEFAULT_TIMEOUT_MIN_VALUE,
                                        CBT_MIN_TIMEOUT_MIN_VALUE,
                                        CBT_MAX_TIMEOUT_MIN_VALUE);

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

/**
366
 * Retrieve and bounds-check the cbtinitialtimeout consensus parameter.
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
 *
 * Effect: This is the timeout value to use before computing a timeout,
 * in milliseconds.
 */
int32_t
circuit_build_times_initial_timeout(void)
{
  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);

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

  if (param < min) {
    log_warn(LD_DIR, "Consensus parameter cbtinitialtimeout is too small, "
             "raising to %d", min);
    param = min;
  }
  return param;
}

/**
396
 * Retrieve and bounds-check the cbtrecentcount consensus parameter.
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
 *
 * 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.
 */
static int32_t
circuit_build_times_recent_circuit_count(networkstatus_t *ns)
{
  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;
}

/**
 * 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.
 */
void
circuit_build_times_new_consensus_params(circuit_build_times_t *cbt,
                                         networkstatus_t *ns)
{
  int32_t num;

  /*
   * First check if we're doing adaptive timeouts at all; nothing to
   * update if we aren't.
   */

438
  if (!circuit_build_times_disabled(get_options())) {
439
440
441
442
443
    num = circuit_build_times_recent_circuit_count(ns);

    if (num > 0) {
      if (num != cbt->liveness.num_recent_circs) {
        int8_t *recent_circs;
444
445
446
447
448
449
450
451
        if (cbt->liveness.num_recent_circs > 0) {
          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);
        } else {
          log_notice(LD_CIRC, "Upon receiving a consensus directory, "
                     "re-enabling circuit-based network failure detection.");
        }
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467

        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.
         */
468
        recent_circs = tor_calloc(num, sizeof(int8_t));
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
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
        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 */
    } else { /* num == 0 */
      /*
       * 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.");

      circuit_build_times_free_timeouts(cbt);
    }
  } else {
    /*
     * 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.
     */

    circuit_build_times_free_timeouts(cbt);
  }
}

/**
 * Return the initial default or configured timeout in milliseconds
 */
static double
circuit_build_times_get_initial_timeout(void)
{
  double timeout;
519
  const or_options_t *options = get_options();
520
521
522
523
524

  /*
   * Check if we have LearnCircuitBuildTimeout, and if we don't,
   * always use CircuitBuildTimeout, no questions asked.
   */
525
526
527
  if (!unit_tests && options->CircuitBuildTimeout) {
    timeout = options->CircuitBuildTimeout*1000;
    if (!circuit_build_times_disabled(options) &&
528
529
530
531
        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();
532
533
    }
  } else {
534
    timeout = circuit_build_times_initial_timeout();
535
536
537
538
539
540
541
542
543
544
545
  }

  return timeout;
}

/**
 * Reset the build time state.
 *
 * Leave estimated parameters, timeout and network liveness intact
 * for future use.
 */
546
STATIC void
547
548
549
550
551
552
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;
  cbt->have_computed_timeout = 0;
553
554
555
556
557

  // Reset timeout and close counts
  cbt->num_circ_succeeded = 0;
  cbt->num_circ_closed = 0;
  cbt->num_circ_timeouts = 0;
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
}

/**
 * Initialize the buildtimes structure for first use.
 *
 * Sets the initial timeout values based on either the config setting,
 * the consensus param, or the default (CBT_DEFAULT_TIMEOUT_INITIAL_VALUE).
 */
void
circuit_build_times_init(circuit_build_times_t *cbt)
{
  memset(cbt, 0, sizeof(*cbt));
  /*
   * Check if we really are using adaptive timeouts, and don't keep
   * track of this stuff if not.
   */
574
  if (!circuit_build_times_disabled(get_options())) {
575
576
577
    cbt->liveness.num_recent_circs =
      circuit_build_times_recent_circuit_count(NULL);
    cbt->liveness.timeouts_after_firsthop =
578
      tor_calloc(cbt->liveness.num_recent_circs, sizeof(int8_t));
579
580
581
582
583
  } else {
    cbt->liveness.num_recent_circs = 0;
    cbt->liveness.timeouts_after_firsthop = NULL;
  }
  cbt->close_ms = cbt->timeout_ms = circuit_build_times_get_initial_timeout();
584
  cbt_control_event_buildtimeout_set(cbt, BUILDTIMEOUT_SET_EVENT_RESET);
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
}

/**
 * Free the saved timeouts, if the cbtdisabled consensus parameter got turned
 * on or something.
 */

void
circuit_build_times_free_timeouts(circuit_build_times_t *cbt)
{
  if (!cbt) return;

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

  cbt->liveness.num_recent_circs = 0;
}

#if 0
/**
 * Rewind our build time history by n positions.
 */
static void
circuit_build_times_rewind_history(circuit_build_times_t *cbt, int n)
{
  int i = 0;

  cbt->build_times_idx -= n;
  cbt->build_times_idx %= CBT_NCIRCUITS_TO_OBSERVE;

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

  if (cbt->total_build_times > n) {
    cbt->total_build_times -= n;
  } else {
    cbt->total_build_times = 0;
  }

  log_info(LD_CIRC,
          "Rewound history by %d places. Current index: %d. "
          "Total: %d", n, cbt->build_times_idx, cbt->total_build_times);
}
631
#endif /* 0 */
632

633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
/**
 * Mark this circuit as timed out, but change its purpose
 * so that it continues to build, allowing us to measure
 * its full build time.
 */
void
circuit_build_times_mark_circ_as_measurement_only(origin_circuit_t *circ)
{
  control_event_circuit_status(circ,
                               CIRC_EVENT_FAILED,
                               END_CIRC_REASON_TIMEOUT);
  circuit_change_purpose(TO_CIRCUIT(circ),
                         CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT);
  /* Record this event to check for too many timeouts
   * in a row. This function does not record a time value yet
   * (we do that later); it only counts the fact that we did
   * have a timeout. We also want to avoid double-counting
   * already "relaxed" circuits, which are counted in
   * circuit_expire_building(). */
  if (!circ->relaxed_timeout) {
    int first_hop_succeeded = circ->cpath &&
          circ->cpath->state == CPATH_STATE_OPEN;

    circuit_build_times_count_timeout(
                                 get_circuit_build_times_mutable(),
                                 first_hop_succeeded);
  }
}

662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
/**
 * Perform the build time work that needs to be done when a circuit
 * completes a hop.
 *
 * This function decides if we should record a circuit's build time
 * in our histogram data and other statistics, and if so, records it.
 * It also will mark circuits that have already timed out as
 * measurement-only circuits, so they can continue to build but
 * not get used.
 *
 * For this, we want to consider circuits that will eventually make
 * it to the third hop. For circuits longer than 3 hops, we want to
 * record their build time when they reach the third hop, but let
 * them continue (and not count them later). For circuits that are
 * exactly 3 hops, this will count them when they are completed. We
 * do this so that CBT is always gathering statistics on circuits
 * of the same length, regardless of their type.
 */
void
circuit_build_times_handle_completed_hop(origin_circuit_t *circ)
{
  struct timeval end;
  long timediff;

  /* If circuit build times are disabled, let circuit_expire_building()
   * handle it.. */
  if (circuit_build_times_disabled(get_options())) {
    return;
  }

  /* Is this a circuit for which the timeout applies in a straight-forward
   * way? If so, handle it below. If not, just return (and let
   * circuit_expire_building() eventually take care of it).
   */
  if (!circuit_timeout_want_to_count_circ(circ)) {
    return;
  }

700
701
702
703
704
705
706
707
708
709
710
711
712
713
  tor_gettimeofday(&end);
  timediff = tv_mdiff(&circ->base_.timestamp_began, &end);

  /* Check if we would have timed out already. If so, change the
   * purpose here. But don't do any timeout handling here if there
   * are no circuits opened yet. Save it for circuit_expire_building()
   * (to allow it to handle timeout "relaxing" over there). */
  if (timediff > get_circuit_build_timeout_ms() &&
      circuit_any_opened_circuits_cached()) {

    /* Circuits are allowed to last longer for measurement.
     * Switch their purpose and wait. */
    if (circ->base_.purpose != CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT) {
      log_info(LD_CIRC,
714
715
               "Deciding to timeout circuit %"PRIu32"\n",
               (circ->global_identifier));
716
717
718
719
      circuit_build_times_mark_circ_as_measurement_only(circ);
    }
  }

720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
  /* If the circuit is built to exactly the DEFAULT_ROUTE_LEN,
   * add it to our buildtimes. */
  if (circuit_get_cpath_opened_len(circ) == DEFAULT_ROUTE_LEN) {
    /* If the circuit build time is much greater than we would have cut
     * it off at, we probably had a suspend event along this codepath,
     * and we should discard the value.
     */
    if (timediff < 0 ||
        timediff > 2*get_circuit_build_close_time_ms()+1000) {
      log_notice(LD_CIRC, "Strange value for circuit build time: %ldmsec. "
                 "Assuming clock jump. Purpose %d (%s)", timediff,
                 circ->base_.purpose,
                 circuit_purpose_to_string(circ->base_.purpose));
    } else {
      /* Only count circuit times if the network is live */
      if (circuit_build_times_network_check_live(
736
                            get_circuit_build_times())) {
737
738
739
740
741
742
743
744
745
746
747
748
749
        circuit_build_times_add_time(get_circuit_build_times_mutable(),
                                     (build_time_t)timediff);
        circuit_build_times_set_timeout(get_circuit_build_times_mutable());
      }

      if (circ->base_.purpose != CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT) {
        circuit_build_times_network_circ_success(
                                      get_circuit_build_times_mutable());
      }
    }
  }
}

750
751
752
753
754
755
756
757
/**
 * Add a new build time value <b>time</b> to the set of build times. Time
 * units are milliseconds.
 *
 * circuit_build_times <b>cbt</b> is a circular array, so loop around when
 * array is full.
 */
int
758
circuit_build_times_add_time(circuit_build_times_t *cbt, build_time_t btime)
759
{
760
  if (btime <= 0 || btime > CBT_BUILD_TIME_MAX) {
761
    log_warn(LD_BUG, "Circuit build time is too large (%u)."
762
                      "This is probably a bug.", btime);
763
764
765
766
    tor_fragile_assert();
    return -1;
  }

767
  log_debug(LD_CIRC, "Adding circuit build time %u", btime);
768

769
  cbt->circuit_build_times[cbt->build_times_idx] = btime;
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
  cbt->build_times_idx = (cbt->build_times_idx + 1) % CBT_NCIRCUITS_TO_OBSERVE;
  if (cbt->total_build_times < CBT_NCIRCUITS_TO_OBSERVE)
    cbt->total_build_times++;

  if ((cbt->total_build_times % CBT_SAVE_STATE_EVERY) == 0) {
    /* Save state every n circuit builds */
    if (!unit_tests && !get_options()->AvoidDiskWrites)
      or_state_mark_dirty(get_or_state(), 0);
  }

  return 0;
}

/**
 * Return maximum circuit build time
 */
static build_time_t
787
circuit_build_times_max(const circuit_build_times_t *cbt)
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
{
  int i = 0;
  build_time_t max_build_time = 0;
  for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
    if (cbt->circuit_build_times[i] > max_build_time
            && cbt->circuit_build_times[i] != CBT_BUILD_ABANDONED)
      max_build_time = cbt->circuit_build_times[i];
  }
  return max_build_time;
}

#if 0
/** Return minimum circuit build time */
build_time_t
circuit_build_times_min(circuit_build_times_t *cbt)
{
  int i = 0;
  build_time_t min_build_time = CBT_BUILD_TIME_MAX;
  for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
    if (cbt->circuit_build_times[i] && /* 0 <-> uninitialized */
        cbt->circuit_build_times[i] < min_build_time)
      min_build_time = cbt->circuit_build_times[i];
  }
  if (min_build_time == CBT_BUILD_TIME_MAX) {
    log_warn(LD_CIRC, "No build times less than CBT_BUILD_TIME_MAX!");
  }
  return min_build_time;
}
816
#endif /* 0 */
817
818
819
820
821
822
823
824
825
826
827

/**
 * Calculate and return a histogram for the set of build times.
 *
 * Returns an allocated array of histrogram bins representing
 * the frequency of index*CBT_BIN_WIDTH millisecond
 * build times. Also outputs the number of bins in nbins.
 *
 * The return value must be freed by the caller.
 */
static uint32_t *
828
circuit_build_times_create_histogram(const circuit_build_times_t *cbt,
829
830
831
832
833
834
835
                                     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 / CBT_BIN_WIDTH);
836
  histogram = tor_calloc(*nbins, sizeof(build_time_t));
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877

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

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

  return histogram;
}

/**
 * Return the Pareto start-of-curve parameter Xm.
 *
 * Because we are not a true Pareto curve, we compute this as the
 * 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).
 */
static build_time_t
circuit_build_times_get_xm(circuit_build_times_t *cbt)
{
  build_time_t i, nbins;
  build_time_t *nth_max_bin;
  int32_t bin_counts=0;
  build_time_t ret = 0;
  uint32_t *histogram = circuit_build_times_create_histogram(cbt, &nbins);
  int n=0;
  int num_modes = circuit_build_times_default_num_xm_modes();

  tor_assert(nbins > 0);
  tor_assert(num_modes > 0);

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

878
  nth_max_bin = tor_calloc(num_modes, sizeof(build_time_t));
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901

  /* Determine the N most common build times */
  for (i = 0; i < nbins; i++) {
    if (histogram[i] >= histogram[nth_max_bin[0]]) {
      nth_max_bin[0] = i;
    }

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

  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]]);
  }

902
903
904
905
906
907
908
909
910
911
912
913
  /* bin_counts can become zero if all of our last CBT_NCIRCUITS_TO_OBSERVE
   * circuits were abandoned before they completed. This shouldn't happen,
   * though. We should have reset/re-learned a lower timeout first. */
  if (bin_counts == 0) {
    ret = 0;
    log_warn(LD_CIRC,
               "No valid circuit build time data out of %d times, %u modes, "
               "have_timeout=%d, %lfms", cbt->total_build_times, num_modes,
               cbt->have_computed_timeout, cbt->timeout_ms);
    goto done;
  }

914
915
916
  tor_assert(bin_counts > 0);

  ret /= bin_counts;
917
918

 done:
919
920
921
922
923
924
925
926
927
928
929
  tor_free(histogram);
  tor_free(nth_max_bin);

  return ret;
}

/**
 * Output a histogram of current circuit build times to
 * the or_state_t state structure.
 */
void
930
circuit_build_times_update_state(const circuit_build_times_t *cbt,
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
                                 or_state_t *state)
{
  uint32_t *histogram;
  build_time_t i = 0;
  build_time_t nbins = 0;
  config_line_t **next, *line;

  histogram = circuit_build_times_create_histogram(cbt, &nbins);
  // write to state
  config_free_lines(state->BuildtimeHistogram);
  next = &state->BuildtimeHistogram;
  *next = NULL;

  state->TotalBuildTimes = cbt->total_build_times;
  state->CircuitBuildAbandonedCount = 0;

  for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
    if (cbt->circuit_build_times[i] == CBT_BUILD_ABANDONED)
      state->CircuitBuildAbandonedCount++;
  }

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

  if (!unit_tests) {
    if (!get_options()->AvoidDiskWrites)
      or_state_mark_dirty(get_or_state(), 0);
  }

  tor_free(histogram);
}

/**
 * Shuffle the build times array.
 *
 * Adapted from http://en.wikipedia.org/wiki/Fisher-Yates_shuffle
 */
static void
circuit_build_times_shuffle_and_store_array(circuit_build_times_t *cbt,
                                            build_time_t *raw_times,
                                            uint32_t num_times)
{
  uint32_t n = num_times;
  if (num_times > CBT_NCIRCUITS_TO_OBSERVE) {
    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 "
               "%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;
  }

  /* 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];
For faster browsing, not all history is shown. View entire blame