Tor  0.4.7.0-alpha-dev
bwhist.c
Go to the documentation of this file.
1 /* Copyright (c) 2001 Matej Pfajfar.
2  * Copyright (c) 2001-2004, Roger Dingledine.
3  * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
4  * Copyright (c) 2007-2021, The Tor Project, Inc. */
5 /* See LICENSE for licensing information */
6 
7 /**
8  * @file bwhist.c
9  * @brief Tracking for relay bandwidth history
10  *
11  * This module handles bandwidth usage history, used by relays to
12  * self-report how much bandwidth they've used for different
13  * purposes over last day or so, in order to generate the
14  * {dirreq-,}{read,write}-history lines in that they publish.
15  **/
16 
17 #define BWHIST_PRIVATE
18 #include "orconfig.h"
19 #include "core/or/or.h"
20 #include "feature/stats/bwhist.h"
21 
22 #include "app/config/config.h"
23 #include "app/config/statefile.h"
25 
27 #include "app/config/or_state_st.h"
29 
30 /** Shift the current period of b forward by one. */
31 STATIC void
33 {
34  /* Store total from current period. */
36  /* Store maximum from current period. */
37  b->maxima[b->next_max_idx++] = b->max_total;
38  /* Advance next_period and next_max_idx */
40  if (b->next_max_idx == NUM_TOTALS)
41  b->next_max_idx = 0;
42  if (b->num_maxes_set < NUM_TOTALS)
43  ++b->num_maxes_set;
44  /* Reset max_total. */
45  b->max_total = 0;
46  /* Reset total_in_period. */
47  b->total_in_period = 0;
48 }
49 
50 /** Shift the current observation time of <b>b</b> forward by one second. */
51 STATIC void
53 {
54  int nextidx;
55  uint64_t total;
56 
57  /* Calculate the total bandwidth for the last NUM_SECS_ROLLING_MEASURE
58  * seconds; adjust max_total as needed.*/
59  total = b->total_obs + b->obs[b->cur_obs_idx];
60  if (total > b->max_total)
61  b->max_total = total;
62 
63  nextidx = b->cur_obs_idx+1;
64  if (nextidx == NUM_SECS_ROLLING_MEASURE)
65  nextidx = 0;
66 
67  b->total_obs = total - b->obs[nextidx];
68  b->obs[nextidx]=0;
69  b->cur_obs_idx = nextidx;
70 
71  if (++b->cur_obs_time >= b->next_period)
72  commit_max(b);
73 }
74 
75 /** Add <b>n</b> bytes to the number of bytes in <b>b</b> for second
76  * <b>when</b>. */
77 STATIC void
78 add_obs(bw_array_t *b, time_t when, uint64_t n)
79 {
80  if (when < b->cur_obs_time)
81  return; /* Don't record data in the past. */
82 
83  /* If we're currently adding observations for an earlier second than
84  * 'when', advance b->cur_obs_time and b->cur_obs_idx by an
85  * appropriate number of seconds, and do all the other housekeeping. */
86  while (when > b->cur_obs_time) {
87  /* Doing this one second at a time is potentially inefficient, if we start
88  with a state file that is very old. Fortunately, it doesn't seem to
89  show up in profiles, so we can just ignore it for now. */
90  advance_obs(b);
91  }
92 
93  b->obs[b->cur_obs_idx] += n;
94  b->total_in_period += n;
95 }
96 
97 /** Allocate, initialize, and return a new bw_array. */
100 {
101  bw_array_t *b;
102  time_t start;
103  b = tor_malloc_zero(sizeof(bw_array_t));
104  start = time(NULL);
105  b->cur_obs_time = start;
107  return b;
108 }
109 
110 /** Free storage held by bandwidth array <b>b</b>. */
111 STATIC void
113 {
114  if (!b) {
115  return;
116  }
117 
118  tor_free(b);
119 }
120 
121 /** Recent history of bandwidth observations for (all) read operations. */
122 static bw_array_t *read_array = NULL;
123 /** Recent history of bandwidth observations for IPv6 read operations. */
125 /** Recent history of bandwidth observations for (all) write operations. */
127 /** Recent history of bandwidth observations for IPv6 write operations. */
129 /** Recent history of bandwidth observations for read operations for the
130  directory protocol. */
131 static bw_array_t *dir_read_array = NULL;
132 /** Recent history of bandwidth observations for write operations for the
133  directory protocol. */
135 
136 /** Set up structures for bandwidth history, clearing them if they already
137  * exist. */
138 void
140 {
141  bw_array_free(read_array);
142  bw_array_free(read_array_ipv6);
143  bw_array_free(write_array);
144  bw_array_free(write_array_ipv6);
145  bw_array_free(dir_read_array);
146  bw_array_free(dir_write_array);
147 
154 }
155 
156 /** Remember that we read <b>num_bytes</b> bytes in second <b>when</b>.
157  *
158  * Add num_bytes to the current running total for <b>when</b>.
159  *
160  * <b>when</b> can go back to time, but it's safe to ignore calls
161  * earlier than the latest <b>when</b> you've heard of.
162  */
163 void
164 bwhist_note_bytes_written(uint64_t num_bytes, time_t when, bool ipv6)
165 {
166 /* Maybe a circular array for recent seconds, and step to a new point
167  * every time a new second shows up. Or simpler is to just to have
168  * a normal array and push down each item every second; it's short.
169  */
170 /* When a new second has rolled over, compute the sum of the bytes we've
171  * seen over when-1 to when-1-NUM_SECS_ROLLING_MEASURE, and stick it
172  * somewhere. See bwhist_bandwidth_assess() below.
173  */
174  add_obs(write_array, when, num_bytes);
175  if (ipv6)
176  add_obs(write_array_ipv6, when, num_bytes);
177 }
178 
179 /** Remember that we wrote <b>num_bytes</b> bytes in second <b>when</b>.
180  * (like bwhist_note_bytes_written() above)
181  */
182 void
183 bwhist_note_bytes_read(uint64_t num_bytes, time_t when, bool ipv6)
184 {
185 /* if we're smart, we can make this func and the one above share code */
186  add_obs(read_array, when, num_bytes);
187  if (ipv6)
188  add_obs(read_array_ipv6, when, num_bytes);
189 }
190 
191 /** Remember that we wrote <b>num_bytes</b> directory bytes in second
192  * <b>when</b>. (like bwhist_note_bytes_written() above)
193  */
194 void
195 bwhist_note_dir_bytes_written(uint64_t num_bytes, time_t when)
196 {
197  add_obs(dir_write_array, when, num_bytes);
198 }
199 
200 /** Remember that we read <b>num_bytes</b> directory bytes in second
201  * <b>when</b>. (like bwhist_note_bytes_written() above)
202  */
203 void
204 bwhist_note_dir_bytes_read(uint64_t num_bytes, time_t when)
205 {
206  add_obs(dir_read_array, when, num_bytes);
207 }
208 
209 /** Helper: Return the largest value in b->maxima. (This is equal to the
210  * most bandwidth used in any NUM_SECS_ROLLING_MEASURE period for the last
211  * NUM_SECS_BW_SUM_IS_VALID seconds.)
212  */
213 STATIC uint64_t
215 {
216  int i;
217  uint64_t max;
218  max=0;
219  for (i=0; i<NUM_TOTALS; ++i) {
220  if (b->maxima[i]>max)
221  max = b->maxima[i];
222  }
223  return max;
224 }
225 
226 /** Find the largest sums in the past NUM_SECS_BW_SUM_IS_VALID (roughly)
227  * seconds. Find one sum for reading and one for writing. They don't have
228  * to be at the same time.
229  *
230  * Return the smaller of these sums, divided by NUM_SECS_ROLLING_MEASURE.
231  */
232 MOCK_IMPL(int,
234 {
235  uint64_t w,r;
238  if (r>w)
239  return (int)(((double)w)/NUM_SECS_ROLLING_MEASURE);
240  else
241  return (int)(((double)r)/NUM_SECS_ROLLING_MEASURE);
242 }
243 
244 /** Print the bandwidth history of b (either [dir-]read_array or
245  * [dir-]write_array) into the buffer pointed to by buf. The format is
246  * simply comma separated numbers, from oldest to newest.
247  *
248  * It returns the number of bytes written.
249  */
250 STATIC size_t
251 bwhist_fill_bandwidth_history(char *buf, size_t len, const bw_array_t *b)
252 {
253  char *cp = buf;
254  int i, n;
255  const or_options_t *options = get_options();
256  uint64_t cutoff;
257 
258  if (b->num_maxes_set <= b->next_max_idx) {
259  /* We haven't been through the circular array yet; time starts at i=0.*/
260  i = 0;
261  } else {
262  /* We've been around the array at least once. The next i to be
263  overwritten is the oldest. */
264  i = b->next_max_idx;
265  }
266 
267  if (options->RelayBandwidthRate) {
268  /* We don't want to report that we used more bandwidth than the max we're
269  * willing to relay; otherwise everybody will know how much traffic
270  * we used ourself. */
271  cutoff = options->RelayBandwidthRate * NUM_SECS_BW_SUM_INTERVAL;
272  } else {
273  cutoff = UINT64_MAX;
274  }
275 
276  for (n=0; n<b->num_maxes_set; ++n,++i) {
277  uint64_t total;
278  if (i >= NUM_TOTALS)
279  i -= NUM_TOTALS;
280  tor_assert(i < NUM_TOTALS);
281  /* Round the bandwidth used down to the nearest 1k. */
282  total = b->totals[i] & ~0x3ff;
283  if (total > cutoff)
284  total = cutoff;
285 
286  if (n==(b->num_maxes_set-1))
287  tor_snprintf(cp, len-(cp-buf), "%"PRIu64, (total));
288  else
289  tor_snprintf(cp, len-(cp-buf), "%"PRIu64",", (total));
290  cp += strlen(cp);
291  }
292  return cp-buf;
293 }
294 
295 /** Encode a single bandwidth history line into <b>buf</b>. */
296 static void
297 bwhist_get_one_bandwidth_line(buf_t *buf, const char *desc,
298  const bw_array_t *b)
299 {
300  /* [dirreq-](read|write)-history yyyy-mm-dd HH:MM:SS (n s) n,n,n... */
301  /* The n,n,n part above. Largest representation of a uint64_t is 20 chars
302  * long, plus the comma. */
303 #define MAX_HIST_VALUE_LEN (21*NUM_TOTALS)
304 
305  char tmp[MAX_HIST_VALUE_LEN];
306  char end[ISO_TIME_LEN+1];
307 
308  size_t slen = bwhist_fill_bandwidth_history(tmp, MAX_HIST_VALUE_LEN, b);
309  /* If we don't have anything to write, skip to the next entry. */
310  if (slen == 0)
311  return;
312 
314  buf_add_printf(buf, "%s %s (%d s) %s\n",
315  desc, end, NUM_SECS_BW_SUM_INTERVAL, tmp);
316 }
317 
318 /** Allocate and return lines for representing this server's bandwidth
319  * history in its descriptor. We publish these lines in our extra-info
320  * descriptor.
321  */
322 char *
324 {
325  buf_t *buf = buf_new();
326 
327  bwhist_get_one_bandwidth_line(buf, "write-history", write_array);
328  bwhist_get_one_bandwidth_line(buf, "read-history", read_array);
329  bwhist_get_one_bandwidth_line(buf, "ipv6-write-history", write_array_ipv6);
330  bwhist_get_one_bandwidth_line(buf, "ipv6-read-history", read_array_ipv6);
331  bwhist_get_one_bandwidth_line(buf, "dirreq-write-history", dir_write_array);
332  bwhist_get_one_bandwidth_line(buf, "dirreq-read-history", dir_read_array);
333 
334  char *result = buf_extract(buf, NULL);
335  buf_free(buf);
336  return result;
337 }
338 
339 /** Write a single bw_array_t into the Values, Ends, Interval, and Maximum
340  * entries of an or_state_t. Done before writing out a new state file. */
341 static void
343  const bw_array_t *b,
344  smartlist_t **s_values,
345  smartlist_t **s_maxima,
346  time_t *s_begins,
347  int *s_interval)
348 {
349  int i,j;
350  uint64_t maxval;
351 
352  if (*s_values) {
353  SMARTLIST_FOREACH(*s_values, char *, val, tor_free(val));
354  smartlist_free(*s_values);
355  }
356  if (*s_maxima) {
357  SMARTLIST_FOREACH(*s_maxima, char *, val, tor_free(val));
358  smartlist_free(*s_maxima);
359  }
360  if (! server_mode(get_options())) {
361  /* Clients don't need to store bandwidth history persistently;
362  * force these values to the defaults. */
363  /* FFFF we should pull the default out of config.c's state table,
364  * so we don't have two defaults. */
365  if (*s_begins != 0 || *s_interval != 900) {
366  time_t now = time(NULL);
367  time_t save_at = get_options()->AvoidDiskWrites ? now+3600 : now+600;
368  or_state_mark_dirty(state, save_at);
369  }
370  *s_begins = 0;
371  *s_interval = 900;
372  *s_values = smartlist_new();
373  *s_maxima = smartlist_new();
374  return;
375  }
376  *s_begins = b->next_period;
377  *s_interval = NUM_SECS_BW_SUM_INTERVAL;
378 
379  *s_values = smartlist_new();
380  *s_maxima = smartlist_new();
381  /* Set i to first position in circular array */
382  i = (b->num_maxes_set <= b->next_max_idx) ? 0 : b->next_max_idx;
383  for (j=0; j < b->num_maxes_set; ++j,++i) {
384  if (i >= NUM_TOTALS)
385  i = 0;
386  smartlist_add_asprintf(*s_values, "%"PRIu64,
387  (b->totals[i] & ~0x3ff));
388  maxval = b->maxima[i] / NUM_SECS_ROLLING_MEASURE;
389  smartlist_add_asprintf(*s_maxima, "%"PRIu64,
390  (maxval & ~0x3ff));
391  }
392  smartlist_add_asprintf(*s_values, "%"PRIu64,
393  (b->total_in_period & ~0x3ff));
394  maxval = b->max_total / NUM_SECS_ROLLING_MEASURE;
395  smartlist_add_asprintf(*s_maxima, "%"PRIu64,
396  (maxval & ~0x3ff));
397 }
398 
399 /** Update <b>state</b> with the newest bandwidth history. Done before
400  * writing out a new state file. */
401 void
403 {
404 #define UPDATE(arrname,st) \
405  bwhist_update_bwhist_state_section(state,\
406  (arrname),\
407  &state->BWHistory ## st ## Values, \
408  &state->BWHistory ## st ## Maxima, \
409  &state->BWHistory ## st ## Ends, \
410  &state->BWHistory ## st ## Interval)
411 
412  UPDATE(write_array, Write);
413  UPDATE(read_array, Read);
414  UPDATE(write_array_ipv6, IPv6Write);
415  UPDATE(read_array_ipv6, IPv6Read);
416  UPDATE(dir_write_array, DirWrite);
417  UPDATE(dir_read_array, DirRead);
418 
419  if (server_mode(get_options())) {
420  or_state_mark_dirty(state, time(NULL)+(2*3600));
421  }
422 #undef UPDATE
423 }
424 
425 /** Load a single bw_array_t from its Values, Ends, Maxima, and Interval
426  * entries in an or_state_t. Done while reading the state file. */
427 static int
429  const smartlist_t *s_values,
430  const smartlist_t *s_maxima,
431  const time_t s_begins,
432  const int s_interval)
433 {
434  time_t now = time(NULL);
435  int retval = 0;
436  time_t start;
437 
438  uint64_t v, mv;
439  int i,ok,ok_m = 0;
440  int have_maxima = s_maxima && s_values &&
441  (smartlist_len(s_values) == smartlist_len(s_maxima));
442 
443  if (s_values && s_begins >= now - NUM_SECS_BW_SUM_INTERVAL*NUM_TOTALS) {
444  start = s_begins - s_interval*(smartlist_len(s_values));
445  if (start > now)
446  return 0;
447  b->cur_obs_time = start;
449  SMARTLIST_FOREACH_BEGIN(s_values, const char *, cp) {
450  const char *maxstr = NULL;
451  v = tor_parse_uint64(cp, 10, 0, UINT64_MAX, &ok, NULL);
452  if (have_maxima) {
453  maxstr = smartlist_get(s_maxima, cp_sl_idx);
454  mv = tor_parse_uint64(maxstr, 10, 0, UINT64_MAX, &ok_m, NULL);
456  } else {
457  /* No maxima known; guess average rate to be conservative. */
458  mv = (v / s_interval) * NUM_SECS_ROLLING_MEASURE;
459  }
460  if (!ok) {
461  retval = -1;
462  log_notice(LD_HIST, "Could not parse value '%s' into a number.'",cp);
463  }
464  if (maxstr && !ok_m) {
465  retval = -1;
466  log_notice(LD_HIST, "Could not parse maximum '%s' into a number.'",
467  maxstr);
468  }
469 
470  if (start < now) {
471  time_t cur_start = start;
472  time_t actual_interval_len = s_interval;
473  uint64_t cur_val = 0;
474  /* Calculate the average per second. This is the best we can do
475  * because our state file doesn't have per-second resolution. */
476  if (start + s_interval > now)
477  actual_interval_len = now - start;
478  cur_val = v / actual_interval_len;
479  /* This is potentially inefficient, but since we don't do it very
480  * often it should be ok. */
481  while (cur_start < start + actual_interval_len) {
482  add_obs(b, cur_start, cur_val);
483  ++cur_start;
484  }
485  b->max_total = mv;
486  /* This will result in some fairly choppy history if s_interval
487  * is not the same as NUM_SECS_BW_SUM_INTERVAL. XXXX */
488  start += actual_interval_len;
489  }
490  } SMARTLIST_FOREACH_END(cp);
491  }
492 
493  /* Clean up maxima and observed */
494  for (i=0; i<NUM_SECS_ROLLING_MEASURE; ++i) {
495  b->obs[i] = 0;
496  }
497  b->total_obs = 0;
498 
499  return retval;
500 }
501 
502 /** Set bandwidth history from the state file we just loaded. */
503 int
504 bwhist_load_state(or_state_t *state, char **err)
505 {
506  int all_ok = 1;
507 
508  /* Assert they already have been malloced */
512 
513 #define LOAD(arrname,st) \
514  if (bwhist_load_bwhist_state_section( \
515  (arrname), \
516  state->BWHistory ## st ## Values, \
517  state->BWHistory ## st ## Maxima, \
518  state->BWHistory ## st ## Ends, \
519  state->BWHistory ## st ## Interval)<0) \
520  all_ok = 0
521 
522  LOAD(write_array, Write);
523  LOAD(read_array, Read);
524  LOAD(write_array_ipv6, IPv6Write);
525  LOAD(read_array_ipv6, IPv6Read);
526  LOAD(dir_write_array, DirWrite);
527  LOAD(dir_read_array, DirRead);
528 
529 #undef LOAD
530  if (!all_ok) {
531  *err = tor_strdup("Parsing of bandwidth history values failed");
532  /* and create fresh arrays */
533  bwhist_init();
534  return -1;
535  }
536  return 0;
537 }
538 
539 void
540 bwhist_free_all(void)
541 {
542  bw_array_free(read_array);
543  bw_array_free(read_array_ipv6);
544  bw_array_free(write_array);
545  bw_array_free(write_array_ipv6);
546  bw_array_free(dir_read_array);
547  bw_array_free(dir_write_array);
548 }
void buf_add_printf(buf_t *buf, const char *format,...)
Definition: buffers.c:568
buf_t * buf_new(void)
Definition: buffers.c:365
char * buf_extract(buf_t *buf, size_t *sz_out)
Definition: buffers.c:592
Declaration for bw_array_t structure and related constants.
#define NUM_SECS_BW_SUM_INTERVAL
Definition: bw_array_st.h:19
#define NUM_SECS_ROLLING_MEASURE
Definition: bw_array_st.h:17
#define NUM_TOTALS
Definition: bw_array_st.h:23
void bwhist_note_dir_bytes_written(uint64_t num_bytes, time_t when)
Definition: bwhist.c:195
STATIC void commit_max(bw_array_t *b)
Definition: bwhist.c:32
static bw_array_t * write_array_ipv6
Definition: bwhist.c:128
static int bwhist_load_bwhist_state_section(bw_array_t *b, const smartlist_t *s_values, const smartlist_t *s_maxima, const time_t s_begins, const int s_interval)
Definition: bwhist.c:428
char * bwhist_get_bandwidth_lines(void)
Definition: bwhist.c:323
STATIC void bw_array_free_(bw_array_t *b)
Definition: bwhist.c:112
void bwhist_init(void)
Definition: bwhist.c:139
static bw_array_t * dir_read_array
Definition: bwhist.c:131
void bwhist_update_state(or_state_t *state)
Definition: bwhist.c:402
STATIC bw_array_t * write_array
Definition: bwhist.c:126
void bwhist_note_bytes_read(uint64_t num_bytes, time_t when, bool ipv6)
Definition: bwhist.c:183
int bwhist_load_state(or_state_t *state, char **err)
Definition: bwhist.c:504
static bw_array_t * dir_write_array
Definition: bwhist.c:134
static bw_array_t * read_array
Definition: bwhist.c:122
void bwhist_note_dir_bytes_read(uint64_t num_bytes, time_t when)
Definition: bwhist.c:204
void bwhist_note_bytes_written(uint64_t num_bytes, time_t when, bool ipv6)
Definition: bwhist.c:164
static void bwhist_update_bwhist_state_section(or_state_t *state, const bw_array_t *b, smartlist_t **s_values, smartlist_t **s_maxima, time_t *s_begins, int *s_interval)
Definition: bwhist.c:342
STATIC size_t bwhist_fill_bandwidth_history(char *buf, size_t len, const bw_array_t *b)
Definition: bwhist.c:251
static void bwhist_get_one_bandwidth_line(buf_t *buf, const char *desc, const bw_array_t *b)
Definition: bwhist.c:297
static bw_array_t * read_array_ipv6
Definition: bwhist.c:124
int bwhist_bandwidth_assess(void)
Definition: bwhist.c:233
STATIC void advance_obs(bw_array_t *b)
Definition: bwhist.c:52
STATIC uint64_t find_largest_max(bw_array_t *b)
Definition: bwhist.c:214
STATIC void add_obs(bw_array_t *b, time_t when, uint64_t n)
Definition: bwhist.c:78
STATIC bw_array_t * bw_array_new(void)
Definition: bwhist.c:99
Header for feature/stats/bwhist.c.
const or_options_t * get_options(void)
Definition: config.c:919
Header file for config.c.
#define LD_HIST
Definition: log.h:99
#define tor_free(p)
Definition: malloc.h:52
Master header file for Tor-specific functionality.
The or_options_t structure, which represents Tor's configuration.
The or_state_t structure, which represents Tor's state file.
uint64_t tor_parse_uint64(const char *s, int base, uint64_t min, uint64_t max, int *ok, char **next)
Definition: parse_int.c:110
int tor_snprintf(char *str, size_t size, const char *format,...)
Definition: printf.c:27
int server_mode(const or_options_t *options)
Definition: routermode.c:34
Header file for routermode.c.
void smartlist_add_asprintf(struct smartlist_t *sl, const char *pattern,...)
Definition: smartlist.c:36
smartlist_t * smartlist_new(void)
#define SMARTLIST_FOREACH_BEGIN(sl, type, var)
#define SMARTLIST_FOREACH(sl, type, var, cmd)
void or_state_mark_dirty(or_state_t *state, time_t when)
Definition: statefile.c:784
Header for statefile.c.
uint64_t totals[NUM_TOTALS]
Definition: bw_array_st.h:54
int num_maxes_set
Definition: bw_array_st.h:47
uint64_t obs[NUM_SECS_ROLLING_MEASURE]
Definition: bw_array_st.h:31
int cur_obs_idx
Definition: bw_array_st.h:32
uint64_t maxima[NUM_TOTALS]
Definition: bw_array_st.h:51
int next_max_idx
Definition: bw_array_st.h:45
time_t next_period
Definition: bw_array_st.h:42
uint64_t max_total
Definition: bw_array_st.h:36
uint64_t total_obs
Definition: bw_array_st.h:34
time_t cur_obs_time
Definition: bw_array_st.h:33
uint64_t total_in_period
Definition: bw_array_st.h:38
uint64_t RelayBandwidthRate
#define STATIC
Definition: testsupport.h:32
#define MOCK_IMPL(rv, funcname, arglist)
Definition: testsupport.h:133
void format_iso_time(char *buf, time_t t)
Definition: time_fmt.c:295
#define tor_assert(expr)
Definition: util_bug.h:102