circuitbuild.c 164 KB

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