circuitbuild.c

关于tor匿名通信的源代码

    if (r->is_running == 0) {
//      log_debug(LD_CIRC,"Nope, the directory says %d is not running.",i);
      goto next_i_loop;
    }
    if (r->is_valid == 0) {
//      log_debug(LD_CIRC,"Nope, the directory says %d is not valid.",i);
      goto next_i_loop;
      /* XXX This clause makes us count incorrectly: if AllowInvalidRouters
       * allows this node in some places, then we're getting an inaccurate
       * count. For now, be conservative and don't count it. But later we
       * should try to be smarter. */
    }
    num++;
//    log_debug(LD_CIRC,"I like %d. num_acceptable_routers now %d.",i, num);
    next_i_loop:
      ; /* C requires an explicit statement after the label */
  }

  return num;
}

/** Add <b>new_hop</b> to the end of the doubly-linked-list <b>head_ptr</b>.
 * This function is used to extend cpath by another hop.
 */
void
onion_append_to_cpath(crypt_path_t **head_ptr, crypt_path_t *new_hop)
{
  if (*head_ptr) {
    new_hop->next = (*head_ptr);
    new_hop->prev = (*head_ptr)->prev;
    (*head_ptr)->prev->next = new_hop;
    (*head_ptr)->prev = new_hop;
  } else {
    *head_ptr = new_hop;
    new_hop->prev = new_hop->next = new_hop;
  }
}

/** Pick a random server digest that's running a Tor version that
 * doesn't have the reachability bug. These are versions 0.1.1.21-cvs+
 * and 0.1.2.1-alpha+. Avoid picking authorities, since we're
 * probably already connected to them.
 *
 * We only return one, so this doesn't become stupid when the
 * whole network has upgraded.
 * XXX021 we can great simplify this function now that all the broken
 * versions are obsolete. -RD */
static char *
compute_preferred_testing_list(const char *answer)
{
  smartlist_t *choices;
  routerlist_t *rl = router_get_routerlist();
  routerinfo_t *router;
  char *s;

  if (answer) /* they have one in mind -- easy */
    return tor_strdup(answer);

  choices = smartlist_create();
  /* now count up our choices */
  SMARTLIST_FOREACH(rl->routers, routerinfo_t *, r,
    if (r->is_running && r->is_valid &&
        ((tor_version_as_new_as(r->platform,"0.1.1.21-cvs") &&
          !tor_version_as_new_as(r->platform,"0.1.2.0-alpha-cvs")) ||
         tor_version_as_new_as(r->platform,"0.1.2.1-alpha")) &&
        !is_local_IP(r->addr) &&
        !router_get_trusteddirserver_by_digest(r->cache_info.identity_digest))
      smartlist_add(choices, r));
  router = smartlist_choose(choices);
  smartlist_free(choices);
  if (!router) {
    log_info(LD_CIRC, "Looking for middle server that doesn't have the "
             "reachability bug, but didn't find one. Oh well.");
    return NULL;
  }
  log_info(LD_CIRC, "Looking for middle server that doesn't have the "
             "reachability bug, and chose '%s'. Great.", router->nickname);
  s = tor_malloc(HEX_DIGEST_LEN+2);
  s[0] = '$';
  base16_encode(s+1, HEX_DIGEST_LEN+1,
                router->cache_info.identity_digest, DIGEST_LEN);
  return s;
}

/** A helper function used by onion_extend_cpath(). Use <b>purpose</b>
 * and <b>state</b> and the cpath <b>head</b> (currently populated only
 * to length <b>cur_len</b> to decide a suitable middle hop for a
 * circuit. In particular, make sure we don't pick the exit node or its
 * family, and make sure we don't duplicate any previous nodes or their
 * families. */
static routerinfo_t *
choose_good_middle_server(uint8_t purpose,
                          cpath_build_state_t *state,
                          crypt_path_t *head,
                          int cur_len)
{
  int i;
  routerinfo_t *r, *choice;
  crypt_path_t *cpath;
  smartlist_t *excluded;
  or_options_t *options = get_options();
  char *preferred = NULL;
  tor_assert(_CIRCUIT_PURPOSE_MIN <= purpose &&
             purpose <= _CIRCUIT_PURPOSE_MAX);

  log_debug(LD_CIRC, "Contemplating intermediate hop: random choice.");
  excluded = smartlist_create();
  if ((r = build_state_get_exit_router(state))) {
    smartlist_add(excluded, r);
    routerlist_add_family(excluded, r);
  }
  for (i = 0, cpath = head; i < cur_len; ++i, cpath=cpath->next) {
    if ((r = router_get_by_digest(cpath->extend_info->identity_digest))) {
      smartlist_add(excluded, r);
      routerlist_add_family(excluded, r);
    }
  }
  if (purpose == CIRCUIT_PURPOSE_TESTING)
    preferred = compute_preferred_testing_list(options->TestVia);
  choice = router_choose_random_node(preferred,
           options->ExcludeNodes, excluded,
           state->need_uptime, state->need_capacity, 0,
           options->_AllowInvalid & ALLOW_INVALID_MIDDLE, 0, 0);
  tor_free(preferred);
  smartlist_free(excluded);
  return choice;
}

/** Pick a good entry server for the circuit to be built according to
 * <b>state</b>.  Don't reuse a chosen exit (if any), don't use this
 * router (if we're an OR), and respect firewall settings; if we're
 * configured to use entry guards, return one.
 *
 * If <b>state</b> is NULL, we're choosing a router to serve as an entry
 * guard, not for any particular circuit.
 */
static routerinfo_t *
choose_good_entry_server(uint8_t purpose, cpath_build_state_t *state)
{
  routerinfo_t *r, *choice;
  smartlist_t *excluded;
  or_options_t *options = get_options();
  (void)purpose; /* not used yet. */

  if (state && options->UseEntryGuards) {
    return choose_random_entry(state);
  }

  excluded = smartlist_create();

  if (state && (r = build_state_get_exit_router(state))) {
    smartlist_add(excluded, r);
    routerlist_add_family(excluded, r);
  }
  if (firewall_is_fascist_or()) {
    /* exclude all ORs that listen on the wrong port */
    routerlist_t *rl = router_get_routerlist();
    int i;

    for (i=0; i < smartlist_len(rl->routers); i++) {
      r = smartlist_get(rl->routers, i);
      if (!fascist_firewall_allows_address_or(r->addr,r->or_port))
        smartlist_add(excluded, r);
    }
  }
  /* and exclude current entry guards, if applicable */
  if (options->UseEntryGuards && entry_guards) {
    SMARTLIST_FOREACH(entry_guards, entry_guard_t *, entry,
      {
        if ((r = router_get_by_digest(entry->identity)))
          smartlist_add(excluded, r);
      });
  }

  choice = router_choose_random_node(
           NULL, options->ExcludeNodes,
           excluded, state ? state->need_uptime : 0,
           state ? state->need_capacity : 0,
           state ? 0 : 1,
           options->_AllowInvalid & ALLOW_INVALID_ENTRY, 0, 0);
  smartlist_free(excluded);
  return choice;
}

/** Return the first non-open hop in cpath, or return NULL if all
 * hops are open. */
static crypt_path_t *
onion_next_hop_in_cpath(crypt_path_t *cpath)
{
  crypt_path_t *hop = cpath;
  do {
    if (hop->state != CPATH_STATE_OPEN)
      return hop;
    hop = hop->next;
  } while (hop != cpath);
  return NULL;
}

/** Choose a suitable next hop in the cpath <b>head_ptr</b>,
 * based on <b>state</b>. Append the hop info to head_ptr.
 */
static int
onion_extend_cpath(origin_circuit_t *circ)
{
  uint8_t purpose = circ->_base.purpose;
  cpath_build_state_t *state = circ->build_state;
  int cur_len = circuit_get_cpath_len(circ);
  extend_info_t *info = NULL;

  if (cur_len >= state->desired_path_len) {
    log_debug(LD_CIRC, "Path is complete: %d steps long",
              state->desired_path_len);
    return 1;
  }

  log_debug(LD_CIRC, "Path is %d long; we want %d", cur_len,
            state->desired_path_len);

  if (cur_len == state->desired_path_len - 1) { /* Picking last node */
    info = extend_info_dup(state->chosen_exit);
  } else if (cur_len == 0) { /* picking first node */
    routerinfo_t *r = choose_good_entry_server(purpose, state);
    if (r)
      info = extend_info_from_router(r);
  } else {
    routerinfo_t *r =
      choose_good_middle_server(purpose, state, circ->cpath, cur_len);
    if (r)
      info = extend_info_from_router(r);
  }

  if (!info) {
    log_warn(LD_CIRC,"Failed to find node for hop %d of our path. Discarding "
             "this circuit.", cur_len);
    return -1;
  }

  log_debug(LD_CIRC,"Chose router %s for hop %d (exit is %s)",
            info->nickname, cur_len+1, build_state_get_exit_nickname(state));

  onion_append_hop(&circ->cpath, info);
  extend_info_free(info);
  return 0;
}

/** Create a new hop, annotate it with information about its
 * corresponding router <b>choice</b>, and append it to the
 * end of the cpath <b>head_ptr</b>. */
static int
onion_append_hop(crypt_path_t **head_ptr, extend_info_t *choice)
{
  crypt_path_t *hop = tor_malloc_zero(sizeof(crypt_path_t));

  /* link hop into the cpath, at the end. */
  onion_append_to_cpath(head_ptr, hop);

  hop->magic = CRYPT_PATH_MAGIC;
  hop->state = CPATH_STATE_CLOSED;

  hop->extend_info = extend_info_dup(choice);

  hop->package_window = CIRCWINDOW_START;
  hop->deliver_window = CIRCWINDOW_START;

  return 0;
}

/** Allocate a new extend_info object based on the various arguments. */
extend_info_t *
extend_info_alloc(const char *nickname, const char *digest,
                  crypto_pk_env_t *onion_key,
                  uint32_t addr, uint16_t port)
{
  extend_info_t *info = tor_malloc_zero(sizeof(extend_info_t));
  memcpy(info->identity_digest, digest, DIGEST_LEN);
  if (nickname)
    strlcpy(info->nickname, nickname, sizeof(info->nickname));
  if (onion_key)
    info->onion_key = crypto_pk_dup_key(onion_key);
  info->addr = addr;
  info->port = port;
  return info;
}

/** Allocate and return a new extend_info_t that can be used to build a
 * circuit to or through the router <b>r</b>. */
extend_info_t *
extend_info_from_router(routerinfo_t *r)
{
  tor_assert(r);
  return extend_info_alloc(r->nickname, r->cache_info.identity_digest,
                           r->onion_pkey, r->addr, r->or_port);
}

/** Release storage held by an extend_info_t struct. */
void
extend_info_free(extend_info_t *info)
{
  tor_assert(info);
  if (info->onion_key)
    crypto_free_pk_env(info->onion_key);
  tor_free(info);
}

/** Allocate and return a new extend_info_t with the same contents as
 * <b>info</b>. */
extend_info_t *
extend_info_dup(extend_info_t *info)
{
  extend_info_t *newinfo;
  tor_assert(info);
  newinfo = tor_malloc(sizeof(extend_info_t));
  memcpy(newinfo, info, sizeof(extend_info_t));
  if (info->onion_key)
    newinfo->onion_key = crypto_pk_dup_key(info->onion_key);
  else
    newinfo->onion_key = NULL;
  return newinfo;
}

/** Return the routerinfo_t for the chosen exit router in <b>state</b>.
 * If there is no chosen exit, or if we don't know the routerinfo_t for
 * the chosen exit, return NULL.
 */
routerinfo_t *
build_state_get_exit_router(cpath_build_state_t *state)
{
  if (!state || !state->chosen_exit)
    return NULL;
  return router_get_by_digest(state->chosen_exit->identity_digest);
}

/** Return the nickname for the chosen exit router in <b>state</b>. If
 * there is no chosen exit, or if we don't know the routerinfo_t for the
 * chosen exit, return NULL.
 */
const char *
build_state_get_exit_nickname(cpath_build_state_t *state)
{
  if (!state || !state->chosen_exit)
    return NULL;
  return state->chosen_exit->nickname;
}

/** Check whether the entry guard <b>e</b> is usable, given the directory
 * authorities' opinion about the router (stored in <b>ri</b>) and the user's
 * configuration (in <b>options</b>). Set <b>e</b>-&gt;bad_since
 * accordingly. Return true iff the entry guard's status changes.
 *
 * If it's not usable, set *<b>reason</b> to a static string explaining why.
 */
/*XXXX021 take a routerstatus, not a routerinfo. */
static int
entry_guard_set_status(entry_guard_t *e, routerinfo_t *ri,
                       time_t now, or_options_t *options, const char **reason)
{
  char buf[HEX_DIGEST_LEN+1];
  int changed = 0;

  tor_assert(options);

  *reason = NULL;

  /* Do we want to mark this gu