circuitlist.c 92.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-2019, 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
#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"
65
#include "core/or/circuitpadding.h"
66
#include "core/or/crypt_path.h"
67
68
69
70
#include "core/mainloop/connection.h"
#include "app/config/config.h"
#include "core/or/connection_edge.h"
#include "core/or/connection_or.h"
71
#include "feature/control/control_events.h"
72
73
#include "lib/crypt_ops/crypto_rand.h"
#include "lib/crypt_ops/crypto_util.h"
74
#include "lib/crypt_ops/crypto_dh.h"
75
#include "feature/dircommon/directory.h"
76
#include "feature/client/entrynodes.h"
77
#include "core/mainloop/mainloop.h"
78
79
80
81
82
#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"
83
84
#include "feature/relay/onion_queue.h"
#include "core/crypto/onion_crypto.h"
85
86
87
88
89
90
#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"
91
#include "feature/stats/predict_ports.h"
92
93
94
95
#include "feature/stats/rephist.h"
#include "feature/nodelist/routerlist.h"
#include "feature/nodelist/routerset.h"
#include "core/or/channelpadding.h"
96
#include "lib/compress/compress.h"
97
98
99
#include "lib/compress/compress_lzma.h"
#include "lib/compress/compress_zlib.h"
#include "lib/compress/compress_zstd.h"
100
#include "lib/buf/buffers.h"
101

102
103
104
#define OCIRC_EVENT_PRIVATE
#include "core/or/ocirc_event.h"

105
#include "ht.h"
106

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

116
117
/********* START VARIABLES **********/

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

121
122
123
124
/** 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;

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

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

136
static void cpath_ref_decref(crypt_path_reference_t *cpath_ref);
137
static void circuit_about_to_free_atexit(circuit_t *circ);
138
static void circuit_about_to_free(circuit_t *circ);
139

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

148
149
/********* END VARIABLES ************/

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
/** 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
367
368
    if (!ent->made_placeholder_at)
      ent->made_placeholder_at = approx_time();
369
370
371
372
  } 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
373
374
    /* leave circuit at NULL. */
    ent->made_placeholder_at = approx_time();
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
402
    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);
}

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

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

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

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

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

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

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

483
484
  if (circ->n_delete_pending && old_chan) {
    channel_mark_circid_unusable(old_chan, old_id);
485
    circ->n_delete_pending = 0;
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
538
/**
 * 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);
}

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

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

579
  if (!circuits_pending_chans)
580
581
    return;

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

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

  tor_assert(chan);

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

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

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

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

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

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

  smartlist_clear(circuits_pending_close);
686
687
}

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

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

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

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

    case CIRCUIT_PURPOSE_C_HSDIR_GET:
      return "HS_CLIENT_HSDIR";

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

805
806
807
    case CIRCUIT_PURPOSE_S_HSDIR_POST:
      return "HS_SERVICE_HSDIR";

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

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

835
836
837
838
839
840
841
842
843
844
845
846
847
/** 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();
848
      FALLTHROUGH;
849
850
851
852
853
854

    case CIRCUIT_PURPOSE_OR:
    case CIRCUIT_PURPOSE_C_GENERAL:
    case CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT:
    case CIRCUIT_PURPOSE_TESTING:
    case CIRCUIT_PURPOSE_CONTROLLER:
855
    case CIRCUIT_PURPOSE_PATH_BIAS_TESTING:
856
    case CIRCUIT_PURPOSE_HS_VANGUARDS:
857
    case CIRCUIT_PURPOSE_C_CIRCUIT_PADDING:
858
859
860
861
862
863
864
865
866
      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";

867
    case CIRCUIT_PURPOSE_C_HSDIR_GET:
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
    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";

884
    case CIRCUIT_PURPOSE_S_HSDIR_POST:
885
886
887
888
889
890
891
892
893
894
895
896
    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";
    }
}

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

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

    case CIRCUIT_PURPOSE_TESTING:
      return "Testing circuit";

    case CIRCUIT_PURPOSE_CONTROLLER:
      return "Circuit made by controller";

952
953
954
    case CIRCUIT_PURPOSE_PATH_BIAS_TESTING:
      return "Path-bias testing circuit";

955
956
957
    case CIRCUIT_PURPOSE_HS_VANGUARDS:
      return "Hidden service: Pre-built vanguard circuit";

958
959
960
    case CIRCUIT_PURPOSE_C_CIRCUIT_PADDING:
      return "Circuit kept open for padding";

961
962
963
964
965
966
    default:
      tor_snprintf(buf, sizeof(buf), "UNKNOWN_%d", (int)purpose);
      return buf;
  }
}

967
968
969
970
971
972
/** 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)
{
973
974
975
  int32_t num = networkstatus_get_param(NULL, "circwindow", CIRCWINDOW_START,
                                        CIRCWINDOW_START_MIN,
                                        CIRCWINDOW_START_MAX);
976
977
978
979
  /* If the consensus tells us a negative number, we'd assert. */
  if (num < 0)
    num = CIRCWINDOW_START;
  return num;
980
981
}

982
983
/** Initialize the common elements in a circuit_t, and add it to the global
 * list. */
984
985
static void
init_circuit_base(circuit_t *circ)
986
{
987
  tor_gettimeofday(&circ->timestamp_created);
988

989
990
991
992
993
  // 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;

994
  circ->package_window = circuit_initial_package_window();
995
  circ->deliver_window = CIRCWINDOW_START;
996
  circuit_reset_sendme_randomness(circ);
997
  cell_queue_init(&circ->n_chan_cells);
998

999
1000
  smartlist_add(circuit_get_global_list(), circ);
  circ->global_circuitlist_idx = smartlist_len(circuit_get_global_list()) - 1;
For faster browsing, not all history is shown. View entire blame