routerlist.c

关于tor匿名通信的源代码

static void
routerlist_add_network_family(smartlist_t *sl, routerinfo_t *router)
{
  SMARTLIST_FOREACH(routerlist->routers, routerinfo_t *, r,
  {
    if (router != r && routers_in_same_network_family(router, r))
      smartlist_add(sl, r);
  });
}

/** Add all the family of <b>router</b> to the smartlist <b>sl</b>.
 * This is used to make sure we don't pick siblings in a single path.
 */
void
routerlist_add_family(smartlist_t *sl, routerinfo_t *router)
{
  routerinfo_t *r;
  config_line_t *cl;
  or_options_t *options = get_options();

  /* First, add any routers with similar network addresses. */
  if (options->EnforceDistinctSubnets)
    routerlist_add_network_family(sl, router);

  if (router->declared_family) {
    /* Add every r such that router declares familyness with r, and r
     * declares familyhood with router. */
    SMARTLIST_FOREACH(router->declared_family, const char *, n,
      {
        if (!(r = router_get_by_nickname(n, 0)))
          continue;
        if (!r->declared_family)
          continue;
        SMARTLIST_FOREACH(r->declared_family, const char *, n2,
          {
            if (router_nickname_matches(router, n2))
              smartlist_add(sl, r);
          });
      });
  }

  /* If the user declared any families locally, honor those too. */
  for (cl = options->NodeFamilies; cl; cl = cl->next) {
    if (router_nickname_is_in_list(router, cl->value)) {
      add_nickname_list_to_smartlist(sl, cl->value, 0);
    }
  }
}

/** Return true iff r is named by some nickname in <b>lst</b>. */
static INLINE int
router_in_nickname_smartlist(smartlist_t *lst, routerinfo_t *r)
{
  if (!lst) return 0;
  SMARTLIST_FOREACH(lst, const char *, name,
    if (router_nickname_matches(r, name))
      return 1;);
  return 0;
}

/** Return true iff r1 and r2 are in the same family, but not the same
 * router. */
int
routers_in_same_family(routerinfo_t *r1, routerinfo_t *r2)
{
  or_options_t *options = get_options();
  config_line_t *cl;

  if (options->EnforceDistinctSubnets && routers_in_same_network_family(r1,r2))
    return 1;

  if (router_in_nickname_smartlist(r1->declared_family, r2) &&
      router_in_nickname_smartlist(r2->declared_family, r1))
    return 1;

  for (cl = options->NodeFamilies; cl; cl = cl->next) {
    if (router_nickname_is_in_list(r1, cl->value) &&
        router_nickname_is_in_list(r2, cl->value))
      return 1;
  }
  return 0;
}

/** Given a (possibly NULL) comma-and-whitespace separated list of nicknames,
 * see which nicknames in <b>list</b> name routers in our routerlist, and add
 * the routerinfos for those routers to <b>sl</b>.  If <b>must_be_running</b>,
 * only include routers that we think are running.
 * Warn if any non-Named routers are specified by nickname.
 */
void
add_nickname_list_to_smartlist(smartlist_t *sl, const char *list,
                               int must_be_running)
{
  routerinfo_t *router;
  smartlist_t *nickname_list;
  int have_dir_info = router_have_minimum_dir_info();

  if (!list)
    return; /* nothing to do */
  tor_assert(sl);

  nickname_list = smartlist_create();
  if (!warned_nicknames)
    warned_nicknames = smartlist_create();

  smartlist_split_string(nickname_list, list, ",",
                         SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);

  SMARTLIST_FOREACH(nickname_list, const char *, nick, {
    int warned;
    if (!is_legal_nickname_or_hexdigest(nick)) {
      log_warn(LD_CONFIG, "Nickname '%s' is misformed; skipping", nick);
      continue;
    }
    router = router_get_by_nickname(nick, 1);
    warned = smartlist_string_isin(warned_nicknames, nick);
    if (router) {
      if (!must_be_running || router->is_running) {
        smartlist_add(sl,router);
      }
    } else if (!router_get_consensus_status_by_nickname(nick,1)) {
      if (!warned) {
        log_fn(have_dir_info ? LOG_WARN : LOG_INFO, LD_CONFIG,
               "Nickname list includes '%s' which isn't a known router.",nick);
        smartlist_add(warned_nicknames, tor_strdup(nick));
      }
    }
  });
  SMARTLIST_FOREACH(nickname_list, char *, nick, tor_free(nick));
  smartlist_free(nickname_list);
}

/** Return 1 iff any member of the (possibly NULL) comma-separated list
 * <b>list</b> is an acceptable nickname or hexdigest for <b>router</b>.  Else
 * return 0.
 */
int
router_nickname_is_in_list(routerinfo_t *router, const char *list)
{
  smartlist_t *nickname_list;
  int v = 0;

  if (!list)
    return 0; /* definitely not */
  tor_assert(router);

  nickname_list = smartlist_create();
  smartlist_split_string(nickname_list, list, ",",
                         SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
  SMARTLIST_FOREACH(nickname_list, const char *, cp,
                    if (router_nickname_matches(router, cp)) {v=1;break;});
  SMARTLIST_FOREACH(nickname_list, char *, cp, tor_free(cp));
  smartlist_free(nickname_list);
  return v;
}

/** Add every suitable router from our routerlist to <b>sl</b>, so that
 * we can pick a node for a circuit.
 */
static void
router_add_running_routers_to_smartlist(smartlist_t *sl, int allow_invalid,
                                        int need_uptime, int need_capacity,
                                        int need_guard)
{
  if (!routerlist)
    return;

  SMARTLIST_FOREACH(routerlist->routers, routerinfo_t *, router,
  {
    if (router->is_running &&
        router->purpose == ROUTER_PURPOSE_GENERAL &&
        (router->is_valid || allow_invalid) &&
        !router_is_unreliable(router, need_uptime,
                              need_capacity, need_guard)) {
      /* If it's running, and it's suitable according to the
       * other flags we had in mind */
      smartlist_add(sl, router);
    }
  });
}

/** Look through the routerlist until we find a router that has my key.
 Return it. */
routerinfo_t *
routerlist_find_my_routerinfo(void)
{
  if (!routerlist)
    return NULL;

  SMARTLIST_FOREACH(routerlist->routers, routerinfo_t *, router,
  {
    if (router_is_me(router))
      return router;
  });
  return NULL;
}

/** Find a router that's up, that has this IP address, and
 * that allows exit to this address:port, or return NULL if there
 * isn't a good one.
 */
routerinfo_t *
router_find_exact_exit_enclave(const char *address, uint16_t port)
{
  uint32_t addr;
  struct in_addr in;

  if (!tor_inet_aton(address, &in))
    return NULL; /* it's not an IP already */
  addr = ntohl(in.s_addr);

  SMARTLIST_FOREACH(routerlist->routers, routerinfo_t *, router,
  {
    if (router->is_running &&
        router->addr == addr &&
        compare_addr_to_addr_policy(addr, port, router->exit_policy) ==
          ADDR_POLICY_ACCEPTED)
      return router;
  });
  return NULL;
}

/** Return 1 if <b>router</b> is not suitable for these parameters, else 0.
 * If <b>need_uptime</b> is non-zero, we require a minimum uptime.
 * If <b>need_capacity</b> is non-zero, we require a minimum advertised
 * bandwidth.
 * If <b>need_guard</b>, we require that the router is a possible entry guard.
 */
int
router_is_unreliable(routerinfo_t *router, int need_uptime,
                     int need_capacity, int need_guard)
{
  if (need_uptime && !router->is_stable)
    return 1;
  if (need_capacity && !router->is_fast)
    return 1;
  if (need_guard && !router->is_possible_guard)
    return 1;
  return 0;
}

/** Return the smaller of the router's configured BandwidthRate
 * and its advertised capacity. */
uint32_t
router_get_advertised_bandwidth(routerinfo_t *router)
{
  if (router->bandwidthcapacity < router->bandwidthrate)
    return router->bandwidthcapacity;
  return router->bandwidthrate;
}

/** Do not weight any declared bandwidth more than this much when picking
 * routers by bandwidth. */
#define DEFAULT_MAX_BELIEVABLE_BANDWIDTH 10000000 /* 10 MB/sec */

/** Eventually, the number we return will come from the directory
 * consensus, so clients can dynamically update to better numbers.
 *
 * But for now, or in case there is no consensus available, just return
 * a sufficient default. */
static uint32_t
get_max_believable_bandwidth(void)
{
  return DEFAULT_MAX_BELIEVABLE_BANDWIDTH;
}

/** Helper function:
 * choose a random element of smartlist <b>sl</b>, weighted by
 * the advertised bandwidth of each element.
 *
 * If <b>statuses</b> is zero, then <b>sl</b> is a list of
 * routerinfo_t's. Otherwise it's a list of routerstatus_t's.
 *
 * If <b>rule</b>==WEIGHT_FOR_EXIT. we're picking an exit node: consider all
 * nodes' bandwidth equally regardless of their Exit status, since there may
 * be some in the list because they exit to obscure ports. If
 * <b>rule</b>==NO_WEIGHTING, we're picking a non-exit node: weight
 * exit-node's bandwidth less depending on the smallness of the fraction of
 * Exit-to-total bandwidth.  If <b>rule</b>==WEIGHT_FOR_GUARD, we're picking a
 * guard node: consider all guard's bandwidth equally. Otherwise, weight
 * guards proportionally less.
 */
static void *
smartlist_choose_by_bandwidth(smartlist_t *sl, bandwidth_weight_rule_t rule,
                              int statuses)
{
  unsigned int i;
  routerinfo_t *router;
  routerstatus_t *status=NULL;
  int32_t *bandwidths;
  int is_exit;
  int is_guard;
  uint64_t total_nonexit_bw = 0, total_exit_bw = 0, total_bw = 0;
  uint64_t total_nonguard_bw = 0, total_guard_bw = 0;
  uint64_t rand_bw, tmp;
  double exit_weight;
  double guard_weight;
  int n_unknown = 0;
  bitarray_t *exit_bits;
  bitarray_t *guard_bits;
  uint32_t max_believable_bw = get_max_believable_bandwidth();

  /* Can't choose exit and guard at same time */
  tor_assert(rule == NO_WEIGHTING ||
             rule == WEIGHT_FOR_EXIT ||
             rule == WEIGHT_FOR_GUARD);

  /* First count the total bandwidth weight, and make a list
   * of each value.  <0 means "unknown; no routerinfo."  We use the
   * bits of negative values to remember whether the router was fast (-x)&1
   * and whether it was an exit (-x)&2 or guard (-x)&4.  Yes, it's a hack. */
  bandwidths = tor_malloc(sizeof(int32_t)*smartlist_len(sl));
  exit_bits = bitarray_init_zero(smartlist_len(sl));
  guard_bits = bitarray_init_zero(smartlist_len(sl));

  /* Iterate over all the routerinfo_t or routerstatus_t, and */
  for (i = 0; i < (unsigned)smartlist_len(sl); ++i) {
    /* first, learn what bandwidth we think i has */
    int is_known = 1;
    int32_t flags = 0;
    uint32_t this_bw = 0;
    if (statuses) {
      /* need to extract router info */
      status = smartlist_get(sl, i);
      router = router_get_by_digest(status->identity_digest);
      is_exit = status->is_exit;
      is_guard = status->is_possible_guard;
      if (router) {
        this_bw = router_get_advertised_bandwidth(router);
      } else { /* guess */
        is_known = 0;
        flags = status->is_fast ? 1 : 0;
        flags |= is_exit ? 2 : 0;
        flags |= is_guard ? 4 : 0;
      }
    } else {
      router = smartlist_get(sl, i);
      is_exit = router->is_exit;
      is_guard = router->is_possible_guard;
      this_bw = router_get_advertised_bandwidth(router);
    }
    if (is_exit)
      bitarray_set(exit_bits, i);
    if (is_guard)
      bitarray_set(guard_bits, i);
    /* if they claim something huge, don't believe it */
    if (this_bw > max_believable_bw) {
      char fp[HEX_DIGEST_LEN+1];
      base16_encode(fp, sizeof(fp), statuses ?
                      status->identity_digest :
                      router->cache_info.identity_digest,
                    DIGEST_LEN);
      log_fn(LOG_PROTOCOL_WARN, LD_DIR,
             "Bandwidth %d for router %s (%s) exceeds allowed max %d, capping",
             this_bw, router ? router->nickname : "(null)",
             fp, max_believable_bw);
      this_bw = max_believable_bw;
    }
    if (is_known) {
      bandwidths[i] = (int32_t) this_bw; // safe since MAX_BELIEVABLE<INT32_MAX
      if (is_guard)
        total_guard_bw += this_bw;
      else
        total_nonguard_bw += this_bw;
      if (is_exit)
        total_exit_bw += this_bw;
      else
        total_nonexit_bw += this_bw;
    } else {
      ++n_unknown;
      bandwidths[i] = -flags;
    }
  }

  /* Now, fill in the unknown values. */
  if (n_unknown) {