/* Copyright (c) 2009-2011, The Tor Project, Inc. */ /* See LICENSE for licensing information */ #include "or.h" #include "config.h" #include "directory.h" #include "dirserv.h" #include "microdesc.h" #include "networkstatus.h" #include "nodelist.h" #include "policies.h" #include "router.h" #include "routerlist.h" #include "routerparse.h" /** A data structure to hold a bunch of cached microdescriptors. There are * two active files in the cache: a "cache file" that we mmap, and a "journal * file" that we append to. Periodically, we rebuild the cache file to hold * only the microdescriptors that we want to keep */ struct microdesc_cache_t { /** Map from sha256-digest to microdesc_t for every microdesc_t in the * cache. */ HT_HEAD(microdesc_map, microdesc_t) map; /** Name of the cache file. */ char *cache_fname; /** Name of the journal file. */ char *journal_fname; /** Mmap'd contents of the cache file, or NULL if there is none. */ tor_mmap_t *cache_content; /** Number of bytes used in the journal file. */ size_t journal_len; /** Number of bytes in descriptors removed as too old. */ size_t bytes_dropped; /** Total bytes of microdescriptor bodies we have added to this cache */ uint64_t total_len_seen; /** Total number of microdescriptors we have added to this cache */ unsigned n_seen; }; /** Helper: computes a hash of md to place it in a hash table. */ static INLINE unsigned int _microdesc_hash(microdesc_t *md) { unsigned *d = (unsigned*)md->digest; #if SIZEOF_INT == 4 return d[0] ^ d[1] ^ d[2] ^ d[3] ^ d[4] ^ d[5] ^ d[6] ^ d[7]; #else return d[0] ^ d[1] ^ d[2] ^ d[3]; #endif } /** Helper: compares a and for equality for hash-table purposes. */ static INLINE int _microdesc_eq(microdesc_t *a, microdesc_t *b) { return tor_memeq(a->digest, b->digest, DIGEST256_LEN); } HT_PROTOTYPE(microdesc_map, microdesc_t, node, _microdesc_hash, _microdesc_eq); HT_GENERATE(microdesc_map, microdesc_t, node, _microdesc_hash, _microdesc_eq, 0.6, malloc, realloc, free); /** Write the body of md into f, with appropriate annotations. * On success, return the total number of bytes written, and set * *annotation_len_out to the number of bytes written as * annotations. */ static ssize_t dump_microdescriptor(FILE *f, microdesc_t *md, size_t *annotation_len_out) { ssize_t r = 0; size_t written; /* XXXX drops unkown annotations. */ if (md->last_listed) { char buf[ISO_TIME_LEN+1]; char annotation[ISO_TIME_LEN+32]; format_iso_time(buf, md->last_listed); tor_snprintf(annotation, sizeof(annotation), "@last-listed %s\n", buf); fputs(annotation, f); r += strlen(annotation); *annotation_len_out = r; } else { *annotation_len_out = 0; } md->off = (off_t) ftell(f); written = fwrite(md->body, 1, md->bodylen, f); if (written != md->bodylen) { log_warn(LD_DIR, "Couldn't dump microdescriptor (wrote %lu out of %lu): %s", (unsigned long)written, (unsigned long)md->bodylen, strerror(ferror(f))); return -1; } r += md->bodylen; return r; } /** Holds a pointer to the current microdesc_cache_t object, or NULL if no * such object has been allocated. */ static microdesc_cache_t *the_microdesc_cache = NULL; /** Return a pointer to the microdescriptor cache, loading it if necessary. */ microdesc_cache_t * get_microdesc_cache(void) { if (PREDICT_UNLIKELY(the_microdesc_cache==NULL)) { microdesc_cache_t *cache = tor_malloc_zero(sizeof(microdesc_cache_t)); HT_INIT(microdesc_map, &cache->map); cache->cache_fname = get_datadir_fname("cached-microdescs"); cache->journal_fname = get_datadir_fname("cached-microdescs.new"); microdesc_cache_reload(cache); the_microdesc_cache = cache; } return the_microdesc_cache; } /* There are three sources of microdescriptors: 1) Generated by us while acting as a directory authority. 2) Loaded from the cache on disk. 3) Downloaded. */ /** Decode the microdescriptors from the string starting at s and * ending at eos, and store them in cache. If no-save, * mark them as non-writable to disk. If where is SAVED_IN_CACHE, * leave their bodies as pointers to the mmap'd cache. If where is * SAVED_NOWHERE, do not allow annotations. If listed_at is positive, * set the last_listed field of every microdesc to listed_at. If * requested_digests is non-null, then it contains a list of digests we mean * to allow, so we should reject any non-requested microdesc with a different * digest, and alter the list to contain only the digests of those microdescs * we didn't find. * Return a newly allocated list of the added microdescriptors, or NULL */ smartlist_t * microdescs_add_to_cache(microdesc_cache_t *cache, const char *s, const char *eos, saved_location_t where, int no_save, time_t listed_at, smartlist_t *requested_digests256) { smartlist_t *descriptors, *added; const int allow_annotations = (where != SAVED_NOWHERE); const int copy_body = (where != SAVED_IN_CACHE); descriptors = microdescs_parse_from_string(s, eos, allow_annotations, copy_body); if (listed_at > 0) { SMARTLIST_FOREACH(descriptors, microdesc_t *, md, md->last_listed = listed_at); } if (requested_digests256) { digestmap_t *requested; /* XXXX actuqlly we should just use a digest256map */ requested = digestmap_new(); SMARTLIST_FOREACH(requested_digests256, const char *, cp, digestmap_set(requested, cp, (void*)1)); SMARTLIST_FOREACH_BEGIN(descriptors, microdesc_t *, md) { if (digestmap_get(requested, md->digest)) { digestmap_set(requested, md->digest, (void*)2); } else { log_fn(LOG_PROTOCOL_WARN, LD_DIR, "Received non-requested microcdesc"); microdesc_free(md); SMARTLIST_DEL_CURRENT(descriptors, md); } } SMARTLIST_FOREACH_END(md); SMARTLIST_FOREACH_BEGIN(requested_digests256, char *, cp) { if (digestmap_get(requested, cp) == (void*)2) { tor_free(cp); SMARTLIST_DEL_CURRENT(requested_digests256, cp); } } SMARTLIST_FOREACH_END(cp); digestmap_free(requested, NULL); } added = microdescs_add_list_to_cache(cache, descriptors, where, no_save); smartlist_free(descriptors); return added; } /* As microdescs_add_to_cache, but takes a list of micrdescriptors instead of * a string to decode. Frees any members of descriptors that it does * not add. */ smartlist_t * microdescs_add_list_to_cache(microdesc_cache_t *cache, smartlist_t *descriptors, saved_location_t where, int no_save) { smartlist_t *added; open_file_t *open_file = NULL; FILE *f = NULL; // int n_added = 0; ssize_t size = 0; if (where == SAVED_NOWHERE && !no_save) { f = start_writing_to_stdio_file(cache->journal_fname, OPEN_FLAGS_APPEND|O_BINARY, 0600, &open_file); if (!f) { log_warn(LD_DIR, "Couldn't append to journal in %s: %s", cache->journal_fname, strerror(errno)); return NULL; } } added = smartlist_create(); SMARTLIST_FOREACH_BEGIN(descriptors, microdesc_t *, md) { microdesc_t *md2; md2 = HT_FIND(microdesc_map, &cache->map, md); if (md2) { /* We already had this one. */ if (md2->last_listed < md->last_listed) md2->last_listed = md->last_listed; microdesc_free(md); if (where != SAVED_NOWHERE) cache->bytes_dropped += size; continue; } /* Okay, it's a new one. */ if (f) { size_t annotation_len; size = dump_microdescriptor(f, md, &annotation_len); if (size < 0) { /* XXX handle errors from dump_microdescriptor() */ /* log? return -1? die? coredump the universe? */ continue; } md->saved_location = SAVED_IN_JOURNAL; cache->journal_len += size; } else { md->saved_location = where; } md->no_save = no_save; HT_INSERT(microdesc_map, &cache->map, md); md->held_in_map = 1; smartlist_add(added, md); ++cache->n_seen; cache->total_len_seen += md->bodylen; } SMARTLIST_FOREACH_END(md); if (f) finish_writing_to_file(open_file); /*XXX Check me.*/ { networkstatus_t *ns = networkstatus_get_latest_consensus(); if (ns && ns->flavor == FLAV_MICRODESC) SMARTLIST_FOREACH(added, microdesc_t *, md, nodelist_add_microdesc(md)); } if (smartlist_len(added)) router_dir_info_changed(); return added; } /** Remove every microdescriptor in cache. */ void microdesc_cache_clear(microdesc_cache_t *cache) { microdesc_t **entry, **next; for (entry = HT_START(microdesc_map, &cache->map); entry; entry = next) { microdesc_t *md = *entry; next = HT_NEXT_RMV(microdesc_map, &cache->map, entry); md->held_in_map = 0; microdesc_free(md); } HT_CLEAR(microdesc_map, &cache->map); if (cache->cache_content) { tor_munmap_file(cache->cache_content); cache->cache_content = NULL; } cache->total_len_seen = 0; cache->n_seen = 0; cache->bytes_dropped = 0; } /** Reload the contents of cache from disk. If it is empty, load it * for the first time. Return 0 on success, -1 on failure. */ int microdesc_cache_reload(microdesc_cache_t *cache) { struct stat st; char *journal_content; smartlist_t *added; tor_mmap_t *mm; int total = 0; microdesc_cache_clear(cache); mm = cache->cache_content = tor_mmap_file(cache->cache_fname); if (mm) { added = microdescs_add_to_cache(cache, mm->data, mm->data+mm->size, SAVED_IN_CACHE, 0, -1, NULL); if (added) { total += smartlist_len(added); smartlist_free(added); } } journal_content = read_file_to_str(cache->journal_fname, RFTS_IGNORE_MISSING, &st); if (journal_content) { cache->journal_len = (size_t) st.st_size; added = microdescs_add_to_cache(cache, journal_content, journal_content+st.st_size, SAVED_IN_JOURNAL, 0, -1, NULL); if (added) { total += smartlist_len(added); smartlist_free(added); } tor_free(journal_content); } log_notice(LD_DIR, "Reloaded microdescriptor cache. Found %d descriptors.", total); microdesc_cache_rebuild(cache, 0 /* don't force */); return 0; } /** By default, we remove any microdescriptors that have gone at least this * long without appearing in a current consensus. */ #define TOLERATE_MICRODESC_AGE (7*24*60*60) /** Remove all microdescriptors from cache that haven't been listed for * a long time. Does not rebuild the cache on disk. If cutoff is * positive, specifically remove microdescriptors that have been unlisted * since cutoff. If force is true, remove microdescriptors even * if we have no current live microdescriptor consensus. */ void microdesc_cache_clean(microdesc_cache_t *cache, time_t cutoff, int force) { microdesc_t **mdp, *victim; int dropped=0, kept=0; size_t bytes_dropped = 0; time_t now = time(NULL); /* If we don't know a live consensus, don't believe last_listed values: we * might be starting up after being down for a while. */ if (! force && ! networkstatus_get_reasonably_live_consensus(now, FLAV_MICRODESC)) return; if (cutoff <= 0) cutoff = now - TOLERATE_MICRODESC_AGE; for (mdp = HT_START(microdesc_map, &cache->map); mdp != NULL; ) { if ((*mdp)->last_listed < cutoff) { ++dropped; victim = *mdp; mdp = HT_NEXT_RMV(microdesc_map, &cache->map, mdp); victim->held_in_map = 0; bytes_dropped += victim->bodylen; microdesc_free(victim); } else { ++kept; mdp = HT_NEXT(microdesc_map, &cache->map, mdp); } } if (dropped) { log_notice(LD_DIR, "Removed %d/%d microdescriptors as old.", dropped,dropped+kept); cache->bytes_dropped += bytes_dropped; } } static int should_rebuild_md_cache(microdesc_cache_t *cache) { const size_t old_len = cache->cache_content ? cache->cache_content->size : 0; const size_t journal_len = cache->journal_len; const size_t dropped = cache->bytes_dropped; if (journal_len < 16384) return 0; /* Don't bother, not enough has happened yet. */ if (dropped > (journal_len + old_len) / 3) return 1; /* We could save 1/3 or more of the currently used space. */ if (journal_len > old_len / 2) return 1; /* We should append to the regular file */ return 0; } /** Regenerate the main cache file for cache, clear the journal file, * and update every microdesc_t in the cache with pointers to its new * location. If force is true, do this unconditionally. If * force is false, do it only if we expect to save space on disk. */ int microdesc_cache_rebuild(microdesc_cache_t *cache, int force) { open_file_t *open_file; FILE *f; microdesc_t **mdp; smartlist_t *wrote; ssize_t size; off_t off = 0; int orig_size, new_size; if (cache == NULL) { cache = the_microdesc_cache; if (cache == NULL) return 0; } /* Remove dead descriptors */ microdesc_cache_clean(cache, 0/*cutoff*/, 0/*force*/); if (!force && !should_rebuild_md_cache(cache)) return 0; log_info(LD_DIR, "Rebuilding the microdescriptor cache..."); orig_size = (int)(cache->cache_content ? cache->cache_content->size : 0); orig_size += (int)cache->journal_len; f = start_writing_to_stdio_file(cache->cache_fname, OPEN_FLAGS_REPLACE|O_BINARY, 0600, &open_file); if (!f) return -1; wrote = smartlist_create(); HT_FOREACH(mdp, microdesc_map, &cache->map) { microdesc_t *md = *mdp; size_t annotation_len; if (md->no_save) continue; size = dump_microdescriptor(f, md, &annotation_len); if (size < 0) { /* XXX handle errors from dump_microdescriptor() */ /* log? return -1? die? coredump the universe? */ continue; } tor_assert(((size_t)size) == annotation_len + md->bodylen); md->off = off + annotation_len; off += size; if (md->saved_location != SAVED_IN_CACHE) { tor_free(md->body); md->saved_location = SAVED_IN_CACHE; } smartlist_add(wrote, md); } if (cache->cache_content) tor_munmap_file(cache->cache_content); finish_writing_to_file(open_file); /*XXX Check me.*/ cache->cache_content = tor_mmap_file(cache->cache_fname); if (!cache->cache_content && smartlist_len(wrote)) { log_err(LD_DIR, "Couldn't map file that we just wrote to %s!", cache->cache_fname); smartlist_free(wrote); return -1; } SMARTLIST_FOREACH_BEGIN(wrote, microdesc_t *, md) { tor_assert(md->saved_location == SAVED_IN_CACHE); md->body = (char*)cache->cache_content->data + md->off; if (PREDICT_UNLIKELY( md->bodylen < 9 || fast_memneq(md->body, "onion-key", 9) != 0)) { /* XXXX023 once bug 2022 is solved, we can kill this block and turn it * into just the tor_assert(!memcmp) */ off_t avail = cache->cache_content->size - md->off; char *bad_str; tor_assert(avail >= 0); bad_str = tor_strndup(md->body, MIN(128, (size_t)avail)); log_err(LD_BUG, "After rebuilding microdesc cache, offsets seem wrong. " " At offset %d, I expected to find a microdescriptor starting " " with \"onion-key\". Instead I got %s.", (int)md->off, escaped(bad_str)); tor_free(bad_str); tor_assert(fast_memeq(md->body, "onion-key", 9)); } } SMARTLIST_FOREACH_END(md); smartlist_free(wrote); write_str_to_file(cache->journal_fname, "", 1); cache->journal_len = 0; cache->bytes_dropped = 0; new_size = cache->cache_content ? (int)cache->cache_content->size : 0; log_info(LD_DIR, "Done rebuilding microdesc cache. " "Saved %d bytes; %d still used.", orig_size-new_size, new_size); return 0; } /** Deallocate a single microdescriptor. Note: the microdescriptor MUST have * previously been removed from the cache if it had ever been inserted. */ void microdesc_free(microdesc_t *md) { if (!md) return; /* Make sure that the microdesc was really removed from the appropriate data structures. */ if (md->held_in_map) { microdesc_cache_t *cache = get_microdesc_cache(); microdesc_t *md2 = HT_FIND(microdesc_map, &cache->map, md); if (md2 == md) { log_warn(LD_BUG, "microdesc_free() called, but md was still in " "microdesc_map"); HT_REMOVE(microdesc_map, &cache->map, md); } else { log_warn(LD_BUG, "microdesc_free() called with held_in_map set, but " "microdesc was not in the map."); } tor_fragile_assert(); } if (md->held_by_node) { int found=0; const smartlist_t *nodes = nodelist_get_list(); SMARTLIST_FOREACH(nodes, node_t *, node, { if (node->md == md) { ++found; node->md = NULL; } }); if (found) { log_warn(LD_BUG, "microdesc_free() called, but md was still referenced " "%d node(s)", found); } else { log_warn(LD_BUG, "microdesc_free() called with held_by_node set, but " "md was not refrenced by any nodes"); } tor_fragile_assert(); } //tor_assert(md->held_in_map == 0); //tor_assert(md->held_by_node == 0); if (md->onion_pkey) crypto_free_pk_env(md->onion_pkey); if (md->body && md->saved_location != SAVED_IN_CACHE) tor_free(md->body); if (md->family) { SMARTLIST_FOREACH(md->family, char *, cp, tor_free(cp)); smartlist_free(md->family); } short_policy_free(md->exit_policy); tor_free(md); } /** Free all storage held in the microdesc.c module. */ void microdesc_free_all(void) { if (the_microdesc_cache) { microdesc_cache_clear(the_microdesc_cache); tor_free(the_microdesc_cache->cache_fname); tor_free(the_microdesc_cache->journal_fname); tor_free(the_microdesc_cache); } } /** If there is a microdescriptor in cache whose sha256 digest is * d, return it. Otherwise return NULL. */ microdesc_t * microdesc_cache_lookup_by_digest256(microdesc_cache_t *cache, const char *d) { microdesc_t *md, search; if (!cache) cache = get_microdesc_cache(); memcpy(search.digest, d, DIGEST256_LEN); md = HT_FIND(microdesc_map, &cache->map, &search); return md; } /** Return the mean size of decriptors added to cache since it was last * cleared. Used to estimate the size of large downloads. */ size_t microdesc_average_size(microdesc_cache_t *cache) { if (!cache) cache = get_microdesc_cache(); if (!cache->n_seen) return 512; return (size_t)(cache->total_len_seen / cache->n_seen); } /** Return a smartlist of all the sha256 digest of the microdescriptors that * are listed in ns but not present in cache. Returns pointers * to internals of ns; you should not free the members of the resulting * smartlist. Omit all microdescriptors whose digest appear in skip. */ smartlist_t * microdesc_list_missing_digest256(networkstatus_t *ns, microdesc_cache_t *cache, int downloadable_only, digestmap_t *skip) { smartlist_t *result = smartlist_create(); time_t now = time(NULL); tor_assert(ns->flavor == FLAV_MICRODESC); SMARTLIST_FOREACH_BEGIN(ns->routerstatus_list, routerstatus_t *, rs) { if (microdesc_cache_lookup_by_digest256(cache, rs->descriptor_digest)) continue; if (downloadable_only && !download_status_is_ready(&rs->dl_status, now, MAX_MICRODESC_DOWNLOAD_FAILURES)) continue; if (skip && digestmap_get(skip, rs->descriptor_digest)) continue; if (tor_mem_is_zero(rs->descriptor_digest, DIGEST256_LEN)) continue; /* This indicates a bug somewhere XXXX023*/ /* XXXX Also skip if we're a noncache and wouldn't use this router. * XXXX NM Microdesc */ smartlist_add(result, rs->descriptor_digest); } SMARTLIST_FOREACH_END(rs); return result; } /** Launch download requests for mircodescriptors as appropriate. * * Specifically, we should launch download requests if we are configured to * download mirodescriptors, and there are some microdescriptors listed the * current microdesc consensus that we don't have, and either we never asked * for them, or we failed to download them but we're willing to retry. */ void update_microdesc_downloads(time_t now) { const or_options_t *options = get_options(); networkstatus_t *consensus; smartlist_t *missing; digestmap_t *pending; if (should_delay_dir_fetches(options)) return; if (directory_too_idle_to_fetch_descriptors(options, now)) return; consensus = networkstatus_get_reasonably_live_consensus(now, FLAV_MICRODESC); if (!consensus) return; if (!we_fetch_microdescriptors(options)) return; pending = digestmap_new(); list_pending_microdesc_downloads(pending); missing = microdesc_list_missing_digest256(consensus, get_microdesc_cache(), 1, pending); digestmap_free(pending, NULL); launch_descriptor_downloads(DIR_PURPOSE_FETCH_MICRODESC, missing, NULL, now); smartlist_free(missing); } /** For every microdescriptor listed in the current microdecriptor consensus, * update its last_listed field to be at least as recent as the publication * time of the current microdescriptor consensus. */ void update_microdescs_from_networkstatus(time_t now) { microdesc_cache_t *cache = get_microdesc_cache(); microdesc_t *md; networkstatus_t *ns = networkstatus_get_reasonably_live_consensus(now, FLAV_MICRODESC); if (! ns) return; tor_assert(ns->flavor == FLAV_MICRODESC); SMARTLIST_FOREACH_BEGIN(ns->routerstatus_list, routerstatus_t *, rs) { md = microdesc_cache_lookup_by_digest256(cache, rs->descriptor_digest); if (md && ns->valid_after > md->last_listed) md->last_listed = ns->valid_after; } SMARTLIST_FOREACH_END(rs); } /** Return true iff we should prefer to use microdescriptors rather than * routerdescs for building circuits. */ int we_use_microdescriptors_for_circuits(const or_options_t *options) { int ret = options->UseMicrodescriptors; if (ret == -1) { /* UseMicrodescriptors is "auto"; we need to decide: */ /* So we decide that we'll use microdescriptors iff we are not a server */ ret = ! server_mode(options); } return ret; } /** Return true iff we should try to download microdescriptors at all. */ int we_fetch_microdescriptors(const or_options_t *options) { if (directory_caches_dir_info(options)) return 1; return we_use_microdescriptors_for_circuits(options); } /** Return true iff we should try to download router descriptors at all. */ int we_fetch_router_descriptors(const or_options_t *options) { if (directory_caches_dir_info(options)) return 1; return ! we_use_microdescriptors_for_circuits(options); } /** Return the consensus flavor we actually want to use to build circuits. */ int usable_consensus_flavor(void) { if (we_use_microdescriptors_for_circuits(get_options())) { return FLAV_MICRODESC; } else { return FLAV_NS; } }