Tor  0.4.4.0-alpha-dev
circuitmux_ewma.c
Go to the documentation of this file.
1 /* * Copyright (c) 2012-2020, 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 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);
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
146 {
147  monotime_coarse_t now;
148  monotime_coarse_get(&now);
150  &now);
151  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 
160 ewma_alloc_cmux_data(circuitmux_t *cmux)
161 {
162  ewma_policy_data_t *pol = NULL;
163 
164  tor_assert(cmux);
165 
166  pol = tor_malloc_zero(sizeof(*pol));
167  pol->base_.magic = EWMA_POL_DATA_MAGIC;
168  pol->active_circuit_pqueue = smartlist_new();
169  pol->active_circuit_pqueue_last_recalibrated = cell_ewma_get_tick();
170 
171  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 ewma_free_cmux_data(circuitmux_t *cmux,
180  circuitmux_policy_data_t *pol_data)
181 {
182  ewma_policy_data_t *pol = NULL;
183 
184  tor_assert(cmux);
185  if (!pol_data) return;
186 
187  pol = TO_EWMA_POL_DATA(pol_data);
188 
189  smartlist_free(pol->active_circuit_pqueue);
190  memwipe(pol, 0xda, sizeof(ewma_policy_data_t));
191  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 
201 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  ewma_policy_circ_data_t *cdata = NULL;
208 
209  tor_assert(cmux);
210  tor_assert(pol_data);
211  tor_assert(circ);
212  tor_assert(direction == CELL_DIRECTION_OUT ||
213  direction == CELL_DIRECTION_IN);
214  /* Shut the compiler up without triggering -Wtautological-compare */
215  (void)cell_count;
216 
217  cdata = tor_malloc_zero(sizeof(*cdata));
218  cdata->base_.magic = EWMA_POL_CIRC_DATA_MAGIC;
219  cdata->circ = circ;
220 
221  /*
222  * Initialize the cell_ewma_t structure (formerly in
223  * init_circuit_base())
224  */
225  cdata->cell_ewma.last_adjusted_tick = cell_ewma_get_tick();
226  cdata->cell_ewma.cell_count = 0.0;
227  cdata->cell_ewma.heap_index = -1;
228  if (direction == CELL_DIRECTION_IN) {
229  cdata->cell_ewma.is_for_p_chan = 1;
230  } else {
231  cdata->cell_ewma.is_for_p_chan = 0;
232  }
233 
234  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 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  ewma_policy_circ_data_t *cdata = NULL;
249 
250  tor_assert(cmux);
251  tor_assert(circ);
252  tor_assert(pol_data);
253 
254  if (!pol_circ_data) return;
255 
256  cdata = TO_EWMA_POL_CIRC_DATA(pol_circ_data);
257  memwipe(cdata, 0xdc, sizeof(ewma_policy_circ_data_t));
258  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 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  ewma_policy_data_t *pol = NULL;
273  ewma_policy_circ_data_t *cdata = NULL;
274 
275  tor_assert(cmux);
276  tor_assert(pol_data);
277  tor_assert(circ);
278  tor_assert(pol_circ_data);
279 
280  pol = TO_EWMA_POL_DATA(pol_data);
281  cdata = TO_EWMA_POL_CIRC_DATA(pol_circ_data);
282 
283  add_cell_ewma(pol, &(cdata->cell_ewma));
284 }
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 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  ewma_policy_data_t *pol = NULL;
298  ewma_policy_circ_data_t *cdata = NULL;
299 
300  tor_assert(cmux);
301  tor_assert(pol_data);
302  tor_assert(circ);
303  tor_assert(pol_circ_data);
304 
305  pol = TO_EWMA_POL_DATA(pol_data);
306  cdata = TO_EWMA_POL_CIRC_DATA(pol_circ_data);
307 
308  remove_cell_ewma(pol, &(cdata->cell_ewma));
309 }
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 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  ewma_policy_data_t *pol = NULL;
325  ewma_policy_circ_data_t *cdata = NULL;
326  unsigned int tick;
327  double fractional_tick, ewma_increment;
328  cell_ewma_t *cell_ewma, *tmp;
329 
330  tor_assert(cmux);
331  tor_assert(pol_data);
332  tor_assert(circ);
333  tor_assert(pol_circ_data);
334  tor_assert(n_cells > 0);
335 
336  pol = TO_EWMA_POL_DATA(pol_data);
337  cdata = TO_EWMA_POL_CIRC_DATA(pol_circ_data);
338 
339  /* Rescale the EWMAs if needed */
340  tick = cell_ewma_get_current_tick_and_fraction(&fractional_tick);
341 
342  if (tick != pol->active_circuit_pqueue_last_recalibrated) {
343  scale_active_circuits(pol, tick);
344  }
345 
346  /* How much do we adjust the cell count in cell_ewma by? */
347  ewma_increment =
348  ((double)(n_cells)) * pow(ewma_scale_factor, -fractional_tick);
349 
350  /* Do the adjustment */
351  cell_ewma = &(cdata->cell_ewma);
352  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  tmp = pop_first_cell_ewma(pol);
359  tor_assert(tmp == cell_ewma);
360  add_cell_ewma(pol, cell_ewma);
361 }
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 ewma_pick_active_circuit(circuitmux_t *cmux,
371  circuitmux_policy_data_t *pol_data)
372 {
373  ewma_policy_data_t *pol = NULL;
374  circuit_t *circ = NULL;
375  cell_ewma_t *cell_ewma = NULL;
376 
377  tor_assert(cmux);
378  tor_assert(pol_data);
379 
380  pol = TO_EWMA_POL_DATA(pol_data);
381 
382  if (smartlist_len(pol->active_circuit_pqueue) > 0) {
383  /* Get the head of the queue */
384  cell_ewma = smartlist_get(pol->active_circuit_pqueue, 0);
385  circ = cell_ewma_to_circuit(cell_ewma);
386  }
387 
388  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 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  ewma_policy_data_t *p1 = NULL, *p2 = NULL;
401  cell_ewma_t *ce1 = NULL, *ce2 = NULL;
402 
403  tor_assert(cmux_1);
404  tor_assert(pol_data_1);
405  tor_assert(cmux_2);
406  tor_assert(pol_data_2);
407 
408  p1 = TO_EWMA_POL_DATA(pol_data_1);
409  p2 = TO_EWMA_POL_DATA(pol_data_2);
410 
411  if (p1 != p2) {
412  /* Get the head cell_ewma_t from each queue */
413  if (smartlist_len(p1->active_circuit_pqueue) > 0) {
414  ce1 = smartlist_get(p1->active_circuit_pqueue, 0);
415  }
416 
417  if (smartlist_len(p2->active_circuit_pqueue) > 0) {
418  ce2 = smartlist_get(p2->active_circuit_pqueue, 0);
419  }
420 
421  /* Got both of them? */
422  if (ce1 != NULL && ce2 != NULL) {
423  /* Pick whichever one has the better best circuit */
424  return compare_cell_ewma_counts(ce1, ce2);
425  } else {
426  if (ce1 != NULL) {
427  /* We only have a circuit on cmux_1, so prefer it */
428  return -1;
429  } 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  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 compare_cell_ewma_counts(const void *p1, const void *p2)
446 {
447  const cell_ewma_t *e1 = p1, *e2 = p2;
448 
449  if (e1->cell_count < e2->cell_count)
450  return -1;
451  else if (e1->cell_count > e2->cell_count)
452  return 1;
453  else
454  return 0;
455 }
456 
457 /** Given a cell_ewma_t, return a pointer to the circuit containing it. */
458 static circuit_t *
459 cell_ewma_to_circuit(cell_ewma_t *ewma)
460 {
461  ewma_policy_circ_data_t *cdata = NULL;
462 
463  tor_assert(ewma);
464  cdata = SUBTYPE_P(ewma, ewma_policy_circ_data_t, cell_ewma);
465  tor_assert(cdata);
466 
467  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
506 {
508  return;
509  monotime_coarse_get(&start_of_current_tick);
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
522 {
523  if (BUG(!ewma_ticks_initialized)) {
524  cell_ewma_initialize_ticks(); // LCOV_EXCL_LINE
525  }
526  monotime_coarse_t now;
527  monotime_coarse_get(&now);
529  &now);
530  if (msec_diff > (1000*EWMA_TICK_LEN)) {
531  unsigned ticks_difference = msec_diff / (1000*EWMA_TICK_LEN);
532  monotime_coarse_add_msec(&start_of_current_tick,
534  ticks_difference * 1000 * EWMA_TICK_LEN);
535  current_tick_num += ticks_difference;
536  msec_diff %= 1000*EWMA_TICK_LEN;
537  }
538  *remainder_out = ((double)msec_diff) / (1.0e3 * EWMA_TICK_LEN);
539  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 get_circuit_priority_halflife(const or_options_t *options,
558  const networkstatus_t *consensus,
559  const char **source_msg)
560 {
561  int32_t halflife_ms;
562  double halflife;
563  /* Compute the default value now. We might need it. */
564  double halflife_default =
565  ((double) CMUX_PRIORITY_HALFLIFE_MSEC_DEFAULT) / 1000.0;
566 
567  /* Try to get it from configuration file first. */
568  if (options && options->CircuitPriorityHalflife >= -EPSILON) {
569  halflife = options->CircuitPriorityHalflife;
570  *source_msg = "CircuitPriorityHalflife in configuration";
571  goto end;
572  }
573 
574  /* Try to get the msec value from the consensus. */
575  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  halflife = ((double) halflife_ms) / 1000.0;
581  *source_msg = "CircuitPriorityHalflifeMsec in consensus";
582 
583  end:
584  /* We should never go below the EPSILON else we would consider it disabled
585  * and we can't have that. */
586  if (halflife < EPSILON) {
587  log_warn(LD_CONFIG, "CircuitPriorityHalflife is too small (%f). "
588  "Adjusting to the smallest value allowed: %f.",
589  halflife, halflife_default);
590  halflife = halflife_default;
591  }
592  return halflife;
593 }
594 
595 /** Adjust the global cell scale factor based on <b>options</b> */
596 void
598  const networkstatus_t *consensus)
599 {
600  double halflife;
601  const char *source;
602 
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  halflife = get_circuit_priority_halflife(options, consensus, &source);
608 
609  /* convert halflife into halflife-per-tick. */
610  halflife /= EWMA_TICK_LEN;
611  /* compute per-tick scale factor. */
612  ewma_scale_factor = exp(LOG_ONEHALF / halflife);
613  log_info(LD_OR,
614  "Enabled cell_ewma algorithm because of value in %s; "
615  "scale factor is %f per %d seconds",
617 }
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 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  int diff = (int)(to_tick - from_tick);
627  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 scale_single_cell_ewma(cell_ewma_t *ewma, unsigned cur_tick)
634 {
635  double factor = get_scale_factor(ewma->last_adjusted_tick, cur_tick);
636  ewma->cell_count *= factor;
637  ewma->last_adjusted_tick = cur_tick;
638 }
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 scale_active_circuits(ewma_policy_data_t *pol, unsigned cur_tick)
644 {
645  double factor;
646 
647  tor_assert(pol);
648  tor_assert(pol->active_circuit_pqueue);
649 
650  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. */
657  pol->active_circuit_pqueue,
658  cell_ewma_t *, e) {
659  tor_assert(e->last_adjusted_tick ==
660  pol->active_circuit_pqueue_last_recalibrated);
661  e->cell_count *= factor;
662  e->last_adjusted_tick = cur_tick;
663  } SMARTLIST_FOREACH_END(e);
664  pol->active_circuit_pqueue_last_recalibrated = cur_tick;
665 }
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 add_cell_ewma(ewma_policy_data_t *pol, cell_ewma_t *ewma)
671 {
672  tor_assert(pol);
673  tor_assert(pol->active_circuit_pqueue);
674  tor_assert(ewma);
675  tor_assert(ewma->heap_index == -1);
676 
678  ewma,
679  pol->active_circuit_pqueue_last_recalibrated);
680 
681  smartlist_pqueue_add(pol->active_circuit_pqueue,
683  offsetof(cell_ewma_t, heap_index),
684  ewma);
685 }
686 
687 /** Remove <b>ewma</b> from <b>pol</b>'s priority queue of active circuits */
688 static void
689 remove_cell_ewma(ewma_policy_data_t *pol, cell_ewma_t *ewma)
690 {
691  tor_assert(pol);
692  tor_assert(pol->active_circuit_pqueue);
693  tor_assert(ewma);
694  tor_assert(ewma->heap_index != -1);
695 
696  smartlist_pqueue_remove(pol->active_circuit_pqueue,
698  offsetof(cell_ewma_t, heap_index),
699  ewma);
700 }
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 pop_first_cell_ewma(ewma_policy_data_t *pol)
706 {
707  tor_assert(pol);
708  tor_assert(pol->active_circuit_pqueue);
709 
710  return smartlist_pqueue_pop(pol->active_circuit_pqueue,
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
720 {
722 }
tor_free
#define tor_free(p)
Definition: malloc.h:52
pop_first_cell_ewma
static cell_ewma_t * pop_first_cell_ewma(ewma_policy_data_t *pol)
Definition: circuitmux_ewma.c:705
circuitmux_ewma.h
Header file for circuitmux_ewma.c.
memwipe
void memwipe(void *mem, uint8_t byte, size_t sz)
Definition: crypto_util.c:55
or_options_st.h
The or_options_t structure, which represents Tor's configuration.
EWMA_TICK_LEN
#define EWMA_TICK_LEN
Definition: circuitmux_ewma.c:48
tor_assert
#define tor_assert(expr)
Definition: util_bug.h:102
cell_ewma_get_tick
static unsigned int cell_ewma_get_tick(void)
Definition: circuitmux_ewma.c:145
cell_direction_t
cell_direction_t
Definition: or.h:482
smartlist_pqueue_remove
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
circuitmux_ewma_free_all
void circuitmux_ewma_free_all(void)
Definition: circuitmux_ewma.c:719
ewma_notify_xmit_cells
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)
Definition: circuitmux_ewma.c:318
ewma_alloc_cmux_data
static circuitmux_policy_data_t * ewma_alloc_cmux_data(circuitmux_t *cmux)
Definition: circuitmux_ewma.c:160
scale_active_circuits
static void scale_active_circuits(ewma_policy_data_t *pol, unsigned cur_tick)
Definition: circuitmux_ewma.c:643
smartlist_new
smartlist_t * smartlist_new(void)
Definition: smartlist_core.c:26
scale_single_cell_ewma
static void scale_single_cell_ewma(cell_ewma_t *ewma, unsigned cur_tick)
Definition: circuitmux_ewma.c:633
circuitmux.h
Header file for circuitmux.c.
ewma_notify_circ_active
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)
Definition: circuitmux_ewma.c:267
networkstatus.h
Header file for networkstatus.c.
cmux_ewma_set_options
void cmux_ewma_set_options(const or_options_t *options, const networkstatus_t *consensus)
Definition: circuitmux_ewma.c:597
crypto_util.h
Common functions for cryptographic routines.
CELL_DIRECTION_OUT
@ CELL_DIRECTION_OUT
Definition: or.h:484
cell_ewma_initialize_ticks
STATIC void cell_ewma_initialize_ticks(void)
Definition: circuitmux_ewma.c:505
start_of_current_tick
static monotime_coarse_t start_of_current_tick
Definition: circuitmux_ewma.c:137
monotime_coarse_diff_msec32
static int32_t monotime_coarse_diff_msec32(const monotime_coarse_t *start, const monotime_coarse_t *end)
Definition: compat_time.h:338
ewma_ticks_initialized
static int ewma_ticks_initialized
Definition: circuitmux_ewma.c:135
LD_OR
#define LD_OR
Definition: log.h:92
current_tick_num
static unsigned current_tick_num
Definition: circuitmux_ewma.c:139
circuit_t
Definition: circuit_st.h:61
smartlist_pqueue_add
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
add_cell_ewma
static void add_cell_ewma(ewma_policy_data_t *pol, cell_ewma_t *ewma)
Definition: circuitmux_ewma.c:670
LD_CONFIG
#define LD_CONFIG
Definition: log.h:68
ewma_alloc_circ_data
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)
Definition: circuitmux_ewma.c:201
remove_cell_ewma
static void remove_cell_ewma(ewma_policy_data_t *pol, cell_ewma_t *ewma)
Definition: circuitmux_ewma.c:689
ewma_cmp_cmux
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)
Definition: circuitmux_ewma.c:397
crypto_rand.h
Common functions for using (pseudo-)random number generators.
or_options_t::CircuitPriorityHalflife
double CircuitPriorityHalflife
Definition: or_options_st.h:810
circuitmux_policy_circ_data_t
Definition: circuitmux.h:79
ewma_scale_factor
static double ewma_scale_factor
Definition: circuitmux_ewma.c:117
get_scale_factor
static double get_scale_factor(unsigned from_tick, unsigned to_tick)
Definition: circuitmux_ewma.c:622
ewma_pick_active_circuit
static circuit_t * ewma_pick_active_circuit(circuitmux_t *cmux, circuitmux_policy_data_t *pol_data)
Definition: circuitmux_ewma.c:370
LOG_ONEHALF
#define LOG_ONEHALF
Definition: circuitmux_ewma.c:60
SMARTLIST_FOREACH_BEGIN
#define SMARTLIST_FOREACH_BEGIN(sl, type, var)
Definition: smartlist_foreach.h:78
ewma_notify_circ_inactive
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)
Definition: circuitmux_ewma.c:292
cell_ewma_get_current_tick_and_fraction
STATIC unsigned cell_ewma_get_current_tick_and_fraction(double *remainder_out)
Definition: circuitmux_ewma.c:521
circuitmux_policy_data_t
Definition: circuitmux.h:70
circuitmux_policy_t
Definition: circuitmux.h:19
cell_ewma_to_circuit
static circuit_t * cell_ewma_to_circuit(cell_ewma_t *ewma)
Definition: circuitmux_ewma.c:459
EPSILON
#define EPSILON
Definition: circuitmux_ewma.c:58
or_options_t
Definition: or_options_st.h:39
crypto_rand
void crypto_rand(char *to, size_t n)
Definition: crypto_rand.c:477
SUBTYPE_P
#define SUBTYPE_P(p, subtype, basemember)
Definition: compat_compiler.h:218
STATIC
#define STATIC
Definition: testsupport.h:32
TO_CMUX_POL_CIRC_DATA
#define TO_CMUX_POL_CIRC_DATA(x)
Definition: circuitmux.h:98
smartlist_pqueue_pop
void * smartlist_pqueue_pop(smartlist_t *sl, int(*compare)(const void *a, const void *b), ptrdiff_t idx_field_offset)
Definition: smartlist.c:755
compare_cell_ewma_counts
static int compare_cell_ewma_counts(const void *p1, const void *p2)
Definition: circuitmux_ewma.c:445
networkstatus_get_param
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)
Definition: networkstatus.c:2490
networkstatus_t
Definition: networkstatus_st.h:26
CELL_DIRECTION_IN
@ CELL_DIRECTION_IN
Definition: or.h:483
ewma_free_circ_data
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)
Definition: circuitmux_ewma.c:242
or.h
Master header file for Tor-specific functionality.
TO_CMUX_POL_DATA
#define TO_CMUX_POL_DATA(x)
Definition: circuitmux.h:91
ewma_free_cmux_data
static void ewma_free_cmux_data(circuitmux_t *cmux, circuitmux_policy_data_t *pol_data)
Definition: circuitmux_ewma.c:179