circuitlist.c 72.1 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-2013, The Tor Project, Inc. */
5
6
7
8
9
10
/* See LICENSE for licensing information */

/**
 * \file circuitlist.c
 * \brief Manage the global circuit list.
 **/
11
#define CIRCUITLIST_PRIVATE
12
#include "or.h"
13
#include "channel.h"
14
#include "circpathbias.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
15
#include "circuitbuild.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
16
#include "circuitlist.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
17
#include "circuituse.h"
18
#include "circuitstats.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
19
#include "connection.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
20
#include "config.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
21
#include "connection_edge.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
22
#include "connection_or.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
23
#include "control.h"
24
#include "main.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
25
#include "networkstatus.h"
26
#include "nodelist.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
27
#include "onion.h"
28
#include "onion_fast.h"
29
#include "policies.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
30
#include "relay.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
31
#include "rendclient.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
32
#include "rendcommon.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
33
#include "rephist.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
34
#include "routerlist.h"
35
#include "routerset.h"
36

37
#include "ht.h"
38
39
40

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

41
/** A global list of all circuits at this hop. */
42
static smartlist_t *global_circuitlist = NULL;
43

44
45
/** A list of all the circuits in CIRCUIT_STATE_CHAN_WAIT. */
static smartlist_t *circuits_pending_chans = NULL;
46

47
static void circuit_free_cpath_node(crypt_path_t *victim);
48
static void cpath_ref_decref(crypt_path_reference_t *cpath_ref);
49
50
51
//static void circuit_set_rend_token(or_circuit_t *circ, int is_rend_circ,
//                                   const uint8_t *token);
static void circuit_clear_rend_token(or_circuit_t *circ);
52

53
54
/********* END VARIABLES ************/

55
/** A map from channel and circuit ID to circuit.  (Lookup performance is
56
 * very important here, since we need to do it every time a cell arrives.) */
57
58
59
typedef struct chan_circid_circuit_map_t {
  HT_ENTRY(chan_circid_circuit_map_t) node;
  channel_t *chan;
60
  circid_t circ_id;
61
  circuit_t *circuit;
Nick Mathewson's avatar
Nick Mathewson committed
62
63
  /* For debugging 12184: when was this placeholder item added? */
  time_t made_placeholder_at;
64
} chan_circid_circuit_map_t;
65

66
/** Helper for hash tables: compare the channel and circuit ID for a and
67
 * b, and return less than, equal to, or greater than zero appropriately.
68
 */
69
static INLINE int
70
chan_circid_entries_eq_(chan_circid_circuit_map_t *a,
71
                        chan_circid_circuit_map_t *b)
72
{
73
  return a->chan == b->chan && a->circ_id == b->circ_id;
74
75
}

76
/** Helper: return a hash based on circuit ID and the pointer value of
77
 * chan in <b>a</b>. */
78
static INLINE unsigned int
79
chan_circid_entry_hash_(chan_circid_circuit_map_t *a)
80
{
81
82
83
84
85
86
87
88
89
  /* 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));
90
91
}

92
93
94
95
/** 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,
96
             chan_circid_entry_hash_, chan_circid_entries_eq_)
97
98
99
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_)
100

101
/** The most recently returned entry from circuit_get_by_circid_chan;
102
103
 * used to improve performance when many cells arrive in a row from the
 * same circuit.
104
 */
105
chan_circid_circuit_map_t *_last_circid_chan_ent = NULL;
106

107
108
109
/** 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
110
 * the old entry (if any) and adding a new one. */
111
static void
112
113
114
circuit_set_circid_chan_helper(circuit_t *circ, int direction,
                               circid_t id,
                               channel_t *chan)
115
{
116
117
118
  chan_circid_circuit_map_t search;
  chan_circid_circuit_map_t *found;
  channel_t *old_chan, **chan_ptr;
119
  circid_t old_id, *circid_ptr;
120
  int make_active, attached = 0;
121
122

  if (direction == CELL_DIRECTION_OUT) {
123
    chan_ptr = &circ->n_chan;
124
    circid_ptr = &circ->n_circ_id;
125
    make_active = circ->n_chan_cells.n > 0;
126
127
  } else {
    or_circuit_t *c = TO_OR_CIRCUIT(circ);
128
    chan_ptr = &c->p_chan;
129
    circid_ptr = &c->p_circ_id;
130
    make_active = c->p_chan_cells.n > 0;
131
  }
132
  old_chan = *chan_ptr;
133
134
  old_id = *circid_ptr;

135
  if (id == old_id && chan == old_chan)
136
    return;
137

138
139
140
141
142
143
  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;
144
145
  }

146
147
148
  if (old_chan) {
    /*
     * If we're changing channels or ID and had an old channel and a non
149
150
151
     * 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).
152
     */
153
    if (old_id != 0 && (old_chan != chan || old_id != id) &&
154
        !(circ->marked_for_close)) {
155
156
157
158
159
      tor_assert(old_chan->cmux);
      circuitmux_detach_circuit(old_chan->cmux, circ);
    }

    /* we may need to remove it from the conn-circid map */
160
    search.circ_id = old_id;
161
162
    search.chan = old_chan;
    found = HT_REMOVE(chan_circid_map, &chan_circid_map, &search);
163
    if (found) {
164
      tor_free(found);
165
166
167
168
169
170
171
172
      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);
      }
    }
173
174
  }

175
  /* Change the values only after we have possibly made the circuit inactive
176
177
   * on the previous chan. */
  *chan_ptr = chan;
178
179
  *circid_ptr = id;

180
  if (chan == NULL)
181
182
    return;

183
  /* now add the new one to the conn-circid map */
184
  search.circ_id = id;
185
186
  search.chan = chan;
  found = HT_FIND(chan_circid_map, &chan_circid_map, &search);
187
188
  if (found) {
    found->circuit = circ;
Nick Mathewson's avatar
Nick Mathewson committed
189
    found->made_placeholder_at = 0;
190
  } else {
191
    found = tor_malloc_zero(sizeof(chan_circid_circuit_map_t));
192
    found->circ_id = id;
193
    found->chan = chan;
194
    found->circuit = circ;
195
    HT_INSERT(chan_circid_map, &chan_circid_map, found);
196
  }
197

198
199
  /*
   * Attach to the circuitmux if we're changing channels or IDs and
200
201
   * have a new channel and ID to use and the circuit is not marked for
   * close.
202
   */
203
204
  if (chan && id != 0 && (old_chan != chan || old_id != id) &&
      !(circ->marked_for_close)) {
205
206
    tor_assert(chan->cmux);
    circuitmux_attach_circuit(chan->cmux, circ, direction);
207
    attached = 1;
208
209
210
211
212
213
  }

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

217
218
219
220
221
222
  /* Adjust circuit counts on new channel */
  if (direction == CELL_DIRECTION_OUT) {
    ++chan->num_n_circuits;
  } else {
    ++chan->num_p_circuits;
  }
223
224
}

225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
/** 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
247
248
    if (!ent->made_placeholder_at)
      ent->made_placeholder_at = approx_time();
249
250
251
252
  } 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
253
254
    /* leave circuit at NULL. */
    ent->made_placeholder_at = approx_time();
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
    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);
}

283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
/** 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. */
void
channel_note_destroy_not_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 = 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);
}

324
325
/** Set the p_conn field of a circuit <b>circ</b>, along
 * with the corresponding circuit ID, and add the circuit as appropriate
326
 * to the (chan,id)-\>circuit map. */
327
void
328
circuit_set_p_circid_chan(or_circuit_t *or_circ, circid_t id,
329
                          channel_t *chan)
330
{
331
332
333
334
335
  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);
336

337
  if (chan) {
338
339
340
    tor_assert(bool_eq(or_circ->p_chan_cells.n,
                       or_circ->next_active_on_p_chan));

341
342
    chan->timestamp_last_had_circuits = approx_time();
  }
343

344
345
346
347
  if (circ->p_delete_pending && old_chan) {
    channel_mark_circid_unusable(old_chan, old_id);
    circ->p_delete_pending = 0;
  }
348
349
350
351
}

/** Set the n_conn field of a circuit <b>circ</b>, along
 * with the corresponding circuit ID, and add the circuit as appropriate
352
 * to the (chan,id)-\>circuit map. */
353
void
354
355
circuit_set_n_circid_chan(circuit_t *circ, circid_t id,
                          channel_t *chan)
356
{
357
358
359
  channel_t *old_chan = circ->n_chan;
  circid_t old_id = circ->n_circ_id;

360
  circuit_set_circid_chan_helper(circ, CELL_DIRECTION_OUT, id, chan);
361

362
  if (chan) {
363
    tor_assert(bool_eq(circ->n_chan_cells.n, circ->next_active_on_n_chan));
364

365
366
    chan->timestamp_last_had_circuits = approx_time();
  }
367

368
369
  if (circ->n_delete_pending && old_chan) {
    channel_mark_circid_unusable(old_chan, old_id);
370
    circ->n_delete_pending = 0;
371
  }
372
373
}

374
375
/** Change the state of <b>circ</b> to <b>state</b>, adding it to or removing
 * it from lists as appropriate. */
376
void
377
circuit_set_state(circuit_t *circ, uint8_t state)
378
379
380
381
{
  tor_assert(circ);
  if (state == circ->state)
    return;
382
383
384
  if (!circuits_pending_chans)
    circuits_pending_chans = smartlist_new();
  if (circ->state == CIRCUIT_STATE_CHAN_WAIT) {
385
    /* remove from waiting-circuit list. */
386
    smartlist_remove(circuits_pending_chans, circ);
387
  }
388
  if (state == CIRCUIT_STATE_CHAN_WAIT) {
389
    /* add to waiting-circuit list. */
390
    smartlist_add(circuits_pending_chans, circ);
391
  }
392
  if (state == CIRCUIT_STATE_OPEN)
393
    tor_assert(!circ->n_chan_create_cell);
394
  circ->state = state;
395
396
}

397
/** Append to <b>out</b> all circuits in state CHAN_WAIT waiting for
398
399
 * the given connection. */
void
400
circuit_get_all_pending_on_channel(smartlist_t *out, channel_t *chan)
401
402
{
  tor_assert(out);
403
  tor_assert(chan);
404

405
  if (!circuits_pending_chans)
406
407
    return;

408
  SMARTLIST_FOREACH_BEGIN(circuits_pending_chans, circuit_t *, circ) {
409
410
    if (circ->marked_for_close)
      continue;
411
412
    if (!circ->n_hop)
      continue;
413
    tor_assert(circ->state == CIRCUIT_STATE_CHAN_WAIT);
414
    if (tor_digest_is_zero(circ->n_hop->identity_digest)) {
415
      /* Look at addr/port. This is an unkeyed connection. */
416
      if (!channel_matches_extend_info(chan, circ->n_hop))
417
418
419
        continue;
    } else {
      /* We expected a key. See if it's the right one. */
420
421
      if (tor_memneq(chan->identity_digest,
                     circ->n_hop->identity_digest, DIGEST_LEN))
422
        continue;
423
    }
424
    smartlist_add(out, circ);
425
  } SMARTLIST_FOREACH_END(circ);
426
427
}

428
429
/** Return the number of circuits in state CHAN_WAIT, waiting for the given
 * channel. */
430
int
431
circuit_count_pending_on_channel(channel_t *chan)
432
433
{
  int cnt;
434
  smartlist_t *sl = smartlist_new();
435
436
437
438

  tor_assert(chan);

  circuit_get_all_pending_on_channel(sl, chan);
439
440
  cnt = smartlist_len(sl);
  smartlist_free(sl);
441
  log_debug(LD_CIRC,"or_conn to %s at %s, %d pending circs",
442
            chan->nickname ? chan->nickname : "NULL",
443
            channel_get_canonical_remote_descr(chan),
444
            cnt);
445
446
447
  return cnt;
}

448
449
450
/** Detach from the global circuit list, and deallocate, all
 * circuits that have been marked for close.
 */
451
452
void
circuit_close_all_marked(void)
453
{
454
455
456
457
458
459
  smartlist_t *lst = circuit_get_global_list();
  SMARTLIST_FOREACH_BEGIN(lst, circuit_t *, circ) {
    /* Fix up index if SMARTLIST_DEL_CURRENT just moved this one. */
    circ->global_circuitlist_idx = circ_sl_idx;
    if (circ->marked_for_close) {
      circ->global_circuitlist_idx = -1;
460
      circuit_free(circ);
461
462
463
      SMARTLIST_DEL_CURRENT(lst, circ);
    }
  } SMARTLIST_FOREACH_END(circ);
464
465
}

466
/** Return the head of the global linked list of circuits. */
467
MOCK_IMPL(smartlist_t *,
468
circuit_get_global_list,(void))
469
{
470
471
472
  if (NULL == global_circuitlist)
    global_circuitlist = smartlist_new();
  return global_circuitlist;
473
474
}

475
476
/** Function to make circ-\>state human-readable */
const char *
477
478
circuit_state_to_string(int state)
{
Nick Mathewson's avatar
Nick Mathewson committed
479
  static char buf[64];
480
481
482
  switch (state) {
    case CIRCUIT_STATE_BUILDING: return "doing handshakes";
    case CIRCUIT_STATE_ONIONSKIN_PENDING: return "processing the onion";
483
    case CIRCUIT_STATE_CHAN_WAIT: return "connecting to server";
484
485
    case CIRCUIT_STATE_OPEN: return "open";
    default:
486
      log_warn(LD_BUG, "Unknown circuit state %d", state);
487
      tor_snprintf(buf, sizeof(buf), "unknown state [%d]", state);
488
489
490
491
      return buf;
  }
}

492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
/** 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";
507
    case CIRCUIT_PURPOSE_C_INTRODUCING:
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
    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";
528
    case CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT:
529
      return "MEASURE_TIMEOUT";
530
531
    case CIRCUIT_PURPOSE_CONTROLLER:
      return "CONTROLLER";
532
533
    case CIRCUIT_PURPOSE_PATH_BIAS_TESTING:
      return "PATH_BIAS_TESTING";
534
535
536
537
538
539
540

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

541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
/** 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:
561
    case CIRCUIT_PURPOSE_PATH_BIAS_TESTING:
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
      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";
    }
}

599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
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
/** 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";

649
650
651
    case CIRCUIT_PURPOSE_PATH_BIAS_TESTING:
      return "Path-bias testing circuit";

652
653
654
655
656
657
    default:
      tor_snprintf(buf, sizeof(buf), "UNKNOWN_%d", (int)purpose);
      return buf;
  }
}

658
659
660
661
662
663
/** 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)
{
664
665
666
  int32_t num = networkstatus_get_param(NULL, "circwindow", CIRCWINDOW_START,
                                        CIRCWINDOW_START_MIN,
                                        CIRCWINDOW_START_MAX);
667
668
669
670
  /* If the consensus tells us a negative number, we'd assert. */
  if (num < 0)
    num = CIRCWINDOW_START;
  return num;
671
672
}

673
674
/** Initialize the common elements in a circuit_t, and add it to the global
 * list. */
675
676
static void
init_circuit_base(circuit_t *circ)
677
{
678
  tor_gettimeofday(&circ->timestamp_created);
679

680
681
682
683
684
  // 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;

685
  circ->package_window = circuit_initial_package_window();
686
  circ->deliver_window = CIRCWINDOW_START;
687
  cell_queue_init(&circ->n_chan_cells);
688

689
690
  smartlist_add(circuit_get_global_list(), circ);
  circ->global_circuitlist_idx = smartlist_len(circuit_get_global_list()) - 1;
691
692
693
694
695
696
697
698
699
}

/** 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;
700
701
702
  /* never zero, since a global ID of 0 is treated specially by the
   * controller */
  static uint32_t n_circuits_allocated = 1;
703
704

  circ = tor_malloc_zero(sizeof(origin_circuit_t));
705
  circ->base_.magic = ORIGIN_CIRCUIT_MAGIC;
706
707

  circ->next_stream_id = crypto_rand_int(1<<16);
708
  circ->global_identifier = n_circuits_allocated++;
709
710
  circ->remaining_relay_early_cells = MAX_RELAY_EARLY_CELLS_PER_CIRCUIT;
  circ->remaining_relay_early_cells -= crypto_rand_int(2);
711
712
713

  init_circuit_base(TO_CIRCUIT(circ));

714
  circuit_build_times_update_last_circ(get_circuit_build_times_mutable());
Mike Perry's avatar
Mike Perry committed
715

716
717
718
  return circ;
}

719
720
/** Allocate a new or_circuit_t, connected to <b>p_conn</b> as
 * <b>p_circ_id</b>.  If <b>p_conn</b> is NULL, the circuit is unattached. */
721
or_circuit_t *
722
or_circuit_new(circid_t p_circ_id, channel_t *p_chan)
723
724
725
726
727
{
  /* CircIDs */
  or_circuit_t *circ;

  circ = tor_malloc_zero(sizeof(or_circuit_t));
728
  circ->base_.magic = OR_CIRCUIT_MAGIC;
729

730
731
  if (p_chan)
    circuit_set_p_circid_chan(circ, p_circ_id, p_chan);
732

733
  circ->remaining_relay_early_cells = MAX_RELAY_EARLY_CELLS_PER_CIRCUIT;
734
  cell_queue_init(&circ->p_chan_cells);
735

736
  init_circuit_base(TO_CIRCUIT(circ));
737
738
739
740
741
742

  return circ;
}

/** Deallocate space associated with circ.
 */
743
STATIC void
744
745
circuit_free(circuit_t *circ)
{
746
  void *mem;
747
  size_t memlen;
748
749
750
  if (!circ)
    return;

751
752
753
  if (CIRCUIT_IS_ORIGIN(circ)) {
    origin_circuit_t *ocirc = TO_ORIGIN_CIRCUIT(circ);
    mem = ocirc;
754
    memlen = sizeof(origin_circuit_t);
755
756
757
758
    tor_assert(circ->magic == ORIGIN_CIRCUIT_MAGIC);
    if (ocirc->build_state) {
        extend_info_free(ocirc->build_state->chosen_exit);
        circuit_free_cpath_node(ocirc->build_state->pending_final_cpath);
759
        cpath_ref_decref(ocirc->build_state->service_pending_final_cpath_ref);
760
761
762
    }
    tor_free(ocirc->build_state);

763
    circuit_clear_cpath(ocirc);
764

765
    crypto_pk_free(ocirc->intro_key);
766
    rend_data_free(ocirc->rend_data);
767
768

    tor_free(ocirc->dest_address);
769
    if (ocirc->socks_username) {
770
      memwipe(ocirc->socks_username, 0x12, ocirc->socks_username_len);
771
772
773
      tor_free(ocirc->socks_username);
    }
    if (ocirc->socks_password) {
774
      memwipe(ocirc->socks_password, 0x06, ocirc->socks_password_len);
775
776
      tor_free(ocirc->socks_password);
    }
777
    addr_policy_list_free(ocirc->prepend_policy);
778
779
  } else {
    or_circuit_t *ocirc = TO_OR_CIRCUIT(circ);
780
781
    /* Remember cell statistics for this circuit before deallocating. */
    if (get_options()->CellStatistics)
782
      rep_hist_buffer_stats_add_circ(circ, time(NULL));
783
    mem = ocirc;
784
    memlen = sizeof(or_circuit_t);
785
786
    tor_assert(circ->magic == OR_CIRCUIT_MAGIC);

787
788
789
790
    crypto_cipher_free(ocirc->p_crypto);
    crypto_digest_free(ocirc->p_digest);
    crypto_cipher_free(ocirc->n_crypto);
    crypto_digest_free(ocirc->n_digest);
791

792
793
    circuit_clear_rend_token(ocirc);

794
795
    if (ocirc->rend_splice) {
      or_circuit_t *other = ocirc->rend_splice;
796
      tor_assert(other->base_.magic == OR_CIRCUIT_MAGIC);
797
798
799
800
      other->rend_splice = NULL;
    }

    /* remove from map. */
801
    circuit_set_p_circid_chan(ocirc, 0, NULL);
802

803
804
    /* Clear cell queue _after_ removing it from the map.  Otherwise our
     * "active" checks will be violated. */
805
    cell_queue_clear(&ocirc->p_chan_cells);
806
  }
807

808
  extend_info_free(circ->n_hop);
809
  tor_free(circ->n_chan_create_cell);
810

811
812
813
814
815
816
817
818
819
820
  if (circ->global_circuitlist_idx != -1) {
    int idx = circ->global_circuitlist_idx;
    circuit_t *c2 = smartlist_get(global_circuitlist, idx);
    tor_assert(c2 == circ);
    smartlist_del(global_circuitlist, idx);
    if (idx < smartlist_len(global_circuitlist)) {
      c2 = smartlist_get(global_circuitlist, idx);
      c2->global_circuitlist_idx = idx;
    }
  }
821

822
  /* Remove from map. */
823
  circuit_set_n_circid_chan(circ, 0, NULL);
824

825
826
  /* Clear cell queue _after_ removing it from the map.  Otherwise our
   * "active" checks will be violated. */
827
  cell_queue_clear(&circ->n_chan_cells);
828

829
  memwipe(mem, 0xAA, memlen); /* poison memory */
830
  tor_free(mem);
831
832
}

833
834
835
836
/** Deallocate the linked list circ-><b>cpath</b>, and remove the cpath from
 * <b>circ</b>. */
void
circuit_clear_cpath(origin_circuit_t *circ)
837
{
838
839
840
  crypt_path_t *victim, *head, *cpath;

  head = cpath = circ->cpath;
841

842
  if (!cpath)
843
844
    return;

845
  /* it's a circular list, so we have to notice when we've
846
   * gone through it once. */
847
  while (cpath->next && cpath->next != head) {
848
849
850
851
852
853
854
    victim = cpath;
    cpath = victim->next;
    circuit_free_cpath_node(victim);
  }

  circuit_free_cpath_node(cpath);

855
856
857
  circ->cpath = NULL;
}

858
859
860
861
/** Release all storage held by circuits. */
void
circuit_free_all(void)
{
862
  smartlist_t *lst = circuit_get_global_list();
863

864
  SMARTLIST_FOREACH_BEGIN(lst, circuit_t *, tmp) {
865
866
    if (! CIRCUIT_IS_ORIGIN(tmp)) {
      or_circuit_t *or_circ = TO_OR_CIRCUIT(tmp);
867
      while (or_circ->resolving_streams) {
868
869
        edge_connection_t *next_conn;
        next_conn = or_circ->resolving_streams->next_stream;
870
        connection_free(TO_CONN(or_circ->resolving_streams));
871
        or_circ->resolving_streams = next_conn;
872
      }
873
    }
874
    tmp->global_circuitlist_idx = -1;
875
    circuit_free(tmp);
876
877
878
879
880
    SMARTLIST_DEL_CURRENT(lst, tmp);
  } SMARTLIST_FOREACH_END(tmp);

  smartlist_free(lst);
  global_circuitlist = NULL;
881

882
883
  smartlist_free(circuits_pending_chans);
  circuits_pending_chans = NULL;
884

885
886
887
888
889
890
891
892
893
894
895
896
  {
    chan_circid_circuit_map_t **elt, **next, *c;
    for (elt = HT_START(chan_circid_map, &chan_circid_map);
         elt;
         elt = next) {
      c = *elt;
      next = HT_NEXT_RMV(chan_circid_map, &chan_circid_map, elt);

      tor_assert(c->circuit == NULL);
      tor_free(c);
    }
  }
897
  HT_CLEAR(chan_circid_map, &chan_circid_map);
898
899
}

900
/** Deallocate space associated with the cpath node <b>victim</b>. */
901
static void
902
903
circuit_free_cpath_node(crypt_path_t *victim)
{
904
905
906
  if (!victim)
    return;

907
908
909
910
  crypto_cipher_free(victim->f_crypto);
  crypto_cipher_free(victim->b_crypto);
  crypto_digest_free(victim->f_digest);
  crypto_digest_free(victim->b_digest);
911
912
  onion_handshake_state_release(&victim->handshake_state);
  crypto_dh_free(victim->rend_dh_handshake_state);
913
  extend_info_free(victim->extend_info);
914

915
  memwipe(victim, 0xBB, sizeof(crypt_path_t)); /* poison memory */
Roger Dingledine's avatar
Roger Dingledine committed
916
  tor_free(victim);
917
918
}

919
920
921
922
923
924
925
926
927
928
929
930
/** Release a crypt_path_reference_t*, which may be NULL. */
static void
cpath_ref_decref(crypt_path_reference_t *cpath_ref)
{
  if (cpath_ref != NULL) {
    if (--(cpath_ref->refcount) == 0) {
      circuit_free_cpath_node(cpath_ref->cpath);
      tor_free(cpath_ref);
    }
  }
}

931
932
933
934
/** A helper function for circuit_dump_by_conn() below. Log a bunch
 * of information about circuit <b>circ</b>.
 */
static void
935
936
937
938
circuit_dump_conn_details(int severity,
                          circuit_t *circ,
                          int conn_array_index,
                          const char *type,
939
940
                          circid_t this_circid,
                          circid_t other_circid)
941
{
942
943
944
945
  tor_log(severity, LD_CIRC, "Conn %d has %s circuit: circID %u "
      "(other side %u), state %d (%s), born %ld:",
      conn_array_index, type, (unsigned)this_circid, (unsigned)other_circid,
      circ->state, circuit_state_to_string(circ->state),
946
      (long)circ->timestamp_began.tv_sec);
947
948
949
950
951
952
953
954
955
956
957
  if (CIRCUIT_IS_ORIGIN(circ)) { /* circ starts at this node */
    circuit_log_path(severity, LD_CIRC, TO_ORIGIN_CIRCUIT(circ));
  }
}

/** Log, at severity <b>severity</b>, information about each circuit
 * that is connected to <b>conn</b>.
 */
void
circuit_dump_by_conn(connection_t *conn, int severity)
{
958
  edge_connection_t *tmpconn;
959

960
  SMARTLIST_FOREACH_BEGIN(circuit_get_global_list(), circuit_t *, circ) {
961
    circid_t n_circ_id = circ->n_circ_id, p_circ_id = 0;
962
963

    if (circ->marked_for_close) {
964
      continue;
965
    }
966

967
    if (!CIRCUIT_IS_ORIGIN(circ)) {
968
      p_circ_id = TO_OR_CIRCUIT(circ)->p_circ_id;
969
    }
970
971
972
973

    if (CIRCUIT_IS_ORIGIN(circ)) {
      for (tmpconn=TO_ORIGIN_CIRCUIT(circ)->p_streams; tmpconn;
           tmpconn=tmpconn->next_stream) {
974
        if (TO_CONN(tmpconn) == conn) {
975
976
          circuit_dump_conn_details(severity, circ, conn->conn_array_index,
                                    "App-ward", p_circ_id, n_circ_id);
977
978
979
        }
      }
    }
980

981
982
983
    if (! CIRCUIT_IS_ORIGIN(circ)) {
      for (tmpconn=TO_OR_CIRCUIT(circ)->n_streams; tmpconn;
           tmpconn=tmpconn->next_stream) {
984
        if (TO_CONN(tmpconn) == conn) {
985
986
          circuit_dump_conn_details(severity, circ, conn->conn_array_index,
                                    "Exit-ward", n_circ_id, p_circ_id);
987
988
989
        }
      }
    }
990
  }
991
  SMARTLIST_FOREACH_END(circ);
992
993
}

994
995
/** Return the circuit whose global ID is <b>id</b>, or NULL if no
 * such circuit exists. */
996
origin_circuit_t *
997
998
circuit_get_by_global_id(uint32_t id)
{
999
  SMARTLIST_FOREACH_BEGIN(circuit_get_global_list(), circuit_t *, circ) {
1000
    if (CIRCUIT_IS_ORIGIN(circ) &&