rephist.c 65 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844184518461847184818491850185118521853185418551856185718581859186018611862186318641865186618671868186918701871187218731874187518761877187818791880188118821883188418851886188718881889189018911892189318941895189618971898189919001901190219031904190519061907190819091910191119121913191419151916191719181919192019211922192319241925192619271928192919301931193219331934193519361937193819391940194119421943194419451946194719481949195019511952195319541955195619571958195919601961196219631964196519661967196819691970197119721973197419751976197719781979198019811982198319841985198619871988198919901991199219931994199519961997199819992000200120022003200420052006200720082009201020112012201320142015201620172018201920202021202220232024202520262027202820292030203120322033203420352036203720382039204020412042204320442045204620472048204920502051205220532054205520562057205820592060206120622063206420652066206720682069207020712072207320742075207620772078207920802081208220832084208520862087208820892090209120922093209420952096209720982099210021012102210321042105210621072108210921102111
  1. /* Copyright 2004-2007 Roger Dingledine, Nick Mathewson. */
  2. /* See LICENSE for licensing information */
  3. /* $Id$ */
  4. const char rephist_c_id[] =
  5. "$Id$";
  6. /**
  7. * \file rephist.c
  8. * \brief Basic history and "reputation" 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.
  11. **/
  12. #include "or.h"
  13. static void bw_arrays_init(void);
  14. static void predicted_ports_init(void);
  15. static void hs_usage_init(void);
  16. uint64_t rephist_total_alloc=0;
  17. uint32_t rephist_total_num=0;
  18. /** If the total weighted run count of all runs for a router ever falls
  19. * below this amount, the router can be treated as having 0 MTBF. */
  20. #define STABILITY_EPSILON 0.0001
  21. /** Value by which to discount all old intervals for MTBF purposses. This
  22. * is compounded every STABILITY_INTERVAL. */
  23. #define STABILITY_ALPHA 0.95
  24. /** Interval at which to discount all old intervals for MTBF purposes. */
  25. #define STABILITY_INTERVAL (12*60*60)
  26. /* (This combination of ALPHA, INTERVAL, and EPSILON makes it so that an
  27. * interval that just ended counts twice as much as one that ended a week ago,
  28. * 20X as much as one that ended a month ago, and routers that have had no
  29. * uptime data for about half a year will get forgotten.) */
  30. /** History of an OR-\>OR link. */
  31. typedef struct link_history_t {
  32. /** When did we start tracking this list? */
  33. time_t since;
  34. /** When did we most recently note a change to this link */
  35. time_t changed;
  36. /** How many times did extending from OR1 to OR2 succeed? */
  37. unsigned long n_extend_ok;
  38. /** How many times did extending from OR1 to OR2 fail? */
  39. unsigned long n_extend_fail;
  40. } link_history_t;
  41. /** History of an OR. */
  42. typedef struct or_history_t {
  43. /** When did we start tracking this OR? */
  44. time_t since;
  45. /** When did we most recently note a change to this OR? */
  46. time_t changed;
  47. /** How many times did we successfully connect? */
  48. unsigned long n_conn_ok;
  49. /** How many times did we try to connect and fail?*/
  50. unsigned long n_conn_fail;
  51. /** How many seconds have we been connected to this OR before
  52. * 'up_since'? */
  53. unsigned long uptime;
  54. /** How many seconds have we been unable to connect to this OR before
  55. * 'down_since'? */
  56. unsigned long downtime;
  57. /** If nonzero, we have been connected since this time. */
  58. time_t up_since;
  59. /** If nonzero, we have been unable to connect since this time. */
  60. time_t down_since;
  61. /* === For MTBF tracking: */
  62. /** Weighted sum total of all times that this router has been online.
  63. */
  64. unsigned long weighted_run_length;
  65. /** If the router is now online (according to stability-checking rules),
  66. * when did it come online? */
  67. time_t start_of_run;
  68. /** Sum of weights for runs in weighted_run_length. */
  69. double total_run_weights;
  70. /* === For fractional uptime tracking: */
  71. time_t start_of_downtime;
  72. unsigned long weighted_uptime;
  73. unsigned long total_weighted_time;
  74. /** Map from hex OR2 identity digest to a link_history_t for the link
  75. * from this OR to OR2. */
  76. digestmap_t *link_history_map;
  77. } or_history_t;
  78. /** When did we last multiply all routers' weighted_run_length and
  79. * total_run_weights by STABILITY_ALPHA? */
  80. static time_t stability_last_downrated = 0;
  81. /** */
  82. static time_t started_tracking_stability = 0;
  83. /** Map from hex OR identity digest to or_history_t. */
  84. static digestmap_t *history_map = NULL;
  85. /** Return the or_history_t for the OR with identity digest <b>id</b>,
  86. * creating it if necessary. */
  87. static or_history_t *
  88. get_or_history(const char* id)
  89. {
  90. or_history_t *hist;
  91. if (tor_mem_is_zero(id, DIGEST_LEN))
  92. return NULL;
  93. hist = digestmap_get(history_map, id);
  94. if (!hist) {
  95. hist = tor_malloc_zero(sizeof(or_history_t));
  96. rephist_total_alloc += sizeof(or_history_t);
  97. rephist_total_num++;
  98. hist->link_history_map = digestmap_new();
  99. hist->since = hist->changed = time(NULL);
  100. digestmap_set(history_map, id, hist);
  101. }
  102. return hist;
  103. }
  104. /** Return the link_history_t for the link from the first named OR to
  105. * the second, creating it if necessary. (ORs are identified by
  106. * identity digest.)
  107. */
  108. static link_history_t *
  109. get_link_history(const char *from_id, const char *to_id)
  110. {
  111. or_history_t *orhist;
  112. link_history_t *lhist;
  113. orhist = get_or_history(from_id);
  114. if (!orhist)
  115. return NULL;
  116. if (tor_mem_is_zero(to_id, DIGEST_LEN))
  117. return NULL;
  118. lhist = (link_history_t*) digestmap_get(orhist->link_history_map, to_id);
  119. if (!lhist) {
  120. lhist = tor_malloc_zero(sizeof(link_history_t));
  121. rephist_total_alloc += sizeof(link_history_t);
  122. lhist->since = lhist->changed = time(NULL);
  123. digestmap_set(orhist->link_history_map, to_id, lhist);
  124. }
  125. return lhist;
  126. }
  127. /** Helper: free storage held by a single link history entry. */
  128. static void
  129. _free_link_history(void *val)
  130. {
  131. rephist_total_alloc -= sizeof(link_history_t);
  132. tor_free(val);
  133. }
  134. /** Helper: free storage held by a single OR history entry. */
  135. static void
  136. free_or_history(void *_hist)
  137. {
  138. or_history_t *hist = _hist;
  139. digestmap_free(hist->link_history_map, _free_link_history);
  140. rephist_total_alloc -= sizeof(or_history_t);
  141. rephist_total_num--;
  142. tor_free(hist);
  143. }
  144. /** Update an or_history_t object <b>hist</b> so that its uptime/downtime
  145. * count is up-to-date as of <b>when</b>.
  146. */
  147. static void
  148. update_or_history(or_history_t *hist, time_t when)
  149. {
  150. tor_assert(hist);
  151. if (hist->up_since) {
  152. tor_assert(!hist->down_since);
  153. hist->uptime += (when - hist->up_since);
  154. hist->up_since = when;
  155. } else if (hist->down_since) {
  156. hist->downtime += (when - hist->down_since);
  157. hist->down_since = when;
  158. }
  159. }
  160. /** Initialize the static data structures for tracking history. */
  161. void
  162. rep_hist_init(void)
  163. {
  164. history_map = digestmap_new();
  165. bw_arrays_init();
  166. predicted_ports_init();
  167. hs_usage_init();
  168. }
  169. /** Helper: note that we are no longer connected to the router with history
  170. * <b>hist</b>. If <b>failed</b>, the connection failed; otherwise, it was
  171. * closed correctly. */
  172. static void
  173. mark_or_down(or_history_t *hist, time_t when, int failed)
  174. {
  175. if (hist->up_since) {
  176. hist->uptime += (when - hist->up_since);
  177. hist->up_since = 0;
  178. }
  179. if (failed && !hist->down_since) {
  180. hist->down_since = when;
  181. }
  182. }
  183. /** Helper: note that we are connected to the router with history
  184. * <b>hist</b>. */
  185. static void
  186. mark_or_up(or_history_t *hist, time_t when)
  187. {
  188. if (hist->down_since) {
  189. hist->downtime += (when - hist->down_since);
  190. hist->down_since = 0;
  191. }
  192. if (!hist->up_since) {
  193. hist->up_since = when;
  194. }
  195. }
  196. /** Remember that an attempt to connect to the OR with identity digest
  197. * <b>id</b> failed at <b>when</b>.
  198. */
  199. void
  200. rep_hist_note_connect_failed(const char* id, time_t when)
  201. {
  202. or_history_t *hist;
  203. hist = get_or_history(id);
  204. if (!hist)
  205. return;
  206. ++hist->n_conn_fail;
  207. mark_or_down(hist, when, 1);
  208. hist->changed = when;
  209. }
  210. /** Remember that an attempt to connect to the OR with identity digest
  211. * <b>id</b> succeeded at <b>when</b>.
  212. */
  213. void
  214. rep_hist_note_connect_succeeded(const char* id, time_t when)
  215. {
  216. or_history_t *hist;
  217. hist = get_or_history(id);
  218. if (!hist)
  219. return;
  220. ++hist->n_conn_ok;
  221. mark_or_up(hist, when);
  222. hist->changed = when;
  223. }
  224. /** Remember that we intentionally closed our connection to the OR
  225. * with identity digest <b>id</b> at <b>when</b>.
  226. */
  227. void
  228. rep_hist_note_disconnect(const char* id, time_t when)
  229. {
  230. or_history_t *hist;
  231. hist = get_or_history(id);
  232. if (!hist)
  233. return;
  234. mark_or_down(hist, when, 0);
  235. hist->changed = when;
  236. }
  237. /** Remember that our connection to the OR with identity digest
  238. * <b>id</b> had an error and stopped working at <b>when</b>.
  239. */
  240. void
  241. rep_hist_note_connection_died(const char* id, time_t when)
  242. {
  243. or_history_t *hist;
  244. if (!id) {
  245. /* If conn has no identity, it didn't complete its handshake, or something
  246. * went wrong. Ignore it.
  247. */
  248. return;
  249. }
  250. hist = get_or_history(id);
  251. if (!hist)
  252. return;
  253. mark_or_down(hist, when, 1);
  254. hist->changed = when;
  255. }
  256. /** We have just decided that this router is reachable, meaning
  257. * we will give it a "Running" flag for the next while. */
  258. void
  259. rep_hist_note_router_reachable(const char *id, time_t when)
  260. {
  261. or_history_t *hist = get_or_history(id);
  262. if (!started_tracking_stability)
  263. started_tracking_stability = time(NULL);
  264. if (hist && !hist->start_of_run) {
  265. hist->start_of_run = when;
  266. }
  267. if (hist && hist->start_of_downtime) {
  268. long down_length = when - hist->start_of_downtime;
  269. hist->total_weighted_time += down_length;
  270. hist->start_of_downtime = 0;
  271. }
  272. }
  273. /** We have just decided that this router is unreachable, meaning
  274. * we are taking away its "Running" flag. */
  275. void
  276. rep_hist_note_router_unreachable(const char *id, time_t when)
  277. {
  278. or_history_t *hist = get_or_history(id);
  279. if (!started_tracking_stability)
  280. started_tracking_stability = time(NULL);
  281. if (hist && hist->start_of_run) {
  282. /*XXXX020 treat failure specially? */
  283. long run_length = when - hist->start_of_run;
  284. hist->weighted_run_length += run_length;
  285. hist->total_run_weights += 1.0;
  286. hist->start_of_run = 0;
  287. hist->weighted_uptime += run_length;
  288. hist->total_weighted_time += run_length;
  289. }
  290. if (hist && !hist->start_of_downtime) {
  291. hist->start_of_downtime = when;
  292. }
  293. }
  294. /** Helper: Discount all old MTBF data, if it is time to do so. Return
  295. * the time at which we should next discount MTBF data. */
  296. time_t
  297. rep_hist_downrate_old_runs(time_t now)
  298. {
  299. digestmap_iter_t *orhist_it;
  300. const char *digest1;
  301. or_history_t *hist;
  302. void *hist_p;
  303. double alpha = 1.0;
  304. if (!history_map)
  305. history_map = digestmap_new();
  306. if (!stability_last_downrated)
  307. stability_last_downrated = now;
  308. if (stability_last_downrated + STABILITY_INTERVAL > now)
  309. return stability_last_downrated + STABILITY_INTERVAL;
  310. /* Okay, we should downrate the data. By how much? */
  311. while (stability_last_downrated + STABILITY_INTERVAL < now) {
  312. stability_last_downrated += STABILITY_INTERVAL;
  313. alpha *= STABILITY_ALPHA;
  314. }
  315. /* Multiply every w_r_l, t_r_w pair by alpha. */
  316. for (orhist_it = digestmap_iter_init(history_map);
  317. !digestmap_iter_done(orhist_it);
  318. orhist_it = digestmap_iter_next(history_map,orhist_it)) {
  319. digestmap_iter_get(orhist_it, &digest1, &hist_p);
  320. hist = hist_p;
  321. hist->weighted_run_length =
  322. (unsigned long)(hist->weighted_run_length * alpha);
  323. hist->total_run_weights *= alpha;
  324. hist->weighted_uptime *= alpha;
  325. hist->total_weighted_time *= alpha;
  326. }
  327. return stability_last_downrated + STABILITY_INTERVAL;
  328. }
  329. /** Helper: Return the weighted MTBF of the router with history <b>hist</b>. */
  330. static double
  331. get_stability(or_history_t *hist, time_t when)
  332. {
  333. unsigned long total = hist->weighted_run_length;
  334. double total_weights = hist->total_run_weights;
  335. if (hist->start_of_run) {
  336. /* We're currently in a run. Let total and total_weights hold the values
  337. * they would hold if the current run were to end now. */
  338. total += (when-hist->start_of_run);
  339. total_weights += 1.0;
  340. }
  341. if (total_weights < STABILITY_EPSILON) {
  342. /* Round down to zero, and avoid divide-by-zero. */
  343. return 0.0;
  344. }
  345. return total / total_weights;
  346. }
  347. /** Helper: Return the weighted percent-of-time-online of the router with
  348. * history <b>hist</b>. */
  349. static double
  350. get_weighted_fractional_uptime(or_history_t *hist, time_t when)
  351. {
  352. unsigned long total = hist->total_weighted_time;
  353. unsigned long up = hist->weighted_uptime;
  354. if (hist->start_of_run) {
  355. long run_length = (when - hist->start_of_run);
  356. up += run_length;
  357. total += run_length;
  358. } else if (hist->start_of_downtime) {
  359. total += (when - hist->start_of_downtime);
  360. }
  361. return ((double) up) / total;
  362. }
  363. /** Return an estimated MTBF for the router whose identity digest is
  364. * <b>id</b>. Return 0 if the router is unknown. */
  365. double
  366. rep_hist_get_stability(const char *id, time_t when)
  367. {
  368. or_history_t *hist = get_or_history(id);
  369. if (!hist)
  370. return 0.0;
  371. return get_stability(hist, when);
  372. }
  373. /** Return an estimated percent-of-time-online for the router whose identity
  374. * digest is <b>id</b>. Return 0 if the router is unknown. */
  375. double
  376. rep_hist_get_weighted_fractional_uptime(const char *id, time_t when)
  377. {
  378. or_history_t *hist = get_or_history(id);
  379. if (!hist)
  380. return 0.0;
  381. return get_weighted_fractional_uptime(hist, when);
  382. }
  383. /** Return true if we've been measuring MTBFs for long enough to
  384. * prounounce on Stability. */
  385. int
  386. rep_hist_have_measured_enough_stability(void)
  387. {
  388. /* XXXX020 This doesn't do so well when we change our opinion
  389. * as to whether we're tracking router stability. */
  390. return started_tracking_stability < time(NULL) - 4*60*60;
  391. }
  392. /** Remember that we successfully extended from the OR with identity
  393. * digest <b>from_id</b> to the OR with identity digest
  394. * <b>to_name</b>.
  395. */
  396. void
  397. rep_hist_note_extend_succeeded(const char *from_id, const char *to_id)
  398. {
  399. link_history_t *hist;
  400. /* log_fn(LOG_WARN, "EXTEND SUCCEEDED: %s->%s",from_name,to_name); */
  401. hist = get_link_history(from_id, to_id);
  402. if (!hist)
  403. return;
  404. ++hist->n_extend_ok;
  405. hist->changed = time(NULL);
  406. }
  407. /** Remember that we tried to extend from the OR with identity digest
  408. * <b>from_id</b> to the OR with identity digest <b>to_name</b>, but
  409. * failed.
  410. */
  411. void
  412. rep_hist_note_extend_failed(const char *from_id, const char *to_id)
  413. {
  414. link_history_t *hist;
  415. /* log_fn(LOG_WARN, "EXTEND FAILED: %s->%s",from_name,to_name); */
  416. hist = get_link_history(from_id, to_id);
  417. if (!hist)
  418. return;
  419. ++hist->n_extend_fail;
  420. hist->changed = time(NULL);
  421. }
  422. /** Log all the reliability data we have remembered, with the chosen
  423. * severity.
  424. */
  425. void
  426. rep_hist_dump_stats(time_t now, int severity)
  427. {
  428. digestmap_iter_t *lhist_it;
  429. digestmap_iter_t *orhist_it;
  430. const char *name1, *name2, *digest1, *digest2;
  431. char hexdigest1[HEX_DIGEST_LEN+1];
  432. or_history_t *or_history;
  433. link_history_t *link_history;
  434. void *or_history_p, *link_history_p;
  435. double uptime;
  436. char buffer[2048];
  437. size_t len;
  438. int ret;
  439. unsigned long upt, downt;
  440. routerinfo_t *r;
  441. rep_history_clean(now - get_options()->RephistTrackTime);
  442. log(severity, LD_GENERAL, "--------------- Dumping history information:");
  443. for (orhist_it = digestmap_iter_init(history_map);
  444. !digestmap_iter_done(orhist_it);
  445. orhist_it = digestmap_iter_next(history_map,orhist_it)) {
  446. double s;
  447. long stability;
  448. digestmap_iter_get(orhist_it, &digest1, &or_history_p);
  449. or_history = (or_history_t*) or_history_p;
  450. if ((r = router_get_by_digest(digest1)))
  451. name1 = r->nickname;
  452. else
  453. name1 = "(unknown)";
  454. base16_encode(hexdigest1, sizeof(hexdigest1), digest1, DIGEST_LEN);
  455. update_or_history(or_history, now);
  456. upt = or_history->uptime;
  457. downt = or_history->downtime;
  458. s = get_stability(or_history, now);
  459. stability = (long)s;
  460. if (upt+downt) {
  461. uptime = ((double)upt) / (upt+downt);
  462. } else {
  463. uptime=1.0;
  464. }
  465. log(severity, LD_GENERAL,
  466. "OR %s [%s]: %ld/%ld good connections; uptime %ld/%ld sec (%.2f%%); "
  467. "wmtbf %lu:%02lu:%02lu",
  468. name1, hexdigest1,
  469. or_history->n_conn_ok, or_history->n_conn_fail+or_history->n_conn_ok,
  470. upt, upt+downt, uptime*100.0,
  471. stability/3600, (stability/60)%60, stability%60);
  472. if (!digestmap_isempty(or_history->link_history_map)) {
  473. strlcpy(buffer, " Extend attempts: ", sizeof(buffer));
  474. len = strlen(buffer);
  475. for (lhist_it = digestmap_iter_init(or_history->link_history_map);
  476. !digestmap_iter_done(lhist_it);
  477. lhist_it = digestmap_iter_next(or_history->link_history_map,
  478. lhist_it)) {
  479. digestmap_iter_get(lhist_it, &digest2, &link_history_p);
  480. if ((r = router_get_by_digest(digest2)))
  481. name2 = r->nickname;
  482. else
  483. name2 = "(unknown)";
  484. link_history = (link_history_t*) link_history_p;
  485. ret = tor_snprintf(buffer+len, 2048-len, "%s(%ld/%ld); ", name2,
  486. link_history->n_extend_ok,
  487. link_history->n_extend_ok+link_history->n_extend_fail);
  488. if (ret<0)
  489. break;
  490. else
  491. len += ret;
  492. }
  493. log(severity, LD_GENERAL, "%s", buffer);
  494. }
  495. }
  496. }
  497. /** Remove history info for routers/links that haven't changed since
  498. * <b>before</b>.
  499. */
  500. void
  501. rep_history_clean(time_t before)
  502. {
  503. int authority = authdir_mode(get_options());
  504. or_history_t *or_history;
  505. link_history_t *link_history;
  506. void *or_history_p, *link_history_p;
  507. digestmap_iter_t *orhist_it, *lhist_it;
  508. const char *d1, *d2;
  509. orhist_it = digestmap_iter_init(history_map);
  510. while (!digestmap_iter_done(orhist_it)) {
  511. int remove;
  512. digestmap_iter_get(orhist_it, &d1, &or_history_p);
  513. or_history = or_history_p;
  514. remove = authority ? (or_history->total_run_weights < STABILITY_EPSILON &&
  515. !or_history->start_of_run)
  516. : (or_history->changed < before);
  517. if (remove) {
  518. orhist_it = digestmap_iter_next_rmv(history_map, orhist_it);
  519. free_or_history(or_history);
  520. continue;
  521. }
  522. for (lhist_it = digestmap_iter_init(or_history->link_history_map);
  523. !digestmap_iter_done(lhist_it); ) {
  524. digestmap_iter_get(lhist_it, &d2, &link_history_p);
  525. link_history = link_history_p;
  526. if (link_history->changed < before) {
  527. lhist_it = digestmap_iter_next_rmv(or_history->link_history_map,
  528. lhist_it);
  529. rephist_total_alloc -= sizeof(link_history_t);
  530. tor_free(link_history);
  531. continue;
  532. }
  533. lhist_it = digestmap_iter_next(or_history->link_history_map,lhist_it);
  534. }
  535. orhist_it = digestmap_iter_next(history_map, orhist_it);
  536. }
  537. }
  538. /** Write MTBF data to disk. Returns 0 on success, negative on failure. */
  539. int
  540. rep_hist_record_mtbf_data(void)
  541. {
  542. char time_buf[ISO_TIME_LEN+1];
  543. digestmap_iter_t *orhist_it;
  544. const char *digest;
  545. void *or_history_p;
  546. or_history_t *hist;
  547. open_file_t *open_file = NULL;
  548. FILE *f;
  549. {
  550. char *filename = get_datadir_fname("router-stability");
  551. f = start_writing_to_stdio_file(filename, OPEN_FLAGS_REPLACE|O_TEXT, 0600,
  552. &open_file);
  553. tor_free(filename);
  554. if (!f)
  555. return -1;
  556. }
  557. /* File format is:
  558. * FormatLine *KeywordLine Data
  559. *
  560. * FormatLine = "format 1" NL
  561. * KeywordLine = Keyword SP Arguments NL
  562. * Data = "data" NL *RouterMTBFLine "." NL
  563. * RouterMTBFLine = Fingerprint SP WeightedRunLen SP
  564. * TotalRunWeights [SP S=StartRunTime] NL
  565. */
  566. #define PUT(s) STMT_BEGIN if (fputs((s),f)<0) goto err; STMT_END
  567. #define PRINTF(args) STMT_BEGIN if (fprintf args <0) goto err; STMT_END
  568. PUT("format 2\n");
  569. format_iso_time(time_buf, time(NULL));
  570. PRINTF((f, "stored-at %s\n", time_buf));
  571. if (started_tracking_stability) {
  572. format_iso_time(time_buf, started_tracking_stability);
  573. PRINTF((f, "tracked-since %s\n", time_buf));
  574. }
  575. if (stability_last_downrated) {
  576. format_iso_time(time_buf, stability_last_downrated);
  577. PRINTF((f, "last-downrated %s\n", time_buf));
  578. }
  579. PUT("data\n");
  580. for (orhist_it = digestmap_iter_init(history_map);
  581. !digestmap_iter_done(orhist_it);
  582. orhist_it = digestmap_iter_next(history_map,orhist_it)) {
  583. char dbuf[HEX_DIGEST_LEN+1];
  584. const char *t = NULL;
  585. digestmap_iter_get(orhist_it, &digest, &or_history_p);
  586. hist = (or_history_t*) or_history_p;
  587. base16_encode(dbuf, sizeof(dbuf), digest, DIGEST_LEN);
  588. PRINTF((f, "R %s\n", dbuf));
  589. if (hist->start_of_run) {
  590. format_iso_time(time_buf, hist->start_of_run);
  591. t = time_buf;
  592. }
  593. PRINTF((f, "+MTBF %lu %.5lf%s%s\n",
  594. hist->weighted_run_length, hist->total_run_weights,
  595. t ? " S=" : "", t ? t : ""));
  596. t = NULL;
  597. if (hist->start_of_downtime) {
  598. format_iso_time(time_buf, hist->start_of_downtime);
  599. t = time_buf;
  600. }
  601. PRINTF((f, "+WFU %lu %lu%s%s\n",
  602. hist->weighted_uptime, hist->total_weighted_time,
  603. t ? " S=" : "", t ? t : ""));
  604. }
  605. PUT(".\n");
  606. #undef PUT
  607. #undef PRINTF
  608. return finish_writing_to_file(open_file);
  609. err:
  610. abort_writing_to_file(open_file);
  611. return -1;
  612. }
  613. /** Helper: return the first j >= i such that !strcmpstart(sl[j], prefix) and
  614. * such that no line sl[k] with i <= k < j starts with "R ". Return -1 if no
  615. * such line exists. */
  616. static int
  617. find_next_with(smartlist_t *sl, int i, const char *prefix)
  618. {
  619. for ( ; i < smartlist_len(sl); ++i) {
  620. const char *line = smartlist_get(sl, i);
  621. if (!strcmpstart(line, prefix))
  622. return i;
  623. if (!strcmpstart(line, "R "))
  624. return -1;
  625. }
  626. return -1;
  627. }
  628. /** Load MTBF data from disk. Returns 0 on success or recoverable error, -1
  629. * on failure. */
  630. int
  631. rep_hist_load_mtbf_data(time_t now)
  632. {
  633. /* XXXX won't handle being called while history is already populated. */
  634. smartlist_t *lines;
  635. const char *line = NULL;
  636. int r=0, i;
  637. time_t last_downrated = 0, stored_at = 0, tracked_since = 0;
  638. time_t latest_possible_start = now;
  639. long format = -1;
  640. {
  641. char *filename = get_datadir_fname("router-stability");
  642. char *d = read_file_to_str(filename, RFTS_IGNORE_MISSING, NULL);
  643. tor_free(filename);
  644. if (!d)
  645. return -1;
  646. lines = smartlist_create();
  647. smartlist_split_string(lines, d, "\n", SPLIT_SKIP_SPACE, 0);
  648. tor_free(d);
  649. }
  650. {
  651. const char *firstline;
  652. if (smartlist_len(lines)>4) {
  653. firstline = smartlist_get(lines, 0);
  654. if (!strcmpstart(firstline, "format "))
  655. format = tor_parse_long(firstline+strlen("format "),
  656. 10, -1, LONG_MAX, NULL, NULL);
  657. }
  658. }
  659. if (format != 1 && format != 2) {
  660. log_warn(LD_GENERAL,
  661. "Unrecognized format in mtbf history file. Skipping.");
  662. goto err;
  663. }
  664. for (i = 1; i < smartlist_len(lines); ++i) {
  665. line = smartlist_get(lines, i);
  666. if (!strcmp(line, "data"))
  667. break;
  668. if (!strcmpstart(line, "last-downrated ")) {
  669. if (parse_iso_time(line+strlen("last-downrated "), &last_downrated)<0)
  670. log_warn(LD_GENERAL,"Couldn't parse downrate time in mtbf "
  671. "history file.");
  672. }
  673. if (!strcmpstart(line, "stored-at ")) {
  674. if (parse_iso_time(line+strlen("stored-at "), &stored_at)<0)
  675. log_warn(LD_GENERAL,"Couldn't parse stored time in mtbf "
  676. "history file.");
  677. }
  678. if (!strcmpstart(line, "tracked-since ")) {
  679. if (parse_iso_time(line+strlen("tracked-since "), &tracked_since)<0)
  680. log_warn(LD_GENERAL,"Couldn't parse started-tracking time in mtbf "
  681. "history file.");
  682. }
  683. }
  684. if (last_downrated > now)
  685. last_downrated = now;
  686. if (tracked_since > now)
  687. tracked_since = now;
  688. if (!stored_at) {
  689. log_warn(LD_GENERAL, "No stored time recorded.");
  690. goto err;
  691. }
  692. if (line && !strcmp(line, "data"))
  693. ++i;
  694. for (; i < smartlist_len(lines); ++i) {
  695. char digest[DIGEST_LEN];
  696. char hexbuf[HEX_DIGEST_LEN+1];
  697. char mtbf_timebuf[ISO_TIME_LEN+1];
  698. char wfu_timebuf[ISO_TIME_LEN+1];
  699. time_t start_of_run = 0;
  700. time_t start_of_downtime = 0;
  701. int have_mtbf = 0, have_wfu = 0;
  702. long wrl = 0;
  703. double trw = 0;
  704. long wt_uptime = 0, total_wt_time = 0;
  705. int n;
  706. or_history_t *hist;
  707. line = smartlist_get(lines, i);
  708. if (!strcmp(line, "."))
  709. break;
  710. mtbf_timebuf[0] = '\0';
  711. wfu_timebuf[0] = '\0';
  712. if (format == 1) {
  713. /* XXXX020 audit the heck out of my scanf usage. */
  714. n = sscanf(line, "%40s %ld %lf S=%10s %8s",
  715. hexbuf, &wrl, &trw, mtbf_timebuf, mtbf_timebuf+11);
  716. if (n != 3 && n != 5) {
  717. log_warn(LD_GENERAL, "Couldn't scan line %s", escaped(line));
  718. continue;
  719. }
  720. have_mtbf = 1;
  721. } else {
  722. // format == 2.
  723. int mtbf_idx, wfu_idx;
  724. if (strcmpstart(line, "R ") || strlen(line) < 2+HEX_DIGEST_LEN)
  725. continue;
  726. strlcpy(hexbuf, line+2, sizeof(hexbuf));
  727. mtbf_idx = find_next_with(lines, i+1, "+MTBF ");
  728. wfu_idx = find_next_with(lines, i+1, "+WFU ");
  729. if (mtbf_idx >= 0) {
  730. const char *mtbfline = smartlist_get(lines, mtbf_idx);
  731. n = sscanf(mtbfline, "+MTBF %lu %lf S=%10s %8s",
  732. &wrl, &trw, mtbf_timebuf, mtbf_timebuf+11);
  733. if (n == 2 || n == 4) {
  734. have_mtbf = 1;
  735. } else {
  736. log_warn(LD_GENERAL, "Couldn't scan +MTBF line %s",
  737. escaped(mtbfline));
  738. }
  739. }
  740. if (wfu_idx >= 0) {
  741. const char *wfuline = smartlist_get(lines, wfu_idx);
  742. n = sscanf(wfuline, "+WFU %lu %lu S=%10s %8s",
  743. &wt_uptime, &total_wt_time,
  744. wfu_timebuf, wfu_timebuf+11);
  745. if (n == 2 || n == 4) {
  746. have_wfu = 1;
  747. } else {
  748. log_warn(LD_GENERAL, "Couldn't scan +WFU line %s", escaped(wfuline));
  749. }
  750. }
  751. if (wfu_idx > i)
  752. i = wfu_idx;
  753. if (mtbf_idx > i)
  754. i = mtbf_idx;
  755. }
  756. if (base16_decode(digest, DIGEST_LEN, hexbuf, HEX_DIGEST_LEN) < 0) {
  757. log_warn(LD_GENERAL, "Couldn't hex string %s", escaped(hexbuf));
  758. continue;
  759. }
  760. hist = get_or_history(digest);
  761. if (!hist)
  762. continue;
  763. if (have_mtbf) {
  764. if (mtbf_timebuf[0]) {
  765. mtbf_timebuf[10] = ' ';
  766. if (parse_iso_time(mtbf_timebuf, &start_of_run)<0)
  767. log_warn(LD_GENERAL, "Couldn't parse time %s",
  768. escaped(mtbf_timebuf));
  769. }
  770. if (!start_of_run || start_of_run > stored_at) {
  771. hist->start_of_run = 0;
  772. } else {
  773. long run_length = stored_at - start_of_run;
  774. hist->start_of_run = now - run_length;
  775. }
  776. if (hist->start_of_run < latest_possible_start + wrl)
  777. latest_possible_start = hist->start_of_run - wrl;
  778. hist->weighted_run_length = wrl;
  779. hist->total_run_weights = trw;
  780. }
  781. if (have_wfu) {
  782. if (wfu_timebuf[0]) {
  783. wfu_timebuf[10] = ' ';
  784. if (parse_iso_time(wfu_timebuf, &start_of_downtime)<0)
  785. log_warn(LD_GENERAL, "Couldn't parse time %s", escaped(wfu_timebuf));
  786. }
  787. }
  788. if (!start_of_downtime || start_of_downtime > stored_at) {
  789. hist->start_of_downtime = 0;
  790. } else {
  791. long down_length = stored_at - start_of_downtime;
  792. hist->start_of_downtime = start_of_downtime - down_length;
  793. }
  794. hist->weighted_uptime = wt_uptime;
  795. hist->total_weighted_time = total_wt_time;
  796. }
  797. if (strcmp(line, "."))
  798. log_warn(LD_GENERAL, "Truncated MTBF file.");
  799. if (!tracked_since)
  800. tracked_since = latest_possible_start;
  801. stability_last_downrated = last_downrated;
  802. started_tracking_stability = tracked_since;
  803. goto done;
  804. err:
  805. r = -1;
  806. done:
  807. SMARTLIST_FOREACH(lines, char *, cp, tor_free(cp));
  808. smartlist_free(lines);
  809. return r;
  810. }
  811. /** For how many seconds do we keep track of individual per-second bandwidth
  812. * totals? */
  813. #define NUM_SECS_ROLLING_MEASURE 10
  814. /** How large are the intervals for which we track and report bandwidth use? */
  815. #define NUM_SECS_BW_SUM_INTERVAL (15*60)
  816. /** How far in the past do we remember and publish bandwidth use? */
  817. #define NUM_SECS_BW_SUM_IS_VALID (24*60*60)
  818. /** How many bandwidth usage intervals do we remember? (derived) */
  819. #define NUM_TOTALS (NUM_SECS_BW_SUM_IS_VALID/NUM_SECS_BW_SUM_INTERVAL)
  820. /** Structure to track bandwidth use, and remember the maxima for a given
  821. * time period.
  822. */
  823. typedef struct bw_array_t {
  824. /** Observation array: Total number of bytes transferred in each of the last
  825. * NUM_SECS_ROLLING_MEASURE seconds. This is used as a circular array. */
  826. uint64_t obs[NUM_SECS_ROLLING_MEASURE];
  827. int cur_obs_idx; /**< Current position in obs. */
  828. time_t cur_obs_time; /**< Time represented in obs[cur_obs_idx] */
  829. uint64_t total_obs; /**< Total for all members of obs except
  830. * obs[cur_obs_idx] */
  831. uint64_t max_total; /**< Largest value that total_obs has taken on in the
  832. * current period. */
  833. uint64_t total_in_period; /**< Total bytes transferred in the current
  834. * period. */
  835. /** When does the next period begin? */
  836. time_t next_period;
  837. /** Where in 'maxima' should the maximum bandwidth usage for the current
  838. * period be stored? */
  839. int next_max_idx;
  840. /** How many values in maxima/totals have been set ever? */
  841. int num_maxes_set;
  842. /** Circular array of the maximum
  843. * bandwidth-per-NUM_SECS_ROLLING_MEASURE usage for the last
  844. * NUM_TOTALS periods */
  845. uint64_t maxima[NUM_TOTALS];
  846. /** Circular array of the total bandwidth usage for the last NUM_TOTALS
  847. * periods */
  848. uint64_t totals[NUM_TOTALS];
  849. } bw_array_t;
  850. /** Shift the current period of b forward by one. */
  851. static void
  852. commit_max(bw_array_t *b)
  853. {
  854. /* Store total from current period. */
  855. b->totals[b->next_max_idx] = b->total_in_period;
  856. /* Store maximum from current period. */
  857. b->maxima[b->next_max_idx++] = b->max_total;
  858. /* Advance next_period and next_max_idx */
  859. b->next_period += NUM_SECS_BW_SUM_INTERVAL;
  860. if (b->next_max_idx == NUM_TOTALS)
  861. b->next_max_idx = 0;
  862. if (b->num_maxes_set < NUM_TOTALS)
  863. ++b->num_maxes_set;
  864. /* Reset max_total. */
  865. b->max_total = 0;
  866. /* Reset total_in_period. */
  867. b->total_in_period = 0;
  868. }
  869. /** Shift the current observation time of 'b' forward by one second. */
  870. static INLINE void
  871. advance_obs(bw_array_t *b)
  872. {
  873. int nextidx;
  874. uint64_t total;
  875. /* Calculate the total bandwidth for the last NUM_SECS_ROLLING_MEASURE
  876. * seconds; adjust max_total as needed.*/
  877. total = b->total_obs + b->obs[b->cur_obs_idx];
  878. if (total > b->max_total)
  879. b->max_total = total;
  880. nextidx = b->cur_obs_idx+1;
  881. if (nextidx == NUM_SECS_ROLLING_MEASURE)
  882. nextidx = 0;
  883. b->total_obs = total - b->obs[nextidx];
  884. b->obs[nextidx]=0;
  885. b->cur_obs_idx = nextidx;
  886. if (++b->cur_obs_time >= b->next_period)
  887. commit_max(b);
  888. }
  889. /** Add 'n' bytes to the number of bytes in b for second 'when'. */
  890. static INLINE void
  891. add_obs(bw_array_t *b, time_t when, uint64_t n)
  892. {
  893. /* Don't record data in the past. */
  894. if (when<b->cur_obs_time)
  895. return;
  896. /* If we're currently adding observations for an earlier second than
  897. * 'when', advance b->cur_obs_time and b->cur_obs_idx by an
  898. * appropriate number of seconds, and do all the other housekeeping */
  899. while (when>b->cur_obs_time)
  900. advance_obs(b);
  901. b->obs[b->cur_obs_idx] += n;
  902. b->total_in_period += n;
  903. }
  904. /** Allocate, initialize, and return a new bw_array. */
  905. static bw_array_t *
  906. bw_array_new(void)
  907. {
  908. bw_array_t *b;
  909. time_t start;
  910. b = tor_malloc_zero(sizeof(bw_array_t));
  911. rephist_total_alloc += sizeof(bw_array_t);
  912. start = time(NULL);
  913. b->cur_obs_time = start;
  914. b->next_period = start + NUM_SECS_BW_SUM_INTERVAL;
  915. return b;
  916. }
  917. static bw_array_t *read_array = NULL;
  918. static bw_array_t *write_array = NULL;
  919. /** Set up read_array and write_array. */
  920. static void
  921. bw_arrays_init(void)
  922. {
  923. read_array = bw_array_new();
  924. write_array = bw_array_new();
  925. }
  926. /** We read <b>num_bytes</b> more bytes in second <b>when</b>.
  927. *
  928. * Add num_bytes to the current running total for <b>when</b>.
  929. *
  930. * <b>when</b> can go back to time, but it's safe to ignore calls
  931. * earlier than the latest <b>when</b> you've heard of.
  932. */
  933. void
  934. rep_hist_note_bytes_written(int num_bytes, time_t when)
  935. {
  936. /* Maybe a circular array for recent seconds, and step to a new point
  937. * every time a new second shows up. Or simpler is to just to have
  938. * a normal array and push down each item every second; it's short.
  939. */
  940. /* When a new second has rolled over, compute the sum of the bytes we've
  941. * seen over when-1 to when-1-NUM_SECS_ROLLING_MEASURE, and stick it
  942. * somewhere. See rep_hist_bandwidth_assess() below.
  943. */
  944. add_obs(write_array, when, num_bytes);
  945. }
  946. /** We wrote <b>num_bytes</b> more bytes in second <b>when</b>.
  947. * (like rep_hist_note_bytes_written() above)
  948. */
  949. void
  950. rep_hist_note_bytes_read(int num_bytes, time_t when)
  951. {
  952. /* if we're smart, we can make this func and the one above share code */
  953. add_obs(read_array, when, num_bytes);
  954. }
  955. /** Helper: Return the largest value in b->maxima. (This is equal to the
  956. * most bandwidth used in any NUM_SECS_ROLLING_MEASURE period for the last
  957. * NUM_SECS_BW_SUM_IS_VALID seconds.)
  958. */
  959. static uint64_t
  960. find_largest_max(bw_array_t *b)
  961. {
  962. int i;
  963. uint64_t max;
  964. max=0;
  965. for (i=0; i<NUM_TOTALS; ++i) {
  966. if (b->maxima[i]>max)
  967. max = b->maxima[i];
  968. }
  969. return max;
  970. }
  971. /** Find the largest sums in the past NUM_SECS_BW_SUM_IS_VALID (roughly)
  972. * seconds. Find one sum for reading and one for writing. They don't have
  973. * to be at the same time).
  974. *
  975. * Return the smaller of these sums, divided by NUM_SECS_ROLLING_MEASURE.
  976. */
  977. int
  978. rep_hist_bandwidth_assess(void)
  979. {
  980. uint64_t w,r;
  981. r = find_largest_max(read_array);
  982. w = find_largest_max(write_array);
  983. if (r>w)
  984. return (int)(U64_TO_DBL(w)/NUM_SECS_ROLLING_MEASURE);
  985. else
  986. return (int)(U64_TO_DBL(r)/NUM_SECS_ROLLING_MEASURE);
  987. }
  988. /** Print the bandwidth history of b (either read_array or write_array)
  989. * into the buffer pointed to by buf. The format is simply comma
  990. * separated numbers, from oldest to newest.
  991. *
  992. * It returns the number of bytes written.
  993. */
  994. static size_t
  995. rep_hist_fill_bandwidth_history(char *buf, size_t len, bw_array_t *b)
  996. {
  997. char *cp = buf;
  998. int i, n;
  999. or_options_t *options = get_options();
  1000. uint64_t cutoff;
  1001. if (b->num_maxes_set <= b->next_max_idx) {
  1002. /* We haven't been through the circular array yet; time starts at i=0.*/
  1003. i = 0;
  1004. } else {
  1005. /* We've been around the array at least once. The next i to be
  1006. overwritten is the oldest. */
  1007. i = b->next_max_idx;
  1008. }
  1009. if (options->RelayBandwidthRate) {
  1010. /* We don't want to report that we used more bandwidth than the max we're
  1011. * willing to relay; otherwise everybody will know how much traffic
  1012. * we used ourself. */
  1013. cutoff = options->RelayBandwidthRate * NUM_SECS_BW_SUM_INTERVAL;
  1014. } else {
  1015. cutoff = UINT64_MAX;
  1016. }
  1017. for (n=0; n<b->num_maxes_set; ++n,++i) {
  1018. uint64_t total;
  1019. if (i >= NUM_TOTALS)
  1020. i -= NUM_TOTALS;
  1021. tor_assert(i < NUM_TOTALS);
  1022. /* Round the bandwidth used down to the nearest 1k. */
  1023. total = b->totals[i] & ~0x3ff;
  1024. if (total > cutoff)
  1025. total = cutoff;
  1026. if (n==(b->num_maxes_set-1))
  1027. tor_snprintf(cp, len-(cp-buf), U64_FORMAT, U64_PRINTF_ARG(total));
  1028. else
  1029. tor_snprintf(cp, len-(cp-buf), U64_FORMAT",", U64_PRINTF_ARG(total));
  1030. cp += strlen(cp);
  1031. }
  1032. return cp-buf;
  1033. }
  1034. /** Allocate and return lines for representing this server's bandwidth
  1035. * history in its descriptor.
  1036. */
  1037. char *
  1038. rep_hist_get_bandwidth_lines(int for_extrainfo)
  1039. {
  1040. char *buf, *cp;
  1041. char t[ISO_TIME_LEN+1];
  1042. int r;
  1043. bw_array_t *b;
  1044. size_t len;
  1045. /* opt (read|write)-history yyyy-mm-dd HH:MM:SS (n s) n,n,n,n,n... */
  1046. len = (60+20*NUM_TOTALS)*2;
  1047. buf = tor_malloc_zero(len);
  1048. cp = buf;
  1049. for (r=0;r<2;++r) {
  1050. b = r?read_array:write_array;
  1051. tor_assert(b);
  1052. format_iso_time(t, b->next_period-NUM_SECS_BW_SUM_INTERVAL);
  1053. tor_snprintf(cp, len-(cp-buf), "%s%s %s (%d s) ",
  1054. for_extrainfo ? "" : "opt ",
  1055. r ? "read-history" : "write-history", t,
  1056. NUM_SECS_BW_SUM_INTERVAL);
  1057. cp += strlen(cp);
  1058. cp += rep_hist_fill_bandwidth_history(cp, len-(cp-buf), b);
  1059. strlcat(cp, "\n", len-(cp-buf));
  1060. ++cp;
  1061. }
  1062. return buf;
  1063. }
  1064. /** Update <b>state</b> with the newest bandwidth history. */
  1065. void
  1066. rep_hist_update_state(or_state_t *state)
  1067. {
  1068. int len, r;
  1069. char *buf, *cp;
  1070. smartlist_t **s_values;
  1071. time_t *s_begins;
  1072. int *s_interval;
  1073. bw_array_t *b;
  1074. len = 20*NUM_TOTALS+1;
  1075. buf = tor_malloc_zero(len);
  1076. for (r=0;r<2;++r) {
  1077. b = r?read_array:write_array;
  1078. s_begins = r?&state->BWHistoryReadEnds :&state->BWHistoryWriteEnds;
  1079. s_interval= r?&state->BWHistoryReadInterval:&state->BWHistoryWriteInterval;
  1080. s_values = r?&state->BWHistoryReadValues :&state->BWHistoryWriteValues;
  1081. if (*s_values) {
  1082. SMARTLIST_FOREACH(*s_values, char *, val, tor_free(val));
  1083. smartlist_free(*s_values);
  1084. }
  1085. if (! server_mode(get_options())) {
  1086. /* Clients don't need to store bandwidth history persistently;
  1087. * force these values to the defaults. */
  1088. /* FFFF we should pull the default out of config.c's state table,
  1089. * so we don't have two defaults. */
  1090. if (*s_begins != 0 || *s_interval != 900) {
  1091. time_t now = time(NULL);
  1092. time_t save_at = get_options()->AvoidDiskWrites ? now+3600 : now+600;
  1093. or_state_mark_dirty(state, save_at);
  1094. }
  1095. *s_begins = 0;
  1096. *s_interval = 900;
  1097. *s_values = smartlist_create();
  1098. continue;
  1099. }
  1100. *s_begins = b->next_period;
  1101. *s_interval = NUM_SECS_BW_SUM_INTERVAL;
  1102. cp = buf;
  1103. cp += rep_hist_fill_bandwidth_history(cp, len, b);
  1104. tor_snprintf(cp, len-(cp-buf), cp == buf ? U64_FORMAT : ","U64_FORMAT,
  1105. U64_PRINTF_ARG(b->total_in_period));
  1106. *s_values = smartlist_create();
  1107. if (server_mode(get_options()))
  1108. smartlist_split_string(*s_values, buf, ",", SPLIT_SKIP_SPACE, 0);
  1109. }
  1110. tor_free(buf);
  1111. if (server_mode(get_options())) {
  1112. or_state_mark_dirty(get_or_state(), time(NULL)+(2*3600));
  1113. }
  1114. }
  1115. /** Set bandwidth history from our saved state. */
  1116. int
  1117. rep_hist_load_state(or_state_t *state, char **err)
  1118. {
  1119. time_t s_begins, start;
  1120. time_t now = time(NULL);
  1121. uint64_t v;
  1122. int r,i,ok;
  1123. int all_ok = 1;
  1124. int s_interval;
  1125. smartlist_t *s_values;
  1126. bw_array_t *b;
  1127. /* Assert they already have been malloced */
  1128. tor_assert(read_array && write_array);
  1129. for (r=0;r<2;++r) {
  1130. b = r?read_array:write_array;
  1131. s_begins = r?state->BWHistoryReadEnds:state->BWHistoryWriteEnds;
  1132. s_interval = r?state->BWHistoryReadInterval:state->BWHistoryWriteInterval;
  1133. s_values = r?state->BWHistoryReadValues:state->BWHistoryWriteValues;
  1134. if (s_values && s_begins >= now - NUM_SECS_BW_SUM_INTERVAL*NUM_TOTALS) {
  1135. start = s_begins - s_interval*(smartlist_len(s_values));
  1136. if (start > now)
  1137. continue;
  1138. b->cur_obs_time = start;
  1139. b->next_period = start + NUM_SECS_BW_SUM_INTERVAL;
  1140. SMARTLIST_FOREACH(s_values, char *, cp, {
  1141. v = tor_parse_uint64(cp, 10, 0, UINT64_MAX, &ok, NULL);
  1142. if (!ok) {
  1143. all_ok=0;
  1144. log_notice(LD_GENERAL, "Could not parse '%s' into a number.'", cp);
  1145. }
  1146. if (start < now) {
  1147. add_obs(b, start, v);
  1148. start += NUM_SECS_BW_SUM_INTERVAL;
  1149. }
  1150. });
  1151. }
  1152. /* Clean up maxima and observed */
  1153. /* Do we really want to zero this for the purpose of max capacity? */
  1154. for (i=0; i<NUM_SECS_ROLLING_MEASURE; ++i) {
  1155. b->obs[i] = 0;
  1156. }
  1157. b->total_obs = 0;
  1158. for (i=0; i<NUM_TOTALS; ++i) {
  1159. b->maxima[i] = 0;
  1160. }
  1161. b->max_total = 0;
  1162. }
  1163. if (!all_ok) {
  1164. *err = tor_strdup("Parsing of bandwidth history values failed");
  1165. /* and create fresh arrays */
  1166. tor_free(read_array);
  1167. tor_free(write_array);
  1168. read_array = bw_array_new();
  1169. write_array = bw_array_new();
  1170. return -1;
  1171. }
  1172. return 0;
  1173. }
  1174. /*********************************************************************/
  1175. /** A list of port numbers that have been used recently. */
  1176. static smartlist_t *predicted_ports_list=NULL;
  1177. /** The corresponding most recently used time for each port. */
  1178. static smartlist_t *predicted_ports_times=NULL;
  1179. /** We just got an application request for a connection with
  1180. * port <b>port</b>. Remember it for the future, so we can keep
  1181. * some circuits open that will exit to this port.
  1182. */
  1183. static void
  1184. add_predicted_port(uint16_t port, time_t now)
  1185. {
  1186. /* XXXX we could just use uintptr_t here, I think. */
  1187. uint16_t *tmp_port = tor_malloc(sizeof(uint16_t));
  1188. time_t *tmp_time = tor_malloc(sizeof(time_t));
  1189. *tmp_port = port;
  1190. *tmp_time = now;
  1191. rephist_total_alloc += sizeof(uint16_t) + sizeof(time_t);
  1192. smartlist_add(predicted_ports_list, tmp_port);
  1193. smartlist_add(predicted_ports_times, tmp_time);
  1194. }
  1195. /** Initialize whatever memory and structs are needed for predicting
  1196. * which ports will be used. Also seed it with port 80, so we'll build
  1197. * circuits on start-up.
  1198. */
  1199. static void
  1200. predicted_ports_init(void)
  1201. {
  1202. predicted_ports_list = smartlist_create();
  1203. predicted_ports_times = smartlist_create();
  1204. add_predicted_port(80, time(NULL)); /* add one to kickstart us */
  1205. }
  1206. /** Free whatever memory is needed for predicting which ports will
  1207. * be used.
  1208. */
  1209. static void
  1210. predicted_ports_free(void)
  1211. {
  1212. rephist_total_alloc -= smartlist_len(predicted_ports_list)*sizeof(uint16_t);
  1213. SMARTLIST_FOREACH(predicted_ports_list, char *, cp, tor_free(cp));
  1214. smartlist_free(predicted_ports_list);
  1215. rephist_total_alloc -= smartlist_len(predicted_ports_times)*sizeof(time_t);
  1216. SMARTLIST_FOREACH(predicted_ports_times, char *, cp, tor_free(cp));
  1217. smartlist_free(predicted_ports_times);
  1218. }
  1219. /** Remember that <b>port</b> has been asked for as of time <b>now</b>.
  1220. * This is used for predicting what sorts of streams we'll make in the
  1221. * future and making exit circuits to anticipate that.
  1222. */
  1223. void
  1224. rep_hist_note_used_port(uint16_t port, time_t now)
  1225. {
  1226. int i;
  1227. uint16_t *tmp_port;
  1228. time_t *tmp_time;
  1229. tor_assert(predicted_ports_list);
  1230. tor_assert(predicted_ports_times);
  1231. if (!port) /* record nothing */
  1232. return;
  1233. for (i = 0; i < smartlist_len(predicted_ports_list); ++i) {
  1234. tmp_port = smartlist_get(predicted_ports_list, i);
  1235. tmp_time = smartlist_get(predicted_ports_times, i);
  1236. if (*tmp_port == port) {
  1237. *tmp_time = now;
  1238. return;
  1239. }
  1240. }
  1241. /* it's not there yet; we need to add it */
  1242. add_predicted_port(port, now);
  1243. }
  1244. /** For this long after we've seen a request for a given port, assume that
  1245. * we'll want to make connections to the same port in the future. */
  1246. #define PREDICTED_CIRCS_RELEVANCE_TIME (60*60)
  1247. /** Return a pointer to the list of port numbers that
  1248. * are likely to be asked for in the near future.
  1249. *
  1250. * The caller promises not to mess with it.
  1251. */
  1252. smartlist_t *
  1253. rep_hist_get_predicted_ports(time_t now)
  1254. {
  1255. int i;
  1256. uint16_t *tmp_port;
  1257. time_t *tmp_time;
  1258. tor_assert(predicted_ports_list);
  1259. tor_assert(predicted_ports_times);
  1260. /* clean out obsolete entries */
  1261. for (i = 0; i < smartlist_len(predicted_ports_list); ++i) {
  1262. tmp_time = smartlist_get(predicted_ports_times, i);
  1263. if (*tmp_time + PREDICTED_CIRCS_RELEVANCE_TIME < now) {
  1264. tmp_port = smartlist_get(predicted_ports_list, i);
  1265. log_debug(LD_CIRC, "Expiring predicted port %d", *tmp_port);
  1266. smartlist_del(predicted_ports_list, i);
  1267. smartlist_del(predicted_ports_times, i);
  1268. rephist_total_alloc -= sizeof(uint16_t)+sizeof(time_t);
  1269. tor_free(tmp_port);
  1270. tor_free(tmp_time);
  1271. i--;
  1272. }
  1273. }
  1274. return predicted_ports_list;
  1275. }
  1276. /** The user asked us to do a resolve. Rather than keeping track of
  1277. * timings and such of resolves, we fake it for now by making treating
  1278. * it the same way as a connection to port 80. This way we will continue
  1279. * to have circuits lying around if the user only uses Tor for resolves.
  1280. */
  1281. void
  1282. rep_hist_note_used_resolve(time_t now)
  1283. {
  1284. rep_hist_note_used_port(80, now);
  1285. }
  1286. /** The last time at which we needed an internal circ. */
  1287. static time_t predicted_internal_time = 0;
  1288. /** The last time we needed an internal circ with good uptime. */
  1289. static time_t predicted_internal_uptime_time = 0;
  1290. /** The last time we needed an internal circ with good capacity. */
  1291. static time_t predicted_internal_capacity_time = 0;
  1292. /** Remember that we used an internal circ at time <b>now</b>. */
  1293. void
  1294. rep_hist_note_used_internal(time_t now, int need_uptime, int need_capacity)
  1295. {
  1296. predicted_internal_time = now;
  1297. if (need_uptime)
  1298. predicted_internal_uptime_time = now;
  1299. if (need_capacity)
  1300. predicted_internal_capacity_time = now;
  1301. }
  1302. /** Return 1 if we've used an internal circ recently; else return 0. */
  1303. int
  1304. rep_hist_get_predicted_internal(time_t now, int *need_uptime,
  1305. int *need_capacity)
  1306. {
  1307. if (!predicted_internal_time) { /* initialize it */
  1308. predicted_internal_time = now;
  1309. predicted_internal_uptime_time = now;
  1310. predicted_internal_capacity_time = now;
  1311. }
  1312. if (predicted_internal_time + PREDICTED_CIRCS_RELEVANCE_TIME < now)
  1313. return 0; /* too long ago */
  1314. if (predicted_internal_uptime_time + PREDICTED_CIRCS_RELEVANCE_TIME >= now)
  1315. *need_uptime = 1;
  1316. if (predicted_internal_capacity_time + PREDICTED_CIRCS_RELEVANCE_TIME >= now)
  1317. *need_capacity = 1;
  1318. return 1;
  1319. }
  1320. /** Any ports used lately? These are pre-seeded if we just started
  1321. * up or if we're running a hidden service. */
  1322. int
  1323. any_predicted_circuits(time_t now)
  1324. {
  1325. return smartlist_len(predicted_ports_list) ||
  1326. predicted_internal_time + PREDICTED_CIRCS_RELEVANCE_TIME >= now;
  1327. }
  1328. /** Return 1 if we have no need for circuits currently, else return 0. */
  1329. int
  1330. rep_hist_circbuilding_dormant(time_t now)
  1331. {
  1332. if (any_predicted_circuits(now))
  1333. return 0;
  1334. /* see if we'll still need to build testing circuits */
  1335. if (server_mode(get_options()) && !check_whether_orport_reachable())
  1336. return 0;
  1337. if (!check_whether_dirport_reachable())
  1338. return 0;
  1339. return 1;
  1340. }
  1341. static uint32_t n_signed_dir_objs = 0;
  1342. static uint32_t n_signed_routerdescs = 0;
  1343. static uint32_t n_verified_dir_objs = 0;
  1344. static uint32_t n_verified_routerdescs = 0;
  1345. static uint32_t n_onionskins_encrypted = 0;
  1346. static uint32_t n_onionskins_decrypted = 0;
  1347. static uint32_t n_tls_client_handshakes = 0;
  1348. static uint32_t n_tls_server_handshakes = 0;
  1349. static uint32_t n_rend_client_ops = 0;
  1350. static uint32_t n_rend_mid_ops = 0;
  1351. static uint32_t n_rend_server_ops = 0;
  1352. /** Increment the count of the number of times we've done <b>operation</b>. */
  1353. void
  1354. note_crypto_pk_op(pk_op_t operation)
  1355. {
  1356. switch (operation)
  1357. {
  1358. case SIGN_DIR:
  1359. n_signed_dir_objs++;
  1360. break;
  1361. case SIGN_RTR:
  1362. n_signed_routerdescs++;
  1363. break;
  1364. case VERIFY_DIR:
  1365. n_verified_dir_objs++;
  1366. break;
  1367. case VERIFY_RTR:
  1368. n_verified_routerdescs++;
  1369. break;
  1370. case ENC_ONIONSKIN:
  1371. n_onionskins_encrypted++;
  1372. break;
  1373. case DEC_ONIONSKIN:
  1374. n_onionskins_decrypted++;
  1375. break;
  1376. case TLS_HANDSHAKE_C:
  1377. n_tls_client_handshakes++;
  1378. break;
  1379. case TLS_HANDSHAKE_S:
  1380. n_tls_server_handshakes++;
  1381. break;
  1382. case REND_CLIENT:
  1383. n_rend_client_ops++;
  1384. break;
  1385. case REND_MID:
  1386. n_rend_mid_ops++;
  1387. break;
  1388. case REND_SERVER:
  1389. n_rend_server_ops++;
  1390. break;
  1391. default:
  1392. log_warn(LD_BUG, "Unknown pk operation %d", operation);
  1393. }
  1394. }
  1395. /** Log the number of times we've done each public/private-key operation. */
  1396. void
  1397. dump_pk_ops(int severity)
  1398. {
  1399. log(severity, LD_GENERAL,
  1400. "PK operations: %lu directory objects signed, "
  1401. "%lu directory objects verified, "
  1402. "%lu routerdescs signed, "
  1403. "%lu routerdescs verified, "
  1404. "%lu onionskins encrypted, "
  1405. "%lu onionskins decrypted, "
  1406. "%lu client-side TLS handshakes, "
  1407. "%lu server-side TLS handshakes, "
  1408. "%lu rendezvous client operations, "
  1409. "%lu rendezvous middle operations, "
  1410. "%lu rendezvous server operations.",
  1411. (unsigned long) n_signed_dir_objs,
  1412. (unsigned long) n_verified_dir_objs,
  1413. (unsigned long) n_signed_routerdescs,
  1414. (unsigned long) n_verified_routerdescs,
  1415. (unsigned long) n_onionskins_encrypted,
  1416. (unsigned long) n_onionskins_decrypted,
  1417. (unsigned long) n_tls_client_handshakes,
  1418. (unsigned long) n_tls_server_handshakes,
  1419. (unsigned long) n_rend_client_ops,
  1420. (unsigned long) n_rend_mid_ops,
  1421. (unsigned long) n_rend_server_ops);
  1422. }
  1423. /** Free all storage held by the OR/link history caches, by the
  1424. * bandwidth history arrays, or by the port history. */
  1425. void
  1426. rep_hist_free_all(void)
  1427. {
  1428. digestmap_free(history_map, free_or_history);
  1429. tor_free(read_array);
  1430. tor_free(write_array);
  1431. predicted_ports_free();
  1432. }
  1433. /****************** hidden service usage statistics ******************/
  1434. /** How large are the intervals for which we track and report hidden service
  1435. * use? */
  1436. #define NUM_SECS_HS_USAGE_SUM_INTERVAL (15*60)
  1437. /** How far in the past do we remember and publish hidden service use? */
  1438. #define NUM_SECS_HS_USAGE_SUM_IS_VALID (24*60*60)
  1439. /** How many hidden service usage intervals do we remember? (derived) */
  1440. #define NUM_TOTALS_HS_USAGE (NUM_SECS_HS_USAGE_SUM_IS_VALID/ \
  1441. NUM_SECS_HS_USAGE_SUM_INTERVAL)
  1442. /** List element containing a service id and the count. */
  1443. typedef struct hs_usage_list_elem_t {
  1444. /** Service id of this elem. */
  1445. char service_id[REND_SERVICE_ID_LEN+1];
  1446. /** Number of occurrences for the given service id. */
  1447. uint32_t count;
  1448. /* Pointer to next list elem */
  1449. struct hs_usage_list_elem_t *next;
  1450. } hs_usage_list_elem_t;
  1451. /* Ordered list that stores service ids and the number of observations. It is
  1452. * ordered by the number of occurrences in descending order. Its purpose is to
  1453. * calculate the frequency distribution when the period is over. */
  1454. typedef struct hs_usage_list_t {
  1455. /* Pointer to the first element in the list. */
  1456. hs_usage_list_elem_t *start;
  1457. /* Number of total occurrences for all list elements. */
  1458. uint32_t total_count;
  1459. /* Number of service ids, i.e. number of list elements. */
  1460. uint32_t total_service_ids;
  1461. } hs_usage_list_t;
  1462. /** Tracks service-related observations in the current period and their
  1463. * history. */
  1464. typedef struct hs_usage_service_related_observation_t {
  1465. /** Ordered list that stores service ids and the number of observations in
  1466. * the current period. It is ordered by the number of occurrences in
  1467. * descending order. Its purpose is to calculate the frequency distribution
  1468. * when the period is over. */
  1469. hs_usage_list_t *list;
  1470. /** Circular arrays that store the history of observations. totals stores all
  1471. * observations, twenty (ten, five) the number of observations related to a
  1472. * service id being accounted for the top 20 (10, 5) percent of all
  1473. * observations. */
  1474. uint32_t totals[NUM_TOTALS_HS_USAGE];
  1475. uint32_t five[NUM_TOTALS_HS_USAGE];
  1476. uint32_t ten[NUM_TOTALS_HS_USAGE];
  1477. uint32_t twenty[NUM_TOTALS_HS_USAGE];
  1478. } hs_usage_service_related_observation_t;
  1479. /** Tracks the history of general period-related observations, i.e. those that
  1480. * cannot be related to a specific service id. */
  1481. typedef struct hs_usage_general_period_related_observations_t {
  1482. /** Circular array that stores the history of observations. */
  1483. uint32_t totals[NUM_TOTALS_HS_USAGE];
  1484. } hs_usage_general_period_related_observations_t;
  1485. /** Keeps information about the current observation period and its relation to
  1486. * the histories of observations. */
  1487. typedef struct hs_usage_current_observation_period_t {
  1488. /** Where do we write the next history entry? */
  1489. int next_idx;
  1490. /** How many values in history have been set ever? (upper bound!) */
  1491. int num_set;
  1492. /** When did this period begin? */
  1493. time_t start_of_current_period;
  1494. /** When does the next period begin? */
  1495. time_t start_of_next_period;
  1496. } hs_usage_current_observation_period_t;
  1497. static hs_usage_current_observation_period_t *current_period = NULL;
  1498. static hs_usage_service_related_observation_t *publish_total = NULL;
  1499. static hs_usage_service_related_observation_t *publish_novel = NULL;
  1500. static hs_usage_service_related_observation_t *fetch_total = NULL;
  1501. static hs_usage_service_related_observation_t *fetch_successful = NULL;
  1502. static hs_usage_general_period_related_observations_t *descs = NULL;
  1503. /** Creates an empty ordered list element. */
  1504. static hs_usage_list_elem_t *
  1505. hs_usage_list_elem_new(void)
  1506. {
  1507. hs_usage_list_elem_t *e;
  1508. e = tor_malloc_zero(sizeof(hs_usage_list_elem_t));
  1509. rephist_total_alloc += sizeof(hs_usage_list_elem_t);
  1510. e->count = 1;
  1511. e->next = NULL;
  1512. return e;
  1513. }
  1514. /** Creates an empty ordered list. */
  1515. static hs_usage_list_t *
  1516. hs_usage_list_new(void)
  1517. {
  1518. hs_usage_list_t *l;
  1519. l = tor_malloc_zero(sizeof(hs_usage_list_t));
  1520. rephist_total_alloc += sizeof(hs_usage_list_t);
  1521. l->start = NULL;
  1522. l->total_count = 0;
  1523. l->total_service_ids = 0;
  1524. return l;
  1525. }
  1526. /** Creates an empty structure for storing service-related observations. */
  1527. static hs_usage_service_related_observation_t *
  1528. hs_usage_service_related_observation_new(void)
  1529. {
  1530. hs_usage_service_related_observation_t *h;
  1531. h = tor_malloc_zero(sizeof(hs_usage_service_related_observation_t));
  1532. rephist_total_alloc += sizeof(hs_usage_service_related_observation_t);
  1533. h->list = hs_usage_list_new();
  1534. return h;
  1535. }
  1536. /** Creates an empty structure for storing general period-related
  1537. * observations. */
  1538. static hs_usage_general_period_related_observations_t *
  1539. hs_usage_general_period_related_observations_new(void)
  1540. {
  1541. hs_usage_general_period_related_observations_t *p;
  1542. p = tor_malloc_zero(sizeof(hs_usage_general_period_related_observations_t));
  1543. rephist_total_alloc+= sizeof(hs_usage_general_period_related_observations_t);
  1544. return p;
  1545. }
  1546. /** Creates an empty structure for storing period-specific information. */
  1547. static hs_usage_current_observation_period_t *
  1548. hs_usage_current_observation_period_new(void)
  1549. {
  1550. hs_usage_current_observation_period_t *c;
  1551. time_t now;
  1552. c = tor_malloc_zero(sizeof(hs_usage_current_observation_period_t));
  1553. rephist_total_alloc += sizeof(hs_usage_current_observation_period_t);
  1554. now = time(NULL);
  1555. c->start_of_current_period = now;
  1556. c->start_of_next_period = now + NUM_SECS_HS_USAGE_SUM_INTERVAL;
  1557. return c;
  1558. }
  1559. /** Initializes the structures for collecting hidden service usage data. */
  1560. static void
  1561. hs_usage_init(void)
  1562. {
  1563. current_period = hs_usage_current_observation_period_new();
  1564. publish_total = hs_usage_service_related_observation_new();
  1565. publish_novel = hs_usage_service_related_observation_new();
  1566. fetch_total = hs_usage_service_related_observation_new();
  1567. fetch_successful = hs_usage_service_related_observation_new();
  1568. descs = hs_usage_general_period_related_observations_new();
  1569. }
  1570. /** Clears the given ordered list by resetting its attributes and releasing
  1571. * the memory allocated by its elements. */
  1572. static void
  1573. hs_usage_list_clear(hs_usage_list_t *lst)
  1574. {
  1575. /* walk through elements and free memory */
  1576. hs_usage_list_elem_t *current = lst->start;
  1577. hs_usage_list_elem_t *tmp;
  1578. while (current != NULL) {
  1579. tmp = current->next;
  1580. rephist_total_alloc -= sizeof(hs_usage_list_elem_t);
  1581. tor_free(current);
  1582. current = tmp;
  1583. }
  1584. /* reset attributes */
  1585. lst->start = NULL;
  1586. lst->total_count = 0;
  1587. lst->total_service_ids = 0;
  1588. return;
  1589. }
  1590. /** Frees the memory used by the given list. */
  1591. static void
  1592. hs_usage_list_free(hs_usage_list_t *lst)
  1593. {
  1594. if (!lst)
  1595. return;
  1596. hs_usage_list_clear(lst);
  1597. rephist_total_alloc -= sizeof(hs_usage_list_t);
  1598. tor_free(lst);
  1599. }
  1600. /** Frees the memory used by the given service-related observations. */
  1601. static void
  1602. hs_usage_service_related_observation_free(
  1603. hs_usage_service_related_observation_t *s)
  1604. {
  1605. if (!s)
  1606. return;
  1607. hs_usage_list_free(s->list);
  1608. rephist_total_alloc -= sizeof(hs_usage_service_related_observation_t);
  1609. tor_free(s);
  1610. }
  1611. /** Frees the memory used by the given period-specific observations. */
  1612. static void
  1613. hs_usage_general_period_related_observations_free(
  1614. hs_usage_general_period_related_observations_t *s)
  1615. {
  1616. rephist_total_alloc-=sizeof(hs_usage_general_period_related_observations_t);
  1617. tor_free(s);
  1618. }
  1619. /** Frees the memory used by period-specific information. */
  1620. static void
  1621. hs_usage_current_observation_period_free(
  1622. hs_usage_current_observation_period_t *s)
  1623. {
  1624. rephist_total_alloc -= sizeof(hs_usage_current_observation_period_t);
  1625. tor_free(s);
  1626. }
  1627. /** Frees all memory that was used for collecting hidden service usage data. */
  1628. void
  1629. hs_usage_free_all(void)
  1630. {
  1631. hs_usage_general_period_related_observations_free(descs);
  1632. descs = NULL;
  1633. hs_usage_service_related_observation_free(fetch_successful);
  1634. hs_usage_service_related_observation_free(fetch_total);
  1635. hs_usage_service_related_observation_free(publish_novel);
  1636. hs_usage_service_related_observation_free(publish_total);
  1637. fetch_successful = fetch_total = publish_novel = publish_total = NULL;
  1638. hs_usage_current_observation_period_free(current_period);
  1639. current_period = NULL;
  1640. }
  1641. /** Inserts a new occurrence for the given service id to the given ordered
  1642. * list. */
  1643. static void
  1644. hs_usage_insert_value(hs_usage_list_t *lst, const char *service_id)
  1645. {
  1646. /* search if there is already an elem with same service_id in list */
  1647. hs_usage_list_elem_t *current = lst->start;
  1648. hs_usage_list_elem_t *previous = NULL;
  1649. while (current != NULL && strcasecmp(current->service_id,service_id)) {
  1650. previous = current;
  1651. current = current->next;
  1652. }
  1653. /* found an element with same service_id? */
  1654. if (current == NULL) {
  1655. /* not found! append to end (which could also be the end of a zero-length
  1656. * list), don't need to sort (1 is smallest value). */
  1657. /* create elem */
  1658. hs_usage_list_elem_t *e = hs_usage_list_elem_new();
  1659. /* update list attributes (one new elem, one new occurrence) */
  1660. lst->total_count++;
  1661. lst->total_service_ids++;
  1662. /* copy service id to elem */
  1663. strlcpy(e->service_id,service_id,sizeof(e->service_id));
  1664. /* let either l->start or previously last elem point to new elem */
  1665. if (lst->start == NULL) {
  1666. /* this is the first elem */
  1667. lst->start = e;
  1668. } else {
  1669. /* there were elems in the list before */
  1670. previous->next = e;
  1671. }
  1672. } else {
  1673. /* found! add occurrence to elem and consider resorting */
  1674. /* update list attributes (no new elem, but one new occurrence) */
  1675. lst->total_count++;
  1676. /* add occurrence to elem */
  1677. current->count++;
  1678. /* is it another than the first list elem? and has previous elem fewer
  1679. * count than current? then we need to resort */
  1680. if (previous != NULL && previous->count < current->count) {
  1681. /* yes! we need to resort */
  1682. /* remove current elem first */
  1683. previous->next = current->next;
  1684. /* can we prepend elem to all other elements? */
  1685. if (lst->start->count <= current->count) {
  1686. /* yes! prepend elem */
  1687. current->next = lst->start;
  1688. lst->start = current;
  1689. } else {
  1690. /* no! walk through list a second time and insert at correct place */
  1691. hs_usage_list_elem_t *insert_current = lst->start->next;
  1692. hs_usage_list_elem_t *insert_previous = lst->start;
  1693. while (insert_current != NULL &&
  1694. insert_current->count > current->count) {
  1695. insert_previous = insert_current;
  1696. insert_current = insert_current->next;
  1697. }
  1698. /* insert here */
  1699. current->next = insert_current;
  1700. insert_previous->next = current;
  1701. }
  1702. }
  1703. }
  1704. }
  1705. /** Writes the current service-related observations to the history array and
  1706. * clears the observations of the current period. */
  1707. static void
  1708. hs_usage_write_service_related_observations_to_history(
  1709. hs_usage_current_observation_period_t *p,
  1710. hs_usage_service_related_observation_t *h)
  1711. {
  1712. /* walk through the first 20 % of list elements and calculate frequency
  1713. * distributions */
  1714. /* maximum indices for the three frequencies */
  1715. int five_percent_idx = h->list->total_service_ids/20;
  1716. int ten_percent_idx = h->list->total_service_ids/10;
  1717. int twenty_percent_idx = h->list->total_service_ids/5;
  1718. /* temp values */
  1719. uint32_t five_percent = 0;
  1720. uint32_t ten_percent = 0;
  1721. uint32_t twenty_percent = 0;
  1722. /* walk through list */
  1723. hs_usage_list_elem_t *current = h->list->start;
  1724. int i=0;
  1725. while (current != NULL && i <= twenty_percent_idx) {
  1726. twenty_percent += current->count;
  1727. if (i <= ten_percent_idx)
  1728. ten_percent += current->count;
  1729. if (i <= five_percent_idx)
  1730. five_percent += current->count;
  1731. current = current->next;
  1732. i++;
  1733. }
  1734. /* copy frequencies */
  1735. h->twenty[p->next_idx] = twenty_percent;
  1736. h->ten[p->next_idx] = ten_percent;
  1737. h->five[p->next_idx] = five_percent;
  1738. /* copy total number of observations */
  1739. h->totals[p->next_idx] = h->list->total_count;
  1740. /* free memory of old list */
  1741. hs_usage_list_clear(h->list);
  1742. }
  1743. /** Advances to next observation period. */
  1744. static void
  1745. hs_usage_advance_current_observation_period(void)
  1746. {
  1747. /* aggregate observations to history, including frequency distribution
  1748. * arrays */
  1749. hs_usage_write_service_related_observations_to_history(
  1750. current_period, publish_total);
  1751. hs_usage_write_service_related_observations_to_history(
  1752. current_period, publish_novel);
  1753. hs_usage_write_service_related_observations_to_history(
  1754. current_period, fetch_total);
  1755. hs_usage_write_service_related_observations_to_history(
  1756. current_period, fetch_successful);
  1757. /* write current number of descriptors to descs history */
  1758. descs->totals[current_period->next_idx] = rend_cache_size();
  1759. /* advance to next period */
  1760. current_period->next_idx++;
  1761. if (current_period->next_idx == NUM_TOTALS_HS_USAGE)
  1762. current_period->next_idx = 0;
  1763. if (current_period->num_set < NUM_TOTALS_HS_USAGE)
  1764. ++current_period->num_set;
  1765. current_period->start_of_current_period=current_period->start_of_next_period;
  1766. current_period->start_of_next_period += NUM_SECS_HS_USAGE_SUM_INTERVAL;
  1767. }
  1768. /** Checks if the current period is up to date, and if not, advances it. */
  1769. static void
  1770. hs_usage_check_if_current_period_is_up_to_date(time_t now)
  1771. {
  1772. while (now > current_period->start_of_next_period) {
  1773. hs_usage_advance_current_observation_period();
  1774. }
  1775. }
  1776. /** Adds a service-related observation, maybe after advancing to next
  1777. * observation period. */
  1778. static void
  1779. hs_usage_add_service_related_observation(
  1780. hs_usage_service_related_observation_t *h,
  1781. time_t now,
  1782. const char *service_id)
  1783. {
  1784. if (now < current_period->start_of_current_period) {
  1785. /* don't record old data */
  1786. return;
  1787. }
  1788. /* check if we are up-to-date */
  1789. hs_usage_check_if_current_period_is_up_to_date(now);
  1790. /* add observation */
  1791. hs_usage_insert_value(h->list, service_id);
  1792. }
  1793. /** Adds the observation of storing a rendezvous service descriptor to our
  1794. * cache in our role as HS authoritative directory. */
  1795. void
  1796. hs_usage_note_publish_total(const char *service_id, time_t now)
  1797. {
  1798. hs_usage_add_service_related_observation(publish_total, now, service_id);
  1799. }
  1800. /** Adds the observation of storing a novel rendezvous service descriptor to
  1801. * our cache in our role as HS authoritative directory. */
  1802. void
  1803. hs_usage_note_publish_novel(const char *service_id, time_t now)
  1804. {
  1805. hs_usage_add_service_related_observation(publish_novel, now, service_id);
  1806. }
  1807. /** Adds the observation of being requested for a rendezvous service descriptor
  1808. * in our role as HS authoritative directory. */
  1809. void
  1810. hs_usage_note_fetch_total(const char *service_id, time_t now)
  1811. {
  1812. hs_usage_add_service_related_observation(fetch_total, now, service_id);
  1813. }
  1814. /** Adds the observation of being requested for a rendezvous service descriptor
  1815. * in our role as HS authoritative directory and being able to answer that
  1816. * request successfully. */
  1817. void
  1818. hs_usage_note_fetch_successful(const char *service_id, time_t now)
  1819. {
  1820. hs_usage_add_service_related_observation(fetch_successful, now, service_id);
  1821. }
  1822. /** Writes the given circular array to a string. */
  1823. static size_t
  1824. hs_usage_format_history(char *buf, size_t len, uint32_t *data)
  1825. {
  1826. char *cp = buf; /* pointer where we are in the buffer */
  1827. int i, n;
  1828. if (current_period->num_set <= current_period->next_idx) {
  1829. i = 0; /* not been through circular array */
  1830. } else {
  1831. i = current_period->next_idx;
  1832. }
  1833. for (n = 0; n < current_period->num_set; ++n,++i) {
  1834. if (i >= NUM_TOTALS_HS_USAGE)
  1835. i -= NUM_TOTALS_HS_USAGE;
  1836. tor_assert(i < NUM_TOTALS_HS_USAGE);
  1837. if (n == (current_period->num_set-1))
  1838. tor_snprintf(cp, len-(cp-buf), "%d", data[i]);
  1839. else
  1840. tor_snprintf(cp, len-(cp-buf), "%d,", data[i]);
  1841. cp += strlen(cp);
  1842. }
  1843. return cp-buf;
  1844. }
  1845. /** Writes the complete usage history as hidden service authoritative directory
  1846. * to a string. */
  1847. static char *
  1848. hs_usage_format_statistics(void)
  1849. {
  1850. char *buf, *cp, *s = NULL;
  1851. char t[ISO_TIME_LEN+1];
  1852. int r;
  1853. uint32_t *data = NULL;
  1854. size_t len;
  1855. len = (70+20*NUM_TOTALS_HS_USAGE)*11;
  1856. buf = tor_malloc_zero(len);
  1857. cp = buf;
  1858. for (r = 0; r < 11; ++r) {
  1859. switch (r) {
  1860. case 0:
  1861. s = (char*) "publish-total-history";
  1862. data = publish_total->totals;
  1863. break;
  1864. case 1:
  1865. s = (char*) "publish-novel-history";
  1866. data = publish_novel->totals;
  1867. break;
  1868. case 2:
  1869. s = (char*) "publish-top-5-percent-history";
  1870. data = publish_total->five;
  1871. break;
  1872. case 3:
  1873. s = (char*) "publish-top-10-percent-history";
  1874. data = publish_total->ten;
  1875. break;
  1876. case 4:
  1877. s = (char*) "publish-top-20-percent-history";
  1878. data = publish_total->twenty;
  1879. break;
  1880. case 5:
  1881. s = (char*) "fetch-total-history";
  1882. data = fetch_total->totals;
  1883. break;
  1884. case 6:
  1885. s = (char*) "fetch-successful-history";
  1886. data = fetch_successful->totals;
  1887. break;
  1888. case 7:
  1889. s = (char*) "fetch-top-5-percent-history";
  1890. data = fetch_total->five;
  1891. break;
  1892. case 8:
  1893. s = (char*) "fetch-top-10-percent-history";
  1894. data = fetch_total->ten;
  1895. break;
  1896. case 9:
  1897. s = (char*) "fetch-top-20-percent-history";
  1898. data = fetch_total->twenty;
  1899. break;
  1900. case 10:
  1901. s = (char*) "desc-total-history";
  1902. data = descs->totals;
  1903. break;
  1904. }
  1905. format_iso_time(t, current_period->start_of_current_period);
  1906. tor_snprintf(cp, len-(cp-buf), "%s %s (%d s) ", s, t,
  1907. NUM_SECS_HS_USAGE_SUM_INTERVAL);
  1908. cp += strlen(cp);
  1909. cp += hs_usage_format_history(cp, len-(cp-buf), data);
  1910. strlcat(cp, "\n", len-(cp-buf));
  1911. ++cp;
  1912. }
  1913. return buf;
  1914. }
  1915. /** Writes current statistics to file. */
  1916. void
  1917. hs_usage_write_statistics_to_file(time_t now)
  1918. {
  1919. char *buf;
  1920. size_t len;
  1921. char *fname;
  1922. or_options_t *options;
  1923. /* check if we are up-to-date */
  1924. hs_usage_check_if_current_period_is_up_to_date(now);
  1925. buf = hs_usage_format_statistics();
  1926. options = get_options();
  1927. len = strlen(options->DataDirectory) + 16;
  1928. fname = tor_malloc(len);
  1929. tor_snprintf(fname,len, "%s"PATH_SEPARATOR"hsusage", options->DataDirectory);
  1930. write_str_to_file(fname,buf,0);
  1931. tor_free(buf);
  1932. tor_free(fname);
  1933. }