Macros | Functions
node_select.c File Reference
#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/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.


#define RETRY_ALTERNATE_IP_VERSION(retry_label)
#define RETRY_WITHOUT_EXCLUDE(retry_label)
#define SKIP_MISSING_TRUSTED_EXTRAINFO(type, identity)
#define BRIDGE_MIN_BELIEVABLE_BANDWIDTH   20000 /* 20 kB/sec */
#define BRIDGE_MAX_BELIEVABLE_BANDWIDTH   100000 /* 100 kB/sec */


static int compute_weighted_bandwidths (const smartlist_t *sl, bandwidth_weight_rule_t rule, double **bandwidths_out, double *total_bandwidth_out)
static const routerstatus_trouter_pick_trusteddirserver_impl (const smartlist_t *sourcelist, dirinfo_type_t auth, int flags, int *n_busy_out)
static const routerstatus_trouter_pick_dirserver_generic (smartlist_t *sourcelist, dirinfo_type_t type, int flags)
const routerstatus_trouter_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_ (uint32_t ipv4_addr, const tor_addr_t *ipv6_addr, uint16_t dir_port, int serverdesc, int microdesc)
STATIC const routerstatus_trouter_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_tsmartlist_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)
double frac_nodes_with_descriptors (const smartlist_t *sl, bandwidth_weight_rule_t rule, int for_direct_conn)
const node_tnode_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)
const node_trouter_choose_random_node (smartlist_t *excludedsmartlist, routerset_t *excludedset, router_crn_flags_t flags)
const routerstatus_trouter_pick_trusteddirserver (dirinfo_type_t type, int flags)
const routerstatus_trouter_pick_fallback_dirserver (dirinfo_type_t type, int flags)
static const dir_server_tdirserver_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


#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 524 of file node_select.c.


#define RETRY_ALTERNATE_IP_VERSION (   retry_label)
if (result == NULL && try_ip_pref && options->ClientUseIPv4 \
&& fascist_firewall_use_ipv6(options) && !server_mode(options) \
&& !n_busy) { \
n_excluded = 0; \
n_busy = 0; \
try_ip_pref = 0; \
goto retry_label; \
} \
int fascist_firewall_use_ipv6(const or_options_t *options)
Definition: policies.c:459

Definition at line 140 of file node_select.c.


#define RETRY_WITHOUT_EXCLUDE (   retry_label)
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; \
} \

Definition at line 158 of file node_select.c.


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; \
int router_supports_extrainfo(const char *identity_digest, int is_authority)
Definition: dirclient.c:174
int router_digest_is_trusted_dir_type(const char *digest, dirinfo_type_t type)
Definition: dirlist.c:208

Definition at line 176 of file node_select.c.

Function Documentation

◆ bridge_get_advertised_bandwidth_bounded()

static uint32_t bridge_get_advertised_bandwidth_bounded ( routerinfo_t router)

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 532 of file node_select.c.

References routerinfo_t::bandwidthcapacity, and routerinfo_t::bandwidthrate.

◆ 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 453 of file node_select.c.

References crypto_rand_int(), crypto_rand_uint64(), select_array_member_cumulative_timei(), and tor_assert().

◆ compute_weighted_bandwidths()

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

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 552 of file node_select.c.

References tor_assert().

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 

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

Definition at line 1016 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 768 of file node_select.c.

◆ kb_to_bytes()

static int32_t kb_to_bytes ( uint32_t  bw)

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

Definition at line 479 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 803 of file node_select.c.

References smartlist_choose_node_by_bandwidth_weights().

◆ nodelist_subtract()

static void nodelist_subtract ( smartlist_t sl,
const smartlist_t excluded 

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 837 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. If CRN_NEED_UPTIME is set in flags and any router has more than a minimum uptime, return one of those. If CRN_NEED_CAPACITY is set in flags, weight your choice by the advertised capacity of each router. If CRN_NEED_GUARD is set in flags, consider only Guard routers. If CRN_WEIGHT_AS_EXIT is set in flags, we weight bandwidths as if picking an exit node, otherwise we weight bandwidths for picking a relay node (that is, possibly discounting exit nodes). If CRN_NEED_DESC is set in flags, we only consider nodes that have a routerinfo or microdescriptor – that is, enough info to be used to build a circuit. If CRN_PREF_ADDR is set in flags, we only consider nodes that have an address that is preferred by the ClientPreferIPv6ORPort setting (regardless of this flag, we exclude nodes that aren't allowed by the firewall, including ClientUseIPv4 0 and fascist_firewall_use_ipv6() == 0).

Definition at line 903 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 71 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 294 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 

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

Definition at line 103 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 1006 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 995 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 

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 1044 of file node_select.c.

◆ routerlist_add_node_and_family()

static void routerlist_add_node_and_family ( smartlist_t sl,
const routerinfo_t router 

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 816 of file node_select.c.

References DIGEST_LEN, node_t::identity, signed_descriptor_t::identity_digest, and nodelist_add_node_and_family().

◆ 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 424 of file node_select.c.

References tor_llround().

◆ 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 

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 499 of file node_select.c.

References compute_weighted_bandwidths().

Referenced by node_sl_choose_by_bandwidth().