src/or/circuitmux_ewma.c

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