circuitstats.c 51 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623162416251626162716281629163016311632163316341635163616371638163916401641164216431644164516461647164816491650165116521653165416551656165716581659166016611662166316641665166616671668166916701671167216731674
  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-2014, 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_calloc(num, sizeof(int8_t));
  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_calloc(cbt->liveness.num_recent_circs, sizeof(int8_t));
  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_calloc(*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 = tor_calloc(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_calloc(state->TotalBuildTimes, sizeof(build_time_t));
  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. /* If either alpha or p are 0, we would divide by zero, yielding an
  956. * infinite (double) result; which would be clamped to INT32_MAX.
  957. * Instead, initialise ret to INT32_MAX, and skip over these
  958. * potentially illegal/trapping divides by zero.
  959. */
  960. ret = INT32_MAX;
  961. if (cbt->alpha > 0) {
  962. double p;
  963. p = pow(1.0-quantile,1.0/cbt->alpha);
  964. if (p > 0) {
  965. ret = cbt->Xm/p;
  966. }
  967. }
  968. if (ret > INT32_MAX) {
  969. ret = INT32_MAX;
  970. }
  971. tor_assert(ret > 0);
  972. return ret;
  973. }
  974. #ifdef TOR_UNIT_TESTS
  975. /** Pareto CDF */
  976. double
  977. circuit_build_times_cdf(circuit_build_times_t *cbt, double x)
  978. {
  979. double ret;
  980. tor_assert(cbt->Xm > 0);
  981. ret = 1.0-pow(cbt->Xm/x,cbt->alpha);
  982. tor_assert(0 <= ret && ret <= 1.0);
  983. return ret;
  984. }
  985. #endif
  986. #ifdef TOR_UNIT_TESTS
  987. /**
  988. * Generate a synthetic time using our distribution parameters.
  989. *
  990. * The return value will be within the [q_lo, q_hi) quantile points
  991. * on the CDF.
  992. */
  993. build_time_t
  994. circuit_build_times_generate_sample(circuit_build_times_t *cbt,
  995. double q_lo, double q_hi)
  996. {
  997. double randval = crypto_rand_double();
  998. build_time_t ret;
  999. double u;
  1000. /* Generate between [q_lo, q_hi) */
  1001. /*XXXX This is what nextafter is supposed to be for; we should use it on the
  1002. * platforms that support it. */
  1003. q_hi -= 1.0/(INT32_MAX);
  1004. tor_assert(q_lo >= 0);
  1005. tor_assert(q_hi < 1);
  1006. tor_assert(q_lo < q_hi);
  1007. u = q_lo + (q_hi-q_lo)*randval;
  1008. tor_assert(0 <= u && u < 1.0);
  1009. /* circuit_build_times_calculate_timeout returns <= INT32_MAX */
  1010. ret = (build_time_t)
  1011. tor_lround(circuit_build_times_calculate_timeout(cbt, u));
  1012. tor_assert(ret > 0);
  1013. return ret;
  1014. }
  1015. #endif
  1016. #ifdef TOR_UNIT_TESTS
  1017. /**
  1018. * Estimate an initial alpha parameter by solving the quantile
  1019. * function with a quantile point and a specific timeout value.
  1020. */
  1021. void
  1022. circuit_build_times_initial_alpha(circuit_build_times_t *cbt,
  1023. double quantile, double timeout_ms)
  1024. {
  1025. // Q(u) = Xm/((1-u)^(1/a))
  1026. // Q(0.8) = Xm/((1-0.8))^(1/a)) = CircBuildTimeout
  1027. // CircBuildTimeout = Xm/((1-0.8))^(1/a))
  1028. // CircBuildTimeout = Xm*((1-0.8))^(-1/a))
  1029. // ln(CircBuildTimeout) = ln(Xm)+ln(((1-0.8)))*(-1/a)
  1030. // -ln(1-0.8)/(ln(CircBuildTimeout)-ln(Xm))=a
  1031. tor_assert(quantile >= 0);
  1032. tor_assert(cbt->Xm > 0);
  1033. cbt->alpha = tor_mathlog(1.0-quantile)/
  1034. (tor_mathlog(cbt->Xm)-tor_mathlog(timeout_ms));
  1035. tor_assert(cbt->alpha > 0);
  1036. }
  1037. #endif
  1038. /**
  1039. * Returns true if we need circuits to be built
  1040. */
  1041. int
  1042. circuit_build_times_needs_circuits(const circuit_build_times_t *cbt)
  1043. {
  1044. /* Return true if < MIN_CIRCUITS_TO_OBSERVE */
  1045. return !circuit_build_times_enough_to_compute(cbt);
  1046. }
  1047. /**
  1048. * Returns true if we should build a timeout test circuit
  1049. * right now.
  1050. */
  1051. int
  1052. circuit_build_times_needs_circuits_now(const circuit_build_times_t *cbt)
  1053. {
  1054. return circuit_build_times_needs_circuits(cbt) &&
  1055. approx_time()-cbt->last_circ_at > circuit_build_times_test_frequency();
  1056. }
  1057. /**
  1058. * How long should we be unreachable before we think we need to check if
  1059. * our published IP address has changed.
  1060. */
  1061. #define CIRCUIT_TIMEOUT_BEFORE_RECHECK_IP (60*3)
  1062. /**
  1063. * Called to indicate that the network showed some signs of liveness,
  1064. * i.e. we received a cell.
  1065. *
  1066. * This is used by circuit_build_times_network_check_live() to decide
  1067. * if we should record the circuit build timeout or not.
  1068. *
  1069. * This function is called every time we receive a cell. Avoid
  1070. * syscalls, events, and other high-intensity work.
  1071. */
  1072. void
  1073. circuit_build_times_network_is_live(circuit_build_times_t *cbt)
  1074. {
  1075. time_t now = approx_time();
  1076. if (cbt->liveness.nonlive_timeouts > 0) {
  1077. time_t time_since_live = now - cbt->liveness.network_last_live;
  1078. log_notice(LD_CIRC,
  1079. "Tor now sees network activity. Restoring circuit build "
  1080. "timeout recording. Network was down for %d seconds "
  1081. "during %d circuit attempts.",
  1082. (int)time_since_live,
  1083. cbt->liveness.nonlive_timeouts);
  1084. if (time_since_live > CIRCUIT_TIMEOUT_BEFORE_RECHECK_IP)
  1085. reschedule_descriptor_update_check();
  1086. }
  1087. cbt->liveness.network_last_live = now;
  1088. cbt->liveness.nonlive_timeouts = 0;
  1089. }
  1090. /**
  1091. * Called to indicate that we completed a circuit. Because this circuit
  1092. * succeeded, it doesn't count as a timeout-after-the-first-hop.
  1093. *
  1094. * This is used by circuit_build_times_network_check_changed() to determine
  1095. * if we had too many recent timeouts and need to reset our learned timeout
  1096. * to something higher.
  1097. */
  1098. void
  1099. circuit_build_times_network_circ_success(circuit_build_times_t *cbt)
  1100. {
  1101. /* Check for NULLness because we might not be using adaptive timeouts */
  1102. if (cbt->liveness.timeouts_after_firsthop &&
  1103. cbt->liveness.num_recent_circs > 0) {
  1104. cbt->liveness.timeouts_after_firsthop[cbt->liveness.after_firsthop_idx]
  1105. = 0;
  1106. cbt->liveness.after_firsthop_idx++;
  1107. cbt->liveness.after_firsthop_idx %= cbt->liveness.num_recent_circs;
  1108. }
  1109. }
  1110. /**
  1111. * A circuit just timed out. If it failed after the first hop, record it
  1112. * in our history for later deciding if the network speed has changed.
  1113. *
  1114. * This is used by circuit_build_times_network_check_changed() to determine
  1115. * if we had too many recent timeouts and need to reset our learned timeout
  1116. * to something higher.
  1117. */
  1118. static void
  1119. circuit_build_times_network_timeout(circuit_build_times_t *cbt,
  1120. int did_onehop)
  1121. {
  1122. /* Check for NULLness because we might not be using adaptive timeouts */
  1123. if (cbt->liveness.timeouts_after_firsthop &&
  1124. cbt->liveness.num_recent_circs > 0) {
  1125. if (did_onehop) {
  1126. cbt->liveness.timeouts_after_firsthop[cbt->liveness.after_firsthop_idx]
  1127. = 1;
  1128. cbt->liveness.after_firsthop_idx++;
  1129. cbt->liveness.after_firsthop_idx %= cbt->liveness.num_recent_circs;
  1130. }
  1131. }
  1132. }
  1133. /**
  1134. * A circuit was just forcibly closed. If there has been no recent network
  1135. * activity at all, but this circuit was launched back when we thought the
  1136. * network was live, increment the number of "nonlive" circuit timeouts.
  1137. *
  1138. * This is used by circuit_build_times_network_check_live() to decide
  1139. * if we should record the circuit build timeout or not.
  1140. */
  1141. static void
  1142. circuit_build_times_network_close(circuit_build_times_t *cbt,
  1143. int did_onehop, time_t start_time)
  1144. {
  1145. time_t now = time(NULL);
  1146. /*
  1147. * Check if this is a timeout that was for a circuit that spent its
  1148. * entire existence during a time where we have had no network activity.
  1149. */
  1150. if (cbt->liveness.network_last_live < start_time) {
  1151. if (did_onehop) {
  1152. char last_live_buf[ISO_TIME_LEN+1];
  1153. char start_time_buf[ISO_TIME_LEN+1];
  1154. char now_buf[ISO_TIME_LEN+1];
  1155. format_local_iso_time(last_live_buf, cbt->liveness.network_last_live);
  1156. format_local_iso_time(start_time_buf, start_time);
  1157. format_local_iso_time(now_buf, now);
  1158. log_notice(LD_CIRC,
  1159. "A circuit somehow completed a hop while the network was "
  1160. "not live. The network was last live at %s, but the circuit "
  1161. "launched at %s. It's now %s. This could mean your clock "
  1162. "changed.", last_live_buf, start_time_buf, now_buf);
  1163. }
  1164. cbt->liveness.nonlive_timeouts++;
  1165. if (cbt->liveness.nonlive_timeouts == 1) {
  1166. log_notice(LD_CIRC,
  1167. "Tor has not observed any network activity for the past %d "
  1168. "seconds. Disabling circuit build timeout recording.",
  1169. (int)(now - cbt->liveness.network_last_live));
  1170. } else {
  1171. log_info(LD_CIRC,
  1172. "Got non-live timeout. Current count is: %d",
  1173. cbt->liveness.nonlive_timeouts);
  1174. }
  1175. }
  1176. }
  1177. /**
  1178. * When the network is not live, we do not record circuit build times.
  1179. *
  1180. * The network is considered not live if there has been at least one
  1181. * circuit build that began and ended (had its close_ms measurement
  1182. * period expire) since we last received a cell.
  1183. *
  1184. * Also has the side effect of rewinding the circuit time history
  1185. * in the case of recent liveness changes.
  1186. */
  1187. int
  1188. circuit_build_times_network_check_live(const circuit_build_times_t *cbt)
  1189. {
  1190. if (cbt->liveness.nonlive_timeouts > 0) {
  1191. return 0;
  1192. }
  1193. return 1;
  1194. }
  1195. /**
  1196. * Returns true if we have seen more than MAX_RECENT_TIMEOUT_COUNT of
  1197. * the past RECENT_CIRCUITS time out after the first hop. Used to detect
  1198. * if the network connection has changed significantly, and if so,
  1199. * resets our circuit build timeout to the default.
  1200. *
  1201. * Also resets the entire timeout history in this case and causes us
  1202. * to restart the process of building test circuits and estimating a
  1203. * new timeout.
  1204. */
  1205. STATIC int
  1206. circuit_build_times_network_check_changed(circuit_build_times_t *cbt)
  1207. {
  1208. int total_build_times = cbt->total_build_times;
  1209. int timeout_count=0;
  1210. int i;
  1211. if (cbt->liveness.timeouts_after_firsthop &&
  1212. cbt->liveness.num_recent_circs > 0) {
  1213. /* how many of our recent circuits made it to the first hop but then
  1214. * timed out? */
  1215. for (i = 0; i < cbt->liveness.num_recent_circs; i++) {
  1216. timeout_count += cbt->liveness.timeouts_after_firsthop[i];
  1217. }
  1218. }
  1219. /* If 80% of our recent circuits are timing out after the first hop,
  1220. * we need to re-estimate a new initial alpha and timeout. */
  1221. if (timeout_count < circuit_build_times_max_timeouts()) {
  1222. return 0;
  1223. }
  1224. circuit_build_times_reset(cbt);
  1225. if (cbt->liveness.timeouts_after_firsthop &&
  1226. cbt->liveness.num_recent_circs > 0) {
  1227. memset(cbt->liveness.timeouts_after_firsthop, 0,
  1228. sizeof(*cbt->liveness.timeouts_after_firsthop)*
  1229. cbt->liveness.num_recent_circs);
  1230. }
  1231. cbt->liveness.after_firsthop_idx = 0;
  1232. #define MAX_TIMEOUT ((int32_t) (INT32_MAX/2))
  1233. /* Check to see if this has happened before. If so, double the timeout
  1234. * to give people on abysmally bad network connections a shot at access */
  1235. if (cbt->timeout_ms >= circuit_build_times_get_initial_timeout()) {
  1236. if (cbt->timeout_ms > MAX_TIMEOUT || cbt->close_ms > MAX_TIMEOUT) {
  1237. log_warn(LD_CIRC, "Insanely large circuit build timeout value. "
  1238. "(timeout = %fmsec, close = %fmsec)",
  1239. cbt->timeout_ms, cbt->close_ms);
  1240. } else {
  1241. cbt->timeout_ms *= 2;
  1242. cbt->close_ms *= 2;
  1243. }
  1244. } else {
  1245. cbt->close_ms = cbt->timeout_ms
  1246. = circuit_build_times_get_initial_timeout();
  1247. }
  1248. #undef MAX_TIMEOUT
  1249. cbt_control_event_buildtimeout_set(cbt, BUILDTIMEOUT_SET_EVENT_RESET);
  1250. log_notice(LD_CIRC,
  1251. "Your network connection speed appears to have changed. Resetting "
  1252. "timeout to %lds after %d timeouts and %d buildtimes.",
  1253. tor_lround(cbt->timeout_ms/1000), timeout_count,
  1254. total_build_times);
  1255. return 1;
  1256. }
  1257. /**
  1258. * Count the number of timeouts in a set of cbt data.
  1259. */
  1260. double
  1261. circuit_build_times_timeout_rate(const circuit_build_times_t *cbt)
  1262. {
  1263. int i=0,timeouts=0;
  1264. for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
  1265. if (cbt->circuit_build_times[i] >= cbt->timeout_ms) {
  1266. timeouts++;
  1267. }
  1268. }
  1269. if (!cbt->total_build_times)
  1270. return 0;
  1271. return ((double)timeouts)/cbt->total_build_times;
  1272. }
  1273. /**
  1274. * Count the number of closed circuits in a set of cbt data.
  1275. */
  1276. double
  1277. circuit_build_times_close_rate(const circuit_build_times_t *cbt)
  1278. {
  1279. int i=0,closed=0;
  1280. for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
  1281. if (cbt->circuit_build_times[i] == CBT_BUILD_ABANDONED) {
  1282. closed++;
  1283. }
  1284. }
  1285. if (!cbt->total_build_times)
  1286. return 0;
  1287. return ((double)closed)/cbt->total_build_times;
  1288. }
  1289. /**
  1290. * Store a timeout as a synthetic value.
  1291. *
  1292. * Returns true if the store was successful and we should possibly
  1293. * update our timeout estimate.
  1294. */
  1295. int
  1296. circuit_build_times_count_close(circuit_build_times_t *cbt,
  1297. int did_onehop,
  1298. time_t start_time)
  1299. {
  1300. if (circuit_build_times_disabled()) {
  1301. cbt->close_ms = cbt->timeout_ms
  1302. = circuit_build_times_get_initial_timeout();
  1303. return 0;
  1304. }
  1305. /* Record this force-close to help determine if the network is dead */
  1306. circuit_build_times_network_close(cbt, did_onehop, start_time);
  1307. /* Only count timeouts if network is live.. */
  1308. if (!circuit_build_times_network_check_live(cbt)) {
  1309. return 0;
  1310. }
  1311. circuit_build_times_add_time(cbt, CBT_BUILD_ABANDONED);
  1312. return 1;
  1313. }
  1314. /**
  1315. * Update timeout counts to determine if we need to expire
  1316. * our build time history due to excessive timeouts.
  1317. *
  1318. * We do not record any actual time values at this stage;
  1319. * we are only interested in recording the fact that a timeout
  1320. * happened. We record the time values via
  1321. * circuit_build_times_count_close() and circuit_build_times_add_time().
  1322. */
  1323. void
  1324. circuit_build_times_count_timeout(circuit_build_times_t *cbt,
  1325. int did_onehop)
  1326. {
  1327. if (circuit_build_times_disabled()) {
  1328. cbt->close_ms = cbt->timeout_ms
  1329. = circuit_build_times_get_initial_timeout();
  1330. return;
  1331. }
  1332. /* Register the fact that a timeout just occurred. */
  1333. circuit_build_times_network_timeout(cbt, did_onehop);
  1334. /* If there are a ton of timeouts, we should reset
  1335. * the circuit build timeout. */
  1336. circuit_build_times_network_check_changed(cbt);
  1337. }
  1338. /**
  1339. * Estimate a new timeout based on history and set our timeout
  1340. * variable accordingly.
  1341. */
  1342. static int
  1343. circuit_build_times_set_timeout_worker(circuit_build_times_t *cbt)
  1344. {
  1345. build_time_t max_time;
  1346. if (!circuit_build_times_enough_to_compute(cbt))
  1347. return 0;
  1348. if (!circuit_build_times_update_alpha(cbt))
  1349. return 0;
  1350. cbt->timeout_ms = circuit_build_times_calculate_timeout(cbt,
  1351. circuit_build_times_quantile_cutoff());
  1352. cbt->close_ms = circuit_build_times_calculate_timeout(cbt,
  1353. circuit_build_times_close_quantile());
  1354. max_time = circuit_build_times_max(cbt);
  1355. if (cbt->timeout_ms > max_time) {
  1356. log_info(LD_CIRC,
  1357. "Circuit build timeout of %dms is beyond the maximum build "
  1358. "time we have ever observed. Capping it to %dms.",
  1359. (int)cbt->timeout_ms, max_time);
  1360. cbt->timeout_ms = max_time;
  1361. }
  1362. if (max_time < INT32_MAX/2 && cbt->close_ms > 2*max_time) {
  1363. log_info(LD_CIRC,
  1364. "Circuit build measurement period of %dms is more than twice "
  1365. "the maximum build time we have ever observed. Capping it to "
  1366. "%dms.", (int)cbt->close_ms, 2*max_time);
  1367. cbt->close_ms = 2*max_time;
  1368. }
  1369. /* Sometimes really fast guard nodes give us such a steep curve
  1370. * that this ends up being not that much greater than timeout_ms.
  1371. * Make it be at least 1 min to handle this case. */
  1372. cbt->close_ms = MAX(cbt->close_ms, circuit_build_times_initial_timeout());
  1373. cbt->have_computed_timeout = 1;
  1374. return 1;
  1375. }
  1376. /**
  1377. * Exposed function to compute a new timeout. Dispatches events and
  1378. * also filters out extremely high timeout values.
  1379. */
  1380. void
  1381. circuit_build_times_set_timeout(circuit_build_times_t *cbt)
  1382. {
  1383. long prev_timeout = tor_lround(cbt->timeout_ms/1000);
  1384. double timeout_rate;
  1385. /*
  1386. * Just return if we aren't using adaptive timeouts
  1387. */
  1388. if (circuit_build_times_disabled())
  1389. return;
  1390. if (!circuit_build_times_set_timeout_worker(cbt))
  1391. return;
  1392. if (cbt->timeout_ms < circuit_build_times_min_timeout()) {
  1393. log_info(LD_CIRC, "Set buildtimeout to low value %fms. Setting to %dms",
  1394. cbt->timeout_ms, circuit_build_times_min_timeout());
  1395. cbt->timeout_ms = circuit_build_times_min_timeout();
  1396. if (cbt->close_ms < cbt->timeout_ms) {
  1397. /* This shouldn't happen because of MAX() in timeout_worker above,
  1398. * but doing it just in case */
  1399. cbt->close_ms = circuit_build_times_initial_timeout();
  1400. }
  1401. }
  1402. cbt_control_event_buildtimeout_set(cbt, BUILDTIMEOUT_SET_EVENT_COMPUTED);
  1403. timeout_rate = circuit_build_times_timeout_rate(cbt);
  1404. if (prev_timeout > tor_lround(cbt->timeout_ms/1000)) {
  1405. log_info(LD_CIRC,
  1406. "Based on %d circuit times, it looks like we don't need to "
  1407. "wait so long for circuits to finish. We will now assume a "
  1408. "circuit is too slow to use after waiting %ld seconds.",
  1409. cbt->total_build_times,
  1410. tor_lround(cbt->timeout_ms/1000));
  1411. log_info(LD_CIRC,
  1412. "Circuit timeout data: %fms, %fms, Xm: %d, a: %f, r: %f",
  1413. cbt->timeout_ms, cbt->close_ms, cbt->Xm, cbt->alpha,
  1414. timeout_rate);
  1415. } else if (prev_timeout < tor_lround(cbt->timeout_ms/1000)) {
  1416. log_info(LD_CIRC,
  1417. "Based on %d circuit times, it looks like we need to wait "
  1418. "longer for circuits to finish. We will now assume a "
  1419. "circuit is too slow to use after waiting %ld seconds.",
  1420. cbt->total_build_times,
  1421. tor_lround(cbt->timeout_ms/1000));
  1422. log_info(LD_CIRC,
  1423. "Circuit timeout data: %fms, %fms, Xm: %d, a: %f, r: %f",
  1424. cbt->timeout_ms, cbt->close_ms, cbt->Xm, cbt->alpha,
  1425. timeout_rate);
  1426. } else {
  1427. log_info(LD_CIRC,
  1428. "Set circuit build timeout to %lds (%fms, %fms, Xm: %d, a: %f,"
  1429. " r: %f) based on %d circuit times",
  1430. tor_lround(cbt->timeout_ms/1000),
  1431. cbt->timeout_ms, cbt->close_ms, cbt->Xm, cbt->alpha, timeout_rate,
  1432. cbt->total_build_times);
  1433. }
  1434. }
  1435. #ifdef TOR_UNIT_TESTS
  1436. /** Make a note that we're running unit tests (rather than running Tor
  1437. * itself), so we avoid clobbering our state file. */
  1438. void
  1439. circuitbuild_running_unit_tests(void)
  1440. {
  1441. unit_tests = 1;
  1442. }
  1443. #endif
  1444. void
  1445. circuit_build_times_update_last_circ(circuit_build_times_t *cbt)
  1446. {
  1447. cbt->last_circ_at = approx_time();
  1448. }
  1449. static void
  1450. cbt_control_event_buildtimeout_set(const circuit_build_times_t *cbt,
  1451. buildtimeout_set_event_t type)
  1452. {
  1453. char *args = NULL;
  1454. double qnt;
  1455. switch (type) {
  1456. case BUILDTIMEOUT_SET_EVENT_RESET:
  1457. case BUILDTIMEOUT_SET_EVENT_SUSPENDED:
  1458. case BUILDTIMEOUT_SET_EVENT_DISCARD:
  1459. qnt = 1.0;
  1460. break;
  1461. case BUILDTIMEOUT_SET_EVENT_COMPUTED:
  1462. case BUILDTIMEOUT_SET_EVENT_RESUME:
  1463. default:
  1464. qnt = circuit_build_times_quantile_cutoff();
  1465. break;
  1466. }
  1467. tor_asprintf(&args, "TOTAL_TIMES=%lu "
  1468. "TIMEOUT_MS=%lu XM=%lu ALPHA=%f CUTOFF_QUANTILE=%f "
  1469. "TIMEOUT_RATE=%f CLOSE_MS=%lu CLOSE_RATE=%f",
  1470. (unsigned long)cbt->total_build_times,
  1471. (unsigned long)cbt->timeout_ms,
  1472. (unsigned long)cbt->Xm, cbt->alpha, qnt,
  1473. circuit_build_times_timeout_rate(cbt),
  1474. (unsigned long)cbt->close_ms,
  1475. circuit_build_times_close_rate(cbt));
  1476. control_event_buildtimeout_set(type, args);
  1477. tor_free(args);
  1478. }