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-2013, The Tor Project, Inc. */
5 /* See LICENSE for licensing information */
10 * maintain and access the global list of routerinfos for known
14 #define ROUTERLIST_PRIVATE
16 #include "circuitstats.h"
18 #include "connection.h"
20 #include "directory.h"
23 #include "entrynodes.h"
26 #include "hibernate.h"
28 #include "microdesc.h"
29 #include "networkstatus.h"
33 #include "rendcommon.h"
34 #include "rendservice.h"
37 #include "routerlist.h"
38 #include "routerparse.h"
39 #include "routerset.h"
40 #include "../common/sandbox.h"
41 // #define DEBUG_ROUTERLIST
43 /****************************************************************************/
45 DECLARE_TYPED_DIGESTMAP_FNS(sdmap_
, digest_sd_map_t
, signed_descriptor_t
)
46 DECLARE_TYPED_DIGESTMAP_FNS(rimap_
, digest_ri_map_t
, routerinfo_t
)
47 DECLARE_TYPED_DIGESTMAP_FNS(eimap_
, digest_ei_map_t
, extrainfo_t
)
48 DECLARE_TYPED_DIGESTMAP_FNS(dsmap_
, digest_ds_map_t
, download_status_t
)
49 #define SDMAP_FOREACH(map, keyvar, valvar) \
50 DIGESTMAP_FOREACH(sdmap_to_digestmap(map), keyvar, signed_descriptor_t *, \
52 #define RIMAP_FOREACH(map, keyvar, valvar) \
53 DIGESTMAP_FOREACH(rimap_to_digestmap(map), keyvar, routerinfo_t *, valvar)
54 #define EIMAP_FOREACH(map, keyvar, valvar) \
55 DIGESTMAP_FOREACH(eimap_to_digestmap(map), keyvar, extrainfo_t *, valvar)
56 #define DSMAP_FOREACH(map, keyvar, valvar) \
57 DIGESTMAP_FOREACH(dsmap_to_digestmap(map), keyvar, download_status_t *, \
60 /* Forward declaration for cert_list_t */
61 typedef struct cert_list_t cert_list_t
;
63 /* static function prototypes */
64 static int compute_weighted_bandwidths(const smartlist_t
*sl
,
65 bandwidth_weight_rule_t rule
,
66 u64_dbl_t
**bandwidths_out
);
67 static const routerstatus_t
*router_pick_directory_server_impl(
68 dirinfo_type_t auth
, int flags
);
69 static const routerstatus_t
*router_pick_trusteddirserver_impl(
70 const smartlist_t
*sourcelist
, dirinfo_type_t auth
,
71 int flags
, int *n_busy_out
);
72 static const routerstatus_t
*router_pick_dirserver_generic(
73 smartlist_t
*sourcelist
,
74 dirinfo_type_t type
, int flags
);
75 static void mark_all_dirservers_up(smartlist_t
*server_list
);
76 static void dir_server_free(dir_server_t
*ds
);
77 static int signed_desc_digest_is_recognized(signed_descriptor_t
*desc
);
78 static const char *signed_descriptor_get_body_impl(
79 const signed_descriptor_t
*desc
,
80 int with_annotations
);
81 static void list_pending_downloads(digestmap_t
*result
,
82 int purpose
, const char *prefix
);
83 static void list_pending_fpsk_downloads(fp_pair_map_t
*result
);
84 static void launch_dummy_descriptor_download_as_needed(time_t now
,
85 const or_options_t
*options
);
86 static void download_status_reset_by_sk_in_cl(cert_list_t
*cl
,
88 static int download_status_is_ready_by_sk_in_cl(cert_list_t
*cl
,
90 time_t now
, int max_failures
);
92 /****************************************************************************/
94 /** Global list of a dir_server_t object for each directory
96 static smartlist_t
*trusted_dir_servers
= NULL
;
97 /** Global list of dir_server_t objects for all directory authorities
98 * and all fallback directory servers. */
99 static smartlist_t
*fallback_dir_servers
= NULL
;
101 /** List of certificates for a single authority, and download status for
102 * latest certificate.
106 * The keys of download status map are cert->signing_key_digest for pending
107 * downloads by (identity digest/signing key digest) pair; functions such
108 * as authority_cert_get_by_digest() already assume these are unique.
110 struct digest_ds_map_t
*dl_status_map
;
111 /* There is also a dlstatus for the download by identity key only */
112 download_status_t dl_status_by_id
;
115 /** Map from v3 identity key digest to cert_list_t. */
116 static digestmap_t
*trusted_dir_certs
= NULL
;
117 /** True iff any key certificate in at least one member of
118 * <b>trusted_dir_certs</b> has changed since we last flushed the
119 * certificates to disk. */
120 static int trusted_dir_servers_certs_changed
= 0;
122 /** Global list of all of the routers that we know about. */
123 static routerlist_t
*routerlist
= NULL
;
125 /** List of strings for nicknames we've already warned about and that are
126 * still unknown / unavailable. */
127 static smartlist_t
*warned_nicknames
= NULL
;
129 /** The last time we tried to download any routerdesc, or 0 for "never". We
130 * use this to rate-limit download attempts when the number of routerdescs to
131 * download is low. */
132 static time_t last_descriptor_download_attempted
= 0;
134 /** Return the number of directory authorities whose type matches some bit set
137 get_n_authorities(dirinfo_type_t type
)
140 if (!trusted_dir_servers
)
142 SMARTLIST_FOREACH(trusted_dir_servers
, dir_server_t
*, ds
,
148 /** Reset the download status of a specified element in a dsmap */
150 download_status_reset_by_sk_in_cl(cert_list_t
*cl
, const char *digest
)
152 download_status_t
*dlstatus
= NULL
;
157 /* Make sure we have a dsmap */
158 if (!(cl
->dl_status_map
)) {
159 cl
->dl_status_map
= dsmap_new();
161 /* Look for a download_status_t in the map with this digest */
162 dlstatus
= dsmap_get(cl
->dl_status_map
, digest
);
165 /* Insert before we reset */
166 dlstatus
= tor_malloc_zero(sizeof(*dlstatus
));
167 dsmap_set(cl
->dl_status_map
, digest
, dlstatus
);
169 tor_assert(dlstatus
);
170 /* Go ahead and reset it */
171 download_status_reset(dlstatus
);
175 * Return true if the download for this signing key digest in cl is ready
176 * to be re-attempted.
179 download_status_is_ready_by_sk_in_cl(cert_list_t
*cl
,
181 time_t now
, int max_failures
)
184 download_status_t
*dlstatus
= NULL
;
189 /* Make sure we have a dsmap */
190 if (!(cl
->dl_status_map
)) {
191 cl
->dl_status_map
= dsmap_new();
193 /* Look for a download_status_t in the map with this digest */
194 dlstatus
= dsmap_get(cl
->dl_status_map
, digest
);
197 /* Use download_status_is_ready() */
198 rv
= download_status_is_ready(dlstatus
, now
, max_failures
);
201 * If we don't know anything about it, return 1, since we haven't
202 * tried this one before. We need to create a new entry here,
205 dlstatus
= tor_malloc_zero(sizeof(*dlstatus
));
206 download_status_reset(dlstatus
);
207 dsmap_set(cl
->dl_status_map
, digest
, dlstatus
);
214 /** Helper: Return the cert_list_t for an authority whose authority ID is
215 * <b>id_digest</b>, allocating a new list if necessary. */
217 get_cert_list(const char *id_digest
)
220 if (!trusted_dir_certs
)
221 trusted_dir_certs
= digestmap_new();
222 cl
= digestmap_get(trusted_dir_certs
, id_digest
);
224 cl
= tor_malloc_zero(sizeof(cert_list_t
));
225 cl
->dl_status_by_id
.schedule
= DL_SCHED_CONSENSUS
;
226 cl
->certs
= smartlist_new();
227 cl
->dl_status_map
= dsmap_new();
228 digestmap_set(trusted_dir_certs
, id_digest
, cl
);
233 /** Release all space held by a cert_list_t */
235 cert_list_free(cert_list_t
*cl
)
240 SMARTLIST_FOREACH(cl
->certs
, authority_cert_t
*, cert
,
241 authority_cert_free(cert
));
242 smartlist_free(cl
->certs
);
243 dsmap_free(cl
->dl_status_map
, tor_free_
);
247 /** Wrapper for cert_list_free so we can pass it to digestmap_free */
249 cert_list_free_(void *cl
)
254 /** Reload the cached v3 key certificates from the cached-certs file in
255 * the data directory. Return 0 on success, -1 on failure. */
257 trusted_dirs_reload_certs(void)
263 filename
= get_datadir_fname("cached-certs");
264 contents
= read_file_to_str(filename
, RFTS_IGNORE_MISSING
, NULL
);
268 r
= trusted_dirs_load_certs_from_string(
270 TRUSTED_DIRS_CERTS_SRC_FROM_STORE
, 1);
275 /** Helper: return true iff we already have loaded the exact cert
278 already_have_cert(authority_cert_t
*cert
)
280 cert_list_t
*cl
= get_cert_list(cert
->cache_info
.identity_digest
);
282 SMARTLIST_FOREACH(cl
->certs
, authority_cert_t
*, c
,
284 if (tor_memeq(c
->cache_info
.signed_descriptor_digest
,
285 cert
->cache_info
.signed_descriptor_digest
,
292 /** Load a bunch of new key certificates from the string <b>contents</b>. If
293 * <b>source</b> is TRUSTED_DIRS_CERTS_SRC_FROM_STORE, the certificates are
294 * from the cache, and we don't need to flush them to disk. If we are a
295 * dirauth loading our own cert, source is TRUSTED_DIRS_CERTS_SRC_SELF.
296 * Otherwise, source is download type: TRUSTED_DIRS_CERTS_SRC_DL_BY_ID_DIGEST
297 * or TRUSTED_DIRS_CERTS_SRC_DL_BY_ID_SK_DIGEST. If <b>flush</b> is true, we
298 * need to flush any changed certificates to disk now. Return 0 on success,
299 * -1 if any certs fail to parse.
303 trusted_dirs_load_certs_from_string(const char *contents
, int source
,
308 int failure_code
= 0;
309 int from_store
= (source
== TRUSTED_DIRS_CERTS_SRC_FROM_STORE
);
311 for (s
= contents
; *s
; s
= eos
) {
312 authority_cert_t
*cert
= authority_cert_parse_from_string(s
, &eos
);
318 ds
= trusteddirserver_get_by_v3_auth_digest(
319 cert
->cache_info
.identity_digest
);
320 log_debug(LD_DIR
, "Parsed certificate for %s",
321 ds
? ds
->nickname
: "unknown authority");
323 if (already_have_cert(cert
)) {
324 /* we already have this one. continue. */
325 log_info(LD_DIR
, "Skipping %s certificate for %s that we "
327 from_store
? "cached" : "downloaded",
328 ds
? ds
->nickname
: "an old or new authority");
331 * A duplicate on download should be treated as a failure, so we call
332 * authority_cert_dl_failed() to reset the download status to make sure
333 * we can't try again. Since we've implemented the fp-sk mechanism
334 * to download certs by signing key, this should be much rarer than it
335 * was and is perhaps cause for concern.
338 if (authdir_mode(get_options())) {
340 "Got a certificate for %s, but we already have it. "
341 "Maybe they haven't updated it. Waiting for a while.",
342 ds
? ds
->nickname
: "an old or new authority");
345 "Got a certificate for %s, but we already have it. "
346 "Maybe they haven't updated it. Waiting for a while.",
347 ds
? ds
->nickname
: "an old or new authority");
351 * This is where we care about the source; authority_cert_dl_failed()
352 * needs to know whether the download was by fp or (fp,sk) pair to
353 * twiddle the right bit in the download map.
355 if (source
== TRUSTED_DIRS_CERTS_SRC_DL_BY_ID_DIGEST
) {
356 authority_cert_dl_failed(cert
->cache_info
.identity_digest
,
358 } else if (source
== TRUSTED_DIRS_CERTS_SRC_DL_BY_ID_SK_DIGEST
) {
359 authority_cert_dl_failed(cert
->cache_info
.identity_digest
,
360 cert
->signing_key_digest
, 404);
364 authority_cert_free(cert
);
369 log_info(LD_DIR
, "Adding %s certificate for directory authority %s with "
370 "signing key %s", from_store
? "cached" : "downloaded",
371 ds
->nickname
, hex_str(cert
->signing_key_digest
,DIGEST_LEN
));
373 int adding
= directory_caches_unknown_auth_certs(get_options());
374 log_info(LD_DIR
, "%s %s certificate for unrecognized directory "
375 "authority with signing key %s",
376 adding
? "Adding" : "Not adding",
377 from_store
? "cached" : "downloaded",
378 hex_str(cert
->signing_key_digest
,DIGEST_LEN
));
380 authority_cert_free(cert
);
385 cl
= get_cert_list(cert
->cache_info
.identity_digest
);
386 smartlist_add(cl
->certs
, cert
);
387 if (ds
&& cert
->cache_info
.published_on
> ds
->addr_current_at
) {
388 /* Check to see whether we should update our view of the authority's
390 if (cert
->addr
&& cert
->dir_port
&&
391 (ds
->addr
!= cert
->addr
||
392 ds
->dir_port
!= cert
->dir_port
)) {
393 char *a
= tor_dup_ip(cert
->addr
);
394 log_notice(LD_DIR
, "Updating address for directory authority %s "
395 "from %s:%d to %s:%d based on certificate.",
396 ds
->nickname
, ds
->address
, (int)ds
->dir_port
,
399 ds
->addr
= cert
->addr
;
400 ds
->dir_port
= cert
->dir_port
;
402 ds
->addr_current_at
= cert
->cache_info
.published_on
;
406 trusted_dir_servers_certs_changed
= 1;
410 trusted_dirs_flush_certs_to_disk();
412 /* call this even if failure_code is <0, since some certs might have
414 networkstatus_note_certs_arrived();
419 /** Save all v3 key certificates to the cached-certs file. */
421 trusted_dirs_flush_certs_to_disk(void)
426 if (!trusted_dir_servers_certs_changed
|| !trusted_dir_certs
)
429 chunks
= smartlist_new();
430 DIGESTMAP_FOREACH(trusted_dir_certs
, key
, cert_list_t
*, cl
) {
431 SMARTLIST_FOREACH(cl
->certs
, authority_cert_t
*, cert
,
433 sized_chunk_t
*c
= tor_malloc(sizeof(sized_chunk_t
));
434 c
->bytes
= cert
->cache_info
.signed_descriptor_body
;
435 c
->len
= cert
->cache_info
.signed_descriptor_len
;
436 smartlist_add(chunks
, c
);
438 } DIGESTMAP_FOREACH_END
;
440 filename
= get_datadir_fname("cached-certs");
441 if (write_chunks_to_file(filename
, chunks
, 0, 0)) {
442 log_warn(LD_FS
, "Error writing certificates to disk.");
445 SMARTLIST_FOREACH(chunks
, sized_chunk_t
*, c
, tor_free(c
));
446 smartlist_free(chunks
);
448 trusted_dir_servers_certs_changed
= 0;
451 /** Remove all v3 authority certificates that have been superseded for more
452 * than 48 hours. (If the most recent cert was published more than 48 hours
453 * ago, then we aren't going to get any consensuses signed with older
456 trusted_dirs_remove_old_certs(void)
458 time_t now
= time(NULL
);
459 #define DEAD_CERT_LIFETIME (2*24*60*60)
460 #define OLD_CERT_LIFETIME (7*24*60*60)
461 if (!trusted_dir_certs
)
464 DIGESTMAP_FOREACH(trusted_dir_certs
, key
, cert_list_t
*, cl
) {
465 authority_cert_t
*newest
= NULL
;
466 SMARTLIST_FOREACH(cl
->certs
, authority_cert_t
*, cert
,
467 if (!newest
|| (cert
->cache_info
.published_on
>
468 newest
->cache_info
.published_on
))
471 const time_t newest_published
= newest
->cache_info
.published_on
;
472 SMARTLIST_FOREACH_BEGIN(cl
->certs
, authority_cert_t
*, cert
) {
474 time_t cert_published
;
477 expired
= now
> cert
->expires
;
478 cert_published
= cert
->cache_info
.published_on
;
479 /* Store expired certs for 48 hours after a newer arrives;
482 (newest_published
+ DEAD_CERT_LIFETIME
< now
) :
483 (cert_published
+ OLD_CERT_LIFETIME
< newest_published
)) {
484 SMARTLIST_DEL_CURRENT(cl
->certs
, cert
);
485 authority_cert_free(cert
);
486 trusted_dir_servers_certs_changed
= 1;
488 } SMARTLIST_FOREACH_END(cert
);
490 } DIGESTMAP_FOREACH_END
;
491 #undef OLD_CERT_LIFETIME
493 trusted_dirs_flush_certs_to_disk();
496 /** Return the newest v3 authority certificate whose v3 authority identity key
497 * has digest <b>id_digest</b>. Return NULL if no such authority is known,
498 * or it has no certificate. */
500 authority_cert_get_newest_by_id(const char *id_digest
)
503 authority_cert_t
*best
= NULL
;
504 if (!trusted_dir_certs
||
505 !(cl
= digestmap_get(trusted_dir_certs
, id_digest
)))
508 SMARTLIST_FOREACH(cl
->certs
, authority_cert_t
*, cert
,
510 if (!best
|| cert
->cache_info
.published_on
> best
->cache_info
.published_on
)
516 /** Return the newest v3 authority certificate whose directory signing key has
517 * digest <b>sk_digest</b>. Return NULL if no such certificate is known.
520 authority_cert_get_by_sk_digest(const char *sk_digest
)
523 if (!trusted_dir_certs
)
526 if ((c
= get_my_v3_authority_cert()) &&
527 tor_memeq(c
->signing_key_digest
, sk_digest
, DIGEST_LEN
))
529 if ((c
= get_my_v3_legacy_cert()) &&
530 tor_memeq(c
->signing_key_digest
, sk_digest
, DIGEST_LEN
))
533 DIGESTMAP_FOREACH(trusted_dir_certs
, key
, cert_list_t
*, cl
) {
534 SMARTLIST_FOREACH(cl
->certs
, authority_cert_t
*, cert
,
536 if (tor_memeq(cert
->signing_key_digest
, sk_digest
, DIGEST_LEN
))
539 } DIGESTMAP_FOREACH_END
;
543 /** Return the v3 authority certificate with signing key matching
544 * <b>sk_digest</b>, for the authority with identity digest <b>id_digest</b>.
545 * Return NULL if no such authority is known. */
547 authority_cert_get_by_digests(const char *id_digest
,
548 const char *sk_digest
)
551 if (!trusted_dir_certs
||
552 !(cl
= digestmap_get(trusted_dir_certs
, id_digest
)))
554 SMARTLIST_FOREACH(cl
->certs
, authority_cert_t
*, cert
,
555 if (tor_memeq(cert
->signing_key_digest
, sk_digest
, DIGEST_LEN
))
561 /** Add every known authority_cert_t to <b>certs_out</b>. */
563 authority_cert_get_all(smartlist_t
*certs_out
)
565 tor_assert(certs_out
);
566 if (!trusted_dir_certs
)
569 DIGESTMAP_FOREACH(trusted_dir_certs
, key
, cert_list_t
*, cl
) {
570 SMARTLIST_FOREACH(cl
->certs
, authority_cert_t
*, c
,
571 smartlist_add(certs_out
, c
));
572 } DIGESTMAP_FOREACH_END
;
575 /** Called when an attempt to download a certificate with the authority with
576 * ID <b>id_digest</b> and, if not NULL, signed with key signing_key_digest
577 * fails with HTTP response code <b>status</b>: remember the failure, so we
578 * don't try again immediately. */
580 authority_cert_dl_failed(const char *id_digest
,
581 const char *signing_key_digest
, int status
)
584 download_status_t
*dlstatus
= NULL
;
585 char id_digest_str
[2*DIGEST_LEN
+1];
586 char sk_digest_str
[2*DIGEST_LEN
+1];
588 if (!trusted_dir_certs
||
589 !(cl
= digestmap_get(trusted_dir_certs
, id_digest
)))
593 * Are we noting a failed download of the latest cert for the id digest,
594 * or of a download by (id, signing key) digest pair?
596 if (!signing_key_digest
) {
597 /* Just by id digest */
598 download_status_failed(&cl
->dl_status_by_id
, status
);
600 /* Reset by (id, signing key) digest pair
602 * Look for a download_status_t in the map with this digest
604 dlstatus
= dsmap_get(cl
->dl_status_map
, signing_key_digest
);
607 download_status_failed(dlstatus
, status
);
610 * Do this rather than hex_str(), since hex_str clobbers
611 * old results and we call twice in the param list.
613 base16_encode(id_digest_str
, sizeof(id_digest_str
),
614 id_digest
, DIGEST_LEN
);
615 base16_encode(sk_digest_str
, sizeof(sk_digest_str
),
616 signing_key_digest
, DIGEST_LEN
);
618 "Got failure for cert fetch with (fp,sk) = (%s,%s), with "
619 "status %d, but knew nothing about the download.",
620 id_digest_str
, sk_digest_str
, status
);
625 static const char *BAD_SIGNING_KEYS
[] = {
626 "09CD84F751FD6E955E0F8ADB497D5401470D697E", // Expires 2015-01-11 16:26:31
627 "0E7E9C07F0969D0468AD741E172A6109DC289F3C", // Expires 2014-08-12 10:18:26
628 "57B85409891D3FB32137F642FDEDF8B7F8CDFDCD", // Expires 2015-02-11 17:19:09
629 "87326329007AF781F587AF5B594E540B2B6C7630", // Expires 2014-07-17 11:10:09
630 "98CC82342DE8D298CF99D3F1A396475901E0D38E", // Expires 2014-11-10 13:18:56
631 "9904B52336713A5ADCB13E4FB14DC919E0D45571", // Expires 2014-04-20 20:01:01
632 "9DCD8E3F1DD1597E2AD476BBA28A1A89F3095227", // Expires 2015-01-16 03:52:30
633 "A61682F34B9BB9694AC98491FE1ABBFE61923941", // Expires 2014-06-11 09:25:09
634 "B59F6E99C575113650C99F1C425BA7B20A8C071D", // Expires 2014-07-31 13:22:10
635 "D27178388FA75B96D37FA36E0B015227DDDBDA51", // Expires 2014-08-04 04:01:57
641 authority_cert_is_blacklisted(const authority_cert_t
*cert
)
643 char hex_digest
[HEX_DIGEST_LEN
+1];
645 base16_encode(hex_digest
, sizeof(hex_digest
),
646 cert
->signing_key_digest
, sizeof(cert
->signing_key_digest
));
648 for (i
= 0; BAD_SIGNING_KEYS
[i
]; ++i
) {
649 if (!strcasecmp(hex_digest
, BAD_SIGNING_KEYS
[i
])) {
656 /** Return true iff when we've been getting enough failures when trying to
657 * download the certificate with ID digest <b>id_digest</b> that we're willing
658 * to start bugging the user about it. */
660 authority_cert_dl_looks_uncertain(const char *id_digest
)
662 #define N_AUTH_CERT_DL_FAILURES_TO_BUG_USER 2
665 if (!trusted_dir_certs
||
666 !(cl
= digestmap_get(trusted_dir_certs
, id_digest
)))
669 n_failures
= download_status_get_n_failures(&cl
->dl_status_by_id
);
670 return n_failures
>= N_AUTH_CERT_DL_FAILURES_TO_BUG_USER
;
673 /** Try to download any v3 authority certificates that we may be missing. If
674 * <b>status</b> is provided, try to get all the ones that were used to sign
675 * <b>status</b>. Additionally, try to have a non-expired certificate for
676 * every V3 authority in trusted_dir_servers. Don't fetch certificates we
680 authority_certs_fetch_missing(networkstatus_t
*status
, time_t now
)
683 * The pending_id digestmap tracks pending certificate downloads by
684 * identity digest; the pending_cert digestmap tracks pending downloads
685 * by (identity digest, signing key digest) pairs.
687 digestmap_t
*pending_id
;
688 fp_pair_map_t
*pending_cert
;
689 authority_cert_t
*cert
;
691 * The missing_id_digests smartlist will hold a list of id digests
692 * we want to fetch the newest cert for; the missing_cert_digests
693 * smartlist will hold a list of fp_pair_t with an identity and
694 * signing key digest.
696 smartlist_t
*missing_cert_digests
, *missing_id_digests
;
697 char *resource
= NULL
;
699 const int cache
= directory_caches_unknown_auth_certs(get_options());
700 fp_pair_t
*fp_tmp
= NULL
;
701 char id_digest_str
[2*DIGEST_LEN
+1];
702 char sk_digest_str
[2*DIGEST_LEN
+1];
704 if (should_delay_dir_fetches(get_options(), NULL
))
707 pending_cert
= fp_pair_map_new();
708 pending_id
= digestmap_new();
709 missing_cert_digests
= smartlist_new();
710 missing_id_digests
= smartlist_new();
713 * First, we get the lists of already pending downloads so we don't
716 list_pending_downloads(pending_id
, DIR_PURPOSE_FETCH_CERTIFICATE
, "fp/");
717 list_pending_fpsk_downloads(pending_cert
);
720 * Now, we download any trusted authority certs we don't have by
721 * identity digest only. This gets the latest cert for that authority.
723 SMARTLIST_FOREACH_BEGIN(trusted_dir_servers
, dir_server_t
*, ds
) {
725 if (!(ds
->type
& V3_DIRINFO
))
727 if (smartlist_contains_digest(missing_id_digests
,
728 ds
->v3_identity_digest
))
730 cl
= get_cert_list(ds
->v3_identity_digest
);
731 SMARTLIST_FOREACH_BEGIN(cl
->certs
, authority_cert_t
*, cert
) {
732 if (now
< cert
->expires
) {
733 /* It's not expired, and we weren't looking for something to
734 * verify a consensus with. Call it done. */
735 download_status_reset(&(cl
->dl_status_by_id
));
736 /* No sense trying to download it specifically by signing key hash */
737 download_status_reset_by_sk_in_cl(cl
, cert
->signing_key_digest
);
741 } SMARTLIST_FOREACH_END(cert
);
743 download_status_is_ready(&(cl
->dl_status_by_id
), now
,
744 get_options()->TestingCertMaxDownloadTries
) &&
745 !digestmap_get(pending_id
, ds
->v3_identity_digest
)) {
747 "No current certificate known for authority %s "
748 "(ID digest %s); launching request.",
749 ds
->nickname
, hex_str(ds
->v3_identity_digest
, DIGEST_LEN
));
750 smartlist_add(missing_id_digests
, ds
->v3_identity_digest
);
752 } SMARTLIST_FOREACH_END(ds
);
755 * Next, if we have a consensus, scan through it and look for anything
756 * signed with a key from a cert we don't have. Those get downloaded
757 * by (fp,sk) pair, but if we don't know any certs at all for the fp
758 * (identity digest), and it's one of the trusted dir server certs
759 * we started off above or a pending download in pending_id, don't
760 * try to get it yet. Most likely, the one we'll get for that will
761 * have the right signing key too, and we'd just be downloading
765 SMARTLIST_FOREACH_BEGIN(status
->voters
, networkstatus_voter_info_t
*,
767 if (!smartlist_len(voter
->sigs
))
768 continue; /* This authority never signed this consensus, so don't
769 * go looking for a cert with key digest 0000000000. */
771 !trusteddirserver_get_by_v3_auth_digest(voter
->identity_digest
))
772 continue; /* We are not a cache, and we don't know this authority.*/
775 * If we don't know *any* cert for this authority, and a download by ID
776 * is pending or we added it to missing_id_digests above, skip this
777 * one for now to avoid duplicate downloads.
779 cl
= get_cert_list(voter
->identity_digest
);
780 if (smartlist_len(cl
->certs
) == 0) {
781 /* We have no certs at all for this one */
783 /* Do we have a download of one pending? */
784 if (digestmap_get(pending_id
, voter
->identity_digest
))
788 * Are we about to launch a download of one due to the trusted
789 * dir server check above?
791 if (smartlist_contains_digest(missing_id_digests
,
792 voter
->identity_digest
))
796 SMARTLIST_FOREACH_BEGIN(voter
->sigs
, document_signature_t
*, sig
) {
797 cert
= authority_cert_get_by_digests(voter
->identity_digest
,
798 sig
->signing_key_digest
);
800 if (now
< cert
->expires
)
801 download_status_reset_by_sk_in_cl(cl
, sig
->signing_key_digest
);
804 if (download_status_is_ready_by_sk_in_cl(
805 cl
, sig
->signing_key_digest
,
806 now
, get_options()->TestingCertMaxDownloadTries
) &&
807 !fp_pair_map_get_by_digests(pending_cert
,
808 voter
->identity_digest
,
809 sig
->signing_key_digest
)) {
811 * Do this rather than hex_str(), since hex_str clobbers
812 * old results and we call twice in the param list.
814 base16_encode(id_digest_str
, sizeof(id_digest_str
),
815 voter
->identity_digest
, DIGEST_LEN
);
816 base16_encode(sk_digest_str
, sizeof(sk_digest_str
),
817 sig
->signing_key_digest
, DIGEST_LEN
);
819 if (voter
->nickname
) {
821 "We're missing a certificate from authority %s "
822 "(ID digest %s) with signing key %s: "
823 "launching request.",
824 voter
->nickname
, id_digest_str
, sk_digest_str
);
827 "We're missing a certificate from authority ID digest "
828 "%s with signing key %s: launching request.",
829 id_digest_str
, sk_digest_str
);
832 /* Allocate a new fp_pair_t to append */
833 fp_tmp
= tor_malloc(sizeof(*fp_tmp
));
834 memcpy(fp_tmp
->first
, voter
->identity_digest
, sizeof(fp_tmp
->first
));
835 memcpy(fp_tmp
->second
, sig
->signing_key_digest
,
836 sizeof(fp_tmp
->second
));
837 smartlist_add(missing_cert_digests
, fp_tmp
);
839 } SMARTLIST_FOREACH_END(sig
);
840 } SMARTLIST_FOREACH_END(voter
);
843 /* Do downloads by identity digest */
844 if (smartlist_len(missing_id_digests
) > 0) {
846 smartlist_t
*fps
= smartlist_new();
848 smartlist_add(fps
, tor_strdup("fp/"));
850 SMARTLIST_FOREACH_BEGIN(missing_id_digests
, const char *, d
) {
853 if (digestmap_get(pending_id
, d
))
856 base16_encode(id_digest_str
, sizeof(id_digest_str
),
860 tor_asprintf(&fp
, "+%s", id_digest_str
);
862 /* No need for tor_asprintf() in this case; first one gets no '+' */
863 fp
= tor_strdup(id_digest_str
);
867 smartlist_add(fps
, fp
);
868 } SMARTLIST_FOREACH_END(d
);
870 if (smartlist_len(fps
) > 1) {
871 resource
= smartlist_join_strings(fps
, "", 0, NULL
);
872 directory_get_from_dirserver(DIR_PURPOSE_FETCH_CERTIFICATE
, 0,
873 resource
, PDS_RETRY_IF_NO_SERVERS
);
876 /* else we didn't add any: they were all pending */
878 SMARTLIST_FOREACH(fps
, char *, cp
, tor_free(cp
));
882 /* Do downloads by identity digest/signing key pair */
883 if (smartlist_len(missing_cert_digests
) > 0) {
885 smartlist_t
*fp_pairs
= smartlist_new();
887 smartlist_add(fp_pairs
, tor_strdup("fp-sk/"));
889 SMARTLIST_FOREACH_BEGIN(missing_cert_digests
, const fp_pair_t
*, d
) {
890 char *fp_pair
= NULL
;
892 if (fp_pair_map_get(pending_cert
, d
))
895 /* Construct string encodings of the digests */
896 base16_encode(id_digest_str
, sizeof(id_digest_str
),
897 d
->first
, DIGEST_LEN
);
898 base16_encode(sk_digest_str
, sizeof(sk_digest_str
),
899 d
->second
, DIGEST_LEN
);
901 /* Now tor_asprintf() */
903 tor_asprintf(&fp_pair
, "+%s-%s", id_digest_str
, sk_digest_str
);
905 /* First one in the list doesn't get a '+' */
906 tor_asprintf(&fp_pair
, "%s-%s", id_digest_str
, sk_digest_str
);
910 /* Add it to the list of pairs to request */
911 smartlist_add(fp_pairs
, fp_pair
);
912 } SMARTLIST_FOREACH_END(d
);
914 if (smartlist_len(fp_pairs
) > 1) {
915 resource
= smartlist_join_strings(fp_pairs
, "", 0, NULL
);
916 directory_get_from_dirserver(DIR_PURPOSE_FETCH_CERTIFICATE
, 0,
917 resource
, PDS_RETRY_IF_NO_SERVERS
);
920 /* else they were all pending */
922 SMARTLIST_FOREACH(fp_pairs
, char *, p
, tor_free(p
));
923 smartlist_free(fp_pairs
);
926 smartlist_free(missing_id_digests
);
927 SMARTLIST_FOREACH(missing_cert_digests
, fp_pair_t
*, p
, tor_free(p
));
928 smartlist_free(missing_cert_digests
);
929 digestmap_free(pending_id
, NULL
);
930 fp_pair_map_free(pending_cert
, NULL
);
933 /* Router descriptor storage.
935 * Routerdescs are stored in a big file, named "cached-descriptors". As new
936 * routerdescs arrive, we append them to a journal file named
937 * "cached-descriptors.new".
939 * From time to time, we replace "cached-descriptors" with a new file
940 * containing only the live, non-superseded descriptors, and clear
941 * cached-routers.new.
943 * On startup, we read both files.
946 /** Helper: return 1 iff the router log is so big we want to rebuild the
949 router_should_rebuild_store(desc_store_t
*store
)
951 if (store
->store_len
> (1<<16))
952 return (store
->journal_len
> store
->store_len
/ 2 ||
953 store
->bytes_dropped
> store
->store_len
/ 2);
955 return store
->journal_len
> (1<<15);
958 /** Return the desc_store_t in <b>rl</b> that should be used to store
960 static INLINE desc_store_t
*
961 desc_get_store(routerlist_t
*rl
, const signed_descriptor_t
*sd
)
963 if (sd
->is_extrainfo
)
964 return &rl
->extrainfo_store
;
966 return &rl
->desc_store
;
969 /** Add the signed_descriptor_t in <b>desc</b> to the router
970 * journal; change its saved_location to SAVED_IN_JOURNAL and set its
971 * offset appropriately. */
973 signed_desc_append_to_journal(signed_descriptor_t
*desc
,
976 char *fname
= get_datadir_fname_suffix(store
->fname_base
, ".new");
977 const char *body
= signed_descriptor_get_body_impl(desc
,1);
978 size_t len
= desc
->signed_descriptor_len
+ desc
->annotations_len
;
980 if (append_bytes_to_file(fname
, body
, len
, 1)) {
981 log_warn(LD_FS
, "Unable to store router descriptor");
985 desc
->saved_location
= SAVED_IN_JOURNAL
;
988 desc
->saved_offset
= store
->journal_len
;
989 store
->journal_len
+= len
;
994 /** Sorting helper: return <0, 0, or >0 depending on whether the
995 * signed_descriptor_t* in *<b>a</b> is older, the same age as, or newer than
996 * the signed_descriptor_t* in *<b>b</b>. */
998 compare_signed_descriptors_by_age_(const void **_a
, const void **_b
)
1000 const signed_descriptor_t
*r1
= *_a
, *r2
= *_b
;
1001 return (int)(r1
->published_on
- r2
->published_on
);
1005 #define RRS_DONT_REMOVE_OLD 2
1007 /** If the journal of <b>store</b> is too long, or if RRS_FORCE is set in
1008 * <b>flags</b>, then atomically replace the saved router store with the
1009 * routers currently in our routerlist, and clear the journal. Unless
1010 * RRS_DONT_REMOVE_OLD is set in <b>flags</b>, delete expired routers before
1011 * rebuilding the store. Return 0 on success, -1 on failure.
1014 router_rebuild_store(int flags
, desc_store_t
*store
)
1016 smartlist_t
*chunk_list
= NULL
;
1017 char *fname
= NULL
, *fname_tmp
= NULL
;
1020 smartlist_t
*signed_descriptors
= NULL
;
1022 size_t total_expected_len
= 0;
1024 int force
= flags
& RRS_FORCE
;
1026 if (!force
&& !router_should_rebuild_store(store
)) {
1035 if (store
->type
== EXTRAINFO_STORE
)
1036 had_any
= !eimap_isempty(routerlist
->extra_info_map
);
1038 had_any
= (smartlist_len(routerlist
->routers
)+
1039 smartlist_len(routerlist
->old_routers
))>0;
1041 /* Don't save deadweight. */
1042 if (!(flags
& RRS_DONT_REMOVE_OLD
))
1043 routerlist_remove_old_routers();
1045 log_info(LD_DIR
, "Rebuilding %s cache", store
->description
);
1047 fname
= get_datadir_fname(store
->fname_base
);
1048 fname_tmp
= get_datadir_fname_suffix(store
->fname_base
, ".tmp");
1050 chunk_list
= smartlist_new();
1052 /* We sort the routers by age to enhance locality on disk. */
1053 signed_descriptors
= smartlist_new();
1054 if (store
->type
== EXTRAINFO_STORE
) {
1056 for (iter
= eimap_iter_init(routerlist
->extra_info_map
);
1057 !eimap_iter_done(iter
);
1058 iter
= eimap_iter_next(routerlist
->extra_info_map
, iter
)) {
1061 eimap_iter_get(iter
, &key
, &ei
);
1062 smartlist_add(signed_descriptors
, &ei
->cache_info
);
1065 SMARTLIST_FOREACH(routerlist
->old_routers
, signed_descriptor_t
*, sd
,
1066 smartlist_add(signed_descriptors
, sd
));
1067 SMARTLIST_FOREACH(routerlist
->routers
, routerinfo_t
*, ri
,
1068 smartlist_add(signed_descriptors
, &ri
->cache_info
));
1071 smartlist_sort(signed_descriptors
, compare_signed_descriptors_by_age_
);
1073 /* Now, add the appropriate members to chunk_list */
1074 SMARTLIST_FOREACH_BEGIN(signed_descriptors
, signed_descriptor_t
*, sd
) {
1076 const char *body
= signed_descriptor_get_body_impl(sd
, 1);
1078 log_warn(LD_BUG
, "No descriptor available for router.");
1081 if (sd
->do_not_cache
) {
1085 c
= tor_malloc(sizeof(sized_chunk_t
));
1087 c
->len
= sd
->signed_descriptor_len
+ sd
->annotations_len
;
1088 total_expected_len
+= c
->len
;
1089 smartlist_add(chunk_list
, c
);
1090 } SMARTLIST_FOREACH_END(sd
);
1092 if (write_chunks_to_file(fname_tmp
, chunk_list
, 1, 1)<0) {
1093 log_warn(LD_FS
, "Error writing router store to disk.");
1097 /* Our mmap is now invalid. */
1099 int res
= tor_munmap_file(store
->mmap
);
1102 log_warn(LD_FS
, "Unable to munmap route store in %s", fname
);
1106 if (replace_file(fname_tmp
, fname
)<0) {
1107 log_warn(LD_FS
, "Error replacing old router store: %s", strerror(errno
));
1112 store
->mmap
= tor_mmap_file(fname
);
1113 if (! store
->mmap
) {
1114 if (errno
== ERANGE
) {
1116 if (total_expected_len
) {
1117 log_warn(LD_FS
, "We wrote some bytes to a new descriptor file at '%s',"
1118 " but when we went to mmap it, it was empty!", fname
);
1119 } else if (had_any
) {
1120 log_info(LD_FS
, "We just removed every descriptor in '%s'. This is "
1121 "okay if we're just starting up after a long time. "
1122 "Otherwise, it's a bug.", fname
);
1125 log_warn(LD_FS
, "Unable to mmap new descriptor file at '%s'.",fname
);
1129 log_info(LD_DIR
, "Reconstructing pointers into cache");
1132 SMARTLIST_FOREACH_BEGIN(signed_descriptors
, signed_descriptor_t
*, sd
) {
1133 if (sd
->do_not_cache
)
1135 sd
->saved_location
= SAVED_IN_CACHE
;
1137 tor_free(sd
->signed_descriptor_body
); // sets it to null
1138 sd
->saved_offset
= offset
;
1140 offset
+= sd
->signed_descriptor_len
+ sd
->annotations_len
;
1141 signed_descriptor_get_body(sd
); /* reconstruct and assert */
1142 } SMARTLIST_FOREACH_END(sd
);
1145 fname
= get_datadir_fname_suffix(store
->fname_base
, ".new");
1146 write_str_to_file(fname
, "", 1);
1149 store
->store_len
= (size_t) offset
;
1150 store
->journal_len
= 0;
1151 store
->bytes_dropped
= 0;
1153 smartlist_free(signed_descriptors
);
1155 tor_free(fname_tmp
);
1157 SMARTLIST_FOREACH(chunk_list
, sized_chunk_t
*, c
, tor_free(c
));
1158 smartlist_free(chunk_list
);
1164 /** Helper: Reload a cache file and its associated journal, setting metadata
1165 * appropriately. If <b>extrainfo</b> is true, reload the extrainfo store;
1166 * else reload the router descriptor store. */
1168 router_reload_router_list_impl(desc_store_t
*store
)
1170 char *fname
= NULL
, *contents
= NULL
;
1172 int extrainfo
= (store
->type
== EXTRAINFO_STORE
);
1173 store
->journal_len
= store
->store_len
= 0;
1175 fname
= get_datadir_fname(store
->fname_base
);
1178 /* get rid of it first */
1179 int res
= tor_munmap_file(store
->mmap
);
1182 log_warn(LD_FS
, "Failed to munmap %s", fname
);
1188 store
->mmap
= tor_mmap_file(fname
);
1190 store
->store_len
= store
->mmap
->size
;
1192 router_load_extrainfo_from_string(store
->mmap
->data
,
1193 store
->mmap
->data
+store
->mmap
->size
,
1194 SAVED_IN_CACHE
, NULL
, 0);
1196 router_load_routers_from_string(store
->mmap
->data
,
1197 store
->mmap
->data
+store
->mmap
->size
,
1198 SAVED_IN_CACHE
, NULL
, 0, NULL
);
1202 fname
= get_datadir_fname_suffix(store
->fname_base
, ".new");
1203 if (file_status(fname
) == FN_FILE
)
1204 contents
= read_file_to_str(fname
, RFTS_BIN
|RFTS_IGNORE_MISSING
, &st
);
1207 router_load_extrainfo_from_string(contents
, NULL
,SAVED_IN_JOURNAL
,
1210 router_load_routers_from_string(contents
, NULL
, SAVED_IN_JOURNAL
,
1212 store
->journal_len
= (size_t) st
.st_size
;
1218 if (store
->journal_len
) {
1219 /* Always clear the journal on startup.*/
1220 router_rebuild_store(RRS_FORCE
, store
);
1221 } else if (!extrainfo
) {
1222 /* Don't cache expired routers. (This is in an else because
1223 * router_rebuild_store() also calls remove_old_routers().) */
1224 routerlist_remove_old_routers();
1230 /** Load all cached router descriptors and extra-info documents from the
1231 * store. Return 0 on success and -1 on failure.
1234 router_reload_router_list(void)
1236 routerlist_t
*rl
= router_get_routerlist();
1237 if (router_reload_router_list_impl(&rl
->desc_store
))
1239 if (router_reload_router_list_impl(&rl
->extrainfo_store
))
1244 /** Return a smartlist containing a list of dir_server_t * for all
1245 * known trusted dirservers. Callers must not modify the list or its
1249 router_get_trusted_dir_servers(void)
1251 if (!trusted_dir_servers
)
1252 trusted_dir_servers
= smartlist_new();
1254 return trusted_dir_servers
;
1258 router_get_fallback_dir_servers(void)
1260 if (!fallback_dir_servers
)
1261 fallback_dir_servers
= smartlist_new();
1263 return fallback_dir_servers
;
1266 /** Try to find a running dirserver that supports operations of <b>type</b>.
1268 * If there are no running dirservers in our routerlist and the
1269 * <b>PDS_RETRY_IF_NO_SERVERS</b> flag is set, set all the authoritative ones
1270 * as running again, and pick one.
1272 * If the <b>PDS_IGNORE_FASCISTFIREWALL</b> flag is set, then include
1273 * dirservers that we can't reach.
1275 * If the <b>PDS_ALLOW_SELF</b> flag is not set, then don't include ourself
1276 * (if we're a dirserver).
1278 * Don't pick an authority if any non-authority is viable; try to avoid using
1279 * servers that have returned 503 recently.
1281 const routerstatus_t
*
1282 router_pick_directory_server(dirinfo_type_t type
, int flags
)
1284 const routerstatus_t
*choice
;
1289 choice
= router_pick_directory_server_impl(type
, flags
);
1290 if (choice
|| !(flags
& PDS_RETRY_IF_NO_SERVERS
))
1294 "No reachable router entries for dirservers. "
1295 "Trying them all again.");
1296 /* mark all authdirservers as up again */
1297 mark_all_dirservers_up(fallback_dir_servers
);
1299 choice
= router_pick_directory_server_impl(type
, flags
);
1303 /** Return the dir_server_t for the directory authority whose identity
1304 * key hashes to <b>digest</b>, or NULL if no such authority is known.
1307 router_get_trusteddirserver_by_digest(const char *digest
)
1309 if (!trusted_dir_servers
)
1312 SMARTLIST_FOREACH(trusted_dir_servers
, dir_server_t
*, ds
,
1314 if (tor_memeq(ds
->digest
, digest
, DIGEST_LEN
))
1321 /** Return the dir_server_t for the fallback dirserver whose identity
1322 * key hashes to <b>digest</b>, or NULL if no such authority is known.
1325 router_get_fallback_dirserver_by_digest(const char *digest
)
1327 if (!trusted_dir_servers
)
1330 SMARTLIST_FOREACH(trusted_dir_servers
, dir_server_t
*, ds
,
1332 if (tor_memeq(ds
->digest
, digest
, DIGEST_LEN
))
1339 /** Return the dir_server_t for the directory authority whose
1340 * v3 identity key hashes to <b>digest</b>, or NULL if no such authority
1344 trusteddirserver_get_by_v3_auth_digest(const char *digest
)
1346 if (!trusted_dir_servers
)
1349 SMARTLIST_FOREACH(trusted_dir_servers
, dir_server_t
*, ds
,
1351 if (tor_memeq(ds
->v3_identity_digest
, digest
, DIGEST_LEN
) &&
1352 (ds
->type
& V3_DIRINFO
))
1359 /** Try to find a running directory authority. Flags are as for
1360 * router_pick_directory_server.
1362 const routerstatus_t
*
1363 router_pick_trusteddirserver(dirinfo_type_t type
, int flags
)
1365 return router_pick_dirserver_generic(trusted_dir_servers
, type
, flags
);
1368 /** Try to find a running fallback directory. Flags are as for
1369 * router_pick_directory_server.
1371 const routerstatus_t
*
1372 router_pick_fallback_dirserver(dirinfo_type_t type
, int flags
)
1374 return router_pick_dirserver_generic(fallback_dir_servers
, type
, flags
);
1377 /** Try to find a running fallback directory. Flags are as for
1378 * router_pick_directory_server.
1380 static const routerstatus_t
*
1381 router_pick_dirserver_generic(smartlist_t
*sourcelist
,
1382 dirinfo_type_t type
, int flags
)
1384 const routerstatus_t
*choice
;
1387 choice
= router_pick_trusteddirserver_impl(sourcelist
, type
, flags
, &busy
);
1388 if (choice
|| !(flags
& PDS_RETRY_IF_NO_SERVERS
))
1391 /* If the reason that we got no server is that servers are "busy",
1392 * we must be excluding good servers because we already have serverdesc
1393 * fetches with them. Do not mark down servers up because of this. */
1394 tor_assert((flags
& (PDS_NO_EXISTING_SERVERDESC_FETCH
|
1395 PDS_NO_EXISTING_MICRODESC_FETCH
)));
1400 "No dirservers are reachable. Trying them all again.");
1401 mark_all_dirservers_up(sourcelist
);
1402 return router_pick_trusteddirserver_impl(sourcelist
, type
, flags
, NULL
);
1405 /** How long do we avoid using a directory server after it's given us a 503? */
1406 #define DIR_503_TIMEOUT (60*60)
1408 /** Pick a random running valid directory server/mirror from our
1409 * routerlist. Arguments are as for router_pick_directory_server(), except
1410 * that RETRY_IF_NO_SERVERS is ignored.
1412 static const routerstatus_t
*
1413 router_pick_directory_server_impl(dirinfo_type_t type
, int flags
)
1415 const or_options_t
*options
= get_options();
1416 const node_t
*result
;
1417 smartlist_t
*direct
, *tunnel
;
1418 smartlist_t
*trusted_direct
, *trusted_tunnel
;
1419 smartlist_t
*overloaded_direct
, *overloaded_tunnel
;
1420 time_t now
= time(NULL
);
1421 const networkstatus_t
*consensus
= networkstatus_get_latest_consensus();
1422 int requireother
= ! (flags
& PDS_ALLOW_SELF
);
1423 int fascistfirewall
= ! (flags
& PDS_IGNORE_FASCISTFIREWALL
);
1424 int for_guard
= (flags
& PDS_FOR_GUARD
);
1425 int try_excluding
= 1, n_excluded
= 0;
1430 retry_without_exclude
:
1432 direct
= smartlist_new();
1433 tunnel
= smartlist_new();
1434 trusted_direct
= smartlist_new();
1435 trusted_tunnel
= smartlist_new();
1436 overloaded_direct
= smartlist_new();
1437 overloaded_tunnel
= smartlist_new();
1439 /* Find all the running dirservers we know about. */
1440 SMARTLIST_FOREACH_BEGIN(nodelist_get_list(), const node_t
*, node
) {
1444 const routerstatus_t
*status
= node
->rs
;
1445 const country_t country
= node
->country
;
1449 if (!node
->is_running
|| !status
->dir_port
|| !node
->is_valid
)
1451 if (node
->is_bad_directory
)
1453 if (requireother
&& router_digest_is_me(node
->identity
))
1455 is_trusted
= router_digest_is_trusted_dir(node
->identity
);
1456 if ((type
& EXTRAINFO_DIRINFO
) &&
1457 !router_supports_extrainfo(node
->identity
, 0))
1459 if ((type
& MICRODESC_DIRINFO
) && !is_trusted
&&
1460 !node
->rs
->version_supports_microdesc_cache
)
1462 if (for_guard
&& node
->using_as_guard
)
1463 continue; /* Don't make the same node a guard twice. */
1464 if (try_excluding
&&
1465 routerset_contains_routerstatus(options
->ExcludeNodes
, status
,
1471 /* XXXX IP6 proposal 118 */
1472 tor_addr_from_ipv4h(&addr
, node
->rs
->addr
);
1474 is_overloaded
= status
->last_dir_503_at
+ DIR_503_TIMEOUT
> now
;
1476 if ((!fascistfirewall
||
1477 fascist_firewall_allows_address_or(&addr
, status
->or_port
)))
1478 smartlist_add(is_trusted
? trusted_tunnel
:
1479 is_overloaded
? overloaded_tunnel
: tunnel
, (void*)node
);
1480 else if (!fascistfirewall
||
1481 fascist_firewall_allows_address_dir(&addr
, status
->dir_port
))
1482 smartlist_add(is_trusted
? trusted_direct
:
1483 is_overloaded
? overloaded_direct
: direct
, (void*)node
);
1484 } SMARTLIST_FOREACH_END(node
);
1486 if (smartlist_len(tunnel
)) {
1487 result
= node_sl_choose_by_bandwidth(tunnel
, WEIGHT_FOR_DIR
);
1488 } else if (smartlist_len(overloaded_tunnel
)) {
1489 result
= node_sl_choose_by_bandwidth(overloaded_tunnel
,
1491 } else if (smartlist_len(trusted_tunnel
)) {
1492 /* FFFF We don't distinguish between trusteds and overloaded trusteds
1493 * yet. Maybe one day we should. */
1494 /* FFFF We also don't load balance over authorities yet. I think this
1495 * is a feature, but it could easily be a bug. -RD */
1496 result
= smartlist_choose(trusted_tunnel
);
1497 } else if (smartlist_len(direct
)) {
1498 result
= node_sl_choose_by_bandwidth(direct
, WEIGHT_FOR_DIR
);
1499 } else if (smartlist_len(overloaded_direct
)) {
1500 result
= node_sl_choose_by_bandwidth(overloaded_direct
,
1503 result
= smartlist_choose(trusted_direct
);
1505 smartlist_free(direct
);
1506 smartlist_free(tunnel
);
1507 smartlist_free(trusted_direct
);
1508 smartlist_free(trusted_tunnel
);
1509 smartlist_free(overloaded_direct
);
1510 smartlist_free(overloaded_tunnel
);
1512 if (result
== NULL
&& try_excluding
&& !options
->StrictNodes
&& n_excluded
) {
1513 /* If we got no result, and we are excluding nodes, and StrictNodes is
1514 * not set, try again without excluding nodes. */
1517 goto retry_without_exclude
;
1520 return result
? result
->rs
: NULL
;
1523 /** Pick a random element from a list of dir_server_t, weighting by their
1524 * <b>weight</b> field. */
1525 static const dir_server_t
*
1526 dirserver_choose_by_weight(const smartlist_t
*servers
, double authority_weight
)
1528 int n
= smartlist_len(servers
);
1531 const dir_server_t
*ds
;
1533 weights
= tor_malloc(sizeof(u64_dbl_t
) * n
);
1534 for (i
= 0; i
< n
; ++i
) {
1535 ds
= smartlist_get(servers
, i
);
1536 weights
[i
].dbl
= ds
->weight
;
1537 if (ds
->is_authority
)
1538 weights
[i
].dbl
*= authority_weight
;
1541 scale_array_elements_to_u64(weights
, n
, NULL
);
1542 i
= choose_array_element_by_weight(weights
, n
);
1544 return (i
< 0) ? NULL
: smartlist_get(servers
, i
);
1547 /** Choose randomly from among the dir_server_ts in sourcelist that
1548 * are up. Flags are as for router_pick_directory_server_impl().
1550 static const routerstatus_t
*
1551 router_pick_trusteddirserver_impl(const smartlist_t
*sourcelist
,
1552 dirinfo_type_t type
, int flags
,
1555 const or_options_t
*options
= get_options();
1556 smartlist_t
*direct
, *tunnel
;
1557 smartlist_t
*overloaded_direct
, *overloaded_tunnel
;
1558 const routerinfo_t
*me
= router_get_my_routerinfo();
1559 const routerstatus_t
*result
= NULL
;
1560 time_t now
= time(NULL
);
1561 const int requireother
= ! (flags
& PDS_ALLOW_SELF
);
1562 const int fascistfirewall
= ! (flags
& PDS_IGNORE_FASCISTFIREWALL
);
1563 const int no_serverdesc_fetching
=(flags
& PDS_NO_EXISTING_SERVERDESC_FETCH
);
1564 const int no_microdesc_fetching
=(flags
& PDS_NO_EXISTING_MICRODESC_FETCH
);
1565 const double auth_weight
= (sourcelist
== fallback_dir_servers
) ?
1566 options
->DirAuthorityFallbackRate
: 1.0;
1567 smartlist_t
*pick_from
;
1569 int try_excluding
= 1, n_excluded
= 0;
1574 retry_without_exclude
:
1576 direct
= smartlist_new();
1577 tunnel
= smartlist_new();
1578 overloaded_direct
= smartlist_new();
1579 overloaded_tunnel
= smartlist_new();
1581 SMARTLIST_FOREACH_BEGIN(sourcelist
, const dir_server_t
*, d
)
1584 d
->fake_status
.last_dir_503_at
+ DIR_503_TIMEOUT
> now
;
1586 if (!d
->is_running
) continue;
1587 if ((type
& d
->type
) == 0)
1589 if ((type
& EXTRAINFO_DIRINFO
) &&
1590 !router_supports_extrainfo(d
->digest
, 1))
1592 if (requireother
&& me
&& router_digest_is_me(d
->digest
))
1594 if (try_excluding
&&
1595 routerset_contains_routerstatus(options
->ExcludeNodes
,
1596 &d
->fake_status
, -1)) {
1601 /* XXXX IP6 proposal 118 */
1602 tor_addr_from_ipv4h(&addr
, d
->addr
);
1604 if (no_serverdesc_fetching
) {
1605 if (connection_get_by_type_addr_port_purpose(
1606 CONN_TYPE_DIR
, &addr
, d
->dir_port
, DIR_PURPOSE_FETCH_SERVERDESC
)
1607 || connection_get_by_type_addr_port_purpose(
1608 CONN_TYPE_DIR
, &addr
, d
->dir_port
, DIR_PURPOSE_FETCH_EXTRAINFO
)) {
1609 //log_debug(LD_DIR, "We have an existing connection to fetch "
1610 // "descriptor from %s; delaying",d->description);
1615 if (no_microdesc_fetching
) {
1616 if (connection_get_by_type_addr_port_purpose(
1617 CONN_TYPE_DIR
, &addr
, d
->dir_port
, DIR_PURPOSE_FETCH_MICRODESC
)) {
1624 (!fascistfirewall
||
1625 fascist_firewall_allows_address_or(&addr
, d
->or_port
)))
1626 smartlist_add(is_overloaded
? overloaded_tunnel
: tunnel
, (void*)d
);
1627 else if (!fascistfirewall
||
1628 fascist_firewall_allows_address_dir(&addr
, d
->dir_port
))
1629 smartlist_add(is_overloaded
? overloaded_direct
: direct
, (void*)d
);
1631 SMARTLIST_FOREACH_END(d
);
1633 if (smartlist_len(tunnel
)) {
1635 } else if (smartlist_len(overloaded_tunnel
)) {
1636 pick_from
= overloaded_tunnel
;
1637 } else if (smartlist_len(direct
)) {
1640 pick_from
= overloaded_direct
;
1644 const dir_server_t
*selection
=
1645 dirserver_choose_by_weight(pick_from
, auth_weight
);
1648 result
= &selection
->fake_status
;
1652 *n_busy_out
= n_busy
;
1654 smartlist_free(direct
);
1655 smartlist_free(tunnel
);
1656 smartlist_free(overloaded_direct
);
1657 smartlist_free(overloaded_tunnel
);
1659 if (result
== NULL
&& try_excluding
&& !options
->StrictNodes
&& n_excluded
) {
1660 /* If we got no result, and we are excluding nodes, and StrictNodes is
1661 * not set, try again without excluding nodes. */
1664 goto retry_without_exclude
;
1670 /** Mark as running every dir_server_t in <b>server_list</b>. */
1672 mark_all_dirservers_up(smartlist_t
*server_list
)
1675 SMARTLIST_FOREACH_BEGIN(server_list
, dir_server_t
*, dir
) {
1678 dir
->is_running
= 1;
1679 node
= node_get_mutable_by_id(dir
->digest
);
1681 node
->is_running
= 1;
1682 rs
= router_get_mutable_consensus_status_by_id(dir
->digest
);
1684 rs
->last_dir_503_at
= 0;
1685 control_event_networkstatus_changed_single(rs
);
1687 } SMARTLIST_FOREACH_END(dir
);
1689 router_dir_info_changed();
1692 /** Return true iff r1 and r2 have the same address and OR port. */
1694 routers_have_same_or_addrs(const routerinfo_t
*r1
, const routerinfo_t
*r2
)
1696 return r1
->addr
== r2
->addr
&& r1
->or_port
== r2
->or_port
&&
1697 tor_addr_eq(&r1
->ipv6_addr
, &r2
->ipv6_addr
) &&
1698 r1
->ipv6_orport
== r2
->ipv6_orport
;
1701 /** Reset all internal variables used to count failed downloads of network
1702 * status objects. */
1704 router_reset_status_download_failures(void)
1706 mark_all_dirservers_up(fallback_dir_servers
);
1709 /** Given a <b>router</b>, add every node_t in its family (including the
1710 * node itself!) to <b>sl</b>.
1712 * Note the type mismatch: This function takes a routerinfo, but adds nodes
1716 routerlist_add_node_and_family(smartlist_t
*sl
, const routerinfo_t
*router
)
1720 const node_t
*node
= node_get_by_id(router
->cache_info
.identity_digest
);;
1722 memset(&fake_node
, 0, sizeof(fake_node
));
1723 fake_node
.ri
= (routerinfo_t
*)router
;
1724 memcpy(fake_node
.identity
, router
->cache_info
.identity_digest
, DIGEST_LEN
);
1727 nodelist_add_node_and_family(sl
, node
);
1730 /** Add every suitable node from our nodelist to <b>sl</b>, so that
1731 * we can pick a node for a circuit.
1734 router_add_running_nodes_to_smartlist(smartlist_t
*sl
, int allow_invalid
,
1735 int need_uptime
, int need_capacity
,
1736 int need_guard
, int need_desc
)
1738 SMARTLIST_FOREACH_BEGIN(nodelist_get_list(), const node_t
*, node
) {
1739 if (!node
->is_running
||
1740 (!node
->is_valid
&& !allow_invalid
))
1742 if (need_desc
&& !(node
->ri
|| (node
->rs
&& node
->md
)))
1744 if (node
->ri
&& node
->ri
->purpose
!= ROUTER_PURPOSE_GENERAL
)
1746 if (node_is_unreliable(node
, need_uptime
, need_capacity
, need_guard
))
1749 smartlist_add(sl
, (void *)node
);
1750 } SMARTLIST_FOREACH_END(node
);
1753 /** Look through the routerlist until we find a router that has my key.
1755 const routerinfo_t
*
1756 routerlist_find_my_routerinfo(void)
1761 SMARTLIST_FOREACH(routerlist
->routers
, routerinfo_t
*, router
,
1763 if (router_is_me(router
))
1769 /** Return the smaller of the router's configured BandwidthRate
1770 * and its advertised capacity. */
1772 router_get_advertised_bandwidth(const routerinfo_t
*router
)
1774 if (router
->bandwidthcapacity
< router
->bandwidthrate
)
1775 return router
->bandwidthcapacity
;
1776 return router
->bandwidthrate
;
1779 /** Do not weight any declared bandwidth more than this much when picking
1780 * routers by bandwidth. */
1781 #define DEFAULT_MAX_BELIEVABLE_BANDWIDTH 10000000 /* 10 MB/sec */
1783 /** Return the smaller of the router's configured BandwidthRate
1784 * and its advertised capacity, capped by max-believe-bw. */
1786 router_get_advertised_bandwidth_capped(const routerinfo_t
*router
)
1788 uint32_t result
= router
->bandwidthcapacity
;
1789 if (result
> router
->bandwidthrate
)
1790 result
= router
->bandwidthrate
;
1791 if (result
> DEFAULT_MAX_BELIEVABLE_BANDWIDTH
)
1792 result
= DEFAULT_MAX_BELIEVABLE_BANDWIDTH
;
1796 /** Given an array of double/uint64_t unions that are currently being used as
1797 * doubles, convert them to uint64_t, and try to scale them linearly so as to
1798 * much of the range of uint64_t. If <b>total_out</b> is provided, set it to
1799 * the sum of all elements in the array _before_ scaling. */
1801 scale_array_elements_to_u64(u64_dbl_t
*entries
, int n_entries
,
1802 uint64_t *total_out
)
1805 double scale_factor
;
1807 /* big, but far away from overflowing an int64_t */
1808 #define SCALE_TO_U64_MAX (INT64_MAX / 4)
1810 for (i
= 0; i
< n_entries
; ++i
)
1811 total
+= entries
[i
].dbl
;
1813 scale_factor
= SCALE_TO_U64_MAX
/ total
;
1815 for (i
= 0; i
< n_entries
; ++i
)
1816 entries
[i
].u64
= tor_llround(entries
[i
].dbl
* scale_factor
);
1819 *total_out
= (uint64_t) total
;
1821 #undef SCALE_TO_U64_MAX
1824 /** Time-invariant 64-bit greater-than; works on two integers in the range
1826 #if SIZEOF_VOID_P == 8
1827 #define gt_i64_timei(a,b) ((a) > (b))
1830 gt_i64_timei(uint64_t a
, uint64_t b
)
1832 int64_t diff
= (int64_t) (b
- a
);
1833 int res
= diff
>> 63;
1838 /** Pick a random element of <b>n_entries</b>-element array <b>entries</b>,
1839 * choosing each element with a probability proportional to its (uint64_t)
1840 * value, and return the index of that element. If all elements are 0, choose
1841 * an index at random. Return -1 on error.
1844 choose_array_element_by_weight(const u64_dbl_t
*entries
, int n_entries
)
1846 int i
, i_chosen
=-1, n_chosen
=0;
1847 uint64_t total_so_far
= 0;
1851 for (i
= 0; i
< n_entries
; ++i
)
1852 total
+= entries
[i
].u64
;
1858 return crypto_rand_int(n_entries
);
1860 tor_assert(total
< INT64_MAX
);
1862 rand_val
= crypto_rand_uint64(total
);
1864 for (i
= 0; i
< n_entries
; ++i
) {
1865 total_so_far
+= entries
[i
].u64
;
1866 if (gt_i64_timei(total_so_far
, rand_val
)) {
1869 /* Set rand_val to INT64_MAX rather than stopping the loop. This way,
1870 * the time we spend in the loop does not leak which element we chose. */
1871 rand_val
= INT64_MAX
;
1874 tor_assert(total_so_far
== total
);
1875 tor_assert(n_chosen
== 1);
1876 tor_assert(i_chosen
>= 0);
1877 tor_assert(i_chosen
< n_entries
);
1882 /** When weighting bridges, enforce these values as lower and upper
1883 * bound for believable bandwidth, because there is no way for us
1884 * to verify a bridge's bandwidth currently. */
1885 #define BRIDGE_MIN_BELIEVABLE_BANDWIDTH 20000 /* 20 kB/sec */
1886 #define BRIDGE_MAX_BELIEVABLE_BANDWIDTH 100000 /* 100 kB/sec */
1888 /** Return the smaller of the router's configured BandwidthRate
1889 * and its advertised capacity, making sure to stay within the
1890 * interval between bridge-min-believe-bw and
1891 * bridge-max-believe-bw. */
1893 bridge_get_advertised_bandwidth_bounded(routerinfo_t
*router
)
1895 uint32_t result
= router
->bandwidthcapacity
;
1896 if (result
> router
->bandwidthrate
)
1897 result
= router
->bandwidthrate
;
1898 if (result
> BRIDGE_MAX_BELIEVABLE_BANDWIDTH
)
1899 result
= BRIDGE_MAX_BELIEVABLE_BANDWIDTH
;
1900 else if (result
< BRIDGE_MIN_BELIEVABLE_BANDWIDTH
)
1901 result
= BRIDGE_MIN_BELIEVABLE_BANDWIDTH
;
1905 /** Return bw*1000, unless bw*1000 would overflow, in which case return
1907 static INLINE
int32_t
1908 kb_to_bytes(uint32_t bw
)
1910 return (bw
> (INT32_MAX
/1000)) ? INT32_MAX
: bw
*1000;
1913 /** Helper function:
1914 * choose a random element of smartlist <b>sl</b> of nodes, weighted by
1915 * the advertised bandwidth of each element using the consensus
1916 * bandwidth weights.
1918 * If <b>rule</b>==WEIGHT_FOR_EXIT. we're picking an exit node: consider all
1919 * nodes' bandwidth equally regardless of their Exit status, since there may
1920 * be some in the list because they exit to obscure ports. If
1921 * <b>rule</b>==NO_WEIGHTING, we're picking a non-exit node: weight
1922 * exit-node's bandwidth less depending on the smallness of the fraction of
1923 * Exit-to-total bandwidth. If <b>rule</b>==WEIGHT_FOR_GUARD, we're picking a
1924 * guard node: consider all guard's bandwidth equally. Otherwise, weight
1925 * guards proportionally less.
1927 static const node_t
*
1928 smartlist_choose_node_by_bandwidth_weights(const smartlist_t
*sl
,
1929 bandwidth_weight_rule_t rule
)
1931 u64_dbl_t
*bandwidths
=NULL
;
1933 if (compute_weighted_bandwidths(sl
, rule
, &bandwidths
) < 0)
1936 scale_array_elements_to_u64(bandwidths
, smartlist_len(sl
), NULL
);
1939 int idx
= choose_array_element_by_weight(bandwidths
,
1941 tor_free(bandwidths
);
1942 return idx
< 0 ? NULL
: smartlist_get(sl
, idx
);
1946 /** Given a list of routers and a weighting rule as in
1947 * smartlist_choose_node_by_bandwidth_weights, compute weighted bandwidth
1948 * values for each node and store them in a freshly allocated
1949 * *<b>bandwidths_out</b> of the same length as <b>sl</b>, and holding results
1950 * as doubles. Return 0 on success, -1 on failure. */
1952 compute_weighted_bandwidths(const smartlist_t
*sl
,
1953 bandwidth_weight_rule_t rule
,
1954 u64_dbl_t
**bandwidths_out
)
1956 int64_t weight_scale
;
1957 double Wg
= -1, Wm
= -1, We
= -1, Wd
= -1;
1958 double Wgb
= -1, Wmb
= -1, Web
= -1, Wdb
= -1;
1959 uint64_t weighted_bw
= 0;
1960 u64_dbl_t
*bandwidths
;
1962 /* Can't choose exit and guard at same time */
1963 tor_assert(rule
== NO_WEIGHTING
||
1964 rule
== WEIGHT_FOR_EXIT
||
1965 rule
== WEIGHT_FOR_GUARD
||
1966 rule
== WEIGHT_FOR_MID
||
1967 rule
== WEIGHT_FOR_DIR
);
1969 if (smartlist_len(sl
) == 0) {
1971 "Empty routerlist passed in to consensus weight node "
1972 "selection for rule %s",
1973 bandwidth_weight_rule_to_string(rule
));
1977 weight_scale
= networkstatus_get_weight_scale_param(NULL
);
1979 if (rule
== WEIGHT_FOR_GUARD
) {
1980 Wg
= networkstatus_get_bw_weight(NULL
, "Wgg", -1);
1981 Wm
= networkstatus_get_bw_weight(NULL
, "Wgm", -1); /* Bridges */
1983 Wd
= networkstatus_get_bw_weight(NULL
, "Wgd", -1);
1985 Wgb
= networkstatus_get_bw_weight(NULL
, "Wgb", -1);
1986 Wmb
= networkstatus_get_bw_weight(NULL
, "Wmb", -1);
1987 Web
= networkstatus_get_bw_weight(NULL
, "Web", -1);
1988 Wdb
= networkstatus_get_bw_weight(NULL
, "Wdb", -1);
1989 } else if (rule
== WEIGHT_FOR_MID
) {
1990 Wg
= networkstatus_get_bw_weight(NULL
, "Wmg", -1);
1991 Wm
= networkstatus_get_bw_weight(NULL
, "Wmm", -1);
1992 We
= networkstatus_get_bw_weight(NULL
, "Wme", -1);
1993 Wd
= networkstatus_get_bw_weight(NULL
, "Wmd", -1);
1995 Wgb
= networkstatus_get_bw_weight(NULL
, "Wgb", -1);
1996 Wmb
= networkstatus_get_bw_weight(NULL
, "Wmb", -1);
1997 Web
= networkstatus_get_bw_weight(NULL
, "Web", -1);
1998 Wdb
= networkstatus_get_bw_weight(NULL
, "Wdb", -1);
1999 } else if (rule
== WEIGHT_FOR_EXIT
) {
2000 // Guards CAN be exits if they have weird exit policies
2001 // They are d then I guess...
2002 We
= networkstatus_get_bw_weight(NULL
, "Wee", -1);
2003 Wm
= networkstatus_get_bw_weight(NULL
, "Wem", -1); /* Odd exit policies */
2004 Wd
= networkstatus_get_bw_weight(NULL
, "Wed", -1);
2005 Wg
= networkstatus_get_bw_weight(NULL
, "Weg", -1); /* Odd exit policies */
2007 Wgb
= networkstatus_get_bw_weight(NULL
, "Wgb", -1);
2008 Wmb
= networkstatus_get_bw_weight(NULL
, "Wmb", -1);
2009 Web
= networkstatus_get_bw_weight(NULL
, "Web", -1);
2010 Wdb
= networkstatus_get_bw_weight(NULL
, "Wdb", -1);
2011 } else if (rule
== WEIGHT_FOR_DIR
) {
2012 We
= networkstatus_get_bw_weight(NULL
, "Wbe", -1);
2013 Wm
= networkstatus_get_bw_weight(NULL
, "Wbm", -1);
2014 Wd
= networkstatus_get_bw_weight(NULL
, "Wbd", -1);
2015 Wg
= networkstatus_get_bw_weight(NULL
, "Wbg", -1);
2017 Wgb
= Wmb
= Web
= Wdb
= weight_scale
;
2018 } else if (rule
== NO_WEIGHTING
) {
2019 Wg
= Wm
= We
= Wd
= weight_scale
;
2020 Wgb
= Wmb
= Web
= Wdb
= weight_scale
;
2023 if (Wg
< 0 || Wm
< 0 || We
< 0 || Wd
< 0 || Wgb
< 0 || Wmb
< 0 || Wdb
< 0
2026 "Got negative bandwidth weights. Defaulting to old selection"
2028 return -1; // Use old algorithm.
2036 Wgb
/= weight_scale
;
2037 Wmb
/= weight_scale
;
2038 Web
/= weight_scale
;
2039 Wdb
/= weight_scale
;
2041 bandwidths
= tor_malloc_zero(sizeof(u64_dbl_t
)*smartlist_len(sl
));
2043 // Cycle through smartlist and total the bandwidth.
2044 SMARTLIST_FOREACH_BEGIN(sl
, const node_t
*, node
) {
2045 int is_exit
= 0, is_guard
= 0, is_dir
= 0, this_bw
= 0;
2047 is_exit
= node
->is_exit
&& ! node
->is_bad_exit
;
2048 is_guard
= node
->is_possible_guard
;
2049 is_dir
= node_is_dir(node
);
2051 if (!node
->rs
->has_bandwidth
) {
2052 tor_free(bandwidths
);
2053 /* This should never happen, unless all the authorites downgrade
2054 * to 0.2.0 or rogue routerstatuses get inserted into our consensus. */
2056 "Consensus is not listing bandwidths. Defaulting back to "
2057 "old router selection algorithm.");
2060 this_bw
= kb_to_bytes(node
->rs
->bandwidth_kb
);
2061 } else if (node
->ri
) {
2062 /* bridge or other descriptor not in our consensus */
2063 this_bw
= bridge_get_advertised_bandwidth_bounded(node
->ri
);
2065 /* We can't use this one. */
2069 if (is_guard
&& is_exit
) {
2070 weight
= (is_dir
? Wdb
*Wd
: Wd
);
2071 } else if (is_guard
) {
2072 weight
= (is_dir
? Wgb
*Wg
: Wg
);
2073 } else if (is_exit
) {
2074 weight
= (is_dir
? Web
*We
: We
);
2076 weight
= (is_dir
? Wmb
*Wm
: Wm
);
2078 /* These should be impossible; but overflows here would be bad, so let's
2085 bandwidths
[node_sl_idx
].dbl
= weight
*this_bw
+ 0.5;
2086 } SMARTLIST_FOREACH_END(node
);
2088 log_debug(LD_CIRC
, "Generated weighted bandwidths for rule %s based "
2090 "Wg=%f Wm=%f We=%f Wd=%f with total bw "U64_FORMAT
,
2091 bandwidth_weight_rule_to_string(rule
),
2092 Wg
, Wm
, We
, Wd
, U64_PRINTF_ARG(weighted_bw
));
2094 *bandwidths_out
= bandwidths
;
2099 /** For all nodes in <b>sl</b>, return the fraction of those nodes, weighted
2100 * by their weighted bandwidths with rule <b>rule</b>, for which we have
2103 frac_nodes_with_descriptors(const smartlist_t
*sl
,
2104 bandwidth_weight_rule_t rule
)
2106 u64_dbl_t
*bandwidths
= NULL
;
2107 double total
, present
;
2109 if (smartlist_len(sl
) == 0)
2112 if (compute_weighted_bandwidths(sl
, rule
, &bandwidths
) < 0) {
2113 int n_with_descs
= 0;
2114 SMARTLIST_FOREACH(sl
, const node_t
*, node
, {
2115 if (node_has_descriptor(node
))
2118 return ((double)n_with_descs
) / (double)smartlist_len(sl
);
2121 total
= present
= 0.0;
2122 SMARTLIST_FOREACH_BEGIN(sl
, const node_t
*, node
) {
2123 const double bw
= bandwidths
[node_sl_idx
].dbl
;
2125 if (node_has_descriptor(node
))
2127 } SMARTLIST_FOREACH_END(node
);
2129 tor_free(bandwidths
);
2134 return present
/ total
;
2137 /** Helper function:
2138 * choose a random node_t element of smartlist <b>sl</b>, weighted by
2139 * the advertised bandwidth of each element.
2141 * If <b>rule</b>==WEIGHT_FOR_EXIT. we're picking an exit node: consider all
2142 * nodes' bandwidth equally regardless of their Exit status, since there may
2143 * be some in the list because they exit to obscure ports. If
2144 * <b>rule</b>==NO_WEIGHTING, we're picking a non-exit node: weight
2145 * exit-node's bandwidth less depending on the smallness of the fraction of
2146 * Exit-to-total bandwidth. If <b>rule</b>==WEIGHT_FOR_GUARD, we're picking a
2147 * guard node: consider all guard's bandwidth equally. Otherwise, weight
2148 * guards proportionally less.
2150 static const node_t
*
2151 smartlist_choose_node_by_bandwidth(const smartlist_t
*sl
,
2152 bandwidth_weight_rule_t rule
)
2155 u64_dbl_t
*bandwidths
;
2159 double total_nonexit_bw
= 0, total_exit_bw
= 0;
2160 double total_nonguard_bw
= 0, total_guard_bw
= 0;
2162 double guard_weight
;
2164 bitarray_t
*fast_bits
;
2165 bitarray_t
*exit_bits
;
2166 bitarray_t
*guard_bits
;
2168 // This function does not support WEIGHT_FOR_DIR
2169 // or WEIGHT_FOR_MID
2170 if (rule
== WEIGHT_FOR_DIR
|| rule
== WEIGHT_FOR_MID
) {
2171 rule
= NO_WEIGHTING
;
2174 /* Can't choose exit and guard at same time */
2175 tor_assert(rule
== NO_WEIGHTING
||
2176 rule
== WEIGHT_FOR_EXIT
||
2177 rule
== WEIGHT_FOR_GUARD
);
2179 if (smartlist_len(sl
) == 0) {
2181 "Empty routerlist passed in to old node selection for rule %s",
2182 bandwidth_weight_rule_to_string(rule
));
2186 /* First count the total bandwidth weight, and make a list
2187 * of each value. We use UINT64_MAX to indicate "unknown". */
2188 bandwidths
= tor_malloc_zero(sizeof(u64_dbl_t
)*smartlist_len(sl
));
2189 fast_bits
= bitarray_init_zero(smartlist_len(sl
));
2190 exit_bits
= bitarray_init_zero(smartlist_len(sl
));
2191 guard_bits
= bitarray_init_zero(smartlist_len(sl
));
2193 /* Iterate over all the routerinfo_t or routerstatus_t, and */
2194 SMARTLIST_FOREACH_BEGIN(sl
, const node_t
*, node
) {
2195 /* first, learn what bandwidth we think i has */
2197 uint32_t this_bw
= 0;
2200 is_exit
= node
->is_exit
;
2201 is_guard
= node
->is_possible_guard
;
2203 if (node
->rs
->has_bandwidth
) {
2204 this_bw
= kb_to_bytes(node
->rs
->bandwidth_kb
);
2205 } else { /* guess */
2208 } else if (node
->ri
) {
2209 /* Must be a bridge if we're willing to use it */
2210 this_bw
= bridge_get_advertised_bandwidth_bounded(node
->ri
);
2214 bitarray_set(exit_bits
, i
);
2216 bitarray_set(guard_bits
, i
);
2218 bitarray_set(fast_bits
, i
);
2221 bandwidths
[i
].dbl
= this_bw
;
2223 total_guard_bw
+= this_bw
;
2225 total_nonguard_bw
+= this_bw
;
2227 total_exit_bw
+= this_bw
;
2229 total_nonexit_bw
+= this_bw
;
2232 bandwidths
[i
].dbl
= -1.0;
2234 } SMARTLIST_FOREACH_END(node
);
2238 /* Now, fill in the unknown values. */
2240 int32_t avg_fast
, avg_slow
;
2241 if (total_exit_bw
+total_nonexit_bw
< EPSILON
) {
2242 /* if there's some bandwidth, there's at least one known router,
2243 * so no worries about div by 0 here */
2244 int n_known
= smartlist_len(sl
)-n_unknown
;
2245 avg_fast
= avg_slow
= (int32_t)
2246 ((total_exit_bw
+total_nonexit_bw
)/((uint64_t) n_known
));
2251 for (i
=0; i
<(unsigned)smartlist_len(sl
); ++i
) {
2252 if (bandwidths
[i
].dbl
>= 0.0)
2254 is_fast
= bitarray_is_set(fast_bits
, i
);
2255 is_exit
= bitarray_is_set(exit_bits
, i
);
2256 is_guard
= bitarray_is_set(guard_bits
, i
);
2257 bandwidths
[i
].dbl
= is_fast
? avg_fast
: avg_slow
;
2259 total_exit_bw
+= bandwidths
[i
].dbl
;
2261 total_nonexit_bw
+= bandwidths
[i
].dbl
;
2263 total_guard_bw
+= bandwidths
[i
].dbl
;
2265 total_nonguard_bw
+= bandwidths
[i
].dbl
;
2269 /* If there's no bandwidth at all, pick at random. */
2270 if (total_exit_bw
+total_nonexit_bw
< EPSILON
) {
2271 tor_free(bandwidths
);
2272 tor_free(fast_bits
);
2273 tor_free(exit_bits
);
2274 tor_free(guard_bits
);
2275 return smartlist_choose(sl
);
2278 /* Figure out how to weight exits and guards */
2280 double all_bw
= U64_TO_DBL(total_exit_bw
+total_nonexit_bw
);
2281 double exit_bw
= U64_TO_DBL(total_exit_bw
);
2282 double guard_bw
= U64_TO_DBL(total_guard_bw
);
2284 * For detailed derivation of this formula, see
2285 * http://archives.seul.org/or/dev/Jul-2007/msg00056.html
2287 if (rule
== WEIGHT_FOR_EXIT
|| total_exit_bw
<EPSILON
)
2290 exit_weight
= 1.0 - all_bw
/(3.0*exit_bw
);
2292 if (rule
== WEIGHT_FOR_GUARD
|| total_guard_bw
<EPSILON
)
2295 guard_weight
= 1.0 - all_bw
/(3.0*guard_bw
);
2297 if (exit_weight
<= 0.0)
2300 if (guard_weight
<= 0.0)
2303 for (i
=0; i
< (unsigned)smartlist_len(sl
); i
++) {
2304 tor_assert(bandwidths
[i
].dbl
>= 0.0);
2306 is_exit
= bitarray_is_set(exit_bits
, i
);
2307 is_guard
= bitarray_is_set(guard_bits
, i
);
2308 if (is_exit
&& is_guard
)
2309 bandwidths
[i
].dbl
*= exit_weight
* guard_weight
;
2311 bandwidths
[i
].dbl
*= guard_weight
;
2313 bandwidths
[i
].dbl
*= exit_weight
;
2318 log_debug(LD_CIRC
, "Total weighted bw = "U64_FORMAT
2319 ", exit bw = "U64_FORMAT
2320 ", nonexit bw = "U64_FORMAT
", exit weight = %f "
2322 ", guard bw = "U64_FORMAT
2323 ", nonguard bw = "U64_FORMAT
", guard weight = %f "
2324 "(for guard == %d)",
2325 U64_PRINTF_ARG(total_bw
),
2326 U64_PRINTF_ARG(total_exit_bw
), U64_PRINTF_ARG(total_nonexit_bw
),
2327 exit_weight
, (int)(rule
== WEIGHT_FOR_EXIT
),
2328 U64_PRINTF_ARG(total_guard_bw
), U64_PRINTF_ARG(total_nonguard_bw
),
2329 guard_weight
, (int)(rule
== WEIGHT_FOR_GUARD
));
2332 scale_array_elements_to_u64(bandwidths
, smartlist_len(sl
), NULL
);
2335 int idx
= choose_array_element_by_weight(bandwidths
,
2337 tor_free(bandwidths
);
2338 tor_free(fast_bits
);
2339 tor_free(exit_bits
);
2340 tor_free(guard_bits
);
2341 return idx
< 0 ? NULL
: smartlist_get(sl
, idx
);
2345 /** Choose a random element of status list <b>sl</b>, weighted by
2346 * the advertised bandwidth of each node */
2348 node_sl_choose_by_bandwidth(const smartlist_t
*sl
,
2349 bandwidth_weight_rule_t rule
)
2352 if ((ret
= smartlist_choose_node_by_bandwidth_weights(sl
, rule
))) {
2355 return smartlist_choose_node_by_bandwidth(sl
, rule
);
2359 /** Return a random running node from the nodelist. Never
2360 * pick a node that is in
2361 * <b>excludedsmartlist</b>, or which matches <b>excludedset</b>,
2362 * even if they are the only nodes available.
2363 * If <b>CRN_NEED_UPTIME</b> is set in flags and any router has more than
2364 * a minimum uptime, return one of those.
2365 * If <b>CRN_NEED_CAPACITY</b> is set in flags, weight your choice by the
2366 * advertised capacity of each router.
2367 * If <b>CRN_ALLOW_INVALID</b> is not set in flags, consider only Valid
2369 * If <b>CRN_NEED_GUARD</b> is set in flags, consider only Guard routers.
2370 * If <b>CRN_WEIGHT_AS_EXIT</b> is set in flags, we weight bandwidths as if
2371 * picking an exit node, otherwise we weight bandwidths for picking a relay
2372 * node (that is, possibly discounting exit nodes).
2373 * If <b>CRN_NEED_DESC</b> is set in flags, we only consider nodes that
2374 * have a routerinfo or microdescriptor -- that is, enough info to be
2375 * used to build a circuit.
2378 router_choose_random_node(smartlist_t
*excludedsmartlist
,
2379 routerset_t
*excludedset
,
2380 router_crn_flags_t flags
)
2382 const int need_uptime
= (flags
& CRN_NEED_UPTIME
) != 0;
2383 const int need_capacity
= (flags
& CRN_NEED_CAPACITY
) != 0;
2384 const int need_guard
= (flags
& CRN_NEED_GUARD
) != 0;
2385 const int allow_invalid
= (flags
& CRN_ALLOW_INVALID
) != 0;
2386 const int weight_for_exit
= (flags
& CRN_WEIGHT_AS_EXIT
) != 0;
2387 const int need_desc
= (flags
& CRN_NEED_DESC
) != 0;
2389 smartlist_t
*sl
=smartlist_new(),
2390 *excludednodes
=smartlist_new();
2391 const node_t
*choice
= NULL
;
2392 const routerinfo_t
*r
;
2393 bandwidth_weight_rule_t rule
;
2395 tor_assert(!(weight_for_exit
&& need_guard
));
2396 rule
= weight_for_exit
? WEIGHT_FOR_EXIT
:
2397 (need_guard
? WEIGHT_FOR_GUARD
: WEIGHT_FOR_MID
);
2399 /* Exclude relays that allow single hop exit circuits, if the user
2400 * wants to (such relays might be risky) */
2401 if (get_options()->ExcludeSingleHopRelays
) {
2402 SMARTLIST_FOREACH(nodelist_get_list(), node_t
*, node
,
2403 if (node_allows_single_hop_exits(node
)) {
2404 smartlist_add(excludednodes
, node
);
2408 if ((r
= routerlist_find_my_routerinfo()))
2409 routerlist_add_node_and_family(excludednodes
, r
);
2411 router_add_running_nodes_to_smartlist(sl
, allow_invalid
,
2412 need_uptime
, need_capacity
,
2413 need_guard
, need_desc
);
2414 smartlist_subtract(sl
,excludednodes
);
2415 if (excludedsmartlist
)
2416 smartlist_subtract(sl
,excludedsmartlist
);
2418 routerset_subtract_nodes(sl
,excludedset
);
2420 // Always weight by bandwidth
2421 choice
= node_sl_choose_by_bandwidth(sl
, rule
);
2424 if (!choice
&& (need_uptime
|| need_capacity
|| need_guard
)) {
2425 /* try once more -- recurse but with fewer restrictions. */
2427 "We couldn't find any live%s%s%s routers; falling back "
2428 "to list of all routers.",
2429 need_capacity
?", fast":"",
2430 need_uptime
?", stable":"",
2431 need_guard
?", guard":"");
2432 flags
&= ~ (CRN_NEED_UPTIME
|CRN_NEED_CAPACITY
|CRN_NEED_GUARD
);
2433 choice
= router_choose_random_node(
2434 excludedsmartlist
, excludedset
, flags
);
2436 smartlist_free(excludednodes
);
2439 "No available nodes when trying to choose node. Failing.");
2444 /** Helper: given an extended nickname in <b>hexdigest</b> try to decode it.
2445 * Return 0 on success, -1 on failure. Store the result into the
2446 * DIGEST_LEN-byte buffer at <b>digest_out</b>, the single character at
2447 * <b>nickname_qualifier_char_out</b>, and the MAXNICKNAME_LEN+1-byte buffer
2448 * at <b>nickname_out</b>.
2450 * The recognized format is:
2451 * HexName = Dollar? HexDigest NamePart?
2453 * HexDigest = HexChar*20
2454 * HexChar = 'a'..'f' | 'A'..'F' | '0'..'9'
2455 * NamePart = QualChar Name
2456 * QualChar = '=' | '~'
2457 * Name = NameChar*(1..MAX_NICKNAME_LEN)
2458 * NameChar = Any ASCII alphanumeric character
2461 hex_digest_nickname_decode(const char *hexdigest
,
2463 char *nickname_qualifier_char_out
,
2468 tor_assert(hexdigest
);
2469 if (hexdigest
[0] == '$')
2472 len
= strlen(hexdigest
);
2473 if (len
< HEX_DIGEST_LEN
) {
2475 } else if (len
> HEX_DIGEST_LEN
&& (hexdigest
[HEX_DIGEST_LEN
] == '=' ||
2476 hexdigest
[HEX_DIGEST_LEN
] == '~') &&
2477 len
<= HEX_DIGEST_LEN
+1+MAX_NICKNAME_LEN
) {
2478 *nickname_qualifier_char_out
= hexdigest
[HEX_DIGEST_LEN
];
2479 strlcpy(nickname_out
, hexdigest
+HEX_DIGEST_LEN
+1 , MAX_NICKNAME_LEN
+1);
2480 } else if (len
== HEX_DIGEST_LEN
) {
2486 if (base16_decode(digest_out
, DIGEST_LEN
, hexdigest
, HEX_DIGEST_LEN
)<0)
2491 /** Helper: Return true iff the <b>identity_digest</b> and <b>nickname</b>
2492 * combination of a router, encoded in hexadecimal, matches <b>hexdigest</b>
2493 * (which is optionally prefixed with a single dollar sign). Return false if
2494 * <b>hexdigest</b> is malformed, or it doesn't match. */
2496 hex_digest_nickname_matches(const char *hexdigest
, const char *identity_digest
,
2497 const char *nickname
, int is_named
)
2499 char digest
[DIGEST_LEN
];
2501 char nn_buf
[MAX_NICKNAME_LEN
+1];
2503 if (hex_digest_nickname_decode(hexdigest
, digest
, &nn_char
, nn_buf
) == -1)
2506 if (nn_char
== '=' || nn_char
== '~') {
2509 if (strcasecmp(nn_buf
, nickname
))
2511 if (nn_char
== '=' && !is_named
)
2515 return tor_memeq(digest
, identity_digest
, DIGEST_LEN
);
2518 /** Return true iff <b>router</b> is listed as named in the current
2521 router_is_named(const routerinfo_t
*router
)
2523 const char *digest
=
2524 networkstatus_get_router_digest_by_nickname(router
->nickname
);
2527 tor_memeq(digest
, router
->cache_info
.identity_digest
, DIGEST_LEN
));
2530 /** Return true iff <b>digest</b> is the digest of the identity key of a
2531 * trusted directory matching at least one bit of <b>type</b>. If <b>type</b>
2532 * is zero, any authority is okay. */
2534 router_digest_is_trusted_dir_type(const char *digest
, dirinfo_type_t type
)
2536 if (!trusted_dir_servers
)
2538 if (authdir_mode(get_options()) && router_digest_is_me(digest
))
2540 SMARTLIST_FOREACH(trusted_dir_servers
, dir_server_t
*, ent
,
2541 if (tor_memeq(digest
, ent
->digest
, DIGEST_LEN
)) {
2542 return (!type
) || ((type
& ent
->type
) != 0);
2547 /** Return true iff <b>addr</b> is the address of one of our trusted
2548 * directory authorities. */
2550 router_addr_is_trusted_dir(uint32_t addr
)
2552 if (!trusted_dir_servers
)
2554 SMARTLIST_FOREACH(trusted_dir_servers
, dir_server_t
*, ent
,
2555 if (ent
->addr
== addr
)
2561 /** If hexdigest is correctly formed, base16_decode it into
2562 * digest, which must have DIGEST_LEN space in it.
2563 * Return 0 on success, -1 on failure.
2566 hexdigest_to_digest(const char *hexdigest
, char *digest
)
2568 if (hexdigest
[0]=='$')
2570 if (strlen(hexdigest
) < HEX_DIGEST_LEN
||
2571 base16_decode(digest
,DIGEST_LEN
,hexdigest
,HEX_DIGEST_LEN
) < 0)
2576 /** As router_get_by_id_digest,but return a pointer that you're allowed to
2579 router_get_mutable_by_digest(const char *digest
)
2583 if (!routerlist
) return NULL
;
2585 // routerlist_assert_ok(routerlist);
2587 return rimap_get(routerlist
->identity_map
, digest
);
2590 /** Return the router in our routerlist whose 20-byte key digest
2591 * is <b>digest</b>. Return NULL if no such router is known. */
2592 const routerinfo_t
*
2593 router_get_by_id_digest(const char *digest
)
2595 return router_get_mutable_by_digest(digest
);
2598 /** Return the router in our routerlist whose 20-byte descriptor
2599 * is <b>digest</b>. Return NULL if no such router is known. */
2600 signed_descriptor_t
*
2601 router_get_by_descriptor_digest(const char *digest
)
2605 if (!routerlist
) return NULL
;
2607 return sdmap_get(routerlist
->desc_digest_map
, digest
);
2610 /** Return the signed descriptor for the router in our routerlist whose
2611 * 20-byte extra-info digest is <b>digest</b>. Return NULL if no such router
2613 signed_descriptor_t
*
2614 router_get_by_extrainfo_digest(const char *digest
)
2618 if (!routerlist
) return NULL
;
2620 return sdmap_get(routerlist
->desc_by_eid_map
, digest
);
2623 /** Return the signed descriptor for the extrainfo_t in our routerlist whose
2624 * extra-info-digest is <b>digest</b>. Return NULL if no such extra-info
2625 * document is known. */
2626 signed_descriptor_t
*
2627 extrainfo_get_by_descriptor_digest(const char *digest
)
2631 if (!routerlist
) return NULL
;
2632 ei
= eimap_get(routerlist
->extra_info_map
, digest
);
2633 return ei
? &ei
->cache_info
: NULL
;
2636 /** Return a pointer to the signed textual representation of a descriptor.
2637 * The returned string is not guaranteed to be NUL-terminated: the string's
2638 * length will be in desc-\>signed_descriptor_len.
2640 * If <b>with_annotations</b> is set, the returned string will include
2642 * (if any) preceding the descriptor. This will increase the length of the
2643 * string by desc-\>annotations_len.
2645 * The caller must not free the string returned.
2648 signed_descriptor_get_body_impl(const signed_descriptor_t
*desc
,
2649 int with_annotations
)
2651 const char *r
= NULL
;
2652 size_t len
= desc
->signed_descriptor_len
;
2653 off_t offset
= desc
->saved_offset
;
2654 if (with_annotations
)
2655 len
+= desc
->annotations_len
;
2657 offset
+= desc
->annotations_len
;
2659 tor_assert(len
> 32);
2660 if (desc
->saved_location
== SAVED_IN_CACHE
&& routerlist
) {
2661 desc_store_t
*store
= desc_get_store(router_get_routerlist(), desc
);
2662 if (store
&& store
->mmap
) {
2663 tor_assert(desc
->saved_offset
+ len
<= store
->mmap
->size
);
2664 r
= store
->mmap
->data
+ offset
;
2666 log_err(LD_DIR
, "We couldn't read a descriptor that is supposedly "
2667 "mmaped in our cache. Is another process running in our data "
2668 "directory? Exiting.");
2672 if (!r
) /* no mmap, or not in cache. */
2673 r
= desc
->signed_descriptor_body
+
2674 (with_annotations
? 0 : desc
->annotations_len
);
2677 if (!with_annotations
) {
2678 if (fast_memcmp("router ", r
, 7) && fast_memcmp("extra-info ", r
, 11)) {
2679 char *cp
= tor_strndup(r
, 64);
2680 log_err(LD_DIR
, "descriptor at %p begins with unexpected string %s. "
2681 "Is another process running in our data directory? Exiting.",
2690 /** Return a pointer to the signed textual representation of a descriptor.
2691 * The returned string is not guaranteed to be NUL-terminated: the string's
2692 * length will be in desc-\>signed_descriptor_len.
2694 * The caller must not free the string returned.
2697 signed_descriptor_get_body(const signed_descriptor_t
*desc
)
2699 return signed_descriptor_get_body_impl(desc
, 0);
2702 /** As signed_descriptor_get_body(), but points to the beginning of the
2703 * annotations section rather than the beginning of the descriptor. */
2705 signed_descriptor_get_annotations(const signed_descriptor_t
*desc
)
2707 return signed_descriptor_get_body_impl(desc
, 1);
2710 /** Return the current list of all known routers. */
2712 router_get_routerlist(void)
2714 if (PREDICT_UNLIKELY(!routerlist
)) {
2715 routerlist
= tor_malloc_zero(sizeof(routerlist_t
));
2716 routerlist
->routers
= smartlist_new();
2717 routerlist
->old_routers
= smartlist_new();
2718 routerlist
->identity_map
= rimap_new();
2719 routerlist
->desc_digest_map
= sdmap_new();
2720 routerlist
->desc_by_eid_map
= sdmap_new();
2721 routerlist
->extra_info_map
= eimap_new();
2723 routerlist
->desc_store
.fname_base
= "cached-descriptors";
2724 routerlist
->extrainfo_store
.fname_base
= "cached-extrainfo";
2726 routerlist
->desc_store
.type
= ROUTER_STORE
;
2727 routerlist
->extrainfo_store
.type
= EXTRAINFO_STORE
;
2729 routerlist
->desc_store
.description
= "router descriptors";
2730 routerlist
->extrainfo_store
.description
= "extra-info documents";
2735 /** Free all storage held by <b>router</b>. */
2737 routerinfo_free(routerinfo_t
*router
)
2742 tor_free(router
->cache_info
.signed_descriptor_body
);
2743 tor_free(router
->nickname
);
2744 tor_free(router
->platform
);
2745 tor_free(router
->contact_info
);
2746 if (router
->onion_pkey
)
2747 crypto_pk_free(router
->onion_pkey
);
2748 tor_free(router
->onion_curve25519_pkey
);
2749 if (router
->identity_pkey
)
2750 crypto_pk_free(router
->identity_pkey
);
2751 if (router
->declared_family
) {
2752 SMARTLIST_FOREACH(router
->declared_family
, char *, s
, tor_free(s
));
2753 smartlist_free(router
->declared_family
);
2755 addr_policy_list_free(router
->exit_policy
);
2756 short_policy_free(router
->ipv6_exit_policy
);
2758 memset(router
, 77, sizeof(routerinfo_t
));
2763 /** Release all storage held by <b>extrainfo</b> */
2765 extrainfo_free(extrainfo_t
*extrainfo
)
2769 tor_free(extrainfo
->cache_info
.signed_descriptor_body
);
2770 tor_free(extrainfo
->pending_sig
);
2772 memset(extrainfo
, 88, sizeof(extrainfo_t
)); /* debug bad memory usage */
2773 tor_free(extrainfo
);
2776 /** Release storage held by <b>sd</b>. */
2778 signed_descriptor_free(signed_descriptor_t
*sd
)
2783 tor_free(sd
->signed_descriptor_body
);
2785 memset(sd
, 99, sizeof(signed_descriptor_t
)); /* Debug bad mem usage */
2789 /** Extract a signed_descriptor_t from a general routerinfo, and free the
2792 static signed_descriptor_t
*
2793 signed_descriptor_from_routerinfo(routerinfo_t
*ri
)
2795 signed_descriptor_t
*sd
;
2796 tor_assert(ri
->purpose
== ROUTER_PURPOSE_GENERAL
);
2797 sd
= tor_malloc_zero(sizeof(signed_descriptor_t
));
2798 memcpy(sd
, &(ri
->cache_info
), sizeof(signed_descriptor_t
));
2799 sd
->routerlist_index
= -1;
2800 ri
->cache_info
.signed_descriptor_body
= NULL
;
2801 routerinfo_free(ri
);
2805 /** Helper: free the storage held by the extrainfo_t in <b>e</b>. */
2807 extrainfo_free_(void *e
)
2812 /** Free all storage held by a routerlist <b>rl</b>. */
2814 routerlist_free(routerlist_t
*rl
)
2818 rimap_free(rl
->identity_map
, NULL
);
2819 sdmap_free(rl
->desc_digest_map
, NULL
);
2820 sdmap_free(rl
->desc_by_eid_map
, NULL
);
2821 eimap_free(rl
->extra_info_map
, extrainfo_free_
);
2822 SMARTLIST_FOREACH(rl
->routers
, routerinfo_t
*, r
,
2823 routerinfo_free(r
));
2824 SMARTLIST_FOREACH(rl
->old_routers
, signed_descriptor_t
*, sd
,
2825 signed_descriptor_free(sd
));
2826 smartlist_free(rl
->routers
);
2827 smartlist_free(rl
->old_routers
);
2828 if (rl
->desc_store
.mmap
) {
2829 int res
= tor_munmap_file(routerlist
->desc_store
.mmap
);
2831 log_warn(LD_FS
, "Failed to munmap routerlist->desc_store.mmap");
2834 if (rl
->extrainfo_store
.mmap
) {
2835 int res
= tor_munmap_file(routerlist
->extrainfo_store
.mmap
);
2837 log_warn(LD_FS
, "Failed to munmap routerlist->extrainfo_store.mmap");
2842 router_dir_info_changed();
2845 /** Log information about how much memory is being used for routerlist,
2846 * at log level <b>severity</b>. */
2848 dump_routerlist_mem_usage(int severity
)
2850 uint64_t livedescs
= 0;
2851 uint64_t olddescs
= 0;
2854 SMARTLIST_FOREACH(routerlist
->routers
, routerinfo_t
*, r
,
2855 livedescs
+= r
->cache_info
.signed_descriptor_len
);
2856 SMARTLIST_FOREACH(routerlist
->old_routers
, signed_descriptor_t
*, sd
,
2857 olddescs
+= sd
->signed_descriptor_len
);
2859 tor_log(severity
, LD_DIR
,
2860 "In %d live descriptors: "U64_FORMAT
" bytes. "
2861 "In %d old descriptors: "U64_FORMAT
" bytes.",
2862 smartlist_len(routerlist
->routers
), U64_PRINTF_ARG(livedescs
),
2863 smartlist_len(routerlist
->old_routers
), U64_PRINTF_ARG(olddescs
));
2866 /** Debugging helper: If <b>idx</b> is nonnegative, assert that <b>ri</b> is
2867 * in <b>sl</b> at position <b>idx</b>. Otherwise, search <b>sl</b> for
2868 * <b>ri</b>. Return the index of <b>ri</b> in <b>sl</b>, or -1 if <b>ri</b>
2869 * is not in <b>sl</b>. */
2871 routerlist_find_elt_(smartlist_t
*sl
, void *ri
, int idx
)
2875 SMARTLIST_FOREACH(sl
, routerinfo_t
*, r
,
2881 tor_assert(idx
< smartlist_len(sl
));
2882 tor_assert(smartlist_get(sl
, idx
) == ri
);
2887 /** Insert an item <b>ri</b> into the routerlist <b>rl</b>, updating indices
2888 * as needed. There must be no previous member of <b>rl</b> with the same
2889 * identity digest as <b>ri</b>: If there is, call routerlist_replace
2893 routerlist_insert(routerlist_t
*rl
, routerinfo_t
*ri
)
2895 routerinfo_t
*ri_old
;
2896 signed_descriptor_t
*sd_old
;
2898 const routerinfo_t
*ri_generated
= router_get_my_routerinfo();
2899 tor_assert(ri_generated
!= ri
);
2901 tor_assert(ri
->cache_info
.routerlist_index
== -1);
2903 ri_old
= rimap_set(rl
->identity_map
, ri
->cache_info
.identity_digest
, ri
);
2904 tor_assert(!ri_old
);
2906 sd_old
= sdmap_set(rl
->desc_digest_map
,
2907 ri
->cache_info
.signed_descriptor_digest
,
2910 int idx
= sd_old
->routerlist_index
;
2911 sd_old
->routerlist_index
= -1;
2912 smartlist_del(rl
->old_routers
, idx
);
2913 if (idx
< smartlist_len(rl
->old_routers
)) {
2914 signed_descriptor_t
*d
= smartlist_get(rl
->old_routers
, idx
);
2915 d
->routerlist_index
= idx
;
2917 rl
->desc_store
.bytes_dropped
+= sd_old
->signed_descriptor_len
;
2918 sdmap_remove(rl
->desc_by_eid_map
, sd_old
->extra_info_digest
);
2919 signed_descriptor_free(sd_old
);
2922 if (!tor_digest_is_zero(ri
->cache_info
.extra_info_digest
))
2923 sdmap_set(rl
->desc_by_eid_map
, ri
->cache_info
.extra_info_digest
,
2925 smartlist_add(rl
->routers
, ri
);
2926 ri
->cache_info
.routerlist_index
= smartlist_len(rl
->routers
) - 1;
2927 nodelist_set_routerinfo(ri
, NULL
);
2928 router_dir_info_changed();
2929 #ifdef DEBUG_ROUTERLIST
2930 routerlist_assert_ok(rl
);
2934 /** Adds the extrainfo_t <b>ei</b> to the routerlist <b>rl</b>, if there is a
2935 * corresponding router in rl-\>routers or rl-\>old_routers. Return true iff
2936 * we actually inserted <b>ei</b>. Free <b>ei</b> if it isn't inserted. */
2938 extrainfo_insert(routerlist_t
*rl
, extrainfo_t
*ei
)
2941 routerinfo_t
*ri
= rimap_get(rl
->identity_map
,
2942 ei
->cache_info
.identity_digest
);
2943 signed_descriptor_t
*sd
=
2944 sdmap_get(rl
->desc_by_eid_map
, ei
->cache_info
.signed_descriptor_digest
);
2945 extrainfo_t
*ei_tmp
;
2948 extrainfo_t
*ei_generated
= router_get_my_extrainfo();
2949 tor_assert(ei_generated
!= ei
);
2953 /* This router is unknown; we can't even verify the signature. Give up.*/
2956 if (routerinfo_incompatible_with_extrainfo(ri
, ei
, sd
, NULL
)) {
2960 /* Okay, if we make it here, we definitely have a router corresponding to
2961 * this extrainfo. */
2963 ei_tmp
= eimap_set(rl
->extra_info_map
,
2964 ei
->cache_info
.signed_descriptor_digest
,
2968 rl
->extrainfo_store
.bytes_dropped
+=
2969 ei_tmp
->cache_info
.signed_descriptor_len
;
2970 extrainfo_free(ei_tmp
);
2977 #ifdef DEBUG_ROUTERLIST
2978 routerlist_assert_ok(rl
);
2983 #define should_cache_old_descriptors() \
2984 directory_caches_dir_info(get_options())
2986 /** If we're a directory cache and routerlist <b>rl</b> doesn't have
2987 * a copy of router <b>ri</b> yet, add it to the list of old (not
2988 * recommended but still served) descriptors. Else free it. */
2990 routerlist_insert_old(routerlist_t
*rl
, routerinfo_t
*ri
)
2993 const routerinfo_t
*ri_generated
= router_get_my_routerinfo();
2994 tor_assert(ri_generated
!= ri
);
2996 tor_assert(ri
->cache_info
.routerlist_index
== -1);
2998 if (should_cache_old_descriptors() &&
2999 ri
->purpose
== ROUTER_PURPOSE_GENERAL
&&
3000 !sdmap_get(rl
->desc_digest_map
,
3001 ri
->cache_info
.signed_descriptor_digest
)) {
3002 signed_descriptor_t
*sd
= signed_descriptor_from_routerinfo(ri
);
3003 sdmap_set(rl
->desc_digest_map
, sd
->signed_descriptor_digest
, sd
);
3004 smartlist_add(rl
->old_routers
, sd
);
3005 sd
->routerlist_index
= smartlist_len(rl
->old_routers
)-1;
3006 if (!tor_digest_is_zero(sd
->extra_info_digest
))
3007 sdmap_set(rl
->desc_by_eid_map
, sd
->extra_info_digest
, sd
);
3009 routerinfo_free(ri
);
3011 #ifdef DEBUG_ROUTERLIST
3012 routerlist_assert_ok(rl
);
3016 /** Remove an item <b>ri</b> from the routerlist <b>rl</b>, updating indices
3017 * as needed. If <b>idx</b> is nonnegative and smartlist_get(rl->routers,
3018 * idx) == ri, we don't need to do a linear search over the list to decide
3019 * which to remove. We fill the gap in rl->routers with a later element in
3020 * the list, if any exists. <b>ri</b> is freed.
3022 * If <b>make_old</b> is true, instead of deleting the router, we try adding
3023 * it to rl->old_routers. */
3025 routerlist_remove(routerlist_t
*rl
, routerinfo_t
*ri
, int make_old
, time_t now
)
3027 routerinfo_t
*ri_tmp
;
3028 extrainfo_t
*ei_tmp
;
3029 int idx
= ri
->cache_info
.routerlist_index
;
3030 tor_assert(0 <= idx
&& idx
< smartlist_len(rl
->routers
));
3031 tor_assert(smartlist_get(rl
->routers
, idx
) == ri
);
3033 nodelist_remove_routerinfo(ri
);
3035 /* make sure the rephist module knows that it's not running */
3036 rep_hist_note_router_unreachable(ri
->cache_info
.identity_digest
, now
);
3038 ri
->cache_info
.routerlist_index
= -1;
3039 smartlist_del(rl
->routers
, idx
);
3040 if (idx
< smartlist_len(rl
->routers
)) {
3041 routerinfo_t
*r
= smartlist_get(rl
->routers
, idx
);
3042 r
->cache_info
.routerlist_index
= idx
;
3045 ri_tmp
= rimap_remove(rl
->identity_map
, ri
->cache_info
.identity_digest
);
3046 router_dir_info_changed();
3047 tor_assert(ri_tmp
== ri
);
3049 if (make_old
&& should_cache_old_descriptors() &&
3050 ri
->purpose
== ROUTER_PURPOSE_GENERAL
) {
3051 signed_descriptor_t
*sd
;
3052 sd
= signed_descriptor_from_routerinfo(ri
);
3053 smartlist_add(rl
->old_routers
, sd
);
3054 sd
->routerlist_index
= smartlist_len(rl
->old_routers
)-1;
3055 sdmap_set(rl
->desc_digest_map
, sd
->signed_descriptor_digest
, sd
);
3056 if (!tor_digest_is_zero(sd
->extra_info_digest
))
3057 sdmap_set(rl
->desc_by_eid_map
, sd
->extra_info_digest
, sd
);
3059 signed_descriptor_t
*sd_tmp
;
3060 sd_tmp
= sdmap_remove(rl
->desc_digest_map
,
3061 ri
->cache_info
.signed_descriptor_digest
);
3062 tor_assert(sd_tmp
== &(ri
->cache_info
));
3063 rl
->desc_store
.bytes_dropped
+= ri
->cache_info
.signed_descriptor_len
;
3064 ei_tmp
= eimap_remove(rl
->extra_info_map
,
3065 ri
->cache_info
.extra_info_digest
);
3067 rl
->extrainfo_store
.bytes_dropped
+=
3068 ei_tmp
->cache_info
.signed_descriptor_len
;
3069 extrainfo_free(ei_tmp
);
3071 if (!tor_digest_is_zero(ri
->cache_info
.extra_info_digest
))
3072 sdmap_remove(rl
->desc_by_eid_map
, ri
->cache_info
.extra_info_digest
);
3073 routerinfo_free(ri
);
3075 #ifdef DEBUG_ROUTERLIST
3076 routerlist_assert_ok(rl
);
3080 /** Remove a signed_descriptor_t <b>sd</b> from <b>rl</b>-\>old_routers, and
3081 * adjust <b>rl</b> as appropriate. <b>idx</b> is -1, or the index of
3084 routerlist_remove_old(routerlist_t
*rl
, signed_descriptor_t
*sd
, int idx
)
3086 signed_descriptor_t
*sd_tmp
;
3087 extrainfo_t
*ei_tmp
;
3088 desc_store_t
*store
;
3090 idx
= sd
->routerlist_index
;
3092 tor_assert(0 <= idx
&& idx
< smartlist_len(rl
->old_routers
));
3093 /* XXXX edmanm's bridge relay triggered the following assert while
3094 * running 0.2.0.12-alpha. If anybody triggers this again, see if we
3095 * can get a backtrace. */
3096 tor_assert(smartlist_get(rl
->old_routers
, idx
) == sd
);
3097 tor_assert(idx
== sd
->routerlist_index
);
3099 sd
->routerlist_index
= -1;
3100 smartlist_del(rl
->old_routers
, idx
);
3101 if (idx
< smartlist_len(rl
->old_routers
)) {
3102 signed_descriptor_t
*d
= smartlist_get(rl
->old_routers
, idx
);
3103 d
->routerlist_index
= idx
;
3105 sd_tmp
= sdmap_remove(rl
->desc_digest_map
,
3106 sd
->signed_descriptor_digest
);
3107 tor_assert(sd_tmp
== sd
);
3108 store
= desc_get_store(rl
, sd
);
3110 store
->bytes_dropped
+= sd
->signed_descriptor_len
;
3112 ei_tmp
= eimap_remove(rl
->extra_info_map
,
3113 sd
->extra_info_digest
);
3115 rl
->extrainfo_store
.bytes_dropped
+=
3116 ei_tmp
->cache_info
.signed_descriptor_len
;
3117 extrainfo_free(ei_tmp
);
3119 if (!tor_digest_is_zero(sd
->extra_info_digest
))
3120 sdmap_remove(rl
->desc_by_eid_map
, sd
->extra_info_digest
);
3122 signed_descriptor_free(sd
);
3123 #ifdef DEBUG_ROUTERLIST
3124 routerlist_assert_ok(rl
);
3128 /** Remove <b>ri_old</b> from the routerlist <b>rl</b>, and replace it with
3129 * <b>ri_new</b>, updating all index info. If <b>idx</b> is nonnegative and
3130 * smartlist_get(rl->routers, idx) == ri, we don't need to do a linear
3131 * search over the list to decide which to remove. We put ri_new in the same
3132 * index as ri_old, if possible. ri is freed as appropriate.
3134 * If should_cache_descriptors() is true, instead of deleting the router,
3135 * we add it to rl->old_routers. */
3137 routerlist_replace(routerlist_t
*rl
, routerinfo_t
*ri_old
,
3138 routerinfo_t
*ri_new
)
3141 int same_descriptors
;
3143 routerinfo_t
*ri_tmp
;
3144 extrainfo_t
*ei_tmp
;
3146 const routerinfo_t
*ri_generated
= router_get_my_routerinfo();
3147 tor_assert(ri_generated
!= ri_new
);
3149 tor_assert(ri_old
!= ri_new
);
3150 tor_assert(ri_new
->cache_info
.routerlist_index
== -1);
3152 idx
= ri_old
->cache_info
.routerlist_index
;
3153 tor_assert(0 <= idx
&& idx
< smartlist_len(rl
->routers
));
3154 tor_assert(smartlist_get(rl
->routers
, idx
) == ri_old
);
3157 routerinfo_t
*ri_old_tmp
=NULL
;
3158 nodelist_set_routerinfo(ri_new
, &ri_old_tmp
);
3159 tor_assert(ri_old
== ri_old_tmp
);
3162 router_dir_info_changed();
3164 smartlist_set(rl
->routers
, idx
, ri_new
);
3165 ri_old
->cache_info
.routerlist_index
= -1;
3166 ri_new
->cache_info
.routerlist_index
= idx
;
3167 /* Check that ri_old is not in rl->routers anymore: */
3168 tor_assert( routerlist_find_elt_(rl
->routers
, ri_old
, -1) == -1 );
3170 log_warn(LD_BUG
, "Appending entry from routerlist_replace.");
3171 routerlist_insert(rl
, ri_new
);
3174 if (tor_memneq(ri_old
->cache_info
.identity_digest
,
3175 ri_new
->cache_info
.identity_digest
, DIGEST_LEN
)) {
3176 /* digests don't match; digestmap_set won't replace */
3177 rimap_remove(rl
->identity_map
, ri_old
->cache_info
.identity_digest
);
3179 ri_tmp
= rimap_set(rl
->identity_map
,
3180 ri_new
->cache_info
.identity_digest
, ri_new
);
3181 tor_assert(!ri_tmp
|| ri_tmp
== ri_old
);
3182 sdmap_set(rl
->desc_digest_map
,
3183 ri_new
->cache_info
.signed_descriptor_digest
,
3184 &(ri_new
->cache_info
));
3186 if (!tor_digest_is_zero(ri_new
->cache_info
.extra_info_digest
)) {
3187 sdmap_set(rl
->desc_by_eid_map
, ri_new
->cache_info
.extra_info_digest
,
3188 &ri_new
->cache_info
);
3191 same_descriptors
= tor_memeq(ri_old
->cache_info
.signed_descriptor_digest
,
3192 ri_new
->cache_info
.signed_descriptor_digest
,
3195 if (should_cache_old_descriptors() &&
3196 ri_old
->purpose
== ROUTER_PURPOSE_GENERAL
&&
3197 !same_descriptors
) {
3198 /* ri_old is going to become a signed_descriptor_t and go into
3200 signed_descriptor_t
*sd
= signed_descriptor_from_routerinfo(ri_old
);
3201 smartlist_add(rl
->old_routers
, sd
);
3202 sd
->routerlist_index
= smartlist_len(rl
->old_routers
)-1;
3203 sdmap_set(rl
->desc_digest_map
, sd
->signed_descriptor_digest
, sd
);
3204 if (!tor_digest_is_zero(sd
->extra_info_digest
))
3205 sdmap_set(rl
->desc_by_eid_map
, sd
->extra_info_digest
, sd
);
3207 /* We're dropping ri_old. */
3208 if (!same_descriptors
) {
3209 /* digests don't match; The sdmap_set above didn't replace */
3210 sdmap_remove(rl
->desc_digest_map
,
3211 ri_old
->cache_info
.signed_descriptor_digest
);
3213 if (tor_memneq(ri_old
->cache_info
.extra_info_digest
,
3214 ri_new
->cache_info
.extra_info_digest
, DIGEST_LEN
)) {
3215 ei_tmp
= eimap_remove(rl
->extra_info_map
,
3216 ri_old
->cache_info
.extra_info_digest
);
3218 rl
->extrainfo_store
.bytes_dropped
+=
3219 ei_tmp
->cache_info
.signed_descriptor_len
;
3220 extrainfo_free(ei_tmp
);
3224 if (!tor_digest_is_zero(ri_old
->cache_info
.extra_info_digest
)) {
3225 sdmap_remove(rl
->desc_by_eid_map
,
3226 ri_old
->cache_info
.extra_info_digest
);
3229 rl
->desc_store
.bytes_dropped
+= ri_old
->cache_info
.signed_descriptor_len
;
3230 routerinfo_free(ri_old
);
3232 #ifdef DEBUG_ROUTERLIST
3233 routerlist_assert_ok(rl
);
3237 /** Extract the descriptor <b>sd</b> from old_routerlist, and re-parse
3238 * it as a fresh routerinfo_t. */
3239 static routerinfo_t
*
3240 routerlist_reparse_old(routerlist_t
*rl
, signed_descriptor_t
*sd
)
3245 body
= signed_descriptor_get_annotations(sd
);
3247 ri
= router_parse_entry_from_string(body
,
3248 body
+sd
->signed_descriptor_len
+sd
->annotations_len
,
3252 memcpy(&ri
->cache_info
, sd
, sizeof(signed_descriptor_t
));
3253 sd
->signed_descriptor_body
= NULL
; /* Steal reference. */
3254 ri
->cache_info
.routerlist_index
= -1;
3256 routerlist_remove_old(rl
, sd
, -1);
3261 /** Free all memory held by the routerlist module. */
3263 routerlist_free_all(void)
3265 routerlist_free(routerlist
);
3267 if (warned_nicknames
) {
3268 SMARTLIST_FOREACH(warned_nicknames
, char *, cp
, tor_free(cp
));
3269 smartlist_free(warned_nicknames
);
3270 warned_nicknames
= NULL
;
3272 clear_dir_servers();
3273 smartlist_free(trusted_dir_servers
);
3274 smartlist_free(fallback_dir_servers
);
3275 trusted_dir_servers
= fallback_dir_servers
= NULL
;
3276 if (trusted_dir_certs
) {
3277 digestmap_free(trusted_dir_certs
, cert_list_free_
);
3278 trusted_dir_certs
= NULL
;
3282 /** Forget that we have issued any router-related warnings, so that we'll
3283 * warn again if we see the same errors. */
3285 routerlist_reset_warnings(void)
3287 if (!warned_nicknames
)
3288 warned_nicknames
= smartlist_new();
3289 SMARTLIST_FOREACH(warned_nicknames
, char *, cp
, tor_free(cp
));
3290 smartlist_clear(warned_nicknames
); /* now the list is empty. */
3292 networkstatus_reset_warnings();
3295 /** Add <b>router</b> to the routerlist, if we don't already have it. Replace
3296 * older entries (if any) with the same key. Note: Callers should not hold
3297 * their pointers to <b>router</b> if this function fails; <b>router</b>
3298 * will either be inserted into the routerlist or freed. Similarly, even
3299 * if this call succeeds, they should not hold their pointers to
3300 * <b>router</b> after subsequent calls with other routerinfo's -- they
3301 * might cause the original routerinfo to get freed.
3303 * Returns the status for the operation. Might set *<b>msg</b> if it wants
3304 * the poster of the router to know something.
3306 * If <b>from_cache</b>, this descriptor came from our disk cache. If
3307 * <b>from_fetch</b>, we received it in response to a request we made.
3308 * (If both are false, that means it was uploaded to us as an auth dir
3309 * server or via the controller.)
3311 * This function should be called *after*
3312 * routers_update_status_from_consensus_networkstatus; subsequently, you
3313 * should call router_rebuild_store and routerlist_descriptors_added.
3316 router_add_to_routerlist(routerinfo_t
*router
, const char **msg
,
3317 int from_cache
, int from_fetch
)
3319 const char *id_digest
;
3320 const or_options_t
*options
= get_options();
3321 int authdir
= authdir_mode_handles_descs(options
, router
->purpose
);
3322 int authdir_believes_valid
= 0;
3323 routerinfo_t
*old_router
;
3324 networkstatus_t
*consensus
=
3325 networkstatus_get_latest_consensus_by_flavor(FLAV_NS
);
3326 int in_consensus
= 0;
3331 router_get_routerlist();
3333 id_digest
= router
->cache_info
.identity_digest
;
3335 old_router
= router_get_mutable_by_digest(id_digest
);
3337 /* Make sure that we haven't already got this exact descriptor. */
3338 if (sdmap_get(routerlist
->desc_digest_map
,
3339 router
->cache_info
.signed_descriptor_digest
)) {
3340 /* If we have this descriptor already and the new descriptor is a bridge
3341 * descriptor, replace it. If we had a bridge descriptor before and the
3342 * new one is not a bridge descriptor, don't replace it. */
3344 /* Only members of routerlist->identity_map can be bridges; we don't
3345 * put bridges in old_routers. */
3346 const int was_bridge
= old_router
&&
3347 old_router
->purpose
== ROUTER_PURPOSE_BRIDGE
;
3349 if (routerinfo_is_a_configured_bridge(router
) &&
3350 router
->purpose
== ROUTER_PURPOSE_BRIDGE
&&
3352 log_info(LD_DIR
, "Replacing non-bridge descriptor with bridge "
3353 "descriptor for router %s",
3354 router_describe(router
));
3357 "Dropping descriptor that we already have for router %s",
3358 router_describe(router
));
3359 *msg
= "Router descriptor was not new.";
3360 routerinfo_free(router
);
3361 return ROUTER_WAS_NOT_NEW
;
3366 if (authdir_wants_to_reject_router(router
, msg
,
3367 !from_cache
&& !from_fetch
,
3368 &authdir_believes_valid
)) {
3370 routerinfo_free(router
);
3371 return ROUTER_AUTHDIR_REJECTS
;
3373 } else if (from_fetch
) {
3374 /* Only check the descriptor digest against the network statuses when
3375 * we are receiving in response to a fetch. */
3377 if (!signed_desc_digest_is_recognized(&router
->cache_info
) &&
3378 !routerinfo_is_a_configured_bridge(router
)) {
3379 /* We asked for it, so some networkstatus must have listed it when we
3380 * did. Save it if we're a cache in case somebody else asks for it. */
3382 "Received a no-longer-recognized descriptor for router %s",
3383 router_describe(router
));
3384 *msg
= "Router descriptor is not referenced by any network-status.";
3386 /* Only journal this desc if we'll be serving it. */
3387 if (!from_cache
&& should_cache_old_descriptors())
3388 signed_desc_append_to_journal(&router
->cache_info
,
3389 &routerlist
->desc_store
);
3390 routerlist_insert_old(routerlist
, router
);
3391 return ROUTER_NOT_IN_CONSENSUS_OR_NETWORKSTATUS
;
3395 /* We no longer need a router with this descriptor digest. */
3397 routerstatus_t
*rs
= networkstatus_vote_find_mutable_entry(
3398 consensus
, id_digest
);
3399 if (rs
&& tor_memeq(rs
->descriptor_digest
,
3400 router
->cache_info
.signed_descriptor_digest
,
3406 if (router
->purpose
== ROUTER_PURPOSE_GENERAL
&&
3407 consensus
&& !in_consensus
&& !authdir
) {
3408 /* If it's a general router not listed in the consensus, then don't
3409 * consider replacing the latest router with it. */
3410 if (!from_cache
&& should_cache_old_descriptors())
3411 signed_desc_append_to_journal(&router
->cache_info
,
3412 &routerlist
->desc_store
);
3413 routerlist_insert_old(routerlist
, router
);
3414 *msg
= "Skipping router descriptor: not in consensus.";
3415 return ROUTER_NOT_IN_CONSENSUS
;
3418 /* If we're reading a bridge descriptor from our cache, and we don't
3419 * recognize it as one of our currently configured bridges, drop the
3420 * descriptor. Otherwise we could end up using it as one of our entry
3421 * guards even if it isn't in our Bridge config lines. */
3422 if (router
->purpose
== ROUTER_PURPOSE_BRIDGE
&& from_cache
&&
3423 !authdir_mode_bridge(options
) &&
3424 !routerinfo_is_a_configured_bridge(router
)) {
3425 log_info(LD_DIR
, "Dropping bridge descriptor for %s because we have "
3426 "no bridge configured at that address.",
3427 safe_str_client(router_describe(router
)));
3428 *msg
= "Router descriptor was not a configured bridge.";
3429 routerinfo_free(router
);
3430 return ROUTER_WAS_NOT_WANTED
;
3433 /* If we have a router with the same identity key, choose the newer one. */
3435 if (!in_consensus
&& (router
->cache_info
.published_on
<=
3436 old_router
->cache_info
.published_on
)) {
3437 /* Same key, but old. This one is not listed in the consensus. */
3438 log_debug(LD_DIR
, "Not-new descriptor for router %s",
3439 router_describe(router
));
3440 /* Only journal this desc if we'll be serving it. */
3441 if (!from_cache
&& should_cache_old_descriptors())
3442 signed_desc_append_to_journal(&router
->cache_info
,
3443 &routerlist
->desc_store
);
3444 routerlist_insert_old(routerlist
, router
);
3445 *msg
= "Router descriptor was not new.";
3446 return ROUTER_WAS_NOT_NEW
;
3448 /* Same key, and either new, or listed in the consensus. */
3449 log_debug(LD_DIR
, "Replacing entry for router %s",
3450 router_describe(router
));
3451 routerlist_replace(routerlist
, old_router
, router
);
3453 signed_desc_append_to_journal(&router
->cache_info
,
3454 &routerlist
->desc_store
);
3456 *msg
= authdir_believes_valid
? "Valid server updated" :
3457 ("Invalid server updated. (This dirserver is marking your "
3458 "server as unapproved.)");
3459 return ROUTER_ADDED_SUCCESSFULLY
;
3463 if (!in_consensus
&& from_cache
&&
3464 router
->cache_info
.published_on
< time(NULL
) - OLD_ROUTER_DESC_MAX_AGE
) {
3465 *msg
= "Router descriptor was really old.";
3466 routerinfo_free(router
);
3467 return ROUTER_WAS_NOT_NEW
;
3470 /* We haven't seen a router with this identity before. Add it to the end of
3472 routerlist_insert(routerlist
, router
);
3474 signed_desc_append_to_journal(&router
->cache_info
,
3475 &routerlist
->desc_store
);
3477 return ROUTER_ADDED_SUCCESSFULLY
;
3480 /** Insert <b>ei</b> into the routerlist, or free it. Other arguments are
3481 * as for router_add_to_routerlist(). Return ROUTER_ADDED_SUCCESSFULLY iff
3482 * we actually inserted it, ROUTER_BAD_EI otherwise.
3485 router_add_extrainfo_to_routerlist(extrainfo_t
*ei
, const char **msg
,
3486 int from_cache
, int from_fetch
)
3490 if (msg
) *msg
= NULL
;
3491 /*XXXX023 Do something with msg */
3493 inserted
= extrainfo_insert(router_get_routerlist(), ei
);
3495 if (inserted
&& !from_cache
)
3496 signed_desc_append_to_journal(&ei
->cache_info
,
3497 &routerlist
->extrainfo_store
);
3500 return ROUTER_ADDED_SUCCESSFULLY
;
3502 return ROUTER_BAD_EI
;
3505 /** Sorting helper: return <0, 0, or >0 depending on whether the
3506 * signed_descriptor_t* in *<b>a</b> has an identity digest preceding, equal
3507 * to, or later than that of *<b>b</b>. */
3509 compare_old_routers_by_identity_(const void **_a
, const void **_b
)
3512 const signed_descriptor_t
*r1
= *_a
, *r2
= *_b
;
3513 if ((i
= fast_memcmp(r1
->identity_digest
, r2
->identity_digest
, DIGEST_LEN
)))
3515 return (int)(r1
->published_on
- r2
->published_on
);
3518 /** Internal type used to represent how long an old descriptor was valid,
3519 * where it appeared in the list of old descriptors, and whether it's extra
3520 * old. Used only by routerlist_remove_old_cached_routers_with_id(). */
3521 struct duration_idx_t
{
3527 /** Sorting helper: compare two duration_idx_t by their duration. */
3529 compare_duration_idx_(const void *_d1
, const void *_d2
)
3531 const struct duration_idx_t
*d1
= _d1
;
3532 const struct duration_idx_t
*d2
= _d2
;
3533 return d1
->duration
- d2
->duration
;
3536 /** The range <b>lo</b> through <b>hi</b> inclusive of routerlist->old_routers
3537 * must contain routerinfo_t with the same identity and with publication time
3538 * in ascending order. Remove members from this range until there are no more
3539 * than max_descriptors_per_router() remaining. Start by removing the oldest
3540 * members from before <b>cutoff</b>, then remove members which were current
3541 * for the lowest amount of time. The order of members of old_routers at
3542 * indices <b>lo</b> or higher may be changed.
3545 routerlist_remove_old_cached_routers_with_id(time_t now
,
3546 time_t cutoff
, int lo
, int hi
,
3547 digestset_t
*retain
)
3550 unsigned n_extra
, n_rmv
= 0;
3551 struct duration_idx_t
*lifespans
;
3552 uint8_t *rmv
, *must_keep
;
3553 smartlist_t
*lst
= routerlist
->old_routers
;
3556 tor_assert(hi
< smartlist_len(lst
));
3557 tor_assert(lo
<= hi
);
3558 ident
= ((signed_descriptor_t
*)smartlist_get(lst
, lo
))->identity_digest
;
3559 for (i
= lo
+1; i
<= hi
; ++i
) {
3560 signed_descriptor_t
*r
= smartlist_get(lst
, i
);
3561 tor_assert(tor_memeq(ident
, r
->identity_digest
, DIGEST_LEN
));
3564 /* Check whether we need to do anything at all. */
3566 int mdpr
= directory_caches_dir_info(get_options()) ? 2 : 1;
3572 lifespans
= tor_malloc_zero(sizeof(struct duration_idx_t
)*n
);
3573 rmv
= tor_malloc_zero(sizeof(uint8_t)*n
);
3574 must_keep
= tor_malloc_zero(sizeof(uint8_t)*n
);
3575 /* Set lifespans to contain the lifespan and index of each server. */
3576 /* Set rmv[i-lo]=1 if we're going to remove a server for being too old. */
3577 for (i
= lo
; i
<= hi
; ++i
) {
3578 signed_descriptor_t
*r
= smartlist_get(lst
, i
);
3579 signed_descriptor_t
*r_next
;
3580 lifespans
[i
-lo
].idx
= i
;
3581 if (r
->last_listed_as_valid_until
>= now
||
3582 (retain
&& digestset_contains(retain
, r
->signed_descriptor_digest
))) {
3583 must_keep
[i
-lo
] = 1;
3586 r_next
= smartlist_get(lst
, i
+1);
3587 tor_assert(r
->published_on
<= r_next
->published_on
);
3588 lifespans
[i
-lo
].duration
= (int)(r_next
->published_on
- r
->published_on
);
3591 lifespans
[i
-lo
].duration
= INT_MAX
;
3593 if (!must_keep
[i
-lo
] && r
->published_on
< cutoff
&& n_rmv
< n_extra
) {
3595 lifespans
[i
-lo
].old
= 1;
3600 if (n_rmv
< n_extra
) {
3602 * We aren't removing enough servers for being old. Sort lifespans by
3603 * the duration of liveness, and remove the ones we're not already going to
3604 * remove based on how long they were alive.
3606 qsort(lifespans
, n
, sizeof(struct duration_idx_t
), compare_duration_idx_
);
3607 for (i
= 0; i
< n
&& n_rmv
< n_extra
; ++i
) {
3608 if (!must_keep
[lifespans
[i
].idx
-lo
] && !lifespans
[i
].old
) {
3609 rmv
[lifespans
[i
].idx
-lo
] = 1;
3618 routerlist_remove_old(routerlist
, smartlist_get(lst
, i
), i
);
3619 } while (--i
>= lo
);
3620 tor_free(must_keep
);
3622 tor_free(lifespans
);
3625 /** Deactivate any routers from the routerlist that are more than
3626 * ROUTER_MAX_AGE seconds old and not recommended by any networkstatuses;
3627 * remove old routers from the list of cached routers if we have too many.
3630 routerlist_remove_old_routers(void)
3633 const char *cur_id
= NULL
;
3634 time_t now
= time(NULL
);
3636 routerinfo_t
*router
;
3637 signed_descriptor_t
*sd
;
3638 digestset_t
*retain
;
3639 const networkstatus_t
*consensus
= networkstatus_get_latest_consensus();
3641 trusted_dirs_remove_old_certs();
3643 if (!routerlist
|| !consensus
)
3646 // routerlist_assert_ok(routerlist);
3648 /* We need to guess how many router descriptors we will wind up wanting to
3649 retain, so that we can be sure to allocate a large enough Bloom filter
3650 to hold the digest set. Overestimating is fine; underestimating is bad.
3653 /* We'll probably retain everything in the consensus. */
3654 int n_max_retain
= smartlist_len(consensus
->routerstatus_list
);
3655 retain
= digestset_new(n_max_retain
);
3658 cutoff
= now
- OLD_ROUTER_DESC_MAX_AGE
;
3659 /* Retain anything listed in the consensus. */
3661 SMARTLIST_FOREACH(consensus
->routerstatus_list
, routerstatus_t
*, rs
,
3662 if (rs
->published_on
>= cutoff
)
3663 digestset_add(retain
, rs
->descriptor_digest
));
3666 /* If we have a consensus, we should consider pruning current routers that
3667 * are too old and that nobody recommends. (If we don't have a consensus,
3668 * then we should get one before we decide to kill routers.) */
3671 cutoff
= now
- ROUTER_MAX_AGE
;
3672 /* Remove too-old unrecommended members of routerlist->routers. */
3673 for (i
= 0; i
< smartlist_len(routerlist
->routers
); ++i
) {
3674 router
= smartlist_get(routerlist
->routers
, i
);
3675 if (router
->cache_info
.published_on
<= cutoff
&&
3676 router
->cache_info
.last_listed_as_valid_until
< now
&&
3677 !digestset_contains(retain
,
3678 router
->cache_info
.signed_descriptor_digest
)) {
3679 /* Too old: remove it. (If we're a cache, just move it into
3682 "Forgetting obsolete (too old) routerinfo for router %s",
3683 router_describe(router
));
3684 routerlist_remove(routerlist
, router
, 1, now
);
3690 //routerlist_assert_ok(routerlist);
3692 /* Remove far-too-old members of routerlist->old_routers. */
3693 cutoff
= now
- OLD_ROUTER_DESC_MAX_AGE
;
3694 for (i
= 0; i
< smartlist_len(routerlist
->old_routers
); ++i
) {
3695 sd
= smartlist_get(routerlist
->old_routers
, i
);
3696 if (sd
->published_on
<= cutoff
&&
3697 sd
->last_listed_as_valid_until
< now
&&
3698 !digestset_contains(retain
, sd
->signed_descriptor_digest
)) {
3699 /* Too old. Remove it. */
3700 routerlist_remove_old(routerlist
, sd
, i
--);
3704 //routerlist_assert_ok(routerlist);
3706 log_info(LD_DIR
, "We have %d live routers and %d old router descriptors.",
3707 smartlist_len(routerlist
->routers
),
3708 smartlist_len(routerlist
->old_routers
));
3710 /* Now we might have to look at routerlist->old_routers for extraneous
3711 * members. (We'd keep all the members if we could, but we need to save
3712 * space.) First, check whether we have too many router descriptors, total.
3713 * We're okay with having too many for some given router, so long as the
3714 * total number doesn't approach max_descriptors_per_router()*len(router).
3716 if (smartlist_len(routerlist
->old_routers
) <
3717 smartlist_len(routerlist
->routers
))
3720 /* Sort by identity, then fix indices. */
3721 smartlist_sort(routerlist
->old_routers
, compare_old_routers_by_identity_
);
3723 for (i
= 0; i
< smartlist_len(routerlist
->old_routers
); ++i
) {
3724 signed_descriptor_t
*r
= smartlist_get(routerlist
->old_routers
, i
);
3725 r
->routerlist_index
= i
;
3728 /* Iterate through the list from back to front, so when we remove descriptors
3729 * we don't mess up groups we haven't gotten to. */
3730 for (i
= smartlist_len(routerlist
->old_routers
)-1; i
>= 0; --i
) {
3731 signed_descriptor_t
*r
= smartlist_get(routerlist
->old_routers
, i
);
3733 cur_id
= r
->identity_digest
;
3736 if (tor_memneq(cur_id
, r
->identity_digest
, DIGEST_LEN
)) {
3737 routerlist_remove_old_cached_routers_with_id(now
,
3738 cutoff
, i
+1, hi
, retain
);
3739 cur_id
= r
->identity_digest
;
3744 routerlist_remove_old_cached_routers_with_id(now
, cutoff
, 0, hi
, retain
);
3745 //routerlist_assert_ok(routerlist);
3748 digestset_free(retain
);
3749 router_rebuild_store(RRS_DONT_REMOVE_OLD
, &routerlist
->desc_store
);
3750 router_rebuild_store(RRS_DONT_REMOVE_OLD
,&routerlist
->extrainfo_store
);
3753 /** We just added a new set of descriptors. Take whatever extra steps
3756 routerlist_descriptors_added(smartlist_t
*sl
, int from_cache
)
3759 control_event_descriptors_changed(sl
);
3760 SMARTLIST_FOREACH_BEGIN(sl
, routerinfo_t
*, ri
) {
3761 if (ri
->purpose
== ROUTER_PURPOSE_BRIDGE
)
3762 learned_bridge_descriptor(ri
, from_cache
);
3763 if (ri
->needs_retest_if_added
) {
3764 ri
->needs_retest_if_added
= 0;
3765 dirserv_single_reachability_test(approx_time(), ri
);
3767 } SMARTLIST_FOREACH_END(ri
);
3771 * Code to parse a single router descriptor and insert it into the
3772 * routerlist. Return -1 if the descriptor was ill-formed; 0 if the
3773 * descriptor was well-formed but could not be added; and 1 if the
3774 * descriptor was added.
3776 * If we don't add it and <b>msg</b> is not NULL, then assign to
3777 * *<b>msg</b> a static string describing the reason for refusing the
3780 * This is used only by the controller.
3783 router_load_single_router(const char *s
, uint8_t purpose
, int cache
,
3787 was_router_added_t r
;
3789 char annotation_buf
[ROUTER_ANNOTATION_BUF_LEN
];
3793 tor_snprintf(annotation_buf
, sizeof(annotation_buf
),
3794 "@source controller\n"
3795 "@purpose %s\n", router_purpose_to_string(purpose
));
3797 if (!(ri
= router_parse_entry_from_string(s
, NULL
, 1, 0, annotation_buf
))) {
3798 log_warn(LD_DIR
, "Error parsing router descriptor; dropping.");
3799 *msg
= "Couldn't parse router descriptor.";
3802 tor_assert(ri
->purpose
== purpose
);
3803 if (router_is_me(ri
)) {
3804 log_warn(LD_DIR
, "Router's identity key matches mine; dropping.");
3805 *msg
= "Router's identity key matches mine.";
3806 routerinfo_free(ri
);
3810 if (!cache
) /* obey the preference of the controller */
3811 ri
->cache_info
.do_not_cache
= 1;
3813 lst
= smartlist_new();
3814 smartlist_add(lst
, ri
);
3815 routers_update_status_from_consensus_networkstatus(lst
, 0);
3817 r
= router_add_to_routerlist(ri
, msg
, 0, 0);
3818 if (!WRA_WAS_ADDED(r
)) {
3819 /* we've already assigned to *msg now, and ri is already freed */
3821 if (r
== ROUTER_AUTHDIR_REJECTS
)
3822 log_warn(LD_DIR
, "Couldn't add router to list: %s Dropping.", *msg
);
3823 smartlist_free(lst
);
3826 routerlist_descriptors_added(lst
, 0);
3827 smartlist_free(lst
);
3828 log_debug(LD_DIR
, "Added router to list");
3833 /** Given a string <b>s</b> containing some routerdescs, parse it and put the
3834 * routers into our directory. If saved_location is SAVED_NOWHERE, the routers
3835 * are in response to a query to the network: cache them by adding them to
3838 * Return the number of routers actually added.
3840 * If <b>requested_fingerprints</b> is provided, it must contain a list of
3841 * uppercased fingerprints. Do not update any router whose
3842 * fingerprint is not on the list; after updating a router, remove its
3843 * fingerprint from the list.
3845 * If <b>descriptor_digests</b> is non-zero, then the requested_fingerprints
3846 * are descriptor digests. Otherwise they are identity digests.
3849 router_load_routers_from_string(const char *s
, const char *eos
,
3850 saved_location_t saved_location
,
3851 smartlist_t
*requested_fingerprints
,
3852 int descriptor_digests
,
3853 const char *prepend_annotations
)
3855 smartlist_t
*routers
= smartlist_new(), *changed
= smartlist_new();
3856 char fp
[HEX_DIGEST_LEN
+1];
3858 int from_cache
= (saved_location
!= SAVED_NOWHERE
);
3859 int allow_annotations
= (saved_location
!= SAVED_NOWHERE
);
3860 int any_changed
= 0;
3862 router_parse_list_from_string(&s
, eos
, routers
, saved_location
, 0,
3863 allow_annotations
, prepend_annotations
);
3865 routers_update_status_from_consensus_networkstatus(routers
, !from_cache
);
3867 log_info(LD_DIR
, "%d elements to add", smartlist_len(routers
));
3869 SMARTLIST_FOREACH_BEGIN(routers
, routerinfo_t
*, ri
) {
3870 was_router_added_t r
;
3872 if (requested_fingerprints
) {
3873 base16_encode(fp
, sizeof(fp
), descriptor_digests
?
3874 ri
->cache_info
.signed_descriptor_digest
:
3875 ri
->cache_info
.identity_digest
,
3877 if (smartlist_contains_string(requested_fingerprints
, fp
)) {
3878 smartlist_string_remove(requested_fingerprints
, fp
);
3881 smartlist_join_strings(requested_fingerprints
," ",0,NULL
);
3883 "We received a router descriptor with a fingerprint (%s) "
3884 "that we never requested. (We asked for: %s.) Dropping.",
3886 tor_free(requested
);
3887 routerinfo_free(ri
);
3892 memcpy(d
, ri
->cache_info
.signed_descriptor_digest
, DIGEST_LEN
);
3893 r
= router_add_to_routerlist(ri
, &msg
, from_cache
, !from_cache
);
3894 if (WRA_WAS_ADDED(r
)) {
3896 smartlist_add(changed
, ri
);
3897 routerlist_descriptors_added(changed
, from_cache
);
3898 smartlist_clear(changed
);
3899 } else if (WRA_WAS_REJECTED(r
)) {
3900 download_status_t
*dl_status
;
3901 dl_status
= router_get_dl_status_by_descriptor_digest(d
);
3903 log_info(LD_GENERAL
, "Marking router %s as never downloadable",
3904 hex_str(d
, DIGEST_LEN
));
3905 download_status_mark_impossible(dl_status
);
3908 } SMARTLIST_FOREACH_END(ri
);
3910 routerlist_assert_ok(routerlist
);
3913 router_rebuild_store(0, &routerlist
->desc_store
);
3915 smartlist_free(routers
);
3916 smartlist_free(changed
);
3921 /** Parse one or more extrainfos from <b>s</b> (ending immediately before
3922 * <b>eos</b> if <b>eos</b> is present). Other arguments are as for
3923 * router_load_routers_from_string(). */
3925 router_load_extrainfo_from_string(const char *s
, const char *eos
,
3926 saved_location_t saved_location
,
3927 smartlist_t
*requested_fingerprints
,
3928 int descriptor_digests
)
3930 smartlist_t
*extrainfo_list
= smartlist_new();
3932 int from_cache
= (saved_location
!= SAVED_NOWHERE
);
3934 router_parse_list_from_string(&s
, eos
, extrainfo_list
, saved_location
, 1, 0,
3937 log_info(LD_DIR
, "%d elements to add", smartlist_len(extrainfo_list
));
3939 SMARTLIST_FOREACH_BEGIN(extrainfo_list
, extrainfo_t
*, ei
) {
3940 was_router_added_t added
=
3941 router_add_extrainfo_to_routerlist(ei
, &msg
, from_cache
, !from_cache
);
3942 if (WRA_WAS_ADDED(added
) && requested_fingerprints
) {
3943 char fp
[HEX_DIGEST_LEN
+1];
3944 base16_encode(fp
, sizeof(fp
), descriptor_digests
?
3945 ei
->cache_info
.signed_descriptor_digest
:
3946 ei
->cache_info
.identity_digest
,
3948 smartlist_string_remove(requested_fingerprints
, fp
);
3949 /* We silently let people stuff us with extrainfos we didn't ask for,
3950 * so long as we would have wanted them anyway. Since we always fetch
3951 * all the extrainfos we want, and we never actually act on them
3952 * inside Tor, this should be harmless. */
3954 } SMARTLIST_FOREACH_END(ei
);
3956 routerlist_assert_ok(routerlist
);
3957 router_rebuild_store(0, &router_get_routerlist()->extrainfo_store
);
3959 smartlist_free(extrainfo_list
);
3962 /** Return true iff any networkstatus includes a descriptor whose digest
3963 * is that of <b>desc</b>. */
3965 signed_desc_digest_is_recognized(signed_descriptor_t
*desc
)
3967 const routerstatus_t
*rs
;
3968 networkstatus_t
*consensus
= networkstatus_get_latest_consensus();
3971 rs
= networkstatus_vote_find_entry(consensus
, desc
->identity_digest
);
3972 if (rs
&& tor_memeq(rs
->descriptor_digest
,
3973 desc
->signed_descriptor_digest
, DIGEST_LEN
))
3979 /** Update downloads for router descriptors and/or microdescriptors as
3982 update_all_descriptor_downloads(time_t now
)
3984 if (get_options()->DisableNetwork
)
3986 update_router_descriptor_downloads(now
);
3987 update_microdesc_downloads(now
);
3988 launch_dummy_descriptor_download_as_needed(now
, get_options());
3991 /** Clear all our timeouts for fetching v3 directory stuff, and then
3992 * give it all a try again. */
3994 routerlist_retry_directory_downloads(time_t now
)
3996 router_reset_status_download_failures();
3997 router_reset_descriptor_download_failures();
3998 if (get_options()->DisableNetwork
)
4000 update_networkstatus_downloads(now
);
4001 update_all_descriptor_downloads(now
);
4004 /** Return true iff <b>router</b> does not permit exit streams.
4007 router_exit_policy_rejects_all(const routerinfo_t
*router
)
4009 return router
->policy_is_reject_star
;
4012 /** Create an directory server at <b>address</b>:<b>port</b>, with OR identity
4013 * key <b>digest</b>. If <b>address</b> is NULL, add ourself. If
4014 * <b>is_authority</b>, this is a directory authority. Return the new
4015 * directory server entry on success or NULL on failure. */
4016 static dir_server_t
*
4017 dir_server_new(int is_authority
,
4018 const char *nickname
,
4019 const tor_addr_t
*addr
,
4020 const char *hostname
,
4021 uint16_t dir_port
, uint16_t or_port
,
4022 const char *digest
, const char *v3_auth_digest
,
4023 dirinfo_type_t type
,
4028 char *hostname_
= NULL
;
4033 if (tor_addr_family(addr
) == AF_INET
)
4034 a
= tor_addr_to_ipv4h(addr
);
4036 return NULL
; /*XXXX Support IPv6 */
4039 hostname_
= tor_dup_addr(addr
);
4041 hostname_
= tor_strdup(hostname
);
4043 ent
= tor_malloc_zero(sizeof(dir_server_t
));
4044 ent
->nickname
= nickname
? tor_strdup(nickname
) : NULL
;
4045 ent
->address
= hostname_
;
4047 ent
->dir_port
= dir_port
;
4048 ent
->or_port
= or_port
;
4049 ent
->is_running
= 1;
4050 ent
->is_authority
= is_authority
;
4052 ent
->weight
= weight
;
4053 memcpy(ent
->digest
, digest
, DIGEST_LEN
);
4054 if (v3_auth_digest
&& (type
& V3_DIRINFO
))
4055 memcpy(ent
->v3_identity_digest
, v3_auth_digest
, DIGEST_LEN
);
4058 tor_asprintf(&ent
->description
, "directory server \"%s\" at %s:%d",
4059 nickname
, hostname
, (int)dir_port
);
4061 tor_asprintf(&ent
->description
, "directory server at %s:%d",
4062 hostname
, (int)dir_port
);
4064 ent
->fake_status
.addr
= ent
->addr
;
4065 memcpy(ent
->fake_status
.identity_digest
, digest
, DIGEST_LEN
);
4067 strlcpy(ent
->fake_status
.nickname
, nickname
,
4068 sizeof(ent
->fake_status
.nickname
));
4070 ent
->fake_status
.nickname
[0] = '\0';
4071 ent
->fake_status
.dir_port
= ent
->dir_port
;
4072 ent
->fake_status
.or_port
= ent
->or_port
;
4077 /** Create an authoritative directory server at
4078 * <b>address</b>:<b>port</b>, with identity key <b>digest</b>. If
4079 * <b>address</b> is NULL, add ourself. Return the new trusted directory
4080 * server entry on success or NULL if we couldn't add it. */
4082 trusted_dir_server_new(const char *nickname
, const char *address
,
4083 uint16_t dir_port
, uint16_t or_port
,
4084 const char *digest
, const char *v3_auth_digest
,
4085 dirinfo_type_t type
, double weight
)
4089 char *hostname
=NULL
;
4090 dir_server_t
*result
;
4092 if (!address
) { /* The address is us; we should guess. */
4093 if (resolve_my_address(LOG_WARN
, get_options(),
4094 &a
, NULL
, &hostname
) < 0) {
4096 "Couldn't find a suitable address when adding ourself as a "
4097 "trusted directory server.");
4101 hostname
= tor_dup_ip(a
);
4103 if (tor_lookup_hostname(address
, &a
)) {
4105 "Unable to lookup address for directory server at '%s'",
4109 hostname
= tor_strdup(address
);
4111 tor_addr_from_ipv4h(&addr
, a
);
4113 result
= dir_server_new(1, nickname
, &addr
, hostname
,
4114 dir_port
, or_port
, digest
,
4115 v3_auth_digest
, type
, weight
);
4120 /** Return a new dir_server_t for a fallback directory server at
4121 * <b>addr</b>:<b>or_port</b>/<b>dir_port</b>, with identity key digest
4122 * <b>id_digest</b> */
4124 fallback_dir_server_new(const tor_addr_t
*addr
,
4125 uint16_t dir_port
, uint16_t or_port
,
4126 const char *id_digest
, double weight
)
4128 return dir_server_new(0, NULL
, addr
, NULL
, dir_port
, or_port
, id_digest
,
4129 NULL
, ALL_DIRINFO
, weight
);
4132 /** Add a directory server to the global list(s). */
4134 dir_server_add(dir_server_t
*ent
)
4136 if (!trusted_dir_servers
)
4137 trusted_dir_servers
= smartlist_new();
4138 if (!fallback_dir_servers
)
4139 fallback_dir_servers
= smartlist_new();
4141 if (ent
->is_authority
)
4142 smartlist_add(trusted_dir_servers
, ent
);
4144 smartlist_add(fallback_dir_servers
, ent
);
4145 router_dir_info_changed();
4148 /** Free storage held in <b>cert</b>. */
4150 authority_cert_free(authority_cert_t
*cert
)
4155 tor_free(cert
->cache_info
.signed_descriptor_body
);
4156 crypto_pk_free(cert
->signing_key
);
4157 crypto_pk_free(cert
->identity_key
);
4162 /** Free storage held in <b>ds</b>. */
4164 dir_server_free(dir_server_t
*ds
)
4169 tor_free(ds
->nickname
);
4170 tor_free(ds
->description
);
4171 tor_free(ds
->address
);
4175 /** Remove all members from the list of dir servers. */
4177 clear_dir_servers(void)
4179 if (fallback_dir_servers
) {
4180 SMARTLIST_FOREACH(fallback_dir_servers
, dir_server_t
*, ent
,
4181 dir_server_free(ent
));
4182 smartlist_clear(fallback_dir_servers
);
4184 fallback_dir_servers
= smartlist_new();
4186 if (trusted_dir_servers
) {
4187 smartlist_clear(trusted_dir_servers
);
4189 trusted_dir_servers
= smartlist_new();
4191 router_dir_info_changed();
4194 /** For every current directory connection whose purpose is <b>purpose</b>,
4195 * and where the resource being downloaded begins with <b>prefix</b>, split
4196 * rest of the resource into base16 fingerprints (or base64 fingerprints if
4197 * purpose==DIR_PURPPOSE_FETCH_MICRODESC), decode them, and set the
4198 * corresponding elements of <b>result</b> to a nonzero value.
4201 list_pending_downloads(digestmap_t
*result
,
4202 int purpose
, const char *prefix
)
4204 const size_t p_len
= strlen(prefix
);
4205 smartlist_t
*tmp
= smartlist_new();
4206 smartlist_t
*conns
= get_connection_array();
4207 int flags
= DSR_HEX
;
4208 if (purpose
== DIR_PURPOSE_FETCH_MICRODESC
)
4209 flags
= DSR_DIGEST256
|DSR_BASE64
;
4213 SMARTLIST_FOREACH_BEGIN(conns
, connection_t
*, conn
) {
4214 if (conn
->type
== CONN_TYPE_DIR
&&
4215 conn
->purpose
== purpose
&&
4216 !conn
->marked_for_close
) {
4217 const char *resource
= TO_DIR_CONN(conn
)->requested_resource
;
4218 if (!strcmpstart(resource
, prefix
))
4219 dir_split_resource_into_fingerprints(resource
+ p_len
,
4222 } SMARTLIST_FOREACH_END(conn
);
4224 SMARTLIST_FOREACH(tmp
, char *, d
,
4226 digestmap_set(result
, d
, (void*)1);
4229 smartlist_free(tmp
);
4232 /** For every router descriptor (or extra-info document if <b>extrainfo</b> is
4233 * true) we are currently downloading by descriptor digest, set result[d] to
4236 list_pending_descriptor_downloads(digestmap_t
*result
, int extrainfo
)
4239 extrainfo
? DIR_PURPOSE_FETCH_EXTRAINFO
: DIR_PURPOSE_FETCH_SERVERDESC
;
4240 list_pending_downloads(result
, purpose
, "d/");
4243 /** For every microdescriptor we are currently downloading by descriptor
4244 * digest, set result[d] to (void*)1. (Note that microdescriptor digests
4245 * are 256-bit, and digestmap_t only holds 160-bit digests, so we're only
4246 * getting the first 20 bytes of each digest here.)
4248 * XXXX Let there be a digestmap256_t, and use that instead.
4251 list_pending_microdesc_downloads(digestmap_t
*result
)
4253 list_pending_downloads(result
, DIR_PURPOSE_FETCH_MICRODESC
, "d/");
4256 /** For every certificate we are currently downloading by (identity digest,
4257 * signing key digest) pair, set result[fp_pair] to (void *1).
4260 list_pending_fpsk_downloads(fp_pair_map_t
*result
)
4262 const char *pfx
= "fp-sk/";
4265 const char *resource
;
4269 tmp
= smartlist_new();
4270 conns
= get_connection_array();
4272 SMARTLIST_FOREACH_BEGIN(conns
, connection_t
*, conn
) {
4273 if (conn
->type
== CONN_TYPE_DIR
&&
4274 conn
->purpose
== DIR_PURPOSE_FETCH_CERTIFICATE
&&
4275 !conn
->marked_for_close
) {
4276 resource
= TO_DIR_CONN(conn
)->requested_resource
;
4277 if (!strcmpstart(resource
, pfx
))
4278 dir_split_resource_into_fingerprint_pairs(resource
+ strlen(pfx
),
4281 } SMARTLIST_FOREACH_END(conn
);
4283 SMARTLIST_FOREACH_BEGIN(tmp
, fp_pair_t
*, fp
) {
4284 fp_pair_map_set(result
, fp
, (void*)1);
4286 } SMARTLIST_FOREACH_END(fp
);
4288 smartlist_free(tmp
);
4291 /** Launch downloads for all the descriptors whose digests or digests256
4292 * are listed as digests[i] for lo <= i < hi. (Lo and hi may be out of
4293 * range.) If <b>source</b> is given, download from <b>source</b>;
4294 * otherwise, download from an appropriate random directory server.
4297 initiate_descriptor_downloads(const routerstatus_t
*source
,
4299 smartlist_t
*digests
,
4300 int lo
, int hi
, int pds_flags
)
4303 char *resource
, *cp
;
4306 int digest_len
= DIGEST_LEN
, enc_digest_len
= HEX_DIGEST_LEN
;
4310 if (purpose
== DIR_PURPOSE_FETCH_MICRODESC
) {
4311 /* Microdescriptors are downloaded by "-"-separated base64-encoded
4312 * 256-bit digests. */
4313 digest_len
= DIGEST256_LEN
;
4314 enc_digest_len
= BASE64_DIGEST256_LEN
;
4323 if (hi
> smartlist_len(digests
))
4324 hi
= smartlist_len(digests
);
4326 r_len
= 8 + (enc_digest_len
+1)*n
;
4327 cp
= resource
= tor_malloc(r_len
);
4328 memcpy(cp
, "d/", 2);
4330 for (i
= lo
; i
< hi
; ++i
) {
4332 digest256_to_base64(cp
, smartlist_get(digests
, i
));
4334 base16_encode(cp
, r_len
-(cp
-resource
),
4335 smartlist_get(digests
,i
), digest_len
);
4337 cp
+= enc_digest_len
;
4340 memcpy(cp
-1, ".z", 3);
4343 /* We know which authority we want. */
4344 directory_initiate_command_routerstatus(source
, purpose
,
4345 ROUTER_PURPOSE_GENERAL
,
4347 resource
, NULL
, 0, 0);
4349 directory_get_from_dirserver(purpose
, ROUTER_PURPOSE_GENERAL
, resource
,
4355 /** Max amount of hashes to download per request.
4356 * Since squid does not like URLs >= 4096 bytes we limit it to 96.
4357 * 4096 - strlen(http://255.255.255.255/tor/server/d/.z) == 4058
4358 * 4058/41 (40 for the hash and 1 for the + that separates them) => 98
4359 * So use 96 because it's a nice number.
4361 #define MAX_DL_PER_REQUEST 96
4362 #define MAX_MICRODESC_DL_PER_REQUEST 92
4363 /** Don't split our requests so finely that we are requesting fewer than
4364 * this number per server. */
4365 #define MIN_DL_PER_REQUEST 4
4366 /** To prevent a single screwy cache from confusing us by selective reply,
4367 * try to split our requests into at least this many requests. */
4368 #define MIN_REQUESTS 3
4369 /** If we want fewer than this many descriptors, wait until we
4370 * want more, or until TestingClientMaxIntervalWithoutRequest has passed. */
4371 #define MAX_DL_TO_DELAY 16
4373 /** Given a <b>purpose</b> (FETCH_MICRODESC or FETCH_SERVERDESC) and a list of
4374 * router descriptor digests or microdescriptor digest256s in
4375 * <b>downloadable</b>, decide whether to delay fetching until we have more.
4376 * If we don't want to delay, launch one or more requests to the appropriate
4377 * directory authorities.
4380 launch_descriptor_downloads(int purpose
,
4381 smartlist_t
*downloadable
,
4382 const routerstatus_t
*source
, time_t now
)
4384 int should_delay
= 0, n_downloadable
;
4385 const or_options_t
*options
= get_options();
4386 const char *descname
;
4388 tor_assert(purpose
== DIR_PURPOSE_FETCH_SERVERDESC
||
4389 purpose
== DIR_PURPOSE_FETCH_MICRODESC
);
4391 descname
= (purpose
== DIR_PURPOSE_FETCH_SERVERDESC
) ?
4392 "routerdesc" : "microdesc";
4394 n_downloadable
= smartlist_len(downloadable
);
4395 if (!directory_fetches_dir_info_early(options
)) {
4396 if (n_downloadable
>= MAX_DL_TO_DELAY
) {
4398 "There are enough downloadable %ss to launch requests.",
4402 should_delay
= (last_descriptor_download_attempted
+
4403 options
->TestingClientMaxIntervalWithoutRequest
) > now
;
4404 if (!should_delay
&& n_downloadable
) {
4405 if (last_descriptor_download_attempted
) {
4407 "There are not many downloadable %ss, but we've "
4408 "been waiting long enough (%d seconds). Downloading.",
4410 (int)(now
-last_descriptor_download_attempted
));
4413 "There are not many downloadable %ss, but we haven't "
4414 "tried downloading descriptors recently. Downloading.",
4421 if (! should_delay
&& n_downloadable
) {
4422 int i
, n_per_request
;
4423 const char *req_plural
= "", *rtr_plural
= "";
4424 int pds_flags
= PDS_RETRY_IF_NO_SERVERS
;
4425 if (! authdir_mode_any_nonhidserv(options
)) {
4426 /* If we wind up going to the authorities, we want to only open one
4427 * connection to each authority at a time, so that we don't overload
4428 * them. We do this by setting PDS_NO_EXISTING_SERVERDESC_FETCH
4429 * regardless of whether we're a cache or not; it gets ignored if we're
4430 * not calling router_pick_trusteddirserver.
4432 * Setting this flag can make initiate_descriptor_downloads() ignore
4433 * requests. We need to make sure that we do in fact call
4434 * update_router_descriptor_downloads() later on, once the connections
4435 * have succeeded or failed.
4437 pds_flags
|= (purpose
== DIR_PURPOSE_FETCH_MICRODESC
) ?
4438 PDS_NO_EXISTING_MICRODESC_FETCH
:
4439 PDS_NO_EXISTING_SERVERDESC_FETCH
;
4442 n_per_request
= CEIL_DIV(n_downloadable
, MIN_REQUESTS
);
4443 if (purpose
== DIR_PURPOSE_FETCH_MICRODESC
) {
4444 if (n_per_request
> MAX_MICRODESC_DL_PER_REQUEST
)
4445 n_per_request
= MAX_MICRODESC_DL_PER_REQUEST
;
4447 if (n_per_request
> MAX_DL_PER_REQUEST
)
4448 n_per_request
= MAX_DL_PER_REQUEST
;
4450 if (n_per_request
< MIN_DL_PER_REQUEST
)
4451 n_per_request
= MIN_DL_PER_REQUEST
;
4453 if (n_downloadable
> n_per_request
)
4454 req_plural
= rtr_plural
= "s";
4455 else if (n_downloadable
> 1)
4459 "Launching %d request%s for %d %s%s, %d at a time",
4460 CEIL_DIV(n_downloadable
, n_per_request
), req_plural
,
4461 n_downloadable
, descname
, rtr_plural
, n_per_request
);
4462 smartlist_sort_digests(downloadable
);
4463 for (i
=0; i
< n_downloadable
; i
+= n_per_request
) {
4464 initiate_descriptor_downloads(source
, purpose
,
4465 downloadable
, i
, i
+n_per_request
,
4468 last_descriptor_download_attempted
= now
;
4472 /** For any descriptor that we want that's currently listed in
4473 * <b>consensus</b>, download it as appropriate. */
4475 update_consensus_router_descriptor_downloads(time_t now
, int is_vote
,
4476 networkstatus_t
*consensus
)
4478 const or_options_t
*options
= get_options();
4479 digestmap_t
*map
= NULL
;
4480 smartlist_t
*no_longer_old
= smartlist_new();
4481 smartlist_t
*downloadable
= smartlist_new();
4482 routerstatus_t
*source
= NULL
;
4483 int authdir
= authdir_mode(options
);
4484 int n_delayed
=0, n_have
=0, n_would_reject
=0, n_wouldnt_use
=0,
4485 n_inprogress
=0, n_in_oldrouters
=0;
4487 if (directory_too_idle_to_fetch_descriptors(options
, now
))
4493 /* where's it from, so we know whom to ask for descriptors */
4495 networkstatus_voter_info_t
*voter
= smartlist_get(consensus
->voters
, 0);
4497 ds
= trusteddirserver_get_by_v3_auth_digest(voter
->identity_digest
);
4499 source
= &(ds
->fake_status
);
4501 log_warn(LD_DIR
, "couldn't lookup source from vote?");
4504 map
= digestmap_new();
4505 list_pending_descriptor_downloads(map
, 0);
4506 SMARTLIST_FOREACH_BEGIN(consensus
->routerstatus_list
, void *, rsp
) {
4507 routerstatus_t
*rs
=
4508 is_vote
? &(((vote_routerstatus_t
*)rsp
)->status
) : rsp
;
4509 signed_descriptor_t
*sd
;
4510 if ((sd
= router_get_by_descriptor_digest(rs
->descriptor_digest
))) {
4511 const routerinfo_t
*ri
;
4513 if (!(ri
= router_get_by_id_digest(rs
->identity_digest
)) ||
4514 tor_memneq(ri
->cache_info
.signed_descriptor_digest
,
4515 sd
->signed_descriptor_digest
, DIGEST_LEN
)) {
4516 /* We have a descriptor with this digest, but either there is no
4517 * entry in routerlist with the same ID (!ri), or there is one,
4518 * but the identity digest differs (memneq).
4520 smartlist_add(no_longer_old
, sd
);
4521 ++n_in_oldrouters
; /* We have it in old_routers. */
4523 continue; /* We have it already. */
4525 if (digestmap_get(map
, rs
->descriptor_digest
)) {
4527 continue; /* We have an in-progress download. */
4529 if (!download_status_is_ready(&rs
->dl_status
, now
,
4530 options
->TestingDescriptorMaxDownloadTries
)) {
4531 ++n_delayed
; /* Not ready for retry. */
4534 if (authdir
&& dirserv_would_reject_router(rs
)) {
4536 continue; /* We would throw it out immediately. */
4538 if (!directory_caches_dir_info(options
) &&
4539 !client_would_use_router(rs
, now
, options
)) {
4541 continue; /* We would never use it ourself. */
4543 if (is_vote
&& source
) {
4544 char time_bufnew
[ISO_TIME_LEN
+1];
4545 char time_bufold
[ISO_TIME_LEN
+1];
4546 const routerinfo_t
*oldrouter
;
4547 oldrouter
= router_get_by_id_digest(rs
->identity_digest
);
4548 format_iso_time(time_bufnew
, rs
->published_on
);
4550 format_iso_time(time_bufold
, oldrouter
->cache_info
.published_on
);
4551 log_info(LD_DIR
, "Learned about %s (%s vs %s) from %s's vote (%s)",
4552 routerstatus_describe(rs
),
4554 oldrouter
? time_bufold
: "none",
4555 source
->nickname
, oldrouter
? "known" : "unknown");
4557 smartlist_add(downloadable
, rs
->descriptor_digest
);
4558 } SMARTLIST_FOREACH_END(rsp
);
4560 if (!authdir_mode_handles_descs(options
, ROUTER_PURPOSE_GENERAL
)
4561 && smartlist_len(no_longer_old
)) {
4562 routerlist_t
*rl
= router_get_routerlist();
4563 log_info(LD_DIR
, "%d router descriptors listed in consensus are "
4564 "currently in old_routers; making them current.",
4565 smartlist_len(no_longer_old
));
4566 SMARTLIST_FOREACH_BEGIN(no_longer_old
, signed_descriptor_t
*, sd
) {
4568 was_router_added_t r
;
4569 routerinfo_t
*ri
= routerlist_reparse_old(rl
, sd
);
4571 log_warn(LD_BUG
, "Failed to re-parse a router.");
4574 r
= router_add_to_routerlist(ri
, &msg
, 1, 0);
4575 if (WRA_WAS_OUTDATED(r
)) {
4576 log_warn(LD_DIR
, "Couldn't add re-parsed router: %s",
4579 } SMARTLIST_FOREACH_END(sd
);
4580 routerlist_assert_ok(rl
);
4584 "%d router descriptors downloadable. %d delayed; %d present "
4585 "(%d of those were in old_routers); %d would_reject; "
4586 "%d wouldnt_use; %d in progress.",
4587 smartlist_len(downloadable
), n_delayed
, n_have
, n_in_oldrouters
,
4588 n_would_reject
, n_wouldnt_use
, n_inprogress
);
4590 launch_descriptor_downloads(DIR_PURPOSE_FETCH_SERVERDESC
,
4591 downloadable
, source
, now
);
4593 digestmap_free(map
, NULL
);
4595 smartlist_free(downloadable
);
4596 smartlist_free(no_longer_old
);
4599 /** How often should we launch a server/authority request to be sure of getting
4600 * a guess for our IP? */
4601 /*XXXX024 this info should come from netinfo cells or something, or we should
4602 * do this only when we aren't seeing incoming data. see bug 652. */
4603 #define DUMMY_DOWNLOAD_INTERVAL (20*60)
4605 /** As needed, launch a dummy router descriptor fetch to see if our
4606 * address has changed. */
4608 launch_dummy_descriptor_download_as_needed(time_t now
,
4609 const or_options_t
*options
)
4611 static time_t last_dummy_download
= 0;
4612 /* XXXX024 we could be smarter here; see notes on bug 652. */
4613 /* If we're a server that doesn't have a configured address, we rely on
4614 * directory fetches to learn when our address changes. So if we haven't
4615 * tried to get any routerdescs in a long time, try a dummy fetch now. */
4616 if (!options
->Address
&&
4617 server_mode(options
) &&
4618 last_descriptor_download_attempted
+ DUMMY_DOWNLOAD_INTERVAL
< now
&&
4619 last_dummy_download
+ DUMMY_DOWNLOAD_INTERVAL
< now
) {
4620 last_dummy_download
= now
;
4621 directory_get_from_dirserver(DIR_PURPOSE_FETCH_SERVERDESC
,
4622 ROUTER_PURPOSE_GENERAL
, "authority.z",
4623 PDS_RETRY_IF_NO_SERVERS
);
4627 /** Launch downloads for router status as needed. */
4629 update_router_descriptor_downloads(time_t now
)
4631 const or_options_t
*options
= get_options();
4632 if (should_delay_dir_fetches(options
, NULL
))
4634 if (!we_fetch_router_descriptors(options
))
4637 update_consensus_router_descriptor_downloads(now
, 0,
4638 networkstatus_get_reasonably_live_consensus(now
, FLAV_NS
));
4641 /** Launch extrainfo downloads as needed. */
4643 update_extrainfo_downloads(time_t now
)
4645 const or_options_t
*options
= get_options();
4647 smartlist_t
*wanted
;
4648 digestmap_t
*pending
;
4650 int n_no_ei
= 0, n_pending
= 0, n_have
= 0, n_delay
= 0;
4651 if (! options
->DownloadExtraInfo
)
4653 if (should_delay_dir_fetches(options
, NULL
))
4655 if (!router_have_minimum_dir_info())
4658 pending
= digestmap_new();
4659 list_pending_descriptor_downloads(pending
, 1);
4660 rl
= router_get_routerlist();
4661 wanted
= smartlist_new();
4662 for (old_routers
= 0; old_routers
< 2; ++old_routers
) {
4663 smartlist_t
*lst
= old_routers
? rl
->old_routers
: rl
->routers
;
4664 for (i
= 0; i
< smartlist_len(lst
); ++i
) {
4665 signed_descriptor_t
*sd
;
4668 sd
= smartlist_get(lst
, i
);
4670 sd
= &((routerinfo_t
*)smartlist_get(lst
, i
))->cache_info
;
4671 if (sd
->is_extrainfo
)
4672 continue; /* This should never happen. */
4673 if (old_routers
&& !router_get_by_id_digest(sd
->identity_digest
))
4674 continue; /* Couldn't check the signature if we got it. */
4675 if (sd
->extrainfo_is_bogus
)
4677 d
= sd
->extra_info_digest
;
4678 if (tor_digest_is_zero(d
)) {
4682 if (eimap_get(rl
->extra_info_map
, d
)) {
4686 if (!download_status_is_ready(&sd
->ei_dl_status
, now
,
4687 options
->TestingDescriptorMaxDownloadTries
)) {
4691 if (digestmap_get(pending
, d
)) {
4695 smartlist_add(wanted
, d
);
4698 digestmap_free(pending
, NULL
);
4700 log_info(LD_DIR
, "Extrainfo download status: %d router with no ei, %d "
4701 "with present ei, %d delaying, %d pending, %d downloadable.",
4702 n_no_ei
, n_have
, n_delay
, n_pending
, smartlist_len(wanted
));
4704 smartlist_shuffle(wanted
);
4705 for (i
= 0; i
< smartlist_len(wanted
); i
+= MAX_DL_PER_REQUEST
) {
4706 initiate_descriptor_downloads(NULL
, DIR_PURPOSE_FETCH_EXTRAINFO
,
4707 wanted
, i
, i
+ MAX_DL_PER_REQUEST
,
4708 PDS_RETRY_IF_NO_SERVERS
|PDS_NO_EXISTING_SERVERDESC_FETCH
);
4711 smartlist_free(wanted
);
4714 /** Reset the descriptor download failure count on all routers, so that we
4715 * can retry any long-failed routers immediately.
4718 router_reset_descriptor_download_failures(void)
4720 networkstatus_reset_download_failures();
4721 last_descriptor_download_attempted
= 0;
4724 SMARTLIST_FOREACH(routerlist
->routers
, routerinfo_t
*, ri
,
4726 download_status_reset(&ri
->cache_info
.ei_dl_status
);
4728 SMARTLIST_FOREACH(routerlist
->old_routers
, signed_descriptor_t
*, sd
,
4730 download_status_reset(&sd
->ei_dl_status
);
4734 /** Any changes in a router descriptor's publication time larger than this are
4735 * automatically non-cosmetic. */
4736 #define ROUTER_MAX_COSMETIC_TIME_DIFFERENCE (2*60*60)
4738 /** We allow uptime to vary from how much it ought to be by this much. */
4739 #define ROUTER_ALLOW_UPTIME_DRIFT (6*60*60)
4741 /** Return true iff the only differences between r1 and r2 are such that
4742 * would not cause a recent (post 0.1.1.6) dirserver to republish.
4745 router_differences_are_cosmetic(const routerinfo_t
*r1
, const routerinfo_t
*r2
)
4747 time_t r1pub
, r2pub
;
4748 long time_difference
;
4749 tor_assert(r1
&& r2
);
4751 /* r1 should be the one that was published first. */
4752 if (r1
->cache_info
.published_on
> r2
->cache_info
.published_on
) {
4753 const routerinfo_t
*ri_tmp
= r2
;
4758 /* If any key fields differ, they're different. */
4759 if (r1
->addr
!= r2
->addr
||
4760 strcasecmp(r1
->nickname
, r2
->nickname
) ||
4761 r1
->or_port
!= r2
->or_port
||
4762 !tor_addr_eq(&r1
->ipv6_addr
, &r2
->ipv6_addr
) ||
4763 r1
->ipv6_orport
!= r2
->ipv6_orport
||
4764 r1
->dir_port
!= r2
->dir_port
||
4765 r1
->purpose
!= r2
->purpose
||
4766 !crypto_pk_eq_keys(r1
->onion_pkey
, r2
->onion_pkey
) ||
4767 !crypto_pk_eq_keys(r1
->identity_pkey
, r2
->identity_pkey
) ||
4768 strcasecmp(r1
->platform
, r2
->platform
) ||
4769 (r1
->contact_info
&& !r2
->contact_info
) || /* contact_info is optional */
4770 (!r1
->contact_info
&& r2
->contact_info
) ||
4771 (r1
->contact_info
&& r2
->contact_info
&&
4772 strcasecmp(r1
->contact_info
, r2
->contact_info
)) ||
4773 r1
->is_hibernating
!= r2
->is_hibernating
||
4774 cmp_addr_policies(r1
->exit_policy
, r2
->exit_policy
))
4776 if ((r1
->declared_family
== NULL
) != (r2
->declared_family
== NULL
))
4778 if (r1
->declared_family
&& r2
->declared_family
) {
4780 if (smartlist_len(r1
->declared_family
)!=smartlist_len(r2
->declared_family
))
4782 n
= smartlist_len(r1
->declared_family
);
4783 for (i
=0; i
< n
; ++i
) {
4784 if (strcasecmp(smartlist_get(r1
->declared_family
, i
),
4785 smartlist_get(r2
->declared_family
, i
)))
4790 /* Did bandwidth change a lot? */
4791 if ((r1
->bandwidthcapacity
< r2
->bandwidthcapacity
/2) ||
4792 (r2
->bandwidthcapacity
< r1
->bandwidthcapacity
/2))
4795 /* Did the bandwidthrate or bandwidthburst change? */
4796 if ((r1
->bandwidthrate
!= r2
->bandwidthrate
) ||
4797 (r1
->bandwidthburst
!= r2
->bandwidthburst
))
4800 /* Did more than 12 hours pass? */
4801 if (r1
->cache_info
.published_on
+ ROUTER_MAX_COSMETIC_TIME_DIFFERENCE
4802 < r2
->cache_info
.published_on
)
4805 /* Did uptime fail to increase by approximately the amount we would think,
4806 * give or take some slop? */
4807 r1pub
= r1
->cache_info
.published_on
;
4808 r2pub
= r2
->cache_info
.published_on
;
4809 time_difference
= labs(r2
->uptime
- (r1
->uptime
+ (r2pub
- r1pub
)));
4810 if (time_difference
> ROUTER_ALLOW_UPTIME_DRIFT
&&
4811 time_difference
> r1
->uptime
* .05 &&
4812 time_difference
> r2
->uptime
* .05)
4815 /* Otherwise, the difference is cosmetic. */
4819 /** Check whether <b>ri</b> (a.k.a. sd) is a router compatible with the
4820 * extrainfo document
4821 * <b>ei</b>. If no router is compatible with <b>ei</b>, <b>ei</b> should be
4822 * dropped. Return 0 for "compatible", return 1 for "reject, and inform
4823 * whoever uploaded <b>ei</b>, and return -1 for "reject silently.". If
4824 * <b>msg</b> is present, set *<b>msg</b> to a description of the
4825 * incompatibility (if any).
4828 routerinfo_incompatible_with_extrainfo(const routerinfo_t
*ri
,
4830 signed_descriptor_t
*sd
,
4833 int digest_matches
, r
=1;
4837 sd
= (signed_descriptor_t
*)&ri
->cache_info
;
4840 if (msg
) *msg
= "Extrainfo signature was bad, or signed with wrong key.";
4844 digest_matches
= tor_memeq(ei
->cache_info
.signed_descriptor_digest
,
4845 sd
->extra_info_digest
, DIGEST_LEN
);
4847 /* The identity must match exactly to have been generated at the same time
4848 * by the same router. */
4849 if (tor_memneq(ri
->cache_info
.identity_digest
,
4850 ei
->cache_info
.identity_digest
,
4852 if (msg
) *msg
= "Extrainfo nickname or identity did not match routerinfo";
4853 goto err
; /* different servers */
4856 if (ei
->pending_sig
) {
4857 char signed_digest
[128];
4858 if (crypto_pk_public_checksig(ri
->identity_pkey
,
4859 signed_digest
, sizeof(signed_digest
),
4860 ei
->pending_sig
, ei
->pending_sig_len
) != DIGEST_LEN
||
4861 tor_memneq(signed_digest
, ei
->cache_info
.signed_descriptor_digest
,
4864 tor_free(ei
->pending_sig
);
4865 if (msg
) *msg
= "Extrainfo signature bad, or signed with wrong key";
4866 goto err
; /* Bad signature, or no match. */
4869 ei
->cache_info
.send_unencrypted
= ri
->cache_info
.send_unencrypted
;
4870 tor_free(ei
->pending_sig
);
4873 if (ei
->cache_info
.published_on
< sd
->published_on
) {
4874 if (msg
) *msg
= "Extrainfo published time did not match routerdesc";
4876 } else if (ei
->cache_info
.published_on
> sd
->published_on
) {
4877 if (msg
) *msg
= "Extrainfo published time did not match routerdesc";
4882 if (!digest_matches
) {
4883 if (msg
) *msg
= "Extrainfo digest did not match value from routerdesc";
4884 goto err
; /* Digest doesn't match declared value. */
4889 if (digest_matches
) {
4890 /* This signature was okay, and the digest was right: This is indeed the
4891 * corresponding extrainfo. But insanely, it doesn't match the routerinfo
4892 * that lists it. Don't try to fetch this one again. */
4893 sd
->extrainfo_is_bogus
= 1;
4899 /** Assert that the internal representation of <b>rl</b> is
4900 * self-consistent. */
4902 routerlist_assert_ok(const routerlist_t
*rl
)
4905 signed_descriptor_t
*sd2
;
4908 SMARTLIST_FOREACH_BEGIN(rl
->routers
, routerinfo_t
*, r
) {
4909 r2
= rimap_get(rl
->identity_map
, r
->cache_info
.identity_digest
);
4910 tor_assert(r
== r2
);
4911 sd2
= sdmap_get(rl
->desc_digest_map
,
4912 r
->cache_info
.signed_descriptor_digest
);
4913 tor_assert(&(r
->cache_info
) == sd2
);
4914 tor_assert(r
->cache_info
.routerlist_index
== r_sl_idx
);
4917 * Hoo boy. We need to fix this one, and the fix is a bit tricky, so
4918 * commenting this out is just a band-aid.
4920 * The problem is that, although well-behaved router descriptors
4921 * should never have the same value for their extra_info_digest, it's
4922 * possible for ill-behaved routers to claim whatever they like there.
4924 * The real answer is to trash desc_by_eid_map and instead have
4925 * something that indicates for a given extra-info digest we want,
4926 * what its download status is. We'll do that as a part of routerlist
4927 * refactoring once consensus directories are in. For now,
4928 * this rep violation is probably harmless: an adversary can make us
4929 * reset our retry count for an extrainfo, but that's not the end
4930 * of the world. Changing the representation in 0.2.0.x would just
4931 * destabilize the codebase.
4932 if (!tor_digest_is_zero(r->cache_info.extra_info_digest)) {
4933 signed_descriptor_t *sd3 =
4934 sdmap_get(rl->desc_by_eid_map, r->cache_info.extra_info_digest);
4935 tor_assert(sd3 == &(r->cache_info));
4938 } SMARTLIST_FOREACH_END(r
);
4939 SMARTLIST_FOREACH_BEGIN(rl
->old_routers
, signed_descriptor_t
*, sd
) {
4940 r2
= rimap_get(rl
->identity_map
, sd
->identity_digest
);
4941 tor_assert(!r2
|| sd
!= &(r2
->cache_info
));
4942 sd2
= sdmap_get(rl
->desc_digest_map
, sd
->signed_descriptor_digest
);
4943 tor_assert(sd
== sd2
);
4944 tor_assert(sd
->routerlist_index
== sd_sl_idx
);
4946 if (!tor_digest_is_zero(sd->extra_info_digest)) {
4947 signed_descriptor_t *sd3 =
4948 sdmap_get(rl->desc_by_eid_map, sd->extra_info_digest);
4949 tor_assert(sd3 == sd);
4952 } SMARTLIST_FOREACH_END(sd
);
4954 RIMAP_FOREACH(rl
->identity_map
, d
, r
) {
4955 tor_assert(tor_memeq(r
->cache_info
.identity_digest
, d
, DIGEST_LEN
));
4956 } DIGESTMAP_FOREACH_END
;
4957 SDMAP_FOREACH(rl
->desc_digest_map
, d
, sd
) {
4958 tor_assert(tor_memeq(sd
->signed_descriptor_digest
, d
, DIGEST_LEN
));
4959 } DIGESTMAP_FOREACH_END
;
4960 SDMAP_FOREACH(rl
->desc_by_eid_map
, d
, sd
) {
4961 tor_assert(!tor_digest_is_zero(d
));
4963 tor_assert(tor_memeq(sd
->extra_info_digest
, d
, DIGEST_LEN
));
4964 } DIGESTMAP_FOREACH_END
;
4965 EIMAP_FOREACH(rl
->extra_info_map
, d
, ei
) {
4966 signed_descriptor_t
*sd
;
4967 tor_assert(tor_memeq(ei
->cache_info
.signed_descriptor_digest
,
4969 sd
= sdmap_get(rl
->desc_by_eid_map
,
4970 ei
->cache_info
.signed_descriptor_digest
);
4971 // tor_assert(sd); // XXXX see above
4973 tor_assert(tor_memeq(ei
->cache_info
.signed_descriptor_digest
,
4974 sd
->extra_info_digest
, DIGEST_LEN
));
4976 } DIGESTMAP_FOREACH_END
;
4979 /** Allocate and return a new string representing the contact info
4980 * and platform string for <b>router</b>,
4981 * surrounded by quotes and using standard C escapes.
4983 * THIS FUNCTION IS NOT REENTRANT. Don't call it from outside the main
4984 * thread. Also, each call invalidates the last-returned value, so don't
4985 * try log_warn(LD_GENERAL, "%s %s", esc_router_info(a), esc_router_info(b));
4987 * If <b>router</b> is NULL, it just frees its internal memory and returns.
4990 esc_router_info(const routerinfo_t
*router
)
4992 static char *info
=NULL
;
4993 char *esc_contact
, *esc_platform
;
4997 return NULL
; /* we're exiting; just free the memory we use */
4999 esc_contact
= esc_for_log(router
->contact_info
);
5000 esc_platform
= esc_for_log(router
->platform
);
5002 tor_asprintf(&info
, "Contact %s, Platform %s", esc_contact
, esc_platform
);
5003 tor_free(esc_contact
);
5004 tor_free(esc_platform
);
5009 /** Helper for sorting: compare two routerinfos by their identity
5012 compare_routerinfo_by_id_digest_(const void **a
, const void **b
)
5014 routerinfo_t
*first
= *(routerinfo_t
**)a
, *second
= *(routerinfo_t
**)b
;
5015 return fast_memcmp(first
->cache_info
.identity_digest
,
5016 second
->cache_info
.identity_digest
,
5020 /** Sort a list of routerinfo_t in ascending order of identity digest. */
5022 routers_sort_by_identity(smartlist_t
*routers
)
5024 smartlist_sort(routers
, compare_routerinfo_by_id_digest_
);
5027 /** Called when we change a node set, or when we reload the geoip IPv4 list:
5028 * recompute all country info in all configuration node sets and in the
5031 refresh_all_country_info(void)
5033 const or_options_t
*options
= get_options();
5035 if (options
->EntryNodes
)
5036 routerset_refresh_countries(options
->EntryNodes
);
5037 if (options
->ExitNodes
)
5038 routerset_refresh_countries(options
->ExitNodes
);
5039 if (options
->ExcludeNodes
)
5040 routerset_refresh_countries(options
->ExcludeNodes
);
5041 if (options
->ExcludeExitNodes
)
5042 routerset_refresh_countries(options
->ExcludeExitNodes
);
5043 if (options
->ExcludeExitNodesUnion_
)
5044 routerset_refresh_countries(options
->ExcludeExitNodesUnion_
);
5046 nodelist_refresh_countries();
5049 /** Determine the routers that are responsible for <b>id</b> (binary) and
5050 * add pointers to those routers' routerstatus_t to <b>responsible_dirs</b>.
5051 * Return -1 if we're returning an empty smartlist, else return 0.
5054 hid_serv_get_responsible_directories(smartlist_t
*responsible_dirs
,
5057 int start
, found
, n_added
= 0, i
;
5058 networkstatus_t
*c
= networkstatus_get_latest_consensus();
5059 if (!c
|| !smartlist_len(c
->routerstatus_list
)) {
5060 log_warn(LD_REND
, "We don't have a consensus, so we can't perform v2 "
5061 "rendezvous operations.");
5065 start
= networkstatus_vote_find_entry_idx(c
, id
, &found
);
5066 if (start
== smartlist_len(c
->routerstatus_list
)) start
= 0;
5069 routerstatus_t
*r
= smartlist_get(c
->routerstatus_list
, i
);
5071 smartlist_add(responsible_dirs
, r
);
5072 if (++n_added
== REND_NUMBER_OF_CONSECUTIVE_REPLICAS
)
5075 if (++i
== smartlist_len(c
->routerstatus_list
))
5077 } while (i
!= start
);
5079 /* Even though we don't have the desired number of hidden service
5080 * directories, be happy if we got any. */
5081 return smartlist_len(responsible_dirs
) ? 0 : -1;
5084 /** Return true if this node is currently acting as hidden service
5085 * directory, false otherwise. */
5087 hid_serv_acting_as_directory(void)
5089 const routerinfo_t
*me
= router_get_my_routerinfo();
5092 if (!get_options()->HidServDirectoryV2
) {
5093 log_info(LD_REND
, "We are not acting as hidden service directory, "
5094 "because we have not been configured as such.");
5100 /** Return true if this node is responsible for storing the descriptor ID
5101 * in <b>query</b> and false otherwise. */
5103 hid_serv_responsible_for_desc_id(const char *query
)
5105 const routerinfo_t
*me
;
5106 routerstatus_t
*last_rs
;
5107 const char *my_id
, *last_id
;
5109 smartlist_t
*responsible
;
5110 if (!hid_serv_acting_as_directory())
5112 if (!(me
= router_get_my_routerinfo()))
5113 return 0; /* This is redundant, but let's be paranoid. */
5114 my_id
= me
->cache_info
.identity_digest
;
5115 responsible
= smartlist_new();
5116 if (hid_serv_get_responsible_directories(responsible
, query
) < 0) {
5117 smartlist_free(responsible
);
5120 last_rs
= smartlist_get(responsible
, smartlist_len(responsible
)-1);
5121 last_id
= last_rs
->identity_digest
;
5122 result
= rend_id_is_in_interval(my_id
, query
, last_id
);
5123 smartlist_free(responsible
);