node_select.c File Reference

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"

Go to the source code of this file.

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_MAX_BELIEVABLE_BANDWIDTH

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

Definition at line 532 of file node_select.c.

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.

LOG_FALSE_POSITIVES_DURING_BOOTSTRAP

#define LOG_FALSE_POSITIVES_DURING_BOOTSTRAP   0

Definition at line 187 of file node_select.c.

NODE_SELECT_PRIVATE

#define NODE_SELECT_PRIVATE

Definition at line 13 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_choose_random_node_helper()

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  )

static

Definition at line 941 of file node_select.c.

router_is_already_dir_fetching()

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

Definition at line 240 of file node_select.c.

router_is_already_dir_fetching_()

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

Definition at line 271 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.

router_picked_poor_directory_log()

static void router_picked_poor_directory_log ( const routerstatus_t *  rs )

static

Definition at line 192 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().