dirvote.c 128 KB

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