circuitstats.c 51 KB

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