Tor  0.4.5.0-alpha-dev
node_select.c
Go to the documentation of this file.
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-2020, The Tor Project, Inc. */
5 /* See LICENSE for licensing information */
6 
7 /**
8  * \file node_select.c
9  * \brief Code to choose nodes randomly based on restrictions and
10  * weighted probabilities.
11  **/
12 
13 #define NODE_SELECT_PRIVATE
14 #include "core/or/or.h"
15 
16 #include "app/config/config.h"
18 #include "core/or/policies.h"
19 #include "core/or/reasons.h"
32 #include "feature/relay/router.h"
34 #include "lib/container/bitarray.h"
36 #include "lib/math/fp.h"
37 
43 
44 static int compute_weighted_bandwidths(const smartlist_t *sl,
46  double **bandwidths_out,
47  double *total_bandwidth_out);
49  const smartlist_t *sourcelist, dirinfo_type_t auth,
50  int flags, int *n_busy_out);
52  smartlist_t *sourcelist,
53  dirinfo_type_t type, int flags);
54 
55 /** Try to find a running dirserver that supports operations of <b>type</b>.
56  *
57  * If there are no running dirservers in our routerlist and the
58  * <b>PDS_RETRY_IF_NO_SERVERS</b> flag is set, set all the fallback ones
59  * (including authorities) as running again, and pick one.
60  *
61  * If the <b>PDS_IGNORE_FASCISTFIREWALL</b> flag is set, then include
62  * dirservers that we can't reach.
63  *
64  * If the <b>PDS_ALLOW_SELF</b> flag is not set, then don't include ourself
65  * (if we're a dirserver).
66  *
67  * Don't pick a fallback directory mirror if any non-fallback is viable;
68  * (the fallback directory mirrors include the authorities)
69  * try to avoid using servers that have returned 503 recently.
70  */
71 const routerstatus_t *
73 {
74  int busy = 0;
75  const routerstatus_t *choice;
76 
77  choice = router_pick_directory_server_impl(type, flags, &busy);
78  if (choice || !(flags & PDS_RETRY_IF_NO_SERVERS))
79  return choice;
80 
81  if (busy) {
82  /* If the reason that we got no server is that servers are "busy",
83  * we must be excluding good servers because we already have serverdesc
84  * fetches with them. Do not mark down servers up because of this. */
87  return NULL;
88  }
89 
90  log_info(LD_DIR,
91  "No reachable router entries for dirservers. "
92  "Trying them all again.");
93  /* mark all fallback directory mirrors as up again */
95  /* try again */
96  choice = router_pick_directory_server_impl(type, flags, NULL);
97  return choice;
98 }
99 
100 /** Try to find a running fallback directory. Flags are as for
101  * router_pick_directory_server.
102  */
103 const routerstatus_t *
105  dirinfo_type_t type, int flags)
106 {
107  const routerstatus_t *choice;
108  int busy = 0;
109 
110  if (smartlist_len(sourcelist) == 1) {
111  /* If there's only one choice, then we should disable the logic that
112  * would otherwise prevent us from choosing ourself. */
113  flags |= PDS_ALLOW_SELF;
114  }
115 
116  choice = router_pick_trusteddirserver_impl(sourcelist, type, flags, &busy);
117  if (choice || !(flags & PDS_RETRY_IF_NO_SERVERS))
118  return choice;
119  if (busy) {
120  /* If the reason that we got no server is that servers are "busy",
121  * we must be excluding good servers because we already have serverdesc
122  * fetches with them. Do not mark down servers up because of this. */
125  return NULL;
126  }
127 
128  log_info(LD_DIR,
129  "No dirservers are reachable. Trying them all again.");
130  mark_all_dirservers_up(sourcelist);
131  return router_pick_trusteddirserver_impl(sourcelist, type, flags, NULL);
132 }
133 
134 /* Common retry code for router_pick_directory_server_impl and
135  * router_pick_trusteddirserver_impl. Retry with the non-preferred IP version.
136  * Must be called before RETRY_WITHOUT_EXCLUDE().
137  *
138  * If we got no result, and we are applying IP preferences, and we are a
139  * client that could use an alternate IP version, try again with the
140  * opposite preferences. */
141 #define RETRY_ALTERNATE_IP_VERSION(retry_label) \
142  STMT_BEGIN \
143  if (result == NULL && try_ip_pref && options->ClientUseIPv4 \
144  && reachable_addr_use_ipv6(options) && !server_mode(options) \
145  && !n_busy) { \
146  n_excluded = 0; \
147  n_busy = 0; \
148  try_ip_pref = 0; \
149  goto retry_label; \
150  } \
151  STMT_END
152 
153 /* Common retry code for router_pick_directory_server_impl and
154  * router_pick_trusteddirserver_impl. Retry without excluding nodes, but with
155  * the preferred IP version. Must be called after RETRY_ALTERNATE_IP_VERSION().
156  *
157  * If we got no result, and we are excluding nodes, and StrictNodes is
158  * not set, try again without excluding nodes. */
159 #define RETRY_WITHOUT_EXCLUDE(retry_label) \
160  STMT_BEGIN \
161  if (result == NULL && try_excluding && !options->StrictNodes \
162  && n_excluded && !n_busy) { \
163  try_excluding = 0; \
164  n_excluded = 0; \
165  n_busy = 0; \
166  try_ip_pref = 1; \
167  goto retry_label; \
168  } \
169  STMT_END
170 
171 /* Common code used in the loop within router_pick_directory_server_impl and
172  * router_pick_trusteddirserver_impl.
173  *
174  * Check if the given <b>identity</b> supports extrainfo. If not, skip further
175  * checks.
176  */
177 #define SKIP_MISSING_TRUSTED_EXTRAINFO(type, identity) \
178  STMT_BEGIN \
179  int is_trusted_extrainfo = router_digest_is_trusted_dir_type( \
180  (identity), EXTRAINFO_DIRINFO); \
181  if (((type) & EXTRAINFO_DIRINFO) && \
182  !router_supports_extrainfo((identity), is_trusted_extrainfo)) \
183  continue; \
184  STMT_END
185 
186 #ifndef LOG_FALSE_POSITIVES_DURING_BOOTSTRAP
187 #define LOG_FALSE_POSITIVES_DURING_BOOTSTRAP 0
188 #endif
189 
190 /* Log a message if rs is not found or not a preferred address */
191 static void
192 router_picked_poor_directory_log(const routerstatus_t *rs)
193 {
194  const networkstatus_t *usable_consensus;
195  usable_consensus = networkstatus_get_reasonably_live_consensus(time(NULL),
197 
198 #if !LOG_FALSE_POSITIVES_DURING_BOOTSTRAP
199  /* Don't log early in the bootstrap process, it's normal to pick from a
200  * small pool of nodes. Of course, this won't help if we're trying to
201  * diagnose bootstrap issues. */
202  if (!smartlist_len(nodelist_get_list()) || !usable_consensus
204  return;
205  }
206 #endif /* !LOG_FALSE_POSITIVES_DURING_BOOTSTRAP */
207 
208  /* We couldn't find a node, or the one we have doesn't fit our preferences.
209  * Sometimes this is normal, sometimes it can be a reachability issue. */
210  if (!rs) {
211  /* This happens a lot, so it's at debug level */
212  log_debug(LD_DIR, "Wanted to make an outgoing directory connection, but "
213  "we couldn't find a directory that fit our criteria. "
214  "Perhaps we will succeed next time with less strict criteria.");
215  } else if (!reachable_addr_allows_rs(rs, FIREWALL_OR_CONNECTION, 1)
216  && !reachable_addr_allows_rs(rs, FIREWALL_DIR_CONNECTION, 1)
217  ) {
218  /* This is rare, and might be interesting to users trying to diagnose
219  * connection issues on dual-stack machines. */
220  char *ipv4_str = tor_addr_to_str_dup(&rs->ipv4_addr);
221  log_info(LD_DIR, "Selected a directory %s with non-preferred OR and Dir "
222  "addresses for launching an outgoing connection: "
223  "IPv4 %s OR %d Dir %d IPv6 %s OR %d Dir %d",
225  ipv4_str, rs->ipv4_orport,
226  rs->ipv4_dirport, fmt_addr(&rs->ipv6_addr),
227  rs->ipv6_orport, rs->ipv4_dirport);
228  tor_free(ipv4_str);
229  }
230 }
231 
232 #undef LOG_FALSE_POSITIVES_DURING_BOOTSTRAP
233 
234 /* Check if we already have a directory fetch from ap, for serverdesc
235  * (including extrainfo) or microdesc documents.
236  * If so, return 1, if not, return 0.
237  * Also returns 0 if addr is NULL, tor_addr_is_null(addr), or dir_port is 0.
238  */
239 STATIC int
240 router_is_already_dir_fetching(const tor_addr_port_t *ap, int serverdesc,
241  int microdesc)
242 {
243  if (!ap || tor_addr_is_null(&ap->addr) || !ap->port) {
244  return 0;
245  }
246 
247  /* XX/teor - we're not checking tunnel connections here, see #17848
248  */
249  if (serverdesc && (
251  CONN_TYPE_DIR, &ap->addr, ap->port, DIR_PURPOSE_FETCH_SERVERDESC)
253  CONN_TYPE_DIR, &ap->addr, ap->port, DIR_PURPOSE_FETCH_EXTRAINFO))) {
254  return 1;
255  }
256 
257  if (microdesc && (
259  CONN_TYPE_DIR, &ap->addr, ap->port, DIR_PURPOSE_FETCH_MICRODESC))) {
260  return 1;
261  }
262 
263  return 0;
264 }
265 
266 /* Check if we already have a directory fetch from the ipv4 or ipv6
267  * router, for serverdesc (including extrainfo) or microdesc documents.
268  * If so, return 1, if not, return 0.
269  */
270 static int
271 router_is_already_dir_fetching_(const tor_addr_t *ipv4_addr,
272  const tor_addr_t *ipv6_addr,
273  uint16_t dir_port,
274  int serverdesc,
275  int microdesc)
276 {
277  tor_addr_port_t ipv4_dir_ap, ipv6_dir_ap;
278 
279  /* Assume IPv6 DirPort is the same as IPv4 DirPort */
280  tor_addr_copy(&ipv4_dir_ap.addr, ipv4_addr);
281  ipv4_dir_ap.port = dir_port;
282  tor_addr_copy(&ipv6_dir_ap.addr, ipv6_addr);
283  ipv6_dir_ap.port = dir_port;
284 
285  return (router_is_already_dir_fetching(&ipv4_dir_ap, serverdesc, microdesc)
286  || router_is_already_dir_fetching(&ipv6_dir_ap, serverdesc, microdesc));
287 }
288 
289 /** Pick a random running valid directory server/mirror from our
290  * routerlist. Arguments are as for router_pick_directory_server(), except:
291  *
292  * If <b>n_busy_out</b> is provided, set *<b>n_busy_out</b> to the number of
293  * directories that we excluded for no other reason than
294  * PDS_NO_EXISTING_SERVERDESC_FETCH or PDS_NO_EXISTING_MICRODESC_FETCH.
295  */
296 STATIC const routerstatus_t *
298  int *n_busy_out)
299 {
300  const or_options_t *options = get_options();
301  const node_t *result;
302  smartlist_t *direct, *tunnel;
303  smartlist_t *trusted_direct, *trusted_tunnel;
304  smartlist_t *overloaded_direct, *overloaded_tunnel;
305  time_t now = time(NULL);
307  const int requireother = ! (flags & PDS_ALLOW_SELF);
308  const int fascistfirewall = ! (flags & PDS_IGNORE_FASCISTFIREWALL);
309  const int no_serverdesc_fetching =(flags & PDS_NO_EXISTING_SERVERDESC_FETCH);
310  const int no_microdesc_fetching = (flags & PDS_NO_EXISTING_MICRODESC_FETCH);
311  int try_excluding = 1, n_excluded = 0, n_busy = 0;
312  int try_ip_pref = 1;
313 
314  if (!consensus)
315  return NULL;
316 
317  retry_search:
318 
319  direct = smartlist_new();
320  tunnel = smartlist_new();
321  trusted_direct = smartlist_new();
322  trusted_tunnel = smartlist_new();
323  overloaded_direct = smartlist_new();
324  overloaded_tunnel = smartlist_new();
325 
326  const int skip_or_fw = router_or_conn_should_skip_reachable_address_check(
327  options,
328  try_ip_pref);
329  const int skip_dir_fw = router_dir_conn_should_skip_reachable_address_check(
330  options,
331  try_ip_pref);
332  const int must_have_or = dirclient_must_use_begindir(options);
333 
334  /* Find all the running dirservers we know about. */
336  int is_trusted;
337  int is_overloaded;
338  const routerstatus_t *status = node->rs;
339  const country_t country = node->country;
340  if (!status)
341  continue;
342 
343  if (!node->is_running || !node_is_dir(node) || !node->is_valid)
344  continue;
345  if (requireother && router_digest_is_me(node->identity))
346  continue;
347 
348  SKIP_MISSING_TRUSTED_EXTRAINFO(type, node->identity);
349 
350  if (try_excluding &&
352  country)) {
353  ++n_excluded;
354  continue;
355  }
356 
357  if (router_is_already_dir_fetching_(&status->ipv4_addr,
358  &status->ipv6_addr,
359  status->ipv4_dirport,
360  no_serverdesc_fetching,
361  no_microdesc_fetching)) {
362  ++n_busy;
363  continue;
364  }
365 
366  is_overloaded = status->last_dir_503_at + DIR_503_TIMEOUT > now;
367  is_trusted = router_digest_is_trusted_dir(node->identity);
368 
369  /* Clients use IPv6 addresses if the server has one and the client
370  * prefers IPv6.
371  * Add the router if its preferred address and port are reachable.
372  * If we don't get any routers, we'll try again with the non-preferred
373  * address for each router (if any). (To ensure correct load-balancing
374  * we try routers that only have one address both times.)
375  */
376  if (!fascistfirewall || skip_or_fw ||
377  reachable_addr_allows_node(node, FIREWALL_OR_CONNECTION,
378  try_ip_pref))
379  smartlist_add(is_trusted ? trusted_tunnel :
380  is_overloaded ? overloaded_tunnel : tunnel, (void*)node);
381  else if (!must_have_or && (skip_dir_fw ||
382  reachable_addr_allows_node(node, FIREWALL_DIR_CONNECTION,
383  try_ip_pref)))
384  smartlist_add(is_trusted ? trusted_direct :
385  is_overloaded ? overloaded_direct : direct, (void*)node);
386  } SMARTLIST_FOREACH_END(node);
387 
388  if (smartlist_len(tunnel)) {
389  result = node_sl_choose_by_bandwidth(tunnel, WEIGHT_FOR_DIR);
390  } else if (smartlist_len(overloaded_tunnel)) {
391  result = node_sl_choose_by_bandwidth(overloaded_tunnel,
392  WEIGHT_FOR_DIR);
393  } else if (smartlist_len(trusted_tunnel)) {
394  /* FFFF We don't distinguish between trusteds and overloaded trusteds
395  * yet. Maybe one day we should. */
396  /* FFFF We also don't load balance over authorities yet. I think this
397  * is a feature, but it could easily be a bug. -RD */
398  result = smartlist_choose(trusted_tunnel);
399  } else if (smartlist_len(direct)) {
400  result = node_sl_choose_by_bandwidth(direct, WEIGHT_FOR_DIR);
401  } else if (smartlist_len(overloaded_direct)) {
402  result = node_sl_choose_by_bandwidth(overloaded_direct,
403  WEIGHT_FOR_DIR);
404  } else {
405  result = smartlist_choose(trusted_direct);
406  }
407  smartlist_free(direct);
408  smartlist_free(tunnel);
409  smartlist_free(trusted_direct);
410  smartlist_free(trusted_tunnel);
411  smartlist_free(overloaded_direct);
412  smartlist_free(overloaded_tunnel);
413 
414  RETRY_ALTERNATE_IP_VERSION(retry_search);
415 
416  RETRY_WITHOUT_EXCLUDE(retry_search);
417 
418  if (n_busy_out)
419  *n_busy_out = n_busy;
420 
421  router_picked_poor_directory_log(result ? result->rs : NULL);
422 
423  return result ? result->rs : NULL;
424 }
425 
426 /** Given an array of double/uint64_t unions that are currently being used as
427  * doubles, convert them to uint64_t, and try to scale them linearly so as to
428  * much of the range of uint64_t. If <b>total_out</b> is provided, set it to
429  * the sum of all elements in the array _before_ scaling. */
430 STATIC void
431 scale_array_elements_to_u64(uint64_t *entries_out, const double *entries_in,
432  int n_entries,
433  uint64_t *total_out)
434 {
435  double total = 0.0;
436  double scale_factor = 0.0;
437  int i;
438 
439  for (i = 0; i < n_entries; ++i)
440  total += entries_in[i];
441 
442  if (total > 0.0) {
443  scale_factor = ((double)INT64_MAX) / total;
444  scale_factor /= 4.0; /* make sure we're very far away from overflowing */
445  }
446 
447  for (i = 0; i < n_entries; ++i)
448  entries_out[i] = tor_llround(entries_in[i] * scale_factor);
449 
450  if (total_out)
451  *total_out = (uint64_t) total;
452 }
453 
454 /** Pick a random element of <b>n_entries</b>-element array <b>entries</b>,
455  * choosing each element with a probability proportional to its (uint64_t)
456  * value, and return the index of that element. If all elements are 0, choose
457  * an index at random. Return -1 on error.
458  */
459 STATIC int
460 choose_array_element_by_weight(const uint64_t *entries, int n_entries)
461 {
462  int i;
463  uint64_t rand_val;
464  uint64_t total = 0;
465 
466  for (i = 0; i < n_entries; ++i)
467  total += entries[i];
468 
469  if (n_entries < 1)
470  return -1;
471 
472  if (total == 0)
473  return crypto_rand_int(n_entries);
474 
475  tor_assert(total < INT64_MAX);
476 
477  rand_val = crypto_rand_uint64(total);
478 
480  entries, n_entries, total, rand_val);
481 }
482 
483 /** Return bw*1000, unless bw*1000 would overflow, in which case return
484  * INT32_MAX. */
485 static inline int32_t
486 kb_to_bytes(uint32_t bw)
487 {
488  return (bw > (INT32_MAX/1000)) ? INT32_MAX : bw*1000;
489 }
490 
491 /** Helper function:
492  * choose a random element of smartlist <b>sl</b> of nodes, weighted by
493  * the advertised bandwidth of each element using the consensus
494  * bandwidth weights.
495  *
496  * If <b>rule</b>==WEIGHT_FOR_EXIT. we're picking an exit node: consider all
497  * nodes' bandwidth equally regardless of their Exit status, since there may
498  * be some in the list because they exit to obscure ports. If
499  * <b>rule</b>==NO_WEIGHTING, we're picking a non-exit node: weight
500  * exit-node's bandwidth less depending on the smallness of the fraction of
501  * Exit-to-total bandwidth. If <b>rule</b>==WEIGHT_FOR_GUARD, we're picking a
502  * guard node: consider all guard's bandwidth equally. Otherwise, weight
503  * guards proportionally less.
504  */
505 static const node_t *
508 {
509  double *bandwidths_dbl=NULL;
510  uint64_t *bandwidths_u64=NULL;
511 
512  if (compute_weighted_bandwidths(sl, rule, &bandwidths_dbl, NULL) < 0)
513  return NULL;
514 
515  bandwidths_u64 = tor_calloc(smartlist_len(sl), sizeof(uint64_t));
516  scale_array_elements_to_u64(bandwidths_u64, bandwidths_dbl,
517  smartlist_len(sl), NULL);
518 
519  {
520  int idx = choose_array_element_by_weight(bandwidths_u64,
521  smartlist_len(sl));
522  tor_free(bandwidths_dbl);
523  tor_free(bandwidths_u64);
524  return idx < 0 ? NULL : smartlist_get(sl, idx);
525  }
526 }
527 
528 /** When weighting bridges, enforce these values as lower and upper
529  * bound for believable bandwidth, because there is no way for us
530  * to verify a bridge's bandwidth currently. */
531 #define BRIDGE_MIN_BELIEVABLE_BANDWIDTH 20000 /* 20 kB/sec */
532 #define BRIDGE_MAX_BELIEVABLE_BANDWIDTH 100000 /* 100 kB/sec */
533 
534 /** Return the smaller of the router's configured BandwidthRate
535  * and its advertised capacity, making sure to stay within the
536  * interval between bridge-min-believe-bw and
537  * bridge-max-believe-bw. */
538 static uint32_t
540 {
541  uint32_t result = router->bandwidthcapacity;
542  if (result > router->bandwidthrate)
543  result = router->bandwidthrate;
544  if (result > BRIDGE_MAX_BELIEVABLE_BANDWIDTH)
545  result = BRIDGE_MAX_BELIEVABLE_BANDWIDTH;
546  else if (result < BRIDGE_MIN_BELIEVABLE_BANDWIDTH)
548  return result;
549 }
550 
551 /**
552  * We have found an instance of bug 32868: log our best guess about where the
553  * routerstatus was found.
554  **/
555 static void
557 {
558  static ratelim_t buggy_rs_ratelim = RATELIM_INIT(1200);
559  char *m;
560  if ((m = rate_limit_log(&buggy_rs_ratelim, approx_time()))) {
561  log_warn(LD_BUG,
562  "Found a routerstatus %p with has_guardfraction=%u "
563  " and guardfraction_percentage=%u, but is_possible_guard=%u.%s",
564  rs,
565  rs->has_guardfraction,
567  rs->is_possible_guard,
568  m);
569  tor_free(m);
570  networkstatus_t *ns;
571  int in_ns_count = 0;
572  if ((ns = networkstatus_get_latest_consensus_by_flavor(FLAV_NS))) {
573  int pos = smartlist_pos(ns->routerstatus_list, rs);
574  if (pos >= 0) {
575  ++in_ns_count;
576  log_warn(LD_BUG, "Found the routerstatus at position %d of the "
577  "NS consensus.", pos);
578  }
579  }
580  if ((ns = networkstatus_get_latest_consensus_by_flavor(FLAV_MICRODESC))) {
581  int pos = smartlist_pos(ns->routerstatus_list, rs);
582  if (pos >= 0) {
583  ++in_ns_count;
584  log_warn(LD_BUG, "Found the routerstatus at position %d of the "
585  "MD consensus.", pos);
586  }
587  }
588  if (in_ns_count == 0) {
589  log_warn(LD_BUG, "Could not find the routerstatus in any "
590  "latest consensus.");
591  }
593  }
594 }
595 
596 /** Given a list of routers and a weighting rule as in
597  * smartlist_choose_node_by_bandwidth_weights, compute weighted bandwidth
598  * values for each node and store them in a freshly allocated
599  * *<b>bandwidths_out</b> of the same length as <b>sl</b>, and holding results
600  * as doubles. If <b>total_bandwidth_out</b> is non-NULL, set it to the total
601  * of all the bandwidths.
602  * Return 0 on success, -1 on failure. */
603 static int
606  double **bandwidths_out,
607  double *total_bandwidth_out)
608 {
609  int64_t weight_scale;
610  double Wg = -1, Wm = -1, We = -1, Wd = -1;
611  double Wgb = -1, Wmb = -1, Web = -1, Wdb = -1;
612  guardfraction_bandwidth_t guardfraction_bw;
613  double *bandwidths = NULL;
614  double total_bandwidth = 0.0;
615 
616  tor_assert(sl);
617  tor_assert(bandwidths_out);
618 
619  /* Can't choose exit and guard at same time */
620  tor_assert(rule == NO_WEIGHTING ||
621  rule == WEIGHT_FOR_EXIT ||
622  rule == WEIGHT_FOR_GUARD ||
623  rule == WEIGHT_FOR_MID ||
624  rule == WEIGHT_FOR_DIR);
625 
626  *bandwidths_out = NULL;
627 
628  if (total_bandwidth_out) {
629  *total_bandwidth_out = 0.0;
630  }
631 
632  if (smartlist_len(sl) == 0) {
633  log_info(LD_CIRC,
634  "Empty routerlist passed in to consensus weight node "
635  "selection for rule %s",
637  return -1;
638  }
639 
640  weight_scale = networkstatus_get_weight_scale_param(NULL);
641  tor_assert(weight_scale >= 1);
642 
643  if (rule == WEIGHT_FOR_GUARD) {
644  Wg = networkstatus_get_bw_weight(NULL, "Wgg", -1);
645  Wm = networkstatus_get_bw_weight(NULL, "Wgm", -1); /* Bridges */
646  We = 0;
647  Wd = networkstatus_get_bw_weight(NULL, "Wgd", -1);
648 
649  Wgb = networkstatus_get_bw_weight(NULL, "Wgb", -1);
650  Wmb = networkstatus_get_bw_weight(NULL, "Wmb", -1);
651  Web = networkstatus_get_bw_weight(NULL, "Web", -1);
652  Wdb = networkstatus_get_bw_weight(NULL, "Wdb", -1);
653  } else if (rule == WEIGHT_FOR_MID) {
654  Wg = networkstatus_get_bw_weight(NULL, "Wmg", -1);
655  Wm = networkstatus_get_bw_weight(NULL, "Wmm", -1);
656  We = networkstatus_get_bw_weight(NULL, "Wme", -1);
657  Wd = networkstatus_get_bw_weight(NULL, "Wmd", -1);
658 
659  Wgb = networkstatus_get_bw_weight(NULL, "Wgb", -1);
660  Wmb = networkstatus_get_bw_weight(NULL, "Wmb", -1);
661  Web = networkstatus_get_bw_weight(NULL, "Web", -1);
662  Wdb = networkstatus_get_bw_weight(NULL, "Wdb", -1);
663  } else if (rule == WEIGHT_FOR_EXIT) {
664  // Guards CAN be exits if they have weird exit policies
665  // They are d then I guess...
666  We = networkstatus_get_bw_weight(NULL, "Wee", -1);
667  Wm = networkstatus_get_bw_weight(NULL, "Wem", -1); /* Odd exit policies */
668  Wd = networkstatus_get_bw_weight(NULL, "Wed", -1);
669  Wg = networkstatus_get_bw_weight(NULL, "Weg", -1); /* Odd exit policies */
670 
671  Wgb = networkstatus_get_bw_weight(NULL, "Wgb", -1);
672  Wmb = networkstatus_get_bw_weight(NULL, "Wmb", -1);
673  Web = networkstatus_get_bw_weight(NULL, "Web", -1);
674  Wdb = networkstatus_get_bw_weight(NULL, "Wdb", -1);
675  } else if (rule == WEIGHT_FOR_DIR) {
676  We = networkstatus_get_bw_weight(NULL, "Wbe", -1);
677  Wm = networkstatus_get_bw_weight(NULL, "Wbm", -1);
678  Wd = networkstatus_get_bw_weight(NULL, "Wbd", -1);
679  Wg = networkstatus_get_bw_weight(NULL, "Wbg", -1);
680 
681  Wgb = Wmb = Web = Wdb = weight_scale;
682  } else if (rule == NO_WEIGHTING) {
683  Wg = Wm = We = Wd = weight_scale;
684  Wgb = Wmb = Web = Wdb = weight_scale;
685  }
686 
687  if (Wg < 0 || Wm < 0 || We < 0 || Wd < 0 || Wgb < 0 || Wmb < 0 || Wdb < 0
688  || Web < 0) {
689  log_debug(LD_CIRC,
690  "Got negative bandwidth weights. Defaulting to naive selection"
691  " algorithm.");
692  Wg = Wm = We = Wd = weight_scale;
693  Wgb = Wmb = Web = Wdb = weight_scale;
694  }
695 
696  Wg /= weight_scale;
697  Wm /= weight_scale;
698  We /= weight_scale;
699  Wd /= weight_scale;
700 
701  Wgb /= weight_scale;
702  Wmb /= weight_scale;
703  Web /= weight_scale;
704  Wdb /= weight_scale;
705 
706  bandwidths = tor_calloc(smartlist_len(sl), sizeof(double));
707 
708  // Cycle through smartlist and total the bandwidth.
709  static int warned_missing_bw = 0;
710  SMARTLIST_FOREACH_BEGIN(sl, const node_t *, node) {
711  int is_exit = 0, is_guard = 0, is_dir = 0, this_bw = 0;
712  double weight = 1;
713  double weight_without_guard_flag = 0; /* Used for guardfraction */
714  double final_weight = 0;
715  is_exit = node->is_exit && ! node->is_bad_exit;
716  is_guard = node->is_possible_guard;
717  is_dir = node_is_dir(node);
718  if (node->rs) {
719  if (!node->rs->has_bandwidth) {
720  /* This should never happen, unless all the authorities downgrade
721  * to 0.2.0 or rogue routerstatuses get inserted into our consensus. */
722  if (! warned_missing_bw) {
723  log_warn(LD_BUG,
724  "Consensus is missing some bandwidths. Using a naive "
725  "router selection algorithm");
726  warned_missing_bw = 1;
727  }
728  this_bw = 30000; /* Chosen arbitrarily */
729  } else {
730  this_bw = kb_to_bytes(node->rs->bandwidth_kb);
731  }
732  } else if (node->ri) {
733  /* bridge or other descriptor not in our consensus */
734  this_bw = bridge_get_advertised_bandwidth_bounded(node->ri);
735  } else {
736  /* We can't use this one. */
737  continue;
738  }
739 
740  if (is_guard && is_exit) {
741  weight = (is_dir ? Wdb*Wd : Wd);
742  weight_without_guard_flag = (is_dir ? Web*We : We);
743  } else if (is_guard) {
744  weight = (is_dir ? Wgb*Wg : Wg);
745  weight_without_guard_flag = (is_dir ? Wmb*Wm : Wm);
746  } else if (is_exit) {
747  weight = (is_dir ? Web*We : We);
748  } else { // middle
749  weight = (is_dir ? Wmb*Wm : Wm);
750  }
751  /* These should be impossible; but overflows here would be bad, so let's
752  * make sure. */
753  if (this_bw < 0)
754  this_bw = 0;
755  if (weight < 0.0)
756  weight = 0.0;
757  if (weight_without_guard_flag < 0.0)
758  weight_without_guard_flag = 0.0;
759 
760  /* If guardfraction information is available in the consensus, we
761  * want to calculate this router's bandwidth according to its
762  * guardfraction. Quoting from proposal236:
763  *
764  * Let Wpf denote the weight from the 'bandwidth-weights' line a
765  * client would apply to N for position p if it had the guard
766  * flag, Wpn the weight if it did not have the guard flag, and B the
767  * measured bandwidth of N in the consensus. Then instead of choosing
768  * N for position p proportionally to Wpf*B or Wpn*B, clients should
769  * choose N proportionally to F*Wpf*B + (1-F)*Wpn*B.
770  */
771  if (node->rs && node->rs->has_guardfraction && rule != WEIGHT_FOR_GUARD) {
772  /* We should only have guardfraction set if the node has the Guard
773  flag. */
774  if (! node->rs->is_possible_guard) {
775  log_buggy_rs_source(node->rs);
776  }
777 
778  guard_get_guardfraction_bandwidth(&guardfraction_bw,
779  this_bw,
780  node->rs->guardfraction_percentage);
781 
782  /* Calculate final_weight = F*Wpf*B + (1-F)*Wpn*B */
783  final_weight =
784  guardfraction_bw.guard_bw * weight +
785  guardfraction_bw.non_guard_bw * weight_without_guard_flag;
786 
787  log_debug(LD_GENERAL, "%s: Guardfraction weight %f instead of %f (%s)",
788  node->rs->nickname, final_weight, weight*this_bw,
790  } else { /* no guardfraction information. calculate the weight normally. */
791  final_weight = weight*this_bw;
792  }
793 
794  bandwidths[node_sl_idx] = final_weight;
795  total_bandwidth += final_weight;
796  } SMARTLIST_FOREACH_END(node);
797 
798  log_debug(LD_CIRC, "Generated weighted bandwidths for rule %s based "
799  "on weights "
800  "Wg=%f Wm=%f We=%f Wd=%f with total bw %f",
802  Wg, Wm, We, Wd, total_bandwidth);
803 
804  *bandwidths_out = bandwidths;
805 
806  if (total_bandwidth_out) {
807  *total_bandwidth_out = total_bandwidth;
808  }
809 
810  return 0;
811 }
812 
813 /** For all nodes in <b>sl</b>, return the fraction of those nodes, weighted
814  * by their weighted bandwidths with rule <b>rule</b>, for which we have
815  * descriptors.
816  *
817  * If <b>for_direct_connect</b> is true, we intend to connect to the node
818  * directly, as the first hop of a circuit; otherwise, we intend to connect
819  * to it indirectly, or use it as if we were connecting to it indirectly. */
820 double
823  int for_direct_conn)
824 {
825  double *bandwidths = NULL;
826  double total, present;
827 
828  if (smartlist_len(sl) == 0)
829  return 0.0;
830 
831  if (compute_weighted_bandwidths(sl, rule, &bandwidths, &total) < 0 ||
832  total <= 0.0) {
833  int n_with_descs = 0;
834  SMARTLIST_FOREACH(sl, const node_t *, node, {
835  if (node_has_preferred_descriptor(node, for_direct_conn))
836  n_with_descs++;
837  });
838  tor_free(bandwidths);
839  return ((double)n_with_descs) / smartlist_len(sl);
840  }
841 
842  present = 0.0;
843  SMARTLIST_FOREACH_BEGIN(sl, const node_t *, node) {
844  if (node_has_preferred_descriptor(node, for_direct_conn))
845  present += bandwidths[node_sl_idx];
846  } SMARTLIST_FOREACH_END(node);
847 
848  tor_free(bandwidths);
849 
850  return present / total;
851 }
852 
853 /** Choose a random element of status list <b>sl</b>, weighted by
854  * the advertised bandwidth of each node */
855 const node_t *
858 { /*XXXX MOVE */
860 }
861 
862 /** Given a <b>router</b>, add every node_t in its family (including the
863  * node itself!) to <b>sl</b>.
864  *
865  * Note the type mismatch: This function takes a routerinfo, but adds nodes
866  * to the smartlist!
867  */
868 static void
870 {
871  /* XXXX MOVE ? */
872  node_t fake_node;
873  const node_t *node = node_get_by_id(router->cache_info.identity_digest);
874  if (node == NULL) {
875  memset(&fake_node, 0, sizeof(fake_node));
876  fake_node.ri = (routerinfo_t *)router;
877  memcpy(fake_node.identity, router->cache_info.identity_digest, DIGEST_LEN);
878  node = &fake_node;
879  }
881 }
882 
883 /**
884  * Remove every node_t that appears in <b>excluded</b> from <b>sl</b>.
885  *
886  * Behaves like smartlist_subtract, but uses nodelist_idx values to deliver
887  * linear performance when smartlist_subtract would be quadratic.
888  **/
889 static void
891 {
892  const smartlist_t *nodelist = nodelist_get_list();
893  const int nodelist_len = smartlist_len(nodelist);
894  bitarray_t *excluded_idx = bitarray_init_zero(nodelist_len);
895 
896  /* We haven't used nodelist_idx in this way previously, so I'm going to be
897  * paranoid in this code, and check that nodelist_idx is correct for every
898  * node before we use it. If we fail, we fall back to smartlist_subtract().
899  */
900 
901  /* Set the excluded_idx bit corresponding to every excluded node...
902  */
903  SMARTLIST_FOREACH_BEGIN(excluded, const node_t *, node) {
904  const int idx = node->nodelist_idx;
905  if (BUG(idx < 0) || BUG(idx >= nodelist_len) ||
906  BUG(node != smartlist_get(nodelist, idx))) {
907  goto internal_error;
908  }
909  bitarray_set(excluded_idx, idx);
910  } SMARTLIST_FOREACH_END(node);
911 
912  /* Then remove them from sl.
913  */
914  SMARTLIST_FOREACH_BEGIN(sl, const node_t *, node) {
915  const int idx = node->nodelist_idx;
916  if (BUG(idx < 0) || BUG(idx >= nodelist_len) ||
917  BUG(node != smartlist_get(nodelist, idx))) {
918  goto internal_error;
919  }
920  if (bitarray_is_set(excluded_idx, idx)) {
921  SMARTLIST_DEL_CURRENT(sl, node);
922  }
923  } SMARTLIST_FOREACH_END(node);
924 
925  bitarray_free(excluded_idx);
926  return;
927 
928  internal_error:
929  log_warn(LD_BUG, "Internal error prevented us from using the fast method "
930  "for subtracting nodelists. Falling back to the quadratic way.");
931  smartlist_subtract(sl, excluded);
932  bitarray_free(excluded_idx);
933 }
934 
935 /* Node selection helper for router_choose_random_node().
936  *
937  * Populates a node list based on <b>flags</b>, ignoring nodes in
938  * <b>excludednodes</b> and <b>excludedset</b>. Chooses the node based on
939  * <b>rule</b>. */
940 static const node_t *
941 router_choose_random_node_helper(smartlist_t *excludednodes,
942  routerset_t *excludedset,
943  router_crn_flags_t flags,
945 {
947  const node_t *choice = NULL;
948 
950  log_debug(LD_CIRC,
951  "We found %d running nodes.",
952  smartlist_len(sl));
953 
954  nodelist_subtract(sl, excludednodes);
955 
956  if (excludedset) {
957  routerset_subtract_nodes(sl,excludedset);
958  log_debug(LD_CIRC,
959  "We removed excludedset, leaving %d nodes.",
960  smartlist_len(sl));
961  }
962 
963  // Always weight by bandwidth
964  choice = node_sl_choose_by_bandwidth(sl, rule);
965 
966  smartlist_free(sl);
967 
968  return choice;
969 }
970 
971 /** Return a random running node from the nodelist. Never pick a node that is
972  * in <b>excludedsmartlist</b>, or which matches <b>excludedset</b>, even if
973  * they are the only nodes available.
974  *
975  * <b>flags</b> is a set of CRN_* flags, see
976  * router_add_running_nodes_to_smartlist() for details.
977  */
978 const node_t *
980  routerset_t *excludedset,
981  router_crn_flags_t flags)
982 {
983  /* A limited set of flags, used for fallback node selection.
984  */
985  const bool need_uptime = (flags & CRN_NEED_UPTIME) != 0;
986  const bool need_capacity = (flags & CRN_NEED_CAPACITY) != 0;
987  const bool need_guard = (flags & CRN_NEED_GUARD) != 0;
988  const bool pref_addr = (flags & CRN_PREF_ADDR) != 0;
989 
990  smartlist_t *excludednodes=smartlist_new();
991  const node_t *choice = NULL;
992  const routerinfo_t *r;
994 
995  rule = (need_guard ? WEIGHT_FOR_GUARD : WEIGHT_FOR_MID);
996 
997  /* If the node_t is not found we won't be to exclude ourself but we
998  * won't be able to pick ourself in router_choose_random_node() so
999  * this is fine to at least try with our routerinfo_t object. */
1000  if ((r = router_get_my_routerinfo()))
1001  routerlist_add_node_and_family(excludednodes, r);
1002 
1003  if (excludedsmartlist) {
1004  smartlist_add_all(excludednodes, excludedsmartlist);
1005  }
1006 
1007  choice = router_choose_random_node_helper(excludednodes,
1008  excludedset,
1009  flags,
1010  rule);
1011 
1012  if (!choice && (need_uptime || need_capacity || need_guard || pref_addr)) {
1013  /* try once more, with fewer restrictions. */
1014  log_info(LD_CIRC,
1015  "We couldn't find any live%s%s%s%s routers; falling back "
1016  "to list of all routers.",
1017  need_capacity?", fast":"",
1018  need_uptime?", stable":"",
1019  need_guard?", guard":"",
1020  pref_addr?", preferred address":"");
1021  flags &= ~ (CRN_NEED_UPTIME|CRN_NEED_CAPACITY|CRN_NEED_GUARD|
1022  CRN_PREF_ADDR);
1023  choice = router_choose_random_node_helper(excludednodes,
1024  excludedset,
1025  flags,
1026  rule);
1027  }
1028  smartlist_free(excludednodes);
1029  if (!choice) {
1030  log_warn(LD_CIRC,
1031  "No available nodes when trying to choose node. Failing.");
1032  }
1033  return choice;
1034 }
1035 
1036 /** Try to find a running directory authority. Flags are as for
1037  * router_pick_directory_server.
1038  */
1039 const routerstatus_t *
1041 {
1044  type, flags);
1045 }
1046 
1047 /** Try to find a running fallback directory. Flags are as for
1048  * router_pick_directory_server.
1049  */
1050 const routerstatus_t *
1052 {
1054  router_get_fallback_dir_servers_mutable(),
1055  type, flags);
1056 }
1057 
1058 /** Pick a random element from a list of dir_server_t, weighting by their
1059  * <b>weight</b> field. */
1060 static const dir_server_t *
1061 dirserver_choose_by_weight(const smartlist_t *servers, double authority_weight)
1062 {
1063  int n = smartlist_len(servers);
1064  int i;
1065  double *weights_dbl;
1066  uint64_t *weights_u64;
1067  const dir_server_t *ds;
1068 
1069  weights_dbl = tor_calloc(n, sizeof(double));
1070  weights_u64 = tor_calloc(n, sizeof(uint64_t));
1071  for (i = 0; i < n; ++i) {
1072  ds = smartlist_get(servers, i);
1073  weights_dbl[i] = ds->weight;
1074  if (ds->is_authority)
1075  weights_dbl[i] *= authority_weight;
1076  }
1077 
1078  scale_array_elements_to_u64(weights_u64, weights_dbl, n, NULL);
1079  i = choose_array_element_by_weight(weights_u64, n);
1080  tor_free(weights_dbl);
1081  tor_free(weights_u64);
1082  return (i < 0) ? NULL : smartlist_get(servers, i);
1083 }
1084 
1085 /** Choose randomly from among the dir_server_ts in sourcelist that
1086  * are up. Flags are as for router_pick_directory_server_impl().
1087  */
1088 static const routerstatus_t *
1090  dirinfo_type_t type, int flags,
1091  int *n_busy_out)
1092 {
1093  const or_options_t *options = get_options();
1094  smartlist_t *direct, *tunnel;
1095  smartlist_t *overloaded_direct, *overloaded_tunnel;
1096  const routerinfo_t *me = router_get_my_routerinfo();
1097  const routerstatus_t *result = NULL;
1098  time_t now = time(NULL);
1099  const int requireother = ! (flags & PDS_ALLOW_SELF);
1100  const int fascistfirewall = ! (flags & PDS_IGNORE_FASCISTFIREWALL);
1101  const int no_serverdesc_fetching =(flags & PDS_NO_EXISTING_SERVERDESC_FETCH);
1102  const int no_microdesc_fetching =(flags & PDS_NO_EXISTING_MICRODESC_FETCH);
1103  const double auth_weight =
1104  (sourcelist == router_get_fallback_dir_servers()) ?
1105  options->DirAuthorityFallbackRate : 1.0;
1106  smartlist_t *pick_from;
1107  int n_busy = 0;
1108  int try_excluding = 1, n_excluded = 0;
1109  int try_ip_pref = 1;
1110 
1111  if (!sourcelist)
1112  return NULL;
1113 
1114  retry_search:
1115 
1116  direct = smartlist_new();
1117  tunnel = smartlist_new();
1118  overloaded_direct = smartlist_new();
1119  overloaded_tunnel = smartlist_new();
1120 
1121  const int skip_or_fw = router_or_conn_should_skip_reachable_address_check(
1122  options,
1123  try_ip_pref);
1124  const int skip_dir_fw = router_dir_conn_should_skip_reachable_address_check(
1125  options,
1126  try_ip_pref);
1127  const int must_have_or = dirclient_must_use_begindir(options);
1128 
1129  SMARTLIST_FOREACH_BEGIN(sourcelist, const dir_server_t *, d)
1130  {
1131  int is_overloaded =
1132  d->fake_status.last_dir_503_at + DIR_503_TIMEOUT > now;
1133  if (!d->is_running) continue;
1134  if ((type & d->type) == 0)
1135  continue;
1136 
1137  SKIP_MISSING_TRUSTED_EXTRAINFO(type, d->digest);
1138 
1139  if (requireother && me && router_digest_is_me(d->digest))
1140  continue;
1141  if (try_excluding &&
1143  &d->fake_status, -1)) {
1144  ++n_excluded;
1145  continue;
1146  }
1147 
1148  if (router_is_already_dir_fetching_(&d->ipv4_addr,
1149  &d->ipv6_addr,
1150  d->ipv4_dirport,
1151  no_serverdesc_fetching,
1152  no_microdesc_fetching)) {
1153  ++n_busy;
1154  continue;
1155  }
1156 
1157  /* Clients use IPv6 addresses if the server has one and the client
1158  * prefers IPv6.
1159  * Add the router if its preferred address and port are reachable.
1160  * If we don't get any routers, we'll try again with the non-preferred
1161  * address for each router (if any). (To ensure correct load-balancing
1162  * we try routers that only have one address both times.)
1163  */
1164  if (!fascistfirewall || skip_or_fw ||
1165  reachable_addr_allows_dir_server(d, FIREWALL_OR_CONNECTION,
1166  try_ip_pref))
1167  smartlist_add(is_overloaded ? overloaded_tunnel : tunnel, (void*)d);
1168  else if (!must_have_or && (skip_dir_fw ||
1169  reachable_addr_allows_dir_server(d, FIREWALL_DIR_CONNECTION,
1170  try_ip_pref)))
1171  smartlist_add(is_overloaded ? overloaded_direct : direct, (void*)d);
1172  }
1173  SMARTLIST_FOREACH_END(d);
1174 
1175  if (smartlist_len(tunnel)) {
1176  pick_from = tunnel;
1177  } else if (smartlist_len(overloaded_tunnel)) {
1178  pick_from = overloaded_tunnel;
1179  } else if (smartlist_len(direct)) {
1180  pick_from = direct;
1181  } else {
1182  pick_from = overloaded_direct;
1183  }
1184 
1185  {
1186  const dir_server_t *selection =
1187  dirserver_choose_by_weight(pick_from, auth_weight);
1188 
1189  if (selection)
1190  result = &selection->fake_status;
1191  }
1192 
1193  smartlist_free(direct);
1194  smartlist_free(tunnel);
1195  smartlist_free(overloaded_direct);
1196  smartlist_free(overloaded_tunnel);
1197 
1198  RETRY_ALTERNATE_IP_VERSION(retry_search);
1199 
1200  RETRY_WITHOUT_EXCLUDE(retry_search);
1201 
1202  router_picked_poor_directory_log(result);
1203 
1204  if (n_busy_out)
1205  *n_busy_out = n_busy;
1206  return result;
1207 }
guardfraction_bandwidth_t::non_guard_bw
int non_guard_bw
Definition: entrynodes.h:644
routerstatus_t::ipv4_dirport
uint16_t ipv4_dirport
Definition: routerstatus_st.h:34
country_t
int16_t country_t
Definition: country.h:17
routermode.h
Header file for routermode.c.
reachable_addr_allows_dir_server
int reachable_addr_allows_dir_server(const dir_server_t *ds, firewall_connection_t fw_connection, int pref_only)
Definition: policies.c:726
tor_free
#define tor_free(p)
Definition: malloc.h:52
routerinfo_t
Definition: routerinfo_st.h:20
dir_server_st.h
Trusted/fallback directory server structure.
bitarray.h
Implements a variable-sized (but non-resizeable) bit-array.
smartlist_pos
int smartlist_pos(const smartlist_t *sl, const void *element)
Definition: smartlist.c:119
routerstatus_describe
const char * routerstatus_describe(const routerstatus_t *rs)
Definition: describe.c:182
routerinfo_t::bandwidthcapacity
uint32_t bandwidthcapacity
Definition: routerinfo_st.h:58
tor_addr_t
Definition: address.h:69
approx_time
time_t approx_time(void)
Definition: approx_time.c:32
PDS_ALLOW_SELF
#define PDS_ALLOW_SELF
Definition: node_select.h:50
bridge_get_advertised_bandwidth_bounded
static uint32_t bridge_get_advertised_bandwidth_bounded(routerinfo_t *router)
Definition: node_select.c:539
is_dir
bool is_dir(file_status_t file_type)
Definition: files.c:261
tor_assert
#define tor_assert(expr)
Definition: util_bug.h:102
or_options_t::DirAuthorityFallbackRate
double DirAuthorityFallbackRate
Definition: or_options_st.h:457
CONN_TYPE_DIR
#define CONN_TYPE_DIR
Definition: connection.h:55
microdesc.h
Header file for microdesc.c.
LD_BUG
#define LD_BUG
Definition: log.h:86
router.h
Header file for router.c.
DIR_PURPOSE_FETCH_MICRODESC
#define DIR_PURPOSE_FETCH_MICRODESC
Definition: directory.h:71
router_digest_is_me
int router_digest_is_me(const char *digest)
Definition: router.c:1698
LD_GENERAL
#define LD_GENERAL
Definition: log.h:62
smartlist_choose
void * smartlist_choose(const smartlist_t *sl)
Definition: crypto_rand.c:590
router_get_my_routerinfo
const routerinfo_t * router_get_my_routerinfo(void)
Definition: router.c:1760
describe.h
Header file for describe.c.
smartlist_add_all
void smartlist_add_all(smartlist_t *s1, const smartlist_t *s2)
Definition: smartlist_core.c:125
node_get_by_id
const node_t * node_get_by_id(const char *identity_digest)
Definition: nodelist.c:223
smartlist_add
void smartlist_add(smartlist_t *sl, void *element)
Definition: smartlist_core.c:117
kb_to_bytes
static int32_t kb_to_bytes(uint32_t bw)
Definition: node_select.c:486
routerstatus_t::has_guardfraction
unsigned int has_guardfraction
Definition: routerstatus_st.h:74
reachable_addr_allows_rs
int reachable_addr_allows_rs(const routerstatus_t *rs, firewall_connection_t fw_connection, int pref_only)
Definition: policies.c:642
routerstatus_t
Definition: routerstatus_st.h:19
choose_array_element_by_weight
STATIC int choose_array_element_by_weight(const uint64_t *entries, int n_entries)
Definition: node_select.c:460
nodelist_add_node_and_family
void nodelist_add_node_and_family(smartlist_t *sl, const node_t *node)
Definition: nodelist.c:2161
tor_llround
int64_t tor_llround(double d)
Definition: fp.c:46
smartlist_new
smartlist_t * smartlist_new(void)
Definition: smartlist_core.c:26
reasons.h
Header file for reasons.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)
Definition: node_select.c:604
SMARTLIST_FOREACH
#define SMARTLIST_FOREACH(sl, type, var, cmd)
Definition: smartlist_foreach.h:112
crypto_rand_int
int crypto_rand_int(unsigned int max)
Definition: crypto_rand_numeric.c:52
networkstatus.h
Header file for networkstatus.c.
signed_descriptor_t::identity_digest
char identity_digest[DIGEST_LEN]
Definition: signed_descriptor_st.h:31
networkstatus_get_bw_weight
int32_t networkstatus_get_bw_weight(networkstatus_t *ns, const char *weight_name, int32_t default_val)
Definition: networkstatus.c:2546
dirlist.h
Header file for dirlist.c.
dirserver_choose_by_weight
static const dir_server_t * dirserver_choose_by_weight(const smartlist_t *servers, double authority_weight)
Definition: node_select.c:1061
LD_CIRC
#define LD_CIRC
Definition: log.h:82
fp.h
Header for fp.c.
routerset_subtract_nodes
void routerset_subtract_nodes(smartlist_t *lst, const routerset_t *routerset)
Definition: routerset.c:412
node_sl_choose_by_bandwidth
const node_t * node_sl_choose_by_bandwidth(const smartlist_t *sl, bandwidth_weight_rule_t rule)
Definition: node_select.c:856
DIGEST_LEN
#define DIGEST_LEN
Definition: digest_sizes.h:20
routerstatus_t::is_possible_guard
unsigned int is_possible_guard
Definition: routerstatus_st.h:50
rate_limit_log
char * rate_limit_log(ratelim_t *lim, time_t now)
Definition: ratelim.c:42
guardfraction_bandwidth_t
Definition: entrynodes.h:640
DIR_PURPOSE_FETCH_SERVERDESC
#define DIR_PURPOSE_FETCH_SERVERDESC
Definition: directory.h:39
networkstatus_get_latest_consensus_by_flavor
networkstatus_t * networkstatus_get_latest_consensus_by_flavor(consensus_flavor_t f)
Definition: networkstatus.c:1401
tor_addr_port_t
Definition: address.h:81
router_pick_trusteddirserver_impl
static const routerstatus_t * router_pick_trusteddirserver_impl(const smartlist_t *sourcelist, dirinfo_type_t auth, int flags, int *n_busy_out)
Definition: node_select.c:1089
routerstatus_t::ipv4_orport
uint16_t ipv4_orport
Definition: routerstatus_st.h:33
entrynodes.h
Header file for circuitbuild.c.
bitarray_init_zero
static bitarray_t * bitarray_init_zero(unsigned int n_bits)
Definition: bitarray.h:33
networkstatus_get_latest_consensus
networkstatus_t * networkstatus_get_latest_consensus(void)
Definition: networkstatus.c:1390
tor_assert_nonfatal_unreached
#define tor_assert_nonfatal_unreached()
Definition: util_bug.h:176
node_t
Definition: node_st.h:34
router_pick_directory_server
const routerstatus_t * router_pick_directory_server(dirinfo_type_t type, int flags)
Definition: node_select.c:72
dir_server_t::is_authority
unsigned int is_authority
Definition: dir_server_st.h:38
directory.h
Header file for directory.c.
bandwidth_weight_rule_t
bandwidth_weight_rule_t
Definition: node_select.h:41
or_options_t::ExcludeNodes
struct routerset_t * ExcludeNodes
Definition: or_options_st.h:102
networkstatus_get_reasonably_live_consensus
networkstatus_t * networkstatus_get_reasonably_live_consensus(time_t now, int flavor)
Definition: networkstatus.c:1477
usable_consensus_flavor
int usable_consensus_flavor(void)
Definition: microdesc.c:1085
select_array_member_cumulative_timei
int select_array_member_cumulative_timei(const uint64_t *entries, int n_entries, uint64_t total, uint64_t rand_val)
Definition: di_ops.c:259
nodelist_subtract
static void nodelist_subtract(smartlist_t *sl, const smartlist_t *excluded)
Definition: node_select.c:890
nodelist.h
Header file for nodelist.c.
DIR_PURPOSE_FETCH_EXTRAINFO
#define DIR_PURPOSE_FETCH_EXTRAINFO
Definition: directory.h:42
bitarray_set
static void bitarray_set(bitarray_t *b, int bit)
Definition: bitarray.h:68
routerlist.h
Header file for routerlist.c.
dir_server_t::fake_status
routerstatus_t fake_status
Definition: dir_server_st.h:51
routerset.h
Header file for routerset.c.
log_buggy_rs_source
static void log_buggy_rs_source(const routerstatus_t *rs)
Definition: node_select.c:556
router_pick_trusteddirserver
const routerstatus_t * router_pick_trusteddirserver(dirinfo_type_t type, int flags)
Definition: node_select.c:1040
PDS_NO_EXISTING_SERVERDESC_FETCH
#define PDS_NO_EXISTING_SERVERDESC_FETCH
Definition: node_select.h:67
router_get_trusted_dir_servers_mutable
smartlist_t * router_get_trusted_dir_servers_mutable(void)
Definition: dirlist.c:103
routerinfo_st.h
Router descriptor structure.
DIR_503_TIMEOUT
#define DIR_503_TIMEOUT
Definition: routerlist.h:49
PDS_IGNORE_FASCISTFIREWALL
#define PDS_IGNORE_FASCISTFIREWALL
Definition: node_select.h:60
dir_server_t
Definition: dir_server_st.h:21
node_select.h
Header file for node_select.c.
tor_addr_to_str_dup
char * tor_addr_to_str_dup(const tor_addr_t *addr)
Definition: address.c:1164
networkstatus_t::routerstatus_list
smartlist_t * routerstatus_list
Definition: networkstatus_st.h:96
PDS_NO_EXISTING_MICRODESC_FETCH
#define PDS_NO_EXISTING_MICRODESC_FETCH
Definition: node_select.h:73
guardfraction_bandwidth_t::guard_bw
int guard_bw
Definition: entrynodes.h:642
fmt_addr
#define fmt_addr(a)
Definition: address.h:239
crypto_rand.h
Common functions for using (pseudo-)random number generators.
bitarray_t
unsigned int bitarray_t
Definition: bitarray.h:30
get_options
const or_options_t * get_options(void)
Definition: config.c:928
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)
Definition: node_select.c:506
routerstatus_st.h
Routerstatus (consensus entry) structure.
routerstatus_t::guardfraction_percentage
uint32_t guardfraction_percentage
Definition: routerstatus_st.h:76
networkstatus_get_weight_scale_param
int networkstatus_get_weight_scale_param(networkstatus_t *ns)
Definition: networkstatus.c:2533
nodelist_get_list
const smartlist_t * nodelist_get_list(void)
Definition: nodelist.c:966
connection.h
Header file for connection.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)
Definition: node_select.c:431
crypto_rand_uint64
uint64_t crypto_rand_uint64(uint64_t max)
Definition: crypto_rand_numeric.c:106
router_reset_status_download_failures
void router_reset_status_download_failures(void)
Definition: dirlist.c:135
tor_addr_is_null
int tor_addr_is_null(const tor_addr_t *addr)
Definition: address.c:780
dirinfo_type_t
dirinfo_type_t
Definition: or.h:905
dirclient.h
Header file for dirclient.c.
bitarray_is_set
static unsigned int bitarray_is_set(bitarray_t *b, int bit)
Definition: bitarray.h:81
SMARTLIST_FOREACH_BEGIN
#define SMARTLIST_FOREACH_BEGIN(sl, type, var)
Definition: smartlist_foreach.h:78
SMARTLIST_DEL_CURRENT
#define SMARTLIST_DEL_CURRENT(sl, var)
Definition: smartlist_foreach.h:120
node_st.h
Node information structure.
routerstatus_t::ipv6_addr
tor_addr_t ipv6_addr
Definition: routerstatus_st.h:35
bandwidth_weight_rule_to_string
const char * bandwidth_weight_rule_to_string(bandwidth_weight_rule_t rule)
Definition: reasons.c:439
node_is_dir
int node_is_dir(const node_t *node)
Definition: nodelist.c:1383
policies.h
Header file for policies.c.
router_pick_fallback_dirserver
const routerstatus_t * router_pick_fallback_dirserver(dirinfo_type_t type, int flags)
Definition: node_select.c:1051
config.h
Header file for config.c.
router_choose_random_node
const node_t * router_choose_random_node(smartlist_t *excludedsmartlist, routerset_t *excludedset, router_crn_flags_t flags)
Definition: node_select.c:979
PDS_RETRY_IF_NO_SERVERS
#define PDS_RETRY_IF_NO_SERVERS
Definition: node_select.h:54
reachable_addr_allows_node
int reachable_addr_allows_node(const node_t *node, firewall_connection_t fw_connection, int pref_only)
Definition: policies.c:688
routerset_contains_routerstatus
int routerset_contains_routerstatus(const routerset_t *set, const routerstatus_t *rs, country_t country)
Definition: routerset.c:338
router_add_running_nodes_to_smartlist
void router_add_running_nodes_to_smartlist(smartlist_t *sl, int flags)
Definition: routerlist.c:614
frac_nodes_with_descriptors
double frac_nodes_with_descriptors(const smartlist_t *sl, bandwidth_weight_rule_t rule, int for_direct_conn)
Definition: node_select.c:821
or_options_t
Definition: or_options_st.h:45
STATIC
#define STATIC
Definition: testsupport.h:32
routerstatus_t::ipv6_orport
uint16_t ipv6_orport
Definition: routerstatus_st.h:36
routerlist_add_node_and_family
static void routerlist_add_node_and_family(smartlist_t *sl, const routerinfo_t *router)
Definition: node_select.c:869
router_crn_flags_t
router_crn_flags_t
Definition: node_select.h:16
BRIDGE_MIN_BELIEVABLE_BANDWIDTH
#define BRIDGE_MIN_BELIEVABLE_BANDWIDTH
Definition: node_select.c:531
smartlist_subtract
void smartlist_subtract(smartlist_t *sl1, const smartlist_t *sl2)
Definition: smartlist.c:264
router_have_minimum_dir_info
int router_have_minimum_dir_info(void)
Definition: nodelist.c:2346
LD_DIR
#define LD_DIR
Definition: log.h:88
mark_all_dirservers_up
void mark_all_dirservers_up(smartlist_t *server_list)
Definition: dirlist.c:216
networkstatus_st.h
Networkstatus consensus/vote structure.
connection_get_by_type_addr_port_purpose
connection_t * connection_get_by_type_addr_port_purpose(int type, const tor_addr_t *addr, uint16_t port, int purpose)
Definition: connection.c:4742
dirclient_modes.h
Header for feature/dirclient/dirclient_modes.c.
networkstatus_t
Definition: networkstatus_st.h:26
node_has_preferred_descriptor
int node_has_preferred_descriptor(const node_t *node, int for_direct_connect)
Definition: nodelist.c:1419
routerinfo_t::bandwidthrate
uint32_t bandwidthrate
Definition: routerinfo_st.h:54
smartlist_t
Definition: smartlist_core.h:26
router_pick_dirserver_generic
static const routerstatus_t * router_pick_dirserver_generic(smartlist_t *sourcelist, dirinfo_type_t type, int flags)
Definition: node_select.c:104
tor_addr_copy
void tor_addr_copy(tor_addr_t *dest, const tor_addr_t *src)
Definition: address.c:933
node_t::identity
char identity[DIGEST_LEN]
Definition: node_st.h:46
ratelim_t
Definition: ratelim.h:42
or.h
Master header file for Tor-specific functionality.
router_pick_directory_server_impl
STATIC const routerstatus_t * router_pick_directory_server_impl(dirinfo_type_t type, int flags, int *n_busy_out)
Definition: node_select.c:297