circuitlist.c 39.9 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
    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);
    }
    tor_free(ocirc->build_state);

    circuit_free_cpath(ocirc->cpath);
460
461
462

    crypto_free_pk_env(ocirc->intro_key);
    rend_data_free(ocirc->rend_data);
463
464
  } else {
    or_circuit_t *ocirc = TO_OR_CIRCUIT(circ);
465
466
    /* Remember cell statistics for this circuit before deallocating. */
    if (get_options()->CellStatistics)
467
      rep_hist_buffer_stats_add_circ(circ, time(NULL));
468
    mem = ocirc;
469
    memlen = sizeof(or_circuit_t);
470
471
    tor_assert(circ->magic == OR_CIRCUIT_MAGIC);

472
473
474
475
    crypto_free_cipher_env(ocirc->p_crypto);
    crypto_free_digest_env(ocirc->p_digest);
    crypto_free_cipher_env(ocirc->n_crypto);
    crypto_free_digest_env(ocirc->n_digest);
476
477
478
479
480
481
482
483
484
485

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

486
487
488
489
    /* Clear cell queue _after_ removing it from the map.  Otherwise our
     * "active" checks will be violated. */
    cell_queue_clear(&ocirc->p_conn_cells);
  }
490

491
  extend_info_free(circ->n_hop);
492
493
  tor_free(circ->n_conn_onionskin);

494
  /* Remove from map. */
495
  circuit_set_n_circid_orconn(circ, 0, NULL);
496

497
498
499
500
  /* Clear cell queue _after_ removing it from the map.  Otherwise our
   * "active" checks will be violated. */
  cell_queue_clear(&circ->n_conn_cells);

501
  memset(mem, 0xAA, memlen); /* poison memory */
502
  tor_free(mem);
503
504
505
}

/** Deallocate space associated with the linked list <b>cpath</b>. */
506
507
508
static void
circuit_free_cpath(crypt_path_t *cpath)
{
509
510
  crypt_path_t *victim, *head=cpath;

511
  if (!cpath)
512
513
514
515
    return;

  /* it's a doubly linked list, so we have to notice when we've
   * gone through it once. */
516
  while (cpath->next && cpath->next != head) {
517
518
519
520
521
522
523
524
    victim = cpath;
    cpath = victim->next;
    circuit_free_cpath_node(victim);
  }

  circuit_free_cpath_node(cpath);
}

525
526
527
528
529
530
531
/** Release all storage held by circuits. */
void
circuit_free_all(void)
{
  circuit_t *next;
  while (global_circuitlist) {
    next = global_circuitlist->next;
532
533
534
    if (! CIRCUIT_IS_ORIGIN(global_circuitlist)) {
      or_circuit_t *or_circ = TO_OR_CIRCUIT(global_circuitlist);
      while (or_circ->resolving_streams) {
535
536
        edge_connection_t *next_conn;
        next_conn = or_circ->resolving_streams->next_stream;
537
        connection_free(TO_CONN(or_circ->resolving_streams));
538
        or_circ->resolving_streams = next_conn;
539
      }
540
541
542
543
    }
    circuit_free(global_circuitlist);
    global_circuitlist = next;
  }
544
545
546
547

  smartlist_free(circuits_pending_or_conns);
  circuits_pending_or_conns = NULL;

548
  HT_CLEAR(orconn_circid_map, &orconn_circid_circuit_map);
549
550
}

551
/** Deallocate space associated with the cpath node <b>victim</b>. */
552
static void
553
554
circuit_free_cpath_node(crypt_path_t *victim)
{
555
556
557
  if (!victim)
    return;

558
559
560
561
562
563
  crypto_free_cipher_env(victim->f_crypto);
  crypto_free_cipher_env(victim->b_crypto);
  crypto_free_digest_env(victim->f_digest);
  crypto_free_digest_env(victim->b_digest);
  crypto_dh_free(victim->dh_handshake_state);
  extend_info_free(victim->extend_info);
564

565
  memset(victim, 0xBB, sizeof(crypt_path_t)); /* poison memory */
Roger Dingledine's avatar
Roger Dingledine committed
566
  tor_free(victim);
567
568
}

569
570
571
572
/** A helper function for circuit_dump_by_conn() below. Log a bunch
 * of information about circuit <b>circ</b>.
 */
static void
573
circuit_dump_details(int severity, circuit_t *circ, int conn_array_index,
574
575
576
577
                     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:",
578
      conn_array_index, type, this_circid, other_circid, circ->state,
579
580
581
582
583
584
585
586
587
588
589
590
591
      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;
592
  edge_connection_t *tmpconn;
593
594
595
596
597
598
599
600
601

  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;

602
603
    if (! CIRCUIT_IS_ORIGIN(circ) && TO_OR_CIRCUIT(circ)->p_conn &&
        TO_CONN(TO_OR_CIRCUIT(circ)->p_conn) == conn)
604
      circuit_dump_details(severity, circ, conn->conn_array_index, "App-ward",
605
606
607
608
                           p_circ_id, n_circ_id);
    if (CIRCUIT_IS_ORIGIN(circ)) {
      for (tmpconn=TO_ORIGIN_CIRCUIT(circ)->p_streams; tmpconn;
           tmpconn=tmpconn->next_stream) {
609
        if (TO_CONN(tmpconn) == conn) {
610
611
          circuit_dump_details(severity, circ, conn->conn_array_index,
                               "App-ward", p_circ_id, n_circ_id);
612
613
614
        }
      }
    }
615
    if (circ->n_conn && TO_CONN(circ->n_conn) == conn)
616
      circuit_dump_details(severity, circ, conn->conn_array_index, "Exit-ward",
617
618
619
620
                           n_circ_id, p_circ_id);
    if (! CIRCUIT_IS_ORIGIN(circ)) {
      for (tmpconn=TO_OR_CIRCUIT(circ)->n_streams; tmpconn;
           tmpconn=tmpconn->next_stream) {
621
        if (TO_CONN(tmpconn) == conn) {
622
623
          circuit_dump_details(severity, circ, conn->conn_array_index,
                               "Exit-ward", n_circ_id, p_circ_id);
624
625
626
        }
      }
    }
627
    if (!circ->n_conn && circ->n_hop &&
628
        tor_addr_eq(&circ->n_hop->addr, &conn->addr) &&
629
        circ->n_hop->port == conn->port &&
630
        conn->type == CONN_TYPE_OR &&
Karsten Loesing's avatar
Karsten Loesing committed
631
632
        !memcmp(TO_OR_CONN(conn)->identity_digest,
                circ->n_hop->identity_digest, DIGEST_LEN)) {
633
      circuit_dump_details(severity, circ, conn->conn_array_index,
634
635
636
637
638
639
640
641
                           (circ->state == CIRCUIT_STATE_OPEN &&
                            !CIRCUIT_IS_ORIGIN(circ)) ?
                             "Endpoint" : "Pending",
                           n_circ_id, p_circ_id);
    }
  }
}

642
643
/** Return the circuit whose global ID is <b>id</b>, or NULL if no
 * such circuit exists. */
644
origin_circuit_t *
645
646
647
648
circuit_get_by_global_id(uint32_t id)
{
  circuit_t *circ;
  for (circ=global_circuitlist;circ;circ = circ->next) {
649
650
    if (CIRCUIT_IS_ORIGIN(circ) &&
        TO_ORIGIN_CIRCUIT(circ)->global_identifier == id) {
651
652
653
      if (circ->marked_for_close)
        return NULL;
      else
654
        return TO_ORIGIN_CIRCUIT(circ);
655
656
657
658
659
    }
  }
  return NULL;
}

660
661
/** 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
662
 *  - circ is attached to <b>conn</b>, either as p_conn or n_conn.
663
664
 * Return NULL if no such circuit exists.
 */
665
static INLINE circuit_t *
666
circuit_get_by_circid_orconn_impl(circid_t circ_id, or_connection_t *conn)
667
{
668
669
  orconn_circid_circuit_map_t search;
  orconn_circid_circuit_map_t *found;
670

671
672
673
674
675
676
677
  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;
678
    found = HT_FIND(orconn_circid_map, &orconn_circid_circuit_map, &search);
679
680
    _last_circid_orconn_ent = found;
  }
681
  if (found && found->circuit)
682
    return found->circuit;
683

684
  return NULL;
685

686
  /* The rest of this checks for bugs. Disabled by default. */
687
688
689
  {
    circuit_t *circ;
    for (circ=global_circuitlist;circ;circ = circ->next) {
690
691
692
693
694
695
696
      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;
        }
697
698
      }
      if (circ->n_conn == conn && circ->n_circ_id == circ_id) {
699
700
        log_warn(LD_BUG,
                 "circuit matches n_conn, but not in hash table (Bug!)");
701
702
703
        return circ;
      }
    }
704
    return NULL;
705
  }
706
}
707

708
709
710
711
712
713
714
/** 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 *
715
circuit_get_by_circid_orconn(circid_t circ_id, or_connection_t *conn)
716
717
{
  circuit_t *circ = circuit_get_by_circid_orconn_impl(circ_id, conn);
718
  if (!circ || circ->marked_for_close)
719
720
721
722
723
    return NULL;
  else
    return circ;
}

724
725
726
/** Return true iff the circuit ID <b>circ_id</b> is currently used by a
 * circuit, marked or not, on <b>conn</b>. */
int
727
circuit_id_in_use_on_orconn(circid_t circ_id, or_connection_t *conn)
728
729
730
731
{
  return circuit_get_by_circid_orconn_impl(circ_id, conn) != NULL;
}

732
/** Return the circuit that a given edge connection is using. */
733
circuit_t *
734
circuit_get_by_edge_conn(edge_connection_t *conn)
735
736
737
738
{
  circuit_t *circ;

  circ = conn->on_circuit;
739
740
741
  tor_assert(!circ ||
             (CIRCUIT_IS_ORIGIN(circ) ? circ->magic == ORIGIN_CIRCUIT_MAGIC
                                      : circ->magic == OR_CIRCUIT_MAGIC));
742

743
  return circ;
744
745
}

746
/** For each circuit that has <b>conn</b> as n_conn or p_conn, unlink the
747
748
 * circuit from the orconn,circid map, and mark it for close if it hasn't
 * been marked already.
749
 */
750
void
751
circuit_unlink_all_from_or_conn(or_connection_t *conn, int reason)
752
{
753
  circuit_t *circ;
754
755
756

  connection_or_unlink_all_active_circs(conn);

757
  for (circ = global_circuitlist; circ; circ = circ->next) {
758
759
760
761
762
763
764
765
766
767
768
    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;
      }
769
    }
770
771
    if (mark && !circ->marked_for_close)
      circuit_mark_for_close(circ, reason);
772
773
774
775
  }
}

/** Return a circ such that:
776
 *  - circ-\>rend_data-\>query is equal to <b>rend_query</b>, and
777
778
779
780
 *  - circ-\>purpose is equal to <b>purpose</b>.
 *
 * Return NULL if no such circuit exists.
 */
781
origin_circuit_t *
782
783
circuit_get_by_rend_query_and_purpose(const char *rend_query, uint8_t purpose)
{
784
785
  circuit_t *circ;

786
787
  tor_assert(CIRCUIT_PURPOSE_IS_ORIGIN(purpose));

788
789
  for (circ = global_circuitlist; circ; circ = circ->next) {
    if (!circ->marked_for_close &&
790
791
792
793
794
795
796
        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;
    }
797
798
799
800
  }
  return NULL;
}

801
/** Return the first circuit originating here in global_circuitlist after
802
 * <b>start</b> whose purpose is <b>purpose</b>, and where
803
804
 * <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.
805
 */
806
807
origin_circuit_t *
circuit_get_next_by_pk_and_purpose(origin_circuit_t *start,
808
809
810
                                   const char *digest, uint8_t purpose)
{
  circuit_t *circ;
811
  tor_assert(CIRCUIT_PURPOSE_IS_ORIGIN(purpose));
812
813
814
  if (start == NULL)
    circ = global_circuitlist;
  else
815
    circ = TO_CIRCUIT(start)->next;
816

817
  for ( ; circ; circ = circ->next) {
818
819
820
821
    if (circ->marked_for_close)
      continue;
    if (circ->purpose != purpose)
      continue;
822
823
    if (!digest)
      return TO_ORIGIN_CIRCUIT(circ);
824
825
    else if (TO_ORIGIN_CIRCUIT(circ)->rend_data &&
             !memcmp(TO_ORIGIN_CIRCUIT(circ)->rend_data->rend_pk_digest,
826
                     digest, DIGEST_LEN))
827
      return TO_ORIGIN_CIRCUIT(circ);
828
829
830
831
  }
  return NULL;
}

832
833
/** 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
834
 * <b>token</b>. */
835
836
837
static or_circuit_t *
circuit_get_by_rend_token_and_purpose(uint8_t purpose, const char *token,
                                      size_t len)
838
839
840
841
{
  circuit_t *circ;
  for (circ = global_circuitlist; circ; circ = circ->next) {
    if (! circ->marked_for_close &&
842
843
        circ->purpose == purpose &&
        ! memcmp(TO_OR_CIRCUIT(circ)->rend_token, token, len))
844
      return TO_OR_CIRCUIT(circ);
845
846
847
848
  }
  return NULL;
}

849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
/** 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);
}

871
/** Return a circuit that is open, is CIRCUIT_PURPOSE_C_GENERAL,
872
873
 * 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
874
 * as any of its hops; or NULL if no circuit fits this description.
875
 *
876
877
878
879
 * 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.
 *
880
 * If !CIRCLAUNCH_NEED_UPTIME, prefer returning non-uptime circuits.
881
 */
882
origin_circuit_t *
883
circuit_find_to_cannibalize(uint8_t purpose, extend_info_t *info,
884
                            int flags)
885
{
886
887
  circuit_t *_circ;
  origin_circuit_t *best=NULL;
888
889
890
  int need_uptime = (flags & CIRCLAUNCH_NEED_UPTIME) != 0;
  int need_capacity = (flags & CIRCLAUNCH_NEED_CAPACITY) != 0;
  int internal = (flags & CIRCLAUNCH_IS_INTERNAL) != 0;
891

892
893
894
895
  log_debug(LD_CIRC,
            "Hunting for a circ to cannibalize: purpose %d, uptime %d, "
            "capacity %d, internal %d",
            purpose, need_uptime, need_capacity, internal);
896

897
898
899
900
  for (_circ=global_circuitlist; _circ; _circ = _circ->next) {
    if (CIRCUIT_IS_ORIGIN(_circ) &&
        _circ->state == CIRCUIT_STATE_OPEN &&
        !_circ->marked_for_close &&
901
        _circ->purpose == CIRCUIT_PURPOSE_C_GENERAL &&
902
903
904
905
        !_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) &&
906
907
          (internal == circ->build_state->is_internal) &&
          circ->remaining_relay_early_cells) {
908
909
910
        if (info) {
          /* need to make sure we don't duplicate hops */
          crypt_path_t *hop = circ->cpath;
911
          routerinfo_t *ri1 = router_get_by_digest(info->identity_digest);
912
          do {
913
            routerinfo_t *ri2;
914
915
916
            if (!memcmp(hop->extend_info->identity_digest,
                        info->identity_digest, DIGEST_LEN))
              goto next;
917
918
919
920
            if (ri1 &&
                (ri2 = router_get_by_digest(hop->extend_info->identity_digest))
                && routers_in_same_family(ri1, ri2))
              goto next;
921
922
923
924
925
            hop=hop->next;
          } while (hop!=circ->cpath);
        }
        if (!best || (best->build_state->need_uptime && !need_uptime))
          best = circ;
926
      next: ;
927
      }
928
    }
929
  }
930
  return best;
931
932
}

933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
/** 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;
}

948
949
950
951
952
/** 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)
{
953
  if (circ && circ->cpath && hopnum > 0) {
954
955
956
957
958
959
960
961
962
963
    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;
}

964
965
/** Go through the circuitlist; mark-for-close each circuit that starts
 *  at us but has not yet been used. */
966
967
968
void
circuit_mark_all_unused_circs(void)
{
969
970
971
972
973
974
  circuit_t *circ;

  for (circ=global_circuitlist; circ; circ = circ->next) {
    if (CIRCUIT_IS_ORIGIN(circ) &&
        !circ->marked_for_close &&
        !circ->timestamp_dirty)
975
      circuit_mark_for_close(circ, END_CIRC_REASON_FINISHED);
976
977
978
  }
}

979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
/** 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
circuit_expire_all_dirty_circs(void)
{
  circuit_t *circ;
  or_options_t *options = get_options();

  for (circ=global_circuitlist; circ; circ = circ->next) {
    if (CIRCUIT_IS_ORIGIN(circ) &&
        !circ->marked_for_close &&
        circ->timestamp_dirty)
      circ->timestamp_dirty -= options->MaxCircuitDirtiness;
  }
}

1000
/** Mark <b>circ</b> to be closed next time we call