circuitlist.c

关于tor匿名通信的源代码

/* Copyright 2001 Matej Pfajfar.
 * Copyright (c) 2001-2004, Roger Dingledine.
 * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
 * Copyright (c) 2007-2008, The Tor Project, Inc. */
/* See LICENSE for licensing information */
/* $Id$ */
const char circuitlist_c_id[] =
  "$Id$";

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

#include "or.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_OR_WAIT. */
static smartlist_t *circuits_pending_or_conns=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);

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

/** A map from OR connection and circuit ID to circuit.  (Lookup performance is
 * very important here, since we need to do it every time a cell arrives.) */
typedef struct orconn_circid_circuit_map_t {
  HT_ENTRY(orconn_circid_circuit_map_t) node;
  or_connection_t *or_conn;
  uint16_t circ_id;
  circuit_t *circuit;
} orconn_circid_circuit_map_t;

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

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

/** Map from [orconn,circid] to circuit. */
static HT_HEAD(orconn_circid_map, orconn_circid_circuit_map_t)
     orconn_circid_circuit_map = HT_INITIALIZER();
HT_PROTOTYPE(orconn_circid_map, orconn_circid_circuit_map_t, node,
             _orconn_circid_entry_hash, _orconn_circid_entries_eq)
HT_GENERATE(orconn_circid_map, orconn_circid_circuit_map_t, node,
            _orconn_circid_entry_hash, _orconn_circid_entries_eq, 0.6,
            malloc, realloc, free)

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

/** Implementation helper for circuit_set_{p,n}_circid_orconn: A circuit ID
 * and/or or_connection for circ has just changed from <b>old_conn, old_id</b>
 * to <b>conn, id</b>.  Adjust the conn,circid map as appropriate, removing
 * the old entry (if any) and adding a new one.  If <b>active</b> is true,
 * remove the circuit from the list of active circuits on old_conn and add it
 * to the list of active circuits on conn.
 * XXX "active" isn't an arg anymore */
static void
circuit_set_circid_orconn_helper(circuit_t *circ, int direction,
                                 uint16_t id,
                                 or_connection_t *conn)
{
  orconn_circid_circuit_map_t search;
  orconn_circid_circuit_map_t *found;
  or_connection_t *old_conn, **conn_ptr;
  uint16_t old_id, *circid_ptr;
  int was_active, make_active;

  if (direction == CELL_DIRECTION_OUT) {
    conn_ptr = &circ->n_conn;
    circid_ptr = &circ->n_circ_id;
    was_active = circ->next_active_on_n_conn != NULL;
    make_active = circ->n_conn_cells.n > 0;
  } else {
    or_circuit_t *c = TO_OR_CIRCUIT(circ);
    conn_ptr = &c->p_conn;
    circid_ptr = &c->p_circ_id;
    was_active = c->next_active_on_p_conn != NULL;
    make_active = c->p_conn_cells.n > 0;
  }
  old_conn = *conn_ptr;
  old_id = *circid_ptr;

  if (id == old_id && conn == old_conn)
    return;

  if (_last_circid_orconn_ent &&
      ((old_id == _last_circid_orconn_ent->circ_id &&
        old_conn == _last_circid_orconn_ent->or_conn) ||
       (id == _last_circid_orconn_ent->circ_id &&
        conn == _last_circid_orconn_ent->or_conn))) {
    _last_circid_orconn_ent = NULL;
  }

  if (old_conn) { /* we may need to remove it from the conn-circid map */
    tor_assert(old_conn->_base.magic == OR_CONNECTION_MAGIC);
    search.circ_id = old_id;
    search.or_conn = old_conn;
    found = HT_REMOVE(orconn_circid_map, &orconn_circid_circuit_map, &search);
    if (found) {
      tor_free(found);
      --old_conn->n_circuits;
    }
    if (was_active && old_conn != conn)
      make_circuit_inactive_on_conn(circ,old_conn);
  }

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

  if (conn == NULL)
    return;

  /* now add the new one to the conn-circid map */
  search.circ_id = id;
  search.or_conn = conn;
  found = HT_FIND(orconn_circid_map, &orconn_circid_circuit_map, &search);
  if (found) {
    found->circuit = circ;
  } else {
    found = tor_malloc_zero(sizeof(orconn_circid_circuit_map_t));
    found->circ_id = id;
    found->or_conn = conn;
    found->circuit = circ;
    HT_INSERT(orconn_circid_map, &orconn_circid_circuit_map, found);
  }
  if (make_active && old_conn != conn)
    make_circuit_active_on_conn(circ,conn);

  ++conn->n_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 (orconn,id)-\>circuit map. */
void
circuit_set_p_circid_orconn(or_circuit_t *circ, uint16_t id,
                            or_connection_t *conn)
{
  circuit_set_circid_orconn_helper(TO_CIRCUIT(circ), CELL_DIRECTION_IN,
                                   id, conn);

  if (conn)
    tor_assert(bool_eq(circ->p_conn_cells.n, circ->next_active_on_p_conn));
}

/** Set the n_conn field of a circuit <b>circ</b>, along
 * with the corresponding circuit ID, and add the circuit as appropriate
 * to the (orconn,id)-\>circuit map. */
void
circuit_set_n_circid_orconn(circuit_t *circ, uint16_t id,
                            or_connection_t *conn)
{
  circuit_set_circid_orconn_helper(circ, CELL_DIRECTION_OUT, id, conn);

  if (conn)
    tor_assert(bool_eq(circ->n_conn_cells.n, circ->next_active_on_n_conn));
}

/** 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_or_conns)
    circuits_pending_or_conns = smartlist_create();
  if (circ->state == CIRCUIT_STATE_OR_WAIT) {
    /* remove from waiting-circuit list. */
    smartlist_remove(circuits_pending_or_conns, circ);
  }
  if (state == CIRCUIT_STATE_OR_WAIT) {
    /* add to waiting-circuit list. */
    smartlist_add(circuits_pending_or_conns, circ);
  }
  if (state == CIRCUIT_STATE_OPEN)
    tor_assert(!circ->n_conn_onionskin);
  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 OR_WAIT waiting for
 * the given connection. */
void
circuit_get_all_pending_on_or_conn(smartlist_t *out, or_connection_t *or_conn)
{
  tor_assert(out);
  tor_assert(or_conn);

  if (!circuits_pending_or_conns)
    return;

  SMARTLIST_FOREACH(circuits_pending_or_conns, circuit_t *, circ,
  {
    if (circ->marked_for_close)
      continue;
    tor_assert(circ->state == CIRCUIT_STATE_OR_WAIT);
    if (tor_digest_is_zero(circ->n_conn_id_digest)) {
      /* Look at addr/port. This is an unkeyed connection. */
      if (circ->n_addr != or_conn->_base.addr ||
          circ->n_port != or_conn->_base.port)
        continue;
    } else {
      /* We expected a key. See if it's the right one. */
      if (memcmp(or_conn->identity_digest,
                 circ->n_conn_id_digest, DIGEST_LEN))
        continue;
    }
    smartlist_add(out, circ);
  });
}

/** Return the number of circuits in state OR_WAIT, waiting for the given
 * connection. */
int
circuit_count_pending_on_or_conn(or_connection_t *or_conn)
{
  int cnt;
  smartlist_t *sl = smartlist_create();
  circuit_get_all_pending_on_or_conn(sl, or_conn);
  cnt = smartlist_len(sl);
  smartlist_free(sl);
  log_debug(LD_CIRC,"or_conn to %s, %d pending circs",
            or_conn->nickname ? or_conn->nickname : "NULL", cnt);
  return cnt;
}

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

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

  circ->package_window = CIRCWINDOW_START;
  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++;

  init_circuit_base(TO_CIRCUIT(circ));

  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(uint16_t p_circ_id, or_connection_t *p_conn)
{
  /* CircIDs */
  or_circuit_t *circ;

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

  if (p_conn)
    circuit_set_p_circid_orconn(circ, p_circ_id, p_conn);

  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;
  tor_assert(circ);
  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) {
      if (ocirc->build_state->chosen_exit)
        extend_info_free(ocirc->build_state->chosen_exit);
      if (ocirc->build_state->pending_final_cpath)
        circuit_free_cpath_node(ocirc->build_state->pending_final_cpath);
    }
    tor_free(ocirc->build_state);

    circuit_free_cpath(ocirc->cpath);
    if (ocirc->intro_key)
      crypto_free_pk_env(ocirc->intro_key);

  } else {
    or_circuit_t *ocirc = TO_OR_CIRCUIT(circ);
    mem = ocirc;