circuitlist.c 82.5 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.
4
 * Copyright (c) 2007-2017, The Tor Project, Inc. */
5
6
7
8
/* See LICENSE for licensing information */

/**
 * \file circuitlist.c
9
 *
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
 * \brief Manage global structures that list and index circuits, and
 *   look up circuits within them.
 *
 * One of the most frequent operations in Tor occurs every time that
 * a relay cell arrives on a channel.  When that happens, we need to
 * find which circuit it is associated with, based on the channel and the
 * circuit ID in the relay cell.
 *
 * To handle that, we maintain a global list of circuits, and a hashtable
 * mapping [channel,circID] pairs to circuits.  Circuits are added to and
 * removed from this mapping using circuit_set_p_circid_chan() and
 * circuit_set_n_circid_chan().  To look up a circuit from this map, most
 * callers should use circuit_get_by_circid_channel(), though
 * circuit_get_by_circid_channel_even_if_marked() is appropriate under some
 * circumstances.
 *
 * We also need to allow for the possibility that we have blocked use of a
 * circuit ID (because we are waiting to send a DESTROY cell), but the
 * circuit is not there any more.  For that case, we allow placeholder
 * entries in the table, using channel_mark_circid_unusable().
 *
 * To efficiently handle a channel that has just opened, we also maintain a
 * list of the circuits waiting for channels, so we can attach them as
 * needed without iterating through the whole list of circuits, using
 * circuit_get_all_pending_on_channel().
 *
 * In this module, we also handle the list of circuits that have been
 * marked for close elsewhere, and close them as needed.  (We use this
 * "mark now, close later" pattern here and elsewhere to avoid
 * unpredictable recursion if we closed every circuit immediately upon
 * realizing it needed to close.)  See circuit_mark_for_close() for the
 * mark function, and circuit_close_all_marked() for the close function.
 *
 * For hidden services, we need to be able to look up introduction point
 * circuits and rendezvous circuits by cookie, key, etc.  These are
 * currently handled with linear searches in
 * circuit_get_ready_rend_circuit_by_rend_data(),
 * circuit_get_next_by_pk_and_purpose(), and with hash lookups in
 * circuit_get_rendezvous() and circuit_get_intro_point().
 *
 * This module is also the entry point for our out-of-memory handler
 * logic, which was originally circuit-focused.
52
 **/
53
#define CIRCUITLIST_PRIVATE
54
#include "or.h"
55
#include "channel.h"
56
#include "circpathbias.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
57
#include "circuitbuild.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
58
#include "circuitlist.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
59
#include "circuituse.h"
60
#include "circuitstats.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
61
#include "connection.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
62
#include "config.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
63
#include "connection_edge.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
64
#include "connection_or.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
65
#include "control.h"
66
#include "entrynodes.h"
67
#include "main.h"
68
#include "hs_circuit.h"
69
#include "hs_circuitmap.h"
70
#include "hs_common.h"
71
#include "hs_ident.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
72
#include "networkstatus.h"
73
#include "nodelist.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
74
#include "onion.h"
75
#include "onion_fast.h"
76
#include "policies.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
77
#include "relay.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
78
#include "rendclient.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
79
#include "rendcommon.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
80
#include "rephist.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
81
#include "routerlist.h"
82
#include "routerset.h"
83
#include "channelpadding.h"
84

85
#include "ht.h"
86
87
88

/********* START VARIABLES **********/

89
/** A global list of all circuits at this hop. */
90
static smartlist_t *global_circuitlist = NULL;
91

92
93
94
95
/** 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;

96
97
/** A list of all the circuits in CIRCUIT_STATE_CHAN_WAIT. */
static smartlist_t *circuits_pending_chans = NULL;
98

99
100
101
102
/** 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
103
104
/** A list of all the circuits that have been marked with
 * circuit_mark_for_close and which are waiting for circuit_about_to_free. */
105
106
static smartlist_t *circuits_pending_close = NULL;

107
static void circuit_free_cpath_node(crypt_path_t *victim);
108
static void cpath_ref_decref(crypt_path_reference_t *cpath_ref);
109
static void circuit_about_to_free_atexit(circuit_t *circ);
110
static void circuit_about_to_free(circuit_t *circ);
111

112
113
/********* END VARIABLES ************/

114
/** A map from channel and circuit ID to circuit.  (Lookup performance is
115
 * very important here, since we need to do it every time a cell arrives.) */
116
117
118
typedef struct chan_circid_circuit_map_t {
  HT_ENTRY(chan_circid_circuit_map_t) node;
  channel_t *chan;
119
  circid_t circ_id;
120
  circuit_t *circuit;
Nick Mathewson's avatar
Nick Mathewson committed
121
122
  /* For debugging 12184: when was this placeholder item added? */
  time_t made_placeholder_at;
123
} chan_circid_circuit_map_t;
124

125
/** Helper for hash tables: compare the channel and circuit ID for a and
126
 * b, and return less than, equal to, or greater than zero appropriately.
127
 */
128
static inline int
129
chan_circid_entries_eq_(chan_circid_circuit_map_t *a,
130
                        chan_circid_circuit_map_t *b)
131
{
132
  return a->chan == b->chan && a->circ_id == b->circ_id;
133
134
}

135
/** Helper: return a hash based on circuit ID and the pointer value of
136
 * chan in <b>a</b>. */
137
static inline unsigned int
138
chan_circid_entry_hash_(chan_circid_circuit_map_t *a)
139
{
140
141
142
143
144
145
146
147
148
  /* 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));
149
150
}

151
152
153
154
/** 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,
155
             chan_circid_entry_hash_, chan_circid_entries_eq_)
156
157
158
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_)
159

160
/** The most recently returned entry from circuit_get_by_circid_chan;
161
162
 * used to improve performance when many cells arrive in a row from the
 * same circuit.
163
 */
164
static chan_circid_circuit_map_t *_last_circid_chan_ent = NULL;
165

166
167
168
/** 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
169
 * the old entry (if any) and adding a new one. */
170
static void
171
172
173
circuit_set_circid_chan_helper(circuit_t *circ, int direction,
                               circid_t id,
                               channel_t *chan)
174
{
175
176
177
  chan_circid_circuit_map_t search;
  chan_circid_circuit_map_t *found;
  channel_t *old_chan, **chan_ptr;
178
  circid_t old_id, *circid_ptr;
179
  int make_active, attached = 0;
180
181

  if (direction == CELL_DIRECTION_OUT) {
182
    chan_ptr = &circ->n_chan;
183
    circid_ptr = &circ->n_circ_id;
184
    make_active = circ->n_chan_cells.n > 0;
185
186
  } else {
    or_circuit_t *c = TO_OR_CIRCUIT(circ);
187
    chan_ptr = &c->p_chan;
188
    circid_ptr = &c->p_circ_id;
189
    make_active = c->p_chan_cells.n > 0;
190
  }
191
  old_chan = *chan_ptr;
192
193
  old_id = *circid_ptr;

194
  if (id == old_id && chan == old_chan)
195
    return;
196

197
198
199
200
201
202
  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;
203
204
  }

205
206
207
  if (old_chan) {
    /*
     * If we're changing channels or ID and had an old channel and a non
208
209
210
     * 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).
211
     */
212
    if (old_id != 0 && (old_chan != chan || old_id != id) &&
213
        !(circ->marked_for_close)) {
214
215
216
217
218
      tor_assert(old_chan->cmux);
      circuitmux_detach_circuit(old_chan->cmux, circ);
    }

    /* we may need to remove it from the conn-circid map */
219
    search.circ_id = old_id;
220
221
    search.chan = old_chan;
    found = HT_REMOVE(chan_circid_map, &chan_circid_map, &search);
222
    if (found) {
223
      tor_free(found);
224
225
226
227
228
229
230
231
      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);
      }
    }
232
233
  }

234
  /* Change the values only after we have possibly made the circuit inactive
235
236
   * on the previous chan. */
  *chan_ptr = chan;
237
238
  *circid_ptr = id;

239
  if (chan == NULL)
240
241
    return;

242
  /* now add the new one to the conn-circid map */
243
  search.circ_id = id;
244
245
  search.chan = chan;
  found = HT_FIND(chan_circid_map, &chan_circid_map, &search);
246
247
  if (found) {
    found->circuit = circ;
Nick Mathewson's avatar
Nick Mathewson committed
248
    found->made_placeholder_at = 0;
249
  } else {
250
    found = tor_malloc_zero(sizeof(chan_circid_circuit_map_t));
251
    found->circ_id = id;
252
    found->chan = chan;
253
    found->circuit = circ;
254
    HT_INSERT(chan_circid_map, &chan_circid_map, found);
255
  }
256

257
258
  /*
   * Attach to the circuitmux if we're changing channels or IDs and
259
260
   * have a new channel and ID to use and the circuit is not marked for
   * close.
261
   */
262
263
  if (chan && id != 0 && (old_chan != chan || old_id != id) &&
      !(circ->marked_for_close)) {
264
265
    tor_assert(chan->cmux);
    circuitmux_attach_circuit(chan->cmux, circ, direction);
266
    attached = 1;
267
268
269
270
271
272
  }

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

276
277
278
279
280
281
  /* Adjust circuit counts on new channel */
  if (direction == CELL_DIRECTION_OUT) {
    ++chan->num_n_circuits;
  } else {
    ++chan->num_p_circuits;
  }
282
283
}

284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
/** 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
306
307
    if (!ent->made_placeholder_at)
      ent->made_placeholder_at = approx_time();
308
309
310
311
  } 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
312
313
    /* leave circuit at NULL. */
    ent->made_placeholder_at = approx_time();
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
    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);
}

342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
/** 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. */
364
365
MOCK_IMPL(void,
channel_note_destroy_not_pending,(channel_t *chan, circid_t id))
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
{
  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);
}

383
384
/** Set the p_conn field of a circuit <b>circ</b>, along
 * with the corresponding circuit ID, and add the circuit as appropriate
385
 * to the (chan,id)-\>circuit map. */
386
void
387
circuit_set_p_circid_chan(or_circuit_t *or_circ, circid_t id,
388
                          channel_t *chan)
389
{
390
391
392
393
394
  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);
395

396
  if (chan) {
397
398
399
    tor_assert(bool_eq(or_circ->p_chan_cells.n,
                       or_circ->next_active_on_p_chan));

400
401
    chan->timestamp_last_had_circuits = approx_time();
  }
402

403
404
405
406
  if (circ->p_delete_pending && old_chan) {
    channel_mark_circid_unusable(old_chan, old_id);
    circ->p_delete_pending = 0;
  }
407
408
409
410
}

/** Set the n_conn field of a circuit <b>circ</b>, along
 * with the corresponding circuit ID, and add the circuit as appropriate
411
 * to the (chan,id)-\>circuit map. */
412
void
413
414
circuit_set_n_circid_chan(circuit_t *circ, circid_t id,
                          channel_t *chan)
415
{
416
417
418
  channel_t *old_chan = circ->n_chan;
  circid_t old_id = circ->n_circ_id;

419
  circuit_set_circid_chan_helper(circ, CELL_DIRECTION_OUT, id, chan);
420

421
  if (chan) {
422
    tor_assert(bool_eq(circ->n_chan_cells.n, circ->next_active_on_n_chan));
423

424
425
    chan->timestamp_last_had_circuits = approx_time();
  }
426

427
428
  if (circ->n_delete_pending && old_chan) {
    channel_mark_circid_unusable(old_chan, old_id);
429
    circ->n_delete_pending = 0;
430
  }
431
432
}

433
434
/** Change the state of <b>circ</b> to <b>state</b>, adding it to or removing
 * it from lists as appropriate. */
435
void
436
circuit_set_state(circuit_t *circ, uint8_t state)
437
438
439
440
{
  tor_assert(circ);
  if (state == circ->state)
    return;
441
  if (PREDICT_UNLIKELY(!circuits_pending_chans))
442
    circuits_pending_chans = smartlist_new();
443
444
  if (PREDICT_UNLIKELY(!circuits_pending_other_guards))
    circuits_pending_other_guards = smartlist_new();
445
  if (circ->state == CIRCUIT_STATE_CHAN_WAIT) {
446
    /* remove from waiting-circuit list. */
447
    smartlist_remove(circuits_pending_chans, circ);
448
  }
449
  if (state == CIRCUIT_STATE_CHAN_WAIT) {
450
    /* add to waiting-circuit list. */
451
    smartlist_add(circuits_pending_chans, circ);
452
  }
453
454
455
456
457
458
459
  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)
460
    tor_assert(!circ->n_chan_create_cell);
461
  circ->state = state;
462
463
}

464
/** Append to <b>out</b> all circuits in state CHAN_WAIT waiting for
465
466
 * the given connection. */
void
467
circuit_get_all_pending_on_channel(smartlist_t *out, channel_t *chan)
468
469
{
  tor_assert(out);
470
  tor_assert(chan);
471

472
  if (!circuits_pending_chans)
473
474
    return;

475
  SMARTLIST_FOREACH_BEGIN(circuits_pending_chans, circuit_t *, circ) {
476
477
    if (circ->marked_for_close)
      continue;
478
479
    if (!circ->n_hop)
      continue;
480
    tor_assert(circ->state == CIRCUIT_STATE_CHAN_WAIT);
481
    if (tor_digest_is_zero(circ->n_hop->identity_digest)) {
482
      /* Look at addr/port. This is an unkeyed connection. */
483
      if (!channel_matches_extend_info(chan, circ->n_hop))
484
485
486
        continue;
    } else {
      /* We expected a key. See if it's the right one. */
487
488
      if (tor_memneq(chan->identity_digest,
                     circ->n_hop->identity_digest, DIGEST_LEN))
489
        continue;
490
    }
491
    smartlist_add(out, circ);
492
  } SMARTLIST_FOREACH_END(circ);
493
494
}

495
496
/** Return the number of circuits in state CHAN_WAIT, waiting for the given
 * channel. */
497
int
498
circuit_count_pending_on_channel(channel_t *chan)
499
500
{
  int cnt;
501
  smartlist_t *sl = smartlist_new();
502
503
504
505

  tor_assert(chan);

  circuit_get_all_pending_on_channel(sl, chan);
506
507
  cnt = smartlist_len(sl);
  smartlist_free(sl);
508
  log_debug(LD_CIRC,"or_conn to %s at %s, %d pending circs",
509
            chan->nickname ? chan->nickname : "NULL",
510
            channel_get_canonical_remote_descr(chan),
511
            cnt);
512
513
514
  return cnt;
}

515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
/** 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;
}

548
549
550
/** Detach from the global circuit list, and deallocate, all
 * circuits that have been marked for close.
 */
551
552
void
circuit_close_all_marked(void)
553
{
554
555
556
  if (circuits_pending_close == NULL)
    return;

557
  smartlist_t *lst = circuit_get_global_list();
558
559
560
561
562
563
564
565
566
  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;
567
    }
568
569
    circ->global_circuitlist_idx = -1;

570
571
    /* Remove it from the origin circuit list, if appropriate. */
    if (CIRCUIT_IS_ORIGIN(circ)) {
572
      circuit_remove_from_origin_circuit_list(TO_ORIGIN_CIRCUIT(circ));
573
574
    }

575
576
    circuit_about_to_free(circ);
    circuit_free(circ);
577
  } SMARTLIST_FOREACH_END(circ);
578
579

  smartlist_clear(circuits_pending_close);
580
581
}

582
/** Return a pointer to the global list of circuits. */
583
MOCK_IMPL(smartlist_t *,
584
circuit_get_global_list,(void))
585
{
586
587
588
  if (NULL == global_circuitlist)
    global_circuitlist = smartlist_new();
  return global_circuitlist;
589
590
}

591
592
593
594
595
596
/** 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();
597
  return global_origin_circuit_list;
598
599
}

600
601
/** Function to make circ-\>state human-readable */
const char *
602
603
circuit_state_to_string(int state)
{
Nick Mathewson's avatar
Nick Mathewson committed
604
  static char buf[64];
605
606
607
  switch (state) {
    case CIRCUIT_STATE_BUILDING: return "doing handshakes";
    case CIRCUIT_STATE_ONIONSKIN_PENDING: return "processing the onion";
608
    case CIRCUIT_STATE_CHAN_WAIT: return "connecting to server";
609
610
    case CIRCUIT_STATE_GUARD_WAIT: return "waiting to see how other "
      "guards perform";
611
612
    case CIRCUIT_STATE_OPEN: return "open";
    default:
613
      log_warn(LD_BUG, "Unknown circuit state %d", state);
614
      tor_snprintf(buf, sizeof(buf), "unknown state [%d]", state);
615
616
617
618
      return buf;
  }
}

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

    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";
655
    case CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT:
656
      return "MEASURE_TIMEOUT";
657
658
    case CIRCUIT_PURPOSE_CONTROLLER:
      return "CONTROLLER";
659
660
    case CIRCUIT_PURPOSE_PATH_BIAS_TESTING:
      return "PATH_BIAS_TESTING";
661
662
663
664
665
666
667

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

668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
/** 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:
688
    case CIRCUIT_PURPOSE_PATH_BIAS_TESTING:
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
      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";

    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";

    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";
    }
}

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
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
/** 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:
      return "Acting as rendevous (pending)";
    case CIRCUIT_PURPOSE_REND_ESTABLISHED:
      return "Acting as rendevous (established)";
    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";
    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";

    case CIRCUIT_PURPOSE_TESTING:
      return "Testing circuit";

    case CIRCUIT_PURPOSE_CONTROLLER:
      return "Circuit made by controller";

776
777
778
    case CIRCUIT_PURPOSE_PATH_BIAS_TESTING:
      return "Path-bias testing circuit";

779
780
781
782
783
784
    default:
      tor_snprintf(buf, sizeof(buf), "UNKNOWN_%d", (int)purpose);
      return buf;
  }
}

785
786
787
788
789
790
/** 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)
{
791
792
793
  int32_t num = networkstatus_get_param(NULL, "circwindow", CIRCWINDOW_START,
                                        CIRCWINDOW_START_MIN,
                                        CIRCWINDOW_START_MAX);
794
795
796
797
  /* If the consensus tells us a negative number, we'd assert. */
  if (num < 0)
    num = CIRCWINDOW_START;
  return num;
798
799
}

800
801
/** Initialize the common elements in a circuit_t, and add it to the global
 * list. */
802
803
static void
init_circuit_base(circuit_t *circ)
804
{
805
  tor_gettimeofday(&circ->timestamp_created);
806

807
808
809
810
811
  // 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;

812
  circ->package_window = circuit_initial_package_window();
813
  circ->deliver_window = CIRCWINDOW_START;
814
  cell_queue_init(&circ->n_chan_cells);
815

816
817
  smartlist_add(circuit_get_global_list(), circ);
  circ->global_circuitlist_idx = smartlist_len(circuit_get_global_list()) - 1;
818
819
}

820
821
822
823
824
/** If we haven't yet decided on a good timeout value for circuit
 * building, we close idle circuits aggressively so we can get more
 * data points. */
#define IDLE_TIMEOUT_WHILE_LEARNING (1*60)

825
826
827
828
829
830
831
/** Allocate space for a new circuit, initializing with <b>p_circ_id</b>
 * and <b>p_conn</b>. Add it to the global circuit list.
 */
origin_circuit_t *
origin_circuit_new(void)
{
  origin_circuit_t *circ;
832
833
834
  /* never zero, since a global ID of 0 is treated specially by the
   * controller */
  static uint32_t n_circuits_allocated = 1;
835
836

  circ = tor_malloc_zero(sizeof(origin_circuit_t));
837
  circ->base_.magic = ORIGIN_CIRCUIT_MAGIC;
838
839

  circ->next_stream_id = crypto_rand_int(1<<16);
840
  circ->global_identifier = n_circuits_allocated++;
841
842
  circ->remaining_relay_early_cells = MAX_RELAY_EARLY_CELLS_PER_CIRCUIT;
  circ->remaining_relay_early_cells -= crypto_rand_int(2);
843
844
845

  init_circuit_base(TO_CIRCUIT(circ));

846
  /* Add to origin-list. */
847
848
  circ->global_origin_circuit_list_idx = -1;
  circuit_add_to_origin_circuit_list(circ);
849

850
  circuit_build_times_update_last_circ(get_circuit_build_times_mutable());
Mike Perry's avatar
Mike Perry committed
851

852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
  if (! circuit_build_times_disabled(get_options()) &&
      circuit_build_times_needs_circuits(get_circuit_build_times())) {
    /* Circuits should be shorter lived if we need more of them
     * for learning a good build timeout */
    circ->circuit_idle_timeout = IDLE_TIMEOUT_WHILE_LEARNING;
  } else {
    // This should always be larger than the current port prediction time
    // remaining, or else we'll end up with the case where a circuit times out
    // and another one is built, effectively doubling the timeout window.
    //
    // We also randomize it by up to 5% more (ie 5% of 0 to 3600 seconds,
    // depending on how much circuit prediction time is remaining) so that
    // we don't close a bunch of unused circuits all at the same time.
    int prediction_time_remaining =
      predicted_ports_prediction_time_remaining(time(NULL));
    circ->circuit_idle_timeout = prediction_time_remaining+1+
        crypto_rand_int(1+prediction_time_remaining/20);

    if (circ->circuit_idle_timeout <= 0) {
      log_warn(LD_BUG,
               "Circuit chose a negative idle timeout of %d based on "
               "%d seconds of predictive building remaining.",
               circ->circuit_idle_timeout,
               prediction_time_remaining);
      circ->circuit_idle_timeout = IDLE_TIMEOUT_WHILE_LEARNING;
    }

    log_info(LD_CIRC,
              "Circuit " U64_FORMAT " chose an idle timeout of %d based on "
              "%d seconds of predictive building remaining.",
              U64_PRINTF_ARG(circ->global_identifier),
              circ->circuit_idle_timeout,
              prediction_time_remaining);
  }

887
888
889
  return circ;
}

890
891
/** Allocate a new or_circuit_t, connected to <b>p_chan</b> as
 * <b>p_circ_id</b>.  If <b>p_chan</b> is NULL, the circuit is unattached. */
892
or_circuit_t *
893
or_circuit_new(circid_t p_circ_id, channel_t *p_chan)
894
895
896
897
898
{
  /* CircIDs */
  or_circuit_t *circ;

  circ = tor_malloc_zero(sizeof(or_circuit_t));
899
  circ->base_.magic = OR_CIRCUIT_MAGIC;
900

901
902
  if (p_chan)
    circuit_set_p_circid_chan(circ, p_circ_id, p_chan);
903

904
  circ->remaining_relay_early_cells = MAX_RELAY_EARLY_CELLS_PER_CIRCUIT;
905
  cell_queue_init(&circ->p_chan_cells);
906

907
  init_circuit_base(TO_CIRCUIT(circ));
908
909
910
911

  return circ;
}

912
913
914
915
/** Free all storage held in circ->testing_cell_stats */
void
circuit_clear_testing_cell_stats(circuit_t *circ)
{
916
  if (!circ || !circ->testing_cell_stats)
917
918
919
920
921
922
923
    return;
  SMARTLIST_FOREACH(circ->testing_cell_stats, testing_cell_stats_entry_t *,
                    ent, tor_free(ent));
  smartlist_free(circ->testing_cell_stats);
  circ->testing_cell_stats = NULL;
}

924
925
/** Deallocate space associated with circ.
 */
926
STATIC void
927
circuit_free_(circuit_t *circ)
928
{
929
  circid_t n_circ_id = 0;
930
  void *mem;
931
  size_t memlen;
932
  int should_free = 1;
933
934
935
  if (!circ)
    return;

936
937
938
  /* We keep a copy of this so we can log its value before it gets unset. */
  n_circ_id = circ->n_circ_id;

939
940
  circuit_clear_testing_cell_stats(circ);

941
942
943
  if (CIRCUIT_IS_ORIGIN(circ)) {
    origin_circuit_t *ocirc = TO_ORIGIN_CIRCUIT(circ);
    mem = ocirc;
944
    memlen = sizeof(origin_circuit_t);
945
    tor_assert(circ->magic == ORIGIN_CIRCUIT_MAGIC);
946

947
    circuit_remove_from_origin_circuit_list(ocirc);
948

949
950
951
    if (ocirc->build_state) {
        extend_info_free(ocirc->build_state->chosen_exit);
        circuit_free_cpath_node(ocirc->build_state->pending_final_cpath);
952
        cpath_ref_decref(ocirc->build_state->service_pending_final_cpath_ref);
953
954
955
    }
    tor_free(ocirc->build_state);

956
957
    /* Cancel before freeing, if we haven't already succeeded or failed. */
    if (ocirc->guard_state) {
958
      entry_guard_cancel(&ocirc->guard_state);
959
    }
960
    circuit_guard_state_free(ocirc->guard_state);
961

962
    circuit_clear_cpath(ocirc);
963

964
    crypto_pk_free(ocirc->intro_key);
965
    rend_data_free(ocirc->rend_data);
966
    hs_ident_circuit_free(ocirc->hs_ident);
967
968

    tor_free(ocirc->dest_address);
969
    if (ocirc->socks_username) {
970
      memwipe(ocirc->socks_username, 0x12, ocirc->socks_username_len);
971
972
973
      tor_free(ocirc->socks_username);
    }
    if (ocirc->socks_password) {
974
      memwipe(ocirc->socks_password, 0x06, ocirc->socks_password_len);
975
976
      tor_free(ocirc->socks_password);
    }
977
    addr_policy_list_free(ocirc->prepend_policy);
978
979
  } else {
    or_circuit_t *ocirc = TO_OR_CIRCUIT(circ);
980
981
    /* Remember cell statistics for this circuit before deallocating. */
    if (get_options()->CellStatistics)
982
      rep_hist_buffer_stats_add_circ(circ, time(NULL));
983
    mem = ocirc;
984
    memlen = sizeof(or_circuit_t);
985
986
    tor_assert(circ->magic == OR_CIRCUIT_MAGIC);

987
988
    should_free = (ocirc->workqueue_entry == NULL);

989
990
991
992
    crypto_cipher_free(ocirc->p_crypto);
    crypto_digest_free(ocirc->p_digest);
    crypto_cipher_free(ocirc->n_crypto);
    crypto_digest_free(ocirc->n_digest);
993
994
995

    if (ocirc->rend_splice) {
      or_circuit_t *other = ocirc->rend_splice;
996
      tor_assert(other->base_.magic == OR_CIRCUIT_MAGIC);
997
998
999
1000
      other->rend_splice = NULL;
    }

    /* remove from map. */