"Fossies" - the Fresh Open Source Software Archive

Member "tor-0.4.1.6/src/feature/dirauth/dirvote.c" (10 Jun 2019, 169023 Bytes) of package /linux/misc/tor-0.4.1.6.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "dirvote.c" see the Fossies "Dox" file reference documentation and the last Fossies "Diffs" side-by-side code changes report: 0.4.1.6_vs_0.4.2.4-rc.

    1 /* Copyright (c) 2001-2004, Roger Dingledine.
    2  * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
    3  * Copyright (c) 2007-2019, The Tor Project, Inc. */
    4 /* See LICENSE for licensing information */
    5 
    6 #define DIRVOTE_PRIVATE
    7 #include "core/or/or.h"
    8 #include "app/config/config.h"
    9 #include "core/or/policies.h"
   10 #include "core/or/protover.h"
   11 #include "core/or/tor_version_st.h"
   12 #include "core/or/versions.h"
   13 #include "feature/dirauth/bwauth.h"
   14 #include "feature/dirauth/dircollate.h"
   15 #include "feature/dirauth/dsigs_parse.h"
   16 #include "feature/dirauth/guardfraction.h"
   17 #include "feature/dirauth/recommend_pkg.h"
   18 #include "feature/dirauth/voteflags.h"
   19 #include "feature/dircache/dirserv.h"
   20 #include "feature/dirclient/dirclient.h"
   21 #include "feature/dircommon/directory.h"
   22 #include "feature/dirparse/microdesc_parse.h"
   23 #include "feature/dirparse/ns_parse.h"
   24 #include "feature/dirparse/parsecommon.h"
   25 #include "feature/dirparse/signing.h"
   26 #include "feature/nodelist/authcert.h"
   27 #include "feature/nodelist/dirlist.h"
   28 #include "feature/nodelist/fmt_routerstatus.h"
   29 #include "feature/nodelist/microdesc.h"
   30 #include "feature/nodelist/networkstatus.h"
   31 #include "feature/nodelist/nodefamily.h"
   32 #include "feature/nodelist/nodelist.h"
   33 #include "feature/nodelist/routerlist.h"
   34 #include "feature/relay/router.h"
   35 #include "feature/relay/routerkeys.h"
   36 #include "feature/stats/rephist.h"
   37 #include "feature/client/entrynodes.h" /* needed for guardfraction methods */
   38 #include "feature/nodelist/torcert.h"
   39 #include "feature/dircommon/voting_schedule.h"
   40 
   41 #include "feature/dirauth/dirvote.h"
   42 #include "feature/dirauth/authmode.h"
   43 #include "feature/dirauth/shared_random_state.h"
   44 
   45 #include "feature/nodelist/authority_cert_st.h"
   46 #include "feature/dircache/cached_dir_st.h"
   47 #include "feature/dirclient/dir_server_st.h"
   48 #include "feature/nodelist/document_signature_st.h"
   49 #include "feature/nodelist/microdesc_st.h"
   50 #include "feature/nodelist/networkstatus_st.h"
   51 #include "feature/nodelist/networkstatus_voter_info_st.h"
   52 #include "feature/nodelist/node_st.h"
   53 #include "feature/dirauth/ns_detached_signatures_st.h"
   54 #include "feature/nodelist/routerinfo_st.h"
   55 #include "feature/nodelist/routerlist_st.h"
   56 #include "feature/dirauth/vote_microdesc_hash_st.h"
   57 #include "feature/nodelist/vote_routerstatus_st.h"
   58 #include "feature/dircommon/vote_timing_st.h"
   59 
   60 #include "lib/container/order.h"
   61 #include "lib/encoding/confline.h"
   62 #include "lib/crypt_ops/crypto_format.h"
   63 
   64 /* Algorithm to use for the bandwidth file digest. */
   65 #define DIGEST_ALG_BW_FILE DIGEST_SHA256
   66 
   67 /**
   68  * \file dirvote.c
   69  * \brief Functions to compute directory consensus, and schedule voting.
   70  *
   71  * This module is the center of the consensus-voting based directory
   72  * authority system.  With this system, a set of authorities first
   73  * publish vote based on their opinions of the network, and then compute
   74  * a consensus from those votes.  Each authority signs the consensus,
   75  * and clients trust the consensus if enough known authorities have
   76  * signed it.
   77  *
   78  * The code in this module is only invoked on directory authorities.  It's
   79  * responsible for:
   80  *
   81  * <ul>
   82  *   <li>Generating this authority's vote networkstatus, based on the
   83  *       authority's view of the network as represented in dirserv.c
   84  *   <li>Formatting the vote networkstatus objects.
   85  *   <li>Generating the microdescriptors that correspond to our own
   86  *       vote.
   87  *   <li>Sending votes to all the other authorities.
   88  *   <li>Trying to fetch missing votes from other authorities.
   89  *   <li>Computing the consensus from a set of votes, as well as
   90  *       a "detached signature" object for other authorities to fetch.
   91  *   <li>Collecting other authorities' signatures on the same consensus,
   92  *       until there are enough.
   93  *   <li>Publishing the consensus to the reset of the directory system.
   94  *   <li>Scheduling all of the above operations.
   95  * </ul>
   96  *
   97  * The main entry points are in dirvote_act(), which handles scheduled
   98  * actions; and dirvote_add_vote() and dirvote_add_signatures(), which
   99  * handle uploaded and downloaded votes and signatures.
  100  *
  101  * (See dir-spec.txt from torspec.git for a complete specification of
  102  * the directory protocol and voting algorithms.)
  103  **/
  104 
  105 /** A consensus that we have built and are appending signatures to.  Once it's
  106  * time to publish it, it will become an active consensus if it accumulates
  107  * enough signatures. */
  108 typedef struct pending_consensus_t {
  109   /** The body of the consensus that we're currently building.  Once we
  110    * have it built, it goes into dirserv.c */
  111   char *body;
  112   /** The parsed in-progress consensus document. */
  113   networkstatus_t *consensus;
  114 } pending_consensus_t;
  115 
  116 /* DOCDOC dirvote_add_signatures_to_all_pending_consensuses */
  117 static int dirvote_add_signatures_to_all_pending_consensuses(
  118                        const char *detached_signatures_body,
  119                        const char *source,
  120                        const char **msg_out);
  121 static int dirvote_add_signatures_to_pending_consensus(
  122                        pending_consensus_t *pc,
  123                        ns_detached_signatures_t *sigs,
  124                        const char *source,
  125                        int severity,
  126                        const char **msg_out);
  127 static char *list_v3_auth_ids(void);
  128 static void dirvote_fetch_missing_votes(void);
  129 static void dirvote_fetch_missing_signatures(void);
  130 static int dirvote_perform_vote(void);
  131 static void dirvote_clear_votes(int all_votes);
  132 static int dirvote_compute_consensuses(void);
  133 static int dirvote_publish_consensus(void);
  134 
  135 /* =====
  136  * Certificate functions
  137  * ===== */
  138 
  139 /** Allocate and return a new authority_cert_t with the same contents as
  140  * <b>cert</b>. */
  141 STATIC authority_cert_t *
  142 authority_cert_dup(authority_cert_t *cert)
  143 {
  144   authority_cert_t *out = tor_malloc(sizeof(authority_cert_t));
  145   tor_assert(cert);
  146 
  147   memcpy(out, cert, sizeof(authority_cert_t));
  148   /* Now copy pointed-to things. */
  149   out->cache_info.signed_descriptor_body =
  150     tor_strndup(cert->cache_info.signed_descriptor_body,
  151                 cert->cache_info.signed_descriptor_len);
  152   out->cache_info.saved_location = SAVED_NOWHERE;
  153   out->identity_key = crypto_pk_dup_key(cert->identity_key);
  154   out->signing_key = crypto_pk_dup_key(cert->signing_key);
  155 
  156   return out;
  157 }
  158 
  159 /* =====
  160  * Voting
  161  * =====*/
  162 
  163 /* If <b>opt_value</b> is non-NULL, return "keyword opt_value\n" in a new
  164  * string. Otherwise return a new empty string. */
  165 static char *
  166 format_line_if_present(const char *keyword, const char *opt_value)
  167 {
  168   if (opt_value) {
  169     char *result = NULL;
  170     tor_asprintf(&result, "%s %s\n", keyword, opt_value);
  171     return result;
  172   } else {
  173     return tor_strdup("");
  174   }
  175 }
  176 
  177 /** Format the recommended/required-relay-client protocols lines for a vote in
  178  * a newly allocated string, and return that string. */
  179 static char *
  180 format_protocols_lines_for_vote(const networkstatus_t *v3_ns)
  181 {
  182   char *recommended_relay_protocols_line = NULL;
  183   char *recommended_client_protocols_line = NULL;
  184   char *required_relay_protocols_line = NULL;
  185   char *required_client_protocols_line = NULL;
  186 
  187   recommended_relay_protocols_line =
  188     format_line_if_present("recommended-relay-protocols",
  189                            v3_ns->recommended_relay_protocols);
  190   recommended_client_protocols_line =
  191     format_line_if_present("recommended-client-protocols",
  192                            v3_ns->recommended_client_protocols);
  193   required_relay_protocols_line =
  194     format_line_if_present("required-relay-protocols",
  195                            v3_ns->required_relay_protocols);
  196   required_client_protocols_line =
  197     format_line_if_present("required-client-protocols",
  198                            v3_ns->required_client_protocols);
  199 
  200   char *result = NULL;
  201   tor_asprintf(&result, "%s%s%s%s",
  202                recommended_relay_protocols_line,
  203                recommended_client_protocols_line,
  204                required_relay_protocols_line,
  205                required_client_protocols_line);
  206 
  207   tor_free(recommended_relay_protocols_line);
  208   tor_free(recommended_client_protocols_line);
  209   tor_free(required_relay_protocols_line);
  210   tor_free(required_client_protocols_line);
  211 
  212   return result;
  213 }
  214 
  215 /** Return a new string containing the string representation of the vote in
  216  * <b>v3_ns</b>, signed with our v3 signing key <b>private_signing_key</b>.
  217  * For v3 authorities. */
  218 STATIC char *
  219 format_networkstatus_vote(crypto_pk_t *private_signing_key,
  220                           networkstatus_t *v3_ns)
  221 {
  222   smartlist_t *chunks = smartlist_new();
  223   char *packages = NULL;
  224   char fingerprint[FINGERPRINT_LEN+1];
  225   char digest[DIGEST_LEN];
  226   uint32_t addr;
  227   char *protocols_lines = NULL;
  228   char *client_versions_line = NULL, *server_versions_line = NULL;
  229   char *shared_random_vote_str = NULL;
  230   networkstatus_voter_info_t *voter;
  231   char *status = NULL;
  232 
  233   tor_assert(private_signing_key);
  234   tor_assert(v3_ns->type == NS_TYPE_VOTE || v3_ns->type == NS_TYPE_OPINION);
  235 
  236   voter = smartlist_get(v3_ns->voters, 0);
  237 
  238   addr = voter->addr;
  239 
  240   base16_encode(fingerprint, sizeof(fingerprint),
  241                 v3_ns->cert->cache_info.identity_digest, DIGEST_LEN);
  242 
  243   client_versions_line = format_line_if_present("client-versions",
  244                                                 v3_ns->client_versions);
  245   server_versions_line = format_line_if_present("server-versions",
  246                                                 v3_ns->server_versions);
  247   protocols_lines = format_protocols_lines_for_vote(v3_ns);
  248 
  249   if (v3_ns->package_lines) {
  250     smartlist_t *tmp = smartlist_new();
  251     SMARTLIST_FOREACH(v3_ns->package_lines, const char *, p,
  252                       if (validate_recommended_package_line(p))
  253                         smartlist_add_asprintf(tmp, "package %s\n", p));
  254     smartlist_sort_strings(tmp);
  255     packages = smartlist_join_strings(tmp, "", 0, NULL);
  256     SMARTLIST_FOREACH(tmp, char *, cp, tor_free(cp));
  257     smartlist_free(tmp);
  258   } else {
  259     packages = tor_strdup("");
  260   }
  261 
  262     /* Get shared random commitments/reveals line(s). */
  263   shared_random_vote_str = sr_get_string_for_vote();
  264 
  265   {
  266     char published[ISO_TIME_LEN+1];
  267     char va[ISO_TIME_LEN+1];
  268     char fu[ISO_TIME_LEN+1];
  269     char vu[ISO_TIME_LEN+1];
  270     char *flags = smartlist_join_strings(v3_ns->known_flags, " ", 0, NULL);
  271     /* XXXX Abstraction violation: should be pulling a field out of v3_ns.*/
  272     char *flag_thresholds = dirserv_get_flag_thresholds_line();
  273     char *params;
  274     char *bw_headers_line = NULL;
  275     char *bw_file_digest = NULL;
  276     authority_cert_t *cert = v3_ns->cert;
  277     char *methods =
  278       make_consensus_method_list(MIN_SUPPORTED_CONSENSUS_METHOD,
  279                                  MAX_SUPPORTED_CONSENSUS_METHOD, " ");
  280     format_iso_time(published, v3_ns->published);
  281     format_iso_time(va, v3_ns->valid_after);
  282     format_iso_time(fu, v3_ns->fresh_until);
  283     format_iso_time(vu, v3_ns->valid_until);
  284 
  285     if (v3_ns->net_params)
  286       params = smartlist_join_strings(v3_ns->net_params, " ", 0, NULL);
  287     else
  288       params = tor_strdup("");
  289     tor_assert(cert);
  290 
  291     /* v3_ns->bw_file_headers is only set when V3BandwidthsFile is
  292      * configured */
  293     if (v3_ns->bw_file_headers) {
  294       char *bw_file_headers = NULL;
  295       /* If there are too many headers, leave the header string NULL */
  296       if (! BUG(smartlist_len(v3_ns->bw_file_headers)
  297                 > MAX_BW_FILE_HEADER_COUNT_IN_VOTE)) {
  298         bw_file_headers = smartlist_join_strings(v3_ns->bw_file_headers, " ",
  299                                                  0, NULL);
  300         if (BUG(strlen(bw_file_headers) > MAX_BW_FILE_HEADERS_LINE_LEN)) {
  301           /* Free and set to NULL, because the line was too long */
  302           tor_free(bw_file_headers);
  303         }
  304       }
  305       if (!bw_file_headers) {
  306           /* If parsing failed, add a bandwidth header line with no entries */
  307           bw_file_headers = tor_strdup("");
  308       }
  309       /* At this point, the line will always be present */
  310       bw_headers_line = format_line_if_present("bandwidth-file-headers",
  311                                                bw_file_headers);
  312       tor_free(bw_file_headers);
  313     }
  314 
  315     /* Create bandwidth-file-digest if applicable.
  316      * v3_ns->b64_digest_bw_file will contain the digest when V3BandwidthsFile
  317      * is configured and the bandwidth file could be read, even if it was not
  318      * parseable.
  319      */
  320     if (!tor_digest256_is_zero((const char *)v3_ns->bw_file_digest256)) {
  321       /* Encode the digest. */
  322       char b64_digest_bw_file[BASE64_DIGEST256_LEN+1] = {0};
  323       digest256_to_base64(b64_digest_bw_file,
  324                           (const char *)v3_ns->bw_file_digest256);
  325       /* "bandwidth-file-digest" 1*(SP algorithm "=" digest) NL */
  326       char *digest_algo_b64_digest_bw_file = NULL;
  327       tor_asprintf(&digest_algo_b64_digest_bw_file, "%s=%s",
  328                    crypto_digest_algorithm_get_name(DIGEST_ALG_BW_FILE),
  329                    b64_digest_bw_file);
  330       /* No need for tor_strdup(""), format_line_if_present does it. */
  331       bw_file_digest = format_line_if_present(
  332           "bandwidth-file-digest", digest_algo_b64_digest_bw_file);
  333       tor_free(digest_algo_b64_digest_bw_file);
  334     }
  335 
  336     smartlist_add_asprintf(chunks,
  337                  "network-status-version 3\n"
  338                  "vote-status %s\n"
  339                  "consensus-methods %s\n"
  340                  "published %s\n"
  341                  "valid-after %s\n"
  342                  "fresh-until %s\n"
  343                  "valid-until %s\n"
  344                  "voting-delay %d %d\n"
  345                  "%s%s" /* versions */
  346                  "%s" /* protocols */
  347                  "%s" /* packages */
  348                  "known-flags %s\n"
  349                  "flag-thresholds %s\n"
  350                  "params %s\n"
  351                  "%s" /* bandwidth file headers */
  352                  "%s" /* bandwidth file digest */
  353                  "dir-source %s %s %s %s %d %d\n"
  354                  "contact %s\n"
  355                  "%s" /* shared randomness information */
  356                  ,
  357                  v3_ns->type == NS_TYPE_VOTE ? "vote" : "opinion",
  358                  methods,
  359                  published, va, fu, vu,
  360                  v3_ns->vote_seconds, v3_ns->dist_seconds,
  361                  client_versions_line,
  362                  server_versions_line,
  363                  protocols_lines,
  364                  packages,
  365                  flags,
  366                  flag_thresholds,
  367                  params,
  368                  bw_headers_line ? bw_headers_line : "",
  369                  bw_file_digest ? bw_file_digest: "",
  370                  voter->nickname, fingerprint, voter->address,
  371                  fmt_addr32(addr), voter->dir_port, voter->or_port,
  372                  voter->contact,
  373                  shared_random_vote_str ?
  374                            shared_random_vote_str : "");
  375 
  376     tor_free(params);
  377     tor_free(flags);
  378     tor_free(flag_thresholds);
  379     tor_free(methods);
  380     tor_free(shared_random_vote_str);
  381     tor_free(bw_headers_line);
  382     tor_free(bw_file_digest);
  383 
  384     if (!tor_digest_is_zero(voter->legacy_id_digest)) {
  385       char fpbuf[HEX_DIGEST_LEN+1];
  386       base16_encode(fpbuf, sizeof(fpbuf), voter->legacy_id_digest, DIGEST_LEN);
  387       smartlist_add_asprintf(chunks, "legacy-dir-key %s\n", fpbuf);
  388     }
  389 
  390     smartlist_add(chunks, tor_strndup(cert->cache_info.signed_descriptor_body,
  391                                       cert->cache_info.signed_descriptor_len));
  392   }
  393 
  394   SMARTLIST_FOREACH_BEGIN(v3_ns->routerstatus_list, vote_routerstatus_t *,
  395                           vrs) {
  396     char *rsf;
  397     vote_microdesc_hash_t *h;
  398     rsf = routerstatus_format_entry(&vrs->status,
  399                                     vrs->version, vrs->protocols,
  400                                     NS_V3_VOTE,
  401                                     ROUTERSTATUS_FORMAT_NO_CONSENSUS_METHOD,
  402                                     vrs);
  403     if (rsf)
  404       smartlist_add(chunks, rsf);
  405 
  406     for (h = vrs->microdesc; h; h = h->next) {
  407       smartlist_add_strdup(chunks, h->microdesc_hash_line);
  408     }
  409   } SMARTLIST_FOREACH_END(vrs);
  410 
  411   smartlist_add_strdup(chunks, "directory-footer\n");
  412 
  413   /* The digest includes everything up through the space after
  414    * directory-signature.  (Yuck.) */
  415   crypto_digest_smartlist(digest, DIGEST_LEN, chunks,
  416                           "directory-signature ", DIGEST_SHA1);
  417 
  418   {
  419     char signing_key_fingerprint[FINGERPRINT_LEN+1];
  420     if (crypto_pk_get_fingerprint(private_signing_key,
  421                                   signing_key_fingerprint, 0)<0) {
  422       log_warn(LD_BUG, "Unable to get fingerprint for signing key");
  423       goto err;
  424     }
  425 
  426     smartlist_add_asprintf(chunks, "directory-signature %s %s\n", fingerprint,
  427                            signing_key_fingerprint);
  428   }
  429 
  430   {
  431     char *sig = router_get_dirobj_signature(digest, DIGEST_LEN,
  432                                             private_signing_key);
  433     if (!sig) {
  434       log_warn(LD_BUG, "Unable to sign networkstatus vote.");
  435       goto err;
  436     }
  437     smartlist_add(chunks, sig);
  438   }
  439 
  440   status = smartlist_join_strings(chunks, "", 0, NULL);
  441 
  442   {
  443     networkstatus_t *v;
  444     if (!(v = networkstatus_parse_vote_from_string(status, strlen(status),
  445                                                    NULL,
  446                                                    v3_ns->type))) {
  447       log_err(LD_BUG,"Generated a networkstatus %s we couldn't parse: "
  448               "<<%s>>",
  449               v3_ns->type == NS_TYPE_VOTE ? "vote" : "opinion", status);
  450       goto err;
  451     }
  452     networkstatus_vote_free(v);
  453   }
  454 
  455   goto done;
  456 
  457  err:
  458   tor_free(status);
  459  done:
  460   tor_free(client_versions_line);
  461   tor_free(server_versions_line);
  462   tor_free(protocols_lines);
  463   tor_free(packages);
  464 
  465   SMARTLIST_FOREACH(chunks, char *, cp, tor_free(cp));
  466   smartlist_free(chunks);
  467   return status;
  468 }
  469 
  470 /** Set *<b>timing_out</b> to the intervals at which we would like to vote.
  471  * Note that these aren't the intervals we'll use to vote; they're the ones
  472  * that we'll vote to use. */
  473 static void
  474 dirvote_get_preferred_voting_intervals(vote_timing_t *timing_out)
  475 {
  476   const or_options_t *options = get_options();
  477 
  478   tor_assert(timing_out);
  479 
  480   timing_out->vote_interval = options->V3AuthVotingInterval;
  481   timing_out->n_intervals_valid = options->V3AuthNIntervalsValid;
  482   timing_out->vote_delay = options->V3AuthVoteDelay;
  483   timing_out->dist_delay = options->V3AuthDistDelay;
  484 }
  485 
  486 /* =====
  487  * Consensus generation
  488  * ===== */
  489 
  490 /** If <b>vrs</b> has a hash made for the consensus method <b>method</b> with
  491  * the digest algorithm <b>alg</b>, decode it and copy it into
  492  * <b>digest256_out</b> and return 0.  Otherwise return -1. */
  493 static int
  494 vote_routerstatus_find_microdesc_hash(char *digest256_out,
  495                                       const vote_routerstatus_t *vrs,
  496                                       int method,
  497                                       digest_algorithm_t alg)
  498 {
  499   /* XXXX only returns the sha256 method. */
  500   const vote_microdesc_hash_t *h;
  501   char mstr[64];
  502   size_t mlen;
  503   char dstr[64];
  504 
  505   tor_snprintf(mstr, sizeof(mstr), "%d", method);
  506   mlen = strlen(mstr);
  507   tor_snprintf(dstr, sizeof(dstr), " %s=",
  508                crypto_digest_algorithm_get_name(alg));
  509 
  510   for (h = vrs->microdesc; h; h = h->next) {
  511     const char *cp = h->microdesc_hash_line;
  512     size_t num_len;
  513     /* cp looks like \d+(,\d+)* (digesttype=val )+ .  Let's hunt for mstr in
  514      * the first part. */
  515     while (1) {
  516       num_len = strspn(cp, "1234567890");
  517       if (num_len == mlen && fast_memeq(mstr, cp, mlen)) {
  518         /* This is the line. */
  519         char buf[BASE64_DIGEST256_LEN+1];
  520         /* XXXX ignores extraneous stuff if the digest is too long.  This
  521          * seems harmless enough, right? */
  522         cp = strstr(cp, dstr);
  523         if (!cp)
  524           return -1;
  525         cp += strlen(dstr);
  526         strlcpy(buf, cp, sizeof(buf));
  527         return digest256_from_base64(digest256_out, buf);
  528       }
  529       if (num_len == 0 || cp[num_len] != ',')
  530         break;
  531       cp += num_len + 1;
  532     }
  533   }
  534   return -1;
  535 }
  536 
  537 /** Given a vote <b>vote</b> (not a consensus!), return its associated
  538  * networkstatus_voter_info_t. */
  539 static networkstatus_voter_info_t *
  540 get_voter(const networkstatus_t *vote)
  541 {
  542   tor_assert(vote);
  543   tor_assert(vote->type == NS_TYPE_VOTE);
  544   tor_assert(vote->voters);
  545   tor_assert(smartlist_len(vote->voters) == 1);
  546   return smartlist_get(vote->voters, 0);
  547 }
  548 
  549 /** Temporary structure used in constructing a list of dir-source entries
  550  * for a consensus.  One of these is generated for every vote, and one more
  551  * for every legacy key in each vote. */
  552 typedef struct dir_src_ent_t {
  553   networkstatus_t *v;
  554   const char *digest;
  555   int is_legacy;
  556 } dir_src_ent_t;
  557 
  558 /** Helper for sorting networkstatus_t votes (not consensuses) by the
  559  * hash of their voters' identity digests. */
  560 static int
  561 compare_votes_by_authority_id_(const void **_a, const void **_b)
  562 {
  563   const networkstatus_t *a = *_a, *b = *_b;
  564   return fast_memcmp(get_voter(a)->identity_digest,
  565                 get_voter(b)->identity_digest, DIGEST_LEN);
  566 }
  567 
  568 /** Helper: Compare the dir_src_ent_ts in *<b>_a</b> and *<b>_b</b> by
  569  * their identity digests, and return -1, 0, or 1 depending on their
  570  * ordering */
  571 static int
  572 compare_dir_src_ents_by_authority_id_(const void **_a, const void **_b)
  573 {
  574   const dir_src_ent_t *a = *_a, *b = *_b;
  575   const networkstatus_voter_info_t *a_v = get_voter(a->v),
  576     *b_v = get_voter(b->v);
  577   const char *a_id, *b_id;
  578   a_id = a->is_legacy ? a_v->legacy_id_digest : a_v->identity_digest;
  579   b_id = b->is_legacy ? b_v->legacy_id_digest : b_v->identity_digest;
  580 
  581   return fast_memcmp(a_id, b_id, DIGEST_LEN);
  582 }
  583 
  584 /** Given a sorted list of strings <b>in</b>, add every member to <b>out</b>
  585  * that occurs more than <b>min</b> times. */
  586 static void
  587 get_frequent_members(smartlist_t *out, smartlist_t *in, int min)
  588 {
  589   char *cur = NULL;
  590   int count = 0;
  591   SMARTLIST_FOREACH_BEGIN(in, char *, cp) {
  592     if (cur && !strcmp(cp, cur)) {
  593       ++count;
  594     } else {
  595       if (count > min)
  596         smartlist_add(out, cur);
  597       cur = cp;
  598       count = 1;
  599     }
  600   } SMARTLIST_FOREACH_END(cp);
  601   if (count > min)
  602     smartlist_add(out, cur);
  603 }
  604 
  605 /** Given a sorted list of strings <b>lst</b>, return the member that appears
  606  * most.  Break ties in favor of later-occurring members. */
  607 #define get_most_frequent_member(lst)           \
  608   smartlist_get_most_frequent_string(lst)
  609 
  610 /** Return 0 if and only if <b>a</b> and <b>b</b> are routerstatuses
  611  * that come from the same routerinfo, with the same derived elements.
  612  */
  613 static int
  614 compare_vote_rs(const vote_routerstatus_t *a, const vote_routerstatus_t *b)
  615 {
  616   int r;
  617   tor_assert(a);
  618   tor_assert(b);
  619 
  620   if ((r = fast_memcmp(a->status.identity_digest, b->status.identity_digest,
  621                   DIGEST_LEN)))
  622     return r;
  623   if ((r = fast_memcmp(a->status.descriptor_digest,
  624                        b->status.descriptor_digest,
  625                        DIGEST_LEN)))
  626     return r;
  627   /* If we actually reached this point, then the identities and
  628    * the descriptor digests matched, so somebody is making SHA1 collisions.
  629    */
  630 #define CMP_FIELD(utype, itype, field) do {                             \
  631     utype aval = (utype) (itype) a->status.field;                       \
  632     utype bval = (utype) (itype) b->status.field;                       \
  633     utype u = bval - aval;                                              \
  634     itype r2 = (itype) u;                                               \
  635     if (r2 < 0) {                                                       \
  636       return -1;                                                        \
  637     } else if (r2 > 0) {                                                \
  638       return 1;                                                         \
  639     }                                                                   \
  640   } while (0)
  641 
  642   CMP_FIELD(uint64_t, int64_t, published_on);
  643 
  644   if ((r = strcmp(b->status.nickname, a->status.nickname)))
  645     return r;
  646 
  647   CMP_FIELD(unsigned, int, addr);
  648   CMP_FIELD(unsigned, int, or_port);
  649   CMP_FIELD(unsigned, int, dir_port);
  650 
  651   return 0;
  652 }
  653 
  654 /** Helper for sorting routerlists based on compare_vote_rs. */
  655 static int
  656 compare_vote_rs_(const void **_a, const void **_b)
  657 {
  658   const vote_routerstatus_t *a = *_a, *b = *_b;
  659   return compare_vote_rs(a,b);
  660 }
  661 
  662 /** Helper for sorting OR ports. */
  663 static int
  664 compare_orports_(const void **_a, const void **_b)
  665 {
  666   const tor_addr_port_t *a = *_a, *b = *_b;
  667   int r;
  668 
  669   if ((r = tor_addr_compare(&a->addr, &b->addr, CMP_EXACT)))
  670     return r;
  671   if ((r = (((int) b->port) - ((int) a->port))))
  672     return r;
  673 
  674   return 0;
  675 }
  676 
  677 /** Given a list of vote_routerstatus_t, all for the same router identity,
  678  * return whichever is most frequent, breaking ties in favor of more
  679  * recently published vote_routerstatus_t and in case of ties there,
  680  * in favor of smaller descriptor digest.
  681  */
  682 static vote_routerstatus_t *
  683 compute_routerstatus_consensus(smartlist_t *votes, int consensus_method,
  684                                char *microdesc_digest256_out,
  685                                tor_addr_port_t *best_alt_orport_out)
  686 {
  687   vote_routerstatus_t *most = NULL, *cur = NULL;
  688   int most_n = 0, cur_n = 0;
  689   time_t most_published = 0;
  690 
  691   /* compare_vote_rs_() sorts the items by identity digest (all the same),
  692    * then by SD digest.  That way, if we have a tie that the published_on
  693    * date cannot break, we use the descriptor with the smaller digest.
  694    */
  695   smartlist_sort(votes, compare_vote_rs_);
  696   SMARTLIST_FOREACH_BEGIN(votes, vote_routerstatus_t *, rs) {
  697     if (cur && !compare_vote_rs(cur, rs)) {
  698       ++cur_n;
  699     } else {
  700       if (cur && (cur_n > most_n ||
  701                   (cur_n == most_n &&
  702                    cur->status.published_on > most_published))) {
  703         most = cur;
  704         most_n = cur_n;
  705         most_published = cur->status.published_on;
  706       }
  707       cur_n = 1;
  708       cur = rs;
  709     }
  710   } SMARTLIST_FOREACH_END(rs);
  711 
  712   if (cur_n > most_n ||
  713       (cur && cur_n == most_n && cur->status.published_on > most_published)) {
  714     most = cur;
  715     // most_n = cur_n; // unused after this point.
  716     // most_published = cur->status.published_on; // unused after this point.
  717   }
  718 
  719   tor_assert(most);
  720 
  721   /* Vote on potential alternative (sets of) OR port(s) in the winning
  722    * routerstatuses.
  723    *
  724    * XXX prop186 There's at most one alternative OR port (_the_ IPv6
  725    * port) for now. */
  726   if (best_alt_orport_out) {
  727     smartlist_t *alt_orports = smartlist_new();
  728     const tor_addr_port_t *most_alt_orport = NULL;
  729 
  730     SMARTLIST_FOREACH_BEGIN(votes, vote_routerstatus_t *, rs) {
  731       tor_assert(rs);
  732       if (compare_vote_rs(most, rs) == 0 &&
  733           !tor_addr_is_null(&rs->status.ipv6_addr)
  734           && rs->status.ipv6_orport) {
  735         smartlist_add(alt_orports, tor_addr_port_new(&rs->status.ipv6_addr,
  736                                                      rs->status.ipv6_orport));
  737       }
  738     } SMARTLIST_FOREACH_END(rs);
  739 
  740     smartlist_sort(alt_orports, compare_orports_);
  741     most_alt_orport = smartlist_get_most_frequent(alt_orports,
  742                                                   compare_orports_);
  743     if (most_alt_orport) {
  744       memcpy(best_alt_orport_out, most_alt_orport, sizeof(tor_addr_port_t));
  745       log_debug(LD_DIR, "\"a\" line winner for %s is %s",
  746                 most->status.nickname,
  747                 fmt_addrport(&most_alt_orport->addr, most_alt_orport->port));
  748     }
  749 
  750     SMARTLIST_FOREACH(alt_orports, tor_addr_port_t *, ap, tor_free(ap));
  751     smartlist_free(alt_orports);
  752   }
  753 
  754   if (microdesc_digest256_out) {
  755     smartlist_t *digests = smartlist_new();
  756     const uint8_t *best_microdesc_digest;
  757     SMARTLIST_FOREACH_BEGIN(votes, vote_routerstatus_t *, rs) {
  758         char d[DIGEST256_LEN];
  759         if (compare_vote_rs(rs, most))
  760           continue;
  761         if (!vote_routerstatus_find_microdesc_hash(d, rs, consensus_method,
  762                                                    DIGEST_SHA256))
  763           smartlist_add(digests, tor_memdup(d, sizeof(d)));
  764     } SMARTLIST_FOREACH_END(rs);
  765     smartlist_sort_digests256(digests);
  766     best_microdesc_digest = smartlist_get_most_frequent_digest256(digests);
  767     if (best_microdesc_digest)
  768       memcpy(microdesc_digest256_out, best_microdesc_digest, DIGEST256_LEN);
  769     SMARTLIST_FOREACH(digests, char *, cp, tor_free(cp));
  770     smartlist_free(digests);
  771   }
  772 
  773   return most;
  774 }
  775 
  776 /** Sorting helper: compare two strings based on their values as base-ten
  777  * positive integers. (Non-integers are treated as prior to all integers, and
  778  * compared lexically.) */
  779 static int
  780 cmp_int_strings_(const void **_a, const void **_b)
  781 {
  782   const char *a = *_a, *b = *_b;
  783   int ai = (int)tor_parse_long(a, 10, 1, INT_MAX, NULL, NULL);
  784   int bi = (int)tor_parse_long(b, 10, 1, INT_MAX, NULL, NULL);
  785   if (ai<bi) {
  786     return -1;
  787   } else if (ai==bi) {
  788     if (ai == 0) /* Parsing failed. */
  789       return strcmp(a, b);
  790     return 0;
  791   } else {
  792     return 1;
  793   }
  794 }
  795 
  796 /** Given a list of networkstatus_t votes, determine and return the number of
  797  * the highest consensus method that is supported by 2/3 of the voters. */
  798 static int
  799 compute_consensus_method(smartlist_t *votes)
  800 {
  801   smartlist_t *all_methods = smartlist_new();
  802   smartlist_t *acceptable_methods = smartlist_new();
  803   smartlist_t *tmp = smartlist_new();
  804   int min = (smartlist_len(votes) * 2) / 3;
  805   int n_ok;
  806   int result;
  807   SMARTLIST_FOREACH(votes, networkstatus_t *, vote,
  808   {
  809     tor_assert(vote->supported_methods);
  810     smartlist_add_all(tmp, vote->supported_methods);
  811     smartlist_sort(tmp, cmp_int_strings_);
  812     smartlist_uniq(tmp, cmp_int_strings_, NULL);
  813     smartlist_add_all(all_methods, tmp);
  814     smartlist_clear(tmp);
  815   });
  816 
  817   smartlist_sort(all_methods, cmp_int_strings_);
  818   get_frequent_members(acceptable_methods, all_methods, min);
  819   n_ok = smartlist_len(acceptable_methods);
  820   if (n_ok) {
  821     const char *best = smartlist_get(acceptable_methods, n_ok-1);
  822     result = (int)tor_parse_long(best, 10, 1, INT_MAX, NULL, NULL);
  823   } else {
  824     result = 1;
  825   }
  826   smartlist_free(tmp);
  827   smartlist_free(all_methods);
  828   smartlist_free(acceptable_methods);
  829   return result;
  830 }
  831 
  832 /** Return true iff <b>method</b> is a consensus method that we support. */
  833 static int
  834 consensus_method_is_supported(int method)
  835 {
  836   return (method >= MIN_SUPPORTED_CONSENSUS_METHOD) &&
  837     (method <= MAX_SUPPORTED_CONSENSUS_METHOD);
  838 }
  839 
  840 /** Return a newly allocated string holding the numbers between low and high
  841  * (inclusive) that are supported consensus methods. */
  842 STATIC char *
  843 make_consensus_method_list(int low, int high, const char *separator)
  844 {
  845   char *list;
  846 
  847   int i;
  848   smartlist_t *lst;
  849   lst = smartlist_new();
  850   for (i = low; i <= high; ++i) {
  851     if (!consensus_method_is_supported(i))
  852       continue;
  853     smartlist_add_asprintf(lst, "%d", i);
  854   }
  855   list = smartlist_join_strings(lst, separator, 0, NULL);
  856   tor_assert(list);
  857   SMARTLIST_FOREACH(lst, char *, cp, tor_free(cp));
  858   smartlist_free(lst);
  859   return list;
  860 }
  861 
  862 /** Helper: given <b>lst</b>, a list of version strings such that every
  863  * version appears once for every versioning voter who recommends it, return a
  864  * newly allocated string holding the resulting client-versions or
  865  * server-versions list. May change contents of <b>lst</b> */
  866 static char *
  867 compute_consensus_versions_list(smartlist_t *lst, int n_versioning)
  868 {
  869   int min = n_versioning / 2;
  870   smartlist_t *good = smartlist_new();
  871   char *result;
  872   SMARTLIST_FOREACH_BEGIN(lst, const char *, v) {
  873     if (strchr(v, ' ')) {
  874       log_warn(LD_DIR, "At least one authority has voted for a version %s "
  875                "that contains a space. This probably wasn't intentional, and "
  876                "is likely to cause trouble. Please tell them to stop it.",
  877                escaped(v));
  878     }
  879   } SMARTLIST_FOREACH_END(v);
  880   sort_version_list(lst, 0);
  881   get_frequent_members(good, lst, min);
  882   result = smartlist_join_strings(good, ",", 0, NULL);
  883   smartlist_free(good);
  884   return result;
  885 }
  886 
  887 /** Given a list of K=V values, return the int32_t value corresponding to
  888  * KEYWORD=, or default_val if no such value exists, or if the value is
  889  * corrupt.
  890  */
  891 STATIC int32_t
  892 dirvote_get_intermediate_param_value(const smartlist_t *param_list,
  893                                      const char *keyword,
  894                                      int32_t default_val)
  895 {
  896   unsigned int n_found = 0;
  897   int32_t value = default_val;
  898 
  899   SMARTLIST_FOREACH_BEGIN(param_list, const char *, k_v_pair) {
  900     if (!strcmpstart(k_v_pair, keyword) && k_v_pair[strlen(keyword)] == '=') {
  901       const char *integer_str = &k_v_pair[strlen(keyword)+1];
  902       int ok;
  903       value = (int32_t)
  904         tor_parse_long(integer_str, 10, INT32_MIN, INT32_MAX, &ok, NULL);
  905       if (BUG(! ok))
  906         return default_val;
  907       ++n_found;
  908     }
  909   } SMARTLIST_FOREACH_END(k_v_pair);
  910 
  911   if (n_found == 1) {
  912     return value;
  913   } else {
  914     tor_assert_nonfatal(n_found == 0);
  915     return default_val;
  916   }
  917 }
  918 
  919 /** Minimum number of directory authorities voting for a parameter to
  920  * include it in the consensus, if consensus method 12 or later is to be
  921  * used. See proposal 178 for details. */
  922 #define MIN_VOTES_FOR_PARAM 3
  923 
  924 /** Helper: given a list of valid networkstatus_t, return a new smartlist
  925  * containing the contents of the consensus network parameter set.
  926  */
  927 STATIC smartlist_t *
  928 dirvote_compute_params(smartlist_t *votes, int method, int total_authorities)
  929 {
  930   int i;
  931   int32_t *vals;
  932 
  933   int cur_param_len;
  934   const char *cur_param;
  935   const char *eq;
  936 
  937   const int n_votes = smartlist_len(votes);
  938   smartlist_t *output;
  939   smartlist_t *param_list = smartlist_new();
  940   (void) method;
  941 
  942   /* We require that the parameter lists in the votes are well-formed: that
  943      is, that their keywords are unique and sorted, and that their values are
  944      between INT32_MIN and INT32_MAX inclusive.  This should be guaranteed by
  945      the parsing code. */
  946 
  947   vals = tor_calloc(n_votes, sizeof(int));
  948 
  949   SMARTLIST_FOREACH_BEGIN(votes, networkstatus_t *, v) {
  950     if (!v->net_params)
  951       continue;
  952     smartlist_add_all(param_list, v->net_params);
  953   } SMARTLIST_FOREACH_END(v);
  954 
  955   if (smartlist_len(param_list) == 0) {
  956     tor_free(vals);
  957     return param_list;
  958   }
  959 
  960   smartlist_sort_strings(param_list);
  961   i = 0;
  962   cur_param = smartlist_get(param_list, 0);
  963   eq = strchr(cur_param, '=');
  964   tor_assert(eq);
  965   cur_param_len = (int)(eq+1 - cur_param);
  966 
  967   output = smartlist_new();
  968 
  969   SMARTLIST_FOREACH_BEGIN(param_list, const char *, param) {
  970     /* resolve spurious clang shallow analysis null pointer errors */
  971     tor_assert(param);
  972 
  973     const char *next_param;
  974     int ok=0;
  975     eq = strchr(param, '=');
  976     tor_assert(i<n_votes); /* Make sure we prevented vote-stuffing. */
  977     vals[i++] = (int32_t)
  978       tor_parse_long(eq+1, 10, INT32_MIN, INT32_MAX, &ok, NULL);
  979     tor_assert(ok); /* Already checked these when parsing. */
  980 
  981     if (param_sl_idx+1 == smartlist_len(param_list))
  982       next_param = NULL;
  983     else
  984       next_param = smartlist_get(param_list, param_sl_idx+1);
  985 
  986     if (!next_param || strncmp(next_param, param, cur_param_len)) {
  987       /* We've reached the end of a series. */
  988       /* Make sure enough authorities voted on this param, unless the
  989        * the consensus method we use is too old for that. */
  990       if (i > total_authorities/2 ||
  991           i >= MIN_VOTES_FOR_PARAM) {
  992         int32_t median = median_int32(vals, i);
  993         char *out_string = tor_malloc(64+cur_param_len);
  994         memcpy(out_string, param, cur_param_len);
  995         tor_snprintf(out_string+cur_param_len,64, "%ld", (long)median);
  996         smartlist_add(output, out_string);
  997       }
  998 
  999       i = 0;
 1000       if (next_param) {
 1001         eq = strchr(next_param, '=');
 1002         cur_param_len = (int)(eq+1 - next_param);
 1003       }
 1004     }
 1005   } SMARTLIST_FOREACH_END(param);
 1006 
 1007   smartlist_free(param_list);
 1008   tor_free(vals);
 1009   return output;
 1010 }
 1011 
 1012 #define RANGE_CHECK(a,b,c,d,e,f,g,mx) \
 1013        ((a) >= 0 && (a) <= (mx) && (b) >= 0 && (b) <= (mx) && \
 1014         (c) >= 0 && (c) <= (mx) && (d) >= 0 && (d) <= (mx) && \
 1015         (e) >= 0 && (e) <= (mx) && (f) >= 0 && (f) <= (mx) && \
 1016         (g) >= 0 && (g) <= (mx))
 1017 
 1018 #define CHECK_EQ(a, b, margin) \
 1019      ((a)-(b) >= 0 ? (a)-(b) <= (margin) : (b)-(a) <= (margin))
 1020 
 1021 typedef enum {
 1022  BW_WEIGHTS_NO_ERROR = 0,
 1023  BW_WEIGHTS_RANGE_ERROR = 1,
 1024  BW_WEIGHTS_SUMG_ERROR = 2,
 1025  BW_WEIGHTS_SUME_ERROR = 3,
 1026  BW_WEIGHTS_SUMD_ERROR = 4,
 1027  BW_WEIGHTS_BALANCE_MID_ERROR = 5,
 1028  BW_WEIGHTS_BALANCE_EG_ERROR = 6
 1029 } bw_weights_error_t;
 1030 
 1031 /**
 1032  * Verify that any weightings satisfy the balanced formulas.
 1033  */
 1034 static bw_weights_error_t
 1035 networkstatus_check_weights(int64_t Wgg, int64_t Wgd, int64_t Wmg,
 1036                             int64_t Wme, int64_t Wmd, int64_t Wee,
 1037                             int64_t Wed, int64_t scale, int64_t G,
 1038                             int64_t M, int64_t E, int64_t D, int64_t T,
 1039                             int64_t margin, int do_balance) {
 1040   bw_weights_error_t berr = BW_WEIGHTS_NO_ERROR;
 1041 
 1042   // Wed + Wmd + Wgd == 1
 1043   if (!CHECK_EQ(Wed + Wmd + Wgd, scale, margin)) {
 1044     berr = BW_WEIGHTS_SUMD_ERROR;
 1045     goto out;
 1046   }
 1047 
 1048   // Wmg + Wgg == 1
 1049   if (!CHECK_EQ(Wmg + Wgg, scale, margin)) {
 1050     berr = BW_WEIGHTS_SUMG_ERROR;
 1051     goto out;
 1052   }
 1053 
 1054   // Wme + Wee == 1
 1055   if (!CHECK_EQ(Wme + Wee, scale, margin)) {
 1056     berr = BW_WEIGHTS_SUME_ERROR;
 1057     goto out;
 1058   }
 1059 
 1060   // Verify weights within range 0->1
 1061   if (!RANGE_CHECK(Wgg, Wgd, Wmg, Wme, Wmd, Wed, Wee, scale)) {
 1062     berr = BW_WEIGHTS_RANGE_ERROR;
 1063     goto out;
 1064   }
 1065 
 1066   if (do_balance) {
 1067     // Wgg*G + Wgd*D == Wee*E + Wed*D, already scaled
 1068     if (!CHECK_EQ(Wgg*G + Wgd*D, Wee*E + Wed*D, (margin*T)/3)) {
 1069       berr = BW_WEIGHTS_BALANCE_EG_ERROR;
 1070       goto out;
 1071     }
 1072 
 1073     // Wgg*G + Wgd*D == M*scale + Wmd*D + Wme*E + Wmg*G, already scaled
 1074     if (!CHECK_EQ(Wgg*G + Wgd*D, M*scale + Wmd*D + Wme*E + Wmg*G,
 1075                 (margin*T)/3)) {
 1076       berr = BW_WEIGHTS_BALANCE_MID_ERROR;
 1077       goto out;
 1078     }
 1079   }
 1080 
 1081  out:
 1082   if (berr) {
 1083     log_info(LD_DIR,
 1084              "Bw weight mismatch %d. G=%"PRId64" M=%"PRId64
 1085              " E=%"PRId64" D=%"PRId64" T=%"PRId64
 1086              " Wmd=%d Wme=%d Wmg=%d Wed=%d Wee=%d"
 1087              " Wgd=%d Wgg=%d Wme=%d Wmg=%d",
 1088              berr,
 1089              (G), (M), (E),
 1090              (D), (T),
 1091              (int)Wmd, (int)Wme, (int)Wmg, (int)Wed, (int)Wee,
 1092              (int)Wgd, (int)Wgg, (int)Wme, (int)Wmg);
 1093   }
 1094 
 1095   return berr;
 1096 }
 1097 
 1098 /**
 1099  * This function computes the bandwidth weights for consensus method 10.
 1100  *
 1101  * It returns true if weights could be computed, false otherwise.
 1102  */
 1103 int
 1104 networkstatus_compute_bw_weights_v10(smartlist_t *chunks, int64_t G,
 1105                                      int64_t M, int64_t E, int64_t D,
 1106                                      int64_t T, int64_t weight_scale)
 1107 {
 1108   bw_weights_error_t berr = 0;
 1109   int64_t Wgg = -1, Wgd = -1;
 1110   int64_t Wmg = -1, Wme = -1, Wmd = -1;
 1111   int64_t Wed = -1, Wee = -1;
 1112   const char *casename;
 1113 
 1114   if (G <= 0 || M <= 0 || E <= 0 || D <= 0) {
 1115     log_warn(LD_DIR, "Consensus with empty bandwidth: "
 1116                      "G=%"PRId64" M=%"PRId64" E=%"PRId64
 1117                      " D=%"PRId64" T=%"PRId64,
 1118              (G), (M), (E),
 1119              (D), (T));
 1120     return 0;
 1121   }
 1122 
 1123   /*
 1124    * Computed from cases in 3.8.3 of dir-spec.txt
 1125    *
 1126    * 1. Neither are scarce
 1127    * 2. Both Guard and Exit are scarce
 1128    *    a. R+D <= S
 1129    *    b. R+D > S
 1130    * 3. One of Guard or Exit is scarce
 1131    *    a. S+D < T/3
 1132    *    b. S+D >= T/3
 1133    */
 1134   if (3*E >= T && 3*G >= T) { // E >= T/3 && G >= T/3
 1135     /* Case 1: Neither are scarce.  */
 1136     casename = "Case 1 (Wgd=Wmd=Wed)";
 1137     Wgd = weight_scale/3;
 1138     Wed = weight_scale/3;
 1139     Wmd = weight_scale/3;
 1140     Wee = (weight_scale*(E+G+M))/(3*E);
 1141     Wme = weight_scale - Wee;
 1142     Wmg = (weight_scale*(2*G-E-M))/(3*G);
 1143     Wgg = weight_scale - Wmg;
 1144 
 1145     berr = networkstatus_check_weights(Wgg, Wgd, Wmg, Wme, Wmd, Wee, Wed,
 1146                                        weight_scale, G, M, E, D, T, 10, 1);
 1147 
 1148     if (berr) {
 1149       log_warn(LD_DIR,
 1150              "Bw Weights error %d for %s v10. G=%"PRId64" M=%"PRId64
 1151              " E=%"PRId64" D=%"PRId64" T=%"PRId64
 1152              " Wmd=%d Wme=%d Wmg=%d Wed=%d Wee=%d"
 1153              " Wgd=%d Wgg=%d Wme=%d Wmg=%d weight_scale=%d",
 1154              berr, casename,
 1155              (G), (M), (E),
 1156              (D), (T),
 1157              (int)Wmd, (int)Wme, (int)Wmg, (int)Wed, (int)Wee,
 1158              (int)Wgd, (int)Wgg, (int)Wme, (int)Wmg, (int)weight_scale);
 1159       return 0;
 1160     }
 1161   } else if (3*E < T && 3*G < T) { // E < T/3 && G < T/3
 1162     int64_t R = MIN(E, G);
 1163     int64_t S = MAX(E, G);
 1164     /*
 1165      * Case 2: Both Guards and Exits are scarce
 1166      * Balance D between E and G, depending upon
 1167      * D capacity and scarcity.
 1168      */
 1169     if (R+D < S) { // Subcase a
 1170       Wgg = weight_scale;
 1171       Wee = weight_scale;
 1172       Wmg = 0;
 1173       Wme = 0;
 1174       Wmd = 0;
 1175       if (E < G) {
 1176         casename = "Case 2a (E scarce)";
 1177         Wed = weight_scale;
 1178         Wgd = 0;
 1179       } else { /* E >= G */
 1180         casename = "Case 2a (G scarce)";
 1181         Wed = 0;
 1182         Wgd = weight_scale;
 1183       }
 1184     } else { // Subcase b: R+D >= S
 1185       casename = "Case 2b1 (Wgg=weight_scale, Wmd=Wgd)";
 1186       Wee = (weight_scale*(E - G + M))/E;
 1187       Wed = (weight_scale*(D - 2*E + 4*G - 2*M))/(3*D);
 1188       Wme = (weight_scale*(G-M))/E;
 1189       Wmg = 0;
 1190       Wgg = weight_scale;
 1191       Wmd = (weight_scale - Wed)/2;
 1192       Wgd = (weight_scale - Wed)/2;
 1193 
 1194       berr = networkstatus_check_weights(Wgg, Wgd, Wmg, Wme, Wmd, Wee, Wed,
 1195                                        weight_scale, G, M, E, D, T, 10, 1);
 1196 
 1197       if (berr) {
 1198         casename = "Case 2b2 (Wgg=weight_scale, Wee=weight_scale)";
 1199         Wgg = weight_scale;
 1200         Wee = weight_scale;
 1201         Wed = (weight_scale*(D - 2*E + G + M))/(3*D);
 1202         Wmd = (weight_scale*(D - 2*M + G + E))/(3*D);
 1203         Wme = 0;
 1204         Wmg = 0;
 1205 
 1206         if (Wmd < 0) { // Can happen if M > T/3
 1207           casename = "Case 2b3 (Wmd=0)";
 1208           Wmd = 0;
 1209           log_warn(LD_DIR,
 1210                    "Too much Middle bandwidth on the network to calculate "
 1211                    "balanced bandwidth-weights. Consider increasing the "
 1212                    "number of Guard nodes by lowering the requirements.");
 1213         }
 1214         Wgd = weight_scale - Wed - Wmd;
 1215         berr = networkstatus_check_weights(Wgg, Wgd, Wmg, Wme, Wmd, Wee,
 1216                   Wed, weight_scale, G, M, E, D, T, 10, 1);
 1217       }
 1218       if (berr != BW_WEIGHTS_NO_ERROR &&
 1219               berr != BW_WEIGHTS_BALANCE_MID_ERROR) {
 1220         log_warn(LD_DIR,
 1221              "Bw Weights error %d for %s v10. G=%"PRId64" M=%"PRId64
 1222              " E=%"PRId64" D=%"PRId64" T=%"PRId64
 1223              " Wmd=%d Wme=%d Wmg=%d Wed=%d Wee=%d"
 1224              " Wgd=%d Wgg=%d Wme=%d Wmg=%d weight_scale=%d",
 1225              berr, casename,
 1226              (G), (M), (E),
 1227              (D), (T),
 1228              (int)Wmd, (int)Wme, (int)Wmg, (int)Wed, (int)Wee,
 1229              (int)Wgd, (int)Wgg, (int)Wme, (int)Wmg, (int)weight_scale);
 1230         return 0;
 1231       }
 1232     }
 1233   } else { // if (E < T/3 || G < T/3) {
 1234     int64_t S = MIN(E, G);
 1235     // Case 3: Exactly one of Guard or Exit is scarce
 1236     if (!(3*E < T || 3*G < T) || !(3*G >= T || 3*E >= T)) {
 1237       log_warn(LD_BUG,
 1238            "Bw-Weights Case 3 v10 but with G=%"PRId64" M="
 1239            "%"PRId64" E=%"PRId64" D=%"PRId64" T=%"PRId64,
 1240                (G), (M), (E),
 1241                (D), (T));
 1242     }
 1243 
 1244     if (3*(S+D) < T) { // Subcase a: S+D < T/3
 1245       if (G < E) {
 1246         casename = "Case 3a (G scarce)";
 1247         Wgg = Wgd = weight_scale;
 1248         Wmd = Wed = Wmg = 0;
 1249         // Minor subcase, if E is more scarce than M,
 1250         // keep its bandwidth in place.
 1251         if (E < M) Wme = 0;
 1252         else Wme = (weight_scale*(E-M))/(2*E);
 1253         Wee = weight_scale-Wme;
 1254       } else { // G >= E
 1255         casename = "Case 3a (E scarce)";
 1256         Wee = Wed = weight_scale;
 1257         Wmd = Wgd = Wme = 0;
 1258         // Minor subcase, if G is more scarce than M,
 1259         // keep its bandwidth in place.
 1260         if (G < M) Wmg = 0;
 1261         else Wmg = (weight_scale*(G-M))/(2*G);
 1262         Wgg = weight_scale-Wmg;
 1263       }
 1264     } else { // Subcase b: S+D >= T/3
 1265       // D != 0 because S+D >= T/3
 1266       if (G < E) {
 1267         casename = "Case 3bg (G scarce, Wgg=weight_scale, Wmd == Wed)";
 1268         Wgg = weight_scale;
 1269         Wgd = (weight_scale*(D - 2*G + E + M))/(3*D);
 1270         Wmg = 0;
 1271         Wee = (weight_scale*(E+M))/(2*E);
 1272         Wme = weight_scale - Wee;
 1273         Wmd = (weight_scale - Wgd)/2;
 1274         Wed = (weight_scale - Wgd)/2;
 1275 
 1276         berr = networkstatus_check_weights(Wgg, Wgd, Wmg, Wme, Wmd, Wee,
 1277                     Wed, weight_scale, G, M, E, D, T, 10, 1);
 1278       } else { // G >= E
 1279         casename = "Case 3be (E scarce, Wee=weight_scale, Wmd == Wgd)";
 1280         Wee = weight_scale;
 1281         Wed = (weight_scale*(D - 2*E + G + M))/(3*D);
 1282         Wme = 0;
 1283         Wgg = (weight_scale*(G+M))/(2*G);
 1284         Wmg = weight_scale - Wgg;
 1285         Wmd = (weight_scale - Wed)/2;
 1286         Wgd = (weight_scale - Wed)/2;
 1287 
 1288         berr = networkstatus_check_weights(Wgg, Wgd, Wmg, Wme, Wmd, Wee,
 1289                       Wed, weight_scale, G, M, E, D, T, 10, 1);
 1290       }
 1291       if (berr) {
 1292         log_warn(LD_DIR,
 1293              "Bw Weights error %d for %s v10. G=%"PRId64" M=%"PRId64
 1294              " E=%"PRId64" D=%"PRId64" T=%"PRId64
 1295              " Wmd=%d Wme=%d Wmg=%d Wed=%d Wee=%d"
 1296              " Wgd=%d Wgg=%d Wme=%d Wmg=%d weight_scale=%d",
 1297              berr, casename,
 1298              (G), (M), (E),
 1299              (D), (T),
 1300              (int)Wmd, (int)Wme, (int)Wmg, (int)Wed, (int)Wee,
 1301              (int)Wgd, (int)Wgg, (int)Wme, (int)Wmg, (int)weight_scale);
 1302         return 0;
 1303       }
 1304     }
 1305   }
 1306 
 1307   /* We cast down the weights to 32 bit ints on the assumption that
 1308    * weight_scale is ~= 10000. We need to ensure a rogue authority
 1309    * doesn't break this assumption to rig our weights */
 1310   tor_assert(0 < weight_scale && weight_scale <= INT32_MAX);
 1311 
 1312   /*
 1313    * Provide Wgm=Wgg, Wmm=weight_scale, Wem=Wee, Weg=Wed. May later determine
 1314    * that middle nodes need different bandwidth weights for dirport traffic,
 1315    * or that weird exit policies need special weight, or that bridges
 1316    * need special weight.
 1317    *
 1318    * NOTE: This list is sorted.
 1319    */
 1320   smartlist_add_asprintf(chunks,
 1321      "bandwidth-weights Wbd=%d Wbe=%d Wbg=%d Wbm=%d "
 1322      "Wdb=%d "
 1323      "Web=%d Wed=%d Wee=%d Weg=%d Wem=%d "
 1324      "Wgb=%d Wgd=%d Wgg=%d Wgm=%d "
 1325      "Wmb=%d Wmd=%d Wme=%d Wmg=%d Wmm=%d\n",
 1326      (int)Wmd, (int)Wme, (int)Wmg, (int)weight_scale,
 1327      (int)weight_scale,
 1328      (int)weight_scale, (int)Wed, (int)Wee, (int)Wed, (int)Wee,
 1329      (int)weight_scale, (int)Wgd, (int)Wgg, (int)Wgg,
 1330      (int)weight_scale, (int)Wmd, (int)Wme, (int)Wmg, (int)weight_scale);
 1331 
 1332   log_notice(LD_CIRC, "Computed bandwidth weights for %s with v10: "
 1333              "G=%"PRId64" M=%"PRId64" E=%"PRId64" D=%"PRId64
 1334              " T=%"PRId64,
 1335              casename,
 1336              (G), (M), (E),
 1337              (D), (T));
 1338   return 1;
 1339 }
 1340 
 1341 /** Update total bandwidth weights (G/M/E/D/T) with the bandwidth of
 1342  *  the router in <b>rs</b>. */
 1343 static void
 1344 update_total_bandwidth_weights(const routerstatus_t *rs,
 1345                                int is_exit, int is_guard,
 1346                                int64_t *G, int64_t *M, int64_t *E, int64_t *D,
 1347                                int64_t *T)
 1348 {
 1349   int default_bandwidth = rs->bandwidth_kb;
 1350   int guardfraction_bandwidth = 0;
 1351 
 1352   if (!rs->has_bandwidth) {
 1353     log_info(LD_BUG, "Missing consensus bandwidth for router %s",
 1354              rs->nickname);
 1355     return;
 1356   }
 1357 
 1358   /* If this routerstatus represents a guard that we have
 1359    * guardfraction information on, use it to calculate its actual
 1360    * bandwidth. From proposal236:
 1361    *
 1362    *    Similarly, when calculating the bandwidth-weights line as in
 1363    *    section 3.8.3 of dir-spec.txt, directory authorities should treat N
 1364    *    as if fraction F of its bandwidth has the guard flag and (1-F) does
 1365    *    not.  So when computing the totals G,M,E,D, each relay N with guard
 1366    *    visibility fraction F and bandwidth B should be added as follows:
 1367    *
 1368    *    G' = G + F*B, if N does not have the exit flag
 1369    *    M' = M + (1-F)*B, if N does not have the exit flag
 1370    *
 1371    *    or
 1372    *
 1373    *    D' = D + F*B, if N has the exit flag
 1374    *    E' = E + (1-F)*B, if N has the exit flag
 1375    *
 1376    * In this block of code, we prepare the bandwidth values by setting
 1377    * the default_bandwidth to F*B and guardfraction_bandwidth to (1-F)*B.
 1378    */
 1379   if (rs->has_guardfraction) {
 1380     guardfraction_bandwidth_t guardfraction_bw;
 1381 
 1382     tor_assert(is_guard);
 1383 
 1384     guard_get_guardfraction_bandwidth(&guardfraction_bw,
 1385                                       rs->bandwidth_kb,
 1386                                       rs->guardfraction_percentage);
 1387 
 1388     default_bandwidth = guardfraction_bw.guard_bw;
 1389     guardfraction_bandwidth = guardfraction_bw.non_guard_bw;
 1390   }
 1391 
 1392   /* Now calculate the total bandwidth weights with or without
 1393    * guardfraction. Depending on the flags of the relay, add its
 1394    * bandwidth to the appropriate weight pool. If it's a guard and
 1395    * guardfraction is enabled, add its bandwidth to both pools as
 1396    * indicated by the previous comment.
 1397    */
 1398   *T += default_bandwidth;
 1399   if (is_exit && is_guard) {
 1400 
 1401     *D += default_bandwidth;
 1402     if (rs->has_guardfraction) {
 1403       *E += guardfraction_bandwidth;
 1404     }
 1405 
 1406   } else if (is_exit) {
 1407 
 1408     *E += default_bandwidth;
 1409 
 1410   } else if (is_guard) {
 1411 
 1412     *G += default_bandwidth;
 1413     if (rs->has_guardfraction) {
 1414       *M += guardfraction_bandwidth;
 1415     }
 1416 
 1417   } else {
 1418 
 1419     *M += default_bandwidth;
 1420   }
 1421 }
 1422 
 1423 /** Considering the different recommended/required protocols sets as a
 1424  * 4-element array, return the element from <b>vote</b> for that protocol
 1425  * set.
 1426  */
 1427 static const char *
 1428 get_nth_protocol_set_vote(int n, const networkstatus_t *vote)
 1429 {
 1430   switch (n) {
 1431     case 0: return vote->recommended_client_protocols;
 1432     case 1: return vote->recommended_relay_protocols;
 1433     case 2: return vote->required_client_protocols;
 1434     case 3: return vote->required_relay_protocols;
 1435     default:
 1436       tor_assert_unreached();
 1437       return NULL;
 1438   }
 1439 }
 1440 
 1441 /** Considering the different recommended/required protocols sets as a
 1442  * 4-element array, return a newly allocated string for the consensus value
 1443  * for the n'th set.
 1444  */
 1445 static char *
 1446 compute_nth_protocol_set(int n, int n_voters, const smartlist_t *votes)
 1447 {
 1448   const char *keyword;
 1449   smartlist_t *proto_votes = smartlist_new();
 1450   int threshold;
 1451   switch (n) {
 1452     case 0:
 1453       keyword = "recommended-client-protocols";
 1454       threshold = CEIL_DIV(n_voters, 2);
 1455       break;
 1456     case 1:
 1457       keyword = "recommended-relay-protocols";
 1458       threshold = CEIL_DIV(n_voters, 2);
 1459       break;
 1460     case 2:
 1461       keyword = "required-client-protocols";
 1462       threshold = CEIL_DIV(n_voters * 2, 3);
 1463       break;
 1464     case 3:
 1465       keyword = "required-relay-protocols";
 1466       threshold = CEIL_DIV(n_voters * 2, 3);
 1467       break;
 1468     default:
 1469       tor_assert_unreached();
 1470       return NULL;
 1471   }
 1472 
 1473   SMARTLIST_FOREACH_BEGIN(votes, const networkstatus_t *, ns) {
 1474     const char *v = get_nth_protocol_set_vote(n, ns);
 1475     if (v)
 1476       smartlist_add(proto_votes, (void*)v);
 1477   } SMARTLIST_FOREACH_END(ns);
 1478 
 1479   char *protocols = protover_compute_vote(proto_votes, threshold);
 1480   smartlist_free(proto_votes);
 1481 
 1482   char *result = NULL;
 1483   tor_asprintf(&result, "%s %s\n", keyword, protocols);
 1484   tor_free(protocols);
 1485 
 1486   return result;
 1487 }
 1488 
 1489 /** Given a list of vote networkstatus_t in <b>votes</b>, our public
 1490  * authority <b>identity_key</b>, our private authority <b>signing_key</b>,
 1491  * and the number of <b>total_authorities</b> that we believe exist in our
 1492  * voting quorum, generate the text of a new v3 consensus or microdescriptor
 1493  * consensus (depending on <b>flavor</b>), and return the value in a newly
 1494  * allocated string.
 1495  *
 1496  * Note: this function DOES NOT check whether the votes are from
 1497  * recognized authorities.   (dirvote_add_vote does that.)
 1498  *
 1499  * <strong>WATCH OUT</strong>: You need to think before you change the
 1500  * behavior of this function, or of the functions it calls! If some
 1501  * authorities compute the consensus with a different algorithm than
 1502  * others, they will not reach the same result, and they will not all
 1503  * sign the same thing!  If you really need to change the algorithm
 1504  * here, you should allocate a new "consensus_method" for the new
 1505  * behavior, and make the new behavior conditional on a new-enough
 1506  * consensus_method.
 1507  **/
 1508 STATIC char *
 1509 networkstatus_compute_consensus(smartlist_t *votes,
 1510                                 int total_authorities,
 1511                                 crypto_pk_t *identity_key,
 1512                                 crypto_pk_t *signing_key,
 1513                                 const char *legacy_id_key_digest,
 1514                                 crypto_pk_t *legacy_signing_key,
 1515                                 consensus_flavor_t flavor)
 1516 {
 1517   smartlist_t *chunks;
 1518   char *result = NULL;
 1519   int consensus_method;
 1520   time_t valid_after, fresh_until, valid_until;
 1521   int vote_seconds, dist_seconds;
 1522   char *client_versions = NULL, *server_versions = NULL;
 1523   smartlist_t *flags;
 1524   const char *flavor_name;
 1525   uint32_t max_unmeasured_bw_kb = DEFAULT_MAX_UNMEASURED_BW_KB;
 1526   int64_t G, M, E, D, T; /* For bandwidth weights */
 1527   const routerstatus_format_type_t rs_format =
 1528     flavor == FLAV_NS ? NS_V3_CONSENSUS : NS_V3_CONSENSUS_MICRODESC;
 1529   char *params = NULL;
 1530   char *packages = NULL;
 1531   int added_weights = 0;
 1532   dircollator_t *collator = NULL;
 1533   smartlist_t *param_list = NULL;
 1534 
 1535   tor_assert(flavor == FLAV_NS || flavor == FLAV_MICRODESC);
 1536   tor_assert(total_authorities >= smartlist_len(votes));
 1537   tor_assert(total_authorities > 0);
 1538 
 1539   flavor_name = networkstatus_get_flavor_name(flavor);
 1540 
 1541   if (!smartlist_len(votes)) {
 1542     log_warn(LD_DIR, "Can't compute a consensus from no votes.");
 1543     return NULL;
 1544   }
 1545   flags = smartlist_new();
 1546 
 1547   consensus_method = compute_consensus_method(votes);
 1548   if (consensus_method_is_supported(consensus_method)) {
 1549     log_info(LD_DIR, "Generating consensus using method %d.",
 1550              consensus_method);
 1551   } else {
 1552     log_warn(LD_DIR, "The other authorities will use consensus method %d, "
 1553              "which I don't support.  Maybe I should upgrade!",
 1554              consensus_method);
 1555     consensus_method = MAX_SUPPORTED_CONSENSUS_METHOD;
 1556   }
 1557 
 1558   if (consensus_method >= MIN_METHOD_FOR_INIT_BW_WEIGHTS_ONE) {
 1559     /* It's smarter to initialize these weights to 1, so that later on,
 1560      * we can't accidentally divide by zero. */
 1561     G = M = E = D = 1;
 1562     T = 4;
 1563   } else {
 1564     /* ...but originally, they were set to zero. */
 1565     G = M = E = D = T = 0;
 1566   }
 1567 
 1568   /* Compute medians of time-related things, and figure out how many
 1569    * routers we might need to talk about. */
 1570   {
 1571     int n_votes = smartlist_len(votes);
 1572     time_t *va_times = tor_calloc(n_votes, sizeof(time_t));
 1573     time_t *fu_times = tor_calloc(n_votes, sizeof(time_t));
 1574     time_t *vu_times = tor_calloc(n_votes, sizeof(time_t));
 1575     int *votesec_list = tor_calloc(n_votes, sizeof(int));
 1576     int *distsec_list = tor_calloc(n_votes, sizeof(int));
 1577     int n_versioning_clients = 0, n_versioning_servers = 0;
 1578     smartlist_t *combined_client_versions = smartlist_new();
 1579     smartlist_t *combined_server_versions = smartlist_new();
 1580 
 1581     SMARTLIST_FOREACH_BEGIN(votes, networkstatus_t *, v) {
 1582       tor_assert(v->type == NS_TYPE_VOTE);
 1583       va_times[v_sl_idx] = v->valid_after;
 1584       fu_times[v_sl_idx] = v->fresh_until;
 1585       vu_times[v_sl_idx] = v->valid_until;
 1586       votesec_list[v_sl_idx] = v->vote_seconds;
 1587       distsec_list[v_sl_idx] = v->dist_seconds;
 1588       if (v->client_versions) {
 1589         smartlist_t *cv = smartlist_new();
 1590         ++n_versioning_clients;
 1591         smartlist_split_string(cv, v->client_versions, ",",
 1592                                SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
 1593         sort_version_list(cv, 1);
 1594         smartlist_add_all(combined_client_versions, cv);
 1595         smartlist_free(cv); /* elements get freed later. */
 1596       }
 1597       if (v->server_versions) {
 1598         smartlist_t *sv = smartlist_new();
 1599         ++n_versioning_servers;
 1600         smartlist_split_string(sv, v->server_versions, ",",
 1601                                SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
 1602         sort_version_list(sv, 1);
 1603         smartlist_add_all(combined_server_versions, sv);
 1604         smartlist_free(sv); /* elements get freed later. */
 1605       }
 1606       SMARTLIST_FOREACH(v->known_flags, const char *, cp,
 1607                         smartlist_add_strdup(flags, cp));
 1608     } SMARTLIST_FOREACH_END(v);
 1609     valid_after = median_time(va_times, n_votes);
 1610     fresh_until = median_time(fu_times, n_votes);
 1611     valid_until = median_time(vu_times, n_votes);
 1612     vote_seconds = median_int(votesec_list, n_votes);
 1613     dist_seconds = median_int(distsec_list, n_votes);
 1614 
 1615     tor_assert(valid_after +
 1616                (get_options()->TestingTorNetwork ?
 1617                 MIN_VOTE_INTERVAL_TESTING : MIN_VOTE_INTERVAL) <= fresh_until);
 1618     tor_assert(fresh_until +
 1619                (get_options()->TestingTorNetwork ?
 1620                 MIN_VOTE_INTERVAL_TESTING : MIN_VOTE_INTERVAL) <= valid_until);
 1621     tor_assert(vote_seconds >= MIN_VOTE_SECONDS);
 1622     tor_assert(dist_seconds >= MIN_DIST_SECONDS);
 1623 
 1624     server_versions = compute_consensus_versions_list(combined_server_versions,
 1625                                                       n_versioning_servers);
 1626     client_versions = compute_consensus_versions_list(combined_client_versions,
 1627                                                       n_versioning_clients);
 1628     packages = compute_consensus_package_lines(votes);
 1629 
 1630     SMARTLIST_FOREACH(combined_server_versions, char *, cp, tor_free(cp));
 1631     SMARTLIST_FOREACH(combined_client_versions, char *, cp, tor_free(cp));
 1632     smartlist_free(combined_server_versions);
 1633     smartlist_free(combined_client_versions);
 1634 
 1635     smartlist_add_strdup(flags, "NoEdConsensus");
 1636 
 1637     smartlist_sort_strings(flags);
 1638     smartlist_uniq_strings(flags);
 1639 
 1640     tor_free(va_times);
 1641     tor_free(fu_times);
 1642     tor_free(vu_times);
 1643     tor_free(votesec_list);
 1644     tor_free(distsec_list);
 1645   }
 1646 
 1647   chunks = smartlist_new();
 1648 
 1649   {
 1650     char va_buf[ISO_TIME_LEN+1], fu_buf[ISO_TIME_LEN+1],
 1651       vu_buf[ISO_TIME_LEN+1];
 1652     char *flaglist;
 1653     format_iso_time(va_buf, valid_after);
 1654     format_iso_time(fu_buf, fresh_until);
 1655     format_iso_time(vu_buf, valid_until);
 1656     flaglist = smartlist_join_strings(flags, " ", 0, NULL);
 1657 
 1658     smartlist_add_asprintf(chunks, "network-status-version 3%s%s\n"
 1659                  "vote-status consensus\n",
 1660                  flavor == FLAV_NS ? "" : " ",
 1661                  flavor == FLAV_NS ? "" : flavor_name);
 1662 
 1663     smartlist_add_asprintf(chunks, "consensus-method %d\n",
 1664                            consensus_method);
 1665 
 1666     smartlist_add_asprintf(chunks,
 1667                  "valid-after %s\n"
 1668                  "fresh-until %s\n"
 1669                  "valid-until %s\n"
 1670                  "voting-delay %d %d\n"
 1671                  "client-versions %s\n"
 1672                  "server-versions %s\n"
 1673                  "%s" /* packages */
 1674                  "known-flags %s\n",
 1675                  va_buf, fu_buf, vu_buf,
 1676                  vote_seconds, dist_seconds,
 1677                  client_versions, server_versions,
 1678                  packages,
 1679                  flaglist);
 1680 
 1681     tor_free(flaglist);
 1682   }
 1683 
 1684   {
 1685     int num_dirauth = get_n_authorities(V3_DIRINFO);
 1686     int idx;
 1687     for (idx = 0; idx < 4; ++idx) {
 1688       char *proto_line = compute_nth_protocol_set(idx, num_dirauth, votes);
 1689       if (BUG(!proto_line))
 1690         continue;
 1691       smartlist_add(chunks, proto_line);
 1692     }
 1693   }
 1694 
 1695   param_list = dirvote_compute_params(votes, consensus_method,
 1696                                       total_authorities);
 1697   if (smartlist_len(param_list)) {
 1698     params = smartlist_join_strings(param_list, " ", 0, NULL);
 1699     smartlist_add_strdup(chunks, "params ");
 1700     smartlist_add(chunks, params);
 1701     smartlist_add_strdup(chunks, "\n");
 1702   }
 1703 
 1704   {
 1705     int num_dirauth = get_n_authorities(V3_DIRINFO);
 1706     /* Default value of this is 2/3 of the total number of authorities. For
 1707      * instance, if we have 9 dirauth, the default value is 6. The following
 1708      * calculation will round it down. */
 1709     int32_t num_srv_agreements =
 1710       dirvote_get_intermediate_param_value(param_list,
 1711                                            "AuthDirNumSRVAgreements",
 1712                                            (num_dirauth * 2) / 3);
 1713     /* Add the shared random value. */
 1714     char *srv_lines = sr_get_string_for_consensus(votes, num_srv_agreements);
 1715     if (srv_lines != NULL) {
 1716       smartlist_add(chunks, srv_lines);
 1717     }
 1718   }
 1719 
 1720   /* Sort the votes. */
 1721   smartlist_sort(votes, compare_votes_by_authority_id_);
 1722   /* Add the authority sections. */
 1723   {
 1724     smartlist_t *dir_sources = smartlist_new();
 1725     SMARTLIST_FOREACH_BEGIN(votes, networkstatus_t *, v) {
 1726       dir_src_ent_t *e = tor_malloc_zero(sizeof(dir_src_ent_t));
 1727       e->v = v;
 1728       e->digest = get_voter(v)->identity_digest;
 1729       e->is_legacy = 0;
 1730       smartlist_add(dir_sources, e);
 1731       if (!tor_digest_is_zero(get_voter(v)->legacy_id_digest)) {
 1732         dir_src_ent_t *e_legacy = tor_malloc_zero(sizeof(dir_src_ent_t));
 1733         e_legacy->v = v;
 1734         e_legacy->digest = get_voter(v)->legacy_id_digest;
 1735         e_legacy->is_legacy = 1;
 1736         smartlist_add(dir_sources, e_legacy);
 1737       }
 1738     } SMARTLIST_FOREACH_END(v);
 1739     smartlist_sort(dir_sources, compare_dir_src_ents_by_authority_id_);
 1740 
 1741     SMARTLIST_FOREACH_BEGIN(dir_sources, const dir_src_ent_t *, e) {
 1742       char fingerprint[HEX_DIGEST_LEN+1];
 1743       char votedigest[HEX_DIGEST_LEN+1];
 1744       networkstatus_t *v = e->v;
 1745       networkstatus_voter_info_t *voter = get_voter(v);
 1746 
 1747       base16_encode(fingerprint, sizeof(fingerprint), e->digest, DIGEST_LEN);
 1748       base16_encode(votedigest, sizeof(votedigest), voter->vote_digest,
 1749                     DIGEST_LEN);
 1750 
 1751       smartlist_add_asprintf(chunks,
 1752                    "dir-source %s%s %s %s %s %d %d\n",
 1753                    voter->nickname, e->is_legacy ? "-legacy" : "",
 1754                    fingerprint, voter->address, fmt_addr32(voter->addr),
 1755                    voter->dir_port,
 1756                    voter->or_port);
 1757       if (! e->is_legacy) {
 1758         smartlist_add_asprintf(chunks,
 1759                      "contact %s\n"
 1760                      "vote-digest %s\n",
 1761                      voter->contact,
 1762                      votedigest);
 1763       }
 1764     } SMARTLIST_FOREACH_END(e);
 1765     SMARTLIST_FOREACH(dir_sources, dir_src_ent_t *, e, tor_free(e));
 1766     smartlist_free(dir_sources);
 1767   }
 1768 
 1769   {
 1770     char *max_unmeasured_param = NULL;
 1771     /* XXXX Extract this code into a common function.  Or don't!  see #19011 */
 1772     if (params) {
 1773       if (strcmpstart(params, "maxunmeasuredbw=") == 0)
 1774         max_unmeasured_param = params;
 1775       else
 1776         max_unmeasured_param = strstr(params, " maxunmeasuredbw=");
 1777     }
 1778     if (max_unmeasured_param) {
 1779       int ok = 0;
 1780       char *eq = strchr(max_unmeasured_param, '=');
 1781       if (eq) {
 1782         max_unmeasured_bw_kb = (uint32_t)
 1783           tor_parse_ulong(eq+1, 10, 1, UINT32_MAX, &ok, NULL);
 1784         if (!ok) {
 1785           log_warn(LD_DIR, "Bad element '%s' in max unmeasured bw param",
 1786                    escaped(max_unmeasured_param));
 1787           max_unmeasured_bw_kb = DEFAULT_MAX_UNMEASURED_BW_KB;
 1788         }
 1789       }
 1790     }
 1791   }
 1792 
 1793   /* Add the actual router entries. */
 1794   {
 1795     int *size; /* size[j] is the number of routerstatuses in votes[j]. */
 1796     int *flag_counts; /* The number of voters that list flag[j] for the
 1797                        * currently considered router. */
 1798     int i;
 1799     smartlist_t *matching_descs = smartlist_new();
 1800     smartlist_t *chosen_flags = smartlist_new();
 1801     smartlist_t *versions = smartlist_new();
 1802     smartlist_t *protocols = smartlist_new();
 1803     smartlist_t *exitsummaries = smartlist_new();
 1804     uint32_t *bandwidths_kb = tor_calloc(smartlist_len(votes),
 1805                                          sizeof(uint32_t));
 1806     uint32_t *measured_bws_kb = tor_calloc(smartlist_len(votes),
 1807                                            sizeof(uint32_t));
 1808     uint32_t *measured_guardfraction = tor_calloc(smartlist_len(votes),
 1809                                                   sizeof(uint32_t));
 1810     int num_bandwidths;
 1811     int num_mbws;
 1812     int num_guardfraction_inputs;
 1813 
 1814     int *n_voter_flags; /* n_voter_flags[j] is the number of flags that
 1815                          * votes[j] knows about. */
 1816     int *n_flag_voters; /* n_flag_voters[f] is the number of votes that care
 1817                          * about flags[f]. */
 1818     int **flag_map; /* flag_map[j][b] is an index f such that flag_map[f]
 1819                      * is the same flag as votes[j]->known_flags[b]. */
 1820     int *named_flag; /* Index of the flag "Named" for votes[j] */
 1821     int *unnamed_flag; /* Index of the flag "Unnamed" for votes[j] */
 1822     int n_authorities_measuring_bandwidth;
 1823 
 1824     strmap_t *name_to_id_map = strmap_new();
 1825     char conflict[DIGEST_LEN];
 1826     char unknown[DIGEST_LEN];
 1827     memset(conflict, 0, sizeof(conflict));
 1828     memset(unknown, 0xff, sizeof(conflict));
 1829 
 1830     size = tor_calloc(smartlist_len(votes), sizeof(int));
 1831     n_voter_flags = tor_calloc(smartlist_len(votes), sizeof(int));
 1832     n_flag_voters = tor_calloc(smartlist_len(flags), sizeof(int));
 1833     flag_map = tor_calloc(smartlist_len(votes), sizeof(int *));
 1834     named_flag = tor_calloc(smartlist_len(votes), sizeof(int));
 1835     unnamed_flag = tor_calloc(smartlist_len(votes), sizeof(int));
 1836     for (i = 0; i < smartlist_len(votes); ++i)
 1837       unnamed_flag[i] = named_flag[i] = -1;
 1838 
 1839     /* Build the flag indexes. Note that no vote can have more than 64 members
 1840      * for known_flags, so no value will be greater than 63, so it's safe to
 1841      * do UINT64_C(1) << index on these values.  But note also that
 1842      * named_flag and unnamed_flag are initialized to -1, so we need to check
 1843      * that they're actually set before doing UINT64_C(1) << index with
 1844      * them.*/
 1845     SMARTLIST_FOREACH_BEGIN(votes, networkstatus_t *, v) {
 1846       flag_map[v_sl_idx] = tor_calloc(smartlist_len(v->known_flags),
 1847                                       sizeof(int));
 1848       if (smartlist_len(v->known_flags) > MAX_KNOWN_FLAGS_IN_VOTE) {
 1849         log_warn(LD_BUG, "Somehow, a vote has %d entries in known_flags",
 1850                  smartlist_len(v->known_flags));
 1851       }
 1852       SMARTLIST_FOREACH_BEGIN(v->known_flags, const char *, fl) {
 1853         int p = smartlist_string_pos(flags, fl);
 1854         tor_assert(p >= 0);
 1855         flag_map[v_sl_idx][fl_sl_idx] = p;
 1856         ++n_flag_voters[p];
 1857         if (!strcmp(fl, "Named"))
 1858           named_flag[v_sl_idx] = fl_sl_idx;
 1859         if (!strcmp(fl, "Unnamed"))
 1860           unnamed_flag[v_sl_idx] = fl_sl_idx;
 1861       } SMARTLIST_FOREACH_END(fl);
 1862       n_voter_flags[v_sl_idx] = smartlist_len(v->known_flags);
 1863       size[v_sl_idx] = smartlist_len(v->routerstatus_list);
 1864     } SMARTLIST_FOREACH_END(v);
 1865 
 1866     /* Named and Unnamed get treated specially */
 1867     {
 1868       SMARTLIST_FOREACH_BEGIN(votes, networkstatus_t *, v) {
 1869         uint64_t nf;
 1870         if (named_flag[v_sl_idx]<0)
 1871           continue;
 1872         nf = UINT64_C(1) << named_flag[v_sl_idx];
 1873         SMARTLIST_FOREACH_BEGIN(v->routerstatus_list,
 1874                                 vote_routerstatus_t *, rs) {
 1875 
 1876           if ((rs->flags & nf) != 0) {
 1877             const char *d = strmap_get_lc(name_to_id_map, rs->status.nickname);
 1878             if (!d) {
 1879               /* We have no name officially mapped to this digest. */
 1880               strmap_set_lc(name_to_id_map, rs->status.nickname,
 1881                             rs->status.identity_digest);
 1882             } else if (d != conflict &&
 1883                 fast_memcmp(d, rs->status.identity_digest, DIGEST_LEN)) {
 1884               /* Authorities disagree about this nickname. */
 1885               strmap_set_lc(name_to_id_map, rs->status.nickname, conflict);
 1886             } else {
 1887               /* It's already a conflict, or it's already this ID. */
 1888             }
 1889           }
 1890         } SMARTLIST_FOREACH_END(rs);
 1891       } SMARTLIST_FOREACH_END(v);
 1892 
 1893       SMARTLIST_FOREACH_BEGIN(votes, networkstatus_t *, v) {
 1894         uint64_t uf;
 1895         if (unnamed_flag[v_sl_idx]<0)
 1896           continue;
 1897         uf = UINT64_C(1) << unnamed_flag[v_sl_idx];
 1898         SMARTLIST_FOREACH_BEGIN(v->routerstatus_list,
 1899                                 vote_routerstatus_t *, rs) {
 1900           if ((rs->flags & uf) != 0) {
 1901             const char *d = strmap_get_lc(name_to_id_map, rs->status.nickname);
 1902             if (d == conflict || d == unknown) {
 1903               /* Leave it alone; we know what it is. */
 1904             } else if (!d) {
 1905               /* We have no name officially mapped to this digest. */
 1906               strmap_set_lc(name_to_id_map, rs->status.nickname, unknown);
 1907             } else if (fast_memeq(d, rs->status.identity_digest, DIGEST_LEN)) {
 1908               /* Authorities disagree about this nickname. */
 1909               strmap_set_lc(name_to_id_map, rs->status.nickname, conflict);
 1910             } else {
 1911               /* It's mapped to a different name. */
 1912             }
 1913           }
 1914         } SMARTLIST_FOREACH_END(rs);
 1915       } SMARTLIST_FOREACH_END(v);
 1916     }
 1917 
 1918     /* We need to know how many votes measure bandwidth. */
 1919     n_authorities_measuring_bandwidth = 0;
 1920     SMARTLIST_FOREACH(votes, const networkstatus_t *, v,
 1921        if (v->has_measured_bws) {
 1922          ++n_authorities_measuring_bandwidth;
 1923        }
 1924     );
 1925 
 1926     /* Populate the collator */
 1927     collator = dircollator_new(smartlist_len(votes), total_authorities);
 1928     SMARTLIST_FOREACH_BEGIN(votes, networkstatus_t *, v) {
 1929       dircollator_add_vote(collator, v);
 1930     } SMARTLIST_FOREACH_END(v);
 1931 
 1932     dircollator_collate(collator, consensus_method);
 1933 
 1934     /* Now go through all the votes */
 1935     flag_counts = tor_calloc(smartlist_len(flags), sizeof(int));
 1936     const int num_routers = dircollator_n_routers(collator);
 1937     for (i = 0; i < num_routers; ++i) {
 1938       vote_routerstatus_t **vrs_lst =
 1939         dircollator_get_votes_for_router(collator, i);
 1940 
 1941       vote_routerstatus_t *rs;
 1942       routerstatus_t rs_out;
 1943       const char *current_rsa_id = NULL;
 1944       const char *chosen_version;
 1945       const char *chosen_protocol_list;
 1946       const char *chosen_name = NULL;
 1947       int exitsummary_disagreement = 0;
 1948       int is_named = 0, is_unnamed = 0, is_running = 0, is_valid = 0;
 1949       int is_guard = 0, is_exit = 0, is_bad_exit = 0;
 1950       int naming_conflict = 0;
 1951       int n_listing = 0;
 1952       char microdesc_digest[DIGEST256_LEN];
 1953       tor_addr_port_t alt_orport = {TOR_ADDR_NULL, 0};
 1954 
 1955       memset(flag_counts, 0, sizeof(int)*smartlist_len(flags));
 1956       smartlist_clear(matching_descs);
 1957       smartlist_clear(chosen_flags);
 1958       smartlist_clear(versions);
 1959       smartlist_clear(protocols);
 1960       num_bandwidths = 0;
 1961       num_mbws = 0;
 1962       num_guardfraction_inputs = 0;
 1963       int ed_consensus = 0;
 1964       const uint8_t *ed_consensus_val = NULL;
 1965 
 1966       /* Okay, go through all the entries for this digest. */
 1967       for (int voter_idx = 0; voter_idx < smartlist_len(votes); ++voter_idx) {
 1968         if (vrs_lst[voter_idx] == NULL)
 1969           continue; /* This voter had nothing to say about this entry. */
 1970         rs = vrs_lst[voter_idx];
 1971         ++n_listing;
 1972 
 1973         current_rsa_id = rs->status.identity_digest;
 1974 
 1975         smartlist_add(matching_descs, rs);
 1976         if (rs->version && rs->version[0])
 1977           smartlist_add(versions, rs->version);
 1978 
 1979         if (rs->protocols) {
 1980           /* We include this one even if it's empty: voting for an
 1981            * empty protocol list actually is meaningful. */
 1982           smartlist_add(protocols, rs->protocols);
 1983         }
 1984 
 1985         /* Tally up all the flags. */
 1986         for (int flag = 0; flag < n_voter_flags[voter_idx]; ++flag) {
 1987           if (rs->flags & (UINT64_C(1) << flag))
 1988             ++flag_counts[flag_map[voter_idx][flag]];
 1989         }
 1990         if (named_flag[voter_idx] >= 0 &&
 1991             (rs->flags & (UINT64_C(1) << named_flag[voter_idx]))) {
 1992           if (chosen_name && strcmp(chosen_name, rs->status.nickname)) {
 1993             log_notice(LD_DIR, "Conflict on naming for router: %s vs %s",
 1994                        chosen_name, rs->status.nickname);
 1995             naming_conflict = 1;
 1996           }
 1997           chosen_name = rs->status.nickname;
 1998         }
 1999 
 2000         /* Count guardfraction votes and note down the values. */
 2001         if (rs->status.has_guardfraction) {
 2002           measured_guardfraction[num_guardfraction_inputs++] =
 2003             rs->status.guardfraction_percentage;
 2004         }
 2005 
 2006         /* count bandwidths */
 2007         if (rs->has_measured_bw)
 2008           measured_bws_kb[num_mbws++] = rs->measured_bw_kb;
 2009 
 2010         if (rs->status.has_bandwidth)
 2011           bandwidths_kb[num_bandwidths++] = rs->status.bandwidth_kb;
 2012 
 2013         /* Count number for which ed25519 is canonical. */
 2014         if (rs->ed25519_reflects_consensus) {
 2015           ++ed_consensus;
 2016           if (ed_consensus_val) {
 2017             tor_assert(fast_memeq(ed_consensus_val, rs->ed25519_id,
 2018                                   ED25519_PUBKEY_LEN));
 2019           } else {
 2020             ed_consensus_val = rs->ed25519_id;
 2021           }
 2022         }
 2023       }
 2024 
 2025       /* We don't include this router at all unless more than half of
 2026        * the authorities we believe in list it. */
 2027       if (n_listing <= total_authorities/2)
 2028         continue;
 2029 
 2030       if (ed_consensus > 0) {
 2031         if (ed_consensus <= total_authorities / 2) {
 2032           log_warn(LD_BUG, "Not enough entries had ed_consensus set; how "
 2033                    "can we have a consensus of %d?", ed_consensus);
 2034         }
 2035       }
 2036 
 2037       /* The clangalyzer can't figure out that this will never be NULL
 2038        * if n_listing is at least 1 */
 2039       tor_assert(current_rsa_id);
 2040 
 2041       /* Figure out the most popular opinion of what the most recent
 2042        * routerinfo and its contents are. */
 2043       memset(microdesc_digest, 0, sizeof(microdesc_digest));
 2044       rs = compute_routerstatus_consensus(matching_descs, consensus_method,
 2045                                           microdesc_digest, &alt_orport);
 2046       /* Copy bits of that into rs_out. */
 2047       memset(&rs_out, 0, sizeof(rs_out));
 2048       tor_assert(fast_memeq(current_rsa_id,
 2049                             rs->status.identity_digest,DIGEST_LEN));
 2050       memcpy(rs_out.identity_digest, current_rsa_id, DIGEST_LEN);
 2051       memcpy(rs_out.descriptor_digest, rs->status.descriptor_digest,
 2052              DIGEST_LEN);
 2053       rs_out.addr = rs->status.addr;
 2054       rs_out.published_on = rs->status.published_on;
 2055       rs_out.dir_port = rs->status.dir_port;
 2056       rs_out.or_port = rs->status.or_port;
 2057       tor_addr_copy(&rs_out.ipv6_addr, &alt_orport.addr);
 2058       rs_out.ipv6_orport = alt_orport.port;
 2059       rs_out.has_bandwidth = 0;
 2060       rs_out.has_exitsummary = 0;
 2061 
 2062       if (chosen_name && !naming_conflict) {
 2063         strlcpy(rs_out.nickname, chosen_name, sizeof(rs_out.nickname));
 2064       } else {
 2065         strlcpy(rs_out.nickname, rs->status.nickname, sizeof(rs_out.nickname));
 2066       }
 2067 
 2068       {
 2069         const char *d = strmap_get_lc(name_to_id_map, rs_out.nickname);
 2070         if (!d) {
 2071           is_named = is_unnamed = 0;
 2072         } else if (fast_memeq(d, current_rsa_id, DIGEST_LEN)) {
 2073           is_named = 1; is_unnamed = 0;
 2074         } else {
 2075           is_named = 0; is_unnamed = 1;
 2076         }
 2077       }
 2078 
 2079       /* Set the flags. */
 2080       smartlist_add(chosen_flags, (char*)"s"); /* for the start of the line. */
 2081       SMARTLIST_FOREACH_BEGIN(flags, const char *, fl) {
 2082         if (!strcmp(fl, "Named")) {
 2083           if (is_named)
 2084             smartlist_add(chosen_flags, (char*)fl);
 2085         } else if (!strcmp(fl, "Unnamed")) {
 2086           if (is_unnamed)
 2087             smartlist_add(chosen_flags, (char*)fl);
 2088         } else if (!strcmp(fl, "NoEdConsensus")) {
 2089           if (ed_consensus <= total_authorities/2)
 2090             smartlist_add(chosen_flags, (char*)fl);
 2091         } else {
 2092           if (flag_counts[fl_sl_idx] > n_flag_voters[fl_sl_idx]/2) {
 2093             smartlist_add(chosen_flags, (char*)fl);
 2094             if (!strcmp(fl, "Exit"))
 2095               is_exit = 1;
 2096             else if (!strcmp(fl, "Guard"))
 2097               is_guard = 1;
 2098             else if (!strcmp(fl, "Running"))
 2099               is_running = 1;
 2100             else if (!strcmp(fl, "BadExit"))
 2101               is_bad_exit = 1;
 2102             else if (!strcmp(fl, "Valid"))
 2103               is_valid = 1;
 2104           }
 2105         }
 2106       } SMARTLIST_FOREACH_END(fl);
 2107 
 2108       /* Starting with consensus method 4 we do not list servers
 2109        * that are not running in a consensus.  See Proposal 138 */
 2110       if (!is_running)
 2111         continue;
 2112 
 2113       /* Starting with consensus method 24, we don't list servers
 2114        * that are not valid in a consensus.  See Proposal 272 */
 2115       if (!is_valid)
 2116         continue;
 2117 
 2118       /* Pick the version. */
 2119       if (smartlist_len(versions)) {
 2120         sort_version_list(versions, 0);
 2121         chosen_version = get_most_frequent_member(versions);
 2122       } else {
 2123         chosen_version = NULL;
 2124       }
 2125 
 2126       /* Pick the protocol list */
 2127       if (smartlist_len(protocols)) {
 2128         smartlist_sort_strings(protocols);
 2129         chosen_protocol_list = get_most_frequent_member(protocols);
 2130       } else {
 2131         chosen_protocol_list = NULL;
 2132       }
 2133 
 2134       /* If it's a guard and we have enough guardfraction votes,
 2135          calculate its consensus guardfraction value. */
 2136       if (is_guard && num_guardfraction_inputs > 2) {
 2137         rs_out.has_guardfraction = 1;
 2138         rs_out.guardfraction_percentage = median_uint32(measured_guardfraction,
 2139                                                      num_guardfraction_inputs);
 2140         /* final value should be an integer percentage! */
 2141         tor_assert(rs_out.guardfraction_percentage <= 100);
 2142       }
 2143 
 2144       /* Pick a bandwidth */
 2145       if (num_mbws > 2) {
 2146         rs_out.has_bandwidth = 1;
 2147         rs_out.bw_is_unmeasured = 0;
 2148         rs_out.bandwidth_kb = median_uint32(measured_bws_kb, num_mbws);
 2149       } else if (num_bandwidths > 0) {
 2150         rs_out.has_bandwidth = 1;
 2151         rs_out.bw_is_unmeasured = 1;
 2152         rs_out.bandwidth_kb = median_uint32(bandwidths_kb, num_bandwidths);
 2153         if (n_authorities_measuring_bandwidth > 2) {
 2154           /* Cap non-measured bandwidths. */
 2155           if (rs_out.bandwidth_kb > max_unmeasured_bw_kb) {
 2156             rs_out.bandwidth_kb = max_unmeasured_bw_kb;
 2157           }
 2158         }
 2159       }
 2160 
 2161       /* Fix bug 2203: Do not count BadExit nodes as Exits for bw weights */
 2162       is_exit = is_exit && !is_bad_exit;
 2163 
 2164       /* Update total bandwidth weights with the bandwidths of this router. */
 2165       {
 2166         update_total_bandwidth_weights(&rs_out,
 2167                                        is_exit, is_guard,
 2168                                        &G, &M, &E, &D, &T);
 2169       }
 2170 
 2171       /* Ok, we already picked a descriptor digest we want to list
 2172        * previously.  Now we want to use the exit policy summary from
 2173        * that descriptor.  If everybody plays nice all the voters who
 2174        * listed that descriptor will have the same summary.  If not then
 2175        * something is fishy and we'll use the most common one (breaking
 2176        * ties in favor of lexicographically larger one (only because it
 2177        * lets me reuse more existing code)).
 2178        *
 2179        * The other case that can happen is that no authority that voted
 2180        * for that descriptor has an exit policy summary.  That's
 2181        * probably quite unlikely but can happen.  In that case we use
 2182        * the policy that was most often listed in votes, again breaking
 2183        * ties like in the previous case.
 2184        */
 2185       {
 2186         /* Okay, go through all the votes for this router.  We prepared
 2187          * that list previously */
 2188         const char *chosen_exitsummary = NULL;
 2189         smartlist_clear(exitsummaries);
 2190         SMARTLIST_FOREACH_BEGIN(matching_descs, vote_routerstatus_t *, vsr) {
 2191           /* Check if the vote where this status comes from had the
 2192            * proper descriptor */
 2193           tor_assert(fast_memeq(rs_out.identity_digest,
 2194                              vsr->status.identity_digest,
 2195                              DIGEST_LEN));
 2196           if (vsr->status.has_exitsummary &&
 2197                fast_memeq(rs_out.descriptor_digest,
 2198                        vsr->status.descriptor_digest,
 2199                        DIGEST_LEN)) {
 2200             tor_assert(vsr->status.exitsummary);
 2201             smartlist_add(exitsummaries, vsr->status.exitsummary);
 2202             if (!chosen_exitsummary) {
 2203               chosen_exitsummary = vsr->status.exitsummary;
 2204             } else if (strcmp(chosen_exitsummary, vsr->status.exitsummary)) {
 2205               /* Great.  There's disagreement among the voters.  That
 2206                * really shouldn't be */
 2207               exitsummary_disagreement = 1;
 2208             }
 2209           }
 2210         } SMARTLIST_FOREACH_END(vsr);
 2211 
 2212         if (exitsummary_disagreement) {
 2213           char id[HEX_DIGEST_LEN+1];
 2214           char dd[HEX_DIGEST_LEN+1];
 2215           base16_encode(id, sizeof(dd), rs_out.identity_digest, DIGEST_LEN);
 2216           base16_encode(dd, sizeof(dd), rs_out.descriptor_digest, DIGEST_LEN);
 2217           log_warn(LD_DIR, "The voters disagreed on the exit policy summary "
 2218                    " for router %s with descriptor %s.  This really shouldn't"
 2219                    " have happened.", id, dd);
 2220 
 2221           smartlist_sort_strings(exitsummaries);
 2222           chosen_exitsummary = get_most_frequent_member(exitsummaries);
 2223         } else if (!chosen_exitsummary) {
 2224           char id[HEX_DIGEST_LEN+1];
 2225           char dd[HEX_DIGEST_LEN+1];
 2226           base16_encode(id, sizeof(dd), rs_out.identity_digest, DIGEST_LEN);
 2227           base16_encode(dd, sizeof(dd), rs_out.descriptor_digest, DIGEST_LEN);
 2228           log_warn(LD_DIR, "Not one of the voters that made us select"
 2229                    "descriptor %s for router %s had an exit policy"
 2230                    "summary", dd, id);
 2231 
 2232           /* Ok, none of those voting for the digest we chose had an
 2233            * exit policy for us.  Well, that kinda sucks.
 2234            */
 2235           smartlist_clear(exitsummaries);
 2236           SMARTLIST_FOREACH(matching_descs, vote_routerstatus_t *, vsr, {
 2237             if (vsr->status.has_exitsummary)
 2238               smartlist_add(exitsummaries, vsr->status.exitsummary);
 2239           });
 2240           smartlist_sort_strings(exitsummaries);
 2241           chosen_exitsummary = get_most_frequent_member(exitsummaries);
 2242 
 2243           if (!chosen_exitsummary)
 2244             log_warn(LD_DIR, "Wow, not one of the voters had an exit "
 2245                      "policy summary for %s.  Wow.", id);
 2246         }
 2247 
 2248         if (chosen_exitsummary) {
 2249           rs_out.has_exitsummary = 1;
 2250           /* yea, discards the const */
 2251           rs_out.exitsummary = (char *)chosen_exitsummary;
 2252         }
 2253       }
 2254 
 2255       if (flavor == FLAV_MICRODESC &&
 2256           tor_digest256_is_zero(microdesc_digest)) {
 2257         /* With no microdescriptor digest, we omit the entry entirely. */
 2258         continue;
 2259       }
 2260 
 2261       {
 2262         char *buf;
 2263         /* Okay!! Now we can write the descriptor... */
 2264         /*     First line goes into "buf". */
 2265         buf = routerstatus_format_entry(&rs_out, NULL, NULL,
 2266                                         rs_format, consensus_method, NULL);
 2267         if (buf)
 2268           smartlist_add(chunks, buf);
 2269       }
 2270       /*     Now an m line, if applicable. */
 2271       if (flavor == FLAV_MICRODESC &&
 2272           !tor_digest256_is_zero(microdesc_digest)) {
 2273         char m[BASE64_DIGEST256_LEN+1];
 2274         digest256_to_base64(m, microdesc_digest);
 2275         smartlist_add_asprintf(chunks, "m %s\n", m);
 2276       }
 2277       /*     Next line is all flags.  The "\n" is missing. */
 2278       smartlist_add(chunks,
 2279                     smartlist_join_strings(chosen_flags, " ", 0, NULL));
 2280       /*     Now the version line. */
 2281       if (chosen_version) {
 2282         smartlist_add_strdup(chunks, "\nv ");
 2283         smartlist_add_strdup(chunks, chosen_version);
 2284       }
 2285       smartlist_add_strdup(chunks, "\n");
 2286       if (chosen_protocol_list &&
 2287           consensus_method >= MIN_METHOD_FOR_RS_PROTOCOLS) {
 2288         smartlist_add_asprintf(chunks, "pr %s\n", chosen_protocol_list);
 2289       }
 2290       /*     Now the weight line. */
 2291       if (rs_out.has_bandwidth) {
 2292         char *guardfraction_str = NULL;
 2293         int unmeasured = rs_out.bw_is_unmeasured;
 2294 
 2295         /* If we have guardfraction info, include it in the 'w' line. */
 2296         if (rs_out.has_guardfraction) {
 2297           tor_asprintf(&guardfraction_str,
 2298                        " GuardFraction=%u", rs_out.guardfraction_percentage);
 2299         }
 2300         smartlist_add_asprintf(chunks, "w Bandwidth=%d%s%s\n",
 2301                                rs_out.bandwidth_kb,
 2302                                unmeasured?" Unmeasured=1":"",
 2303                                guardfraction_str ? guardfraction_str : "");
 2304 
 2305         tor_free(guardfraction_str);
 2306       }
 2307 
 2308       /*     Now the exitpolicy summary line. */
 2309       if (rs_out.has_exitsummary && flavor == FLAV_NS) {
 2310         smartlist_add_asprintf(chunks, "p %s\n", rs_out.exitsummary);
 2311       }
 2312 
 2313       /* And the loop is over and we move on to the next router */
 2314     }
 2315 
 2316     tor_free(size);
 2317     tor_free(n_voter_flags);
 2318     tor_free(n_flag_voters);
 2319     for (i = 0; i < smartlist_len(votes); ++i)
 2320       tor_free(flag_map[i]);
 2321     tor_free(flag_map);
 2322     tor_free(flag_counts);
 2323     tor_free(named_flag);
 2324     tor_free(unnamed_flag);
 2325     strmap_free(name_to_id_map, NULL);
 2326     smartlist_free(matching_descs);
 2327     smartlist_free(chosen_flags);
 2328     smartlist_free(versions);
 2329     smartlist_free(protocols);
 2330     smartlist_free(exitsummaries);
 2331     tor_free(bandwidths_kb);
 2332     tor_free(measured_bws_kb);
 2333     tor_free(measured_guardfraction);
 2334   }
 2335 
 2336   /* Mark the directory footer region */
 2337   smartlist_add_strdup(chunks, "directory-footer\n");
 2338 
 2339   {
 2340     int64_t weight_scale = BW_WEIGHT_SCALE;
 2341     char *bw_weight_param = NULL;
 2342 
 2343     // Parse params, extract BW_WEIGHT_SCALE if present
 2344     // DO NOT use consensus_param_bw_weight_scale() in this code!
 2345     // The consensus is not formed yet!
 2346     /* XXXX Extract this code into a common function. Or not: #19011. */
 2347     if (params) {
 2348       if (strcmpstart(params, "bwweightscale=") == 0)
 2349         bw_weight_param = params;
 2350       else
 2351         bw_weight_param = strstr(params, " bwweightscale=");
 2352     }
 2353 
 2354     if (bw_weight_param) {
 2355       int ok=0;
 2356       char *eq = strchr(bw_weight_param, '=');
 2357       if (eq) {
 2358         weight_scale = tor_parse_long(eq+1, 10, 1, INT32_MAX, &ok,
 2359                                          NULL);
 2360         if (!ok) {
 2361           log_warn(LD_DIR, "Bad element '%s' in bw weight param",
 2362               escaped(bw_weight_param));
 2363           weight_scale = BW_WEIGHT_SCALE;
 2364         }
 2365       } else {
 2366         log_warn(LD_DIR, "Bad element '%s' in bw weight param",
 2367             escaped(bw_weight_param));
 2368         weight_scale = BW_WEIGHT_SCALE;
 2369       }
 2370     }
 2371 
 2372     added_weights = networkstatus_compute_bw_weights_v10(chunks, G, M, E, D,
 2373                                                          T, weight_scale);
 2374   }
 2375 
 2376   /* Add a signature. */
 2377   {
 2378     char digest[DIGEST256_LEN];
 2379     char fingerprint[HEX_DIGEST_LEN+1];
 2380     char signing_key_fingerprint[HEX_DIGEST_LEN+1];
 2381     digest_algorithm_t digest_alg =
 2382       flavor == FLAV_NS ? DIGEST_SHA1 : DIGEST_SHA256;
 2383     size_t digest_len =
 2384       flavor == FLAV_NS ? DIGEST_LEN : DIGEST256_LEN;
 2385     const char *algname = crypto_digest_algorithm_get_name(digest_alg);
 2386     char *signature;
 2387 
 2388     smartlist_add_strdup(chunks, "directory-signature ");
 2389 
 2390     /* Compute the hash of the chunks. */
 2391     crypto_digest_smartlist(digest, digest_len, chunks, "", digest_alg);
 2392 
 2393     /* Get the fingerprints */
 2394     crypto_pk_get_fingerprint(identity_key, fingerprint, 0);
 2395     crypto_pk_get_fingerprint(signing_key, signing_key_fingerprint, 0);
 2396 
 2397     /* add the junk that will go at the end of the line. */
 2398     if (flavor == FLAV_NS) {
 2399       smartlist_add_asprintf(chunks, "%s %s\n", fingerprint,
 2400                    signing_key_fingerprint);
 2401     } else {
 2402       smartlist_add_asprintf(chunks, "%s %s %s\n",
 2403                    algname, fingerprint,
 2404                    signing_key_fingerprint);
 2405     }
 2406     /* And the signature. */
 2407     if (!(signature = router_get_dirobj_signature(digest, digest_len,
 2408                                                   signing_key))) {
 2409       log_warn(LD_BUG, "Couldn't sign consensus networkstatus.");
 2410       goto done;
 2411     }
 2412     smartlist_add(chunks, signature);
 2413 
 2414     if (legacy_id_key_digest && legacy_signing_key) {
 2415       smartlist_add_strdup(chunks, "directory-signature ");
 2416       base16_encode(fingerprint, sizeof(fingerprint),
 2417                     legacy_id_key_digest, DIGEST_LEN);
 2418       crypto_pk_get_fingerprint(legacy_signing_key,
 2419                                 signing_key_fingerprint, 0);
 2420       if (flavor == FLAV_NS) {
 2421         smartlist_add_asprintf(chunks, "%s %s\n", fingerprint,
 2422                      signing_key_fingerprint);
 2423       } else {
 2424         smartlist_add_asprintf(chunks, "%s %s %s\n",
 2425                      algname, fingerprint,
 2426                      signing_key_fingerprint);
 2427       }
 2428 
 2429       if (!(signature = router_get_dirobj_signature(digest, digest_len,
 2430                                                     legacy_signing_key))) {
 2431         log_warn(LD_BUG, "Couldn't sign consensus networkstatus.");
 2432         goto done;
 2433       }
 2434       smartlist_add(chunks, signature);
 2435     }
 2436   }
 2437 
 2438   result = smartlist_join_strings(chunks, "", 0, NULL);
 2439 
 2440   {
 2441     networkstatus_t *c;
 2442     if (!(c = networkstatus_parse_vote_from_string(result, strlen(result),
 2443                                                    NULL,
 2444                                                    NS_TYPE_CONSENSUS))) {
 2445       log_err(LD_BUG, "Generated a networkstatus consensus we couldn't "
 2446               "parse.");
 2447       tor_free(result);
 2448       goto done;
 2449     }
 2450     // Verify balancing parameters
 2451     if (added_weights) {
 2452       networkstatus_verify_bw_weights(c, consensus_method);
 2453     }
 2454     networkstatus_vote_free(c);
 2455   }
 2456 
 2457  done:
 2458 
 2459   dircollator_free(collator);
 2460   tor_free(client_versions);
 2461   tor_free(server_versions);
 2462   tor_free(packages);
 2463   SMARTLIST_FOREACH(flags, char *, cp, tor_free(cp));
 2464   smartlist_free(flags);
 2465   SMARTLIST_FOREACH(chunks, char *, cp, tor_free(cp));
 2466   smartlist_free(chunks);
 2467   SMARTLIST_FOREACH(param_list, char *, cp, tor_free(cp));
 2468   smartlist_free(param_list);
 2469 
 2470   return result;
 2471 }
 2472 
 2473 /** Given a list of networkstatus_t for each vote, return a newly allocated
 2474  * string containing the "package" lines for the vote. */
 2475 STATIC char *
 2476 compute_consensus_package_lines(smartlist_t *votes)
 2477 {
 2478   const int n_votes = smartlist_len(votes);
 2479 
 2480   /* This will be a map from "packagename version" strings to arrays
 2481    * of const char *, with the i'th member of the array corresponding to the
 2482    * package line from the i'th vote.
 2483    */
 2484   strmap_t *package_status = strmap_new();
 2485 
 2486   SMARTLIST_FOREACH_BEGIN(votes, networkstatus_t *, v) {
 2487     if (! v->package_lines)
 2488       continue;
 2489     SMARTLIST_FOREACH_BEGIN(v->package_lines, const char *, line) {
 2490       if (! validate_recommended_package_line(line))
 2491         continue;
 2492 
 2493       /* Skip 'cp' to the second space in the line. */
 2494       const char *cp = strchr(line, ' ');
 2495       if (!cp) continue;
 2496       ++cp;
 2497       cp = strchr(cp, ' ');
 2498       if (!cp) continue;
 2499 
 2500       char *key = tor_strndup(line, cp - line);
 2501 
 2502       const char **status = strmap_get(package_status, key);
 2503       if (!status) {
 2504         status = tor_calloc(n_votes, sizeof(const char *));
 2505         strmap_set(package_status, key, status);
 2506       }
 2507       status[v_sl_idx] = line; /* overwrite old value */
 2508       tor_free(key);
 2509     } SMARTLIST_FOREACH_END(line);
 2510   } SMARTLIST_FOREACH_END(v);
 2511 
 2512   smartlist_t *entries = smartlist_new(); /* temporary */
 2513   smartlist_t *result_list = smartlist_new(); /* output */
 2514   STRMAP_FOREACH(package_status, key, const char **, values) {
 2515     int i, count=-1;
 2516     for (i = 0; i < n_votes; ++i) {
 2517       if (values[i])
 2518         smartlist_add(entries, (void*) values[i]);
 2519     }
 2520     smartlist_sort_strings(entries);
 2521     int n_voting_for_entry = smartlist_len(entries);
 2522     const char *most_frequent =
 2523       smartlist_get_most_frequent_string_(entries, &count);
 2524 
 2525     if (n_voting_for_entry >= 3 && count > n_voting_for_entry / 2) {
 2526       smartlist_add_asprintf(result_list, "package %s\n", most_frequent);
 2527     }
 2528 
 2529     smartlist_clear(entries);
 2530 
 2531   } STRMAP_FOREACH_END;
 2532 
 2533   smartlist_sort_strings(result_list);
 2534 
 2535   char *result = smartlist_join_strings(result_list, "", 0, NULL);
 2536 
 2537   SMARTLIST_FOREACH(result_list, char *, cp, tor_free(cp));
 2538   smartlist_free(result_list);
 2539   smartlist_free(entries);
 2540   strmap_free(package_status, tor_free_);
 2541 
 2542   return result;
 2543 }
 2544 
 2545 /** Given a consensus vote <b>target</b> and a set of detached signatures in
 2546  * <b>sigs</b> that correspond to the same consensus, check whether there are
 2547  * any new signatures in <b>src_voter_list</b> that should be added to
 2548  * <b>target</b>. (A signature should be added if we have no signature for that
 2549  * voter in <b>target</b> yet, or if we have no verifiable signature and the
 2550  * new signature is verifiable.)  Return the number of signatures added or
 2551  * changed, or -1 if the document signed by <b>sigs</b> isn't the same
 2552  * document as <b>target</b>. */
 2553 STATIC int
 2554 networkstatus_add_detached_signatures(networkstatus_t *target,
 2555                                       ns_detached_signatures_t *sigs,
 2556                                       const char *source,
 2557                                       int severity,
 2558                                       const char **msg_out)
 2559 {
 2560   int r = 0;
 2561   const char *flavor;
 2562   smartlist_t *siglist;
 2563   tor_assert(sigs);
 2564   tor_assert(target);
 2565   tor_assert(target->type == NS_TYPE_CONSENSUS);
 2566 
 2567   flavor = networkstatus_get_flavor_name(target->flavor);
 2568 
 2569   /* Do the times seem right? */
 2570   if (target->valid_after != sigs->valid_after) {
 2571     *msg_out = "Valid-After times do not match "
 2572       "when adding detached signatures to consensus";
 2573     return -1;
 2574   }
 2575   if (target->fresh_until != sigs->fresh_until) {
 2576     *msg_out = "Fresh-until times do not match "
 2577       "when adding detached signatures to consensus";
 2578     return -1;
 2579   }
 2580   if (target->valid_until != sigs->valid_until) {
 2581     *msg_out = "Valid-until times do not match "
 2582       "when adding detached signatures to consensus";
 2583     return -1;
 2584   }
 2585   siglist = strmap_get(sigs->signatures, flavor);
 2586   if (!siglist) {
 2587     *msg_out = "No signatures for given consensus flavor";
 2588     return -1;
 2589   }
 2590 
 2591   /** Make sure all the digests we know match, and at least one matches. */
 2592   {
 2593     common_digests_t *digests = strmap_get(sigs->digests, flavor);
 2594     int n_matches = 0;
 2595     int alg;
 2596     if (!digests) {
 2597       *msg_out = "No digests for given consensus flavor";
 2598       return -1;
 2599     }
 2600     for (alg = DIGEST_SHA1; alg < N_COMMON_DIGEST_ALGORITHMS; ++alg) {
 2601       if (!fast_mem_is_zero(digests->d[alg], DIGEST256_LEN)) {
 2602         if (fast_memeq(target->digests.d[alg], digests->d[alg],
 2603                        DIGEST256_LEN)) {
 2604           ++n_matches;
 2605         } else {
 2606           *msg_out = "Mismatched digest.";
 2607           return -1;
 2608         }
 2609       }
 2610     }
 2611     if (!n_matches) {
 2612       *msg_out = "No recognized digests for given consensus flavor";
 2613     }
 2614   }
 2615 
 2616   /* For each voter in src... */
 2617   SMARTLIST_FOREACH_BEGIN(siglist, document_signature_t *, sig) {
 2618     char voter_identity[HEX_DIGEST_LEN+1];
 2619     networkstatus_voter_info_t *target_voter =
 2620       networkstatus_get_voter_by_id(target, sig->identity_digest);
 2621     authority_cert_t *cert = NULL;
 2622     const char *algorithm;
 2623     document_signature_t *old_sig = NULL;
 2624 
 2625     algorithm = crypto_digest_algorithm_get_name(sig->alg);
 2626 
 2627     base16_encode(voter_identity, sizeof(voter_identity),
 2628                   sig->identity_digest, DIGEST_LEN);
 2629     log_info(LD_DIR, "Looking at signature from %s using %s", voter_identity,
 2630              algorithm);
 2631     /* If the target doesn't know about this voter, then forget it. */
 2632     if (!target_voter) {
 2633       log_info(LD_DIR, "We do not know any voter with ID %s", voter_identity);
 2634       continue;
 2635     }
 2636 
 2637     old_sig = networkstatus_get_voter_sig_by_alg(target_voter, sig->alg);
 2638 
 2639     /* If the target already has a good signature from this voter, then skip
 2640      * this one. */
 2641     if (old_sig && old_sig->good_signature) {
 2642       log_info(LD_DIR, "We already have a good signature from %s using %s",
 2643                voter_identity, algorithm);
 2644       continue;
 2645     }
 2646 
 2647     /* Try checking the signature if we haven't already. */
 2648     if (!sig->good_signature && !sig->bad_signature) {
 2649       cert = authority_cert_get_by_digests(sig->identity_digest,
 2650                                            sig->signing_key_digest);
 2651       if (cert) {
 2652         /* Not checking the return value here, since we are going to look
 2653          * at the status of sig->good_signature in a moment. */
 2654         (void) networkstatus_check_document_signature(target, sig, cert);
 2655       }
 2656     }
 2657 
 2658     /* If this signature is good, or we don't have any signature yet,
 2659      * then maybe add it. */
 2660     if (sig->good_signature || !old_sig || old_sig->bad_signature) {
 2661       log_info(LD_DIR, "Adding signature from %s with %s", voter_identity,
 2662                algorithm);
 2663       tor_log(severity, LD_DIR, "Added a signature for %s from %s.",
 2664           target_voter->nickname, source);
 2665       ++r;
 2666       if (old_sig) {
 2667         smartlist_remove(target_voter->sigs, old_sig);
 2668         document_signature_free(old_sig);
 2669       }
 2670       smartlist_add(target_voter->sigs, document_signature_dup(sig));
 2671     } else {
 2672       log_info(LD_DIR, "Not adding signature from %s", voter_identity);
 2673     }
 2674   } SMARTLIST_FOREACH_END(sig);
 2675 
 2676   return r;
 2677 }
 2678 
 2679 /** Return a newly allocated string containing all the signatures on
 2680  * <b>consensus</b> by all voters. If <b>for_detached_signatures</b> is true,
 2681  * then the signatures will be put in a detached signatures document, so
 2682  * prefix any non-NS-flavored signatures with "additional-signature" rather
 2683  * than "directory-signature". */
 2684 static char *
 2685 networkstatus_format_signatures(networkstatus_t *consensus,
 2686                                 int for_detached_signatures)
 2687 {
 2688   smartlist_t *elements;
 2689   char buf[4096];
 2690   char *result = NULL;
 2691   int n_sigs = 0;
 2692   const consensus_flavor_t flavor = consensus->flavor;
 2693   const char *flavor_name = networkstatus_get_flavor_name(flavor);
 2694   const char *keyword;
 2695 
 2696   if (for_detached_signatures && flavor != FLAV_NS)
 2697     keyword = "additional-signature";
 2698   else
 2699     keyword = "directory-signature";
 2700 
 2701   elements = smartlist_new();
 2702 
 2703   SMARTLIST_FOREACH_BEGIN(consensus->voters, networkstatus_voter_info_t *, v) {
 2704     SMARTLIST_FOREACH_BEGIN(v->sigs, document_signature_t *, sig) {
 2705       char sk[HEX_DIGEST_LEN+1];
 2706       char id[HEX_DIGEST_LEN+1];
 2707       if (!sig->signature || sig->bad_signature)
 2708         continue;
 2709       ++n_sigs;
 2710       base16_encode(sk, sizeof(sk), sig->signing_key_digest, DIGEST_LEN);
 2711       base16_encode(id, sizeof(id), sig->identity_digest, DIGEST_LEN);
 2712       if (flavor == FLAV_NS) {
 2713         smartlist_add_asprintf(elements,
 2714                      "%s %s %s\n-----BEGIN SIGNATURE-----\n",
 2715                      keyword, id, sk);
 2716       } else {
 2717         const char *digest_name =
 2718           crypto_digest_algorithm_get_name(sig->alg);
 2719         smartlist_add_asprintf(elements,
 2720                      "%s%s%s %s %s %s\n-----BEGIN SIGNATURE-----\n",
 2721                      keyword,
 2722                      for_detached_signatures ? " " : "",
 2723                      for_detached_signatures ? flavor_name : "",
 2724                      digest_name, id, sk);
 2725       }
 2726       base64_encode(buf, sizeof(buf), sig->signature, sig->signature_len,
 2727                     BASE64_ENCODE_MULTILINE);
 2728       strlcat(buf, "-----END SIGNATURE-----\n", sizeof(buf));
 2729       smartlist_add_strdup(elements, buf);
 2730     } SMARTLIST_FOREACH_END(sig);
 2731   } SMARTLIST_FOREACH_END(v);
 2732 
 2733   result = smartlist_join_strings(elements, "", 0, NULL);
 2734   SMARTLIST_FOREACH(elements, char *, cp, tor_free(cp));
 2735   smartlist_free(elements);
 2736   if (!n_sigs)
 2737     tor_free(result);
 2738   return result;
 2739 }
 2740 
 2741 /** Return a newly allocated string holding the detached-signatures document
 2742  * corresponding to the signatures on <b>consensuses</b>, which must contain
 2743  * exactly one FLAV_NS consensus, and no more than one consensus for each
 2744  * other flavor. */
 2745 STATIC char *
 2746 networkstatus_get_detached_signatures(smartlist_t *consensuses)
 2747 {
 2748   smartlist_t *elements;
 2749   char *result = NULL, *sigs = NULL;
 2750   networkstatus_t *consensus_ns = NULL;
 2751   tor_assert(consensuses);
 2752 
 2753   SMARTLIST_FOREACH(consensuses, networkstatus_t *, ns, {
 2754       tor_assert(ns);
 2755       tor_assert(ns->type == NS_TYPE_CONSENSUS);
 2756       if (ns && ns->flavor == FLAV_NS)
 2757         consensus_ns = ns;
 2758   });
 2759   if (!consensus_ns) {
 2760     log_warn(LD_BUG, "No NS consensus given.");
 2761     return NULL;
 2762   }
 2763 
 2764   elements = smartlist_new();
 2765 
 2766   {
 2767     char va_buf[ISO_TIME_LEN+1], fu_buf[ISO_TIME_LEN+1],
 2768       vu_buf[ISO_TIME_LEN+1];
 2769     char d[HEX_DIGEST_LEN+1];
 2770 
 2771     base16_encode(d, sizeof(d),
 2772                   consensus_ns->digests.d[DIGEST_SHA1], DIGEST_LEN);
 2773     format_iso_time(va_buf, consensus_ns->valid_after);
 2774     format_iso_time(fu_buf, consensus_ns->fresh_until);
 2775     format_iso_time(vu_buf, consensus_ns->valid_until);
 2776 
 2777     smartlist_add_asprintf(elements,
 2778                  "consensus-digest %s\n"
 2779                  "valid-after %s\n"
 2780                  "fresh-until %s\n"
 2781                  "valid-until %s\n", d, va_buf, fu_buf, vu_buf);
 2782   }
 2783 
 2784   /* Get all the digests for the non-FLAV_NS consensuses */
 2785   SMARTLIST_FOREACH_BEGIN(consensuses, networkstatus_t *, ns) {
 2786     const char *flavor_name = networkstatus_get_flavor_name(ns->flavor);
 2787     int alg;
 2788     if (ns->flavor == FLAV_NS)
 2789       continue;
 2790 
 2791     /* start with SHA256; we don't include SHA1 for anything but the basic
 2792      * consensus. */
 2793     for (alg = DIGEST_SHA256; alg < N_COMMON_DIGEST_ALGORITHMS; ++alg) {
 2794       char d[HEX_DIGEST256_LEN+1];
 2795       const char *alg_name =
 2796         crypto_digest_algorithm_get_name(alg);
 2797       if (fast_mem_is_zero(ns->digests.d[alg], DIGEST256_LEN))
 2798         continue;
 2799       base16_encode(d, sizeof(d), ns->digests.d[alg], DIGEST256_LEN);
 2800       smartlist_add_asprintf(elements, "additional-digest %s %s %s\n",
 2801                    flavor_name, alg_name, d);
 2802     }
 2803   } SMARTLIST_FOREACH_END(ns);
 2804 
 2805   /* Now get all the sigs for non-FLAV_NS consensuses */
 2806   SMARTLIST_FOREACH_BEGIN(consensuses, networkstatus_t *, ns) {
 2807     char *sigs_on_this_consensus;
 2808     if (ns->flavor == FLAV_NS)
 2809       continue;
 2810     sigs_on_this_consensus = networkstatus_format_signatures(ns, 1);
 2811     if (!sigs_on_this_consensus) {
 2812       log_warn(LD_DIR, "Couldn't format signatures");
 2813       goto err;
 2814     }
 2815     smartlist_add(elements, sigs_on_this_consensus);
 2816   } SMARTLIST_FOREACH_END(ns);
 2817 
 2818   /* Now add the FLAV_NS consensus signatrures. */
 2819   sigs = networkstatus_format_signatures(consensus_ns, 1);
 2820   if (!sigs)
 2821     goto err;
 2822   smartlist_add(elements, sigs);
 2823 
 2824   result = smartlist_join_strings(elements, "", 0, NULL);
 2825  err:
 2826   SMARTLIST_FOREACH(elements, char *, cp, tor_free(cp));
 2827   smartlist_free(elements);
 2828   return result;
 2829 }
 2830 
 2831 /** Return a newly allocated string holding a detached-signatures document for
 2832  * all of the in-progress consensuses in the <b>n_flavors</b>-element array at
 2833  * <b>pending</b>. */
 2834 static char *
 2835 get_detached_signatures_from_pending_consensuses(pending_consensus_t *pending,
 2836                                                  int n_flavors)
 2837 {
 2838   int flav;
 2839   char *signatures;
 2840   smartlist_t *c = smartlist_new();
 2841   for (flav = 0; flav < n_flavors; ++flav) {
 2842     if (pending[flav].consensus)
 2843       smartlist_add(c, pending[flav].consensus);
 2844   }
 2845   signatures = networkstatus_get_detached_signatures(c);
 2846   smartlist_free(c);
 2847   return signatures;
 2848 }
 2849 
 2850 /**
 2851  * Entry point: Take whatever voting actions are pending as of <b>now</b>.
 2852  *
 2853  * Return the time at which the next action should be taken.
 2854  */
 2855 time_t
 2856 dirvote_act(const or_options_t *options, time_t now)
 2857 {
 2858   if (!authdir_mode_v3(options))
 2859     return TIME_MAX;
 2860   tor_assert_nonfatal(voting_schedule.voting_starts);
 2861   /* If we haven't initialized this object through this codeflow, we need to
 2862    * recalculate the timings to match our vote. The reason to do that is if we
 2863    * have a voting schedule initialized 1 minute ago, the voting timings might
 2864    * not be aligned to what we should expect with "now". This is especially
 2865    * true for TestingTorNetwork using smaller timings.  */
 2866   if (voting_schedule.created_on_demand) {
 2867     char *keys = list_v3_auth_ids();
 2868     authority_cert_t *c = get_my_v3_authority_cert();
 2869     log_notice(LD_DIR, "Scheduling voting.  Known authority IDs are %s. "
 2870                "Mine is %s.",
 2871                keys, hex_str(c->cache_info.identity_digest, DIGEST_LEN));
 2872     tor_free(keys);
 2873     voting_schedule_recalculate_timing(options, now);
 2874   }
 2875 
 2876 #define IF_TIME_FOR_NEXT_ACTION(when_field, done_field) \
 2877   if (! voting_schedule.done_field) {                   \
 2878     if (voting_schedule.when_field > now) {             \
 2879       return voting_schedule.when_field;                \
 2880     } else {
 2881 #define ENDIF \
 2882     }           \
 2883   }
 2884 
 2885   IF_TIME_FOR_NEXT_ACTION(voting_starts, have_voted) {
 2886     log_notice(LD_DIR, "Time to vote.");
 2887     dirvote_perform_vote();
 2888     voting_schedule.have_voted = 1;
 2889   } ENDIF
 2890   IF_TIME_FOR_NEXT_ACTION(fetch_missing_votes, have_fetched_missing_votes) {
 2891     log_notice(LD_DIR, "Time to fetch any votes that we're missing.");
 2892     dirvote_fetch_missing_votes();
 2893     voting_schedule.have_fetched_missing_votes = 1;
 2894   } ENDIF
 2895   IF_TIME_FOR_NEXT_ACTION(voting_ends, have_built_consensus) {
 2896     log_notice(LD_DIR, "Time to compute a consensus.");
 2897     dirvote_compute_consensuses();
 2898     /* XXXX We will want to try again later if we haven't got enough
 2899      * votes yet.  Implement this if it turns out to ever happen. */
 2900     voting_schedule.have_built_consensus = 1;
 2901   } ENDIF
 2902   IF_TIME_FOR_NEXT_ACTION(fetch_missing_signatures,
 2903                           have_fetched_missing_signatures) {
 2904     log_notice(LD_DIR, "Time to fetch any signatures that we're missing.");
 2905     dirvote_fetch_missing_signatures();
 2906     voting_schedule.have_fetched_missing_signatures = 1;
 2907   } ENDIF
 2908   IF_TIME_FOR_NEXT_ACTION(interval_starts,
 2909                           have_published_consensus) {
 2910     log_notice(LD_DIR, "Time to publish the consensus and discard old votes");
 2911     dirvote_publish_consensus();
 2912     dirvote_clear_votes(0);
 2913     voting_schedule.have_published_consensus = 1;
 2914     /* Update our shared random state with the consensus just published. */
 2915     sr_act_post_consensus(
 2916                 networkstatus_get_latest_consensus_by_flavor(FLAV_NS));
 2917     /* XXXX We will want to try again later if we haven't got enough
 2918      * signatures yet.  Implement this if it turns out to ever happen. */
 2919     voting_schedule_recalculate_timing(options, now);
 2920     return voting_schedule.voting_starts;
 2921   } ENDIF
 2922 
 2923   tor_assert_nonfatal_unreached();
 2924   return now + 1;
 2925 
 2926 #undef ENDIF
 2927 #undef IF_TIME_FOR_NEXT_ACTION
 2928 }
 2929 
 2930 /** A vote networkstatus_t and its unparsed body: held around so we can
 2931  * use it to generate a consensus (at voting_ends) and so we can serve it to
 2932  * other authorities that might want it. */
 2933 typedef struct pending_vote_t {
 2934   cached_dir_t *vote_body;
 2935   networkstatus_t *vote;
 2936 } pending_vote_t;
 2937 
 2938 /** List of pending_vote_t for the current vote.  Before we've used them to
 2939  * build a consensus, the votes go here. */
 2940 static smartlist_t *pending_vote_list = NULL;
 2941 /** List of pending_vote_t for the previous vote.  After we've used them to
 2942  * build a consensus, the votes go here for the next period. */
 2943 static smartlist_t *previous_vote_list = NULL;
 2944 
 2945 /* DOCDOC pending_consensuses */
 2946 static pending_consensus_t pending_consensuses[N_CONSENSUS_FLAVORS];
 2947 
 2948 /** The detached signatures for the consensus that we're currently
 2949  * building. */
 2950 static char *pending_consensus_signatures = NULL;
 2951 
 2952 /** List of ns_detached_signatures_t: hold signatures that get posted to us
 2953  * before we have generated the consensus on our own. */
 2954 static smartlist_t *pending_consensus_signature_list = NULL;
 2955 
 2956 /** Generate a networkstatus vote and post it to all the v3 authorities.
 2957  * (V3 Authority only) */
 2958 static int
 2959 dirvote_perform_vote(void)
 2960 {
 2961   crypto_pk_t *key = get_my_v3_authority_signing_key();
 2962   authority_cert_t *cert = get_my_v3_authority_cert();
 2963   networkstatus_t *ns;
 2964   char *contents;
 2965   pending_vote_t *pending_vote;
 2966   time_t now = time(NULL);
 2967 
 2968   int status;
 2969   const char *msg = "";
 2970 
 2971   if (!cert || !key) {
 2972     log_warn(LD_NET, "Didn't find key/certificate to generate v3 vote");
 2973     return -1;
 2974   } else if (cert->expires < now) {
 2975     log_warn(LD_NET, "Can't generate v3 vote with expired certificate");
 2976     return -1;
 2977   }
 2978   if (!(ns = dirserv_generate_networkstatus_vote_obj(key, cert)))
 2979     return -1;
 2980 
 2981   contents = format_networkstatus_vote(key, ns);
 2982   networkstatus_vote_free(ns);
 2983   if (!contents)
 2984     return -1;
 2985 
 2986   pending_vote = dirvote_add_vote(contents, &msg, &status);
 2987   tor_free(contents);
 2988   if (!pending_vote) {
 2989     log_warn(LD_DIR, "Couldn't store my own vote! (I told myself, '%s'.)",
 2990              msg);
 2991     return -1;
 2992   }
 2993 
 2994   directory_post_to_dirservers(DIR_PURPOSE_UPLOAD_VOTE,
 2995                                ROUTER_PURPOSE_GENERAL,
 2996                                V3_DIRINFO,
 2997                                pending_vote->vote_body->dir,
 2998                                pending_vote->vote_body->dir_len, 0);
 2999   log_notice(LD_DIR, "Vote posted.");
 3000   return 0;
 3001 }
 3002 
 3003 /** Send an HTTP request to every other v3 authority, for the votes of every
 3004  * authority for which we haven't received a vote yet in this period. (V3
 3005  * authority only) */
 3006 static void
 3007 dirvote_fetch_missing_votes(void)
 3008 {
 3009   smartlist_t *missing_fps = smartlist_new();
 3010   char *resource;
 3011 
 3012   SMARTLIST_FOREACH_BEGIN(router_get_trusted_dir_servers(),
 3013                           dir_server_t *, ds) {
 3014       if (!(ds->type & V3_DIRINFO))
 3015         continue;
 3016       if (!dirvote_get_vote(ds->v3_identity_digest,
 3017                             DGV_BY_ID|DGV_INCLUDE_PENDING)) {
 3018         char *cp = tor_malloc(HEX_DIGEST_LEN+1);
 3019         base16_encode(cp, HEX_DIGEST_LEN+1, ds->v3_identity_digest,
 3020                       DIGEST_LEN);
 3021         smartlist_add(missing_fps, cp);
 3022       }
 3023   } SMARTLIST_FOREACH_END(ds);
 3024 
 3025   if (!smartlist_len(missing_fps)) {
 3026     smartlist_free(missing_fps);
 3027     return;
 3028   }
 3029   {
 3030     char *tmp = smartlist_join_strings(missing_fps, " ", 0, NULL);
 3031     log_notice(LOG_NOTICE, "We're missing votes from %d authorities (%s). "
 3032                "Asking every other authority for a copy.",
 3033                smartlist_len(missing_fps), tmp);
 3034     tor_free(tmp);
 3035   }
 3036   resource = smartlist_join_strings(missing_fps, "+", 0, NULL);
 3037   directory_get_from_all_authorities(DIR_PURPOSE_FETCH_STATUS_VOTE,
 3038                                      0, resource);
 3039   tor_free(resource);
 3040   SMARTLIST_FOREACH(missing_fps, char *, cp, tor_free(cp));
 3041   smartlist_free(missing_fps);
 3042 }
 3043 
 3044 /** Send a request to every other authority for its detached signatures,
 3045  * unless we have signatures from all other v3 authorities already. */
 3046 static void
 3047 dirvote_fetch_missing_signatures(void)
 3048 {
 3049   int need_any = 0;
 3050   int i;
 3051   for (i=0; i < N_CONSENSUS_FLAVORS; ++i) {
 3052     networkstatus_t *consensus = pending_consensuses[i].consensus;
 3053     if (!consensus ||
 3054         networkstatus_check_consensus_signature(consensus, -1) == 1) {
 3055       /* We have no consensus, or we have one that's signed by everybody. */
 3056       continue;
 3057     }
 3058     need_any = 1;
 3059   }
 3060   if (!need_any)
 3061     return;
 3062 
 3063   directory_get_from_all_authorities(DIR_PURPOSE_FETCH_DETACHED_SIGNATURES,
 3064                                      0, NULL);
 3065 }
 3066 
 3067 /** Release all storage held by pending consensuses (those waiting for
 3068  * signatures). */
 3069 static void
 3070 dirvote_clear_pending_consensuses(void)
 3071 {
 3072   int i;
 3073   for (i = 0; i < N_CONSENSUS_FLAVORS; ++i) {
 3074     pending_consensus_t *pc = &pending_consensuses[i];
 3075     tor_free(pc->body);
 3076 
 3077     networkstatus_vote_free(pc->consensus);
 3078     pc->consensus = NULL;
 3079   }
 3080 }
 3081 
 3082 /** Drop all currently pending votes, consensus, and detached signatures. */
 3083 static void
 3084 dirvote_clear_votes(int all_votes)
 3085 {
 3086   if (!previous_vote_list)
 3087     previous_vote_list = smartlist_new();
 3088   if (!pending_vote_list)
 3089     pending_vote_list = smartlist_new();
 3090 
 3091   /* All "previous" votes are now junk. */
 3092   SMARTLIST_FOREACH(previous_vote_list, pending_vote_t *, v, {
 3093       cached_dir_decref(v->vote_body);
 3094       v->vote_body = NULL;
 3095       networkstatus_vote_free(v->vote);
 3096       tor_free(v);
 3097     });
 3098   smartlist_clear(previous_vote_list);
 3099 
 3100   if (all_votes) {
 3101     /* If we're dumping all the votes, we delete the pending ones. */
 3102     SMARTLIST_FOREACH(pending_vote_list, pending_vote_t *, v, {
 3103         cached_dir_decref(v->vote_body);
 3104         v->vote_body = NULL;
 3105         networkstatus_vote_free(v->vote);
 3106         tor_free(v);
 3107       });
 3108   } else {
 3109     /* Otherwise, we move them into "previous". */
 3110     smartlist_add_all(previous_vote_list, pending_vote_list);
 3111   }
 3112   smartlist_clear(pending_vote_list);
 3113 
 3114   if (pending_consensus_signature_list) {
 3115     SMARTLIST_FOREACH(pending_consensus_signature_list, char *, cp,
 3116                       tor_free(cp));
 3117     smartlist_clear(pending_consensus_signature_list);
 3118   }
 3119   tor_free(pending_consensus_signatures);
 3120   dirvote_clear_pending_consensuses();
 3121 }
 3122 
 3123 /** Return a newly allocated string containing the hex-encoded v3 authority
 3124     identity digest of every recognized v3 authority. */
 3125 static char *
 3126 list_v3_auth_ids(void)
 3127 {
 3128   smartlist_t *known_v3_keys = smartlist_new();
 3129   char *keys;
 3130   SMARTLIST_FOREACH(router_get_trusted_dir_servers(),
 3131                     dir_server_t *, ds,
 3132     if ((ds->type & V3_DIRINFO) &&
 3133         !tor_digest_is_zero(ds->v3_identity_digest))
 3134       smartlist_add(known_v3_keys,
 3135                     tor_strdup(hex_str(ds->v3_identity_digest, DIGEST_LEN))));
 3136   keys = smartlist_join_strings(known_v3_keys, ", ", 0, NULL);
 3137   SMARTLIST_FOREACH(known_v3_keys, char *, cp, tor_free(cp));
 3138   smartlist_free(known_v3_keys);
 3139   return keys;
 3140 }
 3141 
 3142 /** Called when we have received a networkstatus vote in <b>vote_body</b>.
 3143  * Parse and validate it, and on success store it as a pending vote (which we
 3144  * then return).  Return NULL on failure.  Sets *<b>msg_out</b> and
 3145  * *<b>status_out</b> to an HTTP response and status code.  (V3 authority
 3146  * only) */
 3147 pending_vote_t *
 3148 dirvote_add_vote(const char *vote_body, const char **msg_out, int *status_out)
 3149 {
 3150   networkstatus_t *vote;
 3151   networkstatus_voter_info_t *vi;
 3152   dir_server_t *ds;
 3153   pending_vote_t *pending_vote = NULL;
 3154   const char *end_of_vote = NULL;
 3155   int any_failed = 0;
 3156   tor_assert(vote_body);
 3157   tor_assert(msg_out);
 3158   tor_assert(status_out);
 3159 
 3160   if (!pending_vote_list)
 3161     pending_vote_list = smartlist_new();
 3162   *status_out = 0;
 3163   *msg_out = NULL;
 3164 
 3165  again:
 3166   vote = networkstatus_parse_vote_from_string(vote_body, strlen(vote_body),
 3167                                               &end_of_vote,
 3168                                               NS_TYPE_VOTE);
 3169   if (!end_of_vote)
 3170     end_of_vote = vote_body + strlen(vote_body);
 3171   if (!vote) {
 3172     log_warn(LD_DIR, "Couldn't parse vote: length was %d",
 3173              (int)strlen(vote_body));
 3174     *msg_out = "Unable to parse vote";
 3175     goto err;
 3176   }
 3177   tor_assert(smartlist_len(vote->voters) == 1);
 3178   vi = get_voter(vote);
 3179   {
 3180     int any_sig_good = 0;
 3181     SMARTLIST_FOREACH(vi->sigs, document_signature_t *, sig,
 3182                       if (sig->good_signature)
 3183                         any_sig_good = 1);
 3184     tor_assert(any_sig_good);
 3185   }
 3186   ds = trusteddirserver_get_by_v3_auth_digest(vi->identity_digest);
 3187   if (!ds) {
 3188     char *keys = list_v3_auth_ids();
 3189     log_warn(LD_DIR, "Got a vote from an authority (nickname %s, address %s) "
 3190              "with authority key ID %s. "
 3191              "This key ID is not recognized.  Known v3 key IDs are: %s",
 3192              vi->nickname, vi->address,
 3193              hex_str(vi->identity_digest, DIGEST_LEN), keys);
 3194     tor_free(keys);
 3195     *msg_out = "Vote not from a recognized v3 authority";
 3196     goto err;
 3197   }
 3198   tor_assert(vote->cert);
 3199   if (!authority_cert_get_by_digests(vote->cert->cache_info.identity_digest,
 3200                                      vote->cert->signing_key_digest)) {
 3201     /* Hey, it's a new cert! */
 3202     trusted_dirs_load_certs_from_string(
 3203                                vote->cert->cache_info.signed_descriptor_body,
 3204                                TRUSTED_DIRS_CERTS_SRC_FROM_VOTE, 1 /*flush*/,
 3205                                NULL);
 3206     if (!authority_cert_get_by_digests(vote->cert->cache_info.identity_digest,
 3207                                        vote->cert->signing_key_digest)) {
 3208       log_warn(LD_BUG, "We added a cert, but still couldn't find it.");
 3209     }
 3210   }
 3211 
 3212   /* Is it for the right period? */
 3213   if (vote->valid_after != voting_schedule.interval_starts) {
 3214     char tbuf1[ISO_TIME_LEN+1], tbuf2[ISO_TIME_LEN+1];
 3215     format_iso_time(tbuf1, vote->valid_after);
 3216     format_iso_time(tbuf2, voting_schedule.interval_starts);
 3217     log_warn(LD_DIR, "Rejecting vote from %s with valid-after time of %s; "
 3218              "we were expecting %s", vi->address, tbuf1, tbuf2);
 3219     *msg_out = "Bad valid-after time";
 3220     goto err;
 3221   }
 3222 
 3223   /* Fetch any new router descriptors we just learned about */
 3224   update_consensus_router_descriptor_downloads(time(NULL), 1, vote);
 3225 
 3226   /* Now see whether we already have a vote from this authority. */
 3227   SMARTLIST_FOREACH_BEGIN(pending_vote_list, pending_vote_t *, v) {
 3228       if (fast_memeq(v->vote->cert->cache_info.identity_digest,
 3229                    vote->cert->cache_info.identity_digest,
 3230                    DIGEST_LEN)) {
 3231         networkstatus_voter_info_t *vi_old = get_voter(v->vote);
 3232         if (fast_memeq(vi_old->vote_digest, vi->vote_digest, DIGEST_LEN)) {
 3233           /* Ah, it's the same vote. Not a problem. */
 3234           log_info(LD_DIR, "Discarding a vote we already have (from %s).",
 3235                    vi->address);
 3236           if (*status_out < 200)
 3237             *status_out = 200;
 3238           goto discard;
 3239         } else if (v->vote->published < vote->published) {
 3240           log_notice(LD_DIR, "Replacing an older pending vote from this "
 3241                      "directory (%s)", vi->address);
 3242           cached_dir_decref(v->vote_body);
 3243           networkstatus_vote_free(v->vote);
 3244           v->vote_body = new_cached_dir(tor_strndup(vote_body,
 3245                                                     end_of_vote-vote_body),
 3246                                         vote->published);
 3247           v->vote = vote;
 3248           if (end_of_vote &&
 3249               !strcmpstart(end_of_vote, "network-status-version"))
 3250             goto again;
 3251 
 3252           if (*status_out < 200)
 3253             *status_out = 200;
 3254           if (!*msg_out)
 3255             *msg_out = "OK";
 3256           return v;
 3257         } else {
 3258           *msg_out = "Already have a newer pending vote";
 3259           goto err;
 3260         }
 3261       }
 3262   } SMARTLIST_FOREACH_END(v);
 3263 
 3264   /* This a valid vote, update our shared random state. */
 3265   sr_handle_received_commits(vote->sr_info.commits,
 3266                              vote->cert->identity_key);
 3267 
 3268   pending_vote = tor_malloc_zero(sizeof(pending_vote_t));
 3269   pending_vote->vote_body = new_cached_dir(tor_strndup(vote_body,
 3270                                                        end_of_vote-vote_body),
 3271                                            vote->published);
 3272   pending_vote->vote = vote;
 3273   smartlist_add(pending_vote_list, pending_vote);
 3274 
 3275   if (!strcmpstart(end_of_vote, "network-status-version ")) {
 3276     vote_body = end_of_vote;
 3277     goto again;
 3278   }
 3279 
 3280   goto done;
 3281 
 3282  err:
 3283   any_failed = 1;
 3284   if (!*msg_out)
 3285     *msg_out = "Error adding vote";
 3286   if (*status_out < 400)
 3287     *status_out = 400;
 3288 
 3289  discard:
 3290   networkstatus_vote_free(vote);
 3291 
 3292   if (end_of_vote && !strcmpstart(end_of_vote, "network-status-version ")) {
 3293     vote_body = end_of_vote;
 3294     goto again;
 3295   }
 3296 
 3297  done:
 3298 
 3299   if (*status_out < 200)
 3300     *status_out = 200;
 3301   if (!*msg_out) {
 3302     if (!any_failed && !pending_vote) {
 3303       *msg_out = "Duplicate discarded";
 3304     } else {
 3305       *msg_out = "ok";
 3306     }
 3307   }
 3308 
 3309   return any_failed ? NULL : pending_vote;
 3310 }
 3311 
 3312 /* Write the votes in <b>pending_vote_list</b> to disk. */
 3313 static void
 3314 write_v3_votes_to_disk(const smartlist_t *pending_votes)
 3315 {
 3316   smartlist_t *votestrings = smartlist_new();
 3317   char *votefile = NULL;
 3318 
 3319   SMARTLIST_FOREACH(pending_votes, pending_vote_t *, v,
 3320     {
 3321       sized_chunk_t *c = tor_malloc(sizeof(sized_chunk_t));
 3322       c->bytes = v->vote_body->dir;
 3323       c->len = v->vote_body->dir_len;
 3324       smartlist_add(votestrings, c); /* collect strings to write to disk */
 3325     });
 3326 
 3327   votefile = get_datadir_fname("v3-status-votes");
 3328   write_chunks_to_file(votefile, votestrings, 0, 0);
 3329   log_debug(LD_DIR, "Wrote votes to disk (%s)!", votefile);
 3330 
 3331   tor_free(votefile);
 3332   SMARTLIST_FOREACH(votestrings, sized_chunk_t *, c, tor_free(c));
 3333   smartlist_free(votestrings);
 3334 }
 3335 
 3336 /** Try to compute a v3 networkstatus consensus from the currently pending
 3337  * votes.  Return 0 on success, -1 on failure.  Store the consensus in
 3338  * pending_consensus: it won't be ready to be published until we have
 3339  * everybody else's signatures collected too. (V3 Authority only) */
 3340 static int
 3341 dirvote_compute_consensuses(void)
 3342 {
 3343   /* Have we got enough votes to try? */
 3344   int n_votes, n_voters, n_vote_running = 0;
 3345   smartlist_t *votes = NULL;
 3346   char *consensus_body = NULL, *signatures = NULL;
 3347   networkstatus_t *consensus = NULL;
 3348   authority_cert_t *my_cert;
 3349   pending_consensus_t pending[N_CONSENSUS_FLAVORS];
 3350   int flav;
 3351 
 3352   memset(pending, 0, sizeof(pending));
 3353 
 3354   if (!pending_vote_list)
 3355     pending_vote_list = smartlist_new();
 3356 
 3357   /* Write votes to disk */
 3358   write_v3_votes_to_disk(pending_vote_list);
 3359 
 3360   /* Setup votes smartlist */
 3361   votes = smartlist_new();
 3362   SMARTLIST_FOREACH(pending_vote_list, pending_vote_t *, v,
 3363     {
 3364       smartlist_add(votes, v->vote); /* collect votes to compute consensus */
 3365     });
 3366 
 3367   /* See if consensus managed to achieve majority */
 3368   n_voters = get_n_authorities(V3_DIRINFO);
 3369   n_votes = smartlist_len(pending_vote_list);
 3370   if (n_votes <= n_voters/2) {
 3371     log_warn(LD_DIR, "We don't have enough votes to generate a consensus: "
 3372              "%d of %d", n_votes, n_voters/2+1);
 3373     goto err;
 3374   }
 3375   tor_assert(pending_vote_list);
 3376   SMARTLIST_FOREACH(pending_vote_list, pending_vote_t *, v, {
 3377     if (smartlist_contains_string(v->vote->known_flags, "Running"))
 3378       n_vote_running++;
 3379   });
 3380   if (!n_vote_running) {
 3381     /* See task 1066. */
 3382     log_warn(LD_DIR, "Nobody has voted on the Running flag. Generating "
 3383                      "and publishing a consensus without Running nodes "
 3384                      "would make many clients stop working. Not "
 3385                      "generating a consensus!");
 3386     goto err;
 3387   }
 3388 
 3389   if (!(my_cert = get_my_v3_authority_cert())) {
 3390     log_warn(LD_DIR, "Can't generate consensus without a certificate.");
 3391     goto err;
 3392   }
 3393 
 3394   {
 3395     char legacy_dbuf[DIGEST_LEN];
 3396     crypto_pk_t *legacy_sign=NULL;
 3397     char *legacy_id_digest = NULL;
 3398     int n_generated = 0;
 3399     if (get_options()->V3AuthUseLegacyKey) {
 3400       authority_cert_t *cert = get_my_v3_legacy_cert();
 3401       legacy_sign = get_my_v3_legacy_signing_key();
 3402       if (cert) {
 3403         if (crypto_pk_get_digest(cert->identity_key, legacy_dbuf)) {
 3404           log_warn(LD_BUG,
 3405                    "Unable to compute digest of legacy v3 identity key");
 3406         } else {
 3407           legacy_id_digest = legacy_dbuf;
 3408         }
 3409       }
 3410     }
 3411 
 3412     for (flav = 0; flav < N_CONSENSUS_FLAVORS; ++flav) {
 3413       const char *flavor_name = networkstatus_get_flavor_name(flav);
 3414       consensus_body = networkstatus_compute_consensus(
 3415         votes, n_voters,
 3416         my_cert->identity_key,
 3417         get_my_v3_authority_signing_key(), legacy_id_digest, legacy_sign,
 3418         flav);
 3419 
 3420       if (!consensus_body) {
 3421         log_warn(LD_DIR, "Couldn't generate a %s consensus at all!",
 3422                  flavor_name);
 3423         continue;
 3424       }
 3425       consensus = networkstatus_parse_vote_from_string(consensus_body,
 3426                                                        strlen(consensus_body),
 3427                                                        NULL,
 3428                                                        NS_TYPE_CONSENSUS);
 3429       if (!consensus) {
 3430         log_warn(LD_DIR, "Couldn't parse %s consensus we generated!",
 3431                  flavor_name);
 3432         tor_free(consensus_body);
 3433         continue;
 3434       }
 3435 
 3436       /* 'Check' our own signature, to mark it valid. */
 3437       networkstatus_check_consensus_signature(consensus, -1);
 3438 
 3439       pending[flav].body = consensus_body;
 3440       pending[flav].consensus = consensus;
 3441       n_generated++;
 3442       consensus_body = NULL;
 3443       consensus = NULL;
 3444     }
 3445     if (!n_generated) {
 3446       log_warn(LD_DIR, "Couldn't generate any consensus flavors at all.");
 3447       goto err;
 3448     }
 3449   }
 3450 
 3451   signatures = get_detached_signatures_from_pending_consensuses(
 3452        pending, N_CONSENSUS_FLAVORS);
 3453 
 3454   if (!signatures) {
 3455     log_warn(LD_DIR, "Couldn't extract signatures.");
 3456     goto err;
 3457   }
 3458 
 3459   dirvote_clear_pending_consensuses();
 3460   memcpy(pending_consensuses, pending, sizeof(pending));
 3461 
 3462   tor_free(pending_consensus_signatures);
 3463   pending_consensus_signatures = signatures;
 3464 
 3465   if (pending_consensus_signature_list) {
 3466     int n_sigs = 0;
 3467     /* we may have gotten signatures for this consensus before we built
 3468      * it ourself.  Add them now. */
 3469     SMARTLIST_FOREACH_BEGIN(pending_consensus_signature_list, char *, sig) {
 3470         const char *msg = NULL;
 3471         int r = dirvote_add_signatures_to_all_pending_consensuses(sig,
 3472                                                      "pending", &msg);
 3473         if (r >= 0)
 3474           n_sigs += r;
 3475         else
 3476           log_warn(LD_DIR,
 3477                    "Could not add queued signature to new consensus: %s",
 3478                    msg);
 3479         tor_free(sig);
 3480     } SMARTLIST_FOREACH_END(sig);
 3481     if (n_sigs)
 3482       log_notice(LD_DIR, "Added %d pending signatures while building "
 3483                  "consensus.", n_sigs);
 3484     smartlist_clear(pending_consensus_signature_list);
 3485   }
 3486 
 3487   log_notice(LD_DIR, "Consensus computed; uploading signature(s)");
 3488 
 3489   directory_post_to_dirservers(DIR_PURPOSE_UPLOAD_SIGNATURES,
 3490                                ROUTER_PURPOSE_GENERAL,
 3491                                V3_DIRINFO,
 3492                                pending_consensus_signatures,
 3493                                strlen(pending_consensus_signatures), 0);
 3494   log_notice(LD_DIR, "Signature(s) posted.");
 3495 
 3496   smartlist_free(votes);
 3497   return 0;
 3498  err:
 3499   smartlist_free(votes);
 3500   tor_free(consensus_body);
 3501   tor_free(signatures);
 3502   networkstatus_vote_free(consensus);
 3503 
 3504   return -1;
 3505 }
 3506 
 3507 /** Helper: we just got the <b>detached_signatures_body</b> sent to us as
 3508  * signatures on the currently pending consensus.  Add them to <b>pc</b>
 3509  * as appropriate.  Return the number of signatures added. (?) */
 3510 static int
 3511 dirvote_add_signatures_to_pending_consensus(
 3512                        pending_consensus_t *pc,
 3513                        ns_detached_signatures_t *sigs,
 3514                        const char *source,
 3515                        int severity,
 3516                        const char **msg_out)
 3517 {
 3518   const char *flavor_name;
 3519   int r = -1;
 3520 
 3521   /* Only call if we have a pending consensus right now. */
 3522   tor_assert(pc->consensus);
 3523   tor_assert(pc->body);
 3524   tor_assert(pending_consensus_signatures);
 3525 
 3526   flavor_name = networkstatus_get_flavor_name(pc->consensus->flavor);
 3527   *msg_out = NULL;
 3528 
 3529   {
 3530     smartlist_t *sig_list = strmap_get(sigs->signatures, flavor_name);
 3531     log_info(LD_DIR, "Have %d signatures for adding to %s consensus.",
 3532              sig_list ? smartlist_len(sig_list) : 0, flavor_name);
 3533   }
 3534   r = networkstatus_add_detached_signatures(pc->consensus, sigs,
 3535                                             source, severity, msg_out);
 3536   if (r >= 0) {
 3537     log_info(LD_DIR,"Added %d signatures to consensus.", r);
 3538   } else {
 3539     log_fn(LOG_PROTOCOL_WARN, LD_DIR,
 3540            "Unable to add signatures to consensus: %s",
 3541            *msg_out ? *msg_out : "(unknown)");
 3542   }
 3543 
 3544   if (r >= 1) {
 3545     char *new_signatures =
 3546       networkstatus_format_signatures(pc->consensus, 0);
 3547     char *dst, *dst_end;
 3548     size_t new_consensus_len;
 3549     if (!new_signatures) {
 3550       *msg_out = "No signatures to add";
 3551       goto err;
 3552     }
 3553     new_consensus_len =
 3554       strlen(pc->body) + strlen(new_signatures) + 1;
 3555     pc->body = tor_realloc(pc->body, new_consensus_len);
 3556     dst_end = pc->body + new_consensus_len;
 3557     dst = strstr(pc->body, "directory-signature ");
 3558     tor_assert(dst);
 3559     strlcpy(dst, new_signatures, dst_end-dst);
 3560 
 3561     /* We remove this block once it has failed to crash for a while.  But
 3562      * unless it shows up in profiles, we're probably better leaving it in,
 3563      * just in case we break detached signature processing at some point. */
 3564     {
 3565       networkstatus_t *v = networkstatus_parse_vote_from_string(
 3566                                              pc->body, strlen(pc->body), NULL,
 3567                                              NS_TYPE_CONSENSUS);
 3568       tor_assert(v);
 3569       networkstatus_vote_free(v);
 3570     }
 3571     *msg_out = "Signatures added";
 3572     tor_free(new_signatures);
 3573   } else if (r == 0) {
 3574     *msg_out = "Signatures ignored";
 3575   } else {
 3576     goto err;
 3577   }
 3578 
 3579   goto done;
 3580  err:
 3581   if (!*msg_out)
 3582     *msg_out = "Unrecognized error while adding detached signatures.";
 3583  done:
 3584   return r;
 3585 }
 3586 
 3587 static int
 3588 dirvote_add_signatures_to_all_pending_consensuses(
 3589                        const char *detached_signatures_body,
 3590                        const char *source,
 3591                        const char **msg_out)
 3592 {
 3593   int r=0, i, n_added = 0, errors = 0;
 3594   ns_detached_signatures_t *sigs;
 3595   tor_assert(detached_signatures_body);
 3596   tor_assert(msg_out);
 3597   tor_assert(pending_consensus_signatures);
 3598 
 3599   if (!(sigs = networkstatus_parse_detached_signatures(
 3600                                detached_signatures_body, NULL))) {
 3601     *msg_out = "Couldn't parse detached signatures.";
 3602     goto err;
 3603   }
 3604 
 3605   for (i = 0; i < N_CONSENSUS_FLAVORS; ++i) {
 3606     int res;
 3607     int severity = i == FLAV_NS ? LOG_NOTICE : LOG_INFO;
 3608     pending_consensus_t *pc = &pending_consensuses[i];
 3609     if (!pc->consensus)
 3610       continue;
 3611     res = dirvote_add_signatures_to_pending_consensus(pc, sigs, source,
 3612                                                       severity, msg_out);
 3613     if (res < 0)
 3614       errors++;
 3615     else
 3616       n_added += res;
 3617   }
 3618 
 3619   if (errors && !n_added) {
 3620     r = -1;
 3621     goto err;
 3622   }
 3623 
 3624   if (n_added && pending_consensuses[FLAV_NS].consensus) {
 3625     char *new_detached =
 3626       get_detached_signatures_from_pending_consensuses(
 3627                       pending_consensuses, N_CONSENSUS_FLAVORS);
 3628     if (new_detached) {
 3629       tor_free(pending_consensus_signatures);
 3630       pending_consensus_signatures = new_detached;
 3631     }
 3632   }
 3633 
 3634   r = n_added;
 3635   goto done;
 3636  err:
 3637   if (!*msg_out)
 3638     *msg_out = "Unrecognized error while adding detached signatures.";
 3639  done:
 3640   ns_detached_signatures_free(sigs);
 3641   /* XXXX NM Check how return is used.  We can now have an error *and*
 3642      signatures added. */
 3643   return r;
 3644 }
 3645 
 3646 /** Helper: we just got the <b>detached_signatures_body</b> sent to us as
 3647  * signatures on the currently pending consensus.  Add them to the pending
 3648  * consensus (if we have one); otherwise queue them until we have a
 3649  * consensus.  Return negative on failure, nonnegative on success. */
 3650 int
 3651 dirvote_add_signatures(const char *detached_signatures_body,
 3652                        const char *source,
 3653                        const char **msg)
 3654 {
 3655   if (pending_consensuses[FLAV_NS].consensus) {
 3656     log_notice(LD_DIR, "Got a signature from %s. "
 3657                        "Adding it to the pending consensus.", source);
 3658     return dirvote_add_signatures_to_all_pending_consensuses(
 3659                                      detached_signatures_body, source, msg);
 3660   } else {
 3661     log_notice(LD_DIR, "Got a signature from %s. "
 3662                        "Queuing it for the next consensus.", source);
 3663     if (!pending_consensus_signature_list)
 3664       pending_consensus_signature_list = smartlist_new();
 3665     smartlist_add_strdup(pending_consensus_signature_list,
 3666                   detached_signatures_body);
 3667     *msg = "Signature queued";
 3668     return 0;
 3669   }
 3670 }
 3671 
 3672 /** Replace the consensus that we're currently serving with the one that we've
 3673  * been building. (V3 Authority only) */
 3674 static int
 3675 dirvote_publish_consensus(void)
 3676 {
 3677   int i;
 3678 
 3679   /* Now remember all the other consensuses as if we were a directory cache. */
 3680   for (i = 0; i < N_CONSENSUS_FLAVORS; ++i) {
 3681     pending_consensus_t *pending = &pending_consensuses[i];
 3682     const char *name;
 3683     name = networkstatus_get_flavor_name(i);
 3684     tor_assert(name);
 3685     if (!pending->consensus ||
 3686       networkstatus_check_consensus_signature(pending->consensus, 1)<0) {
 3687       log_warn(LD_DIR, "Not enough info to publish pending %s consensus",name);
 3688       continue;
 3689     }
 3690 
 3691     if (networkstatus_set_current_consensus(pending->body,
 3692                                             strlen(pending->body),
 3693                                             name, 0, NULL))
 3694       log_warn(LD_DIR, "Error publishing %s consensus", name);
 3695     else
 3696       log_notice(LD_DIR, "Published %s consensus", name);
 3697   }
 3698 
 3699   return 0;
 3700 }
 3701 
 3702 /** Release all static storage held in dirvote.c */
 3703 void
 3704 dirvote_free_all(void)
 3705 {
 3706   dirvote_clear_votes(1);
 3707   /* now empty as a result of dirvote_clear_votes(). */
 3708   smartlist_free(pending_vote_list);
 3709   pending_vote_list = NULL;
 3710   smartlist_free(previous_vote_list);
 3711   previous_vote_list = NULL;
 3712 
 3713   dirvote_clear_pending_consensuses();
 3714   tor_free(pending_consensus_signatures);
 3715   if (pending_consensus_signature_list) {
 3716     /* now empty as a result of dirvote_clear_votes(). */
 3717     smartlist_free(pending_consensus_signature_list);
 3718     pending_consensus_signature_list = NULL;
 3719   }
 3720 }
 3721 
 3722 /* ====
 3723  * Access to pending items.
 3724  * ==== */
 3725 
 3726 /** Return the body of the consensus that we're currently trying to build. */
 3727 MOCK_IMPL(const char *,
 3728 dirvote_get_pending_consensus, (consensus_flavor_t flav))
 3729 {
 3730   tor_assert(((int)flav) >= 0 && (int)flav < N_CONSENSUS_FLAVORS);
 3731   return pending_consensuses[flav].body;
 3732 }
 3733 
 3734 /** Return the signatures that we know for the consensus that we're currently
 3735  * trying to build. */
 3736 MOCK_IMPL(const char *,
 3737 dirvote_get_pending_detached_signatures, (void))
 3738 {
 3739   return pending_consensus_signatures;
 3740 }
 3741 
 3742 /** Return a given vote specified by <b>fp</b>.  If <b>by_id</b>, return the
 3743  * vote for the authority with the v3 authority identity key digest <b>fp</b>;
 3744  * if <b>by_id</b> is false, return the vote whose digest is <b>fp</b>.  If
 3745  * <b>fp</b> is NULL, return our own vote.  If <b>include_previous</b> is
 3746  * false, do not consider any votes for a consensus that's already been built.
 3747  * If <b>include_pending</b> is false, do not consider any votes for the
 3748  * consensus that's in progress.  May return NULL if we have no vote for the
 3749  * authority in question. */
 3750 const cached_dir_t *
 3751 dirvote_get_vote(const char *fp, int flags)
 3752 {
 3753   int by_id = flags & DGV_BY_ID;
 3754   const int include_pending = flags & DGV_INCLUDE_PENDING;
 3755   const int include_previous = flags & DGV_INCLUDE_PREVIOUS;
 3756 
 3757   if (!pending_vote_list && !previous_vote_list)
 3758     return NULL;
 3759   if (fp == NULL) {
 3760     authority_cert_t *c = get_my_v3_authority_cert();
 3761     if (c) {
 3762       fp = c->cache_info.identity_digest;
 3763       by_id = 1;
 3764     } else
 3765       return NULL;
 3766   }
 3767   if (by_id) {
 3768     if (pending_vote_list && include_pending) {
 3769       SMARTLIST_FOREACH(pending_vote_list, pending_vote_t *, pv,
 3770         if (fast_memeq(get_voter(pv->vote)->identity_digest, fp, DIGEST_LEN))
 3771           return pv->vote_body);
 3772     }
 3773     if (previous_vote_list && include_previous) {
 3774       SMARTLIST_FOREACH(previous_vote_list, pending_vote_t *, pv,
 3775         if (fast_memeq(get_voter(pv->vote)->identity_digest, fp, DIGEST_LEN))
 3776           return pv->vote_body);
 3777     }
 3778   } else {
 3779     if (pending_vote_list && include_pending) {
 3780       SMARTLIST_FOREACH(pending_vote_list, pending_vote_t *, pv,
 3781         if (fast_memeq(pv->vote->digests.d[DIGEST_SHA1], fp, DIGEST_LEN))
 3782           return pv->vote_body);
 3783     }
 3784     if (previous_vote_list && include_previous) {
 3785       SMARTLIST_FOREACH(previous_vote_list, pending_vote_t *, pv,
 3786         if (fast_memeq(pv->vote->digests.d[DIGEST_SHA1], fp, DIGEST_LEN))
 3787           return pv->vote_body);
 3788     }
 3789   }
 3790   return NULL;
 3791 }
 3792 
 3793 /** Construct and return a new microdescriptor from a routerinfo <b>ri</b>
 3794  * according to <b>consensus_method</b>.
 3795  **/
 3796 STATIC microdesc_t *
 3797 dirvote_create_microdescriptor(const routerinfo_t *ri, int consensus_method)
 3798 {
 3799   microdesc_t *result = NULL;
 3800   char *key = NULL, *summary = NULL, *family = NULL;
 3801   size_t keylen;
 3802   smartlist_t *chunks = smartlist_new();
 3803   char *output = NULL;
 3804   crypto_pk_t *rsa_pubkey = router_get_rsa_onion_pkey(ri->onion_pkey,
 3805                                                       ri->onion_pkey_len);
 3806 
 3807   if (crypto_pk_write_public_key_to_string(rsa_pubkey, &key, &keylen)<0)
 3808     goto done;
 3809   summary = policy_summarize(ri->exit_policy, AF_INET);
 3810   if (ri->declared_family)
 3811     family = smartlist_join_strings(ri->declared_family, " ", 0, NULL);
 3812 
 3813   smartlist_add_asprintf(chunks, "onion-key\n%s", key);
 3814 
 3815   if (ri->onion_curve25519_pkey) {
 3816     char kbuf[128];
 3817     base64_encode(kbuf, sizeof(kbuf),
 3818                   (const char*)ri->onion_curve25519_pkey->public_key,
 3819                   CURVE25519_PUBKEY_LEN, BASE64_ENCODE_MULTILINE);
 3820     smartlist_add_asprintf(chunks, "ntor-onion-key %s", kbuf);
 3821   }
 3822 
 3823   /* We originally put a lines in the micrdescriptors, but then we worked out
 3824    * that we needed them in the microdesc consensus. See #20916. */
 3825   if (consensus_method < MIN_METHOD_FOR_NO_A_LINES_IN_MICRODESC &&
 3826       !tor_addr_is_null(&ri->ipv6_addr) && ri->ipv6_orport)
 3827     smartlist_add_asprintf(chunks, "a %s\n",
 3828                            fmt_addrport(&ri->ipv6_addr, ri->ipv6_orport));
 3829 
 3830   if (family) {
 3831     if (consensus_method < MIN_METHOD_FOR_CANONICAL_FAMILIES_IN_MICRODESCS) {
 3832       smartlist_add_asprintf(chunks, "family %s\n", family);
 3833     } else {
 3834       const uint8_t *id = (const uint8_t *)ri->cache_info.identity_digest;
 3835       char *canonical_family = nodefamily_canonicalize(family, id, 0);
 3836       smartlist_add_asprintf(chunks, "family %s\n", canonical_family);
 3837       tor_free(canonical_family);
 3838     }
 3839   }
 3840 
 3841   if (summary && strcmp(summary, "reject 1-65535"))
 3842     smartlist_add_asprintf(chunks, "p %s\n", summary);
 3843 
 3844   if (ri->ipv6_exit_policy) {
 3845     /* XXXX+++ This doesn't match proposal 208, which says these should
 3846      * be taken unchanged from the routerinfo.  That's bogosity, IMO:
 3847      * the proposal should have said to do this instead.*/
 3848     char *p6 = write_short_policy(ri->ipv6_exit_policy);
 3849     if (p6 && strcmp(p6, "reject 1-65535"))
 3850       smartlist_add_asprintf(chunks, "p6 %s\n", p6);
 3851     tor_free(p6);
 3852   }
 3853 
 3854   {
 3855     char idbuf[ED25519_BASE64_LEN+1];
 3856     const char *keytype;
 3857     if (ri->cache_info.signing_key_cert &&
 3858         ri->cache_info.signing_key_cert->signing_key_included) {
 3859       keytype = "ed25519";
 3860       ed25519_public_to_base64(idbuf,
 3861                                &ri->cache_info.signing_key_cert->signing_key);
 3862     } else {
 3863       keytype = "rsa1024";
 3864       digest_to_base64(idbuf, ri->cache_info.identity_digest);
 3865     }
 3866     smartlist_add_asprintf(chunks, "id %s %s\n", keytype, idbuf);
 3867   }
 3868 
 3869   output = smartlist_join_strings(chunks, "", 0, NULL);
 3870 
 3871   {
 3872     smartlist_t *lst = microdescs_parse_from_string(output,
 3873                                                     output+strlen(output), 0,
 3874                                                     SAVED_NOWHERE, NULL);
 3875     if (smartlist_len(lst) != 1) {
 3876       log_warn(LD_DIR, "We generated a microdescriptor we couldn't parse.");
 3877       SMARTLIST_FOREACH(lst, microdesc_t *, md, microdesc_free(md));
 3878       smartlist_free(lst);
 3879       goto done;
 3880     }
 3881     result = smartlist_get(lst, 0);
 3882     smartlist_free(lst);
 3883   }
 3884 
 3885  done:
 3886   crypto_pk_free(rsa_pubkey);
 3887   tor_free(output);
 3888   tor_free(key);
 3889   tor_free(summary);
 3890   tor_free(family);
 3891   if (chunks) {
 3892     SMARTLIST_FOREACH(chunks, char *, cp, tor_free(cp));
 3893     smartlist_free(chunks);
 3894   }
 3895   return result;
 3896 }
 3897 
 3898 /** Format the appropriate vote line to describe the microdescriptor <b>md</b>
 3899  * in a consensus vote document.  Write it into the <b>out_len</b>-byte buffer
 3900  * in <b>out</b>.  Return -1 on failure and the number of characters written
 3901  * on success. */
 3902 static ssize_t
 3903 dirvote_format_microdesc_vote_line(char *out_buf, size_t out_buf_len,
 3904                                    const microdesc_t *md,
 3905                                    int consensus_method_low,
 3906                                    int consensus_method_high)
 3907 {
 3908   ssize_t ret = -1;
 3909   char d64[BASE64_DIGEST256_LEN+1];
 3910   char *microdesc_consensus_methods =
 3911     make_consensus_method_list(consensus_method_low,
 3912                                consensus_method_high,
 3913                                ",");
 3914   tor_assert(microdesc_consensus_methods);
 3915 
 3916   digest256_to_base64(d64, md->digest);
 3917 
 3918   if (tor_snprintf(out_buf, out_buf_len, "m %s sha256=%s\n",
 3919                    microdesc_consensus_methods, d64)<0)
 3920     goto out;
 3921 
 3922   ret = strlen(out_buf);
 3923 
 3924  out:
 3925   tor_free(microdesc_consensus_methods);
 3926   return ret;
 3927 }
 3928 
 3929 /** Array of start and end of consensus methods used for supported
 3930     microdescriptor formats. */
 3931 static const struct consensus_method_range_t {
 3932   int low;
 3933   int high;
 3934 } microdesc_consensus_methods[] = {
 3935   {MIN_SUPPORTED_CONSENSUS_METHOD, MIN_METHOD_FOR_NO_A_LINES_IN_MICRODESC - 1},
 3936   {MIN_METHOD_FOR_NO_A_LINES_IN_MICRODESC,
 3937    MIN_METHOD_FOR_CANONICAL_FAMILIES_IN_MICRODESCS - 1},
 3938   {MIN_METHOD_FOR_CANONICAL_FAMILIES_IN_MICRODESCS,
 3939    MAX_SUPPORTED_CONSENSUS_METHOD},
 3940   {-1, -1}
 3941 };
 3942 
 3943 /** Helper type used when generating the microdescriptor lines in a directory
 3944  * vote. */
 3945 typedef struct microdesc_vote_line_t {
 3946   int low;
 3947   int high;
 3948   microdesc_t *md;
 3949   struct microdesc_vote_line_t *next;
 3950 } microdesc_vote_line_t;
 3951 
 3952 /** Generate and return a linked list of all the lines that should appear to
 3953  * describe a router's microdescriptor versions in a directory vote.
 3954  * Add the generated microdescriptors to <b>microdescriptors_out</b>. */
 3955 vote_microdesc_hash_t *
 3956 dirvote_format_all_microdesc_vote_lines(const routerinfo_t *ri, time_t now,
 3957                                         smartlist_t *microdescriptors_out)
 3958 {
 3959   const struct consensus_method_range_t *cmr;
 3960   microdesc_vote_line_t *entries = NULL, *ep;
 3961   vote_microdesc_hash_t *result = NULL;
 3962 
 3963   /* Generate the microdescriptors. */
 3964   for (cmr = microdesc_consensus_methods;
 3965        cmr->low != -1 && cmr->high != -1;
 3966        cmr++) {
 3967     microdesc_t *md = dirvote_create_microdescriptor(ri, cmr->low);
 3968     if (md) {
 3969       microdesc_vote_line_t *e =
 3970         tor_malloc_zero(sizeof(microdesc_vote_line_t));
 3971       e->md = md;
 3972       e->low = cmr->low;
 3973       e->high = cmr->high;
 3974       e->next = entries;
 3975       entries = e;
 3976     }
 3977   }
 3978 
 3979   /* Compress adjacent identical ones */
 3980   for (ep = entries; ep; ep = ep->next) {
 3981     while (ep->next &&
 3982            fast_memeq(ep->md->digest, ep->next->md->digest, DIGEST256_LEN) &&
 3983            ep->low == ep->next->high + 1) {
 3984       microdesc_vote_line_t *next = ep->next;
 3985       ep->low = next->low;
 3986       microdesc_free(next->md);
 3987       ep->next = next->next;
 3988       tor_free(next);
 3989     }
 3990   }
 3991 
 3992   /* Format them into vote_microdesc_hash_t, and add to microdescriptors_out.*/
 3993   while ((ep = entries)) {
 3994     char buf[128];
 3995     vote_microdesc_hash_t *h;
 3996     if (dirvote_format_microdesc_vote_line(buf, sizeof(buf), ep->md,
 3997                                            ep->low, ep->high) >= 0) {
 3998       h = tor_malloc_zero(sizeof(vote_microdesc_hash_t));
 3999       h->microdesc_hash_line = tor_strdup(buf);
 4000       h->next = result;
 4001       result = h;
 4002       ep->md->last_listed = now;
 4003       smartlist_add(microdescriptors_out, ep->md);
 4004     }
 4005     entries = ep->next;
 4006     tor_free(ep);
 4007   }
 4008 
 4009   return result;
 4010 }
 4011 
 4012 /** Parse and extract all SR commits from <b>tokens</b> and place them in
 4013  *  <b>ns</b>. */
 4014 static void
 4015 extract_shared_random_commits(networkstatus_t *ns, const smartlist_t *tokens)
 4016 {
 4017   smartlist_t *chunks = NULL;
 4018 
 4019   tor_assert(ns);
 4020   tor_assert(tokens);
 4021   /* Commits are only present in a vote. */
 4022   tor_assert(ns->type == NS_TYPE_VOTE);
 4023 
 4024   ns->sr_info.commits = smartlist_new();
 4025 
 4026   smartlist_t *commits = find_all_by_keyword(tokens, K_COMMIT);
 4027   /* It's normal that a vote might contain no commits even if it participates
 4028    * in the SR protocol. Don't treat it as an error. */
 4029   if (commits == NULL) {
 4030     goto end;
 4031   }
 4032 
 4033   /* Parse the commit. We do NO validation of number of arguments or ordering
 4034    * for forward compatibility, it's the parse commit job to inform us if it's
 4035    * supported or not. */
 4036   chunks = smartlist_new();
 4037   SMARTLIST_FOREACH_BEGIN(commits, directory_token_t *, tok) {
 4038     /* Extract all arguments and put them in the chunks list. */
 4039     for (int i = 0; i < tok->n_args; i++) {
 4040       smartlist_add(chunks, tok->args[i]);
 4041     }
 4042     sr_commit_t *commit = sr_parse_commit(chunks);
 4043     smartlist_clear(chunks);
 4044     if (commit == NULL) {
 4045       /* Get voter identity so we can warn that this dirauth vote contains
 4046        * commit we can't parse. */
 4047       networkstatus_voter_info_t *voter = smartlist_get(ns->voters, 0);
 4048       tor_assert(voter);
 4049       log_warn(LD_DIR, "SR: Unable to parse commit %s from vote of voter %s.",
 4050                escaped(tok->object_body),
 4051                hex_str(voter->identity_digest,
 4052                        sizeof(voter->identity_digest)));
 4053       /* Commitment couldn't be parsed. Continue onto the next commit because
 4054        * this one could be unsupported for instance. */
 4055       continue;
 4056     }
 4057     /* Add newly created commit object to the vote. */
 4058     smartlist_add(ns->sr_info.commits, commit);
 4059   } SMARTLIST_FOREACH_END(tok);
 4060 
 4061  end:
 4062   smartlist_free(chunks);
 4063   smartlist_free(commits);
 4064 }
 4065 
 4066 /* Using the given directory tokens in tokens, parse the shared random commits
 4067  * and put them in the given vote document ns.
 4068  *
 4069  * This also sets the SR participation flag if present in the vote. */
 4070 void
 4071 dirvote_parse_sr_commits(networkstatus_t *ns, const smartlist_t *tokens)
 4072 {
 4073   /* Does this authority participates in the SR protocol? */
 4074   directory_token_t *tok = find_opt_by_keyword(tokens, K_SR_FLAG);
 4075   if (tok) {
 4076     ns->sr_info.participate = 1;
 4077     /* Get the SR commitments and reveals from the vote. */
 4078     extract_shared_random_commits(ns, tokens);
 4079   }
 4080 }
 4081 
 4082 /* For the given vote, free the shared random commits if any. */
 4083 void
 4084 dirvote_clear_commits(networkstatus_t *ns)
 4085 {
 4086   tor_assert(ns->type == NS_TYPE_VOTE);
 4087 
 4088   if (ns->sr_info.commits) {
 4089     SMARTLIST_FOREACH(ns->sr_info.commits, sr_commit_t *, c,
 4090                       sr_commit_free(c));
 4091     smartlist_free(ns->sr_info.commits);
 4092   }
 4093 }
 4094 
 4095 /* The given url is the /tor/status-vote GET directory request. Populates the
 4096  * items list with strings that we can compress on the fly and dir_items with
 4097  * cached_dir_t objects that have a precompressed deflated version. */
 4098 void
 4099 dirvote_dirreq_get_status_vote(const char *url, smartlist_t *items,
 4100                                smartlist_t *dir_items)
 4101 {
 4102   int current;
 4103 
 4104   url += strlen("/tor/status-vote/");
 4105   current = !strcmpstart(url, "current/");
 4106   url = strchr(url, '/');
 4107   tor_assert(url);
 4108   ++url;
 4109   if (!strcmp(url, "consensus")) {
 4110     const char *item;
 4111     tor_assert(!current); /* we handle current consensus specially above,
 4112                            * since it wants to be spooled. */
 4113     if ((item = dirvote_get_pending_consensus(FLAV_NS)))
 4114       smartlist_add(items, (char*)item);
 4115   } else if (!current && !strcmp(url, "consensus-signatures")) {
 4116     /* XXXX the spec says that we should implement
 4117      * current/consensus-signatures too.  It doesn't seem to be needed,
 4118      * though. */
 4119     const char *item;
 4120     if ((item=dirvote_get_pending_detached_signatures()))
 4121       smartlist_add(items, (char*)item);
 4122   } else if (!strcmp(url, "authority")) {
 4123     const cached_dir_t *d;
 4124     int flags = DGV_BY_ID |
 4125       (current ? DGV_INCLUDE_PREVIOUS : DGV_INCLUDE_PENDING);
 4126     if ((d=dirvote_get_vote(NULL, flags)))
 4127       smartlist_add(dir_items, (cached_dir_t*)d);
 4128   } else {
 4129     const cached_dir_t *d;
 4130     smartlist_t *fps = smartlist_new();
 4131     int flags;
 4132     if (!strcmpstart(url, "d/")) {
 4133       url += 2;
 4134       flags = DGV_INCLUDE_PENDING | DGV_INCLUDE_PREVIOUS;
 4135     } else {
 4136       flags = DGV_BY_ID |
 4137         (current ? DGV_INCLUDE_PREVIOUS : DGV_INCLUDE_PENDING);
 4138     }
 4139     dir_split_resource_into_fingerprints(url, fps, NULL,
 4140                                          DSR_HEX|DSR_SORT_UNIQ);
 4141     SMARTLIST_FOREACH(fps, char *, fp, {
 4142                       if ((d = dirvote_get_vote(fp, flags)))
 4143                       smartlist_add(dir_items, (cached_dir_t*)d);
 4144                       tor_free(fp);
 4145                       });
 4146     smartlist_free(fps);
 4147   }
 4148 }
 4149 
 4150 /** Get the best estimate of a router's bandwidth for dirauth purposes,
 4151  * preferring measured to advertised values if available. */
 4152 static uint32_t
 4153 dirserv_get_bandwidth_for_router_kb(const routerinfo_t *ri)
 4154 {
 4155   uint32_t bw_kb = 0;
 4156   /*
 4157    * Yeah, measured bandwidths in measured_bw_line_t are (implicitly
 4158    * signed) longs and the ones router_get_advertised_bandwidth() returns
 4159    * are uint32_t.
 4160    */
 4161   long mbw_kb = 0;
 4162 
 4163   if (ri) {
 4164     /*
 4165      * * First try to see if we have a measured bandwidth; don't bother with
 4166      * as_of_out here, on the theory that a stale measured bandwidth is still
 4167      * better to trust than an advertised one.
 4168      */
 4169     if (dirserv_query_measured_bw_cache_kb(ri->cache_info.identity_digest,
 4170                                            &mbw_kb, NULL)) {
 4171       /* Got one! */
 4172       bw_kb = (uint32_t)mbw_kb;
 4173     } else {
 4174       /* If not, fall back to advertised */
 4175       bw_kb = router_get_advertised_bandwidth(ri) / 1000;
 4176     }
 4177   }
 4178 
 4179   return bw_kb;
 4180 }
 4181 
 4182 /** Helper for sorting: compares two routerinfos first by address, and then by
 4183  * descending order of "usefulness".  (An authority is more useful than a
 4184  * non-authority; a running router is more useful than a non-running router;
 4185  * and a router with more bandwidth is more useful than one with less.)
 4186  **/
 4187 static int
 4188 compare_routerinfo_by_ip_and_bw_(const void **a, const void **b)
 4189 {
 4190   routerinfo_t *first = *(routerinfo_t **)a, *second = *(routerinfo_t **)b;
 4191   int first_is_auth, second_is_auth;
 4192   uint32_t bw_kb_first, bw_kb_second;
 4193   const node_t *node_first, *node_second;
 4194   int first_is_running, second_is_running;
 4195 
 4196   /* we return -1 if first should appear before second... that is,
 4197    * if first is a better router. */
 4198   if (first->addr < second->addr)
 4199     return -1;
 4200   else if (first->addr > second->addr)
 4201     return 1;
 4202 
 4203   /* Potentially, this next bit could cause k n lg n memeq calls.  But in
 4204    * reality, we will almost never get here, since addresses will usually be
 4205    * different. */
 4206 
 4207   first_is_auth =
 4208     router_digest_is_trusted_dir(first->cache_info.identity_digest);
 4209   second_is_auth =
 4210     router_digest_is_trusted_dir(second->cache_info.identity_digest);
 4211 
 4212   if (first_is_auth && !second_is_auth)
 4213     return -1;
 4214   else if (!first_is_auth && second_is_auth)
 4215     return 1;
 4216 
 4217   node_first = node_get_by_id(first->cache_info.identity_digest);
 4218   node_second = node_get_by_id(second->cache_info.identity_digest);
 4219   first_is_running = node_first && node_first->is_running;
 4220   second_is_running = node_second && node_second->is_running;
 4221 
 4222   if (first_is_running && !second_is_running)
 4223     return -1;
 4224   else if (!first_is_running && second_is_running)
 4225     return 1;
 4226 
 4227   bw_kb_first = dirserv_get_bandwidth_for_router_kb(first);
 4228   bw_kb_second = dirserv_get_bandwidth_for_router_kb(second);
 4229 
 4230   if (bw_kb_first > bw_kb_second)
 4231     return -1;
 4232   else if (bw_kb_first < bw_kb_second)
 4233     return 1;
 4234 
 4235   /* They're equal! Compare by identity digest, so there's a
 4236    * deterministic order and we avoid flapping. */
 4237   return fast_memcmp(first->cache_info.identity_digest,
 4238                      second->cache_info.identity_digest,
 4239                      DIGEST_LEN);
 4240 }
 4241 
 4242 /** Given a list of routerinfo_t in <b>routers</b>, return a new digestmap_t
 4243  * whose keys are the identity digests of those routers that we're going to
 4244  * exclude for Sybil-like appearance. */
 4245 static digestmap_t *
 4246 get_possible_sybil_list(const smartlist_t *routers)
 4247 {
 4248   const or_options_t *options = get_options();
 4249   digestmap_t *omit_as_sybil;
 4250   smartlist_t *routers_by_ip = smartlist_new();
 4251   uint32_t last_addr;
 4252   int addr_count;
 4253   /* Allow at most this number of Tor servers on a single IP address, ... */
 4254   int max_with_same_addr = options->AuthDirMaxServersPerAddr;
 4255   if (max_with_same_addr <= 0)
 4256     max_with_same_addr = INT_MAX;
 4257 
 4258   smartlist_add_all(routers_by_ip, routers);
 4259   smartlist_sort(routers_by_ip, compare_routerinfo_by_ip_and_bw_);
 4260   omit_as_sybil = digestmap_new();
 4261 
 4262   last_addr = 0;
 4263   addr_count = 0;
 4264   SMARTLIST_FOREACH_BEGIN(routers_by_ip, routerinfo_t *, ri) {
 4265     if (last_addr != ri->addr) {
 4266       last_addr = ri->addr;
 4267       addr_count = 1;
 4268     } else if (++addr_count > max_with_same_addr) {
 4269       digestmap_set(omit_as_sybil, ri->cache_info.identity_digest, ri);
 4270     }
 4271   } SMARTLIST_FOREACH_END(ri);
 4272 
 4273   smartlist_free(routers_by_ip);
 4274   return omit_as_sybil;
 4275 }
 4276 
 4277 /** Given a platform string as in a routerinfo_t (possibly null), return a
 4278  * newly allocated version string for a networkstatus document, or NULL if the
 4279  * platform doesn't give a Tor version. */
 4280 static char *
 4281 version_from_platform(const char *platform)
 4282 {
 4283   if (platform && !strcmpstart(platform, "Tor ")) {
 4284     const char *eos = find_whitespace(platform+4);
 4285     if (eos && !strcmpstart(eos, " (r")) {
 4286       /* XXXX Unify this logic with the other version extraction
 4287        * logic in routerparse.c. */
 4288       eos = find_whitespace(eos+1);
 4289     }
 4290     if (eos) {
 4291       return tor_strndup(platform, eos-platform);
 4292     }
 4293   }
 4294   return NULL;
 4295 }
 4296 
 4297 /** Given a (possibly empty) list of config_line_t, each line of which contains
 4298  * a list of comma-separated version numbers surrounded by optional space,
 4299  * allocate and return a new string containing the version numbers, in order,
 4300  * separated by commas.  Used to generate Recommended(Client|Server)?Versions
 4301  */
 4302 char *
 4303 format_recommended_version_list(const config_line_t *ln, int warn)
 4304 {
 4305   smartlist_t *versions;
 4306   char *result;
 4307   versions = smartlist_new();
 4308   for ( ; ln; ln = ln->next) {
 4309     smartlist_split_string(versions, ln->value, ",",
 4310                            SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
 4311   }
 4312 
 4313   /* Handle the case where a dirauth operator has accidentally made some
 4314    * versions space-separated instead of comma-separated. */
 4315   smartlist_t *more_versions = smartlist_new();
 4316   SMARTLIST_FOREACH_BEGIN(versions, char *, v) {
 4317     if (strchr(v, ' ')) {
 4318       if (warn)
 4319         log_warn(LD_DIRSERV, "Unexpected space in versions list member %s. "
 4320                  "(These are supposed to be comma-separated; I'll pretend you "
 4321                  "used commas instead.)", escaped(v));
 4322       SMARTLIST_DEL_CURRENT(versions, v);
 4323       smartlist_split_string(more_versions, v, NULL,
 4324                              SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
 4325       tor_free(v);
 4326     }
 4327   } SMARTLIST_FOREACH_END(v);
 4328   smartlist_add_all(versions, more_versions);
 4329   smartlist_free(more_versions);
 4330 
 4331   /* Check to make sure everything looks like a version. */
 4332   if (warn) {
 4333     SMARTLIST_FOREACH_BEGIN(versions, const char *, v) {
 4334       tor_version_t ver;
 4335       if (tor_version_parse(v, &ver) < 0) {
 4336         log_warn(LD_DIRSERV, "Recommended version %s does not look valid. "
 4337                  " (I'll include it anyway, since you told me to.)",
 4338                  escaped(v));
 4339       }
 4340     } SMARTLIST_FOREACH_END(v);
 4341   }
 4342 
 4343   sort_version_list(versions, 1);
 4344   result = smartlist_join_strings(versions,",",0,NULL);
 4345   SMARTLIST_FOREACH(versions,char *,s,tor_free(s));
 4346   smartlist_free(versions);
 4347   return result;
 4348 }
 4349 
 4350 /** If there are entries in <b>routers</b> with exactly the same ed25519 keys,
 4351  * remove the older one.  If they are exactly the same age, remove the one
 4352  * with the greater descriptor digest. May alter the order of the list. */
 4353 static void
 4354 routers_make_ed_keys_unique(smartlist_t *routers)
 4355 {
 4356   routerinfo_t *ri2;
 4357   digest256map_t *by_ed_key = digest256map_new();
 4358 
 4359   SMARTLIST_FOREACH_BEGIN(routers, routerinfo_t *, ri) {
 4360     ri->omit_from_vote = 0;
 4361     if (ri->cache_info.signing_key_cert == NULL)
 4362       continue; /* No ed key */
 4363     const uint8_t *pk = ri->cache_info.signing_key_cert->signing_key.pubkey;
 4364     if ((ri2 = digest256map_get(by_ed_key, pk))) {
 4365       /* Duplicate; must omit one.  Set the omit_from_vote flag in whichever
 4366        * one has the earlier published_on. */
 4367       const time_t ri_pub = ri->cache_info.published_on;
 4368       const time_t ri2_pub = ri2->cache_info.published_on;
 4369       if (ri2_pub < ri_pub ||
 4370           (ri2_pub == ri_pub &&
 4371            fast_memcmp(ri->cache_info.signed_descriptor_digest,
 4372                      ri2->cache_info.signed_descriptor_digest,DIGEST_LEN)<0)) {
 4373         digest256map_set(by_ed_key, pk, ri);
 4374         ri2->omit_from_vote = 1;
 4375       } else {
 4376         ri->omit_from_vote = 1;
 4377       }
 4378     } else {
 4379       /* Add to map */
 4380       digest256map_set(by_ed_key, pk, ri);
 4381     }
 4382   } SMARTLIST_FOREACH_END(ri);
 4383 
 4384   digest256map_free(by_ed_key, NULL);
 4385 
 4386   /* Now remove every router where the omit_from_vote flag got set. */
 4387   SMARTLIST_FOREACH_BEGIN(routers, const routerinfo_t *, ri) {
 4388     if (ri->omit_from_vote) {
 4389       SMARTLIST_DEL_CURRENT(routers, ri);
 4390     }
 4391   } SMARTLIST_FOREACH_END(ri);
 4392 }
 4393 
 4394 /** Routerstatus <b>rs</b> is part of a group of routers that are on
 4395  * too narrow an IP-space. Clear out its flags since we don't want it be used
 4396  * because of its Sybil-like appearance.
 4397  *
 4398  * Leave its BadExit flag alone though, since if we think it's a bad exit,
 4399  * we want to vote that way in case all the other authorities are voting
 4400  * Running and Exit.
 4401  */
 4402 static void
 4403 clear_status_flags_on_sybil(routerstatus_t *rs)
 4404 {
 4405   rs->is_authority = rs->is_exit = rs->is_stable = rs->is_fast =
 4406     rs->is_flagged_running = rs->is_named = rs->is_valid =
 4407     rs->is_hs_dir = rs->is_v2_dir = rs->is_possible_guard = 0;
 4408   /* FFFF we might want some mechanism to check later on if we
 4409    * missed zeroing any flags: it's easy to add a new flag but
 4410    * forget to add it to this clause. */
 4411 }
 4412 
 4413 /** Space-separated list of all the flags that we will always vote on. */
 4414 const char DIRVOTE_UNIVERSAL_FLAGS[] =
 4415   "Authority "
 4416   "Exit "
 4417   "Fast "
 4418   "Guard "
 4419   "HSDir "
 4420   "Stable "
 4421   "StaleDesc "
 4422   "V2Dir "
 4423   "Valid";
 4424 /** Space-separated list of all flags that we may or may not vote on,
 4425  * depending on our configuration. */
 4426 const char DIRVOTE_OPTIONAL_FLAGS[] =
 4427   "BadExit "
 4428   "Running";
 4429 
 4430 /** Return a new networkstatus_t* containing our current opinion. (For v3
 4431  * authorities) */
 4432 networkstatus_t *
 4433 dirserv_generate_networkstatus_vote_obj(crypto_pk_t *private_key,
 4434                                         authority_cert_t *cert)
 4435 {
 4436   const or_options_t *options = get_options();
 4437   networkstatus_t *v3_out = NULL;
 4438   uint32_t addr;
 4439   char *hostname = NULL, *client_versions = NULL, *server_versions = NULL;
 4440   const char *contact;
 4441   smartlist_t *routers, *routerstatuses;
 4442   char identity_digest[DIGEST_LEN];
 4443   char signing_key_digest[DIGEST_LEN];
 4444   int listbadexits = options->AuthDirListBadExits;
 4445   routerlist_t *rl = router_get_routerlist();
 4446   time_t now = time(NULL);
 4447   time_t cutoff = now - ROUTER_MAX_AGE_TO_PUBLISH;
 4448   networkstatus_voter_info_t *voter = NULL;
 4449   vote_timing_t timing;
 4450   digestmap_t *omit_as_sybil = NULL;
 4451   const int vote_on_reachability = running_long_enough_to_decide_unreachable();
 4452   smartlist_t *microdescriptors = NULL;
 4453   smartlist_t *bw_file_headers = NULL;
 4454   uint8_t bw_file_digest256[DIGEST256_LEN] = {0};
 4455 
 4456   tor_assert(private_key);
 4457   tor_assert(cert);
 4458 
 4459   if (crypto_pk_get_digest(private_key, signing_key_digest)<0) {
 4460     log_err(LD_BUG, "Error computing signing key digest");
 4461     return NULL;
 4462   }
 4463   if (crypto_pk_get_digest(cert->identity_key, identity_digest)<0) {
 4464     log_err(LD_BUG, "Error computing identity key digest");
 4465     return NULL;
 4466   }
 4467   if (resolve_my_address(LOG_WARN, options, &addr, NULL, &hostname)<0) {
 4468     log_warn(LD_NET, "Couldn't resolve my hostname");
 4469     return NULL;
 4470   }
 4471   if (!hostname || !strchr(hostname, '.')) {
 4472     tor_free(hostname);
 4473     hostname = tor_dup_ip(addr);
 4474   }
 4475 
 4476   if (options->VersioningAuthoritativeDir) {
 4477     client_versions =
 4478       format_recommended_version_list(options->RecommendedClientVersions, 0);
 4479     server_versions =
 4480       format_recommended_version_list(options->RecommendedServerVersions, 0);
 4481   }
 4482 
 4483   contact = get_options()->ContactInfo;
 4484   if (!contact)
 4485     contact = "(none)";
 4486 
 4487   /*
 4488    * Do this so dirserv_compute_performance_thresholds() and
 4489    * set_routerstatus_from_routerinfo() see up-to-date bandwidth info.
 4490    */
 4491   if (options->V3BandwidthsFile) {
 4492     dirserv_read_measured_bandwidths(options->V3BandwidthsFile, NULL, NULL,
 4493                                      NULL);
 4494   } else {
 4495     /*
 4496      * No bandwidths file; clear the measured bandwidth cache in case we had
 4497      * one last time around.
 4498      */
 4499     if (dirserv_get_measured_bw_cache_size() > 0) {
 4500       dirserv_clear_measured_bw_cache();
 4501     }
 4502   }
 4503 
 4504   /* precompute this part, since we need it to decide what "stable"
 4505    * means. */
 4506   SMARTLIST_FOREACH(rl->routers, routerinfo_t *, ri, {
 4507                     dirserv_set_router_is_running(ri, now);
 4508                     });
 4509 
 4510   routers = smartlist_new();
 4511   smartlist_add_all(routers, rl->routers);
 4512   routers_make_ed_keys_unique(routers);
 4513   /* After this point, don't use rl->routers; use 'routers' instead. */
 4514   routers_sort_by_identity(routers);
 4515   omit_as_sybil = get_possible_sybil_list(routers);
 4516 
 4517   DIGESTMAP_FOREACH(omit_as_sybil, sybil_id, void *, ignore) {
 4518     (void) ignore;
 4519     rep_hist_make_router_pessimal(sybil_id, now);
 4520   } DIGESTMAP_FOREACH_END;
 4521 
 4522   /* Count how many have measured bandwidths so we know how to assign flags;
 4523    * this must come before dirserv_compute_performance_thresholds() */
 4524   dirserv_count_measured_bws(routers);
 4525 
 4526   dirserv_compute_performance_thresholds(omit_as_sybil);
 4527 
 4528   routerstatuses = smartlist_new();
 4529   microdescriptors = smartlist_new();
 4530 
 4531   SMARTLIST_FOREACH_BEGIN(routers, routerinfo_t *, ri) {
 4532     /* If it has a protover list and contains a protocol name greater than
 4533      * MAX_PROTOCOL_NAME_LENGTH, skip it. */
 4534     if (ri->protocol_list &&
 4535         protover_contains_long_protocol_names(ri->protocol_list)) {
 4536       continue;
 4537     }
 4538     if (ri->cache_info.published_on >= cutoff) {
 4539       routerstatus_t *rs;
 4540       vote_routerstatus_t *vrs;
 4541       node_t *node = node_get_mutable_by_id(ri->cache_info.identity_digest);
 4542       if (!node)
 4543         continue;
 4544 
 4545       vrs = tor_malloc_zero(sizeof(vote_routerstatus_t));
 4546       rs = &vrs->status;
 4547       dirauth_set_routerstatus_from_routerinfo(rs, node, ri, now,
 4548                                                listbadexits);
 4549 
 4550       if (ri->cache_info.signing_key_cert) {
 4551         memcpy(vrs->ed25519_id,
 4552                ri->cache_info.signing_key_cert->signing_key.pubkey,
 4553                ED25519_PUBKEY_LEN);
 4554       }
 4555 
 4556       if (digestmap_get(omit_as_sybil, ri->cache_info.identity_digest))
 4557         clear_status_flags_on_sybil(rs);
 4558 
 4559       if (!vote_on_reachability)
 4560         rs->is_flagged_running = 0;
 4561 
 4562       vrs->version = version_from_platform(ri->platform);
 4563       if (ri->protocol_list) {
 4564         vrs->protocols = tor_strdup(ri->protocol_list);
 4565       } else {
 4566         vrs->protocols = tor_strdup(
 4567                                 protover_compute_for_old_tor(vrs->version));
 4568       }
 4569       vrs->microdesc = dirvote_format_all_microdesc_vote_lines(ri, now,
 4570                                                             microdescriptors);
 4571 
 4572       smartlist_add(routerstatuses, vrs);
 4573     }
 4574   } SMARTLIST_FOREACH_END(ri);
 4575 
 4576   {
 4577     smartlist_t *added =
 4578       microdescs_add_list_to_cache(get_microdesc_cache(),
 4579                                    microdescriptors, SAVED_NOWHERE, 0);
 4580     smartlist_free(added);
 4581     smartlist_free(microdescriptors);
 4582   }
 4583 
 4584   smartlist_free(routers);
 4585   digestmap_free(omit_as_sybil, NULL);
 4586 
 4587   /* Apply guardfraction information to routerstatuses. */
 4588   if (options->GuardfractionFile) {
 4589     dirserv_read_guardfraction_file(options->GuardfractionFile,
 4590                                     routerstatuses);
 4591   }
 4592 
 4593   /* This pass through applies the measured bw lines to the routerstatuses */
 4594   if (options->V3BandwidthsFile) {
 4595     /* Only set bw_file_headers when V3BandwidthsFile is configured */
 4596     bw_file_headers = smartlist_new();
 4597     dirserv_read_measured_bandwidths(options->V3BandwidthsFile,
 4598                                      routerstatuses, bw_file_headers,
 4599                                      bw_file_digest256);
 4600 
 4601   } else {
 4602     /*
 4603      * No bandwidths file; clear the measured bandwidth cache in case we had
 4604      * one last time around.
 4605      */
 4606     if (dirserv_get_measured_bw_cache_size() > 0) {
 4607       dirserv_clear_measured_bw_cache();
 4608     }
 4609   }
 4610 
 4611   v3_out = tor_malloc_zero(sizeof(networkstatus_t));
 4612 
 4613   v3_out->type = NS_TYPE_VOTE;
 4614   dirvote_get_preferred_voting_intervals(&timing);
 4615   v3_out->published = now;
 4616   {
 4617     char tbuf[ISO_TIME_LEN+1];
 4618     networkstatus_t *current_consensus =
 4619       networkstatus_get_live_consensus(now);
 4620     long last_consensus_interval; /* only used to pick a valid_after */
 4621     if (current_consensus)
 4622       last_consensus_interval = current_consensus->fresh_until -
 4623         current_consensus->valid_after;
 4624     else
 4625       last_consensus_interval = options->TestingV3AuthInitialVotingInterval;
 4626     v3_out->valid_after =
 4627       voting_schedule_get_start_of_next_interval(now,
 4628                                    (int)last_consensus_interval,
 4629                                    options->TestingV3AuthVotingStartOffset);
 4630     format_iso_time(tbuf, v3_out->valid_after);
 4631     log_notice(LD_DIR,"Choosing valid-after time in vote as %s: "
 4632                "consensus_set=%d, last_interval=%d",
 4633                tbuf, current_consensus?1:0, (int)last_consensus_interval);
 4634   }
 4635   v3_out->fresh_until = v3_out->valid_after + timing.vote_interval;
 4636   v3_out->valid_until = v3_out->valid_after +
 4637     (timing.vote_interval * timing.n_intervals_valid);
 4638   v3_out->vote_seconds = timing.vote_delay;
 4639   v3_out->dist_seconds = timing.dist_delay;
 4640   tor_assert(v3_out->vote_seconds > 0);
 4641   tor_assert(v3_out->dist_seconds > 0);
 4642   tor_assert(timing.n_intervals_valid > 0);
 4643 
 4644   v3_out->client_versions = client_versions;
 4645   v3_out->server_versions = server_versions;
 4646 
 4647   /* These are hardwired, to avoid disaster. */
 4648   v3_out->recommended_relay_protocols =
 4649     tor_strdup("Cons=1-2 Desc=1-2 DirCache=1 HSDir=1 HSIntro=3 HSRend=1 "
 4650                "Link=4 Microdesc=1-2 Relay=2");
 4651   v3_out->recommended_client_protocols =
 4652     tor_strdup("Cons=1-2 Desc=1-2 DirCache=1 HSDir=1 HSIntro=3 HSRend=1 "
 4653                "Link=4 Microdesc=1-2 Relay=2");
 4654   v3_out->required_client_protocols =
 4655     tor_strdup("Cons=1-2 Desc=1-2 DirCache=1 HSDir=1 HSIntro=3 HSRend=1 "
 4656                "Link=4 Microdesc=1-2 Relay=2");
 4657   v3_out->required_relay_protocols =
 4658     tor_strdup("Cons=1 Desc=1 DirCache=1 HSDir=1 HSIntro=3 HSRend=1 "
 4659                "Link=3-4 Microdesc=1 Relay=1-2");
 4660 
 4661   /* We are not allowed to vote to require anything we don't have. */
 4662   tor_assert(protover_all_supported(v3_out->required_relay_protocols, NULL));
 4663   tor_assert(protover_all_supported(v3_out->required_client_protocols, NULL));
 4664 
 4665   /* We should not recommend anything we don't have. */
 4666   tor_assert_nonfatal(protover_all_supported(
 4667                                v3_out->recommended_relay_protocols, NULL));
 4668   tor_assert_nonfatal(protover_all_supported(
 4669                                v3_out->recommended_client_protocols, NULL));
 4670 
 4671   v3_out->package_lines = smartlist_new();
 4672   {
 4673     config_line_t *cl;
 4674     for (cl = get_options()->RecommendedPackages; cl; cl = cl->next) {
 4675       if (validate_recommended_package_line(cl->value))
 4676         smartlist_add_strdup(v3_out->package_lines, cl->value);
 4677     }
 4678   }
 4679 
 4680   v3_out->known_flags = smartlist_new();
 4681   smartlist_split_string(v3_out->known_flags,
 4682                          DIRVOTE_UNIVERSAL_FLAGS,
 4683                          0, SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
 4684   if (vote_on_reachability)
 4685     smartlist_add_strdup(v3_out->known_flags, "Running");
 4686   if (listbadexits)
 4687     smartlist_add_strdup(v3_out->known_flags, "BadExit");
 4688   smartlist_sort_strings(v3_out->known_flags);
 4689 
 4690   if (options->ConsensusParams) {
 4691     v3_out->net_params = smartlist_new();
 4692     smartlist_split_string(v3_out->net_params,
 4693                            options->ConsensusParams, NULL, 0, 0);
 4694     smartlist_sort_strings(v3_out->net_params);
 4695   }
 4696   v3_out->bw_file_headers = bw_file_headers;
 4697   memcpy(v3_out->bw_file_digest256, bw_file_digest256, DIGEST256_LEN);
 4698 
 4699   voter = tor_malloc_zero(sizeof(networkstatus_voter_info_t));
 4700   voter->nickname = tor_strdup(options->Nickname);
 4701   memcpy(voter->identity_digest, identity_digest, DIGEST_LEN);
 4702   voter->sigs = smartlist_new();
 4703   voter->address = hostname;
 4704   voter->addr = addr;
 4705   voter->dir_port = router_get_advertised_dir_port(options, 0);
 4706   voter->or_port = router_get_advertised_or_port(options);
 4707   voter->contact = tor_strdup(contact);
 4708   if (options->V3AuthUseLegacyKey) {
 4709     authority_cert_t *c = get_my_v3_legacy_cert();
 4710     if (c) {
 4711       if (crypto_pk_get_digest(c->identity_key, voter->legacy_id_digest)) {
 4712         log_warn(LD_BUG, "Unable to compute digest of legacy v3 identity key");
 4713         memset(voter->legacy_id_digest, 0, DIGEST_LEN);
 4714       }
 4715     }
 4716   }
 4717 
 4718   v3_out->voters = smartlist_new();
 4719   smartlist_add(v3_out->voters, voter);
 4720   v3_out->cert = authority_cert_dup(cert);
 4721   v3_out->routerstatus_list = routerstatuses;
 4722   /* Note: networkstatus_digest is unset; it won't get set until we actually
 4723    * format the vote. */
 4724 
 4725   return v3_out;
 4726 }