dirvote.c 127 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582158315841585158615871588158915901591159215931594159515961597159815991600160116021603160416051606160716081609161016111612161316141615161616171618161916201621162216231624162516261627162816291630163116321633163416351636163716381639164016411642164316441645164616471648164916501651165216531654165516561657165816591660166116621663166416651666166716681669167016711672167316741675167616771678167916801681168216831684168516861687168816891690169116921693169416951696169716981699170017011702170317041705170617071708170917101711171217131714171517161717171817191720172117221723172417251726172717281729173017311732173317341735173617371738173917401741174217431744174517461747174817491750175117521753175417551756175717581759176017611762176317641765176617671768176917701771177217731774177517761777177817791780178117821783178417851786178717881789179017911792179317941795179617971798179918001801180218031804180518061807180818091810181118121813181418151816181718181819182018211822182318241825182618271828182918301831183218331834183518361837183818391840184118421843184418451846184718481849185018511852185318541855185618571858185918601861186218631864186518661867186818691870187118721873187418751876187718781879188018811882188318841885188618871888188918901891189218931894189518961897189818991900190119021903190419051906190719081909191019111912191319141915191619171918191919201921192219231924192519261927192819291930193119321933193419351936193719381939194019411942194319441945194619471948194919501951195219531954195519561957195819591960196119621963196419651966196719681969197019711972197319741975197619771978197919801981198219831984198519861987198819891990199119921993199419951996199719981999200020012002200320042005200620072008200920102011201220132014201520162017201820192020202120222023202420252026202720282029203020312032203320342035203620372038203920402041204220432044204520462047204820492050205120522053205420552056205720582059206020612062206320642065206620672068206920702071207220732074207520762077207820792080208120822083208420852086208720882089209020912092209320942095209620972098209921002101210221032104210521062107210821092110211121122113211421152116211721182119212021212122212321242125212621272128212921302131213221332134213521362137213821392140214121422143214421452146214721482149215021512152215321542155215621572158215921602161216221632164216521662167216821692170217121722173217421752176217721782179218021812182218321842185218621872188218921902191219221932194219521962197219821992200220122022203220422052206220722082209221022112212221322142215221622172218221922202221222222232224222522262227222822292230223122322233223422352236223722382239224022412242224322442245224622472248224922502251225222532254225522562257225822592260226122622263226422652266226722682269227022712272227322742275227622772278227922802281228222832284228522862287228822892290229122922293229422952296229722982299230023012302230323042305230623072308230923102311231223132314231523162317231823192320232123222323232423252326232723282329233023312332233323342335233623372338233923402341234223432344234523462347234823492350235123522353235423552356235723582359236023612362236323642365236623672368236923702371237223732374237523762377237823792380238123822383238423852386238723882389239023912392239323942395239623972398239924002401240224032404240524062407240824092410241124122413241424152416241724182419242024212422242324242425242624272428242924302431243224332434243524362437243824392440244124422443244424452446244724482449245024512452245324542455245624572458245924602461246224632464246524662467246824692470247124722473247424752476247724782479248024812482248324842485248624872488248924902491249224932494249524962497249824992500250125022503250425052506250725082509251025112512251325142515251625172518251925202521252225232524252525262527252825292530253125322533253425352536253725382539254025412542254325442545254625472548254925502551255225532554255525562557255825592560256125622563256425652566256725682569257025712572257325742575257625772578257925802581258225832584258525862587258825892590259125922593259425952596259725982599260026012602260326042605260626072608260926102611261226132614261526162617261826192620262126222623262426252626262726282629263026312632263326342635263626372638263926402641264226432644264526462647264826492650265126522653265426552656265726582659266026612662266326642665266626672668266926702671267226732674267526762677267826792680268126822683268426852686268726882689269026912692269326942695269626972698269927002701270227032704270527062707270827092710271127122713271427152716271727182719272027212722272327242725272627272728272927302731273227332734273527362737273827392740274127422743274427452746274727482749275027512752275327542755275627572758275927602761276227632764276527662767276827692770277127722773277427752776277727782779278027812782278327842785278627872788278927902791279227932794279527962797279827992800280128022803280428052806280728082809281028112812281328142815281628172818281928202821282228232824282528262827282828292830283128322833283428352836283728382839284028412842284328442845284628472848284928502851285228532854285528562857285828592860286128622863286428652866286728682869287028712872287328742875287628772878287928802881288228832884288528862887288828892890289128922893289428952896289728982899290029012902290329042905290629072908290929102911291229132914291529162917291829192920292129222923292429252926292729282929293029312932293329342935293629372938293929402941294229432944294529462947294829492950295129522953295429552956295729582959296029612962296329642965296629672968296929702971297229732974297529762977297829792980298129822983298429852986298729882989299029912992299329942995299629972998299930003001300230033004300530063007300830093010301130123013301430153016301730183019302030213022302330243025302630273028302930303031303230333034303530363037303830393040304130423043304430453046304730483049305030513052305330543055305630573058305930603061306230633064306530663067306830693070307130723073307430753076307730783079308030813082308330843085308630873088308930903091309230933094309530963097309830993100310131023103310431053106310731083109311031113112311331143115311631173118311931203121312231233124312531263127312831293130313131323133313431353136313731383139314031413142314331443145314631473148314931503151315231533154315531563157315831593160316131623163316431653166316731683169317031713172317331743175317631773178317931803181318231833184318531863187318831893190319131923193319431953196319731983199320032013202320332043205320632073208320932103211321232133214321532163217321832193220322132223223322432253226322732283229323032313232323332343235323632373238323932403241324232433244324532463247324832493250325132523253325432553256325732583259326032613262326332643265326632673268326932703271327232733274327532763277327832793280328132823283328432853286328732883289329032913292329332943295329632973298329933003301330233033304330533063307330833093310331133123313331433153316331733183319332033213322332333243325332633273328332933303331333233333334333533363337333833393340334133423343334433453346334733483349335033513352335333543355335633573358335933603361336233633364336533663367336833693370337133723373337433753376337733783379338033813382338333843385338633873388338933903391339233933394339533963397339833993400340134023403340434053406340734083409341034113412341334143415341634173418341934203421342234233424342534263427342834293430343134323433343434353436343734383439344034413442344334443445344634473448344934503451345234533454345534563457345834593460346134623463346434653466346734683469347034713472347334743475347634773478347934803481348234833484348534863487348834893490349134923493349434953496349734983499350035013502350335043505350635073508350935103511351235133514351535163517351835193520352135223523352435253526352735283529353035313532353335343535353635373538353935403541354235433544354535463547354835493550355135523553355435553556355735583559356035613562356335643565356635673568356935703571357235733574357535763577357835793580358135823583358435853586358735883589359035913592359335943595359635973598359936003601360236033604360536063607360836093610361136123613361436153616361736183619362036213622362336243625362636273628362936303631363236333634363536363637363836393640364136423643364436453646364736483649365036513652365336543655365636573658365936603661366236633664366536663667366836693670367136723673367436753676367736783679368036813682368336843685368636873688368936903691369236933694369536963697
  1. /* Copyright (c) 2001-2004, Roger Dingledine.
  2. * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
  3. * Copyright (c) 2007-2015, The Tor Project, Inc. */
  4. /* See LICENSE for licensing information */
  5. #define DIRVOTE_PRIVATE
  6. #include "or.h"
  7. #include "config.h"
  8. #include "dircollate.h"
  9. #include "directory.h"
  10. #include "dirserv.h"
  11. #include "dirvote.h"
  12. #include "microdesc.h"
  13. #include "networkstatus.h"
  14. #include "policies.h"
  15. #include "rephist.h"
  16. #include "router.h"
  17. #include "routerlist.h"
  18. #include "routerparse.h"
  19. #include "entrynodes.h" /* needed for guardfraction methods */
  20. #include "torcert.h"
  21. /**
  22. * \file dirvote.c
  23. * \brief Functions to compute directory consensus, and schedule voting.
  24. **/
  25. /** A consensus that we have built and are appending signatures to. Once it's
  26. * time to publish it, it will become an active consensus if it accumulates
  27. * enough signatures. */
  28. typedef struct pending_consensus_t {
  29. /** The body of the consensus that we're currently building. Once we
  30. * have it built, it goes into dirserv.c */
  31. char *body;
  32. /** The parsed in-progress consensus document. */
  33. networkstatus_t *consensus;
  34. } pending_consensus_t;
  35. /* DOCDOC dirvote_add_signatures_to_all_pending_consensuses */
  36. static int dirvote_add_signatures_to_all_pending_consensuses(
  37. const char *detached_signatures_body,
  38. const char *source,
  39. const char **msg_out);
  40. static int dirvote_add_signatures_to_pending_consensus(
  41. pending_consensus_t *pc,
  42. ns_detached_signatures_t *sigs,
  43. const char *source,
  44. int severity,
  45. const char **msg_out);
  46. static char *list_v3_auth_ids(void);
  47. static void dirvote_fetch_missing_votes(void);
  48. static void dirvote_fetch_missing_signatures(void);
  49. static int dirvote_perform_vote(void);
  50. static void dirvote_clear_votes(int all_votes);
  51. static int dirvote_compute_consensuses(void);
  52. static int dirvote_publish_consensus(void);
  53. static char *make_consensus_method_list(int low, int high, const char *sep);
  54. /* =====
  55. * Voting
  56. * =====*/
  57. /** Return a new string containing the string representation of the vote in
  58. * <b>v3_ns</b>, signed with our v3 signing key <b>private_signing_key</b>.
  59. * For v3 authorities. */
  60. STATIC char *
  61. format_networkstatus_vote(crypto_pk_t *private_signing_key,
  62. networkstatus_t *v3_ns)
  63. {
  64. smartlist_t *chunks = smartlist_new();
  65. const char *client_versions = NULL, *server_versions = NULL;
  66. char *packages = NULL;
  67. char fingerprint[FINGERPRINT_LEN+1];
  68. char digest[DIGEST_LEN];
  69. uint32_t addr;
  70. char *client_versions_line = NULL, *server_versions_line = NULL;
  71. networkstatus_voter_info_t *voter;
  72. char *status = NULL;
  73. tor_assert(private_signing_key);
  74. tor_assert(v3_ns->type == NS_TYPE_VOTE || v3_ns->type == NS_TYPE_OPINION);
  75. voter = smartlist_get(v3_ns->voters, 0);
  76. addr = voter->addr;
  77. base16_encode(fingerprint, sizeof(fingerprint),
  78. v3_ns->cert->cache_info.identity_digest, DIGEST_LEN);
  79. client_versions = v3_ns->client_versions;
  80. server_versions = v3_ns->server_versions;
  81. if (client_versions) {
  82. tor_asprintf(&client_versions_line, "client-versions %s\n",
  83. client_versions);
  84. } else {
  85. client_versions_line = tor_strdup("");
  86. }
  87. if (server_versions) {
  88. tor_asprintf(&server_versions_line, "server-versions %s\n",
  89. server_versions);
  90. } else {
  91. server_versions_line = tor_strdup("");
  92. }
  93. if (v3_ns->package_lines) {
  94. smartlist_t *tmp = smartlist_new();
  95. SMARTLIST_FOREACH(v3_ns->package_lines, const char *, p,
  96. if (validate_recommended_package_line(p))
  97. smartlist_add_asprintf(tmp, "package %s\n", p));
  98. packages = smartlist_join_strings(tmp, "", 0, NULL);
  99. SMARTLIST_FOREACH(tmp, char *, cp, tor_free(cp));
  100. smartlist_free(tmp);
  101. } else {
  102. packages = tor_strdup("");
  103. }
  104. {
  105. char published[ISO_TIME_LEN+1];
  106. char va[ISO_TIME_LEN+1];
  107. char fu[ISO_TIME_LEN+1];
  108. char vu[ISO_TIME_LEN+1];
  109. char *flags = smartlist_join_strings(v3_ns->known_flags, " ", 0, NULL);
  110. /* XXXX Abstraction violation: should be pulling a field out of v3_ns.*/
  111. char *flag_thresholds = dirserv_get_flag_thresholds_line();
  112. char *params;
  113. authority_cert_t *cert = v3_ns->cert;
  114. char *methods =
  115. make_consensus_method_list(MIN_SUPPORTED_CONSENSUS_METHOD,
  116. MAX_SUPPORTED_CONSENSUS_METHOD, " ");
  117. format_iso_time(published, v3_ns->published);
  118. format_iso_time(va, v3_ns->valid_after);
  119. format_iso_time(fu, v3_ns->fresh_until);
  120. format_iso_time(vu, v3_ns->valid_until);
  121. if (v3_ns->net_params)
  122. params = smartlist_join_strings(v3_ns->net_params, " ", 0, NULL);
  123. else
  124. params = tor_strdup("");
  125. tor_assert(cert);
  126. smartlist_add_asprintf(chunks,
  127. "network-status-version 3\n"
  128. "vote-status %s\n"
  129. "consensus-methods %s\n"
  130. "published %s\n"
  131. "valid-after %s\n"
  132. "fresh-until %s\n"
  133. "valid-until %s\n"
  134. "voting-delay %d %d\n"
  135. "%s%s" /* versions */
  136. "%s" /* packages */
  137. "known-flags %s\n"
  138. "flag-thresholds %s\n"
  139. "params %s\n"
  140. "dir-source %s %s %s %s %d %d\n"
  141. "contact %s\n",
  142. v3_ns->type == NS_TYPE_VOTE ? "vote" : "opinion",
  143. methods,
  144. published, va, fu, vu,
  145. v3_ns->vote_seconds, v3_ns->dist_seconds,
  146. client_versions_line,
  147. server_versions_line,
  148. packages,
  149. flags,
  150. flag_thresholds,
  151. params,
  152. voter->nickname, fingerprint, voter->address,
  153. fmt_addr32(addr), voter->dir_port, voter->or_port,
  154. voter->contact);
  155. tor_free(params);
  156. tor_free(flags);
  157. tor_free(flag_thresholds);
  158. tor_free(methods);
  159. if (!tor_digest_is_zero(voter->legacy_id_digest)) {
  160. char fpbuf[HEX_DIGEST_LEN+1];
  161. base16_encode(fpbuf, sizeof(fpbuf), voter->legacy_id_digest, DIGEST_LEN);
  162. smartlist_add_asprintf(chunks, "legacy-dir-key %s\n", fpbuf);
  163. }
  164. smartlist_add(chunks, tor_strndup(cert->cache_info.signed_descriptor_body,
  165. cert->cache_info.signed_descriptor_len));
  166. }
  167. SMARTLIST_FOREACH_BEGIN(v3_ns->routerstatus_list, vote_routerstatus_t *,
  168. vrs) {
  169. char *rsf;
  170. vote_microdesc_hash_t *h;
  171. rsf = routerstatus_format_entry(&vrs->status,
  172. vrs->version, NS_V3_VOTE, vrs);
  173. if (rsf)
  174. smartlist_add(chunks, rsf);
  175. for (h = vrs->microdesc; h; h = h->next) {
  176. smartlist_add(chunks, tor_strdup(h->microdesc_hash_line));
  177. }
  178. } SMARTLIST_FOREACH_END(vrs);
  179. smartlist_add(chunks, tor_strdup("directory-footer\n"));
  180. /* The digest includes everything up through the space after
  181. * directory-signature. (Yuck.) */
  182. crypto_digest_smartlist(digest, DIGEST_LEN, chunks,
  183. "directory-signature ", DIGEST_SHA1);
  184. {
  185. char signing_key_fingerprint[FINGERPRINT_LEN+1];
  186. if (crypto_pk_get_fingerprint(private_signing_key,
  187. signing_key_fingerprint, 0)<0) {
  188. log_warn(LD_BUG, "Unable to get fingerprint for signing key");
  189. goto err;
  190. }
  191. smartlist_add_asprintf(chunks, "directory-signature %s %s\n", fingerprint,
  192. signing_key_fingerprint);
  193. }
  194. note_crypto_pk_op(SIGN_DIR);
  195. {
  196. char *sig = router_get_dirobj_signature(digest, DIGEST_LEN,
  197. private_signing_key);
  198. if (!sig) {
  199. log_warn(LD_BUG, "Unable to sign networkstatus vote.");
  200. goto err;
  201. }
  202. smartlist_add(chunks, sig);
  203. }
  204. status = smartlist_join_strings(chunks, "", 0, NULL);
  205. {
  206. networkstatus_t *v;
  207. if (!(v = networkstatus_parse_vote_from_string(status, NULL,
  208. v3_ns->type))) {
  209. log_err(LD_BUG,"Generated a networkstatus %s we couldn't parse: "
  210. "<<%s>>",
  211. v3_ns->type == NS_TYPE_VOTE ? "vote" : "opinion", status);
  212. goto err;
  213. }
  214. networkstatus_vote_free(v);
  215. }
  216. goto done;
  217. err:
  218. tor_free(status);
  219. done:
  220. tor_free(client_versions_line);
  221. tor_free(server_versions_line);
  222. tor_free(packages);
  223. SMARTLIST_FOREACH(chunks, char *, cp, tor_free(cp));
  224. smartlist_free(chunks);
  225. return status;
  226. }
  227. /* =====
  228. * Consensus generation
  229. * ===== */
  230. /** Given a vote <b>vote</b> (not a consensus!), return its associated
  231. * networkstatus_voter_info_t. */
  232. static networkstatus_voter_info_t *
  233. get_voter(const networkstatus_t *vote)
  234. {
  235. tor_assert(vote);
  236. tor_assert(vote->type == NS_TYPE_VOTE);
  237. tor_assert(vote->voters);
  238. tor_assert(smartlist_len(vote->voters) == 1);
  239. return smartlist_get(vote->voters, 0);
  240. }
  241. /** Return the signature made by <b>voter</b> using the algorithm
  242. * <b>alg</b>, or NULL if none is found. */
  243. document_signature_t *
  244. voter_get_sig_by_algorithm(const networkstatus_voter_info_t *voter,
  245. digest_algorithm_t alg)
  246. {
  247. if (!voter->sigs)
  248. return NULL;
  249. SMARTLIST_FOREACH(voter->sigs, document_signature_t *, sig,
  250. if (sig->alg == alg)
  251. return sig);
  252. return NULL;
  253. }
  254. /** Temporary structure used in constructing a list of dir-source entries
  255. * for a consensus. One of these is generated for every vote, and one more
  256. * for every legacy key in each vote. */
  257. typedef struct dir_src_ent_t {
  258. networkstatus_t *v;
  259. const char *digest;
  260. int is_legacy;
  261. } dir_src_ent_t;
  262. /** Helper for sorting networkstatus_t votes (not consensuses) by the
  263. * hash of their voters' identity digests. */
  264. static int
  265. compare_votes_by_authority_id_(const void **_a, const void **_b)
  266. {
  267. const networkstatus_t *a = *_a, *b = *_b;
  268. return fast_memcmp(get_voter(a)->identity_digest,
  269. get_voter(b)->identity_digest, DIGEST_LEN);
  270. }
  271. /** Helper: Compare the dir_src_ent_ts in *<b>_a</b> and *<b>_b</b> by
  272. * their identity digests, and return -1, 0, or 1 depending on their
  273. * ordering */
  274. static int
  275. compare_dir_src_ents_by_authority_id_(const void **_a, const void **_b)
  276. {
  277. const dir_src_ent_t *a = *_a, *b = *_b;
  278. const networkstatus_voter_info_t *a_v = get_voter(a->v),
  279. *b_v = get_voter(b->v);
  280. const char *a_id, *b_id;
  281. a_id = a->is_legacy ? a_v->legacy_id_digest : a_v->identity_digest;
  282. b_id = b->is_legacy ? b_v->legacy_id_digest : b_v->identity_digest;
  283. return fast_memcmp(a_id, b_id, DIGEST_LEN);
  284. }
  285. /** Given a sorted list of strings <b>in</b>, add every member to <b>out</b>
  286. * that occurs more than <b>min</b> times. */
  287. static void
  288. get_frequent_members(smartlist_t *out, smartlist_t *in, int min)
  289. {
  290. char *cur = NULL;
  291. int count = 0;
  292. SMARTLIST_FOREACH_BEGIN(in, char *, cp) {
  293. if (cur && !strcmp(cp, cur)) {
  294. ++count;
  295. } else {
  296. if (count > min)
  297. smartlist_add(out, cur);
  298. cur = cp;
  299. count = 1;
  300. }
  301. } SMARTLIST_FOREACH_END(cp);
  302. if (count > min)
  303. smartlist_add(out, cur);
  304. }
  305. /** Given a sorted list of strings <b>lst</b>, return the member that appears
  306. * most. Break ties in favor of later-occurring members. */
  307. #define get_most_frequent_member(lst) \
  308. smartlist_get_most_frequent_string(lst)
  309. /** Return 0 if and only if <b>a</b> and <b>b</b> are routerstatuses
  310. * that come from the same routerinfo, with the same derived elements.
  311. */
  312. static int
  313. compare_vote_rs(const vote_routerstatus_t *a, const vote_routerstatus_t *b)
  314. {
  315. int r;
  316. tor_assert(a);
  317. tor_assert(b);
  318. if ((r = fast_memcmp(a->status.identity_digest, b->status.identity_digest,
  319. DIGEST_LEN)))
  320. return r;
  321. if ((r = fast_memcmp(a->status.descriptor_digest,
  322. b->status.descriptor_digest,
  323. DIGEST_LEN)))
  324. return r;
  325. if ((r = (int)(b->status.published_on - a->status.published_on)))
  326. return r;
  327. if ((r = strcmp(b->status.nickname, a->status.nickname)))
  328. return r;
  329. if ((r = (((int)b->status.addr) - ((int)a->status.addr))))
  330. return r;
  331. if ((r = (((int)b->status.or_port) - ((int)a->status.or_port))))
  332. return r;
  333. if ((r = (((int)b->status.dir_port) - ((int)a->status.dir_port))))
  334. return r;
  335. return 0;
  336. }
  337. /** Helper for sorting routerlists based on compare_vote_rs. */
  338. static int
  339. compare_vote_rs_(const void **_a, const void **_b)
  340. {
  341. const vote_routerstatus_t *a = *_a, *b = *_b;
  342. return compare_vote_rs(a,b);
  343. }
  344. /** Helper for sorting OR ports. */
  345. static int
  346. compare_orports_(const void **_a, const void **_b)
  347. {
  348. const tor_addr_port_t *a = *_a, *b = *_b;
  349. int r;
  350. if ((r = tor_addr_compare(&a->addr, &b->addr, CMP_EXACT)))
  351. return r;
  352. if ((r = (((int) b->port) - ((int) a->port))))
  353. return r;
  354. return 0;
  355. }
  356. /** Given a list of vote_routerstatus_t, all for the same router identity,
  357. * return whichever is most frequent, breaking ties in favor of more
  358. * recently published vote_routerstatus_t and in case of ties there,
  359. * in favor of smaller descriptor digest.
  360. */
  361. static vote_routerstatus_t *
  362. compute_routerstatus_consensus(smartlist_t *votes, int consensus_method,
  363. char *microdesc_digest256_out,
  364. tor_addr_port_t *best_alt_orport_out)
  365. {
  366. vote_routerstatus_t *most = NULL, *cur = NULL;
  367. int most_n = 0, cur_n = 0;
  368. time_t most_published = 0;
  369. /* compare_vote_rs_() sorts the items by identity digest (all the same),
  370. * then by SD digest. That way, if we have a tie that the published_on
  371. * date cannot tie, we use the descriptor with the smaller digest.
  372. */
  373. smartlist_sort(votes, compare_vote_rs_);
  374. SMARTLIST_FOREACH_BEGIN(votes, vote_routerstatus_t *, rs) {
  375. if (cur && !compare_vote_rs(cur, rs)) {
  376. ++cur_n;
  377. } else {
  378. if (cur && (cur_n > most_n ||
  379. (cur_n == most_n &&
  380. cur->status.published_on > most_published))) {
  381. most = cur;
  382. most_n = cur_n;
  383. most_published = cur->status.published_on;
  384. }
  385. cur_n = 1;
  386. cur = rs;
  387. }
  388. } SMARTLIST_FOREACH_END(rs);
  389. if (cur_n > most_n ||
  390. (cur && cur_n == most_n && cur->status.published_on > most_published)) {
  391. most = cur;
  392. most_n = cur_n;
  393. most_published = cur->status.published_on;
  394. }
  395. tor_assert(most);
  396. /* If we're producing "a" lines, vote on potential alternative (sets
  397. * of) OR port(s) in the winning routerstatuses.
  398. *
  399. * XXX prop186 There's at most one alternative OR port (_the_ IPv6
  400. * port) for now. */
  401. if (consensus_method >= MIN_METHOD_FOR_A_LINES && best_alt_orport_out) {
  402. smartlist_t *alt_orports = smartlist_new();
  403. const tor_addr_port_t *most_alt_orport = NULL;
  404. SMARTLIST_FOREACH_BEGIN(votes, vote_routerstatus_t *, rs) {
  405. tor_assert(rs);
  406. if (compare_vote_rs(most, rs) == 0 &&
  407. !tor_addr_is_null(&rs->status.ipv6_addr)
  408. && rs->status.ipv6_orport) {
  409. smartlist_add(alt_orports, tor_addr_port_new(&rs->status.ipv6_addr,
  410. rs->status.ipv6_orport));
  411. }
  412. } SMARTLIST_FOREACH_END(rs);
  413. smartlist_sort(alt_orports, compare_orports_);
  414. most_alt_orport = smartlist_get_most_frequent(alt_orports,
  415. compare_orports_);
  416. if (most_alt_orport) {
  417. memcpy(best_alt_orport_out, most_alt_orport, sizeof(tor_addr_port_t));
  418. log_debug(LD_DIR, "\"a\" line winner for %s is %s",
  419. most->status.nickname,
  420. fmt_addrport(&most_alt_orport->addr, most_alt_orport->port));
  421. }
  422. SMARTLIST_FOREACH(alt_orports, tor_addr_port_t *, ap, tor_free(ap));
  423. smartlist_free(alt_orports);
  424. }
  425. if (microdesc_digest256_out) {
  426. smartlist_t *digests = smartlist_new();
  427. const uint8_t *best_microdesc_digest;
  428. SMARTLIST_FOREACH_BEGIN(votes, vote_routerstatus_t *, rs) {
  429. char d[DIGEST256_LEN];
  430. if (compare_vote_rs(rs, most))
  431. continue;
  432. if (!vote_routerstatus_find_microdesc_hash(d, rs, consensus_method,
  433. DIGEST_SHA256))
  434. smartlist_add(digests, tor_memdup(d, sizeof(d)));
  435. } SMARTLIST_FOREACH_END(rs);
  436. smartlist_sort_digests256(digests);
  437. best_microdesc_digest = smartlist_get_most_frequent_digest256(digests);
  438. if (best_microdesc_digest)
  439. memcpy(microdesc_digest256_out, best_microdesc_digest, DIGEST256_LEN);
  440. SMARTLIST_FOREACH(digests, char *, cp, tor_free(cp));
  441. smartlist_free(digests);
  442. }
  443. return most;
  444. }
  445. /** Sorting helper: compare two strings based on their values as base-ten
  446. * positive integers. (Non-integers are treated as prior to all integers, and
  447. * compared lexically.) */
  448. static int
  449. cmp_int_strings_(const void **_a, const void **_b)
  450. {
  451. const char *a = *_a, *b = *_b;
  452. int ai = (int)tor_parse_long(a, 10, 1, INT_MAX, NULL, NULL);
  453. int bi = (int)tor_parse_long(b, 10, 1, INT_MAX, NULL, NULL);
  454. if (ai<bi) {
  455. return -1;
  456. } else if (ai==bi) {
  457. if (ai == 0) /* Parsing failed. */
  458. return strcmp(a, b);
  459. return 0;
  460. } else {
  461. return 1;
  462. }
  463. }
  464. /** Given a list of networkstatus_t votes, determine and return the number of
  465. * the highest consensus method that is supported by 2/3 of the voters. */
  466. static int
  467. compute_consensus_method(smartlist_t *votes)
  468. {
  469. smartlist_t *all_methods = smartlist_new();
  470. smartlist_t *acceptable_methods = smartlist_new();
  471. smartlist_t *tmp = smartlist_new();
  472. int min = (smartlist_len(votes) * 2) / 3;
  473. int n_ok;
  474. int result;
  475. SMARTLIST_FOREACH(votes, networkstatus_t *, vote,
  476. {
  477. tor_assert(vote->supported_methods);
  478. smartlist_add_all(tmp, vote->supported_methods);
  479. smartlist_sort(tmp, cmp_int_strings_);
  480. smartlist_uniq(tmp, cmp_int_strings_, NULL);
  481. smartlist_add_all(all_methods, tmp);
  482. smartlist_clear(tmp);
  483. });
  484. smartlist_sort(all_methods, cmp_int_strings_);
  485. get_frequent_members(acceptable_methods, all_methods, min);
  486. n_ok = smartlist_len(acceptable_methods);
  487. if (n_ok) {
  488. const char *best = smartlist_get(acceptable_methods, n_ok-1);
  489. result = (int)tor_parse_long(best, 10, 1, INT_MAX, NULL, NULL);
  490. } else {
  491. result = 1;
  492. }
  493. smartlist_free(tmp);
  494. smartlist_free(all_methods);
  495. smartlist_free(acceptable_methods);
  496. return result;
  497. }
  498. /** Return true iff <b>method</b> is a consensus method that we support. */
  499. static int
  500. consensus_method_is_supported(int method)
  501. {
  502. return (method >= MIN_SUPPORTED_CONSENSUS_METHOD) &&
  503. (method <= MAX_SUPPORTED_CONSENSUS_METHOD);
  504. }
  505. /** Return a newly allocated string holding the numbers between low and high
  506. * (inclusive) that are supported consensus methods. */
  507. static char *
  508. make_consensus_method_list(int low, int high, const char *separator)
  509. {
  510. char *list;
  511. int i;
  512. smartlist_t *lst;
  513. lst = smartlist_new();
  514. for (i = low; i <= high; ++i) {
  515. if (!consensus_method_is_supported(i))
  516. continue;
  517. smartlist_add_asprintf(lst, "%d", i);
  518. }
  519. list = smartlist_join_strings(lst, separator, 0, NULL);
  520. tor_assert(list);
  521. SMARTLIST_FOREACH(lst, char *, cp, tor_free(cp));
  522. smartlist_free(lst);
  523. return list;
  524. }
  525. /** Helper: given <b>lst</b>, a list of version strings such that every
  526. * version appears once for every versioning voter who recommends it, return a
  527. * newly allocated string holding the resulting client-versions or
  528. * server-versions list. May change contents of <b>lst</b> */
  529. static char *
  530. compute_consensus_versions_list(smartlist_t *lst, int n_versioning)
  531. {
  532. int min = n_versioning / 2;
  533. smartlist_t *good = smartlist_new();
  534. char *result;
  535. sort_version_list(lst, 0);
  536. get_frequent_members(good, lst, min);
  537. result = smartlist_join_strings(good, ",", 0, NULL);
  538. smartlist_free(good);
  539. return result;
  540. }
  541. /** Minimum number of directory authorities voting for a parameter to
  542. * include it in the consensus, if consensus method 12 or later is to be
  543. * used. See proposal 178 for details. */
  544. #define MIN_VOTES_FOR_PARAM 3
  545. /** Helper: given a list of valid networkstatus_t, return a new string
  546. * containing the contents of the consensus network parameter set.
  547. */
  548. STATIC char *
  549. dirvote_compute_params(smartlist_t *votes, int method, int total_authorities)
  550. {
  551. int i;
  552. int32_t *vals;
  553. int cur_param_len;
  554. const char *cur_param;
  555. const char *eq;
  556. char *result;
  557. const int n_votes = smartlist_len(votes);
  558. smartlist_t *output;
  559. smartlist_t *param_list = smartlist_new();
  560. (void) method;
  561. /* We require that the parameter lists in the votes are well-formed: that
  562. is, that their keywords are unique and sorted, and that their values are
  563. between INT32_MIN and INT32_MAX inclusive. This should be guaranteed by
  564. the parsing code. */
  565. vals = tor_calloc(n_votes, sizeof(int));
  566. SMARTLIST_FOREACH_BEGIN(votes, networkstatus_t *, v) {
  567. if (!v->net_params)
  568. continue;
  569. smartlist_add_all(param_list, v->net_params);
  570. } SMARTLIST_FOREACH_END(v);
  571. if (smartlist_len(param_list) == 0) {
  572. tor_free(vals);
  573. smartlist_free(param_list);
  574. return NULL;
  575. }
  576. smartlist_sort_strings(param_list);
  577. i = 0;
  578. cur_param = smartlist_get(param_list, 0);
  579. eq = strchr(cur_param, '=');
  580. tor_assert(eq);
  581. cur_param_len = (int)(eq+1 - cur_param);
  582. output = smartlist_new();
  583. SMARTLIST_FOREACH_BEGIN(param_list, const char *, param) {
  584. const char *next_param;
  585. int ok=0;
  586. eq = strchr(param, '=');
  587. tor_assert(i<n_votes); /* Make sure we prevented vote-stuffing. */
  588. vals[i++] = (int32_t)
  589. tor_parse_long(eq+1, 10, INT32_MIN, INT32_MAX, &ok, NULL);
  590. tor_assert(ok); /* Already checked these when parsing. */
  591. if (param_sl_idx+1 == smartlist_len(param_list))
  592. next_param = NULL;
  593. else
  594. next_param = smartlist_get(param_list, param_sl_idx+1);
  595. /* resolve spurious clang shallow analysis null pointer errors */
  596. tor_assert(param);
  597. if (!next_param || strncmp(next_param, param, cur_param_len)) {
  598. /* We've reached the end of a series. */
  599. /* Make sure enough authorities voted on this param, unless the
  600. * the consensus method we use is too old for that. */
  601. if (i > total_authorities/2 ||
  602. i >= MIN_VOTES_FOR_PARAM) {
  603. int32_t median = median_int32(vals, i);
  604. char *out_string = tor_malloc(64+cur_param_len);
  605. memcpy(out_string, param, cur_param_len);
  606. tor_snprintf(out_string+cur_param_len,64, "%ld", (long)median);
  607. smartlist_add(output, out_string);
  608. }
  609. i = 0;
  610. if (next_param) {
  611. eq = strchr(next_param, '=');
  612. cur_param_len = (int)(eq+1 - next_param);
  613. }
  614. }
  615. } SMARTLIST_FOREACH_END(param);
  616. result = smartlist_join_strings(output, " ", 0, NULL);
  617. SMARTLIST_FOREACH(output, char *, cp, tor_free(cp));
  618. smartlist_free(output);
  619. smartlist_free(param_list);
  620. tor_free(vals);
  621. return result;
  622. }
  623. #define RANGE_CHECK(a,b,c,d,e,f,g,mx) \
  624. ((a) >= 0 && (a) <= (mx) && (b) >= 0 && (b) <= (mx) && \
  625. (c) >= 0 && (c) <= (mx) && (d) >= 0 && (d) <= (mx) && \
  626. (e) >= 0 && (e) <= (mx) && (f) >= 0 && (f) <= (mx) && \
  627. (g) >= 0 && (g) <= (mx))
  628. #define CHECK_EQ(a, b, margin) \
  629. ((a)-(b) >= 0 ? (a)-(b) <= (margin) : (b)-(a) <= (margin))
  630. typedef enum {
  631. BW_WEIGHTS_NO_ERROR = 0,
  632. BW_WEIGHTS_RANGE_ERROR = 1,
  633. BW_WEIGHTS_SUMG_ERROR = 2,
  634. BW_WEIGHTS_SUME_ERROR = 3,
  635. BW_WEIGHTS_SUMD_ERROR = 4,
  636. BW_WEIGHTS_BALANCE_MID_ERROR = 5,
  637. BW_WEIGHTS_BALANCE_EG_ERROR = 6
  638. } bw_weights_error_t;
  639. /**
  640. * Verify that any weightings satisfy the balanced formulas.
  641. */
  642. static bw_weights_error_t
  643. networkstatus_check_weights(int64_t Wgg, int64_t Wgd, int64_t Wmg,
  644. int64_t Wme, int64_t Wmd, int64_t Wee,
  645. int64_t Wed, int64_t scale, int64_t G,
  646. int64_t M, int64_t E, int64_t D, int64_t T,
  647. int64_t margin, int do_balance) {
  648. bw_weights_error_t berr = BW_WEIGHTS_NO_ERROR;
  649. // Wed + Wmd + Wgd == 1
  650. if (!CHECK_EQ(Wed + Wmd + Wgd, scale, margin)) {
  651. berr = BW_WEIGHTS_SUMD_ERROR;
  652. goto out;
  653. }
  654. // Wmg + Wgg == 1
  655. if (!CHECK_EQ(Wmg + Wgg, scale, margin)) {
  656. berr = BW_WEIGHTS_SUMG_ERROR;
  657. goto out;
  658. }
  659. // Wme + Wee == 1
  660. if (!CHECK_EQ(Wme + Wee, scale, margin)) {
  661. berr = BW_WEIGHTS_SUME_ERROR;
  662. goto out;
  663. }
  664. // Verify weights within range 0->1
  665. if (!RANGE_CHECK(Wgg, Wgd, Wmg, Wme, Wmd, Wed, Wee, scale)) {
  666. berr = BW_WEIGHTS_RANGE_ERROR;
  667. goto out;
  668. }
  669. if (do_balance) {
  670. // Wgg*G + Wgd*D == Wee*E + Wed*D, already scaled
  671. if (!CHECK_EQ(Wgg*G + Wgd*D, Wee*E + Wed*D, (margin*T)/3)) {
  672. berr = BW_WEIGHTS_BALANCE_EG_ERROR;
  673. goto out;
  674. }
  675. // Wgg*G + Wgd*D == M*scale + Wmd*D + Wme*E + Wmg*G, already scaled
  676. if (!CHECK_EQ(Wgg*G + Wgd*D, M*scale + Wmd*D + Wme*E + Wmg*G,
  677. (margin*T)/3)) {
  678. berr = BW_WEIGHTS_BALANCE_MID_ERROR;
  679. goto out;
  680. }
  681. }
  682. out:
  683. if (berr) {
  684. log_info(LD_DIR,
  685. "Bw weight mismatch %d. G="I64_FORMAT" M="I64_FORMAT
  686. " E="I64_FORMAT" D="I64_FORMAT" T="I64_FORMAT
  687. " Wmd=%d Wme=%d Wmg=%d Wed=%d Wee=%d"
  688. " Wgd=%d Wgg=%d Wme=%d Wmg=%d",
  689. berr,
  690. I64_PRINTF_ARG(G), I64_PRINTF_ARG(M), I64_PRINTF_ARG(E),
  691. I64_PRINTF_ARG(D), I64_PRINTF_ARG(T),
  692. (int)Wmd, (int)Wme, (int)Wmg, (int)Wed, (int)Wee,
  693. (int)Wgd, (int)Wgg, (int)Wme, (int)Wmg);
  694. }
  695. return berr;
  696. }
  697. /**
  698. * This function computes the bandwidth weights for consensus method 10.
  699. *
  700. * It returns true if weights could be computed, false otherwise.
  701. */
  702. static int
  703. networkstatus_compute_bw_weights_v10(smartlist_t *chunks, int64_t G,
  704. int64_t M, int64_t E, int64_t D,
  705. int64_t T, int64_t weight_scale)
  706. {
  707. bw_weights_error_t berr = 0;
  708. int64_t Wgg = -1, Wgd = -1;
  709. int64_t Wmg = -1, Wme = -1, Wmd = -1;
  710. int64_t Wed = -1, Wee = -1;
  711. const char *casename;
  712. if (G <= 0 || M <= 0 || E <= 0 || D <= 0) {
  713. log_warn(LD_DIR, "Consensus with empty bandwidth: "
  714. "G="I64_FORMAT" M="I64_FORMAT" E="I64_FORMAT
  715. " D="I64_FORMAT" T="I64_FORMAT,
  716. I64_PRINTF_ARG(G), I64_PRINTF_ARG(M), I64_PRINTF_ARG(E),
  717. I64_PRINTF_ARG(D), I64_PRINTF_ARG(T));
  718. return 0;
  719. }
  720. /*
  721. * Computed from cases in 3.4.3 of dir-spec.txt
  722. *
  723. * 1. Neither are scarce
  724. * 2. Both Guard and Exit are scarce
  725. * a. R+D <= S
  726. * b. R+D > S
  727. * 3. One of Guard or Exit is scarce
  728. * a. S+D < T/3
  729. * b. S+D >= T/3
  730. */
  731. if (3*E >= T && 3*G >= T) { // E >= T/3 && G >= T/3
  732. /* Case 1: Neither are scarce. */
  733. casename = "Case 1 (Wgd=Wmd=Wed)";
  734. Wgd = weight_scale/3;
  735. Wed = weight_scale/3;
  736. Wmd = weight_scale/3;
  737. Wee = (weight_scale*(E+G+M))/(3*E);
  738. Wme = weight_scale - Wee;
  739. Wmg = (weight_scale*(2*G-E-M))/(3*G);
  740. Wgg = weight_scale - Wmg;
  741. berr = networkstatus_check_weights(Wgg, Wgd, Wmg, Wme, Wmd, Wee, Wed,
  742. weight_scale, G, M, E, D, T, 10, 1);
  743. if (berr) {
  744. log_warn(LD_DIR,
  745. "Bw Weights error %d for %s v10. G="I64_FORMAT" M="I64_FORMAT
  746. " E="I64_FORMAT" D="I64_FORMAT" T="I64_FORMAT
  747. " Wmd=%d Wme=%d Wmg=%d Wed=%d Wee=%d"
  748. " Wgd=%d Wgg=%d Wme=%d Wmg=%d weight_scale=%d",
  749. berr, casename,
  750. I64_PRINTF_ARG(G), I64_PRINTF_ARG(M), I64_PRINTF_ARG(E),
  751. I64_PRINTF_ARG(D), I64_PRINTF_ARG(T),
  752. (int)Wmd, (int)Wme, (int)Wmg, (int)Wed, (int)Wee,
  753. (int)Wgd, (int)Wgg, (int)Wme, (int)Wmg, (int)weight_scale);
  754. return 0;
  755. }
  756. } else if (3*E < T && 3*G < T) { // E < T/3 && G < T/3
  757. int64_t R = MIN(E, G);
  758. int64_t S = MAX(E, G);
  759. /*
  760. * Case 2: Both Guards and Exits are scarce
  761. * Balance D between E and G, depending upon
  762. * D capacity and scarcity.
  763. */
  764. if (R+D < S) { // Subcase a
  765. Wgg = weight_scale;
  766. Wee = weight_scale;
  767. Wmg = 0;
  768. Wme = 0;
  769. Wmd = 0;
  770. if (E < G) {
  771. casename = "Case 2a (E scarce)";
  772. Wed = weight_scale;
  773. Wgd = 0;
  774. } else { /* E >= G */
  775. casename = "Case 2a (G scarce)";
  776. Wed = 0;
  777. Wgd = weight_scale;
  778. }
  779. } else { // Subcase b: R+D >= S
  780. casename = "Case 2b1 (Wgg=1, Wmd=Wgd)";
  781. Wee = (weight_scale*(E - G + M))/E;
  782. Wed = (weight_scale*(D - 2*E + 4*G - 2*M))/(3*D);
  783. Wme = (weight_scale*(G-M))/E;
  784. Wmg = 0;
  785. Wgg = weight_scale;
  786. Wmd = (weight_scale - Wed)/2;
  787. Wgd = (weight_scale - Wed)/2;
  788. berr = networkstatus_check_weights(Wgg, Wgd, Wmg, Wme, Wmd, Wee, Wed,
  789. weight_scale, G, M, E, D, T, 10, 1);
  790. if (berr) {
  791. casename = "Case 2b2 (Wgg=1, Wee=1)";
  792. Wgg = weight_scale;
  793. Wee = weight_scale;
  794. Wed = (weight_scale*(D - 2*E + G + M))/(3*D);
  795. Wmd = (weight_scale*(D - 2*M + G + E))/(3*D);
  796. Wme = 0;
  797. Wmg = 0;
  798. if (Wmd < 0) { // Can happen if M > T/3
  799. casename = "Case 2b3 (Wmd=0)";
  800. Wmd = 0;
  801. log_warn(LD_DIR,
  802. "Too much Middle bandwidth on the network to calculate "
  803. "balanced bandwidth-weights. Consider increasing the "
  804. "number of Guard nodes by lowering the requirements.");
  805. }
  806. Wgd = weight_scale - Wed - Wmd;
  807. berr = networkstatus_check_weights(Wgg, Wgd, Wmg, Wme, Wmd, Wee,
  808. Wed, weight_scale, G, M, E, D, T, 10, 1);
  809. }
  810. if (berr != BW_WEIGHTS_NO_ERROR &&
  811. berr != BW_WEIGHTS_BALANCE_MID_ERROR) {
  812. log_warn(LD_DIR,
  813. "Bw Weights error %d for %s v10. G="I64_FORMAT" M="I64_FORMAT
  814. " E="I64_FORMAT" D="I64_FORMAT" T="I64_FORMAT
  815. " Wmd=%d Wme=%d Wmg=%d Wed=%d Wee=%d"
  816. " Wgd=%d Wgg=%d Wme=%d Wmg=%d weight_scale=%d",
  817. berr, casename,
  818. I64_PRINTF_ARG(G), I64_PRINTF_ARG(M), I64_PRINTF_ARG(E),
  819. I64_PRINTF_ARG(D), I64_PRINTF_ARG(T),
  820. (int)Wmd, (int)Wme, (int)Wmg, (int)Wed, (int)Wee,
  821. (int)Wgd, (int)Wgg, (int)Wme, (int)Wmg, (int)weight_scale);
  822. return 0;
  823. }
  824. }
  825. } else { // if (E < T/3 || G < T/3) {
  826. int64_t S = MIN(E, G);
  827. // Case 3: Exactly one of Guard or Exit is scarce
  828. if (!(3*E < T || 3*G < T) || !(3*G >= T || 3*E >= T)) {
  829. log_warn(LD_BUG,
  830. "Bw-Weights Case 3 v10 but with G="I64_FORMAT" M="
  831. I64_FORMAT" E="I64_FORMAT" D="I64_FORMAT" T="I64_FORMAT,
  832. I64_PRINTF_ARG(G), I64_PRINTF_ARG(M), I64_PRINTF_ARG(E),
  833. I64_PRINTF_ARG(D), I64_PRINTF_ARG(T));
  834. }
  835. if (3*(S+D) < T) { // Subcase a: S+D < T/3
  836. if (G < E) {
  837. casename = "Case 3a (G scarce)";
  838. Wgg = Wgd = weight_scale;
  839. Wmd = Wed = Wmg = 0;
  840. // Minor subcase, if E is more scarce than M,
  841. // keep its bandwidth in place.
  842. if (E < M) Wme = 0;
  843. else Wme = (weight_scale*(E-M))/(2*E);
  844. Wee = weight_scale-Wme;
  845. } else { // G >= E
  846. casename = "Case 3a (E scarce)";
  847. Wee = Wed = weight_scale;
  848. Wmd = Wgd = Wme = 0;
  849. // Minor subcase, if G is more scarce than M,
  850. // keep its bandwidth in place.
  851. if (G < M) Wmg = 0;
  852. else Wmg = (weight_scale*(G-M))/(2*G);
  853. Wgg = weight_scale-Wmg;
  854. }
  855. } else { // Subcase b: S+D >= T/3
  856. // D != 0 because S+D >= T/3
  857. if (G < E) {
  858. casename = "Case 3bg (G scarce, Wgg=1, Wmd == Wed)";
  859. Wgg = weight_scale;
  860. Wgd = (weight_scale*(D - 2*G + E + M))/(3*D);
  861. Wmg = 0;
  862. Wee = (weight_scale*(E+M))/(2*E);
  863. Wme = weight_scale - Wee;
  864. Wmd = (weight_scale - Wgd)/2;
  865. Wed = (weight_scale - Wgd)/2;
  866. berr = networkstatus_check_weights(Wgg, Wgd, Wmg, Wme, Wmd, Wee,
  867. Wed, weight_scale, G, M, E, D, T, 10, 1);
  868. } else { // G >= E
  869. casename = "Case 3be (E scarce, Wee=1, Wmd == Wgd)";
  870. Wee = weight_scale;
  871. Wed = (weight_scale*(D - 2*E + G + M))/(3*D);
  872. Wme = 0;
  873. Wgg = (weight_scale*(G+M))/(2*G);
  874. Wmg = weight_scale - Wgg;
  875. Wmd = (weight_scale - Wed)/2;
  876. Wgd = (weight_scale - Wed)/2;
  877. berr = networkstatus_check_weights(Wgg, Wgd, Wmg, Wme, Wmd, Wee,
  878. Wed, weight_scale, G, M, E, D, T, 10, 1);
  879. }
  880. if (berr) {
  881. log_warn(LD_DIR,
  882. "Bw Weights error %d for %s v10. G="I64_FORMAT" M="I64_FORMAT
  883. " E="I64_FORMAT" D="I64_FORMAT" T="I64_FORMAT
  884. " Wmd=%d Wme=%d Wmg=%d Wed=%d Wee=%d"
  885. " Wgd=%d Wgg=%d Wme=%d Wmg=%d weight_scale=%d",
  886. berr, casename,
  887. I64_PRINTF_ARG(G), I64_PRINTF_ARG(M), I64_PRINTF_ARG(E),
  888. I64_PRINTF_ARG(D), I64_PRINTF_ARG(T),
  889. (int)Wmd, (int)Wme, (int)Wmg, (int)Wed, (int)Wee,
  890. (int)Wgd, (int)Wgg, (int)Wme, (int)Wmg, (int)weight_scale);
  891. return 0;
  892. }
  893. }
  894. }
  895. /* We cast down the weights to 32 bit ints on the assumption that
  896. * weight_scale is ~= 10000. We need to ensure a rogue authority
  897. * doesn't break this assumption to rig our weights */
  898. tor_assert(0 < weight_scale && weight_scale <= INT32_MAX);
  899. /*
  900. * Provide Wgm=Wgg, Wmm=1, Wem=Wee, Weg=Wed. May later determine
  901. * that middle nodes need different bandwidth weights for dirport traffic,
  902. * or that weird exit policies need special weight, or that bridges
  903. * need special weight.
  904. *
  905. * NOTE: This list is sorted.
  906. */
  907. smartlist_add_asprintf(chunks,
  908. "bandwidth-weights Wbd=%d Wbe=%d Wbg=%d Wbm=%d "
  909. "Wdb=%d "
  910. "Web=%d Wed=%d Wee=%d Weg=%d Wem=%d "
  911. "Wgb=%d Wgd=%d Wgg=%d Wgm=%d "
  912. "Wmb=%d Wmd=%d Wme=%d Wmg=%d Wmm=%d\n",
  913. (int)Wmd, (int)Wme, (int)Wmg, (int)weight_scale,
  914. (int)weight_scale,
  915. (int)weight_scale, (int)Wed, (int)Wee, (int)Wed, (int)Wee,
  916. (int)weight_scale, (int)Wgd, (int)Wgg, (int)Wgg,
  917. (int)weight_scale, (int)Wmd, (int)Wme, (int)Wmg, (int)weight_scale);
  918. log_notice(LD_CIRC, "Computed bandwidth weights for %s with v10: "
  919. "G="I64_FORMAT" M="I64_FORMAT" E="I64_FORMAT" D="I64_FORMAT
  920. " T="I64_FORMAT,
  921. casename,
  922. I64_PRINTF_ARG(G), I64_PRINTF_ARG(M), I64_PRINTF_ARG(E),
  923. I64_PRINTF_ARG(D), I64_PRINTF_ARG(T));
  924. return 1;
  925. }
  926. /** Update total bandwidth weights (G/M/E/D/T) with the bandwidth of
  927. * the router in <b>rs</b>. */
  928. static void
  929. update_total_bandwidth_weights(const routerstatus_t *rs,
  930. int is_exit, int is_guard,
  931. int64_t *G, int64_t *M, int64_t *E, int64_t *D,
  932. int64_t *T)
  933. {
  934. int default_bandwidth = rs->bandwidth_kb;
  935. int guardfraction_bandwidth = 0;
  936. if (!rs->has_bandwidth) {
  937. log_info(LD_BUG, "Missing consensus bandwidth for router %s",
  938. rs->nickname);
  939. return;
  940. }
  941. /* If this routerstatus represents a guard that we have
  942. * guardfraction information on, use it to calculate its actual
  943. * bandwidth. From proposal236:
  944. *
  945. * Similarly, when calculating the bandwidth-weights line as in
  946. * section 3.8.3 of dir-spec.txt, directory authorities should treat N
  947. * as if fraction F of its bandwidth has the guard flag and (1-F) does
  948. * not. So when computing the totals G,M,E,D, each relay N with guard
  949. * visibility fraction F and bandwidth B should be added as follows:
  950. *
  951. * G' = G + F*B, if N does not have the exit flag
  952. * M' = M + (1-F)*B, if N does not have the exit flag
  953. *
  954. * or
  955. *
  956. * D' = D + F*B, if N has the exit flag
  957. * E' = E + (1-F)*B, if N has the exit flag
  958. *
  959. * In this block of code, we prepare the bandwidth values by setting
  960. * the default_bandwidth to F*B and guardfraction_bandwidth to (1-F)*B.
  961. */
  962. if (rs->has_guardfraction) {
  963. guardfraction_bandwidth_t guardfraction_bw;
  964. tor_assert(is_guard);
  965. guard_get_guardfraction_bandwidth(&guardfraction_bw,
  966. rs->bandwidth_kb,
  967. rs->guardfraction_percentage);
  968. default_bandwidth = guardfraction_bw.guard_bw;
  969. guardfraction_bandwidth = guardfraction_bw.non_guard_bw;
  970. }
  971. /* Now calculate the total bandwidth weights with or without
  972. * guardfraction. Depending on the flags of the relay, add its
  973. * bandwidth to the appropriate weight pool. If it's a guard and
  974. * guardfraction is enabled, add its bandwidth to both pools as
  975. * indicated by the previous comment.
  976. */
  977. *T += default_bandwidth;
  978. if (is_exit && is_guard) {
  979. *D += default_bandwidth;
  980. if (rs->has_guardfraction) {
  981. *E += guardfraction_bandwidth;
  982. }
  983. } else if (is_exit) {
  984. *E += default_bandwidth;
  985. } else if (is_guard) {
  986. *G += default_bandwidth;
  987. if (rs->has_guardfraction) {
  988. *M += guardfraction_bandwidth;
  989. }
  990. } else {
  991. *M += default_bandwidth;
  992. }
  993. }
  994. /** Given a list of vote networkstatus_t in <b>votes</b>, our public
  995. * authority <b>identity_key</b>, our private authority <b>signing_key</b>,
  996. * and the number of <b>total_authorities</b> that we believe exist in our
  997. * voting quorum, generate the text of a new v3 consensus vote, and return the
  998. * value in a newly allocated string.
  999. *
  1000. * Note: this function DOES NOT check whether the votes are from
  1001. * recognized authorities. (dirvote_add_vote does that.) */
  1002. char *
  1003. networkstatus_compute_consensus(smartlist_t *votes,
  1004. int total_authorities,
  1005. crypto_pk_t *identity_key,
  1006. crypto_pk_t *signing_key,
  1007. const char *legacy_id_key_digest,
  1008. crypto_pk_t *legacy_signing_key,
  1009. consensus_flavor_t flavor)
  1010. {
  1011. smartlist_t *chunks;
  1012. char *result = NULL;
  1013. int consensus_method;
  1014. time_t valid_after, fresh_until, valid_until;
  1015. int vote_seconds, dist_seconds;
  1016. char *client_versions = NULL, *server_versions = NULL;
  1017. smartlist_t *flags;
  1018. const char *flavor_name;
  1019. uint32_t max_unmeasured_bw_kb = DEFAULT_MAX_UNMEASURED_BW_KB;
  1020. int64_t G=0, M=0, E=0, D=0, T=0; /* For bandwidth weights */
  1021. const routerstatus_format_type_t rs_format =
  1022. flavor == FLAV_NS ? NS_V3_CONSENSUS : NS_V3_CONSENSUS_MICRODESC;
  1023. char *params = NULL;
  1024. char *packages = NULL;
  1025. int added_weights = 0;
  1026. dircollator_t *collator = NULL;
  1027. tor_assert(flavor == FLAV_NS || flavor == FLAV_MICRODESC);
  1028. tor_assert(total_authorities >= smartlist_len(votes));
  1029. tor_assert(total_authorities > 0);
  1030. flavor_name = networkstatus_get_flavor_name(flavor);
  1031. if (!smartlist_len(votes)) {
  1032. log_warn(LD_DIR, "Can't compute a consensus from no votes.");
  1033. return NULL;
  1034. }
  1035. flags = smartlist_new();
  1036. consensus_method = compute_consensus_method(votes);
  1037. if (consensus_method_is_supported(consensus_method)) {
  1038. log_info(LD_DIR, "Generating consensus using method %d.",
  1039. consensus_method);
  1040. } else {
  1041. log_warn(LD_DIR, "The other authorities will use consensus method %d, "
  1042. "which I don't support. Maybe I should upgrade!",
  1043. consensus_method);
  1044. consensus_method = MAX_SUPPORTED_CONSENSUS_METHOD;
  1045. }
  1046. /* Compute medians of time-related things, and figure out how many
  1047. * routers we might need to talk about. */
  1048. {
  1049. int n_votes = smartlist_len(votes);
  1050. time_t *va_times = tor_calloc(n_votes, sizeof(time_t));
  1051. time_t *fu_times = tor_calloc(n_votes, sizeof(time_t));
  1052. time_t *vu_times = tor_calloc(n_votes, sizeof(time_t));
  1053. int *votesec_list = tor_calloc(n_votes, sizeof(int));
  1054. int *distsec_list = tor_calloc(n_votes, sizeof(int));
  1055. int n_versioning_clients = 0, n_versioning_servers = 0;
  1056. smartlist_t *combined_client_versions = smartlist_new();
  1057. smartlist_t *combined_server_versions = smartlist_new();
  1058. SMARTLIST_FOREACH_BEGIN(votes, networkstatus_t *, v) {
  1059. tor_assert(v->type == NS_TYPE_VOTE);
  1060. va_times[v_sl_idx] = v->valid_after;
  1061. fu_times[v_sl_idx] = v->fresh_until;
  1062. vu_times[v_sl_idx] = v->valid_until;
  1063. votesec_list[v_sl_idx] = v->vote_seconds;
  1064. distsec_list[v_sl_idx] = v->dist_seconds;
  1065. if (v->client_versions) {
  1066. smartlist_t *cv = smartlist_new();
  1067. ++n_versioning_clients;
  1068. smartlist_split_string(cv, v->client_versions, ",",
  1069. SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
  1070. sort_version_list(cv, 1);
  1071. smartlist_add_all(combined_client_versions, cv);
  1072. smartlist_free(cv); /* elements get freed later. */
  1073. }
  1074. if (v->server_versions) {
  1075. smartlist_t *sv = smartlist_new();
  1076. ++n_versioning_servers;
  1077. smartlist_split_string(sv, v->server_versions, ",",
  1078. SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
  1079. sort_version_list(sv, 1);
  1080. smartlist_add_all(combined_server_versions, sv);
  1081. smartlist_free(sv); /* elements get freed later. */
  1082. }
  1083. SMARTLIST_FOREACH(v->known_flags, const char *, cp,
  1084. smartlist_add(flags, tor_strdup(cp)));
  1085. } SMARTLIST_FOREACH_END(v);
  1086. valid_after = median_time(va_times, n_votes);
  1087. fresh_until = median_time(fu_times, n_votes);
  1088. valid_until = median_time(vu_times, n_votes);
  1089. vote_seconds = median_int(votesec_list, n_votes);
  1090. dist_seconds = median_int(distsec_list, n_votes);
  1091. tor_assert(valid_after +
  1092. (get_options()->TestingTorNetwork ?
  1093. MIN_VOTE_INTERVAL_TESTING : MIN_VOTE_INTERVAL) <= fresh_until);
  1094. tor_assert(fresh_until +
  1095. (get_options()->TestingTorNetwork ?
  1096. MIN_VOTE_INTERVAL_TESTING : MIN_VOTE_INTERVAL) <= valid_until);
  1097. tor_assert(vote_seconds >= MIN_VOTE_SECONDS);
  1098. tor_assert(dist_seconds >= MIN_DIST_SECONDS);
  1099. server_versions = compute_consensus_versions_list(combined_server_versions,
  1100. n_versioning_servers);
  1101. client_versions = compute_consensus_versions_list(combined_client_versions,
  1102. n_versioning_clients);
  1103. if (consensus_method >= MIN_METHOD_FOR_PACKAGE_LINES) {
  1104. packages = compute_consensus_package_lines(votes);
  1105. } else {
  1106. packages = tor_strdup("");
  1107. }
  1108. SMARTLIST_FOREACH(combined_server_versions, char *, cp, tor_free(cp));
  1109. SMARTLIST_FOREACH(combined_client_versions, char *, cp, tor_free(cp));
  1110. smartlist_free(combined_server_versions);
  1111. smartlist_free(combined_client_versions);
  1112. smartlist_sort_strings(flags);
  1113. smartlist_uniq_strings(flags);
  1114. tor_free(va_times);
  1115. tor_free(fu_times);
  1116. tor_free(vu_times);
  1117. tor_free(votesec_list);
  1118. tor_free(distsec_list);
  1119. }
  1120. chunks = smartlist_new();
  1121. {
  1122. char va_buf[ISO_TIME_LEN+1], fu_buf[ISO_TIME_LEN+1],
  1123. vu_buf[ISO_TIME_LEN+1];
  1124. char *flaglist;
  1125. format_iso_time(va_buf, valid_after);
  1126. format_iso_time(fu_buf, fresh_until);
  1127. format_iso_time(vu_buf, valid_until);
  1128. flaglist = smartlist_join_strings(flags, " ", 0, NULL);
  1129. smartlist_add_asprintf(chunks, "network-status-version 3%s%s\n"
  1130. "vote-status consensus\n",
  1131. flavor == FLAV_NS ? "" : " ",
  1132. flavor == FLAV_NS ? "" : flavor_name);
  1133. smartlist_add_asprintf(chunks, "consensus-method %d\n",
  1134. consensus_method);
  1135. smartlist_add_asprintf(chunks,
  1136. "valid-after %s\n"
  1137. "fresh-until %s\n"
  1138. "valid-until %s\n"
  1139. "voting-delay %d %d\n"
  1140. "client-versions %s\n"
  1141. "server-versions %s\n"
  1142. "%s" /* packages */
  1143. "known-flags %s\n",
  1144. va_buf, fu_buf, vu_buf,
  1145. vote_seconds, dist_seconds,
  1146. client_versions, server_versions,
  1147. packages,
  1148. flaglist);
  1149. tor_free(flaglist);
  1150. }
  1151. params = dirvote_compute_params(votes, consensus_method,
  1152. total_authorities);
  1153. if (params) {
  1154. smartlist_add(chunks, tor_strdup("params "));
  1155. smartlist_add(chunks, params);
  1156. smartlist_add(chunks, tor_strdup("\n"));
  1157. }
  1158. /* Sort the votes. */
  1159. smartlist_sort(votes, compare_votes_by_authority_id_);
  1160. /* Add the authority sections. */
  1161. {
  1162. smartlist_t *dir_sources = smartlist_new();
  1163. SMARTLIST_FOREACH_BEGIN(votes, networkstatus_t *, v) {
  1164. dir_src_ent_t *e = tor_malloc_zero(sizeof(dir_src_ent_t));
  1165. e->v = v;
  1166. e->digest = get_voter(v)->identity_digest;
  1167. e->is_legacy = 0;
  1168. smartlist_add(dir_sources, e);
  1169. if (!tor_digest_is_zero(get_voter(v)->legacy_id_digest)) {
  1170. dir_src_ent_t *e_legacy = tor_malloc_zero(sizeof(dir_src_ent_t));
  1171. e_legacy->v = v;
  1172. e_legacy->digest = get_voter(v)->legacy_id_digest;
  1173. e_legacy->is_legacy = 1;
  1174. smartlist_add(dir_sources, e_legacy);
  1175. }
  1176. } SMARTLIST_FOREACH_END(v);
  1177. smartlist_sort(dir_sources, compare_dir_src_ents_by_authority_id_);
  1178. SMARTLIST_FOREACH_BEGIN(dir_sources, const dir_src_ent_t *, e) {
  1179. char fingerprint[HEX_DIGEST_LEN+1];
  1180. char votedigest[HEX_DIGEST_LEN+1];
  1181. networkstatus_t *v = e->v;
  1182. networkstatus_voter_info_t *voter = get_voter(v);
  1183. base16_encode(fingerprint, sizeof(fingerprint), e->digest, DIGEST_LEN);
  1184. base16_encode(votedigest, sizeof(votedigest), voter->vote_digest,
  1185. DIGEST_LEN);
  1186. smartlist_add_asprintf(chunks,
  1187. "dir-source %s%s %s %s %s %d %d\n",
  1188. voter->nickname, e->is_legacy ? "-legacy" : "",
  1189. fingerprint, voter->address, fmt_addr32(voter->addr),
  1190. voter->dir_port,
  1191. voter->or_port);
  1192. if (! e->is_legacy) {
  1193. smartlist_add_asprintf(chunks,
  1194. "contact %s\n"
  1195. "vote-digest %s\n",
  1196. voter->contact,
  1197. votedigest);
  1198. }
  1199. } SMARTLIST_FOREACH_END(e);
  1200. SMARTLIST_FOREACH(dir_sources, dir_src_ent_t *, e, tor_free(e));
  1201. smartlist_free(dir_sources);
  1202. }
  1203. if (consensus_method >= MIN_METHOD_TO_CLIP_UNMEASURED_BW) {
  1204. char *max_unmeasured_param = NULL;
  1205. /* XXXX Extract this code into a common function */
  1206. if (params) {
  1207. if (strcmpstart(params, "maxunmeasuredbw=") == 0)
  1208. max_unmeasured_param = params;
  1209. else
  1210. max_unmeasured_param = strstr(params, " maxunmeasuredbw=");
  1211. }
  1212. if (max_unmeasured_param) {
  1213. int ok = 0;
  1214. char *eq = strchr(max_unmeasured_param, '=');
  1215. if (eq) {
  1216. max_unmeasured_bw_kb = (uint32_t)
  1217. tor_parse_ulong(eq+1, 10, 1, UINT32_MAX, &ok, NULL);
  1218. if (!ok) {
  1219. log_warn(LD_DIR, "Bad element '%s' in max unmeasured bw param",
  1220. escaped(max_unmeasured_param));
  1221. max_unmeasured_bw_kb = DEFAULT_MAX_UNMEASURED_BW_KB;
  1222. }
  1223. }
  1224. }
  1225. }
  1226. /* Add the actual router entries. */
  1227. {
  1228. int *index; /* index[j] is the current index into votes[j]. */
  1229. int *size; /* size[j] is the number of routerstatuses in votes[j]. */
  1230. int *flag_counts; /* The number of voters that list flag[j] for the
  1231. * currently considered router. */
  1232. int i;
  1233. smartlist_t *matching_descs = smartlist_new();
  1234. smartlist_t *chosen_flags = smartlist_new();
  1235. smartlist_t *versions = smartlist_new();
  1236. smartlist_t *exitsummaries = smartlist_new();
  1237. uint32_t *bandwidths_kb = tor_calloc(smartlist_len(votes),
  1238. sizeof(uint32_t));
  1239. uint32_t *measured_bws_kb = tor_calloc(smartlist_len(votes),
  1240. sizeof(uint32_t));
  1241. uint32_t *measured_guardfraction = tor_calloc(smartlist_len(votes),
  1242. sizeof(uint32_t));
  1243. int num_bandwidths;
  1244. int num_mbws;
  1245. int num_guardfraction_inputs;
  1246. int *n_voter_flags; /* n_voter_flags[j] is the number of flags that
  1247. * votes[j] knows about. */
  1248. int *n_flag_voters; /* n_flag_voters[f] is the number of votes that care
  1249. * about flags[f]. */
  1250. int **flag_map; /* flag_map[j][b] is an index f such that flag_map[f]
  1251. * is the same flag as votes[j]->known_flags[b]. */
  1252. int *named_flag; /* Index of the flag "Named" for votes[j] */
  1253. int *unnamed_flag; /* Index of the flag "Unnamed" for votes[j] */
  1254. int n_authorities_measuring_bandwidth;
  1255. strmap_t *name_to_id_map = strmap_new();
  1256. char conflict[DIGEST_LEN];
  1257. char unknown[DIGEST_LEN];
  1258. memset(conflict, 0, sizeof(conflict));
  1259. memset(unknown, 0xff, sizeof(conflict));
  1260. index = tor_calloc(smartlist_len(votes), sizeof(int));
  1261. size = tor_calloc(smartlist_len(votes), sizeof(int));
  1262. n_voter_flags = tor_calloc(smartlist_len(votes), sizeof(int));
  1263. n_flag_voters = tor_calloc(smartlist_len(flags), sizeof(int));
  1264. flag_map = tor_calloc(smartlist_len(votes), sizeof(int *));
  1265. named_flag = tor_calloc(smartlist_len(votes), sizeof(int));
  1266. unnamed_flag = tor_calloc(smartlist_len(votes), sizeof(int));
  1267. for (i = 0; i < smartlist_len(votes); ++i)
  1268. unnamed_flag[i] = named_flag[i] = -1;
  1269. /* Build the flag indexes. Note that no vote can have more than 64 members
  1270. * for known_flags, so no value will be greater than 63, so it's safe to
  1271. * do U64_LITERAL(1) << index on these values. But note also that
  1272. * named_flag and unnamed_flag are initialized to -1, so we need to check
  1273. * that they're actually set before doing U64_LITERAL(1) << index with
  1274. * them.*/
  1275. SMARTLIST_FOREACH_BEGIN(votes, networkstatus_t *, v) {
  1276. flag_map[v_sl_idx] = tor_calloc(smartlist_len(v->known_flags),
  1277. sizeof(int));
  1278. if (smartlist_len(v->known_flags) > MAX_KNOWN_FLAGS_IN_VOTE) {
  1279. log_warn(LD_BUG, "Somehow, a vote has %d entries in known_flags",
  1280. smartlist_len(v->known_flags));
  1281. }
  1282. SMARTLIST_FOREACH_BEGIN(v->known_flags, const char *, fl) {
  1283. int p = smartlist_string_pos(flags, fl);
  1284. tor_assert(p >= 0);
  1285. flag_map[v_sl_idx][fl_sl_idx] = p;
  1286. ++n_flag_voters[p];
  1287. if (!strcmp(fl, "Named"))
  1288. named_flag[v_sl_idx] = fl_sl_idx;
  1289. if (!strcmp(fl, "Unnamed"))
  1290. unnamed_flag[v_sl_idx] = fl_sl_idx;
  1291. } SMARTLIST_FOREACH_END(fl);
  1292. n_voter_flags[v_sl_idx] = smartlist_len(v->known_flags);
  1293. size[v_sl_idx] = smartlist_len(v->routerstatus_list);
  1294. } SMARTLIST_FOREACH_END(v);
  1295. /* Named and Unnamed get treated specially */
  1296. {
  1297. SMARTLIST_FOREACH_BEGIN(votes, networkstatus_t *, v) {
  1298. uint64_t nf;
  1299. if (named_flag[v_sl_idx]<0)
  1300. continue;
  1301. nf = U64_LITERAL(1) << named_flag[v_sl_idx];
  1302. SMARTLIST_FOREACH_BEGIN(v->routerstatus_list,
  1303. vote_routerstatus_t *, rs) {
  1304. if ((rs->flags & nf) != 0) {
  1305. const char *d = strmap_get_lc(name_to_id_map, rs->status.nickname);
  1306. if (!d) {
  1307. /* We have no name officially mapped to this digest. */
  1308. strmap_set_lc(name_to_id_map, rs->status.nickname,
  1309. rs->status.identity_digest);
  1310. } else if (d != conflict &&
  1311. fast_memcmp(d, rs->status.identity_digest, DIGEST_LEN)) {
  1312. /* Authorities disagree about this nickname. */
  1313. strmap_set_lc(name_to_id_map, rs->status.nickname, conflict);
  1314. } else {
  1315. /* It's already a conflict, or it's already this ID. */
  1316. }
  1317. }
  1318. } SMARTLIST_FOREACH_END(rs);
  1319. } SMARTLIST_FOREACH_END(v);
  1320. SMARTLIST_FOREACH_BEGIN(votes, networkstatus_t *, v) {
  1321. uint64_t uf;
  1322. if (unnamed_flag[v_sl_idx]<0)
  1323. continue;
  1324. uf = U64_LITERAL(1) << unnamed_flag[v_sl_idx];
  1325. SMARTLIST_FOREACH_BEGIN(v->routerstatus_list,
  1326. vote_routerstatus_t *, rs) {
  1327. if ((rs->flags & uf) != 0) {
  1328. const char *d = strmap_get_lc(name_to_id_map, rs->status.nickname);
  1329. if (d == conflict || d == unknown) {
  1330. /* Leave it alone; we know what it is. */
  1331. } else if (!d) {
  1332. /* We have no name officially mapped to this digest. */
  1333. strmap_set_lc(name_to_id_map, rs->status.nickname, unknown);
  1334. } else if (fast_memeq(d, rs->status.identity_digest, DIGEST_LEN)) {
  1335. /* Authorities disagree about this nickname. */
  1336. strmap_set_lc(name_to_id_map, rs->status.nickname, conflict);
  1337. } else {
  1338. /* It's mapped to a different name. */
  1339. }
  1340. }
  1341. } SMARTLIST_FOREACH_END(rs);
  1342. } SMARTLIST_FOREACH_END(v);
  1343. }
  1344. /* We need to know how many votes measure bandwidth. */
  1345. n_authorities_measuring_bandwidth = 0;
  1346. SMARTLIST_FOREACH(votes, const networkstatus_t *, v,
  1347. if (v->has_measured_bws) {
  1348. ++n_authorities_measuring_bandwidth;
  1349. }
  1350. );
  1351. /* Populate the collator */
  1352. collator = dircollator_new(smartlist_len(votes), total_authorities);
  1353. SMARTLIST_FOREACH_BEGIN(votes, networkstatus_t *, v) {
  1354. dircollator_add_vote(collator, v);
  1355. } SMARTLIST_FOREACH_END(v);
  1356. dircollator_collate(collator, consensus_method);
  1357. /* Now go through all the votes */
  1358. flag_counts = tor_calloc(smartlist_len(flags), sizeof(int));
  1359. const int num_routers = dircollator_n_routers(collator);
  1360. for (i = 0; i < num_routers; ++i) {
  1361. vote_routerstatus_t **vrs_lst =
  1362. dircollator_get_votes_for_router(collator, i);
  1363. vote_routerstatus_t *rs;
  1364. routerstatus_t rs_out;
  1365. const char *current_rsa_id = NULL;
  1366. const char *chosen_version;
  1367. const char *chosen_name = NULL;
  1368. int exitsummary_disagreement = 0;
  1369. int is_named = 0, is_unnamed = 0, is_running = 0;
  1370. int is_guard = 0, is_exit = 0, is_bad_exit = 0;
  1371. int naming_conflict = 0;
  1372. int n_listing = 0;
  1373. char microdesc_digest[DIGEST256_LEN];
  1374. tor_addr_port_t alt_orport = {TOR_ADDR_NULL, 0};
  1375. memset(flag_counts, 0, sizeof(int)*smartlist_len(flags));
  1376. smartlist_clear(matching_descs);
  1377. smartlist_clear(chosen_flags);
  1378. smartlist_clear(versions);
  1379. num_bandwidths = 0;
  1380. num_mbws = 0;
  1381. num_guardfraction_inputs = 0;
  1382. /* Okay, go through all the entries for this digest. */
  1383. for (int voter_idx = 0; voter_idx < smartlist_len(votes); ++voter_idx) {
  1384. if (vrs_lst[voter_idx] == NULL)
  1385. continue; /* This voter had nothing to say about this entry. */
  1386. rs = vrs_lst[voter_idx];
  1387. ++n_listing;
  1388. current_rsa_id = rs->status.identity_digest;
  1389. smartlist_add(matching_descs, rs);
  1390. if (rs->version && rs->version[0])
  1391. smartlist_add(versions, rs->version);
  1392. /* Tally up all the flags. */
  1393. for (int flag = 0; flag < n_voter_flags[voter_idx]; ++flag) {
  1394. if (rs->flags & (U64_LITERAL(1) << flag))
  1395. ++flag_counts[flag_map[voter_idx][flag]];
  1396. }
  1397. if (named_flag[voter_idx] >= 0 &&
  1398. (rs->flags & (U64_LITERAL(1) << named_flag[voter_idx]))) {
  1399. if (chosen_name && strcmp(chosen_name, rs->status.nickname)) {
  1400. log_notice(LD_DIR, "Conflict on naming for router: %s vs %s",
  1401. chosen_name, rs->status.nickname);
  1402. naming_conflict = 1;
  1403. }
  1404. chosen_name = rs->status.nickname;
  1405. }
  1406. /* Count guardfraction votes and note down the values. */
  1407. if (rs->status.has_guardfraction) {
  1408. measured_guardfraction[num_guardfraction_inputs++] =
  1409. rs->status.guardfraction_percentage;
  1410. }
  1411. /* count bandwidths */
  1412. if (rs->has_measured_bw)
  1413. measured_bws_kb[num_mbws++] = rs->measured_bw_kb;
  1414. if (rs->status.has_bandwidth)
  1415. bandwidths_kb[num_bandwidths++] = rs->status.bandwidth_kb;
  1416. }
  1417. /* We don't include this router at all unless more than half of
  1418. * the authorities we believe in list it. */
  1419. if (n_listing <= total_authorities/2)
  1420. continue;
  1421. /* The clangalyzer can't figure out that this will never be NULL
  1422. * if n_listing is at least 1 */
  1423. tor_assert(current_rsa_id);
  1424. /* Figure out the most popular opinion of what the most recent
  1425. * routerinfo and its contents are. */
  1426. memset(microdesc_digest, 0, sizeof(microdesc_digest));
  1427. rs = compute_routerstatus_consensus(matching_descs, consensus_method,
  1428. microdesc_digest, &alt_orport);
  1429. /* Copy bits of that into rs_out. */
  1430. memset(&rs_out, 0, sizeof(rs_out));
  1431. tor_assert(fast_memeq(current_rsa_id,
  1432. rs->status.identity_digest,DIGEST_LEN));
  1433. memcpy(rs_out.identity_digest, current_rsa_id, DIGEST_LEN);
  1434. memcpy(rs_out.descriptor_digest, rs->status.descriptor_digest,
  1435. DIGEST_LEN);
  1436. rs_out.addr = rs->status.addr;
  1437. rs_out.published_on = rs->status.published_on;
  1438. rs_out.dir_port = rs->status.dir_port;
  1439. rs_out.or_port = rs->status.or_port;
  1440. if (consensus_method >= MIN_METHOD_FOR_A_LINES) {
  1441. tor_addr_copy(&rs_out.ipv6_addr, &alt_orport.addr);
  1442. rs_out.ipv6_orport = alt_orport.port;
  1443. }
  1444. rs_out.has_bandwidth = 0;
  1445. rs_out.has_exitsummary = 0;
  1446. if (chosen_name && !naming_conflict) {
  1447. strlcpy(rs_out.nickname, chosen_name, sizeof(rs_out.nickname));
  1448. } else {
  1449. strlcpy(rs_out.nickname, rs->status.nickname, sizeof(rs_out.nickname));
  1450. }
  1451. {
  1452. const char *d = strmap_get_lc(name_to_id_map, rs_out.nickname);
  1453. if (!d) {
  1454. is_named = is_unnamed = 0;
  1455. } else if (fast_memeq(d, current_rsa_id, DIGEST_LEN)) {
  1456. is_named = 1; is_unnamed = 0;
  1457. } else {
  1458. is_named = 0; is_unnamed = 1;
  1459. }
  1460. }
  1461. /* Set the flags. */
  1462. smartlist_add(chosen_flags, (char*)"s"); /* for the start of the line. */
  1463. SMARTLIST_FOREACH_BEGIN(flags, const char *, fl) {
  1464. if (!strcmp(fl, "Named")) {
  1465. if (is_named)
  1466. smartlist_add(chosen_flags, (char*)fl);
  1467. } else if (!strcmp(fl, "Unnamed")) {
  1468. if (is_unnamed)
  1469. smartlist_add(chosen_flags, (char*)fl);
  1470. } else {
  1471. if (flag_counts[fl_sl_idx] > n_flag_voters[fl_sl_idx]/2) {
  1472. smartlist_add(chosen_flags, (char*)fl);
  1473. if (!strcmp(fl, "Exit"))
  1474. is_exit = 1;
  1475. else if (!strcmp(fl, "Guard"))
  1476. is_guard = 1;
  1477. else if (!strcmp(fl, "Running"))
  1478. is_running = 1;
  1479. else if (!strcmp(fl, "BadExit"))
  1480. is_bad_exit = 1;
  1481. }
  1482. }
  1483. } SMARTLIST_FOREACH_END(fl);
  1484. /* Starting with consensus method 4 we do not list servers
  1485. * that are not running in a consensus. See Proposal 138 */
  1486. if (!is_running)
  1487. continue;
  1488. /* Pick the version. */
  1489. if (smartlist_len(versions)) {
  1490. sort_version_list(versions, 0);
  1491. chosen_version = get_most_frequent_member(versions);
  1492. } else {
  1493. chosen_version = NULL;
  1494. }
  1495. /* If it's a guard and we have enough guardfraction votes,
  1496. calculate its consensus guardfraction value. */
  1497. if (is_guard && num_guardfraction_inputs > 2 &&
  1498. consensus_method >= MIN_METHOD_FOR_GUARDFRACTION) {
  1499. rs_out.has_guardfraction = 1;
  1500. rs_out.guardfraction_percentage = median_uint32(measured_guardfraction,
  1501. num_guardfraction_inputs);
  1502. /* final value should be an integer percentage! */
  1503. tor_assert(rs_out.guardfraction_percentage <= 100);
  1504. }
  1505. /* Pick a bandwidth */
  1506. if (num_mbws > 2) {
  1507. rs_out.has_bandwidth = 1;
  1508. rs_out.bw_is_unmeasured = 0;
  1509. rs_out.bandwidth_kb = median_uint32(measured_bws_kb, num_mbws);
  1510. } else if (num_bandwidths > 0) {
  1511. rs_out.has_bandwidth = 1;
  1512. rs_out.bw_is_unmeasured = 1;
  1513. rs_out.bandwidth_kb = median_uint32(bandwidths_kb, num_bandwidths);
  1514. if (consensus_method >= MIN_METHOD_TO_CLIP_UNMEASURED_BW &&
  1515. n_authorities_measuring_bandwidth > 2) {
  1516. /* Cap non-measured bandwidths. */
  1517. if (rs_out.bandwidth_kb > max_unmeasured_bw_kb) {
  1518. rs_out.bandwidth_kb = max_unmeasured_bw_kb;
  1519. }
  1520. }
  1521. }
  1522. /* Fix bug 2203: Do not count BadExit nodes as Exits for bw weights */
  1523. is_exit = is_exit && !is_bad_exit;
  1524. /* Update total bandwidth weights with the bandwidths of this router. */
  1525. {
  1526. update_total_bandwidth_weights(&rs_out,
  1527. is_exit, is_guard,
  1528. &G, &M, &E, &D, &T);
  1529. }
  1530. /* Ok, we already picked a descriptor digest we want to list
  1531. * previously. Now we want to use the exit policy summary from
  1532. * that descriptor. If everybody plays nice all the voters who
  1533. * listed that descriptor will have the same summary. If not then
  1534. * something is fishy and we'll use the most common one (breaking
  1535. * ties in favor of lexicographically larger one (only because it
  1536. * lets me reuse more existing code)).
  1537. *
  1538. * The other case that can happen is that no authority that voted
  1539. * for that descriptor has an exit policy summary. That's
  1540. * probably quite unlikely but can happen. In that case we use
  1541. * the policy that was most often listed in votes, again breaking
  1542. * ties like in the previous case.
  1543. */
  1544. {
  1545. /* Okay, go through all the votes for this router. We prepared
  1546. * that list previously */
  1547. const char *chosen_exitsummary = NULL;
  1548. smartlist_clear(exitsummaries);
  1549. SMARTLIST_FOREACH_BEGIN(matching_descs, vote_routerstatus_t *, vsr) {
  1550. /* Check if the vote where this status comes from had the
  1551. * proper descriptor */
  1552. tor_assert(fast_memeq(rs_out.identity_digest,
  1553. vsr->status.identity_digest,
  1554. DIGEST_LEN));
  1555. if (vsr->status.has_exitsummary &&
  1556. fast_memeq(rs_out.descriptor_digest,
  1557. vsr->status.descriptor_digest,
  1558. DIGEST_LEN)) {
  1559. tor_assert(vsr->status.exitsummary);
  1560. smartlist_add(exitsummaries, vsr->status.exitsummary);
  1561. if (!chosen_exitsummary) {
  1562. chosen_exitsummary = vsr->status.exitsummary;
  1563. } else if (strcmp(chosen_exitsummary, vsr->status.exitsummary)) {
  1564. /* Great. There's disagreement among the voters. That
  1565. * really shouldn't be */
  1566. exitsummary_disagreement = 1;
  1567. }
  1568. }
  1569. } SMARTLIST_FOREACH_END(vsr);
  1570. if (exitsummary_disagreement) {
  1571. char id[HEX_DIGEST_LEN+1];
  1572. char dd[HEX_DIGEST_LEN+1];
  1573. base16_encode(id, sizeof(dd), rs_out.identity_digest, DIGEST_LEN);
  1574. base16_encode(dd, sizeof(dd), rs_out.descriptor_digest, DIGEST_LEN);
  1575. log_warn(LD_DIR, "The voters disagreed on the exit policy summary "
  1576. " for router %s with descriptor %s. This really shouldn't"
  1577. " have happened.", id, dd);
  1578. smartlist_sort_strings(exitsummaries);
  1579. chosen_exitsummary = get_most_frequent_member(exitsummaries);
  1580. } else if (!chosen_exitsummary) {
  1581. char id[HEX_DIGEST_LEN+1];
  1582. char dd[HEX_DIGEST_LEN+1];
  1583. base16_encode(id, sizeof(dd), rs_out.identity_digest, DIGEST_LEN);
  1584. base16_encode(dd, sizeof(dd), rs_out.descriptor_digest, DIGEST_LEN);
  1585. log_warn(LD_DIR, "Not one of the voters that made us select"
  1586. "descriptor %s for router %s had an exit policy"
  1587. "summary", dd, id);
  1588. /* Ok, none of those voting for the digest we chose had an
  1589. * exit policy for us. Well, that kinda sucks.
  1590. */
  1591. smartlist_clear(exitsummaries);
  1592. SMARTLIST_FOREACH(matching_descs, vote_routerstatus_t *, vsr, {
  1593. if (vsr->status.has_exitsummary)
  1594. smartlist_add(exitsummaries, vsr->status.exitsummary);
  1595. });
  1596. smartlist_sort_strings(exitsummaries);
  1597. chosen_exitsummary = get_most_frequent_member(exitsummaries);
  1598. if (!chosen_exitsummary)
  1599. log_warn(LD_DIR, "Wow, not one of the voters had an exit "
  1600. "policy summary for %s. Wow.", id);
  1601. }
  1602. if (chosen_exitsummary) {
  1603. rs_out.has_exitsummary = 1;
  1604. /* yea, discards the const */
  1605. rs_out.exitsummary = (char *)chosen_exitsummary;
  1606. }
  1607. }
  1608. if (flavor == FLAV_MICRODESC &&
  1609. tor_digest256_is_zero(microdesc_digest)) {
  1610. /* With no microdescriptor digest, we omit the entry entirely. */
  1611. continue;
  1612. }
  1613. {
  1614. char *buf;
  1615. /* Okay!! Now we can write the descriptor... */
  1616. /* First line goes into "buf". */
  1617. buf = routerstatus_format_entry(&rs_out, NULL, rs_format, NULL);
  1618. if (buf)
  1619. smartlist_add(chunks, buf);
  1620. }
  1621. /* Now an m line, if applicable. */
  1622. if (flavor == FLAV_MICRODESC &&
  1623. !tor_digest256_is_zero(microdesc_digest)) {
  1624. char m[BASE64_DIGEST256_LEN+1];
  1625. digest256_to_base64(m, microdesc_digest);
  1626. smartlist_add_asprintf(chunks, "m %s\n", m);
  1627. }
  1628. /* Next line is all flags. The "\n" is missing. */
  1629. smartlist_add(chunks,
  1630. smartlist_join_strings(chosen_flags, " ", 0, NULL));
  1631. /* Now the version line. */
  1632. if (chosen_version) {
  1633. smartlist_add(chunks, tor_strdup("\nv "));
  1634. smartlist_add(chunks, tor_strdup(chosen_version));
  1635. }
  1636. smartlist_add(chunks, tor_strdup("\n"));
  1637. /* Now the weight line. */
  1638. if (rs_out.has_bandwidth) {
  1639. char *guardfraction_str = NULL;
  1640. int unmeasured = rs_out.bw_is_unmeasured &&
  1641. consensus_method >= MIN_METHOD_TO_CLIP_UNMEASURED_BW;
  1642. /* If we have guardfraction info, include it in the 'w' line. */
  1643. if (rs_out.has_guardfraction) {
  1644. tor_asprintf(&guardfraction_str,
  1645. " GuardFraction=%u", rs_out.guardfraction_percentage);
  1646. }
  1647. smartlist_add_asprintf(chunks, "w Bandwidth=%d%s%s\n",
  1648. rs_out.bandwidth_kb,
  1649. unmeasured?" Unmeasured=1":"",
  1650. guardfraction_str ? guardfraction_str : "");
  1651. tor_free(guardfraction_str);
  1652. }
  1653. /* Now the exitpolicy summary line. */
  1654. if (rs_out.has_exitsummary && flavor == FLAV_NS) {
  1655. smartlist_add_asprintf(chunks, "p %s\n", rs_out.exitsummary);
  1656. }
  1657. /* And the loop is over and we move on to the next router */
  1658. }
  1659. tor_free(index);
  1660. tor_free(size);
  1661. tor_free(n_voter_flags);
  1662. tor_free(n_flag_voters);
  1663. for (i = 0; i < smartlist_len(votes); ++i)
  1664. tor_free(flag_map[i]);
  1665. tor_free(flag_map);
  1666. tor_free(flag_counts);
  1667. tor_free(named_flag);
  1668. tor_free(unnamed_flag);
  1669. strmap_free(name_to_id_map, NULL);
  1670. smartlist_free(matching_descs);
  1671. smartlist_free(chosen_flags);
  1672. smartlist_free(versions);
  1673. smartlist_free(exitsummaries);
  1674. tor_free(bandwidths_kb);
  1675. tor_free(measured_bws_kb);
  1676. tor_free(measured_guardfraction);
  1677. }
  1678. /* Mark the directory footer region */
  1679. smartlist_add(chunks, tor_strdup("directory-footer\n"));
  1680. {
  1681. int64_t weight_scale = BW_WEIGHT_SCALE;
  1682. char *bw_weight_param = NULL;
  1683. // Parse params, extract BW_WEIGHT_SCALE if present
  1684. // DO NOT use consensus_param_bw_weight_scale() in this code!
  1685. // The consensus is not formed yet!
  1686. /* XXXX Extract this code into a common function */
  1687. if (params) {
  1688. if (strcmpstart(params, "bwweightscale=") == 0)
  1689. bw_weight_param = params;
  1690. else
  1691. bw_weight_param = strstr(params, " bwweightscale=");
  1692. }
  1693. if (bw_weight_param) {
  1694. int ok=0;
  1695. char *eq = strchr(bw_weight_param, '=');
  1696. if (eq) {
  1697. weight_scale = tor_parse_long(eq+1, 10, 1, INT32_MAX, &ok,
  1698. NULL);
  1699. if (!ok) {
  1700. log_warn(LD_DIR, "Bad element '%s' in bw weight param",
  1701. escaped(bw_weight_param));
  1702. weight_scale = BW_WEIGHT_SCALE;
  1703. }
  1704. } else {
  1705. log_warn(LD_DIR, "Bad element '%s' in bw weight param",
  1706. escaped(bw_weight_param));
  1707. weight_scale = BW_WEIGHT_SCALE;
  1708. }
  1709. }
  1710. added_weights = networkstatus_compute_bw_weights_v10(chunks, G, M, E, D,
  1711. T, weight_scale);
  1712. }
  1713. /* Add a signature. */
  1714. {
  1715. char digest[DIGEST256_LEN];
  1716. char fingerprint[HEX_DIGEST_LEN+1];
  1717. char signing_key_fingerprint[HEX_DIGEST_LEN+1];
  1718. digest_algorithm_t digest_alg =
  1719. flavor == FLAV_NS ? DIGEST_SHA1 : DIGEST_SHA256;
  1720. size_t digest_len =
  1721. flavor == FLAV_NS ? DIGEST_LEN : DIGEST256_LEN;
  1722. const char *algname = crypto_digest_algorithm_get_name(digest_alg);
  1723. char *signature;
  1724. smartlist_add(chunks, tor_strdup("directory-signature "));
  1725. /* Compute the hash of the chunks. */
  1726. crypto_digest_smartlist(digest, digest_len, chunks, "", digest_alg);
  1727. /* Get the fingerprints */
  1728. crypto_pk_get_fingerprint(identity_key, fingerprint, 0);
  1729. crypto_pk_get_fingerprint(signing_key, signing_key_fingerprint, 0);
  1730. /* add the junk that will go at the end of the line. */
  1731. if (flavor == FLAV_NS) {
  1732. smartlist_add_asprintf(chunks, "%s %s\n", fingerprint,
  1733. signing_key_fingerprint);
  1734. } else {
  1735. smartlist_add_asprintf(chunks, "%s %s %s\n",
  1736. algname, fingerprint,
  1737. signing_key_fingerprint);
  1738. }
  1739. /* And the signature. */
  1740. if (!(signature = router_get_dirobj_signature(digest, digest_len,
  1741. signing_key))) {
  1742. log_warn(LD_BUG, "Couldn't sign consensus networkstatus.");
  1743. goto done;
  1744. }
  1745. smartlist_add(chunks, signature);
  1746. if (legacy_id_key_digest && legacy_signing_key) {
  1747. smartlist_add(chunks, tor_strdup("directory-signature "));
  1748. base16_encode(fingerprint, sizeof(fingerprint),
  1749. legacy_id_key_digest, DIGEST_LEN);
  1750. crypto_pk_get_fingerprint(legacy_signing_key,
  1751. signing_key_fingerprint, 0);
  1752. if (flavor == FLAV_NS) {
  1753. smartlist_add_asprintf(chunks, "%s %s\n", fingerprint,
  1754. signing_key_fingerprint);
  1755. } else {
  1756. smartlist_add_asprintf(chunks, "%s %s %s\n",
  1757. algname, fingerprint,
  1758. signing_key_fingerprint);
  1759. }
  1760. if (!(signature = router_get_dirobj_signature(digest, digest_len,
  1761. legacy_signing_key))) {
  1762. log_warn(LD_BUG, "Couldn't sign consensus networkstatus.");
  1763. goto done;
  1764. }
  1765. smartlist_add(chunks, signature);
  1766. }
  1767. }
  1768. result = smartlist_join_strings(chunks, "", 0, NULL);
  1769. {
  1770. networkstatus_t *c;
  1771. if (!(c = networkstatus_parse_vote_from_string(result, NULL,
  1772. NS_TYPE_CONSENSUS))) {
  1773. log_err(LD_BUG, "Generated a networkstatus consensus we couldn't "
  1774. "parse.");
  1775. tor_free(result);
  1776. goto done;
  1777. }
  1778. // Verify balancing parameters
  1779. if (added_weights) {
  1780. networkstatus_verify_bw_weights(c, consensus_method);
  1781. }
  1782. networkstatus_vote_free(c);
  1783. }
  1784. done:
  1785. dircollator_free(collator);
  1786. tor_free(client_versions);
  1787. tor_free(server_versions);
  1788. tor_free(packages);
  1789. SMARTLIST_FOREACH(flags, char *, cp, tor_free(cp));
  1790. smartlist_free(flags);
  1791. SMARTLIST_FOREACH(chunks, char *, cp, tor_free(cp));
  1792. smartlist_free(chunks);
  1793. return result;
  1794. }
  1795. /** Given a list of networkstatus_t for each vote, return a newly allocated
  1796. * string containing the "package" lines for the vote. */
  1797. STATIC char *
  1798. compute_consensus_package_lines(smartlist_t *votes)
  1799. {
  1800. const int n_votes = smartlist_len(votes);
  1801. /* This will be a map from "packagename version" strings to arrays
  1802. * of const char *, with the i'th member of the array corresponding to the
  1803. * package line from the i'th vote.
  1804. */
  1805. strmap_t *package_status = strmap_new();
  1806. SMARTLIST_FOREACH_BEGIN(votes, networkstatus_t *, v) {
  1807. if (! v->package_lines)
  1808. continue;
  1809. SMARTLIST_FOREACH_BEGIN(v->package_lines, const char *, line) {
  1810. if (! validate_recommended_package_line(line))
  1811. continue;
  1812. /* Skip 'cp' to the second space in the line. */
  1813. const char *cp = strchr(line, ' ');
  1814. if (!cp) continue;
  1815. ++cp;
  1816. cp = strchr(cp, ' ');
  1817. if (!cp) continue;
  1818. char *key = tor_strndup(line, cp - line);
  1819. const char **status = strmap_get(package_status, key);
  1820. if (!status) {
  1821. status = tor_calloc(n_votes, sizeof(const char *));
  1822. strmap_set(package_status, key, status);
  1823. }
  1824. status[v_sl_idx] = line; /* overwrite old value */
  1825. tor_free(key);
  1826. } SMARTLIST_FOREACH_END(line);
  1827. } SMARTLIST_FOREACH_END(v);
  1828. smartlist_t *entries = smartlist_new(); /* temporary */
  1829. smartlist_t *result_list = smartlist_new(); /* output */
  1830. STRMAP_FOREACH(package_status, key, const char **, values) {
  1831. int i, count=-1;
  1832. for (i = 0; i < n_votes; ++i) {
  1833. if (values[i])
  1834. smartlist_add(entries, (void*) values[i]);
  1835. }
  1836. smartlist_sort_strings(entries);
  1837. int n_voting_for_entry = smartlist_len(entries);
  1838. const char *most_frequent =
  1839. smartlist_get_most_frequent_string_(entries, &count);
  1840. if (n_voting_for_entry >= 3 && count > n_voting_for_entry / 2) {
  1841. smartlist_add_asprintf(result_list, "package %s\n", most_frequent);
  1842. }
  1843. smartlist_clear(entries);
  1844. } STRMAP_FOREACH_END;
  1845. smartlist_sort_strings(result_list);
  1846. char *result = smartlist_join_strings(result_list, "", 0, NULL);
  1847. SMARTLIST_FOREACH(result_list, char *, cp, tor_free(cp));
  1848. smartlist_free(result_list);
  1849. smartlist_free(entries);
  1850. strmap_free(package_status, tor_free_);
  1851. return result;
  1852. }
  1853. /** Given a consensus vote <b>target</b> and a set of detached signatures in
  1854. * <b>sigs</b> that correspond to the same consensus, check whether there are
  1855. * any new signatures in <b>src_voter_list</b> that should be added to
  1856. * <b>target</b>. (A signature should be added if we have no signature for that
  1857. * voter in <b>target</b> yet, or if we have no verifiable signature and the
  1858. * new signature is verifiable.) Return the number of signatures added or
  1859. * changed, or -1 if the document signed by <b>sigs</b> isn't the same
  1860. * document as <b>target</b>. */
  1861. int
  1862. networkstatus_add_detached_signatures(networkstatus_t *target,
  1863. ns_detached_signatures_t *sigs,
  1864. const char *source,
  1865. int severity,
  1866. const char **msg_out)
  1867. {
  1868. int r = 0;
  1869. const char *flavor;
  1870. smartlist_t *siglist;
  1871. tor_assert(sigs);
  1872. tor_assert(target);
  1873. tor_assert(target->type == NS_TYPE_CONSENSUS);
  1874. flavor = networkstatus_get_flavor_name(target->flavor);
  1875. /* Do the times seem right? */
  1876. if (target->valid_after != sigs->valid_after) {
  1877. *msg_out = "Valid-After times do not match "
  1878. "when adding detached signatures to consensus";
  1879. return -1;
  1880. }
  1881. if (target->fresh_until != sigs->fresh_until) {
  1882. *msg_out = "Fresh-until times do not match "
  1883. "when adding detached signatures to consensus";
  1884. return -1;
  1885. }
  1886. if (target->valid_until != sigs->valid_until) {
  1887. *msg_out = "Valid-until times do not match "
  1888. "when adding detached signatures to consensus";
  1889. return -1;
  1890. }
  1891. siglist = strmap_get(sigs->signatures, flavor);
  1892. if (!siglist) {
  1893. *msg_out = "No signatures for given consensus flavor";
  1894. return -1;
  1895. }
  1896. /** Make sure all the digests we know match, and at least one matches. */
  1897. {
  1898. digests_t *digests = strmap_get(sigs->digests, flavor);
  1899. int n_matches = 0;
  1900. int alg;
  1901. if (!digests) {
  1902. *msg_out = "No digests for given consensus flavor";
  1903. return -1;
  1904. }
  1905. for (alg = DIGEST_SHA1; alg < N_DIGEST_ALGORITHMS; ++alg) {
  1906. if (!tor_mem_is_zero(digests->d[alg], DIGEST256_LEN)) {
  1907. if (fast_memeq(target->digests.d[alg], digests->d[alg],
  1908. DIGEST256_LEN)) {
  1909. ++n_matches;
  1910. } else {
  1911. *msg_out = "Mismatched digest.";
  1912. return -1;
  1913. }
  1914. }
  1915. }
  1916. if (!n_matches) {
  1917. *msg_out = "No regognized digests for given consensus flavor";
  1918. }
  1919. }
  1920. /* For each voter in src... */
  1921. SMARTLIST_FOREACH_BEGIN(siglist, document_signature_t *, sig) {
  1922. char voter_identity[HEX_DIGEST_LEN+1];
  1923. networkstatus_voter_info_t *target_voter =
  1924. networkstatus_get_voter_by_id(target, sig->identity_digest);
  1925. authority_cert_t *cert = NULL;
  1926. const char *algorithm;
  1927. document_signature_t *old_sig = NULL;
  1928. algorithm = crypto_digest_algorithm_get_name(sig->alg);
  1929. base16_encode(voter_identity, sizeof(voter_identity),
  1930. sig->identity_digest, DIGEST_LEN);
  1931. log_info(LD_DIR, "Looking at signature from %s using %s", voter_identity,
  1932. algorithm);
  1933. /* If the target doesn't know about this voter, then forget it. */
  1934. if (!target_voter) {
  1935. log_info(LD_DIR, "We do not know any voter with ID %s", voter_identity);
  1936. continue;
  1937. }
  1938. old_sig = voter_get_sig_by_algorithm(target_voter, sig->alg);
  1939. /* If the target already has a good signature from this voter, then skip
  1940. * this one. */
  1941. if (old_sig && old_sig->good_signature) {
  1942. log_info(LD_DIR, "We already have a good signature from %s using %s",
  1943. voter_identity, algorithm);
  1944. continue;
  1945. }
  1946. /* Try checking the signature if we haven't already. */
  1947. if (!sig->good_signature && !sig->bad_signature) {
  1948. cert = authority_cert_get_by_digests(sig->identity_digest,
  1949. sig->signing_key_digest);
  1950. if (cert) {
  1951. /* Not checking the return value here, since we are going to look
  1952. * at the status of sig->good_signature in a moment. */
  1953. (void) networkstatus_check_document_signature(target, sig, cert);
  1954. }
  1955. }
  1956. /* If this signature is good, or we don't have any signature yet,
  1957. * then maybe add it. */
  1958. if (sig->good_signature || !old_sig || old_sig->bad_signature) {
  1959. log_info(LD_DIR, "Adding signature from %s with %s", voter_identity,
  1960. algorithm);
  1961. tor_log(severity, LD_DIR, "Added a signature for %s from %s.",
  1962. target_voter->nickname, source);
  1963. ++r;
  1964. if (old_sig) {
  1965. smartlist_remove(target_voter->sigs, old_sig);
  1966. document_signature_free(old_sig);
  1967. }
  1968. smartlist_add(target_voter->sigs, document_signature_dup(sig));
  1969. } else {
  1970. log_info(LD_DIR, "Not adding signature from %s", voter_identity);
  1971. }
  1972. } SMARTLIST_FOREACH_END(sig);
  1973. return r;
  1974. }
  1975. /** Return a newly allocated string containing all the signatures on
  1976. * <b>consensus</b> by all voters. If <b>for_detached_signatures</b> is true,
  1977. * then the signatures will be put in a detached signatures document, so
  1978. * prefix any non-NS-flavored signatures with "additional-signature" rather
  1979. * than "directory-signature". */
  1980. static char *
  1981. networkstatus_format_signatures(networkstatus_t *consensus,
  1982. int for_detached_signatures)
  1983. {
  1984. smartlist_t *elements;
  1985. char buf[4096];
  1986. char *result = NULL;
  1987. int n_sigs = 0;
  1988. const consensus_flavor_t flavor = consensus->flavor;
  1989. const char *flavor_name = networkstatus_get_flavor_name(flavor);
  1990. const char *keyword;
  1991. if (for_detached_signatures && flavor != FLAV_NS)
  1992. keyword = "additional-signature";
  1993. else
  1994. keyword = "directory-signature";
  1995. elements = smartlist_new();
  1996. SMARTLIST_FOREACH_BEGIN(consensus->voters, networkstatus_voter_info_t *, v) {
  1997. SMARTLIST_FOREACH_BEGIN(v->sigs, document_signature_t *, sig) {
  1998. char sk[HEX_DIGEST_LEN+1];
  1999. char id[HEX_DIGEST_LEN+1];
  2000. if (!sig->signature || sig->bad_signature)
  2001. continue;
  2002. ++n_sigs;
  2003. base16_encode(sk, sizeof(sk), sig->signing_key_digest, DIGEST_LEN);
  2004. base16_encode(id, sizeof(id), sig->identity_digest, DIGEST_LEN);
  2005. if (flavor == FLAV_NS) {
  2006. smartlist_add_asprintf(elements,
  2007. "%s %s %s\n-----BEGIN SIGNATURE-----\n",
  2008. keyword, id, sk);
  2009. } else {
  2010. const char *digest_name =
  2011. crypto_digest_algorithm_get_name(sig->alg);
  2012. smartlist_add_asprintf(elements,
  2013. "%s%s%s %s %s %s\n-----BEGIN SIGNATURE-----\n",
  2014. keyword,
  2015. for_detached_signatures ? " " : "",
  2016. for_detached_signatures ? flavor_name : "",
  2017. digest_name, id, sk);
  2018. }
  2019. base64_encode(buf, sizeof(buf), sig->signature, sig->signature_len,
  2020. BASE64_ENCODE_MULTILINE);
  2021. strlcat(buf, "-----END SIGNATURE-----\n", sizeof(buf));
  2022. smartlist_add(elements, tor_strdup(buf));
  2023. } SMARTLIST_FOREACH_END(sig);
  2024. } SMARTLIST_FOREACH_END(v);
  2025. result = smartlist_join_strings(elements, "", 0, NULL);
  2026. SMARTLIST_FOREACH(elements, char *, cp, tor_free(cp));
  2027. smartlist_free(elements);
  2028. if (!n_sigs)
  2029. tor_free(result);
  2030. return result;
  2031. }
  2032. /** Return a newly allocated string holding the detached-signatures document
  2033. * corresponding to the signatures on <b>consensuses</b>, which must contain
  2034. * exactly one FLAV_NS consensus, and no more than one consensus for each
  2035. * other flavor. */
  2036. char *
  2037. networkstatus_get_detached_signatures(smartlist_t *consensuses)
  2038. {
  2039. smartlist_t *elements;
  2040. char *result = NULL, *sigs = NULL;
  2041. networkstatus_t *consensus_ns = NULL;
  2042. tor_assert(consensuses);
  2043. SMARTLIST_FOREACH(consensuses, networkstatus_t *, ns, {
  2044. tor_assert(ns);
  2045. tor_assert(ns->type == NS_TYPE_CONSENSUS);
  2046. if (ns && ns->flavor == FLAV_NS)
  2047. consensus_ns = ns;
  2048. });
  2049. if (!consensus_ns) {
  2050. log_warn(LD_BUG, "No NS consensus given.");
  2051. return NULL;
  2052. }
  2053. elements = smartlist_new();
  2054. {
  2055. char va_buf[ISO_TIME_LEN+1], fu_buf[ISO_TIME_LEN+1],
  2056. vu_buf[ISO_TIME_LEN+1];
  2057. char d[HEX_DIGEST_LEN+1];
  2058. base16_encode(d, sizeof(d),
  2059. consensus_ns->digests.d[DIGEST_SHA1], DIGEST_LEN);
  2060. format_iso_time(va_buf, consensus_ns->valid_after);
  2061. format_iso_time(fu_buf, consensus_ns->fresh_until);
  2062. format_iso_time(vu_buf, consensus_ns->valid_until);
  2063. smartlist_add_asprintf(elements,
  2064. "consensus-digest %s\n"
  2065. "valid-after %s\n"
  2066. "fresh-until %s\n"
  2067. "valid-until %s\n", d, va_buf, fu_buf, vu_buf);
  2068. }
  2069. /* Get all the digests for the non-FLAV_NS consensuses */
  2070. SMARTLIST_FOREACH_BEGIN(consensuses, networkstatus_t *, ns) {
  2071. const char *flavor_name = networkstatus_get_flavor_name(ns->flavor);
  2072. int alg;
  2073. if (ns->flavor == FLAV_NS)
  2074. continue;
  2075. /* start with SHA256; we don't include SHA1 for anything but the basic
  2076. * consensus. */
  2077. for (alg = DIGEST_SHA256; alg < N_DIGEST_ALGORITHMS; ++alg) {
  2078. char d[HEX_DIGEST256_LEN+1];
  2079. const char *alg_name =
  2080. crypto_digest_algorithm_get_name(alg);
  2081. if (tor_mem_is_zero(ns->digests.d[alg], DIGEST256_LEN))
  2082. continue;
  2083. base16_encode(d, sizeof(d), ns->digests.d[alg], DIGEST256_LEN);
  2084. smartlist_add_asprintf(elements, "additional-digest %s %s %s\n",
  2085. flavor_name, alg_name, d);
  2086. }
  2087. } SMARTLIST_FOREACH_END(ns);
  2088. /* Now get all the sigs for non-FLAV_NS consensuses */
  2089. SMARTLIST_FOREACH_BEGIN(consensuses, networkstatus_t *, ns) {
  2090. char *sigs;
  2091. if (ns->flavor == FLAV_NS)
  2092. continue;
  2093. sigs = networkstatus_format_signatures(ns, 1);
  2094. if (!sigs) {
  2095. log_warn(LD_DIR, "Couldn't format signatures");
  2096. goto err;
  2097. }
  2098. smartlist_add(elements, sigs);
  2099. } SMARTLIST_FOREACH_END(ns);
  2100. /* Now add the FLAV_NS consensus signatrures. */
  2101. sigs = networkstatus_format_signatures(consensus_ns, 1);
  2102. if (!sigs)
  2103. goto err;
  2104. smartlist_add(elements, sigs);
  2105. result = smartlist_join_strings(elements, "", 0, NULL);
  2106. err:
  2107. SMARTLIST_FOREACH(elements, char *, cp, tor_free(cp));
  2108. smartlist_free(elements);
  2109. return result;
  2110. }
  2111. /** Return a newly allocated string holding a detached-signatures document for
  2112. * all of the in-progress consensuses in the <b>n_flavors</b>-element array at
  2113. * <b>pending</b>. */
  2114. static char *
  2115. get_detached_signatures_from_pending_consensuses(pending_consensus_t *pending,
  2116. int n_flavors)
  2117. {
  2118. int flav;
  2119. char *signatures;
  2120. smartlist_t *c = smartlist_new();
  2121. for (flav = 0; flav < n_flavors; ++flav) {
  2122. if (pending[flav].consensus)
  2123. smartlist_add(c, pending[flav].consensus);
  2124. }
  2125. signatures = networkstatus_get_detached_signatures(c);
  2126. smartlist_free(c);
  2127. return signatures;
  2128. }
  2129. /** Release all storage held in <b>s</b>. */
  2130. void
  2131. ns_detached_signatures_free(ns_detached_signatures_t *s)
  2132. {
  2133. if (!s)
  2134. return;
  2135. if (s->signatures) {
  2136. STRMAP_FOREACH(s->signatures, flavor, smartlist_t *, sigs) {
  2137. SMARTLIST_FOREACH(sigs, document_signature_t *, sig,
  2138. document_signature_free(sig));
  2139. smartlist_free(sigs);
  2140. } STRMAP_FOREACH_END;
  2141. strmap_free(s->signatures, NULL);
  2142. strmap_free(s->digests, tor_free_);
  2143. }
  2144. tor_free(s);
  2145. }
  2146. /* =====
  2147. * Certificate functions
  2148. * ===== */
  2149. /** Allocate and return a new authority_cert_t with the same contents as
  2150. * <b>cert</b>. */
  2151. authority_cert_t *
  2152. authority_cert_dup(authority_cert_t *cert)
  2153. {
  2154. authority_cert_t *out = tor_malloc(sizeof(authority_cert_t));
  2155. tor_assert(cert);
  2156. memcpy(out, cert, sizeof(authority_cert_t));
  2157. /* Now copy pointed-to things. */
  2158. out->cache_info.signed_descriptor_body =
  2159. tor_strndup(cert->cache_info.signed_descriptor_body,
  2160. cert->cache_info.signed_descriptor_len);
  2161. out->cache_info.saved_location = SAVED_NOWHERE;
  2162. out->identity_key = crypto_pk_dup_key(cert->identity_key);
  2163. out->signing_key = crypto_pk_dup_key(cert->signing_key);
  2164. return out;
  2165. }
  2166. /* =====
  2167. * Vote scheduling
  2168. * ===== */
  2169. /** Set *<b>timing_out</b> to the intervals at which we would like to vote.
  2170. * Note that these aren't the intervals we'll use to vote; they're the ones
  2171. * that we'll vote to use. */
  2172. void
  2173. dirvote_get_preferred_voting_intervals(vote_timing_t *timing_out)
  2174. {
  2175. const or_options_t *options = get_options();
  2176. tor_assert(timing_out);
  2177. timing_out->vote_interval = options->V3AuthVotingInterval;
  2178. timing_out->n_intervals_valid = options->V3AuthNIntervalsValid;
  2179. timing_out->vote_delay = options->V3AuthVoteDelay;
  2180. timing_out->dist_delay = options->V3AuthDistDelay;
  2181. }
  2182. /** Return the start of the next interval of size <b>interval</b> (in
  2183. * seconds) after <b>now</b>, plus <b>offset</b>. Midnight always
  2184. * starts a fresh interval, and if the last interval of a day would be
  2185. * truncated to less than half its size, it is rolled into the
  2186. * previous interval. */
  2187. time_t
  2188. dirvote_get_start_of_next_interval(time_t now, int interval, int offset)
  2189. {
  2190. struct tm tm;
  2191. time_t midnight_today=0;
  2192. time_t midnight_tomorrow;
  2193. time_t next;
  2194. tor_gmtime_r(&now, &tm);
  2195. tm.tm_hour = 0;
  2196. tm.tm_min = 0;
  2197. tm.tm_sec = 0;
  2198. if (tor_timegm(&tm, &midnight_today) < 0) {
  2199. log_warn(LD_BUG, "Ran into an invalid time when trying to find midnight.");
  2200. }
  2201. midnight_tomorrow = midnight_today + (24*60*60);
  2202. next = midnight_today + ((now-midnight_today)/interval + 1)*interval;
  2203. /* Intervals never cross midnight. */
  2204. if (next > midnight_tomorrow)
  2205. next = midnight_tomorrow;
  2206. /* If the interval would only last half as long as it's supposed to, then
  2207. * skip over to the next day. */
  2208. if (next + interval/2 > midnight_tomorrow)
  2209. next = midnight_tomorrow;
  2210. next += offset;
  2211. if (next - interval > now)
  2212. next -= interval;
  2213. return next;
  2214. }
  2215. /** Scheduling information for a voting interval. */
  2216. static struct {
  2217. /** When do we generate and distribute our vote for this interval? */
  2218. time_t voting_starts;
  2219. /** When do we send an HTTP request for any votes that we haven't
  2220. * been posted yet?*/
  2221. time_t fetch_missing_votes;
  2222. /** When do we give up on getting more votes and generate a consensus? */
  2223. time_t voting_ends;
  2224. /** When do we send an HTTP request for any signatures we're expecting to
  2225. * see on the consensus? */
  2226. time_t fetch_missing_signatures;
  2227. /** When do we publish the consensus? */
  2228. time_t interval_starts;
  2229. /* True iff we have generated and distributed our vote. */
  2230. int have_voted;
  2231. /* True iff we've requested missing votes. */
  2232. int have_fetched_missing_votes;
  2233. /* True iff we have built a consensus and sent the signatures around. */
  2234. int have_built_consensus;
  2235. /* True iff we've fetched missing signatures. */
  2236. int have_fetched_missing_signatures;
  2237. /* True iff we have published our consensus. */
  2238. int have_published_consensus;
  2239. } voting_schedule = {0,0,0,0,0,0,0,0,0,0};
  2240. /** Set voting_schedule to hold the timing for the next vote we should be
  2241. * doing. */
  2242. void
  2243. dirvote_recalculate_timing(const or_options_t *options, time_t now)
  2244. {
  2245. int interval, vote_delay, dist_delay;
  2246. time_t start;
  2247. time_t end;
  2248. networkstatus_t *consensus;
  2249. if (!authdir_mode_v3(options))
  2250. return;
  2251. consensus = networkstatus_get_live_consensus(now);
  2252. memset(&voting_schedule, 0, sizeof(voting_schedule));
  2253. if (consensus) {
  2254. interval = (int)( consensus->fresh_until - consensus->valid_after );
  2255. vote_delay = consensus->vote_seconds;
  2256. dist_delay = consensus->dist_seconds;
  2257. } else {
  2258. interval = options->TestingV3AuthInitialVotingInterval;
  2259. vote_delay = options->TestingV3AuthInitialVoteDelay;
  2260. dist_delay = options->TestingV3AuthInitialDistDelay;
  2261. }
  2262. tor_assert(interval > 0);
  2263. if (vote_delay + dist_delay > interval/2)
  2264. vote_delay = dist_delay = interval / 4;
  2265. start = voting_schedule.interval_starts =
  2266. dirvote_get_start_of_next_interval(now,interval,
  2267. options->TestingV3AuthVotingStartOffset);
  2268. end = dirvote_get_start_of_next_interval(start+1, interval,
  2269. options->TestingV3AuthVotingStartOffset);
  2270. tor_assert(end > start);
  2271. voting_schedule.fetch_missing_signatures = start - (dist_delay/2);
  2272. voting_schedule.voting_ends = start - dist_delay;
  2273. voting_schedule.fetch_missing_votes = start - dist_delay - (vote_delay/2);
  2274. voting_schedule.voting_starts = start - dist_delay - vote_delay;
  2275. {
  2276. char tbuf[ISO_TIME_LEN+1];
  2277. format_iso_time(tbuf, voting_schedule.interval_starts);
  2278. log_notice(LD_DIR,"Choosing expected valid-after time as %s: "
  2279. "consensus_set=%d, interval=%d",
  2280. tbuf, consensus?1:0, interval);
  2281. }
  2282. }
  2283. /** Entry point: Take whatever voting actions are pending as of <b>now</b>. */
  2284. void
  2285. dirvote_act(const or_options_t *options, time_t now)
  2286. {
  2287. if (!authdir_mode_v3(options))
  2288. return;
  2289. if (!voting_schedule.voting_starts) {
  2290. char *keys = list_v3_auth_ids();
  2291. authority_cert_t *c = get_my_v3_authority_cert();
  2292. log_notice(LD_DIR, "Scheduling voting. Known authority IDs are %s. "
  2293. "Mine is %s.",
  2294. keys, hex_str(c->cache_info.identity_digest, DIGEST_LEN));
  2295. tor_free(keys);
  2296. dirvote_recalculate_timing(options, now);
  2297. }
  2298. if (voting_schedule.voting_starts < now && !voting_schedule.have_voted) {
  2299. log_notice(LD_DIR, "Time to vote.");
  2300. dirvote_perform_vote();
  2301. voting_schedule.have_voted = 1;
  2302. }
  2303. if (voting_schedule.fetch_missing_votes < now &&
  2304. !voting_schedule.have_fetched_missing_votes) {
  2305. log_notice(LD_DIR, "Time to fetch any votes that we're missing.");
  2306. dirvote_fetch_missing_votes();
  2307. voting_schedule.have_fetched_missing_votes = 1;
  2308. }
  2309. if (voting_schedule.voting_ends < now &&
  2310. !voting_schedule.have_built_consensus) {
  2311. log_notice(LD_DIR, "Time to compute a consensus.");
  2312. dirvote_compute_consensuses();
  2313. /* XXXX We will want to try again later if we haven't got enough
  2314. * votes yet. Implement this if it turns out to ever happen. */
  2315. voting_schedule.have_built_consensus = 1;
  2316. }
  2317. if (voting_schedule.fetch_missing_signatures < now &&
  2318. !voting_schedule.have_fetched_missing_signatures) {
  2319. log_notice(LD_DIR, "Time to fetch any signatures that we're missing.");
  2320. dirvote_fetch_missing_signatures();
  2321. voting_schedule.have_fetched_missing_signatures = 1;
  2322. }
  2323. if (voting_schedule.interval_starts < now &&
  2324. !voting_schedule.have_published_consensus) {
  2325. log_notice(LD_DIR, "Time to publish the consensus and discard old votes");
  2326. dirvote_publish_consensus();
  2327. dirvote_clear_votes(0);
  2328. voting_schedule.have_published_consensus = 1;
  2329. /* XXXX We will want to try again later if we haven't got enough
  2330. * signatures yet. Implement this if it turns out to ever happen. */
  2331. dirvote_recalculate_timing(options, now);
  2332. }
  2333. }
  2334. /** A vote networkstatus_t and its unparsed body: held around so we can
  2335. * use it to generate a consensus (at voting_ends) and so we can serve it to
  2336. * other authorities that might want it. */
  2337. typedef struct pending_vote_t {
  2338. cached_dir_t *vote_body;
  2339. networkstatus_t *vote;
  2340. } pending_vote_t;
  2341. /** List of pending_vote_t for the current vote. Before we've used them to
  2342. * build a consensus, the votes go here. */
  2343. static smartlist_t *pending_vote_list = NULL;
  2344. /** List of pending_vote_t for the previous vote. After we've used them to
  2345. * build a consensus, the votes go here for the next period. */
  2346. static smartlist_t *previous_vote_list = NULL;
  2347. /* DOCDOC pending_consensuses */
  2348. static pending_consensus_t pending_consensuses[N_CONSENSUS_FLAVORS];
  2349. /** The detached signatures for the consensus that we're currently
  2350. * building. */
  2351. static char *pending_consensus_signatures = NULL;
  2352. /** List of ns_detached_signatures_t: hold signatures that get posted to us
  2353. * before we have generated the consensus on our own. */
  2354. static smartlist_t *pending_consensus_signature_list = NULL;
  2355. /** Generate a networkstatus vote and post it to all the v3 authorities.
  2356. * (V3 Authority only) */
  2357. static int
  2358. dirvote_perform_vote(void)
  2359. {
  2360. crypto_pk_t *key = get_my_v3_authority_signing_key();
  2361. authority_cert_t *cert = get_my_v3_authority_cert();
  2362. networkstatus_t *ns;
  2363. char *contents;
  2364. pending_vote_t *pending_vote;
  2365. time_t now = time(NULL);
  2366. int status;
  2367. const char *msg = "";
  2368. if (!cert || !key) {
  2369. log_warn(LD_NET, "Didn't find key/certificate to generate v3 vote");
  2370. return -1;
  2371. } else if (cert->expires < now) {
  2372. log_warn(LD_NET, "Can't generate v3 vote with expired certificate");
  2373. return -1;
  2374. }
  2375. if (!(ns = dirserv_generate_networkstatus_vote_obj(key, cert)))
  2376. return -1;
  2377. contents = format_networkstatus_vote(key, ns);
  2378. networkstatus_vote_free(ns);
  2379. if (!contents)
  2380. return -1;
  2381. pending_vote = dirvote_add_vote(contents, &msg, &status);
  2382. tor_free(contents);
  2383. if (!pending_vote) {
  2384. log_warn(LD_DIR, "Couldn't store my own vote! (I told myself, '%s'.)",
  2385. msg);
  2386. return -1;
  2387. }
  2388. directory_post_to_dirservers(DIR_PURPOSE_UPLOAD_VOTE,
  2389. ROUTER_PURPOSE_GENERAL,
  2390. V3_DIRINFO,
  2391. pending_vote->vote_body->dir,
  2392. pending_vote->vote_body->dir_len, 0);
  2393. log_notice(LD_DIR, "Vote posted.");
  2394. return 0;
  2395. }
  2396. /** Send an HTTP request to every other v3 authority, for the votes of every
  2397. * authority for which we haven't received a vote yet in this period. (V3
  2398. * authority only) */
  2399. static void
  2400. dirvote_fetch_missing_votes(void)
  2401. {
  2402. smartlist_t *missing_fps = smartlist_new();
  2403. char *resource;
  2404. SMARTLIST_FOREACH_BEGIN(router_get_trusted_dir_servers(),
  2405. dir_server_t *, ds) {
  2406. if (!(ds->type & V3_DIRINFO))
  2407. continue;
  2408. if (!dirvote_get_vote(ds->v3_identity_digest,
  2409. DGV_BY_ID|DGV_INCLUDE_PENDING)) {
  2410. char *cp = tor_malloc(HEX_DIGEST_LEN+1);
  2411. base16_encode(cp, HEX_DIGEST_LEN+1, ds->v3_identity_digest,
  2412. DIGEST_LEN);
  2413. smartlist_add(missing_fps, cp);
  2414. }
  2415. } SMARTLIST_FOREACH_END(ds);
  2416. if (!smartlist_len(missing_fps)) {
  2417. smartlist_free(missing_fps);
  2418. return;
  2419. }
  2420. {
  2421. char *tmp = smartlist_join_strings(missing_fps, " ", 0, NULL);
  2422. log_notice(LOG_NOTICE, "We're missing votes from %d authorities (%s). "
  2423. "Asking every other authority for a copy.",
  2424. smartlist_len(missing_fps), tmp);
  2425. tor_free(tmp);
  2426. }
  2427. resource = smartlist_join_strings(missing_fps, "+", 0, NULL);
  2428. directory_get_from_all_authorities(DIR_PURPOSE_FETCH_STATUS_VOTE,
  2429. 0, resource);
  2430. tor_free(resource);
  2431. SMARTLIST_FOREACH(missing_fps, char *, cp, tor_free(cp));
  2432. smartlist_free(missing_fps);
  2433. }
  2434. /** Send a request to every other authority for its detached signatures,
  2435. * unless we have signatures from all other v3 authorities already. */
  2436. static void
  2437. dirvote_fetch_missing_signatures(void)
  2438. {
  2439. int need_any = 0;
  2440. int i;
  2441. for (i=0; i < N_CONSENSUS_FLAVORS; ++i) {
  2442. networkstatus_t *consensus = pending_consensuses[i].consensus;
  2443. if (!consensus ||
  2444. networkstatus_check_consensus_signature(consensus, -1) == 1) {
  2445. /* We have no consensus, or we have one that's signed by everybody. */
  2446. continue;
  2447. }
  2448. need_any = 1;
  2449. }
  2450. if (!need_any)
  2451. return;
  2452. directory_get_from_all_authorities(DIR_PURPOSE_FETCH_DETACHED_SIGNATURES,
  2453. 0, NULL);
  2454. }
  2455. /** Release all storage held by pending consensuses (those waiting for
  2456. * signatures). */
  2457. static void
  2458. dirvote_clear_pending_consensuses(void)
  2459. {
  2460. int i;
  2461. for (i = 0; i < N_CONSENSUS_FLAVORS; ++i) {
  2462. pending_consensus_t *pc = &pending_consensuses[i];
  2463. tor_free(pc->body);
  2464. networkstatus_vote_free(pc->consensus);
  2465. pc->consensus = NULL;
  2466. }
  2467. }
  2468. /** Drop all currently pending votes, consensus, and detached signatures. */
  2469. static void
  2470. dirvote_clear_votes(int all_votes)
  2471. {
  2472. if (!previous_vote_list)
  2473. previous_vote_list = smartlist_new();
  2474. if (!pending_vote_list)
  2475. pending_vote_list = smartlist_new();
  2476. /* All "previous" votes are now junk. */
  2477. SMARTLIST_FOREACH(previous_vote_list, pending_vote_t *, v, {
  2478. cached_dir_decref(v->vote_body);
  2479. v->vote_body = NULL;
  2480. networkstatus_vote_free(v->vote);
  2481. tor_free(v);
  2482. });
  2483. smartlist_clear(previous_vote_list);
  2484. if (all_votes) {
  2485. /* If we're dumping all the votes, we delete the pending ones. */
  2486. SMARTLIST_FOREACH(pending_vote_list, pending_vote_t *, v, {
  2487. cached_dir_decref(v->vote_body);
  2488. v->vote_body = NULL;
  2489. networkstatus_vote_free(v->vote);
  2490. tor_free(v);
  2491. });
  2492. } else {
  2493. /* Otherwise, we move them into "previous". */
  2494. smartlist_add_all(previous_vote_list, pending_vote_list);
  2495. }
  2496. smartlist_clear(pending_vote_list);
  2497. if (pending_consensus_signature_list) {
  2498. SMARTLIST_FOREACH(pending_consensus_signature_list, char *, cp,
  2499. tor_free(cp));
  2500. smartlist_clear(pending_consensus_signature_list);
  2501. }
  2502. tor_free(pending_consensus_signatures);
  2503. dirvote_clear_pending_consensuses();
  2504. }
  2505. /** Return a newly allocated string containing the hex-encoded v3 authority
  2506. identity digest of every recognized v3 authority. */
  2507. static char *
  2508. list_v3_auth_ids(void)
  2509. {
  2510. smartlist_t *known_v3_keys = smartlist_new();
  2511. char *keys;
  2512. SMARTLIST_FOREACH(router_get_trusted_dir_servers(),
  2513. dir_server_t *, ds,
  2514. if ((ds->type & V3_DIRINFO) &&
  2515. !tor_digest_is_zero(ds->v3_identity_digest))
  2516. smartlist_add(known_v3_keys,
  2517. tor_strdup(hex_str(ds->v3_identity_digest, DIGEST_LEN))));
  2518. keys = smartlist_join_strings(known_v3_keys, ", ", 0, NULL);
  2519. SMARTLIST_FOREACH(known_v3_keys, char *, cp, tor_free(cp));
  2520. smartlist_free(known_v3_keys);
  2521. return keys;
  2522. }
  2523. /** Called when we have received a networkstatus vote in <b>vote_body</b>.
  2524. * Parse and validate it, and on success store it as a pending vote (which we
  2525. * then return). Return NULL on failure. Sets *<b>msg_out</b> and
  2526. * *<b>status_out</b> to an HTTP response and status code. (V3 authority
  2527. * only) */
  2528. pending_vote_t *
  2529. dirvote_add_vote(const char *vote_body, const char **msg_out, int *status_out)
  2530. {
  2531. networkstatus_t *vote;
  2532. networkstatus_voter_info_t *vi;
  2533. dir_server_t *ds;
  2534. pending_vote_t *pending_vote = NULL;
  2535. const char *end_of_vote = NULL;
  2536. int any_failed = 0;
  2537. tor_assert(vote_body);
  2538. tor_assert(msg_out);
  2539. tor_assert(status_out);
  2540. if (!pending_vote_list)
  2541. pending_vote_list = smartlist_new();
  2542. *status_out = 0;
  2543. *msg_out = NULL;
  2544. again:
  2545. vote = networkstatus_parse_vote_from_string(vote_body, &end_of_vote,
  2546. NS_TYPE_VOTE);
  2547. if (!end_of_vote)
  2548. end_of_vote = vote_body + strlen(vote_body);
  2549. if (!vote) {
  2550. log_warn(LD_DIR, "Couldn't parse vote: length was %d",
  2551. (int)strlen(vote_body));
  2552. *msg_out = "Unable to parse vote";
  2553. goto err;
  2554. }
  2555. tor_assert(smartlist_len(vote->voters) == 1);
  2556. vi = get_voter(vote);
  2557. {
  2558. int any_sig_good = 0;
  2559. SMARTLIST_FOREACH(vi->sigs, document_signature_t *, sig,
  2560. if (sig->good_signature)
  2561. any_sig_good = 1);
  2562. tor_assert(any_sig_good);
  2563. }
  2564. ds = trusteddirserver_get_by_v3_auth_digest(vi->identity_digest);
  2565. if (!ds) {
  2566. char *keys = list_v3_auth_ids();
  2567. log_warn(LD_DIR, "Got a vote from an authority (nickname %s, address %s) "
  2568. "with authority key ID %s. "
  2569. "This key ID is not recognized. Known v3 key IDs are: %s",
  2570. vi->nickname, vi->address,
  2571. hex_str(vi->identity_digest, DIGEST_LEN), keys);
  2572. tor_free(keys);
  2573. *msg_out = "Vote not from a recognized v3 authority";
  2574. goto err;
  2575. }
  2576. tor_assert(vote->cert);
  2577. if (!authority_cert_get_by_digests(vote->cert->cache_info.identity_digest,
  2578. vote->cert->signing_key_digest)) {
  2579. /* Hey, it's a new cert! */
  2580. trusted_dirs_load_certs_from_string(
  2581. vote->cert->cache_info.signed_descriptor_body,
  2582. TRUSTED_DIRS_CERTS_SRC_FROM_VOTE, 1 /*flush*/);
  2583. if (!authority_cert_get_by_digests(vote->cert->cache_info.identity_digest,
  2584. vote->cert->signing_key_digest)) {
  2585. log_warn(LD_BUG, "We added a cert, but still couldn't find it.");
  2586. }
  2587. }
  2588. /* Is it for the right period? */
  2589. if (vote->valid_after != voting_schedule.interval_starts) {
  2590. char tbuf1[ISO_TIME_LEN+1], tbuf2[ISO_TIME_LEN+1];
  2591. format_iso_time(tbuf1, vote->valid_after);
  2592. format_iso_time(tbuf2, voting_schedule.interval_starts);
  2593. log_warn(LD_DIR, "Rejecting vote from %s with valid-after time of %s; "
  2594. "we were expecting %s", vi->address, tbuf1, tbuf2);
  2595. *msg_out = "Bad valid-after time";
  2596. goto err;
  2597. }
  2598. /* Fetch any new router descriptors we just learned about */
  2599. update_consensus_router_descriptor_downloads(time(NULL), 1, vote);
  2600. /* Now see whether we already have a vote from this authority. */
  2601. SMARTLIST_FOREACH_BEGIN(pending_vote_list, pending_vote_t *, v) {
  2602. if (fast_memeq(v->vote->cert->cache_info.identity_digest,
  2603. vote->cert->cache_info.identity_digest,
  2604. DIGEST_LEN)) {
  2605. networkstatus_voter_info_t *vi_old = get_voter(v->vote);
  2606. if (fast_memeq(vi_old->vote_digest, vi->vote_digest, DIGEST_LEN)) {
  2607. /* Ah, it's the same vote. Not a problem. */
  2608. log_info(LD_DIR, "Discarding a vote we already have (from %s).",
  2609. vi->address);
  2610. if (*status_out < 200)
  2611. *status_out = 200;
  2612. goto discard;
  2613. } else if (v->vote->published < vote->published) {
  2614. log_notice(LD_DIR, "Replacing an older pending vote from this "
  2615. "directory (%s)", vi->address);
  2616. cached_dir_decref(v->vote_body);
  2617. networkstatus_vote_free(v->vote);
  2618. v->vote_body = new_cached_dir(tor_strndup(vote_body,
  2619. end_of_vote-vote_body),
  2620. vote->published);
  2621. v->vote = vote;
  2622. if (end_of_vote &&
  2623. !strcmpstart(end_of_vote, "network-status-version"))
  2624. goto again;
  2625. if (*status_out < 200)
  2626. *status_out = 200;
  2627. if (!*msg_out)
  2628. *msg_out = "OK";
  2629. return v;
  2630. } else {
  2631. *msg_out = "Already have a newer pending vote";
  2632. goto err;
  2633. }
  2634. }
  2635. } SMARTLIST_FOREACH_END(v);
  2636. pending_vote = tor_malloc_zero(sizeof(pending_vote_t));
  2637. pending_vote->vote_body = new_cached_dir(tor_strndup(vote_body,
  2638. end_of_vote-vote_body),
  2639. vote->published);
  2640. pending_vote->vote = vote;
  2641. smartlist_add(pending_vote_list, pending_vote);
  2642. if (!strcmpstart(end_of_vote, "network-status-version ")) {
  2643. vote_body = end_of_vote;
  2644. goto again;
  2645. }
  2646. goto done;
  2647. err:
  2648. any_failed = 1;
  2649. if (!*msg_out)
  2650. *msg_out = "Error adding vote";
  2651. if (*status_out < 400)
  2652. *status_out = 400;
  2653. discard:
  2654. networkstatus_vote_free(vote);
  2655. if (end_of_vote && !strcmpstart(end_of_vote, "network-status-version ")) {
  2656. vote_body = end_of_vote;
  2657. goto again;
  2658. }
  2659. done:
  2660. if (*status_out < 200)
  2661. *status_out = 200;
  2662. if (!*msg_out) {
  2663. if (!any_failed && !pending_vote) {
  2664. *msg_out = "Duplicate discarded";
  2665. } else {
  2666. *msg_out = "ok";
  2667. }
  2668. }
  2669. return any_failed ? NULL : pending_vote;
  2670. }
  2671. /** Try to compute a v3 networkstatus consensus from the currently pending
  2672. * votes. Return 0 on success, -1 on failure. Store the consensus in
  2673. * pending_consensus: it won't be ready to be published until we have
  2674. * everybody else's signatures collected too. (V3 Authority only) */
  2675. static int
  2676. dirvote_compute_consensuses(void)
  2677. {
  2678. /* Have we got enough votes to try? */
  2679. int n_votes, n_voters, n_vote_running = 0;
  2680. smartlist_t *votes = NULL, *votestrings = NULL;
  2681. char *consensus_body = NULL, *signatures = NULL, *votefile;
  2682. networkstatus_t *consensus = NULL;
  2683. authority_cert_t *my_cert;
  2684. pending_consensus_t pending[N_CONSENSUS_FLAVORS];
  2685. int flav;
  2686. memset(pending, 0, sizeof(pending));
  2687. if (!pending_vote_list)
  2688. pending_vote_list = smartlist_new();
  2689. n_voters = get_n_authorities(V3_DIRINFO);
  2690. n_votes = smartlist_len(pending_vote_list);
  2691. if (n_votes <= n_voters/2) {
  2692. log_warn(LD_DIR, "We don't have enough votes to generate a consensus: "
  2693. "%d of %d", n_votes, n_voters/2+1);
  2694. goto err;
  2695. }
  2696. tor_assert(pending_vote_list);
  2697. SMARTLIST_FOREACH(pending_vote_list, pending_vote_t *, v, {
  2698. if (smartlist_contains_string(v->vote->known_flags, "Running"))
  2699. n_vote_running++;
  2700. });
  2701. if (!n_vote_running) {
  2702. /* See task 1066. */
  2703. log_warn(LD_DIR, "Nobody has voted on the Running flag. Generating "
  2704. "and publishing a consensus without Running nodes "
  2705. "would make many clients stop working. Not "
  2706. "generating a consensus!");
  2707. goto err;
  2708. }
  2709. if (!(my_cert = get_my_v3_authority_cert())) {
  2710. log_warn(LD_DIR, "Can't generate consensus without a certificate.");
  2711. goto err;
  2712. }
  2713. votes = smartlist_new();
  2714. votestrings = smartlist_new();
  2715. SMARTLIST_FOREACH(pending_vote_list, pending_vote_t *, v,
  2716. {
  2717. sized_chunk_t *c = tor_malloc(sizeof(sized_chunk_t));
  2718. c->bytes = v->vote_body->dir;
  2719. c->len = v->vote_body->dir_len;
  2720. smartlist_add(votestrings, c); /* collect strings to write to disk */
  2721. smartlist_add(votes, v->vote); /* collect votes to compute consensus */
  2722. });
  2723. votefile = get_datadir_fname("v3-status-votes");
  2724. write_chunks_to_file(votefile, votestrings, 0, 0);
  2725. tor_free(votefile);
  2726. SMARTLIST_FOREACH(votestrings, sized_chunk_t *, c, tor_free(c));
  2727. smartlist_free(votestrings);
  2728. {
  2729. char legacy_dbuf[DIGEST_LEN];
  2730. crypto_pk_t *legacy_sign=NULL;
  2731. char *legacy_id_digest = NULL;
  2732. int n_generated = 0;
  2733. if (get_options()->V3AuthUseLegacyKey) {
  2734. authority_cert_t *cert = get_my_v3_legacy_cert();
  2735. legacy_sign = get_my_v3_legacy_signing_key();
  2736. if (cert) {
  2737. if (crypto_pk_get_digest(cert->identity_key, legacy_dbuf)) {
  2738. log_warn(LD_BUG,
  2739. "Unable to compute digest of legacy v3 identity key");
  2740. } else {
  2741. legacy_id_digest = legacy_dbuf;
  2742. }
  2743. }
  2744. }
  2745. for (flav = 0; flav < N_CONSENSUS_FLAVORS; ++flav) {
  2746. const char *flavor_name = networkstatus_get_flavor_name(flav);
  2747. consensus_body = networkstatus_compute_consensus(
  2748. votes, n_voters,
  2749. my_cert->identity_key,
  2750. get_my_v3_authority_signing_key(), legacy_id_digest, legacy_sign,
  2751. flav);
  2752. if (!consensus_body) {
  2753. log_warn(LD_DIR, "Couldn't generate a %s consensus at all!",
  2754. flavor_name);
  2755. continue;
  2756. }
  2757. consensus = networkstatus_parse_vote_from_string(consensus_body, NULL,
  2758. NS_TYPE_CONSENSUS);
  2759. if (!consensus) {
  2760. log_warn(LD_DIR, "Couldn't parse %s consensus we generated!",
  2761. flavor_name);
  2762. tor_free(consensus_body);
  2763. continue;
  2764. }
  2765. /* 'Check' our own signature, to mark it valid. */
  2766. networkstatus_check_consensus_signature(consensus, -1);
  2767. pending[flav].body = consensus_body;
  2768. pending[flav].consensus = consensus;
  2769. n_generated++;
  2770. consensus_body = NULL;
  2771. consensus = NULL;
  2772. }
  2773. if (!n_generated) {
  2774. log_warn(LD_DIR, "Couldn't generate any consensus flavors at all.");
  2775. goto err;
  2776. }
  2777. }
  2778. signatures = get_detached_signatures_from_pending_consensuses(
  2779. pending, N_CONSENSUS_FLAVORS);
  2780. if (!signatures) {
  2781. log_warn(LD_DIR, "Couldn't extract signatures.");
  2782. goto err;
  2783. }
  2784. dirvote_clear_pending_consensuses();
  2785. memcpy(pending_consensuses, pending, sizeof(pending));
  2786. tor_free(pending_consensus_signatures);
  2787. pending_consensus_signatures = signatures;
  2788. if (pending_consensus_signature_list) {
  2789. int n_sigs = 0;
  2790. /* we may have gotten signatures for this consensus before we built
  2791. * it ourself. Add them now. */
  2792. SMARTLIST_FOREACH_BEGIN(pending_consensus_signature_list, char *, sig) {
  2793. const char *msg = NULL;
  2794. int r = dirvote_add_signatures_to_all_pending_consensuses(sig,
  2795. "pending", &msg);
  2796. if (r >= 0)
  2797. n_sigs += r;
  2798. else
  2799. log_warn(LD_DIR,
  2800. "Could not add queued signature to new consensus: %s",
  2801. msg);
  2802. tor_free(sig);
  2803. } SMARTLIST_FOREACH_END(sig);
  2804. if (n_sigs)
  2805. log_notice(LD_DIR, "Added %d pending signatures while building "
  2806. "consensus.", n_sigs);
  2807. smartlist_clear(pending_consensus_signature_list);
  2808. }
  2809. log_notice(LD_DIR, "Consensus computed; uploading signature(s)");
  2810. directory_post_to_dirservers(DIR_PURPOSE_UPLOAD_SIGNATURES,
  2811. ROUTER_PURPOSE_GENERAL,
  2812. V3_DIRINFO,
  2813. pending_consensus_signatures,
  2814. strlen(pending_consensus_signatures), 0);
  2815. log_notice(LD_DIR, "Signature(s) posted.");
  2816. smartlist_free(votes);
  2817. return 0;
  2818. err:
  2819. smartlist_free(votes);
  2820. tor_free(consensus_body);
  2821. tor_free(signatures);
  2822. networkstatus_vote_free(consensus);
  2823. return -1;
  2824. }
  2825. /** Helper: we just got the <b>detached_signatures_body</b> sent to us as
  2826. * signatures on the currently pending consensus. Add them to <b>pc</b>
  2827. * as appropriate. Return the number of signatures added. (?) */
  2828. static int
  2829. dirvote_add_signatures_to_pending_consensus(
  2830. pending_consensus_t *pc,
  2831. ns_detached_signatures_t *sigs,
  2832. const char *source,
  2833. int severity,
  2834. const char **msg_out)
  2835. {
  2836. const char *flavor_name;
  2837. int r = -1;
  2838. /* Only call if we have a pending consensus right now. */
  2839. tor_assert(pc->consensus);
  2840. tor_assert(pc->body);
  2841. tor_assert(pending_consensus_signatures);
  2842. flavor_name = networkstatus_get_flavor_name(pc->consensus->flavor);
  2843. *msg_out = NULL;
  2844. {
  2845. smartlist_t *sig_list = strmap_get(sigs->signatures, flavor_name);
  2846. log_info(LD_DIR, "Have %d signatures for adding to %s consensus.",
  2847. sig_list ? smartlist_len(sig_list) : 0, flavor_name);
  2848. }
  2849. r = networkstatus_add_detached_signatures(pc->consensus, sigs,
  2850. source, severity, msg_out);
  2851. log_info(LD_DIR,"Added %d signatures to consensus.", r);
  2852. if (r >= 1) {
  2853. char *new_signatures =
  2854. networkstatus_format_signatures(pc->consensus, 0);
  2855. char *dst, *dst_end;
  2856. size_t new_consensus_len;
  2857. if (!new_signatures) {
  2858. *msg_out = "No signatures to add";
  2859. goto err;
  2860. }
  2861. new_consensus_len =
  2862. strlen(pc->body) + strlen(new_signatures) + 1;
  2863. pc->body = tor_realloc(pc->body, new_consensus_len);
  2864. dst_end = pc->body + new_consensus_len;
  2865. dst = strstr(pc->body, "directory-signature ");
  2866. tor_assert(dst);
  2867. strlcpy(dst, new_signatures, dst_end-dst);
  2868. /* We remove this block once it has failed to crash for a while. But
  2869. * unless it shows up in profiles, we're probably better leaving it in,
  2870. * just in case we break detached signature processing at some point. */
  2871. {
  2872. networkstatus_t *v = networkstatus_parse_vote_from_string(
  2873. pc->body, NULL,
  2874. NS_TYPE_CONSENSUS);
  2875. tor_assert(v);
  2876. networkstatus_vote_free(v);
  2877. }
  2878. *msg_out = "Signatures added";
  2879. tor_free(new_signatures);
  2880. } else if (r == 0) {
  2881. *msg_out = "Signatures ignored";
  2882. } else {
  2883. goto err;
  2884. }
  2885. goto done;
  2886. err:
  2887. if (!*msg_out)
  2888. *msg_out = "Unrecognized error while adding detached signatures.";
  2889. done:
  2890. return r;
  2891. }
  2892. static int
  2893. dirvote_add_signatures_to_all_pending_consensuses(
  2894. const char *detached_signatures_body,
  2895. const char *source,
  2896. const char **msg_out)
  2897. {
  2898. int r=0, i, n_added = 0, errors = 0;
  2899. ns_detached_signatures_t *sigs;
  2900. tor_assert(detached_signatures_body);
  2901. tor_assert(msg_out);
  2902. tor_assert(pending_consensus_signatures);
  2903. if (!(sigs = networkstatus_parse_detached_signatures(
  2904. detached_signatures_body, NULL))) {
  2905. *msg_out = "Couldn't parse detached signatures.";
  2906. goto err;
  2907. }
  2908. for (i = 0; i < N_CONSENSUS_FLAVORS; ++i) {
  2909. int res;
  2910. int severity = i == FLAV_NS ? LOG_NOTICE : LOG_INFO;
  2911. pending_consensus_t *pc = &pending_consensuses[i];
  2912. if (!pc->consensus)
  2913. continue;
  2914. res = dirvote_add_signatures_to_pending_consensus(pc, sigs, source,
  2915. severity, msg_out);
  2916. if (res < 0)
  2917. errors++;
  2918. else
  2919. n_added += res;
  2920. }
  2921. if (errors && !n_added) {
  2922. r = -1;
  2923. goto err;
  2924. }
  2925. if (n_added && pending_consensuses[FLAV_NS].consensus) {
  2926. char *new_detached =
  2927. get_detached_signatures_from_pending_consensuses(
  2928. pending_consensuses, N_CONSENSUS_FLAVORS);
  2929. if (new_detached) {
  2930. tor_free(pending_consensus_signatures);
  2931. pending_consensus_signatures = new_detached;
  2932. }
  2933. }
  2934. r = n_added;
  2935. goto done;
  2936. err:
  2937. if (!*msg_out)
  2938. *msg_out = "Unrecognized error while adding detached signatures.";
  2939. done:
  2940. ns_detached_signatures_free(sigs);
  2941. /* XXXX NM Check how return is used. We can now have an error *and*
  2942. signatures added. */
  2943. return r;
  2944. }
  2945. /** Helper: we just got the <b>detached_signatures_body</b> sent to us as
  2946. * signatures on the currently pending consensus. Add them to the pending
  2947. * consensus (if we have one); otherwise queue them until we have a
  2948. * consensus. Return negative on failure, nonnegative on success. */
  2949. int
  2950. dirvote_add_signatures(const char *detached_signatures_body,
  2951. const char *source,
  2952. const char **msg)
  2953. {
  2954. if (pending_consensuses[FLAV_NS].consensus) {
  2955. log_notice(LD_DIR, "Got a signature from %s. "
  2956. "Adding it to the pending consensus.", source);
  2957. return dirvote_add_signatures_to_all_pending_consensuses(
  2958. detached_signatures_body, source, msg);
  2959. } else {
  2960. log_notice(LD_DIR, "Got a signature from %s. "
  2961. "Queuing it for the next consensus.", source);
  2962. if (!pending_consensus_signature_list)
  2963. pending_consensus_signature_list = smartlist_new();
  2964. smartlist_add(pending_consensus_signature_list,
  2965. tor_strdup(detached_signatures_body));
  2966. *msg = "Signature queued";
  2967. return 0;
  2968. }
  2969. }
  2970. /** Replace the consensus that we're currently serving with the one that we've
  2971. * been building. (V3 Authority only) */
  2972. static int
  2973. dirvote_publish_consensus(void)
  2974. {
  2975. int i;
  2976. /* Now remember all the other consensuses as if we were a directory cache. */
  2977. for (i = 0; i < N_CONSENSUS_FLAVORS; ++i) {
  2978. pending_consensus_t *pending = &pending_consensuses[i];
  2979. const char *name;
  2980. name = networkstatus_get_flavor_name(i);
  2981. tor_assert(name);
  2982. if (!pending->consensus ||
  2983. networkstatus_check_consensus_signature(pending->consensus, 1)<0) {
  2984. log_warn(LD_DIR, "Not enough info to publish pending %s consensus",name);
  2985. continue;
  2986. }
  2987. if (networkstatus_set_current_consensus(pending->body, name, 0))
  2988. log_warn(LD_DIR, "Error publishing %s consensus", name);
  2989. else
  2990. log_notice(LD_DIR, "Published %s consensus", name);
  2991. }
  2992. return 0;
  2993. }
  2994. /** Release all static storage held in dirvote.c */
  2995. void
  2996. dirvote_free_all(void)
  2997. {
  2998. dirvote_clear_votes(1);
  2999. /* now empty as a result of dirvote_clear_votes(). */
  3000. smartlist_free(pending_vote_list);
  3001. pending_vote_list = NULL;
  3002. smartlist_free(previous_vote_list);
  3003. previous_vote_list = NULL;
  3004. dirvote_clear_pending_consensuses();
  3005. tor_free(pending_consensus_signatures);
  3006. if (pending_consensus_signature_list) {
  3007. /* now empty as a result of dirvote_clear_votes(). */
  3008. smartlist_free(pending_consensus_signature_list);
  3009. pending_consensus_signature_list = NULL;
  3010. }
  3011. }
  3012. /* ====
  3013. * Access to pending items.
  3014. * ==== */
  3015. /** Return the body of the consensus that we're currently trying to build. */
  3016. const char *
  3017. dirvote_get_pending_consensus(consensus_flavor_t flav)
  3018. {
  3019. tor_assert(((int)flav) >= 0 && (int)flav < N_CONSENSUS_FLAVORS);
  3020. return pending_consensuses[flav].body;
  3021. }
  3022. /** Return the signatures that we know for the consensus that we're currently
  3023. * trying to build. */
  3024. const char *
  3025. dirvote_get_pending_detached_signatures(void)
  3026. {
  3027. return pending_consensus_signatures;
  3028. }
  3029. /** Return a given vote specified by <b>fp</b>. If <b>by_id</b>, return the
  3030. * vote for the authority with the v3 authority identity key digest <b>fp</b>;
  3031. * if <b>by_id</b> is false, return the vote whose digest is <b>fp</b>. If
  3032. * <b>fp</b> is NULL, return our own vote. If <b>include_previous</b> is
  3033. * false, do not consider any votes for a consensus that's already been built.
  3034. * If <b>include_pending</b> is false, do not consider any votes for the
  3035. * consensus that's in progress. May return NULL if we have no vote for the
  3036. * authority in question. */
  3037. const cached_dir_t *
  3038. dirvote_get_vote(const char *fp, int flags)
  3039. {
  3040. int by_id = flags & DGV_BY_ID;
  3041. const int include_pending = flags & DGV_INCLUDE_PENDING;
  3042. const int include_previous = flags & DGV_INCLUDE_PREVIOUS;
  3043. if (!pending_vote_list && !previous_vote_list)
  3044. return NULL;
  3045. if (fp == NULL) {
  3046. authority_cert_t *c = get_my_v3_authority_cert();
  3047. if (c) {
  3048. fp = c->cache_info.identity_digest;
  3049. by_id = 1;
  3050. } else
  3051. return NULL;
  3052. }
  3053. if (by_id) {
  3054. if (pending_vote_list && include_pending) {
  3055. SMARTLIST_FOREACH(pending_vote_list, pending_vote_t *, pv,
  3056. if (fast_memeq(get_voter(pv->vote)->identity_digest, fp, DIGEST_LEN))
  3057. return pv->vote_body);
  3058. }
  3059. if (previous_vote_list && include_previous) {
  3060. SMARTLIST_FOREACH(previous_vote_list, pending_vote_t *, pv,
  3061. if (fast_memeq(get_voter(pv->vote)->identity_digest, fp, DIGEST_LEN))
  3062. return pv->vote_body);
  3063. }
  3064. } else {
  3065. if (pending_vote_list && include_pending) {
  3066. SMARTLIST_FOREACH(pending_vote_list, pending_vote_t *, pv,
  3067. if (fast_memeq(pv->vote->digests.d[DIGEST_SHA1], fp, DIGEST_LEN))
  3068. return pv->vote_body);
  3069. }
  3070. if (previous_vote_list && include_previous) {
  3071. SMARTLIST_FOREACH(previous_vote_list, pending_vote_t *, pv,
  3072. if (fast_memeq(pv->vote->digests.d[DIGEST_SHA1], fp, DIGEST_LEN))
  3073. return pv->vote_body);
  3074. }
  3075. }
  3076. return NULL;
  3077. }
  3078. /** Construct and return a new microdescriptor from a routerinfo <b>ri</b>
  3079. * according to <b>consensus_method</b>.
  3080. **/
  3081. microdesc_t *
  3082. dirvote_create_microdescriptor(const routerinfo_t *ri, int consensus_method)
  3083. {
  3084. microdesc_t *result = NULL;
  3085. char *key = NULL, *summary = NULL, *family = NULL;
  3086. size_t keylen;
  3087. smartlist_t *chunks = smartlist_new();
  3088. char *output = NULL;
  3089. if (crypto_pk_write_public_key_to_string(ri->onion_pkey, &key, &keylen)<0)
  3090. goto done;
  3091. summary = policy_summarize(ri->exit_policy, AF_INET);
  3092. if (ri->declared_family)
  3093. family = smartlist_join_strings(ri->declared_family, " ", 0, NULL);
  3094. smartlist_add_asprintf(chunks, "onion-key\n%s", key);
  3095. if (consensus_method >= MIN_METHOD_FOR_NTOR_KEY &&
  3096. ri->onion_curve25519_pkey) {
  3097. char kbuf[128];
  3098. base64_encode(kbuf, sizeof(kbuf),
  3099. (const char*)ri->onion_curve25519_pkey->public_key,
  3100. CURVE25519_PUBKEY_LEN, BASE64_ENCODE_MULTILINE);
  3101. smartlist_add_asprintf(chunks, "ntor-onion-key %s", kbuf);
  3102. }
  3103. if (consensus_method >= MIN_METHOD_FOR_A_LINES &&
  3104. !tor_addr_is_null(&ri->ipv6_addr) && ri->ipv6_orport)
  3105. smartlist_add_asprintf(chunks, "a %s\n",
  3106. fmt_addrport(&ri->ipv6_addr, ri->ipv6_orport));
  3107. if (family)
  3108. smartlist_add_asprintf(chunks, "family %s\n", family);
  3109. if (summary && strcmp(summary, "reject 1-65535"))
  3110. smartlist_add_asprintf(chunks, "p %s\n", summary);
  3111. if (consensus_method >= MIN_METHOD_FOR_P6_LINES &&
  3112. ri->ipv6_exit_policy) {
  3113. /* XXXX024 This doesn't match proposal 208, which says these should
  3114. * be taken unchanged from the routerinfo. That's bogosity, IMO:
  3115. * the proposal should have said to do this instead.*/
  3116. char *p6 = write_short_policy(ri->ipv6_exit_policy);
  3117. if (p6 && strcmp(p6, "reject 1-65535"))
  3118. smartlist_add_asprintf(chunks, "p6 %s\n", p6);
  3119. tor_free(p6);
  3120. }
  3121. if (consensus_method >= MIN_METHOD_FOR_ID_HASH_IN_MD) {
  3122. char idbuf[ED25519_BASE64_LEN+1];
  3123. const char *keytype;
  3124. if (consensus_method >= MIN_METHOD_FOR_ED25519_ID_IN_MD &&
  3125. ri->signing_key_cert &&
  3126. ri->signing_key_cert->signing_key_included) {
  3127. keytype = "ed25519";
  3128. ed25519_public_to_base64(idbuf, &ri->signing_key_cert->signing_key);
  3129. } else {
  3130. keytype = "rsa1024";
  3131. digest_to_base64(idbuf, ri->cache_info.identity_digest);
  3132. }
  3133. smartlist_add_asprintf(chunks, "id %s %s\n", keytype, idbuf);
  3134. }
  3135. output = smartlist_join_strings(chunks, "", 0, NULL);
  3136. {
  3137. smartlist_t *lst = microdescs_parse_from_string(output,
  3138. output+strlen(output), 0,
  3139. SAVED_NOWHERE, NULL);
  3140. if (smartlist_len(lst) != 1) {
  3141. log_warn(LD_DIR, "We generated a microdescriptor we couldn't parse.");
  3142. SMARTLIST_FOREACH(lst, microdesc_t *, md, microdesc_free(md));
  3143. smartlist_free(lst);
  3144. goto done;
  3145. }
  3146. result = smartlist_get(lst, 0);
  3147. smartlist_free(lst);
  3148. }
  3149. done:
  3150. tor_free(output);
  3151. tor_free(key);
  3152. tor_free(summary);
  3153. tor_free(family);
  3154. if (chunks) {
  3155. SMARTLIST_FOREACH(chunks, char *, cp, tor_free(cp));
  3156. smartlist_free(chunks);
  3157. }
  3158. return result;
  3159. }
  3160. /** Format the appropriate vote line to describe the microdescriptor <b>md</b>
  3161. * in a consensus vote document. Write it into the <b>out_len</b>-byte buffer
  3162. * in <b>out</b>. Return -1 on failure and the number of characters written
  3163. * on success. */
  3164. ssize_t
  3165. dirvote_format_microdesc_vote_line(char *out_buf, size_t out_buf_len,
  3166. const microdesc_t *md,
  3167. int consensus_method_low,
  3168. int consensus_method_high)
  3169. {
  3170. ssize_t ret = -1;
  3171. char d64[BASE64_DIGEST256_LEN+1];
  3172. char *microdesc_consensus_methods =
  3173. make_consensus_method_list(consensus_method_low,
  3174. consensus_method_high,
  3175. ",");
  3176. tor_assert(microdesc_consensus_methods);
  3177. if (digest256_to_base64(d64, md->digest)<0)
  3178. goto out;
  3179. if (tor_snprintf(out_buf, out_buf_len, "m %s sha256=%s\n",
  3180. microdesc_consensus_methods, d64)<0)
  3181. goto out;
  3182. ret = strlen(out_buf);
  3183. out:
  3184. tor_free(microdesc_consensus_methods);
  3185. return ret;
  3186. }
  3187. /** Array of start and end of consensus methods used for supported
  3188. microdescriptor formats. */
  3189. static const struct consensus_method_range_t {
  3190. int low;
  3191. int high;
  3192. } microdesc_consensus_methods[] = {
  3193. {MIN_SUPPORTED_CONSENSUS_METHOD, MIN_METHOD_FOR_A_LINES - 1},
  3194. {MIN_METHOD_FOR_A_LINES, MIN_METHOD_FOR_P6_LINES - 1},
  3195. {MIN_METHOD_FOR_P6_LINES, MIN_METHOD_FOR_NTOR_KEY - 1},
  3196. {MIN_METHOD_FOR_NTOR_KEY, MIN_METHOD_FOR_ID_HASH_IN_MD - 1},
  3197. {MIN_METHOD_FOR_ID_HASH_IN_MD, MIN_METHOD_FOR_ED25519_ID_IN_MD - 1},
  3198. {MIN_METHOD_FOR_ED25519_ID_IN_MD, MAX_SUPPORTED_CONSENSUS_METHOD},
  3199. {-1, -1}
  3200. };
  3201. /** Helper type used when generating the microdescriptor lines in a directory
  3202. * vote. */
  3203. typedef struct microdesc_vote_line_t {
  3204. int low;
  3205. int high;
  3206. microdesc_t *md;
  3207. struct microdesc_vote_line_t *next;
  3208. } microdesc_vote_line_t;
  3209. /** Generate and return a linked list of all the lines that should appear to
  3210. * describe a router's microdescriptor versions in a directory vote.
  3211. * Add the generated microdescriptors to <b>microdescriptors_out</b>. */
  3212. vote_microdesc_hash_t *
  3213. dirvote_format_all_microdesc_vote_lines(const routerinfo_t *ri, time_t now,
  3214. smartlist_t *microdescriptors_out)
  3215. {
  3216. const struct consensus_method_range_t *cmr;
  3217. microdesc_vote_line_t *entries = NULL, *ep;
  3218. vote_microdesc_hash_t *result = NULL;
  3219. /* Generate the microdescriptors. */
  3220. for (cmr = microdesc_consensus_methods;
  3221. cmr->low != -1 && cmr->high != -1;
  3222. cmr++) {
  3223. microdesc_t *md = dirvote_create_microdescriptor(ri, cmr->low);
  3224. if (md) {
  3225. microdesc_vote_line_t *e =
  3226. tor_malloc_zero(sizeof(microdesc_vote_line_t));
  3227. e->md = md;
  3228. e->low = cmr->low;
  3229. e->high = cmr->high;
  3230. e->next = entries;
  3231. entries = e;
  3232. }
  3233. }
  3234. /* Compress adjacent identical ones */
  3235. for (ep = entries; ep; ep = ep->next) {
  3236. while (ep->next &&
  3237. fast_memeq(ep->md->digest, ep->next->md->digest, DIGEST256_LEN) &&
  3238. ep->low == ep->next->high + 1) {
  3239. microdesc_vote_line_t *next = ep->next;
  3240. ep->low = next->low;
  3241. microdesc_free(next->md);
  3242. ep->next = next->next;
  3243. tor_free(next);
  3244. }
  3245. }
  3246. /* Format them into vote_microdesc_hash_t, and add to microdescriptors_out.*/
  3247. while ((ep = entries)) {
  3248. char buf[128];
  3249. vote_microdesc_hash_t *h;
  3250. dirvote_format_microdesc_vote_line(buf, sizeof(buf), ep->md,
  3251. ep->low, ep->high);
  3252. h = tor_malloc_zero(sizeof(vote_microdesc_hash_t));
  3253. h->microdesc_hash_line = tor_strdup(buf);
  3254. h->next = result;
  3255. result = h;
  3256. ep->md->last_listed = now;
  3257. smartlist_add(microdescriptors_out, ep->md);
  3258. entries = ep->next;
  3259. tor_free(ep);
  3260. }
  3261. return result;
  3262. }
  3263. /** If <b>vrs</b> has a hash made for the consensus method <b>method</b> with
  3264. * the digest algorithm <b>alg</b>, decode it and copy it into
  3265. * <b>digest256_out</b> and return 0. Otherwise return -1. */
  3266. int
  3267. vote_routerstatus_find_microdesc_hash(char *digest256_out,
  3268. const vote_routerstatus_t *vrs,
  3269. int method,
  3270. digest_algorithm_t alg)
  3271. {
  3272. /* XXXX only returns the sha256 method. */
  3273. const vote_microdesc_hash_t *h;
  3274. char mstr[64];
  3275. size_t mlen;
  3276. char dstr[64];
  3277. tor_snprintf(mstr, sizeof(mstr), "%d", method);
  3278. mlen = strlen(mstr);
  3279. tor_snprintf(dstr, sizeof(dstr), " %s=",
  3280. crypto_digest_algorithm_get_name(alg));
  3281. for (h = vrs->microdesc; h; h = h->next) {
  3282. const char *cp = h->microdesc_hash_line;
  3283. size_t num_len;
  3284. /* cp looks like \d+(,\d+)* (digesttype=val )+ . Let's hunt for mstr in
  3285. * the first part. */
  3286. while (1) {
  3287. num_len = strspn(cp, "1234567890");
  3288. if (num_len == mlen && fast_memeq(mstr, cp, mlen)) {
  3289. /* This is the line. */
  3290. char buf[BASE64_DIGEST256_LEN+1];
  3291. /* XXXX ignores extraneous stuff if the digest is too long. This
  3292. * seems harmless enough, right? */
  3293. cp = strstr(cp, dstr);
  3294. if (!cp)
  3295. return -1;
  3296. cp += strlen(dstr);
  3297. strlcpy(buf, cp, sizeof(buf));
  3298. return digest256_from_base64(digest256_out, buf);
  3299. }
  3300. if (num_len == 0 || cp[num_len] != ',')
  3301. break;
  3302. cp += num_len + 1;
  3303. }
  3304. }
  3305. return -1;
  3306. }