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