microdesc.c 34 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045
  1. /* Copyright (c) 2009-2017, The Tor Project, Inc. */
  2. /* See LICENSE for licensing information */
  3. /**
  4. * \file microdesc.c
  5. *
  6. * \brief Implements microdescriptors -- an abbreviated description of
  7. * less-frequently-changing router information.
  8. */
  9. #include "or.h"
  10. #include "circuitbuild.h"
  11. #include "config.h"
  12. #include "directory.h"
  13. #include "dirserv.h"
  14. #include "entrynodes.h"
  15. #include "microdesc.h"
  16. #include "networkstatus.h"
  17. #include "nodelist.h"
  18. #include "policies.h"
  19. #include "router.h"
  20. #include "routerlist.h"
  21. #include "routerparse.h"
  22. /** A data structure to hold a bunch of cached microdescriptors. There are
  23. * two active files in the cache: a "cache file" that we mmap, and a "journal
  24. * file" that we append to. Periodically, we rebuild the cache file to hold
  25. * only the microdescriptors that we want to keep */
  26. struct microdesc_cache_t {
  27. /** Map from sha256-digest to microdesc_t for every microdesc_t in the
  28. * cache. */
  29. HT_HEAD(microdesc_map, microdesc_t) map;
  30. /** Name of the cache file. */
  31. char *cache_fname;
  32. /** Name of the journal file. */
  33. char *journal_fname;
  34. /** Mmap'd contents of the cache file, or NULL if there is none. */
  35. tor_mmap_t *cache_content;
  36. /** Number of bytes used in the journal file. */
  37. size_t journal_len;
  38. /** Number of bytes in descriptors removed as too old. */
  39. size_t bytes_dropped;
  40. /** Total bytes of microdescriptor bodies we have added to this cache */
  41. uint64_t total_len_seen;
  42. /** Total number of microdescriptors we have added to this cache */
  43. unsigned n_seen;
  44. /** True iff we have loaded this cache from disk ever. */
  45. int is_loaded;
  46. };
  47. static microdesc_cache_t *get_microdesc_cache_noload(void);
  48. /** Helper: computes a hash of <b>md</b> to place it in a hash table. */
  49. static inline unsigned int
  50. microdesc_hash_(microdesc_t *md)
  51. {
  52. return (unsigned) siphash24g(md->digest, sizeof(md->digest));
  53. }
  54. /** Helper: compares <b>a</b> and <b>b</b> for equality for hash-table
  55. * purposes. */
  56. static inline int
  57. microdesc_eq_(microdesc_t *a, microdesc_t *b)
  58. {
  59. return tor_memeq(a->digest, b->digest, DIGEST256_LEN);
  60. }
  61. HT_PROTOTYPE(microdesc_map, microdesc_t, node,
  62. microdesc_hash_, microdesc_eq_)
  63. HT_GENERATE2(microdesc_map, microdesc_t, node,
  64. microdesc_hash_, microdesc_eq_, 0.6,
  65. tor_reallocarray_, tor_free_)
  66. /************************* md fetch fail cache *****************************/
  67. /* If we end up with too many outdated dirservers, something probably went
  68. * wrong so clean up the list. */
  69. #define TOO_MANY_OUTDATED_DIRSERVERS 30
  70. /** List of dirservers with outdated microdesc information. The smartlist is
  71. * filled with the hex digests of outdated dirservers. */
  72. static smartlist_t *outdated_dirserver_list = NULL;
  73. /** Note that we failed to fetch a microdescriptor from the relay with
  74. * <b>relay_digest</b> (of size DIGEST_LEN). */
  75. void
  76. microdesc_note_outdated_dirserver(const char *relay_digest)
  77. {
  78. char relay_hexdigest[HEX_DIGEST_LEN+1];
  79. /* Don't register outdated dirservers if we don't have a live consensus,
  80. * since we might be trying to fetch microdescriptors that are not even
  81. * currently active. */
  82. if (!networkstatus_get_live_consensus(approx_time())) {
  83. return;
  84. }
  85. if (!outdated_dirserver_list) {
  86. outdated_dirserver_list = smartlist_new();
  87. }
  88. tor_assert(outdated_dirserver_list);
  89. /* If the list grows too big, clean it up */
  90. if (BUG(smartlist_len(outdated_dirserver_list) >
  91. TOO_MANY_OUTDATED_DIRSERVERS)) {
  92. microdesc_reset_outdated_dirservers_list();
  93. }
  94. /* Turn the binary relay digest to a hex since smartlists have better support
  95. * for strings than digests. */
  96. base16_encode(relay_hexdigest,sizeof(relay_hexdigest),
  97. relay_digest, DIGEST_LEN);
  98. /* Make sure we don't add a dirauth as an outdated dirserver */
  99. if (router_get_trusteddirserver_by_digest(relay_digest)) {
  100. log_info(LD_GENERAL, "Auth %s gave us outdated dirinfo.", relay_hexdigest);
  101. return;
  102. }
  103. /* Don't double-add outdated dirservers */
  104. if (smartlist_contains_string(outdated_dirserver_list, relay_hexdigest)) {
  105. return;
  106. }
  107. /* Add it to the list of outdated dirservers */
  108. smartlist_add_strdup(outdated_dirserver_list, relay_hexdigest);
  109. log_info(LD_GENERAL, "Noted %s as outdated md dirserver", relay_hexdigest);
  110. }
  111. /** Return True if the relay with <b>relay_digest</b> (size DIGEST_LEN) is an
  112. * outdated dirserver */
  113. int
  114. microdesc_relay_is_outdated_dirserver(const char *relay_digest)
  115. {
  116. char relay_hexdigest[HEX_DIGEST_LEN+1];
  117. if (!outdated_dirserver_list) {
  118. return 0;
  119. }
  120. /* Convert identity digest to hex digest */
  121. base16_encode(relay_hexdigest, sizeof(relay_hexdigest),
  122. relay_digest, DIGEST_LEN);
  123. /* Last time we tried to fetch microdescs, was this directory mirror missing
  124. * any mds we asked for? */
  125. if (smartlist_contains_string(outdated_dirserver_list, relay_hexdigest)) {
  126. return 1;
  127. }
  128. return 0;
  129. }
  130. /** Reset the list of outdated dirservers. */
  131. void
  132. microdesc_reset_outdated_dirservers_list(void)
  133. {
  134. if (!outdated_dirserver_list) {
  135. return;
  136. }
  137. SMARTLIST_FOREACH(outdated_dirserver_list, char *, cp, tor_free(cp));
  138. smartlist_clear(outdated_dirserver_list);
  139. }
  140. /****************************************************************************/
  141. /** Write the body of <b>md</b> into <b>f</b>, with appropriate annotations.
  142. * On success, return the total number of bytes written, and set
  143. * *<b>annotation_len_out</b> to the number of bytes written as
  144. * annotations. */
  145. static ssize_t
  146. dump_microdescriptor(int fd, microdesc_t *md, size_t *annotation_len_out)
  147. {
  148. ssize_t r = 0;
  149. ssize_t written;
  150. if (md->body == NULL) {
  151. *annotation_len_out = 0;
  152. return 0;
  153. }
  154. /* XXXX drops unknown annotations. */
  155. if (md->last_listed) {
  156. char buf[ISO_TIME_LEN+1];
  157. char annotation[ISO_TIME_LEN+32];
  158. format_iso_time(buf, md->last_listed);
  159. tor_snprintf(annotation, sizeof(annotation), "@last-listed %s\n", buf);
  160. if (write_all(fd, annotation, strlen(annotation), 0) < 0) {
  161. log_warn(LD_DIR,
  162. "Couldn't write microdescriptor annotation: %s",
  163. strerror(errno));
  164. return -1;
  165. }
  166. r += strlen(annotation);
  167. *annotation_len_out = r;
  168. } else {
  169. *annotation_len_out = 0;
  170. }
  171. md->off = tor_fd_getpos(fd);
  172. written = write_all(fd, md->body, md->bodylen, 0);
  173. if (written != (ssize_t)md->bodylen) {
  174. written = written < 0 ? 0 : written;
  175. log_warn(LD_DIR,
  176. "Couldn't dump microdescriptor (wrote %ld out of %lu): %s",
  177. (long)written, (unsigned long)md->bodylen,
  178. strerror(errno));
  179. return -1;
  180. }
  181. r += md->bodylen;
  182. return r;
  183. }
  184. /** Holds a pointer to the current microdesc_cache_t object, or NULL if no
  185. * such object has been allocated. */
  186. static microdesc_cache_t *the_microdesc_cache = NULL;
  187. /** Return a pointer to the microdescriptor cache, loading it if necessary. */
  188. microdesc_cache_t *
  189. get_microdesc_cache(void)
  190. {
  191. microdesc_cache_t *cache = get_microdesc_cache_noload();
  192. if (PREDICT_UNLIKELY(cache->is_loaded == 0)) {
  193. microdesc_cache_reload(cache);
  194. }
  195. return cache;
  196. }
  197. /** Return a pointer to the microdescriptor cache, creating (but not loading)
  198. * it if necessary. */
  199. static microdesc_cache_t *
  200. get_microdesc_cache_noload(void)
  201. {
  202. if (PREDICT_UNLIKELY(the_microdesc_cache==NULL)) {
  203. microdesc_cache_t *cache = tor_malloc_zero(sizeof(*cache));
  204. HT_INIT(microdesc_map, &cache->map);
  205. cache->cache_fname = get_cachedir_fname("cached-microdescs");
  206. cache->journal_fname = get_cachedir_fname("cached-microdescs.new");
  207. the_microdesc_cache = cache;
  208. }
  209. return the_microdesc_cache;
  210. }
  211. /* There are three sources of microdescriptors:
  212. 1) Generated by us while acting as a directory authority.
  213. 2) Loaded from the cache on disk.
  214. 3) Downloaded.
  215. */
  216. /** Decode the microdescriptors from the string starting at <b>s</b> and
  217. * ending at <b>eos</b>, and store them in <b>cache</b>. If <b>no_save</b>,
  218. * mark them as non-writable to disk. If <b>where</b> is SAVED_IN_CACHE,
  219. * leave their bodies as pointers to the mmap'd cache. If where is
  220. * <b>SAVED_NOWHERE</b>, do not allow annotations. If listed_at is not -1,
  221. * set the last_listed field of every microdesc to listed_at. If
  222. * requested_digests is non-null, then it contains a list of digests we mean
  223. * to allow, so we should reject any non-requested microdesc with a different
  224. * digest, and alter the list to contain only the digests of those microdescs
  225. * we didn't find.
  226. * Return a newly allocated list of the added microdescriptors, or NULL */
  227. smartlist_t *
  228. microdescs_add_to_cache(microdesc_cache_t *cache,
  229. const char *s, const char *eos, saved_location_t where,
  230. int no_save, time_t listed_at,
  231. smartlist_t *requested_digests256)
  232. {
  233. void * const DIGEST_REQUESTED = (void*)1;
  234. void * const DIGEST_RECEIVED = (void*)2;
  235. void * const DIGEST_INVALID = (void*)3;
  236. smartlist_t *descriptors, *added;
  237. const int allow_annotations = (where != SAVED_NOWHERE);
  238. smartlist_t *invalid_digests = smartlist_new();
  239. descriptors = microdescs_parse_from_string(s, eos,
  240. allow_annotations,
  241. where, invalid_digests);
  242. if (listed_at != (time_t)-1) {
  243. SMARTLIST_FOREACH(descriptors, microdesc_t *, md,
  244. md->last_listed = listed_at);
  245. }
  246. if (requested_digests256) {
  247. digest256map_t *requested;
  248. requested = digest256map_new();
  249. /* Set requested[d] to DIGEST_REQUESTED for every md we requested. */
  250. SMARTLIST_FOREACH(requested_digests256, const uint8_t *, cp,
  251. digest256map_set(requested, cp, DIGEST_REQUESTED));
  252. /* Set requested[d] to DIGEST_INVALID for every md we requested which we
  253. * will never be able to parse. Remove the ones we didn't request from
  254. * invalid_digests.
  255. */
  256. SMARTLIST_FOREACH_BEGIN(invalid_digests, uint8_t *, cp) {
  257. if (digest256map_get(requested, cp)) {
  258. digest256map_set(requested, cp, DIGEST_INVALID);
  259. } else {
  260. tor_free(cp);
  261. SMARTLIST_DEL_CURRENT(invalid_digests, cp);
  262. }
  263. } SMARTLIST_FOREACH_END(cp);
  264. /* Update requested[d] to 2 for the mds we asked for and got. Delete the
  265. * ones we never requested from the 'descriptors' smartlist.
  266. */
  267. SMARTLIST_FOREACH_BEGIN(descriptors, microdesc_t *, md) {
  268. if (digest256map_get(requested, (const uint8_t*)md->digest)) {
  269. digest256map_set(requested, (const uint8_t*)md->digest,
  270. DIGEST_RECEIVED);
  271. } else {
  272. log_fn(LOG_PROTOCOL_WARN, LD_DIR, "Received non-requested microdesc");
  273. microdesc_free(md);
  274. SMARTLIST_DEL_CURRENT(descriptors, md);
  275. }
  276. } SMARTLIST_FOREACH_END(md);
  277. /* Remove the ones we got or the invalid ones from requested_digests256.
  278. */
  279. SMARTLIST_FOREACH_BEGIN(requested_digests256, uint8_t *, cp) {
  280. void *status = digest256map_get(requested, cp);
  281. if (status == DIGEST_RECEIVED || status == DIGEST_INVALID) {
  282. tor_free(cp);
  283. SMARTLIST_DEL_CURRENT(requested_digests256, cp);
  284. }
  285. } SMARTLIST_FOREACH_END(cp);
  286. digest256map_free(requested, NULL);
  287. }
  288. /* For every requested microdescriptor that was unparseable, mark it
  289. * as not to be retried. */
  290. if (smartlist_len(invalid_digests)) {
  291. networkstatus_t *ns =
  292. networkstatus_get_latest_consensus_by_flavor(FLAV_MICRODESC);
  293. if (ns) {
  294. SMARTLIST_FOREACH_BEGIN(invalid_digests, char *, d) {
  295. routerstatus_t *rs =
  296. router_get_mutable_consensus_status_by_descriptor_digest(ns, d);
  297. if (rs && tor_memeq(d, rs->descriptor_digest, DIGEST256_LEN)) {
  298. download_status_mark_impossible(&rs->dl_status);
  299. }
  300. } SMARTLIST_FOREACH_END(d);
  301. }
  302. }
  303. SMARTLIST_FOREACH(invalid_digests, uint8_t *, d, tor_free(d));
  304. smartlist_free(invalid_digests);
  305. added = microdescs_add_list_to_cache(cache, descriptors, where, no_save);
  306. smartlist_free(descriptors);
  307. return added;
  308. }
  309. /** As microdescs_add_to_cache, but takes a list of microdescriptors instead of
  310. * a string to decode. Frees any members of <b>descriptors</b> that it does
  311. * not add. */
  312. smartlist_t *
  313. microdescs_add_list_to_cache(microdesc_cache_t *cache,
  314. smartlist_t *descriptors, saved_location_t where,
  315. int no_save)
  316. {
  317. smartlist_t *added;
  318. open_file_t *open_file = NULL;
  319. int fd = -1;
  320. // int n_added = 0;
  321. ssize_t size = 0;
  322. if (where == SAVED_NOWHERE && !no_save) {
  323. fd = start_writing_to_file(cache->journal_fname,
  324. OPEN_FLAGS_APPEND|O_BINARY,
  325. 0600, &open_file);
  326. if (fd < 0) {
  327. log_warn(LD_DIR, "Couldn't append to journal in %s: %s",
  328. cache->journal_fname, strerror(errno));
  329. }
  330. }
  331. added = smartlist_new();
  332. SMARTLIST_FOREACH_BEGIN(descriptors, microdesc_t *, md) {
  333. microdesc_t *md2;
  334. md2 = HT_FIND(microdesc_map, &cache->map, md);
  335. if (md2) {
  336. /* We already had this one. */
  337. if (md2->last_listed < md->last_listed)
  338. md2->last_listed = md->last_listed;
  339. microdesc_free(md);
  340. if (where != SAVED_NOWHERE)
  341. cache->bytes_dropped += size;
  342. continue;
  343. }
  344. /* Okay, it's a new one. */
  345. if (fd >= 0) {
  346. size_t annotation_len;
  347. size = dump_microdescriptor(fd, md, &annotation_len);
  348. if (size < 0) {
  349. /* we already warned in dump_microdescriptor */
  350. abort_writing_to_file(open_file);
  351. fd = -1;
  352. } else {
  353. md->saved_location = SAVED_IN_JOURNAL;
  354. cache->journal_len += size;
  355. }
  356. } else {
  357. md->saved_location = where;
  358. }
  359. md->no_save = no_save;
  360. HT_INSERT(microdesc_map, &cache->map, md);
  361. md->held_in_map = 1;
  362. smartlist_add(added, md);
  363. ++cache->n_seen;
  364. cache->total_len_seen += md->bodylen;
  365. } SMARTLIST_FOREACH_END(md);
  366. if (fd >= 0) {
  367. if (finish_writing_to_file(open_file) < 0) {
  368. log_warn(LD_DIR, "Error appending to microdescriptor file: %s",
  369. strerror(errno));
  370. smartlist_clear(added);
  371. return added;
  372. }
  373. }
  374. {
  375. networkstatus_t *ns = networkstatus_get_latest_consensus();
  376. if (ns && ns->flavor == FLAV_MICRODESC)
  377. SMARTLIST_FOREACH(added, microdesc_t *, md, nodelist_add_microdesc(md));
  378. }
  379. if (smartlist_len(added))
  380. router_dir_info_changed();
  381. return added;
  382. }
  383. /** Remove every microdescriptor in <b>cache</b>. */
  384. void
  385. microdesc_cache_clear(microdesc_cache_t *cache)
  386. {
  387. microdesc_t **entry, **next;
  388. for (entry = HT_START(microdesc_map, &cache->map); entry; entry = next) {
  389. microdesc_t *md = *entry;
  390. next = HT_NEXT_RMV(microdesc_map, &cache->map, entry);
  391. md->held_in_map = 0;
  392. microdesc_free(md);
  393. }
  394. HT_CLEAR(microdesc_map, &cache->map);
  395. if (cache->cache_content) {
  396. int res = tor_munmap_file(cache->cache_content);
  397. if (res != 0) {
  398. log_warn(LD_FS,
  399. "tor_munmap_file() failed clearing microdesc cache; "
  400. "we are probably about to leak memory.");
  401. /* TODO something smarter? */
  402. }
  403. cache->cache_content = NULL;
  404. }
  405. cache->total_len_seen = 0;
  406. cache->n_seen = 0;
  407. cache->bytes_dropped = 0;
  408. }
  409. /** Reload the contents of <b>cache</b> from disk. If it is empty, load it
  410. * for the first time. Return 0 on success, -1 on failure. */
  411. int
  412. microdesc_cache_reload(microdesc_cache_t *cache)
  413. {
  414. struct stat st;
  415. char *journal_content;
  416. smartlist_t *added;
  417. tor_mmap_t *mm;
  418. int total = 0;
  419. microdesc_cache_clear(cache);
  420. cache->is_loaded = 1;
  421. mm = cache->cache_content = tor_mmap_file(cache->cache_fname);
  422. if (mm) {
  423. added = microdescs_add_to_cache(cache, mm->data, mm->data+mm->size,
  424. SAVED_IN_CACHE, 0, -1, NULL);
  425. if (added) {
  426. total += smartlist_len(added);
  427. smartlist_free(added);
  428. }
  429. }
  430. journal_content = read_file_to_str(cache->journal_fname,
  431. RFTS_IGNORE_MISSING, &st);
  432. if (journal_content) {
  433. cache->journal_len = (size_t) st.st_size;
  434. added = microdescs_add_to_cache(cache, journal_content,
  435. journal_content+st.st_size,
  436. SAVED_IN_JOURNAL, 0, -1, NULL);
  437. if (added) {
  438. total += smartlist_len(added);
  439. smartlist_free(added);
  440. }
  441. tor_free(journal_content);
  442. }
  443. log_info(LD_DIR, "Reloaded microdescriptor cache. Found %d descriptors.",
  444. total);
  445. microdesc_cache_rebuild(cache, 0 /* don't force */);
  446. return 0;
  447. }
  448. /** By default, we remove any microdescriptors that have gone at least this
  449. * long without appearing in a current consensus. */
  450. #define TOLERATE_MICRODESC_AGE (7*24*60*60)
  451. /** Remove all microdescriptors from <b>cache</b> that haven't been listed for
  452. * a long time. Does not rebuild the cache on disk. If <b>cutoff</b> is
  453. * positive, specifically remove microdescriptors that have been unlisted
  454. * since <b>cutoff</b>. If <b>force</b> is true, remove microdescriptors even
  455. * if we have no current live microdescriptor consensus.
  456. */
  457. void
  458. microdesc_cache_clean(microdesc_cache_t *cache, time_t cutoff, int force)
  459. {
  460. microdesc_t **mdp, *victim;
  461. int dropped=0, kept=0;
  462. size_t bytes_dropped = 0;
  463. time_t now = time(NULL);
  464. /* If we don't know a live consensus, don't believe last_listed values: we
  465. * might be starting up after being down for a while. */
  466. if (! force &&
  467. ! networkstatus_get_reasonably_live_consensus(now, FLAV_MICRODESC))
  468. return;
  469. if (cutoff <= 0)
  470. cutoff = now - TOLERATE_MICRODESC_AGE;
  471. for (mdp = HT_START(microdesc_map, &cache->map); mdp != NULL; ) {
  472. const int is_old = (*mdp)->last_listed < cutoff;
  473. const unsigned held_by_nodes = (*mdp)->held_by_nodes;
  474. if (is_old && !held_by_nodes) {
  475. ++dropped;
  476. victim = *mdp;
  477. mdp = HT_NEXT_RMV(microdesc_map, &cache->map, mdp);
  478. victim->held_in_map = 0;
  479. bytes_dropped += victim->bodylen;
  480. microdesc_free(victim);
  481. } else {
  482. if (is_old) {
  483. /* It's old, but it has held_by_nodes set. That's not okay. */
  484. /* Let's try to diagnose and fix #7164 . */
  485. smartlist_t *nodes = nodelist_find_nodes_with_microdesc(*mdp);
  486. const networkstatus_t *ns = networkstatus_get_latest_consensus();
  487. long networkstatus_age = -1;
  488. const int ht_badness = HT_REP_IS_BAD_(microdesc_map, &cache->map);
  489. if (ns) {
  490. networkstatus_age = now - ns->valid_after;
  491. }
  492. log_warn(LD_BUG, "Microdescriptor seemed very old "
  493. "(last listed %d hours ago vs %d hour cutoff), but is still "
  494. "marked as being held by %d node(s). I found %d node(s) "
  495. "holding it. Current networkstatus is %ld hours old. "
  496. "Hashtable badness is %d.",
  497. (int)((now - (*mdp)->last_listed) / 3600),
  498. (int)((now - cutoff) / 3600),
  499. held_by_nodes,
  500. smartlist_len(nodes),
  501. networkstatus_age / 3600,
  502. ht_badness);
  503. SMARTLIST_FOREACH_BEGIN(nodes, const node_t *, node) {
  504. const char *rs_match = "No RS";
  505. const char *rs_present = "";
  506. if (node->rs) {
  507. if (tor_memeq(node->rs->descriptor_digest,
  508. (*mdp)->digest, DIGEST256_LEN)) {
  509. rs_match = "Microdesc digest in RS matches";
  510. } else {
  511. rs_match = "Microdesc digest in RS does match";
  512. }
  513. if (ns) {
  514. /* This should be impossible, but let's see! */
  515. rs_present = " RS not present in networkstatus.";
  516. SMARTLIST_FOREACH(ns->routerstatus_list, routerstatus_t *,rs, {
  517. if (rs == node->rs) {
  518. rs_present = " RS okay in networkstatus.";
  519. }
  520. });
  521. }
  522. }
  523. log_warn(LD_BUG, " [%d]: ID=%s. md=%p, rs=%p, ri=%p. %s.%s",
  524. node_sl_idx,
  525. hex_str(node->identity, DIGEST_LEN),
  526. node->md, node->rs, node->ri, rs_match, rs_present);
  527. } SMARTLIST_FOREACH_END(node);
  528. smartlist_free(nodes);
  529. (*mdp)->last_listed = now;
  530. }
  531. ++kept;
  532. mdp = HT_NEXT(microdesc_map, &cache->map, mdp);
  533. }
  534. }
  535. if (dropped) {
  536. log_info(LD_DIR, "Removed %d/%d microdescriptors as old.",
  537. dropped,dropped+kept);
  538. cache->bytes_dropped += bytes_dropped;
  539. }
  540. }
  541. static int
  542. should_rebuild_md_cache(microdesc_cache_t *cache)
  543. {
  544. const size_t old_len =
  545. cache->cache_content ? cache->cache_content->size : 0;
  546. const size_t journal_len = cache->journal_len;
  547. const size_t dropped = cache->bytes_dropped;
  548. if (journal_len < 16384)
  549. return 0; /* Don't bother, not enough has happened yet. */
  550. if (dropped > (journal_len + old_len) / 3)
  551. return 1; /* We could save 1/3 or more of the currently used space. */
  552. if (journal_len > old_len / 2)
  553. return 1; /* We should append to the regular file */
  554. return 0;
  555. }
  556. /**
  557. * Mark <b>md</b> as having no body, and release any storage previously held
  558. * by its body.
  559. */
  560. static void
  561. microdesc_wipe_body(microdesc_t *md)
  562. {
  563. if (!md)
  564. return;
  565. if (md->saved_location != SAVED_IN_CACHE)
  566. tor_free(md->body);
  567. md->off = 0;
  568. md->saved_location = SAVED_NOWHERE;
  569. md->body = NULL;
  570. md->bodylen = 0;
  571. md->no_save = 1;
  572. }
  573. /** Regenerate the main cache file for <b>cache</b>, clear the journal file,
  574. * and update every microdesc_t in the cache with pointers to its new
  575. * location. If <b>force</b> is true, do this unconditionally. If
  576. * <b>force</b> is false, do it only if we expect to save space on disk. */
  577. int
  578. microdesc_cache_rebuild(microdesc_cache_t *cache, int force)
  579. {
  580. open_file_t *open_file;
  581. int fd = -1, res;
  582. microdesc_t **mdp;
  583. smartlist_t *wrote;
  584. ssize_t size;
  585. off_t off = 0, off_real;
  586. int orig_size, new_size;
  587. if (cache == NULL) {
  588. cache = the_microdesc_cache;
  589. if (cache == NULL)
  590. return 0;
  591. }
  592. /* Remove dead descriptors */
  593. microdesc_cache_clean(cache, 0/*cutoff*/, 0/*force*/);
  594. if (!force && !should_rebuild_md_cache(cache))
  595. return 0;
  596. log_info(LD_DIR, "Rebuilding the microdescriptor cache...");
  597. orig_size = (int)(cache->cache_content ? cache->cache_content->size : 0);
  598. orig_size += (int)cache->journal_len;
  599. fd = start_writing_to_file(cache->cache_fname,
  600. OPEN_FLAGS_REPLACE|O_BINARY,
  601. 0600, &open_file);
  602. if (fd < 0)
  603. return -1;
  604. wrote = smartlist_new();
  605. HT_FOREACH(mdp, microdesc_map, &cache->map) {
  606. microdesc_t *md = *mdp;
  607. size_t annotation_len;
  608. if (md->no_save || !md->body)
  609. continue;
  610. size = dump_microdescriptor(fd, md, &annotation_len);
  611. if (size < 0) {
  612. microdesc_wipe_body(md);
  613. /* rewind, in case it was a partial write. */
  614. tor_fd_setpos(fd, off);
  615. continue;
  616. }
  617. tor_assert(((size_t)size) == annotation_len + md->bodylen);
  618. md->off = off + annotation_len;
  619. off += size;
  620. off_real = tor_fd_getpos(fd);
  621. if (off_real != off) {
  622. log_warn(LD_BUG, "Discontinuity in position in microdescriptor cache."
  623. "By my count, I'm at "I64_FORMAT
  624. ", but I should be at "I64_FORMAT,
  625. I64_PRINTF_ARG(off), I64_PRINTF_ARG(off_real));
  626. if (off_real >= 0)
  627. off = off_real;
  628. }
  629. if (md->saved_location != SAVED_IN_CACHE) {
  630. tor_free(md->body);
  631. md->saved_location = SAVED_IN_CACHE;
  632. }
  633. smartlist_add(wrote, md);
  634. }
  635. /* We must do this unmap _before_ we call finish_writing_to_file(), or
  636. * windows will not actually replace the file. */
  637. if (cache->cache_content) {
  638. res = tor_munmap_file(cache->cache_content);
  639. if (res != 0) {
  640. log_warn(LD_FS,
  641. "Failed to unmap old microdescriptor cache while rebuilding");
  642. }
  643. cache->cache_content = NULL;
  644. }
  645. if (finish_writing_to_file(open_file) < 0) {
  646. log_warn(LD_DIR, "Error rebuilding microdescriptor cache: %s",
  647. strerror(errno));
  648. /* Okay. Let's prevent from making things worse elsewhere. */
  649. cache->cache_content = NULL;
  650. HT_FOREACH(mdp, microdesc_map, &cache->map) {
  651. microdesc_t *md = *mdp;
  652. if (md->saved_location == SAVED_IN_CACHE) {
  653. microdesc_wipe_body(md);
  654. }
  655. }
  656. smartlist_free(wrote);
  657. return -1;
  658. }
  659. cache->cache_content = tor_mmap_file(cache->cache_fname);
  660. if (!cache->cache_content && smartlist_len(wrote)) {
  661. log_err(LD_DIR, "Couldn't map file that we just wrote to %s!",
  662. cache->cache_fname);
  663. smartlist_free(wrote);
  664. return -1;
  665. }
  666. SMARTLIST_FOREACH_BEGIN(wrote, microdesc_t *, md) {
  667. tor_assert(md->saved_location == SAVED_IN_CACHE);
  668. md->body = (char*)cache->cache_content->data + md->off;
  669. if (PREDICT_UNLIKELY(
  670. md->bodylen < 9 || fast_memneq(md->body, "onion-key", 9) != 0)) {
  671. /* XXXX once bug 2022 is solved, we can kill this block and turn it
  672. * into just the tor_assert(fast_memeq) */
  673. off_t avail = cache->cache_content->size - md->off;
  674. char *bad_str;
  675. tor_assert(avail >= 0);
  676. bad_str = tor_strndup(md->body, MIN(128, (size_t)avail));
  677. log_err(LD_BUG, "After rebuilding microdesc cache, offsets seem wrong. "
  678. " At offset %d, I expected to find a microdescriptor starting "
  679. " with \"onion-key\". Instead I got %s.",
  680. (int)md->off, escaped(bad_str));
  681. tor_free(bad_str);
  682. tor_assert(fast_memeq(md->body, "onion-key", 9));
  683. }
  684. } SMARTLIST_FOREACH_END(md);
  685. smartlist_free(wrote);
  686. write_str_to_file(cache->journal_fname, "", 1);
  687. cache->journal_len = 0;
  688. cache->bytes_dropped = 0;
  689. new_size = cache->cache_content ? (int)cache->cache_content->size : 0;
  690. log_info(LD_DIR, "Done rebuilding microdesc cache. "
  691. "Saved %d bytes; %d still used.",
  692. orig_size-new_size, new_size);
  693. return 0;
  694. }
  695. /** Make sure that the reference count of every microdescriptor in cache is
  696. * accurate. */
  697. void
  698. microdesc_check_counts(void)
  699. {
  700. microdesc_t **mdp;
  701. if (!the_microdesc_cache)
  702. return;
  703. HT_FOREACH(mdp, microdesc_map, &the_microdesc_cache->map) {
  704. microdesc_t *md = *mdp;
  705. unsigned int found=0;
  706. const smartlist_t *nodes = nodelist_get_list();
  707. SMARTLIST_FOREACH(nodes, node_t *, node, {
  708. if (node->md == md) {
  709. ++found;
  710. }
  711. });
  712. tor_assert(found == md->held_by_nodes);
  713. }
  714. }
  715. /** Deallocate a single microdescriptor. Note: the microdescriptor MUST have
  716. * previously been removed from the cache if it had ever been inserted. */
  717. void
  718. microdesc_free_(microdesc_t *md, const char *fname, int lineno)
  719. {
  720. if (!md)
  721. return;
  722. /* Make sure that the microdesc was really removed from the appropriate data
  723. structures. */
  724. if (md->held_in_map) {
  725. microdesc_cache_t *cache = get_microdesc_cache_noload();
  726. microdesc_t *md2 = HT_FIND(microdesc_map, &cache->map, md);
  727. if (md2 == md) {
  728. log_warn(LD_BUG, "microdesc_free() called from %s:%d, but md was still "
  729. "in microdesc_map", fname, lineno);
  730. HT_REMOVE(microdesc_map, &cache->map, md);
  731. } else {
  732. log_warn(LD_BUG, "microdesc_free() called from %s:%d with held_in_map "
  733. "set, but microdesc was not in the map.", fname, lineno);
  734. }
  735. tor_fragile_assert();
  736. }
  737. if (md->held_by_nodes) {
  738. microdesc_cache_t *cache = get_microdesc_cache_noload();
  739. int found=0;
  740. const smartlist_t *nodes = nodelist_get_list();
  741. const int ht_badness = HT_REP_IS_BAD_(microdesc_map, &cache->map);
  742. SMARTLIST_FOREACH(nodes, node_t *, node, {
  743. if (node->md == md) {
  744. ++found;
  745. node->md = NULL;
  746. }
  747. });
  748. if (found) {
  749. log_warn(LD_BUG, "microdesc_free() called from %s:%d, but md was still "
  750. "referenced %d node(s); held_by_nodes == %u, ht_badness == %d",
  751. fname, lineno, found, md->held_by_nodes, ht_badness);
  752. } else {
  753. log_warn(LD_BUG, "microdesc_free() called from %s:%d with held_by_nodes "
  754. "set to %u, but md was not referenced by any nodes. "
  755. "ht_badness == %d",
  756. fname, lineno, md->held_by_nodes, ht_badness);
  757. }
  758. tor_fragile_assert();
  759. }
  760. //tor_assert(md->held_in_map == 0);
  761. //tor_assert(md->held_by_nodes == 0);
  762. if (md->onion_pkey)
  763. crypto_pk_free(md->onion_pkey);
  764. tor_free(md->onion_curve25519_pkey);
  765. tor_free(md->ed25519_identity_pkey);
  766. if (md->body && md->saved_location != SAVED_IN_CACHE)
  767. tor_free(md->body);
  768. if (md->family) {
  769. SMARTLIST_FOREACH(md->family, char *, cp, tor_free(cp));
  770. smartlist_free(md->family);
  771. }
  772. short_policy_free(md->exit_policy);
  773. short_policy_free(md->ipv6_exit_policy);
  774. tor_free(md);
  775. }
  776. /** Free all storage held in the microdesc.c module. */
  777. void
  778. microdesc_free_all(void)
  779. {
  780. if (the_microdesc_cache) {
  781. microdesc_cache_clear(the_microdesc_cache);
  782. tor_free(the_microdesc_cache->cache_fname);
  783. tor_free(the_microdesc_cache->journal_fname);
  784. tor_free(the_microdesc_cache);
  785. }
  786. if (outdated_dirserver_list) {
  787. SMARTLIST_FOREACH(outdated_dirserver_list, char *, cp, tor_free(cp));
  788. smartlist_free(outdated_dirserver_list);
  789. }
  790. }
  791. /** If there is a microdescriptor in <b>cache</b> whose sha256 digest is
  792. * <b>d</b>, return it. Otherwise return NULL. */
  793. microdesc_t *
  794. microdesc_cache_lookup_by_digest256(microdesc_cache_t *cache, const char *d)
  795. {
  796. microdesc_t *md, search;
  797. if (!cache)
  798. cache = get_microdesc_cache();
  799. memcpy(search.digest, d, DIGEST256_LEN);
  800. md = HT_FIND(microdesc_map, &cache->map, &search);
  801. return md;
  802. }
  803. /** Return a smartlist of all the sha256 digest of the microdescriptors that
  804. * are listed in <b>ns</b> but not present in <b>cache</b>. Returns pointers
  805. * to internals of <b>ns</b>; you should not free the members of the resulting
  806. * smartlist. Omit all microdescriptors whose digest appear in <b>skip</b>. */
  807. smartlist_t *
  808. microdesc_list_missing_digest256(networkstatus_t *ns, microdesc_cache_t *cache,
  809. int downloadable_only, digest256map_t *skip)
  810. {
  811. smartlist_t *result = smartlist_new();
  812. time_t now = time(NULL);
  813. tor_assert(ns->flavor == FLAV_MICRODESC);
  814. SMARTLIST_FOREACH_BEGIN(ns->routerstatus_list, routerstatus_t *, rs) {
  815. if (microdesc_cache_lookup_by_digest256(cache, rs->descriptor_digest))
  816. continue;
  817. if (downloadable_only &&
  818. !download_status_is_ready(&rs->dl_status, now))
  819. continue;
  820. if (skip && digest256map_get(skip, (const uint8_t*)rs->descriptor_digest))
  821. continue;
  822. if (tor_mem_is_zero(rs->descriptor_digest, DIGEST256_LEN))
  823. continue;
  824. /* XXXX Also skip if we're a noncache and wouldn't use this router.
  825. * XXXX NM Microdesc
  826. */
  827. smartlist_add(result, rs->descriptor_digest);
  828. } SMARTLIST_FOREACH_END(rs);
  829. return result;
  830. }
  831. /** Launch download requests for microdescriptors as appropriate.
  832. *
  833. * Specifically, we should launch download requests if we are configured to
  834. * download mirodescriptors, and there are some microdescriptors listed in the
  835. * current microdesc consensus that we don't have, and either we never asked
  836. * for them, or we failed to download them but we're willing to retry.
  837. */
  838. void
  839. update_microdesc_downloads(time_t now)
  840. {
  841. const or_options_t *options = get_options();
  842. networkstatus_t *consensus;
  843. smartlist_t *missing;
  844. digest256map_t *pending;
  845. if (should_delay_dir_fetches(options, NULL))
  846. return;
  847. if (directory_too_idle_to_fetch_descriptors(options, now))
  848. return;
  849. consensus = networkstatus_get_reasonably_live_consensus(now, FLAV_MICRODESC);
  850. if (!consensus)
  851. return;
  852. if (!we_fetch_microdescriptors(options))
  853. return;
  854. pending = digest256map_new();
  855. list_pending_microdesc_downloads(pending);
  856. missing = microdesc_list_missing_digest256(consensus,
  857. get_microdesc_cache(),
  858. 1,
  859. pending);
  860. digest256map_free(pending, NULL);
  861. launch_descriptor_downloads(DIR_PURPOSE_FETCH_MICRODESC,
  862. missing, NULL, now);
  863. smartlist_free(missing);
  864. }
  865. /** For every microdescriptor listed in the current microdescriptor consensus,
  866. * update its last_listed field to be at least as recent as the publication
  867. * time of the current microdescriptor consensus.
  868. */
  869. void
  870. update_microdescs_from_networkstatus(time_t now)
  871. {
  872. microdesc_cache_t *cache = get_microdesc_cache();
  873. microdesc_t *md;
  874. networkstatus_t *ns =
  875. networkstatus_get_reasonably_live_consensus(now, FLAV_MICRODESC);
  876. if (! ns)
  877. return;
  878. tor_assert(ns->flavor == FLAV_MICRODESC);
  879. SMARTLIST_FOREACH_BEGIN(ns->routerstatus_list, routerstatus_t *, rs) {
  880. md = microdesc_cache_lookup_by_digest256(cache, rs->descriptor_digest);
  881. if (md && ns->valid_after > md->last_listed)
  882. md->last_listed = ns->valid_after;
  883. } SMARTLIST_FOREACH_END(rs);
  884. }
  885. /** Return true iff we should prefer to use microdescriptors rather than
  886. * routerdescs for building circuits. */
  887. int
  888. we_use_microdescriptors_for_circuits(const or_options_t *options)
  889. {
  890. if (options->UseMicrodescriptors == 0)
  891. return 0; /* the user explicitly picked no */
  892. return 1; /* yes and auto both mean yes */
  893. }
  894. /** Return true iff we should try to download microdescriptors at all. */
  895. int
  896. we_fetch_microdescriptors(const or_options_t *options)
  897. {
  898. if (directory_caches_dir_info(options))
  899. return 1;
  900. if (options->FetchUselessDescriptors)
  901. return 1;
  902. return we_use_microdescriptors_for_circuits(options);
  903. }
  904. /** Return true iff we should try to download router descriptors at all. */
  905. int
  906. we_fetch_router_descriptors(const or_options_t *options)
  907. {
  908. if (directory_caches_dir_info(options))
  909. return 1;
  910. if (options->FetchUselessDescriptors)
  911. return 1;
  912. return ! we_use_microdescriptors_for_circuits(options);
  913. }
  914. /** Return the consensus flavor we actually want to use to build circuits. */
  915. MOCK_IMPL(int,
  916. usable_consensus_flavor,(void))
  917. {
  918. if (we_use_microdescriptors_for_circuits(get_options())) {
  919. return FLAV_MICRODESC;
  920. } else {
  921. return FLAV_NS;
  922. }
  923. }