circuitstats.c 62 KB

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