src/core/or/circuitmux_ewma.c

   1 /* * Copyright (c) 2012-2021, The Tor Project, Inc. */
   2 /* See LICENSE for licensing information */
   3
   4 /**
   5  * \file circuitmux_ewma.c
   6  * \brief EWMA circuit selection as a circuitmux_t policy
   7  *
   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.
  13  *
  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.
  17  *
  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.
  24  *
  25  *
  26  * This module should be used through the interfaces in circuitmux.c, which it
  27  * implements.
  28  *
  29  **/
  30
  31 #define CIRCUITMUX_EWMA_PRIVATE
  32
  33 #include "orconfig.h"
  34
  35 #include <math.h>
  36
  37 #include "core/or/or.h"
  38 #include "core/or/circuitmux.h"
  39 #include "core/or/circuitmux_ewma.h"
  40 #include "lib/crypt_ops/crypto_rand.h"
  41 #include "lib/crypt_ops/crypto_util.h"
  42 #include "feature/nodelist/networkstatus.h"
  43 #include "app/config/or_options_st.h"
  44
  45 /*** EWMA parameter #defines ***/
  46
  47 /** How long does a tick last (seconds)? */
  48 #define EWMA_TICK_LEN_DEFAULT 10
  49 #define EWMA_TICK_LEN_MIN 1
  50 #define EWMA_TICK_LEN_MAX 600
  51 static int ewma_tick_len = EWMA_TICK_LEN_DEFAULT;
  52
  53 /** The default per-tick scale factor, if it hasn't been overridden by a
  54  * consensus or a configuration setting.  zero means "disabled". */
  55 #define EWMA_DEFAULT_HALFLIFE 0.0
  56
  57 /*** Some useful constant #defines ***/
  58
  59 /** Any halflife smaller than this number of seconds is considered to be
  60  * "disabled". */
  61 #define EPSILON 0.00001
  62 /** The natural logarithm of 0.5. */
  63 #define LOG_ONEHALF -0.69314718055994529
  64
  65 /*** Static declarations for circuitmux_ewma.c ***/
  66
  67 static void add_cell_ewma(ewma_policy_data_t *pol, cell_ewma_t *ewma);
  68 static int compare_cell_ewma_counts(const void *p1, const void *p2);
  69 static circuit_t * cell_ewma_to_circuit(cell_ewma_t *ewma);
  70 static inline double get_scale_factor(unsigned from_tick, unsigned to_tick);
  71 static cell_ewma_t * pop_first_cell_ewma(ewma_policy_data_t *pol);
  72 static void remove_cell_ewma(ewma_policy_data_t *pol, cell_ewma_t *ewma);
  73 static void scale_single_cell_ewma(cell_ewma_t *ewma, unsigned cur_tick);
  74 static void scale_active_circuits(ewma_policy_data_t *pol,
  75                                   unsigned cur_tick);
  76
  77 /*** Circuitmux policy methods ***/
  78
  79 static circuitmux_policy_data_t * ewma_alloc_cmux_data(circuitmux_t *cmux);
  80 static void ewma_free_cmux_data(circuitmux_t *cmux,
  81                                 circuitmux_policy_data_t *pol_data);
  82 static circuitmux_policy_circ_data_t *
  83 ewma_alloc_circ_data(circuitmux_t *cmux, circuitmux_policy_data_t *pol_data,
  84                      circuit_t *circ, cell_direction_t direction,
  85                      unsigned int cell_count);
  86 static void
  87 ewma_free_circ_data(circuitmux_t *cmux,
  88                     circuitmux_policy_data_t *pol_data,
  89                     circuit_t *circ,
  90                     circuitmux_policy_circ_data_t *pol_circ_data);
  91 static void
  92 ewma_notify_circ_active(circuitmux_t *cmux,
  93                         circuitmux_policy_data_t *pol_data,
  94                         circuit_t *circ,
  95                         circuitmux_policy_circ_data_t *pol_circ_data);
  96 static void
  97 ewma_notify_circ_inactive(circuitmux_t *cmux,
  98                           circuitmux_policy_data_t *pol_data,
  99                           circuit_t *circ,
 100                           circuitmux_policy_circ_data_t *pol_circ_data);
 101 static void
 102 ewma_notify_xmit_cells(circuitmux_t *cmux,
 103                        circuitmux_policy_data_t *pol_data,
 104                        circuit_t *circ,
 105                        circuitmux_policy_circ_data_t *pol_circ_data,
 106                        unsigned int n_cells);
 107 static circuit_t *
 108 ewma_pick_active_circuit(circuitmux_t *cmux,
 109                          circuitmux_policy_data_t *pol_data);
 110 static int
 111 ewma_cmp_cmux(circuitmux_t *cmux_1, circuitmux_policy_data_t *pol_data_1,
 112               circuitmux_t *cmux_2, circuitmux_policy_data_t *pol_data_2);
 113
 114 /*** EWMA global variables ***/
 115
 116 /** The per-tick scale factor to be used when computing cell-count EWMA
 117  * values.  (A cell sent N ticks before the start of the current tick
 118  * has value ewma_scale_factor ** N.)
 119  */
 120 static double ewma_scale_factor = 0.1;
 121
 122 /*** EWMA circuitmux_policy_t method table ***/
 123
 124 circuitmux_policy_t ewma_policy = {
 125   /*.alloc_cmux_data =*/ ewma_alloc_cmux_data,
 126   /*.free_cmux_data =*/ ewma_free_cmux_data,
 127   /*.alloc_circ_data =*/ ewma_alloc_circ_data,
 128   /*.free_circ_data =*/ ewma_free_circ_data,
 129   /*.notify_circ_active =*/ ewma_notify_circ_active,
 130   /*.notify_circ_inactive =*/ ewma_notify_circ_inactive,
 131   /*.notify_set_n_cells =*/ NULL, /* EWMA doesn't need this */
 132   /*.notify_xmit_cells =*/ ewma_notify_xmit_cells,
 133   /*.pick_active_circuit =*/ ewma_pick_active_circuit,
 134   /*.cmp_cmux =*/ ewma_cmp_cmux
 135 };
 136
 137 /** Have we initialized the ewma tick-counting logic? */
 138 static int ewma_ticks_initialized = 0;
 139 /** At what monotime_coarse_t did the current tick begin? */
 140 static monotime_coarse_t start_of_current_tick;
 141 /** What is the number of the current tick? */
 142 static unsigned current_tick_num;
 143
 144 /*** EWMA method implementations using the below EWMA helper functions ***/
 145
 146 /** Compute and return the current cell_ewma tick. */
 147 static inline unsigned int
 148 cell_ewma_get_tick(void)
 149 {
 150   monotime_coarse_t now;
 151   monotime_coarse_get(&now);
 152   int32_t msec_diff = monotime_coarse_diff_msec32(&start_of_current_tick,
 153                                                   &now);
 154   return current_tick_num + msec_diff / (1000*ewma_tick_len);
 155 }
 156
 157 /**
 158  * Allocate an ewma_policy_data_t and upcast it to a circuitmux_policy_data_t;
 159  * this is called when setting the policy on a circuitmux_t to ewma_policy.
 160  */
 161
 162 static circuitmux_policy_data_t *
 163 ewma_alloc_cmux_data(circuitmux_t *cmux)
 164 {
 165   ewma_policy_data_t *pol = NULL;
 166
 167   tor_assert(cmux);
 168
 169   pol = tor_malloc_zero(sizeof(*pol));
 170   pol->base_.magic = EWMA_POL_DATA_MAGIC;
 171   pol->active_circuit_pqueue = smartlist_new();
 172   pol->active_circuit_pqueue_last_recalibrated = cell_ewma_get_tick();
 173
 174   return TO_CMUX_POL_DATA(pol);
 175 }
 176
 177 /**
 178  * Free an ewma_policy_data_t allocated with ewma_alloc_cmux_data()
 179  */
 180
 181 static void
 182 ewma_free_cmux_data(circuitmux_t *cmux,
 183                     circuitmux_policy_data_t *pol_data)
 184 {
 185   ewma_policy_data_t *pol = NULL;
 186
 187   tor_assert(cmux);
 188   if (!pol_data) return;
 189
 190   pol = TO_EWMA_POL_DATA(pol_data);
 191
 192   smartlist_free(pol->active_circuit_pqueue);
 193   memwipe(pol, 0xda, sizeof(ewma_policy_data_t));
 194   tor_free(pol);
 195 }
 196
 197 /**
 198  * Allocate an ewma_policy_circ_data_t and upcast it to a
 199  * circuitmux_policy_data_t; this is called when attaching a circuit to a
 200  * circuitmux_t with ewma_policy.
 201  */
 202
 203 static circuitmux_policy_circ_data_t *
 204 ewma_alloc_circ_data(circuitmux_t *cmux,
 205                      circuitmux_policy_data_t *pol_data,
 206                      circuit_t *circ,
 207                      cell_direction_t direction,
 208                      unsigned int cell_count)
 209 {
 210   ewma_policy_circ_data_t *cdata = NULL;
 211
 212   tor_assert(cmux);
 213   tor_assert(pol_data);
 214   tor_assert(circ);
 215   tor_assert(direction == CELL_DIRECTION_OUT ||
 216              direction == CELL_DIRECTION_IN);
 217   /* Shut the compiler up without triggering -Wtautological-compare */
 218   (void)cell_count;
 219
 220   cdata = tor_malloc_zero(sizeof(*cdata));
 221   cdata->base_.magic = EWMA_POL_CIRC_DATA_MAGIC;
 222   cdata->circ = circ;
 223
 224   /*
 225    * Initialize the cell_ewma_t structure (formerly in
 226    * init_circuit_base())
 227    */
 228   cdata->cell_ewma.last_adjusted_tick = cell_ewma_get_tick();
 229   cdata->cell_ewma.cell_count = 0.0;
 230   cdata->cell_ewma.heap_index = -1;
 231   if (direction == CELL_DIRECTION_IN) {
 232     cdata->cell_ewma.is_for_p_chan = 1;
 233   } else {
 234     cdata->cell_ewma.is_for_p_chan = 0;
 235   }
 236
 237   return TO_CMUX_POL_CIRC_DATA(cdata);
 238 }
 239
 240 /**
 241  * Free an ewma_policy_circ_data_t allocated with ewma_alloc_circ_data()
 242  */
 243
 244 static void
 245 ewma_free_circ_data(circuitmux_t *cmux,
 246                     circuitmux_policy_data_t *pol_data,
 247                     circuit_t *circ,
 248                     circuitmux_policy_circ_data_t *pol_circ_data)
 249
 250 {
 251   ewma_policy_circ_data_t *cdata = NULL;
 252
 253   tor_assert(cmux);
 254   tor_assert(circ);
 255   tor_assert(pol_data);
 256
 257   if (!pol_circ_data) return;
 258
 259   cdata = TO_EWMA_POL_CIRC_DATA(pol_circ_data);
 260   memwipe(cdata, 0xdc, sizeof(ewma_policy_circ_data_t));
 261   tor_free(cdata);
 262 }
 263
 264 /**
 265  * Handle circuit activation; this inserts the circuit's cell_ewma into
 266  * the active_circuits_pqueue.
 267  */
 268
 269 static void
 270 ewma_notify_circ_active(circuitmux_t *cmux,
 271                         circuitmux_policy_data_t *pol_data,
 272                         circuit_t *circ,
 273                         circuitmux_policy_circ_data_t *pol_circ_data)
 274 {
 275   ewma_policy_data_t *pol = NULL;
 276   ewma_policy_circ_data_t *cdata = NULL;
 277
 278   tor_assert(cmux);
 279   tor_assert(pol_data);
 280   tor_assert(circ);
 281   tor_assert(pol_circ_data);
 282
 283   pol = TO_EWMA_POL_DATA(pol_data);
 284   cdata = TO_EWMA_POL_CIRC_DATA(pol_circ_data);
 285
 286   add_cell_ewma(pol, &(cdata->cell_ewma));
 287 }
 288
 289 /**
 290  * Handle circuit deactivation; this removes the circuit's cell_ewma from
 291  * the active_circuits_pqueue.
 292  */
 293
 294 static void
 295 ewma_notify_circ_inactive(circuitmux_t *cmux,
 296                           circuitmux_policy_data_t *pol_data,
 297                           circuit_t *circ,
 298                           circuitmux_policy_circ_data_t *pol_circ_data)
 299 {
 300   ewma_policy_data_t *pol = NULL;
 301   ewma_policy_circ_data_t *cdata = NULL;
 302
 303   tor_assert(cmux);
 304   tor_assert(pol_data);
 305   tor_assert(circ);
 306   tor_assert(pol_circ_data);
 307
 308   pol = TO_EWMA_POL_DATA(pol_data);
 309   cdata = TO_EWMA_POL_CIRC_DATA(pol_circ_data);
 310
 311   remove_cell_ewma(pol, &(cdata->cell_ewma));
 312 }
 313
 314 /**
 315  * Update cell_ewma for this circuit after we've sent some cells, and
 316  * remove/reinsert it in the queue.  This used to be done (brokenly,
 317  * see bug 6816) in channel_flush_from_first_active_circuit().
 318  */
 319
 320 static void
 321 ewma_notify_xmit_cells(circuitmux_t *cmux,
 322                        circuitmux_policy_data_t *pol_data,
 323                        circuit_t *circ,
 324                        circuitmux_policy_circ_data_t *pol_circ_data,
 325                        unsigned int n_cells)
 326 {
 327   ewma_policy_data_t *pol = NULL;
 328   ewma_policy_circ_data_t *cdata = NULL;
 329   unsigned int tick;
 330   double fractional_tick, ewma_increment;
 331   cell_ewma_t *cell_ewma, *tmp;
 332
 333   tor_assert(cmux);
 334   tor_assert(pol_data);
 335   tor_assert(circ);
 336   tor_assert(pol_circ_data);
 337   tor_assert(n_cells > 0);
 338
 339   pol = TO_EWMA_POL_DATA(pol_data);
 340   cdata = TO_EWMA_POL_CIRC_DATA(pol_circ_data);
 341
 342   /* Rescale the EWMAs if needed */
 343   tick = cell_ewma_get_current_tick_and_fraction(&fractional_tick);
 344
 345   if (tick != pol->active_circuit_pqueue_last_recalibrated) {
 346     scale_active_circuits(pol, tick);
 347   }
 348
 349   /* How much do we adjust the cell count in cell_ewma by? */
 350   ewma_increment =
 351     ((double)(n_cells)) * pow(ewma_scale_factor, -fractional_tick);
 352
 353   /* Do the adjustment */
 354   cell_ewma = &(cdata->cell_ewma);
 355   cell_ewma->cell_count += ewma_increment;
 356
 357   /*
 358    * Since we just sent on this circuit, it should be at the head of
 359    * the queue.  Pop the head, assert that it matches, then re-add.
 360    */
 361   tmp = pop_first_cell_ewma(pol);
 362   tor_assert(tmp == cell_ewma);
 363   add_cell_ewma(pol, cell_ewma);
 364 }
 365
 366 /**
 367  * Pick the preferred circuit to send from; this will be the one with
 368  * the lowest EWMA value in the priority queue.  This used to be done
 369  * in channel_flush_from_first_active_circuit().
 370  */
 371
 372 static circuit_t *
 373 ewma_pick_active_circuit(circuitmux_t *cmux,
 374                          circuitmux_policy_data_t *pol_data)
 375 {
 376   ewma_policy_data_t *pol = NULL;
 377   circuit_t *circ = NULL;
 378   cell_ewma_t *cell_ewma = NULL;
 379
 380   tor_assert(cmux);
 381   tor_assert(pol_data);
 382
 383   pol = TO_EWMA_POL_DATA(pol_data);
 384
 385   if (smartlist_len(pol->active_circuit_pqueue) > 0) {
 386     /* Get the head of the queue */
 387     cell_ewma = smartlist_get(pol->active_circuit_pqueue, 0);
 388     circ = cell_ewma_to_circuit(cell_ewma);
 389   }
 390
 391   return circ;
 392 }
 393
 394 /**
 395  * Compare two EWMA cmuxes, and return -1, 0 or 1 to indicate which should
 396  * be more preferred - see circuitmux_compare_muxes() of circuitmux.c.
 397  */
 398
 399 static int
 400 ewma_cmp_cmux(circuitmux_t *cmux_1, circuitmux_policy_data_t *pol_data_1,
 401               circuitmux_t *cmux_2, circuitmux_policy_data_t *pol_data_2)
 402 {
 403   ewma_policy_data_t *p1 = NULL, *p2 = NULL;
 404   cell_ewma_t *ce1 = NULL, *ce2 = NULL;
 405
 406   tor_assert(cmux_1);
 407   tor_assert(pol_data_1);
 408   tor_assert(cmux_2);
 409   tor_assert(pol_data_2);
 410
 411   p1 = TO_EWMA_POL_DATA(pol_data_1);
 412   p2 = TO_EWMA_POL_DATA(pol_data_2);
 413
 414   if (p1 != p2) {
 415     /* Get the head cell_ewma_t from each queue */
 416     if (smartlist_len(p1->active_circuit_pqueue) > 0) {
 417       ce1 = smartlist_get(p1->active_circuit_pqueue, 0);
 418     }
 419
 420     if (smartlist_len(p2->active_circuit_pqueue) > 0) {
 421       ce2 = smartlist_get(p2->active_circuit_pqueue, 0);
 422     }
 423
 424     /* Got both of them? */
 425     if (ce1 != NULL && ce2 != NULL) {
 426       /* Pick whichever one has the better best circuit */
 427       return compare_cell_ewma_counts(ce1, ce2);
 428     } else {
 429       if (ce1 != NULL) {
 430         /* We only have a circuit on cmux_1, so prefer it */
 431         return -1;
 432       } else if (ce2 != NULL) {
 433         /* We only have a circuit on cmux_2, so prefer it */
 434         return 1;
 435       } else {
 436         /* No circuits at all; no preference */
 437         return 0;
 438       }
 439     }
 440   } else {
 441     /* We got identical params */
 442     return 0;
 443   }
 444 }
 445
 446 /** Helper for sorting cell_ewma_t values in their priority queue. */
 447 static int
 448 compare_cell_ewma_counts(const void *p1, const void *p2)
 449 {
 450   const cell_ewma_t *e1 = p1, *e2 = p2;
 451
 452   if (e1->cell_count < e2->cell_count)
 453     return -1;
 454   else if (e1->cell_count > e2->cell_count)
 455     return 1;
 456   else
 457     return 0;
 458 }
 459
 460 /** Given a cell_ewma_t, return a pointer to the circuit containing it. */
 461 static circuit_t *
 462 cell_ewma_to_circuit(cell_ewma_t *ewma)
 463 {
 464   ewma_policy_circ_data_t *cdata = NULL;
 465
 466   tor_assert(ewma);
 467   cdata = SUBTYPE_P(ewma, ewma_policy_circ_data_t, cell_ewma);
 468   tor_assert(cdata);
 469
 470   return cdata->circ;
 471 }
 472
 473 /* ==== Functions for scaling cell_ewma_t ====
 474
 475    When choosing which cells to relay first, we favor circuits that have been
 476    quiet recently.  This gives better latency on connections that aren't
 477    pushing lots of data, and makes the network feel more interactive.
 478
 479    Conceptually, we take an exponentially weighted mean average of the number
 480    of cells a circuit has sent, and allow active circuits (those with cells to
 481    relay) to send cells in reverse order of their exponentially-weighted mean
 482    average (EWMA) cell count.  [That is, a cell sent N seconds ago 'counts'
 483    F^N times as much as a cell sent now, for 0<F<1.0, and we favor the
 484    circuit that has sent the fewest cells]
 485
 486    If 'double' had infinite precision, we could do this simply by counting a
 487    cell sent at startup as having weight 1.0, and a cell sent N seconds later
 488    as having weight F^-N.  This way, we would never need to re-scale
 489    any already-sent cells.
 490
 491    To prevent double from overflowing, we could count a cell sent now as
 492    having weight 1.0 and a cell sent N seconds ago as having weight F^N.
 493    This, however, would mean we'd need to re-scale *ALL* old circuits every
 494    time we wanted to send a cell.
 495
 496    So as a compromise, we divide time into 'ticks' (currently, 10-second
 497    increments) and say that a cell sent at the start of a current tick is
 498    worth 1.0, a cell sent N seconds before the start of the current tick is
 499    worth F^N, and a cell sent N seconds after the start of the current tick is
 500    worth F^-N.  This way we don't overflow, and we don't need to constantly
 501    rescale.
 502  */
 503
 504 /**
 505  * Initialize the system that tells which ewma tick we are in.
 506  */
 507 STATIC void
 508 cell_ewma_initialize_ticks(void)
 509 {
 510   if (ewma_ticks_initialized)
 511     return;
 512   monotime_coarse_get(&start_of_current_tick);
 513   crypto_rand((char*)&current_tick_num, sizeof(current_tick_num));
 514   ewma_ticks_initialized = 1;
 515 }
 516
 517 /** Compute the current cell_ewma tick and the fraction of the tick that has
 518  * elapsed between the start of the tick and the current time.  Return the
 519  * former and store the latter in *<b>remainder_out</b>.
 520  *
 521  * These tick values are not meant to be shared between Tor instances, or used
 522  * for other purposes. */
 523 STATIC unsigned
 524 cell_ewma_get_current_tick_and_fraction(double *remainder_out)
 525 {
 526   if (BUG(!ewma_ticks_initialized)) {
 527     cell_ewma_initialize_ticks(); // LCOV_EXCL_LINE
 528   }
 529   monotime_coarse_t now;
 530   monotime_coarse_get(&now);
 531   int32_t msec_diff = monotime_coarse_diff_msec32(&start_of_current_tick,
 532                                                   &now);
 533   if (msec_diff > (1000*ewma_tick_len)) {
 534     unsigned ticks_difference = msec_diff / (1000*ewma_tick_len);
 535     monotime_coarse_add_msec(&start_of_current_tick,
 536                              &start_of_current_tick,
 537                              ticks_difference * 1000 * ewma_tick_len);
 538     current_tick_num += ticks_difference;
 539     msec_diff %= 1000*ewma_tick_len;
 540   }
 541   *remainder_out = ((double)msec_diff) / (1.0e3 * ewma_tick_len);
 542   return current_tick_num;
 543 }
 544
 545 /* Default value for the CircuitPriorityHalflifeMsec consensus parameter in
 546  * msec. */
 547 #define CMUX_PRIORITY_HALFLIFE_MSEC_DEFAULT 30000
 548 /* Minimum and maximum value for the CircuitPriorityHalflifeMsec consensus
 549  * parameter. */
 550 #define CMUX_PRIORITY_HALFLIFE_MSEC_MIN 1
 551 #define CMUX_PRIORITY_HALFLIFE_MSEC_MAX INT32_MAX
 552
 553 /* Return the value of the circuit priority halflife from the options if
 554  * available or else from the consensus (in that order). If none can be found,
 555  * a default value is returned.
 556  *
 557  * The source_msg points to a string describing from where the value was
 558  * picked so it can be used for logging. */
 559 static double
 560 get_circuit_priority_halflife(const or_options_t *options,
 561                               const networkstatus_t *consensus,
 562                               const char **source_msg)
 563 {
 564   int32_t halflife_ms;
 565   double halflife;
 566   /* Compute the default value now. We might need it. */
 567   double halflife_default =
 568     ((double) CMUX_PRIORITY_HALFLIFE_MSEC_DEFAULT) / 1000.0;
 569
 570   /* Try to get it from configuration file first. */
 571   if (options && options->CircuitPriorityHalflife >= -EPSILON) {
 572     halflife = options->CircuitPriorityHalflife;
 573     *source_msg = "CircuitPriorityHalflife in configuration";
 574     goto end;
 575   }
 576
 577   /* Try to get the msec value from the consensus. */
 578   halflife_ms = networkstatus_get_param(consensus,
 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";
 585
 586  end:
 587   /* We should never go below the EPSILON else we would consider it disabled
 588    * and we can't have that. */
 589   if (halflife < EPSILON) {
 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;
 594   }
 595   return halflife;
 596 }
 597
 598 /** Adjust the global cell scale factor based on <b>options</b> */
 599 void
 600 cmux_ewma_set_options(const or_options_t *options,
 601                       const networkstatus_t *consensus)
 602 {
 603   double halflife;
 604   const char *source;
 605
 606   cell_ewma_initialize_ticks();
 607
 608   /* Both options and consensus can be NULL. This assures us to either get a
 609    * valid configured value or the default one. */
 610   halflife = get_circuit_priority_halflife(options, consensus, &source);
 611   ewma_tick_len = networkstatus_get_param(consensus,
 612                                         "CircuitPriorityTickSecs",
 613                                         EWMA_TICK_LEN_DEFAULT,
 614                                         EWMA_TICK_LEN_MIN,
 615                                         EWMA_TICK_LEN_MAX);
 616
 617   /* convert halflife into halflife-per-tick. */
 618   halflife /= ewma_tick_len;
 619   /* compute per-tick scale factor. */
 620   ewma_scale_factor = exp(LOG_ONEHALF / halflife);
 621   log_info(LD_OR,
 622            "Enabled cell_ewma algorithm because of value in %s; "
 623            "scale factor is %f per %d seconds",
 624            source, ewma_scale_factor, ewma_tick_len);
 625 }
 626
 627 /** Return the multiplier necessary to convert the value of a cell sent in
 628  * 'from_tick' to one sent in 'to_tick'. */
 629 static inline double
 630 get_scale_factor(unsigned from_tick, unsigned to_tick)
 631 {
 632   /* This math can wrap around, but that's okay: unsigned overflow is
 633      well-defined */
 634   int diff = (int)(to_tick - from_tick);
 635   return pow(ewma_scale_factor, diff);
 636 }
 637
 638 /** Adjust the cell count of <b>ewma</b> so that it is scaled with respect to
 639  * <b>cur_tick</b> */
 640 static void
 641 scale_single_cell_ewma(cell_ewma_t *ewma, unsigned cur_tick)
 642 {
 643   double factor = get_scale_factor(ewma->last_adjusted_tick, cur_tick);
 644   ewma->cell_count *= factor;
 645   ewma->last_adjusted_tick = cur_tick;
 646 }
 647
 648 /** Adjust the cell count of every active circuit on <b>chan</b> so
 649  * that they are scaled with respect to <b>cur_tick</b> */
 650 static void
 651 scale_active_circuits(ewma_policy_data_t *pol, unsigned cur_tick)
 652 {
 653   double factor;
 654
 655   tor_assert(pol);
 656   tor_assert(pol->active_circuit_pqueue);
 657
 658   factor =
 659     get_scale_factor(
 660       pol->active_circuit_pqueue_last_recalibrated,
 661       cur_tick);
 662   /** Ordinarily it isn't okay to change the value of an element in a heap,
 663    * but it's okay here, since we are preserving the order. */
 664   SMARTLIST_FOREACH_BEGIN(
 665       pol->active_circuit_pqueue,
 666       cell_ewma_t *, e) {
 667     tor_assert(e->last_adjusted_tick ==
 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;
 673 }
 674
 675 /** Rescale <b>ewma</b> to the same scale as <b>pol</b>, and add it to
 676  * <b>pol</b>'s priority queue of active circuits */
 677 static void
 678 add_cell_ewma(ewma_policy_data_t *pol, cell_ewma_t *ewma)
 679 {
 680   tor_assert(pol);
 681   tor_assert(pol->active_circuit_pqueue);
 682   tor_assert(ewma);
 683   tor_assert(ewma->heap_index == -1);
 684
 685   scale_single_cell_ewma(
 686       ewma,
 687       pol->active_circuit_pqueue_last_recalibrated);
 688
 689   smartlist_pqueue_add(pol->active_circuit_pqueue,
 690                        compare_cell_ewma_counts,
 691                        offsetof(cell_ewma_t, heap_index),
 692                        ewma);
 693 }
 694
 695 /** Remove <b>ewma</b> from <b>pol</b>'s priority queue of active circuits */
 696 static void
 697 remove_cell_ewma(ewma_policy_data_t *pol, cell_ewma_t *ewma)
 698 {
 699   tor_assert(pol);
 700   tor_assert(pol->active_circuit_pqueue);
 701   tor_assert(ewma);
 702   tor_assert(ewma->heap_index != -1);
 703
 704   smartlist_pqueue_remove(pol->active_circuit_pqueue,
 705                           compare_cell_ewma_counts,
 706                           offsetof(cell_ewma_t, heap_index),
 707                           ewma);
 708 }
 709
 710 /** Remove and return the first cell_ewma_t from pol's priority queue of
 711  * active circuits.  Requires that the priority queue is nonempty. */
 712 static cell_ewma_t *
 713 pop_first_cell_ewma(ewma_policy_data_t *pol)
 714 {
 715   tor_assert(pol);
 716   tor_assert(pol->active_circuit_pqueue);
 717
 718   return smartlist_pqueue_pop(pol->active_circuit_pqueue,
 719                               compare_cell_ewma_counts,
 720                               offsetof(cell_ewma_t, heap_index));
 721 }
 722
 723 /**
 724  * Drop all resources held by circuitmux_ewma.c, and deinitialize the
 725  * module. */
 726 void
 727 circuitmux_ewma_free_all(void)
 728 {
 729   ewma_ticks_initialized = 0;
 730 }