31 #define CIRCUITMUX_EWMA_PRIVATE
48 #define EWMA_TICK_LEN 10
52 #define EWMA_DEFAULT_HALFLIFE 0.0
58 #define EPSILON 0.00001
60 #define LOG_ONEHALF -0.69314718055994529
64 static void add_cell_ewma(ewma_policy_data_t *pol, cell_ewma_t *ewma);
82 unsigned int cell_count);
103 unsigned int n_cells);
144 static inline unsigned int
147 monotime_coarse_t now;
148 monotime_coarse_get(&now);
162 ewma_policy_data_t *pol = NULL;
166 pol = tor_malloc_zero(
sizeof(*pol));
167 pol->base_.magic = EWMA_POL_DATA_MAGIC;
182 ewma_policy_data_t *pol = NULL;
185 if (!pol_data)
return;
187 pol = TO_EWMA_POL_DATA(pol_data);
189 smartlist_free(pol->active_circuit_pqueue);
190 memwipe(pol, 0xda,
sizeof(ewma_policy_data_t));
205 unsigned int cell_count)
207 ewma_policy_circ_data_t *cdata = NULL;
217 cdata = tor_malloc_zero(
sizeof(*cdata));
218 cdata->base_.magic = EWMA_POL_CIRC_DATA_MAGIC;
226 cdata->cell_ewma.cell_count = 0.0;
227 cdata->cell_ewma.heap_index = -1;
229 cdata->cell_ewma.is_for_p_chan = 1;
231 cdata->cell_ewma.is_for_p_chan = 0;
248 ewma_policy_circ_data_t *cdata = NULL;
254 if (!pol_circ_data)
return;
256 cdata = TO_EWMA_POL_CIRC_DATA(pol_circ_data);
257 memwipe(cdata, 0xdc,
sizeof(ewma_policy_circ_data_t));
272 ewma_policy_data_t *pol = NULL;
273 ewma_policy_circ_data_t *cdata = NULL;
280 pol = TO_EWMA_POL_DATA(pol_data);
281 cdata = TO_EWMA_POL_CIRC_DATA(pol_circ_data);
297 ewma_policy_data_t *pol = NULL;
298 ewma_policy_circ_data_t *cdata = NULL;
305 pol = TO_EWMA_POL_DATA(pol_data);
306 cdata = TO_EWMA_POL_CIRC_DATA(pol_circ_data);
322 unsigned int n_cells)
324 ewma_policy_data_t *pol = NULL;
325 ewma_policy_circ_data_t *cdata = NULL;
327 double fractional_tick, ewma_increment;
328 cell_ewma_t *cell_ewma, *tmp;
336 pol = TO_EWMA_POL_DATA(pol_data);
337 cdata = TO_EWMA_POL_CIRC_DATA(pol_circ_data);
342 if (tick != pol->active_circuit_pqueue_last_recalibrated) {
351 cell_ewma = &(cdata->cell_ewma);
352 cell_ewma->cell_count += ewma_increment;
373 ewma_policy_data_t *pol = NULL;
375 cell_ewma_t *cell_ewma = NULL;
380 pol = TO_EWMA_POL_DATA(pol_data);
382 if (smartlist_len(pol->active_circuit_pqueue) > 0) {
384 cell_ewma = smartlist_get(pol->active_circuit_pqueue, 0);
400 ewma_policy_data_t *p1 = NULL, *p2 = NULL;
401 cell_ewma_t *ce1 = NULL, *ce2 = NULL;
408 p1 = TO_EWMA_POL_DATA(pol_data_1);
409 p2 = TO_EWMA_POL_DATA(pol_data_2);
413 if (smartlist_len(p1->active_circuit_pqueue) > 0) {
414 ce1 = smartlist_get(p1->active_circuit_pqueue, 0);
417 if (smartlist_len(p2->active_circuit_pqueue) > 0) {
418 ce2 = smartlist_get(p2->active_circuit_pqueue, 0);
422 if (ce1 != NULL && ce2 != NULL) {
429 }
else if (ce2 != NULL) {
447 const cell_ewma_t *e1 = p1, *e2 = p2;
449 if (e1->cell_count < e2->cell_count)
451 else if (e1->cell_count > e2->cell_count)
461 ewma_policy_circ_data_t *cdata = NULL;
464 cdata =
SUBTYPE_P(ewma, ewma_policy_circ_data_t, cell_ewma);
526 monotime_coarse_t now;
527 monotime_coarse_get(&now);
531 unsigned ticks_difference = msec_diff / (1000*
EWMA_TICK_LEN);
538 *remainder_out = ((double)msec_diff) / (1.0e3 *
EWMA_TICK_LEN);
544 #define CMUX_PRIORITY_HALFLIFE_MSEC_DEFAULT 30000
547 #define CMUX_PRIORITY_HALFLIFE_MSEC_MIN 1
548 #define CMUX_PRIORITY_HALFLIFE_MSEC_MAX INT32_MAX
557 get_circuit_priority_halflife(
const or_options_t *options,
559 const char **source_msg)
564 double halflife_default =
565 ((double) CMUX_PRIORITY_HALFLIFE_MSEC_DEFAULT) / 1000.0;
570 *source_msg =
"CircuitPriorityHalflife in configuration";
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";
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;
607 halflife = get_circuit_priority_halflife(options, consensus, &source);
614 "Enabled cell_ewma algorithm because of value in %s; "
615 "scale factor is %f per %d seconds",
626 int diff = (int)(to_tick - from_tick);
636 ewma->cell_count *= factor;
637 ewma->last_adjusted_tick = cur_tick;
652 pol->active_circuit_pqueue_last_recalibrated,
657 pol->active_circuit_pqueue,
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;
679 pol->active_circuit_pqueue_last_recalibrated);
683 offsetof(cell_ewma_t, heap_index),
698 offsetof(cell_ewma_t, heap_index),
712 offsetof(cell_ewma_t, heap_index));