routerlist.c 200 KB

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