tor  0.4.1.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-2019, The Tor Project, Inc. */
5 /* See LICENSE for licensing information */
6 
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"
30 #include "feature/nodelist/routerset.h"
31 #include "feature/relay/router.h"
34 #include "lib/math/fp.h"
35 
36 #include "feature/dirclient/dir_server_st.h"
37 #include "feature/nodelist/networkstatus_st.h"
38 #include "feature/nodelist/node_st.h"
39 #include "feature/nodelist/routerinfo_st.h"
40 #include "feature/nodelist/routerstatus_st.h"
41 
42 static int compute_weighted_bandwidths(const smartlist_t *sl,
44  double **bandwidths_out,
45  double *total_bandwidth_out);
47  const smartlist_t *sourcelist, dirinfo_type_t auth,
48  int flags, int *n_busy_out);
50  smartlist_t *sourcelist,
51  dirinfo_type_t type, int flags);
52 
69 const routerstatus_t *
71 {
72  int busy = 0;
73  const routerstatus_t *choice;
74 
75  choice = router_pick_directory_server_impl(type, flags, &busy);
76  if (choice || !(flags & PDS_RETRY_IF_NO_SERVERS))
77  return choice;
78 
79  if (busy) {
80  /* If the reason that we got no server is that servers are "busy",
81  * we must be excluding good servers because we already have serverdesc
82  * fetches with them. Do not mark down servers up because of this. */
85  return NULL;
86  }
87 
88  log_info(LD_DIR,
89  "No reachable router entries for dirservers. "
90  "Trying them all again.");
91  /* mark all fallback directory mirrors as up again */
93  /* try again */
94  choice = router_pick_directory_server_impl(type, flags, NULL);
95  return choice;
96 }
97 
101 const routerstatus_t *
103  dirinfo_type_t type, int flags)
104 {
105  const routerstatus_t *choice;
106  int busy = 0;
107 
108  if (smartlist_len(sourcelist) == 1) {
109  /* If there's only one choice, then we should disable the logic that
110  * would otherwise prevent us from choosing ourself. */
111  flags |= PDS_ALLOW_SELF;
112  }
113 
114  choice = router_pick_trusteddirserver_impl(sourcelist, type, flags, &busy);
115  if (choice || !(flags & PDS_RETRY_IF_NO_SERVERS))
116  return choice;
117  if (busy) {
118  /* If the reason that we got no server is that servers are "busy",
119  * we must be excluding good servers because we already have serverdesc
120  * fetches with them. Do not mark down servers up because of this. */
123  return NULL;
124  }
125 
126  log_info(LD_DIR,
127  "No dirservers are reachable. Trying them all again.");
128  mark_all_dirservers_up(sourcelist);
129  return router_pick_trusteddirserver_impl(sourcelist, type, flags, NULL);
130 }
131 
132 /* Common retry code for router_pick_directory_server_impl and
133  * router_pick_trusteddirserver_impl. Retry with the non-preferred IP version.
134  * Must be called before RETRY_WITHOUT_EXCLUDE().
135  *
136  * If we got no result, and we are applying IP preferences, and we are a
137  * client that could use an alternate IP version, try again with the
138  * opposite preferences. */
139 #define RETRY_ALTERNATE_IP_VERSION(retry_label) \
140  STMT_BEGIN \
141  if (result == NULL && try_ip_pref && options->ClientUseIPv4 \
142  && fascist_firewall_use_ipv6(options) && !server_mode(options) \
143  && !n_busy) { \
144  n_excluded = 0; \
145  n_busy = 0; \
146  try_ip_pref = 0; \
147  goto retry_label; \
148  } \
149  STMT_END \
150 
151 /* Common retry code for router_pick_directory_server_impl and
152  * router_pick_trusteddirserver_impl. Retry without excluding nodes, but with
153  * the preferred IP version. Must be called after RETRY_ALTERNATE_IP_VERSION().
154  *
155  * If we got no result, and we are excluding nodes, and StrictNodes is
156  * not set, try again without excluding nodes. */
157 #define RETRY_WITHOUT_EXCLUDE(retry_label) \
158  STMT_BEGIN \
159  if (result == NULL && try_excluding && !options->StrictNodes \
160  && n_excluded && !n_busy) { \
161  try_excluding = 0; \
162  n_excluded = 0; \
163  n_busy = 0; \
164  try_ip_pref = 1; \
165  goto retry_label; \
166  } \
167  STMT_END
168 
169 /* Common code used in the loop within router_pick_directory_server_impl and
170  * router_pick_trusteddirserver_impl.
171  *
172  * Check if the given <b>identity</b> supports extrainfo. If not, skip further
173  * checks.
174  */
175 #define SKIP_MISSING_TRUSTED_EXTRAINFO(type, identity) \
176  STMT_BEGIN \
177  int is_trusted_extrainfo = router_digest_is_trusted_dir_type( \
178  (identity), EXTRAINFO_DIRINFO); \
179  if (((type) & EXTRAINFO_DIRINFO) && \
180  !router_supports_extrainfo((identity), is_trusted_extrainfo)) \
181  continue; \
182  STMT_END
183 
184 #ifndef LOG_FALSE_POSITIVES_DURING_BOOTSTRAP
185 #define LOG_FALSE_POSITIVES_DURING_BOOTSTRAP 0
186 #endif
187 
188 /* Log a message if rs is not found or not a preferred address */
189 static void
190 router_picked_poor_directory_log(const routerstatus_t *rs)
191 {
192  const networkstatus_t *usable_consensus;
193  usable_consensus = networkstatus_get_reasonably_live_consensus(time(NULL),
194  usable_consensus_flavor());
195 
196 #if !LOG_FALSE_POSITIVES_DURING_BOOTSTRAP
197  /* Don't log early in the bootstrap process, it's normal to pick from a
198  * small pool of nodes. Of course, this won't help if we're trying to
199  * diagnose bootstrap issues. */
200  if (!smartlist_len(nodelist_get_list()) || !usable_consensus
201  || !router_have_minimum_dir_info()) {
202  return;
203  }
204 #endif /* !LOG_FALSE_POSITIVES_DURING_BOOTSTRAP */
205 
206  /* We couldn't find a node, or the one we have doesn't fit our preferences.
207  * Sometimes this is normal, sometimes it can be a reachability issue. */
208  if (!rs) {
209  /* This happens a lot, so it's at debug level */
210  log_debug(LD_DIR, "Wanted to make an outgoing directory connection, but "
211  "we couldn't find a directory that fit our criteria. "
212  "Perhaps we will succeed next time with less strict criteria.");
213  } else if (!fascist_firewall_allows_rs(rs, FIREWALL_OR_CONNECTION, 1)
214  && !fascist_firewall_allows_rs(rs, FIREWALL_DIR_CONNECTION, 1)
215  ) {
216  /* This is rare, and might be interesting to users trying to diagnose
217  * connection issues on dual-stack machines. */
218  log_info(LD_DIR, "Selected a directory %s with non-preferred OR and Dir "
219  "addresses for launching an outgoing connection: "
220  "IPv4 %s OR %d Dir %d IPv6 %s OR %d Dir %d",
222  fmt_addr32(rs->addr), rs->or_port,
223  rs->dir_port, fmt_addr(&rs->ipv6_addr),
224  rs->ipv6_orport, rs->dir_port);
225  }
226 }
227 
228 #undef LOG_FALSE_POSITIVES_DURING_BOOTSTRAP
229 
230 /* Check if we already have a directory fetch from ap, for serverdesc
231  * (including extrainfo) or microdesc documents.
232  * If so, return 1, if not, return 0.
233  * Also returns 0 if addr is NULL, tor_addr_is_null(addr), or dir_port is 0.
234  */
235 STATIC int
236 router_is_already_dir_fetching(const tor_addr_port_t *ap, int serverdesc,
237  int microdesc)
238 {
239  if (!ap || tor_addr_is_null(&ap->addr) || !ap->port) {
240  return 0;
241  }
242 
243  /* XX/teor - we're not checking tunnel connections here, see #17848
244  */
245  if (serverdesc && (
246  connection_get_by_type_addr_port_purpose(
247  CONN_TYPE_DIR, &ap->addr, ap->port, DIR_PURPOSE_FETCH_SERVERDESC)
248  || connection_get_by_type_addr_port_purpose(
249  CONN_TYPE_DIR, &ap->addr, ap->port, DIR_PURPOSE_FETCH_EXTRAINFO))) {
250  return 1;
251  }
252 
253  if (microdesc && (
254  connection_get_by_type_addr_port_purpose(
255  CONN_TYPE_DIR, &ap->addr, ap->port, DIR_PURPOSE_FETCH_MICRODESC))) {
256  return 1;
257  }
258 
259  return 0;
260 }
261 
262 /* Check if we already have a directory fetch from the ipv4 or ipv6
263  * router, for serverdesc (including extrainfo) or microdesc documents.
264  * If so, return 1, if not, return 0.
265  */
266 static int
267 router_is_already_dir_fetching_(uint32_t ipv4_addr,
268  const tor_addr_t *ipv6_addr,
269  uint16_t dir_port,
270  int serverdesc,
271  int microdesc)
272 {
273  tor_addr_port_t ipv4_dir_ap, ipv6_dir_ap;
274 
275  /* Assume IPv6 DirPort is the same as IPv4 DirPort */
276  tor_addr_from_ipv4h(&ipv4_dir_ap.addr, ipv4_addr);
277  ipv4_dir_ap.port = dir_port;
278  tor_addr_copy(&ipv6_dir_ap.addr, ipv6_addr);
279  ipv6_dir_ap.port = dir_port;
280 
281  return (router_is_already_dir_fetching(&ipv4_dir_ap, serverdesc, microdesc)
282  || router_is_already_dir_fetching(&ipv6_dir_ap, serverdesc, microdesc));
283 }
284 
292 STATIC const routerstatus_t *
294  int *n_busy_out)
295 {
296  const or_options_t *options = get_options();
297  const node_t *result;
298  smartlist_t *direct, *tunnel;
299  smartlist_t *trusted_direct, *trusted_tunnel;
300  smartlist_t *overloaded_direct, *overloaded_tunnel;
301  time_t now = time(NULL);
302  const networkstatus_t *consensus = networkstatus_get_latest_consensus();
303  const int requireother = ! (flags & PDS_ALLOW_SELF);
304  const int fascistfirewall = ! (flags & PDS_IGNORE_FASCISTFIREWALL);
305  const int no_serverdesc_fetching =(flags & PDS_NO_EXISTING_SERVERDESC_FETCH);
306  const int no_microdesc_fetching = (flags & PDS_NO_EXISTING_MICRODESC_FETCH);
307  int try_excluding = 1, n_excluded = 0, n_busy = 0;
308  int try_ip_pref = 1;
309 
310  if (!consensus)
311  return NULL;
312 
313  retry_search:
314 
315  direct = smartlist_new();
316  tunnel = smartlist_new();
317  trusted_direct = smartlist_new();
318  trusted_tunnel = smartlist_new();
319  overloaded_direct = smartlist_new();
320  overloaded_tunnel = smartlist_new();
321 
322  const int skip_or_fw = router_skip_or_reachability(options, try_ip_pref);
323  const int skip_dir_fw = router_skip_dir_reachability(options, try_ip_pref);
324  const int must_have_or = directory_must_use_begindir(options);
325 
326  /* Find all the running dirservers we know about. */
327  SMARTLIST_FOREACH_BEGIN(nodelist_get_list(), const node_t *, node) {
328  int is_trusted;
329  int is_overloaded;
330  const routerstatus_t *status = node->rs;
331  const country_t country = node->country;
332  if (!status)
333  continue;
334 
335  if (!node->is_running || !node_is_dir(node) || !node->is_valid)
336  continue;
337  if (requireother && router_digest_is_me(node->identity))
338  continue;
339 
340  SKIP_MISSING_TRUSTED_EXTRAINFO(type, node->identity);
341 
342  if (try_excluding &&
344  country)) {
345  ++n_excluded;
346  continue;
347  }
348 
349  if (router_is_already_dir_fetching_(status->addr,
350  &status->ipv6_addr,
351  status->dir_port,
352  no_serverdesc_fetching,
353  no_microdesc_fetching)) {
354  ++n_busy;
355  continue;
356  }
357 
358  is_overloaded = status->last_dir_503_at + DIR_503_TIMEOUT > now;
359  is_trusted = router_digest_is_trusted_dir(node->identity);
360 
361  /* Clients use IPv6 addresses if the server has one and the client
362  * prefers IPv6.
363  * Add the router if its preferred address and port are reachable.
364  * If we don't get any routers, we'll try again with the non-preferred
365  * address for each router (if any). (To ensure correct load-balancing
366  * we try routers that only have one address both times.)
367  */
368  if (!fascistfirewall || skip_or_fw ||
369  fascist_firewall_allows_node(node, FIREWALL_OR_CONNECTION,
370  try_ip_pref))
371  smartlist_add(is_trusted ? trusted_tunnel :
372  is_overloaded ? overloaded_tunnel : tunnel, (void*)node);
373  else if (!must_have_or && (skip_dir_fw ||
374  fascist_firewall_allows_node(node, FIREWALL_DIR_CONNECTION,
375  try_ip_pref)))
376  smartlist_add(is_trusted ? trusted_direct :
377  is_overloaded ? overloaded_direct : direct, (void*)node);
378  } SMARTLIST_FOREACH_END(node);
379 
380  if (smartlist_len(tunnel)) {
381  result = node_sl_choose_by_bandwidth(tunnel, WEIGHT_FOR_DIR);
382  } else if (smartlist_len(overloaded_tunnel)) {
383  result = node_sl_choose_by_bandwidth(overloaded_tunnel,
384  WEIGHT_FOR_DIR);
385  } else if (smartlist_len(trusted_tunnel)) {
386  /* FFFF We don't distinguish between trusteds and overloaded trusteds
387  * yet. Maybe one day we should. */
388  /* FFFF We also don't load balance over authorities yet. I think this
389  * is a feature, but it could easily be a bug. -RD */
390  result = smartlist_choose(trusted_tunnel);
391  } else if (smartlist_len(direct)) {
392  result = node_sl_choose_by_bandwidth(direct, WEIGHT_FOR_DIR);
393  } else if (smartlist_len(overloaded_direct)) {
394  result = node_sl_choose_by_bandwidth(overloaded_direct,
395  WEIGHT_FOR_DIR);
396  } else {
397  result = smartlist_choose(trusted_direct);
398  }
399  smartlist_free(direct);
400  smartlist_free(tunnel);
401  smartlist_free(trusted_direct);
402  smartlist_free(trusted_tunnel);
403  smartlist_free(overloaded_direct);
404  smartlist_free(overloaded_tunnel);
405 
406  RETRY_ALTERNATE_IP_VERSION(retry_search);
407 
408  RETRY_WITHOUT_EXCLUDE(retry_search);
409 
410  if (n_busy_out)
411  *n_busy_out = n_busy;
412 
413  router_picked_poor_directory_log(result ? result->rs : NULL);
414 
415  return result ? result->rs : NULL;
416 }
417 
422 STATIC void
423 scale_array_elements_to_u64(uint64_t *entries_out, const double *entries_in,
424  int n_entries,
425  uint64_t *total_out)
426 {
427  double total = 0.0;
428  double scale_factor = 0.0;
429  int i;
430 
431  for (i = 0; i < n_entries; ++i)
432  total += entries_in[i];
433 
434  if (total > 0.0) {
435  scale_factor = ((double)INT64_MAX) / total;
436  scale_factor /= 4.0; /* make sure we're very far away from overflowing */
437  }
438 
439  for (i = 0; i < n_entries; ++i)
440  entries_out[i] = tor_llround(entries_in[i] * scale_factor);
441 
442  if (total_out)
443  *total_out = (uint64_t) total;
444 }
445 
451 STATIC int
452 choose_array_element_by_weight(const uint64_t *entries, int n_entries)
453 {
454  int i;
455  uint64_t rand_val;
456  uint64_t total = 0;
457 
458  for (i = 0; i < n_entries; ++i)
459  total += entries[i];
460 
461  if (n_entries < 1)
462  return -1;
463 
464  if (total == 0)
465  return crypto_rand_int(n_entries);
466 
467  tor_assert(total < INT64_MAX);
468 
469  rand_val = crypto_rand_uint64(total);
470 
472  entries, n_entries, total, rand_val);
473 }
474 
477 static inline int32_t
478 kb_to_bytes(uint32_t bw)
479 {
480  return (bw > (INT32_MAX/1000)) ? INT32_MAX : bw*1000;
481 }
482 
497 static const node_t *
500 {
501  double *bandwidths_dbl=NULL;
502  uint64_t *bandwidths_u64=NULL;
503 
504  if (compute_weighted_bandwidths(sl, rule, &bandwidths_dbl, NULL) < 0)
505  return NULL;
506 
507  bandwidths_u64 = tor_calloc(smartlist_len(sl), sizeof(uint64_t));
508  scale_array_elements_to_u64(bandwidths_u64, bandwidths_dbl,
509  smartlist_len(sl), NULL);
510 
511  {
512  int idx = choose_array_element_by_weight(bandwidths_u64,
513  smartlist_len(sl));
514  tor_free(bandwidths_dbl);
515  tor_free(bandwidths_u64);
516  return idx < 0 ? NULL : smartlist_get(sl, idx);
517  }
518 }
519 
523 #define BRIDGE_MIN_BELIEVABLE_BANDWIDTH 20000 /* 20 kB/sec */
524 #define BRIDGE_MAX_BELIEVABLE_BANDWIDTH 100000 /* 100 kB/sec */
525 
530 static uint32_t
532 {
533  uint32_t result = router->bandwidthcapacity;
534  if (result > router->bandwidthrate)
535  result = router->bandwidthrate;
536  if (result > BRIDGE_MAX_BELIEVABLE_BANDWIDTH)
537  result = BRIDGE_MAX_BELIEVABLE_BANDWIDTH;
538  else if (result < BRIDGE_MIN_BELIEVABLE_BANDWIDTH)
540  return result;
541 }
542 
550 static int
553  double **bandwidths_out,
554  double *total_bandwidth_out)
555 {
556  int64_t weight_scale;
557  double Wg = -1, Wm = -1, We = -1, Wd = -1;
558  double Wgb = -1, Wmb = -1, Web = -1, Wdb = -1;
559  guardfraction_bandwidth_t guardfraction_bw;
560  double *bandwidths = NULL;
561  double total_bandwidth = 0.0;
562 
563  tor_assert(sl);
564  tor_assert(bandwidths_out);
565 
566  /* Can't choose exit and guard at same time */
567  tor_assert(rule == NO_WEIGHTING ||
568  rule == WEIGHT_FOR_EXIT ||
569  rule == WEIGHT_FOR_GUARD ||
570  rule == WEIGHT_FOR_MID ||
571  rule == WEIGHT_FOR_DIR);
572 
573  *bandwidths_out = NULL;
574 
575  if (total_bandwidth_out) {
576  *total_bandwidth_out = 0.0;
577  }
578 
579  if (smartlist_len(sl) == 0) {
580  log_info(LD_CIRC,
581  "Empty routerlist passed in to consensus weight node "
582  "selection for rule %s",
584  return -1;
585  }
586 
587  weight_scale = networkstatus_get_weight_scale_param(NULL);
588 
589  if (rule == WEIGHT_FOR_GUARD) {
590  Wg = networkstatus_get_bw_weight(NULL, "Wgg", -1);
591  Wm = networkstatus_get_bw_weight(NULL, "Wgm", -1); /* Bridges */
592  We = 0;
593  Wd = networkstatus_get_bw_weight(NULL, "Wgd", -1);
594 
595  Wgb = networkstatus_get_bw_weight(NULL, "Wgb", -1);
596  Wmb = networkstatus_get_bw_weight(NULL, "Wmb", -1);
597  Web = networkstatus_get_bw_weight(NULL, "Web", -1);
598  Wdb = networkstatus_get_bw_weight(NULL, "Wdb", -1);
599  } else if (rule == WEIGHT_FOR_MID) {
600  Wg = networkstatus_get_bw_weight(NULL, "Wmg", -1);
601  Wm = networkstatus_get_bw_weight(NULL, "Wmm", -1);
602  We = networkstatus_get_bw_weight(NULL, "Wme", -1);
603  Wd = networkstatus_get_bw_weight(NULL, "Wmd", -1);
604 
605  Wgb = networkstatus_get_bw_weight(NULL, "Wgb", -1);
606  Wmb = networkstatus_get_bw_weight(NULL, "Wmb", -1);
607  Web = networkstatus_get_bw_weight(NULL, "Web", -1);
608  Wdb = networkstatus_get_bw_weight(NULL, "Wdb", -1);
609  } else if (rule == WEIGHT_FOR_EXIT) {
610  // Guards CAN be exits if they have weird exit policies
611  // They are d then I guess...
612  We = networkstatus_get_bw_weight(NULL, "Wee", -1);
613  Wm = networkstatus_get_bw_weight(NULL, "Wem", -1); /* Odd exit policies */
614  Wd = networkstatus_get_bw_weight(NULL, "Wed", -1);
615  Wg = networkstatus_get_bw_weight(NULL, "Weg", -1); /* Odd exit policies */
616 
617  Wgb = networkstatus_get_bw_weight(NULL, "Wgb", -1);
618  Wmb = networkstatus_get_bw_weight(NULL, "Wmb", -1);
619  Web = networkstatus_get_bw_weight(NULL, "Web", -1);
620  Wdb = networkstatus_get_bw_weight(NULL, "Wdb", -1);
621  } else if (rule == WEIGHT_FOR_DIR) {
622  We = networkstatus_get_bw_weight(NULL, "Wbe", -1);
623  Wm = networkstatus_get_bw_weight(NULL, "Wbm", -1);
624  Wd = networkstatus_get_bw_weight(NULL, "Wbd", -1);
625  Wg = networkstatus_get_bw_weight(NULL, "Wbg", -1);
626 
627  Wgb = Wmb = Web = Wdb = weight_scale;
628  } else if (rule == NO_WEIGHTING) {
629  Wg = Wm = We = Wd = weight_scale;
630  Wgb = Wmb = Web = Wdb = weight_scale;
631  }
632 
633  if (Wg < 0 || Wm < 0 || We < 0 || Wd < 0 || Wgb < 0 || Wmb < 0 || Wdb < 0
634  || Web < 0) {
635  log_debug(LD_CIRC,
636  "Got negative bandwidth weights. Defaulting to naive selection"
637  " algorithm.");
638  Wg = Wm = We = Wd = weight_scale;
639  Wgb = Wmb = Web = Wdb = weight_scale;
640  }
641 
642  Wg /= weight_scale;
643  Wm /= weight_scale;
644  We /= weight_scale;
645  Wd /= weight_scale;
646 
647  Wgb /= weight_scale;
648  Wmb /= weight_scale;
649  Web /= weight_scale;
650  Wdb /= weight_scale;
651 
652  bandwidths = tor_calloc(smartlist_len(sl), sizeof(double));
653 
654  // Cycle through smartlist and total the bandwidth.
655  static int warned_missing_bw = 0;
656  SMARTLIST_FOREACH_BEGIN(sl, const node_t *, node) {
657  int is_exit = 0, is_guard = 0, is_dir = 0, this_bw = 0;
658  double weight = 1;
659  double weight_without_guard_flag = 0; /* Used for guardfraction */
660  double final_weight = 0;
661  is_exit = node->is_exit && ! node->is_bad_exit;
662  is_guard = node->is_possible_guard;
663  is_dir = node_is_dir(node);
664  if (node->rs) {
665  if (!node->rs->has_bandwidth) {
666  /* This should never happen, unless all the authorities downgrade
667  * to 0.2.0 or rogue routerstatuses get inserted into our consensus. */
668  if (! warned_missing_bw) {
669  log_warn(LD_BUG,
670  "Consensus is missing some bandwidths. Using a naive "
671  "router selection algorithm");
672  warned_missing_bw = 1;
673  }
674  this_bw = 30000; /* Chosen arbitrarily */
675  } else {
676  this_bw = kb_to_bytes(node->rs->bandwidth_kb);
677  }
678  } else if (node->ri) {
679  /* bridge or other descriptor not in our consensus */
680  this_bw = bridge_get_advertised_bandwidth_bounded(node->ri);
681  } else {
682  /* We can't use this one. */
683  continue;
684  }
685 
686  if (is_guard && is_exit) {
687  weight = (is_dir ? Wdb*Wd : Wd);
688  weight_without_guard_flag = (is_dir ? Web*We : We);
689  } else if (is_guard) {
690  weight = (is_dir ? Wgb*Wg : Wg);
691  weight_without_guard_flag = (is_dir ? Wmb*Wm : Wm);
692  } else if (is_exit) {
693  weight = (is_dir ? Web*We : We);
694  } else { // middle
695  weight = (is_dir ? Wmb*Wm : Wm);
696  }
697  /* These should be impossible; but overflows here would be bad, so let's
698  * make sure. */
699  if (this_bw < 0)
700  this_bw = 0;
701  if (weight < 0.0)
702  weight = 0.0;
703  if (weight_without_guard_flag < 0.0)
704  weight_without_guard_flag = 0.0;
705 
706  /* If guardfraction information is available in the consensus, we
707  * want to calculate this router's bandwidth according to its
708  * guardfraction. Quoting from proposal236:
709  *
710  * Let Wpf denote the weight from the 'bandwidth-weights' line a
711  * client would apply to N for position p if it had the guard
712  * flag, Wpn the weight if it did not have the guard flag, and B the
713  * measured bandwidth of N in the consensus. Then instead of choosing
714  * N for position p proportionally to Wpf*B or Wpn*B, clients should
715  * choose N proportionally to F*Wpf*B + (1-F)*Wpn*B.
716  */
717  if (node->rs && node->rs->has_guardfraction && rule != WEIGHT_FOR_GUARD) {
718  /* XXX The assert should actually check for is_guard. However,
719  * that crashes dirauths because of #13297. This should be
720  * equivalent: */
721  tor_assert(node->rs->is_possible_guard);
722 
723  guard_get_guardfraction_bandwidth(&guardfraction_bw,
724  this_bw,
725  node->rs->guardfraction_percentage);
726 
727  /* Calculate final_weight = F*Wpf*B + (1-F)*Wpn*B */
728  final_weight =
729  guardfraction_bw.guard_bw * weight +
730  guardfraction_bw.non_guard_bw * weight_without_guard_flag;
731 
732  log_debug(LD_GENERAL, "%s: Guardfraction weight %f instead of %f (%s)",
733  node->rs->nickname, final_weight, weight*this_bw,
735  } else { /* no guardfraction information. calculate the weight normally. */
736  final_weight = weight*this_bw;
737  }
738 
739  bandwidths[node_sl_idx] = final_weight;
740  total_bandwidth += final_weight;
741  } SMARTLIST_FOREACH_END(node);
742 
743  log_debug(LD_CIRC, "Generated weighted bandwidths for rule %s based "
744  "on weights "
745  "Wg=%f Wm=%f We=%f Wd=%f with total bw %f",
747  Wg, Wm, We, Wd, total_bandwidth);
748 
749  *bandwidths_out = bandwidths;
750 
751  if (total_bandwidth_out) {
752  *total_bandwidth_out = total_bandwidth;
753  }
754 
755  return 0;
756 }
757 
765 double
768  int for_direct_conn)
769 {
770  double *bandwidths = NULL;
771  double total, present;
772 
773  if (smartlist_len(sl) == 0)
774  return 0.0;
775 
776  if (compute_weighted_bandwidths(sl, rule, &bandwidths, &total) < 0 ||
777  total <= 0.0) {
778  int n_with_descs = 0;
779  SMARTLIST_FOREACH(sl, const node_t *, node, {
780  if (node_has_preferred_descriptor(node, for_direct_conn))
781  n_with_descs++;
782  });
783  tor_free(bandwidths);
784  return ((double)n_with_descs) / smartlist_len(sl);
785  }
786 
787  present = 0.0;
788  SMARTLIST_FOREACH_BEGIN(sl, const node_t *, node) {
789  if (node_has_preferred_descriptor(node, for_direct_conn))
790  present += bandwidths[node_sl_idx];
791  } SMARTLIST_FOREACH_END(node);
792 
793  tor_free(bandwidths);
794 
795  return present / total;
796 }
797 
800 const node_t *
803 { /*XXXX MOVE */
805 }
806 
813 static void
815 {
816  /* XXXX MOVE ? */
817  node_t fake_node;
818  const node_t *node = node_get_by_id(router->cache_info.identity_digest);
819  if (node == NULL) {
820  memset(&fake_node, 0, sizeof(fake_node));
821  fake_node.ri = (routerinfo_t *)router;
822  memcpy(fake_node.identity, router->cache_info.identity_digest, DIGEST_LEN);
823  node = &fake_node;
824  }
826 }
827 
848 const node_t *
850  routerset_t *excludedset,
851  router_crn_flags_t flags)
852 { /* XXXX MOVE */
853  const int need_uptime = (flags & CRN_NEED_UPTIME) != 0;
854  const int need_capacity = (flags & CRN_NEED_CAPACITY) != 0;
855  const int need_guard = (flags & CRN_NEED_GUARD) != 0;
856  const int weight_for_exit = (flags & CRN_WEIGHT_AS_EXIT) != 0;
857  const int need_desc = (flags & CRN_NEED_DESC) != 0;
858  const int pref_addr = (flags & CRN_PREF_ADDR) != 0;
859  const int direct_conn = (flags & CRN_DIRECT_CONN) != 0;
860  const int rendezvous_v3 = (flags & CRN_RENDEZVOUS_V3) != 0;
861 
862  smartlist_t *sl=smartlist_new(),
863  *excludednodes=smartlist_new();
864  const node_t *choice = NULL;
865  const routerinfo_t *r;
867 
868  tor_assert(!(weight_for_exit && need_guard));
869  rule = weight_for_exit ? WEIGHT_FOR_EXIT :
870  (need_guard ? WEIGHT_FOR_GUARD : WEIGHT_FOR_MID);
871 
872  SMARTLIST_FOREACH_BEGIN(nodelist_get_list(), node_t *, node) {
873  if (node_allows_single_hop_exits(node)) {
874  /* Exclude relays that allow single hop exit circuits. This is an
875  * obsolete option since 0.2.9.2-alpha and done by default in
876  * 0.3.1.0-alpha. */
877  smartlist_add(excludednodes, node);
878  } else if (rendezvous_v3 &&
880  /* Exclude relays that do not support to rendezvous for a hidden service
881  * version 3. */
882  smartlist_add(excludednodes, node);
883  }
884  } SMARTLIST_FOREACH_END(node);
885 
886  /* If the node_t is not found we won't be to exclude ourself but we
887  * won't be able to pick ourself in router_choose_random_node() so
888  * this is fine to at least try with our routerinfo_t object. */
889  if ((r = router_get_my_routerinfo()))
890  routerlist_add_node_and_family(excludednodes, r);
891 
892  router_add_running_nodes_to_smartlist(sl, need_uptime, need_capacity,
893  need_guard, need_desc, pref_addr,
894  direct_conn);
895  log_debug(LD_CIRC,
896  "We found %d running nodes.",
897  smartlist_len(sl));
898 
899  smartlist_subtract(sl,excludednodes);
900  log_debug(LD_CIRC,
901  "We removed %d excludednodes, leaving %d nodes.",
902  smartlist_len(excludednodes),
903  smartlist_len(sl));
904 
905  if (excludedsmartlist) {
906  smartlist_subtract(sl,excludedsmartlist);
907  log_debug(LD_CIRC,
908  "We removed %d excludedsmartlist, leaving %d nodes.",
909  smartlist_len(excludedsmartlist),
910  smartlist_len(sl));
911  }
912  if (excludedset) {
913  routerset_subtract_nodes(sl,excludedset);
914  log_debug(LD_CIRC,
915  "We removed excludedset, leaving %d nodes.",
916  smartlist_len(sl));
917  }
918 
919  // Always weight by bandwidth
920  choice = node_sl_choose_by_bandwidth(sl, rule);
921 
922  smartlist_free(sl);
923  if (!choice && (need_uptime || need_capacity || need_guard || pref_addr)) {
924  /* try once more -- recurse but with fewer restrictions. */
925  log_info(LD_CIRC,
926  "We couldn't find any live%s%s%s routers; falling back "
927  "to list of all routers.",
928  need_capacity?", fast":"",
929  need_uptime?", stable":"",
930  need_guard?", guard":"");
931  flags &= ~ (CRN_NEED_UPTIME|CRN_NEED_CAPACITY|CRN_NEED_GUARD|
932  CRN_PREF_ADDR);
933  choice = router_choose_random_node(
934  excludedsmartlist, excludedset, flags);
935  }
936  smartlist_free(excludednodes);
937  if (!choice) {
938  log_warn(LD_CIRC,
939  "No available nodes when trying to choose node. Failing.");
940  }
941  return choice;
942 }
943 
947 const routerstatus_t *
949 {
952  type, flags);
953 }
954 
958 const routerstatus_t *
960 {
962  router_get_fallback_dir_servers_mutable(),
963  type, flags);
964 }
965 
968 static const dir_server_t *
969 dirserver_choose_by_weight(const smartlist_t *servers, double authority_weight)
970 {
971  int n = smartlist_len(servers);
972  int i;
973  double *weights_dbl;
974  uint64_t *weights_u64;
975  const dir_server_t *ds;
976 
977  weights_dbl = tor_calloc(n, sizeof(double));
978  weights_u64 = tor_calloc(n, sizeof(uint64_t));
979  for (i = 0; i < n; ++i) {
980  ds = smartlist_get(servers, i);
981  weights_dbl[i] = ds->weight;
982  if (ds->is_authority)
983  weights_dbl[i] *= authority_weight;
984  }
985 
986  scale_array_elements_to_u64(weights_u64, weights_dbl, n, NULL);
987  i = choose_array_element_by_weight(weights_u64, n);
988  tor_free(weights_dbl);
989  tor_free(weights_u64);
990  return (i < 0) ? NULL : smartlist_get(servers, i);
991 }
992 
996 static const routerstatus_t *
998  dirinfo_type_t type, int flags,
999  int *n_busy_out)
1000 {
1001  const or_options_t *options = get_options();
1002  smartlist_t *direct, *tunnel;
1003  smartlist_t *overloaded_direct, *overloaded_tunnel;
1004  const routerinfo_t *me = router_get_my_routerinfo();
1005  const routerstatus_t *result = NULL;
1006  time_t now = time(NULL);
1007  const int requireother = ! (flags & PDS_ALLOW_SELF);
1008  const int fascistfirewall = ! (flags & PDS_IGNORE_FASCISTFIREWALL);
1009  const int no_serverdesc_fetching =(flags & PDS_NO_EXISTING_SERVERDESC_FETCH);
1010  const int no_microdesc_fetching =(flags & PDS_NO_EXISTING_MICRODESC_FETCH);
1011  const double auth_weight =
1012  (sourcelist == router_get_fallback_dir_servers()) ?
1013  options->DirAuthorityFallbackRate : 1.0;
1014  smartlist_t *pick_from;
1015  int n_busy = 0;
1016  int try_excluding = 1, n_excluded = 0;
1017  int try_ip_pref = 1;
1018 
1019  if (!sourcelist)
1020  return NULL;
1021 
1022  retry_search:
1023 
1024  direct = smartlist_new();
1025  tunnel = smartlist_new();
1026  overloaded_direct = smartlist_new();
1027  overloaded_tunnel = smartlist_new();
1028 
1029  const int skip_or_fw = router_skip_or_reachability(options, try_ip_pref);
1030  const int skip_dir_fw = router_skip_dir_reachability(options, try_ip_pref);
1031  const int must_have_or = directory_must_use_begindir(options);
1032 
1033  SMARTLIST_FOREACH_BEGIN(sourcelist, const dir_server_t *, d)
1034  {
1035  int is_overloaded =
1036  d->fake_status.last_dir_503_at + DIR_503_TIMEOUT > now;
1037  if (!d->is_running) continue;
1038  if ((type & d->type) == 0)
1039  continue;
1040 
1041  SKIP_MISSING_TRUSTED_EXTRAINFO(type, d->digest);
1042 
1043  if (requireother && me && router_digest_is_me(d->digest))
1044  continue;
1045  if (try_excluding &&
1047  &d->fake_status, -1)) {
1048  ++n_excluded;
1049  continue;
1050  }
1051 
1052  if (router_is_already_dir_fetching_(d->addr,
1053  &d->ipv6_addr,
1054  d->dir_port,
1055  no_serverdesc_fetching,
1056  no_microdesc_fetching)) {
1057  ++n_busy;
1058  continue;
1059  }
1060 
1061  /* Clients use IPv6 addresses if the server has one and the client
1062  * prefers IPv6.
1063  * Add the router if its preferred address and port are reachable.
1064  * If we don't get any routers, we'll try again with the non-preferred
1065  * address for each router (if any). (To ensure correct load-balancing
1066  * we try routers that only have one address both times.)
1067  */
1068  if (!fascistfirewall || skip_or_fw ||
1069  fascist_firewall_allows_dir_server(d, FIREWALL_OR_CONNECTION,
1070  try_ip_pref))
1071  smartlist_add(is_overloaded ? overloaded_tunnel : tunnel, (void*)d);
1072  else if (!must_have_or && (skip_dir_fw ||
1073  fascist_firewall_allows_dir_server(d, FIREWALL_DIR_CONNECTION,
1074  try_ip_pref)))
1075  smartlist_add(is_overloaded ? overloaded_direct : direct, (void*)d);
1076  }
1077  SMARTLIST_FOREACH_END(d);
1078 
1079  if (smartlist_len(tunnel)) {
1080  pick_from = tunnel;
1081  } else if (smartlist_len(overloaded_tunnel)) {
1082  pick_from = overloaded_tunnel;
1083  } else if (smartlist_len(direct)) {
1084  pick_from = direct;
1085  } else {
1086  pick_from = overloaded_direct;
1087  }
1088 
1089  {
1090  const dir_server_t *selection =
1091  dirserver_choose_by_weight(pick_from, auth_weight);
1092 
1093  if (selection)
1094  result = &selection->fake_status;
1095  }
1096 
1097  smartlist_free(direct);
1098  smartlist_free(tunnel);
1099  smartlist_free(overloaded_direct);
1100  smartlist_free(overloaded_tunnel);
1101 
1102  RETRY_ALTERNATE_IP_VERSION(retry_search);
1103 
1104  RETRY_WITHOUT_EXCLUDE(retry_search);
1105 
1106  router_picked_poor_directory_log(result);
1107 
1108  if (n_busy_out)
1109  *n_busy_out = n_busy;
1110  return result;
1111 }
Header file for dirclient.c.
int node_allows_single_hop_exits(const node_t *node)
Definition: nodelist.c:1408
static void routerlist_add_node_and_family(smartlist_t *sl, const routerinfo_t *router)
Definition: node_select.c:814
Header file for circuitbuild.c.
Common functions for using (pseudo-)random number generators.
Definition: node_st.h:28
#define SMARTLIST_FOREACH_BEGIN(sl, type, var)
int64_t tor_llround(double d)
Definition: fp.c:46
Header file for node_select.c.
Header file for connection.c.
#define LD_GENERAL
Definition: log.h:58
const routerstatus_t * router_pick_trusteddirserver(dirinfo_type_t type, int flags)
Definition: node_select.c:948
int fascist_firewall_allows_rs(const routerstatus_t *rs, firewall_connection_t fw_connection, int pref_only)
Definition: policies.c:686
#define PDS_NO_EXISTING_SERVERDESC_FETCH
Definition: node_select.h:61
Header file for describe.c.
Header file for nodelist.c.
Header file for directory.c.
void smartlist_add(smartlist_t *sl, void *element)
Header file for config.c.
#define BRIDGE_MIN_BELIEVABLE_BANDWIDTH
Definition: node_select.c:523
Header file for microdesc.c.
const routerstatus_t * router_pick_directory_server(dirinfo_type_t type, int flags)
Definition: node_select.c:70
#define tor_free(p)
Definition: malloc.h:52
int node_has_preferred_descriptor(const node_t *node, int for_direct_connect)
Definition: nodelist.c:1340
dirinfo_type_t
Definition: or.h:887
STATIC const routerstatus_t * router_pick_directory_server_impl(dirinfo_type_t type, int flags, int *n_busy_out)
Definition: node_select.c:293
#define DIR_PURPOSE_FETCH_EXTRAINFO
Definition: directory.h:41
smartlist_t * router_get_trusted_dir_servers_mutable(void)
Definition: dirlist.c:71
#define PDS_IGNORE_FASCISTFIREWALL
Definition: node_select.h:54
Header file for policies.c.
static const routerstatus_t * router_pick_dirserver_generic(smartlist_t *sourcelist, dirinfo_type_t type, int flags)
Definition: node_select.c:102
uint32_t bandwidthrate
Definition: routerinfo_st.h:51
void nodelist_add_node_and_family(smartlist_t *sl, const node_t *node)
Definition: nodelist.c:2099
double frac_nodes_with_descriptors(const smartlist_t *sl, bandwidth_weight_rule_t rule, int for_direct_conn)
Definition: node_select.c:766
int node_is_dir(const node_t *node)
Definition: nodelist.c:1304
#define DIR_PURPOSE_FETCH_SERVERDESC
Definition: directory.h:38
tor_assert(buffer)
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:423
#define PDS_ALLOW_SELF
Definition: node_select.h:44
int32_t networkstatus_get_bw_weight(networkstatus_t *ns, const char *weight_name, int32_t default_val)
#define tor_addr_from_ipv4h(dest, v4addr)
Definition: address.h:287
Header for fp.c.
#define LD_CIRC
Definition: log.h:78
static const node_t * smartlist_choose_node_by_bandwidth_weights(const smartlist_t *sl, bandwidth_weight_rule_t rule)
Definition: node_select.c:498
Header file for routermode.c.
routerset_t * ExcludeNodes
Definition: or_options_st.h:84
#define DIGEST_LEN
Definition: digest_sizes.h:20
char identity[DIGEST_LEN]
Definition: node_st.h:40
Master header file for Tor-specific functionality.
routerstatus_t fake_status
Definition: dir_server_st.h:46
int crypto_rand_int(unsigned int max)
double DirAuthorityFallbackRate
uint64_t crypto_rand_uint64(uint64_t max)
const char * fmt_addr32(uint32_t addr)
Definition: address.c:1180
tor_addr_t ipv6_addr
int tor_addr_is_null(const tor_addr_t *addr)
Definition: address.c:769
const node_t * router_choose_random_node(smartlist_t *excludedsmartlist, routerset_t *excludedset, router_crn_flags_t flags)
Definition: node_select.c:849
const char * routerstatus_describe(const routerstatus_t *rs)
Definition: describe.c:134
#define PDS_RETRY_IF_NO_SERVERS
Definition: node_select.h:48
static const dir_server_t * dirserver_choose_by_weight(const smartlist_t *servers, double authority_weight)
Definition: node_select.c:969
router_crn_flags_t
Definition: node_select.h:16
int select_array_member_cumulative_timei(const uint64_t *entries, int n_entries, uint64_t total, uint64_t rand_val)
Definition: di_ops.c:256
#define LD_DIR
Definition: log.h:84
void smartlist_subtract(smartlist_t *sl1, const smartlist_t *sl2)
Definition: smartlist.c:264
void router_reset_status_download_failures(void)
Definition: dirlist.c:103
char identity_digest[DIGEST_LEN]
void router_add_running_nodes_to_smartlist(smartlist_t *sl, int need_uptime, int need_capacity, int need_guard, int need_desc, int pref_addr, int direct_conn)
Definition: routerlist.c:504
const char * bandwidth_weight_rule_to_string(bandwidth_weight_rule_t rule)
Definition: reasons.c:435
int node_supports_v3_rendezvous_point(const node_t *node)
Definition: nodelist.c:1172
bandwidth_weight_rule_t
Definition: node_select.h:35
#define SMARTLIST_FOREACH(sl, type, var, cmd)
static int32_t kb_to_bytes(uint32_t bw)
Definition: node_select.c:478
Header file for router.c.
static uint32_t bridge_get_advertised_bandwidth_bounded(routerinfo_t *router)
Definition: node_select.c:531
void routerset_subtract_nodes(smartlist_t *lst, const routerset_t *routerset)
Definition: routerset.c:394
STATIC int choose_array_element_by_weight(const uint64_t *entries, int n_entries)
Definition: node_select.c:452
#define fmt_addr(a)
Definition: address.h:211
int fascist_firewall_allows_node(const node_t *node, firewall_connection_t fw_connection, int pref_only)
Definition: policies.c:732
int router_digest_is_me(const char *digest)
Definition: router.c:1589
int fascist_firewall_allows_dir_server(const dir_server_t *ds, firewall_connection_t fw_connection, int pref_only)
Definition: policies.c:770
#define DIR_PURPOSE_FETCH_MICRODESC
Definition: directory.h:70
const node_t * node_sl_choose_by_bandwidth(const smartlist_t *sl, bandwidth_weight_rule_t rule)
Definition: node_select.c:801
uint32_t bandwidthcapacity
Definition: routerinfo_st.h:55
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:551
Header file for dirlist.c.
#define PDS_NO_EXISTING_MICRODESC_FETCH
Definition: node_select.h:67
int networkstatus_get_weight_scale_param(networkstatus_t *ns)
Header file for reasons.c.
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:997
void mark_all_dirservers_up(smartlist_t *server_list)
Definition: dirlist.c:184
uint16_t ipv6_orport
#define CONN_TYPE_DIR
Definition: connection.h:35
#define DIR_503_TIMEOUT
Definition: routerlist.h:46
int routerset_contains_routerstatus(const routerset_t *set, const routerstatus_t *rs, country_t country)
Definition: routerset.c:318
void tor_addr_copy(tor_addr_t *dest, const tor_addr_t *src)
Definition: address.c:903
Header file for networkstatus.c.
#define LD_BUG
Definition: log.h:82
unsigned int is_authority
Definition: dir_server_st.h:33
Header file for routerlist.c.
void * smartlist_choose(const smartlist_t *sl)
Definition: crypto_rand.c:589
const routerstatus_t * router_pick_fallback_dirserver(dirinfo_type_t type, int flags)
Definition: node_select.c:959