rephist.c 104 KB

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