Line data Source code
1 : /* * Copyright (c) 2012-2021, The Tor Project, Inc. */
2 : /* See LICENSE for licensing information */
3 :
4 : /**
5 : * \file circuitmux_ewma.c
6 : * \brief EWMA circuit selection as a circuitmux_t policy
7 : *
8 : * The "EWMA" in this module stands for the "exponentially weighted moving
9 : * average" of the number of cells sent on each circuit. The goal is to
10 : * prioritize cells on circuits that have been quiet recently, by looking at
11 : * those that have sent few cells over time, prioritizing recent times
12 : * more than older ones.
13 : *
14 : * Specifically, a cell sent at time "now" has weight 1, but a time X ticks
15 : * before now has weight ewma_scale_factor ^ X , where ewma_scale_factor is
16 : * between 0.0 and 1.0.
17 : *
18 : * For efficiency, we do not re-scale these averages every time we send a
19 : * cell: that would be horribly inefficient. Instead, we we keep the cell
20 : * count on all circuits on the same circuitmux scaled relative to a single
21 : * tick. When we add a new cell, we scale its weight depending on the time
22 : * that has elapsed since the tick. We do re-scale the circuits on the
23 : * circuitmux periodically, so that we don't overflow double.
24 : *
25 : *
26 : * This module should be used through the interfaces in circuitmux.c, which it
27 : * implements.
28 : *
29 : **/
30 :
31 : #define CIRCUITMUX_EWMA_PRIVATE
32 :
33 : #include "orconfig.h"
34 :
35 : #include <math.h>
36 :
37 : #include "core/or/or.h"
38 : #include "core/or/circuitmux.h"
39 : #include "core/or/circuitmux_ewma.h"
40 : #include "lib/crypt_ops/crypto_rand.h"
41 : #include "lib/crypt_ops/crypto_util.h"
42 : #include "feature/nodelist/networkstatus.h"
43 : #include "app/config/or_options_st.h"
44 :
45 : /*** EWMA parameter #defines ***/
46 :
47 : /** How long does a tick last (seconds)? */
48 : #define EWMA_TICK_LEN 10
49 :
50 : /** The default per-tick scale factor, if it hasn't been overridden by a
51 : * consensus or a configuration setting. zero means "disabled". */
52 : #define EWMA_DEFAULT_HALFLIFE 0.0
53 :
54 : /*** Some useful constant #defines ***/
55 :
56 : /** Any halflife smaller than this number of seconds is considered to be
57 : * "disabled". */
58 : #define EPSILON 0.00001
59 : /** The natural logarithm of 0.5. */
60 : #define LOG_ONEHALF -0.69314718055994529
61 :
62 : /*** Static declarations for circuitmux_ewma.c ***/
63 :
64 : static void add_cell_ewma(ewma_policy_data_t *pol, cell_ewma_t *ewma);
65 : static int compare_cell_ewma_counts(const void *p1, const void *p2);
66 : static circuit_t * cell_ewma_to_circuit(cell_ewma_t *ewma);
67 : static inline double get_scale_factor(unsigned from_tick, unsigned to_tick);
68 : static cell_ewma_t * pop_first_cell_ewma(ewma_policy_data_t *pol);
69 : static void remove_cell_ewma(ewma_policy_data_t *pol, cell_ewma_t *ewma);
70 : static void scale_single_cell_ewma(cell_ewma_t *ewma, unsigned cur_tick);
71 : static void scale_active_circuits(ewma_policy_data_t *pol,
72 : unsigned cur_tick);
73 :
74 : /*** Circuitmux policy methods ***/
75 :
76 : static circuitmux_policy_data_t * ewma_alloc_cmux_data(circuitmux_t *cmux);
77 : static void ewma_free_cmux_data(circuitmux_t *cmux,
78 : circuitmux_policy_data_t *pol_data);
79 : static circuitmux_policy_circ_data_t *
80 : ewma_alloc_circ_data(circuitmux_t *cmux, circuitmux_policy_data_t *pol_data,
81 : circuit_t *circ, cell_direction_t direction,
82 : unsigned int cell_count);
83 : static void
84 : ewma_free_circ_data(circuitmux_t *cmux,
85 : circuitmux_policy_data_t *pol_data,
86 : circuit_t *circ,
87 : circuitmux_policy_circ_data_t *pol_circ_data);
88 : static void
89 : ewma_notify_circ_active(circuitmux_t *cmux,
90 : circuitmux_policy_data_t *pol_data,
91 : circuit_t *circ,
92 : circuitmux_policy_circ_data_t *pol_circ_data);
93 : static void
94 : ewma_notify_circ_inactive(circuitmux_t *cmux,
95 : circuitmux_policy_data_t *pol_data,
96 : circuit_t *circ,
97 : circuitmux_policy_circ_data_t *pol_circ_data);
98 : static void
99 : ewma_notify_xmit_cells(circuitmux_t *cmux,
100 : circuitmux_policy_data_t *pol_data,
101 : circuit_t *circ,
102 : circuitmux_policy_circ_data_t *pol_circ_data,
103 : unsigned int n_cells);
104 : static circuit_t *
105 : ewma_pick_active_circuit(circuitmux_t *cmux,
106 : circuitmux_policy_data_t *pol_data);
107 : static int
108 : ewma_cmp_cmux(circuitmux_t *cmux_1, circuitmux_policy_data_t *pol_data_1,
109 : circuitmux_t *cmux_2, circuitmux_policy_data_t *pol_data_2);
110 :
111 : /*** EWMA global variables ***/
112 :
113 : /** The per-tick scale factor to be used when computing cell-count EWMA
114 : * values. (A cell sent N ticks before the start of the current tick
115 : * has value ewma_scale_factor ** N.)
116 : */
117 : static double ewma_scale_factor = 0.1;
118 :
119 : /*** EWMA circuitmux_policy_t method table ***/
120 :
121 : circuitmux_policy_t ewma_policy = {
122 : /*.alloc_cmux_data =*/ ewma_alloc_cmux_data,
123 : /*.free_cmux_data =*/ ewma_free_cmux_data,
124 : /*.alloc_circ_data =*/ ewma_alloc_circ_data,
125 : /*.free_circ_data =*/ ewma_free_circ_data,
126 : /*.notify_circ_active =*/ ewma_notify_circ_active,
127 : /*.notify_circ_inactive =*/ ewma_notify_circ_inactive,
128 : /*.notify_set_n_cells =*/ NULL, /* EWMA doesn't need this */
129 : /*.notify_xmit_cells =*/ ewma_notify_xmit_cells,
130 : /*.pick_active_circuit =*/ ewma_pick_active_circuit,
131 : /*.cmp_cmux =*/ ewma_cmp_cmux
132 : };
133 :
134 : /** Have we initialized the ewma tick-counting logic? */
135 : static int ewma_ticks_initialized = 0;
136 : /** At what monotime_coarse_t did the current tick begin? */
137 : static monotime_coarse_t start_of_current_tick;
138 : /** What is the number of the current tick? */
139 : static unsigned current_tick_num;
140 :
141 : /*** EWMA method implementations using the below EWMA helper functions ***/
142 :
143 : /** Compute and return the current cell_ewma tick. */
144 : static inline unsigned int
145 213 : cell_ewma_get_tick(void)
146 : {
147 213 : monotime_coarse_t now;
148 213 : monotime_coarse_get(&now);
149 213 : int32_t msec_diff = monotime_coarse_diff_msec32(&start_of_current_tick,
150 : &now);
151 213 : return current_tick_num + msec_diff / (1000*EWMA_TICK_LEN);
152 : }
153 :
154 : /**
155 : * Allocate an ewma_policy_data_t and upcast it to a circuitmux_policy_data_t;
156 : * this is called when setting the policy on a circuitmux_t to ewma_policy.
157 : */
158 :
159 : static circuitmux_policy_data_t *
160 192 : ewma_alloc_cmux_data(circuitmux_t *cmux)
161 : {
162 192 : ewma_policy_data_t *pol = NULL;
163 :
164 192 : tor_assert(cmux);
165 :
166 192 : pol = tor_malloc_zero(sizeof(*pol));
167 192 : pol->base_.magic = EWMA_POL_DATA_MAGIC;
168 192 : pol->active_circuit_pqueue = smartlist_new();
169 192 : pol->active_circuit_pqueue_last_recalibrated = cell_ewma_get_tick();
170 :
171 192 : return TO_CMUX_POL_DATA(pol);
172 : }
173 :
174 : /**
175 : * Free an ewma_policy_data_t allocated with ewma_alloc_cmux_data()
176 : */
177 :
178 : static void
179 192 : ewma_free_cmux_data(circuitmux_t *cmux,
180 : circuitmux_policy_data_t *pol_data)
181 : {
182 192 : ewma_policy_data_t *pol = NULL;
183 :
184 192 : tor_assert(cmux);
185 192 : if (!pol_data) return;
186 :
187 192 : pol = TO_EWMA_POL_DATA(pol_data);
188 :
189 192 : smartlist_free(pol->active_circuit_pqueue);
190 192 : memwipe(pol, 0xda, sizeof(ewma_policy_data_t));
191 192 : tor_free(pol);
192 : }
193 :
194 : /**
195 : * Allocate an ewma_policy_circ_data_t and upcast it to a
196 : * circuitmux_policy_data_t; this is called when attaching a circuit to a
197 : * circuitmux_t with ewma_policy.
198 : */
199 :
200 : static circuitmux_policy_circ_data_t *
201 21 : ewma_alloc_circ_data(circuitmux_t *cmux,
202 : circuitmux_policy_data_t *pol_data,
203 : circuit_t *circ,
204 : cell_direction_t direction,
205 : unsigned int cell_count)
206 : {
207 21 : ewma_policy_circ_data_t *cdata = NULL;
208 :
209 21 : tor_assert(cmux);
210 21 : tor_assert(pol_data);
211 21 : tor_assert(circ);
212 21 : tor_assert(direction == CELL_DIRECTION_OUT ||
213 : direction == CELL_DIRECTION_IN);
214 : /* Shut the compiler up without triggering -Wtautological-compare */
215 21 : (void)cell_count;
216 :
217 21 : cdata = tor_malloc_zero(sizeof(*cdata));
218 21 : cdata->base_.magic = EWMA_POL_CIRC_DATA_MAGIC;
219 21 : cdata->circ = circ;
220 :
221 : /*
222 : * Initialize the cell_ewma_t structure (formerly in
223 : * init_circuit_base())
224 : */
225 21 : cdata->cell_ewma.last_adjusted_tick = cell_ewma_get_tick();
226 21 : cdata->cell_ewma.cell_count = 0.0;
227 21 : cdata->cell_ewma.heap_index = -1;
228 21 : if (direction == CELL_DIRECTION_IN) {
229 9 : cdata->cell_ewma.is_for_p_chan = 1;
230 : } else {
231 12 : cdata->cell_ewma.is_for_p_chan = 0;
232 : }
233 :
234 21 : return TO_CMUX_POL_CIRC_DATA(cdata);
235 : }
236 :
237 : /**
238 : * Free an ewma_policy_circ_data_t allocated with ewma_alloc_circ_data()
239 : */
240 :
241 : static void
242 21 : ewma_free_circ_data(circuitmux_t *cmux,
243 : circuitmux_policy_data_t *pol_data,
244 : circuit_t *circ,
245 : circuitmux_policy_circ_data_t *pol_circ_data)
246 :
247 : {
248 21 : ewma_policy_circ_data_t *cdata = NULL;
249 :
250 21 : tor_assert(cmux);
251 21 : tor_assert(circ);
252 21 : tor_assert(pol_data);
253 :
254 21 : if (!pol_circ_data) return;
255 :
256 21 : cdata = TO_EWMA_POL_CIRC_DATA(pol_circ_data);
257 21 : memwipe(cdata, 0xdc, sizeof(ewma_policy_circ_data_t));
258 21 : tor_free(cdata);
259 : }
260 :
261 : /**
262 : * Handle circuit activation; this inserts the circuit's cell_ewma into
263 : * the active_circuits_pqueue.
264 : */
265 :
266 : static void
267 16 : ewma_notify_circ_active(circuitmux_t *cmux,
268 : circuitmux_policy_data_t *pol_data,
269 : circuit_t *circ,
270 : circuitmux_policy_circ_data_t *pol_circ_data)
271 : {
272 16 : ewma_policy_data_t *pol = NULL;
273 16 : ewma_policy_circ_data_t *cdata = NULL;
274 :
275 16 : tor_assert(cmux);
276 16 : tor_assert(pol_data);
277 16 : tor_assert(circ);
278 16 : tor_assert(pol_circ_data);
279 :
280 16 : pol = TO_EWMA_POL_DATA(pol_data);
281 16 : cdata = TO_EWMA_POL_CIRC_DATA(pol_circ_data);
282 :
283 16 : add_cell_ewma(pol, &(cdata->cell_ewma));
284 16 : }
285 :
286 : /**
287 : * Handle circuit deactivation; this removes the circuit's cell_ewma from
288 : * the active_circuits_pqueue.
289 : */
290 :
291 : static void
292 14 : ewma_notify_circ_inactive(circuitmux_t *cmux,
293 : circuitmux_policy_data_t *pol_data,
294 : circuit_t *circ,
295 : circuitmux_policy_circ_data_t *pol_circ_data)
296 : {
297 14 : ewma_policy_data_t *pol = NULL;
298 14 : ewma_policy_circ_data_t *cdata = NULL;
299 :
300 14 : tor_assert(cmux);
301 14 : tor_assert(pol_data);
302 14 : tor_assert(circ);
303 14 : tor_assert(pol_circ_data);
304 :
305 14 : pol = TO_EWMA_POL_DATA(pol_data);
306 14 : cdata = TO_EWMA_POL_CIRC_DATA(pol_circ_data);
307 :
308 14 : remove_cell_ewma(pol, &(cdata->cell_ewma));
309 14 : }
310 :
311 : /**
312 : * Update cell_ewma for this circuit after we've sent some cells, and
313 : * remove/reinsert it in the queue. This used to be done (brokenly,
314 : * see bug 6816) in channel_flush_from_first_active_circuit().
315 : */
316 :
317 : static void
318 5 : ewma_notify_xmit_cells(circuitmux_t *cmux,
319 : circuitmux_policy_data_t *pol_data,
320 : circuit_t *circ,
321 : circuitmux_policy_circ_data_t *pol_circ_data,
322 : unsigned int n_cells)
323 : {
324 5 : ewma_policy_data_t *pol = NULL;
325 5 : ewma_policy_circ_data_t *cdata = NULL;
326 5 : unsigned int tick;
327 5 : double fractional_tick, ewma_increment;
328 5 : cell_ewma_t *cell_ewma, *tmp;
329 :
330 5 : tor_assert(cmux);
331 5 : tor_assert(pol_data);
332 5 : tor_assert(circ);
333 5 : tor_assert(pol_circ_data);
334 5 : tor_assert(n_cells > 0);
335 :
336 5 : pol = TO_EWMA_POL_DATA(pol_data);
337 5 : cdata = TO_EWMA_POL_CIRC_DATA(pol_circ_data);
338 :
339 : /* Rescale the EWMAs if needed */
340 5 : tick = cell_ewma_get_current_tick_and_fraction(&fractional_tick);
341 :
342 5 : if (tick != pol->active_circuit_pqueue_last_recalibrated) {
343 1 : scale_active_circuits(pol, tick);
344 : }
345 :
346 : /* How much do we adjust the cell count in cell_ewma by? */
347 5 : ewma_increment =
348 5 : ((double)(n_cells)) * pow(ewma_scale_factor, -fractional_tick);
349 :
350 : /* Do the adjustment */
351 5 : cell_ewma = &(cdata->cell_ewma);
352 5 : cell_ewma->cell_count += ewma_increment;
353 :
354 : /*
355 : * Since we just sent on this circuit, it should be at the head of
356 : * the queue. Pop the head, assert that it matches, then re-add.
357 : */
358 5 : tmp = pop_first_cell_ewma(pol);
359 5 : tor_assert(tmp == cell_ewma);
360 5 : add_cell_ewma(pol, cell_ewma);
361 5 : }
362 :
363 : /**
364 : * Pick the preferred circuit to send from; this will be the one with
365 : * the lowest EWMA value in the priority queue. This used to be done
366 : * in channel_flush_from_first_active_circuit().
367 : */
368 :
369 : static circuit_t *
370 3 : ewma_pick_active_circuit(circuitmux_t *cmux,
371 : circuitmux_policy_data_t *pol_data)
372 : {
373 3 : ewma_policy_data_t *pol = NULL;
374 3 : circuit_t *circ = NULL;
375 3 : cell_ewma_t *cell_ewma = NULL;
376 :
377 3 : tor_assert(cmux);
378 3 : tor_assert(pol_data);
379 :
380 3 : pol = TO_EWMA_POL_DATA(pol_data);
381 :
382 3 : if (smartlist_len(pol->active_circuit_pqueue) > 0) {
383 : /* Get the head of the queue */
384 3 : cell_ewma = smartlist_get(pol->active_circuit_pqueue, 0);
385 3 : circ = cell_ewma_to_circuit(cell_ewma);
386 : }
387 :
388 3 : return circ;
389 : }
390 :
391 : /**
392 : * Compare two EWMA cmuxes, and return -1, 0 or 1 to indicate which should
393 : * be more preferred - see circuitmux_compare_muxes() of circuitmux.c.
394 : */
395 :
396 : static int
397 20 : ewma_cmp_cmux(circuitmux_t *cmux_1, circuitmux_policy_data_t *pol_data_1,
398 : circuitmux_t *cmux_2, circuitmux_policy_data_t *pol_data_2)
399 : {
400 20 : ewma_policy_data_t *p1 = NULL, *p2 = NULL;
401 20 : cell_ewma_t *ce1 = NULL, *ce2 = NULL;
402 :
403 20 : tor_assert(cmux_1);
404 20 : tor_assert(pol_data_1);
405 20 : tor_assert(cmux_2);
406 20 : tor_assert(pol_data_2);
407 :
408 20 : p1 = TO_EWMA_POL_DATA(pol_data_1);
409 20 : p2 = TO_EWMA_POL_DATA(pol_data_2);
410 :
411 20 : if (p1 != p2) {
412 : /* Get the head cell_ewma_t from each queue */
413 20 : if (smartlist_len(p1->active_circuit_pqueue) > 0) {
414 0 : ce1 = smartlist_get(p1->active_circuit_pqueue, 0);
415 : }
416 :
417 20 : if (smartlist_len(p2->active_circuit_pqueue) > 0) {
418 0 : ce2 = smartlist_get(p2->active_circuit_pqueue, 0);
419 : }
420 :
421 : /* Got both of them? */
422 20 : if (ce1 != NULL && ce2 != NULL) {
423 : /* Pick whichever one has the better best circuit */
424 0 : return compare_cell_ewma_counts(ce1, ce2);
425 : } else {
426 20 : if (ce1 != NULL) {
427 : /* We only have a circuit on cmux_1, so prefer it */
428 : return -1;
429 20 : } else if (ce2 != NULL) {
430 : /* We only have a circuit on cmux_2, so prefer it */
431 : return 1;
432 : } else {
433 : /* No circuits at all; no preference */
434 20 : return 0;
435 : }
436 : }
437 : } else {
438 : /* We got identical params */
439 : return 0;
440 : }
441 : }
442 :
443 : /** Helper for sorting cell_ewma_t values in their priority queue. */
444 : static int
445 0 : compare_cell_ewma_counts(const void *p1, const void *p2)
446 : {
447 0 : const cell_ewma_t *e1 = p1, *e2 = p2;
448 :
449 0 : if (e1->cell_count < e2->cell_count)
450 : return -1;
451 0 : else if (e1->cell_count > e2->cell_count)
452 : return 1;
453 : else
454 0 : return 0;
455 : }
456 :
457 : /** Given a cell_ewma_t, return a pointer to the circuit containing it. */
458 : static circuit_t *
459 3 : cell_ewma_to_circuit(cell_ewma_t *ewma)
460 : {
461 3 : ewma_policy_circ_data_t *cdata = NULL;
462 :
463 3 : tor_assert(ewma);
464 3 : cdata = SUBTYPE_P(ewma, ewma_policy_circ_data_t, cell_ewma);
465 3 : tor_assert(cdata);
466 :
467 3 : return cdata->circ;
468 : }
469 :
470 : /* ==== Functions for scaling cell_ewma_t ====
471 :
472 : When choosing which cells to relay first, we favor circuits that have been
473 : quiet recently. This gives better latency on connections that aren't
474 : pushing lots of data, and makes the network feel more interactive.
475 :
476 : Conceptually, we take an exponentially weighted mean average of the number
477 : of cells a circuit has sent, and allow active circuits (those with cells to
478 : relay) to send cells in reverse order of their exponentially-weighted mean
479 : average (EWMA) cell count. [That is, a cell sent N seconds ago 'counts'
480 : F^N times as much as a cell sent now, for 0<F<1.0, and we favor the
481 : circuit that has sent the fewest cells]
482 :
483 : If 'double' had infinite precision, we could do this simply by counting a
484 : cell sent at startup as having weight 1.0, and a cell sent N seconds later
485 : as having weight F^-N. This way, we would never need to re-scale
486 : any already-sent cells.
487 :
488 : To prevent double from overflowing, we could count a cell sent now as
489 : having weight 1.0 and a cell sent N seconds ago as having weight F^N.
490 : This, however, would mean we'd need to re-scale *ALL* old circuits every
491 : time we wanted to send a cell.
492 :
493 : So as a compromise, we divide time into 'ticks' (currently, 10-second
494 : increments) and say that a cell sent at the start of a current tick is
495 : worth 1.0, a cell sent N seconds before the start of the current tick is
496 : worth F^N, and a cell sent N seconds after the start of the current tick is
497 : worth F^-N. This way we don't overflow, and we don't need to constantly
498 : rescale.
499 : */
500 :
501 : /**
502 : * Initialize the system that tells which ewma tick we are in.
503 : */
504 : STATIC void
505 29 : cell_ewma_initialize_ticks(void)
506 : {
507 29 : if (ewma_ticks_initialized)
508 : return;
509 24 : monotime_coarse_get(&start_of_current_tick);
510 24 : crypto_rand((char*)¤t_tick_num, sizeof(current_tick_num));
511 24 : ewma_ticks_initialized = 1;
512 : }
513 :
514 : /** Compute the current cell_ewma tick and the fraction of the tick that has
515 : * elapsed between the start of the tick and the current time. Return the
516 : * former and store the latter in *<b>remainder_out</b>.
517 : *
518 : * These tick values are not meant to be shared between Tor instances, or used
519 : * for other purposes. */
520 : STATIC unsigned
521 8 : cell_ewma_get_current_tick_and_fraction(double *remainder_out)
522 : {
523 8 : if (BUG(!ewma_ticks_initialized)) {
524 : cell_ewma_initialize_ticks(); // LCOV_EXCL_LINE
525 : }
526 8 : monotime_coarse_t now;
527 8 : monotime_coarse_get(&now);
528 8 : int32_t msec_diff = monotime_coarse_diff_msec32(&start_of_current_tick,
529 : &now);
530 8 : if (msec_diff > (1000*EWMA_TICK_LEN)) {
531 1 : unsigned ticks_difference = msec_diff / (1000*EWMA_TICK_LEN);
532 1 : monotime_coarse_add_msec(&start_of_current_tick,
533 : &start_of_current_tick,
534 : ticks_difference * 1000 * EWMA_TICK_LEN);
535 1 : current_tick_num += ticks_difference;
536 1 : msec_diff %= 1000*EWMA_TICK_LEN;
537 : }
538 8 : *remainder_out = ((double)msec_diff) / (1.0e3 * EWMA_TICK_LEN);
539 8 : return current_tick_num;
540 : }
541 :
542 : /* Default value for the CircuitPriorityHalflifeMsec consensus parameter in
543 : * msec. */
544 : #define CMUX_PRIORITY_HALFLIFE_MSEC_DEFAULT 30000
545 : /* Minimum and maximum value for the CircuitPriorityHalflifeMsec consensus
546 : * parameter. */
547 : #define CMUX_PRIORITY_HALFLIFE_MSEC_MIN 1
548 : #define CMUX_PRIORITY_HALFLIFE_MSEC_MAX INT32_MAX
549 :
550 : /* Return the value of the circuit priority halflife from the options if
551 : * available or else from the consensus (in that order). If none can be found,
552 : * a default value is returned.
553 : *
554 : * The source_msg points to a string describing from where the value was
555 : * picked so it can be used for logging. */
556 : static double
557 15 : get_circuit_priority_halflife(const or_options_t *options,
558 : const networkstatus_t *consensus,
559 : const char **source_msg)
560 : {
561 15 : int32_t halflife_ms;
562 15 : double halflife;
563 : /* Compute the default value now. We might need it. */
564 15 : double halflife_default =
565 : ((double) CMUX_PRIORITY_HALFLIFE_MSEC_DEFAULT) / 1000.0;
566 :
567 : /* Try to get it from configuration file first. */
568 15 : if (options && options->CircuitPriorityHalflife >= -EPSILON) {
569 0 : halflife = options->CircuitPriorityHalflife;
570 0 : *source_msg = "CircuitPriorityHalflife in configuration";
571 0 : goto end;
572 : }
573 :
574 : /* Try to get the msec value from the consensus. */
575 15 : halflife_ms = networkstatus_get_param(consensus,
576 : "CircuitPriorityHalflifeMsec",
577 : CMUX_PRIORITY_HALFLIFE_MSEC_DEFAULT,
578 : CMUX_PRIORITY_HALFLIFE_MSEC_MIN,
579 : CMUX_PRIORITY_HALFLIFE_MSEC_MAX);
580 15 : halflife = ((double) halflife_ms) / 1000.0;
581 15 : *source_msg = "CircuitPriorityHalflifeMsec in consensus";
582 :
583 15 : end:
584 : /* We should never go below the EPSILON else we would consider it disabled
585 : * and we can't have that. */
586 15 : if (halflife < EPSILON) {
587 0 : log_warn(LD_CONFIG, "CircuitPriorityHalflife is too small (%f). "
588 : "Adjusting to the smallest value allowed: %f.",
589 : halflife, halflife_default);
590 0 : halflife = halflife_default;
591 : }
592 15 : return halflife;
593 : }
594 :
595 : /** Adjust the global cell scale factor based on <b>options</b> */
596 : void
597 15 : cmux_ewma_set_options(const or_options_t *options,
598 : const networkstatus_t *consensus)
599 : {
600 15 : double halflife;
601 15 : const char *source;
602 :
603 15 : cell_ewma_initialize_ticks();
604 :
605 : /* Both options and consensus can be NULL. This assures us to either get a
606 : * valid configured value or the default one. */
607 15 : halflife = get_circuit_priority_halflife(options, consensus, &source);
608 :
609 : /* convert halflife into halflife-per-tick. */
610 15 : halflife /= EWMA_TICK_LEN;
611 : /* compute per-tick scale factor. */
612 15 : ewma_scale_factor = exp(LOG_ONEHALF / halflife);
613 15 : log_info(LD_OR,
614 : "Enabled cell_ewma algorithm because of value in %s; "
615 : "scale factor is %f per %d seconds",
616 : source, ewma_scale_factor, EWMA_TICK_LEN);
617 15 : }
618 :
619 : /** Return the multiplier necessary to convert the value of a cell sent in
620 : * 'from_tick' to one sent in 'to_tick'. */
621 : static inline double
622 22 : get_scale_factor(unsigned from_tick, unsigned to_tick)
623 : {
624 : /* This math can wrap around, but that's okay: unsigned overflow is
625 : well-defined */
626 22 : int diff = (int)(to_tick - from_tick);
627 22 : return pow(ewma_scale_factor, diff);
628 : }
629 :
630 : /** Adjust the cell count of <b>ewma</b> so that it is scaled with respect to
631 : * <b>cur_tick</b> */
632 : static void
633 21 : scale_single_cell_ewma(cell_ewma_t *ewma, unsigned cur_tick)
634 : {
635 21 : double factor = get_scale_factor(ewma->last_adjusted_tick, cur_tick);
636 21 : ewma->cell_count *= factor;
637 21 : ewma->last_adjusted_tick = cur_tick;
638 21 : }
639 :
640 : /** Adjust the cell count of every active circuit on <b>chan</b> so
641 : * that they are scaled with respect to <b>cur_tick</b> */
642 : static void
643 1 : scale_active_circuits(ewma_policy_data_t *pol, unsigned cur_tick)
644 : {
645 1 : double factor;
646 :
647 1 : tor_assert(pol);
648 1 : tor_assert(pol->active_circuit_pqueue);
649 :
650 1 : factor =
651 1 : get_scale_factor(
652 : pol->active_circuit_pqueue_last_recalibrated,
653 : cur_tick);
654 : /** Ordinarily it isn't okay to change the value of an element in a heap,
655 : * but it's okay here, since we are preserving the order. */
656 2 : SMARTLIST_FOREACH_BEGIN(
657 : pol->active_circuit_pqueue,
658 : cell_ewma_t *, e) {
659 1 : tor_assert(e->last_adjusted_tick ==
660 : pol->active_circuit_pqueue_last_recalibrated);
661 1 : e->cell_count *= factor;
662 1 : e->last_adjusted_tick = cur_tick;
663 1 : } SMARTLIST_FOREACH_END(e);
664 1 : pol->active_circuit_pqueue_last_recalibrated = cur_tick;
665 1 : }
666 :
667 : /** Rescale <b>ewma</b> to the same scale as <b>pol</b>, and add it to
668 : * <b>pol</b>'s priority queue of active circuits */
669 : static void
670 21 : add_cell_ewma(ewma_policy_data_t *pol, cell_ewma_t *ewma)
671 : {
672 21 : tor_assert(pol);
673 21 : tor_assert(pol->active_circuit_pqueue);
674 21 : tor_assert(ewma);
675 21 : tor_assert(ewma->heap_index == -1);
676 :
677 21 : scale_single_cell_ewma(
678 : ewma,
679 : pol->active_circuit_pqueue_last_recalibrated);
680 :
681 21 : smartlist_pqueue_add(pol->active_circuit_pqueue,
682 : compare_cell_ewma_counts,
683 : offsetof(cell_ewma_t, heap_index),
684 : ewma);
685 21 : }
686 :
687 : /** Remove <b>ewma</b> from <b>pol</b>'s priority queue of active circuits */
688 : static void
689 14 : remove_cell_ewma(ewma_policy_data_t *pol, cell_ewma_t *ewma)
690 : {
691 14 : tor_assert(pol);
692 14 : tor_assert(pol->active_circuit_pqueue);
693 14 : tor_assert(ewma);
694 14 : tor_assert(ewma->heap_index != -1);
695 :
696 14 : smartlist_pqueue_remove(pol->active_circuit_pqueue,
697 : compare_cell_ewma_counts,
698 : offsetof(cell_ewma_t, heap_index),
699 : ewma);
700 14 : }
701 :
702 : /** Remove and return the first cell_ewma_t from pol's priority queue of
703 : * active circuits. Requires that the priority queue is nonempty. */
704 : static cell_ewma_t *
705 5 : pop_first_cell_ewma(ewma_policy_data_t *pol)
706 : {
707 5 : tor_assert(pol);
708 5 : tor_assert(pol->active_circuit_pqueue);
709 :
710 5 : return smartlist_pqueue_pop(pol->active_circuit_pqueue,
711 : compare_cell_ewma_counts,
712 : offsetof(cell_ewma_t, heap_index));
713 : }
714 :
715 : /**
716 : * Drop all resources held by circuitmux_ewma.c, and deinitialize the
717 : * module. */
718 : void
719 249 : circuitmux_ewma_free_all(void)
720 : {
721 249 : ewma_ticks_initialized = 0;
722 249 : }
|
