31 #define CIRCUITMUX_EWMA_PRIVATE
48 #define EWMA_TICK_LEN_DEFAULT 10
49 #define EWMA_TICK_LEN_MIN 1
50 #define EWMA_TICK_LEN_MAX 600
55 #define EWMA_DEFAULT_HALFLIFE 0.0
61 #define EPSILON 0.00001
63 #define LOG_ONEHALF -0.69314718055994529
67 static void add_cell_ewma(ewma_policy_data_t *pol, cell_ewma_t *ewma);
85 unsigned int cell_count);
106 unsigned int n_cells);
147 static inline unsigned int
150 monotime_coarse_t now;
151 monotime_coarse_get(&now);
165 ewma_policy_data_t *pol = NULL;
169 pol = tor_malloc_zero(
sizeof(*pol));
170 pol->base_.magic = EWMA_POL_DATA_MAGIC;
185 ewma_policy_data_t *pol = NULL;
188 if (!pol_data)
return;
190 pol = TO_EWMA_POL_DATA(pol_data);
192 smartlist_free(pol->active_circuit_pqueue);
193 memwipe(pol, 0xda,
sizeof(ewma_policy_data_t));
208 unsigned int cell_count)
210 ewma_policy_circ_data_t *cdata = NULL;
220 cdata = tor_malloc_zero(
sizeof(*cdata));
221 cdata->base_.magic = EWMA_POL_CIRC_DATA_MAGIC;
229 cdata->cell_ewma.cell_count = 0.0;
230 cdata->cell_ewma.heap_index = -1;
232 cdata->cell_ewma.is_for_p_chan = 1;
234 cdata->cell_ewma.is_for_p_chan = 0;
251 ewma_policy_circ_data_t *cdata = NULL;
257 if (!pol_circ_data)
return;
259 cdata = TO_EWMA_POL_CIRC_DATA(pol_circ_data);
260 memwipe(cdata, 0xdc,
sizeof(ewma_policy_circ_data_t));
275 ewma_policy_data_t *pol = NULL;
276 ewma_policy_circ_data_t *cdata = NULL;
283 pol = TO_EWMA_POL_DATA(pol_data);
284 cdata = TO_EWMA_POL_CIRC_DATA(pol_circ_data);
300 ewma_policy_data_t *pol = NULL;
301 ewma_policy_circ_data_t *cdata = NULL;
308 pol = TO_EWMA_POL_DATA(pol_data);
309 cdata = TO_EWMA_POL_CIRC_DATA(pol_circ_data);
325 unsigned int n_cells)
327 ewma_policy_data_t *pol = NULL;
328 ewma_policy_circ_data_t *cdata = NULL;
330 double fractional_tick, ewma_increment;
331 cell_ewma_t *cell_ewma, *tmp;
339 pol = TO_EWMA_POL_DATA(pol_data);
340 cdata = TO_EWMA_POL_CIRC_DATA(pol_circ_data);
345 if (tick != pol->active_circuit_pqueue_last_recalibrated) {
354 cell_ewma = &(cdata->cell_ewma);
355 cell_ewma->cell_count += ewma_increment;
376 ewma_policy_data_t *pol = NULL;
378 cell_ewma_t *cell_ewma = NULL;
383 pol = TO_EWMA_POL_DATA(pol_data);
385 if (smartlist_len(pol->active_circuit_pqueue) > 0) {
387 cell_ewma = smartlist_get(pol->active_circuit_pqueue, 0);
403 ewma_policy_data_t *p1 = NULL, *p2 = NULL;
404 cell_ewma_t *ce1 = NULL, *ce2 = NULL;
411 p1 = TO_EWMA_POL_DATA(pol_data_1);
412 p2 = TO_EWMA_POL_DATA(pol_data_2);
416 if (smartlist_len(p1->active_circuit_pqueue) > 0) {
417 ce1 = smartlist_get(p1->active_circuit_pqueue, 0);
420 if (smartlist_len(p2->active_circuit_pqueue) > 0) {
421 ce2 = smartlist_get(p2->active_circuit_pqueue, 0);
425 if (ce1 != NULL && ce2 != NULL) {
432 }
else if (ce2 != NULL) {
450 const cell_ewma_t *e1 = p1, *e2 = p2;
452 if (e1->cell_count < e2->cell_count)
454 else if (e1->cell_count > e2->cell_count)
464 ewma_policy_circ_data_t *cdata = NULL;
467 cdata =
SUBTYPE_P(ewma, ewma_policy_circ_data_t, cell_ewma);
529 monotime_coarse_t now;
530 monotime_coarse_get(&now);
533 if (msec_diff > (1000*ewma_tick_len)) {
534 unsigned ticks_difference = msec_diff / (1000*ewma_tick_len);
537 ticks_difference * 1000 * ewma_tick_len);
539 msec_diff %= 1000*ewma_tick_len;
541 *remainder_out = ((double)msec_diff) / (1.0e3 * ewma_tick_len);
547 #define CMUX_PRIORITY_HALFLIFE_MSEC_DEFAULT 30000
550 #define CMUX_PRIORITY_HALFLIFE_MSEC_MIN 1
551 #define CMUX_PRIORITY_HALFLIFE_MSEC_MAX INT32_MAX
560 get_circuit_priority_halflife(
const or_options_t *options,
562 const char **source_msg)
567 double halflife_default =
568 ((double) CMUX_PRIORITY_HALFLIFE_MSEC_DEFAULT) / 1000.0;
573 *source_msg =
"CircuitPriorityHalflife in configuration";
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";
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;
610 halflife = get_circuit_priority_halflife(options, consensus, &source);
612 "CircuitPriorityTickSecs",
618 halflife /= ewma_tick_len;
622 "Enabled cell_ewma algorithm because of value in %s; "
623 "scale factor is %f per %d seconds",
634 int diff = (int)(to_tick - from_tick);
644 ewma->cell_count *= factor;
645 ewma->last_adjusted_tick = cur_tick;
660 pol->active_circuit_pqueue_last_recalibrated,
665 pol->active_circuit_pqueue,
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;
687 pol->active_circuit_pqueue_last_recalibrated);
691 offsetof(cell_ewma_t, heap_index),
706 offsetof(cell_ewma_t, heap_index),
720 offsetof(cell_ewma_t, heap_index));
Header file for circuitmux.c.
#define TO_CMUX_POL_DATA(x)
#define TO_CMUX_POL_CIRC_DATA(x)
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)
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)
void crypto_rand(char *to, size_t n)
Common functions for using (pseudo-)random number generators.
void memwipe(void *mem, uint8_t byte, size_t sz)
Common functions for cryptographic routines.
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.
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)
void * smartlist_pqueue_pop(smartlist_t *sl, int(*compare)(const void *a, const void *b), ptrdiff_t idx_field_offset)
void smartlist_pqueue_remove(smartlist_t *sl, int(*compare)(const void *a, const void *b), ptrdiff_t idx_field_offset, void *item)
smartlist_t * smartlist_new(void)
#define SMARTLIST_FOREACH_BEGIN(sl, type, var)
double CircuitPriorityHalflife