circuitlist.c 40.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.
Karsten Loesing's avatar
Karsten Loesing committed
4
 * Copyright (c) 2007-2009, The Tor Project, Inc. */
5
6
7
8
9
10
11
12
/* See LICENSE for licensing information */

/**
 * \file circuitlist.c
 * \brief Manage the global circuit list.
 **/

#include "or.h"
13
#include "ht.h"
14
15
16

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

17
18
/** A global list of all circuits at this hop. */
circuit_t *global_circuitlist=NULL;
19

20
/** A list of all the circuits in CIRCUIT_STATE_OR_WAIT. */
21
static smartlist_t *circuits_pending_or_conns=NULL;
22

23
24
static void circuit_free(circuit_t *circ);
static void circuit_free_cpath(crypt_path_t *cpath);
25
static void circuit_free_cpath_node(crypt_path_t *victim);
26

27
28
/********* END VARIABLES ************/

29
30
/** A map from OR connection and circuit ID to circuit.  (Lookup performance is
 * very important here, since we need to do it every time a cell arrives.) */
31
typedef struct orconn_circid_circuit_map_t {
32
  HT_ENTRY(orconn_circid_circuit_map_t) node;
33
  or_connection_t *or_conn;
34
  circid_t circ_id;
35
  circuit_t *circuit;
36
} orconn_circid_circuit_map_t;
37

38
39
/** Helper for hash tables: compare the OR connection and circuit ID for a and
 * b, and return less than, equal to, or greater than zero appropriately.
40
 */
41
static INLINE int
42
43
44
45
46
47
_orconn_circid_entries_eq(orconn_circid_circuit_map_t *a,
                          orconn_circid_circuit_map_t *b)
{
  return a->or_conn == b->or_conn && a->circ_id == b->circ_id;
}

48
49
/** Helper: return a hash based on circuit ID and the pointer value of
 * or_conn in <b>a</b>. */
50
51
static INLINE unsigned int
_orconn_circid_entry_hash(orconn_circid_circuit_map_t *a)
52
{
53
  return (((unsigned)a->circ_id)<<8) ^ (unsigned)(uintptr_t)(a->or_conn);
54
55
}

56
/** Map from [orconn,circid] to circuit. */
57
58
static HT_HEAD(orconn_circid_map, orconn_circid_circuit_map_t)
     orconn_circid_circuit_map = HT_INITIALIZER();
59
HT_PROTOTYPE(orconn_circid_map, orconn_circid_circuit_map_t, node,
60
             _orconn_circid_entry_hash, _orconn_circid_entries_eq)
61
HT_GENERATE(orconn_circid_map, orconn_circid_circuit_map_t, node,
62
            _orconn_circid_entry_hash, _orconn_circid_entries_eq, 0.6,
63
            malloc, realloc, free)
64

65
66
67
/** The most recently returned entry from circuit_get_by_circid_orconn;
 * used to improve performance when many cells arrive in a row from the
 * same circuit.
68
 */
69
orconn_circid_circuit_map_t *_last_circid_orconn_ent = NULL;
70

71
72
73
/** Implementation helper for circuit_set_{p,n}_circid_orconn: A circuit ID
 * and/or or_connection for circ has just changed from <b>old_conn, old_id</b>
 * to <b>conn, id</b>.  Adjust the conn,circid map as appropriate, removing
74
 * the old entry (if any) and adding a new one.  If <b>active</b> is true,
75
 * remove the circuit from the list of active circuits on old_conn and add it
76
77
 * to the list of active circuits on conn.
 * XXX "active" isn't an arg anymore */
78
static void
79
circuit_set_circid_orconn_helper(circuit_t *circ, int direction,
80
                                 circid_t id,
81
                                 or_connection_t *conn)
82
{
83
84
  orconn_circid_circuit_map_t search;
  orconn_circid_circuit_map_t *found;
85
  or_connection_t *old_conn, **conn_ptr;
86
  circid_t old_id, *circid_ptr;
87
  int was_active, make_active;
88
89
90
91

  if (direction == CELL_DIRECTION_OUT) {
    conn_ptr = &circ->n_conn;
    circid_ptr = &circ->n_circ_id;
92
93
    was_active = circ->next_active_on_n_conn != NULL;
    make_active = circ->n_conn_cells.n > 0;
94
95
96
97
  } else {
    or_circuit_t *c = TO_OR_CIRCUIT(circ);
    conn_ptr = &c->p_conn;
    circid_ptr = &c->p_circ_id;
98
99
    was_active = c->next_active_on_p_conn != NULL;
    make_active = c->p_conn_cells.n > 0;
100
101
102
103
104
105
  }
  old_conn = *conn_ptr;
  old_id = *circid_ptr;

  if (id == old_id && conn == old_conn)
    return;
106

107
108
109
110
111
112
113
114
  if (_last_circid_orconn_ent &&
      ((old_id == _last_circid_orconn_ent->circ_id &&
        old_conn == _last_circid_orconn_ent->or_conn) ||
       (id == _last_circid_orconn_ent->circ_id &&
        conn == _last_circid_orconn_ent->or_conn))) {
    _last_circid_orconn_ent = NULL;
  }

115
  if (old_conn) { /* we may need to remove it from the conn-circid map */
116
    tor_assert(old_conn->_base.magic == OR_CONNECTION_MAGIC);
117
118
    search.circ_id = old_id;
    search.or_conn = old_conn;
119
    found = HT_REMOVE(orconn_circid_map, &orconn_circid_circuit_map, &search);
120
    if (found) {
121
      tor_free(found);
122
      --old_conn->n_circuits;
123
    }
124
    if (was_active && old_conn != conn)
125
      make_circuit_inactive_on_conn(circ,old_conn);
126
127
  }

128
129
130
131
132
  /* Change the values only after we have possibly made the circuit inactive
   * on the previous conn. */
  *conn_ptr = conn;
  *circid_ptr = id;

133
134
135
  if (conn == NULL)
    return;

136
  /* now add the new one to the conn-circid map */
137
138
  search.circ_id = id;
  search.or_conn = conn;
139
  found = HT_FIND(orconn_circid_map, &orconn_circid_circuit_map, &search);
140
141
142
  if (found) {
    found->circuit = circ;
  } else {
143
    found = tor_malloc_zero(sizeof(orconn_circid_circuit_map_t));
144
145
146
    found->circ_id = id;
    found->or_conn = conn;
    found->circuit = circ;
147
    HT_INSERT(orconn_circid_map, &orconn_circid_circuit_map, found);
148
  }
149
  if (make_active && old_conn != conn)
150
151
    make_circuit_active_on_conn(circ,conn);

152
  ++conn->n_circuits;
153
154
}

155
156
157
158
/** Set the p_conn field of a circuit <b>circ</b>, along
 * with the corresponding circuit ID, and add the circuit as appropriate
 * to the (orconn,id)-\>circuit map. */
void
159
circuit_set_p_circid_orconn(or_circuit_t *circ, circid_t id,
160
                            or_connection_t *conn)
161
{
162
  circuit_set_circid_orconn_helper(TO_CIRCUIT(circ), CELL_DIRECTION_IN,
163
                                   id, conn);
164
165

  if (conn)
166
    tor_assert(bool_eq(circ->p_conn_cells.n, circ->next_active_on_p_conn));
167
168
169
170
171
172
}

/** Set the n_conn field of a circuit <b>circ</b>, along
 * with the corresponding circuit ID, and add the circuit as appropriate
 * to the (orconn,id)-\>circuit map. */
void
173
circuit_set_n_circid_orconn(circuit_t *circ, circid_t id,
174
                            or_connection_t *conn)
175
{
176
  circuit_set_circid_orconn_helper(circ, CELL_DIRECTION_OUT, id, conn);
177
178

  if (conn)
179
    tor_assert(bool_eq(circ->n_conn_cells.n, circ->next_active_on_n_conn));
180
181
}

182
183
/** Change the state of <b>circ</b> to <b>state</b>, adding it to or removing
 * it from lists as appropriate. */
184
void
185
circuit_set_state(circuit_t *circ, uint8_t state)
186
187
188
189
{
  tor_assert(circ);
  if (state == circ->state)
    return;
190
191
  if (!circuits_pending_or_conns)
    circuits_pending_or_conns = smartlist_create();
192
193
  if (circ->state == CIRCUIT_STATE_OR_WAIT) {
    /* remove from waiting-circuit list. */
194
    smartlist_remove(circuits_pending_or_conns, circ);
195
196
197
198
199
  }
  if (state == CIRCUIT_STATE_OR_WAIT) {
    /* add to waiting-circuit list. */
    smartlist_add(circuits_pending_or_conns, circ);
  }
200
201
  if (state == CIRCUIT_STATE_OPEN)
    tor_assert(!circ->n_conn_onionskin);
202
203
204
  circ->state = state;
}

205
206
207
/** Add <b>circ</b> to the global list of circuits. This is called only from
 * within circuit_new.
 */
208
209
210
static void
circuit_add(circuit_t *circ)
{
211
  if (!global_circuitlist) { /* first one */
212
213
214
215
216
217
218
219
    global_circuitlist = circ;
    circ->next = NULL;
  } else {
    circ->next = global_circuitlist;
    global_circuitlist = circ;
  }
}

220
/** Append to <b>out</b> all circuits in state OR_WAIT waiting for
221
222
223
224
225
226
227
228
229
230
 * the given connection. */
void
circuit_get_all_pending_on_or_conn(smartlist_t *out, or_connection_t *or_conn)
{
  tor_assert(out);
  tor_assert(or_conn);

  if (!circuits_pending_or_conns)
    return;

231
  SMARTLIST_FOREACH_BEGIN(circuits_pending_or_conns, circuit_t *, circ) {
232
233
    if (circ->marked_for_close)
      continue;
234
235
    if (!circ->n_hop)
      continue;
236
    tor_assert(circ->state == CIRCUIT_STATE_OR_WAIT);
237
    if (tor_digest_is_zero(circ->n_hop->identity_digest)) {
238
      /* Look at addr/port. This is an unkeyed connection. */
239
      if (!tor_addr_eq(&circ->n_hop->addr, &or_conn->_base.addr) ||
240
          circ->n_hop->port != or_conn->_base.port)
241
242
243
244
        continue;
    } else {
      /* We expected a key. See if it's the right one. */
      if (memcmp(or_conn->identity_digest,
245
                 circ->n_hop->identity_digest, DIGEST_LEN))
246
        continue;
247
    }
248
    smartlist_add(out, circ);
249
  } SMARTLIST_FOREACH_END(circ);
250
251
252
}

/** Return the number of circuits in state OR_WAIT, waiting for the given
253
 * connection. */
254
255
256
257
258
259
260
261
262
263
264
265
266
int
circuit_count_pending_on_or_conn(or_connection_t *or_conn)
{
  int cnt;
  smartlist_t *sl = smartlist_create();
  circuit_get_all_pending_on_or_conn(sl, or_conn);
  cnt = smartlist_len(sl);
  smartlist_free(sl);
  log_debug(LD_CIRC,"or_conn to %s, %d pending circs",
            or_conn->nickname ? or_conn->nickname : "NULL", cnt);
  return cnt;
}

267
268
269
/** Detach from the global circuit list, and deallocate, all
 * circuits that have been marked for close.
 */
270
271
void
circuit_close_all_marked(void)
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
{
  circuit_t *tmp,*m;

  while (global_circuitlist && global_circuitlist->marked_for_close) {
    tmp = global_circuitlist->next;
    circuit_free(global_circuitlist);
    global_circuitlist = tmp;
  }

  tmp = global_circuitlist;
  while (tmp && tmp->next) {
    if (tmp->next->marked_for_close) {
      m = tmp->next->next;
      circuit_free(tmp->next);
      tmp->next = m;
      /* Need to check new tmp->next; don't advance tmp. */
    } else {
      /* Advance tmp. */
      tmp = tmp->next;
    }
  }
}

295
/** Return the head of the global linked list of circuits. */
296
297
298
299
300
301
circuit_t *
_circuit_get_global_list(void)
{
  return global_circuitlist;
}

302
303
/** Function to make circ-\>state human-readable */
const char *
304
305
circuit_state_to_string(int state)
{
Nick Mathewson's avatar
Nick Mathewson committed
306
  static char buf[64];
307
308
309
  switch (state) {
    case CIRCUIT_STATE_BUILDING: return "doing handshakes";
    case CIRCUIT_STATE_ONIONSKIN_PENDING: return "processing the onion";
Roger Dingledine's avatar
Roger Dingledine committed
310
    case CIRCUIT_STATE_OR_WAIT: return "connecting to server";
311
312
    case CIRCUIT_STATE_OPEN: return "open";
    default:
313
      log_warn(LD_BUG, "Unknown circuit state %d", state);
314
      tor_snprintf(buf, sizeof(buf), "unknown state [%d]", state);
315
316
317
318
      return buf;
  }
}

319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
/** 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";
334
    case CIRCUIT_PURPOSE_C_INTRODUCING:
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
    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";
    case CIRCUIT_PURPOSE_CONTROLLER:
      return "CONTROLLER";

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

364
365
366
367
368
369
/** 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)
{
370
371
372
373
374
  int32_t num = networkstatus_get_param(NULL, "circwindow", CIRCWINDOW_START);
  /* If the consensus tells us a negative number, we'd assert. */
  if (num < 0)
    num = CIRCWINDOW_START;
  return num;
375
376
}

377
378
/** Initialize the common elements in a circuit_t, and add it to the global
 * list. */
379
380
static void
init_circuit_base(circuit_t *circ)
381
{
382
  circ->timestamp_created = time(NULL);
383
  tor_gettimeofday(&circ->highres_created);
384

385
  circ->package_window = circuit_initial_package_window();
386
387
388
  circ->deliver_window = CIRCWINDOW_START;

  circuit_add(circ);
389
390
391
392
393
394
395
396
397
}

/** 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;
398
399
400
  /* never zero, since a global ID of 0 is treated specially by the
   * controller */
  static uint32_t n_circuits_allocated = 1;
401
402
403
404
405

  circ = tor_malloc_zero(sizeof(origin_circuit_t));
  circ->_base.magic = ORIGIN_CIRCUIT_MAGIC;

  circ->next_stream_id = crypto_rand_int(1<<16);
406
  circ->global_identifier = n_circuits_allocated++;
407
408
  circ->remaining_relay_early_cells = MAX_RELAY_EARLY_CELLS_PER_CIRCUIT;
  circ->remaining_relay_early_cells -= crypto_rand_int(2);
409
410
411

  init_circuit_base(TO_CIRCUIT(circ));

Mike Perry's avatar
Mike Perry committed
412
413
  circ_times.last_circ_at = approx_time();

414
415
416
  return circ;
}

417
418
/** 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. */
419
or_circuit_t *
420
or_circuit_new(circid_t p_circ_id, or_connection_t *p_conn)
421
422
423
424
425
426
427
428
429
430
{
  /* CircIDs */
  or_circuit_t *circ;

  circ = tor_malloc_zero(sizeof(or_circuit_t));
  circ->_base.magic = OR_CIRCUIT_MAGIC;

  if (p_conn)
    circuit_set_p_circid_orconn(circ, p_circ_id, p_conn);

431
432
  circ->remaining_relay_early_cells = MAX_RELAY_EARLY_CELLS_PER_CIRCUIT;

433
  init_circuit_base(TO_CIRCUIT(circ));
434
435
436
437
438
439

  return circ;
}

/** Deallocate space associated with circ.
 */
440
441
442
static void
circuit_free(circuit_t *circ)
{
443
  void *mem;
444
  size_t memlen;
445
446
447
  if (!circ)
    return;

448
449
450
  if (CIRCUIT_IS_ORIGIN(circ)) {
    origin_circuit_t *ocirc = TO_ORIGIN_CIRCUIT(circ);
    mem = ocirc;
451
    memlen = sizeof(origin_circuit_t);
452
453
454
455
456
457
458
459
460
461
    tor_assert(circ->magic == ORIGIN_CIRCUIT_MAGIC);
    if (ocirc->build_state) {
      if (ocirc->build_state->chosen_exit)
        extend_info_free(ocirc->build_state->chosen_exit);
      if (ocirc->build_state->pending_final_cpath)
        circuit_free_cpath_node(ocirc->build_state->pending_final_cpath);
    }
    tor_free(ocirc->build_state);

    circuit_free_cpath(ocirc->cpath);
462
463
    if (ocirc->intro_key)
      crypto_free_pk_env(ocirc->intro_key);
464
465
    if (ocirc->rend_data)
      rend_data_free(ocirc->rend_data);
466
467
  } else {
    or_circuit_t *ocirc = TO_OR_CIRCUIT(circ);
468
469
    /* Remember cell statistics for this circuit before deallocating. */
    if (get_options()->CellStatistics)
470
      rep_hist_buffer_stats_add_circ(circ, time(NULL));
471
    mem = ocirc;
472
    memlen = sizeof(or_circuit_t);
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
    tor_assert(circ->magic == OR_CIRCUIT_MAGIC);

    if (ocirc->p_crypto)
      crypto_free_cipher_env(ocirc->p_crypto);
    if (ocirc->p_digest)
      crypto_free_digest_env(ocirc->p_digest);
    if (ocirc->n_crypto)
      crypto_free_cipher_env(ocirc->n_crypto);
    if (ocirc->n_digest)
      crypto_free_digest_env(ocirc->n_digest);

    if (ocirc->rend_splice) {
      or_circuit_t *other = ocirc->rend_splice;
      tor_assert(other->_base.magic == OR_CIRCUIT_MAGIC);
      other->rend_splice = NULL;
    }

    /* remove from map. */
    circuit_set_p_circid_orconn(ocirc, 0, NULL);

493
494
495
496
    /* Clear cell queue _after_ removing it from the map.  Otherwise our
     * "active" checks will be violated. */
    cell_queue_clear(&ocirc->p_conn_cells);
  }
497

498
499
  if (circ->n_hop)
    extend_info_free(circ->n_hop);
500
501
  tor_free(circ->n_conn_onionskin);

502
  /* Remove from map. */
503
  circuit_set_n_circid_orconn(circ, 0, NULL);
504

505
506
507
508
  /* Clear cell queue _after_ removing it from the map.  Otherwise our
   * "active" checks will be violated. */
  cell_queue_clear(&circ->n_conn_cells);

509
  memset(mem, 0xAA, memlen); /* poison memory */
510
  tor_free(mem);
511
512
513
}

/** Deallocate space associated with the linked list <b>cpath</b>. */
514
515
516
static void
circuit_free_cpath(crypt_path_t *cpath)
{
517
518
  crypt_path_t *victim, *head=cpath;

519
  if (!cpath)
520
521
522
523
    return;

  /* it's a doubly linked list, so we have to notice when we've
   * gone through it once. */
524
  while (cpath->next && cpath->next != head) {
525
526
527
528
529
530
531
532
    victim = cpath;
    cpath = victim->next;
    circuit_free_cpath_node(victim);
  }

  circuit_free_cpath_node(cpath);
}

533
534
535
536
537
538
539
/** Release all storage held by circuits. */
void
circuit_free_all(void)
{
  circuit_t *next;
  while (global_circuitlist) {
    next = global_circuitlist->next;
540
541
542
    if (! CIRCUIT_IS_ORIGIN(global_circuitlist)) {
      or_circuit_t *or_circ = TO_OR_CIRCUIT(global_circuitlist);
      while (or_circ->resolving_streams) {
543
544
        edge_connection_t *next_conn;
        next_conn = or_circ->resolving_streams->next_stream;
545
        connection_free(TO_CONN(or_circ->resolving_streams));
546
        or_circ->resolving_streams = next_conn;
547
      }
548
549
550
551
    }
    circuit_free(global_circuitlist);
    global_circuitlist = next;
  }
552
553
554
555
  if (circuits_pending_or_conns) {
    smartlist_free(circuits_pending_or_conns);
    circuits_pending_or_conns = NULL;
  }
556
  HT_CLEAR(orconn_circid_map, &orconn_circid_circuit_map);
557
558
}

559
/** Deallocate space associated with the cpath node <b>victim</b>. */
560
static void
561
562
circuit_free_cpath_node(crypt_path_t *victim)
{
563
564
565
  if (!victim)
    return;

566
  if (victim->f_crypto)
567
    crypto_free_cipher_env(victim->f_crypto);
568
  if (victim->b_crypto)
569
    crypto_free_cipher_env(victim->b_crypto);
570
  if (victim->f_digest)
571
    crypto_free_digest_env(victim->f_digest);
572
  if (victim->b_digest)
573
    crypto_free_digest_env(victim->b_digest);
574
575
  if (victim->dh_handshake_state)
    crypto_dh_free(victim->dh_handshake_state);
576
577
578
  if (victim->extend_info)
    extend_info_free(victim->extend_info);

579
  memset(victim, 0xBB, sizeof(crypt_path_t)); /* poison memory */
Roger Dingledine's avatar
Roger Dingledine committed
580
  tor_free(victim);
581
582
}

583
584
585
586
/** A helper function for circuit_dump_by_conn() below. Log a bunch
 * of information about circuit <b>circ</b>.
 */
static void
587
circuit_dump_details(int severity, circuit_t *circ, int conn_array_index,
588
589
590
591
                     const char *type, int this_circid, int other_circid)
{
  log(severity, LD_CIRC, "Conn %d has %s circuit: circID %d (other side %d), "
      "state %d (%s), born %d:",
592
      conn_array_index, type, this_circid, other_circid, circ->state,
593
594
595
596
597
598
599
600
601
602
603
604
605
      circuit_state_to_string(circ->state), (int)circ->timestamp_created);
  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)
{
  circuit_t *circ;
606
  edge_connection_t *tmpconn;
607
608
609
610
611
612
613
614
615

  for (circ=global_circuitlist;circ;circ = circ->next) {
    circid_t n_circ_id = circ->n_circ_id, p_circ_id = 0;
    if (circ->marked_for_close)
      continue;

    if (! CIRCUIT_IS_ORIGIN(circ))
      p_circ_id = TO_OR_CIRCUIT(circ)->p_circ_id;

616
617
    if (! CIRCUIT_IS_ORIGIN(circ) && TO_OR_CIRCUIT(circ)->p_conn &&
        TO_CONN(TO_OR_CIRCUIT(circ)->p_conn) == conn)
618
      circuit_dump_details(severity, circ, conn->conn_array_index, "App-ward",
619
620
621
622
                           p_circ_id, n_circ_id);
    if (CIRCUIT_IS_ORIGIN(circ)) {
      for (tmpconn=TO_ORIGIN_CIRCUIT(circ)->p_streams; tmpconn;
           tmpconn=tmpconn->next_stream) {
623
        if (TO_CONN(tmpconn) == conn) {
624
625
          circuit_dump_details(severity, circ, conn->conn_array_index,
                               "App-ward", p_circ_id, n_circ_id);
626
627
628
        }
      }
    }
629
    if (circ->n_conn && TO_CONN(circ->n_conn) == conn)
630
      circuit_dump_details(severity, circ, conn->conn_array_index, "Exit-ward",
631
632
633
634
                           n_circ_id, p_circ_id);
    if (! CIRCUIT_IS_ORIGIN(circ)) {
      for (tmpconn=TO_OR_CIRCUIT(circ)->n_streams; tmpconn;
           tmpconn=tmpconn->next_stream) {
635
        if (TO_CONN(tmpconn) == conn) {
636
637
          circuit_dump_details(severity, circ, conn->conn_array_index,
                               "Exit-ward", n_circ_id, p_circ_id);
638
639
640
        }
      }
    }
641
    if (!circ->n_conn && circ->n_hop &&
642
        tor_addr_eq(&circ->n_hop->addr, &conn->addr) &&
643
        circ->n_hop->port == conn->port &&
644
        conn->type == CONN_TYPE_OR &&
Karsten Loesing's avatar
Karsten Loesing committed
645
646
        !memcmp(TO_OR_CONN(conn)->identity_digest,
                circ->n_hop->identity_digest, DIGEST_LEN)) {
647
      circuit_dump_details(severity, circ, conn->conn_array_index,
648
649
650
651
652
653
654
655
                           (circ->state == CIRCUIT_STATE_OPEN &&
                            !CIRCUIT_IS_ORIGIN(circ)) ?
                             "Endpoint" : "Pending",
                           n_circ_id, p_circ_id);
    }
  }
}

656
657
/** Return the circuit whose global ID is <b>id</b>, or NULL if no
 * such circuit exists. */
658
origin_circuit_t *
659
660
661
662
circuit_get_by_global_id(uint32_t id)
{
  circuit_t *circ;
  for (circ=global_circuitlist;circ;circ = circ->next) {
663
664
    if (CIRCUIT_IS_ORIGIN(circ) &&
        TO_ORIGIN_CIRCUIT(circ)->global_identifier == id) {
665
666
667
      if (circ->marked_for_close)
        return NULL;
      else
668
        return TO_ORIGIN_CIRCUIT(circ);
669
670
671
672
673
    }
  }
  return NULL;
}

674
675
/** Return a circ such that:
 *  - circ-\>n_circ_id or circ-\>p_circ_id is equal to <b>circ_id</b>, and
Roger Dingledine's avatar
Roger Dingledine committed
676
 *  - circ is attached to <b>conn</b>, either as p_conn or n_conn.
677
678
 * Return NULL if no such circuit exists.
 */
679
static INLINE circuit_t *
680
circuit_get_by_circid_orconn_impl(circid_t circ_id, or_connection_t *conn)
681
{
682
683
  orconn_circid_circuit_map_t search;
  orconn_circid_circuit_map_t *found;
684

685
686
687
688
689
690
691
  if (_last_circid_orconn_ent &&
      circ_id == _last_circid_orconn_ent->circ_id &&
      conn == _last_circid_orconn_ent->or_conn) {
    found = _last_circid_orconn_ent;
  } else {
    search.circ_id = circ_id;
    search.or_conn = conn;
692
    found = HT_FIND(orconn_circid_map, &orconn_circid_circuit_map, &search);
693
694
    _last_circid_orconn_ent = found;
  }
695
  if (found && found->circuit)
696
    return found->circuit;
697

698
  return NULL;
699

700
  /* The rest of this checks for bugs. Disabled by default. */
701
702
703
  {
    circuit_t *circ;
    for (circ=global_circuitlist;circ;circ = circ->next) {
704
705
706
707
708
709
710
      if (! CIRCUIT_IS_ORIGIN(circ)) {
        or_circuit_t *or_circ = TO_OR_CIRCUIT(circ);
        if (or_circ->p_conn == conn && or_circ->p_circ_id == circ_id) {
          log_warn(LD_BUG,
                   "circuit matches p_conn, but not in hash table (Bug!)");
          return circ;
        }
711
712
      }
      if (circ->n_conn == conn && circ->n_circ_id == circ_id) {
713
714
        log_warn(LD_BUG,
                 "circuit matches n_conn, but not in hash table (Bug!)");
715
716
717
        return circ;
      }
    }
718
    return NULL;
719
  }
720
}
721

722
723
724
725
726
727
728
/** Return a circ such that:
 *  - circ-\>n_circ_id or circ-\>p_circ_id is equal to <b>circ_id</b>, and
 *  - circ is attached to <b>conn</b>, either as p_conn or n_conn.
 *  - circ is not marked for close.
 * Return NULL if no such circuit exists.
 */
circuit_t *
729
circuit_get_by_circid_orconn(circid_t circ_id, or_connection_t *conn)
730
731
{
  circuit_t *circ = circuit_get_by_circid_orconn_impl(circ_id, conn);
732
  if (!circ || circ->marked_for_close)
733
734
735
736
737
    return NULL;
  else
    return circ;
}

738
739
740
/** Return true iff the circuit ID <b>circ_id</b> is currently used by a
 * circuit, marked or not, on <b>conn</b>. */
int
741
circuit_id_in_use_on_orconn(circid_t circ_id, or_connection_t *conn)
742
743
744
745
{
  return circuit_get_by_circid_orconn_impl(circ_id, conn) != NULL;
}

746
/** Return the circuit that a given edge connection is using. */
747
circuit_t *
748
circuit_get_by_edge_conn(edge_connection_t *conn)
749
750
751
752
{
  circuit_t *circ;

  circ = conn->on_circuit;
753
754
755
  tor_assert(!circ ||
             (CIRCUIT_IS_ORIGIN(circ) ? circ->magic == ORIGIN_CIRCUIT_MAGIC
                                      : circ->magic == OR_CIRCUIT_MAGIC));
756

757
  return circ;
758
759
}

760
/** For each circuit that has <b>conn</b> as n_conn or p_conn, unlink the
761
762
 * circuit from the orconn,circid map, and mark it for close if it hasn't
 * been marked already.
763
 */
764
void
765
circuit_unlink_all_from_or_conn(or_connection_t *conn, int reason)
766
{
767
  circuit_t *circ;
768
769
770

  connection_or_unlink_all_active_circs(conn);

771
  for (circ = global_circuitlist; circ; circ = circ->next) {
772
773
774
775
776
777
778
779
780
781
782
    int mark = 0;
    if (circ->n_conn == conn) {
        circuit_set_n_circid_orconn(circ, 0, NULL);
        mark = 1;
    }
    if (! CIRCUIT_IS_ORIGIN(circ)) {
      or_circuit_t *or_circ = TO_OR_CIRCUIT(circ);
      if (or_circ->p_conn == conn) {
        circuit_set_p_circid_orconn(or_circ, 0, NULL);
        mark = 1;
      }
783
    }
784
785
    if (mark && !circ->marked_for_close)
      circuit_mark_for_close(circ, reason);
786
787
788
789
  }
}

/** Return a circ such that:
790
 *  - circ-\>rend_data-\>query is equal to <b>rend_query</b>, and
791
792
793
794
 *  - circ-\>purpose is equal to <b>purpose</b>.
 *
 * Return NULL if no such circuit exists.
 */
795
origin_circuit_t *
796
797
circuit_get_by_rend_query_and_purpose(const char *rend_query, uint8_t purpose)
{
798
799
  circuit_t *circ;

800
801
  tor_assert(CIRCUIT_PURPOSE_IS_ORIGIN(purpose));

802
803
  for (circ = global_circuitlist; circ; circ = circ->next) {
    if (!circ->marked_for_close &&
804
805
806
807
808
809
810
        circ->purpose == purpose) {
      origin_circuit_t *ocirc = TO_ORIGIN_CIRCUIT(circ);
      if (ocirc->rend_data &&
          !rend_cmp_service_ids(rend_query,
                                ocirc->rend_data->onion_address))
        return ocirc;
    }
811
812
813
814
  }
  return NULL;
}

815
/** Return the first circuit originating here in global_circuitlist after
816
 * <b>start</b> whose purpose is <b>purpose</b>, and where
817
818
 * <b>digest</b> (if set) matches the rend_pk_digest field. Return NULL if no
 * circuit is found.  If <b>start</b> is NULL, begin at the start of the list.
819
 */
820
821
origin_circuit_t *
circuit_get_next_by_pk_and_purpose(origin_circuit_t *start,
822
823
824
                                   const char *digest, uint8_t purpose)
{
  circuit_t *circ;
825
  tor_assert(CIRCUIT_PURPOSE_IS_ORIGIN(purpose));
826
827
828
  if (start == NULL)
    circ = global_circuitlist;
  else
829
    circ = TO_CIRCUIT(start)->next;
830

831
  for ( ; circ; circ = circ->next) {
832
833
834
835
    if (circ->marked_for_close)
      continue;
    if (circ->purpose != purpose)
      continue;
836
837
    if (!digest)
      return TO_ORIGIN_CIRCUIT(circ);
838
839
    else if (TO_ORIGIN_CIRCUIT(circ)->rend_data &&
             !memcmp(TO_ORIGIN_CIRCUIT(circ)->rend_data->rend_pk_digest,
840
                     digest, DIGEST_LEN))
841
      return TO_ORIGIN_CIRCUIT(circ);
842
843
844
845
  }
  return NULL;
}

846
847
/** Return the first OR circuit in the global list whose purpose is
 * <b>purpose</b>, and whose rend_token is the <b>len</b>-byte
848
 * <b>token</b>. */
849
850
851
static or_circuit_t *
circuit_get_by_rend_token_and_purpose(uint8_t purpose, const char *token,
                                      size_t len)
852
853
854
855
{
  circuit_t *circ;
  for (circ = global_circuitlist; circ; circ = circ->next) {
    if (! circ->marked_for_close &&
856
857
        circ->purpose == purpose &&
        ! memcmp(TO_OR_CIRCUIT(circ)->rend_token, token, len))
858
      return TO_OR_CIRCUIT(circ);
859
860
861
862
  }
  return NULL;
}

863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
/** Return the circuit waiting for a rendezvous with the provided cookie.
 * Return NULL if no such circuit is found.
 */
or_circuit_t *
circuit_get_rendezvous(const char *cookie)
{
  return circuit_get_by_rend_token_and_purpose(
                                     CIRCUIT_PURPOSE_REND_POINT_WAITING,
                                     cookie, REND_COOKIE_LEN);
}

/** Return the circuit waiting for intro cells of the given digest.
 * Return NULL if no such circuit is found.
 */
or_circuit_t *
circuit_get_intro_point(const char *digest)
{
  return circuit_get_by_rend_token_and_purpose(
                                     CIRCUIT_PURPOSE_INTRO_POINT, digest,
                                     DIGEST_LEN);
}

885
/** Return a circuit that is open, is CIRCUIT_PURPOSE_C_GENERAL,
886
887
 * has a timestamp_dirty value of 0, has flags matching the CIRCLAUNCH_*
 * flags in <b>flags</b>, and if info is defined, does not already use info
888
 * as any of its hops; or NULL if no circuit fits this description.
889
 *
890
891
892
893
 * The <b>purpose</b> argument (currently ignored) refers to the purpose of
 * the circuit we want to create, not the purpose of the circuit we want to
 * cannibalize.
 *
894
 * If !CIRCLAUNCH_NEED_UPTIME, prefer returning non-uptime circuits.
895
 */
896
origin_circuit_t *
897
circuit_find_to_cannibalize(uint8_t purpose, extend_info_t *info,
898
                            int flags)
899
{
900
901
  circuit_t *_circ;
  origin_circuit_t *best=NULL;
902
903
904
  int need_uptime = (flags & CIRCLAUNCH_NEED_UPTIME) != 0;
  int need_capacity = (flags & CIRCLAUNCH_NEED_CAPACITY) != 0;
  int internal = (flags & CIRCLAUNCH_IS_INTERNAL) != 0;
905

906
907
908
909
  log_debug(LD_CIRC,
            "Hunting for a circ to cannibalize: purpose %d, uptime %d, "
            "capacity %d, internal %d",
            purpose, need_uptime, need_capacity, internal);
910

911
912
913
914
  for (_circ=global_circuitlist; _circ; _circ = _circ->next) {
    if (CIRCUIT_IS_ORIGIN(_circ) &&
        _circ->state == CIRCUIT_STATE_OPEN &&
        !_circ->marked_for_close &&
915
        _circ->purpose == CIRCUIT_PURPOSE_C_GENERAL &&
916
917
918
919
        !_circ->timestamp_dirty) {
      origin_circuit_t *circ = TO_ORIGIN_CIRCUIT(_circ);
      if ((!need_uptime || circ->build_state->need_uptime) &&
          (!need_capacity || circ->build_state->need_capacity) &&
920
921
          (internal == circ->build_state->is_internal) &&
          circ->remaining_relay_early_cells) {
922
923
924
        if (info) {
          /* need to make sure we don't duplicate hops */
          crypt_path_t *hop = circ->cpath;
925
          routerinfo_t *ri1 = router_get_by_digest(info->identity_digest);
926
          do {
927
            routerinfo_t *ri2;
928
929
930
            if (!memcmp(hop->extend_info->identity_digest,
                        info->identity_digest, DIGEST_LEN))
              goto next;
931
932
933
934
            if (ri1 &&
                (ri2 = router_get_by_digest(hop->extend_info->identity_digest))
                && routers_in_same_family(ri1, ri2))
              goto next;
935
936
937
938
939
            hop=hop->next;
          } while (hop!=circ->cpath);
        }
        if (!best || (best->build_state->need_uptime && !need_uptime))
          best = circ;
940
      next: ;
941
      }
942
    }
943
  }
944
  return best;
945
946
}

947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
/** Return the number of hops in circuit's path. */
int
circuit_get_cpath_len(origin_circuit_t *circ)
{
  int n = 0;
  if (circ && circ->cpath) {
    crypt_path_t *cpath, *cpath_next = NULL;
    for (cpath = circ->cpath; cpath_next != circ->cpath; cpath = cpath_next) {
      cpath_next = cpath->next;
      ++n;
    }
  }
  return n;
}

962
963
964
965
966
/** Return the <b>hopnum</b>th hop in <b>circ</b>->cpath, or NULL if there
 * aren't that many hops in the list. */
crypt_path_t *
circuit_get_cpath_hop(origin_circuit_t *circ, int hopnum)
{
967
  if (circ && circ->cpath && hopnum > 0) {
968
969
970
971
972
973
974
975
976
977
    crypt_path_t *cpath, *cpath_next = NULL;
    for (cpath = circ->cpath; cpath_next != circ->cpath; cpath = cpath_next) {
      cpath_next = cpath->next;
      if (--hopnum <= 0)
        return cpath;
    }
  }
  return NULL;
}

978
979
/** Go through the circuitlist; mark-for-close each circuit that starts
 *  at us but has not yet been used. */
980
981
982
void
circuit_mark_all_unused_circs(void)
{
983
984
985
986
987
988
  circuit_t *circ;

  for (circ=global_circuitlist; circ; circ = circ->next) {
    if (CIRCUIT_IS_ORIGIN(circ) &&
        !circ->marked_for_close &&
        !circ->timestamp_dirty)
989
      circuit_mark_for_close(circ, END_CIRC_REASON_FINISHED);
990
991
992
  }
}

993
994
995
996
997
998
999
1000
/** Go through the circuitlist; for each circuit that starts at us
 * and is dirty, frob its timestamp_dirty so we won't use it for any
 * new streams.
 *
 * This is useful for letting the user change pseudonyms, so new
 * streams will not be linkable to old streams.
 */
void