1 /* Copyright (c) 2001 Matej Pfajfar.
2 * Copyright (c) 2001-2004, Roger Dingledine.
3 * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
4 * Copyright (c) 2007-2017, The Tor Project, Inc. */
5 /* See LICENSE for licensing information */
9 * \brief Header file for circuitbuild.c.
12 #ifndef TOR_ENTRYNODES_H
13 #define TOR_ENTRYNODES_H
17 /* Forward declare for guard_selection_t; entrynodes.c has the real struct */
18 typedef struct guard_selection_s guard_selection_t
;
20 /* Forward declare for entry_guard_t; the real declaration is private. */
21 typedef struct entry_guard_t entry_guard_t
;
23 /* Forward declaration for circuit_guard_state_t; the real declaration is
25 typedef struct circuit_guard_state_t circuit_guard_state_t
;
27 /* Forward declaration for entry_guard_restriction_t; the real declaration is
29 typedef struct entry_guard_restriction_t entry_guard_restriction_t
;
31 /* Information about a guard's pathbias status.
32 * These fields are used in circpathbias.c to try to detect entry
33 * nodes that are failing circuits at a suspicious frequency.
35 typedef struct guard_pathbias_t
{
36 unsigned int path_bias_noticed
: 1; /**< Did we alert the user about path
37 * bias for this node already? */
38 unsigned int path_bias_warned
: 1; /**< Did we alert the user about path bias
39 * for this node already? */
40 unsigned int path_bias_extreme
: 1; /**< Did we alert the user about path
41 * bias for this node already? */
42 unsigned int path_bias_disabled
: 1; /**< Have we disabled this node because
43 * of path bias issues? */
44 unsigned int path_bias_use_noticed
: 1; /**< Did we alert the user about path
45 * use bias for this node already? */
46 unsigned int path_bias_use_extreme
: 1; /**< Did we alert the user about path
47 * use bias for this node already? */
49 double circ_attempts
; /**< Number of circuits this guard has "attempted" */
50 double circ_successes
; /**< Number of successfully built circuits using
51 * this guard as first hop. */
52 double successful_circuits_closed
; /**< Number of circuits that carried
53 * streams successfully. */
54 double collapsed_circuits
; /**< Number of fully built circuits that were
55 * remotely closed before any streams were
57 double unusable_circuits
; /**< Number of circuits for which streams were
58 * attempted, but none succeeded. */
59 double timeouts
; /**< Number of 'right-censored' circuit timeouts for this
61 double use_attempts
; /**< Number of circuits we tried to use with streams */
62 double use_successes
; /**< Number of successfully used circuits using
63 * this guard as first hop. */
66 #if defined(ENTRYNODES_PRIVATE)
68 * @name values for entry_guard_t.is_reachable.
70 * See entry_guard_t.is_reachable for more information.
73 #define GUARD_REACHABLE_NO 0
74 #define GUARD_REACHABLE_YES 1
75 #define GUARD_REACHABLE_MAYBE 2
78 /** An entry_guard_t represents our information about a chosen long-term
79 * first hop, known as a "helper" node in the literature. We can't just
80 * use a node_t, since we want to remember these even when we
81 * don't have any directory info. */
82 struct entry_guard_t
{
83 HANDLE_ENTRY(entry_guard
, entry_guard_t
);
85 char nickname
[MAX_HEX_NICKNAME_LEN
+1];
86 char identity
[DIGEST_LEN
];
87 ed25519_public_key_t ed_id
;
90 * @name new guard selection algorithm fields.
92 * Only the new (prop271) algorithm uses these. For a more full
93 * description of the algorithm, see the module documentation for
98 /* == Persistent fields, present for all sampled guards. */
99 /** When was this guard added to the sample? */
100 time_t sampled_on_date
;
101 /** Since what date has this guard been "unlisted"? A guard counts as
102 * unlisted if we have a live consensus that does not include it, or
103 * if we have a live consensus that does not include it as a usable
104 * guard. This field is zero when the guard is listed. */
105 time_t unlisted_since_date
; // can be zero
106 /** What version of Tor added this guard to the sample? */
107 char *sampled_by_version
;
108 /** Is this guard listed right now? If this is set, then
109 * unlisted_since_date should be set too. */
110 unsigned currently_listed
: 1;
112 /* == Persistent fields, for confirmed guards only */
113 /** When was this guard confirmed? (That is, when did we first use it
114 * successfully and decide to keep it?) This field is zero if this is not a
115 * confirmed guard. */
116 time_t confirmed_on_date
; /* 0 if not confirmed */
118 * In what order was this guard confirmed? Guards with lower indices
119 * appear earlier on the confirmed list. If the confirmed list is compacted,
120 * this field corresponds to the index of this guard on the confirmed list.
122 * This field is set to -1 if this guard is not confirmed.
124 int confirmed_idx
; /* -1 if not confirmed; otherwise the order that this
125 * item should occur in the CONFIRMED_GUARDS ordered
129 * Which selection does this guard belong to?
131 char *selection_name
;
133 /** Bridges only: address of the bridge. */
134 tor_addr_port_t
*bridge_addr
;
136 /* ==== Non-persistent fields. */
137 /* == These are used by sampled guards */
138 /** When did we last decide to try using this guard for a circuit? 0 for
139 * "not since we started up." */
140 time_t last_tried_to_connect
;
141 /** How reachable do we consider this guard to be? One of
142 * GUARD_REACHABLE_NO, GUARD_REACHABLE_YES, or GUARD_REACHABLE_MAYBE. */
143 unsigned is_reachable
: 2;
144 /** Boolean: true iff this guard is pending. A pending guard is one
145 * that we have an in-progress circuit through, and which we do not plan
146 * to try again until it either succeeds or fails. Primary guards can
147 * never be pending. */
148 unsigned is_pending
: 1;
149 /** If true, don't write this guard to disk. (Used for bridges with unknown
151 unsigned is_persistent
: 1;
152 /** When did we get the earliest connection failure for this guard?
153 * We clear this field on a successful connect. We do _not_ clear it
154 * when we mark the guard as "MAYBE" reachable.
156 time_t failing_since
;
158 /* == Set inclusion flags. */
159 /** If true, this guard is in the filtered set. The filtered set includes
160 * all sampled guards that our configuration allows us to use. */
161 unsigned is_filtered_guard
: 1;
162 /** If true, this guard is in the usable filtered set. The usable filtered
163 * set includes all filtered guards that are not believed to be
164 * unreachable. (That is, those for which is_reachable is not
165 * GUARD_REACHABLE_NO) */
166 unsigned is_usable_filtered_guard
: 1;
167 unsigned is_primary
:1;
169 /** This string holds any fields that we are maintaining because
170 * we saw them in the state, even if we don't understand them. */
171 char *extra_state_fields
;
173 /** Backpointer to the guard selection that this guard belongs to.
174 * The entry_guard_t must never outlive its guard_selection. */
175 guard_selection_t
*in_selection
;
178 /** Path bias information for this guard. */
183 * Possible rules for a guard selection to follow
185 typedef enum guard_selection_type_t
{
186 /** Infer the type of this selection from its name. */
188 /** Use the normal guard selection algorithm, taking our sample from the
189 * complete list of guards in the consensus. */
191 /** Use the normal guard selection algorithm, taking our sample from the
192 * configured bridges, and allowing it to grow as large as all the configured
195 /** Use the normal guard selection algorithm, taking our sample from the
196 * set of filtered nodes. */
198 } guard_selection_type_t
;
201 * All of the the context for guard selection on a particular client.
203 * We maintain multiple guard selection contexts for a client, depending
204 * aspects on its current configuration -- whether an extremely
205 * restrictive EntryNodes is used, whether UseBridges is enabled, and so
208 * See the module documentation for entrynodes.c for more information
209 * about guard selection algorithms.
211 struct guard_selection_s
{
213 * The name for this guard-selection object. (Must not contain spaces).
218 * What rules does this guard-selection object follow?
220 guard_selection_type_t type
;
223 * A value of 1 means that primary_entry_guards is up-to-date; 0
224 * means we need to recalculate it before using primary_entry_guards
225 * or the is_primary flag on any guard.
227 int primary_guards_up_to_date
;
230 * A list of the sampled entry guards, as entry_guard_t structures.
231 * Not in any particular order. When we 'sample' a guard, we are
232 * noting it as a possible guard to pick in the future. The use of
233 * sampling here prevents us from being forced by an attacker to try
234 * every guard on the network. This list is persistent.
236 smartlist_t
*sampled_entry_guards
;
239 * Ordered list (from highest to lowest priority) of guards that we
240 * have successfully contacted and decided to use. Every member of
241 * this list is a member of sampled_entry_guards. Every member should
242 * have confirmed_on_date set, and have confirmed_idx greater than
243 * any earlier member of the list.
245 * This list is persistent. It is a subset of the elements in
246 * sampled_entry_guards, and its pointers point to elements of
247 * sampled_entry_guards.
249 smartlist_t
*confirmed_entry_guards
;
252 * Ordered list (from highest to lowest priority) of guards that we
253 * are willing to use the most happily. These guards may or may not
254 * yet be confirmed yet. If we can use one of these guards, we are
255 * probably not on a network that is trying to restrict our guard
258 * This list is a subset of the elements in
259 * sampled_entry_guards, and its pointers point to elements of
260 * sampled_entry_guards.
262 smartlist_t
*primary_entry_guards
;
264 /** When did we last successfully build a circuit or use a circuit? */
265 time_t last_time_on_internet
;
267 /** What confirmed_idx value should the next-added member of
268 * confirmed_entry_guards receive? */
269 int next_confirmed_idx
;
273 struct entry_guard_handle_t
;
275 /** Types of restrictions we impose when picking guard nodes */
276 typedef enum guard_restriction_type_t
{
277 /* Don't pick the same guard node as our exit node (or its family) */
279 /* Don't pick dirguards that have previously shown to be outdated */
280 RST_OUTDATED_MD_DIRSERVER
= 1
281 } guard_restriction_type_t
;
284 * A restriction to remember which entry guards are off-limits for a given
287 * Note: This mechanism is NOT for recording which guards are never to be
288 * used: only which guards cannot be used on <em>one particular circuit</em>.
290 struct entry_guard_restriction_t
{
291 /* What type of restriction are we imposing? */
292 guard_restriction_type_t type
;
294 /* In case of restriction type RST_EXIT_NODE, the guard's RSA identity
295 * digest must not equal this; and it must not be in the same family as any
296 * node with this digest. */
297 uint8_t exclude_id
[DIGEST_LEN
];
301 * Per-circuit state to track whether we'll be able to use the circuit.
303 struct circuit_guard_state_t
{
304 /** Handle to the entry guard object for this circuit. */
305 struct entry_guard_handle_t
*guard
;
306 /** The time at which <b>state</b> last changed. */
308 /** One of GUARD_CIRC_STATE_* */
312 * A set of restrictions that were placed on this guard when we selected it
313 * for this particular circuit. We need to remember the restrictions here,
314 * since any guard that breaks these restrictions will not block this
315 * circuit from becoming COMPLETE.
317 entry_guard_restriction_t
*restrictions
;
319 #endif /* defined(ENTRYNODES_PRIVATE) */
321 /* Common entry points for old and new guard code */
322 int guards_update_all(void);
323 const node_t
*guards_choose_guard(cpath_build_state_t
*state
,
324 circuit_guard_state_t
**guard_state_out
);
325 const node_t
*guards_choose_dirguard(uint8_t dir_purpose
,
326 circuit_guard_state_t
**guard_state_out
);
329 /* XXXX NM I would prefer that all of this stuff be private to
331 entry_guard_t
*entry_guard_get_by_id_digest_for_guard_selection(
332 guard_selection_t
*gs
, const char *digest
);
333 entry_guard_t
*entry_guard_get_by_id_digest(const char *digest
);
335 circuit_guard_state_t
*
336 get_guard_state_for_bridge_desc_fetch(const char *digest
);
338 void entry_guards_changed_for_guard_selection(guard_selection_t
*gs
);
339 void entry_guards_changed(void);
340 guard_selection_t
* get_guard_selection_info(void);
341 int num_live_entry_guards_for_guard_selection(
342 guard_selection_t
*gs
,
344 int num_live_entry_guards(int for_directory
);
347 const node_t
*entry_guard_find_node(const entry_guard_t
*guard
);
348 const char *entry_guard_get_rsa_id_digest(const entry_guard_t
*guard
);
349 const char *entry_guard_describe(const entry_guard_t
*guard
);
350 guard_pathbias_t
*entry_guard_get_pathbias_state(entry_guard_t
*guard
);
352 /** Enum to specify how we're going to use a given guard, when we're picking
353 * one for immediate use. */
355 GUARD_USAGE_TRAFFIC
= 0,
356 GUARD_USAGE_DIRGUARD
= 1
359 void circuit_guard_state_free(circuit_guard_state_t
*state
);
360 int entry_guard_pick_for_circuit(guard_selection_t
*gs
,
362 entry_guard_restriction_t
*rst
,
363 const node_t
**chosen_node_out
,
364 circuit_guard_state_t
**guard_state_out
);
366 /* We just connected to an entry guard. What should we do with the circuit? */
368 GUARD_USABLE_NEVER
= -1, /* Never use the circuit */
369 GUARD_MAYBE_USABLE_LATER
= 0, /* Keep it. We might use it in the future */
370 GUARD_USABLE_NOW
= 1, /* Use it right now */
373 guard_usable_t
entry_guard_succeeded(circuit_guard_state_t
**guard_state_p
);
374 void entry_guard_failed(circuit_guard_state_t
**guard_state_p
);
375 void entry_guard_cancel(circuit_guard_state_t
**guard_state_p
);
376 void entry_guard_chan_failed(channel_t
*chan
);
377 int entry_guards_update_all(guard_selection_t
*gs
);
378 int entry_guards_upgrade_waiting_circuits(guard_selection_t
*gs
,
379 const smartlist_t
*all_circuits
,
380 smartlist_t
*newly_complete_out
);
381 int entry_guard_state_should_expire(circuit_guard_state_t
*guard_state
);
382 void entry_guards_note_internet_connectivity(guard_selection_t
*gs
);
384 int update_guard_selection_choice(const or_options_t
*options
);
386 MOCK_DECL(int,num_bridges_usable
,(void));
388 #ifdef ENTRYNODES_PRIVATE
390 * @name Default values for the parameters for the new (prop271) entry guard
395 * We never let our sampled guard set grow larger than this percentage
396 * of the guards on the network.
398 #define DFLT_MAX_SAMPLE_THRESHOLD_PERCENT 20
400 * We never let our sampled guard set grow larger than this number of
403 #define DFLT_MAX_SAMPLE_SIZE 60
405 * We always try to make our sample contain at least this many guards.
407 #define DFLT_MIN_FILTERED_SAMPLE_SIZE 20
409 * If a guard is unlisted for this many days in a row, we remove it.
411 #define DFLT_REMOVE_UNLISTED_GUARDS_AFTER_DAYS 20
413 * We remove unconfirmed guards from the sample after this many days,
414 * regardless of whether they are listed or unlisted.
416 #define DFLT_GUARD_LIFETIME_DAYS 120
418 * We remove confirmed guards from the sample if they were sampled
419 * GUARD_LIFETIME_DAYS ago and confirmed this many days ago.
421 #define DFLT_GUARD_CONFIRMED_MIN_LIFETIME_DAYS 60
423 * How many guards do we try to keep on our primary guard list?
425 #define DFLT_N_PRIMARY_GUARDS 3
427 * Of the live guards on the primary guard list, how many do we consider when
428 * choosing a guard to use?
430 #define DFLT_N_PRIMARY_GUARDS_TO_USE 1
432 * As DFLT_N_PRIMARY_GUARDS, but for choosing which directory guard to use.
434 #define DFLT_N_PRIMARY_DIR_GUARDS_TO_USE 3
436 * If we haven't successfully built or used a circuit in this long, then
437 * consider that the internet is probably down.
439 #define DFLT_INTERNET_LIKELY_DOWN_INTERVAL (10*60)
441 * If we're trying to connect to a nonprimary guard for at least this
442 * many seconds, and we haven't gotten the connection to work, we will treat
443 * lower-priority guards as usable.
445 #define DFLT_NONPRIMARY_GUARD_CONNECT_TIMEOUT 15
447 * If a circuit has been sitting around in 'waiting for better guard' state
448 * for at least this long, we'll expire it.
450 #define DFLT_NONPRIMARY_GUARD_IDLE_TIMEOUT (10*60)
452 * If our configuration retains fewer than this fraction of guards from the
453 * torrc, we are in a restricted setting.
455 #define DFLT_MEANINGFUL_RESTRICTION_PERCENT 20
457 * If our configuration retains fewer than this fraction of guards from the
458 * torrc, we are in an extremely restricted setting, and should warn.
460 #define DFLT_EXTREME_RESTRICTION_PERCENT 1
463 STATIC
double get_max_sample_threshold(void);
464 STATIC
int get_max_sample_size_absolute(void);
465 STATIC
int get_min_filtered_sample_size(void);
466 STATIC
int get_remove_unlisted_guards_after_days(void);
467 STATIC
int get_guard_lifetime(void);
468 STATIC
int get_guard_confirmed_min_lifetime(void);
469 STATIC
int get_n_primary_guards(void);
470 STATIC
int get_n_primary_guards_to_use(guard_usage_t usage
);
471 STATIC
int get_internet_likely_down_interval(void);
472 STATIC
int get_nonprimary_guard_connect_timeout(void);
473 STATIC
int get_nonprimary_guard_idle_timeout(void);
474 STATIC
double get_meaningful_restriction_threshold(void);
475 STATIC
double get_extreme_restriction_threshold(void);
477 HANDLE_DECL(entry_guard
, entry_guard_t
, STATIC
)
478 STATIC guard_selection_type_t
guard_selection_infer_type(
479 guard_selection_type_t type_in
,
481 STATIC guard_selection_t
*guard_selection_new(const char *name
,
482 guard_selection_type_t type
);
483 STATIC guard_selection_t
*get_guard_selection_by_name(
484 const char *name
, guard_selection_type_t type
, int create_if_absent
);
485 STATIC
void guard_selection_free(guard_selection_t
*gs
);
486 MOCK_DECL(STATIC
int, entry_guard_is_listed
,
487 (guard_selection_t
*gs
, const entry_guard_t
*guard
));
488 STATIC
const char *choose_guard_selection(const or_options_t
*options
,
489 const networkstatus_t
*ns
,
490 const guard_selection_t
*old_selection
,
491 guard_selection_type_t
*type_out
);
492 STATIC entry_guard_t
*get_sampled_guard_with_id(guard_selection_t
*gs
,
493 const uint8_t *rsa_id
);
495 MOCK_DECL(STATIC
time_t, randomize_time
, (time_t now
, time_t max_backdate
));
497 STATIC entry_guard_t
*entry_guard_add_to_sample(guard_selection_t
*gs
,
499 STATIC entry_guard_t
*entry_guards_expand_sample(guard_selection_t
*gs
);
500 STATIC
char *entry_guard_encode_for_state(entry_guard_t
*guard
);
501 STATIC entry_guard_t
*entry_guard_parse_from_state(const char *s
);
502 STATIC
void entry_guard_free(entry_guard_t
*e
);
503 STATIC
void entry_guards_update_filtered_sets(guard_selection_t
*gs
);
504 STATIC
int entry_guards_all_primary_guards_are_down(guard_selection_t
*gs
);
506 * @name Flags for sample_reachable_filtered_entry_guards()
509 #define SAMPLE_EXCLUDE_CONFIRMED (1u<<0)
510 #define SAMPLE_EXCLUDE_PRIMARY (1u<<1)
511 #define SAMPLE_EXCLUDE_PENDING (1u<<2)
512 #define SAMPLE_NO_UPDATE_PRIMARY (1u<<3)
513 #define SAMPLE_EXCLUDE_NO_DESCRIPTOR (1u<<4)
515 STATIC entry_guard_t
*sample_reachable_filtered_entry_guards(
516 guard_selection_t
*gs
,
517 const entry_guard_restriction_t
*rst
,
519 STATIC
void entry_guard_consider_retry(entry_guard_t
*guard
);
520 STATIC
void make_guard_confirmed(guard_selection_t
*gs
, entry_guard_t
*guard
);
521 STATIC
void entry_guards_update_confirmed(guard_selection_t
*gs
);
522 STATIC
void entry_guards_update_primary(guard_selection_t
*gs
);
523 STATIC
int num_reachable_filtered_guards(const guard_selection_t
*gs
,
524 const entry_guard_restriction_t
*rst
);
525 STATIC
void sampled_guards_update_from_consensus(guard_selection_t
*gs
);
527 * @name Possible guard-states for a circuit.
530 /** State for a circuit that can (so far as the guard subsystem is
531 * concerned) be used for actual traffic as soon as it is successfully
533 #define GUARD_CIRC_STATE_USABLE_ON_COMPLETION 1
534 /** State for an non-open circuit that we shouldn't use for actual
535 * traffic, when it completes, unless other circuits to preferable
537 #define GUARD_CIRC_STATE_USABLE_IF_NO_BETTER_GUARD 2
538 /** State for an open circuit that we shouldn't use for actual traffic
539 * unless other circuits to preferable guards fail. */
540 #define GUARD_CIRC_STATE_WAITING_FOR_BETTER_GUARD 3
541 /** State for a circuit that can (so far as the guard subsystem is
542 * concerned) be used for actual traffic. */
543 #define GUARD_CIRC_STATE_COMPLETE 4
544 /** State for a circuit that is unusable, and will not become usable. */
545 #define GUARD_CIRC_STATE_DEAD 5
547 STATIC
void entry_guards_note_guard_failure(guard_selection_t
*gs
,
548 entry_guard_t
*guard
);
549 STATIC entry_guard_t
*select_entry_guard_for_circuit(guard_selection_t
*gs
,
551 const entry_guard_restriction_t
*rst
,
552 unsigned *state_out
);
553 STATIC
void mark_primary_guards_maybe_reachable(guard_selection_t
*gs
);
554 STATIC
unsigned entry_guards_note_guard_success(guard_selection_t
*gs
,
555 entry_guard_t
*guard
,
557 STATIC
int entry_guard_has_higher_priority(entry_guard_t
*a
, entry_guard_t
*b
);
558 STATIC
char *getinfo_helper_format_single_entry_guard(const entry_guard_t
*e
);
560 STATIC entry_guard_restriction_t
*guard_create_exit_restriction(
561 const uint8_t *exit_id
);
563 STATIC entry_guard_restriction_t
*guard_create_dirserver_md_restriction(void);
565 STATIC
void entry_guard_restriction_free(entry_guard_restriction_t
*rst
);
567 #endif /* defined(ENTRYNODES_PRIVATE) */
569 void remove_all_entry_guards_for_guard_selection(guard_selection_t
*gs
);
570 void remove_all_entry_guards(void);
572 struct bridge_info_t
;
573 void entry_guard_learned_bridge_identity(const tor_addr_port_t
*addrport
,
574 const uint8_t *rsa_id_digest
);
576 int entry_list_is_constrained(const or_options_t
*options
);
577 int guards_retry_optimistic(const or_options_t
*options
);
578 int entry_guards_parse_state_for_guard_selection(
579 guard_selection_t
*gs
, or_state_t
*state
, int set
, char **msg
);
580 int entry_guards_parse_state(or_state_t
*state
, int set
, char **msg
);
581 void entry_guards_update_state(or_state_t
*state
);
582 int getinfo_helper_entry_guards(control_connection_t
*conn
,
583 const char *question
, char **answer
,
584 const char **errmsg
);
586 int entries_known_but_down(const or_options_t
*options
);
587 void entries_retry_all(const or_options_t
*options
);
589 char *entry_guards_get_err_str_if_dir_info_missing(int using_mds
,
590 int num_present
, int num_usable
);
591 char *guard_selection_get_err_str_if_dir_info_missing(guard_selection_t
*gs
,
593 int num_present
, int num_usable
);
595 void entry_guards_free_all(void);
597 double pathbias_get_close_success_count(entry_guard_t
*guard
);
598 double pathbias_get_use_success_count(entry_guard_t
*guard
);
600 /** Contains the bandwidth of a relay as a guard and as a non-guard
601 * after the guardfraction has been considered. */
602 typedef struct guardfraction_bandwidth_t
{
603 /** Bandwidth as a guard after guardfraction has been considered. */
605 /** Bandwidth as a non-guard after guardfraction has been considered. */
607 } guardfraction_bandwidth_t
;
609 int should_apply_guardfraction(const networkstatus_t
*ns
);
612 guard_get_guardfraction_bandwidth(guardfraction_bandwidth_t
*guardfraction_bw
,
614 uint32_t guardfraction_percentage
);
616 #endif /* !defined(TOR_ENTRYNODES_H) */