circuitbuild.c

/* Copyright (c) 2001 Matej Pfajfar.
 * Copyright (c) 2001-2004, Roger Dingledine.
 * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
 * Copyright (c) 2007-2020, The Tor Project, Inc. */
/* See LICENSE for licensing information */

/**
 * \file circuitbuild.c
 *
 * \brief Implements the details of building circuits (by chosing paths,
 * constructing/sending create/extend cells, and so on).
 *
 * 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.
 *
 * The server side is handled in feature/relay/circuitbuild_relay.c.
 **/

#define CIRCUITBUILD_PRIVATE
#define OCIRC_EVENT_PRIVATE

#include "core/or/or.h"
#include "app/config/config.h"
#include "lib/confmgt/confmgt.h"
#include "core/crypto/hs_ntor.h"
#include "core/crypto/onion_crypto.h"
#include "core/crypto/onion_fast.h"
#include "core/crypto/onion_tap.h"
#include "core/mainloop/connection.h"
#include "core/mainloop/mainloop.h"
#include "core/or/channel.h"
#include "core/or/circuitbuild.h"
#include "core/or/circuitlist.h"
#include "core/or/circuitstats.h"
#include "core/or/circuituse.h"
#include "core/or/circuitpadding.h"
#include "core/or/command.h"
#include "core/or/connection_edge.h"
#include "core/or/connection_or.h"
#include "core/or/onion.h"
#include "core/or/ocirc_event.h"
#include "core/or/policies.h"
#include "core/or/relay.h"
#include "core/or/crypt_path.h"
#include "feature/client/bridges.h"
#include "feature/client/circpathbias.h"
#include "feature/client/entrynodes.h"
#include "feature/client/transports.h"
#include "feature/control/control_events.h"
#include "feature/dircommon/directory.h"
#include "feature/nodelist/describe.h"
#include "feature/nodelist/microdesc.h"
#include "feature/nodelist/networkstatus.h"
#include "feature/nodelist/nickname.h"
#include "feature/nodelist/node_select.h"
#include "feature/nodelist/nodelist.h"
#include "feature/nodelist/routerlist.h"
#include "feature/nodelist/routerset.h"
#include "feature/relay/router.h"
#include "feature/relay/routermode.h"
#include "feature/relay/selftest.h"
#include "feature/rend/rendcommon.h"
#include "feature/stats/predict_ports.h"
#include "lib/crypt_ops/crypto_rand.h"

#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"

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);
static const node_t *choose_good_middle_server(uint8_t purpose,
                          cpath_build_state_t *state,
                          crypt_path_t *head,
                          int cur_len);

/** This function tries to get a channel to the specified endpoint,
 * and then calls command_setup_channel() to give it the right
 * callbacks.
 */
MOCK_IMPL(channel_t *,
channel_connect_for_circuit,(const tor_addr_t *addr, uint16_t port,
                             const char *id_digest,
                             const struct ed25519_public_key_t *ed_id))
{
  channel_t *chan;

  chan = channel_connect(addr, port, id_digest, ed_id);
  if (chan) command_setup_channel(chan);

  return chan;
}

/** 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.
 *
 * Return it, or 0 if can't get a unique circ_id.
 */
STATIC circid_t
get_unique_circ_id_by_chan(channel_t *chan)
{
/* 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. */
#define MAX_CIRCID_ATTEMPTS 64
  int in_use;
  unsigned n_with_circ = 0, n_pending_destroy = 0, n_weird_pending_destroy = 0;
  circid_t test_circ_id;
  circid_t attempts=0;
  circid_t high_bit, max_range, mask;
  int64_t pending_destroy_time_total = 0;
  int64_t pending_destroy_time_max = 0;

  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.");
    return 0;
  }
  max_range = (chan->wide_circ_ids) ? (1u<<31) : (1u<<15);
  mask = max_range - 1;
  high_bit = (chan->circ_id_type == CIRC_ID_TYPE_HIGHER) ? max_range : 0;
  do {
    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.
       */
      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 "
                 "circID support, with %u inbound and %u outbound circuits. "
                 "Found %u circuit IDs in use by circuits, and %u with "
                 "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",
                 chan->wide_circ_ids ? "with" : "without",
                 chan->num_p_circuits, chan->num_n_circuits,
                 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, "
               "of which %u are active. It says it has %"PRId64
               " destroy cells queued.",
               circuitmux_num_circuits(chan->cmux),
               circuitmux_num_active_circuits(chan->cmux),
               (queued_destroys));

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

      channel_dump_statistics(chan, LOG_WARN);

      return 0;
    }

    do {
      crypto_rand((char*) &test_circ_id, sizeof(test_circ_id));
      test_circ_id &= mask;
    } while (test_circ_id == 0);

    test_circ_id |= high_bit;

    in_use = circuit_id_in_use_on_channel(test_circ_id, chan);
    if (in_use == 1)
      ++n_with_circ;
    else if (in_use == 2) {
      time_t since_when;
      ++n_pending_destroy;
      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;
      }
    }
  } while (in_use);
  return test_circ_id;
}

/** 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 hex digests; if <b>verbose_names</b>
 * is true, use $DIGEST=Name style names.
 */
static char *
circuit_list_path_impl(origin_circuit_t *circ, int verbose, int verbose_names)
{
  crypt_path_t *hop;
  smartlist_t *elements;
  const char *states[] = {"closed", "waiting for keys", "open"};
  char *s;

  elements = smartlist_new();

  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*"));
  }

  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 */
      elt = tor_malloc(HEX_DIGEST_LEN+2);
      elt[0] = '$';
      base16_encode(elt+1, HEX_DIGEST_LEN+1, id, DIGEST_LEN);
    }
    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);

  s = smartlist_join_strings(elements, verbose?" ":",", 0, NULL);
  SMARTLIST_FOREACH(elements, char*, cp, tor_free(cp));
  smartlist_free(elements);
  return s;
}

/** 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)
{
  return circuit_list_path_impl(circ, verbose, 0);
}

/** Allocate and return a comma-separated list of the currently built elements
 * of <b>circ</b>, giving each as a verbose nickname.
 */
char *
circuit_list_path_for_controller(origin_circuit_t *circ)
{
  return circuit_list_path_impl(circ, 0, 1);
}

/** 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)
{
  char *s = circuit_list_path(circ,1);
  tor_log(severity,domain,"%s",s);
  tor_free(s);
}

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

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

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

  return 1;
}

/** 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)
{
  int r = 0;

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

  while (r == 0) {
    r = onion_extend_cpath(circ);
    if (r < 0) {
      log_info(LD_CIRC,"Generating cpath hop failed.");
      return -1;
    }
  }

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

  /* 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)) {
    /* 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. */
    return 0;
  }

  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.
     */
    if (!node || !node_has_preferred_descriptor(node, 1)) {
      return 0;
    }
  }

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

/** 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)
{
  /* 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;
}

/** 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.
 *
 * Also launch a connection to the first OR in the chosen path, if
 * it's not open already.
 */
origin_circuit_t *
circuit_establish_circuit(uint8_t purpose, extend_info_t *exit_ei, int flags)
{
  origin_circuit_t *circ;
  int err_reason = 0;
  int is_hs_v3_rp_circuit = 0;

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

  circ = origin_circuit_init(purpose, flags);

  if (onion_pick_cpath_exit(circ, exit_ei, is_hs_v3_rp_circuit) < 0 ||
      onion_populate_cpath(circ) < 0) {
    circuit_mark_for_close(TO_CIRCUIT(circ), END_CIRC_REASON_NOPATH);
    return NULL;
  }

  circuit_event_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;
}

/** 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;
}

/**
 * Helper function to publish a channel association message
 *
 * circuit_handle_first_hop() calls this to notify subscribers about a
 * channel launch event, which associates a circuit with a channel.
 * This doesn't always correspond to an assignment of the circuit's
 * n_chan field, because that seems to be only for fully-open
 * channels.
 **/
static void
circuit_chan_publish(const origin_circuit_t *circ, const channel_t *chan)
{
  ocirc_chan_msg_t *msg = tor_malloc(sizeof(*msg));

  msg->gid = circ->global_identifier;
  msg->chan = chan->global_identifier;
  msg->onehop = circ->build_state->onehop_tunnel;

  ocirc_chan_publish(msg);
}

/** 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)
{
  crypt_path_t *firsthop;
  channel_t *n_chan;
  int err_reason = 0;
  const char *msg = NULL;
  int should_launch = 0;
  const or_options_t *options = get_options();

  firsthop = cpath_get_next_non_open_hop(circ->cpath);
  tor_assert(firsthop);
  tor_assert(firsthop->extend_info);

  /* 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. */
  if (tor_addr_is_internal(&firsthop->extend_info->addr, 0) &&
      !extend_info_is_a_configured_bridge(firsthop->extend_info) &&
      !options->ExtendAllowPrivateAddresses) {
    log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
           "Client asked me to connect directly to a private address");
    return -END_CIRC_REASON_TORPROTOCOL;
  }

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

  /* We'll cleanup this code in #33220, when we add an IPv6 address to
   * extend_info_t. */
  const bool addr_is_ipv4 =
    (tor_addr_family(&firsthop->extend_info->addr) == AF_INET);
  n_chan = channel_get_for_extend(
                          firsthop->extend_info->identity_digest,
                          &firsthop->extend_info->ed_identity,
                          addr_is_ipv4 ? &firsthop->extend_info->addr : NULL,
                          addr_is_ipv4 ? NULL : &firsthop->extend_info->addr,
                          &msg,
                          &should_launch);

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

    if (should_launch) {
      n_chan = channel_connect_for_circuit(
          &firsthop->extend_info->addr,
          firsthop->extend_info->port,
          firsthop->extend_info->identity_digest,
          &firsthop->extend_info->ed_identity);
      if (!n_chan) { /* connect failed, forget the whole thing */
        log_info(LD_CIRC,"connect to firsthop failed. Closing.");
        return -END_CIRC_REASON_CONNECTFAILED;
      }
      circuit_chan_publish(circ, n_chan);
    }

    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;
    circuit_chan_publish(circ, 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.");
      circ->base_.n_chan = NULL;
      return err_reason;
    }
  }
  return 0;
}

/** Find any circuits that are waiting on <b>or_conn</b> to become
 * open and get them to send their create cells forward.
 *
 * Status is 1 if connect succeeded, or 0 if connect failed.
 *
 * 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.)
 */
void
circuit_n_chan_done(channel_t *chan, int status, int close_origin_circuits)
{
  smartlist_t *pending_circs;
  int err_reason = 0;

  tor_assert(chan);

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

  pending_circs = smartlist_new();
  circuit_get_all_pending_on_channel(pending_circs, chan);

  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;

      const char *rsa_ident = NULL;
      const ed25519_public_key_t *ed_ident = NULL;
      if (! tor_digest_is_zero(circ->n_hop->identity_digest)) {
        rsa_ident = circ->n_hop->identity_digest;
      }
      if (! ed25519_public_key_is_zero(&circ->n_hop->ed_identity)) {
        ed_ident = &circ->n_hop->ed_identity;
      }

      if (rsa_ident == NULL && ed_ident == NULL) {
        /* Look at addr/port. This is an unkeyed connection. */
        if (!channel_matches_extend_info(chan, circ->n_hop))
          continue;
      } else {
        /* We expected a key or keys. See if they matched. */
        if (!channel_remote_identity_matches(chan, rsa_ident, ed_ident))
          continue;

        /* If the channel is canonical, great.  If not, it needs to match
         * the requested address exactly. */
        if (! chan->is_canonical &&
            ! channel_matches_extend_info(chan, circ->n_hop)) {
          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);
        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);
        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;

      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 {
        /* pull the create cell out of circ->n_chan_create_cell, and send it */
        tor_assert(circ->n_chan_create_cell);
        if (circuit_deliver_create_cell(circ, circ->n_chan_create_cell, 1)<0) {
          circuit_mark_for_close(circ, END_CIRC_REASON_RESOURCELIMIT);
          continue;
        }
        tor_free(circ->n_chan_create_cell);
        circuit_set_state(circ, CIRCUIT_STATE_OPEN);
      }
    }
  SMARTLIST_FOREACH_END(circ);

  smartlist_free(pending_circs);
}

/** Find a new circid that isn't currently in use on the circ->n_chan
 * for the outgoing
 * 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.
 */
MOCK_IMPL(int,
circuit_deliver_create_cell,(circuit_t *circ,
                             const struct create_cell_t *create_cell,
                             int relayed))
{
  cell_t cell;
  circid_t id;
  int r;

  tor_assert(circ);
  tor_assert(circ->n_chan);
  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);

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

  tor_assert_nonfatal_once(circ->n_chan->is_canonical);

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

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

  if (CIRCUIT_IS_ORIGIN(circ)) {
    /* Update began timestamp for circuits starting their first hop */
    if (TO_ORIGIN_CIRCUIT(circ)->cpath->state == CPATH_STATE_CLOSED) {
      if (!CHANNEL_IS_OPEN(circ->n_chan)) {
        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);
    }

    /* mark it so it gets better rate limiting treatment. */
    channel_timestamp_client(circ->n_chan);
  }

  return 0;
 error:
  circ->n_chan = NULL;
  return -1;
}

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

  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;
  }
  if (public_server_mode(options)) {
    /* We're a server, and we have a usable onion key. We can choose.
     * Prefer to blend our circuit into the other circuits we are
     * creating on behalf of others. */
    return 0;
  }
  return networkstatus_get_param(NULL, "usecreatefast", 0, 0, 1);
}

/**
 * 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.
 */
int
circuit_timeout_want_to_count_circ(const origin_circuit_t *circ)
{
  return !circ->has_opened
          && circ->build_state->desired_path_len >= DEFAULT_ROUTE_LEN
          && circuit_get_cpath_opened_len(circ) <= DEFAULT_ROUTE_LEN;
}

/** 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>
 * accordingly.
 * Note that TAP handshakes in CREATE cells are only used for direct
 * connections:
 *  - from Single Onions to rend points not in the service's consensus.
 * This is checked in onion_populate_cpath. */
static void
circuit_pick_create_handshake(uint8_t *cell_type_out,
                              uint16_t *handshake_type_out,
                              const extend_info_t *ei)
{
  /* torspec says: In general, clients SHOULD use CREATE whenever they are
   * using the TAP handshake, and CREATE2 otherwise. */
  if (extend_info_supports_ntor(ei)) {
    *cell_type_out = CELL_CREATE2;
    *handshake_type_out = ONION_HANDSHAKE_TYPE_NTOR;
  } else {
    /* XXXX030 Remove support for deciding to use TAP and EXTEND. */
    *cell_type_out = CELL_CREATE;
    *handshake_type_out = ONION_HANDSHAKE_TYPE_TAP;
  }
}

/** 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:
 *  - from clients to intro points, and
 *  - from hidden services to rend points.
 * This is checked in onion_populate_cpath.
 */
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);

  /* 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) {
    *cell_type_out = RELAY_COMMAND_EXTEND2;
    *create_cell_type_out = CELL_CREATE2;
  } else {
    /* XXXX030 Remove support for deciding to use TAP and EXTEND. */
    *cell_type_out = RELAY_COMMAND_EXTEND;
    *create_cell_type_out = CELL_CREATE;
  }
}

/**
 * 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;
  }
}

/** This is the backbone function for building circuits.
 *
 * If circ's first hop is closed, then we need to build a create
 * cell and send it forward.
 *
 * 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.
 *
 * Return -reason if we want to tear down circ, else return 0.
 */
int
circuit_send_next_onion_skin(origin_circuit_t *circ)
{
  tor_assert(circ);

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

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

  crypt_path_t *hop = cpath_get_next_non_open_hop(circ->cpath);
  circuit_build_times_handle_completed_hop(circ);

  circpad_machine_event_circ_added_hop(circ);

  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. */
  circpad_machine_event_circ_built(circ);
  return circuit_build_no_more_hops(circ);
}

/**
 * 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).
 */
static int
circuit_send_first_onion_skin(origin_circuit_t *circ)
{
  int fast;
  int len;
  const node_t *node;
  create_cell_t cc;
  memset(&cc, 0, sizeof(cc));

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

  if (circ->build_state->onehop_tunnel) {
    control_event_bootstrap(BOOTSTRAP_STATUS_ONEHOP_CREATE, 0);
  } else {
    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;
  }

  node = node_get_by_id(circ->base_.n_chan->identity_digest);
  fast = should_use_create_fast_for_circuit(circ);
  if (!fast) {
    /* We know the right onion key: we should send a create cell. */
    circuit_pick_create_handshake(&cc.cell_type, &cc.handshake_type,
                                  circ->cpath->extend_info);
  } else {
    /* We don't know an onion key, so we need to fall back to CREATE_FAST. */
    cc.cell_type = CELL_CREATE_FAST;
    cc.handshake_type = ONION_HANDSHAKE_TYPE_FAST;
  }

  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;

  if (circuit_deliver_create_cell(TO_CIRCUIT(circ), &cc, 0) < 0)
    return - END_CIRC_REASON_RESOURCELIMIT;