circuitbuild.c 181 KB

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