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

/**
 * \file node_select.c
 * \brief Code to choose nodes randomly based on restrictions and
 *   weighted probabilities.
 **/

#define NODE_SELECT_PRIVATE
#include "core/or/or.h"

#include "app/config/config.h"
#include "core/mainloop/connection.h"
#include "core/or/policies.h"
#include "core/or/reasons.h"
#include "feature/client/entrynodes.h"
#include "feature/dirclient/dirclient.h"
#include "feature/dircommon/directory.h"
#include "feature/nodelist/describe.h"
#include "feature/nodelist/dirlist.h"
#include "feature/nodelist/microdesc.h"
#include "feature/nodelist/networkstatus.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 "lib/container/bitarray.h"
#include "lib/crypt_ops/crypto_rand.h"
#include "lib/math/fp.h"

#include "feature/dirclient/dir_server_st.h"
#include "feature/nodelist/networkstatus_st.h"
#include "feature/nodelist/node_st.h"
#include "feature/nodelist/routerinfo_st.h"
#include "feature/nodelist/routerstatus_st.h"

static int compute_weighted_bandwidths(const smartlist_t *sl,
                                       bandwidth_weight_rule_t rule,
                                       double **bandwidths_out,
                                       double *total_bandwidth_out);
static const routerstatus_t *router_pick_trusteddirserver_impl(
                const smartlist_t *sourcelist, dirinfo_type_t auth,
                int flags, int *n_busy_out);
static const routerstatus_t *router_pick_dirserver_generic(
                              smartlist_t *sourcelist,
                              dirinfo_type_t type, int flags);

/** Try to find a running dirserver that supports operations of <b>type</b>.
 *
 * If there are no running dirservers in our routerlist and the
 * <b>PDS_RETRY_IF_NO_SERVERS</b> flag is set, set all the fallback ones
 * (including authorities) as running again, and pick one.
 *
 * If the <b>PDS_IGNORE_FASCISTFIREWALL</b> flag is set, then include
 * dirservers that we can't reach.
 *
 * If the <b>PDS_ALLOW_SELF</b> flag is not set, then don't include ourself
 * (if we're a dirserver).
 *
 * Don't pick a fallback directory mirror if any non-fallback is viable;
 * (the fallback directory mirrors include the authorities)
 * try to avoid using servers that have returned 503 recently.
 */
const routerstatus_t *
router_pick_directory_server(dirinfo_type_t type, int flags)
{
  int busy = 0;
  const routerstatus_t *choice;

  choice = router_pick_directory_server_impl(type, flags, &busy);
  if (choice || !(flags & PDS_RETRY_IF_NO_SERVERS))
    return choice;

  if (busy) {
    /* If the reason that we got no server is that servers are "busy",
     * we must be excluding good servers because we already have serverdesc
     * fetches with them.  Do not mark down servers up because of this. */
    tor_assert((flags & (PDS_NO_EXISTING_SERVERDESC_FETCH|
                         PDS_NO_EXISTING_MICRODESC_FETCH)));
    return NULL;
  }

  log_info(LD_DIR,
           "No reachable router entries for dirservers. "
           "Trying them all again.");
  /* mark all fallback directory mirrors as up again */
  router_reset_status_download_failures();
  /* try again */
  choice = router_pick_directory_server_impl(type, flags, NULL);
  return choice;
}

/** Try to find a running fallback directory. Flags are as for
 * router_pick_directory_server.
 */
const routerstatus_t *
router_pick_dirserver_generic(smartlist_t *sourcelist,
                              dirinfo_type_t type, int flags)
{
  const routerstatus_t *choice;
  int busy = 0;

  if (smartlist_len(sourcelist) == 1) {
    /* If there's only one choice, then we should disable the logic that
     * would otherwise prevent us from choosing ourself. */
    flags |= PDS_ALLOW_SELF;
  }

  choice = router_pick_trusteddirserver_impl(sourcelist, type, flags, &busy);
  if (choice || !(flags & PDS_RETRY_IF_NO_SERVERS))
    return choice;
  if (busy) {
    /* If the reason that we got no server is that servers are "busy",
     * we must be excluding good servers because we already have serverdesc
     * fetches with them.  Do not mark down servers up because of this. */
    tor_assert((flags & (PDS_NO_EXISTING_SERVERDESC_FETCH|
                         PDS_NO_EXISTING_MICRODESC_FETCH)));
    return NULL;
  }

  log_info(LD_DIR,
           "No dirservers are reachable. Trying them all again.");
  mark_all_dirservers_up(sourcelist);
  return router_pick_trusteddirserver_impl(sourcelist, type, flags, NULL);
}

/* Common retry code for router_pick_directory_server_impl and
 * router_pick_trusteddirserver_impl. Retry with the non-preferred IP version.
 * Must be called before RETRY_WITHOUT_EXCLUDE().
 *
 * If we got no result, and we are applying IP preferences, and we are a
 * client that could use an alternate IP version, try again with the
 * opposite preferences. */
#define RETRY_ALTERNATE_IP_VERSION(retry_label)                               \
  STMT_BEGIN                                                                  \
    if (result == NULL && try_ip_pref && options->ClientUseIPv4               \
        && fascist_firewall_use_ipv6(options) && !server_mode(options)        \
        && !n_busy) {                                                         \
      n_excluded = 0;                                                         \
      n_busy = 0;                                                             \
      try_ip_pref = 0;                                                        \
      goto retry_label;                                                       \
    }                                                                         \
  STMT_END                                                                    \

/* Common retry code for router_pick_directory_server_impl and
 * router_pick_trusteddirserver_impl. Retry without excluding nodes, but with
 * the preferred IP version. Must be called after RETRY_ALTERNATE_IP_VERSION().
 *
 * If we got no result, and we are excluding nodes, and StrictNodes is
 * not set, try again without excluding nodes. */
#define RETRY_WITHOUT_EXCLUDE(retry_label)                                    \
  STMT_BEGIN                                                                  \
    if (result == NULL && try_excluding && !options->StrictNodes              \
        && n_excluded && !n_busy) {                                           \
      try_excluding = 0;                                                      \
      n_excluded = 0;                                                         \
      n_busy = 0;                                                             \
      try_ip_pref = 1;                                                        \
      goto retry_label;                                                       \
    }                                                                         \
  STMT_END

/* Common code used in the loop within router_pick_directory_server_impl and
 * router_pick_trusteddirserver_impl.
 *
 * Check if the given <b>identity</b> supports extrainfo. If not, skip further
 * checks.
 */
#define SKIP_MISSING_TRUSTED_EXTRAINFO(type, identity)                        \
  STMT_BEGIN                                                                  \
    int is_trusted_extrainfo = router_digest_is_trusted_dir_type(             \
                               (identity), EXTRAINFO_DIRINFO);                \
    if (((type) & EXTRAINFO_DIRINFO) &&                                       \
        !router_supports_extrainfo((identity), is_trusted_extrainfo))         \
      continue;                                                               \
  STMT_END

#ifndef LOG_FALSE_POSITIVES_DURING_BOOTSTRAP
#define LOG_FALSE_POSITIVES_DURING_BOOTSTRAP 0
#endif

/* Log a message if rs is not found or not a preferred address */
static void
router_picked_poor_directory_log(const routerstatus_t *rs)
{
  const networkstatus_t *usable_consensus;
  usable_consensus = networkstatus_get_reasonably_live_consensus(time(NULL),
                                                 usable_consensus_flavor());

#if !LOG_FALSE_POSITIVES_DURING_BOOTSTRAP
  /* Don't log early in the bootstrap process, it's normal to pick from a
   * small pool of nodes. Of course, this won't help if we're trying to
   * diagnose bootstrap issues. */
  if (!smartlist_len(nodelist_get_list()) || !usable_consensus
      || !router_have_minimum_dir_info()) {
    return;
  }
#endif /* !LOG_FALSE_POSITIVES_DURING_BOOTSTRAP */

  /* We couldn't find a node, or the one we have doesn't fit our preferences.
   * Sometimes this is normal, sometimes it can be a reachability issue. */
  if (!rs) {
    /* This happens a lot, so it's at debug level */
    log_debug(LD_DIR, "Wanted to make an outgoing directory connection, but "
              "we couldn't find a directory that fit our criteria. "
              "Perhaps we will succeed next time with less strict criteria.");
  } else if (!fascist_firewall_allows_rs(rs, FIREWALL_OR_CONNECTION, 1)
             && !fascist_firewall_allows_rs(rs, FIREWALL_DIR_CONNECTION, 1)
             ) {
    /* This is rare, and might be interesting to users trying to diagnose
     * connection issues on dual-stack machines. */
    log_info(LD_DIR, "Selected a directory %s with non-preferred OR and Dir "
             "addresses for launching an outgoing connection: "
             "IPv4 %s OR %d Dir %d IPv6 %s OR %d Dir %d",
             routerstatus_describe(rs),
             fmt_addr32(rs->addr), rs->or_port,
             rs->dir_port, fmt_addr(&rs->ipv6_addr),
             rs->ipv6_orport, rs->dir_port);
  }
}

#undef LOG_FALSE_POSITIVES_DURING_BOOTSTRAP

/* Check if we already have a directory fetch from ap, for serverdesc
 * (including extrainfo) or microdesc documents.
 * If so, return 1, if not, return 0.
 * Also returns 0 if addr is NULL, tor_addr_is_null(addr), or dir_port is 0.
 */
STATIC int
router_is_already_dir_fetching(const tor_addr_port_t *ap, int serverdesc,
                               int microdesc)
{
  if (!ap || tor_addr_is_null(&ap->addr) || !ap->port) {
    return 0;
  }

  /* XX/teor - we're not checking tunnel connections here, see #17848
   */
  if (serverdesc && (
     connection_get_by_type_addr_port_purpose(
       CONN_TYPE_DIR, &ap->addr, ap->port, DIR_PURPOSE_FETCH_SERVERDESC)
  || connection_get_by_type_addr_port_purpose(
       CONN_TYPE_DIR, &ap->addr, ap->port, DIR_PURPOSE_FETCH_EXTRAINFO))) {
    return 1;
  }

  if (microdesc && (
     connection_get_by_type_addr_port_purpose(
       CONN_TYPE_DIR, &ap->addr, ap->port, DIR_PURPOSE_FETCH_MICRODESC))) {
    return 1;
  }

  return 0;
}

/* Check if we already have a directory fetch from the ipv4 or ipv6
 * router, for serverdesc (including extrainfo) or microdesc documents.
 * If so, return 1, if not, return 0.
 */
static int
router_is_already_dir_fetching_(uint32_t ipv4_addr,
                                const tor_addr_t *ipv6_addr,
                                uint16_t dir_port,
                                int serverdesc,
                                int microdesc)
{
  tor_addr_port_t ipv4_dir_ap, ipv6_dir_ap;

  /* Assume IPv6 DirPort is the same as IPv4 DirPort */
  tor_addr_from_ipv4h(&ipv4_dir_ap.addr, ipv4_addr);
  ipv4_dir_ap.port = dir_port;
  tor_addr_copy(&ipv6_dir_ap.addr, ipv6_addr);
  ipv6_dir_ap.port = dir_port;

  return (router_is_already_dir_fetching(&ipv4_dir_ap, serverdesc, microdesc)
       || router_is_already_dir_fetching(&ipv6_dir_ap, serverdesc, microdesc));
}

/** Pick a random running valid directory server/mirror from our
 * routerlist.  Arguments are as for router_pick_directory_server(), except:
 *
 * If <b>n_busy_out</b> is provided, set *<b>n_busy_out</b> to the number of
 * directories that we excluded for no other reason than
 * PDS_NO_EXISTING_SERVERDESC_FETCH or PDS_NO_EXISTING_MICRODESC_FETCH.
 */
STATIC const routerstatus_t *
router_pick_directory_server_impl(dirinfo_type_t type, int flags,
                                  int *n_busy_out)
{
  const or_options_t *options = get_options();
  const node_t *result;
  smartlist_t *direct, *tunnel;
  smartlist_t *trusted_direct, *trusted_tunnel;
  smartlist_t *overloaded_direct, *overloaded_tunnel;
  time_t now = time(NULL);
  const networkstatus_t *consensus = networkstatus_get_latest_consensus();
  const int requireother = ! (flags & PDS_ALLOW_SELF);
  const int fascistfirewall = ! (flags & PDS_IGNORE_FASCISTFIREWALL);
  const int no_serverdesc_fetching =(flags & PDS_NO_EXISTING_SERVERDESC_FETCH);
  const int no_microdesc_fetching = (flags & PDS_NO_EXISTING_MICRODESC_FETCH);
  int try_excluding = 1, n_excluded = 0, n_busy = 0;
  int try_ip_pref = 1;

  if (!consensus)
    return NULL;

 retry_search:

  direct = smartlist_new();
  tunnel = smartlist_new();
  trusted_direct = smartlist_new();
  trusted_tunnel = smartlist_new();
  overloaded_direct = smartlist_new();
  overloaded_tunnel = smartlist_new();

  const int skip_or_fw = router_skip_or_reachability(options, try_ip_pref);
  const int skip_dir_fw = router_skip_dir_reachability(options, try_ip_pref);
  const int must_have_or = directory_must_use_begindir(options);

  /* Find all the running dirservers we know about. */
  SMARTLIST_FOREACH_BEGIN(nodelist_get_list(), const node_t *, node) {
    int is_trusted;
    int is_overloaded;
    const routerstatus_t *status = node->rs;
    const country_t country = node->country;
    if (!status)
      continue;

    if (!node->is_running || !node_is_dir(node) || !node->is_valid)
      continue;
    if (requireother && router_digest_is_me(node->identity))
      continue;

    SKIP_MISSING_TRUSTED_EXTRAINFO(type, node->identity);

    if (try_excluding &&
        routerset_contains_routerstatus(options->ExcludeNodes, status,
                                        country)) {
      ++n_excluded;
      continue;
    }

    if (router_is_already_dir_fetching_(status->addr,
                                        &status->ipv6_addr,
                                        status->dir_port,
                                        no_serverdesc_fetching,
                                        no_microdesc_fetching)) {
      ++n_busy;
      continue;
    }

    is_overloaded = status->last_dir_503_at + DIR_503_TIMEOUT > now;
    is_trusted = router_digest_is_trusted_dir(node->identity);

    /* Clients use IPv6 addresses if the server has one and the client
     * prefers IPv6.
     * Add the router if its preferred address and port are reachable.
     * If we don't get any routers, we'll try again with the non-preferred
     * address for each router (if any). (To ensure correct load-balancing
     * we try routers that only have one address both times.)
     */
    if (!fascistfirewall || skip_or_fw ||
        fascist_firewall_allows_node(node, FIREWALL_OR_CONNECTION,
                                     try_ip_pref))
      smartlist_add(is_trusted ? trusted_tunnel :
                    is_overloaded ? overloaded_tunnel : tunnel, (void*)node);
    else if (!must_have_or && (skip_dir_fw ||
             fascist_firewall_allows_node(node, FIREWALL_DIR_CONNECTION,
                                          try_ip_pref)))
      smartlist_add(is_trusted ? trusted_direct :
                    is_overloaded ? overloaded_direct : direct, (void*)node);
  } SMARTLIST_FOREACH_END(node);

  if (smartlist_len(tunnel)) {
    result = node_sl_choose_by_bandwidth(tunnel, WEIGHT_FOR_DIR);
  } else if (smartlist_len(overloaded_tunnel)) {
    result = node_sl_choose_by_bandwidth(overloaded_tunnel,
                                                 WEIGHT_FOR_DIR);
  } else if (smartlist_len(trusted_tunnel)) {
    /* FFFF We don't distinguish between trusteds and overloaded trusteds
     * yet. Maybe one day we should. */
    /* FFFF We also don't load balance over authorities yet. I think this
     * is a feature, but it could easily be a bug. -RD */
    result = smartlist_choose(trusted_tunnel);
  } else if (smartlist_len(direct)) {
    result = node_sl_choose_by_bandwidth(direct, WEIGHT_FOR_DIR);
  } else if (smartlist_len(overloaded_direct)) {
    result = node_sl_choose_by_bandwidth(overloaded_direct,
                                         WEIGHT_FOR_DIR);
  } else {
    result = smartlist_choose(trusted_direct);
  }
  smartlist_free(direct);
  smartlist_free(tunnel);
  smartlist_free(trusted_direct);
  smartlist_free(trusted_tunnel);
  smartlist_free(overloaded_direct);
  smartlist_free(overloaded_tunnel);

  RETRY_ALTERNATE_IP_VERSION(retry_search);

  RETRY_WITHOUT_EXCLUDE(retry_search);

  if (n_busy_out)
    *n_busy_out = n_busy;

  router_picked_poor_directory_log(result ? result->rs : NULL);

  return result ? result->rs : NULL;
}

/** Given an array of double/uint64_t unions that are currently being used as
 * doubles, convert them to uint64_t, and try to scale them linearly so as to
 * much of the range of uint64_t. If <b>total_out</b> is provided, set it to
 * the sum of all elements in the array _before_ scaling. */
STATIC void
scale_array_elements_to_u64(uint64_t *entries_out, const double *entries_in,
                            int n_entries,
                            uint64_t *total_out)
{
  double total = 0.0;
  double scale_factor = 0.0;
  int i;

  for (i = 0; i < n_entries; ++i)
    total += entries_in[i];

  if (total > 0.0) {
    scale_factor = ((double)INT64_MAX) / total;
    scale_factor /= 4.0; /* make sure we're very far away from overflowing */
  }

  for (i = 0; i < n_entries; ++i)
    entries_out[i] = tor_llround(entries_in[i] * scale_factor);

  if (total_out)
    *total_out = (uint64_t) total;
}

/** Pick a random element of <b>n_entries</b>-element array <b>entries</b>,
 * choosing each element with a probability proportional to its (uint64_t)
 * value, and return the index of that element.  If all elements are 0, choose
 * an index at random. Return -1 on error.
 */
STATIC int
choose_array_element_by_weight(const uint64_t *entries, int n_entries)
{
  int i;
  uint64_t rand_val;
  uint64_t total = 0;

  for (i = 0; i < n_entries; ++i)
    total += entries[i];

  if (n_entries < 1)
    return -1;

  if (total == 0)
    return crypto_rand_int(n_entries);

  tor_assert(total < INT64_MAX);

  rand_val = crypto_rand_uint64(total);

  return select_array_member_cumulative_timei(
                           entries, n_entries, total, rand_val);
}

/** Return bw*1000, unless bw*1000 would overflow, in which case return
 * INT32_MAX. */
static inline int32_t
kb_to_bytes(uint32_t bw)
{
  return (bw > (INT32_MAX/1000)) ? INT32_MAX : bw*1000;
}

/** Helper function:
 * choose a random element of smartlist <b>sl</b> of nodes, weighted by
 * the advertised bandwidth of each element using the consensus
 * bandwidth weights.
 *
 * 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 const node_t *
smartlist_choose_node_by_bandwidth_weights(const smartlist_t *sl,
                                           bandwidth_weight_rule_t rule)
{
  double *bandwidths_dbl=NULL;
  uint64_t *bandwidths_u64=NULL;

  if (compute_weighted_bandwidths(sl, rule, &bandwidths_dbl, NULL) < 0)
    return NULL;

  bandwidths_u64 = tor_calloc(smartlist_len(sl), sizeof(uint64_t));
  scale_array_elements_to_u64(bandwidths_u64, bandwidths_dbl,
                              smartlist_len(sl), NULL);

  {
    int idx = choose_array_element_by_weight(bandwidths_u64,
                                             smartlist_len(sl));
    tor_free(bandwidths_dbl);
    tor_free(bandwidths_u64);
    return idx < 0 ? NULL : smartlist_get(sl, idx);
  }
}

/** When weighting bridges, enforce these values as lower and upper
 * bound for believable bandwidth, because there is no way for us
 * to verify a bridge's bandwidth currently. */
#define BRIDGE_MIN_BELIEVABLE_BANDWIDTH 20000  /* 20 kB/sec */
#define BRIDGE_MAX_BELIEVABLE_BANDWIDTH 100000 /* 100 kB/sec */

/** Return the smaller of the router's configured BandwidthRate
 * and its advertised capacity, making sure to stay within the
 * interval between bridge-min-believe-bw and
 * bridge-max-believe-bw. */
static uint32_t
bridge_get_advertised_bandwidth_bounded(routerinfo_t *router)
{
  uint32_t result = router->bandwidthcapacity;
  if (result > router->bandwidthrate)
    result = router->bandwidthrate;
  if (result > BRIDGE_MAX_BELIEVABLE_BANDWIDTH)
    result = BRIDGE_MAX_BELIEVABLE_BANDWIDTH;
  else if (result < BRIDGE_MIN_BELIEVABLE_BANDWIDTH)
    result = BRIDGE_MIN_BELIEVABLE_BANDWIDTH;
  return result;
}

/** Given a list of routers and a weighting rule as in
 * smartlist_choose_node_by_bandwidth_weights, compute weighted bandwidth
 * values for each node and store them in a freshly allocated
 * *<b>bandwidths_out</b> of the same length as <b>sl</b>, and holding results
 * as doubles. If <b>total_bandwidth_out</b> is non-NULL, set it to the total
 * of all the bandwidths.
 * Return 0 on success, -1 on failure. */
static int
compute_weighted_bandwidths(const smartlist_t *sl,
                            bandwidth_weight_rule_t rule,
                            double **bandwidths_out,
                            double *total_bandwidth_out)
{
  int64_t weight_scale;
  double Wg = -1, Wm = -1, We = -1, Wd = -1;
  double Wgb = -1, Wmb = -1, Web = -1, Wdb = -1;
  guardfraction_bandwidth_t guardfraction_bw;
  double *bandwidths = NULL;
  double total_bandwidth = 0.0;

  tor_assert(sl);
  tor_assert(bandwidths_out);

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

  *bandwidths_out = NULL;

  if (total_bandwidth_out) {
    *total_bandwidth_out = 0.0;
  }

  if (smartlist_len(sl) == 0) {
    log_info(LD_CIRC,
             "Empty routerlist passed in to consensus weight node "
             "selection for rule %s",
             bandwidth_weight_rule_to_string(rule));
    return -1;
  }

  weight_scale = networkstatus_get_weight_scale_param(NULL);
  tor_assert(weight_scale >= 1);

  if (rule == WEIGHT_FOR_GUARD) {
    Wg = networkstatus_get_bw_weight(NULL, "Wgg", -1);
    Wm = networkstatus_get_bw_weight(NULL, "Wgm", -1); /* Bridges */
    We = 0;
    Wd = networkstatus_get_bw_weight(NULL, "Wgd", -1);

    Wgb = networkstatus_get_bw_weight(NULL, "Wgb", -1);
    Wmb = networkstatus_get_bw_weight(NULL, "Wmb", -1);
    Web = networkstatus_get_bw_weight(NULL, "Web", -1);
    Wdb = networkstatus_get_bw_weight(NULL, "Wdb", -1);
  } else if (rule == WEIGHT_FOR_MID) {
    Wg = networkstatus_get_bw_weight(NULL, "Wmg", -1);
    Wm = networkstatus_get_bw_weight(NULL, "Wmm", -1);
    We = networkstatus_get_bw_weight(NULL, "Wme", -1);
    Wd = networkstatus_get_bw_weight(NULL, "Wmd", -1);

    Wgb = networkstatus_get_bw_weight(NULL, "Wgb", -1);
    Wmb = networkstatus_get_bw_weight(NULL, "Wmb", -1);
    Web = networkstatus_get_bw_weight(NULL, "Web", -1);
    Wdb = networkstatus_get_bw_weight(NULL, "Wdb", -1);
  } else if (rule == WEIGHT_FOR_EXIT) {
    // Guards CAN be exits if they have weird exit policies
    // They are d then I guess...
    We = networkstatus_get_bw_weight(NULL, "Wee", -1);
    Wm = networkstatus_get_bw_weight(NULL, "Wem", -1); /* Odd exit policies */
    Wd = networkstatus_get_bw_weight(NULL, "Wed", -1);
    Wg = networkstatus_get_bw_weight(NULL, "Weg", -1); /* Odd exit policies */

    Wgb = networkstatus_get_bw_weight(NULL, "Wgb", -1);
    Wmb = networkstatus_get_bw_weight(NULL, "Wmb", -1);
    Web = networkstatus_get_bw_weight(NULL, "Web", -1);
    Wdb = networkstatus_get_bw_weight(NULL, "Wdb", -1);
  } else if (rule == WEIGHT_FOR_DIR) {
    We = networkstatus_get_bw_weight(NULL, "Wbe", -1);
    Wm = networkstatus_get_bw_weight(NULL, "Wbm", -1);
    Wd = networkstatus_get_bw_weight(NULL, "Wbd", -1);
    Wg = networkstatus_get_bw_weight(NULL, "Wbg", -1);

    Wgb = Wmb = Web = Wdb = weight_scale;
  } else if (rule == NO_WEIGHTING) {
    Wg = Wm = We = Wd = weight_scale;
    Wgb = Wmb = Web = Wdb = weight_scale;
  }

  if (Wg < 0 || Wm < 0 || We < 0 || Wd < 0 || Wgb < 0 || Wmb < 0 || Wdb < 0
      || Web < 0) {
    log_debug(LD_CIRC,
              "Got negative bandwidth weights. Defaulting to naive selection"
              " algorithm.");
    Wg = Wm = We = Wd = weight_scale;
    Wgb = Wmb = Web = Wdb = weight_scale;
  }

  Wg /= weight_scale;
  Wm /= weight_scale;
  We /= weight_scale;
  Wd /= weight_scale;

  Wgb /= weight_scale;
  Wmb /= weight_scale;
  Web /= weight_scale;
  Wdb /= weight_scale;

  bandwidths = tor_calloc(smartlist_len(sl), sizeof(double));

  // Cycle through smartlist and total the bandwidth.
  static int warned_missing_bw = 0;
  SMARTLIST_FOREACH_BEGIN(sl, const node_t *, node) {
    int is_exit = 0, is_guard = 0, is_dir = 0, this_bw = 0;
    double weight = 1;
    double weight_without_guard_flag = 0; /* Used for guardfraction */
    double final_weight = 0;
    is_exit = node->is_exit && ! node->is_bad_exit;
    is_guard = node->is_possible_guard;
    is_dir = node_is_dir(node);
    if (node->rs) {
      if (!node->rs->has_bandwidth) {
        /* This should never happen, unless all the authorities downgrade
         * to 0.2.0 or rogue routerstatuses get inserted into our consensus. */
        if (! warned_missing_bw) {
          log_warn(LD_BUG,
                 "Consensus is missing some bandwidths. Using a naive "
                 "router selection algorithm");
          warned_missing_bw = 1;
        }
        this_bw = 30000; /* Chosen arbitrarily */
      } else {
        this_bw = kb_to_bytes(node->rs->bandwidth_kb);
      }
    } else if (node->ri) {
      /* bridge or other descriptor not in our consensus */
      this_bw = bridge_get_advertised_bandwidth_bounded(node->ri);
    } else {
      /* We can't use this one. */
      continue;
    }

    if (is_guard && is_exit) {
      weight = (is_dir ? Wdb*Wd : Wd);
      weight_without_guard_flag = (is_dir ? Web*We : We);
    } else if (is_guard) {
      weight = (is_dir ? Wgb*Wg : Wg);
      weight_without_guard_flag = (is_dir ? Wmb*Wm : Wm);
    } else if (is_exit) {
      weight = (is_dir ? Web*We : We);
    } else { // middle
      weight = (is_dir ? Wmb*Wm : Wm);
    }
    /* These should be impossible; but overflows here would be bad, so let's
     * make sure. */
    if (this_bw < 0)
      this_bw = 0;
    if (weight < 0.0)
      weight = 0.0;
    if (weight_without_guard_flag < 0.0)
      weight_without_guard_flag = 0.0;

    /* If guardfraction information is available in the consensus, we
     * want to calculate this router's bandwidth according to its
     * guardfraction. Quoting from proposal236:
     *
     *    Let Wpf denote the weight from the 'bandwidth-weights' line a
     *    client would apply to N for position p if it had the guard
     *    flag, Wpn the weight if it did not have the guard flag, and B the
     *    measured bandwidth of N in the consensus.  Then instead of choosing
     *    N for position p proportionally to Wpf*B or Wpn*B, clients should
     *    choose N proportionally to F*Wpf*B + (1-F)*Wpn*B.
     */
    if (node->rs && node->rs->has_guardfraction && rule != WEIGHT_FOR_GUARD) {
      /* XXX The assert should actually check for is_guard. However,
       * that crashes dirauths because of #13297. This should be
       * equivalent: */
      tor_assert(node->rs->is_possible_guard);

      guard_get_guardfraction_bandwidth(&guardfraction_bw,
                                        this_bw,
                                        node->rs->guardfraction_percentage);

      /* Calculate final_weight = F*Wpf*B + (1-F)*Wpn*B */
      final_weight =
        guardfraction_bw.guard_bw * weight +
        guardfraction_bw.non_guard_bw * weight_without_guard_flag;

      log_debug(LD_GENERAL, "%s: Guardfraction weight %f instead of %f (%s)",
                node->rs->nickname, final_weight, weight*this_bw,
                bandwidth_weight_rule_to_string(rule));
    } else { /* no guardfraction information. calculate the weight normally. */
      final_weight = weight*this_bw;
    }

    bandwidths[node_sl_idx] = final_weight;
    total_bandwidth += final_weight;
  } SMARTLIST_FOREACH_END(node);

  log_debug(LD_CIRC, "Generated weighted bandwidths for rule %s based "
            "on weights "
            "Wg=%f Wm=%f We=%f Wd=%f with total bw %f",
            bandwidth_weight_rule_to_string(rule),
            Wg, Wm, We, Wd, total_bandwidth);

  *bandwidths_out = bandwidths;

  if (total_bandwidth_out) {
    *total_bandwidth_out = total_bandwidth;
  }

  return 0;
}

/** For all nodes in <b>sl</b>, return the fraction of those nodes, weighted
 * by their weighted bandwidths with rule <b>rule</b>, for which we have
 * descriptors.
 *
 * If <b>for_direct_connect</b> is true, we intend to connect to the node
 * directly, as the first hop of a circuit; otherwise, we intend to connect
 * to it indirectly, or use it as if we were connecting to it indirectly. */
double
frac_nodes_with_descriptors(const smartlist_t *sl,
                            bandwidth_weight_rule_t rule,
                            int for_direct_conn)
{
  double *bandwidths = NULL;
  double total, present;

  if (smartlist_len(sl) == 0)
    return 0.0;

  if (compute_weighted_bandwidths(sl, rule, &bandwidths, &total) < 0 ||
      total <= 0.0) {
    int n_with_descs = 0;
    SMARTLIST_FOREACH(sl, const node_t *, node, {
      if (node_has_preferred_descriptor(node, for_direct_conn))
        n_with_descs++;
    });
    tor_free(bandwidths);
    return ((double)n_with_descs) / smartlist_len(sl);
  }

  present = 0.0;
  SMARTLIST_FOREACH_BEGIN(sl, const node_t *, node) {
    if (node_has_preferred_descriptor(node, for_direct_conn))
      present += bandwidths[node_sl_idx];
  } SMARTLIST_FOREACH_END(node);

  tor_free(bandwidths);

  return present / total;
}

/** Choose a random element of status list <b>sl</b>, weighted by
 * the advertised bandwidth of each node */
const node_t *
node_sl_choose_by_bandwidth(const smartlist_t *sl,
                            bandwidth_weight_rule_t rule)
{ /*XXXX MOVE */
  return smartlist_choose_node_by_bandwidth_weights(sl, rule);
}

/** Given a <b>router</b>, add every node_t in its family (including the
 * node itself!) to <b>sl</b>.
 *
 * Note the type mismatch: This function takes a routerinfo, but adds nodes
 * to the smartlist!
 */
static void
routerlist_add_node_and_family(smartlist_t *sl, const routerinfo_t *router)
{
  /* XXXX MOVE ? */
  node_t fake_node;
  const node_t *node = node_get_by_id(router->cache_info.identity_digest);
  if (node == NULL) {
    memset(&fake_node, 0, sizeof(fake_node));
    fake_node.ri = (routerinfo_t *)router;
    memcpy(fake_node.identity, router->cache_info.identity_digest, DIGEST_LEN);
    node = &fake_node;
  }
  nodelist_add_node_and_family(sl, node);
}

/**
 * Remove every node_t that appears in <b>excluded</b> from <b>sl</b>.
 *
 * Behaves like smartlist_subtract, but uses nodelist_idx values to deliver
 * linear performance when smartlist_subtract would be quadratic.
 **/
static void
nodelist_subtract(smartlist_t *sl, const smartlist_t *excluded)
{
  const smartlist_t *nodelist = nodelist_get_list();
  const int nodelist_len = smartlist_len(nodelist);
  bitarray_t *excluded_idx = bitarray_init_zero(nodelist_len);

  /* We haven't used nodelist_idx in this way previously, so I'm going to be
   * paranoid in this code, and check that nodelist_idx is correct for every
   * node before we use it.  If we fail, we fall back to smartlist_subtract().
   */

  /* Set the excluded_idx bit corresponding to every excluded node...
   */
  SMARTLIST_FOREACH_BEGIN(excluded, const node_t *, node) {
    const int idx = node->nodelist_idx;
    if (BUG(idx < 0) || BUG(idx >= nodelist_len) ||
        BUG(node != smartlist_get(nodelist, idx))) {
      goto internal_error;
    }
    bitarray_set(excluded_idx, idx);
  } SMARTLIST_FOREACH_END(node);

  /* Then remove them from sl.
   */
  SMARTLIST_FOREACH_BEGIN(sl, const node_t *, node) {
    const int idx = node->nodelist_idx;
    if (BUG(idx < 0) || BUG(idx >= nodelist_len) ||
        BUG(node != smartlist_get(nodelist, idx))) {
      goto internal_error;
    }
    if (bitarray_is_set(excluded_idx, idx)) {
      SMARTLIST_DEL_CURRENT(sl, node);
    }
  } SMARTLIST_FOREACH_END(node);

  bitarray_free(excluded_idx);
  return;

 internal_error:
  log_warn(LD_BUG, "Internal error prevented us from using the fast method "
           "for subtracting nodelists. Falling back to the quadratic way.");
  smartlist_subtract(sl, excluded);
  bitarray_free(excluded_idx);
}

/** Return a random running node from the nodelist. Never
 * pick a node that is in
 * <b>excludedsmartlist</b>, or which matches <b>excludedset</b>,
 * even if they are the only nodes available.
 * If <b>CRN_NEED_UPTIME</b> is set in flags and any router has more than
 * a minimum uptime, return one of those.
 * If <b>CRN_NEED_CAPACITY</b> is set in flags, weight your choice by the
 * advertised capacity of each router.
 * If <b>CRN_NEED_GUARD</b> is set in flags, consider only Guard routers.
 * If <b>CRN_WEIGHT_AS_EXIT</b> is set in flags, we weight bandwidths as if
 * picking an exit node, otherwise we weight bandwidths for picking a relay
 * node (that is, possibly discounting exit nodes).
 * If <b>CRN_NEED_DESC</b> is set in flags, we only consider nodes that
 * have a routerinfo or microdescriptor -- that is, enough info to be
 * used to build a circuit.
 * If <b>CRN_PREF_ADDR</b> is set in flags, we only consider nodes that
 * have an address that is preferred by the ClientPreferIPv6ORPort setting
 * (regardless of this flag, we exclude nodes that aren't allowed by the
 * firewall, including ClientUseIPv4 0 and fascist_firewall_use_ipv6() == 0).
 */
const node_t *
router_choose_random_node(smartlist_t *excludedsmartlist,
                          routerset_t *excludedset,
                          router_crn_flags_t flags)
{ /* XXXX MOVE */
  const int need_uptime = (flags & CRN_NEED_UPTIME) != 0;
  const int need_capacity = (flags & CRN_NEED_CAPACITY) != 0;
  const int need_guard = (flags & CRN_NEED_GUARD) != 0;
  const int weight_for_exit = (flags & CRN_WEIGHT_AS_EXIT) != 0;
  const int need_desc = (flags & CRN_NEED_DESC) != 0;
  const int pref_addr = (flags & CRN_PREF_ADDR) != 0;
  const int direct_conn = (flags & CRN_DIRECT_CONN) != 0;
  const int rendezvous_v3 = (flags & CRN_RENDEZVOUS_V3) != 0;

  const smartlist_t *node_list = nodelist_get_list();
  smartlist_t *sl=smartlist_new(),
    *excludednodes=smartlist_new();
  const node_t *choice = NULL;
  const routerinfo_t *r;
  bandwidth_weight_rule_t rule;

  tor_assert(!(weight_for_exit && need_guard));
  rule = weight_for_exit ? WEIGHT_FOR_EXIT :
    (need_guard ? WEIGHT_FOR_GUARD : WEIGHT_FOR_MID);

  SMARTLIST_FOREACH_BEGIN(node_list, const node_t *, node) {
    if (node_allows_single_hop_exits(node)) {
      /* Exclude relays that allow single hop exit circuits. This is an
       * obsolete option since 0.2.9.2-alpha and done by default in
       * 0.3.1.0-alpha. */
      smartlist_add(excludednodes, (node_t*)node);
    } else if (rendezvous_v3 &&
               !node_supports_v3_rendezvous_point(node)) {
      /* Exclude relays that do not support to rendezvous for a hidden service
       * version 3. */
      smartlist_add(excludednodes, (node_t*)node);
    }
  } SMARTLIST_FOREACH_END(node);

  /* If the node_t is not found we won't be to exclude ourself but we
   * won't be able to pick ourself in router_choose_random_node() so
   * this is fine to at least try with our routerinfo_t object. */
  if ((r = router_get_my_routerinfo()))
    routerlist_add_node_and_family(excludednodes, r);

  router_add_running_nodes_to_smartlist(sl, need_uptime, need_capacity,
                                        need_guard, need_desc, pref_addr,
                                        direct_conn);
  log_debug(LD_CIRC,
           "We found %d running nodes.",
            smartlist_len(sl));

  if (excludedsmartlist) {
    smartlist_add_all(excludednodes, excludedsmartlist);
  }
  nodelist_subtract(sl, excludednodes);

  if (excludedset) {
    routerset_subtract_nodes(sl,excludedset);
    log_debug(LD_CIRC,
              "We removed excludedset, leaving %d nodes.",
              smartlist_len(sl));
  }

  // Always weight by bandwidth
  choice = node_sl_choose_by_bandwidth(sl, rule);

  smartlist_free(sl);
  if (!choice && (need_uptime || need_capacity || need_guard || pref_addr)) {
    /* try once more -- recurse but with fewer restrictions. */
    log_info(LD_CIRC,
             "We couldn't find any live%s%s%s routers; falling back "
             "to list of all routers.",
             need_capacity?", fast":"",
             need_uptime?", stable":"",
             need_guard?", guard":"");
    flags &= ~ (CRN_NEED_UPTIME|CRN_NEED_CAPACITY|CRN_NEED_GUARD|
                CRN_PREF_ADDR);
    choice = router_choose_random_node(
                     excludedsmartlist, excludedset, flags);
  }
  smartlist_free(excludednodes);
  if (!choice) {
    log_warn(LD_CIRC,
             "No available nodes when trying to choose node. Failing.");
  }
  return choice;
}

/** Try to find a running directory authority. Flags are as for
 * router_pick_directory_server.
 */
const routerstatus_t *
router_pick_trusteddirserver(dirinfo_type_t type, int flags)
{
  return router_pick_dirserver_generic(
                                  router_get_trusted_dir_servers_mutable(),
                                  type, flags);
}

/** Try to find a running fallback directory. Flags are as for
 * router_pick_directory_server.
 */
const routerstatus_t *
router_pick_fallback_dirserver(dirinfo_type_t type, int flags)
{
  return router_pick_dirserver_generic(
                                  router_get_fallback_dir_servers_mutable(),
                                  type, flags);
}

/** Pick a random element from a list of dir_server_t, weighting by their
 * <b>weight</b> field. */
static const dir_server_t *
dirserver_choose_by_weight(const smartlist_t *servers, double authority_weight)
{
  int n = smartlist_len(servers);
  int i;
  double *weights_dbl;
  uint64_t *weights_u64;
  const dir_server_t *ds;

  weights_dbl = tor_calloc(n, sizeof(double));
  weights_u64 = tor_calloc(n, sizeof(uint64_t));
  for (i = 0; i < n; ++i) {
    ds = smartlist_get(servers, i);
    weights_dbl[i] = ds->weight;
    if (ds->is_authority)
      weights_dbl[i] *= authority_weight;
  }

  scale_array_elements_to_u64(weights_u64, weights_dbl, n, NULL);
  i = choose_array_element_by_weight(weights_u64, n);
  tor_free(weights_dbl);
  tor_free(weights_u64);
  return (i < 0) ? NULL : smartlist_get(servers, i);
}

/** Choose randomly from among the dir_server_ts in sourcelist that
 * are up. Flags are as for router_pick_directory_server_impl().
 */
static const routerstatus_t *
router_pick_trusteddirserver_impl(const smartlist_t *sourcelist,
                                  dirinfo_type_t type, int flags,
                                  int *n_busy_out)
{
  const or_options_t *options = get_options();
  smartlist_t *direct, *tunnel;
  smartlist_t *overloaded_direct, *overloaded_tunnel;
  const routerinfo_t *me = router_get_my_routerinfo();
  const routerstatus_t *result = NULL;
  time_t now = time(NULL);
  const int requireother = ! (flags & PDS_ALLOW_SELF);
  const int fascistfirewall = ! (flags & PDS_IGNORE_FASCISTFIREWALL);
  const int no_serverdesc_fetching =(flags & PDS_NO_EXISTING_SERVERDESC_FETCH);
  const int no_microdesc_fetching =(flags & PDS_NO_EXISTING_MICRODESC_FETCH);
  const double auth_weight =
    (sourcelist == router_get_fallback_dir_servers()) ?
    options->DirAuthorityFallbackRate : 1.0;
  smartlist_t *pick_from;
  int n_busy = 0;
  int try_excluding = 1, n_excluded = 0;
  int try_ip_pref = 1;

  if (!sourcelist)
    return NULL;

 retry_search:

  direct = smartlist_new();
  tunnel = smartlist_new();
  overloaded_direct = smartlist_new();
  overloaded_tunnel = smartlist_new();

  const int skip_or_fw = router_skip_or_reachability(options, try_ip_pref);
  const int skip_dir_fw = router_skip_dir_reachability(options, try_ip_pref);
  const int must_have_or = directory_must_use_begindir(options);

  SMARTLIST_FOREACH_BEGIN(sourcelist, const dir_server_t *, d)
    {
      int is_overloaded =
          d->fake_status.last_dir_503_at + DIR_503_TIMEOUT > now;
      if (!d->is_running) continue;
      if ((type & d->type) == 0)
        continue;

      SKIP_MISSING_TRUSTED_EXTRAINFO(type, d->digest);

      if (requireother && me && router_digest_is_me(d->digest))
        continue;
      if (try_excluding &&
          routerset_contains_routerstatus(options->ExcludeNodes,
                                          &d->fake_status, -1)) {
        ++n_excluded;
        continue;
      }

      if (router_is_already_dir_fetching_(d->addr,
                                          &d->ipv6_addr,
                                          d->dir_port,
                                          no_serverdesc_fetching,
                                          no_microdesc_fetching)) {
        ++n_busy;
        continue;
      }

      /* Clients use IPv6 addresses if the server has one and the client
       * prefers IPv6.
       * Add the router if its preferred address and port are reachable.
       * If we don't get any routers, we'll try again with the non-preferred
       * address for each router (if any). (To ensure correct load-balancing
       * we try routers that only have one address both times.)
       */
      if (!fascistfirewall || skip_or_fw ||
          fascist_firewall_allows_dir_server(d, FIREWALL_OR_CONNECTION,
                                             try_ip_pref))
        smartlist_add(is_overloaded ? overloaded_tunnel : tunnel, (void*)d);
      else if (!must_have_or && (skip_dir_fw ||
               fascist_firewall_allows_dir_server(d, FIREWALL_DIR_CONNECTION,
                                                  try_ip_pref)))
        smartlist_add(is_overloaded ? overloaded_direct : direct, (void*)d);
    }
  SMARTLIST_FOREACH_END(d);

  if (smartlist_len(tunnel)) {
    pick_from = tunnel;
  } else if (smartlist_len(overloaded_tunnel)) {
    pick_from = overloaded_tunnel;
  } else if (smartlist_len(direct)) {
    pick_from = direct;
  } else {
    pick_from = overloaded_direct;
  }

  {
    const dir_server_t *selection =
      dirserver_choose_by_weight(pick_from, auth_weight);

    if (selection)
      result = &selection->fake_status;
  }

  smartlist_free(direct);
  smartlist_free(tunnel);
  smartlist_free(overloaded_direct);
  smartlist_free(overloaded_tunnel);

  RETRY_ALTERNATE_IP_VERSION(retry_search);

  RETRY_WITHOUT_EXCLUDE(retry_search);

  router_picked_poor_directory_log(result);

  if (n_busy_out)
    *n_busy_out = n_busy;
  return result;
}