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