circuitstats.c 54 KB

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