Tor  0.4.4.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  && fascist_firewall_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 (!fascist_firewall_allows_rs(rs, FIREWALL_OR_CONNECTION, 1)
216  && !fascist_firewall_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  log_info(LD_DIR, "Selected a directory %s with non-preferred OR and Dir "
221  "addresses for launching an outgoing connection: "
222  "IPv4 %s OR %d Dir %d IPv6 %s OR %d Dir %d",
224  fmt_addr32(rs->addr), rs->or_port,
225  rs->dir_port, fmt_addr(&rs->ipv6_addr),
226  rs->ipv6_orport, rs->dir_port);
227  }
228 }
229 
230 #undef LOG_FALSE_POSITIVES_DURING_BOOTSTRAP
231 
232 /* Check if we already have a directory fetch from ap, for serverdesc
233  * (including extrainfo) or microdesc documents.
234  * If so, return 1, if not, return 0.
235  * Also returns 0 if addr is NULL, tor_addr_is_null(addr), or dir_port is 0.
236  */
237 STATIC int
238 router_is_already_dir_fetching(const tor_addr_port_t *ap, int serverdesc,
239  int microdesc)
240 {
241  if (!ap || tor_addr_is_null(&ap->addr) || !ap->port) {
242  return 0;
243  }
244 
245  /* XX/teor - we're not checking tunnel connections here, see #17848
246  */
247  if (serverdesc && (
249  CONN_TYPE_DIR, &ap->addr, ap->port, DIR_PURPOSE_FETCH_SERVERDESC)
251  CONN_TYPE_DIR, &ap->addr, ap->port, DIR_PURPOSE_FETCH_EXTRAINFO))) {
252  return 1;
253  }
254 
255  if (microdesc && (
257  CONN_TYPE_DIR, &ap->addr, ap->port, DIR_PURPOSE_FETCH_MICRODESC))) {
258  return 1;
259  }
260 
261  return 0;
262 }
263 
264 /* Check if we already have a directory fetch from the ipv4 or ipv6
265  * router, for serverdesc (including extrainfo) or microdesc documents.
266  * If so, return 1, if not, return 0.
267  */
268 static int
269 router_is_already_dir_fetching_(uint32_t ipv4_addr,
270  const tor_addr_t *ipv6_addr,
271  uint16_t dir_port,
272  int serverdesc,
273  int microdesc)
274 {
275  tor_addr_port_t ipv4_dir_ap, ipv6_dir_ap;
276 
277  /* Assume IPv6 DirPort is the same as IPv4 DirPort */
278  tor_addr_from_ipv4h(&ipv4_dir_ap.addr, ipv4_addr);
279  ipv4_dir_ap.port = dir_port;
280  tor_addr_copy(&ipv6_dir_ap.addr, ipv6_addr);
281  ipv6_dir_ap.port = dir_port;
282 
283  return (router_is_already_dir_fetching(&ipv4_dir_ap, serverdesc, microdesc)
284  || router_is_already_dir_fetching(&ipv6_dir_ap, serverdesc, microdesc));
285 }
286 
287 /** Pick a random running valid directory server/mirror from our
288  * routerlist. Arguments are as for router_pick_directory_server(), except:
289  *
290  * If <b>n_busy_out</b> is provided, set *<b>n_busy_out</b> to the number of
291  * directories that we excluded for no other reason than
292  * PDS_NO_EXISTING_SERVERDESC_FETCH or PDS_NO_EXISTING_MICRODESC_FETCH.
293  */
294 STATIC const routerstatus_t *
296  int *n_busy_out)
297 {
298  const or_options_t *options = get_options();
299  const node_t *result;
300  smartlist_t *direct, *tunnel;
301  smartlist_t *trusted_direct, *trusted_tunnel;
302  smartlist_t *overloaded_direct, *overloaded_tunnel;
303  time_t now = time(NULL);
305  const int requireother = ! (flags & PDS_ALLOW_SELF);
306  const int fascistfirewall = ! (flags & PDS_IGNORE_FASCISTFIREWALL);
307  const int no_serverdesc_fetching =(flags & PDS_NO_EXISTING_SERVERDESC_FETCH);
308  const int no_microdesc_fetching = (flags & PDS_NO_EXISTING_MICRODESC_FETCH);
309  int try_excluding = 1, n_excluded = 0, n_busy = 0;
310  int try_ip_pref = 1;
311 
312  if (!consensus)
313  return NULL;
314 
315  retry_search:
316 
317  direct = smartlist_new();
318  tunnel = smartlist_new();
319  trusted_direct = smartlist_new();
320  trusted_tunnel = smartlist_new();
321  overloaded_direct = smartlist_new();
322  overloaded_tunnel = smartlist_new();
323 
324  const int skip_or_fw = router_skip_or_reachability(options, try_ip_pref);
325  const int skip_dir_fw = router_skip_dir_reachability(options, try_ip_pref);
326  const int must_have_or = dirclient_must_use_begindir(options);
327 
328  /* Find all the running dirservers we know about. */
330  int is_trusted;
331  int is_overloaded;
332  const routerstatus_t *status = node->rs;
333  const country_t country = node->country;
334  if (!status)
335  continue;
336 
337  if (!node->is_running || !node_is_dir(node) || !node->is_valid)
338  continue;
339  if (requireother && router_digest_is_me(node->identity))
340  continue;
341 
342  SKIP_MISSING_TRUSTED_EXTRAINFO(type, node->identity);
343 
344  if (try_excluding &&
346  country)) {
347  ++n_excluded;
348  continue;
349  }
350 
351  if (router_is_already_dir_fetching_(status->addr,
352  &status->ipv6_addr,
353  status->dir_port,
354  no_serverdesc_fetching,
355  no_microdesc_fetching)) {
356  ++n_busy;
357  continue;
358  }
359 
360  is_overloaded = status->last_dir_503_at + DIR_503_TIMEOUT > now;
361  is_trusted = router_digest_is_trusted_dir(node->identity);
362 
363  /* Clients use IPv6 addresses if the server has one and the client
364  * prefers IPv6.
365  * Add the router if its preferred address and port are reachable.
366  * If we don't get any routers, we'll try again with the non-preferred
367  * address for each router (if any). (To ensure correct load-balancing
368  * we try routers that only have one address both times.)
369  */
370  if (!fascistfirewall || skip_or_fw ||
371  fascist_firewall_allows_node(node, FIREWALL_OR_CONNECTION,
372  try_ip_pref))
373  smartlist_add(is_trusted ? trusted_tunnel :
374  is_overloaded ? overloaded_tunnel : tunnel, (void*)node);
375  else if (!must_have_or && (skip_dir_fw ||
376  fascist_firewall_allows_node(node, FIREWALL_DIR_CONNECTION,
377  try_ip_pref)))
378  smartlist_add(is_trusted ? trusted_direct :
379  is_overloaded ? overloaded_direct : direct, (void*)node);
380  } SMARTLIST_FOREACH_END(node);
381 
382  if (smartlist_len(tunnel)) {
383  result = node_sl_choose_by_bandwidth(tunnel, WEIGHT_FOR_DIR);
384  } else if (smartlist_len(overloaded_tunnel)) {
385  result = node_sl_choose_by_bandwidth(overloaded_tunnel,
386  WEIGHT_FOR_DIR);
387  } else if (smartlist_len(trusted_tunnel)) {
388  /* FFFF We don't distinguish between trusteds and overloaded trusteds
389  * yet. Maybe one day we should. */
390  /* FFFF We also don't load balance over authorities yet. I think this
391  * is a feature, but it could easily be a bug. -RD */
392  result = smartlist_choose(trusted_tunnel);
393  } else if (smartlist_len(direct)) {
394  result = node_sl_choose_by_bandwidth(direct, WEIGHT_FOR_DIR);
395  } else if (smartlist_len(overloaded_direct)) {
396  result = node_sl_choose_by_bandwidth(overloaded_direct,
397  WEIGHT_FOR_DIR);
398  } else {
399  result = smartlist_choose(trusted_direct);
400  }
401  smartlist_free(direct);
402  smartlist_free(tunnel);
403  smartlist_free(trusted_direct);
404  smartlist_free(trusted_tunnel);
405  smartlist_free(overloaded_direct);
406  smartlist_free(overloaded_tunnel);
407 
408  RETRY_ALTERNATE_IP_VERSION(retry_search);
409 
410  RETRY_WITHOUT_EXCLUDE(retry_search);
411 
412  if (n_busy_out)
413  *n_busy_out = n_busy;
414 
415  router_picked_poor_directory_log(result ? result->rs : NULL);
416 
417  return result ? result->rs : NULL;
418 }
419 
420 /** Given an array of double/uint64_t unions that are currently being used as
421  * doubles, convert them to uint64_t, and try to scale them linearly so as to
422  * much of the range of uint64_t. If <b>total_out</b> is provided, set it to
423  * the sum of all elements in the array _before_ scaling. */
424 STATIC void
425 scale_array_elements_to_u64(uint64_t *entries_out, const double *entries_in,
426  int n_entries,
427  uint64_t *total_out)
428 {
429  double total = 0.0;
430  double scale_factor = 0.0;
431  int i;
432 
433  for (i = 0; i < n_entries; ++i)
434  total += entries_in[i];
435 
436  if (total > 0.0) {
437  scale_factor = ((double)INT64_MAX) / total;
438  scale_factor /= 4.0; /* make sure we're very far away from overflowing */
439  }
440 
441  for (i = 0; i < n_entries; ++i)
442  entries_out[i] = tor_llround(entries_in[i] * scale_factor);
443 
444  if (total_out)
445  *total_out = (uint64_t) total;
446 }
447 
448 /** Pick a random element of <b>n_entries</b>-element array <b>entries</b>,
449  * choosing each element with a probability proportional to its (uint64_t)
450  * value, and return the index of that element. If all elements are 0, choose
451  * an index at random. Return -1 on error.
452  */
453 STATIC int
454 choose_array_element_by_weight(const uint64_t *entries, int n_entries)
455 {
456  int i;
457  uint64_t rand_val;
458  uint64_t total = 0;
459 
460  for (i = 0; i < n_entries; ++i)
461  total += entries[i];
462 
463  if (n_entries < 1)
464  return -1;
465 
466  if (total == 0)
467  return crypto_rand_int(n_entries);
468 
469  tor_assert(total < INT64_MAX);
470 
471  rand_val = crypto_rand_uint64(total);
472 
474  entries, n_entries, total, rand_val);
475 }
476 
477 /** Return bw*1000, unless bw*1000 would overflow, in which case return
478  * INT32_MAX. */
479 static inline int32_t
480 kb_to_bytes(uint32_t bw)
481 {
482  return (bw > (INT32_MAX/1000)) ? INT32_MAX : bw*1000;
483 }
484 
485 /** Helper function:
486  * choose a random element of smartlist <b>sl</b> of nodes, weighted by
487  * the advertised bandwidth of each element using the consensus
488  * bandwidth weights.
489  *
490  * If <b>rule</b>==WEIGHT_FOR_EXIT. we're picking an exit node: consider all
491  * nodes' bandwidth equally regardless of their Exit status, since there may
492  * be some in the list because they exit to obscure ports. If
493  * <b>rule</b>==NO_WEIGHTING, we're picking a non-exit node: weight
494  * exit-node's bandwidth less depending on the smallness of the fraction of
495  * Exit-to-total bandwidth. If <b>rule</b>==WEIGHT_FOR_GUARD, we're picking a
496  * guard node: consider all guard's bandwidth equally. Otherwise, weight
497  * guards proportionally less.
498  */
499 static const node_t *
502 {
503  double *bandwidths_dbl=NULL;
504  uint64_t *bandwidths_u64=NULL;
505 
506  if (compute_weighted_bandwidths(sl, rule, &bandwidths_dbl, NULL) < 0)
507  return NULL;
508 
509  bandwidths_u64 = tor_calloc(smartlist_len(sl), sizeof(uint64_t));
510  scale_array_elements_to_u64(bandwidths_u64, bandwidths_dbl,
511  smartlist_len(sl), NULL);
512 
513  {
514  int idx = choose_array_element_by_weight(bandwidths_u64,
515  smartlist_len(sl));
516  tor_free(bandwidths_dbl);
517  tor_free(bandwidths_u64);
518  return idx < 0 ? NULL : smartlist_get(sl, idx);
519  }
520 }
521 
522 /** When weighting bridges, enforce these values as lower and upper
523  * bound for believable bandwidth, because there is no way for us
524  * to verify a bridge's bandwidth currently. */
525 #define BRIDGE_MIN_BELIEVABLE_BANDWIDTH 20000 /* 20 kB/sec */
526 #define BRIDGE_MAX_BELIEVABLE_BANDWIDTH 100000 /* 100 kB/sec */
527 
528 /** Return the smaller of the router's configured BandwidthRate
529  * and its advertised capacity, making sure to stay within the
530  * interval between bridge-min-believe-bw and
531  * bridge-max-believe-bw. */
532 static uint32_t
534 {
535  uint32_t result = router->bandwidthcapacity;
536  if (result > router->bandwidthrate)
537  result = router->bandwidthrate;
538  if (result > BRIDGE_MAX_BELIEVABLE_BANDWIDTH)
539  result = BRIDGE_MAX_BELIEVABLE_BANDWIDTH;
540  else if (result < BRIDGE_MIN_BELIEVABLE_BANDWIDTH)
542  return result;
543 }
544 
545 /**
546  * We have found an instance of bug 32868: log our best guess about where the
547  * routerstatus was found.
548  **/
549 static void
551 {
552  static ratelim_t buggy_rs_ratelim = RATELIM_INIT(1200);
553  char *m;
554  if ((m = rate_limit_log(&buggy_rs_ratelim, approx_time()))) {
555  log_warn(LD_BUG,
556  "Found a routerstatus %p with has_guardfraction=%u "
557  " and guardfraction_percentage=%u, but is_possible_guard=%u.%s",
558  rs,
559  rs->has_guardfraction,
561  rs->is_possible_guard,
562  m);
563  tor_free(m);
564  networkstatus_t *ns;
565  int in_ns_count = 0;
566  if ((ns = networkstatus_get_latest_consensus_by_flavor(FLAV_NS))) {
567  int pos = smartlist_pos(ns->routerstatus_list, rs);
568  if (pos >= 0) {
569  ++in_ns_count;
570  log_warn(LD_BUG, "Found the routerstatus at position %d of the "
571  "NS consensus.", pos);
572  }
573  }
574  if ((ns = networkstatus_get_latest_consensus_by_flavor(FLAV_MICRODESC))) {
575  int pos = smartlist_pos(ns->routerstatus_list, rs);
576  if (pos >= 0) {
577  ++in_ns_count;
578  log_warn(LD_BUG, "Found the routerstatus at position %d of the "
579  "MD consensus.", pos);
580  }
581  }
582  if (in_ns_count == 0) {
583  log_warn(LD_BUG, "Could not find the routerstatus in any "
584  "latest consensus.");
585  }
586  tor_assert_nonfatal_unreached();
587  }
588 }
589 
590 /** Given a list of routers and a weighting rule as in
591  * smartlist_choose_node_by_bandwidth_weights, compute weighted bandwidth
592  * values for each node and store them in a freshly allocated
593  * *<b>bandwidths_out</b> of the same length as <b>sl</b>, and holding results
594  * as doubles. If <b>total_bandwidth_out</b> is non-NULL, set it to the total
595  * of all the bandwidths.
596  * Return 0 on success, -1 on failure. */
597 static int
600  double **bandwidths_out,
601  double *total_bandwidth_out)
602 {
603  int64_t weight_scale;
604  double Wg = -1, Wm = -1, We = -1, Wd = -1;
605  double Wgb = -1, Wmb = -1, Web = -1, Wdb = -1;
606  guardfraction_bandwidth_t guardfraction_bw;
607  double *bandwidths = NULL;
608  double total_bandwidth = 0.0;
609 
610  tor_assert(sl);
611  tor_assert(bandwidths_out);
612 
613  /* Can't choose exit and guard at same time */
614  tor_assert(rule == NO_WEIGHTING ||
615  rule == WEIGHT_FOR_EXIT ||
616  rule == WEIGHT_FOR_GUARD ||
617  rule == WEIGHT_FOR_MID ||
618  rule == WEIGHT_FOR_DIR);
619 
620  *bandwidths_out = NULL;
621 
622  if (total_bandwidth_out) {
623  *total_bandwidth_out = 0.0;
624  }
625 
626  if (smartlist_len(sl) == 0) {
627  log_info(LD_CIRC,
628  "Empty routerlist passed in to consensus weight node "
629  "selection for rule %s",
631  return -1;
632  }
633 
634  weight_scale = networkstatus_get_weight_scale_param(NULL);
635  tor_assert(weight_scale >= 1);
636 
637  if (rule == WEIGHT_FOR_GUARD) {
638  Wg = networkstatus_get_bw_weight(NULL, "Wgg", -1);
639  Wm = networkstatus_get_bw_weight(NULL, "Wgm", -1); /* Bridges */
640  We = 0;
641  Wd = networkstatus_get_bw_weight(NULL, "Wgd", -1);
642 
643  Wgb = networkstatus_get_bw_weight(NULL, "Wgb", -1);
644  Wmb = networkstatus_get_bw_weight(NULL, "Wmb", -1);
645  Web = networkstatus_get_bw_weight(NULL, "Web", -1);
646  Wdb = networkstatus_get_bw_weight(NULL, "Wdb", -1);
647  } else if (rule == WEIGHT_FOR_MID) {
648  Wg = networkstatus_get_bw_weight(NULL, "Wmg", -1);
649  Wm = networkstatus_get_bw_weight(NULL, "Wmm", -1);
650  We = networkstatus_get_bw_weight(NULL, "Wme", -1);
651  Wd = networkstatus_get_bw_weight(NULL, "Wmd", -1);
652 
653  Wgb = networkstatus_get_bw_weight(NULL, "Wgb", -1);
654  Wmb = networkstatus_get_bw_weight(NULL, "Wmb", -1);
655  Web = networkstatus_get_bw_weight(NULL, "Web", -1);
656  Wdb = networkstatus_get_bw_weight(NULL, "Wdb", -1);
657  } else if (rule == WEIGHT_FOR_EXIT) {
658  // Guards CAN be exits if they have weird exit policies
659  // They are d then I guess...
660  We = networkstatus_get_bw_weight(NULL, "Wee", -1);
661  Wm = networkstatus_get_bw_weight(NULL, "Wem", -1); /* Odd exit policies */
662  Wd = networkstatus_get_bw_weight(NULL, "Wed", -1);
663  Wg = networkstatus_get_bw_weight(NULL, "Weg", -1); /* Odd exit policies */
664 
665  Wgb = networkstatus_get_bw_weight(NULL, "Wgb", -1);
666  Wmb = networkstatus_get_bw_weight(NULL, "Wmb", -1);
667  Web = networkstatus_get_bw_weight(NULL, "Web", -1);
668  Wdb = networkstatus_get_bw_weight(NULL, "Wdb", -1);
669  } else if (rule == WEIGHT_FOR_DIR) {
670  We = networkstatus_get_bw_weight(NULL, "Wbe", -1);
671  Wm = networkstatus_get_bw_weight(NULL, "Wbm", -1);
672  Wd = networkstatus_get_bw_weight(NULL, "Wbd", -1);
673  Wg = networkstatus_get_bw_weight(NULL, "Wbg", -1);
674 
675  Wgb = Wmb = Web = Wdb = weight_scale;
676  } else if (rule == NO_WEIGHTING) {
677  Wg = Wm = We = Wd = weight_scale;
678  Wgb = Wmb = Web = Wdb = weight_scale;
679  }
680 
681  if (Wg < 0 || Wm < 0 || We < 0 || Wd < 0 || Wgb < 0 || Wmb < 0 || Wdb < 0
682  || Web < 0) {
683  log_debug(LD_CIRC,
684  "Got negative bandwidth weights. Defaulting to naive selection"
685  " algorithm.");
686  Wg = Wm = We = Wd = weight_scale;
687  Wgb = Wmb = Web = Wdb = weight_scale;
688  }
689 
690  Wg /= weight_scale;
691  Wm /= weight_scale;
692  We /= weight_scale;
693  Wd /= weight_scale;
694 
695  Wgb /= weight_scale;
696  Wmb /= weight_scale;
697  Web /= weight_scale;
698  Wdb /= weight_scale;
699 
700  bandwidths = tor_calloc(smartlist_len(sl), sizeof(double));
701 
702  // Cycle through smartlist and total the bandwidth.
703  static int warned_missing_bw = 0;
704  SMARTLIST_FOREACH_BEGIN(sl, const node_t *, node) {
705  int is_exit = 0, is_guard = 0, is_dir = 0, this_bw = 0;
706  double weight = 1;
707  double weight_without_guard_flag = 0; /* Used for guardfraction */
708  double final_weight = 0;
709  is_exit = node->is_exit && ! node->is_bad_exit;
710  is_guard = node->is_possible_guard;
711  is_dir = node_is_dir(node);
712  if (node->rs) {
713  if (!node->rs->has_bandwidth) {
714  /* This should never happen, unless all the authorities downgrade
715  * to 0.2.0 or rogue routerstatuses get inserted into our consensus. */
716  if (! warned_missing_bw) {
717  log_warn(LD_BUG,
718  "Consensus is missing some bandwidths. Using a naive "
719  "router selection algorithm");
720  warned_missing_bw = 1;
721  }
722  this_bw = 30000; /* Chosen arbitrarily */
723  } else {
724  this_bw = kb_to_bytes(node->rs->bandwidth_kb);
725  }
726  } else if (node->ri) {
727  /* bridge or other descriptor not in our consensus */
728  this_bw = bridge_get_advertised_bandwidth_bounded(node->ri);
729  } else {
730  /* We can't use this one. */
731  continue;
732  }
733 
734  if (is_guard && is_exit) {
735  weight = (is_dir ? Wdb*Wd : Wd);
736  weight_without_guard_flag = (is_dir ? Web*We : We);
737  } else if (is_guard) {
738  weight = (is_dir ? Wgb*Wg : Wg);
739  weight_without_guard_flag = (is_dir ? Wmb*Wm : Wm);
740  } else if (is_exit) {
741  weight = (is_dir ? Web*We : We);
742  } else { // middle
743  weight = (is_dir ? Wmb*Wm : Wm);
744  }
745  /* These should be impossible; but overflows here would be bad, so let's
746  * make sure. */
747  if (this_bw < 0)
748  this_bw = 0;
749  if (weight < 0.0)
750  weight = 0.0;
751  if (weight_without_guard_flag < 0.0)
752  weight_without_guard_flag = 0.0;
753 
754  /* If guardfraction information is available in the consensus, we
755  * want to calculate this router's bandwidth according to its
756  * guardfraction. Quoting from proposal236:
757  *
758  * Let Wpf denote the weight from the 'bandwidth-weights' line a
759  * client would apply to N for position p if it had the guard
760  * flag, Wpn the weight if it did not have the guard flag, and B the
761  * measured bandwidth of N in the consensus. Then instead of choosing
762  * N for position p proportionally to Wpf*B or Wpn*B, clients should
763  * choose N proportionally to F*Wpf*B + (1-F)*Wpn*B.
764  */
765  if (node->rs && node->rs->has_guardfraction && rule != WEIGHT_FOR_GUARD) {
766  /* We should only have guardfraction set if the node has the Guard
767  flag. */
768  if (! node->rs->is_possible_guard) {
769  log_buggy_rs_source(node->rs);
770  }
771 
772  guard_get_guardfraction_bandwidth(&guardfraction_bw,
773  this_bw,
774  node->rs->guardfraction_percentage);
775 
776  /* Calculate final_weight = F*Wpf*B + (1-F)*Wpn*B */
777  final_weight =
778  guardfraction_bw.guard_bw * weight +
779  guardfraction_bw.non_guard_bw * weight_without_guard_flag;
780 
781  log_debug(LD_GENERAL, "%s: Guardfraction weight %f instead of %f (%s)",
782  node->rs->nickname, final_weight, weight*this_bw,
784  } else { /* no guardfraction information. calculate the weight normally. */
785  final_weight = weight*this_bw;
786  }
787 
788  bandwidths[node_sl_idx] = final_weight;
789  total_bandwidth += final_weight;
790  } SMARTLIST_FOREACH_END(node);
791 
792  log_debug(LD_CIRC, "Generated weighted bandwidths for rule %s based "
793  "on weights "
794  "Wg=%f Wm=%f We=%f Wd=%f with total bw %f",
796  Wg, Wm, We, Wd, total_bandwidth);
797 
798  *bandwidths_out = bandwidths;
799 
800  if (total_bandwidth_out) {
801  *total_bandwidth_out = total_bandwidth;
802  }
803 
804  return 0;
805 }
806 
807 /** For all nodes in <b>sl</b>, return the fraction of those nodes, weighted
808  * by their weighted bandwidths with rule <b>rule</b>, for which we have
809  * descriptors.
810  *
811  * If <b>for_direct_connect</b> is true, we intend to connect to the node
812  * directly, as the first hop of a circuit; otherwise, we intend to connect
813  * to it indirectly, or use it as if we were connecting to it indirectly. */
814 double
817  int for_direct_conn)
818 {
819  double *bandwidths = NULL;
820  double total, present;
821 
822  if (smartlist_len(sl) == 0)
823  return 0.0;
824 
825  if (compute_weighted_bandwidths(sl, rule, &bandwidths, &total) < 0 ||
826  total <= 0.0) {
827  int n_with_descs = 0;
828  SMARTLIST_FOREACH(sl, const node_t *, node, {
829  if (node_has_preferred_descriptor(node, for_direct_conn))
830  n_with_descs++;
831  });
832  tor_free(bandwidths);
833  return ((double)n_with_descs) / smartlist_len(sl);
834  }
835 
836  present = 0.0;
837  SMARTLIST_FOREACH_BEGIN(sl, const node_t *, node) {
838  if (node_has_preferred_descriptor(node, for_direct_conn))
839  present += bandwidths[node_sl_idx];
840  } SMARTLIST_FOREACH_END(node);
841 
842  tor_free(bandwidths);
843 
844  return present / total;
845 }
846 
847 /** Choose a random element of status list <b>sl</b>, weighted by
848  * the advertised bandwidth of each node */
849 const node_t *
852 { /*XXXX MOVE */
854 }
855 
856 /** Given a <b>router</b>, add every node_t in its family (including the
857  * node itself!) to <b>sl</b>.
858  *
859  * Note the type mismatch: This function takes a routerinfo, but adds nodes
860  * to the smartlist!
861  */
862 static void
864 {
865  /* XXXX MOVE ? */
866  node_t fake_node;
867  const node_t *node = node_get_by_id(router->cache_info.identity_digest);
868  if (node == NULL) {
869  memset(&fake_node, 0, sizeof(fake_node));
870  fake_node.ri = (routerinfo_t *)router;
871  memcpy(fake_node.identity, router->cache_info.identity_digest, DIGEST_LEN);
872  node = &fake_node;
873  }
875 }
876 
877 /**
878  * Remove every node_t that appears in <b>excluded</b> from <b>sl</b>.
879  *
880  * Behaves like smartlist_subtract, but uses nodelist_idx values to deliver
881  * linear performance when smartlist_subtract would be quadratic.
882  **/
883 static void
885 {
886  const smartlist_t *nodelist = nodelist_get_list();
887  const int nodelist_len = smartlist_len(nodelist);
888  bitarray_t *excluded_idx = bitarray_init_zero(nodelist_len);
889 
890  /* We haven't used nodelist_idx in this way previously, so I'm going to be
891  * paranoid in this code, and check that nodelist_idx is correct for every
892  * node before we use it. If we fail, we fall back to smartlist_subtract().
893  */
894 
895  /* Set the excluded_idx bit corresponding to every excluded node...
896  */
897  SMARTLIST_FOREACH_BEGIN(excluded, const node_t *, node) {
898  const int idx = node->nodelist_idx;
899  if (BUG(idx < 0) || BUG(idx >= nodelist_len) ||
900  BUG(node != smartlist_get(nodelist, idx))) {
901  goto internal_error;
902  }
903  bitarray_set(excluded_idx, idx);
904  } SMARTLIST_FOREACH_END(node);
905 
906  /* Then remove them from sl.
907  */
908  SMARTLIST_FOREACH_BEGIN(sl, const node_t *, node) {
909  const int idx = node->nodelist_idx;
910  if (BUG(idx < 0) || BUG(idx >= nodelist_len) ||
911  BUG(node != smartlist_get(nodelist, idx))) {
912  goto internal_error;
913  }
914  if (bitarray_is_set(excluded_idx, idx)) {
915  SMARTLIST_DEL_CURRENT(sl, node);
916  }
917  } SMARTLIST_FOREACH_END(node);
918 
919  bitarray_free(excluded_idx);
920  return;
921 
922  internal_error:
923  log_warn(LD_BUG, "Internal error prevented us from using the fast method "
924  "for subtracting nodelists. Falling back to the quadratic way.");
925  smartlist_subtract(sl, excluded);
926  bitarray_free(excluded_idx);
927 }
928 
929 /** Return a random running node from the nodelist. Never
930  * pick a node that is in
931  * <b>excludedsmartlist</b>, or which matches <b>excludedset</b>,
932  * even if they are the only nodes available.
933  * If <b>CRN_NEED_UPTIME</b> is set in flags and any router has more than
934  * a minimum uptime, return one of those.
935  * If <b>CRN_NEED_CAPACITY</b> is set in flags, weight your choice by the
936  * advertised capacity of each router.
937  * If <b>CRN_NEED_GUARD</b> is set in flags, consider only Guard routers.
938  * If <b>CRN_WEIGHT_AS_EXIT</b> is set in flags, we weight bandwidths as if
939  * picking an exit node, otherwise we weight bandwidths for picking a relay
940  * node (that is, possibly discounting exit nodes).
941  * If <b>CRN_NEED_DESC</b> is set in flags, we only consider nodes that
942  * have a routerinfo or microdescriptor -- that is, enough info to be
943  * used to build a circuit.
944  * If <b>CRN_PREF_ADDR</b> is set in flags, we only consider nodes that
945  * have an address that is preferred by the ClientPreferIPv6ORPort setting
946  * (regardless of this flag, we exclude nodes that aren't allowed by the
947  * firewall, including ClientUseIPv4 0 and fascist_firewall_use_ipv6() == 0).
948  */
949 const node_t *
951  routerset_t *excludedset,
952  router_crn_flags_t flags)
953 { /* XXXX MOVE */
954  const int need_uptime = (flags & CRN_NEED_UPTIME) != 0;
955  const int need_capacity = (flags & CRN_NEED_CAPACITY) != 0;
956  const int need_guard = (flags & CRN_NEED_GUARD) != 0;
957  const int weight_for_exit = (flags & CRN_WEIGHT_AS_EXIT) != 0;
958  const int need_desc = (flags & CRN_NEED_DESC) != 0;
959  const int pref_addr = (flags & CRN_PREF_ADDR) != 0;
960  const int direct_conn = (flags & CRN_DIRECT_CONN) != 0;
961  const int rendezvous_v3 = (flags & CRN_RENDEZVOUS_V3) != 0;
962 
963  const smartlist_t *node_list = nodelist_get_list();
965  *excludednodes=smartlist_new();
966  const node_t *choice = NULL;
967  const routerinfo_t *r;
969 
970  tor_assert(!(weight_for_exit && need_guard));
971  rule = weight_for_exit ? WEIGHT_FOR_EXIT :
972  (need_guard ? WEIGHT_FOR_GUARD : WEIGHT_FOR_MID);
973 
974  SMARTLIST_FOREACH_BEGIN(node_list, const node_t *, node) {
975  if (node_allows_single_hop_exits(node)) {
976  /* Exclude relays that allow single hop exit circuits. This is an
977  * obsolete option since 0.2.9.2-alpha and done by default in
978  * 0.3.1.0-alpha. */
979  smartlist_add(excludednodes, (node_t*)node);
980  } else if (rendezvous_v3 &&
982  /* Exclude relays that do not support to rendezvous for a hidden service
983  * version 3. */
984  smartlist_add(excludednodes, (node_t*)node);
985  }
986  } SMARTLIST_FOREACH_END(node);
987 
988  /* If the node_t is not found we won't be to exclude ourself but we
989  * won't be able to pick ourself in router_choose_random_node() so
990  * this is fine to at least try with our routerinfo_t object. */
991  if ((r = router_get_my_routerinfo()))
992  routerlist_add_node_and_family(excludednodes, r);
993 
994  router_add_running_nodes_to_smartlist(sl, need_uptime, need_capacity,
995  need_guard, need_desc, pref_addr,
996  direct_conn);
997  log_debug(LD_CIRC,
998  "We found %d running nodes.",
999  smartlist_len(sl));
1000 
1001  if (excludedsmartlist) {
1002  smartlist_add_all(excludednodes, excludedsmartlist);
1003  }
1004  nodelist_subtract(sl, excludednodes);
1005 
1006  if (excludedset) {
1007  routerset_subtract_nodes(sl,excludedset);
1008  log_debug(LD_CIRC,
1009  "We removed excludedset, leaving %d nodes.",
1010  smartlist_len(sl));
1011  }
1012 
1013  // Always weight by bandwidth
1014  choice = node_sl_choose_by_bandwidth(sl, rule);
1015 
1016  smartlist_free(sl);
1017  if (!choice && (need_uptime || need_capacity || need_guard || pref_addr)) {
1018  /* try once more -- recurse but with fewer restrictions. */
1019  log_info(LD_CIRC,
1020  "We couldn't find any live%s%s%s routers; falling back "
1021  "to list of all routers.",
1022  need_capacity?", fast":"",
1023  need_uptime?", stable":"",
1024  need_guard?", guard":"");
1025  flags &= ~ (CRN_NEED_UPTIME|CRN_NEED_CAPACITY|CRN_NEED_GUARD|
1026  CRN_PREF_ADDR);
1027  choice = router_choose_random_node(
1028  excludedsmartlist, excludedset, flags);
1029  }
1030  smartlist_free(excludednodes);
1031  if (!choice) {
1032  log_warn(LD_CIRC,
1033  "No available nodes when trying to choose node. Failing.");
1034  }
1035  return choice;
1036 }
1037 
1038 /** Try to find a running directory authority. Flags are as for
1039  * router_pick_directory_server.
1040  */
1041 const routerstatus_t *
1043 {
1046  type, flags);
1047 }
1048 
1049 /** Try to find a running fallback directory. Flags are as for
1050  * router_pick_directory_server.
1051  */
1052 const routerstatus_t *
1054 {
1056  router_get_fallback_dir_servers_mutable(),
1057  type, flags);
1058 }
1059 
1060 /** Pick a random element from a list of dir_server_t, weighting by their
1061  * <b>weight</b> field. */
1062 static const dir_server_t *
1063 dirserver_choose_by_weight(const smartlist_t *servers, double authority_weight)
1064 {
1065  int n = smartlist_len(servers);
1066  int i;
1067  double *weights_dbl;
1068  uint64_t *weights_u64;
1069  const dir_server_t *ds;
1070 
1071  weights_dbl = tor_calloc(n, sizeof(double));
1072  weights_u64 = tor_calloc(n, sizeof(uint64_t));
1073  for (i = 0; i < n; ++i) {
1074  ds = smartlist_get(servers, i);
1075  weights_dbl[i] = ds->weight;
1076  if (ds->is_authority)
1077  weights_dbl[i] *= authority_weight;
1078  }
1079 
1080  scale_array_elements_to_u64(weights_u64, weights_dbl, n, NULL);
1081  i = choose_array_element_by_weight(weights_u64, n);
1082  tor_free(weights_dbl);
1083  tor_free(weights_u64);
1084  return (i < 0) ? NULL : smartlist_get(servers, i);
1085 }
1086 
1087 /** Choose randomly from among the dir_server_ts in sourcelist that
1088  * are up. Flags are as for router_pick_directory_server_impl().
1089  */
1090 static const routerstatus_t *
1092  dirinfo_type_t type, int flags,
1093  int *n_busy_out)
1094 {
1095  const or_options_t *options = get_options();
1096  smartlist_t *direct, *tunnel;
1097  smartlist_t *overloaded_direct, *overloaded_tunnel;
1098  const routerinfo_t *me = router_get_my_routerinfo();
1099  const routerstatus_t *result = NULL;
1100  time_t now = time(NULL);
1101  const int requireother = ! (flags & PDS_ALLOW_SELF);
1102  const int fascistfirewall = ! (flags & PDS_IGNORE_FASCISTFIREWALL);
1103  const int no_serverdesc_fetching =(flags & PDS_NO_EXISTING_SERVERDESC_FETCH);
1104  const int no_microdesc_fetching =(flags & PDS_NO_EXISTING_MICRODESC_FETCH);
1105  const double auth_weight =
1106  (sourcelist == router_get_fallback_dir_servers()) ?
1107  options->DirAuthorityFallbackRate : 1.0;
1108  smartlist_t *pick_from;
1109  int n_busy = 0;
1110  int try_excluding = 1, n_excluded = 0;
1111  int try_ip_pref = 1;
1112 
1113  if (!sourcelist)
1114  return NULL;
1115 
1116  retry_search:
1117 
1118  direct = smartlist_new();
1119  tunnel = smartlist_new();
1120  overloaded_direct = smartlist_new();
1121  overloaded_tunnel = smartlist_new();
1122 
1123  const int skip_or_fw = router_skip_or_reachability(options, try_ip_pref);
1124  const int skip_dir_fw = router_skip_dir_reachability(options, try_ip_pref);
1125  const int must_have_or = dirclient_must_use_begindir(options);
1126 
1127  SMARTLIST_FOREACH_BEGIN(sourcelist, const dir_server_t *, d)
1128  {
1129  int is_overloaded =
1130  d->fake_status.last_dir_503_at + DIR_503_TIMEOUT > now;
1131  if (!d->is_running) continue;
1132  if ((type & d->type) == 0)
1133  continue;
1134 
1135  SKIP_MISSING_TRUSTED_EXTRAINFO(type, d->digest);
1136 
1137  if (requireother && me && router_digest_is_me(d->digest))
1138  continue;
1139  if (try_excluding &&
1141  &d->fake_status, -1)) {
1142  ++n_excluded;
1143  continue;
1144  }
1145 
1146  if (router_is_already_dir_fetching_(d->addr,
1147  &d->ipv6_addr,
1148  d->dir_port,
1149  no_serverdesc_fetching,
1150  no_microdesc_fetching)) {
1151  ++n_busy;
1152  continue;
1153  }
1154 
1155  /* Clients use IPv6 addresses if the server has one and the client
1156  * prefers IPv6.
1157  * Add the router if its preferred address and port are reachable.
1158  * If we don't get any routers, we'll try again with the non-preferred
1159  * address for each router (if any). (To ensure correct load-balancing
1160  * we try routers that only have one address both times.)
1161  */
1162  if (!fascistfirewall || skip_or_fw ||
1163  fascist_firewall_allows_dir_server(d, FIREWALL_OR_CONNECTION,
1164  try_ip_pref))
1165  smartlist_add(is_overloaded ? overloaded_tunnel : tunnel, (void*)d);
1166  else if (!must_have_or && (skip_dir_fw ||
1167  fascist_firewall_allows_dir_server(d, FIREWALL_DIR_CONNECTION,
1168  try_ip_pref)))
1169  smartlist_add(is_overloaded ? overloaded_direct : direct, (void*)d);
1170  }
1171  SMARTLIST_FOREACH_END(d);
1172 
1173  if (smartlist_len(tunnel)) {
1174  pick_from = tunnel;
1175  } else if (smartlist_len(overloaded_tunnel)) {
1176  pick_from = overloaded_tunnel;
1177  } else if (smartlist_len(direct)) {
1178  pick_from = direct;
1179  } else {
1180  pick_from = overloaded_direct;
1181  }
1182 
1183  {
1184  const dir_server_t *selection =
1185  dirserver_choose_by_weight(pick_from, auth_weight);
1186 
1187  if (selection)
1188  result = &selection->fake_status;
1189  }
1190 
1191  smartlist_free(direct);
1192  smartlist_free(tunnel);
1193  smartlist_free(overloaded_direct);
1194  smartlist_free(overloaded_tunnel);
1195 
1196  RETRY_ALTERNATE_IP_VERSION(retry_search);
1197 
1198  RETRY_WITHOUT_EXCLUDE(retry_search);
1199 
1200  router_picked_poor_directory_log(result);
1201 
1202  if (n_busy_out)
1203  *n_busy_out = n_busy;
1204  return result;
1205 }
Header file for dirclient.c.
int node_allows_single_hop_exits(const node_t *node)
Definition: nodelist.c:1446
Router descriptor structure.
uint16_t ipv6_orport
static void nodelist_subtract(smartlist_t *sl, const smartlist_t *excluded)
Definition: node_select.c:884
static void routerlist_add_node_and_family(smartlist_t *sl, const routerinfo_t *router)
Definition: node_select.c:863
Header file for circuitbuild.c.
Common functions for using (pseudo-)random number generators.
Definition: node_st.h:34
#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:62
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:1042
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)
Node information structure.
char * rate_limit_log(ratelim_t *lim, time_t now)
Definition: ratelim.c:41
Header file for config.c.
char identity_digest[DIGEST_LEN]
const or_options_t * get_options(void)
Definition: config.c:926
#define tor_assert(expr)
Definition: util_bug.h:102
#define BRIDGE_MIN_BELIEVABLE_BANDWIDTH
Definition: node_select.c:525
Header file for microdesc.c.
networkstatus_t * networkstatus_get_latest_consensus_by_flavor(consensus_flavor_t f)
const routerstatus_t * router_pick_directory_server(dirinfo_type_t type, int flags)
Definition: node_select.c:72
#define tor_free(p)
Definition: malloc.h:52
int node_has_preferred_descriptor(const node_t *node, int for_direct_connect)
Definition: nodelist.c:1378
#define SMARTLIST_DEL_CURRENT(sl, var)
uint32_t bandwidthrate
Definition: routerinfo_st.h:56
dirinfo_type_t
Definition: or.h:891
smartlist_t * smartlist_new(void)
double DirAuthorityFallbackRate
struct routerset_t * ExcludeNodes
Definition: or_options_st.h:89
#define STATIC
Definition: testsupport.h:32
STATIC const routerstatus_t * router_pick_directory_server_impl(dirinfo_type_t type, int flags, int *n_busy_out)
Definition: node_select.c:295
static void bitarray_set(bitarray_t *b, int bit)
Definition: bitarray.h:68
int router_have_minimum_dir_info(void)
Definition: nodelist.c:2324
#define DIR_PURPOSE_FETCH_EXTRAINFO
Definition: directory.h:41
Header file for routerset.c.
Routerstatus (consensus entry) structure.
smartlist_t * router_get_trusted_dir_servers_mutable(void)
Definition: dirlist.c:102
#define PDS_IGNORE_FASCISTFIREWALL
Definition: node_select.h:54
Trusted/fallback directory server structure.
networkstatus_t * networkstatus_get_latest_consensus(void)
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:104
void nodelist_add_node_and_family(smartlist_t *sl, const node_t *node)
Definition: nodelist.c:2136
double frac_nodes_with_descriptors(const smartlist_t *sl, bandwidth_weight_rule_t rule, int for_direct_conn)
Definition: node_select.c:815
int node_is_dir(const node_t *node)
Definition: nodelist.c:1342
#define DIR_PURPOSE_FETCH_SERVERDESC
Definition: directory.h:38
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:425
#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)
networkstatus_t * networkstatus_get_reasonably_live_consensus(time_t now, int flavor)
#define tor_addr_from_ipv4h(dest, v4addr)
Definition: address.h:299
Header for fp.c.
#define LD_CIRC
Definition: log.h:82
static const node_t * smartlist_choose_node_by_bandwidth_weights(const smartlist_t *sl, bandwidth_weight_rule_t rule)
Definition: node_select.c:500
Header file for routermode.c.
#define DIGEST_LEN
Definition: digest_sizes.h:20
unsigned int is_possible_guard
int usable_consensus_flavor(void)
Definition: microdesc.c:1085
Master header file for Tor-specific functionality.
int crypto_rand_int(unsigned int max)
const node_t * node_get_by_id(const char *identity_digest)
Definition: nodelist.c:223
char identity[DIGEST_LEN]
Definition: node_st.h:46
tor_addr_t ipv6_addr
uint64_t crypto_rand_uint64(uint64_t max)
const char * fmt_addr32(uint32_t addr)
Definition: address.c:1181
uint32_t bandwidthcapacity
Definition: routerinfo_st.h:60
int tor_addr_is_null(const tor_addr_t *addr)
Definition: address.c:770
unsigned int has_guardfraction
const node_t * router_choose_random_node(smartlist_t *excludedsmartlist, routerset_t *excludedset, router_crn_flags_t flags)
Definition: node_select.c:950
const char * routerstatus_describe(const routerstatus_t *rs)
Definition: describe.c:184
Header for feature/dirclient/dirclient_modes.c.
#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:1063
int smartlist_pos(const smartlist_t *sl, const void *element)
Definition: smartlist.c:119
unsigned int is_authority
Definition: dir_server_st.h:38
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:259
#define LD_DIR
Definition: log.h:88
void smartlist_subtract(smartlist_t *sl1, const smartlist_t *sl2)
Definition: smartlist.c:264
void router_reset_status_download_failures(void)
Definition: dirlist.c:134
const smartlist_t * nodelist_get_list(void)
Definition: nodelist.c:975
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:505
const char * bandwidth_weight_rule_to_string(bandwidth_weight_rule_t rule)
Definition: reasons.c:435
const routerinfo_t * router_get_my_routerinfo(void)
Definition: router.c:1624
int node_supports_v3_rendezvous_point(const node_t *node)
Definition: nodelist.c:1210
bandwidth_weight_rule_t
Definition: node_select.h:35
#define SMARTLIST_FOREACH(sl, type, var, cmd)
uint32_t guardfraction_percentage
static int32_t kb_to_bytes(uint32_t bw)
Definition: node_select.c:480
Header file for router.c.
static uint32_t bridge_get_advertised_bandwidth_bounded(routerinfo_t *router)
Definition: node_select.c:533
void routerset_subtract_nodes(smartlist_t *lst, const routerset_t *routerset)
Definition: routerset.c:398
smartlist_t * routerstatus_list
STATIC int choose_array_element_by_weight(const uint64_t *entries, int n_entries)
Definition: node_select.c:454
#define fmt_addr(a)
Definition: address.h:216
int fascist_firewall_allows_node(const node_t *node, firewall_connection_t fw_connection, int pref_only)
Definition: policies.c:733
static void log_buggy_rs_source(const routerstatus_t *rs)
Definition: node_select.c:550
connection_t * connection_get_by_type_addr_port_purpose(int type, const tor_addr_t *addr, uint16_t port, int purpose)
Definition: connection.c:4559
int router_digest_is_me(const char *digest)
Definition: router.c:1587
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:850
time_t approx_time(void)
Definition: approx_time.c:32
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:598
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:1091
int16_t country_t
Definition: country.h:17
void mark_all_dirservers_up(smartlist_t *server_list)
Definition: dirlist.c:215
#define CONN_TYPE_DIR
Definition: connection.h:53
routerstatus_t fake_status
Definition: dir_server_st.h:51
#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:86
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:1053
Networkstatus consensus/vote structure.