Tor  0.4.7.0-alpha-dev
Macros | Functions
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_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_ (const tor_addr_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)
 
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_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)
 
static const node_trouter_choose_random_node_helper (smartlist_t *excludednodes, routerset_t *excludedset, router_crn_flags_t flags, bandwidth_weight_rule_t rule)
 
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

◆ 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
int reachable_addr_use_ipv6(const or_options_t *options)
Definition: policies.c:448
int server_mode(const or_options_t *options)
Definition: routermode.c:34

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
int router_supports_extrainfo(const char *identity_digest, int is_authority)
Definition: dirclient.c:175
int router_digest_is_trusted_dir_type(const char *digest, dirinfo_type_t type)
Definition: dirlist.c:256
@ EXTRAINFO_DIRINFO
Definition: or.h:792

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().