/* Copyright (c) 2001 Matej Pfajfar. * Copyright (c) 2001-2004, Roger Dingledine. * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. * Copyright (c) 2007-2008, The Tor Project, Inc. */ /* See LICENSE for licensing information */ /** * \file routerlist.c * \brief Code to * maintain and access the global list of routerinfos for known * servers. **/ #include "or.h" // #define DEBUG_ROUTERLIST /****************************************************************************/ /* static function prototypes */ static routerstatus_t *router_pick_directory_server_impl( authority_type_t auth, int flags); static routerstatus_t *router_pick_trusteddirserver_impl( authority_type_t auth, int flags, int *n_busy_out); static void mark_all_trusteddirservers_up(void); static int router_nickname_matches(routerinfo_t *router, const char *nickname); static void trusted_dir_server_free(trusted_dir_server_t *ds); static void launch_router_descriptor_downloads(smartlist_t *downloadable, time_t now); static void update_consensus_router_descriptor_downloads(time_t now); static int signed_desc_digest_is_recognized(signed_descriptor_t *desc); static void update_router_have_minimum_dir_info(void); static const char *signed_descriptor_get_body_impl(signed_descriptor_t *desc, int with_annotations); static void list_pending_downloads(digestmap_t *result, int purpose, const char *prefix); DECLARE_TYPED_DIGESTMAP_FNS(sdmap_, digest_sd_map_t, signed_descriptor_t) DECLARE_TYPED_DIGESTMAP_FNS(rimap_, digest_ri_map_t, routerinfo_t) DECLARE_TYPED_DIGESTMAP_FNS(eimap_, digest_ei_map_t, extrainfo_t) #define SDMAP_FOREACH(map, keyvar, valvar) \ DIGESTMAP_FOREACH(sdmap_to_digestmap(map), keyvar, signed_descriptor_t *, \ valvar) #define RIMAP_FOREACH(map, keyvar, valvar) \ DIGESTMAP_FOREACH(rimap_to_digestmap(map), keyvar, routerinfo_t *, valvar) #define EIMAP_FOREACH(map, keyvar, valvar) \ DIGESTMAP_FOREACH(eimap_to_digestmap(map), keyvar, extrainfo_t *, valvar) /****************************************************************************/ /** Global list of a trusted_dir_server_t object for each trusted directory * server. */ static smartlist_t *trusted_dir_servers = NULL; /** List of for a given authority, and download status for latest certificate. */ typedef struct cert_list_t { download_status_t dl_status; smartlist_t *certs; } cert_list_t; /** Map from v3 identity key digest to cert_list_t. */ static digestmap_t *trusted_dir_certs = NULL; /** True iff any key certificate in at least one member of * trusted_dir_certs has changed since we last flushed the * certificates to disk. */ static int trusted_dir_servers_certs_changed = 0; /** Global list of all of the routers that we know about. */ static routerlist_t *routerlist = NULL; /** List of strings for nicknames we've already warned about and that are * still unknown / unavailable. */ static smartlist_t *warned_nicknames = NULL; /** The last time we tried to download any routerdesc, or 0 for "never". We * use this to rate-limit download attempts when the number of routerdescs to * download is low. */ static time_t last_routerdesc_download_attempted = 0; /** When we last computed the weights to use for bandwidths on directory * requests, what were the total weighted bandwidth, and our share of that * bandwidth? Used to determine what fraction of directory requests we should * expect to see. */ static uint64_t sl_last_total_weighted_bw = 0, sl_last_weighted_bw_of_me = 0; /** Return the number of directory authorities whose type matches some bit set * in type */ int get_n_authorities(authority_type_t type) { int n = 0; if (!trusted_dir_servers) return 0; SMARTLIST_FOREACH(trusted_dir_servers, trusted_dir_server_t *, ds, if (ds->type & type) ++n); return n; } #define get_n_v2_authorities() get_n_authorities(V2_AUTHORITY) /** Helper: Return the cert_list_t for an authority whose authority ID is * id_digest, allocating a new list if necessary. */ static cert_list_t * get_cert_list(const char *id_digest) { cert_list_t *cl; if (!trusted_dir_certs) trusted_dir_certs = digestmap_new(); cl = digestmap_get(trusted_dir_certs, id_digest); if (!cl) { cl = tor_malloc_zero(sizeof(cert_list_t)); cl->dl_status.schedule = DL_SCHED_CONSENSUS; cl->certs = smartlist_create(); digestmap_set(trusted_dir_certs, id_digest, cl); } return cl; } /** Reload the cached v3 key certificates from the cached-certs file in * the data directory. Return 0 on success, -1 on failure. */ int trusted_dirs_reload_certs(void) { char *filename; char *contents; int r; filename = get_datadir_fname("cached-certs"); contents = read_file_to_str(filename, RFTS_IGNORE_MISSING, NULL); tor_free(filename); if (!contents) return 0; r = trusted_dirs_load_certs_from_string(contents, 1, 1); tor_free(contents); return r; } /** Helper: return true iff we already have loaded the exact cert * cert. */ static INLINE int already_have_cert(authority_cert_t *cert) { cert_list_t *cl = get_cert_list(cert->cache_info.identity_digest); SMARTLIST_FOREACH(cl->certs, authority_cert_t *, c, { if (!memcmp(c->cache_info.signed_descriptor_digest, cert->cache_info.signed_descriptor_digest, DIGEST_LEN)) return 1; }); return 0; } /** Load a bunch of new key certificates from the string contents. If * from_store is true, the certificates are from the cache, and we * don't need to flush them to disk. If from_store is false, we need * to flush any changed certificates to disk. Return 0 on success, -1 on * failure. */ int trusted_dirs_load_certs_from_string(const char *contents, int from_store, int flush) { trusted_dir_server_t *ds; const char *s, *eos; for (s = contents; *s; s = eos) { authority_cert_t *cert = authority_cert_parse_from_string(s, &eos); cert_list_t *cl; if (!cert) break; ds = trusteddirserver_get_by_v3_auth_digest( cert->cache_info.identity_digest); log_debug(LD_DIR, "Parsed certificate for %s", ds ? ds->nickname : "unknown authority"); if (already_have_cert(cert)) { /* we already have this one. continue. */ log_info(LD_DIR, "Skipping %s certificate for %s that we " "already have.", from_store ? "cached" : "downloaded", ds ? ds->nickname : "??"); /* a duplicate on a download should be treated as a failure, since it * probably means we wanted a different secret key or we are trying to * replace an expired cert that has not in fact been updated. */ if (!from_store) { log_warn(LD_DIR, "Got a certificate for %s that we already have. " "Maybe they haven't updated it. Waiting for a while.", ds ? ds->nickname : "??"); authority_cert_dl_failed(cert->cache_info.identity_digest, 404); } authority_cert_free(cert); continue; } if (ds) { log_info(LD_DIR, "Adding %s certificate for directory authority %s with " "signing key %s", from_store ? "cached" : "downloaded", ds->nickname, hex_str(cert->signing_key_digest,DIGEST_LEN)); } else { log_info(LD_DIR, "Adding %s certificate for unrecognized directory " "authority with signing key %s", from_store ? "cached" : "downloaded", hex_str(cert->signing_key_digest,DIGEST_LEN)); } cl = get_cert_list(cert->cache_info.identity_digest); smartlist_add(cl->certs, cert); if (ds && cert->cache_info.published_on > ds->addr_current_at) { /* Check to see whether we should update our view of the authority's * address. */ if (cert->addr && cert->dir_port && (ds->addr != cert->addr || ds->dir_port != cert->dir_port)) { char *a = tor_dup_ip(cert->addr); log_notice(LD_DIR, "Updating address for directory authority %s " "from %s:%d to %s:%d based on in certificate.", ds->nickname, ds->address, (int)ds->dir_port, a, cert->dir_port); tor_free(a); ds->addr = cert->addr; ds->dir_port = cert->dir_port; } ds->addr_current_at = cert->cache_info.published_on; } if (!from_store) trusted_dir_servers_certs_changed = 1; } if (flush) trusted_dirs_flush_certs_to_disk(); networkstatus_note_certs_arrived(); return 0; } /** Save all v3 key certificates to the cached-certs file. */ void trusted_dirs_flush_certs_to_disk(void) { char *filename; smartlist_t *chunks; if (!trusted_dir_servers_certs_changed || !trusted_dir_certs) return; chunks = smartlist_create(); DIGESTMAP_FOREACH(trusted_dir_certs, key, cert_list_t *, cl) { SMARTLIST_FOREACH(cl->certs, authority_cert_t *, cert, { sized_chunk_t *c = tor_malloc(sizeof(sized_chunk_t)); c->bytes = cert->cache_info.signed_descriptor_body; c->len = cert->cache_info.signed_descriptor_len; smartlist_add(chunks, c); }); } DIGESTMAP_FOREACH_END; filename = get_datadir_fname("cached-certs"); if (write_chunks_to_file(filename, chunks, 0)) { log_warn(LD_FS, "Error writing certificates to disk."); } tor_free(filename); SMARTLIST_FOREACH(chunks, sized_chunk_t *, c, tor_free(c)); smartlist_free(chunks); trusted_dir_servers_certs_changed = 0; } /** Remove all v3 authority certificates that have been superseded for more * than 48 hours. (If the most recent cert was published more than 48 hours * ago, then we aren't going to get any consensuses signed with older * keys.) */ static void trusted_dirs_remove_old_certs(void) { time_t now = time(NULL); #define DEAD_CERT_LIFETIME (2*24*60*60) #define OLD_CERT_LIFETIME (7*24*60*60) if (!trusted_dir_certs) return; DIGESTMAP_FOREACH(trusted_dir_certs, key, cert_list_t *, cl) { authority_cert_t *newest = NULL; SMARTLIST_FOREACH(cl->certs, authority_cert_t *, cert, if (!newest || (cert->cache_info.published_on > newest->cache_info.published_on)) newest = cert); if (newest) { const time_t newest_published = newest->cache_info.published_on; SMARTLIST_FOREACH_BEGIN(cl->certs, authority_cert_t *, cert) { int expired; time_t cert_published; if (newest == cert) continue; expired = ftime_definitely_after(now, cert->expires); cert_published = cert->cache_info.published_on; /* Store expired certs for 48 hours after a newer arrives; */ if (expired ? (newest_published + DEAD_CERT_LIFETIME < now) : (cert_published + OLD_CERT_LIFETIME < newest_published)) { SMARTLIST_DEL_CURRENT(cl->certs, cert); authority_cert_free(cert); trusted_dir_servers_certs_changed = 1; } } SMARTLIST_FOREACH_END(cert); } } DIGESTMAP_FOREACH_END; #undef OLD_CERT_LIFETIME trusted_dirs_flush_certs_to_disk(); } /** Return the newest v3 authority certificate whose v3 authority identity key * has digest id_digest. Return NULL if no such authority is known, * or it has no certificate. */ authority_cert_t * authority_cert_get_newest_by_id(const char *id_digest) { cert_list_t *cl; authority_cert_t *best = NULL; if (!trusted_dir_certs || !(cl = digestmap_get(trusted_dir_certs, id_digest))) return NULL; SMARTLIST_FOREACH(cl->certs, authority_cert_t *, cert, { if (!best || cert->cache_info.published_on > best->cache_info.published_on) best = cert; }); return best; } /** Return the newest v3 authority certificate whose directory signing key has * digest sk_digest. Return NULL if no such certificate is known. */ authority_cert_t * authority_cert_get_by_sk_digest(const char *sk_digest) { authority_cert_t *c; if (!trusted_dir_certs) return NULL; if ((c = get_my_v3_authority_cert()) && !memcmp(c->signing_key_digest, sk_digest, DIGEST_LEN)) return c; if ((c = get_my_v3_legacy_cert()) && !memcmp(c->signing_key_digest, sk_digest, DIGEST_LEN)) return c; DIGESTMAP_FOREACH(trusted_dir_certs, key, cert_list_t *, cl) { SMARTLIST_FOREACH(cl->certs, authority_cert_t *, cert, { if (!memcmp(cert->signing_key_digest, sk_digest, DIGEST_LEN)) return cert; }); } DIGESTMAP_FOREACH_END; return NULL; } /** Return the v3 authority certificate with signing key matching * sk_digest, for the authority with identity digest id_digest. * Return NULL if no such authority is known. */ authority_cert_t * authority_cert_get_by_digests(const char *id_digest, const char *sk_digest) { cert_list_t *cl; if (!trusted_dir_certs || !(cl = digestmap_get(trusted_dir_certs, id_digest))) return NULL; SMARTLIST_FOREACH(cl->certs, authority_cert_t *, cert, if (!memcmp(cert->signing_key_digest, sk_digest, DIGEST_LEN)) return cert; ); return NULL; } /** Add every known authority_cert_t to certs_out. */ void authority_cert_get_all(smartlist_t *certs_out) { tor_assert(certs_out); if (!trusted_dir_certs) return; DIGESTMAP_FOREACH(trusted_dir_certs, key, cert_list_t *, cl) { SMARTLIST_FOREACH(cl->certs, authority_cert_t *, c, smartlist_add(certs_out, c)); } DIGESTMAP_FOREACH_END; } /** Called when an attempt to download a certificate with the authority with * ID id_digest fails with HTTP response code status: remember * the failure, so we don't try again immediately. */ void authority_cert_dl_failed(const char *id_digest, int status) { cert_list_t *cl; if (!trusted_dir_certs || !(cl = digestmap_get(trusted_dir_certs, id_digest))) return; download_status_failed(&cl->dl_status, status); } /** How many times will we try to fetch a certificate before giving up? */ #define MAX_CERT_DL_FAILURES 8 /** Try to download any v3 authority certificates that we may be missing. If * status is provided, try to get all the ones that were used to sign * status. Additionally, try to have a non-expired certificate for * every V3 authority in trusted_dir_servers. Don't fetch certificates we * already have. **/ void authority_certs_fetch_missing(networkstatus_t *status, time_t now) { digestmap_t *pending; authority_cert_t *cert; smartlist_t *missing_digests; char *resource = NULL; cert_list_t *cl; const int cache = directory_caches_dir_info(get_options()); if (should_delay_dir_fetches(get_options())) return; pending = digestmap_new(); missing_digests = smartlist_create(); list_pending_downloads(pending, DIR_PURPOSE_FETCH_CERTIFICATE, "fp/"); if (status) { SMARTLIST_FOREACH(status->voters, networkstatus_voter_info_t *, voter, { if (tor_digest_is_zero(voter->signing_key_digest)) continue; /* This authority never signed this consensus, so don't * go looking for a cert with key digest 0000000000. */ if (!cache && !trusteddirserver_get_by_v3_auth_digest(voter->identity_digest)) continue; /* We are not a cache, and we don't know this authority.*/ cl = get_cert_list(voter->identity_digest); cert = authority_cert_get_by_digests(voter->identity_digest, voter->signing_key_digest); if (cert) { if (now < cert->expires) download_status_reset(&cl->dl_status); continue; } if (download_status_is_ready(&cl->dl_status, now, MAX_CERT_DL_FAILURES) && !digestmap_get(pending, voter->identity_digest)) { log_notice(LD_DIR, "We're missing a certificate from authority " "with signing key %s: launching request.", hex_str(voter->signing_key_digest, DIGEST_LEN)); smartlist_add(missing_digests, voter->identity_digest); } }); } SMARTLIST_FOREACH(trusted_dir_servers, trusted_dir_server_t *, ds, { int found = 0; if (!(ds->type & V3_AUTHORITY)) continue; if (smartlist_digest_isin(missing_digests, ds->v3_identity_digest)) continue; cl = get_cert_list(ds->v3_identity_digest); SMARTLIST_FOREACH(cl->certs, authority_cert_t *, cert, { if (!ftime_definitely_after(now, cert->expires)) { /* It's not expired, and we weren't looking for something to * verify a consensus with. Call it done. */ download_status_reset(&cl->dl_status); found = 1; break; } }); if (!found && download_status_is_ready(&cl->dl_status, now,MAX_CERT_DL_FAILURES) && !digestmap_get(pending, ds->v3_identity_digest)) { log_notice(LD_DIR, "No current certificate known for authority %s; " "launching request.", ds->nickname); smartlist_add(missing_digests, ds->v3_identity_digest); } }); if (!smartlist_len(missing_digests)) { goto done; } else { smartlist_t *fps = smartlist_create(); smartlist_add(fps, tor_strdup("fp/")); SMARTLIST_FOREACH(missing_digests, const char *, d, { char *fp; if (digestmap_get(pending, d)) continue; fp = tor_malloc(HEX_DIGEST_LEN+2); base16_encode(fp, HEX_DIGEST_LEN+1, d, DIGEST_LEN); fp[HEX_DIGEST_LEN] = '+'; fp[HEX_DIGEST_LEN+1] = '\0'; smartlist_add(fps, fp); }); if (smartlist_len(fps) == 1) { /* we didn't add any: they were all pending */ SMARTLIST_FOREACH(fps, char *, cp, tor_free(cp)); smartlist_free(fps); goto done; } resource = smartlist_join_strings(fps, "", 0, NULL); resource[strlen(resource)-1] = '\0'; SMARTLIST_FOREACH(fps, char *, cp, tor_free(cp)); smartlist_free(fps); } directory_get_from_dirserver(DIR_PURPOSE_FETCH_CERTIFICATE, 0, resource, PDS_RETRY_IF_NO_SERVERS); done: tor_free(resource); smartlist_free(missing_digests); digestmap_free(pending, NULL); } /* Router descriptor storage. * * Routerdescs are stored in a big file, named "cached-descriptors". As new * routerdescs arrive, we append them to a journal file named * "cached-descriptors.new". * * From time to time, we replace "cached-descriptors" with a new file * containing only the live, non-superseded descriptors, and clear * cached-routers.new. * * On startup, we read both files. */ /** Helper: return 1 iff the router log is so big we want to rebuild the * store. */ static int router_should_rebuild_store(desc_store_t *store) { if (store->store_len > (1<<16)) return (store->journal_len > store->store_len / 2 || store->bytes_dropped > store->store_len / 2); else return store->journal_len > (1<<15); } /** Return the desc_store_t in rl that should be used to store * sd. */ static INLINE desc_store_t * desc_get_store(routerlist_t *rl, signed_descriptor_t *sd) { if (sd->is_extrainfo) return &rl->extrainfo_store; else return &rl->desc_store; } /** Add the signed_descriptor_t in desc to the router * journal; change its saved_location to SAVED_IN_JOURNAL and set its * offset appropriately. */ static int signed_desc_append_to_journal(signed_descriptor_t *desc, desc_store_t *store) { char *fname = get_datadir_fname_suffix(store->fname_base, ".new"); const char *body = signed_descriptor_get_body_impl(desc,1); size_t len = desc->signed_descriptor_len + desc->annotations_len; tor_assert(len == strlen(body)); if (append_bytes_to_file(fname, body, len, 1)) { log_warn(LD_FS, "Unable to store router descriptor"); tor_free(fname); return -1; } desc->saved_location = SAVED_IN_JOURNAL; tor_free(fname); desc->saved_offset = store->journal_len; store->journal_len += len; return 0; } /** Sorting helper: return <0, 0, or >0 depending on whether the * signed_descriptor_t* in *a is older, the same age as, or newer than * the signed_descriptor_t* in *b. */ static int _compare_signed_descriptors_by_age(const void **_a, const void **_b) { const signed_descriptor_t *r1 = *_a, *r2 = *_b; return (int)(r1->published_on - r2->published_on); } #define RRS_FORCE 1 #define RRS_DONT_REMOVE_OLD 2 /** If the journal of store is too long, or if RRS_FORCE is set in * flags, then atomically replace the saved router store with the * routers currently in our routerlist, and clear the journal. Unless * RRS_DONT_REMOVE_OLD is set in flags, delete expired routers before * rebuilding the store. Return 0 on success, -1 on failure. */ static int router_rebuild_store(int flags, desc_store_t *store) { smartlist_t *chunk_list = NULL; char *fname = NULL, *fname_tmp = NULL; int r = -1; off_t offset = 0; smartlist_t *signed_descriptors = NULL; int nocache=0; size_t total_expected_len = 0; int had_any; int force = flags & RRS_FORCE; if (!force && !router_should_rebuild_store(store)) return 0; if (!routerlist) return 0; if (store->type == EXTRAINFO_STORE) had_any = !eimap_isempty(routerlist->extra_info_map); else had_any = (smartlist_len(routerlist->routers)+ smartlist_len(routerlist->old_routers))>0; /* Don't save deadweight. */ if (!(flags & RRS_DONT_REMOVE_OLD)) routerlist_remove_old_routers(); log_info(LD_DIR, "Rebuilding %s cache", store->description); fname = get_datadir_fname(store->fname_base); fname_tmp = get_datadir_fname_suffix(store->fname_base, ".tmp"); chunk_list = smartlist_create(); /* We sort the routers by age to enhance locality on disk. */ signed_descriptors = smartlist_create(); if (store->type == EXTRAINFO_STORE) { eimap_iter_t *iter; for (iter = eimap_iter_init(routerlist->extra_info_map); !eimap_iter_done(iter); iter = eimap_iter_next(routerlist->extra_info_map, iter)) { const char *key; extrainfo_t *ei; eimap_iter_get(iter, &key, &ei); smartlist_add(signed_descriptors, &ei->cache_info); } } else { SMARTLIST_FOREACH(routerlist->old_routers, signed_descriptor_t *, sd, smartlist_add(signed_descriptors, sd)); SMARTLIST_FOREACH(routerlist->routers, routerinfo_t *, ri, smartlist_add(signed_descriptors, &ri->cache_info)); } smartlist_sort(signed_descriptors, _compare_signed_descriptors_by_age); /* Now, add the appropriate members to chunk_list */ SMARTLIST_FOREACH(signed_descriptors, signed_descriptor_t *, sd, { sized_chunk_t *c; const char *body = signed_descriptor_get_body_impl(sd, 1); if (!body) { log_warn(LD_BUG, "No descriptor available for router."); goto done; } if (sd->do_not_cache) { ++nocache; continue; } c = tor_malloc(sizeof(sized_chunk_t)); c->bytes = body; c->len = sd->signed_descriptor_len + sd->annotations_len; total_expected_len += c->len; smartlist_add(chunk_list, c); }); if (write_chunks_to_file(fname_tmp, chunk_list, 1)<0) { log_warn(LD_FS, "Error writing router store to disk."); goto done; } /* Our mmap is now invalid. */ if (store->mmap) { tor_munmap_file(store->mmap); store->mmap = NULL; } if (replace_file(fname_tmp, fname)<0) { log_warn(LD_FS, "Error replacing old router store: %s", strerror(errno)); goto done; } errno = 0; store->mmap = tor_mmap_file(fname); if (! store->mmap) { if (errno == ERANGE) { /* empty store.*/ if (total_expected_len) { log_warn(LD_FS, "We wrote some bytes to a new descriptor file at '%s'," " but when we went to mmap it, it was empty!", fname); } else if (had_any) { log_info(LD_FS, "We just removed every descriptor in '%s'. This is " "okay if we're just starting up after a long time. " "Otherwise, it's a bug.", fname); } } else { log_warn(LD_FS, "Unable to mmap new descriptor file at '%s'.",fname); } } log_info(LD_DIR, "Reconstructing pointers into cache"); offset = 0; SMARTLIST_FOREACH(signed_descriptors, signed_descriptor_t *, sd, { if (sd->do_not_cache) continue; sd->saved_location = SAVED_IN_CACHE; if (store->mmap) { tor_free(sd->signed_descriptor_body); // sets it to null sd->saved_offset = offset; } offset += sd->signed_descriptor_len + sd->annotations_len; signed_descriptor_get_body(sd); /* reconstruct and assert */ }); tor_free(fname); fname = get_datadir_fname_suffix(store->fname_base, ".new"); write_str_to_file(fname, "", 1); r = 0; store->store_len = (size_t) offset; store->journal_len = 0; store->bytes_dropped = 0; done: if (signed_descriptors) smartlist_free(signed_descriptors); tor_free(fname); tor_free(fname_tmp); SMARTLIST_FOREACH(chunk_list, sized_chunk_t *, c, tor_free(c)); smartlist_free(chunk_list); return r; } /** Helper: Reload a cache file and its associated journal, setting metadata * appropriately. If extrainfo is true, reload the extrainfo store; * else reload the router descriptor store. */ static int router_reload_router_list_impl(desc_store_t *store) { char *fname = NULL, *altname = NULL, *contents = NULL; struct stat st; int read_from_old_location = 0; int extrainfo = (store->type == EXTRAINFO_STORE); time_t now = time(NULL); store->journal_len = store->store_len = 0; fname = get_datadir_fname(store->fname_base); if (store->fname_alt_base) altname = get_datadir_fname(store->fname_alt_base); if (store->mmap) /* get rid of it first */ tor_munmap_file(store->mmap); store->mmap = NULL; store->mmap = tor_mmap_file(fname); if (!store->mmap && altname && file_status(altname) == FN_FILE) { read_from_old_location = 1; log_notice(LD_DIR, "Couldn't read %s; trying to load routers from old " "location %s.", fname, altname); if ((store->mmap = tor_mmap_file(altname))) read_from_old_location = 1; } if (altname && !read_from_old_location) { remove_file_if_very_old(altname, now); } if (store->mmap) { store->store_len = store->mmap->size; if (extrainfo) router_load_extrainfo_from_string(store->mmap->data, store->mmap->data+store->mmap->size, SAVED_IN_CACHE, NULL, 0); else router_load_routers_from_string(store->mmap->data, store->mmap->data+store->mmap->size, SAVED_IN_CACHE, NULL, 0, NULL); } tor_free(fname); fname = get_datadir_fname_suffix(store->fname_base, ".new"); if (file_status(fname) == FN_FILE) contents = read_file_to_str(fname, RFTS_BIN|RFTS_IGNORE_MISSING, &st); if (read_from_old_location) { tor_free(altname); altname = get_datadir_fname_suffix(store->fname_alt_base, ".new"); if (!contents) contents = read_file_to_str(altname, RFTS_BIN|RFTS_IGNORE_MISSING, &st); else remove_file_if_very_old(altname, now); } if (contents) { if (extrainfo) router_load_extrainfo_from_string(contents, NULL,SAVED_IN_JOURNAL, NULL, 0); else router_load_routers_from_string(contents, NULL, SAVED_IN_JOURNAL, NULL, 0, NULL); store->journal_len = (size_t) st.st_size; tor_free(contents); } tor_free(fname); tor_free(altname); if (store->journal_len || read_from_old_location) { /* Always clear the journal on startup.*/ router_rebuild_store(RRS_FORCE, store); } else if (!extrainfo) { /* Don't cache expired routers. (This is in an else because * router_rebuild_store() also calls remove_old_routers().) */ routerlist_remove_old_routers(); } return 0; } /** Load all cached router descriptors and extra-info documents from the * store. Return 0 on success and -1 on failure. */ int router_reload_router_list(void) { routerlist_t *rl = router_get_routerlist(); if (router_reload_router_list_impl(&rl->desc_store)) return -1; if (router_reload_router_list_impl(&rl->extrainfo_store)) return -1; return 0; } /** Return a smartlist containing a list of trusted_dir_server_t * for all * known trusted dirservers. Callers must not modify the list or its * contents. */ smartlist_t * router_get_trusted_dir_servers(void) { if (!trusted_dir_servers) trusted_dir_servers = smartlist_create(); return trusted_dir_servers; } /** Try to find a running dirserver that supports operations of type. * * If there are no running dirservers in our routerlist and the * PDS_RETRY_IF_NO_SERVERS flag is set, set all the authoritative ones * as running again, and pick one. * * If the PDS_IGNORE_FASCISTFIREWALL flag is set, then include * dirservers that we can't reach. * * If the PDS_ALLOW_SELF flag is not set, then don't include ourself * (if we're a dirserver). * * Don't pick an authority if any non-authority is viable; try to avoid using * servers that have returned 503 recently. */ routerstatus_t * router_pick_directory_server(authority_type_t type, int flags) { routerstatus_t *choice; if (get_options()->PreferTunneledDirConns) flags |= _PDS_PREFER_TUNNELED_DIR_CONNS; if (!routerlist) return NULL; choice = router_pick_directory_server_impl(type, flags); if (choice || !(flags & PDS_RETRY_IF_NO_SERVERS)) return choice; log_info(LD_DIR, "No reachable router entries for dirservers. " "Trying them all again."); /* mark all authdirservers as up again */ mark_all_trusteddirservers_up(); /* try again */ choice = router_pick_directory_server_impl(type, flags); return choice; } /** Try to determine which fraction of v2 and v3 directory requsts aimed at * caches will be sent to us. Set *v2_share_out and * *v3_share_out to the fractions of v2 and v3 protocol shares we * expect to see, respectively. Return 0 on success, negative on failue. */ int router_get_my_share_of_directory_requests(double *v2_share_out, double *v3_share_out) { routerinfo_t *me = router_get_my_routerinfo(); routerstatus_t *rs; const int pds_flags = PDS_ALLOW_SELF|PDS_IGNORE_FASCISTFIREWALL; *v2_share_out = *v3_share_out = 0.0; if (!me) return -1; rs = router_get_consensus_status_by_id(me->cache_info.identity_digest); if (!rs) return -1; /* Calling for side effect */ /* XXXX This is a bit of a kludge */ if (rs->is_v2_dir) { sl_last_total_weighted_bw = 0; router_pick_directory_server(V2_AUTHORITY, pds_flags); if (sl_last_total_weighted_bw != 0) { *v2_share_out = U64_TO_DBL(sl_last_weighted_bw_of_me) / U64_TO_DBL(sl_last_total_weighted_bw); } } if (rs->version_supports_v3_dir) { sl_last_total_weighted_bw = 0; router_pick_directory_server(V3_AUTHORITY, pds_flags); if (sl_last_total_weighted_bw != 0) { *v3_share_out = U64_TO_DBL(sl_last_weighted_bw_of_me) / U64_TO_DBL(sl_last_total_weighted_bw); } } return 0; } /** Return the trusted_dir_server_t for the directory authority whose identity * key hashes to digest, or NULL if no such authority is known. */ trusted_dir_server_t * router_get_trusteddirserver_by_digest(const char *digest) { if (!trusted_dir_servers) return NULL; SMARTLIST_FOREACH(trusted_dir_servers, trusted_dir_server_t *, ds, { if (!memcmp(ds->digest, digest, DIGEST_LEN)) return ds; }); return NULL; } /** Return the trusted_dir_server_t for the directory authority whose identity * key hashes to digest, or NULL if no such authority is known. */ trusted_dir_server_t * trusteddirserver_get_by_v3_auth_digest(const char *digest) { if (!trusted_dir_servers) return NULL; SMARTLIST_FOREACH(trusted_dir_servers, trusted_dir_server_t *, ds, { if (!memcmp(ds->v3_identity_digest, digest, DIGEST_LEN) && (ds->type & V3_AUTHORITY)) return ds; }); return NULL; } /** Try to find a running trusted dirserver. Flags are as for * router_pick_directory_server. */ routerstatus_t * router_pick_trusteddirserver(authority_type_t type, int flags) { routerstatus_t *choice; int busy = 0; if (get_options()->PreferTunneledDirConns) flags |= _PDS_PREFER_TUNNELED_DIR_CONNS; choice = router_pick_trusteddirserver_impl(type, flags, &busy); if (choice || !(flags & PDS_RETRY_IF_NO_SERVERS)) return choice; if (busy) { /* If the reason that we got no server is that servers are "busy", * we must be excluding good servers because we already have serverdesc * fetches with them. Do not mark down servers up because of this. */ tor_assert((flags & PDS_NO_EXISTING_SERVERDESC_FETCH)); return NULL; } log_info(LD_DIR, "No trusted dirservers are reachable. Trying them all again."); mark_all_trusteddirservers_up(); return router_pick_trusteddirserver_impl(type, flags, NULL); } /** How long do we avoid using a directory server after it's given us a 503? */ #define DIR_503_TIMEOUT (60*60) /** Pick a random running valid directory server/mirror from our * routerlist. Arguments are as for router_pick_directory_server(), except * that RETRY_IF_NO_SERVERS is ignored, and: * * If the _PDS_PREFER_TUNNELED_DIR_CONNS flag is set, prefer directory servers * that we can use with BEGINDIR. */ static routerstatus_t * router_pick_directory_server_impl(authority_type_t type, int flags) { routerstatus_t *result; smartlist_t *direct, *tunnel; smartlist_t *trusted_direct, *trusted_tunnel; smartlist_t *overloaded_direct, *overloaded_tunnel; time_t now = time(NULL); const networkstatus_t *consensus = networkstatus_get_latest_consensus(); int requireother = ! (flags & PDS_ALLOW_SELF); int fascistfirewall = ! (flags & PDS_IGNORE_FASCISTFIREWALL); int prefer_tunnel = (flags & _PDS_PREFER_TUNNELED_DIR_CONNS); if (!consensus) return NULL; direct = smartlist_create(); tunnel = smartlist_create(); trusted_direct = smartlist_create(); trusted_tunnel = smartlist_create(); overloaded_direct = smartlist_create(); overloaded_tunnel = smartlist_create(); /* Find all the running dirservers we know about. */ SMARTLIST_FOREACH_BEGIN(consensus->routerstatus_list, routerstatus_t *, status) { int is_trusted; int is_overloaded = status->last_dir_503_at + DIR_503_TIMEOUT > now; tor_addr_t addr; if (!status->is_running || !status->dir_port || !status->is_valid) continue; if (status->is_bad_directory) continue; if (requireother && router_digest_is_me(status->identity_digest)) continue; if (type & V3_AUTHORITY) { if (!(status->version_supports_v3_dir || router_digest_is_trusted_dir_type(status->identity_digest, V3_AUTHORITY))) continue; } is_trusted = router_digest_is_trusted_dir(status->identity_digest); if ((type & V2_AUTHORITY) && !(status->is_v2_dir || is_trusted)) continue; if ((type & EXTRAINFO_CACHE) && !router_supports_extrainfo(status->identity_digest, 0)) continue; /* XXXX IP6 proposal 118 */ tor_addr_from_ipv4h(&addr, status->addr); if (prefer_tunnel && status->version_supports_begindir && (!fascistfirewall || fascist_firewall_allows_address_or(&addr, status->or_port))) smartlist_add(is_trusted ? trusted_tunnel : is_overloaded ? overloaded_tunnel : tunnel, status); else if (!fascistfirewall || fascist_firewall_allows_address_dir(&addr, status->dir_port)) smartlist_add(is_trusted ? trusted_direct : is_overloaded ? overloaded_direct : direct, status); } SMARTLIST_FOREACH_END(status); if (smartlist_len(tunnel)) { result = routerstatus_sl_choose_by_bandwidth(tunnel); } else if (smartlist_len(overloaded_tunnel)) { result = routerstatus_sl_choose_by_bandwidth(overloaded_tunnel); } else if (smartlist_len(trusted_tunnel)) { /* FFFF We don't distinguish between trusteds and overloaded trusteds * yet. Maybe one day we should. */ /* FFFF We also don't load balance over authorities yet. I think this * is a feature, but it could easily be a bug. -RD */ result = smartlist_choose(trusted_tunnel); } else if (smartlist_len(direct)) { result = routerstatus_sl_choose_by_bandwidth(direct); } else if (smartlist_len(overloaded_direct)) { result = routerstatus_sl_choose_by_bandwidth(overloaded_direct); } else { result = smartlist_choose(trusted_direct); } smartlist_free(direct); smartlist_free(tunnel); smartlist_free(trusted_direct); smartlist_free(trusted_tunnel); smartlist_free(overloaded_direct); smartlist_free(overloaded_tunnel); return result; } /** Choose randomly from among the trusted dirservers that are up. Flags * are as for router_pick_directory_server_impl(). */ static routerstatus_t * router_pick_trusteddirserver_impl(authority_type_t type, int flags, int *n_busy_out) { smartlist_t *direct, *tunnel; smartlist_t *overloaded_direct, *overloaded_tunnel; routerinfo_t *me = router_get_my_routerinfo(); routerstatus_t *result; time_t now = time(NULL); const int requireother = ! (flags & PDS_ALLOW_SELF); const int fascistfirewall = ! (flags & PDS_IGNORE_FASCISTFIREWALL); const int prefer_tunnel = (flags & _PDS_PREFER_TUNNELED_DIR_CONNS); const int no_serverdesc_fetching =(flags & PDS_NO_EXISTING_SERVERDESC_FETCH); int n_busy = 0; if (!trusted_dir_servers) return NULL; direct = smartlist_create(); tunnel = smartlist_create(); overloaded_direct = smartlist_create(); overloaded_tunnel = smartlist_create(); SMARTLIST_FOREACH_BEGIN(trusted_dir_servers, trusted_dir_server_t *, d) { int is_overloaded = d->fake_status.last_dir_503_at + DIR_503_TIMEOUT > now; tor_addr_t addr; if (!d->is_running) continue; if ((type & d->type) == 0) continue; if ((type & EXTRAINFO_CACHE) && !router_supports_extrainfo(d->digest, 1)) continue; if (requireother && me && router_digest_is_me(d->digest)) continue; /* XXXX IP6 proposal 118 */ tor_addr_from_ipv4h(&addr, d->addr); if (no_serverdesc_fetching) { if (connection_get_by_type_addr_port_purpose( CONN_TYPE_DIR, &addr, d->dir_port, DIR_PURPOSE_FETCH_SERVERDESC) || connection_get_by_type_addr_port_purpose( CONN_TYPE_DIR, &addr, d->dir_port, DIR_PURPOSE_FETCH_EXTRAINFO)) { //log_debug(LD_DIR, "We have an existing connection to fetch " // "descriptor from %s; delaying",d->description); ++n_busy; continue; } } if (prefer_tunnel && d->or_port && (!fascistfirewall || fascist_firewall_allows_address_or(&addr, d->or_port))) smartlist_add(is_overloaded ? overloaded_tunnel : tunnel, &d->fake_status); else if (!fascistfirewall || fascist_firewall_allows_address_dir(&addr, d->dir_port)) smartlist_add(is_overloaded ? overloaded_direct : direct, &d->fake_status); } SMARTLIST_FOREACH_END(d); if (smartlist_len(tunnel)) { result = smartlist_choose(tunnel); } else if (smartlist_len(overloaded_tunnel)) { result = smartlist_choose(overloaded_tunnel); } else if (smartlist_len(direct)) { result = smartlist_choose(direct); } else { result = smartlist_choose(overloaded_direct); } if (n_busy_out) *n_busy_out = n_busy; smartlist_free(direct); smartlist_free(tunnel); smartlist_free(overloaded_direct); smartlist_free(overloaded_tunnel); return result; } /** Go through and mark the authoritative dirservers as up. */ static void mark_all_trusteddirservers_up(void) { if (routerlist) { SMARTLIST_FOREACH(routerlist->routers, routerinfo_t *, router, if (router_digest_is_trusted_dir(router->cache_info.identity_digest) && router->dir_port > 0) { router->is_running = 1; }); } if (trusted_dir_servers) { SMARTLIST_FOREACH(trusted_dir_servers, trusted_dir_server_t *, dir, { routerstatus_t *rs; dir->is_running = 1; download_status_reset(&dir->v2_ns_dl_status); rs = router_get_consensus_status_by_id(dir->digest); if (rs && !rs->is_running) { rs->is_running = 1; rs->last_dir_503_at = 0; control_event_networkstatus_changed_single(rs); } }); } router_dir_info_changed(); } /** Reset all internal variables used to count failed downloads of network * status objects. */ void router_reset_status_download_failures(void) { mark_all_trusteddirservers_up(); } /** Return true iff router1 and router2 have the same /16 network. */ static INLINE int routers_in_same_network_family(routerinfo_t *r1, routerinfo_t *r2) { return (r1->addr & 0xffff0000) == (r2->addr & 0xffff0000); } /** Look through the routerlist and identify routers that * advertise the same /16 network address as router. * Add each of them to sl. */ static void routerlist_add_network_family(smartlist_t *sl, routerinfo_t *router) { SMARTLIST_FOREACH(routerlist->routers, routerinfo_t *, r, { if (router != r && routers_in_same_network_family(router, r)) smartlist_add(sl, r); }); } /** Add all the family of router to the smartlist sl. * This is used to make sure we don't pick siblings in a single path, * or pick more than one relay from a family for our entry guard list. */ void routerlist_add_family(smartlist_t *sl, routerinfo_t *router) { routerinfo_t *r; config_line_t *cl; or_options_t *options = get_options(); /* First, add any routers with similar network addresses. */ if (options->EnforceDistinctSubnets) routerlist_add_network_family(sl, router); if (router->declared_family) { /* Add every r such that router declares familyness with r, and r * declares familyhood with router. */ SMARTLIST_FOREACH(router->declared_family, const char *, n, { if (!(r = router_get_by_nickname(n, 0))) continue; if (!r->declared_family) continue; SMARTLIST_FOREACH(r->declared_family, const char *, n2, { if (router_nickname_matches(router, n2)) smartlist_add(sl, r); }); }); } /* If the user declared any families locally, honor those too. */ for (cl = options->NodeFamilies; cl; cl = cl->next) { if (router_nickname_is_in_list(router, cl->value)) { add_nickname_list_to_smartlist(sl, cl->value, 0); } } } /** Return true iff r is named by some nickname in lst. */ static INLINE int router_in_nickname_smartlist(smartlist_t *lst, routerinfo_t *r) { if (!lst) return 0; SMARTLIST_FOREACH(lst, const char *, name, if (router_nickname_matches(r, name)) return 1;); return 0; } /** Return true iff r1 and r2 are in the same family, but not the same * router. */ int routers_in_same_family(routerinfo_t *r1, routerinfo_t *r2) { or_options_t *options = get_options(); config_line_t *cl; if (options->EnforceDistinctSubnets && routers_in_same_network_family(r1,r2)) return 1; if (router_in_nickname_smartlist(r1->declared_family, r2) && router_in_nickname_smartlist(r2->declared_family, r1)) return 1; for (cl = options->NodeFamilies; cl; cl = cl->next) { if (router_nickname_is_in_list(r1, cl->value) && router_nickname_is_in_list(r2, cl->value)) return 1; } return 0; } /** Given a (possibly NULL) comma-and-whitespace separated list of nicknames, * see which nicknames in list name routers in our routerlist, and add * the routerinfos for those routers to sl. If must_be_running, * only include routers that we think are running. * Warn if any non-Named routers are specified by nickname. */ void add_nickname_list_to_smartlist(smartlist_t *sl, const char *list, int must_be_running) { routerinfo_t *router; smartlist_t *nickname_list; int have_dir_info = router_have_minimum_dir_info(); if (!list) return; /* nothing to do */ tor_assert(sl); nickname_list = smartlist_create(); if (!warned_nicknames) warned_nicknames = smartlist_create(); smartlist_split_string(nickname_list, list, ",", SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0); SMARTLIST_FOREACH(nickname_list, const char *, nick, { int warned; if (!is_legal_nickname_or_hexdigest(nick)) { log_warn(LD_CONFIG, "Nickname '%s' is misformed; skipping", nick); continue; } router = router_get_by_nickname(nick, 1); warned = smartlist_string_isin(warned_nicknames, nick); if (router) { if (!must_be_running || router->is_running) { smartlist_add(sl,router); } } else if (!router_get_consensus_status_by_nickname(nick,1)) { if (!warned) { log_fn(have_dir_info ? LOG_WARN : LOG_INFO, LD_CONFIG, "Nickname list includes '%s' which isn't a known router.",nick); smartlist_add(warned_nicknames, tor_strdup(nick)); } } }); SMARTLIST_FOREACH(nickname_list, char *, nick, tor_free(nick)); smartlist_free(nickname_list); } /** Return 1 iff any member of the (possibly NULL) comma-separated list * list is an acceptable nickname or hexdigest for router. Else * return 0. */ int router_nickname_is_in_list(routerinfo_t *router, const char *list) { smartlist_t *nickname_list; int v = 0; if (!list) return 0; /* definitely not */ tor_assert(router); nickname_list = smartlist_create(); smartlist_split_string(nickname_list, list, ",", SPLIT_SKIP_SPACE|SPLIT_STRIP_SPACE|SPLIT_IGNORE_BLANK, 0); SMARTLIST_FOREACH(nickname_list, const char *, cp, if (router_nickname_matches(router, cp)) {v=1;break;}); SMARTLIST_FOREACH(nickname_list, char *, cp, tor_free(cp)); smartlist_free(nickname_list); return v; } /** Add every suitable router from our routerlist to sl, so that * we can pick a node for a circuit. */ static void router_add_running_routers_to_smartlist(smartlist_t *sl, int allow_invalid, int need_uptime, int need_capacity, int need_guard) { if (!routerlist) return; SMARTLIST_FOREACH(routerlist->routers, routerinfo_t *, router, { if (router->is_running && router->purpose == ROUTER_PURPOSE_GENERAL && (router->is_valid || allow_invalid) && !router_is_unreliable(router, need_uptime, need_capacity, need_guard)) { /* If it's running, and it's suitable according to the * other flags we had in mind */ smartlist_add(sl, router); } }); } /** Look through the routerlist until we find a router that has my key. Return it. */ routerinfo_t * routerlist_find_my_routerinfo(void) { if (!routerlist) return NULL; SMARTLIST_FOREACH(routerlist->routers, routerinfo_t *, router, { if (router_is_me(router)) return router; }); return NULL; } /** Find a router that's up, that has this IP address, and * that allows exit to this address:port, or return NULL if there * isn't a good one. */ routerinfo_t * router_find_exact_exit_enclave(const char *address, uint16_t port) { uint32_t addr; struct in_addr in; tor_addr_t a; if (!tor_inet_aton(address, &in)) return NULL; /* it's not an IP already */ addr = ntohl(in.s_addr); tor_addr_from_ipv4h(&a, addr); SMARTLIST_FOREACH(routerlist->routers, routerinfo_t *, router, { if (router->addr == addr && router->is_running && compare_tor_addr_to_addr_policy(&a, port, router->exit_policy) == ADDR_POLICY_ACCEPTED) return router; }); return NULL; } /** Return 1 if router is not suitable for these parameters, else 0. * If need_uptime is non-zero, we require a minimum uptime. * If need_capacity is non-zero, we require a minimum advertised * bandwidth. * If need_guard, we require that the router is a possible entry guard. */ int router_is_unreliable(routerinfo_t *router, int need_uptime, int need_capacity, int need_guard) { if (need_uptime && !router->is_stable) return 1; if (need_capacity && !router->is_fast) return 1; if (need_guard && !router->is_possible_guard) return 1; return 0; } /** Return the smaller of the router's configured BandwidthRate * and its advertised capacity. */ uint32_t router_get_advertised_bandwidth(routerinfo_t *router) { if (router->bandwidthcapacity < router->bandwidthrate) return router->bandwidthcapacity; return router->bandwidthrate; } /** Do not weight any declared bandwidth more than this much when picking * routers by bandwidth. */ #define DEFAULT_MAX_BELIEVABLE_BANDWIDTH 10000000 /* 10 MB/sec */ /** Return the smaller of the router's configured BandwidthRate * and its advertised capacity, capped by max-believe-bw. */ uint32_t router_get_advertised_bandwidth_capped(routerinfo_t *router) { uint32_t result = router->bandwidthcapacity; if (result > router->bandwidthrate) result = router->bandwidthrate; if (result > DEFAULT_MAX_BELIEVABLE_BANDWIDTH) result = DEFAULT_MAX_BELIEVABLE_BANDWIDTH; return result; } /** Eventually, the number we return will come from the directory * consensus, so clients can dynamically update to better numbers. * * But for now, or in case there is no consensus available, just return * a sufficient default. */ static uint32_t get_max_believable_bandwidth(void) { return DEFAULT_MAX_BELIEVABLE_BANDWIDTH; } /** Helper function: * choose a random element of smartlist sl, weighted by * the advertised bandwidth of each element. * * If statuses is zero, then sl is a list of * routerinfo_t's. Otherwise it's a list of routerstatus_t's. * * If rule==WEIGHT_FOR_EXIT. we're picking an exit node: consider all * nodes' bandwidth equally regardless of their Exit status, since there may * be some in the list because they exit to obscure ports. If * rule==NO_WEIGHTING, we're picking a non-exit node: weight * exit-node's bandwidth less depending on the smallness of the fraction of * Exit-to-total bandwidth. If rule==WEIGHT_FOR_GUARD, we're picking a * guard node: consider all guard's bandwidth equally. Otherwise, weight * guards proportionally less. */ static void * smartlist_choose_by_bandwidth(smartlist_t *sl, bandwidth_weight_rule_t rule, int statuses) { unsigned int i; routerinfo_t *router; routerstatus_t *status=NULL; int32_t *bandwidths; int is_exit; int is_guard; uint64_t total_nonexit_bw = 0, total_exit_bw = 0, total_bw = 0; uint64_t total_nonguard_bw = 0, total_guard_bw = 0; uint64_t rand_bw, tmp; double exit_weight; double guard_weight; int n_unknown = 0; bitarray_t *exit_bits; bitarray_t *guard_bits; uint32_t max_believable_bw = get_max_believable_bandwidth(); int me_idx = -1; /* Can't choose exit and guard at same time */ tor_assert(rule == NO_WEIGHTING || rule == WEIGHT_FOR_EXIT || rule == WEIGHT_FOR_GUARD); /* First count the total bandwidth weight, and make a list * of each value. <0 means "unknown; no routerinfo." We use the * bits of negative values to remember whether the router was fast (-x)&1 * and whether it was an exit (-x)&2 or guard (-x)&4. Yes, it's a hack. */ bandwidths = tor_malloc(sizeof(int32_t)*smartlist_len(sl)); exit_bits = bitarray_init_zero(smartlist_len(sl)); guard_bits = bitarray_init_zero(smartlist_len(sl)); /* Iterate over all the routerinfo_t or routerstatus_t, and */ for (i = 0; i < (unsigned)smartlist_len(sl); ++i) { /* first, learn what bandwidth we think i has */ int is_known = 1; int32_t flags = 0; uint32_t this_bw = 0; if (statuses) { /* need to extract router info */ status = smartlist_get(sl, i); if (router_digest_is_me(status->identity_digest)) me_idx = i; router = router_get_by_digest(status->identity_digest); is_exit = status->is_exit; is_guard = status->is_possible_guard; if (router) { this_bw = router_get_advertised_bandwidth(router); } else { /* guess */ is_known = 0; flags = status->is_fast ? 1 : 0; flags |= is_exit ? 2 : 0; flags |= is_guard ? 4 : 0; } } else { router = smartlist_get(sl, i); if (router_digest_is_me(router->cache_info.identity_digest)) me_idx = i; is_exit = router->is_exit; is_guard = router->is_possible_guard; this_bw = router_get_advertised_bandwidth(router); } if (is_exit) bitarray_set(exit_bits, i); if (is_guard) bitarray_set(guard_bits, i); /* if they claim something huge, don't believe it */ if (this_bw > max_believable_bw) { char fp[HEX_DIGEST_LEN+1]; base16_encode(fp, sizeof(fp), statuses ? status->identity_digest : router->cache_info.identity_digest, DIGEST_LEN); log_fn(LOG_PROTOCOL_WARN, LD_DIR, "Bandwidth %d for router %s (%s) exceeds allowed max %d, capping", this_bw, router ? router->nickname : "(null)", fp, max_believable_bw); this_bw = max_believable_bw; } if (is_known) { bandwidths[i] = (int32_t) this_bw; // safe since MAX_BELIEVABLE=0) continue; is_exit = ((-bw)&2); is_guard = ((-bw)&4); bandwidths[i] = ((-bw)&1) ? avg_fast : avg_slow; if (is_exit) total_exit_bw += bandwidths[i]; else total_nonexit_bw += bandwidths[i]; if (is_guard) total_guard_bw += bandwidths[i]; else total_nonguard_bw += bandwidths[i]; } } /* If there's no bandwidth at all, pick at random. */ if (!(total_exit_bw+total_nonexit_bw)) { tor_free(bandwidths); tor_free(exit_bits); tor_free(guard_bits); return smartlist_choose(sl); } /* Figure out how to weight exits and guards */ { double all_bw = U64_TO_DBL(total_exit_bw+total_nonexit_bw); double exit_bw = U64_TO_DBL(total_exit_bw); double guard_bw = U64_TO_DBL(total_guard_bw); /* * For detailed derivation of this formula, see * http://archives.seul.org/or/dev/Jul-2007/msg00056.html */ if (rule == WEIGHT_FOR_EXIT) exit_weight = 1.0; else exit_weight = 1.0 - all_bw/(3.0*exit_bw); if (rule == WEIGHT_FOR_GUARD) guard_weight = 1.0; else guard_weight = 1.0 - all_bw/(3.0*guard_bw); if (exit_weight <= 0.0) exit_weight = 0.0; if (guard_weight <= 0.0) guard_weight = 0.0; total_bw = 0; sl_last_weighted_bw_of_me = 0; for (i=0; i < (unsigned)smartlist_len(sl); i++) { uint64_t bw; is_exit = bitarray_is_set(exit_bits, i); is_guard = bitarray_is_set(guard_bits, i); if (is_exit && is_guard) bw = ((uint64_t)(bandwidths[i] * exit_weight * guard_weight)); else if (is_guard) bw = ((uint64_t)(bandwidths[i] * guard_weight)); else if (is_exit) bw = ((uint64_t)(bandwidths[i] * exit_weight)); else bw = bandwidths[i]; total_bw += bw; if (i == (unsigned) me_idx) sl_last_weighted_bw_of_me = bw; } } /* XXXX022 this is a kludge to expose these values. */ sl_last_total_weighted_bw = total_bw; log_debug(LD_CIRC, "Total weighted bw = "U64_FORMAT ", exit bw = "U64_FORMAT ", nonexit bw = "U64_FORMAT", exit weight = %lf " "(for exit == %d)" ", guard bw = "U64_FORMAT ", nonguard bw = "U64_FORMAT", guard weight = %lf " "(for guard == %d)", U64_PRINTF_ARG(total_bw), U64_PRINTF_ARG(total_exit_bw), U64_PRINTF_ARG(total_nonexit_bw), exit_weight, (int)(rule == WEIGHT_FOR_EXIT), U64_PRINTF_ARG(total_guard_bw), U64_PRINTF_ARG(total_nonguard_bw), guard_weight, (int)(rule == WEIGHT_FOR_GUARD)); /* Almost done: choose a random value from the bandwidth weights. */ rand_bw = crypto_rand_uint64(total_bw); /* Last, count through sl until we get to the element we picked */ tmp = 0; for (i=0; i < (unsigned)smartlist_len(sl); i++) { is_exit = bitarray_is_set(exit_bits, i); is_guard = bitarray_is_set(guard_bits, i); /* Weights can be 0 if not counting guards/exits */ if (is_exit && is_guard) tmp += ((uint64_t)(bandwidths[i] * exit_weight * guard_weight)); else if (is_guard) tmp += ((uint64_t)(bandwidths[i] * guard_weight)); else if (is_exit) tmp += ((uint64_t)(bandwidths[i] * exit_weight)); else tmp += bandwidths[i]; if (tmp >= rand_bw) break; } if (i == (unsigned)smartlist_len(sl)) { /* This was once possible due to round-off error, but shouldn't be able * to occur any longer. */ tor_fragile_assert(); --i; log_warn(LD_BUG, "Round-off error in computing bandwidth had an effect on " " which router we chose. Please tell the developers. " U64_FORMAT " " U64_FORMAT " " U64_FORMAT, U64_PRINTF_ARG(tmp), U64_PRINTF_ARG(rand_bw), U64_PRINTF_ARG(total_bw)); } tor_free(bandwidths); tor_free(exit_bits); tor_free(guard_bits); return smartlist_get(sl, i); } /** Choose a random element of router list sl, weighted by * the advertised bandwidth of each router. */ routerinfo_t * routerlist_sl_choose_by_bandwidth(smartlist_t *sl, bandwidth_weight_rule_t rule) { return smartlist_choose_by_bandwidth(sl, rule, 0); } /** Choose a random element of status list sl, weighted by * the advertised bandwidth of each status. */ routerstatus_t * routerstatus_sl_choose_by_bandwidth(smartlist_t *sl) { /* We are choosing neither exit nor guard here. Weight accordingly. */ return smartlist_choose_by_bandwidth(sl, NO_WEIGHTING, 1); } /** Return a random running router from the routerlist. If any node * named in preferred is available, pick one of those. Never * pick a node whose routerinfo is in * excludedsmartlist, or whose routerinfo matches excludedset, * even if they are the only nodes * available. If CRN_STRICT_PREFERRED is set in flags, never pick * any node besides those in preferred. * If CRN_NEED_UPTIME is set in flags and any router has more than * a minimum uptime, return one of those. * If CRN_NEED_CAPACITY is set in flags, weight your choice by the * advertised capacity of each router. * If CRN_ALLOW_INVALID is not set in flags, consider only Valid * routers. * If CRN_NEED_GUARD is set in flags, consider only Guard routers. * If CRN_WEIGHT_AS_EXIT is set in flags, we weight bandwidths as if * picking an exit node, otherwise we weight bandwidths for picking a relay * node (that is, possibly discounting exit nodes). */ routerinfo_t * router_choose_random_node(const char *preferred, smartlist_t *excludedsmartlist, routerset_t *excludedset, router_crn_flags_t flags) { const int need_uptime = (flags & CRN_NEED_UPTIME) != 0; const int need_capacity = (flags & CRN_NEED_CAPACITY) != 0; const int need_guard = (flags & CRN_NEED_GUARD) != 0; const int allow_invalid = (flags & CRN_ALLOW_INVALID) != 0; const int strict = (flags & CRN_STRICT_PREFERRED) != 0; const int weight_for_exit = (flags & CRN_WEIGHT_AS_EXIT) != 0; smartlist_t *sl, *excludednodes; routerinfo_t *choice = NULL, *r; bandwidth_weight_rule_t rule; tor_assert(!(weight_for_exit && need_guard)); rule = weight_for_exit ? WEIGHT_FOR_EXIT : (need_guard ? WEIGHT_FOR_GUARD : NO_WEIGHTING); excludednodes = smartlist_create(); /* Exclude relays that allow single hop exit circuits, if the user * wants to (such relays might be risky) */ if (get_options()->ExcludeSingleHopRelays) { routerlist_t *rl = router_get_routerlist(); SMARTLIST_FOREACH(rl->routers, routerinfo_t *, r, if (r->allow_single_hop_exits) { smartlist_add(excludednodes, r); }); } if ((r = routerlist_find_my_routerinfo())) { smartlist_add(excludednodes, r); routerlist_add_family(excludednodes, r); } /* Try the preferred nodes first. Ignore need_uptime and need_capacity * and need_guard, since the user explicitly asked for these nodes. */ if (preferred) { sl = smartlist_create(); add_nickname_list_to_smartlist(sl,preferred,1); smartlist_subtract(sl,excludednodes); if (excludedsmartlist) smartlist_subtract(sl,excludedsmartlist); if (excludedset) routerset_subtract_routers(sl,excludedset); choice = smartlist_choose(sl); smartlist_free(sl); } if (!choice && !strict) { /* Then give up on our preferred choices: any node * will do that has the required attributes. */ sl = smartlist_create(); router_add_running_routers_to_smartlist(sl, allow_invalid, need_uptime, need_capacity, need_guard); smartlist_subtract(sl,excludednodes); if (excludedsmartlist) smartlist_subtract(sl,excludedsmartlist); if (excludedset) routerset_subtract_routers(sl,excludedset); if (need_capacity || need_guard) choice = routerlist_sl_choose_by_bandwidth(sl, rule); else choice = smartlist_choose(sl); smartlist_free(sl); if (!choice && (need_uptime || need_capacity || need_guard)) { /* try once more -- recurse but with fewer restrictions. */ log_info(LD_CIRC, "We couldn't find any live%s%s%s routers; falling back " "to list of all routers.", need_capacity?", fast":"", need_uptime?", stable":"", need_guard?", guard":""); flags &= ~ (CRN_NEED_UPTIME|CRN_NEED_CAPACITY|CRN_NEED_GUARD); choice = router_choose_random_node( NULL, excludedsmartlist, excludedset, flags); } } smartlist_free(excludednodes); if (!choice) { if (strict) { log_warn(LD_CIRC, "All preferred nodes were down when trying to choose " "node, and the Strict[...]Nodes option is set. Failing."); } else { log_warn(LD_CIRC, "No available nodes when trying to choose node. Failing."); } } return choice; } /** Helper: Return true iff the identity_digest and nickname * combination of a router, encoded in hexadecimal, matches hexdigest * (which is optionally prefixed with a single dollar sign). Return false if * hexdigest is malformed, or it doesn't match. */ static INLINE int hex_digest_matches(const char *hexdigest, const char *identity_digest, const char *nickname, int is_named) { char digest[DIGEST_LEN]; size_t len; tor_assert(hexdigest); if (hexdigest[0] == '$') ++hexdigest; len = strlen(hexdigest); if (len < HEX_DIGEST_LEN) return 0; else if (len > HEX_DIGEST_LEN && (hexdigest[HEX_DIGEST_LEN] == '=' || hexdigest[HEX_DIGEST_LEN] == '~')) { if (strcasecmp(hexdigest+HEX_DIGEST_LEN+1, nickname)) return 0; if (hexdigest[HEX_DIGEST_LEN] == '=' && !is_named) return 0; } if (base16_decode(digest, DIGEST_LEN, hexdigest, HEX_DIGEST_LEN)<0) return 0; return (!memcmp(digest, identity_digest, DIGEST_LEN)); } /** Return true iff the digest of router's identity key, * encoded in hexadecimal, matches hexdigest (which is * optionally prefixed with a single dollar sign). Return false if * hexdigest is malformed, or it doesn't match. */ static INLINE int router_hex_digest_matches(routerinfo_t *router, const char *hexdigest) { return hex_digest_matches(hexdigest, router->cache_info.identity_digest, router->nickname, router->is_named); } /** Return true if router's nickname matches nickname * (case-insensitive), or if router's identity key digest * matches a hexadecimal value stored in nickname. Return * false otherwise. */ static int router_nickname_matches(routerinfo_t *router, const char *nickname) { if (nickname[0]!='$' && !strcasecmp(router->nickname, nickname)) return 1; return router_hex_digest_matches(router, nickname); } /** Return the router in our routerlist whose (case-insensitive) * nickname or (case-sensitive) hexadecimal key digest is * nickname. Return NULL if no such router is known. */ routerinfo_t * router_get_by_nickname(const char *nickname, int warn_if_unnamed) { int maybedigest; char digest[DIGEST_LEN]; routerinfo_t *best_match=NULL; int n_matches = 0; const char *named_digest = NULL; tor_assert(nickname); if (!routerlist) return NULL; if (nickname[0] == '$') return router_get_by_hexdigest(nickname); if (!strcasecmp(nickname, UNNAMED_ROUTER_NICKNAME)) return NULL; if (server_mode(get_options()) && !strcasecmp(nickname, get_options()->Nickname)) return router_get_my_routerinfo(); maybedigest = (strlen(nickname) >= HEX_DIGEST_LEN) && (base16_decode(digest,DIGEST_LEN,nickname,HEX_DIGEST_LEN) == 0); if ((named_digest = networkstatus_get_router_digest_by_nickname(nickname))) { return rimap_get(routerlist->identity_map, named_digest); } if (networkstatus_nickname_is_unnamed(nickname)) return NULL; /* If we reach this point, there's no canonical value for the nickname. */ SMARTLIST_FOREACH(routerlist->routers, routerinfo_t *, router, { if (!strcasecmp(router->nickname, nickname)) { ++n_matches; if (n_matches <= 1 || router->is_running) best_match = router; } else if (maybedigest && !memcmp(digest, router->cache_info.identity_digest, DIGEST_LEN) ) { if (router_hex_digest_matches(router, nickname)) return router; /* If we reach this point, we have a ID=name syntax that matches the * identity but not the name. That isn't an acceptable match. */ } }); if (best_match) { if (warn_if_unnamed && n_matches > 1) { smartlist_t *fps = smartlist_create(); int any_unwarned = 0; SMARTLIST_FOREACH(routerlist->routers, routerinfo_t *, router, { routerstatus_t *rs; char *desc; size_t dlen; char fp[HEX_DIGEST_LEN+1]; if (strcasecmp(router->nickname, nickname)) continue; rs = router_get_consensus_status_by_id( router->cache_info.identity_digest); if (rs && !rs->name_lookup_warned) { rs->name_lookup_warned = 1; any_unwarned = 1; } base16_encode(fp, sizeof(fp), router->cache_info.identity_digest, DIGEST_LEN); dlen = 32 + HEX_DIGEST_LEN + strlen(router->address); desc = tor_malloc(dlen); tor_snprintf(desc, dlen, "\"$%s\" for the one at %s:%d", fp, router->address, router->or_port); smartlist_add(fps, desc); }); if (any_unwarned) { char *alternatives = smartlist_join_strings(fps, "; ",0,NULL); log_warn(LD_CONFIG, "There are multiple matches for the nickname \"%s\"," " but none is listed as named by the directory authorities. " "Choosing one arbitrarily. If you meant one in particular, " "you should say %s.", nickname, alternatives); tor_free(alternatives); } SMARTLIST_FOREACH(fps, char *, cp, tor_free(cp)); smartlist_free(fps); } else if (warn_if_unnamed) { routerstatus_t *rs = router_get_consensus_status_by_id( best_match->cache_info.identity_digest); if (rs && !rs->name_lookup_warned) { char fp[HEX_DIGEST_LEN+1]; base16_encode(fp, sizeof(fp), best_match->cache_info.identity_digest, DIGEST_LEN); log_warn(LD_CONFIG, "You specified a server \"%s\" by name, but this " "name is not registered, so it could be used by any server, " "not just the one you meant. " "To make sure you get the same server in the future, refer to " "it by key, as \"$%s\".", nickname, fp); rs->name_lookup_warned = 1; } } return best_match; } return NULL; } /** Try to find a routerinfo for digest. If we don't have one, * return 1. If we do, ask tor_version_as_new_as() for the answer. */ int router_digest_version_as_new_as(const char *digest, const char *cutoff) { routerinfo_t *router = router_get_by_digest(digest); if (!router) return 1; return tor_version_as_new_as(router->platform, cutoff); } /** Return true iff digest is the digest of the identity key of a * trusted directory matching at least one bit of type. If type * is zero, any authority is okay. */ int router_digest_is_trusted_dir_type(const char *digest, authority_type_t type) { if (!trusted_dir_servers) return 0; if (authdir_mode(get_options()) && router_digest_is_me(digest)) return 1; SMARTLIST_FOREACH(trusted_dir_servers, trusted_dir_server_t *, ent, if (!memcmp(digest, ent->digest, DIGEST_LEN)) { return (!type) || ((type & ent->type) != 0); }); return 0; } /** Return true iff addr is the address of one of our trusted * directory authorities. */ int router_addr_is_trusted_dir(uint32_t addr) { if (!trusted_dir_servers) return 0; SMARTLIST_FOREACH(trusted_dir_servers, trusted_dir_server_t *, ent, if (ent->addr == addr) return 1; ); return 0; } /** If hexdigest is correctly formed, base16_decode it into * digest, which must have DIGEST_LEN space in it. * Return 0 on success, -1 on failure. */ int hexdigest_to_digest(const char *hexdigest, char *digest) { if (hexdigest[0]=='$') ++hexdigest; if (strlen(hexdigest) < HEX_DIGEST_LEN || base16_decode(digest,DIGEST_LEN,hexdigest,HEX_DIGEST_LEN) < 0) return -1; return 0; } /** Return the router in our routerlist whose hexadecimal key digest * is hexdigest. Return NULL if no such router is known. */ routerinfo_t * router_get_by_hexdigest(const char *hexdigest) { char digest[DIGEST_LEN]; size_t len; routerinfo_t *ri; tor_assert(hexdigest); if (!routerlist) return NULL; if (hexdigest[0]=='$') ++hexdigest; len = strlen(hexdigest); if (hexdigest_to_digest(hexdigest, digest) < 0) return NULL; ri = router_get_by_digest(digest); if (ri && len > HEX_DIGEST_LEN) { if (hexdigest[HEX_DIGEST_LEN] == '=') { if (strcasecmp(ri->nickname, hexdigest+HEX_DIGEST_LEN+1) || !ri->is_named) return NULL; } else if (hexdigest[HEX_DIGEST_LEN] == '~') { if (strcasecmp(ri->nickname, hexdigest+HEX_DIGEST_LEN+1)) return NULL; } else { return NULL; } } return ri; } /** Return the router in our routerlist whose 20-byte key digest * is digest. Return NULL if no such router is known. */ routerinfo_t * router_get_by_digest(const char *digest) { tor_assert(digest); if (!routerlist) return NULL; // routerlist_assert_ok(routerlist); return rimap_get(routerlist->identity_map, digest); } /** Return the router in our routerlist whose 20-byte descriptor * is digest. Return NULL if no such router is known. */ signed_descriptor_t * router_get_by_descriptor_digest(const char *digest) { tor_assert(digest); if (!routerlist) return NULL; return sdmap_get(routerlist->desc_digest_map, digest); } /** Return the signed descriptor for the router in our routerlist whose * 20-byte extra-info digest is digest. Return NULL if no such router * is known. */ signed_descriptor_t * router_get_by_extrainfo_digest(const char *digest) { tor_assert(digest); if (!routerlist) return NULL; return sdmap_get(routerlist->desc_by_eid_map, digest); } /** Return the signed descriptor for the extrainfo_t in our routerlist whose * extra-info-digest is digest. Return NULL if no such extra-info * document is known. */ signed_descriptor_t * extrainfo_get_by_descriptor_digest(const char *digest) { extrainfo_t *ei; tor_assert(digest); if (!routerlist) return NULL; ei = eimap_get(routerlist->extra_info_map, digest); return ei ? &ei->cache_info : NULL; } /** Return a pointer to the signed textual representation of a descriptor. * The returned string is not guaranteed to be NUL-terminated: the string's * length will be in desc-\>signed_descriptor_len. * * If with_annotations is set, the returned string will include * the annotations * (if any) preceding the descriptor. This will increase the length of the * string by desc-\>annotations_len. * * The caller must not free the string returned. */ static const char * signed_descriptor_get_body_impl(signed_descriptor_t *desc, int with_annotations) { const char *r = NULL; size_t len = desc->signed_descriptor_len; off_t offset = desc->saved_offset; if (with_annotations) len += desc->annotations_len; else offset += desc->annotations_len; tor_assert(len > 32); if (desc->saved_location == SAVED_IN_CACHE && routerlist) { desc_store_t *store = desc_get_store(router_get_routerlist(), desc); if (store && store->mmap) { tor_assert(desc->saved_offset + len <= store->mmap->size); r = store->mmap->data + offset; } else if (store) { log_err(LD_DIR, "We couldn't read a descriptor that is supposedly " "mmaped in our cache. Is another process running in our data " "directory? Exiting."); exit(1); } } if (!r) /* no mmap, or not in cache. */ r = desc->signed_descriptor_body + (with_annotations ? 0 : desc->annotations_len); tor_assert(r); if (!with_annotations) { if (memcmp("router ", r, 7) && memcmp("extra-info ", r, 11)) { char *cp = tor_strndup(r, 64); log_err(LD_DIR, "descriptor at %p begins with unexpected string %s. " "Is another process running in our data directory? Exiting.", desc, escaped(cp)); exit(1); } } return r; } /** Return a pointer to the signed textual representation of a descriptor. * The returned string is not guaranteed to be NUL-terminated: the string's * length will be in desc-\>signed_descriptor_len. * * The caller must not free the string returned. */ const char * signed_descriptor_get_body(signed_descriptor_t *desc) { return signed_descriptor_get_body_impl(desc, 0); } /** As signed_descriptor_get_body(), but points to the beginning of the * annotations section rather than the beginning of the descriptor. */ const char * signed_descriptor_get_annotations(signed_descriptor_t *desc) { return signed_descriptor_get_body_impl(desc, 1); } /** Return the current list of all known routers. */ routerlist_t * router_get_routerlist(void) { if (PREDICT_UNLIKELY(!routerlist)) { routerlist = tor_malloc_zero(sizeof(routerlist_t)); routerlist->routers = smartlist_create(); routerlist->old_routers = smartlist_create(); routerlist->identity_map = rimap_new(); routerlist->desc_digest_map = sdmap_new(); routerlist->desc_by_eid_map = sdmap_new(); routerlist->extra_info_map = eimap_new(); routerlist->desc_store.fname_base = "cached-descriptors"; routerlist->desc_store.fname_alt_base = "cached-routers"; routerlist->extrainfo_store.fname_base = "cached-extrainfo"; routerlist->desc_store.type = ROUTER_STORE; routerlist->extrainfo_store.type = EXTRAINFO_STORE; routerlist->desc_store.description = "router descriptors"; routerlist->extrainfo_store.description = "extra-info documents"; } return routerlist; } /** Free all storage held by router. */ void routerinfo_free(routerinfo_t *router) { if (!router) return; tor_free(router->cache_info.signed_descriptor_body); tor_free(router->address); tor_free(router->nickname); tor_free(router->platform); tor_free(router->contact_info); if (router->onion_pkey) crypto_free_pk_env(router->onion_pkey); if (router->identity_pkey) crypto_free_pk_env(router->identity_pkey); if (router->declared_family) { SMARTLIST_FOREACH(router->declared_family, char *, s, tor_free(s)); smartlist_free(router->declared_family); } addr_policy_list_free(router->exit_policy); /* XXXX Remove if this turns out to affect performance. */ memset(router, 77, sizeof(routerinfo_t)); tor_free(router); } /** Release all storage held by extrainfo */ void extrainfo_free(extrainfo_t *extrainfo) { if (!extrainfo) return; tor_free(extrainfo->cache_info.signed_descriptor_body); tor_free(extrainfo->pending_sig); /* XXXX remove this if it turns out to slow us down. */ memset(extrainfo, 88, sizeof(extrainfo_t)); /* debug bad memory usage */ tor_free(extrainfo); } /** Release storage held by sd. */ static void signed_descriptor_free(signed_descriptor_t *sd) { tor_free(sd->signed_descriptor_body); /* XXXX remove this once more bugs go away. */ memset(sd, 99, sizeof(signed_descriptor_t)); /* Debug bad mem usage */ tor_free(sd); } /** Extract a signed_descriptor_t from a routerinfo, and free the routerinfo. */ static signed_descriptor_t * signed_descriptor_from_routerinfo(routerinfo_t *ri) { signed_descriptor_t *sd = tor_malloc_zero(sizeof(signed_descriptor_t)); memcpy(sd, &(ri->cache_info), sizeof(signed_descriptor_t)); sd->routerlist_index = -1; ri->cache_info.signed_descriptor_body = NULL; routerinfo_free(ri); return sd; } /** Helper: free the storage held by the extrainfo_t in e. */ static void _extrainfo_free(void *e) { extrainfo_free(e); } /** Free all storage held by a routerlist rl. */ void routerlist_free(routerlist_t *rl) { tor_assert(rl); rimap_free(rl->identity_map, NULL); sdmap_free(rl->desc_digest_map, NULL); sdmap_free(rl->desc_by_eid_map, NULL); eimap_free(rl->extra_info_map, _extrainfo_free); SMARTLIST_FOREACH(rl->routers, routerinfo_t *, r, routerinfo_free(r)); SMARTLIST_FOREACH(rl->old_routers, signed_descriptor_t *, sd, signed_descriptor_free(sd)); smartlist_free(rl->routers); smartlist_free(rl->old_routers); if (routerlist->desc_store.mmap) tor_munmap_file(routerlist->desc_store.mmap); if (routerlist->extrainfo_store.mmap) tor_munmap_file(routerlist->extrainfo_store.mmap); tor_free(rl); router_dir_info_changed(); } /** Log information about how much memory is being used for routerlist, * at log level severity. */ void dump_routerlist_mem_usage(int severity) { uint64_t livedescs = 0; uint64_t olddescs = 0; if (!routerlist) return; SMARTLIST_FOREACH(routerlist->routers, routerinfo_t *, r, livedescs += r->cache_info.signed_descriptor_len); SMARTLIST_FOREACH(routerlist->old_routers, signed_descriptor_t *, sd, olddescs += sd->signed_descriptor_len); log(severity, LD_DIR, "In %d live descriptors: "U64_FORMAT" bytes. " "In %d old descriptors: "U64_FORMAT" bytes.", smartlist_len(routerlist->routers), U64_PRINTF_ARG(livedescs), smartlist_len(routerlist->old_routers), U64_PRINTF_ARG(olddescs)); #if 0 { const smartlist_t *networkstatus_v2_list = networkstatus_get_v2_list(); networkstatus_t *consensus = networkstatus_get_latest_consensus(); log(severity, LD_DIR, "Now let's look through old_descriptors!"); SMARTLIST_FOREACH(routerlist->old_routers, signed_descriptor_t *, sd, { int in_v2 = 0; int in_v3 = 0; char published[ISO_TIME_LEN+1]; char last_valid_until[ISO_TIME_LEN+1]; char last_served_at[ISO_TIME_LEN+1]; char id[HEX_DIGEST_LEN+1]; routerstatus_t *rs; format_iso_time(published, sd->published_on); format_iso_time(last_valid_until, sd->last_listed_as_valid_until); format_iso_time(last_served_at, sd->last_served_at); base16_encode(id, sizeof(id), sd->identity_digest, DIGEST_LEN); SMARTLIST_FOREACH(networkstatus_v2_list, networkstatus_v2_t *, ns, { rs = networkstatus_v2_find_entry(ns, sd->identity_digest); if (rs && !memcmp(rs->descriptor_digest, sd->signed_descriptor_digest, DIGEST_LEN)) { in_v2 = 1; break; } }); if (consensus) { rs = networkstatus_vote_find_entry(consensus, sd->identity_digest); if (rs && !memcmp(rs->descriptor_digest, sd->signed_descriptor_digest, DIGEST_LEN)) in_v3 = 1; } log(severity, LD_DIR, "Old descriptor for %s (published %s) %sin v2 ns, %sin v3 " "consensus. Last valid until %s; last served at %s.", id, published, in_v2 ? "" : "not ", in_v3 ? "" : "not ", last_valid_until, last_served_at); }); } #endif } /** Debugging helper: If idx is nonnegative, assert that ri is * in sl at position idx. Otherwise, search sl for * ri. Return the index of ri in sl, or -1 if ri * is not in sl. */ static INLINE int _routerlist_find_elt(smartlist_t *sl, void *ri, int idx) { if (idx < 0) { idx = -1; SMARTLIST_FOREACH(sl, routerinfo_t *, r, if (r == ri) { idx = r_sl_idx; break; }); } else { tor_assert(idx < smartlist_len(sl)); tor_assert(smartlist_get(sl, idx) == ri); }; return idx; } /** Insert an item ri into the routerlist rl, updating indices * as needed. There must be no previous member of rl with the same * identity digest as ri: If there is, call routerlist_replace * instead. */ static void routerlist_insert(routerlist_t *rl, routerinfo_t *ri) { routerinfo_t *ri_old; { /* XXXX Remove if this slows us down. */ routerinfo_t *ri_generated = router_get_my_routerinfo(); tor_assert(ri_generated != ri); } tor_assert(ri->cache_info.routerlist_index == -1); ri_old = rimap_set(rl->identity_map, ri->cache_info.identity_digest, ri); tor_assert(!ri_old); sdmap_set(rl->desc_digest_map, ri->cache_info.signed_descriptor_digest, &(ri->cache_info)); if (!tor_digest_is_zero(ri->cache_info.extra_info_digest)) sdmap_set(rl->desc_by_eid_map, ri->cache_info.extra_info_digest, &ri->cache_info); smartlist_add(rl->routers, ri); ri->cache_info.routerlist_index = smartlist_len(rl->routers) - 1; router_dir_info_changed(); #ifdef DEBUG_ROUTERLIST routerlist_assert_ok(rl); #endif } /** Adds the extrainfo_t ei to the routerlist rl, if there is a * corresponding router in rl-\>routers or rl-\>old_routers. Return true iff * we actually inserted ei. Free ei if it isn't inserted. */ static int extrainfo_insert(routerlist_t *rl, extrainfo_t *ei) { int r = 0; routerinfo_t *ri = rimap_get(rl->identity_map, ei->cache_info.identity_digest); signed_descriptor_t *sd = sdmap_get(rl->desc_by_eid_map, ei->cache_info.signed_descriptor_digest); extrainfo_t *ei_tmp; { /* XXXX remove this code if it slows us down. */ extrainfo_t *ei_generated = router_get_my_extrainfo(); tor_assert(ei_generated != ei); } if (!ri) { /* This router is unknown; we can't even verify the signature. Give up.*/ goto done; } if (routerinfo_incompatible_with_extrainfo(ri, ei, sd, NULL)) { goto done; } /* Okay, if we make it here, we definitely have a router corresponding to * this extrainfo. */ ei_tmp = eimap_set(rl->extra_info_map, ei->cache_info.signed_descriptor_digest, ei); r = 1; if (ei_tmp) { rl->extrainfo_store.bytes_dropped += ei_tmp->cache_info.signed_descriptor_len; extrainfo_free(ei_tmp); } done: if (r == 0) extrainfo_free(ei); #ifdef DEBUG_ROUTERLIST routerlist_assert_ok(rl); #endif return r; } #define should_cache_old_descriptors() \ directory_caches_dir_info(get_options()) /** If we're a directory cache and routerlist rl doesn't have * a copy of router ri yet, add it to the list of old (not * recommended but still served) descriptors. Else free it. */ static void routerlist_insert_old(routerlist_t *rl, routerinfo_t *ri) { { /* XXXX remove this code if it slows us down. */ routerinfo_t *ri_generated = router_get_my_routerinfo(); tor_assert(ri_generated != ri); } tor_assert(ri->cache_info.routerlist_index == -1); if (should_cache_old_descriptors() && ri->purpose == ROUTER_PURPOSE_GENERAL && !sdmap_get(rl->desc_digest_map, ri->cache_info.signed_descriptor_digest)) { signed_descriptor_t *sd = signed_descriptor_from_routerinfo(ri); sdmap_set(rl->desc_digest_map, sd->signed_descriptor_digest, sd); smartlist_add(rl->old_routers, sd); sd->routerlist_index = smartlist_len(rl->old_routers)-1; if (!tor_digest_is_zero(sd->extra_info_digest)) sdmap_set(rl->desc_by_eid_map, sd->extra_info_digest, sd); } else { routerinfo_free(ri); } #ifdef DEBUG_ROUTERLIST routerlist_assert_ok(rl); #endif } /** Remove an item ri from the routerlist rl, updating indices * as needed. If idx is nonnegative and smartlist_get(rl->routers, * idx) == ri, we don't need to do a linear search over the list to decide * which to remove. We fill the gap in rl->routers with a later element in * the list, if any exists. ri is freed. * * If make_old is true, instead of deleting the router, we try adding * it to rl->old_routers. */ void routerlist_remove(routerlist_t *rl, routerinfo_t *ri, int make_old) { routerinfo_t *ri_tmp; extrainfo_t *ei_tmp; int idx = ri->cache_info.routerlist_index; tor_assert(0 <= idx && idx < smartlist_len(rl->routers)); tor_assert(smartlist_get(rl->routers, idx) == ri); ri->cache_info.routerlist_index = -1; smartlist_del(rl->routers, idx); if (idx < smartlist_len(rl->routers)) { routerinfo_t *r = smartlist_get(rl->routers, idx); r->cache_info.routerlist_index = idx; } ri_tmp = rimap_remove(rl->identity_map, ri->cache_info.identity_digest); router_dir_info_changed(); tor_assert(ri_tmp == ri); if (make_old && should_cache_old_descriptors() && ri->purpose == ROUTER_PURPOSE_GENERAL) { signed_descriptor_t *sd; sd = signed_descriptor_from_routerinfo(ri); smartlist_add(rl->old_routers, sd); sd->routerlist_index = smartlist_len(rl->old_routers)-1; sdmap_set(rl->desc_digest_map, sd->signed_descriptor_digest, sd); if (!tor_digest_is_zero(sd->extra_info_digest)) sdmap_set(rl->desc_by_eid_map, sd->extra_info_digest, sd); } else { signed_descriptor_t *sd_tmp; sd_tmp = sdmap_remove(rl->desc_digest_map, ri->cache_info.signed_descriptor_digest); tor_assert(sd_tmp == &(ri->cache_info)); rl->desc_store.bytes_dropped += ri->cache_info.signed_descriptor_len; ei_tmp = eimap_remove(rl->extra_info_map, ri->cache_info.extra_info_digest); if (ei_tmp) { rl->extrainfo_store.bytes_dropped += ei_tmp->cache_info.signed_descriptor_len; extrainfo_free(ei_tmp); } if (!tor_digest_is_zero(ri->cache_info.extra_info_digest)) sdmap_remove(rl->desc_by_eid_map, ri->cache_info.extra_info_digest); routerinfo_free(ri); } #ifdef DEBUG_ROUTERLIST routerlist_assert_ok(rl); #endif } /** Remove a signed_descriptor_t sd from rl-\>old_routers, and * adjust rl as appropriate. idx is -1, or the index of * sd. */ static void routerlist_remove_old(routerlist_t *rl, signed_descriptor_t *sd, int idx) { signed_descriptor_t *sd_tmp; extrainfo_t *ei_tmp; desc_store_t *store; if (idx == -1) { idx = sd->routerlist_index; } tor_assert(0 <= idx && idx < smartlist_len(rl->old_routers)); /* XXXX edmanm's bridge relay triggered the following assert while * running 0.2.0.12-alpha. If anybody triggers this again, see if we * can get a backtrace. */ tor_assert(smartlist_get(rl->old_routers, idx) == sd); tor_assert(idx == sd->routerlist_index); sd->routerlist_index = -1; smartlist_del(rl->old_routers, idx); if (idx < smartlist_len(rl->old_routers)) { signed_descriptor_t *d = smartlist_get(rl->old_routers, idx); d->routerlist_index = idx; } sd_tmp = sdmap_remove(rl->desc_digest_map, sd->signed_descriptor_digest); tor_assert(sd_tmp == sd); store = desc_get_store(rl, sd); if (store) store->bytes_dropped += sd->signed_descriptor_len; ei_tmp = eimap_remove(rl->extra_info_map, sd->extra_info_digest); if (ei_tmp) { rl->extrainfo_store.bytes_dropped += ei_tmp->cache_info.signed_descriptor_len; extrainfo_free(ei_tmp); } if (!tor_digest_is_zero(sd->extra_info_digest)) sdmap_remove(rl->desc_by_eid_map, sd->extra_info_digest); signed_descriptor_free(sd); #ifdef DEBUG_ROUTERLIST routerlist_assert_ok(rl); #endif } /** Remove ri_old from the routerlist rl, and replace it with * ri_new, updating all index info. If idx is nonnegative and * smartlist_get(rl->routers, idx) == ri, we don't need to do a linear * search over the list to decide which to remove. We put ri_new in the same * index as ri_old, if possible. ri is freed as appropriate. * * If should_cache_descriptors() is true, instead of deleting the router, * we add it to rl->old_routers. */ static void routerlist_replace(routerlist_t *rl, routerinfo_t *ri_old, routerinfo_t *ri_new) { int idx; routerinfo_t *ri_tmp; extrainfo_t *ei_tmp; { /* XXXX Remove this if it turns out to slow us down. */ routerinfo_t *ri_generated = router_get_my_routerinfo(); tor_assert(ri_generated != ri_new); } tor_assert(ri_old != ri_new); tor_assert(ri_new->cache_info.routerlist_index == -1); idx = ri_old->cache_info.routerlist_index; tor_assert(0 <= idx && idx < smartlist_len(rl->routers)); tor_assert(smartlist_get(rl->routers, idx) == ri_old); router_dir_info_changed(); if (idx >= 0) { smartlist_set(rl->routers, idx, ri_new); ri_old->cache_info.routerlist_index = -1; ri_new->cache_info.routerlist_index = idx; /* Check that ri_old is not in rl->routers anymore: */ tor_assert( _routerlist_find_elt(rl->routers, ri_old, -1) == -1 ); } else { log_warn(LD_BUG, "Appending entry from routerlist_replace."); routerlist_insert(rl, ri_new); return; } if (memcmp(ri_old->cache_info.identity_digest, ri_new->cache_info.identity_digest, DIGEST_LEN)) { /* digests don't match; digestmap_set won't replace */ rimap_remove(rl->identity_map, ri_old->cache_info.identity_digest); } ri_tmp = rimap_set(rl->identity_map, ri_new->cache_info.identity_digest, ri_new); tor_assert(!ri_tmp || ri_tmp == ri_old); sdmap_set(rl->desc_digest_map, ri_new->cache_info.signed_descriptor_digest, &(ri_new->cache_info)); if (!tor_digest_is_zero(ri_new->cache_info.extra_info_digest)) { sdmap_set(rl->desc_by_eid_map, ri_new->cache_info.extra_info_digest, &ri_new->cache_info); } if (should_cache_old_descriptors() && ri_old->purpose == ROUTER_PURPOSE_GENERAL) { signed_descriptor_t *sd = signed_descriptor_from_routerinfo(ri_old); smartlist_add(rl->old_routers, sd); sd->routerlist_index = smartlist_len(rl->old_routers)-1; sdmap_set(rl->desc_digest_map, sd->signed_descriptor_digest, sd); if (!tor_digest_is_zero(sd->extra_info_digest)) sdmap_set(rl->desc_by_eid_map, sd->extra_info_digest, sd); } else { if (memcmp(ri_old->cache_info.signed_descriptor_digest, ri_new->cache_info.signed_descriptor_digest, DIGEST_LEN)) { /* digests don't match; digestmap_set didn't replace */ sdmap_remove(rl->desc_digest_map, ri_old->cache_info.signed_descriptor_digest); } ei_tmp = eimap_remove(rl->extra_info_map, ri_old->cache_info.extra_info_digest); if (ei_tmp) { rl->extrainfo_store.bytes_dropped += ei_tmp->cache_info.signed_descriptor_len; extrainfo_free(ei_tmp); } if (!tor_digest_is_zero(ri_old->cache_info.extra_info_digest)) { sdmap_remove(rl->desc_by_eid_map, ri_old->cache_info.extra_info_digest); } rl->desc_store.bytes_dropped += ri_old->cache_info.signed_descriptor_len; routerinfo_free(ri_old); } #ifdef DEBUG_ROUTERLIST routerlist_assert_ok(rl); #endif } /** Extract the descriptor sd from old_routerlist, and re-parse * it as a fresh routerinfo_t. */ static routerinfo_t * routerlist_reparse_old(routerlist_t *rl, signed_descriptor_t *sd) { routerinfo_t *ri; const char *body; body = signed_descriptor_get_annotations(sd); ri = router_parse_entry_from_string(body, body+sd->signed_descriptor_len+sd->annotations_len, 0, 1, NULL); if (!ri) return NULL; memcpy(&ri->cache_info, sd, sizeof(signed_descriptor_t)); sd->signed_descriptor_body = NULL; /* Steal reference. */ ri->cache_info.routerlist_index = -1; routerlist_remove_old(rl, sd, -1); return ri; } /** Free all memory held by the routerlist module. */ void routerlist_free_all(void) { if (routerlist) routerlist_free(routerlist); routerlist = NULL; if (warned_nicknames) { SMARTLIST_FOREACH(warned_nicknames, char *, cp, tor_free(cp)); smartlist_free(warned_nicknames); warned_nicknames = NULL; } if (trusted_dir_servers) { SMARTLIST_FOREACH(trusted_dir_servers, trusted_dir_server_t *, ds, trusted_dir_server_free(ds)); smartlist_free(trusted_dir_servers); trusted_dir_servers = NULL; } if (trusted_dir_certs) { DIGESTMAP_FOREACH(trusted_dir_certs, key, cert_list_t *, cl) { SMARTLIST_FOREACH(cl->certs, authority_cert_t *, cert, authority_cert_free(cert)); smartlist_free(cl->certs); tor_free(cl); } DIGESTMAP_FOREACH_END; digestmap_free(trusted_dir_certs, NULL); trusted_dir_certs = NULL; } } /** Forget that we have issued any router-related warnings, so that we'll * warn again if we see the same errors. */ void routerlist_reset_warnings(void) { if (!warned_nicknames) warned_nicknames = smartlist_create(); SMARTLIST_FOREACH(warned_nicknames, char *, cp, tor_free(cp)); smartlist_clear(warned_nicknames); /* now the list is empty. */ networkstatus_reset_warnings(); } /** Mark the router with ID digest as running or non-running * in our routerlist. */ void router_set_status(const char *digest, int up) { routerinfo_t *router; routerstatus_t *status; tor_assert(digest); SMARTLIST_FOREACH(trusted_dir_servers, trusted_dir_server_t *, d, if (!memcmp(d->digest, digest, DIGEST_LEN)) d->is_running = up); router = router_get_by_digest(digest); if (router) { log_debug(LD_DIR,"Marking router '%s/%s' as %s.", router->nickname, router->address, up ? "up" : "down"); if (!up && router_is_me(router) && !we_are_hibernating()) log_warn(LD_NET, "We just marked ourself as down. Are your external " "addresses reachable?"); router->is_running = up; } status = router_get_consensus_status_by_id(digest); if (status && status->is_running != up) { status->is_running = up; control_event_networkstatus_changed_single(status); } router_dir_info_changed(); } /** Add router to the routerlist, if we don't already have it. Replace * older entries (if any) with the same key. Note: Callers should not hold * their pointers to router if this function fails; router * will either be inserted into the routerlist or freed. Similarly, even * if this call succeeds, they should not hold their pointers to * router after subsequent calls with other routerinfo's -- they * might cause the original routerinfo to get freed. * * Returns the status for the operation. Might set *msg if it wants * the poster of the router to know something. * * If from_cache, this descriptor came from our disk cache. If * from_fetch, we received it in response to a request we made. * (If both are false, that means it was uploaded to us as an auth dir * server or via the controller.) * * This function should be called *after* * routers_update_status_from_consensus_networkstatus; subsequently, you * should call router_rebuild_store and routerlist_descriptors_added. */ was_router_added_t router_add_to_routerlist(routerinfo_t *router, const char **msg, int from_cache, int from_fetch) { const char *id_digest; int authdir = authdir_mode_handles_descs(get_options(), router->purpose); int authdir_believes_valid = 0; routerinfo_t *old_router; networkstatus_t *consensus = networkstatus_get_latest_consensus(); const smartlist_t *networkstatus_v2_list = networkstatus_get_v2_list(); int in_consensus = 0; tor_assert(msg); if (!routerlist) router_get_routerlist(); id_digest = router->cache_info.identity_digest; /* Make sure that we haven't already got this exact descriptor. */ if (sdmap_get(routerlist->desc_digest_map, router->cache_info.signed_descriptor_digest)) { log_info(LD_DIR, "Dropping descriptor that we already have for router '%s'", router->nickname); *msg = "Router descriptor was not new."; routerinfo_free(router); return ROUTER_WAS_NOT_NEW; } if (authdir) { if (authdir_wants_to_reject_router(router, msg, !from_cache && !from_fetch)) { tor_assert(*msg); routerinfo_free(router); return ROUTER_AUTHDIR_REJECTS; } authdir_believes_valid = router->is_valid; } else if (from_fetch) { /* Only check the descriptor digest against the network statuses when * we are receiving in response to a fetch. */ if (!signed_desc_digest_is_recognized(&router->cache_info) && !routerinfo_is_a_configured_bridge(router)) { /* We asked for it, so some networkstatus must have listed it when we * did. Save it if we're a cache in case somebody else asks for it. */ log_info(LD_DIR, "Received a no-longer-recognized descriptor for router '%s'", router->nickname); *msg = "Router descriptor is not referenced by any network-status."; /* Only journal this desc if we'll be serving it. */ if (!from_cache && should_cache_old_descriptors()) signed_desc_append_to_journal(&router->cache_info, &routerlist->desc_store); routerlist_insert_old(routerlist, router); return ROUTER_NOT_IN_CONSENSUS_OR_NETWORKSTATUS; } } /* We no longer need a router with this descriptor digest. */ SMARTLIST_FOREACH(networkstatus_v2_list, networkstatus_v2_t *, ns, { routerstatus_t *rs = networkstatus_v2_find_entry(ns, router->cache_info.identity_digest); if (rs && !memcmp(rs->descriptor_digest, router->cache_info.signed_descriptor_digest, DIGEST_LEN)) rs->need_to_mirror = 0; }); if (consensus) { routerstatus_t *rs = networkstatus_vote_find_entry(consensus, router->cache_info.identity_digest); if (rs && !memcmp(rs->descriptor_digest, router->cache_info.signed_descriptor_digest, DIGEST_LEN)) { in_consensus = 1; rs->need_to_mirror = 0; } } if (router->purpose == ROUTER_PURPOSE_GENERAL && consensus && !in_consensus && !authdir) { /* If it's a general router not listed in the consensus, then don't * consider replacing the latest router with it. */ if (!from_cache && should_cache_old_descriptors()) signed_desc_append_to_journal(&router->cache_info, &routerlist->desc_store); routerlist_insert_old(routerlist, router); *msg = "Skipping router descriptor: not in consensus."; return ROUTER_NOT_IN_CONSENSUS; } /* If we have a router with the same identity key, choose the newer one. */ old_router = rimap_get(routerlist->identity_map, router->cache_info.identity_digest); if (old_router) { if (!in_consensus && (router->cache_info.published_on <= old_router->cache_info.published_on)) { /* Same key, but old. This one is not listed in the consensus. */ log_debug(LD_DIR, "Skipping not-new descriptor for router '%s'", router->nickname); /* Only journal this desc if we'll be serving it. */ if (!from_cache && should_cache_old_descriptors()) signed_desc_append_to_journal(&router->cache_info, &routerlist->desc_store); routerlist_insert_old(routerlist, router); *msg = "Router descriptor was not new."; return ROUTER_WAS_NOT_NEW; } else { /* Same key, and either new, or listed in the consensus. */ log_debug(LD_DIR, "Replacing entry for router '%s/%s' [%s]", router->nickname, old_router->nickname, hex_str(id_digest,DIGEST_LEN)); if (router->addr == old_router->addr && router->or_port == old_router->or_port) { /* these carry over when the address and orport are unchanged. */ router->last_reachable = old_router->last_reachable; router->testing_since = old_router->testing_since; } routerlist_replace(routerlist, old_router, router); if (!from_cache) { signed_desc_append_to_journal(&router->cache_info, &routerlist->desc_store); } directory_set_dirty(); *msg = authdir_believes_valid ? "Valid server updated" : ("Invalid server updated. (This dirserver is marking your " "server as unapproved.)"); return ROUTER_ADDED_SUCCESSFULLY; } } if (!in_consensus && from_cache && router->cache_info.published_on < time(NULL) - OLD_ROUTER_DESC_MAX_AGE) { *msg = "Router descriptor was really old."; return ROUTER_WAS_NOT_NEW; } /* We haven't seen a router with this identity before. Add it to the end of * the list. */ routerlist_insert(routerlist, router); if (!from_cache) signed_desc_append_to_journal(&router->cache_info, &routerlist->desc_store); directory_set_dirty(); return ROUTER_ADDED_SUCCESSFULLY; } /** Insert ei into the routerlist, or free it. Other arguments are * as for router_add_to_routerlist(). Return ROUTER_ADDED_SUCCESSFULLY iff * we actually inserted it, ROUTER_BAD_EI otherwise. */ was_router_added_t router_add_extrainfo_to_routerlist(extrainfo_t *ei, const char **msg, int from_cache, int from_fetch) { int inserted; (void)from_fetch; if (msg) *msg = NULL; /*XXXX022 Do something with msg */ inserted = extrainfo_insert(router_get_routerlist(), ei); if (inserted && !from_cache) signed_desc_append_to_journal(&ei->cache_info, &routerlist->extrainfo_store); if (inserted) return ROUTER_ADDED_SUCCESSFULLY; else return ROUTER_BAD_EI; } /** Sorting helper: return <0, 0, or >0 depending on whether the * signed_descriptor_t* in *a has an identity digest preceding, equal * to, or later than that of *b. */ static int _compare_old_routers_by_identity(const void **_a, const void **_b) { int i; const signed_descriptor_t *r1 = *_a, *r2 = *_b; if ((i = memcmp(r1->identity_digest, r2->identity_digest, DIGEST_LEN))) return i; return (int)(r1->published_on - r2->published_on); } /** Internal type used to represent how long an old descriptor was valid, * where it appeared in the list of old descriptors, and whether it's extra * old. Used only by routerlist_remove_old_cached_routers_with_id(). */ struct duration_idx_t { int duration; int idx; int old; }; /** Sorting helper: compare two duration_idx_t by their duration. */ static int _compare_duration_idx(const void *_d1, const void *_d2) { const struct duration_idx_t *d1 = _d1; const struct duration_idx_t *d2 = _d2; return d1->duration - d2->duration; } /** The range lo through hi inclusive of routerlist->old_routers * must contain routerinfo_t with the same identity and with publication time * in ascending order. Remove members from this range until there are no more * than max_descriptors_per_router() remaining. Start by removing the oldest * members from before cutoff, then remove members which were current * for the lowest amount of time. The order of members of old_routers at * indices lo or higher may be changed. */ static void routerlist_remove_old_cached_routers_with_id(time_t now, time_t cutoff, int lo, int hi, digestset_t *retain) { int i, n = hi-lo+1; unsigned n_extra, n_rmv = 0; struct duration_idx_t *lifespans; uint8_t *rmv, *must_keep; smartlist_t *lst = routerlist->old_routers; #if 1 const char *ident; tor_assert(hi < smartlist_len(lst)); tor_assert(lo <= hi); ident = ((signed_descriptor_t*)smartlist_get(lst, lo))->identity_digest; for (i = lo+1; i <= hi; ++i) { signed_descriptor_t *r = smartlist_get(lst, i); tor_assert(!memcmp(ident, r->identity_digest, DIGEST_LEN)); } #endif /* Check whether we need to do anything at all. */ { int mdpr = directory_caches_dir_info(get_options()) ? 2 : 1; if (n <= mdpr) return; n_extra = n - mdpr; } lifespans = tor_malloc_zero(sizeof(struct duration_idx_t)*n); rmv = tor_malloc_zero(sizeof(uint8_t)*n); must_keep = tor_malloc_zero(sizeof(uint8_t)*n); /* Set lifespans to contain the lifespan and index of each server. */ /* Set rmv[i-lo]=1 if we're going to remove a server for being too old. */ for (i = lo; i <= hi; ++i) { signed_descriptor_t *r = smartlist_get(lst, i); signed_descriptor_t *r_next; lifespans[i-lo].idx = i; if (r->last_listed_as_valid_until >= now || (retain && digestset_isin(retain, r->signed_descriptor_digest))) { must_keep[i-lo] = 1; } if (i < hi) { r_next = smartlist_get(lst, i+1); tor_assert(r->published_on <= r_next->published_on); lifespans[i-lo].duration = (int)(r_next->published_on - r->published_on); } else { r_next = NULL; lifespans[i-lo].duration = INT_MAX; } if (!must_keep[i-lo] && r->published_on < cutoff && n_rmv < n_extra) { ++n_rmv; lifespans[i-lo].old = 1; rmv[i-lo] = 1; } } if (n_rmv < n_extra) { /** * We aren't removing enough servers for being old. Sort lifespans by * the duration of liveness, and remove the ones we're not already going to * remove based on how long they were alive. **/ qsort(lifespans, n, sizeof(struct duration_idx_t), _compare_duration_idx); for (i = 0; i < n && n_rmv < n_extra; ++i) { if (!must_keep[lifespans[i].idx-lo] && !lifespans[i].old) { rmv[lifespans[i].idx-lo] = 1; ++n_rmv; } } } i = hi; do { if (rmv[i-lo]) routerlist_remove_old(routerlist, smartlist_get(lst, i), i); } while (--i >= lo); tor_free(must_keep); tor_free(rmv); tor_free(lifespans); } /** Deactivate any routers from the routerlist that are more than * ROUTER_MAX_AGE seconds old and not recommended by any networkstatuses; * remove old routers from the list of cached routers if we have too many. */ void routerlist_remove_old_routers(void) { int i, hi=-1; const char *cur_id = NULL; time_t now = time(NULL); time_t cutoff; routerinfo_t *router; signed_descriptor_t *sd; digestset_t *retain; int caches = directory_caches_dir_info(get_options()); const networkstatus_t *consensus = networkstatus_get_latest_consensus(); const smartlist_t *networkstatus_v2_list = networkstatus_get_v2_list(); int have_enough_v2; trusted_dirs_remove_old_certs(); if (!routerlist || !consensus) return; // routerlist_assert_ok(routerlist); /* We need to guess how many router descriptors we will wind up wanting to retain, so that we can be sure to allocate a large enough Bloom filter to hold the digest set. Overestimating is fine; underestimating is bad. */ { /* We'll probably retain everything in the consensus. */ int n_max_retain = smartlist_len(consensus->routerstatus_list); if (caches && networkstatus_v2_list) { /* If we care about v2 statuses, we'll retain at most as many as are listed any of the v2 statues. This will be at least the length of the largest v2 networstatus, and in the worst case, this set will be equal to the sum of the lengths of all v2 consensuses. Take the worst case. */ SMARTLIST_FOREACH(networkstatus_v2_list, networkstatus_v2_t *, ns, n_max_retain += smartlist_len(ns->entries)); } retain = digestset_new(n_max_retain); } cutoff = now - OLD_ROUTER_DESC_MAX_AGE; /* Build a list of all the descriptors that _anybody_ lists. */ if (caches && networkstatus_v2_list) { SMARTLIST_FOREACH(networkstatus_v2_list, networkstatus_v2_t *, ns, { /* XXXX The inner loop here gets pretty expensive, and actually shows up * on some profiles. It may be the reason digestmap_set shows up in * profiles too. If instead we kept a per-descriptor digest count of * how many networkstatuses recommended each descriptor, and changed * that only when the networkstatuses changed, that would be a speed * improvement, possibly 1-4% if it also removes digestmap_set from the * profile. Not worth it for 0.1.2.x, though. The new directory * system will obsolete this whole thing in 0.2.0.x. */ SMARTLIST_FOREACH(ns->entries, routerstatus_t *, rs, if (rs->published_on >= cutoff) digestset_add(retain, rs->descriptor_digest)); }); } /* Retain anything listed in the consensus. */ if (consensus) { SMARTLIST_FOREACH(consensus->routerstatus_list, routerstatus_t *, rs, if (rs->published_on >= cutoff) digestset_add(retain, rs->descriptor_digest)); } /* If we have a consensus, and nearly as many v2 networkstatuses as we want, * we should consider pruning current routers that are too old and that * nobody recommends. (If we don't have a consensus or enough v2 * networkstatuses, then we should get more before we decide to kill * routers.) */ /* we set this to true iff we don't care about v2 info, or we have enough. */ have_enough_v2 = !caches || (networkstatus_v2_list && smartlist_len(networkstatus_v2_list) > get_n_v2_authorities() / 2); if (have_enough_v2 && consensus) { cutoff = now - ROUTER_MAX_AGE; /* Remove too-old unrecommended members of routerlist->routers. */ for (i = 0; i < smartlist_len(routerlist->routers); ++i) { router = smartlist_get(routerlist->routers, i); if (router->cache_info.published_on <= cutoff && router->cache_info.last_listed_as_valid_until < now && !digestset_isin(retain, router->cache_info.signed_descriptor_digest)) { /* Too old: remove it. (If we're a cache, just move it into * old_routers.) */ log_info(LD_DIR, "Forgetting obsolete (too old) routerinfo for router '%s'", router->nickname); routerlist_remove(routerlist, router, 1); i--; } } } //routerlist_assert_ok(routerlist); /* Remove far-too-old members of routerlist->old_routers. */ cutoff = now - OLD_ROUTER_DESC_MAX_AGE; for (i = 0; i < smartlist_len(routerlist->old_routers); ++i) { sd = smartlist_get(routerlist->old_routers, i); if (sd->published_on <= cutoff && sd->last_listed_as_valid_until < now && !digestset_isin(retain, sd->signed_descriptor_digest)) { /* Too old. Remove it. */ routerlist_remove_old(routerlist, sd, i--); } } //routerlist_assert_ok(routerlist); log_info(LD_DIR, "We have %d live routers and %d old router descriptors.", smartlist_len(routerlist->routers), smartlist_len(routerlist->old_routers)); /* Now we might have to look at routerlist->old_routers for extraneous * members. (We'd keep all the members if we could, but we need to save * space.) First, check whether we have too many router descriptors, total. * We're okay with having too many for some given router, so long as the * total number doesn't approach max_descriptors_per_router()*len(router). */ if (smartlist_len(routerlist->old_routers) < smartlist_len(routerlist->routers)) goto done; /* Sort by identity, then fix indices. */ smartlist_sort(routerlist->old_routers, _compare_old_routers_by_identity); /* Fix indices. */ for (i = 0; i < smartlist_len(routerlist->old_routers); ++i) { signed_descriptor_t *r = smartlist_get(routerlist->old_routers, i); r->routerlist_index = i; } /* Iterate through the list from back to front, so when we remove descriptors * we don't mess up groups we haven't gotten to. */ for (i = smartlist_len(routerlist->old_routers)-1; i >= 0; --i) { signed_descriptor_t *r = smartlist_get(routerlist->old_routers, i); if (!cur_id) { cur_id = r->identity_digest; hi = i; } if (memcmp(cur_id, r->identity_digest, DIGEST_LEN)) { routerlist_remove_old_cached_routers_with_id(now, cutoff, i+1, hi, retain); cur_id = r->identity_digest; hi = i; } } if (hi>=0) routerlist_remove_old_cached_routers_with_id(now, cutoff, 0, hi, retain); //routerlist_assert_ok(routerlist); done: digestset_free(retain); router_rebuild_store(RRS_DONT_REMOVE_OLD, &routerlist->desc_store); router_rebuild_store(RRS_DONT_REMOVE_OLD,&routerlist->extrainfo_store); } /** We just added a new set of descriptors. Take whatever extra steps * we need. */ static void routerlist_descriptors_added(smartlist_t *sl, int from_cache) { tor_assert(sl); control_event_descriptors_changed(sl); SMARTLIST_FOREACH(sl, routerinfo_t *, ri, if (ri->purpose == ROUTER_PURPOSE_BRIDGE) learned_bridge_descriptor(ri, from_cache); ); } /** * Code to parse a single router descriptor and insert it into the * routerlist. Return -1 if the descriptor was ill-formed; 0 if the * descriptor was well-formed but could not be added; and 1 if the * descriptor was added. * * If we don't add it and msg is not NULL, then assign to * *msg a static string describing the reason for refusing the * descriptor. * * This is used only by the controller. */ int router_load_single_router(const char *s, uint8_t purpose, int cache, const char **msg) { routerinfo_t *ri; was_router_added_t r; smartlist_t *lst; char annotation_buf[ROUTER_ANNOTATION_BUF_LEN]; tor_assert(msg); *msg = NULL; tor_snprintf(annotation_buf, sizeof(annotation_buf), "@source controller\n" "@purpose %s\n", router_purpose_to_string(purpose)); if (!(ri = router_parse_entry_from_string(s, NULL, 1, 0, annotation_buf))) { log_warn(LD_DIR, "Error parsing router descriptor; dropping."); *msg = "Couldn't parse router descriptor."; return -1; } tor_assert(ri->purpose == purpose); if (router_is_me(ri)) { log_warn(LD_DIR, "Router's identity key matches mine; dropping."); *msg = "Router's identity key matches mine."; routerinfo_free(ri); return 0; } if (!cache) /* obey the preference of the controller */ ri->cache_info.do_not_cache = 1; lst = smartlist_create(); smartlist_add(lst, ri); routers_update_status_from_consensus_networkstatus(lst, 0); r = router_add_to_routerlist(ri, msg, 0, 0); if (!WRA_WAS_ADDED(r)) { /* we've already assigned to *msg now, and ri is already freed */ tor_assert(*msg); if (r == ROUTER_AUTHDIR_REJECTS) log_warn(LD_DIR, "Couldn't add router to list: %s Dropping.", *msg); smartlist_free(lst); return 0; } else { routerlist_descriptors_added(lst, 0); smartlist_free(lst); log_debug(LD_DIR, "Added router to list"); return 1; } } /** Given a string s containing some routerdescs, parse it and put the * routers into our directory. If saved_location is SAVED_NOWHERE, the routers * are in response to a query to the network: cache them by adding them to * the journal. * * Return the number of routers actually added. * * If requested_fingerprints is provided, it must contain a list of * uppercased fingerprints. Do not update any router whose * fingerprint is not on the list; after updating a router, remove its * fingerprint from the list. * * If descriptor_digests is non-zero, then the requested_fingerprints * are descriptor digests. Otherwise they are identity digests. */ int router_load_routers_from_string(const char *s, const char *eos, saved_location_t saved_location, smartlist_t *requested_fingerprints, int descriptor_digests, const char *prepend_annotations) { smartlist_t *routers = smartlist_create(), *changed = smartlist_create(); char fp[HEX_DIGEST_LEN+1]; const char *msg; int from_cache = (saved_location != SAVED_NOWHERE); int allow_annotations = (saved_location != SAVED_NOWHERE); int any_changed = 0; router_parse_list_from_string(&s, eos, routers, saved_location, 0, allow_annotations, prepend_annotations); routers_update_status_from_consensus_networkstatus(routers, !from_cache); log_info(LD_DIR, "%d elements to add", smartlist_len(routers)); SMARTLIST_FOREACH_BEGIN(routers, routerinfo_t *, ri) { was_router_added_t r; if (requested_fingerprints) { base16_encode(fp, sizeof(fp), descriptor_digests ? ri->cache_info.signed_descriptor_digest : ri->cache_info.identity_digest, DIGEST_LEN); if (smartlist_string_isin(requested_fingerprints, fp)) { smartlist_string_remove(requested_fingerprints, fp); } else { char *requested = smartlist_join_strings(requested_fingerprints," ",0,NULL); log_warn(LD_DIR, "We received a router descriptor with a fingerprint (%s) " "that we never requested. (We asked for: %s.) Dropping.", fp, requested); tor_free(requested); routerinfo_free(ri); continue; } } r = router_add_to_routerlist(ri, &msg, from_cache, !from_cache); if (WRA_WAS_ADDED(r)) { any_changed++; smartlist_add(changed, ri); routerlist_descriptors_added(changed, from_cache); smartlist_clear(changed); } else if (WRA_WAS_REJECTED(r)) { download_status_t *dl_status; dl_status = router_get_dl_status_by_descriptor_digest( ri->cache_info.signed_descriptor_digest); if (dl_status) { log_info(LD_GENERAL, "Marking router %s as never downloadable", ri->cache_info.signed_descriptor_digest); download_status_mark_impossible(dl_status); } } } SMARTLIST_FOREACH_END(ri); routerlist_assert_ok(routerlist); if (any_changed) router_rebuild_store(0, &routerlist->desc_store); smartlist_free(routers); smartlist_free(changed); return any_changed; } /** Parse one or more extrainfos from s (ending immediately before * eos if eos is present). Other arguments are as for * router_load_routers_from_string(). */ void router_load_extrainfo_from_string(const char *s, const char *eos, saved_location_t saved_location, smartlist_t *requested_fingerprints, int descriptor_digests) { smartlist_t *extrainfo_list = smartlist_create(); const char *msg; int from_cache = (saved_location != SAVED_NOWHERE); router_parse_list_from_string(&s, eos, extrainfo_list, saved_location, 1, 0, NULL); log_info(LD_DIR, "%d elements to add", smartlist_len(extrainfo_list)); SMARTLIST_FOREACH(extrainfo_list, extrainfo_t *, ei, { was_router_added_t added = router_add_extrainfo_to_routerlist(ei, &msg, from_cache, !from_cache); if (WRA_WAS_ADDED(added) && requested_fingerprints) { char fp[HEX_DIGEST_LEN+1]; base16_encode(fp, sizeof(fp), descriptor_digests ? ei->cache_info.signed_descriptor_digest : ei->cache_info.identity_digest, DIGEST_LEN); smartlist_string_remove(requested_fingerprints, fp); /* We silently let people stuff us with extrainfos we didn't ask for, * so long as we would have wanted them anyway. Since we always fetch * all the extrainfos we want, and we never actually act on them * inside Tor, this should be harmless. */ } }); routerlist_assert_ok(routerlist); router_rebuild_store(0, &router_get_routerlist()->extrainfo_store); smartlist_free(extrainfo_list); } /** Return true iff any networkstatus includes a descriptor whose digest * is that of desc. */ static int signed_desc_digest_is_recognized(signed_descriptor_t *desc) { routerstatus_t *rs; networkstatus_t *consensus = networkstatus_get_latest_consensus(); int caches = directory_caches_dir_info(get_options()); const smartlist_t *networkstatus_v2_list = networkstatus_get_v2_list(); if (consensus) { rs = networkstatus_vote_find_entry(consensus, desc->identity_digest); if (rs && !memcmp(rs->descriptor_digest, desc->signed_descriptor_digest, DIGEST_LEN)) return 1; } if (caches && networkstatus_v2_list) { SMARTLIST_FOREACH(networkstatus_v2_list, networkstatus_v2_t *, ns, { if (!(rs = networkstatus_v2_find_entry(ns, desc->identity_digest))) continue; if (!memcmp(rs->descriptor_digest, desc->signed_descriptor_digest, DIGEST_LEN)) return 1; }); } return 0; } /** Clear all our timeouts for fetching v2 and v3 directory stuff, and then * give it all a try again. */ void routerlist_retry_directory_downloads(time_t now) { router_reset_status_download_failures(); router_reset_descriptor_download_failures(); update_networkstatus_downloads(now); update_router_descriptor_downloads(now); } /** Return 1 if all running sufficiently-stable routers will reject * addr:port, return 0 if any might accept it. */ int router_exit_policy_all_routers_reject(uint32_t addr, uint16_t port, int need_uptime) { addr_policy_result_t r; if (!routerlist) return 1; SMARTLIST_FOREACH(routerlist->routers, routerinfo_t *, router, { if (router->is_running && !router_is_unreliable(router, need_uptime, 0, 0)) { r = compare_addr_to_addr_policy(addr, port, router->exit_policy); if (r != ADDR_POLICY_REJECTED && r != ADDR_POLICY_PROBABLY_REJECTED) return 0; /* this one could be ok. good enough. */ } }); return 1; /* all will reject. */ } /** Return true iff router does not permit exit streams. */ int router_exit_policy_rejects_all(routerinfo_t *router) { return router->policy_is_reject_star; } /** Add to the list of authorized directory servers one at * address:port, with identity key digest. If * address is NULL, add ourself. Return 0 if success, -1 if * we couldn't add it. */ trusted_dir_server_t * add_trusted_dir_server(const char *nickname, const char *address, uint16_t dir_port, uint16_t or_port, const char *digest, const char *v3_auth_digest, authority_type_t type) { trusted_dir_server_t *ent; uint32_t a; char *hostname = NULL; size_t dlen; if (!trusted_dir_servers) trusted_dir_servers = smartlist_create(); if (!address) { /* The address is us; we should guess. */ if (resolve_my_address(LOG_WARN, get_options(), &a, &hostname) < 0) { log_warn(LD_CONFIG, "Couldn't find a suitable address when adding ourself as a " "trusted directory server."); return NULL; } } else { if (tor_lookup_hostname(address, &a)) { log_warn(LD_CONFIG, "Unable to lookup address for directory server at '%s'", address); return NULL; } hostname = tor_strdup(address); } ent = tor_malloc_zero(sizeof(trusted_dir_server_t)); ent->nickname = nickname ? tor_strdup(nickname) : NULL; ent->address = hostname; ent->addr = a; ent->dir_port = dir_port; ent->or_port = or_port; ent->is_running = 1; ent->type = type; memcpy(ent->digest, digest, DIGEST_LEN); if (v3_auth_digest && (type & V3_AUTHORITY)) memcpy(ent->v3_identity_digest, v3_auth_digest, DIGEST_LEN); dlen = 64 + strlen(hostname) + (nickname?strlen(nickname):0); ent->description = tor_malloc(dlen); if (nickname) tor_snprintf(ent->description, dlen, "directory server \"%s\" at %s:%d", nickname, hostname, (int)dir_port); else tor_snprintf(ent->description, dlen, "directory server at %s:%d", hostname, (int)dir_port); ent->fake_status.addr = ent->addr; memcpy(ent->fake_status.identity_digest, digest, DIGEST_LEN); if (nickname) strlcpy(ent->fake_status.nickname, nickname, sizeof(ent->fake_status.nickname)); else ent->fake_status.nickname[0] = '\0'; ent->fake_status.dir_port = ent->dir_port; ent->fake_status.or_port = ent->or_port; if (ent->or_port) ent->fake_status.version_supports_begindir = 1; /* XX021 - wait until authorities are upgraded */ #if 0 ent->fake_status.version_supports_conditional_consensus = 1; #else ent->fake_status.version_supports_conditional_consensus = 0; #endif smartlist_add(trusted_dir_servers, ent); router_dir_info_changed(); return ent; } /** Free storage held in cert. */ void authority_cert_free(authority_cert_t *cert) { if (!cert) return; tor_free(cert->cache_info.signed_descriptor_body); if (cert->signing_key) crypto_free_pk_env(cert->signing_key); if (cert->identity_key) crypto_free_pk_env(cert->identity_key); tor_free(cert); } /** Free storage held in ds. */ static void trusted_dir_server_free(trusted_dir_server_t *ds) { tor_free(ds->nickname); tor_free(ds->description); tor_free(ds->address); tor_free(ds); } /** Remove all members from the list of trusted dir servers. */ void clear_trusted_dir_servers(void) { if (trusted_dir_servers) { SMARTLIST_FOREACH(trusted_dir_servers, trusted_dir_server_t *, ent, trusted_dir_server_free(ent)); smartlist_clear(trusted_dir_servers); } else { trusted_dir_servers = smartlist_create(); } router_dir_info_changed(); } /** Return 1 if any trusted dir server supports v1 directories, * else return 0. */ int any_trusted_dir_is_v1_authority(void) { if (trusted_dir_servers) return get_n_authorities(V1_AUTHORITY) > 0; return 0; } /** For every current directory connection whose purpose is purpose, * and where the resource being downloaded begins with <