routerlist.c 142 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844184518461847184818491850185118521853185418551856185718581859186018611862186318641865186618671868186918701871187218731874187518761877187818791880188118821883188418851886188718881889189018911892189318941895189618971898189919001901190219031904190519061907190819091910191119121913191419151916191719181919192019211922192319241925192619271928192919301931193219331934193519361937193819391940194119421943194419451946194719481949195019511952195319541955195619571958195919601961196219631964196519661967196819691970197119721973197419751976197719781979198019811982198319841985198619871988198919901991199219931994199519961997199819992000200120022003200420052006200720082009201020112012201320142015201620172018201920202021202220232024202520262027202820292030203120322033203420352036203720382039204020412042204320442045204620472048204920502051205220532054205520562057205820592060206120622063206420652066206720682069207020712072207320742075207620772078207920802081208220832084208520862087208820892090209120922093209420952096209720982099210021012102210321042105210621072108210921102111211221132114211521162117211821192120212121222123212421252126212721282129213021312132213321342135213621372138213921402141214221432144214521462147214821492150215121522153215421552156215721582159216021612162216321642165216621672168216921702171217221732174217521762177217821792180218121822183218421852186218721882189219021912192219321942195219621972198219922002201220222032204220522062207220822092210221122122213221422152216221722182219222022212222222322242225222622272228222922302231223222332234223522362237223822392240224122422243224422452246224722482249225022512252225322542255225622572258225922602261226222632264226522662267226822692270227122722273227422752276227722782279228022812282228322842285228622872288228922902291229222932294229522962297229822992300230123022303230423052306230723082309231023112312231323142315231623172318231923202321232223232324232523262327232823292330233123322333233423352336233723382339234023412342234323442345234623472348234923502351235223532354235523562357235823592360236123622363236423652366236723682369237023712372237323742375237623772378237923802381238223832384238523862387238823892390239123922393239423952396239723982399240024012402240324042405240624072408240924102411241224132414241524162417241824192420242124222423242424252426242724282429243024312432243324342435243624372438243924402441244224432444244524462447244824492450245124522453245424552456245724582459246024612462246324642465246624672468246924702471247224732474247524762477247824792480248124822483248424852486248724882489249024912492249324942495249624972498249925002501250225032504250525062507250825092510251125122513251425152516251725182519252025212522252325242525252625272528252925302531253225332534253525362537253825392540254125422543254425452546254725482549255025512552255325542555255625572558255925602561256225632564256525662567256825692570257125722573257425752576257725782579258025812582258325842585258625872588258925902591259225932594259525962597259825992600260126022603260426052606260726082609261026112612261326142615261626172618261926202621262226232624262526262627262826292630263126322633263426352636263726382639264026412642264326442645264626472648264926502651265226532654265526562657265826592660266126622663266426652666266726682669267026712672267326742675267626772678267926802681268226832684268526862687268826892690269126922693269426952696269726982699270027012702270327042705270627072708270927102711271227132714271527162717271827192720272127222723272427252726272727282729273027312732273327342735273627372738273927402741274227432744274527462747274827492750275127522753275427552756275727582759276027612762276327642765276627672768276927702771277227732774277527762777277827792780278127822783278427852786278727882789279027912792279327942795279627972798279928002801280228032804280528062807280828092810281128122813281428152816281728182819282028212822282328242825282628272828282928302831283228332834283528362837283828392840284128422843284428452846284728482849285028512852285328542855285628572858285928602861286228632864286528662867286828692870287128722873287428752876287728782879288028812882288328842885288628872888288928902891289228932894289528962897289828992900290129022903290429052906290729082909291029112912291329142915291629172918291929202921292229232924292529262927292829292930293129322933293429352936293729382939294029412942294329442945294629472948294929502951295229532954295529562957295829592960296129622963296429652966296729682969297029712972297329742975297629772978297929802981298229832984298529862987298829892990299129922993299429952996299729982999300030013002300330043005300630073008300930103011301230133014301530163017301830193020302130223023302430253026302730283029303030313032303330343035303630373038303930403041304230433044304530463047304830493050305130523053305430553056305730583059306030613062306330643065306630673068306930703071307230733074307530763077307830793080308130823083308430853086308730883089309030913092309330943095309630973098309931003101310231033104310531063107310831093110311131123113311431153116311731183119312031213122312331243125312631273128312931303131313231333134313531363137313831393140314131423143314431453146314731483149315031513152315331543155315631573158315931603161316231633164316531663167316831693170317131723173317431753176317731783179318031813182318331843185318631873188318931903191319231933194319531963197319831993200320132023203320432053206320732083209321032113212321332143215321632173218321932203221322232233224322532263227322832293230323132323233323432353236323732383239324032413242324332443245324632473248324932503251325232533254325532563257325832593260326132623263326432653266326732683269327032713272327332743275327632773278327932803281328232833284328532863287328832893290329132923293329432953296329732983299330033013302330333043305330633073308330933103311331233133314331533163317331833193320332133223323332433253326332733283329333033313332333333343335333633373338333933403341334233433344334533463347334833493350335133523353335433553356335733583359336033613362336333643365336633673368336933703371337233733374337533763377337833793380338133823383338433853386338733883389339033913392339333943395339633973398339934003401340234033404340534063407340834093410341134123413341434153416341734183419342034213422342334243425342634273428342934303431343234333434343534363437343834393440344134423443344434453446344734483449345034513452345334543455345634573458345934603461346234633464346534663467346834693470347134723473347434753476347734783479348034813482348334843485348634873488348934903491349234933494349534963497349834993500350135023503350435053506350735083509351035113512351335143515351635173518351935203521352235233524352535263527352835293530353135323533353435353536353735383539354035413542354335443545354635473548354935503551355235533554355535563557355835593560356135623563356435653566356735683569357035713572357335743575357635773578357935803581358235833584358535863587358835893590359135923593359435953596359735983599360036013602360336043605360636073608360936103611361236133614361536163617361836193620362136223623362436253626362736283629363036313632363336343635363636373638363936403641364236433644364536463647364836493650365136523653365436553656365736583659366036613662366336643665366636673668366936703671367236733674367536763677367836793680368136823683368436853686368736883689369036913692369336943695369636973698369937003701370237033704370537063707370837093710371137123713371437153716371737183719372037213722372337243725372637273728372937303731373237333734373537363737373837393740374137423743374437453746374737483749375037513752375337543755375637573758375937603761376237633764376537663767376837693770377137723773377437753776377737783779378037813782378337843785378637873788378937903791379237933794379537963797379837993800380138023803380438053806380738083809381038113812381338143815381638173818381938203821382238233824382538263827382838293830383138323833383438353836383738383839384038413842384338443845384638473848384938503851385238533854385538563857385838593860386138623863386438653866386738683869387038713872387338743875387638773878387938803881388238833884388538863887388838893890389138923893389438953896389738983899390039013902390339043905390639073908390939103911391239133914391539163917391839193920392139223923392439253926392739283929393039313932393339343935393639373938393939403941394239433944394539463947394839493950395139523953395439553956395739583959396039613962396339643965396639673968396939703971397239733974397539763977397839793980398139823983398439853986398739883989399039913992399339943995399639973998399940004001400240034004400540064007400840094010401140124013401440154016401740184019402040214022402340244025402640274028402940304031403240334034403540364037403840394040404140424043404440454046404740484049405040514052405340544055405640574058405940604061406240634064406540664067406840694070407140724073407440754076407740784079408040814082408340844085408640874088408940904091409240934094409540964097409840994100410141024103410441054106410741084109411041114112411341144115411641174118411941204121412241234124412541264127412841294130413141324133413441354136413741384139414041414142414341444145414641474148414941504151415241534154415541564157415841594160416141624163416441654166416741684169417041714172417341744175417641774178417941804181418241834184418541864187418841894190419141924193419441954196419741984199420042014202420342044205420642074208420942104211421242134214421542164217421842194220422142224223422442254226422742284229423042314232423342344235423642374238423942404241424242434244424542464247424842494250
  1. /* Copyright (c) 2001 Matej Pfajfar.
  2. * Copyright (c) 2001-2004, Roger Dingledine.
  3. * Copyright (c) 2004-2007, Roger Dingledine, Nick Mathewson. */
  4. /* See LICENSE for licensing information */
  5. /* $Id$ */
  6. const char routerlist_c_id[] =
  7. "$Id$";
  8. /**
  9. * \file routerlist.c
  10. * \brief Code to
  11. * maintain and access the global list of routerinfos for known
  12. * servers.
  13. **/
  14. #include "or.h"
  15. // #define DEBUG_ROUTERLIST
  16. /****************************************************************************/
  17. /* static function prototypes */
  18. static routerstatus_t *router_pick_directory_server_impl(int requireother,
  19. int fascistfirewall,
  20. int prefer_tunnel,
  21. authority_type_t auth);
  22. static routerstatus_t *router_pick_trusteddirserver_impl(
  23. authority_type_t type, int requireother,
  24. int fascistfirewall, int prefer_tunnel);
  25. static void mark_all_trusteddirservers_up(void);
  26. static int router_nickname_matches(routerinfo_t *router, const char *nickname);
  27. static void trusted_dir_server_free(trusted_dir_server_t *ds);
  28. static void launch_router_descriptor_downloads(smartlist_t *downloadable,
  29. time_t now);
  30. static void update_consensus_router_descriptor_downloads(time_t now);
  31. static int signed_desc_digest_is_recognized(signed_descriptor_t *desc);
  32. static void update_router_have_minimum_dir_info(void);
  33. static const char *signed_descriptor_get_body_impl(signed_descriptor_t *desc,
  34. int with_annotations);
  35. static void list_pending_downloads(digestmap_t *result,
  36. int purpose, const char *prefix);
  37. DECLARE_TYPED_DIGESTMAP_FNS(sdmap_, digest_sd_map_t, signed_descriptor_t)
  38. DECLARE_TYPED_DIGESTMAP_FNS(rimap_, digest_ri_map_t, routerinfo_t)
  39. DECLARE_TYPED_DIGESTMAP_FNS(eimap_, digest_ei_map_t, extrainfo_t)
  40. /****************************************************************************/
  41. /** Global list of a trusted_dir_server_t object for each trusted directory
  42. * server. */
  43. static smartlist_t *trusted_dir_servers = NULL;
  44. /** True iff the key certificate in at least one member of
  45. * <b>trusted_dir_server_t</b> has changed since we last flushed the
  46. * certificates to disk. */
  47. static int trusted_dir_servers_certs_changed = 0;
  48. /** Global list of all of the routers that we know about. */
  49. static routerlist_t *routerlist = NULL;
  50. /** List of strings for nicknames we've already warned about and that are
  51. * still unknown / unavailable. */
  52. static smartlist_t *warned_nicknames = NULL;
  53. /** The last time we tried to download any routerdesc, or 0 for "never". We
  54. * use this to rate-limit download attempts when the number of routerdescs to
  55. * download is low. */
  56. static time_t last_routerdesc_download_attempted = 0;
  57. /** Return the number of directory authorities whose type matches some bit set
  58. * in <b>type</b> */
  59. int
  60. get_n_authorities(authority_type_t type)
  61. {
  62. int n = 0;
  63. if (!trusted_dir_servers)
  64. return 0;
  65. SMARTLIST_FOREACH(trusted_dir_servers, trusted_dir_server_t *, ds,
  66. if (ds->type & type)
  67. ++n);
  68. return n;
  69. }
  70. #define get_n_v2_authorities() get_n_authorities(V2_AUTHORITY)
  71. /** Reload the cached v3 key certificates from the cached-certs file in
  72. * the data directory. Return 0 on success, -1 on failure. */
  73. int
  74. trusted_dirs_reload_certs(void)
  75. {
  76. char *filename;
  77. char *contents;
  78. int r;
  79. filename = get_datadir_fname("cached-certs");
  80. contents = read_file_to_str(filename, RFTS_IGNORE_MISSING, NULL);
  81. tor_free(filename);
  82. if (!contents)
  83. return 0;
  84. r = trusted_dirs_load_certs_from_string(contents, 1);
  85. tor_free(contents);
  86. return r;
  87. }
  88. /** Load a bunch of new key certificates from the string <b>contents</b>. If
  89. * <b>from_store</b> is true, the certificates are from the cache, and we
  90. * don't need to flush them to disk. If <b>from_store</b> is false, we need
  91. * to flush any changed certificates to disk. Return 0 on success, -1 on
  92. * failure. */
  93. int
  94. trusted_dirs_load_certs_from_string(const char *contents, int from_store)
  95. {
  96. trusted_dir_server_t *ds;
  97. const char *s, *eos;
  98. for (s = contents; *s; s = eos) {
  99. authority_cert_t *cert = authority_cert_parse_from_string(s, &eos);
  100. int found = 0;
  101. if (!cert)
  102. break;
  103. ds = trusteddirserver_get_by_v3_auth_digest(
  104. cert->cache_info.identity_digest);
  105. if (!ds) {
  106. log_info(LD_DIR, "Found cached certificate whose key didn't match "
  107. "any v3 authority we recognized; skipping.");
  108. authority_cert_free(cert);
  109. continue;
  110. }
  111. if (!ds->v3_certs)
  112. ds->v3_certs = smartlist_create();
  113. SMARTLIST_FOREACH(ds->v3_certs, authority_cert_t *, c,
  114. {
  115. if (!memcmp(c->cache_info.signed_descriptor_digest,
  116. cert->cache_info.signed_descriptor_digest,
  117. DIGEST_LEN)) {
  118. /* we already have this one. continue. */
  119. authority_cert_free(cert);
  120. found = 1;
  121. break;
  122. }
  123. });
  124. if (found)
  125. continue;
  126. cert->cache_info.signed_descriptor_body = tor_strndup(s, eos-s);
  127. cert->cache_info.signed_descriptor_len = eos-s;
  128. smartlist_add(ds->v3_certs, cert);
  129. if (!from_store)
  130. trusted_dir_servers_certs_changed = 1;
  131. }
  132. trusted_dirs_flush_certs_to_disk();
  133. networkstatus_note_certs_arrived();
  134. return 0;
  135. }
  136. /** Save all v3 key certifiacates to the cached-certs file. */
  137. void
  138. trusted_dirs_flush_certs_to_disk(void)
  139. {
  140. char *filename;
  141. smartlist_t *chunks;
  142. if (!trusted_dir_servers_certs_changed)
  143. return;
  144. chunks = smartlist_create();
  145. SMARTLIST_FOREACH(trusted_dir_servers, trusted_dir_server_t *, ds,
  146. {
  147. if (ds->v3_certs) {
  148. SMARTLIST_FOREACH(ds->v3_certs, authority_cert_t *, cert,
  149. {
  150. sized_chunk_t *c = tor_malloc(sizeof(sized_chunk_t));
  151. c->bytes = cert->cache_info.signed_descriptor_body;
  152. c->len = cert->cache_info.signed_descriptor_len;
  153. smartlist_add(chunks, c);
  154. });
  155. }
  156. });
  157. filename = get_datadir_fname("cached-certs");
  158. if (write_chunks_to_file(filename, chunks, 0)) {
  159. log_warn(LD_FS, "Error writing certificates to disk.");
  160. }
  161. tor_free(filename);
  162. SMARTLIST_FOREACH(chunks, sized_chunk_t *, c, tor_free(c));
  163. smartlist_free(chunks);
  164. trusted_dir_servers_certs_changed = 0;
  165. }
  166. /** Remove all v3 authority certificates that have been superseded for more
  167. * than 48 hours. (If the most recent cert was published more than 48 hours
  168. * ago, then we aren't going to get any consensuses signed with older
  169. * keys.) */
  170. static void
  171. trusted_dirs_remove_old_certs(void)
  172. {
  173. #define OLD_CERT_LIFETIME (48*60*60)
  174. SMARTLIST_FOREACH(trusted_dir_servers, trusted_dir_server_t *, ds,
  175. {
  176. authority_cert_t *newest = NULL;
  177. if (!ds->v3_certs)
  178. continue;
  179. SMARTLIST_FOREACH(ds->v3_certs, authority_cert_t *, cert,
  180. if (!newest || (cert->cache_info.published_on >
  181. newest->cache_info.published_on))
  182. newest = cert);
  183. SMARTLIST_FOREACH(ds->v3_certs, authority_cert_t *, cert,
  184. if (newest && (newest->cache_info.published_on >
  185. cert->cache_info.published_on + OLD_CERT_LIFETIME)) {
  186. SMARTLIST_DEL_CURRENT(ds->v3_certs, cert);
  187. authority_cert_free(cert);
  188. trusted_dir_servers_certs_changed = 1;
  189. });
  190. });
  191. #undef OLD_CERT_LIFETIME
  192. trusted_dirs_flush_certs_to_disk();
  193. }
  194. /** Return the newest v3 authority certificate whose v3 authority identity key
  195. * has digest <b>id_digest</b>. Return NULL if no such authority is known,
  196. * or it has no certificate. */
  197. authority_cert_t *
  198. authority_cert_get_newest_by_id(const char *id_digest)
  199. {
  200. trusted_dir_server_t *ds = trusteddirserver_get_by_v3_auth_digest(id_digest);
  201. authority_cert_t *best = NULL;
  202. if (!ds || !ds->v3_certs)
  203. return NULL;
  204. SMARTLIST_FOREACH(ds->v3_certs, authority_cert_t *, cert,
  205. {
  206. if (!best || cert->cache_info.published_on > best->cache_info.published_on)
  207. best = cert;
  208. });
  209. return best;
  210. }
  211. /** Return the newest v3 authority certificate whose directory signing key has
  212. * giest <sk_digest</b>. Return NULL if no such certificate is known.
  213. */
  214. authority_cert_t *
  215. authority_cert_get_by_sk_digest(const char *sk_digest)
  216. {
  217. if (!trusted_dir_servers)
  218. return NULL;
  219. SMARTLIST_FOREACH(trusted_dir_servers, trusted_dir_server_t *, ds,
  220. {
  221. if (!ds->v3_certs)
  222. continue;
  223. SMARTLIST_FOREACH(ds->v3_certs, authority_cert_t *, cert,
  224. {
  225. if (!memcmp(cert->signing_key_digest, sk_digest, DIGEST_LEN))
  226. return cert;
  227. });
  228. });
  229. return NULL;
  230. }
  231. /** Return the v3 authority certificate with signing key matching
  232. * <b>sk_digest</b>, for the authority with identity digest <b>id_digest</b>.
  233. * Return NULL if no such authority is known. */
  234. authority_cert_t *
  235. authority_cert_get_by_digests(const char *id_digest,
  236. const char *sk_digest)
  237. {
  238. trusted_dir_server_t *ds = trusteddirserver_get_by_v3_auth_digest(id_digest);
  239. if (!ds || !ds->v3_certs)
  240. return NULL;
  241. SMARTLIST_FOREACH(ds->v3_certs, authority_cert_t *, cert,
  242. if (!memcmp(cert->signing_key_digest, sk_digest, DIGEST_LEN))
  243. return cert; );
  244. return NULL;
  245. }
  246. /** How many times will we try to fetch a certificate before giving up? */
  247. #define MAX_CERT_DL_FAILURES 8
  248. /** Try to download any v3 authority certificates that we may be missing. If
  249. * <b>status</b> is provided, try to get all the ones that were used to sign
  250. * <b>status</b>. Additionally, try to have a non-expired certificate for
  251. * every V3 authority in trusted_dir_servers. Don't fetch certificates we
  252. * already have.
  253. **/
  254. void
  255. authority_certs_fetch_missing(networkstatus_vote_t *status, time_t now)
  256. {
  257. digestmap_t *pending = digestmap_new();
  258. smartlist_t *missing_digests = smartlist_create();
  259. char *resource = NULL;
  260. list_pending_downloads(pending, DIR_PURPOSE_FETCH_CERTIFICATE, "fp/");
  261. if (status) {
  262. SMARTLIST_FOREACH(status->voters, networkstatus_voter_info_t *, voter,
  263. {
  264. trusted_dir_server_t *ds
  265. = trusteddirserver_get_by_v3_auth_digest(voter->identity_digest);
  266. if (!ds)
  267. continue;
  268. if (authority_cert_get_by_digests(voter->identity_digest,
  269. voter->signing_key_digest)) {
  270. download_status_reset(&ds->cert_dl_status);
  271. continue;
  272. }
  273. if (download_status_is_ready(&ds->cert_dl_status, now,
  274. MAX_CERT_DL_FAILURES))
  275. smartlist_add(missing_digests, voter->identity_digest);
  276. });
  277. }
  278. SMARTLIST_FOREACH(trusted_dir_servers, trusted_dir_server_t *, ds,
  279. {
  280. int found = 0;
  281. if (!(ds->type & V3_AUTHORITY))
  282. continue;
  283. if (smartlist_digest_isin(missing_digests, ds->v3_identity_digest))
  284. continue;
  285. if (!ds->v3_certs)
  286. ds->v3_certs = smartlist_create();
  287. SMARTLIST_FOREACH(ds->v3_certs, authority_cert_t *, cert,
  288. {
  289. if (!ftime_definitely_after(now, cert->expires)) {
  290. /* It's not expired, and we weren't looking for something to
  291. * verify a consensus with. Call it done. */
  292. download_status_reset(&ds->cert_dl_status);
  293. found = 1;
  294. break;
  295. }
  296. });
  297. if (!found && download_status_is_ready(&ds->cert_dl_status, now,
  298. MAX_CERT_DL_FAILURES))
  299. smartlist_add(missing_digests, ds->v3_identity_digest);
  300. });
  301. if (!smartlist_len(missing_digests)) {
  302. goto done;
  303. } else {
  304. smartlist_t *fps = smartlist_create();
  305. smartlist_add(fps, tor_strdup("fp/"));
  306. SMARTLIST_FOREACH(missing_digests, const char *, d, {
  307. char *fp;
  308. if (digestmap_get(pending, d))
  309. continue;
  310. fp = tor_malloc(HEX_DIGEST_LEN+2);
  311. base16_encode(fp, HEX_DIGEST_LEN+1, d, DIGEST_LEN);
  312. fp[HEX_DIGEST_LEN] = '+';
  313. fp[HEX_DIGEST_LEN+1] = '\0';
  314. smartlist_add(fps, fp);
  315. });
  316. resource = smartlist_join_strings(fps, "", 0, NULL);
  317. resource[strlen(resource)-1] = '\0';
  318. SMARTLIST_FOREACH(fps, char *, cp, tor_free(cp));
  319. smartlist_free(fps);
  320. }
  321. log_notice(LD_DIR, "Launching request for %d missing certificates",
  322. smartlist_len(missing_digests));
  323. directory_get_from_dirserver(DIR_PURPOSE_FETCH_CERTIFICATE, 0,
  324. resource, 1);
  325. done:
  326. tor_free(resource);
  327. smartlist_free(missing_digests);
  328. digestmap_free(pending, NULL);
  329. }
  330. /* Router descriptor storage.
  331. *
  332. * Routerdescs are stored in a big file, named "cached-descriptors". As new
  333. * routerdescs arrive, we append them to a journal file named
  334. * "cached-descriptors.new".
  335. *
  336. * From time to time, we replace "cached-descriptors" with a new file
  337. * containing only the live, non-superseded descriptors, and clear
  338. * cached-routers.new.
  339. *
  340. * On startup, we read both files.
  341. */
  342. /** Helper: return 1 iff the router log is so big we want to rebuild the
  343. * store. */
  344. static int
  345. router_should_rebuild_store(desc_store_t *store)
  346. {
  347. if (store->store_len > (1<<16))
  348. return (store->journal_len > store->store_len / 2 ||
  349. store->bytes_dropped > store->store_len / 2);
  350. else
  351. return store->journal_len > (1<<15);
  352. }
  353. static INLINE desc_store_t *
  354. desc_get_store(routerlist_t *rl, signed_descriptor_t *sd)
  355. {
  356. if (sd->is_extrainfo)
  357. return &rl->extrainfo_store;
  358. else
  359. return &rl->desc_store;
  360. }
  361. static INLINE desc_store_t *
  362. router_get_store(routerlist_t *rl, routerinfo_t *ri)
  363. {
  364. return desc_get_store(rl, &ri->cache_info);
  365. }
  366. /** Add the signed_descriptor_t in <b>desc</b> to the router
  367. * journal; change its saved_location to SAVED_IN_JOURNAL and set its
  368. * offset appropriately. */
  369. static int
  370. signed_desc_append_to_journal(signed_descriptor_t *desc,
  371. desc_store_t *store)
  372. {
  373. char *fname = get_datadir_fname_suffix(store->fname_base, ".new");
  374. const char *body = signed_descriptor_get_body_impl(desc,1);
  375. size_t len = desc->signed_descriptor_len + desc->annotations_len;
  376. tor_assert(len == strlen(body));
  377. if (append_bytes_to_file(fname, body, len, 1)) {
  378. log_warn(LD_FS, "Unable to store router descriptor");
  379. tor_free(fname);
  380. return -1;
  381. }
  382. desc->saved_location = SAVED_IN_JOURNAL;
  383. tor_free(fname);
  384. desc->saved_offset = store->journal_len;
  385. store->journal_len += len;
  386. return 0;
  387. }
  388. /** Sorting helper: return &lt;0, 0, or &gt;0 depending on whether the
  389. * signed_descriptor_t* in *<b>a</b> is older, the same age as, or newer than
  390. * the signed_descriptor_t* in *<b>b</b>. */
  391. static int
  392. _compare_signed_descriptors_by_age(const void **_a, const void **_b)
  393. {
  394. const signed_descriptor_t *r1 = *_a, *r2 = *_b;
  395. return r1->published_on - r2->published_on;
  396. }
  397. /** If the journal is too long, or if <b>force</b> is true, then atomically
  398. * replace the router store with the routers currently in our routerlist, and
  399. * clear the journal. Return 0 on success, -1 on failure.
  400. *
  401. * If <b>extrainfo</b> is true, rebuild the extrainfo store; else rebuild the
  402. * router descriptor store.
  403. */
  404. static int
  405. router_rebuild_store(int force, desc_store_t *store)
  406. {
  407. or_options_t *options;
  408. smartlist_t *chunk_list = NULL;
  409. char *fname = NULL, *fname_tmp = NULL;
  410. int r = -1;
  411. off_t offset = 0;
  412. smartlist_t *signed_descriptors = NULL;
  413. int nocache=0;
  414. if (!force && !router_should_rebuild_store(store))
  415. return 0;
  416. if (!routerlist)
  417. return 0;
  418. //routerlist_assert_ok(routerlist);
  419. /* Don't save deadweight. */
  420. routerlist_remove_old_routers();
  421. log_info(LD_DIR, "Rebuilding %s cache", store->description);
  422. options = get_options();
  423. fname = get_datadir_fname(store->fname_base);
  424. fname_tmp = get_datadir_fname_suffix(store->fname_base, ".tmp");
  425. chunk_list = smartlist_create();
  426. /* We sort the routers by age to enhance locality on disk. */
  427. signed_descriptors = smartlist_create();
  428. if (store->type == EXTRAINFO_STORE) {
  429. eimap_iter_t *iter;
  430. for (iter = eimap_iter_init(routerlist->extra_info_map);
  431. !eimap_iter_done(iter);
  432. iter = eimap_iter_next(routerlist->extra_info_map, iter)) {
  433. const char *key;
  434. extrainfo_t *ei;
  435. eimap_iter_get(iter, &key, &ei);
  436. smartlist_add(signed_descriptors, &ei->cache_info);
  437. }
  438. } else {
  439. SMARTLIST_FOREACH(routerlist->old_routers, signed_descriptor_t *, sd,
  440. smartlist_add(signed_descriptors, sd));
  441. SMARTLIST_FOREACH(routerlist->routers, routerinfo_t *, ri,
  442. smartlist_add(signed_descriptors, &ri->cache_info));
  443. }
  444. smartlist_sort(signed_descriptors, _compare_signed_descriptors_by_age);
  445. /* Now, add the appropriate members to chunk_list */
  446. SMARTLIST_FOREACH(signed_descriptors, signed_descriptor_t *, sd,
  447. {
  448. sized_chunk_t *c;
  449. const char *body = signed_descriptor_get_body_impl(sd, 1);
  450. if (!body) {
  451. log_warn(LD_BUG, "No descriptor available for router.");
  452. goto done;
  453. }
  454. if (sd->do_not_cache) {
  455. ++nocache;
  456. continue;
  457. }
  458. c = tor_malloc(sizeof(sized_chunk_t));
  459. c->bytes = body;
  460. c->len = sd->signed_descriptor_len + sd->annotations_len;
  461. smartlist_add(chunk_list, c);
  462. });
  463. if (write_chunks_to_file(fname_tmp, chunk_list, 1)<0) {
  464. log_warn(LD_FS, "Error writing router store to disk.");
  465. goto done;
  466. }
  467. /* Our mmap is now invalid. */
  468. if (store->mmap) {
  469. tor_munmap_file(store->mmap);
  470. store->mmap = NULL;
  471. }
  472. if (replace_file(fname_tmp, fname)<0) {
  473. log_warn(LD_FS, "Error replacing old router store.");
  474. goto done;
  475. }
  476. store->mmap = tor_mmap_file(fname);
  477. if (! store->mmap) {
  478. log_warn(LD_FS, "Unable to mmap new descriptor file at '%s'.",fname);
  479. //tor_assert(0);
  480. }
  481. log_info(LD_DIR, "Reconstructing pointers into cache");
  482. offset = 0;
  483. SMARTLIST_FOREACH(signed_descriptors, signed_descriptor_t *, sd,
  484. {
  485. if (sd->do_not_cache)
  486. continue;
  487. sd->saved_location = SAVED_IN_CACHE;
  488. if (store->mmap) {
  489. tor_free(sd->signed_descriptor_body); // sets it to null
  490. sd->saved_offset = offset;
  491. }
  492. offset += sd->signed_descriptor_len + sd->annotations_len;
  493. signed_descriptor_get_body(sd); /* reconstruct and assert */
  494. });
  495. tor_free(fname);
  496. fname = get_datadir_fname_suffix(store->fname_base, ".new");
  497. write_str_to_file(fname, "", 1);
  498. r = 0;
  499. store->store_len = (size_t) offset;
  500. store->journal_len = 0;
  501. store->bytes_dropped = 0;
  502. done:
  503. if (signed_descriptors)
  504. smartlist_free(signed_descriptors);
  505. tor_free(fname);
  506. tor_free(fname_tmp);
  507. SMARTLIST_FOREACH(chunk_list, sized_chunk_t *, c, tor_free(c));
  508. smartlist_free(chunk_list);
  509. return r;
  510. }
  511. /** Helper: Reload a cache file and its associated journal, setting metadata
  512. * appropriately. If <b>extrainfo</b> is true, reload the extrainfo store;
  513. * else reload the router descriptor store. */
  514. static int
  515. router_reload_router_list_impl(desc_store_t *store)
  516. {
  517. char *fname = NULL, *altname = NULL, *contents = NULL;
  518. struct stat st;
  519. int read_from_old_location = 0;
  520. int extrainfo = (store->type == EXTRAINFO_STORE);
  521. time_t now = time(NULL);
  522. store->journal_len = store->store_len = 0;
  523. fname = get_datadir_fname(store->fname_base);
  524. if (store->fname_alt_base)
  525. altname = get_datadir_fname(store->fname_alt_base);
  526. if (store->mmap) /* get rid of it first */
  527. tor_munmap_file(store->mmap);
  528. store->mmap = NULL;
  529. store->mmap = tor_mmap_file(fname);
  530. if (!store->mmap && altname && file_status(altname) == FN_FILE) {
  531. read_from_old_location = 1;
  532. log_notice(LD_DIR, "Couldn't read %s; trying to load routers from old "
  533. "location %s.", fname, altname);
  534. if ((store->mmap = tor_mmap_file(altname)))
  535. read_from_old_location = 1;
  536. }
  537. if (altname && !read_from_old_location) {
  538. remove_file_if_very_old(altname, now);
  539. }
  540. if (store->mmap) {
  541. store->store_len = store->mmap->size;
  542. if (extrainfo)
  543. router_load_extrainfo_from_string(store->mmap->data,
  544. store->mmap->data+store->mmap->size,
  545. SAVED_IN_CACHE, NULL, 0);
  546. else
  547. router_load_routers_from_string(store->mmap->data,
  548. store->mmap->data+store->mmap->size,
  549. SAVED_IN_CACHE, NULL, 0, NULL);
  550. }
  551. tor_free(fname);
  552. fname = get_datadir_fname_suffix(store->fname_base, ".new");
  553. if (file_status(fname) == FN_FILE)
  554. contents = read_file_to_str(fname, RFTS_BIN|RFTS_IGNORE_MISSING, &st);
  555. if (read_from_old_location) {
  556. tor_free(altname);
  557. altname = get_datadir_fname_suffix(store->fname_alt_base, ".new");
  558. if (!contents)
  559. contents = read_file_to_str(altname, RFTS_BIN|RFTS_IGNORE_MISSING, &st);
  560. else
  561. remove_file_if_very_old(altname, now);
  562. }
  563. if (contents) {
  564. if (extrainfo)
  565. router_load_extrainfo_from_string(contents, NULL,SAVED_IN_JOURNAL,
  566. NULL, 0);
  567. else
  568. router_load_routers_from_string(contents, NULL, SAVED_IN_JOURNAL,
  569. NULL, 0, NULL);
  570. store->journal_len = (size_t) st.st_size;
  571. tor_free(contents);
  572. }
  573. tor_free(fname);
  574. tor_free(altname);
  575. if (store->journal_len || read_from_old_location) {
  576. /* Always clear the journal on startup.*/
  577. router_rebuild_store(1, store);
  578. } else if (!extrainfo) {
  579. /* Don't cache expired routers. (This is in an else because
  580. * router_rebuild_store() also calls remove_old_routers().) */
  581. routerlist_remove_old_routers();
  582. }
  583. return 0;
  584. }
  585. /** Load all cached router descriptors and extra-info documents from the
  586. * store. Return 0 on success and -1 on failure.
  587. */
  588. int
  589. router_reload_router_list(void)
  590. {
  591. routerlist_t *rl = router_get_routerlist();
  592. if (router_reload_router_list_impl(&rl->desc_store))
  593. return -1;
  594. if (router_reload_router_list_impl(&rl->extrainfo_store))
  595. return -1;
  596. return 0;
  597. }
  598. /** Return a smartlist containing a list of trusted_dir_server_t * for all
  599. * known trusted dirservers. Callers must not modify the list or its
  600. * contents.
  601. */
  602. smartlist_t *
  603. router_get_trusted_dir_servers(void)
  604. {
  605. if (!trusted_dir_servers)
  606. trusted_dir_servers = smartlist_create();
  607. return trusted_dir_servers;
  608. }
  609. /** Try to find a running dirserver. If there are no running dirservers
  610. * in our routerlist and <b>retry_if_no_servers</b> is non-zero,
  611. * set all the authoritative ones as running again, and pick one;
  612. * if there are then no dirservers at all in our routerlist,
  613. * reload the routerlist and try one last time. If for_runningrouters is
  614. * true, then only pick a dirserver that can answer runningrouters queries
  615. * (that is, a trusted dirserver, or one running 0.0.9rc5-cvs or later).
  616. * Don't pick an authority if any non-authority is viable.
  617. * Other args are as in router_pick_directory_server_impl().
  618. */
  619. routerstatus_t *
  620. router_pick_directory_server(int requireother,
  621. int fascistfirewall,
  622. authority_type_t type,
  623. int retry_if_no_servers)
  624. {
  625. routerstatus_t *choice;
  626. int prefer_tunnel = get_options()->PreferTunneledDirConns;
  627. if (!routerlist)
  628. return NULL;
  629. choice = router_pick_directory_server_impl(requireother, fascistfirewall,
  630. prefer_tunnel, type);
  631. if (choice || !retry_if_no_servers)
  632. return choice;
  633. log_info(LD_DIR,
  634. "No reachable router entries for dirservers. "
  635. "Trying them all again.");
  636. /* mark all authdirservers as up again */
  637. mark_all_trusteddirservers_up();
  638. /* try again */
  639. choice = router_pick_directory_server_impl(requireother, fascistfirewall,
  640. prefer_tunnel, type);
  641. if (choice)
  642. return choice;
  643. log_info(LD_DIR,"Still no %s router entries. Reloading and trying again.",
  644. fascistfirewall ? "reachable" : "known");
  645. if (router_reload_router_list()) {
  646. return NULL;
  647. }
  648. /* give it one last try */
  649. choice = router_pick_directory_server_impl(requireother, fascistfirewall,
  650. prefer_tunnel, type);
  651. return choice;
  652. }
  653. /** Return the trusted_dir_server_t for the directory authority whose identity
  654. * key hashes to <b>digest</b>, or NULL if no such authority is known.
  655. */
  656. trusted_dir_server_t *
  657. router_get_trusteddirserver_by_digest(const char *digest)
  658. {
  659. if (!trusted_dir_servers)
  660. return NULL;
  661. SMARTLIST_FOREACH(trusted_dir_servers, trusted_dir_server_t *, ds,
  662. {
  663. if (!memcmp(ds->digest, digest, DIGEST_LEN))
  664. return ds;
  665. });
  666. return NULL;
  667. }
  668. /** Return the trusted_dir_server_t for the directory authority whose identity
  669. * key hashes to <b>digest</b>, or NULL if no such authority is known.
  670. */
  671. trusted_dir_server_t *
  672. trusteddirserver_get_by_v3_auth_digest(const char *digest)
  673. {
  674. if (!trusted_dir_servers)
  675. return NULL;
  676. SMARTLIST_FOREACH(trusted_dir_servers, trusted_dir_server_t *, ds,
  677. {
  678. if (!memcmp(ds->v3_identity_digest, digest, DIGEST_LEN))
  679. return ds;
  680. });
  681. return NULL;
  682. }
  683. /** Try to find a running trusted dirserver. If there are no running
  684. * trusted dirservers and <b>retry_if_no_servers</b> is non-zero,
  685. * set them all as running again, and try again.
  686. * <b>type> specifies the type of authoritative dir we require.
  687. * Other args are as in router_pick_trusteddirserver_impl().
  688. */
  689. routerstatus_t *
  690. router_pick_trusteddirserver(authority_type_t type,
  691. int requireother,
  692. int fascistfirewall,
  693. int retry_if_no_servers)
  694. {
  695. routerstatus_t *choice;
  696. int prefer_tunnel = get_options()->PreferTunneledDirConns;
  697. choice = router_pick_trusteddirserver_impl(type, requireother,
  698. fascistfirewall, prefer_tunnel);
  699. if (choice || !retry_if_no_servers)
  700. return choice;
  701. log_info(LD_DIR,
  702. "No trusted dirservers are reachable. Trying them all again.");
  703. mark_all_trusteddirservers_up();
  704. return router_pick_trusteddirserver_impl(type, requireother,
  705. fascistfirewall, prefer_tunnel);
  706. }
  707. /** How long do we avoid using a directory server after it's given us a 503? */
  708. #define DIR_503_TIMEOUT (60*60)
  709. /** Pick a random running valid directory server/mirror from our
  710. * routerlist.
  711. *
  712. * If <b>fascistfirewall</b>, make sure the router we pick is allowed
  713. * by our firewall options.
  714. * If <b>requireother</b>, it cannot be us. If <b>for_v2_directory</b>,
  715. * choose a directory server new enough to support the v2 directory
  716. * functionality.
  717. * If <b>prefer_tunnel</b>, choose a directory server that is reachable
  718. * and supports BEGIN_DIR cells, if possible.
  719. *
  720. * Don't pick an authority if any non-authorities are viable. Try to
  721. * avoid using servers that are overloaded (have returned 503 recently).
  722. */
  723. static routerstatus_t *
  724. router_pick_directory_server_impl(int requireother, int fascistfirewall,
  725. int prefer_tunnel, authority_type_t type)
  726. {
  727. routerstatus_t *result;
  728. smartlist_t *direct, *tunnel;
  729. smartlist_t *trusted_direct, *trusted_tunnel;
  730. smartlist_t *overloaded_direct, *overloaded_tunnel;
  731. time_t now = time(NULL);
  732. const networkstatus_vote_t *consensus = networkstatus_get_latest_consensus();
  733. if (!consensus)
  734. return NULL;
  735. direct = smartlist_create();
  736. tunnel = smartlist_create();
  737. trusted_direct = smartlist_create();
  738. trusted_tunnel = smartlist_create();
  739. overloaded_direct = smartlist_create();
  740. overloaded_tunnel = smartlist_create();
  741. /* Find all the running dirservers we know about. */
  742. SMARTLIST_FOREACH(consensus->routerstatus_list, routerstatus_t *, status,
  743. {
  744. int is_trusted;
  745. int is_overloaded = status->last_dir_503_at + DIR_503_TIMEOUT > now;
  746. if (!status->is_running || !status->dir_port || !status->is_valid)
  747. continue;
  748. if (status->is_bad_directory)
  749. continue;
  750. if (requireother && router_digest_is_me(status->identity_digest))
  751. continue;
  752. if (type & V3_AUTHORITY) {
  753. if (!(status->version_supports_v3_dir ||
  754. router_digest_is_trusted_dir_type(status->identity_digest,
  755. V3_AUTHORITY)))
  756. continue;
  757. }
  758. is_trusted = router_digest_is_trusted_dir(status->identity_digest);
  759. if ((type & V2_AUTHORITY) && !(status->is_v2_dir || is_trusted))
  760. continue;
  761. if ((type & EXTRAINFO_CACHE) &&
  762. !router_supports_extrainfo(status->identity_digest, 0))
  763. continue;
  764. if (prefer_tunnel &&
  765. status->version_supports_begindir &&
  766. (!fascistfirewall ||
  767. fascist_firewall_allows_address_or(status->addr, status->or_port)))
  768. smartlist_add(is_trusted ? trusted_tunnel :
  769. is_overloaded ? overloaded_tunnel : tunnel, status);
  770. else if (!fascistfirewall ||
  771. fascist_firewall_allows_address_dir(status->addr,
  772. status->dir_port))
  773. smartlist_add(is_trusted ? trusted_direct :
  774. is_overloaded ? overloaded_direct : direct, status);
  775. });
  776. if (smartlist_len(tunnel)) {
  777. result = routerstatus_sl_choose_by_bandwidth(tunnel);
  778. } else if (smartlist_len(overloaded_tunnel)) {
  779. result = routerstatus_sl_choose_by_bandwidth(overloaded_tunnel);
  780. } else if (smartlist_len(trusted_tunnel)) {
  781. /* FFFF We don't distinguish between trusteds and overloaded trusteds
  782. * yet. Maybe one day we should. */
  783. /* FFFF We also don't load balance over authorities yet. I think this
  784. * is a feature, but it could easily be a bug. -RD */
  785. result = smartlist_choose(trusted_tunnel);
  786. } else if (smartlist_len(direct)) {
  787. result = routerstatus_sl_choose_by_bandwidth(direct);
  788. } else if (smartlist_len(overloaded_direct)) {
  789. result = routerstatus_sl_choose_by_bandwidth(overloaded_direct);
  790. } else {
  791. result = smartlist_choose(trusted_direct);
  792. }
  793. smartlist_free(direct);
  794. smartlist_free(tunnel);
  795. smartlist_free(trusted_direct);
  796. smartlist_free(trusted_tunnel);
  797. smartlist_free(overloaded_direct);
  798. smartlist_free(overloaded_tunnel);
  799. return result;
  800. }
  801. /** Choose randomly from among the trusted dirservers that are up. If
  802. * <b>fascistfirewall</b>, make sure the port we pick is allowed by our
  803. * firewall options. If <b>requireother</b>, it cannot be us.
  804. * <b>type> specifies the type of authoritative dir we require.
  805. */
  806. static routerstatus_t *
  807. router_pick_trusteddirserver_impl(authority_type_t type,
  808. int requireother, int fascistfirewall,
  809. int prefer_tunnel)
  810. {
  811. smartlist_t *direct, *tunnel;
  812. smartlist_t *overloaded_direct, *overloaded_tunnel;
  813. routerinfo_t *me = router_get_my_routerinfo();
  814. routerstatus_t *result;
  815. time_t now = time(NULL);
  816. direct = smartlist_create();
  817. tunnel = smartlist_create();
  818. overloaded_direct = smartlist_create();
  819. overloaded_tunnel = smartlist_create();
  820. if (!trusted_dir_servers)
  821. return NULL;
  822. SMARTLIST_FOREACH(trusted_dir_servers, trusted_dir_server_t *, d,
  823. {
  824. int is_overloaded =
  825. d->fake_status.last_dir_503_at + DIR_503_TIMEOUT > now;
  826. if (!d->is_running) continue;
  827. if ((type & d->type) == 0)
  828. continue;
  829. if ((type & EXTRAINFO_CACHE) &&
  830. !router_supports_extrainfo(d->digest, 1))
  831. continue;
  832. if (requireother && me && router_digest_is_me(d->digest))
  833. continue;
  834. if (prefer_tunnel &&
  835. d->or_port &&
  836. (!fascistfirewall ||
  837. fascist_firewall_allows_address_or(d->addr, d->or_port)))
  838. smartlist_add(is_overloaded ? overloaded_tunnel : tunnel,
  839. &d->fake_status);
  840. else if (!fascistfirewall ||
  841. fascist_firewall_allows_address_dir(d->addr, d->dir_port))
  842. smartlist_add(is_overloaded ? overloaded_direct : direct,
  843. &d->fake_status);
  844. });
  845. if (smartlist_len(tunnel)) {
  846. result = smartlist_choose(tunnel);
  847. } else if (smartlist_len(overloaded_tunnel)) {
  848. result = smartlist_choose(overloaded_tunnel);
  849. } else if (smartlist_len(direct)) {
  850. result = smartlist_choose(direct);
  851. } else {
  852. result = smartlist_choose(overloaded_direct);
  853. }
  854. smartlist_free(direct);
  855. smartlist_free(tunnel);
  856. smartlist_free(overloaded_direct);
  857. smartlist_free(overloaded_tunnel);
  858. return result;
  859. }
  860. /** Go through and mark the authoritative dirservers as up. */
  861. static void
  862. mark_all_trusteddirservers_up(void)
  863. {
  864. if (routerlist) {
  865. SMARTLIST_FOREACH(routerlist->routers, routerinfo_t *, router,
  866. if (router_digest_is_trusted_dir(router->cache_info.identity_digest) &&
  867. router->dir_port > 0) {
  868. router->is_running = 1;
  869. });
  870. }
  871. if (trusted_dir_servers) {
  872. SMARTLIST_FOREACH(trusted_dir_servers, trusted_dir_server_t *, dir,
  873. {
  874. routerstatus_t *rs;
  875. dir->is_running = 1;
  876. download_status_reset(&dir->v2_ns_dl_status);
  877. rs = router_get_consensus_status_by_id(dir->digest);
  878. if (rs && !rs->is_running) {
  879. rs->is_running = 1;
  880. rs->last_dir_503_at = 0;
  881. control_event_networkstatus_changed_single(rs);
  882. }
  883. });
  884. }
  885. router_dir_info_changed();
  886. }
  887. /** Reset all internal variables used to count failed downloads of network
  888. * status objects. */
  889. void
  890. router_reset_status_download_failures(void)
  891. {
  892. mark_all_trusteddirservers_up();
  893. }
  894. /** Return true iff router1 and router2 have the same /16 network. */
  895. static INLINE int
  896. routers_in_same_network_family(routerinfo_t *r1, routerinfo_t *r2)
  897. {
  898. return (r1->addr & 0xffff0000) == (r2->addr & 0xffff0000);
  899. }
  900. /** Look through the routerlist and identify routers that
  901. * advertise the same /16 network address as <b>router</b>.
  902. * Add each of them to <b>sl</b>.
  903. */
  904. static void
  905. routerlist_add_network_family(smartlist_t *sl, routerinfo_t *router)
  906. {
  907. SMARTLIST_FOREACH(routerlist->routers, routerinfo_t *, r,
  908. {
  909. if (router != r && routers_in_same_network_family(router, r))
  910. smartlist_add(sl, r);
  911. });
  912. }
  913. /** Add all the family of <b>router</b> to the smartlist <b>sl</b>.
  914. * This is used to make sure we don't pick siblings in a single path.
  915. */
  916. void
  917. routerlist_add_family(smartlist_t *sl, routerinfo_t *router)
  918. {
  919. routerinfo_t *r;
  920. config_line_t *cl;
  921. or_options_t *options = get_options();
  922. /* First, add any routers with similar network addresses. */
  923. if (options->EnforceDistinctSubnets)
  924. routerlist_add_network_family(sl, router);
  925. if (router->declared_family) {
  926. /* Add every r such that router declares familyness with r, and r
  927. * declares familyhood with router. */
  928. SMARTLIST_FOREACH(router->declared_family, const char *, n,
  929. {
  930. if (!(r = router_get_by_nickname(n, 0)))
  931. continue;
  932. if (!r->declared_family)
  933. continue;
  934. SMARTLIST_FOREACH(r->declared_family, const char *, n2,
  935. {
  936. if (router_nickname_matches(router, n2))
  937. smartlist_add(sl, r);
  938. });
  939. });
  940. }
  941. /* If the user declared any families locally, honor those too. */
  942. for (cl = options->NodeFamilies; cl; cl = cl->next) {
  943. if (router_nickname_is_in_list(router, cl->value)) {
  944. add_nickname_list_to_smartlist(sl, cl->value, 0);
  945. }
  946. }
  947. }
  948. /** Return true iff r is named by some nickname in <b>lst</b>. */
  949. static INLINE int
  950. router_in_nickname_smartlist(smartlist_t *lst, routerinfo_t *r)
  951. {
  952. if (!lst) return 0;
  953. SMARTLIST_FOREACH(lst, const char *, name,
  954. if (router_nickname_matches(r, name))
  955. return 1;);
  956. return 0;
  957. }
  958. /** Return true iff r1 and r2 are in the same family, but not the same
  959. * router. */
  960. int
  961. routers_in_same_family(routerinfo_t *r1, routerinfo_t *r2)
  962. {
  963. or_options_t *options = get_options();
  964. config_line_t *cl;
  965. if (options->EnforceDistinctSubnets && routers_in_same_network_family(r1,r2))
  966. return 1;
  967. if (router_in_nickname_smartlist(r1->declared_family, r2) &&
  968. router_in_nickname_smartlist(r2->declared_family, r1))
  969. return 1;
  970. for (cl = options->NodeFamilies; cl; cl = cl->next) {
  971. if (router_nickname_is_in_list(r1, cl->value) &&
  972. router_nickname_is_in_list(r2, cl->value))
  973. return 1;
  974. }
  975. return 0;
  976. }
  977. /** Given a (possibly NULL) comma-and-whitespace separated list of nicknames,
  978. * see which nicknames in <b>list</b> name routers in our routerlist, and add
  979. * the routerinfos for those routers to <b>sl</b>. If <b>must_be_running</b>,
  980. * only include routers that we think are running.
  981. * Warn if any non-Named routers are specified by nickname.
  982. */
  983. void
  984. add_nickname_list_to_smartlist(smartlist_t *sl, const char *list,
  985. int must_be_running)
  986. {
  987. routerinfo_t *router;
  988. smartlist_t *nickname_list;
  989. int have_dir_info = router_have_minimum_dir_info();
  990. if (!list)
  991. return; /* nothing to do */
  992. tor_assert(sl);
  993. nickname_list = smartlist_create();
  994. if (!warned_nicknames)
  995. warned_nicknames = smartlist_create();
  996. smartlist_split_string(nickname_list, list, ",",
  997. SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
  998. SMARTLIST_FOREACH(nickname_list, const char *, nick, {
  999. int warned;
  1000. if (!is_legal_nickname_or_hexdigest(nick)) {
  1001. log_warn(LD_CONFIG, "Nickname '%s' is misformed; skipping", nick);
  1002. continue;
  1003. }
  1004. router = router_get_by_nickname(nick, 1);
  1005. warned = smartlist_string_isin(warned_nicknames, nick);
  1006. if (router) {
  1007. if (!must_be_running || router->is_running) {
  1008. smartlist_add(sl,router);
  1009. }
  1010. } else if (!router_get_consensus_status_by_nickname(nick,1)) {
  1011. if (!warned) {
  1012. log_fn(have_dir_info ? LOG_WARN : LOG_INFO, LD_CONFIG,
  1013. "Nickname list includes '%s' which isn't a known router.",nick);
  1014. smartlist_add(warned_nicknames, tor_strdup(nick));
  1015. }
  1016. }
  1017. });
  1018. SMARTLIST_FOREACH(nickname_list, char *, nick, tor_free(nick));
  1019. smartlist_free(nickname_list);
  1020. }
  1021. /** Return 1 iff any member of the (possibly NULL) comma-separated list
  1022. * <b>list</b> is an acceptable nickname or hexdigest for <b>router</b>. Else
  1023. * return 0.
  1024. */
  1025. int
  1026. router_nickname_is_in_list(routerinfo_t *router, const char *list)
  1027. {
  1028. smartlist_t *nickname_list;
  1029. int v = 0;
  1030. if (!list)
  1031. return 0; /* definitely not */
  1032. tor_assert(router);
  1033. nickname_list = smartlist_create();
  1034. smartlist_split_string(nickname_list, list, ",",
  1035. SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
  1036. SMARTLIST_FOREACH(nickname_list, const char *, cp,
  1037. if (router_nickname_matches(router, cp)) {v=1;break;});
  1038. SMARTLIST_FOREACH(nickname_list, char *, cp, tor_free(cp));
  1039. smartlist_free(nickname_list);
  1040. return v;
  1041. }
  1042. /** Add every suitable router from our routerlist to <b>sl</b>, so that
  1043. * we can pick a node for a circuit.
  1044. */
  1045. static void
  1046. router_add_running_routers_to_smartlist(smartlist_t *sl, int allow_invalid,
  1047. int need_uptime, int need_capacity,
  1048. int need_guard)
  1049. {
  1050. if (!routerlist)
  1051. return;
  1052. SMARTLIST_FOREACH(routerlist->routers, routerinfo_t *, router,
  1053. {
  1054. if (router->is_running &&
  1055. router->purpose == ROUTER_PURPOSE_GENERAL &&
  1056. (router->is_valid || allow_invalid) &&
  1057. !router_is_unreliable(router, need_uptime,
  1058. need_capacity, need_guard)) {
  1059. /* If it's running, and it's suitable according to the
  1060. * other flags we had in mind */
  1061. smartlist_add(sl, router);
  1062. }
  1063. });
  1064. }
  1065. /** Look through the routerlist until we find a router that has my key.
  1066. Return it. */
  1067. routerinfo_t *
  1068. routerlist_find_my_routerinfo(void)
  1069. {
  1070. if (!routerlist)
  1071. return NULL;
  1072. SMARTLIST_FOREACH(routerlist->routers, routerinfo_t *, router,
  1073. {
  1074. if (router_is_me(router))
  1075. return router;
  1076. });
  1077. return NULL;
  1078. }
  1079. /** Find a router that's up, that has this IP address, and
  1080. * that allows exit to this address:port, or return NULL if there
  1081. * isn't a good one.
  1082. */
  1083. routerinfo_t *
  1084. router_find_exact_exit_enclave(const char *address, uint16_t port)
  1085. {
  1086. uint32_t addr;
  1087. struct in_addr in;
  1088. if (!tor_inet_aton(address, &in))
  1089. return NULL; /* it's not an IP already */
  1090. addr = ntohl(in.s_addr);
  1091. SMARTLIST_FOREACH(routerlist->routers, routerinfo_t *, router,
  1092. {
  1093. if (router->is_running &&
  1094. router->addr == addr &&
  1095. compare_addr_to_addr_policy(addr, port, router->exit_policy) ==
  1096. ADDR_POLICY_ACCEPTED)
  1097. return router;
  1098. });
  1099. return NULL;
  1100. }
  1101. /** Return 1 if <b>router</b> is not suitable for these parameters, else 0.
  1102. * If <b>need_uptime</b> is non-zero, we require a minimum uptime.
  1103. * If <b>need_capacity</b> is non-zero, we require a minimum advertised
  1104. * bandwidth.
  1105. * If <b>need_guard</b>, we require that the router is a possible entry guard.
  1106. */
  1107. int
  1108. router_is_unreliable(routerinfo_t *router, int need_uptime,
  1109. int need_capacity, int need_guard)
  1110. {
  1111. if (need_uptime && !router->is_stable)
  1112. return 1;
  1113. if (need_capacity && !router->is_fast)
  1114. return 1;
  1115. if (need_guard && !router->is_possible_guard)
  1116. return 1;
  1117. return 0;
  1118. }
  1119. /** Return the smaller of the router's configured BandwidthRate
  1120. * and its advertised capacity. */
  1121. uint32_t
  1122. router_get_advertised_bandwidth(routerinfo_t *router)
  1123. {
  1124. if (router->bandwidthcapacity < router->bandwidthrate)
  1125. return router->bandwidthcapacity;
  1126. return router->bandwidthrate;
  1127. }
  1128. /** Do not weight any declared bandwidth more than this much when picking
  1129. * routers by bandwidth. */
  1130. #define DEFAULT_MAX_BELIEVABLE_BANDWIDTH 10000000 /* 10 MB/sec */
  1131. /** Eventually, the number we return will come from the directory
  1132. * consensus, so clients can dynamically update to better numbers.
  1133. *
  1134. * But for now, or in case there is no consensus available, just return
  1135. * a sufficient default. */
  1136. static uint32_t
  1137. get_max_believable_bandwidth(void)
  1138. {
  1139. return DEFAULT_MAX_BELIEVABLE_BANDWIDTH;
  1140. }
  1141. /** Helper function:
  1142. * choose a random element of smartlist <b>sl</b>, weighted by
  1143. * the advertised bandwidth of each element.
  1144. *
  1145. * If <b>statuses</b> is zero, then <b>sl</b> is a list of
  1146. * routerinfo_t's. Otherwise it's a list of routerstatus_t's.
  1147. *
  1148. * If <b>for_exit</b>, we're picking an exit node: consider all nodes'
  1149. * bandwidth equally regardless of their Exit status, since there may be
  1150. * some in the list because they exit to obscure ports. If not <b>for_exit</b>,
  1151. * we're picking a non-exit node: weight exit-node's bandwidth less
  1152. * depending on the smallness of the fraction of Exit-to-total bandwidth.
  1153. *
  1154. * If <b>for_guard</b>, we're picking a guard node: consider all guard's
  1155. * bandwidth equally. Otherwise, weight guards proportionally less.
  1156. *
  1157. */
  1158. static void *
  1159. smartlist_choose_by_bandwidth(smartlist_t *sl, bandwidth_weight_rule_t rule,
  1160. int statuses)
  1161. {
  1162. unsigned int i;
  1163. routerinfo_t *router;
  1164. routerstatus_t *status=NULL;
  1165. int32_t *bandwidths;
  1166. int is_exit;
  1167. int is_guard;
  1168. uint64_t total_nonexit_bw = 0, total_exit_bw = 0, total_bw = 0;
  1169. uint64_t total_nonguard_bw = 0, total_guard_bw = 0;
  1170. uint64_t rand_bw, tmp;
  1171. double exit_weight;
  1172. double guard_weight;
  1173. int n_unknown = 0;
  1174. bitarray_t *exit_bits;
  1175. bitarray_t *guard_bits;
  1176. uint32_t max_believable_bw = get_max_believable_bandwidth();
  1177. /* Can't choose exit and guard at same time */
  1178. tor_assert(rule == NO_WEIGHTING ||
  1179. rule == WEIGHT_FOR_EXIT ||
  1180. rule == WEIGHT_FOR_GUARD);
  1181. /* First count the total bandwidth weight, and make a list
  1182. * of each value. <0 means "unknown; no routerinfo." We use the
  1183. * bits of negative values to remember whether the router was fast (-x)&1
  1184. * and whether it was an exit (-x)&2 or guard (-x)&4. Yes, it's a hack. */
  1185. bandwidths = tor_malloc(sizeof(int32_t)*smartlist_len(sl));
  1186. exit_bits = bitarray_init_zero(smartlist_len(sl));
  1187. guard_bits = bitarray_init_zero(smartlist_len(sl));
  1188. /* Iterate over all the routerinfo_t or routerstatus_t, and */
  1189. for (i = 0; i < (unsigned)smartlist_len(sl); ++i) {
  1190. /* first, learn what bandwidth we think i has */
  1191. int is_known = 1;
  1192. int32_t flags = 0;
  1193. uint32_t this_bw = 0;
  1194. if (statuses) {
  1195. /* need to extract router info */
  1196. status = smartlist_get(sl, i);
  1197. router = router_get_by_digest(status->identity_digest);
  1198. is_exit = status->is_exit;
  1199. is_guard = status->is_possible_guard;
  1200. if (router) {
  1201. this_bw = router_get_advertised_bandwidth(router);
  1202. } else { /* guess */
  1203. is_known = 0;
  1204. flags = status->is_fast ? 1 : 0;
  1205. flags |= is_exit ? 2 : 0;
  1206. flags |= is_guard ? 4 : 0;
  1207. }
  1208. } else {
  1209. router = smartlist_get(sl, i);
  1210. is_exit = router->is_exit;
  1211. is_guard = router->is_possible_guard;
  1212. this_bw = router_get_advertised_bandwidth(router);
  1213. }
  1214. if (is_exit)
  1215. bitarray_set(exit_bits, i);
  1216. if (is_guard)
  1217. bitarray_set(guard_bits, i);
  1218. /* if they claim something huge, don't believe it */
  1219. if (this_bw > max_believable_bw) {
  1220. char fp[HEX_DIGEST_LEN+1];
  1221. base16_encode(fp, sizeof(fp), statuses ?
  1222. status->identity_digest :
  1223. router->cache_info.identity_digest,
  1224. DIGEST_LEN);
  1225. log_fn(LOG_PROTOCOL_WARN, LD_DIR,
  1226. "Bandwidth %d for router %s (%s) exceeds allowed max %d, capping",
  1227. this_bw, router ? router->nickname : "(null)",
  1228. fp, max_believable_bw);
  1229. this_bw = max_believable_bw;
  1230. }
  1231. if (is_known) {
  1232. bandwidths[i] = (int32_t) this_bw; // safe since MAX_BELIEVABLE<INT32_MAX
  1233. if (is_guard)
  1234. total_guard_bw += this_bw;
  1235. else
  1236. total_nonguard_bw += this_bw;
  1237. if (is_exit)
  1238. total_exit_bw += this_bw;
  1239. else
  1240. total_nonexit_bw += this_bw;
  1241. } else {
  1242. ++n_unknown;
  1243. bandwidths[i] = -flags;
  1244. }
  1245. }
  1246. /* Now, fill in the unknown values. */
  1247. if (n_unknown) {
  1248. int32_t avg_fast, avg_slow;
  1249. if (total_exit_bw+total_nonexit_bw) {
  1250. /* if there's some bandwidth, there's at least one known router,
  1251. * so no worries about div by 0 here */
  1252. int n_known = smartlist_len(sl)-n_unknown;
  1253. avg_fast = avg_slow = (int32_t)
  1254. ((total_exit_bw+total_nonexit_bw)/((uint64_t) n_known));
  1255. } else {
  1256. avg_fast = 40000;
  1257. avg_slow = 20000;
  1258. }
  1259. for (i=0; i<(unsigned)smartlist_len(sl); ++i) {
  1260. int32_t bw = bandwidths[i];
  1261. if (bw>=0)
  1262. continue;
  1263. is_exit = ((-bw)&2);
  1264. is_guard = ((-bw)&4);
  1265. bandwidths[i] = ((-bw)&1) ? avg_fast : avg_slow;
  1266. if (is_exit)
  1267. total_exit_bw += bandwidths[i];
  1268. else
  1269. total_nonexit_bw += bandwidths[i];
  1270. if (is_guard)
  1271. total_guard_bw += bandwidths[i];
  1272. else
  1273. total_nonguard_bw += bandwidths[i];
  1274. }
  1275. }
  1276. /* If there's no bandwidth at all, pick at random. */
  1277. if (!(total_exit_bw+total_nonexit_bw)) {
  1278. tor_free(bandwidths);
  1279. tor_free(exit_bits);
  1280. tor_free(guard_bits);
  1281. return smartlist_choose(sl);
  1282. }
  1283. /* Figure out how to weight exits and guards */
  1284. {
  1285. double all_bw = U64_TO_DBL(total_exit_bw+total_nonexit_bw);
  1286. double exit_bw = U64_TO_DBL(total_exit_bw);
  1287. double guard_bw = U64_TO_DBL(total_guard_bw);
  1288. /*
  1289. * For detailed derivation of this formula, see
  1290. * http://archives.seul.org/or/dev/Jul-2007/msg00056.html
  1291. */
  1292. if (rule == WEIGHT_FOR_EXIT)
  1293. exit_weight = 1.0;
  1294. else
  1295. exit_weight = 1.0 - all_bw/(3.0*exit_bw);
  1296. if (rule == WEIGHT_FOR_GUARD)
  1297. guard_weight = 1.0;
  1298. else
  1299. guard_weight = 1.0 - all_bw/(3.0*guard_bw);
  1300. if (exit_weight <= 0.0)
  1301. exit_weight = 0.0;
  1302. if (guard_weight <= 0.0)
  1303. guard_weight = 0.0;
  1304. total_bw = 0;
  1305. for (i=0; i < (unsigned)smartlist_len(sl); i++) {
  1306. is_exit = bitarray_is_set(exit_bits, i);
  1307. is_guard = bitarray_is_set(guard_bits, i);
  1308. if (is_exit && is_guard)
  1309. total_bw += ((uint64_t)(bandwidths[i] * exit_weight * guard_weight));
  1310. else if (is_guard)
  1311. total_bw += ((uint64_t)(bandwidths[i] * guard_weight));
  1312. else if (is_exit)
  1313. total_bw += ((uint64_t)(bandwidths[i] * exit_weight));
  1314. else
  1315. total_bw += bandwidths[i];
  1316. }
  1317. }
  1318. log_debug(LD_CIRC, "Total bw = "U64_FORMAT
  1319. ", exit bw = "U64_FORMAT
  1320. ", nonexit bw = "U64_FORMAT", exit weight = %lf "
  1321. "(for exit == %d)"
  1322. ", guard bw = "U64_FORMAT
  1323. ", nonguard bw = "U64_FORMAT", guard weight = %lf "
  1324. "(for guard == %d)",
  1325. U64_PRINTF_ARG(total_bw),
  1326. U64_PRINTF_ARG(total_exit_bw), U64_PRINTF_ARG(total_nonexit_bw),
  1327. exit_weight, (int)(rule == WEIGHT_FOR_EXIT),
  1328. U64_PRINTF_ARG(total_guard_bw), U64_PRINTF_ARG(total_nonguard_bw),
  1329. guard_weight, (int)(rule == WEIGHT_FOR_GUARD));
  1330. /* Almost done: choose a random value from the bandwidth weights. */
  1331. rand_bw = crypto_rand_uint64(total_bw);
  1332. /* Last, count through sl until we get to the element we picked */
  1333. tmp = 0;
  1334. for (i=0; i < (unsigned)smartlist_len(sl); i++) {
  1335. is_exit = bitarray_is_set(exit_bits, i);
  1336. is_guard = bitarray_is_set(guard_bits, i);
  1337. /* Weights can be 0 if not counting guards/exits */
  1338. if (is_exit && is_guard)
  1339. tmp += ((uint64_t)(bandwidths[i] * exit_weight * guard_weight));
  1340. else if (is_guard)
  1341. tmp += ((uint64_t)(bandwidths[i] * guard_weight));
  1342. else if (is_exit)
  1343. tmp += ((uint64_t)(bandwidths[i] * exit_weight));
  1344. else
  1345. tmp += bandwidths[i];
  1346. if (tmp >= rand_bw)
  1347. break;
  1348. }
  1349. if (i == (unsigned)smartlist_len(sl)) {
  1350. /* This was once possible due to round-off error, but shouldn't be able
  1351. * to occur any longer. */
  1352. tor_fragile_assert();
  1353. --i;
  1354. log_warn(LD_BUG, "Round-off error in computing bandwidth had an effect on "
  1355. " which router we chose. Please tell the developers. "
  1356. U64_FORMAT " " U64_FORMAT " " U64_FORMAT, U64_PRINTF_ARG(tmp),
  1357. U64_PRINTF_ARG(rand_bw), U64_PRINTF_ARG(total_bw));
  1358. }
  1359. tor_free(bandwidths);
  1360. tor_free(exit_bits);
  1361. tor_free(guard_bits);
  1362. return smartlist_get(sl, i);
  1363. }
  1364. /** Choose a random element of router list <b>sl</b>, weighted by
  1365. * the advertised bandwidth of each router.
  1366. */
  1367. routerinfo_t *
  1368. routerlist_sl_choose_by_bandwidth(smartlist_t *sl,
  1369. bandwidth_weight_rule_t rule)
  1370. {
  1371. return smartlist_choose_by_bandwidth(sl, rule, 0);
  1372. }
  1373. /** Choose a random element of status list <b>sl</b>, weighted by
  1374. * the advertised bandwidth of each status.
  1375. */
  1376. routerstatus_t *
  1377. routerstatus_sl_choose_by_bandwidth(smartlist_t *sl)
  1378. {
  1379. /* We are choosing neither exit nor guard here. Weight accordingly. */
  1380. return smartlist_choose_by_bandwidth(sl, NO_WEIGHTING, 1);
  1381. }
  1382. /** Return a random running router from the routerlist. If any node
  1383. * named in <b>preferred</b> is available, pick one of those. Never
  1384. * pick a node named in <b>excluded</b>, or whose routerinfo is in
  1385. * <b>excludedsmartlist</b>, even if they are the only nodes
  1386. * available. If <b>strict</b> is true, never pick any node besides
  1387. * those in <b>preferred</b>.
  1388. * If <b>need_uptime</b> is non-zero and any router has more than
  1389. * a minimum uptime, return one of those.
  1390. * If <b>need_capacity</b> is non-zero, weight your choice by the
  1391. * advertised capacity of each router.
  1392. * If ! <b>allow_invalid</b>, consider only Valid routers.
  1393. * If <b>need_guard</b>, consider only Guard routers.
  1394. * If <b>weight_for_exit</b>, we weight bandwidths as if picking an exit node,
  1395. * otherwise we weight bandwidths for picking a relay node (that is, possibly
  1396. * discounting exit nodes).
  1397. */
  1398. routerinfo_t *
  1399. router_choose_random_node(const char *preferred,
  1400. const char *excluded,
  1401. smartlist_t *excludedsmartlist,
  1402. int need_uptime, int need_capacity,
  1403. int need_guard,
  1404. int allow_invalid, int strict,
  1405. int weight_for_exit)
  1406. {
  1407. smartlist_t *sl, *excludednodes;
  1408. routerinfo_t *choice = NULL;
  1409. bandwidth_weight_rule_t rule;
  1410. tor_assert(!(weight_for_exit && need_guard));
  1411. rule = weight_for_exit ? WEIGHT_FOR_EXIT :
  1412. (need_guard ? WEIGHT_FOR_GUARD : NO_WEIGHTING);
  1413. excludednodes = smartlist_create();
  1414. add_nickname_list_to_smartlist(excludednodes,excluded,0);
  1415. /* Try the preferred nodes first. Ignore need_uptime and need_capacity
  1416. * and need_guard, since the user explicitly asked for these nodes. */
  1417. if (preferred) {
  1418. sl = smartlist_create();
  1419. add_nickname_list_to_smartlist(sl,preferred,1);
  1420. smartlist_subtract(sl,excludednodes);
  1421. if (excludedsmartlist)
  1422. smartlist_subtract(sl,excludedsmartlist);
  1423. choice = smartlist_choose(sl);
  1424. smartlist_free(sl);
  1425. }
  1426. if (!choice && !strict) {
  1427. /* Then give up on our preferred choices: any node
  1428. * will do that has the required attributes. */
  1429. sl = smartlist_create();
  1430. router_add_running_routers_to_smartlist(sl, allow_invalid,
  1431. need_uptime, need_capacity,
  1432. need_guard);
  1433. smartlist_subtract(sl,excludednodes);
  1434. if (excludedsmartlist)
  1435. smartlist_subtract(sl,excludedsmartlist);
  1436. if (need_capacity || need_guard)
  1437. choice = routerlist_sl_choose_by_bandwidth(sl, rule);
  1438. else
  1439. choice = smartlist_choose(sl);
  1440. smartlist_free(sl);
  1441. if (!choice && (need_uptime || need_capacity || need_guard)) {
  1442. /* try once more -- recurse but with fewer restrictions. */
  1443. log_info(LD_CIRC,
  1444. "We couldn't find any live%s%s%s routers; falling back "
  1445. "to list of all routers.",
  1446. need_capacity?", fast":"",
  1447. need_uptime?", stable":"",
  1448. need_guard?", guard":"");
  1449. choice = router_choose_random_node(
  1450. NULL, excluded, excludedsmartlist,
  1451. 0, 0, 0, allow_invalid, 0, weight_for_exit);
  1452. }
  1453. }
  1454. smartlist_free(excludednodes);
  1455. if (!choice) {
  1456. if (strict) {
  1457. log_warn(LD_CIRC, "All preferred nodes were down when trying to choose "
  1458. "node, and the Strict[...]Nodes option is set. Failing.");
  1459. } else {
  1460. log_warn(LD_CIRC,
  1461. "No available nodes when trying to choose node. Failing.");
  1462. }
  1463. }
  1464. return choice;
  1465. }
  1466. /** Return true iff the digest of <b>router</b>'s identity key,
  1467. * encoded in hexadecimal, matches <b>hexdigest</b> (which is
  1468. * optionally prefixed with a single dollar sign). Return false if
  1469. * <b>hexdigest</b> is malformed, or it doesn't match. */
  1470. static INLINE int
  1471. router_hex_digest_matches(routerinfo_t *router, const char *hexdigest)
  1472. {
  1473. char digest[DIGEST_LEN];
  1474. size_t len;
  1475. tor_assert(hexdigest);
  1476. if (hexdigest[0] == '$')
  1477. ++hexdigest;
  1478. len = strlen(hexdigest);
  1479. if (len < HEX_DIGEST_LEN)
  1480. return 0;
  1481. else if (len > HEX_DIGEST_LEN &&
  1482. (hexdigest[HEX_DIGEST_LEN] == '=' ||
  1483. hexdigest[HEX_DIGEST_LEN] == '~')) {
  1484. if (strcasecmp(hexdigest+HEX_DIGEST_LEN+1, router->nickname))
  1485. return 0;
  1486. if (hexdigest[HEX_DIGEST_LEN] == '=' && !router->is_named)
  1487. return 0;
  1488. }
  1489. if (base16_decode(digest, DIGEST_LEN, hexdigest, HEX_DIGEST_LEN)<0)
  1490. return 0;
  1491. return (!memcmp(digest, router->cache_info.identity_digest, DIGEST_LEN));
  1492. }
  1493. /** Return true if <b>router</b>'s nickname matches <b>nickname</b>
  1494. * (case-insensitive), or if <b>router's</b> identity key digest
  1495. * matches a hexadecimal value stored in <b>nickname</b>. Return
  1496. * false otherwise. */
  1497. static int
  1498. router_nickname_matches(routerinfo_t *router, const char *nickname)
  1499. {
  1500. if (nickname[0]!='$' && !strcasecmp(router->nickname, nickname))
  1501. return 1;
  1502. return router_hex_digest_matches(router, nickname);
  1503. }
  1504. /** Return the router in our routerlist whose (case-insensitive)
  1505. * nickname or (case-sensitive) hexadecimal key digest is
  1506. * <b>nickname</b>. Return NULL if no such router is known.
  1507. */
  1508. routerinfo_t *
  1509. router_get_by_nickname(const char *nickname, int warn_if_unnamed)
  1510. {
  1511. int maybedigest;
  1512. char digest[DIGEST_LEN];
  1513. routerinfo_t *best_match=NULL;
  1514. int n_matches = 0;
  1515. const char *named_digest = NULL;
  1516. tor_assert(nickname);
  1517. if (!routerlist)
  1518. return NULL;
  1519. if (nickname[0] == '$')
  1520. return router_get_by_hexdigest(nickname);
  1521. if (!strcasecmp(nickname, UNNAMED_ROUTER_NICKNAME))
  1522. return NULL;
  1523. if (server_mode(get_options()) &&
  1524. !strcasecmp(nickname, get_options()->Nickname))
  1525. return router_get_my_routerinfo();
  1526. maybedigest = (strlen(nickname) >= HEX_DIGEST_LEN) &&
  1527. (base16_decode(digest,DIGEST_LEN,nickname,HEX_DIGEST_LEN) == 0);
  1528. if ((named_digest = networkstatus_get_router_digest_by_nickname(nickname))) {
  1529. return rimap_get(routerlist->identity_map, named_digest);
  1530. }
  1531. /* If we reach this point, there's no canonical value for the nickname. */
  1532. SMARTLIST_FOREACH(routerlist->routers, routerinfo_t *, router,
  1533. {
  1534. if (!strcasecmp(router->nickname, nickname)) {
  1535. ++n_matches;
  1536. if (n_matches <= 1 || router->is_running)
  1537. best_match = router;
  1538. } else if (maybedigest &&
  1539. !memcmp(digest, router->cache_info.identity_digest, DIGEST_LEN)
  1540. ) {
  1541. if (router_hex_digest_matches(router, nickname))
  1542. return router;
  1543. else
  1544. best_match = router; // XXXX020 NM not exactly right.
  1545. }
  1546. });
  1547. if (best_match) {
  1548. if (warn_if_unnamed && n_matches > 1) {
  1549. smartlist_t *fps = smartlist_create();
  1550. int any_unwarned = 0;
  1551. SMARTLIST_FOREACH(routerlist->routers, routerinfo_t *, router,
  1552. {
  1553. routerstatus_t *rs;
  1554. char *desc;
  1555. size_t dlen;
  1556. char fp[HEX_DIGEST_LEN+1];
  1557. if (strcasecmp(router->nickname, nickname))
  1558. continue;
  1559. rs = router_get_consensus_status_by_id(
  1560. router->cache_info.identity_digest);
  1561. if (rs && !rs->name_lookup_warned) {
  1562. rs->name_lookup_warned = 1;
  1563. any_unwarned = 1;
  1564. }
  1565. base16_encode(fp, sizeof(fp),
  1566. router->cache_info.identity_digest, DIGEST_LEN);
  1567. dlen = 32 + HEX_DIGEST_LEN + strlen(router->address);
  1568. desc = tor_malloc(dlen);
  1569. tor_snprintf(desc, dlen, "\"$%s\" for the one at %s:%d",
  1570. fp, router->address, router->or_port);
  1571. smartlist_add(fps, desc);
  1572. });
  1573. if (any_unwarned) {
  1574. char *alternatives = smartlist_join_strings(fps, "; ",0,NULL);
  1575. log_warn(LD_CONFIG,
  1576. "There are multiple matches for the nickname \"%s\","
  1577. " but none is listed as named by the directory authorities. "
  1578. "Choosing one arbitrarily. If you meant one in particular, "
  1579. "you should say %s.", nickname, alternatives);
  1580. tor_free(alternatives);
  1581. }
  1582. SMARTLIST_FOREACH(fps, char *, cp, tor_free(cp));
  1583. smartlist_free(fps);
  1584. } else if (warn_if_unnamed) {
  1585. routerstatus_t *rs = router_get_consensus_status_by_id(
  1586. best_match->cache_info.identity_digest);
  1587. if (rs && !rs->name_lookup_warned) {
  1588. char fp[HEX_DIGEST_LEN+1];
  1589. base16_encode(fp, sizeof(fp),
  1590. best_match->cache_info.identity_digest, DIGEST_LEN);
  1591. log_warn(LD_CONFIG, "You specified a server \"%s\" by name, but this "
  1592. "name is not registered, so it could be used by any server, "
  1593. "not just the one you meant. "
  1594. "To make sure you get the same server in the future, refer to "
  1595. "it by key, as \"$%s\".", nickname, fp);
  1596. rs->name_lookup_warned = 1;
  1597. }
  1598. }
  1599. return best_match;
  1600. }
  1601. return NULL;
  1602. }
  1603. /** Try to find a routerinfo for <b>digest</b>. If we don't have one,
  1604. * return 1. If we do, ask tor_version_as_new_as() for the answer.
  1605. */
  1606. int
  1607. router_digest_version_as_new_as(const char *digest, const char *cutoff)
  1608. {
  1609. routerinfo_t *router = router_get_by_digest(digest);
  1610. if (!router)
  1611. return 1;
  1612. return tor_version_as_new_as(router->platform, cutoff);
  1613. }
  1614. /** Return true iff <b>digest</b> is the digest of the identity key of a
  1615. * trusted directory matching at least one bit of <b>type</b>. If <b>type</b>
  1616. * is zero, any authority is okay. */
  1617. int
  1618. router_digest_is_trusted_dir_type(const char *digest, authority_type_t type)
  1619. {
  1620. if (!trusted_dir_servers)
  1621. return 0;
  1622. if (authdir_mode(get_options()) && router_digest_is_me(digest))
  1623. return 1;
  1624. SMARTLIST_FOREACH(trusted_dir_servers, trusted_dir_server_t *, ent,
  1625. if (!memcmp(digest, ent->digest, DIGEST_LEN)) {
  1626. return (!type) || ((type & ent->type) != 0);
  1627. });
  1628. return 0;
  1629. }
  1630. /** Return true iff <b>addr</b> is the address of one of our trusted
  1631. * directory authorities. */
  1632. int
  1633. router_addr_is_trusted_dir(uint32_t addr)
  1634. {
  1635. if (!trusted_dir_servers)
  1636. return 0;
  1637. SMARTLIST_FOREACH(trusted_dir_servers, trusted_dir_server_t *, ent,
  1638. if (ent->addr == addr)
  1639. return 1;
  1640. );
  1641. return 0;
  1642. }
  1643. /** If hexdigest is correctly formed, base16_decode it into
  1644. * digest, which must have DIGEST_LEN space in it.
  1645. * Return 0 on success, -1 on failure.
  1646. */
  1647. int
  1648. hexdigest_to_digest(const char *hexdigest, char *digest)
  1649. {
  1650. if (hexdigest[0]=='$')
  1651. ++hexdigest;
  1652. if (strlen(hexdigest) < HEX_DIGEST_LEN ||
  1653. base16_decode(digest,DIGEST_LEN,hexdigest,HEX_DIGEST_LEN) < 0)
  1654. return -1;
  1655. return 0;
  1656. }
  1657. /** Return the router in our routerlist whose hexadecimal key digest
  1658. * is <b>hexdigest</b>. Return NULL if no such router is known. */
  1659. routerinfo_t *
  1660. router_get_by_hexdigest(const char *hexdigest)
  1661. {
  1662. char digest[DIGEST_LEN];
  1663. size_t len;
  1664. routerinfo_t *ri;
  1665. tor_assert(hexdigest);
  1666. if (!routerlist)
  1667. return NULL;
  1668. if (hexdigest[0]=='$')
  1669. ++hexdigest;
  1670. len = strlen(hexdigest);
  1671. if (hexdigest_to_digest(hexdigest, digest) < 0)
  1672. return NULL;
  1673. ri = router_get_by_digest(digest);
  1674. if (len > HEX_DIGEST_LEN) {
  1675. if (hexdigest[HEX_DIGEST_LEN] == '=') {
  1676. if (strcasecmp(ri->nickname, hexdigest+HEX_DIGEST_LEN+1) ||
  1677. !ri->is_named)
  1678. return NULL;
  1679. } else if (hexdigest[HEX_DIGEST_LEN] == '~') {
  1680. if (strcasecmp(ri->nickname, hexdigest+HEX_DIGEST_LEN+1))
  1681. return NULL;
  1682. } else {
  1683. return NULL;
  1684. }
  1685. }
  1686. return ri;
  1687. }
  1688. /** Return the router in our routerlist whose 20-byte key digest
  1689. * is <b>digest</b>. Return NULL if no such router is known. */
  1690. routerinfo_t *
  1691. router_get_by_digest(const char *digest)
  1692. {
  1693. tor_assert(digest);
  1694. if (!routerlist) return NULL;
  1695. // routerlist_assert_ok(routerlist);
  1696. return rimap_get(routerlist->identity_map, digest);
  1697. }
  1698. /** Return the router in our routerlist whose 20-byte descriptor
  1699. * is <b>digest</b>. Return NULL if no such router is known. */
  1700. signed_descriptor_t *
  1701. router_get_by_descriptor_digest(const char *digest)
  1702. {
  1703. tor_assert(digest);
  1704. if (!routerlist) return NULL;
  1705. return sdmap_get(routerlist->desc_digest_map, digest);
  1706. }
  1707. /** Return the signed descriptor for the router in our routerlist whose
  1708. * 20-byte extra-info digest is <b>digest</b>. Return NULL if no such router
  1709. * is known. */
  1710. signed_descriptor_t *
  1711. router_get_by_extrainfo_digest(const char *digest)
  1712. {
  1713. tor_assert(digest);
  1714. if (!routerlist) return NULL;
  1715. return sdmap_get(routerlist->desc_by_eid_map, digest);
  1716. }
  1717. /** Return the signed descriptor for the extrainfo_t in our routerlist whose
  1718. * extra-info-digest is <b>digest</b>. Return NULL if no such extra-info
  1719. * document is known. */
  1720. signed_descriptor_t *
  1721. extrainfo_get_by_descriptor_digest(const char *digest)
  1722. {
  1723. extrainfo_t *ei;
  1724. tor_assert(digest);
  1725. if (!routerlist) return NULL;
  1726. ei = eimap_get(routerlist->extra_info_map, digest);
  1727. return ei ? &ei->cache_info : NULL;
  1728. }
  1729. /** Return a pointer to the signed textual representation of a descriptor.
  1730. * The returned string is not guaranteed to be NUL-terminated: the string's
  1731. * length will be in desc-\>signed_descriptor_len.
  1732. *
  1733. * If with_annotations is set, the returned string will include the annotations
  1734. * (if any) preceding the descriptor. This will increase the length of the
  1735. * string by desc-\>annotations_len.
  1736. *
  1737. * The caller must not free the string returned.
  1738. */
  1739. static const char *
  1740. signed_descriptor_get_body_impl(signed_descriptor_t *desc,
  1741. int with_annotations)
  1742. {
  1743. const char *r = NULL;
  1744. size_t len = desc->signed_descriptor_len;
  1745. off_t offset = desc->saved_offset;
  1746. if (with_annotations)
  1747. len += desc->annotations_len;
  1748. else
  1749. offset += desc->annotations_len;
  1750. tor_assert(len > 32);
  1751. if (desc->saved_location == SAVED_IN_CACHE && routerlist) {
  1752. desc_store_t *store = desc_get_store(router_get_routerlist(), desc);
  1753. if (store && store->mmap) {
  1754. tor_assert(desc->saved_offset + len <= store->mmap->size);
  1755. r = store->mmap->data + offset;
  1756. }
  1757. }
  1758. if (!r) /* no mmap, or not in cache. */
  1759. r = desc->signed_descriptor_body +
  1760. (with_annotations ? 0 : desc->annotations_len);
  1761. tor_assert(r);
  1762. if (!with_annotations) {
  1763. if (memcmp("router ", r, 7) && memcmp("extra-info ", r, 11)) {
  1764. log_err(LD_DIR, "descriptor at %p begins with unexpected string %s",
  1765. desc, tor_strndup(r, 64));
  1766. }
  1767. tor_assert(!memcmp("router ", r, 7) || !memcmp("extra-info ", r, 11));
  1768. }
  1769. return r;
  1770. }
  1771. /** Return a pointer to the signed textual representation of a descriptor.
  1772. * The returned string is not guaranteed to be NUL-terminated: the string's
  1773. * length will be in desc-\>signed_descriptor_len.
  1774. *
  1775. * The caller must not free the string returned.
  1776. */
  1777. const char *
  1778. signed_descriptor_get_body(signed_descriptor_t *desc)
  1779. {
  1780. return signed_descriptor_get_body_impl(desc, 0);
  1781. }
  1782. /** Return the current list of all known routers. */
  1783. routerlist_t *
  1784. router_get_routerlist(void)
  1785. {
  1786. if (PREDICT_UNLIKELY(!routerlist)) {
  1787. routerlist = tor_malloc_zero(sizeof(routerlist_t));
  1788. routerlist->routers = smartlist_create();
  1789. routerlist->old_routers = smartlist_create();
  1790. routerlist->identity_map = rimap_new();
  1791. routerlist->desc_digest_map = sdmap_new();
  1792. routerlist->desc_by_eid_map = sdmap_new();
  1793. routerlist->extra_info_map = eimap_new();
  1794. routerlist->desc_store.fname_base = "cached-descriptors";
  1795. routerlist->desc_store.fname_alt_base = "cached-routers";
  1796. routerlist->extrainfo_store.fname_base = "cached-extrainfo";
  1797. routerlist->desc_store.type = ROUTER_STORE;
  1798. routerlist->extrainfo_store.type = EXTRAINFO_STORE;
  1799. routerlist->desc_store.description = "router descriptors";
  1800. routerlist->extrainfo_store.description = "extra-info documents";
  1801. }
  1802. return routerlist;
  1803. }
  1804. /** Free all storage held by <b>router</b>. */
  1805. void
  1806. routerinfo_free(routerinfo_t *router)
  1807. {
  1808. if (!router)
  1809. return;
  1810. tor_free(router->cache_info.signed_descriptor_body);
  1811. tor_free(router->address);
  1812. tor_free(router->nickname);
  1813. tor_free(router->platform);
  1814. tor_free(router->contact_info);
  1815. if (router->onion_pkey)
  1816. crypto_free_pk_env(router->onion_pkey);
  1817. if (router->identity_pkey)
  1818. crypto_free_pk_env(router->identity_pkey);
  1819. if (router->declared_family) {
  1820. SMARTLIST_FOREACH(router->declared_family, char *, s, tor_free(s));
  1821. smartlist_free(router->declared_family);
  1822. }
  1823. addr_policy_free(router->exit_policy);
  1824. /* XXXX020 Remove once 414/417 is fixed. But I have a hunch... */
  1825. memset(router, 77, sizeof(routerinfo_t));
  1826. tor_free(router);
  1827. }
  1828. /** Release all storage held by <b>extrainfo</b> */
  1829. void
  1830. extrainfo_free(extrainfo_t *extrainfo)
  1831. {
  1832. if (!extrainfo)
  1833. return;
  1834. tor_free(extrainfo->cache_info.signed_descriptor_body);
  1835. tor_free(extrainfo->pending_sig);
  1836. /* XXXX020 remove this once more bugs go away. */
  1837. memset(extrainfo, 88, sizeof(extrainfo_t)); /* debug bad memory usage */
  1838. tor_free(extrainfo);
  1839. }
  1840. /** Release storage held by <b>sd</b>. */
  1841. static void
  1842. signed_descriptor_free(signed_descriptor_t *sd)
  1843. {
  1844. tor_free(sd->signed_descriptor_body);
  1845. /* XXXX020 remove this once more bugs go away. */
  1846. memset(sd, 99, sizeof(signed_descriptor_t)); /* Debug bad mem usage */
  1847. tor_free(sd);
  1848. }
  1849. /** Extract a signed_descriptor_t from a routerinfo, and free the routerinfo.
  1850. */
  1851. static signed_descriptor_t *
  1852. signed_descriptor_from_routerinfo(routerinfo_t *ri)
  1853. {
  1854. signed_descriptor_t *sd = tor_malloc_zero(sizeof(signed_descriptor_t));
  1855. memcpy(sd, &(ri->cache_info), sizeof(signed_descriptor_t));
  1856. ri->cache_info.signed_descriptor_body = NULL;
  1857. routerinfo_free(ri);
  1858. return sd;
  1859. }
  1860. /** Helper: free the storage held by the extrainfo_t in <b>e</b>. */
  1861. static void
  1862. _extrainfo_free(void *e)
  1863. {
  1864. extrainfo_free(e);
  1865. }
  1866. /** Free all storage held by a routerlist <b>rl</b>. */
  1867. void
  1868. routerlist_free(routerlist_t *rl)
  1869. {
  1870. tor_assert(rl);
  1871. rimap_free(rl->identity_map, NULL);
  1872. sdmap_free(rl->desc_digest_map, NULL);
  1873. sdmap_free(rl->desc_by_eid_map, NULL);
  1874. eimap_free(rl->extra_info_map, _extrainfo_free);
  1875. SMARTLIST_FOREACH(rl->routers, routerinfo_t *, r,
  1876. routerinfo_free(r));
  1877. SMARTLIST_FOREACH(rl->old_routers, signed_descriptor_t *, sd,
  1878. signed_descriptor_free(sd));
  1879. smartlist_free(rl->routers);
  1880. smartlist_free(rl->old_routers);
  1881. if (routerlist->desc_store.mmap)
  1882. tor_munmap_file(routerlist->desc_store.mmap);
  1883. if (routerlist->extrainfo_store.mmap)
  1884. tor_munmap_file(routerlist->extrainfo_store.mmap);
  1885. tor_free(rl);
  1886. router_dir_info_changed();
  1887. }
  1888. /** Log information about how much memory is being used for routerlist,
  1889. * at log level <b>severity</b>. */
  1890. void
  1891. dump_routerlist_mem_usage(int severity)
  1892. {
  1893. uint64_t livedescs = 0;
  1894. uint64_t olddescs = 0;
  1895. if (!routerlist)
  1896. return;
  1897. SMARTLIST_FOREACH(routerlist->routers, routerinfo_t *, r,
  1898. livedescs += r->cache_info.signed_descriptor_len);
  1899. SMARTLIST_FOREACH(routerlist->old_routers, signed_descriptor_t *, sd,
  1900. olddescs += sd->signed_descriptor_len);
  1901. log(severity, LD_GENERAL,
  1902. "In %d live descriptors: "U64_FORMAT" bytes. "
  1903. "In %d old descriptors: "U64_FORMAT" bytes.",
  1904. smartlist_len(routerlist->routers), U64_PRINTF_ARG(livedescs),
  1905. smartlist_len(routerlist->old_routers), U64_PRINTF_ARG(olddescs));
  1906. }
  1907. #if 0
  1908. /** Return non-zero if we have a lot of extra descriptors in our
  1909. * routerlist, and should get rid of some of them. Else return 0.
  1910. *
  1911. * We should be careful to not return true too eagerly, since we
  1912. * could churn. By using "+1" below, we make sure this function
  1913. * only returns true at most every smartlist_len(rl-\>routers)
  1914. * new descriptors.
  1915. */
  1916. static INLINE int
  1917. routerlist_is_overfull(routerlist_t *rl)
  1918. {
  1919. /*XXXX020 no longer wholly logical.*/
  1920. if (dirserver_mode(get_options())) {
  1921. return smartlist_len(rl->old_routers) > smartlist_len(rl->routers)*5;
  1922. } else {
  1923. return smartlist_len(rl->old_routers) > smartlist_len(rl->routers)*2;
  1924. }
  1925. }
  1926. #endif
  1927. static INLINE int
  1928. _routerlist_find_elt(smartlist_t *sl, void *ri, int idx)
  1929. {
  1930. if (idx < 0) {
  1931. idx = -1;
  1932. SMARTLIST_FOREACH(sl, routerinfo_t *, r,
  1933. if (r == ri) {
  1934. idx = r_sl_idx;
  1935. break;
  1936. });
  1937. } else {
  1938. tor_assert(idx < smartlist_len(sl));
  1939. tor_assert(smartlist_get(sl, idx) == ri);
  1940. };
  1941. return idx;
  1942. }
  1943. /** Insert an item <b>ri</b> into the routerlist <b>rl</b>, updating indices
  1944. * as needed. There must be no previous member of <b>rl</b> with the same
  1945. * identity digest as <b>ri</b>: If there is, call routerlist_replace
  1946. * instead.
  1947. */
  1948. static void
  1949. routerlist_insert(routerlist_t *rl, routerinfo_t *ri)
  1950. {
  1951. routerinfo_t *ri_old;
  1952. {
  1953. /* XXXX020 remove this code once bug 417/404 is fixed. */
  1954. routerinfo_t *ri_generated = router_get_my_routerinfo();
  1955. tor_assert(ri_generated != ri);
  1956. }
  1957. tor_assert(ri->routerlist_index == -1);
  1958. ri_old = rimap_set(rl->identity_map, ri->cache_info.identity_digest, ri);
  1959. tor_assert(!ri_old);
  1960. sdmap_set(rl->desc_digest_map, ri->cache_info.signed_descriptor_digest,
  1961. &(ri->cache_info));
  1962. if (!tor_digest_is_zero(ri->cache_info.extra_info_digest))
  1963. sdmap_set(rl->desc_by_eid_map, ri->cache_info.extra_info_digest,
  1964. &ri->cache_info);
  1965. smartlist_add(rl->routers, ri);
  1966. ri->routerlist_index = smartlist_len(rl->routers) - 1;
  1967. router_dir_info_changed();
  1968. #ifdef DEBUG_ROUTERLIST
  1969. routerlist_assert_ok(rl);
  1970. #endif
  1971. }
  1972. /** Adds the extrainfo_t <b>ei</b> to the routerlist <b>rl</b>, if there is a
  1973. * corresponding router in rl-\>routers or rl-\>old_routers. Return true iff
  1974. * we actually inserted <b>ei</b>. Free <b>ei</b> if it isn't inserted. */
  1975. static int
  1976. extrainfo_insert(routerlist_t *rl, extrainfo_t *ei)
  1977. {
  1978. int r = 0;
  1979. routerinfo_t *ri = rimap_get(rl->identity_map,
  1980. ei->cache_info.identity_digest);
  1981. signed_descriptor_t *sd;
  1982. extrainfo_t *ei_tmp;
  1983. {
  1984. /* XXXX020 remove this code once bug 417/404 is fixed. */
  1985. extrainfo_t *ei_generated = router_get_my_extrainfo();
  1986. tor_assert(ei_generated != ei);
  1987. }
  1988. if (!ri) {
  1989. /* This router is unknown; we can't even verify the signature. Give up.*/
  1990. goto done;
  1991. }
  1992. if (routerinfo_incompatible_with_extrainfo(ri, ei, NULL)) {
  1993. if (ei->bad_sig) /* If the signature didn't check, it's just wrong. */
  1994. goto done;
  1995. sd = sdmap_get(rl->desc_by_eid_map,
  1996. ei->cache_info.signed_descriptor_digest);
  1997. if (!sd ||
  1998. memcmp(sd->identity_digest, ei->cache_info.identity_digest,
  1999. DIGEST_LEN) ||
  2000. sd->published_on != ei->cache_info.published_on)
  2001. goto done;
  2002. }
  2003. /* Okay, if we make it here, we definitely have a router corresponding to
  2004. * this extrainfo. */
  2005. ei_tmp = eimap_set(rl->extra_info_map,
  2006. ei->cache_info.signed_descriptor_digest,
  2007. ei);
  2008. r = 1;
  2009. if (ei_tmp) {
  2010. rl->extrainfo_store.bytes_dropped +=
  2011. ei_tmp->cache_info.signed_descriptor_len;
  2012. extrainfo_free(ei_tmp);
  2013. }
  2014. done:
  2015. if (r == 0)
  2016. extrainfo_free(ei);
  2017. #ifdef DEBUG_ROUTERLIST
  2018. routerlist_assert_ok(rl);
  2019. #endif
  2020. return r;
  2021. }
  2022. #define should_cache_old_descriptors() dirserver_mode(get_options())
  2023. /** If we're a directory cache and routerlist <b>rl</b> doesn't have
  2024. * a copy of router <b>ri</b> yet, add it to the list of old (not
  2025. * recommended but still served) descriptors. Else free it. */
  2026. static void
  2027. routerlist_insert_old(routerlist_t *rl, routerinfo_t *ri)
  2028. {
  2029. {
  2030. /* XXXX020 remove this code once bug 417/404 is fixed. */
  2031. routerinfo_t *ri_generated = router_get_my_routerinfo();
  2032. tor_assert(ri_generated != ri);
  2033. }
  2034. tor_assert(ri->routerlist_index == -1);
  2035. if (should_cache_old_descriptors() &&
  2036. ri->purpose == ROUTER_PURPOSE_GENERAL &&
  2037. !sdmap_get(rl->desc_digest_map,
  2038. ri->cache_info.signed_descriptor_digest)) {
  2039. signed_descriptor_t *sd = signed_descriptor_from_routerinfo(ri);
  2040. sdmap_set(rl->desc_digest_map, sd->signed_descriptor_digest, sd);
  2041. smartlist_add(rl->old_routers, sd);
  2042. if (!tor_digest_is_zero(sd->extra_info_digest))
  2043. sdmap_set(rl->desc_by_eid_map, sd->extra_info_digest, sd);
  2044. } else {
  2045. routerinfo_free(ri);
  2046. }
  2047. #ifdef DEBUG_ROUTERLIST
  2048. routerlist_assert_ok(rl);
  2049. #endif
  2050. }
  2051. /** Remove an item <b>ri</b> from the routerlist <b>rl</b>, updating indices
  2052. * as needed. If <b>idx</b> is nonnegative and smartlist_get(rl-&gt;routers,
  2053. * idx) == ri, we don't need to do a linear search over the list to decide
  2054. * which to remove. We fill the gap in rl-&gt;routers with a later element in
  2055. * the list, if any exists. <b>ri</b> is freed.
  2056. *
  2057. * If <b>make_old</b> is true, instead of deleting the router, we try adding
  2058. * it to rl-&gt;old_routers. */
  2059. void
  2060. routerlist_remove(routerlist_t *rl, routerinfo_t *ri, int make_old)
  2061. {
  2062. routerinfo_t *ri_tmp;
  2063. extrainfo_t *ei_tmp;
  2064. int idx = ri->routerlist_index;
  2065. tor_assert(0 <= idx && idx < smartlist_len(rl->routers));
  2066. tor_assert(smartlist_get(rl->routers, idx) == ri);
  2067. ri->routerlist_index = -1;
  2068. smartlist_del(rl->routers, idx);
  2069. if (idx < smartlist_len(rl->routers)) {
  2070. routerinfo_t *r = smartlist_get(rl->routers, idx);
  2071. r->routerlist_index = idx;
  2072. }
  2073. ri_tmp = rimap_remove(rl->identity_map, ri->cache_info.identity_digest);
  2074. router_dir_info_changed();
  2075. tor_assert(ri_tmp == ri);
  2076. if (make_old && should_cache_old_descriptors() &&
  2077. ri->purpose == ROUTER_PURPOSE_GENERAL) {
  2078. signed_descriptor_t *sd;
  2079. sd = signed_descriptor_from_routerinfo(ri);
  2080. smartlist_add(rl->old_routers, sd);
  2081. sdmap_set(rl->desc_digest_map, sd->signed_descriptor_digest, sd);
  2082. if (!tor_digest_is_zero(sd->extra_info_digest))
  2083. sdmap_set(rl->desc_by_eid_map, sd->extra_info_digest, sd);
  2084. } else {
  2085. signed_descriptor_t *sd_tmp;
  2086. desc_store_t *store = router_get_store(rl, ri);
  2087. sd_tmp = sdmap_remove(rl->desc_digest_map,
  2088. ri->cache_info.signed_descriptor_digest);
  2089. tor_assert(sd_tmp == &(ri->cache_info));
  2090. if (store)
  2091. store->bytes_dropped += ri->cache_info.signed_descriptor_len;
  2092. ei_tmp = eimap_remove(rl->extra_info_map,
  2093. ri->cache_info.extra_info_digest);
  2094. if (ei_tmp) {
  2095. rl->extrainfo_store.bytes_dropped +=
  2096. ei_tmp->cache_info.signed_descriptor_len;
  2097. extrainfo_free(ei_tmp);
  2098. }
  2099. if (!tor_digest_is_zero(ri->cache_info.extra_info_digest))
  2100. sdmap_remove(rl->desc_by_eid_map, ri->cache_info.extra_info_digest);
  2101. routerinfo_free(ri);
  2102. }
  2103. #ifdef DEBUG_ROUTERLIST
  2104. routerlist_assert_ok(rl);
  2105. #endif
  2106. }
  2107. /** Remove a signed_descriptor_t <b>sd</b> from <b>rl</b>-\>old_routers, and
  2108. * adjust <b>rl</b> as appropriate. <b>idx</i> is -1, or the index of
  2109. * <b>sd</b>. */
  2110. static void
  2111. routerlist_remove_old(routerlist_t *rl, signed_descriptor_t *sd, int idx)
  2112. {
  2113. signed_descriptor_t *sd_tmp;
  2114. extrainfo_t *ei_tmp;
  2115. desc_store_t *store;
  2116. tor_assert(0 <= idx && idx < smartlist_len(rl->old_routers));
  2117. tor_assert(smartlist_get(rl->old_routers, idx) == sd);
  2118. smartlist_del(rl->old_routers, idx);
  2119. sd_tmp = sdmap_remove(rl->desc_digest_map,
  2120. sd->signed_descriptor_digest);
  2121. tor_assert(sd_tmp == sd);
  2122. store = desc_get_store(rl, sd);
  2123. if (store)
  2124. store->bytes_dropped += sd->signed_descriptor_len;
  2125. ei_tmp = eimap_remove(rl->extra_info_map,
  2126. sd->extra_info_digest);
  2127. if (ei_tmp) {
  2128. rl->extrainfo_store.bytes_dropped +=
  2129. ei_tmp->cache_info.signed_descriptor_len;
  2130. extrainfo_free(ei_tmp);
  2131. }
  2132. if (!tor_digest_is_zero(sd->extra_info_digest))
  2133. sdmap_remove(rl->desc_by_eid_map, sd->extra_info_digest);
  2134. signed_descriptor_free(sd);
  2135. #ifdef DEBUG_ROUTERLIST
  2136. routerlist_assert_ok(rl);
  2137. #endif
  2138. }
  2139. /** Remove <b>ri_old</b> from the routerlist <b>rl</b>, and replace it with
  2140. * <b>ri_new</b>, updating all index info. If <b>idx</b> is nonnegative and
  2141. * smartlist_get(rl-&gt;routers, idx) == ri, we don't need to do a linear
  2142. * search over the list to decide which to remove. We put ri_new in the same
  2143. * index as ri_old, if possible. ri is freed as appropriate.
  2144. *
  2145. * If <b>make_old</b> is true, instead of deleting the router, we try adding
  2146. * it to rl-&gt;old_routers. */
  2147. static void
  2148. routerlist_replace(routerlist_t *rl, routerinfo_t *ri_old,
  2149. routerinfo_t *ri_new)
  2150. {
  2151. int idx;
  2152. routerinfo_t *ri_tmp;
  2153. extrainfo_t *ei_tmp;
  2154. {
  2155. /* XXXX020 remove this code once bug 417/404 is fixed. */
  2156. routerinfo_t *ri_generated = router_get_my_routerinfo();
  2157. tor_assert(ri_generated != ri_new);
  2158. }
  2159. tor_assert(ri_old != ri_new);
  2160. tor_assert(ri_new->routerlist_index == -1);
  2161. idx = ri_old->routerlist_index;
  2162. tor_assert(0 <= idx && idx < smartlist_len(rl->routers));
  2163. tor_assert(smartlist_get(rl->routers, idx) == ri_old);
  2164. router_dir_info_changed();
  2165. if (idx >= 0) {
  2166. smartlist_set(rl->routers, idx, ri_new);
  2167. ri_old->routerlist_index = -1;
  2168. ri_new->routerlist_index = idx;
  2169. /* Check that ri_old is not in rl->routers anymore: */
  2170. tor_assert( _routerlist_find_elt(rl->routers, ri_old, -1) == -1 );
  2171. } else {
  2172. log_warn(LD_BUG, "Appending entry from routerlist_replace.");
  2173. routerlist_insert(rl, ri_new);
  2174. return;
  2175. }
  2176. if (memcmp(ri_old->cache_info.identity_digest,
  2177. ri_new->cache_info.identity_digest, DIGEST_LEN)) {
  2178. /* digests don't match; digestmap_set won't replace */
  2179. rimap_remove(rl->identity_map, ri_old->cache_info.identity_digest);
  2180. }
  2181. ri_tmp = rimap_set(rl->identity_map,
  2182. ri_new->cache_info.identity_digest, ri_new);
  2183. tor_assert(!ri_tmp || ri_tmp == ri_old);
  2184. sdmap_set(rl->desc_digest_map,
  2185. ri_new->cache_info.signed_descriptor_digest,
  2186. &(ri_new->cache_info));
  2187. if (!tor_digest_is_zero(ri_new->cache_info.extra_info_digest)) {
  2188. sdmap_set(rl->desc_by_eid_map, ri_new->cache_info.extra_info_digest,
  2189. &ri_new->cache_info);
  2190. }
  2191. if (should_cache_old_descriptors() &&
  2192. ri_old->purpose == ROUTER_PURPOSE_GENERAL) {
  2193. signed_descriptor_t *sd = signed_descriptor_from_routerinfo(ri_old);
  2194. smartlist_add(rl->old_routers, sd);
  2195. sdmap_set(rl->desc_digest_map, sd->signed_descriptor_digest, sd);
  2196. if (!tor_digest_is_zero(sd->extra_info_digest))
  2197. sdmap_set(rl->desc_by_eid_map, sd->extra_info_digest, sd);
  2198. } else {
  2199. desc_store_t *store;
  2200. if (memcmp(ri_old->cache_info.signed_descriptor_digest,
  2201. ri_new->cache_info.signed_descriptor_digest,
  2202. DIGEST_LEN)) {
  2203. /* digests don't match; digestmap_set didn't replace */
  2204. sdmap_remove(rl->desc_digest_map,
  2205. ri_old->cache_info.signed_descriptor_digest);
  2206. }
  2207. ei_tmp = eimap_remove(rl->extra_info_map,
  2208. ri_old->cache_info.extra_info_digest);
  2209. if (ei_tmp) {
  2210. rl->extrainfo_store.bytes_dropped +=
  2211. ei_tmp->cache_info.signed_descriptor_len;
  2212. extrainfo_free(ei_tmp);
  2213. }
  2214. if (!tor_digest_is_zero(ri_old->cache_info.extra_info_digest)) {
  2215. sdmap_remove(rl->desc_by_eid_map,
  2216. ri_old->cache_info.extra_info_digest);
  2217. }
  2218. store = router_get_store(rl, ri_old);
  2219. if (store)
  2220. store->bytes_dropped += ri_old->cache_info.signed_descriptor_len;
  2221. routerinfo_free(ri_old);
  2222. }
  2223. #ifdef DEBUG_ROUTERLIST
  2224. routerlist_assert_ok(rl);
  2225. #endif
  2226. }
  2227. /** Free all memory held by the routerlist module. */
  2228. void
  2229. routerlist_free_all(void)
  2230. {
  2231. if (routerlist)
  2232. routerlist_free(routerlist);
  2233. routerlist = NULL;
  2234. if (warned_nicknames) {
  2235. SMARTLIST_FOREACH(warned_nicknames, char *, cp, tor_free(cp));
  2236. smartlist_free(warned_nicknames);
  2237. warned_nicknames = NULL;
  2238. }
  2239. if (trusted_dir_servers) {
  2240. SMARTLIST_FOREACH(trusted_dir_servers, trusted_dir_server_t *, ds,
  2241. trusted_dir_server_free(ds));
  2242. smartlist_free(trusted_dir_servers);
  2243. trusted_dir_servers = NULL;
  2244. }
  2245. }
  2246. /** Forget that we have issued any router-related warnings, so that we'll
  2247. * warn again if we see the same errors. */
  2248. void
  2249. routerlist_reset_warnings(void)
  2250. {
  2251. if (!warned_nicknames)
  2252. warned_nicknames = smartlist_create();
  2253. SMARTLIST_FOREACH(warned_nicknames, char *, cp, tor_free(cp));
  2254. smartlist_clear(warned_nicknames); /* now the list is empty. */
  2255. networkstatus_reset_warnings();
  2256. }
  2257. /** Mark the router with ID <b>digest</b> as running or non-running
  2258. * in our routerlist. */
  2259. void
  2260. router_set_status(const char *digest, int up)
  2261. {
  2262. routerinfo_t *router;
  2263. routerstatus_t *status;
  2264. tor_assert(digest);
  2265. SMARTLIST_FOREACH(trusted_dir_servers, trusted_dir_server_t *, d,
  2266. if (!memcmp(d->digest, digest, DIGEST_LEN))
  2267. d->is_running = up);
  2268. router = router_get_by_digest(digest);
  2269. if (router) {
  2270. log_debug(LD_DIR,"Marking router '%s' as %s.",
  2271. router->nickname, up ? "up" : "down");
  2272. if (!up && router_is_me(router) && !we_are_hibernating())
  2273. log_warn(LD_NET, "We just marked ourself as down. Are your external "
  2274. "addresses reachable?");
  2275. router->is_running = up;
  2276. }
  2277. status = router_get_consensus_status_by_id(digest);
  2278. if (status && status->is_running != up) {
  2279. status->is_running = up;
  2280. control_event_networkstatus_changed_single(status);
  2281. }
  2282. router_dir_info_changed();
  2283. }
  2284. /** Add <b>router</b> to the routerlist, if we don't already have it. Replace
  2285. * older entries (if any) with the same key. Note: Callers should not hold
  2286. * their pointers to <b>router</b> if this function fails; <b>router</b>
  2287. * will either be inserted into the routerlist or freed. Similarly, even
  2288. * if this call succeeds, they should not hold their pointers to
  2289. * <b>router</b> after subsequent calls with other routerinfo's -- they
  2290. * might cause the original routerinfo to get freed.
  2291. *
  2292. * Returns >= 0 if the router was added; less than 0 if it was not.
  2293. *
  2294. * If we're returning non-zero, then assign to *<b>msg</b> a static string
  2295. * describing the reason for not liking the routerinfo.
  2296. *
  2297. * If the return value is less than -1, there was a problem with the
  2298. * routerinfo. If the return value is equal to -1, then the routerinfo was
  2299. * fine, but out-of-date. If the return value is equal to 1, the
  2300. * routerinfo was accepted, but we should notify the generator of the
  2301. * descriptor using the message *<b>msg</b>.
  2302. *
  2303. * If <b>from_cache</b>, this descriptor came from our disk cache. If
  2304. * <b>from_fetch</b>, we received it in response to a request we made.
  2305. * (If both are false, that means it was uploaded to us as an auth dir
  2306. * server or via the controller.)
  2307. *
  2308. * This function should be called *after*
  2309. * routers_update_status_from_consensus_networkstatus; subsequently, you
  2310. * should call router_rebuild_store and routerlist_descriptors_added.
  2311. */
  2312. int
  2313. router_add_to_routerlist(routerinfo_t *router, const char **msg,
  2314. int from_cache, int from_fetch)
  2315. {
  2316. const char *id_digest;
  2317. int authdir = authdir_mode(get_options());
  2318. int authdir_believes_valid = 0;
  2319. routerinfo_t *old_router;
  2320. /* router_have_minimum_dir_info() has side effects, so do it before we
  2321. * start the real work */
  2322. int authdir_may_warn_about_unreachable_server =
  2323. authdir && !from_cache && !from_fetch &&
  2324. router_have_minimum_dir_info();
  2325. networkstatus_vote_t *consensus = networkstatus_get_latest_consensus();
  2326. const smartlist_t *networkstatus_v2_list = networkstatus_get_v2_list();
  2327. int in_consensus = 0;
  2328. tor_assert(msg);
  2329. if (!routerlist)
  2330. router_get_routerlist();
  2331. id_digest = router->cache_info.identity_digest;
  2332. /* Make sure that we haven't already got this exact descriptor. */
  2333. if (sdmap_get(routerlist->desc_digest_map,
  2334. router->cache_info.signed_descriptor_digest)) {
  2335. log_info(LD_DIR,
  2336. "Dropping descriptor that we already have for router '%s'",
  2337. router->nickname);
  2338. *msg = "Router descriptor was not new.";
  2339. routerinfo_free(router);
  2340. return -1;
  2341. }
  2342. #if 0
  2343. if (routerlist_is_overfull(routerlist))
  2344. routerlist_remove_old_routers();
  2345. #endif
  2346. if (authdir) {
  2347. if (authdir_wants_to_reject_router(router, msg,
  2348. !from_cache && !from_fetch)) {
  2349. tor_assert(*msg);
  2350. routerinfo_free(router);
  2351. return -2;
  2352. }
  2353. authdir_believes_valid = router->is_valid;
  2354. } else if (from_fetch) {
  2355. /* Only check the descriptor digest against the network statuses when
  2356. * we are receiving in response to a fetch. */
  2357. if (!signed_desc_digest_is_recognized(&router->cache_info) &&
  2358. !routerinfo_is_a_configured_bridge(router)) {
  2359. /* We asked for it, so some networkstatus must have listed it when we
  2360. * did. Save it if we're a cache in case somebody else asks for it. */
  2361. log_info(LD_DIR,
  2362. "Received a no-longer-recognized descriptor for router '%s'",
  2363. router->nickname);
  2364. *msg = "Router descriptor is not referenced by any network-status.";
  2365. /* Only journal this desc if we'll be serving it. */
  2366. if (!from_cache && should_cache_old_descriptors())
  2367. signed_desc_append_to_journal(&router->cache_info,
  2368. router_get_store(routerlist, router));
  2369. routerlist_insert_old(routerlist, router);
  2370. return -1;
  2371. }
  2372. }
  2373. /* We no longer need a router with this descriptor digest. */
  2374. SMARTLIST_FOREACH(networkstatus_v2_list, networkstatus_v2_t *, ns,
  2375. {
  2376. routerstatus_t *rs =
  2377. networkstatus_v2_find_entry(ns, router->cache_info.identity_digest);
  2378. if (rs && !memcmp(rs->descriptor_digest,
  2379. router->cache_info.signed_descriptor_digest,
  2380. DIGEST_LEN))
  2381. rs->need_to_mirror = 0;
  2382. });
  2383. if (consensus) {
  2384. routerstatus_t *rs = networkstatus_vote_find_entry(consensus,
  2385. router->cache_info.identity_digest);
  2386. if (rs && !memcmp(rs->descriptor_digest,
  2387. router->cache_info.signed_descriptor_digest,
  2388. DIGEST_LEN)) {
  2389. in_consensus = 1;
  2390. rs->need_to_mirror = 0;
  2391. }
  2392. }
  2393. if (router->purpose == ROUTER_PURPOSE_GENERAL &&
  2394. consensus && !in_consensus && !authdir_mode(get_options())) {
  2395. /* If it's a general router not listed in the consensus, then don't
  2396. * consider replacing the latest router with it. */
  2397. if (!from_cache && should_cache_old_descriptors())
  2398. signed_desc_append_to_journal(&router->cache_info,
  2399. router_get_store(routerlist, router));
  2400. routerlist_insert_old(routerlist, router);
  2401. return -1;
  2402. }
  2403. /* If we have a router with the same identity key, choose the newer one. */
  2404. old_router = rimap_get(routerlist->identity_map,
  2405. router->cache_info.identity_digest);
  2406. if (old_router) {
  2407. if (router->cache_info.published_on <=
  2408. old_router->cache_info.published_on) {
  2409. /* Same key, but old */
  2410. log_debug(LD_DIR, "Skipping not-new descriptor for router '%s'",
  2411. router->nickname);
  2412. /* Only journal this desc if we'll be serving it. */
  2413. if (!from_cache && should_cache_old_descriptors())
  2414. signed_desc_append_to_journal(&router->cache_info,
  2415. router_get_store(routerlist, router));
  2416. routerlist_insert_old(routerlist, router);
  2417. *msg = "Router descriptor was not new.";
  2418. return -1;
  2419. } else {
  2420. /* Same key, new. */
  2421. int unreachable = 0;
  2422. log_debug(LD_DIR, "Replacing entry for router '%s/%s' [%s]",
  2423. router->nickname, old_router->nickname,
  2424. hex_str(id_digest,DIGEST_LEN));
  2425. if (router->addr == old_router->addr &&
  2426. router->or_port == old_router->or_port) {
  2427. /* these carry over when the address and orport are unchanged.*/
  2428. router->last_reachable = old_router->last_reachable;
  2429. router->testing_since = old_router->testing_since;
  2430. router->num_unreachable_notifications =
  2431. old_router->num_unreachable_notifications;
  2432. }
  2433. if (authdir_may_warn_about_unreachable_server &&
  2434. dirserv_thinks_router_is_blatantly_unreachable(router, time(NULL))) {
  2435. if (router->num_unreachable_notifications >= 3) {
  2436. unreachable = 1;
  2437. log_notice(LD_DIR, "Notifying server '%s' that it's unreachable. "
  2438. "(ContactInfo '%s', platform '%s').",
  2439. router->nickname,
  2440. router->contact_info ? router->contact_info : "",
  2441. router->platform ? router->platform : "");
  2442. } else {
  2443. log_info(LD_DIR,"'%s' may be unreachable -- the %d previous "
  2444. "descriptors were thought to be unreachable.",
  2445. router->nickname, router->num_unreachable_notifications);
  2446. router->num_unreachable_notifications++;
  2447. }
  2448. }
  2449. routerlist_replace(routerlist, old_router, router);
  2450. if (!from_cache) {
  2451. signed_desc_append_to_journal(&router->cache_info,
  2452. router_get_store(routerlist, router));
  2453. }
  2454. directory_set_dirty();
  2455. *msg = unreachable ? "Dirserver believes your ORPort is unreachable" :
  2456. authdir_believes_valid ? "Valid server updated" :
  2457. ("Invalid server updated. (This dirserver is marking your "
  2458. "server as unapproved.)");
  2459. return unreachable ? 1 : 0;
  2460. }
  2461. }
  2462. /* We haven't seen a router with this identity before. Add it to the end of
  2463. * the list. */
  2464. routerlist_insert(routerlist, router);
  2465. if (!from_cache)
  2466. signed_desc_append_to_journal(&router->cache_info,
  2467. router_get_store(routerlist, router));
  2468. directory_set_dirty();
  2469. return 0;
  2470. }
  2471. /** Insert <b>ei</b> into the routerlist, or free it. Other arguments are
  2472. * as for router_add_to_routerlist(). */
  2473. void
  2474. router_add_extrainfo_to_routerlist(extrainfo_t *ei, const char **msg,
  2475. int from_cache, int from_fetch)
  2476. {
  2477. int inserted;
  2478. (void)from_fetch;
  2479. if (msg) *msg = NULL;
  2480. inserted = extrainfo_insert(router_get_routerlist(), ei);
  2481. if (inserted && !from_cache)
  2482. signed_desc_append_to_journal(&ei->cache_info,
  2483. &routerlist->extrainfo_store);
  2484. }
  2485. /** Sorting helper: return &lt;0, 0, or &gt;0 depending on whether the
  2486. * signed_descriptor_t* in *<b>a</b> has an identity digest preceding, equal
  2487. * to, or later than that of *<b>b</b>. */
  2488. static int
  2489. _compare_old_routers_by_identity(const void **_a, const void **_b)
  2490. {
  2491. int i;
  2492. const signed_descriptor_t *r1 = *_a, *r2 = *_b;
  2493. if ((i = memcmp(r1->identity_digest, r2->identity_digest, DIGEST_LEN)))
  2494. return i;
  2495. return r1->published_on - r2->published_on;
  2496. }
  2497. /** Internal type used to represent how long an old descriptor was valid,
  2498. * where it appeared in the list of old descriptors, and whether it's extra
  2499. * old. Used only by routerlist_remove_old_cached_routers_with_id(). */
  2500. struct duration_idx_t {
  2501. int duration;
  2502. int idx;
  2503. int old;
  2504. };
  2505. /** Sorting helper: compare two duration_idx_t by their duration. */
  2506. static int
  2507. _compare_duration_idx(const void *_d1, const void *_d2)
  2508. {
  2509. const struct duration_idx_t *d1 = _d1;
  2510. const struct duration_idx_t *d2 = _d2;
  2511. return d1->duration - d2->duration;
  2512. }
  2513. /** The range <b>lo</b> through <b>hi</b> inclusive of routerlist->old_routers
  2514. * must contain routerinfo_t with the same identity and with publication time
  2515. * in ascending order. Remove members from this range until there are no more
  2516. * than max_descriptors_per_router() remaining. Start by removing the oldest
  2517. * members from before <b>cutoff</b>, then remove members which were current
  2518. * for the lowest amount of time. The order of members of old_routers at
  2519. * indices <b>lo</b> or higher may be changed.
  2520. */
  2521. static void
  2522. routerlist_remove_old_cached_routers_with_id(time_t cutoff, int lo, int hi,
  2523. digestmap_t *retain)
  2524. {
  2525. int i, n = hi-lo+1;
  2526. unsigned n_extra, n_rmv = 0;
  2527. struct duration_idx_t *lifespans;
  2528. uint8_t *rmv, *must_keep;
  2529. smartlist_t *lst = routerlist->old_routers;
  2530. #if 1
  2531. const char *ident;
  2532. tor_assert(hi < smartlist_len(lst));
  2533. tor_assert(lo <= hi);
  2534. ident = ((signed_descriptor_t*)smartlist_get(lst, lo))->identity_digest;
  2535. for (i = lo+1; i <= hi; ++i) {
  2536. signed_descriptor_t *r = smartlist_get(lst, i);
  2537. tor_assert(!memcmp(ident, r->identity_digest, DIGEST_LEN));
  2538. }
  2539. #endif
  2540. /* Check whether we need to do anything at all. */
  2541. {
  2542. int mdpr = dirserver_mode(get_options()) ? 5 : 2;
  2543. if (n <= mdpr)
  2544. return;
  2545. n_extra = n - mdpr;
  2546. }
  2547. lifespans = tor_malloc_zero(sizeof(struct duration_idx_t)*n);
  2548. rmv = tor_malloc_zero(sizeof(uint8_t)*n);
  2549. must_keep = tor_malloc_zero(sizeof(uint8_t)*n);
  2550. /* Set lifespans to contain the lifespan and index of each server. */
  2551. /* Set rmv[i-lo]=1 if we're going to remove a server for being too old. */
  2552. for (i = lo; i <= hi; ++i) {
  2553. signed_descriptor_t *r = smartlist_get(lst, i);
  2554. signed_descriptor_t *r_next;
  2555. lifespans[i-lo].idx = i;
  2556. if (retain && digestmap_get(retain, r->signed_descriptor_digest)) {
  2557. must_keep[i-lo] = 1;
  2558. }
  2559. if (i < hi) {
  2560. r_next = smartlist_get(lst, i+1);
  2561. tor_assert(r->published_on <= r_next->published_on);
  2562. lifespans[i-lo].duration = (r_next->published_on - r->published_on);
  2563. } else {
  2564. r_next = NULL;
  2565. lifespans[i-lo].duration = INT_MAX;
  2566. }
  2567. if (!must_keep[i-lo] && r->published_on < cutoff && n_rmv < n_extra) {
  2568. ++n_rmv;
  2569. lifespans[i-lo].old = 1;
  2570. rmv[i-lo] = 1;
  2571. }
  2572. }
  2573. if (n_rmv < n_extra) {
  2574. /**
  2575. * We aren't removing enough servers for being old. Sort lifespans by
  2576. * the duration of liveness, and remove the ones we're not already going to
  2577. * remove based on how long they were alive.
  2578. **/
  2579. qsort(lifespans, n, sizeof(struct duration_idx_t), _compare_duration_idx);
  2580. for (i = 0; i < n && n_rmv < n_extra; ++i) {
  2581. if (!must_keep[lifespans[i].idx-lo] && !lifespans[i].old) {
  2582. rmv[lifespans[i].idx-lo] = 1;
  2583. ++n_rmv;
  2584. }
  2585. }
  2586. }
  2587. i = hi;
  2588. do {
  2589. if (rmv[i-lo])
  2590. routerlist_remove_old(routerlist, smartlist_get(lst, i), i);
  2591. } while (--i >= lo);
  2592. tor_free(must_keep);
  2593. tor_free(rmv);
  2594. tor_free(lifespans);
  2595. }
  2596. /** Deactivate any routers from the routerlist that are more than
  2597. * ROUTER_MAX_AGE seconds old and not recommended by any networkstatuses;
  2598. * remove old routers from the list of cached routers if we have too many.
  2599. */
  2600. void
  2601. routerlist_remove_old_routers(void)
  2602. {
  2603. int i, hi=-1;
  2604. const char *cur_id = NULL;
  2605. time_t now = time(NULL);
  2606. time_t cutoff;
  2607. routerinfo_t *router;
  2608. signed_descriptor_t *sd;
  2609. digestmap_t *retain;
  2610. int dirserv = dirserver_mode(get_options());
  2611. const networkstatus_vote_t *consensus = networkstatus_get_latest_consensus();
  2612. const smartlist_t *networkstatus_v2_list = networkstatus_get_v2_list();
  2613. trusted_dirs_remove_old_certs();
  2614. if (!routerlist || !consensus)
  2615. return;
  2616. // routerlist_assert_ok(routerlist);
  2617. retain = digestmap_new();
  2618. cutoff = now - OLD_ROUTER_DESC_MAX_AGE;
  2619. /* Build a list of all the descriptors that _anybody_ lists. */
  2620. if (dirserv) {
  2621. SMARTLIST_FOREACH(networkstatus_v2_list, networkstatus_v2_t *, ns,
  2622. {
  2623. /* XXXX The inner loop here gets pretty expensive, and actually shows up
  2624. * on some profiles. It may be the reason digestmap_set shows up in
  2625. * profiles too. If instead we kept a per-descriptor digest count of
  2626. * how many networkstatuses recommended each descriptor, and changed
  2627. * that only when the networkstatuses changed, that would be a speed
  2628. * improvement, possibly 1-4% if it also removes digestmap_set from the
  2629. * profile. Not worth it for 0.1.2.x, though. The new directory
  2630. * system will obsolete this whole thing in 0.2.0.x. */
  2631. SMARTLIST_FOREACH(ns->entries, routerstatus_t *, rs,
  2632. if (rs->published_on >= cutoff)
  2633. digestmap_set(retain, rs->descriptor_digest, (void*)1));
  2634. });
  2635. }
  2636. /* Retain anything listed in the consensus. */
  2637. if (consensus) {
  2638. SMARTLIST_FOREACH(consensus->routerstatus_list, routerstatus_t *, rs,
  2639. if (rs->published_on >= cutoff)
  2640. digestmap_set(retain, rs->descriptor_digest, (void*)1));
  2641. }
  2642. /* If we have a bunch of networkstatuses, we should consider pruning current
  2643. * routers that are too old and that nobody recommends. (If we don't have
  2644. * enough networkstatuses, then we should get more before we decide to kill
  2645. * routers.) */
  2646. if (!dirserv ||
  2647. smartlist_len(networkstatus_v2_list) > get_n_v2_authorities() / 2) {
  2648. cutoff = now - ROUTER_MAX_AGE;
  2649. /* Remove too-old unrecommended members of routerlist->routers. */
  2650. for (i = 0; i < smartlist_len(routerlist->routers); ++i) {
  2651. router = smartlist_get(routerlist->routers, i);
  2652. if (router->cache_info.published_on <= cutoff &&
  2653. !digestmap_get(retain,router->cache_info.signed_descriptor_digest)) {
  2654. /* Too old: remove it. (If we're a cache, just move it into
  2655. * old_routers.) */
  2656. log_info(LD_DIR,
  2657. "Forgetting obsolete (too old) routerinfo for router '%s'",
  2658. router->nickname);
  2659. routerlist_remove(routerlist, router, 1);
  2660. i--;
  2661. }
  2662. }
  2663. }
  2664. //routerlist_assert_ok(routerlist);
  2665. /* Remove far-too-old members of routerlist->old_routers. */
  2666. cutoff = now - OLD_ROUTER_DESC_MAX_AGE;
  2667. for (i = 0; i < smartlist_len(routerlist->old_routers); ++i) {
  2668. sd = smartlist_get(routerlist->old_routers, i);
  2669. if (sd->published_on <= cutoff &&
  2670. !digestmap_get(retain, sd->signed_descriptor_digest)) {
  2671. /* Too old. Remove it. */
  2672. routerlist_remove_old(routerlist, sd, i--);
  2673. }
  2674. }
  2675. //routerlist_assert_ok(routerlist);
  2676. log_info(LD_DIR, "We have %d live routers and %d old router descriptors. "
  2677. "At most %d must be retained because of networkstatuses.",
  2678. smartlist_len(routerlist->routers),
  2679. smartlist_len(routerlist->old_routers),
  2680. digestmap_size(retain));
  2681. /* Now we might have to look at routerlist->old_routers for extraneous
  2682. * members. (We'd keep all the members if we could, but we need to save
  2683. * space.) First, check whether we have too many router descriptors, total.
  2684. * We're okay with having too many for some given router, so long as the
  2685. * total number doesn't approach max_descriptors_per_router()*len(router).
  2686. */
  2687. if (smartlist_len(routerlist->old_routers) <
  2688. smartlist_len(routerlist->routers) * (dirserver_mode(get_options())?4:2))
  2689. goto done;
  2690. smartlist_sort(routerlist->old_routers, _compare_old_routers_by_identity);
  2691. /* Iterate through the list from back to front, so when we remove descriptors
  2692. * we don't mess up groups we haven't gotten to. */
  2693. for (i = smartlist_len(routerlist->old_routers)-1; i >= 0; --i) {
  2694. signed_descriptor_t *r = smartlist_get(routerlist->old_routers, i);
  2695. if (!cur_id) {
  2696. cur_id = r->identity_digest;
  2697. hi = i;
  2698. }
  2699. if (memcmp(cur_id, r->identity_digest, DIGEST_LEN)) {
  2700. routerlist_remove_old_cached_routers_with_id(cutoff, i+1, hi, retain);
  2701. cur_id = r->identity_digest;
  2702. hi = i;
  2703. }
  2704. }
  2705. if (hi>=0)
  2706. routerlist_remove_old_cached_routers_with_id(cutoff, 0, hi, retain);
  2707. //routerlist_assert_ok(routerlist);
  2708. done:
  2709. digestmap_free(retain, NULL);
  2710. }
  2711. /** We just added a new descriptor that isn't of purpose
  2712. * ROUTER_PURPOSE_GENERAL. Take whatever extra steps we need. */
  2713. static void
  2714. routerlist_descriptors_added(smartlist_t *sl)
  2715. {
  2716. tor_assert(sl);
  2717. control_event_descriptors_changed(sl);
  2718. SMARTLIST_FOREACH(sl, routerinfo_t *, ri,
  2719. if (ri->purpose == ROUTER_PURPOSE_BRIDGE)
  2720. learned_bridge_descriptor(ri);
  2721. );
  2722. }
  2723. /**
  2724. * Code to parse a single router descriptor and insert it into the
  2725. * routerlist. Return -1 if the descriptor was ill-formed; 0 if the
  2726. * descriptor was well-formed but could not be added; and 1 if the
  2727. * descriptor was added.
  2728. *
  2729. * If we don't add it and <b>msg</b> is not NULL, then assign to
  2730. * *<b>msg</b> a static string describing the reason for refusing the
  2731. * descriptor.
  2732. *
  2733. * This is used only by the controller.
  2734. */
  2735. int
  2736. router_load_single_router(const char *s, uint8_t purpose, int cache,
  2737. const char **msg)
  2738. {
  2739. routerinfo_t *ri;
  2740. int r;
  2741. smartlist_t *lst;
  2742. char annotation_buf[256];
  2743. tor_assert(msg);
  2744. *msg = NULL;
  2745. tor_snprintf(annotation_buf, sizeof(annotation_buf),
  2746. "@source controller\n"
  2747. "@purpose %s\n", router_purpose_to_string(purpose));
  2748. if (!(ri = router_parse_entry_from_string(s, NULL, 1, 0, annotation_buf))) {
  2749. log_warn(LD_DIR, "Error parsing router descriptor; dropping.");
  2750. *msg = "Couldn't parse router descriptor.";
  2751. return -1;
  2752. }
  2753. tor_assert(ri->purpose == purpose);
  2754. if (router_is_me(ri)) {
  2755. log_warn(LD_DIR, "Router's identity key matches mine; dropping.");
  2756. *msg = "Router's identity key matches mine.";
  2757. routerinfo_free(ri);
  2758. return 0;
  2759. }
  2760. if (!cache) /* obey the preference of the controller */
  2761. ri->cache_info.do_not_cache = 1;
  2762. lst = smartlist_create();
  2763. smartlist_add(lst, ri);
  2764. routers_update_status_from_consensus_networkstatus(lst, 0);
  2765. if ((r=router_add_to_routerlist(ri, msg, 0, 0))<0) {
  2766. /* we've already assigned to *msg now, and ri is already freed */
  2767. tor_assert(*msg);
  2768. if (r < -1)
  2769. log_warn(LD_DIR, "Couldn't add router to list: %s Dropping.", *msg);
  2770. smartlist_free(lst);
  2771. return 0;
  2772. } else {
  2773. routerlist_descriptors_added(lst);
  2774. smartlist_free(lst);
  2775. log_debug(LD_DIR, "Added router to list");
  2776. return 1;
  2777. }
  2778. }
  2779. /** Given a string <b>s</b> containing some routerdescs, parse it and put the
  2780. * routers into our directory. If saved_location is SAVED_NOWHERE, the routers
  2781. * are in response to a query to the network: cache them by adding them to
  2782. * the journal.
  2783. *
  2784. * If <b>requested_fingerprints</b> is provided, it must contain a list of
  2785. * uppercased fingerprints. Do not update any router whose
  2786. * fingerprint is not on the list; after updating a router, remove its
  2787. * fingerprint from the list.
  2788. *
  2789. * If <b>descriptor_digests</b> is non-zero, then the requested_fingerprints
  2790. * are descriptor digests. Otherwise they are identity digests.
  2791. */
  2792. void
  2793. router_load_routers_from_string(const char *s, const char *eos,
  2794. saved_location_t saved_location,
  2795. smartlist_t *requested_fingerprints,
  2796. int descriptor_digests,
  2797. const char *prepend_annotations)
  2798. {
  2799. smartlist_t *routers = smartlist_create(), *changed = smartlist_create();
  2800. char fp[HEX_DIGEST_LEN+1];
  2801. const char *msg;
  2802. int from_cache = (saved_location != SAVED_NOWHERE);
  2803. int allow_annotations = (saved_location != SAVED_NOWHERE);
  2804. router_parse_list_from_string(&s, eos, routers, saved_location, 0,
  2805. allow_annotations, prepend_annotations);
  2806. routers_update_status_from_consensus_networkstatus(routers, !from_cache);
  2807. log_info(LD_DIR, "%d elements to add", smartlist_len(routers));
  2808. SMARTLIST_FOREACH(routers, routerinfo_t *, ri,
  2809. {
  2810. if (requested_fingerprints) {
  2811. base16_encode(fp, sizeof(fp), descriptor_digests ?
  2812. ri->cache_info.signed_descriptor_digest :
  2813. ri->cache_info.identity_digest,
  2814. DIGEST_LEN);
  2815. if (smartlist_string_isin(requested_fingerprints, fp)) {
  2816. smartlist_string_remove(requested_fingerprints, fp);
  2817. } else {
  2818. char *requested =
  2819. smartlist_join_strings(requested_fingerprints," ",0,NULL);
  2820. log_warn(LD_DIR,
  2821. "We received a router descriptor with a fingerprint (%s) "
  2822. "that we never requested. (We asked for: %s.) Dropping.",
  2823. fp, requested);
  2824. tor_free(requested);
  2825. routerinfo_free(ri);
  2826. continue;
  2827. }
  2828. }
  2829. if (router_add_to_routerlist(ri, &msg, from_cache, !from_cache) >= 0) {
  2830. smartlist_add(changed, ri);
  2831. routerlist_descriptors_added(changed);
  2832. smartlist_clear(changed);
  2833. }
  2834. });
  2835. routerlist_assert_ok(routerlist);
  2836. router_rebuild_store(0, &routerlist->desc_store);
  2837. smartlist_free(routers);
  2838. smartlist_free(changed);
  2839. }
  2840. /** Parse one or more extrainfos from <b>s</b> (ending immediately before
  2841. * <b>eos</b> if <b>eos</b> is present). Other arguments are as for
  2842. * router_load_routers_from_string(). */
  2843. void
  2844. router_load_extrainfo_from_string(const char *s, const char *eos,
  2845. saved_location_t saved_location,
  2846. smartlist_t *requested_fingerprints,
  2847. int descriptor_digests)
  2848. {
  2849. smartlist_t *extrainfo_list = smartlist_create();
  2850. const char *msg;
  2851. int from_cache = (saved_location != SAVED_NOWHERE);
  2852. router_parse_list_from_string(&s, eos, extrainfo_list, saved_location, 1, 0,
  2853. NULL);
  2854. log_info(LD_DIR, "%d elements to add", smartlist_len(extrainfo_list));
  2855. SMARTLIST_FOREACH(extrainfo_list, extrainfo_t *, ei, {
  2856. if (requested_fingerprints) {
  2857. char fp[HEX_DIGEST_LEN+1];
  2858. base16_encode(fp, sizeof(fp), descriptor_digests ?
  2859. ei->cache_info.signed_descriptor_digest :
  2860. ei->cache_info.identity_digest,
  2861. DIGEST_LEN);
  2862. smartlist_string_remove(requested_fingerprints, fp);
  2863. /* XXX020 We silently let people stuff us with extrainfos we
  2864. * didn't ask for. Is this a problem? -RD */
  2865. }
  2866. router_add_extrainfo_to_routerlist(ei, &msg, from_cache, !from_cache);
  2867. });
  2868. routerlist_assert_ok(routerlist);
  2869. router_rebuild_store(0, &router_get_routerlist()->extrainfo_store);
  2870. smartlist_free(extrainfo_list);
  2871. }
  2872. /** Return true iff any networkstatus includes a descriptor whose digest
  2873. * is that of <b>desc</b>. */
  2874. static int
  2875. signed_desc_digest_is_recognized(signed_descriptor_t *desc)
  2876. {
  2877. routerstatus_t *rs;
  2878. networkstatus_vote_t *consensus = networkstatus_get_latest_consensus();
  2879. int dirserv = dirserver_mode(get_options());
  2880. const smartlist_t *networkstatus_v2_list = networkstatus_get_v2_list();
  2881. if (consensus) {
  2882. rs = networkstatus_vote_find_entry(consensus, desc->identity_digest);
  2883. if (rs && !memcmp(rs->descriptor_digest,
  2884. desc->signed_descriptor_digest, DIGEST_LEN))
  2885. return 1;
  2886. }
  2887. if (dirserv && networkstatus_v2_list) {
  2888. SMARTLIST_FOREACH(networkstatus_v2_list, networkstatus_v2_t *, ns,
  2889. {
  2890. if (!(rs = networkstatus_v2_find_entry(ns, desc->identity_digest)))
  2891. continue;
  2892. if (!memcmp(rs->descriptor_digest,
  2893. desc->signed_descriptor_digest, DIGEST_LEN))
  2894. return 1;
  2895. });
  2896. }
  2897. return 0;
  2898. }
  2899. /** Clear all our timeouts for fetching v2 and v3 directory stuff, and then
  2900. * give it all a try again. */
  2901. void
  2902. routerlist_retry_directory_downloads(time_t now)
  2903. {
  2904. router_reset_status_download_failures();
  2905. router_reset_descriptor_download_failures();
  2906. update_networkstatus_downloads(now);
  2907. update_router_descriptor_downloads(now);
  2908. }
  2909. /** Return 1 if all running sufficiently-stable routers will reject
  2910. * addr:port, return 0 if any might accept it. */
  2911. int
  2912. router_exit_policy_all_routers_reject(uint32_t addr, uint16_t port,
  2913. int need_uptime)
  2914. {
  2915. addr_policy_result_t r;
  2916. if (!routerlist) return 1;
  2917. SMARTLIST_FOREACH(routerlist->routers, routerinfo_t *, router,
  2918. {
  2919. if (router->is_running &&
  2920. !router_is_unreliable(router, need_uptime, 0, 0)) {
  2921. r = compare_addr_to_addr_policy(addr, port, router->exit_policy);
  2922. if (r != ADDR_POLICY_REJECTED && r != ADDR_POLICY_PROBABLY_REJECTED)
  2923. return 0; /* this one could be ok. good enough. */
  2924. }
  2925. });
  2926. return 1; /* all will reject. */
  2927. }
  2928. /** Return true iff <b>router</b> does not permit exit streams.
  2929. */
  2930. int
  2931. router_exit_policy_rejects_all(routerinfo_t *router)
  2932. {
  2933. return compare_addr_to_addr_policy(0, 0, router->exit_policy)
  2934. == ADDR_POLICY_REJECTED;
  2935. }
  2936. /** Add to the list of authorized directory servers one at
  2937. * <b>address</b>:<b>port</b>, with identity key <b>digest</b>. If
  2938. * <b>address</b> is NULL, add ourself. */
  2939. void
  2940. add_trusted_dir_server(const char *nickname, const char *address,
  2941. uint16_t dir_port, uint16_t or_port,
  2942. const char *digest, const char *v3_auth_digest,
  2943. authority_type_t type)
  2944. {
  2945. trusted_dir_server_t *ent;
  2946. uint32_t a;
  2947. char *hostname = NULL;
  2948. size_t dlen;
  2949. if (!trusted_dir_servers)
  2950. trusted_dir_servers = smartlist_create();
  2951. if (!address) { /* The address is us; we should guess. */
  2952. if (resolve_my_address(LOG_WARN, get_options(), &a, &hostname) < 0) {
  2953. log_warn(LD_CONFIG,
  2954. "Couldn't find a suitable address when adding ourself as a "
  2955. "trusted directory server.");
  2956. return;
  2957. }
  2958. } else {
  2959. if (tor_lookup_hostname(address, &a)) {
  2960. log_warn(LD_CONFIG,
  2961. "Unable to lookup address for directory server at '%s'",
  2962. address);
  2963. return;
  2964. }
  2965. hostname = tor_strdup(address);
  2966. }
  2967. ent = tor_malloc_zero(sizeof(trusted_dir_server_t));
  2968. ent->nickname = nickname ? tor_strdup(nickname) : NULL;
  2969. ent->address = hostname;
  2970. ent->addr = a;
  2971. ent->dir_port = dir_port;
  2972. ent->or_port = or_port;
  2973. ent->is_running = 1;
  2974. ent->type = type;
  2975. memcpy(ent->digest, digest, DIGEST_LEN);
  2976. if (v3_auth_digest && (type & V3_AUTHORITY))
  2977. memcpy(ent->v3_identity_digest, v3_auth_digest, DIGEST_LEN);
  2978. dlen = 64 + strlen(hostname) + (nickname?strlen(nickname):0);
  2979. ent->description = tor_malloc(dlen);
  2980. if (nickname)
  2981. tor_snprintf(ent->description, dlen, "directory server \"%s\" at %s:%d",
  2982. nickname, hostname, (int)dir_port);
  2983. else
  2984. tor_snprintf(ent->description, dlen, "directory server at %s:%d",
  2985. hostname, (int)dir_port);
  2986. ent->fake_status.addr = ent->addr;
  2987. memcpy(ent->fake_status.identity_digest, digest, DIGEST_LEN);
  2988. if (nickname)
  2989. strlcpy(ent->fake_status.nickname, nickname,
  2990. sizeof(ent->fake_status.nickname));
  2991. else
  2992. ent->fake_status.nickname[0] = '\0';
  2993. ent->fake_status.dir_port = ent->dir_port;
  2994. ent->fake_status.or_port = ent->or_port;
  2995. if (ent->or_port)
  2996. ent->fake_status.version_supports_begindir = 1;
  2997. smartlist_add(trusted_dir_servers, ent);
  2998. router_dir_info_changed();
  2999. }
  3000. /** Free storage held in <b>ds</b>. */
  3001. static void
  3002. trusted_dir_server_free(trusted_dir_server_t *ds)
  3003. {
  3004. if (ds->v3_certs) {
  3005. SMARTLIST_FOREACH(ds->v3_certs, authority_cert_t *, cert,
  3006. authority_cert_free(cert));
  3007. smartlist_free(ds->v3_certs);
  3008. }
  3009. tor_free(ds->nickname);
  3010. tor_free(ds->description);
  3011. tor_free(ds->address);
  3012. tor_free(ds);
  3013. }
  3014. /** Remove all members from the list of trusted dir servers. */
  3015. void
  3016. clear_trusted_dir_servers(void)
  3017. {
  3018. if (trusted_dir_servers) {
  3019. SMARTLIST_FOREACH(trusted_dir_servers, trusted_dir_server_t *, ent,
  3020. trusted_dir_server_free(ent));
  3021. smartlist_clear(trusted_dir_servers);
  3022. } else {
  3023. trusted_dir_servers = smartlist_create();
  3024. }
  3025. router_dir_info_changed();
  3026. }
  3027. /** Return 1 if any trusted dir server supports v1 directories,
  3028. * else return 0. */
  3029. int
  3030. any_trusted_dir_is_v1_authority(void)
  3031. {
  3032. if (trusted_dir_servers)
  3033. return get_n_authorities(V1_AUTHORITY) > 0;
  3034. return 0;
  3035. }
  3036. /** For every current directory connection whose purpose is <b>purpose</b>,
  3037. * and where the resource being downloaded begins with <b>prefix</b>, split
  3038. * rest of the resource into base16 fingerprints, decode them, and set the
  3039. * corresponding elements of <b>result</b> to a nonzero value. */
  3040. static void
  3041. list_pending_downloads(digestmap_t *result,
  3042. int purpose, const char *prefix)
  3043. {
  3044. const size_t p_len = strlen(prefix);
  3045. smartlist_t *tmp = smartlist_create();
  3046. smartlist_t *conns = get_connection_array();
  3047. tor_assert(result);
  3048. SMARTLIST_FOREACH(conns, connection_t *, conn,
  3049. {
  3050. if (conn->type == CONN_TYPE_DIR &&
  3051. conn->purpose == purpose &&
  3052. !conn->marked_for_close) {
  3053. const char *resource = TO_DIR_CONN(conn)->requested_resource;
  3054. if (!strcmpstart(resource, prefix))
  3055. dir_split_resource_into_fingerprints(resource + p_len,
  3056. tmp, NULL, 1, 0);
  3057. }
  3058. });
  3059. SMARTLIST_FOREACH(tmp, char *, d,
  3060. {
  3061. digestmap_set(result, d, (void*)1);
  3062. tor_free(d);
  3063. });
  3064. smartlist_free(tmp);
  3065. }
  3066. /** For every router descriptor (or extra-info document if <b>extrainfo</b> is
  3067. * true) we are currently downloading by descriptor digest, set result[d] to
  3068. * (void*)1. */
  3069. static void
  3070. list_pending_descriptor_downloads(digestmap_t *result, int extrainfo)
  3071. {
  3072. int purpose =
  3073. extrainfo ? DIR_PURPOSE_FETCH_EXTRAINFO : DIR_PURPOSE_FETCH_SERVERDESC;
  3074. list_pending_downloads(result, purpose, "d/");
  3075. }
  3076. /** Launch downloads for all the descriptors whose digests are listed
  3077. * as digests[i] for lo <= i < hi. (Lo and hi may be out of range.)
  3078. * If <b>source</b> is given, download from <b>source</b>; otherwise,
  3079. * download from an appropriate random directory server.
  3080. */
  3081. static void
  3082. initiate_descriptor_downloads(routerstatus_t *source,
  3083. int purpose,
  3084. smartlist_t *digests,
  3085. int lo, int hi)
  3086. {
  3087. int i, n = hi-lo;
  3088. char *resource, *cp;
  3089. size_t r_len;
  3090. if (n <= 0)
  3091. return;
  3092. if (lo < 0)
  3093. lo = 0;
  3094. if (hi > smartlist_len(digests))
  3095. hi = smartlist_len(digests);
  3096. r_len = 8 + (HEX_DIGEST_LEN+1)*n;
  3097. cp = resource = tor_malloc(r_len);
  3098. memcpy(cp, "d/", 2);
  3099. cp += 2;
  3100. for (i = lo; i < hi; ++i) {
  3101. base16_encode(cp, r_len-(cp-resource),
  3102. smartlist_get(digests,i), DIGEST_LEN);
  3103. cp += HEX_DIGEST_LEN;
  3104. *cp++ = '+';
  3105. }
  3106. memcpy(cp-1, ".z", 3);
  3107. if (source) {
  3108. /* We know which authority we want. */
  3109. directory_initiate_command_routerstatus(source, purpose,
  3110. ROUTER_PURPOSE_GENERAL,
  3111. 0, /* not private */
  3112. resource, NULL, 0);
  3113. } else {
  3114. directory_get_from_dirserver(purpose, ROUTER_PURPOSE_GENERAL, resource, 1);
  3115. }
  3116. tor_free(resource);
  3117. }
  3118. /** Clients don't download any descriptor this recent, since it will probably
  3119. * not have propagated to enough caches. */
  3120. #define ESTIMATED_PROPAGATION_TIME (10*60)
  3121. /** Return 0 if this routerstatus is obsolete, too new, isn't
  3122. * running, or otherwise not a descriptor that we would make any
  3123. * use of even if we had it. Else return 1. */
  3124. static INLINE int
  3125. client_would_use_router(routerstatus_t *rs, time_t now, or_options_t *options)
  3126. {
  3127. if (!rs->is_running && !options->FetchUselessDescriptors) {
  3128. /* If we had this router descriptor, we wouldn't even bother using it.
  3129. * But, if we want to have a complete list, fetch it anyway. */
  3130. return 0;
  3131. }
  3132. if (rs->published_on + ESTIMATED_PROPAGATION_TIME > now) {
  3133. /* Most caches probably don't have this descriptor yet. */
  3134. return 0;
  3135. }
  3136. if (rs->published_on + OLD_ROUTER_DESC_MAX_AGE < now) {
  3137. /* We'd drop it immediately for being too old. */
  3138. return 0;
  3139. }
  3140. return 1;
  3141. }
  3142. /** Max amount of hashes to download per request.
  3143. * Since squid does not like URLs >= 4096 bytes we limit it to 96.
  3144. * 4096 - strlen(http://255.255.255.255/tor/server/d/.z) == 4058
  3145. * 4058/41 (40 for the hash and 1 for the + that separates them) => 98
  3146. * So use 96 because it's a nice number.
  3147. */
  3148. #define MAX_DL_PER_REQUEST 96
  3149. /** Don't split our requests so finely that we are requesting fewer than
  3150. * this number per server. */
  3151. #define MIN_DL_PER_REQUEST 4
  3152. /** To prevent a single screwy cache from confusing us by selective reply,
  3153. * try to split our requests into at least this this many requests. */
  3154. #define MIN_REQUESTS 3
  3155. /** If we want fewer than this many descriptors, wait until we
  3156. * want more, or until MAX_CLIENT_INTERVAL_WITHOUT_REQUEST has
  3157. * passed. */
  3158. #define MAX_DL_TO_DELAY 16
  3159. /** When directory clients have only a few servers to request, they batch
  3160. * them until they have more, or until this amount of time has passed. */
  3161. #define MAX_CLIENT_INTERVAL_WITHOUT_REQUEST (10*60)
  3162. /** Given a list of router descriptor digests in <b>downloadable</b>, decide
  3163. * whether to delay fetching until we have more. If we don't want to delay,
  3164. * launch one or more requests to the appropriate directory authorities. */
  3165. static void
  3166. launch_router_descriptor_downloads(smartlist_t *downloadable, time_t now)
  3167. {
  3168. int should_delay = 0, n_downloadable;
  3169. or_options_t *options = get_options();
  3170. n_downloadable = smartlist_len(downloadable);
  3171. if (!dirserver_mode(options)) {
  3172. if (n_downloadable >= MAX_DL_TO_DELAY) {
  3173. log_debug(LD_DIR,
  3174. "There are enough downloadable routerdescs to launch requests.");
  3175. should_delay = 0;
  3176. } else {
  3177. should_delay = (last_routerdesc_download_attempted +
  3178. MAX_CLIENT_INTERVAL_WITHOUT_REQUEST) > now;
  3179. if (!should_delay) {
  3180. if (last_routerdesc_download_attempted) {
  3181. log_info(LD_DIR,
  3182. "There are not many downloadable routerdescs, but we've "
  3183. "been waiting long enough (%d seconds). Downloading.",
  3184. (int)(now-last_routerdesc_download_attempted));
  3185. } else {
  3186. log_info(LD_DIR,
  3187. "There are not many downloadable routerdescs, but we haven't "
  3188. "tried downloading descriptors recently. Downloading.");
  3189. }
  3190. }
  3191. }
  3192. }
  3193. if (! should_delay) {
  3194. int i, n_per_request;
  3195. const char *req_plural = "", *rtr_plural = "";
  3196. n_per_request = (n_downloadable+MIN_REQUESTS-1) / MIN_REQUESTS;
  3197. if (n_per_request > MAX_DL_PER_REQUEST)
  3198. n_per_request = MAX_DL_PER_REQUEST;
  3199. if (n_per_request < MIN_DL_PER_REQUEST)
  3200. n_per_request = MIN_DL_PER_REQUEST;
  3201. if (n_downloadable > n_per_request)
  3202. req_plural = rtr_plural = "s";
  3203. else if (n_downloadable > 1)
  3204. rtr_plural = "s";
  3205. log_info(LD_DIR,
  3206. "Launching %d request%s for %d router%s, %d at a time",
  3207. (n_downloadable+n_per_request-1)/n_per_request,
  3208. req_plural, n_downloadable, rtr_plural, n_per_request);
  3209. smartlist_sort_digests(downloadable);
  3210. for (i=0; i < n_downloadable; i += n_per_request) {
  3211. initiate_descriptor_downloads(NULL, DIR_PURPOSE_FETCH_SERVERDESC,
  3212. downloadable, i, i+n_per_request);
  3213. }
  3214. last_routerdesc_download_attempted = now;
  3215. }
  3216. }
  3217. /** Launch downloads for router status as needed, using the strategy used by
  3218. * authorities and caches: download every descriptor we don't have but would
  3219. * serve, from a random authority that lists it. */
  3220. static void
  3221. update_router_descriptor_cache_downloads(time_t now)
  3222. {
  3223. smartlist_t **downloadable; /* For each authority, what can we dl from it? */
  3224. smartlist_t **download_from; /* ... and, what will we dl from it? */
  3225. digestmap_t *map; /* Which descs are in progress, or assigned? */
  3226. int i, j, n;
  3227. int n_download;
  3228. or_options_t *options = get_options();
  3229. const smartlist_t *networkstatus_v2_list = networkstatus_get_v2_list();
  3230. if (! dirserver_mode(options)) {
  3231. log_warn(LD_BUG, "Called update_router_descriptor_cache_downloads() "
  3232. "on a non-dir-mirror?");
  3233. }
  3234. if (!networkstatus_v2_list || !smartlist_len(networkstatus_v2_list))
  3235. return;
  3236. map = digestmap_new();
  3237. n = smartlist_len(networkstatus_v2_list);
  3238. downloadable = tor_malloc_zero(sizeof(smartlist_t*) * n);
  3239. download_from = tor_malloc_zero(sizeof(smartlist_t*) * n);
  3240. /* Set map[d]=1 for the digest of every descriptor that we are currently
  3241. * downloading. */
  3242. list_pending_descriptor_downloads(map, 0);
  3243. /* For the digest of every descriptor that we don't have, and that we aren't
  3244. * downloading, add d to downloadable[i] if the i'th networkstatus knows
  3245. * about that descriptor, and we haven't already failed to get that
  3246. * descriptor from the corresponding authority.
  3247. */
  3248. n_download = 0;
  3249. SMARTLIST_FOREACH(networkstatus_v2_list, networkstatus_v2_t *, ns,
  3250. {
  3251. trusted_dir_server_t *ds;
  3252. smartlist_t *dl;
  3253. dl = downloadable[ns_sl_idx] = smartlist_create();
  3254. download_from[ns_sl_idx] = smartlist_create();
  3255. if (ns->published_on + MAX_NETWORKSTATUS_AGE+10*60 < now) {
  3256. /* Don't download if the networkstatus is almost ancient. */
  3257. /* Actually, I suspect what's happening here is that we ask
  3258. * for the descriptor when we have a given networkstatus,
  3259. * and then we get a newer networkstatus, and then we receive
  3260. * the descriptor. Having a networkstatus actually expire is
  3261. * probably a rare event, and we'll probably be happiest if
  3262. * we take this clause out. -RD */
  3263. continue;
  3264. }
  3265. /* Don't try dirservers that we think are down -- we might have
  3266. * just tried them and just marked them as down. */
  3267. ds = router_get_trusteddirserver_by_digest(ns->identity_digest);
  3268. if (ds && !ds->is_running)
  3269. continue;
  3270. SMARTLIST_FOREACH(ns->entries, routerstatus_t * , rs,
  3271. {
  3272. if (!rs->need_to_mirror)
  3273. continue;
  3274. if (router_get_by_descriptor_digest(rs->descriptor_digest)) {
  3275. log_warn(LD_BUG,
  3276. "We have a router descriptor, but need_to_mirror=1.");
  3277. rs->need_to_mirror = 0;
  3278. continue;
  3279. }
  3280. if (authdir_mode(options) && dirserv_would_reject_router(rs)) {
  3281. rs->need_to_mirror = 0;
  3282. continue;
  3283. }
  3284. if (digestmap_get(map, rs->descriptor_digest)) {
  3285. /* We're downloading it already. */
  3286. continue;
  3287. } else {
  3288. /* We could download it from this guy. */
  3289. smartlist_add(dl, rs->descriptor_digest);
  3290. ++n_download;
  3291. }
  3292. });
  3293. });
  3294. /* At random, assign descriptors to authorities such that:
  3295. * - if d is a member of some downloadable[x], d is a member of some
  3296. * download_from[y]. (Everything we want to download, we try to download
  3297. * from somebody.)
  3298. * - If d is a member of download_from[y], d is a member of downloadable[y].
  3299. * (We only try to download descriptors from authorities who claim to have
  3300. * them.)
  3301. * - No d is a member of download_from[x] and download_from[y] s.t. x != y.
  3302. * (We don't try to download anything from two authorities concurrently.)
  3303. */
  3304. while (n_download) {
  3305. int which_ns = crypto_rand_int(n);
  3306. smartlist_t *dl = downloadable[which_ns];
  3307. int idx;
  3308. char *d;
  3309. if (!smartlist_len(dl))
  3310. continue;
  3311. idx = crypto_rand_int(smartlist_len(dl));
  3312. d = smartlist_get(dl, idx);
  3313. if (! digestmap_get(map, d)) {
  3314. smartlist_add(download_from[which_ns], d);
  3315. digestmap_set(map, d, (void*) 1);
  3316. }
  3317. smartlist_del(dl, idx);
  3318. --n_download;
  3319. }
  3320. /* Now, we can actually launch our requests. */
  3321. for (i=0; i<n; ++i) {
  3322. networkstatus_v2_t *ns = smartlist_get(networkstatus_v2_list, i);
  3323. trusted_dir_server_t *ds =
  3324. router_get_trusteddirserver_by_digest(ns->identity_digest);
  3325. smartlist_t *dl = download_from[i];
  3326. if (!ds) {
  3327. log_warn(LD_BUG, "Networkstatus with no corresponding authority!");
  3328. continue;
  3329. }
  3330. if (! smartlist_len(dl))
  3331. continue;
  3332. log_info(LD_DIR, "Requesting %d descriptors from authority \"%s\"",
  3333. smartlist_len(dl), ds->nickname);
  3334. for (j=0; j < smartlist_len(dl); j += MAX_DL_PER_REQUEST) {
  3335. initiate_descriptor_downloads(&(ds->fake_status),
  3336. DIR_PURPOSE_FETCH_SERVERDESC, dl, j,
  3337. j+MAX_DL_PER_REQUEST);
  3338. }
  3339. }
  3340. for (i=0; i<n; ++i) {
  3341. smartlist_free(download_from[i]);
  3342. smartlist_free(downloadable[i]);
  3343. }
  3344. tor_free(download_from);
  3345. tor_free(downloadable);
  3346. digestmap_free(map,NULL);
  3347. }
  3348. /** For any descriptor that we want that's currently listed in the live
  3349. * consensus, download it as appropriate. */
  3350. static void
  3351. update_consensus_router_descriptor_downloads(time_t now)
  3352. {
  3353. or_options_t *options = get_options();
  3354. digestmap_t *map = NULL;
  3355. smartlist_t *downloadable = smartlist_create();
  3356. int authdir = authdir_mode(options);
  3357. int dirserver = dirserver_mode(options);
  3358. networkstatus_vote_t *consensus = networkstatus_get_live_consensus(now);
  3359. int n_delayed=0, n_have=0, n_would_reject=0, n_wouldnt_use=0,
  3360. n_inprogress=0;
  3361. if (!dirserver) {
  3362. if (rep_hist_circbuilding_dormant(now))
  3363. return;
  3364. }
  3365. if (!consensus)
  3366. return;
  3367. map = digestmap_new();
  3368. list_pending_descriptor_downloads(map, 0);
  3369. SMARTLIST_FOREACH(consensus->routerstatus_list, routerstatus_t *, rs,
  3370. {
  3371. if (router_get_by_descriptor_digest(rs->descriptor_digest)) {
  3372. ++n_have;
  3373. continue; /* We have it already. */
  3374. }
  3375. if (!download_status_is_ready(&rs->dl_status, now,
  3376. MAX_ROUTERDESC_DOWNLOAD_FAILURES)) {
  3377. ++n_delayed; /* Not ready for retry. */
  3378. continue;
  3379. }
  3380. if (authdir && dirserv_would_reject_router(rs)) {
  3381. ++n_would_reject;
  3382. continue; /* We would throw it out immediately. */
  3383. }
  3384. if (!dirserver && !client_would_use_router(rs, now, options)) {
  3385. ++n_wouldnt_use;
  3386. continue; /* We would never use it ourself. */
  3387. }
  3388. if (digestmap_get(map, rs->descriptor_digest)) {
  3389. ++n_inprogress;
  3390. continue; /* We have an in-progress download. */
  3391. }
  3392. smartlist_add(downloadable, rs->descriptor_digest);
  3393. });
  3394. log_info(LD_DIR,
  3395. "%d routers downloadable. %d delayed; %d present; %d would_reject; "
  3396. "%d wouldnt_use, %d in progress.",
  3397. smartlist_len(downloadable), n_delayed, n_have, n_would_reject,
  3398. n_wouldnt_use, n_inprogress);
  3399. launch_router_descriptor_downloads(downloadable, now);
  3400. smartlist_free(downloadable);
  3401. digestmap_free(map, NULL);
  3402. }
  3403. /** Launch downloads for router status as needed. */
  3404. void
  3405. update_router_descriptor_downloads(time_t now)
  3406. {
  3407. or_options_t *options = get_options();
  3408. if (should_delay_dir_fetches(options))
  3409. return;
  3410. if (dirserver_mode(options)) {
  3411. update_router_descriptor_cache_downloads(now);
  3412. }
  3413. update_consensus_router_descriptor_downloads(now);
  3414. }
  3415. /** Launch extrainfo downloads as needed. */
  3416. void
  3417. update_extrainfo_downloads(time_t now)
  3418. {
  3419. or_options_t *options = get_options();
  3420. routerlist_t *rl;
  3421. smartlist_t *wanted;
  3422. digestmap_t *pending;
  3423. int old_routers, i;
  3424. int n_no_ei = 0, n_pending = 0, n_have = 0, n_delay = 0;
  3425. if (! options->DownloadExtraInfo)
  3426. return;
  3427. if (should_delay_dir_fetches(options))
  3428. return;
  3429. pending = digestmap_new();
  3430. list_pending_descriptor_downloads(pending, 1);
  3431. rl = router_get_routerlist();
  3432. wanted = smartlist_create();
  3433. for (old_routers = 0; old_routers < 2; ++old_routers) {
  3434. smartlist_t *lst = old_routers ? rl->old_routers : rl->routers;
  3435. for (i = 0; i < smartlist_len(lst); ++i) {
  3436. signed_descriptor_t *sd;
  3437. char *d;
  3438. if (old_routers)
  3439. sd = smartlist_get(lst, i);
  3440. else
  3441. sd = &((routerinfo_t*)smartlist_get(lst, i))->cache_info;
  3442. if (sd->is_extrainfo)
  3443. continue; /* This should never happen. */
  3444. d = sd->extra_info_digest;
  3445. if (tor_digest_is_zero(d)) {
  3446. ++n_no_ei;
  3447. continue;
  3448. }
  3449. if (eimap_get(rl->extra_info_map, d)) {
  3450. ++n_have;
  3451. continue;
  3452. }
  3453. if (!download_status_is_ready(&sd->ei_dl_status, now,
  3454. MAX_ROUTERDESC_DOWNLOAD_FAILURES)) {
  3455. ++n_delay;
  3456. continue;
  3457. }
  3458. if (digestmap_get(pending, d)) {
  3459. ++n_pending;
  3460. continue;
  3461. }
  3462. smartlist_add(wanted, d);
  3463. }
  3464. }
  3465. digestmap_free(pending, NULL);
  3466. log_info(LD_DIR, "Extrainfo download status: %d router with no ei, %d "
  3467. "with present ei, %d delaying, %d pending, %d downloadable.",
  3468. n_no_ei, n_have, n_delay, n_pending, smartlist_len(wanted));
  3469. smartlist_shuffle(wanted);
  3470. for (i = 0; i < smartlist_len(wanted); i += MAX_DL_PER_REQUEST) {
  3471. initiate_descriptor_downloads(NULL, DIR_PURPOSE_FETCH_EXTRAINFO,
  3472. wanted, i, i + MAX_DL_PER_REQUEST);
  3473. }
  3474. smartlist_free(wanted);
  3475. }
  3476. /** True iff, the last time we checked whether we had enough directory info
  3477. * to build circuits, the answer was "yes". */
  3478. static int have_min_dir_info = 0;
  3479. /** True iff enough has changed since the last time we checked whether we had
  3480. * enough directory info to build circuits that our old answer can no longer
  3481. * be trusted. */
  3482. static int need_to_update_have_min_dir_info = 1;
  3483. /** Return true iff we have enough networkstatus and router information to
  3484. * start building circuits. Right now, this means "more than half the
  3485. * networkstatus documents, and at least 1/4 of expected routers." */
  3486. //XXX should consider whether we have enough exiting nodes here.
  3487. int
  3488. router_have_minimum_dir_info(void)
  3489. {
  3490. if (PREDICT_UNLIKELY(need_to_update_have_min_dir_info)) {
  3491. update_router_have_minimum_dir_info();
  3492. need_to_update_have_min_dir_info = 0;
  3493. }
  3494. return have_min_dir_info;
  3495. }
  3496. /** Called when our internal view of the directory has changed. This can be
  3497. * when the authorities change, networkstatuses change, the list of routerdescs
  3498. * changes, or number of running routers changes.
  3499. */
  3500. void
  3501. router_dir_info_changed(void)
  3502. {
  3503. need_to_update_have_min_dir_info = 1;
  3504. }
  3505. /** Change the value of have_min_dir_info, setting it true iff we have enough
  3506. * network and router information to build circuits. Clear the value of
  3507. * need_to_update_have_min_dir_info. */
  3508. static void
  3509. update_router_have_minimum_dir_info(void)
  3510. {
  3511. /*XXX020 call when dirserver_mode() changes. */
  3512. int num_present = 0, num_usable=0;
  3513. time_t now = time(NULL);
  3514. int res;
  3515. or_options_t *options = get_options();
  3516. const networkstatus_vote_t *consensus =
  3517. networkstatus_get_live_consensus(now);
  3518. if (!consensus) {
  3519. res = 0;
  3520. goto done;
  3521. }
  3522. if (should_delay_dir_fetches(get_options())) {
  3523. log_notice(LD_DIR, "no known bridge descriptors running yet; stalling");
  3524. res = 0;
  3525. goto done;
  3526. }
  3527. SMARTLIST_FOREACH(consensus->routerstatus_list, routerstatus_t *, rs,
  3528. {
  3529. if (client_would_use_router(rs, now, options)) {
  3530. ++num_usable;
  3531. if (router_get_by_digest(rs->identity_digest)) {
  3532. ++num_present;
  3533. }
  3534. }
  3535. });
  3536. res = num_present >= num_usable/4 && num_usable > 2;
  3537. done:
  3538. if (res && !have_min_dir_info) {
  3539. log(LOG_NOTICE, LD_DIR,
  3540. "We now have enough directory information to build circuits.");
  3541. control_event_client_status(LOG_NOTICE, "ENOUGH_DIR_INFO");
  3542. }
  3543. if (!res && have_min_dir_info) {
  3544. log(LOG_NOTICE, LD_DIR,"Our directory information is no longer up-to-date "
  3545. "enough to build circuits.%s",
  3546. num_usable > 2 ? "" : " (Not enough servers seem reachable -- "
  3547. "is your network connection down?)");
  3548. control_event_client_status(LOG_NOTICE, "NOT_ENOUGH_DIR_INFO");
  3549. }
  3550. have_min_dir_info = res;
  3551. }
  3552. /** Reset the descriptor download failure count on all routers, so that we
  3553. * can retry any long-failed routers immediately.
  3554. */
  3555. void
  3556. router_reset_descriptor_download_failures(void)
  3557. {
  3558. networkstatus_reset_download_failures();
  3559. last_routerdesc_download_attempted = 0;
  3560. if (!routerlist)
  3561. return;
  3562. SMARTLIST_FOREACH(routerlist->routers, routerinfo_t *, ri,
  3563. {
  3564. download_status_reset(&ri->cache_info.ei_dl_status);
  3565. });
  3566. SMARTLIST_FOREACH(routerlist->old_routers, signed_descriptor_t *, sd,
  3567. {
  3568. download_status_reset(&sd->ei_dl_status);
  3569. });
  3570. }
  3571. /** Any changes in a router descriptor's publication time larger than this are
  3572. * automatically non-cosmetic. */
  3573. #define ROUTER_MAX_COSMETIC_TIME_DIFFERENCE (12*60*60)
  3574. /** We allow uptime to vary from how much it ought to be by this much. */
  3575. #define ROUTER_ALLOW_UPTIME_DRIFT (6*60*60)
  3576. /** Return true iff the only differences between r1 and r2 are such that
  3577. * would not cause a recent (post 0.1.1.6) dirserver to republish.
  3578. */
  3579. int
  3580. router_differences_are_cosmetic(routerinfo_t *r1, routerinfo_t *r2)
  3581. {
  3582. time_t r1pub, r2pub;
  3583. int time_difference;
  3584. tor_assert(r1 && r2);
  3585. /* r1 should be the one that was published first. */
  3586. if (r1->cache_info.published_on > r2->cache_info.published_on) {
  3587. routerinfo_t *ri_tmp = r2;
  3588. r2 = r1;
  3589. r1 = ri_tmp;
  3590. }
  3591. /* If any key fields differ, they're different. */
  3592. if (strcasecmp(r1->address, r2->address) ||
  3593. strcasecmp(r1->nickname, r2->nickname) ||
  3594. r1->or_port != r2->or_port ||
  3595. r1->dir_port != r2->dir_port ||
  3596. crypto_pk_cmp_keys(r1->onion_pkey, r2->onion_pkey) ||
  3597. crypto_pk_cmp_keys(r1->identity_pkey, r2->identity_pkey) ||
  3598. strcasecmp(r1->platform, r2->platform) ||
  3599. (r1->contact_info && !r2->contact_info) || /* contact_info is optional */
  3600. (!r1->contact_info && r2->contact_info) ||
  3601. (r1->contact_info && r2->contact_info &&
  3602. strcasecmp(r1->contact_info, r2->contact_info)) ||
  3603. r1->is_hibernating != r2->is_hibernating ||
  3604. r1->has_old_dnsworkers != r2->has_old_dnsworkers ||
  3605. cmp_addr_policies(r1->exit_policy, r2->exit_policy))
  3606. return 0;
  3607. if ((r1->declared_family == NULL) != (r2->declared_family == NULL))
  3608. return 0;
  3609. if (r1->declared_family && r2->declared_family) {
  3610. int i, n;
  3611. if (smartlist_len(r1->declared_family)!=smartlist_len(r2->declared_family))
  3612. return 0;
  3613. n = smartlist_len(r1->declared_family);
  3614. for (i=0; i < n; ++i) {
  3615. if (strcasecmp(smartlist_get(r1->declared_family, i),
  3616. smartlist_get(r2->declared_family, i)))
  3617. return 0;
  3618. }
  3619. }
  3620. /* Did bandwidth change a lot? */
  3621. if ((r1->bandwidthcapacity < r2->bandwidthcapacity/2) ||
  3622. (r2->bandwidthcapacity < r1->bandwidthcapacity/2))
  3623. return 0;
  3624. /* Did more than 12 hours pass? */
  3625. if (r1->cache_info.published_on + ROUTER_MAX_COSMETIC_TIME_DIFFERENCE
  3626. < r2->cache_info.published_on)
  3627. return 0;
  3628. /* Did uptime fail to increase by approximately the amount we would think,
  3629. * give or take some slop? */
  3630. r1pub = r1->cache_info.published_on;
  3631. r2pub = r2->cache_info.published_on;
  3632. time_difference = abs(r2->uptime - (r1->uptime + (r2pub - r1pub)));
  3633. if (time_difference > ROUTER_ALLOW_UPTIME_DRIFT &&
  3634. time_difference > r1->uptime * .05 &&
  3635. time_difference > r2->uptime * .05)
  3636. return 0;
  3637. /* Otherwise, the difference is cosmetic. */
  3638. return 1;
  3639. }
  3640. /** Check whether <b>ri</b> is a router compatible with the extrainfo document
  3641. * <b>ei</b>. If no router is compatible with <b>ei</b>, <b>ei</b> should be
  3642. * dropped. Return 0 for "compatible", return 1 for "reject, and inform
  3643. * whoever uploaded <b>ei</b>, and return -1 for "reject silently.". If
  3644. * <b>msg</b> is present, set *<b>msg</b> to a description of the
  3645. * incompatibility (if any). */
  3646. int
  3647. routerinfo_incompatible_with_extrainfo(routerinfo_t *ri, extrainfo_t *ei,
  3648. const char **msg)
  3649. {
  3650. tor_assert(ri);
  3651. tor_assert(ei);
  3652. if (ei->bad_sig) {
  3653. if (msg) *msg = "Extrainfo signature was bad, or signed with wrong key.";
  3654. return 1;
  3655. }
  3656. /* The nickname must match exactly to have been generated at the same time
  3657. * by the same router. */
  3658. if (strcmp(ri->nickname, ei->nickname) ||
  3659. memcmp(ri->cache_info.identity_digest, ei->cache_info.identity_digest,
  3660. DIGEST_LEN)) {
  3661. if (msg) *msg = "Extrainfo nickname or identity did not match routerinfo";
  3662. return 1; /* different servers */
  3663. }
  3664. if (ei->pending_sig) {
  3665. char signed_digest[128];
  3666. if (crypto_pk_public_checksig(ri->identity_pkey, signed_digest,
  3667. ei->pending_sig, ei->pending_sig_len) != DIGEST_LEN ||
  3668. memcmp(signed_digest, ei->cache_info.signed_descriptor_digest,
  3669. DIGEST_LEN)) {
  3670. ei->bad_sig = 1;
  3671. tor_free(ei->pending_sig);
  3672. if (msg) *msg = "Extrainfo signature bad, or signed with wrong key";
  3673. return 1; /* Bad signature, or no match. */
  3674. }
  3675. tor_free(ei->pending_sig);
  3676. }
  3677. if (ei->cache_info.published_on < ri->cache_info.published_on) {
  3678. if (msg) *msg = "Extrainfo published time did not match routerdesc";
  3679. return 1;
  3680. } else if (ei->cache_info.published_on > ri->cache_info.published_on) {
  3681. if (msg) *msg = "Extrainfo published time did not match routerdesc";
  3682. return -1;
  3683. }
  3684. if (memcmp(ei->cache_info.signed_descriptor_digest,
  3685. ri->cache_info.extra_info_digest, DIGEST_LEN)) {
  3686. if (msg) *msg = "Extrainfo digest did not match value from routerdesc";
  3687. return 1; /* Digest doesn't match declared value. */
  3688. }
  3689. return 0;
  3690. }
  3691. /** Assert that the internal representation of <b>rl</b> is
  3692. * self-consistent. */
  3693. void
  3694. routerlist_assert_ok(routerlist_t *rl)
  3695. {
  3696. digestmap_iter_t *iter; /* XXXX020 use the appropriate iter type. */
  3697. routerinfo_t *r2;
  3698. signed_descriptor_t *sd2;
  3699. if (!rl)
  3700. return;
  3701. SMARTLIST_FOREACH(rl->routers, routerinfo_t *, r,
  3702. {
  3703. r2 = rimap_get(rl->identity_map, r->cache_info.identity_digest);
  3704. tor_assert(r == r2);
  3705. sd2 = sdmap_get(rl->desc_digest_map,
  3706. r->cache_info.signed_descriptor_digest);
  3707. tor_assert(&(r->cache_info) == sd2);
  3708. tor_assert(r->routerlist_index == r_sl_idx);
  3709. #if 0
  3710. /* XXXX020.
  3711. *
  3712. * Hoo boy. We need to fix this one, and the fix is a bit tricky, so
  3713. * commenting this out is just a band-aid.
  3714. *
  3715. * The problem is that, although well-behaved router descriptors
  3716. * should never have the same value for their extra_info_digest, it's
  3717. * possible for ill-behaved routers to claim whatever they like there.
  3718. *
  3719. * The real answer is to trash desc_by_eid_map and instead have
  3720. * something that indicates for a given extra-info digest we want,
  3721. * what its download status is. We'll do that as a part of routerlist
  3722. * refactoring once consensus directories are in. For now,
  3723. * this rep violation is probably harmless: an adversary can make us
  3724. * reset our retry count for an extrainfo, but that's not the end
  3725. * of the world.
  3726. */
  3727. if (!tor_digest_is_zero(r->cache_info.extra_info_digest)) {
  3728. signed_descriptor_t *sd3 =
  3729. sdmap_get(rl->desc_by_eid_map, r->cache_info.extra_info_digest);
  3730. tor_assert(sd3 == &(r->cache_info));
  3731. }
  3732. #endif
  3733. });
  3734. SMARTLIST_FOREACH(rl->old_routers, signed_descriptor_t *, sd,
  3735. {
  3736. r2 = rimap_get(rl->identity_map, sd->identity_digest);
  3737. tor_assert(sd != &(r2->cache_info));
  3738. sd2 = sdmap_get(rl->desc_digest_map, sd->signed_descriptor_digest);
  3739. tor_assert(sd == sd2);
  3740. #if 0
  3741. /* XXXX020 see above. */
  3742. if (!tor_digest_is_zero(sd->extra_info_digest)) {
  3743. signed_descriptor_t *sd3 =
  3744. sdmap_get(rl->desc_by_eid_map, sd->extra_info_digest);
  3745. tor_assert(sd3 == sd);
  3746. }
  3747. #endif
  3748. });
  3749. iter = digestmap_iter_init((digestmap_t*)rl->identity_map);
  3750. while (!digestmap_iter_done(iter)) {
  3751. const char *d;
  3752. void *_r;
  3753. routerinfo_t *r;
  3754. digestmap_iter_get(iter, &d, &_r);
  3755. r = _r;
  3756. tor_assert(!memcmp(r->cache_info.identity_digest, d, DIGEST_LEN));
  3757. iter = digestmap_iter_next((digestmap_t*)rl->identity_map, iter);
  3758. }
  3759. iter = digestmap_iter_init((digestmap_t*)rl->desc_digest_map);
  3760. while (!digestmap_iter_done(iter)) {
  3761. const char *d;
  3762. void *_sd;
  3763. signed_descriptor_t *sd;
  3764. digestmap_iter_get(iter, &d, &_sd);
  3765. sd = _sd;
  3766. tor_assert(!memcmp(sd->signed_descriptor_digest, d, DIGEST_LEN));
  3767. iter = digestmap_iter_next((digestmap_t*)rl->desc_digest_map, iter);
  3768. }
  3769. iter = digestmap_iter_init((digestmap_t*)rl->desc_by_eid_map);
  3770. while (!digestmap_iter_done(iter)) {
  3771. const char *d;
  3772. void *_sd;
  3773. signed_descriptor_t *sd;
  3774. digestmap_iter_get(iter, &d, &_sd);
  3775. sd = _sd;
  3776. tor_assert(!tor_digest_is_zero(d));
  3777. tor_assert(sd);
  3778. tor_assert(!memcmp(sd->extra_info_digest, d, DIGEST_LEN));
  3779. iter = digestmap_iter_next((digestmap_t*)rl->desc_by_eid_map, iter);
  3780. }
  3781. iter = digestmap_iter_init((digestmap_t*)rl->extra_info_map);
  3782. while (!digestmap_iter_done(iter)) {
  3783. const char *d;
  3784. void *_ei;
  3785. extrainfo_t *ei;
  3786. signed_descriptor_t *sd;
  3787. digestmap_iter_get(iter, &d, &_ei);
  3788. ei = _ei;
  3789. tor_assert(!memcmp(ei->cache_info.signed_descriptor_digest,
  3790. d, DIGEST_LEN));
  3791. sd = sdmap_get(rl->desc_by_eid_map,
  3792. ei->cache_info.signed_descriptor_digest);
  3793. // tor_assert(sd); // XXXX020 see above
  3794. if (sd) {
  3795. tor_assert(!memcmp(ei->cache_info.signed_descriptor_digest,
  3796. sd->extra_info_digest, DIGEST_LEN));
  3797. }
  3798. iter = digestmap_iter_next((digestmap_t*)rl->extra_info_map, iter);
  3799. }
  3800. }
  3801. /** Allocate and return a new string representing the contact info
  3802. * and platform string for <b>router</b>,
  3803. * surrounded by quotes and using standard C escapes.
  3804. *
  3805. * THIS FUNCTION IS NOT REENTRANT. Don't call it from outside the main
  3806. * thread. Also, each call invalidates the last-returned value, so don't
  3807. * try log_warn(LD_GENERAL, "%s %s", esc_router_info(a), esc_router_info(b));
  3808. *
  3809. * If <b>router</b> is NULL, it just frees its internal memory and returns.
  3810. */
  3811. const char *
  3812. esc_router_info(routerinfo_t *router)
  3813. {
  3814. static char *info=NULL;
  3815. char *esc_contact, *esc_platform;
  3816. size_t len;
  3817. if (info)
  3818. tor_free(info);
  3819. if (!router)
  3820. return NULL; /* we're exiting; just free the memory we use */
  3821. esc_contact = esc_for_log(router->contact_info);
  3822. esc_platform = esc_for_log(router->platform);
  3823. len = strlen(esc_contact)+strlen(esc_platform)+32;
  3824. info = tor_malloc(len);
  3825. tor_snprintf(info, len, "Contact %s, Platform %s", esc_contact,
  3826. esc_platform);
  3827. tor_free(esc_contact);
  3828. tor_free(esc_platform);
  3829. return info;
  3830. }
  3831. /** Helper for sorting: compare two routerinfos by their identity
  3832. * digest. */
  3833. static int
  3834. _compare_routerinfo_by_id_digest(const void **a, const void **b)
  3835. {
  3836. routerinfo_t *first = *(routerinfo_t **)a, *second = *(routerinfo_t **)b;
  3837. return memcmp(first->cache_info.identity_digest,
  3838. second->cache_info.identity_digest,
  3839. DIGEST_LEN);
  3840. }
  3841. /** Sort a list of routerinfo_t in ascending order of identity digest. */
  3842. void
  3843. routers_sort_by_identity(smartlist_t *routers)
  3844. {
  3845. smartlist_sort(routers, _compare_routerinfo_by_id_digest);
  3846. }