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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include "feature/dircache/directory.h"
#include "feature/client/entrynodes.h"
#include "core/mainloop/main.h"
#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"
#include "core/crypto/onion.h"
#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"
91
#include "lib/compress/compress.h"
92
93
94
#include "lib/compress/compress_lzma.h"
#include "lib/compress/compress_zlib.h"
#include "lib/compress/compress_zstd.h"
95
#include "lib/container/buffers.h"
96

97
#include "ht.h"
98

99
100
101
102
#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"
103
#include "core/or/half_edge_st.h"
104
105
106
#include "core/or/extend_info_st.h"
#include "core/or/or_circuit_st.h"
#include "core/or/origin_circuit_st.h"
107

108
109
/********* START VARIABLES **********/

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

113
114
115
116
/** 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;

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

120
121
122
123
/** 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
124
125
/** A list of all the circuits that have been marked with
 * circuit_mark_for_close and which are waiting for circuit_about_to_free. */
126
127
static smartlist_t *circuits_pending_close = NULL;

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

133
134
135
136
137
138
139
140
/**
 * 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;

141
142
/********* END VARIABLES ************/

143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
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);
}

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

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

189
/** Helper: return a hash based on circuit ID and the pointer value of
190
 * chan in <b>a</b>. */
191
static inline unsigned int
192
chan_circid_entry_hash_(chan_circid_circuit_map_t *a)
193
{
194
195
196
197
198
199
200
201
202
  /* 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));
203
204
}

205
206
207
208
/** 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,
209
             chan_circid_entry_hash_, chan_circid_entries_eq_)
210
211
212
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_)
213

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

220
221
222
/** 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
223
 * the old entry (if any) and adding a new one. */
224
static void
225
226
227
circuit_set_circid_chan_helper(circuit_t *circ, int direction,
                               circid_t id,
                               channel_t *chan)
228
{
229
230
231
  chan_circid_circuit_map_t search;
  chan_circid_circuit_map_t *found;
  channel_t *old_chan, **chan_ptr;
232
  circid_t old_id, *circid_ptr;
233
  int make_active, attached = 0;
234
235

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

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

251
252
253
254
255
256
  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;
257
258
  }

259
260
261
  if (old_chan) {
    /*
     * If we're changing channels or ID and had an old channel and a non
262
263
264
     * 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).
265
     */
266
    if (old_id != 0 && (old_chan != chan || old_id != id) &&
267
        !(circ->marked_for_close)) {
268
269
270
271
272
      tor_assert(old_chan->cmux);
      circuitmux_detach_circuit(old_chan->cmux, circ);
    }

    /* we may need to remove it from the conn-circid map */
273
    search.circ_id = old_id;
274
275
    search.chan = old_chan;
    found = HT_REMOVE(chan_circid_map, &chan_circid_map, &search);
276
    if (found) {
277
      tor_free(found);
278
279
280
281
282
283
284
285
      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);
      }
    }
286
287
  }

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

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

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

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

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

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

338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
/** 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
360
361
    if (!ent->made_placeholder_at)
      ent->made_placeholder_at = approx_time();
362
363
364
365
  } 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
366
367
    /* leave circuit at NULL. */
    ent->made_placeholder_at = approx_time();
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
    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);
}

396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
/** 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. */
418
419
MOCK_IMPL(void,
channel_note_destroy_not_pending,(channel_t *chan, circid_t id))
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
{
  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);
}

437
438
/** Set the p_conn field of a circuit <b>circ</b>, along
 * with the corresponding circuit ID, and add the circuit as appropriate
439
 * to the (chan,id)-\>circuit map. */
440
void
441
circuit_set_p_circid_chan(or_circuit_t *or_circ, circid_t id,
442
                          channel_t *chan)
443
{
444
445
446
447
448
  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);
449

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

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

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

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

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

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

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

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

521
  if (!circuits_pending_chans)
522
523
    return;

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

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

  tor_assert(chan);

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

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

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

605
  smartlist_t *lst = circuit_get_global_list();
606
607
608
609
610
611
612
613
614
  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;
615
    }
616
617
    circ->global_circuitlist_idx = -1;

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

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

  smartlist_clear(circuits_pending_close);
628
629
}

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

639
640
641
642
643
644
/** 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();
645
  return global_origin_circuit_list;
646
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
/**
 * 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;
}

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

717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
/** 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";
732
733
734
735

    case CIRCUIT_PURPOSE_C_HSDIR_GET:
      return "HS_CLIENT_HSDIR";

736
    case CIRCUIT_PURPOSE_C_INTRODUCING:
737
738
739
740
741
742
743
744
745
746
    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";

747
748
749
    case CIRCUIT_PURPOSE_S_HSDIR_POST:
      return "HS_SERVICE_HSDIR";

750
751
752
753
754
755
756
757
758
759
    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";
760
    case CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT:
761
      return "MEASURE_TIMEOUT";
762
763
    case CIRCUIT_PURPOSE_CONTROLLER:
      return "CONTROLLER";
764
765
    case CIRCUIT_PURPOSE_PATH_BIAS_TESTING:
      return "PATH_BIAS_TESTING";
766
767
    case CIRCUIT_PURPOSE_HS_VANGUARDS:
      return "HS_VANGUARDS";
768
769
770
771
772
773
774

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

775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
/** 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:
795
    case CIRCUIT_PURPOSE_PATH_BIAS_TESTING:
796
    case CIRCUIT_PURPOSE_HS_VANGUARDS:
797
798
799
800
801
802
803
804
805
      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";

806
    case CIRCUIT_PURPOSE_C_HSDIR_GET:
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
    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";

823
    case CIRCUIT_PURPOSE_S_HSDIR_POST:
824
825
826
827
828
829
830
831
832
833
834
835
    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";
    }
}

836
837
838
839
840
841
842
843
844
845
846
847
848
/** 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:
849
      return "Acting as rendezvous (pending)";
850
    case CIRCUIT_PURPOSE_REND_ESTABLISHED:
851
      return "Acting as rendezvous (established)";
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
    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";
868
869
870
    case CIRCUIT_PURPOSE_C_HSDIR_GET:
      return "Hidden service client: Fetching HS descriptor";

871
872
873
874
875
876
877
878
879
880
881
    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";
882
883
    case CIRCUIT_PURPOSE_S_HSDIR_POST:
      return "Hidden service: Uploading HS descriptor";
884
885
886
887
888
889
890

    case CIRCUIT_PURPOSE_TESTING:
      return "Testing circuit";

    case CIRCUIT_PURPOSE_CONTROLLER:
      return "Circuit made by controller";

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

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

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

903
904
905
906
907
908
/** 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)
{
909
910
911
  int32_t num = networkstatus_get_param(NULL, "circwindow", CIRCWINDOW_START,
                                        CIRCWINDOW_START_MIN,
                                        CIRCWINDOW_START_MAX);
912
913
914
915
  /* If the consensus tells us a negative number, we'd assert. */
  if (num < 0)
    num = CIRCWINDOW_START;
  return num;
916
917
}

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

925
926
927
928
929
  // 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;

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

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

938
939
/** If we haven't yet decided on a good timeout value for circuit
 * building, we close idle circuits aggressively so we can get more
940
941
942
943
 * 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)
944

945
946
947
948
949
950
951
/** 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;
952
953
954
  /* never zero, since a global ID of 0 is treated specially by the
   * controller */
  static uint32_t n_circuits_allocated = 1;
955
956

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

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

  init_circuit_base(TO_CIRCUIT(circ));

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

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

972
973
974
975
  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 */
976
977
978
979
980
    circ->circuit_idle_timeout =
      networkstatus_get_param(NULL, "cbtlearntimeout",
                              DFLT_IDLE_TIMEOUT_WHILE_LEARNING,
                              MIN_IDLE_TIMEOUT_WHILE_LEARNING,
                              MAX_IDLE_TIMEOUT_WHILE_LEARNING);
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
  } 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);
1000
      circ->circuit_idle_timeout =
For faster browsing, not all history is shown. View entire blame