circuitlist.c

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

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

#include "or.h"
#include "channel.h"
#include "circuitbuild.h"
#include "circuitlist.h"
#include "circuituse.h"
#include "circuitstats.h"
#include "connection.h"
#include "config.h"
#include "connection_edge.h"
#include "connection_or.h"
#include "control.h"
#include "networkstatus.h"
#include "nodelist.h"
#include "onion.h"
#include "onion_fast.h"
#include "policies.h"
#include "relay.h"
#include "rendclient.h"
#include "rendcommon.h"
#include "rephist.h"
#include "routerlist.h"
#include "routerset.h"
#include "ht.h"

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

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

/** A list of all the circuits in CIRCUIT_STATE_CHAN_WAIT. */
static smartlist_t *circuits_pending_chans = NULL;

static void circuit_free(circuit_t *circ);
static void circuit_free_cpath(crypt_path_t *cpath);
static void circuit_free_cpath_node(crypt_path_t *victim);
static void cpath_ref_decref(crypt_path_reference_t *cpath_ref);

/********* END VARIABLES ************/

/** A map from channel and circuit ID to circuit.  (Lookup performance is
 * very important here, since we need to do it every time a cell arrives.) */
typedef struct chan_circid_circuit_map_t {
  HT_ENTRY(chan_circid_circuit_map_t) node;
  channel_t *chan;
  circid_t circ_id;
  circuit_t *circuit;
} chan_circid_circuit_map_t;

/** Helper for hash tables: compare the channel and circuit ID for a and
 * b, and return less than, equal to, or greater than zero appropriately.
 */
static INLINE int
chan_circid_entries_eq_(chan_circid_circuit_map_t *a,
                        chan_circid_circuit_map_t *b)
{
  return a->chan == b->chan && a->circ_id == b->circ_id;
}

/** Helper: return a hash based on circuit ID and the pointer value of
 * chan in <b>a</b>. */
static INLINE unsigned int
chan_circid_entry_hash_(chan_circid_circuit_map_t *a)
{
  return ((unsigned)a->circ_id) ^ (unsigned)(uintptr_t)(a->chan);
}

/** Map from [chan,circid] to circuit. */
static HT_HEAD(chan_circid_map, chan_circid_circuit_map_t)
     chan_circid_map = HT_INITIALIZER();
HT_PROTOTYPE(chan_circid_map, chan_circid_circuit_map_t, node,
             chan_circid_entry_hash_, chan_circid_entries_eq_)
HT_GENERATE(chan_circid_map, chan_circid_circuit_map_t, node,
            chan_circid_entry_hash_, chan_circid_entries_eq_, 0.6,
            malloc, realloc, free)

/** The most recently returned entry from circuit_get_by_circid_chan;
 * used to improve performance when many cells arrive in a row from the
 * same circuit.
 */
chan_circid_circuit_map_t *_last_circid_chan_ent = NULL;

/** Implementation helper for circuit_set_{p,n}_circid_channel: A circuit ID
 * and/or channel for circ has just changed from <b>old_chan, old_id</b>
 * to <b>chan, id</b>.  Adjust the chan,circid map as appropriate, removing
 * the old entry (if any) and adding a new one. */
static void
circuit_set_circid_chan_helper(circuit_t *circ, int direction,
                               circid_t id,
                               channel_t *chan)
{
  chan_circid_circuit_map_t search;
  chan_circid_circuit_map_t *found;
  channel_t *old_chan, **chan_ptr;
  circid_t old_id, *circid_ptr;
  int make_active, attached = 0;

  if (direction == CELL_DIRECTION_OUT) {
    chan_ptr = &circ->n_chan;
    circid_ptr = &circ->n_circ_id;
    make_active = circ->n_chan_cells.n > 0;
  } else {
    or_circuit_t *c = TO_OR_CIRCUIT(circ);
    chan_ptr = &c->p_chan;
    circid_ptr = &c->p_circ_id;
    make_active = c->p_chan_cells.n > 0;
  }
  old_chan = *chan_ptr;
  old_id = *circid_ptr;

  if (id == old_id && chan == old_chan)
    return;

  if (_last_circid_chan_ent &&
      ((old_id == _last_circid_chan_ent->circ_id &&
        old_chan == _last_circid_chan_ent->chan) ||
       (id == _last_circid_chan_ent->circ_id &&
        chan == _last_circid_chan_ent->chan))) {
    _last_circid_chan_ent = NULL;
  }

  if (old_chan) {
    /*
     * If we're changing channels or ID and had an old channel and a non
     * zero old ID and weren't marked for close (i.e., we should have been
     * attached), detach the circuit. ID changes require this because
     * circuitmux hashes on (channel_id, circuit_id).
     */
    if (old_id != 0 && (old_chan != chan || old_id != id) &&
        !(circ->marked_for_close)) {
      tor_assert(old_chan->cmux);
      circuitmux_detach_circuit(old_chan->cmux, circ);
    }

    /* we may need to remove it from the conn-circid map */
    search.circ_id = old_id;
    search.chan = old_chan;
    found = HT_REMOVE(chan_circid_map, &chan_circid_map, &search);
    if (found) {
      tor_free(found);
      if (direction == CELL_DIRECTION_OUT) {
        /* One fewer circuits use old_chan as n_chan */
        --(old_chan->num_n_circuits);
      } else {
        /* One fewer circuits use old_chan as p_chan */
        --(old_chan->num_p_circuits);
      }
    }
  }

  /* Change the values only after we have possibly made the circuit inactive
   * on the previous chan. */
  *chan_ptr = chan;
  *circid_ptr = id;

  if (chan == NULL)
    return;

  /* now add the new one to the conn-circid map */
  search.circ_id = id;
  search.chan = chan;
  found = HT_FIND(chan_circid_map, &chan_circid_map, &search);
  if (found) {
    found->circuit = circ;
  } else {
    found = tor_malloc_zero(sizeof(chan_circid_circuit_map_t));
    found->circ_id = id;
    found->chan = chan;
    found->circuit = circ;
    HT_INSERT(chan_circid_map, &chan_circid_map, found);
  }

  /*
   * Attach to the circuitmux if we're changing channels or IDs and
   * have a new channel and ID to use and the circuit is not marked for
   * close.
   */
  if (chan && id != 0 && (old_chan != chan || old_id != id) &&
      !(circ->marked_for_close)) {
    tor_assert(chan->cmux);
    circuitmux_attach_circuit(chan->cmux, circ, direction);
    attached = 1;
  }

  /*
   * This is a no-op if we have no cells, but if we do it marks us active to
   * the circuitmux
   */
  if (make_active && attached)
    update_circuit_on_cmux(circ, direction);

  /* Adjust circuit counts on new channel */
  if (direction == CELL_DIRECTION_OUT) {
    ++chan->num_n_circuits;
  } else {
    ++chan->num_p_circuits;
  }
}

/** Set the p_conn field of a circuit <b>circ</b>, along
 * with the corresponding circuit ID, and add the circuit as appropriate
 * to the (chan,id)-\>circuit map. */
void
circuit_set_p_circid_chan(or_circuit_t *circ, circid_t id,
                          channel_t *chan)
{
  circuit_set_circid_chan_helper(TO_CIRCUIT(circ), CELL_DIRECTION_IN,
                                 id, chan);

  if (chan)
    tor_assert(bool_eq(circ->p_chan_cells.n, circ->next_active_on_p_chan));
}

/** Set the n_conn field of a circuit <b>circ</b>, along
 * with the corresponding circuit ID, and add the circuit as appropriate
 * to the (chan,id)-\>circuit map. */
void
circuit_set_n_circid_chan(circuit_t *circ, circid_t id,
                          channel_t *chan)
{
  circuit_set_circid_chan_helper(circ, CELL_DIRECTION_OUT, id, chan);

  if (chan)
    tor_assert(bool_eq(circ->n_chan_cells.n, circ->next_active_on_n_chan));
}

/** Change the state of <b>circ</b> to <b>state</b>, adding it to or removing
 * it from lists as appropriate. */
void
circuit_set_state(circuit_t *circ, uint8_t state)
{
  tor_assert(circ);
  if (state == circ->state)
    return;
  if (!circuits_pending_chans)
    circuits_pending_chans = smartlist_new();
  if (circ->state == CIRCUIT_STATE_CHAN_WAIT) {
    /* remove from waiting-circuit list. */
    smartlist_remove(circuits_pending_chans, circ);
  }
  if (state == CIRCUIT_STATE_CHAN_WAIT) {
    /* add to waiting-circuit list. */
    smartlist_add(circuits_pending_chans, circ);
  }
  if (state == CIRCUIT_STATE_OPEN)
    tor_assert(!circ->n_chan_create_cell);
  circ->state = state;
}

/** Add <b>circ</b> to the global list of circuits. This is called only from
 * within circuit_new.
 */
static void
circuit_add(circuit_t *circ)
{
  if (!global_circuitlist) { /* first one */
    global_circuitlist = circ;
    circ->next = NULL;
  } else {
    circ->next = global_circuitlist;
    global_circuitlist = circ;
  }
}

/** Append to <b>out</b> all circuits in state CHAN_WAIT waiting for
 * the given connection. */
void
circuit_get_all_pending_on_channel(smartlist_t *out, channel_t *chan)
{
  tor_assert(out);
  tor_assert(chan);

  if (!circuits_pending_chans)
    return;

  SMARTLIST_FOREACH_BEGIN(circuits_pending_chans, circuit_t *, circ) {
    if (circ->marked_for_close)
      continue;
    if (!circ->n_hop)
      continue;
    tor_assert(circ->state == CIRCUIT_STATE_CHAN_WAIT);
    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;
    }
    smartlist_add(out, circ);
  } SMARTLIST_FOREACH_END(circ);
}

/** Return the number of circuits in state CHAN_WAIT, waiting for the given
 * channel. */
int
circuit_count_pending_on_channel(channel_t *chan)
{
  int cnt;
  smartlist_t *sl = smartlist_new();

  tor_assert(chan);

  circuit_get_all_pending_on_channel(sl, chan);
  cnt = smartlist_len(sl);
  smartlist_free(sl);
  log_debug(LD_CIRC,"or_conn to %s at %s, %d pending circs",
            chan->nickname ? chan->nickname : "NULL",
            channel_get_canonical_remote_descr(chan),
            cnt);
  return cnt;
}

/** Detach from the global circuit list, and deallocate, all
 * circuits that have been marked for close.
 */
void
circuit_close_all_marked(void)
{
  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;
    }
  }
}

/** Return the head of the global linked list of circuits. */
circuit_t *
circuit_get_global_list_(void)
{
  return global_circuitlist;
}

/** Function to make circ-\>state human-readable */
const char *
circuit_state_to_string(int state)
{
  static char buf[64];
  switch (state) {
    case CIRCUIT_STATE_BUILDING: return "doing handshakes";
    case CIRCUIT_STATE_ONIONSKIN_PENDING: return "processing the onion";
    case CIRCUIT_STATE_CHAN_WAIT: return "connecting to server";
    case CIRCUIT_STATE_OPEN: return "open";
    default:
      log_warn(LD_BUG, "Unknown circuit state %d", state);
      tor_snprintf(buf, sizeof(buf), "unknown state [%d]", state);
      return buf;
  }
}

/** Map a circuit purpose to a string suitable to be displayed to a
 * controller. */
const char *
circuit_purpose_to_controller_string(uint8_t purpose)
{
  static char buf[32];
  switch (purpose) {
    case CIRCUIT_PURPOSE_OR:
    case CIRCUIT_PURPOSE_INTRO_POINT:
    case CIRCUIT_PURPOSE_REND_POINT_WAITING:
    case CIRCUIT_PURPOSE_REND_ESTABLISHED:
      return "SERVER"; /* A controller should never see these, actually. */

    case CIRCUIT_PURPOSE_C_GENERAL:
      return "GENERAL";
    case CIRCUIT_PURPOSE_C_INTRODUCING:
    case CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT:
    case CIRCUIT_PURPOSE_C_INTRODUCE_ACKED:
      return "HS_CLIENT_INTRO";

    case CIRCUIT_PURPOSE_C_ESTABLISH_REND:
    case CIRCUIT_PURPOSE_C_REND_READY:
    case CIRCUIT_PURPOSE_C_REND_READY_INTRO_ACKED:
    case CIRCUIT_PURPOSE_C_REND_JOINED:
      return "HS_CLIENT_REND";

    case CIRCUIT_PURPOSE_S_ESTABLISH_INTRO:
    case CIRCUIT_PURPOSE_S_INTRO:
      return "HS_SERVICE_INTRO";

    case CIRCUIT_PURPOSE_S_CONNECT_REND:
    case CIRCUIT_PURPOSE_S_REND_JOINED:
      return "HS_SERVICE_REND";

    case CIRCUIT_PURPOSE_TESTING:
      return "TESTING";
    case CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT:
      return "MEASURE_TIMEOUT";
    case CIRCUIT_PURPOSE_CONTROLLER:
      return "CONTROLLER";
    case CIRCUIT_PURPOSE_PATH_BIAS_TESTING:
      return "PATH_BIAS_TESTING";

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

/** Return a string specifying the state of the hidden-service circuit
 * purpose <b>purpose</b>, or NULL if <b>purpose</b> is not a
 * hidden-service-related circuit purpose. */
const char *
circuit_purpose_to_controller_hs_state_string(uint8_t purpose)
{
  switch (purpose)
    {
    default:
      log_fn(LOG_WARN, LD_BUG,
             "Unrecognized circuit purpose: %d",
             (int)purpose);
      tor_fragile_assert();
      /* fall through */

    case CIRCUIT_PURPOSE_OR:
    case CIRCUIT_PURPOSE_C_GENERAL:
    case CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT:
    case CIRCUIT_PURPOSE_TESTING:
    case CIRCUIT_PURPOSE_CONTROLLER:
    case CIRCUIT_PURPOSE_PATH_BIAS_TESTING:
      return NULL;

    case CIRCUIT_PURPOSE_INTRO_POINT:
      return "OR_HSSI_ESTABLISHED";
    case CIRCUIT_PURPOSE_REND_POINT_WAITING:
      return "OR_HSCR_ESTABLISHED";
    case CIRCUIT_PURPOSE_REND_ESTABLISHED:
      return "OR_HS_R_JOINED";

    case CIRCUIT_PURPOSE_C_INTRODUCING:
      return "HSCI_CONNECTING";
    case CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT:
      return "HSCI_INTRO_SENT";
    case CIRCUIT_PURPOSE_C_INTRODUCE_ACKED:
      return "HSCI_DONE";

    case CIRCUIT_PURPOSE_C_ESTABLISH_REND:
      return "HSCR_CONNECTING";
    case CIRCUIT_PURPOSE_C_REND_READY:
      return "HSCR_ESTABLISHED_IDLE";
    case CIRCUIT_PURPOSE_C_REND_READY_INTRO_ACKED:
      return "HSCR_ESTABLISHED_WAITING";
    case CIRCUIT_PURPOSE_C_REND_JOINED:
      return "HSCR_JOINED";

    case CIRCUIT_PURPOSE_S_ESTABLISH_INTRO:
      return "HSSI_CONNECTING";
    case CIRCUIT_PURPOSE_S_INTRO:
      return "HSSI_ESTABLISHED";

    case CIRCUIT_PURPOSE_S_CONNECT_REND:
      return "HSSR_CONNECTING";
    case CIRCUIT_PURPOSE_S_REND_JOINED:
      return "HSSR_JOINED";
    }
}

/** Return a human-readable string for the circuit purpose <b>purpose</b>. */
const char *
circuit_purpose_to_string(uint8_t purpose)
{
  static char buf[32];

  switch (purpose)
    {
    case CIRCUIT_PURPOSE_OR:
      return "Circuit at relay";
    case CIRCUIT_PURPOSE_INTRO_POINT:
      return "Acting as intro point";
    case CIRCUIT_PURPOSE_REND_POINT_WAITING:
      return "Acting as rendevous (pending)";
    case CIRCUIT_PURPOSE_REND_ESTABLISHED:
      return "Acting as rendevous (established)";
    case CIRCUIT_PURPOSE_C_GENERAL:
      return "General-purpose client";
    case CIRCUIT_PURPOSE_C_INTRODUCING:
      return "Hidden service client: Connecting to intro point";
    case CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT:
      return "Hidden service client: Waiting for ack from intro point";
    case CIRCUIT_PURPOSE_C_INTRODUCE_ACKED:
      return "Hidden service client: Received ack from intro point";
    case CIRCUIT_PURPOSE_C_ESTABLISH_REND:
      return "Hidden service client: Establishing rendezvous point";
    case CIRCUIT_PURPOSE_C_REND_READY:
      return "Hidden service client: Pending rendezvous point";
    case CIRCUIT_PURPOSE_C_REND_READY_INTRO_ACKED:
      return "Hidden service client: Pending rendezvous point (ack received)";
    case CIRCUIT_PURPOSE_C_REND_JOINED:
      return "Hidden service client: Active rendezvous point";
    case CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT:
      return "Measuring circuit timeout";

    case CIRCUIT_PURPOSE_S_ESTABLISH_INTRO:
      return "Hidden service: Establishing introduction point";
    case CIRCUIT_PURPOSE_S_INTRO:
      return "Hidden service: Introduction point";
    case CIRCUIT_PURPOSE_S_CONNECT_REND:
      return "Hidden service: Connecting to rendezvous point";
    case CIRCUIT_PURPOSE_S_REND_JOINED:
      return "Hidden service: Active rendezvous point";

    case CIRCUIT_PURPOSE_TESTING:
      return "Testing circuit";

    case CIRCUIT_PURPOSE_CONTROLLER:
      return "Circuit made by controller";

    case CIRCUIT_PURPOSE_PATH_BIAS_TESTING:
      return "Path-bias testing circuit";

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

/** Pick a reasonable package_window to start out for our circuits.
 * Originally this was hard-coded at 1000, but now the consensus votes
 * on the answer. See proposal 168. */
int32_t
circuit_initial_package_window(void)
{
  int32_t num = networkstatus_get_param(NULL, "circwindow", CIRCWINDOW_START,
                                        CIRCWINDOW_START_MIN,
                                        CIRCWINDOW_START_MAX);
  /* If the consensus tells us a negative number, we'd assert. */
  if (num < 0)
    num = CIRCWINDOW_START;
  return num;
}

/** Initialize the common elements in a circuit_t, and add it to the global
 * list. */
static void
init_circuit_base(circuit_t *circ)
{
  tor_gettimeofday(&circ->timestamp_created);

  // Gets reset when we send CREATE_FAST.
  // circuit_expire_building() expects these to be equal
  // until the orconn is built.
  circ->timestamp_began = circ->timestamp_created;

  circ->package_window = circuit_initial_package_window();
  circ->deliver_window = CIRCWINDOW_START;

  circuit_add(circ);
}

/** Allocate space for a new circuit, initializing with <b>p_circ_id</b>
 * and <b>p_conn</b>. Add it to the global circuit list.
 */
origin_circuit_t *
origin_circuit_new(void)
{
  origin_circuit_t *circ;
  /* never zero, since a global ID of 0 is treated specially by the
   * controller */
  static uint32_t n_circuits_allocated = 1;

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

  circ->next_stream_id = crypto_rand_int(1<<16);
  circ->global_identifier = n_circuits_allocated++;
  circ->remaining_relay_early_cells = MAX_RELAY_EARLY_CELLS_PER_CIRCUIT;
  circ->remaining_relay_early_cells -= crypto_rand_int(2);

  init_circuit_base(TO_CIRCUIT(circ));

  circ_times.last_circ_at = approx_time();

  return circ;
}

/** Allocate a new or_circuit_t, connected to <b>p_conn</b> as
 * <b>p_circ_id</b>.  If <b>p_conn</b> is NULL, the circuit is unattached. */
or_circuit_t *
or_circuit_new(circid_t p_circ_id, channel_t *p_chan)
{
  /* CircIDs */
  or_circuit_t *circ;

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

  if (p_chan)
    circuit_set_p_circid_chan(circ, p_circ_id, p_chan);

  circ->remaining_relay_early_cells = MAX_RELAY_EARLY_CELLS_PER_CIRCUIT;

  init_circuit_base(TO_CIRCUIT(circ));

  return circ;
}

/** Deallocate space associated with circ.
 */
static void
circuit_free(circuit_t *circ)
{
  void *mem;
  size_t memlen;
  if (!circ)
    return;

  if (CIRCUIT_IS_ORIGIN(circ)) {
    origin_circuit_t *ocirc = TO_ORIGIN_CIRCUIT(circ);
    mem = ocirc;
    memlen = sizeof(origin_circuit_t);
    tor_assert(circ->magic == ORIGIN_CIRCUIT_MAGIC);
    if (ocirc->build_state) {
        extend_info_free(ocirc->build_state->chosen_exit);
        circuit_free_cpath_node(ocirc->build_state->pending_final_cpath);
        cpath_ref_decref(ocirc->build_state->service_pending_final_cpath_ref);
    }
    tor_free(ocirc->build_state);

    circuit_free_cpath(ocirc->cpath);

    crypto_pk_free(ocirc->intro_key);
    rend_data_free(ocirc->rend_data);

    tor_free(ocirc->dest_address);
    if (ocirc->socks_username) {
      memwipe(ocirc->socks_username, 0x12, ocirc->socks_username_len);
      tor_free(ocirc->socks_username);
    }
    if (ocirc->socks_password) {
      memwipe(ocirc->socks_password, 0x06, ocirc->socks_password_len);
      tor_free(ocirc->socks_password);
    }
    addr_policy_list_free(ocirc->prepend_policy);
  } else {
    or_circuit_t *ocirc = TO_OR_CIRCUIT(circ);
    /* Remember cell statistics for this circuit before deallocating. */
    if (get_options()->CellStatistics)
      rep_hist_buffer_stats_add_circ(circ, time(NULL));
    mem = ocirc;
    memlen = sizeof(or_circuit_t);
    tor_assert(circ->magic == OR_CIRCUIT_MAGIC);

    crypto_cipher_free(ocirc->p_crypto);
    crypto_digest_free(ocirc->p_digest);
    crypto_cipher_free(ocirc->n_crypto);
    crypto_digest_free(ocirc->n_digest);

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

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

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

  extend_info_free(circ->n_hop);
  tor_free(circ->n_chan_create_cell);

  /* Remove from map. */
  circuit_set_n_circid_chan(circ, 0, NULL);

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

  memwipe(mem, 0xAA, memlen); /* poison memory */
  tor_free(mem);
}

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

  if (!cpath)
    return;

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

  circuit_free_cpath_node(cpath);
}

/** Release all storage held by circuits. */
void
circuit_free_all(void)
{
  circuit_t *next;
  while (global_circuitlist) {
    next = global_circuitlist->next;
    if (! CIRCUIT_IS_ORIGIN(global_circuitlist)) {
      or_circuit_t *or_circ = TO_OR_CIRCUIT(global_circuitlist);
      while (or_circ->resolving_streams) {
        edge_connection_t *next_conn;
        next_conn = or_circ->resolving_streams->next_stream;
        connection_free(TO_CONN(or_circ->resolving_streams));
        or_circ->resolving_streams = next_conn;
      }
    }
    circuit_free(global_circuitlist);
    global_circuitlist = next;
  }

  smartlist_free(circuits_pending_chans);
  circuits_pending_chans = NULL;

  HT_CLEAR(chan_circid_map, &chan_circid_map);
}

/** Deallocate space associated with the cpath node <b>victim</b>. */
static void
circuit_free_cpath_node(crypt_path_t *victim)
{
  if (!victim)
    return;

  crypto_cipher_free(victim->f_crypto);
  crypto_cipher_free(victim->b_crypto);
  crypto_digest_free(victim->f_digest);
  crypto_digest_free(victim->b_digest);
  onion_handshake_state_release(&victim->handshake_state);
  crypto_dh_free(victim->rend_dh_handshake_state);
  extend_info_free(victim->extend_info);

  memwipe(victim, 0xBB, sizeof(crypt_path_t)); /* poison memory */
  tor_free(victim);
}

/** Release a crypt_path_reference_t*, which may be NULL. */
static void
cpath_ref_decref(crypt_path_reference_t *cpath_ref)
{
  if (cpath_ref != NULL) {
    if (--(cpath_ref->refcount) == 0) {
      circuit_free_cpath_node(cpath_ref->cpath);
      tor_free(cpath_ref);
    }
  }
}

/** A helper function for circuit_dump_by_conn() below. Log a bunch
 * of information about circuit <b>circ</b>.
 */
static void
circuit_dump_conn_details(int severity,
                          circuit_t *circ,
                          int conn_array_index,
                          const char *type,
                          circid_t this_circid,
                          circid_t other_circid)
{
  tor_log(severity, LD_CIRC, "Conn %d has %s circuit: circID %u "
      "(other side %u), state %d (%s), born %ld:",
      conn_array_index, type, (unsigned)this_circid, (unsigned)other_circid,
      circ->state, circuit_state_to_string(circ->state),
      (long)circ->timestamp_began.tv_sec);
  if (CIRCUIT_IS_ORIGIN(circ)) { /* circ starts at this node */
    circuit_log_path(severity, LD_CIRC, TO_ORIGIN_CIRCUIT(circ));
  }
}

/** Log, at severity <b>severity</b>, information about each circuit
 * that is connected to <b>conn</b>.
 */
void
circuit_dump_by_conn(connection_t *conn, int severity)
{
  circuit_t *circ;
  edge_connection_t *tmpconn;

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

    if (circ->marked_for_close) {
      continue;
    }

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

    if (CIRCUIT_IS_ORIGIN(circ)) {
      for (tmpconn=TO_ORIGIN_CIRCUIT(circ)->p_streams; tmpconn;
           tmpconn=tmpconn->next_stream) {
        if (TO_CONN(tmpconn) == conn) {
          circuit_dump_conn_details(severity, circ, conn->conn_array_index,
                                    "App-ward", p_circ_id, n_circ_id);
        }
      }
    }

    if (! CIRCUIT_IS_ORIGIN(circ)) {
      for (tmpconn=TO_OR_CIRCUIT(circ)->n_streams; tmpconn;
           tmpconn=tmpconn->next_stream) {
        if (TO_CONN(tmpconn) == conn) {
          circuit_dump_conn_details(severity, circ, conn->conn_array_index,
                                    "Exit-ward", n_circ_id, p_circ_id);
        }
      }
    }
  }
}

/** A helper function for circuit_dump_by_chan() below. Log a bunch
 * of information about circuit <b>circ</b>.
 */
static void
circuit_dump_chan_details(int severity,
                          circuit_t *circ,
                          channel_t *chan,
                          const char *type,
                          circid_t this_circid,
                          circid_t other_circid)
{
  tor_log(severity, LD_CIRC, "Conn %p has %s circuit: circID %u "
      "(other side %u), state %d (%s), born %ld:",
      chan, type, (unsigned)this_circid, (unsigned)other_circid, circ->state,
      circuit_state_to_string(circ->state),
      (long)circ->timestamp_began.tv_sec);
  if (CIRCUIT_IS_ORIGIN(circ)) { /* circ starts at this node */
    circuit_log_path(severity, LD_CIRC, TO_ORIGIN_CIRCUIT(circ));
  }
}

/** Log, at severity <b>severity</b>, information about each circuit
 * that is connected to <b>chan</b>.
 */
void
circuit_dump_by_chan(channel_t *chan, int severity)
{
  circuit_t *circ;

  tor_assert(chan);

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

    if (circ->marked_for_close) {
      continue;
    }

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

    if (! CIRCUIT_IS_ORIGIN(circ) && TO_OR_CIRCUIT(circ)->p_chan &&
        TO_OR_CIRCUIT(circ)->p_chan == chan) {
      circuit_dump_chan_details(severity, circ, chan, "App-ward",
                                p_circ_id, n_circ_id);
    }

    if (circ->n_chan && circ->n_chan == chan) {
      circuit_dump_chan_details(severity, circ, chan, "Exit-ward",
                                n_circ_id, p_circ_id);
    }

    if (!circ->n_chan && circ->n_hop &&
        channel_matches_extend_info(chan, circ->n_hop) &&
        tor_memeq(chan->identity_digest,
                  circ->n_hop->identity_digest, DIGEST_LEN)) {
      circuit_dump_chan_details(severity, circ, chan,
                                (circ->state == CIRCUIT_STATE_OPEN &&
                                 !CIRCUIT_IS_ORIGIN(circ)) ?
                                "Endpoint" : "Pending",
                                n_circ_id, p_circ_id);
    }
  }
}

/** Return the circuit whose global ID is <b>id</b>, or NULL if no
 * such circuit exists. */
origin_circuit_t *
circuit_get_by_global_id(uint32_t id)
{
  circuit_t *circ;
  for (circ=global_circuitlist;circ;circ = circ->next) {
    if (CIRCUIT_IS_ORIGIN(circ) &&
        TO_ORIGIN_CIRCUIT(circ)->global_identifier == id) {
      if (circ->marked_for_close)
        return NULL;
      else
        return TO_ORIGIN_CIRCUIT(circ);
    }
  }
  return NULL;
}

/** 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>chan</b>, either as p_chan or n_chan.
 * Return NULL if no such circuit exists.
 */
static INLINE circuit_t *
circuit_get_by_circid_channel_impl(circid_t circ_id, channel_t *chan)
{
  chan_circid_circuit_map_t search;
  chan_circid_circuit_map_t *found;

  if (_last_circid_chan_ent &&
      circ_id == _last_circid_chan_ent->circ_id &&
      chan == _last_circid_chan_ent->chan) {
    found = _last_circid_chan_ent;
  } else {
    search.circ_id = circ_id;
    search.chan = chan;
    found = HT_FIND(chan_circid_map, &chan_circid_map, &search);
    _last_circid_chan_ent = found;
  }
  if (found && found->circuit) {
    log_debug(LD_CIRC,
              "circuit_get_by_circid_channel_impl() returning circuit %p for"
              " circ_id %u, channel ID " U64_FORMAT " (%p)",
              found->circuit, (unsigned)circ_id,
              U64_PRINTF_ARG(chan->global_identifier), chan);
    return found->circuit;
  }

  log_debug(LD_CIRC,
            "circuit_get_by_circid_channel_impl() found nothing for"
            " circ_id %u, channel ID " U64_FORMAT " (%p)",
            (unsigned)circ_id,
            U64_PRINTF_ARG(chan->global_identifier), chan);

  return NULL;
  /* The rest of this checks for bugs. Disabled by default. */
  /* We comment it out because coverity complains otherwise.
  {
    circuit_t *circ;
    for (circ=global_circuitlist;circ;circ = circ->next) {
      if (! CIRCUIT_IS_ORIGIN(circ)) {
        or_circuit_t *or_circ = TO_OR_CIRCUIT(circ);
        if (or_circ->p_chan == chan && or_circ->p_circ_id == circ_id) {
          log_warn(LD_BUG,
                   "circuit matches p_chan, but not in hash table (Bug!)");
          return circ;
        }
      }
      if (circ->n_chan == chan && circ->n_circ_id == circ_id) {
        log_warn(LD_BUG,
                 "circuit matches n_chan, but not in hash table (Bug!)");
        return circ;
      }
    }
    return NULL;
  } */
}

/** 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>chan</b>, either as p_chan or n_chan.
 *  - circ is not marked for close.
 * Return NULL if no such circuit exists.
 */
circuit_t *
circuit_get_by_circid_channel(circid_t circ_id, channel_t *chan)
{
  circuit_t *circ = circuit_get_by_circid_channel_impl(circ_id, chan);
  if (!circ || circ->marked_for_close)
    return NULL;
  else
    return circ;