src/or/circuitmux_ewma.c

   1 /* * Copyright (c) 2012-2013, 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
 191 /*** EWMA global variables ***/
 192
 193 /** The per-tick scale factor to be used when computing cell-count EWMA
 194  * values.  (A cell sent N ticks before the start of the current tick
 195  * has value ewma_scale_factor ** N.)
 196  */
 197 static double ewma_scale_factor = 0.1;
 198 /* DOCDOC ewma_enabled */
 199 static int ewma_enabled = 0;
 200
 201 /*** EWMA circuitmux_policy_t method table ***/
 202
 203 circuitmux_policy_t ewma_policy = {
 204   /*.alloc_cmux_data =*/ ewma_alloc_cmux_data,
 205   /*.free_cmux_data =*/ ewma_free_cmux_data,
 206   /*.alloc_circ_data =*/ ewma_alloc_circ_data,
 207   /*.free_circ_data =*/ ewma_free_circ_data,
 208   /*.notify_circ_active =*/ ewma_notify_circ_active,
 209   /*.notify_circ_inactive =*/ ewma_notify_circ_inactive,
 210   /*.notify_set_n_cells =*/ NULL, /* EWMA doesn't need this */
 211   /*.notify_xmit_cells =*/ ewma_notify_xmit_cells,
 212   /*.pick_active_circuit =*/ ewma_pick_active_circuit
 213 };
 214
 215 /*** EWMA method implementations using the below EWMA helper functions ***/
 216
 217 /**
 218  * Allocate an ewma_policy_data_t and upcast it to a circuitmux_policy_data_t;
 219  * this is called when setting the policy on a circuitmux_t to ewma_policy.
 220  */
 221
 222 static circuitmux_policy_data_t *
 223 ewma_alloc_cmux_data(circuitmux_t *cmux)
 224 {
 225   ewma_policy_data_t *pol = NULL;
 226
 227   tor_assert(cmux);
 228
 229   pol = tor_malloc_zero(sizeof(*pol));
 230   pol->base_.magic = EWMA_POL_DATA_MAGIC;
 231   pol->active_circuit_pqueue = smartlist_new();
 232   pol->active_circuit_pqueue_last_recalibrated = cell_ewma_get_tick();
 233
 234   return TO_CMUX_POL_DATA(pol);
 235 }
 236
 237 /**
 238  * Free an ewma_policy_data_t allocated with ewma_alloc_cmux_data()
 239  */
 240
 241 static void
 242 ewma_free_cmux_data(circuitmux_t *cmux,
 243                     circuitmux_policy_data_t *pol_data)
 244 {
 245   ewma_policy_data_t *pol = NULL;
 246
 247   tor_assert(cmux);
 248   if (!pol_data) return;
 249
 250   pol = TO_EWMA_POL_DATA(pol_data);
 251
 252   smartlist_free(pol->active_circuit_pqueue);
 253   tor_free(pol);
 254 }
 255
 256 /**
 257  * Allocate an ewma_policy_circ_data_t and upcast it to a
 258  * circuitmux_policy_data_t; this is called when attaching a circuit to a
 259  * circuitmux_t with ewma_policy.
 260  */
 261
 262 static circuitmux_policy_circ_data_t *
 263 ewma_alloc_circ_data(circuitmux_t *cmux,
 264                      circuitmux_policy_data_t *pol_data,
 265                      circuit_t *circ,
 266                      cell_direction_t direction,
 267                      unsigned int cell_count)
 268 {
 269   ewma_policy_circ_data_t *cdata = NULL;
 270
 271   tor_assert(cmux);
 272   tor_assert(pol_data);
 273   tor_assert(circ);
 274   tor_assert(direction == CELL_DIRECTION_OUT ||
 275              direction == CELL_DIRECTION_IN);
 276   /* Shut the compiler up */
 277   tor_assert(cell_count == cell_count);
 278
 279   cdata = tor_malloc_zero(sizeof(*cdata));
 280   cdata->base_.magic = EWMA_POL_CIRC_DATA_MAGIC;
 281   cdata->circ = circ;
 282
 283   /*
 284    * Initialize the cell_ewma_t structure (formerly in
 285    * init_circuit_base())
 286    */
 287   cdata->cell_ewma.last_adjusted_tick = cell_ewma_get_tick();
 288   cdata->cell_ewma.cell_count = 0.0;
 289   cdata->cell_ewma.heap_index = -1;
 290   if (direction == CELL_DIRECTION_IN) {
 291     cdata->cell_ewma.is_for_p_chan = 1;
 292   } else {
 293     cdata->cell_ewma.is_for_p_chan = 0;
 294   }
 295
 296   return TO_CMUX_POL_CIRC_DATA(cdata);
 297 }
 298
 299 /**
 300  * Free an ewma_policy_circ_data_t allocated with ewma_alloc_circ_data()
 301  */
 302
 303 static void
 304 ewma_free_circ_data(circuitmux_t *cmux,
 305                     circuitmux_policy_data_t *pol_data,
 306                     circuit_t *circ,
 307                     circuitmux_policy_circ_data_t *pol_circ_data)
 308
 309 {
 310   ewma_policy_circ_data_t *cdata = NULL;
 311
 312   tor_assert(cmux);
 313   tor_assert(circ);
 314   tor_assert(pol_data);
 315
 316   if (!pol_circ_data) return;
 317
 318   cdata = TO_EWMA_POL_CIRC_DATA(pol_circ_data);
 319
 320   tor_free(cdata);
 321 }
 322
 323 /**
 324  * Handle circuit activation; this inserts the circuit's cell_ewma into
 325  * the active_circuits_pqueue.
 326  */
 327
 328 static void
 329 ewma_notify_circ_active(circuitmux_t *cmux,
 330                         circuitmux_policy_data_t *pol_data,
 331                         circuit_t *circ,
 332                         circuitmux_policy_circ_data_t *pol_circ_data)
 333 {
 334   ewma_policy_data_t *pol = NULL;
 335   ewma_policy_circ_data_t *cdata = NULL;
 336
 337   tor_assert(cmux);
 338   tor_assert(pol_data);
 339   tor_assert(circ);
 340   tor_assert(pol_circ_data);
 341
 342   pol = TO_EWMA_POL_DATA(pol_data);
 343   cdata = TO_EWMA_POL_CIRC_DATA(pol_circ_data);
 344
 345   add_cell_ewma(pol, &(cdata->cell_ewma));
 346 }
 347
 348 /**
 349  * Handle circuit deactivation; this removes the circuit's cell_ewma from
 350  * the active_circuits_pqueue.
 351  */
 352
 353 static void
 354 ewma_notify_circ_inactive(circuitmux_t *cmux,
 355                           circuitmux_policy_data_t *pol_data,
 356                           circuit_t *circ,
 357                           circuitmux_policy_circ_data_t *pol_circ_data)
 358 {
 359   ewma_policy_data_t *pol = NULL;
 360   ewma_policy_circ_data_t *cdata = NULL;
 361
 362   tor_assert(cmux);
 363   tor_assert(pol_data);
 364   tor_assert(circ);
 365   tor_assert(pol_circ_data);
 366
 367   pol = TO_EWMA_POL_DATA(pol_data);
 368   cdata = TO_EWMA_POL_CIRC_DATA(pol_circ_data);
 369
 370   remove_cell_ewma(pol, &(cdata->cell_ewma));
 371 }
 372
 373 /**
 374  * Update cell_ewma for this circuit after we've sent some cells, and
 375  * remove/reinsert it in the queue.  This used to be done (brokenly,
 376  * see bug 6816) in channel_flush_from_first_active_circuit().
 377  */
 378
 379 static void
 380 ewma_notify_xmit_cells(circuitmux_t *cmux,
 381                        circuitmux_policy_data_t *pol_data,
 382                        circuit_t *circ,
 383                        circuitmux_policy_circ_data_t *pol_circ_data,
 384                        unsigned int n_cells)
 385 {
 386   ewma_policy_data_t *pol = NULL;
 387   ewma_policy_circ_data_t *cdata = NULL;
 388   unsigned int tick;
 389   double fractional_tick, ewma_increment;
 390   /* The current (hi-res) time */
 391   struct timeval now_hires;
 392   cell_ewma_t *cell_ewma, *tmp;
 393
 394   tor_assert(cmux);
 395   tor_assert(pol_data);
 396   tor_assert(circ);
 397   tor_assert(pol_circ_data);
 398   tor_assert(n_cells > 0);
 399
 400   pol = TO_EWMA_POL_DATA(pol_data);
 401   cdata = TO_EWMA_POL_CIRC_DATA(pol_circ_data);
 402
 403   /* Rescale the EWMAs if needed */
 404   tor_gettimeofday_cached(&now_hires);
 405   tick = cell_ewma_tick_from_timeval(&now_hires, &fractional_tick);
 406
 407   if (tick != pol->active_circuit_pqueue_last_recalibrated) {
 408     scale_active_circuits(pol, tick);
 409   }
 410
 411   /* How much do we adjust the cell count in cell_ewma by? */
 412   ewma_increment =
 413     ((double)(n_cells)) * pow(ewma_scale_factor, -fractional_tick);
 414
 415   /* Do the adjustment */
 416   cell_ewma = &(cdata->cell_ewma);
 417   cell_ewma->cell_count += ewma_increment;
 418
 419   /*
 420    * Since we just sent on this circuit, it should be at the head of
 421    * the queue.  Pop the head, assert that it matches, then re-add.
 422    */
 423   tmp = pop_first_cell_ewma(pol);
 424   tor_assert(tmp == cell_ewma);
 425   add_cell_ewma(pol, cell_ewma);
 426 }
 427
 428 /**
 429  * Pick the preferred circuit to send from; this will be the one with
 430  * the lowest EWMA value in the priority queue.  This used to be done
 431  * in channel_flush_from_first_active_circuit().
 432  */
 433
 434 static circuit_t *
 435 ewma_pick_active_circuit(circuitmux_t *cmux,
 436                          circuitmux_policy_data_t *pol_data)
 437 {
 438   ewma_policy_data_t *pol = NULL;
 439   circuit_t *circ = NULL;
 440   cell_ewma_t *cell_ewma = NULL;
 441
 442   tor_assert(cmux);
 443   tor_assert(pol_data);
 444
 445   pol = TO_EWMA_POL_DATA(pol_data);
 446
 447   if (smartlist_len(pol->active_circuit_pqueue) > 0) {
 448     /* Get the head of the queue */
 449     cell_ewma = smartlist_get(pol->active_circuit_pqueue, 0);
 450     circ = cell_ewma_to_circuit(cell_ewma);
 451   }
 452
 453   return circ;
 454 }
 455
 456 /** Helper for sorting cell_ewma_t values in their priority queue. */
 457 static int
 458 compare_cell_ewma_counts(const void *p1, const void *p2)
 459 {
 460   const cell_ewma_t *e1 = p1, *e2 = p2;
 461
 462   if (e1->cell_count < e2->cell_count)
 463     return -1;
 464   else if (e1->cell_count > e2->cell_count)
 465     return 1;
 466   else
 467     return 0;
 468 }
 469
 470 /** Given a cell_ewma_t, return a pointer to the circuit containing it. */
 471 static circuit_t *
 472 cell_ewma_to_circuit(cell_ewma_t *ewma)
 473 {
 474   ewma_policy_circ_data_t *cdata = NULL;
 475
 476   tor_assert(ewma);
 477   cdata = SUBTYPE_P(ewma, ewma_policy_circ_data_t, cell_ewma);
 478   tor_assert(cdata);
 479
 480   return cdata->circ;
 481 }
 482
 483 /* ==== Functions for scaling cell_ewma_t ====
 484
 485    When choosing which cells to relay first, we favor circuits that have been
 486    quiet recently.  This gives better latency on connections that aren't
 487    pushing lots of data, and makes the network feel more interactive.
 488
 489    Conceptually, we take an exponentially weighted mean average of the number
 490    of cells a circuit has sent, and allow active circuits (those with cells to
 491    relay) to send cells in reverse order of their exponentially-weighted mean
 492    average (EWMA) cell count.  [That is, a cell sent N seconds ago 'counts'
 493    F^N times as much as a cell sent now, for 0<F<1.0, and we favor the
 494    circuit that has sent the fewest cells]
 495
 496    If 'double' had infinite precision, we could do this simply by counting a
 497    cell sent at startup as having weight 1.0, and a cell sent N seconds later
 498    as having weight F^-N.  This way, we would never need to re-scale
 499    any already-sent cells.
 500
 501    To prevent double from overflowing, we could count a cell sent now as
 502    having weight 1.0 and a cell sent N seconds ago as having weight F^N.
 503    This, however, would mean we'd need to re-scale *ALL* old circuits every
 504    time we wanted to send a cell.
 505
 506    So as a compromise, we divide time into 'ticks' (currently, 10-second
 507    increments) and say that a cell sent at the start of a current tick is
 508    worth 1.0, a cell sent N seconds before the start of the current tick is
 509    worth F^N, and a cell sent N seconds after the start of the current tick is
 510    worth F^-N.  This way we don't overflow, and we don't need to constantly
 511    rescale.
 512  */
 513
 514 /** Given a timeval <b>now</b>, compute the cell_ewma tick in which it occurs
 515  * and the fraction of the tick that has elapsed between the start of the tick
 516  * and <b>now</b>.  Return the former and store the latter in
 517  * *<b>remainder_out</b>.
 518  *
 519  * These tick values are not meant to be shared between Tor instances, or used
 520  * for other purposes. */
 521
 522 static unsigned
 523 cell_ewma_tick_from_timeval(const struct timeval *now,
 524                             double *remainder_out)
 525 {
 526   unsigned res = (unsigned) (now->tv_sec / EWMA_TICK_LEN);
 527   /* rem */
 528   double rem = (now->tv_sec % EWMA_TICK_LEN) +
 529     ((double)(now->tv_usec)) / 1.0e6;
 530   *remainder_out = rem / EWMA_TICK_LEN;
 531   return res;
 532 }
 533
 534 /** Tell the caller whether ewma_enabled is set */
 535 int
 536 cell_ewma_enabled(void)
 537 {
 538   return ewma_enabled;
 539 }
 540
 541 /** Compute and return the current cell_ewma tick. */
 542 unsigned int
 543 cell_ewma_get_tick(void)
 544 {
 545   return ((unsigned)approx_time() / EWMA_TICK_LEN);
 546 }
 547
 548 /** Adjust the global cell scale factor based on <b>options</b> */
 549 void
 550 cell_ewma_set_scale_factor(const or_options_t *options,
 551                            const networkstatus_t *consensus)
 552 {
 553   int32_t halflife_ms;
 554   double halflife;
 555   const char *source;
 556   if (options && options->CircuitPriorityHalflife >= -EPSILON) {
 557     halflife = options->CircuitPriorityHalflife;
 558     source = "CircuitPriorityHalflife in configuration";
 559   } else if (consensus && (halflife_ms = networkstatus_get_param(
 560                  consensus, "CircuitPriorityHalflifeMsec",
 561                  -1, -1, INT32_MAX)) >= 0) {
 562     halflife = ((double)halflife_ms)/1000.0;
 563     source = "CircuitPriorityHalflifeMsec in consensus";
 564   } else {
 565     halflife = EWMA_DEFAULT_HALFLIFE;
 566     source = "Default value";
 567   }
 568
 569   if (halflife <= EPSILON) {
 570     /* The cell EWMA algorithm is disabled. */
 571     ewma_scale_factor = 0.1;
 572     ewma_enabled = 0;
 573     log_info(LD_OR,
 574              "Disabled cell_ewma algorithm because of value in %s",
 575              source);
 576   } else {
 577     /* convert halflife into halflife-per-tick. */
 578     halflife /= EWMA_TICK_LEN;
 579     /* compute per-tick scale factor. */
 580     ewma_scale_factor = exp( LOG_ONEHALF / halflife );
 581     ewma_enabled = 1;
 582     log_info(LD_OR,
 583              "Enabled cell_ewma algorithm because of value in %s; "
 584              "scale factor is %f per %d seconds",
 585              source, ewma_scale_factor, EWMA_TICK_LEN);
 586   }
 587 }
 588
 589 /** Return the multiplier necessary to convert the value of a cell sent in
 590  * 'from_tick' to one sent in 'to_tick'. */
 591 static INLINE double
 592 get_scale_factor(unsigned from_tick, unsigned to_tick)
 593 {
 594   /* This math can wrap around, but that's okay: unsigned overflow is
 595      well-defined */
 596   int diff = (int)(to_tick - from_tick);
 597   return pow(ewma_scale_factor, diff);
 598 }
 599
 600 /** Adjust the cell count of <b>ewma</b> so that it is scaled with respect to
 601  * <b>cur_tick</b> */
 602 static void
 603 scale_single_cell_ewma(cell_ewma_t *ewma, unsigned cur_tick)
 604 {
 605   double factor = get_scale_factor(ewma->last_adjusted_tick, cur_tick);
 606   ewma->cell_count *= factor;
 607   ewma->last_adjusted_tick = cur_tick;
 608 }
 609
 610 /** Adjust the cell count of every active circuit on <b>chan</b> so
 611  * that they are scaled with respect to <b>cur_tick</b> */
 612 static void
 613 scale_active_circuits(ewma_policy_data_t *pol, unsigned cur_tick)
 614 {
 615   double factor;
 616
 617   tor_assert(pol);
 618   tor_assert(pol->active_circuit_pqueue);
 619
 620   factor =
 621     get_scale_factor(
 622       pol->active_circuit_pqueue_last_recalibrated,
 623       cur_tick);
 624   /** Ordinarily it isn't okay to change the value of an element in a heap,
 625    * but it's okay here, since we are preserving the order. */
 626   SMARTLIST_FOREACH_BEGIN(
 627       pol->active_circuit_pqueue,
 628       cell_ewma_t *, e) {
 629     tor_assert(e->last_adjusted_tick ==
 630                pol->active_circuit_pqueue_last_recalibrated);
 631     e->cell_count *= factor;
 632     e->last_adjusted_tick = cur_tick;
 633   } SMARTLIST_FOREACH_END(e);
 634   pol->active_circuit_pqueue_last_recalibrated = cur_tick;
 635 }
 636
 637 /** Rescale <b>ewma</b> to the same scale as <b>pol</b>, and add it to
 638  * <b>pol</b>'s priority queue of active circuits */
 639 static void
 640 add_cell_ewma(ewma_policy_data_t *pol, cell_ewma_t *ewma)
 641 {
 642   tor_assert(pol);
 643   tor_assert(pol->active_circuit_pqueue);
 644   tor_assert(ewma);
 645   tor_assert(ewma->heap_index == -1);
 646
 647   scale_single_cell_ewma(
 648       ewma,
 649       pol->active_circuit_pqueue_last_recalibrated);
 650
 651   smartlist_pqueue_add(pol->active_circuit_pqueue,
 652                        compare_cell_ewma_counts,
 653                        STRUCT_OFFSET(cell_ewma_t, heap_index),
 654                        ewma);
 655 }
 656
 657 /** Remove <b>ewma</b> from <b>pol</b>'s priority queue of active circuits */
 658 static void
 659 remove_cell_ewma(ewma_policy_data_t *pol, cell_ewma_t *ewma)
 660 {
 661   tor_assert(pol);
 662   tor_assert(pol->active_circuit_pqueue);
 663   tor_assert(ewma);
 664   tor_assert(ewma->heap_index != -1);
 665
 666   smartlist_pqueue_remove(pol->active_circuit_pqueue,
 667                           compare_cell_ewma_counts,
 668                           STRUCT_OFFSET(cell_ewma_t, heap_index),
 669                           ewma);
 670 }
 671
 672 /** Remove and return the first cell_ewma_t from pol's priority queue of
 673  * active circuits.  Requires that the priority queue is nonempty. */
 674 static cell_ewma_t *
 675 pop_first_cell_ewma(ewma_policy_data_t *pol)
 676 {
 677   tor_assert(pol);
 678   tor_assert(pol->active_circuit_pqueue);
 679
 680   return smartlist_pqueue_pop(pol->active_circuit_pqueue,
 681                               compare_cell_ewma_counts,
 682                               STRUCT_OFFSET(cell_ewma_t, heap_index));
 683 }
 684