circuitstats.c 61 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844184518461847184818491850185118521853185418551856185718581859186018611862186318641865186618671868186918701871187218731874187518761877187818791880188118821883188418851886188718881889189018911892189318941895189618971898189919001901190219031904190519061907190819091910191119121913191419151916191719181919192019211922192319241925192619271928192919301931193219331934193519361937
  1. /* Copyright (c) 2001 Matej Pfajfar.
  2. * Copyright (c) 2001-2004, Roger Dingledine.
  3. * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
  4. * Copyright (c) 2007-2017, The Tor Project, Inc. */
  5. /* See LICENSE for licensing information */
  6. /**
  7. * \file circuitstats.c
  8. *
  9. * \brief Maintains and analyzes statistics about circuit built times, so we
  10. * can tell how long we may need to wait for a fast circuit to be constructed.
  11. *
  12. * By keeping these statistics, a client learns when it should time out a slow
  13. * circuit for being too slow, and when it should keep a circuit open in order
  14. * to wait for it to complete.
  15. *
  16. * The information here is kept in a circuit_built_times_t structure, which is
  17. * currently a singleton, but doesn't need to be. It's updated by calls to
  18. * circuit_build_times_count_timeout() from circuituse.c,
  19. * circuit_build_times_count_close() from circuituse.c, and
  20. * circuit_build_times_add_time() from circuitbuild.c, and inspected by other
  21. * calls into this module, mostly from circuitlist.c. Observations are
  22. * persisted to disk via the or_state_t-related calls.
  23. */
  24. #define CIRCUITSTATS_PRIVATE
  25. #include "or.h"
  26. #include "circuitbuild.h"
  27. #include "circuitstats.h"
  28. #include "config.h"
  29. #include "confparse.h"
  30. #include "control.h"
  31. #include "main.h"
  32. #include "networkstatus.h"
  33. #include "rendclient.h"
  34. #include "rendservice.h"
  35. #include "statefile.h"
  36. #include "circuitlist.h"
  37. #include "circuituse.h"
  38. #undef log
  39. #include <math.h>
  40. static void cbt_control_event_buildtimeout_set(
  41. const circuit_build_times_t *cbt,
  42. buildtimeout_set_event_t type);
  43. static void circuit_build_times_scale_circ_counts(circuit_build_times_t *cbt);
  44. #define CBT_BIN_TO_MS(bin) ((bin)*CBT_BIN_WIDTH + (CBT_BIN_WIDTH/2))
  45. /** Global list of circuit build times */
  46. // XXXX: Add this as a member for entry_guard_t instead of global?
  47. // Then we could do per-guard statistics, as guards are likely to
  48. // vary in their own latency. The downside of this is that guards
  49. // can change frequently, so we'd be building a lot more circuits
  50. // most likely.
  51. static circuit_build_times_t circ_times;
  52. #ifdef TOR_UNIT_TESTS
  53. /** If set, we're running the unit tests: we should avoid clobbering
  54. * our state file or accessing get_options() or get_or_state() */
  55. static int unit_tests = 0;
  56. #else
  57. #define unit_tests 0
  58. #endif /* defined(TOR_UNIT_TESTS) */
  59. /** Return a pointer to the data structure describing our current circuit
  60. * build time history and computations. */
  61. const circuit_build_times_t *
  62. get_circuit_build_times(void)
  63. {
  64. return &circ_times;
  65. }
  66. /** As get_circuit_build_times, but return a mutable pointer. */
  67. circuit_build_times_t *
  68. get_circuit_build_times_mutable(void)
  69. {
  70. return &circ_times;
  71. }
  72. /** Return the time to wait before actually closing an under-construction, in
  73. * milliseconds. */
  74. double
  75. get_circuit_build_close_time_ms(void)
  76. {
  77. return circ_times.close_ms;
  78. }
  79. /** Return the time to wait before giving up on an under-construction circuit,
  80. * in milliseconds. */
  81. double
  82. get_circuit_build_timeout_ms(void)
  83. {
  84. return circ_times.timeout_ms;
  85. }
  86. /**
  87. * This function decides if CBT learning should be disabled. It returns
  88. * true if one or more of the following conditions are met:
  89. *
  90. * 1. If the cbtdisabled consensus parameter is set.
  91. * 2. If the torrc option LearnCircuitBuildTimeout is false.
  92. * 3. If we are a directory authority
  93. * 4. If we fail to write circuit build time history to our state file.
  94. * 5. If we are compiled or configured in Tor2web mode
  95. * 6. If we are configured in Single Onion mode
  96. */
  97. int
  98. circuit_build_times_disabled(const or_options_t *options)
  99. {
  100. return circuit_build_times_disabled_(options, 0);
  101. }
  102. /** As circuit_build_times_disabled, but take options as an argument. */
  103. int
  104. circuit_build_times_disabled_(const or_options_t *options,
  105. int ignore_consensus)
  106. {
  107. if (unit_tests) {
  108. return 0;
  109. } else {
  110. int consensus_disabled =
  111. ignore_consensus ? 0 : networkstatus_get_param(NULL, "cbtdisabled",
  112. 0, 0, 1);
  113. int config_disabled = !options->LearnCircuitBuildTimeout;
  114. int dirauth_disabled = options->AuthoritativeDir;
  115. int state_disabled = did_last_state_file_write_fail() ? 1 : 0;
  116. /* LearnCircuitBuildTimeout and Tor2web/Single Onion Services are
  117. * incompatible in two ways:
  118. *
  119. * - LearnCircuitBuildTimeout results in a low CBT, which
  120. * Single Onion use of one-hop intro and rendezvous circuits lowers
  121. * much further, producing *far* too many timeouts.
  122. *
  123. * - The adaptive CBT code does not update its timeout estimate
  124. * using build times for single-hop circuits.
  125. *
  126. * If we fix both of these issues someday, we should test
  127. * these modes with LearnCircuitBuildTimeout on again. */
  128. int tor2web_disabled = rend_client_allow_non_anonymous_connection(options);
  129. int single_onion_disabled = rend_service_allow_non_anonymous_connection(
  130. options);
  131. if (consensus_disabled || config_disabled || dirauth_disabled ||
  132. state_disabled || tor2web_disabled || single_onion_disabled) {
  133. #if 0
  134. log_debug(LD_CIRC,
  135. "CircuitBuildTime learning is disabled. "
  136. "Consensus=%d, Config=%d, AuthDir=%d, StateFile=%d",
  137. consensus_disabled, config_disabled, dirauth_disabled,
  138. state_disabled);
  139. #endif /* 0 */
  140. return 1;
  141. } else {
  142. #if 0
  143. log_debug(LD_CIRC,
  144. "CircuitBuildTime learning is not disabled. "
  145. "Consensus=%d, Config=%d, AuthDir=%d, StateFile=%d",
  146. consensus_disabled, config_disabled, dirauth_disabled,
  147. state_disabled);
  148. #endif /* 0 */
  149. return 0;
  150. }
  151. }
  152. }
  153. /**
  154. * Retrieve and bounds-check the cbtmaxtimeouts consensus parameter.
  155. *
  156. * Effect: When this many timeouts happen in the last 'cbtrecentcount'
  157. * circuit attempts, the client should discard all of its history and
  158. * begin learning a fresh timeout value.
  159. */
  160. static int32_t
  161. circuit_build_times_max_timeouts(void)
  162. {
  163. int32_t cbt_maxtimeouts;
  164. cbt_maxtimeouts = networkstatus_get_param(NULL, "cbtmaxtimeouts",
  165. CBT_DEFAULT_MAX_RECENT_TIMEOUT_COUNT,
  166. CBT_MIN_MAX_RECENT_TIMEOUT_COUNT,
  167. CBT_MAX_MAX_RECENT_TIMEOUT_COUNT);
  168. if (!(get_options()->LearnCircuitBuildTimeout)) {
  169. log_debug(LD_BUG,
  170. "circuit_build_times_max_timeouts() called, cbtmaxtimeouts is"
  171. " %d",
  172. cbt_maxtimeouts);
  173. }
  174. return cbt_maxtimeouts;
  175. }
  176. /**
  177. * Retrieve and bounds-check the cbtnummodes consensus parameter.
  178. *
  179. * Effect: This value governs how many modes to use in the weighted
  180. * average calculation of Pareto parameter Xm. A value of 3 introduces
  181. * some bias (2-5% of CDF) under ideal conditions, but allows for better
  182. * performance in the event that a client chooses guard nodes of radically
  183. * different performance characteristics.
  184. */
  185. static int32_t
  186. circuit_build_times_default_num_xm_modes(void)
  187. {
  188. int32_t num = networkstatus_get_param(NULL, "cbtnummodes",
  189. CBT_DEFAULT_NUM_XM_MODES,
  190. CBT_MIN_NUM_XM_MODES,
  191. CBT_MAX_NUM_XM_MODES);
  192. if (!(get_options()->LearnCircuitBuildTimeout)) {
  193. log_debug(LD_BUG,
  194. "circuit_build_times_default_num_xm_modes() called, cbtnummodes"
  195. " is %d",
  196. num);
  197. }
  198. return num;
  199. }
  200. /**
  201. * Retrieve and bounds-check the cbtmincircs consensus parameter.
  202. *
  203. * Effect: This is the minimum number of circuits to build before
  204. * computing a timeout.
  205. */
  206. static int32_t
  207. circuit_build_times_min_circs_to_observe(void)
  208. {
  209. int32_t num = networkstatus_get_param(NULL, "cbtmincircs",
  210. CBT_DEFAULT_MIN_CIRCUITS_TO_OBSERVE,
  211. CBT_MIN_MIN_CIRCUITS_TO_OBSERVE,
  212. CBT_MAX_MIN_CIRCUITS_TO_OBSERVE);
  213. if (!(get_options()->LearnCircuitBuildTimeout)) {
  214. log_debug(LD_BUG,
  215. "circuit_build_times_min_circs_to_observe() called, cbtmincircs"
  216. " is %d",
  217. num);
  218. }
  219. return num;
  220. }
  221. /** Return true iff <b>cbt</b> has recorded enough build times that we
  222. * want to start acting on the timeout it implies. */
  223. int
  224. circuit_build_times_enough_to_compute(const circuit_build_times_t *cbt)
  225. {
  226. return cbt->total_build_times >= circuit_build_times_min_circs_to_observe();
  227. }
  228. /**
  229. * Retrieve and bounds-check the cbtquantile consensus parameter.
  230. *
  231. * Effect: This is the position on the quantile curve to use to set the
  232. * timeout value. It is a percent (10-99).
  233. */
  234. double
  235. circuit_build_times_quantile_cutoff(void)
  236. {
  237. int32_t num = networkstatus_get_param(NULL, "cbtquantile",
  238. CBT_DEFAULT_QUANTILE_CUTOFF,
  239. CBT_MIN_QUANTILE_CUTOFF,
  240. CBT_MAX_QUANTILE_CUTOFF);
  241. if (!(get_options()->LearnCircuitBuildTimeout)) {
  242. log_debug(LD_BUG,
  243. "circuit_build_times_quantile_cutoff() called, cbtquantile"
  244. " is %d",
  245. num);
  246. }
  247. return num/100.0;
  248. }
  249. /**
  250. * Retrieve and bounds-check the cbtclosequantile consensus parameter.
  251. *
  252. * Effect: This is the position on the quantile curve to use to set the
  253. * timeout value to use to actually close circuits. It is a percent
  254. * (0-99).
  255. */
  256. static double
  257. circuit_build_times_close_quantile(void)
  258. {
  259. int32_t param;
  260. /* Cast is safe - circuit_build_times_quantile_cutoff() is capped */
  261. int32_t min = (int)tor_lround(100*circuit_build_times_quantile_cutoff());
  262. param = networkstatus_get_param(NULL, "cbtclosequantile",
  263. CBT_DEFAULT_CLOSE_QUANTILE,
  264. CBT_MIN_CLOSE_QUANTILE,
  265. CBT_MAX_CLOSE_QUANTILE);
  266. if (!(get_options()->LearnCircuitBuildTimeout)) {
  267. log_debug(LD_BUG,
  268. "circuit_build_times_close_quantile() called, cbtclosequantile"
  269. " is %d", param);
  270. }
  271. if (param < min) {
  272. log_warn(LD_DIR, "Consensus parameter cbtclosequantile is "
  273. "too small, raising to %d", min);
  274. param = min;
  275. }
  276. return param / 100.0;
  277. }
  278. /**
  279. * Retrieve and bounds-check the cbttestfreq consensus parameter.
  280. *
  281. * Effect: Describes how often in seconds to build a test circuit to
  282. * gather timeout values. Only applies if less than 'cbtmincircs'
  283. * have been recorded.
  284. */
  285. static int32_t
  286. circuit_build_times_test_frequency(void)
  287. {
  288. int32_t num = networkstatus_get_param(NULL, "cbttestfreq",
  289. CBT_DEFAULT_TEST_FREQUENCY,
  290. CBT_MIN_TEST_FREQUENCY,
  291. CBT_MAX_TEST_FREQUENCY);
  292. if (!(get_options()->LearnCircuitBuildTimeout)) {
  293. log_debug(LD_BUG,
  294. "circuit_build_times_test_frequency() called, cbttestfreq is %d",
  295. num);
  296. }
  297. return num;
  298. }
  299. /**
  300. * Retrieve and bounds-check the cbtmintimeout consensus parameter.
  301. *
  302. * Effect: This is the minimum allowed timeout value in milliseconds.
  303. * The minimum is to prevent rounding to 0 (we only check once
  304. * per second).
  305. */
  306. static int32_t
  307. circuit_build_times_min_timeout(void)
  308. {
  309. int32_t num = networkstatus_get_param(NULL, "cbtmintimeout",
  310. CBT_DEFAULT_TIMEOUT_MIN_VALUE,
  311. CBT_MIN_TIMEOUT_MIN_VALUE,
  312. CBT_MAX_TIMEOUT_MIN_VALUE);
  313. if (!(get_options()->LearnCircuitBuildTimeout)) {
  314. log_debug(LD_BUG,
  315. "circuit_build_times_min_timeout() called, cbtmintimeout is %d",
  316. num);
  317. }
  318. return num;
  319. }
  320. /**
  321. * Retrieve and bounds-check the cbtinitialtimeout consensus parameter.
  322. *
  323. * Effect: This is the timeout value to use before computing a timeout,
  324. * in milliseconds.
  325. */
  326. int32_t
  327. circuit_build_times_initial_timeout(void)
  328. {
  329. int32_t min = circuit_build_times_min_timeout();
  330. int32_t param = networkstatus_get_param(NULL, "cbtinitialtimeout",
  331. CBT_DEFAULT_TIMEOUT_INITIAL_VALUE,
  332. CBT_MIN_TIMEOUT_INITIAL_VALUE,
  333. CBT_MAX_TIMEOUT_INITIAL_VALUE);
  334. if (!(get_options()->LearnCircuitBuildTimeout)) {
  335. log_debug(LD_BUG,
  336. "circuit_build_times_initial_timeout() called, "
  337. "cbtinitialtimeout is %d",
  338. param);
  339. }
  340. if (param < min) {
  341. log_warn(LD_DIR, "Consensus parameter cbtinitialtimeout is too small, "
  342. "raising to %d", min);
  343. param = min;
  344. }
  345. return param;
  346. }
  347. /**
  348. * Retrieve and bounds-check the cbtrecentcount consensus parameter.
  349. *
  350. * Effect: This is the number of circuit build times to keep track of
  351. * for deciding if we hit cbtmaxtimeouts and need to reset our state
  352. * and learn a new timeout.
  353. */
  354. static int32_t
  355. circuit_build_times_recent_circuit_count(networkstatus_t *ns)
  356. {
  357. int32_t num;
  358. num = networkstatus_get_param(ns, "cbtrecentcount",
  359. CBT_DEFAULT_RECENT_CIRCUITS,
  360. CBT_MIN_RECENT_CIRCUITS,
  361. CBT_MAX_RECENT_CIRCUITS);
  362. if (!(get_options()->LearnCircuitBuildTimeout)) {
  363. log_debug(LD_BUG,
  364. "circuit_build_times_recent_circuit_count() called, "
  365. "cbtrecentcount is %d",
  366. num);
  367. }
  368. return num;
  369. }
  370. /**
  371. * This function is called when we get a consensus update.
  372. *
  373. * It checks to see if we have changed any consensus parameters
  374. * that require reallocation or discard of previous stats.
  375. */
  376. void
  377. circuit_build_times_new_consensus_params(circuit_build_times_t *cbt,
  378. networkstatus_t *ns)
  379. {
  380. int32_t num;
  381. /*
  382. * First check if we're doing adaptive timeouts at all; nothing to
  383. * update if we aren't.
  384. */
  385. if (!circuit_build_times_disabled(get_options())) {
  386. num = circuit_build_times_recent_circuit_count(ns);
  387. if (num > 0) {
  388. if (num != cbt->liveness.num_recent_circs) {
  389. int8_t *recent_circs;
  390. if (cbt->liveness.num_recent_circs > 0) {
  391. log_notice(LD_CIRC, "The Tor Directory Consensus has changed how "
  392. "many circuits we must track to detect network failures "
  393. "from %d to %d.", cbt->liveness.num_recent_circs, num);
  394. } else {
  395. log_notice(LD_CIRC, "Upon receiving a consensus directory, "
  396. "re-enabling circuit-based network failure detection.");
  397. }
  398. tor_assert(cbt->liveness.timeouts_after_firsthop ||
  399. cbt->liveness.num_recent_circs == 0);
  400. /*
  401. * Technically this is a circular array that we are reallocating
  402. * and memcopying. However, since it only consists of either 1s
  403. * or 0s, and is only used in a statistical test to determine when
  404. * we should discard our history after a sufficient number of 1's
  405. * have been reached, it is fine if order is not preserved or
  406. * elements are lost.
  407. *
  408. * cbtrecentcount should only be changing in cases of severe network
  409. * distress anyway, so memory correctness here is paramount over
  410. * doing acrobatics to preserve the array.
  411. */
  412. recent_circs = tor_calloc(num, sizeof(int8_t));
  413. if (cbt->liveness.timeouts_after_firsthop &&
  414. cbt->liveness.num_recent_circs > 0) {
  415. memcpy(recent_circs, cbt->liveness.timeouts_after_firsthop,
  416. sizeof(int8_t)*MIN(num, cbt->liveness.num_recent_circs));
  417. }
  418. // Adjust the index if it needs it.
  419. if (num < cbt->liveness.num_recent_circs) {
  420. cbt->liveness.after_firsthop_idx = MIN(num-1,
  421. cbt->liveness.after_firsthop_idx);
  422. }
  423. tor_free(cbt->liveness.timeouts_after_firsthop);
  424. cbt->liveness.timeouts_after_firsthop = recent_circs;
  425. cbt->liveness.num_recent_circs = num;
  426. }
  427. /* else no change, nothing to do */
  428. } else { /* num == 0 */
  429. /*
  430. * Weird. This probably shouldn't happen, so log a warning, but try
  431. * to do something sensible anyway.
  432. */
  433. log_warn(LD_CIRC,
  434. "The cbtrecentcircs consensus parameter came back zero! "
  435. "This disables adaptive timeouts since we can't keep track of "
  436. "any recent circuits.");
  437. circuit_build_times_free_timeouts(cbt);
  438. }
  439. } else {
  440. /*
  441. * Adaptive timeouts are disabled; this might be because of the
  442. * LearnCircuitBuildTimes config parameter, and hence permanent, or
  443. * the cbtdisabled consensus parameter, so it may be a new condition.
  444. * Treat it like getting num == 0 above and free the circuit history
  445. * if we have any.
  446. */
  447. circuit_build_times_free_timeouts(cbt);
  448. }
  449. }
  450. /**
  451. * Return the initial default or configured timeout in milliseconds
  452. */
  453. static double
  454. circuit_build_times_get_initial_timeout(void)
  455. {
  456. double timeout;
  457. const or_options_t *options = get_options();
  458. /*
  459. * Check if we have LearnCircuitBuildTimeout, and if we don't,
  460. * always use CircuitBuildTimeout, no questions asked.
  461. */
  462. if (!unit_tests && options->CircuitBuildTimeout) {
  463. timeout = options->CircuitBuildTimeout*1000;
  464. if (!circuit_build_times_disabled(options) &&
  465. timeout < circuit_build_times_min_timeout()) {
  466. log_warn(LD_CIRC, "Config CircuitBuildTimeout too low. Setting to %ds",
  467. circuit_build_times_min_timeout()/1000);
  468. timeout = circuit_build_times_min_timeout();
  469. }
  470. } else {
  471. timeout = circuit_build_times_initial_timeout();
  472. }
  473. return timeout;
  474. }
  475. /**
  476. * Reset the build time state.
  477. *
  478. * Leave estimated parameters, timeout and network liveness intact
  479. * for future use.
  480. */
  481. STATIC void
  482. circuit_build_times_reset(circuit_build_times_t *cbt)
  483. {
  484. memset(cbt->circuit_build_times, 0, sizeof(cbt->circuit_build_times));
  485. cbt->total_build_times = 0;
  486. cbt->build_times_idx = 0;
  487. cbt->have_computed_timeout = 0;
  488. // Reset timeout and close counts
  489. cbt->num_circ_succeeded = 0;
  490. cbt->num_circ_closed = 0;
  491. cbt->num_circ_timeouts = 0;
  492. }
  493. /**
  494. * Initialize the buildtimes structure for first use.
  495. *
  496. * Sets the initial timeout values based on either the config setting,
  497. * the consensus param, or the default (CBT_DEFAULT_TIMEOUT_INITIAL_VALUE).
  498. */
  499. void
  500. circuit_build_times_init(circuit_build_times_t *cbt)
  501. {
  502. memset(cbt, 0, sizeof(*cbt));
  503. /*
  504. * Check if we really are using adaptive timeouts, and don't keep
  505. * track of this stuff if not.
  506. */
  507. if (!circuit_build_times_disabled(get_options())) {
  508. cbt->liveness.num_recent_circs =
  509. circuit_build_times_recent_circuit_count(NULL);
  510. cbt->liveness.timeouts_after_firsthop =
  511. tor_calloc(cbt->liveness.num_recent_circs, sizeof(int8_t));
  512. } else {
  513. cbt->liveness.num_recent_circs = 0;
  514. cbt->liveness.timeouts_after_firsthop = NULL;
  515. }
  516. cbt->close_ms = cbt->timeout_ms = circuit_build_times_get_initial_timeout();
  517. cbt_control_event_buildtimeout_set(cbt, BUILDTIMEOUT_SET_EVENT_RESET);
  518. }
  519. /**
  520. * Free the saved timeouts, if the cbtdisabled consensus parameter got turned
  521. * on or something.
  522. */
  523. void
  524. circuit_build_times_free_timeouts(circuit_build_times_t *cbt)
  525. {
  526. if (!cbt) return;
  527. if (cbt->liveness.timeouts_after_firsthop) {
  528. tor_free(cbt->liveness.timeouts_after_firsthop);
  529. }
  530. cbt->liveness.num_recent_circs = 0;
  531. }
  532. #if 0
  533. /**
  534. * Rewind our build time history by n positions.
  535. */
  536. static void
  537. circuit_build_times_rewind_history(circuit_build_times_t *cbt, int n)
  538. {
  539. int i = 0;
  540. cbt->build_times_idx -= n;
  541. cbt->build_times_idx %= CBT_NCIRCUITS_TO_OBSERVE;
  542. for (i = 0; i < n; i++) {
  543. cbt->circuit_build_times[(i+cbt->build_times_idx)
  544. %CBT_NCIRCUITS_TO_OBSERVE]=0;
  545. }
  546. if (cbt->total_build_times > n) {
  547. cbt->total_build_times -= n;
  548. } else {
  549. cbt->total_build_times = 0;
  550. }
  551. log_info(LD_CIRC,
  552. "Rewound history by %d places. Current index: %d. "
  553. "Total: %d", n, cbt->build_times_idx, cbt->total_build_times);
  554. }
  555. #endif /* 0 */
  556. /**
  557. * Mark this circuit as timed out, but change its purpose
  558. * so that it continues to build, allowing us to measure
  559. * its full build time.
  560. */
  561. void
  562. circuit_build_times_mark_circ_as_measurement_only(origin_circuit_t *circ)
  563. {
  564. control_event_circuit_status(circ,
  565. CIRC_EVENT_FAILED,
  566. END_CIRC_REASON_TIMEOUT);
  567. circuit_change_purpose(TO_CIRCUIT(circ),
  568. CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT);
  569. /* Record this event to check for too many timeouts
  570. * in a row. This function does not record a time value yet
  571. * (we do that later); it only counts the fact that we did
  572. * have a timeout. We also want to avoid double-counting
  573. * already "relaxed" circuits, which are counted in
  574. * circuit_expire_building(). */
  575. if (!circ->relaxed_timeout) {
  576. int first_hop_succeeded = circ->cpath &&
  577. circ->cpath->state == CPATH_STATE_OPEN;
  578. circuit_build_times_count_timeout(
  579. get_circuit_build_times_mutable(),
  580. first_hop_succeeded);
  581. }
  582. }
  583. /**
  584. * Perform the build time work that needs to be done when a circuit
  585. * completes a hop.
  586. *
  587. * This function decides if we should record a circuit's build time
  588. * in our histogram data and other statistics, and if so, records it.
  589. * It also will mark circuits that have already timed out as
  590. * measurement-only circuits, so they can continue to build but
  591. * not get used.
  592. *
  593. * For this, we want to consider circuits that will eventually make
  594. * it to the third hop. For circuits longer than 3 hops, we want to
  595. * record their build time when they reach the third hop, but let
  596. * them continue (and not count them later). For circuits that are
  597. * exactly 3 hops, this will count them when they are completed. We
  598. * do this so that CBT is always gathering statistics on circuits
  599. * of the same length, regardless of their type.
  600. */
  601. void
  602. circuit_build_times_handle_completed_hop(origin_circuit_t *circ)
  603. {
  604. struct timeval end;
  605. long timediff;
  606. /* If circuit build times are disabled, let circuit_expire_building()
  607. * handle it.. */
  608. if (circuit_build_times_disabled(get_options())) {
  609. return;
  610. }
  611. /* Is this a circuit for which the timeout applies in a straight-forward
  612. * way? If so, handle it below. If not, just return (and let
  613. * circuit_expire_building() eventually take care of it).
  614. */
  615. if (!circuit_timeout_want_to_count_circ(circ)) {
  616. return;
  617. }
  618. tor_gettimeofday(&end);
  619. timediff = tv_mdiff(&circ->base_.timestamp_began, &end);
  620. /* Check if we would have timed out already. If so, change the
  621. * purpose here. But don't do any timeout handling here if there
  622. * are no circuits opened yet. Save it for circuit_expire_building()
  623. * (to allow it to handle timeout "relaxing" over there). */
  624. if (timediff > get_circuit_build_timeout_ms() &&
  625. circuit_any_opened_circuits_cached()) {
  626. /* Circuits are allowed to last longer for measurement.
  627. * Switch their purpose and wait. */
  628. if (circ->base_.purpose != CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT) {
  629. log_info(LD_CIRC,
  630. "Deciding to timeout circuit "U64_FORMAT"\n",
  631. U64_PRINTF_ARG(circ->global_identifier));
  632. circuit_build_times_mark_circ_as_measurement_only(circ);
  633. }
  634. }
  635. /* If the circuit is built to exactly the DEFAULT_ROUTE_LEN,
  636. * add it to our buildtimes. */
  637. if (circuit_get_cpath_opened_len(circ) == DEFAULT_ROUTE_LEN) {
  638. /* If the circuit build time is much greater than we would have cut
  639. * it off at, we probably had a suspend event along this codepath,
  640. * and we should discard the value.
  641. */
  642. if (timediff < 0 ||
  643. timediff > 2*get_circuit_build_close_time_ms()+1000) {
  644. log_notice(LD_CIRC, "Strange value for circuit build time: %ldmsec. "
  645. "Assuming clock jump. Purpose %d (%s)", timediff,
  646. circ->base_.purpose,
  647. circuit_purpose_to_string(circ->base_.purpose));
  648. } else {
  649. /* Only count circuit times if the network is live */
  650. if (circuit_build_times_network_check_live(
  651. get_circuit_build_times())) {
  652. circuit_build_times_add_time(get_circuit_build_times_mutable(),
  653. (build_time_t)timediff);
  654. circuit_build_times_set_timeout(get_circuit_build_times_mutable());
  655. }
  656. if (circ->base_.purpose != CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT) {
  657. circuit_build_times_network_circ_success(
  658. get_circuit_build_times_mutable());
  659. }
  660. }
  661. }
  662. }
  663. /**
  664. * Add a new build time value <b>time</b> to the set of build times. Time
  665. * units are milliseconds.
  666. *
  667. * circuit_build_times <b>cbt</b> is a circular array, so loop around when
  668. * array is full.
  669. */
  670. int
  671. circuit_build_times_add_time(circuit_build_times_t *cbt, build_time_t btime)
  672. {
  673. if (btime <= 0 || btime > CBT_BUILD_TIME_MAX) {
  674. log_warn(LD_BUG, "Circuit build time is too large (%u)."
  675. "This is probably a bug.", btime);
  676. tor_fragile_assert();
  677. return -1;
  678. }
  679. log_debug(LD_CIRC, "Adding circuit build time %u", btime);
  680. cbt->circuit_build_times[cbt->build_times_idx] = btime;
  681. cbt->build_times_idx = (cbt->build_times_idx + 1) % CBT_NCIRCUITS_TO_OBSERVE;
  682. if (cbt->total_build_times < CBT_NCIRCUITS_TO_OBSERVE)
  683. cbt->total_build_times++;
  684. if ((cbt->total_build_times % CBT_SAVE_STATE_EVERY) == 0) {
  685. /* Save state every n circuit builds */
  686. if (!unit_tests && !get_options()->AvoidDiskWrites)
  687. or_state_mark_dirty(get_or_state(), 0);
  688. }
  689. return 0;
  690. }
  691. /**
  692. * Return maximum circuit build time
  693. */
  694. static build_time_t
  695. circuit_build_times_max(const circuit_build_times_t *cbt)
  696. {
  697. int i = 0;
  698. build_time_t max_build_time = 0;
  699. for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
  700. if (cbt->circuit_build_times[i] > max_build_time
  701. && cbt->circuit_build_times[i] != CBT_BUILD_ABANDONED)
  702. max_build_time = cbt->circuit_build_times[i];
  703. }
  704. return max_build_time;
  705. }
  706. #if 0
  707. /** Return minimum circuit build time */
  708. build_time_t
  709. circuit_build_times_min(circuit_build_times_t *cbt)
  710. {
  711. int i = 0;
  712. build_time_t min_build_time = CBT_BUILD_TIME_MAX;
  713. for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
  714. if (cbt->circuit_build_times[i] && /* 0 <-> uninitialized */
  715. cbt->circuit_build_times[i] < min_build_time)
  716. min_build_time = cbt->circuit_build_times[i];
  717. }
  718. if (min_build_time == CBT_BUILD_TIME_MAX) {
  719. log_warn(LD_CIRC, "No build times less than CBT_BUILD_TIME_MAX!");
  720. }
  721. return min_build_time;
  722. }
  723. #endif /* 0 */
  724. /**
  725. * Calculate and return a histogram for the set of build times.
  726. *
  727. * Returns an allocated array of histrogram bins representing
  728. * the frequency of index*CBT_BIN_WIDTH millisecond
  729. * build times. Also outputs the number of bins in nbins.
  730. *
  731. * The return value must be freed by the caller.
  732. */
  733. static uint32_t *
  734. circuit_build_times_create_histogram(const circuit_build_times_t *cbt,
  735. build_time_t *nbins)
  736. {
  737. uint32_t *histogram;
  738. build_time_t max_build_time = circuit_build_times_max(cbt);
  739. int i, c;
  740. *nbins = 1 + (max_build_time / CBT_BIN_WIDTH);
  741. histogram = tor_calloc(*nbins, sizeof(build_time_t));
  742. // calculate histogram
  743. for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
  744. if (cbt->circuit_build_times[i] == 0
  745. || cbt->circuit_build_times[i] == CBT_BUILD_ABANDONED)
  746. continue; /* 0 <-> uninitialized */
  747. c = (cbt->circuit_build_times[i] / CBT_BIN_WIDTH);
  748. histogram[c]++;
  749. }
  750. return histogram;
  751. }
  752. /**
  753. * Return the Pareto start-of-curve parameter Xm.
  754. *
  755. * Because we are not a true Pareto curve, we compute this as the
  756. * weighted average of the N most frequent build time bins. N is either
  757. * 1 if we don't have enough circuit build time data collected, or
  758. * determined by the consensus parameter cbtnummodes (default 3).
  759. */
  760. static build_time_t
  761. circuit_build_times_get_xm(circuit_build_times_t *cbt)
  762. {
  763. build_time_t i, nbins;
  764. build_time_t *nth_max_bin;
  765. int32_t bin_counts=0;
  766. build_time_t ret = 0;
  767. uint32_t *histogram = circuit_build_times_create_histogram(cbt, &nbins);
  768. int n=0;
  769. int num_modes = circuit_build_times_default_num_xm_modes();
  770. tor_assert(nbins > 0);
  771. tor_assert(num_modes > 0);
  772. // Only use one mode if < 1000 buildtimes. Not enough data
  773. // for multiple.
  774. if (cbt->total_build_times < CBT_NCIRCUITS_TO_OBSERVE)
  775. num_modes = 1;
  776. nth_max_bin = tor_calloc(num_modes, sizeof(build_time_t));
  777. /* Determine the N most common build times */
  778. for (i = 0; i < nbins; i++) {
  779. if (histogram[i] >= histogram[nth_max_bin[0]]) {
  780. nth_max_bin[0] = i;
  781. }
  782. for (n = 1; n < num_modes; n++) {
  783. if (histogram[i] >= histogram[nth_max_bin[n]] &&
  784. (!histogram[nth_max_bin[n-1]]
  785. || histogram[i] < histogram[nth_max_bin[n-1]])) {
  786. nth_max_bin[n] = i;
  787. }
  788. }
  789. }
  790. for (n = 0; n < num_modes; n++) {
  791. bin_counts += histogram[nth_max_bin[n]];
  792. ret += CBT_BIN_TO_MS(nth_max_bin[n])*histogram[nth_max_bin[n]];
  793. log_info(LD_CIRC, "Xm mode #%d: %u %u", n, CBT_BIN_TO_MS(nth_max_bin[n]),
  794. histogram[nth_max_bin[n]]);
  795. }
  796. /* bin_counts can become zero if all of our last CBT_NCIRCUITS_TO_OBSERVE
  797. * circuits were abandoned before they completed. This shouldn't happen,
  798. * though. We should have reset/re-learned a lower timeout first. */
  799. if (bin_counts == 0) {
  800. ret = 0;
  801. log_warn(LD_CIRC,
  802. "No valid circuit build time data out of %d times, %u modes, "
  803. "have_timeout=%d, %lfms", cbt->total_build_times, num_modes,
  804. cbt->have_computed_timeout, cbt->timeout_ms);
  805. goto done;
  806. }
  807. tor_assert(bin_counts > 0);
  808. ret /= bin_counts;
  809. done:
  810. tor_free(histogram);
  811. tor_free(nth_max_bin);
  812. return ret;
  813. }
  814. /**
  815. * Output a histogram of current circuit build times to
  816. * the or_state_t state structure.
  817. */
  818. void
  819. circuit_build_times_update_state(const circuit_build_times_t *cbt,
  820. or_state_t *state)
  821. {
  822. uint32_t *histogram;
  823. build_time_t i = 0;
  824. build_time_t nbins = 0;
  825. config_line_t **next, *line;
  826. histogram = circuit_build_times_create_histogram(cbt, &nbins);
  827. // write to state
  828. config_free_lines(state->BuildtimeHistogram);
  829. next = &state->BuildtimeHistogram;
  830. *next = NULL;
  831. state->TotalBuildTimes = cbt->total_build_times;
  832. state->CircuitBuildAbandonedCount = 0;
  833. for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
  834. if (cbt->circuit_build_times[i] == CBT_BUILD_ABANDONED)
  835. state->CircuitBuildAbandonedCount++;
  836. }
  837. for (i = 0; i < nbins; i++) {
  838. // compress the histogram by skipping the blanks
  839. if (histogram[i] == 0) continue;
  840. *next = line = tor_malloc_zero(sizeof(config_line_t));
  841. line->key = tor_strdup("CircuitBuildTimeBin");
  842. tor_asprintf(&line->value, "%d %d",
  843. CBT_BIN_TO_MS(i), histogram[i]);
  844. next = &(line->next);
  845. }
  846. if (!unit_tests) {
  847. if (!get_options()->AvoidDiskWrites)
  848. or_state_mark_dirty(get_or_state(), 0);
  849. }
  850. tor_free(histogram);
  851. }
  852. /**
  853. * Shuffle the build times array.
  854. *
  855. * Adapted from http://en.wikipedia.org/wiki/Fisher-Yates_shuffle
  856. */
  857. static void
  858. circuit_build_times_shuffle_and_store_array(circuit_build_times_t *cbt,
  859. build_time_t *raw_times,
  860. uint32_t num_times)
  861. {
  862. uint32_t n = num_times;
  863. if (num_times > CBT_NCIRCUITS_TO_OBSERVE) {
  864. log_notice(LD_CIRC, "The number of circuit times that this Tor version "
  865. "uses to calculate build times is less than the number stored "
  866. "in your state file. Decreasing the circuit time history from "
  867. "%lu to %d.", (unsigned long)num_times,
  868. CBT_NCIRCUITS_TO_OBSERVE);
  869. }
  870. if (n > INT_MAX-1) {
  871. log_warn(LD_CIRC, "For some insane reasons, you had %lu circuit build "
  872. "observations in your state file. That's far too many; probably "
  873. "there's a bug here.", (unsigned long)n);
  874. n = INT_MAX-1;
  875. }
  876. /* This code can only be run on a compact array */
  877. while (n-- > 1) {
  878. int k = crypto_rand_int(n + 1); /* 0 <= k <= n. */
  879. build_time_t tmp = raw_times[k];
  880. raw_times[k] = raw_times[n];
  881. raw_times[n] = tmp;
  882. }
  883. /* Since the times are now shuffled, take a random CBT_NCIRCUITS_TO_OBSERVE
  884. * subset (ie the first CBT_NCIRCUITS_TO_OBSERVE values) */
  885. for (n = 0; n < MIN(num_times, CBT_NCIRCUITS_TO_OBSERVE); n++) {
  886. circuit_build_times_add_time(cbt, raw_times[n]);
  887. }
  888. }
  889. /**
  890. * Filter old synthetic timeouts that were created before the
  891. * new right-censored Pareto calculation was deployed.
  892. *
  893. * Once all clients before 0.2.1.13-alpha are gone, this code
  894. * will be unused.
  895. */
  896. static int
  897. circuit_build_times_filter_timeouts(circuit_build_times_t *cbt)
  898. {
  899. int num_filtered=0, i=0;
  900. double timeout_rate = 0;
  901. build_time_t max_timeout = 0;
  902. timeout_rate = circuit_build_times_timeout_rate(cbt);
  903. max_timeout = (build_time_t)cbt->close_ms;
  904. for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
  905. if (cbt->circuit_build_times[i] > max_timeout) {
  906. build_time_t replaced = cbt->circuit_build_times[i];
  907. num_filtered++;
  908. cbt->circuit_build_times[i] = CBT_BUILD_ABANDONED;
  909. log_debug(LD_CIRC, "Replaced timeout %d with %d", replaced,
  910. cbt->circuit_build_times[i]);
  911. }
  912. }
  913. log_info(LD_CIRC,
  914. "We had %d timeouts out of %d build times, "
  915. "and filtered %d above the max of %u",
  916. (int)(cbt->total_build_times*timeout_rate),
  917. cbt->total_build_times, num_filtered, max_timeout);
  918. return num_filtered;
  919. }
  920. /**
  921. * Load histogram from <b>state</b>, shuffling the resulting array
  922. * after we do so. Use this result to estimate parameters and
  923. * calculate the timeout.
  924. *
  925. * Return -1 on error.
  926. */
  927. int
  928. circuit_build_times_parse_state(circuit_build_times_t *cbt,
  929. or_state_t *state)
  930. {
  931. int tot_values = 0;
  932. uint32_t loaded_cnt = 0, N = 0;
  933. config_line_t *line;
  934. int i;
  935. build_time_t *loaded_times;
  936. int err = 0;
  937. circuit_build_times_init(cbt);
  938. if (circuit_build_times_disabled(get_options())) {
  939. return 0;
  940. }
  941. /* build_time_t 0 means uninitialized */
  942. loaded_times = tor_calloc(state->TotalBuildTimes, sizeof(build_time_t));
  943. for (line = state->BuildtimeHistogram; line; line = line->next) {
  944. smartlist_t *args = smartlist_new();
  945. smartlist_split_string(args, line->value, " ",
  946. SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
  947. if (smartlist_len(args) < 2) {
  948. log_warn(LD_GENERAL, "Unable to parse circuit build times: "
  949. "Too few arguments to CircuitBuildTime");
  950. err = 1;
  951. SMARTLIST_FOREACH(args, char*, cp, tor_free(cp));
  952. smartlist_free(args);
  953. break;
  954. } else {
  955. const char *ms_str = smartlist_get(args,0);
  956. const char *count_str = smartlist_get(args,1);
  957. uint32_t count, k;
  958. build_time_t ms;
  959. int ok;
  960. ms = (build_time_t)tor_parse_ulong(ms_str, 10, 0,
  961. CBT_BUILD_TIME_MAX, &ok, NULL);
  962. if (!ok) {
  963. log_warn(LD_GENERAL, "Unable to parse circuit build times: "
  964. "Unparsable bin number");
  965. err = 1;
  966. SMARTLIST_FOREACH(args, char*, cp, tor_free(cp));
  967. smartlist_free(args);
  968. break;
  969. }
  970. count = (uint32_t)tor_parse_ulong(count_str, 10, 0,
  971. UINT32_MAX, &ok, NULL);
  972. if (!ok) {
  973. log_warn(LD_GENERAL, "Unable to parse circuit build times: "
  974. "Unparsable bin count");
  975. err = 1;
  976. SMARTLIST_FOREACH(args, char*, cp, tor_free(cp));
  977. smartlist_free(args);
  978. break;
  979. }
  980. if (loaded_cnt+count+ (unsigned)state->CircuitBuildAbandonedCount
  981. > (unsigned) state->TotalBuildTimes) {
  982. log_warn(LD_CIRC,
  983. "Too many build times in state file. "
  984. "Stopping short before %d",
  985. loaded_cnt+count);
  986. SMARTLIST_FOREACH(args, char*, cp, tor_free(cp));
  987. smartlist_free(args);
  988. break;
  989. }
  990. for (k = 0; k < count; k++) {
  991. loaded_times[loaded_cnt++] = ms;
  992. }
  993. N++;
  994. SMARTLIST_FOREACH(args, char*, cp, tor_free(cp));
  995. smartlist_free(args);
  996. }
  997. }
  998. log_info(LD_CIRC,
  999. "Adding %d timeouts.", state->CircuitBuildAbandonedCount);
  1000. for (i=0; i < state->CircuitBuildAbandonedCount; i++) {
  1001. loaded_times[loaded_cnt++] = CBT_BUILD_ABANDONED;
  1002. }
  1003. if (loaded_cnt != (unsigned)state->TotalBuildTimes) {
  1004. log_warn(LD_CIRC,
  1005. "Corrupt state file? Build times count mismatch. "
  1006. "Read %d times, but file says %d", loaded_cnt,
  1007. state->TotalBuildTimes);
  1008. err = 1;
  1009. circuit_build_times_reset(cbt);
  1010. goto done;
  1011. }
  1012. circuit_build_times_shuffle_and_store_array(cbt, loaded_times, loaded_cnt);
  1013. /* Verify that we didn't overwrite any indexes */
  1014. for (i=0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
  1015. if (!cbt->circuit_build_times[i])
  1016. break;
  1017. tot_values++;
  1018. }
  1019. log_info(LD_CIRC,
  1020. "Loaded %d/%d values from %d lines in circuit time histogram",
  1021. tot_values, cbt->total_build_times, N);
  1022. if (cbt->total_build_times != tot_values
  1023. || cbt->total_build_times > CBT_NCIRCUITS_TO_OBSERVE) {
  1024. log_warn(LD_CIRC,
  1025. "Corrupt state file? Shuffled build times mismatch. "
  1026. "Read %d times, but file says %d", tot_values,
  1027. state->TotalBuildTimes);
  1028. err = 1;
  1029. circuit_build_times_reset(cbt);
  1030. goto done;
  1031. }
  1032. circuit_build_times_set_timeout(cbt);
  1033. if (!state->CircuitBuildAbandonedCount && cbt->total_build_times) {
  1034. circuit_build_times_filter_timeouts(cbt);
  1035. }
  1036. done:
  1037. tor_free(loaded_times);
  1038. return err ? -1 : 0;
  1039. }
  1040. /**
  1041. * Estimates the Xm and Alpha parameters using
  1042. * http://en.wikipedia.org/wiki/Pareto_distribution#Parameter_estimation
  1043. *
  1044. * The notable difference is that we use mode instead of min to estimate Xm.
  1045. * This is because our distribution is frechet-like. We claim this is
  1046. * an acceptable approximation because we are only concerned with the
  1047. * accuracy of the CDF of the tail.
  1048. */
  1049. STATIC int
  1050. circuit_build_times_update_alpha(circuit_build_times_t *cbt)
  1051. {
  1052. build_time_t *x=cbt->circuit_build_times;
  1053. double a = 0;
  1054. int n=0,i=0,abandoned_count=0;
  1055. build_time_t max_time=0;
  1056. /* http://en.wikipedia.org/wiki/Pareto_distribution#Parameter_estimation */
  1057. /* We sort of cheat here and make our samples slightly more pareto-like
  1058. * and less frechet-like. */
  1059. cbt->Xm = circuit_build_times_get_xm(cbt);
  1060. /* If Xm came back 0, then too many circuits were abandoned. */
  1061. if (cbt->Xm == 0)
  1062. return 0;
  1063. tor_assert(cbt->Xm > 0);
  1064. for (i=0; i< CBT_NCIRCUITS_TO_OBSERVE; i++) {
  1065. if (!x[i]) {
  1066. continue;
  1067. }
  1068. if (x[i] < cbt->Xm) {
  1069. a += tor_mathlog(cbt->Xm);
  1070. } else if (x[i] == CBT_BUILD_ABANDONED) {
  1071. abandoned_count++;
  1072. } else {
  1073. a += tor_mathlog(x[i]);
  1074. if (x[i] > max_time)
  1075. max_time = x[i];
  1076. }
  1077. n++;
  1078. }
  1079. /*
  1080. * We are erring and asserting here because this can only happen
  1081. * in codepaths other than startup. The startup state parsing code
  1082. * performs this same check, and resets state if it hits it. If we
  1083. * hit it at runtime, something serious has gone wrong.
  1084. */
  1085. if (n!=cbt->total_build_times) {
  1086. log_err(LD_CIRC, "Discrepancy in build times count: %d vs %d", n,
  1087. cbt->total_build_times);
  1088. }
  1089. tor_assert(n==cbt->total_build_times);
  1090. if (max_time <= 0) {
  1091. /* This can happen if Xm is actually the *maximum* value in the set.
  1092. * It can also happen if we've abandoned every single circuit somehow.
  1093. * In either case, tell the caller not to compute a new build timeout. */
  1094. log_warn(LD_BUG,
  1095. "Could not determine largest build time (%d). "
  1096. "Xm is %dms and we've abandoned %d out of %d circuits.", max_time,
  1097. cbt->Xm, abandoned_count, n);
  1098. return 0;
  1099. }
  1100. a += abandoned_count*tor_mathlog(max_time);
  1101. a -= n*tor_mathlog(cbt->Xm);
  1102. // Estimator comes from Eq #4 in:
  1103. // "Bayesian estimation based on trimmed samples from Pareto populations"
  1104. // by Arturo J. Fernández. We are right-censored only.
  1105. a = (n-abandoned_count)/a;
  1106. cbt->alpha = a;
  1107. return 1;
  1108. }
  1109. /**
  1110. * This is the Pareto Quantile Function. It calculates the point x
  1111. * in the distribution such that F(x) = quantile (ie quantile*100%
  1112. * of the mass of the density function is below x on the curve).
  1113. *
  1114. * We use it to calculate the timeout and also to generate synthetic
  1115. * values of time for circuits that timeout before completion.
  1116. *
  1117. * See http://en.wikipedia.org/wiki/Quantile_function,
  1118. * http://en.wikipedia.org/wiki/Inverse_transform_sampling and
  1119. * http://en.wikipedia.org/wiki/Pareto_distribution#Generating_a_
  1120. * random_sample_from_Pareto_distribution
  1121. * That's right. I'll cite wikipedia all day long.
  1122. *
  1123. * Return value is in milliseconds, clamped to INT32_MAX.
  1124. */
  1125. STATIC double
  1126. circuit_build_times_calculate_timeout(circuit_build_times_t *cbt,
  1127. double quantile)
  1128. {
  1129. double ret;
  1130. tor_assert(quantile >= 0);
  1131. tor_assert(1.0-quantile > 0);
  1132. tor_assert(cbt->Xm > 0);
  1133. /* If either alpha or p are 0, we would divide by zero, yielding an
  1134. * infinite (double) result; which would be clamped to INT32_MAX.
  1135. * Instead, initialise ret to INT32_MAX, and skip over these
  1136. * potentially illegal/trapping divides by zero.
  1137. */
  1138. ret = INT32_MAX;
  1139. if (cbt->alpha > 0) {
  1140. double p;
  1141. p = pow(1.0-quantile,1.0/cbt->alpha);
  1142. if (p > 0) {
  1143. ret = cbt->Xm/p;
  1144. }
  1145. }
  1146. if (ret > INT32_MAX) {
  1147. ret = INT32_MAX;
  1148. }
  1149. tor_assert(ret > 0);
  1150. return ret;
  1151. }
  1152. #ifdef TOR_UNIT_TESTS
  1153. /** Pareto CDF */
  1154. double
  1155. circuit_build_times_cdf(circuit_build_times_t *cbt, double x)
  1156. {
  1157. double ret;
  1158. tor_assert(cbt->Xm > 0);
  1159. ret = 1.0-pow(cbt->Xm/x,cbt->alpha);
  1160. tor_assert(0 <= ret && ret <= 1.0);
  1161. return ret;
  1162. }
  1163. #endif /* defined(TOR_UNIT_TESTS) */
  1164. #ifdef TOR_UNIT_TESTS
  1165. /**
  1166. * Generate a synthetic time using our distribution parameters.
  1167. *
  1168. * The return value will be within the [q_lo, q_hi) quantile points
  1169. * on the CDF.
  1170. */
  1171. build_time_t
  1172. circuit_build_times_generate_sample(circuit_build_times_t *cbt,
  1173. double q_lo, double q_hi)
  1174. {
  1175. double randval = crypto_rand_double();
  1176. build_time_t ret;
  1177. double u;
  1178. /* Generate between [q_lo, q_hi) */
  1179. /*XXXX This is what nextafter is supposed to be for; we should use it on the
  1180. * platforms that support it. */
  1181. q_hi -= 1.0/(INT32_MAX);
  1182. tor_assert(q_lo >= 0);
  1183. tor_assert(q_hi < 1);
  1184. tor_assert(q_lo < q_hi);
  1185. u = q_lo + (q_hi-q_lo)*randval;
  1186. tor_assert(0 <= u && u < 1.0);
  1187. /* circuit_build_times_calculate_timeout returns <= INT32_MAX */
  1188. ret = (build_time_t)
  1189. tor_lround(circuit_build_times_calculate_timeout(cbt, u));
  1190. tor_assert(ret > 0);
  1191. return ret;
  1192. }
  1193. #endif /* defined(TOR_UNIT_TESTS) */
  1194. #ifdef TOR_UNIT_TESTS
  1195. /**
  1196. * Estimate an initial alpha parameter by solving the quantile
  1197. * function with a quantile point and a specific timeout value.
  1198. */
  1199. void
  1200. circuit_build_times_initial_alpha(circuit_build_times_t *cbt,
  1201. double quantile, double timeout_ms)
  1202. {
  1203. // Q(u) = Xm/((1-u)^(1/a))
  1204. // Q(0.8) = Xm/((1-0.8))^(1/a)) = CircBuildTimeout
  1205. // CircBuildTimeout = Xm/((1-0.8))^(1/a))
  1206. // CircBuildTimeout = Xm*((1-0.8))^(-1/a))
  1207. // ln(CircBuildTimeout) = ln(Xm)+ln(((1-0.8)))*(-1/a)
  1208. // -ln(1-0.8)/(ln(CircBuildTimeout)-ln(Xm))=a
  1209. tor_assert(quantile >= 0);
  1210. tor_assert(cbt->Xm > 0);
  1211. cbt->alpha = tor_mathlog(1.0-quantile)/
  1212. (tor_mathlog(cbt->Xm)-tor_mathlog(timeout_ms));
  1213. tor_assert(cbt->alpha > 0);
  1214. }
  1215. #endif /* defined(TOR_UNIT_TESTS) */
  1216. /**
  1217. * Returns true if we need circuits to be built
  1218. */
  1219. int
  1220. circuit_build_times_needs_circuits(const circuit_build_times_t *cbt)
  1221. {
  1222. /* Return true if < MIN_CIRCUITS_TO_OBSERVE */
  1223. return !circuit_build_times_enough_to_compute(cbt);
  1224. }
  1225. /**
  1226. * Returns true if we should build a timeout test circuit
  1227. * right now.
  1228. */
  1229. int
  1230. circuit_build_times_needs_circuits_now(const circuit_build_times_t *cbt)
  1231. {
  1232. return circuit_build_times_needs_circuits(cbt) &&
  1233. approx_time()-cbt->last_circ_at > circuit_build_times_test_frequency();
  1234. }
  1235. /**
  1236. * How long should we be unreachable before we think we need to check if
  1237. * our published IP address has changed.
  1238. */
  1239. #define CIRCUIT_TIMEOUT_BEFORE_RECHECK_IP (60*3)
  1240. /**
  1241. * Called to indicate that the network showed some signs of liveness,
  1242. * i.e. we received a cell.
  1243. *
  1244. * This is used by circuit_build_times_network_check_live() to decide
  1245. * if we should record the circuit build timeout or not.
  1246. *
  1247. * This function is called every time we receive a cell. Avoid
  1248. * syscalls, events, and other high-intensity work.
  1249. */
  1250. void
  1251. circuit_build_times_network_is_live(circuit_build_times_t *cbt)
  1252. {
  1253. time_t now = approx_time();
  1254. if (cbt->liveness.nonlive_timeouts > 0) {
  1255. time_t time_since_live = now - cbt->liveness.network_last_live;
  1256. log_notice(LD_CIRC,
  1257. "Tor now sees network activity. Restoring circuit build "
  1258. "timeout recording. Network was down for %d seconds "
  1259. "during %d circuit attempts.",
  1260. (int)time_since_live,
  1261. cbt->liveness.nonlive_timeouts);
  1262. if (time_since_live > CIRCUIT_TIMEOUT_BEFORE_RECHECK_IP)
  1263. reschedule_descriptor_update_check();
  1264. }
  1265. cbt->liveness.network_last_live = now;
  1266. cbt->liveness.nonlive_timeouts = 0;
  1267. /* Tell control.c */
  1268. control_event_network_liveness_update(1);
  1269. }
  1270. /**
  1271. * Non-destructively scale all of our circuit success, timeout, and close
  1272. * counts down by a factor of two. Scaling in this way preserves the
  1273. * ratios between succeeded vs timed out vs closed circuits, so that
  1274. * our statistics don't change when we scale.
  1275. *
  1276. * This is used only in the rare event that we build more than
  1277. * INT32_MAX circuits. Since the num_circ_* variables are
  1278. * uint32_t, we won't even be close to overflowing them.
  1279. */
  1280. void
  1281. circuit_build_times_scale_circ_counts(circuit_build_times_t *cbt)
  1282. {
  1283. cbt->num_circ_succeeded /= 2;
  1284. cbt->num_circ_timeouts /= 2;
  1285. cbt->num_circ_closed /= 2;
  1286. }
  1287. /**
  1288. * Called to indicate that we "completed" a circuit. Because this circuit
  1289. * succeeded, it doesn't count as a timeout-after-the-first-hop.
  1290. *
  1291. * (For the purposes of the cbt code, we consider a circuit "completed" if
  1292. * it has 3 hops, regardless of its final hop count. We do this because
  1293. * we're trying to answer the question, "how long should a circuit take to
  1294. * reach the 3-hop count".)
  1295. *
  1296. * This is used by circuit_build_times_network_check_changed() to determine
  1297. * if we had too many recent timeouts and need to reset our learned timeout
  1298. * to something higher.
  1299. */
  1300. void
  1301. circuit_build_times_network_circ_success(circuit_build_times_t *cbt)
  1302. {
  1303. // Count circuit success
  1304. cbt->num_circ_succeeded++;
  1305. // If we're going to wrap int32, scale everything
  1306. if (cbt->num_circ_succeeded >= INT32_MAX) {
  1307. circuit_build_times_scale_circ_counts(cbt);
  1308. }
  1309. /* Check for NULLness because we might not be using adaptive timeouts */
  1310. if (cbt->liveness.timeouts_after_firsthop &&
  1311. cbt->liveness.num_recent_circs > 0) {
  1312. cbt->liveness.timeouts_after_firsthop[cbt->liveness.after_firsthop_idx]
  1313. = 0;
  1314. cbt->liveness.after_firsthop_idx++;
  1315. cbt->liveness.after_firsthop_idx %= cbt->liveness.num_recent_circs;
  1316. }
  1317. }
  1318. /**
  1319. * A circuit just timed out. If it failed after the first hop, record it
  1320. * in our history for later deciding if the network speed has changed.
  1321. *
  1322. * This is used by circuit_build_times_network_check_changed() to determine
  1323. * if we had too many recent timeouts and need to reset our learned timeout
  1324. * to something higher.
  1325. */
  1326. static void
  1327. circuit_build_times_network_timeout(circuit_build_times_t *cbt,
  1328. int did_onehop)
  1329. {
  1330. // Count circuit timeout
  1331. cbt->num_circ_timeouts++;
  1332. // If we're going to wrap int32, scale everything
  1333. if (cbt->num_circ_timeouts >= INT32_MAX) {
  1334. circuit_build_times_scale_circ_counts(cbt);
  1335. }
  1336. /* Check for NULLness because we might not be using adaptive timeouts */
  1337. if (cbt->liveness.timeouts_after_firsthop &&
  1338. cbt->liveness.num_recent_circs > 0) {
  1339. if (did_onehop) {
  1340. cbt->liveness.timeouts_after_firsthop[cbt->liveness.after_firsthop_idx]
  1341. = 1;
  1342. cbt->liveness.after_firsthop_idx++;
  1343. cbt->liveness.after_firsthop_idx %= cbt->liveness.num_recent_circs;
  1344. }
  1345. }
  1346. }
  1347. /**
  1348. * A circuit was just forcibly closed. If there has been no recent network
  1349. * activity at all, but this circuit was launched back when we thought the
  1350. * network was live, increment the number of "nonlive" circuit timeouts.
  1351. *
  1352. * This is used by circuit_build_times_network_check_live() to decide
  1353. * if we should record the circuit build timeout or not.
  1354. */
  1355. static void
  1356. circuit_build_times_network_close(circuit_build_times_t *cbt,
  1357. int did_onehop, time_t start_time)
  1358. {
  1359. time_t now = time(NULL);
  1360. // Count circuit close
  1361. cbt->num_circ_closed++;
  1362. // If we're going to wrap int32, scale everything
  1363. if (cbt->num_circ_closed >= INT32_MAX) {
  1364. circuit_build_times_scale_circ_counts(cbt);
  1365. }
  1366. /*
  1367. * Check if this is a timeout that was for a circuit that spent its
  1368. * entire existence during a time where we have had no network activity.
  1369. */
  1370. if (cbt->liveness.network_last_live < start_time) {
  1371. if (did_onehop) {
  1372. char last_live_buf[ISO_TIME_LEN+1];
  1373. char start_time_buf[ISO_TIME_LEN+1];
  1374. char now_buf[ISO_TIME_LEN+1];
  1375. format_local_iso_time(last_live_buf, cbt->liveness.network_last_live);
  1376. format_local_iso_time(start_time_buf, start_time);
  1377. format_local_iso_time(now_buf, now);
  1378. log_notice(LD_CIRC,
  1379. "A circuit somehow completed a hop while the network was "
  1380. "not live. The network was last live at %s, but the circuit "
  1381. "launched at %s. It's now %s. This could mean your clock "
  1382. "changed.", last_live_buf, start_time_buf, now_buf);
  1383. }
  1384. cbt->liveness.nonlive_timeouts++;
  1385. if (cbt->liveness.nonlive_timeouts == 1) {
  1386. log_notice(LD_CIRC,
  1387. "Tor has not observed any network activity for the past %d "
  1388. "seconds. Disabling circuit build timeout recording.",
  1389. (int)(now - cbt->liveness.network_last_live));
  1390. /* Tell control.c */
  1391. control_event_network_liveness_update(0);
  1392. } else {
  1393. log_info(LD_CIRC,
  1394. "Got non-live timeout. Current count is: %d",
  1395. cbt->liveness.nonlive_timeouts);
  1396. }
  1397. }
  1398. }
  1399. /**
  1400. * When the network is not live, we do not record circuit build times.
  1401. *
  1402. * The network is considered not live if there has been at least one
  1403. * circuit build that began and ended (had its close_ms measurement
  1404. * period expire) since we last received a cell.
  1405. *
  1406. * Also has the side effect of rewinding the circuit time history
  1407. * in the case of recent liveness changes.
  1408. */
  1409. int
  1410. circuit_build_times_network_check_live(const circuit_build_times_t *cbt)
  1411. {
  1412. if (cbt->liveness.nonlive_timeouts > 0) {
  1413. return 0;
  1414. }
  1415. return 1;
  1416. }
  1417. /**
  1418. * Returns true if we have seen more than MAX_RECENT_TIMEOUT_COUNT of
  1419. * the past RECENT_CIRCUITS time out after the first hop. Used to detect
  1420. * if the network connection has changed significantly, and if so,
  1421. * resets our circuit build timeout to the default.
  1422. *
  1423. * Also resets the entire timeout history in this case and causes us
  1424. * to restart the process of building test circuits and estimating a
  1425. * new timeout.
  1426. */
  1427. STATIC int
  1428. circuit_build_times_network_check_changed(circuit_build_times_t *cbt)
  1429. {
  1430. int total_build_times = cbt->total_build_times;
  1431. int timeout_count=0;
  1432. int i;
  1433. if (cbt->liveness.timeouts_after_firsthop &&
  1434. cbt->liveness.num_recent_circs > 0) {
  1435. /* how many of our recent circuits made it to the first hop but then
  1436. * timed out? */
  1437. for (i = 0; i < cbt->liveness.num_recent_circs; i++) {
  1438. timeout_count += cbt->liveness.timeouts_after_firsthop[i];
  1439. }
  1440. }
  1441. /* If 80% of our recent circuits are timing out after the first hop,
  1442. * we need to re-estimate a new initial alpha and timeout. */
  1443. if (timeout_count < circuit_build_times_max_timeouts()) {
  1444. return 0;
  1445. }
  1446. circuit_build_times_reset(cbt);
  1447. if (cbt->liveness.timeouts_after_firsthop &&
  1448. cbt->liveness.num_recent_circs > 0) {
  1449. memset(cbt->liveness.timeouts_after_firsthop, 0,
  1450. sizeof(*cbt->liveness.timeouts_after_firsthop)*
  1451. cbt->liveness.num_recent_circs);
  1452. }
  1453. cbt->liveness.after_firsthop_idx = 0;
  1454. #define MAX_TIMEOUT ((int32_t) (INT32_MAX/2))
  1455. /* Check to see if this has happened before. If so, double the timeout
  1456. * to give clients on abysmally bad network connections a shot at access */
  1457. if (cbt->timeout_ms >= circuit_build_times_get_initial_timeout()) {
  1458. if (cbt->timeout_ms > MAX_TIMEOUT || cbt->close_ms > MAX_TIMEOUT) {
  1459. log_warn(LD_CIRC, "Insanely large circuit build timeout value. "
  1460. "(timeout = %fmsec, close = %fmsec)",
  1461. cbt->timeout_ms, cbt->close_ms);
  1462. } else {
  1463. cbt->timeout_ms *= 2;
  1464. cbt->close_ms *= 2;
  1465. }
  1466. } else {
  1467. cbt->close_ms = cbt->timeout_ms
  1468. = circuit_build_times_get_initial_timeout();
  1469. }
  1470. #undef MAX_TIMEOUT
  1471. cbt_control_event_buildtimeout_set(cbt, BUILDTIMEOUT_SET_EVENT_RESET);
  1472. log_notice(LD_CIRC,
  1473. "Your network connection speed appears to have changed. Resetting "
  1474. "timeout to %lds after %d timeouts and %d buildtimes.",
  1475. tor_lround(cbt->timeout_ms/1000), timeout_count,
  1476. total_build_times);
  1477. return 1;
  1478. }
  1479. /**
  1480. * Count the number of timeouts in a set of cbt data.
  1481. */
  1482. double
  1483. circuit_build_times_timeout_rate(const circuit_build_times_t *cbt)
  1484. {
  1485. int i=0,timeouts=0;
  1486. for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
  1487. if (cbt->circuit_build_times[i] >= cbt->timeout_ms) {
  1488. timeouts++;
  1489. }
  1490. }
  1491. if (!cbt->total_build_times)
  1492. return 0;
  1493. return ((double)timeouts)/cbt->total_build_times;
  1494. }
  1495. /**
  1496. * Count the number of closed circuits in a set of cbt data.
  1497. */
  1498. double
  1499. circuit_build_times_close_rate(const circuit_build_times_t *cbt)
  1500. {
  1501. int i=0,closed=0;
  1502. for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
  1503. if (cbt->circuit_build_times[i] == CBT_BUILD_ABANDONED) {
  1504. closed++;
  1505. }
  1506. }
  1507. if (!cbt->total_build_times)
  1508. return 0;
  1509. return ((double)closed)/cbt->total_build_times;
  1510. }
  1511. /**
  1512. * Store a timeout as a synthetic value.
  1513. *
  1514. * Returns true if the store was successful and we should possibly
  1515. * update our timeout estimate.
  1516. */
  1517. int
  1518. circuit_build_times_count_close(circuit_build_times_t *cbt,
  1519. int did_onehop,
  1520. time_t start_time)
  1521. {
  1522. if (circuit_build_times_disabled(get_options())) {
  1523. cbt->close_ms = cbt->timeout_ms
  1524. = circuit_build_times_get_initial_timeout();
  1525. return 0;
  1526. }
  1527. /* Record this force-close to help determine if the network is dead */
  1528. circuit_build_times_network_close(cbt, did_onehop, start_time);
  1529. /* Only count timeouts if network is live.. */
  1530. if (!circuit_build_times_network_check_live(cbt)) {
  1531. return 0;
  1532. }
  1533. circuit_build_times_add_time(cbt, CBT_BUILD_ABANDONED);
  1534. return 1;
  1535. }
  1536. /**
  1537. * Update timeout counts to determine if we need to expire
  1538. * our build time history due to excessive timeouts.
  1539. *
  1540. * We do not record any actual time values at this stage;
  1541. * we are only interested in recording the fact that a timeout
  1542. * happened. We record the time values via
  1543. * circuit_build_times_count_close() and circuit_build_times_add_time().
  1544. */
  1545. void
  1546. circuit_build_times_count_timeout(circuit_build_times_t *cbt,
  1547. int did_onehop)
  1548. {
  1549. if (circuit_build_times_disabled(get_options())) {
  1550. cbt->close_ms = cbt->timeout_ms
  1551. = circuit_build_times_get_initial_timeout();
  1552. return;
  1553. }
  1554. /* Register the fact that a timeout just occurred. */
  1555. circuit_build_times_network_timeout(cbt, did_onehop);
  1556. /* If there are a ton of timeouts, we should reset
  1557. * the circuit build timeout. */
  1558. circuit_build_times_network_check_changed(cbt);
  1559. }
  1560. /**
  1561. * Estimate a new timeout based on history and set our timeout
  1562. * variable accordingly.
  1563. */
  1564. static int
  1565. circuit_build_times_set_timeout_worker(circuit_build_times_t *cbt)
  1566. {
  1567. build_time_t max_time;
  1568. if (!circuit_build_times_enough_to_compute(cbt))
  1569. return 0;
  1570. if (!circuit_build_times_update_alpha(cbt))
  1571. return 0;
  1572. cbt->timeout_ms = circuit_build_times_calculate_timeout(cbt,
  1573. circuit_build_times_quantile_cutoff());
  1574. cbt->close_ms = circuit_build_times_calculate_timeout(cbt,
  1575. circuit_build_times_close_quantile());
  1576. max_time = circuit_build_times_max(cbt);
  1577. if (cbt->timeout_ms > max_time) {
  1578. log_info(LD_CIRC,
  1579. "Circuit build timeout of %dms is beyond the maximum build "
  1580. "time we have ever observed. Capping it to %dms.",
  1581. (int)cbt->timeout_ms, max_time);
  1582. cbt->timeout_ms = max_time;
  1583. }
  1584. if (max_time < INT32_MAX/2 && cbt->close_ms > 2*max_time) {
  1585. log_info(LD_CIRC,
  1586. "Circuit build measurement period of %dms is more than twice "
  1587. "the maximum build time we have ever observed. Capping it to "
  1588. "%dms.", (int)cbt->close_ms, 2*max_time);
  1589. cbt->close_ms = 2*max_time;
  1590. }
  1591. /* Sometimes really fast guard nodes give us such a steep curve
  1592. * that this ends up being not that much greater than timeout_ms.
  1593. * Make it be at least 1 min to handle this case. */
  1594. cbt->close_ms = MAX(cbt->close_ms, circuit_build_times_initial_timeout());
  1595. cbt->have_computed_timeout = 1;
  1596. return 1;
  1597. }
  1598. /**
  1599. * Exposed function to compute a new timeout. Dispatches events and
  1600. * also filters out extremely high timeout values.
  1601. */
  1602. void
  1603. circuit_build_times_set_timeout(circuit_build_times_t *cbt)
  1604. {
  1605. long prev_timeout = tor_lround(cbt->timeout_ms/1000);
  1606. double timeout_rate;
  1607. /*
  1608. * Just return if we aren't using adaptive timeouts
  1609. */
  1610. if (circuit_build_times_disabled(get_options()))
  1611. return;
  1612. if (!circuit_build_times_set_timeout_worker(cbt))
  1613. return;
  1614. if (cbt->timeout_ms < circuit_build_times_min_timeout()) {
  1615. log_info(LD_CIRC, "Set buildtimeout to low value %fms. Setting to %dms",
  1616. cbt->timeout_ms, circuit_build_times_min_timeout());
  1617. cbt->timeout_ms = circuit_build_times_min_timeout();
  1618. if (cbt->close_ms < cbt->timeout_ms) {
  1619. /* This shouldn't happen because of MAX() in timeout_worker above,
  1620. * but doing it just in case */
  1621. cbt->close_ms = circuit_build_times_initial_timeout();
  1622. }
  1623. }
  1624. cbt_control_event_buildtimeout_set(cbt, BUILDTIMEOUT_SET_EVENT_COMPUTED);
  1625. timeout_rate = circuit_build_times_timeout_rate(cbt);
  1626. if (prev_timeout > tor_lround(cbt->timeout_ms/1000)) {
  1627. log_info(LD_CIRC,
  1628. "Based on %d circuit times, it looks like we don't need to "
  1629. "wait so long for circuits to finish. We will now assume a "
  1630. "circuit is too slow to use after waiting %ld seconds.",
  1631. cbt->total_build_times,
  1632. tor_lround(cbt->timeout_ms/1000));
  1633. log_info(LD_CIRC,
  1634. "Circuit timeout data: %fms, %fms, Xm: %d, a: %f, r: %f",
  1635. cbt->timeout_ms, cbt->close_ms, cbt->Xm, cbt->alpha,
  1636. timeout_rate);
  1637. } else if (prev_timeout < tor_lround(cbt->timeout_ms/1000)) {
  1638. log_info(LD_CIRC,
  1639. "Based on %d circuit times, it looks like we need to wait "
  1640. "longer for circuits to finish. We will now assume a "
  1641. "circuit is too slow to use after waiting %ld seconds.",
  1642. cbt->total_build_times,
  1643. tor_lround(cbt->timeout_ms/1000));
  1644. log_info(LD_CIRC,
  1645. "Circuit timeout data: %fms, %fms, Xm: %d, a: %f, r: %f",
  1646. cbt->timeout_ms, cbt->close_ms, cbt->Xm, cbt->alpha,
  1647. timeout_rate);
  1648. } else {
  1649. log_info(LD_CIRC,
  1650. "Set circuit build timeout to %lds (%fms, %fms, Xm: %d, a: %f,"
  1651. " r: %f) based on %d circuit times",
  1652. tor_lround(cbt->timeout_ms/1000),
  1653. cbt->timeout_ms, cbt->close_ms, cbt->Xm, cbt->alpha, timeout_rate,
  1654. cbt->total_build_times);
  1655. }
  1656. }
  1657. #ifdef TOR_UNIT_TESTS
  1658. /** Make a note that we're running unit tests (rather than running Tor
  1659. * itself), so we avoid clobbering our state file. */
  1660. void
  1661. circuitbuild_running_unit_tests(void)
  1662. {
  1663. unit_tests = 1;
  1664. }
  1665. #endif /* defined(TOR_UNIT_TESTS) */
  1666. void
  1667. circuit_build_times_update_last_circ(circuit_build_times_t *cbt)
  1668. {
  1669. cbt->last_circ_at = approx_time();
  1670. }
  1671. static void
  1672. cbt_control_event_buildtimeout_set(const circuit_build_times_t *cbt,
  1673. buildtimeout_set_event_t type)
  1674. {
  1675. char *args = NULL;
  1676. double qnt;
  1677. double timeout_rate = 0.0;
  1678. double close_rate = 0.0;
  1679. switch (type) {
  1680. case BUILDTIMEOUT_SET_EVENT_RESET:
  1681. case BUILDTIMEOUT_SET_EVENT_SUSPENDED:
  1682. case BUILDTIMEOUT_SET_EVENT_DISCARD:
  1683. qnt = 1.0;
  1684. break;
  1685. case BUILDTIMEOUT_SET_EVENT_COMPUTED:
  1686. case BUILDTIMEOUT_SET_EVENT_RESUME:
  1687. default:
  1688. qnt = circuit_build_times_quantile_cutoff();
  1689. break;
  1690. }
  1691. /* The timeout rate is the ratio of the timeout count over
  1692. * the total number of circuits attempted. The total number of
  1693. * circuits is (timeouts+succeeded+closed), since a circuit can
  1694. * either timeout, close, or succeed. We cast the denominator
  1695. * to promote it to double before the addition, to avoid int32
  1696. * overflow. */
  1697. const double total_circuits =
  1698. ((double)cbt->num_circ_timeouts) + cbt->num_circ_succeeded
  1699. + cbt->num_circ_closed;
  1700. if (total_circuits >= 1.0) {
  1701. timeout_rate = cbt->num_circ_timeouts / total_circuits;
  1702. close_rate = cbt->num_circ_closed / total_circuits;
  1703. }
  1704. tor_asprintf(&args, "TOTAL_TIMES=%lu "
  1705. "TIMEOUT_MS=%lu XM=%lu ALPHA=%f CUTOFF_QUANTILE=%f "
  1706. "TIMEOUT_RATE=%f CLOSE_MS=%lu CLOSE_RATE=%f",
  1707. (unsigned long)cbt->total_build_times,
  1708. (unsigned long)cbt->timeout_ms,
  1709. (unsigned long)cbt->Xm, cbt->alpha, qnt,
  1710. timeout_rate,
  1711. (unsigned long)cbt->close_ms,
  1712. close_rate);
  1713. control_event_buildtimeout_set(type, args);
  1714. tor_free(args);
  1715. }