path: root/src/core/or/circuitmux_ewma.c

/* * Copyright (c) 2012-2020, The Tor Project, Inc. */
/* See LICENSE for licensing information */

/**
 * \file circuitmux_ewma.c
 * \brief 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.
 *
 **/

#define CIRCUITMUX_EWMA_PRIVATE

#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 "lib/crypt_ops/crypto_util.h"
#include "feature/nodelist/networkstatus.h"
#include "app/config/or_options_st.h"

/*** EWMA parameter #defines ***/

/** How long does a tick last (seconds)? */
#define EWMA_TICK_LEN 10

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

/*** Some useful constant #defines ***/

/** Any halflife smaller than this number of seconds is considered to be
 * "disabled". */
#define EPSILON 0.00001
/** The natural logarithm of 0.5. */
#define LOG_ONEHALF -0.69314718055994529

/*** Static declarations for circuitmux_ewma.c ***/

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_t * cell_ewma_to_circuit(cell_ewma_t *ewma);
static inline double get_scale_factor(unsigned from_tick, unsigned to_tick);
static cell_ewma_t * pop_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);

/*** Circuitmux policy methods ***/

static circuitmux_policy_data_t * ewma_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_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 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_t *
ewma_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);

/*** EWMA global variables ***/

/** 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.)
 */
static double ewma_scale_factor = 0.1;

/*** EWMA circuitmux_policy_t method table ***/

circuitmux_policy_t ewma_policy = {
  /*.alloc_cmux_data =*/ ewma_alloc_cmux_data,
  /*.free_cmux_data =*/ ewma_free_cmux_data,
  /*.alloc_circ_data =*/ ewma_alloc_circ_data,
  /*.free_circ_data =*/ ewma_free_circ_data,
  /*.notify_circ_active =*/ ewma_notify_circ_active,
  /*.notify_circ_inactive =*/ ewma_notify_circ_inactive,
  /*.notify_set_n_cells =*/ NULL, /* EWMA doesn't need this */
  /*.notify_xmit_cells =*/ ewma_notify_xmit_cells,
  /*.pick_active_circuit =*/ ewma_pick_active_circuit,
  /*.cmp_cmux =*/ ewma_cmp_cmux
};

/** Have we initialized the ewma tick-counting logic? */
static int ewma_ticks_initialized = 0;
/** At what monotime_coarse_t did the current tick begin? */
static monotime_coarse_t start_of_current_tick;
/** What is the number of the current tick? */
static unsigned current_tick_num;

/*** EWMA method implementations using the below EWMA helper functions ***/

/** Compute and return the current cell_ewma tick. */
static inline unsigned int
cell_ewma_get_tick(void)
{
  monotime_coarse_t now;
  monotime_coarse_get(&now);
  int32_t msec_diff = monotime_coarse_diff_msec32(&start_of_current_tick,
                                                  &now);
  return current_tick_num + msec_diff / (1000*EWMA_TICK_LEN);
}

/**
 * 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.
 */

static circuitmux_policy_data_t *
ewma_alloc_cmux_data(circuitmux_t *cmux)
{
  ewma_policy_data_t *pol = NULL;

  tor_assert(cmux);

  pol = tor_malloc_zero(sizeof(*pol));
  pol->base_.magic = EWMA_POL_DATA_MAGIC;
  pol->active_circuit_pqueue = smartlist_new();
  pol->active_circuit_pqueue_last_recalibrated = cell_ewma_get_tick();

  return TO_CMUX_POL_DATA(pol);
}

/**
 * Free an ewma_policy_data_t allocated with ewma_alloc_cmux_data()
 */

static void
ewma_free_cmux_data(circuitmux_t *cmux,
                    circuitmux_policy_data_t *pol_data)
{
  ewma_policy_data_t *pol = NULL;

  tor_assert(cmux);
  if (!pol_data) return;

  pol = TO_EWMA_POL_DATA(pol_data);

  smartlist_free(pol->active_circuit_pqueue);
  memwipe(pol, 0xda, sizeof(ewma_policy_data_t));
  tor_free(pol);
}

/**
 * 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.
 */

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)
{
  ewma_policy_circ_data_t *cdata = NULL;

  tor_assert(cmux);
  tor_assert(pol_data);
  tor_assert(circ);
  tor_assert(direction == CELL_DIRECTION_OUT ||
             direction == CELL_DIRECTION_IN);
  /* Shut the compiler up without triggering -Wtautological-compare */
  (void)cell_count;

  cdata = tor_malloc_zero(sizeof(*cdata));
  cdata->base_.magic = EWMA_POL_CIRC_DATA_MAGIC;
  cdata->circ = circ;

  /*
   * Initialize the cell_ewma_t structure (formerly in
   * init_circuit_base())
   */
  cdata->cell_ewma.last_adjusted_tick = cell_ewma_get_tick();
  cdata->cell_ewma.cell_count = 0.0;
  cdata->cell_ewma.heap_index = -1;
  if (direction == CELL_DIRECTION_IN)</