circuitbuild.c 198 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623162416251626162716281629163016311632163316341635163616371638163916401641164216431644164516461647164816491650165116521653165416551656165716581659166016611662166316641665166616671668166916701671167216731674167516761677167816791680168116821683168416851686168716881689169016911692169316941695169616971698169917001701170217031704170517061707170817091710171117121713171417151716171717181719172017211722172317241725172617271728172917301731173217331734173517361737173817391740174117421743174417451746174717481749175017511752175317541755175617571758175917601761176217631764176517661767176817691770177117721773177417751776177717781779178017811782178317841785178617871788178917901791179217931794179517961797179817991800180118021803180418051806180718081809181018111812181318141815181618171818181918201821182218231824182518261827182818291830183118321833183418351836183718381839184018411842184318441845184618471848184918501851185218531854185518561857185818591860186118621863186418651866186718681869187018711872187318741875187618771878187918801881188218831884188518861887188818891890189118921893189418951896189718981899190019011902190319041905190619071908190919101911191219131914191519161917191819191920192119221923192419251926192719281929193019311932193319341935193619371938193919401941194219431944194519461947194819491950195119521953195419551956195719581959196019611962196319641965196619671968196919701971197219731974197519761977197819791980198119821983198419851986198719881989199019911992199319941995199619971998199920002001200220032004200520062007200820092010201120122013201420152016201720182019202020212022202320242025202620272028202920302031203220332034203520362037203820392040204120422043204420452046204720482049205020512052205320542055205620572058205920602061206220632064206520662067206820692070207120722073207420752076207720782079208020812082208320842085208620872088208920902091209220932094209520962097209820992100210121022103210421052106210721082109211021112112211321142115211621172118211921202121212221232124212521262127212821292130213121322133213421352136213721382139214021412142214321442145214621472148214921502151215221532154215521562157215821592160216121622163216421652166216721682169217021712172217321742175217621772178217921802181218221832184218521862187218821892190219121922193219421952196219721982199220022012202220322042205220622072208220922102211221222132214221522162217221822192220222122222223222422252226222722282229223022312232223322342235223622372238223922402241224222432244224522462247224822492250225122522253225422552256225722582259226022612262226322642265226622672268226922702271227222732274227522762277227822792280228122822283228422852286228722882289229022912292229322942295229622972298229923002301230223032304230523062307230823092310231123122313231423152316231723182319232023212322232323242325232623272328232923302331233223332334233523362337233823392340234123422343234423452346234723482349235023512352235323542355235623572358235923602361236223632364236523662367236823692370237123722373237423752376237723782379238023812382238323842385238623872388238923902391239223932394239523962397239823992400240124022403240424052406240724082409241024112412241324142415241624172418241924202421242224232424242524262427242824292430243124322433243424352436243724382439244024412442244324442445244624472448244924502451245224532454245524562457245824592460246124622463246424652466246724682469247024712472247324742475247624772478247924802481248224832484248524862487248824892490249124922493249424952496249724982499250025012502250325042505250625072508250925102511251225132514251525162517251825192520252125222523252425252526252725282529253025312532253325342535253625372538253925402541254225432544254525462547254825492550255125522553255425552556255725582559256025612562256325642565256625672568256925702571257225732574257525762577257825792580258125822583258425852586258725882589259025912592259325942595259625972598259926002601260226032604260526062607260826092610261126122613261426152616261726182619262026212622262326242625262626272628262926302631263226332634263526362637263826392640264126422643264426452646264726482649265026512652265326542655265626572658265926602661266226632664266526662667266826692670267126722673267426752676267726782679268026812682268326842685268626872688268926902691269226932694269526962697269826992700270127022703270427052706270727082709271027112712271327142715271627172718271927202721272227232724272527262727272827292730273127322733273427352736273727382739274027412742274327442745274627472748274927502751275227532754275527562757275827592760276127622763276427652766276727682769277027712772277327742775277627772778277927802781278227832784278527862787278827892790279127922793279427952796279727982799280028012802280328042805280628072808280928102811281228132814281528162817281828192820282128222823282428252826282728282829283028312832283328342835283628372838283928402841284228432844284528462847284828492850285128522853285428552856285728582859286028612862286328642865286628672868286928702871287228732874287528762877287828792880288128822883288428852886288728882889289028912892289328942895289628972898289929002901290229032904290529062907290829092910291129122913291429152916291729182919292029212922292329242925292629272928292929302931293229332934293529362937293829392940294129422943294429452946294729482949295029512952295329542955295629572958295929602961296229632964296529662967296829692970297129722973297429752976297729782979298029812982298329842985298629872988298929902991299229932994299529962997299829993000300130023003300430053006300730083009301030113012301330143015301630173018301930203021302230233024302530263027302830293030303130323033303430353036303730383039304030413042304330443045304630473048304930503051305230533054305530563057305830593060306130623063306430653066306730683069307030713072307330743075307630773078307930803081308230833084308530863087308830893090309130923093309430953096309730983099310031013102310331043105310631073108310931103111311231133114311531163117311831193120312131223123312431253126312731283129313031313132313331343135313631373138313931403141314231433144314531463147314831493150315131523153315431553156315731583159316031613162316331643165316631673168316931703171317231733174317531763177317831793180318131823183318431853186318731883189319031913192319331943195319631973198319932003201320232033204320532063207320832093210321132123213321432153216321732183219322032213222322332243225322632273228322932303231323232333234323532363237323832393240324132423243324432453246324732483249325032513252325332543255325632573258325932603261326232633264326532663267326832693270327132723273327432753276327732783279328032813282328332843285328632873288328932903291329232933294329532963297329832993300330133023303330433053306330733083309331033113312331333143315331633173318331933203321332233233324332533263327332833293330333133323333333433353336333733383339334033413342334333443345334633473348334933503351335233533354335533563357335833593360336133623363336433653366336733683369337033713372337333743375337633773378337933803381338233833384338533863387338833893390339133923393339433953396339733983399340034013402340334043405340634073408340934103411341234133414341534163417341834193420342134223423342434253426342734283429343034313432343334343435343634373438343934403441344234433444344534463447344834493450345134523453345434553456345734583459346034613462346334643465346634673468346934703471347234733474347534763477347834793480348134823483348434853486348734883489349034913492349334943495349634973498349935003501350235033504350535063507350835093510351135123513351435153516351735183519352035213522352335243525352635273528352935303531353235333534353535363537353835393540354135423543354435453546354735483549355035513552355335543555355635573558355935603561356235633564356535663567356835693570357135723573357435753576357735783579358035813582358335843585358635873588358935903591359235933594359535963597359835993600360136023603360436053606360736083609361036113612361336143615361636173618361936203621362236233624362536263627362836293630363136323633363436353636363736383639364036413642364336443645364636473648364936503651365236533654365536563657365836593660366136623663366436653666366736683669367036713672367336743675367636773678367936803681368236833684368536863687368836893690369136923693369436953696369736983699370037013702370337043705370637073708370937103711371237133714371537163717371837193720372137223723372437253726372737283729373037313732373337343735373637373738373937403741374237433744374537463747374837493750375137523753375437553756375737583759376037613762376337643765376637673768376937703771377237733774377537763777377837793780378137823783378437853786378737883789379037913792379337943795379637973798379938003801380238033804380538063807380838093810381138123813381438153816381738183819382038213822382338243825382638273828382938303831383238333834383538363837383838393840384138423843384438453846384738483849385038513852385338543855385638573858385938603861386238633864386538663867386838693870387138723873387438753876387738783879388038813882388338843885388638873888388938903891389238933894389538963897389838993900390139023903390439053906390739083909391039113912391339143915391639173918391939203921392239233924392539263927392839293930393139323933393439353936393739383939394039413942394339443945394639473948394939503951395239533954395539563957395839593960396139623963396439653966396739683969397039713972397339743975397639773978397939803981398239833984398539863987398839893990399139923993399439953996399739983999400040014002400340044005400640074008400940104011401240134014401540164017401840194020402140224023402440254026402740284029403040314032403340344035403640374038403940404041404240434044404540464047404840494050405140524053405440554056405740584059406040614062406340644065406640674068406940704071407240734074407540764077407840794080408140824083408440854086408740884089409040914092409340944095409640974098409941004101410241034104410541064107410841094110411141124113411441154116411741184119412041214122412341244125412641274128412941304131413241334134413541364137413841394140414141424143414441454146414741484149415041514152415341544155415641574158415941604161416241634164416541664167416841694170417141724173417441754176417741784179418041814182418341844185418641874188418941904191419241934194419541964197419841994200420142024203420442054206420742084209421042114212421342144215421642174218421942204221422242234224422542264227422842294230423142324233423442354236423742384239424042414242424342444245424642474248424942504251425242534254425542564257425842594260426142624263426442654266426742684269427042714272427342744275427642774278427942804281428242834284428542864287428842894290429142924293429442954296429742984299430043014302430343044305430643074308430943104311431243134314431543164317431843194320432143224323432443254326432743284329433043314332433343344335433643374338433943404341434243434344434543464347434843494350435143524353435443554356435743584359436043614362436343644365436643674368436943704371437243734374437543764377437843794380438143824383438443854386438743884389439043914392439343944395439643974398439944004401440244034404440544064407440844094410441144124413441444154416441744184419442044214422442344244425442644274428442944304431443244334434443544364437443844394440444144424443444444454446444744484449445044514452445344544455445644574458445944604461446244634464446544664467446844694470447144724473447444754476447744784479448044814482448344844485448644874488448944904491449244934494449544964497449844994500450145024503450445054506450745084509451045114512451345144515451645174518451945204521452245234524452545264527452845294530453145324533453445354536453745384539454045414542454345444545454645474548454945504551455245534554455545564557455845594560456145624563456445654566456745684569457045714572457345744575457645774578457945804581458245834584458545864587458845894590459145924593459445954596459745984599460046014602460346044605460646074608460946104611461246134614461546164617461846194620462146224623462446254626462746284629463046314632463346344635463646374638463946404641464246434644464546464647464846494650465146524653465446554656465746584659466046614662466346644665466646674668466946704671467246734674467546764677467846794680468146824683468446854686468746884689469046914692469346944695469646974698469947004701470247034704470547064707470847094710471147124713471447154716471747184719472047214722472347244725472647274728472947304731473247334734473547364737473847394740474147424743474447454746474747484749475047514752475347544755475647574758475947604761476247634764476547664767476847694770477147724773477447754776477747784779478047814782478347844785478647874788478947904791479247934794479547964797479847994800480148024803480448054806480748084809481048114812481348144815481648174818481948204821482248234824482548264827482848294830483148324833483448354836483748384839484048414842484348444845484648474848484948504851485248534854485548564857485848594860486148624863486448654866486748684869487048714872487348744875487648774878487948804881488248834884488548864887488848894890489148924893489448954896489748984899490049014902490349044905490649074908490949104911491249134914491549164917491849194920492149224923492449254926492749284929493049314932493349344935493649374938493949404941494249434944494549464947494849494950495149524953495449554956495749584959496049614962496349644965496649674968496949704971497249734974497549764977497849794980498149824983498449854986498749884989499049914992499349944995499649974998499950005001500250035004500550065007500850095010501150125013501450155016501750185019502050215022502350245025502650275028502950305031503250335034503550365037503850395040504150425043504450455046504750485049505050515052505350545055505650575058505950605061506250635064506550665067506850695070507150725073507450755076507750785079508050815082508350845085508650875088508950905091509250935094509550965097509850995100510151025103510451055106510751085109511051115112511351145115511651175118511951205121512251235124512551265127512851295130513151325133513451355136513751385139514051415142514351445145514651475148514951505151515251535154515551565157515851595160516151625163516451655166516751685169517051715172517351745175517651775178517951805181518251835184518551865187518851895190519151925193519451955196519751985199520052015202520352045205520652075208520952105211521252135214521552165217521852195220522152225223522452255226522752285229523052315232523352345235523652375238523952405241524252435244524552465247524852495250525152525253525452555256525752585259526052615262526352645265526652675268526952705271527252735274527552765277527852795280528152825283528452855286528752885289529052915292529352945295529652975298529953005301530253035304530553065307530853095310531153125313531453155316531753185319532053215322532353245325532653275328532953305331533253335334533553365337533853395340534153425343534453455346534753485349535053515352535353545355535653575358535953605361536253635364536553665367536853695370537153725373537453755376537753785379538053815382538353845385538653875388538953905391539253935394539553965397539853995400540154025403540454055406540754085409541054115412541354145415541654175418541954205421542254235424542554265427542854295430543154325433543454355436543754385439544054415442544354445445544654475448544954505451545254535454545554565457545854595460546154625463546454655466546754685469547054715472547354745475547654775478547954805481548254835484548554865487548854895490549154925493549454955496549754985499550055015502550355045505550655075508550955105511551255135514551555165517551855195520552155225523552455255526552755285529553055315532553355345535553655375538553955405541554255435544554555465547554855495550555155525553555455555556555755585559556055615562556355645565556655675568556955705571557255735574557555765577557855795580558155825583558455855586558755885589559055915592559355945595559655975598559956005601560256035604560556065607560856095610561156125613561456155616561756185619562056215622562356245625562656275628562956305631563256335634563556365637563856395640564156425643564456455646564756485649565056515652565356545655565656575658565956605661566256635664566556665667566856695670567156725673567456755676567756785679568056815682568356845685568656875688568956905691569256935694569556965697569856995700570157025703570457055706570757085709571057115712571357145715571657175718571957205721572257235724572557265727572857295730573157325733573457355736573757385739574057415742574357445745574657475748574957505751575257535754575557565757575857595760576157625763576457655766576757685769577057715772577357745775577657775778577957805781578257835784578557865787578857895790579157925793579457955796579757985799580058015802580358045805580658075808580958105811581258135814581558165817581858195820582158225823582458255826582758285829583058315832583358345835583658375838583958405841584258435844584558465847584858495850585158525853585458555856585758585859586058615862586358645865586658675868586958705871587258735874587558765877587858795880588158825883588458855886588758885889589058915892589358945895589658975898589959005901
  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-2012, The Tor Project, Inc. */
  5. /* See LICENSE for licensing information */
  6. /**
  7. * \file circuitbuild.c
  8. * \brief The actual details of building circuits.
  9. **/
  10. #define CIRCUIT_PRIVATE
  11. #include "or.h"
  12. #include "channel.h"
  13. #include "circuitbuild.h"
  14. #include "circuitlist.h"
  15. #include "circuituse.h"
  16. #include "command.h"
  17. #include "config.h"
  18. #include "confparse.h"
  19. #include "connection.h"
  20. #include "connection_edge.h"
  21. #include "connection_or.h"
  22. #include "control.h"
  23. #include "directory.h"
  24. #include "main.h"
  25. #include "networkstatus.h"
  26. #include "nodelist.h"
  27. #include "onion.h"
  28. #include "policies.h"
  29. #include "transports.h"
  30. #include "relay.h"
  31. #include "rephist.h"
  32. #include "router.h"
  33. #include "routerlist.h"
  34. #include "routerparse.h"
  35. #include "routerset.h"
  36. #include "statefile.h"
  37. #include "crypto.h"
  38. #undef log
  39. #include <math.h>
  40. #ifndef MIN
  41. #define MIN(a,b) ((a)<(b)?(a):(b))
  42. #endif
  43. #define CBT_BIN_TO_MS(bin) ((bin)*CBT_BIN_WIDTH + (CBT_BIN_WIDTH/2))
  44. /********* START VARIABLES **********/
  45. /** Global list of circuit build times */
  46. // XXXX: Add this as a member for entry_guard_t instead of global?
  47. // Then we could do per-guard statistics, as guards are likely to
  48. // vary in their own latency. The downside of this is that guards
  49. // can change frequently, so we'd be building a lot more circuits
  50. // most likely.
  51. /* XXXX024 Make this static; add accessor functions. */
  52. circuit_build_times_t circ_times;
  53. /** A global list of all circuits at this hop. */
  54. extern circuit_t *global_circuitlist;
  55. /** An entry_guard_t represents our information about a chosen long-term
  56. * first hop, known as a "helper" node in the literature. We can't just
  57. * use a node_t, since we want to remember these even when we
  58. * don't have any directory info. */
  59. typedef struct {
  60. char nickname[MAX_NICKNAME_LEN+1];
  61. char identity[DIGEST_LEN];
  62. time_t chosen_on_date; /**< Approximately when was this guard added?
  63. * "0" if we don't know. */
  64. char *chosen_by_version; /**< What tor version added this guard? NULL
  65. * if we don't know. */
  66. unsigned int made_contact : 1; /**< 0 if we have never connected to this
  67. * router, 1 if we have. */
  68. unsigned int can_retry : 1; /**< Should we retry connecting to this entry,
  69. * in spite of having it marked as unreachable?*/
  70. unsigned int path_bias_notice : 1; /**< Did we alert the user about path bias
  71. * for this node already? */
  72. unsigned int path_bias_disabled : 1; /**< Have we disabled this node because
  73. * of path bias issues? */
  74. time_t bad_since; /**< 0 if this guard is currently usable, or the time at
  75. * which it was observed to become (according to the
  76. * directory or the user configuration) unusable. */
  77. time_t unreachable_since; /**< 0 if we can connect to this guard, or the
  78. * time at which we first noticed we couldn't
  79. * connect to it. */
  80. time_t last_attempted; /**< 0 if we can connect to this guard, or the time
  81. * at which we last failed to connect to it. */
  82. unsigned first_hops; /**< Number of first hops this guard has completed */
  83. unsigned circuit_successes; /**< Number of successfully built circuits using
  84. * this guard as first hop. */
  85. } entry_guard_t;
  86. /** Information about a configured bridge. Currently this just matches the
  87. * ones in the torrc file, but one day we may be able to learn about new
  88. * bridges on our own, and remember them in the state file. */
  89. typedef struct {
  90. /** Address of the bridge. */
  91. tor_addr_t addr;
  92. /** TLS port for the bridge. */
  93. uint16_t port;
  94. /** Boolean: We are re-parsing our bridge list, and we are going to remove
  95. * this one if we don't find it in the list of configured bridges. */
  96. unsigned marked_for_removal : 1;
  97. /** Expected identity digest, or all zero bytes if we don't know what the
  98. * digest should be. */
  99. char identity[DIGEST_LEN];
  100. /** Name of pluggable transport protocol taken from its config line. */
  101. char *transport_name;
  102. /** When should we next try to fetch a descriptor for this bridge? */
  103. download_status_t fetch_status;
  104. } bridge_info_t;
  105. /** A list of our chosen entry guards. */
  106. static smartlist_t *entry_guards = NULL;
  107. /** A value of 1 means that the entry_guards list has changed
  108. * and those changes need to be flushed to disk. */
  109. static int entry_guards_dirty = 0;
  110. /** If set, we're running the unit tests: we should avoid clobbering
  111. * our state file or accessing get_options() or get_or_state() */
  112. static int unit_tests = 0;
  113. /********* END VARIABLES ************/
  114. static channel_t * channel_connect_for_circuit(const tor_addr_t *addr,
  115. uint16_t port,
  116. const char *id_digest);
  117. static int circuit_deliver_create_cell(circuit_t *circ,
  118. uint8_t cell_type, const char *payload);
  119. static int onion_pick_cpath_exit(origin_circuit_t *circ, extend_info_t *exit);
  120. static crypt_path_t *onion_next_hop_in_cpath(crypt_path_t *cpath);
  121. static int onion_extend_cpath(origin_circuit_t *circ);
  122. static int count_acceptable_nodes(smartlist_t *routers);
  123. static int onion_append_hop(crypt_path_t **head_ptr, extend_info_t *choice);
  124. static void entry_guards_changed(void);
  125. static entry_guard_t *entry_guard_get_by_id_digest(const char *digest);
  126. static void bridge_free(bridge_info_t *bridge);
  127. static int entry_guard_inc_first_hop_count(entry_guard_t *guard);
  128. static void pathbias_count_success(origin_circuit_t *circ);
  129. /** This function tries to get a channel to the specified endpoint,
  130. * and then calls command_setup_channel() to give it the right
  131. * callbacks.
  132. */
  133. static channel_t *
  134. channel_connect_for_circuit(const tor_addr_t *addr, uint16_t port,
  135. const char *id_digest)
  136. {
  137. channel_t *chan;
  138. chan = channel_connect(addr, port, id_digest);
  139. if (chan) command_setup_channel(chan);
  140. return chan;
  141. }
  142. /**
  143. * This function decides if CBT learning should be disabled. It returns
  144. * true if one or more of the following four conditions are met:
  145. *
  146. * 1. If the cbtdisabled consensus parameter is set.
  147. * 2. If the torrc option LearnCircuitBuildTimeout is false.
  148. * 3. If we are a directory authority
  149. * 4. If we fail to write circuit build time history to our state file.
  150. */
  151. static int
  152. circuit_build_times_disabled(void)
  153. {
  154. if (unit_tests) {
  155. return 0;
  156. } else {
  157. int consensus_disabled = networkstatus_get_param(NULL, "cbtdisabled",
  158. 0, 0, 1);
  159. int config_disabled = !get_options()->LearnCircuitBuildTimeout;
  160. int dirauth_disabled = get_options()->AuthoritativeDir;
  161. int state_disabled = did_last_state_file_write_fail() ? 1 : 0;
  162. if (consensus_disabled || config_disabled || dirauth_disabled ||
  163. state_disabled) {
  164. log_debug(LD_CIRC,
  165. "CircuitBuildTime learning is disabled. "
  166. "Consensus=%d, Config=%d, AuthDir=%d, StateFile=%d",
  167. consensus_disabled, config_disabled, dirauth_disabled,
  168. state_disabled);
  169. return 1;
  170. } else {
  171. log_debug(LD_CIRC,
  172. "CircuitBuildTime learning is not disabled. "
  173. "Consensus=%d, Config=%d, AuthDir=%d, StateFile=%d",
  174. consensus_disabled, config_disabled, dirauth_disabled,
  175. state_disabled);
  176. return 0;
  177. }
  178. }
  179. }
  180. /**
  181. * Retrieve and bounds-check the cbtmaxtimeouts consensus paramter.
  182. *
  183. * Effect: When this many timeouts happen in the last 'cbtrecentcount'
  184. * circuit attempts, the client should discard all of its history and
  185. * begin learning a fresh timeout value.
  186. */
  187. static int32_t
  188. circuit_build_times_max_timeouts(void)
  189. {
  190. int32_t cbt_maxtimeouts;
  191. cbt_maxtimeouts = networkstatus_get_param(NULL, "cbtmaxtimeouts",
  192. CBT_DEFAULT_MAX_RECENT_TIMEOUT_COUNT,
  193. CBT_MIN_MAX_RECENT_TIMEOUT_COUNT,
  194. CBT_MAX_MAX_RECENT_TIMEOUT_COUNT);
  195. if (!(get_options()->LearnCircuitBuildTimeout)) {
  196. log_debug(LD_BUG,
  197. "circuit_build_times_max_timeouts() called, cbtmaxtimeouts is"
  198. " %d",
  199. cbt_maxtimeouts);
  200. }
  201. return cbt_maxtimeouts;
  202. }
  203. /**
  204. * Retrieve and bounds-check the cbtnummodes consensus paramter.
  205. *
  206. * Effect: This value governs how many modes to use in the weighted
  207. * average calculation of Pareto parameter Xm. A value of 3 introduces
  208. * some bias (2-5% of CDF) under ideal conditions, but allows for better
  209. * performance in the event that a client chooses guard nodes of radically
  210. * different performance characteristics.
  211. */
  212. static int32_t
  213. circuit_build_times_default_num_xm_modes(void)
  214. {
  215. int32_t num = networkstatus_get_param(NULL, "cbtnummodes",
  216. CBT_DEFAULT_NUM_XM_MODES,
  217. CBT_MIN_NUM_XM_MODES,
  218. CBT_MAX_NUM_XM_MODES);
  219. if (!(get_options()->LearnCircuitBuildTimeout)) {
  220. log_debug(LD_BUG,
  221. "circuit_build_times_default_num_xm_modes() called, cbtnummodes"
  222. " is %d",
  223. num);
  224. }
  225. return num;
  226. }
  227. /**
  228. * Retrieve and bounds-check the cbtmincircs consensus paramter.
  229. *
  230. * Effect: This is the minimum number of circuits to build before
  231. * computing a timeout.
  232. */
  233. static int32_t
  234. circuit_build_times_min_circs_to_observe(void)
  235. {
  236. int32_t num = networkstatus_get_param(NULL, "cbtmincircs",
  237. CBT_DEFAULT_MIN_CIRCUITS_TO_OBSERVE,
  238. CBT_MIN_MIN_CIRCUITS_TO_OBSERVE,
  239. CBT_MAX_MIN_CIRCUITS_TO_OBSERVE);
  240. if (!(get_options()->LearnCircuitBuildTimeout)) {
  241. log_debug(LD_BUG,
  242. "circuit_build_times_min_circs_to_observe() called, cbtmincircs"
  243. " is %d",
  244. num);
  245. }
  246. return num;
  247. }
  248. /** Return true iff <b>cbt</b> has recorded enough build times that we
  249. * want to start acting on the timeout it implies. */
  250. int
  251. circuit_build_times_enough_to_compute(circuit_build_times_t *cbt)
  252. {
  253. return cbt->total_build_times >= circuit_build_times_min_circs_to_observe();
  254. }
  255. /**
  256. * Retrieve and bounds-check the cbtquantile consensus paramter.
  257. *
  258. * Effect: This is the position on the quantile curve to use to set the
  259. * timeout value. It is a percent (10-99).
  260. */
  261. double
  262. circuit_build_times_quantile_cutoff(void)
  263. {
  264. int32_t num = networkstatus_get_param(NULL, "cbtquantile",
  265. CBT_DEFAULT_QUANTILE_CUTOFF,
  266. CBT_MIN_QUANTILE_CUTOFF,
  267. CBT_MAX_QUANTILE_CUTOFF);
  268. if (!(get_options()->LearnCircuitBuildTimeout)) {
  269. log_debug(LD_BUG,
  270. "circuit_build_times_quantile_cutoff() called, cbtquantile"
  271. " is %d",
  272. num);
  273. }
  274. return num/100.0;
  275. }
  276. /* DOCDOC circuit_build_times_get_bw_scale */
  277. int
  278. circuit_build_times_get_bw_scale(networkstatus_t *ns)
  279. {
  280. return networkstatus_get_param(ns, "bwweightscale",
  281. BW_WEIGHT_SCALE,
  282. BW_MIN_WEIGHT_SCALE,
  283. BW_MAX_WEIGHT_SCALE);
  284. }
  285. /**
  286. * Retrieve and bounds-check the cbtclosequantile consensus paramter.
  287. *
  288. * Effect: This is the position on the quantile curve to use to set the
  289. * timeout value to use to actually close circuits. It is a percent
  290. * (0-99).
  291. */
  292. static double
  293. circuit_build_times_close_quantile(void)
  294. {
  295. int32_t param;
  296. /* Cast is safe - circuit_build_times_quantile_cutoff() is capped */
  297. int32_t min = (int)tor_lround(100*circuit_build_times_quantile_cutoff());
  298. param = networkstatus_get_param(NULL, "cbtclosequantile",
  299. CBT_DEFAULT_CLOSE_QUANTILE,
  300. CBT_MIN_CLOSE_QUANTILE,
  301. CBT_MAX_CLOSE_QUANTILE);
  302. if (!(get_options()->LearnCircuitBuildTimeout)) {
  303. log_debug(LD_BUG,
  304. "circuit_build_times_close_quantile() called, cbtclosequantile"
  305. " is %d", param);
  306. }
  307. if (param < min) {
  308. log_warn(LD_DIR, "Consensus parameter cbtclosequantile is "
  309. "too small, raising to %d", min);
  310. param = min;
  311. }
  312. return param / 100.0;
  313. }
  314. /**
  315. * Retrieve and bounds-check the cbttestfreq consensus paramter.
  316. *
  317. * Effect: Describes how often in seconds to build a test circuit to
  318. * gather timeout values. Only applies if less than 'cbtmincircs'
  319. * have been recorded.
  320. */
  321. static int32_t
  322. circuit_build_times_test_frequency(void)
  323. {
  324. int32_t num = networkstatus_get_param(NULL, "cbttestfreq",
  325. CBT_DEFAULT_TEST_FREQUENCY,
  326. CBT_MIN_TEST_FREQUENCY,
  327. CBT_MAX_TEST_FREQUENCY);
  328. if (!(get_options()->LearnCircuitBuildTimeout)) {
  329. log_debug(LD_BUG,
  330. "circuit_build_times_test_frequency() called, cbttestfreq is %d",
  331. num);
  332. }
  333. return num;
  334. }
  335. /**
  336. * Retrieve and bounds-check the cbtmintimeout consensus parameter.
  337. *
  338. * Effect: This is the minimum allowed timeout value in milliseconds.
  339. * The minimum is to prevent rounding to 0 (we only check once
  340. * per second).
  341. */
  342. static int32_t
  343. circuit_build_times_min_timeout(void)
  344. {
  345. int32_t num = networkstatus_get_param(NULL, "cbtmintimeout",
  346. CBT_DEFAULT_TIMEOUT_MIN_VALUE,
  347. CBT_MIN_TIMEOUT_MIN_VALUE,
  348. CBT_MAX_TIMEOUT_MIN_VALUE);
  349. if (!(get_options()->LearnCircuitBuildTimeout)) {
  350. log_debug(LD_BUG,
  351. "circuit_build_times_min_timeout() called, cbtmintimeout is %d",
  352. num);
  353. }
  354. return num;
  355. }
  356. /**
  357. * Retrieve and bounds-check the cbtinitialtimeout consensus paramter.
  358. *
  359. * Effect: This is the timeout value to use before computing a timeout,
  360. * in milliseconds.
  361. */
  362. int32_t
  363. circuit_build_times_initial_timeout(void)
  364. {
  365. int32_t min = circuit_build_times_min_timeout();
  366. int32_t param = networkstatus_get_param(NULL, "cbtinitialtimeout",
  367. CBT_DEFAULT_TIMEOUT_INITIAL_VALUE,
  368. CBT_MIN_TIMEOUT_INITIAL_VALUE,
  369. CBT_MAX_TIMEOUT_INITIAL_VALUE);
  370. if (!(get_options()->LearnCircuitBuildTimeout)) {
  371. log_debug(LD_BUG,
  372. "circuit_build_times_initial_timeout() called, "
  373. "cbtinitialtimeout is %d",
  374. param);
  375. }
  376. if (param < min) {
  377. log_warn(LD_DIR, "Consensus parameter cbtinitialtimeout is too small, "
  378. "raising to %d", min);
  379. param = min;
  380. }
  381. return param;
  382. }
  383. /**
  384. * Retrieve and bounds-check the cbtrecentcount consensus paramter.
  385. *
  386. * Effect: This is the number of circuit build times to keep track of
  387. * for deciding if we hit cbtmaxtimeouts and need to reset our state
  388. * and learn a new timeout.
  389. */
  390. static int32_t
  391. circuit_build_times_recent_circuit_count(networkstatus_t *ns)
  392. {
  393. int32_t num;
  394. num = networkstatus_get_param(ns, "cbtrecentcount",
  395. CBT_DEFAULT_RECENT_CIRCUITS,
  396. CBT_MIN_RECENT_CIRCUITS,
  397. CBT_MAX_RECENT_CIRCUITS);
  398. if (!(get_options()->LearnCircuitBuildTimeout)) {
  399. log_debug(LD_BUG,
  400. "circuit_build_times_recent_circuit_count() called, "
  401. "cbtrecentcount is %d",
  402. num);
  403. }
  404. return num;
  405. }
  406. /**
  407. * This function is called when we get a consensus update.
  408. *
  409. * It checks to see if we have changed any consensus parameters
  410. * that require reallocation or discard of previous stats.
  411. */
  412. void
  413. circuit_build_times_new_consensus_params(circuit_build_times_t *cbt,
  414. networkstatus_t *ns)
  415. {
  416. int32_t num;
  417. /*
  418. * First check if we're doing adaptive timeouts at all; nothing to
  419. * update if we aren't.
  420. */
  421. if (!circuit_build_times_disabled()) {
  422. num = circuit_build_times_recent_circuit_count(ns);
  423. if (num > 0) {
  424. if (num != cbt->liveness.num_recent_circs) {
  425. int8_t *recent_circs;
  426. log_notice(LD_CIRC, "The Tor Directory Consensus has changed how many "
  427. "circuits we must track to detect network failures from %d "
  428. "to %d.", cbt->liveness.num_recent_circs, num);
  429. tor_assert(cbt->liveness.timeouts_after_firsthop ||
  430. cbt->liveness.num_recent_circs == 0);
  431. /*
  432. * Technically this is a circular array that we are reallocating
  433. * and memcopying. However, since it only consists of either 1s
  434. * or 0s, and is only used in a statistical test to determine when
  435. * we should discard our history after a sufficient number of 1's
  436. * have been reached, it is fine if order is not preserved or
  437. * elements are lost.
  438. *
  439. * cbtrecentcount should only be changing in cases of severe network
  440. * distress anyway, so memory correctness here is paramount over
  441. * doing acrobatics to preserve the array.
  442. */
  443. recent_circs = tor_malloc_zero(sizeof(int8_t)*num);
  444. if (cbt->liveness.timeouts_after_firsthop &&
  445. cbt->liveness.num_recent_circs > 0) {
  446. memcpy(recent_circs, cbt->liveness.timeouts_after_firsthop,
  447. sizeof(int8_t)*MIN(num, cbt->liveness.num_recent_circs));
  448. }
  449. // Adjust the index if it needs it.
  450. if (num < cbt->liveness.num_recent_circs) {
  451. cbt->liveness.after_firsthop_idx = MIN(num-1,
  452. cbt->liveness.after_firsthop_idx);
  453. }
  454. tor_free(cbt->liveness.timeouts_after_firsthop);
  455. cbt->liveness.timeouts_after_firsthop = recent_circs;
  456. cbt->liveness.num_recent_circs = num;
  457. }
  458. /* else no change, nothing to do */
  459. } else { /* num == 0 */
  460. /*
  461. * Weird. This probably shouldn't happen, so log a warning, but try
  462. * to do something sensible anyway.
  463. */
  464. log_warn(LD_CIRC,
  465. "The cbtrecentcircs consensus parameter came back zero! "
  466. "This disables adaptive timeouts since we can't keep track of "
  467. "any recent circuits.");
  468. circuit_build_times_free_timeouts(cbt);
  469. }
  470. } else {
  471. /*
  472. * Adaptive timeouts are disabled; this might be because of the
  473. * LearnCircuitBuildTimes config parameter, and hence permanent, or
  474. * the cbtdisabled consensus parameter, so it may be a new condition.
  475. * Treat it like getting num == 0 above and free the circuit history
  476. * if we have any.
  477. */
  478. circuit_build_times_free_timeouts(cbt);
  479. }
  480. }
  481. /** Make a note that we're running unit tests (rather than running Tor
  482. * itself), so we avoid clobbering our state file. */
  483. void
  484. circuitbuild_running_unit_tests(void)
  485. {
  486. unit_tests = 1;
  487. }
  488. /**
  489. * Return the initial default or configured timeout in milliseconds
  490. */
  491. static double
  492. circuit_build_times_get_initial_timeout(void)
  493. {
  494. double timeout;
  495. /*
  496. * Check if we have LearnCircuitBuildTimeout, and if we don't,
  497. * always use CircuitBuildTimeout, no questions asked.
  498. */
  499. if (get_options()->LearnCircuitBuildTimeout) {
  500. if (!unit_tests && get_options()->CircuitBuildTimeout) {
  501. timeout = get_options()->CircuitBuildTimeout*1000;
  502. if (timeout < circuit_build_times_min_timeout()) {
  503. log_warn(LD_CIRC, "Config CircuitBuildTimeout too low. Setting to %ds",
  504. circuit_build_times_min_timeout()/1000);
  505. timeout = circuit_build_times_min_timeout();
  506. }
  507. } else {
  508. timeout = circuit_build_times_initial_timeout();
  509. }
  510. } else {
  511. timeout = get_options()->CircuitBuildTimeout*1000;
  512. }
  513. return timeout;
  514. }
  515. /**
  516. * Reset the build time state.
  517. *
  518. * Leave estimated parameters, timeout and network liveness intact
  519. * for future use.
  520. */
  521. void
  522. circuit_build_times_reset(circuit_build_times_t *cbt)
  523. {
  524. memset(cbt->circuit_build_times, 0, sizeof(cbt->circuit_build_times));
  525. cbt->total_build_times = 0;
  526. cbt->build_times_idx = 0;
  527. cbt->have_computed_timeout = 0;
  528. }
  529. /**
  530. * Initialize the buildtimes structure for first use.
  531. *
  532. * Sets the initial timeout values based on either the config setting,
  533. * the consensus param, or the default (CBT_DEFAULT_TIMEOUT_INITIAL_VALUE).
  534. */
  535. void
  536. circuit_build_times_init(circuit_build_times_t *cbt)
  537. {
  538. memset(cbt, 0, sizeof(*cbt));
  539. /*
  540. * Check if we really are using adaptive timeouts, and don't keep
  541. * track of this stuff if not.
  542. */
  543. if (!circuit_build_times_disabled()) {
  544. cbt->liveness.num_recent_circs =
  545. circuit_build_times_recent_circuit_count(NULL);
  546. cbt->liveness.timeouts_after_firsthop =
  547. tor_malloc_zero(sizeof(int8_t)*cbt->liveness.num_recent_circs);
  548. } else {
  549. cbt->liveness.num_recent_circs = 0;
  550. cbt->liveness.timeouts_after_firsthop = NULL;
  551. }
  552. cbt->close_ms = cbt->timeout_ms = circuit_build_times_get_initial_timeout();
  553. control_event_buildtimeout_set(cbt, BUILDTIMEOUT_SET_EVENT_RESET);
  554. }
  555. /**
  556. * Free the saved timeouts, if the cbtdisabled consensus parameter got turned
  557. * on or something.
  558. */
  559. void
  560. circuit_build_times_free_timeouts(circuit_build_times_t *cbt)
  561. {
  562. if (!cbt) return;
  563. if (cbt->liveness.timeouts_after_firsthop) {
  564. tor_free(cbt->liveness.timeouts_after_firsthop);
  565. }
  566. cbt->liveness.num_recent_circs = 0;
  567. }
  568. #if 0
  569. /**
  570. * Rewind our build time history by n positions.
  571. */
  572. static void
  573. circuit_build_times_rewind_history(circuit_build_times_t *cbt, int n)
  574. {
  575. int i = 0;
  576. cbt->build_times_idx -= n;
  577. cbt->build_times_idx %= CBT_NCIRCUITS_TO_OBSERVE;
  578. for (i = 0; i < n; i++) {
  579. cbt->circuit_build_times[(i+cbt->build_times_idx)
  580. %CBT_NCIRCUITS_TO_OBSERVE]=0;
  581. }
  582. if (cbt->total_build_times > n) {
  583. cbt->total_build_times -= n;
  584. } else {
  585. cbt->total_build_times = 0;
  586. }
  587. log_info(LD_CIRC,
  588. "Rewound history by %d places. Current index: %d. "
  589. "Total: %d", n, cbt->build_times_idx, cbt->total_build_times);
  590. }
  591. #endif
  592. /**
  593. * Add a new build time value <b>time</b> to the set of build times. Time
  594. * units are milliseconds.
  595. *
  596. * circuit_build_times <b>cbt</b> is a circular array, so loop around when
  597. * array is full.
  598. */
  599. int
  600. circuit_build_times_add_time(circuit_build_times_t *cbt, build_time_t time)
  601. {
  602. if (time <= 0 || time > CBT_BUILD_TIME_MAX) {
  603. log_warn(LD_BUG, "Circuit build time is too large (%u)."
  604. "This is probably a bug.", time);
  605. tor_fragile_assert();
  606. return -1;
  607. }
  608. log_debug(LD_CIRC, "Adding circuit build time %u", time);
  609. cbt->circuit_build_times[cbt->build_times_idx] = time;
  610. cbt->build_times_idx = (cbt->build_times_idx + 1) % CBT_NCIRCUITS_TO_OBSERVE;
  611. if (cbt->total_build_times < CBT_NCIRCUITS_TO_OBSERVE)
  612. cbt->total_build_times++;
  613. if ((cbt->total_build_times % CBT_SAVE_STATE_EVERY) == 0) {
  614. /* Save state every n circuit builds */
  615. if (!unit_tests && !get_options()->AvoidDiskWrites)
  616. or_state_mark_dirty(get_or_state(), 0);
  617. }
  618. return 0;
  619. }
  620. /**
  621. * Return maximum circuit build time
  622. */
  623. static build_time_t
  624. circuit_build_times_max(circuit_build_times_t *cbt)
  625. {
  626. int i = 0;
  627. build_time_t max_build_time = 0;
  628. for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
  629. if (cbt->circuit_build_times[i] > max_build_time
  630. && cbt->circuit_build_times[i] != CBT_BUILD_ABANDONED)
  631. max_build_time = cbt->circuit_build_times[i];
  632. }
  633. return max_build_time;
  634. }
  635. #if 0
  636. /** Return minimum circuit build time */
  637. build_time_t
  638. circuit_build_times_min(circuit_build_times_t *cbt)
  639. {
  640. int i = 0;
  641. build_time_t min_build_time = CBT_BUILD_TIME_MAX;
  642. for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
  643. if (cbt->circuit_build_times[i] && /* 0 <-> uninitialized */
  644. cbt->circuit_build_times[i] < min_build_time)
  645. min_build_time = cbt->circuit_build_times[i];
  646. }
  647. if (min_build_time == CBT_BUILD_TIME_MAX) {
  648. log_warn(LD_CIRC, "No build times less than CBT_BUILD_TIME_MAX!");
  649. }
  650. return min_build_time;
  651. }
  652. #endif
  653. /**
  654. * Calculate and return a histogram for the set of build times.
  655. *
  656. * Returns an allocated array of histrogram bins representing
  657. * the frequency of index*CBT_BIN_WIDTH millisecond
  658. * build times. Also outputs the number of bins in nbins.
  659. *
  660. * The return value must be freed by the caller.
  661. */
  662. static uint32_t *
  663. circuit_build_times_create_histogram(circuit_build_times_t *cbt,
  664. build_time_t *nbins)
  665. {
  666. uint32_t *histogram;
  667. build_time_t max_build_time = circuit_build_times_max(cbt);
  668. int i, c;
  669. *nbins = 1 + (max_build_time / CBT_BIN_WIDTH);
  670. histogram = tor_malloc_zero(*nbins * sizeof(build_time_t));
  671. // calculate histogram
  672. for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
  673. if (cbt->circuit_build_times[i] == 0
  674. || cbt->circuit_build_times[i] == CBT_BUILD_ABANDONED)
  675. continue; /* 0 <-> uninitialized */
  676. c = (cbt->circuit_build_times[i] / CBT_BIN_WIDTH);
  677. histogram[c]++;
  678. }
  679. return histogram;
  680. }
  681. /**
  682. * Return the Pareto start-of-curve parameter Xm.
  683. *
  684. * Because we are not a true Pareto curve, we compute this as the
  685. * weighted average of the N most frequent build time bins. N is either
  686. * 1 if we don't have enough circuit build time data collected, or
  687. * determined by the consensus parameter cbtnummodes (default 3).
  688. */
  689. static build_time_t
  690. circuit_build_times_get_xm(circuit_build_times_t *cbt)
  691. {
  692. build_time_t i, nbins;
  693. build_time_t *nth_max_bin;
  694. int32_t bin_counts=0;
  695. build_time_t ret = 0;
  696. uint32_t *histogram = circuit_build_times_create_histogram(cbt, &nbins);
  697. int n=0;
  698. int num_modes = circuit_build_times_default_num_xm_modes();
  699. tor_assert(nbins > 0);
  700. tor_assert(num_modes > 0);
  701. // Only use one mode if < 1000 buildtimes. Not enough data
  702. // for multiple.
  703. if (cbt->total_build_times < CBT_NCIRCUITS_TO_OBSERVE)
  704. num_modes = 1;
  705. nth_max_bin = (build_time_t*)tor_malloc_zero(num_modes*sizeof(build_time_t));
  706. /* Determine the N most common build times */
  707. for (i = 0; i < nbins; i++) {
  708. if (histogram[i] >= histogram[nth_max_bin[0]]) {
  709. nth_max_bin[0] = i;
  710. }
  711. for (n = 1; n < num_modes; n++) {
  712. if (histogram[i] >= histogram[nth_max_bin[n]] &&
  713. (!histogram[nth_max_bin[n-1]]
  714. || histogram[i] < histogram[nth_max_bin[n-1]])) {
  715. nth_max_bin[n] = i;
  716. }
  717. }
  718. }
  719. for (n = 0; n < num_modes; n++) {
  720. bin_counts += histogram[nth_max_bin[n]];
  721. ret += CBT_BIN_TO_MS(nth_max_bin[n])*histogram[nth_max_bin[n]];
  722. log_info(LD_CIRC, "Xm mode #%d: %u %u", n, CBT_BIN_TO_MS(nth_max_bin[n]),
  723. histogram[nth_max_bin[n]]);
  724. }
  725. /* The following assert is safe, because we don't get called when we
  726. * haven't observed at least CBT_MIN_MIN_CIRCUITS_TO_OBSERVE circuits. */
  727. tor_assert(bin_counts > 0);
  728. ret /= bin_counts;
  729. tor_free(histogram);
  730. tor_free(nth_max_bin);
  731. return ret;
  732. }
  733. /**
  734. * Output a histogram of current circuit build times to
  735. * the or_state_t state structure.
  736. */
  737. void
  738. circuit_build_times_update_state(circuit_build_times_t *cbt,
  739. or_state_t *state)
  740. {
  741. uint32_t *histogram;
  742. build_time_t i = 0;
  743. build_time_t nbins = 0;
  744. config_line_t **next, *line;
  745. histogram = circuit_build_times_create_histogram(cbt, &nbins);
  746. // write to state
  747. config_free_lines(state->BuildtimeHistogram);
  748. next = &state->BuildtimeHistogram;
  749. *next = NULL;
  750. state->TotalBuildTimes = cbt->total_build_times;
  751. state->CircuitBuildAbandonedCount = 0;
  752. for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
  753. if (cbt->circuit_build_times[i] == CBT_BUILD_ABANDONED)
  754. state->CircuitBuildAbandonedCount++;
  755. }
  756. for (i = 0; i < nbins; i++) {
  757. // compress the histogram by skipping the blanks
  758. if (histogram[i] == 0) continue;
  759. *next = line = tor_malloc_zero(sizeof(config_line_t));
  760. line->key = tor_strdup("CircuitBuildTimeBin");
  761. tor_asprintf(&line->value, "%d %d",
  762. CBT_BIN_TO_MS(i), histogram[i]);
  763. next = &(line->next);
  764. }
  765. if (!unit_tests) {
  766. if (!get_options()->AvoidDiskWrites)
  767. or_state_mark_dirty(get_or_state(), 0);
  768. }
  769. tor_free(histogram);
  770. }
  771. /**
  772. * Shuffle the build times array.
  773. *
  774. * Adapted from http://en.wikipedia.org/wiki/Fisher-Yates_shuffle
  775. */
  776. static void
  777. circuit_build_times_shuffle_and_store_array(circuit_build_times_t *cbt,
  778. build_time_t *raw_times,
  779. uint32_t num_times)
  780. {
  781. uint32_t n = num_times;
  782. if (num_times > CBT_NCIRCUITS_TO_OBSERVE) {
  783. log_notice(LD_CIRC, "The number of circuit times that this Tor version "
  784. "uses to calculate build times is less than the number stored "
  785. "in your state file. Decreasing the circuit time history from "
  786. "%lu to %d.", (unsigned long)num_times,
  787. CBT_NCIRCUITS_TO_OBSERVE);
  788. }
  789. if (n > INT_MAX-1) {
  790. log_warn(LD_CIRC, "For some insane reasons, you had %lu circuit build "
  791. "observations in your state file. That's far too many; probably "
  792. "there's a bug here.", (unsigned long)n);
  793. n = INT_MAX-1;
  794. }
  795. /* This code can only be run on a compact array */
  796. while (n-- > 1) {
  797. int k = crypto_rand_int(n + 1); /* 0 <= k <= n. */
  798. build_time_t tmp = raw_times[k];
  799. raw_times[k] = raw_times[n];
  800. raw_times[n] = tmp;
  801. }
  802. /* Since the times are now shuffled, take a random CBT_NCIRCUITS_TO_OBSERVE
  803. * subset (ie the first CBT_NCIRCUITS_TO_OBSERVE values) */
  804. for (n = 0; n < MIN(num_times, CBT_NCIRCUITS_TO_OBSERVE); n++) {
  805. circuit_build_times_add_time(cbt, raw_times[n]);
  806. }
  807. }
  808. /**
  809. * Filter old synthetic timeouts that were created before the
  810. * new right-censored Pareto calculation was deployed.
  811. *
  812. * Once all clients before 0.2.1.13-alpha are gone, this code
  813. * will be unused.
  814. */
  815. static int
  816. circuit_build_times_filter_timeouts(circuit_build_times_t *cbt)
  817. {
  818. int num_filtered=0, i=0;
  819. double timeout_rate = 0;
  820. build_time_t max_timeout = 0;
  821. timeout_rate = circuit_build_times_timeout_rate(cbt);
  822. max_timeout = (build_time_t)cbt->close_ms;
  823. for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
  824. if (cbt->circuit_build_times[i] > max_timeout) {
  825. build_time_t replaced = cbt->circuit_build_times[i];
  826. num_filtered++;
  827. cbt->circuit_build_times[i] = CBT_BUILD_ABANDONED;
  828. log_debug(LD_CIRC, "Replaced timeout %d with %d", replaced,
  829. cbt->circuit_build_times[i]);
  830. }
  831. }
  832. log_info(LD_CIRC,
  833. "We had %d timeouts out of %d build times, "
  834. "and filtered %d above the max of %u",
  835. (int)(cbt->total_build_times*timeout_rate),
  836. cbt->total_build_times, num_filtered, max_timeout);
  837. return num_filtered;
  838. }
  839. /**
  840. * Load histogram from <b>state</b>, shuffling the resulting array
  841. * after we do so. Use this result to estimate parameters and
  842. * calculate the timeout.
  843. *
  844. * Return -1 on error.
  845. */
  846. int
  847. circuit_build_times_parse_state(circuit_build_times_t *cbt,
  848. or_state_t *state)
  849. {
  850. int tot_values = 0;
  851. uint32_t loaded_cnt = 0, N = 0;
  852. config_line_t *line;
  853. unsigned int i;
  854. build_time_t *loaded_times;
  855. int err = 0;
  856. circuit_build_times_init(cbt);
  857. if (circuit_build_times_disabled()) {
  858. return 0;
  859. }
  860. /* build_time_t 0 means uninitialized */
  861. loaded_times = tor_malloc_zero(sizeof(build_time_t)*state->TotalBuildTimes);
  862. for (line = state->BuildtimeHistogram; line; line = line->next) {
  863. smartlist_t *args = smartlist_new();
  864. smartlist_split_string(args, line->value, " ",
  865. SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
  866. if (smartlist_len(args) < 2) {
  867. log_warn(LD_GENERAL, "Unable to parse circuit build times: "
  868. "Too few arguments to CircuitBuildTime");
  869. err = 1;
  870. SMARTLIST_FOREACH(args, char*, cp, tor_free(cp));
  871. smartlist_free(args);
  872. break;
  873. } else {
  874. const char *ms_str = smartlist_get(args,0);
  875. const char *count_str = smartlist_get(args,1);
  876. uint32_t count, k;
  877. build_time_t ms;
  878. int ok;
  879. ms = (build_time_t)tor_parse_ulong(ms_str, 0, 0,
  880. CBT_BUILD_TIME_MAX, &ok, NULL);
  881. if (!ok) {
  882. log_warn(LD_GENERAL, "Unable to parse circuit build times: "
  883. "Unparsable bin number");
  884. err = 1;
  885. SMARTLIST_FOREACH(args, char*, cp, tor_free(cp));
  886. smartlist_free(args);
  887. break;
  888. }
  889. count = (uint32_t)tor_parse_ulong(count_str, 0, 0,
  890. UINT32_MAX, &ok, NULL);
  891. if (!ok) {
  892. log_warn(LD_GENERAL, "Unable to parse circuit build times: "
  893. "Unparsable bin count");
  894. err = 1;
  895. SMARTLIST_FOREACH(args, char*, cp, tor_free(cp));
  896. smartlist_free(args);
  897. break;
  898. }
  899. if (loaded_cnt+count+state->CircuitBuildAbandonedCount
  900. > state->TotalBuildTimes) {
  901. log_warn(LD_CIRC,
  902. "Too many build times in state file. "
  903. "Stopping short before %d",
  904. loaded_cnt+count);
  905. SMARTLIST_FOREACH(args, char*, cp, tor_free(cp));
  906. smartlist_free(args);
  907. break;
  908. }
  909. for (k = 0; k < count; k++) {
  910. loaded_times[loaded_cnt++] = ms;
  911. }
  912. N++;
  913. SMARTLIST_FOREACH(args, char*, cp, tor_free(cp));
  914. smartlist_free(args);
  915. }
  916. }
  917. log_info(LD_CIRC,
  918. "Adding %d timeouts.", state->CircuitBuildAbandonedCount);
  919. for (i=0; i < state->CircuitBuildAbandonedCount; i++) {
  920. loaded_times[loaded_cnt++] = CBT_BUILD_ABANDONED;
  921. }
  922. if (loaded_cnt != state->TotalBuildTimes) {
  923. log_warn(LD_CIRC,
  924. "Corrupt state file? Build times count mismatch. "
  925. "Read %d times, but file says %d", loaded_cnt,
  926. state->TotalBuildTimes);
  927. err = 1;
  928. circuit_build_times_reset(cbt);
  929. goto done;
  930. }
  931. circuit_build_times_shuffle_and_store_array(cbt, loaded_times, loaded_cnt);
  932. /* Verify that we didn't overwrite any indexes */
  933. for (i=0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
  934. if (!cbt->circuit_build_times[i])
  935. break;
  936. tot_values++;
  937. }
  938. log_info(LD_CIRC,
  939. "Loaded %d/%d values from %d lines in circuit time histogram",
  940. tot_values, cbt->total_build_times, N);
  941. if (cbt->total_build_times != tot_values
  942. || cbt->total_build_times > CBT_NCIRCUITS_TO_OBSERVE) {
  943. log_warn(LD_CIRC,
  944. "Corrupt state file? Shuffled build times mismatch. "
  945. "Read %d times, but file says %d", tot_values,
  946. state->TotalBuildTimes);
  947. err = 1;
  948. circuit_build_times_reset(cbt);
  949. goto done;
  950. }
  951. circuit_build_times_set_timeout(cbt);
  952. if (!state->CircuitBuildAbandonedCount && cbt->total_build_times) {
  953. circuit_build_times_filter_timeouts(cbt);
  954. }
  955. done:
  956. tor_free(loaded_times);
  957. return err ? -1 : 0;
  958. }
  959. /**
  960. * Estimates the Xm and Alpha parameters using
  961. * http://en.wikipedia.org/wiki/Pareto_distribution#Parameter_estimation
  962. *
  963. * The notable difference is that we use mode instead of min to estimate Xm.
  964. * This is because our distribution is frechet-like. We claim this is
  965. * an acceptable approximation because we are only concerned with the
  966. * accuracy of the CDF of the tail.
  967. */
  968. int
  969. circuit_build_times_update_alpha(circuit_build_times_t *cbt)
  970. {
  971. build_time_t *x=cbt->circuit_build_times;
  972. double a = 0;
  973. int n=0,i=0,abandoned_count=0;
  974. build_time_t max_time=0;
  975. /* http://en.wikipedia.org/wiki/Pareto_distribution#Parameter_estimation */
  976. /* We sort of cheat here and make our samples slightly more pareto-like
  977. * and less frechet-like. */
  978. cbt->Xm = circuit_build_times_get_xm(cbt);
  979. tor_assert(cbt->Xm > 0);
  980. for (i=0; i< CBT_NCIRCUITS_TO_OBSERVE; i++) {
  981. if (!x[i]) {
  982. continue;
  983. }
  984. if (x[i] < cbt->Xm) {
  985. a += tor_mathlog(cbt->Xm);
  986. } else if (x[i] == CBT_BUILD_ABANDONED) {
  987. abandoned_count++;
  988. } else {
  989. a += tor_mathlog(x[i]);
  990. if (x[i] > max_time)
  991. max_time = x[i];
  992. }
  993. n++;
  994. }
  995. /*
  996. * We are erring and asserting here because this can only happen
  997. * in codepaths other than startup. The startup state parsing code
  998. * performs this same check, and resets state if it hits it. If we
  999. * hit it at runtime, something serious has gone wrong.
  1000. */
  1001. if (n!=cbt->total_build_times) {
  1002. log_err(LD_CIRC, "Discrepancy in build times count: %d vs %d", n,
  1003. cbt->total_build_times);
  1004. }
  1005. tor_assert(n==cbt->total_build_times);
  1006. if (max_time <= 0) {
  1007. /* This can happen if Xm is actually the *maximum* value in the set.
  1008. * It can also happen if we've abandoned every single circuit somehow.
  1009. * In either case, tell the caller not to compute a new build timeout. */
  1010. log_warn(LD_BUG,
  1011. "Could not determine largest build time (%d). "
  1012. "Xm is %dms and we've abandoned %d out of %d circuits.", max_time,
  1013. cbt->Xm, abandoned_count, n);
  1014. return 0;
  1015. }
  1016. a += abandoned_count*tor_mathlog(max_time);
  1017. a -= n*tor_mathlog(cbt->Xm);
  1018. // Estimator comes from Eq #4 in:
  1019. // "Bayesian estimation based on trimmed samples from Pareto populations"
  1020. // by Arturo J. Fernández. We are right-censored only.
  1021. a = (n-abandoned_count)/a;
  1022. cbt->alpha = a;
  1023. return 1;
  1024. }
  1025. /**
  1026. * This is the Pareto Quantile Function. It calculates the point x
  1027. * in the distribution such that F(x) = quantile (ie quantile*100%
  1028. * of the mass of the density function is below x on the curve).
  1029. *
  1030. * We use it to calculate the timeout and also to generate synthetic
  1031. * values of time for circuits that timeout before completion.
  1032. *
  1033. * See http://en.wikipedia.org/wiki/Quantile_function,
  1034. * http://en.wikipedia.org/wiki/Inverse_transform_sampling and
  1035. * http://en.wikipedia.org/wiki/Pareto_distribution#Generating_a_
  1036. * random_sample_from_Pareto_distribution
  1037. * That's right. I'll cite wikipedia all day long.
  1038. *
  1039. * Return value is in milliseconds.
  1040. */
  1041. double
  1042. circuit_build_times_calculate_timeout(circuit_build_times_t *cbt,
  1043. double quantile)
  1044. {
  1045. double ret;
  1046. tor_assert(quantile >= 0);
  1047. tor_assert(1.0-quantile > 0);
  1048. tor_assert(cbt->Xm > 0);
  1049. ret = cbt->Xm/pow(1.0-quantile,1.0/cbt->alpha);
  1050. if (ret > INT32_MAX) {
  1051. ret = INT32_MAX;
  1052. }
  1053. tor_assert(ret > 0);
  1054. return ret;
  1055. }
  1056. /** Pareto CDF */
  1057. double
  1058. circuit_build_times_cdf(circuit_build_times_t *cbt, double x)
  1059. {
  1060. double ret;
  1061. tor_assert(cbt->Xm > 0);
  1062. ret = 1.0-pow(cbt->Xm/x,cbt->alpha);
  1063. tor_assert(0 <= ret && ret <= 1.0);
  1064. return ret;
  1065. }
  1066. /**
  1067. * Generate a synthetic time using our distribution parameters.
  1068. *
  1069. * The return value will be within the [q_lo, q_hi) quantile points
  1070. * on the CDF.
  1071. */
  1072. build_time_t
  1073. circuit_build_times_generate_sample(circuit_build_times_t *cbt,
  1074. double q_lo, double q_hi)
  1075. {
  1076. double randval = crypto_rand_double();
  1077. build_time_t ret;
  1078. double u;
  1079. /* Generate between [q_lo, q_hi) */
  1080. /*XXXX This is what nextafter is supposed to be for; we should use it on the
  1081. * platforms that support it. */
  1082. q_hi -= 1.0/(INT32_MAX);
  1083. tor_assert(q_lo >= 0);
  1084. tor_assert(q_hi < 1);
  1085. tor_assert(q_lo < q_hi);
  1086. u = q_lo + (q_hi-q_lo)*randval;
  1087. tor_assert(0 <= u && u < 1.0);
  1088. /* circuit_build_times_calculate_timeout returns <= INT32_MAX */
  1089. ret = (build_time_t)
  1090. tor_lround(circuit_build_times_calculate_timeout(cbt, u));
  1091. tor_assert(ret > 0);
  1092. return ret;
  1093. }
  1094. /**
  1095. * Estimate an initial alpha parameter by solving the quantile
  1096. * function with a quantile point and a specific timeout value.
  1097. */
  1098. void
  1099. circuit_build_times_initial_alpha(circuit_build_times_t *cbt,
  1100. double quantile, double timeout_ms)
  1101. {
  1102. // Q(u) = Xm/((1-u)^(1/a))
  1103. // Q(0.8) = Xm/((1-0.8))^(1/a)) = CircBuildTimeout
  1104. // CircBuildTimeout = Xm/((1-0.8))^(1/a))
  1105. // CircBuildTimeout = Xm*((1-0.8))^(-1/a))
  1106. // ln(CircBuildTimeout) = ln(Xm)+ln(((1-0.8)))*(-1/a)
  1107. // -ln(1-0.8)/(ln(CircBuildTimeout)-ln(Xm))=a
  1108. tor_assert(quantile >= 0);
  1109. tor_assert(cbt->Xm > 0);
  1110. cbt->alpha = tor_mathlog(1.0-quantile)/
  1111. (tor_mathlog(cbt->Xm)-tor_mathlog(timeout_ms));
  1112. tor_assert(cbt->alpha > 0);
  1113. }
  1114. /**
  1115. * Returns true if we need circuits to be built
  1116. */
  1117. int
  1118. circuit_build_times_needs_circuits(circuit_build_times_t *cbt)
  1119. {
  1120. /* Return true if < MIN_CIRCUITS_TO_OBSERVE */
  1121. return !circuit_build_times_enough_to_compute(cbt);
  1122. }
  1123. /**
  1124. * Returns true if we should build a timeout test circuit
  1125. * right now.
  1126. */
  1127. int
  1128. circuit_build_times_needs_circuits_now(circuit_build_times_t *cbt)
  1129. {
  1130. return circuit_build_times_needs_circuits(cbt) &&
  1131. approx_time()-cbt->last_circ_at > circuit_build_times_test_frequency();
  1132. }
  1133. /**
  1134. * Called to indicate that the network showed some signs of liveness,
  1135. * i.e. we received a cell.
  1136. *
  1137. * This is used by circuit_build_times_network_check_live() to decide
  1138. * if we should record the circuit build timeout or not.
  1139. *
  1140. * This function is called every time we receive a cell. Avoid
  1141. * syscalls, events, and other high-intensity work.
  1142. */
  1143. void
  1144. circuit_build_times_network_is_live(circuit_build_times_t *cbt)
  1145. {
  1146. time_t now = approx_time();
  1147. if (cbt->liveness.nonlive_timeouts > 0) {
  1148. log_notice(LD_CIRC,
  1149. "Tor now sees network activity. Restoring circuit build "
  1150. "timeout recording. Network was down for %d seconds "
  1151. "during %d circuit attempts.",
  1152. (int)(now - cbt->liveness.network_last_live),
  1153. cbt->liveness.nonlive_timeouts);
  1154. }
  1155. cbt->liveness.network_last_live = now;
  1156. cbt->liveness.nonlive_timeouts = 0;
  1157. }
  1158. /**
  1159. * Called to indicate that we completed a circuit. Because this circuit
  1160. * succeeded, it doesn't count as a timeout-after-the-first-hop.
  1161. *
  1162. * This is used by circuit_build_times_network_check_changed() to determine
  1163. * if we had too many recent timeouts and need to reset our learned timeout
  1164. * to something higher.
  1165. */
  1166. void
  1167. circuit_build_times_network_circ_success(circuit_build_times_t *cbt)
  1168. {
  1169. /* Check for NULLness because we might not be using adaptive timeouts */
  1170. if (cbt->liveness.timeouts_after_firsthop &&
  1171. cbt->liveness.num_recent_circs > 0) {
  1172. cbt->liveness.timeouts_after_firsthop[cbt->liveness.after_firsthop_idx]
  1173. = 0;
  1174. cbt->liveness.after_firsthop_idx++;
  1175. cbt->liveness.after_firsthop_idx %= cbt->liveness.num_recent_circs;
  1176. }
  1177. }
  1178. /**
  1179. * A circuit just timed out. If it failed after the first hop, record it
  1180. * in our history for later deciding if the network speed has changed.
  1181. *
  1182. * This is used by circuit_build_times_network_check_changed() to determine
  1183. * if we had too many recent timeouts and need to reset our learned timeout
  1184. * to something higher.
  1185. */
  1186. static void
  1187. circuit_build_times_network_timeout(circuit_build_times_t *cbt,
  1188. int did_onehop)
  1189. {
  1190. /* Check for NULLness because we might not be using adaptive timeouts */
  1191. if (cbt->liveness.timeouts_after_firsthop &&
  1192. cbt->liveness.num_recent_circs > 0) {
  1193. if (did_onehop) {
  1194. cbt->liveness.timeouts_after_firsthop[cbt->liveness.after_firsthop_idx]
  1195. = 1;
  1196. cbt->liveness.after_firsthop_idx++;
  1197. cbt->liveness.after_firsthop_idx %= cbt->liveness.num_recent_circs;
  1198. }
  1199. }
  1200. }
  1201. /**
  1202. * A circuit was just forcibly closed. If there has been no recent network
  1203. * activity at all, but this circuit was launched back when we thought the
  1204. * network was live, increment the number of "nonlive" circuit timeouts.
  1205. *
  1206. * This is used by circuit_build_times_network_check_live() to decide
  1207. * if we should record the circuit build timeout or not.
  1208. */
  1209. static void
  1210. circuit_build_times_network_close(circuit_build_times_t *cbt,
  1211. int did_onehop, time_t start_time)
  1212. {
  1213. time_t now = time(NULL);
  1214. /*
  1215. * Check if this is a timeout that was for a circuit that spent its
  1216. * entire existence during a time where we have had no network activity.
  1217. */
  1218. if (cbt->liveness.network_last_live < start_time) {
  1219. if (did_onehop) {
  1220. char last_live_buf[ISO_TIME_LEN+1];
  1221. char start_time_buf[ISO_TIME_LEN+1];
  1222. char now_buf[ISO_TIME_LEN+1];
  1223. format_local_iso_time(last_live_buf, cbt->liveness.network_last_live);
  1224. format_local_iso_time(start_time_buf, start_time);
  1225. format_local_iso_time(now_buf, now);
  1226. log_warn(LD_BUG,
  1227. "Circuit somehow completed a hop while the network was "
  1228. "not live. Network was last live at %s, but circuit launched "
  1229. "at %s. It's now %s.", last_live_buf, start_time_buf,
  1230. now_buf);
  1231. }
  1232. cbt->liveness.nonlive_timeouts++;
  1233. if (cbt->liveness.nonlive_timeouts == 1) {
  1234. log_notice(LD_CIRC,
  1235. "Tor has not observed any network activity for the past %d "
  1236. "seconds. Disabling circuit build timeout recording.",
  1237. (int)(now - cbt->liveness.network_last_live));
  1238. } else {
  1239. log_info(LD_CIRC,
  1240. "Got non-live timeout. Current count is: %d",
  1241. cbt->liveness.nonlive_timeouts);
  1242. }
  1243. }
  1244. }
  1245. /**
  1246. * When the network is not live, we do not record circuit build times.
  1247. *
  1248. * The network is considered not live if there has been at least one
  1249. * circuit build that began and ended (had its close_ms measurement
  1250. * period expire) since we last received a cell.
  1251. *
  1252. * Also has the side effect of rewinding the circuit time history
  1253. * in the case of recent liveness changes.
  1254. */
  1255. int
  1256. circuit_build_times_network_check_live(circuit_build_times_t *cbt)
  1257. {
  1258. if (cbt->liveness.nonlive_timeouts > 0) {
  1259. return 0;
  1260. }
  1261. return 1;
  1262. }
  1263. /**
  1264. * Returns true if we have seen more than MAX_RECENT_TIMEOUT_COUNT of
  1265. * the past RECENT_CIRCUITS time out after the first hop. Used to detect
  1266. * if the network connection has changed significantly, and if so,
  1267. * resets our circuit build timeout to the default.
  1268. *
  1269. * Also resets the entire timeout history in this case and causes us
  1270. * to restart the process of building test circuits and estimating a
  1271. * new timeout.
  1272. */
  1273. int
  1274. circuit_build_times_network_check_changed(circuit_build_times_t *cbt)
  1275. {
  1276. int total_build_times = cbt->total_build_times;
  1277. int timeout_count=0;
  1278. int i;
  1279. if (cbt->liveness.timeouts_after_firsthop &&
  1280. cbt->liveness.num_recent_circs > 0) {
  1281. /* how many of our recent circuits made it to the first hop but then
  1282. * timed out? */
  1283. for (i = 0; i < cbt->liveness.num_recent_circs; i++) {
  1284. timeout_count += cbt->liveness.timeouts_after_firsthop[i];
  1285. }
  1286. }
  1287. /* If 80% of our recent circuits are timing out after the first hop,
  1288. * we need to re-estimate a new initial alpha and timeout. */
  1289. if (timeout_count < circuit_build_times_max_timeouts()) {
  1290. return 0;
  1291. }
  1292. circuit_build_times_reset(cbt);
  1293. if (cbt->liveness.timeouts_after_firsthop &&
  1294. cbt->liveness.num_recent_circs > 0) {
  1295. memset(cbt->liveness.timeouts_after_firsthop, 0,
  1296. sizeof(*cbt->liveness.timeouts_after_firsthop)*
  1297. cbt->liveness.num_recent_circs);
  1298. }
  1299. cbt->liveness.after_firsthop_idx = 0;
  1300. /* Check to see if this has happened before. If so, double the timeout
  1301. * to give people on abysmally bad network connections a shot at access */
  1302. if (cbt->timeout_ms >= circuit_build_times_get_initial_timeout()) {
  1303. if (cbt->timeout_ms > INT32_MAX/2 || cbt->close_ms > INT32_MAX/2) {
  1304. log_warn(LD_CIRC, "Insanely large circuit build timeout value. "
  1305. "(timeout = %fmsec, close = %fmsec)",
  1306. cbt->timeout_ms, cbt->close_ms);
  1307. } else {
  1308. cbt->timeout_ms *= 2;
  1309. cbt->close_ms *= 2;
  1310. }
  1311. } else {
  1312. cbt->close_ms = cbt->timeout_ms
  1313. = circuit_build_times_get_initial_timeout();
  1314. }
  1315. control_event_buildtimeout_set(cbt, BUILDTIMEOUT_SET_EVENT_RESET);
  1316. log_notice(LD_CIRC,
  1317. "Your network connection speed appears to have changed. Resetting "
  1318. "timeout to %lds after %d timeouts and %d buildtimes.",
  1319. tor_lround(cbt->timeout_ms/1000), timeout_count,
  1320. total_build_times);
  1321. return 1;
  1322. }
  1323. /**
  1324. * Count the number of timeouts in a set of cbt data.
  1325. */
  1326. double
  1327. circuit_build_times_timeout_rate(const circuit_build_times_t *cbt)
  1328. {
  1329. int i=0,timeouts=0;
  1330. for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
  1331. if (cbt->circuit_build_times[i] >= cbt->timeout_ms) {
  1332. timeouts++;
  1333. }
  1334. }
  1335. if (!cbt->total_build_times)
  1336. return 0;
  1337. return ((double)timeouts)/cbt->total_build_times;
  1338. }
  1339. /**
  1340. * Count the number of closed circuits in a set of cbt data.
  1341. */
  1342. double
  1343. circuit_build_times_close_rate(const circuit_build_times_t *cbt)
  1344. {
  1345. int i=0,closed=0;
  1346. for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
  1347. if (cbt->circuit_build_times[i] == CBT_BUILD_ABANDONED) {
  1348. closed++;
  1349. }
  1350. }
  1351. if (!cbt->total_build_times)
  1352. return 0;
  1353. return ((double)closed)/cbt->total_build_times;
  1354. }
  1355. /**
  1356. * Store a timeout as a synthetic value.
  1357. *
  1358. * Returns true if the store was successful and we should possibly
  1359. * update our timeout estimate.
  1360. */
  1361. int
  1362. circuit_build_times_count_close(circuit_build_times_t *cbt,
  1363. int did_onehop,
  1364. time_t start_time)
  1365. {
  1366. if (circuit_build_times_disabled()) {
  1367. cbt->close_ms = cbt->timeout_ms
  1368. = circuit_build_times_get_initial_timeout();
  1369. return 0;
  1370. }
  1371. /* Record this force-close to help determine if the network is dead */
  1372. circuit_build_times_network_close(cbt, did_onehop, start_time);
  1373. /* Only count timeouts if network is live.. */
  1374. if (!circuit_build_times_network_check_live(cbt)) {
  1375. return 0;
  1376. }
  1377. circuit_build_times_add_time(cbt, CBT_BUILD_ABANDONED);
  1378. return 1;
  1379. }
  1380. /**
  1381. * Update timeout counts to determine if we need to expire
  1382. * our build time history due to excessive timeouts.
  1383. *
  1384. * We do not record any actual time values at this stage;
  1385. * we are only interested in recording the fact that a timeout
  1386. * happened. We record the time values via
  1387. * circuit_build_times_count_close() and circuit_build_times_add_time().
  1388. */
  1389. void
  1390. circuit_build_times_count_timeout(circuit_build_times_t *cbt,
  1391. int did_onehop)
  1392. {
  1393. if (circuit_build_times_disabled()) {
  1394. cbt->close_ms = cbt->timeout_ms
  1395. = circuit_build_times_get_initial_timeout();
  1396. return;
  1397. }
  1398. /* Register the fact that a timeout just occurred. */
  1399. circuit_build_times_network_timeout(cbt, did_onehop);
  1400. /* If there are a ton of timeouts, we should reset
  1401. * the circuit build timeout. */
  1402. circuit_build_times_network_check_changed(cbt);
  1403. }
  1404. /**
  1405. * Estimate a new timeout based on history and set our timeout
  1406. * variable accordingly.
  1407. */
  1408. static int
  1409. circuit_build_times_set_timeout_worker(circuit_build_times_t *cbt)
  1410. {
  1411. build_time_t max_time;
  1412. if (!circuit_build_times_enough_to_compute(cbt))
  1413. return 0;
  1414. if (!circuit_build_times_update_alpha(cbt))
  1415. return 0;
  1416. cbt->timeout_ms = circuit_build_times_calculate_timeout(cbt,
  1417. circuit_build_times_quantile_cutoff());
  1418. cbt->close_ms = circuit_build_times_calculate_timeout(cbt,
  1419. circuit_build_times_close_quantile());
  1420. max_time = circuit_build_times_max(cbt);
  1421. /* Sometimes really fast guard nodes give us such a steep curve
  1422. * that this ends up being not that much greater than timeout_ms.
  1423. * Make it be at least 1 min to handle this case. */
  1424. cbt->close_ms = MAX(cbt->close_ms, circuit_build_times_initial_timeout());
  1425. if (cbt->timeout_ms > max_time) {
  1426. log_info(LD_CIRC,
  1427. "Circuit build timeout of %dms is beyond the maximum build "
  1428. "time we have ever observed. Capping it to %dms.",
  1429. (int)cbt->timeout_ms, max_time);
  1430. cbt->timeout_ms = max_time;
  1431. }
  1432. if (max_time < INT32_MAX/2 && cbt->close_ms > 2*max_time) {
  1433. log_info(LD_CIRC,
  1434. "Circuit build measurement period of %dms is more than twice "
  1435. "the maximum build time we have ever observed. Capping it to "
  1436. "%dms.", (int)cbt->close_ms, 2*max_time);
  1437. cbt->close_ms = 2*max_time;
  1438. }
  1439. cbt->have_computed_timeout = 1;
  1440. return 1;
  1441. }
  1442. /**
  1443. * Exposed function to compute a new timeout. Dispatches events and
  1444. * also filters out extremely high timeout values.
  1445. */
  1446. void
  1447. circuit_build_times_set_timeout(circuit_build_times_t *cbt)
  1448. {
  1449. long prev_timeout = tor_lround(cbt->timeout_ms/1000);
  1450. double timeout_rate;
  1451. /*
  1452. * Just return if we aren't using adaptive timeouts
  1453. */
  1454. if (circuit_build_times_disabled())
  1455. return;
  1456. if (!circuit_build_times_set_timeout_worker(cbt))
  1457. return;
  1458. if (cbt->timeout_ms < circuit_build_times_min_timeout()) {
  1459. log_info(LD_CIRC, "Set buildtimeout to low value %fms. Setting to %dms",
  1460. cbt->timeout_ms, circuit_build_times_min_timeout());
  1461. cbt->timeout_ms = circuit_build_times_min_timeout();
  1462. if (cbt->close_ms < cbt->timeout_ms) {
  1463. /* This shouldn't happen because of MAX() in timeout_worker above,
  1464. * but doing it just in case */
  1465. cbt->close_ms = circuit_build_times_initial_timeout();
  1466. }
  1467. }
  1468. control_event_buildtimeout_set(cbt, BUILDTIMEOUT_SET_EVENT_COMPUTED);
  1469. timeout_rate = circuit_build_times_timeout_rate(cbt);
  1470. if (prev_timeout > tor_lround(cbt->timeout_ms/1000)) {
  1471. log_info(LD_CIRC,
  1472. "Based on %d circuit times, it looks like we don't need to "
  1473. "wait so long for circuits to finish. We will now assume a "
  1474. "circuit is too slow to use after waiting %ld seconds.",
  1475. cbt->total_build_times,
  1476. tor_lround(cbt->timeout_ms/1000));
  1477. log_info(LD_CIRC,
  1478. "Circuit timeout data: %fms, %fms, Xm: %d, a: %f, r: %f",
  1479. cbt->timeout_ms, cbt->close_ms, cbt->Xm, cbt->alpha,
  1480. timeout_rate);
  1481. } else if (prev_timeout < tor_lround(cbt->timeout_ms/1000)) {
  1482. log_info(LD_CIRC,
  1483. "Based on %d circuit times, it looks like we need to wait "
  1484. "longer for circuits to finish. We will now assume a "
  1485. "circuit is too slow to use after waiting %ld seconds.",
  1486. cbt->total_build_times,
  1487. tor_lround(cbt->timeout_ms/1000));
  1488. log_info(LD_CIRC,
  1489. "Circuit timeout data: %fms, %fms, Xm: %d, a: %f, r: %f",
  1490. cbt->timeout_ms, cbt->close_ms, cbt->Xm, cbt->alpha,
  1491. timeout_rate);
  1492. } else {
  1493. log_info(LD_CIRC,
  1494. "Set circuit build timeout to %lds (%fms, %fms, Xm: %d, a: %f,"
  1495. " r: %f) based on %d circuit times",
  1496. tor_lround(cbt->timeout_ms/1000),
  1497. cbt->timeout_ms, cbt->close_ms, cbt->Xm, cbt->alpha, timeout_rate,
  1498. cbt->total_build_times);
  1499. }
  1500. }
  1501. /** Iterate over values of circ_id, starting from conn-\>next_circ_id,
  1502. * and with the high bit specified by conn-\>circ_id_type, until we get
  1503. * a circ_id that is not in use by any other circuit on that conn.
  1504. *
  1505. * Return it, or 0 if can't get a unique circ_id.
  1506. */
  1507. static circid_t
  1508. get_unique_circ_id_by_chan(channel_t *chan)
  1509. {
  1510. circid_t test_circ_id;
  1511. circid_t attempts=0;
  1512. circid_t high_bit;
  1513. tor_assert(chan);
  1514. if (chan->circ_id_type == CIRC_ID_TYPE_NEITHER) {
  1515. log_warn(LD_BUG,
  1516. "Trying to pick a circuit ID for a connection from "
  1517. "a client with no identity.");
  1518. return 0;
  1519. }
  1520. high_bit =
  1521. (chan->circ_id_type == CIRC_ID_TYPE_HIGHER) ? 1<<15 : 0;
  1522. do {
  1523. /* Sequentially iterate over test_circ_id=1...1<<15-1 until we find a
  1524. * circID such that (high_bit|test_circ_id) is not already used. */
  1525. test_circ_id = chan->next_circ_id++;
  1526. if (test_circ_id == 0 || test_circ_id >= 1<<15) {
  1527. test_circ_id = 1;
  1528. chan->next_circ_id = 2;
  1529. }
  1530. if (++attempts > 1<<15) {
  1531. /* Make sure we don't loop forever if all circ_id's are used. This
  1532. * matters because it's an external DoS opportunity.
  1533. */
  1534. log_warn(LD_CIRC,"No unused circ IDs. Failing.");
  1535. return 0;
  1536. }
  1537. test_circ_id |= high_bit;
  1538. } while (circuit_id_in_use_on_channel(test_circ_id, chan));
  1539. return test_circ_id;
  1540. }
  1541. /** If <b>verbose</b> is false, allocate and return a comma-separated list of
  1542. * the currently built elements of <b>circ</b>. If <b>verbose</b> is true, also
  1543. * list information about link status in a more verbose format using spaces.
  1544. * If <b>verbose_names</b> is false, give nicknames for Named routers and hex
  1545. * digests for others; if <b>verbose_names</b> is true, use $DIGEST=Name style
  1546. * names.
  1547. */
  1548. static char *
  1549. circuit_list_path_impl(origin_circuit_t *circ, int verbose, int verbose_names)
  1550. {
  1551. crypt_path_t *hop;
  1552. smartlist_t *elements;
  1553. const char *states[] = {"closed", "waiting for keys", "open"};
  1554. char *s;
  1555. elements = smartlist_new();
  1556. if (verbose) {
  1557. const char *nickname = build_state_get_exit_nickname(circ->build_state);
  1558. smartlist_add_asprintf(elements, "%s%s circ (length %d%s%s):",
  1559. circ->build_state->is_internal ? "internal" : "exit",
  1560. circ->build_state->need_uptime ? " (high-uptime)" : "",
  1561. circ->build_state->desired_path_len,
  1562. circ->_base.state == CIRCUIT_STATE_OPEN ? "" : ", last hop ",
  1563. circ->_base.state == CIRCUIT_STATE_OPEN ? "" :
  1564. (nickname?nickname:"*unnamed*"));
  1565. }
  1566. hop = circ->cpath;
  1567. do {
  1568. char *elt;
  1569. const char *id;
  1570. const node_t *node;
  1571. if (!hop)
  1572. break;
  1573. if (!verbose && hop->state != CPATH_STATE_OPEN)
  1574. break;
  1575. if (!hop->extend_info)
  1576. break;
  1577. id = hop->extend_info->identity_digest;
  1578. if (verbose_names) {
  1579. elt = tor_malloc(MAX_VERBOSE_NICKNAME_LEN+1);
  1580. if ((node = node_get_by_id(id))) {
  1581. node_get_verbose_nickname(node, elt);
  1582. } else if (is_legal_nickname(hop->extend_info->nickname)) {
  1583. elt[0] = '$';
  1584. base16_encode(elt+1, HEX_DIGEST_LEN+1, id, DIGEST_LEN);
  1585. elt[HEX_DIGEST_LEN+1]= '~';
  1586. strlcpy(elt+HEX_DIGEST_LEN+2,
  1587. hop->extend_info->nickname, MAX_NICKNAME_LEN+1);
  1588. } else {
  1589. elt[0] = '$';
  1590. base16_encode(elt+1, HEX_DIGEST_LEN+1, id, DIGEST_LEN);
  1591. }
  1592. } else { /* ! verbose_names */
  1593. node = node_get_by_id(id);
  1594. if (node && node_is_named(node)) {
  1595. elt = tor_strdup(node_get_nickname(node));
  1596. } else {
  1597. elt = tor_malloc(HEX_DIGEST_LEN+2);
  1598. elt[0] = '$';
  1599. base16_encode(elt+1, HEX_DIGEST_LEN+1, id, DIGEST_LEN);
  1600. }
  1601. }
  1602. tor_assert(elt);
  1603. if (verbose) {
  1604. tor_assert(hop->state <= 2);
  1605. smartlist_add_asprintf(elements,"%s(%s)",elt,states[hop->state]);
  1606. tor_free(elt);
  1607. } else {
  1608. smartlist_add(elements, elt);
  1609. }
  1610. hop = hop->next;
  1611. } while (hop != circ->cpath);
  1612. s = smartlist_join_strings(elements, verbose?" ":",", 0, NULL);
  1613. SMARTLIST_FOREACH(elements, char*, cp, tor_free(cp));
  1614. smartlist_free(elements);
  1615. return s;
  1616. }
  1617. /** If <b>verbose</b> is false, allocate and return a comma-separated
  1618. * list of the currently built elements of <b>circ</b>. If
  1619. * <b>verbose</b> is true, also list information about link status in
  1620. * a more verbose format using spaces.
  1621. */
  1622. char *
  1623. circuit_list_path(origin_circuit_t *circ, int verbose)
  1624. {
  1625. return circuit_list_path_impl(circ, verbose, 0);
  1626. }
  1627. /** Allocate and return a comma-separated list of the currently built elements
  1628. * of <b>circ</b>, giving each as a verbose nickname.
  1629. */
  1630. char *
  1631. circuit_list_path_for_controller(origin_circuit_t *circ)
  1632. {
  1633. return circuit_list_path_impl(circ, 0, 1);
  1634. }
  1635. /** Log, at severity <b>severity</b>, the nicknames of each router in
  1636. * <b>circ</b>'s cpath. Also log the length of the cpath, and the intended
  1637. * exit point.
  1638. */
  1639. void
  1640. circuit_log_path(int severity, unsigned int domain, origin_circuit_t *circ)
  1641. {
  1642. char *s = circuit_list_path(circ,1);
  1643. tor_log(severity,domain,"%s",s);
  1644. tor_free(s);
  1645. }
  1646. /** Tell the rep(utation)hist(ory) module about the status of the links
  1647. * in <b>circ</b>. Hops that have become OPEN are marked as successfully
  1648. * extended; the _first_ hop that isn't open (if any) is marked as
  1649. * unable to extend.
  1650. */
  1651. /* XXXX Someday we should learn from OR circuits too. */
  1652. void
  1653. circuit_rep_hist_note_result(origin_circuit_t *circ)
  1654. {
  1655. crypt_path_t *hop;
  1656. const char *prev_digest = NULL;
  1657. hop = circ->cpath;
  1658. if (!hop) /* circuit hasn't started building yet. */
  1659. return;
  1660. if (server_mode(get_options())) {
  1661. const routerinfo_t *me = router_get_my_routerinfo();
  1662. if (!me)
  1663. return;
  1664. prev_digest = me->cache_info.identity_digest;
  1665. }
  1666. do {
  1667. const node_t *node = node_get_by_id(hop->extend_info->identity_digest);
  1668. if (node) { /* Why do we check this? We know the identity. -NM XXXX */
  1669. if (prev_digest) {
  1670. if (hop->state == CPATH_STATE_OPEN)
  1671. rep_hist_note_extend_succeeded(prev_digest, node->identity);
  1672. else {
  1673. rep_hist_note_extend_failed(prev_digest, node->identity);
  1674. break;
  1675. }
  1676. }
  1677. prev_digest = node->identity;
  1678. } else {
  1679. prev_digest = NULL;
  1680. }
  1681. hop=hop->next;
  1682. } while (hop!=circ->cpath);
  1683. }
  1684. /** Pick all the entries in our cpath. Stop and return 0 when we're
  1685. * happy, or return -1 if an error occurs. */
  1686. static int
  1687. onion_populate_cpath(origin_circuit_t *circ)
  1688. {
  1689. int r;
  1690. again:
  1691. r = onion_extend_cpath(circ);
  1692. if (r < 0) {
  1693. log_info(LD_CIRC,"Generating cpath hop failed.");
  1694. return -1;
  1695. }
  1696. if (r == 0)
  1697. goto again;
  1698. return 0; /* if r == 1 */
  1699. }
  1700. /** Create and return a new origin circuit. Initialize its purpose and
  1701. * build-state based on our arguments. The <b>flags</b> argument is a
  1702. * bitfield of CIRCLAUNCH_* flags. */
  1703. origin_circuit_t *
  1704. origin_circuit_init(uint8_t purpose, int flags)
  1705. {
  1706. /* sets circ->p_circ_id and circ->p_chan */
  1707. origin_circuit_t *circ = origin_circuit_new();
  1708. circuit_set_state(TO_CIRCUIT(circ), CIRCUIT_STATE_CHAN_WAIT);
  1709. circ->build_state = tor_malloc_zero(sizeof(cpath_build_state_t));
  1710. circ->build_state->onehop_tunnel =
  1711. ((flags & CIRCLAUNCH_ONEHOP_TUNNEL) ? 1 : 0);
  1712. circ->build_state->need_uptime =
  1713. ((flags & CIRCLAUNCH_NEED_UPTIME) ? 1 : 0);
  1714. circ->build_state->need_capacity =
  1715. ((flags & CIRCLAUNCH_NEED_CAPACITY) ? 1 : 0);
  1716. circ->build_state->is_internal =
  1717. ((flags & CIRCLAUNCH_IS_INTERNAL) ? 1 : 0);
  1718. circ->_base.purpose = purpose;
  1719. return circ;
  1720. }
  1721. /** Build a new circuit for <b>purpose</b>. If <b>exit</b>
  1722. * is defined, then use that as your exit router, else choose a suitable
  1723. * exit node.
  1724. *
  1725. * Also launch a connection to the first OR in the chosen path, if
  1726. * it's not open already.
  1727. */
  1728. origin_circuit_t *
  1729. circuit_establish_circuit(uint8_t purpose, extend_info_t *exit, int flags)
  1730. {
  1731. origin_circuit_t *circ;
  1732. int err_reason = 0;
  1733. circ = origin_circuit_init(purpose, flags);
  1734. if (onion_pick_cpath_exit(circ, exit) < 0 ||
  1735. onion_populate_cpath(circ) < 0) {
  1736. circuit_mark_for_close(TO_CIRCUIT(circ), END_CIRC_REASON_NOPATH);
  1737. return NULL;
  1738. }
  1739. control_event_circuit_status(circ, CIRC_EVENT_LAUNCHED, 0);
  1740. if ((err_reason = circuit_handle_first_hop(circ)) < 0) {
  1741. circuit_mark_for_close(TO_CIRCUIT(circ), -err_reason);
  1742. return NULL;
  1743. }
  1744. return circ;
  1745. }
  1746. /** Start establishing the first hop of our circuit. Figure out what
  1747. * OR we should connect to, and if necessary start the connection to
  1748. * it. If we're already connected, then send the 'create' cell.
  1749. * Return 0 for ok, -reason if circ should be marked-for-close. */
  1750. int
  1751. circuit_handle_first_hop(origin_circuit_t *circ)
  1752. {
  1753. crypt_path_t *firsthop;
  1754. channel_t *n_chan;
  1755. int err_reason = 0;
  1756. const char *msg = NULL;
  1757. int should_launch = 0;
  1758. firsthop = onion_next_hop_in_cpath(circ->cpath);
  1759. tor_assert(firsthop);
  1760. tor_assert(firsthop->extend_info);
  1761. /* now see if we're already connected to the first OR in 'route' */
  1762. log_debug(LD_CIRC,"Looking for firsthop '%s:%u'",
  1763. fmt_addr(&firsthop->extend_info->addr),
  1764. firsthop->extend_info->port);
  1765. n_chan = channel_get_for_extend(firsthop->extend_info->identity_digest,
  1766. &firsthop->extend_info->addr,
  1767. &msg,
  1768. &should_launch);
  1769. if (!n_chan) {
  1770. /* not currently connected in a useful way. */
  1771. log_info(LD_CIRC, "Next router is %s: %s",
  1772. safe_str_client(extend_info_describe(firsthop->extend_info)),
  1773. msg?msg:"???");
  1774. circ->_base.n_hop = extend_info_dup(firsthop->extend_info);
  1775. if (should_launch) {
  1776. if (circ->build_state->onehop_tunnel)
  1777. control_event_bootstrap(BOOTSTRAP_STATUS_CONN_DIR, 0);
  1778. n_chan = channel_connect_for_circuit(
  1779. &firsthop->extend_info->addr,
  1780. firsthop->extend_info->port,
  1781. firsthop->extend_info->identity_digest);
  1782. if (!n_chan) { /* connect failed, forget the whole thing */
  1783. log_info(LD_CIRC,"connect to firsthop failed. Closing.");
  1784. return -END_CIRC_REASON_CONNECTFAILED;
  1785. }
  1786. }
  1787. log_debug(LD_CIRC,"connecting in progress (or finished). Good.");
  1788. /* return success. The onion/circuit/etc will be taken care of
  1789. * automatically (may already have been) whenever n_chan reaches
  1790. * OR_CONN_STATE_OPEN.
  1791. */
  1792. return 0;
  1793. } else { /* it's already open. use it. */
  1794. tor_assert(!circ->_base.n_hop);
  1795. circ->_base.n_chan = n_chan;
  1796. log_debug(LD_CIRC,"Conn open. Delivering first onion skin.");
  1797. if ((err_reason = circuit_send_next_onion_skin(circ)) < 0) {
  1798. log_info(LD_CIRC,"circuit_send_next_onion_skin failed.");
  1799. return err_reason;
  1800. }
  1801. }
  1802. return 0;
  1803. }
  1804. /** Find any circuits that are waiting on <b>or_conn</b> to become
  1805. * open and get them to send their create cells forward.
  1806. *
  1807. * Status is 1 if connect succeeded, or 0 if connect failed.
  1808. */
  1809. void
  1810. circuit_n_chan_done(channel_t *chan, int status)
  1811. {
  1812. smartlist_t *pending_circs;
  1813. int err_reason = 0;
  1814. tor_assert(chan);
  1815. log_debug(LD_CIRC,"chan to %s/%s, status=%d",
  1816. chan->nickname ? chan->nickname : "NULL",
  1817. channel_get_canonical_remote_descr(chan), status);
  1818. pending_circs = smartlist_new();
  1819. circuit_get_all_pending_on_channel(pending_circs, chan);
  1820. SMARTLIST_FOREACH_BEGIN(pending_circs, circuit_t *, circ)
  1821. {
  1822. /* These checks are redundant wrt get_all_pending_on_or_conn, but I'm
  1823. * leaving them in in case it's possible for the status of a circuit to
  1824. * change as we're going down the list. */
  1825. if (circ->marked_for_close || circ->n_chan || !circ->n_hop ||
  1826. circ->state != CIRCUIT_STATE_CHAN_WAIT)
  1827. continue;
  1828. if (tor_digest_is_zero(circ->n_hop->identity_digest)) {
  1829. /* Look at addr/port. This is an unkeyed connection. */
  1830. if (!channel_matches_extend_info(chan, circ->n_hop))
  1831. continue;
  1832. } else {
  1833. /* We expected a key. See if it's the right one. */
  1834. if (tor_memneq(chan->identity_digest,
  1835. circ->n_hop->identity_digest, DIGEST_LEN))
  1836. continue;
  1837. }
  1838. if (!status) { /* chan failed; close circ */
  1839. log_info(LD_CIRC,"Channel failed; closing circ.");
  1840. circuit_mark_for_close(circ, END_CIRC_REASON_CHANNEL_CLOSED);
  1841. continue;
  1842. }
  1843. log_debug(LD_CIRC, "Found circ, sending create cell.");
  1844. /* circuit_deliver_create_cell will set n_circ_id and add us to
  1845. * chan_circuid_circuit_map, so we don't need to call
  1846. * set_circid_chan here. */
  1847. circ->n_chan = chan;
  1848. extend_info_free(circ->n_hop);
  1849. circ->n_hop = NULL;
  1850. if (CIRCUIT_IS_ORIGIN(circ)) {
  1851. if ((err_reason =
  1852. circuit_send_next_onion_skin(TO_ORIGIN_CIRCUIT(circ))) < 0) {
  1853. log_info(LD_CIRC,
  1854. "send_next_onion_skin failed; circuit marked for closing.");
  1855. circuit_mark_for_close(circ, -err_reason);
  1856. continue;
  1857. /* XXX could this be bad, eg if next_onion_skin failed because conn
  1858. * died? */
  1859. }
  1860. } else {
  1861. /* pull the create cell out of circ->onionskin, and send it */
  1862. tor_assert(circ->n_chan_onionskin);
  1863. if (circuit_deliver_create_cell(circ,CELL_CREATE,
  1864. circ->n_chan_onionskin)<0) {
  1865. circuit_mark_for_close(circ, END_CIRC_REASON_RESOURCELIMIT);
  1866. continue;
  1867. }
  1868. tor_free(circ->n_chan_onionskin);
  1869. circuit_set_state(circ, CIRCUIT_STATE_OPEN);
  1870. }
  1871. }
  1872. SMARTLIST_FOREACH_END(circ);
  1873. smartlist_free(pending_circs);
  1874. }
  1875. /** Find a new circid that isn't currently in use on the circ->n_chan
  1876. * for the outgoing
  1877. * circuit <b>circ</b>, and deliver a cell of type <b>cell_type</b>
  1878. * (either CELL_CREATE or CELL_CREATE_FAST) with payload <b>payload</b>
  1879. * to this circuit.
  1880. * Return -1 if we failed to find a suitable circid, else return 0.
  1881. */
  1882. static int
  1883. circuit_deliver_create_cell(circuit_t *circ, uint8_t cell_type,
  1884. const char *payload)
  1885. {
  1886. cell_t cell;
  1887. circid_t id;
  1888. tor_assert(circ);
  1889. tor_assert(circ->n_chan);
  1890. tor_assert(payload);
  1891. tor_assert(cell_type == CELL_CREATE || cell_type == CELL_CREATE_FAST);
  1892. id = get_unique_circ_id_by_chan(circ->n_chan);
  1893. if (!id) {
  1894. log_warn(LD_CIRC,"failed to get unique circID.");
  1895. return -1;
  1896. }
  1897. log_debug(LD_CIRC,"Chosen circID %u.", id);
  1898. circuit_set_n_circid_chan(circ, id, circ->n_chan);
  1899. memset(&cell, 0, sizeof(cell_t));
  1900. cell.command = cell_type;
  1901. cell.circ_id = circ->n_circ_id;
  1902. memcpy(cell.payload, payload, ONIONSKIN_CHALLENGE_LEN);
  1903. append_cell_to_circuit_queue(circ, circ->n_chan, &cell,
  1904. CELL_DIRECTION_OUT, 0);
  1905. if (CIRCUIT_IS_ORIGIN(circ)) {
  1906. /* mark it so it gets better rate limiting treatment. */
  1907. channel_timestamp_client(circ->n_chan);
  1908. }
  1909. return 0;
  1910. }
  1911. /** We've decided to start our reachability testing. If all
  1912. * is set, log this to the user. Return 1 if we did, or 0 if
  1913. * we chose not to log anything. */
  1914. int
  1915. inform_testing_reachability(void)
  1916. {
  1917. char dirbuf[128];
  1918. const routerinfo_t *me = router_get_my_routerinfo();
  1919. if (!me)
  1920. return 0;
  1921. control_event_server_status(LOG_NOTICE,
  1922. "CHECKING_REACHABILITY ORADDRESS=%s:%d",
  1923. me->address, me->or_port);
  1924. if (me->dir_port) {
  1925. tor_snprintf(dirbuf, sizeof(dirbuf), " and DirPort %s:%d",
  1926. me->address, me->dir_port);
  1927. control_event_server_status(LOG_NOTICE,
  1928. "CHECKING_REACHABILITY DIRADDRESS=%s:%d",
  1929. me->address, me->dir_port);
  1930. }
  1931. log_notice(LD_OR, "Now checking whether ORPort %s:%d%s %s reachable... "
  1932. "(this may take up to %d minutes -- look for log "
  1933. "messages indicating success)",
  1934. me->address, me->or_port,
  1935. me->dir_port ? dirbuf : "",
  1936. me->dir_port ? "are" : "is",
  1937. TIMEOUT_UNTIL_UNREACHABILITY_COMPLAINT/60);
  1938. return 1;
  1939. }
  1940. /** Return true iff we should send a create_fast cell to start building a given
  1941. * circuit */
  1942. static INLINE int
  1943. should_use_create_fast_for_circuit(origin_circuit_t *circ)
  1944. {
  1945. const or_options_t *options = get_options();
  1946. tor_assert(circ->cpath);
  1947. tor_assert(circ->cpath->extend_info);
  1948. if (!circ->cpath->extend_info->onion_key)
  1949. return 1; /* our hand is forced: only a create_fast will work. */
  1950. if (!options->FastFirstHopPK)
  1951. return 0; /* we prefer to avoid create_fast */
  1952. if (public_server_mode(options)) {
  1953. /* We're a server, and we know an onion key. We can choose.
  1954. * Prefer to blend our circuit into the other circuits we are
  1955. * creating on behalf of others. */
  1956. return 0;
  1957. }
  1958. return 1;
  1959. }
  1960. /** Return true if <b>circ</b> is the type of circuit we want to count
  1961. * timeouts from. In particular, we want it to have not completed yet
  1962. * (already completing indicates we cannibalized it), and we want it to
  1963. * have exactly three hops.
  1964. */
  1965. int
  1966. circuit_timeout_want_to_count_circ(origin_circuit_t *circ)
  1967. {
  1968. return !circ->has_opened
  1969. && circ->build_state->desired_path_len == DEFAULT_ROUTE_LEN;
  1970. }
  1971. /** This is the backbone function for building circuits.
  1972. *
  1973. * If circ's first hop is closed, then we need to build a create
  1974. * cell and send it forward.
  1975. *
  1976. * Otherwise, we need to build a relay extend cell and send it
  1977. * forward.
  1978. *
  1979. * Return -reason if we want to tear down circ, else return 0.
  1980. */
  1981. int
  1982. circuit_send_next_onion_skin(origin_circuit_t *circ)
  1983. {
  1984. crypt_path_t *hop;
  1985. const node_t *node;
  1986. char payload[2+4+DIGEST_LEN+ONIONSKIN_CHALLENGE_LEN];
  1987. char *onionskin;
  1988. size_t payload_len;
  1989. tor_assert(circ);
  1990. if (circ->cpath->state == CPATH_STATE_CLOSED) {
  1991. int fast;
  1992. uint8_t cell_type;
  1993. log_debug(LD_CIRC,"First skin; sending create cell.");
  1994. if (circ->build_state->onehop_tunnel)
  1995. control_event_bootstrap(BOOTSTRAP_STATUS_ONEHOP_CREATE, 0);
  1996. else
  1997. control_event_bootstrap(BOOTSTRAP_STATUS_CIRCUIT_CREATE, 0);
  1998. node = node_get_by_id(circ->_base.n_chan->identity_digest);
  1999. fast = should_use_create_fast_for_circuit(circ);
  2000. if (!fast) {
  2001. /* We are an OR and we know the right onion key: we should
  2002. * send an old slow create cell.
  2003. */
  2004. cell_type = CELL_CREATE;
  2005. if (onion_skin_create(circ->cpath->extend_info->onion_key,
  2006. &(circ->cpath->dh_handshake_state),
  2007. payload) < 0) {
  2008. log_warn(LD_CIRC,"onion_skin_create (first hop) failed.");
  2009. return - END_CIRC_REASON_INTERNAL;
  2010. }
  2011. note_request("cell: create", 1);
  2012. } else {
  2013. /* We are not an OR, and we're building the first hop of a circuit to a
  2014. * new OR: we can be speedy and use CREATE_FAST to save an RSA operation
  2015. * and a DH operation. */
  2016. cell_type = CELL_CREATE_FAST;
  2017. memset(payload, 0, sizeof(payload));
  2018. crypto_rand((char*) circ->cpath->fast_handshake_state,
  2019. sizeof(circ->cpath->fast_handshake_state));
  2020. memcpy(payload, circ->cpath->fast_handshake_state,
  2021. sizeof(circ->cpath->fast_handshake_state));
  2022. note_request("cell: create fast", 1);
  2023. }
  2024. if (circuit_deliver_create_cell(TO_CIRCUIT(circ), cell_type, payload) < 0)
  2025. return - END_CIRC_REASON_RESOURCELIMIT;
  2026. circ->cpath->state = CPATH_STATE_AWAITING_KEYS;
  2027. circuit_set_state(TO_CIRCUIT(circ), CIRCUIT_STATE_BUILDING);
  2028. log_info(LD_CIRC,"First hop: finished sending %s cell to '%s'",
  2029. fast ? "CREATE_FAST" : "CREATE",
  2030. node ? node_describe(node) : "<unnamed>");
  2031. } else {
  2032. tor_assert(circ->cpath->state == CPATH_STATE_OPEN);
  2033. tor_assert(circ->_base.state == CIRCUIT_STATE_BUILDING);
  2034. log_debug(LD_CIRC,"starting to send subsequent skin.");
  2035. hop = onion_next_hop_in_cpath(circ->cpath);
  2036. if (!hop) {
  2037. /* done building the circuit. whew. */
  2038. circuit_set_state(TO_CIRCUIT(circ), CIRCUIT_STATE_OPEN);
  2039. if (circuit_timeout_want_to_count_circ(circ)) {
  2040. struct timeval end;
  2041. long timediff;
  2042. tor_gettimeofday(&end);
  2043. timediff = tv_mdiff(&circ->_base.timestamp_created, &end);
  2044. /*
  2045. * If the circuit build time is much greater than we would have cut
  2046. * it off at, we probably had a suspend event along this codepath,
  2047. * and we should discard the value.
  2048. */
  2049. if (timediff < 0 || timediff > 2*circ_times.close_ms+1000) {
  2050. log_notice(LD_CIRC, "Strange value for circuit build time: %ldmsec. "
  2051. "Assuming clock jump. Purpose %d (%s)", timediff,
  2052. circ->_base.purpose,
  2053. circuit_purpose_to_string(circ->_base.purpose));
  2054. } else if (!circuit_build_times_disabled()) {
  2055. /* Only count circuit times if the network is live */
  2056. if (circuit_build_times_network_check_live(&circ_times)) {
  2057. circuit_build_times_add_time(&circ_times, (build_time_t)timediff);
  2058. circuit_build_times_set_timeout(&circ_times);
  2059. }
  2060. if (circ->_base.purpose != CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT) {
  2061. circuit_build_times_network_circ_success(&circ_times);
  2062. }
  2063. }
  2064. }
  2065. log_info(LD_CIRC,"circuit built!");
  2066. circuit_reset_failure_count(0);
  2067. if (circ->build_state->onehop_tunnel || circ->has_opened) {
  2068. control_event_bootstrap(BOOTSTRAP_STATUS_REQUESTING_STATUS, 0);
  2069. }
  2070. if (!can_complete_circuit && !circ->build_state->onehop_tunnel) {
  2071. const or_options_t *options = get_options();
  2072. can_complete_circuit=1;
  2073. /* FFFF Log a count of known routers here */
  2074. log_notice(LD_GENERAL,
  2075. "Tor has successfully opened a circuit. "
  2076. "Looks like client functionality is working.");
  2077. control_event_bootstrap(BOOTSTRAP_STATUS_DONE, 0);
  2078. control_event_client_status(LOG_NOTICE, "CIRCUIT_ESTABLISHED");
  2079. clear_broken_connection_map(1);
  2080. if (server_mode(options) && !check_whether_orport_reachable()) {
  2081. inform_testing_reachability();
  2082. consider_testing_reachability(1, 1);
  2083. }
  2084. }
  2085. pathbias_count_success(circ);
  2086. circuit_rep_hist_note_result(circ);
  2087. circuit_has_opened(circ); /* do other actions as necessary */
  2088. /* We're done with measurement circuits here. Just close them */
  2089. if (circ->_base.purpose == CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT)
  2090. circuit_mark_for_close(TO_CIRCUIT(circ), END_CIRC_REASON_FINISHED);
  2091. return 0;
  2092. }
  2093. if (tor_addr_family(&hop->extend_info->addr) != AF_INET) {
  2094. log_warn(LD_BUG, "Trying to extend to a non-IPv4 address.");
  2095. return - END_CIRC_REASON_INTERNAL;
  2096. }
  2097. set_uint32(payload, tor_addr_to_ipv4n(&hop->extend_info->addr));
  2098. set_uint16(payload+4, htons(hop->extend_info->port));
  2099. onionskin = payload+2+4;
  2100. memcpy(payload+2+4+ONIONSKIN_CHALLENGE_LEN,
  2101. hop->extend_info->identity_digest, DIGEST_LEN);
  2102. payload_len = 2+4+ONIONSKIN_CHALLENGE_LEN+DIGEST_LEN;
  2103. if (onion_skin_create(hop->extend_info->onion_key,
  2104. &(hop->dh_handshake_state), onionskin) < 0) {
  2105. log_warn(LD_CIRC,"onion_skin_create failed.");
  2106. return - END_CIRC_REASON_INTERNAL;
  2107. }
  2108. log_info(LD_CIRC,"Sending extend relay cell.");
  2109. note_request("cell: extend", 1);
  2110. /* send it to hop->prev, because it will transfer
  2111. * it to a create cell and then send to hop */
  2112. if (relay_send_command_from_edge(0, TO_CIRCUIT(circ),
  2113. RELAY_COMMAND_EXTEND,
  2114. payload, payload_len, hop->prev) < 0)
  2115. return 0; /* circuit is closed */
  2116. hop->state = CPATH_STATE_AWAITING_KEYS;
  2117. }
  2118. return 0;
  2119. }
  2120. /** Our clock just jumped by <b>seconds_elapsed</b>. Assume
  2121. * something has also gone wrong with our network: notify the user,
  2122. * and abandon all not-yet-used circuits. */
  2123. void
  2124. circuit_note_clock_jumped(int seconds_elapsed)
  2125. {
  2126. int severity = server_mode(get_options()) ? LOG_WARN : LOG_NOTICE;
  2127. tor_log(severity, LD_GENERAL, "Your system clock just jumped %d seconds %s; "
  2128. "assuming established circuits no longer work.",
  2129. seconds_elapsed >=0 ? seconds_elapsed : -seconds_elapsed,
  2130. seconds_elapsed >=0 ? "forward" : "backward");
  2131. control_event_general_status(LOG_WARN, "CLOCK_JUMPED TIME=%d",
  2132. seconds_elapsed);
  2133. can_complete_circuit=0; /* so it'll log when it works again */
  2134. control_event_client_status(severity, "CIRCUIT_NOT_ESTABLISHED REASON=%s",
  2135. "CLOCK_JUMPED");
  2136. circuit_mark_all_unused_circs();
  2137. circuit_expire_all_dirty_circs();
  2138. }
  2139. /** Take the 'extend' <b>cell</b>, pull out addr/port plus the onion
  2140. * skin and identity digest for the next hop. If we're already connected,
  2141. * pass the onion skin to the next hop using a create cell; otherwise
  2142. * launch a new OR connection, and <b>circ</b> will notice when the
  2143. * connection succeeds or fails.
  2144. *
  2145. * Return -1 if we want to warn and tear down the circuit, else return 0.
  2146. */
  2147. int
  2148. circuit_extend(cell_t *cell, circuit_t *circ)
  2149. {
  2150. channel_t *n_chan;
  2151. relay_header_t rh;
  2152. char *onionskin;
  2153. char *id_digest=NULL;
  2154. uint32_t n_addr32;
  2155. uint16_t n_port;
  2156. tor_addr_t n_addr;
  2157. const char *msg = NULL;
  2158. int should_launch = 0;
  2159. if (circ->n_chan) {
  2160. log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
  2161. "n_chan already set. Bug/attack. Closing.");
  2162. return -1;
  2163. }
  2164. if (circ->n_hop) {
  2165. log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
  2166. "conn to next hop already launched. Bug/attack. Closing.");
  2167. return -1;
  2168. }
  2169. if (!server_mode(get_options())) {
  2170. log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
  2171. "Got an extend cell, but running as a client. Closing.");
  2172. return -1;
  2173. }
  2174. relay_header_unpack(&rh, cell->payload);
  2175. if (rh.length < 4+2+ONIONSKIN_CHALLENGE_LEN+DIGEST_LEN) {
  2176. log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
  2177. "Wrong length %d on extend cell. Closing circuit.",
  2178. rh.length);
  2179. return -1;
  2180. }
  2181. n_addr32 = ntohl(get_uint32(cell->payload+RELAY_HEADER_SIZE));
  2182. n_port = ntohs(get_uint16(cell->payload+RELAY_HEADER_SIZE+4));
  2183. onionskin = (char*) cell->payload+RELAY_HEADER_SIZE+4+2;
  2184. id_digest = (char*) cell->payload+RELAY_HEADER_SIZE+4+2+
  2185. ONIONSKIN_CHALLENGE_LEN;
  2186. tor_addr_from_ipv4h(&n_addr, n_addr32);
  2187. if (!n_port || !n_addr32) {
  2188. log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
  2189. "Client asked me to extend to zero destination port or addr.");
  2190. return -1;
  2191. }
  2192. if (tor_addr_is_internal(&n_addr, 0) &&
  2193. !get_options()->ExtendAllowPrivateAddresses) {
  2194. log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
  2195. "Client asked me to extend to a private address");
  2196. return -1;
  2197. }
  2198. /* Check if they asked us for 0000..0000. We support using
  2199. * an empty fingerprint for the first hop (e.g. for a bridge relay),
  2200. * but we don't want to let people send us extend cells for empty
  2201. * fingerprints -- a) because it opens the user up to a mitm attack,
  2202. * and b) because it lets an attacker force the relay to hold open a
  2203. * new TLS connection for each extend request. */
  2204. if (tor_digest_is_zero(id_digest)) {
  2205. log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
  2206. "Client asked me to extend without specifying an id_digest.");
  2207. return -1;
  2208. }
  2209. /* Next, check if we're being asked to connect to the hop that the
  2210. * extend cell came from. There isn't any reason for that, and it can
  2211. * assist circular-path attacks. */
  2212. if (tor_memeq(id_digest,
  2213. TO_OR_CIRCUIT(circ)->p_chan->identity_digest,
  2214. DIGEST_LEN)) {
  2215. log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
  2216. "Client asked me to extend back to the previous hop.");
  2217. return -1;
  2218. }
  2219. n_chan = channel_get_for_extend(id_digest,
  2220. &n_addr,
  2221. &msg,
  2222. &should_launch);
  2223. if (!n_chan) {
  2224. log_debug(LD_CIRC|LD_OR,"Next router (%s:%d): %s",
  2225. fmt_addr(&n_addr), (int)n_port, msg?msg:"????");
  2226. circ->n_hop = extend_info_new(NULL /*nickname*/,
  2227. id_digest,
  2228. NULL /*onion_key*/,
  2229. &n_addr, n_port);
  2230. circ->n_chan_onionskin = tor_malloc(ONIONSKIN_CHALLENGE_LEN);
  2231. memcpy(circ->n_chan_onionskin, onionskin, ONIONSKIN_CHALLENGE_LEN);
  2232. circuit_set_state(circ, CIRCUIT_STATE_CHAN_WAIT);
  2233. if (should_launch) {
  2234. /* we should try to open a connection */
  2235. n_chan = channel_connect_for_circuit(&n_addr, n_port, id_digest);
  2236. if (!n_chan) {
  2237. log_info(LD_CIRC,"Launching n_chan failed. Closing circuit.");
  2238. circuit_mark_for_close(circ, END_CIRC_REASON_CONNECTFAILED);
  2239. return 0;
  2240. }
  2241. log_debug(LD_CIRC,"connecting in progress (or finished). Good.");
  2242. }
  2243. /* return success. The onion/circuit/etc will be taken care of
  2244. * automatically (may already have been) whenever n_chan reaches
  2245. * OR_CONN_STATE_OPEN.
  2246. */
  2247. return 0;
  2248. }
  2249. tor_assert(!circ->n_hop); /* Connection is already established. */
  2250. circ->n_chan = n_chan;
  2251. log_debug(LD_CIRC,
  2252. "n_chan is %s",
  2253. channel_get_canonical_remote_descr(n_chan));
  2254. if (circuit_deliver_create_cell(circ, CELL_CREATE, onionskin) < 0)
  2255. return -1;
  2256. return 0;
  2257. }
  2258. /** Initialize cpath-\>{f|b}_{crypto|digest} from the key material in
  2259. * key_data. key_data must contain CPATH_KEY_MATERIAL bytes, which are
  2260. * used as follows:
  2261. * - 20 to initialize f_digest
  2262. * - 20 to initialize b_digest
  2263. * - 16 to key f_crypto
  2264. * - 16 to key b_crypto
  2265. *
  2266. * (If 'reverse' is true, then f_XX and b_XX are swapped.)
  2267. */
  2268. int
  2269. circuit_init_cpath_crypto(crypt_path_t *cpath, const char *key_data,
  2270. int reverse)
  2271. {
  2272. crypto_digest_t *tmp_digest;
  2273. crypto_cipher_t *tmp_crypto;
  2274. tor_assert(cpath);
  2275. tor_assert(key_data);
  2276. tor_assert(!(cpath->f_crypto || cpath->b_crypto ||
  2277. cpath->f_digest || cpath->b_digest));
  2278. cpath->f_digest = crypto_digest_new();
  2279. crypto_digest_add_bytes(cpath->f_digest, key_data, DIGEST_LEN);
  2280. cpath->b_digest = crypto_digest_new();
  2281. crypto_digest_add_bytes(cpath->b_digest, key_data+DIGEST_LEN, DIGEST_LEN);
  2282. if (!(cpath->f_crypto =
  2283. crypto_cipher_new(key_data+(2*DIGEST_LEN)))) {
  2284. log_warn(LD_BUG,"Forward cipher initialization failed.");
  2285. return -1;
  2286. }
  2287. if (!(cpath->b_crypto =
  2288. crypto_cipher_new(key_data+(2*DIGEST_LEN)+CIPHER_KEY_LEN))) {
  2289. log_warn(LD_BUG,"Backward cipher initialization failed.");
  2290. return -1;
  2291. }
  2292. if (reverse) {
  2293. tmp_digest = cpath->f_digest;
  2294. cpath->f_digest = cpath->b_digest;
  2295. cpath->b_digest = tmp_digest;
  2296. tmp_crypto = cpath->f_crypto;
  2297. cpath->f_crypto = cpath->b_crypto;
  2298. cpath->b_crypto = tmp_crypto;
  2299. }
  2300. return 0;
  2301. }
  2302. /** The minimum number of first hop completions before we start
  2303. * thinking about warning about path bias and dropping guards */
  2304. static int
  2305. pathbias_get_min_circs(const or_options_t *options)
  2306. {
  2307. #define DFLT_PATH_BIAS_MIN_CIRC 20
  2308. if (options->PathBiasCircThreshold >= 5)
  2309. return options->PathBiasCircThreshold;
  2310. else
  2311. return networkstatus_get_param(NULL, "pb_mincircs",
  2312. DFLT_PATH_BIAS_MIN_CIRC,
  2313. 5, INT32_MAX);
  2314. }
  2315. static double
  2316. pathbias_get_notice_rate(const or_options_t *options)
  2317. {
  2318. #define DFLT_PATH_BIAS_NOTICE_PCT 40
  2319. if (options->PathBiasNoticeRate >= 0.0)
  2320. return options->PathBiasNoticeRate;
  2321. else
  2322. return networkstatus_get_param(NULL, "pb_noticepct",
  2323. DFLT_PATH_BIAS_NOTICE_PCT, 0, 100)/100.0;
  2324. }
  2325. static double
  2326. pathbias_get_disable_rate(const or_options_t *options)
  2327. {
  2328. // XXX: This needs tuning based on use + experimentation before we set it
  2329. #define DFLT_PATH_BIAS_DISABLE_PCT 0
  2330. if (options->PathBiasDisableRate >= 0.0)
  2331. return options->PathBiasDisableRate;
  2332. else
  2333. return networkstatus_get_param(NULL, "pb_disablepct",
  2334. DFLT_PATH_BIAS_DISABLE_PCT, 0, 100)/100.0;
  2335. }
  2336. static int
  2337. pathbias_get_scale_threshold(const or_options_t *options)
  2338. {
  2339. #define DFLT_PATH_BIAS_SCALE_THRESHOLD 200
  2340. if (options->PathBiasScaleThreshold >= 2)
  2341. return options->PathBiasScaleThreshold;
  2342. else
  2343. return networkstatus_get_param(NULL, "pb_scalecircs",
  2344. DFLT_PATH_BIAS_SCALE_THRESHOLD, 10,
  2345. INT32_MAX);
  2346. }
  2347. static int
  2348. pathbias_get_scale_factor(const or_options_t *options)
  2349. {
  2350. #define DFLT_PATH_BIAS_SCALE_FACTOR 2
  2351. if (options->PathBiasScaleFactor >= 1)
  2352. return options->PathBiasScaleFactor;
  2353. else
  2354. return networkstatus_get_param(NULL, "pb_scalefactor",
  2355. DFLT_PATH_BIAS_SCALE_FACTOR, 1, INT32_MAX);
  2356. }
  2357. static const char *
  2358. pathbias_state_to_string(path_state_t state)
  2359. {
  2360. switch (state) {
  2361. case PATH_STATE_NEW_CIRC:
  2362. return "new";
  2363. case PATH_STATE_DID_FIRST_HOP:
  2364. return "first hop";
  2365. case PATH_STATE_SUCCEEDED:
  2366. return "succeeded";
  2367. }
  2368. return "unknown";
  2369. }
  2370. /**
  2371. * Check our circuit state to see if this is a successful first hop.
  2372. * If so, record it in the current guard's path bias first_hop count.
  2373. *
  2374. * Also check for several potential error cases for bug #6475.
  2375. */
  2376. static int
  2377. pathbias_count_first_hop(origin_circuit_t *circ)
  2378. {
  2379. #define FIRST_HOP_NOTICE_INTERVAL (600)
  2380. static ratelim_t first_hop_notice_limit =
  2381. RATELIM_INIT(FIRST_HOP_NOTICE_INTERVAL);
  2382. char *rate_msg = NULL;
  2383. /* We can't do path bias accounting without entry guards.
  2384. * Testing and controller circuits also have no guards. */
  2385. if (get_options()->UseEntryGuards == 0 ||
  2386. circ->_base.purpose == CIRCUIT_PURPOSE_TESTING ||
  2387. circ->_base.purpose == CIRCUIT_PURPOSE_CONTROLLER) {
  2388. return 0;
  2389. }
  2390. /* Completely ignore one hop circuits */
  2391. if (circ->build_state->onehop_tunnel ||
  2392. circ->build_state->desired_path_len == 1) {
  2393. /* Check for inconsistency */
  2394. if (circ->build_state->desired_path_len != 1 ||
  2395. !circ->build_state->onehop_tunnel) {
  2396. if ((rate_msg = rate_limit_log(&first_hop_notice_limit,
  2397. approx_time()))) {
  2398. log_notice(LD_BUG,
  2399. "One-hop circuit has length %d. Path state is %s. "
  2400. "Circuit is a %s currently %s.%s",
  2401. circ->build_state->desired_path_len,
  2402. pathbias_state_to_string(circ->path_state),
  2403. circuit_purpose_to_string(circ->_base.purpose),
  2404. circuit_state_to_string(circ->_base.state),
  2405. rate_msg);
  2406. tor_free(rate_msg);
  2407. }
  2408. tor_fragile_assert();
  2409. }
  2410. return 0;
  2411. }
  2412. if (circ->cpath->state == CPATH_STATE_AWAITING_KEYS) {
  2413. /* Help track down the real cause of bug #6475: */
  2414. if (circ->has_opened && circ->path_state != PATH_STATE_DID_FIRST_HOP) {
  2415. if ((rate_msg = rate_limit_log(&first_hop_notice_limit,
  2416. approx_time()))) {
  2417. log_info(LD_BUG,
  2418. "Opened circuit is in strange path state %s. "
  2419. "Circuit is a %s currently %s.%s",
  2420. pathbias_state_to_string(circ->path_state),
  2421. circuit_purpose_to_string(circ->_base.purpose),
  2422. circuit_state_to_string(circ->_base.state),
  2423. rate_msg);
  2424. tor_free(rate_msg);
  2425. }
  2426. }
  2427. /* Don't count cannibalized circs for path bias */
  2428. if (!circ->has_opened) {
  2429. entry_guard_t *guard;
  2430. guard =
  2431. entry_guard_get_by_id_digest(circ->_base.n_chan->identity_digest);
  2432. if (guard) {
  2433. if (circ->path_state == PATH_STATE_NEW_CIRC) {
  2434. circ->path_state = PATH_STATE_DID_FIRST_HOP;
  2435. if (entry_guard_inc_first_hop_count(guard) < 0) {
  2436. /* Bogus guard; we already warned. */
  2437. return -END_CIRC_REASON_TORPROTOCOL;
  2438. }
  2439. } else {
  2440. if ((rate_msg = rate_limit_log(&first_hop_notice_limit,
  2441. approx_time()))) {
  2442. log_info(LD_BUG,
  2443. "Unopened circuit has strange path state %s. "
  2444. "Circuit is a %s currently %s.%s",
  2445. pathbias_state_to_string(circ->path_state),
  2446. circuit_purpose_to_string(circ->_base.purpose),
  2447. circuit_state_to_string(circ->_base.state),
  2448. rate_msg);
  2449. tor_free(rate_msg);
  2450. }
  2451. }
  2452. } else {
  2453. if ((rate_msg = rate_limit_log(&first_hop_notice_limit,
  2454. approx_time()))) {
  2455. log_info(LD_BUG,
  2456. "Unopened circuit has no known guard. "
  2457. "Circuit is a %s currently %s.%s",
  2458. circuit_purpose_to_string(circ->_base.purpose),
  2459. circuit_state_to_string(circ->_base.state),
  2460. rate_msg);
  2461. tor_free(rate_msg);
  2462. }
  2463. }
  2464. }
  2465. } else {
  2466. /* Help track down the real cause of bug #6475: */
  2467. if (circ->path_state == PATH_STATE_NEW_CIRC) {
  2468. if ((rate_msg = rate_limit_log(&first_hop_notice_limit,
  2469. approx_time()))) {
  2470. log_info(LD_BUG,
  2471. "A %s circuit is in cpath state %d (opened: %d). "
  2472. "Circuit is a %s currently %s.%s",
  2473. pathbias_state_to_string(circ->path_state),
  2474. circ->cpath->state, circ->has_opened,
  2475. circuit_purpose_to_string(circ->_base.purpose),
  2476. circuit_state_to_string(circ->_base.state),
  2477. rate_msg);
  2478. tor_free(rate_msg);
  2479. }
  2480. }
  2481. }
  2482. return 0;
  2483. }
  2484. /**
  2485. * Check our circuit state to see if this is a successful circuit
  2486. * completion. If so, record it in the current guard's path bias
  2487. * success count.
  2488. *
  2489. * Also check for several potential error cases for bug #6475.
  2490. */
  2491. static void
  2492. pathbias_count_success(origin_circuit_t *circ)
  2493. {
  2494. #define SUCCESS_NOTICE_INTERVAL (600)
  2495. static ratelim_t success_notice_limit =
  2496. RATELIM_INIT(SUCCESS_NOTICE_INTERVAL);
  2497. char *rate_msg = NULL;
  2498. entry_guard_t *guard = NULL;
  2499. /* We can't do path bias accounting without entry guards.
  2500. * Testing and controller circuits also have no guards. */
  2501. if (get_options()->UseEntryGuards == 0 ||
  2502. circ->_base.purpose == CIRCUIT_PURPOSE_TESTING ||
  2503. circ->_base.purpose == CIRCUIT_PURPOSE_CONTROLLER) {
  2504. return;
  2505. }
  2506. /* Ignore one hop circuits */
  2507. if (circ->build_state->onehop_tunnel ||
  2508. circ->build_state->desired_path_len == 1) {
  2509. /* Check for consistency */
  2510. if (circ->build_state->desired_path_len != 1 ||
  2511. !circ->build_state->onehop_tunnel) {
  2512. if ((rate_msg = rate_limit_log(&success_notice_limit,
  2513. approx_time()))) {
  2514. log_notice(LD_BUG,
  2515. "One-hop circuit has length %d. Path state is %s. "
  2516. "Circuit is a %s currently %s.%s",
  2517. circ->build_state->desired_path_len,
  2518. pathbias_state_to_string(circ->path_state),
  2519. circuit_purpose_to_string(circ->_base.purpose),
  2520. circuit_state_to_string(circ->_base.state),
  2521. rate_msg);
  2522. tor_free(rate_msg);
  2523. }
  2524. tor_fragile_assert();
  2525. }
  2526. return;
  2527. }
  2528. /* Don't count cannibalized/reused circs for path bias */
  2529. if (!circ->has_opened) {
  2530. guard =
  2531. entry_guard_get_by_id_digest(circ->_base.n_chan->identity_digest);
  2532. if (guard) {
  2533. if (circ->path_state == PATH_STATE_DID_FIRST_HOP) {
  2534. circ->path_state = PATH_STATE_SUCCEEDED;
  2535. guard->circuit_successes++;
  2536. log_info(LD_PROTOCOL, "Got success count %u/%u for guard %s=%s",
  2537. guard->circuit_successes, guard->first_hops,
  2538. guard->nickname, hex_str(guard->identity, DIGEST_LEN));
  2539. } else {
  2540. if ((rate_msg = rate_limit_log(&success_notice_limit,
  2541. approx_time()))) {
  2542. log_info(LD_BUG,
  2543. "Succeeded circuit is in strange path state %s. "
  2544. "Circuit is a %s currently %s.%s",
  2545. pathbias_state_to_string(circ->path_state),
  2546. circuit_purpose_to_string(circ->_base.purpose),
  2547. circuit_state_to_string(circ->_base.state),
  2548. rate_msg);
  2549. tor_free(rate_msg);
  2550. }
  2551. }
  2552. if (guard->first_hops < guard->circuit_successes) {
  2553. log_notice(LD_BUG, "Unexpectedly high circuit_successes (%u/%u) "
  2554. "for guard %s=%s",
  2555. guard->circuit_successes, guard->first_hops,
  2556. guard->nickname, hex_str(guard->identity, DIGEST_LEN));
  2557. }
  2558. /* In rare cases, CIRCUIT_PURPOSE_TESTING can get converted to
  2559. * CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT and have no guards here.
  2560. * No need to log that case. */
  2561. } else if (circ->_base.purpose != CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT) {
  2562. if ((rate_msg = rate_limit_log(&success_notice_limit,
  2563. approx_time()))) {
  2564. log_info(LD_BUG,
  2565. "Completed circuit has no known guard. "
  2566. "Circuit is a %s currently %s.%s",
  2567. circuit_purpose_to_string(circ->_base.purpose),
  2568. circuit_state_to_string(circ->_base.state),
  2569. rate_msg);
  2570. tor_free(rate_msg);
  2571. }
  2572. }
  2573. } else {
  2574. if (circ->path_state != PATH_STATE_SUCCEEDED) {
  2575. if ((rate_msg = rate_limit_log(&success_notice_limit,
  2576. approx_time()))) {
  2577. log_info(LD_BUG,
  2578. "Opened circuit is in strange path state %s. "
  2579. "Circuit is a %s currently %s.%s",
  2580. pathbias_state_to_string(circ->path_state),
  2581. circuit_purpose_to_string(circ->_base.purpose),
  2582. circuit_state_to_string(circ->_base.state),
  2583. rate_msg);
  2584. tor_free(rate_msg);
  2585. }
  2586. }
  2587. }
  2588. }
  2589. /** Increment the number of times we successfully extended a circuit to
  2590. * 'guard', first checking if the failure rate is high enough that we should
  2591. * eliminate the guard. Return -1 if the guard looks no good; return 0 if the
  2592. * guard looks fine. */
  2593. static int
  2594. entry_guard_inc_first_hop_count(entry_guard_t *guard)
  2595. {
  2596. const or_options_t *options = get_options();
  2597. entry_guards_changed();
  2598. if (guard->first_hops > (unsigned)pathbias_get_min_circs(options)) {
  2599. /* Note: We rely on the < comparison here to allow us to set a 0
  2600. * rate and disable the feature entirely. If refactoring, don't
  2601. * change to <= */
  2602. if (guard->circuit_successes/((double)guard->first_hops)
  2603. < pathbias_get_disable_rate(options)) {
  2604. /* This message is currently disabled by default. */
  2605. log_warn(LD_PROTOCOL,
  2606. "Extremely low circuit success rate %u/%u for guard %s=%s. "
  2607. "This indicates either an overloaded guard, an attack, or "
  2608. "a bug.",
  2609. guard->circuit_successes, guard->first_hops, guard->nickname,
  2610. hex_str(guard->identity, DIGEST_LEN));
  2611. guard->path_bias_disabled = 1;
  2612. guard->bad_since = approx_time();
  2613. return -1;
  2614. } else if (guard->circuit_successes/((double)guard->first_hops)
  2615. < pathbias_get_notice_rate(options)
  2616. && !guard->path_bias_notice) {
  2617. guard->path_bias_notice = 1;
  2618. log_notice(LD_PROTOCOL,
  2619. "Low circuit success rate %u/%u for guard %s=%s.",
  2620. guard->circuit_successes, guard->first_hops, guard->nickname,
  2621. hex_str(guard->identity, DIGEST_LEN));
  2622. }
  2623. }
  2624. /* If we get a ton of circuits, just scale everything down */
  2625. if (guard->first_hops > (unsigned)pathbias_get_scale_threshold(options)) {
  2626. const int scale_factor = pathbias_get_scale_factor(options);
  2627. /* For now, only scale if there will be no rounding error...
  2628. * XXX024: We want to switch to a real moving average for 0.2.4. */
  2629. if ((guard->first_hops % scale_factor) == 0 &&
  2630. (guard->circuit_successes % scale_factor) == 0) {
  2631. log_info(LD_PROTOCOL,
  2632. "Scaling pathbias counts to (%u/%u)/%d for guard %s=%s",
  2633. guard->circuit_successes, guard->first_hops,
  2634. scale_factor, guard->nickname, hex_str(guard->identity,
  2635. DIGEST_LEN));
  2636. guard->first_hops /= scale_factor;
  2637. guard->circuit_successes /= scale_factor;
  2638. }
  2639. }
  2640. guard->first_hops++;
  2641. log_info(LD_PROTOCOL, "Got success count %u/%u for guard %s=%s",
  2642. guard->circuit_successes, guard->first_hops, guard->nickname,
  2643. hex_str(guard->identity, DIGEST_LEN));
  2644. return 0;
  2645. }
  2646. /** A created or extended cell came back to us on the circuit, and it included
  2647. * <b>reply</b> as its body. (If <b>reply_type</b> is CELL_CREATED, the body
  2648. * contains (the second DH key, plus KH). If <b>reply_type</b> is
  2649. * CELL_CREATED_FAST, the body contains a secret y and a hash H(x|y).)
  2650. *
  2651. * Calculate the appropriate keys and digests, make sure KH is
  2652. * correct, and initialize this hop of the cpath.
  2653. *
  2654. * Return - reason if we want to mark circ for close, else return 0.
  2655. */
  2656. int
  2657. circuit_finish_handshake(origin_circuit_t *circ, uint8_t reply_type,
  2658. const uint8_t *reply)
  2659. {
  2660. char keys[CPATH_KEY_MATERIAL_LEN];
  2661. crypt_path_t *hop;
  2662. int rv;
  2663. if ((rv = pathbias_count_first_hop(circ)) < 0)
  2664. return rv;
  2665. if (circ->cpath->state == CPATH_STATE_AWAITING_KEYS) {
  2666. hop = circ->cpath;
  2667. } else {
  2668. hop = onion_next_hop_in_cpath(circ->cpath);
  2669. if (!hop) { /* got an extended when we're all done? */
  2670. log_warn(LD_PROTOCOL,"got extended when circ already built? Closing.");
  2671. return - END_CIRC_REASON_TORPROTOCOL;
  2672. }
  2673. }
  2674. tor_assert(hop->state == CPATH_STATE_AWAITING_KEYS);
  2675. if (reply_type == CELL_CREATED && hop->dh_handshake_state) {
  2676. if (onion_skin_client_handshake(hop->dh_handshake_state, (char*)reply,keys,
  2677. DIGEST_LEN*2+CIPHER_KEY_LEN*2) < 0) {
  2678. log_warn(LD_CIRC,"onion_skin_client_handshake failed.");
  2679. return -END_CIRC_REASON_TORPROTOCOL;
  2680. }
  2681. /* Remember hash of g^xy */
  2682. memcpy(hop->handshake_digest, reply+DH_KEY_LEN, DIGEST_LEN);
  2683. } else if (reply_type == CELL_CREATED_FAST && !hop->dh_handshake_state) {
  2684. if (fast_client_handshake(hop->fast_handshake_state, reply,
  2685. (uint8_t*)keys,
  2686. DIGEST_LEN*2+CIPHER_KEY_LEN*2) < 0) {
  2687. log_warn(LD_CIRC,"fast_client_handshake failed.");
  2688. return -END_CIRC_REASON_TORPROTOCOL;
  2689. }
  2690. memcpy(hop->handshake_digest, reply+DIGEST_LEN, DIGEST_LEN);
  2691. } else {
  2692. log_warn(LD_PROTOCOL,"CREATED cell type did not match CREATE cell type.");
  2693. return -END_CIRC_REASON_TORPROTOCOL;
  2694. }
  2695. crypto_dh_free(hop->dh_handshake_state); /* don't need it anymore */
  2696. hop->dh_handshake_state = NULL;
  2697. memset(hop->fast_handshake_state, 0, sizeof(hop->fast_handshake_state));
  2698. if (circuit_init_cpath_crypto(hop, keys, 0)<0) {
  2699. return -END_CIRC_REASON_TORPROTOCOL;
  2700. }
  2701. hop->state = CPATH_STATE_OPEN;
  2702. log_info(LD_CIRC,"Finished building %scircuit hop:",
  2703. (reply_type == CELL_CREATED_FAST) ? "fast " : "");
  2704. circuit_log_path(LOG_INFO,LD_CIRC,circ);
  2705. control_event_circuit_status(circ, CIRC_EVENT_EXTENDED, 0);
  2706. return 0;
  2707. }
  2708. /** We received a relay truncated cell on circ.
  2709. *
  2710. * Since we don't ask for truncates currently, getting a truncated
  2711. * means that a connection broke or an extend failed. For now,
  2712. * just give up: for circ to close, and return 0.
  2713. */
  2714. int
  2715. circuit_truncated(origin_circuit_t *circ, crypt_path_t *layer, int reason)
  2716. {
  2717. // crypt_path_t *victim;
  2718. // connection_t *stream;
  2719. tor_assert(circ);
  2720. tor_assert(layer);
  2721. /* XXX Since we don't ask for truncates currently, getting a truncated
  2722. * means that a connection broke or an extend failed. For now,
  2723. * just give up.
  2724. */
  2725. circuit_mark_for_close(TO_CIRCUIT(circ),
  2726. END_CIRC_REASON_FLAG_REMOTE|END_CIRC_REASON_CHANNEL_CLOSED|reason);
  2727. return 0;
  2728. #if 0
  2729. while (layer->next != circ->cpath) {
  2730. /* we need to clear out layer->next */
  2731. victim = layer->next;
  2732. log_debug(LD_CIRC, "Killing a layer of the cpath.");
  2733. for (stream = circ->p_streams; stream; stream=stream->next_stream) {
  2734. if (stream->cpath_layer == victim) {
  2735. log_info(LD_APP, "Marking stream %d for close because of truncate.",
  2736. stream->stream_id);
  2737. /* no need to send 'end' relay cells,
  2738. * because the other side's already dead
  2739. */
  2740. connection_mark_unattached_ap(stream, END_STREAM_REASON_DESTROY);
  2741. }
  2742. }
  2743. layer->next = victim->next;
  2744. circuit_free_cpath_node(victim);
  2745. }
  2746. log_info(LD_CIRC, "finished");
  2747. return 0;
  2748. #endif
  2749. }
  2750. /** Given a response payload and keys, initialize, then send a created
  2751. * cell back.
  2752. */
  2753. int
  2754. onionskin_answer(or_circuit_t *circ, uint8_t cell_type, const char *payload,
  2755. const char *keys)
  2756. {
  2757. cell_t cell;
  2758. crypt_path_t *tmp_cpath;
  2759. tmp_cpath = tor_malloc_zero(sizeof(crypt_path_t));
  2760. tmp_cpath->magic = CRYPT_PATH_MAGIC;
  2761. memset(&cell, 0, sizeof(cell_t));
  2762. cell.command = cell_type;
  2763. cell.circ_id = circ->p_circ_id;
  2764. circuit_set_state(TO_CIRCUIT(circ), CIRCUIT_STATE_OPEN);
  2765. memcpy(cell.payload, payload,
  2766. cell_type == CELL_CREATED ? ONIONSKIN_REPLY_LEN : DIGEST_LEN*2);
  2767. log_debug(LD_CIRC,"init digest forward 0x%.8x, backward 0x%.8x.",
  2768. (unsigned int)get_uint32(keys),
  2769. (unsigned int)get_uint32(keys+20));
  2770. if (circuit_init_cpath_crypto(tmp_cpath, keys, 0)<0) {
  2771. log_warn(LD_BUG,"Circuit initialization failed");
  2772. tor_free(tmp_cpath);
  2773. return -1;
  2774. }
  2775. circ->n_digest = tmp_cpath->f_digest;
  2776. circ->n_crypto = tmp_cpath->f_crypto;
  2777. circ->p_digest = tmp_cpath->b_digest;
  2778. circ->p_crypto = tmp_cpath->b_crypto;
  2779. tmp_cpath->magic = 0;
  2780. tor_free(tmp_cpath);
  2781. if (cell_type == CELL_CREATED)
  2782. memcpy(circ->handshake_digest, cell.payload+DH_KEY_LEN, DIGEST_LEN);
  2783. else
  2784. memcpy(circ->handshake_digest, cell.payload+DIGEST_LEN, DIGEST_LEN);
  2785. circ->is_first_hop = (cell_type == CELL_CREATED_FAST);
  2786. append_cell_to_circuit_queue(TO_CIRCUIT(circ),
  2787. circ->p_chan, &cell, CELL_DIRECTION_IN, 0);
  2788. log_debug(LD_CIRC,"Finished sending '%s' cell.",
  2789. circ->is_first_hop ? "created_fast" : "created");
  2790. if (!channel_is_local(circ->p_chan) &&
  2791. !channel_is_outgoing(circ->p_chan)) {
  2792. /* record that we could process create cells from a non-local conn
  2793. * that we didn't initiate; presumably this means that create cells
  2794. * can reach us too. */
  2795. router_orport_found_reachable();
  2796. }
  2797. return 0;
  2798. }
  2799. /** Choose a length for a circuit of purpose <b>purpose</b>.
  2800. * Default length is 3 + the number of endpoints that would give something
  2801. * away. If the routerlist <b>routers</b> doesn't have enough routers
  2802. * to handle the desired path length, return as large a path length as
  2803. * is feasible, except if it's less than 2, in which case return -1.
  2804. */
  2805. static int
  2806. new_route_len(uint8_t purpose, extend_info_t *exit,
  2807. smartlist_t *nodes)
  2808. {
  2809. int num_acceptable_routers;
  2810. int routelen;
  2811. tor_assert(nodes);
  2812. routelen = DEFAULT_ROUTE_LEN;
  2813. if (exit &&
  2814. purpose != CIRCUIT_PURPOSE_TESTING &&
  2815. purpose != CIRCUIT_PURPOSE_S_ESTABLISH_INTRO)
  2816. routelen++;
  2817. num_acceptable_routers = count_acceptable_nodes(nodes);
  2818. log_debug(LD_CIRC,"Chosen route length %d (%d/%d routers suitable).",
  2819. routelen, num_acceptable_routers, smartlist_len(nodes));
  2820. if (num_acceptable_routers < 2) {
  2821. log_info(LD_CIRC,
  2822. "Not enough acceptable routers (%d). Discarding this circuit.",
  2823. num_acceptable_routers);
  2824. return -1;
  2825. }
  2826. if (num_acceptable_routers < routelen) {
  2827. log_info(LD_CIRC,"Not enough routers: cutting routelen from %d to %d.",
  2828. routelen, num_acceptable_routers);
  2829. routelen = num_acceptable_routers;
  2830. }
  2831. return routelen;
  2832. }
  2833. /** Return a newly allocated list of uint16_t * for each predicted port not
  2834. * handled by a current circuit. */
  2835. static smartlist_t *
  2836. circuit_get_unhandled_ports(time_t now)
  2837. {
  2838. smartlist_t *dest = rep_hist_get_predicted_ports(now);
  2839. circuit_remove_handled_ports(dest);
  2840. return dest;
  2841. }
  2842. /** Return 1 if we already have circuits present or on the way for
  2843. * all anticipated ports. Return 0 if we should make more.
  2844. *
  2845. * If we're returning 0, set need_uptime and need_capacity to
  2846. * indicate any requirements that the unhandled ports have.
  2847. */
  2848. int
  2849. circuit_all_predicted_ports_handled(time_t now, int *need_uptime,
  2850. int *need_capacity)
  2851. {
  2852. int i, enough;
  2853. uint16_t *port;
  2854. smartlist_t *sl = circuit_get_unhandled_ports(now);
  2855. smartlist_t *LongLivedServices = get_options()->LongLivedPorts;
  2856. tor_assert(need_uptime);
  2857. tor_assert(need_capacity);
  2858. // Always predict need_capacity
  2859. *need_capacity = 1;
  2860. enough = (smartlist_len(sl) == 0);
  2861. for (i = 0; i < smartlist_len(sl); ++i) {
  2862. port = smartlist_get(sl, i);
  2863. if (smartlist_string_num_isin(LongLivedServices, *port))
  2864. *need_uptime = 1;
  2865. tor_free(port);
  2866. }
  2867. smartlist_free(sl);
  2868. return enough;
  2869. }
  2870. /** Return 1 if <b>node</b> can handle one or more of the ports in
  2871. * <b>needed_ports</b>, else return 0.
  2872. */
  2873. static int
  2874. node_handles_some_port(const node_t *node, smartlist_t *needed_ports)
  2875. { /* XXXX MOVE */
  2876. int i;
  2877. uint16_t port;
  2878. for (i = 0; i < smartlist_len(needed_ports); ++i) {
  2879. addr_policy_result_t r;
  2880. /* alignment issues aren't a worry for this dereference, since
  2881. needed_ports is explicitly a smartlist of uint16_t's */
  2882. port = *(uint16_t *)smartlist_get(needed_ports, i);
  2883. tor_assert(port);
  2884. if (node)
  2885. r = compare_tor_addr_to_node_policy(NULL, port, node);
  2886. else
  2887. continue;
  2888. if (r != ADDR_POLICY_REJECTED && r != ADDR_POLICY_PROBABLY_REJECTED)
  2889. return 1;
  2890. }
  2891. return 0;
  2892. }
  2893. /** Return true iff <b>conn</b> needs another general circuit to be
  2894. * built. */
  2895. static int
  2896. ap_stream_wants_exit_attention(connection_t *conn)
  2897. {
  2898. entry_connection_t *entry;
  2899. if (conn->type != CONN_TYPE_AP)
  2900. return 0;
  2901. entry = TO_ENTRY_CONN(conn);
  2902. if (conn->state == AP_CONN_STATE_CIRCUIT_WAIT &&
  2903. !conn->marked_for_close &&
  2904. !(entry->want_onehop) && /* ignore one-hop streams */
  2905. !(entry->use_begindir) && /* ignore targeted dir fetches */
  2906. !(entry->chosen_exit_name) && /* ignore defined streams */
  2907. !connection_edge_is_rendezvous_stream(TO_EDGE_CONN(conn)) &&
  2908. !circuit_stream_is_being_handled(TO_ENTRY_CONN(conn), 0,
  2909. MIN_CIRCUITS_HANDLING_STREAM))
  2910. return 1;
  2911. return 0;
  2912. }
  2913. /** Return a pointer to a suitable router to be the exit node for the
  2914. * general-purpose circuit we're about to build.
  2915. *
  2916. * Look through the connection array, and choose a router that maximizes
  2917. * the number of pending streams that can exit from this router.
  2918. *
  2919. * Return NULL if we can't find any suitable routers.
  2920. */
  2921. static const node_t *
  2922. choose_good_exit_server_general(int need_uptime, int need_capacity)
  2923. {
  2924. int *n_supported;
  2925. int n_pending_connections = 0;
  2926. smartlist_t *connections;
  2927. int best_support = -1;
  2928. int n_best_support=0;
  2929. const or_options_t *options = get_options();
  2930. const smartlist_t *the_nodes;
  2931. const node_t *node=NULL;
  2932. connections = get_connection_array();
  2933. /* Count how many connections are waiting for a circuit to be built.
  2934. * We use this for log messages now, but in the future we may depend on it.
  2935. */
  2936. SMARTLIST_FOREACH(connections, connection_t *, conn,
  2937. {
  2938. if (ap_stream_wants_exit_attention(conn))
  2939. ++n_pending_connections;
  2940. });
  2941. // log_fn(LOG_DEBUG, "Choosing exit node; %d connections are pending",
  2942. // n_pending_connections);
  2943. /* Now we count, for each of the routers in the directory, how many
  2944. * of the pending connections could possibly exit from that
  2945. * router (n_supported[i]). (We can't be sure about cases where we
  2946. * don't know the IP address of the pending connection.)
  2947. *
  2948. * -1 means "Don't use this router at all."
  2949. */
  2950. the_nodes = nodelist_get_list();
  2951. n_supported = tor_malloc(sizeof(int)*smartlist_len(the_nodes));
  2952. SMARTLIST_FOREACH_BEGIN(the_nodes, const node_t *, node) {
  2953. const int i = node_sl_idx;
  2954. if (router_digest_is_me(node->identity)) {
  2955. n_supported[i] = -1;
  2956. // log_fn(LOG_DEBUG,"Skipping node %s -- it's me.", router->nickname);
  2957. /* XXX there's probably a reverse predecessor attack here, but
  2958. * it's slow. should we take this out? -RD
  2959. */
  2960. continue;
  2961. }
  2962. if (!node_has_descriptor(node)) {
  2963. n_supported[i] = -1;
  2964. continue;
  2965. }
  2966. if (!node->is_running || node->is_bad_exit) {
  2967. n_supported[i] = -1;
  2968. continue; /* skip routers that are known to be down or bad exits */
  2969. }
  2970. if (node_get_purpose(node) != ROUTER_PURPOSE_GENERAL) {
  2971. /* never pick a non-general node as a random exit. */
  2972. n_supported[i] = -1;
  2973. continue;
  2974. }
  2975. if (routerset_contains_node(options->_ExcludeExitNodesUnion, node)) {
  2976. n_supported[i] = -1;
  2977. continue; /* user asked us not to use it, no matter what */
  2978. }
  2979. if (options->ExitNodes &&
  2980. !routerset_contains_node(options->ExitNodes, node)) {
  2981. n_supported[i] = -1;
  2982. continue; /* not one of our chosen exit nodes */
  2983. }
  2984. if (node_is_unreliable(node, need_uptime, need_capacity, 0)) {
  2985. n_supported[i] = -1;
  2986. continue; /* skip routers that are not suitable. Don't worry if
  2987. * this makes us reject all the possible routers: if so,
  2988. * we'll retry later in this function with need_update and
  2989. * need_capacity set to 0. */
  2990. }
  2991. if (!(node->is_valid || options->_AllowInvalid & ALLOW_INVALID_EXIT)) {
  2992. /* if it's invalid and we don't want it */
  2993. n_supported[i] = -1;
  2994. // log_fn(LOG_DEBUG,"Skipping node %s (index %d) -- invalid router.",
  2995. // router->nickname, i);
  2996. continue; /* skip invalid routers */
  2997. }
  2998. if (options->ExcludeSingleHopRelays &&
  2999. node_allows_single_hop_exits(node)) {
  3000. n_supported[i] = -1;
  3001. continue;
  3002. }
  3003. if (node_exit_policy_rejects_all(node)) {
  3004. n_supported[i] = -1;
  3005. // log_fn(LOG_DEBUG,"Skipping node %s (index %d) -- it rejects all.",
  3006. // router->nickname, i);
  3007. continue; /* skip routers that reject all */
  3008. }
  3009. n_supported[i] = 0;
  3010. /* iterate over connections */
  3011. SMARTLIST_FOREACH_BEGIN(connections, connection_t *, conn) {
  3012. if (!ap_stream_wants_exit_attention(conn))
  3013. continue; /* Skip everything but APs in CIRCUIT_WAIT */
  3014. if (connection_ap_can_use_exit(TO_ENTRY_CONN(conn), node)) {
  3015. ++n_supported[i];
  3016. // log_fn(LOG_DEBUG,"%s is supported. n_supported[%d] now %d.",
  3017. // router->nickname, i, n_supported[i]);
  3018. } else {
  3019. // log_fn(LOG_DEBUG,"%s (index %d) would reject this stream.",
  3020. // router->nickname, i);
  3021. }
  3022. } SMARTLIST_FOREACH_END(conn);
  3023. if (n_pending_connections > 0 && n_supported[i] == 0) {
  3024. /* Leave best_support at -1 if that's where it is, so we can
  3025. * distinguish it later. */
  3026. continue;
  3027. }
  3028. if (n_supported[i] > best_support) {
  3029. /* If this router is better than previous ones, remember its index
  3030. * and goodness, and start counting how many routers are this good. */
  3031. best_support = n_supported[i]; n_best_support=1;
  3032. // log_fn(LOG_DEBUG,"%s is new best supported option so far.",
  3033. // router->nickname);
  3034. } else if (n_supported[i] == best_support) {
  3035. /* If this router is _as good_ as the best one, just increment the
  3036. * count of equally good routers.*/
  3037. ++n_best_support;
  3038. }
  3039. } SMARTLIST_FOREACH_END(node);
  3040. log_info(LD_CIRC,
  3041. "Found %d servers that might support %d/%d pending connections.",
  3042. n_best_support, best_support >= 0 ? best_support : 0,
  3043. n_pending_connections);
  3044. /* If any routers definitely support any pending connections, choose one
  3045. * at random. */
  3046. if (best_support > 0) {
  3047. smartlist_t *supporting = smartlist_new();
  3048. SMARTLIST_FOREACH(the_nodes, const node_t *, node, {
  3049. if (n_supported[node_sl_idx] == best_support)
  3050. smartlist_add(supporting, (void*)node);
  3051. });
  3052. node = node_sl_choose_by_bandwidth(supporting, WEIGHT_FOR_EXIT);
  3053. smartlist_free(supporting);
  3054. } else {
  3055. /* Either there are no pending connections, or no routers even seem to
  3056. * possibly support any of them. Choose a router at random that satisfies
  3057. * at least one predicted exit port. */
  3058. int attempt;
  3059. smartlist_t *needed_ports, *supporting;
  3060. if (best_support == -1) {
  3061. if (need_uptime || need_capacity) {
  3062. log_info(LD_CIRC,
  3063. "We couldn't find any live%s%s routers; falling back "
  3064. "to list of all routers.",
  3065. need_capacity?", fast":"",
  3066. need_uptime?", stable":"");
  3067. tor_free(n_supported);
  3068. return choose_good_exit_server_general(0, 0);
  3069. }
  3070. log_notice(LD_CIRC, "All routers are down or won't exit%s -- "
  3071. "choosing a doomed exit at random.",
  3072. options->_ExcludeExitNodesUnion ? " or are Excluded" : "");
  3073. }
  3074. supporting = smartlist_new();
  3075. needed_ports = circuit_get_unhandled_ports(time(NULL));
  3076. for (attempt = 0; attempt < 2; attempt++) {
  3077. /* try once to pick only from routers that satisfy a needed port,
  3078. * then if there are none, pick from any that support exiting. */
  3079. SMARTLIST_FOREACH_BEGIN(the_nodes, const node_t *, node) {
  3080. if (n_supported[node_sl_idx] != -1 &&
  3081. (attempt || node_handles_some_port(node, needed_ports))) {
  3082. // log_fn(LOG_DEBUG,"Try %d: '%s' is a possibility.",
  3083. // try, router->nickname);
  3084. smartlist_add(supporting, (void*)node);
  3085. }
  3086. } SMARTLIST_FOREACH_END(node);
  3087. node = node_sl_choose_by_bandwidth(supporting, WEIGHT_FOR_EXIT);
  3088. if (node)
  3089. break;
  3090. smartlist_clear(supporting);
  3091. /* If we reach this point, we can't actually support any unhandled
  3092. * predicted ports, so clear all the remaining ones. */
  3093. if (smartlist_len(needed_ports))
  3094. rep_hist_remove_predicted_ports(needed_ports);
  3095. }
  3096. SMARTLIST_FOREACH(needed_ports, uint16_t *, cp, tor_free(cp));
  3097. smartlist_free(needed_ports);
  3098. smartlist_free(supporting);
  3099. }
  3100. tor_free(n_supported);
  3101. if (node) {
  3102. log_info(LD_CIRC, "Chose exit server '%s'", node_describe(node));
  3103. return node;
  3104. }
  3105. if (options->ExitNodes) {
  3106. log_warn(LD_CIRC,
  3107. "No specified %sexit routers seem to be running: "
  3108. "can't choose an exit.",
  3109. options->_ExcludeExitNodesUnion ? "non-excluded " : "");
  3110. }
  3111. return NULL;
  3112. }
  3113. /** Return a pointer to a suitable router to be the exit node for the
  3114. * circuit of purpose <b>purpose</b> that we're about to build (or NULL
  3115. * if no router is suitable).
  3116. *
  3117. * For general-purpose circuits, pass it off to
  3118. * choose_good_exit_server_general()
  3119. *
  3120. * For client-side rendezvous circuits, choose a random node, weighted
  3121. * toward the preferences in 'options'.
  3122. */
  3123. static const node_t *
  3124. choose_good_exit_server(uint8_t purpose,
  3125. int need_uptime, int need_capacity, int is_internal)
  3126. {
  3127. const or_options_t *options = get_options();
  3128. router_crn_flags_t flags = CRN_NEED_DESC;
  3129. if (need_uptime)
  3130. flags |= CRN_NEED_UPTIME;
  3131. if (need_capacity)
  3132. flags |= CRN_NEED_CAPACITY;
  3133. switch (purpose) {
  3134. case CIRCUIT_PURPOSE_C_GENERAL:
  3135. if (options->_AllowInvalid & ALLOW_INVALID_MIDDLE)
  3136. flags |= CRN_ALLOW_INVALID;
  3137. if (is_internal) /* pick it like a middle hop */
  3138. return router_choose_random_node(NULL, options->ExcludeNodes, flags);
  3139. else
  3140. return choose_good_exit_server_general(need_uptime,need_capacity);
  3141. case CIRCUIT_PURPOSE_C_ESTABLISH_REND:
  3142. if (options->_AllowInvalid & ALLOW_INVALID_RENDEZVOUS)
  3143. flags |= CRN_ALLOW_INVALID;
  3144. return router_choose_random_node(NULL, options->ExcludeNodes, flags);
  3145. }
  3146. log_warn(LD_BUG,"Unhandled purpose %d", purpose);
  3147. tor_fragile_assert();
  3148. return NULL;
  3149. }
  3150. /** Log a warning if the user specified an exit for the circuit that
  3151. * has been excluded from use by ExcludeNodes or ExcludeExitNodes. */
  3152. static void
  3153. warn_if_last_router_excluded(origin_circuit_t *circ, const extend_info_t *exit)
  3154. {
  3155. const or_options_t *options = get_options();
  3156. routerset_t *rs = options->ExcludeNodes;
  3157. const char *description;
  3158. uint8_t purpose = circ->_base.purpose;
  3159. if (circ->build_state->onehop_tunnel)
  3160. return;
  3161. switch (purpose)
  3162. {
  3163. default:
  3164. case CIRCUIT_PURPOSE_OR:
  3165. case CIRCUIT_PURPOSE_INTRO_POINT:
  3166. case CIRCUIT_PURPOSE_REND_POINT_WAITING:
  3167. case CIRCUIT_PURPOSE_REND_ESTABLISHED:
  3168. log_warn(LD_BUG, "Called on non-origin circuit (purpose %d, %s)",
  3169. (int)purpose,
  3170. circuit_purpose_to_string(purpose));
  3171. return;
  3172. case CIRCUIT_PURPOSE_C_GENERAL:
  3173. if (circ->build_state->is_internal)
  3174. return;
  3175. description = "requested exit node";
  3176. rs = options->_ExcludeExitNodesUnion;
  3177. break;
  3178. case CIRCUIT_PURPOSE_C_INTRODUCING:
  3179. case CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT:
  3180. case CIRCUIT_PURPOSE_C_INTRODUCE_ACKED:
  3181. case CIRCUIT_PURPOSE_S_ESTABLISH_INTRO:
  3182. case CIRCUIT_PURPOSE_S_CONNECT_REND:
  3183. case CIRCUIT_PURPOSE_S_REND_JOINED:
  3184. case CIRCUIT_PURPOSE_TESTING:
  3185. return;
  3186. case CIRCUIT_PURPOSE_C_ESTABLISH_REND:
  3187. case CIRCUIT_PURPOSE_C_REND_READY:
  3188. case CIRCUIT_PURPOSE_C_REND_READY_INTRO_ACKED:
  3189. case CIRCUIT_PURPOSE_C_REND_JOINED:
  3190. description = "chosen rendezvous point";
  3191. break;
  3192. case CIRCUIT_PURPOSE_CONTROLLER:
  3193. rs = options->_ExcludeExitNodesUnion;
  3194. description = "controller-selected circuit target";
  3195. break;
  3196. }
  3197. if (routerset_contains_extendinfo(rs, exit)) {
  3198. /* We should never get here if StrictNodes is set to 1. */
  3199. if (options->StrictNodes) {
  3200. log_warn(LD_BUG, "Using %s '%s' which is listed in ExcludeNodes%s, "
  3201. "even though StrictNodes is set. Please report. "
  3202. "(Circuit purpose: %s)",
  3203. description, extend_info_describe(exit),
  3204. rs==options->ExcludeNodes?"":" or ExcludeExitNodes",
  3205. circuit_purpose_to_string(purpose));
  3206. } else {
  3207. log_warn(LD_CIRC, "Using %s '%s' which is listed in "
  3208. "ExcludeNodes%s, because no better options were available. To "
  3209. "prevent this (and possibly break your Tor functionality), "
  3210. "set the StrictNodes configuration option. "
  3211. "(Circuit purpose: %s)",
  3212. description, extend_info_describe(exit),
  3213. rs==options->ExcludeNodes?"":" or ExcludeExitNodes",
  3214. circuit_purpose_to_string(purpose));
  3215. }
  3216. circuit_log_path(LOG_WARN, LD_CIRC, circ);
  3217. }
  3218. return;
  3219. }
  3220. /** Decide a suitable length for circ's cpath, and pick an exit
  3221. * router (or use <b>exit</b> if provided). Store these in the
  3222. * cpath. Return 0 if ok, -1 if circuit should be closed. */
  3223. static int
  3224. onion_pick_cpath_exit(origin_circuit_t *circ, extend_info_t *exit)
  3225. {
  3226. cpath_build_state_t *state = circ->build_state;
  3227. if (state->onehop_tunnel) {
  3228. log_debug(LD_CIRC, "Launching a one-hop circuit for dir tunnel.");
  3229. state->desired_path_len = 1;
  3230. } else {
  3231. int r = new_route_len(circ->_base.purpose, exit, nodelist_get_list());
  3232. if (r < 1) /* must be at least 1 */
  3233. return -1;
  3234. state->desired_path_len = r;
  3235. }
  3236. if (exit) { /* the circuit-builder pre-requested one */
  3237. warn_if_last_router_excluded(circ, exit);
  3238. log_info(LD_CIRC,"Using requested exit node '%s'",
  3239. extend_info_describe(exit));
  3240. exit = extend_info_dup(exit);
  3241. } else { /* we have to decide one */
  3242. const node_t *node =
  3243. choose_good_exit_server(circ->_base.purpose, state->need_uptime,
  3244. state->need_capacity, state->is_internal);
  3245. if (!node) {
  3246. log_warn(LD_CIRC,"failed to choose an exit server");
  3247. return -1;
  3248. }
  3249. exit = extend_info_from_node(node, 0);
  3250. tor_assert(exit);
  3251. }
  3252. state->chosen_exit = exit;
  3253. return 0;
  3254. }
  3255. /** Give <b>circ</b> a new exit destination to <b>exit</b>, and add a
  3256. * hop to the cpath reflecting this. Don't send the next extend cell --
  3257. * the caller will do this if it wants to.
  3258. */
  3259. int
  3260. circuit_append_new_exit(origin_circuit_t *circ, extend_info_t *exit)
  3261. {
  3262. cpath_build_state_t *state;
  3263. tor_assert(exit);
  3264. tor_assert(circ);
  3265. state = circ->build_state;
  3266. tor_assert(state);
  3267. extend_info_free(state->chosen_exit);
  3268. state->chosen_exit = extend_info_dup(exit);
  3269. ++circ->build_state->desired_path_len;
  3270. onion_append_hop(&circ->cpath, exit);
  3271. return 0;
  3272. }
  3273. /** Take an open <b>circ</b>, and add a new hop at the end, based on
  3274. * <b>info</b>. Set its state back to CIRCUIT_STATE_BUILDING, and then
  3275. * send the next extend cell to begin connecting to that hop.
  3276. */
  3277. int
  3278. circuit_extend_to_new_exit(origin_circuit_t *circ, extend_info_t *exit)
  3279. {
  3280. int err_reason = 0;
  3281. warn_if_last_router_excluded(circ, exit);
  3282. circuit_append_new_exit(circ, exit);
  3283. circuit_set_state(TO_CIRCUIT(circ), CIRCUIT_STATE_BUILDING);
  3284. if ((err_reason = circuit_send_next_onion_skin(circ))<0) {
  3285. log_warn(LD_CIRC, "Couldn't extend circuit to new point %s.",
  3286. extend_info_describe(exit));
  3287. circuit_mark_for_close(TO_CIRCUIT(circ), -err_reason);
  3288. return -1;
  3289. }
  3290. return 0;
  3291. }
  3292. /** Return the number of routers in <b>routers</b> that are currently up
  3293. * and available for building circuits through.
  3294. */
  3295. static int
  3296. count_acceptable_nodes(smartlist_t *nodes)
  3297. {
  3298. int num=0;
  3299. SMARTLIST_FOREACH_BEGIN(nodes, const node_t *, node) {
  3300. // log_debug(LD_CIRC,
  3301. // "Contemplating whether router %d (%s) is a new option.",
  3302. // i, r->nickname);
  3303. if (! node->is_running)
  3304. // log_debug(LD_CIRC,"Nope, the directory says %d is not running.",i);
  3305. continue;
  3306. if (! node->is_valid)
  3307. // log_debug(LD_CIRC,"Nope, the directory says %d is not valid.",i);
  3308. continue;
  3309. if (! node_has_descriptor(node))
  3310. continue;
  3311. /* XXX This clause makes us count incorrectly: if AllowInvalidRouters
  3312. * allows this node in some places, then we're getting an inaccurate
  3313. * count. For now, be conservative and don't count it. But later we
  3314. * should try to be smarter. */
  3315. ++num;
  3316. } SMARTLIST_FOREACH_END(node);
  3317. // log_debug(LD_CIRC,"I like %d. num_acceptable_routers now %d.",i, num);
  3318. return num;
  3319. }
  3320. /** Add <b>new_hop</b> to the end of the doubly-linked-list <b>head_ptr</b>.
  3321. * This function is used to extend cpath by another hop.
  3322. */
  3323. void
  3324. onion_append_to_cpath(crypt_path_t **head_ptr, crypt_path_t *new_hop)
  3325. {
  3326. if (*head_ptr) {
  3327. new_hop->next = (*head_ptr);
  3328. new_hop->prev = (*head_ptr)->prev;
  3329. (*head_ptr)->prev->next = new_hop;
  3330. (*head_ptr)->prev = new_hop;
  3331. } else {
  3332. *head_ptr = new_hop;
  3333. new_hop->prev = new_hop->next = new_hop;
  3334. }
  3335. }
  3336. /** A helper function used by onion_extend_cpath(). Use <b>purpose</b>
  3337. * and <b>state</b> and the cpath <b>head</b> (currently populated only
  3338. * to length <b>cur_len</b> to decide a suitable middle hop for a
  3339. * circuit. In particular, make sure we don't pick the exit node or its
  3340. * family, and make sure we don't duplicate any previous nodes or their
  3341. * families. */
  3342. static const node_t *
  3343. choose_good_middle_server(uint8_t purpose,
  3344. cpath_build_state_t *state,
  3345. crypt_path_t *head,
  3346. int cur_len)
  3347. {
  3348. int i;
  3349. const node_t *r, *choice;
  3350. crypt_path_t *cpath;
  3351. smartlist_t *excluded;
  3352. const or_options_t *options = get_options();
  3353. router_crn_flags_t flags = CRN_NEED_DESC;
  3354. tor_assert(_CIRCUIT_PURPOSE_MIN <= purpose &&
  3355. purpose <= _CIRCUIT_PURPOSE_MAX);
  3356. log_debug(LD_CIRC, "Contemplating intermediate hop: random choice.");
  3357. excluded = smartlist_new();
  3358. if ((r = build_state_get_exit_node(state))) {
  3359. nodelist_add_node_and_family(excluded, r);
  3360. }
  3361. for (i = 0, cpath = head; i < cur_len; ++i, cpath=cpath->next) {
  3362. if ((r = node_get_by_id(cpath->extend_info->identity_digest))) {
  3363. nodelist_add_node_and_family(excluded, r);
  3364. }
  3365. }
  3366. if (state->need_uptime)
  3367. flags |= CRN_NEED_UPTIME;
  3368. if (state->need_capacity)
  3369. flags |= CRN_NEED_CAPACITY;
  3370. if (options->_AllowInvalid & ALLOW_INVALID_MIDDLE)
  3371. flags |= CRN_ALLOW_INVALID;
  3372. choice = router_choose_random_node(excluded, options->ExcludeNodes, flags);
  3373. smartlist_free(excluded);
  3374. return choice;
  3375. }
  3376. /** Pick a good entry server for the circuit to be built according to
  3377. * <b>state</b>. Don't reuse a chosen exit (if any), don't use this
  3378. * router (if we're an OR), and respect firewall settings; if we're
  3379. * configured to use entry guards, return one.
  3380. *
  3381. * If <b>state</b> is NULL, we're choosing a router to serve as an entry
  3382. * guard, not for any particular circuit.
  3383. */
  3384. static const node_t *
  3385. choose_good_entry_server(uint8_t purpose, cpath_build_state_t *state)
  3386. {
  3387. const node_t *choice;
  3388. smartlist_t *excluded;
  3389. const or_options_t *options = get_options();
  3390. router_crn_flags_t flags = CRN_NEED_GUARD|CRN_NEED_DESC;
  3391. const node_t *node;
  3392. if (state && options->UseEntryGuards &&
  3393. (purpose != CIRCUIT_PURPOSE_TESTING || options->BridgeRelay)) {
  3394. /* This request is for an entry server to use for a regular circuit,
  3395. * and we use entry guard nodes. Just return one of the guard nodes. */
  3396. return choose_random_entry(state);
  3397. }
  3398. excluded = smartlist_new();
  3399. if (state && (node = build_state_get_exit_node(state))) {
  3400. /* Exclude the exit node from the state, if we have one. Also exclude its
  3401. * family. */
  3402. nodelist_add_node_and_family(excluded, node);
  3403. }
  3404. if (firewall_is_fascist_or()) {
  3405. /* Exclude all ORs that we can't reach through our firewall */
  3406. smartlist_t *nodes = nodelist_get_list();
  3407. SMARTLIST_FOREACH(nodes, const node_t *, node, {
  3408. if (!fascist_firewall_allows_node(node))
  3409. smartlist_add(excluded, (void*)node);
  3410. });
  3411. }
  3412. /* and exclude current entry guards and their families, if applicable */
  3413. if (options->UseEntryGuards && entry_guards) {
  3414. SMARTLIST_FOREACH(entry_guards, entry_guard_t *, entry,
  3415. {
  3416. if ((node = node_get_by_id(entry->identity))) {
  3417. nodelist_add_node_and_family(excluded, node);
  3418. }
  3419. });
  3420. }
  3421. if (state) {
  3422. if (state->need_uptime)
  3423. flags |= CRN_NEED_UPTIME;
  3424. if (state->need_capacity)
  3425. flags |= CRN_NEED_CAPACITY;
  3426. }
  3427. if (options->_AllowInvalid & ALLOW_INVALID_ENTRY)
  3428. flags |= CRN_ALLOW_INVALID;
  3429. choice = router_choose_random_node(excluded, options->ExcludeNodes, flags);
  3430. smartlist_free(excluded);
  3431. return choice;
  3432. }
  3433. /** Return the first non-open hop in cpath, or return NULL if all
  3434. * hops are open. */
  3435. static crypt_path_t *
  3436. onion_next_hop_in_cpath(crypt_path_t *cpath)
  3437. {
  3438. crypt_path_t *hop = cpath;
  3439. do {
  3440. if (hop->state != CPATH_STATE_OPEN)
  3441. return hop;
  3442. hop = hop->next;
  3443. } while (hop != cpath);
  3444. return NULL;
  3445. }
  3446. /** Choose a suitable next hop in the cpath <b>head_ptr</b>,
  3447. * based on <b>state</b>. Append the hop info to head_ptr.
  3448. */
  3449. static int
  3450. onion_extend_cpath(origin_circuit_t *circ)
  3451. {
  3452. uint8_t purpose = circ->_base.purpose;
  3453. cpath_build_state_t *state = circ->build_state;
  3454. int cur_len = circuit_get_cpath_len(circ);
  3455. extend_info_t *info = NULL;
  3456. if (cur_len >= state->desired_path_len) {
  3457. log_debug(LD_CIRC, "Path is complete: %d steps long",
  3458. state->desired_path_len);
  3459. return 1;
  3460. }
  3461. log_debug(LD_CIRC, "Path is %d long; we want %d", cur_len,
  3462. state->desired_path_len);
  3463. if (cur_len == state->desired_path_len - 1) { /* Picking last node */
  3464. info = extend_info_dup(state->chosen_exit);
  3465. } else if (cur_len == 0) { /* picking first node */
  3466. const node_t *r = choose_good_entry_server(purpose, state);
  3467. if (r) {
  3468. /* If we're a client, use the preferred address rather than the
  3469. primary address, for potentially connecting to an IPv6 OR
  3470. port. */
  3471. info = extend_info_from_node(r, server_mode(get_options()) == 0);
  3472. tor_assert(info);
  3473. }
  3474. } else {
  3475. const node_t *r =
  3476. choose_good_middle_server(purpose, state, circ->cpath, cur_len);
  3477. if (r) {
  3478. info = extend_info_from_node(r, 0);
  3479. tor_assert(info);
  3480. }
  3481. }
  3482. if (!info) {
  3483. log_warn(LD_CIRC,"Failed to find node for hop %d of our path. Discarding "
  3484. "this circuit.", cur_len);
  3485. return -1;
  3486. }
  3487. log_debug(LD_CIRC,"Chose router %s for hop %d (exit is %s)",
  3488. extend_info_describe(info),
  3489. cur_len+1, build_state_get_exit_nickname(state));
  3490. onion_append_hop(&circ->cpath, info);
  3491. extend_info_free(info);
  3492. return 0;
  3493. }
  3494. /** Create a new hop, annotate it with information about its
  3495. * corresponding router <b>choice</b>, and append it to the
  3496. * end of the cpath <b>head_ptr</b>. */
  3497. static int
  3498. onion_append_hop(crypt_path_t **head_ptr, extend_info_t *choice)
  3499. {
  3500. crypt_path_t *hop = tor_malloc_zero(sizeof(crypt_path_t));
  3501. /* link hop into the cpath, at the end. */
  3502. onion_append_to_cpath(head_ptr, hop);
  3503. hop->magic = CRYPT_PATH_MAGIC;
  3504. hop->state = CPATH_STATE_CLOSED;
  3505. hop->extend_info = extend_info_dup(choice);
  3506. hop->package_window = circuit_initial_package_window();
  3507. hop->deliver_window = CIRCWINDOW_START;
  3508. return 0;
  3509. }
  3510. /** Allocate a new extend_info object based on the various arguments. */
  3511. extend_info_t *
  3512. extend_info_new(const char *nickname, const char *digest,
  3513. crypto_pk_t *onion_key,
  3514. const tor_addr_t *addr, uint16_t port)
  3515. {
  3516. extend_info_t *info = tor_malloc_zero(sizeof(extend_info_t));
  3517. memcpy(info->identity_digest, digest, DIGEST_LEN);
  3518. if (nickname)
  3519. strlcpy(info->nickname, nickname, sizeof(info->nickname));
  3520. if (onion_key)
  3521. info->onion_key = crypto_pk_dup_key(onion_key);
  3522. tor_addr_copy(&info->addr, addr);
  3523. info->port = port;
  3524. return info;
  3525. }
  3526. /** Allocate and return a new extend_info that can be used to build a
  3527. * circuit to or through the node <b>node</b>. Use the primary address
  3528. * of the node (i.e. its IPv4 address) unless
  3529. * <b>for_direct_connect</b> is true, in which case the preferred
  3530. * address is used instead. May return NULL if there is not enough
  3531. * info about <b>node</b> to extend to it--for example, if there is no
  3532. * routerinfo_t or microdesc_t.
  3533. **/
  3534. extend_info_t *
  3535. extend_info_from_node(const node_t *node, int for_direct_connect)
  3536. {
  3537. tor_addr_port_t ap;
  3538. if (node->ri == NULL && (node->rs == NULL || node->md == NULL))
  3539. return NULL;
  3540. if (for_direct_connect)
  3541. node_get_pref_orport(node, &ap);
  3542. else
  3543. node_get_prim_orport(node, &ap);
  3544. log_debug(LD_CIRC, "using %s:%d for %s",
  3545. fmt_and_decorate_addr(&ap.addr), ap.port,
  3546. node->ri ? node->ri->nickname : node->rs->nickname);
  3547. if (node->ri)
  3548. return extend_info_new(node->ri->nickname,
  3549. node->identity,
  3550. node->ri->onion_pkey,
  3551. &ap.addr,
  3552. ap.port);
  3553. else if (node->rs && node->md)
  3554. return extend_info_new(node->rs->nickname,
  3555. node->identity,
  3556. node->md->onion_pkey,
  3557. &ap.addr,
  3558. ap.port);
  3559. else
  3560. return NULL;
  3561. }
  3562. /** Release storage held by an extend_info_t struct. */
  3563. void
  3564. extend_info_free(extend_info_t *info)
  3565. {
  3566. if (!info)
  3567. return;
  3568. crypto_pk_free(info->onion_key);
  3569. tor_free(info);
  3570. }
  3571. /** Allocate and return a new extend_info_t with the same contents as
  3572. * <b>info</b>. */
  3573. extend_info_t *
  3574. extend_info_dup(extend_info_t *info)
  3575. {
  3576. extend_info_t *newinfo;
  3577. tor_assert(info);
  3578. newinfo = tor_malloc(sizeof(extend_info_t));
  3579. memcpy(newinfo, info, sizeof(extend_info_t));
  3580. if (info->onion_key)
  3581. newinfo->onion_key = crypto_pk_dup_key(info->onion_key);
  3582. else
  3583. newinfo->onion_key = NULL;
  3584. return newinfo;
  3585. }
  3586. /** Return the routerinfo_t for the chosen exit router in <b>state</b>.
  3587. * If there is no chosen exit, or if we don't know the routerinfo_t for
  3588. * the chosen exit, return NULL.
  3589. */
  3590. const node_t *
  3591. build_state_get_exit_node(cpath_build_state_t *state)
  3592. {
  3593. if (!state || !state->chosen_exit)
  3594. return NULL;
  3595. return node_get_by_id(state->chosen_exit->identity_digest);
  3596. }
  3597. /** Return the nickname for the chosen exit router in <b>state</b>. If
  3598. * there is no chosen exit, or if we don't know the routerinfo_t for the
  3599. * chosen exit, return NULL.
  3600. */
  3601. const char *
  3602. build_state_get_exit_nickname(cpath_build_state_t *state)
  3603. {
  3604. if (!state || !state->chosen_exit)
  3605. return NULL;
  3606. return state->chosen_exit->nickname;
  3607. }
  3608. /** Check whether the entry guard <b>e</b> is usable, given the directory
  3609. * authorities' opinion about the router (stored in <b>ri</b>) and the user's
  3610. * configuration (in <b>options</b>). Set <b>e</b>-&gt;bad_since
  3611. * accordingly. Return true iff the entry guard's status changes.
  3612. *
  3613. * If it's not usable, set *<b>reason</b> to a static string explaining why.
  3614. */
  3615. static int
  3616. entry_guard_set_status(entry_guard_t *e, const node_t *node,
  3617. time_t now, const or_options_t *options,
  3618. const char **reason)
  3619. {
  3620. char buf[HEX_DIGEST_LEN+1];
  3621. int changed = 0;
  3622. *reason = NULL;
  3623. /* Do we want to mark this guard as bad? */
  3624. if (!node)
  3625. *reason = "unlisted";
  3626. else if (!node->is_running)
  3627. *reason = "down";
  3628. else if (options->UseBridges && (!node->ri ||
  3629. node->ri->purpose != ROUTER_PURPOSE_BRIDGE))
  3630. *reason = "not a bridge";
  3631. else if (options->UseBridges && !node_is_a_configured_bridge(node))
  3632. *reason = "not a configured bridge";
  3633. else if (!options->UseBridges && !node->is_possible_guard &&
  3634. !routerset_contains_node(options->EntryNodes,node))
  3635. *reason = "not recommended as a guard";
  3636. else if (routerset_contains_node(options->ExcludeNodes, node))
  3637. *reason = "excluded";
  3638. else if (e->path_bias_disabled)
  3639. *reason = "path-biased";
  3640. if (*reason && ! e->bad_since) {
  3641. /* Router is newly bad. */
  3642. base16_encode(buf, sizeof(buf), e->identity, DIGEST_LEN);
  3643. log_info(LD_CIRC, "Entry guard %s (%s) is %s: marking as unusable.",
  3644. e->nickname, buf, *reason);
  3645. e->bad_since = now;
  3646. control_event_guard(e->nickname, e->identity, "BAD");
  3647. changed = 1;
  3648. } else if (!*reason && e->bad_since) {
  3649. /* There's nothing wrong with the router any more. */
  3650. base16_encode(buf, sizeof(buf), e->identity, DIGEST_LEN);
  3651. log_info(LD_CIRC, "Entry guard %s (%s) is no longer unusable: "
  3652. "marking as ok.", e->nickname, buf);
  3653. e->bad_since = 0;
  3654. control_event_guard(e->nickname, e->identity, "GOOD");
  3655. changed = 1;
  3656. }
  3657. return changed;
  3658. }
  3659. /** Return true iff enough time has passed since we last tried to connect
  3660. * to the unreachable guard <b>e</b> that we're willing to try again. */
  3661. static int
  3662. entry_is_time_to_retry(entry_guard_t *e, time_t now)
  3663. {
  3664. long diff;
  3665. if (e->last_attempted < e->unreachable_since)
  3666. return 1;
  3667. diff = now - e->unreachable_since;
  3668. if (diff < 6*60*60)
  3669. return now > (e->last_attempted + 60*60);
  3670. else if (diff < 3*24*60*60)
  3671. return now > (e->last_attempted + 4*60*60);
  3672. else if (diff < 7*24*60*60)
  3673. return now > (e->last_attempted + 18*60*60);
  3674. else
  3675. return now > (e->last_attempted + 36*60*60);
  3676. }
  3677. /** Return the node corresponding to <b>e</b>, if <b>e</b> is
  3678. * working well enough that we are willing to use it as an entry
  3679. * right now. (Else return NULL.) In particular, it must be
  3680. * - Listed as either up or never yet contacted;
  3681. * - Present in the routerlist;
  3682. * - Listed as 'stable' or 'fast' by the current dirserver consensus,
  3683. * if demanded by <b>need_uptime</b> or <b>need_capacity</b>
  3684. * (unless it's a configured EntryNode);
  3685. * - Allowed by our current ReachableORAddresses config option; and
  3686. * - Currently thought to be reachable by us (unless <b>assume_reachable</b>
  3687. * is true).
  3688. *
  3689. * If the answer is no, set *<b>msg</b> to an explanation of why.
  3690. */
  3691. static INLINE const node_t *
  3692. entry_is_live(entry_guard_t *e, int need_uptime, int need_capacity,
  3693. int assume_reachable, const char **msg)
  3694. {
  3695. const node_t *node;
  3696. const or_options_t *options = get_options();
  3697. tor_assert(msg);
  3698. if (e->path_bias_disabled) {
  3699. *msg = "path-biased";
  3700. return NULL;
  3701. }
  3702. if (e->bad_since) {
  3703. *msg = "bad";
  3704. return NULL;
  3705. }
  3706. /* no good if it's unreachable, unless assume_unreachable or can_retry. */
  3707. if (!assume_reachable && !e->can_retry &&
  3708. e->unreachable_since && !entry_is_time_to_retry(e, time(NULL))) {
  3709. *msg = "unreachable";
  3710. return NULL;
  3711. }
  3712. node = node_get_by_id(e->identity);
  3713. if (!node || !node_has_descriptor(node)) {
  3714. *msg = "no descriptor";
  3715. return NULL;
  3716. }
  3717. if (get_options()->UseBridges) {
  3718. if (node_get_purpose(node) != ROUTER_PURPOSE_BRIDGE) {
  3719. *msg = "not a bridge";
  3720. return NULL;
  3721. }
  3722. if (!node_is_a_configured_bridge(node)) {
  3723. *msg = "not a configured bridge";
  3724. return NULL;
  3725. }
  3726. } else { /* !get_options()->UseBridges */
  3727. if (node_get_purpose(node) != ROUTER_PURPOSE_GENERAL) {
  3728. *msg = "not general-purpose";
  3729. return NULL;
  3730. }
  3731. }
  3732. if (routerset_contains_node(options->EntryNodes, node)) {
  3733. /* they asked for it, they get it */
  3734. need_uptime = need_capacity = 0;
  3735. }
  3736. if (node_is_unreliable(node, need_uptime, need_capacity, 0)) {
  3737. *msg = "not fast/stable";
  3738. return NULL;
  3739. }
  3740. if (!fascist_firewall_allows_node(node)) {
  3741. *msg = "unreachable by config";
  3742. return NULL;
  3743. }
  3744. return node;
  3745. }
  3746. /** Return the number of entry guards that we think are usable. */
  3747. static int
  3748. num_live_entry_guards(void)
  3749. {
  3750. int n = 0;
  3751. const char *msg;
  3752. if (! entry_guards)
  3753. return 0;
  3754. SMARTLIST_FOREACH(entry_guards, entry_guard_t *, entry,
  3755. {
  3756. if (entry_is_live(entry, 0, 1, 0, &msg))
  3757. ++n;
  3758. });
  3759. return n;
  3760. }
  3761. /** If <b>digest</b> matches the identity of any node in the
  3762. * entry_guards list, return that node. Else return NULL. */
  3763. static entry_guard_t *
  3764. entry_guard_get_by_id_digest(const char *digest)
  3765. {
  3766. SMARTLIST_FOREACH(entry_guards, entry_guard_t *, entry,
  3767. if (tor_memeq(digest, entry->identity, DIGEST_LEN))
  3768. return entry;
  3769. );
  3770. return NULL;
  3771. }
  3772. /** Dump a description of our list of entry guards to the log at level
  3773. * <b>severity</b>. */
  3774. static void
  3775. log_entry_guards(int severity)
  3776. {
  3777. smartlist_t *elements = smartlist_new();
  3778. char *s;
  3779. SMARTLIST_FOREACH_BEGIN(entry_guards, entry_guard_t *, e)
  3780. {
  3781. const char *msg = NULL;
  3782. if (entry_is_live(e, 0, 1, 0, &msg))
  3783. smartlist_add_asprintf(elements, "%s [%s] (up %s)",
  3784. e->nickname,
  3785. hex_str(e->identity, DIGEST_LEN),
  3786. e->made_contact ? "made-contact" : "never-contacted");
  3787. else
  3788. smartlist_add_asprintf(elements, "%s [%s] (%s, %s)",
  3789. e->nickname,
  3790. hex_str(e->identity, DIGEST_LEN),
  3791. msg,
  3792. e->made_contact ? "made-contact" : "never-contacted");
  3793. }
  3794. SMARTLIST_FOREACH_END(e);
  3795. s = smartlist_join_strings(elements, ",", 0, NULL);
  3796. SMARTLIST_FOREACH(elements, char*, cp, tor_free(cp));
  3797. smartlist_free(elements);
  3798. log_fn(severity,LD_CIRC,"%s",s);
  3799. tor_free(s);
  3800. }
  3801. /** Called when one or more guards that we would previously have used for some
  3802. * purpose are no longer in use because a higher-priority guard has become
  3803. * usable again. */
  3804. static void
  3805. control_event_guard_deferred(void)
  3806. {
  3807. /* XXXX We don't actually have a good way to figure out _how many_ entries
  3808. * are live for some purpose. We need an entry_is_even_slightly_live()
  3809. * function for this to work right. NumEntryGuards isn't reliable: if we
  3810. * need guards with weird properties, we can have more than that number
  3811. * live.
  3812. **/
  3813. #if 0
  3814. int n = 0;
  3815. const char *msg;
  3816. const or_options_t *options = get_options();
  3817. if (!entry_guards)
  3818. return;
  3819. SMARTLIST_FOREACH(entry_guards, entry_guard_t *, entry,
  3820. {
  3821. if (entry_is_live(entry, 0, 1, 0, &msg)) {
  3822. if (n++ == options->NumEntryGuards) {
  3823. control_event_guard(entry->nickname, entry->identity, "DEFERRED");
  3824. return;
  3825. }
  3826. }
  3827. });
  3828. #endif
  3829. }
  3830. /** Add a new (preferably stable and fast) router to our
  3831. * entry_guards list. Return a pointer to the router if we succeed,
  3832. * or NULL if we can't find any more suitable entries.
  3833. *
  3834. * If <b>chosen</b> is defined, use that one, and if it's not
  3835. * already in our entry_guards list, put it at the *beginning*.
  3836. * Else, put the one we pick at the end of the list. */
  3837. static const node_t *
  3838. add_an_entry_guard(const node_t *chosen, int reset_status, int prepend)
  3839. {
  3840. const node_t *node;
  3841. entry_guard_t *entry;
  3842. if (chosen) {
  3843. node = chosen;
  3844. entry = entry_guard_get_by_id_digest(node->identity);
  3845. if (entry) {
  3846. if (reset_status) {
  3847. entry->bad_since = 0;
  3848. entry->can_retry = 1;
  3849. }
  3850. return NULL;
  3851. }
  3852. } else {
  3853. node = choose_good_entry_server(CIRCUIT_PURPOSE_C_GENERAL, NULL);
  3854. if (!node)
  3855. return NULL;
  3856. }
  3857. entry = tor_malloc_zero(sizeof(entry_guard_t));
  3858. log_info(LD_CIRC, "Chose %s as new entry guard.",
  3859. node_describe(node));
  3860. strlcpy(entry->nickname, node_get_nickname(node), sizeof(entry->nickname));
  3861. memcpy(entry->identity, node->identity, DIGEST_LEN);
  3862. /* Choose expiry time smudged over the past month. The goal here
  3863. * is to a) spread out when Tor clients rotate their guards, so they
  3864. * don't all select them on the same day, and b) avoid leaving a
  3865. * precise timestamp in the state file about when we first picked
  3866. * this guard. For details, see the Jan 2010 or-dev thread. */
  3867. entry->chosen_on_date = time(NULL) - crypto_rand_int(3600*24*30);
  3868. entry->chosen_by_version = tor_strdup(VERSION);
  3869. if (prepend)
  3870. smartlist_insert(entry_guards, 0, entry);
  3871. else
  3872. smartlist_add(entry_guards, entry);
  3873. control_event_guard(entry->nickname, entry->identity, "NEW");
  3874. control_event_guard_deferred();
  3875. log_entry_guards(LOG_INFO);
  3876. return node;
  3877. }
  3878. /** If the use of entry guards is configured, choose more entry guards
  3879. * until we have enough in the list. */
  3880. static void
  3881. pick_entry_guards(const or_options_t *options)
  3882. {
  3883. int changed = 0;
  3884. tor_assert(entry_guards);
  3885. while (num_live_entry_guards() < options->NumEntryGuards) {
  3886. if (!add_an_entry_guard(NULL, 0, 0))
  3887. break;
  3888. changed = 1;
  3889. }
  3890. if (changed)
  3891. entry_guards_changed();
  3892. }
  3893. /** How long (in seconds) do we allow an entry guard to be nonfunctional,
  3894. * unlisted, excluded, or otherwise nonusable before we give up on it? */
  3895. #define ENTRY_GUARD_REMOVE_AFTER (30*24*60*60)
  3896. /** Release all storage held by <b>e</b>. */
  3897. static void
  3898. entry_guard_free(entry_guard_t *e)
  3899. {
  3900. if (!e)
  3901. return;
  3902. tor_free(e->chosen_by_version);
  3903. tor_free(e);
  3904. }
  3905. /** Remove any entry guard which was selected by an unknown version of Tor,
  3906. * or which was selected by a version of Tor that's known to select
  3907. * entry guards badly, or which was selected more 2 months ago. */
  3908. /* XXXX The "obsolete guards" and "chosen long ago guards" things should
  3909. * probably be different functions. */
  3910. static int
  3911. remove_obsolete_entry_guards(time_t now)
  3912. {
  3913. int changed = 0, i;
  3914. for (i = 0; i < smartlist_len(entry_guards); ++i) {
  3915. entry_guard_t *entry = smartlist_get(entry_guards, i);
  3916. const char *ver = entry->chosen_by_version;
  3917. const char *msg = NULL;
  3918. tor_version_t v;
  3919. int version_is_bad = 0, date_is_bad = 0;
  3920. if (!ver) {
  3921. msg = "does not say what version of Tor it was selected by";
  3922. version_is_bad = 1;
  3923. } else if (tor_version_parse(ver, &v)) {
  3924. msg = "does not seem to be from any recognized version of Tor";
  3925. version_is_bad = 1;
  3926. } else {
  3927. char *tor_ver = NULL;
  3928. tor_asprintf(&tor_ver, "Tor %s", ver);
  3929. if ((tor_version_as_new_as(tor_ver, "0.1.0.10-alpha") &&
  3930. !tor_version_as_new_as(tor_ver, "0.1.2.16-dev")) ||
  3931. (tor_version_as_new_as(tor_ver, "0.2.0.0-alpha") &&
  3932. !tor_version_as_new_as(tor_ver, "0.2.0.6-alpha")) ||
  3933. /* above are bug 440; below are bug 1217 */
  3934. (tor_version_as_new_as(tor_ver, "0.2.1.3-alpha") &&
  3935. !tor_version_as_new_as(tor_ver, "0.2.1.23")) ||
  3936. (tor_version_as_new_as(tor_ver, "0.2.2.0-alpha") &&
  3937. !tor_version_as_new_as(tor_ver, "0.2.2.7-alpha"))) {
  3938. msg = "was selected without regard for guard bandwidth";
  3939. version_is_bad = 1;
  3940. }
  3941. tor_free(tor_ver);
  3942. }
  3943. if (!version_is_bad && entry->chosen_on_date + 3600*24*60 < now) {
  3944. /* It's been 2 months since the date listed in our state file. */
  3945. msg = "was selected several months ago";
  3946. date_is_bad = 1;
  3947. }
  3948. if (version_is_bad || date_is_bad) { /* we need to drop it */
  3949. char dbuf[HEX_DIGEST_LEN+1];
  3950. tor_assert(msg);
  3951. base16_encode(dbuf, sizeof(dbuf), entry->identity, DIGEST_LEN);
  3952. log_fn(version_is_bad ? LOG_NOTICE : LOG_INFO, LD_CIRC,
  3953. "Entry guard '%s' (%s) %s. (Version=%s.) Replacing it.",
  3954. entry->nickname, dbuf, msg, ver?escaped(ver):"none");
  3955. control_event_guard(entry->nickname, entry->identity, "DROPPED");
  3956. entry_guard_free(entry);
  3957. smartlist_del_keeporder(entry_guards, i--);
  3958. log_entry_guards(LOG_INFO);
  3959. changed = 1;
  3960. }
  3961. }
  3962. return changed ? 1 : 0;
  3963. }
  3964. /** Remove all entry guards that have been down or unlisted for so
  3965. * long that we don't think they'll come up again. Return 1 if we
  3966. * removed any, or 0 if we did nothing. */
  3967. static int
  3968. remove_dead_entry_guards(time_t now)
  3969. {
  3970. char dbuf[HEX_DIGEST_LEN+1];
  3971. char tbuf[ISO_TIME_LEN+1];
  3972. int i;
  3973. int changed = 0;
  3974. for (i = 0; i < smartlist_len(entry_guards); ) {
  3975. entry_guard_t *entry = smartlist_get(entry_guards, i);
  3976. if (entry->bad_since &&
  3977. ! entry->path_bias_disabled &&
  3978. entry->bad_since + ENTRY_GUARD_REMOVE_AFTER < now) {
  3979. base16_encode(dbuf, sizeof(dbuf), entry->identity, DIGEST_LEN);
  3980. format_local_iso_time(tbuf, entry->bad_since);
  3981. log_info(LD_CIRC, "Entry guard '%s' (%s) has been down or unlisted "
  3982. "since %s local time; removing.",
  3983. entry->nickname, dbuf, tbuf);
  3984. control_event_guard(entry->nickname, entry->identity, "DROPPED");
  3985. entry_guard_free(entry);
  3986. smartlist_del_keeporder(entry_guards, i);
  3987. log_entry_guards(LOG_INFO);
  3988. changed = 1;
  3989. } else
  3990. ++i;
  3991. }
  3992. return changed ? 1 : 0;
  3993. }
  3994. /** A new directory or router-status has arrived; update the down/listed
  3995. * status of the entry guards.
  3996. *
  3997. * An entry is 'down' if the directory lists it as nonrunning.
  3998. * An entry is 'unlisted' if the directory doesn't include it.
  3999. *
  4000. * Don't call this on startup; only on a fresh download. Otherwise we'll
  4001. * think that things are unlisted.
  4002. */
  4003. void
  4004. entry_guards_compute_status(const or_options_t *options, time_t now)
  4005. {
  4006. int changed = 0;
  4007. digestmap_t *reasons;
  4008. if (! entry_guards)
  4009. return;
  4010. if (options->EntryNodes) /* reshuffle the entry guard list if needed */
  4011. entry_nodes_should_be_added();
  4012. reasons = digestmap_new();
  4013. SMARTLIST_FOREACH_BEGIN(entry_guards, entry_guard_t *, entry)
  4014. {
  4015. const node_t *r = node_get_by_id(entry->identity);
  4016. const char *reason = NULL;
  4017. if (entry_guard_set_status(entry, r, now, options, &reason))
  4018. changed = 1;
  4019. if (entry->bad_since)
  4020. tor_assert(reason);
  4021. if (reason)
  4022. digestmap_set(reasons, entry->identity, (char*)reason);
  4023. }
  4024. SMARTLIST_FOREACH_END(entry);
  4025. if (remove_dead_entry_guards(now))
  4026. changed = 1;
  4027. if (remove_obsolete_entry_guards(now))
  4028. changed = 1;
  4029. if (changed) {
  4030. SMARTLIST_FOREACH_BEGIN(entry_guards, entry_guard_t *, entry) {
  4031. const char *reason = digestmap_get(reasons, entry->identity);
  4032. const char *live_msg = "";
  4033. const node_t *r = entry_is_live(entry, 0, 1, 0, &live_msg);
  4034. log_info(LD_CIRC, "Summary: Entry %s [%s] is %s, %s%s%s, and %s%s.",
  4035. entry->nickname,
  4036. hex_str(entry->identity, DIGEST_LEN),
  4037. entry->unreachable_since ? "unreachable" : "reachable",
  4038. entry->bad_since ? "unusable" : "usable",
  4039. reason ? ", ": "",
  4040. reason ? reason : "",
  4041. r ? "live" : "not live / ",
  4042. r ? "" : live_msg);
  4043. } SMARTLIST_FOREACH_END(entry);
  4044. log_info(LD_CIRC, " (%d/%d entry guards are usable/new)",
  4045. num_live_entry_guards(), smartlist_len(entry_guards));
  4046. log_entry_guards(LOG_INFO);
  4047. entry_guards_changed();
  4048. }
  4049. digestmap_free(reasons, NULL);
  4050. }
  4051. /** Called when a connection to an OR with the identity digest <b>digest</b>
  4052. * is established (<b>succeeded</b>==1) or has failed (<b>succeeded</b>==0).
  4053. * If the OR is an entry, change that entry's up/down status.
  4054. * Return 0 normally, or -1 if we want to tear down the new connection.
  4055. *
  4056. * If <b>mark_relay_status</b>, also call router_set_status() on this
  4057. * relay.
  4058. *
  4059. * XXX024 change succeeded and mark_relay_status into 'int flags'.
  4060. */
  4061. int
  4062. entry_guard_register_connect_status(const char *digest, int succeeded,
  4063. int mark_relay_status, time_t now)
  4064. {
  4065. int changed = 0;
  4066. int refuse_conn = 0;
  4067. int first_contact = 0;
  4068. entry_guard_t *entry = NULL;
  4069. int idx = -1;
  4070. char buf[HEX_DIGEST_LEN+1];
  4071. if (! entry_guards)
  4072. return 0;
  4073. SMARTLIST_FOREACH_BEGIN(entry_guards, entry_guard_t *, e) {
  4074. tor_assert(e);
  4075. if (tor_memeq(e->identity, digest, DIGEST_LEN)) {
  4076. entry = e;
  4077. idx = e_sl_idx;
  4078. break;
  4079. }
  4080. } SMARTLIST_FOREACH_END(e);
  4081. if (!entry)
  4082. return 0;
  4083. base16_encode(buf, sizeof(buf), entry->identity, DIGEST_LEN);
  4084. if (succeeded) {
  4085. if (entry->unreachable_since) {
  4086. log_info(LD_CIRC, "Entry guard '%s' (%s) is now reachable again. Good.",
  4087. entry->nickname, buf);
  4088. entry->can_retry = 0;
  4089. entry->unreachable_since = 0;
  4090. entry->last_attempted = now;
  4091. control_event_guard(entry->nickname, entry->identity, "UP");
  4092. changed = 1;
  4093. }
  4094. if (!entry->made_contact) {
  4095. entry->made_contact = 1;
  4096. first_contact = changed = 1;
  4097. }
  4098. } else { /* ! succeeded */
  4099. if (!entry->made_contact) {
  4100. /* We've never connected to this one. */
  4101. log_info(LD_CIRC,
  4102. "Connection to never-contacted entry guard '%s' (%s) failed. "
  4103. "Removing from the list. %d/%d entry guards usable/new.",
  4104. entry->nickname, buf,
  4105. num_live_entry_guards()-1, smartlist_len(entry_guards)-1);
  4106. control_event_guard(entry->nickname, entry->identity, "DROPPED");
  4107. entry_guard_free(entry);
  4108. smartlist_del_keeporder(entry_guards, idx);
  4109. log_entry_guards(LOG_INFO);
  4110. changed = 1;
  4111. } else if (!entry->unreachable_since) {
  4112. log_info(LD_CIRC, "Unable to connect to entry guard '%s' (%s). "
  4113. "Marking as unreachable.", entry->nickname, buf);
  4114. entry->unreachable_since = entry->last_attempted = now;
  4115. control_event_guard(entry->nickname, entry->identity, "DOWN");
  4116. changed = 1;
  4117. entry->can_retry = 0; /* We gave it an early chance; no good. */
  4118. } else {
  4119. char tbuf[ISO_TIME_LEN+1];
  4120. format_iso_time(tbuf, entry->unreachable_since);
  4121. log_debug(LD_CIRC, "Failed to connect to unreachable entry guard "
  4122. "'%s' (%s). It has been unreachable since %s.",
  4123. entry->nickname, buf, tbuf);
  4124. entry->last_attempted = now;
  4125. entry->can_retry = 0; /* We gave it an early chance; no good. */
  4126. }
  4127. }
  4128. /* if the caller asked us to, also update the is_running flags for this
  4129. * relay */
  4130. if (mark_relay_status)
  4131. router_set_status(digest, succeeded);
  4132. if (first_contact) {
  4133. /* We've just added a new long-term entry guard. Perhaps the network just
  4134. * came back? We should give our earlier entries another try too,
  4135. * and close this connection so we don't use it before we've given
  4136. * the others a shot. */
  4137. SMARTLIST_FOREACH_BEGIN(entry_guards, entry_guard_t *, e) {
  4138. if (e == entry)
  4139. break;
  4140. if (e->made_contact) {
  4141. const char *msg;
  4142. const node_t *r = entry_is_live(e, 0, 1, 1, &msg);
  4143. if (r && e->unreachable_since) {
  4144. refuse_conn = 1;
  4145. e->can_retry = 1;
  4146. }
  4147. }
  4148. } SMARTLIST_FOREACH_END(e);
  4149. if (refuse_conn) {
  4150. log_info(LD_CIRC,
  4151. "Connected to new entry guard '%s' (%s). Marking earlier "
  4152. "entry guards up. %d/%d entry guards usable/new.",
  4153. entry->nickname, buf,
  4154. num_live_entry_guards(), smartlist_len(entry_guards));
  4155. log_entry_guards(LOG_INFO);
  4156. changed = 1;
  4157. }
  4158. }
  4159. if (changed)
  4160. entry_guards_changed();
  4161. return refuse_conn ? -1 : 0;
  4162. }
  4163. /** When we try to choose an entry guard, should we parse and add
  4164. * config's EntryNodes first? */
  4165. static int should_add_entry_nodes = 0;
  4166. /** Called when the value of EntryNodes changes in our configuration. */
  4167. void
  4168. entry_nodes_should_be_added(void)
  4169. {
  4170. log_info(LD_CIRC, "EntryNodes config option set. Putting configured "
  4171. "relays at the front of the entry guard list.");
  4172. should_add_entry_nodes = 1;
  4173. }
  4174. /** Adjust the entry guards list so that it only contains entries from
  4175. * EntryNodes, adding new entries from EntryNodes to the list as needed. */
  4176. static void
  4177. entry_guards_set_from_config(const or_options_t *options)
  4178. {
  4179. smartlist_t *entry_nodes, *worse_entry_nodes, *entry_fps;
  4180. smartlist_t *old_entry_guards_on_list, *old_entry_guards_not_on_list;
  4181. tor_assert(entry_guards);
  4182. should_add_entry_nodes = 0;
  4183. if (!options->EntryNodes) {
  4184. /* It's possible that a controller set EntryNodes, thus making
  4185. * should_add_entry_nodes set, then cleared it again, all before the
  4186. * call to choose_random_entry() that triggered us. If so, just return.
  4187. */
  4188. return;
  4189. }
  4190. {
  4191. char *string = routerset_to_string(options->EntryNodes);
  4192. log_info(LD_CIRC,"Adding configured EntryNodes '%s'.", string);
  4193. tor_free(string);
  4194. }
  4195. entry_nodes = smartlist_new();
  4196. worse_entry_nodes = smartlist_new();
  4197. entry_fps = smartlist_new();
  4198. old_entry_guards_on_list = smartlist_new();
  4199. old_entry_guards_not_on_list = smartlist_new();
  4200. /* Split entry guards into those on the list and those not. */
  4201. routerset_get_all_nodes(entry_nodes, options->EntryNodes,
  4202. options->ExcludeNodes, 0);
  4203. SMARTLIST_FOREACH(entry_nodes, const node_t *,node,
  4204. smartlist_add(entry_fps, (void*)node->identity));
  4205. SMARTLIST_FOREACH(entry_guards, entry_guard_t *, e, {
  4206. if (smartlist_digest_isin(entry_fps, e->identity))
  4207. smartlist_add(old_entry_guards_on_list, e);
  4208. else
  4209. smartlist_add(old_entry_guards_not_on_list, e);
  4210. });
  4211. /* Remove all currently configured guard nodes, excluded nodes, unreachable
  4212. * nodes, or non-Guard nodes from entry_nodes. */
  4213. SMARTLIST_FOREACH_BEGIN(entry_nodes, const node_t *, node) {
  4214. if (entry_guard_get_by_id_digest(node->identity)) {
  4215. SMARTLIST_DEL_CURRENT(entry_nodes, node);
  4216. continue;
  4217. } else if (routerset_contains_node(options->ExcludeNodes, node)) {
  4218. SMARTLIST_DEL_CURRENT(entry_nodes, node);
  4219. continue;
  4220. } else if (!fascist_firewall_allows_node(node)) {
  4221. SMARTLIST_DEL_CURRENT(entry_nodes, node);
  4222. continue;
  4223. } else if (! node->is_possible_guard) {
  4224. smartlist_add(worse_entry_nodes, (node_t*)node);
  4225. SMARTLIST_DEL_CURRENT(entry_nodes, node);
  4226. }
  4227. } SMARTLIST_FOREACH_END(node);
  4228. /* Now build the new entry_guards list. */
  4229. smartlist_clear(entry_guards);
  4230. /* First, the previously configured guards that are in EntryNodes. */
  4231. smartlist_add_all(entry_guards, old_entry_guards_on_list);
  4232. /* Next, scramble the rest of EntryNodes, putting the guards first. */
  4233. smartlist_shuffle(entry_nodes);
  4234. smartlist_shuffle(worse_entry_nodes);
  4235. smartlist_add_all(entry_nodes, worse_entry_nodes);
  4236. /* Next, the rest of EntryNodes */
  4237. SMARTLIST_FOREACH_BEGIN(entry_nodes, const node_t *, node) {
  4238. add_an_entry_guard(node, 0, 0);
  4239. if (smartlist_len(entry_guards) > options->NumEntryGuards * 10)
  4240. break;
  4241. } SMARTLIST_FOREACH_END(node);
  4242. log_notice(LD_GENERAL, "%d entries in guards", smartlist_len(entry_guards));
  4243. /* Finally, free the remaining previously configured guards that are not in
  4244. * EntryNodes. */
  4245. SMARTLIST_FOREACH(old_entry_guards_not_on_list, entry_guard_t *, e,
  4246. entry_guard_free(e));
  4247. smartlist_free(entry_nodes);
  4248. smartlist_free(worse_entry_nodes);
  4249. smartlist_free(entry_fps);
  4250. smartlist_free(old_entry_guards_on_list);
  4251. smartlist_free(old_entry_guards_not_on_list);
  4252. entry_guards_changed();
  4253. }
  4254. /** Return 0 if we're fine adding arbitrary routers out of the
  4255. * directory to our entry guard list, or return 1 if we have a
  4256. * list already and we must stick to it.
  4257. */
  4258. int
  4259. entry_list_is_constrained(const or_options_t *options)
  4260. {
  4261. if (options->EntryNodes)
  4262. return 1;
  4263. if (options->UseBridges)
  4264. return 1;
  4265. return 0;
  4266. }
  4267. /** Pick a live (up and listed) entry guard from entry_guards. If
  4268. * <b>state</b> is non-NULL, this is for a specific circuit --
  4269. * make sure not to pick this circuit's exit or any node in the
  4270. * exit's family. If <b>state</b> is NULL, we're looking for a random
  4271. * guard (likely a bridge). */
  4272. const node_t *
  4273. choose_random_entry(cpath_build_state_t *state)
  4274. {
  4275. const or_options_t *options = get_options();
  4276. smartlist_t *live_entry_guards = smartlist_new();
  4277. smartlist_t *exit_family = smartlist_new();
  4278. const node_t *chosen_exit =
  4279. state?build_state_get_exit_node(state) : NULL;
  4280. const node_t *node = NULL;
  4281. int need_uptime = state ? state->need_uptime : 0;
  4282. int need_capacity = state ? state->need_capacity : 0;
  4283. int preferred_min, consider_exit_family = 0;
  4284. if (chosen_exit) {
  4285. nodelist_add_node_and_family(exit_family, chosen_exit);
  4286. consider_exit_family = 1;
  4287. }
  4288. if (!entry_guards)
  4289. entry_guards = smartlist_new();
  4290. if (should_add_entry_nodes)
  4291. entry_guards_set_from_config(options);
  4292. if (!entry_list_is_constrained(options) &&
  4293. smartlist_len(entry_guards) < options->NumEntryGuards)
  4294. pick_entry_guards(options);
  4295. retry:
  4296. smartlist_clear(live_entry_guards);
  4297. SMARTLIST_FOREACH_BEGIN(entry_guards, entry_guard_t *, entry) {
  4298. const char *msg;
  4299. node = entry_is_live(entry, need_uptime, need_capacity, 0, &msg);
  4300. if (!node)
  4301. continue; /* down, no point */
  4302. if (node == chosen_exit)
  4303. continue; /* don't pick the same node for entry and exit */
  4304. if (consider_exit_family && smartlist_isin(exit_family, node))
  4305. continue; /* avoid relays that are family members of our exit */
  4306. #if 0 /* since EntryNodes is always strict now, this clause is moot */
  4307. if (options->EntryNodes &&
  4308. !routerset_contains_node(options->EntryNodes, node)) {
  4309. /* We've come to the end of our preferred entry nodes. */
  4310. if (smartlist_len(live_entry_guards))
  4311. goto choose_and_finish; /* only choose from the ones we like */
  4312. if (options->StrictNodes) {
  4313. /* in theory this case should never happen, since
  4314. * entry_guards_set_from_config() drops unwanted relays */
  4315. tor_fragile_assert();
  4316. } else {
  4317. log_info(LD_CIRC,
  4318. "No relays from EntryNodes available. Using others.");
  4319. }
  4320. }
  4321. #endif
  4322. smartlist_add(live_entry_guards, (void*)node);
  4323. if (!entry->made_contact) {
  4324. /* Always start with the first not-yet-contacted entry
  4325. * guard. Otherwise we might add several new ones, pick
  4326. * the second new one, and now we've expanded our entry
  4327. * guard list without needing to. */
  4328. goto choose_and_finish;
  4329. }
  4330. if (smartlist_len(live_entry_guards) >= options->NumEntryGuards)
  4331. goto choose_and_finish; /* we have enough */
  4332. } SMARTLIST_FOREACH_END(entry);
  4333. if (entry_list_is_constrained(options)) {
  4334. /* If we prefer the entry nodes we've got, and we have at least
  4335. * one choice, that's great. Use it. */
  4336. preferred_min = 1;
  4337. } else {
  4338. /* Try to have at least 2 choices available. This way we don't
  4339. * get stuck with a single live-but-crummy entry and just keep
  4340. * using him.
  4341. * (We might get 2 live-but-crummy entry guards, but so be it.) */
  4342. preferred_min = 2;
  4343. }
  4344. if (smartlist_len(live_entry_guards) < preferred_min) {
  4345. if (!entry_list_is_constrained(options)) {
  4346. /* still no? try adding a new entry then */
  4347. /* XXX if guard doesn't imply fast and stable, then we need
  4348. * to tell add_an_entry_guard below what we want, or it might
  4349. * be a long time til we get it. -RD */
  4350. node = add_an_entry_guard(NULL, 0, 0);
  4351. if (node) {
  4352. entry_guards_changed();
  4353. /* XXX we start over here in case the new node we added shares
  4354. * a family with our exit node. There's a chance that we'll just
  4355. * load up on entry guards here, if the network we're using is
  4356. * one big family. Perhaps we should teach add_an_entry_guard()
  4357. * to understand nodes-to-avoid-if-possible? -RD */
  4358. goto retry;
  4359. }
  4360. }
  4361. if (!node && need_uptime) {
  4362. need_uptime = 0; /* try without that requirement */
  4363. goto retry;
  4364. }
  4365. if (!node && need_capacity) {
  4366. /* still no? last attempt, try without requiring capacity */
  4367. need_capacity = 0;
  4368. goto retry;
  4369. }
  4370. #if 0
  4371. /* Removing this retry logic: if we only allow one exit, and it is in the
  4372. same family as all our entries, then we are just plain not going to win
  4373. here. */
  4374. if (!node && entry_list_is_constrained(options) && consider_exit_family) {
  4375. /* still no? if we're using bridges or have strictentrynodes
  4376. * set, and our chosen exit is in the same family as all our
  4377. * bridges/entry guards, then be flexible about families. */
  4378. consider_exit_family = 0;
  4379. goto retry;
  4380. }
  4381. #endif
  4382. /* live_entry_guards may be empty below. Oh well, we tried. */
  4383. }
  4384. choose_and_finish:
  4385. if (entry_list_is_constrained(options)) {
  4386. /* We need to weight by bandwidth, because our bridges or entryguards
  4387. * were not already selected proportional to their bandwidth. */
  4388. node = node_sl_choose_by_bandwidth(live_entry_guards, WEIGHT_FOR_GUARD);
  4389. } else {
  4390. /* We choose uniformly at random here, because choose_good_entry_server()
  4391. * already weights its choices by bandwidth, so we don't want to
  4392. * *double*-weight our guard selection. */
  4393. node = smartlist_choose(live_entry_guards);
  4394. }
  4395. smartlist_free(live_entry_guards);
  4396. smartlist_free(exit_family);
  4397. return node;
  4398. }
  4399. /** Parse <b>state</b> and learn about the entry guards it describes.
  4400. * If <b>set</b> is true, and there are no errors, replace the global
  4401. * entry_list with what we find.
  4402. * On success, return 0. On failure, alloc into *<b>msg</b> a string
  4403. * describing the error, and return -1.
  4404. */
  4405. int
  4406. entry_guards_parse_state(or_state_t *state, int set, char **msg)
  4407. {
  4408. entry_guard_t *node = NULL;
  4409. smartlist_t *new_entry_guards = smartlist_new();
  4410. config_line_t *line;
  4411. time_t now = time(NULL);
  4412. const char *state_version = state->TorVersion;
  4413. digestmap_t *added_by = digestmap_new();
  4414. *msg = NULL;
  4415. for (line = state->EntryGuards; line; line = line->next) {
  4416. if (!strcasecmp(line->key, "EntryGuard")) {
  4417. smartlist_t *args = smartlist_new();
  4418. node = tor_malloc_zero(sizeof(entry_guard_t));
  4419. /* all entry guards on disk have been contacted */
  4420. node->made_contact = 1;
  4421. smartlist_add(new_entry_guards, node);
  4422. smartlist_split_string(args, line->value, " ",
  4423. SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
  4424. if (smartlist_len(args)<2) {
  4425. *msg = tor_strdup("Unable to parse entry nodes: "
  4426. "Too few arguments to EntryGuard");
  4427. } else if (!is_legal_nickname(smartlist_get(args,0))) {
  4428. *msg = tor_strdup("Unable to parse entry nodes: "
  4429. "Bad nickname for EntryGuard");
  4430. } else {
  4431. strlcpy(node->nickname, smartlist_get(args,0), MAX_NICKNAME_LEN+1);
  4432. if (base16_decode(node->identity, DIGEST_LEN, smartlist_get(args,1),
  4433. strlen(smartlist_get(args,1)))<0) {
  4434. *msg = tor_strdup("Unable to parse entry nodes: "
  4435. "Bad hex digest for EntryGuard");
  4436. }
  4437. }
  4438. SMARTLIST_FOREACH(args, char*, cp, tor_free(cp));
  4439. smartlist_free(args);
  4440. if (*msg)
  4441. break;
  4442. } else if (!strcasecmp(line->key, "EntryGuardDownSince") ||
  4443. !strcasecmp(line->key, "EntryGuardUnlistedSince")) {
  4444. time_t when;
  4445. time_t last_try = 0;
  4446. if (!node) {
  4447. *msg = tor_strdup("Unable to parse entry nodes: "
  4448. "EntryGuardDownSince/UnlistedSince without EntryGuard");
  4449. break;
  4450. }
  4451. if (parse_iso_time(line->value, &when)<0) {
  4452. *msg = tor_strdup("Unable to parse entry nodes: "
  4453. "Bad time in EntryGuardDownSince/UnlistedSince");
  4454. break;
  4455. }
  4456. if (when > now) {
  4457. /* It's a bad idea to believe info in the future: you can wind
  4458. * up with timeouts that aren't allowed to happen for years. */
  4459. continue;
  4460. }
  4461. if (strlen(line->value) >= ISO_TIME_LEN+ISO_TIME_LEN+1) {
  4462. /* ignore failure */
  4463. (void) parse_iso_time(line->value+ISO_TIME_LEN+1, &last_try);
  4464. }
  4465. if (!strcasecmp(line->key, "EntryGuardDownSince")) {
  4466. node->unreachable_since = when;
  4467. node->last_attempted = last_try;
  4468. } else {
  4469. node->bad_since = when;
  4470. }
  4471. } else if (!strcasecmp(line->key, "EntryGuardAddedBy")) {
  4472. char d[DIGEST_LEN];
  4473. /* format is digest version date */
  4474. if (strlen(line->value) < HEX_DIGEST_LEN+1+1+1+ISO_TIME_LEN) {
  4475. log_warn(LD_BUG, "EntryGuardAddedBy line is not long enough.");
  4476. continue;
  4477. }
  4478. if (base16_decode(d, sizeof(d), line->value, HEX_DIGEST_LEN)<0 ||
  4479. line->value[HEX_DIGEST_LEN] != ' ') {
  4480. log_warn(LD_BUG, "EntryGuardAddedBy line %s does not begin with "
  4481. "hex digest", escaped(line->value));
  4482. continue;
  4483. }
  4484. digestmap_set(added_by, d, tor_strdup(line->value+HEX_DIGEST_LEN+1));
  4485. } else if (!strcasecmp(line->key, "EntryGuardPathBias")) {
  4486. const or_options_t *options = get_options();
  4487. unsigned hop_cnt, success_cnt;
  4488. if (!node) {
  4489. *msg = tor_strdup("Unable to parse entry nodes: "
  4490. "EntryGuardPathBias without EntryGuard");
  4491. break;
  4492. }
  4493. if (tor_sscanf(line->value, "%u %u", &success_cnt, &hop_cnt) != 2) {
  4494. log_warn(LD_GENERAL, "Unable to parse guard path bias info: "
  4495. "Misformated EntryGuardPathBias %s", escaped(line->value));
  4496. continue;
  4497. }
  4498. node->first_hops = hop_cnt;
  4499. node->circuit_successes = success_cnt;
  4500. log_info(LD_GENERAL, "Read %u/%u path bias for node %s",
  4501. node->circuit_successes, node->first_hops, node->nickname);
  4502. /* Note: We rely on the < comparison here to allow us to set a 0
  4503. * rate and disable the feature entirely. If refactoring, don't
  4504. * change to <= */
  4505. if (node->circuit_successes/((double)node->first_hops)
  4506. < pathbias_get_disable_rate(options)) {
  4507. node->path_bias_disabled = 1;
  4508. log_info(LD_GENERAL,
  4509. "Path bias is too high (%u/%u); disabling node %s",
  4510. node->circuit_successes, node->first_hops, node->nickname);
  4511. }
  4512. } else {
  4513. log_warn(LD_BUG, "Unexpected key %s", line->key);
  4514. }
  4515. }
  4516. SMARTLIST_FOREACH_BEGIN(new_entry_guards, entry_guard_t *, e) {
  4517. char *sp;
  4518. char *val = digestmap_get(added_by, e->identity);
  4519. if (val && (sp = strchr(val, ' '))) {
  4520. time_t when;
  4521. *sp++ = '\0';
  4522. if (parse_iso_time(sp, &when)<0) {
  4523. log_warn(LD_BUG, "Can't read time %s in EntryGuardAddedBy", sp);
  4524. } else {
  4525. e->chosen_by_version = tor_strdup(val);
  4526. e->chosen_on_date = when;
  4527. }
  4528. } else {
  4529. if (state_version) {
  4530. e->chosen_by_version = tor_strdup(state_version);
  4531. e->chosen_on_date = time(NULL) - crypto_rand_int(3600*24*30);
  4532. }
  4533. }
  4534. if (e->path_bias_disabled && !e->bad_since)
  4535. e->bad_since = time(NULL);
  4536. }
  4537. SMARTLIST_FOREACH_END(e);
  4538. if (*msg || !set) {
  4539. SMARTLIST_FOREACH(new_entry_guards, entry_guard_t *, e,
  4540. entry_guard_free(e));
  4541. smartlist_free(new_entry_guards);
  4542. } else { /* !err && set */
  4543. if (entry_guards) {
  4544. SMARTLIST_FOREACH(entry_guards, entry_guard_t *, e,
  4545. entry_guard_free(e));
  4546. smartlist_free(entry_guards);
  4547. }
  4548. entry_guards = new_entry_guards;
  4549. entry_guards_dirty = 0;
  4550. /* XXX024 hand new_entry_guards to this func, and move it up a
  4551. * few lines, so we don't have to re-dirty it */
  4552. if (remove_obsolete_entry_guards(now))
  4553. entry_guards_dirty = 1;
  4554. }
  4555. digestmap_free(added_by, _tor_free);
  4556. return *msg ? -1 : 0;
  4557. }
  4558. /** Our list of entry guards has changed, or some element of one
  4559. * of our entry guards has changed. Write the changes to disk within
  4560. * the next few minutes.
  4561. */
  4562. static void
  4563. entry_guards_changed(void)
  4564. {
  4565. time_t when;
  4566. entry_guards_dirty = 1;
  4567. /* or_state_save() will call entry_guards_update_state(). */
  4568. when = get_options()->AvoidDiskWrites ? time(NULL) + 3600 : time(NULL)+600;
  4569. or_state_mark_dirty(get_or_state(), when);
  4570. }
  4571. /** If the entry guard info has not changed, do nothing and return.
  4572. * Otherwise, free the EntryGuards piece of <b>state</b> and create
  4573. * a new one out of the global entry_guards list, and then mark
  4574. * <b>state</b> dirty so it will get saved to disk.
  4575. */
  4576. void
  4577. entry_guards_update_state(or_state_t *state)
  4578. {
  4579. config_line_t **next, *line;
  4580. if (! entry_guards_dirty)
  4581. return;
  4582. config_free_lines(state->EntryGuards);
  4583. next = &state->EntryGuards;
  4584. *next = NULL;
  4585. if (!entry_guards)
  4586. entry_guards = smartlist_new();
  4587. SMARTLIST_FOREACH_BEGIN(entry_guards, entry_guard_t *, e) {
  4588. char dbuf[HEX_DIGEST_LEN+1];
  4589. if (!e->made_contact)
  4590. continue; /* don't write this one to disk */
  4591. *next = line = tor_malloc_zero(sizeof(config_line_t));
  4592. line->key = tor_strdup("EntryGuard");
  4593. base16_encode(dbuf, sizeof(dbuf), e->identity, DIGEST_LEN);
  4594. tor_asprintf(&line->value, "%s %s", e->nickname, dbuf);
  4595. next = &(line->next);
  4596. if (e->unreachable_since) {
  4597. *next = line = tor_malloc_zero(sizeof(config_line_t));
  4598. line->key = tor_strdup("EntryGuardDownSince");
  4599. line->value = tor_malloc(ISO_TIME_LEN+1+ISO_TIME_LEN+1);
  4600. format_iso_time(line->value, e->unreachable_since);
  4601. if (e->last_attempted) {
  4602. line->value[ISO_TIME_LEN] = ' ';
  4603. format_iso_time(line->value+ISO_TIME_LEN+1, e->last_attempted);
  4604. }
  4605. next = &(line->next);
  4606. }
  4607. if (e->bad_since) {
  4608. *next = line = tor_malloc_zero(sizeof(config_line_t));
  4609. line->key = tor_strdup("EntryGuardUnlistedSince");
  4610. line->value = tor_malloc(ISO_TIME_LEN+1);
  4611. format_iso_time(line->value, e->bad_since);
  4612. next = &(line->next);
  4613. }
  4614. if (e->chosen_on_date && e->chosen_by_version &&
  4615. !strchr(e->chosen_by_version, ' ')) {
  4616. char d[HEX_DIGEST_LEN+1];
  4617. char t[ISO_TIME_LEN+1];
  4618. *next = line = tor_malloc_zero(sizeof(config_line_t));
  4619. line->key = tor_strdup("EntryGuardAddedBy");
  4620. base16_encode(d, sizeof(d), e->identity, DIGEST_LEN);
  4621. format_iso_time(t, e->chosen_on_date);
  4622. tor_asprintf(&line->value, "%s %s %s",
  4623. d, e->chosen_by_version, t);
  4624. next = &(line->next);
  4625. }
  4626. if (e->first_hops) {
  4627. *next = line = tor_malloc_zero(sizeof(config_line_t));
  4628. line->key = tor_strdup("EntryGuardPathBias");
  4629. tor_asprintf(&line->value, "%u %u",
  4630. e->circuit_successes, e->first_hops);
  4631. next = &(line->next);
  4632. }
  4633. } SMARTLIST_FOREACH_END(e);
  4634. if (!get_options()->AvoidDiskWrites)
  4635. or_state_mark_dirty(get_or_state(), 0);
  4636. entry_guards_dirty = 0;
  4637. }
  4638. /** If <b>question</b> is the string "entry-guards", then dump
  4639. * to *<b>answer</b> a newly allocated string describing all of
  4640. * the nodes in the global entry_guards list. See control-spec.txt
  4641. * for details.
  4642. * For backward compatibility, we also handle the string "helper-nodes".
  4643. * */
  4644. int
  4645. getinfo_helper_entry_guards(control_connection_t *conn,
  4646. const char *question, char **answer,
  4647. const char **errmsg)
  4648. {
  4649. (void) conn;
  4650. (void) errmsg;
  4651. if (!strcmp(question,"entry-guards") ||
  4652. !strcmp(question,"helper-nodes")) {
  4653. smartlist_t *sl = smartlist_new();
  4654. char tbuf[ISO_TIME_LEN+1];
  4655. char nbuf[MAX_VERBOSE_NICKNAME_LEN+1];
  4656. if (!entry_guards)
  4657. entry_guards = smartlist_new();
  4658. SMARTLIST_FOREACH_BEGIN(entry_guards, entry_guard_t *, e) {
  4659. const char *status = NULL;
  4660. time_t when = 0;
  4661. const node_t *node;
  4662. if (!e->made_contact) {
  4663. status = "never-connected";
  4664. } else if (e->bad_since) {
  4665. when = e->bad_since;
  4666. status = "unusable";
  4667. } else {
  4668. status = "up";
  4669. }
  4670. node = node_get_by_id(e->identity);
  4671. if (node) {
  4672. node_get_verbose_nickname(node, nbuf);
  4673. } else {
  4674. nbuf[0] = '$';
  4675. base16_encode(nbuf+1, sizeof(nbuf)-1, e->identity, DIGEST_LEN);
  4676. /* e->nickname field is not very reliable if we don't know about
  4677. * this router any longer; don't include it. */
  4678. }
  4679. if (when) {
  4680. format_iso_time(tbuf, when);
  4681. smartlist_add_asprintf(sl, "%s %s %s\n", nbuf, status, tbuf);
  4682. } else {
  4683. smartlist_add_asprintf(sl, "%s %s\n", nbuf, status);
  4684. }
  4685. } SMARTLIST_FOREACH_END(e);
  4686. *answer = smartlist_join_strings(sl, "", 0, NULL);
  4687. SMARTLIST_FOREACH(sl, char *, c, tor_free(c));
  4688. smartlist_free(sl);
  4689. }
  4690. return 0;
  4691. }
  4692. /** A list of configured bridges. Whenever we actually get a descriptor
  4693. * for one, we add it as an entry guard. Note that the order of bridges
  4694. * in this list does not necessarily correspond to the order of bridges
  4695. * in the torrc. */
  4696. static smartlist_t *bridge_list = NULL;
  4697. /** Mark every entry of the bridge list to be removed on our next call to
  4698. * sweep_bridge_list unless it has first been un-marked. */
  4699. void
  4700. mark_bridge_list(void)
  4701. {
  4702. if (!bridge_list)
  4703. bridge_list = smartlist_new();
  4704. SMARTLIST_FOREACH(bridge_list, bridge_info_t *, b,
  4705. b->marked_for_removal = 1);
  4706. }
  4707. /** Remove every entry of the bridge list that was marked with
  4708. * mark_bridge_list if it has not subsequently been un-marked. */
  4709. void
  4710. sweep_bridge_list(void)
  4711. {
  4712. if (!bridge_list)
  4713. bridge_list = smartlist_new();
  4714. SMARTLIST_FOREACH_BEGIN(bridge_list, bridge_info_t *, b) {
  4715. if (b->marked_for_removal) {
  4716. SMARTLIST_DEL_CURRENT(bridge_list, b);
  4717. bridge_free(b);
  4718. }
  4719. } SMARTLIST_FOREACH_END(b);
  4720. }
  4721. /** Initialize the bridge list to empty, creating it if needed. */
  4722. static void
  4723. clear_bridge_list(void)
  4724. {
  4725. if (!bridge_list)
  4726. bridge_list = smartlist_new();
  4727. SMARTLIST_FOREACH(bridge_list, bridge_info_t *, b, bridge_free(b));
  4728. smartlist_clear(bridge_list);
  4729. }
  4730. /** Free the bridge <b>bridge</b>. */
  4731. static void
  4732. bridge_free(bridge_info_t *bridge)
  4733. {
  4734. if (!bridge)
  4735. return;
  4736. tor_free(bridge->transport_name);
  4737. tor_free(bridge);
  4738. }
  4739. /** If we have a bridge configured whose digest matches <b>digest</b>, or a
  4740. * bridge with no known digest whose address matches any of the
  4741. * tor_addr_port_t's in <b>orports</b>, return that bridge. Else return
  4742. * NULL. */
  4743. static bridge_info_t *
  4744. get_configured_bridge_by_orports_digest(const char *digest,
  4745. const smartlist_t *orports)
  4746. {
  4747. if (!bridge_list)
  4748. return NULL;
  4749. SMARTLIST_FOREACH_BEGIN(bridge_list, bridge_info_t *, bridge)
  4750. {
  4751. if (tor_digest_is_zero(bridge->identity)) {
  4752. SMARTLIST_FOREACH_BEGIN(orports, tor_addr_port_t *, ap)
  4753. {
  4754. if (tor_addr_compare(&bridge->addr, &ap->addr, CMP_EXACT) == 0 &&
  4755. bridge->port == ap->port)
  4756. return bridge;
  4757. }
  4758. SMARTLIST_FOREACH_END(ap);
  4759. }
  4760. if (digest && tor_memeq(bridge->identity, digest, DIGEST_LEN))
  4761. return bridge;
  4762. }
  4763. SMARTLIST_FOREACH_END(bridge);
  4764. return NULL;
  4765. }
  4766. /** If we have a bridge configured whose digest matches <b>digest</b>, or a
  4767. * bridge with no known digest whose address matches <b>addr</b>:<b>/port</b>,
  4768. * return that bridge. Else return NULL. */
  4769. static bridge_info_t *
  4770. get_configured_bridge_by_addr_port_digest(const tor_addr_t *addr,
  4771. uint16_t port,
  4772. const char *digest)
  4773. {
  4774. if (!bridge_list)
  4775. return NULL;
  4776. SMARTLIST_FOREACH_BEGIN(bridge_list, bridge_info_t *, bridge)
  4777. {
  4778. if (tor_digest_is_zero(bridge->identity) &&
  4779. !tor_addr_compare(&bridge->addr, addr, CMP_EXACT) &&
  4780. bridge->port == port)
  4781. return bridge;
  4782. if (digest && tor_memeq(bridge->identity, digest, DIGEST_LEN))
  4783. return bridge;
  4784. }
  4785. SMARTLIST_FOREACH_END(bridge);
  4786. return NULL;
  4787. }
  4788. /** Wrapper around get_configured_bridge_by_addr_port_digest() to look
  4789. * it up via router descriptor <b>ri</b>. */
  4790. static bridge_info_t *
  4791. get_configured_bridge_by_routerinfo(const routerinfo_t *ri)
  4792. {
  4793. bridge_info_t *bi = NULL;
  4794. smartlist_t *orports = router_get_all_orports(ri);
  4795. bi = get_configured_bridge_by_orports_digest(ri->cache_info.identity_digest,
  4796. orports);
  4797. SMARTLIST_FOREACH(orports, tor_addr_port_t *, p, tor_free(p));
  4798. smartlist_free(orports);
  4799. return bi;
  4800. }
  4801. /** Return 1 if <b>ri</b> is one of our known bridges, else 0. */
  4802. int
  4803. routerinfo_is_a_configured_bridge(const routerinfo_t *ri)
  4804. {
  4805. return get_configured_bridge_by_routerinfo(ri) ? 1 : 0;
  4806. }
  4807. /** Return 1 if <b>node</b> is one of our configured bridges, else 0. */
  4808. int
  4809. node_is_a_configured_bridge(const node_t *node)
  4810. {
  4811. int retval = 0;
  4812. smartlist_t *orports = node_get_all_orports(node);
  4813. retval = get_configured_bridge_by_orports_digest(node->identity,
  4814. orports) != NULL;
  4815. SMARTLIST_FOREACH(orports, tor_addr_port_t *, p, tor_free(p));
  4816. smartlist_free(orports);
  4817. return retval;
  4818. }
  4819. /** We made a connection to a router at <b>addr</b>:<b>port</b>
  4820. * without knowing its digest. Its digest turned out to be <b>digest</b>.
  4821. * If it was a bridge, and we still don't know its digest, record it.
  4822. */
  4823. void
  4824. learned_router_identity(const tor_addr_t *addr, uint16_t port,
  4825. const char *digest)
  4826. {
  4827. bridge_info_t *bridge =
  4828. get_configured_bridge_by_addr_port_digest(addr, port, digest);
  4829. if (bridge && tor_digest_is_zero(bridge->identity)) {
  4830. memcpy(bridge->identity, digest, DIGEST_LEN);
  4831. log_notice(LD_DIR, "Learned fingerprint %s for bridge %s:%d",
  4832. hex_str(digest, DIGEST_LEN), fmt_addr(addr), port);
  4833. }
  4834. }
  4835. /** Return true if <b>bridge</b> has the same identity digest as
  4836. * <b>digest</b>. If <b>digest</b> is NULL, it matches
  4837. * bridges with unspecified identity digests. */
  4838. static int
  4839. bridge_has_digest(const bridge_info_t *bridge, const char *digest)
  4840. {
  4841. if (digest)
  4842. return tor_memeq(digest, bridge->identity, DIGEST_LEN);
  4843. else
  4844. return tor_digest_is_zero(bridge->identity);
  4845. }
  4846. /** We are about to add a new bridge at <b>addr</b>:<b>port</b>, with optional
  4847. * <b>digest</b> and <b>transport_name</b>. Mark for removal any previously
  4848. * existing bridge with the same address and port, and warn the user as
  4849. * appropriate.
  4850. */
  4851. static void
  4852. bridge_resolve_conflicts(const tor_addr_t *addr, uint16_t port,
  4853. const char *digest, const char *transport_name)
  4854. {
  4855. /* Iterate the already-registered bridge list:
  4856. If you find a bridge with the same adress and port, mark it for
  4857. removal. It doesn't make sense to have two active bridges with
  4858. the same IP:PORT. If the bridge in question has a different
  4859. digest or transport than <b>digest</b>/<b>transport_name</b>,
  4860. it's probably a misconfiguration and we should warn the user.
  4861. */
  4862. SMARTLIST_FOREACH_BEGIN(bridge_list, bridge_info_t *, bridge) {
  4863. if (bridge->marked_for_removal)
  4864. continue;
  4865. if (tor_addr_eq(&bridge->addr, addr) && (bridge->port == port)) {
  4866. bridge->marked_for_removal = 1;
  4867. if (!bridge_has_digest(bridge, digest) ||
  4868. strcmp_opt(bridge->transport_name, transport_name)) {
  4869. /* warn the user */
  4870. char *bridge_description_new, *bridge_description_old;
  4871. tor_asprintf(&bridge_description_new, "%s:%u:%s:%s",
  4872. fmt_addr(addr), port,
  4873. digest ? hex_str(digest, DIGEST_LEN) : "",
  4874. transport_name ? transport_name : "");
  4875. tor_asprintf(&bridge_description_old, "%s:%u:%s:%s",
  4876. fmt_addr(&bridge->addr), bridge->port,
  4877. tor_digest_is_zero(bridge->identity) ?
  4878. "" : hex_str(bridge->identity,DIGEST_LEN),
  4879. bridge->transport_name ? bridge->transport_name : "");
  4880. log_warn(LD_GENERAL,"Tried to add bridge '%s', but we found a conflict"
  4881. " with the already registered bridge '%s'. We will discard"
  4882. " the old bridge and keep '%s'. If this is not what you"
  4883. " wanted, please change your configuration file accordingly.",
  4884. bridge_description_new, bridge_description_old,
  4885. bridge_description_new);
  4886. tor_free(bridge_description_new);
  4887. tor_free(bridge_description_old);
  4888. }
  4889. }
  4890. } SMARTLIST_FOREACH_END(bridge);
  4891. }
  4892. /** Remember a new bridge at <b>addr</b>:<b>port</b>. If <b>digest</b>
  4893. * is set, it tells us the identity key too. If we already had the
  4894. * bridge in our list, unmark it, and don't actually add anything new.
  4895. * If <b>transport_name</b> is non-NULL - the bridge is associated with a
  4896. * pluggable transport - we assign the transport to the bridge. */
  4897. void
  4898. bridge_add_from_config(const tor_addr_t *addr, uint16_t port,
  4899. const char *digest, const char *transport_name)
  4900. {
  4901. bridge_info_t *b;
  4902. bridge_resolve_conflicts(addr, port, digest, transport_name);
  4903. b = tor_malloc_zero(sizeof(bridge_info_t));
  4904. tor_addr_copy(&b->addr, addr);
  4905. b->port = port;
  4906. if (digest)
  4907. memcpy(b->identity, digest, DIGEST_LEN);
  4908. if (transport_name)
  4909. b->transport_name = tor_strdup(transport_name);
  4910. b->fetch_status.schedule = DL_SCHED_BRIDGE;
  4911. if (!bridge_list)
  4912. bridge_list = smartlist_new();
  4913. smartlist_add(bridge_list, b);
  4914. }
  4915. /** Return true iff <b>routerset</b> contains the bridge <b>bridge</b>. */
  4916. static int
  4917. routerset_contains_bridge(const routerset_t *routerset,
  4918. const bridge_info_t *bridge)
  4919. {
  4920. int result;
  4921. extend_info_t *extinfo;
  4922. tor_assert(bridge);
  4923. if (!routerset)
  4924. return 0;
  4925. extinfo = extend_info_new(
  4926. NULL, bridge->identity, NULL, &bridge->addr, bridge->port);
  4927. result = routerset_contains_extendinfo(routerset, extinfo);
  4928. extend_info_free(extinfo);
  4929. return result;
  4930. }
  4931. /** If <b>digest</b> is one of our known bridges, return it. */
  4932. static bridge_info_t *
  4933. find_bridge_by_digest(const char *digest)
  4934. {
  4935. SMARTLIST_FOREACH(bridge_list, bridge_info_t *, bridge,
  4936. {
  4937. if (tor_memeq(bridge->identity, digest, DIGEST_LEN))
  4938. return bridge;
  4939. });
  4940. return NULL;
  4941. }
  4942. /* DOCDOC find_transport_name_by_bridge_addrport */
  4943. const char *
  4944. find_transport_name_by_bridge_addrport(const tor_addr_t *addr, uint16_t port)
  4945. {
  4946. if (!bridge_list)
  4947. return NULL;
  4948. SMARTLIST_FOREACH_BEGIN(bridge_list, const bridge_info_t *, bridge) {
  4949. if (tor_addr_eq(&bridge->addr, addr) &&
  4950. (bridge->port == port))
  4951. return bridge->transport_name;
  4952. } SMARTLIST_FOREACH_END(bridge);
  4953. return NULL;
  4954. }
  4955. /** If <b>addr</b> and <b>port</b> match the address and port of a
  4956. * bridge of ours that uses pluggable transports, place its transport
  4957. * in <b>transport</b>.
  4958. *
  4959. * Return 0 on success (found a transport, or found a bridge with no
  4960. * transport, or found no bridge); return -1 if we should be using a
  4961. * transport, but the transport could not be found.
  4962. */
  4963. int
  4964. find_transport_by_bridge_addrport(const tor_addr_t *addr, uint16_t port,
  4965. const transport_t **transport)
  4966. {
  4967. *transport = NULL;
  4968. if (!bridge_list)
  4969. return 0;
  4970. SMARTLIST_FOREACH_BEGIN(bridge_list, const bridge_info_t *, bridge) {
  4971. if (tor_addr_eq(&bridge->addr, addr) &&
  4972. (bridge->port == port)) { /* bridge matched */
  4973. if (bridge->transport_name) { /* it also uses pluggable transports */
  4974. *transport = transport_get_by_name(bridge->transport_name);
  4975. if (*transport == NULL) { /* it uses pluggable transports, but
  4976. the transport could not be found! */
  4977. return -1;
  4978. }
  4979. return 0;
  4980. } else { /* bridge matched, but it doesn't use transports. */
  4981. break;
  4982. }
  4983. }
  4984. } SMARTLIST_FOREACH_END(bridge);
  4985. *transport = NULL;
  4986. return 0;
  4987. }
  4988. /** We need to ask <b>bridge</b> for its server descriptor. */
  4989. static void
  4990. launch_direct_bridge_descriptor_fetch(bridge_info_t *bridge)
  4991. {
  4992. char *address;
  4993. const or_options_t *options = get_options();
  4994. if (connection_get_by_type_addr_port_purpose(
  4995. CONN_TYPE_DIR, &bridge->addr, bridge->port,
  4996. DIR_PURPOSE_FETCH_SERVERDESC))
  4997. return; /* it's already on the way */
  4998. if (routerset_contains_bridge(options->ExcludeNodes, bridge)) {
  4999. download_status_mark_impossible(&bridge->fetch_status);
  5000. log_warn(LD_APP, "Not using bridge at %s: it is in ExcludeNodes.",
  5001. safe_str_client(fmt_addr(&bridge->addr)));
  5002. return;
  5003. }
  5004. address = tor_dup_addr(&bridge->addr);
  5005. directory_initiate_command(address, &bridge->addr,
  5006. bridge->port, 0/*no dirport*/,
  5007. bridge->identity,
  5008. DIR_PURPOSE_FETCH_SERVERDESC,
  5009. ROUTER_PURPOSE_BRIDGE,
  5010. DIRIND_ONEHOP, "authority.z", NULL, 0, 0);
  5011. tor_free(address);
  5012. }
  5013. /** Fetching the bridge descriptor from the bridge authority returned a
  5014. * "not found". Fall back to trying a direct fetch. */
  5015. void
  5016. retry_bridge_descriptor_fetch_directly(const char *digest)
  5017. {
  5018. bridge_info_t *bridge = find_bridge_by_digest(digest);
  5019. if (!bridge)
  5020. return; /* not found? oh well. */
  5021. launch_direct_bridge_descriptor_fetch(bridge);
  5022. }
  5023. /** For each bridge in our list for which we don't currently have a
  5024. * descriptor, fetch a new copy of its descriptor -- either directly
  5025. * from the bridge or via a bridge authority. */
  5026. void
  5027. fetch_bridge_descriptors(const or_options_t *options, time_t now)
  5028. {
  5029. int num_bridge_auths = get_n_authorities(BRIDGE_DIRINFO);
  5030. int ask_bridge_directly;
  5031. int can_use_bridge_authority;
  5032. if (!bridge_list)
  5033. return;
  5034. /* If we still have unconfigured managed proxies, don't go and
  5035. connect to a bridge. */
  5036. if (pt_proxies_configuration_pending())
  5037. return;
  5038. SMARTLIST_FOREACH_BEGIN(bridge_list, bridge_info_t *, bridge)
  5039. {
  5040. if (!download_status_is_ready(&bridge->fetch_status, now,
  5041. IMPOSSIBLE_TO_DOWNLOAD))
  5042. continue; /* don't bother, no need to retry yet */
  5043. if (routerset_contains_bridge(options->ExcludeNodes, bridge)) {
  5044. download_status_mark_impossible(&bridge->fetch_status);
  5045. log_warn(LD_APP, "Not using bridge at %s: it is in ExcludeNodes.",
  5046. safe_str_client(fmt_addr(&bridge->addr)));
  5047. continue;
  5048. }
  5049. /* schedule another fetch as if this one will fail, in case it does */
  5050. download_status_failed(&bridge->fetch_status, 0);
  5051. can_use_bridge_authority = !tor_digest_is_zero(bridge->identity) &&
  5052. num_bridge_auths;
  5053. ask_bridge_directly = !can_use_bridge_authority ||
  5054. !options->UpdateBridgesFromAuthority;
  5055. log_debug(LD_DIR, "ask_bridge_directly=%d (%d, %d, %d)",
  5056. ask_bridge_directly, tor_digest_is_zero(bridge->identity),
  5057. !options->UpdateBridgesFromAuthority, !num_bridge_auths);
  5058. if (ask_bridge_directly &&
  5059. !fascist_firewall_allows_address_or(&bridge->addr, bridge->port)) {
  5060. log_notice(LD_DIR, "Bridge at '%s:%d' isn't reachable by our "
  5061. "firewall policy. %s.", fmt_addr(&bridge->addr),
  5062. bridge->port,
  5063. can_use_bridge_authority ?
  5064. "Asking bridge authority instead" : "Skipping");
  5065. if (can_use_bridge_authority)
  5066. ask_bridge_directly = 0;
  5067. else
  5068. continue;
  5069. }
  5070. if (ask_bridge_directly) {
  5071. /* we need to ask the bridge itself for its descriptor. */
  5072. launch_direct_bridge_descriptor_fetch(bridge);
  5073. } else {
  5074. /* We have a digest and we want to ask an authority. We could
  5075. * combine all the requests into one, but that may give more
  5076. * hints to the bridge authority than we want to give. */
  5077. char resource[10 + HEX_DIGEST_LEN];
  5078. memcpy(resource, "fp/", 3);
  5079. base16_encode(resource+3, HEX_DIGEST_LEN+1,
  5080. bridge->identity, DIGEST_LEN);
  5081. memcpy(resource+3+HEX_DIGEST_LEN, ".z", 3);
  5082. log_info(LD_DIR, "Fetching bridge info '%s' from bridge authority.",
  5083. resource);
  5084. directory_get_from_dirserver(DIR_PURPOSE_FETCH_SERVERDESC,
  5085. ROUTER_PURPOSE_BRIDGE, resource, 0);
  5086. }
  5087. }
  5088. SMARTLIST_FOREACH_END(bridge);
  5089. }
  5090. /** If our <b>bridge</b> is configured to be a different address than
  5091. * the bridge gives in <b>node</b>, rewrite the routerinfo
  5092. * we received to use the address we meant to use. Now we handle
  5093. * multihomed bridges better.
  5094. */
  5095. static void
  5096. rewrite_node_address_for_bridge(const bridge_info_t *bridge, node_t *node)
  5097. {
  5098. /* XXXX move this function. */
  5099. /* XXXX overridden addresses should really live in the node_t, so that the
  5100. * routerinfo_t and the microdesc_t can be immutable. But we can only
  5101. * do that safely if we know that no function that connects to an OR
  5102. * does so through an address from any source other than node_get_addr().
  5103. */
  5104. tor_addr_t addr;
  5105. if (node->ri) {
  5106. routerinfo_t *ri = node->ri;
  5107. tor_addr_from_ipv4h(&addr, ri->addr);
  5108. if ((!tor_addr_compare(&bridge->addr, &addr, CMP_EXACT) &&
  5109. bridge->port == ri->or_port) ||
  5110. (!tor_addr_compare(&bridge->addr, &ri->ipv6_addr, CMP_EXACT) &&
  5111. bridge->port == ri->ipv6_orport)) {
  5112. /* they match, so no need to do anything */
  5113. } else {
  5114. if (tor_addr_family(&bridge->addr) == AF_INET) {
  5115. ri->addr = tor_addr_to_ipv4h(&bridge->addr);
  5116. tor_free(ri->address);
  5117. ri->address = tor_dup_ip(ri->addr);
  5118. ri->or_port = bridge->port;
  5119. log_info(LD_DIR,
  5120. "Adjusted bridge routerinfo for '%s' to match configured "
  5121. "address %s:%d.",
  5122. ri->nickname, ri->address, ri->or_port);
  5123. } else if (tor_addr_family(&bridge->addr) == AF_INET6) {
  5124. tor_addr_copy(&ri->ipv6_addr, &bridge->addr);
  5125. ri->ipv6_orport = bridge->port;
  5126. log_info(LD_DIR,
  5127. "Adjusted bridge routerinfo for '%s' to match configured "
  5128. "address %s:%d.",
  5129. ri->nickname, fmt_addr(&ri->ipv6_addr), ri->ipv6_orport);
  5130. } else {
  5131. log_err(LD_BUG, "Address family not supported: %d.",
  5132. tor_addr_family(&bridge->addr));
  5133. return;
  5134. }
  5135. }
  5136. /* Mark which address to use based on which bridge_t we got. */
  5137. node->ipv6_preferred = (tor_addr_family(&bridge->addr) == AF_INET6 &&
  5138. !tor_addr_is_null(&node->ri->ipv6_addr));
  5139. /* XXXipv6 we lack support for falling back to another address for
  5140. the same relay, warn the user */
  5141. if (!tor_addr_is_null(&ri->ipv6_addr)) {
  5142. tor_addr_port_t ap;
  5143. node_get_pref_orport(node, &ap);
  5144. log_notice(LD_CONFIG,
  5145. "Bridge '%s' has both an IPv4 and an IPv6 address. "
  5146. "Will prefer using its %s address (%s:%d).",
  5147. ri->nickname,
  5148. tor_addr_family(&ap.addr) == AF_INET6 ? "IPv6" : "IPv4",
  5149. fmt_addr(&ap.addr), ap.port);
  5150. }
  5151. }
  5152. if (node->rs) {
  5153. routerstatus_t *rs = node->rs;
  5154. tor_addr_from_ipv4h(&addr, rs->addr);
  5155. if (!tor_addr_compare(&bridge->addr, &addr, CMP_EXACT) &&
  5156. bridge->port == rs->or_port) {
  5157. /* they match, so no need to do anything */
  5158. } else {
  5159. rs->addr = tor_addr_to_ipv4h(&bridge->addr);
  5160. rs->or_port = bridge->port;
  5161. log_info(LD_DIR,
  5162. "Adjusted bridge routerstatus for '%s' to match "
  5163. "configured address %s:%d.",
  5164. rs->nickname, fmt_addr(&bridge->addr), rs->or_port);
  5165. }
  5166. }
  5167. }
  5168. /** We just learned a descriptor for a bridge. See if that
  5169. * digest is in our entry guard list, and add it if not. */
  5170. void
  5171. learned_bridge_descriptor(routerinfo_t *ri, int from_cache)
  5172. {
  5173. tor_assert(ri);
  5174. tor_assert(ri->purpose == ROUTER_PURPOSE_BRIDGE);
  5175. if (get_options()->UseBridges) {
  5176. int first = !any_bridge_descriptors_known();
  5177. bridge_info_t *bridge = get_configured_bridge_by_routerinfo(ri);
  5178. time_t now = time(NULL);
  5179. router_set_status(ri->cache_info.identity_digest, 1);
  5180. if (bridge) { /* if we actually want to use this one */
  5181. node_t *node;
  5182. /* it's here; schedule its re-fetch for a long time from now. */
  5183. if (!from_cache)
  5184. download_status_reset(&bridge->fetch_status);
  5185. node = node_get_mutable_by_id(ri->cache_info.identity_digest);
  5186. tor_assert(node);
  5187. rewrite_node_address_for_bridge(bridge, node);
  5188. add_an_entry_guard(node, 1, 1);
  5189. log_notice(LD_DIR, "new bridge descriptor '%s' (%s): %s", ri->nickname,
  5190. from_cache ? "cached" : "fresh", router_describe(ri));
  5191. /* set entry->made_contact so if it goes down we don't drop it from
  5192. * our entry node list */
  5193. entry_guard_register_connect_status(ri->cache_info.identity_digest,
  5194. 1, 0, now);
  5195. if (first)
  5196. routerlist_retry_directory_downloads(now);
  5197. }
  5198. }
  5199. }
  5200. /** Return 1 if any of our entry guards have descriptors that
  5201. * are marked with purpose 'bridge' and are running. Else return 0.
  5202. *
  5203. * We use this function to decide if we're ready to start building
  5204. * circuits through our bridges, or if we need to wait until the
  5205. * directory "server/authority" requests finish. */
  5206. int
  5207. any_bridge_descriptors_known(void)
  5208. {
  5209. tor_assert(get_options()->UseBridges);
  5210. return choose_random_entry(NULL)!=NULL ? 1 : 0;
  5211. }
  5212. /** Return 1 if there are any directory conns fetching bridge descriptors
  5213. * that aren't marked for close. We use this to guess if we should tell
  5214. * the controller that we have a problem. */
  5215. int
  5216. any_pending_bridge_descriptor_fetches(void)
  5217. {
  5218. smartlist_t *conns = get_connection_array();
  5219. SMARTLIST_FOREACH_BEGIN(conns, connection_t *, conn) {
  5220. if (conn->type == CONN_TYPE_DIR &&
  5221. conn->purpose == DIR_PURPOSE_FETCH_SERVERDESC &&
  5222. TO_DIR_CONN(conn)->router_purpose == ROUTER_PURPOSE_BRIDGE &&
  5223. !conn->marked_for_close &&
  5224. conn->linked &&
  5225. conn->linked_conn && !conn->linked_conn->marked_for_close) {
  5226. log_debug(LD_DIR, "found one: %s", conn->address);
  5227. return 1;
  5228. }
  5229. } SMARTLIST_FOREACH_END(conn);
  5230. return 0;
  5231. }
  5232. /** Return 1 if we have at least one descriptor for an entry guard
  5233. * (bridge or member of EntryNodes) and all descriptors we know are
  5234. * down. Else return 0. If <b>act</b> is 1, then mark the down guards
  5235. * up; else just observe and report. */
  5236. static int
  5237. entries_retry_helper(const or_options_t *options, int act)
  5238. {
  5239. const node_t *node;
  5240. int any_known = 0;
  5241. int any_running = 0;
  5242. int need_bridges = options->UseBridges != 0;
  5243. if (!entry_guards)
  5244. entry_guards = smartlist_new();
  5245. SMARTLIST_FOREACH_BEGIN(entry_guards, entry_guard_t *, e) {
  5246. node = node_get_by_id(e->identity);
  5247. if (node && node_has_descriptor(node) &&
  5248. node_is_bridge(node) == need_bridges) {
  5249. any_known = 1;
  5250. if (node->is_running)
  5251. any_running = 1; /* some entry is both known and running */
  5252. else if (act) {
  5253. /* Mark all current connections to this OR as unhealthy, since
  5254. * otherwise there could be one that started 30 seconds
  5255. * ago, and in 30 seconds it will time out, causing us to mark
  5256. * the node down and undermine the retry attempt. We mark even
  5257. * the established conns, since if the network just came back
  5258. * we'll want to attach circuits to fresh conns. */
  5259. connection_or_set_bad_connections(node->identity, 1);
  5260. /* mark this entry node for retry */
  5261. router_set_status(node->identity, 1);
  5262. e->can_retry = 1;
  5263. e->bad_since = 0;
  5264. }
  5265. }
  5266. } SMARTLIST_FOREACH_END(e);
  5267. log_debug(LD_DIR, "%d: any_known %d, any_running %d",
  5268. act, any_known, any_running);
  5269. return any_known && !any_running;
  5270. }
  5271. /** Do we know any descriptors for our bridges / entrynodes, and are
  5272. * all the ones we have descriptors for down? */
  5273. int
  5274. entries_known_but_down(const or_options_t *options)
  5275. {
  5276. tor_assert(entry_list_is_constrained(options));
  5277. return entries_retry_helper(options, 0);
  5278. }
  5279. /** Mark all down known bridges / entrynodes up. */
  5280. void
  5281. entries_retry_all(const or_options_t *options)
  5282. {
  5283. tor_assert(entry_list_is_constrained(options));
  5284. entries_retry_helper(options, 1);
  5285. }
  5286. /** Return true if we've ever had a bridge running a Tor version that can't
  5287. * provide microdescriptors to us. In that case fall back to asking for
  5288. * full descriptors. Eventually all bridges will support microdescriptors
  5289. * and we can take this check out; see bug 4013. */
  5290. int
  5291. any_bridges_dont_support_microdescriptors(void)
  5292. {
  5293. const node_t *node;
  5294. static int ever_answered_yes = 0;
  5295. if (!get_options()->UseBridges || !entry_guards)
  5296. return 0;
  5297. if (ever_answered_yes)
  5298. return 1; /* if we ever answer 'yes', always answer 'yes' */
  5299. SMARTLIST_FOREACH_BEGIN(entry_guards, entry_guard_t *, e) {
  5300. node = node_get_by_id(e->identity);
  5301. if (node && node->ri &&
  5302. node_is_bridge(node) && node_is_a_configured_bridge(node) &&
  5303. !tor_version_supports_microdescriptors(node->ri->platform)) {
  5304. /* This is one of our current bridges, and we know enough about
  5305. * it to know that it won't be able to answer our microdescriptor
  5306. * questions. */
  5307. ever_answered_yes = 1;
  5308. return 1;
  5309. }
  5310. } SMARTLIST_FOREACH_END(e);
  5311. return 0;
  5312. }
  5313. /** Release all storage held by the list of entry guards and related
  5314. * memory structs. */
  5315. void
  5316. entry_guards_free_all(void)
  5317. {
  5318. if (entry_guards) {
  5319. SMARTLIST_FOREACH(entry_guards, entry_guard_t *, e,
  5320. entry_guard_free(e));
  5321. smartlist_free(entry_guards);
  5322. entry_guards = NULL;
  5323. }
  5324. clear_bridge_list();
  5325. smartlist_free(bridge_list);
  5326. bridge_list = NULL;
  5327. }