guard selection: Try to clarify and clean up a bit

This is a follow-on for !182.

1 files changed, 61 insertions, 22 deletions

diff --git a/spec/guard-spec/algorithm.md b/spec/guard-spec/algorithm.md
index 8a3e1ca..1dc0b18 100644
--- a/spec/guard-spec/algorithm.md
+++ b/spec/guard-spec/algorithm.md
@@ -301,11 +301,15 @@ An observation that a guard has been 'unreachable' only lasts for
 a given amount of time, since we can't infer that it's unreachable
 now from the fact that it was unreachable a few minutes ago.
 
-<a id="guard-spec.txt-4.6"></a>
+## Circuit status {#CIRC-STATUS}
 
-## Selecting guards for circuits. \[Section:SELECTING\]
+Sometimes the guard selection algorithm will return a guard that we
+would always be happy to use; but in other cases, the guard
+selection algorithm can return a guard that we shouldn't use
+without gathering additional information.
 
-Every origin circuit is now in one of these states:
+From the point of view of guard selection,
+every circuit we build is considered to be in one of these states:
 
  * `<state:usable_on_completion>`
  * `<state:usable_if_no_better_guard>`
@@ -313,8 +317,8 @@ Every origin circuit is now in one of these states:
  * `<state:complete>`
 
 You may only attach streams to `<complete>` circuits.
-(Additionally, you may only send RENDEZVOUS cells, ESTABLISH_INTRO
-cells, and INTRODUCE cells on `<complete>` circuits.)
+(Additionally, you may only send RENDEZVOUS messages, ESTABLISH_INTRO
+messages, and INTRODUCE messages on `<complete>` circuits.)
 
 The per-circuit state machine is:
 
@@ -334,7 +338,36 @@ The per-circuit state machine is:
  * A `<complete>` circuit remains `<complete>` until it fails or is
    closed.
 
- * Each of these transitions is described below.
+```mermaid
+---
+title: Circuit state transitions
+---
+
+[*] -> usable_on_completion
+[*] -> usable_if_no_better_guard
+usable_on_completion -> complete
+usable_on_completion -> failed
+usable_if_no_better_guard -> usable_on_completion
+usable_if_no_better_guard -> waiting_for_better_guard
+usable_if_no_better_guard -> failed
+waiting_for_better_guard -> complete
+waiting_for_better_guard -> failed
+waiting_for_better_guard -> closed
+complete -> failed
+complete -> closed
+failed -> [*]
+closed -> [*]
+```
+<!-- TODO: The above diagram does not yet render. Fix that. -->
+
+Each of these transitions is described in sections below.
+
+<a id="guard-spec.txt-4.6"></a>
+
+## Selecting guards for circuits. \[Section:SELECTING\]
+
+Now that we have described the various lists of guards, we can explain how
+guards are chosen for each circuit.
 
 We keep, as global transient state:
 
@@ -342,23 +375,29 @@ We keep, as global transient state:
    successfully used a circuit or connected to a guard.  At
    startup we set this to "infinitely far in the past."
 
+As an input to the algorithm, we take a list of _restrictions_.
+These may include specific relays or families that we need to avoid.
+
+Here is the algorithm.  It is given as a series of sub-algorithms,
+in decreasing order of preference from best case to worst case.
 When we want to build a circuit, and we need to pick a guard:
 
- * If any entry in PRIMARY_GUARDS has {is_reachable} status of
-   `<maybe>` or `<yes>`, check the first {NUM_USABLE_PRIMARY_GUARDS} or
-   {NUM_USABLE_PRIMARY_DIRECTORY_GUARDS} such guards against
-   any path selection restrictions, to build a temporary list of
-   usable guards. If the path restriction is circuit-specific and
-   excludes a primary guard, do not use that guard, but still
-   increment the number of usable guards that were considered.
-   If the restriction causes the number of guards considered to
-   exceed either usable limit count, then proceed to select another
-   primary guard.
-
-   This usable list is temporary, but because the primary guard ordering
-   is persistent, it will be a stable set. At the end of this selection
-   process, chose uniformly at random from this usable list. The
-   circuit is `<usable_on_completion>`.
+ * In the base case, if any entry in PRIMARY_GUARDS has {is_reachable} status of
+   `<maybe>` or `<yes>`, consider only such guards.  Call them the
+   "reachable primary guards".
+
+   Start by considering the the first {NUM_USABLE_PRIMARY_GUARDS} (or
+   {NUM_USABLE_PRIMARY_DIRECTORY_GUARDS}) reachable primary guards.
+   Remove any guards that do not follow our path selection
+   restrictions, to build a temporary list. If that temporary list contains at
+   least one guard, choose a guard from that list uniformly at
+   random.
+
+   If the temporary list contains no guards, return the first guard
+   from our reachable primary guard that does obey the path restriction.
+
+   When selecting a guard according to this approach, its circuit
+   is `<usable_on_completion>`.
 
    [Note: We do not use {is_pending} on primary guards, since we
    are willing to try to build multiple circuits through them
@@ -380,7 +419,7 @@ When we want to build a circuit, and we need to pick a guard:
    true, and set its {pending_since} to the current time.
    The circuit is `<usable_if_no_better_guard>`.
 
- * Otherwise, if USABLE_FILTERED_GUARDS is empty, we have exhausted
+ * Otherwise, in the worst case, if USABLE_FILTERED_GUARDS is empty, we have exhausted
    all the sampled guards.  In this case we proceed by marking all guards
    as `<maybe>` reachable so that we can keep on trying circuits.