Merge branch 'split_routerlist.c_rebased'

19 files changed, 1040 insertions, 1108 deletions

diff --git a/src/or/circuitbuild.c b/src/or/circuitbuild.c
index e9d010ee30..d4969239cb 100644
--- a/src/or/circuitbuild.c
+++ b/src/or/circuitbuild.c
@@ -33,6 +33,7 @@
 #include "router.h"
 #include "routerlist.h"
 #include "routerparse.h"
+#include "routerset.h"
 #include "statefile.h"
 #include "crypto.h"
 #undef log
diff --git a/src/or/circuitlist.c b/src/or/circuitlist.c
index 7ed942c8fe..d9b74bd4c2 100644
--- a/src/or/circuitlist.c
+++ b/src/or/circuitlist.c
@@ -26,6 +26,7 @@
 #include "rendcommon.h"
 #include "rephist.h"
 #include "routerlist.h"
+#include "routerset.h"
 #include "ht.h"
 
 /********* START VARIABLES **********/
diff --git a/src/or/config.c b/src/or/config.c
index 3536db6d07..4557853cec 100644
--- a/src/or/config.c
+++ b/src/or/config.c
@@ -28,6 +28,7 @@
 #include "hibernate.h"
 #include "main.h"
 #include "networkstatus.h"
+#include "nodelist.h"
 #include "policies.h"
 #include "relay.h"
 #include "rendclient.h"
@@ -36,6 +37,7 @@
 #include "router.h"
 #include "util.h"
 #include "routerlist.h"
+#include "routerset.h"
 #include "statefile.h"
 #include "transports.h"
 #ifdef _WIN32
diff --git a/src/or/confparse.c b/src/or/confparse.c
index 203395d081..67cf43fe8c 100644
--- a/src/or/confparse.c
+++ b/src/or/confparse.c
@@ -6,7 +6,7 @@
 
 #include "or.h"
 #include "confparse.h"
-#include "routerlist.h"
+#include "routerset.h"
 
 static uint64_t config_parse_memunit(const char *s, int *ok);
 static int config_parse_msec_interval(const char *s, int *ok);
diff --git a/src/or/connection_edge.c b/src/or/connection_edge.c
index 1592033c54..ade3b48df2 100644
--- a/src/or/connection_edge.c
+++ b/src/or/connection_edge.c
@@ -33,6 +33,7 @@
 #include "rephist.h"
 #include "router.h"
 #include "routerlist.h"
+#include "routerset.h"
 
 #ifdef HAVE_LINUX_TYPES_H
 #include <linux/types.h>
diff --git a/src/or/control.c b/src/or/control.c
index bb893267df..74c6acc000 100644
--- a/src/or/control.c
+++ b/src/or/control.c
@@ -1639,10 +1639,13 @@ getinfo_helper_dir(control_connection_t *control_conn,
                    const char *question, char **answer,
                    const char **errmsg)
 {
-  const routerinfo_t *ri;
+  const node_t *node;
+  const routerinfo_t *ri = NULL;
   (void) control_conn;
   if (!strcmpstart(question, "desc/id/")) {
-    ri = router_get_by_hexdigest(question+strlen("desc/id/"));
+    node = node_get_by_hex_id(question+strlen("desc/id/"));
+    if (node)
+      ri = node->ri;
     if (ri) {
       const char *body = signed_descriptor_get_body(&ri->cache_info);
       if (body)
@@ -1651,7 +1654,9 @@ getinfo_helper_dir(control_connection_t *control_conn,
   } else if (!strcmpstart(question, "desc/name/")) {
     /* XXX023 Setting 'warn_if_unnamed' here is a bit silly -- the
      * warning goes to the user, not to the controller. */
-    ri = router_get_by_nickname(question+strlen("desc/name/"),1);
+    node = node_get_by_nickname(question+strlen("desc/name/"), 1);
+    if (node)
+      ri = node->ri;
     if (ri) {
       const char *body = signed_descriptor_get_body(&ri->cache_info);
       if (body)
@@ -1713,8 +1718,9 @@ getinfo_helper_dir(control_connection_t *control_conn,
       *answer = tor_strndup(md->body, md->bodylen);
     }
   } else if (!strcmpstart(question, "desc-annotations/id/")) {
-    ri = router_get_by_hexdigest(question+
-                                 strlen("desc-annotations/id/"));
+    node = node_get_by_hex_id(question+strlen("desc-annotations/id/"));
+    if (node)
+      ri = node->ri;
     if (ri) {
       const char *annotations =
         signed_descriptor_get_annotations(&ri->cache_info);
diff --git a/src/or/directory.c b/src/or/directory.c
index effccc5856..7df91fb57e 100644
--- a/src/or/directory.c
+++ b/src/or/directory.c
@@ -25,6 +25,7 @@
 #include "router.h"
 #include "routerlist.h"
 #include "routerparse.h"
+#include "routerset.h"
 
 #if defined(EXPORTMALLINFO) && defined(HAVE_MALLOC_H) && defined(HAVE_MALLINFO)
 #ifndef OPENBSD
diff --git a/src/or/include.am b/src/or/include.am
index 5c93e3e598..e9811ec962 100644
--- a/src/or/include.am
+++ b/src/or/include.am
@@ -53,6 +53,7 @@ src_or_libtor_a_SOURCES = \
 	src/or/router.c					\
 	src/or/routerlist.c				\
 	src/or/routerparse.c				\
+	src/or/routerset.c				\
 	src/or/statefile.c				\
 	src/or/status.c					\
 	$(evdns_source)					\
@@ -124,6 +125,7 @@ ORHEADERS = \
 	src/or/replaycache.h				\
 	src/or/router.h					\
 	src/or/routerlist.h				\
+	src/or/routerset.h				\
 	src/or/routerparse.h				\
 	src/or/statefile.h				\
 	src/or/status.h
diff --git a/src/or/networkstatus.c b/src/or/networkstatus.c
index ff31f82ff6..0cc6a21085 100644
--- a/src/or/networkstatus.c
+++ b/src/or/networkstatus.c
@@ -2304,6 +2304,30 @@ networkstatus_parse_flavor_name(const char *flavname)
     return -1;
 }
 
+/** Return 0 if this routerstatus is obsolete, too new, isn't
+ * running, or otherwise not a descriptor that we would make any
+ * use of even if we had it. Else return 1. */
+int
+client_would_use_router(const routerstatus_t *rs, time_t now,
+                        const or_options_t *options)
+{
+  if (!rs->is_flagged_running && !options->FetchUselessDescriptors) {
+    /* If we had this router descriptor, we wouldn't even bother using it.
+     * But, if we want to have a complete list, fetch it anyway. */
+    return 0;
+  }
+  if (rs->published_on + options->TestingEstimatedDescriptorPropagationTime
+      > now) {
+    /* Most caches probably don't have this descriptor yet. */
+    return 0;
+  }
+  if (rs->published_on + OLD_ROUTER_DESC_MAX_AGE < now) {
+    /* We'd drop it immediately for being too old. */
+    return 0;
+  }
+  return 1;
+}
+
 /** If <b>question</b> is a string beginning with "ns/" in a format the
  * control interface expects for a GETINFO question, set *<b>answer</b> to a
  * newly-allocated string containing networkstatus lines for the appropriate
diff --git a/src/or/networkstatus.h b/src/or/networkstatus.h
index 0af17512dd..dcd58f8898 100644
--- a/src/or/networkstatus.h
+++ b/src/or/networkstatus.h
@@ -71,6 +71,8 @@ int should_delay_dir_fetches(const or_options_t *options);
 void update_networkstatus_downloads(time_t now);
 void update_certificate_downloads(time_t now);
 int consensus_is_waiting_for_certs(void);
+int client_would_use_router(const routerstatus_t *rs, time_t now,
+                            const or_options_t *options);
 networkstatus_v2_t *networkstatus_v2_get_by_digest(const char *digest);
 networkstatus_t *networkstatus_get_latest_consensus(void);
 networkstatus_t *networkstatus_get_latest_consensus_by_flavor(
diff --git a/src/or/nodelist.c b/src/or/nodelist.c
index b96491f5f9..c357bc0474 100644
--- a/src/or/nodelist.c
+++ b/src/or/nodelist.c
@@ -5,19 +5,26 @@
 /* See LICENSE for licensing information */
 
 #include "or.h"
+#include "address.h"
 #include "config.h"
+#include "control.h"
 #include "dirserv.h"
+#include "geoip.h"
+#include "main.h"
 #include "microdesc.h"
 #include "networkstatus.h"
 #include "nodelist.h"
 #include "policies.h"
+#include "rendservice.h"
 #include "router.h"
 #include "routerlist.h"
+#include "routerset.h"
 
 #include <string.h>
 
 static void nodelist_drop_node(node_t *node, int remove_from_ht);
 static void node_free(node_t *node);
+static void update_router_have_minimum_dir_info(void);
 
 /** 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
@@ -905,3 +912,496 @@ node_get_pref_ipv6_orport(const node_t *node, tor_addr_port_t *ap_out)
   }
 }
 
+/** Refresh the country code of <b>ri</b>.  This function MUST be called on
+ * each router when the GeoIP database is reloaded, and on all new routers. */
+void
+node_set_country(node_t *node)
+{
+  if (node->rs)
+    node->country = geoip_get_country_by_ip(node->rs->addr);
+  else if (node->ri)
+    node->country = geoip_get_country_by_ip(node->ri->addr);
+  else
+    node->country = -1;
+}
+
+/** Set the country code of all routers in the routerlist. */
+void
+nodelist_refresh_countries(void)
+{
+  smartlist_t *nodes = nodelist_get_list();
+  SMARTLIST_FOREACH(nodes, node_t *, node,
+                    node_set_country(node));
+}
+
+/** Return true iff router1 and router2 have similar enough network addresses
+ * that we should treat them as being in the same family */
+static INLINE int
+addrs_in_same_network_family(const tor_addr_t *a1,
+                             const tor_addr_t *a2)
+{
+  return 0 == tor_addr_compare_masked(a1, a2, 16, CMP_SEMANTIC);
+}
+
+/** Return true if <b>node</b>'s nickname matches <b>nickname</b>
+ * (case-insensitive), or if <b>node's</b> identity key digest
+ * matches a hexadecimal value stored in <b>nickname</b>.  Return
+ * false otherwise. */
+static int
+node_nickname_matches(const node_t *node, const char *nickname)
+{
+  const char *n = node_get_nickname(node);
+  if (n && nickname[0]!='$' && !strcasecmp(n, nickname))
+    return 1;
+  return hex_digest_nickname_matches(nickname,
+                                     node->identity,
+                                     n,
+                                     node_is_named(node));
+}
+
+/** Return true iff <b>node</b> is named by some nickname in <b>lst</b>. */
+static INLINE int
+node_in_nickname_smartlist(const smartlist_t *lst, const node_t *node)
+{
+  if (!lst) return 0;
+  SMARTLIST_FOREACH(lst, const char *, name, {
+    if (node_nickname_matches(node, name))
+      return 1;
+  });
+  return 0;
+}
+
+/** Return true iff r1 and r2 are in the same family, but not the same
+ * router. */
+int
+nodes_in_same_family(const node_t *node1, const node_t *node2)
+{
+  const or_options_t *options = get_options();
+
+  /* Are they in the same family because of their addresses? */
+  if (options->EnforceDistinctSubnets) {
+    tor_addr_t a1, a2;
+    node_get_addr(node1, &a1);
+    node_get_addr(node2, &a2);
+    if (addrs_in_same_network_family(&a1, &a2))
+      return 1;
+  }
+
+  /* Are they in the same family because the agree they are? */
+  {
+    const smartlist_t *f1, *f2;
+    f1 = node_get_declared_family(node1);
+    f2 = node_get_declared_family(node2);
+    if (f1 && f2 &&
+        node_in_nickname_smartlist(f1, node2) &&
+        node_in_nickname_smartlist(f2, node1))
+      return 1;
+  }
+
+  /* Are they in the same option because the user says they are? */
+  if (options->NodeFamilySets) {
+    SMARTLIST_FOREACH(options->NodeFamilySets, const routerset_t *, rs, {
+        if (routerset_contains_node(rs, node1) &&
+            routerset_contains_node(rs, node2))
+          return 1;
+      });
+  }
+
+  return 0;
+}
+
+/**
+ * Add all the family of <b>node</b>, including <b>node</b> itself, to
+ * the smartlist <b>sl</b>.
+ *
+ * This is used to make sure we don't pick siblings in a single path, or
+ * pick more than one relay from a family for our entry guard list.
+ * Note that a node may be added to <b>sl</b> more than once if it is
+ * part of <b>node</b>'s family for more than one reason.
+ */
+void
+nodelist_add_node_and_family(smartlist_t *sl, const node_t *node)
+{
+  const smartlist_t *all_nodes = nodelist_get_list();
+  const smartlist_t *declared_family;
+  const or_options_t *options = get_options();
+
+  tor_assert(node);
+
+  declared_family = node_get_declared_family(node);
+
+  /* Let's make sure that we have the node itself, if it's a real node. */
+  {
+    const node_t *real_node = node_get_by_id(node->identity);
+    if (real_node)
+      smartlist_add(sl, (node_t*)real_node);
+  }
+
+  /* First, add any nodes with similar network addresses. */
+  if (options->EnforceDistinctSubnets) {
+    tor_addr_t node_addr;
+    node_get_addr(node, &node_addr);
+
+    SMARTLIST_FOREACH_BEGIN(all_nodes, const node_t *, node2) {
+      tor_addr_t a;
+      node_get_addr(node2, &a);
+      if (addrs_in_same_network_family(&a, &node_addr))
+        smartlist_add(sl, (void*)node2);
+    } SMARTLIST_FOREACH_END(node2);
+  }
+
+  /* Now, add all nodes in the declared_family of this node, if they
+   * also declare this node to be in their family. */
+  if (declared_family) {
+    /* Add every r such that router declares familyness with node, and node
+     * declares familyhood with router. */
+    SMARTLIST_FOREACH_BEGIN(declared_family, const char *, name) {
+      const node_t *node2;
+      const smartlist_t *family2;
+      if (!(node2 = node_get_by_nickname(name, 0)))
+        continue;
+      if (!(family2 = node_get_declared_family(node2)))
+        continue;
+      SMARTLIST_FOREACH_BEGIN(family2, const char *, name2) {
+          if (node_nickname_matches(node, name2)) {
+            smartlist_add(sl, (void*)node2);
+            break;
+          }
+      } SMARTLIST_FOREACH_END(name2);
+    } SMARTLIST_FOREACH_END(name);
+  }
+
+  /* If the user declared any families locally, honor those too. */
+  if (options->NodeFamilySets) {
+    SMARTLIST_FOREACH(options->NodeFamilySets, const routerset_t *, rs, {
+      if (routerset_contains_node(rs, node)) {
+        routerset_get_all_nodes(sl, rs, NULL, 0);
+      }
+    });
+  }
+}
+
+/** 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.
+ * Don't exit enclave to excluded relays -- it wouldn't actually
+ * hurt anything, but this way there are fewer confused users.
+ */
+const node_t *
+router_find_exact_exit_enclave(const char *address, uint16_t port)
+{/*XXXX MOVE*/
+  uint32_t addr;
+  struct in_addr in;
+  tor_addr_t a;
+  const or_options_t *options = get_options();
+
+  if (!tor_inet_aton(address, &in))
+    return NULL; /* it's not an IP already */
+  addr = ntohl(in.s_addr);
+
+  tor_addr_from_ipv4h(&a, addr);
+
+  SMARTLIST_FOREACH(nodelist_get_list(), const node_t *, node, {
+    if (node_get_addr_ipv4h(node) == addr &&
+        node->is_running &&
+        compare_tor_addr_to_node_policy(&a, port, node) ==
+          ADDR_POLICY_ACCEPTED &&
+        !routerset_contains_node(options->_ExcludeExitNodesUnion, node))
+      return node;
+  });
+  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
+node_is_unreliable(const node_t *node, int need_uptime,
+                   int need_capacity, int need_guard)
+{
+  if (need_uptime && !node->is_stable)
+    return 1;
+  if (need_capacity && !node->is_fast)
+    return 1;
+  if (need_guard && !node->is_possible_guard)
+    return 1;
+  return 0;
+}
+
+/** Return 1 if all running sufficiently-stable routers we can use will reject
+ * addr:port, return 0 if any might accept it. */
+int
+router_exit_policy_all_nodes_reject(const tor_addr_t *addr, uint16_t port,
+                                    int need_uptime)
+{
+  addr_policy_result_t r;
+
+  SMARTLIST_FOREACH_BEGIN(nodelist_get_list(), const node_t *, node) {
+    if (node->is_running &&
+        !node_is_unreliable(node, need_uptime, 0, 0)) {
+
+      r = compare_tor_addr_to_node_policy(addr, port, node);
+
+      if (r != ADDR_POLICY_REJECTED && r != ADDR_POLICY_PROBABLY_REJECTED)
+        return 0; /* this one could be ok. good enough. */
+    }
+  } SMARTLIST_FOREACH_END(node);
+  return 1; /* all will reject. */
+}
+
+/** Mark the router with ID <b>digest</b> as running or non-running
+ * in our routerlist. */
+void
+router_set_status(const char *digest, int up)
+{
+  node_t *node;
+  tor_assert(digest);
+
+  SMARTLIST_FOREACH(router_get_trusted_dir_servers(),
+                    trusted_dir_server_t *, d,
+                    if (tor_memeq(d->digest, digest, DIGEST_LEN))
+                      d->is_running = up);
+
+  node = node_get_mutable_by_id(digest);
+  if (node) {
+#if 0
+    log_debug(LD_DIR,"Marking router %s as %s.",
+              node_describe(node), up ? "up" : "down");
+#endif
+    if (!up && node_is_me(node) && !net_is_disabled())
+      log_warn(LD_NET, "We just marked ourself as down. Are your external "
+               "addresses reachable?");
+    node->is_running = up;
+  }
+
+  router_dir_info_changed();
+}
+
+/** True iff, the last time we checked whether we had enough directory info
+ * to build circuits, the answer was "yes". */
+static int have_min_dir_info = 0;
+/** True iff enough has changed since the last time we checked whether we had
+ * enough directory info to build circuits that our old answer can no longer
+ * be trusted. */
+static int need_to_update_have_min_dir_info = 1;
+/** String describing what we're missing before we have enough directory
+ * info. */
+static char dir_info_status[128] = "";
+
+/** Return true iff we have enough networkstatus and router information to
+ * start building circuits.  Right now, this means "more than half the
+ * networkstatus documents, and at least 1/4 of expected routers." */
+//XXX should consider whether we have enough exiting nodes here.
+int
+router_have_minimum_dir_info(void)
+{
+  if (PREDICT_UNLIKELY(need_to_update_have_min_dir_info)) {
+    update_router_have_minimum_dir_info();
+    need_to_update_have_min_dir_info = 0;
+  }
+  return have_min_dir_info;
+}
+
+/** Called when our internal view of the directory has changed.  This can be
+ * when the authorities change, networkstatuses change, the list of routerdescs
+ * changes, or number of running routers changes.
+ */
+void
+router_dir_info_changed(void)
+{
+  need_to_update_have_min_dir_info = 1;
+  rend_hsdir_routers_changed();
+}
+
+/** Return a string describing what we're missing before we have enough
+ * directory info. */
+const char *
+get_dir_info_status_string(void)
+{
+  return dir_info_status;
+}
+
+/** Iterate over the servers listed in <b>consensus</b>, and count how many of
+ * them seem like ones we'd use, and how many of <em>those</em> we have
+ * descriptors for.  Store the former in *<b>num_usable</b> and the latter in
+ * *<b>num_present</b>.  If <b>in_set</b> is non-NULL, only consider those
+ * routers in <b>in_set</b>.  If <b>exit_only</b> is true, only consider nodes
+ * with the Exit flag.
+ */
+static void
+count_usable_descriptors(int *num_present, int *num_usable,
+                         const networkstatus_t *consensus,
+                         const or_options_t *options, time_t now,
+                         routerset_t *in_set, int exit_only)
+{
+  const int md = (consensus->flavor == FLAV_MICRODESC);
+  *num_present = 0, *num_usable=0;
+
+  SMARTLIST_FOREACH_BEGIN(consensus->routerstatus_list, routerstatus_t *, rs)
+    {
+       if (exit_only && ! rs->is_exit)
+         continue;
+       if (in_set && ! routerset_contains_routerstatus(in_set, rs, -1))
+         continue;
+       if (client_would_use_router(rs, now, options)) {
+         const char * const digest = rs->descriptor_digest;
+         int present;
+         ++*num_usable; /* the consensus says we want it. */
+         if (md)
+           present = NULL != microdesc_cache_lookup_by_digest256(NULL, digest);
+         else
+           present = NULL != router_get_by_descriptor_digest(digest);
+         if (present) {
+           /* we have the descriptor listed in the consensus. */
+           ++*num_present;
+         }
+       }
+     }
+  SMARTLIST_FOREACH_END(rs);
+
+  log_debug(LD_DIR, "%d usable, %d present (%s).", *num_usable, *num_present,
+            md ? "microdescs" : "descs");
+}
+
+/** We just fetched a new set of descriptors. Compute how far through
+ * the "loading descriptors" bootstrapping phase we are, so we can inform
+ * the controller of our progress. */
+int
+count_loading_descriptors_progress(void)
+{
+  int num_present = 0, num_usable=0;
+  time_t now = time(NULL);
+  const networkstatus_t *consensus =
+    networkstatus_get_reasonably_live_consensus(now,usable_consensus_flavor());
+  double fraction;
+
+  if (!consensus)
+    return 0; /* can't count descriptors if we have no list of them */
+
+  count_usable_descriptors(&num_present, &num_usable,
+                           consensus, get_options(), now, NULL, 0);
+
+  if (num_usable == 0)
+    return 0; /* don't div by 0 */
+  fraction = num_present / (num_usable/4.);
+  if (fraction > 1.0)
+    return 0; /* it's not the number of descriptors holding us back */
+  return BOOTSTRAP_STATUS_LOADING_DESCRIPTORS + (int)
+    (fraction*(BOOTSTRAP_STATUS_CONN_OR-1 -
+               BOOTSTRAP_STATUS_LOADING_DESCRIPTORS));
+}
+
+/** Change the value of have_min_dir_info, setting it true iff we have enough
+ * network and router information to build circuits.  Clear the value of
+ * need_to_update_have_min_dir_info. */
+static void
+update_router_have_minimum_dir_info(void)
+{
+  int num_present = 0, num_usable=0;
+  int num_exit_present = 0, num_exit_usable = 0;
+  time_t now = time(NULL);
+  int res;
+  const or_options_t *options = get_options();
+  const networkstatus_t *consensus =
+    networkstatus_get_reasonably_live_consensus(now,usable_consensus_flavor());
+  int using_md;
+
+  if (!consensus) {
+    if (!networkstatus_get_latest_consensus())
+      strlcpy(dir_info_status, "We have no usable consensus.",
+              sizeof(dir_info_status));
+    else
+      strlcpy(dir_info_status, "We have no recent usable consensus.",
+              sizeof(dir_info_status));
+    res = 0;
+    goto done;
+  }
+
+  if (should_delay_dir_fetches(get_options())) {
+    log_notice(LD_DIR, "no known bridge descriptors running yet; stalling");
+    strlcpy(dir_info_status, "No live bridge descriptors.",
+            sizeof(dir_info_status));
+    res = 0;
+    goto done;
+  }
+
+  using_md = consensus->flavor == FLAV_MICRODESC;
+
+  count_usable_descriptors(&num_present, &num_usable, consensus, options, now,
+                           NULL, 0);
+  count_usable_descriptors(&num_exit_present, &num_exit_usable,
+                           consensus, options, now, options->ExitNodes, 1);
+
+/* What fraction of desired server descriptors do we need before we will
+ * build circuits? */
+#define FRAC_USABLE_NEEDED .75
+/* What fraction of desired _exit_ server descriptors do we need before we
+ * will build circuits? */
+#define FRAC_EXIT_USABLE_NEEDED .5
+
+  if (num_present < num_usable * FRAC_USABLE_NEEDED) {
+    tor_snprintf(dir_info_status, sizeof(dir_info_status),
+                 "We have only %d/%d usable %sdescriptors.",
+                 num_present, num_usable, using_md ? "micro" : "");
+    res = 0;
+    control_event_bootstrap(BOOTSTRAP_STATUS_REQUESTING_DESCRIPTORS, 0);
+    goto done;
+  } else if (num_present < 2) {
+    tor_snprintf(dir_info_status, sizeof(dir_info_status),
+                 "Only %d %sdescriptor%s here and believed reachable!",
+                 num_present, using_md ? "micro" : "", num_present ? "" : "s");
+    res = 0;
+    goto done;
+  } else if (num_exit_present < num_exit_usable * FRAC_EXIT_USABLE_NEEDED) {
+    tor_snprintf(dir_info_status, sizeof(dir_info_status),
+                 "We have only %d/%d usable exit node descriptors.",
+                 num_exit_present, num_exit_usable);
+    res = 0;
+    control_event_bootstrap(BOOTSTRAP_STATUS_REQUESTING_DESCRIPTORS, 0);
+    goto done;
+  }
+
+  /* Check for entry nodes. */
+  if (options->EntryNodes) {
+    count_usable_descriptors(&num_present, &num_usable, consensus, options,
+                             now, options->EntryNodes, 0);
+
+    if (!num_usable || !num_present) {
+      tor_snprintf(dir_info_status, sizeof(dir_info_status),
+                   "We have only %d/%d usable entry node %sdescriptors.",
+                   num_present, num_usable, using_md?"micro":"");
+      res = 0;
+      goto done;
+    }
+  }
+
+  res = 1;
+
+ done:
+  if (res && !have_min_dir_info) {
+    log(LOG_NOTICE, LD_DIR,
+        "We now have enough directory information to build circuits.");
+    control_event_client_status(LOG_NOTICE, "ENOUGH_DIR_INFO");
+    control_event_bootstrap(BOOTSTRAP_STATUS_CONN_OR, 0);
+  }
+  if (!res && have_min_dir_info) {
+    int quiet = directory_too_idle_to_fetch_descriptors(options, now);
+    log(quiet ? LOG_INFO : LOG_NOTICE, LD_DIR,
+        "Our directory information is no longer up-to-date "
+        "enough to build circuits: %s", dir_info_status);
+
+    /* a) make us log when we next complete a circuit, so we know when Tor
+     * is back up and usable, and b) disable some activities that Tor
+     * should only do while circuits are working, like reachability tests
+     * and fetching bridge descriptors only over circuits. */
+    can_complete_circuit = 0;
+
+    control_event_client_status(LOG_NOTICE, "NOT_ENOUGH_DIR_INFO");
+  }
+  have_min_dir_info = res;
+  need_to_update_have_min_dir_info = 0;
+}
+
diff --git a/src/or/nodelist.h b/src/or/nodelist.h
index fb65fa5483..2e978f1782 100644
--- a/src/or/nodelist.h
+++ b/src/or/nodelist.h
@@ -61,11 +61,22 @@ smartlist_t *nodelist_get_list(void);
 void node_get_addr(const node_t *node, tor_addr_t *addr_out);
 #define node_get_addr_ipv4h(n) node_get_prim_addr_ipv4h((n))
 
-/* XXXX These need to move out of routerlist.c */
 void nodelist_refresh_countries(void);
 void node_set_country(node_t *node);
 void nodelist_add_node_and_family(smartlist_t *nodes, const node_t *node);
 int nodes_in_same_family(const node_t *node1, const node_t *node2);
 
+const node_t *router_find_exact_exit_enclave(const char *address,
+                                             uint16_t port);
+int node_is_unreliable(const node_t *router, int need_uptime,
+                         int need_capacity, int need_guard);
+int router_exit_policy_all_nodes_reject(const tor_addr_t *addr, uint16_t port,
+                                        int need_uptime);
+void router_set_status(const char *digest, int up);
+int router_have_minimum_dir_info(void);
+void router_dir_info_changed(void);
+const char *get_dir_info_status_string(void);
+int count_loading_descriptors_progress(void);
+
 #endif
 
diff --git a/src/or/rendclient.c b/src/or/rendclient.c
index 0b6d82bdf4..73e1c41d7b 100644
--- a/src/or/rendclient.c
+++ b/src/or/rendclient.c
@@ -23,6 +23,7 @@
 #include "rephist.h"
 #include "router.h"
 #include "routerlist.h"
+#include "routerset.h"
 
 static extend_info_t *rend_client_get_random_intro_impl(
                           const rend_cache_entry_t *rend_query,
diff --git a/src/or/rendservice.c b/src/or/rendservice.c
index 394831f857..0bfa17d108 100644
--- a/src/or/rendservice.c
+++ b/src/or/rendservice.c
@@ -26,6 +26,7 @@
 #include "replaycache.h"
 #include "routerlist.h"
 #include "routerparse.h"
+#include "routerset.h"
 
 static origin_circuit_t *find_intro_circuit(rend_intro_point_t *intro,
                                             const char *pk_digest);
diff --git a/src/or/router.c b/src/or/router.c
index 91209eef04..052ed38074 100644
--- a/src/or/router.c
+++ b/src/or/router.c
@@ -29,6 +29,7 @@
 #include "routerparse.h"
 #include "statefile.h"
 #include "transports.h"
+#include "routerset.h"
 
 /**
  * \file router.c
diff --git a/src/or/routerlist.c b/src/or/routerlist.c
index 214c086448..98357d6a38 100644
--- a/src/or/routerlist.c
+++ b/src/or/routerlist.c
@@ -34,6 +34,7 @@
 #include "router.h"
 #include "routerlist.h"
 #include "routerparse.h"
+#include "routerset.h"
 
 // #define DEBUG_ROUTERLIST
 
@@ -47,11 +48,8 @@ static const routerstatus_t *router_pick_trusteddirserver_impl(
 static void mark_all_trusteddirservers_up(void);
 static int router_nickname_matches(const routerinfo_t *router,
                                    const char *nickname);
-static int node_nickname_matches(const node_t *router,
-                                 const char *nickname);
 static void trusted_dir_server_free(trusted_dir_server_t *ds);
 static int signed_desc_digest_is_recognized(signed_descriptor_t *desc);
-static void update_router_have_minimum_dir_info(void);
 static const char *signed_descriptor_get_body_impl(
                                               const signed_descriptor_t *desc,
                                               int with_annotations);
@@ -1352,88 +1350,6 @@ router_reset_status_download_failures(void)
   mark_all_trusteddirservers_up();
 }
 
-/** Return true iff router1 and router2 have similar enough network addresses
- * that we should treat them as being in the same family */
-static INLINE int
-addrs_in_same_network_family(const tor_addr_t *a1,
-                             const tor_addr_t *a2)
-{
-  /* XXXX MOVE ? */
-  return 0 == tor_addr_compare_masked(a1, a2, 16, CMP_SEMANTIC);
-}
-
-/**
- * Add all the family of <b>node</b>, including <b>node</b> itself, to
- * the smartlist <b>sl</b>.
- *
- * This is used to make sure we don't pick siblings in a single path, or
- * pick more than one relay from a family for our entry guard list.
- * Note that a node may be added to <b>sl</b> more than once if it is
- * part of <b>node</b>'s family for more than one reason.
- */
-void
-nodelist_add_node_and_family(smartlist_t *sl, const node_t *node)
-{
-  /* XXXX MOVE */
-  const smartlist_t *all_nodes = nodelist_get_list();
-  const smartlist_t *declared_family;
-  const or_options_t *options = get_options();
-
-  tor_assert(node);
-
-  declared_family = node_get_declared_family(node);
-
-  /* Let's make sure that we have the node itself, if it's a real node. */
-  {
-    const node_t *real_node = node_get_by_id(node->identity);
-    if (real_node)
-      smartlist_add(sl, (node_t*)real_node);
-  }
-
-  /* First, add any nodes with similar network addresses. */
-  if (options->EnforceDistinctSubnets) {
-    tor_addr_t node_addr;
-    node_get_addr(node, &node_addr);
-
-    SMARTLIST_FOREACH_BEGIN(all_nodes, const node_t *, node2) {
-      tor_addr_t a;
-      node_get_addr(node2, &a);
-      if (addrs_in_same_network_family(&a, &node_addr))
-        smartlist_add(sl, (void*)node2);
-    } SMARTLIST_FOREACH_END(node2);
-  }
-
-  /* Now, add all nodes in the declared_family of this node, if they
-   * also declare this node to be in their family. */
-  if (declared_family) {
-    /* Add every r such that router declares familyness with node, and node
-     * declares familyhood with router. */
-    SMARTLIST_FOREACH_BEGIN(declared_family, const char *, name) {
-      const node_t *node2;
-      const smartlist_t *family2;
-      if (!(node2 = node_get_by_nickname(name, 0)))
-        continue;
-      if (!(family2 = node_get_declared_family(node2)))
-        continue;
-      SMARTLIST_FOREACH_BEGIN(family2, const char *, name2) {
-          if (node_nickname_matches(node, name2)) {
-            smartlist_add(sl, (void*)node2);
-            break;
-          }
-      } SMARTLIST_FOREACH_END(name2);
-    } SMARTLIST_FOREACH_END(name);
-  }
-
-  /* If the user declared any families locally, honor those too. */
-  if (options->NodeFamilySets) {
-    SMARTLIST_FOREACH(options->NodeFamilySets, const routerset_t *, rs, {
-      if (routerset_contains_node(rs, node)) {
-        routerset_get_all_nodes(sl, rs, NULL, 0);
-      }
-    });
-  }
-}
-
 /** Given a <b>router</b>, add every node_t in its family (including the
  * node itself!) to <b>sl</b>.
  *
@@ -1455,59 +1371,6 @@ routerlist_add_node_and_family(smartlist_t *sl, const routerinfo_t *router)
   nodelist_add_node_and_family(sl, node);
 }
 
-/** Return true iff <b>node</b> is named by some nickname in <b>lst</b>. */
-static INLINE int
-node_in_nickname_smartlist(const smartlist_t *lst, const node_t *node)
-{
-  /* XXXX MOVE */
-  if (!lst) return 0;
-  SMARTLIST_FOREACH(lst, const char *, name, {
-    if (node_nickname_matches(node, name))
-      return 1;
-  });
-  return 0;
-}
-
-/** Return true iff r1 and r2 are in the same family, but not the same
- * router. */
-int
-nodes_in_same_family(const node_t *node1, const node_t *node2)
-{
-  /* XXXX MOVE */
-  const or_options_t *options = get_options();
-
-  /* Are they in the same family because of their addresses? */
-  if (options->EnforceDistinctSubnets) {
-    tor_addr_t a1, a2;
-    node_get_addr(node1, &a1);
-    node_get_addr(node2, &a2);
-    if (addrs_in_same_network_family(&a1, &a2))
-      return 1;
-  }
-
-  /* Are they in the same family because the agree they are? */
-  {
-    const smartlist_t *f1, *f2;
-    f1 = node_get_declared_family(node1);
-    f2 = node_get_declared_family(node2);
-    if (f1 && f2 &&
-        node_in_nickname_smartlist(f1, node2) &&
-        node_in_nickname_smartlist(f2, node1))
-      return 1;
-  }
-
-  /* Are they in the same option because the user says they are? */
-  if (options->NodeFamilySets) {
-    SMARTLIST_FOREACH(options->NodeFamilySets, const routerset_t *, rs, {
-        if (routerset_contains_node(rs, node1) &&
-            routerset_contains_node(rs, node2))
-          return 1;
-      });
-  }
-
-  return 0;
-}
-
 /** 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.
@@ -1571,56 +1434,6 @@ routerlist_find_my_routerinfo(void)
   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.
- * Don't exit enclave to excluded relays -- it wouldn't actually
- * hurt anything, but this way there are fewer confused users.
- */
-const node_t *
-router_find_exact_exit_enclave(const char *address, uint16_t port)
-{/*XXXX MOVE*/
-  uint32_t addr;
-  struct in_addr in;
-  tor_addr_t a;
-  const or_options_t *options = get_options();
-
-  if (!tor_inet_aton(address, &in))
-    return NULL; /* it's not an IP already */
-  addr = ntohl(in.s_addr);
-
-  tor_addr_from_ipv4h(&a, addr);
-
-  SMARTLIST_FOREACH(nodelist_get_list(), const node_t *, node, {
-    if (node_get_addr_ipv4h(node) == addr &&
-        node->is_running &&
-        compare_tor_addr_to_node_policy(&a, port, node) ==
-          ADDR_POLICY_ACCEPTED &&
-        !routerset_contains_node(options->_ExcludeExitNodesUnion, node))
-      return node;
-  });
-  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
-node_is_unreliable(const node_t *node, int need_uptime,
-                   int need_capacity, int need_guard)
-{
-  if (need_uptime && !node->is_stable)
-    return 1;
-  if (need_capacity && !node->is_fast)
-    return 1;
-  if (need_guard && !node->is_possible_guard)
-    return 1;
-  return 0;
-}
-
 /** Return the smaller of the router's configured BandwidthRate
  * and its advertised capacity. */
 uint32_t
@@ -2301,7 +2114,7 @@ hex_digest_nickname_decode(const char *hexdigest,
  * combination of a router, encoded in hexadecimal, matches <b>hexdigest</b>
  * (which is optionally prefixed with a single dollar sign).  Return false if
  * <b>hexdigest</b> is malformed, or it doesn't match.  */
-static int
+int
 hex_digest_nickname_matches(const char *hexdigest, const char *identity_digest,
                             const char *nickname, int is_named)
 {
@@ -2361,129 +2174,6 @@ router_nickname_matches(const routerinfo_t *router, const char *nickname)
   return router_hex_digest_matches(router, nickname);
 }
 
-/** Return true if <b>node</b>'s nickname matches <b>nickname</b>
- * (case-insensitive), or if <b>node's</b> identity key digest
- * matches a hexadecimal value stored in <b>nickname</b>.  Return
- * false otherwise. */
-static int
-node_nickname_matches(const node_t *node, const char *nickname)
-{
-  const char *n = node_get_nickname(node);
-  if (n && nickname[0]!='$' && !strcasecmp(n, nickname))
-    return 1;
-  return hex_digest_nickname_matches(nickname,
-                                     node->identity,
-                                     n,
-                                     node_is_named(node));
-}
-
-/** Return the router in our routerlist whose (case-insensitive)
- * nickname or (case-sensitive) hexadecimal key digest is
- * <b>nickname</b>.  Return NULL if no such router is known.
- */
-const routerinfo_t *
-router_get_by_nickname(const char *nickname, int warn_if_unnamed)
-{
-#if 1
-  const node_t *node = node_get_by_nickname(nickname, warn_if_unnamed);
-  if (node)
-    return node->ri;
-  else
-    return NULL;
-#else
-  int maybedigest;
-  char digest[DIGEST_LEN];
-  routerinfo_t *best_match=NULL;
-  int n_matches = 0;
-  const char *named_digest = NULL;
-
-  tor_assert(nickname);
-  if (!routerlist)
-    return NULL;
-  if (nickname[0] == '$')
-    return router_get_by_hexdigest(nickname);
-  if (!strcasecmp(nickname, UNNAMED_ROUTER_NICKNAME))
-    return NULL;
-
-  maybedigest = (strlen(nickname) >= HEX_DIGEST_LEN) &&
-    (base16_decode(digest,DIGEST_LEN,nickname,HEX_DIGEST_LEN) == 0);
-
-  if ((named_digest = networkstatus_get_router_digest_by_nickname(nickname))) {
-    return rimap_get(routerlist->identity_map, named_digest);
-  }
-  if (networkstatus_nickname_is_unnamed(nickname))
-    return NULL;
-
-  /* If we reach this point, there's no canonical value for the nickname. */
-
-  SMARTLIST_FOREACH(routerlist->routers, routerinfo_t *, router,
-  {
-    if (!strcasecmp(router->nickname, nickname)) {
-      ++n_matches;
-      if (n_matches <= 1 || router->is_running)
-        best_match = router;
-    } else if (maybedigest &&
-               tor_memeq(digest, router->cache_info.identity_digest,
-                         DIGEST_LEN)) {
-      if (router_hex_digest_matches(router, nickname))
-        return router;
-      /* If we reach this point, we have a ID=name syntax that matches the
-       * identity but not the name. That isn't an acceptable match. */
-    }
-  });
-
-  if (best_match) {
-    if (warn_if_unnamed && n_matches > 1) {
-      smartlist_t *fps = smartlist_new();
-      int any_unwarned = 0;
-      SMARTLIST_FOREACH_BEGIN(routerlist->routers, routerinfo_t *, router) {
-          routerstatus_t *rs;
-          char fp[HEX_DIGEST_LEN+1];
-          if (strcasecmp(router->nickname, nickname))
-            continue;
-          rs = router_get_mutable_consensus_status_by_id(
-                                          router->cache_info.identity_digest);
-          if (rs && !rs->name_lookup_warned) {
-            rs->name_lookup_warned = 1;
-            any_unwarned = 1;
-          }
-          base16_encode(fp, sizeof(fp),
-                        router->cache_info.identity_digest, DIGEST_LEN);
-          smartlist_add_asprintf(fps, "\"$%s\" for the one at %s:%d",
-                       fp, router->address, router->or_port);
-      } SMARTLIST_FOREACH_END(router);
-      if (any_unwarned) {
-        char *alternatives = smartlist_join_strings(fps, "; ",0,NULL);
-        log_warn(LD_CONFIG,
-                 "There are multiple matches for the nickname \"%s\","
-                 " but none is listed as named by the directory authorities. "
-                 "Choosing one arbitrarily. If you meant one in particular, "
-                 "you should say %s.", nickname, alternatives);
-        tor_free(alternatives);
-      }
-      SMARTLIST_FOREACH(fps, char *, cp, tor_free(cp));
-      smartlist_free(fps);
-    } else if (warn_if_unnamed) {
-      routerstatus_t *rs = router_get_mutable_consensus_status_by_id(
-          best_match->cache_info.identity_digest);
-      if (rs && !rs->name_lookup_warned) {
-        char fp[HEX_DIGEST_LEN+1];
-        base16_encode(fp, sizeof(fp),
-                      best_match->cache_info.identity_digest, DIGEST_LEN);
-        log_warn(LD_CONFIG, "You specified a server \"%s\" by name, but this "
-             "name is not registered, so it could be used by any server, "
-             "not just the one you meant. "
-             "To make sure you get the same server in the future, refer to "
-             "it by key, as \"$%s\".", nickname, fp);
-        rs->name_lookup_warned = 1;
-      }
-    }
-    return best_match;
-  }
-  return NULL;
-#endif
-}
-
 /** Return true iff <b>digest</b> is the digest of the identity key of a
  * trusted directory matching at least one bit of <b>type</b>.  If <b>type</b>
  * is zero, any authority is okay. */
@@ -2530,18 +2220,6 @@ hexdigest_to_digest(const char *hexdigest, char *digest)
   return 0;
 }
 
-/** Return the router in our routerlist whose hexadecimal key digest
- * is <b>hexdigest</b>.  Return NULL if no such router is known. */
-const routerinfo_t *
-router_get_by_hexdigest(const char *hexdigest)
-{
-  if (is_legal_nickname(hexdigest))
-    return NULL;
-
-  /* It's not a legal nickname, so it must be a hexdigest or nothing. */
-  return router_get_by_nickname(hexdigest, 1);
-}
-
 /** As router_get_by_id_digest,but return a pointer that you're allowed to
  * modify */
 routerinfo_t *
@@ -3261,33 +2939,6 @@ routerlist_reset_warnings(void)
   networkstatus_reset_warnings();
 }
 
-/** Mark the router with ID <b>digest</b> as running or non-running
- * in our routerlist. */
-void
-router_set_status(const char *digest, int up)
-{
-  node_t *node;
-  tor_assert(digest);
-
-  SMARTLIST_FOREACH(trusted_dir_servers, trusted_dir_server_t *, d,
-                    if (tor_memeq(d->digest, digest, DIGEST_LEN))
-                      d->is_running = up);
-
-  node = node_get_mutable_by_id(digest);
-  if (node) {
-#if 0
-    log_debug(LD_DIR,"Marking router %s as %s.",
-              node_describe(node), up ? "up" : "down");
-#endif
-    if (!up && node_is_me(node) && !net_is_disabled())
-      log_warn(LD_NET, "We just marked ourself as down. Are your external "
-               "addresses reachable?");
-    node->is_running = up;
-  }
-
-  router_dir_info_changed();
-}
-
 /** Add <b>router</b> to the routerlist, if we don't already have it.  Replace
  * older entries (if any) with the same key.  Note: Callers should not hold
  * their pointers to <b>router</b> if this function fails; <b>router</b>
@@ -4061,27 +3712,6 @@ routerlist_retry_directory_downloads(time_t now)
   update_all_descriptor_downloads(now);
 }
 
-/** Return 1 if all running sufficiently-stable routers we can use will reject
- * addr:port, return 0 if any might accept it. */
-int
-router_exit_policy_all_nodes_reject(const tor_addr_t *addr, uint16_t port,
-                                    int need_uptime)
-{ /* XXXX MOVE */
-  addr_policy_result_t r;
-
-  SMARTLIST_FOREACH_BEGIN(nodelist_get_list(), const node_t *, node) {
-    if (node->is_running &&
-        !node_is_unreliable(node, need_uptime, 0, 0)) {
-
-      r = compare_tor_addr_to_node_policy(addr, port, node);
-
-      if (r != ADDR_POLICY_REJECTED && r != ADDR_POLICY_PROBABLY_REJECTED)
-        return 0; /* this one could be ok. good enough. */
-    }
-  } SMARTLIST_FOREACH_END(node);
-  return 1; /* all will reject. */
-}
-
 /** Return true iff <b>router</b> does not permit exit streams.
  */
 int
@@ -4335,30 +3965,6 @@ initiate_descriptor_downloads(const routerstatus_t *source,
   tor_free(resource);
 }
 
-/** Return 0 if this routerstatus is obsolete, too new, isn't
- * running, or otherwise not a descriptor that we would make any
- * use of even if we had it. Else return 1. */
-static INLINE int
-client_would_use_router(const routerstatus_t *rs, time_t now,
-                        const or_options_t *options)
-{
-  if (!rs->is_flagged_running && !options->FetchUselessDescriptors) {
-    /* If we had this router descriptor, we wouldn't even bother using it.
-     * But, if we want to have a complete list, fetch it anyway. */
-    return 0;
-  }
-  if (rs->published_on + options->TestingEstimatedDescriptorPropagationTime
-      > now) {
-    /* Most caches probably don't have this descriptor yet. */
-    return 0;
-  }
-  if (rs->published_on + OLD_ROUTER_DESC_MAX_AGE < now) {
-    /* We'd drop it immediately for being too old. */
-    return 0;
-  }
-  return 1;
-}
-
 /** Max amount of hashes to download per request.
  * Since squid does not like URLs >= 4096 bytes we limit it to 96.
  *   4096 - strlen(http://255.255.255.255/tor/server/d/.z) == 4058
@@ -4871,231 +4477,6 @@ update_extrainfo_downloads(time_t now)
   smartlist_free(wanted);
 }
 
-/** True iff, the last time we checked whether we had enough directory info
- * to build circuits, the answer was "yes". */
-static int have_min_dir_info = 0;
-/** True iff enough has changed since the last time we checked whether we had
- * enough directory info to build circuits that our old answer can no longer
- * be trusted. */
-static int need_to_update_have_min_dir_info = 1;
-/** String describing what we're missing before we have enough directory
- * info. */
-static char dir_info_status[128] = "";
-
-/** Return true iff we have enough networkstatus and router information to
- * start building circuits.  Right now, this means "more than half the
- * networkstatus documents, and at least 1/4 of expected routers." */
-//XXX should consider whether we have enough exiting nodes here.
-int
-router_have_minimum_dir_info(void)
-{
-  if (PREDICT_UNLIKELY(need_to_update_have_min_dir_info)) {
-    update_router_have_minimum_dir_info();
-    need_to_update_have_min_dir_info = 0;
-  }
-  return have_min_dir_info;
-}
-
-/** Called when our internal view of the directory has changed.  This can be
- * when the authorities change, networkstatuses change, the list of routerdescs
- * changes, or number of running routers changes.
- */
-void
-router_dir_info_changed(void)
-{
-  need_to_update_have_min_dir_info = 1;
-  rend_hsdir_routers_changed();
-}
-
-/** Return a string describing what we're missing before we have enough
- * directory info. */
-const char *
-get_dir_info_status_string(void)
-{
-  return dir_info_status;
-}
-
-/** Iterate over the servers listed in <b>consensus</b>, and count how many of
- * them seem like ones we'd use, and how many of <em>those</em> we have
- * descriptors for.  Store the former in *<b>num_usable</b> and the latter in
- * *<b>num_present</b>.  If <b>in_set</b> is non-NULL, only consider those
- * routers in <b>in_set</b>.  If <b>exit_only</b> is true, only consider nodes
- * with the Exit flag.
- */
-static void
-count_usable_descriptors(int *num_present, int *num_usable,
-                         const networkstatus_t *consensus,
-                         const or_options_t *options, time_t now,
-                         routerset_t *in_set, int exit_only)
-{
-  const int md = (consensus->flavor == FLAV_MICRODESC);
-  *num_present = 0, *num_usable=0;
-
-  SMARTLIST_FOREACH_BEGIN(consensus->routerstatus_list, routerstatus_t *, rs)
-    {
-       if (exit_only && ! rs->is_exit)
-         continue;
-       if (in_set && ! routerset_contains_routerstatus(in_set, rs, -1))
-         continue;
-       if (client_would_use_router(rs, now, options)) {
-         const char * const digest = rs->descriptor_digest;
-         int present;
-         ++*num_usable; /* the consensus says we want it. */
-         if (md)
-           present = NULL != microdesc_cache_lookup_by_digest256(NULL, digest);
-         else
-           present = NULL != router_get_by_descriptor_digest(digest);
-         if (present) {
-           /* we have the descriptor listed in the consensus. */
-           ++*num_present;
-         }
-       }
-     }
-  SMARTLIST_FOREACH_END(rs);
-
-  log_debug(LD_DIR, "%d usable, %d present (%s).", *num_usable, *num_present,
-            md ? "microdescs" : "descs");
-}
-
-/** We just fetched a new set of descriptors. Compute how far through
- * the "loading descriptors" bootstrapping phase we are, so we can inform
- * the controller of our progress. */
-int
-count_loading_descriptors_progress(void)
-{
-  int num_present = 0, num_usable=0;
-  time_t now = time(NULL);
-  const networkstatus_t *consensus =
-    networkstatus_get_reasonably_live_consensus(now,usable_consensus_flavor());
-  double fraction;
-
-  if (!consensus)
-    return 0; /* can't count descriptors if we have no list of them */
-
-  count_usable_descriptors(&num_present, &num_usable,
-                           consensus, get_options(), now, NULL, 0);
-
-  if (num_usable == 0)
-    return 0; /* don't div by 0 */
-  fraction = num_present / (num_usable/4.);
-  if (fraction > 1.0)
-    return 0; /* it's not the number of descriptors holding us back */
-  return BOOTSTRAP_STATUS_LOADING_DESCRIPTORS + (int)
-    (fraction*(BOOTSTRAP_STATUS_CONN_OR-1 -
-               BOOTSTRAP_STATUS_LOADING_DESCRIPTORS));
-}
-
-/** Change the value of have_min_dir_info, setting it true iff we have enough
- * network and router information to build circuits.  Clear the value of
- * need_to_update_have_min_dir_info. */
-static void
-update_router_have_minimum_dir_info(void)
-{
-  int num_present = 0, num_usable=0;
-  int num_exit_present = 0, num_exit_usable = 0;
-  time_t now = time(NULL);
-  int res;
-  const or_options_t *options = get_options();
-  const networkstatus_t *consensus =
-    networkstatus_get_reasonably_live_consensus(now,usable_consensus_flavor());
-  int using_md;
-
-  if (!consensus) {
-    if (!networkstatus_get_latest_consensus())
-      strlcpy(dir_info_status, "We have no usable consensus.",
-              sizeof(dir_info_status));
-    else
-      strlcpy(dir_info_status, "We have no recent usable consensus.",
-              sizeof(dir_info_status));
-    res = 0;
-    goto done;
-  }
-
-  if (should_delay_dir_fetches(get_options())) {
-    log_notice(LD_DIR, "no known bridge descriptors running yet; stalling");
-    strlcpy(dir_info_status, "No live bridge descriptors.",
-            sizeof(dir_info_status));
-    res = 0;
-    goto done;
-  }
-
-  using_md = consensus->flavor == FLAV_MICRODESC;
-
-  count_usable_descriptors(&num_present, &num_usable, consensus, options, now,
-                           NULL, 0);
-  count_usable_descriptors(&num_exit_present, &num_exit_usable,
-                           consensus, options, now, options->ExitNodes, 1);
-
-/* What fraction of desired server descriptors do we need before we will
- * build circuits? */
-#define FRAC_USABLE_NEEDED .75
-/* What fraction of desired _exit_ server descriptors do we need before we
- * will build circuits? */
-#define FRAC_EXIT_USABLE_NEEDED .5
-
-  if (num_present < num_usable * FRAC_USABLE_NEEDED) {
-    tor_snprintf(dir_info_status, sizeof(dir_info_status),
-                 "We have only %d/%d usable %sdescriptors.",
-                 num_present, num_usable, using_md ? "micro" : "");
-    res = 0;
-    control_event_bootstrap(BOOTSTRAP_STATUS_REQUESTING_DESCRIPTORS, 0);
-    goto done;
-  } else if (num_present < 2) {
-    tor_snprintf(dir_info_status, sizeof(dir_info_status),
-                 "Only %d %sdescriptor%s here and believed reachable!",
-                 num_present, using_md ? "micro" : "", num_present ? "" : "s");
-    res = 0;
-    goto done;
-  } else if (num_exit_present < num_exit_usable * FRAC_EXIT_USABLE_NEEDED) {
-    tor_snprintf(dir_info_status, sizeof(dir_info_status),
-                 "We have only %d/%d usable exit node descriptors.",
-                 num_exit_present, num_exit_usable);
-    res = 0;
-    control_event_bootstrap(BOOTSTRAP_STATUS_REQUESTING_DESCRIPTORS, 0);
-    goto done;
-  }
-
-  /* Check for entry nodes. */
-  if (options->EntryNodes) {
-    count_usable_descriptors(&num_present, &num_usable, consensus, options,
-                             now, options->EntryNodes, 0);
-
-    if (!num_usable || !num_present) {
-      tor_snprintf(dir_info_status, sizeof(dir_info_status),
-                   "We have only %d/%d usable entry node %sdescriptors.",
-                   num_present, num_usable, using_md?"micro":"");
-      res = 0;
-      goto done;
-    }
-  }
-
-  res = 1;
-
- done:
-  if (res && !have_min_dir_info) {
-    log(LOG_NOTICE, LD_DIR,
-        "We now have enough directory information to build circuits.");
-    control_event_client_status(LOG_NOTICE, "ENOUGH_DIR_INFO");
-    control_event_bootstrap(BOOTSTRAP_STATUS_CONN_OR, 0);
-  }
-  if (!res && have_min_dir_info) {
-    int quiet = directory_too_idle_to_fetch_descriptors(options, now);
-    log(quiet ? LOG_INFO : LOG_NOTICE, LD_DIR,
-        "Our directory information is no longer up-to-date "
-        "enough to build circuits: %s", dir_info_status);
-
-    /* a) make us log when we next complete a circuit, so we know when Tor
-     * is back up and usable, and b) disable some activities that Tor
-     * should only do while circuits are working, like reachability tests
-     * and fetching bridge descriptors only over circuits. */
-    can_complete_circuit = 0;
-
-    control_event_client_status(LOG_NOTICE, "NOT_ENOUGH_DIR_INFO");
-  }
-  have_min_dir_info = res;
-  need_to_update_have_min_dir_info = 0;
-}
-
 /** Reset the descriptor download failure count on all routers, so that we
  * can retry any long-failed routers immediately.
  */
@@ -5409,149 +4790,6 @@ routers_sort_by_identity(smartlist_t *routers)
   smartlist_sort(routers, _compare_routerinfo_by_id_digest);
 }
 
-/** A routerset specifies constraints on a set of possible routerinfos, based
- * on their names, identities, or addresses.  It is optimized for determining
- * whether a router is a member or not, in O(1+P) time, where P is the number
- * of address policy constraints. */
-struct routerset_t {
-  /** A list of strings for the elements of the policy.  Each string is either
-   * a nickname, a hexadecimal identity fingerprint, or an address policy.  A
-   * router belongs to the set if its nickname OR its identity OR its address
-   * matches an entry here. */
-  smartlist_t *list;
-  /** A map from lowercase nicknames of routers in the set to (void*)1 */
-  strmap_t *names;
-  /** A map from identity digests routers in the set to (void*)1 */
-  digestmap_t *digests;
-  /** An address policy for routers in the set.  For implementation reasons,
-   * a router belongs to the set if it is _rejected_ by this policy. */
-  smartlist_t *policies;
-
-  /** A human-readable description of what this routerset is for.  Used in
-   * log messages. */
-  char *description;
-
-  /** A list of the country codes in this set. */
-  smartlist_t *country_names;
-  /** Total number of countries we knew about when we built <b>countries</b>.*/
-  int n_countries;
-  /** Bit array mapping the return value of geoip_get_country() to 1 iff the
-   * country is a member of this routerset.  Note that we MUST call
-   * routerset_refresh_countries() whenever the geoip country list is
-   * reloaded. */
-  bitarray_t *countries;
-};
-
-/** Return a new empty routerset. */
-routerset_t *
-routerset_new(void)
-{
-  routerset_t *result = tor_malloc_zero(sizeof(routerset_t));
-  result->list = smartlist_new();
-  result->names = strmap_new();
-  result->digests = digestmap_new();
-  result->policies = smartlist_new();
-  result->country_names = smartlist_new();
-  return result;
-}
-
-/** If <b>c</b> is a country code in the form {cc}, return a newly allocated
- * string holding the "cc" part.  Else, return NULL. */
-static char *
-routerset_get_countryname(const char *c)
-{
-  char *country;
-
-  if (strlen(c) < 4 || c[0] !='{' || c[3] !='}')
-    return NULL;
-
-  country = tor_strndup(c+1, 2);
-  tor_strlower(country);
-  return country;
-}
-
-/** Update the routerset's <b>countries</b> bitarray_t. Called whenever
- * the GeoIP database is reloaded.
- */
-void
-routerset_refresh_countries(routerset_t *target)
-{
-  int cc;
-  bitarray_free(target->countries);
-
-  if (!geoip_is_loaded()) {
-    target->countries = NULL;
-    target->n_countries = 0;
-    return;
-  }
-  target->n_countries = geoip_get_n_countries();
-  target->countries = bitarray_init_zero(target->n_countries);
-  SMARTLIST_FOREACH_BEGIN(target->country_names, const char *, country) {
-    cc = geoip_get_country(country);
-    if (cc >= 0) {
-      tor_assert(cc < target->n_countries);
-      bitarray_set(target->countries, cc);
-    } else {
-      log(LOG_WARN, LD_CONFIG, "Country code '%s' is not recognized.",
-          country);
-    }
-  } SMARTLIST_FOREACH_END(country);
-}
-
-/** Parse the string <b>s</b> to create a set of routerset entries, and add
- * them to <b>target</b>.  In log messages, refer to the string as
- * <b>description</b>.  Return 0 on success, -1 on failure.
- *
- * Three kinds of elements are allowed in routersets: nicknames, IP address
- * patterns, and fingerprints.  They may be surrounded by optional space, and
- * must be separated by commas.
- */
-int
-routerset_parse(routerset_t *target, const char *s, const char *description)
-{
-  int r = 0;
-  int added_countries = 0;
-  char *countryname;
-  smartlist_t *list = smartlist_new();
-  smartlist_split_string(list, s, ",",
-                         SPLIT_SKIP_SPACE | SPLIT_IGNORE_BLANK, 0);
-  SMARTLIST_FOREACH_BEGIN(list, char *, nick) {
-      addr_policy_t *p;
-      if (is_legal_hexdigest(nick)) {
-        char d[DIGEST_LEN];
-        if (*nick == '$')
-          ++nick;
-        log_debug(LD_CONFIG, "Adding identity %s to %s", nick, description);
-        base16_decode(d, sizeof(d), nick, HEX_DIGEST_LEN);
-        digestmap_set(target->digests, d, (void*)1);
-      } else if (is_legal_nickname(nick)) {
-        log_debug(LD_CONFIG, "Adding nickname %s to %s", nick, description);
-        strmap_set_lc(target->names, nick, (void*)1);
-      } else if ((countryname = routerset_get_countryname(nick)) != NULL) {
-        log_debug(LD_CONFIG, "Adding country %s to %s", nick,
-                  description);
-        smartlist_add(target->country_names, countryname);
-        added_countries = 1;
-      } else if ((strchr(nick,'.') || strchr(nick, '*')) &&
-                 (p = router_parse_addr_policy_item_from_string(
-                                     nick, ADDR_POLICY_REJECT))) {
-        log_debug(LD_CONFIG, "Adding address %s to %s", nick, description);
-        smartlist_add(target->policies, p);
-      } else {
-        log_warn(LD_CONFIG, "Entry '%s' in %s is misformed.", nick,
-                 description);
-        r = -1;
-        tor_free(nick);
-        SMARTLIST_DEL_CURRENT(list, nick);
-      }
-  } SMARTLIST_FOREACH_END(nick);
-  smartlist_add_all(target->list, list);
-  smartlist_free(list);
-  if (added_countries)
-    routerset_refresh_countries(target);
-  return r;
-}
-
 /** Called when we change a node set, or when we reload the geoip list:
  * recompute all country info in all configuration node sets and in the
  * routerlist. */
@@ -5574,297 +4812,6 @@ refresh_all_country_info(void)
   nodelist_refresh_countries();
 }
 
-/** Add all members of the set <b>source</b> to <b>target</b>. */
-void
-routerset_union(routerset_t *target, const routerset_t *source)
-{
-  char *s;
-  tor_assert(target);
-  if (!source || !source->list)
-    return;
-  s = routerset_to_string(source);
-  routerset_parse(target, s, "other routerset");
-  tor_free(s);
-}
-
-/** Return true iff <b>set</b> lists only nicknames and digests, and includes
- * no IP ranges or countries. */
-int
-routerset_is_list(const routerset_t *set)
-{
-  return smartlist_len(set->country_names) == 0 &&
-    smartlist_len(set->policies) == 0;
-}
-
-/** Return true iff we need a GeoIP IP-to-country database to make sense of
- * <b>set</b>. */
-int
-routerset_needs_geoip(const routerset_t *set)
-{
-  return set && smartlist_len(set->country_names);
-}
-
-/** Return true iff there are no entries in <b>set</b>. */
-int
-routerset_is_empty(const routerset_t *set)
-{
-  return !set || smartlist_len(set->list) == 0;
-}
-
-/** Helper.  Return true iff <b>set</b> contains a router based on the other
- * provided fields.  Return higher values for more specific subentries: a
- * single router is more specific than an address range of routers, which is
- * more specific in turn than a country code.
- *
- * (If country is -1, then we take the country
- * from addr.) */
-static int
-routerset_contains(const routerset_t *set, const tor_addr_t *addr,
-                   uint16_t orport,
-                   const char *nickname, const char *id_digest,
-                   country_t country)
-{
-  if (!set || !set->list)
-    return 0;
-  if (nickname && strmap_get_lc(set->names, nickname))
-    return 4;
-  if (id_digest && digestmap_get(set->digests, id_digest))
-    return 4;
-  if (addr && compare_tor_addr_to_addr_policy(addr, orport, set->policies)
-      == ADDR_POLICY_REJECTED)
-    return 3;
-  if (set->countries) {
-    if (country < 0 && addr)
-      country = geoip_get_country_by_ip(tor_addr_to_ipv4h(addr));
-
-    if (country >= 0 && country < set->n_countries &&
-        bitarray_is_set(set->countries, country))
-      return 2;
-  }
-  return 0;
-}
-
-/** Return true iff we can tell that <b>ei</b> is a member of <b>set</b>. */
-int
-routerset_contains_extendinfo(const routerset_t *set, const extend_info_t *ei)
-{
-  return routerset_contains(set,
-                            &ei->addr,
-                            ei->port,
-                            ei->nickname,
-                            ei->identity_digest,
-                            -1 /*country*/);
-}
-
-/** Return true iff <b>ri</b> is in <b>set</b>.  If country is <b>-1</b>, we
- * look up the country. */
-int
-routerset_contains_router(const routerset_t *set, const routerinfo_t *ri,
-                          country_t country)
-{
-  tor_addr_t addr;
-  tor_addr_from_ipv4h(&addr, ri->addr);
-  return routerset_contains(set,
-                            &addr,
-                            ri->or_port,
-                            ri->nickname,
-                            ri->cache_info.identity_digest,
-                            country);
-}
-
-/** Return true iff <b>rs</b> is in <b>set</b>.  If country is <b>-1</b>, we
- * look up the country. */
-int
-routerset_contains_routerstatus(const routerset_t *set,
-                                const routerstatus_t *rs,
-                                country_t country)
-{
-  tor_addr_t addr;
-  tor_addr_from_ipv4h(&addr, rs->addr);
-  return routerset_contains(set,
-                            &addr,
-                            rs->or_port,
-                            rs->nickname,
-                            rs->identity_digest,
-                            country);
-}
-
-/** Return true iff <b>node</b> is in <b>set</b>. */
-int
-routerset_contains_node(const routerset_t *set, const node_t *node)
-{
-  if (node->rs)
-    return routerset_contains_routerstatus(set, node->rs, node->country);
-  else if (node->ri)
-    return routerset_contains_router(set, node->ri, node->country);
-  else
-    return 0;
-}
-
-/** Add every known node_t that is a member of <b>routerset</b> to
- * <b>out</b>, but never add any that are part of <b>excludeset</b>.
- * If <b>running_only</b>, only add the running ones. */
-void
-routerset_get_all_nodes(smartlist_t *out, const routerset_t *routerset,
-                        const routerset_t *excludeset, int running_only)
-{ /* XXXX MOVE */
-  tor_assert(out);
-  if (!routerset || !routerset->list)
-    return;
-
-  if (routerset_is_list(routerset)) {
-    /* No routers are specified by type; all are given by name or digest.
-     * we can do a lookup in O(len(routerset)). */
-    SMARTLIST_FOREACH(routerset->list, const char *, name, {
-        const node_t *node = node_get_by_nickname(name, 1);
-        if (node) {
-          if (!running_only || node->is_running)
-            if (!routerset_contains_node(excludeset, node))
-              smartlist_add(out, (void*)node);
-        }
-    });
-  } else {
-    /* We need to iterate over the routerlist to get all the ones of the
-     * right kind. */
-    smartlist_t *nodes = nodelist_get_list();
-    SMARTLIST_FOREACH(nodes, const node_t *, node, {
-        if (running_only && !node->is_running)
-          continue;
-        if (routerset_contains_node(routerset, node) &&
-            !routerset_contains_node(excludeset, node))
-          smartlist_add(out, (void*)node);
-    });
-  }
-}
-
-#if 0
-/** Add to <b>target</b> every node_t from <b>source</b> except:
- *
- * 1) Don't add it if <b>include</b> is non-empty and the relay isn't in
- * <b>include</b>; and
- * 2) Don't add it if <b>exclude</b> is non-empty and the relay is
- * excluded in a more specific fashion by <b>exclude</b>.
- * 3) If <b>running_only</b>, don't add non-running routers.
- */
-void
-routersets_get_node_disjunction(smartlist_t *target,
-                           const smartlist_t *source,
-                           const routerset_t *include,
-                           const routerset_t *exclude, int running_only)
-{
-  SMARTLIST_FOREACH(source, const node_t *, node, {
-    int include_result;
-    if (running_only && !node->is_running)
-      continue;
-    if (!routerset_is_empty(include))
-      include_result = routerset_contains_node(include, node);
-    else
-      include_result = 1;
-
-    if (include_result) {
-      int exclude_result = routerset_contains_node(exclude, node);
-      if (include_result >= exclude_result)
-        smartlist_add(target, (void*)node);
-    }
-  });
-}
-#endif
-
-/** Remove every node_t from <b>lst</b> that is in <b>routerset</b>. */
-void
-routerset_subtract_nodes(smartlist_t *lst, const routerset_t *routerset)
-{ /*XXXX MOVE ? */
-  tor_assert(lst);
-  if (!routerset)
-    return;
-  SMARTLIST_FOREACH(lst, const node_t *, node, {
-      if (routerset_contains_node(routerset, node)) {
-        //log_debug(LD_DIR, "Subtracting %s",r->nickname);
-        SMARTLIST_DEL_CURRENT(lst, node);
-      }
-    });
-}
-
-/** Return a new string that when parsed by routerset_parse_string() will
- * yield <b>set</b>. */
-char *
-routerset_to_string(const routerset_t *set)
-{
-  if (!set || !set->list)
-    return tor_strdup("");
-  return smartlist_join_strings(set->list, ",", 0, NULL);
-}
-
-/** Helper: return true iff old and new are both NULL, or both non-NULL
- * equal routersets. */
-int
-routerset_equal(const routerset_t *old, const routerset_t *new)
-{
-  if (routerset_is_empty(old) && routerset_is_empty(new)) {
-    /* Two empty sets are equal */
-    return 1;
-  } else if (routerset_is_empty(old) || routerset_is_empty(new)) {
-    /* An empty set is equal to nothing else. */
-    return 0;
-  }
-  tor_assert(old != NULL);
-  tor_assert(new != NULL);
-
-  if (smartlist_len(old->list) != smartlist_len(new->list))
-    return 0;
-
-  SMARTLIST_FOREACH(old->list, const char *, cp1, {
-    const char *cp2 = smartlist_get(new->list, cp1_sl_idx);
-    if (strcmp(cp1, cp2))
-      return 0;
-  });
-
-  return 1;
-}
-
-/** Free all storage held in <b>routerset</b>. */
-void
-routerset_free(routerset_t *routerset)
-{
-  if (!routerset)
-    return;
-
-  SMARTLIST_FOREACH(routerset->list, char *, cp, tor_free(cp));
-  smartlist_free(routerset->list);
-  SMARTLIST_FOREACH(routerset->policies, addr_policy_t *, p,
-                    addr_policy_free(p));
-  smartlist_free(routerset->policies);
-  SMARTLIST_FOREACH(routerset->country_names, char *, cp, tor_free(cp));
-  smartlist_free(routerset->country_names);
-
-  strmap_free(routerset->names, NULL);
-  digestmap_free(routerset->digests, NULL);
-  bitarray_free(routerset->countries);
-  tor_free(routerset);
-}
-
-/** Refresh the country code of <b>ri</b>.  This function MUST be called on
- * each router when the GeoIP database is reloaded, and on all new routers. */
-void
-node_set_country(node_t *node)
-{
-  if (node->rs)
-    node->country = geoip_get_country_by_ip(node->rs->addr);
-  else if (node->ri)
-    node->country = geoip_get_country_by_ip(node->ri->addr);
-  else
-    node->country = -1;
-}
-
-/** Set the country code of all routers in the routerlist. */
-void
-nodelist_refresh_countries(void) /* MOVE */
-{
-  smartlist_t *nodes = nodelist_get_list();
-  SMARTLIST_FOREACH(nodes, node_t *, node,
-                    node_set_country(node));
-}
-
 /** Determine the routers that are responsible for <b>id</b> (binary) and
  * add pointers to those routers' routerstatus_t to <b>responsible_dirs</b>.
  * Return -1 if we're returning an empty smartlist, else return 0.
diff --git a/src/or/routerlist.h b/src/or/routerlist.h
index ab58b9ee5a..58143010b3 100644
--- a/src/or/routerlist.h
+++ b/src/or/routerlist.h
@@ -39,10 +39,6 @@ void router_reset_status_download_failures(void);
 int routers_have_same_or_addrs(const routerinfo_t *r1, const routerinfo_t *r2);
 int router_nickname_is_in_list(const routerinfo_t *router, const char *list);
 const routerinfo_t *routerlist_find_my_routerinfo(void);
-const node_t *router_find_exact_exit_enclave(const char *address,
-                                             uint16_t port);
-int node_is_unreliable(const node_t *router, int need_uptime,
-                         int need_capacity, int need_guard);
 uint32_t router_get_advertised_bandwidth(const routerinfo_t *router);
 uint32_t router_get_advertised_bandwidth_capped(const routerinfo_t *router);
 
@@ -53,8 +49,6 @@ const node_t *router_choose_random_node(smartlist_t *excludedsmartlist,
                                         struct routerset_t *excludedset,
                                         router_crn_flags_t flags);
 
-const routerinfo_t *router_get_by_nickname(const char *nickname,
-                                     int warn_if_unnamed);
 int router_is_named(const routerinfo_t *router);
 int router_digest_is_trusted_dir_type(const char *digest,
                                       dirinfo_type_t type);
@@ -63,7 +57,6 @@ int router_digest_is_trusted_dir_type(const char *digest,
 
 int router_addr_is_trusted_dir(uint32_t addr);
 int hexdigest_to_digest(const char *hexdigest, char *digest);
-const routerinfo_t *router_get_by_hexdigest(const char *hexdigest);
 const routerinfo_t *router_get_by_id_digest(const char *digest);
 routerinfo_t *router_get_mutable_by_digest(const char *digest);
 signed_descriptor_t *router_get_by_descriptor_digest(const char *digest);
@@ -80,7 +73,6 @@ void routerlist_remove(routerlist_t *rl, routerinfo_t *ri, int make_old,
                        time_t now);
 void routerlist_free_all(void);
 void routerlist_reset_warnings(void);
-void router_set_status(const char *digest, int up);
 
 static int WRA_WAS_ADDED(was_router_added_t s);
 static int WRA_WAS_OUTDATED(was_router_added_t s);
@@ -133,8 +125,6 @@ void router_load_extrainfo_from_string(const char *s, const char *eos,
                                        int descriptor_digests);
 
 void routerlist_retry_directory_downloads(time_t now);
-int router_exit_policy_all_nodes_reject(const tor_addr_t *addr, uint16_t port,
-                                        int need_uptime);
 
 int router_exit_policy_rejects_all(const routerinfo_t *router);
 trusted_dir_server_t *add_trusted_dir_server(const char *nickname,
@@ -150,10 +140,6 @@ void update_consensus_router_descriptor_downloads(time_t now, int is_vote,
 void update_router_descriptor_downloads(time_t now);
 void update_all_descriptor_downloads(time_t now);
 void update_extrainfo_downloads(time_t now);
-int router_have_minimum_dir_info(void);
-void router_dir_info_changed(void);
-const char *get_dir_info_status_string(void);
-int count_loading_descriptors_progress(void);
 void router_reset_descriptor_download_failures(void);
 int router_differences_are_cosmetic(const routerinfo_t *r1,
                                     const routerinfo_t *r2);
@@ -166,38 +152,6 @@ void routerlist_assert_ok(const routerlist_t *rl);
 const char *esc_router_info(const routerinfo_t *router);
 void routers_sort_by_identity(smartlist_t *routers);
 
-routerset_t *routerset_new(void);
-void routerset_refresh_countries(routerset_t *rs);
-int routerset_parse(routerset_t *target, const char *s,
-                    const char *description);
-void routerset_union(routerset_t *target, const routerset_t *source);
-int routerset_is_list(const routerset_t *set);
-int routerset_needs_geoip(const routerset_t *set);
-int routerset_is_empty(const routerset_t *set);
-int routerset_contains_router(const routerset_t *set, const routerinfo_t *ri,
-                              country_t country);
-int routerset_contains_routerstatus(const routerset_t *set,
-                                    const routerstatus_t *rs,
-                                    country_t country);
-int routerset_contains_extendinfo(const routerset_t *set,
-                                  const extend_info_t *ei);
-
-int routerset_contains_node(const routerset_t *set, const node_t *node);
-void routerset_get_all_nodes(smartlist_t *out, const routerset_t *routerset,
-                             const routerset_t *excludeset,
-                             int running_only);
-#if 0
-void routersets_get_node_disjunction(smartlist_t *target,
-                                const smartlist_t *source,
-                                const routerset_t *include,
-                                const routerset_t *exclude, int running_only);
-#endif
-void routerset_subtract_nodes(smartlist_t *out,
-                                const routerset_t *routerset);
-
-char *routerset_to_string(const routerset_t *routerset);
-int routerset_equal(const routerset_t *old, const routerset_t *new);
-void routerset_free(routerset_t *routerset);
 void refresh_all_country_info(void);
 
 int hid_serv_get_responsible_directories(smartlist_t *responsible_dirs,
@@ -215,6 +169,9 @@ int hex_digest_nickname_decode(const char *hexdigest,
                                char *digest_out,
                                char *nickname_qualifier_out,
                                char *nickname_out);
+int hex_digest_nickname_matches(const char *hexdigest,
+                                const char *identity_digest,
+                                const char *nickname, int is_named);
 
 #ifdef ROUTERLIST_PRIVATE
 /** Helper type for choosing routers by bandwidth: contains a union of
diff --git a/src/or/routerset.c b/src/or/routerset.c
new file mode 100644
index 0000000000..263cf79d70
--- /dev/null
+++ b/src/or/routerset.c
@@ -0,0 +1,426 @@
+/* Copyright (c) 2001 Matej Pfajfar.
+ * Copyright (c) 2001-2004, Roger Dingledine.
+ * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
+ * Copyright (c) 2007-2012, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+#include "or.h"
+#include "geoip.h"
+#include "nodelist.h"
+#include "policies.h"
+#include "router.h"
+#include "routerparse.h"
+#include "routerset.h"
+
+/** A routerset specifies constraints on a set of possible routerinfos, based
+ * on their names, identities, or addresses.  It is optimized for determining
+ * whether a router is a member or not, in O(1+P) time, where P is the number
+ * of address policy constraints. */
+struct routerset_t {
+  /** A list of strings for the elements of the policy.  Each string is either
+   * a nickname, a hexadecimal identity fingerprint, or an address policy.  A
+   * router belongs to the set if its nickname OR its identity OR its address
+   * matches an entry here. */
+  smartlist_t *list;
+  /** A map from lowercase nicknames of routers in the set to (void*)1 */
+  strmap_t *names;
+  /** A map from identity digests routers in the set to (void*)1 */
+  digestmap_t *digests;
+  /** An address policy for routers in the set.  For implementation reasons,
+   * a router belongs to the set if it is _rejected_ by this policy. */
+  smartlist_t *policies;
+
+  /** A human-readable description of what this routerset is for.  Used in
+   * log messages. */
+  char *description;
+
+  /** A list of the country codes in this set. */
+  smartlist_t *country_names;
+  /** Total number of countries we knew about when we built <b>countries</b>.*/
+  int n_countries;
+  /** Bit array mapping the return value of geoip_get_country() to 1 iff the
+   * country is a member of this routerset.  Note that we MUST call
+   * routerset_refresh_countries() whenever the geoip country list is
+   * reloaded. */
+  bitarray_t *countries;
+};
+
+/** Return a new empty routerset. */
+routerset_t *
+routerset_new(void)
+{
+  routerset_t *result = tor_malloc_zero(sizeof(routerset_t));
+  result->list = smartlist_new();
+  result->names = strmap_new();
+  result->digests = digestmap_new();
+  result->policies = smartlist_new();
+  result->country_names = smartlist_new();
+  return result;
+}
+
+/** If <b>c</b> is a country code in the form {cc}, return a newly allocated
+ * string holding the "cc" part.  Else, return NULL. */
+static char *
+routerset_get_countryname(const char *c)
+{
+  char *country;
+
+  if (strlen(c) < 4 || c[0] !='{' || c[3] !='}')
+    return NULL;
+
+  country = tor_strndup(c+1, 2);
+  tor_strlower(country);
+  return country;
+}
+
+/** Update the routerset's <b>countries</b> bitarray_t. Called whenever
+ * the GeoIP database is reloaded.
+ */
+void
+routerset_refresh_countries(routerset_t *target)
+{
+  int cc;
+  bitarray_free(target->countries);
+
+  if (!geoip_is_loaded()) {
+    target->countries = NULL;
+    target->n_countries = 0;
+    return;
+  }
+  target->n_countries = geoip_get_n_countries();
+  target->countries = bitarray_init_zero(target->n_countries);
+  SMARTLIST_FOREACH_BEGIN(target->country_names, const char *, country) {
+    cc = geoip_get_country(country);
+    if (cc >= 0) {
+      tor_assert(cc < target->n_countries);
+      bitarray_set(target->countries, cc);
+    } else {
+      log(LOG_WARN, LD_CONFIG, "Country code '%s' is not recognized.",
+          country);
+    }
+  } SMARTLIST_FOREACH_END(country);
+}
+
+/** Parse the string <b>s</b> to create a set of routerset entries, and add
+ * them to <b>target</b>.  In log messages, refer to the string as
+ * <b>description</b>.  Return 0 on success, -1 on failure.
+ *
+ * Three kinds of elements are allowed in routersets: nicknames, IP address
+ * patterns, and fingerprints.  They may be surrounded by optional space, and
+ * must be separated by commas.
+ */
+int
+routerset_parse(routerset_t *target, const char *s, const char *description)
+{
+  int r = 0;
+  int added_countries = 0;
+  char *countryname;
+  smartlist_t *list = smartlist_new();
+  smartlist_split_string(list, s, ",",
+                         SPLIT_SKIP_SPACE | SPLIT_IGNORE_BLANK, 0);
+  SMARTLIST_FOREACH_BEGIN(list, char *, nick) {
+      addr_policy_t *p;
+      if (is_legal_hexdigest(nick)) {
+        char d[DIGEST_LEN];
+        if (*nick == '$')
+          ++nick;
+        log_debug(LD_CONFIG, "Adding identity %s to %s", nick, description);
+        base16_decode(d, sizeof(d), nick, HEX_DIGEST_LEN);
+        digestmap_set(target->digests, d, (void*)1);
+      } else if (is_legal_nickname(nick)) {
+        log_debug(LD_CONFIG, "Adding nickname %s to %s", nick, description);
+        strmap_set_lc(target->names, nick, (void*)1);
+      } else if ((countryname = routerset_get_countryname(nick)) != NULL) {
+        log_debug(LD_CONFIG, "Adding country %s to %s", nick,
+                  description);
+        smartlist_add(target->country_names, countryname);
+        added_countries = 1;
+      } else if ((strchr(nick,'.') || strchr(nick, '*')) &&
+                 (p = router_parse_addr_policy_item_from_string(
+                                     nick, ADDR_POLICY_REJECT))) {
+        log_debug(LD_CONFIG, "Adding address %s to %s", nick, description);
+        smartlist_add(target->policies, p);
+      } else {
+        log_warn(LD_CONFIG, "Entry '%s' in %s is misformed.", nick,
+                 description);
+        r = -1;
+        tor_free(nick);
+        SMARTLIST_DEL_CURRENT(list, nick);
+      }
+  } SMARTLIST_FOREACH_END(nick);
+  smartlist_add_all(target->list, list);
+  smartlist_free(list);
+  if (added_countries)
+    routerset_refresh_countries(target);
+  return r;
+}
+
+/** Add all members of the set <b>source</b> to <b>target</b>. */
+void
+routerset_union(routerset_t *target, const routerset_t *source)
+{
+  char *s;
+  tor_assert(target);
+  if (!source || !source->list)
+    return;
+  s = routerset_to_string(source);
+  routerset_parse(target, s, "other routerset");
+  tor_free(s);
+}
+
+/** Return true iff <b>set</b> lists only nicknames and digests, and includes
+ * no IP ranges or countries. */
+int
+routerset_is_list(const routerset_t *set)
+{
+  return smartlist_len(set->country_names) == 0 &&
+    smartlist_len(set->policies) == 0;
+}
+
+/** Return true iff we need a GeoIP IP-to-country database to make sense of
+ * <b>set</b>. */
+int
+routerset_needs_geoip(const routerset_t *set)
+{
+  return set && smartlist_len(set->country_names);
+}
+
+/** Return true iff there are no entries in <b>set</b>. */
+int
+routerset_is_empty(const routerset_t *set)
+{
+  return !set || smartlist_len(set->list) == 0;
+}
+
+/** Helper.  Return true iff <b>set</b> contains a router based on the other
+ * provided fields.  Return higher values for more specific subentries: a
+ * single router is more specific than an address range of routers, which is
+ * more specific in turn than a country code.
+ *
+ * (If country is -1, then we take the country
+ * from addr.) */
+static int
+routerset_contains(const routerset_t *set, const tor_addr_t *addr,
+                   uint16_t orport,
+                   const char *nickname, const char *id_digest,
+                   country_t country)
+{
+  if (!set || !set->list)
+    return 0;
+  if (nickname && strmap_get_lc(set->names, nickname))
+    return 4;
+  if (id_digest && digestmap_get(set->digests, id_digest))
+    return 4;
+  if (addr && compare_tor_addr_to_addr_policy(addr, orport, set->policies)
+      == ADDR_POLICY_REJECTED)
+    return 3;
+  if (set->countries) {
+    if (country < 0 && addr)
+      country = geoip_get_country_by_ip(tor_addr_to_ipv4h(addr));
+
+    if (country >= 0 && country < set->n_countries &&
+        bitarray_is_set(set->countries, country))
+      return 2;
+  }
+  return 0;
+}
+
+/** Return true iff we can tell that <b>ei</b> is a member of <b>set</b>. */
+int
+routerset_contains_extendinfo(const routerset_t *set, const extend_info_t *ei)
+{
+  return routerset_contains(set,
+                            &ei->addr,
+                            ei->port,
+                            ei->nickname,
+                            ei->identity_digest,
+                            -1 /*country*/);
+}
+
+/** Return true iff <b>ri</b> is in <b>set</b>.  If country is <b>-1</b>, we
+ * look up the country. */
+int
+routerset_contains_router(const routerset_t *set, const routerinfo_t *ri,
+                          country_t country)
+{
+  tor_addr_t addr;
+  tor_addr_from_ipv4h(&addr, ri->addr);
+  return routerset_contains(set,
+                            &addr,
+                            ri->or_port,
+                            ri->nickname,
+                            ri->cache_info.identity_digest,
+                            country);
+}
+
+/** Return true iff <b>rs</b> is in <b>set</b>.  If country is <b>-1</b>, we
+ * look up the country. */
+int
+routerset_contains_routerstatus(const routerset_t *set,
+                                const routerstatus_t *rs,
+                                country_t country)
+{
+  tor_addr_t addr;
+  tor_addr_from_ipv4h(&addr, rs->addr);
+  return routerset_contains(set,
+                            &addr,
+                            rs->or_port,
+                            rs->nickname,
+                            rs->identity_digest,
+                            country);
+}
+
+/** Return true iff <b>node</b> is in <b>set</b>. */
+int
+routerset_contains_node(const routerset_t *set, const node_t *node)
+{
+  if (node->rs)
+    return routerset_contains_routerstatus(set, node->rs, node->country);
+  else if (node->ri)
+    return routerset_contains_router(set, node->ri, node->country);
+  else
+    return 0;
+}
+
+/** Add every known node_t that is a member of <b>routerset</b> to
+ * <b>out</b>, but never add any that are part of <b>excludeset</b>.
+ * If <b>running_only</b>, only add the running ones. */
+void
+routerset_get_all_nodes(smartlist_t *out, const routerset_t *routerset,
+                        const routerset_t *excludeset, int running_only)
+{
+  tor_assert(out);
+  if (!routerset || !routerset->list)
+    return;
+
+  if (routerset_is_list(routerset)) {
+    /* No routers are specified by type; all are given by name or digest.
+     * we can do a lookup in O(len(routerset)). */
+    SMARTLIST_FOREACH(routerset->list, const char *, name, {
+        const node_t *node = node_get_by_nickname(name, 1);
+        if (node) {
+          if (!running_only || node->is_running)
+            if (!routerset_contains_node(excludeset, node))
+              smartlist_add(out, (void*)node);
+        }
+    });
+  } else {
+    /* We need to iterate over the routerlist to get all the ones of the
+     * right kind. */
+    smartlist_t *nodes = nodelist_get_list();
+    SMARTLIST_FOREACH(nodes, const node_t *, node, {
+        if (running_only && !node->is_running)
+          continue;
+        if (routerset_contains_node(routerset, node) &&
+            !routerset_contains_node(excludeset, node))
+          smartlist_add(out, (void*)node);
+    });
+  }
+}
+
+#if 0
+/** Add to <b>target</b> every node_t from <b>source</b> except:
+ *
+ * 1) Don't add it if <b>include</b> is non-empty and the relay isn't in
+ * <b>include</b>; and
+ * 2) Don't add it if <b>exclude</b> is non-empty and the relay is
+ * excluded in a more specific fashion by <b>exclude</b>.
+ * 3) If <b>running_only</b>, don't add non-running routers.
+ */
+void
+routersets_get_node_disjunction(smartlist_t *target,
+                           const smartlist_t *source,
+                           const routerset_t *include,
+                           const routerset_t *exclude, int running_only)
+{
+  SMARTLIST_FOREACH(source, const node_t *, node, {
+    int include_result;
+    if (running_only && !node->is_running)
+      continue;
+    if (!routerset_is_empty(include))
+      include_result = routerset_contains_node(include, node);
+    else
+      include_result = 1;
+
+    if (include_result) {
+      int exclude_result = routerset_contains_node(exclude, node);
+      if (include_result >= exclude_result)
+        smartlist_add(target, (void*)node);
+    }
+  });
+}
+#endif
+
+/** Remove every node_t from <b>lst</b> that is in <b>routerset</b>. */
+void
+routerset_subtract_nodes(smartlist_t *lst, const routerset_t *routerset)
+{
+  tor_assert(lst);
+  if (!routerset)
+    return;
+  SMARTLIST_FOREACH(lst, const node_t *, node, {
+      if (routerset_contains_node(routerset, node)) {
+        //log_debug(LD_DIR, "Subtracting %s",r->nickname);
+        SMARTLIST_DEL_CURRENT(lst, node);
+      }
+    });
+}
+
+/** Return a new string that when parsed by routerset_parse_string() will
+ * yield <b>set</b>. */
+char *
+routerset_to_string(const routerset_t *set)
+{
+  if (!set || !set->list)
+    return tor_strdup("");
+  return smartlist_join_strings(set->list, ",", 0, NULL);
+}
+
+/** Helper: return true iff old and new are both NULL, or both non-NULL
+ * equal routersets. */
+int
+routerset_equal(const routerset_t *old, const routerset_t *new)
+{
+  if (routerset_is_empty(old) && routerset_is_empty(new)) {
+    /* Two empty sets are equal */
+    return 1;
+  } else if (routerset_is_empty(old) || routerset_is_empty(new)) {
+    /* An empty set is equal to nothing else. */
+    return 0;
+  }
+  tor_assert(old != NULL);
+  tor_assert(new != NULL);
+
+  if (smartlist_len(old->list) != smartlist_len(new->list))
+    return 0;
+
+  SMARTLIST_FOREACH(old->list, const char *, cp1, {
+    const char *cp2 = smartlist_get(new->list, cp1_sl_idx);
+    if (strcmp(cp1, cp2))
+      return 0;
+  });
+
+  return 1;
+}
+
+/** Free all storage held in <b>routerset</b>. */
+void
+routerset_free(routerset_t *routerset)
+{
+  if (!routerset)
+    return;
+
+  SMARTLIST_FOREACH(routerset->list, char *, cp, tor_free(cp));
+  smartlist_free(routerset->list);
+  SMARTLIST_FOREACH(routerset->policies, addr_policy_t *, p,
+                    addr_policy_free(p));
+  smartlist_free(routerset->policies);
+  SMARTLIST_FOREACH(routerset->country_names, char *, cp, tor_free(cp));
+  smartlist_free(routerset->country_names);
+
+  strmap_free(routerset->names, NULL);
+  digestmap_free(routerset->digests, NULL);
+  bitarray_free(routerset->countries);
+  tor_free(routerset);
+}
+
diff --git a/src/or/routerset.h b/src/or/routerset.h
new file mode 100644
index 0000000000..ad0832e4df
--- /dev/null
+++ b/src/or/routerset.h
@@ -0,0 +1,48 @@
+/* Copyright (c) 2001-2004, Roger Dingledine.
+ * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
+ * Copyright (c) 2007-2012, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+/**
+ * \file routerlist.h
+ * \brief Header file for routerset.c
+ **/
+
+#ifndef TOR_ROUTERSET_H
+#define TOR_ROUTERSET_H
+
+routerset_t *routerset_new(void);
+void routerset_refresh_countries(routerset_t *rs);
+int routerset_parse(routerset_t *target, const char *s,
+                    const char *description);
+void routerset_union(routerset_t *target, const routerset_t *source);
+int routerset_is_list(const routerset_t *set);
+int routerset_needs_geoip(const routerset_t *set);
+int routerset_is_empty(const routerset_t *set);
+int routerset_contains_router(const routerset_t *set, const routerinfo_t *ri,
+                              country_t country);
+int routerset_contains_routerstatus(const routerset_t *set,
+                                    const routerstatus_t *rs,
+                                    country_t country);
+int routerset_contains_extendinfo(const routerset_t *set,
+                                  const extend_info_t *ei);
+
+int routerset_contains_node(const routerset_t *set, const node_t *node);
+void routerset_get_all_nodes(smartlist_t *out, const routerset_t *routerset,
+                             const routerset_t *excludeset,
+                             int running_only);
+#if 0
+void routersets_get_node_disjunction(smartlist_t *target,
+                                const smartlist_t *source,
+                                const routerset_t *include,
+                                const routerset_t *exclude, int running_only);
+#endif
+void routerset_subtract_nodes(smartlist_t *out,
+                                const routerset_t *routerset);
+
+char *routerset_to_string(const routerset_t *routerset);
+int routerset_equal(const routerset_t *old, const routerset_t *new);
+void routerset_free(routerset_t *routerset);
+
+#endif
+