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