circuitbuild.c 104 KB
Newer Older
Roger Dingledine's avatar
Roger Dingledine committed
1
2
/* Copyright (c) 2001 Matej Pfajfar.
 * Copyright (c) 2001-2004, Roger Dingledine.
3
 * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
Nick Mathewson's avatar
Nick Mathewson committed
4
 * Copyright (c) 2007-2018, The Tor Project, Inc. */
5
6
7
8
/* See LICENSE for licensing information */

/**
 * \file circuitbuild.c
9
10
11
 *
 * \brief Implements the details of building circuits (by chosing paths,
 * constructing/sending create/extend cells, and so on).
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 *
 * On the client side, this module handles launching circuits. Circuit
 * launches are srtarted from circuit_establish_circuit(), called from
 * circuit_launch_by_extend_info()).  To choose the path the circuit will
 * take, onion_extend_cpath() calls into a maze of node selection functions.
 *
 * Once the circuit is ready to be launched, the first hop is treated as a
 * special case with circuit_handle_first_hop(), since it might need to open a
 * channel.  As the channel opens, and later as CREATED and RELAY_EXTENDED
 * cells arrive, the client will invoke circuit_send_next_onion_skin() to send
 * CREATE or RELAY_EXTEND cells.
 *
 * On the server side, this module also handles the logic of responding to
 * RELAY_EXTEND requests, using circuit_extend().
26
27
 **/

28
29
#define CIRCUITBUILD_PRIVATE

30
31
32
33
#include "core/or/or.h"
#include "feature/client/bridges.h"
#include "core/or/channel.h"
#include "feature/client/circpathbias.h"
34
#define CIRCUITBUILD_PRIVATE
35
36
37
38
39
40
41
42
43
44
45
#include "core/or/circuitbuild.h"
#include "core/or/circuitlist.h"
#include "core/or/circuitstats.h"
#include "core/or/circuituse.h"
#include "core/or/command.h"
#include "app/config/config.h"
#include "app/config/confparse.h"
#include "core/mainloop/connection.h"
#include "core/or/connection_edge.h"
#include "core/or/connection_or.h"
#include "feature/control/control.h"
46
#include "lib/crypt_ops/crypto_rand.h"
47
48
49
#include "feature/dircache/directory.h"
#include "feature/client/entrynodes.h"
#include "core/crypto/hs_ntor.h"
50
#include "core/mainloop/mainloop.h"
51
52
53
#include "feature/nodelist/microdesc.h"
#include "feature/nodelist/networkstatus.h"
#include "feature/nodelist/nodelist.h"
54
55
#include "core/or/onion.h"
#include "core/crypto/onion_crypto.h"
56
57
58
59
60
61
62
63
#include "core/crypto/onion_tap.h"
#include "core/crypto/onion_fast.h"
#include "core/or/policies.h"
#include "core/or/relay.h"
#include "core/crypto/relay_crypto.h"
#include "feature/rend/rendcommon.h"
#include "feature/stats/rephist.h"
#include "feature/relay/router.h"
64
#include "feature/nodelist/node_select.h"
65
66
67
68
#include "feature/nodelist/routerlist.h"
#include "feature/nodelist/routerparse.h"
#include "feature/nodelist/routerset.h"
#include "feature/client/transports.h"
69

70
71
72
73
74
75
76
77
78
79
#include "core/or/cell_st.h"
#include "core/or/cpath_build_state_st.h"
#include "core/or/entry_connection_st.h"
#include "core/or/extend_info_st.h"
#include "feature/nodelist/node_st.h"
#include "core/or/or_circuit_st.h"
#include "core/or/origin_circuit_st.h"
#include "feature/nodelist/microdesc_st.h"
#include "feature/nodelist/routerinfo_st.h"
#include "feature/nodelist/routerstatus_st.h"
80

81
static channel_t * channel_connect_for_circuit(const tor_addr_t *addr,
82
83
84
                                            uint16_t port,
                                            const char *id_digest,
                                            const ed25519_public_key_t *ed_id);
85
static int circuit_deliver_create_cell(circuit_t *circ,
86
87
                                       const create_cell_t *create_cell,
                                       int relayed);
88
static crypt_path_t *onion_next_hop_in_cpath(crypt_path_t *cpath);
Mike Perry's avatar
Mike Perry committed
89
STATIC int onion_append_hop(crypt_path_t **head_ptr, extend_info_t *choice);
90
91
92
93
static int circuit_send_first_onion_skin(origin_circuit_t *circ);
static int circuit_build_no_more_hops(origin_circuit_t *circ);
static int circuit_send_intermediate_onion_skin(origin_circuit_t *circ,
                                                crypt_path_t *hop);
94
95
96
97
static const node_t *choose_good_middle_server(uint8_t purpose,
                          cpath_build_state_t *state,
                          crypt_path_t *head,
                          int cur_len);
98

99
100
101
102
103
104
/** This function tries to get a channel to the specified endpoint,
 * and then calls command_setup_channel() to give it the right
 * callbacks.
 */
static channel_t *
channel_connect_for_circuit(const tor_addr_t *addr, uint16_t port,
105
106
                            const char *id_digest,
                            const ed25519_public_key_t *ed_id)
107
108
109
{
  channel_t *chan;

110
  chan = channel_connect(addr, port, id_digest, ed_id);
111
112
113
114
115
  if (chan) command_setup_channel(chan);

  return chan;
}

116
117
118
/** Search for a value for circ_id that we can use on <b>chan</b> for an
 * outbound circuit, until we get a circ_id that is not in use by any other
 * circuit on that conn.
Mike Perry's avatar
Mike Perry committed
119
 *
120
 * Return it, or 0 if can't get a unique circ_id.
Mike Perry's avatar
Mike Perry committed
121
 */
122
STATIC circid_t
123
get_unique_circ_id_by_chan(channel_t *chan)
124
{
125
126
127
128
129
130
/* This number is chosen somewhat arbitrarily; see comment below for more
 * info.  When the space is 80% full, it gives a one-in-a-million failure
 * chance; when the space is 90% full, it gives a one-in-850 chance; and when
 * the space is 95% full, it gives a one-in-26 failure chance.  That seems
 * okay, though you could make a case IMO for anything between N=32 and
 * N=256. */
131
#define MAX_CIRCID_ATTEMPTS 64
132
  int in_use;
Nick Mathewson's avatar
Nick Mathewson committed
133
  unsigned n_with_circ = 0, n_pending_destroy = 0, n_weird_pending_destroy = 0;
134
135
  circid_t test_circ_id;
  circid_t attempts=0;
136
  circid_t high_bit, max_range, mask;
Nick Mathewson's avatar
Nick Mathewson committed
137
138
  int64_t pending_destroy_time_total = 0;
  int64_t pending_destroy_time_max = 0;
139
140
141
142
143
144
145

  tor_assert(chan);

  if (chan->circ_id_type == CIRC_ID_TYPE_NEITHER) {
    log_warn(LD_BUG,
             "Trying to pick a circuit ID for a connection from "
             "a client with no identity.");
146
    return 0;
147
  }
148
149
  max_range = (chan->wide_circ_ids) ? (1u<<31) : (1u<<15);
  mask = max_range - 1;
150
  high_bit = (chan->circ_id_type == CIRC_ID_TYPE_HIGHER) ? max_range : 0;
151
  do {
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
    if (++attempts > MAX_CIRCID_ATTEMPTS) {
      /* Make sure we don't loop forever because all circuit IDs are used.
       *
       * Once, we would try until we had tried every possible circuit ID.  But
       * that's quite expensive.  Instead, we try MAX_CIRCID_ATTEMPTS random
       * circuit IDs, and then give up.
       *
       * This potentially causes us to give up early if our circuit ID space
       * is nearly full.  If we have N circuit IDs in use, then we will reject
       * a new circuit with probability (N / max_range) ^ MAX_CIRCID_ATTEMPTS.
       * This means that in practice, a few percent of our circuit ID capacity
       * will go unused.
       *
       * The alternative here, though, is to do a linear search over the
       * whole circuit ID space every time we extend a circuit, which is
       * not so great either.
168
       */
Nick Mathewson's avatar
Nick Mathewson committed
169
170
171
172
173
174
175
176
      int64_t queued_destroys;
      char *m = rate_limit_log(&chan->last_warned_circ_ids_exhausted,
                               approx_time());
      if (m == NULL)
        return 0; /* This message has been rate-limited away. */
      if (n_pending_destroy)
        pending_destroy_time_total /= n_pending_destroy;
      log_warn(LD_CIRC,"No unused circIDs found on channel %s wide "
177
                 "circID support, with %u inbound and %u outbound circuits. "
178
                 "Found %u circuit IDs in use by circuits, and %u with "
Nick Mathewson's avatar
Nick Mathewson committed
179
180
181
182
183
                 "pending destroy cells. (%u of those were marked bogusly.) "
                 "The ones with pending destroy cells "
                 "have been marked unusable for an average of %ld seconds "
                 "and a maximum of %ld seconds. This channel is %ld seconds "
                 "old. Failing a circuit.%s",
184
                 chan->wide_circ_ids ? "with" : "without",
185
                 chan->num_p_circuits, chan->num_n_circuits,
Nick Mathewson's avatar
Nick Mathewson committed
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
                 n_with_circ, n_pending_destroy, n_weird_pending_destroy,
                 (long)pending_destroy_time_total,
                 (long)pending_destroy_time_max,
                 (long)(approx_time() - chan->timestamp_created),
                 m);
      tor_free(m);

      if (!chan->cmux) {
        /* This warning should be impossible. */
        log_warn(LD_BUG, "  This channel somehow has no cmux on it!");
        return 0;
      }

      /* analysis so far on 12184 suggests that we're running out of circuit
         IDs because it looks like we have too many pending destroy
         cells. Let's see how many we really have pending.
      */
      queued_destroys = circuitmux_count_queued_destroy_cells(chan,
                                                              chan->cmux);

      log_warn(LD_CIRC, "  Circuitmux on this channel has %u circuits, "
207
               "of which %u are active. It says it has %"PRId64
Nick Mathewson's avatar
Nick Mathewson committed
208
209
210
               " destroy cells queued.",
               circuitmux_num_circuits(chan->cmux),
               circuitmux_num_active_circuits(chan->cmux),
211
               (queued_destroys));
Nick Mathewson's avatar
Nick Mathewson committed
212
213
214
215
216
217
218
219

      /* Change this into "if (1)" in order to get more information about
       * possible failure modes here.  You'll need to know how to use gdb with
       * Tor: this will make Tor exit with an assertion failure if the cmux is
       * corrupt. */
      if (0)
        circuitmux_assert_okay(chan->cmux);

220
221
      channel_dump_statistics(chan, LOG_WARN);

Mike Perry's avatar
Mike Perry committed
222
223
      return 0;
    }
224

225
226
227
228
229
    do {
      crypto_rand((char*) &test_circ_id, sizeof(test_circ_id));
      test_circ_id &= mask;
    } while (test_circ_id == 0);

230
    test_circ_id |= high_bit;
231
232
233
234

    in_use = circuit_id_in_use_on_channel(test_circ_id, chan);
    if (in_use == 1)
      ++n_with_circ;
Nick Mathewson's avatar
Nick Mathewson committed
235
236
    else if (in_use == 2) {
      time_t since_when;
237
      ++n_pending_destroy;
Nick Mathewson's avatar
Nick Mathewson committed
238
239
240
241
242
243
244
245
246
247
248
      since_when =
        circuit_id_when_marked_unusable_on_channel(test_circ_id, chan);
      if (since_when) {
        time_t waiting = approx_time() - since_when;
        pending_destroy_time_total += waiting;
        if (waiting > pending_destroy_time_max)
          pending_destroy_time_max = waiting;
      } else {
        ++n_weird_pending_destroy;
      }
    }
249
  } while (in_use);
250
  return test_circ_id;
251
252
}

253
254
255
256
257
258
/** If <b>verbose</b> is false, allocate and return a comma-separated list of
 * the currently built elements of <b>circ</b>. If <b>verbose</b> is true, also
 * list information about link status in a more verbose format using spaces.
 * If <b>verbose_names</b> is false, give nicknames for Named routers and hex
 * digests for others; if <b>verbose_names</b> is true, use $DIGEST=Name style
 * names.
Mike Perry's avatar
Mike Perry committed
259
 */
260
261
static char *
circuit_list_path_impl(origin_circuit_t *circ, int verbose, int verbose_names)
Mike Perry's avatar
Mike Perry committed
262
{
263
264
265
266
  crypt_path_t *hop;
  smartlist_t *elements;
  const char *states[] = {"closed", "waiting for keys", "open"};
  char *s;
267

268
  elements = smartlist_new();
Mike Perry's avatar
Mike Perry committed
269

270
271
272
273
274
275
276
277
278
  if (verbose) {
    const char *nickname = build_state_get_exit_nickname(circ->build_state);
    smartlist_add_asprintf(elements, "%s%s circ (length %d%s%s):",
                 circ->build_state->is_internal ? "internal" : "exit",
                 circ->build_state->need_uptime ? " (high-uptime)" : "",
                 circ->build_state->desired_path_len,
                 circ->base_.state == CIRCUIT_STATE_OPEN ? "" : ", last hop ",
                 circ->base_.state == CIRCUIT_STATE_OPEN ? "" :
                 (nickname?nickname:"*unnamed*"));
279
280
  }

281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
  hop = circ->cpath;
  do {
    char *elt;
    const char *id;
    const node_t *node;
    if (!hop)
      break;
    if (!verbose && hop->state != CPATH_STATE_OPEN)
      break;
    if (!hop->extend_info)
      break;
    id = hop->extend_info->identity_digest;
    if (verbose_names) {
      elt = tor_malloc(MAX_VERBOSE_NICKNAME_LEN+1);
      if ((node = node_get_by_id(id))) {
        node_get_verbose_nickname(node, elt);
      } else if (is_legal_nickname(hop->extend_info->nickname)) {
        elt[0] = '$';
        base16_encode(elt+1, HEX_DIGEST_LEN+1, id, DIGEST_LEN);
        elt[HEX_DIGEST_LEN+1]= '~';
        strlcpy(elt+HEX_DIGEST_LEN+2,
                hop->extend_info->nickname, MAX_NICKNAME_LEN+1);
      } else {
        elt[0] = '$';
        base16_encode(elt+1, HEX_DIGEST_LEN+1, id, DIGEST_LEN);
      }
    } else { /* ! verbose_names */
308
309
310
      elt = tor_malloc(HEX_DIGEST_LEN+2);
      elt[0] = '$';
      base16_encode(elt+1, HEX_DIGEST_LEN+1, id, DIGEST_LEN);
311
312
313
314
315
316
317
318
319
320
321
    }
    tor_assert(elt);
    if (verbose) {
      tor_assert(hop->state <= 2);
      smartlist_add_asprintf(elements,"%s(%s)",elt,states[hop->state]);
      tor_free(elt);
    } else {
      smartlist_add(elements, elt);
    }
    hop = hop->next;
  } while (hop != circ->cpath);
322

323
324
325
326
  s = smartlist_join_strings(elements, verbose?" ":",", 0, NULL);
  SMARTLIST_FOREACH(elements, char*, cp, tor_free(cp));
  smartlist_free(elements);
  return s;
Mike Perry's avatar
Mike Perry committed
327
328
}

329
330
331
332
333
334
335
/** If <b>verbose</b> is false, allocate and return a comma-separated
 * list of the currently built elements of <b>circ</b>.  If
 * <b>verbose</b> is true, also list information about link status in
 * a more verbose format using spaces.
 */
char *
circuit_list_path(origin_circuit_t *circ, int verbose)
336
{
337
  return circuit_list_path_impl(circ, verbose, 0);
338
339
}

340
341
/** Allocate and return a comma-separated list of the currently built elements
 * of <b>circ</b>, giving each as a verbose nickname.
Mike Perry's avatar
Mike Perry committed
342
 */
343
344
char *
circuit_list_path_for_controller(origin_circuit_t *circ)
Mike Perry's avatar
Mike Perry committed
345
{
346
  return circuit_list_path_impl(circ, 0, 1);
Mike Perry's avatar
Mike Perry committed
347
348
}

349
350
351
352
353
354
/** Log, at severity <b>severity</b>, the nicknames of each router in
 * <b>circ</b>'s cpath. Also log the length of the cpath, and the intended
 * exit point.
 */
void
circuit_log_path(int severity, unsigned int domain, origin_circuit_t *circ)
355
{
356
357
358
  char *s = circuit_list_path(circ,1);
  tor_log(severity,domain,"%s",s);
  tor_free(s);
359
360
}

361
/** Return 1 iff every node in circ's cpath definitely supports ntor. */
362
363
364
static int
circuit_cpath_supports_ntor(const origin_circuit_t *circ)
{
365
  crypt_path_t *head, *cpath;
366

367
  cpath = head = circ->cpath;
368
  do {
369
370
371
372
    /* if the extend_info is missing, we can't tell if it supports ntor */
    if (!cpath->extend_info) {
      return 0;
    }
373

374
375
376
377
    /* if the key is blank, it definitely doesn't support ntor */
    if (!extend_info_supports_ntor(cpath->extend_info)) {
      return 0;
    }
378
379
380
    cpath = cpath->next;
  } while (cpath != head);

381
  return 1;
382
383
}

384
385
386
387
/** Pick all the entries in our cpath. Stop and return 0 when we're
 * happy, or return -1 if an error occurs. */
static int
onion_populate_cpath(origin_circuit_t *circ)
Mike Perry's avatar
Mike Perry committed
388
{
389
  int r = 0;
390

391
392
393
  /* onion_extend_cpath assumes these are non-NULL */
  tor_assert(circ);
  tor_assert(circ->build_state);
394

395
396
  while (r == 0) {
    r = onion_extend_cpath(circ);
397
398
399
400
    if (r < 0) {
      log_info(LD_CIRC,"Generating cpath hop failed.");
      return -1;
    }
401
  }
402

403
404
  /* The path is complete */
  tor_assert(r == 1);
405

406
407
408
409
410
411
412
  /* Does every node in this path support ntor? */
  int path_supports_ntor = circuit_cpath_supports_ntor(circ);

  /* We would like every path to support ntor, but we have to allow for some
   * edge cases. */
  tor_assert(circuit_get_cpath_len(circ));
  if (circuit_can_use_tap(circ)) {
David Goulet's avatar
David Goulet committed
413
414
415
416
    /* Circuits from clients to intro points, and hidden services to rend
     * points do not support ntor, because the hidden service protocol does
     * not include ntor onion keys. This is also true for Single Onion
     * Services. */
417
418
    return 0;
  }
419

420
421
422
423
424
425
426
427
428
429
430
  if (circuit_get_cpath_len(circ) == 1) {
    /* Allow for bootstrapping: when we're fetching directly from a fallback,
     * authority, or bridge, we have no way of knowing its ntor onion key
     * before we connect to it. So instead, we try connecting, and end up using
     * CREATE_FAST. */
    tor_assert(circ->cpath);
    tor_assert(circ->cpath->extend_info);
    const node_t *node = node_get_by_id(
                                    circ->cpath->extend_info->identity_digest);
    /* If we don't know the node and its descriptor, we must be bootstrapping.
     */
431
    if (!node || !node_has_preferred_descriptor(node, 1)) {
432
      return 0;
433
    }
434
  }
435

436
437
438
439
440
441
442
443
  if (BUG(!path_supports_ntor)) {
    /* If we're building a multi-hop path, and it's not one of the HS or
     * bootstrapping exceptions, and it doesn't support ntor, something has
     * gone wrong. */
    return -1;
  }

  return 0;
Mike Perry's avatar
Mike Perry committed
444
445
}

446
447
448
449
450
/** Create and return a new origin circuit. Initialize its purpose and
 * build-state based on our arguments.  The <b>flags</b> argument is a
 * bitfield of CIRCLAUNCH_* flags. */
origin_circuit_t *
origin_circuit_init(uint8_t purpose, int flags)
Mike Perry's avatar
Mike Perry committed
451
{
452
453
454
455
456
457
458
459
460
461
462
463
464
465
  /* sets circ->p_circ_id and circ->p_chan */
  origin_circuit_t *circ = origin_circuit_new();
  circuit_set_state(TO_CIRCUIT(circ), CIRCUIT_STATE_CHAN_WAIT);
  circ->build_state = tor_malloc_zero(sizeof(cpath_build_state_t));
  circ->build_state->onehop_tunnel =
    ((flags & CIRCLAUNCH_ONEHOP_TUNNEL) ? 1 : 0);
  circ->build_state->need_uptime =
    ((flags & CIRCLAUNCH_NEED_UPTIME) ? 1 : 0);
  circ->build_state->need_capacity =
    ((flags & CIRCLAUNCH_NEED_CAPACITY) ? 1 : 0);
  circ->build_state->is_internal =
    ((flags & CIRCLAUNCH_IS_INTERNAL) ? 1 : 0);
  circ->base_.purpose = purpose;
  return circ;
Mike Perry's avatar
Mike Perry committed
466
467
}

468
469
470
/** Build a new circuit for <b>purpose</b>. If <b>exit</b>
 * is defined, then use that as your exit router, else choose a suitable
 * exit node.
Mike Perry's avatar
Mike Perry committed
471
 *
472
473
 * Also launch a connection to the first OR in the chosen path, if
 * it's not open already.
Mike Perry's avatar
Mike Perry committed
474
 */
475
origin_circuit_t *
476
circuit_establish_circuit(uint8_t purpose, extend_info_t *exit_ei, int flags)
Mike Perry's avatar
Mike Perry committed
477
{
478
479
  origin_circuit_t *circ;
  int err_reason = 0;
480
481
482
483
484
  int is_hs_v3_rp_circuit = 0;

  if (flags & CIRCLAUNCH_IS_V3_RP) {
    is_hs_v3_rp_circuit = 1;
  }
485

486
  circ = origin_circuit_init(purpose, flags);
Mike Perry's avatar
Mike Perry committed
487

488
  if (onion_pick_cpath_exit(circ, exit_ei, is_hs_v3_rp_circuit) < 0 ||
489
490
491
      onion_populate_cpath(circ) < 0) {
    circuit_mark_for_close(TO_CIRCUIT(circ), END_CIRC_REASON_NOPATH);
    return NULL;
492
493
  }

494
495
496
497
498
499
500
  control_event_circuit_status(circ, CIRC_EVENT_LAUNCHED, 0);

  if ((err_reason = circuit_handle_first_hop(circ)) < 0) {
    circuit_mark_for_close(TO_CIRCUIT(circ), -err_reason);
    return NULL;
  }
  return circ;
Mike Perry's avatar
Mike Perry committed
501
502
}

503
504
505
506
507
508
509
/** Return the guard state associated with <b>circ</b>, which may be NULL. */
circuit_guard_state_t *
origin_circuit_get_guard_state(origin_circuit_t *circ)
{
  return circ->guard_state;
}

510
511
512
513
514
515
/** Start establishing the first hop of our circuit. Figure out what
 * OR we should connect to, and if necessary start the connection to
 * it. If we're already connected, then send the 'create' cell.
 * Return 0 for ok, -reason if circ should be marked-for-close. */
int
circuit_handle_first_hop(origin_circuit_t *circ)
Mike Perry's avatar
Mike Perry committed
516
{
517
518
519
520
521
  crypt_path_t *firsthop;
  channel_t *n_chan;
  int err_reason = 0;
  const char *msg = NULL;
  int should_launch = 0;
522
  const or_options_t *options = get_options();
523

524
525
526
  firsthop = onion_next_hop_in_cpath(circ->cpath);
  tor_assert(firsthop);
  tor_assert(firsthop->extend_info);
527

528
529
530
531
532
533
  /* Some bridges are on private addresses. Others pass a dummy private
   * address to the pluggable transport, which ignores it.
   * Deny the connection if:
   * - the address is internal, and
   * - we're not connecting to a configured bridge, and
   * - we're not configured to allow extends to private addresses. */
534
  if (tor_addr_is_internal(&firsthop->extend_info->addr, 0) &&
535
536
      !extend_info_is_a_configured_bridge(firsthop->extend_info) &&
      !options->ExtendAllowPrivateAddresses) {
537
538
539
540
541
    log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
           "Client asked me to connect directly to a private address");
    return -END_CIRC_REASON_TORPROTOCOL;
  }

542
543
544
545
  /* now see if we're already connected to the first OR in 'route' */
  log_debug(LD_CIRC,"Looking for firsthop '%s'",
            fmt_addrport(&firsthop->extend_info->addr,
                         firsthop->extend_info->port));
546

547
  n_chan = channel_get_for_extend(firsthop->extend_info->identity_digest,
548
                                  &firsthop->extend_info->ed_identity,
549
550
551
                                  &firsthop->extend_info->addr,
                                  &msg,
                                  &should_launch);
552

553
554
555
556
557
558
  if (!n_chan) {
    /* not currently connected in a useful way. */
    log_info(LD_CIRC, "Next router is %s: %s",
             safe_str_client(extend_info_describe(firsthop->extend_info)),
             msg?msg:"???");
    circ->base_.n_hop = extend_info_dup(firsthop->extend_info);
559

560
561
562
563
564
565
    if (should_launch) {
      if (circ->build_state->onehop_tunnel)
        control_event_bootstrap(BOOTSTRAP_STATUS_CONN_DIR, 0);
      n_chan = channel_connect_for_circuit(
          &firsthop->extend_info->addr,
          firsthop->extend_info->port,
566
567
          firsthop->extend_info->identity_digest,
          &firsthop->extend_info->ed_identity);
568
569
570
      if (!n_chan) { /* connect failed, forget the whole thing */
        log_info(LD_CIRC,"connect to firsthop failed. Closing.");
        return -END_CIRC_REASON_CONNECTFAILED;
571
572
      }
    }
573

574
575
576
577
578
579
580
581
582
583
584
585
    log_debug(LD_CIRC,"connecting in progress (or finished). Good.");
    /* return success. The onion/circuit/etc will be taken care of
     * automatically (may already have been) whenever n_chan reaches
     * OR_CONN_STATE_OPEN.
     */
    return 0;
  } else { /* it's already open. use it. */
    tor_assert(!circ->base_.n_hop);
    circ->base_.n_chan = n_chan;
    log_debug(LD_CIRC,"Conn open. Delivering first onion skin.");
    if ((err_reason = circuit_send_next_onion_skin(circ)) < 0) {
      log_info(LD_CIRC,"circuit_send_next_onion_skin failed.");
586
      circ->base_.n_chan = NULL;
587
      return err_reason;
588
    }
589
  }
590
  return 0;
591
592
}

593
594
/** Find any circuits that are waiting on <b>or_conn</b> to become
 * open and get them to send their create cells forward.
Mike Perry's avatar
Mike Perry committed
595
 *
596
 * Status is 1 if connect succeeded, or 0 if connect failed.
597
 *
Nick Mathewson's avatar
Nick Mathewson committed
598
599
600
 * Close_origin_circuits is 1 if we should close all the origin circuits
 * through this channel, or 0 otherwise.  (This happens when we want to retry
 * an older guard.)
601
 */
Andrea Shepard's avatar
Andrea Shepard committed
602
void
603
circuit_n_chan_done(channel_t *chan, int status, int close_origin_circuits)
Andrea Shepard's avatar
Andrea Shepard committed
604
{
605
606
  smartlist_t *pending_circs;
  int err_reason = 0;
607

608
  tor_assert(chan);
609

610
  log_debug(LD_CIRC,"chan to %s, status=%d",
611
            channel_get_canonical_remote_descr(chan), status);
612

613
614
  pending_circs = smartlist_new();
  circuit_get_all_pending_on_channel(pending_circs, chan);
615

616
617
618
619
620
621
622
623
  SMARTLIST_FOREACH_BEGIN(pending_circs, circuit_t *, circ)
    {
      /* These checks are redundant wrt get_all_pending_on_or_conn, but I'm
       * leaving them in in case it's possible for the status of a circuit to
       * change as we're going down the list. */
      if (circ->marked_for_close || circ->n_chan || !circ->n_hop ||
          circ->state != CIRCUIT_STATE_CHAN_WAIT)
        continue;
624

625
626
627
628
629
630
631
632
633
634
635
636
637
      if (tor_digest_is_zero(circ->n_hop->identity_digest)) {
        /* Look at addr/port. This is an unkeyed connection. */
        if (!channel_matches_extend_info(chan, circ->n_hop))
          continue;
      } else {
        /* We expected a key. See if it's the right one. */
        if (tor_memneq(chan->identity_digest,
                   circ->n_hop->identity_digest, DIGEST_LEN))
          continue;
      }
      if (!status) { /* chan failed; close circ */
        log_info(LD_CIRC,"Channel failed; closing circ.");
        circuit_mark_for_close(circ, END_CIRC_REASON_CHANNEL_CLOSED);
638
639
640
641
642
        continue;
      }
      if (close_origin_circuits && CIRCUIT_IS_ORIGIN(circ)) {
        log_info(LD_CIRC,"Channel deprecated for origin circs; closing circ.");
        circuit_mark_for_close(circ, END_CIRC_REASON_CHANNEL_CLOSED);
643
644
645
646
647
648
649
650
651
        continue;
      }
      log_debug(LD_CIRC, "Found circ, sending create cell.");
      /* circuit_deliver_create_cell will set n_circ_id and add us to
       * chan_circuid_circuit_map, so we don't need to call
       * set_circid_chan here. */
      circ->n_chan = chan;
      extend_info_free(circ->n_hop);
      circ->n_hop = NULL;
652

653
654
655
656
657
658
659
660
661
662
663
      if (CIRCUIT_IS_ORIGIN(circ)) {
        if ((err_reason =
             circuit_send_next_onion_skin(TO_ORIGIN_CIRCUIT(circ))) < 0) {
          log_info(LD_CIRC,
                   "send_next_onion_skin failed; circuit marked for closing.");
          circuit_mark_for_close(circ, -err_reason);
          continue;
          /* XXX could this be bad, eg if next_onion_skin failed because conn
           *     died? */
        }
      } else {
664
665
        /* pull the create cell out of circ->n_chan_create_cell, and send it */
        tor_assert(circ->n_chan_create_cell);
666
        if (circuit_deliver_create_cell(circ, circ->n_chan_create_cell, 1)<0) {
667
668
669
          circuit_mark_for_close(circ, END_CIRC_REASON_RESOURCELIMIT);
          continue;
        }
670
        tor_free(circ->n_chan_create_cell);
671
672
673
674
        circuit_set_state(circ, CIRCUIT_STATE_OPEN);
      }
    }
  SMARTLIST_FOREACH_END(circ);
675

676
  smartlist_free(pending_circs);
677
678
}

679
680
/** Find a new circid that isn't currently in use on the circ->n_chan
 * for the outgoing
681
682
683
684
 * circuit <b>circ</b>, and deliver the cell <b>create_cell</b> to this
 * circuit.  If <b>relayed</b> is true, this is a create cell somebody
 * gave us via an EXTEND cell, so we shouldn't worry if we don't understand
 * it. Return -1 if we failed to find a suitable circid, else return 0.
685
 */
686
static int
687
688
circuit_deliver_create_cell(circuit_t *circ, const create_cell_t *create_cell,
                            int relayed)
689
{
690
691
  cell_t cell;
  circid_t id;
692
  int r;
693
694
695

  tor_assert(circ);
  tor_assert(circ->n_chan);
696
697
698
699
  tor_assert(create_cell);
  tor_assert(create_cell->cell_type == CELL_CREATE ||
             create_cell->cell_type == CELL_CREATE_FAST ||
             create_cell->cell_type == CELL_CREATE2);
700
701
702

  id = get_unique_circ_id_by_chan(circ->n_chan);
  if (!id) {
703
704
705
    static ratelim_t circid_warning_limit = RATELIM_INIT(9600);
    log_fn_ratelim(&circid_warning_limit, LOG_WARN, LD_CIRC,
                   "failed to get unique circID.");
706
    goto error;
707
  }
708

709
  memset(&cell, 0, sizeof(cell_t));
710
711
712
  r = relayed ? create_cell_format_relayed(&cell, create_cell)
              : create_cell_format(&cell, create_cell);
  if (r < 0) {
713
    log_warn(LD_CIRC,"Couldn't format create cell");
714
    goto error;
715
  }
716
717
  log_debug(LD_CIRC,"Chosen circID %u.", (unsigned)id);
  circuit_set_n_circid_chan(circ, id, circ->n_chan);
718
  cell.circ_id = circ->n_circ_id;
719

720
721
  append_cell_to_circuit_queue(circ, circ->n_chan, &cell,
                               CELL_DIRECTION_OUT, 0);
722

723
  if (CIRCUIT_IS_ORIGIN(circ)) {
724
725
    /* Update began timestamp for circuits starting their first hop */
    if (TO_ORIGIN_CIRCUIT(circ)->cpath->state == CPATH_STATE_CLOSED) {
726
      if (!CHANNEL_IS_OPEN(circ->n_chan)) {
727
728
729
730
731
732
733
734
735
        log_warn(LD_CIRC,
                 "Got first hop for a circuit without an opened channel. "
                 "State: %s.", channel_state_to_string(circ->n_chan->state));
        tor_fragile_assert();
      }

      tor_gettimeofday(&circ->timestamp_began);
    }

736
737
    /* mark it so it gets better rate limiting treatment. */
    channel_timestamp_client(circ->n_chan);
Mike Perry's avatar
Mike Perry committed
738
739
  }

740
  return 0;
741
742
743
 error:
  circ->n_chan = NULL;
  return -1;
744
745
}

746
747
748
749
750
/** We've decided to start our reachability testing. If all
 * is set, log this to the user. Return 1 if we did, or 0 if
 * we chose not to log anything. */
int
inform_testing_reachability(void)
751
{
752
  char dirbuf[128];
753
  char *address;
754
755
756
  const routerinfo_t *me = router_get_my_routerinfo();
  if (!me)
    return 0;
757
  address = tor_dup_ip(me->addr);
758
759
  control_event_server_status(LOG_NOTICE,
                              "CHECKING_REACHABILITY ORADDRESS=%s:%d",
760
                              address, me->or_port);
761
762
  if (me->dir_port) {
    tor_snprintf(dirbuf, sizeof(dirbuf), " and DirPort %s:%d",
763
                 address, me->dir_port);
764
765
    control_event_server_status(LOG_NOTICE,
                                "CHECKING_REACHABILITY DIRADDRESS=%s:%d",
766
                                address, me->dir_port);
767
  }
768
769
770
  log_notice(LD_OR, "Now checking whether ORPort %s:%d%s %s reachable... "
                         "(this may take up to %d minutes -- look for log "
                         "messages indicating success)",
771
      address, me->or_port,
772
773
774
      me->dir_port ? dirbuf : "",
      me->dir_port ? "are" : "is",
      TIMEOUT_UNTIL_UNREACHABILITY_COMPLAINT/60);
775

776
  tor_free(address);
777
  return 1;
778
779
}

780
781
/** Return true iff we should send a create_fast cell to start building a given
 * circuit */
782
static inline int
783
should_use_create_fast_for_circuit(origin_circuit_t *circ)
784
{
785
786
787
  const or_options_t *options = get_options();
  tor_assert(circ->cpath);
  tor_assert(circ->cpath->extend_info);
788

789
790
791
792
793
  if (!circuit_has_usable_onion_key(circ)) {
    /* We don't have ntor, and we don't have or can't use TAP,
     * so our hand is forced: only a create_fast will work. */
    return 1;
  }
794
  if (public_server_mode(options)) {
795
    /* We're a server, and we have a usable onion key. We can choose.
796
797
798
     * Prefer to blend our circuit into the other circuits we are
     * creating on behalf of others. */
    return 0;
799
  }
800
  return networkstatus_get_param(NULL, "usecreatefast", 0, 0, 1);
801
802
}

803
804
805
806
807
808
809
810
811
812
813
814
/**
 * Return true if <b>circ</b> is the type of circuit we want to count
 * timeouts from.
 *
 * In particular, we want to consider any circuit that plans to build
 * at least 3 hops (but maybe more), but has 3 or fewer hops built
 * so far.
 *
 * We still want to consider circuits before 3 hops, because we need
 * to decide if we should convert them to a measurement circuit in
 * circuit_build_times_handle_completed_hop(), rather than letting
 * slow circuits get killed right away.
815
 */
816
int
817
circuit_timeout_want_to_count_circ(const origin_circuit_t *circ)
818
{
819
  return !circ->has_opened
820
821
          && circ->build_state->desired_path_len >= DEFAULT_ROUTE_LEN
          && circuit_get_cpath_opened_len(circ) <= DEFAULT_ROUTE_LEN;
822
823
}

824
825
/** Decide whether to use a TAP or ntor handshake for connecting to <b>ei</b>
 * directly, and set *<b>cell_type_out</b> and *<b>handshake_type_out</b>
826
 * accordingly.
827
828
 * Note that TAP handshakes in CREATE cells are only used for direct
 * connections:
829
830
 *  - from Single Onions to rend points not in the service's consensus.
 * This is checked in onion_populate_cpath. */
831
832
833
834
835
static void
circuit_pick_create_handshake(uint8_t *cell_type_out,
                              uint16_t *handshake_type_out,
                              const extend_info_t *ei)
{
836
837
  /* torspec says: In general, clients SHOULD use CREATE whenever they are
   * using the TAP handshake, and CREATE2 otherwise. */
838
  if (extend_info_supports_ntor(ei)) {
839
840
    *cell_type_out = CELL_CREATE2;
    *handshake_type_out = ONION_HANDSHAKE_TYPE_NTOR;
teor's avatar
teor committed
841
842
843
844
  } else {
    /* XXXX030 Remove support for deciding to use TAP and EXTEND. */
    *cell_type_out = CELL_CREATE;
    *handshake_type_out = ONION_HANDSHAKE_TYPE_TAP;
845
846
847
  }
}

848
849
850
851
852
/** Decide whether to use a TAP or ntor handshake for extending to <b>ei</b>
 * and set *<b>handshake_type_out</b> accordingly. Decide whether we should
 * use an EXTEND2 or an EXTEND cell to do so, and set *<b>cell_type_out</b>
 * and *<b>create_cell_type_out</b> accordingly.
 * Note that TAP handshakes in EXTEND cells are only used:
853
854
 *  - from clients to intro points, and
 *  - from hidden services to rend points.
855
856
 * This is checked in onion_populate_cpath.
 */
857
858
859
860
861
862
863
864
static void
circuit_pick_extend_handshake(uint8_t *cell_type_out,
                              uint8_t *create_cell_type_out,
                              uint16_t *handshake_type_out,
                              const extend_info_t *ei)
{
  uint8_t t;
  circuit_pick_create_handshake(&t, handshake_type_out, ei);
865

866
867
868
  /* torspec says: Clients SHOULD use the EXTEND format whenever sending a TAP
   * handshake... In other cases, clients SHOULD use EXTEND2. */
  if (*handshake_type_out != ONION_HANDSHAKE_TYPE_TAP) {
869
870
871
    *cell_type_out = RELAY_COMMAND_EXTEND2;
    *create_cell_type_out = CELL_CREATE2;
  } else {
872
    /* XXXX030 Remove support for deciding to use TAP and EXTEND. */
873
874
875
    *cell_type_out = RELAY_COMMAND_EXTEND;
    *create_cell_type_out = CELL_CREATE;
  }
876
877
}

878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
/**
 * Return true iff <b>purpose</b> is a purpose for a circuit which is
 * allowed to have no guard configured, even if the circuit is multihop
 * and guards are enabled.
 */
static int
circuit_purpose_may_omit_guard(int purpose)
{
  switch (purpose) {
    case CIRCUIT_PURPOSE_TESTING:
    case CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT:
      /* Testing circuits may omit guards because they're measuring
       * liveness or performance, and don't want guards to interfere. */
      return 1;
    default:
      /* All other multihop circuits should use guards if guards are
       * enabled. */
      return 0;
  }
}

899
/** This is the backbone function for building circuits.
Mike Perry's avatar
Mike Perry committed
900
 *
901
902
903
 * If circ's first hop is closed, then we need to build a create
 * cell and send it forward.
 *
904
905
906
907
908
 * Otherwise, if circ's cpath still has any non-open hops, we need to
 * build a relay extend cell and send it forward to the next non-open hop.
 *
 * If all hops on the cpath are open, we're done building the circuit
 * and we should do housekeeping for the newly opened circuit.
909
 *
910
 * Return -reason if we want to tear down circ, else return 0.
Mike Perry's avatar
Mike Perry committed
911
 */
912
913
int
circuit_send_next_onion_skin(origin_circuit_t *circ)
Mike Perry's avatar
Mike Perry committed
914
{
915
  tor_assert(circ);
Mike Perry's avatar
Mike Perry committed
916

917
  if (circ->cpath->state == CPATH_STATE_CLOSED) {
918
    /* Case one: we're on the first hop. */
919
920
    return circuit_send_first_onion_skin(circ);
  }
921
922
923

  tor_assert(circ->cpath->state == CPATH_STATE_OPEN);
  tor_assert(circ->base_.state == CIRCUIT_STATE_BUILDING);
924

925
  crypt_path_t *hop = onion_next_hop_in_cpath(circ->cpath);
926
  circuit_build_times_handle_completed_hop(circ);
927
928
929
930
931
932
933
934

  if (hop) {
    /* Case two: we're on a hop after the first. */
    return circuit_send_intermediate_onion_skin(circ, hop);
  }

  /* Case three: the circuit is finished. Do housekeeping tasks on it. */
  return circuit_build_no_more_hops(circ);
935
936
}

937
938
939
940
941
942
/**
 * Called from circuit_send_next_onion_skin() when we find ourselves connected
 * to the first hop in <b>circ</b>: Send a CREATE or CREATE2 or CREATE_FAST
 * cell to that hop.  Return 0 on success; -reason on failure (if the circuit
 * should be torn down).
 */
943
944
945
static int
circuit_send_first_onion_skin(origin_circuit_t *circ)
{
946
947
  int fast;
  int len;
948
949
  const node_t *node;
  create_cell_t cc;
950
  memset(&cc, 0, sizeof(cc));
951
952
953
954

  log_debug(LD_CIRC,"First skin; sending create cell.");

  if (circ->build_state->onehop_tunnel) {
955
    control_event_bootstrap(BOOTSTRAP_STATUS_ONEHOP_CREATE, 0);
956
  } else {
957
958
959
960
961
962
963
964
965
966
    control_event_bootstrap(BOOTSTRAP_STATUS_CIRCUIT_CREATE, 0);

    /* If this is not a one-hop tunnel, the channel is being used
     * for traffic that wants anonymity and protection from traffic
     * analysis (such as netflow record retention). That means we want
     * to pad it.
     */
    if (circ->base_.n_chan->channel_usage < CHANNEL_USED_FOR_FULL_CIRCS)
      circ->base_.n_chan->channel_usage = CHANNEL_USED_FOR_FULL_CIRCS;
  }
967

968
969
970
  node = node_get_by_id(circ->base_.n_chan->identity_digest);
  fast = should_use_create_fast_for_circuit(circ);
  if (!fast) {
971
    /* We know the right onion key: we should send a create cell. */
972
973
974
    circuit_pick_create_handshake(&cc.cell_type, &cc.handshake_type,
                                  circ->cpath->extend_info);
  } else {
975
    /* We don't know an onion key, so we need to fall back to CREATE_FAST. */
976
977
978
    cc.cell_type = CELL_CREATE_FAST;
    cc.handshake_type = ONION_HANDSHAKE_TYPE_FAST;
  }
Mike Perry's avatar
Mike Perry committed
979

980
981
982
983
984
985
986
987
988
  len = onion_skin_create(cc.handshake_type,
                          circ->cpath->extend_info,
                          &circ->cpath->handshake_state,
                          cc.onionskin);
  if (len < 0) {
    log_warn(LD_CIRC,"onion_skin_create (first hop) failed.");
    return - END_CIRC_REASON_INTERNAL;
  }
  cc.handshake_len = len;
989

990
991
  if (circuit_deliver_create_cell(TO_CIRCUIT(circ), &cc, 0) < 0)
    return - END_CIRC_REASON_RESOURCELIMIT;
Mike Perry's avatar
Mike Perry committed
992

993
994
995
996
997
998
  circ->cpath->state = CPATH_STATE_AWAITING_KEYS;
  circuit_set_state(TO_CIRCUIT(circ), CIRCUIT_STATE_BUILDING);
  log_info(LD_CIRC,"First hop: finished sending %s cell to '%s'",
           fast ? "CREATE_FAST" : "CREATE",
           node ? node_describe(node) : "<unnamed>");
  return 0;
999
1000
}

For faster browsing, not all history is shown. View entire blame