Back to index

tor  0.2.3.18-rc
dirvote.c
Go to the documentation of this file.
00001 /* Copyright (c) 2001-2004, Roger Dingledine.
00002  * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
00003  * Copyright (c) 2007-2012, The Tor Project, Inc. */
00004 /* See LICENSE for licensing information */
00005 
00006 #define DIRVOTE_PRIVATE
00007 #include "or.h"
00008 #include "config.h"
00009 #include "directory.h"
00010 #include "dirserv.h"
00011 #include "dirvote.h"
00012 #include "microdesc.h"
00013 #include "networkstatus.h"
00014 #include "policies.h"
00015 #include "rephist.h"
00016 #include "router.h"
00017 #include "routerlist.h"
00018 #include "routerparse.h"
00019 
00028 typedef struct pending_consensus_t {
00031   char *body;
00033   networkstatus_t *consensus;
00034 } pending_consensus_t;
00035 
00036 /* DOCDOC dirvote_add_signatures_to_all_pending_consensuses */
00037 static int dirvote_add_signatures_to_all_pending_consensuses(
00038                        const char *detached_signatures_body,
00039                        const char *source,
00040                        const char **msg_out);
00041 static int dirvote_add_signatures_to_pending_consensus(
00042                        pending_consensus_t *pc,
00043                        ns_detached_signatures_t *sigs,
00044                        const char *source,
00045                        int severity,
00046                        const char **msg_out);
00047 static char *list_v3_auth_ids(void);
00048 static void dirvote_fetch_missing_votes(void);
00049 static void dirvote_fetch_missing_signatures(void);
00050 static int dirvote_perform_vote(void);
00051 static void dirvote_clear_votes(int all_votes);
00052 static int dirvote_compute_consensuses(void);
00053 static int dirvote_publish_consensus(void);
00054 static char *make_consensus_method_list(int low, int high, const char *sep);
00055 
00057 #define MAX_SUPPORTED_CONSENSUS_METHOD 12
00058 
00060 #define MIN_METHOD_FOR_FOOTER 9
00061 
00063 #define MIN_METHOD_FOR_BW_WEIGHTS 9
00064 
00066 #define MIN_METHOD_FOR_PARAMS 7
00067 
00069 #define MIN_METHOD_FOR_MICRODESC 8
00070 
00073 #define MIN_METHOD_FOR_MAJORITY_PARAMS 12
00074 
00075 /* =====
00076  * Voting
00077  * =====*/
00078 
00079 /* Overestimated. */
00080 #define MICRODESC_LINE_LEN 80
00081 
00085 char *
00086 format_networkstatus_vote(crypto_pk_t *private_signing_key,
00087                           networkstatus_t *v3_ns)
00088 {
00089   size_t len;
00090   char *status = NULL;
00091   const char *client_versions = NULL, *server_versions = NULL;
00092   char *outp, *endp;
00093   char fingerprint[FINGERPRINT_LEN+1];
00094   char digest[DIGEST_LEN];
00095   uint32_t addr;
00096   routerlist_t *rl = router_get_routerlist();
00097   char *version_lines = NULL;
00098   int r;
00099   networkstatus_voter_info_t *voter;
00100 
00101   tor_assert(private_signing_key);
00102   tor_assert(v3_ns->type == NS_TYPE_VOTE || v3_ns->type == NS_TYPE_OPINION);
00103 
00104   voter = smartlist_get(v3_ns->voters, 0);
00105 
00106   addr = voter->addr;
00107 
00108   base16_encode(fingerprint, sizeof(fingerprint),
00109                 v3_ns->cert->cache_info.identity_digest, DIGEST_LEN);
00110   client_versions = v3_ns->client_versions;
00111   server_versions = v3_ns->server_versions;
00112 
00113   if (client_versions || server_versions) {
00114     size_t v_len = 64;
00115     char *cp;
00116     if (client_versions)
00117       v_len += strlen(client_versions);
00118     if (server_versions)
00119       v_len += strlen(server_versions);
00120     version_lines = tor_malloc(v_len);
00121     cp = version_lines;
00122     if (client_versions) {
00123       r = tor_snprintf(cp, v_len-(cp-version_lines),
00124                    "client-versions %s\n", client_versions);
00125       if (r < 0) {
00126         log_err(LD_BUG, "Insufficient memory for client-versions line");
00127         tor_assert(0);
00128       }
00129       cp += strlen(cp);
00130     }
00131     if (server_versions) {
00132       r = tor_snprintf(cp, v_len-(cp-version_lines),
00133                    "server-versions %s\n", server_versions);
00134       if (r < 0) {
00135         log_err(LD_BUG, "Insufficient memory for server-versions line");
00136         tor_assert(0);
00137       }
00138     }
00139   } else {
00140     version_lines = tor_strdup("");
00141   }
00142 
00143   len = 8192;
00144   len += strlen(version_lines);
00145   len += (RS_ENTRY_LEN+MICRODESC_LINE_LEN)*smartlist_len(rl->routers);
00146   len += strlen("\ndirectory-footer\n");
00147   len += v3_ns->cert->cache_info.signed_descriptor_len;
00148 
00149   status = tor_malloc(len);
00150   {
00151     char published[ISO_TIME_LEN+1];
00152     char va[ISO_TIME_LEN+1];
00153     char fu[ISO_TIME_LEN+1];
00154     char vu[ISO_TIME_LEN+1];
00155     char *flags = smartlist_join_strings(v3_ns->known_flags, " ", 0, NULL);
00156     char *params;
00157     authority_cert_t *cert = v3_ns->cert;
00158     char *methods =
00159       make_consensus_method_list(1, MAX_SUPPORTED_CONSENSUS_METHOD, " ");
00160     format_iso_time(published, v3_ns->published);
00161     format_iso_time(va, v3_ns->valid_after);
00162     format_iso_time(fu, v3_ns->fresh_until);
00163     format_iso_time(vu, v3_ns->valid_until);
00164 
00165     if (v3_ns->net_params)
00166       params = smartlist_join_strings(v3_ns->net_params, " ", 0, NULL);
00167     else
00168       params = tor_strdup("");
00169 
00170     tor_assert(cert);
00171     r = tor_snprintf(status, len,
00172                  "network-status-version 3\n"
00173                  "vote-status %s\n"
00174                  "consensus-methods %s\n"
00175                  "published %s\n"
00176                  "valid-after %s\n"
00177                  "fresh-until %s\n"
00178                  "valid-until %s\n"
00179                  "voting-delay %d %d\n"
00180                  "%s" /* versions */
00181                  "known-flags %s\n"
00182                  "params %s\n"
00183                  "dir-source %s %s %s %s %d %d\n"
00184                  "contact %s\n",
00185                  v3_ns->type == NS_TYPE_VOTE ? "vote" : "opinion",
00186                  methods,
00187                  published, va, fu, vu,
00188                  v3_ns->vote_seconds, v3_ns->dist_seconds,
00189                  version_lines,
00190                  flags,
00191                  params,
00192                  voter->nickname, fingerprint, voter->address,
00193                  fmt_addr32(addr), voter->dir_port, voter->or_port,
00194                  voter->contact);
00195 
00196     if (r < 0) {
00197       log_err(LD_BUG, "Insufficient memory for network status line");
00198       tor_assert(0);
00199     }
00200 
00201     tor_free(params);
00202     tor_free(flags);
00203     tor_free(methods);
00204     outp = status + strlen(status);
00205     endp = status + len;
00206 
00207     if (!tor_digest_is_zero(voter->legacy_id_digest)) {
00208       char fpbuf[HEX_DIGEST_LEN+1];
00209       base16_encode(fpbuf, sizeof(fpbuf), voter->legacy_id_digest, DIGEST_LEN);
00210       r = tor_snprintf(outp, endp-outp, "legacy-dir-key %s\n", fpbuf);
00211       if (r < 0) {
00212         log_err(LD_BUG, "Insufficient memory for legacy-dir-key line");
00213         tor_assert(0);
00214       }
00215       outp += strlen(outp);
00216     }
00217 
00218     tor_assert(outp + cert->cache_info.signed_descriptor_len < endp);
00219     memcpy(outp, cert->cache_info.signed_descriptor_body,
00220            cert->cache_info.signed_descriptor_len);
00221 
00222     outp += cert->cache_info.signed_descriptor_len;
00223   }
00224 
00225   SMARTLIST_FOREACH_BEGIN(v3_ns->routerstatus_list, vote_routerstatus_t *,
00226                           vrs) {
00227     vote_microdesc_hash_t *h;
00228     if (routerstatus_format_entry(outp, endp-outp, &vrs->status,
00229                                   vrs->version, NS_V3_VOTE) < 0) {
00230       log_warn(LD_BUG, "Unable to print router status.");
00231       goto err;
00232     }
00233     outp += strlen(outp);
00234 
00235     for (h = vrs->microdesc; h; h = h->next) {
00236       size_t mlen = strlen(h->microdesc_hash_line);
00237       if (outp+mlen >= endp) {
00238         log_warn(LD_BUG, "Can't fit microdesc line in vote.");
00239       }
00240       memcpy(outp, h->microdesc_hash_line, mlen+1);
00241       outp += strlen(outp);
00242     }
00243   } SMARTLIST_FOREACH_END(vrs);
00244 
00245   r = tor_snprintf(outp, endp-outp, "directory-footer\n");
00246   if (r < 0) {
00247     log_err(LD_BUG, "Insufficient memory for directory-footer line");
00248     tor_assert(0);
00249   }
00250   outp += strlen(outp);
00251 
00252   {
00253     char signing_key_fingerprint[FINGERPRINT_LEN+1];
00254     if (tor_snprintf(outp, endp-outp, "directory-signature ")<0) {
00255       log_warn(LD_BUG, "Unable to start signature line.");
00256       goto err;
00257     }
00258     outp += strlen(outp);
00259 
00260     if (crypto_pk_get_fingerprint(private_signing_key,
00261                                   signing_key_fingerprint, 0)<0) {
00262       log_warn(LD_BUG, "Unable to get fingerprint for signing key");
00263       goto err;
00264     }
00265     if (tor_snprintf(outp, endp-outp, "%s %s\n", fingerprint,
00266                      signing_key_fingerprint)<0) {
00267       log_warn(LD_BUG, "Unable to end signature line.");
00268       goto err;
00269     }
00270     outp += strlen(outp);
00271   }
00272 
00273   if (router_get_networkstatus_v3_hash(status, digest, DIGEST_SHA1)<0)
00274     goto err;
00275   note_crypto_pk_op(SIGN_DIR);
00276   if (router_append_dirobj_signature(outp,endp-outp,digest, DIGEST_LEN,
00277                                      private_signing_key)<0) {
00278     log_warn(LD_BUG, "Unable to sign networkstatus vote.");
00279     goto err;
00280   }
00281 
00282   {
00283     networkstatus_t *v;
00284     if (!(v = networkstatus_parse_vote_from_string(status, NULL,
00285                                                    v3_ns->type))) {
00286       log_err(LD_BUG,"Generated a networkstatus %s we couldn't parse: "
00287               "<<%s>>",
00288               v3_ns->type == NS_TYPE_VOTE ? "vote" : "opinion", status);
00289       goto err;
00290     }
00291     networkstatus_vote_free(v);
00292   }
00293 
00294   goto done;
00295 
00296  err:
00297   tor_free(status);
00298  done:
00299   tor_free(version_lines);
00300   return status;
00301 }
00302 
00303 /* =====
00304  * Consensus generation
00305  * ===== */
00306 
00309 static networkstatus_voter_info_t *
00310 get_voter(const networkstatus_t *vote)
00311 {
00312   tor_assert(vote);
00313   tor_assert(vote->type == NS_TYPE_VOTE);
00314   tor_assert(vote->voters);
00315   tor_assert(smartlist_len(vote->voters) == 1);
00316   return smartlist_get(vote->voters, 0);
00317 }
00318 
00321 document_signature_t *
00322 voter_get_sig_by_algorithm(const networkstatus_voter_info_t *voter,
00323                            digest_algorithm_t alg)
00324 {
00325   if (!voter->sigs)
00326     return NULL;
00327   SMARTLIST_FOREACH(voter->sigs, document_signature_t *, sig,
00328     if (sig->alg == alg)
00329       return sig);
00330   return NULL;
00331 }
00332 
00336 typedef struct dir_src_ent_t {
00337   networkstatus_t *v;
00338   const char *digest;
00339   int is_legacy;
00340 } dir_src_ent_t;
00341 
00344 static int
00345 _compare_votes_by_authority_id(const void **_a, const void **_b)
00346 {
00347   const networkstatus_t *a = *_a, *b = *_b;
00348   return fast_memcmp(get_voter(a)->identity_digest,
00349                 get_voter(b)->identity_digest, DIGEST_LEN);
00350 }
00351 
00355 static int
00356 _compare_dir_src_ents_by_authority_id(const void **_a, const void **_b)
00357 {
00358   const dir_src_ent_t *a = *_a, *b = *_b;
00359   const networkstatus_voter_info_t *a_v = get_voter(a->v),
00360     *b_v = get_voter(b->v);
00361   const char *a_id, *b_id;
00362   a_id = a->is_legacy ? a_v->legacy_id_digest : a_v->identity_digest;
00363   b_id = b->is_legacy ? b_v->legacy_id_digest : b_v->identity_digest;
00364 
00365   return fast_memcmp(a_id, b_id, DIGEST_LEN);
00366 }
00367 
00370 static void
00371 get_frequent_members(smartlist_t *out, smartlist_t *in, int min)
00372 {
00373   char *cur = NULL;
00374   int count = 0;
00375   SMARTLIST_FOREACH(in, char *, cp,
00376   {
00377     if (cur && !strcmp(cp, cur)) {
00378       ++count;
00379     } else {
00380       if (count > min)
00381         smartlist_add(out, cur);
00382       cur = cp;
00383       count = 1;
00384     }
00385   });
00386   if (count > min)
00387     smartlist_add(out, cur);
00388 }
00389 
00392 #define get_most_frequent_member(lst)           \
00393   smartlist_get_most_frequent_string(lst)
00394 
00398 static int
00399 compare_vote_rs(const vote_routerstatus_t *a, const vote_routerstatus_t *b)
00400 {
00401   int r;
00402   if ((r = fast_memcmp(a->status.identity_digest, b->status.identity_digest,
00403                   DIGEST_LEN)))
00404     return r;
00405   if ((r = fast_memcmp(a->status.descriptor_digest,
00406                        b->status.descriptor_digest,
00407                        DIGEST_LEN)))
00408     return r;
00409   if ((r = (int)(b->status.published_on - a->status.published_on)))
00410     return r;
00411   if ((r = strcmp(b->status.nickname, a->status.nickname)))
00412     return r;
00413   if ((r = (((int)b->status.addr) - ((int)a->status.addr))))
00414     return r;
00415   if ((r = (((int)b->status.or_port) - ((int)a->status.or_port))))
00416     return r;
00417   if ((r = (((int)b->status.dir_port) - ((int)a->status.dir_port))))
00418     return r;
00419   return 0;
00420 }
00421 
00423 static int
00424 _compare_vote_rs(const void **_a, const void **_b)
00425 {
00426   const vote_routerstatus_t *a = *_a, *b = *_b;
00427   return compare_vote_rs(a,b);
00428 }
00429 
00435 static vote_routerstatus_t *
00436 compute_routerstatus_consensus(smartlist_t *votes, int consensus_method,
00437                                char *microdesc_digest256_out)
00438 {
00439   vote_routerstatus_t *most = NULL, *cur = NULL;
00440   int most_n = 0, cur_n = 0;
00441   time_t most_published = 0;
00442 
00443   /* _compare_vote_rs() sorts the items by identity digest (all the same),
00444    * then by SD digest.  That way, if we have a tie that the published_on
00445    * date cannot tie, we use the descriptor with the smaller digest.
00446    */
00447   smartlist_sort(votes, _compare_vote_rs);
00448   SMARTLIST_FOREACH(votes, vote_routerstatus_t *, rs,
00449   {
00450     if (cur && !compare_vote_rs(cur, rs)) {
00451       ++cur_n;
00452     } else {
00453       if (cur && (cur_n > most_n ||
00454                   (cur_n == most_n &&
00455                    cur->status.published_on > most_published))) {
00456         most = cur;
00457         most_n = cur_n;
00458         most_published = cur->status.published_on;
00459       }
00460       cur_n = 1;
00461       cur = rs;
00462     }
00463   });
00464 
00465   if (cur_n > most_n ||
00466       (cur && cur_n == most_n && cur->status.published_on > most_published)) {
00467     most = cur;
00468     most_n = cur_n;
00469     most_published = cur->status.published_on;
00470   }
00471 
00472   tor_assert(most);
00473 
00474   if (consensus_method >= MIN_METHOD_FOR_MICRODESC &&
00475       microdesc_digest256_out) {
00476     smartlist_t *digests = smartlist_new();
00477     const char *best_microdesc_digest;
00478     SMARTLIST_FOREACH_BEGIN(votes, vote_routerstatus_t *, rs) {
00479         char d[DIGEST256_LEN];
00480         if (compare_vote_rs(rs, most))
00481           continue;
00482         if (!vote_routerstatus_find_microdesc_hash(d, rs, consensus_method,
00483                                                    DIGEST_SHA256))
00484           smartlist_add(digests, tor_memdup(d, sizeof(d)));
00485     } SMARTLIST_FOREACH_END(rs);
00486     smartlist_sort_digests256(digests);
00487     best_microdesc_digest = smartlist_get_most_frequent_digest256(digests);
00488     if (best_microdesc_digest)
00489       memcpy(microdesc_digest256_out, best_microdesc_digest, DIGEST256_LEN);
00490     SMARTLIST_FOREACH(digests, char *, cp, tor_free(cp));
00491     smartlist_free(digests);
00492   }
00493 
00494   return most;
00495 }
00496 
00500 static void
00501 hash_list_members(char *digest_out, size_t len_out,
00502                   smartlist_t *lst, digest_algorithm_t alg)
00503 {
00504   crypto_digest_t *d;
00505   if (alg == DIGEST_SHA1)
00506     d = crypto_digest_new();
00507   else
00508     d = crypto_digest256_new(alg);
00509   SMARTLIST_FOREACH(lst, const char *, cp,
00510                     crypto_digest_add_bytes(d, cp, strlen(cp)));
00511   crypto_digest_get_digest(d, digest_out, len_out);
00512   crypto_digest_free(d);
00513 }
00514 
00518 static int
00519 _cmp_int_strings(const void **_a, const void **_b)
00520 {
00521   const char *a = *_a, *b = *_b;
00522   int ai = (int)tor_parse_long(a, 10, 1, INT_MAX, NULL, NULL);
00523   int bi = (int)tor_parse_long(b, 10, 1, INT_MAX, NULL, NULL);
00524   if (ai<bi) {
00525     return -1;
00526   } else if (ai==bi) {
00527     if (ai == 0) /* Parsing failed. */
00528       return strcmp(a, b);
00529     return 0;
00530   } else {
00531     return 1;
00532   }
00533 }
00534 
00537 static int
00538 compute_consensus_method(smartlist_t *votes)
00539 {
00540   smartlist_t *all_methods = smartlist_new();
00541   smartlist_t *acceptable_methods = smartlist_new();
00542   smartlist_t *tmp = smartlist_new();
00543   int min = (smartlist_len(votes) * 2) / 3;
00544   int n_ok;
00545   int result;
00546   SMARTLIST_FOREACH(votes, networkstatus_t *, vote,
00547   {
00548     tor_assert(vote->supported_methods);
00549     smartlist_add_all(tmp, vote->supported_methods);
00550     smartlist_sort(tmp, _cmp_int_strings);
00551     smartlist_uniq(tmp, _cmp_int_strings, NULL);
00552     smartlist_add_all(all_methods, tmp);
00553     smartlist_clear(tmp);
00554   });
00555 
00556   smartlist_sort(all_methods, _cmp_int_strings);
00557   get_frequent_members(acceptable_methods, all_methods, min);
00558   n_ok = smartlist_len(acceptable_methods);
00559   if (n_ok) {
00560     const char *best = smartlist_get(acceptable_methods, n_ok-1);
00561     result = (int)tor_parse_long(best, 10, 1, INT_MAX, NULL, NULL);
00562   } else {
00563     result = 1;
00564   }
00565   smartlist_free(tmp);
00566   smartlist_free(all_methods);
00567   smartlist_free(acceptable_methods);
00568   return result;
00569 }
00570 
00572 static int
00573 consensus_method_is_supported(int method)
00574 {
00575   return (method >= 1) && (method <= MAX_SUPPORTED_CONSENSUS_METHOD);
00576 }
00577 
00580 static char *
00581 make_consensus_method_list(int low, int high, const char *separator)
00582 {
00583   char *list;
00584 
00585   int i;
00586   smartlist_t *lst;
00587   lst = smartlist_new();
00588   for (i = low; i <= high; ++i) {
00589     if (!consensus_method_is_supported(i))
00590       continue;
00591     smartlist_add_asprintf(lst, "%d", i);
00592   }
00593   list = smartlist_join_strings(lst, separator, 0, NULL);
00594   tor_assert(list);
00595   SMARTLIST_FOREACH(lst, char *, cp, tor_free(cp));
00596   smartlist_free(lst);
00597   return list;
00598 }
00599 
00604 static char *
00605 compute_consensus_versions_list(smartlist_t *lst, int n_versioning)
00606 {
00607   int min = n_versioning / 2;
00608   smartlist_t *good = smartlist_new();
00609   char *result;
00610   sort_version_list(lst, 0);
00611   get_frequent_members(good, lst, min);
00612   result = smartlist_join_strings(good, ",", 0, NULL);
00613   smartlist_free(good);
00614   return result;
00615 }
00616 
00620 #define MIN_VOTES_FOR_PARAM 3
00621 
00625 /* private */ char *
00626 dirvote_compute_params(smartlist_t *votes, int method, int total_authorities)
00627 {
00628   int i;
00629   int32_t *vals;
00630 
00631   int cur_param_len;
00632   const char *cur_param;
00633   const char *eq;
00634   char *result;
00635 
00636   const int n_votes = smartlist_len(votes);
00637   smartlist_t *output;
00638   smartlist_t *param_list = smartlist_new();
00639 
00640   /* We require that the parameter lists in the votes are well-formed: that
00641      is, that their keywords are unique and sorted, and that their values are
00642      between INT32_MIN and INT32_MAX inclusive.  This should be guaranteed by
00643      the parsing code. */
00644 
00645   vals = tor_malloc(sizeof(int)*n_votes);
00646 
00647   SMARTLIST_FOREACH_BEGIN(votes, networkstatus_t *, v) {
00648     if (!v->net_params)
00649       continue;
00650     smartlist_add_all(param_list, v->net_params);
00651   } SMARTLIST_FOREACH_END(v);
00652 
00653   if (smartlist_len(param_list) == 0) {
00654     tor_free(vals);
00655     smartlist_free(param_list);
00656     return NULL;
00657   }
00658 
00659   smartlist_sort_strings(param_list);
00660   i = 0;
00661   cur_param = smartlist_get(param_list, 0);
00662   eq = strchr(cur_param, '=');
00663   tor_assert(eq);
00664   cur_param_len = (int)(eq+1 - cur_param);
00665 
00666   output = smartlist_new();
00667 
00668   SMARTLIST_FOREACH_BEGIN(param_list, const char *, param) {
00669     const char *next_param;
00670     int ok=0;
00671     eq = strchr(param, '=');
00672     tor_assert(i<n_votes); /* Make sure we prevented vote-stuffing. */
00673     vals[i++] = (int32_t)
00674       tor_parse_long(eq+1, 10, INT32_MIN, INT32_MAX, &ok, NULL);
00675     tor_assert(ok); /* Already checked these when parsing. */
00676 
00677     if (param_sl_idx+1 == smartlist_len(param_list))
00678       next_param = NULL;
00679     else
00680       next_param = smartlist_get(param_list, param_sl_idx+1);
00681     if (!next_param || strncmp(next_param, param, cur_param_len)) {
00682       /* We've reached the end of a series. */
00683       /* Make sure enough authorities voted on this param, unless the
00684        * the consensus method we use is too old for that. */
00685       if (method < MIN_METHOD_FOR_MAJORITY_PARAMS ||
00686           i > total_authorities/2 ||
00687           i >= MIN_VOTES_FOR_PARAM) {
00688         int32_t median = median_int32(vals, i);
00689         char *out_string = tor_malloc(64+cur_param_len);
00690         memcpy(out_string, param, cur_param_len);
00691         tor_snprintf(out_string+cur_param_len,64, "%ld", (long)median);
00692         smartlist_add(output, out_string);
00693       }
00694 
00695       i = 0;
00696       if (next_param) {
00697         eq = strchr(next_param, '=');
00698         cur_param_len = (int)(eq+1 - next_param);
00699       }
00700     }
00701   } SMARTLIST_FOREACH_END(param);
00702 
00703   result = smartlist_join_strings(output, " ", 0, NULL);
00704   SMARTLIST_FOREACH(output, char *, cp, tor_free(cp));
00705   smartlist_free(output);
00706   smartlist_free(param_list);
00707   tor_free(vals);
00708   return result;
00709 }
00710 
00711 #define RANGE_CHECK(a,b,c,d,e,f,g,mx) \
00712        ((a) >= 0 && (a) <= (mx) && (b) >= 0 && (b) <= (mx) && \
00713         (c) >= 0 && (c) <= (mx) && (d) >= 0 && (d) <= (mx) && \
00714         (e) >= 0 && (e) <= (mx) && (f) >= 0 && (f) <= (mx) && \
00715         (g) >= 0 && (g) <= (mx))
00716 
00717 #define CHECK_EQ(a, b, margin) \
00718      ((a)-(b) >= 0 ? (a)-(b) <= (margin) : (b)-(a) <= (margin))
00719 
00720 typedef enum {
00721  BW_WEIGHTS_NO_ERROR = 0,
00722  BW_WEIGHTS_RANGE_ERROR = 1,
00723  BW_WEIGHTS_SUMG_ERROR = 2,
00724  BW_WEIGHTS_SUME_ERROR = 3,
00725  BW_WEIGHTS_SUMD_ERROR = 4,
00726  BW_WEIGHTS_BALANCE_MID_ERROR = 5,
00727  BW_WEIGHTS_BALANCE_EG_ERROR = 6
00728 } bw_weights_error_t;
00729 
00733 static bw_weights_error_t
00734 networkstatus_check_weights(int64_t Wgg, int64_t Wgd, int64_t Wmg,
00735                             int64_t Wme, int64_t Wmd, int64_t Wee,
00736                             int64_t Wed, int64_t scale, int64_t G,
00737                             int64_t M, int64_t E, int64_t D, int64_t T,
00738                             int64_t margin, int do_balance) {
00739   bw_weights_error_t berr = BW_WEIGHTS_NO_ERROR;
00740 
00741   // Wed + Wmd + Wgd == 1
00742   if (!CHECK_EQ(Wed + Wmd + Wgd, scale, margin)) {
00743     berr = BW_WEIGHTS_SUMD_ERROR;
00744     goto out;
00745   }
00746 
00747   // Wmg + Wgg == 1
00748   if (!CHECK_EQ(Wmg + Wgg, scale, margin)) {
00749     berr = BW_WEIGHTS_SUMG_ERROR;
00750     goto out;
00751   }
00752 
00753   // Wme + Wee == 1
00754   if (!CHECK_EQ(Wme + Wee, scale, margin)) {
00755     berr = BW_WEIGHTS_SUME_ERROR;
00756     goto out;
00757   }
00758 
00759   // Verify weights within range 0->1
00760   if (!RANGE_CHECK(Wgg, Wgd, Wmg, Wme, Wmd, Wed, Wee, scale)) {
00761     berr = BW_WEIGHTS_RANGE_ERROR;
00762     goto out;
00763   }
00764 
00765   if (do_balance) {
00766     // Wgg*G + Wgd*D == Wee*E + Wed*D, already scaled
00767     if (!CHECK_EQ(Wgg*G + Wgd*D, Wee*E + Wed*D, (margin*T)/3)) {
00768       berr = BW_WEIGHTS_BALANCE_EG_ERROR;
00769       goto out;
00770     }
00771 
00772     // Wgg*G + Wgd*D == M*scale + Wmd*D + Wme*E + Wmg*G, already scaled
00773     if (!CHECK_EQ(Wgg*G + Wgd*D, M*scale + Wmd*D + Wme*E + Wmg*G,
00774                 (margin*T)/3)) {
00775       berr = BW_WEIGHTS_BALANCE_MID_ERROR;
00776       goto out;
00777     }
00778   }
00779 
00780  out:
00781   if (berr) {
00782     log_info(LD_DIR,
00783              "Bw weight mismatch %d. G="I64_FORMAT" M="I64_FORMAT
00784              " E="I64_FORMAT" D="I64_FORMAT" T="I64_FORMAT
00785              " Wmd=%d Wme=%d Wmg=%d Wed=%d Wee=%d"
00786              " Wgd=%d Wgg=%d Wme=%d Wmg=%d",
00787              berr,
00788              I64_PRINTF_ARG(G), I64_PRINTF_ARG(M), I64_PRINTF_ARG(E),
00789              I64_PRINTF_ARG(D), I64_PRINTF_ARG(T),
00790              (int)Wmd, (int)Wme, (int)Wmg, (int)Wed, (int)Wee,
00791              (int)Wgd, (int)Wgg, (int)Wme, (int)Wmg);
00792   }
00793 
00794   return berr;
00795 }
00796 
00802 static int
00803 networkstatus_compute_bw_weights_v10(smartlist_t *chunks, int64_t G,
00804                                      int64_t M, int64_t E, int64_t D,
00805                                      int64_t T, int64_t weight_scale)
00806 {
00807   bw_weights_error_t berr = 0;
00808   int64_t Wgg = -1, Wgd = -1;
00809   int64_t Wmg = -1, Wme = -1, Wmd = -1;
00810   int64_t Wed = -1, Wee = -1;
00811   const char *casename;
00812 
00813   if (G <= 0 || M <= 0 || E <= 0 || D <= 0) {
00814     log_warn(LD_DIR, "Consensus with empty bandwidth: "
00815                      "G="I64_FORMAT" M="I64_FORMAT" E="I64_FORMAT
00816                      " D="I64_FORMAT" T="I64_FORMAT,
00817              I64_PRINTF_ARG(G), I64_PRINTF_ARG(M), I64_PRINTF_ARG(E),
00818              I64_PRINTF_ARG(D), I64_PRINTF_ARG(T));
00819     return 0;
00820   }
00821 
00822   /*
00823    * Computed from cases in 3.4.3 of dir-spec.txt
00824    *
00825    * 1. Neither are scarce
00826    * 2. Both Guard and Exit are scarce
00827    *    a. R+D <= S
00828    *    b. R+D > S
00829    * 3. One of Guard or Exit is scarce
00830    *    a. S+D < T/3
00831    *    b. S+D >= T/3
00832    */
00833   if (3*E >= T && 3*G >= T) { // E >= T/3 && G >= T/3
00834     /* Case 1: Neither are scarce.  */
00835     casename = "Case 1 (Wgd=Wmd=Wed)";
00836     Wgd = weight_scale/3;
00837     Wed = weight_scale/3;
00838     Wmd = weight_scale/3;
00839     Wee = (weight_scale*(E+G+M))/(3*E);
00840     Wme = weight_scale - Wee;
00841     Wmg = (weight_scale*(2*G-E-M))/(3*G);
00842     Wgg = weight_scale - Wmg;
00843 
00844     berr = networkstatus_check_weights(Wgg, Wgd, Wmg, Wme, Wmd, Wee, Wed,
00845                                        weight_scale, G, M, E, D, T, 10, 1);
00846 
00847     if (berr) {
00848       log_warn(LD_DIR,
00849              "Bw Weights error %d for %s v10. G="I64_FORMAT" M="I64_FORMAT
00850              " E="I64_FORMAT" D="I64_FORMAT" T="I64_FORMAT
00851              " Wmd=%d Wme=%d Wmg=%d Wed=%d Wee=%d"
00852              " Wgd=%d Wgg=%d Wme=%d Wmg=%d weight_scale=%d",
00853              berr, casename,
00854              I64_PRINTF_ARG(G), I64_PRINTF_ARG(M), I64_PRINTF_ARG(E),
00855              I64_PRINTF_ARG(D), I64_PRINTF_ARG(T),
00856              (int)Wmd, (int)Wme, (int)Wmg, (int)Wed, (int)Wee,
00857              (int)Wgd, (int)Wgg, (int)Wme, (int)Wmg, (int)weight_scale);
00858       return 0;
00859     }
00860   } else if (3*E < T && 3*G < T) { // E < T/3 && G < T/3
00861     int64_t R = MIN(E, G);
00862     int64_t S = MAX(E, G);
00863     /*
00864      * Case 2: Both Guards and Exits are scarce
00865      * Balance D between E and G, depending upon
00866      * D capacity and scarcity.
00867      */
00868     if (R+D < S) { // Subcase a
00869       Wgg = weight_scale;
00870       Wee = weight_scale;
00871       Wmg = 0;
00872       Wme = 0;
00873       Wmd = 0;
00874       if (E < G) {
00875         casename = "Case 2a (E scarce)";
00876         Wed = weight_scale;
00877         Wgd = 0;
00878       } else { /* E >= G */
00879         casename = "Case 2a (G scarce)";
00880         Wed = 0;
00881         Wgd = weight_scale;
00882       }
00883     } else { // Subcase b: R+D >= S
00884       casename = "Case 2b1 (Wgg=1, Wmd=Wgd)";
00885       Wee = (weight_scale*(E - G + M))/E;
00886       Wed = (weight_scale*(D - 2*E + 4*G - 2*M))/(3*D);
00887       Wme = (weight_scale*(G-M))/E;
00888       Wmg = 0;
00889       Wgg = weight_scale;
00890       Wmd = (weight_scale - Wed)/2;
00891       Wgd = (weight_scale - Wed)/2;
00892 
00893       berr = networkstatus_check_weights(Wgg, Wgd, Wmg, Wme, Wmd, Wee, Wed,
00894                                        weight_scale, G, M, E, D, T, 10, 1);
00895 
00896       if (berr) {
00897         casename = "Case 2b2 (Wgg=1, Wee=1)";
00898         Wgg = weight_scale;
00899         Wee = weight_scale;
00900         Wed = (weight_scale*(D - 2*E + G + M))/(3*D);
00901         Wmd = (weight_scale*(D - 2*M + G + E))/(3*D);
00902         Wme = 0;
00903         Wmg = 0;
00904 
00905         if (Wmd < 0) { // Can happen if M > T/3
00906           casename = "Case 2b3 (Wmd=0)";
00907           Wmd = 0;
00908           log_warn(LD_DIR,
00909                    "Too much Middle bandwidth on the network to calculate "
00910                    "balanced bandwidth-weights. Consider increasing the "
00911                    "number of Guard nodes by lowering the requirements.");
00912         }
00913         Wgd = weight_scale - Wed - Wmd;
00914         berr = networkstatus_check_weights(Wgg, Wgd, Wmg, Wme, Wmd, Wee,
00915                   Wed, weight_scale, G, M, E, D, T, 10, 1);
00916       }
00917       if (berr != BW_WEIGHTS_NO_ERROR &&
00918               berr != BW_WEIGHTS_BALANCE_MID_ERROR) {
00919         log_warn(LD_DIR,
00920              "Bw Weights error %d for %s v10. G="I64_FORMAT" M="I64_FORMAT
00921              " E="I64_FORMAT" D="I64_FORMAT" T="I64_FORMAT
00922              " Wmd=%d Wme=%d Wmg=%d Wed=%d Wee=%d"
00923              " Wgd=%d Wgg=%d Wme=%d Wmg=%d weight_scale=%d",
00924              berr, casename,
00925              I64_PRINTF_ARG(G), I64_PRINTF_ARG(M), I64_PRINTF_ARG(E),
00926              I64_PRINTF_ARG(D), I64_PRINTF_ARG(T),
00927              (int)Wmd, (int)Wme, (int)Wmg, (int)Wed, (int)Wee,
00928              (int)Wgd, (int)Wgg, (int)Wme, (int)Wmg, (int)weight_scale);
00929         return 0;
00930       }
00931     }
00932   } else { // if (E < T/3 || G < T/3) {
00933     int64_t S = MIN(E, G);
00934     // Case 3: Exactly one of Guard or Exit is scarce
00935     if (!(3*E < T || 3*G < T) || !(3*G >= T || 3*E >= T)) {
00936       log_warn(LD_BUG,
00937            "Bw-Weights Case 3 v10 but with G="I64_FORMAT" M="
00938            I64_FORMAT" E="I64_FORMAT" D="I64_FORMAT" T="I64_FORMAT,
00939                I64_PRINTF_ARG(G), I64_PRINTF_ARG(M), I64_PRINTF_ARG(E),
00940                I64_PRINTF_ARG(D), I64_PRINTF_ARG(T));
00941     }
00942 
00943     if (3*(S+D) < T) { // Subcase a: S+D < T/3
00944       if (G < E) {
00945         casename = "Case 3a (G scarce)";
00946         Wgg = Wgd = weight_scale;
00947         Wmd = Wed = Wmg = 0;
00948         // Minor subcase, if E is more scarce than M,
00949         // keep its bandwidth in place.
00950         if (E < M) Wme = 0;
00951         else Wme = (weight_scale*(E-M))/(2*E);
00952         Wee = weight_scale-Wme;
00953       } else { // G >= E
00954         casename = "Case 3a (E scarce)";
00955         Wee = Wed = weight_scale;
00956         Wmd = Wgd = Wme = 0;
00957         // Minor subcase, if G is more scarce than M,
00958         // keep its bandwidth in place.
00959         if (G < M) Wmg = 0;
00960         else Wmg = (weight_scale*(G-M))/(2*G);
00961         Wgg = weight_scale-Wmg;
00962       }
00963     } else { // Subcase b: S+D >= T/3
00964       // D != 0 because S+D >= T/3
00965       if (G < E) {
00966         casename = "Case 3bg (G scarce, Wgg=1, Wmd == Wed)";
00967         Wgg = weight_scale;
00968         Wgd = (weight_scale*(D - 2*G + E + M))/(3*D);
00969         Wmg = 0;
00970         Wee = (weight_scale*(E+M))/(2*E);
00971         Wme = weight_scale - Wee;
00972         Wmd = (weight_scale - Wgd)/2;
00973         Wed = (weight_scale - Wgd)/2;
00974 
00975         berr = networkstatus_check_weights(Wgg, Wgd, Wmg, Wme, Wmd, Wee,
00976                     Wed, weight_scale, G, M, E, D, T, 10, 1);
00977       } else { // G >= E
00978         casename = "Case 3be (E scarce, Wee=1, Wmd == Wgd)";
00979         Wee = weight_scale;
00980         Wed = (weight_scale*(D - 2*E + G + M))/(3*D);
00981         Wme = 0;
00982         Wgg = (weight_scale*(G+M))/(2*G);
00983         Wmg = weight_scale - Wgg;
00984         Wmd = (weight_scale - Wed)/2;
00985         Wgd = (weight_scale - Wed)/2;
00986 
00987         berr = networkstatus_check_weights(Wgg, Wgd, Wmg, Wme, Wmd, Wee,
00988                       Wed, weight_scale, G, M, E, D, T, 10, 1);
00989       }
00990       if (berr) {
00991         log_warn(LD_DIR,
00992              "Bw Weights error %d for %s v10. G="I64_FORMAT" M="I64_FORMAT
00993              " E="I64_FORMAT" D="I64_FORMAT" T="I64_FORMAT
00994              " Wmd=%d Wme=%d Wmg=%d Wed=%d Wee=%d"
00995              " Wgd=%d Wgg=%d Wme=%d Wmg=%d weight_scale=%d",
00996              berr, casename,
00997              I64_PRINTF_ARG(G), I64_PRINTF_ARG(M), I64_PRINTF_ARG(E),
00998              I64_PRINTF_ARG(D), I64_PRINTF_ARG(T),
00999              (int)Wmd, (int)Wme, (int)Wmg, (int)Wed, (int)Wee,
01000              (int)Wgd, (int)Wgg, (int)Wme, (int)Wmg, (int)weight_scale);
01001         return 0;
01002       }
01003     }
01004   }
01005 
01006   /* We cast down the weights to 32 bit ints on the assumption that
01007    * weight_scale is ~= 10000. We need to ensure a rogue authority
01008    * doesn't break this assumption to rig our weights */
01009   tor_assert(0 < weight_scale && weight_scale <= INT32_MAX);
01010 
01011   /*
01012    * Provide Wgm=Wgg, Wmm=1, Wem=Wee, Weg=Wed. May later determine
01013    * that middle nodes need different bandwidth weights for dirport traffic,
01014    * or that weird exit policies need special weight, or that bridges
01015    * need special weight.
01016    *
01017    * NOTE: This list is sorted.
01018    */
01019   smartlist_add_asprintf(chunks,
01020      "bandwidth-weights Wbd=%d Wbe=%d Wbg=%d Wbm=%d "
01021      "Wdb=%d "
01022      "Web=%d Wed=%d Wee=%d Weg=%d Wem=%d "
01023      "Wgb=%d Wgd=%d Wgg=%d Wgm=%d "
01024      "Wmb=%d Wmd=%d Wme=%d Wmg=%d Wmm=%d\n",
01025      (int)Wmd, (int)Wme, (int)Wmg, (int)weight_scale,
01026      (int)weight_scale,
01027      (int)weight_scale, (int)Wed, (int)Wee, (int)Wed, (int)Wee,
01028      (int)weight_scale, (int)Wgd, (int)Wgg, (int)Wgg,
01029      (int)weight_scale, (int)Wmd, (int)Wme, (int)Wmg, (int)weight_scale);
01030 
01031   log_notice(LD_CIRC, "Computed bandwidth weights for %s with v10: "
01032              "G="I64_FORMAT" M="I64_FORMAT" E="I64_FORMAT" D="I64_FORMAT
01033              " T="I64_FORMAT,
01034              casename,
01035              I64_PRINTF_ARG(G), I64_PRINTF_ARG(M), I64_PRINTF_ARG(E),
01036              I64_PRINTF_ARG(D), I64_PRINTF_ARG(T));
01037   return 1;
01038 }
01044 static void
01045 networkstatus_compute_bw_weights_v9(smartlist_t *chunks, int64_t G, int64_t M,
01046                               int64_t E, int64_t D, int64_t T,
01047                               int64_t weight_scale)
01048 {
01049   int64_t Wgg = -1, Wgd = -1;
01050   int64_t Wmg = -1, Wme = -1, Wmd = -1;
01051   int64_t Wed = -1, Wee = -1;
01052   const char *casename;
01053 
01054   if (G <= 0 || M <= 0 || E <= 0 || D <= 0) {
01055     log_warn(LD_DIR, "Consensus with empty bandwidth: "
01056                      "G="I64_FORMAT" M="I64_FORMAT" E="I64_FORMAT
01057                      " D="I64_FORMAT" T="I64_FORMAT,
01058              I64_PRINTF_ARG(G), I64_PRINTF_ARG(M), I64_PRINTF_ARG(E),
01059              I64_PRINTF_ARG(D), I64_PRINTF_ARG(T));
01060     return;
01061   }
01062 
01063   /*
01064    * Computed from cases in 3.4.3 of dir-spec.txt
01065    *
01066    * 1. Neither are scarce
01067    * 2. Both Guard and Exit are scarce
01068    *    a. R+D <= S
01069    *    b. R+D > S
01070    * 3. One of Guard or Exit is scarce
01071    *    a. S+D < T/3
01072    *    b. S+D >= T/3
01073    */
01074   if (3*E >= T && 3*G >= T) { // E >= T/3 && G >= T/3
01075     bw_weights_error_t berr = 0;
01076     /* Case 1: Neither are scarce.
01077      *
01078      * Attempt to ensure that we have a large amount of exit bandwidth
01079      * in the middle position.
01080      */
01081     casename = "Case 1 (Wme*E = Wmd*D)";
01082     Wgg = (weight_scale*(D+E+G+M))/(3*G);
01083     if (D==0) Wmd = 0;
01084     else Wmd = (weight_scale*(2*D + 2*E - G - M))/(6*D);
01085     Wme = (weight_scale*(2*D + 2*E - G - M))/(6*E);
01086     Wee = (weight_scale*(-2*D + 4*E + G + M))/(6*E);
01087     Wgd = 0;
01088     Wmg = weight_scale - Wgg;
01089     Wed = weight_scale - Wmd;
01090 
01091     berr = networkstatus_check_weights(Wgg, Wgd, Wmg, Wme, Wmd, Wee, Wed,
01092                                        weight_scale, G, M, E, D, T, 10, 1);
01093 
01094     if (berr) {
01095       log_warn(LD_DIR, "Bw Weights error %d for case %s. "
01096                        "G="I64_FORMAT" M="I64_FORMAT" E="I64_FORMAT
01097                        " D="I64_FORMAT" T="I64_FORMAT,
01098                berr, casename,
01099                I64_PRINTF_ARG(G), I64_PRINTF_ARG(M), I64_PRINTF_ARG(E),
01100                I64_PRINTF_ARG(D), I64_PRINTF_ARG(T));
01101     }
01102   } else if (3*E < T && 3*G < T) { // E < T/3 && G < T/3
01103     int64_t R = MIN(E, G);
01104     int64_t S = MAX(E, G);
01105     /*
01106      * Case 2: Both Guards and Exits are scarce
01107      * Balance D between E and G, depending upon
01108      * D capacity and scarcity.
01109      */
01110     if (R+D < S) { // Subcase a
01111       Wgg = weight_scale;
01112       Wee = weight_scale;
01113       Wmg = 0;
01114       Wme = 0;
01115       Wmd = 0;
01116       if (E < G) {
01117         casename = "Case 2a (E scarce)";
01118         Wed = weight_scale;
01119         Wgd = 0;
01120       } else { /* E >= G */
01121         casename = "Case 2a (G scarce)";
01122         Wed = 0;
01123         Wgd = weight_scale;
01124       }
01125     } else { // Subcase b: R+D > S
01126       bw_weights_error_t berr = 0;
01127       casename = "Case 2b (Wme*E == Wmd*D)";
01128       if (D != 0) {
01129         Wgg = weight_scale;
01130         Wgd = (weight_scale*(D + E - 2*G + M))/(3*D); // T/3 >= G (Ok)
01131         Wmd = (weight_scale*(D + E + G - 2*M))/(6*D); // T/3 >= M
01132         Wme = (weight_scale*(D + E + G - 2*M))/(6*E);
01133         Wee = (weight_scale*(-D + 5*E - G + 2*M))/(6*E); // 2E+M >= T/3
01134         Wmg = 0;
01135         Wed = weight_scale - Wgd - Wmd;
01136 
01137         berr = networkstatus_check_weights(Wgg, Wgd, Wmg, Wme, Wmd, Wee, Wed,
01138                                        weight_scale, G, M, E, D, T, 10, 1);
01139       }
01140 
01141       if (D == 0 || berr) { // Can happen if M > T/3
01142         casename = "Case 2b (E=G)";
01143         Wgg = weight_scale;
01144         Wee = weight_scale;
01145         Wmg = 0;
01146         Wme = 0;
01147         Wmd = 0;
01148         if (D == 0) Wgd = 0;
01149         else Wgd = (weight_scale*(D+E-G))/(2*D);
01150         Wed = weight_scale - Wgd;
01151         berr = networkstatus_check_weights(Wgg, Wgd, Wmg, Wme, Wmd, Wee,
01152                 Wed, weight_scale, G, M, E, D, T, 10, 1);
01153       }
01154       if (berr != BW_WEIGHTS_NO_ERROR &&
01155               berr != BW_WEIGHTS_BALANCE_MID_ERROR) {
01156         log_warn(LD_DIR, "Bw Weights error %d for case %s. "
01157                          "G="I64_FORMAT" M="I64_FORMAT" E="I64_FORMAT
01158                          " D="I64_FORMAT" T="I64_FORMAT,
01159                  berr, casename,
01160                  I64_PRINTF_ARG(G), I64_PRINTF_ARG(M), I64_PRINTF_ARG(E),
01161                  I64_PRINTF_ARG(D), I64_PRINTF_ARG(T));
01162       }
01163     }
01164   } else { // if (E < T/3 || G < T/3) {
01165     int64_t S = MIN(E, G);
01166     // Case 3: Exactly one of Guard or Exit is scarce
01167     if (!(3*E < T || 3*G < T) || !(3*G >= T || 3*E >= T)) {
01168       log_warn(LD_BUG,
01169            "Bw-Weights Case 3 but with G="I64_FORMAT" M="
01170            I64_FORMAT" E="I64_FORMAT" D="I64_FORMAT" T="I64_FORMAT,
01171                I64_PRINTF_ARG(G), I64_PRINTF_ARG(M), I64_PRINTF_ARG(E),
01172                I64_PRINTF_ARG(D), I64_PRINTF_ARG(T));
01173     }
01174 
01175     if (3*(S+D) < T) { // Subcase a: S+D < T/3
01176       if (G < E) {
01177         casename = "Case 3a (G scarce)";
01178         Wgg = Wgd = weight_scale;
01179         Wmd = Wed = Wmg = 0;
01180         // Minor subcase, if E is more scarce than M,
01181         // keep its bandwidth in place.
01182         if (E < M) Wme = 0;
01183         else Wme = (weight_scale*(E-M))/(2*E);
01184         Wee = weight_scale-Wme;
01185       } else { // G >= E
01186         casename = "Case 3a (E scarce)";
01187         Wee = Wed = weight_scale;
01188         Wmd = Wgd = Wme = 0;
01189         // Minor subcase, if G is more scarce than M,
01190         // keep its bandwidth in place.
01191         if (G < M) Wmg = 0;
01192         else Wmg = (weight_scale*(G-M))/(2*G);
01193         Wgg = weight_scale-Wmg;
01194       }
01195     } else { // Subcase b: S+D >= T/3
01196       bw_weights_error_t berr = 0;
01197       // D != 0 because S+D >= T/3
01198       if (G < E) {
01199         casename = "Case 3b (G scarce, Wme*E == Wmd*D)";
01200         Wgd = (weight_scale*(D + E - 2*G + M))/(3*D);
01201         Wmd = (weight_scale*(D + E + G - 2*M))/(6*D);
01202         Wme = (weight_scale*(D + E + G - 2*M))/(6*E);
01203         Wee = (weight_scale*(-D + 5*E - G + 2*M))/(6*E);
01204         Wgg = weight_scale;
01205         Wmg = 0;
01206         Wed = weight_scale - Wgd - Wmd;
01207 
01208         berr = networkstatus_check_weights(Wgg, Wgd, Wmg, Wme, Wmd, Wee,
01209                     Wed, weight_scale, G, M, E, D, T, 10, 1);
01210       } else { // G >= E
01211         casename = "Case 3b (E scarce, Wme*E == Wmd*D)";
01212         Wgg = (weight_scale*(D + E + G + M))/(3*G);
01213         Wmd = (weight_scale*(2*D + 2*E - G - M))/(6*D);
01214         Wme = (weight_scale*(2*D + 2*E - G - M))/(6*E);
01215         Wee = (weight_scale*(-2*D + 4*E + G + M))/(6*E);
01216         Wgd = 0;
01217         Wmg = weight_scale - Wgg;
01218         Wed = weight_scale - Wmd;
01219 
01220         berr = networkstatus_check_weights(Wgg, Wgd, Wmg, Wme, Wmd, Wee,
01221                       Wed, weight_scale, G, M, E, D, T, 10, 1);
01222       }
01223       if (berr) {
01224         log_warn(LD_DIR, "Bw Weights error %d for case %s. "
01225                          "G="I64_FORMAT" M="I64_FORMAT
01226                          " E="I64_FORMAT" D="I64_FORMAT" T="I64_FORMAT,
01227                  berr, casename,
01228                I64_PRINTF_ARG(G), I64_PRINTF_ARG(M), I64_PRINTF_ARG(E),
01229                I64_PRINTF_ARG(D), I64_PRINTF_ARG(T));
01230       }
01231     }
01232   }
01233 
01234   /* We cast down the weights to 32 bit ints on the assumption that
01235    * weight_scale is ~= 10000. We need to ensure a rogue authority
01236    * doesn't break this assumption to rig our weights */
01237   tor_assert(0 < weight_scale && weight_scale <= INT32_MAX);
01238 
01239   if (Wgg < 0 || Wgg > weight_scale) {
01240     log_warn(LD_DIR, "Bw %s: Wgg="I64_FORMAT"! G="I64_FORMAT
01241             " M="I64_FORMAT" E="I64_FORMAT" D="I64_FORMAT
01242             " T="I64_FORMAT,
01243              casename, I64_PRINTF_ARG(Wgg),
01244              I64_PRINTF_ARG(G), I64_PRINTF_ARG(M), I64_PRINTF_ARG(E),
01245              I64_PRINTF_ARG(D), I64_PRINTF_ARG(T));
01246 
01247     Wgg = MAX(MIN(Wgg, weight_scale), 0);
01248   }
01249   if (Wgd < 0 || Wgd > weight_scale) {
01250     log_warn(LD_DIR, "Bw %s: Wgd="I64_FORMAT"! G="I64_FORMAT
01251             " M="I64_FORMAT" E="I64_FORMAT" D="I64_FORMAT
01252             " T="I64_FORMAT,
01253              casename, I64_PRINTF_ARG(Wgd),
01254              I64_PRINTF_ARG(G), I64_PRINTF_ARG(M), I64_PRINTF_ARG(E),
01255              I64_PRINTF_ARG(D), I64_PRINTF_ARG(T));
01256     Wgd = MAX(MIN(Wgd, weight_scale), 0);
01257   }
01258   if (Wmg < 0 || Wmg > weight_scale) {
01259     log_warn(LD_DIR, "Bw %s: Wmg="I64_FORMAT"! G="I64_FORMAT
01260             " M="I64_FORMAT" E="I64_FORMAT" D="I64_FORMAT
01261             " T="I64_FORMAT,
01262              casename, I64_PRINTF_ARG(Wmg),
01263              I64_PRINTF_ARG(G), I64_PRINTF_ARG(M), I64_PRINTF_ARG(E),
01264              I64_PRINTF_ARG(D), I64_PRINTF_ARG(T));
01265     Wmg = MAX(MIN(Wmg, weight_scale), 0);
01266   }
01267   if (Wme < 0 || Wme > weight_scale) {
01268     log_warn(LD_DIR, "Bw %s: Wme="I64_FORMAT"! G="I64_FORMAT
01269             " M="I64_FORMAT" E="I64_FORMAT" D="I64_FORMAT
01270             " T="I64_FORMAT,
01271              casename, I64_PRINTF_ARG(Wme),
01272              I64_PRINTF_ARG(G), I64_PRINTF_ARG(M), I64_PRINTF_ARG(E),
01273              I64_PRINTF_ARG(D), I64_PRINTF_ARG(T));
01274     Wme = MAX(MIN(Wme, weight_scale), 0);
01275   }
01276   if (Wmd < 0 || Wmd > weight_scale) {
01277     log_warn(LD_DIR, "Bw %s: Wmd="I64_FORMAT"! G="I64_FORMAT
01278             " M="I64_FORMAT" E="I64_FORMAT" D="I64_FORMAT
01279             " T="I64_FORMAT,
01280              casename, I64_PRINTF_ARG(Wmd),
01281              I64_PRINTF_ARG(G), I64_PRINTF_ARG(M), I64_PRINTF_ARG(E),
01282              I64_PRINTF_ARG(D), I64_PRINTF_ARG(T));
01283     Wmd = MAX(MIN(Wmd, weight_scale), 0);
01284   }
01285   if (Wee < 0 || Wee > weight_scale) {
01286     log_warn(LD_DIR, "Bw %s: Wee="I64_FORMAT"! G="I64_FORMAT
01287             " M="I64_FORMAT" E="I64_FORMAT" D="I64_FORMAT
01288             " T="I64_FORMAT,
01289              casename, I64_PRINTF_ARG(Wee),
01290              I64_PRINTF_ARG(G), I64_PRINTF_ARG(M), I64_PRINTF_ARG(E),
01291              I64_PRINTF_ARG(D), I64_PRINTF_ARG(T));
01292     Wee = MAX(MIN(Wee, weight_scale), 0);
01293   }
01294   if (Wed < 0 || Wed > weight_scale) {
01295     log_warn(LD_DIR, "Bw %s: Wed="I64_FORMAT"! G="I64_FORMAT
01296             " M="I64_FORMAT" E="I64_FORMAT" D="I64_FORMAT
01297             " T="I64_FORMAT,
01298              casename, I64_PRINTF_ARG(Wed),
01299              I64_PRINTF_ARG(G), I64_PRINTF_ARG(M), I64_PRINTF_ARG(E),
01300              I64_PRINTF_ARG(D), I64_PRINTF_ARG(T));
01301     Wed = MAX(MIN(Wed, weight_scale), 0);
01302   }
01303 
01304   // Add consensus weight keywords
01305   smartlist_add(chunks, tor_strdup("bandwidth-weights "));
01306   /*
01307    * Provide Wgm=Wgg, Wmm=1, Wem=Wee, Weg=Wed. May later determine
01308    * that middle nodes need different bandwidth weights for dirport traffic,
01309    * or that weird exit policies need special weight, or that bridges
01310    * need special weight.
01311    *
01312    * NOTE: This list is sorted.
01313    */
01314   smartlist_add_asprintf(chunks,
01315      "Wbd=%d Wbe=%d Wbg=%d Wbm=%d "
01316      "Wdb=%d "
01317      "Web=%d Wed=%d Wee=%d Weg=%d Wem=%d "
01318      "Wgb=%d Wgd=%d Wgg=%d Wgm=%d "
01319      "Wmb=%d Wmd=%d Wme=%d Wmg=%d Wmm=%d\n",
01320      (int)Wmd, (int)Wme, (int)Wmg, (int)weight_scale,
01321      (int)weight_scale,
01322      (int)weight_scale, (int)Wed, (int)Wee, (int)Wed, (int)Wee,
01323      (int)weight_scale, (int)Wgd, (int)Wgg, (int)Wgg,
01324      (int)weight_scale, (int)Wmd, (int)Wme, (int)Wmg, (int)weight_scale);
01325 
01326   log_notice(LD_CIRC, "Computed bandwidth weights for %s with v9: "
01327              "G="I64_FORMAT" M="I64_FORMAT" E="I64_FORMAT" D="I64_FORMAT
01328              " T="I64_FORMAT,
01329              casename,
01330              I64_PRINTF_ARG(G), I64_PRINTF_ARG(M), I64_PRINTF_ARG(E),
01331              I64_PRINTF_ARG(D), I64_PRINTF_ARG(T));
01332 }
01333 
01342 char *
01343 networkstatus_compute_consensus(smartlist_t *votes,
01344                                 int total_authorities,
01345                                 crypto_pk_t *identity_key,
01346                                 crypto_pk_t *signing_key,
01347                                 const char *legacy_id_key_digest,
01348                                 crypto_pk_t *legacy_signing_key,
01349                                 consensus_flavor_t flavor)
01350 {
01351   smartlist_t *chunks;
01352   char *result = NULL;
01353   int consensus_method;
01354   time_t valid_after, fresh_until, valid_until;
01355   int vote_seconds, dist_seconds;
01356   char *client_versions = NULL, *server_versions = NULL;
01357   smartlist_t *flags;
01358   const char *flavor_name;
01359   int64_t G=0, M=0, E=0, D=0, T=0; /* For bandwidth weights */
01360   const routerstatus_format_type_t rs_format =
01361     flavor == FLAV_NS ? NS_V3_CONSENSUS : NS_V3_CONSENSUS_MICRODESC;
01362   char *params = NULL;
01363   int added_weights = 0;
01364   tor_assert(flavor == FLAV_NS || flavor == FLAV_MICRODESC);
01365   tor_assert(total_authorities >= smartlist_len(votes));
01366 
01367   flavor_name = networkstatus_get_flavor_name(flavor);
01368 
01369   if (!smartlist_len(votes)) {
01370     log_warn(LD_DIR, "Can't compute a consensus from no votes.");
01371     return NULL;
01372   }
01373   flags = smartlist_new();
01374 
01375   consensus_method = compute_consensus_method(votes);
01376   if (consensus_method_is_supported(consensus_method)) {
01377     log_info(LD_DIR, "Generating consensus using method %d.",
01378              consensus_method);
01379   } else {
01380     log_warn(LD_DIR, "The other authorities will use consensus method %d, "
01381              "which I don't support.  Maybe I should upgrade!",
01382              consensus_method);
01383     consensus_method = 1;
01384   }
01385 
01386   /* Compute medians of time-related things, and figure out how many
01387    * routers we might need to talk about. */
01388   {
01389     int n_votes = smartlist_len(votes);
01390     time_t *va_times = tor_malloc(n_votes * sizeof(time_t));
01391     time_t *fu_times = tor_malloc(n_votes * sizeof(time_t));
01392     time_t *vu_times = tor_malloc(n_votes * sizeof(time_t));
01393     int *votesec_list = tor_malloc(n_votes * sizeof(int));
01394     int *distsec_list = tor_malloc(n_votes * sizeof(int));
01395     int n_versioning_clients = 0, n_versioning_servers = 0;
01396     smartlist_t *combined_client_versions = smartlist_new();
01397     smartlist_t *combined_server_versions = smartlist_new();
01398 
01399     SMARTLIST_FOREACH_BEGIN(votes, networkstatus_t *, v) {
01400       tor_assert(v->type == NS_TYPE_VOTE);
01401       va_times[v_sl_idx] = v->valid_after;
01402       fu_times[v_sl_idx] = v->fresh_until;
01403       vu_times[v_sl_idx] = v->valid_until;
01404       votesec_list[v_sl_idx] = v->vote_seconds;
01405       distsec_list[v_sl_idx] = v->dist_seconds;
01406       if (v->client_versions) {
01407         smartlist_t *cv = smartlist_new();
01408         ++n_versioning_clients;
01409         smartlist_split_string(cv, v->client_versions, ",",
01410                                SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
01411         sort_version_list(cv, 1);
01412         smartlist_add_all(combined_client_versions, cv);
01413         smartlist_free(cv); /* elements get freed later. */
01414       }
01415       if (v->server_versions) {
01416         smartlist_t *sv = smartlist_new();
01417         ++n_versioning_servers;
01418         smartlist_split_string(sv, v->server_versions, ",",
01419                                SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
01420         sort_version_list(sv, 1);
01421         smartlist_add_all(combined_server_versions, sv);
01422         smartlist_free(sv); /* elements get freed later. */
01423       }
01424       SMARTLIST_FOREACH(v->known_flags, const char *, cp,
01425                         smartlist_add(flags, tor_strdup(cp)));
01426     } SMARTLIST_FOREACH_END(v);
01427     valid_after = median_time(va_times, n_votes);
01428     fresh_until = median_time(fu_times, n_votes);
01429     valid_until = median_time(vu_times, n_votes);
01430     vote_seconds = median_int(votesec_list, n_votes);
01431     dist_seconds = median_int(distsec_list, n_votes);
01432 
01433     tor_assert(valid_after+MIN_VOTE_INTERVAL <= fresh_until);
01434     tor_assert(fresh_until+MIN_VOTE_INTERVAL <= valid_until);
01435     tor_assert(vote_seconds >= MIN_VOTE_SECONDS);
01436     tor_assert(dist_seconds >= MIN_DIST_SECONDS);
01437 
01438     server_versions = compute_consensus_versions_list(combined_server_versions,
01439                                                       n_versioning_servers);
01440     client_versions = compute_consensus_versions_list(combined_client_versions,
01441                                                       n_versioning_clients);
01442 
01443     SMARTLIST_FOREACH(combined_server_versions, char *, cp, tor_free(cp));
01444     SMARTLIST_FOREACH(combined_client_versions, char *, cp, tor_free(cp));
01445     smartlist_free(combined_server_versions);
01446     smartlist_free(combined_client_versions);
01447 
01448     smartlist_sort_strings(flags);
01449     smartlist_uniq_strings(flags);
01450 
01451     tor_free(va_times);
01452     tor_free(fu_times);
01453     tor_free(vu_times);
01454     tor_free(votesec_list);
01455     tor_free(distsec_list);
01456   }
01457 
01458   chunks = smartlist_new();
01459 
01460   {
01461     char va_buf[ISO_TIME_LEN+1], fu_buf[ISO_TIME_LEN+1],
01462       vu_buf[ISO_TIME_LEN+1];
01463     char *flaglist;
01464     format_iso_time(va_buf, valid_after);
01465     format_iso_time(fu_buf, fresh_until);
01466     format_iso_time(vu_buf, valid_until);
01467     flaglist = smartlist_join_strings(flags, " ", 0, NULL);
01468 
01469     smartlist_add_asprintf(chunks, "network-status-version 3%s%s\n"
01470                  "vote-status consensus\n",
01471                  flavor == FLAV_NS ? "" : " ",
01472                  flavor == FLAV_NS ? "" : flavor_name);
01473 
01474     if (consensus_method >= 2) {
01475       smartlist_add_asprintf(chunks, "consensus-method %d\n",
01476                    consensus_method);
01477     }
01478 
01479     smartlist_add_asprintf(chunks,
01480                  "valid-after %s\n"
01481                  "fresh-until %s\n"
01482                  "valid-until %s\n"
01483                  "voting-delay %d %d\n"
01484                  "client-versions %s\n"
01485                  "server-versions %s\n"
01486                  "known-flags %s\n",
01487                  va_buf, fu_buf, vu_buf,
01488                  vote_seconds, dist_seconds,
01489                  client_versions, server_versions, flaglist);
01490 
01491     tor_free(flaglist);
01492   }
01493 
01494   if (consensus_method >= MIN_METHOD_FOR_PARAMS) {
01495     params = dirvote_compute_params(votes, consensus_method,
01496                                     total_authorities);
01497     if (params) {
01498       smartlist_add(chunks, tor_strdup("params "));
01499       smartlist_add(chunks, params);
01500       smartlist_add(chunks, tor_strdup("\n"));
01501     }
01502   }
01503 
01504   /* Sort the votes. */
01505   smartlist_sort(votes, _compare_votes_by_authority_id);
01506   /* Add the authority sections. */
01507   {
01508     smartlist_t *dir_sources = smartlist_new();
01509     SMARTLIST_FOREACH_BEGIN(votes, networkstatus_t *, v) {
01510       dir_src_ent_t *e = tor_malloc_zero(sizeof(dir_src_ent_t));
01511       e->v = v;
01512       e->digest = get_voter(v)->identity_digest;
01513       e->is_legacy = 0;
01514       smartlist_add(dir_sources, e);
01515       if (consensus_method >= 3 &&
01516           !tor_digest_is_zero(get_voter(v)->legacy_id_digest)) {
01517         dir_src_ent_t *e_legacy = tor_malloc_zero(sizeof(dir_src_ent_t));
01518         e_legacy->v = v;
01519         e_legacy->digest = get_voter(v)->legacy_id_digest;
01520         e_legacy->is_legacy = 1;
01521         smartlist_add(dir_sources, e_legacy);
01522       }
01523     } SMARTLIST_FOREACH_END(v);
01524     smartlist_sort(dir_sources, _compare_dir_src_ents_by_authority_id);
01525 
01526     SMARTLIST_FOREACH_BEGIN(dir_sources, const dir_src_ent_t *, e) {
01527       char fingerprint[HEX_DIGEST_LEN+1];
01528       char votedigest[HEX_DIGEST_LEN+1];
01529       networkstatus_t *v = e->v;
01530       networkstatus_voter_info_t *voter = get_voter(v);
01531 
01532       if (e->is_legacy)
01533         tor_assert(consensus_method >= 2);
01534 
01535       base16_encode(fingerprint, sizeof(fingerprint), e->digest, DIGEST_LEN);
01536       base16_encode(votedigest, sizeof(votedigest), voter->vote_digest,
01537                     DIGEST_LEN);
01538 
01539       smartlist_add_asprintf(chunks,
01540                    "dir-source %s%s %s %s %s %d %d\n",
01541                    voter->nickname, e->is_legacy ? "-legacy" : "",
01542                    fingerprint, voter->address, fmt_addr32(voter->addr),
01543                    voter->dir_port,
01544                    voter->or_port);
01545       if (! e->is_legacy) {
01546         smartlist_add_asprintf(chunks,
01547                      "contact %s\n"
01548                      "vote-digest %s\n",
01549                      voter->contact,
01550                      votedigest);
01551       }
01552     } SMARTLIST_FOREACH_END(e);
01553     SMARTLIST_FOREACH(dir_sources, dir_src_ent_t *, e, tor_free(e));
01554     smartlist_free(dir_sources);
01555   }
01556 
01557   /* Add the actual router entries. */
01558   {
01559     int *index; /* index[j] is the current index into votes[j]. */
01560     int *size; /* size[j] is the number of routerstatuses in votes[j]. */
01561     int *flag_counts; /* The number of voters that list flag[j] for the
01562                        * currently considered router. */
01563     int i;
01564     smartlist_t *matching_descs = smartlist_new();
01565     smartlist_t *chosen_flags = smartlist_new();
01566     smartlist_t *versions = smartlist_new();
01567     smartlist_t *exitsummaries = smartlist_new();
01568     uint32_t *bandwidths = tor_malloc(sizeof(uint32_t) * smartlist_len(votes));
01569     uint32_t *measured_bws = tor_malloc(sizeof(uint32_t) *
01570                                         smartlist_len(votes));
01571     int num_bandwidths;
01572     int num_mbws;
01573 
01574     int *n_voter_flags; /* n_voter_flags[j] is the number of flags that
01575                          * votes[j] knows about. */
01576     int *n_flag_voters; /* n_flag_voters[f] is the number of votes that care
01577                          * about flags[f]. */
01578     int **flag_map; /* flag_map[j][b] is an index f such that flag_map[f]
01579                      * is the same flag as votes[j]->known_flags[b]. */
01580     int *named_flag; /* Index of the flag "Named" for votes[j] */
01581     int *unnamed_flag; /* Index of the flag "Unnamed" for votes[j] */
01582     int chosen_named_idx;
01583 
01584     strmap_t *name_to_id_map = strmap_new();
01585     char conflict[DIGEST_LEN];
01586     char unknown[DIGEST_LEN];
01587     memset(conflict, 0, sizeof(conflict));
01588     memset(unknown, 0xff, sizeof(conflict));
01589 
01590     index = tor_malloc_zero(sizeof(int)*smartlist_len(votes));
01591     size = tor_malloc_zero(sizeof(int)*smartlist_len(votes));
01592     n_voter_flags = tor_malloc_zero(sizeof(int) * smartlist_len(votes));
01593     n_flag_voters = tor_malloc_zero(sizeof(int) * smartlist_len(flags));
01594     flag_map = tor_malloc_zero(sizeof(int*) * smartlist_len(votes));
01595     named_flag = tor_malloc_zero(sizeof(int) * smartlist_len(votes));
01596     unnamed_flag = tor_malloc_zero(sizeof(int) * smartlist_len(votes));
01597     for (i = 0; i < smartlist_len(votes); ++i)
01598       unnamed_flag[i] = named_flag[i] = -1;
01599     chosen_named_idx = smartlist_string_pos(flags, "Named");
01600 
01601     /* Build the flag index. */
01602     SMARTLIST_FOREACH(votes, networkstatus_t *, v,
01603     {
01604       flag_map[v_sl_idx] = tor_malloc_zero(
01605                            sizeof(int)*smartlist_len(v->known_flags));
01606       SMARTLIST_FOREACH(v->known_flags, const char *, fl,
01607       {
01608         int p = smartlist_string_pos(flags, fl);
01609         tor_assert(p >= 0);
01610         flag_map[v_sl_idx][fl_sl_idx] = p;
01611         ++n_flag_voters[p];
01612         if (!strcmp(fl, "Named"))
01613           named_flag[v_sl_idx] = fl_sl_idx;
01614         if (!strcmp(fl, "Unnamed"))
01615           unnamed_flag[v_sl_idx] = fl_sl_idx;
01616       });
01617       n_voter_flags[v_sl_idx] = smartlist_len(v->known_flags);
01618       size[v_sl_idx] = smartlist_len(v->routerstatus_list);
01619     });
01620 
01621     /* Named and Unnamed get treated specially */
01622     if (consensus_method >= 2) {
01623       SMARTLIST_FOREACH(votes, networkstatus_t *, v,
01624       {
01625         uint64_t nf;
01626         if (named_flag[v_sl_idx]<0)
01627           continue;
01628         nf = U64_LITERAL(1) << named_flag[v_sl_idx];
01629         SMARTLIST_FOREACH(v->routerstatus_list, vote_routerstatus_t *, rs,
01630         {
01631           if ((rs->flags & nf) != 0) {
01632             const char *d = strmap_get_lc(name_to_id_map, rs->status.nickname);
01633             if (!d) {
01634               /* We have no name officially mapped to this digest. */
01635               strmap_set_lc(name_to_id_map, rs->status.nickname,
01636                             rs->status.identity_digest);
01637             } else if (d != conflict &&
01638                 fast_memcmp(d, rs->status.identity_digest, DIGEST_LEN)) {
01639               /* Authorities disagree about this nickname. */
01640               strmap_set_lc(name_to_id_map, rs->status.nickname, conflict);
01641             } else {
01642               /* It's already a conflict, or it's already this ID. */
01643             }
01644           }
01645         });
01646       });
01647       SMARTLIST_FOREACH(votes, networkstatus_t *, v,
01648       {
01649         uint64_t uf;
01650         if (unnamed_flag[v_sl_idx]<0)
01651           continue;
01652         uf = U64_LITERAL(1) << unnamed_flag[v_sl_idx];
01653         SMARTLIST_FOREACH(v->routerstatus_list, vote_routerstatus_t *, rs,
01654         {
01655           if ((rs->flags & uf) != 0) {
01656             const char *d = strmap_get_lc(name_to_id_map, rs->status.nickname);
01657             if (d == conflict || d == unknown) {
01658               /* Leave it alone; we know what it is. */
01659             } else if (!d) {
01660               /* We have no name officially mapped to this digest. */
01661               strmap_set_lc(name_to_id_map, rs->status.nickname, unknown);
01662             } else if (fast_memeq(d, rs->status.identity_digest, DIGEST_LEN)) {
01663               /* Authorities disagree about this nickname. */
01664               strmap_set_lc(name_to_id_map, rs->status.nickname, conflict);
01665             } else {
01666               /* It's mapped to a different name. */
01667             }
01668           }
01669         });
01670       });
01671     }
01672 
01673     /* Now go through all the votes */
01674     flag_counts = tor_malloc(sizeof(int) * smartlist_len(flags));
01675     while (1) {
01676       vote_routerstatus_t *rs;
01677       routerstatus_t rs_out;
01678       const char *lowest_id = NULL;
01679       const char *chosen_version;
01680       const char *chosen_name = NULL;
01681       int exitsummary_disagreement = 0;
01682       int is_named = 0, is_unnamed = 0, is_running = 0;
01683       int is_guard = 0, is_exit = 0, is_bad_exit = 0;
01684       int naming_conflict = 0;
01685       int n_listing = 0;
01686       int i;
01687       char microdesc_digest[DIGEST256_LEN];
01688 
01689       /* Of the next-to-be-considered digest in each voter, which is first? */
01690       SMARTLIST_FOREACH(votes, networkstatus_t *, v, {
01691         if (index[v_sl_idx] < size[v_sl_idx]) {
01692           rs = smartlist_get(v->routerstatus_list, index[v_sl_idx]);
01693           if (!lowest_id ||
01694               fast_memcmp(rs->status.identity_digest,
01695                           lowest_id, DIGEST_LEN) < 0)
01696             lowest_id = rs->status.identity_digest;
01697         }
01698       });
01699       if (!lowest_id) /* we're out of routers. */
01700         break;
01701 
01702       memset(flag_counts, 0, sizeof(int)*smartlist_len(flags));
01703       smartlist_clear(matching_descs);
01704       smartlist_clear(chosen_flags);
01705       smartlist_clear(versions);
01706       num_bandwidths = 0;
01707       num_mbws = 0;
01708 
01709       /* Okay, go through all the entries for this digest. */
01710       SMARTLIST_FOREACH_BEGIN(votes, networkstatus_t *, v) {
01711         if (index[v_sl_idx] >= size[v_sl_idx])
01712           continue; /* out of entries. */
01713         rs = smartlist_get(v->routerstatus_list, index[v_sl_idx]);
01714         if (fast_memcmp(rs->status.identity_digest, lowest_id, DIGEST_LEN))
01715           continue; /* doesn't include this router. */
01716         /* At this point, we know that we're looking at a routerstatus with
01717          * identity "lowest".
01718          */
01719         ++index[v_sl_idx];
01720         ++n_listing;
01721 
01722         smartlist_add(matching_descs, rs);
01723         if (rs->version && rs->version[0])
01724           smartlist_add(versions, rs->version);
01725 
01726         /* Tally up all the flags. */
01727         for (i = 0; i < n_voter_flags[v_sl_idx]; ++i) {
01728           if (rs->flags & (U64_LITERAL(1) << i))
01729             ++flag_counts[flag_map[v_sl_idx][i]];
01730         }
01731         if (rs->flags & (U64_LITERAL(1) << named_flag[v_sl_idx])) {
01732           if (chosen_name && strcmp(chosen_name, rs->status.nickname)) {
01733             log_notice(LD_DIR, "Conflict on naming for router: %s vs %s",
01734                        chosen_name, rs->status.nickname);
01735             naming_conflict = 1;
01736           }
01737           chosen_name = rs->status.nickname;
01738         }
01739 
01740         /* count bandwidths */
01741         if (rs->status.has_measured_bw)
01742           measured_bws[num_mbws++] = rs->status.measured_bw;
01743 
01744         if (rs->status.has_bandwidth)
01745           bandwidths[num_bandwidths++] = rs->status.bandwidth;
01746       } SMARTLIST_FOREACH_END(v);
01747 
01748       /* We don't include this router at all unless more than half of
01749        * the authorities we believe in list it. */
01750       if (n_listing <= total_authorities/2)
01751         continue;
01752 
01753       /* Figure out the most popular opinion of what the most recent
01754        * routerinfo and its contents are. */
01755       memset(microdesc_digest, 0, sizeof(microdesc_digest));
01756       rs = compute_routerstatus_consensus(matching_descs, consensus_method,
01757                                           microdesc_digest);
01758       /* Copy bits of that into rs_out. */
01759       tor_assert(fast_memeq(lowest_id, rs->status.identity_digest,DIGEST_LEN));
01760       memcpy(rs_out.identity_digest, lowest_id, DIGEST_LEN);
01761       memcpy(rs_out.descriptor_digest, rs->status.descriptor_digest,
01762              DIGEST_LEN);
01763       rs_out.addr = rs->status.addr;
01764       rs_out.published_on = rs->status.published_on;
01765       rs_out.dir_port = rs->status.dir_port;
01766       rs_out.or_port = rs->status.or_port;
01767       rs_out.has_bandwidth = 0;
01768       rs_out.has_exitsummary = 0;
01769 
01770       if (chosen_name && !naming_conflict) {
01771         strlcpy(rs_out.nickname, chosen_name, sizeof(rs_out.nickname));
01772       } else {
01773         strlcpy(rs_out.nickname, rs->status.nickname, sizeof(rs_out.nickname));
01774       }
01775 
01776       if (consensus_method == 1) {
01777         is_named = chosen_named_idx >= 0 &&
01778           (!naming_conflict && flag_counts[chosen_named_idx]);
01779       } else {
01780         const char *d = strmap_get_lc(name_to_id_map, rs_out.nickname);
01781         if (!d) {
01782           is_named = is_unnamed = 0;
01783         } else if (fast_memeq(d, lowest_id, DIGEST_LEN)) {
01784           is_named = 1; is_unnamed = 0;
01785         } else {
01786           is_named = 0; is_unnamed = 1;
01787         }
01788       }
01789 
01790       /* Set the flags. */
01791       smartlist_add(chosen_flags, (char*)"s"); /* for the start of the line. */
01792       SMARTLIST_FOREACH(flags, const char *, fl,
01793       {
01794         if (!strcmp(fl, "Named")) {
01795           if (is_named)
01796             smartlist_add(chosen_flags, (char*)fl);
01797         } else if (!strcmp(fl, "Unnamed") && consensus_method >= 2) {
01798           if (is_unnamed)
01799             smartlist_add(chosen_flags, (char*)fl);
01800         } else {
01801           if (flag_counts[fl_sl_idx] > n_flag_voters[fl_sl_idx]/2) {
01802             smartlist_add(chosen_flags, (char*)fl);
01803             if (!strcmp(fl, "Exit"))
01804               is_exit = 1;
01805             else if (!strcmp(fl, "Guard"))
01806               is_guard = 1;
01807             else if (!strcmp(fl, "Running"))
01808               is_running = 1;
01809             else if (!strcmp(fl, "BadExit"))
01810               is_bad_exit = 1;
01811           }
01812         }
01813       });
01814 
01815       /* Starting with consensus method 4 we do not list servers
01816        * that are not running in a consensus.  See Proposal 138 */
01817       if (consensus_method >= 4 && !is_running)
01818         continue;
01819 
01820       /* Pick the version. */
01821       if (smartlist_len(versions)) {
01822         sort_version_list(versions, 0);
01823         chosen_version = get_most_frequent_member(versions);
01824       } else {
01825         chosen_version = NULL;
01826       }
01827 
01828       /* Pick a bandwidth */
01829       if (consensus_method >= 6 && num_mbws > 2) {
01830         rs_out.has_bandwidth = 1;
01831         rs_out.bandwidth = median_uint32(measured_bws, num_mbws);
01832       } else if (consensus_method >= 5 && num_bandwidths > 0) {
01833         rs_out.has_bandwidth = 1;
01834         rs_out.bandwidth = median_uint32(bandwidths, num_bandwidths);
01835       }
01836 
01837       /* Fix bug 2203: Do not count BadExit nodes as Exits for bw weights */
01838       if (consensus_method >= 11) {
01839         is_exit = is_exit && !is_bad_exit;
01840       }
01841 
01842       if (consensus_method >= MIN_METHOD_FOR_BW_WEIGHTS) {
01843         if (rs_out.has_bandwidth) {
01844           T += rs_out.bandwidth;
01845           if (is_exit && is_guard)
01846             D += rs_out.bandwidth;
01847           else if (is_exit)
01848             E += rs_out.bandwidth;
01849           else if (is_guard)
01850             G += rs_out.bandwidth;
01851           else
01852             M += rs_out.bandwidth;
01853         } else {
01854           log_warn(LD_BUG, "Missing consensus bandwidth for router %s",
01855               rs_out.nickname);
01856         }
01857       }
01858 
01859       /* Ok, we already picked a descriptor digest we want to list
01860        * previously.  Now we want to use the exit policy summary from
01861        * that descriptor.  If everybody plays nice all the voters who
01862        * listed that descriptor will have the same summary.  If not then
01863        * something is fishy and we'll use the most common one (breaking
01864        * ties in favor of lexicographically larger one (only because it
01865        * lets me reuse more existing code.
01866        *
01867        * The other case that can happen is that no authority that voted
01868        * for that descriptor has an exit policy summary.  That's
01869        * probably quite unlikely but can happen.  In that case we use
01870        * the policy that was most often listed in votes, again breaking
01871        * ties like in the previous case.
01872        */
01873       if (consensus_method >= 5) {
01874         /* Okay, go through all the votes for this router.  We prepared
01875          * that list previously */
01876         const char *chosen_exitsummary = NULL;
01877         smartlist_clear(exitsummaries);
01878         SMARTLIST_FOREACH(matching_descs, vote_routerstatus_t *, vsr, {
01879           /* Check if the vote where this status comes from had the
01880            * proper descriptor */
01881           tor_assert(fast_memeq(rs_out.identity_digest,
01882                              vsr->status.identity_digest,
01883                              DIGEST_LEN));
01884           if (vsr->status.has_exitsummary &&
01885                fast_memeq(rs_out.descriptor_digest,
01886                        vsr->status.descriptor_digest,
01887                        DIGEST_LEN)) {
01888             tor_assert(vsr->status.exitsummary);
01889             smartlist_add(exitsummaries, vsr->status.exitsummary);
01890             if (!chosen_exitsummary) {
01891               chosen_exitsummary = vsr->status.exitsummary;
01892             } else if (strcmp(chosen_exitsummary, vsr->status.exitsummary)) {
01893               /* Great.  There's disagreement among the voters.  That
01894                * really shouldn't be */
01895               exitsummary_disagreement = 1;
01896             }
01897           }
01898         });
01899 
01900         if (exitsummary_disagreement) {
01901           char id[HEX_DIGEST_LEN+1];
01902           char dd[HEX_DIGEST_LEN+1];
01903           base16_encode(id, sizeof(dd), rs_out.identity_digest, DIGEST_LEN);
01904           base16_encode(dd, sizeof(dd), rs_out.descriptor_digest, DIGEST_LEN);
01905           log_warn(LD_DIR, "The voters disagreed on the exit policy summary "
01906                    " for router %s with descriptor %s.  This really shouldn't"
01907                    " have happened.", id, dd);
01908 
01909           smartlist_sort_strings(exitsummaries);
01910           chosen_exitsummary = get_most_frequent_member(exitsummaries);
01911         } else if (!chosen_exitsummary) {
01912           char id[HEX_DIGEST_LEN+1];
01913           char dd[HEX_DIGEST_LEN+1];
01914           base16_encode(id, sizeof(dd), rs_out.identity_digest, DIGEST_LEN);
01915           base16_encode(dd, sizeof(dd), rs_out.descriptor_digest, DIGEST_LEN);
01916           log_warn(LD_DIR, "Not one of the voters that made us select"
01917                    "descriptor %s for router %s had an exit policy"
01918                    "summary", dd, id);
01919 
01920           /* Ok, none of those voting for the digest we chose had an
01921            * exit policy for us.  Well, that kinda sucks.
01922            */
01923           smartlist_clear(exitsummaries);
01924           SMARTLIST_FOREACH(matching_descs, vote_routerstatus_t *, vsr, {
01925             if (vsr->status.has_exitsummary)
01926               smartlist_add(exitsummaries, vsr->status.exitsummary);
01927           });
01928           smartlist_sort_strings(exitsummaries);
01929           chosen_exitsummary = get_most_frequent_member(exitsummaries);
01930 
01931           if (!chosen_exitsummary)
01932             log_warn(LD_DIR, "Wow, not one of the voters had an exit "
01933                      "policy summary for %s.  Wow.", id);
01934         }
01935 
01936         if (chosen_exitsummary) {
01937           rs_out.has_exitsummary = 1;
01938           /* yea, discards the const */
01939           rs_out.exitsummary = (char *)chosen_exitsummary;
01940         }
01941       }
01942 
01943       {
01944         char buf[4096];
01945         /* Okay!! Now we can write the descriptor... */
01946         /*     First line goes into "buf". */
01947         routerstatus_format_entry(buf, sizeof(buf), &rs_out, NULL,
01948                                   rs_format);
01949         smartlist_add(chunks, tor_strdup(buf));
01950       }
01951       /*     Now an m line, if applicable. */
01952       if (flavor == FLAV_MICRODESC &&
01953           !tor_digest256_is_zero(microdesc_digest)) {
01954         char m[BASE64_DIGEST256_LEN+1];
01955         digest256_to_base64(m, microdesc_digest);
01956         smartlist_add_asprintf(chunks, "m %s\n", m);
01957       }
01958       /*     Next line is all flags.  The "\n" is missing. */
01959       smartlist_add(chunks,
01960                     smartlist_join_strings(chosen_flags, " ", 0, NULL));
01961       /*     Now the version line. */
01962       if (chosen_version) {
01963         smartlist_add(chunks, tor_strdup("\nv "));
01964         smartlist_add(chunks, tor_strdup(chosen_version));
01965       }
01966       smartlist_add(chunks, tor_strdup("\n"));
01967       /*     Now the weight line. */
01968       if (rs_out.has_bandwidth) {
01969         smartlist_add_asprintf(chunks, "w Bandwidth=%d\n", rs_out.bandwidth);
01970       }
01971 
01972       /*     Now the exitpolicy summary line. */
01973       if (rs_out.has_exitsummary && flavor == FLAV_NS) {
01974         smartlist_add_asprintf(chunks, "p %s\n", rs_out.exitsummary);
01975       }
01976 
01977       /* And the loop is over and we move on to the next router */
01978     }
01979 
01980     tor_free(index);
01981     tor_free(size);
01982     tor_free(n_voter_flags);
01983     tor_free(n_flag_voters);
01984     for (i = 0; i < smartlist_len(votes); ++i)
01985       tor_free(flag_map[i]);
01986     tor_free(flag_map);
01987     tor_free(flag_counts);
01988     tor_free(named_flag);
01989     tor_free(unnamed_flag);
01990     strmap_free(name_to_id_map, NULL);
01991     smartlist_free(matching_descs);
01992     smartlist_free(chosen_flags);
01993     smartlist_free(versions);
01994     smartlist_free(exitsummaries);
01995     tor_free(bandwidths);
01996     tor_free(measured_bws);
01997   }
01998 
01999   if (consensus_method >= MIN_METHOD_FOR_FOOTER) {
02000     /* Starting with consensus method 9, we clearly mark the directory
02001      * footer region */
02002     smartlist_add(chunks, tor_strdup("directory-footer\n"));
02003   }
02004 
02005   if (consensus_method >= MIN_METHOD_FOR_BW_WEIGHTS) {
02006     int64_t weight_scale = BW_WEIGHT_SCALE;
02007     char *bw_weight_param = NULL;
02008 
02009     // Parse params, extract BW_WEIGHT_SCALE if present
02010     // DO NOT use consensus_param_bw_weight_scale() in this code!
02011     // The consensus is not formed yet!
02012     if (params) {
02013       if (strcmpstart(params, "bwweightscale=") == 0)
02014         bw_weight_param = params;
02015       else
02016         bw_weight_param = strstr(params, " bwweightscale=");
02017     }
02018 
02019     if (bw_weight_param) {
02020       int ok=0;
02021       char *eq = strchr(bw_weight_param, '=');
02022       if (eq) {
02023         weight_scale = tor_parse_long(eq+1, 10, 1, INT32_MAX, &ok,
02024                                          NULL);
02025         if (!ok) {
02026           log_warn(LD_DIR, "Bad element '%s' in bw weight param",
02027               escaped(bw_weight_param));
02028           weight_scale = BW_WEIGHT_SCALE;
02029         }
02030       } else {
02031         log_warn(LD_DIR, "Bad element '%s' in bw weight param",
02032             escaped(bw_weight_param));
02033         weight_scale = BW_WEIGHT_SCALE;
02034       }
02035     }
02036 
02037     if (consensus_method < 10) {
02038       networkstatus_compute_bw_weights_v9(chunks, G, M, E, D, T, weight_scale);
02039       added_weights = 1;
02040     } else {
02041       added_weights = networkstatus_compute_bw_weights_v10(chunks, G, M, E, D,
02042                                                            T, weight_scale);
02043     }
02044   }
02045 
02046   /* Add a signature. */
02047   {
02048     char digest[DIGEST256_LEN];
02049     char fingerprint[HEX_DIGEST_LEN+1];
02050     char signing_key_fingerprint[HEX_DIGEST_LEN+1];
02051     digest_algorithm_t digest_alg =
02052       flavor == FLAV_NS ? DIGEST_SHA1 : DIGEST_SHA256;
02053     size_t digest_len =
02054       flavor == FLAV_NS ? DIGEST_LEN : DIGEST256_LEN;
02055     const char *algname = crypto_digest_algorithm_get_name(digest_alg);
02056     char sigbuf[4096];
02057 
02058     smartlist_add(chunks, tor_strdup("directory-signature "));
02059 
02060     /* Compute the hash of the chunks. */
02061     hash_list_members(digest, digest_len, chunks, digest_alg);
02062 
02063     /* Get the fingerprints */
02064     crypto_pk_get_fingerprint(identity_key, fingerprint, 0);
02065     crypto_pk_get_fingerprint(signing_key, signing_key_fingerprint, 0);
02066 
02067     /* add the junk that will go at the end of the line. */
02068     if (flavor == FLAV_NS) {
02069       smartlist_add_asprintf(chunks, "%s %s\n", fingerprint,
02070                    signing_key_fingerprint);
02071     } else {
02072       smartlist_add_asprintf(chunks, "%s %s %s\n",
02073                    algname, fingerprint,
02074                    signing_key_fingerprint);
02075     }
02076     /* And the signature. */
02077     sigbuf[0] = '\0';
02078     if (router_append_dirobj_signature(sigbuf, sizeof(sigbuf),
02079                                        digest, digest_len,
02080                                        signing_key)) {
02081       log_warn(LD_BUG, "Couldn't sign consensus networkstatus.");
02082       return NULL; /* This leaks, but it should never happen. */
02083     }
02084     smartlist_add(chunks, tor_strdup(sigbuf));
02085 
02086     if (legacy_id_key_digest && legacy_signing_key && consensus_method >= 3) {
02087       smartlist_add(chunks, tor_strdup("directory-signature "));
02088       base16_encode(fingerprint, sizeof(fingerprint),
02089                     legacy_id_key_digest, DIGEST_LEN);
02090       crypto_pk_get_fingerprint(legacy_signing_key,
02091                                 signing_key_fingerprint, 0);
02092       if (flavor == FLAV_NS) {
02093         smartlist_add_asprintf(chunks, "%s %s\n", fingerprint,
02094                      signing_key_fingerprint);
02095       } else {
02096         smartlist_add_asprintf(chunks, "%s %s %s\n",
02097                      algname, fingerprint,
02098                      signing_key_fingerprint);
02099       }
02100       sigbuf[0] = '\0';
02101       if (router_append_dirobj_signature(sigbuf, sizeof(sigbuf),
02102                                          digest, digest_len,
02103                                          legacy_signing_key)) {
02104         log_warn(LD_BUG, "Couldn't sign consensus networkstatus.");
02105         return NULL; /* This leaks, but it should never happen. */
02106       }
02107       smartlist_add(chunks, tor_strdup(sigbuf));
02108     }
02109   }
02110 
02111   result = smartlist_join_strings(chunks, "", 0, NULL);
02112 
02113   tor_free(client_versions);
02114   tor_free(server_versions);
02115   SMARTLIST_FOREACH(flags, char *, cp, tor_free(cp));
02116   smartlist_free(flags);
02117   SMARTLIST_FOREACH(chunks, char *, cp, tor_free(cp));
02118   smartlist_free(chunks);
02119 
02120   {
02121     networkstatus_t *c;
02122     if (!(c = networkstatus_parse_vote_from_string(result, NULL,
02123                                                    NS_TYPE_CONSENSUS))) {
02124       log_err(LD_BUG, "Generated a networkstatus consensus we couldn't "
02125               "parse.");
02126       tor_free(result);
02127       return NULL;
02128     }
02129     // Verify balancing parameters
02130     if (consensus_method >= MIN_METHOD_FOR_BW_WEIGHTS && added_weights) {
02131       networkstatus_verify_bw_weights(c);
02132     }
02133     networkstatus_vote_free(c);
02134   }
02135 
02136   return result;
02137 }
02138 
02147 int
02148 networkstatus_add_detached_signatures(networkstatus_t *target,
02149                                       ns_detached_signatures_t *sigs,
02150                                       const char *source,
02151                                       int severity,
02152                                       const char **msg_out)
02153 {
02154   int r = 0;
02155   const char *flavor;
02156   smartlist_t *siglist;
02157   tor_assert(sigs);
02158   tor_assert(target);
02159   tor_assert(target->type == NS_TYPE_CONSENSUS);
02160 
02161   flavor = networkstatus_get_flavor_name(target->flavor);
02162 
02163   /* Do the times seem right? */
02164   if (target->valid_after != sigs->valid_after) {
02165     *msg_out = "Valid-After times do not match "
02166       "when adding detached signatures to consensus";
02167     return -1;
02168   }
02169   if (target->fresh_until != sigs->fresh_until) {
02170     *msg_out = "Fresh-until times do not match "
02171       "when adding detached signatures to consensus";
02172     return -1;
02173   }
02174   if (target->valid_until != sigs->valid_until) {
02175     *msg_out = "Valid-until times do not match "
02176       "when adding detached signatures to consensus";
02177     return -1;
02178   }
02179   siglist = strmap_get(sigs->signatures, flavor);
02180   if (!siglist) {
02181     *msg_out = "No signatures for given consensus flavor";
02182     return -1;
02183   }
02184 
02186   {
02187     digests_t *digests = strmap_get(sigs->digests, flavor);
02188     int n_matches = 0;
02189     digest_algorithm_t alg;
02190     if (!digests) {
02191       *msg_out = "No digests for given consensus flavor";
02192       return -1;
02193     }
02194     for (alg = DIGEST_SHA1; alg < N_DIGEST_ALGORITHMS; ++alg) {
02195       if (!tor_mem_is_zero(digests->d[alg], DIGEST256_LEN)) {
02196         if (fast_memeq(target->digests.d[alg], digests->d[alg],
02197                        DIGEST256_LEN)) {
02198           ++n_matches;
02199         } else {
02200           *msg_out = "Mismatched digest.";
02201           return -1;
02202         }
02203       }
02204     }
02205     if (!n_matches) {
02206       *msg_out = "No regognized digests for given consensus flavor";
02207     }
02208   }
02209 
02210   /* For each voter in src... */
02211   SMARTLIST_FOREACH_BEGIN(siglist, document_signature_t *, sig) {
02212     char voter_identity[HEX_DIGEST_LEN+1];
02213     networkstatus_voter_info_t *target_voter =
02214       networkstatus_get_voter_by_id(target, sig->identity_digest);
02215     authority_cert_t *cert = NULL;
02216     const char *algorithm;
02217     document_signature_t *old_sig = NULL;
02218 
02219     algorithm = crypto_digest_algorithm_get_name(sig->alg);
02220 
02221     base16_encode(voter_identity, sizeof(voter_identity),
02222                   sig->identity_digest, DIGEST_LEN);
02223     log_info(LD_DIR, "Looking at signature from %s using %s", voter_identity,
02224              algorithm);
02225     /* If the target doesn't know about this voter, then forget it. */
02226     if (!target_voter) {
02227       log_info(LD_DIR, "We do not know any voter with ID %s", voter_identity);
02228       continue;
02229     }
02230 
02231     old_sig = voter_get_sig_by_algorithm(target_voter, sig->alg);
02232 
02233     /* If the target already has a good signature from this voter, then skip
02234      * this one. */
02235     if (old_sig && old_sig->good_signature) {
02236       log_info(LD_DIR, "We already have a good signature from %s using %s",
02237                voter_identity, algorithm);
02238       continue;
02239     }
02240 
02241     /* Try checking the signature if we haven't already. */
02242     if (!sig->good_signature && !sig->bad_signature) {
02243       cert = authority_cert_get_by_digests(sig->identity_digest,
02244                                            sig->signing_key_digest);
02245       if (cert)
02246         networkstatus_check_document_signature(target, sig, cert);
02247     }
02248 
02249     /* If this signature is good, or we don't have any signature yet,
02250      * then maybe add it. */
02251     if (sig->good_signature || !old_sig || old_sig->bad_signature) {
02252       log_info(LD_DIR, "Adding signature from %s with %s", voter_identity,
02253                algorithm);
02254       log(severity, LD_DIR, "Added a signature for %s from %s.",
02255           target_voter->nickname, source);
02256       ++r;
02257       if (old_sig) {
02258         smartlist_remove(target_voter->sigs, old_sig);
02259         document_signature_free(old_sig);
02260       }
02261       smartlist_add(target_voter->sigs, document_signature_dup(sig));
02262     } else {
02263       log_info(LD_DIR, "Not adding signature from %s", voter_identity);
02264     }
02265   } SMARTLIST_FOREACH_END(sig);
02266 
02267   return r;
02268 }
02269 
02275 static char *
02276 networkstatus_format_signatures(networkstatus_t *consensus,
02277                                 int for_detached_signatures)
02278 {
02279   smartlist_t *elements;
02280   char buf[4096];
02281   char *result = NULL;
02282   int n_sigs = 0;
02283   const consensus_flavor_t flavor = consensus->flavor;
02284   const char *flavor_name = networkstatus_get_flavor_name(flavor);
02285   const char *keyword;
02286 
02287   if (for_detached_signatures && flavor != FLAV_NS)
02288     keyword = "additional-signature";
02289   else
02290     keyword = "directory-signature";
02291 
02292   elements = smartlist_new();
02293 
02294   SMARTLIST_FOREACH_BEGIN(consensus->voters, networkstatus_voter_info_t *, v) {
02295     SMARTLIST_FOREACH_BEGIN(v->sigs, document_signature_t *, sig) {
02296       char sk[HEX_DIGEST_LEN+1];
02297       char id[HEX_DIGEST_LEN+1];
02298       if (!sig->signature || sig->bad_signature)
02299         continue;
02300       ++n_sigs;
02301       base16_encode(sk, sizeof(sk), sig->signing_key_digest, DIGEST_LEN);
02302       base16_encode(id, sizeof(id), sig->identity_digest, DIGEST_LEN);
02303       if (flavor == FLAV_NS) {
02304         smartlist_add_asprintf(elements,
02305                      "%s %s %s\n-----BEGIN SIGNATURE-----\n",
02306                      keyword, id, sk);
02307       } else {
02308         const char *digest_name =
02309           crypto_digest_algorithm_get_name(sig->alg);
02310         smartlist_add_asprintf(elements,
02311                      "%s%s%s %s %s %s\n-----BEGIN SIGNATURE-----\n",
02312                      keyword,
02313                      for_detached_signatures ? " " : "",
02314                      for_detached_signatures ? flavor_name : "",
02315                      digest_name, id, sk);
02316       }
02317       base64_encode(buf, sizeof(buf), sig->signature, sig->signature_len);
02318       strlcat(buf, "-----END SIGNATURE-----\n", sizeof(buf));
02319       smartlist_add(elements, tor_strdup(buf));
02320     } SMARTLIST_FOREACH_END(sig);
02321   } SMARTLIST_FOREACH_END(v);
02322 
02323   result = smartlist_join_strings(elements, "", 0, NULL);
02324   SMARTLIST_FOREACH(elements, char *, cp, tor_free(cp));
02325   smartlist_free(elements);
02326   if (!n_sigs)
02327     tor_free(result);
02328   return result;
02329 }
02330 
02335 char *
02336 networkstatus_get_detached_signatures(smartlist_t *consensuses)
02337 {
02338   smartlist_t *elements;
02339   char *result = NULL, *sigs = NULL;
02340   networkstatus_t *consensus_ns = NULL;
02341   tor_assert(consensuses);
02342 
02343   SMARTLIST_FOREACH(consensuses, networkstatus_t *, ns, {
02344       tor_assert(ns);
02345       tor_assert(ns->type == NS_TYPE_CONSENSUS);
02346       if (ns && ns->flavor == FLAV_NS)
02347         consensus_ns = ns;
02348   });
02349   if (!consensus_ns) {
02350     log_warn(LD_BUG, "No NS consensus given.");
02351     return NULL;
02352   }
02353 
02354   elements = smartlist_new();
02355 
02356   {
02357     char va_buf[ISO_TIME_LEN+1], fu_buf[ISO_TIME_LEN+1],
02358       vu_buf[ISO_TIME_LEN+1];
02359     char d[HEX_DIGEST_LEN+1];
02360 
02361     base16_encode(d, sizeof(d),
02362                   consensus_ns->digests.d[DIGEST_SHA1], DIGEST_LEN);
02363     format_iso_time(va_buf, consensus_ns->valid_after);
02364     format_iso_time(fu_buf, consensus_ns->fresh_until);
02365     format_iso_time(vu_buf, consensus_ns->valid_until);
02366 
02367     smartlist_add_asprintf(elements,
02368                  "consensus-digest %s\n"
02369                  "valid-after %s\n"
02370                  "fresh-until %s\n"
02371                  "valid-until %s\n", d, va_buf, fu_buf, vu_buf);
02372   }
02373 
02374   /* Get all the digests for the non-FLAV_NS consensuses */
02375   SMARTLIST_FOREACH_BEGIN(consensuses, networkstatus_t *, ns) {
02376     const char *flavor_name = networkstatus_get_flavor_name(ns->flavor);
02377     int alg;
02378     if (ns->flavor == FLAV_NS)
02379       continue;
02380 
02381     /* start with SHA256; we don't include SHA1 for anything but the basic
02382      * consensus. */
02383     for (alg = DIGEST_SHA256; alg < N_DIGEST_ALGORITHMS; ++alg) {
02384       char d[HEX_DIGEST256_LEN+1];
02385       const char *alg_name =
02386         crypto_digest_algorithm_get_name(alg);
02387       if (tor_mem_is_zero(ns->digests.d[alg], DIGEST256_LEN))
02388         continue;
02389       base16_encode(d, sizeof(d), ns->digests.d[alg], DIGEST256_LEN);
02390       smartlist_add_asprintf(elements, "additional-digest %s %s %s\n",
02391                    flavor_name, alg_name, d);
02392     }
02393   } SMARTLIST_FOREACH_END(ns);
02394 
02395   /* Now get all the sigs for non-FLAV_NS consensuses */
02396   SMARTLIST_FOREACH_BEGIN(consensuses, networkstatus_t *, ns) {
02397     char *sigs;
02398     if (ns->flavor == FLAV_NS)
02399       continue;
02400     sigs = networkstatus_format_signatures(ns, 1);
02401     if (!sigs) {
02402       log_warn(LD_DIR, "Couldn't format signatures");
02403       goto err;
02404     }
02405     smartlist_add(elements, sigs);
02406   } SMARTLIST_FOREACH_END(ns);
02407 
02408   /* Now add the FLAV_NS consensus signatrures. */
02409   sigs = networkstatus_format_signatures(consensus_ns, 1);
02410   if (!sigs)
02411     goto err;
02412   smartlist_add(elements, sigs);
02413 
02414   result = smartlist_join_strings(elements, "", 0, NULL);
02415  err:
02416   SMARTLIST_FOREACH(elements, char *, cp, tor_free(cp));
02417   smartlist_free(elements);
02418   return result;
02419 }
02420 
02424 static char *
02425 get_detached_signatures_from_pending_consensuses(pending_consensus_t *pending,
02426                                                  int n_flavors)
02427 {
02428   int flav;
02429   char *signatures;
02430   smartlist_t *c = smartlist_new();
02431   for (flav = 0; flav < n_flavors; ++flav) {
02432     if (pending[flav].consensus)
02433       smartlist_add(c, pending[flav].consensus);
02434   }
02435   signatures = networkstatus_get_detached_signatures(c);
02436   smartlist_free(c);
02437   return signatures;
02438 }
02439 
02441 void
02442 ns_detached_signatures_free(ns_detached_signatures_t *s)
02443 {
02444   if (!s)
02445     return;
02446   if (s->signatures) {
02447     STRMAP_FOREACH(s->signatures, flavor, smartlist_t *, sigs) {
02448       SMARTLIST_FOREACH(sigs, document_signature_t *, sig,
02449                         document_signature_free(sig));
02450       smartlist_free(sigs);
02451     } STRMAP_FOREACH_END;
02452     strmap_free(s->signatures, NULL);
02453     strmap_free(s->digests, _tor_free);
02454   }
02455 
02456   tor_free(s);
02457 }
02458 
02459 /* =====
02460  * Certificate functions
02461  * ===== */
02462 
02465 authority_cert_t *
02466 authority_cert_dup(authority_cert_t *cert)
02467 {
02468   authority_cert_t *out = tor_malloc(sizeof(authority_cert_t));
02469   tor_assert(cert);
02470 
02471   memcpy(out, cert, sizeof(authority_cert_t));
02472   /* Now copy pointed-to things. */
02473   out->cache_info.signed_descriptor_body =
02474     tor_strndup(cert->cache_info.signed_descriptor_body,
02475                 cert->cache_info.signed_descriptor_len);
02476   out->cache_info.saved_location = SAVED_NOWHERE;
02477   out->identity_key = crypto_pk_dup_key(cert->identity_key);
02478   out->signing_key = crypto_pk_dup_key(cert->signing_key);
02479 
02480   return out;
02481 }
02482 
02483 /* =====
02484  * Vote scheduling
02485  * ===== */
02486 
02490 void
02491 dirvote_get_preferred_voting_intervals(vote_timing_t *timing_out)
02492 {
02493   const or_options_t *options = get_options();
02494 
02495   tor_assert(timing_out);
02496 
02497   timing_out->vote_interval = options->V3AuthVotingInterval;
02498   timing_out->n_intervals_valid = options->V3AuthNIntervalsValid;
02499   timing_out->vote_delay = options->V3AuthVoteDelay;
02500   timing_out->dist_delay = options->V3AuthDistDelay;
02501 }
02502 
02507 time_t
02508 dirvote_get_start_of_next_interval(time_t now, int interval)
02509 {
02510   struct tm tm;
02511   time_t midnight_today;
02512   time_t midnight_tomorrow;
02513   time_t next;
02514 
02515   tor_gmtime_r(&now, &tm);
02516   tm.tm_hour = 0;
02517   tm.tm_min = 0;
02518   tm.tm_sec = 0;
02519 
02520   midnight_today = tor_timegm(&tm);
02521   midnight_tomorrow = midnight_today + (24*60*60);
02522 
02523   next = midnight_today + ((now-midnight_today)/interval + 1)*interval;
02524 
02525   /* Intervals never cross midnight. */
02526   if (next > midnight_tomorrow)
02527     next = midnight_tomorrow;
02528 
02529   /* If the interval would only last half as long as it's supposed to, then
02530    * skip over to the next day. */
02531   if (next + interval/2 > midnight_tomorrow)
02532     next = midnight_tomorrow;
02533 
02534   return next;
02535 }
02536 
02538 static struct {
02540   time_t voting_starts;
02543   time_t fetch_missing_votes;
02545   time_t voting_ends;
02548   time_t fetch_missing_signatures;
02550   time_t interval_starts;
02551 
02552   /* True iff we have generated and distributed our vote. */
02553   int have_voted;
02554   /* True iff we've requested missing votes. */
02555   int have_fetched_missing_votes;
02556   /* True iff we have built a consensus and sent the signatures around. */
02557   int have_built_consensus;
02558   /* True iff we've fetched missing signatures. */
02559   int have_fetched_missing_signatures;
02560   /* True iff we have published our consensus. */
02561   int have_published_consensus;
02562 } voting_schedule = {0,0,0,0,0,0,0,0,0,0};
02563 
02566 void
02567 dirvote_recalculate_timing(const or_options_t *options, time_t now)
02568 {
02569   int interval, vote_delay, dist_delay;
02570   time_t start;
02571   time_t end;
02572   networkstatus_t *consensus;
02573 
02574   if (!authdir_mode_v3(options))
02575     return;
02576 
02577   consensus = networkstatus_get_live_consensus(now);
02578 
02579   memset(&voting_schedule, 0, sizeof(voting_schedule));
02580 
02581   if (consensus) {
02582     interval = (int)( consensus->fresh_until - consensus->valid_after );
02583     vote_delay = consensus->vote_seconds;
02584     dist_delay = consensus->dist_seconds;
02585   } else {
02586     interval = options->TestingV3AuthInitialVotingInterval;
02587     vote_delay = options->TestingV3AuthInitialVoteDelay;
02588     dist_delay = options->TestingV3AuthInitialDistDelay;
02589   }
02590 
02591   tor_assert(interval > 0);
02592 
02593   if (vote_delay + dist_delay > interval/2)
02594     vote_delay = dist_delay = interval / 4;
02595 
02596   start = voting_schedule.interval_starts =
02597     dirvote_get_start_of_next_interval(now,interval);
02598   end = dirvote_get_start_of_next_interval(start+1, interval);
02599 
02600   tor_assert(end > start);
02601 
02602   voting_schedule.fetch_missing_signatures = start - (dist_delay/2);
02603   voting_schedule.voting_ends = start - dist_delay;
02604   voting_schedule.fetch_missing_votes = start - dist_delay - (vote_delay/2);
02605   voting_schedule.voting_starts = start - dist_delay - vote_delay;
02606 
02607   {
02608     char tbuf[ISO_TIME_LEN+1];
02609     format_iso_time(tbuf, voting_schedule.interval_starts);
02610     log_notice(LD_DIR,"Choosing expected valid-after time as %s: "
02611                "consensus_set=%d, interval=%d",
02612                tbuf, consensus?1:0, interval);
02613   }
02614 }
02615 
02617 void
02618 dirvote_act(const or_options_t *options, time_t now)
02619 {
02620   if (!authdir_mode_v3(options))
02621     return;
02622   if (!voting_schedule.voting_starts) {
02623     char *keys = list_v3_auth_ids();
02624     authority_cert_t *c = get_my_v3_authority_cert();
02625     log_notice(LD_DIR, "Scheduling voting.  Known authority IDs are %s. "
02626                "Mine is %s.",
02627                keys, hex_str(c->cache_info.identity_digest, DIGEST_LEN));
02628     tor_free(keys);
02629     dirvote_recalculate_timing(options, now);
02630   }
02631   if (voting_schedule.voting_starts < now && !voting_schedule.have_voted) {
02632     log_notice(LD_DIR, "Time to vote.");
02633     dirvote_perform_vote();
02634     voting_schedule.have_voted = 1;
02635   }
02636   if (voting_schedule.fetch_missing_votes < now &&
02637       !voting_schedule.have_fetched_missing_votes) {
02638     log_notice(LD_DIR, "Time to fetch any votes that we're missing.");
02639     dirvote_fetch_missing_votes();
02640     voting_schedule.have_fetched_missing_votes = 1;
02641   }
02642   if (voting_schedule.voting_ends < now &&
02643       !voting_schedule.have_built_consensus) {
02644     log_notice(LD_DIR, "Time to compute a consensus.");
02645     dirvote_compute_consensuses();
02646     /* XXXX We will want to try again later if we haven't got enough
02647      * votes yet.  Implement this if it turns out to ever happen. */
02648     voting_schedule.have_built_consensus = 1;
02649   }
02650   if (voting_schedule.fetch_missing_signatures < now &&
02651       !voting_schedule.have_fetched_missing_signatures) {
02652     log_notice(LD_DIR, "Time to fetch any signatures that we're missing.");
02653     dirvote_fetch_missing_signatures();
02654     voting_schedule.have_fetched_missing_signatures = 1;
02655   }
02656   if (voting_schedule.interval_starts < now &&
02657       !voting_schedule.have_published_consensus) {
02658     log_notice(LD_DIR, "Time to publish the consensus and discard old votes");
02659     dirvote_publish_consensus();
02660     dirvote_clear_votes(0);
02661     voting_schedule.have_published_consensus = 1;
02662     /* XXXX We will want to try again later if we haven't got enough
02663      * signatures yet.  Implement this if it turns out to ever happen. */
02664     dirvote_recalculate_timing(options, now);
02665   }
02666 }
02667 
02671 typedef struct pending_vote_t {
02672   cached_dir_t *vote_body;
02673   networkstatus_t *vote;
02674 } pending_vote_t;
02675 
02678 static smartlist_t *pending_vote_list = NULL;
02681 static smartlist_t *previous_vote_list = NULL;
02682 
02683 /* DOCDOC pending_consensuses */
02684 static pending_consensus_t pending_consensuses[N_CONSENSUS_FLAVORS];
02685 
02688 static char *pending_consensus_signatures = NULL;
02689 
02692 static smartlist_t *pending_consensus_signature_list = NULL;
02693 
02696 static int
02697 dirvote_perform_vote(void)
02698 {
02699   crypto_pk_t *key = get_my_v3_authority_signing_key();
02700   authority_cert_t *cert = get_my_v3_authority_cert();
02701   networkstatus_t *ns;
02702   char *contents;
02703   pending_vote_t *pending_vote;
02704   time_t now = time(NULL);
02705 
02706   int status;
02707   const char *msg = "";
02708 
02709   if (!cert || !key) {
02710     log_warn(LD_NET, "Didn't find key/certificate to generate v3 vote");
02711     return -1;
02712   } else if (cert->expires < now) {
02713     log_warn(LD_NET, "Can't generate v3 vote with expired certificate");
02714     return -1;
02715   }
02716   if (!(ns = dirserv_generate_networkstatus_vote_obj(key, cert)))
02717     return -1;
02718 
02719   contents = format_networkstatus_vote(key, ns);
02720   networkstatus_vote_free(ns);
02721   if (!contents)
02722     return -1;
02723 
02724   pending_vote = dirvote_add_vote(contents, &msg, &status);
02725   tor_free(contents);
02726   if (!pending_vote) {
02727     log_warn(LD_DIR, "Couldn't store my own vote! (I told myself, '%s'.)",
02728              msg);
02729     return -1;
02730   }
02731 
02732   directory_post_to_dirservers(DIR_PURPOSE_UPLOAD_VOTE,
02733                                ROUTER_PURPOSE_GENERAL,
02734                                V3_DIRINFO,
02735                                pending_vote->vote_body->dir,
02736                                pending_vote->vote_body->dir_len, 0);
02737   log_notice(LD_DIR, "Vote posted.");
02738   return 0;
02739 }
02740 
02744 static void
02745 dirvote_fetch_missing_votes(void)
02746 {
02747   smartlist_t *missing_fps = smartlist_new();
02748   char *resource;
02749 
02750   SMARTLIST_FOREACH(router_get_trusted_dir_servers(),
02751                     trusted_dir_server_t *, ds,
02752     {
02753       if (!(ds->type & V3_DIRINFO))
02754         continue;
02755       if (!dirvote_get_vote(ds->v3_identity_digest,
02756                             DGV_BY_ID|DGV_INCLUDE_PENDING)) {
02757         char *cp = tor_malloc(HEX_DIGEST_LEN+1);
02758         base16_encode(cp, HEX_DIGEST_LEN+1, ds->v3_identity_digest,
02759                       DIGEST_LEN);
02760         smartlist_add(missing_fps, cp);
02761       }
02762     });
02763 
02764   if (!smartlist_len(missing_fps)) {
02765     smartlist_free(missing_fps);
02766     return;
02767   }
02768   {
02769     char *tmp = smartlist_join_strings(missing_fps, " ", 0, NULL);
02770     log_notice(LOG_NOTICE, "We're missing votes from %d authorities (%s). "
02771                "Asking every other authority for a copy.",
02772                smartlist_len(missing_fps), tmp);
02773     tor_free(tmp);
02774   }
02775   resource = smartlist_join_strings(missing_fps, "+", 0, NULL);
02776   directory_get_from_all_authorities(DIR_PURPOSE_FETCH_STATUS_VOTE,
02777                                      0, resource);
02778   tor_free(resource);
02779   SMARTLIST_FOREACH(missing_fps, char *, cp, tor_free(cp));
02780   smartlist_free(missing_fps);
02781 }
02782 
02785 static void
02786 dirvote_fetch_missing_signatures(void)
02787 {
02788   int need_any = 0;
02789   int i;
02790   for (i=0; i < N_CONSENSUS_FLAVORS; ++i) {
02791     networkstatus_t *consensus = pending_consensuses[i].consensus;
02792     if (!consensus ||
02793         networkstatus_check_consensus_signature(consensus, -1) == 1) {
02794       /* We have no consensus, or we have one that's signed by everybody. */
02795       continue;
02796     }
02797     need_any = 1;
02798   }
02799   if (!need_any)
02800     return;
02801 
02802   directory_get_from_all_authorities(DIR_PURPOSE_FETCH_DETACHED_SIGNATURES,
02803                                      0, NULL);
02804 }
02805 
02808 static void
02809 dirvote_clear_pending_consensuses(void)
02810 {
02811   int i;
02812   for (i = 0; i < N_CONSENSUS_FLAVORS; ++i) {
02813     pending_consensus_t *pc = &pending_consensuses[i];
02814     tor_free(pc->body);
02815 
02816     networkstatus_vote_free(pc->consensus);
02817     pc->consensus = NULL;
02818   }
02819 }
02820 
02822 static void
02823 dirvote_clear_votes(int all_votes)
02824 {
02825   if (!previous_vote_list)
02826     previous_vote_list = smartlist_new();
02827   if (!pending_vote_list)
02828     pending_vote_list = smartlist_new();
02829 
02830   /* All "previous" votes are now junk. */
02831   SMARTLIST_FOREACH(previous_vote_list, pending_vote_t *, v, {
02832       cached_dir_decref(v->vote_body);
02833       v->vote_body = NULL;
02834       networkstatus_vote_free(v->vote);
02835       tor_free(v);
02836     });
02837   smartlist_clear(previous_vote_list);
02838 
02839   if (all_votes) {
02840     /* If we're dumping all the votes, we delete the pending ones. */
02841     SMARTLIST_FOREACH(pending_vote_list, pending_vote_t *, v, {
02842         cached_dir_decref(v->vote_body);
02843         v->vote_body = NULL;
02844         networkstatus_vote_free(v->vote);
02845         tor_free(v);
02846       });
02847   } else {
02848     /* Otherwise, we move them into "previous". */
02849     smartlist_add_all(previous_vote_list, pending_vote_list);
02850   }
02851   smartlist_clear(pending_vote_list);
02852 
02853   if (pending_consensus_signature_list) {
02854     SMARTLIST_FOREACH(pending_consensus_signature_list, char *, cp,
02855                       tor_free(cp));
02856     smartlist_clear(pending_consensus_signature_list);
02857   }
02858   tor_free(pending_consensus_signatures);
02859   dirvote_clear_pending_consensuses();
02860 }
02861 
02864 static char *
02865 list_v3_auth_ids(void)
02866 {
02867   smartlist_t *known_v3_keys = smartlist_new();
02868   char *keys;
02869   SMARTLIST_FOREACH(router_get_trusted_dir_servers(),
02870                     trusted_dir_server_t *, ds,
02871     if ((ds->type & V3_DIRINFO) &&
02872         !tor_digest_is_zero(ds->v3_identity_digest))
02873       smartlist_add(known_v3_keys,
02874                     tor_strdup(hex_str(ds->v3_identity_digest, DIGEST_LEN))));
02875   keys = smartlist_join_strings(known_v3_keys, ", ", 0, NULL);
02876   SMARTLIST_FOREACH(known_v3_keys, char *, cp, tor_free(cp));
02877   smartlist_free(known_v3_keys);
02878   return keys;
02879 }
02880 
02886 pending_vote_t *
02887 dirvote_add_vote(const char *vote_body, const char **msg_out, int *status_out)
02888 {
02889   networkstatus_t *vote;
02890   networkstatus_voter_info_t *vi;
02891   trusted_dir_server_t *ds;
02892   pending_vote_t *pending_vote = NULL;
02893   const char *end_of_vote = NULL;
02894   int any_failed = 0;
02895   tor_assert(vote_body);
02896   tor_assert(msg_out);
02897   tor_assert(status_out);
02898 
02899   if (!pending_vote_list)
02900     pending_vote_list = smartlist_new();
02901   *status_out = 0;
02902   *msg_out = NULL;
02903 
02904  again:
02905   vote = networkstatus_parse_vote_from_string(vote_body, &end_of_vote,
02906                                               NS_TYPE_VOTE);
02907   if (!end_of_vote)
02908     end_of_vote = vote_body + strlen(vote_body);
02909   if (!vote) {
02910     log_warn(LD_DIR, "Couldn't parse vote: length was %d",
02911              (int)strlen(vote_body));
02912     *msg_out = "Unable to parse vote";
02913     goto err;
02914   }
02915   tor_assert(smartlist_len(vote->voters) == 1);
02916   vi = get_voter(vote);
02917   {
02918     int any_sig_good = 0;
02919     SMARTLIST_FOREACH(vi->sigs, document_signature_t *, sig,
02920                       if (sig->good_signature)
02921                         any_sig_good = 1);
02922     tor_assert(any_sig_good);
02923   }
02924   ds = trusteddirserver_get_by_v3_auth_digest(vi->identity_digest);
02925   if (!ds) {
02926     char *keys = list_v3_auth_ids();
02927     log_warn(LD_DIR, "Got a vote from an authority (nickname %s, address %s) "
02928              "with authority key ID %s. "
02929              "This key ID is not recognized.  Known v3 key IDs are: %s",
02930              vi->nickname, vi->address,
02931              hex_str(vi->identity_digest, DIGEST_LEN), keys);
02932     tor_free(keys);
02933     *msg_out = "Vote not from a recognized v3 authority";
02934     goto err;
02935   }
02936   tor_assert(vote->cert);
02937   if (!authority_cert_get_by_digests(vote->cert->cache_info.identity_digest,
02938                                      vote->cert->signing_key_digest)) {
02939     /* Hey, it's a new cert! */
02940     trusted_dirs_load_certs_from_string(
02941                                vote->cert->cache_info.signed_descriptor_body,
02942                                0 /* from_store */, 1 /*flush*/);
02943     if (!authority_cert_get_by_digests(vote->cert->cache_info.identity_digest,
02944                                        vote->cert->signing_key_digest)) {
02945       log_warn(LD_BUG, "We added a cert, but still couldn't find it.");
02946     }
02947   }
02948 
02949   /* Is it for the right period? */
02950   if (vote->valid_after != voting_schedule.interval_starts) {
02951     char tbuf1[ISO_TIME_LEN+1], tbuf2[ISO_TIME_LEN+1];
02952     format_iso_time(tbuf1, vote->valid_after);
02953     format_iso_time(tbuf2, voting_schedule.interval_starts);
02954     log_warn(LD_DIR, "Rejecting vote from %s with valid-after time of %s; "
02955              "we were expecting %s", vi->address, tbuf1, tbuf2);
02956     *msg_out = "Bad valid-after time";
02957     goto err;
02958   }
02959 
02960   /* Fetch any new router descriptors we just learned about */
02961   update_consensus_router_descriptor_downloads(time(NULL), 1, vote);
02962 
02963   /* Now see whether we already have a vote from this authority. */
02964   SMARTLIST_FOREACH(pending_vote_list, pending_vote_t *, v, {
02965       if (fast_memeq(v->vote->cert->cache_info.identity_digest,
02966                    vote->cert->cache_info.identity_digest,
02967                    DIGEST_LEN)) {
02968         networkstatus_voter_info_t *vi_old = get_voter(v->vote);
02969         if (fast_memeq(vi_old->vote_digest, vi->vote_digest, DIGEST_LEN)) {
02970           /* Ah, it's the same vote. Not a problem. */
02971           log_info(LD_DIR, "Discarding a vote we already have (from %s).",
02972                    vi->address);
02973           if (*status_out < 200)
02974             *status_out = 200;
02975           goto discard;
02976         } else if (v->vote->published < vote->published) {
02977           log_notice(LD_DIR, "Replacing an older pending vote from this "
02978                      "directory.");
02979           cached_dir_decref(v->vote_body);
02980           networkstatus_vote_free(v->vote);
02981           v->vote_body = new_cached_dir(tor_strndup(vote_body,
02982                                                     end_of_vote-vote_body),
02983                                         vote->published);
02984           v->vote = vote;
02985           if (end_of_vote &&
02986               !strcmpstart(end_of_vote, "network-status-version"))
02987             goto again;
02988 
02989           if (*status_out < 200)
02990             *status_out = 200;
02991           if (!*msg_out)
02992             *msg_out = "OK";
02993           return v;
02994         } else {
02995           *msg_out = "Already have a newer pending vote";
02996           goto err;
02997         }
02998       }
02999   });
03000 
03001   pending_vote = tor_malloc_zero(sizeof(pending_vote_t));
03002   pending_vote->vote_body = new_cached_dir(tor_strndup(vote_body,
03003                                                        end_of_vote-vote_body),
03004                                            vote->published);
03005   pending_vote->vote = vote;
03006   smartlist_add(pending_vote_list, pending_vote);
03007 
03008   if (!strcmpstart(end_of_vote, "network-status-version ")) {
03009     vote_body = end_of_vote;
03010     goto again;
03011   }
03012 
03013   goto done;
03014 
03015  err:
03016   any_failed = 1;
03017   if (!*msg_out)
03018     *msg_out = "Error adding vote";
03019   if (*status_out < 400)
03020     *status_out = 400;
03021 
03022  discard:
03023   networkstatus_vote_free(vote);
03024 
03025   if (end_of_vote && !strcmpstart(end_of_vote, "network-status-version ")) {
03026     vote_body = end_of_vote;
03027     goto again;
03028   }
03029 
03030  done:
03031 
03032   if (*status_out < 200)
03033     *status_out = 200;
03034   if (!*msg_out) {
03035     if (!any_failed && !pending_vote) {
03036       *msg_out = "Duplicate discarded";
03037     } else {
03038       *msg_out = "ok";
03039     }
03040   }
03041 
03042   return any_failed ? NULL : pending_vote;
03043 }
03044 
03049 static int
03050 dirvote_compute_consensuses(void)
03051 {
03052   /* Have we got enough votes to try? */
03053   int n_votes, n_voters, n_vote_running = 0;
03054   smartlist_t *votes = NULL, *votestrings = NULL;
03055   char *consensus_body = NULL, *signatures = NULL, *votefile;
03056   networkstatus_t *consensus = NULL;
03057   authority_cert_t *my_cert;
03058   pending_consensus_t pending[N_CONSENSUS_FLAVORS];
03059   int flav;
03060 
03061   memset(pending, 0, sizeof(pending));
03062 
03063   if (!pending_vote_list)
03064     pending_vote_list = smartlist_new();
03065 
03066   n_voters = get_n_authorities(V3_DIRINFO);
03067   n_votes = smartlist_len(pending_vote_list);
03068   if (n_votes <= n_voters/2) {
03069     log_warn(LD_DIR, "We don't have enough votes to generate a consensus: "
03070              "%d of %d", n_votes, n_voters/2+1);
03071     goto err;
03072   }
03073   tor_assert(pending_vote_list);
03074   SMARTLIST_FOREACH(pending_vote_list, pending_vote_t *, v, {
03075     if (smartlist_string_isin(v->vote->known_flags, "Running"))
03076       n_vote_running++;
03077   });
03078   if (!n_vote_running) {
03079     /* See task 1066. */
03080     log_warn(LD_DIR, "Nobody has voted on the Running flag. Generating "
03081                      "and publishing a consensus without Running nodes "
03082                      "would make many clients stop working. Not "
03083                      "generating a consensus!");
03084     goto err;
03085   }
03086 
03087   if (!(my_cert = get_my_v3_authority_cert())) {
03088     log_warn(LD_DIR, "Can't generate consensus without a certificate.");
03089     goto err;
03090   }
03091 
03092   votes = smartlist_new();
03093   votestrings = smartlist_new();
03094   SMARTLIST_FOREACH(pending_vote_list, pending_vote_t *, v,
03095     {
03096       sized_chunk_t *c = tor_malloc(sizeof(sized_chunk_t));
03097       c->bytes = v->vote_body->dir;
03098       c->len = v->vote_body->dir_len;
03099       smartlist_add(votestrings, c); /* collect strings to write to disk */
03100 
03101       smartlist_add(votes, v->vote); /* collect votes to compute consensus */
03102     });
03103 
03104   votefile = get_datadir_fname("v3-status-votes");
03105   write_chunks_to_file(votefile, votestrings, 0);
03106   tor_free(votefile);
03107   SMARTLIST_FOREACH(votestrings, sized_chunk_t *, c, tor_free(c));
03108   smartlist_free(votestrings);
03109 
03110   {
03111     char legacy_dbuf[DIGEST_LEN];
03112     crypto_pk_t *legacy_sign=NULL;
03113     char *legacy_id_digest = NULL;
03114     int n_generated = 0;
03115     if (get_options()->V3AuthUseLegacyKey) {
03116       authority_cert_t *cert = get_my_v3_legacy_cert();
03117       legacy_sign = get_my_v3_legacy_signing_key();
03118       if (cert) {
03119         if (crypto_pk_get_digest(cert->identity_key, legacy_dbuf)) {
03120           log_warn(LD_BUG,
03121                    "Unable to compute digest of legacy v3 identity key");
03122         } else {
03123           legacy_id_digest = legacy_dbuf;
03124         }
03125       }
03126     }
03127 
03128     for (flav = 0; flav < N_CONSENSUS_FLAVORS; ++flav) {
03129       const char *flavor_name = networkstatus_get_flavor_name(flav);
03130       consensus_body = networkstatus_compute_consensus(
03131         votes, n_voters,
03132         my_cert->identity_key,
03133         get_my_v3_authority_signing_key(), legacy_id_digest, legacy_sign,
03134         flav);
03135 
03136       if (!consensus_body) {
03137         log_warn(LD_DIR, "Couldn't generate a %s consensus at all!",
03138                  flavor_name);
03139         continue;
03140       }
03141       consensus = networkstatus_parse_vote_from_string(consensus_body, NULL,
03142                                                        NS_TYPE_CONSENSUS);
03143       if (!consensus) {
03144         log_warn(LD_DIR, "Couldn't parse %s consensus we generated!",
03145                  flavor_name);
03146         tor_free(consensus_body);
03147         continue;
03148       }
03149 
03150       /* 'Check' our own signature, to mark it valid. */
03151       networkstatus_check_consensus_signature(consensus, -1);
03152 
03153       pending[flav].body = consensus_body;
03154       pending[flav].consensus = consensus;
03155       n_generated++;
03156       consensus_body = NULL;
03157       consensus = NULL;
03158     }
03159     if (!n_generated) {
03160       log_warn(LD_DIR, "Couldn't generate any consensus flavors at all.");
03161       goto err;
03162     }
03163   }
03164 
03165   signatures = get_detached_signatures_from_pending_consensuses(
03166        pending, N_CONSENSUS_FLAVORS);
03167 
03168   if (!signatures) {
03169     log_warn(LD_DIR, "Couldn't extract signatures.");
03170     goto err;
03171   }
03172 
03173   dirvote_clear_pending_consensuses();
03174   memcpy(pending_consensuses, pending, sizeof(pending));
03175 
03176   tor_free(pending_consensus_signatures);
03177   pending_consensus_signatures = signatures;
03178 
03179   if (pending_consensus_signature_list) {
03180     int n_sigs = 0;
03181     /* we may have gotten signatures for this consensus before we built
03182      * it ourself.  Add them now. */
03183     SMARTLIST_FOREACH(pending_consensus_signature_list, char *, sig,
03184       {
03185         const char *msg = NULL;
03186         int r = dirvote_add_signatures_to_all_pending_consensuses(sig,
03187                                                      "pending", &msg);
03188         if (r >= 0)
03189           n_sigs += r;
03190         else
03191           log_warn(LD_DIR,
03192                    "Could not add queued signature to new consensus: %s",
03193                    msg);
03194         tor_free(sig);
03195       });
03196     if (n_sigs)
03197       log_notice(LD_DIR, "Added %d pending signatures while building "
03198                  "consensus.", n_sigs);
03199     smartlist_clear(pending_consensus_signature_list);
03200   }
03201 
03202   log_notice(LD_DIR, "Consensus computed; uploading signature(s)");
03203 
03204   directory_post_to_dirservers(DIR_PURPOSE_UPLOAD_SIGNATURES,
03205                                ROUTER_PURPOSE_GENERAL,
03206                                V3_DIRINFO,
03207                                pending_consensus_signatures,
03208                                strlen(pending_consensus_signatures), 0);
03209   log_notice(LD_DIR, "Signature(s) posted.");
03210 
03211   smartlist_free(votes);
03212   return 0;
03213  err:
03214   smartlist_free(votes);
03215   tor_free(consensus_body);
03216   tor_free(signatures);
03217   networkstatus_vote_free(consensus);
03218 
03219   return -1;
03220 }
03221 
03225 static int
03226 dirvote_add_signatures_to_pending_consensus(
03227                        pending_consensus_t *pc,
03228                        ns_detached_signatures_t *sigs,
03229                        const char *source,
03230                        int severity,
03231                        const char **msg_out)
03232 {
03233   const char *flavor_name;
03234   int r = -1;
03235 
03236   /* Only call if we have a pending consensus right now. */
03237   tor_assert(pc->consensus);
03238   tor_assert(pc->body);
03239   tor_assert(pending_consensus_signatures);
03240 
03241   flavor_name = networkstatus_get_flavor_name(pc->consensus->flavor);
03242   *msg_out = NULL;
03243 
03244   {
03245     smartlist_t *sig_list = strmap_get(sigs->signatures, flavor_name);
03246     log_info(LD_DIR, "Have %d signatures for adding to %s consensus.",
03247              sig_list ? smartlist_len(sig_list) : 0, flavor_name);
03248   }
03249   r = networkstatus_add_detached_signatures(pc->consensus, sigs,
03250                                             source, severity, msg_out);
03251   log_info(LD_DIR,"Added %d signatures to consensus.", r);
03252 
03253   if (r >= 1) {
03254     char *new_signatures =
03255       networkstatus_format_signatures(pc->consensus, 0);
03256     char *dst, *dst_end;
03257     size_t new_consensus_len;
03258     if (!new_signatures) {
03259       *msg_out = "No signatures to add";
03260       goto err;
03261     }
03262     new_consensus_len =
03263       strlen(pc->body) + strlen(new_signatures) + 1;
03264     pc->body = tor_realloc(pc->body, new_consensus_len);
03265     dst_end = pc->body + new_consensus_len;
03266     dst = strstr(pc->body, "directory-signature ");
03267     tor_assert(dst);
03268     strlcpy(dst, new_signatures, dst_end-dst);
03269 
03270     /* We remove this block once it has failed to crash for a while.  But
03271      * unless it shows up in profiles, we're probably better leaving it in,
03272      * just in case we break detached signature processing at some point. */
03273     {
03274       networkstatus_t *v = networkstatus_parse_vote_from_string(
03275                                              pc->body, NULL,
03276                                              NS_TYPE_CONSENSUS);
03277       tor_assert(v);
03278       networkstatus_vote_free(v);
03279     }
03280     *msg_out = "Signatures added";
03281     tor_free(new_signatures);
03282   } else if (r == 0) {
03283     *msg_out = "Signatures ignored";
03284   } else {
03285     goto err;
03286   }
03287 
03288   goto done;
03289  err:
03290   if (!*msg_out)
03291     *msg_out = "Unrecognized error while adding detached signatures.";
03292  done:
03293   return r;
03294 }
03295 
03296 static int
03297 dirvote_add_signatures_to_all_pending_consensuses(
03298                        const char *detached_signatures_body,
03299                        const char *source,
03300                        const char **msg_out)
03301 {
03302   int r=0, i, n_added = 0, errors = 0;
03303   ns_detached_signatures_t *sigs;
03304   tor_assert(detached_signatures_body);
03305   tor_assert(msg_out);
03306   tor_assert(pending_consensus_signatures);
03307 
03308   if (!(sigs = networkstatus_parse_detached_signatures(
03309                                detached_signatures_body, NULL))) {
03310     *msg_out = "Couldn't parse detached signatures.";
03311     goto err;
03312   }
03313 
03314   for (i = 0; i < N_CONSENSUS_FLAVORS; ++i) {
03315     int res;
03316     int severity = i == FLAV_NS ? LOG_NOTICE : LOG_INFO;
03317     pending_consensus_t *pc = &pending_consensuses[i];
03318     if (!pc->consensus)
03319       continue;
03320     res = dirvote_add_signatures_to_pending_consensus(pc, sigs, source,
03321                                                       severity, msg_out);
03322     if (res < 0)
03323       errors++;
03324     else
03325       n_added += res;
03326   }
03327 
03328   if (errors && !n_added) {
03329     r = -1;
03330     goto err;
03331   }
03332 
03333   if (n_added && pending_consensuses[FLAV_NS].consensus) {
03334     char *new_detached =
03335       get_detached_signatures_from_pending_consensuses(
03336                       pending_consensuses, N_CONSENSUS_FLAVORS);
03337     if (new_detached) {
03338       tor_free(pending_consensus_signatures);
03339       pending_consensus_signatures = new_detached;
03340     }
03341   }
03342 
03343   r = n_added;
03344   goto done;
03345  err:
03346   if (!*msg_out)
03347     *msg_out = "Unrecognized error while adding detached signatures.";
03348  done:
03349   ns_detached_signatures_free(sigs);
03350   /* XXXX NM Check how return is used.  We can now have an error *and*
03351      signatures added. */
03352   return r;
03353 }
03354 
03359 int
03360 dirvote_add_signatures(const char *detached_signatures_body,
03361                        const char *source,
03362                        const char **msg)
03363 {
03364   if (pending_consensuses[FLAV_NS].consensus) {
03365     log_notice(LD_DIR, "Got a signature from %s. "
03366                        "Adding it to the pending consensus.", source);
03367     return dirvote_add_signatures_to_all_pending_consensuses(
03368                                      detached_signatures_body, source, msg);
03369   } else {
03370     log_notice(LD_DIR, "Got a signature from %s. "
03371                        "Queuing it for the next consensus.", source);
03372     if (!pending_consensus_signature_list)
03373       pending_consensus_signature_list = smartlist_new();
03374     smartlist_add(pending_consensus_signature_list,
03375                   tor_strdup(detached_signatures_body));
03376     *msg = "Signature queued";
03377     return 0;
03378   }
03379 }
03380 
03383 static int
03384 dirvote_publish_consensus(void)
03385 {
03386   int i;
03387 
03388   /* Now remember all the other consensuses as if we were a directory cache. */
03389   for (i = 0; i < N_CONSENSUS_FLAVORS; ++i) {
03390     pending_consensus_t *pending = &pending_consensuses[i];
03391     const char *name;
03392     name = networkstatus_get_flavor_name(i);
03393     tor_assert(name);
03394     if (!pending->consensus ||
03395       networkstatus_check_consensus_signature(pending->consensus, 1)<0) {
03396       log_warn(LD_DIR, "Not enough info to publish pending %s consensus",name);
03397       continue;
03398     }
03399 
03400     if (networkstatus_set_current_consensus(pending->body, name, 0))
03401       log_warn(LD_DIR, "Error publishing %s consensus", name);
03402     else
03403       log_notice(LD_DIR, "Published %s consensus", name);
03404   }
03405 
03406   return 0;
03407 }
03408 
03410 void
03411 dirvote_free_all(void)
03412 {
03413   dirvote_clear_votes(1);
03414   /* now empty as a result of dirvote_clear_votes(). */
03415   smartlist_free(pending_vote_list);
03416   pending_vote_list = NULL;
03417   smartlist_free(previous_vote_list);
03418   previous_vote_list = NULL;
03419 
03420   dirvote_clear_pending_consensuses();
03421   tor_free(pending_consensus_signatures);
03422   if (pending_consensus_signature_list) {
03423     /* now empty as a result of dirvote_clear_votes(). */
03424     smartlist_free(pending_consensus_signature_list);
03425     pending_consensus_signature_list = NULL;
03426   }
03427 }
03428 
03429 /* ====
03430  * Access to pending items.
03431  * ==== */
03432 
03434 const char *
03435 dirvote_get_pending_consensus(consensus_flavor_t flav)
03436 {
03437   tor_assert(((int)flav) >= 0 && flav < N_CONSENSUS_FLAVORS);
03438   return pending_consensuses[flav].body;
03439 }
03440 
03443 const char *
03444 dirvote_get_pending_detached_signatures(void)
03445 {
03446   return pending_consensus_signatures;
03447 }
03448 
03457 const cached_dir_t *
03458 dirvote_get_vote(const char *fp, int flags)
03459 {
03460   int by_id = flags & DGV_BY_ID;
03461   const int include_pending = flags & DGV_INCLUDE_PENDING;
03462   const int include_previous = flags & DGV_INCLUDE_PREVIOUS;
03463 
03464   if (!pending_vote_list && !previous_vote_list)
03465     return NULL;
03466   if (fp == NULL) {
03467     authority_cert_t *c = get_my_v3_authority_cert();
03468     if (c) {
03469       fp = c->cache_info.identity_digest;
03470       by_id = 1;
03471     } else
03472       return NULL;
03473   }
03474   if (by_id) {
03475     if (pending_vote_list && include_pending) {
03476       SMARTLIST_FOREACH(pending_vote_list, pending_vote_t *, pv,
03477         if (fast_memeq(get_voter(pv->vote)->identity_digest, fp, DIGEST_LEN))
03478           return pv->vote_body);
03479     }
03480     if (previous_vote_list && include_previous) {
03481       SMARTLIST_FOREACH(previous_vote_list, pending_vote_t *, pv,
03482         if (fast_memeq(get_voter(pv->vote)->identity_digest, fp, DIGEST_LEN))
03483           return pv->vote_body);
03484     }
03485   } else {
03486     if (pending_vote_list && include_pending) {
03487       SMARTLIST_FOREACH(pending_vote_list, pending_vote_t *, pv,
03488         if (fast_memeq(pv->vote->digests.d[DIGEST_SHA1], fp, DIGEST_LEN))
03489           return pv->vote_body);
03490     }
03491     if (previous_vote_list && include_previous) {
03492       SMARTLIST_FOREACH(previous_vote_list, pending_vote_t *, pv,
03493         if (fast_memeq(pv->vote->digests.d[DIGEST_SHA1], fp, DIGEST_LEN))
03494           return pv->vote_body);
03495     }
03496   }
03497   return NULL;
03498 }
03499 
03507 microdesc_t *
03508 dirvote_create_microdescriptor(const routerinfo_t *ri)
03509 {
03510   microdesc_t *result = NULL;
03511   char *key = NULL, *summary = NULL, *family = NULL;
03512   char buf[1024];
03513   size_t keylen;
03514   char *out = buf, *end = buf+sizeof(buf);
03515 
03516   if (crypto_pk_write_public_key_to_string(ri->onion_pkey, &key, &keylen)<0)
03517     goto done;
03518   summary = policy_summarize(ri->exit_policy);
03519   if (ri->declared_family)
03520     family = smartlist_join_strings(ri->declared_family, " ", 0, NULL);
03521 
03522   if (tor_snprintf(out, end-out, "onion-key\n%s", key)<0)
03523     goto done;
03524   out += strlen(out);
03525   if (family) {
03526     if (tor_snprintf(out, end-out, "family %s\n", family)<0)
03527       goto done;
03528     out += strlen(out);
03529   }
03530   if (summary && strcmp(summary, "reject 1-65535")) {
03531     if (tor_snprintf(out, end-out, "p %s\n", summary)<0)
03532       goto done;
03533     out += strlen(out);
03534   }
03535   *out = '\0'; /* Make sure it's nul-terminated.  This should be a no-op */
03536 
03537   {
03538     smartlist_t *lst = microdescs_parse_from_string(buf, out, 0, 1);
03539     if (smartlist_len(lst) != 1) {
03540       log_warn(LD_DIR, "We generated a microdescriptor we couldn't parse.");
03541       SMARTLIST_FOREACH(lst, microdesc_t *, md, microdesc_free(md));
03542       smartlist_free(lst);
03543       goto done;
03544     }
03545     result = smartlist_get(lst, 0);
03546     smartlist_free(lst);
03547   }
03548 
03549  done:
03550   tor_free(key);
03551   tor_free(summary);
03552   tor_free(family);
03553   return result;
03554 }
03555 
03557 static char *microdesc_consensus_methods = NULL;
03558 
03563 ssize_t
03564 dirvote_format_microdesc_vote_line(char *out, size_t out_len,
03565                                    const microdesc_t *md)
03566 {
03567   char d64[BASE64_DIGEST256_LEN+1];
03568   if (!microdesc_consensus_methods) {
03569     microdesc_consensus_methods =
03570       make_consensus_method_list(MIN_METHOD_FOR_MICRODESC,
03571                                  MAX_SUPPORTED_CONSENSUS_METHOD,
03572                                  ",");
03573     tor_assert(microdesc_consensus_methods);
03574   }
03575   if (digest256_to_base64(d64, md->digest)<0)
03576     return -1;
03577 
03578   if (tor_snprintf(out, out_len, "m %s sha256=%s\n",
03579                    microdesc_consensus_methods, d64)<0)
03580     return -1;
03581 
03582   return strlen(out);
03583 }
03584 
03588 int
03589 vote_routerstatus_find_microdesc_hash(char *digest256_out,
03590                                       const vote_routerstatus_t *vrs,
03591                                       int method,
03592                                       digest_algorithm_t alg)
03593 {
03594   /* XXXX only returns the sha256 method. */
03595   const vote_microdesc_hash_t *h;
03596   char mstr[64];
03597   size_t mlen;
03598   char dstr[64];
03599 
03600   tor_snprintf(mstr, sizeof(mstr), "%d", method);
03601   mlen = strlen(mstr);
03602   tor_snprintf(dstr, sizeof(dstr), " %s=",
03603                crypto_digest_algorithm_get_name(alg));
03604 
03605   for (h = vrs->microdesc; h; h = h->next) {
03606     const char *cp = h->microdesc_hash_line;
03607     size_t num_len;
03608     /* cp looks like \d+(,\d+)* (digesttype=val )+ .  Let's hunt for mstr in
03609      * the first part. */
03610     while (1) {
03611       num_len = strspn(cp, "1234567890");
03612       if (num_len == mlen && fast_memeq(mstr, cp, mlen)) {
03613         /* This is the line. */
03614         char buf[BASE64_DIGEST256_LEN+1];
03615         /* XXXX ignores extraneous stuff if the digest is too long.  This
03616          * seems harmless enough, right? */
03617         cp = strstr(cp, dstr);
03618         if (!cp)
03619           return -1;
03620         cp += strlen(dstr);
03621         strlcpy(buf, cp, sizeof(buf));
03622         return digest256_from_base64(digest256_out, buf);
03623       }
03624       if (num_len == 0 || cp[num_len] != ',')
03625         break;
03626       cp += num_len + 1;
03627     }
03628   }
03629   return -1;
03630 }
03631