Line data Source code
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"
24 : #include "feature/relay/routermode.h"
25 :
26 : #include "feature/stats/bw_array_st.h"
27 : #include "app/config/or_state_st.h"
28 : #include "app/config/or_options_st.h"
29 :
30 : /** Shift the current period of b forward by one. */
31 : STATIC void
32 28 : commit_max(bw_array_t *b)
33 : {
34 : /* Store total from current period. */
35 28 : b->totals[b->next_max_idx] = b->total_in_period;
36 : /* Store maximum from current period. */
37 28 : b->maxima[b->next_max_idx++] = b->max_total;
38 : /* Advance next_period and next_max_idx */
39 28 : b->next_period += NUM_SECS_BW_SUM_INTERVAL;
40 28 : if (b->next_max_idx == NUM_TOTALS)
41 5 : b->next_max_idx = 0;
42 28 : if (b->num_maxes_set < NUM_TOTALS)
43 28 : ++b->num_maxes_set;
44 : /* Reset max_total. */
45 28 : b->max_total = 0;
46 : /* Reset total_in_period. */
47 28 : b->total_in_period = 0;
48 28 : }
49 :
50 : /** Shift the current observation time of <b>b</b> forward by one second. */
51 : STATIC void
52 1818090 : advance_obs(bw_array_t *b)
53 : {
54 1818090 : int nextidx;
55 1818090 : uint64_t total;
56 :
57 : /* Calculate the total bandwidth for the last NUM_SECS_ROLLING_MEASURE
58 : * seconds; adjust max_total as needed.*/
59 1818090 : total = b->total_obs + b->obs[b->cur_obs_idx];
60 1818090 : if (total > b->max_total)
61 32 : b->max_total = total;
62 :
63 1818090 : nextidx = b->cur_obs_idx+1;
64 1818090 : if (nextidx == NUM_SECS_ROLLING_MEASURE)
65 181806 : nextidx = 0;
66 :
67 1818090 : b->total_obs = total - b->obs[nextidx];
68 1818090 : b->obs[nextidx]=0;
69 1818090 : b->cur_obs_idx = nextidx;
70 :
71 1818090 : if (++b->cur_obs_time >= b->next_period)
72 22 : commit_max(b);
73 1818090 : }
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 50 : add_obs(bw_array_t *b, time_t when, uint64_t n)
79 : {
80 50 : 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 1818127 : 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 1818078 : advance_obs(b);
91 : }
92 :
93 49 : b->obs[b->cur_obs_idx] += n;
94 49 : b->total_in_period += n;
95 : }
96 :
97 : /** Allocate, initialize, and return a new bw_array. */
98 : STATIC bw_array_t *
99 1474 : bw_array_new(void)
100 : {
101 1474 : bw_array_t *b;
102 1474 : time_t start;
103 1474 : b = tor_malloc_zero(sizeof(bw_array_t));
104 1474 : start = time(NULL);
105 1474 : b->cur_obs_time = start;
106 1474 : b->next_period = start + NUM_SECS_BW_SUM_INTERVAL;
107 1474 : return b;
108 : }
109 :
110 : /** Free storage held by bandwidth array <b>b</b>. */
111 : STATIC void
112 2890 : bw_array_free_(bw_array_t *b)
113 : {
114 2890 : if (!b) {
115 : return;
116 : }
117 :
118 1426 : 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. */
124 : static bw_array_t *read_array_ipv6 = NULL;
125 : /** Recent history of bandwidth observations for (all) write operations. */
126 : STATIC bw_array_t *write_array = NULL;
127 : /** Recent history of bandwidth observations for IPv6 write operations. */
128 : static bw_array_t *write_array_ipv6 = NULL;
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. */
134 : static bw_array_t *dir_write_array = NULL;
135 :
136 : /** Set up structures for bandwidth history, clearing them if they already
137 : * exist. */
138 : void
139 245 : bwhist_init(void)
140 : {
141 245 : bw_array_free(read_array);
142 245 : bw_array_free(read_array_ipv6);
143 245 : bw_array_free(write_array);
144 245 : bw_array_free(write_array_ipv6);
145 245 : bw_array_free(dir_read_array);
146 245 : bw_array_free(dir_write_array);
147 :
148 245 : read_array = bw_array_new();
149 245 : read_array_ipv6 = bw_array_new();
150 245 : write_array = bw_array_new();
151 245 : write_array_ipv6 = bw_array_new();
152 245 : dir_read_array = bw_array_new();
153 245 : dir_write_array = bw_array_new();
154 245 : }
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 28 : 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 28 : add_obs(write_array, when, num_bytes);
175 28 : if (ipv6)
176 0 : add_obs(write_array_ipv6, when, num_bytes);
177 28 : }
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 6 : 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 6 : add_obs(read_array, when, num_bytes);
187 6 : if (ipv6)
188 0 : add_obs(read_array_ipv6, when, num_bytes);
189 6 : }
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 6 : bwhist_note_dir_bytes_written(uint64_t num_bytes, time_t when)
196 : {
197 6 : add_obs(dir_write_array, when, num_bytes);
198 6 : }
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 6 : bwhist_note_dir_bytes_read(uint64_t num_bytes, time_t when)
205 : {
206 6 : add_obs(dir_read_array, when, num_bytes);
207 6 : }
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
214 12 : find_largest_max(bw_array_t *b)
215 : {
216 12 : int i;
217 12 : uint64_t max;
218 12 : max=0;
219 72 : for (i=0; i<NUM_TOTALS; ++i) {
220 60 : if (b->maxima[i]>max)
221 : max = b->maxima[i];
222 : }
223 12 : 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 5 : MOCK_IMPL(int,
233 : bwhist_bandwidth_assess,(void))
234 : {
235 5 : uint64_t w,r;
236 5 : r = find_largest_max(read_array);
237 5 : w = find_largest_max(write_array);
238 5 : if (r>w)
239 0 : return (int)(((double)w)/NUM_SECS_ROLLING_MEASURE);
240 : else
241 5 : 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 50 : bwhist_fill_bandwidth_history(char *buf, size_t len, const bw_array_t *b)
252 : {
253 50 : char *cp = buf;
254 50 : int i, n;
255 50 : const or_options_t *options = get_options();
256 50 : uint64_t cutoff;
257 :
258 50 : 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 7 : i = b->next_max_idx;
265 : }
266 :
267 50 : 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 1 : cutoff = options->RelayBandwidthRate * NUM_SECS_BW_SUM_INTERVAL;
272 : } else {
273 : cutoff = UINT64_MAX;
274 : }
275 :
276 95 : for (n=0; n<b->num_maxes_set; ++n,++i) {
277 45 : uint64_t total;
278 45 : if (i >= NUM_TOTALS)
279 2 : i -= NUM_TOTALS;
280 45 : tor_assert(i < NUM_TOTALS);
281 : /* Round the bandwidth used down to the nearest 1k. */
282 45 : total = b->totals[i] & ~0x3ff;
283 45 : if (total > cutoff)
284 : total = cutoff;
285 :
286 45 : if (n==(b->num_maxes_set-1))
287 11 : tor_snprintf(cp, len-(cp-buf), "%"PRIu64, (total));
288 : else
289 34 : tor_snprintf(cp, len-(cp-buf), "%"PRIu64",", (total));
290 45 : cp += strlen(cp);
291 : }
292 50 : return cp-buf;
293 : }
294 :
295 : /** Encode a single bandwidth history line into <b>buf</b>. */
296 : static void
297 42 : 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 42 : char tmp[MAX_HIST_VALUE_LEN];
306 42 : char end[ISO_TIME_LEN+1];
307 :
308 42 : 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 42 : if (slen == 0)
311 38 : return;
312 :
313 4 : format_iso_time(end, b->next_period-NUM_SECS_BW_SUM_INTERVAL);
314 4 : 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 *
323 7 : bwhist_get_bandwidth_lines(void)
324 : {
325 7 : buf_t *buf = buf_new();
326 :
327 7 : bwhist_get_one_bandwidth_line(buf, "write-history", write_array);
328 7 : bwhist_get_one_bandwidth_line(buf, "read-history", read_array);
329 7 : bwhist_get_one_bandwidth_line(buf, "ipv6-write-history", write_array_ipv6);
330 7 : bwhist_get_one_bandwidth_line(buf, "ipv6-read-history", read_array_ipv6);
331 7 : bwhist_get_one_bandwidth_line(buf, "dirreq-write-history", dir_write_array);
332 7 : bwhist_get_one_bandwidth_line(buf, "dirreq-read-history", dir_read_array);
333 :
334 7 : char *result = buf_extract(buf, NULL);
335 7 : buf_free(buf);
336 7 : 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
342 24 : bwhist_update_bwhist_state_section(or_state_t *state,
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 24 : int i,j;
350 24 : uint64_t maxval;
351 :
352 24 : if (*s_values) {
353 24 : SMARTLIST_FOREACH(*s_values, char *, val, tor_free(val));
354 24 : smartlist_free(*s_values);
355 : }
356 24 : if (*s_maxima) {
357 24 : SMARTLIST_FOREACH(*s_maxima, char *, val, tor_free(val));
358 24 : smartlist_free(*s_maxima);
359 : }
360 24 : 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 0 : if (*s_begins != 0 || *s_interval != 900) {
366 0 : time_t now = time(NULL);
367 0 : time_t save_at = get_options()->AvoidDiskWrites ? now+3600 : now+600;
368 0 : or_state_mark_dirty(state, save_at);
369 : }
370 0 : *s_begins = 0;
371 0 : *s_interval = 900;
372 0 : *s_values = smartlist_new();
373 0 : *s_maxima = smartlist_new();
374 0 : return;
375 : }
376 24 : *s_begins = b->next_period;
377 24 : *s_interval = NUM_SECS_BW_SUM_INTERVAL;
378 :
379 24 : *s_values = smartlist_new();
380 24 : *s_maxima = smartlist_new();
381 : /* Set i to first position in circular array */
382 24 : i = (b->num_maxes_set <= b->next_max_idx) ? 0 : b->next_max_idx;
383 24 : for (j=0; j < b->num_maxes_set; ++j,++i) {
384 0 : if (i >= NUM_TOTALS)
385 0 : i = 0;
386 0 : smartlist_add_asprintf(*s_values, "%"PRIu64,
387 0 : (b->totals[i] & ~0x3ff));
388 0 : maxval = b->maxima[i] / NUM_SECS_ROLLING_MEASURE;
389 0 : smartlist_add_asprintf(*s_maxima, "%"PRIu64,
390 : (maxval & ~0x3ff));
391 : }
392 24 : smartlist_add_asprintf(*s_values, "%"PRIu64,
393 24 : (b->total_in_period & ~0x3ff));
394 24 : maxval = b->max_total / NUM_SECS_ROLLING_MEASURE;
395 24 : 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
402 4 : bwhist_update_state(or_state_t *state)
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 4 : UPDATE(write_array, Write);
413 4 : UPDATE(read_array, Read);
414 4 : UPDATE(write_array_ipv6, IPv6Write);
415 4 : UPDATE(read_array_ipv6, IPv6Read);
416 4 : UPDATE(dir_write_array, DirWrite);
417 4 : UPDATE(dir_read_array, DirRead);
418 :
419 4 : if (server_mode(get_options())) {
420 4 : or_state_mark_dirty(state, time(NULL)+(2*3600));
421 : }
422 : #undef UPDATE
423 4 : }
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
428 24 : bwhist_load_bwhist_state_section(bw_array_t *b,
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 24 : time_t now = time(NULL);
435 24 : int retval = 0;
436 24 : time_t start;
437 :
438 24 : uint64_t v, mv;
439 24 : int i,ok,ok_m = 0;
440 24 : int have_maxima = s_maxima && s_values &&
441 24 : (smartlist_len(s_values) == smartlist_len(s_maxima));
442 :
443 24 : if (s_values && s_begins >= now - NUM_SECS_BW_SUM_INTERVAL*NUM_TOTALS) {
444 0 : start = s_begins - s_interval*(smartlist_len(s_values));
445 0 : if (start > now)
446 : return 0;
447 0 : b->cur_obs_time = start;
448 0 : b->next_period = start + NUM_SECS_BW_SUM_INTERVAL;
449 0 : SMARTLIST_FOREACH_BEGIN(s_values, const char *, cp) {
450 0 : const char *maxstr = NULL;
451 0 : v = tor_parse_uint64(cp, 10, 0, UINT64_MAX, &ok, NULL);
452 0 : if (have_maxima) {
453 0 : maxstr = smartlist_get(s_maxima, cp_sl_idx);
454 0 : mv = tor_parse_uint64(maxstr, 10, 0, UINT64_MAX, &ok_m, NULL);
455 0 : mv *= NUM_SECS_ROLLING_MEASURE;
456 : } else {
457 : /* No maxima known; guess average rate to be conservative. */
458 0 : mv = (v / s_interval) * NUM_SECS_ROLLING_MEASURE;
459 : }
460 0 : if (!ok) {
461 0 : retval = -1;
462 0 : log_notice(LD_HIST, "Could not parse value '%s' into a number.'",cp);
463 : }
464 0 : if (maxstr && !ok_m) {
465 0 : retval = -1;
466 0 : log_notice(LD_HIST, "Could not parse maximum '%s' into a number.'",
467 : maxstr);
468 : }
469 :
470 0 : if (start < now) {
471 0 : time_t cur_start = start;
472 0 : time_t actual_interval_len = s_interval;
473 0 : 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 0 : if (start + s_interval > now)
477 0 : actual_interval_len = now - start;
478 0 : 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 0 : while (cur_start < start + actual_interval_len) {
482 0 : add_obs(b, cur_start, cur_val);
483 0 : ++cur_start;
484 : }
485 0 : 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 0 : start += actual_interval_len;
489 : }
490 0 : } SMARTLIST_FOREACH_END(cp);
491 : }
492 :
493 : /* Clean up maxima and observed */
494 264 : for (i=0; i<NUM_SECS_ROLLING_MEASURE; ++i) {
495 240 : b->obs[i] = 0;
496 : }
497 24 : b->total_obs = 0;
498 :
499 24 : return retval;
500 : }
501 :
502 : /** Set bandwidth history from the state file we just loaded. */
503 : int
504 4 : bwhist_load_state(or_state_t *state, char **err)
505 : {
506 4 : int all_ok = 1;
507 :
508 : /* Assert they already have been malloced */
509 4 : tor_assert(read_array && write_array);
510 4 : tor_assert(read_array_ipv6 && write_array_ipv6);
511 4 : tor_assert(dir_read_array && dir_write_array);
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 4 : LOAD(write_array, Write);
523 4 : LOAD(read_array, Read);
524 4 : LOAD(write_array_ipv6, IPv6Write);
525 4 : LOAD(read_array_ipv6, IPv6Read);
526 4 : LOAD(dir_write_array, DirWrite);
527 4 : LOAD(dir_read_array, DirRead);
528 :
529 : #undef LOAD
530 4 : if (!all_ok) {
531 0 : *err = tor_strdup("Parsing of bandwidth history values failed");
532 : /* and create fresh arrays */
533 0 : bwhist_init();
534 0 : return -1;
535 : }
536 : return 0;
537 : }
538 :
539 : void
540 236 : bwhist_free_all(void)
541 : {
542 236 : bw_array_free(read_array);
543 236 : bw_array_free(read_array_ipv6);
544 236 : bw_array_free(write_array);
545 236 : bw_array_free(write_array_ipv6);
546 236 : bw_array_free(dir_read_array);
547 236 : bw_array_free(dir_write_array);
548 236 : }
|
