Merge branch 'no-exit-bootstrap-squashed'

14 files changed, 420 insertions, 75 deletions

diff --git a/changes/bug13718-add-internal-bootstrap-statuses b/changes/bug13718-add-internal-bootstrap-statuses
new file mode 100644
index 0000000000..d3e9a7709c
--- /dev/null
+++ b/changes/bug13718-add-internal-bootstrap-statuses
@@ -0,0 +1,9 @@
+  o Minor bugfixes:
+    - Add "internal" to some bootstrap statuses when no exits are available.
+      If the consensus does not contain Exits, Tor will only build internal
+      circuits. In this case, relevant statuses will contain the word
+      "internal" as indicated in the Tor control-spec.txt. When bootstrap
+      completes, Tor will be ready to handle an application requesting an
+      internal circuit to hidden services at ".onion" addresses.
+      If a future consensus contains Exits, exit circuits may become available.
+      Consequential change from #13718.
diff --git a/changes/bug13718-avoid-excluding-guards b/changes/bug13718-avoid-excluding-guards
new file mode 100644
index 0000000000..bf80d2a7e7
--- /dev/null
+++ b/changes/bug13718-avoid-excluding-guards
@@ -0,0 +1,8 @@
+  o Minor bugfixes:
+    - Avoid excluding guards from path building in minimal test networks,
+      when we're in a test network, and excluding guards would exclude
+      all nodes. This typically occurs in incredibly small tor networks,
+      and those using TestingAuthVoteGuard *
+      This fix only applies to minimal, testing tor networks,
+      so it's no less secure.
+      Discovered as part of #13718.
diff --git a/changes/bug13718-check-consensus-exits b/changes/bug13718-check-consensus-exits
new file mode 100644
index 0000000000..5ca4b115eb
--- /dev/null
+++ b/changes/bug13718-check-consensus-exits
@@ -0,0 +1,6 @@
+  o Minor enhancement:
+    - Check if there are exits in the consensus.
+      Add router_have_consensus_path() which reports whether
+      the consensus has exit paths, internal paths, or whether it
+      just doesn't know.
+      Used by #13718 and #13814.
diff --git a/changes/bug13718-make-nodelist-args-readable b/changes/bug13718-make-nodelist-args-readable
new file mode 100644
index 0000000000..7377a81d38
--- /dev/null
+++ b/changes/bug13718-make-nodelist-args-readable
@@ -0,0 +1,8 @@
+  o Minor refactoring:
+    - Refactor count_usable_descriptors to use named enums for exit_only.
+      count_usable_descriptors now uses named exit_only values:
+       *  USABLE_DESCRIPTOR_ALL
+       *  USABLE_DESCRIPTOR_EXIT_ONLY
+    - Add debug logging code for descriptor counts.
+      This resolves nickm's request in bug 13718 to improve argument
+      readability.
diff --git a/changes/bug13814-avoid-exit-paths-no-exits b/changes/bug13814-avoid-exit-paths-no-exits
new file mode 100644
index 0000000000..8b0446f5f0
--- /dev/null
+++ b/changes/bug13814-avoid-exit-paths-no-exits
@@ -0,0 +1,25 @@
+  o Minor bugfixes:
+    - Avoid building exit circuits from a consensus with no exits
+      Tor can now build circuits from a consensus with no exits.
+      But if it tries to build exit circuits, they fail and flood the logs.
+      The circuit types in the Exit Circuits list below will only be
+      built if the current consensus has exits. If it doesn't,
+      only the Internal Circuits will be built. (This can change
+      with each new consensus.)
+      Fixes bug #13814, causes fewer path failures due to #13817.
+
+      Exit Circuits:
+        Predicted Exit Circuits
+        User Traffic Circuits
+        Most AP Streams
+        Circuits Marked Exit
+        Build Timeout Circuits (with exits)
+
+      Internal Circuits:
+        Hidden Service Server Circuits
+        Hidden Service Client Circuits
+        Hidden Service AP Streams
+        Hidden Service Intro Point Streams
+        Circuits Marked Internal
+        Build Timeout Circuits (with no exits)
+        Other Circuits?
diff --git a/changes/bug13814-reachability-without-exits b/changes/bug13814-reachability-without-exits
new file mode 100644
index 0000000000..43a326b847
--- /dev/null
+++ b/changes/bug13814-reachability-without-exits
@@ -0,0 +1,15 @@
+  o Minor bugfixes:
+    - Allow tor to build circuits using a consensus with
+      no exits. If the consensus has no exits (typical of
+      a bootstrapping test network), allow tor to build
+      circuits once enough descriptors have been
+      downloaded.
+      When there are no exits, we always have "enough"
+      exit descriptors. (We treat the proportion of
+      available exit descriptors as 100%.)
+      This assists in bootstrapping a testing Tor
+      network.
+      Fixes bug 13718.
+      Makes bug 13161's TestingDirAuthVoteExit
+      non-essential.
+      (But still useful for speeding up a bootstrap.)
diff --git a/changes/bug13924-fix-testing-reachability b/changes/bug13924-fix-testing-reachability
new file mode 100644
index 0000000000..914a159007
--- /dev/null
+++ b/changes/bug13924-fix-testing-reachability
@@ -0,0 +1,7 @@
+  o Minor bugfixes:
+    - Stop assuming that private addresses are local when checking
+      reachability in a TestingTorNetwork. Instead, when testing, assume
+      all OR connections are remote. (This is necessary due to many test
+      scenarios running all nodes on localhost.)
+      This assists in bootstrapping a testing Tor network.
+      Fixes bugs 13718 & 13924.
diff --git a/src/or/circuitbuild.c b/src/or/circuitbuild.c
index faddc08e03..7061ab0e0b 100644
--- a/src/or/circuitbuild.c
+++ b/src/or/circuitbuild.c
@@ -1378,8 +1378,10 @@ onionskin_answer(or_circuit_t *circ,
   log_debug(LD_CIRC,"Finished sending '%s' cell.",
             circ->is_first_hop ? "created_fast" : "created");
 
-  if (!channel_is_local(circ->p_chan) &&
-      !channel_is_outgoing(circ->p_chan)) {
+  /* Ignore the local bit when testing - many test networks run on local
+   * addresses */
+  if ((!channel_is_local(circ->p_chan) || get_options()->TestingTorNetwork)
+      && !channel_is_outgoing(circ->p_chan)) {
     /* record that we could process create cells from a non-local conn
      * that we didn't initiate; presumably this means that create cells
      * can reach us too. */
@@ -1863,7 +1865,7 @@ onion_pick_cpath_exit(origin_circuit_t *circ, extend_info_t *exit)
       choose_good_exit_server(circ->base_.purpose, state->need_uptime,
                               state->need_capacity, state->is_internal);
     if (!node) {
-      log_warn(LD_CIRC,"failed to choose an exit server");
+      log_warn(LD_CIRC,"Failed to choose an exit server");
       return -1;
     }
     exit = extend_info_from_node(node, 0);
@@ -1990,7 +1992,8 @@ choose_good_middle_server(uint8_t purpose,
   tor_assert(CIRCUIT_PURPOSE_MIN_ <= purpose &&
              purpose <= CIRCUIT_PURPOSE_MAX_);
 
-  log_debug(LD_CIRC, "Contemplating intermediate hop: random choice.");
+  log_debug(LD_CIRC, "Contemplating intermediate hop %d: random choice.",
+            cur_len);
   excluded = smartlist_new();
   if ((r = build_state_get_exit_node(state))) {
     nodelist_add_node_and_family(excluded, r);
@@ -2052,9 +2055,18 @@ choose_good_entry_server(uint8_t purpose, cpath_build_state_t *state)
         smartlist_add(excluded, (void*)node);
     });
   }
-  /* and exclude current entry guards and their families, if applicable */
+  /* and exclude current entry guards and their families,
+   * unless we're in a test network, and excluding guards
+   * would exclude all nodes (i.e. we're in an incredibly small tor network,
+   * or we're using TestingAuthVoteGuard *).
+   * This is an incomplete fix, but is no worse than the previous behaviour,
+   * and only applies to minimal, testing tor networks
+   * (so it's no less secure) */
   /*XXXX025 use the using_as_guard flag to accomplish this.*/
-  if (options->UseEntryGuards) {
+  if (options->UseEntryGuards
+      && (!options->TestingTorNetwork ||
+          smartlist_len(nodelist_get_list()) > smartlist_len(get_entry_guards())
+     )) {
     SMARTLIST_FOREACH(get_entry_guards(), const entry_guard_t *, entry,
       {
         if ((node = node_get_by_id(entry->identity))) {
diff --git a/src/or/circuituse.c b/src/or/circuituse.c
index 90571360de..015270cd25 100644
--- a/src/or/circuituse.c
+++ b/src/or/circuituse.c
@@ -1024,9 +1024,11 @@ circuit_predict_and_launch_new(void)
 
   /* Second, see if we need any more exit circuits. */
   /* check if we know of a port that's been requested recently
-   * and no circuit is currently available that can handle it. */
+   * and no circuit is currently available that can handle it.
+   * Exits (obviously) require an exit circuit. */
   if (!circuit_all_predicted_ports_handled(now, &port_needs_uptime,
-                                           &port_needs_capacity)) {
+                                           &port_needs_capacity)
+      && router_have_consensus_path() == CONSENSUS_PATH_EXIT) {
     if (port_needs_uptime)
       flags |= CIRCLAUNCH_NEED_UPTIME;
     if (port_needs_capacity)
@@ -1038,8 +1040,10 @@ circuit_predict_and_launch_new(void)
     return;
   }
 
-  /* Third, see if we need any more hidden service (server) circuits. */
-  if (num_rend_services() && num_uptime_internal < 3) {
+  /* Third, see if we need any more hidden service (server) circuits.
+   * HS servers only need an internal circuit. */
+  if (num_rend_services() && num_uptime_internal < 3
+      && router_have_consensus_path() != CONSENSUS_PATH_UNKNOWN) {
     flags = (CIRCLAUNCH_NEED_CAPACITY | CIRCLAUNCH_NEED_UPTIME |
              CIRCLAUNCH_IS_INTERNAL);
     log_info(LD_CIRC,
@@ -1050,11 +1054,13 @@ circuit_predict_and_launch_new(void)
     return;
   }
 
-  /* Fourth, see if we need any more hidden service (client) circuits. */
+  /* Fourth, see if we need any more hidden service (client) circuits.
+   * HS clients only need an internal circuit. */
   if (rep_hist_get_predicted_internal(now, &hidserv_needs_uptime,
                                       &hidserv_needs_capacity) &&
       ((num_uptime_internal<2 && hidserv_needs_uptime) ||
-        num_internal<2)) {
+        num_internal<2)
+        && router_have_consensus_path() != CONSENSUS_PATH_UNKNOWN) {
     if (hidserv_needs_uptime)
       flags |= CIRCLAUNCH_NEED_UPTIME;
     if (hidserv_needs_capacity)
@@ -1071,15 +1077,23 @@ circuit_predict_and_launch_new(void)
   /* Finally, check to see if we still need more circuits to learn
    * a good build timeout. But if we're close to our max number we
    * want, don't do another -- we want to leave a few slots open so
-   * we can still build circuits preemptively as needed. */
-  if (num < MAX_UNUSED_OPEN_CIRCUITS-2 &&
-      ! circuit_build_times_disabled() &&
-      circuit_build_times_needs_circuits_now(get_circuit_build_times())) {
-    flags = CIRCLAUNCH_NEED_CAPACITY;
-    log_info(LD_CIRC,
-             "Have %d clean circs need another buildtime test circ.", num);
-    circuit_launch(CIRCUIT_PURPOSE_C_GENERAL, flags);
-    return;
+   * we can still build circuits preemptively as needed.
+   * XXXX make the assumption that build timeout streams should be
+   * created whenever we can build internal circuits. */
+  if (router_have_consensus_path() != CONSENSUS_PATH_UNKNOWN) {
+    if (num < MAX_UNUSED_OPEN_CIRCUITS-2 &&
+        ! circuit_build_times_disabled() &&
+        circuit_build_times_needs_circuits_now(get_circuit_build_times())) {
+      flags = CIRCLAUNCH_NEED_CAPACITY;
+      /* if there are no exits in the consensus, make timeout
+       * circuits internal */
+      if (router_have_consensus_path() == CONSENSUS_PATH_INTERNAL)
+        flags |= CIRCLAUNCH_IS_INTERNAL;
+      log_info(LD_CIRC,
+               "Have %d clean circs need another buildtime test circ.", num);
+      circuit_launch(CIRCUIT_PURPOSE_C_GENERAL, flags);
+      return;
+    }
   }
 }
 
@@ -1096,11 +1110,17 @@ circuit_build_needed_circs(time_t now)
 {
   const or_options_t *options = get_options();
 
-  /* launch a new circ for any pending streams that need one */
-  connection_ap_attach_pending();
+  /* launch a new circ for any pending streams that need one
+   * XXXX make the assumption that (some) AP streams (i.e. HS clients)
+   * don't require an exit circuit, review in #13814.
+   * This allows HSs to function in a consensus without exits. */
+  if (router_have_consensus_path() != CONSENSUS_PATH_UNKNOWN)
+    connection_ap_attach_pending();
 
-  /* make sure any hidden services have enough intro points */
-  rend_services_introduce();
+  /* make sure any hidden services have enough intro points
+   * HS intro point streams only require an internal circuit */
+  if (router_have_consensus_path() != CONSENSUS_PATH_UNKNOWN)
+    rend_services_introduce();
 
   circuit_expire_old_circs_as_needed(now);
 
@@ -1632,6 +1652,16 @@ circuit_launch(uint8_t purpose, int flags)
   return circuit_launch_by_extend_info(purpose, NULL, flags);
 }
 
+/** DOCDOC */
+static int
+have_enough_path_info(int need_exit)
+{
+  if (need_exit)
+    return router_have_consensus_path() == CONSENSUS_PATH_EXIT;
+  else
+    return router_have_consensus_path() != CONSENSUS_PATH_UNKNOWN
+}
+
 /** Launch a new circuit with purpose <b>purpose</b> and exit node
  * <b>extend_info</b> (or NULL to select a random exit node).  If flags
  * contains CIRCLAUNCH_NEED_UPTIME, choose among routers with high uptime.  If
@@ -1646,10 +1676,14 @@ circuit_launch_by_extend_info(uint8_t purpose,
 {
   origin_circuit_t *circ;
   int onehop_tunnel = (flags & CIRCLAUNCH_ONEHOP_TUNNEL) != 0;
-
-  if (!onehop_tunnel && !router_have_minimum_dir_info()) {
-    log_debug(LD_CIRC,"Haven't fetched enough directory info yet; canceling "
-              "circuit launch.");
+  int have_path = have_enough_path_info(! (flags & CIRCLAUNCH_IS_INTERNAL) );
+
+  if (!onehop_tunnel && (!router_have_minimum_dir_info() || !have_path)) {
+    log_debug(LD_CIRC,"Haven't %s yet; canceling "
+              "circuit launch.",
+              !router_have_minimum_dir_info() ?
+              "fetched enough directory info" :
+              "received a consensus with exits");
     return NULL;
   }
 
@@ -1806,7 +1840,9 @@ circuit_get_open_circ_or_launch(entry_connection_t *conn,
     return 1; /* we're happy */
   }
 
-  if (!want_onehop && !router_have_minimum_dir_info()) {
+  int have_path = have_enough_path_info(!need_internal);
+
+  if (!want_onehop && (!router_have_minimum_dir_info() || !have_path)) {
     if (!connection_get_by_type(CONN_TYPE_DIR)) {
       int severity = LOG_NOTICE;
       /* FFFF if this is a tunneled directory fetch, don't yell
@@ -1814,14 +1850,20 @@ circuit_get_open_circ_or_launch(entry_connection_t *conn,
       if (entry_list_is_constrained(options) &&
           entries_known_but_down(options)) {
         log_fn(severity, LD_APP|LD_DIR,
-               "Application request when we haven't used client functionality "
-               "lately. Optimistically trying known %s again.",
+               "Application request when we haven't %s. "
+               "Optimistically trying known %s again.",
+               !router_have_minimum_dir_info() ?
+               "used client functionality lately" :
+               "received a consensus with exits",
                options->UseBridges ? "bridges" : "entrynodes");
         entries_retry_all(options);
       } else if (!options->UseBridges || any_bridge_descriptors_known()) {
         log_fn(severity, LD_APP|LD_DIR,
-               "Application request when we haven't used client functionality "
-               "lately. Optimistically trying directory fetches again.");
+               "Application request when we haven't %s. "
+               "Optimistically trying directory fetches again.",
+               !router_have_minimum_dir_info() ?
+               "used client functionality lately" :
+               "received a consensus with exits");
         routerlist_retry_directory_downloads(time(NULL));
       }
     }
diff --git a/src/or/config.c b/src/or/config.c
index ae4b0892d6..9f5bd3b957 100644
--- a/src/or/config.c
+++ b/src/or/config.c
@@ -1833,7 +1833,7 @@ options_act(const or_options_t *old_options)
                  directory_fetches_dir_info_early(old_options)) ||
         !bool_eq(directory_fetches_dir_info_later(options),
                  directory_fetches_dir_info_later(old_options))) {
-      /* Make sure update_router_have_min_dir_info gets called. */
+      /* Make sure update_router_have_minimum_dir_info() gets called. */
       router_dir_info_changed();
       /* We might need to download a new consensus status later or sooner than
        * we had expected. */
diff --git a/src/or/control.c b/src/or/control.c
index dc67588d6a..7214559136 100644
--- a/src/or/control.c
+++ b/src/or/control.c
@@ -4807,23 +4807,43 @@ bootstrap_status_to_string(bootstrap_status_t s, const char **tag,
       break;
     case BOOTSTRAP_STATUS_REQUESTING_DESCRIPTORS:
       *tag = "requesting_descriptors";
-      *summary = "Asking for relay descriptors";
+      /* XXXX this appears to incorrectly report internal on most loads */
+      *summary = router_have_consensus_path() == CONSENSUS_PATH_INTERNAL ?
+        "Asking for relay descriptors for internal paths" :
+        "Asking for relay descriptors";
       break;
+    /* If we're sure there are no exits in the consensus,
+     * inform the controller by adding "internal"
+     * to the status summaries.
+     * (We only check this while loading descriptors,
+     * so we may not know in the earlier stages.)
+     * But if there are exits, we can't be sure whether
+     * we're creating internal or exit paths/circuits.
+     * XXXX Or should be use different tags or statuses
+     * for internal and exit/all? */
     case BOOTSTRAP_STATUS_LOADING_DESCRIPTORS:
       *tag = "loading_descriptors";
-      *summary = "Loading relay descriptors";
+      *summary = router_have_consensus_path() == CONSENSUS_PATH_INTERNAL ?
+        "Loading relay descriptors for internal paths" :
+        "Loading relay descriptors";
       break;
     case BOOTSTRAP_STATUS_CONN_OR:
       *tag = "conn_or";
-      *summary = "Connecting to the Tor network";
+      *summary = router_have_consensus_path() == CONSENSUS_PATH_INTERNAL ?
+        "Connecting to the Tor network internally" :
+        "Connecting to the Tor network";
       break;
     case BOOTSTRAP_STATUS_HANDSHAKE_OR:
       *tag = "handshake_or";
-      *summary = "Finishing handshake with first hop";
+      *summary = router_have_consensus_path() == CONSENSUS_PATH_INTERNAL ?
+        "Finishing handshake with first hop of internal circuit" :
+        "Finishing handshake with first hop";
       break;
     case BOOTSTRAP_STATUS_CIRCUIT_CREATE:
       *tag = "circuit_create";
-      *summary = "Establishing a Tor circuit";
+      *summary = router_have_consensus_path() == CONSENSUS_PATH_INTERNAL ?
+        "Establishing an internal Tor circuit" :
+        "Establishing a Tor circuit";
       break;
     case BOOTSTRAP_STATUS_DONE:
       *tag = "done";
diff --git a/src/or/dirserv.c b/src/or/dirserv.c
index a1d22b041f..45d12ed3b1 100644
--- a/src/or/dirserv.c
+++ b/src/or/dirserv.c
@@ -733,7 +733,7 @@ running_long_enough_to_decide_unreachable(void)
 }
 
 /** Each server needs to have passed a reachability test no more
- * than this number of seconds ago, or he is listed as down in
+ * than this number of seconds ago, or it is listed as down in
  * the directory. */
 #define REACHABLE_TIMEOUT (45*60)
 
diff --git a/src/or/nodelist.c b/src/or/nodelist.c
index e0e01ec190..34d1d5f4d7 100644
--- a/src/or/nodelist.c
+++ b/src/or/nodelist.c
@@ -24,6 +24,23 @@
 
 static void nodelist_drop_node(node_t *node, int remove_from_ht);
 static void node_free(node_t *node);
+
+/** count_usable_descriptors counts descriptors with these flag(s)
+ */
+typedef enum {
+  /* All descriptors regardless of flags */
+  USABLE_DESCRIPTOR_ALL = 0,
+  /* Only descriptors with the Exit flag */
+  USABLE_DESCRIPTOR_EXIT_ONLY = 1
+} usable_descriptor_t;
+static void count_usable_descriptors(int *num_present,
+                                     int *num_usable,
+                                     smartlist_t *descs_out,
+                                     const networkstatus_t *consensus,
+                                     const or_options_t *options,
+                                     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);
@@ -1256,20 +1273,28 @@ router_set_status(const char *digest, int up)
 }
 
 /** True iff, the last time we checked whether we had enough directory info
- * to build circuits, the answer was "yes". */
+ * to build circuits, the answer was "yes". If there are no exits in the
+ * consensus, we act as if we have 100% of the exit directory info. */
 static int have_min_dir_info = 0;
+
+/** Does the consensus contain nodes that can exit? */
+static consensus_path_type_t have_consensus_path = CONSENSUS_PATH_UNKNOWN;
+
 /** 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[256] = "";
-
-/** 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.
+static char dir_info_status[512] = "";
+
+/** Return true iff we have enough consensus information to
+ * start building circuits.  Right now, this means "a consensus that's
+ * less than a day old, and at least 60% of router descriptors (configurable),
+ * weighted by bandwidth. Treat the exit fraction as 100% if there are
+ * no exits in the consensus."
+ * To obtain the final weighted bandwidth, we multiply the
+ * weighted bandwidth fraction for each position (guard, middle, exit). */
 int
 router_have_minimum_dir_info(void)
 {
@@ -1291,6 +1316,24 @@ router_have_minimum_dir_info(void)
   return have_min_dir_info;
 }
 
+/** Set to CONSENSUS_PATH_EXIT if there is at least one exit node
+ * in the consensus. We update this flag in compute_frac_paths_available if
+ * there is at least one relay that has an Exit flag in the consensus.
+ * Used to avoid building exit circuits when they will almost certainly fail.
+ * Set to CONSENSUS_PATH_INTERNAL if there are no exits in the consensus.
+ * (This situation typically occurs during bootstrap of a test network.)
+ * Set to CONSENSUS_PATH_UNKNOWN if we have never checked, or have
+ * reason to believe our last known value was invalid or has expired.
+ * If we're in a network with TestingDirAuthVoteExit set,
+ * this can cause router_have_consensus_path() to be set to
+ * CONSENSUS_PATH_EXIT, even if there are no nodes with accept exit policies.
+ */
+consensus_path_type_t
+router_have_consensus_path(void)
+{
+  return have_consensus_path;
+}
+
 /** 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.
@@ -1313,20 +1356,23 @@ get_dir_info_status_string(void)
 /** 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.  If *descs_out is present, add a node_t for each
- * usable descriptor to it.
+ * *<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 USABLE_DESCRIPTOR_EXIT_ONLY, only consider nodes
+ * with the Exit flag.
+ * If *<b>descs_out</b> is present, add a node_t for each usable descriptor
+ * to it.
  */
 static void
 count_usable_descriptors(int *num_present, int *num_usable,
                          smartlist_t *descs_out,
                          const networkstatus_t *consensus,
                          const or_options_t *options, time_t now,
-                         routerset_t *in_set, int exit_only)
+                         routerset_t *in_set,
+                         usable_descriptor_t exit_only)
 {
   const int md = (consensus->flavor == FLAV_MICRODESC);
-  *num_present = 0, *num_usable=0;
+  *num_present = 0, *num_usable = 0;
 
   SMARTLIST_FOREACH_BEGIN(consensus->routerstatus_list, routerstatus_t *, rs)
     {
@@ -1334,7 +1380,7 @@ count_usable_descriptors(int *num_present, int *num_usable,
        if (!node)
          continue; /* This would be a bug: every entry in the consensus is
                     * supposed to have a node. */
-       if (exit_only && ! rs->is_exit)
+       if (exit_only == USABLE_DESCRIPTOR_EXIT_ONLY && ! rs->is_exit)
          continue;
        if (in_set && ! routerset_contains_routerstatus(in_set, rs, -1))
          continue;
@@ -1358,11 +1404,21 @@ count_usable_descriptors(int *num_present, int *num_usable,
 
   log_debug(LD_DIR, "%d usable, %d present (%s%s).",
             *num_usable, *num_present,
-            md ? "microdesc" : "desc", exit_only ? " exits" : "s");
+            md ? "microdesc" : "desc",
+            exit_only == USABLE_DESCRIPTOR_EXIT_ONLY ? " exits" : "s");
 }
 
 /** Return an estimate of which fraction of usable paths through the Tor
- * network we have available for use. */
+ * network we have available for use.
+ * Count how many routers seem like ones we'd use, and how many of
+ * <em>those</em> we have descriptors for.  Store the former in
+ * *<b>num_usable_out</b> and the latter in *<b>num_present_out</b>.
+ * If **<b>status_out</b> is present, allocate a new string and print the
+ * available percentages of guard, middle, and exit nodes to it, noting
+ * whether there are exits in the consensus.
+ * If there are no guards in the consensus,
+ * we treat the exit fraction as 100%.
+ */
 static double
 compute_frac_paths_available(const networkstatus_t *consensus,
                              const or_options_t *options, time_t now,
@@ -1375,14 +1431,19 @@ compute_frac_paths_available(const networkstatus_t *consensus,
   smartlist_t *myexits= smartlist_new();
   smartlist_t *myexits_unflagged = smartlist_new();
   double f_guard, f_mid, f_exit, f_myexit, f_myexit_unflagged;
-  int np, nu; /* Ignored */
+  double f_path = 0.0;
+  /* Used to determine whether there are any exits in the consensus */
+  int np = 0;
+  /* Used to determine whether there are any exits with descriptors */
+  int nu = 0;
   const int authdir = authdir_mode_v3(options);
 
   count_usable_descriptors(num_present_out, num_usable_out,
-                           mid, consensus, options, now, NULL, 0);
+                           mid, consensus, options, now, NULL,
+                           USABLE_DESCRIPTOR_ALL);
   if (options->EntryNodes) {
     count_usable_descriptors(&np, &nu, guards, consensus, options, now,
-                             options->EntryNodes, 0);
+                             options->EntryNodes, USABLE_DESCRIPTOR_ALL);
   } else {
     SMARTLIST_FOREACH(mid, const node_t *, node, {
       if (authdir) {
@@ -1395,22 +1456,78 @@ compute_frac_paths_available(const networkstatus_t *consensus,
     });
   }
 
-  /* All nodes with exit flag */
+  /* All nodes with exit flag
+   * If we're in a network with TestingDirAuthVoteExit set,
+   * this can cause false positives on have_consensus_path,
+   * incorrectly setting it to CONSENSUS_PATH_EXIT. This is
+   * an unavoidable feature of forcing authorities to declare
+   * certain nodes as exits.
+   */
   count_usable_descriptors(&np, &nu, exits, consensus, options, now,
-                           NULL, 1);
+                           NULL, USABLE_DESCRIPTOR_EXIT_ONLY);
+  log_debug(LD_NET,
+            "%s: %d present, %d usable",
+            "exits",
+            np,
+            nu);
+
+  /* We need at least 1 exit present in the consensus to consider
+   * building exit paths */
+  /* Update our understanding of whether the consensus has exits */
+  consensus_path_type_t old_have_consensus_path = have_consensus_path;
+  have_consensus_path = ((np > 0) ?
+                         CONSENSUS_PATH_EXIT :
+                         CONSENSUS_PATH_INTERNAL);
+
+  if (have_consensus_path == CONSENSUS_PATH_INTERNAL
+      && old_have_consensus_path != have_consensus_path) {
+    log_notice(LD_NET,
+               "The current consensus has no exit nodes. "
+               "Tor can only build internal paths, "
+               "such as paths to hidden services.");
+
+    /* However, exit nodes can reachability self-test using this consensus,
+     * join the network, and appear in a later consensus. This will allow
+     * the network to build exit paths, such as paths for world wide web
+     * browsing (as distinct from hidden service web browsing). */
+  }
+
   /* All nodes with exit flag in ExitNodes option */
   count_usable_descriptors(&np, &nu, myexits, consensus, options, now,
-                           options->ExitNodes, 1);
+                           options->ExitNodes, USABLE_DESCRIPTOR_EXIT_ONLY);
+  log_debug(LD_NET,
+            "%s: %d present, %d usable",
+            "myexits",
+            np,
+            nu);
+
   /* Now compute the nodes in the ExitNodes option where which we don't know
    * what their exit policy is, or we know it permits something. */
   count_usable_descriptors(&np, &nu, myexits_unflagged,
                            consensus, options, now,
-                           options->ExitNodes, 0);
+                           options->ExitNodes, USABLE_DESCRIPTOR_ALL);
+  log_debug(LD_NET,
+            "%s: %d present, %d usable",
+            "myexits_unflagged (initial)",
+            np,
+            nu);
+
   SMARTLIST_FOREACH_BEGIN(myexits_unflagged, const node_t *, node) {
-    if (node_has_descriptor(node) && node_exit_policy_rejects_all(node))
+    if (node_has_descriptor(node) && node_exit_policy_rejects_all(node)) {
       SMARTLIST_DEL_CURRENT(myexits_unflagged, node);
+      /* this node is not actually an exit */
+      np--;
+      /* this node is unusable as an exit */
+      nu--;
+    }
   } SMARTLIST_FOREACH_END(node);
 
+  log_debug(LD_NET,
+            "%s: %d present, %d usable",
+            "myexits_unflagged (final)",
+            np,
+            nu);
+
   f_guard = frac_nodes_with_descriptors(guards, WEIGHT_FOR_GUARD);
   f_mid   = frac_nodes_with_descriptors(mid,    WEIGHT_FOR_MID);
   f_exit  = frac_nodes_with_descriptors(exits,  WEIGHT_FOR_EXIT);
@@ -1418,6 +1535,12 @@ compute_frac_paths_available(const networkstatus_t *consensus,
   f_myexit_unflagged=
             frac_nodes_with_descriptors(myexits_unflagged,WEIGHT_FOR_EXIT);
 
+  log_debug(LD_NET,
+            "f_exit: %.2f, f_myexit: %.2f, f_myexit_unflagged: %.2f",
+            f_exit,
+            f_myexit,
+            f_myexit_unflagged);
+
   /* If our ExitNodes list has eliminated every possible Exit node, and there
    * were some possible Exit nodes, then instead consider nodes that permit
    * exiting to some ports. */
@@ -1439,16 +1562,28 @@ compute_frac_paths_available(const networkstatus_t *consensus,
   if (f_myexit < f_exit)
     f_exit = f_myexit;
 
+  /* if the consensus has no exits, treat the exit fraction as 100% */
+  if (router_have_consensus_path() != CONSENSUS_PATH_EXIT) {
+    f_exit = 1.0;
+  }
+
+  f_path = f_guard * f_mid * f_exit;
+
   if (status_out)
     tor_asprintf(status_out,
                  "%d%% of guards bw, "
                  "%d%% of midpoint bw, and "
-                 "%d%% of exit bw",
+                 "%d%% of exit bw%s = "
+                 "%d%% of path bw",
                  (int)(f_guard*100),
                  (int)(f_mid*100),
-                 (int)(f_exit*100));
+                 (int)(f_exit*100),
+                 (router_have_consensus_path() == CONSENSUS_PATH_EXIT ?
+                  "" :
+                  " (no exits in consensus)"),
+                 (int)(f_path*100));
 
-  return f_guard * f_mid * f_exit;
+  return f_path;
 }
 
 /** We just fetched a new set of descriptors. Compute how far through
@@ -1521,6 +1656,9 @@ update_router_have_minimum_dir_info(void)
 
   using_md = consensus->flavor == FLAV_MICRODESC;
 
+#define NOTICE_DIR_INFO_STATUS_INTERVAL (60)
+
+  /* Check fraction of available paths */
   {
     char *status = NULL;
     int num_present=0, num_usable=0;
@@ -1529,16 +1667,37 @@ update_router_have_minimum_dir_info(void)
                                                 &status);
 
     if (paths < get_frac_paths_needed_for_circs(options,consensus)) {
-      tor_snprintf(dir_info_status, sizeof(dir_info_status),
-                   "We need more %sdescriptors: we have %d/%d, and "
-                   "can only build %d%% of likely paths. (We have %s.)",
-                   using_md?"micro":"", num_present, num_usable,
-                   (int)(paths*100), status);
-      /* log_notice(LD_NET, "%s", dir_info_status); */
+      /* these messages can be excessive in testing networks */
+      static ratelim_t last_warned =
+        RATELIM_INIT(NOTICE_DIR_INFO_STATUS_INTERVAL);
+      char *suppression_msg = NULL;
+      if ((suppression_msg = rate_limit_log(&last_warned, time(NULL)))) {
+        tor_snprintf(dir_info_status, sizeof(dir_info_status),
+                     "We need more %sdescriptors: we have %d/%d, and "
+                     "can only build %d%% of likely paths. (We have %s.)",
+                     using_md?"micro":"", num_present, num_usable,
+                     (int)(paths*100), status);
+        log_warn(LD_NET, "%s%s", dir_info_status, suppression_msg);
+        tor_free(suppression_msg);
+      }
       tor_free(status);
       res = 0;
       control_event_bootstrap(BOOTSTRAP_STATUS_REQUESTING_DESCRIPTORS, 0);
       goto done;
+    } else {
+      /* these messages can be excessive in testing networks */
+      static ratelim_t last_warned =
+      RATELIM_INIT(NOTICE_DIR_INFO_STATUS_INTERVAL);
+      char *suppression_msg = NULL;
+      if ((suppression_msg = rate_limit_log(&last_warned, time(NULL)))) {
+        tor_snprintf(dir_info_status, sizeof(dir_info_status),
+                     "We have enough %sdescriptors: we have %d/%d, and "
+                     "can build %d%% of likely paths. (We have %s.)",
+                     using_md?"micro":"", num_present, num_usable,
+                     (int)(paths*100), status);
+        log_info(LD_NET, "%s%s", dir_info_status, suppression_msg);
+        tor_free(suppression_msg);
+      }
     }
 
     tor_free(status);
@@ -1546,12 +1705,16 @@ update_router_have_minimum_dir_info(void)
   }
 
  done:
+
+  /* If paths have just become available in this update. */
   if (res && !have_min_dir_info) {
     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 paths have just become unavailable in this update. */
   if (!res && have_min_dir_info) {
     int quiet = directory_too_idle_to_fetch_descriptors(options, now);
     tor_log(quiet ? LOG_INFO : LOG_NOTICE, LD_DIR,
@@ -1563,7 +1726,7 @@ update_router_have_minimum_dir_info(void)
      * should only do while circuits are working, like reachability tests
      * and fetching bridge descriptors only over circuits. */
     note_that_we_maybe_cant_complete_circuits();
-
+    have_consensus_path = CONSENSUS_PATH_UNKNOWN;
     control_event_client_status(LOG_NOTICE, "NOT_ENOUGH_DIR_INFO");
   }
   have_min_dir_info = res;
diff --git a/src/or/nodelist.h b/src/or/nodelist.h
index 48b0e94be0..2e59da673e 100644
--- a/src/or/nodelist.h
+++ b/src/or/nodelist.h
@@ -79,7 +79,37 @@ int node_is_unreliable(const node_t *router, int need_uptime,
 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);
+
+/** router_have_minimum_dir_info tests to see if we have enough
+ * descriptor information to create circuits.
+ * If there are exits in the consensus, we wait until we have enough
+ * info to create exit paths before creating any circuits. If there are
+ * no exits in the consensus, we wait for enough info to create internal
+ * paths, and should avoid creating exit paths, as they will simply fail.
+ * We make sure we create all available circuit types at the same time. */
 int router_have_minimum_dir_info(void);
+
+/** Set to CONSENSUS_PATH_EXIT if there is at least one exit node
+ * in the consensus. We update this flag in compute_frac_paths_available if
+ * there is at least one relay that has an Exit flag in the consensus.
+ * Used to avoid building exit circuits when they will almost certainly fail.
+ * Set to CONSENSUS_PATH_INTERNAL if there are no exits in the consensus.
+ * (This situation typically occurs during bootstrap of a test network.)
+ * Set to CONSENSUS_PATH_UNKNOWN if we have never checked, or have
+ * reason to believe our last known value was invalid or has expired.
+ */
+typedef enum {
+  /* we haven't checked yet, or we have invalidated our previous check */
+  CONSENSUS_PATH_UNKNOWN = -1,
+  /* The consensus only has internal relays, and we should only
+   * create internal paths, circuits, streams, ... */
+  CONSENSUS_PATH_INTERNAL = 0,
+  /* The consensus has at least one exit, and can therefore (potentially)
+   * create exit and internal paths, circuits, streams, ... */
+  CONSENSUS_PATH_EXIT = 1
+} consensus_path_type_t;
+consensus_path_type_t router_have_consensus_path(void);
+
 void router_dir_info_changed(void);
 const char *get_dir_info_status_string(void);
 int count_loading_descriptors_progress(void);