circuitbuild.c 156 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844184518461847184818491850185118521853185418551856185718581859186018611862186318641865186618671868186918701871187218731874187518761877187818791880188118821883188418851886188718881889189018911892189318941895189618971898189919001901190219031904190519061907190819091910191119121913191419151916191719181919192019211922192319241925192619271928192919301931193219331934193519361937193819391940194119421943194419451946194719481949195019511952195319541955195619571958195919601961196219631964196519661967196819691970197119721973197419751976197719781979198019811982198319841985198619871988198919901991199219931994199519961997199819992000200120022003200420052006200720082009201020112012201320142015201620172018201920202021202220232024202520262027202820292030203120322033203420352036203720382039204020412042204320442045204620472048204920502051205220532054205520562057205820592060206120622063206420652066206720682069207020712072207320742075207620772078207920802081208220832084208520862087208820892090209120922093209420952096209720982099210021012102210321042105210621072108210921102111211221132114211521162117211821192120212121222123212421252126212721282129213021312132213321342135213621372138213921402141214221432144214521462147214821492150215121522153215421552156215721582159216021612162216321642165216621672168216921702171217221732174217521762177217821792180218121822183218421852186218721882189219021912192219321942195219621972198219922002201220222032204220522062207220822092210221122122213221422152216221722182219222022212222222322242225222622272228222922302231223222332234223522362237223822392240224122422243224422452246224722482249225022512252225322542255225622572258225922602261226222632264226522662267226822692270227122722273227422752276227722782279228022812282228322842285228622872288228922902291229222932294229522962297229822992300230123022303230423052306230723082309231023112312231323142315231623172318231923202321232223232324232523262327232823292330233123322333233423352336233723382339234023412342234323442345234623472348234923502351235223532354235523562357235823592360236123622363236423652366236723682369237023712372237323742375237623772378237923802381238223832384238523862387238823892390239123922393239423952396239723982399240024012402240324042405240624072408240924102411241224132414241524162417241824192420242124222423242424252426242724282429243024312432243324342435243624372438243924402441244224432444244524462447244824492450245124522453245424552456245724582459246024612462246324642465246624672468246924702471247224732474247524762477247824792480248124822483248424852486248724882489249024912492249324942495249624972498249925002501250225032504250525062507250825092510251125122513251425152516251725182519252025212522252325242525252625272528252925302531253225332534253525362537253825392540254125422543254425452546254725482549255025512552255325542555255625572558255925602561256225632564256525662567256825692570257125722573257425752576257725782579258025812582258325842585258625872588258925902591259225932594259525962597259825992600260126022603260426052606260726082609261026112612261326142615261626172618261926202621262226232624262526262627262826292630263126322633263426352636263726382639264026412642264326442645264626472648264926502651265226532654265526562657265826592660266126622663266426652666266726682669267026712672267326742675267626772678267926802681268226832684268526862687268826892690269126922693269426952696269726982699270027012702270327042705270627072708270927102711271227132714271527162717271827192720272127222723272427252726272727282729273027312732273327342735273627372738273927402741274227432744274527462747274827492750275127522753275427552756275727582759276027612762276327642765276627672768276927702771277227732774277527762777277827792780278127822783278427852786278727882789279027912792279327942795279627972798279928002801280228032804280528062807280828092810281128122813281428152816281728182819282028212822282328242825282628272828282928302831283228332834283528362837283828392840284128422843284428452846284728482849285028512852285328542855285628572858285928602861286228632864286528662867286828692870287128722873287428752876287728782879288028812882288328842885288628872888288928902891289228932894289528962897289828992900290129022903290429052906290729082909291029112912291329142915291629172918291929202921292229232924292529262927292829292930293129322933293429352936293729382939294029412942294329442945294629472948294929502951295229532954295529562957295829592960296129622963296429652966296729682969297029712972297329742975297629772978297929802981298229832984298529862987298829892990299129922993299429952996299729982999300030013002300330043005300630073008300930103011301230133014301530163017301830193020302130223023302430253026302730283029303030313032303330343035303630373038303930403041304230433044304530463047304830493050305130523053305430553056305730583059306030613062306330643065306630673068306930703071307230733074307530763077307830793080308130823083308430853086308730883089309030913092309330943095309630973098309931003101310231033104310531063107310831093110311131123113311431153116311731183119312031213122312331243125312631273128312931303131313231333134313531363137313831393140314131423143314431453146314731483149315031513152315331543155315631573158315931603161316231633164316531663167316831693170317131723173317431753176317731783179318031813182318331843185318631873188318931903191319231933194319531963197319831993200320132023203320432053206320732083209321032113212321332143215321632173218321932203221322232233224322532263227322832293230323132323233323432353236323732383239324032413242324332443245324632473248324932503251325232533254325532563257325832593260326132623263326432653266326732683269327032713272327332743275327632773278327932803281328232833284328532863287328832893290329132923293329432953296329732983299330033013302330333043305330633073308330933103311331233133314331533163317331833193320332133223323332433253326332733283329333033313332333333343335333633373338333933403341334233433344334533463347334833493350335133523353335433553356335733583359336033613362336333643365336633673368336933703371337233733374337533763377337833793380338133823383338433853386338733883389339033913392339333943395339633973398339934003401340234033404340534063407340834093410341134123413341434153416341734183419342034213422342334243425342634273428342934303431343234333434343534363437343834393440344134423443344434453446344734483449345034513452345334543455345634573458345934603461346234633464346534663467346834693470347134723473347434753476347734783479348034813482348334843485348634873488348934903491349234933494349534963497349834993500350135023503350435053506350735083509351035113512351335143515351635173518351935203521352235233524352535263527352835293530353135323533353435353536353735383539354035413542354335443545354635473548354935503551355235533554355535563557355835593560356135623563356435653566356735683569357035713572357335743575357635773578357935803581358235833584358535863587358835893590359135923593359435953596359735983599360036013602360336043605360636073608360936103611361236133614361536163617361836193620362136223623362436253626362736283629363036313632363336343635363636373638363936403641364236433644364536463647364836493650365136523653365436553656365736583659366036613662366336643665366636673668366936703671367236733674367536763677367836793680368136823683368436853686368736883689369036913692369336943695369636973698369937003701370237033704370537063707370837093710371137123713371437153716371737183719372037213722372337243725372637273728372937303731373237333734373537363737373837393740374137423743374437453746374737483749375037513752375337543755375637573758375937603761376237633764376537663767376837693770377137723773377437753776377737783779378037813782378337843785378637873788378937903791379237933794379537963797379837993800380138023803380438053806380738083809381038113812381338143815381638173818381938203821382238233824382538263827382838293830383138323833383438353836383738383839384038413842384338443845384638473848384938503851385238533854385538563857385838593860386138623863386438653866386738683869387038713872387338743875387638773878387938803881388238833884388538863887388838893890389138923893389438953896389738983899390039013902390339043905390639073908390939103911391239133914391539163917391839193920392139223923392439253926392739283929393039313932393339343935393639373938393939403941394239433944394539463947394839493950395139523953395439553956395739583959396039613962396339643965396639673968396939703971397239733974397539763977397839793980398139823983398439853986398739883989399039913992399339943995399639973998399940004001400240034004400540064007400840094010401140124013401440154016401740184019402040214022402340244025402640274028402940304031403240334034403540364037403840394040404140424043404440454046404740484049405040514052405340544055405640574058405940604061406240634064406540664067406840694070407140724073407440754076407740784079408040814082408340844085408640874088408940904091409240934094409540964097409840994100410141024103410441054106410741084109411041114112411341144115411641174118411941204121412241234124412541264127412841294130413141324133413441354136413741384139414041414142414341444145414641474148414941504151415241534154415541564157415841594160416141624163416441654166416741684169417041714172417341744175417641774178417941804181418241834184418541864187418841894190419141924193419441954196419741984199420042014202420342044205420642074208420942104211421242134214421542164217421842194220422142224223422442254226422742284229423042314232423342344235423642374238423942404241424242434244424542464247424842494250425142524253425442554256425742584259426042614262426342644265426642674268426942704271427242734274427542764277427842794280428142824283428442854286428742884289429042914292429342944295429642974298429943004301430243034304430543064307430843094310431143124313431443154316431743184319432043214322432343244325432643274328432943304331433243334334433543364337433843394340434143424343434443454346434743484349435043514352435343544355435643574358435943604361436243634364436543664367436843694370437143724373437443754376437743784379438043814382438343844385438643874388438943904391439243934394439543964397439843994400440144024403440444054406440744084409441044114412441344144415441644174418441944204421442244234424442544264427442844294430443144324433443444354436443744384439444044414442444344444445444644474448444944504451445244534454445544564457445844594460446144624463446444654466446744684469447044714472447344744475447644774478447944804481448244834484448544864487448844894490449144924493449444954496449744984499450045014502450345044505450645074508450945104511451245134514451545164517451845194520452145224523452445254526452745284529453045314532453345344535453645374538453945404541454245434544454545464547454845494550455145524553455445554556455745584559456045614562456345644565456645674568456945704571457245734574457545764577457845794580458145824583458445854586458745884589459045914592459345944595459645974598459946004601460246034604460546064607460846094610461146124613461446154616461746184619462046214622462346244625462646274628462946304631463246334634463546364637463846394640464146424643464446454646464746484649465046514652465346544655465646574658465946604661466246634664466546664667466846694670467146724673467446754676467746784679468046814682468346844685468646874688468946904691469246934694469546964697469846994700
  1. /* Copyright (c) 2001 Matej Pfajfar.
  2. * Copyright (c) 2001-2004, Roger Dingledine.
  3. * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
  4. * Copyright (c) 2007-2011, The Tor Project, Inc. */
  5. /* See LICENSE for licensing information */
  6. /**
  7. * \file circuitbuild.c
  8. * \brief The actual details of building circuits.
  9. **/
  10. #define CIRCUIT_PRIVATE
  11. #include "or.h"
  12. #include "circuitbuild.h"
  13. #include "circuitlist.h"
  14. #include "circuituse.h"
  15. #include "config.h"
  16. #include "connection.h"
  17. #include "connection_edge.h"
  18. #include "connection_or.h"
  19. #include "control.h"
  20. #include "directory.h"
  21. #include "main.h"
  22. #include "networkstatus.h"
  23. #include "onion.h"
  24. #include "policies.h"
  25. #include "relay.h"
  26. #include "rephist.h"
  27. #include "router.h"
  28. #include "routerlist.h"
  29. #include "routerparse.h"
  30. #include "crypto.h"
  31. #undef log
  32. #include <math.h>
  33. #ifndef MIN
  34. #define MIN(a,b) ((a)<(b)?(a):(b))
  35. #endif
  36. #define CBT_BIN_TO_MS(bin) ((bin)*CBT_BIN_WIDTH + (CBT_BIN_WIDTH/2))
  37. /********* START VARIABLES **********/
  38. /** Global list of circuit build times */
  39. // FIXME: Add this as a member for entry_guard_t instead of global?
  40. // Then we could do per-guard statistics, as guards are likely to
  41. // vary in their own latency. The downside of this is that guards
  42. // can change frequently, so we'd be building a lot more circuits
  43. // most likely.
  44. circuit_build_times_t circ_times;
  45. /** A global list of all circuits at this hop. */
  46. extern circuit_t *global_circuitlist;
  47. /** An entry_guard_t represents our information about a chosen long-term
  48. * first hop, known as a "helper" node in the literature. We can't just
  49. * use a routerinfo_t, since we want to remember these even when we
  50. * don't have a directory. */
  51. typedef struct {
  52. char nickname[MAX_NICKNAME_LEN+1];
  53. char identity[DIGEST_LEN];
  54. time_t chosen_on_date; /**< Approximately when was this guard added?
  55. * "0" if we don't know. */
  56. char *chosen_by_version; /**< What tor version added this guard? NULL
  57. * if we don't know. */
  58. unsigned int made_contact : 1; /**< 0 if we have never connected to this
  59. * router, 1 if we have. */
  60. unsigned int can_retry : 1; /**< Should we retry connecting to this entry,
  61. * in spite of having it marked as unreachable?*/
  62. time_t bad_since; /**< 0 if this guard is currently usable, or the time at
  63. * which it was observed to become (according to the
  64. * directory or the user configuration) unusable. */
  65. time_t unreachable_since; /**< 0 if we can connect to this guard, or the
  66. * time at which we first noticed we couldn't
  67. * connect to it. */
  68. time_t last_attempted; /**< 0 if we can connect to this guard, or the time
  69. * at which we last failed to connect to it. */
  70. } entry_guard_t;
  71. /** A list of our chosen entry guards. */
  72. static smartlist_t *entry_guards = NULL;
  73. /** A value of 1 means that the entry_guards list has changed
  74. * and those changes need to be flushed to disk. */
  75. static int entry_guards_dirty = 0;
  76. /** If set, we're running the unit tests: we should avoid clobbering
  77. * our state file or accessing get_options() or get_or_state() */
  78. static int unit_tests = 0;
  79. /********* END VARIABLES ************/
  80. static int circuit_deliver_create_cell(circuit_t *circ,
  81. uint8_t cell_type, const char *payload);
  82. static int onion_pick_cpath_exit(origin_circuit_t *circ, extend_info_t *exit);
  83. static crypt_path_t *onion_next_hop_in_cpath(crypt_path_t *cpath);
  84. static int onion_extend_cpath(origin_circuit_t *circ);
  85. static int count_acceptable_routers(smartlist_t *routers);
  86. static int onion_append_hop(crypt_path_t **head_ptr, extend_info_t *choice);
  87. static void entry_guards_changed(void);
  88. static int
  89. circuit_build_times_disabled(void)
  90. {
  91. if (unit_tests) {
  92. return 0;
  93. } else {
  94. int consensus_disabled = networkstatus_get_param(NULL, "cbtdisabled",
  95. 0);
  96. int config_disabled = !get_options()->LearnCircuitBuildTimeout;
  97. int dirauth_disabled = get_options()->AuthoritativeDir;
  98. int state_disabled = (get_or_state()->LastWritten == -1);
  99. if (consensus_disabled || config_disabled || dirauth_disabled ||
  100. state_disabled) {
  101. log_info(LD_CIRC,
  102. "CircuitBuildTime learning is disabled. "
  103. "Consensus=%d, Config=%d, AuthDir=%d, StateFile=%d",
  104. consensus_disabled, config_disabled, dirauth_disabled,
  105. state_disabled);
  106. return 1;
  107. } else {
  108. return 0;
  109. }
  110. }
  111. }
  112. static int32_t
  113. circuit_build_times_max_timeouts(void)
  114. {
  115. int32_t num = networkstatus_get_param(NULL, "cbtmaxtimeouts",
  116. CBT_DEFAULT_MAX_RECENT_TIMEOUT_COUNT);
  117. return num;
  118. }
  119. static int32_t
  120. circuit_build_times_default_num_xm_modes(void)
  121. {
  122. int32_t num = networkstatus_get_param(NULL, "cbtnummodes",
  123. CBT_DEFAULT_NUM_XM_MODES);
  124. return num;
  125. }
  126. static int32_t
  127. circuit_build_times_min_circs_to_observe(void)
  128. {
  129. int32_t num = networkstatus_get_param(NULL, "cbtmincircs",
  130. CBT_DEFAULT_MIN_CIRCUITS_TO_OBSERVE);
  131. return num;
  132. }
  133. /** Return true iff <b>cbt</b> has recorded enough build times that we
  134. * want to start acting on the timeout it implies. */
  135. int
  136. circuit_build_times_enough_to_compute(circuit_build_times_t *cbt)
  137. {
  138. return cbt->total_build_times >= circuit_build_times_min_circs_to_observe();
  139. }
  140. double
  141. circuit_build_times_quantile_cutoff(void)
  142. {
  143. int32_t num = networkstatus_get_param(NULL, "cbtquantile",
  144. CBT_DEFAULT_QUANTILE_CUTOFF);
  145. return num/100.0;
  146. }
  147. static double
  148. circuit_build_times_close_quantile(void)
  149. {
  150. int32_t num = networkstatus_get_param(NULL, "cbtclosequantile",
  151. CBT_DEFAULT_CLOSE_QUANTILE);
  152. return num/100.0;
  153. }
  154. static int32_t
  155. circuit_build_times_test_frequency(void)
  156. {
  157. int32_t num = networkstatus_get_param(NULL, "cbttestfreq",
  158. CBT_DEFAULT_TEST_FREQUENCY);
  159. return num;
  160. }
  161. static int32_t
  162. circuit_build_times_min_timeout(void)
  163. {
  164. int32_t num = networkstatus_get_param(NULL, "cbtmintimeout",
  165. CBT_DEFAULT_TIMEOUT_MIN_VALUE);
  166. return num;
  167. }
  168. int32_t
  169. circuit_build_times_initial_timeout(void)
  170. {
  171. int32_t num = networkstatus_get_param(NULL, "cbtinitialtimeout",
  172. CBT_DEFAULT_TIMEOUT_INITIAL_VALUE);
  173. return num;
  174. }
  175. static int32_t
  176. circuit_build_times_recent_circuit_count(void)
  177. {
  178. int32_t num = networkstatus_get_param(NULL, "cbtrecentcount",
  179. CBT_DEFAULT_RECENT_CIRCUITS);
  180. return num;
  181. }
  182. /**
  183. * This function is called when we get a consensus update.
  184. *
  185. * It checks to see if we have changed any consensus parameters
  186. * that require reallocation or discard of previous stats.
  187. */
  188. void
  189. circuit_build_times_new_consensus_params(circuit_build_times_t *cbt,
  190. networkstatus_t *ns)
  191. {
  192. int32_t num = networkstatus_get_param(ns, "cbtrecentcount",
  193. CBT_DEFAULT_RECENT_CIRCUITS);
  194. if (num > 0 && num != cbt->liveness.num_recent_circs) {
  195. int8_t *recent_circs;
  196. log_notice(LD_CIRC, "Changing recent timeout size from %d to %d",
  197. cbt->liveness.num_recent_circs, num);
  198. tor_assert(cbt->liveness.timeouts_after_firsthop);
  199. /*
  200. * Technically this is a circular array that we are reallocating
  201. * and memcopying. However, since it only consists of either 1s
  202. * or 0s, and is only used in a statistical test to determine when
  203. * we should discard our history after a sufficient number of 1's
  204. * have been reached, it is fine if order is not preserved or
  205. * elements are lost.
  206. *
  207. * cbtrecentcount should only be changing in cases of severe network
  208. * distress anyway, so memory correctness here is paramount over
  209. * doing acrobatics to preserve the array.
  210. */
  211. recent_circs = tor_malloc_zero(sizeof(int8_t)*num);
  212. memcpy(recent_circs, cbt->liveness.timeouts_after_firsthop,
  213. sizeof(int8_t)*MIN(num, cbt->liveness.num_recent_circs));
  214. // Adjust the index if it needs it.
  215. if (num < cbt->liveness.num_recent_circs) {
  216. cbt->liveness.after_firsthop_idx = MIN(num-1,
  217. cbt->liveness.after_firsthop_idx);
  218. }
  219. tor_free(cbt->liveness.timeouts_after_firsthop);
  220. cbt->liveness.timeouts_after_firsthop = recent_circs;
  221. cbt->liveness.num_recent_circs = num;
  222. }
  223. }
  224. /** Make a note that we're running unit tests (rather than running Tor
  225. * itself), so we avoid clobbering our state file. */
  226. void
  227. circuitbuild_running_unit_tests(void)
  228. {
  229. unit_tests = 1;
  230. }
  231. /**
  232. * Return the initial default or configured timeout in milliseconds
  233. */
  234. static double
  235. circuit_build_times_get_initial_timeout(void)
  236. {
  237. double timeout;
  238. if (!unit_tests && get_options()->CircuitBuildTimeout) {
  239. timeout = get_options()->CircuitBuildTimeout*1000;
  240. if (timeout < circuit_build_times_min_timeout()) {
  241. log_warn(LD_CIRC, "Config CircuitBuildTimeout too low. Setting to %ds",
  242. circuit_build_times_min_timeout()/1000);
  243. timeout = circuit_build_times_min_timeout();
  244. }
  245. } else {
  246. timeout = circuit_build_times_initial_timeout();
  247. }
  248. return timeout;
  249. }
  250. /**
  251. * Reset the build time state.
  252. *
  253. * Leave estimated parameters, timeout and network liveness intact
  254. * for future use.
  255. */
  256. void
  257. circuit_build_times_reset(circuit_build_times_t *cbt)
  258. {
  259. memset(cbt->circuit_build_times, 0, sizeof(cbt->circuit_build_times));
  260. cbt->total_build_times = 0;
  261. cbt->build_times_idx = 0;
  262. cbt->have_computed_timeout = 0;
  263. }
  264. /**
  265. * Initialize the buildtimes structure for first use.
  266. *
  267. * Sets the initial timeout values based on either the config setting,
  268. * the consensus param, or the default (CBT_DEFAULT_TIMEOUT_INITIAL_VALUE).
  269. */
  270. void
  271. circuit_build_times_init(circuit_build_times_t *cbt)
  272. {
  273. memset(cbt, 0, sizeof(*cbt));
  274. cbt->liveness.num_recent_circs = circuit_build_times_recent_circuit_count();
  275. cbt->liveness.timeouts_after_firsthop = tor_malloc_zero(sizeof(int8_t)*
  276. cbt->liveness.num_recent_circs);
  277. cbt->close_ms = cbt->timeout_ms = circuit_build_times_get_initial_timeout();
  278. control_event_buildtimeout_set(cbt, BUILDTIMEOUT_SET_EVENT_RESET);
  279. }
  280. #if 0
  281. /**
  282. * Rewind our build time history by n positions.
  283. */
  284. static void
  285. circuit_build_times_rewind_history(circuit_build_times_t *cbt, int n)
  286. {
  287. int i = 0;
  288. cbt->build_times_idx -= n;
  289. cbt->build_times_idx %= CBT_NCIRCUITS_TO_OBSERVE;
  290. for (i = 0; i < n; i++) {
  291. cbt->circuit_build_times[(i+cbt->build_times_idx)
  292. %CBT_NCIRCUITS_TO_OBSERVE]=0;
  293. }
  294. if (cbt->total_build_times > n) {
  295. cbt->total_build_times -= n;
  296. } else {
  297. cbt->total_build_times = 0;
  298. }
  299. log_info(LD_CIRC,
  300. "Rewound history by %d places. Current index: %d. "
  301. "Total: %d", n, cbt->build_times_idx, cbt->total_build_times);
  302. }
  303. #endif
  304. /**
  305. * Add a new build time value <b>time</b> to the set of build times. Time
  306. * units are milliseconds.
  307. *
  308. * circuit_build_times <b>cbt</a> is a circular array, so loop around when
  309. * array is full.
  310. */
  311. int
  312. circuit_build_times_add_time(circuit_build_times_t *cbt, build_time_t time)
  313. {
  314. if (time <= 0 || time > CBT_BUILD_TIME_MAX) {
  315. log_warn(LD_BUG, "Circuit build time is too large (%u)."
  316. "This is probably a bug.", time);
  317. tor_fragile_assert();
  318. return -1;
  319. }
  320. log_debug(LD_CIRC, "Adding circuit build time %u", time);
  321. cbt->circuit_build_times[cbt->build_times_idx] = time;
  322. cbt->build_times_idx = (cbt->build_times_idx + 1) % CBT_NCIRCUITS_TO_OBSERVE;
  323. if (cbt->total_build_times < CBT_NCIRCUITS_TO_OBSERVE)
  324. cbt->total_build_times++;
  325. if ((cbt->total_build_times % CBT_SAVE_STATE_EVERY) == 0) {
  326. /* Save state every n circuit builds */
  327. if (!unit_tests && !get_options()->AvoidDiskWrites)
  328. or_state_mark_dirty(get_or_state(), 0);
  329. }
  330. return 0;
  331. }
  332. /**
  333. * Return maximum circuit build time
  334. */
  335. static build_time_t
  336. circuit_build_times_max(circuit_build_times_t *cbt)
  337. {
  338. int i = 0;
  339. build_time_t max_build_time = 0;
  340. for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
  341. if (cbt->circuit_build_times[i] > max_build_time
  342. && cbt->circuit_build_times[i] != CBT_BUILD_ABANDONED)
  343. max_build_time = cbt->circuit_build_times[i];
  344. }
  345. return max_build_time;
  346. }
  347. #if 0
  348. /** Return minimum circuit build time */
  349. build_time_t
  350. circuit_build_times_min(circuit_build_times_t *cbt)
  351. {
  352. int i = 0;
  353. build_time_t min_build_time = CBT_BUILD_TIME_MAX;
  354. for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
  355. if (cbt->circuit_build_times[i] && /* 0 <-> uninitialized */
  356. cbt->circuit_build_times[i] < min_build_time)
  357. min_build_time = cbt->circuit_build_times[i];
  358. }
  359. if (min_build_time == CBT_BUILD_TIME_MAX) {
  360. log_warn(LD_CIRC, "No build times less than CBT_BUILD_TIME_MAX!");
  361. }
  362. return min_build_time;
  363. }
  364. #endif
  365. /**
  366. * Calculate and return a histogram for the set of build times.
  367. *
  368. * Returns an allocated array of histrogram bins representing
  369. * the frequency of index*CBT_BIN_WIDTH millisecond
  370. * build times. Also outputs the number of bins in nbins.
  371. *
  372. * The return value must be freed by the caller.
  373. */
  374. static uint32_t *
  375. circuit_build_times_create_histogram(circuit_build_times_t *cbt,
  376. build_time_t *nbins)
  377. {
  378. uint32_t *histogram;
  379. build_time_t max_build_time = circuit_build_times_max(cbt);
  380. int i, c;
  381. *nbins = 1 + (max_build_time / CBT_BIN_WIDTH);
  382. histogram = tor_malloc_zero(*nbins * sizeof(build_time_t));
  383. // calculate histogram
  384. for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
  385. if (cbt->circuit_build_times[i] == 0
  386. || cbt->circuit_build_times[i] == CBT_BUILD_ABANDONED)
  387. continue; /* 0 <-> uninitialized */
  388. c = (cbt->circuit_build_times[i] / CBT_BIN_WIDTH);
  389. histogram[c]++;
  390. }
  391. return histogram;
  392. }
  393. /**
  394. * Return the Pareto start-of-curve parameter Xm.
  395. *
  396. * Because we are not a true Pareto curve, we compute this as the
  397. * weighted average of the N=3 most frequent build time bins.
  398. */
  399. static build_time_t
  400. circuit_build_times_get_xm(circuit_build_times_t *cbt)
  401. {
  402. build_time_t i, nbins;
  403. build_time_t *nth_max_bin;
  404. int32_t bin_counts=0;
  405. build_time_t ret = 0;
  406. uint32_t *histogram = circuit_build_times_create_histogram(cbt, &nbins);
  407. int n=0;
  408. int num_modes = circuit_build_times_default_num_xm_modes();
  409. // Only use one mode if < 1000 buildtimes. Not enough data
  410. // for multiple.
  411. if (cbt->total_build_times < CBT_NCIRCUITS_TO_OBSERVE)
  412. num_modes = 1;
  413. nth_max_bin = (build_time_t*)tor_malloc_zero(num_modes*sizeof(build_time_t));
  414. for (i = 0; i < nbins; i++) {
  415. if (histogram[i] >= histogram[nth_max_bin[0]]) {
  416. nth_max_bin[0] = i;
  417. }
  418. for (n = 1; n < num_modes; n++) {
  419. if (histogram[i] >= histogram[nth_max_bin[n]] &&
  420. (!histogram[nth_max_bin[n-1]]
  421. || histogram[i] < histogram[nth_max_bin[n-1]])) {
  422. nth_max_bin[n] = i;
  423. }
  424. }
  425. }
  426. for (n = 0; n < num_modes; n++) {
  427. bin_counts += histogram[nth_max_bin[n]];
  428. ret += CBT_BIN_TO_MS(nth_max_bin[n])*histogram[nth_max_bin[n]];
  429. log_info(LD_CIRC, "Xm mode #%d: %u %u", n, CBT_BIN_TO_MS(nth_max_bin[n]),
  430. histogram[nth_max_bin[n]]);
  431. }
  432. ret /= bin_counts;
  433. tor_free(histogram);
  434. tor_free(nth_max_bin);
  435. return ret;
  436. }
  437. /**
  438. * Output a histogram of current circuit build times to
  439. * the or_state_t state structure.
  440. */
  441. void
  442. circuit_build_times_update_state(circuit_build_times_t *cbt,
  443. or_state_t *state)
  444. {
  445. uint32_t *histogram;
  446. build_time_t i = 0;
  447. build_time_t nbins = 0;
  448. config_line_t **next, *line;
  449. histogram = circuit_build_times_create_histogram(cbt, &nbins);
  450. // write to state
  451. config_free_lines(state->BuildtimeHistogram);
  452. next = &state->BuildtimeHistogram;
  453. *next = NULL;
  454. state->TotalBuildTimes = cbt->total_build_times;
  455. state->CircuitBuildAbandonedCount = 0;
  456. for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
  457. if (cbt->circuit_build_times[i] == CBT_BUILD_ABANDONED)
  458. state->CircuitBuildAbandonedCount++;
  459. }
  460. for (i = 0; i < nbins; i++) {
  461. // compress the histogram by skipping the blanks
  462. if (histogram[i] == 0) continue;
  463. *next = line = tor_malloc_zero(sizeof(config_line_t));
  464. line->key = tor_strdup("CircuitBuildTimeBin");
  465. line->value = tor_malloc(25);
  466. tor_snprintf(line->value, 25, "%d %d",
  467. CBT_BIN_TO_MS(i), histogram[i]);
  468. next = &(line->next);
  469. }
  470. if (!unit_tests) {
  471. if (!get_options()->AvoidDiskWrites)
  472. or_state_mark_dirty(get_or_state(), 0);
  473. }
  474. tor_free(histogram);
  475. }
  476. /**
  477. * Shuffle the build times array.
  478. *
  479. * Stolen from http://en.wikipedia.org/wiki/Fisher\u2013Yates_shuffle
  480. */
  481. static void
  482. circuit_build_times_shuffle_and_store_array(circuit_build_times_t *cbt,
  483. build_time_t *raw_times,
  484. int num_times)
  485. {
  486. int n = num_times;
  487. if (num_times > CBT_NCIRCUITS_TO_OBSERVE) {
  488. log_notice(LD_CIRC, "Decreasing circuit_build_times size from %d to %d",
  489. num_times, CBT_NCIRCUITS_TO_OBSERVE);
  490. }
  491. /* This code can only be run on a compact array */
  492. while (n-- > 1) {
  493. int k = crypto_rand_int(n + 1); /* 0 <= k <= n. */
  494. build_time_t tmp = raw_times[k];
  495. raw_times[k] = raw_times[n];
  496. raw_times[n] = tmp;
  497. }
  498. /* Since the times are now shuffled, take a random CBT_NCIRCUITS_TO_OBSERVE
  499. * subset (ie the first CBT_NCIRCUITS_TO_OBSERVE values) */
  500. for (n = 0; n < MIN(num_times, CBT_NCIRCUITS_TO_OBSERVE); n++) {
  501. circuit_build_times_add_time(cbt, raw_times[n]);
  502. }
  503. }
  504. /**
  505. * Filter old synthetic timeouts that were created before the
  506. * new right-censored Pareto calculation was deployed.
  507. *
  508. * Once all clients before 0.2.1.13-alpha are gone, this code
  509. * will be unused.
  510. */
  511. static int
  512. circuit_build_times_filter_timeouts(circuit_build_times_t *cbt)
  513. {
  514. int num_filtered=0, i=0;
  515. double timeout_rate = 0;
  516. build_time_t max_timeout = 0;
  517. timeout_rate = circuit_build_times_timeout_rate(cbt);
  518. max_timeout = (build_time_t)cbt->close_ms;
  519. for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
  520. if (cbt->circuit_build_times[i] > max_timeout) {
  521. build_time_t replaced = cbt->circuit_build_times[i];
  522. num_filtered++;
  523. cbt->circuit_build_times[i] = CBT_BUILD_ABANDONED;
  524. log_debug(LD_CIRC, "Replaced timeout %d with %d", replaced,
  525. cbt->circuit_build_times[i]);
  526. }
  527. }
  528. log_info(LD_CIRC,
  529. "We had %d timeouts out of %d build times, "
  530. "and filtered %d above the max of %u",
  531. (int)(cbt->total_build_times*timeout_rate),
  532. cbt->total_build_times, num_filtered, max_timeout);
  533. return num_filtered;
  534. }
  535. /**
  536. * Load histogram from <b>state</b>, shuffling the resulting array
  537. * after we do so. Use this result to estimate parameters and
  538. * calculate the timeout.
  539. *
  540. * Return -1 on error.
  541. */
  542. int
  543. circuit_build_times_parse_state(circuit_build_times_t *cbt,
  544. or_state_t *state)
  545. {
  546. int tot_values = 0;
  547. uint32_t loaded_cnt = 0, N = 0;
  548. config_line_t *line;
  549. unsigned int i;
  550. build_time_t *loaded_times;
  551. int err = 0;
  552. circuit_build_times_init(cbt);
  553. if (circuit_build_times_disabled()) {
  554. return 0;
  555. }
  556. /* build_time_t 0 means uninitialized */
  557. loaded_times = tor_malloc_zero(sizeof(build_time_t)*state->TotalBuildTimes);
  558. for (line = state->BuildtimeHistogram; line; line = line->next) {
  559. smartlist_t *args = smartlist_create();
  560. smartlist_split_string(args, line->value, " ",
  561. SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
  562. if (smartlist_len(args) < 2) {
  563. log_warn(LD_GENERAL, "Unable to parse circuit build times: "
  564. "Too few arguments to CircuitBuildTime");
  565. err = 1;
  566. SMARTLIST_FOREACH(args, char*, cp, tor_free(cp));
  567. smartlist_free(args);
  568. break;
  569. } else {
  570. const char *ms_str = smartlist_get(args,0);
  571. const char *count_str = smartlist_get(args,1);
  572. uint32_t count, k;
  573. build_time_t ms;
  574. int ok;
  575. ms = (build_time_t)tor_parse_ulong(ms_str, 0, 0,
  576. CBT_BUILD_TIME_MAX, &ok, NULL);
  577. if (!ok) {
  578. log_warn(LD_GENERAL, "Unable to parse circuit build times: "
  579. "Unparsable bin number");
  580. err = 1;
  581. SMARTLIST_FOREACH(args, char*, cp, tor_free(cp));
  582. smartlist_free(args);
  583. break;
  584. }
  585. count = (uint32_t)tor_parse_ulong(count_str, 0, 0,
  586. UINT32_MAX, &ok, NULL);
  587. if (!ok) {
  588. log_warn(LD_GENERAL, "Unable to parse circuit build times: "
  589. "Unparsable bin count");
  590. err = 1;
  591. SMARTLIST_FOREACH(args, char*, cp, tor_free(cp));
  592. smartlist_free(args);
  593. break;
  594. }
  595. if (loaded_cnt+count+state->CircuitBuildAbandonedCount
  596. > state->TotalBuildTimes) {
  597. log_warn(LD_CIRC,
  598. "Too many build times in state file. "
  599. "Stopping short before %d",
  600. loaded_cnt+count);
  601. SMARTLIST_FOREACH(args, char*, cp, tor_free(cp));
  602. smartlist_free(args);
  603. break;
  604. }
  605. for (k = 0; k < count; k++) {
  606. loaded_times[loaded_cnt++] = ms;
  607. }
  608. N++;
  609. SMARTLIST_FOREACH(args, char*, cp, tor_free(cp));
  610. smartlist_free(args);
  611. }
  612. }
  613. log_info(LD_CIRC,
  614. "Adding %d timeouts.", state->CircuitBuildAbandonedCount);
  615. for (i=0; i < state->CircuitBuildAbandonedCount; i++) {
  616. loaded_times[loaded_cnt++] = CBT_BUILD_ABANDONED;
  617. }
  618. if (loaded_cnt != state->TotalBuildTimes) {
  619. log_warn(LD_CIRC,
  620. "Corrupt state file? Build times count mismatch. "
  621. "Read %d times, but file says %d", loaded_cnt,
  622. state->TotalBuildTimes);
  623. err = 1;
  624. circuit_build_times_reset(cbt);
  625. goto done;
  626. }
  627. circuit_build_times_shuffle_and_store_array(cbt, loaded_times, loaded_cnt);
  628. /* Verify that we didn't overwrite any indexes */
  629. for (i=0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
  630. if (!cbt->circuit_build_times[i])
  631. break;
  632. tot_values++;
  633. }
  634. log_info(LD_CIRC,
  635. "Loaded %d/%d values from %d lines in circuit time histogram",
  636. tot_values, cbt->total_build_times, N);
  637. if (cbt->total_build_times != tot_values
  638. || cbt->total_build_times > CBT_NCIRCUITS_TO_OBSERVE) {
  639. log_warn(LD_CIRC,
  640. "Corrupt state file? Shuffled build times mismatch. "
  641. "Read %d times, but file says %d", tot_values,
  642. state->TotalBuildTimes);
  643. err = 1;
  644. circuit_build_times_reset(cbt);
  645. goto done;
  646. }
  647. circuit_build_times_set_timeout(cbt);
  648. if (!state->CircuitBuildAbandonedCount && cbt->total_build_times) {
  649. circuit_build_times_filter_timeouts(cbt);
  650. }
  651. done:
  652. tor_free(loaded_times);
  653. return err ? -1 : 0;
  654. }
  655. /**
  656. * Estimates the Xm and Alpha parameters using
  657. * http://en.wikipedia.org/wiki/Pareto_distribution#Parameter_estimation
  658. *
  659. * The notable difference is that we use mode instead of min to estimate Xm.
  660. * This is because our distribution is frechet-like. We claim this is
  661. * an acceptable approximation because we are only concerned with the
  662. * accuracy of the CDF of the tail.
  663. */
  664. int
  665. circuit_build_times_update_alpha(circuit_build_times_t *cbt)
  666. {
  667. build_time_t *x=cbt->circuit_build_times;
  668. double a = 0;
  669. int n=0,i=0,abandoned_count=0;
  670. build_time_t max_time=0;
  671. /* http://en.wikipedia.org/wiki/Pareto_distribution#Parameter_estimation */
  672. /* We sort of cheat here and make our samples slightly more pareto-like
  673. * and less frechet-like. */
  674. cbt->Xm = circuit_build_times_get_xm(cbt);
  675. tor_assert(cbt->Xm > 0);
  676. for (i=0; i< CBT_NCIRCUITS_TO_OBSERVE; i++) {
  677. if (!x[i]) {
  678. continue;
  679. }
  680. if (x[i] < cbt->Xm) {
  681. a += tor_mathlog(cbt->Xm);
  682. } else if (x[i] == CBT_BUILD_ABANDONED) {
  683. abandoned_count++;
  684. } else {
  685. a += tor_mathlog(x[i]);
  686. if (x[i] > max_time)
  687. max_time = x[i];
  688. }
  689. n++;
  690. }
  691. /*
  692. * We are erring and asserting here because this can only happen
  693. * in codepaths other than startup. The startup state parsing code
  694. * performs this same check, and resets state if it hits it. If we
  695. * hit it at runtime, something serious has gone wrong.
  696. */
  697. if (n!=cbt->total_build_times) {
  698. log_err(LD_CIRC, "Discrepancy in build times count: %d vs %d", n,
  699. cbt->total_build_times);
  700. }
  701. tor_assert(n==cbt->total_build_times);
  702. if (max_time <= 0) {
  703. /* This can happen if Xm is actually the *maximum* value in the set.
  704. * It can also happen if we've abandoned every single circuit somehow.
  705. * In either case, tell the caller not to compute a new build timeout. */
  706. log_warn(LD_BUG,
  707. "Could not determine largest build time (%d). "
  708. "Xm is %dms and we've abandoned %d out of %d circuits.", max_time,
  709. cbt->Xm, abandoned_count, n);
  710. return 0;
  711. }
  712. a += abandoned_count*tor_mathlog(max_time);
  713. a -= n*tor_mathlog(cbt->Xm);
  714. // Estimator comes from Eq #4 in:
  715. // "Bayesian estimation based on trimmed samples from Pareto populations"
  716. // by Arturo J. Fernández. We are right-censored only.
  717. a = (n-abandoned_count)/a;
  718. cbt->alpha = a;
  719. return 1;
  720. }
  721. /**
  722. * This is the Pareto Quantile Function. It calculates the point x
  723. * in the distribution such that F(x) = quantile (ie quantile*100%
  724. * of the mass of the density function is below x on the curve).
  725. *
  726. * We use it to calculate the timeout and also to generate synthetic
  727. * values of time for circuits that timeout before completion.
  728. *
  729. * See http://en.wikipedia.org/wiki/Quantile_function,
  730. * http://en.wikipedia.org/wiki/Inverse_transform_sampling and
  731. * http://en.wikipedia.org/wiki/Pareto_distribution#Generating_a_
  732. * random_sample_from_Pareto_distribution
  733. * That's right. I'll cite wikipedia all day long.
  734. *
  735. * Return value is in milliseconds.
  736. */
  737. double
  738. circuit_build_times_calculate_timeout(circuit_build_times_t *cbt,
  739. double quantile)
  740. {
  741. double ret;
  742. tor_assert(quantile >= 0);
  743. tor_assert(1.0-quantile > 0);
  744. tor_assert(cbt->Xm > 0);
  745. ret = cbt->Xm/pow(1.0-quantile,1.0/cbt->alpha);
  746. if (ret > INT32_MAX) {
  747. ret = INT32_MAX;
  748. }
  749. tor_assert(ret > 0);
  750. return ret;
  751. }
  752. /** Pareto CDF */
  753. double
  754. circuit_build_times_cdf(circuit_build_times_t *cbt, double x)
  755. {
  756. double ret;
  757. tor_assert(cbt->Xm > 0);
  758. ret = 1.0-pow(cbt->Xm/x,cbt->alpha);
  759. tor_assert(0 <= ret && ret <= 1.0);
  760. return ret;
  761. }
  762. /**
  763. * Generate a synthetic time using our distribution parameters.
  764. *
  765. * The return value will be within the [q_lo, q_hi) quantile points
  766. * on the CDF.
  767. */
  768. build_time_t
  769. circuit_build_times_generate_sample(circuit_build_times_t *cbt,
  770. double q_lo, double q_hi)
  771. {
  772. double randval = crypto_rand_double();
  773. build_time_t ret;
  774. double u;
  775. /* Generate between [q_lo, q_hi) */
  776. /*XXXX This is what nextafter is supposed to be for; we should use it on the
  777. * platforms that support it. */
  778. q_hi -= 1.0/(INT32_MAX);
  779. tor_assert(q_lo >= 0);
  780. tor_assert(q_hi < 1);
  781. tor_assert(q_lo < q_hi);
  782. u = q_lo + (q_hi-q_lo)*randval;
  783. tor_assert(0 <= u && u < 1.0);
  784. /* circuit_build_times_calculate_timeout returns <= INT32_MAX */
  785. ret = (build_time_t)
  786. tor_lround(circuit_build_times_calculate_timeout(cbt, u));
  787. tor_assert(ret > 0);
  788. return ret;
  789. }
  790. /**
  791. * Estimate an initial alpha parameter by solving the quantile
  792. * function with a quantile point and a specific timeout value.
  793. */
  794. void
  795. circuit_build_times_initial_alpha(circuit_build_times_t *cbt,
  796. double quantile, double timeout_ms)
  797. {
  798. // Q(u) = Xm/((1-u)^(1/a))
  799. // Q(0.8) = Xm/((1-0.8))^(1/a)) = CircBuildTimeout
  800. // CircBuildTimeout = Xm/((1-0.8))^(1/a))
  801. // CircBuildTimeout = Xm*((1-0.8))^(-1/a))
  802. // ln(CircBuildTimeout) = ln(Xm)+ln(((1-0.8)))*(-1/a)
  803. // -ln(1-0.8)/(ln(CircBuildTimeout)-ln(Xm))=a
  804. tor_assert(quantile >= 0);
  805. tor_assert(cbt->Xm > 0);
  806. cbt->alpha = tor_mathlog(1.0-quantile)/
  807. (tor_mathlog(cbt->Xm)-tor_mathlog(timeout_ms));
  808. tor_assert(cbt->alpha > 0);
  809. }
  810. /**
  811. * Returns true if we need circuits to be built
  812. */
  813. int
  814. circuit_build_times_needs_circuits(circuit_build_times_t *cbt)
  815. {
  816. /* Return true if < MIN_CIRCUITS_TO_OBSERVE */
  817. return !circuit_build_times_enough_to_compute(cbt);
  818. }
  819. /**
  820. * Returns true if we should build a timeout test circuit
  821. * right now.
  822. */
  823. int
  824. circuit_build_times_needs_circuits_now(circuit_build_times_t *cbt)
  825. {
  826. return circuit_build_times_needs_circuits(cbt) &&
  827. approx_time()-cbt->last_circ_at > circuit_build_times_test_frequency();
  828. }
  829. /**
  830. * Called to indicate that the network showed some signs of liveness,
  831. * i.e. we received a cell.
  832. *
  833. * This is used by circuit_build_times_network_check_live() to decide
  834. * if we should record the circuit build timeout or not.
  835. *
  836. * This function is called every time we receive a cell. Avoid
  837. * syscalls, events, and other high-intensity work.
  838. */
  839. void
  840. circuit_build_times_network_is_live(circuit_build_times_t *cbt)
  841. {
  842. time_t now = approx_time();
  843. if (cbt->liveness.nonlive_timeouts > 0) {
  844. log_notice(LD_CIRC,
  845. "Tor now sees network activity. Restoring circuit build "
  846. "timeout recording. Network was down for %d seconds "
  847. "during %d circuit attempts.",
  848. (int)(now - cbt->liveness.network_last_live),
  849. cbt->liveness.nonlive_timeouts);
  850. }
  851. cbt->liveness.network_last_live = now;
  852. cbt->liveness.nonlive_timeouts = 0;
  853. }
  854. /**
  855. * Called to indicate that we completed a circuit. Because this circuit
  856. * succeeded, it doesn't count as a timeout-after-the-first-hop.
  857. *
  858. * This is used by circuit_build_times_network_check_changed() to determine
  859. * if we had too many recent timeouts and need to reset our learned timeout
  860. * to something higher.
  861. */
  862. void
  863. circuit_build_times_network_circ_success(circuit_build_times_t *cbt)
  864. {
  865. cbt->liveness.timeouts_after_firsthop[cbt->liveness.after_firsthop_idx] = 0;
  866. cbt->liveness.after_firsthop_idx++;
  867. cbt->liveness.after_firsthop_idx %= cbt->liveness.num_recent_circs;
  868. }
  869. /**
  870. * A circuit just timed out. If it failed after the first hop, record it
  871. * in our history for later deciding if the network speed has changed.
  872. *
  873. * This is used by circuit_build_times_network_check_changed() to determine
  874. * if we had too many recent timeouts and need to reset our learned timeout
  875. * to something higher.
  876. */
  877. static void
  878. circuit_build_times_network_timeout(circuit_build_times_t *cbt,
  879. int did_onehop)
  880. {
  881. if (did_onehop) {
  882. cbt->liveness.timeouts_after_firsthop[cbt->liveness.after_firsthop_idx]=1;
  883. cbt->liveness.after_firsthop_idx++;
  884. cbt->liveness.after_firsthop_idx %= cbt->liveness.num_recent_circs;
  885. }
  886. }
  887. /**
  888. * A circuit was just forcibly closed. If there has been no recent network
  889. * activity at all, but this circuit was launched back when we thought the
  890. * network was live, increment the number of "nonlive" circuit timeouts.
  891. *
  892. * This is used by circuit_build_times_network_check_live() to decide
  893. * if we should record the circuit build timeout or not.
  894. */
  895. static void
  896. circuit_build_times_network_close(circuit_build_times_t *cbt,
  897. int did_onehop, time_t start_time)
  898. {
  899. time_t now = time(NULL);
  900. /*
  901. * Check if this is a timeout that was for a circuit that spent its
  902. * entire existence during a time where we have had no network activity.
  903. */
  904. if (cbt->liveness.network_last_live < start_time) {
  905. if (did_onehop) {
  906. char last_live_buf[ISO_TIME_LEN+1];
  907. char start_time_buf[ISO_TIME_LEN+1];
  908. char now_buf[ISO_TIME_LEN+1];
  909. format_local_iso_time(last_live_buf, cbt->liveness.network_last_live);
  910. format_local_iso_time(start_time_buf, start_time);
  911. format_local_iso_time(now_buf, now);
  912. log_warn(LD_BUG,
  913. "Circuit somehow completed a hop while the network was "
  914. "not live. Network was last live at %s, but circuit launched "
  915. "at %s. It's now %s.", last_live_buf, start_time_buf,
  916. now_buf);
  917. }
  918. cbt->liveness.nonlive_timeouts++;
  919. if (cbt->liveness.nonlive_timeouts == 1) {
  920. log_notice(LD_CIRC,
  921. "Tor has not observed any network activity for the past %d "
  922. "seconds. Disabling circuit build timeout code.",
  923. (int)(now - cbt->liveness.network_last_live));
  924. } else {
  925. log_info(LD_CIRC,
  926. "Got non-live timeout. Current count is: %d",
  927. cbt->liveness.nonlive_timeouts);
  928. }
  929. }
  930. }
  931. /**
  932. * When the network is not live, we do not record circuit build times.
  933. *
  934. * The network is considered not live if there has been at least one
  935. * circuit build that began and ended (had its close_ms measurement
  936. * period expire) since we last received a cell.
  937. *
  938. * Also has the side effect of rewinding the circuit time history
  939. * in the case of recent liveness changes.
  940. */
  941. int
  942. circuit_build_times_network_check_live(circuit_build_times_t *cbt)
  943. {
  944. if (cbt->liveness.nonlive_timeouts > 0) {
  945. return 0;
  946. }
  947. return 1;
  948. }
  949. /**
  950. * Returns true if we have seen more than MAX_RECENT_TIMEOUT_COUNT of
  951. * the past RECENT_CIRCUITS time out after the first hop. Used to detect
  952. * if the network connection has changed significantly, and if so,
  953. * resets our circuit build timeout to the default.
  954. *
  955. * Also resets the entire timeout history in this case and causes us
  956. * to restart the process of building test circuits and estimating a
  957. * new timeout.
  958. */
  959. int
  960. circuit_build_times_network_check_changed(circuit_build_times_t *cbt)
  961. {
  962. int total_build_times = cbt->total_build_times;
  963. int timeout_count=0;
  964. int i;
  965. /* how many of our recent circuits made it to the first hop but then
  966. * timed out? */
  967. for (i = 0; i < cbt->liveness.num_recent_circs; i++) {
  968. timeout_count += cbt->liveness.timeouts_after_firsthop[i];
  969. }
  970. /* If 80% of our recent circuits are timing out after the first hop,
  971. * we need to re-estimate a new initial alpha and timeout. */
  972. if (timeout_count < circuit_build_times_max_timeouts()) {
  973. return 0;
  974. }
  975. circuit_build_times_reset(cbt);
  976. memset(cbt->liveness.timeouts_after_firsthop, 0,
  977. sizeof(*cbt->liveness.timeouts_after_firsthop)*
  978. cbt->liveness.num_recent_circs);
  979. cbt->liveness.after_firsthop_idx = 0;
  980. /* Check to see if this has happened before. If so, double the timeout
  981. * to give people on abysmally bad network connections a shot at access */
  982. if (cbt->timeout_ms >= circuit_build_times_get_initial_timeout()) {
  983. if (cbt->timeout_ms > INT32_MAX/2 || cbt->close_ms > INT32_MAX/2) {
  984. log_warn(LD_CIRC, "Insanely large circuit build timeout value. "
  985. "(timeout = %lfmsec, close = %lfmsec)",
  986. cbt->timeout_ms, cbt->close_ms);
  987. } else {
  988. cbt->timeout_ms *= 2;
  989. cbt->close_ms *= 2;
  990. }
  991. } else {
  992. cbt->close_ms = cbt->timeout_ms
  993. = circuit_build_times_get_initial_timeout();
  994. }
  995. control_event_buildtimeout_set(cbt, BUILDTIMEOUT_SET_EVENT_RESET);
  996. log_notice(LD_CIRC,
  997. "Network connection speed appears to have changed. Resetting "
  998. "timeout to %lds after %d timeouts and %d buildtimes.",
  999. tor_lround(cbt->timeout_ms/1000), timeout_count,
  1000. total_build_times);
  1001. return 1;
  1002. }
  1003. /**
  1004. * Count the number of timeouts in a set of cbt data.
  1005. */
  1006. double
  1007. circuit_build_times_timeout_rate(const circuit_build_times_t *cbt)
  1008. {
  1009. int i=0,timeouts=0;
  1010. for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
  1011. if (cbt->circuit_build_times[i] >= cbt->timeout_ms) {
  1012. timeouts++;
  1013. }
  1014. }
  1015. if (!cbt->total_build_times)
  1016. return 0;
  1017. return ((double)timeouts)/cbt->total_build_times;
  1018. }
  1019. /**
  1020. * Count the number of closed circuits in a set of cbt data.
  1021. */
  1022. double
  1023. circuit_build_times_close_rate(const circuit_build_times_t *cbt)
  1024. {
  1025. int i=0,closed=0;
  1026. for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
  1027. if (cbt->circuit_build_times[i] == CBT_BUILD_ABANDONED) {
  1028. closed++;
  1029. }
  1030. }
  1031. if (!cbt->total_build_times)
  1032. return 0;
  1033. return ((double)closed)/cbt->total_build_times;
  1034. }
  1035. /**
  1036. * Store a timeout as a synthetic value.
  1037. *
  1038. * Returns true if the store was successful and we should possibly
  1039. * update our timeout estimate.
  1040. */
  1041. int
  1042. circuit_build_times_count_close(circuit_build_times_t *cbt,
  1043. int did_onehop,
  1044. time_t start_time)
  1045. {
  1046. if (circuit_build_times_disabled()) {
  1047. cbt->close_ms = cbt->timeout_ms
  1048. = circuit_build_times_get_initial_timeout();
  1049. return 0;
  1050. }
  1051. /* Record this force-close to help determine if the network is dead */
  1052. circuit_build_times_network_close(cbt, did_onehop, start_time);
  1053. /* Only count timeouts if network is live.. */
  1054. if (!circuit_build_times_network_check_live(cbt)) {
  1055. return 0;
  1056. }
  1057. circuit_build_times_add_time(cbt, CBT_BUILD_ABANDONED);
  1058. return 1;
  1059. }
  1060. /**
  1061. * Update timeout counts to determine if we need to expire
  1062. * our build time history due to excessive timeouts.
  1063. *
  1064. * We do not record any actual time values at this stage;
  1065. * we are only interested in recording the fact that a timeout
  1066. * happened. We record the time values via
  1067. * circuit_build_times_count_close() and circuit_build_times_add_time().
  1068. */
  1069. void
  1070. circuit_build_times_count_timeout(circuit_build_times_t *cbt,
  1071. int did_onehop)
  1072. {
  1073. if (circuit_build_times_disabled()) {
  1074. cbt->close_ms = cbt->timeout_ms
  1075. = circuit_build_times_get_initial_timeout();
  1076. return;
  1077. }
  1078. /* Register the fact that a timeout just occurred. */
  1079. circuit_build_times_network_timeout(cbt, did_onehop);
  1080. /* If there are a ton of timeouts, we should reset
  1081. * the circuit build timeout. */
  1082. circuit_build_times_network_check_changed(cbt);
  1083. }
  1084. /**
  1085. * Estimate a new timeout based on history and set our timeout
  1086. * variable accordingly.
  1087. */
  1088. static int
  1089. circuit_build_times_set_timeout_worker(circuit_build_times_t *cbt)
  1090. {
  1091. build_time_t max_time;
  1092. if (!circuit_build_times_enough_to_compute(cbt))
  1093. return 0;
  1094. if (!circuit_build_times_update_alpha(cbt))
  1095. return 0;
  1096. cbt->timeout_ms = circuit_build_times_calculate_timeout(cbt,
  1097. circuit_build_times_quantile_cutoff());
  1098. cbt->close_ms = circuit_build_times_calculate_timeout(cbt,
  1099. circuit_build_times_close_quantile());
  1100. max_time = circuit_build_times_max(cbt);
  1101. /* Sometimes really fast guard nodes give us such a steep curve
  1102. * that this ends up being not that much greater than timeout_ms.
  1103. * Make it be at least 1 min to handle this case. */
  1104. cbt->close_ms = MAX(cbt->close_ms, circuit_build_times_initial_timeout());
  1105. if (cbt->timeout_ms > max_time) {
  1106. log_notice(LD_CIRC,
  1107. "Circuit build timeout of %dms is beyond the maximum build "
  1108. "time we have ever observed. Capping it to %dms.",
  1109. (int)cbt->timeout_ms, max_time);
  1110. cbt->timeout_ms = max_time;
  1111. }
  1112. if (max_time < INT32_MAX/2 && cbt->close_ms > 2*max_time) {
  1113. log_notice(LD_CIRC,
  1114. "Circuit build measurement period of %dms is more than twice "
  1115. "the maximum build time we have ever observed. Capping it to "
  1116. "%dms.", (int)cbt->close_ms, 2*max_time);
  1117. cbt->close_ms = 2*max_time;
  1118. }
  1119. cbt->have_computed_timeout = 1;
  1120. return 1;
  1121. }
  1122. /**
  1123. * Exposed function to compute a new timeout. Dispatches events and
  1124. * also filters out extremely high timeout values.
  1125. */
  1126. void
  1127. circuit_build_times_set_timeout(circuit_build_times_t *cbt)
  1128. {
  1129. long prev_timeout = tor_lround(cbt->timeout_ms/1000);
  1130. double timeout_rate;
  1131. if (!circuit_build_times_set_timeout_worker(cbt))
  1132. return;
  1133. if (cbt->timeout_ms < circuit_build_times_min_timeout()) {
  1134. log_warn(LD_CIRC, "Set buildtimeout to low value %lfms. Setting to %dms",
  1135. cbt->timeout_ms, circuit_build_times_min_timeout());
  1136. cbt->timeout_ms = circuit_build_times_min_timeout();
  1137. if (cbt->close_ms < cbt->timeout_ms) {
  1138. /* This shouldn't happen because of MAX() in timeout_worker above,
  1139. * but doing it just in case */
  1140. cbt->close_ms = circuit_build_times_initial_timeout();
  1141. }
  1142. }
  1143. control_event_buildtimeout_set(cbt, BUILDTIMEOUT_SET_EVENT_COMPUTED);
  1144. timeout_rate = circuit_build_times_timeout_rate(cbt);
  1145. if (prev_timeout > tor_lround(cbt->timeout_ms/1000)) {
  1146. log_notice(LD_CIRC,
  1147. "Based on %d circuit times, it looks like we don't need to "
  1148. "wait so long for circuits to finish. We will now assume a "
  1149. "circuit is too slow to use after waiting %ld seconds.",
  1150. cbt->total_build_times,
  1151. tor_lround(cbt->timeout_ms/1000));
  1152. log_info(LD_CIRC,
  1153. "Circuit timeout data: %lfms, %lfms, Xm: %d, a: %lf, r: %lf",
  1154. cbt->timeout_ms, cbt->close_ms, cbt->Xm, cbt->alpha,
  1155. timeout_rate);
  1156. } else if (prev_timeout < tor_lround(cbt->timeout_ms/1000)) {
  1157. log_notice(LD_CIRC,
  1158. "Based on %d circuit times, it looks like we need to wait "
  1159. "longer for circuits to finish. We will now assume a "
  1160. "circuit is too slow to use after waiting %ld seconds.",
  1161. cbt->total_build_times,
  1162. tor_lround(cbt->timeout_ms/1000));
  1163. log_info(LD_CIRC,
  1164. "Circuit timeout data: %lfms, %lfms, Xm: %d, a: %lf, r: %lf",
  1165. cbt->timeout_ms, cbt->close_ms, cbt->Xm, cbt->alpha,
  1166. timeout_rate);
  1167. } else {
  1168. log_info(LD_CIRC,
  1169. "Set circuit build timeout to %lds (%lfms, %lfms, Xm: %d, a: %lf,"
  1170. " r: %lf) based on %d circuit times",
  1171. tor_lround(cbt->timeout_ms/1000),
  1172. cbt->timeout_ms, cbt->close_ms, cbt->Xm, cbt->alpha, timeout_rate,
  1173. cbt->total_build_times);
  1174. }
  1175. }
  1176. /** Iterate over values of circ_id, starting from conn-\>next_circ_id,
  1177. * and with the high bit specified by conn-\>circ_id_type, until we get
  1178. * a circ_id that is not in use by any other circuit on that conn.
  1179. *
  1180. * Return it, or 0 if can't get a unique circ_id.
  1181. */
  1182. static circid_t
  1183. get_unique_circ_id_by_conn(or_connection_t *conn)
  1184. {
  1185. circid_t test_circ_id;
  1186. circid_t attempts=0;
  1187. circid_t high_bit;
  1188. tor_assert(conn);
  1189. if (conn->circ_id_type == CIRC_ID_TYPE_NEITHER) {
  1190. log_warn(LD_BUG, "Trying to pick a circuit ID for a connection from "
  1191. "a client with no identity.");
  1192. return 0;
  1193. }
  1194. high_bit = (conn->circ_id_type == CIRC_ID_TYPE_HIGHER) ? 1<<15 : 0;
  1195. do {
  1196. /* Sequentially iterate over test_circ_id=1...1<<15-1 until we find a
  1197. * circID such that (high_bit|test_circ_id) is not already used. */
  1198. test_circ_id = conn->next_circ_id++;
  1199. if (test_circ_id == 0 || test_circ_id >= 1<<15) {
  1200. test_circ_id = 1;
  1201. conn->next_circ_id = 2;
  1202. }
  1203. if (++attempts > 1<<15) {
  1204. /* Make sure we don't loop forever if all circ_id's are used. This
  1205. * matters because it's an external DoS opportunity.
  1206. */
  1207. log_warn(LD_CIRC,"No unused circ IDs. Failing.");
  1208. return 0;
  1209. }
  1210. test_circ_id |= high_bit;
  1211. } while (circuit_id_in_use_on_orconn(test_circ_id, conn));
  1212. return test_circ_id;
  1213. }
  1214. /** If <b>verbose</b> is false, allocate and return a comma-separated list of
  1215. * the currently built elements of circuit_t. If <b>verbose</b> is true, also
  1216. * list information about link status in a more verbose format using spaces.
  1217. * If <b>verbose_names</b> is false, give nicknames for Named routers and hex
  1218. * digests for others; if <b>verbose_names</b> is true, use $DIGEST=Name style
  1219. * names.
  1220. */
  1221. static char *
  1222. circuit_list_path_impl(origin_circuit_t *circ, int verbose, int verbose_names)
  1223. {
  1224. crypt_path_t *hop;
  1225. smartlist_t *elements;
  1226. const char *states[] = {"closed", "waiting for keys", "open"};
  1227. char *s;
  1228. elements = smartlist_create();
  1229. if (verbose) {
  1230. const char *nickname = build_state_get_exit_nickname(circ->build_state);
  1231. char *cp;
  1232. tor_asprintf(&cp, "%s%s circ (length %d%s%s):",
  1233. circ->build_state->is_internal ? "internal" : "exit",
  1234. circ->build_state->need_uptime ? " (high-uptime)" : "",
  1235. circ->build_state->desired_path_len,
  1236. circ->_base.state == CIRCUIT_STATE_OPEN ? "" : ", exit ",
  1237. circ->_base.state == CIRCUIT_STATE_OPEN ? "" :
  1238. (nickname?nickname:"*unnamed*"));
  1239. smartlist_add(elements, cp);
  1240. }
  1241. hop = circ->cpath;
  1242. do {
  1243. routerinfo_t *ri;
  1244. routerstatus_t *rs;
  1245. char *elt;
  1246. const char *id;
  1247. if (!hop)
  1248. break;
  1249. if (!verbose && hop->state != CPATH_STATE_OPEN)
  1250. break;
  1251. if (!hop->extend_info)
  1252. break;
  1253. id = hop->extend_info->identity_digest;
  1254. if (verbose_names) {
  1255. elt = tor_malloc(MAX_VERBOSE_NICKNAME_LEN+1);
  1256. if ((ri = router_get_by_digest(id))) {
  1257. router_get_verbose_nickname(elt, ri);
  1258. } else if ((rs = router_get_consensus_status_by_id(id))) {
  1259. routerstatus_get_verbose_nickname(elt, rs);
  1260. } else if (is_legal_nickname(hop->extend_info->nickname)) {
  1261. elt[0] = '$';
  1262. base16_encode(elt+1, HEX_DIGEST_LEN+1, id, DIGEST_LEN);
  1263. elt[HEX_DIGEST_LEN+1]= '~';
  1264. strlcpy(elt+HEX_DIGEST_LEN+2,
  1265. hop->extend_info->nickname, MAX_NICKNAME_LEN+1);
  1266. } else {
  1267. elt[0] = '$';
  1268. base16_encode(elt+1, HEX_DIGEST_LEN+1, id, DIGEST_LEN);
  1269. }
  1270. } else { /* ! verbose_names */
  1271. if ((ri = router_get_by_digest(id)) &&
  1272. ri->is_named) {
  1273. elt = tor_strdup(hop->extend_info->nickname);
  1274. } else {
  1275. elt = tor_malloc(HEX_DIGEST_LEN+2);
  1276. elt[0] = '$';
  1277. base16_encode(elt+1, HEX_DIGEST_LEN+1, id, DIGEST_LEN);
  1278. }
  1279. }
  1280. tor_assert(elt);
  1281. if (verbose) {
  1282. size_t len = strlen(elt)+2+strlen(states[hop->state])+1;
  1283. char *v = tor_malloc(len);
  1284. tor_assert(hop->state <= 2);
  1285. tor_snprintf(v,len,"%s(%s)",elt,states[hop->state]);
  1286. smartlist_add(elements, v);
  1287. tor_free(elt);
  1288. } else {
  1289. smartlist_add(elements, elt);
  1290. }
  1291. hop = hop->next;
  1292. } while (hop != circ->cpath);
  1293. s = smartlist_join_strings(elements, verbose?" ":",", 0, NULL);
  1294. SMARTLIST_FOREACH(elements, char*, cp, tor_free(cp));
  1295. smartlist_free(elements);
  1296. return s;
  1297. }
  1298. /** If <b>verbose</b> is false, allocate and return a comma-separated
  1299. * list of the currently built elements of circuit_t. If
  1300. * <b>verbose</b> is true, also list information about link status in
  1301. * a more verbose format using spaces.
  1302. */
  1303. char *
  1304. circuit_list_path(origin_circuit_t *circ, int verbose)
  1305. {
  1306. return circuit_list_path_impl(circ, verbose, 0);
  1307. }
  1308. /** Allocate and return a comma-separated list of the currently built elements
  1309. * of circuit_t, giving each as a verbose nickname.
  1310. */
  1311. char *
  1312. circuit_list_path_for_controller(origin_circuit_t *circ)
  1313. {
  1314. return circuit_list_path_impl(circ, 0, 1);
  1315. }
  1316. /** Log, at severity <b>severity</b>, the nicknames of each router in
  1317. * circ's cpath. Also log the length of the cpath, and the intended
  1318. * exit point.
  1319. */
  1320. void
  1321. circuit_log_path(int severity, unsigned int domain, origin_circuit_t *circ)
  1322. {
  1323. char *s = circuit_list_path(circ,1);
  1324. tor_log(severity,domain,"%s",s);
  1325. tor_free(s);
  1326. }
  1327. /** Tell the rep(utation)hist(ory) module about the status of the links
  1328. * in circ. Hops that have become OPEN are marked as successfully
  1329. * extended; the _first_ hop that isn't open (if any) is marked as
  1330. * unable to extend.
  1331. */
  1332. /* XXXX Someday we should learn from OR circuits too. */
  1333. void
  1334. circuit_rep_hist_note_result(origin_circuit_t *circ)
  1335. {
  1336. crypt_path_t *hop;
  1337. char *prev_digest = NULL;
  1338. routerinfo_t *router;
  1339. hop = circ->cpath;
  1340. if (!hop) /* circuit hasn't started building yet. */
  1341. return;
  1342. if (server_mode(get_options())) {
  1343. routerinfo_t *me = router_get_my_routerinfo();
  1344. if (!me)
  1345. return;
  1346. prev_digest = me->cache_info.identity_digest;
  1347. }
  1348. do {
  1349. router = router_get_by_digest(hop->extend_info->identity_digest);
  1350. if (router) {
  1351. if (prev_digest) {
  1352. if (hop->state == CPATH_STATE_OPEN)
  1353. rep_hist_note_extend_succeeded(prev_digest,
  1354. router->cache_info.identity_digest);
  1355. else {
  1356. rep_hist_note_extend_failed(prev_digest,
  1357. router->cache_info.identity_digest);
  1358. break;
  1359. }
  1360. }
  1361. prev_digest = router->cache_info.identity_digest;
  1362. } else {
  1363. prev_digest = NULL;
  1364. }
  1365. hop=hop->next;
  1366. } while (hop!=circ->cpath);
  1367. }
  1368. /** Pick all the entries in our cpath. Stop and return 0 when we're
  1369. * happy, or return -1 if an error occurs. */
  1370. static int
  1371. onion_populate_cpath(origin_circuit_t *circ)
  1372. {
  1373. int r;
  1374. again:
  1375. r = onion_extend_cpath(circ);
  1376. if (r < 0) {
  1377. log_info(LD_CIRC,"Generating cpath hop failed.");
  1378. return -1;
  1379. }
  1380. if (r == 0)
  1381. goto again;
  1382. return 0; /* if r == 1 */
  1383. }
  1384. /** Create and return a new origin circuit. Initialize its purpose and
  1385. * build-state based on our arguments. The <b>flags</b> argument is a
  1386. * bitfield of CIRCLAUNCH_* flags. */
  1387. origin_circuit_t *
  1388. origin_circuit_init(uint8_t purpose, int flags)
  1389. {
  1390. /* sets circ->p_circ_id and circ->p_conn */
  1391. origin_circuit_t *circ = origin_circuit_new();
  1392. circuit_set_state(TO_CIRCUIT(circ), CIRCUIT_STATE_OR_WAIT);
  1393. circ->build_state = tor_malloc_zero(sizeof(cpath_build_state_t));
  1394. circ->build_state->onehop_tunnel =
  1395. ((flags & CIRCLAUNCH_ONEHOP_TUNNEL) ? 1 : 0);
  1396. circ->build_state->need_uptime =
  1397. ((flags & CIRCLAUNCH_NEED_UPTIME) ? 1 : 0);
  1398. circ->build_state->need_capacity =
  1399. ((flags & CIRCLAUNCH_NEED_CAPACITY) ? 1 : 0);
  1400. circ->build_state->is_internal =
  1401. ((flags & CIRCLAUNCH_IS_INTERNAL) ? 1 : 0);
  1402. circ->_base.purpose = purpose;
  1403. return circ;
  1404. }
  1405. /** Build a new circuit for <b>purpose</b>. If <b>exit</b>
  1406. * is defined, then use that as your exit router, else choose a suitable
  1407. * exit node.
  1408. *
  1409. * Also launch a connection to the first OR in the chosen path, if
  1410. * it's not open already.
  1411. */
  1412. origin_circuit_t *
  1413. circuit_establish_circuit(uint8_t purpose, extend_info_t *exit, int flags)
  1414. {
  1415. origin_circuit_t *circ;
  1416. int err_reason = 0;
  1417. circ = origin_circuit_init(purpose, flags);
  1418. if (onion_pick_cpath_exit(circ, exit) < 0 ||
  1419. onion_populate_cpath(circ) < 0) {
  1420. circuit_mark_for_close(TO_CIRCUIT(circ), END_CIRC_REASON_NOPATH);
  1421. return NULL;
  1422. }
  1423. control_event_circuit_status(circ, CIRC_EVENT_LAUNCHED, 0);
  1424. if ((err_reason = circuit_handle_first_hop(circ)) < 0) {
  1425. circuit_mark_for_close(TO_CIRCUIT(circ), -err_reason);
  1426. return NULL;
  1427. }
  1428. return circ;
  1429. }
  1430. /** Start establishing the first hop of our circuit. Figure out what
  1431. * OR we should connect to, and if necessary start the connection to
  1432. * it. If we're already connected, then send the 'create' cell.
  1433. * Return 0 for ok, -reason if circ should be marked-for-close. */
  1434. int
  1435. circuit_handle_first_hop(origin_circuit_t *circ)
  1436. {
  1437. crypt_path_t *firsthop;
  1438. or_connection_t *n_conn;
  1439. int err_reason = 0;
  1440. const char *msg = NULL;
  1441. int should_launch = 0;
  1442. firsthop = onion_next_hop_in_cpath(circ->cpath);
  1443. tor_assert(firsthop);
  1444. tor_assert(firsthop->extend_info);
  1445. /* now see if we're already connected to the first OR in 'route' */
  1446. log_debug(LD_CIRC,"Looking for firsthop '%s:%u'",
  1447. fmt_addr(&firsthop->extend_info->addr),
  1448. firsthop->extend_info->port);
  1449. n_conn = connection_or_get_for_extend(firsthop->extend_info->identity_digest,
  1450. &firsthop->extend_info->addr,
  1451. &msg,
  1452. &should_launch);
  1453. if (!n_conn) {
  1454. /* not currently connected in a useful way. */
  1455. const char *name = strlen(firsthop->extend_info->nickname) ?
  1456. firsthop->extend_info->nickname : fmt_addr(&firsthop->extend_info->addr);
  1457. log_info(LD_CIRC, "Next router is %s: %s ",
  1458. safe_str_client(name), msg?msg:"???");
  1459. circ->_base.n_hop = extend_info_dup(firsthop->extend_info);
  1460. if (should_launch) {
  1461. if (circ->build_state->onehop_tunnel)
  1462. control_event_bootstrap(BOOTSTRAP_STATUS_CONN_DIR, 0);
  1463. n_conn = connection_or_connect(&firsthop->extend_info->addr,
  1464. firsthop->extend_info->port,
  1465. firsthop->extend_info->identity_digest);
  1466. if (!n_conn) { /* connect failed, forget the whole thing */
  1467. log_info(LD_CIRC,"connect to firsthop failed. Closing.");
  1468. return -END_CIRC_REASON_CONNECTFAILED;
  1469. }
  1470. }
  1471. log_debug(LD_CIRC,"connecting in progress (or finished). Good.");
  1472. /* return success. The onion/circuit/etc will be taken care of
  1473. * automatically (may already have been) whenever n_conn reaches
  1474. * OR_CONN_STATE_OPEN.
  1475. */
  1476. return 0;
  1477. } else { /* it's already open. use it. */
  1478. tor_assert(!circ->_base.n_hop);
  1479. circ->_base.n_conn = n_conn;
  1480. log_debug(LD_CIRC,"Conn open. Delivering first onion skin.");
  1481. if ((err_reason = circuit_send_next_onion_skin(circ)) < 0) {
  1482. log_info(LD_CIRC,"circuit_send_next_onion_skin failed.");
  1483. return err_reason;
  1484. }
  1485. }
  1486. return 0;
  1487. }
  1488. /** Find any circuits that are waiting on <b>or_conn</b> to become
  1489. * open and get them to send their create cells forward.
  1490. *
  1491. * Status is 1 if connect succeeded, or 0 if connect failed.
  1492. */
  1493. void
  1494. circuit_n_conn_done(or_connection_t *or_conn, int status)
  1495. {
  1496. smartlist_t *pending_circs;
  1497. int err_reason = 0;
  1498. log_debug(LD_CIRC,"or_conn to %s/%s, status=%d",
  1499. or_conn->nickname ? or_conn->nickname : "NULL",
  1500. or_conn->_base.address, status);
  1501. pending_circs = smartlist_create();
  1502. circuit_get_all_pending_on_or_conn(pending_circs, or_conn);
  1503. SMARTLIST_FOREACH_BEGIN(pending_circs, circuit_t *, circ)
  1504. {
  1505. /* These checks are redundant wrt get_all_pending_on_or_conn, but I'm
  1506. * leaving them in in case it's possible for the status of a circuit to
  1507. * change as we're going down the list. */
  1508. if (circ->marked_for_close || circ->n_conn || !circ->n_hop ||
  1509. circ->state != CIRCUIT_STATE_OR_WAIT)
  1510. continue;
  1511. if (tor_digest_is_zero(circ->n_hop->identity_digest)) {
  1512. /* Look at addr/port. This is an unkeyed connection. */
  1513. if (!tor_addr_eq(&circ->n_hop->addr, &or_conn->_base.addr) ||
  1514. circ->n_hop->port != or_conn->_base.port)
  1515. continue;
  1516. } else {
  1517. /* We expected a key. See if it's the right one. */
  1518. if (memcmp(or_conn->identity_digest,
  1519. circ->n_hop->identity_digest, DIGEST_LEN))
  1520. continue;
  1521. }
  1522. if (!status) { /* or_conn failed; close circ */
  1523. log_info(LD_CIRC,"or_conn failed. Closing circ.");
  1524. circuit_mark_for_close(circ, END_CIRC_REASON_OR_CONN_CLOSED);
  1525. continue;
  1526. }
  1527. log_debug(LD_CIRC, "Found circ, sending create cell.");
  1528. /* circuit_deliver_create_cell will set n_circ_id and add us to
  1529. * orconn_circuid_circuit_map, so we don't need to call
  1530. * set_circid_orconn here. */
  1531. circ->n_conn = or_conn;
  1532. extend_info_free(circ->n_hop);
  1533. circ->n_hop = NULL;
  1534. if (CIRCUIT_IS_ORIGIN(circ)) {
  1535. if ((err_reason =
  1536. circuit_send_next_onion_skin(TO_ORIGIN_CIRCUIT(circ))) < 0) {
  1537. log_info(LD_CIRC,
  1538. "send_next_onion_skin failed; circuit marked for closing.");
  1539. circuit_mark_for_close(circ, -err_reason);
  1540. continue;
  1541. /* XXX could this be bad, eg if next_onion_skin failed because conn
  1542. * died? */
  1543. }
  1544. } else {
  1545. /* pull the create cell out of circ->onionskin, and send it */
  1546. tor_assert(circ->n_conn_onionskin);
  1547. if (circuit_deliver_create_cell(circ,CELL_CREATE,
  1548. circ->n_conn_onionskin)<0) {
  1549. circuit_mark_for_close(circ, END_CIRC_REASON_RESOURCELIMIT);
  1550. continue;
  1551. }
  1552. tor_free(circ->n_conn_onionskin);
  1553. circuit_set_state(circ, CIRCUIT_STATE_OPEN);
  1554. }
  1555. }
  1556. SMARTLIST_FOREACH_END(circ);
  1557. smartlist_free(pending_circs);
  1558. }
  1559. /** Find a new circid that isn't currently in use on the circ->n_conn
  1560. * for the outgoing
  1561. * circuit <b>circ</b>, and deliver a cell of type <b>cell_type</b>
  1562. * (either CELL_CREATE or CELL_CREATE_FAST) with payload <b>payload</b>
  1563. * to this circuit.
  1564. * Return -1 if we failed to find a suitable circid, else return 0.
  1565. */
  1566. static int
  1567. circuit_deliver_create_cell(circuit_t *circ, uint8_t cell_type,
  1568. const char *payload)
  1569. {
  1570. cell_t cell;
  1571. circid_t id;
  1572. tor_assert(circ);
  1573. tor_assert(circ->n_conn);
  1574. tor_assert(payload);
  1575. tor_assert(cell_type == CELL_CREATE || cell_type == CELL_CREATE_FAST);
  1576. id = get_unique_circ_id_by_conn(circ->n_conn);
  1577. if (!id) {
  1578. log_warn(LD_CIRC,"failed to get unique circID.");
  1579. return -1;
  1580. }
  1581. log_debug(LD_CIRC,"Chosen circID %u.", id);
  1582. circuit_set_n_circid_orconn(circ, id, circ->n_conn);
  1583. memset(&cell, 0, sizeof(cell_t));
  1584. cell.command = cell_type;
  1585. cell.circ_id = circ->n_circ_id;
  1586. memcpy(cell.payload, payload, ONIONSKIN_CHALLENGE_LEN);
  1587. append_cell_to_circuit_queue(circ, circ->n_conn, &cell,
  1588. CELL_DIRECTION_OUT, 0);
  1589. if (CIRCUIT_IS_ORIGIN(circ)) {
  1590. /* mark it so it gets better rate limiting treatment. */
  1591. circ->n_conn->client_used = time(NULL);
  1592. }
  1593. return 0;
  1594. }
  1595. /** We've decided to start our reachability testing. If all
  1596. * is set, log this to the user. Return 1 if we did, or 0 if
  1597. * we chose not to log anything. */
  1598. int
  1599. inform_testing_reachability(void)
  1600. {
  1601. char dirbuf[128];
  1602. routerinfo_t *me = router_get_my_routerinfo();
  1603. if (!me)
  1604. return 0;
  1605. control_event_server_status(LOG_NOTICE,
  1606. "CHECKING_REACHABILITY ORADDRESS=%s:%d",
  1607. me->address, me->or_port);
  1608. if (me->dir_port) {
  1609. tor_snprintf(dirbuf, sizeof(dirbuf), " and DirPort %s:%d",
  1610. me->address, me->dir_port);
  1611. control_event_server_status(LOG_NOTICE,
  1612. "CHECKING_REACHABILITY DIRADDRESS=%s:%d",
  1613. me->address, me->dir_port);
  1614. }
  1615. log_notice(LD_OR, "Now checking whether ORPort %s:%d%s %s reachable... "
  1616. "(this may take up to %d minutes -- look for log "
  1617. "messages indicating success)",
  1618. me->address, me->or_port,
  1619. me->dir_port ? dirbuf : "",
  1620. me->dir_port ? "are" : "is",
  1621. TIMEOUT_UNTIL_UNREACHABILITY_COMPLAINT/60);
  1622. return 1;
  1623. }
  1624. /** Return true iff we should send a create_fast cell to start building a given
  1625. * circuit */
  1626. static INLINE int
  1627. should_use_create_fast_for_circuit(origin_circuit_t *circ)
  1628. {
  1629. or_options_t *options = get_options();
  1630. tor_assert(circ->cpath);
  1631. tor_assert(circ->cpath->extend_info);
  1632. if (!circ->cpath->extend_info->onion_key)
  1633. return 1; /* our hand is forced: only a create_fast will work. */
  1634. if (!options->FastFirstHopPK)
  1635. return 0; /* we prefer to avoid create_fast */
  1636. if (server_mode(options)) {
  1637. /* We're a server, and we know an onion key. We can choose.
  1638. * Prefer to blend in. */
  1639. return 0;
  1640. }
  1641. return 1;
  1642. }
  1643. /** Return true if <b>circ</b> is the type of circuit we want to count
  1644. * timeouts from. In particular, we want it to have not completed yet
  1645. * (already completing indicates we cannibalized it), and we want it to
  1646. * have exactly three hops.
  1647. */
  1648. int
  1649. circuit_timeout_want_to_count_circ(origin_circuit_t *circ)
  1650. {
  1651. return !circ->has_opened
  1652. && circ->build_state->desired_path_len == DEFAULT_ROUTE_LEN;
  1653. }
  1654. /** This is the backbone function for building circuits.
  1655. *
  1656. * If circ's first hop is closed, then we need to build a create
  1657. * cell and send it forward.
  1658. *
  1659. * Otherwise, we need to build a relay extend cell and send it
  1660. * forward.
  1661. *
  1662. * Return -reason if we want to tear down circ, else return 0.
  1663. */
  1664. int
  1665. circuit_send_next_onion_skin(origin_circuit_t *circ)
  1666. {
  1667. crypt_path_t *hop;
  1668. routerinfo_t *router;
  1669. char payload[2+4+DIGEST_LEN+ONIONSKIN_CHALLENGE_LEN];
  1670. char *onionskin;
  1671. size_t payload_len;
  1672. tor_assert(circ);
  1673. if (circ->cpath->state == CPATH_STATE_CLOSED) {
  1674. int fast;
  1675. uint8_t cell_type;
  1676. log_debug(LD_CIRC,"First skin; sending create cell.");
  1677. if (circ->build_state->onehop_tunnel)
  1678. control_event_bootstrap(BOOTSTRAP_STATUS_ONEHOP_CREATE, 0);
  1679. else
  1680. control_event_bootstrap(BOOTSTRAP_STATUS_CIRCUIT_CREATE, 0);
  1681. router = router_get_by_digest(circ->_base.n_conn->identity_digest);
  1682. fast = should_use_create_fast_for_circuit(circ);
  1683. if (!fast) {
  1684. /* We are an OR and we know the right onion key: we should
  1685. * send an old slow create cell.
  1686. */
  1687. cell_type = CELL_CREATE;
  1688. if (onion_skin_create(circ->cpath->extend_info->onion_key,
  1689. &(circ->cpath->dh_handshake_state),
  1690. payload) < 0) {
  1691. log_warn(LD_CIRC,"onion_skin_create (first hop) failed.");
  1692. return - END_CIRC_REASON_INTERNAL;
  1693. }
  1694. note_request("cell: create", 1);
  1695. } else {
  1696. /* We are not an OR, and we're building the first hop of a circuit to a
  1697. * new OR: we can be speedy and use CREATE_FAST to save an RSA operation
  1698. * and a DH operation. */
  1699. cell_type = CELL_CREATE_FAST;
  1700. memset(payload, 0, sizeof(payload));
  1701. crypto_rand((char*) circ->cpath->fast_handshake_state,
  1702. sizeof(circ->cpath->fast_handshake_state));
  1703. memcpy(payload, circ->cpath->fast_handshake_state,
  1704. sizeof(circ->cpath->fast_handshake_state));
  1705. note_request("cell: create fast", 1);
  1706. }
  1707. if (circuit_deliver_create_cell(TO_CIRCUIT(circ), cell_type, payload) < 0)
  1708. return - END_CIRC_REASON_RESOURCELIMIT;
  1709. circ->cpath->state = CPATH_STATE_AWAITING_KEYS;
  1710. circuit_set_state(TO_CIRCUIT(circ), CIRCUIT_STATE_BUILDING);
  1711. log_info(LD_CIRC,"First hop: finished sending %s cell to '%s'",
  1712. fast ? "CREATE_FAST" : "CREATE",
  1713. router ? router->nickname : "<unnamed>");
  1714. } else {
  1715. tor_assert(circ->cpath->state == CPATH_STATE_OPEN);
  1716. tor_assert(circ->_base.state == CIRCUIT_STATE_BUILDING);
  1717. log_debug(LD_CIRC,"starting to send subsequent skin.");
  1718. hop = onion_next_hop_in_cpath(circ->cpath);
  1719. if (!hop) {
  1720. /* done building the circuit. whew. */
  1721. circuit_set_state(TO_CIRCUIT(circ), CIRCUIT_STATE_OPEN);
  1722. if (circuit_timeout_want_to_count_circ(circ)) {
  1723. struct timeval end;
  1724. long timediff;
  1725. tor_gettimeofday(&end);
  1726. timediff = tv_mdiff(&circ->_base.highres_created, &end);
  1727. /*
  1728. * If the circuit build time is much greater than we would have cut
  1729. * it off at, we probably had a suspend event along this codepath,
  1730. * and we should discard the value.
  1731. */
  1732. if (timediff < 0 || timediff > 2*circ_times.close_ms+1000) {
  1733. log_notice(LD_CIRC, "Strange value for circuit build time: %ldmsec. "
  1734. "Assuming clock jump. Purpose %d", timediff,
  1735. circ->_base.purpose);
  1736. } else if (!circuit_build_times_disabled()) {
  1737. /* Only count circuit times if the network is live */
  1738. if (circuit_build_times_network_check_live(&circ_times)) {
  1739. circuit_build_times_add_time(&circ_times, (build_time_t)timediff);
  1740. circuit_build_times_set_timeout(&circ_times);
  1741. }
  1742. if (circ->_base.purpose != CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT) {
  1743. circuit_build_times_network_circ_success(&circ_times);
  1744. }
  1745. }
  1746. }
  1747. log_info(LD_CIRC,"circuit built!");
  1748. circuit_reset_failure_count(0);
  1749. if (circ->build_state->onehop_tunnel)
  1750. control_event_bootstrap(BOOTSTRAP_STATUS_REQUESTING_STATUS, 0);
  1751. if (!can_complete_circuit && !circ->build_state->onehop_tunnel) {
  1752. or_options_t *options = get_options();
  1753. can_complete_circuit=1;
  1754. /* FFFF Log a count of known routers here */
  1755. log_notice(LD_GENERAL,
  1756. "Tor has successfully opened a circuit. "
  1757. "Looks like client functionality is working.");
  1758. control_event_bootstrap(BOOTSTRAP_STATUS_DONE, 0);
  1759. control_event_client_status(LOG_NOTICE, "CIRCUIT_ESTABLISHED");
  1760. if (server_mode(options) && !check_whether_orport_reachable()) {
  1761. inform_testing_reachability();
  1762. consider_testing_reachability(1, 1);
  1763. }
  1764. }
  1765. circuit_rep_hist_note_result(circ);
  1766. circuit_has_opened(circ); /* do other actions as necessary */
  1767. /* We're done with measurement circuits here. Just close them */
  1768. if (circ->_base.purpose == CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT)
  1769. circuit_mark_for_close(TO_CIRCUIT(circ), END_CIRC_REASON_FINISHED);
  1770. return 0;
  1771. }
  1772. if (tor_addr_family(&hop->extend_info->addr) != AF_INET) {
  1773. log_warn(LD_BUG, "Trying to extend to a non-IPv4 address.");
  1774. return - END_CIRC_REASON_INTERNAL;
  1775. }
  1776. set_uint32(payload, tor_addr_to_ipv4n(&hop->extend_info->addr));
  1777. set_uint16(payload+4, htons(hop->extend_info->port));
  1778. onionskin = payload+2+4;
  1779. memcpy(payload+2+4+ONIONSKIN_CHALLENGE_LEN,
  1780. hop->extend_info->identity_digest, DIGEST_LEN);
  1781. payload_len = 2+4+ONIONSKIN_CHALLENGE_LEN+DIGEST_LEN;
  1782. if (onion_skin_create(hop->extend_info->onion_key,
  1783. &(hop->dh_handshake_state), onionskin) < 0) {
  1784. log_warn(LD_CIRC,"onion_skin_create failed.");
  1785. return - END_CIRC_REASON_INTERNAL;
  1786. }
  1787. log_info(LD_CIRC,"Sending extend relay cell.");
  1788. note_request("cell: extend", 1);
  1789. /* send it to hop->prev, because it will transfer
  1790. * it to a create cell and then send to hop */
  1791. if (relay_send_command_from_edge(0, TO_CIRCUIT(circ),
  1792. RELAY_COMMAND_EXTEND,
  1793. payload, payload_len, hop->prev) < 0)
  1794. return 0; /* circuit is closed */
  1795. hop->state = CPATH_STATE_AWAITING_KEYS;
  1796. }
  1797. return 0;
  1798. }
  1799. /** Our clock just jumped by <b>seconds_elapsed</b>. Assume
  1800. * something has also gone wrong with our network: notify the user,
  1801. * and abandon all not-yet-used circuits. */
  1802. void
  1803. circuit_note_clock_jumped(int seconds_elapsed)
  1804. {
  1805. int severity = server_mode(get_options()) ? LOG_WARN : LOG_NOTICE;
  1806. tor_log(severity, LD_GENERAL, "Your system clock just jumped %d seconds %s; "
  1807. "assuming established circuits no longer work.",
  1808. seconds_elapsed >=0 ? seconds_elapsed : -seconds_elapsed,
  1809. seconds_elapsed >=0 ? "forward" : "backward");
  1810. control_event_general_status(LOG_WARN, "CLOCK_JUMPED TIME=%d",
  1811. seconds_elapsed);
  1812. can_complete_circuit=0; /* so it'll log when it works again */
  1813. control_event_client_status(severity, "CIRCUIT_NOT_ESTABLISHED REASON=%s",
  1814. "CLOCK_JUMPED");
  1815. circuit_mark_all_unused_circs();
  1816. circuit_expire_all_dirty_circs();
  1817. }
  1818. /** Take the 'extend' <b>cell</b>, pull out addr/port plus the onion
  1819. * skin and identity digest for the next hop. If we're already connected,
  1820. * pass the onion skin to the next hop using a create cell; otherwise
  1821. * launch a new OR connection, and <b>circ</b> will notice when the
  1822. * connection succeeds or fails.
  1823. *
  1824. * Return -1 if we want to warn and tear down the circuit, else return 0.
  1825. */
  1826. int
  1827. circuit_extend(cell_t *cell, circuit_t *circ)
  1828. {
  1829. or_connection_t *n_conn;
  1830. relay_header_t rh;
  1831. char *onionskin;
  1832. char *id_digest=NULL;
  1833. uint32_t n_addr32;
  1834. uint16_t n_port;
  1835. tor_addr_t n_addr;
  1836. const char *msg = NULL;
  1837. int should_launch = 0;
  1838. if (circ->n_conn) {
  1839. log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
  1840. "n_conn already set. Bug/attack. Closing.");
  1841. return -1;
  1842. }
  1843. if (circ->n_hop) {
  1844. log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
  1845. "conn to next hop already launched. Bug/attack. Closing.");
  1846. return -1;
  1847. }
  1848. if (!server_mode(get_options())) {
  1849. log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
  1850. "Got an extend cell, but running as a client. Closing.");
  1851. return -1;
  1852. }
  1853. relay_header_unpack(&rh, cell->payload);
  1854. if (rh.length < 4+2+ONIONSKIN_CHALLENGE_LEN+DIGEST_LEN) {
  1855. log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
  1856. "Wrong length %d on extend cell. Closing circuit.",
  1857. rh.length);
  1858. return -1;
  1859. }
  1860. n_addr32 = ntohl(get_uint32(cell->payload+RELAY_HEADER_SIZE));
  1861. n_port = ntohs(get_uint16(cell->payload+RELAY_HEADER_SIZE+4));
  1862. onionskin = (char*) cell->payload+RELAY_HEADER_SIZE+4+2;
  1863. id_digest = (char*) cell->payload+RELAY_HEADER_SIZE+4+2+
  1864. ONIONSKIN_CHALLENGE_LEN;
  1865. tor_addr_from_ipv4h(&n_addr, n_addr32);
  1866. if (!n_port || !n_addr32) {
  1867. log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
  1868. "Client asked me to extend to zero destination port or addr.");
  1869. return -1;
  1870. }
  1871. /* Check if they asked us for 0000..0000. We support using
  1872. * an empty fingerprint for the first hop (e.g. for a bridge relay),
  1873. * but we don't want to let people send us extend cells for empty
  1874. * fingerprints -- a) because it opens the user up to a mitm attack,
  1875. * and b) because it lets an attacker force the relay to hold open a
  1876. * new TLS connection for each extend request. */
  1877. if (tor_digest_is_zero(id_digest)) {
  1878. log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
  1879. "Client asked me to extend without specifying an id_digest.");
  1880. return -1;
  1881. }
  1882. /* Next, check if we're being asked to connect to the hop that the
  1883. * extend cell came from. There isn't any reason for that, and it can
  1884. * assist circular-path attacks. */
  1885. if (!memcmp(id_digest, TO_OR_CIRCUIT(circ)->p_conn->identity_digest,
  1886. DIGEST_LEN)) {
  1887. log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
  1888. "Client asked me to extend back to the previous hop.");
  1889. return -1;
  1890. }
  1891. n_conn = connection_or_get_for_extend(id_digest,
  1892. &n_addr,
  1893. &msg,
  1894. &should_launch);
  1895. if (!n_conn) {
  1896. log_debug(LD_CIRC|LD_OR,"Next router (%s:%d): %s",
  1897. fmt_addr(&n_addr), (int)n_port, msg?msg:"????");
  1898. circ->n_hop = extend_info_alloc(NULL /*nickname*/,
  1899. id_digest,
  1900. NULL /*onion_key*/,
  1901. &n_addr, n_port);
  1902. circ->n_conn_onionskin = tor_malloc(ONIONSKIN_CHALLENGE_LEN);
  1903. memcpy(circ->n_conn_onionskin, onionskin, ONIONSKIN_CHALLENGE_LEN);
  1904. circuit_set_state(circ, CIRCUIT_STATE_OR_WAIT);
  1905. if (should_launch) {
  1906. /* we should try to open a connection */
  1907. n_conn = connection_or_connect(&n_addr, n_port, id_digest);
  1908. if (!n_conn) {
  1909. log_info(LD_CIRC,"Launching n_conn failed. Closing circuit.");
  1910. circuit_mark_for_close(circ, END_CIRC_REASON_CONNECTFAILED);
  1911. return 0;
  1912. }
  1913. log_debug(LD_CIRC,"connecting in progress (or finished). Good.");
  1914. }
  1915. /* return success. The onion/circuit/etc will be taken care of
  1916. * automatically (may already have been) whenever n_conn reaches
  1917. * OR_CONN_STATE_OPEN.
  1918. */
  1919. return 0;
  1920. }
  1921. tor_assert(!circ->n_hop); /* Connection is already established. */
  1922. circ->n_conn = n_conn;
  1923. log_debug(LD_CIRC,"n_conn is %s:%u",
  1924. n_conn->_base.address,n_conn->_base.port);
  1925. if (circuit_deliver_create_cell(circ, CELL_CREATE, onionskin) < 0)
  1926. return -1;
  1927. return 0;
  1928. }
  1929. /** Initialize cpath-\>{f|b}_{crypto|digest} from the key material in
  1930. * key_data. key_data must contain CPATH_KEY_MATERIAL bytes, which are
  1931. * used as follows:
  1932. * - 20 to initialize f_digest
  1933. * - 20 to initialize b_digest
  1934. * - 16 to key f_crypto
  1935. * - 16 to key b_crypto
  1936. *
  1937. * (If 'reverse' is true, then f_XX and b_XX are swapped.)
  1938. */
  1939. int
  1940. circuit_init_cpath_crypto(crypt_path_t *cpath, const char *key_data,
  1941. int reverse)
  1942. {
  1943. crypto_digest_env_t *tmp_digest;
  1944. crypto_cipher_env_t *tmp_crypto;
  1945. tor_assert(cpath);
  1946. tor_assert(key_data);
  1947. tor_assert(!(cpath->f_crypto || cpath->b_crypto ||
  1948. cpath->f_digest || cpath->b_digest));
  1949. cpath->f_digest = crypto_new_digest_env();
  1950. crypto_digest_add_bytes(cpath->f_digest, key_data, DIGEST_LEN);
  1951. cpath->b_digest = crypto_new_digest_env();
  1952. crypto_digest_add_bytes(cpath->b_digest, key_data+DIGEST_LEN, DIGEST_LEN);
  1953. if (!(cpath->f_crypto =
  1954. crypto_create_init_cipher(key_data+(2*DIGEST_LEN),1))) {
  1955. log_warn(LD_BUG,"Forward cipher initialization failed.");
  1956. return -1;
  1957. }
  1958. if (!(cpath->b_crypto =
  1959. crypto_create_init_cipher(key_data+(2*DIGEST_LEN)+CIPHER_KEY_LEN,0))) {
  1960. log_warn(LD_BUG,"Backward cipher initialization failed.");
  1961. return -1;
  1962. }
  1963. if (reverse) {
  1964. tmp_digest = cpath->f_digest;
  1965. cpath->f_digest = cpath->b_digest;
  1966. cpath->b_digest = tmp_digest;
  1967. tmp_crypto = cpath->f_crypto;
  1968. cpath->f_crypto = cpath->b_crypto;
  1969. cpath->b_crypto = tmp_crypto;
  1970. }
  1971. return 0;
  1972. }
  1973. /** A created or extended cell came back to us on the circuit, and it included
  1974. * <b>reply</b> as its body. (If <b>reply_type</b> is CELL_CREATED, the body
  1975. * contains (the second DH key, plus KH). If <b>reply_type</b> is
  1976. * CELL_CREATED_FAST, the body contains a secret y and a hash H(x|y).)
  1977. *
  1978. * Calculate the appropriate keys and digests, make sure KH is
  1979. * correct, and initialize this hop of the cpath.
  1980. *
  1981. * Return - reason if we want to mark circ for close, else return 0.
  1982. */
  1983. int
  1984. circuit_finish_handshake(origin_circuit_t *circ, uint8_t reply_type,
  1985. const uint8_t *reply)
  1986. {
  1987. char keys[CPATH_KEY_MATERIAL_LEN];
  1988. crypt_path_t *hop;
  1989. if (circ->cpath->state == CPATH_STATE_AWAITING_KEYS)
  1990. hop = circ->cpath;
  1991. else {
  1992. hop = onion_next_hop_in_cpath(circ->cpath);
  1993. if (!hop) { /* got an extended when we're all done? */
  1994. log_warn(LD_PROTOCOL,"got extended when circ already built? Closing.");
  1995. return - END_CIRC_REASON_TORPROTOCOL;
  1996. }
  1997. }
  1998. tor_assert(hop->state == CPATH_STATE_AWAITING_KEYS);
  1999. if (reply_type == CELL_CREATED && hop->dh_handshake_state) {
  2000. if (onion_skin_client_handshake(hop->dh_handshake_state, (char*)reply,keys,
  2001. DIGEST_LEN*2+CIPHER_KEY_LEN*2) < 0) {
  2002. log_warn(LD_CIRC,"onion_skin_client_handshake failed.");
  2003. return -END_CIRC_REASON_TORPROTOCOL;
  2004. }
  2005. /* Remember hash of g^xy */
  2006. memcpy(hop->handshake_digest, reply+DH_KEY_LEN, DIGEST_LEN);
  2007. } else if (reply_type == CELL_CREATED_FAST && !hop->dh_handshake_state) {
  2008. if (fast_client_handshake(hop->fast_handshake_state, reply,
  2009. (uint8_t*)keys,
  2010. DIGEST_LEN*2+CIPHER_KEY_LEN*2) < 0) {
  2011. log_warn(LD_CIRC,"fast_client_handshake failed.");
  2012. return -END_CIRC_REASON_TORPROTOCOL;
  2013. }
  2014. memcpy(hop->handshake_digest, reply+DIGEST_LEN, DIGEST_LEN);
  2015. } else {
  2016. log_warn(LD_PROTOCOL,"CREATED cell type did not match CREATE cell type.");
  2017. return -END_CIRC_REASON_TORPROTOCOL;
  2018. }
  2019. crypto_dh_free(hop->dh_handshake_state); /* don't need it anymore */
  2020. hop->dh_handshake_state = NULL;
  2021. memset(hop->fast_handshake_state, 0, sizeof(hop->fast_handshake_state));
  2022. if (circuit_init_cpath_crypto(hop, keys, 0)<0) {
  2023. return -END_CIRC_REASON_TORPROTOCOL;
  2024. }
  2025. hop->state = CPATH_STATE_OPEN;
  2026. log_info(LD_CIRC,"Finished building %scircuit hop:",
  2027. (reply_type == CELL_CREATED_FAST) ? "fast " : "");
  2028. circuit_log_path(LOG_INFO,LD_CIRC,circ);
  2029. control_event_circuit_status(circ, CIRC_EVENT_EXTENDED, 0);
  2030. return 0;
  2031. }
  2032. /** We received a relay truncated cell on circ.
  2033. *
  2034. * Since we don't ask for truncates currently, getting a truncated
  2035. * means that a connection broke or an extend failed. For now,
  2036. * just give up: for circ to close, and return 0.
  2037. */
  2038. int
  2039. circuit_truncated(origin_circuit_t *circ, crypt_path_t *layer)
  2040. {
  2041. // crypt_path_t *victim;
  2042. // connection_t *stream;
  2043. tor_assert(circ);
  2044. tor_assert(layer);
  2045. /* XXX Since we don't ask for truncates currently, getting a truncated
  2046. * means that a connection broke or an extend failed. For now,
  2047. * just give up.
  2048. */
  2049. circuit_mark_for_close(TO_CIRCUIT(circ),
  2050. END_CIRC_REASON_FLAG_REMOTE|END_CIRC_REASON_OR_CONN_CLOSED);
  2051. return 0;
  2052. #if 0
  2053. while (layer->next != circ->cpath) {
  2054. /* we need to clear out layer->next */
  2055. victim = layer->next;
  2056. log_debug(LD_CIRC, "Killing a layer of the cpath.");
  2057. for (stream = circ->p_streams; stream; stream=stream->next_stream) {
  2058. if (stream->cpath_layer == victim) {
  2059. log_info(LD_APP, "Marking stream %d for close because of truncate.",
  2060. stream->stream_id);
  2061. /* no need to send 'end' relay cells,
  2062. * because the other side's already dead
  2063. */
  2064. connection_mark_unattached_ap(stream, END_STREAM_REASON_DESTROY);
  2065. }
  2066. }
  2067. layer->next = victim->next;
  2068. circuit_free_cpath_node(victim);
  2069. }
  2070. log_info(LD_CIRC, "finished");
  2071. return 0;
  2072. #endif
  2073. }
  2074. /** Given a response payload and keys, initialize, then send a created
  2075. * cell back.
  2076. */
  2077. int
  2078. onionskin_answer(or_circuit_t *circ, uint8_t cell_type, const char *payload,
  2079. const char *keys)
  2080. {
  2081. cell_t cell;
  2082. crypt_path_t *tmp_cpath;
  2083. tmp_cpath = tor_malloc_zero(sizeof(crypt_path_t));
  2084. tmp_cpath->magic = CRYPT_PATH_MAGIC;
  2085. memset(&cell, 0, sizeof(cell_t));
  2086. cell.command = cell_type;
  2087. cell.circ_id = circ->p_circ_id;
  2088. circuit_set_state(TO_CIRCUIT(circ), CIRCUIT_STATE_OPEN);
  2089. memcpy(cell.payload, payload,
  2090. cell_type == CELL_CREATED ? ONIONSKIN_REPLY_LEN : DIGEST_LEN*2);
  2091. log_debug(LD_CIRC,"init digest forward 0x%.8x, backward 0x%.8x.",
  2092. (unsigned int)get_uint32(keys),
  2093. (unsigned int)get_uint32(keys+20));
  2094. if (circuit_init_cpath_crypto(tmp_cpath, keys, 0)<0) {
  2095. log_warn(LD_BUG,"Circuit initialization failed");
  2096. tor_free(tmp_cpath);
  2097. return -1;
  2098. }
  2099. circ->n_digest = tmp_cpath->f_digest;
  2100. circ->n_crypto = tmp_cpath->f_crypto;
  2101. circ->p_digest = tmp_cpath->b_digest;
  2102. circ->p_crypto = tmp_cpath->b_crypto;
  2103. tmp_cpath->magic = 0;
  2104. tor_free(tmp_cpath);
  2105. if (cell_type == CELL_CREATED)
  2106. memcpy(circ->handshake_digest, cell.payload+DH_KEY_LEN, DIGEST_LEN);
  2107. else
  2108. memcpy(circ->handshake_digest, cell.payload+DIGEST_LEN, DIGEST_LEN);
  2109. circ->is_first_hop = (cell_type == CELL_CREATED_FAST);
  2110. append_cell_to_circuit_queue(TO_CIRCUIT(circ),
  2111. circ->p_conn, &cell, CELL_DIRECTION_IN, 0);
  2112. log_debug(LD_CIRC,"Finished sending 'created' cell.");
  2113. if (!is_local_addr(&circ->p_conn->_base.addr) &&
  2114. !connection_or_nonopen_was_started_here(circ->p_conn)) {
  2115. /* record that we could process create cells from a non-local conn
  2116. * that we didn't initiate; presumably this means that create cells
  2117. * can reach us too. */
  2118. router_orport_found_reachable();
  2119. }
  2120. return 0;
  2121. }
  2122. /** Choose a length for a circuit of purpose <b>purpose</b>.
  2123. * Default length is 3 + the number of endpoints that would give something
  2124. * away. If the routerlist <b>routers</b> doesn't have enough routers
  2125. * to handle the desired path length, return as large a path length as
  2126. * is feasible, except if it's less than 2, in which case return -1.
  2127. */
  2128. static int
  2129. new_route_len(uint8_t purpose, extend_info_t *exit,
  2130. smartlist_t *routers)
  2131. {
  2132. int num_acceptable_routers;
  2133. int routelen;
  2134. tor_assert(routers);
  2135. routelen = DEFAULT_ROUTE_LEN;
  2136. if (exit &&
  2137. purpose != CIRCUIT_PURPOSE_TESTING &&
  2138. purpose != CIRCUIT_PURPOSE_S_ESTABLISH_INTRO)
  2139. routelen++;
  2140. num_acceptable_routers = count_acceptable_routers(routers);
  2141. log_debug(LD_CIRC,"Chosen route length %d (%d/%d routers suitable).",
  2142. routelen, num_acceptable_routers, smartlist_len(routers));
  2143. if (num_acceptable_routers < 2) {
  2144. log_info(LD_CIRC,
  2145. "Not enough acceptable routers (%d). Discarding this circuit.",
  2146. num_acceptable_routers);
  2147. return -1;
  2148. }
  2149. if (num_acceptable_routers < routelen) {
  2150. log_info(LD_CIRC,"Not enough routers: cutting routelen from %d to %d.",
  2151. routelen, num_acceptable_routers);
  2152. routelen = num_acceptable_routers;
  2153. }
  2154. return routelen;
  2155. }
  2156. /** Fetch the list of predicted ports, dup it into a smartlist of
  2157. * uint16_t's, remove the ones that are already handled by an
  2158. * existing circuit, and return it.
  2159. */
  2160. static smartlist_t *
  2161. circuit_get_unhandled_ports(time_t now)
  2162. {
  2163. smartlist_t *source = rep_hist_get_predicted_ports(now);
  2164. smartlist_t *dest = smartlist_create();
  2165. uint16_t *tmp;
  2166. int i;
  2167. for (i = 0; i < smartlist_len(source); ++i) {
  2168. tmp = tor_malloc(sizeof(uint16_t));
  2169. memcpy(tmp, smartlist_get(source, i), sizeof(uint16_t));
  2170. smartlist_add(dest, tmp);
  2171. }
  2172. circuit_remove_handled_ports(dest);
  2173. return dest;
  2174. }
  2175. /** Return 1 if we already have circuits present or on the way for
  2176. * all anticipated ports. Return 0 if we should make more.
  2177. *
  2178. * If we're returning 0, set need_uptime and need_capacity to
  2179. * indicate any requirements that the unhandled ports have.
  2180. */
  2181. int
  2182. circuit_all_predicted_ports_handled(time_t now, int *need_uptime,
  2183. int *need_capacity)
  2184. {
  2185. int i, enough;
  2186. uint16_t *port;
  2187. smartlist_t *sl = circuit_get_unhandled_ports(now);
  2188. smartlist_t *LongLivedServices = get_options()->LongLivedPorts;
  2189. tor_assert(need_uptime);
  2190. tor_assert(need_capacity);
  2191. // Always predict need_capacity
  2192. *need_capacity = 1;
  2193. enough = (smartlist_len(sl) == 0);
  2194. for (i = 0; i < smartlist_len(sl); ++i) {
  2195. port = smartlist_get(sl, i);
  2196. if (smartlist_string_num_isin(LongLivedServices, *port))
  2197. *need_uptime = 1;
  2198. tor_free(port);
  2199. }
  2200. smartlist_free(sl);
  2201. return enough;
  2202. }
  2203. /** Return 1 if <b>router</b> can handle one or more of the ports in
  2204. * <b>needed_ports</b>, else return 0.
  2205. */
  2206. static int
  2207. router_handles_some_port(routerinfo_t *router, smartlist_t *needed_ports)
  2208. {
  2209. int i;
  2210. uint16_t port;
  2211. for (i = 0; i < smartlist_len(needed_ports); ++i) {
  2212. addr_policy_result_t r;
  2213. /* alignment issues aren't a worry for this dereference, since
  2214. needed_ports is explicitly a smartlist of uint16_t's */
  2215. port = *(uint16_t *)smartlist_get(needed_ports, i);
  2216. tor_assert(port);
  2217. r = compare_addr_to_addr_policy(0, port, router->exit_policy);
  2218. if (r != ADDR_POLICY_REJECTED && r != ADDR_POLICY_PROBABLY_REJECTED)
  2219. return 1;
  2220. }
  2221. return 0;
  2222. }
  2223. /** Return true iff <b>conn</b> needs another general circuit to be
  2224. * built. */
  2225. static int
  2226. ap_stream_wants_exit_attention(connection_t *conn)
  2227. {
  2228. if (conn->type == CONN_TYPE_AP &&
  2229. conn->state == AP_CONN_STATE_CIRCUIT_WAIT &&
  2230. !conn->marked_for_close &&
  2231. !(TO_EDGE_CONN(conn)->want_onehop) && /* ignore one-hop streams */
  2232. !(TO_EDGE_CONN(conn)->use_begindir) && /* ignore targeted dir fetches */
  2233. !(TO_EDGE_CONN(conn)->chosen_exit_name) && /* ignore defined streams */
  2234. !connection_edge_is_rendezvous_stream(TO_EDGE_CONN(conn)) &&
  2235. !circuit_stream_is_being_handled(TO_EDGE_CONN(conn), 0,
  2236. MIN_CIRCUITS_HANDLING_STREAM))
  2237. return 1;
  2238. return 0;
  2239. }
  2240. /** Return a pointer to a suitable router to be the exit node for the
  2241. * general-purpose circuit we're about to build.
  2242. *
  2243. * Look through the connection array, and choose a router that maximizes
  2244. * the number of pending streams that can exit from this router.
  2245. *
  2246. * Return NULL if we can't find any suitable routers.
  2247. */
  2248. static routerinfo_t *
  2249. choose_good_exit_server_general(routerlist_t *dir, int need_uptime,
  2250. int need_capacity)
  2251. {
  2252. int *n_supported;
  2253. int i;
  2254. int n_pending_connections = 0;
  2255. smartlist_t *connections;
  2256. int best_support = -1;
  2257. int n_best_support=0;
  2258. routerinfo_t *router;
  2259. or_options_t *options = get_options();
  2260. connections = get_connection_array();
  2261. /* Count how many connections are waiting for a circuit to be built.
  2262. * We use this for log messages now, but in the future we may depend on it.
  2263. */
  2264. SMARTLIST_FOREACH(connections, connection_t *, conn,
  2265. {
  2266. if (ap_stream_wants_exit_attention(conn))
  2267. ++n_pending_connections;
  2268. });
  2269. // log_fn(LOG_DEBUG, "Choosing exit node; %d connections are pending",
  2270. // n_pending_connections);
  2271. /* Now we count, for each of the routers in the directory, how many
  2272. * of the pending connections could possibly exit from that
  2273. * router (n_supported[i]). (We can't be sure about cases where we
  2274. * don't know the IP address of the pending connection.)
  2275. *
  2276. * -1 means "Don't use this router at all."
  2277. */
  2278. n_supported = tor_malloc(sizeof(int)*smartlist_len(dir->routers));
  2279. for (i = 0; i < smartlist_len(dir->routers); ++i) {/* iterate over routers */
  2280. router = smartlist_get(dir->routers, i);
  2281. if (router_is_me(router)) {
  2282. n_supported[i] = -1;
  2283. // log_fn(LOG_DEBUG,"Skipping node %s -- it's me.", router->nickname);
  2284. /* XXX there's probably a reverse predecessor attack here, but
  2285. * it's slow. should we take this out? -RD
  2286. */
  2287. continue;
  2288. }
  2289. if (!router->is_running || router->is_bad_exit) {
  2290. n_supported[i] = -1;
  2291. continue; /* skip routers that are known to be down or bad exits */
  2292. }
  2293. if (router_is_unreliable(router, need_uptime, need_capacity, 0) &&
  2294. (!options->ExitNodes ||
  2295. !routerset_contains_router(options->ExitNodes, router))) {
  2296. /* FFFF Someday, differentiate between a routerset that names
  2297. * routers, and a routerset that names countries, and only do this
  2298. * check if they've asked for specific exit relays. Or if the country
  2299. * they ask for is rare. Or something. */
  2300. n_supported[i] = -1;
  2301. continue; /* skip routers that are not suitable, unless we have
  2302. * ExitNodes set, in which case we asked for it */
  2303. }
  2304. if (!(router->is_valid || options->_AllowInvalid & ALLOW_INVALID_EXIT)) {
  2305. /* if it's invalid and we don't want it */
  2306. n_supported[i] = -1;
  2307. // log_fn(LOG_DEBUG,"Skipping node %s (index %d) -- invalid router.",
  2308. // router->nickname, i);
  2309. continue; /* skip invalid routers */
  2310. }
  2311. if (options->ExcludeSingleHopRelays && router->allow_single_hop_exits) {
  2312. n_supported[i] = -1;
  2313. continue;
  2314. }
  2315. if (router_exit_policy_rejects_all(router)) {
  2316. n_supported[i] = -1;
  2317. // log_fn(LOG_DEBUG,"Skipping node %s (index %d) -- it rejects all.",
  2318. // router->nickname, i);
  2319. continue; /* skip routers that reject all */
  2320. }
  2321. n_supported[i] = 0;
  2322. /* iterate over connections */
  2323. SMARTLIST_FOREACH(connections, connection_t *, conn,
  2324. {
  2325. if (!ap_stream_wants_exit_attention(conn))
  2326. continue; /* Skip everything but APs in CIRCUIT_WAIT */
  2327. if (connection_ap_can_use_exit(TO_EDGE_CONN(conn), router, 1)) {
  2328. ++n_supported[i];
  2329. // log_fn(LOG_DEBUG,"%s is supported. n_supported[%d] now %d.",
  2330. // router->nickname, i, n_supported[i]);
  2331. } else {
  2332. // log_fn(LOG_DEBUG,"%s (index %d) would reject this stream.",
  2333. // router->nickname, i);
  2334. }
  2335. }); /* End looping over connections. */
  2336. if (n_pending_connections > 0 && n_supported[i] == 0) {
  2337. /* Leave best_support at -1 if that's where it is, so we can
  2338. * distinguish it later. */
  2339. continue;
  2340. }
  2341. if (n_supported[i] > best_support) {
  2342. /* If this router is better than previous ones, remember its index
  2343. * and goodness, and start counting how many routers are this good. */
  2344. best_support = n_supported[i]; n_best_support=1;
  2345. // log_fn(LOG_DEBUG,"%s is new best supported option so far.",
  2346. // router->nickname);
  2347. } else if (n_supported[i] == best_support) {
  2348. /* If this router is _as good_ as the best one, just increment the
  2349. * count of equally good routers.*/
  2350. ++n_best_support;
  2351. }
  2352. }
  2353. log_info(LD_CIRC,
  2354. "Found %d servers that might support %d/%d pending connections.",
  2355. n_best_support, best_support >= 0 ? best_support : 0,
  2356. n_pending_connections);
  2357. /* If any routers definitely support any pending connections, choose one
  2358. * at random. */
  2359. if (best_support > 0) {
  2360. smartlist_t *supporting = smartlist_create(), *use = smartlist_create();
  2361. for (i = 0; i < smartlist_len(dir->routers); i++)
  2362. if (n_supported[i] == best_support)
  2363. smartlist_add(supporting, smartlist_get(dir->routers, i));
  2364. routersets_get_disjunction(use, supporting, options->ExitNodes,
  2365. options->_ExcludeExitNodesUnion, 1);
  2366. if (smartlist_len(use) == 0 && options->ExitNodes &&
  2367. !options->StrictNodes) { /* give up on exitnodes and try again */
  2368. routersets_get_disjunction(use, supporting, NULL,
  2369. options->_ExcludeExitNodesUnion, 1);
  2370. }
  2371. router = routerlist_sl_choose_by_bandwidth(use, WEIGHT_FOR_EXIT);
  2372. smartlist_free(use);
  2373. smartlist_free(supporting);
  2374. } else {
  2375. /* Either there are no pending connections, or no routers even seem to
  2376. * possibly support any of them. Choose a router at random that satisfies
  2377. * at least one predicted exit port. */
  2378. int attempt;
  2379. smartlist_t *needed_ports, *supporting, *use;
  2380. if (best_support == -1) {
  2381. if (need_uptime || need_capacity) {
  2382. log_info(LD_CIRC,
  2383. "We couldn't find any live%s%s routers; falling back "
  2384. "to list of all routers.",
  2385. need_capacity?", fast":"",
  2386. need_uptime?", stable":"");
  2387. tor_free(n_supported);
  2388. return choose_good_exit_server_general(dir, 0, 0);
  2389. }
  2390. log_notice(LD_CIRC, "All routers are down or won't exit%s -- "
  2391. "choosing a doomed exit at random.",
  2392. options->_ExcludeExitNodesUnion ? " or are Excluded" : "");
  2393. }
  2394. supporting = smartlist_create();
  2395. use = smartlist_create();
  2396. needed_ports = circuit_get_unhandled_ports(time(NULL));
  2397. for (attempt = 0; attempt < 2; attempt++) {
  2398. /* try once to pick only from routers that satisfy a needed port,
  2399. * then if there are none, pick from any that support exiting. */
  2400. for (i = 0; i < smartlist_len(dir->routers); i++) {
  2401. router = smartlist_get(dir->routers, i);
  2402. if (n_supported[i] != -1 &&
  2403. (attempt || router_handles_some_port(router, needed_ports))) {
  2404. // log_fn(LOG_DEBUG,"Try %d: '%s' is a possibility.",
  2405. // try, router->nickname);
  2406. smartlist_add(supporting, router);
  2407. }
  2408. }
  2409. routersets_get_disjunction(use, supporting, options->ExitNodes,
  2410. options->_ExcludeExitNodesUnion, 1);
  2411. if (smartlist_len(use) == 0 && options->ExitNodes &&
  2412. !options->StrictNodes) { /* give up on exitnodes and try again */
  2413. routersets_get_disjunction(use, supporting, NULL,
  2414. options->_ExcludeExitNodesUnion, 1);
  2415. }
  2416. /* FFF sometimes the above results in null, when the requested
  2417. * exit node is considered down by the consensus. we should pick
  2418. * it anyway, since the user asked for it. */
  2419. router = routerlist_sl_choose_by_bandwidth(use, WEIGHT_FOR_EXIT);
  2420. if (router)
  2421. break;
  2422. smartlist_clear(supporting);
  2423. smartlist_clear(use);
  2424. }
  2425. SMARTLIST_FOREACH(needed_ports, uint16_t *, cp, tor_free(cp));
  2426. smartlist_free(needed_ports);
  2427. smartlist_free(use);
  2428. smartlist_free(supporting);
  2429. }
  2430. tor_free(n_supported);
  2431. if (router) {
  2432. log_info(LD_CIRC, "Chose exit server '%s'", router->nickname);
  2433. return router;
  2434. }
  2435. if (options->ExitNodes && options->StrictNodes) {
  2436. log_warn(LD_CIRC,
  2437. "No specified exit routers seem to be running, and "
  2438. "StrictNodes is set: can't choose an exit.");
  2439. }
  2440. return NULL;
  2441. }
  2442. /** Return a pointer to a suitable router to be the exit node for the
  2443. * circuit of purpose <b>purpose</b> that we're about to build (or NULL
  2444. * if no router is suitable).
  2445. *
  2446. * For general-purpose circuits, pass it off to
  2447. * choose_good_exit_server_general()
  2448. *
  2449. * For client-side rendezvous circuits, choose a random node, weighted
  2450. * toward the preferences in 'options'.
  2451. */
  2452. static routerinfo_t *
  2453. choose_good_exit_server(uint8_t purpose, routerlist_t *dir,
  2454. int need_uptime, int need_capacity, int is_internal)
  2455. {
  2456. or_options_t *options = get_options();
  2457. router_crn_flags_t flags = 0;
  2458. if (need_uptime)
  2459. flags |= CRN_NEED_UPTIME;
  2460. if (need_capacity)
  2461. flags |= CRN_NEED_CAPACITY;
  2462. switch (purpose) {
  2463. case CIRCUIT_PURPOSE_C_GENERAL:
  2464. if (options->_AllowInvalid & ALLOW_INVALID_MIDDLE)
  2465. flags |= CRN_ALLOW_INVALID;
  2466. if (is_internal) /* pick it like a middle hop */
  2467. return router_choose_random_node(NULL, options->ExcludeNodes, flags);
  2468. else
  2469. return choose_good_exit_server_general(dir,need_uptime,need_capacity);
  2470. case CIRCUIT_PURPOSE_C_ESTABLISH_REND:
  2471. if (options->_AllowInvalid & ALLOW_INVALID_RENDEZVOUS)
  2472. flags |= CRN_ALLOW_INVALID;
  2473. return router_choose_random_node(NULL, options->ExcludeNodes, flags);
  2474. }
  2475. log_warn(LD_BUG,"Unhandled purpose %d", purpose);
  2476. tor_fragile_assert();
  2477. return NULL;
  2478. }
  2479. /** Log a warning if the user specified an exit for the circuit that
  2480. * has been excluded from use by ExcludeNodes or ExcludeExitNodes. */
  2481. static void
  2482. warn_if_last_router_excluded(origin_circuit_t *circ, const extend_info_t *exit)
  2483. {
  2484. or_options_t *options = get_options();
  2485. routerset_t *rs = options->ExcludeNodes;
  2486. const char *description;
  2487. int domain = LD_CIRC;
  2488. uint8_t purpose = circ->_base.purpose;
  2489. if (circ->build_state->onehop_tunnel)
  2490. return;
  2491. switch (purpose)
  2492. {
  2493. default:
  2494. case CIRCUIT_PURPOSE_OR:
  2495. case CIRCUIT_PURPOSE_INTRO_POINT:
  2496. case CIRCUIT_PURPOSE_REND_POINT_WAITING:
  2497. case CIRCUIT_PURPOSE_REND_ESTABLISHED:
  2498. log_warn(LD_BUG, "Called on non-origin circuit (purpose %d)",
  2499. (int)purpose);
  2500. return;
  2501. case CIRCUIT_PURPOSE_C_GENERAL:
  2502. if (circ->build_state->is_internal)
  2503. return;
  2504. description = "Requested exit node";
  2505. rs = options->_ExcludeExitNodesUnion;
  2506. break;
  2507. case CIRCUIT_PURPOSE_C_INTRODUCING:
  2508. case CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT:
  2509. case CIRCUIT_PURPOSE_C_INTRODUCE_ACKED:
  2510. case CIRCUIT_PURPOSE_S_ESTABLISH_INTRO:
  2511. case CIRCUIT_PURPOSE_S_CONNECT_REND:
  2512. case CIRCUIT_PURPOSE_S_REND_JOINED:
  2513. case CIRCUIT_PURPOSE_TESTING:
  2514. return;
  2515. case CIRCUIT_PURPOSE_C_ESTABLISH_REND:
  2516. case CIRCUIT_PURPOSE_C_REND_READY:
  2517. case CIRCUIT_PURPOSE_C_REND_READY_INTRO_ACKED:
  2518. case CIRCUIT_PURPOSE_C_REND_JOINED:
  2519. description = "Chosen rendezvous point";
  2520. domain = LD_BUG;
  2521. break;
  2522. case CIRCUIT_PURPOSE_CONTROLLER:
  2523. rs = options->_ExcludeExitNodesUnion;
  2524. description = "Controller-selected circuit target";
  2525. break;
  2526. }
  2527. if (routerset_contains_extendinfo(rs, exit)) {
  2528. log_fn(LOG_WARN, domain, "%s '%s' is in ExcludeNodes%s. Using anyway "
  2529. "(circuit purpose %d).",
  2530. description,exit->nickname,
  2531. rs==options->ExcludeNodes?"":" or ExcludeExitNodes",
  2532. (int)purpose);
  2533. circuit_log_path(LOG_WARN, domain, circ);
  2534. }
  2535. return;
  2536. }
  2537. /** Decide a suitable length for circ's cpath, and pick an exit
  2538. * router (or use <b>exit</b> if provided). Store these in the
  2539. * cpath. Return 0 if ok, -1 if circuit should be closed. */
  2540. static int
  2541. onion_pick_cpath_exit(origin_circuit_t *circ, extend_info_t *exit)
  2542. {
  2543. cpath_build_state_t *state = circ->build_state;
  2544. routerlist_t *rl = router_get_routerlist();
  2545. if (state->onehop_tunnel) {
  2546. log_debug(LD_CIRC, "Launching a one-hop circuit for dir tunnel.");
  2547. state->desired_path_len = 1;
  2548. } else {
  2549. int r = new_route_len(circ->_base.purpose, exit, rl->routers);
  2550. if (r < 1) /* must be at least 1 */
  2551. return -1;
  2552. state->desired_path_len = r;
  2553. }
  2554. if (exit) { /* the circuit-builder pre-requested one */
  2555. warn_if_last_router_excluded(circ, exit);
  2556. log_info(LD_CIRC,"Using requested exit node '%s'", exit->nickname);
  2557. exit = extend_info_dup(exit);
  2558. } else { /* we have to decide one */
  2559. routerinfo_t *router =
  2560. choose_good_exit_server(circ->_base.purpose, rl, state->need_uptime,
  2561. state->need_capacity, state->is_internal);
  2562. if (!router) {
  2563. log_warn(LD_CIRC,"failed to choose an exit server");
  2564. return -1;
  2565. }
  2566. exit = extend_info_from_router(router);
  2567. }
  2568. state->chosen_exit = exit;
  2569. return 0;
  2570. }
  2571. /** Give <b>circ</b> a new exit destination to <b>exit</b>, and add a
  2572. * hop to the cpath reflecting this. Don't send the next extend cell --
  2573. * the caller will do this if it wants to.
  2574. */
  2575. int
  2576. circuit_append_new_exit(origin_circuit_t *circ, extend_info_t *exit)
  2577. {
  2578. cpath_build_state_t *state;
  2579. tor_assert(exit);
  2580. tor_assert(circ);
  2581. state = circ->build_state;
  2582. tor_assert(state);
  2583. extend_info_free(state->chosen_exit);
  2584. state->chosen_exit = extend_info_dup(exit);
  2585. ++circ->build_state->desired_path_len;
  2586. onion_append_hop(&circ->cpath, exit);
  2587. return 0;
  2588. }
  2589. /** Take an open <b>circ</b>, and add a new hop at the end, based on
  2590. * <b>info</b>. Set its state back to CIRCUIT_STATE_BUILDING, and then
  2591. * send the next extend cell to begin connecting to that hop.
  2592. */
  2593. int
  2594. circuit_extend_to_new_exit(origin_circuit_t *circ, extend_info_t *exit)
  2595. {
  2596. int err_reason = 0;
  2597. warn_if_last_router_excluded(circ, exit);
  2598. circuit_append_new_exit(circ, exit);
  2599. circuit_set_state(TO_CIRCUIT(circ), CIRCUIT_STATE_BUILDING);
  2600. if ((err_reason = circuit_send_next_onion_skin(circ))<0) {
  2601. log_warn(LD_CIRC, "Couldn't extend circuit to new point '%s'.",
  2602. exit->nickname);
  2603. circuit_mark_for_close(TO_CIRCUIT(circ), -err_reason);
  2604. return -1;
  2605. }
  2606. return 0;
  2607. }
  2608. /** Return the number of routers in <b>routers</b> that are currently up
  2609. * and available for building circuits through.
  2610. */
  2611. static int
  2612. count_acceptable_routers(smartlist_t *routers)
  2613. {
  2614. int i, n;
  2615. int num=0;
  2616. routerinfo_t *r;
  2617. n = smartlist_len(routers);
  2618. for (i=0;i<n;i++) {
  2619. r = smartlist_get(routers, i);
  2620. // log_debug(LD_CIRC,
  2621. // "Contemplating whether router %d (%s) is a new option.",
  2622. // i, r->nickname);
  2623. if (r->is_running == 0) {
  2624. // log_debug(LD_CIRC,"Nope, the directory says %d is not running.",i);
  2625. goto next_i_loop;
  2626. }
  2627. if (r->is_valid == 0) {
  2628. // log_debug(LD_CIRC,"Nope, the directory says %d is not valid.",i);
  2629. goto next_i_loop;
  2630. /* XXX This clause makes us count incorrectly: if AllowInvalidRouters
  2631. * allows this node in some places, then we're getting an inaccurate
  2632. * count. For now, be conservative and don't count it. But later we
  2633. * should try to be smarter. */
  2634. }
  2635. num++;
  2636. // log_debug(LD_CIRC,"I like %d. num_acceptable_routers now %d.",i, num);
  2637. next_i_loop:
  2638. ; /* C requires an explicit statement after the label */
  2639. }
  2640. return num;
  2641. }
  2642. /** Add <b>new_hop</b> to the end of the doubly-linked-list <b>head_ptr</b>.
  2643. * This function is used to extend cpath by another hop.
  2644. */
  2645. void
  2646. onion_append_to_cpath(crypt_path_t **head_ptr, crypt_path_t *new_hop)
  2647. {
  2648. if (*head_ptr) {
  2649. new_hop->next = (*head_ptr);
  2650. new_hop->prev = (*head_ptr)->prev;
  2651. (*head_ptr)->prev->next = new_hop;
  2652. (*head_ptr)->prev = new_hop;
  2653. } else {
  2654. *head_ptr = new_hop;
  2655. new_hop->prev = new_hop->next = new_hop;
  2656. }
  2657. }
  2658. /** A helper function used by onion_extend_cpath(). Use <b>purpose</b>
  2659. * and <b>state</b> and the cpath <b>head</b> (currently populated only
  2660. * to length <b>cur_len</b> to decide a suitable middle hop for a
  2661. * circuit. In particular, make sure we don't pick the exit node or its
  2662. * family, and make sure we don't duplicate any previous nodes or their
  2663. * families. */
  2664. static routerinfo_t *
  2665. choose_good_middle_server(uint8_t purpose,
  2666. cpath_build_state_t *state,
  2667. crypt_path_t *head,
  2668. int cur_len)
  2669. {
  2670. int i;
  2671. routerinfo_t *r, *choice;
  2672. crypt_path_t *cpath;
  2673. smartlist_t *excluded;
  2674. or_options_t *options = get_options();
  2675. router_crn_flags_t flags = 0;
  2676. tor_assert(_CIRCUIT_PURPOSE_MIN <= purpose &&
  2677. purpose <= _CIRCUIT_PURPOSE_MAX);
  2678. log_debug(LD_CIRC, "Contemplating intermediate hop: random choice.");
  2679. excluded = smartlist_create();
  2680. if ((r = build_state_get_exit_router(state))) {
  2681. smartlist_add(excluded, r);
  2682. routerlist_add_family(excluded, r);
  2683. }
  2684. for (i = 0, cpath = head; i < cur_len; ++i, cpath=cpath->next) {
  2685. if ((r = router_get_by_digest(cpath->extend_info->identity_digest))) {
  2686. smartlist_add(excluded, r);
  2687. routerlist_add_family(excluded, r);
  2688. }
  2689. }
  2690. if (state->need_uptime)
  2691. flags |= CRN_NEED_UPTIME;
  2692. if (state->need_capacity)
  2693. flags |= CRN_NEED_CAPACITY;
  2694. if (options->_AllowInvalid & ALLOW_INVALID_MIDDLE)
  2695. flags |= CRN_ALLOW_INVALID;
  2696. choice = router_choose_random_node(excluded, options->ExcludeNodes, flags);
  2697. smartlist_free(excluded);
  2698. return choice;
  2699. }
  2700. /** Pick a good entry server for the circuit to be built according to
  2701. * <b>state</b>. Don't reuse a chosen exit (if any), don't use this
  2702. * router (if we're an OR), and respect firewall settings; if we're
  2703. * configured to use entry guards, return one.
  2704. *
  2705. * If <b>state</b> is NULL, we're choosing a router to serve as an entry
  2706. * guard, not for any particular circuit.
  2707. */
  2708. static routerinfo_t *
  2709. choose_good_entry_server(uint8_t purpose, cpath_build_state_t *state)
  2710. {
  2711. routerinfo_t *r, *choice;
  2712. smartlist_t *excluded;
  2713. or_options_t *options = get_options();
  2714. router_crn_flags_t flags = CRN_NEED_GUARD;
  2715. if (state && options->UseEntryGuards &&
  2716. (purpose != CIRCUIT_PURPOSE_TESTING || options->BridgeRelay)) {
  2717. return choose_random_entry(state);
  2718. }
  2719. excluded = smartlist_create();
  2720. if (state && (r = build_state_get_exit_router(state))) {
  2721. smartlist_add(excluded, r);
  2722. routerlist_add_family(excluded, r);
  2723. }
  2724. if (firewall_is_fascist_or()) {
  2725. /*XXXX This could slow things down a lot; use a smarter implementation */
  2726. /* exclude all ORs that listen on the wrong port, if anybody notices. */
  2727. routerlist_t *rl = router_get_routerlist();
  2728. int i;
  2729. for (i=0; i < smartlist_len(rl->routers); i++) {
  2730. r = smartlist_get(rl->routers, i);
  2731. if (!fascist_firewall_allows_or(r))
  2732. smartlist_add(excluded, r);
  2733. }
  2734. }
  2735. /* and exclude current entry guards, if applicable */
  2736. if (options->UseEntryGuards && entry_guards) {
  2737. SMARTLIST_FOREACH(entry_guards, entry_guard_t *, entry,
  2738. {
  2739. if ((r = router_get_by_digest(entry->identity))) {
  2740. smartlist_add(excluded, r);
  2741. routerlist_add_family(excluded, r);
  2742. }
  2743. });
  2744. }
  2745. if (state) {
  2746. if (state->need_uptime)
  2747. flags |= CRN_NEED_UPTIME;
  2748. if (state->need_capacity)
  2749. flags |= CRN_NEED_CAPACITY;
  2750. }
  2751. if (options->_AllowInvalid & ALLOW_INVALID_ENTRY)
  2752. flags |= CRN_ALLOW_INVALID;
  2753. choice = router_choose_random_node(excluded, options->ExcludeNodes, flags);
  2754. smartlist_free(excluded);
  2755. return choice;
  2756. }
  2757. /** Return the first non-open hop in cpath, or return NULL if all
  2758. * hops are open. */
  2759. static crypt_path_t *
  2760. onion_next_hop_in_cpath(crypt_path_t *cpath)
  2761. {
  2762. crypt_path_t *hop = cpath;
  2763. do {
  2764. if (hop->state != CPATH_STATE_OPEN)
  2765. return hop;
  2766. hop = hop->next;
  2767. } while (hop != cpath);
  2768. return NULL;
  2769. }
  2770. /** Choose a suitable next hop in the cpath <b>head_ptr</b>,
  2771. * based on <b>state</b>. Append the hop info to head_ptr.
  2772. */
  2773. static int
  2774. onion_extend_cpath(origin_circuit_t *circ)
  2775. {
  2776. uint8_t purpose = circ->_base.purpose;
  2777. cpath_build_state_t *state = circ->build_state;
  2778. int cur_len = circuit_get_cpath_len(circ);
  2779. extend_info_t *info = NULL;
  2780. if (cur_len >= state->desired_path_len) {
  2781. log_debug(LD_CIRC, "Path is complete: %d steps long",
  2782. state->desired_path_len);
  2783. return 1;
  2784. }
  2785. log_debug(LD_CIRC, "Path is %d long; we want %d", cur_len,
  2786. state->desired_path_len);
  2787. if (cur_len == state->desired_path_len - 1) { /* Picking last node */
  2788. info = extend_info_dup(state->chosen_exit);
  2789. } else if (cur_len == 0) { /* picking first node */
  2790. routerinfo_t *r = choose_good_entry_server(purpose, state);
  2791. if (r)
  2792. info = extend_info_from_router(r);
  2793. } else {
  2794. routerinfo_t *r =
  2795. choose_good_middle_server(purpose, state, circ->cpath, cur_len);
  2796. if (r)
  2797. info = extend_info_from_router(r);
  2798. }
  2799. if (!info) {
  2800. log_warn(LD_CIRC,"Failed to find node for hop %d of our path. Discarding "
  2801. "this circuit.", cur_len);
  2802. return -1;
  2803. }
  2804. log_debug(LD_CIRC,"Chose router %s for hop %d (exit is %s)",
  2805. info->nickname, cur_len+1, build_state_get_exit_nickname(state));
  2806. onion_append_hop(&circ->cpath, info);
  2807. extend_info_free(info);
  2808. return 0;
  2809. }
  2810. /** Create a new hop, annotate it with information about its
  2811. * corresponding router <b>choice</b>, and append it to the
  2812. * end of the cpath <b>head_ptr</b>. */
  2813. static int
  2814. onion_append_hop(crypt_path_t **head_ptr, extend_info_t *choice)
  2815. {
  2816. crypt_path_t *hop = tor_malloc_zero(sizeof(crypt_path_t));
  2817. /* link hop into the cpath, at the end. */
  2818. onion_append_to_cpath(head_ptr, hop);
  2819. hop->magic = CRYPT_PATH_MAGIC;
  2820. hop->state = CPATH_STATE_CLOSED;
  2821. hop->extend_info = extend_info_dup(choice);
  2822. hop->package_window = circuit_initial_package_window();
  2823. hop->deliver_window = CIRCWINDOW_START;
  2824. return 0;
  2825. }
  2826. /** Allocate a new extend_info object based on the various arguments. */
  2827. extend_info_t *
  2828. extend_info_alloc(const char *nickname, const char *digest,
  2829. crypto_pk_env_t *onion_key,
  2830. const tor_addr_t *addr, uint16_t port)
  2831. {
  2832. extend_info_t *info = tor_malloc_zero(sizeof(extend_info_t));
  2833. memcpy(info->identity_digest, digest, DIGEST_LEN);
  2834. if (nickname)
  2835. strlcpy(info->nickname, nickname, sizeof(info->nickname));
  2836. if (onion_key)
  2837. info->onion_key = crypto_pk_dup_key(onion_key);
  2838. tor_addr_copy(&info->addr, addr);
  2839. info->port = port;
  2840. return info;
  2841. }
  2842. /** Allocate and return a new extend_info_t that can be used to build a
  2843. * circuit to or through the router <b>r</b>. */
  2844. extend_info_t *
  2845. extend_info_from_router(routerinfo_t *r)
  2846. {
  2847. tor_addr_t addr;
  2848. tor_assert(r);
  2849. tor_addr_from_ipv4h(&addr, r->addr);
  2850. return extend_info_alloc(r->nickname, r->cache_info.identity_digest,
  2851. r->onion_pkey, &addr, r->or_port);
  2852. }
  2853. /** Release storage held by an extend_info_t struct. */
  2854. void
  2855. extend_info_free(extend_info_t *info)
  2856. {
  2857. if (!info)
  2858. return;
  2859. crypto_free_pk_env(info->onion_key);
  2860. tor_free(info);
  2861. }
  2862. /** Allocate and return a new extend_info_t with the same contents as
  2863. * <b>info</b>. */
  2864. extend_info_t *
  2865. extend_info_dup(extend_info_t *info)
  2866. {
  2867. extend_info_t *newinfo;
  2868. tor_assert(info);
  2869. newinfo = tor_malloc(sizeof(extend_info_t));
  2870. memcpy(newinfo, info, sizeof(extend_info_t));
  2871. if (info->onion_key)
  2872. newinfo->onion_key = crypto_pk_dup_key(info->onion_key);
  2873. else
  2874. newinfo->onion_key = NULL;
  2875. return newinfo;
  2876. }
  2877. /** Return the routerinfo_t for the chosen exit router in <b>state</b>.
  2878. * If there is no chosen exit, or if we don't know the routerinfo_t for
  2879. * the chosen exit, return NULL.
  2880. */
  2881. routerinfo_t *
  2882. build_state_get_exit_router(cpath_build_state_t *state)
  2883. {
  2884. if (!state || !state->chosen_exit)
  2885. return NULL;
  2886. return router_get_by_digest(state->chosen_exit->identity_digest);
  2887. }
  2888. /** Return the nickname for the chosen exit router in <b>state</b>. If
  2889. * there is no chosen exit, or if we don't know the routerinfo_t for the
  2890. * chosen exit, return NULL.
  2891. */
  2892. const char *
  2893. build_state_get_exit_nickname(cpath_build_state_t *state)
  2894. {
  2895. if (!state || !state->chosen_exit)
  2896. return NULL;
  2897. return state->chosen_exit->nickname;
  2898. }
  2899. /** Check whether the entry guard <b>e</b> is usable, given the directory
  2900. * authorities' opinion about the router (stored in <b>ri</b>) and the user's
  2901. * configuration (in <b>options</b>). Set <b>e</b>-&gt;bad_since
  2902. * accordingly. Return true iff the entry guard's status changes.
  2903. *
  2904. * If it's not usable, set *<b>reason</b> to a static string explaining why.
  2905. */
  2906. /*XXXX take a routerstatus, not a routerinfo. */
  2907. static int
  2908. entry_guard_set_status(entry_guard_t *e, routerinfo_t *ri,
  2909. time_t now, or_options_t *options, const char **reason)
  2910. {
  2911. char buf[HEX_DIGEST_LEN+1];
  2912. int changed = 0;
  2913. *reason = NULL;
  2914. /* Do we want to mark this guard as bad? */
  2915. if (!ri)
  2916. *reason = "unlisted";
  2917. else if (!ri->is_running)
  2918. *reason = "down";
  2919. else if (options->UseBridges && ri->purpose != ROUTER_PURPOSE_BRIDGE)
  2920. *reason = "not a bridge";
  2921. else if (!options->UseBridges && !ri->is_possible_guard &&
  2922. !routerset_contains_router(options->EntryNodes,ri))
  2923. *reason = "not recommended as a guard";
  2924. else if (routerset_contains_router(options->ExcludeNodes, ri))
  2925. *reason = "excluded";
  2926. if (*reason && ! e->bad_since) {
  2927. /* Router is newly bad. */
  2928. base16_encode(buf, sizeof(buf), e->identity, DIGEST_LEN);
  2929. log_info(LD_CIRC, "Entry guard %s (%s) is %s: marking as unusable.",
  2930. e->nickname, buf, *reason);
  2931. e->bad_since = now;
  2932. control_event_guard(e->nickname, e->identity, "BAD");
  2933. changed = 1;
  2934. } else if (!*reason && e->bad_since) {
  2935. /* There's nothing wrong with the router any more. */
  2936. base16_encode(buf, sizeof(buf), e->identity, DIGEST_LEN);
  2937. log_info(LD_CIRC, "Entry guard %s (%s) is no longer unusable: "
  2938. "marking as ok.", e->nickname, buf);
  2939. e->bad_since = 0;
  2940. control_event_guard(e->nickname, e->identity, "GOOD");
  2941. changed = 1;
  2942. }
  2943. return changed;
  2944. }
  2945. /** Return true iff enough time has passed since we last tried to connect
  2946. * to the unreachable guard <b>e</b> that we're willing to try again. */
  2947. static int
  2948. entry_is_time_to_retry(entry_guard_t *e, time_t now)
  2949. {
  2950. long diff;
  2951. if (e->last_attempted < e->unreachable_since)
  2952. return 1;
  2953. diff = now - e->unreachable_since;
  2954. if (diff < 6*60*60)
  2955. return now > (e->last_attempted + 60*60);
  2956. else if (diff < 3*24*60*60)
  2957. return now > (e->last_attempted + 4*60*60);
  2958. else if (diff < 7*24*60*60)
  2959. return now > (e->last_attempted + 18*60*60);
  2960. else
  2961. return now > (e->last_attempted + 36*60*60);
  2962. }
  2963. /** Return the router corresponding to <b>e</b>, if <b>e</b> is
  2964. * working well enough that we are willing to use it as an entry
  2965. * right now. (Else return NULL.) In particular, it must be
  2966. * - Listed as either up or never yet contacted;
  2967. * - Present in the routerlist;
  2968. * - Listed as 'stable' or 'fast' by the current dirserver consensus,
  2969. * if demanded by <b>need_uptime</b> or <b>need_capacity</b>
  2970. * (unless it's a configured EntryNode);
  2971. * - Allowed by our current ReachableORAddresses config option; and
  2972. * - Currently thought to be reachable by us (unless <b>assume_reachable</b>
  2973. * is true).
  2974. *
  2975. * If the answer is no, set *<b>msg</b> to an explanation of why.
  2976. */
  2977. static INLINE routerinfo_t *
  2978. entry_is_live(entry_guard_t *e, int need_uptime, int need_capacity,
  2979. int assume_reachable, const char **msg)
  2980. {
  2981. routerinfo_t *r;
  2982. or_options_t *options = get_options();
  2983. tor_assert(msg);
  2984. if (e->bad_since) {
  2985. *msg = "bad";
  2986. return NULL;
  2987. }
  2988. /* no good if it's unreachable, unless assume_unreachable or can_retry. */
  2989. if (!assume_reachable && !e->can_retry &&
  2990. e->unreachable_since && !entry_is_time_to_retry(e, time(NULL))) {
  2991. *msg = "unreachable";
  2992. return NULL;
  2993. }
  2994. r = router_get_by_digest(e->identity);
  2995. if (!r) {
  2996. *msg = "no descriptor";
  2997. return NULL;
  2998. }
  2999. if (get_options()->UseBridges && r->purpose != ROUTER_PURPOSE_BRIDGE) {
  3000. *msg = "not a bridge";
  3001. return NULL;
  3002. }
  3003. if (!get_options()->UseBridges && r->purpose != ROUTER_PURPOSE_GENERAL) {
  3004. *msg = "not general-purpose";
  3005. return NULL;
  3006. }
  3007. if (options->EntryNodes &&
  3008. routerset_contains_router(options->EntryNodes, r)) {
  3009. /* they asked for it, they get it */
  3010. need_uptime = need_capacity = 0;
  3011. }
  3012. if (router_is_unreliable(r, need_uptime, need_capacity, 0)) {
  3013. *msg = "not fast/stable";
  3014. return NULL;
  3015. }
  3016. if (!fascist_firewall_allows_or(r)) {
  3017. *msg = "unreachable by config";
  3018. return NULL;
  3019. }
  3020. return r;
  3021. }
  3022. /** Return the number of entry guards that we think are usable. */
  3023. static int
  3024. num_live_entry_guards(void)
  3025. {
  3026. int n = 0;
  3027. const char *msg;
  3028. if (! entry_guards)
  3029. return 0;
  3030. SMARTLIST_FOREACH(entry_guards, entry_guard_t *, entry,
  3031. {
  3032. if (entry_is_live(entry, 0, 1, 0, &msg))
  3033. ++n;
  3034. });
  3035. return n;
  3036. }
  3037. /** If <b>digest</b> matches the identity of any node in the
  3038. * entry_guards list, return that node. Else return NULL. */
  3039. static INLINE entry_guard_t *
  3040. is_an_entry_guard(const char *digest)
  3041. {
  3042. SMARTLIST_FOREACH(entry_guards, entry_guard_t *, entry,
  3043. if (!memcmp(digest, entry->identity, DIGEST_LEN))
  3044. return entry;
  3045. );
  3046. return NULL;
  3047. }
  3048. /** Dump a description of our list of entry guards to the log at level
  3049. * <b>severity</b>. */
  3050. static void
  3051. log_entry_guards(int severity)
  3052. {
  3053. smartlist_t *elements = smartlist_create();
  3054. char *s;
  3055. SMARTLIST_FOREACH(entry_guards, entry_guard_t *, e,
  3056. {
  3057. const char *msg = NULL;
  3058. char *cp;
  3059. if (entry_is_live(e, 0, 1, 0, &msg))
  3060. tor_asprintf(&cp, "%s (up %s)",
  3061. e->nickname,
  3062. e->made_contact ? "made-contact" : "never-contacted");
  3063. else
  3064. tor_asprintf(&cp, "%s (%s, %s)",
  3065. e->nickname, msg,
  3066. e->made_contact ? "made-contact" : "never-contacted");
  3067. smartlist_add(elements, cp);
  3068. });
  3069. s = smartlist_join_strings(elements, ",", 0, NULL);
  3070. SMARTLIST_FOREACH(elements, char*, cp, tor_free(cp));
  3071. smartlist_free(elements);
  3072. log_fn(severity,LD_CIRC,"%s",s);
  3073. tor_free(s);
  3074. }
  3075. /** Called when one or more guards that we would previously have used for some
  3076. * purpose are no longer in use because a higher-priority guard has become
  3077. * usable again. */
  3078. static void
  3079. control_event_guard_deferred(void)
  3080. {
  3081. /* XXXX We don't actually have a good way to figure out _how many_ entries
  3082. * are live for some purpose. We need an entry_is_even_slightly_live()
  3083. * function for this to work right. NumEntryGuards isn't reliable: if we
  3084. * need guards with weird properties, we can have more than that number
  3085. * live.
  3086. **/
  3087. #if 0
  3088. int n = 0;
  3089. const char *msg;
  3090. or_options_t *options = get_options();
  3091. if (!entry_guards)
  3092. return;
  3093. SMARTLIST_FOREACH(entry_guards, entry_guard_t *, entry,
  3094. {
  3095. if (entry_is_live(entry, 0, 1, 0, &msg)) {
  3096. if (n++ == options->NumEntryGuards) {
  3097. control_event_guard(entry->nickname, entry->identity, "DEFERRED");
  3098. return;
  3099. }
  3100. }
  3101. });
  3102. #endif
  3103. }
  3104. /** Add a new (preferably stable and fast) router to our
  3105. * entry_guards list. Return a pointer to the router if we succeed,
  3106. * or NULL if we can't find any more suitable entries.
  3107. *
  3108. * If <b>chosen</b> is defined, use that one, and if it's not
  3109. * already in our entry_guards list, put it at the *beginning*.
  3110. * Else, put the one we pick at the end of the list. */
  3111. static routerinfo_t *
  3112. add_an_entry_guard(routerinfo_t *chosen, int reset_status)
  3113. {
  3114. routerinfo_t *router;
  3115. entry_guard_t *entry;
  3116. if (chosen) {
  3117. router = chosen;
  3118. entry = is_an_entry_guard(router->cache_info.identity_digest);
  3119. if (entry) {
  3120. if (reset_status) {
  3121. entry->bad_since = 0;
  3122. entry->can_retry = 1;
  3123. }
  3124. return NULL;
  3125. }
  3126. } else {
  3127. router = choose_good_entry_server(CIRCUIT_PURPOSE_C_GENERAL, NULL);
  3128. if (!router)
  3129. return NULL;
  3130. }
  3131. entry = tor_malloc_zero(sizeof(entry_guard_t));
  3132. log_info(LD_CIRC, "Chose '%s' as new entry guard.", router->nickname);
  3133. strlcpy(entry->nickname, router->nickname, sizeof(entry->nickname));
  3134. memcpy(entry->identity, router->cache_info.identity_digest, DIGEST_LEN);
  3135. /* Choose expiry time smudged over the past month. The goal here
  3136. * is to a) spread out when Tor clients rotate their guards, so they
  3137. * don't all select them on the same day, and b) avoid leaving a
  3138. * precise timestamp in the state file about when we first picked
  3139. * this guard. For details, see the Jan 2010 or-dev thread. */
  3140. entry->chosen_on_date = time(NULL) - crypto_rand_int(3600*24*30);
  3141. entry->chosen_by_version = tor_strdup(VERSION);
  3142. if (chosen) /* prepend */
  3143. smartlist_insert(entry_guards, 0, entry);
  3144. else /* append */
  3145. smartlist_add(entry_guards, entry);
  3146. control_event_guard(entry->nickname, entry->identity, "NEW");
  3147. control_event_guard_deferred();
  3148. log_entry_guards(LOG_INFO);
  3149. return router;
  3150. }
  3151. /** If the use of entry guards is configured, choose more entry guards
  3152. * until we have enough in the list. */
  3153. static void
  3154. pick_entry_guards(or_options_t *options)
  3155. {
  3156. int changed = 0;
  3157. tor_assert(entry_guards);
  3158. while (num_live_entry_guards() < options->NumEntryGuards) {
  3159. if (!add_an_entry_guard(NULL, 0))
  3160. break;
  3161. changed = 1;
  3162. }
  3163. if (changed)
  3164. entry_guards_changed();
  3165. }
  3166. /** How long (in seconds) do we allow an entry guard to be nonfunctional,
  3167. * unlisted, excluded, or otherwise nonusable before we give up on it? */
  3168. #define ENTRY_GUARD_REMOVE_AFTER (30*24*60*60)
  3169. /** Release all storage held by <b>e</b>. */
  3170. static void
  3171. entry_guard_free(entry_guard_t *e)
  3172. {
  3173. if (!e)
  3174. return;
  3175. tor_free(e->chosen_by_version);
  3176. tor_free(e);
  3177. }
  3178. /** Remove any entry guard which was selected by an unknown version of Tor,
  3179. * or which was selected by a version of Tor that's known to select
  3180. * entry guards badly. */
  3181. static int
  3182. remove_obsolete_entry_guards(time_t now)
  3183. {
  3184. int changed = 0, i;
  3185. for (i = 0; i < smartlist_len(entry_guards); ++i) {
  3186. entry_guard_t *entry = smartlist_get(entry_guards, i);
  3187. const char *ver = entry->chosen_by_version;
  3188. const char *msg = NULL;
  3189. tor_version_t v;
  3190. int version_is_bad = 0, date_is_bad = 0;
  3191. if (!ver) {
  3192. msg = "does not say what version of Tor it was selected by";
  3193. version_is_bad = 1;
  3194. } else if (tor_version_parse(ver, &v)) {
  3195. msg = "does not seem to be from any recognized version of Tor";
  3196. version_is_bad = 1;
  3197. } else {
  3198. size_t len = strlen(ver)+5;
  3199. char *tor_ver = tor_malloc(len);
  3200. tor_snprintf(tor_ver, len, "Tor %s", ver);
  3201. if ((tor_version_as_new_as(tor_ver, "0.1.0.10-alpha") &&
  3202. !tor_version_as_new_as(tor_ver, "0.1.2.16-dev")) ||
  3203. (tor_version_as_new_as(tor_ver, "0.2.0.0-alpha") &&
  3204. !tor_version_as_new_as(tor_ver, "0.2.0.6-alpha")) ||
  3205. /* above are bug 440; below are bug 1217 */
  3206. (tor_version_as_new_as(tor_ver, "0.2.1.3-alpha") &&
  3207. !tor_version_as_new_as(tor_ver, "0.2.1.23")) ||
  3208. (tor_version_as_new_as(tor_ver, "0.2.2.0-alpha") &&
  3209. !tor_version_as_new_as(tor_ver, "0.2.2.7-alpha"))) {
  3210. msg = "was selected without regard for guard bandwidth";
  3211. version_is_bad = 1;
  3212. }
  3213. tor_free(tor_ver);
  3214. }
  3215. if (!version_is_bad && entry->chosen_on_date + 3600*24*60 < now) {
  3216. /* It's been 2 months since the date listed in our state file. */
  3217. msg = "was selected several months ago";
  3218. date_is_bad = 1;
  3219. }
  3220. if (version_is_bad || date_is_bad) { /* we need to drop it */
  3221. char dbuf[HEX_DIGEST_LEN+1];
  3222. tor_assert(msg);
  3223. base16_encode(dbuf, sizeof(dbuf), entry->identity, DIGEST_LEN);
  3224. log_fn(version_is_bad ? LOG_NOTICE : LOG_INFO, LD_CIRC,
  3225. "Entry guard '%s' (%s) %s. (Version=%s.) Replacing it.",
  3226. entry->nickname, dbuf, msg, ver?escaped(ver):"none");
  3227. control_event_guard(entry->nickname, entry->identity, "DROPPED");
  3228. entry_guard_free(entry);
  3229. smartlist_del_keeporder(entry_guards, i--);
  3230. log_entry_guards(LOG_INFO);
  3231. changed = 1;
  3232. }
  3233. }
  3234. return changed ? 1 : 0;
  3235. }
  3236. /** Remove all entry guards that have been down or unlisted for so
  3237. * long that we don't think they'll come up again. Return 1 if we
  3238. * removed any, or 0 if we did nothing. */
  3239. static int
  3240. remove_dead_entry_guards(time_t now)
  3241. {
  3242. char dbuf[HEX_DIGEST_LEN+1];
  3243. char tbuf[ISO_TIME_LEN+1];
  3244. int i;
  3245. int changed = 0;
  3246. for (i = 0; i < smartlist_len(entry_guards); ) {
  3247. entry_guard_t *entry = smartlist_get(entry_guards, i);
  3248. if (entry->bad_since &&
  3249. entry->bad_since + ENTRY_GUARD_REMOVE_AFTER < now) {
  3250. base16_encode(dbuf, sizeof(dbuf), entry->identity, DIGEST_LEN);
  3251. format_local_iso_time(tbuf, entry->bad_since);
  3252. log_info(LD_CIRC, "Entry guard '%s' (%s) has been down or unlisted "
  3253. "since %s local time; removing.",
  3254. entry->nickname, dbuf, tbuf);
  3255. control_event_guard(entry->nickname, entry->identity, "DROPPED");
  3256. entry_guard_free(entry);
  3257. smartlist_del_keeporder(entry_guards, i);
  3258. log_entry_guards(LOG_INFO);
  3259. changed = 1;
  3260. } else
  3261. ++i;
  3262. }
  3263. return changed ? 1 : 0;
  3264. }
  3265. /** A new directory or router-status has arrived; update the down/listed
  3266. * status of the entry guards.
  3267. *
  3268. * An entry is 'down' if the directory lists it as nonrunning.
  3269. * An entry is 'unlisted' if the directory doesn't include it.
  3270. *
  3271. * Don't call this on startup; only on a fresh download. Otherwise we'll
  3272. * think that things are unlisted.
  3273. */
  3274. void
  3275. entry_guards_compute_status(or_options_t *options, time_t now)
  3276. {
  3277. int changed = 0;
  3278. int severity = LOG_DEBUG;
  3279. digestmap_t *reasons;
  3280. if (! entry_guards)
  3281. return;
  3282. if (options->EntryNodes) /* reshuffle the entry guard list if needed */
  3283. entry_nodes_should_be_added();
  3284. reasons = digestmap_new();
  3285. SMARTLIST_FOREACH_BEGIN(entry_guards, entry_guard_t *, entry)
  3286. {
  3287. routerinfo_t *r = router_get_by_digest(entry->identity);
  3288. const char *reason = NULL;
  3289. if (entry_guard_set_status(entry, r, now, options, &reason))
  3290. changed = 1;
  3291. if (entry->bad_since)
  3292. tor_assert(reason);
  3293. if (reason)
  3294. digestmap_set(reasons, entry->identity, (char*)reason);
  3295. }
  3296. SMARTLIST_FOREACH_END(entry);
  3297. if (remove_dead_entry_guards(now))
  3298. changed = 1;
  3299. severity = changed ? LOG_DEBUG : LOG_INFO;
  3300. if (changed) {
  3301. SMARTLIST_FOREACH_BEGIN(entry_guards, entry_guard_t *, entry) {
  3302. const char *reason = digestmap_get(reasons, entry->identity);
  3303. const char *live_msg = "";
  3304. routerinfo_t *r = entry_is_live(entry, 0, 1, 0, &live_msg);
  3305. log_info(LD_CIRC, "Summary: Entry '%s' is %s, %s%s%s, and %s%s.",
  3306. entry->nickname,
  3307. entry->unreachable_since ? "unreachable" : "reachable",
  3308. entry->bad_since ? "unusable" : "usable",
  3309. reason ? ", ": "",
  3310. reason ? reason : "",
  3311. r ? "live" : "not live / ",
  3312. r ? "" : live_msg);
  3313. } SMARTLIST_FOREACH_END(entry);
  3314. log_info(LD_CIRC, " (%d/%d entry guards are usable/new)",
  3315. num_live_entry_guards(), smartlist_len(entry_guards));
  3316. log_entry_guards(LOG_INFO);
  3317. entry_guards_changed();
  3318. }
  3319. digestmap_free(reasons, NULL);
  3320. }
  3321. /** Called when a connection to an OR with the identity digest <b>digest</b>
  3322. * is established (<b>succeeded</b>==1) or has failed (<b>succeeded</b>==0).
  3323. * If the OR is an entry, change that entry's up/down status.
  3324. * Return 0 normally, or -1 if we want to tear down the new connection.
  3325. *
  3326. * If <b>mark_relay_status</b>, also call router_set_status() on this
  3327. * relay.
  3328. *
  3329. * XXX022 change succeeded and mark_relay_status into 'int flags'.
  3330. */
  3331. int
  3332. entry_guard_register_connect_status(const char *digest, int succeeded,
  3333. int mark_relay_status, time_t now)
  3334. {
  3335. int changed = 0;
  3336. int refuse_conn = 0;
  3337. int first_contact = 0;
  3338. entry_guard_t *entry = NULL;
  3339. int idx = -1;
  3340. char buf[HEX_DIGEST_LEN+1];
  3341. if (! entry_guards)
  3342. return 0;
  3343. SMARTLIST_FOREACH(entry_guards, entry_guard_t *, e,
  3344. {
  3345. if (!memcmp(e->identity, digest, DIGEST_LEN)) {
  3346. entry = e;
  3347. idx = e_sl_idx;
  3348. break;
  3349. }
  3350. });
  3351. if (!entry)
  3352. return 0;
  3353. base16_encode(buf, sizeof(buf), entry->identity, DIGEST_LEN);
  3354. if (succeeded) {
  3355. if (entry->unreachable_since) {
  3356. log_info(LD_CIRC, "Entry guard '%s' (%s) is now reachable again. Good.",
  3357. entry->nickname, buf);
  3358. entry->can_retry = 0;
  3359. entry->unreachable_since = 0;
  3360. entry->last_attempted = now;
  3361. control_event_guard(entry->nickname, entry->identity, "UP");
  3362. changed = 1;
  3363. }
  3364. if (!entry->made_contact) {
  3365. entry->made_contact = 1;
  3366. first_contact = changed = 1;
  3367. }
  3368. } else { /* ! succeeded */
  3369. if (!entry->made_contact) {
  3370. /* We've never connected to this one. */
  3371. log_info(LD_CIRC,
  3372. "Connection to never-contacted entry guard '%s' (%s) failed. "
  3373. "Removing from the list. %d/%d entry guards usable/new.",
  3374. entry->nickname, buf,
  3375. num_live_entry_guards()-1, smartlist_len(entry_guards)-1);
  3376. control_event_guard(entry->nickname, entry->identity, "DROPPED");
  3377. entry_guard_free(entry);
  3378. smartlist_del_keeporder(entry_guards, idx);
  3379. log_entry_guards(LOG_INFO);
  3380. changed = 1;
  3381. } else if (!entry->unreachable_since) {
  3382. log_info(LD_CIRC, "Unable to connect to entry guard '%s' (%s). "
  3383. "Marking as unreachable.", entry->nickname, buf);
  3384. entry->unreachable_since = entry->last_attempted = now;
  3385. control_event_guard(entry->nickname, entry->identity, "DOWN");
  3386. changed = 1;
  3387. entry->can_retry = 0; /* We gave it an early chance; no good. */
  3388. } else {
  3389. char tbuf[ISO_TIME_LEN+1];
  3390. format_iso_time(tbuf, entry->unreachable_since);
  3391. log_debug(LD_CIRC, "Failed to connect to unreachable entry guard "
  3392. "'%s' (%s). It has been unreachable since %s.",
  3393. entry->nickname, buf, tbuf);
  3394. entry->last_attempted = now;
  3395. entry->can_retry = 0; /* We gave it an early chance; no good. */
  3396. }
  3397. }
  3398. /* if the caller asked us to, also update the is_running flags for this
  3399. * relay */
  3400. if (mark_relay_status)
  3401. router_set_status(digest, succeeded);
  3402. if (first_contact) {
  3403. /* We've just added a new long-term entry guard. Perhaps the network just
  3404. * came back? We should give our earlier entries another try too,
  3405. * and close this connection so we don't use it before we've given
  3406. * the others a shot. */
  3407. SMARTLIST_FOREACH(entry_guards, entry_guard_t *, e, {
  3408. if (e == entry)
  3409. break;
  3410. if (e->made_contact) {
  3411. const char *msg;
  3412. routerinfo_t *r = entry_is_live(e, 0, 1, 1, &msg);
  3413. if (r && e->unreachable_since) {
  3414. refuse_conn = 1;
  3415. e->can_retry = 1;
  3416. }
  3417. }
  3418. });
  3419. if (refuse_conn) {
  3420. log_info(LD_CIRC,
  3421. "Connected to new entry guard '%s' (%s). Marking earlier "
  3422. "entry guards up. %d/%d entry guards usable/new.",
  3423. entry->nickname, buf,
  3424. num_live_entry_guards(), smartlist_len(entry_guards));
  3425. log_entry_guards(LOG_INFO);
  3426. changed = 1;
  3427. }
  3428. }
  3429. if (changed)
  3430. entry_guards_changed();
  3431. return refuse_conn ? -1 : 0;
  3432. }
  3433. /** When we try to choose an entry guard, should we parse and add
  3434. * config's EntryNodes first? */
  3435. static int should_add_entry_nodes = 0;
  3436. /** Called when the value of EntryNodes changes in our configuration. */
  3437. void
  3438. entry_nodes_should_be_added(void)
  3439. {
  3440. log_info(LD_CIRC, "EntryNodes config option set. Putting configured "
  3441. "relays at the front of the entry guard list.");
  3442. should_add_entry_nodes = 1;
  3443. }
  3444. /** Add all nodes in EntryNodes that aren't currently guard nodes to the list
  3445. * of guard nodes, at the front. */
  3446. static void
  3447. entry_guards_prepend_from_config(or_options_t *options)
  3448. {
  3449. smartlist_t *entry_routers, *entry_fps;
  3450. smartlist_t *old_entry_guards_on_list, *old_entry_guards_not_on_list;
  3451. tor_assert(entry_guards);
  3452. should_add_entry_nodes = 0;
  3453. if (!options->EntryNodes) {
  3454. /* It's possible that a controller set EntryNodes, thus making
  3455. * should_add_entry_nodes set, then cleared it again, all before the
  3456. * call to choose_random_entry() that triggered us. If so, just return.
  3457. */
  3458. return;
  3459. }
  3460. {
  3461. char *string = routerset_to_string(options->EntryNodes);
  3462. log_info(LD_CIRC,"Adding configured EntryNodes '%s'.", string);
  3463. tor_free(string);
  3464. }
  3465. entry_routers = smartlist_create();
  3466. entry_fps = smartlist_create();
  3467. old_entry_guards_on_list = smartlist_create();
  3468. old_entry_guards_not_on_list = smartlist_create();
  3469. /* Split entry guards into those on the list and those not. */
  3470. /* XXXX022 Now that we allow countries and IP ranges in EntryNodes, this is
  3471. * potentially an enormous list. For now, we disable such values for
  3472. * EntryNodes in options_validate(); really, this wants a better solution.
  3473. * Perhaps we should do this calculation once whenever the list of routers
  3474. * changes or the entrynodes setting changes.
  3475. */
  3476. routerset_get_all_routers(entry_routers, options->EntryNodes, 0);
  3477. SMARTLIST_FOREACH(entry_routers, routerinfo_t *, ri,
  3478. smartlist_add(entry_fps,ri->cache_info.identity_digest));
  3479. SMARTLIST_FOREACH(entry_guards, entry_guard_t *, e, {
  3480. if (smartlist_digest_isin(entry_fps, e->identity))
  3481. smartlist_add(old_entry_guards_on_list, e);
  3482. else
  3483. smartlist_add(old_entry_guards_not_on_list, e);
  3484. });
  3485. /* Remove all currently configured entry guards from entry_routers. */
  3486. SMARTLIST_FOREACH(entry_routers, routerinfo_t *, ri, {
  3487. if (is_an_entry_guard(ri->cache_info.identity_digest)) {
  3488. SMARTLIST_DEL_CURRENT(entry_routers, ri);
  3489. }
  3490. });
  3491. /* Now build the new entry_guards list. */
  3492. smartlist_clear(entry_guards);
  3493. /* First, the previously configured guards that are in EntryNodes. */
  3494. smartlist_add_all(entry_guards, old_entry_guards_on_list);
  3495. /* Next, the rest of EntryNodes */
  3496. SMARTLIST_FOREACH(entry_routers, routerinfo_t *, ri, {
  3497. add_an_entry_guard(ri, 0);
  3498. });
  3499. /* Finally, the remaining previously configured guards that are not in
  3500. * EntryNodes, unless we're strict in which case we drop them */
  3501. if (options->StrictNodes) {
  3502. SMARTLIST_FOREACH(old_entry_guards_not_on_list, entry_guard_t *, e,
  3503. entry_guard_free(e));
  3504. } else {
  3505. smartlist_add_all(entry_guards, old_entry_guards_not_on_list);
  3506. }
  3507. smartlist_free(entry_routers);
  3508. smartlist_free(entry_fps);
  3509. smartlist_free(old_entry_guards_on_list);
  3510. smartlist_free(old_entry_guards_not_on_list);
  3511. entry_guards_changed();
  3512. }
  3513. /** Return 0 if we're fine adding arbitrary routers out of the
  3514. * directory to our entry guard list, or return 1 if we have a
  3515. * list already and we'd prefer to stick to it.
  3516. */
  3517. int
  3518. entry_list_is_constrained(or_options_t *options)
  3519. {
  3520. if (options->EntryNodes)
  3521. return 1;
  3522. if (options->UseBridges)
  3523. return 1;
  3524. return 0;
  3525. }
  3526. /* Are we dead set against changing our entry guard list, or would we
  3527. * change it if it means keeping Tor usable? */
  3528. static int
  3529. entry_list_is_totally_static(or_options_t *options)
  3530. {
  3531. if (options->EntryNodes && options->StrictNodes)
  3532. return 1;
  3533. if (options->UseBridges)
  3534. return 1;
  3535. return 0;
  3536. }
  3537. /** Pick a live (up and listed) entry guard from entry_guards. If
  3538. * <b>state</b> is non-NULL, this is for a specific circuit --
  3539. * make sure not to pick this circuit's exit or any node in the
  3540. * exit's family. If <b>state</b> is NULL, we're looking for a random
  3541. * guard (likely a bridge). */
  3542. routerinfo_t *
  3543. choose_random_entry(cpath_build_state_t *state)
  3544. {
  3545. or_options_t *options = get_options();
  3546. smartlist_t *live_entry_guards = smartlist_create();
  3547. smartlist_t *exit_family = smartlist_create();
  3548. routerinfo_t *chosen_exit = state?build_state_get_exit_router(state) : NULL;
  3549. routerinfo_t *r = NULL;
  3550. int need_uptime = state ? state->need_uptime : 0;
  3551. int need_capacity = state ? state->need_capacity : 0;
  3552. int preferred_min, consider_exit_family = 0;
  3553. if (chosen_exit) {
  3554. smartlist_add(exit_family, chosen_exit);
  3555. routerlist_add_family(exit_family, chosen_exit);
  3556. consider_exit_family = 1;
  3557. }
  3558. if (!entry_guards)
  3559. entry_guards = smartlist_create();
  3560. if (should_add_entry_nodes)
  3561. entry_guards_prepend_from_config(options);
  3562. if (!entry_list_is_constrained(options) &&
  3563. smartlist_len(entry_guards) < options->NumEntryGuards)
  3564. pick_entry_guards(options);
  3565. retry:
  3566. smartlist_clear(live_entry_guards);
  3567. SMARTLIST_FOREACH(entry_guards, entry_guard_t *, entry,
  3568. {
  3569. const char *msg;
  3570. r = entry_is_live(entry, need_uptime, need_capacity, 0, &msg);
  3571. if (!r)
  3572. continue; /* down, no point */
  3573. if (consider_exit_family && smartlist_isin(exit_family, r))
  3574. continue; /* avoid relays that are family members of our exit */
  3575. if (options->EntryNodes &&
  3576. !routerset_contains_router(options->EntryNodes, r)) {
  3577. /* We've come to the end of our preferred entry nodes. */
  3578. if (smartlist_len(live_entry_guards))
  3579. goto choose_and_finish; /* only choose from the ones we like */
  3580. if (options->StrictNodes) {
  3581. /* in theory this case should never happen, since
  3582. * entry_guards_prepend_from_config() drops unwanted relays */
  3583. tor_fragile_assert();
  3584. } else {
  3585. log_info(LD_CIRC,
  3586. "No relays from EntryNodes available. Using others.");
  3587. }
  3588. }
  3589. smartlist_add(live_entry_guards, r);
  3590. if (!entry->made_contact) {
  3591. /* Always start with the first not-yet-contacted entry
  3592. * guard. Otherwise we might add several new ones, pick
  3593. * the second new one, and now we've expanded our entry
  3594. * guard list without needing to. */
  3595. goto choose_and_finish;
  3596. }
  3597. if (smartlist_len(live_entry_guards) >= options->NumEntryGuards)
  3598. break; /* we have enough */
  3599. });
  3600. if (entry_list_is_constrained(options)) {
  3601. /* If we prefer the entry nodes we've got, and we have at least
  3602. * one choice, that's great. Use it. */
  3603. preferred_min = 1;
  3604. } else {
  3605. /* Try to have at least 2 choices available. This way we don't
  3606. * get stuck with a single live-but-crummy entry and just keep
  3607. * using him.
  3608. * (We might get 2 live-but-crummy entry guards, but so be it.) */
  3609. preferred_min = 2;
  3610. }
  3611. if (smartlist_len(live_entry_guards) < preferred_min) {
  3612. if (!entry_list_is_totally_static(options)) {
  3613. /* still no? try adding a new entry then */
  3614. /* XXX if guard doesn't imply fast and stable, then we need
  3615. * to tell add_an_entry_guard below what we want, or it might
  3616. * be a long time til we get it. -RD */
  3617. r = add_an_entry_guard(NULL, 0);
  3618. if (r) {
  3619. entry_guards_changed();
  3620. /* XXX we start over here in case the new node we added shares
  3621. * a family with our exit node. There's a chance that we'll just
  3622. * load up on entry guards here, if the network we're using is
  3623. * one big family. Perhaps we should teach add_an_entry_guard()
  3624. * to understand nodes-to-avoid-if-possible? -RD */
  3625. goto retry;
  3626. }
  3627. }
  3628. if (!r && need_uptime) {
  3629. need_uptime = 0; /* try without that requirement */
  3630. goto retry;
  3631. }
  3632. if (!r && need_capacity) {
  3633. /* still no? last attempt, try without requiring capacity */
  3634. need_capacity = 0;
  3635. goto retry;
  3636. }
  3637. if (!r && entry_list_is_constrained(options) && consider_exit_family) {
  3638. /* still no? if we're using bridges or have strictentrynodes
  3639. * set, and our chosen exit is in the same family as all our
  3640. * bridges/entry guards, then be flexible about families. */
  3641. consider_exit_family = 0;
  3642. goto retry;
  3643. }
  3644. /* live_entry_guards may be empty below. Oh well, we tried. */
  3645. }
  3646. choose_and_finish:
  3647. if (entry_list_is_constrained(options)) {
  3648. /* We need to weight by bandwidth, because our bridges or entryguards
  3649. * were not already selected proportional to their bandwidth. */
  3650. r = routerlist_sl_choose_by_bandwidth(live_entry_guards, WEIGHT_FOR_GUARD);
  3651. } else {
  3652. /* We choose uniformly at random here, because choose_good_entry_server()
  3653. * already weights its choices by bandwidth, so we don't want to
  3654. * *double*-weight our guard selection. */
  3655. r = smartlist_choose(live_entry_guards);
  3656. }
  3657. smartlist_free(live_entry_guards);
  3658. smartlist_free(exit_family);
  3659. return r;
  3660. }
  3661. /** Parse <b>state</b> and learn about the entry guards it describes.
  3662. * If <b>set</b> is true, and there are no errors, replace the global
  3663. * entry_list with what we find.
  3664. * On success, return 0. On failure, alloc into *<b>msg</b> a string
  3665. * describing the error, and return -1.
  3666. */
  3667. int
  3668. entry_guards_parse_state(or_state_t *state, int set, char **msg)
  3669. {
  3670. entry_guard_t *node = NULL;
  3671. smartlist_t *new_entry_guards = smartlist_create();
  3672. config_line_t *line;
  3673. time_t now = time(NULL);
  3674. const char *state_version = state->TorVersion;
  3675. digestmap_t *added_by = digestmap_new();
  3676. *msg = NULL;
  3677. for (line = state->EntryGuards; line; line = line->next) {
  3678. if (!strcasecmp(line->key, "EntryGuard")) {
  3679. smartlist_t *args = smartlist_create();
  3680. node = tor_malloc_zero(sizeof(entry_guard_t));
  3681. /* all entry guards on disk have been contacted */
  3682. node->made_contact = 1;
  3683. smartlist_add(new_entry_guards, node);
  3684. smartlist_split_string(args, line->value, " ",
  3685. SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
  3686. if (smartlist_len(args)<2) {
  3687. *msg = tor_strdup("Unable to parse entry nodes: "
  3688. "Too few arguments to EntryGuard");
  3689. } else if (!is_legal_nickname(smartlist_get(args,0))) {
  3690. *msg = tor_strdup("Unable to parse entry nodes: "
  3691. "Bad nickname for EntryGuard");
  3692. } else {
  3693. strlcpy(node->nickname, smartlist_get(args,0), MAX_NICKNAME_LEN+1);
  3694. if (base16_decode(node->identity, DIGEST_LEN, smartlist_get(args,1),
  3695. strlen(smartlist_get(args,1)))<0) {
  3696. *msg = tor_strdup("Unable to parse entry nodes: "
  3697. "Bad hex digest for EntryGuard");
  3698. }
  3699. }
  3700. SMARTLIST_FOREACH(args, char*, cp, tor_free(cp));
  3701. smartlist_free(args);
  3702. if (*msg)
  3703. break;
  3704. } else if (!strcasecmp(line->key, "EntryGuardDownSince") ||
  3705. !strcasecmp(line->key, "EntryGuardUnlistedSince")) {
  3706. time_t when;
  3707. time_t last_try = 0;
  3708. if (!node) {
  3709. *msg = tor_strdup("Unable to parse entry nodes: "
  3710. "EntryGuardDownSince/UnlistedSince without EntryGuard");
  3711. break;
  3712. }
  3713. if (parse_iso_time(line->value, &when)<0) {
  3714. *msg = tor_strdup("Unable to parse entry nodes: "
  3715. "Bad time in EntryGuardDownSince/UnlistedSince");
  3716. break;
  3717. }
  3718. if (when > now) {
  3719. /* It's a bad idea to believe info in the future: you can wind
  3720. * up with timeouts that aren't allowed to happen for years. */
  3721. continue;
  3722. }
  3723. if (strlen(line->value) >= ISO_TIME_LEN+ISO_TIME_LEN+1) {
  3724. /* ignore failure */
  3725. (void) parse_iso_time(line->value+ISO_TIME_LEN+1, &last_try);
  3726. }
  3727. if (!strcasecmp(line->key, "EntryGuardDownSince")) {
  3728. node->unreachable_since = when;
  3729. node->last_attempted = last_try;
  3730. } else {
  3731. node->bad_since = when;
  3732. }
  3733. } else if (!strcasecmp(line->key, "EntryGuardAddedBy")) {
  3734. char d[DIGEST_LEN];
  3735. /* format is digest version date */
  3736. if (strlen(line->value) < HEX_DIGEST_LEN+1+1+1+ISO_TIME_LEN) {
  3737. log_warn(LD_BUG, "EntryGuardAddedBy line is not long enough.");
  3738. continue;
  3739. }
  3740. if (base16_decode(d, sizeof(d), line->value, HEX_DIGEST_LEN)<0 ||
  3741. line->value[HEX_DIGEST_LEN] != ' ') {
  3742. log_warn(LD_BUG, "EntryGuardAddedBy line %s does not begin with "
  3743. "hex digest", escaped(line->value));
  3744. continue;
  3745. }
  3746. digestmap_set(added_by, d, tor_strdup(line->value+HEX_DIGEST_LEN+1));
  3747. } else {
  3748. log_warn(LD_BUG, "Unexpected key %s", line->key);
  3749. }
  3750. }
  3751. SMARTLIST_FOREACH(new_entry_guards, entry_guard_t *, e,
  3752. {
  3753. char *sp;
  3754. char *val = digestmap_get(added_by, e->identity);
  3755. if (val && (sp = strchr(val, ' '))) {
  3756. time_t when;
  3757. *sp++ = '\0';
  3758. if (parse_iso_time(sp, &when)<0) {
  3759. log_warn(LD_BUG, "Can't read time %s in EntryGuardAddedBy", sp);
  3760. } else {
  3761. e->chosen_by_version = tor_strdup(val);
  3762. e->chosen_on_date = when;
  3763. }
  3764. } else {
  3765. if (state_version) {
  3766. e->chosen_by_version = tor_strdup(state_version);
  3767. e->chosen_on_date = time(NULL) - crypto_rand_int(3600*24*30);
  3768. }
  3769. }
  3770. });
  3771. if (*msg || !set) {
  3772. SMARTLIST_FOREACH(new_entry_guards, entry_guard_t *, e,
  3773. entry_guard_free(e));
  3774. smartlist_free(new_entry_guards);
  3775. } else { /* !err && set */
  3776. if (entry_guards) {
  3777. SMARTLIST_FOREACH(entry_guards, entry_guard_t *, e,
  3778. entry_guard_free(e));
  3779. smartlist_free(entry_guards);
  3780. }
  3781. entry_guards = new_entry_guards;
  3782. entry_guards_dirty = 0;
  3783. /* XXX022 hand new_entry_guards to this func, and move it up a
  3784. * few lines, so we don't have to re-dirty it */
  3785. if (remove_obsolete_entry_guards(now))
  3786. entry_guards_dirty = 1;
  3787. }
  3788. digestmap_free(added_by, _tor_free);
  3789. return *msg ? -1 : 0;
  3790. }
  3791. /** Our list of entry guards has changed, or some element of one
  3792. * of our entry guards has changed. Write the changes to disk within
  3793. * the next few minutes.
  3794. */
  3795. static void
  3796. entry_guards_changed(void)
  3797. {
  3798. time_t when;
  3799. entry_guards_dirty = 1;
  3800. /* or_state_save() will call entry_guards_update_state(). */
  3801. when = get_options()->AvoidDiskWrites ? time(NULL) + 3600 : time(NULL)+600;
  3802. or_state_mark_dirty(get_or_state(), when);
  3803. }
  3804. /** If the entry guard info has not changed, do nothing and return.
  3805. * Otherwise, free the EntryGuards piece of <b>state</b> and create
  3806. * a new one out of the global entry_guards list, and then mark
  3807. * <b>state</b> dirty so it will get saved to disk.
  3808. */
  3809. void
  3810. entry_guards_update_state(or_state_t *state)
  3811. {
  3812. config_line_t **next, *line;
  3813. if (! entry_guards_dirty)
  3814. return;
  3815. config_free_lines(state->EntryGuards);
  3816. next = &state->EntryGuards;
  3817. *next = NULL;
  3818. if (!entry_guards)
  3819. entry_guards = smartlist_create();
  3820. SMARTLIST_FOREACH(entry_guards, entry_guard_t *, e,
  3821. {
  3822. char dbuf[HEX_DIGEST_LEN+1];
  3823. if (!e->made_contact)
  3824. continue; /* don't write this one to disk */
  3825. *next = line = tor_malloc_zero(sizeof(config_line_t));
  3826. line->key = tor_strdup("EntryGuard");
  3827. line->value = tor_malloc(HEX_DIGEST_LEN+MAX_NICKNAME_LEN+2);
  3828. base16_encode(dbuf, sizeof(dbuf), e->identity, DIGEST_LEN);
  3829. tor_snprintf(line->value,HEX_DIGEST_LEN+MAX_NICKNAME_LEN+2,
  3830. "%s %s", e->nickname, dbuf);
  3831. next = &(line->next);
  3832. if (e->unreachable_since) {
  3833. *next = line = tor_malloc_zero(sizeof(config_line_t));
  3834. line->key = tor_strdup("EntryGuardDownSince");
  3835. line->value = tor_malloc(ISO_TIME_LEN+1+ISO_TIME_LEN+1);
  3836. format_iso_time(line->value, e->unreachable_since);
  3837. if (e->last_attempted) {
  3838. line->value[ISO_TIME_LEN] = ' ';
  3839. format_iso_time(line->value+ISO_TIME_LEN+1, e->last_attempted);
  3840. }
  3841. next = &(line->next);
  3842. }
  3843. if (e->bad_since) {
  3844. *next = line = tor_malloc_zero(sizeof(config_line_t));
  3845. line->key = tor_strdup("EntryGuardUnlistedSince");
  3846. line->value = tor_malloc(ISO_TIME_LEN+1);
  3847. format_iso_time(line->value, e->bad_since);
  3848. next = &(line->next);
  3849. }
  3850. if (e->chosen_on_date && e->chosen_by_version &&
  3851. !strchr(e->chosen_by_version, ' ')) {
  3852. char d[HEX_DIGEST_LEN+1];
  3853. char t[ISO_TIME_LEN+1];
  3854. size_t val_len;
  3855. *next = line = tor_malloc_zero(sizeof(config_line_t));
  3856. line->key = tor_strdup("EntryGuardAddedBy");
  3857. val_len = (HEX_DIGEST_LEN+1+strlen(e->chosen_by_version)
  3858. +1+ISO_TIME_LEN+1);
  3859. line->value = tor_malloc(val_len);
  3860. base16_encode(d, sizeof(d), e->identity, DIGEST_LEN);
  3861. format_iso_time(t, e->chosen_on_date);
  3862. tor_snprintf(line->value, val_len, "%s %s %s",
  3863. d, e->chosen_by_version, t);
  3864. next = &(line->next);
  3865. }
  3866. });
  3867. if (!get_options()->AvoidDiskWrites)
  3868. or_state_mark_dirty(get_or_state(), 0);
  3869. entry_guards_dirty = 0;
  3870. }
  3871. /** If <b>question</b> is the string "entry-guards", then dump
  3872. * to *<b>answer</b> a newly allocated string describing all of
  3873. * the nodes in the global entry_guards list. See control-spec.txt
  3874. * for details.
  3875. * For backward compatibility, we also handle the string "helper-nodes".
  3876. * */
  3877. int
  3878. getinfo_helper_entry_guards(control_connection_t *conn,
  3879. const char *question, char **answer,
  3880. const char **errmsg)
  3881. {
  3882. (void) conn;
  3883. (void) errmsg;
  3884. if (!strcmp(question,"entry-guards") ||
  3885. !strcmp(question,"helper-nodes")) {
  3886. smartlist_t *sl = smartlist_create();
  3887. char tbuf[ISO_TIME_LEN+1];
  3888. char nbuf[MAX_VERBOSE_NICKNAME_LEN+1];
  3889. if (!entry_guards)
  3890. entry_guards = smartlist_create();
  3891. SMARTLIST_FOREACH_BEGIN(entry_guards, entry_guard_t *, e) {
  3892. size_t len = MAX_VERBOSE_NICKNAME_LEN+ISO_TIME_LEN+32;
  3893. char *c = tor_malloc(len);
  3894. const char *status = NULL;
  3895. time_t when = 0;
  3896. routerinfo_t *ri;
  3897. if (!e->made_contact) {
  3898. status = "never-connected";
  3899. } else if (e->bad_since) {
  3900. when = e->bad_since;
  3901. status = "unusable";
  3902. } else {
  3903. status = "up";
  3904. }
  3905. ri = router_get_by_digest(e->identity);
  3906. if (ri) {
  3907. router_get_verbose_nickname(nbuf, ri);
  3908. } else {
  3909. nbuf[0] = '$';
  3910. base16_encode(nbuf+1, sizeof(nbuf)-1, e->identity, DIGEST_LEN);
  3911. /* e->nickname field is not very reliable if we don't know about
  3912. * this router any longer; don't include it. */
  3913. }
  3914. if (when) {
  3915. format_iso_time(tbuf, when);
  3916. tor_snprintf(c, len, "%s %s %s\n", nbuf, status, tbuf);
  3917. } else {
  3918. tor_snprintf(c, len, "%s %s\n", nbuf, status);
  3919. }
  3920. smartlist_add(sl, c);
  3921. } SMARTLIST_FOREACH_END(e);
  3922. *answer = smartlist_join_strings(sl, "", 0, NULL);
  3923. SMARTLIST_FOREACH(sl, char *, c, tor_free(c));
  3924. smartlist_free(sl);
  3925. }
  3926. return 0;
  3927. }
  3928. /** Information about a configured bridge. Currently this just matches the
  3929. * ones in the torrc file, but one day we may be able to learn about new
  3930. * bridges on our own, and remember them in the state file. */
  3931. typedef struct {
  3932. /** Address of the bridge. */
  3933. tor_addr_t addr;
  3934. /** TLS port for the bridge. */
  3935. uint16_t port;
  3936. /** Expected identity digest, or all zero bytes if we don't know what the
  3937. * digest should be. */
  3938. char identity[DIGEST_LEN];
  3939. /** When should we next try to fetch a descriptor for this bridge? */
  3940. download_status_t fetch_status;
  3941. } bridge_info_t;
  3942. /** A list of configured bridges. Whenever we actually get a descriptor
  3943. * for one, we add it as an entry guard. */
  3944. static smartlist_t *bridge_list = NULL;
  3945. /** Initialize the bridge list to empty, creating it if needed. */
  3946. void
  3947. clear_bridge_list(void)
  3948. {
  3949. if (!bridge_list)
  3950. bridge_list = smartlist_create();
  3951. SMARTLIST_FOREACH(bridge_list, bridge_info_t *, b, tor_free(b));
  3952. smartlist_clear(bridge_list);
  3953. }
  3954. /** Return a bridge pointer if <b>ri</b> is one of our known bridges
  3955. * (either by comparing keys if possible, else by comparing addr/port).
  3956. * Else return NULL. */
  3957. static bridge_info_t *
  3958. get_configured_bridge_by_addr_port_digest(tor_addr_t *addr, uint16_t port,
  3959. const char *digest)
  3960. {
  3961. if (!bridge_list)
  3962. return NULL;
  3963. SMARTLIST_FOREACH_BEGIN(bridge_list, bridge_info_t *, bridge)
  3964. {
  3965. if (tor_digest_is_zero(bridge->identity) &&
  3966. !tor_addr_compare(&bridge->addr, addr, CMP_EXACT) &&
  3967. bridge->port == port)
  3968. return bridge;
  3969. if (!memcmp(bridge->identity, digest, DIGEST_LEN))
  3970. return bridge;
  3971. }
  3972. SMARTLIST_FOREACH_END(bridge);
  3973. return NULL;
  3974. }
  3975. /** Wrapper around get_configured_bridge_by_addr_port_digest() to look
  3976. * it up via router descriptor <b>ri</b>. */
  3977. static bridge_info_t *
  3978. get_configured_bridge_by_routerinfo(routerinfo_t *ri)
  3979. {
  3980. tor_addr_t addr;
  3981. tor_addr_from_ipv4h(&addr, ri->addr);
  3982. return get_configured_bridge_by_addr_port_digest(&addr,
  3983. ri->or_port, ri->cache_info.identity_digest);
  3984. }
  3985. /** Return 1 if <b>ri</b> is one of our known bridges, else 0. */
  3986. int
  3987. routerinfo_is_a_configured_bridge(routerinfo_t *ri)
  3988. {
  3989. return get_configured_bridge_by_routerinfo(ri) ? 1 : 0;
  3990. }
  3991. /** We made a connection to a router at <b>addr</b>:<b>port</b>
  3992. * without knowing its digest. Its digest turned out to be <b>digest</b>.
  3993. * If it was a bridge, and we still don't know its digest, record it.
  3994. */
  3995. void
  3996. learned_router_identity(tor_addr_t *addr, uint16_t port, const char *digest)
  3997. {
  3998. bridge_info_t *bridge =
  3999. get_configured_bridge_by_addr_port_digest(addr, port, digest);
  4000. if (bridge && tor_digest_is_zero(bridge->identity)) {
  4001. memcpy(bridge->identity, digest, DIGEST_LEN);
  4002. log_notice(LD_DIR, "Learned fingerprint %s for bridge %s:%d",
  4003. hex_str(digest, DIGEST_LEN), fmt_addr(addr), port);
  4004. }
  4005. }
  4006. /** Remember a new bridge at <b>addr</b>:<b>port</b>. If <b>digest</b>
  4007. * is set, it tells us the identity key too. */
  4008. void
  4009. bridge_add_from_config(const tor_addr_t *addr, uint16_t port, char *digest)
  4010. {
  4011. bridge_info_t *b = tor_malloc_zero(sizeof(bridge_info_t));
  4012. tor_addr_copy(&b->addr, addr);
  4013. b->port = port;
  4014. if (digest)
  4015. memcpy(b->identity, digest, DIGEST_LEN);
  4016. b->fetch_status.schedule = DL_SCHED_BRIDGE;
  4017. if (!bridge_list)
  4018. bridge_list = smartlist_create();
  4019. smartlist_add(bridge_list, b);
  4020. }
  4021. /** If <b>digest</b> is one of our known bridges, return it. */
  4022. static bridge_info_t *
  4023. find_bridge_by_digest(const char *digest)
  4024. {
  4025. SMARTLIST_FOREACH(bridge_list, bridge_info_t *, bridge,
  4026. {
  4027. if (!memcmp(bridge->identity, digest, DIGEST_LEN))
  4028. return bridge;
  4029. });
  4030. return NULL;
  4031. }
  4032. /** We need to ask <b>bridge</b> for its server descriptor. <b>address</b>
  4033. * is a helpful string describing this bridge. */
  4034. static void
  4035. launch_direct_bridge_descriptor_fetch(bridge_info_t *bridge)
  4036. {
  4037. char *address;
  4038. if (connection_get_by_type_addr_port_purpose(
  4039. CONN_TYPE_DIR, &bridge->addr, bridge->port,
  4040. DIR_PURPOSE_FETCH_SERVERDESC))
  4041. return; /* it's already on the way */
  4042. address = tor_dup_addr(&bridge->addr);
  4043. directory_initiate_command(address, &bridge->addr,
  4044. bridge->port, 0,
  4045. 0, /* does not matter */
  4046. 1, bridge->identity,
  4047. DIR_PURPOSE_FETCH_SERVERDESC,
  4048. ROUTER_PURPOSE_BRIDGE,
  4049. 0, "authority.z", NULL, 0, 0);
  4050. tor_free(address);
  4051. }
  4052. /** Fetching the bridge descriptor from the bridge authority returned a
  4053. * "not found". Fall back to trying a direct fetch. */
  4054. void
  4055. retry_bridge_descriptor_fetch_directly(const char *digest)
  4056. {
  4057. bridge_info_t *bridge = find_bridge_by_digest(digest);
  4058. if (!bridge)
  4059. return; /* not found? oh well. */
  4060. launch_direct_bridge_descriptor_fetch(bridge);
  4061. }
  4062. /** For each bridge in our list for which we don't currently have a
  4063. * descriptor, fetch a new copy of its descriptor -- either directly
  4064. * from the bridge or via a bridge authority. */
  4065. void
  4066. fetch_bridge_descriptors(or_options_t *options, time_t now)
  4067. {
  4068. int num_bridge_auths = get_n_authorities(BRIDGE_AUTHORITY);
  4069. int ask_bridge_directly;
  4070. int can_use_bridge_authority;
  4071. if (!bridge_list)
  4072. return;
  4073. SMARTLIST_FOREACH_BEGIN(bridge_list, bridge_info_t *, bridge)
  4074. {
  4075. if (!download_status_is_ready(&bridge->fetch_status, now,
  4076. IMPOSSIBLE_TO_DOWNLOAD))
  4077. continue; /* don't bother, no need to retry yet */
  4078. /* schedule another fetch as if this one will fail, in case it does */
  4079. download_status_failed(&bridge->fetch_status, 0);
  4080. can_use_bridge_authority = !tor_digest_is_zero(bridge->identity) &&
  4081. num_bridge_auths;
  4082. ask_bridge_directly = !can_use_bridge_authority ||
  4083. !options->UpdateBridgesFromAuthority;
  4084. log_debug(LD_DIR, "ask_bridge_directly=%d (%d, %d, %d)",
  4085. ask_bridge_directly, tor_digest_is_zero(bridge->identity),
  4086. !options->UpdateBridgesFromAuthority, !num_bridge_auths);
  4087. if (ask_bridge_directly &&
  4088. !fascist_firewall_allows_address_or(&bridge->addr, bridge->port)) {
  4089. log_notice(LD_DIR, "Bridge at '%s:%d' isn't reachable by our "
  4090. "firewall policy. %s.", fmt_addr(&bridge->addr),
  4091. bridge->port,
  4092. can_use_bridge_authority ?
  4093. "Asking bridge authority instead" : "Skipping");
  4094. if (can_use_bridge_authority)
  4095. ask_bridge_directly = 0;
  4096. else
  4097. continue;
  4098. }
  4099. if (ask_bridge_directly) {
  4100. /* we need to ask the bridge itself for its descriptor. */
  4101. launch_direct_bridge_descriptor_fetch(bridge);
  4102. } else {
  4103. /* We have a digest and we want to ask an authority. We could
  4104. * combine all the requests into one, but that may give more
  4105. * hints to the bridge authority than we want to give. */
  4106. char resource[10 + HEX_DIGEST_LEN];
  4107. memcpy(resource, "fp/", 3);
  4108. base16_encode(resource+3, HEX_DIGEST_LEN+1,
  4109. bridge->identity, DIGEST_LEN);
  4110. memcpy(resource+3+HEX_DIGEST_LEN, ".z", 3);
  4111. log_info(LD_DIR, "Fetching bridge info '%s' from bridge authority.",
  4112. resource);
  4113. directory_get_from_dirserver(DIR_PURPOSE_FETCH_SERVERDESC,
  4114. ROUTER_PURPOSE_BRIDGE, resource, 0);
  4115. }
  4116. }
  4117. SMARTLIST_FOREACH_END(bridge);
  4118. }
  4119. /** We just learned a descriptor for a bridge. See if that
  4120. * digest is in our entry guard list, and add it if not. */
  4121. void
  4122. learned_bridge_descriptor(routerinfo_t *ri, int from_cache)
  4123. {
  4124. tor_assert(ri);
  4125. tor_assert(ri->purpose == ROUTER_PURPOSE_BRIDGE);
  4126. if (get_options()->UseBridges) {
  4127. int first = !any_bridge_descriptors_known();
  4128. bridge_info_t *bridge = get_configured_bridge_by_routerinfo(ri);
  4129. time_t now = time(NULL);
  4130. ri->is_running = 1;
  4131. if (bridge) { /* if we actually want to use this one */
  4132. /* it's here; schedule its re-fetch for a long time from now. */
  4133. if (!from_cache)
  4134. download_status_reset(&bridge->fetch_status);
  4135. add_an_entry_guard(ri, 1);
  4136. log_notice(LD_DIR, "new bridge descriptor '%s' (%s)", ri->nickname,
  4137. from_cache ? "cached" : "fresh");
  4138. /* set entry->made_contact so if it goes down we don't drop it from
  4139. * our entry node list */
  4140. entry_guard_register_connect_status(ri->cache_info.identity_digest,
  4141. 1, 0, now);
  4142. if (first)
  4143. routerlist_retry_directory_downloads(now);
  4144. }
  4145. }
  4146. }
  4147. /** Return 1 if any of our entry guards have descriptors that
  4148. * are marked with purpose 'bridge' and are running. Else return 0.
  4149. *
  4150. * We use this function to decide if we're ready to start building
  4151. * circuits through our bridges, or if we need to wait until the
  4152. * directory "server/authority" requests finish. */
  4153. int
  4154. any_bridge_descriptors_known(void)
  4155. {
  4156. tor_assert(get_options()->UseBridges);
  4157. return choose_random_entry(NULL)!=NULL ? 1 : 0;
  4158. }
  4159. /** Return 1 if there are any directory conns fetching bridge descriptors
  4160. * that aren't marked for close. We use this to guess if we should tell
  4161. * the controller that we have a problem. */
  4162. int
  4163. any_pending_bridge_descriptor_fetches(void)
  4164. {
  4165. smartlist_t *conns = get_connection_array();
  4166. SMARTLIST_FOREACH(conns, connection_t *, conn,
  4167. {
  4168. if (conn->type == CONN_TYPE_DIR &&
  4169. conn->purpose == DIR_PURPOSE_FETCH_SERVERDESC &&
  4170. TO_DIR_CONN(conn)->router_purpose == ROUTER_PURPOSE_BRIDGE &&
  4171. !conn->marked_for_close &&
  4172. conn->linked && !conn->linked_conn->marked_for_close) {
  4173. log_debug(LD_DIR, "found one: %s", conn->address);
  4174. return 1;
  4175. }
  4176. });
  4177. return 0;
  4178. }
  4179. /** Return 1 if we have at least one descriptor for an entry guard
  4180. * (bridge or member of EntryNodes) and all descriptors we know are
  4181. * down. Else return 0. If <b>act</b> is 1, then mark the down guards
  4182. * up; else just observe and report. */
  4183. static int
  4184. entries_retry_helper(or_options_t *options, int act)
  4185. {
  4186. routerinfo_t *ri;
  4187. int any_known = 0;
  4188. int any_running = 0;
  4189. int purpose = options->UseBridges ?
  4190. ROUTER_PURPOSE_BRIDGE : ROUTER_PURPOSE_GENERAL;
  4191. if (!entry_guards)
  4192. entry_guards = smartlist_create();
  4193. SMARTLIST_FOREACH(entry_guards, entry_guard_t *, e,
  4194. {
  4195. ri = router_get_by_digest(e->identity);
  4196. if (ri && ri->purpose == purpose) {
  4197. any_known = 1;
  4198. if (ri->is_running)
  4199. any_running = 1; /* some entry is both known and running */
  4200. else if (act) {
  4201. /* Mark all current connections to this OR as unhealthy, since
  4202. * otherwise there could be one that started 30 seconds
  4203. * ago, and in 30 seconds it will time out, causing us to mark
  4204. * the node down and undermine the retry attempt. We mark even
  4205. * the established conns, since if the network just came back
  4206. * we'll want to attach circuits to fresh conns. */
  4207. connection_or_set_bad_connections(ri->cache_info.identity_digest, 1);
  4208. /* mark this entry node for retry */
  4209. router_set_status(ri->cache_info.identity_digest, 1);
  4210. e->can_retry = 1;
  4211. e->bad_since = 0;
  4212. }
  4213. }
  4214. });
  4215. log_debug(LD_DIR, "%d: any_known %d, any_running %d",
  4216. act, any_known, any_running);
  4217. return any_known && !any_running;
  4218. }
  4219. /** Do we know any descriptors for our bridges / entrynodes, and are
  4220. * all the ones we have descriptors for down? */
  4221. int
  4222. entries_known_but_down(or_options_t *options)
  4223. {
  4224. tor_assert(entry_list_is_constrained(options));
  4225. return entries_retry_helper(options, 0);
  4226. }
  4227. /** Mark all down known bridges / entrynodes up. */
  4228. void
  4229. entries_retry_all(or_options_t *options)
  4230. {
  4231. tor_assert(entry_list_is_constrained(options));
  4232. entries_retry_helper(options, 1);
  4233. }
  4234. /** Release all storage held by the list of entry guards and related
  4235. * memory structs. */
  4236. void
  4237. entry_guards_free_all(void)
  4238. {
  4239. if (entry_guards) {
  4240. SMARTLIST_FOREACH(entry_guards, entry_guard_t *, e,
  4241. entry_guard_free(e));
  4242. smartlist_free(entry_guards);
  4243. entry_guards = NULL;
  4244. }
  4245. clear_bridge_list();
  4246. smartlist_free(bridge_list);
  4247. bridge_list = NULL;
  4248. }