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