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
/**
 * 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)
{
499
  ocirc_cevent_msg_t *msg = tor_malloc(sizeof(*msg));
500
501
502

  tor_assert(circ);

503
504
505
506
  msg->gid = circ->global_identifier;
  msg->evtype = tp;
  msg->reason = reason_code;
  msg->onehop = circ->build_state->onehop_tunnel;
507

508
  ocirc_cevent_publish(msg);
509
510
511
512
513
514
515
  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
516
517
 * of the state of an origin circuit.  @a circ must be an origin
 * circuit.
518
519
520
521
 **/
static void
circuit_state_publish(const circuit_t *circ)
{
522
  ocirc_state_msg_t *msg = tor_malloc(sizeof(*msg));
523
524
  const origin_circuit_t *ocirc;

525
  tor_assert(CIRCUIT_IS_ORIGIN(circ));
526
527
528
529
  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);

530
531
532
  msg->gid = ocirc->global_identifier;
  msg->state = circ->state;
  msg->onehop = ocirc->build_state->onehop_tunnel;
533

534
  ocirc_state_publish(msg);
535
536
}

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

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

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

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

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

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

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

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

    case CIRCUIT_PURPOSE_TESTING:
      return "Testing circuit";

    case CIRCUIT_PURPOSE_CONTROLLER:
      return "Circuit made by controller";

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

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

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

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

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

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

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

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

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