rephist.c 106 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582158315841585158615871588158915901591159215931594159515961597159815991600160116021603160416051606160716081609161016111612161316141615161616171618161916201621162216231624162516261627162816291630163116321633163416351636163716381639164016411642164316441645164616471648164916501651165216531654165516561657165816591660166116621663166416651666166716681669167016711672167316741675167616771678167916801681168216831684168516861687168816891690169116921693169416951696169716981699170017011702170317041705170617071708170917101711171217131714171517161717171817191720172117221723172417251726172717281729173017311732173317341735173617371738173917401741174217431744174517461747174817491750175117521753175417551756175717581759176017611762176317641765176617671768176917701771177217731774177517761777177817791780178117821783178417851786178717881789179017911792179317941795179617971798179918001801180218031804180518061807180818091810181118121813181418151816181718181819182018211822182318241825182618271828182918301831183218331834183518361837183818391840184118421843184418451846184718481849185018511852185318541855185618571858185918601861186218631864186518661867186818691870187118721873187418751876187718781879188018811882188318841885188618871888188918901891189218931894189518961897189818991900190119021903190419051906190719081909191019111912191319141915191619171918191919201921192219231924192519261927192819291930193119321933193419351936193719381939194019411942194319441945194619471948194919501951195219531954195519561957195819591960196119621963196419651966196719681969197019711972197319741975197619771978197919801981198219831984198519861987198819891990199119921993199419951996199719981999200020012002200320042005200620072008200920102011201220132014201520162017201820192020202120222023202420252026202720282029203020312032203320342035203620372038203920402041204220432044204520462047204820492050205120522053205420552056205720582059206020612062206320642065206620672068206920702071207220732074207520762077207820792080208120822083208420852086208720882089209020912092209320942095209620972098209921002101210221032104210521062107210821092110211121122113211421152116211721182119212021212122212321242125212621272128212921302131213221332134213521362137213821392140214121422143214421452146214721482149215021512152215321542155215621572158215921602161216221632164216521662167216821692170217121722173217421752176217721782179218021812182218321842185218621872188218921902191219221932194219521962197219821992200220122022203220422052206220722082209221022112212221322142215221622172218221922202221222222232224222522262227222822292230223122322233223422352236223722382239224022412242224322442245224622472248224922502251225222532254225522562257225822592260226122622263226422652266226722682269227022712272227322742275227622772278227922802281228222832284228522862287228822892290229122922293229422952296229722982299230023012302230323042305230623072308230923102311231223132314231523162317231823192320232123222323232423252326232723282329233023312332233323342335233623372338233923402341234223432344234523462347234823492350235123522353235423552356235723582359236023612362236323642365236623672368236923702371237223732374237523762377237823792380238123822383238423852386238723882389239023912392239323942395239623972398239924002401240224032404240524062407240824092410241124122413241424152416241724182419242024212422242324242425242624272428242924302431243224332434243524362437243824392440244124422443244424452446244724482449245024512452245324542455245624572458245924602461246224632464246524662467246824692470247124722473247424752476247724782479248024812482248324842485248624872488248924902491249224932494249524962497249824992500250125022503250425052506250725082509251025112512251325142515251625172518251925202521252225232524252525262527252825292530253125322533253425352536253725382539254025412542254325442545254625472548254925502551255225532554255525562557255825592560256125622563256425652566256725682569257025712572257325742575257625772578257925802581258225832584258525862587258825892590259125922593259425952596259725982599260026012602260326042605260626072608260926102611261226132614261526162617261826192620262126222623262426252626262726282629263026312632263326342635263626372638263926402641264226432644264526462647264826492650265126522653265426552656265726582659266026612662266326642665266626672668266926702671267226732674267526762677267826792680268126822683268426852686268726882689269026912692269326942695269626972698269927002701270227032704270527062707270827092710271127122713271427152716271727182719272027212722272327242725272627272728272927302731273227332734273527362737273827392740274127422743274427452746274727482749275027512752275327542755275627572758275927602761276227632764276527662767276827692770277127722773277427752776277727782779278027812782278327842785278627872788278927902791279227932794279527962797279827992800280128022803280428052806280728082809281028112812281328142815281628172818281928202821282228232824282528262827282828292830283128322833283428352836283728382839284028412842284328442845284628472848284928502851285228532854285528562857285828592860286128622863286428652866286728682869287028712872287328742875287628772878287928802881288228832884288528862887288828892890289128922893289428952896289728982899290029012902290329042905290629072908290929102911291229132914291529162917291829192920292129222923292429252926292729282929293029312932293329342935293629372938293929402941294229432944294529462947294829492950295129522953295429552956295729582959296029612962296329642965296629672968296929702971297229732974297529762977297829792980298129822983298429852986298729882989299029912992299329942995299629972998299930003001300230033004300530063007300830093010301130123013301430153016301730183019302030213022302330243025302630273028302930303031303230333034303530363037303830393040304130423043304430453046304730483049305030513052305330543055305630573058305930603061306230633064306530663067306830693070307130723073307430753076307730783079308030813082308330843085308630873088308930903091309230933094309530963097309830993100310131023103310431053106310731083109311031113112311331143115311631173118311931203121312231233124312531263127312831293130313131323133313431353136313731383139314031413142314331443145314631473148314931503151315231533154315531563157315831593160316131623163316431653166316731683169317031713172317331743175317631773178317931803181318231833184318531863187318831893190319131923193319431953196319731983199320032013202320332043205320632073208320932103211321232133214321532163217321832193220322132223223322432253226322732283229323032313232323332343235323632373238323932403241324232433244324532463247324832493250325132523253325432553256325732583259326032613262326332643265326632673268326932703271327232733274327532763277327832793280328132823283328432853286328732883289329032913292329332943295
  1. /* Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
  2. * Copyright (c) 2007-2016, The Tor Project, Inc. */
  3. /* See LICENSE for licensing information */
  4. /**
  5. * \file rephist.c
  6. * \brief Basic history and performance-tracking functionality.
  7. *
  8. * Basic history and performance-tracking functionality to remember
  9. * which servers have worked in the past, how much bandwidth we've
  10. * been using, which ports we tend to want, and so on; further,
  11. * exit port statistics, cell statistics, and connection statistics.
  12. *
  13. * The history and information tracked in this module could sensibly be
  14. * divided into several categories:
  15. *
  16. * <ul><li>Statistics used by authorities to remember the uptime and
  17. * stability information about various relays, including "uptime",
  18. * "weighted fractional uptime" and "mean time between failures".
  19. *
  20. * <li>Bandwidth usage history, used by relays to self-report how much
  21. * bandwidth they've used for different purposes over last day or so,
  22. * in order to generate the {dirreq-,}{read,write}-history lines in
  23. * that they publish.
  24. *
  25. * <li>Predicted ports, used by clients to remember how long it's been
  26. * since they opened an exit connection to each given target
  27. * port. Clients use this information in order to try to keep circuits
  28. * open to exit nodes that can connect to the ports that they care
  29. * about. (The predicted ports mechanism also handles predicted circuit
  30. * usage that _isn't_ port-specific, such as resolves, internal circuits,
  31. * and so on.)
  32. *
  33. * <li>Public key operation counters, for tracking how many times we've
  34. * done each public key operation. (This is unmaintained and we should
  35. * remove it.)
  36. *
  37. * <li>Exit statistics by port, used by exits to keep track of the
  38. * number of streams and bytes they've served at each exit port, so they
  39. * can generate their exit-kibibytes-{read,written} and
  40. * exit-streams-opened statistics.
  41. *
  42. * <li>Circuit stats, used by relays instances to tract circuit
  43. * queue fullness and delay over time, and generate cell-processed-cells,
  44. * cell-queued-cells, cell-time-in-queue, and cell-circuits-per-decile
  45. * statistics.
  46. *
  47. * <li>Descriptor serving statistics, used by directory caches to track
  48. * how many descriptors they've served.
  49. *
  50. * <li>Connection statistics, used by relays to track one-way and
  51. * bidirectional connections.
  52. *
  53. * <li>Onion handshake statistics, used by relays to count how many
  54. * TAP and ntor handshakes they've handled.
  55. *
  56. * <li>Hidden service statistics, used by relays to count rendezvous
  57. * traffic and HSDir-stored descriptors.
  58. *
  59. * <li>Link protocol statistics, used by relays to count how many times
  60. * each link protocol has been used.
  61. *
  62. * </ul>
  63. *
  64. * The entry points for this module are scattered throughout the
  65. * codebase. Sending data, receiving data, connecting to a relay,
  66. * losing a connection to a relay, and so on can all trigger a change in
  67. * our current stats. Relays also invoke this module in order to
  68. * extract their statistics when building routerinfo and extrainfo
  69. * objects in router.c.
  70. *
  71. * TODO: This module should be broken up.
  72. *
  73. * (The "rephist" name originally stood for "reputation and history". )
  74. **/
  75. #include "or.h"
  76. #include "circuitlist.h"
  77. #include "circuituse.h"
  78. #include "config.h"
  79. #include "networkstatus.h"
  80. #include "nodelist.h"
  81. #include "rephist.h"
  82. #include "router.h"
  83. #include "routerlist.h"
  84. #include "ht.h"
  85. static void bw_arrays_init(void);
  86. static void predicted_ports_init(void);
  87. /** Total number of bytes currently allocated in fields used by rephist.c. */
  88. uint64_t rephist_total_alloc=0;
  89. /** Number of or_history_t objects currently allocated. */
  90. uint32_t rephist_total_num=0;
  91. /** If the total weighted run count of all runs for a router ever falls
  92. * below this amount, the router can be treated as having 0 MTBF. */
  93. #define STABILITY_EPSILON 0.0001
  94. /** Value by which to discount all old intervals for MTBF purposes. This
  95. * is compounded every STABILITY_INTERVAL. */
  96. #define STABILITY_ALPHA 0.95
  97. /** Interval at which to discount all old intervals for MTBF purposes. */
  98. #define STABILITY_INTERVAL (12*60*60)
  99. /* (This combination of ALPHA, INTERVAL, and EPSILON makes it so that an
  100. * interval that just ended counts twice as much as one that ended a week ago,
  101. * 20X as much as one that ended a month ago, and routers that have had no
  102. * uptime data for about half a year will get forgotten.) */
  103. /** History of an OR-\>OR link. */
  104. typedef struct link_history_t {
  105. /** When did we start tracking this list? */
  106. time_t since;
  107. /** When did we most recently note a change to this link */
  108. time_t changed;
  109. /** How many times did extending from OR1 to OR2 succeed? */
  110. unsigned long n_extend_ok;
  111. /** How many times did extending from OR1 to OR2 fail? */
  112. unsigned long n_extend_fail;
  113. } link_history_t;
  114. /** History of an OR. */
  115. typedef struct or_history_t {
  116. /** When did we start tracking this OR? */
  117. time_t since;
  118. /** When did we most recently note a change to this OR? */
  119. time_t changed;
  120. /** How many times did we successfully connect? */
  121. unsigned long n_conn_ok;
  122. /** How many times did we try to connect and fail?*/
  123. unsigned long n_conn_fail;
  124. /** How many seconds have we been connected to this OR before
  125. * 'up_since'? */
  126. unsigned long uptime;
  127. /** How many seconds have we been unable to connect to this OR before
  128. * 'down_since'? */
  129. unsigned long downtime;
  130. /** If nonzero, we have been connected since this time. */
  131. time_t up_since;
  132. /** If nonzero, we have been unable to connect since this time. */
  133. time_t down_since;
  134. /** The address at which we most recently connected to this OR
  135. * successfully. */
  136. tor_addr_t last_reached_addr;
  137. /** The port at which we most recently connected to this OR successfully */
  138. uint16_t last_reached_port;
  139. /* === For MTBF tracking: */
  140. /** Weighted sum total of all times that this router has been online.
  141. */
  142. unsigned long weighted_run_length;
  143. /** If the router is now online (according to stability-checking rules),
  144. * when did it come online? */
  145. time_t start_of_run;
  146. /** Sum of weights for runs in weighted_run_length. */
  147. double total_run_weights;
  148. /* === For fractional uptime tracking: */
  149. time_t start_of_downtime;
  150. unsigned long weighted_uptime;
  151. unsigned long total_weighted_time;
  152. /** Map from hex OR2 identity digest to a link_history_t for the link
  153. * from this OR to OR2. */
  154. digestmap_t *link_history_map;
  155. } or_history_t;
  156. /** When did we last multiply all routers' weighted_run_length and
  157. * total_run_weights by STABILITY_ALPHA? */
  158. static time_t stability_last_downrated = 0;
  159. /** */
  160. static time_t started_tracking_stability = 0;
  161. /** Map from hex OR identity digest to or_history_t. */
  162. static digestmap_t *history_map = NULL;
  163. /** Return the or_history_t for the OR with identity digest <b>id</b>,
  164. * creating it if necessary. */
  165. static or_history_t *
  166. get_or_history(const char* id)
  167. {
  168. or_history_t *hist;
  169. if (tor_digest_is_zero(id))
  170. return NULL;
  171. hist = digestmap_get(history_map, id);
  172. if (!hist) {
  173. hist = tor_malloc_zero(sizeof(or_history_t));
  174. rephist_total_alloc += sizeof(or_history_t);
  175. rephist_total_num++;
  176. hist->link_history_map = digestmap_new();
  177. hist->since = hist->changed = time(NULL);
  178. tor_addr_make_unspec(&hist->last_reached_addr);
  179. digestmap_set(history_map, id, hist);
  180. }
  181. return hist;
  182. }
  183. /** Return the link_history_t for the link from the first named OR to
  184. * the second, creating it if necessary. (ORs are identified by
  185. * identity digest.)
  186. */
  187. static link_history_t *
  188. get_link_history(const char *from_id, const char *to_id)
  189. {
  190. or_history_t *orhist;
  191. link_history_t *lhist;
  192. orhist = get_or_history(from_id);
  193. if (!orhist)
  194. return NULL;
  195. if (tor_digest_is_zero(to_id))
  196. return NULL;
  197. lhist = digestmap_get(orhist->link_history_map, to_id);
  198. if (!lhist) {
  199. lhist = tor_malloc_zero(sizeof(link_history_t));
  200. rephist_total_alloc += sizeof(link_history_t);
  201. lhist->since = lhist->changed = time(NULL);
  202. digestmap_set(orhist->link_history_map, to_id, lhist);
  203. }
  204. return lhist;
  205. }
  206. /** Helper: free storage held by a single link history entry. */
  207. static void
  208. free_link_history_(void *val)
  209. {
  210. rephist_total_alloc -= sizeof(link_history_t);
  211. tor_free(val);
  212. }
  213. /** Helper: free storage held by a single OR history entry. */
  214. static void
  215. free_or_history(void *_hist)
  216. {
  217. or_history_t *hist = _hist;
  218. digestmap_free(hist->link_history_map, free_link_history_);
  219. rephist_total_alloc -= sizeof(or_history_t);
  220. rephist_total_num--;
  221. tor_free(hist);
  222. }
  223. /** Update an or_history_t object <b>hist</b> so that its uptime/downtime
  224. * count is up-to-date as of <b>when</b>.
  225. */
  226. static void
  227. update_or_history(or_history_t *hist, time_t when)
  228. {
  229. tor_assert(hist);
  230. if (hist->up_since) {
  231. tor_assert(!hist->down_since);
  232. hist->uptime += (when - hist->up_since);
  233. hist->up_since = when;
  234. } else if (hist->down_since) {
  235. hist->downtime += (when - hist->down_since);
  236. hist->down_since = when;
  237. }
  238. }
  239. /** Initialize the static data structures for tracking history. */
  240. void
  241. rep_hist_init(void)
  242. {
  243. history_map = digestmap_new();
  244. bw_arrays_init();
  245. predicted_ports_init();
  246. }
  247. /** Helper: note that we are no longer connected to the router with history
  248. * <b>hist</b>. If <b>failed</b>, the connection failed; otherwise, it was
  249. * closed correctly. */
  250. static void
  251. mark_or_down(or_history_t *hist, time_t when, int failed)
  252. {
  253. if (hist->up_since) {
  254. hist->uptime += (when - hist->up_since);
  255. hist->up_since = 0;
  256. }
  257. if (failed && !hist->down_since) {
  258. hist->down_since = when;
  259. }
  260. }
  261. /** Helper: note that we are connected to the router with history
  262. * <b>hist</b>. */
  263. static void
  264. mark_or_up(or_history_t *hist, time_t when)
  265. {
  266. if (hist->down_since) {
  267. hist->downtime += (when - hist->down_since);
  268. hist->down_since = 0;
  269. }
  270. if (!hist->up_since) {
  271. hist->up_since = when;
  272. }
  273. }
  274. /** Remember that an attempt to connect to the OR with identity digest
  275. * <b>id</b> failed at <b>when</b>.
  276. */
  277. void
  278. rep_hist_note_connect_failed(const char* id, time_t when)
  279. {
  280. or_history_t *hist;
  281. hist = get_or_history(id);
  282. if (!hist)
  283. return;
  284. ++hist->n_conn_fail;
  285. mark_or_down(hist, when, 1);
  286. hist->changed = when;
  287. }
  288. /** Remember that an attempt to connect to the OR with identity digest
  289. * <b>id</b> succeeded at <b>when</b>.
  290. */
  291. void
  292. rep_hist_note_connect_succeeded(const char* id, time_t when)
  293. {
  294. or_history_t *hist;
  295. hist = get_or_history(id);
  296. if (!hist)
  297. return;
  298. ++hist->n_conn_ok;
  299. mark_or_up(hist, when);
  300. hist->changed = when;
  301. }
  302. /** Remember that we intentionally closed our connection to the OR
  303. * with identity digest <b>id</b> at <b>when</b>.
  304. */
  305. void
  306. rep_hist_note_disconnect(const char* id, time_t when)
  307. {
  308. or_history_t *hist;
  309. hist = get_or_history(id);
  310. if (!hist)
  311. return;
  312. mark_or_down(hist, when, 0);
  313. hist->changed = when;
  314. }
  315. /** Remember that our connection to the OR with identity digest
  316. * <b>id</b> had an error and stopped working at <b>when</b>.
  317. */
  318. void
  319. rep_hist_note_connection_died(const char* id, time_t when)
  320. {
  321. or_history_t *hist;
  322. if (!id) {
  323. /* If conn has no identity, it didn't complete its handshake, or something
  324. * went wrong. Ignore it.
  325. */
  326. return;
  327. }
  328. hist = get_or_history(id);
  329. if (!hist)
  330. return;
  331. mark_or_down(hist, when, 1);
  332. hist->changed = when;
  333. }
  334. /** We have just decided that this router with identity digest <b>id</b> is
  335. * reachable, meaning we will give it a "Running" flag for the next while. */
  336. void
  337. rep_hist_note_router_reachable(const char *id, const tor_addr_t *at_addr,
  338. const uint16_t at_port, time_t when)
  339. {
  340. or_history_t *hist = get_or_history(id);
  341. int was_in_run = 1;
  342. char tbuf[ISO_TIME_LEN+1];
  343. int addr_changed, port_changed;
  344. tor_assert(hist);
  345. tor_assert((!at_addr && !at_port) || (at_addr && at_port));
  346. addr_changed = at_addr && !tor_addr_is_null(&hist->last_reached_addr) &&
  347. tor_addr_compare(at_addr, &hist->last_reached_addr, CMP_EXACT) != 0;
  348. port_changed = at_port && hist->last_reached_port &&
  349. at_port != hist->last_reached_port;
  350. if (!started_tracking_stability)
  351. started_tracking_stability = time(NULL);
  352. if (!hist->start_of_run) {
  353. hist->start_of_run = when;
  354. was_in_run = 0;
  355. }
  356. if (hist->start_of_downtime) {
  357. long down_length;
  358. format_local_iso_time(tbuf, hist->start_of_downtime);
  359. log_info(LD_HIST, "Router %s is now Running; it had been down since %s.",
  360. hex_str(id, DIGEST_LEN), tbuf);
  361. if (was_in_run)
  362. log_info(LD_HIST, " (Paradoxically, it was already Running too.)");
  363. down_length = when - hist->start_of_downtime;
  364. hist->total_weighted_time += down_length;
  365. hist->start_of_downtime = 0;
  366. } else if (addr_changed || port_changed) {
  367. /* If we're reachable, but the address changed, treat this as some
  368. * downtime. */
  369. int penalty = get_options()->TestingTorNetwork ? 240 : 3600;
  370. networkstatus_t *ns;
  371. if ((ns = networkstatus_get_latest_consensus())) {
  372. int fresh_interval = (int)(ns->fresh_until - ns->valid_after);
  373. int live_interval = (int)(ns->valid_until - ns->valid_after);
  374. /* on average, a descriptor addr change takes .5 intervals to make it
  375. * into a consensus, and half a liveness period to make it to
  376. * clients. */
  377. penalty = (int)(fresh_interval + live_interval) / 2;
  378. }
  379. format_local_iso_time(tbuf, hist->start_of_run);
  380. log_info(LD_HIST,"Router %s still seems Running, but its address appears "
  381. "to have changed since the last time it was reachable. I'm "
  382. "going to treat it as having been down for %d seconds",
  383. hex_str(id, DIGEST_LEN), penalty);
  384. rep_hist_note_router_unreachable(id, when-penalty);
  385. rep_hist_note_router_reachable(id, NULL, 0, when);
  386. } else {
  387. format_local_iso_time(tbuf, hist->start_of_run);
  388. if (was_in_run)
  389. log_debug(LD_HIST, "Router %s is still Running; it has been Running "
  390. "since %s", hex_str(id, DIGEST_LEN), tbuf);
  391. else
  392. log_info(LD_HIST,"Router %s is now Running; it was previously untracked",
  393. hex_str(id, DIGEST_LEN));
  394. }
  395. if (at_addr)
  396. tor_addr_copy(&hist->last_reached_addr, at_addr);
  397. if (at_port)
  398. hist->last_reached_port = at_port;
  399. }
  400. /** We have just decided that this router is unreachable, meaning
  401. * we are taking away its "Running" flag. */
  402. void
  403. rep_hist_note_router_unreachable(const char *id, time_t when)
  404. {
  405. or_history_t *hist = get_or_history(id);
  406. char tbuf[ISO_TIME_LEN+1];
  407. int was_running = 0;
  408. if (!started_tracking_stability)
  409. started_tracking_stability = time(NULL);
  410. tor_assert(hist);
  411. if (hist->start_of_run) {
  412. /*XXXX We could treat failed connections differently from failed
  413. * connect attempts. */
  414. long run_length = when - hist->start_of_run;
  415. format_local_iso_time(tbuf, hist->start_of_run);
  416. hist->total_run_weights += 1.0;
  417. hist->start_of_run = 0;
  418. if (run_length < 0) {
  419. unsigned long penalty = -run_length;
  420. #define SUBTRACT_CLAMPED(var, penalty) \
  421. do { (var) = (var) < (penalty) ? 0 : (var) - (penalty); } while (0)
  422. SUBTRACT_CLAMPED(hist->weighted_run_length, penalty);
  423. SUBTRACT_CLAMPED(hist->weighted_uptime, penalty);
  424. } else {
  425. hist->weighted_run_length += run_length;
  426. hist->weighted_uptime += run_length;
  427. hist->total_weighted_time += run_length;
  428. }
  429. was_running = 1;
  430. log_info(LD_HIST, "Router %s is now non-Running: it had previously been "
  431. "Running since %s. Its total weighted uptime is %lu/%lu.",
  432. hex_str(id, DIGEST_LEN), tbuf, hist->weighted_uptime,
  433. hist->total_weighted_time);
  434. }
  435. if (!hist->start_of_downtime) {
  436. hist->start_of_downtime = when;
  437. if (!was_running)
  438. log_info(LD_HIST, "Router %s is now non-Running; it was previously "
  439. "untracked.", hex_str(id, DIGEST_LEN));
  440. } else {
  441. if (!was_running) {
  442. format_local_iso_time(tbuf, hist->start_of_downtime);
  443. log_info(LD_HIST, "Router %s is still non-Running; it has been "
  444. "non-Running since %s.", hex_str(id, DIGEST_LEN), tbuf);
  445. }
  446. }
  447. }
  448. /** Mark a router with ID <b>id</b> as non-Running, and retroactively declare
  449. * that it has never been running: give it no stability and no WFU. */
  450. void
  451. rep_hist_make_router_pessimal(const char *id, time_t when)
  452. {
  453. or_history_t *hist = get_or_history(id);
  454. tor_assert(hist);
  455. rep_hist_note_router_unreachable(id, when);
  456. mark_or_down(hist, when, 1);
  457. hist->weighted_run_length = 0;
  458. hist->weighted_uptime = 0;
  459. }
  460. /** Helper: Discount all old MTBF data, if it is time to do so. Return
  461. * the time at which we should next discount MTBF data. */
  462. time_t
  463. rep_hist_downrate_old_runs(time_t now)
  464. {
  465. digestmap_iter_t *orhist_it;
  466. const char *digest1;
  467. or_history_t *hist;
  468. void *hist_p;
  469. double alpha = 1.0;
  470. if (!history_map)
  471. history_map = digestmap_new();
  472. if (!stability_last_downrated)
  473. stability_last_downrated = now;
  474. if (stability_last_downrated + STABILITY_INTERVAL > now)
  475. return stability_last_downrated + STABILITY_INTERVAL;
  476. /* Okay, we should downrate the data. By how much? */
  477. while (stability_last_downrated + STABILITY_INTERVAL < now) {
  478. stability_last_downrated += STABILITY_INTERVAL;
  479. alpha *= STABILITY_ALPHA;
  480. }
  481. log_info(LD_HIST, "Discounting all old stability info by a factor of %f",
  482. alpha);
  483. /* Multiply every w_r_l, t_r_w pair by alpha. */
  484. for (orhist_it = digestmap_iter_init(history_map);
  485. !digestmap_iter_done(orhist_it);
  486. orhist_it = digestmap_iter_next(history_map,orhist_it)) {
  487. digestmap_iter_get(orhist_it, &digest1, &hist_p);
  488. hist = hist_p;
  489. hist->weighted_run_length =
  490. (unsigned long)(hist->weighted_run_length * alpha);
  491. hist->total_run_weights *= alpha;
  492. hist->weighted_uptime = (unsigned long)(hist->weighted_uptime * alpha);
  493. hist->total_weighted_time = (unsigned long)
  494. (hist->total_weighted_time * alpha);
  495. }
  496. return stability_last_downrated + STABILITY_INTERVAL;
  497. }
  498. /** Helper: Return the weighted MTBF of the router with history <b>hist</b>. */
  499. static double
  500. get_stability(or_history_t *hist, time_t when)
  501. {
  502. long total = hist->weighted_run_length;
  503. double total_weights = hist->total_run_weights;
  504. if (hist->start_of_run) {
  505. /* We're currently in a run. Let total and total_weights hold the values
  506. * they would hold if the current run were to end now. */
  507. total += (when-hist->start_of_run);
  508. total_weights += 1.0;
  509. }
  510. if (total_weights < STABILITY_EPSILON) {
  511. /* Round down to zero, and avoid divide-by-zero. */
  512. return 0.0;
  513. }
  514. return total / total_weights;
  515. }
  516. /** Return the total amount of time we've been observing, with each run of
  517. * time downrated by the appropriate factor. */
  518. static long
  519. get_total_weighted_time(or_history_t *hist, time_t when)
  520. {
  521. long total = hist->total_weighted_time;
  522. if (hist->start_of_run) {
  523. total += (when - hist->start_of_run);
  524. } else if (hist->start_of_downtime) {
  525. total += (when - hist->start_of_downtime);
  526. }
  527. return total;
  528. }
  529. /** Helper: Return the weighted percent-of-time-online of the router with
  530. * history <b>hist</b>. */
  531. static double
  532. get_weighted_fractional_uptime(or_history_t *hist, time_t when)
  533. {
  534. long total = hist->total_weighted_time;
  535. long up = hist->weighted_uptime;
  536. if (hist->start_of_run) {
  537. long run_length = (when - hist->start_of_run);
  538. up += run_length;
  539. total += run_length;
  540. } else if (hist->start_of_downtime) {
  541. total += (when - hist->start_of_downtime);
  542. }
  543. if (!total) {
  544. /* Avoid calling anybody's uptime infinity (which should be impossible if
  545. * the code is working), or NaN (which can happen for any router we haven't
  546. * observed up or down yet). */
  547. return 0.0;
  548. }
  549. return ((double) up) / total;
  550. }
  551. /** Return how long the router whose identity digest is <b>id</b> has
  552. * been reachable. Return 0 if the router is unknown or currently deemed
  553. * unreachable. */
  554. long
  555. rep_hist_get_uptime(const char *id, time_t when)
  556. {
  557. or_history_t *hist = get_or_history(id);
  558. if (!hist)
  559. return 0;
  560. if (!hist->start_of_run || when < hist->start_of_run)
  561. return 0;
  562. return when - hist->start_of_run;
  563. }
  564. /** Return an estimated MTBF for the router whose identity digest is
  565. * <b>id</b>. Return 0 if the router is unknown. */
  566. double
  567. rep_hist_get_stability(const char *id, time_t when)
  568. {
  569. or_history_t *hist = get_or_history(id);
  570. if (!hist)
  571. return 0.0;
  572. return get_stability(hist, when);
  573. }
  574. /** Return an estimated percent-of-time-online for the router whose identity
  575. * digest is <b>id</b>. Return 0 if the router is unknown. */
  576. double
  577. rep_hist_get_weighted_fractional_uptime(const char *id, time_t when)
  578. {
  579. or_history_t *hist = get_or_history(id);
  580. if (!hist)
  581. return 0.0;
  582. return get_weighted_fractional_uptime(hist, when);
  583. }
  584. /** Return a number representing how long we've known about the router whose
  585. * digest is <b>id</b>. Return 0 if the router is unknown.
  586. *
  587. * Be careful: this measure increases monotonically as we know the router for
  588. * longer and longer, but it doesn't increase linearly.
  589. */
  590. long
  591. rep_hist_get_weighted_time_known(const char *id, time_t when)
  592. {
  593. or_history_t *hist = get_or_history(id);
  594. if (!hist)
  595. return 0;
  596. return get_total_weighted_time(hist, when);
  597. }
  598. /** Return true if we've been measuring MTBFs for long enough to
  599. * pronounce on Stability. */
  600. int
  601. rep_hist_have_measured_enough_stability(void)
  602. {
  603. /* XXXX++ This doesn't do so well when we change our opinion
  604. * as to whether we're tracking router stability. */
  605. return started_tracking_stability < time(NULL) - 4*60*60;
  606. }
  607. /** Remember that we successfully extended from the OR with identity
  608. * digest <b>from_id</b> to the OR with identity digest
  609. * <b>to_name</b>.
  610. */
  611. void
  612. rep_hist_note_extend_succeeded(const char *from_id, const char *to_id)
  613. {
  614. link_history_t *hist;
  615. /* log_fn(LOG_WARN, "EXTEND SUCCEEDED: %s->%s",from_name,to_name); */
  616. hist = get_link_history(from_id, to_id);
  617. if (!hist)
  618. return;
  619. ++hist->n_extend_ok;
  620. hist->changed = time(NULL);
  621. }
  622. /** Remember that we tried to extend from the OR with identity digest
  623. * <b>from_id</b> to the OR with identity digest <b>to_name</b>, but
  624. * failed.
  625. */
  626. void
  627. rep_hist_note_extend_failed(const char *from_id, const char *to_id)
  628. {
  629. link_history_t *hist;
  630. /* log_fn(LOG_WARN, "EXTEND FAILED: %s->%s",from_name,to_name); */
  631. hist = get_link_history(from_id, to_id);
  632. if (!hist)
  633. return;
  634. ++hist->n_extend_fail;
  635. hist->changed = time(NULL);
  636. }
  637. /** Log all the reliability data we have remembered, with the chosen
  638. * severity.
  639. */
  640. void
  641. rep_hist_dump_stats(time_t now, int severity)
  642. {
  643. digestmap_iter_t *lhist_it;
  644. digestmap_iter_t *orhist_it;
  645. const char *name1, *name2, *digest1, *digest2;
  646. char hexdigest1[HEX_DIGEST_LEN+1];
  647. char hexdigest2[HEX_DIGEST_LEN+1];
  648. or_history_t *or_history;
  649. link_history_t *link_history;
  650. void *or_history_p, *link_history_p;
  651. double uptime;
  652. char buffer[2048];
  653. size_t len;
  654. int ret;
  655. unsigned long upt, downt;
  656. const node_t *node;
  657. rep_history_clean(now - get_options()->RephistTrackTime);
  658. tor_log(severity, LD_HIST, "--------------- Dumping history information:");
  659. for (orhist_it = digestmap_iter_init(history_map);
  660. !digestmap_iter_done(orhist_it);
  661. orhist_it = digestmap_iter_next(history_map,orhist_it)) {
  662. double s;
  663. long stability;
  664. digestmap_iter_get(orhist_it, &digest1, &or_history_p);
  665. or_history = (or_history_t*) or_history_p;
  666. if ((node = node_get_by_id(digest1)) && node_get_nickname(node))
  667. name1 = node_get_nickname(node);
  668. else
  669. name1 = "(unknown)";
  670. base16_encode(hexdigest1, sizeof(hexdigest1), digest1, DIGEST_LEN);
  671. update_or_history(or_history, now);
  672. upt = or_history->uptime;
  673. downt = or_history->downtime;
  674. s = get_stability(or_history, now);
  675. stability = (long)s;
  676. if (upt+downt) {
  677. uptime = ((double)upt) / (upt+downt);
  678. } else {
  679. uptime=1.0;
  680. }
  681. tor_log(severity, LD_HIST,
  682. "OR %s [%s]: %ld/%ld good connections; uptime %ld/%ld sec (%.2f%%); "
  683. "wmtbf %lu:%02lu:%02lu",
  684. name1, hexdigest1,
  685. or_history->n_conn_ok, or_history->n_conn_fail+or_history->n_conn_ok,
  686. upt, upt+downt, uptime*100.0,
  687. stability/3600, (stability/60)%60, stability%60);
  688. if (!digestmap_isempty(or_history->link_history_map)) {
  689. strlcpy(buffer, " Extend attempts: ", sizeof(buffer));
  690. len = strlen(buffer);
  691. for (lhist_it = digestmap_iter_init(or_history->link_history_map);
  692. !digestmap_iter_done(lhist_it);
  693. lhist_it = digestmap_iter_next(or_history->link_history_map,
  694. lhist_it)) {
  695. digestmap_iter_get(lhist_it, &digest2, &link_history_p);
  696. if ((node = node_get_by_id(digest2)) && node_get_nickname(node))
  697. name2 = node_get_nickname(node);
  698. else
  699. name2 = "(unknown)";
  700. link_history = (link_history_t*) link_history_p;
  701. base16_encode(hexdigest2, sizeof(hexdigest2), digest2, DIGEST_LEN);
  702. ret = tor_snprintf(buffer+len, 2048-len, "%s [%s](%ld/%ld); ",
  703. name2,
  704. hexdigest2,
  705. link_history->n_extend_ok,
  706. link_history->n_extend_ok+link_history->n_extend_fail);
  707. if (ret<0)
  708. break;
  709. else
  710. len += ret;
  711. }
  712. tor_log(severity, LD_HIST, "%s", buffer);
  713. }
  714. }
  715. }
  716. /** Remove history info for routers/links that haven't changed since
  717. * <b>before</b>.
  718. */
  719. void
  720. rep_history_clean(time_t before)
  721. {
  722. int authority = authdir_mode(get_options());
  723. or_history_t *or_history;
  724. link_history_t *link_history;
  725. void *or_history_p, *link_history_p;
  726. digestmap_iter_t *orhist_it, *lhist_it;
  727. const char *d1, *d2;
  728. orhist_it = digestmap_iter_init(history_map);
  729. while (!digestmap_iter_done(orhist_it)) {
  730. int should_remove;
  731. digestmap_iter_get(orhist_it, &d1, &or_history_p);
  732. or_history = or_history_p;
  733. should_remove = authority ?
  734. (or_history->total_run_weights < STABILITY_EPSILON &&
  735. !or_history->start_of_run)
  736. : (or_history->changed < before);
  737. if (should_remove) {
  738. orhist_it = digestmap_iter_next_rmv(history_map, orhist_it);
  739. free_or_history(or_history);
  740. continue;
  741. }
  742. for (lhist_it = digestmap_iter_init(or_history->link_history_map);
  743. !digestmap_iter_done(lhist_it); ) {
  744. digestmap_iter_get(lhist_it, &d2, &link_history_p);
  745. link_history = link_history_p;
  746. if (link_history->changed < before) {
  747. lhist_it = digestmap_iter_next_rmv(or_history->link_history_map,
  748. lhist_it);
  749. rephist_total_alloc -= sizeof(link_history_t);
  750. tor_free(link_history);
  751. continue;
  752. }
  753. lhist_it = digestmap_iter_next(or_history->link_history_map,lhist_it);
  754. }
  755. orhist_it = digestmap_iter_next(history_map, orhist_it);
  756. }
  757. }
  758. /** Write MTBF data to disk. Return 0 on success, negative on failure.
  759. *
  760. * If <b>missing_means_down</b>, then if we're about to write an entry
  761. * that is still considered up but isn't in our routerlist, consider it
  762. * to be down. */
  763. int
  764. rep_hist_record_mtbf_data(time_t now, int missing_means_down)
  765. {
  766. char time_buf[ISO_TIME_LEN+1];
  767. digestmap_iter_t *orhist_it;
  768. const char *digest;
  769. void *or_history_p;
  770. or_history_t *hist;
  771. open_file_t *open_file = NULL;
  772. FILE *f;
  773. {
  774. char *filename = get_datadir_fname("router-stability");
  775. f = start_writing_to_stdio_file(filename, OPEN_FLAGS_REPLACE|O_TEXT, 0600,
  776. &open_file);
  777. tor_free(filename);
  778. if (!f)
  779. return -1;
  780. }
  781. /* File format is:
  782. * FormatLine *KeywordLine Data
  783. *
  784. * FormatLine = "format 1" NL
  785. * KeywordLine = Keyword SP Arguments NL
  786. * Data = "data" NL *RouterMTBFLine "." NL
  787. * RouterMTBFLine = Fingerprint SP WeightedRunLen SP
  788. * TotalRunWeights [SP S=StartRunTime] NL
  789. */
  790. #define PUT(s) STMT_BEGIN if (fputs((s),f)<0) goto err; STMT_END
  791. #define PRINTF(args) STMT_BEGIN if (fprintf args <0) goto err; STMT_END
  792. PUT("format 2\n");
  793. format_iso_time(time_buf, time(NULL));
  794. PRINTF((f, "stored-at %s\n", time_buf));
  795. if (started_tracking_stability) {
  796. format_iso_time(time_buf, started_tracking_stability);
  797. PRINTF((f, "tracked-since %s\n", time_buf));
  798. }
  799. if (stability_last_downrated) {
  800. format_iso_time(time_buf, stability_last_downrated);
  801. PRINTF((f, "last-downrated %s\n", time_buf));
  802. }
  803. PUT("data\n");
  804. /* XXX Nick: now bridge auths record this for all routers too.
  805. * Should we make them record it only for bridge routers? -RD
  806. * Not for 0.2.0. -NM */
  807. for (orhist_it = digestmap_iter_init(history_map);
  808. !digestmap_iter_done(orhist_it);
  809. orhist_it = digestmap_iter_next(history_map,orhist_it)) {
  810. char dbuf[HEX_DIGEST_LEN+1];
  811. const char *t = NULL;
  812. digestmap_iter_get(orhist_it, &digest, &or_history_p);
  813. hist = (or_history_t*) or_history_p;
  814. base16_encode(dbuf, sizeof(dbuf), digest, DIGEST_LEN);
  815. if (missing_means_down && hist->start_of_run &&
  816. !router_get_by_id_digest(digest)) {
  817. /* We think this relay is running, but it's not listed in our
  818. * routerlist. Somehow it fell out without telling us it went
  819. * down. Complain and also correct it. */
  820. log_info(LD_HIST,
  821. "Relay '%s' is listed as up in rephist, but it's not in "
  822. "our routerlist. Correcting.", dbuf);
  823. rep_hist_note_router_unreachable(digest, now);
  824. }
  825. PRINTF((f, "R %s\n", dbuf));
  826. if (hist->start_of_run > 0) {
  827. format_iso_time(time_buf, hist->start_of_run);
  828. t = time_buf;
  829. }
  830. PRINTF((f, "+MTBF %lu %.5f%s%s\n",
  831. hist->weighted_run_length, hist->total_run_weights,
  832. t ? " S=" : "", t ? t : ""));
  833. t = NULL;
  834. if (hist->start_of_downtime > 0) {
  835. format_iso_time(time_buf, hist->start_of_downtime);
  836. t = time_buf;
  837. }
  838. PRINTF((f, "+WFU %lu %lu%s%s\n",
  839. hist->weighted_uptime, hist->total_weighted_time,
  840. t ? " S=" : "", t ? t : ""));
  841. }
  842. PUT(".\n");
  843. #undef PUT
  844. #undef PRINTF
  845. return finish_writing_to_file(open_file);
  846. err:
  847. abort_writing_to_file(open_file);
  848. return -1;
  849. }
  850. /** Helper: return the first j >= i such that !strcmpstart(sl[j], prefix) and
  851. * such that no line sl[k] with i <= k < j starts with "R ". Return -1 if no
  852. * such line exists. */
  853. static int
  854. find_next_with(smartlist_t *sl, int i, const char *prefix)
  855. {
  856. for ( ; i < smartlist_len(sl); ++i) {
  857. const char *line = smartlist_get(sl, i);
  858. if (!strcmpstart(line, prefix))
  859. return i;
  860. if (!strcmpstart(line, "R "))
  861. return -1;
  862. }
  863. return -1;
  864. }
  865. /** How many bad times has parse_possibly_bad_iso_time() parsed? */
  866. static int n_bogus_times = 0;
  867. /** Parse the ISO-formatted time in <b>s</b> into *<b>time_out</b>, but
  868. * round any pre-1970 date to Jan 1, 1970. */
  869. static int
  870. parse_possibly_bad_iso_time(const char *s, time_t *time_out)
  871. {
  872. int year;
  873. char b[5];
  874. strlcpy(b, s, sizeof(b));
  875. b[4] = '\0';
  876. year = (int)tor_parse_long(b, 10, 0, INT_MAX, NULL, NULL);
  877. if (year < 1970) {
  878. *time_out = 0;
  879. ++n_bogus_times;
  880. return 0;
  881. } else
  882. return parse_iso_time(s, time_out);
  883. }
  884. /** We've read a time <b>t</b> from a file stored at <b>stored_at</b>, which
  885. * says we started measuring at <b>started_measuring</b>. Return a new number
  886. * that's about as much before <b>now</b> as <b>t</b> was before
  887. * <b>stored_at</b>.
  888. */
  889. static inline time_t
  890. correct_time(time_t t, time_t now, time_t stored_at, time_t started_measuring)
  891. {
  892. if (t < started_measuring - 24*60*60*365)
  893. return 0;
  894. else if (t < started_measuring)
  895. return started_measuring;
  896. else if (t > stored_at)
  897. return 0;
  898. else {
  899. long run_length = stored_at - t;
  900. t = (time_t)(now - run_length);
  901. if (t < started_measuring)
  902. t = started_measuring;
  903. return t;
  904. }
  905. }
  906. /** Load MTBF data from disk. Returns 0 on success or recoverable error, -1
  907. * on failure. */
  908. int
  909. rep_hist_load_mtbf_data(time_t now)
  910. {
  911. /* XXXX won't handle being called while history is already populated. */
  912. smartlist_t *lines;
  913. const char *line = NULL;
  914. int r=0, i;
  915. time_t last_downrated = 0, stored_at = 0, tracked_since = 0;
  916. time_t latest_possible_start = now;
  917. long format = -1;
  918. {
  919. char *filename = get_datadir_fname("router-stability");
  920. char *d = read_file_to_str(filename, RFTS_IGNORE_MISSING, NULL);
  921. tor_free(filename);
  922. if (!d)
  923. return -1;
  924. lines = smartlist_new();
  925. smartlist_split_string(lines, d, "\n", SPLIT_SKIP_SPACE, 0);
  926. tor_free(d);
  927. }
  928. {
  929. const char *firstline;
  930. if (smartlist_len(lines)>4) {
  931. firstline = smartlist_get(lines, 0);
  932. if (!strcmpstart(firstline, "format "))
  933. format = tor_parse_long(firstline+strlen("format "),
  934. 10, -1, LONG_MAX, NULL, NULL);
  935. }
  936. }
  937. if (format != 1 && format != 2) {
  938. log_warn(LD_HIST,
  939. "Unrecognized format in mtbf history file. Skipping.");
  940. goto err;
  941. }
  942. for (i = 1; i < smartlist_len(lines); ++i) {
  943. line = smartlist_get(lines, i);
  944. if (!strcmp(line, "data"))
  945. break;
  946. if (!strcmpstart(line, "last-downrated ")) {
  947. if (parse_iso_time(line+strlen("last-downrated "), &last_downrated)<0)
  948. log_warn(LD_HIST,"Couldn't parse downrate time in mtbf "
  949. "history file.");
  950. }
  951. if (!strcmpstart(line, "stored-at ")) {
  952. if (parse_iso_time(line+strlen("stored-at "), &stored_at)<0)
  953. log_warn(LD_HIST,"Couldn't parse stored time in mtbf "
  954. "history file.");
  955. }
  956. if (!strcmpstart(line, "tracked-since ")) {
  957. if (parse_iso_time(line+strlen("tracked-since "), &tracked_since)<0)
  958. log_warn(LD_HIST,"Couldn't parse started-tracking time in mtbf "
  959. "history file.");
  960. }
  961. }
  962. if (last_downrated > now)
  963. last_downrated = now;
  964. if (tracked_since > now)
  965. tracked_since = now;
  966. if (!stored_at) {
  967. log_warn(LD_HIST, "No stored time recorded.");
  968. goto err;
  969. }
  970. if (line && !strcmp(line, "data"))
  971. ++i;
  972. n_bogus_times = 0;
  973. for (; i < smartlist_len(lines); ++i) {
  974. char digest[DIGEST_LEN];
  975. char hexbuf[HEX_DIGEST_LEN+1];
  976. char mtbf_timebuf[ISO_TIME_LEN+1];
  977. char wfu_timebuf[ISO_TIME_LEN+1];
  978. time_t start_of_run = 0;
  979. time_t start_of_downtime = 0;
  980. int have_mtbf = 0, have_wfu = 0;
  981. long wrl = 0;
  982. double trw = 0;
  983. long wt_uptime = 0, total_wt_time = 0;
  984. int n;
  985. or_history_t *hist;
  986. line = smartlist_get(lines, i);
  987. if (!strcmp(line, "."))
  988. break;
  989. mtbf_timebuf[0] = '\0';
  990. wfu_timebuf[0] = '\0';
  991. if (format == 1) {
  992. n = tor_sscanf(line, "%40s %ld %lf S=%10s %8s",
  993. hexbuf, &wrl, &trw, mtbf_timebuf, mtbf_timebuf+11);
  994. if (n != 3 && n != 5) {
  995. log_warn(LD_HIST, "Couldn't scan line %s", escaped(line));
  996. continue;
  997. }
  998. have_mtbf = 1;
  999. } else {
  1000. // format == 2.
  1001. int mtbf_idx, wfu_idx;
  1002. if (strcmpstart(line, "R ") || strlen(line) < 2+HEX_DIGEST_LEN)
  1003. continue;
  1004. strlcpy(hexbuf, line+2, sizeof(hexbuf));
  1005. mtbf_idx = find_next_with(lines, i+1, "+MTBF ");
  1006. wfu_idx = find_next_with(lines, i+1, "+WFU ");
  1007. if (mtbf_idx >= 0) {
  1008. const char *mtbfline = smartlist_get(lines, mtbf_idx);
  1009. n = tor_sscanf(mtbfline, "+MTBF %lu %lf S=%10s %8s",
  1010. &wrl, &trw, mtbf_timebuf, mtbf_timebuf+11);
  1011. if (n == 2 || n == 4) {
  1012. have_mtbf = 1;
  1013. } else {
  1014. log_warn(LD_HIST, "Couldn't scan +MTBF line %s",
  1015. escaped(mtbfline));
  1016. }
  1017. }
  1018. if (wfu_idx >= 0) {
  1019. const char *wfuline = smartlist_get(lines, wfu_idx);
  1020. n = tor_sscanf(wfuline, "+WFU %lu %lu S=%10s %8s",
  1021. &wt_uptime, &total_wt_time,
  1022. wfu_timebuf, wfu_timebuf+11);
  1023. if (n == 2 || n == 4) {
  1024. have_wfu = 1;
  1025. } else {
  1026. log_warn(LD_HIST, "Couldn't scan +WFU line %s", escaped(wfuline));
  1027. }
  1028. }
  1029. if (wfu_idx > i)
  1030. i = wfu_idx;
  1031. if (mtbf_idx > i)
  1032. i = mtbf_idx;
  1033. }
  1034. if (base16_decode(digest, DIGEST_LEN,
  1035. hexbuf, HEX_DIGEST_LEN) != DIGEST_LEN) {
  1036. log_warn(LD_HIST, "Couldn't hex string %s", escaped(hexbuf));
  1037. continue;
  1038. }
  1039. hist = get_or_history(digest);
  1040. if (!hist)
  1041. continue;
  1042. if (have_mtbf) {
  1043. if (mtbf_timebuf[0]) {
  1044. mtbf_timebuf[10] = ' ';
  1045. if (parse_possibly_bad_iso_time(mtbf_timebuf, &start_of_run)<0)
  1046. log_warn(LD_HIST, "Couldn't parse time %s",
  1047. escaped(mtbf_timebuf));
  1048. }
  1049. hist->start_of_run = correct_time(start_of_run, now, stored_at,
  1050. tracked_since);
  1051. if (hist->start_of_run < latest_possible_start + wrl)
  1052. latest_possible_start = (time_t)(hist->start_of_run - wrl);
  1053. hist->weighted_run_length = wrl;
  1054. hist->total_run_weights = trw;
  1055. }
  1056. if (have_wfu) {
  1057. if (wfu_timebuf[0]) {
  1058. wfu_timebuf[10] = ' ';
  1059. if (parse_possibly_bad_iso_time(wfu_timebuf, &start_of_downtime)<0)
  1060. log_warn(LD_HIST, "Couldn't parse time %s", escaped(wfu_timebuf));
  1061. }
  1062. }
  1063. hist->start_of_downtime = correct_time(start_of_downtime, now, stored_at,
  1064. tracked_since);
  1065. hist->weighted_uptime = wt_uptime;
  1066. hist->total_weighted_time = total_wt_time;
  1067. }
  1068. if (strcmp(line, "."))
  1069. log_warn(LD_HIST, "Truncated MTBF file.");
  1070. if (tracked_since < 86400*365) /* Recover from insanely early value. */
  1071. tracked_since = latest_possible_start;
  1072. stability_last_downrated = last_downrated;
  1073. started_tracking_stability = tracked_since;
  1074. goto done;
  1075. err:
  1076. r = -1;
  1077. done:
  1078. SMARTLIST_FOREACH(lines, char *, cp, tor_free(cp));
  1079. smartlist_free(lines);
  1080. return r;
  1081. }
  1082. /** For how many seconds do we keep track of individual per-second bandwidth
  1083. * totals? */
  1084. #define NUM_SECS_ROLLING_MEASURE 10
  1085. /** How large are the intervals for which we track and report bandwidth use? */
  1086. #define NUM_SECS_BW_SUM_INTERVAL (4*60*60)
  1087. /** How far in the past do we remember and publish bandwidth use? */
  1088. #define NUM_SECS_BW_SUM_IS_VALID (24*60*60)
  1089. /** How many bandwidth usage intervals do we remember? (derived) */
  1090. #define NUM_TOTALS (NUM_SECS_BW_SUM_IS_VALID/NUM_SECS_BW_SUM_INTERVAL)
  1091. /** Structure to track bandwidth use, and remember the maxima for a given
  1092. * time period.
  1093. */
  1094. typedef struct bw_array_t {
  1095. /** Observation array: Total number of bytes transferred in each of the last
  1096. * NUM_SECS_ROLLING_MEASURE seconds. This is used as a circular array. */
  1097. uint64_t obs[NUM_SECS_ROLLING_MEASURE];
  1098. int cur_obs_idx; /**< Current position in obs. */
  1099. time_t cur_obs_time; /**< Time represented in obs[cur_obs_idx] */
  1100. uint64_t total_obs; /**< Total for all members of obs except
  1101. * obs[cur_obs_idx] */
  1102. uint64_t max_total; /**< Largest value that total_obs has taken on in the
  1103. * current period. */
  1104. uint64_t total_in_period; /**< Total bytes transferred in the current
  1105. * period. */
  1106. /** When does the next period begin? */
  1107. time_t next_period;
  1108. /** Where in 'maxima' should the maximum bandwidth usage for the current
  1109. * period be stored? */
  1110. int next_max_idx;
  1111. /** How many values in maxima/totals have been set ever? */
  1112. int num_maxes_set;
  1113. /** Circular array of the maximum
  1114. * bandwidth-per-NUM_SECS_ROLLING_MEASURE usage for the last
  1115. * NUM_TOTALS periods */
  1116. uint64_t maxima[NUM_TOTALS];
  1117. /** Circular array of the total bandwidth usage for the last NUM_TOTALS
  1118. * periods */
  1119. uint64_t totals[NUM_TOTALS];
  1120. } bw_array_t;
  1121. /** Shift the current period of b forward by one. */
  1122. static void
  1123. commit_max(bw_array_t *b)
  1124. {
  1125. /* Store total from current period. */
  1126. b->totals[b->next_max_idx] = b->total_in_period;
  1127. /* Store maximum from current period. */
  1128. b->maxima[b->next_max_idx++] = b->max_total;
  1129. /* Advance next_period and next_max_idx */
  1130. b->next_period += NUM_SECS_BW_SUM_INTERVAL;
  1131. if (b->next_max_idx == NUM_TOTALS)
  1132. b->next_max_idx = 0;
  1133. if (b->num_maxes_set < NUM_TOTALS)
  1134. ++b->num_maxes_set;
  1135. /* Reset max_total. */
  1136. b->max_total = 0;
  1137. /* Reset total_in_period. */
  1138. b->total_in_period = 0;
  1139. }
  1140. /** Shift the current observation time of <b>b</b> forward by one second. */
  1141. static inline void
  1142. advance_obs(bw_array_t *b)
  1143. {
  1144. int nextidx;
  1145. uint64_t total;
  1146. /* Calculate the total bandwidth for the last NUM_SECS_ROLLING_MEASURE
  1147. * seconds; adjust max_total as needed.*/
  1148. total = b->total_obs + b->obs[b->cur_obs_idx];
  1149. if (total > b->max_total)
  1150. b->max_total = total;
  1151. nextidx = b->cur_obs_idx+1;
  1152. if (nextidx == NUM_SECS_ROLLING_MEASURE)
  1153. nextidx = 0;
  1154. b->total_obs = total - b->obs[nextidx];
  1155. b->obs[nextidx]=0;
  1156. b->cur_obs_idx = nextidx;
  1157. if (++b->cur_obs_time >= b->next_period)
  1158. commit_max(b);
  1159. }
  1160. /** Add <b>n</b> bytes to the number of bytes in <b>b</b> for second
  1161. * <b>when</b>. */
  1162. static inline void
  1163. add_obs(bw_array_t *b, time_t when, uint64_t n)
  1164. {
  1165. if (when < b->cur_obs_time)
  1166. return; /* Don't record data in the past. */
  1167. /* If we're currently adding observations for an earlier second than
  1168. * 'when', advance b->cur_obs_time and b->cur_obs_idx by an
  1169. * appropriate number of seconds, and do all the other housekeeping. */
  1170. while (when > b->cur_obs_time) {
  1171. /* Doing this one second at a time is potentially inefficient, if we start
  1172. with a state file that is very old. Fortunately, it doesn't seem to
  1173. show up in profiles, so we can just ignore it for now. */
  1174. advance_obs(b);
  1175. }
  1176. b->obs[b->cur_obs_idx] += n;
  1177. b->total_in_period += n;
  1178. }
  1179. /** Allocate, initialize, and return a new bw_array. */
  1180. static bw_array_t *
  1181. bw_array_new(void)
  1182. {
  1183. bw_array_t *b;
  1184. time_t start;
  1185. b = tor_malloc_zero(sizeof(bw_array_t));
  1186. rephist_total_alloc += sizeof(bw_array_t);
  1187. start = time(NULL);
  1188. b->cur_obs_time = start;
  1189. b->next_period = start + NUM_SECS_BW_SUM_INTERVAL;
  1190. return b;
  1191. }
  1192. /** Free storage held by bandwidth array <b>b</b>. */
  1193. static void
  1194. bw_array_free(bw_array_t *b)
  1195. {
  1196. if (!b) {
  1197. return;
  1198. }
  1199. rephist_total_alloc -= sizeof(bw_array_t);
  1200. tor_free(b);
  1201. }
  1202. /** Recent history of bandwidth observations for read operations. */
  1203. static bw_array_t *read_array = NULL;
  1204. /** Recent history of bandwidth observations for write operations. */
  1205. static bw_array_t *write_array = NULL;
  1206. /** Recent history of bandwidth observations for read operations for the
  1207. directory protocol. */
  1208. static bw_array_t *dir_read_array = NULL;
  1209. /** Recent history of bandwidth observations for write operations for the
  1210. directory protocol. */
  1211. static bw_array_t *dir_write_array = NULL;
  1212. /** Set up [dir-]read_array and [dir-]write_array, freeing them if they
  1213. * already exist. */
  1214. static void
  1215. bw_arrays_init(void)
  1216. {
  1217. bw_array_free(read_array);
  1218. bw_array_free(write_array);
  1219. bw_array_free(dir_read_array);
  1220. bw_array_free(dir_write_array);
  1221. read_array = bw_array_new();
  1222. write_array = bw_array_new();
  1223. dir_read_array = bw_array_new();
  1224. dir_write_array = bw_array_new();
  1225. }
  1226. /** Remember that we read <b>num_bytes</b> bytes in second <b>when</b>.
  1227. *
  1228. * Add num_bytes to the current running total for <b>when</b>.
  1229. *
  1230. * <b>when</b> can go back to time, but it's safe to ignore calls
  1231. * earlier than the latest <b>when</b> you've heard of.
  1232. */
  1233. void
  1234. rep_hist_note_bytes_written(size_t num_bytes, time_t when)
  1235. {
  1236. /* Maybe a circular array for recent seconds, and step to a new point
  1237. * every time a new second shows up. Or simpler is to just to have
  1238. * a normal array and push down each item every second; it's short.
  1239. */
  1240. /* When a new second has rolled over, compute the sum of the bytes we've
  1241. * seen over when-1 to when-1-NUM_SECS_ROLLING_MEASURE, and stick it
  1242. * somewhere. See rep_hist_bandwidth_assess() below.
  1243. */
  1244. add_obs(write_array, when, num_bytes);
  1245. }
  1246. /** Remember that we wrote <b>num_bytes</b> bytes in second <b>when</b>.
  1247. * (like rep_hist_note_bytes_written() above)
  1248. */
  1249. void
  1250. rep_hist_note_bytes_read(size_t num_bytes, time_t when)
  1251. {
  1252. /* if we're smart, we can make this func and the one above share code */
  1253. add_obs(read_array, when, num_bytes);
  1254. }
  1255. /** Remember that we wrote <b>num_bytes</b> directory bytes in second
  1256. * <b>when</b>. (like rep_hist_note_bytes_written() above)
  1257. */
  1258. void
  1259. rep_hist_note_dir_bytes_written(size_t num_bytes, time_t when)
  1260. {
  1261. add_obs(dir_write_array, when, num_bytes);
  1262. }
  1263. /** Remember that we read <b>num_bytes</b> directory bytes in second
  1264. * <b>when</b>. (like rep_hist_note_bytes_written() above)
  1265. */
  1266. void
  1267. rep_hist_note_dir_bytes_read(size_t num_bytes, time_t when)
  1268. {
  1269. add_obs(dir_read_array, when, num_bytes);
  1270. }
  1271. /** Helper: Return the largest value in b->maxima. (This is equal to the
  1272. * most bandwidth used in any NUM_SECS_ROLLING_MEASURE period for the last
  1273. * NUM_SECS_BW_SUM_IS_VALID seconds.)
  1274. */
  1275. static uint64_t
  1276. find_largest_max(bw_array_t *b)
  1277. {
  1278. int i;
  1279. uint64_t max;
  1280. max=0;
  1281. for (i=0; i<NUM_TOTALS; ++i) {
  1282. if (b->maxima[i]>max)
  1283. max = b->maxima[i];
  1284. }
  1285. return max;
  1286. }
  1287. /** Find the largest sums in the past NUM_SECS_BW_SUM_IS_VALID (roughly)
  1288. * seconds. Find one sum for reading and one for writing. They don't have
  1289. * to be at the same time.
  1290. *
  1291. * Return the smaller of these sums, divided by NUM_SECS_ROLLING_MEASURE.
  1292. */
  1293. int
  1294. rep_hist_bandwidth_assess(void)
  1295. {
  1296. uint64_t w,r;
  1297. r = find_largest_max(read_array);
  1298. w = find_largest_max(write_array);
  1299. if (r>w)
  1300. return (int)(U64_TO_DBL(w)/NUM_SECS_ROLLING_MEASURE);
  1301. else
  1302. return (int)(U64_TO_DBL(r)/NUM_SECS_ROLLING_MEASURE);
  1303. }
  1304. /** Print the bandwidth history of b (either [dir-]read_array or
  1305. * [dir-]write_array) into the buffer pointed to by buf. The format is
  1306. * simply comma separated numbers, from oldest to newest.
  1307. *
  1308. * It returns the number of bytes written.
  1309. */
  1310. static size_t
  1311. rep_hist_fill_bandwidth_history(char *buf, size_t len, const bw_array_t *b)
  1312. {
  1313. char *cp = buf;
  1314. int i, n;
  1315. const or_options_t *options = get_options();
  1316. uint64_t cutoff;
  1317. if (b->num_maxes_set <= b->next_max_idx) {
  1318. /* We haven't been through the circular array yet; time starts at i=0.*/
  1319. i = 0;
  1320. } else {
  1321. /* We've been around the array at least once. The next i to be
  1322. overwritten is the oldest. */
  1323. i = b->next_max_idx;
  1324. }
  1325. if (options->RelayBandwidthRate) {
  1326. /* We don't want to report that we used more bandwidth than the max we're
  1327. * willing to relay; otherwise everybody will know how much traffic
  1328. * we used ourself. */
  1329. cutoff = options->RelayBandwidthRate * NUM_SECS_BW_SUM_INTERVAL;
  1330. } else {
  1331. cutoff = UINT64_MAX;
  1332. }
  1333. for (n=0; n<b->num_maxes_set; ++n,++i) {
  1334. uint64_t total;
  1335. if (i >= NUM_TOTALS)
  1336. i -= NUM_TOTALS;
  1337. tor_assert(i < NUM_TOTALS);
  1338. /* Round the bandwidth used down to the nearest 1k. */
  1339. total = b->totals[i] & ~0x3ff;
  1340. if (total > cutoff)
  1341. total = cutoff;
  1342. if (n==(b->num_maxes_set-1))
  1343. tor_snprintf(cp, len-(cp-buf), U64_FORMAT, U64_PRINTF_ARG(total));
  1344. else
  1345. tor_snprintf(cp, len-(cp-buf), U64_FORMAT",", U64_PRINTF_ARG(total));
  1346. cp += strlen(cp);
  1347. }
  1348. return cp-buf;
  1349. }
  1350. /** Allocate and return lines for representing this server's bandwidth
  1351. * history in its descriptor. We publish these lines in our extra-info
  1352. * descriptor.
  1353. */
  1354. char *
  1355. rep_hist_get_bandwidth_lines(void)
  1356. {
  1357. char *buf, *cp;
  1358. char t[ISO_TIME_LEN+1];
  1359. int r;
  1360. bw_array_t *b = NULL;
  1361. const char *desc = NULL;
  1362. size_t len;
  1363. /* [dirreq-](read|write)-history yyyy-mm-dd HH:MM:SS (n s) n,n,n... */
  1364. /* The n,n,n part above. Largest representation of a uint64_t is 20 chars
  1365. * long, plus the comma. */
  1366. #define MAX_HIST_VALUE_LEN (21*NUM_TOTALS)
  1367. len = (67+MAX_HIST_VALUE_LEN)*4;
  1368. buf = tor_malloc_zero(len);
  1369. cp = buf;
  1370. for (r=0;r<4;++r) {
  1371. char tmp[MAX_HIST_VALUE_LEN];
  1372. size_t slen;
  1373. switch (r) {
  1374. case 0:
  1375. b = write_array;
  1376. desc = "write-history";
  1377. break;
  1378. case 1:
  1379. b = read_array;
  1380. desc = "read-history";
  1381. break;
  1382. case 2:
  1383. b = dir_write_array;
  1384. desc = "dirreq-write-history";
  1385. break;
  1386. case 3:
  1387. b = dir_read_array;
  1388. desc = "dirreq-read-history";
  1389. break;
  1390. }
  1391. tor_assert(b);
  1392. slen = rep_hist_fill_bandwidth_history(tmp, MAX_HIST_VALUE_LEN, b);
  1393. /* If we don't have anything to write, skip to the next entry. */
  1394. if (slen == 0)
  1395. continue;
  1396. format_iso_time(t, b->next_period-NUM_SECS_BW_SUM_INTERVAL);
  1397. tor_snprintf(cp, len-(cp-buf), "%s %s (%d s) ",
  1398. desc, t, NUM_SECS_BW_SUM_INTERVAL);
  1399. cp += strlen(cp);
  1400. strlcat(cp, tmp, len-(cp-buf));
  1401. cp += slen;
  1402. strlcat(cp, "\n", len-(cp-buf));
  1403. ++cp;
  1404. }
  1405. return buf;
  1406. }
  1407. /** Write a single bw_array_t into the Values, Ends, Interval, and Maximum
  1408. * entries of an or_state_t. Done before writing out a new state file. */
  1409. static void
  1410. rep_hist_update_bwhist_state_section(or_state_t *state,
  1411. const bw_array_t *b,
  1412. smartlist_t **s_values,
  1413. smartlist_t **s_maxima,
  1414. time_t *s_begins,
  1415. int *s_interval)
  1416. {
  1417. int i,j;
  1418. uint64_t maxval;
  1419. if (*s_values) {
  1420. SMARTLIST_FOREACH(*s_values, char *, val, tor_free(val));
  1421. smartlist_free(*s_values);
  1422. }
  1423. if (*s_maxima) {
  1424. SMARTLIST_FOREACH(*s_maxima, char *, val, tor_free(val));
  1425. smartlist_free(*s_maxima);
  1426. }
  1427. if (! server_mode(get_options())) {
  1428. /* Clients don't need to store bandwidth history persistently;
  1429. * force these values to the defaults. */
  1430. /* FFFF we should pull the default out of config.c's state table,
  1431. * so we don't have two defaults. */
  1432. if (*s_begins != 0 || *s_interval != 900) {
  1433. time_t now = time(NULL);
  1434. time_t save_at = get_options()->AvoidDiskWrites ? now+3600 : now+600;
  1435. or_state_mark_dirty(state, save_at);
  1436. }
  1437. *s_begins = 0;
  1438. *s_interval = 900;
  1439. *s_values = smartlist_new();
  1440. *s_maxima = smartlist_new();
  1441. return;
  1442. }
  1443. *s_begins = b->next_period;
  1444. *s_interval = NUM_SECS_BW_SUM_INTERVAL;
  1445. *s_values = smartlist_new();
  1446. *s_maxima = smartlist_new();
  1447. /* Set i to first position in circular array */
  1448. i = (b->num_maxes_set <= b->next_max_idx) ? 0 : b->next_max_idx;
  1449. for (j=0; j < b->num_maxes_set; ++j,++i) {
  1450. if (i >= NUM_TOTALS)
  1451. i = 0;
  1452. smartlist_add_asprintf(*s_values, U64_FORMAT,
  1453. U64_PRINTF_ARG(b->totals[i] & ~0x3ff));
  1454. maxval = b->maxima[i] / NUM_SECS_ROLLING_MEASURE;
  1455. smartlist_add_asprintf(*s_maxima, U64_FORMAT,
  1456. U64_PRINTF_ARG(maxval & ~0x3ff));
  1457. }
  1458. smartlist_add_asprintf(*s_values, U64_FORMAT,
  1459. U64_PRINTF_ARG(b->total_in_period & ~0x3ff));
  1460. maxval = b->max_total / NUM_SECS_ROLLING_MEASURE;
  1461. smartlist_add_asprintf(*s_maxima, U64_FORMAT,
  1462. U64_PRINTF_ARG(maxval & ~0x3ff));
  1463. }
  1464. /** Update <b>state</b> with the newest bandwidth history. Done before
  1465. * writing out a new state file. */
  1466. void
  1467. rep_hist_update_state(or_state_t *state)
  1468. {
  1469. #define UPDATE(arrname,st) \
  1470. rep_hist_update_bwhist_state_section(state,\
  1471. (arrname),\
  1472. &state->BWHistory ## st ## Values, \
  1473. &state->BWHistory ## st ## Maxima, \
  1474. &state->BWHistory ## st ## Ends, \
  1475. &state->BWHistory ## st ## Interval)
  1476. UPDATE(write_array, Write);
  1477. UPDATE(read_array, Read);
  1478. UPDATE(dir_write_array, DirWrite);
  1479. UPDATE(dir_read_array, DirRead);
  1480. if (server_mode(get_options())) {
  1481. or_state_mark_dirty(state, time(NULL)+(2*3600));
  1482. }
  1483. #undef UPDATE
  1484. }
  1485. /** Load a single bw_array_t from its Values, Ends, Maxima, and Interval
  1486. * entries in an or_state_t. Done while reading the state file. */
  1487. static int
  1488. rep_hist_load_bwhist_state_section(bw_array_t *b,
  1489. const smartlist_t *s_values,
  1490. const smartlist_t *s_maxima,
  1491. const time_t s_begins,
  1492. const int s_interval)
  1493. {
  1494. time_t now = time(NULL);
  1495. int retval = 0;
  1496. time_t start;
  1497. uint64_t v, mv;
  1498. int i,ok,ok_m = 0;
  1499. int have_maxima = s_maxima && s_values &&
  1500. (smartlist_len(s_values) == smartlist_len(s_maxima));
  1501. if (s_values && s_begins >= now - NUM_SECS_BW_SUM_INTERVAL*NUM_TOTALS) {
  1502. start = s_begins - s_interval*(smartlist_len(s_values));
  1503. if (start > now)
  1504. return 0;
  1505. b->cur_obs_time = start;
  1506. b->next_period = start + NUM_SECS_BW_SUM_INTERVAL;
  1507. SMARTLIST_FOREACH_BEGIN(s_values, const char *, cp) {
  1508. const char *maxstr = NULL;
  1509. v = tor_parse_uint64(cp, 10, 0, UINT64_MAX, &ok, NULL);
  1510. if (have_maxima) {
  1511. maxstr = smartlist_get(s_maxima, cp_sl_idx);
  1512. mv = tor_parse_uint64(maxstr, 10, 0, UINT64_MAX, &ok_m, NULL);
  1513. mv *= NUM_SECS_ROLLING_MEASURE;
  1514. } else {
  1515. /* No maxima known; guess average rate to be conservative. */
  1516. mv = (v / s_interval) * NUM_SECS_ROLLING_MEASURE;
  1517. }
  1518. if (!ok) {
  1519. retval = -1;
  1520. log_notice(LD_HIST, "Could not parse value '%s' into a number.'",cp);
  1521. }
  1522. if (maxstr && !ok_m) {
  1523. retval = -1;
  1524. log_notice(LD_HIST, "Could not parse maximum '%s' into a number.'",
  1525. maxstr);
  1526. }
  1527. if (start < now) {
  1528. time_t cur_start = start;
  1529. time_t actual_interval_len = s_interval;
  1530. uint64_t cur_val = 0;
  1531. /* Calculate the average per second. This is the best we can do
  1532. * because our state file doesn't have per-second resolution. */
  1533. if (start + s_interval > now)
  1534. actual_interval_len = now - start;
  1535. cur_val = v / actual_interval_len;
  1536. /* This is potentially inefficient, but since we don't do it very
  1537. * often it should be ok. */
  1538. while (cur_start < start + actual_interval_len) {
  1539. add_obs(b, cur_start, cur_val);
  1540. ++cur_start;
  1541. }
  1542. b->max_total = mv;
  1543. /* This will result in some fairly choppy history if s_interval
  1544. * is not the same as NUM_SECS_BW_SUM_INTERVAL. XXXX */
  1545. start += actual_interval_len;
  1546. }
  1547. } SMARTLIST_FOREACH_END(cp);
  1548. }
  1549. /* Clean up maxima and observed */
  1550. for (i=0; i<NUM_SECS_ROLLING_MEASURE; ++i) {
  1551. b->obs[i] = 0;
  1552. }
  1553. b->total_obs = 0;
  1554. return retval;
  1555. }
  1556. /** Set bandwidth history from the state file we just loaded. */
  1557. int
  1558. rep_hist_load_state(or_state_t *state, char **err)
  1559. {
  1560. int all_ok = 1;
  1561. /* Assert they already have been malloced */
  1562. tor_assert(read_array && write_array);
  1563. tor_assert(dir_read_array && dir_write_array);
  1564. #define LOAD(arrname,st) \
  1565. if (rep_hist_load_bwhist_state_section( \
  1566. (arrname), \
  1567. state->BWHistory ## st ## Values, \
  1568. state->BWHistory ## st ## Maxima, \
  1569. state->BWHistory ## st ## Ends, \
  1570. state->BWHistory ## st ## Interval)<0) \
  1571. all_ok = 0
  1572. LOAD(write_array, Write);
  1573. LOAD(read_array, Read);
  1574. LOAD(dir_write_array, DirWrite);
  1575. LOAD(dir_read_array, DirRead);
  1576. #undef LOAD
  1577. if (!all_ok) {
  1578. *err = tor_strdup("Parsing of bandwidth history values failed");
  1579. /* and create fresh arrays */
  1580. bw_arrays_init();
  1581. return -1;
  1582. }
  1583. return 0;
  1584. }
  1585. /*********************************************************************/
  1586. /** A single predicted port: used to remember which ports we've made
  1587. * connections to, so that we can try to keep making circuits that can handle
  1588. * those ports. */
  1589. typedef struct predicted_port_t {
  1590. /** The port we connected to */
  1591. uint16_t port;
  1592. /** The time at which we last used it */
  1593. time_t time;
  1594. } predicted_port_t;
  1595. /** A list of port numbers that have been used recently. */
  1596. static smartlist_t *predicted_ports_list=NULL;
  1597. /** We just got an application request for a connection with
  1598. * port <b>port</b>. Remember it for the future, so we can keep
  1599. * some circuits open that will exit to this port.
  1600. */
  1601. static void
  1602. add_predicted_port(time_t now, uint16_t port)
  1603. {
  1604. predicted_port_t *pp = tor_malloc(sizeof(predicted_port_t));
  1605. pp->port = port;
  1606. pp->time = now;
  1607. rephist_total_alloc += sizeof(*pp);
  1608. smartlist_add(predicted_ports_list, pp);
  1609. }
  1610. /** Initialize whatever memory and structs are needed for predicting
  1611. * which ports will be used. Also seed it with port 80, so we'll build
  1612. * circuits on start-up.
  1613. */
  1614. static void
  1615. predicted_ports_init(void)
  1616. {
  1617. predicted_ports_list = smartlist_new();
  1618. add_predicted_port(time(NULL), 80); /* add one to kickstart us */
  1619. }
  1620. /** Free whatever memory is needed for predicting which ports will
  1621. * be used.
  1622. */
  1623. static void
  1624. predicted_ports_free(void)
  1625. {
  1626. rephist_total_alloc -=
  1627. smartlist_len(predicted_ports_list)*sizeof(predicted_port_t);
  1628. SMARTLIST_FOREACH(predicted_ports_list, predicted_port_t *,
  1629. pp, tor_free(pp));
  1630. smartlist_free(predicted_ports_list);
  1631. }
  1632. /** Remember that <b>port</b> has been asked for as of time <b>now</b>.
  1633. * This is used for predicting what sorts of streams we'll make in the
  1634. * future and making exit circuits to anticipate that.
  1635. */
  1636. void
  1637. rep_hist_note_used_port(time_t now, uint16_t port)
  1638. {
  1639. tor_assert(predicted_ports_list);
  1640. if (!port) /* record nothing */
  1641. return;
  1642. SMARTLIST_FOREACH_BEGIN(predicted_ports_list, predicted_port_t *, pp) {
  1643. if (pp->port == port) {
  1644. pp->time = now;
  1645. return;
  1646. }
  1647. } SMARTLIST_FOREACH_END(pp);
  1648. /* it's not there yet; we need to add it */
  1649. add_predicted_port(now, port);
  1650. }
  1651. /** Return a newly allocated pointer to a list of uint16_t * for ports that
  1652. * are likely to be asked for in the near future.
  1653. */
  1654. smartlist_t *
  1655. rep_hist_get_predicted_ports(time_t now)
  1656. {
  1657. int predicted_circs_relevance_time;
  1658. smartlist_t *out = smartlist_new();
  1659. tor_assert(predicted_ports_list);
  1660. predicted_circs_relevance_time = get_options()->PredictedPortsRelevanceTime;
  1661. /* clean out obsolete entries */
  1662. SMARTLIST_FOREACH_BEGIN(predicted_ports_list, predicted_port_t *, pp) {
  1663. if (pp->time + predicted_circs_relevance_time < now) {
  1664. log_debug(LD_CIRC, "Expiring predicted port %d", pp->port);
  1665. rephist_total_alloc -= sizeof(predicted_port_t);
  1666. tor_free(pp);
  1667. SMARTLIST_DEL_CURRENT(predicted_ports_list, pp);
  1668. } else {
  1669. smartlist_add(out, tor_memdup(&pp->port, sizeof(uint16_t)));
  1670. }
  1671. } SMARTLIST_FOREACH_END(pp);
  1672. return out;
  1673. }
  1674. /**
  1675. * Take a list of uint16_t *, and remove every port in the list from the
  1676. * current list of predicted ports.
  1677. */
  1678. void
  1679. rep_hist_remove_predicted_ports(const smartlist_t *rmv_ports)
  1680. {
  1681. /* Let's do this on O(N), not O(N^2). */
  1682. bitarray_t *remove_ports = bitarray_init_zero(UINT16_MAX);
  1683. SMARTLIST_FOREACH(rmv_ports, const uint16_t *, p,
  1684. bitarray_set(remove_ports, *p));
  1685. SMARTLIST_FOREACH_BEGIN(predicted_ports_list, predicted_port_t *, pp) {
  1686. if (bitarray_is_set(remove_ports, pp->port)) {
  1687. tor_free(pp);
  1688. rephist_total_alloc -= sizeof(*pp);
  1689. SMARTLIST_DEL_CURRENT(predicted_ports_list, pp);
  1690. }
  1691. } SMARTLIST_FOREACH_END(pp);
  1692. bitarray_free(remove_ports);
  1693. }
  1694. /** The user asked us to do a resolve. Rather than keeping track of
  1695. * timings and such of resolves, we fake it for now by treating
  1696. * it the same way as a connection to port 80. This way we will continue
  1697. * to have circuits lying around if the user only uses Tor for resolves.
  1698. */
  1699. void
  1700. rep_hist_note_used_resolve(time_t now)
  1701. {
  1702. rep_hist_note_used_port(now, 80);
  1703. }
  1704. /** The last time at which we needed an internal circ. */
  1705. static time_t predicted_internal_time = 0;
  1706. /** The last time we needed an internal circ with good uptime. */
  1707. static time_t predicted_internal_uptime_time = 0;
  1708. /** The last time we needed an internal circ with good capacity. */
  1709. static time_t predicted_internal_capacity_time = 0;
  1710. /** Remember that we used an internal circ at time <b>now</b>. */
  1711. void
  1712. rep_hist_note_used_internal(time_t now, int need_uptime, int need_capacity)
  1713. {
  1714. predicted_internal_time = now;
  1715. if (need_uptime)
  1716. predicted_internal_uptime_time = now;
  1717. if (need_capacity)
  1718. predicted_internal_capacity_time = now;
  1719. }
  1720. /** Return 1 if we've used an internal circ recently; else return 0. */
  1721. int
  1722. rep_hist_get_predicted_internal(time_t now, int *need_uptime,
  1723. int *need_capacity)
  1724. {
  1725. int predicted_circs_relevance_time;
  1726. predicted_circs_relevance_time = get_options()->PredictedPortsRelevanceTime;
  1727. if (!predicted_internal_time) { /* initialize it */
  1728. predicted_internal_time = now;
  1729. predicted_internal_uptime_time = now;
  1730. predicted_internal_capacity_time = now;
  1731. }
  1732. if (predicted_internal_time + predicted_circs_relevance_time < now)
  1733. return 0; /* too long ago */
  1734. if (predicted_internal_uptime_time + predicted_circs_relevance_time >= now)
  1735. *need_uptime = 1;
  1736. // Always predict that we need capacity.
  1737. *need_capacity = 1;
  1738. return 1;
  1739. }
  1740. /** Any ports used lately? These are pre-seeded if we just started
  1741. * up or if we're running a hidden service. */
  1742. int
  1743. any_predicted_circuits(time_t now)
  1744. {
  1745. int predicted_circs_relevance_time;
  1746. predicted_circs_relevance_time = get_options()->PredictedPortsRelevanceTime;
  1747. return smartlist_len(predicted_ports_list) ||
  1748. predicted_internal_time + predicted_circs_relevance_time >= now;
  1749. }
  1750. /** Return 1 if we have no need for circuits currently, else return 0. */
  1751. int
  1752. rep_hist_circbuilding_dormant(time_t now)
  1753. {
  1754. const or_options_t *options = get_options();
  1755. if (any_predicted_circuits(now))
  1756. return 0;
  1757. /* see if we'll still need to build testing circuits */
  1758. if (server_mode(options) &&
  1759. (!check_whether_orport_reachable(options) ||
  1760. !circuit_enough_testing_circs()))
  1761. return 0;
  1762. if (!check_whether_dirport_reachable(options))
  1763. return 0;
  1764. return 1;
  1765. }
  1766. /** Structure to track how many times we've done each public key operation. */
  1767. static struct {
  1768. /** How many directory objects have we signed? */
  1769. unsigned long n_signed_dir_objs;
  1770. /** How many routerdescs have we signed? */
  1771. unsigned long n_signed_routerdescs;
  1772. /** How many directory objects have we verified? */
  1773. unsigned long n_verified_dir_objs;
  1774. /** How many routerdescs have we verified */
  1775. unsigned long n_verified_routerdescs;
  1776. /** How many onionskins have we encrypted to build circuits? */
  1777. unsigned long n_onionskins_encrypted;
  1778. /** How many onionskins have we decrypted to do circuit build requests? */
  1779. unsigned long n_onionskins_decrypted;
  1780. /** How many times have we done the TLS handshake as a client? */
  1781. unsigned long n_tls_client_handshakes;
  1782. /** How many times have we done the TLS handshake as a server? */
  1783. unsigned long n_tls_server_handshakes;
  1784. /** How many PK operations have we done as a hidden service client? */
  1785. unsigned long n_rend_client_ops;
  1786. /** How many PK operations have we done as a hidden service midpoint? */
  1787. unsigned long n_rend_mid_ops;
  1788. /** How many PK operations have we done as a hidden service provider? */
  1789. unsigned long n_rend_server_ops;
  1790. } pk_op_counts = {0,0,0,0,0,0,0,0,0,0,0};
  1791. /** Increment the count of the number of times we've done <b>operation</b>. */
  1792. void
  1793. note_crypto_pk_op(pk_op_t operation)
  1794. {
  1795. switch (operation)
  1796. {
  1797. case SIGN_DIR:
  1798. pk_op_counts.n_signed_dir_objs++;
  1799. break;
  1800. case SIGN_RTR:
  1801. pk_op_counts.n_signed_routerdescs++;
  1802. break;
  1803. case VERIFY_DIR:
  1804. pk_op_counts.n_verified_dir_objs++;
  1805. break;
  1806. case VERIFY_RTR:
  1807. pk_op_counts.n_verified_routerdescs++;
  1808. break;
  1809. case ENC_ONIONSKIN:
  1810. pk_op_counts.n_onionskins_encrypted++;
  1811. break;
  1812. case DEC_ONIONSKIN:
  1813. pk_op_counts.n_onionskins_decrypted++;
  1814. break;
  1815. case TLS_HANDSHAKE_C:
  1816. pk_op_counts.n_tls_client_handshakes++;
  1817. break;
  1818. case TLS_HANDSHAKE_S:
  1819. pk_op_counts.n_tls_server_handshakes++;
  1820. break;
  1821. case REND_CLIENT:
  1822. pk_op_counts.n_rend_client_ops++;
  1823. break;
  1824. case REND_MID:
  1825. pk_op_counts.n_rend_mid_ops++;
  1826. break;
  1827. case REND_SERVER:
  1828. pk_op_counts.n_rend_server_ops++;
  1829. break;
  1830. default:
  1831. log_warn(LD_BUG, "Unknown pk operation %d", operation);
  1832. }
  1833. }
  1834. /** Log the number of times we've done each public/private-key operation. */
  1835. void
  1836. dump_pk_ops(int severity)
  1837. {
  1838. tor_log(severity, LD_HIST,
  1839. "PK operations: %lu directory objects signed, "
  1840. "%lu directory objects verified, "
  1841. "%lu routerdescs signed, "
  1842. "%lu routerdescs verified, "
  1843. "%lu onionskins encrypted, "
  1844. "%lu onionskins decrypted, "
  1845. "%lu client-side TLS handshakes, "
  1846. "%lu server-side TLS handshakes, "
  1847. "%lu rendezvous client operations, "
  1848. "%lu rendezvous middle operations, "
  1849. "%lu rendezvous server operations.",
  1850. pk_op_counts.n_signed_dir_objs,
  1851. pk_op_counts.n_verified_dir_objs,
  1852. pk_op_counts.n_signed_routerdescs,
  1853. pk_op_counts.n_verified_routerdescs,
  1854. pk_op_counts.n_onionskins_encrypted,
  1855. pk_op_counts.n_onionskins_decrypted,
  1856. pk_op_counts.n_tls_client_handshakes,
  1857. pk_op_counts.n_tls_server_handshakes,
  1858. pk_op_counts.n_rend_client_ops,
  1859. pk_op_counts.n_rend_mid_ops,
  1860. pk_op_counts.n_rend_server_ops);
  1861. }
  1862. /*** Exit port statistics ***/
  1863. /* Some constants */
  1864. /** To what multiple should byte numbers be rounded up? */
  1865. #define EXIT_STATS_ROUND_UP_BYTES 1024
  1866. /** To what multiple should stream counts be rounded up? */
  1867. #define EXIT_STATS_ROUND_UP_STREAMS 4
  1868. /** Number of TCP ports */
  1869. #define EXIT_STATS_NUM_PORTS 65536
  1870. /** Top n ports that will be included in exit stats. */
  1871. #define EXIT_STATS_TOP_N_PORTS 10
  1872. /* The following data structures are arrays and no fancy smartlists or maps,
  1873. * so that all write operations can be done in constant time. This comes at
  1874. * the price of some memory (1.25 MB) and linear complexity when writing
  1875. * stats for measuring relays. */
  1876. /** Number of bytes read in current period by exit port */
  1877. static uint64_t *exit_bytes_read = NULL;
  1878. /** Number of bytes written in current period by exit port */
  1879. static uint64_t *exit_bytes_written = NULL;
  1880. /** Number of streams opened in current period by exit port */
  1881. static uint32_t *exit_streams = NULL;
  1882. /** Start time of exit stats or 0 if we're not collecting exit stats. */
  1883. static time_t start_of_exit_stats_interval;
  1884. /** Initialize exit port stats. */
  1885. void
  1886. rep_hist_exit_stats_init(time_t now)
  1887. {
  1888. start_of_exit_stats_interval = now;
  1889. exit_bytes_read = tor_calloc(EXIT_STATS_NUM_PORTS, sizeof(uint64_t));
  1890. exit_bytes_written = tor_calloc(EXIT_STATS_NUM_PORTS, sizeof(uint64_t));
  1891. exit_streams = tor_calloc(EXIT_STATS_NUM_PORTS, sizeof(uint32_t));
  1892. }
  1893. /** Reset counters for exit port statistics. */
  1894. void
  1895. rep_hist_reset_exit_stats(time_t now)
  1896. {
  1897. start_of_exit_stats_interval = now;
  1898. memset(exit_bytes_read, 0, EXIT_STATS_NUM_PORTS * sizeof(uint64_t));
  1899. memset(exit_bytes_written, 0, EXIT_STATS_NUM_PORTS * sizeof(uint64_t));
  1900. memset(exit_streams, 0, EXIT_STATS_NUM_PORTS * sizeof(uint32_t));
  1901. }
  1902. /** Stop collecting exit port stats in a way that we can re-start doing
  1903. * so in rep_hist_exit_stats_init(). */
  1904. void
  1905. rep_hist_exit_stats_term(void)
  1906. {
  1907. start_of_exit_stats_interval = 0;
  1908. tor_free(exit_bytes_read);
  1909. tor_free(exit_bytes_written);
  1910. tor_free(exit_streams);
  1911. }
  1912. /** Helper for qsort: compare two ints. Does not handle overflow properly,
  1913. * but works fine for sorting an array of port numbers, which is what we use
  1914. * it for. */
  1915. static int
  1916. compare_int_(const void *x, const void *y)
  1917. {
  1918. return (*(int*)x - *(int*)y);
  1919. }
  1920. /** Return a newly allocated string containing the exit port statistics
  1921. * until <b>now</b>, or NULL if we're not collecting exit stats. Caller
  1922. * must ensure start_of_exit_stats_interval is in the past. */
  1923. char *
  1924. rep_hist_format_exit_stats(time_t now)
  1925. {
  1926. int i, j, top_elements = 0, cur_min_idx = 0, cur_port;
  1927. uint64_t top_bytes[EXIT_STATS_TOP_N_PORTS];
  1928. int top_ports[EXIT_STATS_TOP_N_PORTS];
  1929. uint64_t cur_bytes = 0, other_read = 0, other_written = 0,
  1930. total_read = 0, total_written = 0;
  1931. uint32_t total_streams = 0, other_streams = 0;
  1932. smartlist_t *written_strings, *read_strings, *streams_strings;
  1933. char *written_string, *read_string, *streams_string;
  1934. char t[ISO_TIME_LEN+1];
  1935. char *result;
  1936. if (!start_of_exit_stats_interval)
  1937. return NULL; /* Not initialized. */
  1938. tor_assert(now >= start_of_exit_stats_interval);
  1939. /* Go through all ports to find the n ports that saw most written and
  1940. * read bytes.
  1941. *
  1942. * Invariant: at the end of the loop for iteration i,
  1943. * total_read is the sum of all exit_bytes_read[0..i]
  1944. * total_written is the sum of all exit_bytes_written[0..i]
  1945. * total_stream is the sum of all exit_streams[0..i]
  1946. *
  1947. * top_elements = MAX(EXIT_STATS_TOP_N_PORTS,
  1948. * #{j | 0 <= j <= i && volume(i) > 0})
  1949. *
  1950. * For all 0 <= j < top_elements,
  1951. * top_bytes[j] > 0
  1952. * 0 <= top_ports[j] <= 65535
  1953. * top_bytes[j] = volume(top_ports[j])
  1954. *
  1955. * There is no j in 0..i and k in 0..top_elements such that:
  1956. * volume(j) > top_bytes[k] AND j is not in top_ports[0..top_elements]
  1957. *
  1958. * There is no j!=cur_min_idx in 0..top_elements such that:
  1959. * top_bytes[j] < top_bytes[cur_min_idx]
  1960. *
  1961. * where volume(x) == exit_bytes_read[x]+exit_bytes_written[x]
  1962. *
  1963. * Worst case: O(EXIT_STATS_NUM_PORTS * EXIT_STATS_TOP_N_PORTS)
  1964. */
  1965. for (i = 1; i < EXIT_STATS_NUM_PORTS; i++) {
  1966. total_read += exit_bytes_read[i];
  1967. total_written += exit_bytes_written[i];
  1968. total_streams += exit_streams[i];
  1969. cur_bytes = exit_bytes_read[i] + exit_bytes_written[i];
  1970. if (cur_bytes == 0) {
  1971. continue;
  1972. }
  1973. if (top_elements < EXIT_STATS_TOP_N_PORTS) {
  1974. top_bytes[top_elements] = cur_bytes;
  1975. top_ports[top_elements++] = i;
  1976. } else if (cur_bytes > top_bytes[cur_min_idx]) {
  1977. top_bytes[cur_min_idx] = cur_bytes;
  1978. top_ports[cur_min_idx] = i;
  1979. } else {
  1980. continue;
  1981. }
  1982. cur_min_idx = 0;
  1983. for (j = 1; j < top_elements; j++) {
  1984. if (top_bytes[j] < top_bytes[cur_min_idx]) {
  1985. cur_min_idx = j;
  1986. }
  1987. }
  1988. }
  1989. /* Add observations of top ports to smartlists. */
  1990. written_strings = smartlist_new();
  1991. read_strings = smartlist_new();
  1992. streams_strings = smartlist_new();
  1993. other_read = total_read;
  1994. other_written = total_written;
  1995. other_streams = total_streams;
  1996. /* Sort the ports; this puts them out of sync with top_bytes, but we
  1997. * won't be using top_bytes again anyway */
  1998. qsort(top_ports, top_elements, sizeof(int), compare_int_);
  1999. for (j = 0; j < top_elements; j++) {
  2000. cur_port = top_ports[j];
  2001. if (exit_bytes_written[cur_port] > 0) {
  2002. uint64_t num = round_uint64_to_next_multiple_of(
  2003. exit_bytes_written[cur_port],
  2004. EXIT_STATS_ROUND_UP_BYTES);
  2005. num /= 1024;
  2006. smartlist_add_asprintf(written_strings, "%d="U64_FORMAT,
  2007. cur_port, U64_PRINTF_ARG(num));
  2008. other_written -= exit_bytes_written[cur_port];
  2009. }
  2010. if (exit_bytes_read[cur_port] > 0) {
  2011. uint64_t num = round_uint64_to_next_multiple_of(
  2012. exit_bytes_read[cur_port],
  2013. EXIT_STATS_ROUND_UP_BYTES);
  2014. num /= 1024;
  2015. smartlist_add_asprintf(read_strings, "%d="U64_FORMAT,
  2016. cur_port, U64_PRINTF_ARG(num));
  2017. other_read -= exit_bytes_read[cur_port];
  2018. }
  2019. if (exit_streams[cur_port] > 0) {
  2020. uint32_t num = round_uint32_to_next_multiple_of(
  2021. exit_streams[cur_port],
  2022. EXIT_STATS_ROUND_UP_STREAMS);
  2023. smartlist_add_asprintf(streams_strings, "%d=%u", cur_port, num);
  2024. other_streams -= exit_streams[cur_port];
  2025. }
  2026. }
  2027. /* Add observations of other ports in a single element. */
  2028. other_written = round_uint64_to_next_multiple_of(other_written,
  2029. EXIT_STATS_ROUND_UP_BYTES);
  2030. other_written /= 1024;
  2031. smartlist_add_asprintf(written_strings, "other="U64_FORMAT,
  2032. U64_PRINTF_ARG(other_written));
  2033. other_read = round_uint64_to_next_multiple_of(other_read,
  2034. EXIT_STATS_ROUND_UP_BYTES);
  2035. other_read /= 1024;
  2036. smartlist_add_asprintf(read_strings, "other="U64_FORMAT,
  2037. U64_PRINTF_ARG(other_read));
  2038. other_streams = round_uint32_to_next_multiple_of(other_streams,
  2039. EXIT_STATS_ROUND_UP_STREAMS);
  2040. smartlist_add_asprintf(streams_strings, "other=%u", other_streams);
  2041. /* Join all observations in single strings. */
  2042. written_string = smartlist_join_strings(written_strings, ",", 0, NULL);
  2043. read_string = smartlist_join_strings(read_strings, ",", 0, NULL);
  2044. streams_string = smartlist_join_strings(streams_strings, ",", 0, NULL);
  2045. SMARTLIST_FOREACH(written_strings, char *, cp, tor_free(cp));
  2046. SMARTLIST_FOREACH(read_strings, char *, cp, tor_free(cp));
  2047. SMARTLIST_FOREACH(streams_strings, char *, cp, tor_free(cp));
  2048. smartlist_free(written_strings);
  2049. smartlist_free(read_strings);
  2050. smartlist_free(streams_strings);
  2051. /* Put everything together. */
  2052. format_iso_time(t, now);
  2053. tor_asprintf(&result, "exit-stats-end %s (%d s)\n"
  2054. "exit-kibibytes-written %s\n"
  2055. "exit-kibibytes-read %s\n"
  2056. "exit-streams-opened %s\n",
  2057. t, (unsigned) (now - start_of_exit_stats_interval),
  2058. written_string,
  2059. read_string,
  2060. streams_string);
  2061. tor_free(written_string);
  2062. tor_free(read_string);
  2063. tor_free(streams_string);
  2064. return result;
  2065. }
  2066. /** If 24 hours have passed since the beginning of the current exit port
  2067. * stats period, write exit stats to $DATADIR/stats/exit-stats (possibly
  2068. * overwriting an existing file) and reset counters. Return when we would
  2069. * next want to write exit stats or 0 if we never want to write. */
  2070. time_t
  2071. rep_hist_exit_stats_write(time_t now)
  2072. {
  2073. char *str = NULL;
  2074. if (!start_of_exit_stats_interval)
  2075. return 0; /* Not initialized. */
  2076. if (start_of_exit_stats_interval + WRITE_STATS_INTERVAL > now)
  2077. goto done; /* Not ready to write. */
  2078. log_info(LD_HIST, "Writing exit port statistics to disk.");
  2079. /* Generate history string. */
  2080. str = rep_hist_format_exit_stats(now);
  2081. /* Reset counters. */
  2082. rep_hist_reset_exit_stats(now);
  2083. /* Try to write to disk. */
  2084. if (!check_or_create_data_subdir("stats")) {
  2085. write_to_data_subdir("stats", "exit-stats", str, "exit port statistics");
  2086. }
  2087. done:
  2088. tor_free(str);
  2089. return start_of_exit_stats_interval + WRITE_STATS_INTERVAL;
  2090. }
  2091. /** Note that we wrote <b>num_written</b> bytes and read <b>num_read</b>
  2092. * bytes to/from an exit connection to <b>port</b>. */
  2093. void
  2094. rep_hist_note_exit_bytes(uint16_t port, size_t num_written,
  2095. size_t num_read)
  2096. {
  2097. if (!start_of_exit_stats_interval)
  2098. return; /* Not initialized. */
  2099. exit_bytes_written[port] += num_written;
  2100. exit_bytes_read[port] += num_read;
  2101. log_debug(LD_HIST, "Written %lu bytes and read %lu bytes to/from an "
  2102. "exit connection to port %d.",
  2103. (unsigned long)num_written, (unsigned long)num_read, port);
  2104. }
  2105. /** Note that we opened an exit stream to <b>port</b>. */
  2106. void
  2107. rep_hist_note_exit_stream_opened(uint16_t port)
  2108. {
  2109. if (!start_of_exit_stats_interval)
  2110. return; /* Not initialized. */
  2111. exit_streams[port]++;
  2112. log_debug(LD_HIST, "Opened exit stream to port %d", port);
  2113. }
  2114. /*** cell statistics ***/
  2115. /** Start of the current buffer stats interval or 0 if we're not
  2116. * collecting buffer statistics. */
  2117. static time_t start_of_buffer_stats_interval;
  2118. /** Initialize buffer stats. */
  2119. void
  2120. rep_hist_buffer_stats_init(time_t now)
  2121. {
  2122. start_of_buffer_stats_interval = now;
  2123. }
  2124. /** Statistics from a single circuit. Collected when the circuit closes, or
  2125. * when we flush statistics to disk. */
  2126. typedef struct circ_buffer_stats_t {
  2127. /** Average number of cells in the circuit's queue */
  2128. double mean_num_cells_in_queue;
  2129. /** Average time a cell waits in the queue. */
  2130. double mean_time_cells_in_queue;
  2131. /** Total number of cells sent over this circuit */
  2132. uint32_t processed_cells;
  2133. } circ_buffer_stats_t;
  2134. /** List of circ_buffer_stats_t. */
  2135. static smartlist_t *circuits_for_buffer_stats = NULL;
  2136. /** Remember cell statistics <b>mean_num_cells_in_queue</b>,
  2137. * <b>mean_time_cells_in_queue</b>, and <b>processed_cells</b> of a
  2138. * circuit. */
  2139. void
  2140. rep_hist_add_buffer_stats(double mean_num_cells_in_queue,
  2141. double mean_time_cells_in_queue, uint32_t processed_cells)
  2142. {
  2143. circ_buffer_stats_t *stats;
  2144. if (!start_of_buffer_stats_interval)
  2145. return; /* Not initialized. */
  2146. stats = tor_malloc_zero(sizeof(circ_buffer_stats_t));
  2147. stats->mean_num_cells_in_queue = mean_num_cells_in_queue;
  2148. stats->mean_time_cells_in_queue = mean_time_cells_in_queue;
  2149. stats->processed_cells = processed_cells;
  2150. if (!circuits_for_buffer_stats)
  2151. circuits_for_buffer_stats = smartlist_new();
  2152. smartlist_add(circuits_for_buffer_stats, stats);
  2153. }
  2154. /** Remember cell statistics for circuit <b>circ</b> at time
  2155. * <b>end_of_interval</b> and reset cell counters in case the circuit
  2156. * remains open in the next measurement interval. */
  2157. void
  2158. rep_hist_buffer_stats_add_circ(circuit_t *circ, time_t end_of_interval)
  2159. {
  2160. time_t start_of_interval;
  2161. int interval_length;
  2162. or_circuit_t *orcirc;
  2163. double mean_num_cells_in_queue, mean_time_cells_in_queue;
  2164. uint32_t processed_cells;
  2165. if (CIRCUIT_IS_ORIGIN(circ))
  2166. return;
  2167. orcirc = TO_OR_CIRCUIT(circ);
  2168. if (!orcirc->processed_cells)
  2169. return;
  2170. start_of_interval = (circ->timestamp_created.tv_sec >
  2171. start_of_buffer_stats_interval) ?
  2172. (time_t)circ->timestamp_created.tv_sec :
  2173. start_of_buffer_stats_interval;
  2174. interval_length = (int) (end_of_interval - start_of_interval);
  2175. if (interval_length <= 0)
  2176. return;
  2177. processed_cells = orcirc->processed_cells;
  2178. /* 1000.0 for s -> ms; 2.0 because of app-ward and exit-ward queues */
  2179. mean_num_cells_in_queue = (double) orcirc->total_cell_waiting_time /
  2180. (double) interval_length / 1000.0 / 2.0;
  2181. mean_time_cells_in_queue =
  2182. (double) orcirc->total_cell_waiting_time /
  2183. (double) orcirc->processed_cells;
  2184. orcirc->total_cell_waiting_time = 0;
  2185. orcirc->processed_cells = 0;
  2186. rep_hist_add_buffer_stats(mean_num_cells_in_queue,
  2187. mean_time_cells_in_queue,
  2188. processed_cells);
  2189. }
  2190. /** Sorting helper: return -1, 1, or 0 based on comparison of two
  2191. * circ_buffer_stats_t */
  2192. static int
  2193. buffer_stats_compare_entries_(const void **_a, const void **_b)
  2194. {
  2195. const circ_buffer_stats_t *a = *_a, *b = *_b;
  2196. if (a->processed_cells < b->processed_cells)
  2197. return 1;
  2198. else if (a->processed_cells > b->processed_cells)
  2199. return -1;
  2200. else
  2201. return 0;
  2202. }
  2203. /** Stop collecting cell stats in a way that we can re-start doing so in
  2204. * rep_hist_buffer_stats_init(). */
  2205. void
  2206. rep_hist_buffer_stats_term(void)
  2207. {
  2208. rep_hist_reset_buffer_stats(0);
  2209. }
  2210. /** Clear history of circuit statistics and set the measurement interval
  2211. * start to <b>now</b>. */
  2212. void
  2213. rep_hist_reset_buffer_stats(time_t now)
  2214. {
  2215. if (!circuits_for_buffer_stats)
  2216. circuits_for_buffer_stats = smartlist_new();
  2217. SMARTLIST_FOREACH(circuits_for_buffer_stats, circ_buffer_stats_t *,
  2218. stats, tor_free(stats));
  2219. smartlist_clear(circuits_for_buffer_stats);
  2220. start_of_buffer_stats_interval = now;
  2221. }
  2222. /** Return a newly allocated string containing the buffer statistics until
  2223. * <b>now</b>, or NULL if we're not collecting buffer stats. Caller must
  2224. * ensure start_of_buffer_stats_interval is in the past. */
  2225. char *
  2226. rep_hist_format_buffer_stats(time_t now)
  2227. {
  2228. #define SHARES 10
  2229. uint64_t processed_cells[SHARES];
  2230. uint32_t circs_in_share[SHARES];
  2231. int number_of_circuits, i;
  2232. double queued_cells[SHARES], time_in_queue[SHARES];
  2233. smartlist_t *processed_cells_strings, *queued_cells_strings,
  2234. *time_in_queue_strings;
  2235. char *processed_cells_string, *queued_cells_string,
  2236. *time_in_queue_string;
  2237. char t[ISO_TIME_LEN+1];
  2238. char *result;
  2239. if (!start_of_buffer_stats_interval)
  2240. return NULL; /* Not initialized. */
  2241. tor_assert(now >= start_of_buffer_stats_interval);
  2242. /* Calculate deciles if we saw at least one circuit. */
  2243. memset(processed_cells, 0, SHARES * sizeof(uint64_t));
  2244. memset(circs_in_share, 0, SHARES * sizeof(uint32_t));
  2245. memset(queued_cells, 0, SHARES * sizeof(double));
  2246. memset(time_in_queue, 0, SHARES * sizeof(double));
  2247. if (!circuits_for_buffer_stats)
  2248. circuits_for_buffer_stats = smartlist_new();
  2249. number_of_circuits = smartlist_len(circuits_for_buffer_stats);
  2250. if (number_of_circuits > 0) {
  2251. smartlist_sort(circuits_for_buffer_stats,
  2252. buffer_stats_compare_entries_);
  2253. i = 0;
  2254. SMARTLIST_FOREACH_BEGIN(circuits_for_buffer_stats,
  2255. circ_buffer_stats_t *, stats)
  2256. {
  2257. int share = i++ * SHARES / number_of_circuits;
  2258. processed_cells[share] += stats->processed_cells;
  2259. queued_cells[share] += stats->mean_num_cells_in_queue;
  2260. time_in_queue[share] += stats->mean_time_cells_in_queue;
  2261. circs_in_share[share]++;
  2262. }
  2263. SMARTLIST_FOREACH_END(stats);
  2264. }
  2265. /* Write deciles to strings. */
  2266. processed_cells_strings = smartlist_new();
  2267. queued_cells_strings = smartlist_new();
  2268. time_in_queue_strings = smartlist_new();
  2269. for (i = 0; i < SHARES; i++) {
  2270. smartlist_add_asprintf(processed_cells_strings,
  2271. U64_FORMAT, !circs_in_share[i] ? 0 :
  2272. U64_PRINTF_ARG(processed_cells[i] /
  2273. circs_in_share[i]));
  2274. }
  2275. for (i = 0; i < SHARES; i++) {
  2276. smartlist_add_asprintf(queued_cells_strings, "%.2f",
  2277. circs_in_share[i] == 0 ? 0.0 :
  2278. queued_cells[i] / (double) circs_in_share[i]);
  2279. }
  2280. for (i = 0; i < SHARES; i++) {
  2281. smartlist_add_asprintf(time_in_queue_strings, "%.0f",
  2282. circs_in_share[i] == 0 ? 0.0 :
  2283. time_in_queue[i] / (double) circs_in_share[i]);
  2284. }
  2285. /* Join all observations in single strings. */
  2286. processed_cells_string = smartlist_join_strings(processed_cells_strings,
  2287. ",", 0, NULL);
  2288. queued_cells_string = smartlist_join_strings(queued_cells_strings,
  2289. ",", 0, NULL);
  2290. time_in_queue_string = smartlist_join_strings(time_in_queue_strings,
  2291. ",", 0, NULL);
  2292. SMARTLIST_FOREACH(processed_cells_strings, char *, cp, tor_free(cp));
  2293. SMARTLIST_FOREACH(queued_cells_strings, char *, cp, tor_free(cp));
  2294. SMARTLIST_FOREACH(time_in_queue_strings, char *, cp, tor_free(cp));
  2295. smartlist_free(processed_cells_strings);
  2296. smartlist_free(queued_cells_strings);
  2297. smartlist_free(time_in_queue_strings);
  2298. /* Put everything together. */
  2299. format_iso_time(t, now);
  2300. tor_asprintf(&result, "cell-stats-end %s (%d s)\n"
  2301. "cell-processed-cells %s\n"
  2302. "cell-queued-cells %s\n"
  2303. "cell-time-in-queue %s\n"
  2304. "cell-circuits-per-decile %d\n",
  2305. t, (unsigned) (now - start_of_buffer_stats_interval),
  2306. processed_cells_string,
  2307. queued_cells_string,
  2308. time_in_queue_string,
  2309. (number_of_circuits + SHARES - 1) / SHARES);
  2310. tor_free(processed_cells_string);
  2311. tor_free(queued_cells_string);
  2312. tor_free(time_in_queue_string);
  2313. return result;
  2314. #undef SHARES
  2315. }
  2316. /** If 24 hours have passed since the beginning of the current buffer
  2317. * stats period, write buffer stats to $DATADIR/stats/buffer-stats
  2318. * (possibly overwriting an existing file) and reset counters. Return
  2319. * when we would next want to write buffer stats or 0 if we never want to
  2320. * write. */
  2321. time_t
  2322. rep_hist_buffer_stats_write(time_t now)
  2323. {
  2324. char *str = NULL;
  2325. if (!start_of_buffer_stats_interval)
  2326. return 0; /* Not initialized. */
  2327. if (start_of_buffer_stats_interval + WRITE_STATS_INTERVAL > now)
  2328. goto done; /* Not ready to write */
  2329. /* Add open circuits to the history. */
  2330. SMARTLIST_FOREACH_BEGIN(circuit_get_global_list(), circuit_t *, circ) {
  2331. rep_hist_buffer_stats_add_circ(circ, now);
  2332. }
  2333. SMARTLIST_FOREACH_END(circ);
  2334. /* Generate history string. */
  2335. str = rep_hist_format_buffer_stats(now);
  2336. /* Reset both buffer history and counters of open circuits. */
  2337. rep_hist_reset_buffer_stats(now);
  2338. /* Try to write to disk. */
  2339. if (!check_or_create_data_subdir("stats")) {
  2340. write_to_data_subdir("stats", "buffer-stats", str, "buffer statistics");
  2341. }
  2342. done:
  2343. tor_free(str);
  2344. return start_of_buffer_stats_interval + WRITE_STATS_INTERVAL;
  2345. }
  2346. /*** Descriptor serving statistics ***/
  2347. /** Digestmap to track which descriptors were downloaded this stats
  2348. * collection interval. It maps descriptor digest to pointers to 1,
  2349. * effectively turning this into a list. */
  2350. static digestmap_t *served_descs = NULL;
  2351. /** Number of how many descriptors were downloaded in total during this
  2352. * interval. */
  2353. static unsigned long total_descriptor_downloads;
  2354. /** Start time of served descs stats or 0 if we're not collecting those. */
  2355. static time_t start_of_served_descs_stats_interval;
  2356. /** Initialize descriptor stats. */
  2357. void
  2358. rep_hist_desc_stats_init(time_t now)
  2359. {
  2360. if (served_descs) {
  2361. log_warn(LD_BUG, "Called rep_hist_desc_stats_init() when desc stats were "
  2362. "already initialized. This is probably harmless.");
  2363. return; // Already initialized
  2364. }
  2365. served_descs = digestmap_new();
  2366. total_descriptor_downloads = 0;
  2367. start_of_served_descs_stats_interval = now;
  2368. }
  2369. /** Reset served descs stats to empty, starting a new interval <b>now</b>. */
  2370. static void
  2371. rep_hist_reset_desc_stats(time_t now)
  2372. {
  2373. rep_hist_desc_stats_term();
  2374. rep_hist_desc_stats_init(now);
  2375. }
  2376. /** Stop collecting served descs stats, so that rep_hist_desc_stats_init() is
  2377. * safe to be called again. */
  2378. void
  2379. rep_hist_desc_stats_term(void)
  2380. {
  2381. digestmap_free(served_descs, NULL);
  2382. served_descs = NULL;
  2383. start_of_served_descs_stats_interval = 0;
  2384. total_descriptor_downloads = 0;
  2385. }
  2386. /** Helper for rep_hist_desc_stats_write(). Return a newly allocated string
  2387. * containing the served desc statistics until now, or NULL if we're not
  2388. * collecting served desc stats. Caller must ensure that now is not before
  2389. * start_of_served_descs_stats_interval. */
  2390. static char *
  2391. rep_hist_format_desc_stats(time_t now)
  2392. {
  2393. char t[ISO_TIME_LEN+1];
  2394. char *result;
  2395. digestmap_iter_t *iter;
  2396. const char *key;
  2397. void *val;
  2398. unsigned size;
  2399. int *vals, max = 0, q3 = 0, md = 0, q1 = 0, min = 0;
  2400. int n = 0;
  2401. if (!start_of_served_descs_stats_interval)
  2402. return NULL;
  2403. size = digestmap_size(served_descs);
  2404. if (size > 0) {
  2405. vals = tor_calloc(size, sizeof(int));
  2406. for (iter = digestmap_iter_init(served_descs);
  2407. !digestmap_iter_done(iter);
  2408. iter = digestmap_iter_next(served_descs, iter)) {
  2409. uintptr_t count;
  2410. digestmap_iter_get(iter, &key, &val);
  2411. count = (uintptr_t)val;
  2412. vals[n++] = (int)count;
  2413. (void)key;
  2414. }
  2415. max = find_nth_int(vals, size, size-1);
  2416. q3 = find_nth_int(vals, size, (3*size-1)/4);
  2417. md = find_nth_int(vals, size, (size-1)/2);
  2418. q1 = find_nth_int(vals, size, (size-1)/4);
  2419. min = find_nth_int(vals, size, 0);
  2420. tor_free(vals);
  2421. }
  2422. format_iso_time(t, now);
  2423. tor_asprintf(&result,
  2424. "served-descs-stats-end %s (%d s) total=%lu unique=%u "
  2425. "max=%d q3=%d md=%d q1=%d min=%d\n",
  2426. t,
  2427. (unsigned) (now - start_of_served_descs_stats_interval),
  2428. total_descriptor_downloads,
  2429. size, max, q3, md, q1, min);
  2430. return result;
  2431. }
  2432. /** If WRITE_STATS_INTERVAL seconds have passed since the beginning of
  2433. * the current served desc stats interval, write the stats to
  2434. * $DATADIR/stats/served-desc-stats (possibly appending to an existing file)
  2435. * and reset the state for the next interval. Return when we would next want
  2436. * to write served desc stats or 0 if we won't want to write. */
  2437. time_t
  2438. rep_hist_desc_stats_write(time_t now)
  2439. {
  2440. char *filename = NULL, *str = NULL;
  2441. if (!start_of_served_descs_stats_interval)
  2442. return 0; /* We're not collecting stats. */
  2443. if (start_of_served_descs_stats_interval + WRITE_STATS_INTERVAL > now)
  2444. return start_of_served_descs_stats_interval + WRITE_STATS_INTERVAL;
  2445. str = rep_hist_format_desc_stats(now);
  2446. tor_assert(str != NULL);
  2447. if (check_or_create_data_subdir("stats") < 0) {
  2448. goto done;
  2449. }
  2450. filename = get_datadir_fname2("stats", "served-desc-stats");
  2451. if (append_bytes_to_file(filename, str, strlen(str), 0) < 0)
  2452. log_warn(LD_HIST, "Unable to write served descs statistics to disk!");
  2453. rep_hist_reset_desc_stats(now);
  2454. done:
  2455. tor_free(filename);
  2456. tor_free(str);
  2457. return start_of_served_descs_stats_interval + WRITE_STATS_INTERVAL;
  2458. }
  2459. /** Called to note that we've served a given descriptor (by
  2460. * digest). Incrememnts the count of descriptors served, and the number
  2461. * of times we've served this descriptor. */
  2462. void
  2463. rep_hist_note_desc_served(const char * desc)
  2464. {
  2465. void *val;
  2466. uintptr_t count;
  2467. if (!served_descs)
  2468. return; // We're not collecting stats
  2469. val = digestmap_get(served_descs, desc);
  2470. count = (uintptr_t)val;
  2471. if (count != INT_MAX)
  2472. ++count;
  2473. digestmap_set(served_descs, desc, (void*)count);
  2474. total_descriptor_downloads++;
  2475. }
  2476. /*** Connection statistics ***/
  2477. /** Start of the current connection stats interval or 0 if we're not
  2478. * collecting connection statistics. */
  2479. static time_t start_of_conn_stats_interval;
  2480. /** Initialize connection stats. */
  2481. void
  2482. rep_hist_conn_stats_init(time_t now)
  2483. {
  2484. start_of_conn_stats_interval = now;
  2485. }
  2486. /* Count connections that we read and wrote less than these many bytes
  2487. * from/to as below threshold. */
  2488. #define BIDI_THRESHOLD 20480
  2489. /* Count connections that we read or wrote at least this factor as many
  2490. * bytes from/to than we wrote or read to/from as mostly reading or
  2491. * writing. */
  2492. #define BIDI_FACTOR 10
  2493. /* Interval length in seconds for considering read and written bytes for
  2494. * connection stats. */
  2495. #define BIDI_INTERVAL 10
  2496. /** Start of next BIDI_INTERVAL second interval. */
  2497. static time_t bidi_next_interval = 0;
  2498. /** Number of connections that we read and wrote less than BIDI_THRESHOLD
  2499. * bytes from/to in BIDI_INTERVAL seconds. */
  2500. static uint32_t below_threshold = 0;
  2501. /** Number of connections that we read at least BIDI_FACTOR times more
  2502. * bytes from than we wrote to in BIDI_INTERVAL seconds. */
  2503. static uint32_t mostly_read = 0;
  2504. /** Number of connections that we wrote at least BIDI_FACTOR times more
  2505. * bytes to than we read from in BIDI_INTERVAL seconds. */
  2506. static uint32_t mostly_written = 0;
  2507. /** Number of connections that we read and wrote at least BIDI_THRESHOLD
  2508. * bytes from/to, but not BIDI_FACTOR times more in either direction in
  2509. * BIDI_INTERVAL seconds. */
  2510. static uint32_t both_read_and_written = 0;
  2511. /** Entry in a map from connection ID to the number of read and written
  2512. * bytes on this connection in a BIDI_INTERVAL second interval. */
  2513. typedef struct bidi_map_entry_t {
  2514. HT_ENTRY(bidi_map_entry_t) node;
  2515. uint64_t conn_id; /**< Connection ID */
  2516. size_t read; /**< Number of read bytes */
  2517. size_t written; /**< Number of written bytes */
  2518. } bidi_map_entry_t;
  2519. /** Map of OR connections together with the number of read and written
  2520. * bytes in the current BIDI_INTERVAL second interval. */
  2521. static HT_HEAD(bidimap, bidi_map_entry_t) bidi_map =
  2522. HT_INITIALIZER();
  2523. static int
  2524. bidi_map_ent_eq(const bidi_map_entry_t *a, const bidi_map_entry_t *b)
  2525. {
  2526. return a->conn_id == b->conn_id;
  2527. }
  2528. /* DOCDOC bidi_map_ent_hash */
  2529. static unsigned
  2530. bidi_map_ent_hash(const bidi_map_entry_t *entry)
  2531. {
  2532. return (unsigned) entry->conn_id;
  2533. }
  2534. HT_PROTOTYPE(bidimap, bidi_map_entry_t, node, bidi_map_ent_hash,
  2535. bidi_map_ent_eq)
  2536. HT_GENERATE2(bidimap, bidi_map_entry_t, node, bidi_map_ent_hash,
  2537. bidi_map_ent_eq, 0.6, tor_reallocarray_, tor_free_)
  2538. /* DOCDOC bidi_map_free */
  2539. static void
  2540. bidi_map_free(void)
  2541. {
  2542. bidi_map_entry_t **ptr, **next, *ent;
  2543. for (ptr = HT_START(bidimap, &bidi_map); ptr; ptr = next) {
  2544. ent = *ptr;
  2545. next = HT_NEXT_RMV(bidimap, &bidi_map, ptr);
  2546. tor_free(ent);
  2547. }
  2548. HT_CLEAR(bidimap, &bidi_map);
  2549. }
  2550. /** Reset counters for conn statistics. */
  2551. void
  2552. rep_hist_reset_conn_stats(time_t now)
  2553. {
  2554. start_of_conn_stats_interval = now;
  2555. below_threshold = 0;
  2556. mostly_read = 0;
  2557. mostly_written = 0;
  2558. both_read_and_written = 0;
  2559. bidi_map_free();
  2560. }
  2561. /** Stop collecting connection stats in a way that we can re-start doing
  2562. * so in rep_hist_conn_stats_init(). */
  2563. void
  2564. rep_hist_conn_stats_term(void)
  2565. {
  2566. rep_hist_reset_conn_stats(0);
  2567. }
  2568. /** We read <b>num_read</b> bytes and wrote <b>num_written</b> from/to OR
  2569. * connection <b>conn_id</b> in second <b>when</b>. If this is the first
  2570. * observation in a new interval, sum up the last observations. Add bytes
  2571. * for this connection. */
  2572. void
  2573. rep_hist_note_or_conn_bytes(uint64_t conn_id, size_t num_read,
  2574. size_t num_written, time_t when)
  2575. {
  2576. if (!start_of_conn_stats_interval)
  2577. return;
  2578. /* Initialize */
  2579. if (bidi_next_interval == 0)
  2580. bidi_next_interval = when + BIDI_INTERVAL;
  2581. /* Sum up last period's statistics */
  2582. if (when >= bidi_next_interval) {
  2583. bidi_map_entry_t **ptr, **next, *ent;
  2584. for (ptr = HT_START(bidimap, &bidi_map); ptr; ptr = next) {
  2585. ent = *ptr;
  2586. if (ent->read + ent->written < BIDI_THRESHOLD)
  2587. below_threshold++;
  2588. else if (ent->read >= ent->written * BIDI_FACTOR)
  2589. mostly_read++;
  2590. else if (ent->written >= ent->read * BIDI_FACTOR)
  2591. mostly_written++;
  2592. else
  2593. both_read_and_written++;
  2594. next = HT_NEXT_RMV(bidimap, &bidi_map, ptr);
  2595. tor_free(ent);
  2596. }
  2597. while (when >= bidi_next_interval)
  2598. bidi_next_interval += BIDI_INTERVAL;
  2599. log_info(LD_GENERAL, "%d below threshold, %d mostly read, "
  2600. "%d mostly written, %d both read and written.",
  2601. below_threshold, mostly_read, mostly_written,
  2602. both_read_and_written);
  2603. }
  2604. /* Add this connection's bytes. */
  2605. if (num_read > 0 || num_written > 0) {
  2606. bidi_map_entry_t *entry, lookup;
  2607. lookup.conn_id = conn_id;
  2608. entry = HT_FIND(bidimap, &bidi_map, &lookup);
  2609. if (entry) {
  2610. entry->written += num_written;
  2611. entry->read += num_read;
  2612. } else {
  2613. entry = tor_malloc_zero(sizeof(bidi_map_entry_t));
  2614. entry->conn_id = conn_id;
  2615. entry->written = num_written;
  2616. entry->read = num_read;
  2617. HT_INSERT(bidimap, &bidi_map, entry);
  2618. }
  2619. }
  2620. }
  2621. /** Return a newly allocated string containing the connection statistics
  2622. * until <b>now</b>, or NULL if we're not collecting conn stats. Caller must
  2623. * ensure start_of_conn_stats_interval is in the past. */
  2624. char *
  2625. rep_hist_format_conn_stats(time_t now)
  2626. {
  2627. char *result, written[ISO_TIME_LEN+1];
  2628. if (!start_of_conn_stats_interval)
  2629. return NULL; /* Not initialized. */
  2630. tor_assert(now >= start_of_conn_stats_interval);
  2631. format_iso_time(written, now);
  2632. tor_asprintf(&result, "conn-bi-direct %s (%d s) %d,%d,%d,%d\n",
  2633. written,
  2634. (unsigned) (now - start_of_conn_stats_interval),
  2635. below_threshold,
  2636. mostly_read,
  2637. mostly_written,
  2638. both_read_and_written);
  2639. return result;
  2640. }
  2641. /** If 24 hours have passed since the beginning of the current conn stats
  2642. * period, write conn stats to $DATADIR/stats/conn-stats (possibly
  2643. * overwriting an existing file) and reset counters. Return when we would
  2644. * next want to write conn stats or 0 if we never want to write. */
  2645. time_t
  2646. rep_hist_conn_stats_write(time_t now)
  2647. {
  2648. char *str = NULL;
  2649. if (!start_of_conn_stats_interval)
  2650. return 0; /* Not initialized. */
  2651. if (start_of_conn_stats_interval + WRITE_STATS_INTERVAL > now)
  2652. goto done; /* Not ready to write */
  2653. /* Generate history string. */
  2654. str = rep_hist_format_conn_stats(now);
  2655. /* Reset counters. */
  2656. rep_hist_reset_conn_stats(now);
  2657. /* Try to write to disk. */
  2658. if (!check_or_create_data_subdir("stats")) {
  2659. write_to_data_subdir("stats", "conn-stats", str, "connection statistics");
  2660. }
  2661. done:
  2662. tor_free(str);
  2663. return start_of_conn_stats_interval + WRITE_STATS_INTERVAL;
  2664. }
  2665. /** Internal statistics to track how many requests of each type of
  2666. * handshake we've received, and how many we've assigned to cpuworkers.
  2667. * Useful for seeing trends in cpu load.
  2668. * @{ */
  2669. STATIC int onion_handshakes_requested[MAX_ONION_HANDSHAKE_TYPE+1] = {0};
  2670. STATIC int onion_handshakes_assigned[MAX_ONION_HANDSHAKE_TYPE+1] = {0};
  2671. /**@}*/
  2672. /** A new onionskin (using the <b>type</b> handshake) has arrived. */
  2673. void
  2674. rep_hist_note_circuit_handshake_requested(uint16_t type)
  2675. {
  2676. if (type <= MAX_ONION_HANDSHAKE_TYPE)
  2677. onion_handshakes_requested[type]++;
  2678. }
  2679. /** We've sent an onionskin (using the <b>type</b> handshake) to a
  2680. * cpuworker. */
  2681. void
  2682. rep_hist_note_circuit_handshake_assigned(uint16_t type)
  2683. {
  2684. if (type <= MAX_ONION_HANDSHAKE_TYPE)
  2685. onion_handshakes_assigned[type]++;
  2686. }
  2687. /** Log our onionskin statistics since the last time we were called. */
  2688. void
  2689. rep_hist_log_circuit_handshake_stats(time_t now)
  2690. {
  2691. (void)now;
  2692. log_notice(LD_HEARTBEAT, "Circuit handshake stats since last time: "
  2693. "%d/%d TAP, %d/%d NTor.",
  2694. onion_handshakes_assigned[ONION_HANDSHAKE_TYPE_TAP],
  2695. onion_handshakes_requested[ONION_HANDSHAKE_TYPE_TAP],
  2696. onion_handshakes_assigned[ONION_HANDSHAKE_TYPE_NTOR],
  2697. onion_handshakes_requested[ONION_HANDSHAKE_TYPE_NTOR]);
  2698. memset(onion_handshakes_assigned, 0, sizeof(onion_handshakes_assigned));
  2699. memset(onion_handshakes_requested, 0, sizeof(onion_handshakes_requested));
  2700. }
  2701. /* Hidden service statistics section */
  2702. /** Start of the current hidden service stats interval or 0 if we're
  2703. * not collecting hidden service statistics. */
  2704. static time_t start_of_hs_stats_interval;
  2705. /** Carries the various hidden service statistics, and any other
  2706. * information needed. */
  2707. typedef struct hs_stats_t {
  2708. /** How many relay cells have we seen as rendezvous points? */
  2709. uint64_t rp_relay_cells_seen;
  2710. /** Set of unique public key digests we've seen this stat period
  2711. * (could also be implemented as sorted smartlist). */
  2712. digestmap_t *onions_seen_this_period;
  2713. } hs_stats_t;
  2714. /** Our statistics structure singleton. */
  2715. static hs_stats_t *hs_stats = NULL;
  2716. /** Allocate, initialize and return an hs_stats_t structure. */
  2717. static hs_stats_t *
  2718. hs_stats_new(void)
  2719. {
  2720. hs_stats_t *new_hs_stats = tor_malloc_zero(sizeof(hs_stats_t));
  2721. new_hs_stats->onions_seen_this_period = digestmap_new();
  2722. return new_hs_stats;
  2723. }
  2724. /** Free an hs_stats_t structure. */
  2725. static void
  2726. hs_stats_free(hs_stats_t *victim_hs_stats)
  2727. {
  2728. if (!victim_hs_stats) {
  2729. return;
  2730. }
  2731. digestmap_free(victim_hs_stats->onions_seen_this_period, NULL);
  2732. tor_free(victim_hs_stats);
  2733. }
  2734. /** Initialize hidden service statistics. */
  2735. void
  2736. rep_hist_hs_stats_init(time_t now)
  2737. {
  2738. if (!hs_stats) {
  2739. hs_stats = hs_stats_new();
  2740. }
  2741. start_of_hs_stats_interval = now;
  2742. }
  2743. /** Clear history of hidden service statistics and set the measurement
  2744. * interval start to <b>now</b>. */
  2745. static void
  2746. rep_hist_reset_hs_stats(time_t now)
  2747. {
  2748. if (!hs_stats) {
  2749. hs_stats = hs_stats_new();
  2750. }
  2751. hs_stats->rp_relay_cells_seen = 0;
  2752. digestmap_free(hs_stats->onions_seen_this_period, NULL);
  2753. hs_stats->onions_seen_this_period = digestmap_new();
  2754. start_of_hs_stats_interval = now;
  2755. }
  2756. /** Stop collecting hidden service stats in a way that we can re-start
  2757. * doing so in rep_hist_buffer_stats_init(). */
  2758. void
  2759. rep_hist_hs_stats_term(void)
  2760. {
  2761. rep_hist_reset_hs_stats(0);
  2762. }
  2763. /** We saw a new HS relay cell, Count it! */
  2764. void
  2765. rep_hist_seen_new_rp_cell(void)
  2766. {
  2767. if (!hs_stats) {
  2768. return; // We're not collecting stats
  2769. }
  2770. hs_stats->rp_relay_cells_seen++;
  2771. }
  2772. /** As HSDirs, we saw another hidden service with public key
  2773. * <b>pubkey</b>. Check whether we have counted it before, if not
  2774. * count it now! */
  2775. void
  2776. rep_hist_stored_maybe_new_hs(const crypto_pk_t *pubkey)
  2777. {
  2778. char pubkey_hash[DIGEST_LEN];
  2779. if (!hs_stats) {
  2780. return; // We're not collecting stats
  2781. }
  2782. /* Get the digest of the pubkey which will be used to detect whether
  2783. we've seen this hidden service before or not. */
  2784. if (crypto_pk_get_digest(pubkey, pubkey_hash) < 0) {
  2785. /* This fail should not happen; key has been validated by
  2786. descriptor parsing code first. */
  2787. return;
  2788. }
  2789. /* Check if this is the first time we've seen this hidden
  2790. service. If it is, count it as new. */
  2791. if (!digestmap_get(hs_stats->onions_seen_this_period,
  2792. pubkey_hash)) {
  2793. digestmap_set(hs_stats->onions_seen_this_period,
  2794. pubkey_hash, (void*)(uintptr_t)1);
  2795. }
  2796. }
  2797. /* The number of cells that are supposed to be hidden from the adversary
  2798. * by adding noise from the Laplace distribution. This value, divided by
  2799. * EPSILON, is Laplace parameter b. It must be greather than 0. */
  2800. #define REND_CELLS_DELTA_F 2048
  2801. /* Security parameter for obfuscating number of cells with a value between
  2802. * ]0.0, 1.0]. Smaller values obfuscate observations more, but at the same
  2803. * time make statistics less usable. */
  2804. #define REND_CELLS_EPSILON 0.3
  2805. /* The number of cells that are supposed to be hidden from the adversary
  2806. * by rounding up to the next multiple of this number. */
  2807. #define REND_CELLS_BIN_SIZE 1024
  2808. /* The number of service identities that are supposed to be hidden from the
  2809. * adversary by adding noise from the Laplace distribution. This value,
  2810. * divided by EPSILON, is Laplace parameter b. It must be greater than 0. */
  2811. #define ONIONS_SEEN_DELTA_F 8
  2812. /* Security parameter for obfuscating number of service identities with a
  2813. * value between ]0.0, 1.0]. Smaller values obfuscate observations more, but
  2814. * at the same time make statistics less usable. */
  2815. #define ONIONS_SEEN_EPSILON 0.3
  2816. /* The number of service identities that are supposed to be hidden from
  2817. * the adversary by rounding up to the next multiple of this number. */
  2818. #define ONIONS_SEEN_BIN_SIZE 8
  2819. /** Allocate and return a string containing hidden service stats that
  2820. * are meant to be placed in the extra-info descriptor. */
  2821. static char *
  2822. rep_hist_format_hs_stats(time_t now)
  2823. {
  2824. char t[ISO_TIME_LEN+1];
  2825. char *hs_stats_string;
  2826. int64_t obfuscated_cells_seen;
  2827. int64_t obfuscated_onions_seen;
  2828. uint64_t rounded_cells_seen
  2829. = round_uint64_to_next_multiple_of(hs_stats->rp_relay_cells_seen,
  2830. REND_CELLS_BIN_SIZE);
  2831. rounded_cells_seen = MIN(rounded_cells_seen, INT64_MAX);
  2832. obfuscated_cells_seen = add_laplace_noise((int64_t)rounded_cells_seen,
  2833. crypto_rand_double(),
  2834. REND_CELLS_DELTA_F, REND_CELLS_EPSILON);
  2835. uint64_t rounded_onions_seen =
  2836. round_uint64_to_next_multiple_of((size_t)digestmap_size(
  2837. hs_stats->onions_seen_this_period),
  2838. ONIONS_SEEN_BIN_SIZE);
  2839. rounded_onions_seen = MIN(rounded_onions_seen, INT64_MAX);
  2840. obfuscated_onions_seen = add_laplace_noise((int64_t)rounded_onions_seen,
  2841. crypto_rand_double(), ONIONS_SEEN_DELTA_F,
  2842. ONIONS_SEEN_EPSILON);
  2843. format_iso_time(t, now);
  2844. tor_asprintf(&hs_stats_string, "hidserv-stats-end %s (%d s)\n"
  2845. "hidserv-rend-relayed-cells "I64_FORMAT" delta_f=%d "
  2846. "epsilon=%.2f bin_size=%d\n"
  2847. "hidserv-dir-onions-seen "I64_FORMAT" delta_f=%d "
  2848. "epsilon=%.2f bin_size=%d\n",
  2849. t, (unsigned) (now - start_of_hs_stats_interval),
  2850. I64_PRINTF_ARG(obfuscated_cells_seen), REND_CELLS_DELTA_F,
  2851. REND_CELLS_EPSILON, REND_CELLS_BIN_SIZE,
  2852. I64_PRINTF_ARG(obfuscated_onions_seen),
  2853. ONIONS_SEEN_DELTA_F,
  2854. ONIONS_SEEN_EPSILON, ONIONS_SEEN_BIN_SIZE);
  2855. return hs_stats_string;
  2856. }
  2857. /** If 24 hours have passed since the beginning of the current HS
  2858. * stats period, write buffer stats to $DATADIR/stats/hidserv-stats
  2859. * (possibly overwriting an existing file) and reset counters. Return
  2860. * when we would next want to write buffer stats or 0 if we never want to
  2861. * write. */
  2862. time_t
  2863. rep_hist_hs_stats_write(time_t now)
  2864. {
  2865. char *str = NULL;
  2866. if (!start_of_hs_stats_interval) {
  2867. return 0; /* Not initialized. */
  2868. }
  2869. if (start_of_hs_stats_interval + WRITE_STATS_INTERVAL > now) {
  2870. goto done; /* Not ready to write */
  2871. }
  2872. /* Generate history string. */
  2873. str = rep_hist_format_hs_stats(now);
  2874. /* Reset HS history. */
  2875. rep_hist_reset_hs_stats(now);
  2876. /* Try to write to disk. */
  2877. if (!check_or_create_data_subdir("stats")) {
  2878. write_to_data_subdir("stats", "hidserv-stats", str,
  2879. "hidden service stats");
  2880. }
  2881. done:
  2882. tor_free(str);
  2883. return start_of_hs_stats_interval + WRITE_STATS_INTERVAL;
  2884. }
  2885. #define MAX_LINK_PROTO_TO_LOG 4
  2886. static uint64_t link_proto_count[MAX_LINK_PROTO_TO_LOG+1][2];
  2887. /** Note that we negotiated link protocol version <b>link_proto</b>, on
  2888. * a connection that started here iff <b>started_here</b> is true.
  2889. */
  2890. void
  2891. rep_hist_note_negotiated_link_proto(unsigned link_proto, int started_here)
  2892. {
  2893. started_here = !!started_here; /* force to 0 or 1 */
  2894. if (link_proto > MAX_LINK_PROTO_TO_LOG) {
  2895. log_warn(LD_BUG, "Can't log link protocol %u", link_proto);
  2896. return;
  2897. }
  2898. link_proto_count[link_proto][started_here]++;
  2899. }
  2900. /** Log a heartbeat message explaining how many connections of each link
  2901. * protocol version we have used.
  2902. */
  2903. void
  2904. rep_hist_log_link_protocol_counts(void)
  2905. {
  2906. log_notice(LD_HEARTBEAT,
  2907. "Since startup, we have initiated "
  2908. U64_FORMAT" v1 connections, "
  2909. U64_FORMAT" v2 connections, "
  2910. U64_FORMAT" v3 connections, and "
  2911. U64_FORMAT" v4 connections; and received "
  2912. U64_FORMAT" v1 connections, "
  2913. U64_FORMAT" v2 connections, "
  2914. U64_FORMAT" v3 connections, and "
  2915. U64_FORMAT" v4 connections.",
  2916. U64_PRINTF_ARG(link_proto_count[1][1]),
  2917. U64_PRINTF_ARG(link_proto_count[2][1]),
  2918. U64_PRINTF_ARG(link_proto_count[3][1]),
  2919. U64_PRINTF_ARG(link_proto_count[4][1]),
  2920. U64_PRINTF_ARG(link_proto_count[1][0]),
  2921. U64_PRINTF_ARG(link_proto_count[2][0]),
  2922. U64_PRINTF_ARG(link_proto_count[3][0]),
  2923. U64_PRINTF_ARG(link_proto_count[4][0]));
  2924. }
  2925. /** Free all storage held by the OR/link history caches, by the
  2926. * bandwidth history arrays, by the port history, or by statistics . */
  2927. void
  2928. rep_hist_free_all(void)
  2929. {
  2930. hs_stats_free(hs_stats);
  2931. digestmap_free(history_map, free_or_history);
  2932. bw_array_free(read_array);
  2933. read_array = NULL;
  2934. bw_array_free(write_array);
  2935. write_array = NULL;
  2936. bw_array_free(dir_read_array);
  2937. dir_read_array = NULL;
  2938. bw_array_free(dir_write_array);
  2939. dir_write_array = NULL;
  2940. tor_free(exit_bytes_read);
  2941. tor_free(exit_bytes_written);
  2942. tor_free(exit_streams);
  2943. predicted_ports_free();
  2944. bidi_map_free();
  2945. if (circuits_for_buffer_stats) {
  2946. SMARTLIST_FOREACH(circuits_for_buffer_stats, circ_buffer_stats_t *, s,
  2947. tor_free(s));
  2948. smartlist_free(circuits_for_buffer_stats);
  2949. circuits_for_buffer_stats = NULL;
  2950. }
  2951. rep_hist_desc_stats_term();
  2952. total_descriptor_downloads = 0;
  2953. tor_assert_nonfatal(rephist_total_alloc == 0);
  2954. tor_assert_nonfatal_once(rephist_total_num == 0);
  2955. }