circuitlist.c 25 KB
Newer Older
Roger Dingledine's avatar
Roger Dingledine committed
1
2
/* Copyright 2001 Matej Pfajfar.
 * Copyright 2001-2004 Roger Dingledine.
Nick Mathewson's avatar
Nick Mathewson committed
3
 * Copyright 2004-2005 Roger Dingledine, Nick Mathewson. */
4
5
/* See LICENSE for licensing information */
/* $Id$ */
6
const char circuitlist_c_id[] = "$Id$";
7
8
9
10
11
12
13

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

#include "or.h"
14

15
#include "../common/ht.h"
16
17
18

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

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

22
23
24
/** A list of all the circuits in CIRCUIT_STATE_OR_WAIT. */
smartlist_t *circuits_pending_or_conns=NULL;

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

29
30
/********* END VARIABLES ************/

31
32
/** 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.) */
33
typedef struct orconn_circid_circuit_map_t {
34
  HT_ENTRY(orconn_circid_circuit_map_t) node;
35
36
37
  connection_t *or_conn;
  uint16_t circ_id;
  circuit_t *circuit;
38
} orconn_circid_circuit_map_t;
39

40
/** Helper for hash tables: compare the OR connection and circuit ID for a and b,
41
42
 * and return less than, equal to, or greater than zero appropriately.
 */
43
static INLINE int
44
45
46
47
48
49
50
51
_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;
}

static INLINE unsigned int
_orconn_circid_entry_hash(orconn_circid_circuit_map_t *a)
52
{
53
54
55
  return (((unsigned)a->circ_id)<<16) ^ (unsigned)(uintptr_t)(a->or_conn);
}

56
57
static HT_HEAD(orconn_circid_map, orconn_circid_circuit_map_t) orconn_circid_circuit_map = HT_INITIALIZER();
HT_PROTOTYPE(orconn_circid_map, orconn_circid_circuit_map_t, node,
58
             _orconn_circid_entry_hash, _orconn_circid_entries_eq);
59
HT_GENERATE(orconn_circid_map, orconn_circid_circuit_map_t, node,
60
61
            _orconn_circid_entry_hash, _orconn_circid_entries_eq, 0.6,
            malloc, realloc, free);
62

63
64
65
/** 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.
66
 */
67
orconn_circid_circuit_map_t *_last_circid_orconn_ent = NULL;
68

69
70
71
/** Set the p_conn or 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. */
72
73
74
75
76
77
78
void
circuit_set_circid_orconn(circuit_t *circ, uint16_t id,
                          connection_t *conn,
                          enum which_conn_changed_t which)
{
  uint16_t old_id;
  connection_t *old_conn;
79
80
  orconn_circid_circuit_map_t search;
  orconn_circid_circuit_map_t *found;
81
82
83
84
85
86
87
88
89
90
91
92
93
94

  tor_assert(!conn || conn->type == CONN_TYPE_OR);

  if (which == P_CONN_CHANGED) {
    old_id = circ->p_circ_id;
    old_conn = circ->p_conn;
    circ->p_circ_id = id;
    circ->p_conn = conn;
  } else {
    old_id = circ->n_circ_id;
    old_conn = circ->n_conn;
    circ->n_circ_id = id;
    circ->n_conn = conn;
  }
95
96
  if (conn == old_conn && old_id == id)
    return;
97

98
99
100
101
102
103
104
105
  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;
  }

106
  if (old_conn) { /* we may need to remove it from the conn-circid map */
107
108
    search.circ_id = old_id;
    search.or_conn = old_conn;
109
    found = HT_REMOVE(orconn_circid_map, &orconn_circid_circuit_map, &search);
110
    if (found) {
111
      tor_free(found);
112
    }
113
    --old_conn->n_circuits;
114
115
116
117
118
  }

  if (conn == NULL)
    return;

119
  /* now add the new one to the conn-circid map */
120
121
  search.circ_id = id;
  search.or_conn = conn;
122
  found = HT_FIND(orconn_circid_map, &orconn_circid_circuit_map, &search);
123
124
125
  if (found) {
    found->circuit = circ;
  } else {
126
    found = tor_malloc_zero(sizeof(orconn_circid_circuit_map_t));
127
128
129
    found->circ_id = id;
    found->or_conn = conn;
    found->circuit = circ;
130
    HT_INSERT(orconn_circid_map, &orconn_circid_circuit_map, found);
131
  }
132
  ++conn->n_circuits;
133
134
}

135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
/** Add <b>circ</b> to the list of circuits waiting for us to connect to
 * an OR. */
void
circuit_set_state(circuit_t *circ, int state)
{
  tor_assert(circ);
  if (state == circ->state)
    return;
  if (circ->state == CIRCUIT_STATE_OR_WAIT) {
    /* remove from waiting-circuit list. */
    if (!circuits_pending_or_conns)
      circuits_pending_or_conns = smartlist_create();
    smartlist_remove(circuits_pending_or_conns, circ);
  }
  if (state == CIRCUIT_STATE_OR_WAIT) {
    /* add to waiting-circuit list. */
    if (!circuits_pending_or_conns)
      circuits_pending_or_conns = smartlist_create();
    smartlist_add(circuits_pending_or_conns, circ);
  }
  circ->state = state;
}

/** Remove <b>circ</b> from the list of circuits waiting for us to connect to
 * an OR. */
void
circuit_clear_state_orwait(circuit_t *circ)
{
}

165
166
167
/** Add <b>circ</b> to the global list of circuits. This is called only from
 * within circuit_new.
 */
168
169
170
static void
circuit_add(circuit_t *circ)
{
171
  if (!global_circuitlist) { /* first one */
172
173
174
175
176
177
178
179
180
181
182
    global_circuitlist = circ;
    circ->next = NULL;
  } else {
    circ->next = global_circuitlist;
    global_circuitlist = circ;
  }
}

/** Detach from the global circuit list, and deallocate, all
 * circuits that have been marked for close.
 */
183
184
void
circuit_close_all_marked(void)
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
{
  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;
    }
  }
}

208
/** Return the head of the global linked list of circuits. **/
209
210
211
212
213
214
circuit_t *
_circuit_get_global_list(void)
{
  return global_circuitlist;
}

215
216
/** Function to make circ-\>state human-readable */
const char *
217
218
circuit_state_to_string(int state)
{
Nick Mathewson's avatar
Nick Mathewson committed
219
  static char buf[64];
220
221
222
  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
223
    case CIRCUIT_STATE_OR_WAIT: return "connecting to server";
224
225
    case CIRCUIT_STATE_OPEN: return "open";
    default:
226
      warn(LD_BUG, "Bug: unknown circuit state %d", state);
227
      tor_snprintf(buf, sizeof(buf), "unknown state [%d]", state);
228
229
230
231
      return buf;
  }
}

232
233
234
/** 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.
 */
235
236
237
circuit_t *
circuit_new(uint16_t p_circ_id, connection_t *p_conn)
{
238
  circuit_t *circ;
239
  static uint32_t n_circuits_allocated = 1;
Roger Dingledine's avatar
Roger Dingledine committed
240
241
  /* never zero, since a global ID of 0 is treated specially by the
   * controller */
242
243
244
245
246
247
248

  circ = tor_malloc_zero(sizeof(circuit_t));
  circ->magic = CIRCUIT_MAGIC;

  circ->timestamp_created = time(NULL);

  /* CircIDs */
249
250
251
  if (p_conn) {
    circuit_set_circid_orconn(circ, p_circ_id, p_conn, P_CONN_CHANGED);
  }
252
253
254
255
256
  /* circ->n_circ_id remains 0 because we haven't identified the next hop yet */

  circ->package_window = CIRCWINDOW_START;
  circ->deliver_window = CIRCWINDOW_START;

257
  circ->next_stream_id = crypto_rand_int(1<<16);
258
  circ->global_identifier = n_circuits_allocated++;
259
260
261
262
263
264
265
266

  circuit_add(circ);

  return circ;
}

/** Deallocate space associated with circ.
 */
267
268
269
static void
circuit_free(circuit_t *circ)
{
270
271
272
273
274
275
276
277
278
279
  tor_assert(circ);
  tor_assert(circ->magic == CIRCUIT_MAGIC);
  if (circ->n_crypto)
    crypto_free_cipher_env(circ->n_crypto);
  if (circ->p_crypto)
    crypto_free_cipher_env(circ->p_crypto);
  if (circ->n_digest)
    crypto_free_digest_env(circ->n_digest);
  if (circ->p_digest)
    crypto_free_digest_env(circ->p_digest);
280
  if (circ->build_state) {
281
282
    if (circ->build_state->chosen_exit)
      extend_info_free(circ->build_state->chosen_exit);
283
284
285
286
    if (circ->build_state->pending_final_cpath)
      circuit_free_cpath_node(circ->build_state->pending_final_cpath);
  }
  tor_free(circ->build_state);
287
  tor_free(circ->onionskin);
288
289
290
291
  circuit_free_cpath(circ->cpath);
  if (circ->rend_splice) {
    circ->rend_splice->rend_splice = NULL;
  }
292
293
294
  /* Remove from map. */
  circuit_set_circid_orconn(circ, 0, NULL, P_CONN_CHANGED);
  circuit_set_circid_orconn(circ, 0, NULL, N_CONN_CHANGED);
295
296

  memset(circ, 0xAA, sizeof(circuit_t)); /* poison memory */
Roger Dingledine's avatar
Roger Dingledine committed
297
  tor_free(circ);
298
299
300
}

/** Deallocate space associated with the linked list <b>cpath</b>. */
301
302
303
static void
circuit_free_cpath(crypt_path_t *cpath)
{
304
305
  crypt_path_t *victim, *head=cpath;

306
  if (!cpath)
307
308
309
310
    return;

  /* it's a doubly linked list, so we have to notice when we've
   * gone through it once. */
311
  while (cpath->next && cpath->next != head) {
312
313
314
315
316
317
318
319
    victim = cpath;
    cpath = victim->next;
    circuit_free_cpath_node(victim);
  }

  circuit_free_cpath_node(cpath);
}

320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
/** Release all storage held by circuits. */
void
circuit_free_all(void)
{
  circuit_t *next;
  while (global_circuitlist) {
    next = global_circuitlist->next;
    while (global_circuitlist->resolving_streams) {
      connection_t *next;
      next = global_circuitlist->resolving_streams->next_stream;
      connection_free(global_circuitlist->resolving_streams);
      global_circuitlist->resolving_streams = next;
    }
    circuit_free(global_circuitlist);
    global_circuitlist = next;
  }
336
337
  smartlist_free(circuits_pending_or_conns);
  circuits_pending_or_conns = NULL;
338
339
}

340
/** Deallocate space associated with the cpath node <b>victim</b>. */
341
static void
342
343
circuit_free_cpath_node(crypt_path_t *victim)
{
344
  if (victim->f_crypto)
345
    crypto_free_cipher_env(victim->f_crypto);
346
  if (victim->b_crypto)
347
    crypto_free_cipher_env(victim->b_crypto);
348
  if (victim->f_digest)
349
    crypto_free_digest_env(victim->f_digest);
350
  if (victim->b_digest)
351
    crypto_free_digest_env(victim->b_digest);
352
353
  if (victim->dh_handshake_state)
    crypto_dh_free(victim->dh_handshake_state);
354
355
356
  if (victim->extend_info)
    extend_info_free(victim->extend_info);

357
  victim->magic = 0xDEADBEEFu;
Roger Dingledine's avatar
Roger Dingledine committed
358
  tor_free(victim);
359
360
}

361
362
/** Return the circuit whose global ID is <b>id</b>, or NULL if no
 * such circuit exists. */
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
circuit_t *
circuit_get_by_global_id(uint32_t id)
{
  circuit_t *circ;
  for (circ=global_circuitlist;circ;circ = circ->next) {
    if (circ->global_identifier == id) {
      if (circ->marked_for_close)
        return NULL;
      else
        return circ;
    }
  }
  return NULL;
}

378
379
/** 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
380
 *  - circ is attached to <b>conn</b>, either as p_conn or n_conn.
381
382
 * Return NULL if no such circuit exists.
 */
383
384
static INLINE circuit_t *
circuit_get_by_circid_orconn_impl(uint16_t circ_id, connection_t *conn)
385
{
386
387
  orconn_circid_circuit_map_t search;
  orconn_circid_circuit_map_t *found;
388

389
  tor_assert(conn->type == CONN_TYPE_OR);
390

391
392
393
394
395
396
397
  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;
398
    found = HT_FIND(orconn_circid_map, &orconn_circid_circuit_map, &search);
399
400
    _last_circid_orconn_ent = found;
  }
401
  if (found && found->circuit)
402
    return found->circuit;
403

404
  return NULL;
405

406
  /* The rest of this checks for bugs. Disabled by default. */
407
408
409
410
  {
    circuit_t *circ;
    for (circ=global_circuitlist;circ;circ = circ->next) {
      if (circ->p_conn == conn && circ->p_circ_id == circ_id) {
411
        warn(LD_BUG, "circuit matches p_conn, but not in hash table (Bug!)");
412
413
414
        return circ;
      }
      if (circ->n_conn == conn && circ->n_circ_id == circ_id) {
415
        warn(LD_BUG, "circuit matches n_conn, but not in hash table (Bug!)");
416
417
418
        return circ;
      }
    }
419
    return NULL;
420
  }
421
}
422

423
424
425
426
427
428
429
430
431
432
/** 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 *
circuit_get_by_circid_orconn(uint16_t circ_id, connection_t *conn)
{
  circuit_t *circ = circuit_get_by_circid_orconn_impl(circ_id, conn);
433
  if (!circ || circ->marked_for_close)
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
    return NULL;
  else
    return circ;
}

/** Return true iff there is 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.
 * Return NULL if no such circuit exists.
 */
int
circuit_id_used_on_conn(uint16_t circ_id, connection_t *conn)
{
  circuit_t *circ = circuit_get_by_circid_orconn_impl(circ_id, conn);
  if (circ && circ->marked_for_close)
    log_fn(LOG_NOTICE, LD_CIRC,
           "I was about to re-use a circuit ID that had been marked."
           " Good thing we fixed that bug!");
  return circ != NULL;
453
454
}

455
/** Return the circuit that a given edge connection is using. */
456
457
circuit_t *
circuit_get_by_edge_conn(connection_t *conn)
458
459
460
461
462
{
  circuit_t *circ;
  tor_assert(CONN_IS_EDGE(conn));

  circ = conn->on_circuit;
463
464
  tor_assert(!circ || circ->magic == CIRCUIT_MAGIC);

465
  return circ;
466
467
}

468
/** Return a new list of all circuits that have <b>conn</b> as n_conn or p_conn.
469
 */
470
471
smartlist_t *
circuit_get_all_on_orconn(connection_t *conn)
472
{
473
  smartlist_t *res = smartlist_create();
474
475
  circuit_t *circ;

476
  for (circ=global_circuitlist;circ;circ = circ->next) {
477
478
    if (!circ->marked_for_close &&
        (circ->p_conn == conn || circ->n_conn == conn))
479
      smartlist_add(res, circ);
480
  }
481
  return res;
482
483
484
485
486
487
488
489
}

/** Return a circ such that:
 *  - circ-\>rend_query is equal to <b>rend_query</b>, and
 *  - circ-\>purpose is equal to <b>purpose</b>.
 *
 * Return NULL if no such circuit exists.
 */
490
491
492
circuit_t *
circuit_get_by_rend_query_and_purpose(const char *rend_query, uint8_t purpose)
{
493
494
495
496
497
498
499
500
501
502
503
  circuit_t *circ;

  for (circ = global_circuitlist; circ; circ = circ->next) {
    if (!circ->marked_for_close &&
        circ->purpose == purpose &&
        !rend_cmp_service_ids(rend_query, circ->rend_query))
      return circ;
  }
  return NULL;
}

Roger Dingledine's avatar
Roger Dingledine committed
504
505
506
507
/** Return the first circuit in global_circuitlist after <b>start</b>
 * whose rend_pk_digest field is <b>digest</b> and whose purpose is
 * <b>purpose</b>. Returns NULL if no circuit is found.
 * If <b>start</b> is NULL, begin at the start of the list.
508
509
510
511
512
513
514
515
516
517
518
 */
circuit_t *
circuit_get_next_by_pk_and_purpose(circuit_t *start,
                                   const char *digest, uint8_t purpose)
{
  circuit_t *circ;
  if (start == NULL)
    circ = global_circuitlist;
  else
    circ = start->next;

519
  for ( ; circ; circ = circ->next) {
520
521
522
523
524
525
526
527
528
529
530
531
532
    if (circ->marked_for_close)
      continue;
    if (circ->purpose != purpose)
      continue;
    if (!memcmp(circ->rend_pk_digest, digest, DIGEST_LEN))
      return circ;
  }
  return NULL;
}

/** Return the circuit waiting for a rendezvous with the provided cookie.
 * Return NULL if no such circuit is found.
 */
533
534
circuit_t *
circuit_get_rendezvous(const char *cookie)
535
536
537
538
539
540
541
542
543
544
545
{
  circuit_t *circ;
  for (circ = global_circuitlist; circ; circ = circ->next) {
    if (! circ->marked_for_close &&
        circ->purpose == CIRCUIT_PURPOSE_REND_POINT_WAITING &&
        ! memcmp(circ->rend_cookie, cookie, REND_COOKIE_LEN) )
      return circ;
  }
  return NULL;
}

546
/** Return a circuit that is open, has specified <b>purpose</b>,
547
548
549
 * has a timestamp_dirty value of 0, is uptime/capacity/internal
 * if required, and if info is defined, does not already use info
 * as any of its hops; or NULL if no circuit fits this description.
550
 *
551
552
 * Return need_uptime circuits if that is requested; and if it's not
 * requested, return non-uptime circuits if possible, else either.
553
 *
554
 * Only return internal circuits if that is requested.
555
556
 */
circuit_t *
557
558
559
circuit_find_to_cannibalize(uint8_t purpose, extend_info_t *info,
                            int need_uptime,
                            int need_capacity, int internal)
560
{
561
  circuit_t *circ;
562
  circuit_t *best=NULL;
563

564
  debug(LD_CIRC,"Hunting for a circ to cannibalize: purpose %d, uptime %d, capacity %d, internal %d", purpose, need_uptime, need_capacity, internal);
565
566

  for (circ=global_circuitlist; circ; circ = circ->next) {
567
568
569
570
571
    if (CIRCUIT_IS_ORIGIN(circ) &&
        circ->state == CIRCUIT_STATE_OPEN &&
        !circ->marked_for_close &&
        circ->purpose == purpose &&
        !circ->timestamp_dirty &&
572
573
        (!need_uptime || circ->build_state->need_uptime) &&
        (!need_capacity || circ->build_state->need_capacity) &&
574
        (internal == circ->build_state->is_internal)) {
575
576
577
578
579
580
581
582
583
584
      if (info) {
        /* need to make sure we don't duplicate hops */
        crypt_path_t *hop = circ->cpath;
        do {
          if (!memcmp(hop->extend_info->identity_digest,
                      info->identity_digest, DIGEST_LEN))
            goto next;
          hop=hop->next;
        } while (hop!=circ->cpath);
      }
585
586
      if (!best || (best->build_state->need_uptime && !need_uptime))
        best = circ;
587
      next: ;
588
    }
589
  }
590
  return best;
591
592
}

593
594
/** Go through the circuitlist; mark-for-close each circuit that starts
 *  at us but has not yet been used. */
595
596
597
void
circuit_mark_all_unused_circs(void)
{
598
599
600
601
602
603
604
605
606
607
  circuit_t *circ;

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

608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
/** 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;
  }
}

629
630
631
632
/** Mark <b>circ</b> to be closed next time we call
 * circuit_close_all_marked(). Do any cleanup needed:
 *   - If state is onionskin_pending, remove circ from the onion_pending
 *     list.
Roger Dingledine's avatar
Roger Dingledine committed
633
634
 *   - If circ isn't open yet: call circuit_build_failed() if we're
 *     the origin, and in either case call circuit_rep_hist_note_result()
635
636
637
638
639
640
641
642
643
 *     to note stats.
 *   - If purpose is C_INTRODUCE_ACK_WAIT, remove the intro point we
 *     just tried from our list of intro points for that service
 *     descriptor.
 *   - Send appropriate destroys and edge_destroys for conns and
 *     streams attached to circ.
 *   - If circ->rend_splice is set (we are the midpoint of a joined
 *     rendezvous stream), then mark the other circuit to close as well.
 */
644
645
void
_circuit_mark_for_close(circuit_t *circ, int line, const char *file)
646
{
647
648
649
  connection_t *conn;

  assert_circuit_ok(circ);
650
651
652
653
  tor_assert(line);
  tor_assert(file);

  if (circ->marked_for_close) {
654
    log(LOG_WARN,LD_BUG,
655
        "Duplicate call to circuit_mark_for_close at %s:%d"
656
        " (first at %s:%d)", file, line,
657
658
659
        circ->marked_for_close_file, circ->marked_for_close);
    return;
  }
660

661
  if (circ->state == CIRCUIT_STATE_ONIONSKIN_PENDING) {
662
663
664
665
666
667
668
    onion_pending_remove(circ);
  }
  /* If the circuit ever became OPEN, we sent it to the reputation history
   * module then.  If it isn't OPEN, we send it there now to remember which
   * links worked and which didn't.
   */
  if (circ->state != CIRCUIT_STATE_OPEN) {
669
    if (CIRCUIT_IS_ORIGIN(circ)) {
670
      circuit_build_failed(circ); /* take actions if necessary */
671
    }
672
673
    circuit_rep_hist_note_result(circ);
  }
674
675
676
677
  if (circ->state == CIRCUIT_STATE_OR_WAIT) {
    if (circuits_pending_or_conns)
      smartlist_remove(circuits_pending_or_conns, circ);
  }
678
679
680
681
  if (CIRCUIT_IS_ORIGIN(circ)) {
    control_event_circuit_status(circ,
     (circ->state == CIRCUIT_STATE_OPEN)?CIRC_EVENT_CLOSED:CIRC_EVENT_FAILED);
  }
682
683
  if (circ->purpose == CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT) {
    tor_assert(circ->state == CIRCUIT_STATE_OPEN);
684
    tor_assert(circ->build_state->chosen_exit);
685
    /* treat this like getting a nack from it */
686
    info(LD_REND,"Failed intro circ %s to %s (awaiting ack). Removing from descriptor.",
687
688
689
690
           safe_str(circ->rend_query),
           safe_str(build_state_get_exit_nickname(circ->build_state)));
    rend_client_remove_intro_point(circ->build_state->chosen_exit,
                                   circ->rend_query);
691
692
  }

693
  if (circ->n_conn)
694
    connection_send_destroy(circ->n_circ_id, circ->n_conn);
695
  for (conn=circ->n_streams; conn; conn=conn->next_stream)
696
    connection_edge_destroy(circ->n_circ_id, conn);
697
  while (circ->resolving_streams) {
698
699
    conn = circ->resolving_streams;
    circ->resolving_streams = conn->next_stream;
700
701
702
703
    if (!conn->marked_for_close) {
      /* The other side will see a DESTROY, and infer that the connections
       * are closing because the circuit is getting torn down.  No need
       * to send an end cell*/
704
      conn->has_sent_end = 1; /* we're closing the circuit, nothing to send to */
705
      connection_mark_for_close(conn);
706
    }
707
    conn->on_circuit = NULL;
708
  }
709
  if (circ->p_conn)
710
    connection_send_destroy(circ->p_circ_id, circ->p_conn);
711
  for (conn=circ->p_streams; conn; conn=conn->next_stream)
712
713
    connection_edge_destroy(circ->p_circ_id, conn);

714
715
  circ->marked_for_close = line;
  circ->marked_for_close_file = file;
716
717
718
719
720
721
722
723
724
725
726

  if (circ->rend_splice && !circ->rend_splice->marked_for_close) {
    /* do this after marking this circuit, to avoid infinite recursion. */
    circuit_mark_for_close(circ->rend_splice);
    circ->rend_splice = NULL;
  }
}

/** Verify that cpath layer <b>cp</b> has all of its invariants
 * correct. Trigger an assert if anything is invalid.
 */
727
728
void
assert_cpath_layer_ok(const crypt_path_t *cp)
729
730
731
{
//  tor_assert(cp->addr); /* these are zero for rendezvous extra-hops */
//  tor_assert(cp->port);
732
733
  tor_assert(cp);
  tor_assert(cp->magic == CRYPT_PATH_MAGIC);
734
  switch (cp->state)
735
736
    {
    case CPATH_STATE_OPEN:
737
738
739
740
      tor_assert(cp->f_crypto);
      tor_assert(cp->b_crypto);
      /* fall through */
    case CPATH_STATE_CLOSED:
741
      tor_assert(!cp->dh_handshake_state);
742
743
      break;
    case CPATH_STATE_AWAITING_KEYS:
744
      /* tor_assert(cp->dh_handshake_state); */
745
746
      break;
    default:
747
      log_fn(LOG_ERR, LD_BUG, "Unexpected state %d", cp->state);
748
749
750
751
752
753
754
755
756
757
      tor_assert(0);
    }
  tor_assert(cp->package_window >= 0);
  tor_assert(cp->deliver_window >= 0);
}

/** Verify that cpath <b>cp</b> has all of its invariants
 * correct. Trigger an assert if anything is invalid.
 */
static void
Nick Mathewson's avatar
Nick Mathewson committed
758
assert_cpath_ok(const crypt_path_t *cp)
759
{
Nick Mathewson's avatar
Nick Mathewson committed
760
  const crypt_path_t *start = cp;
761

Nick Mathewson's avatar
Nick Mathewson committed
762
  do {
763
764
    assert_cpath_layer_ok(cp);
    /* layers must be in sequence of: "open* awaiting? closed*" */
Nick Mathewson's avatar
Nick Mathewson committed
765
766
767
768
769
    if (cp != start) {
      if (cp->state == CPATH_STATE_AWAITING_KEYS) {
        tor_assert(cp->prev->state == CPATH_STATE_OPEN);
      } else if (cp->state == CPATH_STATE_OPEN) {
        tor_assert(cp->prev->state == CPATH_STATE_OPEN);
770
771
772
      }
    }
    cp = cp->next;
Nick Mathewson's avatar
Nick Mathewson committed
773
774
    tor_assert(cp);
  } while (cp != start);
775
776
777
778
779
}

/** Verify that circuit <b>c</b> has all of its invariants
 * correct. Trigger an assert if anything is invalid.
 */
780
781
void
assert_circuit_ok(const circuit_t *c)
782
783
784
785
786
787
788
789
{
  connection_t *conn;

  tor_assert(c);
  tor_assert(c->magic == CIRCUIT_MAGIC);
  tor_assert(c->purpose >= _CIRCUIT_PURPOSE_MIN &&
             c->purpose <= _CIRCUIT_PURPOSE_MAX);

790
  if (c->n_conn) {
791
    tor_assert(c->n_conn->type == CONN_TYPE_OR);
792
    tor_assert(!memcmp(c->n_conn->identity_digest, c->n_conn_id_digest, DIGEST_LEN));
793
794
    if (c->n_circ_id)
      tor_assert(c == circuit_get_by_circid_orconn(c->n_circ_id, c->n_conn));
795
  }
796
  if (c->p_conn) {
797
    tor_assert(c->p_conn->type == CONN_TYPE_OR);
798
799
800
    if (c->p_circ_id)
      tor_assert(c == circuit_get_by_circid_orconn(c->p_circ_id, c->p_conn));
  }
801
802
803
804
805
806
807
808
  for (conn = c->p_streams; conn; conn = conn->next_stream)
    tor_assert(conn->type == CONN_TYPE_AP);
  for (conn = c->n_streams; conn; conn = conn->next_stream)
    tor_assert(conn->type == CONN_TYPE_EXIT);

  tor_assert(c->deliver_window >= 0);
  tor_assert(c->package_window >= 0);
  if (c->state == CIRCUIT_STATE_OPEN) {
809
    tor_assert(!c->onionskin);
810
811
812
813
814
815
816
817
818
819
820
821
822
823
    if (c->cpath) {
      tor_assert(CIRCUIT_IS_ORIGIN(c));
      tor_assert(!c->n_crypto);
      tor_assert(!c->p_crypto);
      tor_assert(!c->n_digest);
      tor_assert(!c->p_digest);
    } else {
      tor_assert(!CIRCUIT_IS_ORIGIN(c));
      tor_assert(c->n_crypto);
      tor_assert(c->p_crypto);
      tor_assert(c->n_digest);
      tor_assert(c->p_digest);
    }
  }
824
825
826
827
828
829
830
  if (c->state == CIRCUIT_STATE_OR_WAIT && !c->marked_for_close) {
    tor_assert(circuits_pending_or_conns &&
               smartlist_isin(circuits_pending_or_conns, c));
  } else {
    tor_assert(!circuits_pending_or_conns || !
               !smartlist_isin(circuits_pending_or_conns, c));
  }
831
  if (c->cpath) {
Nick Mathewson's avatar
Nick Mathewson committed
832
    assert_cpath_ok(c->cpath);
833
834
835
836
837
838
839
840
841
842
843
  }
  if (c->purpose == CIRCUIT_PURPOSE_REND_ESTABLISHED) {
    if (!c->marked_for_close) {
      tor_assert(c->rend_splice);
      tor_assert(c->rend_splice->rend_splice == c);
    }
    tor_assert(c->rend_splice != c);
  } else {
    tor_assert(!c->rend_splice);
  }
}
844