bwauth.c 14 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453
  1. /* Copyright (c) 2001-2004, Roger Dingledine.
  2. * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
  3. * Copyright (c) 2007-2018, The Tor Project, Inc. */
  4. /* See LICENSE for licensing information */
  5. /**
  6. * \file bwauth.c
  7. * \brief Code to read and apply bandwidth authority data.
  8. **/
  9. #define BWAUTH_PRIVATE
  10. #include "core/or/or.h"
  11. #include "feature/dirauth/bwauth.h"
  12. #include "app/config/config.h"
  13. #include "feature/nodelist/networkstatus.h"
  14. #include "feature/nodelist/routerlist.h"
  15. #include "feature/dirparse/ns_parse.h"
  16. #include "feature/nodelist/routerinfo_st.h"
  17. #include "feature/nodelist/vote_routerstatus_st.h"
  18. #include "lib/encoding/keyval.h"
  19. /** Total number of routers with measured bandwidth; this is set by
  20. * dirserv_count_measured_bs() before the loop in
  21. * dirserv_generate_networkstatus_vote_obj() and checked by
  22. * dirserv_get_credible_bandwidth() and
  23. * dirserv_compute_performance_thresholds() */
  24. static int routers_with_measured_bw = 0;
  25. /** Look through the routerlist, and using the measured bandwidth cache count
  26. * how many measured bandwidths we know. This is used to decide whether we
  27. * ever trust advertised bandwidths for purposes of assigning flags. */
  28. void
  29. dirserv_count_measured_bws(const smartlist_t *routers)
  30. {
  31. /* Initialize this first */
  32. routers_with_measured_bw = 0;
  33. /* Iterate over the routerlist and count measured bandwidths */
  34. SMARTLIST_FOREACH_BEGIN(routers, const routerinfo_t *, ri) {
  35. /* Check if we know a measured bandwidth for this one */
  36. if (dirserv_has_measured_bw(ri->cache_info.identity_digest)) {
  37. ++routers_with_measured_bw;
  38. }
  39. } SMARTLIST_FOREACH_END(ri);
  40. }
  41. /** Return the last-computed result from dirserv_count_mesured_bws(). */
  42. int
  43. dirserv_get_last_n_measured_bws(void)
  44. {
  45. return routers_with_measured_bw;
  46. }
  47. /** Measured bandwidth cache entry */
  48. typedef struct mbw_cache_entry_s {
  49. long mbw_kb;
  50. time_t as_of;
  51. } mbw_cache_entry_t;
  52. /** Measured bandwidth cache - keys are identity_digests, values are
  53. * mbw_cache_entry_t *. */
  54. static digestmap_t *mbw_cache = NULL;
  55. /** Store a measured bandwidth cache entry when reading the measured
  56. * bandwidths file. */
  57. STATIC void
  58. dirserv_cache_measured_bw(const measured_bw_line_t *parsed_line,
  59. time_t as_of)
  60. {
  61. mbw_cache_entry_t *e = NULL;
  62. tor_assert(parsed_line);
  63. /* Allocate a cache if we need */
  64. if (!mbw_cache) mbw_cache = digestmap_new();
  65. /* Check if we have an existing entry */
  66. e = digestmap_get(mbw_cache, parsed_line->node_id);
  67. /* If we do, we can re-use it */
  68. if (e) {
  69. /* Check that we really are newer, and update */
  70. if (as_of > e->as_of) {
  71. e->mbw_kb = parsed_line->bw_kb;
  72. e->as_of = as_of;
  73. }
  74. } else {
  75. /* We'll have to insert a new entry */
  76. e = tor_malloc(sizeof(*e));
  77. e->mbw_kb = parsed_line->bw_kb;
  78. e->as_of = as_of;
  79. digestmap_set(mbw_cache, parsed_line->node_id, e);
  80. }
  81. }
  82. /** Clear and free the measured bandwidth cache */
  83. void
  84. dirserv_clear_measured_bw_cache(void)
  85. {
  86. if (mbw_cache) {
  87. /* Free the map and all entries */
  88. digestmap_free(mbw_cache, tor_free_);
  89. mbw_cache = NULL;
  90. }
  91. }
  92. /** Scan the measured bandwidth cache and remove expired entries */
  93. STATIC void
  94. dirserv_expire_measured_bw_cache(time_t now)
  95. {
  96. if (mbw_cache) {
  97. /* Iterate through the cache and check each entry */
  98. DIGESTMAP_FOREACH_MODIFY(mbw_cache, k, mbw_cache_entry_t *, e) {
  99. if (now > e->as_of + MAX_MEASUREMENT_AGE) {
  100. tor_free(e);
  101. MAP_DEL_CURRENT(k);
  102. }
  103. } DIGESTMAP_FOREACH_END;
  104. /* Check if we cleared the whole thing and free if so */
  105. if (digestmap_size(mbw_cache) == 0) {
  106. digestmap_free(mbw_cache, tor_free_);
  107. mbw_cache = 0;
  108. }
  109. }
  110. }
  111. /** Query the cache by identity digest, return value indicates whether
  112. * we found it. The bw_out and as_of_out pointers receive the cached
  113. * bandwidth value and the time it was cached if not NULL. */
  114. int
  115. dirserv_query_measured_bw_cache_kb(const char *node_id, long *bw_kb_out,
  116. time_t *as_of_out)
  117. {
  118. mbw_cache_entry_t *v = NULL;
  119. int rv = 0;
  120. if (mbw_cache && node_id) {
  121. v = digestmap_get(mbw_cache, node_id);
  122. if (v) {
  123. /* Found something */
  124. rv = 1;
  125. if (bw_kb_out) *bw_kb_out = v->mbw_kb;
  126. if (as_of_out) *as_of_out = v->as_of;
  127. }
  128. }
  129. return rv;
  130. }
  131. /** Predicate wrapper for dirserv_query_measured_bw_cache() */
  132. int
  133. dirserv_has_measured_bw(const char *node_id)
  134. {
  135. return dirserv_query_measured_bw_cache_kb(node_id, NULL, NULL);
  136. }
  137. /** Get the current size of the measured bandwidth cache */
  138. int
  139. dirserv_get_measured_bw_cache_size(void)
  140. {
  141. if (mbw_cache) return digestmap_size(mbw_cache);
  142. else return 0;
  143. }
  144. /** Return the bandwidth we believe for assigning flags; prefer measured
  145. * over advertised, and if we have above a threshold quantity of measured
  146. * bandwidths, we don't want to ever give flags to unmeasured routers, so
  147. * return 0. */
  148. uint32_t
  149. dirserv_get_credible_bandwidth_kb(const routerinfo_t *ri)
  150. {
  151. int threshold;
  152. uint32_t bw_kb = 0;
  153. long mbw_kb;
  154. tor_assert(ri);
  155. /* Check if we have a measured bandwidth, and check the threshold if not */
  156. if (!(dirserv_query_measured_bw_cache_kb(ri->cache_info.identity_digest,
  157. &mbw_kb, NULL))) {
  158. threshold = get_options()->MinMeasuredBWsForAuthToIgnoreAdvertised;
  159. if (routers_with_measured_bw > threshold) {
  160. /* Return zero for unmeasured bandwidth if we are above threshold */
  161. bw_kb = 0;
  162. } else {
  163. /* Return an advertised bandwidth otherwise */
  164. bw_kb = router_get_advertised_bandwidth_capped(ri) / 1000;
  165. }
  166. } else {
  167. /* We have the measured bandwidth in mbw */
  168. bw_kb = (uint32_t)mbw_kb;
  169. }
  170. return bw_kb;
  171. }
  172. /**
  173. * Read the measured bandwidth list file, apply it to the list of
  174. * vote_routerstatus_t and store all the headers in <b>bw_file_headers</b>.
  175. * Returns -1 on error, 0 otherwise.
  176. */
  177. int
  178. dirserv_read_measured_bandwidths(const char *from_file,
  179. smartlist_t *routerstatuses,
  180. smartlist_t *bw_file_headers)
  181. {
  182. FILE *fp = tor_fopen_cloexec(from_file, "r");
  183. int applied_lines = 0;
  184. time_t file_time, now;
  185. int ok;
  186. /* This flag will be 1 only when the first successful bw measurement line
  187. * has been encountered, so that measured_bw_line_parse don't give warnings
  188. * if there are additional header lines, as introduced in Bandwidth List spec
  189. * version 1.1.0 */
  190. int line_is_after_headers = 0;
  191. int rv = -1;
  192. char *line = NULL;
  193. size_t n = 0;
  194. /* Initialise line, so that we can't possibly run off the end. */
  195. if (fp == NULL) {
  196. log_warn(LD_CONFIG, "Can't open bandwidth file at configured location: %s",
  197. from_file);
  198. goto err;
  199. }
  200. /* If fgets fails, line is either unmodified, or indeterminate. */
  201. if (tor_getline(&line,&n,fp) <= 0) {
  202. log_warn(LD_DIRSERV, "Empty bandwidth file");
  203. goto err;
  204. }
  205. if (!strlen(line) || line[strlen(line)-1] != '\n') {
  206. log_warn(LD_DIRSERV, "Long or truncated time in bandwidth file: %s",
  207. escaped(line));
  208. goto err;
  209. }
  210. line[strlen(line)-1] = '\0';
  211. file_time = (time_t)tor_parse_ulong(line, 10, 0, ULONG_MAX, &ok, NULL);
  212. if (!ok) {
  213. log_warn(LD_DIRSERV, "Non-integer time in bandwidth file: %s",
  214. escaped(line));
  215. goto err;
  216. }
  217. now = time(NULL);
  218. if ((now - file_time) > MAX_MEASUREMENT_AGE) {
  219. log_warn(LD_DIRSERV, "Bandwidth measurement file stale. Age: %u",
  220. (unsigned)(time(NULL) - file_time));
  221. goto err;
  222. }
  223. /* If timestamp was correct and bw_file_headers is not NULL,
  224. * add timestamp to bw_file_headers */
  225. if (bw_file_headers)
  226. smartlist_add_asprintf(bw_file_headers, "timestamp=%lu",
  227. (unsigned long)file_time);
  228. if (routerstatuses)
  229. smartlist_sort(routerstatuses, compare_vote_routerstatus_entries);
  230. while (!feof(fp)) {
  231. measured_bw_line_t parsed_line;
  232. if (tor_getline(&line, &n, fp) >= 0) {
  233. if (measured_bw_line_parse(&parsed_line, line,
  234. line_is_after_headers) != -1) {
  235. /* This condition will be true when the first complete valid bw line
  236. * has been encountered, which means the end of the header lines. */
  237. line_is_after_headers = 1;
  238. /* Also cache the line for dirserv_get_bandwidth_for_router() */
  239. dirserv_cache_measured_bw(&parsed_line, file_time);
  240. if (measured_bw_line_apply(&parsed_line, routerstatuses) > 0)
  241. applied_lines++;
  242. /* if the terminator is found, it is the end of header lines, set the
  243. * flag but do not store anything */
  244. } else if (strcmp(line, BW_FILE_HEADERS_TERMINATOR) == 0) {
  245. line_is_after_headers = 1;
  246. /* if the line was not a correct relay line nor the terminator and
  247. * the end of the header lines has not been detected yet
  248. * and it is key_value and bw_file_headers did not reach the maximum
  249. * number of headers,
  250. * then assume this line is a header and add it to bw_file_headers */
  251. } else if (bw_file_headers &&
  252. (line_is_after_headers == 0) &&
  253. string_is_key_value(LOG_DEBUG, line) &&
  254. !strchr(line, ' ') &&
  255. (smartlist_len(bw_file_headers)
  256. < MAX_BW_FILE_HEADER_COUNT_IN_VOTE)) {
  257. line[strlen(line)-1] = '\0';
  258. smartlist_add_strdup(bw_file_headers, line);
  259. };
  260. }
  261. }
  262. /* Now would be a nice time to clean the cache, too */
  263. dirserv_expire_measured_bw_cache(now);
  264. log_info(LD_DIRSERV,
  265. "Bandwidth measurement file successfully read. "
  266. "Applied %d measurements.", applied_lines);
  267. rv = 0;
  268. err:
  269. if (line) {
  270. // we need to raw_free this buffer because we got it from tor_getdelim()
  271. raw_free(line);
  272. }
  273. if (fp)
  274. fclose(fp);
  275. return rv;
  276. }
  277. /**
  278. * Helper function to parse out a line in the measured bandwidth file
  279. * into a measured_bw_line_t output structure.
  280. *
  281. * If <b>line_is_after_headers</b> is true, then if we encounter an incomplete
  282. * bw line, return -1 and warn, since we are after the headers and we should
  283. * only parse bw lines. Return 0 otherwise.
  284. *
  285. * If <b>line_is_after_headers</b> is false then it means that we are not past
  286. * the header block yet. If we encounter an incomplete bw line, return -1 but
  287. * don't warn since there could be additional header lines coming. If we
  288. * encounter a proper bw line, return 0 (and we got past the headers).
  289. */
  290. STATIC int
  291. measured_bw_line_parse(measured_bw_line_t *out, const char *orig_line,
  292. int line_is_after_headers)
  293. {
  294. char *line = tor_strdup(orig_line);
  295. char *cp = line;
  296. int got_bw = 0;
  297. int got_node_id = 0;
  298. char *strtok_state; /* lame sauce d'jour */
  299. if (strlen(line) == 0) {
  300. log_warn(LD_DIRSERV, "Empty line in bandwidth file");
  301. tor_free(line);
  302. return -1;
  303. }
  304. /* Remove end of line character, so that is not part of the token */
  305. if (line[strlen(line) - 1] == '\n') {
  306. line[strlen(line) - 1] = '\0';
  307. }
  308. cp = tor_strtok_r(cp, " \t", &strtok_state);
  309. if (!cp) {
  310. log_warn(LD_DIRSERV, "Invalid line in bandwidth file: %s",
  311. escaped(orig_line));
  312. tor_free(line);
  313. return -1;
  314. }
  315. if (orig_line[strlen(orig_line)-1] != '\n') {
  316. log_warn(LD_DIRSERV, "Incomplete line in bandwidth file: %s",
  317. escaped(orig_line));
  318. tor_free(line);
  319. return -1;
  320. }
  321. do {
  322. if (strcmpstart(cp, "bw=") == 0) {
  323. int parse_ok = 0;
  324. char *endptr;
  325. if (got_bw) {
  326. log_warn(LD_DIRSERV, "Double bw= in bandwidth file line: %s",
  327. escaped(orig_line));
  328. tor_free(line);
  329. return -1;
  330. }
  331. cp+=strlen("bw=");
  332. out->bw_kb = tor_parse_long(cp, 10, 0, LONG_MAX, &parse_ok, &endptr);
  333. if (!parse_ok || (*endptr && !TOR_ISSPACE(*endptr))) {
  334. log_warn(LD_DIRSERV, "Invalid bandwidth in bandwidth file line: %s",
  335. escaped(orig_line));
  336. tor_free(line);
  337. return -1;
  338. }
  339. got_bw=1;
  340. } else if (strcmpstart(cp, "node_id=$") == 0) {
  341. if (got_node_id) {
  342. log_warn(LD_DIRSERV, "Double node_id= in bandwidth file line: %s",
  343. escaped(orig_line));
  344. tor_free(line);
  345. return -1;
  346. }
  347. cp+=strlen("node_id=$");
  348. if (strlen(cp) != HEX_DIGEST_LEN ||
  349. base16_decode(out->node_id, DIGEST_LEN,
  350. cp, HEX_DIGEST_LEN) != DIGEST_LEN) {
  351. log_warn(LD_DIRSERV, "Invalid node_id in bandwidth file line: %s",
  352. escaped(orig_line));
  353. tor_free(line);
  354. return -1;
  355. }
  356. strlcpy(out->node_hex, cp, sizeof(out->node_hex));
  357. got_node_id=1;
  358. }
  359. } while ((cp = tor_strtok_r(NULL, " \t", &strtok_state)));
  360. if (got_bw && got_node_id) {
  361. tor_free(line);
  362. return 0;
  363. } else if (line_is_after_headers == 0) {
  364. /* There could be additional header lines, therefore do not give warnings
  365. * but returns -1 since it's not a complete bw line. */
  366. log_debug(LD_DIRSERV, "Missing bw or node_id in bandwidth file line: %s",
  367. escaped(orig_line));
  368. tor_free(line);
  369. return -1;
  370. } else {
  371. log_warn(LD_DIRSERV, "Incomplete line in bandwidth file: %s",
  372. escaped(orig_line));
  373. tor_free(line);
  374. return -1;
  375. }
  376. }
  377. /**
  378. * Helper function to apply a parsed measurement line to a list
  379. * of bandwidth statuses. Returns true if a line is found,
  380. * false otherwise.
  381. */
  382. STATIC int
  383. measured_bw_line_apply(measured_bw_line_t *parsed_line,
  384. smartlist_t *routerstatuses)
  385. {
  386. vote_routerstatus_t *rs = NULL;
  387. if (!routerstatuses)
  388. return 0;
  389. rs = smartlist_bsearch(routerstatuses, parsed_line->node_id,
  390. compare_digest_to_vote_routerstatus_entry);
  391. if (rs) {
  392. rs->has_measured_bw = 1;
  393. rs->measured_bw_kb = (uint32_t)parsed_line->bw_kb;
  394. } else {
  395. log_info(LD_DIRSERV, "Node ID %s not found in routerstatus list",
  396. parsed_line->node_hex);
  397. }
  398. return rs != NULL;
  399. }