routerlist.c 201 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623162416251626162716281629163016311632163316341635163616371638163916401641164216431644164516461647164816491650165116521653165416551656165716581659166016611662166316641665166616671668166916701671167216731674167516761677167816791680168116821683168416851686168716881689169016911692169316941695169616971698169917001701170217031704170517061707170817091710171117121713171417151716171717181719172017211722172317241725172617271728172917301731173217331734173517361737173817391740174117421743174417451746174717481749175017511752175317541755175617571758175917601761176217631764176517661767176817691770177117721773177417751776177717781779178017811782178317841785178617871788178917901791179217931794179517961797179817991800180118021803180418051806180718081809181018111812181318141815181618171818181918201821182218231824182518261827182818291830183118321833183418351836183718381839184018411842184318441845184618471848184918501851185218531854185518561857185818591860186118621863186418651866186718681869187018711872187318741875187618771878187918801881188218831884188518861887188818891890189118921893189418951896189718981899190019011902190319041905190619071908190919101911191219131914191519161917191819191920192119221923192419251926192719281929193019311932193319341935193619371938193919401941194219431944194519461947194819491950195119521953195419551956195719581959196019611962196319641965196619671968196919701971197219731974197519761977197819791980198119821983198419851986198719881989199019911992199319941995199619971998199920002001200220032004200520062007200820092010201120122013201420152016201720182019202020212022202320242025202620272028202920302031203220332034203520362037203820392040204120422043204420452046204720482049205020512052205320542055205620572058205920602061206220632064206520662067206820692070207120722073207420752076207720782079208020812082208320842085208620872088208920902091209220932094209520962097209820992100210121022103210421052106210721082109211021112112211321142115211621172118211921202121212221232124212521262127212821292130213121322133213421352136213721382139214021412142214321442145214621472148214921502151215221532154215521562157215821592160216121622163216421652166216721682169217021712172217321742175217621772178217921802181218221832184218521862187218821892190219121922193219421952196219721982199220022012202220322042205220622072208220922102211221222132214221522162217221822192220222122222223222422252226222722282229223022312232223322342235223622372238223922402241224222432244224522462247224822492250225122522253225422552256225722582259226022612262226322642265226622672268226922702271227222732274227522762277227822792280228122822283228422852286228722882289229022912292229322942295229622972298229923002301230223032304230523062307230823092310231123122313231423152316231723182319232023212322232323242325232623272328232923302331233223332334233523362337233823392340234123422343234423452346234723482349235023512352235323542355235623572358235923602361236223632364236523662367236823692370237123722373237423752376237723782379238023812382238323842385238623872388238923902391239223932394239523962397239823992400240124022403240424052406240724082409241024112412241324142415241624172418241924202421242224232424242524262427242824292430243124322433243424352436243724382439244024412442244324442445244624472448244924502451245224532454245524562457245824592460246124622463246424652466246724682469247024712472247324742475247624772478247924802481248224832484248524862487248824892490249124922493249424952496249724982499250025012502250325042505250625072508250925102511251225132514251525162517251825192520252125222523252425252526252725282529253025312532253325342535253625372538253925402541254225432544254525462547254825492550255125522553255425552556255725582559256025612562256325642565256625672568256925702571257225732574257525762577257825792580258125822583258425852586258725882589259025912592259325942595259625972598259926002601260226032604260526062607260826092610261126122613261426152616261726182619262026212622262326242625262626272628262926302631263226332634263526362637263826392640264126422643264426452646264726482649265026512652265326542655265626572658265926602661266226632664266526662667266826692670267126722673267426752676267726782679268026812682268326842685268626872688268926902691269226932694269526962697269826992700270127022703270427052706270727082709271027112712271327142715271627172718271927202721272227232724272527262727272827292730273127322733273427352736273727382739274027412742274327442745274627472748274927502751275227532754275527562757275827592760276127622763276427652766276727682769277027712772277327742775277627772778277927802781278227832784278527862787278827892790279127922793279427952796279727982799280028012802280328042805280628072808280928102811281228132814281528162817281828192820282128222823282428252826282728282829283028312832283328342835283628372838283928402841284228432844284528462847284828492850285128522853285428552856285728582859286028612862286328642865286628672868286928702871287228732874287528762877287828792880288128822883288428852886288728882889289028912892289328942895289628972898289929002901290229032904290529062907290829092910291129122913291429152916291729182919292029212922292329242925292629272928292929302931293229332934293529362937293829392940294129422943294429452946294729482949295029512952295329542955295629572958295929602961296229632964296529662967296829692970297129722973297429752976297729782979298029812982298329842985298629872988298929902991299229932994299529962997299829993000300130023003300430053006300730083009301030113012301330143015301630173018301930203021302230233024302530263027302830293030303130323033303430353036303730383039304030413042304330443045304630473048304930503051305230533054305530563057305830593060306130623063306430653066306730683069307030713072307330743075307630773078307930803081308230833084308530863087308830893090309130923093309430953096309730983099310031013102310331043105310631073108310931103111311231133114311531163117311831193120312131223123312431253126312731283129313031313132313331343135313631373138313931403141314231433144314531463147314831493150315131523153315431553156315731583159316031613162316331643165316631673168316931703171317231733174317531763177317831793180318131823183318431853186318731883189319031913192319331943195319631973198319932003201320232033204320532063207320832093210321132123213321432153216321732183219322032213222322332243225322632273228322932303231323232333234323532363237323832393240324132423243324432453246324732483249325032513252325332543255325632573258325932603261326232633264326532663267326832693270327132723273327432753276327732783279328032813282328332843285328632873288328932903291329232933294329532963297329832993300330133023303330433053306330733083309331033113312331333143315331633173318331933203321332233233324332533263327332833293330333133323333333433353336333733383339334033413342334333443345334633473348334933503351335233533354335533563357335833593360336133623363336433653366336733683369337033713372337333743375337633773378337933803381338233833384338533863387338833893390339133923393339433953396339733983399340034013402340334043405340634073408340934103411341234133414341534163417341834193420342134223423342434253426342734283429343034313432343334343435343634373438343934403441344234433444344534463447344834493450345134523453345434553456345734583459346034613462346334643465346634673468346934703471347234733474347534763477347834793480348134823483348434853486348734883489349034913492349334943495349634973498349935003501350235033504350535063507350835093510351135123513351435153516351735183519352035213522352335243525352635273528352935303531353235333534353535363537353835393540354135423543354435453546354735483549355035513552355335543555355635573558355935603561356235633564356535663567356835693570357135723573357435753576357735783579358035813582358335843585358635873588358935903591359235933594359535963597359835993600360136023603360436053606360736083609361036113612361336143615361636173618361936203621362236233624362536263627362836293630363136323633363436353636363736383639364036413642364336443645364636473648364936503651365236533654365536563657365836593660366136623663366436653666366736683669367036713672367336743675367636773678367936803681368236833684368536863687368836893690369136923693369436953696369736983699370037013702370337043705370637073708370937103711371237133714371537163717371837193720372137223723372437253726372737283729373037313732373337343735373637373738373937403741374237433744374537463747374837493750375137523753375437553756375737583759376037613762376337643765376637673768376937703771377237733774377537763777377837793780378137823783378437853786378737883789379037913792379337943795379637973798379938003801380238033804380538063807380838093810381138123813381438153816381738183819382038213822382338243825382638273828382938303831383238333834383538363837383838393840384138423843384438453846384738483849385038513852385338543855385638573858385938603861386238633864386538663867386838693870387138723873387438753876387738783879388038813882388338843885388638873888388938903891389238933894389538963897389838993900390139023903390439053906390739083909391039113912391339143915391639173918391939203921392239233924392539263927392839293930393139323933393439353936393739383939394039413942394339443945394639473948394939503951395239533954395539563957395839593960396139623963396439653966396739683969397039713972397339743975397639773978397939803981398239833984398539863987398839893990399139923993399439953996399739983999400040014002400340044005400640074008400940104011401240134014401540164017401840194020402140224023402440254026402740284029403040314032403340344035403640374038403940404041404240434044404540464047404840494050405140524053405440554056405740584059406040614062406340644065406640674068406940704071407240734074407540764077407840794080408140824083408440854086408740884089409040914092409340944095409640974098409941004101410241034104410541064107410841094110411141124113411441154116411741184119412041214122412341244125412641274128412941304131413241334134413541364137413841394140414141424143414441454146414741484149415041514152415341544155415641574158415941604161416241634164416541664167416841694170417141724173417441754176417741784179418041814182418341844185418641874188418941904191419241934194419541964197419841994200420142024203420442054206420742084209421042114212421342144215421642174218421942204221422242234224422542264227422842294230423142324233423442354236423742384239424042414242424342444245424642474248424942504251425242534254425542564257425842594260426142624263426442654266426742684269427042714272427342744275427642774278427942804281428242834284428542864287428842894290429142924293429442954296429742984299430043014302430343044305430643074308430943104311431243134314431543164317431843194320432143224323432443254326432743284329433043314332433343344335433643374338433943404341434243434344434543464347434843494350435143524353435443554356435743584359436043614362436343644365436643674368436943704371437243734374437543764377437843794380438143824383438443854386438743884389439043914392439343944395439643974398439944004401440244034404440544064407440844094410441144124413441444154416441744184419442044214422442344244425442644274428442944304431443244334434443544364437443844394440444144424443444444454446444744484449445044514452445344544455445644574458445944604461446244634464446544664467446844694470447144724473447444754476447744784479448044814482448344844485448644874488448944904491449244934494449544964497449844994500450145024503450445054506450745084509451045114512451345144515451645174518451945204521452245234524452545264527452845294530453145324533453445354536453745384539454045414542454345444545454645474548454945504551455245534554455545564557455845594560456145624563456445654566456745684569457045714572457345744575457645774578457945804581458245834584458545864587458845894590459145924593459445954596459745984599460046014602460346044605460646074608460946104611461246134614461546164617461846194620462146224623462446254626462746284629463046314632463346344635463646374638463946404641464246434644464546464647464846494650465146524653465446554656465746584659466046614662466346644665466646674668466946704671467246734674467546764677467846794680468146824683468446854686468746884689469046914692469346944695469646974698469947004701470247034704470547064707470847094710471147124713471447154716471747184719472047214722472347244725472647274728472947304731473247334734473547364737473847394740474147424743474447454746474747484749475047514752475347544755475647574758475947604761476247634764476547664767476847694770477147724773477447754776477747784779478047814782478347844785478647874788478947904791479247934794479547964797479847994800480148024803480448054806480748084809481048114812481348144815481648174818481948204821482248234824482548264827482848294830483148324833483448354836483748384839484048414842484348444845484648474848484948504851485248534854485548564857485848594860486148624863486448654866486748684869487048714872487348744875487648774878487948804881488248834884488548864887488848894890489148924893489448954896489748984899490049014902490349044905490649074908490949104911491249134914491549164917491849194920492149224923492449254926492749284929493049314932493349344935493649374938493949404941494249434944494549464947494849494950495149524953495449554956495749584959496049614962496349644965496649674968496949704971497249734974497549764977497849794980498149824983498449854986498749884989499049914992499349944995499649974998499950005001500250035004500550065007500850095010501150125013501450155016501750185019502050215022502350245025502650275028502950305031503250335034503550365037503850395040504150425043504450455046504750485049505050515052505350545055505650575058505950605061506250635064506550665067506850695070507150725073507450755076507750785079508050815082508350845085508650875088508950905091509250935094509550965097509850995100510151025103510451055106510751085109511051115112511351145115511651175118511951205121512251235124512551265127512851295130513151325133513451355136513751385139514051415142514351445145514651475148514951505151515251535154515551565157515851595160516151625163516451655166516751685169517051715172517351745175517651775178517951805181518251835184518551865187518851895190519151925193519451955196519751985199520052015202520352045205520652075208520952105211521252135214521552165217521852195220522152225223522452255226522752285229523052315232523352345235523652375238523952405241524252435244524552465247524852495250525152525253525452555256525752585259526052615262526352645265526652675268526952705271527252735274527552765277527852795280528152825283528452855286528752885289529052915292529352945295529652975298529953005301530253035304530553065307530853095310531153125313531453155316531753185319532053215322532353245325532653275328532953305331533253335334533553365337533853395340534153425343534453455346534753485349535053515352535353545355535653575358535953605361536253635364536553665367536853695370537153725373537453755376537753785379538053815382538353845385538653875388538953905391539253935394539553965397539853995400540154025403540454055406540754085409541054115412541354145415541654175418541954205421542254235424542554265427542854295430543154325433543454355436543754385439544054415442544354445445544654475448544954505451545254535454545554565457545854595460546154625463546454655466546754685469547054715472547354745475547654775478547954805481548254835484548554865487548854895490549154925493549454955496549754985499550055015502550355045505550655075508550955105511551255135514551555165517551855195520552155225523552455255526552755285529553055315532553355345535553655375538553955405541554255435544554555465547554855495550555155525553555455555556555755585559556055615562556355645565556655675568556955705571557255735574557555765577557855795580558155825583558455855586558755885589559055915592559355945595559655975598559956005601560256035604560556065607560856095610561156125613561456155616561756185619562056215622562356245625562656275628562956305631563256335634563556365637563856395640564156425643564456455646564756485649565056515652565356545655565656575658565956605661566256635664566556665667566856695670567156725673567456755676567756785679568056815682568356845685568656875688568956905691569256935694569556965697569856995700570157025703570457055706570757085709571057115712571357145715571657175718571957205721572257235724572557265727572857295730573157325733573457355736573757385739574057415742574357445745574657475748574957505751575257535754575557565757575857595760576157625763576457655766576757685769577057715772577357745775577657775778577957805781578257835784578557865787578857895790579157925793579457955796579757985799580058015802580358045805580658075808580958105811581258135814581558165817581858195820582158225823582458255826582758285829583058315832583358345835583658375838583958405841584258435844584558465847584858495850585158525853585458555856585758585859586058615862586358645865586658675868586958705871587258735874587558765877587858795880588158825883588458855886588758885889589058915892589358945895589658975898589959005901590259035904590559065907590859095910591159125913591459155916591759185919592059215922592359245925592659275928592959305931
  1. /* Copyright (c) 2001 Matej Pfajfar.
  2. * Copyright (c) 2001-2004, Roger Dingledine.
  3. * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
  4. * Copyright (c) 2007-2011, The Tor Project, Inc. */
  5. /* See LICENSE for licensing information */
  6. /**
  7. * \file routerlist.c
  8. * \brief Code to
  9. * maintain and access the global list of routerinfos for known
  10. * servers.
  11. **/
  12. #include "or.h"
  13. #include "circuitbuild.h"
  14. #include "config.h"
  15. #include "connection.h"
  16. #include "control.h"
  17. #include "directory.h"
  18. #include "dirserv.h"
  19. #include "dirvote.h"
  20. #include "geoip.h"
  21. #include "hibernate.h"
  22. #include "main.h"
  23. #include "microdesc.h"
  24. #include "networkstatus.h"
  25. #include "nodelist.h"
  26. #include "policies.h"
  27. #include "reasons.h"
  28. #include "rendcommon.h"
  29. #include "rendservice.h"
  30. #include "rephist.h"
  31. #include "router.h"
  32. #include "routerlist.h"
  33. #include "routerparse.h"
  34. // #define DEBUG_ROUTERLIST
  35. /****************************************************************************/
  36. /* static function prototypes */
  37. static const routerstatus_t *router_pick_directory_server_impl(
  38. dirinfo_type_t auth, int flags);
  39. static const routerstatus_t *router_pick_trusteddirserver_impl(
  40. dirinfo_type_t auth, int flags, int *n_busy_out);
  41. static void mark_all_trusteddirservers_up(void);
  42. static int router_nickname_matches(const routerinfo_t *router,
  43. const char *nickname);
  44. static int node_nickname_matches(const node_t *router,
  45. const char *nickname);
  46. static void trusted_dir_server_free(trusted_dir_server_t *ds);
  47. static int signed_desc_digest_is_recognized(signed_descriptor_t *desc);
  48. static void update_router_have_minimum_dir_info(void);
  49. static const char *signed_descriptor_get_body_impl(
  50. const signed_descriptor_t *desc,
  51. int with_annotations);
  52. static void list_pending_downloads(digestmap_t *result,
  53. int purpose, const char *prefix);
  54. static void launch_dummy_descriptor_download_as_needed(time_t now,
  55. const or_options_t *options);
  56. DECLARE_TYPED_DIGESTMAP_FNS(sdmap_, digest_sd_map_t, signed_descriptor_t)
  57. DECLARE_TYPED_DIGESTMAP_FNS(rimap_, digest_ri_map_t, routerinfo_t)
  58. DECLARE_TYPED_DIGESTMAP_FNS(eimap_, digest_ei_map_t, extrainfo_t)
  59. #define SDMAP_FOREACH(map, keyvar, valvar) \
  60. DIGESTMAP_FOREACH(sdmap_to_digestmap(map), keyvar, signed_descriptor_t *, \
  61. valvar)
  62. #define RIMAP_FOREACH(map, keyvar, valvar) \
  63. DIGESTMAP_FOREACH(rimap_to_digestmap(map), keyvar, routerinfo_t *, valvar)
  64. #define EIMAP_FOREACH(map, keyvar, valvar) \
  65. DIGESTMAP_FOREACH(eimap_to_digestmap(map), keyvar, extrainfo_t *, valvar)
  66. /****************************************************************************/
  67. /** Global list of a trusted_dir_server_t object for each trusted directory
  68. * server. */
  69. static smartlist_t *trusted_dir_servers = NULL;
  70. /** List of for a given authority, and download status for latest certificate.
  71. */
  72. typedef struct cert_list_t {
  73. download_status_t dl_status;
  74. smartlist_t *certs;
  75. } cert_list_t;
  76. /** Map from v3 identity key digest to cert_list_t. */
  77. static digestmap_t *trusted_dir_certs = NULL;
  78. /** True iff any key certificate in at least one member of
  79. * <b>trusted_dir_certs</b> has changed since we last flushed the
  80. * certificates to disk. */
  81. static int trusted_dir_servers_certs_changed = 0;
  82. /** Global list of all of the routers that we know about. */
  83. static routerlist_t *routerlist = NULL;
  84. /** List of strings for nicknames we've already warned about and that are
  85. * still unknown / unavailable. */
  86. static smartlist_t *warned_nicknames = NULL;
  87. /** The last time we tried to download any routerdesc, or 0 for "never". We
  88. * use this to rate-limit download attempts when the number of routerdescs to
  89. * download is low. */
  90. static time_t last_descriptor_download_attempted = 0;
  91. /** When we last computed the weights to use for bandwidths on directory
  92. * requests, what were the total weighted bandwidth, and our share of that
  93. * bandwidth? Used to determine what fraction of directory requests we should
  94. * expect to see.
  95. *
  96. * @{ */
  97. static uint64_t sl_last_total_weighted_bw = 0,
  98. sl_last_weighted_bw_of_me = 0;
  99. /**@}*/
  100. /** Return the number of directory authorities whose type matches some bit set
  101. * in <b>type</b> */
  102. int
  103. get_n_authorities(dirinfo_type_t type)
  104. {
  105. int n = 0;
  106. if (!trusted_dir_servers)
  107. return 0;
  108. SMARTLIST_FOREACH(trusted_dir_servers, trusted_dir_server_t *, ds,
  109. if (ds->type & type)
  110. ++n);
  111. return n;
  112. }
  113. #define get_n_v2_authorities() get_n_authorities(V2_DIRINFO)
  114. /** Helper: Return the cert_list_t for an authority whose authority ID is
  115. * <b>id_digest</b>, allocating a new list if necessary. */
  116. static cert_list_t *
  117. get_cert_list(const char *id_digest)
  118. {
  119. cert_list_t *cl;
  120. if (!trusted_dir_certs)
  121. trusted_dir_certs = digestmap_new();
  122. cl = digestmap_get(trusted_dir_certs, id_digest);
  123. if (!cl) {
  124. cl = tor_malloc_zero(sizeof(cert_list_t));
  125. cl->dl_status.schedule = DL_SCHED_CONSENSUS;
  126. cl->certs = smartlist_new();
  127. digestmap_set(trusted_dir_certs, id_digest, cl);
  128. }
  129. return cl;
  130. }
  131. /** Reload the cached v3 key certificates from the cached-certs file in
  132. * the data directory. Return 0 on success, -1 on failure. */
  133. int
  134. trusted_dirs_reload_certs(void)
  135. {
  136. char *filename;
  137. char *contents;
  138. int r;
  139. filename = get_datadir_fname("cached-certs");
  140. contents = read_file_to_str(filename, RFTS_IGNORE_MISSING, NULL);
  141. tor_free(filename);
  142. if (!contents)
  143. return 0;
  144. r = trusted_dirs_load_certs_from_string(contents, 1, 1);
  145. tor_free(contents);
  146. return r;
  147. }
  148. /** Helper: return true iff we already have loaded the exact cert
  149. * <b>cert</b>. */
  150. static INLINE int
  151. already_have_cert(authority_cert_t *cert)
  152. {
  153. cert_list_t *cl = get_cert_list(cert->cache_info.identity_digest);
  154. SMARTLIST_FOREACH(cl->certs, authority_cert_t *, c,
  155. {
  156. if (tor_memeq(c->cache_info.signed_descriptor_digest,
  157. cert->cache_info.signed_descriptor_digest,
  158. DIGEST_LEN))
  159. return 1;
  160. });
  161. return 0;
  162. }
  163. /** Load a bunch of new key certificates from the string <b>contents</b>. If
  164. * <b>from_store</b> is true, the certificates are from the cache, and we
  165. * don't need to flush them to disk. If <b>flush</b> is true, we need
  166. * to flush any changed certificates to disk now. Return 0 on success, -1
  167. * if any certs fail to parse. */
  168. int
  169. trusted_dirs_load_certs_from_string(const char *contents, int from_store,
  170. int flush)
  171. {
  172. trusted_dir_server_t *ds;
  173. const char *s, *eos;
  174. int failure_code = 0;
  175. for (s = contents; *s; s = eos) {
  176. authority_cert_t *cert = authority_cert_parse_from_string(s, &eos);
  177. cert_list_t *cl;
  178. if (!cert) {
  179. failure_code = -1;
  180. break;
  181. }
  182. ds = trusteddirserver_get_by_v3_auth_digest(
  183. cert->cache_info.identity_digest);
  184. log_debug(LD_DIR, "Parsed certificate for %s",
  185. ds ? ds->nickname : "unknown authority");
  186. if (already_have_cert(cert)) {
  187. /* we already have this one. continue. */
  188. log_info(LD_DIR, "Skipping %s certificate for %s that we "
  189. "already have.",
  190. from_store ? "cached" : "downloaded",
  191. ds ? ds->nickname : "an old or new authority");
  192. /* a duplicate on a download should be treated as a failure, since it
  193. * probably means we wanted a different secret key or we are trying to
  194. * replace an expired cert that has not in fact been updated. */
  195. if (!from_store) {
  196. log_warn(LD_DIR, "Got a certificate for %s, but we already have it. "
  197. "Maybe they haven't updated it. Waiting for a while.",
  198. ds ? ds->nickname : "an old or new authority");
  199. authority_cert_dl_failed(cert->cache_info.identity_digest, 404);
  200. }
  201. authority_cert_free(cert);
  202. continue;
  203. }
  204. if (ds) {
  205. log_info(LD_DIR, "Adding %s certificate for directory authority %s with "
  206. "signing key %s", from_store ? "cached" : "downloaded",
  207. ds->nickname, hex_str(cert->signing_key_digest,DIGEST_LEN));
  208. } else {
  209. int adding = directory_caches_unknown_auth_certs(get_options());
  210. log_info(LD_DIR, "%s %s certificate for unrecognized directory "
  211. "authority with signing key %s",
  212. adding ? "Adding" : "Not adding",
  213. from_store ? "cached" : "downloaded",
  214. hex_str(cert->signing_key_digest,DIGEST_LEN));
  215. if (!adding) {
  216. authority_cert_free(cert);
  217. continue;
  218. }
  219. }
  220. cl = get_cert_list(cert->cache_info.identity_digest);
  221. smartlist_add(cl->certs, cert);
  222. if (ds && cert->cache_info.published_on > ds->addr_current_at) {
  223. /* Check to see whether we should update our view of the authority's
  224. * address. */
  225. if (cert->addr && cert->dir_port &&
  226. (ds->addr != cert->addr ||
  227. ds->dir_port != cert->dir_port)) {
  228. char *a = tor_dup_ip(cert->addr);
  229. log_notice(LD_DIR, "Updating address for directory authority %s "
  230. "from %s:%d to %s:%d based on certificate.",
  231. ds->nickname, ds->address, (int)ds->dir_port,
  232. a, cert->dir_port);
  233. tor_free(a);
  234. ds->addr = cert->addr;
  235. ds->dir_port = cert->dir_port;
  236. }
  237. ds->addr_current_at = cert->cache_info.published_on;
  238. }
  239. if (!from_store)
  240. trusted_dir_servers_certs_changed = 1;
  241. }
  242. if (flush)
  243. trusted_dirs_flush_certs_to_disk();
  244. /* call this even if failure_code is <0, since some certs might have
  245. * succeeded. */
  246. networkstatus_note_certs_arrived();
  247. return failure_code;
  248. }
  249. /** Save all v3 key certificates to the cached-certs file. */
  250. void
  251. trusted_dirs_flush_certs_to_disk(void)
  252. {
  253. char *filename;
  254. smartlist_t *chunks;
  255. if (!trusted_dir_servers_certs_changed || !trusted_dir_certs)
  256. return;
  257. chunks = smartlist_new();
  258. DIGESTMAP_FOREACH(trusted_dir_certs, key, cert_list_t *, cl) {
  259. SMARTLIST_FOREACH(cl->certs, authority_cert_t *, cert,
  260. {
  261. sized_chunk_t *c = tor_malloc(sizeof(sized_chunk_t));
  262. c->bytes = cert->cache_info.signed_descriptor_body;
  263. c->len = cert->cache_info.signed_descriptor_len;
  264. smartlist_add(chunks, c);
  265. });
  266. } DIGESTMAP_FOREACH_END;
  267. filename = get_datadir_fname("cached-certs");
  268. if (write_chunks_to_file(filename, chunks, 0)) {
  269. log_warn(LD_FS, "Error writing certificates to disk.");
  270. }
  271. tor_free(filename);
  272. SMARTLIST_FOREACH(chunks, sized_chunk_t *, c, tor_free(c));
  273. smartlist_free(chunks);
  274. trusted_dir_servers_certs_changed = 0;
  275. }
  276. /** Remove all v3 authority certificates that have been superseded for more
  277. * than 48 hours. (If the most recent cert was published more than 48 hours
  278. * ago, then we aren't going to get any consensuses signed with older
  279. * keys.) */
  280. static void
  281. trusted_dirs_remove_old_certs(void)
  282. {
  283. time_t now = time(NULL);
  284. #define DEAD_CERT_LIFETIME (2*24*60*60)
  285. #define OLD_CERT_LIFETIME (7*24*60*60)
  286. #define CERT_EXPIRY_SKEW (60*60)
  287. if (!trusted_dir_certs)
  288. return;
  289. DIGESTMAP_FOREACH(trusted_dir_certs, key, cert_list_t *, cl) {
  290. authority_cert_t *newest = NULL;
  291. SMARTLIST_FOREACH(cl->certs, authority_cert_t *, cert,
  292. if (!newest || (cert->cache_info.published_on >
  293. newest->cache_info.published_on))
  294. newest = cert);
  295. if (newest) {
  296. const time_t newest_published = newest->cache_info.published_on;
  297. SMARTLIST_FOREACH_BEGIN(cl->certs, authority_cert_t *, cert) {
  298. int expired;
  299. time_t cert_published;
  300. if (newest == cert)
  301. continue;
  302. expired = now > cert->expires;
  303. cert_published = cert->cache_info.published_on;
  304. /* Store expired certs for 48 hours after a newer arrives;
  305. */
  306. if (expired ?
  307. (newest_published + DEAD_CERT_LIFETIME < now) :
  308. (cert_published + OLD_CERT_LIFETIME < newest_published)) {
  309. SMARTLIST_DEL_CURRENT(cl->certs, cert);
  310. authority_cert_free(cert);
  311. trusted_dir_servers_certs_changed = 1;
  312. }
  313. } SMARTLIST_FOREACH_END(cert);
  314. }
  315. } DIGESTMAP_FOREACH_END;
  316. #undef OLD_CERT_LIFETIME
  317. trusted_dirs_flush_certs_to_disk();
  318. }
  319. /** Return the newest v3 authority certificate whose v3 authority identity key
  320. * has digest <b>id_digest</b>. Return NULL if no such authority is known,
  321. * or it has no certificate. */
  322. authority_cert_t *
  323. authority_cert_get_newest_by_id(const char *id_digest)
  324. {
  325. cert_list_t *cl;
  326. authority_cert_t *best = NULL;
  327. if (!trusted_dir_certs ||
  328. !(cl = digestmap_get(trusted_dir_certs, id_digest)))
  329. return NULL;
  330. SMARTLIST_FOREACH(cl->certs, authority_cert_t *, cert,
  331. {
  332. if (!best || cert->cache_info.published_on > best->cache_info.published_on)
  333. best = cert;
  334. });
  335. return best;
  336. }
  337. /** Return the newest v3 authority certificate whose directory signing key has
  338. * digest <b>sk_digest</b>. Return NULL if no such certificate is known.
  339. */
  340. authority_cert_t *
  341. authority_cert_get_by_sk_digest(const char *sk_digest)
  342. {
  343. authority_cert_t *c;
  344. if (!trusted_dir_certs)
  345. return NULL;
  346. if ((c = get_my_v3_authority_cert()) &&
  347. tor_memeq(c->signing_key_digest, sk_digest, DIGEST_LEN))
  348. return c;
  349. if ((c = get_my_v3_legacy_cert()) &&
  350. tor_memeq(c->signing_key_digest, sk_digest, DIGEST_LEN))
  351. return c;
  352. DIGESTMAP_FOREACH(trusted_dir_certs, key, cert_list_t *, cl) {
  353. SMARTLIST_FOREACH(cl->certs, authority_cert_t *, cert,
  354. {
  355. if (tor_memeq(cert->signing_key_digest, sk_digest, DIGEST_LEN))
  356. return cert;
  357. });
  358. } DIGESTMAP_FOREACH_END;
  359. return NULL;
  360. }
  361. /** Return the v3 authority certificate with signing key matching
  362. * <b>sk_digest</b>, for the authority with identity digest <b>id_digest</b>.
  363. * Return NULL if no such authority is known. */
  364. authority_cert_t *
  365. authority_cert_get_by_digests(const char *id_digest,
  366. const char *sk_digest)
  367. {
  368. cert_list_t *cl;
  369. if (!trusted_dir_certs ||
  370. !(cl = digestmap_get(trusted_dir_certs, id_digest)))
  371. return NULL;
  372. SMARTLIST_FOREACH(cl->certs, authority_cert_t *, cert,
  373. if (tor_memeq(cert->signing_key_digest, sk_digest, DIGEST_LEN))
  374. return cert; );
  375. return NULL;
  376. }
  377. /** Add every known authority_cert_t to <b>certs_out</b>. */
  378. void
  379. authority_cert_get_all(smartlist_t *certs_out)
  380. {
  381. tor_assert(certs_out);
  382. if (!trusted_dir_certs)
  383. return;
  384. DIGESTMAP_FOREACH(trusted_dir_certs, key, cert_list_t *, cl) {
  385. SMARTLIST_FOREACH(cl->certs, authority_cert_t *, c,
  386. smartlist_add(certs_out, c));
  387. } DIGESTMAP_FOREACH_END;
  388. }
  389. /** Called when an attempt to download a certificate with the authority with
  390. * ID <b>id_digest</b> fails with HTTP response code <b>status</b>: remember
  391. * the failure, so we don't try again immediately. */
  392. void
  393. authority_cert_dl_failed(const char *id_digest, int status)
  394. {
  395. cert_list_t *cl;
  396. if (!trusted_dir_certs ||
  397. !(cl = digestmap_get(trusted_dir_certs, id_digest)))
  398. return;
  399. download_status_failed(&cl->dl_status, status);
  400. }
  401. /** Return true iff when we've been getting enough failures when trying to
  402. * download the certificate with ID digest <b>id_digest</b> that we're willing
  403. * to start bugging the user about it. */
  404. int
  405. authority_cert_dl_looks_uncertain(const char *id_digest)
  406. {
  407. #define N_AUTH_CERT_DL_FAILURES_TO_BUG_USER 2
  408. cert_list_t *cl;
  409. int n_failures;
  410. if (!trusted_dir_certs ||
  411. !(cl = digestmap_get(trusted_dir_certs, id_digest)))
  412. return 0;
  413. n_failures = download_status_get_n_failures(&cl->dl_status);
  414. return n_failures >= N_AUTH_CERT_DL_FAILURES_TO_BUG_USER;
  415. }
  416. /** How many times will we try to fetch a certificate before giving up? */
  417. #define MAX_CERT_DL_FAILURES 8
  418. /** Try to download any v3 authority certificates that we may be missing. If
  419. * <b>status</b> is provided, try to get all the ones that were used to sign
  420. * <b>status</b>. Additionally, try to have a non-expired certificate for
  421. * every V3 authority in trusted_dir_servers. Don't fetch certificates we
  422. * already have.
  423. **/
  424. void
  425. authority_certs_fetch_missing(networkstatus_t *status, time_t now)
  426. {
  427. digestmap_t *pending;
  428. authority_cert_t *cert;
  429. smartlist_t *missing_digests;
  430. char *resource = NULL;
  431. cert_list_t *cl;
  432. const int cache = directory_caches_unknown_auth_certs(get_options());
  433. if (should_delay_dir_fetches(get_options()))
  434. return;
  435. pending = digestmap_new();
  436. missing_digests = smartlist_new();
  437. list_pending_downloads(pending, DIR_PURPOSE_FETCH_CERTIFICATE, "fp/");
  438. if (status) {
  439. SMARTLIST_FOREACH_BEGIN(status->voters, networkstatus_voter_info_t *,
  440. voter) {
  441. if (!smartlist_len(voter->sigs))
  442. continue; /* This authority never signed this consensus, so don't
  443. * go looking for a cert with key digest 0000000000. */
  444. if (!cache &&
  445. !trusteddirserver_get_by_v3_auth_digest(voter->identity_digest))
  446. continue; /* We are not a cache, and we don't know this authority.*/
  447. cl = get_cert_list(voter->identity_digest);
  448. SMARTLIST_FOREACH_BEGIN(voter->sigs, document_signature_t *, sig) {
  449. cert = authority_cert_get_by_digests(voter->identity_digest,
  450. sig->signing_key_digest);
  451. if (cert) {
  452. if (now < cert->expires)
  453. download_status_reset(&cl->dl_status);
  454. continue;
  455. }
  456. if (download_status_is_ready(&cl->dl_status, now,
  457. MAX_CERT_DL_FAILURES) &&
  458. !digestmap_get(pending, voter->identity_digest)) {
  459. log_info(LD_DIR, "We're missing a certificate from authority "
  460. "with signing key %s: launching request.",
  461. hex_str(sig->signing_key_digest, DIGEST_LEN));
  462. smartlist_add(missing_digests, sig->identity_digest);
  463. }
  464. } SMARTLIST_FOREACH_END(sig);
  465. } SMARTLIST_FOREACH_END(voter);
  466. }
  467. SMARTLIST_FOREACH_BEGIN(trusted_dir_servers, trusted_dir_server_t *, ds) {
  468. int found = 0;
  469. if (!(ds->type & V3_DIRINFO))
  470. continue;
  471. if (smartlist_digest_isin(missing_digests, ds->v3_identity_digest))
  472. continue;
  473. cl = get_cert_list(ds->v3_identity_digest);
  474. SMARTLIST_FOREACH(cl->certs, authority_cert_t *, cert, {
  475. if (now < cert->expires) {
  476. /* It's not expired, and we weren't looking for something to
  477. * verify a consensus with. Call it done. */
  478. download_status_reset(&cl->dl_status);
  479. found = 1;
  480. break;
  481. }
  482. });
  483. if (!found &&
  484. download_status_is_ready(&cl->dl_status, now,MAX_CERT_DL_FAILURES) &&
  485. !digestmap_get(pending, ds->v3_identity_digest)) {
  486. log_info(LD_DIR, "No current certificate known for authority %s; "
  487. "launching request.", ds->nickname);
  488. smartlist_add(missing_digests, ds->v3_identity_digest);
  489. }
  490. } SMARTLIST_FOREACH_END(ds);
  491. if (!smartlist_len(missing_digests)) {
  492. goto done;
  493. } else {
  494. smartlist_t *fps = smartlist_new();
  495. smartlist_add(fps, tor_strdup("fp/"));
  496. SMARTLIST_FOREACH(missing_digests, const char *, d, {
  497. char *fp;
  498. if (digestmap_get(pending, d))
  499. continue;
  500. fp = tor_malloc(HEX_DIGEST_LEN+2);
  501. base16_encode(fp, HEX_DIGEST_LEN+1, d, DIGEST_LEN);
  502. fp[HEX_DIGEST_LEN] = '+';
  503. fp[HEX_DIGEST_LEN+1] = '\0';
  504. smartlist_add(fps, fp);
  505. });
  506. if (smartlist_len(fps) == 1) {
  507. /* we didn't add any: they were all pending */
  508. SMARTLIST_FOREACH(fps, char *, cp, tor_free(cp));
  509. smartlist_free(fps);
  510. goto done;
  511. }
  512. resource = smartlist_join_strings(fps, "", 0, NULL);
  513. resource[strlen(resource)-1] = '\0';
  514. SMARTLIST_FOREACH(fps, char *, cp, tor_free(cp));
  515. smartlist_free(fps);
  516. }
  517. directory_get_from_dirserver(DIR_PURPOSE_FETCH_CERTIFICATE, 0,
  518. resource, PDS_RETRY_IF_NO_SERVERS);
  519. done:
  520. tor_free(resource);
  521. smartlist_free(missing_digests);
  522. digestmap_free(pending, NULL);
  523. }
  524. /* Router descriptor storage.
  525. *
  526. * Routerdescs are stored in a big file, named "cached-descriptors". As new
  527. * routerdescs arrive, we append them to a journal file named
  528. * "cached-descriptors.new".
  529. *
  530. * From time to time, we replace "cached-descriptors" with a new file
  531. * containing only the live, non-superseded descriptors, and clear
  532. * cached-routers.new.
  533. *
  534. * On startup, we read both files.
  535. */
  536. /** Helper: return 1 iff the router log is so big we want to rebuild the
  537. * store. */
  538. static int
  539. router_should_rebuild_store(desc_store_t *store)
  540. {
  541. if (store->store_len > (1<<16))
  542. return (store->journal_len > store->store_len / 2 ||
  543. store->bytes_dropped > store->store_len / 2);
  544. else
  545. return store->journal_len > (1<<15);
  546. }
  547. /** Return the desc_store_t in <b>rl</b> that should be used to store
  548. * <b>sd</b>. */
  549. static INLINE desc_store_t *
  550. desc_get_store(routerlist_t *rl, const signed_descriptor_t *sd)
  551. {
  552. if (sd->is_extrainfo)
  553. return &rl->extrainfo_store;
  554. else
  555. return &rl->desc_store;
  556. }
  557. /** Add the signed_descriptor_t in <b>desc</b> to the router
  558. * journal; change its saved_location to SAVED_IN_JOURNAL and set its
  559. * offset appropriately. */
  560. static int
  561. signed_desc_append_to_journal(signed_descriptor_t *desc,
  562. desc_store_t *store)
  563. {
  564. char *fname = get_datadir_fname_suffix(store->fname_base, ".new");
  565. const char *body = signed_descriptor_get_body_impl(desc,1);
  566. size_t len = desc->signed_descriptor_len + desc->annotations_len;
  567. if (append_bytes_to_file(fname, body, len, 1)) {
  568. log_warn(LD_FS, "Unable to store router descriptor");
  569. tor_free(fname);
  570. return -1;
  571. }
  572. desc->saved_location = SAVED_IN_JOURNAL;
  573. tor_free(fname);
  574. desc->saved_offset = store->journal_len;
  575. store->journal_len += len;
  576. return 0;
  577. }
  578. /** Sorting helper: return &lt;0, 0, or &gt;0 depending on whether the
  579. * signed_descriptor_t* in *<b>a</b> is older, the same age as, or newer than
  580. * the signed_descriptor_t* in *<b>b</b>. */
  581. static int
  582. _compare_signed_descriptors_by_age(const void **_a, const void **_b)
  583. {
  584. const signed_descriptor_t *r1 = *_a, *r2 = *_b;
  585. return (int)(r1->published_on - r2->published_on);
  586. }
  587. #define RRS_FORCE 1
  588. #define RRS_DONT_REMOVE_OLD 2
  589. /** If the journal of <b>store</b> is too long, or if RRS_FORCE is set in
  590. * <b>flags</b>, then atomically replace the saved router store with the
  591. * routers currently in our routerlist, and clear the journal. Unless
  592. * RRS_DONT_REMOVE_OLD is set in <b>flags</b>, delete expired routers before
  593. * rebuilding the store. Return 0 on success, -1 on failure.
  594. */
  595. static int
  596. router_rebuild_store(int flags, desc_store_t *store)
  597. {
  598. smartlist_t *chunk_list = NULL;
  599. char *fname = NULL, *fname_tmp = NULL;
  600. int r = -1;
  601. off_t offset = 0;
  602. smartlist_t *signed_descriptors = NULL;
  603. int nocache=0;
  604. size_t total_expected_len = 0;
  605. int had_any;
  606. int force = flags & RRS_FORCE;
  607. if (!force && !router_should_rebuild_store(store)) {
  608. r = 0;
  609. goto done;
  610. }
  611. if (!routerlist) {
  612. r = 0;
  613. goto done;
  614. }
  615. if (store->type == EXTRAINFO_STORE)
  616. had_any = !eimap_isempty(routerlist->extra_info_map);
  617. else
  618. had_any = (smartlist_len(routerlist->routers)+
  619. smartlist_len(routerlist->old_routers))>0;
  620. /* Don't save deadweight. */
  621. if (!(flags & RRS_DONT_REMOVE_OLD))
  622. routerlist_remove_old_routers();
  623. log_info(LD_DIR, "Rebuilding %s cache", store->description);
  624. fname = get_datadir_fname(store->fname_base);
  625. fname_tmp = get_datadir_fname_suffix(store->fname_base, ".tmp");
  626. chunk_list = smartlist_new();
  627. /* We sort the routers by age to enhance locality on disk. */
  628. signed_descriptors = smartlist_new();
  629. if (store->type == EXTRAINFO_STORE) {
  630. eimap_iter_t *iter;
  631. for (iter = eimap_iter_init(routerlist->extra_info_map);
  632. !eimap_iter_done(iter);
  633. iter = eimap_iter_next(routerlist->extra_info_map, iter)) {
  634. const char *key;
  635. extrainfo_t *ei;
  636. eimap_iter_get(iter, &key, &ei);
  637. smartlist_add(signed_descriptors, &ei->cache_info);
  638. }
  639. } else {
  640. SMARTLIST_FOREACH(routerlist->old_routers, signed_descriptor_t *, sd,
  641. smartlist_add(signed_descriptors, sd));
  642. SMARTLIST_FOREACH(routerlist->routers, routerinfo_t *, ri,
  643. smartlist_add(signed_descriptors, &ri->cache_info));
  644. }
  645. smartlist_sort(signed_descriptors, _compare_signed_descriptors_by_age);
  646. /* Now, add the appropriate members to chunk_list */
  647. SMARTLIST_FOREACH(signed_descriptors, signed_descriptor_t *, sd,
  648. {
  649. sized_chunk_t *c;
  650. const char *body = signed_descriptor_get_body_impl(sd, 1);
  651. if (!body) {
  652. log_warn(LD_BUG, "No descriptor available for router.");
  653. goto done;
  654. }
  655. if (sd->do_not_cache) {
  656. ++nocache;
  657. continue;
  658. }
  659. c = tor_malloc(sizeof(sized_chunk_t));
  660. c->bytes = body;
  661. c->len = sd->signed_descriptor_len + sd->annotations_len;
  662. total_expected_len += c->len;
  663. smartlist_add(chunk_list, c);
  664. });
  665. if (write_chunks_to_file(fname_tmp, chunk_list, 1)<0) {
  666. log_warn(LD_FS, "Error writing router store to disk.");
  667. goto done;
  668. }
  669. /* Our mmap is now invalid. */
  670. if (store->mmap) {
  671. tor_munmap_file(store->mmap);
  672. store->mmap = NULL;
  673. }
  674. if (replace_file(fname_tmp, fname)<0) {
  675. log_warn(LD_FS, "Error replacing old router store: %s", strerror(errno));
  676. goto done;
  677. }
  678. errno = 0;
  679. store->mmap = tor_mmap_file(fname);
  680. if (! store->mmap) {
  681. if (errno == ERANGE) {
  682. /* empty store.*/
  683. if (total_expected_len) {
  684. log_warn(LD_FS, "We wrote some bytes to a new descriptor file at '%s',"
  685. " but when we went to mmap it, it was empty!", fname);
  686. } else if (had_any) {
  687. log_info(LD_FS, "We just removed every descriptor in '%s'. This is "
  688. "okay if we're just starting up after a long time. "
  689. "Otherwise, it's a bug.", fname);
  690. }
  691. } else {
  692. log_warn(LD_FS, "Unable to mmap new descriptor file at '%s'.",fname);
  693. }
  694. }
  695. log_info(LD_DIR, "Reconstructing pointers into cache");
  696. offset = 0;
  697. SMARTLIST_FOREACH(signed_descriptors, signed_descriptor_t *, sd,
  698. {
  699. if (sd->do_not_cache)
  700. continue;
  701. sd->saved_location = SAVED_IN_CACHE;
  702. if (store->mmap) {
  703. tor_free(sd->signed_descriptor_body); // sets it to null
  704. sd->saved_offset = offset;
  705. }
  706. offset += sd->signed_descriptor_len + sd->annotations_len;
  707. signed_descriptor_get_body(sd); /* reconstruct and assert */
  708. });
  709. tor_free(fname);
  710. fname = get_datadir_fname_suffix(store->fname_base, ".new");
  711. write_str_to_file(fname, "", 1);
  712. r = 0;
  713. store->store_len = (size_t) offset;
  714. store->journal_len = 0;
  715. store->bytes_dropped = 0;
  716. done:
  717. smartlist_free(signed_descriptors);
  718. tor_free(fname);
  719. tor_free(fname_tmp);
  720. if (chunk_list) {
  721. SMARTLIST_FOREACH(chunk_list, sized_chunk_t *, c, tor_free(c));
  722. smartlist_free(chunk_list);
  723. }
  724. return r;
  725. }
  726. /** Helper: Reload a cache file and its associated journal, setting metadata
  727. * appropriately. If <b>extrainfo</b> is true, reload the extrainfo store;
  728. * else reload the router descriptor store. */
  729. static int
  730. router_reload_router_list_impl(desc_store_t *store)
  731. {
  732. char *fname = NULL, *altname = NULL, *contents = NULL;
  733. struct stat st;
  734. int read_from_old_location = 0;
  735. int extrainfo = (store->type == EXTRAINFO_STORE);
  736. time_t now = time(NULL);
  737. store->journal_len = store->store_len = 0;
  738. fname = get_datadir_fname(store->fname_base);
  739. if (store->fname_alt_base)
  740. altname = get_datadir_fname(store->fname_alt_base);
  741. if (store->mmap) /* get rid of it first */
  742. tor_munmap_file(store->mmap);
  743. store->mmap = NULL;
  744. store->mmap = tor_mmap_file(fname);
  745. if (!store->mmap && altname && file_status(altname) == FN_FILE) {
  746. read_from_old_location = 1;
  747. log_notice(LD_DIR, "Couldn't read %s; trying to load routers from old "
  748. "location %s.", fname, altname);
  749. if ((store->mmap = tor_mmap_file(altname)))
  750. read_from_old_location = 1;
  751. }
  752. if (altname && !read_from_old_location) {
  753. remove_file_if_very_old(altname, now);
  754. }
  755. if (store->mmap) {
  756. store->store_len = store->mmap->size;
  757. if (extrainfo)
  758. router_load_extrainfo_from_string(store->mmap->data,
  759. store->mmap->data+store->mmap->size,
  760. SAVED_IN_CACHE, NULL, 0);
  761. else
  762. router_load_routers_from_string(store->mmap->data,
  763. store->mmap->data+store->mmap->size,
  764. SAVED_IN_CACHE, NULL, 0, NULL);
  765. }
  766. tor_free(fname);
  767. fname = get_datadir_fname_suffix(store->fname_base, ".new");
  768. if (file_status(fname) == FN_FILE)
  769. contents = read_file_to_str(fname, RFTS_BIN|RFTS_IGNORE_MISSING, &st);
  770. if (read_from_old_location) {
  771. tor_free(altname);
  772. altname = get_datadir_fname_suffix(store->fname_alt_base, ".new");
  773. if (!contents)
  774. contents = read_file_to_str(altname, RFTS_BIN|RFTS_IGNORE_MISSING, &st);
  775. else
  776. remove_file_if_very_old(altname, now);
  777. }
  778. if (contents) {
  779. if (extrainfo)
  780. router_load_extrainfo_from_string(contents, NULL,SAVED_IN_JOURNAL,
  781. NULL, 0);
  782. else
  783. router_load_routers_from_string(contents, NULL, SAVED_IN_JOURNAL,
  784. NULL, 0, NULL);
  785. store->journal_len = (size_t) st.st_size;
  786. tor_free(contents);
  787. }
  788. tor_free(fname);
  789. tor_free(altname);
  790. if (store->journal_len || read_from_old_location) {
  791. /* Always clear the journal on startup.*/
  792. router_rebuild_store(RRS_FORCE, store);
  793. } else if (!extrainfo) {
  794. /* Don't cache expired routers. (This is in an else because
  795. * router_rebuild_store() also calls remove_old_routers().) */
  796. routerlist_remove_old_routers();
  797. }
  798. return 0;
  799. }
  800. /** Load all cached router descriptors and extra-info documents from the
  801. * store. Return 0 on success and -1 on failure.
  802. */
  803. int
  804. router_reload_router_list(void)
  805. {
  806. routerlist_t *rl = router_get_routerlist();
  807. if (router_reload_router_list_impl(&rl->desc_store))
  808. return -1;
  809. if (router_reload_router_list_impl(&rl->extrainfo_store))
  810. return -1;
  811. return 0;
  812. }
  813. /** Return a smartlist containing a list of trusted_dir_server_t * for all
  814. * known trusted dirservers. Callers must not modify the list or its
  815. * contents.
  816. */
  817. smartlist_t *
  818. router_get_trusted_dir_servers(void)
  819. {
  820. if (!trusted_dir_servers)
  821. trusted_dir_servers = smartlist_new();
  822. return trusted_dir_servers;
  823. }
  824. /** Try to find a running dirserver that supports operations of <b>type</b>.
  825. *
  826. * If there are no running dirservers in our routerlist and the
  827. * <b>PDS_RETRY_IF_NO_SERVERS</b> flag is set, set all the authoritative ones
  828. * as running again, and pick one.
  829. *
  830. * If the <b>PDS_IGNORE_FASCISTFIREWALL</b> flag is set, then include
  831. * dirservers that we can't reach.
  832. *
  833. * If the <b>PDS_ALLOW_SELF</b> flag is not set, then don't include ourself
  834. * (if we're a dirserver).
  835. *
  836. * Don't pick an authority if any non-authority is viable; try to avoid using
  837. * servers that have returned 503 recently.
  838. */
  839. const routerstatus_t *
  840. router_pick_directory_server(dirinfo_type_t type, int flags)
  841. {
  842. const routerstatus_t *choice;
  843. if (get_options()->PreferTunneledDirConns)
  844. flags |= _PDS_PREFER_TUNNELED_DIR_CONNS;
  845. if (!routerlist)
  846. return NULL;
  847. choice = router_pick_directory_server_impl(type, flags);
  848. if (choice || !(flags & PDS_RETRY_IF_NO_SERVERS))
  849. return choice;
  850. log_info(LD_DIR,
  851. "No reachable router entries for dirservers. "
  852. "Trying them all again.");
  853. /* mark all authdirservers as up again */
  854. mark_all_trusteddirservers_up();
  855. /* try again */
  856. choice = router_pick_directory_server_impl(type, flags);
  857. return choice;
  858. }
  859. /** Try to determine which fraction of v2 and v3 directory requests aimed at
  860. * caches will be sent to us. Set *<b>v2_share_out</b> and
  861. * *<b>v3_share_out</b> to the fractions of v2 and v3 protocol shares we
  862. * expect to see, respectively. Return 0 on success, negative on failure. */
  863. int
  864. router_get_my_share_of_directory_requests(double *v2_share_out,
  865. double *v3_share_out)
  866. {
  867. const routerinfo_t *me = router_get_my_routerinfo();
  868. const routerstatus_t *rs;
  869. const int pds_flags = PDS_ALLOW_SELF|PDS_IGNORE_FASCISTFIREWALL;
  870. *v2_share_out = *v3_share_out = 0.0;
  871. if (!me)
  872. return -1;
  873. rs = router_get_consensus_status_by_id(me->cache_info.identity_digest);
  874. if (!rs)
  875. return -1;
  876. /* Calling for side effect */
  877. /* XXXX This is a bit of a kludge */
  878. if (rs->is_v2_dir) {
  879. sl_last_total_weighted_bw = 0;
  880. router_pick_directory_server(V2_DIRINFO, pds_flags);
  881. if (sl_last_total_weighted_bw != 0) {
  882. *v2_share_out = U64_TO_DBL(sl_last_weighted_bw_of_me) /
  883. U64_TO_DBL(sl_last_total_weighted_bw);
  884. }
  885. }
  886. if (rs->version_supports_v3_dir) {
  887. sl_last_total_weighted_bw = 0;
  888. router_pick_directory_server(V3_DIRINFO, pds_flags);
  889. if (sl_last_total_weighted_bw != 0) {
  890. *v3_share_out = U64_TO_DBL(sl_last_weighted_bw_of_me) /
  891. U64_TO_DBL(sl_last_total_weighted_bw);
  892. }
  893. }
  894. return 0;
  895. }
  896. /** Return the trusted_dir_server_t for the directory authority whose identity
  897. * key hashes to <b>digest</b>, or NULL if no such authority is known.
  898. */
  899. trusted_dir_server_t *
  900. router_get_trusteddirserver_by_digest(const char *digest)
  901. {
  902. if (!trusted_dir_servers)
  903. return NULL;
  904. SMARTLIST_FOREACH(trusted_dir_servers, trusted_dir_server_t *, ds,
  905. {
  906. if (tor_memeq(ds->digest, digest, DIGEST_LEN))
  907. return ds;
  908. });
  909. return NULL;
  910. }
  911. /** Return the trusted_dir_server_t for the directory authority whose
  912. * v3 identity key hashes to <b>digest</b>, or NULL if no such authority
  913. * is known.
  914. */
  915. trusted_dir_server_t *
  916. trusteddirserver_get_by_v3_auth_digest(const char *digest)
  917. {
  918. if (!trusted_dir_servers)
  919. return NULL;
  920. SMARTLIST_FOREACH(trusted_dir_servers, trusted_dir_server_t *, ds,
  921. {
  922. if (tor_memeq(ds->v3_identity_digest, digest, DIGEST_LEN) &&
  923. (ds->type & V3_DIRINFO))
  924. return ds;
  925. });
  926. return NULL;
  927. }
  928. /** Try to find a running trusted dirserver. Flags are as for
  929. * router_pick_directory_server.
  930. */
  931. const routerstatus_t *
  932. router_pick_trusteddirserver(dirinfo_type_t type, int flags)
  933. {
  934. const routerstatus_t *choice;
  935. int busy = 0;
  936. if (get_options()->PreferTunneledDirConns)
  937. flags |= _PDS_PREFER_TUNNELED_DIR_CONNS;
  938. choice = router_pick_trusteddirserver_impl(type, flags, &busy);
  939. if (choice || !(flags & PDS_RETRY_IF_NO_SERVERS))
  940. return choice;
  941. if (busy) {
  942. /* If the reason that we got no server is that servers are "busy",
  943. * we must be excluding good servers because we already have serverdesc
  944. * fetches with them. Do not mark down servers up because of this. */
  945. tor_assert((flags & (PDS_NO_EXISTING_SERVERDESC_FETCH|
  946. PDS_NO_EXISTING_MICRODESC_FETCH)));
  947. return NULL;
  948. }
  949. log_info(LD_DIR,
  950. "No trusted dirservers are reachable. Trying them all again.");
  951. mark_all_trusteddirservers_up();
  952. return router_pick_trusteddirserver_impl(type, flags, NULL);
  953. }
  954. /** How long do we avoid using a directory server after it's given us a 503? */
  955. #define DIR_503_TIMEOUT (60*60)
  956. /** Pick a random running valid directory server/mirror from our
  957. * routerlist. Arguments are as for router_pick_directory_server(), except
  958. * that RETRY_IF_NO_SERVERS is ignored, and:
  959. *
  960. * If the _PDS_PREFER_TUNNELED_DIR_CONNS flag is set, prefer directory servers
  961. * that we can use with BEGINDIR.
  962. */
  963. static const routerstatus_t *
  964. router_pick_directory_server_impl(dirinfo_type_t type, int flags)
  965. {
  966. const or_options_t *options = get_options();
  967. const node_t *result;
  968. smartlist_t *direct, *tunnel;
  969. smartlist_t *trusted_direct, *trusted_tunnel;
  970. smartlist_t *overloaded_direct, *overloaded_tunnel;
  971. time_t now = time(NULL);
  972. const networkstatus_t *consensus = networkstatus_get_latest_consensus();
  973. int requireother = ! (flags & PDS_ALLOW_SELF);
  974. int fascistfirewall = ! (flags & PDS_IGNORE_FASCISTFIREWALL);
  975. int prefer_tunnel = (flags & _PDS_PREFER_TUNNELED_DIR_CONNS);
  976. int try_excluding = 1, n_excluded = 0;
  977. if (!consensus)
  978. return NULL;
  979. retry_without_exclude:
  980. direct = smartlist_new();
  981. tunnel = smartlist_new();
  982. trusted_direct = smartlist_new();
  983. trusted_tunnel = smartlist_new();
  984. overloaded_direct = smartlist_new();
  985. overloaded_tunnel = smartlist_new();
  986. /* Find all the running dirservers we know about. */
  987. SMARTLIST_FOREACH_BEGIN(nodelist_get_list(), const node_t *, node) {
  988. int is_trusted;
  989. int is_overloaded;
  990. tor_addr_t addr;
  991. const routerstatus_t *status = node->rs;
  992. const country_t country = node->country;
  993. if (!status)
  994. continue;
  995. if (!node->is_running || !status->dir_port || !node->is_valid)
  996. continue;
  997. if (node->is_bad_directory)
  998. continue;
  999. if (requireother && router_digest_is_me(node->identity))
  1000. continue;
  1001. if (type & V3_DIRINFO) {
  1002. if (!(status->version_supports_v3_dir ||
  1003. router_digest_is_trusted_dir_type(node->identity,
  1004. V3_DIRINFO)))
  1005. continue;
  1006. }
  1007. is_trusted = router_digest_is_trusted_dir(node->identity);
  1008. if ((type & V2_DIRINFO) && !(node->rs->is_v2_dir || is_trusted))
  1009. continue;
  1010. if ((type & EXTRAINFO_DIRINFO) &&
  1011. !router_supports_extrainfo(node->identity, 0))
  1012. continue;
  1013. if ((type & MICRODESC_DIRINFO) && !is_trusted &&
  1014. !node->rs->version_supports_microdesc_cache)
  1015. continue;
  1016. if (try_excluding &&
  1017. routerset_contains_routerstatus(options->ExcludeNodes, status,
  1018. country)) {
  1019. ++n_excluded;
  1020. continue;
  1021. }
  1022. /* XXXX IP6 proposal 118 */
  1023. tor_addr_from_ipv4h(&addr, node->rs->addr);
  1024. is_overloaded = status->last_dir_503_at + DIR_503_TIMEOUT > now;
  1025. if (prefer_tunnel &&
  1026. status->version_supports_begindir &&
  1027. (!fascistfirewall ||
  1028. fascist_firewall_allows_address_or(&addr, status->or_port)))
  1029. smartlist_add(is_trusted ? trusted_tunnel :
  1030. is_overloaded ? overloaded_tunnel : tunnel, (void*)node);
  1031. else if (!fascistfirewall ||
  1032. fascist_firewall_allows_address_dir(&addr, status->dir_port))
  1033. smartlist_add(is_trusted ? trusted_direct :
  1034. is_overloaded ? overloaded_direct : direct, (void*)node);
  1035. } SMARTLIST_FOREACH_END(node);
  1036. if (smartlist_len(tunnel)) {
  1037. result = node_sl_choose_by_bandwidth(tunnel, WEIGHT_FOR_DIR);
  1038. } else if (smartlist_len(overloaded_tunnel)) {
  1039. result = node_sl_choose_by_bandwidth(overloaded_tunnel,
  1040. WEIGHT_FOR_DIR);
  1041. } else if (smartlist_len(trusted_tunnel)) {
  1042. /* FFFF We don't distinguish between trusteds and overloaded trusteds
  1043. * yet. Maybe one day we should. */
  1044. /* FFFF We also don't load balance over authorities yet. I think this
  1045. * is a feature, but it could easily be a bug. -RD */
  1046. result = smartlist_choose(trusted_tunnel);
  1047. } else if (smartlist_len(direct)) {
  1048. result = node_sl_choose_by_bandwidth(direct, WEIGHT_FOR_DIR);
  1049. } else if (smartlist_len(overloaded_direct)) {
  1050. result = node_sl_choose_by_bandwidth(overloaded_direct,
  1051. WEIGHT_FOR_DIR);
  1052. } else {
  1053. result = smartlist_choose(trusted_direct);
  1054. }
  1055. smartlist_free(direct);
  1056. smartlist_free(tunnel);
  1057. smartlist_free(trusted_direct);
  1058. smartlist_free(trusted_tunnel);
  1059. smartlist_free(overloaded_direct);
  1060. smartlist_free(overloaded_tunnel);
  1061. if (result == NULL && try_excluding && !options->StrictNodes && n_excluded) {
  1062. /* If we got no result, and we are excluding nodes, and StrictNodes is
  1063. * not set, try again without excluding nodes. */
  1064. try_excluding = 0;
  1065. n_excluded = 0;
  1066. goto retry_without_exclude;
  1067. }
  1068. return result ? result->rs : NULL;
  1069. }
  1070. /** Choose randomly from among the trusted dirservers that are up. Flags
  1071. * are as for router_pick_directory_server_impl().
  1072. */
  1073. static const routerstatus_t *
  1074. router_pick_trusteddirserver_impl(dirinfo_type_t type, int flags,
  1075. int *n_busy_out)
  1076. {
  1077. const or_options_t *options = get_options();
  1078. smartlist_t *direct, *tunnel;
  1079. smartlist_t *overloaded_direct, *overloaded_tunnel;
  1080. const routerinfo_t *me = router_get_my_routerinfo();
  1081. const routerstatus_t *result;
  1082. time_t now = time(NULL);
  1083. const int requireother = ! (flags & PDS_ALLOW_SELF);
  1084. const int fascistfirewall = ! (flags & PDS_IGNORE_FASCISTFIREWALL);
  1085. const int prefer_tunnel = (flags & _PDS_PREFER_TUNNELED_DIR_CONNS);
  1086. const int no_serverdesc_fetching =(flags & PDS_NO_EXISTING_SERVERDESC_FETCH);
  1087. const int no_microdesc_fetching =(flags & PDS_NO_EXISTING_MICRODESC_FETCH);
  1088. int n_busy = 0;
  1089. int try_excluding = 1, n_excluded = 0;
  1090. if (!trusted_dir_servers)
  1091. return NULL;
  1092. retry_without_exclude:
  1093. direct = smartlist_new();
  1094. tunnel = smartlist_new();
  1095. overloaded_direct = smartlist_new();
  1096. overloaded_tunnel = smartlist_new();
  1097. SMARTLIST_FOREACH_BEGIN(trusted_dir_servers, trusted_dir_server_t *, d)
  1098. {
  1099. int is_overloaded =
  1100. d->fake_status.last_dir_503_at + DIR_503_TIMEOUT > now;
  1101. tor_addr_t addr;
  1102. if (!d->is_running) continue;
  1103. if ((type & d->type) == 0)
  1104. continue;
  1105. if ((type & EXTRAINFO_DIRINFO) &&
  1106. !router_supports_extrainfo(d->digest, 1))
  1107. continue;
  1108. if (requireother && me && router_digest_is_me(d->digest))
  1109. continue;
  1110. if (try_excluding &&
  1111. routerset_contains_routerstatus(options->ExcludeNodes,
  1112. &d->fake_status, -1)) {
  1113. ++n_excluded;
  1114. continue;
  1115. }
  1116. /* XXXX IP6 proposal 118 */
  1117. tor_addr_from_ipv4h(&addr, d->addr);
  1118. if (no_serverdesc_fetching) {
  1119. if (connection_get_by_type_addr_port_purpose(
  1120. CONN_TYPE_DIR, &addr, d->dir_port, DIR_PURPOSE_FETCH_SERVERDESC)
  1121. || connection_get_by_type_addr_port_purpose(
  1122. CONN_TYPE_DIR, &addr, d->dir_port, DIR_PURPOSE_FETCH_EXTRAINFO)) {
  1123. //log_debug(LD_DIR, "We have an existing connection to fetch "
  1124. // "descriptor from %s; delaying",d->description);
  1125. ++n_busy;
  1126. continue;
  1127. }
  1128. }
  1129. if (no_microdesc_fetching) {
  1130. if (connection_get_by_type_addr_port_purpose(
  1131. CONN_TYPE_DIR, &addr, d->dir_port, DIR_PURPOSE_FETCH_MICRODESC)) {
  1132. ++n_busy;
  1133. continue;
  1134. }
  1135. }
  1136. if (prefer_tunnel &&
  1137. d->or_port &&
  1138. (!fascistfirewall ||
  1139. fascist_firewall_allows_address_or(&addr, d->or_port)))
  1140. smartlist_add(is_overloaded ? overloaded_tunnel : tunnel,
  1141. &d->fake_status);
  1142. else if (!fascistfirewall ||
  1143. fascist_firewall_allows_address_dir(&addr, d->dir_port))
  1144. smartlist_add(is_overloaded ? overloaded_direct : direct,
  1145. &d->fake_status);
  1146. }
  1147. SMARTLIST_FOREACH_END(d);
  1148. if (smartlist_len(tunnel)) {
  1149. result = smartlist_choose(tunnel);
  1150. } else if (smartlist_len(overloaded_tunnel)) {
  1151. result = smartlist_choose(overloaded_tunnel);
  1152. } else if (smartlist_len(direct)) {
  1153. result = smartlist_choose(direct);
  1154. } else {
  1155. result = smartlist_choose(overloaded_direct);
  1156. }
  1157. if (n_busy_out)
  1158. *n_busy_out = n_busy;
  1159. smartlist_free(direct);
  1160. smartlist_free(tunnel);
  1161. smartlist_free(overloaded_direct);
  1162. smartlist_free(overloaded_tunnel);
  1163. if (result == NULL && try_excluding && !options->StrictNodes && n_excluded) {
  1164. /* If we got no result, and we are excluding nodes, and StrictNodes is
  1165. * not set, try again without excluding nodes. */
  1166. try_excluding = 0;
  1167. n_excluded = 0;
  1168. goto retry_without_exclude;
  1169. }
  1170. return result;
  1171. }
  1172. /** Go through and mark the authoritative dirservers as up. */
  1173. static void
  1174. mark_all_trusteddirservers_up(void)
  1175. {
  1176. SMARTLIST_FOREACH(nodelist_get_list(), node_t *, node, {
  1177. if (router_digest_is_trusted_dir(node->identity))
  1178. node->is_running = 1;
  1179. });
  1180. if (trusted_dir_servers) {
  1181. SMARTLIST_FOREACH(trusted_dir_servers, trusted_dir_server_t *, dir,
  1182. {
  1183. routerstatus_t *rs;
  1184. dir->is_running = 1;
  1185. download_status_reset(&dir->v2_ns_dl_status);
  1186. rs = router_get_mutable_consensus_status_by_id(dir->digest);
  1187. if (rs) {
  1188. rs->last_dir_503_at = 0;
  1189. control_event_networkstatus_changed_single(rs);
  1190. }
  1191. });
  1192. }
  1193. router_dir_info_changed();
  1194. }
  1195. /** Return true iff r1 and r2 have the same address and OR port. */
  1196. int
  1197. routers_have_same_or_addr(const routerinfo_t *r1, const routerinfo_t *r2)
  1198. {
  1199. return r1->addr == r2->addr && r1->or_port == r2->or_port;
  1200. }
  1201. /** Reset all internal variables used to count failed downloads of network
  1202. * status objects. */
  1203. void
  1204. router_reset_status_download_failures(void)
  1205. {
  1206. mark_all_trusteddirservers_up();
  1207. }
  1208. /** Return true iff router1 and router2 have similar enough network addresses
  1209. * that we should treat them as being in the same family */
  1210. static INLINE int
  1211. addrs_in_same_network_family(const tor_addr_t *a1,
  1212. const tor_addr_t *a2)
  1213. {
  1214. /* XXXX MOVE ? */
  1215. return 0 == tor_addr_compare_masked(a1, a2, 16, CMP_SEMANTIC);
  1216. }
  1217. /**
  1218. * Add all the family of <b>node</b>, including <b>node</b> itself, to
  1219. * the smartlist <b>sl</b>.
  1220. *
  1221. * This is used to make sure we don't pick siblings in a single path, or
  1222. * pick more than one relay from a family for our entry guard list.
  1223. * Note that a node may be added to <b>sl</b> more than once if it is
  1224. * part of <b>node</b>'s family for more than one reason.
  1225. */
  1226. void
  1227. nodelist_add_node_and_family(smartlist_t *sl, const node_t *node)
  1228. {
  1229. /* XXXX MOVE */
  1230. const smartlist_t *all_nodes = nodelist_get_list();
  1231. const smartlist_t *declared_family;
  1232. const or_options_t *options = get_options();
  1233. tor_assert(node);
  1234. declared_family = node_get_declared_family(node);
  1235. /* Let's make sure that we have the node itself, if it's a real node. */
  1236. {
  1237. const node_t *real_node = node_get_by_id(node->identity);
  1238. if (real_node)
  1239. smartlist_add(sl, (node_t*)real_node);
  1240. }
  1241. /* First, add any nodes with similar network addresses. */
  1242. if (options->EnforceDistinctSubnets) {
  1243. tor_addr_t node_addr;
  1244. node_get_addr(node, &node_addr);
  1245. SMARTLIST_FOREACH_BEGIN(all_nodes, const node_t *, node2) {
  1246. tor_addr_t a;
  1247. node_get_addr(node2, &a);
  1248. if (addrs_in_same_network_family(&a, &node_addr))
  1249. smartlist_add(sl, (void*)node2);
  1250. } SMARTLIST_FOREACH_END(node2);
  1251. }
  1252. /* Now, add all nodes in the declared_family of this node, if they
  1253. * also declare this node to be in their family. */
  1254. if (declared_family) {
  1255. /* Add every r such that router declares familyness with node, and node
  1256. * declares familyhood with router. */
  1257. SMARTLIST_FOREACH_BEGIN(declared_family, const char *, name) {
  1258. const node_t *node2;
  1259. const smartlist_t *family2;
  1260. if (!(node2 = node_get_by_nickname(name, 0)))
  1261. continue;
  1262. if (!(family2 = node_get_declared_family(node2)))
  1263. continue;
  1264. SMARTLIST_FOREACH_BEGIN(family2, const char *, name2) {
  1265. if (node_nickname_matches(node, name2)) {
  1266. smartlist_add(sl, (void*)node2);
  1267. break;
  1268. }
  1269. } SMARTLIST_FOREACH_END(name2);
  1270. } SMARTLIST_FOREACH_END(name);
  1271. }
  1272. /* If the user declared any families locally, honor those too. */
  1273. if (options->NodeFamilySets) {
  1274. SMARTLIST_FOREACH(options->NodeFamilySets, const routerset_t *, rs, {
  1275. if (routerset_contains_node(rs, node)) {
  1276. routerset_get_all_nodes(sl, rs, NULL, 0);
  1277. }
  1278. });
  1279. }
  1280. }
  1281. /** Given a <b>router</b>, add every node_t in its family (including the
  1282. * node itself!) to <b>sl</b>.
  1283. *
  1284. * Note the type mismatch: This function takes a routerinfo, but adds nodes
  1285. * to the smartlist!
  1286. */
  1287. static void
  1288. routerlist_add_node_and_family(smartlist_t *sl, const routerinfo_t *router)
  1289. {
  1290. /* XXXX MOVE ? */
  1291. node_t fake_node;
  1292. const node_t *node = node_get_by_id(router->cache_info.identity_digest);;
  1293. if (node == NULL) {
  1294. memset(&fake_node, 0, sizeof(fake_node));
  1295. fake_node.ri = (routerinfo_t *)router;
  1296. memcpy(fake_node.identity, router->cache_info.identity_digest, DIGEST_LEN);
  1297. node = &fake_node;
  1298. }
  1299. nodelist_add_node_and_family(sl, node);
  1300. }
  1301. /** Return true iff <b>node</b> is named by some nickname in <b>lst</b>. */
  1302. static INLINE int
  1303. node_in_nickname_smartlist(const smartlist_t *lst, const node_t *node)
  1304. {
  1305. /* XXXX MOVE */
  1306. if (!lst) return 0;
  1307. SMARTLIST_FOREACH(lst, const char *, name, {
  1308. if (node_nickname_matches(node, name))
  1309. return 1;
  1310. });
  1311. return 0;
  1312. }
  1313. /** Return true iff r1 and r2 are in the same family, but not the same
  1314. * router. */
  1315. int
  1316. nodes_in_same_family(const node_t *node1, const node_t *node2)
  1317. {
  1318. /* XXXX MOVE */
  1319. const or_options_t *options = get_options();
  1320. /* Are they in the same family because of their addresses? */
  1321. if (options->EnforceDistinctSubnets) {
  1322. tor_addr_t a1, a2;
  1323. node_get_addr(node1, &a1);
  1324. node_get_addr(node2, &a2);
  1325. if (addrs_in_same_network_family(&a1, &a2))
  1326. return 1;
  1327. }
  1328. /* Are they in the same family because the agree they are? */
  1329. {
  1330. const smartlist_t *f1, *f2;
  1331. f1 = node_get_declared_family(node1);
  1332. f2 = node_get_declared_family(node2);
  1333. if (f1 && f2 &&
  1334. node_in_nickname_smartlist(f1, node2) &&
  1335. node_in_nickname_smartlist(f2, node1))
  1336. return 1;
  1337. }
  1338. /* Are they in the same option because the user says they are? */
  1339. if (options->NodeFamilySets) {
  1340. SMARTLIST_FOREACH(options->NodeFamilySets, const routerset_t *, rs, {
  1341. if (routerset_contains_node(rs, node1) &&
  1342. routerset_contains_node(rs, node2))
  1343. return 1;
  1344. });
  1345. }
  1346. return 0;
  1347. }
  1348. /** Return 1 iff any member of the (possibly NULL) comma-separated list
  1349. * <b>list</b> is an acceptable nickname or hexdigest for <b>router</b>. Else
  1350. * return 0.
  1351. */
  1352. int
  1353. router_nickname_is_in_list(const routerinfo_t *router, const char *list)
  1354. {
  1355. smartlist_t *nickname_list;
  1356. int v = 0;
  1357. if (!list)
  1358. return 0; /* definitely not */
  1359. tor_assert(router);
  1360. nickname_list = smartlist_new();
  1361. smartlist_split_string(nickname_list, list, ",",
  1362. SPLIT_SKIP_SPACE|SPLIT_STRIP_SPACE|SPLIT_IGNORE_BLANK, 0);
  1363. SMARTLIST_FOREACH(nickname_list, const char *, cp,
  1364. if (router_nickname_matches(router, cp)) {v=1;break;});
  1365. SMARTLIST_FOREACH(nickname_list, char *, cp, tor_free(cp));
  1366. smartlist_free(nickname_list);
  1367. return v;
  1368. }
  1369. /** Add every suitable node from our nodelist to <b>sl</b>, so that
  1370. * we can pick a node for a circuit.
  1371. */
  1372. static void
  1373. router_add_running_nodes_to_smartlist(smartlist_t *sl, int allow_invalid,
  1374. int need_uptime, int need_capacity,
  1375. int need_guard, int need_desc)
  1376. { /* XXXX MOVE */
  1377. SMARTLIST_FOREACH_BEGIN(nodelist_get_list(), const node_t *, node) {
  1378. if (!node->is_running ||
  1379. (!node->is_valid && !allow_invalid))
  1380. continue;
  1381. if (need_desc && !(node->ri || (node->rs && node->md)))
  1382. continue;
  1383. if (node->ri && node->ri->purpose != ROUTER_PURPOSE_GENERAL)
  1384. continue;
  1385. if (node_is_unreliable(node, need_uptime, need_capacity, need_guard))
  1386. continue;
  1387. smartlist_add(sl, (void *)node);
  1388. } SMARTLIST_FOREACH_END(node);
  1389. }
  1390. /** Look through the routerlist until we find a router that has my key.
  1391. Return it. */
  1392. const routerinfo_t *
  1393. routerlist_find_my_routerinfo(void)
  1394. {
  1395. if (!routerlist)
  1396. return NULL;
  1397. SMARTLIST_FOREACH(routerlist->routers, routerinfo_t *, router,
  1398. {
  1399. if (router_is_me(router))
  1400. return router;
  1401. });
  1402. return NULL;
  1403. }
  1404. /** Find a router that's up, that has this IP address, and
  1405. * that allows exit to this address:port, or return NULL if there
  1406. * isn't a good one.
  1407. * Don't exit enclave to excluded relays -- it wouldn't actually
  1408. * hurt anything, but this way there are fewer confused users.
  1409. */
  1410. const node_t *
  1411. router_find_exact_exit_enclave(const char *address, uint16_t port)
  1412. {/*XXXX MOVE*/
  1413. uint32_t addr;
  1414. struct in_addr in;
  1415. tor_addr_t a;
  1416. const or_options_t *options = get_options();
  1417. if (!tor_inet_aton(address, &in))
  1418. return NULL; /* it's not an IP already */
  1419. addr = ntohl(in.s_addr);
  1420. tor_addr_from_ipv4h(&a, addr);
  1421. SMARTLIST_FOREACH(nodelist_get_list(), const node_t *, node, {
  1422. if (node_get_addr_ipv4h(node) == addr &&
  1423. node->is_running &&
  1424. compare_tor_addr_to_node_policy(&a, port, node) ==
  1425. ADDR_POLICY_ACCEPTED &&
  1426. !routerset_contains_node(options->_ExcludeExitNodesUnion, node))
  1427. return node;
  1428. });
  1429. return NULL;
  1430. }
  1431. /** Return 1 if <b>router</b> is not suitable for these parameters, else 0.
  1432. * If <b>need_uptime</b> is non-zero, we require a minimum uptime.
  1433. * If <b>need_capacity</b> is non-zero, we require a minimum advertised
  1434. * bandwidth.
  1435. * If <b>need_guard</b>, we require that the router is a possible entry guard.
  1436. */
  1437. int
  1438. node_is_unreliable(const node_t *node, int need_uptime,
  1439. int need_capacity, int need_guard)
  1440. {
  1441. if (need_uptime && !node->is_stable)
  1442. return 1;
  1443. if (need_capacity && !node->is_fast)
  1444. return 1;
  1445. if (need_guard && !node->is_possible_guard)
  1446. return 1;
  1447. return 0;
  1448. }
  1449. /** Return the smaller of the router's configured BandwidthRate
  1450. * and its advertised capacity. */
  1451. uint32_t
  1452. router_get_advertised_bandwidth(const routerinfo_t *router)
  1453. {
  1454. if (router->bandwidthcapacity < router->bandwidthrate)
  1455. return router->bandwidthcapacity;
  1456. return router->bandwidthrate;
  1457. }
  1458. /** Do not weight any declared bandwidth more than this much when picking
  1459. * routers by bandwidth. */
  1460. #define DEFAULT_MAX_BELIEVABLE_BANDWIDTH 10000000 /* 10 MB/sec */
  1461. /** Return the smaller of the router's configured BandwidthRate
  1462. * and its advertised capacity, capped by max-believe-bw. */
  1463. uint32_t
  1464. router_get_advertised_bandwidth_capped(const routerinfo_t *router)
  1465. {
  1466. uint32_t result = router->bandwidthcapacity;
  1467. if (result > router->bandwidthrate)
  1468. result = router->bandwidthrate;
  1469. if (result > DEFAULT_MAX_BELIEVABLE_BANDWIDTH)
  1470. result = DEFAULT_MAX_BELIEVABLE_BANDWIDTH;
  1471. return result;
  1472. }
  1473. /** When weighting bridges, enforce these values as lower and upper
  1474. * bound for believable bandwidth, because there is no way for us
  1475. * to verify a bridge's bandwidth currently. */
  1476. #define BRIDGE_MIN_BELIEVABLE_BANDWIDTH 20000 /* 20 kB/sec */
  1477. #define BRIDGE_MAX_BELIEVABLE_BANDWIDTH 100000 /* 100 kB/sec */
  1478. /** Return the smaller of the router's configured BandwidthRate
  1479. * and its advertised capacity, making sure to stay within the
  1480. * interval between bridge-min-believe-bw and
  1481. * bridge-max-believe-bw. */
  1482. static uint32_t
  1483. bridge_get_advertised_bandwidth_bounded(routerinfo_t *router)
  1484. {
  1485. uint32_t result = router->bandwidthcapacity;
  1486. if (result > router->bandwidthrate)
  1487. result = router->bandwidthrate;
  1488. if (result > BRIDGE_MAX_BELIEVABLE_BANDWIDTH)
  1489. result = BRIDGE_MAX_BELIEVABLE_BANDWIDTH;
  1490. else if (result < BRIDGE_MIN_BELIEVABLE_BANDWIDTH)
  1491. result = BRIDGE_MIN_BELIEVABLE_BANDWIDTH;
  1492. return result;
  1493. }
  1494. /** Return bw*1000, unless bw*1000 would overflow, in which case return
  1495. * INT32_MAX. */
  1496. static INLINE int32_t
  1497. kb_to_bytes(uint32_t bw)
  1498. {
  1499. return (bw > (INT32_MAX/1000)) ? INT32_MAX : bw*1000;
  1500. }
  1501. /** Helper function:
  1502. * choose a random element of smartlist <b>sl</b> of nodes, weighted by
  1503. * the advertised bandwidth of each element using the consensus
  1504. * bandwidth weights.
  1505. *
  1506. * If <b>rule</b>==WEIGHT_FOR_EXIT. we're picking an exit node: consider all
  1507. * nodes' bandwidth equally regardless of their Exit status, since there may
  1508. * be some in the list because they exit to obscure ports. If
  1509. * <b>rule</b>==NO_WEIGHTING, we're picking a non-exit node: weight
  1510. * exit-node's bandwidth less depending on the smallness of the fraction of
  1511. * Exit-to-total bandwidth. If <b>rule</b>==WEIGHT_FOR_GUARD, we're picking a
  1512. * guard node: consider all guard's bandwidth equally. Otherwise, weight
  1513. * guards proportionally less.
  1514. */
  1515. static const node_t *
  1516. smartlist_choose_node_by_bandwidth_weights(smartlist_t *sl,
  1517. bandwidth_weight_rule_t rule)
  1518. {
  1519. int64_t weight_scale;
  1520. int64_t rand_bw;
  1521. double Wg = -1, Wm = -1, We = -1, Wd = -1;
  1522. double Wgb = -1, Wmb = -1, Web = -1, Wdb = -1;
  1523. double weighted_bw = 0;
  1524. double *bandwidths;
  1525. double tmp = 0;
  1526. unsigned int i;
  1527. int have_unknown = 0; /* true iff sl contains element not in consensus. */
  1528. /* Can't choose exit and guard at same time */
  1529. tor_assert(rule == NO_WEIGHTING ||
  1530. rule == WEIGHT_FOR_EXIT ||
  1531. rule == WEIGHT_FOR_GUARD ||
  1532. rule == WEIGHT_FOR_MID ||
  1533. rule == WEIGHT_FOR_DIR);
  1534. if (smartlist_len(sl) == 0) {
  1535. log_info(LD_CIRC,
  1536. "Empty routerlist passed in to consensus weight node "
  1537. "selection for rule %s",
  1538. bandwidth_weight_rule_to_string(rule));
  1539. return NULL;
  1540. }
  1541. weight_scale = circuit_build_times_get_bw_scale(NULL);
  1542. if (rule == WEIGHT_FOR_GUARD) {
  1543. Wg = networkstatus_get_bw_weight(NULL, "Wgg", -1);
  1544. Wm = networkstatus_get_bw_weight(NULL, "Wgm", -1); /* Bridges */
  1545. We = 0;
  1546. Wd = networkstatus_get_bw_weight(NULL, "Wgd", -1);
  1547. Wgb = networkstatus_get_bw_weight(NULL, "Wgb", -1);
  1548. Wmb = networkstatus_get_bw_weight(NULL, "Wmb", -1);
  1549. Web = networkstatus_get_bw_weight(NULL, "Web", -1);
  1550. Wdb = networkstatus_get_bw_weight(NULL, "Wdb", -1);
  1551. } else if (rule == WEIGHT_FOR_MID) {
  1552. Wg = networkstatus_get_bw_weight(NULL, "Wmg", -1);
  1553. Wm = networkstatus_get_bw_weight(NULL, "Wmm", -1);
  1554. We = networkstatus_get_bw_weight(NULL, "Wme", -1);
  1555. Wd = networkstatus_get_bw_weight(NULL, "Wmd", -1);
  1556. Wgb = networkstatus_get_bw_weight(NULL, "Wgb", -1);
  1557. Wmb = networkstatus_get_bw_weight(NULL, "Wmb", -1);
  1558. Web = networkstatus_get_bw_weight(NULL, "Web", -1);
  1559. Wdb = networkstatus_get_bw_weight(NULL, "Wdb", -1);
  1560. } else if (rule == WEIGHT_FOR_EXIT) {
  1561. // Guards CAN be exits if they have weird exit policies
  1562. // They are d then I guess...
  1563. We = networkstatus_get_bw_weight(NULL, "Wee", -1);
  1564. Wm = networkstatus_get_bw_weight(NULL, "Wem", -1); /* Odd exit policies */
  1565. Wd = networkstatus_get_bw_weight(NULL, "Wed", -1);
  1566. Wg = networkstatus_get_bw_weight(NULL, "Weg", -1); /* Odd exit policies */
  1567. Wgb = networkstatus_get_bw_weight(NULL, "Wgb", -1);
  1568. Wmb = networkstatus_get_bw_weight(NULL, "Wmb", -1);
  1569. Web = networkstatus_get_bw_weight(NULL, "Web", -1);
  1570. Wdb = networkstatus_get_bw_weight(NULL, "Wdb", -1);
  1571. } else if (rule == WEIGHT_FOR_DIR) {
  1572. We = networkstatus_get_bw_weight(NULL, "Wbe", -1);
  1573. Wm = networkstatus_get_bw_weight(NULL, "Wbm", -1);
  1574. Wd = networkstatus_get_bw_weight(NULL, "Wbd", -1);
  1575. Wg = networkstatus_get_bw_weight(NULL, "Wbg", -1);
  1576. Wgb = Wmb = Web = Wdb = weight_scale;
  1577. } else if (rule == NO_WEIGHTING) {
  1578. Wg = Wm = We = Wd = weight_scale;
  1579. Wgb = Wmb = Web = Wdb = weight_scale;
  1580. }
  1581. if (Wg < 0 || Wm < 0 || We < 0 || Wd < 0 || Wgb < 0 || Wmb < 0 || Wdb < 0
  1582. || Web < 0) {
  1583. log_debug(LD_CIRC,
  1584. "Got negative bandwidth weights. Defaulting to old selection"
  1585. " algorithm.");
  1586. return NULL; // Use old algorithm.
  1587. }
  1588. Wg /= weight_scale;
  1589. Wm /= weight_scale;
  1590. We /= weight_scale;
  1591. Wd /= weight_scale;
  1592. Wgb /= weight_scale;
  1593. Wmb /= weight_scale;
  1594. Web /= weight_scale;
  1595. Wdb /= weight_scale;
  1596. bandwidths = tor_malloc_zero(sizeof(double)*smartlist_len(sl));
  1597. // Cycle through smartlist and total the bandwidth.
  1598. SMARTLIST_FOREACH_BEGIN(sl, const node_t *, node) {
  1599. int is_exit = 0, is_guard = 0, is_dir = 0, this_bw = 0, is_me = 0;
  1600. double weight = 1;
  1601. is_exit = node->is_exit && ! node->is_bad_exit;
  1602. is_guard = node->is_possible_guard;
  1603. is_dir = node_is_dir(node);
  1604. if (node->rs) {
  1605. if (!node->rs->has_bandwidth) {
  1606. tor_free(bandwidths);
  1607. /* This should never happen, unless all the authorites downgrade
  1608. * to 0.2.0 or rogue routerstatuses get inserted into our consensus. */
  1609. log_warn(LD_BUG,
  1610. "Consensus is not listing bandwidths. Defaulting back to "
  1611. "old router selection algorithm.");
  1612. return NULL;
  1613. }
  1614. this_bw = kb_to_bytes(node->rs->bandwidth);
  1615. } else if (node->ri) {
  1616. /* bridge or other descriptor not in our consensus */
  1617. this_bw = bridge_get_advertised_bandwidth_bounded(node->ri);
  1618. have_unknown = 1;
  1619. } else {
  1620. /* We can't use this one. */
  1621. continue;
  1622. }
  1623. is_me = router_digest_is_me(node->identity);
  1624. if (is_guard && is_exit) {
  1625. weight = (is_dir ? Wdb*Wd : Wd);
  1626. } else if (is_guard) {
  1627. weight = (is_dir ? Wgb*Wg : Wg);
  1628. } else if (is_exit) {
  1629. weight = (is_dir ? Web*We : We);
  1630. } else { // middle
  1631. weight = (is_dir ? Wmb*Wm : Wm);
  1632. }
  1633. bandwidths[node_sl_idx] = weight*this_bw;
  1634. weighted_bw += weight*this_bw;
  1635. if (is_me)
  1636. sl_last_weighted_bw_of_me = weight*this_bw;
  1637. } SMARTLIST_FOREACH_END(node);
  1638. /* XXXX023 this is a kludge to expose these values. */
  1639. sl_last_total_weighted_bw = weighted_bw;
  1640. log_debug(LD_CIRC, "Choosing node for rule %s based on weights "
  1641. "Wg=%f Wm=%f We=%f Wd=%f with total bw %f",
  1642. bandwidth_weight_rule_to_string(rule),
  1643. Wg, Wm, We, Wd, weighted_bw);
  1644. /* If there is no bandwidth, choose at random */
  1645. if (DBL_TO_U64(weighted_bw) == 0) {
  1646. /* Don't warn when using bridges/relays not in the consensus */
  1647. if (!have_unknown)
  1648. log_warn(LD_CIRC,
  1649. "Weighted bandwidth is %f in node selection for rule %s",
  1650. weighted_bw, bandwidth_weight_rule_to_string(rule));
  1651. tor_free(bandwidths);
  1652. return smartlist_choose(sl);
  1653. }
  1654. rand_bw = crypto_rand_uint64(DBL_TO_U64(weighted_bw));
  1655. rand_bw++; /* crypto_rand_uint64() counts from 0, and we need to count
  1656. * from 1 below. See bug 1203 for details. */
  1657. /* Last, count through sl until we get to the element we picked */
  1658. tmp = 0.0;
  1659. for (i=0; i < (unsigned)smartlist_len(sl); i++) {
  1660. tmp += bandwidths[i];
  1661. if (tmp >= rand_bw)
  1662. break;
  1663. }
  1664. if (i == (unsigned)smartlist_len(sl)) {
  1665. /* This was once possible due to round-off error, but shouldn't be able
  1666. * to occur any longer. */
  1667. tor_fragile_assert();
  1668. --i;
  1669. log_warn(LD_BUG, "Round-off error in computing bandwidth had an effect on "
  1670. " which router we chose. Please tell the developers. "
  1671. "%f " U64_FORMAT " %f", tmp, U64_PRINTF_ARG(rand_bw),
  1672. weighted_bw);
  1673. }
  1674. tor_free(bandwidths);
  1675. return smartlist_get(sl, i);
  1676. }
  1677. /** Helper function:
  1678. * choose a random node_t element of smartlist <b>sl</b>, weighted by
  1679. * the advertised bandwidth of each element.
  1680. *
  1681. * If <b>rule</b>==WEIGHT_FOR_EXIT. we're picking an exit node: consider all
  1682. * nodes' bandwidth equally regardless of their Exit status, since there may
  1683. * be some in the list because they exit to obscure ports. If
  1684. * <b>rule</b>==NO_WEIGHTING, we're picking a non-exit node: weight
  1685. * exit-node's bandwidth less depending on the smallness of the fraction of
  1686. * Exit-to-total bandwidth. If <b>rule</b>==WEIGHT_FOR_GUARD, we're picking a
  1687. * guard node: consider all guard's bandwidth equally. Otherwise, weight
  1688. * guards proportionally less.
  1689. */
  1690. static const node_t *
  1691. smartlist_choose_node_by_bandwidth(smartlist_t *sl,
  1692. bandwidth_weight_rule_t rule)
  1693. {
  1694. unsigned i;
  1695. int32_t *bandwidths;
  1696. int is_exit;
  1697. int is_guard;
  1698. uint64_t total_nonexit_bw = 0, total_exit_bw = 0, total_bw = 0;
  1699. uint64_t total_nonguard_bw = 0, total_guard_bw = 0;
  1700. uint64_t rand_bw, tmp;
  1701. double exit_weight;
  1702. double guard_weight;
  1703. int n_unknown = 0;
  1704. bitarray_t *exit_bits;
  1705. bitarray_t *guard_bits;
  1706. int me_idx = -1;
  1707. // This function does not support WEIGHT_FOR_DIR
  1708. // or WEIGHT_FOR_MID
  1709. if (rule == WEIGHT_FOR_DIR || rule == WEIGHT_FOR_MID) {
  1710. rule = NO_WEIGHTING;
  1711. }
  1712. /* Can't choose exit and guard at same time */
  1713. tor_assert(rule == NO_WEIGHTING ||
  1714. rule == WEIGHT_FOR_EXIT ||
  1715. rule == WEIGHT_FOR_GUARD);
  1716. if (smartlist_len(sl) == 0) {
  1717. log_info(LD_CIRC,
  1718. "Empty routerlist passed in to old node selection for rule %s",
  1719. bandwidth_weight_rule_to_string(rule));
  1720. return NULL;
  1721. }
  1722. /* First count the total bandwidth weight, and make a list
  1723. * of each value. <0 means "unknown; no routerinfo." We use the
  1724. * bits of negative values to remember whether the router was fast (-x)&1
  1725. * and whether it was an exit (-x)&2 or guard (-x)&4. Yes, it's a hack. */
  1726. bandwidths = tor_malloc(sizeof(int32_t)*smartlist_len(sl));
  1727. exit_bits = bitarray_init_zero(smartlist_len(sl));
  1728. guard_bits = bitarray_init_zero(smartlist_len(sl));
  1729. /* Iterate over all the routerinfo_t or routerstatus_t, and */
  1730. SMARTLIST_FOREACH_BEGIN(sl, const node_t *, node) {
  1731. /* first, learn what bandwidth we think i has */
  1732. int is_known = 1;
  1733. int32_t flags = 0;
  1734. uint32_t this_bw = 0;
  1735. i = node_sl_idx;
  1736. if (router_digest_is_me(node->identity))
  1737. me_idx = node_sl_idx;
  1738. is_exit = node->is_exit;
  1739. is_guard = node->is_possible_guard;
  1740. if (node->rs) {
  1741. if (node->rs->has_bandwidth) {
  1742. this_bw = kb_to_bytes(node->rs->bandwidth);
  1743. } else { /* guess */
  1744. /* XXX023 once consensuses always list bandwidths, we can take
  1745. * this guessing business out. -RD */
  1746. is_known = 0;
  1747. flags = node->rs->is_fast ? 1 : 0;
  1748. flags |= is_exit ? 2 : 0;
  1749. flags |= is_guard ? 4 : 0;
  1750. }
  1751. } else if (node->ri) {
  1752. /* Must be a bridge if we're willing to use it */
  1753. this_bw = bridge_get_advertised_bandwidth_bounded(node->ri);
  1754. }
  1755. if (is_exit)
  1756. bitarray_set(exit_bits, i);
  1757. if (is_guard)
  1758. bitarray_set(guard_bits, i);
  1759. if (is_known) {
  1760. bandwidths[i] = (int32_t) this_bw; // safe since MAX_BELIEVABLE<INT32_MAX
  1761. // XXX this is no longer true! We don't always cap the bw anymore. Can
  1762. // a consensus make us overflow?-sh
  1763. tor_assert(bandwidths[i] >= 0);
  1764. if (is_guard)
  1765. total_guard_bw += this_bw;
  1766. else
  1767. total_nonguard_bw += this_bw;
  1768. if (is_exit)
  1769. total_exit_bw += this_bw;
  1770. else
  1771. total_nonexit_bw += this_bw;
  1772. } else {
  1773. ++n_unknown;
  1774. bandwidths[node_sl_idx] = -flags;
  1775. }
  1776. } SMARTLIST_FOREACH_END(node);
  1777. /* Now, fill in the unknown values. */
  1778. if (n_unknown) {
  1779. int32_t avg_fast, avg_slow;
  1780. if (total_exit_bw+total_nonexit_bw) {
  1781. /* if there's some bandwidth, there's at least one known router,
  1782. * so no worries about div by 0 here */
  1783. int n_known = smartlist_len(sl)-n_unknown;
  1784. avg_fast = avg_slow = (int32_t)
  1785. ((total_exit_bw+total_nonexit_bw)/((uint64_t) n_known));
  1786. } else {
  1787. avg_fast = 40000;
  1788. avg_slow = 20000;
  1789. }
  1790. for (i=0; i<(unsigned)smartlist_len(sl); ++i) {
  1791. int32_t bw = bandwidths[i];
  1792. if (bw>=0)
  1793. continue;
  1794. is_exit = ((-bw)&2);
  1795. is_guard = ((-bw)&4);
  1796. bandwidths[i] = ((-bw)&1) ? avg_fast : avg_slow;
  1797. if (is_exit)
  1798. total_exit_bw += bandwidths[i];
  1799. else
  1800. total_nonexit_bw += bandwidths[i];
  1801. if (is_guard)
  1802. total_guard_bw += bandwidths[i];
  1803. else
  1804. total_nonguard_bw += bandwidths[i];
  1805. }
  1806. }
  1807. /* If there's no bandwidth at all, pick at random. */
  1808. if (!(total_exit_bw+total_nonexit_bw)) {
  1809. tor_free(bandwidths);
  1810. tor_free(exit_bits);
  1811. tor_free(guard_bits);
  1812. return smartlist_choose(sl);
  1813. }
  1814. /* Figure out how to weight exits and guards */
  1815. {
  1816. double all_bw = U64_TO_DBL(total_exit_bw+total_nonexit_bw);
  1817. double exit_bw = U64_TO_DBL(total_exit_bw);
  1818. double guard_bw = U64_TO_DBL(total_guard_bw);
  1819. /*
  1820. * For detailed derivation of this formula, see
  1821. * http://archives.seul.org/or/dev/Jul-2007/msg00056.html
  1822. */
  1823. if (rule == WEIGHT_FOR_EXIT || !total_exit_bw)
  1824. exit_weight = 1.0;
  1825. else
  1826. exit_weight = 1.0 - all_bw/(3.0*exit_bw);
  1827. if (rule == WEIGHT_FOR_GUARD || !total_guard_bw)
  1828. guard_weight = 1.0;
  1829. else
  1830. guard_weight = 1.0 - all_bw/(3.0*guard_bw);
  1831. if (exit_weight <= 0.0)
  1832. exit_weight = 0.0;
  1833. if (guard_weight <= 0.0)
  1834. guard_weight = 0.0;
  1835. total_bw = 0;
  1836. sl_last_weighted_bw_of_me = 0;
  1837. for (i=0; i < (unsigned)smartlist_len(sl); i++) {
  1838. uint64_t bw;
  1839. is_exit = bitarray_is_set(exit_bits, i);
  1840. is_guard = bitarray_is_set(guard_bits, i);
  1841. if (is_exit && is_guard)
  1842. bw = ((uint64_t)(bandwidths[i] * exit_weight * guard_weight));
  1843. else if (is_guard)
  1844. bw = ((uint64_t)(bandwidths[i] * guard_weight));
  1845. else if (is_exit)
  1846. bw = ((uint64_t)(bandwidths[i] * exit_weight));
  1847. else
  1848. bw = bandwidths[i];
  1849. total_bw += bw;
  1850. if (i == (unsigned) me_idx)
  1851. sl_last_weighted_bw_of_me = bw;
  1852. }
  1853. }
  1854. /* XXXX023 this is a kludge to expose these values. */
  1855. sl_last_total_weighted_bw = total_bw;
  1856. log_debug(LD_CIRC, "Total weighted bw = "U64_FORMAT
  1857. ", exit bw = "U64_FORMAT
  1858. ", nonexit bw = "U64_FORMAT", exit weight = %f "
  1859. "(for exit == %d)"
  1860. ", guard bw = "U64_FORMAT
  1861. ", nonguard bw = "U64_FORMAT", guard weight = %f "
  1862. "(for guard == %d)",
  1863. U64_PRINTF_ARG(total_bw),
  1864. U64_PRINTF_ARG(total_exit_bw), U64_PRINTF_ARG(total_nonexit_bw),
  1865. exit_weight, (int)(rule == WEIGHT_FOR_EXIT),
  1866. U64_PRINTF_ARG(total_guard_bw), U64_PRINTF_ARG(total_nonguard_bw),
  1867. guard_weight, (int)(rule == WEIGHT_FOR_GUARD));
  1868. /* Almost done: choose a random value from the bandwidth weights. */
  1869. rand_bw = crypto_rand_uint64(total_bw);
  1870. rand_bw++; /* crypto_rand_uint64() counts from 0, and we need to count
  1871. * from 1 below. See bug 1203 for details. */
  1872. /* Last, count through sl until we get to the element we picked */
  1873. tmp = 0;
  1874. for (i=0; i < (unsigned)smartlist_len(sl); i++) {
  1875. is_exit = bitarray_is_set(exit_bits, i);
  1876. is_guard = bitarray_is_set(guard_bits, i);
  1877. /* Weights can be 0 if not counting guards/exits */
  1878. if (is_exit && is_guard)
  1879. tmp += ((uint64_t)(bandwidths[i] * exit_weight * guard_weight));
  1880. else if (is_guard)
  1881. tmp += ((uint64_t)(bandwidths[i] * guard_weight));
  1882. else if (is_exit)
  1883. tmp += ((uint64_t)(bandwidths[i] * exit_weight));
  1884. else
  1885. tmp += bandwidths[i];
  1886. if (tmp >= rand_bw)
  1887. break;
  1888. }
  1889. if (i == (unsigned)smartlist_len(sl)) {
  1890. /* This was once possible due to round-off error, but shouldn't be able
  1891. * to occur any longer. */
  1892. tor_fragile_assert();
  1893. --i;
  1894. log_warn(LD_BUG, "Round-off error in computing bandwidth had an effect on "
  1895. " which router we chose. Please tell the developers. "
  1896. U64_FORMAT " " U64_FORMAT " " U64_FORMAT, U64_PRINTF_ARG(tmp),
  1897. U64_PRINTF_ARG(rand_bw), U64_PRINTF_ARG(total_bw));
  1898. }
  1899. tor_free(bandwidths);
  1900. tor_free(exit_bits);
  1901. tor_free(guard_bits);
  1902. return smartlist_get(sl, i);
  1903. }
  1904. /** Choose a random element of status list <b>sl</b>, weighted by
  1905. * the advertised bandwidth of each node */
  1906. const node_t *
  1907. node_sl_choose_by_bandwidth(smartlist_t *sl,
  1908. bandwidth_weight_rule_t rule)
  1909. { /*XXXX MOVE */
  1910. const node_t *ret;
  1911. if ((ret = smartlist_choose_node_by_bandwidth_weights(sl, rule))) {
  1912. return ret;
  1913. } else {
  1914. return smartlist_choose_node_by_bandwidth(sl, rule);
  1915. }
  1916. }
  1917. /** Return a random running node from the nodelist. Never
  1918. * pick a node that is in
  1919. * <b>excludedsmartlist</b>, or which matches <b>excludedset</b>,
  1920. * even if they are the only nodes available.
  1921. * If <b>CRN_NEED_UPTIME</b> is set in flags and any router has more than
  1922. * a minimum uptime, return one of those.
  1923. * If <b>CRN_NEED_CAPACITY</b> is set in flags, weight your choice by the
  1924. * advertised capacity of each router.
  1925. * If <b>CRN_ALLOW_INVALID</b> is not set in flags, consider only Valid
  1926. * routers.
  1927. * If <b>CRN_NEED_GUARD</b> is set in flags, consider only Guard routers.
  1928. * If <b>CRN_WEIGHT_AS_EXIT</b> is set in flags, we weight bandwidths as if
  1929. * picking an exit node, otherwise we weight bandwidths for picking a relay
  1930. * node (that is, possibly discounting exit nodes).
  1931. * If <b>CRN_NEED_DESC</b> is set in flags, we only consider nodes that
  1932. * have a routerinfo or microdescriptor -- that is, enough info to be
  1933. * used to build a circuit.
  1934. */
  1935. const node_t *
  1936. router_choose_random_node(smartlist_t *excludedsmartlist,
  1937. routerset_t *excludedset,
  1938. router_crn_flags_t flags)
  1939. { /* XXXX MOVE */
  1940. const int need_uptime = (flags & CRN_NEED_UPTIME) != 0;
  1941. const int need_capacity = (flags & CRN_NEED_CAPACITY) != 0;
  1942. const int need_guard = (flags & CRN_NEED_GUARD) != 0;
  1943. const int allow_invalid = (flags & CRN_ALLOW_INVALID) != 0;
  1944. const int weight_for_exit = (flags & CRN_WEIGHT_AS_EXIT) != 0;
  1945. const int need_desc = (flags & CRN_NEED_DESC) != 0;
  1946. smartlist_t *sl=smartlist_new(),
  1947. *excludednodes=smartlist_new();
  1948. const node_t *choice = NULL;
  1949. const routerinfo_t *r;
  1950. bandwidth_weight_rule_t rule;
  1951. tor_assert(!(weight_for_exit && need_guard));
  1952. rule = weight_for_exit ? WEIGHT_FOR_EXIT :
  1953. (need_guard ? WEIGHT_FOR_GUARD : WEIGHT_FOR_MID);
  1954. /* Exclude relays that allow single hop exit circuits, if the user
  1955. * wants to (such relays might be risky) */
  1956. if (get_options()->ExcludeSingleHopRelays) {
  1957. SMARTLIST_FOREACH(nodelist_get_list(), node_t *, node,
  1958. if (node_allows_single_hop_exits(node)) {
  1959. smartlist_add(excludednodes, node);
  1960. });
  1961. }
  1962. if ((r = routerlist_find_my_routerinfo()))
  1963. routerlist_add_node_and_family(excludednodes, r);
  1964. router_add_running_nodes_to_smartlist(sl, allow_invalid,
  1965. need_uptime, need_capacity,
  1966. need_guard, need_desc);
  1967. smartlist_subtract(sl,excludednodes);
  1968. if (excludedsmartlist)
  1969. smartlist_subtract(sl,excludedsmartlist);
  1970. if (excludedset)
  1971. routerset_subtract_nodes(sl,excludedset);
  1972. // Always weight by bandwidth
  1973. choice = node_sl_choose_by_bandwidth(sl, rule);
  1974. smartlist_free(sl);
  1975. if (!choice && (need_uptime || need_capacity || need_guard)) {
  1976. /* try once more -- recurse but with fewer restrictions. */
  1977. log_info(LD_CIRC,
  1978. "We couldn't find any live%s%s%s routers; falling back "
  1979. "to list of all routers.",
  1980. need_capacity?", fast":"",
  1981. need_uptime?", stable":"",
  1982. need_guard?", guard":"");
  1983. flags &= ~ (CRN_NEED_UPTIME|CRN_NEED_CAPACITY|CRN_NEED_GUARD);
  1984. choice = router_choose_random_node(
  1985. excludedsmartlist, excludedset, flags);
  1986. }
  1987. smartlist_free(excludednodes);
  1988. if (!choice) {
  1989. log_warn(LD_CIRC,
  1990. "No available nodes when trying to choose node. Failing.");
  1991. }
  1992. return choice;
  1993. }
  1994. /** Helper: given an extended nickname in <b>hexdigest</b> try to decode it.
  1995. * Return 0 on success, -1 on failure. Store the result into the
  1996. * DIGEST_LEN-byte buffer at <b>digest_out</b>, the single character at
  1997. * <b>nickname_qualifier_char_out</b>, and the MAXNICKNAME_LEN+1-byte buffer
  1998. * at <b>nickname_out</b>.
  1999. *
  2000. * The recognized format is:
  2001. * HexName = Dollar? HexDigest NamePart?
  2002. * Dollar = '?'
  2003. * HexDigest = HexChar*20
  2004. * HexChar = 'a'..'f' | 'A'..'F' | '0'..'9'
  2005. * NamePart = QualChar Name
  2006. * QualChar = '=' | '~'
  2007. * Name = NameChar*(1..MAX_NICKNAME_LEN)
  2008. * NameChar = Any ASCII alphanumeric character
  2009. */
  2010. int
  2011. hex_digest_nickname_decode(const char *hexdigest,
  2012. char *digest_out,
  2013. char *nickname_qualifier_char_out,
  2014. char *nickname_out)
  2015. {
  2016. size_t len;
  2017. tor_assert(hexdigest);
  2018. if (hexdigest[0] == '$')
  2019. ++hexdigest;
  2020. len = strlen(hexdigest);
  2021. if (len < HEX_DIGEST_LEN) {
  2022. return -1;
  2023. } else if (len > HEX_DIGEST_LEN && (hexdigest[HEX_DIGEST_LEN] == '=' ||
  2024. hexdigest[HEX_DIGEST_LEN] == '~') &&
  2025. len <= HEX_DIGEST_LEN+1+MAX_NICKNAME_LEN) {
  2026. *nickname_qualifier_char_out = hexdigest[HEX_DIGEST_LEN];
  2027. strlcpy(nickname_out, hexdigest+HEX_DIGEST_LEN+1 , MAX_NICKNAME_LEN+1);
  2028. } else if (len == HEX_DIGEST_LEN) {
  2029. ;
  2030. } else {
  2031. return -1;
  2032. }
  2033. if (base16_decode(digest_out, DIGEST_LEN, hexdigest, HEX_DIGEST_LEN)<0)
  2034. return -1;
  2035. return 0;
  2036. }
  2037. /** Helper: Return true iff the <b>identity_digest</b> and <b>nickname</b>
  2038. * combination of a router, encoded in hexadecimal, matches <b>hexdigest</b>
  2039. * (which is optionally prefixed with a single dollar sign). Return false if
  2040. * <b>hexdigest</b> is malformed, or it doesn't match. */
  2041. static int
  2042. hex_digest_nickname_matches(const char *hexdigest, const char *identity_digest,
  2043. const char *nickname, int is_named)
  2044. {
  2045. char digest[DIGEST_LEN];
  2046. char nn_char='\0';
  2047. char nn_buf[MAX_NICKNAME_LEN+1];
  2048. if (hex_digest_nickname_decode(hexdigest, digest, &nn_char, nn_buf) == -1)
  2049. return 0;
  2050. if (nn_char == '=' || nn_char == '~') {
  2051. if (!nickname)
  2052. return 0;
  2053. if (strcasecmp(nn_buf, nickname))
  2054. return 0;
  2055. if (nn_char == '=' && !is_named)
  2056. return 0;
  2057. }
  2058. return tor_memeq(digest, identity_digest, DIGEST_LEN);
  2059. }
  2060. /** Return true iff <b>router</b> is listed as named in the current
  2061. * consensus. */
  2062. int
  2063. router_is_named(const routerinfo_t *router)
  2064. {
  2065. const char *digest =
  2066. networkstatus_get_router_digest_by_nickname(router->nickname);
  2067. return (digest &&
  2068. tor_memeq(digest, router->cache_info.identity_digest, DIGEST_LEN));
  2069. }
  2070. /** Return true iff the digest of <b>router</b>'s identity key,
  2071. * encoded in hexadecimal, matches <b>hexdigest</b> (which is
  2072. * optionally prefixed with a single dollar sign). Return false if
  2073. * <b>hexdigest</b> is malformed, or it doesn't match. */
  2074. static INLINE int
  2075. router_hex_digest_matches(const routerinfo_t *router, const char *hexdigest)
  2076. {
  2077. return hex_digest_nickname_matches(hexdigest,
  2078. router->cache_info.identity_digest,
  2079. router->nickname,
  2080. router_is_named(router));
  2081. }
  2082. /** Return true if <b>router</b>'s nickname matches <b>nickname</b>
  2083. * (case-insensitive), or if <b>router's</b> identity key digest
  2084. * matches a hexadecimal value stored in <b>nickname</b>. Return
  2085. * false otherwise. */
  2086. static int
  2087. router_nickname_matches(const routerinfo_t *router, const char *nickname)
  2088. {
  2089. if (nickname[0]!='$' && !strcasecmp(router->nickname, nickname))
  2090. return 1;
  2091. return router_hex_digest_matches(router, nickname);
  2092. }
  2093. /** Return true if <b>node</b>'s nickname matches <b>nickname</b>
  2094. * (case-insensitive), or if <b>node's</b> identity key digest
  2095. * matches a hexadecimal value stored in <b>nickname</b>. Return
  2096. * false otherwise. */
  2097. static int
  2098. node_nickname_matches(const node_t *node, const char *nickname)
  2099. {
  2100. const char *n = node_get_nickname(node);
  2101. if (n && nickname[0]!='$' && !strcasecmp(n, nickname))
  2102. return 1;
  2103. return hex_digest_nickname_matches(nickname,
  2104. node->identity,
  2105. n,
  2106. node_is_named(node));
  2107. }
  2108. /** Return the router in our routerlist whose (case-insensitive)
  2109. * nickname or (case-sensitive) hexadecimal key digest is
  2110. * <b>nickname</b>. Return NULL if no such router is known.
  2111. */
  2112. const routerinfo_t *
  2113. router_get_by_nickname(const char *nickname, int warn_if_unnamed)
  2114. {
  2115. #if 1
  2116. const node_t *node = node_get_by_nickname(nickname, warn_if_unnamed);
  2117. if (node)
  2118. return node->ri;
  2119. else
  2120. return NULL;
  2121. #else
  2122. int maybedigest;
  2123. char digest[DIGEST_LEN];
  2124. routerinfo_t *best_match=NULL;
  2125. int n_matches = 0;
  2126. const char *named_digest = NULL;
  2127. tor_assert(nickname);
  2128. if (!routerlist)
  2129. return NULL;
  2130. if (nickname[0] == '$')
  2131. return router_get_by_hexdigest(nickname);
  2132. if (!strcasecmp(nickname, UNNAMED_ROUTER_NICKNAME))
  2133. return NULL;
  2134. maybedigest = (strlen(nickname) >= HEX_DIGEST_LEN) &&
  2135. (base16_decode(digest,DIGEST_LEN,nickname,HEX_DIGEST_LEN) == 0);
  2136. if ((named_digest = networkstatus_get_router_digest_by_nickname(nickname))) {
  2137. return rimap_get(routerlist->identity_map, named_digest);
  2138. }
  2139. if (networkstatus_nickname_is_unnamed(nickname))
  2140. return NULL;
  2141. /* If we reach this point, there's no canonical value for the nickname. */
  2142. SMARTLIST_FOREACH(routerlist->routers, routerinfo_t *, router,
  2143. {
  2144. if (!strcasecmp(router->nickname, nickname)) {
  2145. ++n_matches;
  2146. if (n_matches <= 1 || router->is_running)
  2147. best_match = router;
  2148. } else if (maybedigest &&
  2149. tor_memeq(digest, router->cache_info.identity_digest,
  2150. DIGEST_LEN)) {
  2151. if (router_hex_digest_matches(router, nickname))
  2152. return router;
  2153. /* If we reach this point, we have a ID=name syntax that matches the
  2154. * identity but not the name. That isn't an acceptable match. */
  2155. }
  2156. });
  2157. if (best_match) {
  2158. if (warn_if_unnamed && n_matches > 1) {
  2159. smartlist_t *fps = smartlist_new();
  2160. int any_unwarned = 0;
  2161. SMARTLIST_FOREACH_BEGIN(routerlist->routers, routerinfo_t *, router) {
  2162. routerstatus_t *rs;
  2163. char fp[HEX_DIGEST_LEN+1];
  2164. if (strcasecmp(router->nickname, nickname))
  2165. continue;
  2166. rs = router_get_mutable_consensus_status_by_id(
  2167. router->cache_info.identity_digest);
  2168. if (rs && !rs->name_lookup_warned) {
  2169. rs->name_lookup_warned = 1;
  2170. any_unwarned = 1;
  2171. }
  2172. base16_encode(fp, sizeof(fp),
  2173. router->cache_info.identity_digest, DIGEST_LEN);
  2174. smartlist_add_asprintf(fps, "\"$%s\" for the one at %s:%d",
  2175. fp, router->address, router->or_port);
  2176. } SMARTLIST_FOREACH_END(router);
  2177. if (any_unwarned) {
  2178. char *alternatives = smartlist_join_strings(fps, "; ",0,NULL);
  2179. log_warn(LD_CONFIG,
  2180. "There are multiple matches for the nickname \"%s\","
  2181. " but none is listed as named by the directory authorities. "
  2182. "Choosing one arbitrarily. If you meant one in particular, "
  2183. "you should say %s.", nickname, alternatives);
  2184. tor_free(alternatives);
  2185. }
  2186. SMARTLIST_FOREACH(fps, char *, cp, tor_free(cp));
  2187. smartlist_free(fps);
  2188. } else if (warn_if_unnamed) {
  2189. routerstatus_t *rs = router_get_mutable_consensus_status_by_id(
  2190. best_match->cache_info.identity_digest);
  2191. if (rs && !rs->name_lookup_warned) {
  2192. char fp[HEX_DIGEST_LEN+1];
  2193. base16_encode(fp, sizeof(fp),
  2194. best_match->cache_info.identity_digest, DIGEST_LEN);
  2195. log_warn(LD_CONFIG, "You specified a server \"%s\" by name, but this "
  2196. "name is not registered, so it could be used by any server, "
  2197. "not just the one you meant. "
  2198. "To make sure you get the same server in the future, refer to "
  2199. "it by key, as \"$%s\".", nickname, fp);
  2200. rs->name_lookup_warned = 1;
  2201. }
  2202. }
  2203. return best_match;
  2204. }
  2205. return NULL;
  2206. #endif
  2207. }
  2208. /** Return true iff <b>digest</b> is the digest of the identity key of a
  2209. * trusted directory matching at least one bit of <b>type</b>. If <b>type</b>
  2210. * is zero, any authority is okay. */
  2211. int
  2212. router_digest_is_trusted_dir_type(const char *digest, dirinfo_type_t type)
  2213. {
  2214. if (!trusted_dir_servers)
  2215. return 0;
  2216. if (authdir_mode(get_options()) && router_digest_is_me(digest))
  2217. return 1;
  2218. SMARTLIST_FOREACH(trusted_dir_servers, trusted_dir_server_t *, ent,
  2219. if (tor_memeq(digest, ent->digest, DIGEST_LEN)) {
  2220. return (!type) || ((type & ent->type) != 0);
  2221. });
  2222. return 0;
  2223. }
  2224. /** Return true iff <b>addr</b> is the address of one of our trusted
  2225. * directory authorities. */
  2226. int
  2227. router_addr_is_trusted_dir(uint32_t addr)
  2228. {
  2229. if (!trusted_dir_servers)
  2230. return 0;
  2231. SMARTLIST_FOREACH(trusted_dir_servers, trusted_dir_server_t *, ent,
  2232. if (ent->addr == addr)
  2233. return 1;
  2234. );
  2235. return 0;
  2236. }
  2237. /** If hexdigest is correctly formed, base16_decode it into
  2238. * digest, which must have DIGEST_LEN space in it.
  2239. * Return 0 on success, -1 on failure.
  2240. */
  2241. int
  2242. hexdigest_to_digest(const char *hexdigest, char *digest)
  2243. {
  2244. if (hexdigest[0]=='$')
  2245. ++hexdigest;
  2246. if (strlen(hexdigest) < HEX_DIGEST_LEN ||
  2247. base16_decode(digest,DIGEST_LEN,hexdigest,HEX_DIGEST_LEN) < 0)
  2248. return -1;
  2249. return 0;
  2250. }
  2251. /** Return the router in our routerlist whose hexadecimal key digest
  2252. * is <b>hexdigest</b>. Return NULL if no such router is known. */
  2253. const routerinfo_t *
  2254. router_get_by_hexdigest(const char *hexdigest)
  2255. {
  2256. if (is_legal_nickname(hexdigest))
  2257. return NULL;
  2258. /* It's not a legal nickname, so it must be a hexdigest or nothing. */
  2259. return router_get_by_nickname(hexdigest, 1);
  2260. }
  2261. /** As router_get_by_id_digest,but return a pointer that you're allowed to
  2262. * modify */
  2263. routerinfo_t *
  2264. router_get_mutable_by_digest(const char *digest)
  2265. {
  2266. tor_assert(digest);
  2267. if (!routerlist) return NULL;
  2268. // routerlist_assert_ok(routerlist);
  2269. return rimap_get(routerlist->identity_map, digest);
  2270. }
  2271. /** Return the router in our routerlist whose 20-byte key digest
  2272. * is <b>digest</b>. Return NULL if no such router is known. */
  2273. const routerinfo_t *
  2274. router_get_by_id_digest(const char *digest)
  2275. {
  2276. return router_get_mutable_by_digest(digest);
  2277. }
  2278. /** Return the router in our routerlist whose 20-byte descriptor
  2279. * is <b>digest</b>. Return NULL if no such router is known. */
  2280. signed_descriptor_t *
  2281. router_get_by_descriptor_digest(const char *digest)
  2282. {
  2283. tor_assert(digest);
  2284. if (!routerlist) return NULL;
  2285. return sdmap_get(routerlist->desc_digest_map, digest);
  2286. }
  2287. /** Return the signed descriptor for the router in our routerlist whose
  2288. * 20-byte extra-info digest is <b>digest</b>. Return NULL if no such router
  2289. * is known. */
  2290. signed_descriptor_t *
  2291. router_get_by_extrainfo_digest(const char *digest)
  2292. {
  2293. tor_assert(digest);
  2294. if (!routerlist) return NULL;
  2295. return sdmap_get(routerlist->desc_by_eid_map, digest);
  2296. }
  2297. /** Return the signed descriptor for the extrainfo_t in our routerlist whose
  2298. * extra-info-digest is <b>digest</b>. Return NULL if no such extra-info
  2299. * document is known. */
  2300. signed_descriptor_t *
  2301. extrainfo_get_by_descriptor_digest(const char *digest)
  2302. {
  2303. extrainfo_t *ei;
  2304. tor_assert(digest);
  2305. if (!routerlist) return NULL;
  2306. ei = eimap_get(routerlist->extra_info_map, digest);
  2307. return ei ? &ei->cache_info : NULL;
  2308. }
  2309. /** Return a pointer to the signed textual representation of a descriptor.
  2310. * The returned string is not guaranteed to be NUL-terminated: the string's
  2311. * length will be in desc-\>signed_descriptor_len.
  2312. *
  2313. * If <b>with_annotations</b> is set, the returned string will include
  2314. * the annotations
  2315. * (if any) preceding the descriptor. This will increase the length of the
  2316. * string by desc-\>annotations_len.
  2317. *
  2318. * The caller must not free the string returned.
  2319. */
  2320. static const char *
  2321. signed_descriptor_get_body_impl(const signed_descriptor_t *desc,
  2322. int with_annotations)
  2323. {
  2324. const char *r = NULL;
  2325. size_t len = desc->signed_descriptor_len;
  2326. off_t offset = desc->saved_offset;
  2327. if (with_annotations)
  2328. len += desc->annotations_len;
  2329. else
  2330. offset += desc->annotations_len;
  2331. tor_assert(len > 32);
  2332. if (desc->saved_location == SAVED_IN_CACHE && routerlist) {
  2333. desc_store_t *store = desc_get_store(router_get_routerlist(), desc);
  2334. if (store && store->mmap) {
  2335. tor_assert(desc->saved_offset + len <= store->mmap->size);
  2336. r = store->mmap->data + offset;
  2337. } else if (store) {
  2338. log_err(LD_DIR, "We couldn't read a descriptor that is supposedly "
  2339. "mmaped in our cache. Is another process running in our data "
  2340. "directory? Exiting.");
  2341. exit(1);
  2342. }
  2343. }
  2344. if (!r) /* no mmap, or not in cache. */
  2345. r = desc->signed_descriptor_body +
  2346. (with_annotations ? 0 : desc->annotations_len);
  2347. tor_assert(r);
  2348. if (!with_annotations) {
  2349. if (fast_memcmp("router ", r, 7) && fast_memcmp("extra-info ", r, 11)) {
  2350. char *cp = tor_strndup(r, 64);
  2351. log_err(LD_DIR, "descriptor at %p begins with unexpected string %s. "
  2352. "Is another process running in our data directory? Exiting.",
  2353. desc, escaped(cp));
  2354. exit(1);
  2355. }
  2356. }
  2357. return r;
  2358. }
  2359. /** Return a pointer to the signed textual representation of a descriptor.
  2360. * The returned string is not guaranteed to be NUL-terminated: the string's
  2361. * length will be in desc-\>signed_descriptor_len.
  2362. *
  2363. * The caller must not free the string returned.
  2364. */
  2365. const char *
  2366. signed_descriptor_get_body(const signed_descriptor_t *desc)
  2367. {
  2368. return signed_descriptor_get_body_impl(desc, 0);
  2369. }
  2370. /** As signed_descriptor_get_body(), but points to the beginning of the
  2371. * annotations section rather than the beginning of the descriptor. */
  2372. const char *
  2373. signed_descriptor_get_annotations(const signed_descriptor_t *desc)
  2374. {
  2375. return signed_descriptor_get_body_impl(desc, 1);
  2376. }
  2377. /** Return the current list of all known routers. */
  2378. routerlist_t *
  2379. router_get_routerlist(void)
  2380. {
  2381. if (PREDICT_UNLIKELY(!routerlist)) {
  2382. routerlist = tor_malloc_zero(sizeof(routerlist_t));
  2383. routerlist->routers = smartlist_new();
  2384. routerlist->old_routers = smartlist_new();
  2385. routerlist->identity_map = rimap_new();
  2386. routerlist->desc_digest_map = sdmap_new();
  2387. routerlist->desc_by_eid_map = sdmap_new();
  2388. routerlist->extra_info_map = eimap_new();
  2389. routerlist->desc_store.fname_base = "cached-descriptors";
  2390. routerlist->desc_store.fname_alt_base = "cached-routers";
  2391. routerlist->extrainfo_store.fname_base = "cached-extrainfo";
  2392. routerlist->desc_store.type = ROUTER_STORE;
  2393. routerlist->extrainfo_store.type = EXTRAINFO_STORE;
  2394. routerlist->desc_store.description = "router descriptors";
  2395. routerlist->extrainfo_store.description = "extra-info documents";
  2396. }
  2397. return routerlist;
  2398. }
  2399. /** Free all storage held by <b>router</b>. */
  2400. void
  2401. routerinfo_free(routerinfo_t *router)
  2402. {
  2403. if (!router)
  2404. return;
  2405. tor_free(router->cache_info.signed_descriptor_body);
  2406. tor_free(router->address);
  2407. tor_free(router->nickname);
  2408. tor_free(router->platform);
  2409. tor_free(router->contact_info);
  2410. if (router->onion_pkey)
  2411. crypto_pk_free(router->onion_pkey);
  2412. if (router->identity_pkey)
  2413. crypto_pk_free(router->identity_pkey);
  2414. if (router->declared_family) {
  2415. SMARTLIST_FOREACH(router->declared_family, char *, s, tor_free(s));
  2416. smartlist_free(router->declared_family);
  2417. }
  2418. addr_policy_list_free(router->exit_policy);
  2419. memset(router, 77, sizeof(routerinfo_t));
  2420. tor_free(router);
  2421. }
  2422. /** Release all storage held by <b>extrainfo</b> */
  2423. void
  2424. extrainfo_free(extrainfo_t *extrainfo)
  2425. {
  2426. if (!extrainfo)
  2427. return;
  2428. tor_free(extrainfo->cache_info.signed_descriptor_body);
  2429. tor_free(extrainfo->pending_sig);
  2430. memset(extrainfo, 88, sizeof(extrainfo_t)); /* debug bad memory usage */
  2431. tor_free(extrainfo);
  2432. }
  2433. /** Release storage held by <b>sd</b>. */
  2434. static void
  2435. signed_descriptor_free(signed_descriptor_t *sd)
  2436. {
  2437. if (!sd)
  2438. return;
  2439. tor_free(sd->signed_descriptor_body);
  2440. memset(sd, 99, sizeof(signed_descriptor_t)); /* Debug bad mem usage */
  2441. tor_free(sd);
  2442. }
  2443. /** Extract a signed_descriptor_t from a general routerinfo, and free the
  2444. * routerinfo.
  2445. */
  2446. static signed_descriptor_t *
  2447. signed_descriptor_from_routerinfo(routerinfo_t *ri)
  2448. {
  2449. signed_descriptor_t *sd;
  2450. tor_assert(ri->purpose == ROUTER_PURPOSE_GENERAL);
  2451. sd = tor_malloc_zero(sizeof(signed_descriptor_t));
  2452. memcpy(sd, &(ri->cache_info), sizeof(signed_descriptor_t));
  2453. sd->routerlist_index = -1;
  2454. ri->cache_info.signed_descriptor_body = NULL;
  2455. routerinfo_free(ri);
  2456. return sd;
  2457. }
  2458. /** Helper: free the storage held by the extrainfo_t in <b>e</b>. */
  2459. static void
  2460. _extrainfo_free(void *e)
  2461. {
  2462. extrainfo_free(e);
  2463. }
  2464. /** Free all storage held by a routerlist <b>rl</b>. */
  2465. void
  2466. routerlist_free(routerlist_t *rl)
  2467. {
  2468. if (!rl)
  2469. return;
  2470. rimap_free(rl->identity_map, NULL);
  2471. sdmap_free(rl->desc_digest_map, NULL);
  2472. sdmap_free(rl->desc_by_eid_map, NULL);
  2473. eimap_free(rl->extra_info_map, _extrainfo_free);
  2474. SMARTLIST_FOREACH(rl->routers, routerinfo_t *, r,
  2475. routerinfo_free(r));
  2476. SMARTLIST_FOREACH(rl->old_routers, signed_descriptor_t *, sd,
  2477. signed_descriptor_free(sd));
  2478. smartlist_free(rl->routers);
  2479. smartlist_free(rl->old_routers);
  2480. if (routerlist->desc_store.mmap)
  2481. tor_munmap_file(routerlist->desc_store.mmap);
  2482. if (routerlist->extrainfo_store.mmap)
  2483. tor_munmap_file(routerlist->extrainfo_store.mmap);
  2484. tor_free(rl);
  2485. router_dir_info_changed();
  2486. }
  2487. /** Log information about how much memory is being used for routerlist,
  2488. * at log level <b>severity</b>. */
  2489. void
  2490. dump_routerlist_mem_usage(int severity)
  2491. {
  2492. uint64_t livedescs = 0;
  2493. uint64_t olddescs = 0;
  2494. if (!routerlist)
  2495. return;
  2496. SMARTLIST_FOREACH(routerlist->routers, routerinfo_t *, r,
  2497. livedescs += r->cache_info.signed_descriptor_len);
  2498. SMARTLIST_FOREACH(routerlist->old_routers, signed_descriptor_t *, sd,
  2499. olddescs += sd->signed_descriptor_len);
  2500. log(severity, LD_DIR,
  2501. "In %d live descriptors: "U64_FORMAT" bytes. "
  2502. "In %d old descriptors: "U64_FORMAT" bytes.",
  2503. smartlist_len(routerlist->routers), U64_PRINTF_ARG(livedescs),
  2504. smartlist_len(routerlist->old_routers), U64_PRINTF_ARG(olddescs));
  2505. }
  2506. /** Debugging helper: If <b>idx</b> is nonnegative, assert that <b>ri</b> is
  2507. * in <b>sl</b> at position <b>idx</b>. Otherwise, search <b>sl</b> for
  2508. * <b>ri</b>. Return the index of <b>ri</b> in <b>sl</b>, or -1 if <b>ri</b>
  2509. * is not in <b>sl</b>. */
  2510. static INLINE int
  2511. _routerlist_find_elt(smartlist_t *sl, void *ri, int idx)
  2512. {
  2513. if (idx < 0) {
  2514. idx = -1;
  2515. SMARTLIST_FOREACH(sl, routerinfo_t *, r,
  2516. if (r == ri) {
  2517. idx = r_sl_idx;
  2518. break;
  2519. });
  2520. } else {
  2521. tor_assert(idx < smartlist_len(sl));
  2522. tor_assert(smartlist_get(sl, idx) == ri);
  2523. };
  2524. return idx;
  2525. }
  2526. /** Insert an item <b>ri</b> into the routerlist <b>rl</b>, updating indices
  2527. * as needed. There must be no previous member of <b>rl</b> with the same
  2528. * identity digest as <b>ri</b>: If there is, call routerlist_replace
  2529. * instead.
  2530. */
  2531. static void
  2532. routerlist_insert(routerlist_t *rl, routerinfo_t *ri)
  2533. {
  2534. routerinfo_t *ri_old;
  2535. signed_descriptor_t *sd_old;
  2536. {
  2537. const routerinfo_t *ri_generated = router_get_my_routerinfo();
  2538. tor_assert(ri_generated != ri);
  2539. }
  2540. tor_assert(ri->cache_info.routerlist_index == -1);
  2541. ri_old = rimap_set(rl->identity_map, ri->cache_info.identity_digest, ri);
  2542. tor_assert(!ri_old);
  2543. sd_old = sdmap_set(rl->desc_digest_map,
  2544. ri->cache_info.signed_descriptor_digest,
  2545. &(ri->cache_info));
  2546. if (sd_old) {
  2547. int idx = sd_old->routerlist_index;
  2548. sd_old->routerlist_index = -1;
  2549. smartlist_del(rl->old_routers, idx);
  2550. if (idx < smartlist_len(rl->old_routers)) {
  2551. signed_descriptor_t *d = smartlist_get(rl->old_routers, idx);
  2552. d->routerlist_index = idx;
  2553. }
  2554. rl->desc_store.bytes_dropped += sd_old->signed_descriptor_len;
  2555. sdmap_remove(rl->desc_by_eid_map, sd_old->extra_info_digest);
  2556. signed_descriptor_free(sd_old);
  2557. }
  2558. if (!tor_digest_is_zero(ri->cache_info.extra_info_digest))
  2559. sdmap_set(rl->desc_by_eid_map, ri->cache_info.extra_info_digest,
  2560. &ri->cache_info);
  2561. smartlist_add(rl->routers, ri);
  2562. ri->cache_info.routerlist_index = smartlist_len(rl->routers) - 1;
  2563. nodelist_add_routerinfo(ri);
  2564. router_dir_info_changed();
  2565. #ifdef DEBUG_ROUTERLIST
  2566. routerlist_assert_ok(rl);
  2567. #endif
  2568. }
  2569. /** Adds the extrainfo_t <b>ei</b> to the routerlist <b>rl</b>, if there is a
  2570. * corresponding router in rl-\>routers or rl-\>old_routers. Return true iff
  2571. * we actually inserted <b>ei</b>. Free <b>ei</b> if it isn't inserted. */
  2572. static int
  2573. extrainfo_insert(routerlist_t *rl, extrainfo_t *ei)
  2574. {
  2575. int r = 0;
  2576. routerinfo_t *ri = rimap_get(rl->identity_map,
  2577. ei->cache_info.identity_digest);
  2578. signed_descriptor_t *sd =
  2579. sdmap_get(rl->desc_by_eid_map, ei->cache_info.signed_descriptor_digest);
  2580. extrainfo_t *ei_tmp;
  2581. {
  2582. extrainfo_t *ei_generated = router_get_my_extrainfo();
  2583. tor_assert(ei_generated != ei);
  2584. }
  2585. if (!ri) {
  2586. /* This router is unknown; we can't even verify the signature. Give up.*/
  2587. goto done;
  2588. }
  2589. if (routerinfo_incompatible_with_extrainfo(ri, ei, sd, NULL)) {
  2590. goto done;
  2591. }
  2592. /* Okay, if we make it here, we definitely have a router corresponding to
  2593. * this extrainfo. */
  2594. ei_tmp = eimap_set(rl->extra_info_map,
  2595. ei->cache_info.signed_descriptor_digest,
  2596. ei);
  2597. r = 1;
  2598. if (ei_tmp) {
  2599. rl->extrainfo_store.bytes_dropped +=
  2600. ei_tmp->cache_info.signed_descriptor_len;
  2601. extrainfo_free(ei_tmp);
  2602. }
  2603. done:
  2604. if (r == 0)
  2605. extrainfo_free(ei);
  2606. #ifdef DEBUG_ROUTERLIST
  2607. routerlist_assert_ok(rl);
  2608. #endif
  2609. return r;
  2610. }
  2611. #define should_cache_old_descriptors() \
  2612. directory_caches_dir_info(get_options())
  2613. /** If we're a directory cache and routerlist <b>rl</b> doesn't have
  2614. * a copy of router <b>ri</b> yet, add it to the list of old (not
  2615. * recommended but still served) descriptors. Else free it. */
  2616. static void
  2617. routerlist_insert_old(routerlist_t *rl, routerinfo_t *ri)
  2618. {
  2619. {
  2620. const routerinfo_t *ri_generated = router_get_my_routerinfo();
  2621. tor_assert(ri_generated != ri);
  2622. }
  2623. tor_assert(ri->cache_info.routerlist_index == -1);
  2624. if (should_cache_old_descriptors() &&
  2625. ri->purpose == ROUTER_PURPOSE_GENERAL &&
  2626. !sdmap_get(rl->desc_digest_map,
  2627. ri->cache_info.signed_descriptor_digest)) {
  2628. signed_descriptor_t *sd = signed_descriptor_from_routerinfo(ri);
  2629. sdmap_set(rl->desc_digest_map, sd->signed_descriptor_digest, sd);
  2630. smartlist_add(rl->old_routers, sd);
  2631. sd->routerlist_index = smartlist_len(rl->old_routers)-1;
  2632. if (!tor_digest_is_zero(sd->extra_info_digest))
  2633. sdmap_set(rl->desc_by_eid_map, sd->extra_info_digest, sd);
  2634. } else {
  2635. routerinfo_free(ri);
  2636. }
  2637. #ifdef DEBUG_ROUTERLIST
  2638. routerlist_assert_ok(rl);
  2639. #endif
  2640. }
  2641. /** Remove an item <b>ri</b> from the routerlist <b>rl</b>, updating indices
  2642. * as needed. If <b>idx</b> is nonnegative and smartlist_get(rl-&gt;routers,
  2643. * idx) == ri, we don't need to do a linear search over the list to decide
  2644. * which to remove. We fill the gap in rl-&gt;routers with a later element in
  2645. * the list, if any exists. <b>ri</b> is freed.
  2646. *
  2647. * If <b>make_old</b> is true, instead of deleting the router, we try adding
  2648. * it to rl-&gt;old_routers. */
  2649. void
  2650. routerlist_remove(routerlist_t *rl, routerinfo_t *ri, int make_old, time_t now)
  2651. {
  2652. routerinfo_t *ri_tmp;
  2653. extrainfo_t *ei_tmp;
  2654. int idx = ri->cache_info.routerlist_index;
  2655. tor_assert(0 <= idx && idx < smartlist_len(rl->routers));
  2656. tor_assert(smartlist_get(rl->routers, idx) == ri);
  2657. nodelist_remove_routerinfo(ri);
  2658. /* make sure the rephist module knows that it's not running */
  2659. rep_hist_note_router_unreachable(ri->cache_info.identity_digest, now);
  2660. ri->cache_info.routerlist_index = -1;
  2661. smartlist_del(rl->routers, idx);
  2662. if (idx < smartlist_len(rl->routers)) {
  2663. routerinfo_t *r = smartlist_get(rl->routers, idx);
  2664. r->cache_info.routerlist_index = idx;
  2665. }
  2666. ri_tmp = rimap_remove(rl->identity_map, ri->cache_info.identity_digest);
  2667. router_dir_info_changed();
  2668. tor_assert(ri_tmp == ri);
  2669. if (make_old && should_cache_old_descriptors() &&
  2670. ri->purpose == ROUTER_PURPOSE_GENERAL) {
  2671. signed_descriptor_t *sd;
  2672. sd = signed_descriptor_from_routerinfo(ri);
  2673. smartlist_add(rl->old_routers, sd);
  2674. sd->routerlist_index = smartlist_len(rl->old_routers)-1;
  2675. sdmap_set(rl->desc_digest_map, sd->signed_descriptor_digest, sd);
  2676. if (!tor_digest_is_zero(sd->extra_info_digest))
  2677. sdmap_set(rl->desc_by_eid_map, sd->extra_info_digest, sd);
  2678. } else {
  2679. signed_descriptor_t *sd_tmp;
  2680. sd_tmp = sdmap_remove(rl->desc_digest_map,
  2681. ri->cache_info.signed_descriptor_digest);
  2682. tor_assert(sd_tmp == &(ri->cache_info));
  2683. rl->desc_store.bytes_dropped += ri->cache_info.signed_descriptor_len;
  2684. ei_tmp = eimap_remove(rl->extra_info_map,
  2685. ri->cache_info.extra_info_digest);
  2686. if (ei_tmp) {
  2687. rl->extrainfo_store.bytes_dropped +=
  2688. ei_tmp->cache_info.signed_descriptor_len;
  2689. extrainfo_free(ei_tmp);
  2690. }
  2691. if (!tor_digest_is_zero(ri->cache_info.extra_info_digest))
  2692. sdmap_remove(rl->desc_by_eid_map, ri->cache_info.extra_info_digest);
  2693. routerinfo_free(ri);
  2694. }
  2695. #ifdef DEBUG_ROUTERLIST
  2696. routerlist_assert_ok(rl);
  2697. #endif
  2698. }
  2699. /** Remove a signed_descriptor_t <b>sd</b> from <b>rl</b>-\>old_routers, and
  2700. * adjust <b>rl</b> as appropriate. <b>idx</b> is -1, or the index of
  2701. * <b>sd</b>. */
  2702. static void
  2703. routerlist_remove_old(routerlist_t *rl, signed_descriptor_t *sd, int idx)
  2704. {
  2705. signed_descriptor_t *sd_tmp;
  2706. extrainfo_t *ei_tmp;
  2707. desc_store_t *store;
  2708. if (idx == -1) {
  2709. idx = sd->routerlist_index;
  2710. }
  2711. tor_assert(0 <= idx && idx < smartlist_len(rl->old_routers));
  2712. /* XXXX edmanm's bridge relay triggered the following assert while
  2713. * running 0.2.0.12-alpha. If anybody triggers this again, see if we
  2714. * can get a backtrace. */
  2715. tor_assert(smartlist_get(rl->old_routers, idx) == sd);
  2716. tor_assert(idx == sd->routerlist_index);
  2717. sd->routerlist_index = -1;
  2718. smartlist_del(rl->old_routers, idx);
  2719. if (idx < smartlist_len(rl->old_routers)) {
  2720. signed_descriptor_t *d = smartlist_get(rl->old_routers, idx);
  2721. d->routerlist_index = idx;
  2722. }
  2723. sd_tmp = sdmap_remove(rl->desc_digest_map,
  2724. sd->signed_descriptor_digest);
  2725. tor_assert(sd_tmp == sd);
  2726. store = desc_get_store(rl, sd);
  2727. if (store)
  2728. store->bytes_dropped += sd->signed_descriptor_len;
  2729. ei_tmp = eimap_remove(rl->extra_info_map,
  2730. sd->extra_info_digest);
  2731. if (ei_tmp) {
  2732. rl->extrainfo_store.bytes_dropped +=
  2733. ei_tmp->cache_info.signed_descriptor_len;
  2734. extrainfo_free(ei_tmp);
  2735. }
  2736. if (!tor_digest_is_zero(sd->extra_info_digest))
  2737. sdmap_remove(rl->desc_by_eid_map, sd->extra_info_digest);
  2738. signed_descriptor_free(sd);
  2739. #ifdef DEBUG_ROUTERLIST
  2740. routerlist_assert_ok(rl);
  2741. #endif
  2742. }
  2743. /** Remove <b>ri_old</b> from the routerlist <b>rl</b>, and replace it with
  2744. * <b>ri_new</b>, updating all index info. If <b>idx</b> is nonnegative and
  2745. * smartlist_get(rl-&gt;routers, idx) == ri, we don't need to do a linear
  2746. * search over the list to decide which to remove. We put ri_new in the same
  2747. * index as ri_old, if possible. ri is freed as appropriate.
  2748. *
  2749. * If should_cache_descriptors() is true, instead of deleting the router,
  2750. * we add it to rl-&gt;old_routers. */
  2751. static void
  2752. routerlist_replace(routerlist_t *rl, routerinfo_t *ri_old,
  2753. routerinfo_t *ri_new)
  2754. {
  2755. int idx;
  2756. int same_descriptors;
  2757. routerinfo_t *ri_tmp;
  2758. extrainfo_t *ei_tmp;
  2759. {
  2760. const routerinfo_t *ri_generated = router_get_my_routerinfo();
  2761. tor_assert(ri_generated != ri_new);
  2762. }
  2763. tor_assert(ri_old != ri_new);
  2764. tor_assert(ri_new->cache_info.routerlist_index == -1);
  2765. idx = ri_old->cache_info.routerlist_index;
  2766. tor_assert(0 <= idx && idx < smartlist_len(rl->routers));
  2767. tor_assert(smartlist_get(rl->routers, idx) == ri_old);
  2768. nodelist_remove_routerinfo(ri_old);
  2769. nodelist_add_routerinfo(ri_new);
  2770. router_dir_info_changed();
  2771. if (idx >= 0) {
  2772. smartlist_set(rl->routers, idx, ri_new);
  2773. ri_old->cache_info.routerlist_index = -1;
  2774. ri_new->cache_info.routerlist_index = idx;
  2775. /* Check that ri_old is not in rl->routers anymore: */
  2776. tor_assert( _routerlist_find_elt(rl->routers, ri_old, -1) == -1 );
  2777. } else {
  2778. log_warn(LD_BUG, "Appending entry from routerlist_replace.");
  2779. routerlist_insert(rl, ri_new);
  2780. return;
  2781. }
  2782. if (tor_memneq(ri_old->cache_info.identity_digest,
  2783. ri_new->cache_info.identity_digest, DIGEST_LEN)) {
  2784. /* digests don't match; digestmap_set won't replace */
  2785. rimap_remove(rl->identity_map, ri_old->cache_info.identity_digest);
  2786. }
  2787. ri_tmp = rimap_set(rl->identity_map,
  2788. ri_new->cache_info.identity_digest, ri_new);
  2789. tor_assert(!ri_tmp || ri_tmp == ri_old);
  2790. sdmap_set(rl->desc_digest_map,
  2791. ri_new->cache_info.signed_descriptor_digest,
  2792. &(ri_new->cache_info));
  2793. if (!tor_digest_is_zero(ri_new->cache_info.extra_info_digest)) {
  2794. sdmap_set(rl->desc_by_eid_map, ri_new->cache_info.extra_info_digest,
  2795. &ri_new->cache_info);
  2796. }
  2797. same_descriptors = tor_memeq(ri_old->cache_info.signed_descriptor_digest,
  2798. ri_new->cache_info.signed_descriptor_digest,
  2799. DIGEST_LEN);
  2800. if (should_cache_old_descriptors() &&
  2801. ri_old->purpose == ROUTER_PURPOSE_GENERAL &&
  2802. !same_descriptors) {
  2803. /* ri_old is going to become a signed_descriptor_t and go into
  2804. * old_routers */
  2805. signed_descriptor_t *sd = signed_descriptor_from_routerinfo(ri_old);
  2806. smartlist_add(rl->old_routers, sd);
  2807. sd->routerlist_index = smartlist_len(rl->old_routers)-1;
  2808. sdmap_set(rl->desc_digest_map, sd->signed_descriptor_digest, sd);
  2809. if (!tor_digest_is_zero(sd->extra_info_digest))
  2810. sdmap_set(rl->desc_by_eid_map, sd->extra_info_digest, sd);
  2811. } else {
  2812. /* We're dropping ri_old. */
  2813. if (!same_descriptors) {
  2814. /* digests don't match; The sdmap_set above didn't replace */
  2815. sdmap_remove(rl->desc_digest_map,
  2816. ri_old->cache_info.signed_descriptor_digest);
  2817. if (tor_memneq(ri_old->cache_info.extra_info_digest,
  2818. ri_new->cache_info.extra_info_digest, DIGEST_LEN)) {
  2819. ei_tmp = eimap_remove(rl->extra_info_map,
  2820. ri_old->cache_info.extra_info_digest);
  2821. if (ei_tmp) {
  2822. rl->extrainfo_store.bytes_dropped +=
  2823. ei_tmp->cache_info.signed_descriptor_len;
  2824. extrainfo_free(ei_tmp);
  2825. }
  2826. }
  2827. if (!tor_digest_is_zero(ri_old->cache_info.extra_info_digest)) {
  2828. sdmap_remove(rl->desc_by_eid_map,
  2829. ri_old->cache_info.extra_info_digest);
  2830. }
  2831. }
  2832. rl->desc_store.bytes_dropped += ri_old->cache_info.signed_descriptor_len;
  2833. routerinfo_free(ri_old);
  2834. }
  2835. #ifdef DEBUG_ROUTERLIST
  2836. routerlist_assert_ok(rl);
  2837. #endif
  2838. }
  2839. /** Extract the descriptor <b>sd</b> from old_routerlist, and re-parse
  2840. * it as a fresh routerinfo_t. */
  2841. static routerinfo_t *
  2842. routerlist_reparse_old(routerlist_t *rl, signed_descriptor_t *sd)
  2843. {
  2844. routerinfo_t *ri;
  2845. const char *body;
  2846. body = signed_descriptor_get_annotations(sd);
  2847. ri = router_parse_entry_from_string(body,
  2848. body+sd->signed_descriptor_len+sd->annotations_len,
  2849. 0, 1, NULL);
  2850. if (!ri)
  2851. return NULL;
  2852. memcpy(&ri->cache_info, sd, sizeof(signed_descriptor_t));
  2853. sd->signed_descriptor_body = NULL; /* Steal reference. */
  2854. ri->cache_info.routerlist_index = -1;
  2855. routerlist_remove_old(rl, sd, -1);
  2856. return ri;
  2857. }
  2858. /** Free all memory held by the routerlist module. */
  2859. void
  2860. routerlist_free_all(void)
  2861. {
  2862. routerlist_free(routerlist);
  2863. routerlist = NULL;
  2864. if (warned_nicknames) {
  2865. SMARTLIST_FOREACH(warned_nicknames, char *, cp, tor_free(cp));
  2866. smartlist_free(warned_nicknames);
  2867. warned_nicknames = NULL;
  2868. }
  2869. if (trusted_dir_servers) {
  2870. SMARTLIST_FOREACH(trusted_dir_servers, trusted_dir_server_t *, ds,
  2871. trusted_dir_server_free(ds));
  2872. smartlist_free(trusted_dir_servers);
  2873. trusted_dir_servers = NULL;
  2874. }
  2875. if (trusted_dir_certs) {
  2876. DIGESTMAP_FOREACH(trusted_dir_certs, key, cert_list_t *, cl) {
  2877. SMARTLIST_FOREACH(cl->certs, authority_cert_t *, cert,
  2878. authority_cert_free(cert));
  2879. smartlist_free(cl->certs);
  2880. tor_free(cl);
  2881. } DIGESTMAP_FOREACH_END;
  2882. digestmap_free(trusted_dir_certs, NULL);
  2883. trusted_dir_certs = NULL;
  2884. }
  2885. }
  2886. /** Forget that we have issued any router-related warnings, so that we'll
  2887. * warn again if we see the same errors. */
  2888. void
  2889. routerlist_reset_warnings(void)
  2890. {
  2891. if (!warned_nicknames)
  2892. warned_nicknames = smartlist_new();
  2893. SMARTLIST_FOREACH(warned_nicknames, char *, cp, tor_free(cp));
  2894. smartlist_clear(warned_nicknames); /* now the list is empty. */
  2895. networkstatus_reset_warnings();
  2896. }
  2897. /** Mark the router with ID <b>digest</b> as running or non-running
  2898. * in our routerlist. */
  2899. void
  2900. router_set_status(const char *digest, int up)
  2901. {
  2902. node_t *node;
  2903. tor_assert(digest);
  2904. SMARTLIST_FOREACH(trusted_dir_servers, trusted_dir_server_t *, d,
  2905. if (tor_memeq(d->digest, digest, DIGEST_LEN))
  2906. d->is_running = up);
  2907. node = node_get_mutable_by_id(digest);
  2908. if (node) {
  2909. #if 0
  2910. log_debug(LD_DIR,"Marking router %s as %s.",
  2911. node_describe(node), up ? "up" : "down");
  2912. #endif
  2913. if (!up && node_is_me(node) && !net_is_disabled())
  2914. log_warn(LD_NET, "We just marked ourself as down. Are your external "
  2915. "addresses reachable?");
  2916. node->is_running = up;
  2917. }
  2918. router_dir_info_changed();
  2919. }
  2920. /** Add <b>router</b> to the routerlist, if we don't already have it. Replace
  2921. * older entries (if any) with the same key. Note: Callers should not hold
  2922. * their pointers to <b>router</b> if this function fails; <b>router</b>
  2923. * will either be inserted into the routerlist or freed. Similarly, even
  2924. * if this call succeeds, they should not hold their pointers to
  2925. * <b>router</b> after subsequent calls with other routerinfo's -- they
  2926. * might cause the original routerinfo to get freed.
  2927. *
  2928. * Returns the status for the operation. Might set *<b>msg</b> if it wants
  2929. * the poster of the router to know something.
  2930. *
  2931. * If <b>from_cache</b>, this descriptor came from our disk cache. If
  2932. * <b>from_fetch</b>, we received it in response to a request we made.
  2933. * (If both are false, that means it was uploaded to us as an auth dir
  2934. * server or via the controller.)
  2935. *
  2936. * This function should be called *after*
  2937. * routers_update_status_from_consensus_networkstatus; subsequently, you
  2938. * should call router_rebuild_store and routerlist_descriptors_added.
  2939. */
  2940. was_router_added_t
  2941. router_add_to_routerlist(routerinfo_t *router, const char **msg,
  2942. int from_cache, int from_fetch)
  2943. {
  2944. const char *id_digest;
  2945. const or_options_t *options = get_options();
  2946. int authdir = authdir_mode_handles_descs(options, router->purpose);
  2947. int authdir_believes_valid = 0;
  2948. routerinfo_t *old_router;
  2949. networkstatus_t *consensus =
  2950. networkstatus_get_latest_consensus_by_flavor(FLAV_NS);
  2951. const smartlist_t *networkstatus_v2_list = networkstatus_get_v2_list();
  2952. int in_consensus = 0;
  2953. tor_assert(msg);
  2954. if (!routerlist)
  2955. router_get_routerlist();
  2956. id_digest = router->cache_info.identity_digest;
  2957. old_router = router_get_mutable_by_digest(id_digest);
  2958. /* Make sure that we haven't already got this exact descriptor. */
  2959. if (sdmap_get(routerlist->desc_digest_map,
  2960. router->cache_info.signed_descriptor_digest)) {
  2961. /* If we have this descriptor already and the new descriptor is a bridge
  2962. * descriptor, replace it. If we had a bridge descriptor before and the
  2963. * new one is not a bridge descriptor, don't replace it. */
  2964. /* Only members of routerlist->identity_map can be bridges; we don't
  2965. * put bridges in old_routers. */
  2966. const int was_bridge = old_router &&
  2967. old_router->purpose == ROUTER_PURPOSE_BRIDGE;
  2968. if (routerinfo_is_a_configured_bridge(router) &&
  2969. router->purpose == ROUTER_PURPOSE_BRIDGE &&
  2970. !was_bridge) {
  2971. log_info(LD_DIR, "Replacing non-bridge descriptor with bridge "
  2972. "descriptor for router %s",
  2973. router_describe(router));
  2974. } else {
  2975. log_info(LD_DIR,
  2976. "Dropping descriptor that we already have for router %s",
  2977. router_describe(router));
  2978. *msg = "Router descriptor was not new.";
  2979. routerinfo_free(router);
  2980. return ROUTER_WAS_NOT_NEW;
  2981. }
  2982. }
  2983. if (authdir) {
  2984. if (authdir_wants_to_reject_router(router, msg,
  2985. !from_cache && !from_fetch,
  2986. &authdir_believes_valid)) {
  2987. tor_assert(*msg);
  2988. routerinfo_free(router);
  2989. return ROUTER_AUTHDIR_REJECTS;
  2990. }
  2991. } else if (from_fetch) {
  2992. /* Only check the descriptor digest against the network statuses when
  2993. * we are receiving in response to a fetch. */
  2994. if (!signed_desc_digest_is_recognized(&router->cache_info) &&
  2995. !routerinfo_is_a_configured_bridge(router)) {
  2996. /* We asked for it, so some networkstatus must have listed it when we
  2997. * did. Save it if we're a cache in case somebody else asks for it. */
  2998. log_info(LD_DIR,
  2999. "Received a no-longer-recognized descriptor for router %s",
  3000. router_describe(router));
  3001. *msg = "Router descriptor is not referenced by any network-status.";
  3002. /* Only journal this desc if we'll be serving it. */
  3003. if (!from_cache && should_cache_old_descriptors())
  3004. signed_desc_append_to_journal(&router->cache_info,
  3005. &routerlist->desc_store);
  3006. routerlist_insert_old(routerlist, router);
  3007. return ROUTER_NOT_IN_CONSENSUS_OR_NETWORKSTATUS;
  3008. }
  3009. }
  3010. /* We no longer need a router with this descriptor digest. */
  3011. SMARTLIST_FOREACH(networkstatus_v2_list, networkstatus_v2_t *, ns,
  3012. {
  3013. routerstatus_t *rs =
  3014. networkstatus_v2_find_mutable_entry(ns, id_digest);
  3015. if (rs && tor_memeq(rs->descriptor_digest,
  3016. router->cache_info.signed_descriptor_digest,
  3017. DIGEST_LEN))
  3018. rs->need_to_mirror = 0;
  3019. });
  3020. if (consensus) {
  3021. routerstatus_t *rs = networkstatus_vote_find_mutable_entry(
  3022. consensus, id_digest);
  3023. if (rs && tor_memeq(rs->descriptor_digest,
  3024. router->cache_info.signed_descriptor_digest,
  3025. DIGEST_LEN)) {
  3026. in_consensus = 1;
  3027. rs->need_to_mirror = 0;
  3028. }
  3029. }
  3030. if (router->purpose == ROUTER_PURPOSE_GENERAL &&
  3031. consensus && !in_consensus && !authdir) {
  3032. /* If it's a general router not listed in the consensus, then don't
  3033. * consider replacing the latest router with it. */
  3034. if (!from_cache && should_cache_old_descriptors())
  3035. signed_desc_append_to_journal(&router->cache_info,
  3036. &routerlist->desc_store);
  3037. routerlist_insert_old(routerlist, router);
  3038. *msg = "Skipping router descriptor: not in consensus.";
  3039. return ROUTER_NOT_IN_CONSENSUS;
  3040. }
  3041. /* If we're reading a bridge descriptor from our cache, and we don't
  3042. * recognize it as one of our currently configured bridges, drop the
  3043. * descriptor. Otherwise we could end up using it as one of our entry
  3044. * guards even if it isn't in our Bridge config lines. */
  3045. if (router->purpose == ROUTER_PURPOSE_BRIDGE && from_cache &&
  3046. !authdir_mode_bridge(options) &&
  3047. !routerinfo_is_a_configured_bridge(router)) {
  3048. log_info(LD_DIR, "Dropping bridge descriptor for %s because we have "
  3049. "no bridge configured at that address.",
  3050. safe_str_client(router_describe(router)));
  3051. *msg = "Router descriptor was not a configured bridge.";
  3052. routerinfo_free(router);
  3053. return ROUTER_WAS_NOT_WANTED;
  3054. }
  3055. /* If we have a router with the same identity key, choose the newer one. */
  3056. if (old_router) {
  3057. if (!in_consensus && (router->cache_info.published_on <=
  3058. old_router->cache_info.published_on)) {
  3059. /* Same key, but old. This one is not listed in the consensus. */
  3060. log_debug(LD_DIR, "Not-new descriptor for router %s",
  3061. router_describe(router));
  3062. /* Only journal this desc if we'll be serving it. */
  3063. if (!from_cache && should_cache_old_descriptors())
  3064. signed_desc_append_to_journal(&router->cache_info,
  3065. &routerlist->desc_store);
  3066. routerlist_insert_old(routerlist, router);
  3067. *msg = "Router descriptor was not new.";
  3068. return ROUTER_WAS_NOT_NEW;
  3069. } else {
  3070. /* Same key, and either new, or listed in the consensus. */
  3071. log_debug(LD_DIR, "Replacing entry for router %s",
  3072. router_describe(router));
  3073. if (routers_have_same_or_addr(router, old_router)) {
  3074. /* these carry over when the address and orport are unchanged. */
  3075. router->last_reachable = old_router->last_reachable;
  3076. router->testing_since = old_router->testing_since;
  3077. }
  3078. routerlist_replace(routerlist, old_router, router);
  3079. if (!from_cache) {
  3080. signed_desc_append_to_journal(&router->cache_info,
  3081. &routerlist->desc_store);
  3082. }
  3083. directory_set_dirty();
  3084. *msg = authdir_believes_valid ? "Valid server updated" :
  3085. ("Invalid server updated. (This dirserver is marking your "
  3086. "server as unapproved.)");
  3087. return ROUTER_ADDED_SUCCESSFULLY;
  3088. }
  3089. }
  3090. if (!in_consensus && from_cache &&
  3091. router->cache_info.published_on < time(NULL) - OLD_ROUTER_DESC_MAX_AGE) {
  3092. *msg = "Router descriptor was really old.";
  3093. routerinfo_free(router);
  3094. return ROUTER_WAS_NOT_NEW;
  3095. }
  3096. /* We haven't seen a router with this identity before. Add it to the end of
  3097. * the list. */
  3098. routerlist_insert(routerlist, router);
  3099. if (!from_cache) {
  3100. signed_desc_append_to_journal(&router->cache_info,
  3101. &routerlist->desc_store);
  3102. }
  3103. directory_set_dirty();
  3104. return ROUTER_ADDED_SUCCESSFULLY;
  3105. }
  3106. /** Insert <b>ei</b> into the routerlist, or free it. Other arguments are
  3107. * as for router_add_to_routerlist(). Return ROUTER_ADDED_SUCCESSFULLY iff
  3108. * we actually inserted it, ROUTER_BAD_EI otherwise.
  3109. */
  3110. was_router_added_t
  3111. router_add_extrainfo_to_routerlist(extrainfo_t *ei, const char **msg,
  3112. int from_cache, int from_fetch)
  3113. {
  3114. int inserted;
  3115. (void)from_fetch;
  3116. if (msg) *msg = NULL;
  3117. /*XXXX023 Do something with msg */
  3118. inserted = extrainfo_insert(router_get_routerlist(), ei);
  3119. if (inserted && !from_cache)
  3120. signed_desc_append_to_journal(&ei->cache_info,
  3121. &routerlist->extrainfo_store);
  3122. if (inserted)
  3123. return ROUTER_ADDED_SUCCESSFULLY;
  3124. else
  3125. return ROUTER_BAD_EI;
  3126. }
  3127. /** Sorting helper: return &lt;0, 0, or &gt;0 depending on whether the
  3128. * signed_descriptor_t* in *<b>a</b> has an identity digest preceding, equal
  3129. * to, or later than that of *<b>b</b>. */
  3130. static int
  3131. _compare_old_routers_by_identity(const void **_a, const void **_b)
  3132. {
  3133. int i;
  3134. const signed_descriptor_t *r1 = *_a, *r2 = *_b;
  3135. if ((i = fast_memcmp(r1->identity_digest, r2->identity_digest, DIGEST_LEN)))
  3136. return i;
  3137. return (int)(r1->published_on - r2->published_on);
  3138. }
  3139. /** Internal type used to represent how long an old descriptor was valid,
  3140. * where it appeared in the list of old descriptors, and whether it's extra
  3141. * old. Used only by routerlist_remove_old_cached_routers_with_id(). */
  3142. struct duration_idx_t {
  3143. int duration;
  3144. int idx;
  3145. int old;
  3146. };
  3147. /** Sorting helper: compare two duration_idx_t by their duration. */
  3148. static int
  3149. _compare_duration_idx(const void *_d1, const void *_d2)
  3150. {
  3151. const struct duration_idx_t *d1 = _d1;
  3152. const struct duration_idx_t *d2 = _d2;
  3153. return d1->duration - d2->duration;
  3154. }
  3155. /** The range <b>lo</b> through <b>hi</b> inclusive of routerlist->old_routers
  3156. * must contain routerinfo_t with the same identity and with publication time
  3157. * in ascending order. Remove members from this range until there are no more
  3158. * than max_descriptors_per_router() remaining. Start by removing the oldest
  3159. * members from before <b>cutoff</b>, then remove members which were current
  3160. * for the lowest amount of time. The order of members of old_routers at
  3161. * indices <b>lo</b> or higher may be changed.
  3162. */
  3163. static void
  3164. routerlist_remove_old_cached_routers_with_id(time_t now,
  3165. time_t cutoff, int lo, int hi,
  3166. digestset_t *retain)
  3167. {
  3168. int i, n = hi-lo+1;
  3169. unsigned n_extra, n_rmv = 0;
  3170. struct duration_idx_t *lifespans;
  3171. uint8_t *rmv, *must_keep;
  3172. smartlist_t *lst = routerlist->old_routers;
  3173. #if 1
  3174. const char *ident;
  3175. tor_assert(hi < smartlist_len(lst));
  3176. tor_assert(lo <= hi);
  3177. ident = ((signed_descriptor_t*)smartlist_get(lst, lo))->identity_digest;
  3178. for (i = lo+1; i <= hi; ++i) {
  3179. signed_descriptor_t *r = smartlist_get(lst, i);
  3180. tor_assert(tor_memeq(ident, r->identity_digest, DIGEST_LEN));
  3181. }
  3182. #endif
  3183. /* Check whether we need to do anything at all. */
  3184. {
  3185. int mdpr = directory_caches_dir_info(get_options()) ? 2 : 1;
  3186. if (n <= mdpr)
  3187. return;
  3188. n_extra = n - mdpr;
  3189. }
  3190. lifespans = tor_malloc_zero(sizeof(struct duration_idx_t)*n);
  3191. rmv = tor_malloc_zero(sizeof(uint8_t)*n);
  3192. must_keep = tor_malloc_zero(sizeof(uint8_t)*n);
  3193. /* Set lifespans to contain the lifespan and index of each server. */
  3194. /* Set rmv[i-lo]=1 if we're going to remove a server for being too old. */
  3195. for (i = lo; i <= hi; ++i) {
  3196. signed_descriptor_t *r = smartlist_get(lst, i);
  3197. signed_descriptor_t *r_next;
  3198. lifespans[i-lo].idx = i;
  3199. if (r->last_listed_as_valid_until >= now ||
  3200. (retain && digestset_isin(retain, r->signed_descriptor_digest))) {
  3201. must_keep[i-lo] = 1;
  3202. }
  3203. if (i < hi) {
  3204. r_next = smartlist_get(lst, i+1);
  3205. tor_assert(r->published_on <= r_next->published_on);
  3206. lifespans[i-lo].duration = (int)(r_next->published_on - r->published_on);
  3207. } else {
  3208. r_next = NULL;
  3209. lifespans[i-lo].duration = INT_MAX;
  3210. }
  3211. if (!must_keep[i-lo] && r->published_on < cutoff && n_rmv < n_extra) {
  3212. ++n_rmv;
  3213. lifespans[i-lo].old = 1;
  3214. rmv[i-lo] = 1;
  3215. }
  3216. }
  3217. if (n_rmv < n_extra) {
  3218. /**
  3219. * We aren't removing enough servers for being old. Sort lifespans by
  3220. * the duration of liveness, and remove the ones we're not already going to
  3221. * remove based on how long they were alive.
  3222. **/
  3223. qsort(lifespans, n, sizeof(struct duration_idx_t), _compare_duration_idx);
  3224. for (i = 0; i < n && n_rmv < n_extra; ++i) {
  3225. if (!must_keep[lifespans[i].idx-lo] && !lifespans[i].old) {
  3226. rmv[lifespans[i].idx-lo] = 1;
  3227. ++n_rmv;
  3228. }
  3229. }
  3230. }
  3231. i = hi;
  3232. do {
  3233. if (rmv[i-lo])
  3234. routerlist_remove_old(routerlist, smartlist_get(lst, i), i);
  3235. } while (--i >= lo);
  3236. tor_free(must_keep);
  3237. tor_free(rmv);
  3238. tor_free(lifespans);
  3239. }
  3240. /** Deactivate any routers from the routerlist that are more than
  3241. * ROUTER_MAX_AGE seconds old and not recommended by any networkstatuses;
  3242. * remove old routers from the list of cached routers if we have too many.
  3243. */
  3244. void
  3245. routerlist_remove_old_routers(void)
  3246. {
  3247. int i, hi=-1;
  3248. const char *cur_id = NULL;
  3249. time_t now = time(NULL);
  3250. time_t cutoff;
  3251. routerinfo_t *router;
  3252. signed_descriptor_t *sd;
  3253. digestset_t *retain;
  3254. int caches = directory_caches_dir_info(get_options());
  3255. const networkstatus_t *consensus = networkstatus_get_latest_consensus();
  3256. const smartlist_t *networkstatus_v2_list = networkstatus_get_v2_list();
  3257. int have_enough_v2;
  3258. const or_options_t *options = get_options();
  3259. trusted_dirs_remove_old_certs();
  3260. if (!routerlist || !consensus)
  3261. return;
  3262. // routerlist_assert_ok(routerlist);
  3263. /* We need to guess how many router descriptors we will wind up wanting to
  3264. retain, so that we can be sure to allocate a large enough Bloom filter
  3265. to hold the digest set. Overestimating is fine; underestimating is bad.
  3266. */
  3267. {
  3268. /* We'll probably retain everything in the consensus. */
  3269. int n_max_retain = smartlist_len(consensus->routerstatus_list);
  3270. if (caches && networkstatus_v2_list) {
  3271. /* If we care about v2 statuses, we'll retain at most as many as are
  3272. listed any of the v2 statues. This will be at least the length of
  3273. the largest v2 networkstatus, and in the worst case, this set will be
  3274. equal to the sum of the lengths of all v2 consensuses. Take the
  3275. worst case.
  3276. */
  3277. SMARTLIST_FOREACH(networkstatus_v2_list, networkstatus_v2_t *, ns,
  3278. n_max_retain += smartlist_len(ns->entries));
  3279. }
  3280. retain = digestset_new(n_max_retain);
  3281. }
  3282. cutoff = now - OLD_ROUTER_DESC_MAX_AGE;
  3283. /* Build a list of all the descriptors that _anybody_ lists. */
  3284. if (caches && networkstatus_v2_list) {
  3285. SMARTLIST_FOREACH(networkstatus_v2_list, networkstatus_v2_t *, ns,
  3286. {
  3287. /* XXXX The inner loop here gets pretty expensive, and actually shows up
  3288. * on some profiles. It may be the reason digestmap_set shows up in
  3289. * profiles too. If instead we kept a per-descriptor digest count of
  3290. * how many networkstatuses recommended each descriptor, and changed
  3291. * that only when the networkstatuses changed, that would be a speed
  3292. * improvement, possibly 1-4% if it also removes digestmap_set from the
  3293. * profile. Not worth it for 0.1.2.x, though. The new directory
  3294. * system will obsolete this whole thing in 0.2.0.x. */
  3295. SMARTLIST_FOREACH(ns->entries, routerstatus_t *, rs,
  3296. if (rs->published_on >= cutoff)
  3297. digestset_add(retain, rs->descriptor_digest));
  3298. });
  3299. }
  3300. /* Retain anything listed in the consensus. */
  3301. if (consensus) {
  3302. SMARTLIST_FOREACH(consensus->routerstatus_list, routerstatus_t *, rs,
  3303. if (rs->published_on >= cutoff)
  3304. digestset_add(retain, rs->descriptor_digest));
  3305. }
  3306. /* If we have a consensus, and nearly as many v2 networkstatuses as we want,
  3307. * we should consider pruning current routers that are too old and that
  3308. * nobody recommends. (If we don't have a consensus or enough v2
  3309. * networkstatuses, then we should get more before we decide to kill
  3310. * routers.) */
  3311. /* we set this to true iff we don't care about v2 info, or we have enough. */
  3312. have_enough_v2 = !caches ||
  3313. !(authdir_mode_any_main(options) || options->FetchV2Networkstatus) ||
  3314. (networkstatus_v2_list &&
  3315. smartlist_len(networkstatus_v2_list) > get_n_v2_authorities() / 2);
  3316. if (have_enough_v2 && consensus) {
  3317. cutoff = now - ROUTER_MAX_AGE;
  3318. /* Remove too-old unrecommended members of routerlist->routers. */
  3319. for (i = 0; i < smartlist_len(routerlist->routers); ++i) {
  3320. router = smartlist_get(routerlist->routers, i);
  3321. if (router->cache_info.published_on <= cutoff &&
  3322. router->cache_info.last_listed_as_valid_until < now &&
  3323. !digestset_isin(retain,
  3324. router->cache_info.signed_descriptor_digest)) {
  3325. /* Too old: remove it. (If we're a cache, just move it into
  3326. * old_routers.) */
  3327. log_info(LD_DIR,
  3328. "Forgetting obsolete (too old) routerinfo for router %s",
  3329. router_describe(router));
  3330. routerlist_remove(routerlist, router, 1, now);
  3331. i--;
  3332. }
  3333. }
  3334. }
  3335. //routerlist_assert_ok(routerlist);
  3336. /* Remove far-too-old members of routerlist->old_routers. */
  3337. cutoff = now - OLD_ROUTER_DESC_MAX_AGE;
  3338. for (i = 0; i < smartlist_len(routerlist->old_routers); ++i) {
  3339. sd = smartlist_get(routerlist->old_routers, i);
  3340. if (sd->published_on <= cutoff &&
  3341. sd->last_listed_as_valid_until < now &&
  3342. !digestset_isin(retain, sd->signed_descriptor_digest)) {
  3343. /* Too old. Remove it. */
  3344. routerlist_remove_old(routerlist, sd, i--);
  3345. }
  3346. }
  3347. //routerlist_assert_ok(routerlist);
  3348. log_info(LD_DIR, "We have %d live routers and %d old router descriptors.",
  3349. smartlist_len(routerlist->routers),
  3350. smartlist_len(routerlist->old_routers));
  3351. /* Now we might have to look at routerlist->old_routers for extraneous
  3352. * members. (We'd keep all the members if we could, but we need to save
  3353. * space.) First, check whether we have too many router descriptors, total.
  3354. * We're okay with having too many for some given router, so long as the
  3355. * total number doesn't approach max_descriptors_per_router()*len(router).
  3356. */
  3357. if (smartlist_len(routerlist->old_routers) <
  3358. smartlist_len(routerlist->routers))
  3359. goto done;
  3360. /* Sort by identity, then fix indices. */
  3361. smartlist_sort(routerlist->old_routers, _compare_old_routers_by_identity);
  3362. /* Fix indices. */
  3363. for (i = 0; i < smartlist_len(routerlist->old_routers); ++i) {
  3364. signed_descriptor_t *r = smartlist_get(routerlist->old_routers, i);
  3365. r->routerlist_index = i;
  3366. }
  3367. /* Iterate through the list from back to front, so when we remove descriptors
  3368. * we don't mess up groups we haven't gotten to. */
  3369. for (i = smartlist_len(routerlist->old_routers)-1; i >= 0; --i) {
  3370. signed_descriptor_t *r = smartlist_get(routerlist->old_routers, i);
  3371. if (!cur_id) {
  3372. cur_id = r->identity_digest;
  3373. hi = i;
  3374. }
  3375. if (tor_memneq(cur_id, r->identity_digest, DIGEST_LEN)) {
  3376. routerlist_remove_old_cached_routers_with_id(now,
  3377. cutoff, i+1, hi, retain);
  3378. cur_id = r->identity_digest;
  3379. hi = i;
  3380. }
  3381. }
  3382. if (hi>=0)
  3383. routerlist_remove_old_cached_routers_with_id(now, cutoff, 0, hi, retain);
  3384. //routerlist_assert_ok(routerlist);
  3385. done:
  3386. digestset_free(retain);
  3387. router_rebuild_store(RRS_DONT_REMOVE_OLD, &routerlist->desc_store);
  3388. router_rebuild_store(RRS_DONT_REMOVE_OLD,&routerlist->extrainfo_store);
  3389. }
  3390. /** We just added a new set of descriptors. Take whatever extra steps
  3391. * we need. */
  3392. void
  3393. routerlist_descriptors_added(smartlist_t *sl, int from_cache)
  3394. {
  3395. tor_assert(sl);
  3396. control_event_descriptors_changed(sl);
  3397. SMARTLIST_FOREACH_BEGIN(sl, routerinfo_t *, ri) {
  3398. if (ri->purpose == ROUTER_PURPOSE_BRIDGE)
  3399. learned_bridge_descriptor(ri, from_cache);
  3400. if (ri->needs_retest_if_added) {
  3401. ri->needs_retest_if_added = 0;
  3402. dirserv_single_reachability_test(approx_time(), ri);
  3403. }
  3404. } SMARTLIST_FOREACH_END(ri);
  3405. }
  3406. /**
  3407. * Code to parse a single router descriptor and insert it into the
  3408. * routerlist. Return -1 if the descriptor was ill-formed; 0 if the
  3409. * descriptor was well-formed but could not be added; and 1 if the
  3410. * descriptor was added.
  3411. *
  3412. * If we don't add it and <b>msg</b> is not NULL, then assign to
  3413. * *<b>msg</b> a static string describing the reason for refusing the
  3414. * descriptor.
  3415. *
  3416. * This is used only by the controller.
  3417. */
  3418. int
  3419. router_load_single_router(const char *s, uint8_t purpose, int cache,
  3420. const char **msg)
  3421. {
  3422. routerinfo_t *ri;
  3423. was_router_added_t r;
  3424. smartlist_t *lst;
  3425. char annotation_buf[ROUTER_ANNOTATION_BUF_LEN];
  3426. tor_assert(msg);
  3427. *msg = NULL;
  3428. tor_snprintf(annotation_buf, sizeof(annotation_buf),
  3429. "@source controller\n"
  3430. "@purpose %s\n", router_purpose_to_string(purpose));
  3431. if (!(ri = router_parse_entry_from_string(s, NULL, 1, 0, annotation_buf))) {
  3432. log_warn(LD_DIR, "Error parsing router descriptor; dropping.");
  3433. *msg = "Couldn't parse router descriptor.";
  3434. return -1;
  3435. }
  3436. tor_assert(ri->purpose == purpose);
  3437. if (router_is_me(ri)) {
  3438. log_warn(LD_DIR, "Router's identity key matches mine; dropping.");
  3439. *msg = "Router's identity key matches mine.";
  3440. routerinfo_free(ri);
  3441. return 0;
  3442. }
  3443. if (!cache) /* obey the preference of the controller */
  3444. ri->cache_info.do_not_cache = 1;
  3445. lst = smartlist_new();
  3446. smartlist_add(lst, ri);
  3447. routers_update_status_from_consensus_networkstatus(lst, 0);
  3448. r = router_add_to_routerlist(ri, msg, 0, 0);
  3449. if (!WRA_WAS_ADDED(r)) {
  3450. /* we've already assigned to *msg now, and ri is already freed */
  3451. tor_assert(*msg);
  3452. if (r == ROUTER_AUTHDIR_REJECTS)
  3453. log_warn(LD_DIR, "Couldn't add router to list: %s Dropping.", *msg);
  3454. smartlist_free(lst);
  3455. return 0;
  3456. } else {
  3457. routerlist_descriptors_added(lst, 0);
  3458. smartlist_free(lst);
  3459. log_debug(LD_DIR, "Added router to list");
  3460. return 1;
  3461. }
  3462. }
  3463. /** Given a string <b>s</b> containing some routerdescs, parse it and put the
  3464. * routers into our directory. If saved_location is SAVED_NOWHERE, the routers
  3465. * are in response to a query to the network: cache them by adding them to
  3466. * the journal.
  3467. *
  3468. * Return the number of routers actually added.
  3469. *
  3470. * If <b>requested_fingerprints</b> is provided, it must contain a list of
  3471. * uppercased fingerprints. Do not update any router whose
  3472. * fingerprint is not on the list; after updating a router, remove its
  3473. * fingerprint from the list.
  3474. *
  3475. * If <b>descriptor_digests</b> is non-zero, then the requested_fingerprints
  3476. * are descriptor digests. Otherwise they are identity digests.
  3477. */
  3478. int
  3479. router_load_routers_from_string(const char *s, const char *eos,
  3480. saved_location_t saved_location,
  3481. smartlist_t *requested_fingerprints,
  3482. int descriptor_digests,
  3483. const char *prepend_annotations)
  3484. {
  3485. smartlist_t *routers = smartlist_new(), *changed = smartlist_new();
  3486. char fp[HEX_DIGEST_LEN+1];
  3487. const char *msg;
  3488. int from_cache = (saved_location != SAVED_NOWHERE);
  3489. int allow_annotations = (saved_location != SAVED_NOWHERE);
  3490. int any_changed = 0;
  3491. router_parse_list_from_string(&s, eos, routers, saved_location, 0,
  3492. allow_annotations, prepend_annotations);
  3493. routers_update_status_from_consensus_networkstatus(routers, !from_cache);
  3494. log_info(LD_DIR, "%d elements to add", smartlist_len(routers));
  3495. SMARTLIST_FOREACH_BEGIN(routers, routerinfo_t *, ri) {
  3496. was_router_added_t r;
  3497. char d[DIGEST_LEN];
  3498. if (requested_fingerprints) {
  3499. base16_encode(fp, sizeof(fp), descriptor_digests ?
  3500. ri->cache_info.signed_descriptor_digest :
  3501. ri->cache_info.identity_digest,
  3502. DIGEST_LEN);
  3503. if (smartlist_string_isin(requested_fingerprints, fp)) {
  3504. smartlist_string_remove(requested_fingerprints, fp);
  3505. } else {
  3506. char *requested =
  3507. smartlist_join_strings(requested_fingerprints," ",0,NULL);
  3508. log_warn(LD_DIR,
  3509. "We received a router descriptor with a fingerprint (%s) "
  3510. "that we never requested. (We asked for: %s.) Dropping.",
  3511. fp, requested);
  3512. tor_free(requested);
  3513. routerinfo_free(ri);
  3514. continue;
  3515. }
  3516. }
  3517. memcpy(d, ri->cache_info.signed_descriptor_digest, DIGEST_LEN);
  3518. r = router_add_to_routerlist(ri, &msg, from_cache, !from_cache);
  3519. if (WRA_WAS_ADDED(r)) {
  3520. any_changed++;
  3521. smartlist_add(changed, ri);
  3522. routerlist_descriptors_added(changed, from_cache);
  3523. smartlist_clear(changed);
  3524. } else if (WRA_WAS_REJECTED(r)) {
  3525. download_status_t *dl_status;
  3526. dl_status = router_get_dl_status_by_descriptor_digest(d);
  3527. if (dl_status) {
  3528. log_info(LD_GENERAL, "Marking router %s as never downloadable",
  3529. hex_str(d, DIGEST_LEN));
  3530. download_status_mark_impossible(dl_status);
  3531. }
  3532. }
  3533. } SMARTLIST_FOREACH_END(ri);
  3534. routerlist_assert_ok(routerlist);
  3535. if (any_changed)
  3536. router_rebuild_store(0, &routerlist->desc_store);
  3537. smartlist_free(routers);
  3538. smartlist_free(changed);
  3539. return any_changed;
  3540. }
  3541. /** Parse one or more extrainfos from <b>s</b> (ending immediately before
  3542. * <b>eos</b> if <b>eos</b> is present). Other arguments are as for
  3543. * router_load_routers_from_string(). */
  3544. void
  3545. router_load_extrainfo_from_string(const char *s, const char *eos,
  3546. saved_location_t saved_location,
  3547. smartlist_t *requested_fingerprints,
  3548. int descriptor_digests)
  3549. {
  3550. smartlist_t *extrainfo_list = smartlist_new();
  3551. const char *msg;
  3552. int from_cache = (saved_location != SAVED_NOWHERE);
  3553. router_parse_list_from_string(&s, eos, extrainfo_list, saved_location, 1, 0,
  3554. NULL);
  3555. log_info(LD_DIR, "%d elements to add", smartlist_len(extrainfo_list));
  3556. SMARTLIST_FOREACH(extrainfo_list, extrainfo_t *, ei, {
  3557. was_router_added_t added =
  3558. router_add_extrainfo_to_routerlist(ei, &msg, from_cache, !from_cache);
  3559. if (WRA_WAS_ADDED(added) && requested_fingerprints) {
  3560. char fp[HEX_DIGEST_LEN+1];
  3561. base16_encode(fp, sizeof(fp), descriptor_digests ?
  3562. ei->cache_info.signed_descriptor_digest :
  3563. ei->cache_info.identity_digest,
  3564. DIGEST_LEN);
  3565. smartlist_string_remove(requested_fingerprints, fp);
  3566. /* We silently let people stuff us with extrainfos we didn't ask for,
  3567. * so long as we would have wanted them anyway. Since we always fetch
  3568. * all the extrainfos we want, and we never actually act on them
  3569. * inside Tor, this should be harmless. */
  3570. }
  3571. });
  3572. routerlist_assert_ok(routerlist);
  3573. router_rebuild_store(0, &router_get_routerlist()->extrainfo_store);
  3574. smartlist_free(extrainfo_list);
  3575. }
  3576. /** Return true iff any networkstatus includes a descriptor whose digest
  3577. * is that of <b>desc</b>. */
  3578. static int
  3579. signed_desc_digest_is_recognized(signed_descriptor_t *desc)
  3580. {
  3581. const routerstatus_t *rs;
  3582. networkstatus_t *consensus = networkstatus_get_latest_consensus();
  3583. int caches = directory_caches_dir_info(get_options());
  3584. const smartlist_t *networkstatus_v2_list = networkstatus_get_v2_list();
  3585. if (consensus) {
  3586. rs = networkstatus_vote_find_entry(consensus, desc->identity_digest);
  3587. if (rs && tor_memeq(rs->descriptor_digest,
  3588. desc->signed_descriptor_digest, DIGEST_LEN))
  3589. return 1;
  3590. }
  3591. if (caches && networkstatus_v2_list) {
  3592. SMARTLIST_FOREACH(networkstatus_v2_list, networkstatus_v2_t *, ns,
  3593. {
  3594. if (!(rs = networkstatus_v2_find_entry(ns, desc->identity_digest)))
  3595. continue;
  3596. if (tor_memeq(rs->descriptor_digest,
  3597. desc->signed_descriptor_digest, DIGEST_LEN))
  3598. return 1;
  3599. });
  3600. }
  3601. return 0;
  3602. }
  3603. /** Update downloads for router descriptors and/or microdescriptors as
  3604. * appropriate. */
  3605. void
  3606. update_all_descriptor_downloads(time_t now)
  3607. {
  3608. if (get_options()->DisableNetwork)
  3609. return;
  3610. update_router_descriptor_downloads(now);
  3611. update_microdesc_downloads(now);
  3612. launch_dummy_descriptor_download_as_needed(now, get_options());
  3613. }
  3614. /** Clear all our timeouts for fetching v2 and v3 directory stuff, and then
  3615. * give it all a try again. */
  3616. void
  3617. routerlist_retry_directory_downloads(time_t now)
  3618. {
  3619. router_reset_status_download_failures();
  3620. router_reset_descriptor_download_failures();
  3621. if (get_options()->DisableNetwork)
  3622. return;
  3623. update_networkstatus_downloads(now);
  3624. update_all_descriptor_downloads(now);
  3625. }
  3626. /** Return 1 if all running sufficiently-stable routers we can use will reject
  3627. * addr:port, return 0 if any might accept it. */
  3628. int
  3629. router_exit_policy_all_nodes_reject(const tor_addr_t *addr, uint16_t port,
  3630. int need_uptime)
  3631. { /* XXXX MOVE */
  3632. addr_policy_result_t r;
  3633. SMARTLIST_FOREACH_BEGIN(nodelist_get_list(), const node_t *, node) {
  3634. if (node->is_running &&
  3635. !node_is_unreliable(node, need_uptime, 0, 0)) {
  3636. r = compare_tor_addr_to_node_policy(addr, port, node);
  3637. if (r != ADDR_POLICY_REJECTED && r != ADDR_POLICY_PROBABLY_REJECTED)
  3638. return 0; /* this one could be ok. good enough. */
  3639. }
  3640. } SMARTLIST_FOREACH_END(node);
  3641. return 1; /* all will reject. */
  3642. }
  3643. /** Return true iff <b>router</b> does not permit exit streams.
  3644. */
  3645. int
  3646. router_exit_policy_rejects_all(const routerinfo_t *router)
  3647. {
  3648. return router->policy_is_reject_star;
  3649. }
  3650. /** Add to the list of authoritative directory servers one at
  3651. * <b>address</b>:<b>port</b>, with identity key <b>digest</b>. If
  3652. * <b>address</b> is NULL, add ourself. Return the new trusted directory
  3653. * server entry on success or NULL if we couldn't add it. */
  3654. trusted_dir_server_t *
  3655. add_trusted_dir_server(const char *nickname, const char *address,
  3656. uint16_t dir_port, uint16_t or_port,
  3657. const char *digest, const char *v3_auth_digest,
  3658. dirinfo_type_t type)
  3659. {
  3660. trusted_dir_server_t *ent;
  3661. uint32_t a;
  3662. char *hostname = NULL;
  3663. if (!trusted_dir_servers)
  3664. trusted_dir_servers = smartlist_new();
  3665. if (!address) { /* The address is us; we should guess. */
  3666. if (resolve_my_address(LOG_WARN, get_options(), &a, &hostname) < 0) {
  3667. log_warn(LD_CONFIG,
  3668. "Couldn't find a suitable address when adding ourself as a "
  3669. "trusted directory server.");
  3670. return NULL;
  3671. }
  3672. } else {
  3673. if (tor_lookup_hostname(address, &a)) {
  3674. log_warn(LD_CONFIG,
  3675. "Unable to lookup address for directory server at '%s'",
  3676. address);
  3677. return NULL;
  3678. }
  3679. hostname = tor_strdup(address);
  3680. }
  3681. ent = tor_malloc_zero(sizeof(trusted_dir_server_t));
  3682. ent->nickname = nickname ? tor_strdup(nickname) : NULL;
  3683. ent->address = hostname;
  3684. ent->addr = a;
  3685. ent->dir_port = dir_port;
  3686. ent->or_port = or_port;
  3687. ent->is_running = 1;
  3688. ent->type = type;
  3689. memcpy(ent->digest, digest, DIGEST_LEN);
  3690. if (v3_auth_digest && (type & V3_DIRINFO))
  3691. memcpy(ent->v3_identity_digest, v3_auth_digest, DIGEST_LEN);
  3692. if (nickname)
  3693. tor_asprintf(&ent->description, "directory server \"%s\" at %s:%d",
  3694. nickname, hostname, (int)dir_port);
  3695. else
  3696. tor_asprintf(&ent->description, "directory server at %s:%d",
  3697. hostname, (int)dir_port);
  3698. ent->fake_status.addr = ent->addr;
  3699. memcpy(ent->fake_status.identity_digest, digest, DIGEST_LEN);
  3700. if (nickname)
  3701. strlcpy(ent->fake_status.nickname, nickname,
  3702. sizeof(ent->fake_status.nickname));
  3703. else
  3704. ent->fake_status.nickname[0] = '\0';
  3705. ent->fake_status.dir_port = ent->dir_port;
  3706. ent->fake_status.or_port = ent->or_port;
  3707. if (ent->or_port)
  3708. ent->fake_status.version_supports_begindir = 1;
  3709. ent->fake_status.version_supports_conditional_consensus = 1;
  3710. smartlist_add(trusted_dir_servers, ent);
  3711. router_dir_info_changed();
  3712. return ent;
  3713. }
  3714. /** Free storage held in <b>cert</b>. */
  3715. void
  3716. authority_cert_free(authority_cert_t *cert)
  3717. {
  3718. if (!cert)
  3719. return;
  3720. tor_free(cert->cache_info.signed_descriptor_body);
  3721. crypto_pk_free(cert->signing_key);
  3722. crypto_pk_free(cert->identity_key);
  3723. tor_free(cert);
  3724. }
  3725. /** Free storage held in <b>ds</b>. */
  3726. static void
  3727. trusted_dir_server_free(trusted_dir_server_t *ds)
  3728. {
  3729. if (!ds)
  3730. return;
  3731. tor_free(ds->nickname);
  3732. tor_free(ds->description);
  3733. tor_free(ds->address);
  3734. tor_free(ds);
  3735. }
  3736. /** Remove all members from the list of trusted dir servers. */
  3737. void
  3738. clear_trusted_dir_servers(void)
  3739. {
  3740. if (trusted_dir_servers) {
  3741. SMARTLIST_FOREACH(trusted_dir_servers, trusted_dir_server_t *, ent,
  3742. trusted_dir_server_free(ent));
  3743. smartlist_clear(trusted_dir_servers);
  3744. } else {
  3745. trusted_dir_servers = smartlist_new();
  3746. }
  3747. router_dir_info_changed();
  3748. }
  3749. /** Return 1 if any trusted dir server supports v1 directories,
  3750. * else return 0. */
  3751. int
  3752. any_trusted_dir_is_v1_authority(void)
  3753. {
  3754. if (trusted_dir_servers)
  3755. return get_n_authorities(V1_DIRINFO) > 0;
  3756. return 0;
  3757. }
  3758. /** For every current directory connection whose purpose is <b>purpose</b>,
  3759. * and where the resource being downloaded begins with <b>prefix</b>, split
  3760. * rest of the resource into base16 fingerprints (or base64 fingerprints if
  3761. * purpose==DIR_PURPPOSE_FETCH_MICRODESC), decode them, and set the
  3762. * corresponding elements of <b>result</b> to a nonzero value.
  3763. */
  3764. static void
  3765. list_pending_downloads(digestmap_t *result,
  3766. int purpose, const char *prefix)
  3767. {
  3768. const size_t p_len = strlen(prefix);
  3769. smartlist_t *tmp = smartlist_new();
  3770. smartlist_t *conns = get_connection_array();
  3771. int flags = DSR_HEX;
  3772. if (purpose == DIR_PURPOSE_FETCH_MICRODESC)
  3773. flags = DSR_DIGEST256|DSR_BASE64;
  3774. tor_assert(result);
  3775. SMARTLIST_FOREACH_BEGIN(conns, connection_t *, conn) {
  3776. if (conn->type == CONN_TYPE_DIR &&
  3777. conn->purpose == purpose &&
  3778. !conn->marked_for_close) {
  3779. const char *resource = TO_DIR_CONN(conn)->requested_resource;
  3780. if (!strcmpstart(resource, prefix))
  3781. dir_split_resource_into_fingerprints(resource + p_len,
  3782. tmp, NULL, flags);
  3783. }
  3784. } SMARTLIST_FOREACH_END(conn);
  3785. SMARTLIST_FOREACH(tmp, char *, d,
  3786. {
  3787. digestmap_set(result, d, (void*)1);
  3788. tor_free(d);
  3789. });
  3790. smartlist_free(tmp);
  3791. }
  3792. /** For every router descriptor (or extra-info document if <b>extrainfo</b> is
  3793. * true) we are currently downloading by descriptor digest, set result[d] to
  3794. * (void*)1. */
  3795. static void
  3796. list_pending_descriptor_downloads(digestmap_t *result, int extrainfo)
  3797. {
  3798. int purpose =
  3799. extrainfo ? DIR_PURPOSE_FETCH_EXTRAINFO : DIR_PURPOSE_FETCH_SERVERDESC;
  3800. list_pending_downloads(result, purpose, "d/");
  3801. }
  3802. /** For every microdescriptor we are currently downloading by descriptor
  3803. * digest, set result[d] to (void*)1. (Note that microdescriptor digests
  3804. * are 256-bit, and digestmap_t only holds 160-bit digests, so we're only
  3805. * getting the first 20 bytes of each digest here.)
  3806. *
  3807. * XXXX Let there be a digestmap256_t, and use that instead.
  3808. */
  3809. void
  3810. list_pending_microdesc_downloads(digestmap_t *result)
  3811. {
  3812. list_pending_downloads(result, DIR_PURPOSE_FETCH_MICRODESC, "d/");
  3813. }
  3814. /** Launch downloads for all the descriptors whose digests or digests256
  3815. * are listed as digests[i] for lo <= i < hi. (Lo and hi may be out of
  3816. * range.) If <b>source</b> is given, download from <b>source</b>;
  3817. * otherwise, download from an appropriate random directory server.
  3818. */
  3819. static void
  3820. initiate_descriptor_downloads(const routerstatus_t *source,
  3821. int purpose,
  3822. smartlist_t *digests,
  3823. int lo, int hi, int pds_flags)
  3824. {
  3825. int i, n = hi-lo;
  3826. char *resource, *cp;
  3827. size_t r_len;
  3828. int digest_len = DIGEST_LEN, enc_digest_len = HEX_DIGEST_LEN;
  3829. char sep = '+';
  3830. int b64_256 = 0;
  3831. if (purpose == DIR_PURPOSE_FETCH_MICRODESC) {
  3832. /* Microdescriptors are downloaded by "-"-separated base64-encoded
  3833. * 256-bit digests. */
  3834. digest_len = DIGEST256_LEN;
  3835. enc_digest_len = BASE64_DIGEST256_LEN;
  3836. sep = '-';
  3837. b64_256 = 1;
  3838. }
  3839. if (n <= 0)
  3840. return;
  3841. if (lo < 0)
  3842. lo = 0;
  3843. if (hi > smartlist_len(digests))
  3844. hi = smartlist_len(digests);
  3845. r_len = 8 + (enc_digest_len+1)*n;
  3846. cp = resource = tor_malloc(r_len);
  3847. memcpy(cp, "d/", 2);
  3848. cp += 2;
  3849. for (i = lo; i < hi; ++i) {
  3850. if (b64_256) {
  3851. digest256_to_base64(cp, smartlist_get(digests, i));
  3852. } else {
  3853. base16_encode(cp, r_len-(cp-resource),
  3854. smartlist_get(digests,i), digest_len);
  3855. }
  3856. cp += enc_digest_len;
  3857. *cp++ = sep;
  3858. }
  3859. memcpy(cp-1, ".z", 3);
  3860. if (source) {
  3861. /* We know which authority we want. */
  3862. directory_initiate_command_routerstatus(source, purpose,
  3863. ROUTER_PURPOSE_GENERAL,
  3864. 0, /* not private */
  3865. resource, NULL, 0, 0);
  3866. } else {
  3867. directory_get_from_dirserver(purpose, ROUTER_PURPOSE_GENERAL, resource,
  3868. pds_flags);
  3869. }
  3870. tor_free(resource);
  3871. }
  3872. /** Return 0 if this routerstatus is obsolete, too new, isn't
  3873. * running, or otherwise not a descriptor that we would make any
  3874. * use of even if we had it. Else return 1. */
  3875. static INLINE int
  3876. client_would_use_router(const routerstatus_t *rs, time_t now,
  3877. const or_options_t *options)
  3878. {
  3879. if (!rs->is_flagged_running && !options->FetchUselessDescriptors) {
  3880. /* If we had this router descriptor, we wouldn't even bother using it.
  3881. * But, if we want to have a complete list, fetch it anyway. */
  3882. return 0;
  3883. }
  3884. if (rs->published_on + options->TestingEstimatedDescriptorPropagationTime
  3885. > now) {
  3886. /* Most caches probably don't have this descriptor yet. */
  3887. return 0;
  3888. }
  3889. if (rs->published_on + OLD_ROUTER_DESC_MAX_AGE < now) {
  3890. /* We'd drop it immediately for being too old. */
  3891. return 0;
  3892. }
  3893. return 1;
  3894. }
  3895. /** Max amount of hashes to download per request.
  3896. * Since squid does not like URLs >= 4096 bytes we limit it to 96.
  3897. * 4096 - strlen(http://255.255.255.255/tor/server/d/.z) == 4058
  3898. * 4058/41 (40 for the hash and 1 for the + that separates them) => 98
  3899. * So use 96 because it's a nice number.
  3900. */
  3901. #define MAX_DL_PER_REQUEST 96
  3902. #define MAX_MICRODESC_DL_PER_REQUEST 92
  3903. /** Don't split our requests so finely that we are requesting fewer than
  3904. * this number per server. */
  3905. #define MIN_DL_PER_REQUEST 4
  3906. /** To prevent a single screwy cache from confusing us by selective reply,
  3907. * try to split our requests into at least this many requests. */
  3908. #define MIN_REQUESTS 3
  3909. /** If we want fewer than this many descriptors, wait until we
  3910. * want more, or until MAX_CLIENT_INTERVAL_WITHOUT_REQUEST has
  3911. * passed. */
  3912. #define MAX_DL_TO_DELAY 16
  3913. /** When directory clients have only a few servers to request, they batch
  3914. * them until they have more, or until this amount of time has passed. */
  3915. #define MAX_CLIENT_INTERVAL_WITHOUT_REQUEST (10*60)
  3916. /** Given a <b>purpose</b> (FETCH_MICRODESC or FETCH_SERVERDESC) and a list of
  3917. * router descriptor digests or microdescriptor digest256s in
  3918. * <b>downloadable</b>, decide whether to delay fetching until we have more.
  3919. * If we don't want to delay, launch one or more requests to the appropriate
  3920. * directory authorities.
  3921. */
  3922. void
  3923. launch_descriptor_downloads(int purpose,
  3924. smartlist_t *downloadable,
  3925. const routerstatus_t *source, time_t now)
  3926. {
  3927. int should_delay = 0, n_downloadable;
  3928. const or_options_t *options = get_options();
  3929. const char *descname;
  3930. tor_assert(purpose == DIR_PURPOSE_FETCH_SERVERDESC ||
  3931. purpose == DIR_PURPOSE_FETCH_MICRODESC);
  3932. descname = (purpose == DIR_PURPOSE_FETCH_SERVERDESC) ?
  3933. "routerdesc" : "microdesc";
  3934. n_downloadable = smartlist_len(downloadable);
  3935. if (!directory_fetches_dir_info_early(options)) {
  3936. if (n_downloadable >= MAX_DL_TO_DELAY) {
  3937. log_debug(LD_DIR,
  3938. "There are enough downloadable %ss to launch requests.",
  3939. descname);
  3940. should_delay = 0;
  3941. } else {
  3942. should_delay = (last_descriptor_download_attempted +
  3943. MAX_CLIENT_INTERVAL_WITHOUT_REQUEST) > now;
  3944. if (!should_delay && n_downloadable) {
  3945. if (last_descriptor_download_attempted) {
  3946. log_info(LD_DIR,
  3947. "There are not many downloadable %ss, but we've "
  3948. "been waiting long enough (%d seconds). Downloading.",
  3949. descname,
  3950. (int)(now-last_descriptor_download_attempted));
  3951. } else {
  3952. log_info(LD_DIR,
  3953. "There are not many downloadable %ss, but we haven't "
  3954. "tried downloading descriptors recently. Downloading.",
  3955. descname);
  3956. }
  3957. }
  3958. }
  3959. }
  3960. /* XXX should we consider having even the dir mirrors delay
  3961. * a little bit, so we don't load the authorities as much? -RD
  3962. * I don't think so. If we do, clients that want those descriptors may
  3963. * not actually find them if the caches haven't got them yet. -NM
  3964. */
  3965. if (! should_delay && n_downloadable) {
  3966. int i, n_per_request;
  3967. const char *req_plural = "", *rtr_plural = "";
  3968. int pds_flags = PDS_RETRY_IF_NO_SERVERS;
  3969. if (! authdir_mode_any_nonhidserv(options)) {
  3970. /* If we wind up going to the authorities, we want to only open one
  3971. * connection to each authority at a time, so that we don't overload
  3972. * them. We do this by setting PDS_NO_EXISTING_SERVERDESC_FETCH
  3973. * regardless of whether we're a cache or not; it gets ignored if we're
  3974. * not calling router_pick_trusteddirserver.
  3975. *
  3976. * Setting this flag can make initiate_descriptor_downloads() ignore
  3977. * requests. We need to make sure that we do in fact call
  3978. * update_router_descriptor_downloads() later on, once the connections
  3979. * have succeeded or failed.
  3980. */
  3981. pds_flags |= (purpose == DIR_PURPOSE_FETCH_MICRODESC) ?
  3982. PDS_NO_EXISTING_MICRODESC_FETCH :
  3983. PDS_NO_EXISTING_SERVERDESC_FETCH;
  3984. }
  3985. n_per_request = CEIL_DIV(n_downloadable, MIN_REQUESTS);
  3986. if (purpose == DIR_PURPOSE_FETCH_MICRODESC) {
  3987. if (n_per_request > MAX_MICRODESC_DL_PER_REQUEST)
  3988. n_per_request = MAX_MICRODESC_DL_PER_REQUEST;
  3989. } else {
  3990. if (n_per_request > MAX_DL_PER_REQUEST)
  3991. n_per_request = MAX_DL_PER_REQUEST;
  3992. }
  3993. if (n_per_request < MIN_DL_PER_REQUEST)
  3994. n_per_request = MIN_DL_PER_REQUEST;
  3995. if (n_downloadable > n_per_request)
  3996. req_plural = rtr_plural = "s";
  3997. else if (n_downloadable > 1)
  3998. rtr_plural = "s";
  3999. log_info(LD_DIR,
  4000. "Launching %d request%s for %d router%s, %d at a time",
  4001. CEIL_DIV(n_downloadable, n_per_request),
  4002. req_plural, n_downloadable, rtr_plural, n_per_request);
  4003. smartlist_sort_digests(downloadable);
  4004. for (i=0; i < n_downloadable; i += n_per_request) {
  4005. initiate_descriptor_downloads(source, purpose,
  4006. downloadable, i, i+n_per_request,
  4007. pds_flags);
  4008. }
  4009. last_descriptor_download_attempted = now;
  4010. }
  4011. }
  4012. /** Launch downloads for router status as needed, using the strategy used by
  4013. * authorities and caches: based on the v2 networkstatuses we have, download
  4014. * every descriptor we don't have but would serve, from a random authority
  4015. * that lists it. */
  4016. static void
  4017. update_router_descriptor_cache_downloads_v2(time_t now)
  4018. {
  4019. smartlist_t **downloadable; /* For each authority, what can we dl from it? */
  4020. smartlist_t **download_from; /* ... and, what will we dl from it? */
  4021. digestmap_t *map; /* Which descs are in progress, or assigned? */
  4022. int i, j, n;
  4023. int n_download;
  4024. const or_options_t *options = get_options();
  4025. const smartlist_t *networkstatus_v2_list = networkstatus_get_v2_list();
  4026. if (! directory_fetches_dir_info_early(options)) {
  4027. log_warn(LD_BUG, "Called update_router_descriptor_cache_downloads_v2() "
  4028. "on a non-dir-mirror?");
  4029. }
  4030. if (!networkstatus_v2_list || !smartlist_len(networkstatus_v2_list))
  4031. return;
  4032. map = digestmap_new();
  4033. n = smartlist_len(networkstatus_v2_list);
  4034. downloadable = tor_malloc_zero(sizeof(smartlist_t*) * n);
  4035. download_from = tor_malloc_zero(sizeof(smartlist_t*) * n);
  4036. /* Set map[d]=1 for the digest of every descriptor that we are currently
  4037. * downloading. */
  4038. list_pending_descriptor_downloads(map, 0);
  4039. /* For the digest of every descriptor that we don't have, and that we aren't
  4040. * downloading, add d to downloadable[i] if the i'th networkstatus knows
  4041. * about that descriptor, and we haven't already failed to get that
  4042. * descriptor from the corresponding authority.
  4043. */
  4044. n_download = 0;
  4045. SMARTLIST_FOREACH(networkstatus_v2_list, networkstatus_v2_t *, ns,
  4046. {
  4047. trusted_dir_server_t *ds;
  4048. smartlist_t *dl;
  4049. dl = downloadable[ns_sl_idx] = smartlist_new();
  4050. download_from[ns_sl_idx] = smartlist_new();
  4051. if (ns->published_on + MAX_NETWORKSTATUS_AGE+10*60 < now) {
  4052. /* Don't download if the networkstatus is almost ancient. */
  4053. /* Actually, I suspect what's happening here is that we ask
  4054. * for the descriptor when we have a given networkstatus,
  4055. * and then we get a newer networkstatus, and then we receive
  4056. * the descriptor. Having a networkstatus actually expire is
  4057. * probably a rare event, and we'll probably be happiest if
  4058. * we take this clause out. -RD */
  4059. continue;
  4060. }
  4061. /* Don't try dirservers that we think are down -- we might have
  4062. * just tried them and just marked them as down. */
  4063. ds = router_get_trusteddirserver_by_digest(ns->identity_digest);
  4064. if (ds && !ds->is_running)
  4065. continue;
  4066. SMARTLIST_FOREACH(ns->entries, routerstatus_t * , rs,
  4067. {
  4068. if (!rs->need_to_mirror)
  4069. continue;
  4070. if (router_get_by_descriptor_digest(rs->descriptor_digest)) {
  4071. log_warn(LD_BUG,
  4072. "We have a router descriptor, but need_to_mirror=1.");
  4073. rs->need_to_mirror = 0;
  4074. continue;
  4075. }
  4076. if (authdir_mode(options) && dirserv_would_reject_router(rs)) {
  4077. rs->need_to_mirror = 0;
  4078. continue;
  4079. }
  4080. if (digestmap_get(map, rs->descriptor_digest)) {
  4081. /* We're downloading it already. */
  4082. continue;
  4083. } else {
  4084. /* We could download it from this guy. */
  4085. smartlist_add(dl, rs->descriptor_digest);
  4086. ++n_download;
  4087. }
  4088. });
  4089. });
  4090. /* At random, assign descriptors to authorities such that:
  4091. * - if d is a member of some downloadable[x], d is a member of some
  4092. * download_from[y]. (Everything we want to download, we try to download
  4093. * from somebody.)
  4094. * - If d is a member of download_from[y], d is a member of downloadable[y].
  4095. * (We only try to download descriptors from authorities who claim to have
  4096. * them.)
  4097. * - No d is a member of download_from[x] and download_from[y] s.t. x != y.
  4098. * (We don't try to download anything from two authorities concurrently.)
  4099. */
  4100. while (n_download) {
  4101. int which_ns = crypto_rand_int(n);
  4102. smartlist_t *dl = downloadable[which_ns];
  4103. int idx;
  4104. char *d;
  4105. if (!smartlist_len(dl))
  4106. continue;
  4107. idx = crypto_rand_int(smartlist_len(dl));
  4108. d = smartlist_get(dl, idx);
  4109. if (! digestmap_get(map, d)) {
  4110. smartlist_add(download_from[which_ns], d);
  4111. digestmap_set(map, d, (void*) 1);
  4112. }
  4113. smartlist_del(dl, idx);
  4114. --n_download;
  4115. }
  4116. /* Now, we can actually launch our requests. */
  4117. for (i=0; i<n; ++i) {
  4118. networkstatus_v2_t *ns = smartlist_get(networkstatus_v2_list, i);
  4119. trusted_dir_server_t *ds =
  4120. router_get_trusteddirserver_by_digest(ns->identity_digest);
  4121. smartlist_t *dl = download_from[i];
  4122. int pds_flags = PDS_RETRY_IF_NO_SERVERS;
  4123. if (! authdir_mode_any_nonhidserv(options))
  4124. pds_flags |= PDS_NO_EXISTING_SERVERDESC_FETCH; /* XXXX ignored*/
  4125. if (!ds) {
  4126. log_info(LD_DIR, "Networkstatus with no corresponding authority!");
  4127. continue;
  4128. }
  4129. if (! smartlist_len(dl))
  4130. continue;
  4131. log_info(LD_DIR, "Requesting %d descriptors from authority \"%s\"",
  4132. smartlist_len(dl), ds->nickname);
  4133. for (j=0; j < smartlist_len(dl); j += MAX_DL_PER_REQUEST) {
  4134. initiate_descriptor_downloads(&(ds->fake_status),
  4135. DIR_PURPOSE_FETCH_SERVERDESC, dl, j,
  4136. j+MAX_DL_PER_REQUEST, pds_flags);
  4137. }
  4138. }
  4139. for (i=0; i<n; ++i) {
  4140. smartlist_free(download_from[i]);
  4141. smartlist_free(downloadable[i]);
  4142. }
  4143. tor_free(download_from);
  4144. tor_free(downloadable);
  4145. digestmap_free(map,NULL);
  4146. }
  4147. /** For any descriptor that we want that's currently listed in
  4148. * <b>consensus</b>, download it as appropriate. */
  4149. void
  4150. update_consensus_router_descriptor_downloads(time_t now, int is_vote,
  4151. networkstatus_t *consensus)
  4152. {
  4153. const or_options_t *options = get_options();
  4154. digestmap_t *map = NULL;
  4155. smartlist_t *no_longer_old = smartlist_new();
  4156. smartlist_t *downloadable = smartlist_new();
  4157. routerstatus_t *source = NULL;
  4158. int authdir = authdir_mode(options);
  4159. int n_delayed=0, n_have=0, n_would_reject=0, n_wouldnt_use=0,
  4160. n_inprogress=0, n_in_oldrouters=0;
  4161. if (directory_too_idle_to_fetch_descriptors(options, now))
  4162. goto done;
  4163. if (!consensus)
  4164. goto done;
  4165. if (is_vote) {
  4166. /* where's it from, so we know whom to ask for descriptors */
  4167. trusted_dir_server_t *ds;
  4168. networkstatus_voter_info_t *voter = smartlist_get(consensus->voters, 0);
  4169. tor_assert(voter);
  4170. ds = trusteddirserver_get_by_v3_auth_digest(voter->identity_digest);
  4171. if (ds)
  4172. source = &(ds->fake_status);
  4173. else
  4174. log_warn(LD_DIR, "couldn't lookup source from vote?");
  4175. }
  4176. map = digestmap_new();
  4177. list_pending_descriptor_downloads(map, 0);
  4178. SMARTLIST_FOREACH_BEGIN(consensus->routerstatus_list, void *, rsp) {
  4179. routerstatus_t *rs =
  4180. is_vote ? &(((vote_routerstatus_t *)rsp)->status) : rsp;
  4181. signed_descriptor_t *sd;
  4182. if ((sd = router_get_by_descriptor_digest(rs->descriptor_digest))) {
  4183. const routerinfo_t *ri;
  4184. ++n_have;
  4185. if (!(ri = router_get_by_id_digest(rs->identity_digest)) ||
  4186. tor_memneq(ri->cache_info.signed_descriptor_digest,
  4187. sd->signed_descriptor_digest, DIGEST_LEN)) {
  4188. /* We have a descriptor with this digest, but either there is no
  4189. * entry in routerlist with the same ID (!ri), or there is one,
  4190. * but the identity digest differs (memcmp).
  4191. */
  4192. smartlist_add(no_longer_old, sd);
  4193. ++n_in_oldrouters; /* We have it in old_routers. */
  4194. }
  4195. continue; /* We have it already. */
  4196. }
  4197. if (digestmap_get(map, rs->descriptor_digest)) {
  4198. ++n_inprogress;
  4199. continue; /* We have an in-progress download. */
  4200. }
  4201. if (!download_status_is_ready(&rs->dl_status, now,
  4202. MAX_ROUTERDESC_DOWNLOAD_FAILURES)) {
  4203. ++n_delayed; /* Not ready for retry. */
  4204. continue;
  4205. }
  4206. if (authdir && dirserv_would_reject_router(rs)) {
  4207. ++n_would_reject;
  4208. continue; /* We would throw it out immediately. */
  4209. }
  4210. if (!directory_caches_dir_info(options) &&
  4211. !client_would_use_router(rs, now, options)) {
  4212. ++n_wouldnt_use;
  4213. continue; /* We would never use it ourself. */
  4214. }
  4215. if (is_vote && source) {
  4216. char time_bufnew[ISO_TIME_LEN+1];
  4217. char time_bufold[ISO_TIME_LEN+1];
  4218. const routerinfo_t *oldrouter;
  4219. oldrouter = router_get_by_id_digest(rs->identity_digest);
  4220. format_iso_time(time_bufnew, rs->published_on);
  4221. if (oldrouter)
  4222. format_iso_time(time_bufold, oldrouter->cache_info.published_on);
  4223. log_info(LD_DIR, "Learned about %s (%s vs %s) from %s's vote (%s)",
  4224. routerstatus_describe(rs),
  4225. time_bufnew,
  4226. oldrouter ? time_bufold : "none",
  4227. source->nickname, oldrouter ? "known" : "unknown");
  4228. }
  4229. smartlist_add(downloadable, rs->descriptor_digest);
  4230. } SMARTLIST_FOREACH_END(rsp);
  4231. if (!authdir_mode_handles_descs(options, ROUTER_PURPOSE_GENERAL)
  4232. && smartlist_len(no_longer_old)) {
  4233. routerlist_t *rl = router_get_routerlist();
  4234. log_info(LD_DIR, "%d router descriptors listed in consensus are "
  4235. "currently in old_routers; making them current.",
  4236. smartlist_len(no_longer_old));
  4237. SMARTLIST_FOREACH(no_longer_old, signed_descriptor_t *, sd, {
  4238. const char *msg;
  4239. was_router_added_t r;
  4240. routerinfo_t *ri = routerlist_reparse_old(rl, sd);
  4241. if (!ri) {
  4242. log_warn(LD_BUG, "Failed to re-parse a router.");
  4243. continue;
  4244. }
  4245. r = router_add_to_routerlist(ri, &msg, 1, 0);
  4246. if (WRA_WAS_OUTDATED(r)) {
  4247. log_warn(LD_DIR, "Couldn't add re-parsed router: %s",
  4248. msg?msg:"???");
  4249. }
  4250. });
  4251. routerlist_assert_ok(rl);
  4252. }
  4253. log_info(LD_DIR,
  4254. "%d router descriptors downloadable. %d delayed; %d present "
  4255. "(%d of those were in old_routers); %d would_reject; "
  4256. "%d wouldnt_use; %d in progress.",
  4257. smartlist_len(downloadable), n_delayed, n_have, n_in_oldrouters,
  4258. n_would_reject, n_wouldnt_use, n_inprogress);
  4259. launch_descriptor_downloads(DIR_PURPOSE_FETCH_SERVERDESC,
  4260. downloadable, source, now);
  4261. digestmap_free(map, NULL);
  4262. done:
  4263. smartlist_free(downloadable);
  4264. smartlist_free(no_longer_old);
  4265. }
  4266. /** How often should we launch a server/authority request to be sure of getting
  4267. * a guess for our IP? */
  4268. /*XXXX023 this info should come from netinfo cells or something, or we should
  4269. * do this only when we aren't seeing incoming data. see bug 652. */
  4270. #define DUMMY_DOWNLOAD_INTERVAL (20*60)
  4271. /** As needed, launch a dummy router descriptor fetch to see if our
  4272. * address has changed. */
  4273. static void
  4274. launch_dummy_descriptor_download_as_needed(time_t now,
  4275. const or_options_t *options)
  4276. {
  4277. static time_t last_dummy_download = 0;
  4278. /* XXXX023 we could be smarter here; see notes on bug 652. */
  4279. /* If we're a server that doesn't have a configured address, we rely on
  4280. * directory fetches to learn when our address changes. So if we haven't
  4281. * tried to get any routerdescs in a long time, try a dummy fetch now. */
  4282. if (!options->Address &&
  4283. server_mode(options) &&
  4284. last_descriptor_download_attempted + DUMMY_DOWNLOAD_INTERVAL < now &&
  4285. last_dummy_download + DUMMY_DOWNLOAD_INTERVAL < now) {
  4286. last_dummy_download = now;
  4287. directory_get_from_dirserver(DIR_PURPOSE_FETCH_SERVERDESC,
  4288. ROUTER_PURPOSE_GENERAL, "authority.z",
  4289. PDS_RETRY_IF_NO_SERVERS);
  4290. }
  4291. }
  4292. /** Launch downloads for router status as needed. */
  4293. void
  4294. update_router_descriptor_downloads(time_t now)
  4295. {
  4296. const or_options_t *options = get_options();
  4297. if (should_delay_dir_fetches(options))
  4298. return;
  4299. if (!we_fetch_router_descriptors(options))
  4300. return;
  4301. if (directory_fetches_dir_info_early(options)) {
  4302. update_router_descriptor_cache_downloads_v2(now);
  4303. }
  4304. update_consensus_router_descriptor_downloads(now, 0,
  4305. networkstatus_get_reasonably_live_consensus(now, FLAV_NS));
  4306. }
  4307. /** Launch extrainfo downloads as needed. */
  4308. void
  4309. update_extrainfo_downloads(time_t now)
  4310. {
  4311. const or_options_t *options = get_options();
  4312. routerlist_t *rl;
  4313. smartlist_t *wanted;
  4314. digestmap_t *pending;
  4315. int old_routers, i;
  4316. int n_no_ei = 0, n_pending = 0, n_have = 0, n_delay = 0;
  4317. if (! options->DownloadExtraInfo)
  4318. return;
  4319. if (should_delay_dir_fetches(options))
  4320. return;
  4321. if (!router_have_minimum_dir_info())
  4322. return;
  4323. pending = digestmap_new();
  4324. list_pending_descriptor_downloads(pending, 1);
  4325. rl = router_get_routerlist();
  4326. wanted = smartlist_new();
  4327. for (old_routers = 0; old_routers < 2; ++old_routers) {
  4328. smartlist_t *lst = old_routers ? rl->old_routers : rl->routers;
  4329. for (i = 0; i < smartlist_len(lst); ++i) {
  4330. signed_descriptor_t *sd;
  4331. char *d;
  4332. if (old_routers)
  4333. sd = smartlist_get(lst, i);
  4334. else
  4335. sd = &((routerinfo_t*)smartlist_get(lst, i))->cache_info;
  4336. if (sd->is_extrainfo)
  4337. continue; /* This should never happen. */
  4338. if (old_routers && !router_get_by_id_digest(sd->identity_digest))
  4339. continue; /* Couldn't check the signature if we got it. */
  4340. if (sd->extrainfo_is_bogus)
  4341. continue;
  4342. d = sd->extra_info_digest;
  4343. if (tor_digest_is_zero(d)) {
  4344. ++n_no_ei;
  4345. continue;
  4346. }
  4347. if (eimap_get(rl->extra_info_map, d)) {
  4348. ++n_have;
  4349. continue;
  4350. }
  4351. if (!download_status_is_ready(&sd->ei_dl_status, now,
  4352. MAX_ROUTERDESC_DOWNLOAD_FAILURES)) {
  4353. ++n_delay;
  4354. continue;
  4355. }
  4356. if (digestmap_get(pending, d)) {
  4357. ++n_pending;
  4358. continue;
  4359. }
  4360. smartlist_add(wanted, d);
  4361. }
  4362. }
  4363. digestmap_free(pending, NULL);
  4364. log_info(LD_DIR, "Extrainfo download status: %d router with no ei, %d "
  4365. "with present ei, %d delaying, %d pending, %d downloadable.",
  4366. n_no_ei, n_have, n_delay, n_pending, smartlist_len(wanted));
  4367. smartlist_shuffle(wanted);
  4368. for (i = 0; i < smartlist_len(wanted); i += MAX_DL_PER_REQUEST) {
  4369. initiate_descriptor_downloads(NULL, DIR_PURPOSE_FETCH_EXTRAINFO,
  4370. wanted, i, i + MAX_DL_PER_REQUEST,
  4371. PDS_RETRY_IF_NO_SERVERS|PDS_NO_EXISTING_SERVERDESC_FETCH);
  4372. }
  4373. smartlist_free(wanted);
  4374. }
  4375. /** True iff, the last time we checked whether we had enough directory info
  4376. * to build circuits, the answer was "yes". */
  4377. static int have_min_dir_info = 0;
  4378. /** True iff enough has changed since the last time we checked whether we had
  4379. * enough directory info to build circuits that our old answer can no longer
  4380. * be trusted. */
  4381. static int need_to_update_have_min_dir_info = 1;
  4382. /** String describing what we're missing before we have enough directory
  4383. * info. */
  4384. static char dir_info_status[128] = "";
  4385. /** Return true iff we have enough networkstatus and router information to
  4386. * start building circuits. Right now, this means "more than half the
  4387. * networkstatus documents, and at least 1/4 of expected routers." */
  4388. //XXX should consider whether we have enough exiting nodes here.
  4389. int
  4390. router_have_minimum_dir_info(void)
  4391. {
  4392. if (PREDICT_UNLIKELY(need_to_update_have_min_dir_info)) {
  4393. update_router_have_minimum_dir_info();
  4394. need_to_update_have_min_dir_info = 0;
  4395. }
  4396. return have_min_dir_info;
  4397. }
  4398. /** Called when our internal view of the directory has changed. This can be
  4399. * when the authorities change, networkstatuses change, the list of routerdescs
  4400. * changes, or number of running routers changes.
  4401. */
  4402. void
  4403. router_dir_info_changed(void)
  4404. {
  4405. need_to_update_have_min_dir_info = 1;
  4406. rend_hsdir_routers_changed();
  4407. }
  4408. /** Return a string describing what we're missing before we have enough
  4409. * directory info. */
  4410. const char *
  4411. get_dir_info_status_string(void)
  4412. {
  4413. return dir_info_status;
  4414. }
  4415. /** Iterate over the servers listed in <b>consensus</b>, and count how many of
  4416. * them seem like ones we'd use, and how many of <em>those</em> we have
  4417. * descriptors for. Store the former in *<b>num_usable</b> and the latter in
  4418. * *<b>num_present</b>. If <b>in_set</b> is non-NULL, only consider those
  4419. * routers in <b>in_set</b>. If <b>exit_only</b> is true, only consider nodes
  4420. * with the Exit flag.
  4421. */
  4422. static void
  4423. count_usable_descriptors(int *num_present, int *num_usable,
  4424. const networkstatus_t *consensus,
  4425. const or_options_t *options, time_t now,
  4426. routerset_t *in_set, int exit_only)
  4427. {
  4428. const int md = (consensus->flavor == FLAV_MICRODESC);
  4429. *num_present = 0, *num_usable=0;
  4430. SMARTLIST_FOREACH_BEGIN(consensus->routerstatus_list, routerstatus_t *, rs)
  4431. {
  4432. if (exit_only && ! rs->is_exit)
  4433. continue;
  4434. if (in_set && ! routerset_contains_routerstatus(in_set, rs, -1))
  4435. continue;
  4436. if (client_would_use_router(rs, now, options)) {
  4437. const char * const digest = rs->descriptor_digest;
  4438. int present;
  4439. ++*num_usable; /* the consensus says we want it. */
  4440. if (md)
  4441. present = NULL != microdesc_cache_lookup_by_digest256(NULL, digest);
  4442. else
  4443. present = NULL != router_get_by_descriptor_digest(digest);
  4444. if (present) {
  4445. /* we have the descriptor listed in the consensus. */
  4446. ++*num_present;
  4447. }
  4448. }
  4449. }
  4450. SMARTLIST_FOREACH_END(rs);
  4451. log_debug(LD_DIR, "%d usable, %d present.", *num_usable, *num_present);
  4452. }
  4453. /** We just fetched a new set of descriptors. Compute how far through
  4454. * the "loading descriptors" bootstrapping phase we are, so we can inform
  4455. * the controller of our progress. */
  4456. int
  4457. count_loading_descriptors_progress(void)
  4458. {
  4459. int num_present = 0, num_usable=0;
  4460. time_t now = time(NULL);
  4461. const networkstatus_t *consensus =
  4462. networkstatus_get_reasonably_live_consensus(now,usable_consensus_flavor());
  4463. double fraction;
  4464. if (!consensus)
  4465. return 0; /* can't count descriptors if we have no list of them */
  4466. count_usable_descriptors(&num_present, &num_usable,
  4467. consensus, get_options(), now, NULL, 0);
  4468. if (num_usable == 0)
  4469. return 0; /* don't div by 0 */
  4470. fraction = num_present / (num_usable/4.);
  4471. if (fraction > 1.0)
  4472. return 0; /* it's not the number of descriptors holding us back */
  4473. return BOOTSTRAP_STATUS_LOADING_DESCRIPTORS + (int)
  4474. (fraction*(BOOTSTRAP_STATUS_CONN_OR-1 -
  4475. BOOTSTRAP_STATUS_LOADING_DESCRIPTORS));
  4476. }
  4477. /** Change the value of have_min_dir_info, setting it true iff we have enough
  4478. * network and router information to build circuits. Clear the value of
  4479. * need_to_update_have_min_dir_info. */
  4480. static void
  4481. update_router_have_minimum_dir_info(void)
  4482. {
  4483. int num_present = 0, num_usable=0;
  4484. int num_exit_present = 0, num_exit_usable = 0;
  4485. time_t now = time(NULL);
  4486. int res;
  4487. const or_options_t *options = get_options();
  4488. const networkstatus_t *consensus =
  4489. networkstatus_get_reasonably_live_consensus(now,usable_consensus_flavor());
  4490. int using_md;
  4491. if (!consensus) {
  4492. if (!networkstatus_get_latest_consensus())
  4493. strlcpy(dir_info_status, "We have no usable consensus.",
  4494. sizeof(dir_info_status));
  4495. else
  4496. strlcpy(dir_info_status, "We have no recent usable consensus.",
  4497. sizeof(dir_info_status));
  4498. res = 0;
  4499. goto done;
  4500. }
  4501. if (should_delay_dir_fetches(get_options())) {
  4502. log_notice(LD_DIR, "no known bridge descriptors running yet; stalling");
  4503. strlcpy(dir_info_status, "No live bridge descriptors.",
  4504. sizeof(dir_info_status));
  4505. res = 0;
  4506. goto done;
  4507. }
  4508. using_md = consensus->flavor == FLAV_MICRODESC;
  4509. count_usable_descriptors(&num_present, &num_usable, consensus, options, now,
  4510. NULL, 0);
  4511. count_usable_descriptors(&num_exit_present, &num_exit_usable,
  4512. consensus, options, now, options->ExitNodes, 1);
  4513. /* What fraction of desired server descriptors do we need before we will
  4514. * build circuits? */
  4515. #define FRACTION_USABLE_NEEDED .75
  4516. /* What fraction of desired _exit_ server descriptors do we need before we
  4517. * will build circuits? */
  4518. #define FRACTION_EXIT_USABLE_NEEDED .5
  4519. if (num_present < num_usable * FRACTION_USABLE_NEEDED) {
  4520. tor_snprintf(dir_info_status, sizeof(dir_info_status),
  4521. "We have only %d/%d usable %sdescriptors.",
  4522. num_present, num_usable, using_md ? "micro" : "");
  4523. res = 0;
  4524. control_event_bootstrap(BOOTSTRAP_STATUS_REQUESTING_DESCRIPTORS, 0);
  4525. goto done;
  4526. } else if (num_present < 2) {
  4527. tor_snprintf(dir_info_status, sizeof(dir_info_status),
  4528. "Only %d %sdescriptor%s here and believed reachable!",
  4529. num_present, using_md ? "micro" : "", num_present ? "" : "s");
  4530. res = 0;
  4531. goto done;
  4532. } else if (num_exit_present < num_exit_usable * FRACTION_EXIT_USABLE_NEEDED) {
  4533. tor_snprintf(dir_info_status, sizeof(dir_info_status),
  4534. "We have only %d/%d usable exit node descriptors.",
  4535. num_exit_present, num_exit_usable);
  4536. res = 0;
  4537. control_event_bootstrap(BOOTSTRAP_STATUS_REQUESTING_DESCRIPTORS, 0);
  4538. goto done;
  4539. }
  4540. /* Check for entry nodes. */
  4541. if (options->EntryNodes) {
  4542. count_usable_descriptors(&num_present, &num_usable, consensus, options,
  4543. now, options->EntryNodes, 0);
  4544. if (!num_usable || !num_present) {
  4545. tor_snprintf(dir_info_status, sizeof(dir_info_status),
  4546. "We have only %d/%d usable entry node %sdescriptors.",
  4547. num_present, num_usable, using_md?"micro":"");
  4548. res = 0;
  4549. goto done;
  4550. }
  4551. }
  4552. res = 1;
  4553. done:
  4554. if (res && !have_min_dir_info) {
  4555. log(LOG_NOTICE, LD_DIR,
  4556. "We now have enough directory information to build circuits.");
  4557. control_event_client_status(LOG_NOTICE, "ENOUGH_DIR_INFO");
  4558. control_event_bootstrap(BOOTSTRAP_STATUS_CONN_OR, 0);
  4559. }
  4560. if (!res && have_min_dir_info) {
  4561. int quiet = directory_too_idle_to_fetch_descriptors(options, now);
  4562. log(quiet ? LOG_INFO : LOG_NOTICE, LD_DIR,
  4563. "Our directory information is no longer up-to-date "
  4564. "enough to build circuits: %s", dir_info_status);
  4565. /* a) make us log when we next complete a circuit, so we know when Tor
  4566. * is back up and usable, and b) disable some activities that Tor
  4567. * should only do while circuits are working, like reachability tests
  4568. * and fetching bridge descriptors only over circuits. */
  4569. can_complete_circuit = 0;
  4570. control_event_client_status(LOG_NOTICE, "NOT_ENOUGH_DIR_INFO");
  4571. }
  4572. have_min_dir_info = res;
  4573. need_to_update_have_min_dir_info = 0;
  4574. }
  4575. /** Reset the descriptor download failure count on all routers, so that we
  4576. * can retry any long-failed routers immediately.
  4577. */
  4578. void
  4579. router_reset_descriptor_download_failures(void)
  4580. {
  4581. networkstatus_reset_download_failures();
  4582. last_descriptor_download_attempted = 0;
  4583. if (!routerlist)
  4584. return;
  4585. SMARTLIST_FOREACH(routerlist->routers, routerinfo_t *, ri,
  4586. {
  4587. download_status_reset(&ri->cache_info.ei_dl_status);
  4588. });
  4589. SMARTLIST_FOREACH(routerlist->old_routers, signed_descriptor_t *, sd,
  4590. {
  4591. download_status_reset(&sd->ei_dl_status);
  4592. });
  4593. }
  4594. /** Any changes in a router descriptor's publication time larger than this are
  4595. * automatically non-cosmetic. */
  4596. #define ROUTER_MAX_COSMETIC_TIME_DIFFERENCE (2*60*60)
  4597. /** We allow uptime to vary from how much it ought to be by this much. */
  4598. #define ROUTER_ALLOW_UPTIME_DRIFT (6*60*60)
  4599. /** Return true iff the only differences between r1 and r2 are such that
  4600. * would not cause a recent (post 0.1.1.6) dirserver to republish.
  4601. */
  4602. int
  4603. router_differences_are_cosmetic(const routerinfo_t *r1, const routerinfo_t *r2)
  4604. {
  4605. time_t r1pub, r2pub;
  4606. long time_difference;
  4607. tor_assert(r1 && r2);
  4608. /* r1 should be the one that was published first. */
  4609. if (r1->cache_info.published_on > r2->cache_info.published_on) {
  4610. const routerinfo_t *ri_tmp = r2;
  4611. r2 = r1;
  4612. r1 = ri_tmp;
  4613. }
  4614. /* If any key fields differ, they're different. */
  4615. if (strcasecmp(r1->address, r2->address) ||
  4616. strcasecmp(r1->nickname, r2->nickname) ||
  4617. r1->or_port != r2->or_port ||
  4618. r1->dir_port != r2->dir_port ||
  4619. r1->purpose != r2->purpose ||
  4620. crypto_pk_cmp_keys(r1->onion_pkey, r2->onion_pkey) ||
  4621. crypto_pk_cmp_keys(r1->identity_pkey, r2->identity_pkey) ||
  4622. strcasecmp(r1->platform, r2->platform) ||
  4623. (r1->contact_info && !r2->contact_info) || /* contact_info is optional */
  4624. (!r1->contact_info && r2->contact_info) ||
  4625. (r1->contact_info && r2->contact_info &&
  4626. strcasecmp(r1->contact_info, r2->contact_info)) ||
  4627. r1->is_hibernating != r2->is_hibernating ||
  4628. cmp_addr_policies(r1->exit_policy, r2->exit_policy))
  4629. return 0;
  4630. if ((r1->declared_family == NULL) != (r2->declared_family == NULL))
  4631. return 0;
  4632. if (r1->declared_family && r2->declared_family) {
  4633. int i, n;
  4634. if (smartlist_len(r1->declared_family)!=smartlist_len(r2->declared_family))
  4635. return 0;
  4636. n = smartlist_len(r1->declared_family);
  4637. for (i=0; i < n; ++i) {
  4638. if (strcasecmp(smartlist_get(r1->declared_family, i),
  4639. smartlist_get(r2->declared_family, i)))
  4640. return 0;
  4641. }
  4642. }
  4643. /* Did bandwidth change a lot? */
  4644. if ((r1->bandwidthcapacity < r2->bandwidthcapacity/2) ||
  4645. (r2->bandwidthcapacity < r1->bandwidthcapacity/2))
  4646. return 0;
  4647. /* Did the bandwidthrate or bandwidthburst change? */
  4648. if ((r1->bandwidthrate != r2->bandwidthrate) ||
  4649. (r1->bandwidthburst != r2->bandwidthburst))
  4650. return 0;
  4651. /* Did more than 12 hours pass? */
  4652. if (r1->cache_info.published_on + ROUTER_MAX_COSMETIC_TIME_DIFFERENCE
  4653. < r2->cache_info.published_on)
  4654. return 0;
  4655. /* Did uptime fail to increase by approximately the amount we would think,
  4656. * give or take some slop? */
  4657. r1pub = r1->cache_info.published_on;
  4658. r2pub = r2->cache_info.published_on;
  4659. time_difference = labs(r2->uptime - (r1->uptime + (r2pub - r1pub)));
  4660. if (time_difference > ROUTER_ALLOW_UPTIME_DRIFT &&
  4661. time_difference > r1->uptime * .05 &&
  4662. time_difference > r2->uptime * .05)
  4663. return 0;
  4664. /* Otherwise, the difference is cosmetic. */
  4665. return 1;
  4666. }
  4667. /** Check whether <b>ri</b> (a.k.a. sd) is a router compatible with the
  4668. * extrainfo document
  4669. * <b>ei</b>. If no router is compatible with <b>ei</b>, <b>ei</b> should be
  4670. * dropped. Return 0 for "compatible", return 1 for "reject, and inform
  4671. * whoever uploaded <b>ei</b>, and return -1 for "reject silently.". If
  4672. * <b>msg</b> is present, set *<b>msg</b> to a description of the
  4673. * incompatibility (if any).
  4674. **/
  4675. int
  4676. routerinfo_incompatible_with_extrainfo(const routerinfo_t *ri,
  4677. extrainfo_t *ei,
  4678. signed_descriptor_t *sd,
  4679. const char **msg)
  4680. {
  4681. int digest_matches, r=1;
  4682. tor_assert(ri);
  4683. tor_assert(ei);
  4684. if (!sd)
  4685. sd = (signed_descriptor_t*)&ri->cache_info;
  4686. if (ei->bad_sig) {
  4687. if (msg) *msg = "Extrainfo signature was bad, or signed with wrong key.";
  4688. return 1;
  4689. }
  4690. digest_matches = tor_memeq(ei->cache_info.signed_descriptor_digest,
  4691. sd->extra_info_digest, DIGEST_LEN);
  4692. /* The identity must match exactly to have been generated at the same time
  4693. * by the same router. */
  4694. if (tor_memneq(ri->cache_info.identity_digest,
  4695. ei->cache_info.identity_digest,
  4696. DIGEST_LEN)) {
  4697. if (msg) *msg = "Extrainfo nickname or identity did not match routerinfo";
  4698. goto err; /* different servers */
  4699. }
  4700. if (ei->pending_sig) {
  4701. char signed_digest[128];
  4702. if (crypto_pk_public_checksig(ri->identity_pkey,
  4703. signed_digest, sizeof(signed_digest),
  4704. ei->pending_sig, ei->pending_sig_len) != DIGEST_LEN ||
  4705. tor_memneq(signed_digest, ei->cache_info.signed_descriptor_digest,
  4706. DIGEST_LEN)) {
  4707. ei->bad_sig = 1;
  4708. tor_free(ei->pending_sig);
  4709. if (msg) *msg = "Extrainfo signature bad, or signed with wrong key";
  4710. goto err; /* Bad signature, or no match. */
  4711. }
  4712. ei->cache_info.send_unencrypted = ri->cache_info.send_unencrypted;
  4713. tor_free(ei->pending_sig);
  4714. }
  4715. if (ei->cache_info.published_on < sd->published_on) {
  4716. if (msg) *msg = "Extrainfo published time did not match routerdesc";
  4717. goto err;
  4718. } else if (ei->cache_info.published_on > sd->published_on) {
  4719. if (msg) *msg = "Extrainfo published time did not match routerdesc";
  4720. r = -1;
  4721. goto err;
  4722. }
  4723. if (!digest_matches) {
  4724. if (msg) *msg = "Extrainfo digest did not match value from routerdesc";
  4725. goto err; /* Digest doesn't match declared value. */
  4726. }
  4727. return 0;
  4728. err:
  4729. if (digest_matches) {
  4730. /* This signature was okay, and the digest was right: This is indeed the
  4731. * corresponding extrainfo. But insanely, it doesn't match the routerinfo
  4732. * that lists it. Don't try to fetch this one again. */
  4733. sd->extrainfo_is_bogus = 1;
  4734. }
  4735. return r;
  4736. }
  4737. /** Assert that the internal representation of <b>rl</b> is
  4738. * self-consistent. */
  4739. void
  4740. routerlist_assert_ok(const routerlist_t *rl)
  4741. {
  4742. routerinfo_t *r2;
  4743. signed_descriptor_t *sd2;
  4744. if (!rl)
  4745. return;
  4746. SMARTLIST_FOREACH(rl->routers, routerinfo_t *, r,
  4747. {
  4748. r2 = rimap_get(rl->identity_map, r->cache_info.identity_digest);
  4749. tor_assert(r == r2);
  4750. sd2 = sdmap_get(rl->desc_digest_map,
  4751. r->cache_info.signed_descriptor_digest);
  4752. tor_assert(&(r->cache_info) == sd2);
  4753. tor_assert(r->cache_info.routerlist_index == r_sl_idx);
  4754. /* XXXX
  4755. *
  4756. * Hoo boy. We need to fix this one, and the fix is a bit tricky, so
  4757. * commenting this out is just a band-aid.
  4758. *
  4759. * The problem is that, although well-behaved router descriptors
  4760. * should never have the same value for their extra_info_digest, it's
  4761. * possible for ill-behaved routers to claim whatever they like there.
  4762. *
  4763. * The real answer is to trash desc_by_eid_map and instead have
  4764. * something that indicates for a given extra-info digest we want,
  4765. * what its download status is. We'll do that as a part of routerlist
  4766. * refactoring once consensus directories are in. For now,
  4767. * this rep violation is probably harmless: an adversary can make us
  4768. * reset our retry count for an extrainfo, but that's not the end
  4769. * of the world. Changing the representation in 0.2.0.x would just
  4770. * destabilize the codebase.
  4771. if (!tor_digest_is_zero(r->cache_info.extra_info_digest)) {
  4772. signed_descriptor_t *sd3 =
  4773. sdmap_get(rl->desc_by_eid_map, r->cache_info.extra_info_digest);
  4774. tor_assert(sd3 == &(r->cache_info));
  4775. }
  4776. */
  4777. });
  4778. SMARTLIST_FOREACH(rl->old_routers, signed_descriptor_t *, sd,
  4779. {
  4780. r2 = rimap_get(rl->identity_map, sd->identity_digest);
  4781. tor_assert(sd != &(r2->cache_info));
  4782. sd2 = sdmap_get(rl->desc_digest_map, sd->signed_descriptor_digest);
  4783. tor_assert(sd == sd2);
  4784. tor_assert(sd->routerlist_index == sd_sl_idx);
  4785. /* XXXX see above.
  4786. if (!tor_digest_is_zero(sd->extra_info_digest)) {
  4787. signed_descriptor_t *sd3 =
  4788. sdmap_get(rl->desc_by_eid_map, sd->extra_info_digest);
  4789. tor_assert(sd3 == sd);
  4790. }
  4791. */
  4792. });
  4793. RIMAP_FOREACH(rl->identity_map, d, r) {
  4794. tor_assert(tor_memeq(r->cache_info.identity_digest, d, DIGEST_LEN));
  4795. } DIGESTMAP_FOREACH_END;
  4796. SDMAP_FOREACH(rl->desc_digest_map, d, sd) {
  4797. tor_assert(tor_memeq(sd->signed_descriptor_digest, d, DIGEST_LEN));
  4798. } DIGESTMAP_FOREACH_END;
  4799. SDMAP_FOREACH(rl->desc_by_eid_map, d, sd) {
  4800. tor_assert(!tor_digest_is_zero(d));
  4801. tor_assert(sd);
  4802. tor_assert(tor_memeq(sd->extra_info_digest, d, DIGEST_LEN));
  4803. } DIGESTMAP_FOREACH_END;
  4804. EIMAP_FOREACH(rl->extra_info_map, d, ei) {
  4805. signed_descriptor_t *sd;
  4806. tor_assert(tor_memeq(ei->cache_info.signed_descriptor_digest,
  4807. d, DIGEST_LEN));
  4808. sd = sdmap_get(rl->desc_by_eid_map,
  4809. ei->cache_info.signed_descriptor_digest);
  4810. // tor_assert(sd); // XXXX see above
  4811. if (sd) {
  4812. tor_assert(tor_memeq(ei->cache_info.signed_descriptor_digest,
  4813. sd->extra_info_digest, DIGEST_LEN));
  4814. }
  4815. } DIGESTMAP_FOREACH_END;
  4816. }
  4817. /** Allocate and return a new string representing the contact info
  4818. * and platform string for <b>router</b>,
  4819. * surrounded by quotes and using standard C escapes.
  4820. *
  4821. * THIS FUNCTION IS NOT REENTRANT. Don't call it from outside the main
  4822. * thread. Also, each call invalidates the last-returned value, so don't
  4823. * try log_warn(LD_GENERAL, "%s %s", esc_router_info(a), esc_router_info(b));
  4824. *
  4825. * If <b>router</b> is NULL, it just frees its internal memory and returns.
  4826. */
  4827. const char *
  4828. esc_router_info(const routerinfo_t *router)
  4829. {
  4830. static char *info=NULL;
  4831. char *esc_contact, *esc_platform;
  4832. tor_free(info);
  4833. if (!router)
  4834. return NULL; /* we're exiting; just free the memory we use */
  4835. esc_contact = esc_for_log(router->contact_info);
  4836. esc_platform = esc_for_log(router->platform);
  4837. tor_asprintf(&info, "Contact %s, Platform %s", esc_contact, esc_platform);
  4838. tor_free(esc_contact);
  4839. tor_free(esc_platform);
  4840. return info;
  4841. }
  4842. /** Helper for sorting: compare two routerinfos by their identity
  4843. * digest. */
  4844. static int
  4845. _compare_routerinfo_by_id_digest(const void **a, const void **b)
  4846. {
  4847. routerinfo_t *first = *(routerinfo_t **)a, *second = *(routerinfo_t **)b;
  4848. return fast_memcmp(first->cache_info.identity_digest,
  4849. second->cache_info.identity_digest,
  4850. DIGEST_LEN);
  4851. }
  4852. /** Sort a list of routerinfo_t in ascending order of identity digest. */
  4853. void
  4854. routers_sort_by_identity(smartlist_t *routers)
  4855. {
  4856. smartlist_sort(routers, _compare_routerinfo_by_id_digest);
  4857. }
  4858. /** A routerset specifies constraints on a set of possible routerinfos, based
  4859. * on their names, identities, or addresses. It is optimized for determining
  4860. * whether a router is a member or not, in O(1+P) time, where P is the number
  4861. * of address policy constraints. */
  4862. struct routerset_t {
  4863. /** A list of strings for the elements of the policy. Each string is either
  4864. * a nickname, a hexadecimal identity fingerprint, or an address policy. A
  4865. * router belongs to the set if its nickname OR its identity OR its address
  4866. * matches an entry here. */
  4867. smartlist_t *list;
  4868. /** A map from lowercase nicknames of routers in the set to (void*)1 */
  4869. strmap_t *names;
  4870. /** A map from identity digests routers in the set to (void*)1 */
  4871. digestmap_t *digests;
  4872. /** An address policy for routers in the set. For implementation reasons,
  4873. * a router belongs to the set if it is _rejected_ by this policy. */
  4874. smartlist_t *policies;
  4875. /** A human-readable description of what this routerset is for. Used in
  4876. * log messages. */
  4877. char *description;
  4878. /** A list of the country codes in this set. */
  4879. smartlist_t *country_names;
  4880. /** Total number of countries we knew about when we built <b>countries</b>.*/
  4881. int n_countries;
  4882. /** Bit array mapping the return value of geoip_get_country() to 1 iff the
  4883. * country is a member of this routerset. Note that we MUST call
  4884. * routerset_refresh_countries() whenever the geoip country list is
  4885. * reloaded. */
  4886. bitarray_t *countries;
  4887. };
  4888. /** Return a new empty routerset. */
  4889. routerset_t *
  4890. routerset_new(void)
  4891. {
  4892. routerset_t *result = tor_malloc_zero(sizeof(routerset_t));
  4893. result->list = smartlist_new();
  4894. result->names = strmap_new();
  4895. result->digests = digestmap_new();
  4896. result->policies = smartlist_new();
  4897. result->country_names = smartlist_new();
  4898. return result;
  4899. }
  4900. /** If <b>c</b> is a country code in the form {cc}, return a newly allocated
  4901. * string holding the "cc" part. Else, return NULL. */
  4902. static char *
  4903. routerset_get_countryname(const char *c)
  4904. {
  4905. char *country;
  4906. if (strlen(c) < 4 || c[0] !='{' || c[3] !='}')
  4907. return NULL;
  4908. country = tor_strndup(c+1, 2);
  4909. tor_strlower(country);
  4910. return country;
  4911. }
  4912. /** Update the routerset's <b>countries</b> bitarray_t. Called whenever
  4913. * the GeoIP database is reloaded.
  4914. */
  4915. void
  4916. routerset_refresh_countries(routerset_t *target)
  4917. {
  4918. int cc;
  4919. bitarray_free(target->countries);
  4920. if (!geoip_is_loaded()) {
  4921. target->countries = NULL;
  4922. target->n_countries = 0;
  4923. return;
  4924. }
  4925. target->n_countries = geoip_get_n_countries();
  4926. target->countries = bitarray_init_zero(target->n_countries);
  4927. SMARTLIST_FOREACH_BEGIN(target->country_names, const char *, country) {
  4928. cc = geoip_get_country(country);
  4929. if (cc >= 0) {
  4930. tor_assert(cc < target->n_countries);
  4931. bitarray_set(target->countries, cc);
  4932. } else {
  4933. log(LOG_WARN, LD_CONFIG, "Country code '%s' is not recognized.",
  4934. country);
  4935. }
  4936. } SMARTLIST_FOREACH_END(country);
  4937. }
  4938. /** Parse the string <b>s</b> to create a set of routerset entries, and add
  4939. * them to <b>target</b>. In log messages, refer to the string as
  4940. * <b>description</b>. Return 0 on success, -1 on failure.
  4941. *
  4942. * Three kinds of elements are allowed in routersets: nicknames, IP address
  4943. * patterns, and fingerprints. They may be surrounded by optional space, and
  4944. * must be separated by commas.
  4945. */
  4946. int
  4947. routerset_parse(routerset_t *target, const char *s, const char *description)
  4948. {
  4949. int r = 0;
  4950. int added_countries = 0;
  4951. char *countryname;
  4952. smartlist_t *list = smartlist_new();
  4953. smartlist_split_string(list, s, ",",
  4954. SPLIT_SKIP_SPACE | SPLIT_IGNORE_BLANK, 0);
  4955. SMARTLIST_FOREACH_BEGIN(list, char *, nick) {
  4956. addr_policy_t *p;
  4957. if (is_legal_hexdigest(nick)) {
  4958. char d[DIGEST_LEN];
  4959. if (*nick == '$')
  4960. ++nick;
  4961. log_debug(LD_CONFIG, "Adding identity %s to %s", nick, description);
  4962. base16_decode(d, sizeof(d), nick, HEX_DIGEST_LEN);
  4963. digestmap_set(target->digests, d, (void*)1);
  4964. } else if (is_legal_nickname(nick)) {
  4965. log_debug(LD_CONFIG, "Adding nickname %s to %s", nick, description);
  4966. strmap_set_lc(target->names, nick, (void*)1);
  4967. } else if ((countryname = routerset_get_countryname(nick)) != NULL) {
  4968. log_debug(LD_CONFIG, "Adding country %s to %s", nick,
  4969. description);
  4970. smartlist_add(target->country_names, countryname);
  4971. added_countries = 1;
  4972. } else if ((strchr(nick,'.') || strchr(nick, '*')) &&
  4973. (p = router_parse_addr_policy_item_from_string(
  4974. nick, ADDR_POLICY_REJECT))) {
  4975. log_debug(LD_CONFIG, "Adding address %s to %s", nick, description);
  4976. smartlist_add(target->policies, p);
  4977. } else {
  4978. log_warn(LD_CONFIG, "Entry '%s' in %s is misformed.", nick,
  4979. description);
  4980. r = -1;
  4981. tor_free(nick);
  4982. SMARTLIST_DEL_CURRENT(list, nick);
  4983. }
  4984. } SMARTLIST_FOREACH_END(nick);
  4985. smartlist_add_all(target->list, list);
  4986. smartlist_free(list);
  4987. if (added_countries)
  4988. routerset_refresh_countries(target);
  4989. return r;
  4990. }
  4991. /** Called when we change a node set, or when we reload the geoip list:
  4992. * recompute all country info in all configuration node sets and in the
  4993. * routerlist. */
  4994. void
  4995. refresh_all_country_info(void)
  4996. {
  4997. const or_options_t *options = get_options();
  4998. if (options->EntryNodes)
  4999. routerset_refresh_countries(options->EntryNodes);
  5000. if (options->ExitNodes)
  5001. routerset_refresh_countries(options->ExitNodes);
  5002. if (options->ExcludeNodes)
  5003. routerset_refresh_countries(options->ExcludeNodes);
  5004. if (options->ExcludeExitNodes)
  5005. routerset_refresh_countries(options->ExcludeExitNodes);
  5006. if (options->_ExcludeExitNodesUnion)
  5007. routerset_refresh_countries(options->_ExcludeExitNodesUnion);
  5008. nodelist_refresh_countries();
  5009. }
  5010. /** Add all members of the set <b>source</b> to <b>target</b>. */
  5011. void
  5012. routerset_union(routerset_t *target, const routerset_t *source)
  5013. {
  5014. char *s;
  5015. tor_assert(target);
  5016. if (!source || !source->list)
  5017. return;
  5018. s = routerset_to_string(source);
  5019. routerset_parse(target, s, "other routerset");
  5020. tor_free(s);
  5021. }
  5022. /** Return true iff <b>set</b> lists only nicknames and digests, and includes
  5023. * no IP ranges or countries. */
  5024. int
  5025. routerset_is_list(const routerset_t *set)
  5026. {
  5027. return smartlist_len(set->country_names) == 0 &&
  5028. smartlist_len(set->policies) == 0;
  5029. }
  5030. /** Return true iff we need a GeoIP IP-to-country database to make sense of
  5031. * <b>set</b>. */
  5032. int
  5033. routerset_needs_geoip(const routerset_t *set)
  5034. {
  5035. return set && smartlist_len(set->country_names);
  5036. }
  5037. /** Return true iff there are no entries in <b>set</b>. */
  5038. int
  5039. routerset_is_empty(const routerset_t *set)
  5040. {
  5041. return !set || smartlist_len(set->list) == 0;
  5042. }
  5043. /** Helper. Return true iff <b>set</b> contains a router based on the other
  5044. * provided fields. Return higher values for more specific subentries: a
  5045. * single router is more specific than an address range of routers, which is
  5046. * more specific in turn than a country code.
  5047. *
  5048. * (If country is -1, then we take the country
  5049. * from addr.) */
  5050. static int
  5051. routerset_contains(const routerset_t *set, const tor_addr_t *addr,
  5052. uint16_t orport,
  5053. const char *nickname, const char *id_digest,
  5054. country_t country)
  5055. {
  5056. if (!set || !set->list)
  5057. return 0;
  5058. if (nickname && strmap_get_lc(set->names, nickname))
  5059. return 4;
  5060. if (id_digest && digestmap_get(set->digests, id_digest))
  5061. return 4;
  5062. if (addr && compare_tor_addr_to_addr_policy(addr, orport, set->policies)
  5063. == ADDR_POLICY_REJECTED)
  5064. return 3;
  5065. if (set->countries) {
  5066. if (country < 0 && addr)
  5067. country = geoip_get_country_by_ip(tor_addr_to_ipv4h(addr));
  5068. if (country >= 0 && country < set->n_countries &&
  5069. bitarray_is_set(set->countries, country))
  5070. return 2;
  5071. }
  5072. return 0;
  5073. }
  5074. /** Return true iff we can tell that <b>ei</b> is a member of <b>set</b>. */
  5075. int
  5076. routerset_contains_extendinfo(const routerset_t *set, const extend_info_t *ei)
  5077. {
  5078. return routerset_contains(set,
  5079. &ei->addr,
  5080. ei->port,
  5081. ei->nickname,
  5082. ei->identity_digest,
  5083. -1 /*country*/);
  5084. }
  5085. /** Return true iff <b>ri</b> is in <b>set</b>. If country is <b>-1</b>, we
  5086. * look up the country. */
  5087. int
  5088. routerset_contains_router(const routerset_t *set, const routerinfo_t *ri,
  5089. country_t country)
  5090. {
  5091. tor_addr_t addr;
  5092. tor_addr_from_ipv4h(&addr, ri->addr);
  5093. return routerset_contains(set,
  5094. &addr,
  5095. ri->or_port,
  5096. ri->nickname,
  5097. ri->cache_info.identity_digest,
  5098. country);
  5099. }
  5100. /** Return true iff <b>rs</b> is in <b>set</b>. If country is <b>-1</b>, we
  5101. * look up the country. */
  5102. int
  5103. routerset_contains_routerstatus(const routerset_t *set,
  5104. const routerstatus_t *rs,
  5105. country_t country)
  5106. {
  5107. tor_addr_t addr;
  5108. tor_addr_from_ipv4h(&addr, rs->addr);
  5109. return routerset_contains(set,
  5110. &addr,
  5111. rs->or_port,
  5112. rs->nickname,
  5113. rs->identity_digest,
  5114. country);
  5115. }
  5116. /** Return true iff <b>node</b> is in <b>set</b>. */
  5117. int
  5118. routerset_contains_node(const routerset_t *set, const node_t *node)
  5119. {
  5120. if (node->rs)
  5121. return routerset_contains_routerstatus(set, node->rs, node->country);
  5122. else if (node->ri)
  5123. return routerset_contains_router(set, node->ri, node->country);
  5124. else
  5125. return 0;
  5126. }
  5127. /** Add every known node_t that is a member of <b>routerset</b> to
  5128. * <b>out</b>, but never add any that are part of <b>excludeset</b>.
  5129. * If <b>running_only</b>, only add the running ones. */
  5130. void
  5131. routerset_get_all_nodes(smartlist_t *out, const routerset_t *routerset,
  5132. const routerset_t *excludeset, int running_only)
  5133. { /* XXXX MOVE */
  5134. tor_assert(out);
  5135. if (!routerset || !routerset->list)
  5136. return;
  5137. if (routerset_is_list(routerset)) {
  5138. /* No routers are specified by type; all are given by name or digest.
  5139. * we can do a lookup in O(len(routerset)). */
  5140. SMARTLIST_FOREACH(routerset->list, const char *, name, {
  5141. const node_t *node = node_get_by_nickname(name, 1);
  5142. if (node) {
  5143. if (!running_only || node->is_running)
  5144. if (!routerset_contains_node(excludeset, node))
  5145. smartlist_add(out, (void*)node);
  5146. }
  5147. });
  5148. } else {
  5149. /* We need to iterate over the routerlist to get all the ones of the
  5150. * right kind. */
  5151. smartlist_t *nodes = nodelist_get_list();
  5152. SMARTLIST_FOREACH(nodes, const node_t *, node, {
  5153. if (running_only && !node->is_running)
  5154. continue;
  5155. if (routerset_contains_node(routerset, node) &&
  5156. !routerset_contains_node(excludeset, node))
  5157. smartlist_add(out, (void*)node);
  5158. });
  5159. }
  5160. }
  5161. #if 0
  5162. /** Add to <b>target</b> every node_t from <b>source</b> except:
  5163. *
  5164. * 1) Don't add it if <b>include</b> is non-empty and the relay isn't in
  5165. * <b>include</b>; and
  5166. * 2) Don't add it if <b>exclude</b> is non-empty and the relay is
  5167. * excluded in a more specific fashion by <b>exclude</b>.
  5168. * 3) If <b>running_only</b>, don't add non-running routers.
  5169. */
  5170. void
  5171. routersets_get_node_disjunction(smartlist_t *target,
  5172. const smartlist_t *source,
  5173. const routerset_t *include,
  5174. const routerset_t *exclude, int running_only)
  5175. {
  5176. SMARTLIST_FOREACH(source, const node_t *, node, {
  5177. int include_result;
  5178. if (running_only && !node->is_running)
  5179. continue;
  5180. if (!routerset_is_empty(include))
  5181. include_result = routerset_contains_node(include, node);
  5182. else
  5183. include_result = 1;
  5184. if (include_result) {
  5185. int exclude_result = routerset_contains_node(exclude, node);
  5186. if (include_result >= exclude_result)
  5187. smartlist_add(target, (void*)node);
  5188. }
  5189. });
  5190. }
  5191. #endif
  5192. /** Remove every node_t from <b>lst</b> that is in <b>routerset</b>. */
  5193. void
  5194. routerset_subtract_nodes(smartlist_t *lst, const routerset_t *routerset)
  5195. { /*XXXX MOVE ? */
  5196. tor_assert(lst);
  5197. if (!routerset)
  5198. return;
  5199. SMARTLIST_FOREACH(lst, const node_t *, node, {
  5200. if (routerset_contains_node(routerset, node)) {
  5201. //log_debug(LD_DIR, "Subtracting %s",r->nickname);
  5202. SMARTLIST_DEL_CURRENT(lst, node);
  5203. }
  5204. });
  5205. }
  5206. /** Return a new string that when parsed by routerset_parse_string() will
  5207. * yield <b>set</b>. */
  5208. char *
  5209. routerset_to_string(const routerset_t *set)
  5210. {
  5211. if (!set || !set->list)
  5212. return tor_strdup("");
  5213. return smartlist_join_strings(set->list, ",", 0, NULL);
  5214. }
  5215. /** Helper: return true iff old and new are both NULL, or both non-NULL
  5216. * equal routersets. */
  5217. int
  5218. routerset_equal(const routerset_t *old, const routerset_t *new)
  5219. {
  5220. if (routerset_is_empty(old) && routerset_is_empty(new)) {
  5221. /* Two empty sets are equal */
  5222. return 1;
  5223. } else if (routerset_is_empty(old) || routerset_is_empty(new)) {
  5224. /* An empty set is equal to nothing else. */
  5225. return 0;
  5226. }
  5227. tor_assert(old != NULL);
  5228. tor_assert(new != NULL);
  5229. if (smartlist_len(old->list) != smartlist_len(new->list))
  5230. return 0;
  5231. SMARTLIST_FOREACH(old->list, const char *, cp1, {
  5232. const char *cp2 = smartlist_get(new->list, cp1_sl_idx);
  5233. if (strcmp(cp1, cp2))
  5234. return 0;
  5235. });
  5236. return 1;
  5237. }
  5238. /** Free all storage held in <b>routerset</b>. */
  5239. void
  5240. routerset_free(routerset_t *routerset)
  5241. {
  5242. if (!routerset)
  5243. return;
  5244. SMARTLIST_FOREACH(routerset->list, char *, cp, tor_free(cp));
  5245. smartlist_free(routerset->list);
  5246. SMARTLIST_FOREACH(routerset->policies, addr_policy_t *, p,
  5247. addr_policy_free(p));
  5248. smartlist_free(routerset->policies);
  5249. SMARTLIST_FOREACH(routerset->country_names, char *, cp, tor_free(cp));
  5250. smartlist_free(routerset->country_names);
  5251. strmap_free(routerset->names, NULL);
  5252. digestmap_free(routerset->digests, NULL);
  5253. bitarray_free(routerset->countries);
  5254. tor_free(routerset);
  5255. }
  5256. /** Refresh the country code of <b>ri</b>. This function MUST be called on
  5257. * each router when the GeoIP database is reloaded, and on all new routers. */
  5258. void
  5259. node_set_country(node_t *node)
  5260. {
  5261. if (node->rs)
  5262. node->country = geoip_get_country_by_ip(node->rs->addr);
  5263. else if (node->ri)
  5264. node->country = geoip_get_country_by_ip(node->ri->addr);
  5265. else
  5266. node->country = -1;
  5267. }
  5268. /** Set the country code of all routers in the routerlist. */
  5269. void
  5270. nodelist_refresh_countries(void) /* MOVE */
  5271. {
  5272. smartlist_t *nodes = nodelist_get_list();
  5273. SMARTLIST_FOREACH(nodes, node_t *, node,
  5274. node_set_country(node));
  5275. }
  5276. /** Determine the routers that are responsible for <b>id</b> (binary) and
  5277. * add pointers to those routers' routerstatus_t to <b>responsible_dirs</b>.
  5278. * Return -1 if we're returning an empty smartlist, else return 0.
  5279. */
  5280. int
  5281. hid_serv_get_responsible_directories(smartlist_t *responsible_dirs,
  5282. const char *id)
  5283. {
  5284. int start, found, n_added = 0, i;
  5285. networkstatus_t *c = networkstatus_get_latest_consensus();
  5286. if (!c || !smartlist_len(c->routerstatus_list)) {
  5287. log_warn(LD_REND, "We don't have a consensus, so we can't perform v2 "
  5288. "rendezvous operations.");
  5289. return -1;
  5290. }
  5291. tor_assert(id);
  5292. start = networkstatus_vote_find_entry_idx(c, id, &found);
  5293. if (start == smartlist_len(c->routerstatus_list)) start = 0;
  5294. i = start;
  5295. do {
  5296. routerstatus_t *r = smartlist_get(c->routerstatus_list, i);
  5297. if (r->is_hs_dir) {
  5298. smartlist_add(responsible_dirs, r);
  5299. if (++n_added == REND_NUMBER_OF_CONSECUTIVE_REPLICAS)
  5300. return 0;
  5301. }
  5302. if (++i == smartlist_len(c->routerstatus_list))
  5303. i = 0;
  5304. } while (i != start);
  5305. /* Even though we don't have the desired number of hidden service
  5306. * directories, be happy if we got any. */
  5307. return smartlist_len(responsible_dirs) ? 0 : -1;
  5308. }
  5309. /** Return true if this node is currently acting as hidden service
  5310. * directory, false otherwise. */
  5311. int
  5312. hid_serv_acting_as_directory(void)
  5313. {
  5314. const routerinfo_t *me = router_get_my_routerinfo();
  5315. if (!me)
  5316. return 0;
  5317. if (!get_options()->HidServDirectoryV2) {
  5318. log_info(LD_REND, "We are not acting as hidden service directory, "
  5319. "because we have not been configured as such.");
  5320. return 0;
  5321. }
  5322. return 1;
  5323. }
  5324. /** Return true if this node is responsible for storing the descriptor ID
  5325. * in <b>query</b> and false otherwise. */
  5326. int
  5327. hid_serv_responsible_for_desc_id(const char *query)
  5328. {
  5329. const routerinfo_t *me;
  5330. routerstatus_t *last_rs;
  5331. const char *my_id, *last_id;
  5332. int result;
  5333. smartlist_t *responsible;
  5334. if (!hid_serv_acting_as_directory())
  5335. return 0;
  5336. if (!(me = router_get_my_routerinfo()))
  5337. return 0; /* This is redundant, but let's be paranoid. */
  5338. my_id = me->cache_info.identity_digest;
  5339. responsible = smartlist_new();
  5340. if (hid_serv_get_responsible_directories(responsible, query) < 0) {
  5341. smartlist_free(responsible);
  5342. return 0;
  5343. }
  5344. last_rs = smartlist_get(responsible, smartlist_len(responsible)-1);
  5345. last_id = last_rs->identity_digest;
  5346. result = rend_id_is_in_interval(my_id, query, last_id);
  5347. smartlist_free(responsible);
  5348. return result;
  5349. }