nodelist.c

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

/**
 * \file nodelist.c
 *
 * \brief Structures and functions for tracking what we know about the routers
 *   on the Tor network, and correlating information from networkstatus,
 *   routerinfo, and microdescs.
 *
 * The key structure here is node_t: that's the canonical way to refer
 * to a Tor relay that we might want to build a circuit through.  Every
 * node_t has either a routerinfo_t, or a routerstatus_t from the current
 * networkstatus consensus.  If it has a routerstatus_t, it will also
 * need to have a microdesc_t before you can use it for circuits.
 *
 * The nodelist_t is a global singleton that maps identities to node_t
 * objects.  Access them with the node_get_*() functions.  The nodelist_t
 * is maintained by calls throughout the codebase
 *
 * Generally, other code should not have to reach inside a node_t to
 * see what information it has.  Instead, you should call one of the
 * many accessor functions that works on a generic node_t.  If there
 * isn't one that does what you need, it's better to make such a function,
 * and then use it.
 *
 * For historical reasons, some of the functions that select a node_t
 * from the list of all usable node_t objects are in the routerlist.c
 * module, since they originally selected a routerinfo_t. (TODO: They
 * should move!)
 *
 * (TODO: Perhaps someday we should abstract the remaining ways of
 * talking about a relay to also be node_t instances. Those would be
 * routerstatus_t as used for directory requests, and dir_server_t as
 * used for authorities and fallback directories.)
 */

#define NODELIST_PRIVATE

#include "core/or/or.h"
#include "app/config/config.h"
#include "core/mainloop/mainloop.h"
#include "core/mainloop/netstatus.h"
#include "core/or/address_set.h"
#include "core/or/policies.h"
#include "core/or/protover.h"
#include "feature/client/bridges.h"
#include "feature/client/entrynodes.h"
#include "feature/control/control.h"
#include "feature/dirauth/process_descs.h"
#include "feature/dircache/dirserv.h"
#include "feature/hs/hs_client.h"
#include "feature/hs/hs_common.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/nodelist/torcert.h"
#include "feature/rend/rendservice.h"
#include "lib/encoding/binascii.h"
#include "lib/err/backtrace.h"
#include "lib/geoip/geoip.h"
#include "lib/net/address.h"

#include <string.h>

#include "feature/dirauth/authmode.h"

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

static void nodelist_drop_node(node_t *node, int remove_from_ht);
#define node_free(val) \
  FREE_AND_NULL(node_t, node_free_, (val))
static void node_free_(node_t *node);

/** count_usable_descriptors counts descriptors with these flag(s)
 */
typedef enum {
  /* All descriptors regardless of flags or exit policies */
  USABLE_DESCRIPTOR_ALL         = 0U,
  /* Only count descriptors with an exit policy that allows at least one port
   */
  USABLE_DESCRIPTOR_EXIT_POLICY = 1U << 0,
  /* Only count descriptors for relays that have the exit flag in the
   * consensus */
  USABLE_DESCRIPTOR_EXIT_FLAG   = 1U << 1,
  /* Only count descriptors for relays that have the policy and the flag */
  USABLE_DESCRIPTOR_EXIT_POLICY_AND_FLAG = (USABLE_DESCRIPTOR_EXIT_POLICY |
                                            USABLE_DESCRIPTOR_EXIT_FLAG)
} usable_descriptor_t;
static void count_usable_descriptors(int *num_present,
                                     int *num_usable,
                                     smartlist_t *descs_out,
                                     const networkstatus_t *consensus,
                                     time_t now,
                                     routerset_t *in_set,
                                     usable_descriptor_t exit_only);
static void update_router_have_minimum_dir_info(void);
static double get_frac_paths_needed_for_circs(const or_options_t *options,
                                              const networkstatus_t *ns);
static void node_add_to_address_set(const node_t *node);

/** A nodelist_t holds a node_t object for every router we're "willing to use
 * for something".  Specifically, it should hold a node_t for every node that
 * is currently in the routerlist, or currently in the consensus we're using.
 */
typedef struct nodelist_t {
  /* A list of all the nodes. */
  smartlist_t *nodes;
  /* Hash table to map from node ID digest to node. */
  HT_HEAD(nodelist_map, node_t) nodes_by_id;
  /* Hash table to map from node Ed25519 ID to node.
   *
   * Whenever a node's routerinfo or microdescriptor is about to change,
   * you should remove it from this map with node_remove_from_ed25519_map().
   * Whenever a node's routerinfo or microdescriptor has just chaned,
   * you should add it to this map with node_add_to_ed25519_map().
   */
  HT_HEAD(nodelist_ed_map, node_t) nodes_by_ed_id;

  /* Set of addresses that belong to nodes we believe in. */
  address_set_t *node_addrs;

  /* The valid-after time of the last live consensus that initialized the
   * nodelist.  We use this to detect outdated nodelists that need to be
   * rebuilt using a newer consensus. */
  time_t live_consensus_valid_after;
} nodelist_t;

static inline unsigned int
node_id_hash(const node_t *node)
{
  return (unsigned) siphash24g(node->identity, DIGEST_LEN);
}

static inline unsigned int
node_id_eq(const node_t *node1, const node_t *node2)
{
  return tor_memeq(node1->identity, node2->identity, DIGEST_LEN);
}

HT_PROTOTYPE(nodelist_map, node_t, ht_ent, node_id_hash, node_id_eq)
HT_GENERATE2(nodelist_map, node_t, ht_ent, node_id_hash, node_id_eq,
             0.6, tor_reallocarray_, tor_free_)

static inline unsigned int
node_ed_id_hash(const node_t *node)
{
  return (unsigned) siphash24g(node->ed25519_id.pubkey, ED25519_PUBKEY_LEN);
}

static inline unsigned int
node_ed_id_eq(const node_t *node1, const node_t *node2)
{
  return ed25519_pubkey_eq(&node1->ed25519_id, &node2->ed25519_id);
}

HT_PROTOTYPE(nodelist_ed_map, node_t, ed_ht_ent, node_ed_id_hash,
             node_ed_id_eq)
HT_GENERATE2(nodelist_ed_map, node_t, ed_ht_ent, node_ed_id_hash,
             node_ed_id_eq, 0.6, tor_reallocarray_, tor_free_)

/** The global nodelist. */
static nodelist_t *the_nodelist=NULL;

/** Create an empty nodelist if we haven't done so already. */
static void
init_nodelist(void)
{
  if (PREDICT_UNLIKELY(the_nodelist == NULL)) {
    the_nodelist = tor_malloc_zero(sizeof(nodelist_t));
    HT_INIT(nodelist_map, &the_nodelist->nodes_by_id);
    HT_INIT(nodelist_ed_map, &the_nodelist->nodes_by_ed_id);
    the_nodelist->nodes = smartlist_new();
  }
}

/** As node_get_by_id, but returns a non-const pointer */
MOCK_IMPL(node_t *,
node_get_mutable_by_id,(const char *identity_digest))
{
  node_t search, *node;
  if (PREDICT_UNLIKELY(the_nodelist == NULL))
    return NULL;

  memcpy(&search.identity, identity_digest, DIGEST_LEN);
  node = HT_FIND(nodelist_map, &the_nodelist->nodes_by_id, &search);
  return node;
}

/** As node_get_by_ed25519_id, but returns a non-const pointer */
node_t *
node_get_mutable_by_ed25519_id(const ed25519_public_key_t *ed_id)
{
  node_t search, *node;
  if (PREDICT_UNLIKELY(the_nodelist == NULL))
    return NULL;
  if (BUG(ed_id == NULL) || BUG(ed25519_public_key_is_zero(ed_id)))
    return NULL;

  memcpy(&search.ed25519_id, ed_id, sizeof(search.ed25519_id));
  node = HT_FIND(nodelist_ed_map, &the_nodelist->nodes_by_ed_id, &search);
  return node;
}

/** Return the node_t whose identity is <b>identity_digest</b>, or NULL
 * if no such node exists. */
MOCK_IMPL(const node_t *,
node_get_by_id,(const char *identity_digest))
{
  return node_get_mutable_by_id(identity_digest);
}

/** Return the node_t whose ed25519 identity is <b>ed_id</b>, or NULL
 * if no such node exists. */
MOCK_IMPL(const node_t *,
node_get_by_ed25519_id,(const ed25519_public_key_t *ed_id))
{
  return node_get_mutable_by_ed25519_id(ed_id);
}

/** Internal: return the node_t whose identity_digest is
 * <b>identity_digest</b>.  If none exists, create a new one, add it to the
 * nodelist, and return it.
 *
 * Requires that the nodelist be initialized.
 */
static node_t *
node_get_or_create(const char *identity_digest)
{
  node_t *node;

  if ((node = node_get_mutable_by_id(identity_digest)))
    return node;

  node = tor_malloc_zero(sizeof(node_t));
  memcpy(node->identity, identity_digest, DIGEST_LEN);
  HT_INSERT(nodelist_map, &the_nodelist->nodes_by_id, node);

  smartlist_add(the_nodelist->nodes, node);
  node->nodelist_idx = smartlist_len(the_nodelist->nodes) - 1;

  node->country = -1;

  return node;
}

/** Remove <b>node</b> from the ed25519 map (if it present), and
 * set its ed25519_id field to zero. */
static int
node_remove_from_ed25519_map(node_t *node)
{
  tor_assert(the_nodelist);
  tor_assert(node);

  if (ed25519_public_key_is_zero(&node->ed25519_id)) {
    return 0;
  }

  int rv = 0;
  node_t *search =
    HT_FIND(nodelist_ed_map, &the_nodelist->nodes_by_ed_id, node);
  if (BUG(search != node)) {
    goto clear_and_return;
  }

  search = HT_REMOVE(nodelist_ed_map, &the_nodelist->nodes_by_ed_id, node);
  tor_assert(search == node);
  rv = 1;

 clear_and_return:
  memset(&node->ed25519_id, 0, sizeof(node->ed25519_id));
  return rv;
}

/** Helper function to log details of duplicated ed2559_ids */
static void
node_log_dup_ed_id(const node_t *old, const node_t *node, const char *ed_id)
{
  char *s;
  char *olddesc = tor_strdup(node_describe(old));

  tor_asprintf(&s, "Reused ed25519_id %s: old %s new %s", ed_id,
               olddesc, node_describe(node));
  log_backtrace(LOG_NOTICE, LD_DIR, s);
  tor_free(olddesc);
  tor_free(s);
}

/** If <b>node</b> has an ed25519 id, and it is not already in the ed25519 id
 * map, set its ed25519_id field, and add it to the ed25519 map.
 */
static int
node_add_to_ed25519_map(node_t *node)
{
  tor_assert(the_nodelist);
  tor_assert(node);

  if (! ed25519_public_key_is_zero(&node->ed25519_id)) {
    return 0;
  }

  const ed25519_public_key_t *key = node_get_ed25519_id(node);
  if (!key) {
    return 0;
  }

  node_t *old;
  memcpy(&node->ed25519_id, key, sizeof(node->ed25519_id));
  old = HT_FIND(nodelist_ed_map, &the_nodelist->nodes_by_ed_id, node);
  if (old) {
    char ed_id[BASE32_BUFSIZE(sizeof(key->pubkey))];

    base32_encode(ed_id, sizeof(ed_id), (const char *)key->pubkey,
                  sizeof(key->pubkey));
    if (BUG(old == node)) {
      /* Actual bug: all callers of this function call
       * node_remove_from_ed25519_map first. */
      log_err(LD_BUG,
              "Unexpectedly found deleted node with ed25519_id %s", ed_id);
    } else {
      /* Distinct nodes sharing a ed25519 id, possibly due to relay
       * misconfiguration.  The key pinning might not catch this,
       * possibly due to downloading a missing descriptor during
       * consensus voting. */
      node_log_dup_ed_id(old, node, ed_id);
      memset(&node->ed25519_id, 0, sizeof(node->ed25519_id));
    }
    return 0;
  }

  HT_INSERT(nodelist_ed_map, &the_nodelist->nodes_by_ed_id, node);
  return 1;
}

/* For a given <b>node</b> for the consensus <b>ns</b>, set the hsdir index
 * for the node, both current and next if possible. This can only fails if the
 * node_t ed25519 identity key can't be found which would be a bug. */
STATIC void
node_set_hsdir_index(node_t *node, const networkstatus_t *ns)
{
  time_t now = approx_time();
  const ed25519_public_key_t *node_identity_pk;
  uint8_t *fetch_srv = NULL, *store_first_srv = NULL, *store_second_srv = NULL;
  uint64_t next_time_period_num, current_time_period_num;
  uint64_t fetch_tp, store_first_tp, store_second_tp;

  tor_assert(node);
  tor_assert(ns);

  if (!networkstatus_is_live(ns, now)) {
    static struct ratelim_t live_consensus_ratelim = RATELIM_INIT(30 * 60);
    log_fn_ratelim(&live_consensus_ratelim, LOG_INFO, LD_GENERAL,
                   "Not setting hsdir index with a non-live consensus.");
    goto done;
  }

  node_identity_pk = node_get_ed25519_id(node);
  if (node_identity_pk == NULL) {
    log_debug(LD_GENERAL, "ed25519 identity public key not found when "
                          "trying to build the hsdir indexes for node %s",
              node_describe(node));
    goto done;
  }

  /* Get the current and next time period number. */
  current_time_period_num = hs_get_time_period_num(0);
  next_time_period_num = hs_get_next_time_period_num(0);

  /* We always use the current time period for fetching descs */
  fetch_tp = current_time_period_num;

  /* Now extract the needed SRVs and time periods for building hsdir indices */
  if (hs_in_period_between_tp_and_srv(ns, now)) {
    fetch_srv = hs_get_current_srv(fetch_tp, ns);

    store_first_tp = hs_get_previous_time_period_num(0);
    store_second_tp = current_time_period_num;
  } else {
    fetch_srv = hs_get_previous_srv(fetch_tp, ns);

    store_first_tp = current_time_period_num;
    store_second_tp = next_time_period_num;
  }

  /* We always use the old SRV for storing the first descriptor and the latest
   * SRV for storing the second descriptor */
  store_first_srv = hs_get_previous_srv(store_first_tp, ns);
  store_second_srv = hs_get_current_srv(store_second_tp, ns);

  /* Build the fetch index. */
  hs_build_hsdir_index(node_identity_pk, fetch_srv, fetch_tp,
                       node->hsdir_index.fetch);

  /* If we are in the time segment between SRV#N and TP#N, the fetch index is
     the same as the first store index */
  if (!hs_in_period_between_tp_and_srv(ns, now)) {
    memcpy(node->hsdir_index.store_first, node->hsdir_index.fetch,
           sizeof(node->hsdir_index.store_first));
  } else {
    hs_build_hsdir_index(node_identity_pk, store_first_srv, store_first_tp,
                         node->hsdir_index.store_first);
  }

  /* If we are in the time segment between TP#N and SRV#N+1, the fetch index is
     the same as the second store index */
  if (hs_in_period_between_tp_and_srv(ns, now)) {
    memcpy(node->hsdir_index.store_second, node->hsdir_index.fetch,
           sizeof(node->hsdir_index.store_second));
  } else {
    hs_build_hsdir_index(node_identity_pk, store_second_srv, store_second_tp,
                         node->hsdir_index.store_second);
  }

 done:
  tor_free(fetch_srv);
  tor_free(store_first_srv);
  tor_free(store_second_srv);
  return;
}

/** Called when a node's address changes. */
static void
node_addrs_changed(node_t *node)
{
  node->last_reachable = node->last_reachable6 = 0;
  node->country = -1;
}

/** Add all address information about <b>node</b> to the current address
 * set (if there is one).
 */
static void
node_add_to_address_set(const node_t *node)
{
  if (!the_nodelist || !the_nodelist->node_addrs)
    return;

  /* These various address sources can be redundant, but it's likely faster
   * to add them all than to compare them all for equality. */

  if (node->rs) {
    if (node->rs->addr)
      address_set_add_ipv4h(the_nodelist->node_addrs, node->rs->addr);
    if (!tor_addr_is_null(&node->rs->ipv6_addr))
      address_set_add(the_nodelist->node_addrs, &node->rs->ipv6_addr);
  }
  if (node->ri) {
    if (node->ri->addr)
      address_set_add_ipv4h(the_nodelist->node_addrs, node->ri->addr);
    if (!tor_addr_is_null(&node->ri->ipv6_addr))
      address_set_add(the_nodelist->node_addrs, &node->ri->ipv6_addr);
  }
  if (node->md) {
    if (!tor_addr_is_null(&node->md->ipv6_addr))
      address_set_add(the_nodelist->node_addrs, &node->md->ipv6_addr);
  }
}

/** Return true if <b>addr</b> is the address of some node in the nodelist.
 * If not, probably return false. */
int
nodelist_probably_contains_address(const tor_addr_t *addr)
{
  if (BUG(!addr))
    return 0;

  if (!the_nodelist || !the_nodelist->node_addrs)
    return 0;

  return address_set_probably_contains(the_nodelist->node_addrs, addr);
}

/** Add <b>ri</b> to an appropriate node in the nodelist.  If we replace an
 * old routerinfo, and <b>ri_old_out</b> is not NULL, set *<b>ri_old_out</b>
 * to the previous routerinfo.
 */
node_t *
nodelist_set_routerinfo(routerinfo_t *ri, routerinfo_t **ri_old_out)
{
  node_t *node;
  const char *id_digest;
  int had_router = 0;
  tor_assert(ri);

  init_nodelist();
  id_digest = ri->cache_info.identity_digest;
  node = node_get_or_create(id_digest);

  node_remove_from_ed25519_map(node);

  if (node->ri) {
    if (!routers_have_same_or_addrs(node->ri, ri)) {
      node_addrs_changed(node);
    }
    had_router = 1;
    if (ri_old_out)
      *ri_old_out = node->ri;
  } else {
    if (ri_old_out)
      *ri_old_out = NULL;
  }
  node->ri = ri;

  node_add_to_ed25519_map(node);

  if (node->country == -1)
    node_set_country(node);

  if (authdir_mode(get_options()) && !had_router) {
    const char *discard=NULL;
    uint32_t status = dirserv_router_get_status(ri, &discard, LOG_INFO);
    dirserv_set_node_flags_from_authoritative_status(node, status);
  }

  /* Setting the HSDir index requires the ed25519 identity key which can
   * only be found either in the ri or md. This is why this is called here.
   * Only nodes supporting HSDir=2 protocol version needs this index. */
  if (node->rs && node->rs->pv.supports_v3_hsdir) {
    node_set_hsdir_index(node,
                         networkstatus_get_latest_consensus());
  }

  node_add_to_address_set(node);

  return node;
}

/** Set the appropriate node_t to use <b>md</b> as its microdescriptor.
 *
 * Called when a new microdesc has arrived and the usable consensus flavor
 * is "microdesc".
 **/
node_t *
nodelist_add_microdesc(microdesc_t *md)
{
  networkstatus_t *ns =
    networkstatus_get_latest_consensus_by_flavor(FLAV_MICRODESC);
  const routerstatus_t *rs;
  node_t *node;
  if (ns == NULL)
    return NULL;
  init_nodelist();

  /* Microdescriptors don't carry an identity digest, so we need to figure
   * it out by looking up the routerstatus. */
  rs = router_get_consensus_status_by_descriptor_digest(ns, md->digest);
  if (rs == NULL)
    return NULL;
  node = node_get_mutable_by_id(rs->identity_digest);
  if (node == NULL)
    return NULL;

  node_remove_from_ed25519_map(node);
  if (node->md)
    node->md->held_by_nodes--;

  node->md = md;
  md->held_by_nodes++;
  /* Setting the HSDir index requires the ed25519 identity key which can
   * only be found either in the ri or md. This is why this is called here.
   * Only nodes supporting HSDir=2 protocol version needs this index. */
  if (rs->pv.supports_v3_hsdir) {
    node_set_hsdir_index(node, ns);
  }
  node_add_to_ed25519_map(node);
  node_add_to_address_set(node);

  return node;
}

/* Default value. */
#define ESTIMATED_ADDRESS_PER_NODE 2

/* Return the estimated number of address per node_t. This is used for the
 * size of the bloom filter in the nodelist (node_addrs). */
MOCK_IMPL(int,
get_estimated_address_per_node, (void))
{
  return ESTIMATED_ADDRESS_PER_NODE;
}

/** Tell the nodelist that the current usable consensus is <b>ns</b>.
 * This makes the nodelist change all of the routerstatus entries for
 * the nodes, drop nodes that no longer have enough info to get used,
 * and grab microdescriptors into nodes as appropriate.
 */
void
nodelist_set_consensus(networkstatus_t *ns)
{
  const or_options_t *options = get_options();
  int authdir = authdir_mode_v3(options);

  init_nodelist();
  if (ns->flavor == FLAV_MICRODESC)
    (void) get_microdesc_cache(); /* Make sure it exists first. */

  SMARTLIST_FOREACH(the_nodelist->nodes, node_t *, node,
                    node->rs = NULL);

  /* Conservatively estimate that every node will have 2 addresses. */
  const int estimated_addresses = smartlist_len(ns->routerstatus_list) *
                                  get_estimated_address_per_node();
  address_set_free(the_nodelist->node_addrs);
  the_nodelist->node_addrs = address_set_new(estimated_addresses);

  SMARTLIST_FOREACH_BEGIN(ns->routerstatus_list, routerstatus_t *, rs) {
    node_t *node = node_get_or_create(rs->identity_digest);
    node->rs = rs;
    if (ns->flavor == FLAV_MICRODESC) {
      if (node->md == NULL ||
          tor_memneq(node->md->digest,rs->descriptor_digest,DIGEST256_LEN)) {
        node_remove_from_ed25519_map(node);
        if (node->md)
          node->md->held_by_nodes--;
        node->md = microdesc_cache_lookup_by_digest256(NULL,
                                                       rs->descriptor_digest);
        if (node->md)
          node->md->held_by_nodes++;
        node_add_to_ed25519_map(node);
      }
    }

    if (rs->pv.supports_v3_hsdir) {
      node_set_hsdir_index(node, ns);
    }
    node_set_country(node);

    /* If we're not an authdir, believe others. */
    if (!authdir) {
      node->is_valid = rs->is_valid;
      node->is_running = rs->is_flagged_running;
      node->is_fast = rs->is_fast;
      node->is_stable = rs->is_stable;
      node->is_possible_guard = rs->is_possible_guard;
      node->is_exit = rs->is_exit;
      node->is_bad_exit = rs->is_bad_exit;
      node->is_hs_dir = rs->is_hs_dir;
      node->ipv6_preferred = 0;
      if (fascist_firewall_prefer_ipv6_orport(options) &&
          (tor_addr_is_null(&rs->ipv6_addr) == 0 ||
           (node->md && tor_addr_is_null(&node->md->ipv6_addr) == 0)))
        node->ipv6_preferred = 1;
    }

  } SMARTLIST_FOREACH_END(rs);

  nodelist_purge();

  /* Now add all the nodes we have to the address set. */
  SMARTLIST_FOREACH_BEGIN(the_nodelist->nodes, node_t *, node) {
    node_add_to_address_set(node);
  } SMARTLIST_FOREACH_END(node);

  if (! authdir) {
    SMARTLIST_FOREACH_BEGIN(the_nodelist->nodes, node_t *, node) {
      /* We have no routerstatus for this router. Clear flags so we can skip
       * it, maybe.*/
      if (!node->rs) {
        tor_assert(node->ri); /* if it had only an md, or nothing, purge
                               * would have removed it. */
        if (node->ri->purpose == ROUTER_PURPOSE_GENERAL) {
          /* Clear all flags. */
          node->is_valid = node->is_running = node->is_hs_dir =
            node->is_fast = node->is_stable =
            node->is_possible_guard = node->is_exit =
            node->is_bad_exit = node->ipv6_preferred = 0;
        }
      }
    } SMARTLIST_FOREACH_END(node);
  }

  /* If the consensus is live, note down the consensus valid-after that formed
   * the nodelist. */
  if (networkstatus_is_live(ns, approx_time())) {
    the_nodelist->live_consensus_valid_after = ns->valid_after;
  }
}

/** Return 1 iff <b>node</b> has Exit flag and no BadExit flag.
 * Otherwise, return 0.
 */
int
node_is_good_exit(const node_t *node)
{
  return node->is_exit && ! node->is_bad_exit;
}

/** Helper: return true iff a node has a usable amount of information*/
static inline int
node_is_usable(const node_t *node)
{
  return (node->rs) || (node->ri);
}

/** Tell the nodelist that <b>md</b> is no longer a microdescriptor for the
 * node with <b>identity_digest</b>. */
void
nodelist_remove_microdesc(const char *identity_digest, microdesc_t *md)
{
  node_t *node = node_get_mutable_by_id(identity_digest);
  if (node && node->md == md) {
    node->md = NULL;
    md->held_by_nodes--;
    if (! node_get_ed25519_id(node)) {
      node_remove_from_ed25519_map(node);
    }
  }
}

/** Tell the nodelist that <b>ri</b> is no longer in the routerlist. */
void
nodelist_remove_routerinfo(routerinfo_t *ri)
{
  node_t *node = node_get_mutable_by_id(ri->cache_info.identity_digest);
  if (node && node->ri == ri) {
    node->ri = NULL;
    if (! node_is_usable(node)) {
      nodelist_drop_node(node, 1);
      node_free(node);
    }
  }
}

/** Remove <b>node</b> from the nodelist.  (Asserts that it was there to begin
 * with.) */
static void
nodelist_drop_node(node_t *node, int remove_from_ht)
{
  node_t *tmp;
  int idx;
  if (remove_from_ht) {
    tmp = HT_REMOVE(nodelist_map, &the_nodelist->nodes_by_id, node);
    tor_assert(tmp == node);
  }
  node_remove_from_ed25519_map(node);

  idx = node->nodelist_idx;
  tor_assert(idx >= 0);

  tor_assert(node == smartlist_get(the_nodelist->nodes, idx));
  smartlist_del(the_nodelist->nodes, idx);
  if (idx < smartlist_len(the_nodelist->nodes)) {
    tmp = smartlist_get(the_nodelist->nodes, idx);
    tmp->nodelist_idx = idx;
  }
  node->nodelist_idx = -1;
}

/** Return a newly allocated smartlist of the nodes that have <b>md</b> as
 * their microdescriptor. */
smartlist_t *
nodelist_find_nodes_with_microdesc(const microdesc_t *md)
{
  smartlist_t *result = smartlist_new();

  if (the_nodelist == NULL)
    return result;

  SMARTLIST_FOREACH_BEGIN(the_nodelist->nodes, node_t *, node) {
    if (node->md == md) {
      smartlist_add(result, node);
    }
  } SMARTLIST_FOREACH_END(node);

  return result;
}

/** Release storage held by <b>node</b>  */
static void
node_free_(node_t *node)
{
  if (!node)
    return;
  if (node->md)
    node->md->held_by_nodes--;
  tor_assert(node->nodelist_idx == -1);
  tor_free(node);
}

/** Remove all entries from the nodelist that don't have enough info to be
 * usable for anything. */
void
nodelist_purge(void)
{
  node_t **iter;
  if (PREDICT_UNLIKELY(the_nodelist == NULL))
    return;

  /* Remove the non-usable nodes. */
  for (iter = HT_START(nodelist_map, &the_nodelist->nodes_by_id); iter; ) {
    node_t *node = *iter;

    if (node->md && !node->rs) {
      /* An md is only useful if there is an rs. */
      node->md->held_by_nodes--;
      node->md = NULL;
    }

    if (node_is_usable(node)) {
      iter = HT_NEXT(nodelist_map, &the_nodelist->nodes_by_id, iter);
    } else {
      iter = HT_NEXT_RMV(nodelist_map, &the_nodelist->nodes_by_id, iter);
      nodelist_drop_node(node, 0);
      node_free(node);
    }
  }
  nodelist_assert_ok();
}

/** Release all storage held by the nodelist. */
void
nodelist_free_all(void)
{
  if (PREDICT_UNLIKELY(the_nodelist == NULL))
    return;

  HT_CLEAR(nodelist_map, &the_nodelist->nodes_by_id);
  HT_CLEAR(nodelist_ed_map, &the_nodelist->nodes_by_ed_id);
  SMARTLIST_FOREACH_BEGIN(the_nodelist->nodes, node_t *, node) {
    node->nodelist_idx = -1;
    node_free(node);
  } SMARTLIST_FOREACH_END(node);

  smartlist_free(the_nodelist->nodes);

  address_set_free(the_nodelist->node_addrs);
  the_nodelist->node_addrs = NULL;

  tor_free(the_nodelist);
}

/** Check that the nodelist is internally consistent, and consistent with
 * the directory info it's derived from.
 */
void
nodelist_assert_ok(void)
{
  routerlist_t *rl = router_get_routerlist();
  networkstatus_t *ns = networkstatus_get_latest_consensus();
  digestmap_t *dm;

  if (!the_nodelist)
    return;

  dm = digestmap_new();

  /* every routerinfo in rl->routers should be in the nodelist. */
  if (rl) {
    SMARTLIST_FOREACH_BEGIN(rl->routers, routerinfo_t *, ri) {
      const node_t *node = node_get_by_id(ri->cache_info.identity_digest);
      tor_assert(node && node->ri == ri);
      tor_assert(fast_memeq(ri->cache_info.identity_digest,
                             node->identity, DIGEST_LEN));
      tor_assert(! digestmap_get(dm, node->identity));
      digestmap_set(dm, node->identity, (void*)node);
    } SMARTLIST_FOREACH_END(ri);
  }

  /* every routerstatus in ns should be in the nodelist */
  if (ns) {
    SMARTLIST_FOREACH_BEGIN(ns->routerstatus_list, routerstatus_t *, rs) {
      const node_t *node = node_get_by_id(rs->identity_digest);
      tor_assert(node && node->rs == rs);
      tor_assert(fast_memeq(rs->identity_digest, node->identity, DIGEST_LEN));
      digestmap_set(dm, node->identity, (void*)node);
      if (ns->flavor == FLAV_MICRODESC) {
        /* If it's a microdesc consensus, every entry that has a
         * microdescriptor should be in the nodelist.
         */
        microdesc_t *md =
          microdesc_cache_lookup_by_digest256(NULL, rs->descriptor_digest);
        tor_assert(md == node->md);
        if (md)
          tor_assert(md->held_by_nodes >= 1);
      }
    } SMARTLIST_FOREACH_END(rs);
  }

  /* The nodelist should have no other entries, and its entries should be
   * well-formed. */
  SMARTLIST_FOREACH_BEGIN(the_nodelist->nodes, node_t *, node) {
    tor_assert(digestmap_get(dm, node->identity) != NULL);
    tor_assert(node_sl_idx == node->nodelist_idx);
  } SMARTLIST_FOREACH_END(node);

  /* Every node listed with an ed25519 identity should be listed by that
   * identity.
   */
  SMARTLIST_FOREACH_BEGIN(the_nodelist->nodes, node_t *, node) {
    if (!ed25519_public_key_is_zero(&node->ed25519_id)) {
      tor_assert(node == node_get_by_ed25519_id(&node->ed25519_id));
    }
  } SMARTLIST_FOREACH_END(node);

  node_t **idx;
  HT_FOREACH(idx, nodelist_ed_map, &the_nodelist->nodes_by_ed_id) {
    node_t *node = *idx;
    tor_assert(node == node_get_by_ed25519_id(&node->ed25519_id));
  }

  tor_assert((long)smartlist_len(the_nodelist->nodes) ==
             (long)HT_SIZE(&the_nodelist->nodes_by_id));

  tor_assert((long)smartlist_len(the_nodelist->nodes) >=
             (long)HT_SIZE(&the_nodelist->nodes_by_ed_id));

  digestmap_free(dm, NULL);
}

/** Ensure that the nodelist has been created with the most recent consensus.
 *  If that's not the case, make it so.  */
void
nodelist_ensure_freshness(networkstatus_t *ns)
{
  tor_assert(ns);

  /* We don't even have a nodelist: this is a NOP. */
  if (!the_nodelist) {
    return;
  }

  if (the_nodelist->live_consensus_valid_after != ns->valid_after) {
    log_info(LD_GENERAL, "Nodelist was not fresh: rebuilding. (%d / %d)",
             (int) the_nodelist->live_consensus_valid_after,
             (int) ns->valid_after);
    nodelist_set_consensus(ns);
  }
}
/** Return a list of a node_t * for every node we know about.  The caller
 * MUST NOT modify the list. (You can set and clear flags in the nodes if
 * you must, but you must not add or remove nodes.) */
MOCK_IMPL(smartlist_t *,
nodelist_get_list,(void))
{
  init_nodelist();
  return the_nodelist->nodes;
}

/** Given a hex-encoded nickname of the format DIGEST, $DIGEST, $DIGEST=name,
 * or $DIGEST~name, return the node with the matching identity digest and
 * nickname (if any).  Return NULL if no such node exists, or if <b>hex_id</b>
 * is not well-formed. DOCDOC flags */
const node_t *
node_get_by_hex_id(const char *hex_id, unsigned flags)
{
  char digest_buf[DIGEST_LEN];
  char nn_buf[MAX_NICKNAME_LEN+1];
  char nn_char='\0';

  (void) flags; // XXXX

  if (hex_digest_nickname_decode(hex_id, digest_buf, &nn_char, nn_buf)==0) {
    const node_t *node = node_get_by_id(digest_buf);
    if (!node)
      return NULL;
    if (nn_char == '=') {
      /* "=" indicates a Named relay, but there aren't any of those now. */
      return NULL;
    }
    return node;
  }

  return NULL;
}

/** Given a nickname (possibly verbose, possibly a hexadecimal digest), return
 * the corresponding node_t, or NULL if none exists. Warn the user if they
 * have specified a router by nickname, unless the NNF_NO_WARN_UNNAMED bit is
 * set in <b>flags</b>. */
MOCK_IMPL(const node_t *,
node_get_by_nickname,(const char *nickname, unsigned flags))
{
  const int warn_if_unnamed = !(flags & NNF_NO_WARN_UNNAMED);

  if (!the_nodelist)
    return NULL;

  /* Handle these cases: DIGEST, $DIGEST, $DIGEST=name, $DIGEST~name. */
  {
    const node_t *node;
    if ((node = node_get_by_hex_id(nickname, flags)) != NULL)
      return node;
  }

  if (!strcasecmp(nickname, UNNAMED_ROUTER_NICKNAME))
    return NULL;