tor  0.4.2.0-alpha-dev
Data Structures | Macros | Typedefs | Functions | Variables
circuitmux_ewma.c File Reference
#include "orconfig.h"
#include <math.h>
#include "core/or/or.h"
#include "core/or/circuitmux.h"
#include "core/or/circuitmux_ewma.h"
#include "lib/crypt_ops/crypto_rand.h"
#include "feature/nodelist/networkstatus.h"
#include "app/config/or_options_st.h"

Go to the source code of this file.

Data Structures

struct  cell_ewma_s
 
struct  ewma_policy_data_s
 
struct  ewma_policy_circ_data_s
 

Macros

#define CIRCUITMUX_EWMA_PRIVATE
 
#define EWMA_TICK_LEN   10
 
#define EWMA_DEFAULT_HALFLIFE   0.0
 
#define EPSILON   0.00001
 
#define LOG_ONEHALF   -0.69314718055994529
 
#define EWMA_POL_DATA_MAGIC   0x2fd8b16aU
 
#define EWMA_POL_CIRC_DATA_MAGIC   0x761e7747U
 
#define CMUX_PRIORITY_HALFLIFE_MSEC_DEFAULT   30000
 
#define CMUX_PRIORITY_HALFLIFE_MSEC_MIN   1
 
#define CMUX_PRIORITY_HALFLIFE_MSEC_MAX   INT32_MAX
 

Typedefs

typedef struct cell_ewma_s cell_ewma_t
 
typedef struct ewma_policy_data_s ewma_policy_data_t
 
typedef struct ewma_policy_circ_data_s ewma_policy_circ_data_t
 

Functions

static ewma_policy_data_tTO_EWMA_POL_DATA (circuitmux_policy_data_t *)
 
static ewma_policy_circ_data_tTO_EWMA_POL_CIRC_DATA (circuitmux_policy_circ_data_t *)
 
static void add_cell_ewma (ewma_policy_data_t *pol, cell_ewma_t *ewma)
 
static int compare_cell_ewma_counts (const void *p1, const void *p2)
 
static circuit_tcell_ewma_to_circuit (cell_ewma_t *ewma)
 
static double get_scale_factor (unsigned from_tick, unsigned to_tick)
 
static cell_ewma_tpop_first_cell_ewma (ewma_policy_data_t *pol)
 
static void remove_cell_ewma (ewma_policy_data_t *pol, cell_ewma_t *ewma)
 
static void scale_single_cell_ewma (cell_ewma_t *ewma, unsigned cur_tick)
 
static void scale_active_circuits (ewma_policy_data_t *pol, unsigned cur_tick)
 
static circuitmux_policy_data_tewma_alloc_cmux_data (circuitmux_t *cmux)
 
static void ewma_free_cmux_data (circuitmux_t *cmux, circuitmux_policy_data_t *pol_data)
 
static circuitmux_policy_circ_data_tewma_alloc_circ_data (circuitmux_t *cmux, circuitmux_policy_data_t *pol_data, circuit_t *circ, cell_direction_t direction, unsigned int cell_count)
 
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_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 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 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 circuit_tewma_pick_active_circuit (circuitmux_t *cmux, circuitmux_policy_data_t *pol_data)
 
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 unsigned int cell_ewma_get_tick (void)
 
STATIC void cell_ewma_initialize_ticks (void)
 
STATIC unsigned cell_ewma_get_current_tick_and_fraction (double *remainder_out)
 
static double get_circuit_priority_halflife (const or_options_t *options, const networkstatus_t *consensus, const char **source_msg)
 
void cmux_ewma_set_options (const or_options_t *options, const networkstatus_t *consensus)
 
void circuitmux_ewma_free_all (void)
 

Variables

static double ewma_scale_factor = 0.1
 
circuitmux_policy_t ewma_policy
 
static int ewma_ticks_initialized = 0
 
static monotime_coarse_t start_of_current_tick
 
static unsigned current_tick_num
 

Detailed Description

EWMA circuit selection as a circuitmux_t policy.

The "EWMA" in this module stands for the "exponentially weighted moving average" of the number of cells sent on each circuit. The goal is to prioritize cells on circuits that have been quiet recently, by looking at those that have sent few cells over time, prioritizing recent times more than older ones.

Specifically, a cell sent at time "now" has weight 1, but a time X ticks before now has weight ewma_scale_factor ^ X , where ewma_scale_factor is between 0.0 and 1.0.

For efficiency, we do not re-scale these averages every time we send a cell: that would be horribly inefficient. Instead, we we keep the cell count on all circuits on the same circuitmux scaled relative to a single tick. When we add a new cell, we scale its weight depending on the time that has elapsed since the tick. We do re-scale the circuits on the circuitmux periodically, so that we don't overflow double.

This module should be used through the interfaces in circuitmux.c, which it implements.

Definition in file circuitmux_ewma.c.

Macro Definition Documentation

◆ EPSILON

#define EPSILON   0.00001

Any halflife smaller than this number of seconds is considered to be "disabled".

Definition at line 57 of file circuitmux_ewma.c.

◆ EWMA_DEFAULT_HALFLIFE

#define EWMA_DEFAULT_HALFLIFE   0.0

The default per-tick scale factor, if it hasn't been overridden by a consensus or a configuration setting. zero means "disabled".

Definition at line 51 of file circuitmux_ewma.c.

◆ EWMA_TICK_LEN

#define EWMA_TICK_LEN   10

How long does a tick last (seconds)?

Definition at line 47 of file circuitmux_ewma.c.

◆ LOG_ONEHALF

#define LOG_ONEHALF   -0.69314718055994529

The natural logarithm of 0.5.

Definition at line 59 of file circuitmux_ewma.c.

Function Documentation

◆ add_cell_ewma()

static void add_cell_ewma ( ewma_policy_data_t pol,
cell_ewma_t ewma 
)
static

◆ cell_ewma_get_current_tick_and_fraction()

STATIC unsigned cell_ewma_get_current_tick_and_fraction ( double *  remainder_out)

Compute the current cell_ewma tick and the fraction of the tick that has elapsed between the start of the tick and the current time. Return the former and store the latter in *remainder_out.

These tick values are not meant to be shared between Tor instances, or used for other purposes.

Definition at line 628 of file circuitmux_ewma.c.

Referenced by ewma_notify_xmit_cells().

◆ cell_ewma_get_tick()

static unsigned int cell_ewma_get_tick ( void  )
inlinestatic

Compute and return the current cell_ewma tick.

Definition at line 253 of file circuitmux_ewma.c.

◆ cell_ewma_initialize_ticks()

STATIC void cell_ewma_initialize_ticks ( void  )

Initialize the system that tells which ewma tick we are in.

Definition at line 612 of file circuitmux_ewma.c.

References ewma_ticks_initialized.

Referenced by cmux_ewma_set_options().

◆ cell_ewma_to_circuit()

static circuit_t * cell_ewma_to_circuit ( cell_ewma_t ewma)
static

Given a cell_ewma_t, return a pointer to the circuit containing it.

Definition at line 566 of file circuitmux_ewma.c.

References ewma_policy_circ_data_s::circ, SUBTYPE_P, and tor_assert().

◆ circuitmux_ewma_free_all()

void circuitmux_ewma_free_all ( void  )

Drop all resources held by circuitmux_ewma.c, and deinitialize the module.

Definition at line 826 of file circuitmux_ewma.c.

References ewma_ticks_initialized.

◆ cmux_ewma_set_options()

void cmux_ewma_set_options ( const or_options_t options,
const networkstatus_t consensus 
)

Adjust the global cell scale factor based on options

Definition at line 704 of file circuitmux_ewma.c.

References cell_ewma_initialize_ticks().

◆ compare_cell_ewma_counts()

static int compare_cell_ewma_counts ( const void *  p1,
const void *  p2 
)
static

Helper for sorting cell_ewma_t values in their priority queue.

Definition at line 552 of file circuitmux_ewma.c.

References cell_ewma_s::cell_count.

Referenced by add_cell_ewma(), pop_first_cell_ewma(), and remove_cell_ewma().

◆ 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 
)
static

Allocate an ewma_policy_circ_data_t and upcast it to a circuitmux_policy_data_t; this is called when attaching a circuit to a circuitmux_t with ewma_policy.

Definition at line 308 of file circuitmux_ewma.c.

References CELL_DIRECTION_IN, CELL_DIRECTION_OUT, and tor_assert().

◆ ewma_alloc_cmux_data()

static circuitmux_policy_data_t * ewma_alloc_cmux_data ( circuitmux_t cmux)
static

Allocate an ewma_policy_data_t and upcast it to a circuitmux_policy_data_t; this is called when setting the policy on a circuitmux_t to ewma_policy.

Definition at line 268 of file circuitmux_ewma.c.

References tor_assert().

◆ 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 
)
static

Compare two EWMA cmuxes, and return -1, 0 or 1 to indicate which should be more preferred - see circuitmux_compare_muxes() of circuitmux.c.

Definition at line 504 of file circuitmux_ewma.c.

References TO_EWMA_POL_DATA(), and tor_assert().

◆ 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 
)
static

Free an ewma_policy_circ_data_t allocated with ewma_alloc_circ_data()

Definition at line 349 of file circuitmux_ewma.c.

References TO_EWMA_POL_CIRC_DATA(), tor_assert(), and tor_free.

◆ ewma_free_cmux_data()

static void ewma_free_cmux_data ( circuitmux_t cmux,
circuitmux_policy_data_t pol_data 
)
static

Free an ewma_policy_data_t allocated with ewma_alloc_cmux_data()

Definition at line 287 of file circuitmux_ewma.c.

References TO_EWMA_POL_DATA(), and tor_assert().

◆ 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 
)
static

Handle circuit activation; this inserts the circuit's cell_ewma into the active_circuits_pqueue.

Definition at line 374 of file circuitmux_ewma.c.

References add_cell_ewma(), ewma_policy_circ_data_s::cell_ewma, TO_EWMA_POL_CIRC_DATA(), TO_EWMA_POL_DATA(), and tor_assert().

◆ 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 
)
static

Handle circuit deactivation; this removes the circuit's cell_ewma from the active_circuits_pqueue.

Definition at line 399 of file circuitmux_ewma.c.

References ewma_policy_circ_data_s::cell_ewma, remove_cell_ewma(), TO_EWMA_POL_CIRC_DATA(), TO_EWMA_POL_DATA(), and tor_assert().

◆ 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 
)
static

Update cell_ewma for this circuit after we've sent some cells, and remove/reinsert it in the queue. This used to be done (brokenly, see bug 6816) in channel_flush_from_first_active_circuit().

Definition at line 425 of file circuitmux_ewma.c.

References ewma_policy_data_s::active_circuit_pqueue_last_recalibrated, add_cell_ewma(), cell_ewma_s::cell_count, ewma_policy_circ_data_s::cell_ewma, cell_ewma_get_current_tick_and_fraction(), ewma_scale_factor, pop_first_cell_ewma(), scale_active_circuits(), TO_EWMA_POL_CIRC_DATA(), TO_EWMA_POL_DATA(), and tor_assert().

◆ ewma_pick_active_circuit()

static circuit_t * ewma_pick_active_circuit ( circuitmux_t cmux,
circuitmux_policy_data_t pol_data 
)
static

Pick the preferred circuit to send from; this will be the one with the lowest EWMA value in the priority queue. This used to be done in channel_flush_from_first_active_circuit().

Definition at line 477 of file circuitmux_ewma.c.

References TO_EWMA_POL_DATA(), and tor_assert().

◆ get_scale_factor()

static double get_scale_factor ( unsigned  from_tick,
unsigned  to_tick 
)
inlinestatic

Return the multiplier necessary to convert the value of a cell sent in 'from_tick' to one sent in 'to_tick'.

Definition at line 729 of file circuitmux_ewma.c.

References ewma_scale_factor.

Referenced by scale_active_circuits(), and scale_single_cell_ewma().

◆ pop_first_cell_ewma()

static cell_ewma_t * pop_first_cell_ewma ( ewma_policy_data_t pol)
static

Remove and return the first cell_ewma_t from pol's priority queue of active circuits. Requires that the priority queue is nonempty.

Definition at line 812 of file circuitmux_ewma.c.

References ewma_policy_data_s::active_circuit_pqueue, compare_cell_ewma_counts(), smartlist_pqueue_pop(), and tor_assert().

Referenced by ewma_notify_xmit_cells().

◆ remove_cell_ewma()

static void remove_cell_ewma ( ewma_policy_data_t pol,
cell_ewma_t ewma 
)
static

Remove ewma from pol's priority queue of active circuits

Definition at line 796 of file circuitmux_ewma.c.

References ewma_policy_data_s::active_circuit_pqueue, compare_cell_ewma_counts(), cell_ewma_s::heap_index, smartlist_pqueue_remove(), and tor_assert().

Referenced by ewma_notify_circ_inactive().

◆ scale_active_circuits()

static void scale_active_circuits ( ewma_policy_data_t pol,
unsigned  cur_tick 
)
static

Adjust the cell count of every active circuit on chan so that they are scaled with respect to cur_tick

Ordinarily it isn't okay to change the value of an element in a heap, but it's okay here, since we are preserving the order.

Definition at line 750 of file circuitmux_ewma.c.

References ewma_policy_data_s::active_circuit_pqueue, ewma_policy_data_s::active_circuit_pqueue_last_recalibrated, get_scale_factor(), SMARTLIST_FOREACH_BEGIN, and tor_assert().

Referenced by ewma_notify_xmit_cells().

◆ scale_single_cell_ewma()

static void scale_single_cell_ewma ( cell_ewma_t ewma,
unsigned  cur_tick 
)
static

Adjust the cell count of ewma so that it is scaled with respect to cur_tick

Definition at line 740 of file circuitmux_ewma.c.

References cell_ewma_s::cell_count, get_scale_factor(), and cell_ewma_s::last_adjusted_tick.

Referenced by add_cell_ewma().

◆ TO_EWMA_POL_CIRC_DATA()

static ewma_policy_circ_data_t * TO_EWMA_POL_CIRC_DATA ( circuitmux_policy_circ_data_t pol)
inlinestatic

Downcast a circuitmux_policy_circ_data_t to an ewma_policy_circ_data_t and assert if the cast is impossible.

Definition at line 161 of file circuitmux_ewma.c.

References tor_assert().

Referenced by ewma_free_circ_data(), ewma_notify_circ_active(), ewma_notify_circ_inactive(), and ewma_notify_xmit_cells().

◆ TO_EWMA_POL_DATA()

static ewma_policy_data_t * TO_EWMA_POL_DATA ( circuitmux_policy_data_t pol)
inlinestatic

Downcast a circuitmux_policy_data_t to an ewma_policy_data_t and assert if the cast is impossible.

Definition at line 146 of file circuitmux_ewma.c.

References tor_assert().

Referenced by ewma_cmp_cmux(), ewma_free_cmux_data(), ewma_notify_circ_active(), ewma_notify_circ_inactive(), ewma_notify_xmit_cells(), and ewma_pick_active_circuit().

Variable Documentation

◆ current_tick_num

unsigned current_tick_num
static

What is the number of the current tick?

Definition at line 247 of file circuitmux_ewma.c.

◆ ewma_policy

circuitmux_policy_t ewma_policy
Initial value:
= {
NULL,
}
static void ewma_free_cmux_data(circuitmux_t *cmux, circuitmux_policy_data_t *pol_data)
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 circuitmux_policy_data_t * ewma_alloc_cmux_data(circuitmux_t *cmux)
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 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 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 circuit_t * ewma_pick_active_circuit(circuitmux_t *cmux, circuitmux_policy_data_t *pol_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 at line 229 of file circuitmux_ewma.c.

◆ ewma_scale_factor

double ewma_scale_factor = 0.1
static

The per-tick scale factor to be used when computing cell-count EWMA values. (A cell sent N ticks before the start of the current tick has value ewma_scale_factor ** N.)

Definition at line 225 of file circuitmux_ewma.c.

Referenced by ewma_notify_xmit_cells(), and get_scale_factor().

◆ ewma_ticks_initialized

int ewma_ticks_initialized = 0
static

Have we initialized the ewma tick-counting logic?

Definition at line 243 of file circuitmux_ewma.c.

Referenced by cell_ewma_initialize_ticks(), and circuitmux_ewma_free_all().

◆ start_of_current_tick

monotime_coarse_t start_of_current_tick
static

At what monotime_coarse_t did the current tick begin?

Definition at line 245 of file circuitmux_ewma.c.