Code to choose nodes randomly based on restrictions and weighted probabilities. More...

#include "core/or/or.h"
#include "app/config/config.h"
#include "core/mainloop/connection.h"
#include "core/or/policies.h"
#include "core/or/reasons.h"
#include "feature/client/entrynodes.h"
#include "feature/dirclient/dirclient.h"
#include "feature/dirclient/dirclient_modes.h"
#include "feature/dircommon/directory.h"
#include "feature/nodelist/describe.h"
#include "feature/nodelist/dirlist.h"
#include "feature/nodelist/microdesc.h"
#include "feature/nodelist/networkstatus.h"
#include "feature/nodelist/node_select.h"
#include "feature/nodelist/nodelist.h"
#include "feature/nodelist/routerlist.h"
#include "feature/nodelist/routerset.h"
#include "feature/relay/router.h"
#include "feature/relay/routermode.h"
#include "lib/container/bitarray.h"
#include "lib/crypt_ops/crypto_rand.h"
#include "lib/math/fp.h"
#include "feature/dirclient/dir_server_st.h"
#include "feature/nodelist/networkstatus_st.h"
#include "feature/nodelist/node_st.h"
#include "feature/nodelist/routerinfo_st.h"
#include "feature/nodelist/routerstatus_st.h"

Macros
#define	NODE_SELECT_PRIVATE

#define	RETRY_ALTERNATE_IP_VERSION(retry_label)

#define	RETRY_WITHOUT_EXCLUDE(retry_label)

#define	SKIP_MISSING_TRUSTED_EXTRAINFO(type, identity)

#define	LOG_FALSE_POSITIVES_DURING_BOOTSTRAP 0

#define	BRIDGE_MIN_BELIEVABLE_BANDWIDTH 20000 /* 20 kB/sec */

#define	BRIDGE_MAX_BELIEVABLE_BANDWIDTH 100000 /* 100 kB/sec */

Functions
static int	compute_weighted_bandwidths (const smartlist_t sl, bandwidth_weight_rule_t rule, double bandwidths_out, double total_bandwidth_out)

static const routerstatus_t *	router_pick_trusteddirserver_impl (const smartlist_t sourcelist, dirinfo_type_t auth, int flags, int n_busy_out)

static const routerstatus_t *	router_pick_dirserver_generic (smartlist_t *sourcelist, dirinfo_type_t type, int flags)

const routerstatus_t *	router_pick_directory_server (dirinfo_type_t type, int flags)

static void	router_picked_poor_directory_log (const routerstatus_t *rs)

STATIC int	router_is_already_dir_fetching (const tor_addr_port_t *ap, int serverdesc, int microdesc)

static int	router_is_already_dir_fetching_ (const tor_addr_t ipv4_addr, const tor_addr_t ipv6_addr, uint16_t dir_port, int serverdesc, int microdesc)

STATIC const routerstatus_t *	router_pick_directory_server_impl (dirinfo_type_t type, int flags, int *n_busy_out)

STATIC void	scale_array_elements_to_u64 (uint64_t entries_out, const double entries_in, int n_entries, uint64_t *total_out)

STATIC int	choose_array_element_by_weight (const uint64_t *entries, int n_entries)

static int32_t	kb_to_bytes (uint32_t bw)

static const node_t *	smartlist_choose_node_by_bandwidth_weights (const smartlist_t *sl, bandwidth_weight_rule_t rule)

static uint32_t	bridge_get_advertised_bandwidth_bounded (routerinfo_t *router)

static void	log_buggy_rs_source (const routerstatus_t *rs)

double	frac_nodes_with_descriptors (const smartlist_t *sl, bandwidth_weight_rule_t rule, int for_direct_conn)

const node_t *	node_sl_choose_by_bandwidth (const smartlist_t *sl, bandwidth_weight_rule_t rule)

static void	routerlist_add_node_and_family (smartlist_t sl, const routerinfo_t router)

static void	nodelist_subtract (smartlist_t sl, const smartlist_t excluded)

static const node_t *	router_choose_random_node_helper (smartlist_t excludednodes, routerset_t excludedset, router_crn_flags_t flags, bandwidth_weight_rule_t rule)

const node_t *	router_choose_random_node (smartlist_t excludedsmartlist, routerset_t excludedset, router_crn_flags_t flags)

const routerstatus_t *	router_pick_trusteddirserver (dirinfo_type_t type, int flags)

const routerstatus_t *	router_pick_fallback_dirserver (dirinfo_type_t type, int flags)

static const dir_server_t *	dirserver_choose_by_weight (const smartlist_t *servers, double authority_weight)

Detailed Description

Code to choose nodes randomly based on restrictions and weighted probabilities.

Definition in file node_select.c.

Macro Definition Documentation

◆ BRIDGE_MIN_BELIEVABLE_BANDWIDTH

#define BRIDGE_MIN_BELIEVABLE_BANDWIDTH 20000 /* 20 kB/sec */

When weighting bridges, enforce these values as lower and upper bound for believable bandwidth, because there is no way for us to verify a bridge's bandwidth currently.

Definition at line 531 of file node_select.c.

◆ RETRY_ALTERNATE_IP_VERSION

#define RETRY_ALTERNATE_IP_VERSION ( retry_label )

Value:

  STMT_BEGIN                                                                  \
    if (result == NULL && try_ip_pref && options->ClientUseIPv4               \
        && reachable_addr_use_ipv6(options) && !server_mode(options)        \
        && !n_busy) {                                                         \
      n_excluded = 0;                                                         \
      n_busy = 0;                                                             \
      try_ip_pref = 0;                                                        \
      goto retry_label;                                                       \
    }                                                                         \
  STMT_END

Definition at line 141 of file node_select.c.

◆ RETRY_WITHOUT_EXCLUDE

#define RETRY_WITHOUT_EXCLUDE ( retry_label )

Value:

  STMT_BEGIN                                                                  \
    if (result == NULL && try_excluding && !options->StrictNodes              \
        && n_excluded && !n_busy) {                                           \
      try_excluding = 0;                                                      \
      n_excluded = 0;                                                         \
      n_busy = 0;                                                             \
      try_ip_pref = 1;                                                        \
      goto retry_label;                                                       \
    }                                                                         \
  STMT_END

Definition at line 159 of file node_select.c.

◆ SKIP_MISSING_TRUSTED_EXTRAINFO

#define SKIP_MISSING_TRUSTED_EXTRAINFO	(	type,
		identity
	)

Value:

  STMT_BEGIN                                                                  \
    int is_trusted_extrainfo = router_digest_is_trusted_dir_type(             \
                               (identity), EXTRAINFO_DIRINFO);                \
    if (((type) & EXTRAINFO_DIRINFO) &&                                       \
        !router_supports_extrainfo((identity), is_trusted_extrainfo))         \
      continue;                                                               \
  STMT_END

Definition at line 177 of file node_select.c.

Function Documentation

◆ bridge_get_advertised_bandwidth_bounded()

static uint32_t bridge_get_advertised_bandwidth_bounded ( routerinfo_t * router )

static

Return the smaller of the router's configured BandwidthRate and its advertised capacity, making sure to stay within the interval between bridge-min-believe-bw and bridge-max-believe-bw.

Definition at line 539 of file node_select.c.

◆ choose_array_element_by_weight()

STATIC int choose_array_element_by_weight	(	const uint64_t *	entries,
		int	n_entries
	)

Pick a random element of n_entries-element array entries, choosing each element with a probability proportional to its (uint64_t) value, and return the index of that element. If all elements are 0, choose an index at random. Return -1 on error.

Definition at line 460 of file node_select.c.

◆ compute_weighted_bandwidths()

static int compute_weighted_bandwidths	(	const smartlist_t *	sl,
		bandwidth_weight_rule_t	rule,
		double **	bandwidths_out,
		double *	total_bandwidth_out
	)

static

Given a list of routers and a weighting rule as in smartlist_choose_node_by_bandwidth_weights, compute weighted bandwidth values for each node and store them in a freshly allocated *bandwidths_out of the same length as sl, and holding results as doubles. If total_bandwidth_out is non-NULL, set it to the total of all the bandwidths. Return 0 on success, -1 on failure.

Definition at line 604 of file node_select.c.

Referenced by smartlist_choose_node_by_bandwidth_weights().

◆ dirserver_choose_by_weight()

static const dir_server_t* dirserver_choose_by_weight	(	const smartlist_t *	servers,
		double	authority_weight
	)

static

Pick a random element from a list of dir_server_t, weighting by their weight field.

Definition at line 1061 of file node_select.c.

◆ frac_nodes_with_descriptors()

double frac_nodes_with_descriptors	(	const smartlist_t *	sl,
		bandwidth_weight_rule_t	rule,
		int	for_direct_conn
	)

For all nodes in sl, return the fraction of those nodes, weighted by their weighted bandwidths with rule rule, for which we have descriptors.

If for_direct_connect is true, we intend to connect to the node directly, as the first hop of a circuit; otherwise, we intend to connect to it indirectly, or use it as if we were connecting to it indirectly.

Definition at line 821 of file node_select.c.

◆ kb_to_bytes()

static int32_t kb_to_bytes ( uint32_t bw )

inlinestatic

Return bw*1000, unless bw*1000 would overflow, in which case return INT32_MAX.

Definition at line 486 of file node_select.c.

◆ log_buggy_rs_source()

static void log_buggy_rs_source ( const routerstatus_t * rs )

static

We have found an instance of bug 32868: log our best guess about where the routerstatus was found.

Definition at line 556 of file node_select.c.

◆ node_sl_choose_by_bandwidth()

const node_t* node_sl_choose_by_bandwidth	(	const smartlist_t *	sl,
		bandwidth_weight_rule_t	rule
	)

Choose a random element of status list sl, weighted by the advertised bandwidth of each node

Definition at line 856 of file node_select.c.

◆ nodelist_subtract()

static void nodelist_subtract	(	smartlist_t *	sl,
		const smartlist_t *	excluded
	)

static

Remove every node_t that appears in excluded from sl.

Behaves like smartlist_subtract, but uses nodelist_idx values to deliver linear performance when smartlist_subtract would be quadratic.

Definition at line 890 of file node_select.c.

◆ router_choose_random_node()

const node_t* router_choose_random_node	(	smartlist_t *	excludedsmartlist,
		routerset_t *	excludedset,
		router_crn_flags_t	flags
	)

Return a random running node from the nodelist. Never pick a node that is in excludedsmartlist, or which matches excludedset, even if they are the only nodes available.

flags is a set of CRN_* flags, see router_add_running_nodes_to_smartlist() for details.

Definition at line 979 of file node_select.c.

◆ router_pick_directory_server()

const routerstatus_t* router_pick_directory_server	(	dirinfo_type_t	type,
		int	flags
	)

Try to find a running dirserver that supports operations of type.

If there are no running dirservers in our routerlist and the PDS_RETRY_IF_NO_SERVERS flag is set, set all the fallback ones (including authorities) as running again, and pick one.

If the PDS_IGNORE_FASCISTFIREWALL flag is set, then include dirservers that we can't reach.

If the PDS_ALLOW_SELF flag is not set, then don't include ourself (if we're a dirserver).

Don't pick a fallback directory mirror if any non-fallback is viable; (the fallback directory mirrors include the authorities) try to avoid using servers that have returned 503 recently.

Definition at line 72 of file node_select.c.

◆ router_pick_directory_server_impl()

STATIC const routerstatus_t* router_pick_directory_server_impl	(	dirinfo_type_t	type,
		int	flags,
		int *	n_busy_out
	)

Pick a random running valid directory server/mirror from our routerlist. Arguments are as for router_pick_directory_server(), except:

If n_busy_out is provided, set *n_busy_out to the number of directories that we excluded for no other reason than PDS_NO_EXISTING_SERVERDESC_FETCH or PDS_NO_EXISTING_MICRODESC_FETCH.

Definition at line 297 of file node_select.c.

◆ router_pick_dirserver_generic()

const routerstatus_t * router_pick_dirserver_generic	(	smartlist_t *	sourcelist,
		dirinfo_type_t	type,
		int	flags
	)

static

Try to find a running fallback directory. Flags are as for router_pick_directory_server.

Definition at line 104 of file node_select.c.

◆ router_pick_fallback_dirserver()

const routerstatus_t* router_pick_fallback_dirserver	(	dirinfo_type_t	type,
		int	flags
	)

Try to find a running fallback directory. Flags are as for router_pick_directory_server.

Definition at line 1051 of file node_select.c.

◆ router_pick_trusteddirserver()

const routerstatus_t* router_pick_trusteddirserver	(	dirinfo_type_t	type,
		int	flags
	)

Try to find a running directory authority. Flags are as for router_pick_directory_server.

Definition at line 1040 of file node_select.c.

◆ router_pick_trusteddirserver_impl()

static const routerstatus_t * router_pick_trusteddirserver_impl	(	const smartlist_t *	sourcelist,
		dirinfo_type_t	type,
		int	flags,
		int *	n_busy_out
	)

static

Choose randomly from among the dir_server_ts in sourcelist that are up. Flags are as for router_pick_directory_server_impl().

Definition at line 1089 of file node_select.c.

◆ routerlist_add_node_and_family()

static void routerlist_add_node_and_family	(	smartlist_t *	sl,
		const routerinfo_t *	router
	)

static

Given a router, add every node_t in its family (including the node itself!) to sl.

Note the type mismatch: This function takes a routerinfo, but adds nodes to the smartlist!

Definition at line 869 of file node_select.c.

◆ scale_array_elements_to_u64()

STATIC void scale_array_elements_to_u64	(	uint64_t *	entries_out,
		const double *	entries_in,
		int	n_entries,
		uint64_t *	total_out
	)

Given an array of double/uint64_t unions that are currently being used as doubles, convert them to uint64_t, and try to scale them linearly so as to much of the range of uint64_t. If total_out is provided, set it to the sum of all elements in the array before scaling.

Definition at line 431 of file node_select.c.

◆ smartlist_choose_node_by_bandwidth_weights()

static const node_t* smartlist_choose_node_by_bandwidth_weights	(	const smartlist_t *	sl,
		bandwidth_weight_rule_t	rule
	)

static

Helper function: choose a random element of smartlist sl of nodes, weighted by the advertised bandwidth of each element using the consensus bandwidth weights.

If rule==WEIGHT_FOR_EXIT. we're picking an exit node: consider all nodes' bandwidth equally regardless of their Exit status, since there may be some in the list because they exit to obscure ports. If rule==NO_WEIGHTING, we're picking a non-exit node: weight exit-node's bandwidth less depending on the smallness of the fraction of Exit-to-total bandwidth. If rule==WEIGHT_FOR_GUARD, we're picking a guard node: consider all guard's bandwidth equally. Otherwise, weight guards proportionally less.

Definition at line 506 of file node_select.c.

Referenced by node_sl_choose_by_bandwidth().

Macros

Functions

Detailed Description

Macro Definition Documentation

◆ BRIDGE_MIN_BELIEVABLE_BANDWIDTH

◆ RETRY_ALTERNATE_IP_VERSION

◆ RETRY_WITHOUT_EXCLUDE

◆ SKIP_MISSING_TRUSTED_EXTRAINFO

Function Documentation

◆ bridge_get_advertised_bandwidth_bounded()

◆ choose_array_element_by_weight()

◆ compute_weighted_bandwidths()

◆ dirserver_choose_by_weight()

◆ frac_nodes_with_descriptors()

◆ kb_to_bytes()

◆ log_buggy_rs_source()

◆ node_sl_choose_by_bandwidth()

◆ nodelist_subtract()

◆ router_choose_random_node()

◆ router_pick_directory_server()

◆ router_pick_directory_server_impl()

◆ router_pick_dirserver_generic()

◆ router_pick_fallback_dirserver()

◆ router_pick_trusteddirserver()

◆ router_pick_trusteddirserver_impl()

◆ routerlist_add_node_and_family()

◆ scale_array_elements_to_u64()

◆ smartlist_choose_node_by_bandwidth_weights()