circuitstats.c 61 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582158315841585158615871588158915901591159215931594159515961597159815991600160116021603160416051606160716081609161016111612161316141615161616171618161916201621162216231624162516261627162816291630163116321633163416351636163716381639164016411642164316441645164616471648164916501651165216531654165516561657165816591660166116621663166416651666166716681669167016711672167316741675167616771678167916801681168216831684168516861687168816891690169116921693169416951696169716981699170017011702170317041705170617071708170917101711171217131714171517161717171817191720172117221723172417251726172717281729173017311732173317341735173617371738173917401741174217431744174517461747174817491750175117521753175417551756175717581759176017611762176317641765176617671768176917701771177217731774177517761777177817791780178117821783178417851786178717881789179017911792179317941795179617971798179918001801180218031804180518061807180818091810181118121813181418151816181718181819182018211822182318241825182618271828182918301831183218331834183518361837183818391840184118421843184418451846184718481849185018511852185318541855185618571858185918601861186218631864186518661867186818691870187118721873187418751876187718781879188018811882188318841885188618871888188918901891189218931894189518961897189818991900190119021903190419051906190719081909191019111912191319141915191619171918191919201921
  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. /* The following assert is safe, because we don't get called when we
  797. * haven't observed at least CBT_MIN_MIN_CIRCUITS_TO_OBSERVE circuits. */
  798. tor_assert(bin_counts > 0);
  799. ret /= bin_counts;
  800. tor_free(histogram);
  801. tor_free(nth_max_bin);
  802. return ret;
  803. }
  804. /**
  805. * Output a histogram of current circuit build times to
  806. * the or_state_t state structure.
  807. */
  808. void
  809. circuit_build_times_update_state(const circuit_build_times_t *cbt,
  810. or_state_t *state)
  811. {
  812. uint32_t *histogram;
  813. build_time_t i = 0;
  814. build_time_t nbins = 0;
  815. config_line_t **next, *line;
  816. histogram = circuit_build_times_create_histogram(cbt, &nbins);
  817. // write to state
  818. config_free_lines(state->BuildtimeHistogram);
  819. next = &state->BuildtimeHistogram;
  820. *next = NULL;
  821. state->TotalBuildTimes = cbt->total_build_times;
  822. state->CircuitBuildAbandonedCount = 0;
  823. for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
  824. if (cbt->circuit_build_times[i] == CBT_BUILD_ABANDONED)
  825. state->CircuitBuildAbandonedCount++;
  826. }
  827. for (i = 0; i < nbins; i++) {
  828. // compress the histogram by skipping the blanks
  829. if (histogram[i] == 0) continue;
  830. *next = line = tor_malloc_zero(sizeof(config_line_t));
  831. line->key = tor_strdup("CircuitBuildTimeBin");
  832. tor_asprintf(&line->value, "%d %d",
  833. CBT_BIN_TO_MS(i), histogram[i]);
  834. next = &(line->next);
  835. }
  836. if (!unit_tests) {
  837. if (!get_options()->AvoidDiskWrites)
  838. or_state_mark_dirty(get_or_state(), 0);
  839. }
  840. tor_free(histogram);
  841. }
  842. /**
  843. * Shuffle the build times array.
  844. *
  845. * Adapted from http://en.wikipedia.org/wiki/Fisher-Yates_shuffle
  846. */
  847. static void
  848. circuit_build_times_shuffle_and_store_array(circuit_build_times_t *cbt,
  849. build_time_t *raw_times,
  850. uint32_t num_times)
  851. {
  852. uint32_t n = num_times;
  853. if (num_times > CBT_NCIRCUITS_TO_OBSERVE) {
  854. log_notice(LD_CIRC, "The number of circuit times that this Tor version "
  855. "uses to calculate build times is less than the number stored "
  856. "in your state file. Decreasing the circuit time history from "
  857. "%lu to %d.", (unsigned long)num_times,
  858. CBT_NCIRCUITS_TO_OBSERVE);
  859. }
  860. if (n > INT_MAX-1) {
  861. log_warn(LD_CIRC, "For some insane reasons, you had %lu circuit build "
  862. "observations in your state file. That's far too many; probably "
  863. "there's a bug here.", (unsigned long)n);
  864. n = INT_MAX-1;
  865. }
  866. /* This code can only be run on a compact array */
  867. while (n-- > 1) {
  868. int k = crypto_rand_int(n + 1); /* 0 <= k <= n. */
  869. build_time_t tmp = raw_times[k];
  870. raw_times[k] = raw_times[n];
  871. raw_times[n] = tmp;
  872. }
  873. /* Since the times are now shuffled, take a random CBT_NCIRCUITS_TO_OBSERVE
  874. * subset (ie the first CBT_NCIRCUITS_TO_OBSERVE values) */
  875. for (n = 0; n < MIN(num_times, CBT_NCIRCUITS_TO_OBSERVE); n++) {
  876. circuit_build_times_add_time(cbt, raw_times[n]);
  877. }
  878. }
  879. /**
  880. * Filter old synthetic timeouts that were created before the
  881. * new right-censored Pareto calculation was deployed.
  882. *
  883. * Once all clients before 0.2.1.13-alpha are gone, this code
  884. * will be unused.
  885. */
  886. static int
  887. circuit_build_times_filter_timeouts(circuit_build_times_t *cbt)
  888. {
  889. int num_filtered=0, i=0;
  890. double timeout_rate = 0;
  891. build_time_t max_timeout = 0;
  892. timeout_rate = circuit_build_times_timeout_rate(cbt);
  893. max_timeout = (build_time_t)cbt->close_ms;
  894. for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
  895. if (cbt->circuit_build_times[i] > max_timeout) {
  896. build_time_t replaced = cbt->circuit_build_times[i];
  897. num_filtered++;
  898. cbt->circuit_build_times[i] = CBT_BUILD_ABANDONED;
  899. log_debug(LD_CIRC, "Replaced timeout %d with %d", replaced,
  900. cbt->circuit_build_times[i]);
  901. }
  902. }
  903. log_info(LD_CIRC,
  904. "We had %d timeouts out of %d build times, "
  905. "and filtered %d above the max of %u",
  906. (int)(cbt->total_build_times*timeout_rate),
  907. cbt->total_build_times, num_filtered, max_timeout);
  908. return num_filtered;
  909. }
  910. /**
  911. * Load histogram from <b>state</b>, shuffling the resulting array
  912. * after we do so. Use this result to estimate parameters and
  913. * calculate the timeout.
  914. *
  915. * Return -1 on error.
  916. */
  917. int
  918. circuit_build_times_parse_state(circuit_build_times_t *cbt,
  919. or_state_t *state)
  920. {
  921. int tot_values = 0;
  922. uint32_t loaded_cnt = 0, N = 0;
  923. config_line_t *line;
  924. int i;
  925. build_time_t *loaded_times;
  926. int err = 0;
  927. circuit_build_times_init(cbt);
  928. if (circuit_build_times_disabled(get_options())) {
  929. return 0;
  930. }
  931. /* build_time_t 0 means uninitialized */
  932. loaded_times = tor_calloc(state->TotalBuildTimes, sizeof(build_time_t));
  933. for (line = state->BuildtimeHistogram; line; line = line->next) {
  934. smartlist_t *args = smartlist_new();
  935. smartlist_split_string(args, line->value, " ",
  936. SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
  937. if (smartlist_len(args) < 2) {
  938. log_warn(LD_GENERAL, "Unable to parse circuit build times: "
  939. "Too few arguments to CircuitBuildTime");
  940. err = 1;
  941. SMARTLIST_FOREACH(args, char*, cp, tor_free(cp));
  942. smartlist_free(args);
  943. break;
  944. } else {
  945. const char *ms_str = smartlist_get(args,0);
  946. const char *count_str = smartlist_get(args,1);
  947. uint32_t count, k;
  948. build_time_t ms;
  949. int ok;
  950. ms = (build_time_t)tor_parse_ulong(ms_str, 10, 0,
  951. CBT_BUILD_TIME_MAX, &ok, NULL);
  952. if (!ok) {
  953. log_warn(LD_GENERAL, "Unable to parse circuit build times: "
  954. "Unparsable bin number");
  955. err = 1;
  956. SMARTLIST_FOREACH(args, char*, cp, tor_free(cp));
  957. smartlist_free(args);
  958. break;
  959. }
  960. count = (uint32_t)tor_parse_ulong(count_str, 10, 0,
  961. UINT32_MAX, &ok, NULL);
  962. if (!ok) {
  963. log_warn(LD_GENERAL, "Unable to parse circuit build times: "
  964. "Unparsable bin count");
  965. err = 1;
  966. SMARTLIST_FOREACH(args, char*, cp, tor_free(cp));
  967. smartlist_free(args);
  968. break;
  969. }
  970. if (loaded_cnt+count+ (unsigned)state->CircuitBuildAbandonedCount
  971. > (unsigned) state->TotalBuildTimes) {
  972. log_warn(LD_CIRC,
  973. "Too many build times in state file. "
  974. "Stopping short before %d",
  975. loaded_cnt+count);
  976. SMARTLIST_FOREACH(args, char*, cp, tor_free(cp));
  977. smartlist_free(args);
  978. break;
  979. }
  980. for (k = 0; k < count; k++) {
  981. loaded_times[loaded_cnt++] = ms;
  982. }
  983. N++;
  984. SMARTLIST_FOREACH(args, char*, cp, tor_free(cp));
  985. smartlist_free(args);
  986. }
  987. }
  988. log_info(LD_CIRC,
  989. "Adding %d timeouts.", state->CircuitBuildAbandonedCount);
  990. for (i=0; i < state->CircuitBuildAbandonedCount; i++) {
  991. loaded_times[loaded_cnt++] = CBT_BUILD_ABANDONED;
  992. }
  993. if (loaded_cnt != (unsigned)state->TotalBuildTimes) {
  994. log_warn(LD_CIRC,
  995. "Corrupt state file? Build times count mismatch. "
  996. "Read %d times, but file says %d", loaded_cnt,
  997. state->TotalBuildTimes);
  998. err = 1;
  999. circuit_build_times_reset(cbt);
  1000. goto done;
  1001. }
  1002. circuit_build_times_shuffle_and_store_array(cbt, loaded_times, loaded_cnt);
  1003. /* Verify that we didn't overwrite any indexes */
  1004. for (i=0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
  1005. if (!cbt->circuit_build_times[i])
  1006. break;
  1007. tot_values++;
  1008. }
  1009. log_info(LD_CIRC,
  1010. "Loaded %d/%d values from %d lines in circuit time histogram",
  1011. tot_values, cbt->total_build_times, N);
  1012. if (cbt->total_build_times != tot_values
  1013. || cbt->total_build_times > CBT_NCIRCUITS_TO_OBSERVE) {
  1014. log_warn(LD_CIRC,
  1015. "Corrupt state file? Shuffled build times mismatch. "
  1016. "Read %d times, but file says %d", tot_values,
  1017. state->TotalBuildTimes);
  1018. err = 1;
  1019. circuit_build_times_reset(cbt);
  1020. goto done;
  1021. }
  1022. circuit_build_times_set_timeout(cbt);
  1023. if (!state->CircuitBuildAbandonedCount && cbt->total_build_times) {
  1024. circuit_build_times_filter_timeouts(cbt);
  1025. }
  1026. done:
  1027. tor_free(loaded_times);
  1028. return err ? -1 : 0;
  1029. }
  1030. /**
  1031. * Estimates the Xm and Alpha parameters using
  1032. * http://en.wikipedia.org/wiki/Pareto_distribution#Parameter_estimation
  1033. *
  1034. * The notable difference is that we use mode instead of min to estimate Xm.
  1035. * This is because our distribution is frechet-like. We claim this is
  1036. * an acceptable approximation because we are only concerned with the
  1037. * accuracy of the CDF of the tail.
  1038. */
  1039. STATIC int
  1040. circuit_build_times_update_alpha(circuit_build_times_t *cbt)
  1041. {
  1042. build_time_t *x=cbt->circuit_build_times;
  1043. double a = 0;
  1044. int n=0,i=0,abandoned_count=0;
  1045. build_time_t max_time=0;
  1046. /* http://en.wikipedia.org/wiki/Pareto_distribution#Parameter_estimation */
  1047. /* We sort of cheat here and make our samples slightly more pareto-like
  1048. * and less frechet-like. */
  1049. cbt->Xm = circuit_build_times_get_xm(cbt);
  1050. tor_assert(cbt->Xm > 0);
  1051. for (i=0; i< CBT_NCIRCUITS_TO_OBSERVE; i++) {
  1052. if (!x[i]) {
  1053. continue;
  1054. }
  1055. if (x[i] < cbt->Xm) {
  1056. a += tor_mathlog(cbt->Xm);
  1057. } else if (x[i] == CBT_BUILD_ABANDONED) {
  1058. abandoned_count++;
  1059. } else {
  1060. a += tor_mathlog(x[i]);
  1061. if (x[i] > max_time)
  1062. max_time = x[i];
  1063. }
  1064. n++;
  1065. }
  1066. /*
  1067. * We are erring and asserting here because this can only happen
  1068. * in codepaths other than startup. The startup state parsing code
  1069. * performs this same check, and resets state if it hits it. If we
  1070. * hit it at runtime, something serious has gone wrong.
  1071. */
  1072. if (n!=cbt->total_build_times) {
  1073. log_err(LD_CIRC, "Discrepancy in build times count: %d vs %d", n,
  1074. cbt->total_build_times);
  1075. }
  1076. tor_assert(n==cbt->total_build_times);
  1077. if (max_time <= 0) {
  1078. /* This can happen if Xm is actually the *maximum* value in the set.
  1079. * It can also happen if we've abandoned every single circuit somehow.
  1080. * In either case, tell the caller not to compute a new build timeout. */
  1081. log_warn(LD_BUG,
  1082. "Could not determine largest build time (%d). "
  1083. "Xm is %dms and we've abandoned %d out of %d circuits.", max_time,
  1084. cbt->Xm, abandoned_count, n);
  1085. return 0;
  1086. }
  1087. a += abandoned_count*tor_mathlog(max_time);
  1088. a -= n*tor_mathlog(cbt->Xm);
  1089. // Estimator comes from Eq #4 in:
  1090. // "Bayesian estimation based on trimmed samples from Pareto populations"
  1091. // by Arturo J. Fernández. We are right-censored only.
  1092. a = (n-abandoned_count)/a;
  1093. cbt->alpha = a;
  1094. return 1;
  1095. }
  1096. /**
  1097. * This is the Pareto Quantile Function. It calculates the point x
  1098. * in the distribution such that F(x) = quantile (ie quantile*100%
  1099. * of the mass of the density function is below x on the curve).
  1100. *
  1101. * We use it to calculate the timeout and also to generate synthetic
  1102. * values of time for circuits that timeout before completion.
  1103. *
  1104. * See http://en.wikipedia.org/wiki/Quantile_function,
  1105. * http://en.wikipedia.org/wiki/Inverse_transform_sampling and
  1106. * http://en.wikipedia.org/wiki/Pareto_distribution#Generating_a_
  1107. * random_sample_from_Pareto_distribution
  1108. * That's right. I'll cite wikipedia all day long.
  1109. *
  1110. * Return value is in milliseconds, clamped to INT32_MAX.
  1111. */
  1112. STATIC double
  1113. circuit_build_times_calculate_timeout(circuit_build_times_t *cbt,
  1114. double quantile)
  1115. {
  1116. double ret;
  1117. tor_assert(quantile >= 0);
  1118. tor_assert(1.0-quantile > 0);
  1119. tor_assert(cbt->Xm > 0);
  1120. /* If either alpha or p are 0, we would divide by zero, yielding an
  1121. * infinite (double) result; which would be clamped to INT32_MAX.
  1122. * Instead, initialise ret to INT32_MAX, and skip over these
  1123. * potentially illegal/trapping divides by zero.
  1124. */
  1125. ret = INT32_MAX;
  1126. if (cbt->alpha > 0) {
  1127. double p;
  1128. p = pow(1.0-quantile,1.0/cbt->alpha);
  1129. if (p > 0) {
  1130. ret = cbt->Xm/p;
  1131. }
  1132. }
  1133. if (ret > INT32_MAX) {
  1134. ret = INT32_MAX;
  1135. }
  1136. tor_assert(ret > 0);
  1137. return ret;
  1138. }
  1139. #ifdef TOR_UNIT_TESTS
  1140. /** Pareto CDF */
  1141. double
  1142. circuit_build_times_cdf(circuit_build_times_t *cbt, double x)
  1143. {
  1144. double ret;
  1145. tor_assert(cbt->Xm > 0);
  1146. ret = 1.0-pow(cbt->Xm/x,cbt->alpha);
  1147. tor_assert(0 <= ret && ret <= 1.0);
  1148. return ret;
  1149. }
  1150. #endif /* defined(TOR_UNIT_TESTS) */
  1151. #ifdef TOR_UNIT_TESTS
  1152. /**
  1153. * Generate a synthetic time using our distribution parameters.
  1154. *
  1155. * The return value will be within the [q_lo, q_hi) quantile points
  1156. * on the CDF.
  1157. */
  1158. build_time_t
  1159. circuit_build_times_generate_sample(circuit_build_times_t *cbt,
  1160. double q_lo, double q_hi)
  1161. {
  1162. double randval = crypto_rand_double();
  1163. build_time_t ret;
  1164. double u;
  1165. /* Generate between [q_lo, q_hi) */
  1166. /*XXXX This is what nextafter is supposed to be for; we should use it on the
  1167. * platforms that support it. */
  1168. q_hi -= 1.0/(INT32_MAX);
  1169. tor_assert(q_lo >= 0);
  1170. tor_assert(q_hi < 1);
  1171. tor_assert(q_lo < q_hi);
  1172. u = q_lo + (q_hi-q_lo)*randval;
  1173. tor_assert(0 <= u && u < 1.0);
  1174. /* circuit_build_times_calculate_timeout returns <= INT32_MAX */
  1175. ret = (build_time_t)
  1176. tor_lround(circuit_build_times_calculate_timeout(cbt, u));
  1177. tor_assert(ret > 0);
  1178. return ret;
  1179. }
  1180. #endif /* defined(TOR_UNIT_TESTS) */
  1181. #ifdef TOR_UNIT_TESTS
  1182. /**
  1183. * Estimate an initial alpha parameter by solving the quantile
  1184. * function with a quantile point and a specific timeout value.
  1185. */
  1186. void
  1187. circuit_build_times_initial_alpha(circuit_build_times_t *cbt,
  1188. double quantile, double timeout_ms)
  1189. {
  1190. // Q(u) = Xm/((1-u)^(1/a))
  1191. // Q(0.8) = Xm/((1-0.8))^(1/a)) = CircBuildTimeout
  1192. // CircBuildTimeout = Xm/((1-0.8))^(1/a))
  1193. // CircBuildTimeout = Xm*((1-0.8))^(-1/a))
  1194. // ln(CircBuildTimeout) = ln(Xm)+ln(((1-0.8)))*(-1/a)
  1195. // -ln(1-0.8)/(ln(CircBuildTimeout)-ln(Xm))=a
  1196. tor_assert(quantile >= 0);
  1197. tor_assert(cbt->Xm > 0);
  1198. cbt->alpha = tor_mathlog(1.0-quantile)/
  1199. (tor_mathlog(cbt->Xm)-tor_mathlog(timeout_ms));
  1200. tor_assert(cbt->alpha > 0);
  1201. }
  1202. #endif /* defined(TOR_UNIT_TESTS) */
  1203. /**
  1204. * Returns true if we need circuits to be built
  1205. */
  1206. int
  1207. circuit_build_times_needs_circuits(const circuit_build_times_t *cbt)
  1208. {
  1209. /* Return true if < MIN_CIRCUITS_TO_OBSERVE */
  1210. return !circuit_build_times_enough_to_compute(cbt);
  1211. }
  1212. /**
  1213. * Returns true if we should build a timeout test circuit
  1214. * right now.
  1215. */
  1216. int
  1217. circuit_build_times_needs_circuits_now(const circuit_build_times_t *cbt)
  1218. {
  1219. return circuit_build_times_needs_circuits(cbt) &&
  1220. approx_time()-cbt->last_circ_at > circuit_build_times_test_frequency();
  1221. }
  1222. /**
  1223. * How long should we be unreachable before we think we need to check if
  1224. * our published IP address has changed.
  1225. */
  1226. #define CIRCUIT_TIMEOUT_BEFORE_RECHECK_IP (60*3)
  1227. /**
  1228. * Called to indicate that the network showed some signs of liveness,
  1229. * i.e. we received a cell.
  1230. *
  1231. * This is used by circuit_build_times_network_check_live() to decide
  1232. * if we should record the circuit build timeout or not.
  1233. *
  1234. * This function is called every time we receive a cell. Avoid
  1235. * syscalls, events, and other high-intensity work.
  1236. */
  1237. void
  1238. circuit_build_times_network_is_live(circuit_build_times_t *cbt)
  1239. {
  1240. time_t now = approx_time();
  1241. if (cbt->liveness.nonlive_timeouts > 0) {
  1242. time_t time_since_live = now - cbt->liveness.network_last_live;
  1243. log_notice(LD_CIRC,
  1244. "Tor now sees network activity. Restoring circuit build "
  1245. "timeout recording. Network was down for %d seconds "
  1246. "during %d circuit attempts.",
  1247. (int)time_since_live,
  1248. cbt->liveness.nonlive_timeouts);
  1249. if (time_since_live > CIRCUIT_TIMEOUT_BEFORE_RECHECK_IP)
  1250. reschedule_descriptor_update_check();
  1251. }
  1252. cbt->liveness.network_last_live = now;
  1253. cbt->liveness.nonlive_timeouts = 0;
  1254. /* Tell control.c */
  1255. control_event_network_liveness_update(1);
  1256. }
  1257. /**
  1258. * Non-destructively scale all of our circuit success, timeout, and close
  1259. * counts down by a factor of two. Scaling in this way preserves the
  1260. * ratios between succeeded vs timed out vs closed circuits, so that
  1261. * our statistics don't change when we scale.
  1262. *
  1263. * This is used only in the rare event that we build more than
  1264. * INT32_MAX circuits. Since the num_circ_* variables are
  1265. * uint32_t, we won't even be close to overflowing them.
  1266. */
  1267. void
  1268. circuit_build_times_scale_circ_counts(circuit_build_times_t *cbt)
  1269. {
  1270. cbt->num_circ_succeeded /= 2;
  1271. cbt->num_circ_timeouts /= 2;
  1272. cbt->num_circ_closed /= 2;
  1273. }
  1274. /**
  1275. * Called to indicate that we "completed" a circuit. Because this circuit
  1276. * succeeded, it doesn't count as a timeout-after-the-first-hop.
  1277. *
  1278. * (For the purposes of the cbt code, we consider a circuit "completed" if
  1279. * it has 3 hops, regardless of its final hop count. We do this because
  1280. * we're trying to answer the question, "how long should a circuit take to
  1281. * reach the 3-hop count".)
  1282. *
  1283. * This is used by circuit_build_times_network_check_changed() to determine
  1284. * if we had too many recent timeouts and need to reset our learned timeout
  1285. * to something higher.
  1286. */
  1287. void
  1288. circuit_build_times_network_circ_success(circuit_build_times_t *cbt)
  1289. {
  1290. // Count circuit success
  1291. cbt->num_circ_succeeded++;
  1292. // If we're going to wrap int32, scale everything
  1293. if (cbt->num_circ_succeeded >= INT32_MAX) {
  1294. circuit_build_times_scale_circ_counts(cbt);
  1295. }
  1296. /* Check for NULLness because we might not be using adaptive timeouts */
  1297. if (cbt->liveness.timeouts_after_firsthop &&
  1298. cbt->liveness.num_recent_circs > 0) {
  1299. cbt->liveness.timeouts_after_firsthop[cbt->liveness.after_firsthop_idx]
  1300. = 0;
  1301. cbt->liveness.after_firsthop_idx++;
  1302. cbt->liveness.after_firsthop_idx %= cbt->liveness.num_recent_circs;
  1303. }
  1304. }
  1305. /**
  1306. * A circuit just timed out. If it failed after the first hop, record it
  1307. * in our history for later deciding if the network speed has changed.
  1308. *
  1309. * This is used by circuit_build_times_network_check_changed() to determine
  1310. * if we had too many recent timeouts and need to reset our learned timeout
  1311. * to something higher.
  1312. */
  1313. static void
  1314. circuit_build_times_network_timeout(circuit_build_times_t *cbt,
  1315. int did_onehop)
  1316. {
  1317. // Count circuit timeout
  1318. cbt->num_circ_timeouts++;
  1319. // If we're going to wrap int32, scale everything
  1320. if (cbt->num_circ_timeouts >= INT32_MAX) {
  1321. circuit_build_times_scale_circ_counts(cbt);
  1322. }
  1323. /* Check for NULLness because we might not be using adaptive timeouts */
  1324. if (cbt->liveness.timeouts_after_firsthop &&
  1325. cbt->liveness.num_recent_circs > 0) {
  1326. if (did_onehop) {
  1327. cbt->liveness.timeouts_after_firsthop[cbt->liveness.after_firsthop_idx]
  1328. = 1;
  1329. cbt->liveness.after_firsthop_idx++;
  1330. cbt->liveness.after_firsthop_idx %= cbt->liveness.num_recent_circs;
  1331. }
  1332. }
  1333. }
  1334. /**
  1335. * A circuit was just forcibly closed. If there has been no recent network
  1336. * activity at all, but this circuit was launched back when we thought the
  1337. * network was live, increment the number of "nonlive" circuit timeouts.
  1338. *
  1339. * This is used by circuit_build_times_network_check_live() to decide
  1340. * if we should record the circuit build timeout or not.
  1341. */
  1342. static void
  1343. circuit_build_times_network_close(circuit_build_times_t *cbt,
  1344. int did_onehop, time_t start_time)
  1345. {
  1346. time_t now = time(NULL);
  1347. // Count circuit close
  1348. cbt->num_circ_closed++;
  1349. // If we're going to wrap int32, scale everything
  1350. if (cbt->num_circ_closed >= INT32_MAX) {
  1351. circuit_build_times_scale_circ_counts(cbt);
  1352. }
  1353. /*
  1354. * Check if this is a timeout that was for a circuit that spent its
  1355. * entire existence during a time where we have had no network activity.
  1356. */
  1357. if (cbt->liveness.network_last_live < start_time) {
  1358. if (did_onehop) {
  1359. char last_live_buf[ISO_TIME_LEN+1];
  1360. char start_time_buf[ISO_TIME_LEN+1];
  1361. char now_buf[ISO_TIME_LEN+1];
  1362. format_local_iso_time(last_live_buf, cbt->liveness.network_last_live);
  1363. format_local_iso_time(start_time_buf, start_time);
  1364. format_local_iso_time(now_buf, now);
  1365. log_notice(LD_CIRC,
  1366. "A circuit somehow completed a hop while the network was "
  1367. "not live. The network was last live at %s, but the circuit "
  1368. "launched at %s. It's now %s. This could mean your clock "
  1369. "changed.", last_live_buf, start_time_buf, now_buf);
  1370. }
  1371. cbt->liveness.nonlive_timeouts++;
  1372. if (cbt->liveness.nonlive_timeouts == 1) {
  1373. log_notice(LD_CIRC,
  1374. "Tor has not observed any network activity for the past %d "
  1375. "seconds. Disabling circuit build timeout recording.",
  1376. (int)(now - cbt->liveness.network_last_live));
  1377. /* Tell control.c */
  1378. control_event_network_liveness_update(0);
  1379. } else {
  1380. log_info(LD_CIRC,
  1381. "Got non-live timeout. Current count is: %d",
  1382. cbt->liveness.nonlive_timeouts);
  1383. }
  1384. }
  1385. }
  1386. /**
  1387. * When the network is not live, we do not record circuit build times.
  1388. *
  1389. * The network is considered not live if there has been at least one
  1390. * circuit build that began and ended (had its close_ms measurement
  1391. * period expire) since we last received a cell.
  1392. *
  1393. * Also has the side effect of rewinding the circuit time history
  1394. * in the case of recent liveness changes.
  1395. */
  1396. int
  1397. circuit_build_times_network_check_live(const circuit_build_times_t *cbt)
  1398. {
  1399. if (cbt->liveness.nonlive_timeouts > 0) {
  1400. return 0;
  1401. }
  1402. return 1;
  1403. }
  1404. /**
  1405. * Returns true if we have seen more than MAX_RECENT_TIMEOUT_COUNT of
  1406. * the past RECENT_CIRCUITS time out after the first hop. Used to detect
  1407. * if the network connection has changed significantly, and if so,
  1408. * resets our circuit build timeout to the default.
  1409. *
  1410. * Also resets the entire timeout history in this case and causes us
  1411. * to restart the process of building test circuits and estimating a
  1412. * new timeout.
  1413. */
  1414. STATIC int
  1415. circuit_build_times_network_check_changed(circuit_build_times_t *cbt)
  1416. {
  1417. int total_build_times = cbt->total_build_times;
  1418. int timeout_count=0;
  1419. int i;
  1420. if (cbt->liveness.timeouts_after_firsthop &&
  1421. cbt->liveness.num_recent_circs > 0) {
  1422. /* how many of our recent circuits made it to the first hop but then
  1423. * timed out? */
  1424. for (i = 0; i < cbt->liveness.num_recent_circs; i++) {
  1425. timeout_count += cbt->liveness.timeouts_after_firsthop[i];
  1426. }
  1427. }
  1428. /* If 80% of our recent circuits are timing out after the first hop,
  1429. * we need to re-estimate a new initial alpha and timeout. */
  1430. if (timeout_count < circuit_build_times_max_timeouts()) {
  1431. return 0;
  1432. }
  1433. circuit_build_times_reset(cbt);
  1434. if (cbt->liveness.timeouts_after_firsthop &&
  1435. cbt->liveness.num_recent_circs > 0) {
  1436. memset(cbt->liveness.timeouts_after_firsthop, 0,
  1437. sizeof(*cbt->liveness.timeouts_after_firsthop)*
  1438. cbt->liveness.num_recent_circs);
  1439. }
  1440. cbt->liveness.after_firsthop_idx = 0;
  1441. #define MAX_TIMEOUT ((int32_t) (INT32_MAX/2))
  1442. /* Check to see if this has happened before. If so, double the timeout
  1443. * to give clients on abysmally bad network connections a shot at access */
  1444. if (cbt->timeout_ms >= circuit_build_times_get_initial_timeout()) {
  1445. if (cbt->timeout_ms > MAX_TIMEOUT || cbt->close_ms > MAX_TIMEOUT) {
  1446. log_warn(LD_CIRC, "Insanely large circuit build timeout value. "
  1447. "(timeout = %fmsec, close = %fmsec)",
  1448. cbt->timeout_ms, cbt->close_ms);
  1449. } else {
  1450. cbt->timeout_ms *= 2;
  1451. cbt->close_ms *= 2;
  1452. }
  1453. } else {
  1454. cbt->close_ms = cbt->timeout_ms
  1455. = circuit_build_times_get_initial_timeout();
  1456. }
  1457. #undef MAX_TIMEOUT
  1458. cbt_control_event_buildtimeout_set(cbt, BUILDTIMEOUT_SET_EVENT_RESET);
  1459. log_notice(LD_CIRC,
  1460. "Your network connection speed appears to have changed. Resetting "
  1461. "timeout to %lds after %d timeouts and %d buildtimes.",
  1462. tor_lround(cbt->timeout_ms/1000), timeout_count,
  1463. total_build_times);
  1464. return 1;
  1465. }
  1466. /**
  1467. * Count the number of timeouts in a set of cbt data.
  1468. */
  1469. double
  1470. circuit_build_times_timeout_rate(const circuit_build_times_t *cbt)
  1471. {
  1472. int i=0,timeouts=0;
  1473. for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
  1474. if (cbt->circuit_build_times[i] >= cbt->timeout_ms) {
  1475. timeouts++;
  1476. }
  1477. }
  1478. if (!cbt->total_build_times)
  1479. return 0;
  1480. return ((double)timeouts)/cbt->total_build_times;
  1481. }
  1482. /**
  1483. * Count the number of closed circuits in a set of cbt data.
  1484. */
  1485. double
  1486. circuit_build_times_close_rate(const circuit_build_times_t *cbt)
  1487. {
  1488. int i=0,closed=0;
  1489. for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
  1490. if (cbt->circuit_build_times[i] == CBT_BUILD_ABANDONED) {
  1491. closed++;
  1492. }
  1493. }
  1494. if (!cbt->total_build_times)
  1495. return 0;
  1496. return ((double)closed)/cbt->total_build_times;
  1497. }
  1498. /**
  1499. * Store a timeout as a synthetic value.
  1500. *
  1501. * Returns true if the store was successful and we should possibly
  1502. * update our timeout estimate.
  1503. */
  1504. int
  1505. circuit_build_times_count_close(circuit_build_times_t *cbt,
  1506. int did_onehop,
  1507. time_t start_time)
  1508. {
  1509. if (circuit_build_times_disabled(get_options())) {
  1510. cbt->close_ms = cbt->timeout_ms
  1511. = circuit_build_times_get_initial_timeout();
  1512. return 0;
  1513. }
  1514. /* Record this force-close to help determine if the network is dead */
  1515. circuit_build_times_network_close(cbt, did_onehop, start_time);
  1516. /* Only count timeouts if network is live.. */
  1517. if (!circuit_build_times_network_check_live(cbt)) {
  1518. return 0;
  1519. }
  1520. circuit_build_times_add_time(cbt, CBT_BUILD_ABANDONED);
  1521. return 1;
  1522. }
  1523. /**
  1524. * Update timeout counts to determine if we need to expire
  1525. * our build time history due to excessive timeouts.
  1526. *
  1527. * We do not record any actual time values at this stage;
  1528. * we are only interested in recording the fact that a timeout
  1529. * happened. We record the time values via
  1530. * circuit_build_times_count_close() and circuit_build_times_add_time().
  1531. */
  1532. void
  1533. circuit_build_times_count_timeout(circuit_build_times_t *cbt,
  1534. int did_onehop)
  1535. {
  1536. if (circuit_build_times_disabled(get_options())) {
  1537. cbt->close_ms = cbt->timeout_ms
  1538. = circuit_build_times_get_initial_timeout();
  1539. return;
  1540. }
  1541. /* Register the fact that a timeout just occurred. */
  1542. circuit_build_times_network_timeout(cbt, did_onehop);
  1543. /* If there are a ton of timeouts, we should reset
  1544. * the circuit build timeout. */
  1545. circuit_build_times_network_check_changed(cbt);
  1546. }
  1547. /**
  1548. * Estimate a new timeout based on history and set our timeout
  1549. * variable accordingly.
  1550. */
  1551. static int
  1552. circuit_build_times_set_timeout_worker(circuit_build_times_t *cbt)
  1553. {
  1554. build_time_t max_time;
  1555. if (!circuit_build_times_enough_to_compute(cbt))
  1556. return 0;
  1557. if (!circuit_build_times_update_alpha(cbt))
  1558. return 0;
  1559. cbt->timeout_ms = circuit_build_times_calculate_timeout(cbt,
  1560. circuit_build_times_quantile_cutoff());
  1561. cbt->close_ms = circuit_build_times_calculate_timeout(cbt,
  1562. circuit_build_times_close_quantile());
  1563. max_time = circuit_build_times_max(cbt);
  1564. if (cbt->timeout_ms > max_time) {
  1565. log_info(LD_CIRC,
  1566. "Circuit build timeout of %dms is beyond the maximum build "
  1567. "time we have ever observed. Capping it to %dms.",
  1568. (int)cbt->timeout_ms, max_time);
  1569. cbt->timeout_ms = max_time;
  1570. }
  1571. if (max_time < INT32_MAX/2 && cbt->close_ms > 2*max_time) {
  1572. log_info(LD_CIRC,
  1573. "Circuit build measurement period of %dms is more than twice "
  1574. "the maximum build time we have ever observed. Capping it to "
  1575. "%dms.", (int)cbt->close_ms, 2*max_time);
  1576. cbt->close_ms = 2*max_time;
  1577. }
  1578. /* Sometimes really fast guard nodes give us such a steep curve
  1579. * that this ends up being not that much greater than timeout_ms.
  1580. * Make it be at least 1 min to handle this case. */
  1581. cbt->close_ms = MAX(cbt->close_ms, circuit_build_times_initial_timeout());
  1582. cbt->have_computed_timeout = 1;
  1583. return 1;
  1584. }
  1585. /**
  1586. * Exposed function to compute a new timeout. Dispatches events and
  1587. * also filters out extremely high timeout values.
  1588. */
  1589. void
  1590. circuit_build_times_set_timeout(circuit_build_times_t *cbt)
  1591. {
  1592. long prev_timeout = tor_lround(cbt->timeout_ms/1000);
  1593. double timeout_rate;
  1594. /*
  1595. * Just return if we aren't using adaptive timeouts
  1596. */
  1597. if (circuit_build_times_disabled(get_options()))
  1598. return;
  1599. if (!circuit_build_times_set_timeout_worker(cbt))
  1600. return;
  1601. if (cbt->timeout_ms < circuit_build_times_min_timeout()) {
  1602. log_info(LD_CIRC, "Set buildtimeout to low value %fms. Setting to %dms",
  1603. cbt->timeout_ms, circuit_build_times_min_timeout());
  1604. cbt->timeout_ms = circuit_build_times_min_timeout();
  1605. if (cbt->close_ms < cbt->timeout_ms) {
  1606. /* This shouldn't happen because of MAX() in timeout_worker above,
  1607. * but doing it just in case */
  1608. cbt->close_ms = circuit_build_times_initial_timeout();
  1609. }
  1610. }
  1611. cbt_control_event_buildtimeout_set(cbt, BUILDTIMEOUT_SET_EVENT_COMPUTED);
  1612. timeout_rate = circuit_build_times_timeout_rate(cbt);
  1613. if (prev_timeout > tor_lround(cbt->timeout_ms/1000)) {
  1614. log_info(LD_CIRC,
  1615. "Based on %d circuit times, it looks like we don't need to "
  1616. "wait so long for circuits to finish. We will now assume a "
  1617. "circuit is too slow to use after waiting %ld seconds.",
  1618. cbt->total_build_times,
  1619. tor_lround(cbt->timeout_ms/1000));
  1620. log_info(LD_CIRC,
  1621. "Circuit timeout data: %fms, %fms, Xm: %d, a: %f, r: %f",
  1622. cbt->timeout_ms, cbt->close_ms, cbt->Xm, cbt->alpha,
  1623. timeout_rate);
  1624. } else if (prev_timeout < tor_lround(cbt->timeout_ms/1000)) {
  1625. log_info(LD_CIRC,
  1626. "Based on %d circuit times, it looks like we need to wait "
  1627. "longer for circuits to finish. We will now assume a "
  1628. "circuit is too slow to use after waiting %ld seconds.",
  1629. cbt->total_build_times,
  1630. tor_lround(cbt->timeout_ms/1000));
  1631. log_info(LD_CIRC,
  1632. "Circuit timeout data: %fms, %fms, Xm: %d, a: %f, r: %f",
  1633. cbt->timeout_ms, cbt->close_ms, cbt->Xm, cbt->alpha,
  1634. timeout_rate);
  1635. } else {
  1636. log_info(LD_CIRC,
  1637. "Set circuit build timeout to %lds (%fms, %fms, Xm: %d, a: %f,"
  1638. " r: %f) based on %d circuit times",
  1639. tor_lround(cbt->timeout_ms/1000),
  1640. cbt->timeout_ms, cbt->close_ms, cbt->Xm, cbt->alpha, timeout_rate,
  1641. cbt->total_build_times);
  1642. }
  1643. }
  1644. #ifdef TOR_UNIT_TESTS
  1645. /** Make a note that we're running unit tests (rather than running Tor
  1646. * itself), so we avoid clobbering our state file. */
  1647. void
  1648. circuitbuild_running_unit_tests(void)
  1649. {
  1650. unit_tests = 1;
  1651. }
  1652. #endif /* defined(TOR_UNIT_TESTS) */
  1653. void
  1654. circuit_build_times_update_last_circ(circuit_build_times_t *cbt)
  1655. {
  1656. cbt->last_circ_at = approx_time();
  1657. }
  1658. static void
  1659. cbt_control_event_buildtimeout_set(const circuit_build_times_t *cbt,
  1660. buildtimeout_set_event_t type)
  1661. {
  1662. char *args = NULL;
  1663. double qnt;
  1664. double timeout_rate = 0.0;
  1665. double close_rate = 0.0;
  1666. switch (type) {
  1667. case BUILDTIMEOUT_SET_EVENT_RESET:
  1668. case BUILDTIMEOUT_SET_EVENT_SUSPENDED:
  1669. case BUILDTIMEOUT_SET_EVENT_DISCARD:
  1670. qnt = 1.0;
  1671. break;
  1672. case BUILDTIMEOUT_SET_EVENT_COMPUTED:
  1673. case BUILDTIMEOUT_SET_EVENT_RESUME:
  1674. default:
  1675. qnt = circuit_build_times_quantile_cutoff();
  1676. break;
  1677. }
  1678. /* The timeout rate is the ratio of the timeout count over
  1679. * the total number of circuits attempted. The total number of
  1680. * circuits is (timeouts+succeeded+closed), since a circuit can
  1681. * either timeout, close, or succeed. We cast the denominator
  1682. * to promote it to double before the addition, to avoid int32
  1683. * overflow. */
  1684. const double total_circuits =
  1685. ((double)cbt->num_circ_timeouts) + cbt->num_circ_succeeded
  1686. + cbt->num_circ_closed;
  1687. if (total_circuits >= 1.0) {
  1688. timeout_rate = cbt->num_circ_timeouts / total_circuits;
  1689. close_rate = cbt->num_circ_closed / total_circuits;
  1690. }
  1691. tor_asprintf(&args, "TOTAL_TIMES=%lu "
  1692. "TIMEOUT_MS=%lu XM=%lu ALPHA=%f CUTOFF_QUANTILE=%f "
  1693. "TIMEOUT_RATE=%f CLOSE_MS=%lu CLOSE_RATE=%f",
  1694. (unsigned long)cbt->total_build_times,
  1695. (unsigned long)cbt->timeout_ms,
  1696. (unsigned long)cbt->Xm, cbt->alpha, qnt,
  1697. timeout_rate,
  1698. (unsigned long)cbt->close_ms,
  1699. close_rate);
  1700. control_event_buildtimeout_set(type, args);
  1701. tor_free(args);
  1702. }