Tor  0.4.3.0-alpha-dev
bwauth.c
Go to the documentation of this file.
1 /* Copyright (c) 2001-2004, Roger Dingledine.
2  * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
3  * Copyright (c) 2007-2020, 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"
20 
24 
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
40 {
41  /* Initialize this first */
43 
44  /* Iterate over the routerlist and count measured bandwidths */
45  SMARTLIST_FOREACH_BEGIN(routers, const routerinfo_t *, ri) {
46  /* Check if we know a measured bandwidth for this one */
47  if (dirserv_has_measured_bw(ri->cache_info.identity_digest)) {
49  }
50  } SMARTLIST_FOREACH_END(ri);
51 }
52 
53 /** Return the last-computed result from dirserv_count_mesured_bws(). */
54 int
56 {
58 }
59 
60 /** Measured bandwidth cache entry */
61 typedef struct mbw_cache_entry_t {
62  long mbw_kb;
63  time_t as_of;
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 dirserv_cache_measured_bw(const measured_bw_line_t *parsed_line,
74  time_t as_of)
75 {
76  mbw_cache_entry_t *e = NULL;
77 
78  tor_assert(parsed_line);
79 
80  /* Allocate a cache if we need */
81  if (!mbw_cache) mbw_cache = digestmap_new();
82 
83  /* Check if we have an existing entry */
84  e = digestmap_get(mbw_cache, parsed_line->node_id);
85  /* If we do, we can re-use it */
86  if (e) {
87  /* Check that we really are newer, and update */
88  if (as_of > e->as_of) {
89  e->mbw_kb = parsed_line->bw_kb;
90  e->as_of = as_of;
91  }
92  } else {
93  /* We'll have to insert a new entry */
94  e = tor_malloc(sizeof(*e));
95  e->mbw_kb = parsed_line->bw_kb;
96  e->as_of = as_of;
97  digestmap_set(mbw_cache, parsed_line->node_id, e);
98  }
99 }
100 
101 /** Clear and free the measured bandwidth cache */
102 void
104 {
105  if (mbw_cache) {
106  /* Free the map and all entries */
107  digestmap_free(mbw_cache, tor_free_);
108  mbw_cache = NULL;
109  }
110 }
111 
112 /** Scan the measured bandwidth cache and remove expired entries */
113 STATIC void
115 {
116 
117  if (mbw_cache) {
118  /* Iterate through the cache and check each entry */
120  if (now > e->as_of + MAX_MEASUREMENT_AGE) {
121  tor_free(e);
122  MAP_DEL_CURRENT(k);
123  }
125 
126  /* Check if we cleared the whole thing and free if so */
127  if (digestmap_size(mbw_cache) == 0) {
128  digestmap_free(mbw_cache, tor_free_);
129  mbw_cache = 0;
130  }
131  }
132 }
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 dirserv_query_measured_bw_cache_kb(const char *node_id, long *bw_kb_out,
139  time_t *as_of_out)
140 {
141  mbw_cache_entry_t *v = NULL;
142  int rv = 0;
143 
144  if (mbw_cache && node_id) {
145  v = digestmap_get(mbw_cache, node_id);
146  if (v) {
147  /* Found something */
148  rv = 1;
149  if (bw_kb_out) *bw_kb_out = v->mbw_kb;
150  if (as_of_out) *as_of_out = v->as_of;
151  }
152  }
153 
154  return rv;
155 }
156 
157 /** Predicate wrapper for dirserv_query_measured_bw_cache() */
158 int
159 dirserv_has_measured_bw(const char *node_id)
160 {
161  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
167 {
168  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
178 {
179  int threshold;
180  uint32_t bw_kb = 0;
181  long mbw_kb;
182 
183  tor_assert(ri);
184  /* Check if we have a measured bandwidth, and check the threshold if not */
186  &mbw_kb, NULL))) {
187  threshold = dirauth_get_options()->MinMeasuredBWsForAuthToIgnoreAdvertised;
188  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  bw_kb = router_get_advertised_bandwidth_capped(ri) / 1000;
194  }
195  } else {
196  /* We have the measured bandwidth in mbw */
197  bw_kb = (uint32_t)mbw_kb;
198  }
199 
200  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 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  FILE *fp = tor_fopen_cloexec(from_file, "r");
238  int applied_lines = 0;
239  time_t file_time, now;
240  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  int line_is_after_headers = 0;
246  int rv = -1;
247  char *line = NULL;
248  size_t n = 0;
249  crypto_digest_t *digest = crypto_digest256_new(DIGEST_SHA256);
250 
251  if (fp == NULL) {
252  log_warn(LD_CONFIG, "Can't open bandwidth file at configured location: %s",
253  from_file);
254  goto err;
255  }
256 
257  if (tor_getline(&line,&n,fp) <= 0) {
258  log_warn(LD_DIRSERV, "Empty bandwidth file");
259  goto err;
260  }
261  /* If the line could be gotten, add it to the digest */
262  crypto_digest_add_bytes(digest, (const char *) line, strlen(line));
263 
264  if (!strlen(line) || line[strlen(line)-1] != '\n') {
265  log_warn(LD_DIRSERV, "Long or truncated time in bandwidth file: %s",
266  escaped(line));
267  /* Continue adding lines to the digest. */
268  goto continue_digest;
269  }
270 
271  line[strlen(line)-1] = '\0';
272  file_time = (time_t)tor_parse_ulong(line, 10, 0, ULONG_MAX, &ok, NULL);
273  if (!ok) {
274  log_warn(LD_DIRSERV, "Non-integer time in bandwidth file: %s",
275  escaped(line));
276  goto continue_digest;
277  }
278 
279  now = approx_time();
280  if ((now - file_time) > MAX_MEASUREMENT_AGE) {
281  log_warn(LD_DIRSERV, "Bandwidth measurement file stale. Age: %u",
282  (unsigned)(time(NULL) - file_time));
283  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  if (bw_file_headers)
289  smartlist_add_asprintf(bw_file_headers, "timestamp=%lu",
290  (unsigned long)file_time);
291 
292  if (routerstatuses)
293  smartlist_sort(routerstatuses, compare_vote_routerstatus_entries);
294 
295  while (!feof(fp)) {
296  measured_bw_line_t parsed_line;
297  if (tor_getline(&line, &n, fp) >= 0) {
298  crypto_digest_add_bytes(digest, (const char *) line, strlen(line));
299  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  line_is_after_headers = 1;
304  /* Also cache the line for dirserv_get_bandwidth_for_router() */
305  dirserv_cache_measured_bw(&parsed_line, file_time);
306  if (measured_bw_line_apply(&parsed_line, routerstatuses) > 0)
307  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  } 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  } else if (bw_file_headers &&
318  (line_is_after_headers == 0) &&
320  !strchr(line, ' ') &&
321  (smartlist_len(bw_file_headers)
323  line[strlen(line)-1] = '\0';
324  smartlist_add_strdup(bw_file_headers, line);
325  };
326  }
327  }
328 
329  /* Now would be a nice time to clean the cache, too */
331 
332  log_info(LD_DIRSERV,
333  "Bandwidth measurement file successfully read. "
334  "Applied %d measurements.", applied_lines);
335  rv = 0;
336 
337  continue_digest:
338  /* Continue parsing lines to return the digest of the Bandwidth File. */
339  while (!feof(fp)) {
340  if (tor_getline(&line, &n, fp) >= 0) {
341  crypto_digest_add_bytes(digest, (const char *) line, strlen(line));
342  }
343  }
344 
345  err:
346  if (line) {
347  // we need to raw_free this buffer because we got it from tor_getdelim()
348  raw_free(line);
349  }
350  if (fp)
351  fclose(fp);
352  if (digest_out)
353  crypto_digest_get_digest(digest, (char *) digest_out, DIGEST256_LEN);
354  crypto_digest_free(digest);
355  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 measured_bw_line_parse(measured_bw_line_t *out, const char *orig_line,
376  int line_is_after_headers)
377 {
378  char *line = tor_strdup(orig_line);
379  char *cp = line;
380  int got_bw = 0;
381  int got_node_id = 0;
382  char *strtok_state; /* lame sauce d'jour */
383 
384  if (strlen(line) == 0) {
385  log_warn(LD_DIRSERV, "Empty line in bandwidth file");
386  tor_free(line);
387  return -1;
388  }
389 
390  /* Remove end of line character, so that is not part of the token */
391  if (line[strlen(line) - 1] == '\n') {
392  line[strlen(line) - 1] = '\0';
393  }
394 
395  cp = tor_strtok_r(cp, " \t", &strtok_state);
396 
397  if (!cp) {
398  log_warn(LD_DIRSERV, "Invalid line in bandwidth file: %s",
399  escaped(orig_line));
400  tor_free(line);
401  return -1;
402  }
403 
404  if (orig_line[strlen(orig_line)-1] != '\n') {
405  log_warn(LD_DIRSERV, "Incomplete line in bandwidth file: %s",
406  escaped(orig_line));
407  tor_free(line);
408  return -1;
409  }
410 
411  do {
412  // If the line contains vote=0, ignore it.
413  if (strcmpstart(cp, "vote=0") == 0) {
414  log_debug(LD_DIRSERV, "Ignoring bandwidth file line that contains "
415  "vote=0: %s",escaped(orig_line));
416  tor_free(line);
417  return -1;
418  } else if (strcmpstart(cp, "bw=") == 0) {
419  int parse_ok = 0;
420  char *endptr;
421  if (got_bw) {
422  log_warn(LD_DIRSERV, "Double bw= in bandwidth file line: %s",
423  escaped(orig_line));
424  tor_free(line);
425  return -1;
426  }
427  cp+=strlen("bw=");
428 
429  out->bw_kb = tor_parse_long(cp, 10, 0, LONG_MAX, &parse_ok, &endptr);
430  if (!parse_ok || (*endptr && !TOR_ISSPACE(*endptr))) {
431  log_warn(LD_DIRSERV, "Invalid bandwidth in bandwidth file line: %s",
432  escaped(orig_line));
433  tor_free(line);
434  return -1;
435  }
436  got_bw=1;
437  } else if (strcmpstart(cp, "node_id=$") == 0) {
438  if (got_node_id) {
439  log_warn(LD_DIRSERV, "Double node_id= in bandwidth file line: %s",
440  escaped(orig_line));
441  tor_free(line);
442  return -1;
443  }
444  cp+=strlen("node_id=$");
445 
446  if (strlen(cp) != HEX_DIGEST_LEN ||
447  base16_decode(out->node_id, DIGEST_LEN,
448  cp, HEX_DIGEST_LEN) != DIGEST_LEN) {
449  log_warn(LD_DIRSERV, "Invalid node_id in bandwidth file line: %s",
450  escaped(orig_line));
451  tor_free(line);
452  return -1;
453  }
454  strlcpy(out->node_hex, cp, sizeof(out->node_hex));
455  got_node_id=1;
456  }
457  } while ((cp = tor_strtok_r(NULL, " \t", &strtok_state)));
458 
459  if (got_bw && got_node_id) {
460  tor_free(line);
461  return 0;
462  } 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  log_debug(LD_DIRSERV, "Missing bw or node_id in bandwidth file line: %s",
466  escaped(orig_line));
467  tor_free(line);
468  return -1;
469  } else {
470  log_warn(LD_DIRSERV, "Incomplete line in bandwidth file: %s",
471  escaped(orig_line));
472  tor_free(line);
473  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 measured_bw_line_apply(measured_bw_line_t *parsed_line,
484  smartlist_t *routerstatuses)
485 {
486  vote_routerstatus_t *rs = NULL;
487  if (!routerstatuses)
488  return 0;
489 
490  rs = smartlist_bsearch(routerstatuses, parsed_line->node_id,
492 
493  if (rs) {
494  rs->has_measured_bw = 1;
495  rs->measured_bw_kb = (uint32_t)parsed_line->bw_kb;
496  } else {
497  log_info(LD_DIRSERV, "Node ID %s not found in routerstatus list",
498  parsed_line->node_hex);
499  }
500 
501  return rs != NULL;
502 }
uint32_t router_get_advertised_bandwidth_capped(const routerinfo_t *router)
Definition: routerlist.c:572
int dirserv_get_measured_bw_cache_size(void)
Definition: bwauth.c:166
Structure dirauth_options_t to hold directory authority options.
Router descriptor structure.
#define SMARTLIST_FOREACH_BEGIN(sl, type, var)
void crypto_digest_get_digest(crypto_digest_t *digest, char *out, size_t out_len)
Header for dirauth_sys.c.
void smartlist_add_strdup(struct smartlist_t *sl, const char *string)
void dirserv_count_measured_bws(const smartlist_t *routers)
Definition: bwauth.c:39
unsigned long tor_parse_ulong(const char *s, int base, unsigned long min, unsigned long max, int *ok, char **next)
Definition: parse_int.c:78
crypto_digest_t * crypto_digest256_new(digest_algorithm_t algorithm)
Header file for config.c.
char identity_digest[DIGEST_LEN]
void crypto_digest_add_bytes(crypto_digest_t *digest, const char *data, size_t len)
#define tor_assert(expr)
Definition: util_bug.h:102
int strcmpstart(const char *s1, const char *s2)
Definition: util_string.c:206
#define MAP_DEL_CURRENT(keyvar)
Definition: map.h:140
#define BW_FILE_HEADERS_TERMINATOR
Definition: bwauth.h:20
#define tor_free(p)
Definition: malloc.h:52
int dirserv_has_measured_bw(const char *node_id)
Definition: bwauth.c:159
static int routers_with_measured_bw
Definition: bwauth.c:33
void dirserv_clear_measured_bw_cache(void)
Definition: bwauth.c:103
#define STATIC
Definition: testsupport.h:32
uint32_t dirserv_get_credible_bandwidth_kb(const routerinfo_t *ri)
Definition: bwauth.c:177
#define MAX_BW_FILE_HEADER_COUNT_IN_VOTE
Definition: bwauth.h:16
int dirserv_read_measured_bandwidths(const char *from_file, smartlist_t *routerstatuses, smartlist_t *bw_file_headers, uint8_t *digest_out)
Definition: bwauth.c:232
#define DIGEST256_LEN
Definition: digest_sizes.h:23
STATIC void dirserv_expire_measured_bw_cache(time_t now)
Definition: bwauth.c:114
Header for crypto_format.c.
INT MinMeasuredBWsForAuthToIgnoreAdvertised
#define DIGEST_LEN
Definition: digest_sizes.h:20
void smartlist_add_asprintf(struct smartlist_t *sl, const char *pattern,...)
Definition: smartlist.c:36
Master header file for Tor-specific functionality.
STATIC void dirserv_cache_measured_bw(const measured_bw_line_t *parsed_line, time_t as_of)
Definition: bwauth.c:73
#define LD_DIRSERV
Definition: log.h:90
Header file for bwauth.c.
void tor_free_(void *mem)
Definition: malloc.c:227
#define crypto_digest_free(d)
int compare_digest_to_vote_routerstatus_entry(const void *_key, const void **_member)
void * smartlist_bsearch(const smartlist_t *sl, const void *key, int(*compare)(const void *key, const void **member))
Definition: smartlist.c:411
#define DIGESTMAP_FOREACH_END
Definition: map.h:168
#define HEX_DIGEST_LEN
Definition: crypto_digest.h:35
STATIC int measured_bw_line_parse(measured_bw_line_t *out, const char *orig_line, int line_is_after_headers)
Definition: bwauth.c:375
int dirserv_get_last_n_measured_bws(void)
Definition: bwauth.c:55
Definition: bwauth.c:61
Header file for ns_parse.c.
int dirserv_query_measured_bw_cache_kb(const char *node_id, long *bw_kb_out, time_t *as_of_out)
Definition: bwauth.c:138
static digestmap_t * mbw_cache
Definition: bwauth.c:68
const char * escaped(const char *s)
Definition: escape.c:126
#define DIGESTMAP_FOREACH_MODIFY(map, keyvar, valtype, valvar)
Definition: map.h:165
Header for keyval.c.
time_t approx_time(void)
Definition: approx_time.c:32
#define LOG_DEBUG
Definition: log.h:42
long tor_parse_long(const char *s, int base, long min, long max, int *ok, char **next)
Definition: parse_int.c:59
int base16_decode(char *dest, size_t destlen, const char *src, size_t srclen)
Definition: binascii.c:506
STATIC int measured_bw_line_apply(measured_bw_line_t *parsed_line, smartlist_t *routerstatuses)
Definition: bwauth.c:483
int string_is_key_value(int severity, const char *string)
Definition: keyval.c:25
FILE * tor_fopen_cloexec(const char *path, const char *mode)
Definition: files.c:86
void smartlist_sort(smartlist_t *sl, int(*compare)(const void **a, const void **b))
Definition: smartlist.c:334
Header file for networkstatus.c.
#define LD_CONFIG
Definition: log.h:68
Header file for routerlist.c.
Routerstatus (vote entry) structure.