circuitlist.c 93.9 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
#define OCIRC_EVENT_PRIVATE
55
#include "lib/cc/torint.h"  /* TOR_PRIuSZ */
56

57
58
#include "core/or/or.h"
#include "core/or/channel.h"
59
#include "core/or/channeltls.h"
60
61
62
63
64
65
66
67
68
69
#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"
70
71
#include "lib/crypt_ops/crypto_rand.h"
#include "lib/crypt_ops/crypto_util.h"
72
#include "lib/crypt_ops/crypto_dh.h"
73
#include "feature/dircommon/directory.h"
74
#include "feature/client/entrynodes.h"
75
#include "core/mainloop/mainloop.h"
76
77
78
79
80
#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"
81
82
#include "feature/relay/onion_queue.h"
#include "core/crypto/onion_crypto.h"
83
84
85
86
87
88
#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"
89
#include "feature/stats/predict_ports.h"
90
91
92
93
#include "feature/stats/rephist.h"
#include "feature/nodelist/routerlist.h"
#include "feature/nodelist/routerset.h"
#include "core/or/channelpadding.h"
94
#include "lib/compress/compress.h"
95
96
97
#include "lib/compress/compress_lzma.h"
#include "lib/compress/compress_zlib.h"
#include "lib/compress/compress_zstd.h"
98
#include "lib/buf/buffers.h"
99

100
101
102
#define OCIRC_EVENT_PRIVATE
#include "core/or/ocirc_event.h"

103
#include "ht.h"
104

105
106
107
108
#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"
109
#include "core/or/half_edge_st.h"
110
111
112
#include "core/or/extend_info_st.h"
#include "core/or/or_circuit_st.h"
#include "core/or/origin_circuit_st.h"
113

114
115
/********* START VARIABLES **********/

116
/** A global list of all circuits at this hop. */
117
static smartlist_t *global_circuitlist = NULL;
118

119
120
121
122
/** 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;

123
124
/** A list of all the circuits in CIRCUIT_STATE_CHAN_WAIT. */
static smartlist_t *circuits_pending_chans = NULL;
125

126
127
128
129
/** 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
130
131
/** A list of all the circuits that have been marked with
 * circuit_mark_for_close and which are waiting for circuit_about_to_free. */
132
133
static smartlist_t *circuits_pending_close = NULL;

134
static void circuit_free_cpath_node(crypt_path_t *victim);
135
static void cpath_ref_decref(crypt_path_reference_t *cpath_ref);
136
static void circuit_about_to_free_atexit(circuit_t *circ);
137
static void circuit_about_to_free(circuit_t *circ);
138

139
140
141
142
143
144
145
146
/**
 * 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;

147
148
/********* END VARIABLES ************/

149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
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);
}

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

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

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

211
212
213
214
/** 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,
215
             chan_circid_entry_hash_, chan_circid_entries_eq_)
216
217
218
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_)
219

220
/** The most recently returned entry from circuit_get_by_circid_chan;
221
222
 * used to improve performance when many cells arrive in a row from the
 * same circuit.
223
 */
224
static chan_circid_circuit_map_t *_last_circid_chan_ent = NULL;
225

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

  if (direction == CELL_DIRECTION_OUT) {
242
    chan_ptr = &circ->n_chan;
243
    circid_ptr = &circ->n_circ_id;
244
    make_active = circ->n_chan_cells.n > 0;
245
246
  } else {
    or_circuit_t *c = TO_OR_CIRCUIT(circ);
247
    chan_ptr = &c->p_chan;
248
    circid_ptr = &c->p_circ_id;
249
    make_active = c->p_chan_cells.n > 0;
250
  }
251
  old_chan = *chan_ptr;
252
253
  old_id = *circid_ptr;

254
  if (id == old_id && chan == old_chan)
255
    return;
256

257
258
259
260
261
262
  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;
263
264
  }

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

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

294
  /* Change the values only after we have possibly made the circuit inactive
295
296
   * on the previous chan. */
  *chan_ptr = chan;
297
298
  *circid_ptr = id;

299
  if (chan == NULL)
300
301
    return;

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

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

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

336
337
338
339
340
341
  /* Adjust circuit counts on new channel */
  if (direction == CELL_DIRECTION_OUT) {
    ++chan->num_n_circuits;
  } else {
    ++chan->num_p_circuits;
  }
342
343
}

344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
/** 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
366
367
    if (!ent->made_placeholder_at)
      ent->made_placeholder_at = approx_time();
368
369
370
371
  } 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
372
373
    /* leave circuit at NULL. */
    ent->made_placeholder_at = approx_time();
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
    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);
}

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

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

456
457
458
  if (chan) {
    chan->timestamp_last_had_circuits = approx_time();
  }
459

460
461
462
463
  if (circ->p_delete_pending && old_chan) {
    channel_mark_circid_unusable(old_chan, old_id);
    circ->p_delete_pending = 0;
  }
464
465
466
467
}

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

476
  circuit_set_circid_chan_helper(circ, CELL_DIRECTION_OUT, id, chan);
477

478
479
480
  if (chan) {
    chan->timestamp_last_had_circuits = approx_time();
  }
481

482
483
  if (circ->n_delete_pending && old_chan) {
    channel_mark_circid_unusable(old_chan, old_id);
484
    circ->n_delete_pending = 0;
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
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
/**
 * Helper function to publish a message about events on an origin circuit
 *
 * Publishes a message to subscribers of origin circuit events, and
 * sends the control event.
 **/
int
circuit_event_status(origin_circuit_t *circ, circuit_status_event_t tp,
                     int reason_code)
{
  ocirc_event_msg_t msg;

  tor_assert(circ);

  msg.type = OCIRC_MSGTYPE_CEVENT;
  msg.u.cevent.gid = circ->global_identifier;
  msg.u.cevent.evtype = tp;
  msg.u.cevent.reason = reason_code;
  msg.u.cevent.onehop = circ->build_state->onehop_tunnel;

  ocirc_event_publish(&msg);
  return control_event_circuit_status(circ, tp, reason_code);
}

/**
 * Helper function to publish a state change message
 *
 * circuit_set_state() calls this to notify subscribers about a change
 * of the state of an origin circuit.
 **/
static void
circuit_state_publish(const circuit_t *circ)
{
  ocirc_event_msg_t msg;
  const origin_circuit_t *ocirc;

  if (!CIRCUIT_IS_ORIGIN(circ))
    return;
  ocirc = CONST_TO_ORIGIN_CIRCUIT(circ);
  /* Only inbound OR circuits can be in this state, not origin circuits. */
  tor_assert(circ->state != CIRCUIT_STATE_ONIONSKIN_PENDING);

  msg.type = OCIRC_MSGTYPE_STATE;
  msg.u.state.gid = ocirc->global_identifier;
  msg.u.state.state = circ->state;
  msg.u.state.onehop = ocirc->build_state->onehop_tunnel;

  ocirc_event_publish(&msg);
}

538
539
/** Change the state of <b>circ</b> to <b>state</b>, adding it to or removing
 * it from lists as appropriate. */
540
void
541
circuit_set_state(circuit_t *circ, uint8_t state)
542
543
544
545
{
  tor_assert(circ);
  if (state == circ->state)
    return;
546
  if (PREDICT_UNLIKELY(!circuits_pending_chans))
547
    circuits_pending_chans = smartlist_new();
548
549
  if (PREDICT_UNLIKELY(!circuits_pending_other_guards))
    circuits_pending_other_guards = smartlist_new();
550
  if (circ->state == CIRCUIT_STATE_CHAN_WAIT) {
551
    /* remove from waiting-circuit list. */
552
    smartlist_remove(circuits_pending_chans, circ);
553
  }
554
  if (state == CIRCUIT_STATE_CHAN_WAIT) {
555
    /* add to waiting-circuit list. */
556
    smartlist_add(circuits_pending_chans, circ);
557
  }
558
559
560
561
562
563
564
  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)
565
    tor_assert(!circ->n_chan_create_cell);
566
  circ->state = state;
567
  circuit_state_publish(circ);
568
569
}

570
/** Append to <b>out</b> all circuits in state CHAN_WAIT waiting for
571
572
 * the given connection. */
void
573
circuit_get_all_pending_on_channel(smartlist_t *out, channel_t *chan)
574
575
{
  tor_assert(out);
576
  tor_assert(chan);
577

578
  if (!circuits_pending_chans)
579
580
    return;

581
  SMARTLIST_FOREACH_BEGIN(circuits_pending_chans, circuit_t *, circ) {
582
583
    if (circ->marked_for_close)
      continue;
584
585
    if (!circ->n_hop)
      continue;
586
    tor_assert(circ->state == CIRCUIT_STATE_CHAN_WAIT);
587
    if (tor_digest_is_zero(circ->n_hop->identity_digest)) {
588
      /* Look at addr/port. This is an unkeyed connection. */
589
      if (!channel_matches_extend_info(chan, circ->n_hop))
590
591
592
        continue;
    } else {
      /* We expected a key. See if it's the right one. */
593
594
      if (tor_memneq(chan->identity_digest,
                     circ->n_hop->identity_digest, DIGEST_LEN))
595
        continue;
596
    }
597
    smartlist_add(out, circ);
598
  } SMARTLIST_FOREACH_END(circ);
599
600
}

601
602
/** Return the number of circuits in state CHAN_WAIT, waiting for the given
 * channel. */
603
int
604
circuit_count_pending_on_channel(channel_t *chan)
605
606
{
  int cnt;
607
  smartlist_t *sl = smartlist_new();
608
609
610
611

  tor_assert(chan);

  circuit_get_all_pending_on_channel(sl, chan);
612
613
  cnt = smartlist_len(sl);
  smartlist_free(sl);
614
  log_debug(LD_CIRC,"or_conn to %s, %d pending circs",
615
            channel_get_canonical_remote_descr(chan),
616
            cnt);
617
618
619
  return cnt;
}

620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
/** 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;
}

653
654
655
/** Detach from the global circuit list, and deallocate, all
 * circuits that have been marked for close.
 */
656
657
void
circuit_close_all_marked(void)
658
{
659
660
661
  if (circuits_pending_close == NULL)
    return;

662
  smartlist_t *lst = circuit_get_global_list();
663
664
665
666
667
668
669
670
671
  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;
672
    }
673
674
    circ->global_circuitlist_idx = -1;

675
676
    /* Remove it from the origin circuit list, if appropriate. */
    if (CIRCUIT_IS_ORIGIN(circ)) {
677
      circuit_remove_from_origin_circuit_list(TO_ORIGIN_CIRCUIT(circ));
678
679
    }

680
681
    circuit_about_to_free(circ);
    circuit_free(circ);
682
  } SMARTLIST_FOREACH_END(circ);
683
684

  smartlist_clear(circuits_pending_close);
685
686
}

687
/** Return a pointer to the global list of circuits. */
688
MOCK_IMPL(smartlist_t *,
689
circuit_get_global_list,(void))
690
{
691
692
693
  if (NULL == global_circuitlist)
    global_circuitlist = smartlist_new();
  return global_circuitlist;
694
695
}

696
697
698
699
700
701
/** 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();
702
  return global_origin_circuit_list;
703
704
}

705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
/**
 * 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;
}

755
756
/** Function to make circ-\>state human-readable */
const char *
757
758
circuit_state_to_string(int state)
{
Nick Mathewson's avatar
Nick Mathewson committed
759
  static char buf[64];
760
761
762
  switch (state) {
    case CIRCUIT_STATE_BUILDING: return "doing handshakes";
    case CIRCUIT_STATE_ONIONSKIN_PENDING: return "processing the onion";
763
    case CIRCUIT_STATE_CHAN_WAIT: return "connecting to server";
764
765
    case CIRCUIT_STATE_GUARD_WAIT: return "waiting to see how other "
      "guards perform";
766
767
    case CIRCUIT_STATE_OPEN: return "open";
    default:
768
      log_warn(LD_BUG, "Unknown circuit state %d", state);
769
      tor_snprintf(buf, sizeof(buf), "unknown state [%d]", state);
770
771
772
773
      return buf;
  }
}

774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
/** 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";
789
790
791
792

    case CIRCUIT_PURPOSE_C_HSDIR_GET:
      return "HS_CLIENT_HSDIR";

793
    case CIRCUIT_PURPOSE_C_INTRODUCING:
794
795
796
797
798
799
800
801
802
803
    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";

804
805
806
    case CIRCUIT_PURPOSE_S_HSDIR_POST:
      return "HS_SERVICE_HSDIR";

807
808
809
810
811
812
813
814
815
816
    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";
817
    case CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT:
818
      return "MEASURE_TIMEOUT";
819
820
    case CIRCUIT_PURPOSE_CONTROLLER:
      return "CONTROLLER";
821
822
    case CIRCUIT_PURPOSE_PATH_BIAS_TESTING:
      return "PATH_BIAS_TESTING";
823
824
    case CIRCUIT_PURPOSE_HS_VANGUARDS:
      return "HS_VANGUARDS";
825
826
827
828
829
830
831

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

832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
/** 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:
852
    case CIRCUIT_PURPOSE_PATH_BIAS_TESTING:
853
    case CIRCUIT_PURPOSE_HS_VANGUARDS:
854
855
856
857
858
859
860
861
862
      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";

863
    case CIRCUIT_PURPOSE_C_HSDIR_GET:
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
    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";

880
    case CIRCUIT_PURPOSE_S_HSDIR_POST:
881
882
883
884
885
886
887
888
889
890
891
892
    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";
    }
}

893
894
895
896
897
898
899
900
901
902
903
904
905
/** 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:
906
      return "Acting as rendezvous (pending)";
907
    case CIRCUIT_PURPOSE_REND_ESTABLISHED:
908
      return "Acting as rendezvous (established)";
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
    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";
925
926
927
    case CIRCUIT_PURPOSE_C_HSDIR_GET:
      return "Hidden service client: Fetching HS descriptor";

928
929
930
931
932
933
934
935
936
937
938
    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";
939
940
    case CIRCUIT_PURPOSE_S_HSDIR_POST:
      return "Hidden service: Uploading HS descriptor";
941
942
943
944
945
946
947

    case CIRCUIT_PURPOSE_TESTING:
      return "Testing circuit";

    case CIRCUIT_PURPOSE_CONTROLLER:
      return "Circuit made by controller";

948
949
950
    case CIRCUIT_PURPOSE_PATH_BIAS_TESTING:
      return "Path-bias testing circuit";

951
952
953
    case CIRCUIT_PURPOSE_HS_VANGUARDS:
      return "Hidden service: Pre-built vanguard circuit";

954
955
956
957
958
959
    default:
      tor_snprintf(buf, sizeof(buf), "UNKNOWN_%d", (int)purpose);
      return buf;
  }
}

960
961
962
963
964
965
/** 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)
{
966
967
968
  int32_t num = networkstatus_get_param(NULL, "circwindow", CIRCWINDOW_START,
                                        CIRCWINDOW_START_MIN,
                                        CIRCWINDOW_START_MAX);
969
970
971
972
  /* If the consensus tells us a negative number, we'd assert. */
  if (num < 0)
    num = CIRCWINDOW_START;
  return num;
973
974
}

975
976
/** Initialize the common elements in a circuit_t, and add it to the global
 * list. */
977
978
static void
init_circuit_base(circuit_t *circ)
979
{
980
  tor_gettimeofday(&circ->timestamp_created);
981

982
983
984
985
986
  // 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;

987
  circ->package_window = circuit_initial_package_window();
988
  circ->deliver_window = CIRCWINDOW_START;
989
  cell_queue_init(&circ->n_chan_cells);
990

991
992
  smartlist_add(circuit_get_global_list(), circ);
  circ->global_circuitlist_idx = smartlist_len(circuit_get_global_list()) - 1;
993
994
}

995
996
/** If we haven't yet decided on a good timeout value for circuit
 * building, we close idle circuits aggressively so we can get more
997
998
999
1000
 * 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)
For faster browsing, not all history is shown. View entire blame