circuitmux_ewma.c (24125B)
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*)¤t_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 }