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