circuitstats.c 54 KB

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