circuitlist.c 91.4 KB
Newer Older
Roger Dingledine's avatar
Roger Dingledine committed
1
/* Copyright 2001 Matej Pfajfar.
Roger Dingledine's avatar
Roger Dingledine committed
2
 * Copyright (c) 2001-2004, Roger Dingledine.
3
 * 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
7
8
/* See LICENSE for licensing information */

/**
 * \file circuitlist.c
9
 *
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
 * \brief Manage global structures that list and index circuits, and
 *   look up circuits within them.
 *
 * One of the most frequent operations in Tor occurs every time that
 * a relay cell arrives on a channel.  When that happens, we need to
 * find which circuit it is associated with, based on the channel and the
 * circuit ID in the relay cell.
 *
 * To handle that, we maintain a global list of circuits, and a hashtable
 * mapping [channel,circID] pairs to circuits.  Circuits are added to and
 * removed from this mapping using circuit_set_p_circid_chan() and
 * circuit_set_n_circid_chan().  To look up a circuit from this map, most
 * callers should use circuit_get_by_circid_channel(), though
 * circuit_get_by_circid_channel_even_if_marked() is appropriate under some
 * circumstances.
 *
 * We also need to allow for the possibility that we have blocked use of a
 * circuit ID (because we are waiting to send a DESTROY cell), but the
 * circuit is not there any more.  For that case, we allow placeholder
 * entries in the table, using channel_mark_circid_unusable().
 *
 * To efficiently handle a channel that has just opened, we also maintain a
 * list of the circuits waiting for channels, so we can attach them as
 * needed without iterating through the whole list of circuits, using
 * circuit_get_all_pending_on_channel().
 *
 * In this module, we also handle the list of circuits that have been
 * marked for close elsewhere, and close them as needed.  (We use this
 * "mark now, close later" pattern here and elsewhere to avoid
 * unpredictable recursion if we closed every circuit immediately upon
 * realizing it needed to close.)  See circuit_mark_for_close() for the
 * mark function, and circuit_close_all_marked() for the close function.
 *
 * For hidden services, we need to be able to look up introduction point
 * circuits and rendezvous circuits by cookie, key, etc.  These are
 * currently handled with linear searches in
 * circuit_get_ready_rend_circuit_by_rend_data(),
 * circuit_get_next_by_pk_and_purpose(), and with hash lookups in
 * circuit_get_rendezvous() and circuit_get_intro_point().
 *
 * This module is also the entry point for our out-of-memory handler
 * logic, which was originally circuit-focused.
52
 **/
53
#define CIRCUITLIST_PRIVATE
54
#include "lib/cc/torint.h"  /* TOR_PRIuSZ */
55

56
57
#include "core/or/or.h"
#include "core/or/channel.h"
58
#include "core/or/channeltls.h"
59
60
61
62
63
64
65
66
67
68
#include "feature/client/circpathbias.h"
#include "core/or/circuitbuild.h"
#include "core/or/circuitlist.h"
#include "core/or/circuituse.h"
#include "core/or/circuitstats.h"
#include "core/mainloop/connection.h"
#include "app/config/config.h"
#include "core/or/connection_edge.h"
#include "core/or/connection_or.h"
#include "feature/control/control.h"
69
70
#include "lib/crypt_ops/crypto_rand.h"
#include "lib/crypt_ops/crypto_util.h"
71
#include "lib/crypt_ops/crypto_dh.h"
72
73
#include "feature/dircache/directory.h"
#include "feature/client/entrynodes.h"
74
#include "core/mainloop/mainloop.h"
75
76
77
78
79
#include "feature/hs/hs_circuit.h"
#include "feature/hs/hs_circuitmap.h"
#include "feature/hs/hs_ident.h"
#include "feature/nodelist/networkstatus.h"
#include "feature/nodelist/nodelist.h"
80
81
#include "feature/relay/onion_queue.h"
#include "core/crypto/onion_crypto.h"
82
83
84
85
86
87
88
89
90
91
#include "core/crypto/onion_fast.h"
#include "core/or/policies.h"
#include "core/or/relay.h"
#include "core/crypto/relay_crypto.h"
#include "feature/rend/rendclient.h"
#include "feature/rend/rendcommon.h"
#include "feature/stats/rephist.h"
#include "feature/nodelist/routerlist.h"
#include "feature/nodelist/routerset.h"
#include "core/or/channelpadding.h"
92
#include "lib/compress/compress.h"
93
94
95
#include "lib/compress/compress_lzma.h"
#include "lib/compress/compress_zlib.h"
#include "lib/compress/compress_zstd.h"
96
#include "lib/container/buffers.h"
97

98
#include "ht.h"
99

100
101
102
103
#include "core/or/cpath_build_state_st.h"
#include "core/or/crypt_path_reference_st.h"
#include "feature/dircommon/dir_connection_st.h"
#include "core/or/edge_connection_st.h"
104
#include "core/or/half_edge_st.h"
105
106
107
#include "core/or/extend_info_st.h"
#include "core/or/or_circuit_st.h"
#include "core/or/origin_circuit_st.h"
108

109
110
/********* START VARIABLES **********/

111
/** A global list of all circuits at this hop. */
112
static smartlist_t *global_circuitlist = NULL;
113

114
115
116
117
/** A global list of all origin circuits. Every element of this is also
 * an element of global_circuitlist. */
static smartlist_t *global_origin_circuit_list = NULL;

118
119
/** A list of all the circuits in CIRCUIT_STATE_CHAN_WAIT. */
static smartlist_t *circuits_pending_chans = NULL;
120

121
122
123
124
/** List of all the (origin) circuits whose state is
 * CIRCUIT_STATE_GUARD_WAIT. */
static smartlist_t *circuits_pending_other_guards = NULL;

Nick Mathewson's avatar
Nick Mathewson committed
125
126
/** A list of all the circuits that have been marked with
 * circuit_mark_for_close and which are waiting for circuit_about_to_free. */
127
128
static smartlist_t *circuits_pending_close = NULL;

129
static void circuit_free_cpath_node(crypt_path_t *victim);
130
static void cpath_ref_decref(crypt_path_reference_t *cpath_ref);
131
static void circuit_about_to_free_atexit(circuit_t *circ);
132
static void circuit_about_to_free(circuit_t *circ);
133

134
135
136
137
138
139
140
141
/**
 * A cached value of the current state of the origin circuit list.  Has the
 * value 1 if we saw any opened circuits recently (since the last call to
 * circuit_any_opened_circuits(), which gets called around once a second by
 * circuit_expire_building). 0 otherwise.
 */
static int any_opened_circs_cached_val = 0;

142
143
/********* END VARIABLES ************/

144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
or_circuit_t *
TO_OR_CIRCUIT(circuit_t *x)
{
  tor_assert(x->magic == OR_CIRCUIT_MAGIC);
  return DOWNCAST(or_circuit_t, x);
}
const or_circuit_t *
CONST_TO_OR_CIRCUIT(const circuit_t *x)
{
  tor_assert(x->magic == OR_CIRCUIT_MAGIC);
  return DOWNCAST(or_circuit_t, x);
}
origin_circuit_t *
TO_ORIGIN_CIRCUIT(circuit_t *x)
{
  tor_assert(x->magic == ORIGIN_CIRCUIT_MAGIC);
  return DOWNCAST(origin_circuit_t, x);
}
const origin_circuit_t *
CONST_TO_ORIGIN_CIRCUIT(const circuit_t *x)
{
  tor_assert(x->magic == ORIGIN_CIRCUIT_MAGIC);
  return DOWNCAST(origin_circuit_t, x);
}

169
/** A map from channel and circuit ID to circuit.  (Lookup performance is
170
 * very important here, since we need to do it every time a cell arrives.) */
171
172
173
typedef struct chan_circid_circuit_map_t {
  HT_ENTRY(chan_circid_circuit_map_t) node;
  channel_t *chan;
174
  circid_t circ_id;
175
  circuit_t *circuit;
Nick Mathewson's avatar
Nick Mathewson committed
176
177
  /* For debugging 12184: when was this placeholder item added? */
  time_t made_placeholder_at;
178
} chan_circid_circuit_map_t;
179

180
/** Helper for hash tables: compare the channel and circuit ID for a and
181
 * b, and return less than, equal to, or greater than zero appropriately.
182
 */
183
static inline int
184
chan_circid_entries_eq_(chan_circid_circuit_map_t *a,
185
                        chan_circid_circuit_map_t *b)
186
{
187
  return a->chan == b->chan && a->circ_id == b->circ_id;
188
189
}

190
/** Helper: return a hash based on circuit ID and the pointer value of
191
 * chan in <b>a</b>. */
192
static inline unsigned int
193
chan_circid_entry_hash_(chan_circid_circuit_map_t *a)
194
{
195
196
197
198
199
200
201
202
203
  /* Try to squeze the siphash input into 8 bytes to save any extra siphash
   * rounds.  This hash function is in the critical path. */
  uintptr_t chan = (uintptr_t) (void*) a->chan;
  uint32_t array[2];
  array[0] = a->circ_id;
  /* The low bits of the channel pointer are uninteresting, since the channel
   * is a pretty big structure. */
  array[1] = (uint32_t) (chan >> 6);
  return (unsigned) siphash24g(array, sizeof(array));
204
205
}

206
207
208
209
/** Map from [chan,circid] to circuit. */
static HT_HEAD(chan_circid_map, chan_circid_circuit_map_t)
     chan_circid_map = HT_INITIALIZER();
HT_PROTOTYPE(chan_circid_map, chan_circid_circuit_map_t, node,
210
             chan_circid_entry_hash_, chan_circid_entries_eq_)
211
212
213
HT_GENERATE2(chan_circid_map, chan_circid_circuit_map_t, node,
             chan_circid_entry_hash_, chan_circid_entries_eq_, 0.6,
             tor_reallocarray_, tor_free_)
214

215
/** The most recently returned entry from circuit_get_by_circid_chan;
216
217
 * used to improve performance when many cells arrive in a row from the
 * same circuit.
218
 */
219
static chan_circid_circuit_map_t *_last_circid_chan_ent = NULL;
220

221
222
223
/** Implementation helper for circuit_set_{p,n}_circid_channel: A circuit ID
 * and/or channel for circ has just changed from <b>old_chan, old_id</b>
 * to <b>chan, id</b>.  Adjust the chan,circid map as appropriate, removing
224
 * the old entry (if any) and adding a new one. */
225
static void
226
227
228
circuit_set_circid_chan_helper(circuit_t *circ, int direction,
                               circid_t id,
                               channel_t *chan)
229
{
230
231
232
  chan_circid_circuit_map_t search;
  chan_circid_circuit_map_t *found;
  channel_t *old_chan, **chan_ptr;
233
  circid_t old_id, *circid_ptr;
234
  int make_active, attached = 0;
235
236

  if (direction == CELL_DIRECTION_OUT) {
237
    chan_ptr = &circ->n_chan;
238
    circid_ptr = &circ->n_circ_id;
239
    make_active = circ->n_chan_cells.n > 0;
240
241
  } else {
    or_circuit_t *c = TO_OR_CIRCUIT(circ);
242
    chan_ptr = &c->p_chan;
243
    circid_ptr = &c->p_circ_id;
244
    make_active = c->p_chan_cells.n > 0;
245
  }
246
  old_chan = *chan_ptr;
247
248
  old_id = *circid_ptr;

249
  if (id == old_id && chan == old_chan)
250
    return;
251

252
253
254
255
256
257
  if (_last_circid_chan_ent &&
      ((old_id == _last_circid_chan_ent->circ_id &&
        old_chan == _last_circid_chan_ent->chan) ||
       (id == _last_circid_chan_ent->circ_id &&
        chan == _last_circid_chan_ent->chan))) {
    _last_circid_chan_ent = NULL;
258
259
  }

260
261
262
  if (old_chan) {
    /*
     * If we're changing channels or ID and had an old channel and a non
263
264
265
     * zero old ID and weren't marked for close (i.e., we should have been
     * attached), detach the circuit. ID changes require this because
     * circuitmux hashes on (channel_id, circuit_id).
266
     */
267
    if (old_id != 0 && (old_chan != chan || old_id != id) &&
268
        !(circ->marked_for_close)) {
269
270
271
272
273
      tor_assert(old_chan->cmux);
      circuitmux_detach_circuit(old_chan->cmux, circ);
    }

    /* we may need to remove it from the conn-circid map */
274
    search.circ_id = old_id;
275
276
    search.chan = old_chan;
    found = HT_REMOVE(chan_circid_map, &chan_circid_map, &search);
277
    if (found) {
278
      tor_free(found);
279
280
281
282
283
284
285
286
      if (direction == CELL_DIRECTION_OUT) {
        /* One fewer circuits use old_chan as n_chan */
        --(old_chan->num_n_circuits);
      } else {
        /* One fewer circuits use old_chan as p_chan */
        --(old_chan->num_p_circuits);
      }
    }
287
288
  }

289
  /* Change the values only after we have possibly made the circuit inactive
290
291
   * on the previous chan. */
  *chan_ptr = chan;
292
293
  *circid_ptr = id;

294
  if (chan == NULL)
295
296
    return;

297
  /* now add the new one to the conn-circid map */
298
  search.circ_id = id;
299
300
  search.chan = chan;
  found = HT_FIND(chan_circid_map, &chan_circid_map, &search);
301
302
  if (found) {
    found->circuit = circ;
Nick Mathewson's avatar
Nick Mathewson committed
303
    found->made_placeholder_at = 0;
304
  } else {
305
    found = tor_malloc_zero(sizeof(chan_circid_circuit_map_t));
306
    found->circ_id = id;
307
    found->chan = chan;
308
    found->circuit = circ;
309
    HT_INSERT(chan_circid_map, &chan_circid_map, found);
310
  }
311

312
313
  /*
   * Attach to the circuitmux if we're changing channels or IDs and
314
315
   * have a new channel and ID to use and the circuit is not marked for
   * close.
316
   */
317
318
  if (chan && id != 0 && (old_chan != chan || old_id != id) &&
      !(circ->marked_for_close)) {
319
320
    tor_assert(chan->cmux);
    circuitmux_attach_circuit(chan->cmux, circ, direction);
321
    attached = 1;
322
323
324
325
326
327
  }

  /*
   * This is a no-op if we have no cells, but if we do it marks us active to
   * the circuitmux
   */
328
  if (make_active && attached)
329
    update_circuit_on_cmux(circ, direction);
330

331
332
333
334
335
336
  /* Adjust circuit counts on new channel */
  if (direction == CELL_DIRECTION_OUT) {
    ++chan->num_n_circuits;
  } else {
    ++chan->num_p_circuits;
  }
337
338
}

339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
/** Mark that circuit id <b>id</b> shouldn't be used on channel <b>chan</b>,
 * even if there is no circuit on the channel. We use this to keep the
 * circuit id from getting re-used while we have queued but not yet sent
 * a destroy cell. */
void
channel_mark_circid_unusable(channel_t *chan, circid_t id)
{
  chan_circid_circuit_map_t search;
  chan_circid_circuit_map_t *ent;

  /* See if there's an entry there. That wouldn't be good. */
  memset(&search, 0, sizeof(search));
  search.chan = chan;
  search.circ_id = id;
  ent = HT_FIND(chan_circid_map, &chan_circid_map, &search);

  if (ent && ent->circuit) {
    /* we have a problem. */
    log_warn(LD_BUG, "Tried to mark %u unusable on %p, but there was already "
             "a circuit there.", (unsigned)id, chan);
  } else if (ent) {
    /* It's already marked. */
Nick Mathewson's avatar
Nick Mathewson committed
361
362
    if (!ent->made_placeholder_at)
      ent->made_placeholder_at = approx_time();
363
364
365
366
  } else {
    ent = tor_malloc_zero(sizeof(chan_circid_circuit_map_t));
    ent->chan = chan;
    ent->circ_id = id;
Nick Mathewson's avatar
Nick Mathewson committed
367
368
    /* leave circuit at NULL. */
    ent->made_placeholder_at = approx_time();
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
396
    HT_INSERT(chan_circid_map, &chan_circid_map, ent);
  }
}

/** Mark that a circuit id <b>id</b> can be used again on <b>chan</b>.
 * We use this to re-enable the circuit ID after we've sent a destroy cell.
 */
void
channel_mark_circid_usable(channel_t *chan, circid_t id)
{
  chan_circid_circuit_map_t search;
  chan_circid_circuit_map_t *ent;

  /* See if there's an entry there. That wouldn't be good. */
  memset(&search, 0, sizeof(search));
  search.chan = chan;
  search.circ_id = id;
  ent = HT_REMOVE(chan_circid_map, &chan_circid_map, &search);
  if (ent && ent->circuit) {
    log_warn(LD_BUG, "Tried to mark %u usable on %p, but there was already "
             "a circuit there.", (unsigned)id, chan);
    return;
  }
  if (_last_circid_chan_ent == ent)
    _last_circid_chan_ent = NULL;
  tor_free(ent);
}

397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
/** Called to indicate that a DESTROY is pending on <b>chan</b> with
 * circuit ID <b>id</b>, but hasn't been sent yet. */
void
channel_note_destroy_pending(channel_t *chan, circid_t id)
{
  circuit_t *circ = circuit_get_by_circid_channel_even_if_marked(id,chan);
  if (circ) {
    if (circ->n_chan == chan && circ->n_circ_id == id) {
      circ->n_delete_pending = 1;
    } else {
      or_circuit_t *orcirc = TO_OR_CIRCUIT(circ);
      if (orcirc->p_chan == chan && orcirc->p_circ_id == id) {
        circ->p_delete_pending = 1;
      }
    }
    return;
  }
  channel_mark_circid_unusable(chan, id);
}

/** Called to indicate that a DESTROY is no longer pending on <b>chan</b> with
 * circuit ID <b>id</b> -- typically, because it has been sent. */
419
420
MOCK_IMPL(void,
channel_note_destroy_not_pending,(channel_t *chan, circid_t id))
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
{
  circuit_t *circ = circuit_get_by_circid_channel_even_if_marked(id,chan);
  if (circ) {
    if (circ->n_chan == chan && circ->n_circ_id == id) {
      circ->n_delete_pending = 0;
    } else {
      or_circuit_t *orcirc = TO_OR_CIRCUIT(circ);
      if (orcirc->p_chan == chan && orcirc->p_circ_id == id) {
        circ->p_delete_pending = 0;
      }
    }
    /* XXXX this shouldn't happen; log a bug here. */
    return;
  }
  channel_mark_circid_usable(chan, id);
}

438
439
/** Set the p_conn field of a circuit <b>circ</b>, along
 * with the corresponding circuit ID, and add the circuit as appropriate
440
 * to the (chan,id)-\>circuit map. */
441
void
442
circuit_set_p_circid_chan(or_circuit_t *or_circ, circid_t id,
443
                          channel_t *chan)
444
{
445
446
447
448
449
  circuit_t *circ = TO_CIRCUIT(or_circ);
  channel_t *old_chan = or_circ->p_chan;
  circid_t old_id = or_circ->p_circ_id;

  circuit_set_circid_chan_helper(circ, CELL_DIRECTION_IN, id, chan);
450

451
452
453
  if (chan) {
    chan->timestamp_last_had_circuits = approx_time();
  }
454

455
456
457
458
  if (circ->p_delete_pending && old_chan) {
    channel_mark_circid_unusable(old_chan, old_id);
    circ->p_delete_pending = 0;
  }
459
460
461
462
}

/** Set the n_conn field of a circuit <b>circ</b>, along
 * with the corresponding circuit ID, and add the circuit as appropriate
463
 * to the (chan,id)-\>circuit map. */
464
void
465
466
circuit_set_n_circid_chan(circuit_t *circ, circid_t id,
                          channel_t *chan)
467
{
468
469
470
  channel_t *old_chan = circ->n_chan;
  circid_t old_id = circ->n_circ_id;

471
  circuit_set_circid_chan_helper(circ, CELL_DIRECTION_OUT, id, chan);
472

473
474
475
  if (chan) {
    chan->timestamp_last_had_circuits = approx_time();
  }
476

477
478
  if (circ->n_delete_pending && old_chan) {
    channel_mark_circid_unusable(old_chan, old_id);
479
    circ->n_delete_pending = 0;
480
  }
481
482
}

483
484
/** Change the state of <b>circ</b> to <b>state</b>, adding it to or removing
 * it from lists as appropriate. */
485
void
486
circuit_set_state(circuit_t *circ, uint8_t state)
487
488
489
490
{
  tor_assert(circ);
  if (state == circ->state)
    return;
491
  if (PREDICT_UNLIKELY(!circuits_pending_chans))
492
    circuits_pending_chans = smartlist_new();
493
494
  if (PREDICT_UNLIKELY(!circuits_pending_other_guards))
    circuits_pending_other_guards = smartlist_new();
495
  if (circ->state == CIRCUIT_STATE_CHAN_WAIT) {
496
    /* remove from waiting-circuit list. */
497
    smartlist_remove(circuits_pending_chans, circ);
498
  }
499
  if (state == CIRCUIT_STATE_CHAN_WAIT) {
500
    /* add to waiting-circuit list. */
501
    smartlist_add(circuits_pending_chans, circ);
502
  }
503
504
505
506
507
508
509
  if (circ->state == CIRCUIT_STATE_GUARD_WAIT) {
    smartlist_remove(circuits_pending_other_guards, circ);
  }
  if (state == CIRCUIT_STATE_GUARD_WAIT) {
    smartlist_add(circuits_pending_other_guards, circ);
  }
  if (state == CIRCUIT_STATE_GUARD_WAIT || state == CIRCUIT_STATE_OPEN)
510
    tor_assert(!circ->n_chan_create_cell);
511
  circ->state = state;
512
513
}

514
/** Append to <b>out</b> all circuits in state CHAN_WAIT waiting for
515
516
 * the given connection. */
void
517
circuit_get_all_pending_on_channel(smartlist_t *out, channel_t *chan)
518
519
{
  tor_assert(out);
520
  tor_assert(chan);
521

522
  if (!circuits_pending_chans)
523
524
    return;

525
  SMARTLIST_FOREACH_BEGIN(circuits_pending_chans, circuit_t *, circ) {
526
527
    if (circ->marked_for_close)
      continue;
528
529
    if (!circ->n_hop)
      continue;
530
    tor_assert(circ->state == CIRCUIT_STATE_CHAN_WAIT);
531
    if (tor_digest_is_zero(circ->n_hop->identity_digest)) {
532
      /* Look at addr/port. This is an unkeyed connection. */
533
      if (!channel_matches_extend_info(chan, circ->n_hop))
534
535
536
        continue;
    } else {
      /* We expected a key. See if it's the right one. */
537
538
      if (tor_memneq(chan->identity_digest,
                     circ->n_hop->identity_digest, DIGEST_LEN))
539
        continue;
540
    }
541
    smartlist_add(out, circ);
542
  } SMARTLIST_FOREACH_END(circ);
543
544
}

545
546
/** Return the number of circuits in state CHAN_WAIT, waiting for the given
 * channel. */
547
int
548
circuit_count_pending_on_channel(channel_t *chan)
549
550
{
  int cnt;
551
  smartlist_t *sl = smartlist_new();
552
553
554
555

  tor_assert(chan);

  circuit_get_all_pending_on_channel(sl, chan);
556
557
  cnt = smartlist_len(sl);
  smartlist_free(sl);
558
  log_debug(LD_CIRC,"or_conn to %s, %d pending circs",
559
            channel_get_canonical_remote_descr(chan),
560
            cnt);
561
562
563
  return cnt;
}

564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
/** Remove <b>origin_circ</b> from the global list of origin circuits.
 * Called when we are freeing a circuit.
 */
static void
circuit_remove_from_origin_circuit_list(origin_circuit_t *origin_circ)
{
  int origin_idx = origin_circ->global_origin_circuit_list_idx;
  if (origin_idx < 0)
    return;
  origin_circuit_t *c2;
  tor_assert(origin_idx <= smartlist_len(global_origin_circuit_list));
  c2 = smartlist_get(global_origin_circuit_list, origin_idx);
  tor_assert(origin_circ == c2);
  smartlist_del(global_origin_circuit_list, origin_idx);
  if (origin_idx < smartlist_len(global_origin_circuit_list)) {
    origin_circuit_t *replacement =
      smartlist_get(global_origin_circuit_list, origin_idx);
    replacement->global_origin_circuit_list_idx = origin_idx;
  }
  origin_circ->global_origin_circuit_list_idx = -1;
}

/** Add <b>origin_circ</b> to the global list of origin circuits. Called
 * when creating the circuit. */
static void
circuit_add_to_origin_circuit_list(origin_circuit_t *origin_circ)
{
  tor_assert(origin_circ->global_origin_circuit_list_idx == -1);
  smartlist_t *lst = circuit_get_global_origin_circuit_list();
  smartlist_add(lst, origin_circ);
  origin_circ->global_origin_circuit_list_idx = smartlist_len(lst) - 1;
}

597
598
599
/** Detach from the global circuit list, and deallocate, all
 * circuits that have been marked for close.
 */
600
601
void
circuit_close_all_marked(void)
602
{
603
604
605
  if (circuits_pending_close == NULL)
    return;

606
  smartlist_t *lst = circuit_get_global_list();
607
608
609
610
611
612
613
614
615
  SMARTLIST_FOREACH_BEGIN(circuits_pending_close, circuit_t *, circ) {
    tor_assert(circ->marked_for_close);

    /* Remove it from the circuit list. */
    int idx = circ->global_circuitlist_idx;
    smartlist_del(lst, idx);
    if (idx < smartlist_len(lst)) {
      circuit_t *replacement = smartlist_get(lst, idx);
      replacement->global_circuitlist_idx = idx;
616
    }
617
618
    circ->global_circuitlist_idx = -1;

619
620
    /* Remove it from the origin circuit list, if appropriate. */
    if (CIRCUIT_IS_ORIGIN(circ)) {
621
      circuit_remove_from_origin_circuit_list(TO_ORIGIN_CIRCUIT(circ));
622
623
    }

624
625
    circuit_about_to_free(circ);
    circuit_free(circ);
626
  } SMARTLIST_FOREACH_END(circ);
627
628

  smartlist_clear(circuits_pending_close);
629
630
}

631
/** Return a pointer to the global list of circuits. */
632
MOCK_IMPL(smartlist_t *,
633
circuit_get_global_list,(void))
634
{
635
636
637
  if (NULL == global_circuitlist)
    global_circuitlist = smartlist_new();
  return global_circuitlist;
638
639
}

640
641
642
643
644
645
/** Return a pointer to the global list of origin circuits. */
smartlist_t *
circuit_get_global_origin_circuit_list(void)
{
  if (NULL == global_origin_circuit_list)
    global_origin_circuit_list = smartlist_new();
646
  return global_origin_circuit_list;
647
648
}

649
650
651
652
653
654
655
656
657
658
659
660
661
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
/**
 * Return true if we have any opened general-purpose 3 hop
 * origin circuits.
 *
 * The result from this function is cached for use by
 * circuit_any_opened_circuits_cached().
 */
int
circuit_any_opened_circuits(void)
{
  SMARTLIST_FOREACH_BEGIN(circuit_get_global_origin_circuit_list(),
          const origin_circuit_t *, next_circ) {
    if (!TO_CIRCUIT(next_circ)->marked_for_close &&
        next_circ->has_opened &&
        TO_CIRCUIT(next_circ)->state == CIRCUIT_STATE_OPEN &&
        TO_CIRCUIT(next_circ)->purpose != CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT &&
        next_circ->build_state &&
        next_circ->build_state->desired_path_len == DEFAULT_ROUTE_LEN) {
      circuit_cache_opened_circuit_state(1);
      return 1;
    }
  } SMARTLIST_FOREACH_END(next_circ);

  circuit_cache_opened_circuit_state(0);
  return 0;
}

/**
 * Cache the "any circuits opened" state, as specified in param
 * circuits_are_opened. This is a helper function to update
 * the circuit opened status whenever we happen to look at the
 * circuit list.
 */
void
circuit_cache_opened_circuit_state(int circuits_are_opened)
{
  any_opened_circs_cached_val = circuits_are_opened;
}

/**
 * Return true if there were any opened circuits since the last call to
 * circuit_any_opened_circuits(), or since circuit_expire_building() last
 * ran (it runs roughly once per second).
 */
int
circuit_any_opened_circuits_cached(void)
{
  return any_opened_circs_cached_val;
}

699
700
/** Function to make circ-\>state human-readable */
const char *
701
702
circuit_state_to_string(int state)
{
Nick Mathewson's avatar
Nick Mathewson committed
703
  static char buf[64];
704
705
706
  switch (state) {
    case CIRCUIT_STATE_BUILDING: return "doing handshakes";
    case CIRCUIT_STATE_ONIONSKIN_PENDING: return "processing the onion";
707
    case CIRCUIT_STATE_CHAN_WAIT: return "connecting to server";
708
709
    case CIRCUIT_STATE_GUARD_WAIT: return "waiting to see how other "
      "guards perform";
710
711
    case CIRCUIT_STATE_OPEN: return "open";
    default:
712
      log_warn(LD_BUG, "Unknown circuit state %d", state);
713
      tor_snprintf(buf, sizeof(buf), "unknown state [%d]", state);
714
715
716
717
      return buf;
  }
}

718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
/** Map a circuit purpose to a string suitable to be displayed to a
 * controller. */
const char *
circuit_purpose_to_controller_string(uint8_t purpose)
{
  static char buf[32];
  switch (purpose) {
    case CIRCUIT_PURPOSE_OR:
    case CIRCUIT_PURPOSE_INTRO_POINT:
    case CIRCUIT_PURPOSE_REND_POINT_WAITING:
    case CIRCUIT_PURPOSE_REND_ESTABLISHED:
      return "SERVER"; /* A controller should never see these, actually. */

    case CIRCUIT_PURPOSE_C_GENERAL:
      return "GENERAL";
733
734
735
736

    case CIRCUIT_PURPOSE_C_HSDIR_GET:
      return "HS_CLIENT_HSDIR";

737
    case CIRCUIT_PURPOSE_C_INTRODUCING:
738
739
740
741
742
743
744
745
746
747
    case CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT:
    case CIRCUIT_PURPOSE_C_INTRODUCE_ACKED:
      return "HS_CLIENT_INTRO";

    case CIRCUIT_PURPOSE_C_ESTABLISH_REND:
    case CIRCUIT_PURPOSE_C_REND_READY:
    case CIRCUIT_PURPOSE_C_REND_READY_INTRO_ACKED:
    case CIRCUIT_PURPOSE_C_REND_JOINED:
      return "HS_CLIENT_REND";

748
749
750
    case CIRCUIT_PURPOSE_S_HSDIR_POST:
      return "HS_SERVICE_HSDIR";

751
752
753
754
755
756
757
758
759
760
    case CIRCUIT_PURPOSE_S_ESTABLISH_INTRO:
    case CIRCUIT_PURPOSE_S_INTRO:
      return "HS_SERVICE_INTRO";

    case CIRCUIT_PURPOSE_S_CONNECT_REND:
    case CIRCUIT_PURPOSE_S_REND_JOINED:
      return "HS_SERVICE_REND";

    case CIRCUIT_PURPOSE_TESTING:
      return "TESTING";
761
    case CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT:
762
      return "MEASURE_TIMEOUT";
763
764
    case CIRCUIT_PURPOSE_CONTROLLER:
      return "CONTROLLER";
765
766
    case CIRCUIT_PURPOSE_PATH_BIAS_TESTING:
      return "PATH_BIAS_TESTING";
767
768
    case CIRCUIT_PURPOSE_HS_VANGUARDS:
      return "HS_VANGUARDS";
769
770
771
772
773
774
775

    default:
      tor_snprintf(buf, sizeof(buf), "UNKNOWN_%d", (int)purpose);
      return buf;
  }
}

776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
/** Return a string specifying the state of the hidden-service circuit
 * purpose <b>purpose</b>, or NULL if <b>purpose</b> is not a
 * hidden-service-related circuit purpose. */
const char *
circuit_purpose_to_controller_hs_state_string(uint8_t purpose)
{
  switch (purpose)
    {
    default:
      log_fn(LOG_WARN, LD_BUG,
             "Unrecognized circuit purpose: %d",
             (int)purpose);
      tor_fragile_assert();
      /* fall through */

    case CIRCUIT_PURPOSE_OR:
    case CIRCUIT_PURPOSE_C_GENERAL:
    case CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT:
    case CIRCUIT_PURPOSE_TESTING:
    case CIRCUIT_PURPOSE_CONTROLLER:
796
    case CIRCUIT_PURPOSE_PATH_BIAS_TESTING:
797
    case CIRCUIT_PURPOSE_HS_VANGUARDS:
798
799
800
801
802
803
804
805
806
      return NULL;

    case CIRCUIT_PURPOSE_INTRO_POINT:
      return "OR_HSSI_ESTABLISHED";
    case CIRCUIT_PURPOSE_REND_POINT_WAITING:
      return "OR_HSCR_ESTABLISHED";
    case CIRCUIT_PURPOSE_REND_ESTABLISHED:
      return "OR_HS_R_JOINED";

807
    case CIRCUIT_PURPOSE_C_HSDIR_GET:
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
    case CIRCUIT_PURPOSE_C_INTRODUCING:
      return "HSCI_CONNECTING";
    case CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT:
      return "HSCI_INTRO_SENT";
    case CIRCUIT_PURPOSE_C_INTRODUCE_ACKED:
      return "HSCI_DONE";

    case CIRCUIT_PURPOSE_C_ESTABLISH_REND:
      return "HSCR_CONNECTING";
    case CIRCUIT_PURPOSE_C_REND_READY:
      return "HSCR_ESTABLISHED_IDLE";
    case CIRCUIT_PURPOSE_C_REND_READY_INTRO_ACKED:
      return "HSCR_ESTABLISHED_WAITING";
    case CIRCUIT_PURPOSE_C_REND_JOINED:
      return "HSCR_JOINED";

824
    case CIRCUIT_PURPOSE_S_HSDIR_POST:
825
826
827
828
829
830
831
832
833
834
835
836
    case CIRCUIT_PURPOSE_S_ESTABLISH_INTRO:
      return "HSSI_CONNECTING";
    case CIRCUIT_PURPOSE_S_INTRO:
      return "HSSI_ESTABLISHED";

    case CIRCUIT_PURPOSE_S_CONNECT_REND:
      return "HSSR_CONNECTING";
    case CIRCUIT_PURPOSE_S_REND_JOINED:
      return "HSSR_JOINED";
    }
}

837
838
839
840
841
842
843
844
845
846
847
848
849
/** Return a human-readable string for the circuit purpose <b>purpose</b>. */
const char *
circuit_purpose_to_string(uint8_t purpose)
{
  static char buf[32];

  switch (purpose)
    {
    case CIRCUIT_PURPOSE_OR:
      return "Circuit at relay";
    case CIRCUIT_PURPOSE_INTRO_POINT:
      return "Acting as intro point";
    case CIRCUIT_PURPOSE_REND_POINT_WAITING:
850
      return "Acting as rendezvous (pending)";
851
    case CIRCUIT_PURPOSE_REND_ESTABLISHED:
852
      return "Acting as rendezvous (established)";
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
    case CIRCUIT_PURPOSE_C_GENERAL:
      return "General-purpose client";
    case CIRCUIT_PURPOSE_C_INTRODUCING:
      return "Hidden service client: Connecting to intro point";
    case CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT:
      return "Hidden service client: Waiting for ack from intro point";
    case CIRCUIT_PURPOSE_C_INTRODUCE_ACKED:
      return "Hidden service client: Received ack from intro point";
    case CIRCUIT_PURPOSE_C_ESTABLISH_REND:
      return "Hidden service client: Establishing rendezvous point";
    case CIRCUIT_PURPOSE_C_REND_READY:
      return "Hidden service client: Pending rendezvous point";
    case CIRCUIT_PURPOSE_C_REND_READY_INTRO_ACKED:
      return "Hidden service client: Pending rendezvous point (ack received)";
    case CIRCUIT_PURPOSE_C_REND_JOINED:
      return "Hidden service client: Active rendezvous point";
869
870
871
    case CIRCUIT_PURPOSE_C_HSDIR_GET:
      return "Hidden service client: Fetching HS descriptor";

872
873
874
875
876
877
878
879
880
881
882
    case CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT:
      return "Measuring circuit timeout";

    case CIRCUIT_PURPOSE_S_ESTABLISH_INTRO:
      return "Hidden service: Establishing introduction point";
    case CIRCUIT_PURPOSE_S_INTRO:
      return "Hidden service: Introduction point";
    case CIRCUIT_PURPOSE_S_CONNECT_REND:
      return "Hidden service: Connecting to rendezvous point";
    case CIRCUIT_PURPOSE_S_REND_JOINED:
      return "Hidden service: Active rendezvous point";
883
884
    case CIRCUIT_PURPOSE_S_HSDIR_POST:
      return "Hidden service: Uploading HS descriptor";
885
886
887
888
889
890
891

    case CIRCUIT_PURPOSE_TESTING:
      return "Testing circuit";

    case CIRCUIT_PURPOSE_CONTROLLER:
      return "Circuit made by controller";

892
893
894
    case CIRCUIT_PURPOSE_PATH_BIAS_TESTING:
      return "Path-bias testing circuit";

895
896
897
    case CIRCUIT_PURPOSE_HS_VANGUARDS:
      return "Hidden service: Pre-built vanguard circuit";

898
899
900
901
902
903
    default:
      tor_snprintf(buf, sizeof(buf), "UNKNOWN_%d", (int)purpose);
      return buf;
  }
}

904
905
906
907
908
909
/** Pick a reasonable package_window to start out for our circuits.
 * Originally this was hard-coded at 1000, but now the consensus votes
 * on the answer. See proposal 168. */
int32_t
circuit_initial_package_window(void)
{
910
911
912
  int32_t num = networkstatus_get_param(NULL, "circwindow", CIRCWINDOW_START,
                                        CIRCWINDOW_START_MIN,
                                        CIRCWINDOW_START_MAX);
913
914
915
916
  /* If the consensus tells us a negative number, we'd assert. */
  if (num < 0)
    num = CIRCWINDOW_START;
  return num;
917
918
}

919
920
/** Initialize the common elements in a circuit_t, and add it to the global
 * list. */
921
922
static void
init_circuit_base(circuit_t *circ)
923
{
924
  tor_gettimeofday(&circ->timestamp_created);
925

926
927
928
929
930
  // Gets reset when we send CREATE_FAST.
  // circuit_expire_building() expects these to be equal
  // until the orconn is built.
  circ->timestamp_began = circ->timestamp_created;

931
  circ->package_window = circuit_initial_package_window();
932
  circ->deliver_window = CIRCWINDOW_START;
933
  cell_queue_init(&circ->n_chan_cells);
934

935
936
  smartlist_add(circuit_get_global_list(), circ);
  circ->global_circuitlist_idx = smartlist_len(circuit_get_global_list()) - 1;
937
938
}

939
940
/** If we haven't yet decided on a good timeout value for circuit
 * building, we close idle circuits aggressively so we can get more
941
942
943
944
 * data points. These are the default, min, and max consensus values */
#define DFLT_IDLE_TIMEOUT_WHILE_LEARNING (3*60)
#define MIN_IDLE_TIMEOUT_WHILE_LEARNING (10)
#define MAX_IDLE_TIMEOUT_WHILE_LEARNING (1000*60)
945

946
947
948
949
950
951
952
/** Allocate space for a new circuit, initializing with <b>p_circ_id</b>
 * and <b>p_conn</b>. Add it to the global circuit list.
 */
origin_circuit_t *
origin_circuit_new(void)
{
  origin_circuit_t *circ;
953
954
955
  /* never zero, since a global ID of 0 is treated specially by the
   * controller */
  static uint32_t n_circuits_allocated = 1;
956
957

  circ = tor_malloc_zero(sizeof(origin_circuit_t));
958
  circ->base_.magic = ORIGIN_CIRCUIT_MAGIC;
959
960

  circ->next_stream_id = crypto_rand_int(1<<16);
961
  circ->global_identifier = n_circuits_allocated++;
962
963
  circ->remaining_relay_early_cells = MAX_RELAY_EARLY_CELLS_PER_CIRCUIT;
  circ->remaining_relay_early_cells -= crypto_rand_int(2);
964
965
966

  init_circuit_base(TO_CIRCUIT(circ));

967
  /* Add to origin-list. */
968
969
  circ->global_origin_circuit_list_idx = -1;
  circuit_add_to_origin_circuit_list(circ);
970

971
  circuit_build_times_update_last_circ(get_circuit_build_times_mutable());
Mike Perry's avatar
Mike Perry committed
972

973
974
975
976
  if (! circuit_build_times_disabled(get_options()) &&
      circuit_build_times_needs_circuits(get_circuit_build_times())) {
    /* Circuits should be shorter lived if we need more of them
     * for learning a good build timeout */
977
978
979
980
981
    circ->circuit_idle_timeout =
      networkstatus_get_param(NULL, "cbtlearntimeout",
                              DFLT_IDLE_TIMEOUT_WHILE_LEARNING,
                              MIN_IDLE_TIMEOUT_WHILE_LEARNING,
                              MAX_IDLE_TIMEOUT_WHILE_LEARNING);
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
  } else {
    // This should always be larger than the current port prediction time
    // remaining, or else we'll end up with the case where a circuit times out
    // and another one is built, effectively doubling the timeout window.
    //
    // We also randomize it by up to 5% more (ie 5% of 0 to 3600 seconds,
    // depending on how much circuit prediction time is remaining) so that
    // we don't close a bunch of unused circuits all at the same time.
    int prediction_time_remaining =
      predicted_ports_prediction_time_remaining(time(NULL));
    circ->circuit_idle_timeout = prediction_time_remaining+1+
        crypto_rand_int(1+prediction_time_remaining/20);

    if (circ->circuit_idle_timeout <= 0) {
      log_warn(LD_BUG,
               "Circuit chose a negative idle timeout of %d based on "
               "%d seconds of predictive building remaining.",
               circ->circuit_idle_timeout,
               prediction_time_remaining);
For faster browsing, not all history is shown. View entire blame