Tor  0.4.3.1-alpha-dev
routerlist.c
Go to the documentation of this file.
1 /* Copyright (c) 2001 Matej Pfajfar.
2  * Copyright (c) 2001-2004, Roger Dingledine.
3  * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
4  * Copyright (c) 2007-2020, The Tor Project, Inc. */
5 /* See LICENSE for licensing information */
6 
7 /**
8  * \file routerlist.c
9  * \brief Code to
10  * maintain and access the global list of routerinfos for known
11  * servers.
12  *
13  * A "routerinfo_t" object represents a single self-signed router
14  * descriptor, as generated by a Tor relay in order to tell the rest of
15  * the world about its keys, address, and capabilities. An
16  * "extrainfo_t" object represents an adjunct "extra-info" object,
17  * certified by a corresponding router descriptor, reporting more
18  * information about the relay that nearly all users will not need.
19  *
20  * Most users will not use router descriptors for most relays. Instead,
21  * they use the information in microdescriptors and in the consensus
22  * networkstatus.
23  *
24  * Right now, routerinfo_t objects are used in these ways:
25  * <ul>
26  * <li>By clients, in order to learn about bridge keys and capabilities.
27  * (Bridges aren't listed in the consensus networkstatus, so they
28  * can't have microdescriptors.)
29  * <li>By relays, since relays want more information about other relays
30  * than they can learn from microdescriptors. (TODO: Is this still true?)
31  * <li>By authorities, which receive them and use them to generate the
32  * consensus and the microdescriptors.
33  * <li>By all directory caches, which download them in case somebody
34  * else wants them.
35  * </ul>
36  *
37  * Routerinfos are mostly created by parsing them from a string, in
38  * routerparse.c. We store them to disk on receiving them, and
39  * periodically discard the ones we don't need. On restarting, we
40  * re-read them from disk. (This also applies to extrainfo documents, if
41  * we are configured to fetch them.)
42  *
43  * In order to keep our list of routerinfos up-to-date, we periodically
44  * check whether there are any listed in the latest consensus (or in the
45  * votes from other authorities, if we are an authority) that we don't
46  * have. (This also applies to extrainfo documents, if we are
47  * configured to fetch them.)
48  *
49  * Almost nothing in Tor should use a routerinfo_t to refer directly to
50  * a relay; instead, almost everything should use node_t (implemented in
51  * nodelist.c), which provides a common interface to routerinfo_t,
52  * routerstatus_t, and microdescriptor_t.
53  *
54  * <br>
55  *
56  * This module also has some of the functions used for choosing random
57  * nodes according to different rules and weights. Historically, they
58  * were all in this module. Now, they are spread across this module,
59  * nodelist.c, and networkstatus.c. (TODO: Fix that.)
60  **/
61 
62 #define ROUTERLIST_PRIVATE
63 #include "core/or/or.h"
64 
65 #include "app/config/config.h"
67 #include "core/mainloop/mainloop.h"
68 #include "core/or/policies.h"
69 #include "feature/client/bridges.h"
92 #include "feature/stats/rephist.h"
95 
106 
107 #include "lib/crypt_ops/digestset.h"
108 
109 #ifdef HAVE_SYS_STAT_H
110 #include <sys/stat.h>
111 #endif
112 
113 // #define DEBUG_ROUTERLIST
114 
115 /****************************************************************************/
116 
117 /* Typed wrappers for different digestmap types; used to avoid type
118  * confusion. */
119 
120 DECLARE_TYPED_DIGESTMAP_FNS(sdmap_, digest_sd_map_t, signed_descriptor_t)
121 DECLARE_TYPED_DIGESTMAP_FNS(rimap_, digest_ri_map_t, routerinfo_t)
122 DECLARE_TYPED_DIGESTMAP_FNS(eimap_, digest_ei_map_t, extrainfo_t)
123 #define SDMAP_FOREACH(map, keyvar, valvar) \
124  DIGESTMAP_FOREACH(sdmap_to_digestmap(map), keyvar, signed_descriptor_t *, \
125  valvar)
126 #define RIMAP_FOREACH(map, keyvar, valvar) \
127  DIGESTMAP_FOREACH(rimap_to_digestmap(map), keyvar, routerinfo_t *, valvar)
128 #define EIMAP_FOREACH(map, keyvar, valvar) \
129  DIGESTMAP_FOREACH(eimap_to_digestmap(map), keyvar, extrainfo_t *, valvar)
130 #define eimap_free(map, fn) MAP_FREE_AND_NULL(eimap, (map), (fn))
131 #define rimap_free(map, fn) MAP_FREE_AND_NULL(rimap, (map), (fn))
132 #define sdmap_free(map, fn) MAP_FREE_AND_NULL(sdmap, (map), (fn))
133 
134 /* static function prototypes */
136 static const char *signed_descriptor_get_body_impl(
137  const signed_descriptor_t *desc,
138  int with_annotations);
139 static void launch_dummy_descriptor_download_as_needed(time_t now,
140  const or_options_t *options);
141 
142 /****************************************************************************/
143 
144 /** Global list of all of the routers that we know about. */
145 static routerlist_t *routerlist = NULL;
146 
147 /** List of strings for nicknames we've already warned about and that are
148  * still unknown / unavailable. */
150 
151 /** The last time we tried to download any routerdesc, or 0 for "never". We
152  * use this to rate-limit download attempts when the number of routerdescs to
153  * download is low. */
155 
156 /* Router descriptor storage.
157  *
158  * Routerdescs are stored in a big file, named "cached-descriptors". As new
159  * routerdescs arrive, we append them to a journal file named
160  * "cached-descriptors.new".
161  *
162  * From time to time, we replace "cached-descriptors" with a new file
163  * containing only the live, non-superseded descriptors, and clear
164  * cached-descriptors.new.
165  *
166  * On startup, we read both files.
167  */
168 
169 /** Helper: return 1 iff the router log is so big we want to rebuild the
170  * store. */
171 static int
173 {
174  if (store->store_len > (1<<16))
175  return (store->journal_len > store->store_len / 2 ||
176  store->bytes_dropped > store->store_len / 2);
177  else
178  return store->journal_len > (1<<15);
179 }
180 
181 /** Return the desc_store_t in <b>rl</b> that should be used to store
182  * <b>sd</b>. */
183 static inline desc_store_t *
185 {
186  if (sd->is_extrainfo)
187  return &rl->extrainfo_store;
188  else
189  return &rl->desc_store;
190 }
191 
192 /** Add the signed_descriptor_t in <b>desc</b> to the router
193  * journal; change its saved_location to SAVED_IN_JOURNAL and set its
194  * offset appropriately. */
195 static int
197  desc_store_t *store)
198 {
199  char *fname = get_cachedir_fname_suffix(store->fname_base, ".new");
200  const char *body = signed_descriptor_get_body_impl(desc,1);
201  size_t len = desc->signed_descriptor_len + desc->annotations_len;
202 
203  if (append_bytes_to_file(fname, body, len, 1)) {
204  log_warn(LD_FS, "Unable to store router descriptor");
205  tor_free(fname);
206  return -1;
207  }
209  tor_free(fname);
210 
211  desc->saved_offset = store->journal_len;
212  store->journal_len += len;
213 
214  return 0;
215 }
216 
217 /** Sorting helper: return &lt;0, 0, or &gt;0 depending on whether the
218  * signed_descriptor_t* in *<b>a</b> is older, the same age as, or newer than
219  * the signed_descriptor_t* in *<b>b</b>. */
220 static int
221 compare_signed_descriptors_by_age_(const void **_a, const void **_b)
222 {
223  const signed_descriptor_t *r1 = *_a, *r2 = *_b;
224  return (int)(r1->published_on - r2->published_on);
225 }
226 
227 #define RRS_FORCE 1
228 #define RRS_DONT_REMOVE_OLD 2
229 
230 /** If the journal of <b>store</b> is too long, or if RRS_FORCE is set in
231  * <b>flags</b>, then atomically replace the saved router store with the
232  * routers currently in our routerlist, and clear the journal. Unless
233  * RRS_DONT_REMOVE_OLD is set in <b>flags</b>, delete expired routers before
234  * rebuilding the store. Return 0 on success, -1 on failure.
235  */
236 static int
238 {
239  smartlist_t *chunk_list = NULL;
240  char *fname = NULL, *fname_tmp = NULL;
241  int r = -1;
242  off_t offset = 0;
243  smartlist_t *signed_descriptors = NULL;
244  int nocache=0;
245  size_t total_expected_len = 0;
246  int had_any;
247  int force = flags & RRS_FORCE;
248 
249  if (!force && !router_should_rebuild_store(store)) {
250  r = 0;
251  goto done;
252  }
253  if (!routerlist) {
254  r = 0;
255  goto done;
256  }
257 
258  if (store->type == EXTRAINFO_STORE)
259  had_any = !eimap_isempty(routerlist->extra_info_map);
260  else
261  had_any = (smartlist_len(routerlist->routers)+
262  smartlist_len(routerlist->old_routers))>0;
263 
264  /* Don't save deadweight. */
265  if (!(flags & RRS_DONT_REMOVE_OLD))
267 
268  log_info(LD_DIR, "Rebuilding %s cache", store->description);
269 
270  fname = get_cachedir_fname(store->fname_base);
271  fname_tmp = get_cachedir_fname_suffix(store->fname_base, ".tmp");
272 
273  chunk_list = smartlist_new();
274 
275  /* We sort the routers by age to enhance locality on disk. */
276  signed_descriptors = smartlist_new();
277  if (store->type == EXTRAINFO_STORE) {
278  eimap_iter_t *iter;
279  for (iter = eimap_iter_init(routerlist->extra_info_map);
280  !eimap_iter_done(iter);
281  iter = eimap_iter_next(routerlist->extra_info_map, iter)) {
282  const char *key;
283  extrainfo_t *ei;
284  eimap_iter_get(iter, &key, &ei);
285  smartlist_add(signed_descriptors, &ei->cache_info);
286  }
287  } else {
289  smartlist_add(signed_descriptors, sd));
291  smartlist_add(signed_descriptors, &ri->cache_info));
292  }
293 
295 
296  /* Now, add the appropriate members to chunk_list */
297  SMARTLIST_FOREACH_BEGIN(signed_descriptors, signed_descriptor_t *, sd) {
298  sized_chunk_t *c;
299  const char *body = signed_descriptor_get_body_impl(sd, 1);
300  if (!body) {
301  log_warn(LD_BUG, "No descriptor available for router.");
302  goto done;
303  }
304  if (sd->do_not_cache) {
305  ++nocache;
306  continue;
307  }
308  c = tor_malloc(sizeof(sized_chunk_t));
309  c->bytes = body;
310  c->len = sd->signed_descriptor_len + sd->annotations_len;
311  total_expected_len += c->len;
312  smartlist_add(chunk_list, c);
313  } SMARTLIST_FOREACH_END(sd);
314 
315  if (write_chunks_to_file(fname_tmp, chunk_list, 1, 1)<0) {
316  log_warn(LD_FS, "Error writing router store to disk.");
317  goto done;
318  }
319 
320  /* Our mmap is now invalid. */
321  if (store->mmap) {
322  int res = tor_munmap_file(store->mmap);
323  store->mmap = NULL;
324  if (res != 0) {
325  log_warn(LD_FS, "Unable to munmap route store in %s", fname);
326  }
327  }
328 
329  if (replace_file(fname_tmp, fname)<0) {
330  log_warn(LD_FS, "Error replacing old router store: %s", strerror(errno));
331  goto done;
332  }
333 
334  errno = 0;
335  store->mmap = tor_mmap_file(fname);
336  if (! store->mmap) {
337  if (errno == ERANGE) {
338  /* empty store.*/
339  if (total_expected_len) {
340  log_warn(LD_FS, "We wrote some bytes to a new descriptor file at '%s',"
341  " but when we went to mmap it, it was empty!", fname);
342  } else if (had_any) {
343  log_info(LD_FS, "We just removed every descriptor in '%s'. This is "
344  "okay if we're just starting up after a long time. "
345  "Otherwise, it's a bug.", fname);
346  }
347  } else {
348  log_warn(LD_FS, "Unable to mmap new descriptor file at '%s'.",fname);
349  }
350  }
351 
352  log_info(LD_DIR, "Reconstructing pointers into cache");
353 
354  offset = 0;
355  SMARTLIST_FOREACH_BEGIN(signed_descriptors, signed_descriptor_t *, sd) {
356  if (sd->do_not_cache)
357  continue;
358  sd->saved_location = SAVED_IN_CACHE;
359  if (store->mmap) {
360  tor_free(sd->signed_descriptor_body); // sets it to null
361  sd->saved_offset = offset;
362  }
363  offset += sd->signed_descriptor_len + sd->annotations_len;
364  signed_descriptor_get_body(sd); /* reconstruct and assert */
365  } SMARTLIST_FOREACH_END(sd);
366 
367  tor_free(fname);
368  fname = get_cachedir_fname_suffix(store->fname_base, ".new");
369  write_str_to_file(fname, "", 1);
370 
371  r = 0;
372  store->store_len = (size_t) offset;
373  store->journal_len = 0;
374  store->bytes_dropped = 0;
375  done:
376  smartlist_free(signed_descriptors);
377  tor_free(fname);
378  tor_free(fname_tmp);
379  if (chunk_list) {
380  SMARTLIST_FOREACH(chunk_list, sized_chunk_t *, c, tor_free(c));
381  smartlist_free(chunk_list);
382  }
383 
384  return r;
385 }
386 
387 /** Helper: Reload a cache file and its associated journal, setting metadata
388  * appropriately. If <b>extrainfo</b> is true, reload the extrainfo store;
389  * else reload the router descriptor store. */
390 static int
392 {
393  char *fname = NULL, *contents = NULL;
394  struct stat st;
395  int extrainfo = (store->type == EXTRAINFO_STORE);
396  store->journal_len = store->store_len = 0;
397 
398  fname = get_cachedir_fname(store->fname_base);
399 
400  if (store->mmap) {
401  /* get rid of it first */
402  int res = tor_munmap_file(store->mmap);
403  store->mmap = NULL;
404  if (res != 0) {
405  log_warn(LD_FS, "Failed to munmap %s", fname);
406  tor_free(fname);
407  return -1;
408  }
409  }
410 
411  store->mmap = tor_mmap_file(fname);
412  if (store->mmap) {
413  store->store_len = store->mmap->size;
414  if (extrainfo)
416  store->mmap->data+store->mmap->size,
417  SAVED_IN_CACHE, NULL, 0);
418  else
420  store->mmap->data+store->mmap->size,
421  SAVED_IN_CACHE, NULL, 0, NULL);
422  }
423 
424  tor_free(fname);
425  fname = get_cachedir_fname_suffix(store->fname_base, ".new");
426  /* don't load empty files - we wouldn't get any data, even if we tried */
427  if (file_status(fname) == FN_FILE)
428  contents = read_file_to_str(fname, RFTS_BIN|RFTS_IGNORE_MISSING, &st);
429  if (contents) {
430  if (extrainfo)
432  NULL, 0);
433  else
435  NULL, 0, NULL);
436  store->journal_len = (size_t) st.st_size;
437  tor_free(contents);
438  }
439 
440  tor_free(fname);
441 
442  if (store->journal_len) {
443  /* Always clear the journal on startup.*/
444  router_rebuild_store(RRS_FORCE, store);
445  } else if (!extrainfo) {
446  /* Don't cache expired routers. (This is in an else because
447  * router_rebuild_store() also calls remove_old_routers().) */
449  }
450 
451  return 0;
452 }
453 
454 /** Load all cached router descriptors and extra-info documents from the
455  * store. Return 0 on success and -1 on failure.
456  */
457 int
459 {
462  return -1;
464  return -1;
465  return 0;
466 }
467 
468 /* When iterating through the routerlist, can OR address/port preference
469  * and reachability checks be skipped?
470  */
471 int
472 router_skip_or_reachability(const or_options_t *options, int try_ip_pref)
473 {
474  /* Servers always have and prefer IPv4.
475  * And if clients are checking against the firewall for reachability only,
476  * but there's no firewall, don't bother checking */
477  return server_mode(options) || (!try_ip_pref && !firewall_is_fascist_or());
478 }
479 
480 /* When iterating through the routerlist, can Dir address/port preference
481  * and reachability checks be skipped?
482  */
483 int
484 router_skip_dir_reachability(const or_options_t *options, int try_ip_pref)
485 {
486  /* Servers always have and prefer IPv4.
487  * And if clients are checking against the firewall for reachability only,
488  * but there's no firewall, don't bother checking */
489  return server_mode(options) || (!try_ip_pref && !firewall_is_fascist_dir());
490 }
491 
492 /** Return true iff r1 and r2 have the same address and OR port. */
493 int
495 {
496  return r1->addr == r2->addr && r1->or_port == r2->or_port &&
497  tor_addr_eq(&r1->ipv6_addr, &r2->ipv6_addr) &&
498  r1->ipv6_orport == r2->ipv6_orport;
499 }
500 
501 /** Add every suitable node from our nodelist to <b>sl</b>, so that
502  * we can pick a node for a circuit.
503  */
504 void
506  int need_capacity, int need_guard,
507  int need_desc, int pref_addr,
508  int direct_conn)
509 {
510  const int check_reach = !router_skip_or_reachability(get_options(),
511  pref_addr);
512  /* XXXX MOVE */
514  if (!node->is_running || !node->is_valid)
515  continue;
516  if (need_desc && !node_has_preferred_descriptor(node, direct_conn))
517  continue;
518  if (node->ri && node->ri->purpose != ROUTER_PURPOSE_GENERAL)
519  continue;
520  if (node_is_unreliable(node, need_uptime, need_capacity, need_guard))
521  continue;
522  /* Don't choose nodes if we are certain they can't do EXTEND2 cells */
523  if (node->rs && !routerstatus_version_supports_extend2_cells(node->rs, 1))
524  continue;
525  /* Don't choose nodes if we are certain they can't do ntor. */
526  if ((node->ri || node->md) && !node_has_curve25519_onion_key(node))
527  continue;
528  /* Choose a node with an OR address that matches the firewall rules */
529  if (direct_conn && check_reach &&
531  FIREWALL_OR_CONNECTION,
532  pref_addr))
533  continue;
534 
535  smartlist_add(sl, (void *)node);
536  } SMARTLIST_FOREACH_END(node);
537 }
538 
539 /** Look through the routerlist until we find a router that has my key.
540  Return it. */
541 const routerinfo_t *
543 {
544  if (!routerlist)
545  return NULL;
546 
548  {
549  if (router_is_me(router))
550  return router;
551  });
552  return NULL;
553 }
554 
555 /** Return the smaller of the router's configured BandwidthRate
556  * and its advertised capacity. */
557 uint32_t
559 {
560  if (router->bandwidthcapacity < router->bandwidthrate)
561  return router->bandwidthcapacity;
562  return router->bandwidthrate;
563 }
564 
565 /** Do not weight any declared bandwidth more than this much when picking
566  * routers by bandwidth. */
567 #define DEFAULT_MAX_BELIEVABLE_BANDWIDTH 10000000 /* 10 MB/sec */
568 
569 /** Return the smaller of the router's configured BandwidthRate
570  * and its advertised capacity, capped by max-believe-bw. */
571 uint32_t
573 {
574  uint32_t result = router->bandwidthcapacity;
575  if (result > router->bandwidthrate)
576  result = router->bandwidthrate;
579  return result;
580 }
581 
582 /** Helper: given an extended nickname in <b>hexdigest</b> try to decode it.
583  * Return 0 on success, -1 on failure. Store the result into the
584  * DIGEST_LEN-byte buffer at <b>digest_out</b>, the single character at
585  * <b>nickname_qualifier_char_out</b>, and the MAXNICKNAME_LEN+1-byte buffer
586  * at <b>nickname_out</b>.
587  *
588  * The recognized format is:
589  * HexName = Dollar? HexDigest NamePart?
590  * Dollar = '?'
591  * HexDigest = HexChar*20
592  * HexChar = 'a'..'f' | 'A'..'F' | '0'..'9'
593  * NamePart = QualChar Name
594  * QualChar = '=' | '~'
595  * Name = NameChar*(1..MAX_NICKNAME_LEN)
596  * NameChar = Any ASCII alphanumeric character
597  */
598 int
599 hex_digest_nickname_decode(const char *hexdigest,
600  char *digest_out,
601  char *nickname_qualifier_char_out,
602  char *nickname_out)
603 {
604  size_t len;
605 
606  tor_assert(hexdigest);
607  if (hexdigest[0] == '$')
608  ++hexdigest;
609 
610  len = strlen(hexdigest);
611  if (len < HEX_DIGEST_LEN) {
612  return -1;
613  } else if (len > HEX_DIGEST_LEN && (hexdigest[HEX_DIGEST_LEN] == '=' ||
614  hexdigest[HEX_DIGEST_LEN] == '~') &&
615  len <= HEX_DIGEST_LEN+1+MAX_NICKNAME_LEN) {
616  *nickname_qualifier_char_out = hexdigest[HEX_DIGEST_LEN];
617  strlcpy(nickname_out, hexdigest+HEX_DIGEST_LEN+1 , MAX_NICKNAME_LEN+1);
618  } else if (len == HEX_DIGEST_LEN) {
619  ;
620  } else {
621  return -1;
622  }
623 
624  if (base16_decode(digest_out, DIGEST_LEN,
625  hexdigest, HEX_DIGEST_LEN) != DIGEST_LEN)
626  return -1;
627  return 0;
628 }
629 
630 /** Helper: Return true iff the <b>identity_digest</b> and <b>nickname</b>
631  * combination of a router, encoded in hexadecimal, matches <b>hexdigest</b>
632  * (which is optionally prefixed with a single dollar sign). Return false if
633  * <b>hexdigest</b> is malformed, or it doesn't match. */
634 int
635 hex_digest_nickname_matches(const char *hexdigest, const char *identity_digest,
636  const char *nickname)
637 {
638  char digest[DIGEST_LEN];
639  char nn_char='\0';
640  char nn_buf[MAX_NICKNAME_LEN+1];
641 
642  if (hex_digest_nickname_decode(hexdigest, digest, &nn_char, nn_buf) == -1)
643  return 0;
644 
645  if (nn_char == '=') {
646  return 0;
647  }
648 
649  if (nn_char == '~') {
650  if (!nickname) // XXX This seems wrong. -NM
651  return 0;
652  if (strcasecmp(nn_buf, nickname))
653  return 0;
654  }
655 
656  return tor_memeq(digest, identity_digest, DIGEST_LEN);
657 }
658 
659 /** If hexdigest is correctly formed, base16_decode it into
660  * digest, which must have DIGEST_LEN space in it.
661  * Return 0 on success, -1 on failure.
662  */
663 int
664 hexdigest_to_digest(const char *hexdigest, char *digest)
665 {
666  if (hexdigest[0]=='$')
667  ++hexdigest;
668  if (strlen(hexdigest) < HEX_DIGEST_LEN ||
669  base16_decode(digest,DIGEST_LEN,hexdigest,HEX_DIGEST_LEN) != DIGEST_LEN)
670  return -1;
671  return 0;
672 }
673 
674 /** As router_get_by_id_digest,but return a pointer that you're allowed to
675  * modify */
676 routerinfo_t *
677 router_get_mutable_by_digest(const char *digest)
678 {
679  tor_assert(digest);
680 
681  if (!routerlist) return NULL;
682 
683  // routerlist_assert_ok(routerlist);
684 
685  return rimap_get(routerlist->identity_map, digest);
686 }
687 
688 /** Return the router in our routerlist whose 20-byte key digest
689  * is <b>digest</b>. Return NULL if no such router is known. */
690 const routerinfo_t *
691 router_get_by_id_digest(const char *digest)
692 {
693  return router_get_mutable_by_digest(digest);
694 }
695 
696 /** Return the router in our routerlist whose 20-byte descriptor
697  * is <b>digest</b>. Return NULL if no such router is known. */
700 {
701  tor_assert(digest);
702 
703  if (!routerlist) return NULL;
704 
705  return sdmap_get(routerlist->desc_digest_map, digest);
706 }
707 
708 /** Return the signed descriptor for the router in our routerlist whose
709  * 20-byte extra-info digest is <b>digest</b>. Return NULL if no such router
710  * is known. */
712 router_get_by_extrainfo_digest,(const char *digest))
713 {
714  tor_assert(digest);
715 
716  if (!routerlist) return NULL;
717 
718  return sdmap_get(routerlist->desc_by_eid_map, digest);
719 }
720 
721 /** Return the signed descriptor for the extrainfo_t in our routerlist whose
722  * extra-info-digest is <b>digest</b>. Return NULL if no such extra-info
723  * document is known. */
726 {
727  extrainfo_t *ei;
728  tor_assert(digest);
729  if (!routerlist) return NULL;
730  ei = eimap_get(routerlist->extra_info_map, digest);
731  return ei ? &ei->cache_info : NULL;
732 }
733 
734 /** Return a pointer to the signed textual representation of a descriptor.
735  * The returned string is not guaranteed to be NUL-terminated: the string's
736  * length will be in desc->signed_descriptor_len.
737  *
738  * If <b>with_annotations</b> is set, the returned string will include
739  * the annotations
740  * (if any) preceding the descriptor. This will increase the length of the
741  * string by desc->annotations_len.
742  *
743  * The caller must not free the string returned.
744  */
745 static const char *
747  int with_annotations)
748 {
749  const char *r = NULL;
750  size_t len = desc->signed_descriptor_len;
751  off_t offset = desc->saved_offset;
752  if (with_annotations)
753  len += desc->annotations_len;
754  else
755  offset += desc->annotations_len;
756 
757  tor_assert(len > 32);
758  if (desc->saved_location == SAVED_IN_CACHE && routerlist) {
760  if (store && store->mmap) {
761  tor_assert(desc->saved_offset + len <= store->mmap->size);
762  r = store->mmap->data + offset;
763  } else if (store) {
764  log_err(LD_DIR, "We couldn't read a descriptor that is supposedly "
765  "mmaped in our cache. Is another process running in our data "
766  "directory? Exiting.");
767  exit(1); // XXXX bad exit: should recover.
768  }
769  }
770  if (!r) /* no mmap, or not in cache. */
771  r = desc->signed_descriptor_body +
772  (with_annotations ? 0 : desc->annotations_len);
773 
774  tor_assert(r);
775  if (!with_annotations) {
776  if (fast_memcmp("router ", r, 7) && fast_memcmp("extra-info ", r, 11)) {
777  char *cp = tor_strndup(r, 64);
778  log_err(LD_DIR, "descriptor at %p begins with unexpected string %s. "
779  "Is another process running in our data directory? Exiting.",
780  desc, escaped(cp));
781  exit(1); // XXXX bad exit: should recover.
782  }
783  }
784 
785  return r;
786 }
787 
788 /** Return a pointer to the signed textual representation of a descriptor.
789  * The returned string is not guaranteed to be NUL-terminated: the string's
790  * length will be in desc->signed_descriptor_len.
791  *
792  * The caller must not free the string returned.
793  */
794 const char *
796 {
797  return signed_descriptor_get_body_impl(desc, 0);
798 }
799 
800 /** As signed_descriptor_get_body(), but points to the beginning of the
801  * annotations section rather than the beginning of the descriptor. */
802 const char *
804 {
805  return signed_descriptor_get_body_impl(desc, 1);
806 }
807 
808 /** Return the current list of all known routers. */
809 routerlist_t *
811 {
812  if (PREDICT_UNLIKELY(!routerlist)) {
813  routerlist = tor_malloc_zero(sizeof(routerlist_t));
816  routerlist->identity_map = rimap_new();
817  routerlist->desc_digest_map = sdmap_new();
818  routerlist->desc_by_eid_map = sdmap_new();
819  routerlist->extra_info_map = eimap_new();
820 
821  routerlist->desc_store.fname_base = "cached-descriptors";
822  routerlist->extrainfo_store.fname_base = "cached-extrainfo";
823 
824  routerlist->desc_store.type = ROUTER_STORE;
825  routerlist->extrainfo_store.type = EXTRAINFO_STORE;
826 
827  routerlist->desc_store.description = "router descriptors";
828  routerlist->extrainfo_store.description = "extra-info documents";
829  }
830  return routerlist;
831 }
832 
833 /** Free all storage held by <b>router</b>. */
834 void
836 {
837  if (!router)
838  return;
839 
840  tor_free(router->cache_info.signed_descriptor_body);
841  tor_free(router->nickname);
842  tor_free(router->platform);
843  tor_free(router->protocol_list);
844  tor_free(router->contact_info);
845  if (router->onion_pkey)
846  tor_free(router->onion_pkey);
848  if (router->identity_pkey)
849  crypto_pk_free(router->identity_pkey);
850  tor_cert_free(router->cache_info.signing_key_cert);
851  if (router->declared_family) {
852  SMARTLIST_FOREACH(router->declared_family, char *, s, tor_free(s));
853  smartlist_free(router->declared_family);
854  }
855  addr_policy_list_free(router->exit_policy);
856  short_policy_free(router->ipv6_exit_policy);
857 
858  memset(router, 77, sizeof(routerinfo_t));
859 
860  tor_free(router);
861 }
862 
863 /** Release all storage held by <b>extrainfo</b> */
864 void
866 {
867  if (!extrainfo)
868  return;
869  tor_cert_free(extrainfo->cache_info.signing_key_cert);
870  tor_free(extrainfo->cache_info.signed_descriptor_body);
871  tor_free(extrainfo->pending_sig);
872 
873  memset(extrainfo, 88, sizeof(extrainfo_t)); /* debug bad memory usage */
874  tor_free(extrainfo);
875 }
876 
877 #define signed_descriptor_free(val) \
878  FREE_AND_NULL(signed_descriptor_t, signed_descriptor_free_, (val))
879 
880 /** Release storage held by <b>sd</b>. */
881 static void
883 {
884  if (!sd)
885  return;
886 
888  tor_cert_free(sd->signing_key_cert);
889 
890  memset(sd, 99, sizeof(signed_descriptor_t)); /* Debug bad mem usage */
891  tor_free(sd);
892 }
893 
894 /** Reset the given signed descriptor <b>sd</b> by freeing the allocated
895  * memory inside the object and by zeroing its content. */
896 static void
898 {
899  tor_assert(sd);
901  tor_cert_free(sd->signing_key_cert);
902  memset(sd, 0, sizeof(*sd));
903 }
904 
905 /** Copy src into dest, and steal all references inside src so that when
906  * we free src, we don't mess up dest. */
907 static void
909  signed_descriptor_t *src)
910 {
911  tor_assert(dest != src);
912  /* Cleanup destination object before overwriting it.*/
914  memcpy(dest, src, sizeof(signed_descriptor_t));
915  src->signed_descriptor_body = NULL;
916  src->signing_key_cert = NULL;
917  dest->routerlist_index = -1;
918 }
919 
920 /** Extract a signed_descriptor_t from a general routerinfo, and free the
921  * routerinfo.
922  */
923 static signed_descriptor_t *
925 {
928  sd = tor_malloc_zero(sizeof(signed_descriptor_t));
929  signed_descriptor_move(sd, &ri->cache_info);
930  routerinfo_free(ri);
931  return sd;
932 }
933 
934 /** Helper: free the storage held by the extrainfo_t in <b>e</b>. */
935 static void
937 {
938  extrainfo_free_(e);
939 }
940 
941 /** Free all storage held by a routerlist <b>rl</b>. */
942 void
944 {
945  if (!rl)
946  return;
947  rimap_free(rl->identity_map, NULL);
948  sdmap_free(rl->desc_digest_map, NULL);
949  sdmap_free(rl->desc_by_eid_map, NULL);
950  eimap_free(rl->extra_info_map, extrainfo_free_void);
952  routerinfo_free(r));
954  signed_descriptor_free(sd));
955  smartlist_free(rl->routers);
956  smartlist_free(rl->old_routers);
957  if (rl->desc_store.mmap) {
958  int res = tor_munmap_file(rl->desc_store.mmap);
959  if (res != 0) {
960  log_warn(LD_FS, "Failed to munmap routerlist->desc_store.mmap");
961  }
962  }
963  if (rl->extrainfo_store.mmap) {
964  int res = tor_munmap_file(rl->extrainfo_store.mmap);
965  if (res != 0) {
966  log_warn(LD_FS, "Failed to munmap routerlist->extrainfo_store.mmap");
967  }
968  }
969  tor_free(rl);
970 }
971 
972 /** Log information about how much memory is being used for routerlist,
973  * at log level <b>severity</b>. */
974 void
976 {
977  uint64_t livedescs = 0;
978  uint64_t olddescs = 0;
979  if (!routerlist)
980  return;
982  livedescs += r->cache_info.signed_descriptor_len);
984  olddescs += sd->signed_descriptor_len);
985 
986  tor_log(severity, LD_DIR,
987  "In %d live descriptors: %"PRIu64" bytes. "
988  "In %d old descriptors: %"PRIu64" bytes.",
989  smartlist_len(routerlist->routers), (livedescs),
990  smartlist_len(routerlist->old_routers), (olddescs));
991 }
992 
993 /** Debugging helper: If <b>idx</b> is nonnegative, assert that <b>ri</b> is
994  * in <b>sl</b> at position <b>idx</b>. Otherwise, search <b>sl</b> for
995  * <b>ri</b>. Return the index of <b>ri</b> in <b>sl</b>, or -1 if <b>ri</b>
996  * is not in <b>sl</b>. */
997 static inline int
998 routerlist_find_elt_(smartlist_t *sl, void *ri, int idx)
999 {
1000  if (idx < 0) {
1001  idx = -1;
1003  if (r == ri) {
1004  idx = r_sl_idx;
1005  break;
1006  });
1007  } else {
1008  tor_assert(idx < smartlist_len(sl));
1009  tor_assert(smartlist_get(sl, idx) == ri);
1010  };
1011  return idx;
1012 }
1013 
1014 /** Insert an item <b>ri</b> into the routerlist <b>rl</b>, updating indices
1015  * as needed. There must be no previous member of <b>rl</b> with the same
1016  * identity digest as <b>ri</b>: If there is, call routerlist_replace
1017  * instead.
1018  */
1019 static void
1021 {
1022  routerinfo_t *ri_old;
1023  signed_descriptor_t *sd_old;
1024  {
1025  const routerinfo_t *ri_generated = router_get_my_routerinfo();
1026  tor_assert(ri_generated != ri);
1027  }
1028  tor_assert(ri->cache_info.routerlist_index == -1);
1029 
1030  ri_old = rimap_set(rl->identity_map, ri->cache_info.identity_digest, ri);
1031  tor_assert(!ri_old);
1032 
1033  sd_old = sdmap_set(rl->desc_digest_map,
1034  ri->cache_info.signed_descriptor_digest,
1035  &(ri->cache_info));
1036  if (sd_old) {
1037  int idx = sd_old->routerlist_index;
1038  sd_old->routerlist_index = -1;
1039  smartlist_del(rl->old_routers, idx);
1040  if (idx < smartlist_len(rl->old_routers)) {
1041  signed_descriptor_t *d = smartlist_get(rl->old_routers, idx);
1042  d->routerlist_index = idx;
1043  }
1045  sdmap_remove(rl->desc_by_eid_map, sd_old->extra_info_digest);
1046  signed_descriptor_free(sd_old);
1047  }
1048 
1049  if (!tor_digest_is_zero(ri->cache_info.extra_info_digest))
1050  sdmap_set(rl->desc_by_eid_map, ri->cache_info.extra_info_digest,
1051  &ri->cache_info);
1052  smartlist_add(rl->routers, ri);
1053  ri->cache_info.routerlist_index = smartlist_len(rl->routers) - 1;
1054  nodelist_set_routerinfo(ri, NULL);
1056 #ifdef DEBUG_ROUTERLIST
1058 #endif
1059 }
1060 
1061 /** Adds the extrainfo_t <b>ei</b> to the routerlist <b>rl</b>, if there is a
1062  * corresponding router in rl->routers or rl->old_routers. Return the status
1063  * of inserting <b>ei</b>. Free <b>ei</b> if it isn't inserted. */
1065 extrainfo_insert,(routerlist_t *rl, extrainfo_t *ei, int warn_if_incompatible))
1066 {
1068  const char *compatibility_error_msg;
1069  routerinfo_t *ri = rimap_get(rl->identity_map,
1070  ei->cache_info.identity_digest);
1071  signed_descriptor_t *sd =
1072  sdmap_get(rl->desc_by_eid_map, ei->cache_info.signed_descriptor_digest);
1073  extrainfo_t *ei_tmp;
1074  const int severity = warn_if_incompatible ? LOG_WARN : LOG_INFO;
1075 
1076  {
1077  extrainfo_t *ei_generated = router_get_my_extrainfo();
1078  tor_assert(ei_generated != ei);
1079  }
1080 
1081  if (!ri) {
1082  /* This router is unknown; we can't even verify the signature. Give up.*/
1083  r = ROUTER_NOT_IN_CONSENSUS;
1084  goto done;
1085  }
1086  if (! sd) {
1087  /* The extrainfo router doesn't have a known routerdesc to attach it to.
1088  * This just won't work. */;
1089  static ratelim_t no_sd_ratelim = RATELIM_INIT(1800);
1090  r = ROUTER_BAD_EI;
1091  log_fn_ratelim(&no_sd_ratelim, severity, LD_BUG,
1092  "No entry found in extrainfo map.");
1093  goto done;
1094  }
1095  if (tor_memneq(ei->cache_info.signed_descriptor_digest,
1096  sd->extra_info_digest, DIGEST_LEN)) {
1097  static ratelim_t digest_mismatch_ratelim = RATELIM_INIT(1800);
1098  /* The sd we got from the map doesn't match the digest we used to look
1099  * it up. This makes no sense. */
1100  r = ROUTER_BAD_EI;
1101  log_fn_ratelim(&digest_mismatch_ratelim, severity, LD_BUG,
1102  "Mismatch in digest in extrainfo map.");
1103  goto done;
1104  }
1106  &compatibility_error_msg)) {
1107  char d1[HEX_DIGEST_LEN+1], d2[HEX_DIGEST_LEN+1];
1108  r = (ri->cache_info.extrainfo_is_bogus) ?
1109  ROUTER_BAD_EI : ROUTER_NOT_IN_CONSENSUS;
1110 
1111  base16_encode(d1, sizeof(d1), ri->cache_info.identity_digest, DIGEST_LEN);
1112  base16_encode(d2, sizeof(d2), ei->cache_info.identity_digest, DIGEST_LEN);
1113 
1114  log_fn(severity,LD_DIR,
1115  "router info incompatible with extra info (ri id: %s, ei id %s, "
1116  "reason: %s)", d1, d2, compatibility_error_msg);
1117 
1118  goto done;
1119  }
1120 
1121  /* Okay, if we make it here, we definitely have a router corresponding to
1122  * this extrainfo. */
1123 
1124  ei_tmp = eimap_set(rl->extra_info_map,
1125  ei->cache_info.signed_descriptor_digest,
1126  ei);
1127  r = ROUTER_ADDED_SUCCESSFULLY;
1128  if (ei_tmp) {
1130  ei_tmp->cache_info.signed_descriptor_len;
1131  extrainfo_free(ei_tmp);
1132  }
1133 
1134  done:
1135  if (r != ROUTER_ADDED_SUCCESSFULLY)
1136  extrainfo_free(ei);
1137 
1138 #ifdef DEBUG_ROUTERLIST
1140 #endif
1141  return r;
1142 }
1143 
1144 #define should_cache_old_descriptors() \
1145  directory_caches_dir_info(get_options())
1146 
1147 /** If we're a directory cache and routerlist <b>rl</b> doesn't have
1148  * a copy of router <b>ri</b> yet, add it to the list of old (not
1149  * recommended but still served) descriptors. Else free it. */
1150 static void
1152 {
1153  {
1154  const routerinfo_t *ri_generated = router_get_my_routerinfo();
1155  tor_assert(ri_generated != ri);
1156  }
1157  tor_assert(ri->cache_info.routerlist_index == -1);
1158 
1159  if (should_cache_old_descriptors() &&
1161  !sdmap_get(rl->desc_digest_map,
1162  ri->cache_info.signed_descriptor_digest)) {
1164  sdmap_set(rl->desc_digest_map, sd->signed_descriptor_digest, sd);
1165  smartlist_add(rl->old_routers, sd);
1166  sd->routerlist_index = smartlist_len(rl->old_routers)-1;
1168  sdmap_set(rl->desc_by_eid_map, sd->extra_info_digest, sd);
1169  } else {
1170  routerinfo_free(ri);
1171  }
1172 #ifdef DEBUG_ROUTERLIST
1174 #endif
1175 }
1176 
1177 /** Remove an item <b>ri</b> from the routerlist <b>rl</b>, updating indices
1178  * as needed. If <b>idx</b> is nonnegative and smartlist_get(rl-&gt;routers,
1179  * idx) == ri, we don't need to do a linear search over the list to decide
1180  * which to remove. We fill the gap in rl-&gt;routers with a later element in
1181  * the list, if any exists. <b>ri</b> is freed.
1182  *
1183  * If <b>make_old</b> is true, instead of deleting the router, we try adding
1184  * it to rl-&gt;old_routers. */
1185 void
1186 routerlist_remove(routerlist_t *rl, routerinfo_t *ri, int make_old, time_t now)
1187 {
1188  routerinfo_t *ri_tmp;
1189  extrainfo_t *ei_tmp;
1190  int idx = ri->cache_info.routerlist_index;
1191  tor_assert(0 <= idx && idx < smartlist_len(rl->routers));
1192  tor_assert(smartlist_get(rl->routers, idx) == ri);
1193 
1195 
1196  /* make sure the rephist module knows that it's not running */
1198 
1199  ri->cache_info.routerlist_index = -1;
1200  smartlist_del(rl->routers, idx);
1201  if (idx < smartlist_len(rl->routers)) {
1202  routerinfo_t *r = smartlist_get(rl->routers, idx);
1203  r->cache_info.routerlist_index = idx;
1204  }
1205 
1206  ri_tmp = rimap_remove(rl->identity_map, ri->cache_info.identity_digest);
1208  tor_assert(ri_tmp == ri);
1209 
1210  if (make_old && should_cache_old_descriptors() &&
1212  signed_descriptor_t *sd;
1214  smartlist_add(rl->old_routers, sd);
1215  sd->routerlist_index = smartlist_len(rl->old_routers)-1;
1216  sdmap_set(rl->desc_digest_map, sd->signed_descriptor_digest, sd);
1218  sdmap_set(rl->desc_by_eid_map, sd->extra_info_digest, sd);
1219  } else {
1220  signed_descriptor_t *sd_tmp;
1221  sd_tmp = sdmap_remove(rl->desc_digest_map,
1222  ri->cache_info.signed_descriptor_digest);
1223  tor_assert(sd_tmp == &(ri->cache_info));
1224  rl->desc_store.bytes_dropped += ri->cache_info.signed_descriptor_len;
1225  ei_tmp = eimap_remove(rl->extra_info_map,
1226  ri->cache_info.extra_info_digest);
1227  if (ei_tmp) {
1229  ei_tmp->cache_info.signed_descriptor_len;
1230  extrainfo_free(ei_tmp);
1231  }
1232  if (!tor_digest_is_zero(ri->cache_info.extra_info_digest))
1233  sdmap_remove(rl->desc_by_eid_map, ri->cache_info.extra_info_digest);
1234  routerinfo_free(ri);
1235  }
1236 #ifdef DEBUG_ROUTERLIST
1238 #endif
1239 }
1240 
1241 /** Remove a signed_descriptor_t <b>sd</b> from <b>rl</b>->old_routers, and
1242  * adjust <b>rl</b> as appropriate. <b>idx</b> is -1, or the index of
1243  * <b>sd</b>. */
1244 static void
1246 {
1247  signed_descriptor_t *sd_tmp;
1248  extrainfo_t *ei_tmp;
1249  desc_store_t *store;
1250  if (idx == -1) {
1251  idx = sd->routerlist_index;
1252  }
1253  tor_assert(0 <= idx && idx < smartlist_len(rl->old_routers));
1254  /* XXXX edmanm's bridge relay triggered the following assert while
1255  * running 0.2.0.12-alpha. If anybody triggers this again, see if we
1256  * can get a backtrace. */
1257  tor_assert(smartlist_get(rl->old_routers, idx) == sd);
1258  tor_assert(idx == sd->routerlist_index);
1259 
1260  sd->routerlist_index = -1;
1261  smartlist_del(rl->old_routers, idx);
1262  if (idx < smartlist_len(rl->old_routers)) {
1263  signed_descriptor_t *d = smartlist_get(rl->old_routers, idx);
1264  d->routerlist_index = idx;
1265  }
1266  sd_tmp = sdmap_remove(rl->desc_digest_map,
1268  tor_assert(sd_tmp == sd);
1269  store = desc_get_store(rl, sd);
1270  if (store)
1271  store->bytes_dropped += sd->signed_descriptor_len;
1272 
1273  ei_tmp = eimap_remove(rl->extra_info_map,
1274  sd->extra_info_digest);
1275  if (ei_tmp) {
1277  ei_tmp->cache_info.signed_descriptor_len;
1278  extrainfo_free(ei_tmp);
1279  }
1281  sdmap_remove(rl->desc_by_eid_map, sd->extra_info_digest);
1282 
1283  signed_descriptor_free(sd);
1284 #ifdef DEBUG_ROUTERLIST
1286 #endif
1287 }
1288 
1289 /** Remove <b>ri_old</b> from the routerlist <b>rl</b>, and replace it with
1290  * <b>ri_new</b>, updating all index info. If <b>idx</b> is nonnegative and
1291  * smartlist_get(rl-&gt;routers, idx) == ri, we don't need to do a linear
1292  * search over the list to decide which to remove. We put ri_new in the same
1293  * index as ri_old, if possible. ri is freed as appropriate.
1294  *
1295  * If should_cache_descriptors() is true, instead of deleting the router,
1296  * we add it to rl-&gt;old_routers. */
1297 static void
1299  routerinfo_t *ri_new)
1300 {
1301  int idx;
1302  int same_descriptors;
1303 
1304  routerinfo_t *ri_tmp;
1305  extrainfo_t *ei_tmp;
1306  {
1307  const routerinfo_t *ri_generated = router_get_my_routerinfo();
1308  tor_assert(ri_generated != ri_new);
1309  }
1310  tor_assert(ri_old != ri_new);
1311  tor_assert(ri_new->cache_info.routerlist_index == -1);
1312 
1313  idx = ri_old->cache_info.routerlist_index;
1314  tor_assert(0 <= idx && idx < smartlist_len(rl->routers));
1315  tor_assert(smartlist_get(rl->routers, idx) == ri_old);
1316 
1317  {
1318  routerinfo_t *ri_old_tmp=NULL;
1319  nodelist_set_routerinfo(ri_new, &ri_old_tmp);
1320  tor_assert(ri_old == ri_old_tmp);
1321  }
1322 
1324  if (idx >= 0) {
1325  smartlist_set(rl->routers, idx, ri_new);
1326  ri_old->cache_info.routerlist_index = -1;
1327  ri_new->cache_info.routerlist_index = idx;
1328  /* Check that ri_old is not in rl->routers anymore: */
1329  tor_assert( routerlist_find_elt_(rl->routers, ri_old, -1) == -1 );
1330  } else {
1331  log_warn(LD_BUG, "Appending entry from routerlist_replace.");
1332  routerlist_insert(rl, ri_new);
1333  return;
1334  }
1335  if (tor_memneq(ri_old->cache_info.identity_digest,
1336  ri_new->cache_info.identity_digest, DIGEST_LEN)) {
1337  /* digests don't match; digestmap_set won't replace */
1338  rimap_remove(rl->identity_map, ri_old->cache_info.identity_digest);
1339  }
1340  ri_tmp = rimap_set(rl->identity_map,
1341  ri_new->cache_info.identity_digest, ri_new);
1342  tor_assert(!ri_tmp || ri_tmp == ri_old);
1343  sdmap_set(rl->desc_digest_map,
1344  ri_new->cache_info.signed_descriptor_digest,
1345  &(ri_new->cache_info));
1346 
1347  if (!tor_digest_is_zero(ri_new->cache_info.extra_info_digest)) {
1348  sdmap_set(rl->desc_by_eid_map, ri_new->cache_info.extra_info_digest,
1349  &ri_new->cache_info);
1350  }
1351 
1352  same_descriptors = tor_memeq(ri_old->cache_info.signed_descriptor_digest,
1353  ri_new->cache_info.signed_descriptor_digest,
1354  DIGEST_LEN);
1355 
1356  if (should_cache_old_descriptors() &&
1357  ri_old->purpose == ROUTER_PURPOSE_GENERAL &&
1358  !same_descriptors) {
1359  /* ri_old is going to become a signed_descriptor_t and go into
1360  * old_routers */
1362  smartlist_add(rl->old_routers, sd);
1363  sd->routerlist_index = smartlist_len(rl->old_routers)-1;
1364  sdmap_set(rl->desc_digest_map, sd->signed_descriptor_digest, sd);
1366  sdmap_set(rl->desc_by_eid_map, sd->extra_info_digest, sd);
1367  } else {
1368  /* We're dropping ri_old. */
1369  if (!same_descriptors) {
1370  /* digests don't match; The sdmap_set above didn't replace */
1371  sdmap_remove(rl->desc_digest_map,
1372  ri_old->cache_info.signed_descriptor_digest);
1373 
1374  if (tor_memneq(ri_old->cache_info.extra_info_digest,
1375  ri_new->cache_info.extra_info_digest, DIGEST_LEN)) {
1376  ei_tmp = eimap_remove(rl->extra_info_map,
1377  ri_old->cache_info.extra_info_digest);
1378  if (ei_tmp) {
1380  ei_tmp->cache_info.signed_descriptor_len;
1381  extrainfo_free(ei_tmp);
1382  }
1383  }
1384 
1385  if (!tor_digest_is_zero(ri_old->cache_info.extra_info_digest)) {
1386  sdmap_remove(rl->desc_by_eid_map,
1387  ri_old->cache_info.extra_info_digest);
1388  }
1389  }
1390  rl->desc_store.bytes_dropped += ri_old->cache_info.signed_descriptor_len;
1391  routerinfo_free(ri_old);
1392  }
1393 #ifdef DEBUG_ROUTERLIST
1395 #endif
1396 }
1397 
1398 /** Extract the descriptor <b>sd</b> from old_routerlist, and re-parse
1399  * it as a fresh routerinfo_t. */
1400 static routerinfo_t *
1402 {
1403  routerinfo_t *ri;
1404  const char *body;
1405 
1407 
1410  0, 1, NULL, NULL);
1411  if (!ri)
1412  return NULL;
1413  signed_descriptor_move(&ri->cache_info, sd);
1414 
1415  routerlist_remove_old(rl, sd, -1);
1416 
1417  return ri;
1418 }
1419 
1420 /** Free all memory held by the routerlist module.
1421  * Note: Calling routerlist_free_all() should always be paired with
1422  * a call to nodelist_free_all(). These should only be called during
1423  * cleanup.
1424  */
1425 void
1427 {
1428  routerlist_t *rl = routerlist;
1429  routerlist = NULL; // Prevent internals of routerlist_free() from using
1430  // routerlist.
1431  routerlist_free(rl);
1432  dirlist_free_all();
1433  if (warned_nicknames) {
1434  SMARTLIST_FOREACH(warned_nicknames, char *, cp, tor_free(cp));
1435  smartlist_free(warned_nicknames);
1436  warned_nicknames = NULL;
1437  }
1438  authcert_free_all();
1439 }
1440 
1441 /** Forget that we have issued any router-related warnings, so that we'll
1442  * warn again if we see the same errors. */
1443 void
1445 {
1446  if (!warned_nicknames)
1448  SMARTLIST_FOREACH(warned_nicknames, char *, cp, tor_free(cp));
1449  smartlist_clear(warned_nicknames); /* now the list is empty. */
1450 
1452 }
1453 
1454 /** Return 1 if the signed descriptor of this router is older than
1455  * <b>seconds</b> seconds. Otherwise return 0. */
1456 MOCK_IMPL(int,
1457 router_descriptor_is_older_than,(const routerinfo_t *router, int seconds))
1458 {
1459  return router->cache_info.published_on < approx_time() - seconds;
1460 }
1461 
1462 /** Add <b>router</b> to the routerlist, if we don't already have it. Replace
1463  * older entries (if any) with the same key.
1464  *
1465  * Note: Callers should not hold their pointers to <b>router</b> if this
1466  * function fails; <b>router</b> will either be inserted into the routerlist or
1467  * freed. Similarly, even if this call succeeds, they should not hold their
1468  * pointers to <b>router</b> after subsequent calls with other routerinfo's --
1469  * they might cause the original routerinfo to get freed.
1470  *
1471  * Returns the status for the operation. Might set *<b>msg</b> if it wants
1472  * the poster of the router to know something.
1473  *
1474  * If <b>from_cache</b>, this descriptor came from our disk cache. If
1475  * <b>from_fetch</b>, we received it in response to a request we made.
1476  * (If both are false, that means it was uploaded to us as an auth dir
1477  * server or via the controller.)
1478  *
1479  * This function should be called *after*
1480  * routers_update_status_from_consensus_networkstatus; subsequently, you
1481  * should call router_rebuild_store and routerlist_descriptors_added.
1482  */
1484 router_add_to_routerlist(routerinfo_t *router, const char **msg,
1485  int from_cache, int from_fetch)
1486 {
1487  const char *id_digest;
1488  const or_options_t *options = get_options();
1489  int authdir = authdir_mode_handles_descs(options, router->purpose);
1490  int authdir_believes_valid = 0;
1491  routerinfo_t *old_router;
1492  networkstatus_t *consensus =
1494  int in_consensus = 0;
1495 
1496  tor_assert(msg);
1497 
1498  if (!routerlist)
1500 
1501  id_digest = router->cache_info.identity_digest;
1502 
1503  old_router = router_get_mutable_by_digest(id_digest);
1504 
1505  /* Make sure that it isn't expired. */
1506  if (router->cert_expiration_time < approx_time()) {
1507  routerinfo_free(router);
1508  *msg = "Some certs on this router are expired.";
1509  return ROUTER_CERTS_EXPIRED;
1510  }
1511 
1512  /* Make sure that we haven't already got this exact descriptor. */
1513  if (sdmap_get(routerlist->desc_digest_map,
1514  router->cache_info.signed_descriptor_digest)) {
1515  /* If we have this descriptor already and the new descriptor is a bridge
1516  * descriptor, replace it. If we had a bridge descriptor before and the
1517  * new one is not a bridge descriptor, don't replace it. */
1518 
1519  /* Only members of routerlist->identity_map can be bridges; we don't
1520  * put bridges in old_routers. */
1521  const int was_bridge = old_router &&
1522  old_router->purpose == ROUTER_PURPOSE_BRIDGE;
1523 
1524  if (routerinfo_is_a_configured_bridge(router) &&
1525  router->purpose == ROUTER_PURPOSE_BRIDGE &&
1526  !was_bridge) {
1527  log_info(LD_DIR, "Replacing non-bridge descriptor with bridge "
1528  "descriptor for router %s",
1529  router_describe(router));
1530  } else {
1531  log_info(LD_DIR,
1532  "Dropping descriptor that we already have for router %s",
1533  router_describe(router));
1534  *msg = "Router descriptor was not new.";
1535  routerinfo_free(router);
1536  return ROUTER_IS_ALREADY_KNOWN;
1537  }
1538  }
1539 
1540  if (authdir) {
1541  if (authdir_wants_to_reject_router(router, msg,
1542  !from_cache && !from_fetch,
1543  &authdir_believes_valid)) {
1544  tor_assert(*msg);
1545  routerinfo_free(router);
1546  return ROUTER_AUTHDIR_REJECTS;
1547  }
1548  } else if (from_fetch) {
1549  /* Only check the descriptor digest against the network statuses when
1550  * we are receiving in response to a fetch. */
1551 
1552  if (!signed_desc_digest_is_recognized(&router->cache_info) &&
1554  /* We asked for it, so some networkstatus must have listed it when we
1555  * did. Save it if we're a cache in case somebody else asks for it. */
1556  log_info(LD_DIR,
1557  "Received a no-longer-recognized descriptor for router %s",
1558  router_describe(router));
1559  *msg = "Router descriptor is not referenced by any network-status.";
1560 
1561  /* Only journal this desc if we want to keep old descriptors */
1562  if (!from_cache && should_cache_old_descriptors())
1563  signed_desc_append_to_journal(&router->cache_info,
1566  return ROUTER_NOT_IN_CONSENSUS_OR_NETWORKSTATUS;
1567  }
1568  }
1569 
1570  /* We no longer need a router with this descriptor digest. */
1571  if (consensus) {
1573  consensus, id_digest);
1574  if (rs && tor_memeq(rs->descriptor_digest,
1575  router->cache_info.signed_descriptor_digest,
1576  DIGEST_LEN)) {
1577  in_consensus = 1;
1578  }
1579  }
1580 
1581  if (router->purpose == ROUTER_PURPOSE_GENERAL &&
1582  consensus && !in_consensus && !authdir) {
1583  /* If it's a general router not listed in the consensus, then don't
1584  * consider replacing the latest router with it. */
1585  if (!from_cache && should_cache_old_descriptors())
1586  signed_desc_append_to_journal(&router->cache_info,
1589  *msg = "Skipping router descriptor: not in consensus.";
1590  return ROUTER_NOT_IN_CONSENSUS;
1591  }
1592 
1593  /* If we're reading a bridge descriptor from our cache, and we don't
1594  * recognize it as one of our currently configured bridges, drop the
1595  * descriptor. Otherwise we could end up using it as one of our entry
1596  * guards even if it isn't in our Bridge config lines. */
1597  if (router->purpose == ROUTER_PURPOSE_BRIDGE && from_cache &&
1598  !authdir_mode_bridge(options) &&
1600  log_info(LD_DIR, "Dropping bridge descriptor for %s because we have "
1601  "no bridge configured at that address.",
1602  safe_str_client(router_describe(router)));
1603  *msg = "Router descriptor was not a configured bridge.";
1604  routerinfo_free(router);
1605  return ROUTER_WAS_NOT_WANTED;
1606  }
1607 
1608  /* If we have a router with the same identity key, choose the newer one. */
1609  if (old_router) {
1610  if (!in_consensus && (router->cache_info.published_on <=
1611  old_router->cache_info.published_on)) {
1612  /* Same key, but old. This one is not listed in the consensus. */
1613  log_debug(LD_DIR, "Not-new descriptor for router %s",
1614  router_describe(router));
1615  /* Only journal this desc if we'll be serving it. */
1616  if (!from_cache && should_cache_old_descriptors())
1617  signed_desc_append_to_journal(&router->cache_info,
1620  *msg = "Router descriptor was not new.";
1621  return ROUTER_IS_ALREADY_KNOWN;
1622  } else {
1623  /* Same key, and either new, or listed in the consensus. */
1624  log_debug(LD_DIR, "Replacing entry for router %s",
1625  router_describe(router));
1626  routerlist_replace(routerlist, old_router, router);
1627  if (!from_cache) {
1628  signed_desc_append_to_journal(&router->cache_info,
1630  }
1631  *msg = authdir_believes_valid ? "Valid server updated" :
1632  ("Invalid server updated. (This dirserver is marking your "
1633  "server as unapproved.)");
1634  return ROUTER_ADDED_SUCCESSFULLY;
1635  }
1636  }
1637 
1638  if (!in_consensus && from_cache &&
1640  *msg = "Router descriptor was really old.";
1641  routerinfo_free(router);
1642  return ROUTER_WAS_TOO_OLD;
1643  }
1644 
1645  /* We haven't seen a router with this identity before. Add it to the end of
1646  * the list. */
1647  routerlist_insert(routerlist, router);
1648  if (!from_cache) {
1649  signed_desc_append_to_journal(&router->cache_info,
1651  }
1652  return ROUTER_ADDED_SUCCESSFULLY;
1653 }
1654 
1655 /** Insert <b>ei</b> into the routerlist, or free it. Other arguments are
1656  * as for router_add_to_routerlist(). Return ROUTER_ADDED_SUCCESSFULLY iff
1657  * we actually inserted it, ROUTER_BAD_EI otherwise.
1658  */
1661  int from_cache, int from_fetch)
1662 {
1663  was_router_added_t inserted;
1664  (void)from_fetch;
1665  if (msg) *msg = NULL;
1666  /*XXXX Do something with msg */
1667 
1668  inserted = extrainfo_insert(router_get_routerlist(), ei, !from_cache);
1669 
1670  if (WRA_WAS_ADDED(inserted) && !from_cache)
1671  signed_desc_append_to_journal(&ei->cache_info,
1673 
1674  return inserted;
1675 }
1676 
1677 /** Sorting helper: return &lt;0, 0, or &gt;0 depending on whether the
1678  * signed_descriptor_t* in *<b>a</b> has an identity digest preceding, equal
1679  * to, or later than that of *<b>b</b>. */
1680 static int
1681 compare_old_routers_by_identity_(const void **_a, const void **_b)
1682 {
1683  int i;
1684  const signed_descriptor_t *r1 = *_a, *r2 = *_b;
1685  if ((i = fast_memcmp(r1->identity_digest, r2->identity_digest, DIGEST_LEN)))
1686  return i;
1687  return (int)(r1->published_on - r2->published_on);
1688 }
1689 
1690 /** Internal type used to represent how long an old descriptor was valid,
1691  * where it appeared in the list of old descriptors, and whether it's extra
1692  * old. Used only by routerlist_remove_old_cached_routers_with_id(). */
1694  int duration;
1695  int idx;
1696  int old;
1697 };
1698 
1699 /** Sorting helper: compare two duration_idx_t by their duration. */
1700 static int
1701 compare_duration_idx_(const void *_d1, const void *_d2)
1702 {
1703  const struct duration_idx_t *d1 = _d1;
1704  const struct duration_idx_t *d2 = _d2;
1705  return d1->duration - d2->duration;
1706 }
1707 
1708 /** The range <b>lo</b> through <b>hi</b> inclusive of routerlist->old_routers
1709  * must contain routerinfo_t with the same identity and with publication time
1710  * in ascending order. Remove members from this range until there are no more
1711  * than max_descriptors_per_router() remaining. Start by removing the oldest
1712  * members from before <b>cutoff</b>, then remove members which were current
1713  * for the lowest amount of time. The order of members of old_routers at
1714  * indices <b>lo</b> or higher may be changed.
1715  */
1716 static void
1718  time_t cutoff, int lo, int hi,
1719  digestset_t *retain)
1720 {
1721  int i, n = hi-lo+1;
1722  unsigned n_extra, n_rmv = 0;
1723  struct duration_idx_t *lifespans;
1724  uint8_t *rmv, *must_keep;
1726 #if 1
1727  const char *ident;
1728  tor_assert(hi < smartlist_len(lst));
1729  tor_assert(lo <= hi);
1730  ident = ((signed_descriptor_t*)smartlist_get(lst, lo))->identity_digest;
1731  for (i = lo+1; i <= hi; ++i) {
1732  signed_descriptor_t *r = smartlist_get(lst, i);
1734  }
1735 #endif /* 1 */
1736  /* Check whether we need to do anything at all. */
1737  {
1738  int mdpr = directory_caches_dir_info(get_options()) ? 2 : 1;
1739  if (n <= mdpr)
1740  return;
1741  n_extra = n - mdpr;
1742  }
1743 
1744  lifespans = tor_calloc(n, sizeof(struct duration_idx_t));
1745  rmv = tor_calloc(n, sizeof(uint8_t));
1746  must_keep = tor_calloc(n, sizeof(uint8_t));
1747  /* Set lifespans to contain the lifespan and index of each server. */
1748  /* Set rmv[i-lo]=1 if we're going to remove a server for being too old. */
1749  for (i = lo; i <= hi; ++i) {
1750  signed_descriptor_t *r = smartlist_get(lst, i);
1751  signed_descriptor_t *r_next;
1752  lifespans[i-lo].idx = i;
1753  if (r->last_listed_as_valid_until >= now ||
1754  (retain && digestset_probably_contains(retain,
1755  r->signed_descriptor_digest))) {
1756  must_keep[i-lo] = 1;
1757  }
1758  if (i < hi) {
1759  r_next = smartlist_get(lst, i+1);
1760  tor_assert(r->published_on <= r_next->published_on);
1761  lifespans[i-lo].duration = (int)(r_next->published_on - r->published_on);
1762  } else {
1763  r_next = NULL;
1764  lifespans[i-lo].duration = INT_MAX;
1765  }
1766  if (!must_keep[i-lo] && r->published_on < cutoff && n_rmv < n_extra) {
1767  ++n_rmv;
1768  lifespans[i-lo].old = 1;
1769  rmv[i-lo] = 1;
1770  }
1771  }
1772 
1773  if (n_rmv < n_extra) {
1774  /**
1775  * We aren't removing enough servers for being old. Sort lifespans by
1776  * the duration of liveness, and remove the ones we're not already going to
1777  * remove based on how long they were alive.
1778  **/
1779  qsort(lifespans, n, sizeof(struct duration_idx_t), compare_duration_idx_);
1780  for (i = 0; i < n && n_rmv < n_extra; ++i) {
1781  if (!must_keep[lifespans[i].idx-lo] && !lifespans[i].old) {
1782  rmv[lifespans[i].idx-lo] = 1;
1783  ++n_rmv;
1784  }
1785  }
1786  }
1787 
1788  i = hi;
1789  do {
1790  if (rmv[i-lo])
1791  routerlist_remove_old(routerlist, smartlist_get(lst, i), i);
1792  } while (--i >= lo);
1793  tor_free(must_keep);
1794  tor_free(rmv);
1795  tor_free(lifespans);
1796 }
1797 
1798 /** Deactivate any routers from the routerlist that are more than
1799  * ROUTER_MAX_AGE seconds old and not recommended by any networkstatuses;
1800  * remove old routers from the list of cached routers if we have too many.
1801  */
1802 void
1804 {
1805  int i, hi=-1;
1806  const char *cur_id = NULL;
1807  time_t now = time(NULL);
1808  time_t cutoff;
1809  routerinfo_t *router;
1810  signed_descriptor_t *sd;
1811  digestset_t *retain;
1813 
1815 
1816  if (!routerlist || !consensus)
1817  return;
1818 
1819  // routerlist_assert_ok(routerlist);
1820 
1821  /* We need to guess how many router descriptors we will wind up wanting to
1822  retain, so that we can be sure to allocate a large enough Bloom filter
1823  to hold the digest set. Overestimating is fine; underestimating is bad.
1824  */
1825  {
1826  /* We'll probably retain everything in the consensus. */
1827  int n_max_retain = smartlist_len(consensus->routerstatus_list);
1828  retain = digestset_new(n_max_retain);
1829  }
1830 
1831  cutoff = now - OLD_ROUTER_DESC_MAX_AGE;
1832  /* Retain anything listed in the consensus. */
1833  if (consensus) {
1835  if (rs->published_on >= cutoff)
1836  digestset_add(retain, rs->descriptor_digest));
1837  }
1838 
1839  /* If we have a consensus, we should consider pruning current routers that
1840  * are too old and that nobody recommends. (If we don't have a consensus,
1841  * then we should get one before we decide to kill routers.) */
1842 
1843  if (consensus) {
1844  cutoff = now - ROUTER_MAX_AGE;
1845  /* Remove too-old unrecommended members of routerlist->routers. */
1846  for (i = 0; i < smartlist_len(routerlist->routers); ++i) {
1847  router = smartlist_get(routerlist->routers, i);
1848  if (router->cache_info.published_on <= cutoff &&
1849  router->cache_info.last_listed_as_valid_until < now &&
1851  router->cache_info.signed_descriptor_digest)) {
1852  /* Too old: remove it. (If we're a cache, just move it into
1853  * old_routers.) */
1854  log_info(LD_DIR,
1855  "Forgetting obsolete (too old) routerinfo for router %s",
1856  router_describe(router));
1857  routerlist_remove(routerlist, router, 1, now);
1858  i--;
1859  }
1860  }
1861  }
1862 
1863  //routerlist_assert_ok(routerlist);
1864 
1865  /* Remove far-too-old members of routerlist->old_routers. */
1866  cutoff = now - OLD_ROUTER_DESC_MAX_AGE;
1867  for (i = 0; i < smartlist_len(routerlist->old_routers); ++i) {
1868  sd = smartlist_get(routerlist->old_routers, i);
1869  if (sd->published_on <= cutoff &&
1870  sd->last_listed_as_valid_until < now &&
1872  /* Too old. Remove it. */
1874  }
1875  }
1876 
1877  //routerlist_assert_ok(routerlist);
1878 
1879  log_info(LD_DIR, "We have %d live routers and %d old router descriptors.",
1880  smartlist_len(routerlist->routers),
1881  smartlist_len(routerlist->old_routers));
1882 
1883  /* Now we might have to look at routerlist->old_routers for extraneous
1884  * members. (We'd keep all the members if we could, but we need to save
1885  * space.) First, check whether we have too many router descriptors, total.
1886  * We're okay with having too many for some given router, so long as the
1887  * total number doesn't approach max_descriptors_per_router()*len(router).
1888  */
1889  if (smartlist_len(routerlist->old_routers) <
1890  smartlist_len(routerlist->routers))
1891  goto done;
1892 
1893  /* Sort by identity, then fix indices. */
1895  /* Fix indices. */
1896  for (i = 0; i < smartlist_len(routerlist->old_routers); ++i) {
1897  signed_descriptor_t *r = smartlist_get(routerlist->old_routers, i);
1898  r->routerlist_index = i;
1899  }
1900 
1901  /* Iterate through the list from back to front, so when we remove descriptors
1902  * we don't mess up groups we haven't gotten to. */
1903  for (i = smartlist_len(routerlist->old_routers)-1; i >= 0; --i) {
1904  signed_descriptor_t *r = smartlist_get(routerlist->old_routers, i);
1905  if (!cur_id) {
1906  cur_id = r->identity_digest;
1907  hi = i;
1908  }
1909  if (tor_memneq(cur_id, r->identity_digest, DIGEST_LEN)) {
1911  cutoff, i+1, hi, retain);
1912  cur_id = r->identity_digest;
1913  hi = i;
1914  }
1915  }
1916  if (hi>=0)
1917  routerlist_remove_old_cached_routers_with_id(now, cutoff, 0, hi, retain);
1918  //routerlist_assert_ok(routerlist);
1919 
1920  done:
1921  digestset_free(retain);
1922  router_rebuild_store(RRS_DONT_REMOVE_OLD, &routerlist->desc_store);
1923  router_rebuild_store(RRS_DONT_REMOVE_OLD,&routerlist->extrainfo_store);
1924 }
1925 
1926 /** We just added a new set of descriptors. Take whatever extra steps
1927  * we need. */
1928 void
1930 {
1931  // XXXX use pubsub mechanism here.
1932 
1933  tor_assert(sl);
1936  if (ri->purpose == ROUTER_PURPOSE_BRIDGE)
1937  learned_bridge_descriptor(ri, from_cache);
1938  if (ri->needs_retest_if_added) {
1939  ri->needs_retest_if_added = 0;
1941  }
1942  } SMARTLIST_FOREACH_END(ri);
1943 }
1944 
1945 /**
1946  * Code to parse a single router descriptor and insert it into the
1947  * routerlist. Return -1 if the descriptor was ill-formed; 0 if the
1948  * descriptor was well-formed but could not be added; and 1 if the
1949  * descriptor was added.
1950  *
1951  * If we don't add it and <b>msg</b> is not NULL, then assign to
1952  * *<b>msg</b> a static string describing the reason for refusing the
1953  * descriptor.
1954  *
1955  * This is used only by the controller.
1956  */
1957 int
1958 router_load_single_router(const char *s, uint8_t purpose, int cache,
1959  const char **msg)
1960 {
1961  routerinfo_t *ri;
1963  smartlist_t *lst;
1964  char annotation_buf[ROUTER_ANNOTATION_BUF_LEN];
1965  tor_assert(msg);
1966  *msg = NULL;
1967 
1968  tor_snprintf(annotation_buf, sizeof(annotation_buf),
1969  "@source controller\n"
1970  "@purpose %s\n", router_purpose_to_string(purpose));
1971 
1972  if (!(ri = router_parse_entry_from_string(s, NULL, 1, 0,
1973  annotation_buf, NULL))) {
1974  log_warn(LD_DIR, "Error parsing router descriptor; dropping.");
1975  *msg = "Couldn't parse router descriptor.";
1976  return -1;
1977  }
1978  tor_assert(ri->purpose == purpose);
1979  if (router_is_me(ri)) {
1980  log_warn(LD_DIR, "Router's identity key matches mine; dropping.");
1981  *msg = "Router's identity key matches mine.";
1982  routerinfo_free(ri);
1983  return 0;
1984  }
1985 
1986  if (!cache) /* obey the preference of the controller */
1987  ri->cache_info.do_not_cache = 1;
1988 
1989  lst = smartlist_new();
1990  smartlist_add(lst, ri);
1992 
1993  r = router_add_to_routerlist(ri, msg, 0, 0);
1994  if (!WRA_WAS_ADDED(r)) {
1995  /* we've already assigned to *msg now, and ri is already freed */
1996  tor_assert(*msg);
1997  if (r == ROUTER_AUTHDIR_REJECTS)
1998  log_warn(LD_DIR, "Couldn't add router to list: %s Dropping.", *msg);
1999  smartlist_free(lst);
2000  return 0;
2001  } else {
2003  smartlist_free(lst);
2004  log_debug(LD_DIR, "Added router to list");
2005  return 1;
2006  }
2007 }
2008 
2009 /** Given a string <b>s</b> containing some routerdescs, parse it and put the
2010  * routers into our directory. If saved_location is SAVED_NOWHERE, the routers
2011  * are in response to a query to the network: cache them by adding them to
2012  * the journal.
2013  *
2014  * Return the number of routers actually added.
2015  *
2016  * If <b>requested_fingerprints</b> is provided, it must contain a list of
2017  * uppercased fingerprints. Do not update any router whose
2018  * fingerprint is not on the list; after updating a router, remove its
2019  * fingerprint from the list.
2020  *
2021  * If <b>descriptor_digests</b> is non-zero, then the requested_fingerprints
2022  * are descriptor digests. Otherwise they are identity digests.
2023  */
2024 int
2025 router_load_routers_from_string(const char *s, const char *eos,
2026  saved_location_t saved_location,
2027  smartlist_t *requested_fingerprints,
2028  int descriptor_digests,
2029  const char *prepend_annotations)
2030 {
2031  smartlist_t *routers = smartlist_new(), *changed = smartlist_new();
2032  char fp[HEX_DIGEST_LEN+1];
2033  const char *msg;
2034  int from_cache = (saved_location != SAVED_NOWHERE);
2035  int allow_annotations = (saved_location != SAVED_NOWHERE);
2036  int any_changed = 0;
2037  smartlist_t *invalid_digests = smartlist_new();
2038 
2039  router_parse_list_from_string(&s, eos, routers, saved_location, 0,
2040  allow_annotations, prepend_annotations,
2041  invalid_digests);
2042 
2044 
2045  log_info(LD_DIR, "%d elements to add", smartlist_len(routers));
2046 
2047  SMARTLIST_FOREACH_BEGIN(routers, routerinfo_t *, ri) {
2049  char d[DIGEST_LEN];
2050  if (requested_fingerprints) {
2051  base16_encode(fp, sizeof(fp), descriptor_digests ?
2052  ri->cache_info.signed_descriptor_digest :
2053  ri->cache_info.identity_digest,
2054  DIGEST_LEN);
2055  if (smartlist_contains_string(requested_fingerprints, fp)) {
2056  smartlist_string_remove(requested_fingerprints, fp);
2057  } else {
2058  char *requested =
2059  smartlist_join_strings(requested_fingerprints," ",0,NULL);
2060  log_warn(LD_DIR,
2061  "We received a router descriptor with a fingerprint (%s) "
2062  "that we never requested. (We asked for: %s.) Dropping.",
2063  fp, requested);
2064  tor_free(requested);
2065  routerinfo_free(ri);
2066  continue;
2067  }
2068  }
2069 
2070  memcpy(d, ri->cache_info.signed_descriptor_digest, DIGEST_LEN);
2071  r = router_add_to_routerlist(ri, &msg, from_cache, !from_cache);
2072  if (WRA_WAS_ADDED(r)) {
2073  any_changed++;
2074  smartlist_add(changed, ri);
2075  routerlist_descriptors_added(changed, from_cache);
2076  smartlist_clear(changed);
2077  } else if (WRA_NEVER_DOWNLOADABLE(r)) {
2078  download_status_t *dl_status;
2080  if (dl_status) {
2081  log_info(LD_GENERAL, "Marking router %s as never downloadable",
2082  hex_str(d, DIGEST_LEN));
2084  }
2085  }
2086  } SMARTLIST_FOREACH_END(ri);
2087 
2088  SMARTLIST_FOREACH_BEGIN(invalid_digests, const uint8_t *, bad_digest) {
2089  /* This digest is never going to be parseable. */
2090  base16_encode(fp, sizeof(fp), (char*)bad_digest, DIGEST_LEN);
2091  if (requested_fingerprints && descriptor_digests) {
2092  if (! smartlist_contains_string(requested_fingerprints, fp)) {
2093  /* But we didn't ask for it, so we should assume shennanegans. */
2094  continue;
2095  }
2096  smartlist_string_remove(requested_fingerprints, fp);
2097  }
2098  download_status_t *dls;
2099  dls = router_get_dl_status_by_descriptor_digest((char*)bad_digest);
2100  if (dls) {
2101  log_info(LD_GENERAL, "Marking router with descriptor %s as unparseable, "
2102  "and therefore undownloadable", fp);
2104  }
2105  } SMARTLIST_FOREACH_END(bad_digest);
2106  SMARTLIST_FOREACH(invalid_digests, uint8_t *, d, tor_free(d));
2107  smartlist_free(invalid_digests);
2108 
2110 
2111  if (any_changed)
2113 
2114  smartlist_free(routers);
2115  smartlist_free(changed);
2116 
2117  return any_changed;
2118 }
2119 
2120 /** Parse one or more extrainfos from <b>s</b> (ending immediately before
2121  * <b>eos</b> if <b>eos</b> is present). Other arguments are as for
2122  * router_load_routers_from_string(). */
2123 void
2124 router_load_extrainfo_from_string(const char *s, const char *eos,
2125  saved_location_t saved_location,
2126  smartlist_t *requested_fingerprints,
2127  int descriptor_digests)
2128 {
2129  smartlist_t *extrainfo_list = smartlist_new();
2130  const char *msg;
2131  int from_cache = (saved_location != SAVED_NOWHERE);
2132  smartlist_t *invalid_digests = smartlist_new();
2133 
2134  router_parse_list_from_string(&s, eos, extrainfo_list, saved_location, 1, 0,
2135  NULL, invalid_digests);
2136 
2137  log_info(LD_DIR, "%d elements to add", smartlist_len(extrainfo_list));
2138 
2139  SMARTLIST_FOREACH_BEGIN(extrainfo_list, extrainfo_t *, ei) {
2140  uint8_t d[DIGEST_LEN];
2141  memcpy(d, ei->cache_info.signed_descriptor_digest, DIGEST_LEN);
2142  was_router_added_t added =
2143  router_add_extrainfo_to_routerlist(ei, &msg, from_cache, !from_cache);
2144  if (WRA_WAS_ADDED(added) && requested_fingerprints) {
2145  char fp[HEX_DIGEST_LEN+1];
2146  base16_encode(fp, sizeof(fp), descriptor_digests ?
2147  ei->cache_info.signed_descriptor_digest :
2148  ei->cache_info.identity_digest,
2149  DIGEST_LEN);
2150  smartlist_string_remove(requested_fingerprints, fp);
2151  /* We silently let relays stuff us with extrainfos we didn't ask for,
2152  * so long as we would have wanted them anyway. Since we always fetch
2153  * all the extrainfos we want, and we never actually act on them
2154  * inside Tor, this should be harmless. */
2155  } else if (WRA_NEVER_DOWNLOADABLE(added)) {
2157  if (sd) {
2158  log_info(LD_GENERAL, "Marking extrainfo with descriptor %s as "
2159  "unparseable, and therefore undownloadable",
2160  hex_str((char*)d,DIGEST_LEN));
2162  }
2163  }
2164  } SMARTLIST_FOREACH_END(ei);
2165 
2166  SMARTLIST_FOREACH_BEGIN(invalid_digests, const uint8_t *, bad_digest) {
2167  /* This digest is never going to be parseable. */
2168  char fp[HEX_DIGEST_LEN+1];
2169  base16_encode(fp, sizeof(fp), (char*)bad_digest, DIGEST_LEN);
2170  if (requested_fingerprints) {
2171  if (! smartlist_contains_string(requested_fingerprints, fp)) {
2172  /* But we didn't ask for it, so we should assume shennanegans. */
2173  continue;
2174  }
2175  smartlist_string_remove(requested_fingerprints, fp);
2176  }
2177  signed_descriptor_t *sd =
2178  router_get_by_extrainfo_digest((char*)bad_digest);
2179  if (sd) {
2180  log_info(LD_GENERAL, "Marking extrainfo with descriptor %s as "
2181  "unparseable, and therefore undownloadable", fp);
2183  }
2184  } SMARTLIST_FOREACH_END(bad_digest);
2185  SMARTLIST_FOREACH(invalid_digests, uint8_t *, d, tor_free(d));
2186  smartlist_free(invalid_digests);
2187 
2189  router_rebuild_store(0, &router_get_routerlist()->extrainfo_store);
2190 
2191  smartlist_free(extrainfo_list);
2192 }
2193 
2194 /** Return true iff the latest ns-flavored consensus includes a descriptor
2195  * whose digest is that of <b>desc</b>. */
2196 static int
2198 {
2199  const routerstatus_t *rs;
2201  FLAV_NS);
2202 
2203  if (consensus) {
2204  rs = networkstatus_vote_find_entry(consensus, desc->identity_digest);
2205  if (rs && tor_memeq(rs->descriptor_digest,
2207  return 1;
2208  }
2209  return 0;
2210 }
2211 
2212 /** Update downloads for router descriptors and/or microdescriptors as
2213  * appropriate. */
2214 void
2216 {
2218  return;
2222 }
2223 
2224 /** Clear all our timeouts for fetching v3 directory stuff, and then
2225  * give it all a try again. */
2226 void
2228 {
2229  (void)now;
2230 
2231  log_debug(LD_GENERAL,
2232  "In routerlist_retry_directory_downloads()");
2233 
2237 }
2238 
2239 /** Return true iff <b>router</b> does not permit exit streams.
2240  */
2241 int
2243 {
2244  return router->policy_is_reject_star;
2245 }
2246 
2247 /** For every current directory connection whose purpose is <b>purpose</b>,
2248  * and where the resource being downloaded begins with <b>prefix</b>, split
2249  * rest of the resource into base16 fingerprints (or base64 fingerprints if
2250  * purpose==DIR_PURPOSE_FETCH_MICRODESC), decode them, and set the
2251  * corresponding elements of <b>result</b> to a nonzero value.
2252  */
2253 void
2254 list_pending_downloads(digestmap_t *result, digest256map_t *result256,
2255  int purpose, const char *prefix)
2256 {
2257  const size_t p_len = strlen(prefix);
2258  smartlist_t *tmp = smartlist_new();
2259  smartlist_t *conns = get_connection_array();
2260  int flags = DSR_HEX;
2261  if (purpose == DIR_PURPOSE_FETCH_MICRODESC)
2262  flags = DSR_DIGEST256|DSR_BASE64;
2263 
2264  tor_assert(result || result256);
2265 
2266  SMARTLIST_FOREACH_BEGIN(conns, connection_t *, conn) {
2267  if (conn->type == CONN_TYPE_DIR &&
2268  conn->purpose == purpose &&
2269  !conn->marked_for_close) {
2270  const char *resource = TO_DIR_CONN(conn)->requested_resource;
2271  if (!strcmpstart(resource, prefix))
2272  dir_split_resource_into_fingerprints(resource + p_len,
2273  tmp, NULL, flags);
2274  }
2275  } SMARTLIST_FOREACH_END(conn);
2276 
2277  if (result) {
2278  SMARTLIST_FOREACH(tmp, char *, d,
2279  {
2280  digestmap_set(result, d, (void*)1);
2281  tor_free(d);
2282  });
2283  } else if (result256) {
2284  SMARTLIST_FOREACH(tmp, uint8_t *, d,
2285  {
2286  digest256map_set(result256, d, (void*)1);
2287  tor_free(d);
2288  });
2289  }
2290  smartlist_free(tmp);
2291 }
2292 
2293 /** For every router descriptor (or extra-info document if <b>extrainfo</b> is
2294  * true) we are currently downloading by descriptor digest, set result[d] to
2295  * (void*)1. */
2296 static void
2297 list_pending_descriptor_downloads(digestmap_t *result, int extrainfo)
2298 {
2299  int purpose =
2301  list_pending_downloads(result, NULL, purpose, "d/");
2302 }
2303 
2304 /** For every microdescriptor we are currently downloading by descriptor
2305  * digest, set result[d] to (void*)1.
2306  */
2307 void
2308 list_pending_microdesc_downloads(digest256map_t *result)
2309 {
2311 }
2312 
2313 /** Launch downloads for all the descriptors whose digests or digests256
2314  * are listed as digests[i] for lo <= i < hi. (Lo and hi may be out of
2315  * range.) If <b>source</b> is given, download from <b>source</b>;
2316  * otherwise, download from an appropriate random directory server.
2317  */
2318 MOCK_IMPL(STATIC void,
2320  int purpose, smartlist_t *digests,
2321  int lo, int hi, int pds_flags))
2322 {
2323  char *resource, *cp;
2324  int digest_len, enc_digest_len;
2325  const char *sep;
2326  int b64_256;
2327  smartlist_t *tmp;
2328 
2329  if (purpose == DIR_PURPOSE_FETCH_MICRODESC) {
2330  /* Microdescriptors are downloaded by "-"-separated base64-encoded
2331  * 256-bit digests. */
2332  digest_len = DIGEST256_LEN;
2333  enc_digest_len = BASE64_DIGEST256_LEN + 1;
2334  sep = "-";
2335  b64_256 = 1;
2336  } else {
2337  digest_len = DIGEST_LEN;
2338  enc_digest_len = HEX_DIGEST_LEN + 1;
2339  sep = "+";
2340  b64_256 = 0;
2341  }
2342 
2343  if (lo < 0)
2344  lo = 0;
2345  if (hi > smartlist_len(digests))
2346  hi = smartlist_len(digests);
2347 
2348  if (hi-lo <= 0)
2349  return;
2350 
2351  tmp = smartlist_new();
2352 
2353  for (; lo < hi; ++lo) {
2354  cp = tor_malloc(enc_digest_len);
2355  if (b64_256) {
2356  digest256_to_base64(cp, smartlist_get(digests, lo));
2357  } else {
2358  base16_encode(cp, enc_digest_len, smartlist_get(digests, lo),
2359  digest_len);
2360  }
2361  smartlist_add(tmp, cp);
2362  }
2363 
2364  cp = smartlist_join_strings(tmp, sep, 0, NULL);
2365  tor_asprintf(&resource, "d/%s.z", cp);
2366 
2367  SMARTLIST_FOREACH(tmp, char *, cp1, tor_free(cp1));
2368  smartlist_free(tmp);
2369  tor_free(cp);
2370 
2371  if (source) {
2372  /* We know which authority or directory mirror we want. */
2375  directory_request_set_resource(req, resource);
2377  directory_request_free(req);
2378  } else {
2380  pds_flags, DL_WANT_ANY_DIRSERVER);
2381  }
2382  tor_free(resource);
2383 }
2384 
2385 /** Return the max number of hashes to put in a URL for a given request.
2386  */
2387 static int
2388 max_dl_per_request(const or_options_t *options, int purpose)
2389 {
2390  /* Since squid does not like URLs >= 4096 bytes we limit it to 96.
2391  * 4096 - strlen(http://[ffff:ffff:ffff:ffff:ffff:ffff:ffff:ffff]:65535
2392  * /tor/server/d/.z) == 4026
2393  * 4026/41 (40 for the hash and 1 for the + that separates them) => 98
2394  * So use 96 because it's a nice number.
2395  *
2396  * For microdescriptors, the calculation is
2397  * 4096 - strlen(http://[ffff:ffff:ffff:ffff:ffff:ffff:ffff:ffff]:65535
2398  * /tor/micro/d/.z) == 4027
2399  * 4027/44 (43 for the hash and 1 for the - that separates them) => 91
2400  * So use 90 because it's a nice number.
2401  */
2402  int max = 96;
2403  if (purpose == DIR_PURPOSE_FETCH_MICRODESC) {
2404  max = 90;
2405  }
2406  /* If we're going to tunnel our connections, we can ask for a lot more
2407  * in a request. */
2408  if (dirclient_must_use_begindir(options)) {
2409  max = 500;
2410  }
2411  return max;
2412 }
2413 
2414 /** Don't split our requests so finely that we are requesting fewer than
2415  * this number per server. (Grouping more than this at once leads to
2416  * diminishing returns.) */
2417 #define MIN_DL_PER_REQUEST 32
2418 /** To prevent a single screwy cache from confusing us by selective reply,
2419  * try to split our requests into at least this many requests. */
2420 #define MIN_REQUESTS 3
2421 /** If we want fewer than this many descriptors, wait until we
2422  * want more, or until TestingClientMaxIntervalWithoutRequest has passed. */
2423 #define MAX_DL_TO_DELAY 16
2424 
2425 /** Given a <b>purpose</b> (FETCH_MICRODESC or FETCH_SERVERDESC) and a list of
2426  * router descriptor digests or microdescriptor digest256s in
2427  * <b>downloadable</b>, decide whether to delay fetching until we have more.
2428  * If we don't want to delay, launch one or more requests to the appropriate
2429  * directory authorities.
2430  */
2431 void
2433  smartlist_t *downloadable,
2434  const routerstatus_t *source, time_t now)
2435 {
2436  const or_options_t *options = get_options();
2437  const char *descname;
2438  const int fetch_microdesc = (purpose == DIR_PURPOSE_FETCH_MICRODESC);
2439  int n_downloadable = smartlist_len(downloadable);
2440 
2441  int i, n_per_request, max_dl_per_req;
2442  const char *req_plural = "", *rtr_plural = "";
2443  int pds_flags = PDS_RETRY_IF_NO_SERVERS;
2444 
2445  tor_assert(fetch_microdesc || purpose == DIR_PURPOSE_FETCH_SERVERDESC);
2446  descname = fetch_microdesc ? "microdesc" : "routerdesc";
2447 
2448  if (!n_downloadable)
2449  return;
2450 
2451  if (!dirclient_fetches_dir_info_early(options)) {
2452  if (n_downloadable >= MAX_DL_TO_DELAY) {
2453  log_debug(LD_DIR,
2454  "There are enough downloadable %ss to launch requests.",
2455  descname);
2456  } else if (! router_have_minimum_dir_info()) {
2457  log_debug(LD_DIR,
2458  "We are only missing %d %ss, but we'll fetch anyway, since "
2459  "we don't yet have enough directory info.",
2460  n_downloadable, descname);
2461  } else {
2462 
2463  /* should delay */
2466  return;
2467 
2469  log_info(LD_DIR,
2470  "There are not many downloadable %ss, but we've "
2471  "been waiting long enough (%d seconds). Downloading.",
2472  descname,
2474  } else {
2475  log_info(LD_DIR,
2476  "There are not many downloadable %ss, but we haven't "
2477  "tried downloading descriptors recently. Downloading.",
2478  descname);
2479  }
2480  }
2481  }
2482 
2483  if (!authdir_mode(options)) {
2484  /* If we wind up going to the authorities, we want to only open one
2485  * connection to each authority at a time, so that we don't overload
2486  * them. We do this by setting PDS_NO_EXISTING_SERVERDESC_FETCH
2487  * regardless of whether we're a cache or not.
2488  *
2489  * Setting this flag can make initiate_descriptor_downloads() ignore
2490  * requests. We need to make sure that we do in fact call
2491  * update_router_descriptor_downloads() later on, once the connections
2492  * have succeeded or failed.
2493  */
2494  pds_flags |= fetch_microdesc ?
2497  }
2498 
2499  n_per_request = CEIL_DIV(n_downloadable, MIN_REQUESTS);
2500  max_dl_per_req = max_dl_per_request(options, purpose);
2501 
2502  if (n_per_request > max_dl_per_req)
2503  n_per_request = max_dl_per_req;
2504 
2505  if (n_per_request < MIN_DL_PER_REQUEST) {
2506  n_per_request = MIN(MIN_DL_PER_REQUEST, n_downloadable);
2507  }
2508 
2509  if (n_downloadable > n_per_request)
2510  req_plural = rtr_plural = "s";
2511  else if (n_downloadable > 1)
2512  rtr_plural = "s";
2513 
2514  log_info(LD_DIR,
2515  "Launching %d request%s for %d %s%s, %d at a time",
2516  CEIL_DIV(n_downloadable, n_per_request), req_plural,
2517  n_downloadable, descname, rtr_plural, n_per_request);
2518  smartlist_sort_digests(downloadable);
2519  for (i=0; i < n_downloadable; i += n_per_request) {
2520  initiate_descriptor_downloads(source, purpose,
2521  downloadable, i, i+n_per_request,
2522  pds_flags);
2523  }
2525 }
2526 
2527 /** For any descriptor that we want that's currently listed in
2528  * <b>consensus</b>, download it as appropriate. */
2529 void
2531  networkstatus_t *consensus)
2532 {
2533  const or_options_t *options = get_options();
2534  digestmap_t *map = NULL;
2535  smartlist_t *no_longer_old = smartlist_new();
2536  smartlist_t *downloadable = smartlist_new();
2537  routerstatus_t *source = NULL;
2538  int authdir = authdir_mode(options);
2539  int n_delayed=0, n_have=0, n_would_reject=0, n_wouldnt_use=0,
2540  n_inprogress=0, n_in_oldrouters=0;
2541 
2542  if (dirclient_too_idle_to_fetch_descriptors(options, now))
2543  goto done;
2544  if (!consensus)
2545  goto done;
2546 
2547  if (is_vote) {
2548  /* where's it from, so we know whom to ask for descriptors */
2549  dir_server_t *ds;
2550  networkstatus_voter_info_t *voter = smartlist_get(consensus->voters, 0);
2551  tor_assert(voter);
2553  if (ds)
2554  source = &(ds->fake_status);
2555  else
2556  log_warn(LD_DIR, "couldn't lookup source from vote?");
2557  }
2558 
2559  map = digestmap_new();
2561  SMARTLIST_FOREACH_BEGIN(consensus->routerstatus_list, void *, rsp) {
2562  routerstatus_t *rs;
2563  vote_routerstatus_t *vrs;
2564  if (is_vote) {
2565  rs = &(((vote_routerstatus_t *)rsp)->status);
2566  vrs = rsp;
2567  } else {
2568  rs = rsp;
2569  vrs = NULL;
2570  }
2571  signed_descriptor_t *sd;
2573  const routerinfo_t *ri;
2574  ++n_have;
2575  if (!(ri = router_get_by_id_digest(rs->identity_digest)) ||
2576  tor_memneq(ri->cache_info.signed_descriptor_digest,
2578  /* We have a descriptor with this digest, but either there is no
2579  * entry in routerlist with the same ID (!ri), or there is one,
2580  * but the identity digest differs (memneq).
2581  */
2582  smartlist_add(no_longer_old, sd);
2583  ++n_in_oldrouters; /* We have it in old_routers. */
2584  }
2585  continue; /* We have it already. */
2586  }
2587  if (digestmap_get(map, rs->descriptor_digest)) {
2588  ++n_inprogress;
2589  continue; /* We have an in-progress download. */
2590  }
2591  if (!download_status_is_ready(&rs->dl_status, now)) {
2592  ++n_delayed; /* Not ready for retry. */
2593  continue;
2594  }
2595  if (authdir && is_vote && dirserv_would_reject_router(rs, vrs)) {
2596  ++n_would_reject;
2597  continue; /* We would throw it out immediately. */
2598  }
2599  if (!we_want_to_fetch_flavor(options, consensus->flavor) &&
2600  !client_would_use_router(rs, now)) {
2601  ++n_wouldnt_use;
2602  continue; /* We would never use it ourself. */
2603  }
2604  if (is_vote && source) {
2605  char time_bufnew[ISO_TIME_LEN+1];
2606  char time_bufold[ISO_TIME_LEN+1];
2607  const routerinfo_t *oldrouter;
2608  oldrouter = router_get_by_id_digest(rs->identity_digest);
2609  format_iso_time(time_bufnew, rs->published_on);
2610  if (oldrouter)
2611  format_iso_time(time_bufold, oldrouter->cache_info.published_on);
2612  log_info(LD_DIR, "Learned about %s (%s vs %s) from %s's vote (%s)",
2614  time_bufnew,
2615  oldrouter ? time_bufold : "none",
2616  source->nickname, oldrouter ? "known" : "unknown");
2617  }
2618  smartlist_add(downloadable, rs->descriptor_digest);
2619  } SMARTLIST_FOREACH_END(rsp);
2620 
2621  if (!authdir_mode_v3(options)
2622  && smartlist_len(no_longer_old)) {
2624  log_info(LD_DIR, "%d router descriptors listed in consensus are "
2625  "currently in old_routers; making them current.",
2626  smartlist_len(no_longer_old));
2627  SMARTLIST_FOREACH_BEGIN(no_longer_old, signed_descriptor_t *, sd) {
2628  const char *msg;
2630  time_t tmp_cert_expiration_time;
2631  routerinfo_t *ri = routerlist_reparse_old(rl, sd);
2632  if (!ri) {
2633  log_warn(LD_BUG, "Failed to re-parse a router.");
2634  continue;
2635  }
2636  /* need to remember for below, since add_to_routerlist may free. */
2637  tmp_cert_expiration_time = ri->cert_expiration_time;
2638 
2639  r = router_add_to_routerlist(ri, &msg, 1, 0);
2640  if (WRA_WAS_OUTDATED(r)) {
2641  log_warn(LD_DIR, "Couldn't add re-parsed router: %s. This isn't "
2642  "usually a big deal, but you should make sure that your "
2643  "clock and timezone are set correctly.",
2644  msg?msg:"???");
2645  if (r == ROUTER_CERTS_EXPIRED) {
2646  char time_cons[ISO_TIME_LEN+1];
2647  char time_cert_expires[ISO_TIME_LEN+1];
2648  format_iso_time(time_cons, consensus->valid_after);
2649  format_iso_time(time_cert_expires, tmp_cert_expiration_time);
2650  log_warn(LD_DIR, " (I'm looking at a consensus from %s; This "
2651  "router's certificates began expiring at %s.)",
2652  time_cons, time_cert_expires);
2653  }
2654  }
2655  } SMARTLIST_FOREACH_END(sd);
2657  }
2658 
2659  log_info(LD_DIR,
2660  "%d router descriptors downloadable. %d delayed; %d present "
2661  "(%d of those were in old_routers); %d would_reject; "
2662  "%d wouldnt_use; %d in progress.",
2663  smartlist_len(downloadable), n_delayed, n_have, n_in_oldrouters,
2664  n_would_reject, n_wouldnt_use, n_inprogress);
2665 
2667  downloadable, source, now);
2668 
2669  digestmap_free(map, NULL);
2670  done:
2671  smartlist_free(downloadable);
2672  smartlist_free(no_longer_old);
2673 }
2674 
2675 /** How often should we launch a server/authority request to be sure of getting
2676  * a guess for our IP? */
2677 /*XXXX+ this info should come from netinfo cells or something, or we should
2678  * do this only when we aren't seeing incoming data. see bug 652. */
2679 #define DUMMY_DOWNLOAD_INTERVAL (20*60)
2680 
2681 /** As needed, launch a dummy router descriptor fetch to see if our
2682  * address has changed. */
2683 static void
2685  const or_options_t *options)
2686 {
2687  static time_t last_dummy_download = 0;
2688  /* XXXX+ we could be smarter here; see notes on bug 652. */
2689  /* If we're a server that doesn't have a configured address, we rely on
2690  * directory fetches to learn when our address changes. So if we haven't
2691  * tried to get any routerdescs in a long time, try a dummy fetch now. */
2692  if (!options->Address &&
2693  server_mode(options) &&
2695  last_dummy_download + DUMMY_DOWNLOAD_INTERVAL < now) {
2696  last_dummy_download = now;
2697  /* XX/teor - do we want an authority here, because they are less likely
2698  * to give us the wrong address? (See #17782)
2699  * I'm leaving the previous behaviour intact, because I don't like
2700  * the idea of some relays contacting an authority every 20 minutes. */
2702  ROUTER_PURPOSE_GENERAL, "authority.z",
2704  DL_WANT_ANY_DIRSERVER);
2705  }
2706 }
2707 
2708 /** Launch downloads for router status as needed. */
2709 void
2711 {
2712  const or_options_t *options = get_options();
2713  if (should_delay_dir_fetches(options, NULL))
2714  return;
2715  if (!we_fetch_router_descriptors(options))
2716  return;
2717 
2720 }
2721 
2722 /** Launch extrainfo downloads as needed. */
2723 void
2725 {
2726  const or_options_t *options = get_options();
2727  routerlist_t *rl;
2728  smartlist_t *wanted;
2729  digestmap_t *pending;
2730  int old_routers, i, max_dl_per_req;
2731  int n_no_ei = 0, n_pending = 0, n_have = 0, n_delay = 0, n_bogus[2] = {0,0};
2732  if (! options->DownloadExtraInfo)
2733  return;
2734  if (should_delay_dir_fetches(options, NULL))
2735  return;
2737  return;
2738 
2739  pending = digestmap_new();
2741  rl = router_get_routerlist();
2742  wanted = smartlist_new();
2743  for (old_routers = 0; old_routers < 2; ++old_routers) {
2744  smartlist_t *lst = old_routers ? rl->old_routers : rl->routers;
2745  for (i = 0; i < smartlist_len(lst); ++i) {
2746  signed_descriptor_t *sd;
2747  char *d;
2748  if (old_routers)
2749  sd = smartlist_get(lst, i);
2750  else
2751  sd = &((routerinfo_t*)smartlist_get(lst, i))->cache_info;
2752  if (sd->is_extrainfo)
2753  continue; /* This should never happen. */
2754  if (old_routers && !router_get_by_id_digest(sd->identity_digest))
2755  continue; /* Couldn't check the signature if we got it. */
2756  if (sd->extrainfo_is_bogus)
2757  continue;
2758  d = sd->extra_info_digest;
2759  if (tor_digest_is_zero(d)) {
2760  ++n_no_ei;
2761  continue;
2762  }
2763  if (eimap_get(rl->extra_info_map, d)) {
2764  ++n_have;
2765  continue;
2766  }
2767  if (!download_status_is_ready(&sd->ei_dl_status, now)) {
2768  ++n_delay;
2769  continue;
2770  }
2771  if (digestmap_get(pending, d)) {
2772  ++n_pending;
2773  continue;
2774  }
2775 
2777  if (sd2 != sd) {
2778  if (sd2 != NULL) {
2779  char d1[HEX_DIGEST_LEN+1], d2[HEX_DIGEST_LEN+1];
2780  char d3[HEX_DIGEST_LEN+1], d4[HEX_DIGEST_LEN+1];
2781  base16_encode(d1, sizeof(d1), sd->identity_digest, DIGEST_LEN);
2782  base16_encode(d2, sizeof(d2), sd2->identity_digest, DIGEST_LEN);
2783  base16_encode(d3, sizeof(d3), d, DIGEST_LEN);
2784  base16_encode(d4, sizeof(d3), sd2->extra_info_digest, DIGEST_LEN);
2785 
2786  log_info(LD_DIR, "Found an entry in %s with mismatched "
2787  "router_get_by_extrainfo_digest() value. This has ID %s "
2788  "but the entry in the map has ID %s. This has EI digest "
2789  "%s and the entry in the map has EI digest %s.",
2790  old_routers?"old_routers":"routers",
2791  d1, d2, d3, d4);
2792  } else {
2793  char d1[HEX_DIGEST_LEN+1], d2[HEX_DIGEST_LEN+1];
2794  base16_encode(d1, sizeof(d1), sd->identity_digest, DIGEST_LEN);
2795  base16_encode(d2, sizeof(d2), d, DIGEST_LEN);
2796 
2797  log_info(LD_DIR, "Found an entry in %s with NULL "
2798  "router_get_by_extrainfo_digest() value. This has ID %s "
2799  "and EI digest %s.",
2800  old_routers?"old_routers":"routers",
2801  d1, d2);
2802  }
2803  ++n_bogus[old_routers];
2804  continue;
2805  }
2806  smartlist_add(wanted, d);
2807  }
2808  }
2809  digestmap_free(pending, NULL);
2810 
2811  log_info(LD_DIR, "Extrainfo download status: %d router with no ei, %d "
2812  "with present ei, %d delaying, %d pending, %d downloadable, %d "
2813  "bogus in routers, %d bogus in old_routers",
2814  n_no_ei, n_have, n_delay, n_pending, smartlist_len(wanted),
2815  n_bogus[0], n_bogus[1]);
2816 
2817  smartlist_shuffle(wanted);
2818 
2819  max_dl_per_req = max_dl_per_request(options, DIR_PURPOSE_FETCH_EXTRAINFO);
2820  for (i = 0; i < smartlist_len(wanted); i += max_dl_per_req) {
2822  wanted, i, i+max_dl_per_req,
2824  }
2825 
2826  smartlist_free(wanted);
2827 }
2828 
2829 /** Reset the consensus and extra-info download failure count on all routers.
2830  * When we get a new consensus,
2831  * routers_update_status_from_consensus_networkstatus() will reset the
2832  * download statuses on the descriptors in that consensus.
2833  */
2834 void
2836 {
2837  log_debug(LD_GENERAL,
2838  "In router_reset_descriptor_download_failures()");
2839 
2842  if (!routerlist)
2843  return;
2844  /* We want to download *all* extra-info descriptors, not just those in
2845  * the consensus we currently have (or are about to have) */
2847  {
2848  download_status_reset(&ri->cache_info.ei_dl_status);
2849  });
2851  {
2852  download_status_reset(&sd->ei_dl_status);
2853  });
2854 }
2855 
2856 /** Any changes in a router descriptor's publication time larger than this are
2857  * automatically non-cosmetic. */
2858 #define ROUTER_MAX_COSMETIC_TIME_DIFFERENCE (2*60*60)
2859 
2860 /** We allow uptime to vary from how much it ought to be by this much. */
2861 #define ROUTER_ALLOW_UPTIME_DRIFT (6*60*60)
2862 
2863 /** Return true iff the only differences between r1 and r2 are such that
2864  * would not cause a recent (post 0.1.1.6) dirserver to republish.
2865  */
2866 int
2868 {
2869  time_t r1pub, r2pub;
2870  time_t time_difference;
2871  tor_assert(r1 && r2);
2872 
2873  /* r1 should be the one that was published first. */
2874  if (r1->cache_info.published_on > r2->cache_info.published_on) {
2875  const routerinfo_t *ri_tmp = r2;
2876  r2 = r1;
2877  r1 = ri_tmp;
2878  }
2879 
2880  /* If any key fields differ, they're different. */
2881  if (r1->addr != r2->addr ||
2882  strcasecmp(r1->nickname, r2->nickname) ||
2883  r1->or_port != r2->or_port ||
2884  !tor_addr_eq(&r1->ipv6_addr, &r2->ipv6_addr) ||
2885  r1->ipv6_orport != r2->ipv6_orport ||
2886  r1->dir_port != r2->dir_port ||
2887  r1->purpose != r2->purpose ||
2888  r1->onion_pkey_len != r2->onion_pkey_len ||
2889  !tor_memeq(r1->onion_pkey, r2->onion_pkey, r1->onion_pkey_len) ||
2891  strcasecmp(r1->platform, r2->platform) ||
2892  (r1->contact_info && !r2->contact_info) || /* contact_info is optional */
2893  (!r1->contact_info && r2->contact_info) ||
2894  (r1->contact_info && r2->contact_info &&
2895  strcasecmp(r1->contact_info, r2->contact_info)) ||
2896  r1->is_hibernating != r2->is_hibernating ||
2900  return 0;
2901  if ((r1->declared_family == NULL) != (r2->declared_family == NULL))
2902  return 0;
2903  if (r1->declared_family && r2->declared_family) {
2904  int i, n;
2905  if (smartlist_len(r1->declared_family)!=smartlist_len(r2->declared_family))
2906  return 0;
2907  n = smartlist_len(r1->declared_family);
2908  for (i=0; i < n; ++i) {
2909  if (strcasecmp(smartlist_get(r1->declared_family, i),
2910  smartlist_get(r2->declared_family, i)))
2911  return 0;
2912  }
2913  }
2914 
2915  /* Did bandwidth change a lot? */
2916  if ((r1->bandwidthcapacity < r2->bandwidthcapacity/2) ||
2917  (r2->bandwidthcapacity < r1->bandwidthcapacity/2))
2918  return 0;
2919 
2920  /* Did the bandwidthrate or bandwidthburst change? */
2921  if ((r1->bandwidthrate != r2->bandwidthrate) ||
2922  (r1->bandwidthburst != r2->bandwidthburst))
2923  return 0;
2924 
2925  /* Did more than 12 hours pass? */
2927  < r2->cache_info.published_on)
2928  return 0;
2929 
2930  /* Did uptime fail to increase by approximately the amount we would think,
2931  * give or take some slop? */
2932  r1pub = r1->cache_info.published_on;
2933  r2pub = r2->cache_info.published_on;
2934  time_difference = r2->uptime - (r1->uptime + (r2pub - r1pub));
2935  if (time_difference < 0)
2936  time_difference = - time_difference;
2937  if (time_difference > ROUTER_ALLOW_UPTIME_DRIFT &&
2938  time_difference > r1->uptime * .05 &&
2939  time_difference > r2->uptime * .05)
2940  return 0;
2941 
2942  /* Otherwise, the difference is cosmetic. */
2943  return 1;
2944 }
2945 
2946 /** Check whether <b>sd</b> describes a router descriptor compatible with the
2947  * extrainfo document <b>ei</b>.
2948  *
2949  * <b>identity_pkey</b> (which must also be provided) is RSA1024 identity key
2950  * for the router. We use it to check the signature of the extrainfo document,
2951  * if it has not already been checked.
2952  *
2953  * If no router is compatible with <b>ei</b>, <b>ei</b> should be
2954  * dropped. Return 0 for "compatible", return 1 for "reject, and inform
2955  * whoever uploaded <b>ei</b>, and return -1 for "reject silently.". If
2956  * <b>msg</b> is present, set *<b>msg</b> to a description of the
2957  * incompatibility (if any).
2958  *
2959  * Set the extrainfo_is_bogus field in <b>sd</b> if the digests matched
2960  * but the extrainfo was nonetheless incompatible.
2961  **/
2962 int
2964  extrainfo_t *ei,
2965  signed_descriptor_t *sd,
2966  const char **msg)
2967 {
2968  int digest_matches, digest256_matches, r=1;
2969  tor_assert(identity_pkey);
2970  tor_assert(sd);
2971  tor_assert(ei);
2972 
2973  if (ei->bad_sig) {
2974  if (msg) *msg = "Extrainfo signature was bad, or signed with wrong key.";
2975  return 1;
2976  }
2977 
2978  digest_matches = tor_memeq(ei->cache_info.signed_descriptor_digest,
2980  /* Set digest256_matches to 1 if the digest is correct, or if no
2981  * digest256 was in the ri. */
2982  digest256_matches = tor_memeq(ei->digest256,
2984  digest256_matches |=
2986 
2987  /* The identity must match exactly to have been generated at the same time
2988  * by the same router. */
2989  if (tor_memneq(sd->identity_digest,
2990  ei->cache_info.identity_digest,
2991  DIGEST_LEN)) {
2992  if (msg) *msg = "Extrainfo nickname or identity did not match routerinfo";
2993  goto err; /* different servers */
2994  }
2995 
2997  ei->cache_info.signing_key_cert)) {
2998  if (msg) *msg = "Extrainfo signing key cert didn't match routerinfo";
2999  goto err; /* different servers */
3000  }
3001 
3002  if (ei->pending_sig) {
3003  char signed_digest[128];
3004  if (crypto_pk_public_checksig(identity_pkey,
3005  signed_digest, sizeof(signed_digest),
3006  ei->pending_sig, ei->pending_sig_len) != DIGEST_LEN ||
3007  tor_memneq(signed_digest, ei->cache_info.signed_descriptor_digest,
3008  DIGEST_LEN)) {
3009  ei->bad_sig = 1;
3010  tor_free(ei->pending_sig);
3011  if (msg) *msg = "Extrainfo signature bad, or signed with wrong key";
3012  goto err; /* Bad signature, or no match. */
3013  }
3014 
3015  ei->cache_info.send_unencrypted = sd->send_unencrypted;
3016  tor_free(ei->pending_sig);
3017  }
3018 
3019  if (ei->cache_info.published_on < sd->published_on) {
3020  if (msg) *msg = "Extrainfo published time did not match routerdesc";
3021  goto err;
3022  } else if (ei->cache_info.published_on > sd->published_on) {
3023  if (msg) *msg = "Extrainfo published time did not match routerdesc";
3024  r = -1;
3025  goto err;
3026  }
3027 
3028  if (!digest256_matches && !digest_matches) {
3029  if (msg) *msg = "Neither digest256 or digest matched "
3030  "digest from routerdesc";
3031  goto err;
3032  }
3033 
3034  if (!digest256_matches) {
3035  if (msg) *msg = "Extrainfo digest did not match digest256 from routerdesc";
3036  goto err; /* Digest doesn't match declared value. */
3037  }
3038 
3039  if (!digest_matches) {
3040  if (msg) *msg = "Extrainfo digest did not match value from routerdesc";
3041  goto err; /* Digest doesn't match declared value. */
3042  }
3043 
3044  return 0;
3045  err:
3046  if (digest_matches) {
3047  /* This signature was okay, and the digest was right: This is indeed the
3048  * corresponding extrainfo. But insanely, it doesn't match the routerinfo
3049  * that lists it. Don't try to fetch this one again. */
3050  sd->extrainfo_is_bogus = 1;
3051  }
3052 
3053  return r;
3054 }
3055 
3056 /* Does ri have a valid ntor onion key?
3057  * Valid ntor onion keys exist and have at least one non-zero byte. */
3058 int
3059 routerinfo_has_curve25519_onion_key(const routerinfo_t *ri)
3060 {
3061  if (!ri) {
3062  return 0;
3063  }
3064 
3065  if (!ri->onion_curve25519_pkey) {
3066  return 0;
3067  }
3068 
3069  if (fast_mem_is_zero((const char*)ri->onion_curve25519_pkey->public_key,
3071  return 0;
3072  }
3073 
3074  return 1;
3075 }
3076 
3077 /* Is rs running a tor version known to support EXTEND2 cells?
3078  * If allow_unknown_versions is true, return true if we can't tell
3079  * (from a versions line or a protocols line) whether it supports extend2
3080  * cells.
3081  * Otherwise, return false if the version is unknown. */
3082 int
3083 routerstatus_version_supports_extend2_cells(const routerstatus_t *rs,
3084  int allow_unknown_versions)
3085 {
3086  if (!rs) {
3087  return allow_unknown_versions;
3088  }
3089 
3090  if (!rs->pv.protocols_known) {
3091  return allow_unknown_versions;
3092  }
3093 
3094  return rs->pv.supports_extend2_cells;
3095 }
3096 
3097 /** Assert that the internal representation of <b>rl</b> is
3098  * self-consistent. */
3099 void
3101 {
3102  routerinfo_t *r2;
3103  signed_descriptor_t *sd2;
3104  if (!rl)
3105  return;
3107  r2 = rimap_get(rl->identity_map, r->cache_info.identity_digest);
3108  tor_assert(r == r2);
3109  sd2 = sdmap_get(rl->desc_digest_map,
3110  r->cache_info.signed_descriptor_digest);
3111  tor_assert(&(r->cache_info) == sd2);
3112  tor_assert(r->cache_info.routerlist_index == r_sl_idx);
3113  /* XXXX
3114  *
3115  * Hoo boy. We need to fix this one, and the fix is a bit tricky, so
3116  * commenting this out is just a band-aid.
3117  *
3118  * The problem is that, although well-behaved router descriptors
3119  * should never have the same value for their extra_info_digest, it's
3120  * possible for ill-behaved routers to claim whatever they like there.
3121  *
3122  * The real answer is to trash desc_by_eid_map and instead have
3123  * something that indicates for a given extra-info digest we want,
3124  * what its download status is. We'll do that as a part of routerlist
3125  * refactoring once consensus directories are in. For now,
3126  * this rep violation is probably harmless: an adversary can make us
3127  * reset our retry count for an extrainfo, but that's not the end
3128  * of the world. Changing the representation in 0.2.0.x would just
3129  * destabilize the codebase.
3130  if (!tor_digest_is_zero(r->cache_info.extra_info_digest)) {
3131  signed_descriptor_t *sd3 =
3132  sdmap_get(rl->desc_by_eid_map, r->cache_info.extra_info_digest);
3133  tor_assert(sd3 == &(r->cache_info));
3134  }
3135  */
3136  } SMARTLIST_FOREACH_END(r);
3138  r2 = rimap_get(rl->identity_map, sd->identity_digest);
3139  tor_assert(!r2 || sd != &(r2->cache_info));
3140  sd2 = sdmap_get(rl->desc_digest_map, sd->signed_descriptor_digest);
3141  tor_assert(sd == sd2);
3142  tor_assert(sd->routerlist_index == sd_sl_idx);
3143  /* XXXX see above.
3144  if (!tor_digest_is_zero(sd->extra_info_digest)) {
3145  signed_descriptor_t *sd3 =
3146  sdmap_get(rl->desc_by_eid_map, sd->extra_info_digest);
3147  tor_assert(sd3 == sd);
3148  }
3149  */
3150  } SMARTLIST_FOREACH_END(sd);
3151 
3152  RIMAP_FOREACH(rl->identity_map, d, r) {
3153  tor_assert(tor_memeq(r->cache_info.identity_digest, d, DIGEST_LEN));
3155  SDMAP_FOREACH(rl->desc_digest_map, d, sd) {
3156  tor_assert(tor_memeq(sd->signed_descriptor_digest, d, DIGEST_LEN));
3158  SDMAP_FOREACH(rl->desc_by_eid_map, d, sd) {
3160  tor_assert(sd);
3161  tor_assert(tor_memeq(sd->extra_info_digest, d, DIGEST_LEN));
3163  EIMAP_FOREACH(rl->extra_info_map, d, ei) {
3164  signed_descriptor_t *sd;
3165  tor_assert(tor_memeq(ei->cache_info.signed_descriptor_digest,
3166  d, DIGEST_LEN));
3167  sd = sdmap_get(rl->desc_by_eid_map,
3168  ei->cache_info.signed_descriptor_digest);
3169  // tor_assert(sd); // XXXX see above
3170  if (sd) {
3171  tor_assert(tor_memeq(ei->cache_info.signed_descriptor_digest,
3173  }
3175 }
3176 
3177 /** Allocate and return a new string representing the contact info
3178  * and platform string for <b>router</b>,
3179  * surrounded by quotes and using standard C escapes.
3180  *
3181  * THIS FUNCTION IS NOT REENTRANT. Don't call it from outside the main
3182  * thread. Also, each call invalidates the last-returned value, so don't
3183  * try log_warn(LD_GENERAL, "%s %s", esc_router_info(a), esc_router_info(b));
3184  *
3185  * If <b>router</b> is NULL, it just frees its internal memory and returns.
3186  */
3187 const char *
3189 {
3190  static char *info=NULL;
3191  char *esc_contact, *esc_platform;
3192  tor_free(info);
3193 
3194  if (!router)
3195  return NULL; /* we're exiting; just free the memory we use */
3196 
3197  esc_contact = esc_for_log(router->contact_info);
3198  esc_platform = esc_for_log(router->platform);
3199 
3200  tor_asprintf(&info, "Contact %s, Platform %s", esc_contact, esc_platform);
3201  tor_free(esc_contact);
3202  tor_free(esc_platform);
3203 
3204  return info;
3205 }
3206 
3207 /** Helper for sorting: compare two routerinfos by their identity
3208  * digest. */
3209 static int
3210 compare_routerinfo_by_id_digest_(const void **a, const void **b)
3211 {
3212  routerinfo_t *first = *(routerinfo_t **)a, *second = *(routerinfo_t **)b;
3213  return fast_memcmp(first->cache_info.identity_digest,
3214  second->cache_info.identity_digest,
3215  DIGEST_LEN);
3216 }
3217 
3218 /** Sort a list of routerinfo_t in ascending order of identity digest. */
3219 void
3221 {
3223 }
3224 
3225 /** Called when we change a node set, or when we reload the geoip IPv4 list:
3226  * recompute all country info in all configuration node sets and in the
3227  * routerlist. */
3228 void
3230 {
3231  const or_options_t *options = get_options();
3232 
3233  if (options->EntryNodes)
3235  if (options->ExitNodes)
3237  if (options->MiddleNodes)
3239  if (options->ExcludeNodes)
3241  if (options->ExcludeExitNodes)
3243  if (options->ExcludeExitNodesUnion_)
3245 
3247 }
static void signed_descriptor_free_(signed_descriptor_t *sd)
Definition: routerlist.c:882
Header file for dirserv.c.
crypto_pk_t * identity_pkey
Definition: routerinfo_st.h:43
smartlist_t * get_connection_array(void)
Definition: mainloop.c:452
void router_reset_descriptor_download_failures(void)
Definition: routerlist.c:2835
STATIC was_router_added_t extrainfo_insert(routerlist_t *rl, extrainfo_t *ei, int warn_if_incompatible)
Definition: routerlist.c:1065
size_t onion_pkey_len
Definition: routerinfo_st.h:41
int crypto_pk_eq_keys(const crypto_pk_t *a, const crypto_pk_t *b)
Definition: crypto_rsa.c:71
A relay's extra-info structure.
uint32_t router_get_advertised_bandwidth_capped(const routerinfo_t *router)
Definition: routerlist.c:572
STATIC void initiate_descriptor_downloads(const routerstatus_t *source, int purpose, smartlist_t *digests, int lo, int hi, int pds_flags)
Definition: routerlist.c:2321
extrainfo_t * router_get_my_extrainfo(void)
Definition: router.c:1687
void update_all_descriptor_downloads(time_t now)
Definition: routerlist.c:2215
Header file for dirclient.c.
desc_store_t desc_store
Definition: routerlist_st.h:39
uint16_t dir_port
Definition: routerinfo_st.h:26
void smartlist_string_remove(smartlist_t *sl, const char *element)
Definition: smartlist.c:74
smartlist_t * declared_family
Definition: routerinfo_st.h:67
Router descriptor structure.
store_type_t type
Definition: desc_store_st.h:33
char * contact_info
Definition: routerinfo_st.h:69
char * protocol_list
Definition: routerinfo_st.h:52
Common functions for using (pseudo-)random number generators.
Definition: node_st.h:34
smartlist_t * routers
Definition: routerlist_st.h:32
smartlist_t * voters
#define SMARTLIST_FOREACH_BEGIN(sl, type, var)
int router_is_me(const routerinfo_t *router)
Definition: router.c:1616
int router_differences_are_cosmetic(const routerinfo_t *r1, const routerinfo_t *r2)
Definition: routerlist.c:2867
was_router_added_t
Definition: routerlist.h:17
#define MOCK_IMPL(rv, funcname, arglist)
Definition: testsupport.h:133
static smartlist_t * warned_nicknames
Definition: routerlist.c:149
static int router_rebuild_store(int flags, desc_store_t *store)
Definition: routerlist.c:237
static int compare_duration_idx_(const void *_d1, const void *_d2)
Definition: routerlist.c:1701
static void launch_dummy_descriptor_download_as_needed(time_t now, const or_options_t *options)
Definition: routerlist.c:2684
const char * signed_descriptor_get_annotations(const signed_descriptor_t *desc)
Definition: routerlist.c:803
size_t store_len
Definition: desc_store_st.h:38
Header file for node_select.c.
void router_dir_info_changed(void)
Definition: nodelist.c:2340
void dump_routerlist_mem_usage(int severity)
Definition: routerlist.c:975
Header file for connection.c.
struct digest_sd_map_t * desc_by_eid_map
Definition: routerlist_st.h:30
#define MAX_DL_TO_DELAY
Definition: routerlist.c:2423
#define LD_GENERAL
Definition: log.h:62
int replace_file(const char *from, const char *to)
Definition: files.c:117
int authdir_mode(const or_options_t *options)
Definition: authmode.c:25
#define PDS_NO_EXISTING_SERVERDESC_FETCH
Definition: node_select.h:61
void learned_bridge_descriptor(routerinfo_t *ri, int from_cache)
Definition: bridges.c:937
#define LOG_INFO
Definition: log.h:45
void update_router_descriptor_downloads(time_t now)
Definition: routerlist.c:2710
Header file for describe.c.
Header file for nodelist.c.
int firewall_is_fascist_dir(void)
Definition: policies.c:365
signed_descriptor_t * extrainfo_get_by_descriptor_digest(const char *digest)
Definition: routerlist.c:725
Single consensus voter structure.
int we_want_to_fetch_flavor(const or_options_t *options, int flavor)
void tor_log(int severity, log_domain_mask_t domain, const char *format,...)
Definition: log.c:628
struct digest_ei_map_t * extra_info_map
Definition: routerlist_st.h:26
int addr_policies_eq(const smartlist_t *a, const smartlist_t *b)
Definition: policies.c:1351
Header file for directory.c.
int firewall_is_fascist_or(void)
Definition: policies.c:354
void smartlist_add(smartlist_t *sl, void *element)
char nickname[MAX_NICKNAME_LEN+1]
static int WRA_WAS_ADDED(was_router_added_t s)
Definition: routerlist.h:104
const char * signed_descriptor_get_body(const signed_descriptor_t *desc)
Definition: routerlist.c:795
void digestset_add(digestset_t *set, const char *digest)
Definition: digestset.c:44
Node information structure.
#define MAX_NICKNAME_LEN
Definition: or.h:112
int authdir_mode_bridge(const or_options_t *options)
Definition: authmode.c:76
struct directory_request_t directory_request_t
Definition: dirclient.h:50
void list_pending_microdesc_downloads(digest256map_t *result)
Definition: routerlist.c:2308
static int routerlist_find_elt_(smartlist_t *sl, void *ri, int idx)
Definition: routerlist.c:998
#define MIN_REQUESTS
Definition: routerlist.c:2420
Header file for config.c.
Header file for authcert.c.
static int signed_desc_digest_is_recognized(signed_descriptor_t *desc)
Definition: routerlist.c:2197
char identity_digest[DIGEST_LEN]
const or_options_t * get_options(void)
Definition: config.c:926
void refresh_all_country_info(void)
Definition: routerlist.c:3229
int fast_mem_is_zero(const char *mem, size_t len)
Definition: util_string.c:74
#define tor_assert(expr)
Definition: util_bug.h:102
int routerinfo_is_a_configured_bridge(const routerinfo_t *ri)
Definition: bridges.c:286
#define OLD_ROUTER_DESC_MAX_AGE
Definition: or.h:163
Header file for microdesc.c.
struct routerset_t * EntryNodes
Definition: or_options_st.h:83
routerinfo_t * router_get_mutable_by_digest(const char *digest)
Definition: routerlist.c:677
void routers_sort_by_identity(smartlist_t *routers)
Definition: routerlist.c:3220
int we_fetch_router_descriptors(const or_options_t *options)
Definition: microdesc.c:1074
networkstatus_t * networkstatus_get_latest_consensus_by_flavor(consensus_flavor_t f)
unsigned int supports_extend2_cells
Definition: or.h:816
consensus_flavor_t flavor
char * Address
Definition: or_options_st.h:74
download_status_t * router_get_dl_status_by_descriptor_digest(const char *d)
struct routerset_t * ExitNodes
Definition: or_options_st.h:77
Header file for reachability.c.
int strcmpstart(const char *s1, const char *s2)
Definition: util_string.c:206
char * nickname
Definition: routerinfo_st.h:22
static void routerlist_replace(routerlist_t *rl, routerinfo_t *ri_old, routerinfo_t *ri_new)
Definition: routerlist.c:1298
const routerstatus_t * networkstatus_vote_find_entry(networkstatus_t *ns, const char *digest)
#define tor_free(p)
Definition: malloc.h:52
uint8_t digest256[DIGEST256_LEN]
Definition: extrainfo_st.h:21
static routerlist_t * routerlist
Definition: routerlist.c:145
int node_has_preferred_descriptor(const node_t *node, int for_direct_connect)
Definition: nodelist.c:1351
static int router_should_rebuild_store(desc_store_t *store)
Definition: routerlist.c:172
Header file for mainloop.c.
uint32_t bandwidthrate
Definition: routerinfo_st.h:56
static int signed_desc_append_to_journal(signed_descriptor_t *desc, desc_store_t *store)
Definition: routerlist.c:196
void directory_request_set_resource(directory_request_t *req, const char *resource)
Definition: dirclient.c:1039
smartlist_t * smartlist_new(void)
int control_event_descriptors_changed(smartlist_t *routers)
unsigned int policy_is_reject_star
Definition: routerinfo_st.h:79
struct routerset_t * ExcludeNodes
Definition: or_options_st.h:89
void routerset_refresh_countries(routerset_t *target)
Definition: routerset.c:81
int node_has_curve25519_onion_key(const node_t *node)
Definition: nodelist.c:1882
static void extrainfo_free_void(void *e)
Definition: routerlist.c:936
void update_microdesc_downloads(time_t now)
Definition: microdesc.c:992
const char * description
Definition: desc_store_st.h:29
void smartlist_shuffle(smartlist_t *sl)
Definition: crypto_rand.c:602
#define STATIC
Definition: testsupport.h:32
uint8_t purpose
saved_location_t
Definition: or.h:746
#define tor_memneq(a, b, sz)
Definition: di_ops.h:21
int router_have_minimum_dir_info(void)
Definition: nodelist.c:2297
int write_str_to_file(const char *fname, const char *str, int bin)
Definition: files.c:258
#define DIR_PURPOSE_FETCH_EXTRAINFO
Definition: directory.h:41
Header file for routerset.c.
void routerlist_assert_ok(const routerlist_t *rl)
Definition: routerlist.c:3100
struct curve25519_public_key_t * onion_curve25519_pkey
Definition: routerinfo_st.h:45
int node_is_unreliable(const node_t *node, int need_uptime, int need_capacity, int need_guard)
Definition: nodelist.c:2205
Header file for directory authority mode.
int routers_have_same_or_addrs(const routerinfo_t *r1, const routerinfo_t *r2)
Definition: routerlist.c:494
void trusted_dirs_remove_old_certs(void)
Definition: authcert.c:550
size_t journal_len
Definition: desc_store_st.h:36
directory_request_t * directory_request_new(uint8_t dir_purpose)
Definition: dirclient.c:942
Trusted/fallback directory server structure.
networkstatus_t * networkstatus_get_latest_consensus(void)
int router_exit_policy_rejects_all(const routerinfo_t *router)
Definition: routerlist.c:2242
static void routerlist_insert(routerlist_t *rl, routerinfo_t *ri)
Definition: routerlist.c:1020
#define DIGEST256_LEN
Definition: digest_sizes.h:23
size_t bytes_dropped
Definition: desc_store_st.h:41
Header file for policies.c.
Authority signature structure.
char signed_descriptor_digest[DIGEST_LEN]
char descriptor_digest[DIGEST256_LEN]
void routerinfo_free_(routerinfo_t *router)
Definition: routerlist.c:835
void update_consensus_router_descriptor_downloads(time_t now, int is_vote, networkstatus_t *consensus)
Definition: routerlist.c:2530
static routerinfo_t * routerlist_reparse_old(routerlist_t *rl, signed_descriptor_t *sd)
Definition: routerlist.c:1401
void extrainfo_free_(extrainfo_t *extrainfo)
Definition: routerlist.c:865
#define DIR_PURPOSE_FETCH_SERVERDESC
Definition: directory.h:38
desc_store_t extrainfo_store
Definition: routerlist_st.h:41
void routerlist_reset_warnings(void)
Definition: routerlist.c:1444
networkstatus_t * networkstatus_get_reasonably_live_consensus(time_t now, int flavor)
int router_parse_list_from_string(const char **s, const char *eos, smartlist_t *dest, saved_location_t saved_location, int want_extrainfo, int allow_annotations, const char *prepend_annotations, smartlist_t *invalid_digests_out)
Definition: routerparse.c:245
Header for crypto_format.c.
int dirclient_fetches_dir_info_early(const or_options_t *options)
int append_bytes_to_file(const char *fname, const char *str, size_t len, int bin)
Definition: files.c:538
int router_descriptor_is_older_than(const routerinfo_t *router, int seconds)
Definition: routerlist.c:1457
Header file for routermode.c.
static void signed_descriptor_move(signed_descriptor_t *dest, signed_descriptor_t *src)
Definition: routerlist.c:908
int tor_memeq(const void *a, const void *b, size_t sz)
Definition: di_ops.c:107
int tor_asprintf(char **strp, const char *fmt,...)
Definition: printf.c:75
struct routerset_t * MiddleNodes
Definition: or_options_st.h:80
static const char * signed_descriptor_get_body_impl(const signed_descriptor_t *desc, int with_annotations)
Definition: routerlist.c:746
int authdir_mode_handles_descs(const or_options_t *options, int purpose)
Definition: authmode.c:43
dir_connection_t * TO_DIR_CONN(connection_t *c)
Definition: directory.c:85
const routerinfo_t * router_get_by_id_digest(const char *digest)
Definition: routerlist.c:691
#define DIGEST_LEN
Definition: digest_sizes.h:20
Header file for circuitbuild.c.
static int WRA_NEVER_DOWNLOADABLE(was_router_added_t s)
Definition: routerlist.h:130
unsigned int is_hibernating
Definition: routerinfo_st.h:70
routerinfo_t * router_parse_entry_from_string(const char *s, const char *end, int cache_copy, int allow_annotations, const char *prepend_annotations, int *can_dl_again_out)
Definition: routerparse.c:390
Master header file for Tor-specific functionality.
char extra_info_digest256[DIGEST256_LEN]
unsigned int protocols_known
Definition: or.h:812
signed_descriptor_t * router_get_by_extrainfo_digest(const char *digest)
Definition: routerlist.c:712
int dirclient_too_idle_to_fetch_descriptors(const or_options_t *options, time_t now)
const char * hex_str(const char *from, size_t fromlen)
Definition: binascii.c:34
download_status_t ei_dl_status
protover_summary_flags_t pv
int TestingClientMaxIntervalWithoutRequest
const char * data
Definition: mmap.h:26
int crypto_pk_public_checksig(const crypto_pk_t *env, char *to, size_t tolen, const char *from, size_t fromlen)
int dirserv_would_reject_router(const routerstatus_t *rs, const vote_routerstatus_t *vrs)
int hexdigest_to_digest(const char *hexdigest, char *digest)
Definition: routerlist.c:664
void networkstatus_reset_warnings(void)
saved_location_t saved_location
#define ROUTER_MAX_COSMETIC_TIME_DIFFERENCE
Definition: routerlist.c:2858
void routerlist_descriptors_added(smartlist_t *sl, int from_cache)
Definition: routerlist.c:1929
Header file for rephist.c.
uint32_t bandwidthcapacity
Definition: routerinfo_st.h:60
#define ROUTER_PURPOSE_BRIDGE
static void routerlist_remove_old_cached_routers_with_id(time_t now, time_t cutoff, int lo, int hi, digestset_t *retain)
Definition: routerlist.c:1717
void networkstatus_reset_download_failures(void)
#define ROUTER_PURPOSE_GENERAL
struct digest_ri_map_t * identity_map
Definition: routerlist_st.h:20
#define LOG_WARN
Definition: log.h:53
uint32_t bandwidthburst
Definition: routerinfo_st.h:58
static void signed_descriptor_reset(signed_descriptor_t *sd)
Definition: routerlist.c:897
static void list_pending_descriptor_downloads(digestmap_t *result, int extrainfo)
Definition: routerlist.c:2297
#define MIN_DL_PER_REQUEST
Definition: routerlist.c:2417
const char * routerstatus_describe(const routerstatus_t *rs)
Definition: describe.c:184
Header for feature/dirclient/dirclient_modes.c.
struct short_policy_t * ipv6_exit_policy
Definition: routerinfo_st.h:65
#define PDS_RETRY_IF_NO_SERVERS
Definition: node_select.h:48
#define log_fn_ratelim(ratelim, severity, domain, args,...)
Definition: log.h:292
void base16_encode(char *dest, size_t destlen, const char *src, size_t srclen)
Definition: binascii.c:478
signed_descriptor_t * router_get_by_descriptor_digest(const char *digest)
Definition: routerlist.c:699
void routers_update_status_from_consensus_networkstatus(smartlist_t *routers, int reset_failures)
void smartlist_del(smartlist_t *sl, int idx)
static signed_descriptor_t * signed_descriptor_from_routerinfo(routerinfo_t *ri)
Definition: routerlist.c:924
#define RFTS_IGNORE_MISSING
Definition: files.h:97
Header file for process_descs.c.
#define ROUTER_ALLOW_UPTIME_DRIFT
Definition: routerlist.c:2861
Types to handle sets of digests, based on bloom filters.
void routerlist_remove_old_routers(void)
Definition: routerlist.c:1803
time_t cert_expiration_time
Definition: routerinfo_st.h:48
int tor_digest_is_zero(const char *digest)
Definition: util_string.c:96
void digest256_to_base64(char *d64, const char *digest)
Client/server directory connection structure.
#define DIGESTMAP_FOREACH_END
Definition: map.h:168
#define LD_FS
Definition: log.h:70
void directory_get_from_dirserver(uint8_t dir_purpose, uint8_t router_purpose, const char *resource, int pds_flags, download_want_authority_t want_authority)
Definition: dirclient.c:453
const char * esc_router_info(const routerinfo_t *router)
Definition: routerlist.c:3188
unsigned int bad_sig
Definition: extrainfo_st.h:26
const routerinfo_t * routerlist_find_my_routerinfo(void)
Definition: routerlist.c:542
#define HEX_DIGEST_LEN
Definition: crypto_digest.h:35
char * platform
Definition: routerinfo_st.h:50
#define LD_DIR
Definition: log.h:88
void router_reset_status_download_failures(void)
Definition: dirlist.c:103
node_t * nodelist_set_routerinfo(routerinfo_t *ri, routerinfo_t **ri_old_out)
Definition: nodelist.c:493
int router_load_single_router(const char *s, uint8_t purpose, int cache, const char **msg)
Definition: routerlist.c:1958
void launch_descriptor_downloads(int purpose, smartlist_t *downloadable, const routerstatus_t *source, time_t now)
Definition: routerlist.c:2432
const smartlist_t * nodelist_get_list(void)
Definition: nodelist.c:948
struct routerset_t * ExcludeExitNodes
Definition: or_options_st.h:93
int hex_digest_nickname_matches(const char *hexdigest, const char *identity_digest, const char *nickname)
Definition: routerlist.c:635
int smartlist_contains_string(const smartlist_t *sl, const char *element)
Definition: smartlist.c:93
int digestset_probably_contains(const digestset_t *set, const char *digest)
Definition: digestset.c:54
static time_t last_descriptor_download_attempted
Definition: routerlist.c:154
void router_add_running_nodes_to_smartlist(smartlist_t *sl, int need_uptime, int need_capacity, int need_guard, int need_desc, int pref_addr, int direct_conn)
Definition: routerlist.c:505
int hex_digest_nickname_decode(const char *hexdigest, char *digest_out, char *nickname_qualifier_char_out, char *nickname_out)
Definition: routerlist.c:599
void rep_hist_note_router_unreachable(const char *id, time_t when)
Definition: rephist.c:314
int tor_snprintf(char *str, size_t size, const char *format,...)
Definition: printf.c:27
void format_iso_time(char *buf, time_t t)
Definition: time_fmt.c:295
const routerinfo_t * router_get_my_routerinfo(void)
Definition: router.c:1624
char * smartlist_join_strings(smartlist_t *sl, const char *join, int terminate, size_t *len_out)
Definition: smartlist.c:279
int authdir_wants_to_reject_router(routerinfo_t *ri, const char **msg, int complain, int *valid_out)
void list_pending_downloads(digestmap_t *result, digest256map_t *result256, int purpose, const char *prefix)
Definition: routerlist.c:2254
#define RFTS_BIN
Definition: files.h:95
tor_mmap_t * mmap
Definition: desc_store_st.h:31
#define SMARTLIST_FOREACH(sl, type, var, cmd)
const char * fname_base
Definition: desc_store_st.h:27
const char * escaped(const char *s)
Definition: escape.c:126
smartlist_t * old_routers
Definition: routerlist_st.h:35
static int compare_signed_descriptors_by_age_(const void **_a, const void **_b)
Definition: routerlist.c:221
smartlist_t * routerstatus_list
void routerlist_retry_directory_downloads(time_t now)
Definition: routerlist.c:2227
void routerlist_remove(routerlist_t *rl, routerinfo_t *ri, int make_old, time_t now)
Definition: routerlist.c:1186
char identity_digest[DIGEST_LEN]
static void routerlist_insert_old(routerlist_t *rl, routerinfo_t *ri)
Definition: routerlist.c:1151
Header file for dlstatus.c.
int fascist_firewall_allows_node(const node_t *node, firewall_connection_t fw_connection, int pref_only)
Definition: policies.c:733
void directory_initiate_request(directory_request_t *request)
Definition: dirclient.c:1229
const char * router_purpose_to_string(uint8_t p)
Definition: routerinfo.c:59
smartlist_t * exit_policy
Definition: routerinfo_st.h:61
#define log_fn(severity, domain, args,...)
Definition: log.h:287
char * onion_pkey
Definition: routerinfo_st.h:39
void dirserv_single_reachability_test(time_t now, routerinfo_t *router)
Definition: reachability.c:128
int dir_split_resource_into_fingerprints(const char *resource, smartlist_t *fp_out, int *compressed_out, int flags)
Definition: directory.c:628
routerstatus_t * networkstatus_vote_find_mutable_entry(networkstatus_t *ns, const char *digest)
void smartlist_sort_digests(smartlist_t *sl)
Definition: smartlist.c:824
#define DIR_PURPOSE_FETCH_MICRODESC
Definition: directory.h:70
void update_extrainfo_downloads(time_t now)
Definition: routerlist.c:2724
#define tor_addr_eq(a, b)
Definition: address.h:244
#define fast_memcmp(a, b, c)
Definition: di_ops.h:28
tor_addr_t ipv6_addr
Definition: routerinfo_st.h:32
time_t approx_time(void)
Definition: approx_time.c:32
static int WRA_WAS_OUTDATED(was_router_added_t s)
Definition: routerlist.h:114
int tor_cert_opt_eq(const tor_cert_t *cert1, const tor_cert_t *cert2)
Definition: torcert.c:315
void routerlist_free_all(void)
Definition: routerlist.c:1426
#define BASE64_DIGEST256_LEN
Definition: crypto_digest.h:29
uint16_t or_port
Definition: routerinfo_st.h:25
Header for torcert.c.
Header file for dirlist.c.
#define PDS_NO_EXISTING_MICRODESC_FETCH
Definition: node_select.h:67
dir_server_t * trusteddirserver_get_by_v3_auth_digest(const char *digest)
Definition: dirlist.c:167
int router_reload_router_list(void)
Definition: routerlist.c:458
struct tor_cert_st * signing_key_cert
void reschedule_directory_downloads(void)
Definition: mainloop.c:1610
static int compare_old_routers_by_identity_(const void **_a, const void **_b)
Definition: routerlist.c:1681
struct routerset_t * ExcludeExitNodesUnion_
Definition: or_options_st.h:99
int directory_caches_dir_info(const or_options_t *options)
Definition: dirserv.c:94
char extra_info_digest[DIGEST_LEN]
was_router_added_t router_add_to_routerlist(routerinfo_t *router, const char **msg, int from_cache, int from_fetch)
Definition: routerlist.c:1484
void nodelist_remove_routerinfo(routerinfo_t *ri)
Definition: nodelist.c:727
int base16_decode(char *dest, size_t destlen, const char *src, size_t srclen)
Definition: binascii.c:506
size_t size
Definition: mmap.h:27
#define CONN_TYPE_DIR
Definition: connection.h:53
uint32_t addr
Definition: routerinfo_st.h:24
routerstatus_t fake_status
Definition: dir_server_st.h:51
#define ROUTER_ANNOTATION_BUF_LEN
Definition: or.h:803
static int compare_routerinfo_by_id_digest_(const void **a, const void **b)
Definition: routerlist.c:3210
struct digest_sd_map_t * desc_digest_map
Definition: routerlist_st.h:23
char * esc_for_log(const char *s)
Definition: escape.c:30
digestset_t * digestset_new(int max_guess)
Definition: digestset.c:30
static desc_store_t * desc_get_store(routerlist_t *rl, const signed_descriptor_t *sd)
Definition: routerlist.c:184
void download_status_mark_impossible(download_status_t *dl)
Definition: dlstatus.c:393
static void routerlist_remove_old(routerlist_t *rl, signed_descriptor_t *sd, int idx)
Definition: routerlist.c:1245
int server_mode(const or_options_t *options)
Definition: routermode.c:34
void nodelist_refresh_countries(void)
Definition: nodelist.c:1950
int routerinfo_incompatible_with_extrainfo(const crypto_pk_t *identity_pkey, extrainfo_t *ei, signed_descriptor_t *sd, const char **msg)
Definition: routerlist.c:2963
Header file for routerinfo.c.
int download_status_is_ready(download_status_t *dls, time_t now)
Definition: dlstatus.c:381
#define DUMMY_DOWNLOAD_INTERVAL
Definition: routerlist.c:2679
int client_would_use_router(const routerstatus_t *rs, time_t now)
Header file for control_events.c.
void smartlist_clear(smartlist_t *sl)
void routerlist_free_(routerlist_t *rl)
Definition: routerlist.c:943
#define ROUTER_MAX_AGE
Definition: or.h:158
void directory_request_set_routerstatus(directory_request_t *req, const routerstatus_t *status)
Definition: dirclient.c:1156
uint32_t router_get_advertised_bandwidth(const routerinfo_t *router)
Definition: routerlist.c:558
void smartlist_sort(smartlist_t *sl, int(*compare)(const void **a, const void **b))
Definition: smartlist.c:334
static int router_reload_router_list_impl(desc_store_t *store)
Definition: routerlist.c:391
#define DEFAULT_MAX_BELIEVABLE_BANDWIDTH
Definition: routerlist.c:567
const char * router_describe(const routerinfo_t *ri)
Definition: describe.c:123
int should_delay_dir_fetches(const or_options_t *options, const char **msg_out)
char * pending_sig
Definition: extrainfo_st.h:29
routerlist_t * router_get_routerlist(void)
Definition: routerlist.c:810
was_router_added_t router_add_extrainfo_to_routerlist(extrainfo_t *ei, const char **msg, int from_cache, int from_fetch)
Definition: routerlist.c:1660
file_status_t file_status(const char *filename)
Definition: files.c:212
Header file for networkstatus.c.
#define LD_BUG
Definition: log.h:86
Router descriptor list structure.
#define CURVE25519_PUBKEY_LEN
Definition: x25519_sizes.h:20
static int max_dl_per_request(const or_options_t *options, int purpose)
Definition: routerlist.c:2388
Header file for routerlist.c.
Routerstatus (vote entry) structure.
size_t pending_sig_len
Definition: extrainfo_st.h:31
Header file for routerparse.c.
unsigned int supports_tunnelled_dir_requests
Definition: routerinfo_st.h:88
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)
Definition: routerlist.c:2025
Networkstatus consensus/vote structure.
void router_load_extrainfo_from_string(const char *s, const char *eos, saved_location_t saved_location, smartlist_t *requested_fingerprints, int descriptor_digests)
Definition: routerlist.c:2124