1 /* * Copyright (c) 2012-2017, The Tor Project, Inc. */
2 /* See LICENSE for licensing information */
5 * \file circuitmux_ewma.c
6 * \brief EWMA circuit selection as a circuitmux_t policy
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.
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.
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.
26 * This module should be used through the interfaces in circuitmux.c, which it
31 #define TOR_CIRCUITMUX_EWMA_C_
38 #include "circuitmux.h"
39 #include "circuitmux_ewma.h"
40 #include "networkstatus.h"
42 /*** EWMA parameter #defines ***/
44 /** How long does a tick last (seconds)? */
45 #define EWMA_TICK_LEN 10
47 /** The default per-tick scale factor, if it hasn't been overridden by a
48 * consensus or a configuration setting. zero means "disabled". */
49 #define EWMA_DEFAULT_HALFLIFE 0.0
51 /*** Some useful constant #defines ***/
53 /** Any halflife smaller than this number of seconds is considered to be
55 #define EPSILON 0.00001
56 /** The natural logarithm of 0.5. */
57 #define LOG_ONEHALF -0.69314718055994529
59 /*** EWMA structures ***/
61 typedef struct cell_ewma_s cell_ewma_t
;
62 typedef struct ewma_policy_data_s ewma_policy_data_t
;
63 typedef struct ewma_policy_circ_data_s ewma_policy_circ_data_t
;
66 * The cell_ewma_t structure keeps track of how many cells a circuit has
67 * transferred recently. It keeps an EWMA (exponentially weighted moving
68 * average) of the number of cells flushed from the circuit queue onto a
69 * connection in channel_flush_from_first_active_circuit().
73 /** The last 'tick' at which we recalibrated cell_count.
75 * A cell sent at exactly the start of this tick has weight 1.0. Cells sent
76 * since the start of this tick have weight greater than 1.0; ones sent
77 * earlier have less weight. */
78 unsigned int last_adjusted_tick
;
79 /** The EWMA of the cell count. */
81 /** True iff this is the cell count for a circuit's previous
83 unsigned int is_for_p_chan
: 1;
84 /** The position of the circuit within the OR connection's priority
89 struct ewma_policy_data_s
{
90 circuitmux_policy_data_t base_
;
93 * Priority queue of cell_ewma_t for circuits with queued cells waiting
94 * for room to free up on the channel that owns this circuitmux. Kept
95 * in heap order according to EWMA. This was formerly in channel_t, and
96 * in or_connection_t before that.
98 smartlist_t
*active_circuit_pqueue
;
101 * The tick on which the cell_ewma_ts in active_circuit_pqueue last had
102 * their ewma values rescaled. This was formerly in channel_t, and in
103 * or_connection_t before that.
105 unsigned int active_circuit_pqueue_last_recalibrated
;
108 struct ewma_policy_circ_data_s
{
109 circuitmux_policy_circ_data_t base_
;
112 * The EWMA count for the number of cells flushed from this circuit
113 * onto this circuitmux. Used to determine which circuit to flush
114 * from next. This was formerly in circuit_t and or_circuit_t.
116 cell_ewma_t cell_ewma
;
119 * Pointer back to the circuit_t this is for; since we're separating
120 * out circuit selection policy like this, we can't attach cell_ewma_t
121 * to the circuit_t any more, so we can't use SUBTYPE_P directly to a
122 * circuit_t like before; instead get it here.
127 #define EWMA_POL_DATA_MAGIC 0x2fd8b16aU
128 #define EWMA_POL_CIRC_DATA_MAGIC 0x761e7747U
130 /*** Downcasts for the above types ***/
132 static ewma_policy_data_t
*
133 TO_EWMA_POL_DATA(circuitmux_policy_data_t
*);
135 static ewma_policy_circ_data_t
*
136 TO_EWMA_POL_CIRC_DATA(circuitmux_policy_circ_data_t
*);
139 * Downcast a circuitmux_policy_data_t to an ewma_policy_data_t and assert
140 * if the cast is impossible.
143 static inline ewma_policy_data_t
*
144 TO_EWMA_POL_DATA(circuitmux_policy_data_t
*pol
)
146 if (!pol
) return NULL
;
148 tor_assert(pol
->magic
== EWMA_POL_DATA_MAGIC
);
149 return DOWNCAST(ewma_policy_data_t
, pol
);
154 * Downcast a circuitmux_policy_circ_data_t to an ewma_policy_circ_data_t
155 * and assert if the cast is impossible.
158 static inline ewma_policy_circ_data_t
*
159 TO_EWMA_POL_CIRC_DATA(circuitmux_policy_circ_data_t
*pol
)
161 if (!pol
) return NULL
;
163 tor_assert(pol
->magic
== EWMA_POL_CIRC_DATA_MAGIC
);
164 return DOWNCAST(ewma_policy_circ_data_t
, pol
);
168 /*** Static declarations for circuitmux_ewma.c ***/
170 static void add_cell_ewma(ewma_policy_data_t
*pol
, cell_ewma_t
*ewma
);
171 static int compare_cell_ewma_counts(const void *p1
, const void *p2
);
172 static unsigned cell_ewma_tick_from_timeval(const struct timeval
*now
,
173 double *remainder_out
);
174 static circuit_t
* cell_ewma_to_circuit(cell_ewma_t
*ewma
);
175 static inline double get_scale_factor(unsigned from_tick
, unsigned to_tick
);
176 static cell_ewma_t
* pop_first_cell_ewma(ewma_policy_data_t
*pol
);
177 static void remove_cell_ewma(ewma_policy_data_t
*pol
, cell_ewma_t
*ewma
);
178 static void scale_single_cell_ewma(cell_ewma_t
*ewma
, unsigned cur_tick
);
179 static void scale_active_circuits(ewma_policy_data_t
*pol
,
182 /*** Circuitmux policy methods ***/
184 static circuitmux_policy_data_t
* ewma_alloc_cmux_data(circuitmux_t
*cmux
);
185 static void ewma_free_cmux_data(circuitmux_t
*cmux
,
186 circuitmux_policy_data_t
*pol_data
);
187 static circuitmux_policy_circ_data_t
*
188 ewma_alloc_circ_data(circuitmux_t
*cmux
, circuitmux_policy_data_t
*pol_data
,
189 circuit_t
*circ
, cell_direction_t direction
,
190 unsigned int cell_count
);
192 ewma_free_circ_data(circuitmux_t
*cmux
,
193 circuitmux_policy_data_t
*pol_data
,
195 circuitmux_policy_circ_data_t
*pol_circ_data
);
197 ewma_notify_circ_active(circuitmux_t
*cmux
,
198 circuitmux_policy_data_t
*pol_data
,
200 circuitmux_policy_circ_data_t
*pol_circ_data
);
202 ewma_notify_circ_inactive(circuitmux_t
*cmux
,
203 circuitmux_policy_data_t
*pol_data
,
205 circuitmux_policy_circ_data_t
*pol_circ_data
);
207 ewma_notify_xmit_cells(circuitmux_t
*cmux
,
208 circuitmux_policy_data_t
*pol_data
,
210 circuitmux_policy_circ_data_t
*pol_circ_data
,
211 unsigned int n_cells
);
213 ewma_pick_active_circuit(circuitmux_t
*cmux
,
214 circuitmux_policy_data_t
*pol_data
);
216 ewma_cmp_cmux(circuitmux_t
*cmux_1
, circuitmux_policy_data_t
*pol_data_1
,
217 circuitmux_t
*cmux_2
, circuitmux_policy_data_t
*pol_data_2
);
219 /*** EWMA global variables ***/
221 /** The per-tick scale factor to be used when computing cell-count EWMA
222 * values. (A cell sent N ticks before the start of the current tick
223 * has value ewma_scale_factor ** N.)
225 static double ewma_scale_factor
= 0.1;
227 /*** EWMA circuitmux_policy_t method table ***/
229 circuitmux_policy_t ewma_policy
= {
230 /*.alloc_cmux_data =*/ ewma_alloc_cmux_data
,
231 /*.free_cmux_data =*/ ewma_free_cmux_data
,
232 /*.alloc_circ_data =*/ ewma_alloc_circ_data
,
233 /*.free_circ_data =*/ ewma_free_circ_data
,
234 /*.notify_circ_active =*/ ewma_notify_circ_active
,
235 /*.notify_circ_inactive =*/ ewma_notify_circ_inactive
,
236 /*.notify_set_n_cells =*/ NULL
, /* EWMA doesn't need this */
237 /*.notify_xmit_cells =*/ ewma_notify_xmit_cells
,
238 /*.pick_active_circuit =*/ ewma_pick_active_circuit
,
239 /*.cmp_cmux =*/ ewma_cmp_cmux
242 /*** EWMA method implementations using the below EWMA helper functions ***/
244 /** Compute and return the current cell_ewma tick. */
245 static inline unsigned int
246 cell_ewma_get_tick(void)
248 return ((unsigned)approx_time() / EWMA_TICK_LEN
);
252 * Allocate an ewma_policy_data_t and upcast it to a circuitmux_policy_data_t;
253 * this is called when setting the policy on a circuitmux_t to ewma_policy.
256 static circuitmux_policy_data_t
*
257 ewma_alloc_cmux_data(circuitmux_t
*cmux
)
259 ewma_policy_data_t
*pol
= NULL
;
263 pol
= tor_malloc_zero(sizeof(*pol
));
264 pol
->base_
.magic
= EWMA_POL_DATA_MAGIC
;
265 pol
->active_circuit_pqueue
= smartlist_new();
266 pol
->active_circuit_pqueue_last_recalibrated
= cell_ewma_get_tick();
268 return TO_CMUX_POL_DATA(pol
);
272 * Free an ewma_policy_data_t allocated with ewma_alloc_cmux_data()
276 ewma_free_cmux_data(circuitmux_t
*cmux
,
277 circuitmux_policy_data_t
*pol_data
)
279 ewma_policy_data_t
*pol
= NULL
;
282 if (!pol_data
) return;
284 pol
= TO_EWMA_POL_DATA(pol_data
);
286 smartlist_free(pol
->active_circuit_pqueue
);
291 * Allocate an ewma_policy_circ_data_t and upcast it to a
292 * circuitmux_policy_data_t; this is called when attaching a circuit to a
293 * circuitmux_t with ewma_policy.
296 static circuitmux_policy_circ_data_t
*
297 ewma_alloc_circ_data(circuitmux_t
*cmux
,
298 circuitmux_policy_data_t
*pol_data
,
300 cell_direction_t direction
,
301 unsigned int cell_count
)
303 ewma_policy_circ_data_t
*cdata
= NULL
;
306 tor_assert(pol_data
);
308 tor_assert(direction
== CELL_DIRECTION_OUT
||
309 direction
== CELL_DIRECTION_IN
);
310 /* Shut the compiler up without triggering -Wtautological-compare */
313 cdata
= tor_malloc_zero(sizeof(*cdata
));
314 cdata
->base_
.magic
= EWMA_POL_CIRC_DATA_MAGIC
;
318 * Initialize the cell_ewma_t structure (formerly in
319 * init_circuit_base())
321 cdata
->cell_ewma
.last_adjusted_tick
= cell_ewma_get_tick();
322 cdata
->cell_ewma
.cell_count
= 0.0;
323 cdata
->cell_ewma
.heap_index
= -1;
324 if (direction
== CELL_DIRECTION_IN
) {
325 cdata
->cell_ewma
.is_for_p_chan
= 1;
327 cdata
->cell_ewma
.is_for_p_chan
= 0;
330 return TO_CMUX_POL_CIRC_DATA(cdata
);
334 * Free an ewma_policy_circ_data_t allocated with ewma_alloc_circ_data()
338 ewma_free_circ_data(circuitmux_t
*cmux
,
339 circuitmux_policy_data_t
*pol_data
,
341 circuitmux_policy_circ_data_t
*pol_circ_data
)
344 ewma_policy_circ_data_t
*cdata
= NULL
;
348 tor_assert(pol_data
);
350 if (!pol_circ_data
) return;
352 cdata
= TO_EWMA_POL_CIRC_DATA(pol_circ_data
);
358 * Handle circuit activation; this inserts the circuit's cell_ewma into
359 * the active_circuits_pqueue.
363 ewma_notify_circ_active(circuitmux_t
*cmux
,
364 circuitmux_policy_data_t
*pol_data
,
366 circuitmux_policy_circ_data_t
*pol_circ_data
)
368 ewma_policy_data_t
*pol
= NULL
;
369 ewma_policy_circ_data_t
*cdata
= NULL
;
372 tor_assert(pol_data
);
374 tor_assert(pol_circ_data
);
376 pol
= TO_EWMA_POL_DATA(pol_data
);
377 cdata
= TO_EWMA_POL_CIRC_DATA(pol_circ_data
);
379 add_cell_ewma(pol
, &(cdata
->cell_ewma
));
383 * Handle circuit deactivation; this removes the circuit's cell_ewma from
384 * the active_circuits_pqueue.
388 ewma_notify_circ_inactive(circuitmux_t
*cmux
,
389 circuitmux_policy_data_t
*pol_data
,
391 circuitmux_policy_circ_data_t
*pol_circ_data
)
393 ewma_policy_data_t
*pol
= NULL
;
394 ewma_policy_circ_data_t
*cdata
= NULL
;
397 tor_assert(pol_data
);
399 tor_assert(pol_circ_data
);
401 pol
= TO_EWMA_POL_DATA(pol_data
);
402 cdata
= TO_EWMA_POL_CIRC_DATA(pol_circ_data
);
404 remove_cell_ewma(pol
, &(cdata
->cell_ewma
));
408 * Update cell_ewma for this circuit after we've sent some cells, and
409 * remove/reinsert it in the queue. This used to be done (brokenly,
410 * see bug 6816) in channel_flush_from_first_active_circuit().
414 ewma_notify_xmit_cells(circuitmux_t
*cmux
,
415 circuitmux_policy_data_t
*pol_data
,
417 circuitmux_policy_circ_data_t
*pol_circ_data
,
418 unsigned int n_cells
)
420 ewma_policy_data_t
*pol
= NULL
;
421 ewma_policy_circ_data_t
*cdata
= NULL
;
423 double fractional_tick
, ewma_increment
;
424 /* The current (hi-res) time */
425 struct timeval now_hires
;
426 cell_ewma_t
*cell_ewma
, *tmp
;
429 tor_assert(pol_data
);
431 tor_assert(pol_circ_data
);
432 tor_assert(n_cells
> 0);
434 pol
= TO_EWMA_POL_DATA(pol_data
);
435 cdata
= TO_EWMA_POL_CIRC_DATA(pol_circ_data
);
437 /* Rescale the EWMAs if needed */
438 tor_gettimeofday_cached(&now_hires
);
439 tick
= cell_ewma_tick_from_timeval(&now_hires
, &fractional_tick
);
441 if (tick
!= pol
->active_circuit_pqueue_last_recalibrated
) {
442 scale_active_circuits(pol
, tick
);
445 /* How much do we adjust the cell count in cell_ewma by? */
447 ((double)(n_cells
)) * pow(ewma_scale_factor
, -fractional_tick
);
449 /* Do the adjustment */
450 cell_ewma
= &(cdata
->cell_ewma
);
451 cell_ewma
->cell_count
+= ewma_increment
;
454 * Since we just sent on this circuit, it should be at the head of
455 * the queue. Pop the head, assert that it matches, then re-add.
457 tmp
= pop_first_cell_ewma(pol
);
458 tor_assert(tmp
== cell_ewma
);
459 add_cell_ewma(pol
, cell_ewma
);
463 * Pick the preferred circuit to send from; this will be the one with
464 * the lowest EWMA value in the priority queue. This used to be done
465 * in channel_flush_from_first_active_circuit().
469 ewma_pick_active_circuit(circuitmux_t
*cmux
,
470 circuitmux_policy_data_t
*pol_data
)
472 ewma_policy_data_t
*pol
= NULL
;
473 circuit_t
*circ
= NULL
;
474 cell_ewma_t
*cell_ewma
= NULL
;
477 tor_assert(pol_data
);
479 pol
= TO_EWMA_POL_DATA(pol_data
);
481 if (smartlist_len(pol
->active_circuit_pqueue
) > 0) {
482 /* Get the head of the queue */
483 cell_ewma
= smartlist_get(pol
->active_circuit_pqueue
, 0);
484 circ
= cell_ewma_to_circuit(cell_ewma
);
491 * Compare two EWMA cmuxes, and return -1, 0 or 1 to indicate which should
492 * be more preferred - see circuitmux_compare_muxes() of circuitmux.c.
496 ewma_cmp_cmux(circuitmux_t
*cmux_1
, circuitmux_policy_data_t
*pol_data_1
,
497 circuitmux_t
*cmux_2
, circuitmux_policy_data_t
*pol_data_2
)
499 ewma_policy_data_t
*p1
= NULL
, *p2
= NULL
;
500 cell_ewma_t
*ce1
= NULL
, *ce2
= NULL
;
503 tor_assert(pol_data_1
);
505 tor_assert(pol_data_2
);
507 p1
= TO_EWMA_POL_DATA(pol_data_1
);
508 p2
= TO_EWMA_POL_DATA(pol_data_2
);
511 /* Get the head cell_ewma_t from each queue */
512 if (smartlist_len(p1
->active_circuit_pqueue
) > 0) {
513 ce1
= smartlist_get(p1
->active_circuit_pqueue
, 0);
516 if (smartlist_len(p2
->active_circuit_pqueue
) > 0) {
517 ce2
= smartlist_get(p2
->active_circuit_pqueue
, 0);
520 /* Got both of them? */
521 if (ce1
!= NULL
&& ce2
!= NULL
) {
522 /* Pick whichever one has the better best circuit */
523 return compare_cell_ewma_counts(ce1
, ce2
);
526 /* We only have a circuit on cmux_1, so prefer it */
528 } else if (ce2
!= NULL
) {
529 /* We only have a circuit on cmux_2, so prefer it */
532 /* No circuits at all; no preference */
537 /* We got identical params */
542 /** Helper for sorting cell_ewma_t values in their priority queue. */
544 compare_cell_ewma_counts(const void *p1
, const void *p2
)
546 const cell_ewma_t
*e1
= p1
, *e2
= p2
;
548 if (e1
->cell_count
< e2
->cell_count
)
550 else if (e1
->cell_count
> e2
->cell_count
)
556 /** Given a cell_ewma_t, return a pointer to the circuit containing it. */
558 cell_ewma_to_circuit(cell_ewma_t
*ewma
)
560 ewma_policy_circ_data_t
*cdata
= NULL
;
563 cdata
= SUBTYPE_P(ewma
, ewma_policy_circ_data_t
, cell_ewma
);
569 /* ==== Functions for scaling cell_ewma_t ====
571 When choosing which cells to relay first, we favor circuits that have been
572 quiet recently. This gives better latency on connections that aren't
573 pushing lots of data, and makes the network feel more interactive.
575 Conceptually, we take an exponentially weighted mean average of the number
576 of cells a circuit has sent, and allow active circuits (those with cells to
577 relay) to send cells in reverse order of their exponentially-weighted mean
578 average (EWMA) cell count. [That is, a cell sent N seconds ago 'counts'
579 F^N times as much as a cell sent now, for 0<F<1.0, and we favor the
580 circuit that has sent the fewest cells]
582 If 'double' had infinite precision, we could do this simply by counting a
583 cell sent at startup as having weight 1.0, and a cell sent N seconds later
584 as having weight F^-N. This way, we would never need to re-scale
585 any already-sent cells.
587 To prevent double from overflowing, we could count a cell sent now as
588 having weight 1.0 and a cell sent N seconds ago as having weight F^N.
589 This, however, would mean we'd need to re-scale *ALL* old circuits every
590 time we wanted to send a cell.
592 So as a compromise, we divide time into 'ticks' (currently, 10-second
593 increments) and say that a cell sent at the start of a current tick is
594 worth 1.0, a cell sent N seconds before the start of the current tick is
595 worth F^N, and a cell sent N seconds after the start of the current tick is
596 worth F^-N. This way we don't overflow, and we don't need to constantly
600 /** Given a timeval <b>now</b>, compute the cell_ewma tick in which it occurs
601 * and the fraction of the tick that has elapsed between the start of the tick
602 * and <b>now</b>. Return the former and store the latter in
603 * *<b>remainder_out</b>.
605 * These tick values are not meant to be shared between Tor instances, or used
606 * for other purposes. */
609 cell_ewma_tick_from_timeval(const struct timeval
*now
,
610 double *remainder_out
)
612 unsigned res
= (unsigned) (now
->tv_sec
/ EWMA_TICK_LEN
);
614 double rem
= (now
->tv_sec
% EWMA_TICK_LEN
) +
615 ((double)(now
->tv_usec
)) / 1.0e6
;
616 *remainder_out
= rem
/ EWMA_TICK_LEN
;
620 /* Default value for the CircuitPriorityHalflifeMsec consensus parameter in
622 #define CMUX_PRIORITY_HALFLIFE_MSEC_DEFAULT 30000
623 /* Minimum and maximum value for the CircuitPriorityHalflifeMsec consensus
625 #define CMUX_PRIORITY_HALFLIFE_MSEC_MIN 1
626 #define CMUX_PRIORITY_HALFLIFE_MSEC_MAX INT32_MAX
628 /* Return the value of the circuit priority halflife from the options if
629 * available or else from the consensus (in that order). If none can be found,
630 * a default value is returned.
632 * The source_msg points to a string describing from where the value was
633 * picked so it can be used for logging. */
635 get_circuit_priority_halflife(const or_options_t
*options
,
636 const networkstatus_t
*consensus
,
637 const char **source_msg
)
641 /* Compute the default value now. We might need it. */
642 double halflife_default
=
643 ((double) CMUX_PRIORITY_HALFLIFE_MSEC_DEFAULT
) / 1000.0;
645 /* Try to get it from configuration file first. */
646 if (options
&& options
->CircuitPriorityHalflife
< EPSILON
) {
647 halflife
= options
->CircuitPriorityHalflife
;
648 *source_msg
= "CircuitPriorityHalflife in configuration";
652 /* Try to get the msec value from the consensus. */
653 halflife_ms
= networkstatus_get_param(consensus
,
654 "CircuitPriorityHalflifeMsec",
655 CMUX_PRIORITY_HALFLIFE_MSEC_DEFAULT
,
656 CMUX_PRIORITY_HALFLIFE_MSEC_MIN
,
657 CMUX_PRIORITY_HALFLIFE_MSEC_MAX
);
658 halflife
= ((double) halflife_ms
) / 1000.0;
659 *source_msg
= "CircuitPriorityHalflifeMsec in consensus";
662 /* We should never go below the EPSILON else we would consider it disabled
663 * and we can't have that. */
664 if (halflife
< EPSILON
) {
665 log_warn(LD_CONFIG
, "CircuitPriorityHalflife is too small (%f). "
666 "Adjusting to the smallest value allowed: %f.",
667 halflife
, halflife_default
);
668 halflife
= halflife_default
;
673 /** Adjust the global cell scale factor based on <b>options</b> */
675 cmux_ewma_set_options(const or_options_t
*options
,
676 const networkstatus_t
*consensus
)
681 /* Both options and consensus can be NULL. This assures us to either get a
682 * valid configured value or the default one. */
683 halflife
= get_circuit_priority_halflife(options
, consensus
, &source
);
685 /* convert halflife into halflife-per-tick. */
686 halflife
/= EWMA_TICK_LEN
;
687 /* compute per-tick scale factor. */
688 ewma_scale_factor
= exp( LOG_ONEHALF
/ halflife
);
690 "Enabled cell_ewma algorithm because of value in %s; "
691 "scale factor is %f per %d seconds",
692 source
, ewma_scale_factor
, EWMA_TICK_LEN
);
695 /** Return the multiplier necessary to convert the value of a cell sent in
696 * 'from_tick' to one sent in 'to_tick'. */
698 get_scale_factor(unsigned from_tick
, unsigned to_tick
)
700 /* This math can wrap around, but that's okay: unsigned overflow is
702 int diff
= (int)(to_tick
- from_tick
);
703 return pow(ewma_scale_factor
, diff
);
706 /** Adjust the cell count of <b>ewma</b> so that it is scaled with respect to
709 scale_single_cell_ewma(cell_ewma_t
*ewma
, unsigned cur_tick
)
711 double factor
= get_scale_factor(ewma
->last_adjusted_tick
, cur_tick
);
712 ewma
->cell_count
*= factor
;
713 ewma
->last_adjusted_tick
= cur_tick
;
716 /** Adjust the cell count of every active circuit on <b>chan</b> so
717 * that they are scaled with respect to <b>cur_tick</b> */
719 scale_active_circuits(ewma_policy_data_t
*pol
, unsigned cur_tick
)
724 tor_assert(pol
->active_circuit_pqueue
);
728 pol
->active_circuit_pqueue_last_recalibrated
,
730 /** Ordinarily it isn't okay to change the value of an element in a heap,
731 * but it's okay here, since we are preserving the order. */
732 SMARTLIST_FOREACH_BEGIN(
733 pol
->active_circuit_pqueue
,
735 tor_assert(e
->last_adjusted_tick
==
736 pol
->active_circuit_pqueue_last_recalibrated
);
737 e
->cell_count
*= factor
;
738 e
->last_adjusted_tick
= cur_tick
;
739 } SMARTLIST_FOREACH_END(e
);
740 pol
->active_circuit_pqueue_last_recalibrated
= cur_tick
;
743 /** Rescale <b>ewma</b> to the same scale as <b>pol</b>, and add it to
744 * <b>pol</b>'s priority queue of active circuits */
746 add_cell_ewma(ewma_policy_data_t
*pol
, cell_ewma_t
*ewma
)
749 tor_assert(pol
->active_circuit_pqueue
);
751 tor_assert(ewma
->heap_index
== -1);
753 scale_single_cell_ewma(
755 pol
->active_circuit_pqueue_last_recalibrated
);
757 smartlist_pqueue_add(pol
->active_circuit_pqueue
,
758 compare_cell_ewma_counts
,
759 offsetof(cell_ewma_t
, heap_index
),
763 /** Remove <b>ewma</b> from <b>pol</b>'s priority queue of active circuits */
765 remove_cell_ewma(ewma_policy_data_t
*pol
, cell_ewma_t
*ewma
)
768 tor_assert(pol
->active_circuit_pqueue
);
770 tor_assert(ewma
->heap_index
!= -1);
772 smartlist_pqueue_remove(pol
->active_circuit_pqueue
,
773 compare_cell_ewma_counts
,
774 offsetof(cell_ewma_t
, heap_index
),
778 /** Remove and return the first cell_ewma_t from pol's priority queue of
779 * active circuits. Requires that the priority queue is nonempty. */
781 pop_first_cell_ewma(ewma_policy_data_t
*pol
)
784 tor_assert(pol
->active_circuit_pqueue
);
786 return smartlist_pqueue_pop(pol
->active_circuit_pqueue
,
787 compare_cell_ewma_counts
,
788 offsetof(cell_ewma_t
, heap_index
));