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